Exponent 3 damage spreads...

[Hal Finney]

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 majordomo at metzdowd.com