Jim Ellis wrote:
>
> Hi,
>
> I have been using BN_mod_exp for some time now with no problems, but I have
> found a set of values where the result of BN_mod_exp appears to be
> incorrect.
>
> I have created a modified version of exptest.c to demonstrate this bug case.
> I have included the c code below.
>
> Here are the results of running that code which does a^b % m.
> I realize the numbers here may not be legitimate primes but I viewed
> BN_mod_exp as a general purpose routine not subject to this limitation.
> Is this not true?
>
> a (1024) =
> FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF
> FFFFFFFFFFFFFFFFE00000000000000000000000000000000000000000000000000000000000
> 0000000000000000000000000000000000000000000000000000000000000000000000000000
> 0000000000000000000000000000
> b (950) =
> 3FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF
> FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF
> FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF
> FFFFFFFFFF
> m (1024) =
> FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF
> FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF
> FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF
> FFFFFFFFFFFFFFFFFFFFFFFFFFFF
> simple
> =F324E9CE6C2333BFF214495FEF0905623CF406F14243451110C7487E8987E9481271E191413
> DC355082DDDB56D4FB952E80B8DBBF1221F505456BA7E5C805B7998EAE482F4C56C3C9A627F2
> E2DB6B6F6152933D82FBF193EE0ED4C3D14C08CF680932A1A0401C7D22C1B8BE652EF1CABED7
> 025BB94977599E754F24C7F3D53D1
> recp
> =F324E9CE6C2333BFF214495FEF0905623CF406F14243451110C7487E8987E9481271E191413
> DC355082DDDB56D4FB952E80B8DBBF1221F505456BA7E5C805B7998EAE482F4C56C3C9A627F2
> E2DB6B6F6152933D82FBF193EE0ED4C3D14C08CF680932A1A0401C7D22C1B8BE652EF1CABED7
> 025BB94977599E754F24C7F3D53D1
> mont
> =F324E9CE6C2333BFF214495FEF0905623CF406F14243451110C7487E8987E9481271E191413
> DC355082DDDB56D4FB952E80B8DBBF1221F505456BA7E5C805B7998EAE482F4C56C3C9A627F2
> E2DB6B6F6152933D82FBF193EE0ED4C3D14C08CF680932A1A0401C7D22C1B8BE652EF1CABED7
> 025BB94977599E754F24C7F3D53D1
>
> What I believe to be the correct answer(from GNU MP http://www.swox.com/gmp/
> and other sources) is
> 009c51d6b1e3c88b0cd806c9583c1202585e7799fd883736a2cae08d9acdf95587b1dc9e9edd
> a847727f6902f9e28986817fa682680999fa780218d1a505adb0714217d1666c6ac3898054ff
> 267abfb3ec36acc6e475b30ad09b0691595931f9361ffde727a06c4befa356b12ac828e9da85
> 0b1a67ad0f50c195170973286aa8c9
>
> I tried to debug the BN_mod_exp_simple routine and found that it worked when
> the value of "a" was 2 and the other values were left the same.
>
> Here is my system info:
> OpenSSL version: 0.9.6b
> Last change: Change ssleay_rand_bytes (crypto/rand/md_rand.c)...
> OS (uname): SunOS 5.7 Generic_106541-15 sun4u sparc SUNW,Ultra-5_10
> OS (config): sun4u-whatever-solaris2
> Target (default): solaris-sparcv9-cc
> Target: dist
> Compiler: cc: Sun WorkShop 6 update 1 C 5.2 2000/09/11
>
> Any information on this subject would be greatly appreciated.
Alarmingly, I tried to build the sample code, and a slight error caused
something even worse to happen:
a (1024) =
FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF0FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFE000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
b (950) =
3FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF0FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF0FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF0FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF
m (1024) =
FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF0FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF0FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF0FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF
simple
=FE53FD9D91C832950E1365C2C53A38893AE29D35AAB9CD2A81D5CF85B7F3768692A20917B9B75AC74A7FE14FF0262B91C2760A20EA5175C754560D4FD4A1800C943F172A52CFD7D65C051F3F46E563BAA2BF8679FDFB0C4827E18A1FB303EF72AB3532D7E219577CCAE880301B15E55DAE6DB2252B43CB7E69101EF1F685EBD2
recp
=FE53FD9D91C832950E1365C2C53A38893AE29D35AAB9CD2A81D5CF85B7F3768692A20917B9B75AC74A7FE14FF0262B91C2760A20EA5175C754560D4FD4A1800C943F172A52CFD7D65C051F3F46E563BAA2BF8679FDFB0C4827E18A1FB303EF72AB3532D7E219577CCAE880301B15E55DAE6DB2252B43CB7E69101EF1F685EBD2
mont
=98FA7EA6C6E14F5C1CE194E321A6C4851878D57B2E85C90606FE5CF8B1B089236E858D38B0DFE76DB345B1338F73D793C42DB7335F8BAA87A36985323B3AAD03A42AE1C6DD005AD44AAA078DB8F9FD31BD96C320829FC70803E36A3394FBEAE81486000A77DB28D1627D3F5A82F9552EA8EDD79C190BEBC25279EB8958784715
The Montgomery version in this case doesn't even match!!! (note the 0s
injected into a, b and m).
Cheers,
Ben.
--
http://www.apache-ssl.org/ben.html
"There is no limit to what a man can do or how far he can go if he
doesn't mind who gets the credit." - Robert Woodruff
______________________________________________________________________
OpenSSL Project http://www.openssl.org
Development Mailing List [EMAIL PROTECTED]
Automated List Manager [EMAIL PROTECTED]
