Mod-expt of number greater than 2048 returns incorrect answer

[Takashi Kato]

This

(mod-expt #x2d2875f005db8c7ef05939e2c4a0e004d0484c2695399d31451732a7d3ec5237c916e0f79480bb8cd66dc3a51d99f7b21d473123e264a58ff7cdf434f99bdf363d22bc2adb35e3c227f071e55916078c0c2fc05badb4868772e079b812fff3360bf2492bc39a90eb01a719532a197901426ed2af7a4a4d65ff902ce0cc4902b21fd981d6e2c97c73586ee6df462ef14d274c414cf5a48a20fcb0a5a4e73a028b0f8a2f671620e3fda15a600cfb12d41bf0957a88cd812675e3949f34ef49382905ce89d10ae321724463913b66ea5bd20af66ddf74a3600bfa9db9ff4b45413d47a9f2a9a2f9539f6a747183bfc499e5aab66c853c0481ad45ca5663b285895c0f598b8ddcad057be03d28f63bc6d20426d542ff43da2158ddc1117ffc721e6917f36d2696dc1e31a53cad6f7d8e114c783f1d52ddf2bd1e50f3a4cbc0740d3658848a8b8207d154d3afff34d45cf8e8a8a448dd491b93bf5da47d0f14d55aafdef63f18d6255361349a78d5f5dc0b171eaed74b5c33ab79ef403d6fb7b68ff93ffaf68f288b5d842958ebea3303042e22cf2f999d7a631a023f7ec2ad29bc0450080f1d72af5d7a24b5ae6c88822e5ff442f2a42d18ebc99ffc9a06925f5380216c2d7ad249f1305a321fb4229f2eb2cb590bb8e93b674c1296e5438567a89ee264ee7c5d034c0a7137ed14663d572b1583e1129f386e0428f4d42c1bc9e311
          #x10001
          #xd2de09e51c3f01ff3fd33e378843f0201bac1a76d758ac3d41663b308c28e59bc6b3a1323de9a37a720c54e7d16f3bcf926fedd0e5405e595d71537728c837ed1c0d857defc7a7dd5698c6b43af0d149d96fcdb847f156d738f665f8e6437e0558e3e03a048791ee6d4bf390a6df4775bacc6b4b38c707cb4462a68ccc652d74f2838ac27cce3ecc322a31e87d5043ed8d4b9dbe92597b5968e468a7506ff4208161b1688689e5be65864a847198904b16c5738e66ba3b1deeca681b427cef473a1f8c6c4941659acd040f8593362b17293688f1d63574be41a8b6c8d8c688e231a2b0852ec458f3cc7cc306dd0a4358ee82671f955d12dfde93b6337d7f0a4e2e7722d70f5ed4d5680d710e5306bff6adb7c52aed8ac89b25aec9d125398f96f9a8a59465c46c9afddcb0c3f7f0199ee234bee840213fbe19542b7a3bf54b2e84985d9a0352e9ca7b826df0f93253a1acd46e02b6339d4eb91e0792ea96d6192b8067d11667f4f1130cba6a2fb01f180d5b606c868c7f4d987d06b104db44042727243261b8cee3efdad884e36b0adb8e6a8240a794c219b021436de68ed321548306413029ace2364f679ddfd87e94b81caa7a05136dbd9585126e0af62f93b87bf6b1c54d69c8da6bd130582d01cc3a68691bbffe9c205228dfb63a87aaa9f5c378331160e93ad3f449ff0fd15fd29b9237eabdc175dd49addb5f658a0881)

must return

277637098854488092554278456117449521139939927266889531367154038505621425317258691888954058815997220036871157056711004675415435508562024777641508740617014167233205008385359638465553830294823592284785554792458023072266349507301351191222532685448930793734072131753940315392315568185260988543541386825999697694490576582360819405335602625421979942499367237884552258948386891314122540110246781054696461332786020761937912284968198882786635940085567133284402079724215397831890639090584022377626419889752010798418217459665843847503706204744219980103186742573461848835278566285214497578200652454165141276790123560155983256093217965415965972902046720851640830290875212675840048737380436495239685228034221504446069447555091234653752769688611851466006091180096151427494324917443699904856514876519250885629579159562634662441380373807772858494293209423756652189081311477347031867849996956787197435180001905091774479552329957991348222709477157027591233159646281419586255410338138170555136367780140698814200205761309668233011659428813809943665327073992101184728659018751638987957003930494706820981247694779852286197732819193772682449891231506472016752694333616738462431501038916048271685829216974197890708600105970583031975443415252897888258327650625

but returns

752726126686721189688397149393498588911757179564464850217790591686981753043936321163522422232167209798013285786511602288526296812976568730277757774272377425038928206020389852343353693246008265437306368147676420216819840844814949888206156229852129587698016317047606862510420455088223105144790107854855946651406641580063671767143201334840153540857880465122506834378365839416964624487076915203445542173924463261731555795319822160720440721730932398881487912972486813068284683757345851189793162011729547569719157981308013429092731560059840684681721054044769249103299230592324866738983409719343999951081755362252752296847498805560311118768891372768354428661415533298938762320065719939050534686306312668494288848888698194041727201179849610105153909177835602801322562110670066949641076203891184050561944835115762898292020917632603400460840944632138240727472080591152141343269799417561807644797838615083022334563232177345530814520403134178382274110367728928791062660880244021557470071068172498760979896131470982410437827409307168304379636662940750508923325246813854082334524471621078744246151884238144722204356782562583552497276929019705487977344775043421509125129372858830387908423453375462662540885694524202853209414851500083322077263933859

‌

[Takashi Kato]

A generated signature was valid on BouncyCastle, so verify procedure is probably broken

[Takashi Kato]

Seems mod-expt with the 4096 bits keys are broken.

[Takashi Kato]

Apparently, starting 4096 bits we use karatsuba_square, so we never used this one before…

That’s a lie (square is working properly)

[Takashi Kato]

karatsuba had a bug

[Takashi Kato]

Fixing recursive karatsuba multiplication, e.g. over 4096 bits. (Fixes #276)

→ <<cset 8aa932e350fe>>