Exponent 3 damage spreads...

[Anton Stiglic]

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:hal at finney.org] 
Sent: September 20, 2006 6:21 PM
To: astiglic at okiok.com; cryptography at 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 majordomo at metzdowd.com