Thanks for taking the time to look at this. But I recounted, and I count 765 hex (with the formatting I get in my mail, 11 lines of 68 hex + 17 hex at the end), which gives 3060 bits. Considering that the first hex is 1 and can be represented in 1 bit, not for, that would give 3060 - 3 = 3057 bits.
The modulus is the same size, but starts with 1D instead of 1F (the beginning of s^3), so s^3 is bigger. My bc library has a function called bits which returns the number of bits, I get 3057 in both cases, see bellow (also look at the value of m - s, which is negative, and modexp(s, 3, m) which doesn't have the form we want, but modexp(s/100, 3, m) does). But I seem to remember now that in openssl, mod(x, y) doesn't always return a value which is between 0 and y, maybe it would accept my s. Will try it. --Anton m 1D851D5148345606F586935D227CD5CF7F04F890AC5024178BA5F4EE85D7796918C3\ DC7A5951C985539CB240E28BA4AC3AFBE0F6EB3151A0DBAFD686C234A30D07D590D6\ 1A5474491BF0D68E1AC7F94CDC989C19C2E25B12511A29FFAF5F11E0B994E19C5C3D\ C298F9E584FFF3C7DBB8F703A0EAD97167F88C7229BBFA55B449CDE4C91B409D5B9A\ CF0134CB61352E9CE6CB3D847C7F3D9AFA74E8E19DD1ED7923270E310A5D91E97EF1\ 98694465950715AA066ACB06FAEC0BA64FCCCA155104852EFD41346F75D1ACB8574B\ BE3C7C8D6D1B501C1163AD2058506DF1B64059A6932C0672FB9D094364EA4D7FA044\ 42B8E643B74B8746B594866C7CBDAB8FEA954FDEE7C44B9C5D6B9E19B49082D65B51\ 7EA7DBFEF5CA1EEA39AB2283CDB854C8B246F2B8EFE51895349640248A3248EC65F6\ 4A89CA5AB194B444DF676B015AFBCACE13697CEEB5268F5E9AA674A83DD1B0CE4DC8\ 3603CFFB801DB669216FC647CD7A6A84831E421D9676C7AAC44411B2AB3E901A7139\ B3519B58EBAEEC20B s 7FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF\ FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF\ FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEAAEAD6EAB6B2B18EBD595822B1555\ AC5D20CF08046814578C2B994E1DBD8413A43C0564000000000 bits(m) BF1 bits(s^3) BF1 m - s^3 -27AE2AEB7CBA9F90A796CA2DD832A3080FB076F53AFDBE8745A0B117A288696E73C\ 2385A6AE367AAC634DBF1D745B53C5041F0914CEAE5F245029793DCB5CF2F82A6F29\ E5AB8BB6E40F2971E53806B3236763E63D1DA4DDB1E7E900E10140D0269B4003F3C2\ 7EACDEB5C1035A4765F029AF59AB74B1A6C2A091E14405AA4BB6321B36E4BF62A465\ 30FECB349ECAD1631934C27B8380C265058B171E622E1286DCD8F1CEF5A26E16810E\ 6796BB9A6DA29467C54B41AC61C95E3785A9F85D4578F21C056D03ECF9128580717D\ 563B5F437FEB9CDCAAE7E01D6C84F908AF5336EC3D710D6DF1F282A270E150F32438\ 31826C7843300F514A6B799383425470156AB021183BB4637CBCB87B1902C4D519D7\ 52B7C10EC94263DF2E26A5466F17150A2E4E2745BD967E5CC8352D58EE7A5237E637\ 3B36C59357EE1C3BCBBAE5A3EBFA812347B2D71FF03ECAD84A80E22419EA004D6C73\ 4BD35CE67B61094E6292B8E8BA5005F3D0F436A6C0EE1F47EDAFD37F94C16FE58EC6\ 4CAE64A7145113DF5 modexp(s, 3, m) 27AE2AEB7CBA9F90A796CA2DD832A3080FB076F53AFDBE8745A0B117A288696E73C2\ 385A6AE367AAC634DBF1D745B53C5041F0914CEAE5F245029793DCB5CF2F82A6F29E\ 5AB8BB6E40F2971E53806B3236763E63D1DA4DDB1E7E900E10140D0269B4003F3C27\ EACDEB5C1035A4765F029AF59AB74B1A6C2A091E14405AA4BB6321B36E4BF62A4653\ 0FECB349ECAD1631934C27B8380C265058B171E622E1286DCD8F1CEF5A26E16810E6\ 796BB9A6DA29467C54B41AC61C95E3785A9F85D4578F21C056D03ECF9128580717D5\ 63B5F437FEB9CDCAAE7E01D6C84F908AF5336EC3D710D6DF1F282A270E150F324383\ 1826C7843300F514A6B799383425470156AB021183BB4637CBCB87B1902C4D519D75\ 2B7C10EC94263DF2E26A5466F17150A2E4E2745BD967E5CC8352D58EE7A5237E6373\ B36C59357EE1C3BCBBAE5A3EBFA812347B2D71FF03ECAD84A80E22419EA004D6C734\ BD35CE67B61094E6292B8E8BA5005F3D0F436A6C0EE1F47EDAFD37F94C16FE58EC64\ CAE64A7145113DF5 modexp(s/100, 3, m) 1FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF\ FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF\ FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF003021300906052B0E03021A05000\ 4145D89B46034E0F41A920B2FA964E230EBB2D040B00000000000000000000000000\ 00000000000000000000000000000000000000000000000000000000000000000000\ 0000000002A9AA11CBB60CB35CB569DDD576C272967D774B02AE385C6EE43238C8C9\ 1477DBD0ED06ECF8BC4B8D3DC4D566FA65939092D09D13E0ED8F8BE5D5CB9E72C47C\ 743B52BBFA7B9697FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFDA285694CD9347AB7528\ D15F9D0DBF0C82C967D1C7CA3CCF69D2E09519FEAD7B96F1FCCB6D7D78AC9B244C2D\ 85C08FEE0982D080AB2250A546F64BF15B1C540EA5655A36E52756CC57BBB11BBA3B\ 81D72CE1FB7EBFB784027F3087CA7078541278C45764E6F2B1F3E532400000000000\ 00000000000 -----Original Message----- From: "Hal Finney" [mailto:[EMAIL PROTECTED] Sent: September 20, 2006 6:21 PM To: [EMAIL PROTECTED]; cryptography@metzdowd.com Subject: RE: Exponent 3 damage spreads... Anton Stiglic writes: > I tried coming up with my own forged signature that could be validated with > OpenSSL (which I intended to use to test other libraries). ... > Now let's look at s^3 > 1FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF\ > FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF\ > FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF003021300906052B0E03021A05000\ > 4145D89B46034E0F41A920B2FA964E230EBB2D040B00000000000000000000000000\ > 00000000000000000000000000000000000000000000000000000000000000000000\ > 0000000002A9AA11CBB60CB35CB569DDD576C272967D774B02AE385C6EE43238C8C9\ > 1477DBD0ED06ECF8BC4B8D3DC4D566FA65939092D09D13E0ED8F8BE5D5CB9E72C47C\ > 743B52BBFA7B9697FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFDA285694CD9347AB7528\ > D15F9D0DBF0C82C967D1C7CA3CCF69D2E09519FEAD7B96F1FCCB6D7D78AC9B244C2D\ > 85C08FEE0982D080AB2250A546F64BF15B1C540EA5655A36E52756CC57BBB11BBA3B\ > 81D72CE1FB7EBFB784027F3087CA7078541278C45764E6F2B1F3E532400000000000\ > 00000000000000000 > > This has the form we are looking for, the 01 FF FF ... FF header that ends > with 00, and then we have > 03021300906052B0E03021A050004145D89B46034E0F41A920B2FA964E230EBB2D040B0 > which is the d we started out with, and the rest is the GARBAGE part. > > Only one problem, s^3 is larger than m, so if we computed modexp(s, 3, m) > the result would be rounded out modulo m and we would loose the above > structure. This is not correct. I counted, and the number shown above has 762 hex digits. It is 3057 bits long, compared to m which is 3072 bits. It is not bigger than m, and does not need to be adjusted. 3057 is precisely the correct number of bits for a PKCS-1 padded value for a 3072 bit exponent. Hal --------------------------------------------------------------------- The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]