Make bn_mul_recursive constant-time.
I left the input length as int because the calling convention passes
these messy deltas around. This micro-optimization is almost certainly
pointless, but bn_sub_part_words is written in assembly, so I've left it
alone for now. The documented preconditions were also all completely
wrong, so I've fixed them. We actually only call them for even tighter
bounds (one of dna or dnb is 0 and the other is 0 or -1), at least
outside bn_mul_part_recursive which I still need to read through.
This leaves bn_mul_part_recursive, which is reachable for RSA keys which
are not a power of two in bit width.
The first iteration of this had an uncaught bug, so I added a few more
aggressive tests generated with:
A = 0x...
B = 0x...
# Chop off 0, 1 and > 1 word for both 32 and 64-bit.
for i in (0, 1, 2, 4):
for j in (0, 1, 2, 4):
a = A >> (32*i)
b = B >> (32*j)
p = a * b
print "Product = %x" % p
print "A = %x" % a
print "B = %x" % b
print
Bug: 234
Change-Id: I72848d992637c0390cdd3c4f81cb919393b59eb8
Reviewed-on: https://boringssl-review.googlesource.com/25344
Commit-Queue: David Benjamin <davidben@google.com>
CQ-Verified: CQ bot account: commit-bot@chromium.org <commit-bot@chromium.org>
Reviewed-by: Adam Langley <agl@google.com>
diff --git a/crypto/fipsmodule/bn/bn_tests.txt b/crypto/fipsmodule/bn/bn_tests.txt
index 87e64e2..a5724fc 100644
--- a/crypto/fipsmodule/bn/bn_tests.txt
+++ b/crypto/fipsmodule/bn/bn_tests.txt
@@ -5976,6 +5976,70 @@
A = 542fb814f45924aa09a16f2a6
B = 1
+Product = 4f993781409d730da892c8451cc47a4c5c132a2c079f6c13a2689e9552450ed0b35c5291b82aae5614c0fc34f777940798a33b8bd5e010eb3c5c88595e8668fc8fb88ccd3d0cd5eee7c88e5b0b2be4605980fea4f8f2e42457963abe7860060482cfa2291e568ea55095ae2ada1c6bf9fda228664c9e02e7f12a8da4c355af044a537dd65dbf9c5d746c3c5f05a3d4d0515a48d9434b38fcbcc485558964fd9f212cf3c4aee9c03aebc468c25740df679d17823bfb20d96620c64b29f4013f0385cdd1a40fcbec3b06132a52aee615c4dbd880d0b030d5bc6aa06801d21fabd49774cd81ef504696d9655652db220ef989b0c6121e293a817a4d8899f571f257fa81c36a868d80e7fa2bcbda68a72ca3e31db8892b94d073e006433dd7128b7bf677d2b411532e5662cdff66d657673d58e03d4a338bae1a5513296f91d4d2b5b680527a2e12318e422ec2b7f05ea4fd3ef4780576488211dad5733685a8f0e5d2ecda549a15eebb235495e70d26b194c994cf16d98d356218d08a34d1593d90bc0d3572df0e84bdb1705c6c5e64ea4895599bb21bf219abdd4329813ecc198e708cee199c22f749bdeb0c206690e8420883f6c0661e47b29969986a7a72996ef63234c31aa39b7be37995d2898063ef5c3b672c43afbc1a065dec2671ae87e17639cfcd3148145a8323e1e9dc4f9c9daf981dd6aba4e8be01344c2eda185b87
+A = f33cad5d3876f0b60a001e13043e41033ee78c29ed8528fd6f22a87fc65c8c650277fab430722fcf63b3984c35ac46883127d544e2f44a465647814e15c0ff595382eff8bdff3be862f8a57a51f27ab4af9899861240855380f5bb883476699ef9eff179a1b88c64cfd6648240a5fc68de054468dc91dac11aaebe696dc05b6b0de0f54bd365ad798f3c85bceaf6ddf976b72cdf69de58335520d358f90e9856de5357dd5d2686cd1a41293d8c2687ba2cb1504420ae2c07014521889172b30df89521e2f66142345115110adf3dc603b1ddba5d80dc6b42fb980e9994aba2dfca00a3df8ea9062f570ec7e0e94d2bc95262b94a0aca2f9ffec082c58ba611f7
+B = 53c66ff2bc0e0d733d26f809aeedd151406ae8f44104f4e58f99e3eb54b06d542806932966bdbf30e13d81e5d6fa96f5308fc45613894b49dc7b766af02738dd89b10ca372d6232b0cbd57dcb873dea3c7598ef69b58ea5d72a0f2aaabd71025b488824a35cc33f8068ae4cd999fbb536be54e07f26df5d3bf8705281c8e94dd3712ad7c6a88f9d7b04f6f8924e18568ea07d46e58d197984824d797dd9ca1efe9763c62cc55fff69fad60d6501765dcf4926c18c027b4f9825d53cc38e99365c1b869245e66e7792f40dabeefe63e404cffc1d2ea63a9dd3fd4643afb2ddd288c6d4737abf20cec860584a7a600b4ad1eb654821c4af954a6ea39224eed9ef1
+
+Product = 4f993781409d730da892c8451cc47a4c5c132a2c079f6c13a2689e9552450ed0b35c5291b82aae5614c0fc34f777940798a33b8bd5e010eb3c5c88595e8668fc8fb88ccd3d0cd5eee7c88e5b0b2be4605980fea4f8f2e42457963abe7860060482cfa2291e568ea55095ae2ada1c6bf9fda228664c9e02e7f12a8da4c355af044a537dd65dbf9c5d746c3c5f05a3d4d0515a48d9434b38fcbcc485558964fd9f212cf3c4aee9c03aebc468c25740df679d17823bfb20d96620c64b29f4013f0385cdd1a40fcbec3b06132a52aee615c4dbd880d0b030d5bc6aa06801d21fabd49774cd81ef504696d9655652db220ef989b0c6121e293a817a4d8899aa73af54a4e1825aa6714016da99d9e3d0c02eb139716db437705cd9efabf0123b0831689735f4e488f226e577d4688d30914dd50ed368939452af0a7a094c065c6718bd54f53a808585fc1728c3bd1e7c968d76c6dca32f95a8323bacad31cdd4aae544d4208262c40bcf726c2f26cf1e60341c3e1e0c8ed4542555b9bf00488680b737a245cc9b7817231f1f6f1e614cdf43ea281fb850ebbb9305b1aa441a45dfdaa1e98b9d79d9ca511be070bfa94d8cd3cc750607c93e1b451a14e32356bd48d77860b37fd2e714827e770a5648ce8579a00ba5cae034502a8b03ba754994d9e002130cfdee6bfdf078dc8f6767b927c964197664c8e32bd3d31bd461ce
+A = f33cad5d3876f0b60a001e13043e41033ee78c29ed8528fd6f22a87fc65c8c650277fab430722fcf63b3984c35ac46883127d544e2f44a465647814e15c0ff595382eff8bdff3be862f8a57a51f27ab4af9899861240855380f5bb883476699ef9eff179a1b88c64cfd6648240a5fc68de054468dc91dac11aaebe696dc05b6b0de0f54bd365ad798f3c85bceaf6ddf976b72cdf69de58335520d358f90e9856de5357dd5d2686cd1a41293d8c2687ba2cb1504420ae2c07014521889172b30df89521e2f66142345115110adf3dc603b1ddba5d80dc6b42fb980e9994aba2dfca00a3df8ea9062f570ec7e0e94d2bc95262b94a0aca2f9ffec082c58ba611f7
+B = 53c66ff2bc0e0d733d26f809aeedd151406ae8f44104f4e58f99e3eb54b06d542806932966bdbf30e13d81e5d6fa96f5308fc45613894b49dc7b766af02738dd89b10ca372d6232b0cbd57dcb873dea3c7598ef69b58ea5d72a0f2aaabd71025b488824a35cc33f8068ae4cd999fbb536be54e07f26df5d3bf8705281c8e94dd3712ad7c6a88f9d7b04f6f8924e18568ea07d46e58d197984824d797dd9ca1efe9763c62cc55fff69fad60d6501765dcf4926c18c027b4f9825d53cc38e99365c1b869245e66e7792f40dabeefe63e404cffc1d2ea63a9dd3fd4643afb2ddd288c6d4737abf20cec860584a7a600b4ad1eb654821c4af954a6ea3922
+
+Product = 4f993781409d730da892c8451cc47a4c5c132a2c079f6c13a2689e9552450ed0b35c5291b82aae5614c0fc34f777940798a33b8bd5e010eb3c5c88595e8668fc8fb88ccd3d0cd5eee7c88e5b0b2be4605980fea4f8f2e42457963abe7860060482cfa2291e568ea55095ae2ada1c6bf9fda228664c9e02e7f12a8da4c355af044a537dd65dbf9c5d746c3c5f05a3d4d0515a48d9434b38fcbcc485558964fd9f212cf3c4aee9c03aebc468c25740df679d17823bfb20d96620c64b29f4013f0385cdd1a40fcbec3b06132a52aee615c4dbd880d0b030d5bc6aa06801d21fabd49774cd81ef504696d9655652db220ef989b0c6121e293a80dbb5a46feff82a92989bca577998c68ee619d9ea9972c6f139e97f5bdde635152830bedf302873508d2ed73badb82f9e32e1f4d12ea8c8b1059aa6d15f8e17d649bf41467903ab40d220d50570b5a263f637c0fcebc0ca29f8a81e2a01bf39bcb60cb9229dfd40618f706b941836bc5c291dec45ee9193e74d3a4cc5f73054ca56fd774a359f17a687268587393b76204a37cd48dcb09d3daed57a7e6d7d93a0ca3d6de8557fc4ddbfe9cb163fd10b7fe5f270dc57aa2fb88cdca2a3795015a17fd352d85fb688a38fa54883d0cab67aab08dbabd58d307c601f0f810014d78b101ff0bddb6d550b2480782406a905b9201e70ef6c1cb9765e91c10c8f5d240c
+A = f33cad5d3876f0b60a001e13043e41033ee78c29ed8528fd6f22a87fc65c8c650277fab430722fcf63b3984c35ac46883127d544e2f44a465647814e15c0ff595382eff8bdff3be862f8a57a51f27ab4af9899861240855380f5bb883476699ef9eff179a1b88c64cfd6648240a5fc68de054468dc91dac11aaebe696dc05b6b0de0f54bd365ad798f3c85bceaf6ddf976b72cdf69de58335520d358f90e9856de5357dd5d2686cd1a41293d8c2687ba2cb1504420ae2c07014521889172b30df89521e2f66142345115110adf3dc603b1ddba5d80dc6b42fb980e9994aba2dfca00a3df8ea9062f570ec7e0e94d2bc95262b94a0aca2f9ffec082c58ba611f7
+B = 53c66ff2bc0e0d733d26f809aeedd151406ae8f44104f4e58f99e3eb54b06d542806932966bdbf30e13d81e5d6fa96f5308fc45613894b49dc7b766af02738dd89b10ca372d6232b0cbd57dcb873dea3c7598ef69b58ea5d72a0f2aaabd71025b488824a35cc33f8068ae4cd999fbb536be54e07f26df5d3bf8705281c8e94dd3712ad7c6a88f9d7b04f6f8924e18568ea07d46e58d197984824d797dd9ca1efe9763c62cc55fff69fad60d6501765dcf4926c18c027b4f9825d53cc38e99365c1b869245e66e7792f40dabeefe63e404cffc1d2ea63a9dd3fd4643afb2ddd288c6d4737abf20cec860584a7a600b4ad1eb654821c4af954
+
+Product = 4f993781409d730da892c8451cc47a4c5c132a2c079f6c13a2689e9552450ed0b35c5291b82aae5614c0fc34f777940798a33b8bd5e010eb3c5c88595e8668fc8fb88ccd3d0cd5eee7c88e5b0b2be4605980fea4f8f2e42457963abe7860060482cfa2291e568ea55095ae2ada1c6bf9fda228664c9e02e7f12a8da4c355af044a537dd65dbf9c5d746c3c5f05a3d4d0515a48d9434b38fcbcc485558964fd9f212cf3c4aee9c03aebc468c25740df679d17823bfb20d96620c64b29f4013f0385cdd1a40fcbec3b06132a52aee615c4dbd880d0b030d5bc6aa06801d21fabd49774cd81ef504696d9655652db220ef96c826c5268b0a6788e14a9e3812764dd3ebb7489e6e66058ca6ccf9c007f8c049eda369b2889cc411bca78d4f5b0e3a9e80243e87e112072b01922b595afdef4dd562e58ce917f11e69c8fe050de54fdb2d607d05f09afd6dd140e9d195b91d85269610a1e5d5036e8c9fea2d4fa693d80ecdc819b201c0aed27dfe0b92b4b3b9ecabb3b9548f0d27dc917ffb14308c4f970863e163f375852fcd9fb115640dc40534f8f51a7b903599117dca6c80924fa9a1aeb43cf5a9a3f67ae818b484feed51d7ef60b3656720891b13a983c02c281c8a0954f13b7bfaca844d2cb66de5c11ff507e39cf774c7c93b38e296a44f04e5ecf2819b57943fb0509774ddbcfeb
+A = f33cad5d3876f0b60a001e13043e41033ee78c29ed8528fd6f22a87fc65c8c650277fab430722fcf63b3984c35ac46883127d544e2f44a465647814e15c0ff595382eff8bdff3be862f8a57a51f27ab4af9899861240855380f5bb883476699ef9eff179a1b88c64cfd6648240a5fc68de054468dc91dac11aaebe696dc05b6b0de0f54bd365ad798f3c85bceaf6ddf976b72cdf69de58335520d358f90e9856de5357dd5d2686cd1a41293d8c2687ba2cb1504420ae2c07014521889172b30df89521e2f66142345115110adf3dc603b1ddba5d80dc6b42fb980e9994aba2dfca00a3df8ea9062f570ec7e0e94d2bc95262b94a0aca2f9ffec082c58ba611f7
+B = 53c66ff2bc0e0d733d26f809aeedd151406ae8f44104f4e58f99e3eb54b06d542806932966bdbf30e13d81e5d6fa96f5308fc45613894b49dc7b766af02738dd89b10ca372d6232b0cbd57dcb873dea3c7598ef69b58ea5d72a0f2aaabd71025b488824a35cc33f8068ae4cd999fbb536be54e07f26df5d3bf8705281c8e94dd3712ad7c6a88f9d7b04f6f8924e18568ea07d46e58d197984824d797dd9ca1efe9763c62cc55fff69fad60d6501765dcf4926c18c027b4f9825d53cc38e99365c1b869245e66e7792f40dabeefe63e404cffc1d2ea63a9dd3fd4643afb2ddd288c6d4737abf20cec860584a7a600b4ad
+
+Product = 4f993781409d730da892c8451cc47a4c5c132a2c079f6c13a2689e9552450ed0b35c5291b82aae5614c0fc34f777940798a33b8bd5e010eb3c5c88595e8668fc8fb88ccd3d0cd5eee7c88e5b0b2be4605980fea4f8f2e42457963abe7860060482cfa2291e568ea55095ae2ada1c6bf9fda228664c9e02e7f12a8da4c355af044a537dd65dbf9c5d746c3c5f05a3d4d0515a48d9434b38fcbcc485558964fd9f212cf3c4aee9c03aebc468c25740df679d17823bfb20d96620c64b29f4013f0385cdd1a40fcbec3b06132a52aee615c4dbd880d0b030d5bc6aa06801d21fabd49774cd81ef504696d9655652db220ef989b0c6121e293a817a4d8899c7bedb01951b0f4fdb2c0fb64ad74707fda20027f4cee25da9b59be288d404cbd348f27600b87015d28f03cdf411f0e8c22deb9de5b3e0094f7820d78d59c90017cbd426297f8a32fb4b55b09362cf7cfb5910085acb24dbf618752b8b74c7e87f9cac44cb3b7486c43aa9b19a64d40a74eaf1de8b5f168b43d5750236aef753278c11294efd1adaddb6addb846f45fa55d7391898e8ec1c82bcf0008d9850c4c096571e8872e975dc8af1ba01bfbe8c8c27dc30cdaddd198936e4496579741a3a20e1b8e17241fe4abe5e98794e469180b742b2e1904940381f703f512885bda0340fe74e997ab269be00a3ca29bb937db2e06d8054e26dc13a5014ba51b175
+A = f33cad5d3876f0b60a001e13043e41033ee78c29ed8528fd6f22a87fc65c8c650277fab430722fcf63b3984c35ac46883127d544e2f44a465647814e15c0ff595382eff8bdff3be862f8a57a51f27ab4af9899861240855380f5bb883476699ef9eff179a1b88c64cfd6648240a5fc68de054468dc91dac11aaebe696dc05b6b0de0f54bd365ad798f3c85bceaf6ddf976b72cdf69de58335520d358f90e9856de5357dd5d2686cd1a41293d8c2687ba2cb1504420ae2c07014521889172b30df89521e2f66142345115110adf3dc603b1ddba5d80dc6b42fb980e9994aba2dfca00a3df8ea9062f570ec7e0e94d2bc95262b94a0aca2f9ffec082c5
+B = 53c66ff2bc0e0d733d26f809aeedd151406ae8f44104f4e58f99e3eb54b06d542806932966bdbf30e13d81e5d6fa96f5308fc45613894b49dc7b766af02738dd89b10ca372d6232b0cbd57dcb873dea3c7598ef69b58ea5d72a0f2aaabd71025b488824a35cc33f8068ae4cd999fbb536be54e07f26df5d3bf8705281c8e94dd3712ad7c6a88f9d7b04f6f8924e18568ea07d46e58d197984824d797dd9ca1efe9763c62cc55fff69fad60d6501765dcf4926c18c027b4f9825d53cc38e99365c1b869245e66e7792f40dabeefe63e404cffc1d2ea63a9dd3fd4643afb2ddd288c6d4737abf20cec860584a7a600b4ad1eb654821c4af954a6ea39224eed9ef1
+
+Product = 4f993781409d730da892c8451cc47a4c5c132a2c079f6c13a2689e9552450ed0b35c5291b82aae5614c0fc34f777940798a33b8bd5e010eb3c5c88595e8668fc8fb88ccd3d0cd5eee7c88e5b0b2be4605980fea4f8f2e42457963abe7860060482cfa2291e568ea55095ae2ada1c6bf9fda228664c9e02e7f12a8da4c355af044a537dd65dbf9c5d746c3c5f05a3d4d0515a48d9434b38fcbcc485558964fd9f212cf3c4aee9c03aebc468c25740df679d17823bfb20d96620c64b29f4013f0385cdd1a40fcbec3b06132a52aee615c4dbd880d0b030d5bc6aa06801d21fabd49774cd81ef504696d9655652db220ef989b0c6121e293a817a4d88997cc097fe3f7ace3ffb0fcee52b45551165bb02354b229788b59128489879b1a0373e9862a17692464a2dfc5d09185a0f1c67d2359ba70b52b03f21c7b24feb96e25e1a2dc7f4723952bf203979f7c9e38790f881e2b35006157825555d4c867fce9ea0a3cc6f1c94ee308a68e33f64f286247465ffe854033e9c64f5d79d6d66dcb38ad03535b20376bf4c3cf26e07ef445192ba2baf08bb5286695a61ff6b5dc7aa1832017198d61a324b8c244572157323c7bb3a2fee226133e1b0e0f2ff067cf71fc24bf38d0e172f459b0cdf0707c5bc586390faacf428bfdeb04e850ee0c35f6807eb6ca8d3a473dcc2239541115a8b0d33ea33295ff8c13b2a
+A = f33cad5d3876f0b60a001e13043e41033ee78c29ed8528fd6f22a87fc65c8c650277fab430722fcf63b3984c35ac46883127d544e2f44a465647814e15c0ff595382eff8bdff3be862f8a57a51f27ab4af9899861240855380f5bb883476699ef9eff179a1b88c64cfd6648240a5fc68de054468dc91dac11aaebe696dc05b6b0de0f54bd365ad798f3c85bceaf6ddf976b72cdf69de58335520d358f90e9856de5357dd5d2686cd1a41293d8c2687ba2cb1504420ae2c07014521889172b30df89521e2f66142345115110adf3dc603b1ddba5d80dc6b42fb980e9994aba2dfca00a3df8ea9062f570ec7e0e94d2bc95262b94a0aca2f9ffec082c5
+B = 53c66ff2bc0e0d733d26f809aeedd151406ae8f44104f4e58f99e3eb54b06d542806932966bdbf30e13d81e5d6fa96f5308fc45613894b49dc7b766af02738dd89b10ca372d6232b0cbd57dcb873dea3c7598ef69b58ea5d72a0f2aaabd71025b488824a35cc33f8068ae4cd999fbb536be54e07f26df5d3bf8705281c8e94dd3712ad7c6a88f9d7b04f6f8924e18568ea07d46e58d197984824d797dd9ca1efe9763c62cc55fff69fad60d6501765dcf4926c18c027b4f9825d53cc38e99365c1b869245e66e7792f40dabeefe63e404cffc1d2ea63a9dd3fd4643afb2ddd288c6d4737abf20cec860584a7a600b4ad1eb654821c4af954a6ea3922
+
+Product = 4f993781409d730da892c8451cc47a4c5c132a2c079f6c13a2689e9552450ed0b35c5291b82aae5614c0fc34f777940798a33b8bd5e010eb3c5c88595e8668fc8fb88ccd3d0cd5eee7c88e5b0b2be4605980fea4f8f2e42457963abe7860060482cfa2291e568ea55095ae2ada1c6bf9fda228664c9e02e7f12a8da4c355af044a537dd65dbf9c5d746c3c5f05a3d4d0515a48d9434b38fcbcc485558964fd9f212cf3c4aee9c03aebc468c25740df679d17823bfb20d96620c64b29f4013f0385cdd1a40fcbec3b06132a52aee615c4dbd880d0b030d5bc6aa06801d21fabd49774cd81ef504696d9655652db220ef989b0c6121e293a80dbb5a46fc245133c3335163cce37555d36c555182e6d9a754b9aa9305c070083d0fe806d2c5eda4a976f749d6ef40515c425e6531a7f4d11926e49907b7a8a938205e0d6fefaacb145200cbe3deec686476bcdc1f6bb3535147ecb00818f2cd666ac0dd497f0fbc087bf05c6425b7752a02e2a695655d4310f04943a6178946a74dbe4688bd1eb3f1a166aef37e39f3e1d36b6d6d422ec0db264cae8d44869f57a92952bd74a026dd7cfc672803905f029c723487d4123a7520688fc9c68b2384be32e881f64d0ed7ae555bf00e5799740dd8c6accc40f3fe573f194f4848bb05aea8a5509f2dd10fce023093f1ef20267244a990d7ffd462f4e85a4
+A = f33cad5d3876f0b60a001e13043e41033ee78c29ed8528fd6f22a87fc65c8c650277fab430722fcf63b3984c35ac46883127d544e2f44a465647814e15c0ff595382eff8bdff3be862f8a57a51f27ab4af9899861240855380f5bb883476699ef9eff179a1b88c64cfd6648240a5fc68de054468dc91dac11aaebe696dc05b6b0de0f54bd365ad798f3c85bceaf6ddf976b72cdf69de58335520d358f90e9856de5357dd5d2686cd1a41293d8c2687ba2cb1504420ae2c07014521889172b30df89521e2f66142345115110adf3dc603b1ddba5d80dc6b42fb980e9994aba2dfca00a3df8ea9062f570ec7e0e94d2bc95262b94a0aca2f9ffec082c5
+B = 53c66ff2bc0e0d733d26f809aeedd151406ae8f44104f4e58f99e3eb54b06d542806932966bdbf30e13d81e5d6fa96f5308fc45613894b49dc7b766af02738dd89b10ca372d6232b0cbd57dcb873dea3c7598ef69b58ea5d72a0f2aaabd71025b488824a35cc33f8068ae4cd999fbb536be54e07f26df5d3bf8705281c8e94dd3712ad7c6a88f9d7b04f6f8924e18568ea07d46e58d197984824d797dd9ca1efe9763c62cc55fff69fad60d6501765dcf4926c18c027b4f9825d53cc38e99365c1b869245e66e7792f40dabeefe63e404cffc1d2ea63a9dd3fd4643afb2ddd288c6d4737abf20cec860584a7a600b4ad1eb654821c4af954
+
+Product = 4f993781409d730da892c8451cc47a4c5c132a2c079f6c13a2689e9552450ed0b35c5291b82aae5614c0fc34f777940798a33b8bd5e010eb3c5c88595e8668fc8fb88ccd3d0cd5eee7c88e5b0b2be4605980fea4f8f2e42457963abe7860060482cfa2291e568ea55095ae2ada1c6bf9fda228664c9e02e7f12a8da4c355af044a537dd65dbf9c5d746c3c5f05a3d4d0515a48d9434b38fcbcc485558964fd9f212cf3c4aee9c03aebc468c25740df679d17823bfb20d96620c64b29f4013f0385cdd1a40fcbec3b06132a52aee615c4dbd880d0b030d5bc6aa06801d21fabd49774cd81ef504696d9655652db220ef96c826c5268b0a6788e14a9e353744d86d954c06f3b84ef271b184ac9957a5f88b08b606fa6aa97afc4983a62f1e74aa3f242e14a3f4cf5ea415d1437818663556a29d117ea7df1cf1ee32f70d6d5566e25d53f892c42d3f92e481b622455fce36e400de09e2d435099695354ceee249c793b76b3c544d70164381e0420ef8b85609502afff9130729ba7851e0775dc5d8c606ba614e7607625fbc38908c88fac43e29ff9b8728f5809e63f20289246b5128016478437550a833c60edb0df43dd9a47654f2e4ef308d4a18cea57ea4b0c6d08add07f2e7adc427cf591c29dbd1f975432922e3f2b71c75e4d2557efccf626be7a0d522b658d420ae321
+A = f33cad5d3876f0b60a001e13043e41033ee78c29ed8528fd6f22a87fc65c8c650277fab430722fcf63b3984c35ac46883127d544e2f44a465647814e15c0ff595382eff8bdff3be862f8a57a51f27ab4af9899861240855380f5bb883476699ef9eff179a1b88c64cfd6648240a5fc68de054468dc91dac11aaebe696dc05b6b0de0f54bd365ad798f3c85bceaf6ddf976b72cdf69de58335520d358f90e9856de5357dd5d2686cd1a41293d8c2687ba2cb1504420ae2c07014521889172b30df89521e2f66142345115110adf3dc603b1ddba5d80dc6b42fb980e9994aba2dfca00a3df8ea9062f570ec7e0e94d2bc95262b94a0aca2f9ffec082c5
+B = 53c66ff2bc0e0d733d26f809aeedd151406ae8f44104f4e58f99e3eb54b06d542806932966bdbf30e13d81e5d6fa96f5308fc45613894b49dc7b766af02738dd89b10ca372d6232b0cbd57dcb873dea3c7598ef69b58ea5d72a0f2aaabd71025b488824a35cc33f8068ae4cd999fbb536be54e07f26df5d3bf8705281c8e94dd3712ad7c6a88f9d7b04f6f8924e18568ea07d46e58d197984824d797dd9ca1efe9763c62cc55fff69fad60d6501765dcf4926c18c027b4f9825d53cc38e99365c1b869245e66e7792f40dabeefe63e404cffc1d2ea63a9dd3fd4643afb2ddd288c6d4737abf20cec860584a7a600b4ad
+
+Product = 4f993781409d730da892c8451cc47a4c5c132a2c079f6c13a2689e9552450ed0b35c5291b82aae5614c0fc34f777940798a33b8bd5e010eb3c5c88595e8668fc8fb88ccd3d0cd5eee7c88e5b0b2be4605980fea4f8f2e42457963abe7860060482cfa2291e568ea55095ae2ada1c6bf9fda228664c9e02e7f12a8da4c355af044a537dd65dbf9c5d746c3c5f05a3d4d0515a48d9434b38fcbcc485558964fd9f212cf3c4aee9c03aebc468c25740df679d17823bfb20d96620c64b29f4013f0385cdd1a40fcbec3b06132a52aee615c4dbd880d0b030d5bc6aa06801d21fabd49774cd81ef504696d9655652db220ef989b0c6121e293a8126efa5e7be8e75d54e5ba9405f671d624eaf8d7a115d0479f6fb773b940525fd46b69bc43c815b6bb1798813ca95790bc68032f0b9e73fc964a9922507d8aac25f859745939b828ef5ed326b226b555e5088f13531be16272a89ad41ae82c940935b5d8fe75dc520a230cc279a887bce01bae0a79356f044af13c6f4a5e53c00b2d03cfcbb0f93b26202441a207ec91576410ac1750e257906d945bfe9204b73fc417600bd191edcf2e3eb79acbf4f84dda372405b5e98397abe85c1593543cd7a5b17cb90e299f422f0ce107d86b56474e435dbbcbb5314fb579cd68d54777aa2d0ff9b6b96de62b4676edea5b09589698ed829cad22a52aaec732b79edf6af
+A = f33cad5d3876f0b60a001e13043e41033ee78c29ed8528fd6f22a87fc65c8c650277fab430722fcf63b3984c35ac46883127d544e2f44a465647814e15c0ff595382eff8bdff3be862f8a57a51f27ab4af9899861240855380f5bb883476699ef9eff179a1b88c64cfd6648240a5fc68de054468dc91dac11aaebe696dc05b6b0de0f54bd365ad798f3c85bceaf6ddf976b72cdf69de58335520d358f90e9856de5357dd5d2686cd1a41293d8c2687ba2cb1504420ae2c07014521889172b30df89521e2f66142345115110adf3dc603b1ddba5d80dc6b42fb980e9994aba2dfca00a3df8ea9062f570ec7e0e94d2bc95262b94a0aca2f9f
+B = 53c66ff2bc0e0d733d26f809aeedd151406ae8f44104f4e58f99e3eb54b06d542806932966bdbf30e13d81e5d6fa96f5308fc45613894b49dc7b766af02738dd89b10ca372d6232b0cbd57dcb873dea3c7598ef69b58ea5d72a0f2aaabd71025b488824a35cc33f8068ae4cd999fbb536be54e07f26df5d3bf8705281c8e94dd3712ad7c6a88f9d7b04f6f8924e18568ea07d46e58d197984824d797dd9ca1efe9763c62cc55fff69fad60d6501765dcf4926c18c027b4f9825d53cc38e99365c1b869245e66e7792f40dabeefe63e404cffc1d2ea63a9dd3fd4643afb2ddd288c6d4737abf20cec860584a7a600b4ad1eb654821c4af954a6ea39224eed9ef1
+
+Product = 4f993781409d730da892c8451cc47a4c5c132a2c079f6c13a2689e9552450ed0b35c5291b82aae5614c0fc34f777940798a33b8bd5e010eb3c5c88595e8668fc8fb88ccd3d0cd5eee7c88e5b0b2be4605980fea4f8f2e42457963abe7860060482cfa2291e568ea55095ae2ada1c6bf9fda228664c9e02e7f12a8da4c355af044a537dd65dbf9c5d746c3c5f05a3d4d0515a48d9434b38fcbcc485558964fd9f212cf3c4aee9c03aebc468c25740df679d17823bfb20d96620c64b29f4013f0385cdd1a40fcbec3b06132a52aee615c4dbd880d0b030d5bc6aa06801d21fabd49774cd81ef504696d9655652db220ef989b0c6121e293a8126efa5e7739032d1f8bb68307f4adc912f1d9b83797606874d4f2c669fe0b263565c4898a07701585237aa444234719adb869c17142126611a9cbd6e689fabb2847bb9dc5e2dc89694621a7179df1fe7371deb9bbdf5fea0b271d86bcde2796a65331c27365fb97fa3647435c47e5c854a95718fa49072cc239d046ca0ac2bf453beb31070370d59483adb42b9876776e43fccb663887f1a999f625eb8e9c4cdd0a89099c42cdff06be29ad9ea66a957002925c9425a83c3e74096ca31324134f5d4a2b7d3b8d7fd8d72192049f79c670874f65201c068c5aac2008a7df4e5eba02d88be8ec23683513a9cffe06671a7c2fa5da7a7aa571914caba1e
+A = f33cad5d3876f0b60a001e13043e41033ee78c29ed8528fd6f22a87fc65c8c650277fab430722fcf63b3984c35ac46883127d544e2f44a465647814e15c0ff595382eff8bdff3be862f8a57a51f27ab4af9899861240855380f5bb883476699ef9eff179a1b88c64cfd6648240a5fc68de054468dc91dac11aaebe696dc05b6b0de0f54bd365ad798f3c85bceaf6ddf976b72cdf69de58335520d358f90e9856de5357dd5d2686cd1a41293d8c2687ba2cb1504420ae2c07014521889172b30df89521e2f66142345115110adf3dc603b1ddba5d80dc6b42fb980e9994aba2dfca00a3df8ea9062f570ec7e0e94d2bc95262b94a0aca2f9f
+B = 53c66ff2bc0e0d733d26f809aeedd151406ae8f44104f4e58f99e3eb54b06d542806932966bdbf30e13d81e5d6fa96f5308fc45613894b49dc7b766af02738dd89b10ca372d6232b0cbd57dcb873dea3c7598ef69b58ea5d72a0f2aaabd71025b488824a35cc33f8068ae4cd999fbb536be54e07f26df5d3bf8705281c8e94dd3712ad7c6a88f9d7b04f6f8924e18568ea07d46e58d197984824d797dd9ca1efe9763c62cc55fff69fad60d6501765dcf4926c18c027b4f9825d53cc38e99365c1b869245e66e7792f40dabeefe63e404cffc1d2ea63a9dd3fd4643afb2ddd288c6d4737abf20cec860584a7a600b4ad1eb654821c4af954a6ea3922
+
+Product = 4f993781409d730da892c8451cc47a4c5c132a2c079f6c13a2689e9552450ed0b35c5291b82aae5614c0fc34f777940798a33b8bd5e010eb3c5c88595e8668fc8fb88ccd3d0cd5eee7c88e5b0b2be4605980fea4f8f2e42457963abe7860060482cfa2291e568ea55095ae2ada1c6bf9fda228664c9e02e7f12a8da4c355af044a537dd65dbf9c5d746c3c5f05a3d4d0515a48d9434b38fcbcc485558964fd9f212cf3c4aee9c03aebc468c25740df679d17823bfb20d96620c64b29f4013f0385cdd1a40fcbec3b06132a52aee615c4dbd880d0b030d5bc6aa06801d21fabd49774cd81ef504696d9655652db220ef989b0c6121e293a808857c1bdb914ae0fec75b02d527263093a9d9b8a42289ec74dc73e0e46568a9e8ee117659597434048308c9b66fa7a539694285b1238a13d1163fbac33db147e5431af1c7aca5b1a118db4f6650ec6340491ef7a2d203b53e43d536639f980eb6e92a37bffb2149c5eb45d6718a9496f0784370674c1d29732b944a3c3885b68f0fd2a121f556dc82d1b942e7aabba780f087b9df359d86e2055248c3aabc568e93bba67d3ccca2c4240c876506d63bb05aad6fc4c77dfafff1731a46c6711bc60c4d23976268928bc63e1d133add0633c737bb508c81fa1ff3b452b49b992ebac930432d555ab8c62ae17357b1186e80689672f5a9f472c
+A = f33cad5d3876f0b60a001e13043e41033ee78c29ed8528fd6f22a87fc65c8c650277fab430722fcf63b3984c35ac46883127d544e2f44a465647814e15c0ff595382eff8bdff3be862f8a57a51f27ab4af9899861240855380f5bb883476699ef9eff179a1b88c64cfd6648240a5fc68de054468dc91dac11aaebe696dc05b6b0de0f54bd365ad798f3c85bceaf6ddf976b72cdf69de58335520d358f90e9856de5357dd5d2686cd1a41293d8c2687ba2cb1504420ae2c07014521889172b30df89521e2f66142345115110adf3dc603b1ddba5d80dc6b42fb980e9994aba2dfca00a3df8ea9062f570ec7e0e94d2bc95262b94a0aca2f9f
+B = 53c66ff2bc0e0d733d26f809aeedd151406ae8f44104f4e58f99e3eb54b06d542806932966bdbf30e13d81e5d6fa96f5308fc45613894b49dc7b766af02738dd89b10ca372d6232b0cbd57dcb873dea3c7598ef69b58ea5d72a0f2aaabd71025b488824a35cc33f8068ae4cd999fbb536be54e07f26df5d3bf8705281c8e94dd3712ad7c6a88f9d7b04f6f8924e18568ea07d46e58d197984824d797dd9ca1efe9763c62cc55fff69fad60d6501765dcf4926c18c027b4f9825d53cc38e99365c1b869245e66e7792f40dabeefe63e404cffc1d2ea63a9dd3fd4643afb2ddd288c6d4737abf20cec860584a7a600b4ad1eb654821c4af954
+
+Product = 4f993781409d730da892c8451cc47a4c5c132a2c079f6c13a2689e9552450ed0b35c5291b82aae5614c0fc34f777940798a33b8bd5e010eb3c5c88595e8668fc8fb88ccd3d0cd5eee7c88e5b0b2be4605980fea4f8f2e42457963abe7860060482cfa2291e568ea55095ae2ada1c6bf9fda228664c9e02e7f12a8da4c355af044a537dd65dbf9c5d746c3c5f05a3d4d0515a48d9434b38fcbcc485558964fd9f212cf3c4aee9c03aebc468c25740df679d17823bfb20d96620c64b29f4013f0385cdd1a40fcbec3b06132a52aee615c4dbd880d0b030d5bc6aa06801d21fabd49774cd81ef504696d9655652db220ef96c826c5268b0a6783ab6c7314a43e85a92955a5fbfbffcd31ef0913ba93563dab2b7f54d90fa21ca827ad15b5b1fb399a303f94837536b2813cb563f793fb780e91f8333a2de7bb9f10efdb652a504d6f242e7c15362d3a6eb6e3d1a5abb03023dfe964656979765a14fe8fc36af3d785030ce549b92a91dcb8e2aa13f5b89eb8449b31961a0f77117c8cac79af95ee69f6594e557af7bb017cd885027ff7c0cb1d2f99d1ed5eacb788f645c25150e737cf1184b546bb2d55f2014a18015ffe647580df6fe4d528ce983309baeac0347ae8739e2b1f6d1a83e12e4dbfea1cd81b11b8628837432ad1906c70323529b718c8c6e398e1dfa73
+A = f33cad5d3876f0b60a001e13043e41033ee78c29ed8528fd6f22a87fc65c8c650277fab430722fcf63b3984c35ac46883127d544e2f44a465647814e15c0ff595382eff8bdff3be862f8a57a51f27ab4af9899861240855380f5bb883476699ef9eff179a1b88c64cfd6648240a5fc68de054468dc91dac11aaebe696dc05b6b0de0f54bd365ad798f3c85bceaf6ddf976b72cdf69de58335520d358f90e9856de5357dd5d2686cd1a41293d8c2687ba2cb1504420ae2c07014521889172b30df89521e2f66142345115110adf3dc603b1ddba5d80dc6b42fb980e9994aba2dfca00a3df8ea9062f570ec7e0e94d2bc95262b94a0aca2f9f
+B = 53c66ff2bc0e0d733d26f809aeedd151406ae8f44104f4e58f99e3eb54b06d542806932966bdbf30e13d81e5d6fa96f5308fc45613894b49dc7b766af02738dd89b10ca372d6232b0cbd57dcb873dea3c7598ef69b58ea5d72a0f2aaabd71025b488824a35cc33f8068ae4cd999fbb536be54e07f26df5d3bf8705281c8e94dd3712ad7c6a88f9d7b04f6f8924e18568ea07d46e58d197984824d797dd9ca1efe9763c62cc55fff69fad60d6501765dcf4926c18c027b4f9825d53cc38e99365c1b869245e66e7792f40dabeefe63e404cffc1d2ea63a9dd3fd4643afb2ddd288c6d4737abf20cec860584a7a600b4ad
+
+Product = 4f993781409d730da892c8451cc47a4c5c132a2c079f6c13a2689e9552450ed0b35c5291b82aae5614c0fc34f777940798a33b8bd5e010eb3c5c88595e8668fc8fb88ccd3d0cd5eee7c88e5b0b2be4605980fea4f8f2e42457963abe7860060482cfa2291e568ea55095ae2ada1c6bf9fda228664c9e02e7f12a8da4c355af044a537dd65dbf9c5d746c3c5f05a3d4d0515a48d9434b38fcbcc485558964fd9f212cf3c4aee9c03aebc468c25740df679d17823bfb20d96620c64b29f4013f0385cdd1a40fcbec3b06132a52aee615c4dbd880d0b030d5bc6aa06801d21fabd49774cd81ef504696d9655652db220ef96ebae79ce1360c374bc58f225bca564b7e6561b56e0edbb3a7f5934f382b916ab38423221d656357ce0e9bf1e9b04c0678b9c555e8365a0f977c95bd8dca1fb2ad2268193531ca36cbe7f40da8e1afe097e451dc2931b323ce731c03cc027a92ed8ae105c5e9c1bd385e238d989fadbf3aa54c097a8666df8a66b7e2d016e65a2a632603f2c84290ccd7346ada28dff79dd06c7f7989689aca4f494b977f984650f91327ab9936cb92675932440f135e54e4abeecf255d7061482b4c8d91769e02fc94b8acc43325d69541903c3ef7a7a8a5bd19bf886506d42bcf0efcb6197a8d178d6a60516a5aa771ae238a342dc61df8c18c6ba1ed952d4e0c3409c14639
+A = f33cad5d3876f0b60a001e13043e41033ee78c29ed8528fd6f22a87fc65c8c650277fab430722fcf63b3984c35ac46883127d544e2f44a465647814e15c0ff595382eff8bdff3be862f8a57a51f27ab4af9899861240855380f5bb883476699ef9eff179a1b88c64cfd6648240a5fc68de054468dc91dac11aaebe696dc05b6b0de0f54bd365ad798f3c85bceaf6ddf976b72cdf69de58335520d358f90e9856de5357dd5d2686cd1a41293d8c2687ba2cb1504420ae2c07014521889172b30df89521e2f66142345115110adf3dc603b1ddba5d80dc6b42fb980e9994aba2dfca00a3df8ea9062f570ec7e0e94d2bc9
+B = 53c66ff2bc0e0d733d26f809aeedd151406ae8f44104f4e58f99e3eb54b06d542806932966bdbf30e13d81e5d6fa96f5308fc45613894b49dc7b766af02738dd89b10ca372d6232b0cbd57dcb873dea3c7598ef69b58ea5d72a0f2aaabd71025b488824a35cc33f8068ae4cd999fbb536be54e07f26df5d3bf8705281c8e94dd3712ad7c6a88f9d7b04f6f8924e18568ea07d46e58d197984824d797dd9ca1efe9763c62cc55fff69fad60d6501765dcf4926c18c027b4f9825d53cc38e99365c1b869245e66e7792f40dabeefe63e404cffc1d2ea63a9dd3fd4643afb2ddd288c6d4737abf20cec860584a7a600b4ad1eb654821c4af954a6ea39224eed9ef1
+
+Product = 4f993781409d730da892c8451cc47a4c5c132a2c079f6c13a2689e9552450ed0b35c5291b82aae5614c0fc34f777940798a33b8bd5e010eb3c5c88595e8668fc8fb88ccd3d0cd5eee7c88e5b0b2be4605980fea4f8f2e42457963abe7860060482cfa2291e568ea55095ae2ada1c6bf9fda228664c9e02e7f12a8da4c355af044a537dd65dbf9c5d746c3c5f05a3d4d0515a48d9434b38fcbcc485558964fd9f212cf3c4aee9c03aebc468c25740df679d17823bfb20d96620c64b29f4013f0385cdd1a40fcbec3b06132a52aee615c4dbd880d0b030d5bc6aa06801d21fabd49774cd81ef504696d9655652db220ef96ebae79ce1360c374bc58f2210cc134828c520a58df29ae28863a158a044937809d7d84d2940efbdddb448c64da5f1f31977e7865fd5529eac82fee3e804064a6315936295f8cb26f0de16a47373f5e8365939e280a57dacb508166a583a630c75730c2fe54971e70a35e224e7a1a21e3bd8f417a47c4796d34148cae15068e19eec637bed8f32846dc5aa7e8f50599e840903a8129206fc384e0b4085f9f1e7e3bf2fc67b62b02566ce73cb4b22d471cde35b4f0cccb74283cdded5748d62286f7ea5c184c1308d520ecc7c7f1535b1132708298bf94c0967bc8f8541bb2f2b3c81f11e50f1d8cba4ce3746ad5f85e6bacbefada657c9b386b991b2
+A = f33cad5d3876f0b60a001e13043e41033ee78c29ed8528fd6f22a87fc65c8c650277fab430722fcf63b3984c35ac46883127d544e2f44a465647814e15c0ff595382eff8bdff3be862f8a57a51f27ab4af9899861240855380f5bb883476699ef9eff179a1b88c64cfd6648240a5fc68de054468dc91dac11aaebe696dc05b6b0de0f54bd365ad798f3c85bceaf6ddf976b72cdf69de58335520d358f90e9856de5357dd5d2686cd1a41293d8c2687ba2cb1504420ae2c07014521889172b30df89521e2f66142345115110adf3dc603b1ddba5d80dc6b42fb980e9994aba2dfca00a3df8ea9062f570ec7e0e94d2bc9
+B = 53c66ff2bc0e0d733d26f809aeedd151406ae8f44104f4e58f99e3eb54b06d542806932966bdbf30e13d81e5d6fa96f5308fc45613894b49dc7b766af02738dd89b10ca372d6232b0cbd57dcb873dea3c7598ef69b58ea5d72a0f2aaabd71025b488824a35cc33f8068ae4cd999fbb536be54e07f26df5d3bf8705281c8e94dd3712ad7c6a88f9d7b04f6f8924e18568ea07d46e58d197984824d797dd9ca1efe9763c62cc55fff69fad60d6501765dcf4926c18c027b4f9825d53cc38e99365c1b869245e66e7792f40dabeefe63e404cffc1d2ea63a9dd3fd4643afb2ddd288c6d4737abf20cec860584a7a600b4ad1eb654821c4af954a6ea3922
+
+Product = 4f993781409d730da892c8451cc47a4c5c132a2c079f6c13a2689e9552450ed0b35c5291b82aae5614c0fc34f777940798a33b8bd5e010eb3c5c88595e8668fc8fb88ccd3d0cd5eee7c88e5b0b2be4605980fea4f8f2e42457963abe7860060482cfa2291e568ea55095ae2ada1c6bf9fda228664c9e02e7f12a8da4c355af044a537dd65dbf9c5d746c3c5f05a3d4d0515a48d9434b38fcbcc485558964fd9f212cf3c4aee9c03aebc468c25740df679d17823bfb20d96620c64b29f4013f0385cdd1a40fcbec3b06132a52aee615c4dbd880d0b030d5bc6aa06801d21fabd49774cd81ef504696d9655652db220ef96ebae79ce1360c36ad2daaf856508e861c7f68a2611a215a93e3a15f68f72bb80a4fe9f4cfb6c7f91639179342c633db0f70c9dd849b5b5767908b27e61b812659dcd1a0613433f2c0940be49010886bb384d4676bd523f9827c1a48c7649fbfa73e872a5160796813956979b0f3fd3af728dd48f8a7348090300e41b181c8acae08a3b3106b61f90b0421803e6eba0d68e9bc93d3b659fd6316ba2815cb4b3b6a74f1f3fd24b0c07f619d995ac2beada44188eb72d371a6894f90087eaabe148755409bbff60114bcfefbfe2182e6dc4218d0da75af80059bbb14e848c2e60790fb35bf1cb685cbb133b2baf3f2faefcc3f69e34102def4
+A = f33cad5d3876f0b60a001e13043e41033ee78c29ed8528fd6f22a87fc65c8c650277fab430722fcf63b3984c35ac46883127d544e2f44a465647814e15c0ff595382eff8bdff3be862f8a57a51f27ab4af9899861240855380f5bb883476699ef9eff179a1b88c64cfd6648240a5fc68de054468dc91dac11aaebe696dc05b6b0de0f54bd365ad798f3c85bceaf6ddf976b72cdf69de58335520d358f90e9856de5357dd5d2686cd1a41293d8c2687ba2cb1504420ae2c07014521889172b30df89521e2f66142345115110adf3dc603b1ddba5d80dc6b42fb980e9994aba2dfca00a3df8ea9062f570ec7e0e94d2bc9
+B = 53c66ff2bc0e0d733d26f809aeedd151406ae8f44104f4e58f99e3eb54b06d542806932966bdbf30e13d81e5d6fa96f5308fc45613894b49dc7b766af02738dd89b10ca372d6232b0cbd57dcb873dea3c7598ef69b58ea5d72a0f2aaabd71025b488824a35cc33f8068ae4cd999fbb536be54e07f26df5d3bf8705281c8e94dd3712ad7c6a88f9d7b04f6f8924e18568ea07d46e58d197984824d797dd9ca1efe9763c62cc55fff69fad60d6501765dcf4926c18c027b4f9825d53cc38e99365c1b869245e66e7792f40dabeefe63e404cffc1d2ea63a9dd3fd4643afb2ddd288c6d4737abf20cec860584a7a600b4ad1eb654821c4af954
+
+Product = 4f993781409d730da892c8451cc47a4c5c132a2c079f6c13a2689e9552450ed0b35c5291b82aae5614c0fc34f777940798a33b8bd5e010eb3c5c88595e8668fc8fb88ccd3d0cd5eee7c88e5b0b2be4605980fea4f8f2e42457963abe7860060482cfa2291e568ea55095ae2ada1c6bf9fda228664c9e02e7f12a8da4c355af044a537dd65dbf9c5d746c3c5f05a3d4d0515a48d9434b38fcbcc485558964fd9f212cf3c4aee9c03aebc468c25740df679d17823bfb20d96620c64b29f4013f0385cdd1a40fcbec3b06132a52aee615c4dbd880d0b030d5bc6aa06801d21fabd49774cd81ef504696d9655652db220ef9518c8ddd2bbd782e5f8cb06be77fc8d0c29f12d4ce67bb2478369710d003f0cb6f40a1341a5a5f2509d2d189084ea4346a44368a54f44c2be4c7b90c4d22976a31985927d0379b2e5d715a7e67eb3228943a07325a29316c695867e8f4ff676e00ffca0a6dfe8fe24652aef9e7f12616e8a54e367b90942f543a01dc7c1b8000ff991228ae83fe0131cfc235ba12ab2bdb33bd4ab0ba1b356bdbc6da4a70eed9fbf2c704e14ed6230eb5478dac0b02f4def1d8c076d1c0c0e2c4cdadb248de4acf961cee51dc41e545bd5a605a0860fb343c28ebf3f8814a9d5a7e0f3e9c93e742db76bc5671258d1da7758b41efead5
+A = f33cad5d3876f0b60a001e13043e41033ee78c29ed8528fd6f22a87fc65c8c650277fab430722fcf63b3984c35ac46883127d544e2f44a465647814e15c0ff595382eff8bdff3be862f8a57a51f27ab4af9899861240855380f5bb883476699ef9eff179a1b88c64cfd6648240a5fc68de054468dc91dac11aaebe696dc05b6b0de0f54bd365ad798f3c85bceaf6ddf976b72cdf69de58335520d358f90e9856de5357dd5d2686cd1a41293d8c2687ba2cb1504420ae2c07014521889172b30df89521e2f66142345115110adf3dc603b1ddba5d80dc6b42fb980e9994aba2dfca00a3df8ea9062f570ec7e0e94d2bc9
+B = 53c66ff2bc0e0d733d26f809aeedd151406ae8f44104f4e58f99e3eb54b06d542806932966bdbf30e13d81e5d6fa96f5308fc45613894b49dc7b766af02738dd89b10ca372d6232b0cbd57dcb873dea3c7598ef69b58ea5d72a0f2aaabd71025b488824a35cc33f8068ae4cd999fbb536be54e07f26df5d3bf8705281c8e94dd3712ad7c6a88f9d7b04f6f8924e18568ea07d46e58d197984824d797dd9ca1efe9763c62cc55fff69fad60d6501765dcf4926c18c027b4f9825d53cc38e99365c1b869245e66e7792f40dabeefe63e404cffc1d2ea63a9dd3fd4643afb2ddd288c6d4737abf20cec860584a7a600b4ad
+
# Quotient tests.
#
diff --git a/crypto/fipsmodule/bn/mul.c b/crypto/fipsmodule/bn/mul.c
index 1bd099c..d97e584 100644
--- a/crypto/fipsmodule/bn/mul.c
+++ b/crypto/fipsmodule/bn/mul.c
@@ -61,6 +61,7 @@
#include <openssl/err.h>
#include <openssl/mem.h>
+#include <openssl/type_check.h>
#include "internal.h"
#include "../../internal.h"
@@ -286,25 +287,43 @@
int cl, int dl);
#endif
+// bn_abs_sub_part_words computes |r| = |a| - |b|, storing the absolute value
+// and returning a mask of all ones if the result was negative and all zeros if
+// the result was positive. |cl| and |dl| follow the |bn_sub_part_words| calling
+// convention.
+//
+// TODO(davidben): Make this take |size_t|. The |cl| + |dl| calling convention
+// is confusing. The trouble is 32-bit x86 implements |bn_sub_part_words| in
+// assembly, but we can probably just delete it?
+static BN_ULONG bn_abs_sub_part_words(BN_ULONG *r, const BN_ULONG *a,
+ const BN_ULONG *b, int cl, int dl,
+ BN_ULONG *tmp) {
+ BN_ULONG borrow = bn_sub_part_words(tmp, a, b, cl, dl);
+ bn_sub_part_words(r, b, a, cl, -dl);
+ int r_len = cl + (dl < 0 ? -dl : dl);
+ borrow = 0 - borrow;
+ bn_select_words(r, borrow, r /* tmp < 0 */, tmp /* tmp >= 0 */, r_len);
+ return borrow;
+}
+
// Karatsuba recursive multiplication algorithm
// (cf. Knuth, The Art of Computer Programming, Vol. 2)
-// r is 2*n2 words in size,
-// a and b are both n2 words in size.
-// n2 must be a power of 2.
-// We multiply and return the result.
-// t must be 2*n2 words in size
-// We calculate
-// a[0]*b[0]
-// a[0]*b[0]+a[1]*b[1]+(a[0]-a[1])*(b[1]-b[0])
-// a[1]*b[1]
-// dnX may not be positive, but n2/2+dnX has to be
+// bn_mul_recursive sets |r| to |a| * |b|, using |t| as scratch space. |r| has
+// length 2*|n2|, |a| has length |n2| + |dna|, |b| has length |n2| + |dnb|, and
+// |t| has length 4*|n2|. |n2| must be a power of two. Finally, we must have
+// -|BN_MUL_RECURSIVE_SIZE_NORMAL|/2 <= |dna| <= 0 and
+// -|BN_MUL_RECURSIVE_SIZE_NORMAL|/2 <= |dnb| <= 0.
+//
+// TODO(davidben): Simplify and |size_t| the calling convention around lengths
+// here.
static void bn_mul_recursive(BN_ULONG *r, const BN_ULONG *a, const BN_ULONG *b,
int n2, int dna, int dnb, BN_ULONG *t) {
- int n = n2 / 2, c1, c2;
- int tna = n + dna, tnb = n + dnb;
- unsigned int neg, zero;
- BN_ULONG ln, lo, *p;
+ // |n2| is a power of two.
+ assert(n2 != 0 && (n2 & (n2 - 1)) == 0);
+ // Check |dna| and |dnb| are in range.
+ assert(-BN_MUL_RECURSIVE_SIZE_NORMAL/2 <= dna && dna <= 0);
+ assert(-BN_MUL_RECURSIVE_SIZE_NORMAL/2 <= dnb && dnb <= 0);
// Only call bn_mul_comba 8 if n2 == 8 and the
// two arrays are complete [steve]
@@ -316,119 +335,78 @@
// Else do normal multiply
if (n2 < BN_MUL_RECURSIVE_SIZE_NORMAL) {
bn_mul_normal(r, a, n2 + dna, b, n2 + dnb);
- if ((dna + dnb) < 0) {
+ if (dna + dnb < 0) {
OPENSSL_memset(&r[2 * n2 + dna + dnb], 0,
sizeof(BN_ULONG) * -(dna + dnb));
}
return;
}
- // TODO(davidben): This function is not constant-time, but should be. See
- // https://crbug.com/boringssl/234.
+ // Split |a| and |b| into a0,a1 and b0,b1, where a0 and b0 have size |n|.
+ // Split |t| into t0,t1,t2,t3, each of size |n|, with the remaining 4*|n| used
+ // for recursive calls.
+ // Split |r| into r0,r1,r2,r3. We must contribute a0*b0 to r0,r1, a0*a1+b0*b1
+ // to r1,r2, and a1*b1 to r2,r3. The middle term we will compute as:
+ //
+ // a0*a1 + b0*b1 = (a0 - a1)*(b1 - b0) + a1*b1 + a0*b0
+ //
+ // Note that we know |n| >= |BN_MUL_RECURSIVE_SIZE_NORMAL|/2 above, so
+ // |tna| and |tnb| are non-negative.
+ int n = n2 / 2, tna = n + dna, tnb = n + dnb;
- // r=(a[0]-a[1])*(b[1]-b[0])
- c1 = bn_cmp_part_words(a, &(a[n]), tna, n - tna);
- c2 = bn_cmp_part_words(&(b[n]), b, tnb, tnb - n);
- zero = neg = 0;
- switch (c1 * 3 + c2) {
- case -4:
- bn_sub_part_words(t, &(a[n]), a, tna, tna - n); // -
- bn_sub_part_words(&(t[n]), b, &(b[n]), tnb, n - tnb); // -
- break;
- case -3:
- zero = 1;
- break;
- case -2:
- bn_sub_part_words(t, &(a[n]), a, tna, tna - n); // -
- bn_sub_part_words(&(t[n]), &(b[n]), b, tnb, tnb - n); // +
- neg = 1;
- break;
- case -1:
- case 0:
- case 1:
- zero = 1;
- break;
- case 2:
- bn_sub_part_words(t, a, &(a[n]), tna, n - tna); // +
- bn_sub_part_words(&(t[n]), b, &(b[n]), tnb, n - tnb); // -
- neg = 1;
- break;
- case 3:
- zero = 1;
- break;
- case 4:
- bn_sub_part_words(t, a, &(a[n]), tna, n - tna);
- bn_sub_part_words(&(t[n]), &(b[n]), b, tnb, tnb - n);
- break;
- }
+ // t0 = a0 - a1 and t1 = b1 - b0. The result will be multiplied, so we XOR
+ // their sign masks, giving the sign of (a0 - a1)*(b1 - b0). t0 and t1
+ // themselves store the absolute value.
+ BN_ULONG neg = bn_abs_sub_part_words(t, a, &a[n], tna, n - tna, &t[n2]);
+ neg ^= bn_abs_sub_part_words(&t[n], &b[n], b, tnb, tnb - n, &t[n2]);
+ // Compute:
+ // t2,t3 = t0 * t1 = |(a0 - a1)*(b1 - b0)|
+ // r0,r1 = a0 * b0
+ // r2,r3 = a1 * b1
if (n == 4 && dna == 0 && dnb == 0) {
- // XXX: bn_mul_comba4 could take extra args to do this well
- if (!zero) {
- bn_mul_comba4(&(t[n2]), t, &(t[n]));
- } else {
- OPENSSL_memset(&(t[n2]), 0, 8 * sizeof(BN_ULONG));
- }
+ bn_mul_comba4(&t[n2], t, &t[n]);
bn_mul_comba4(r, a, b);
- bn_mul_comba4(&(r[n2]), &(a[n]), &(b[n]));
+ bn_mul_comba4(&r[n2], &a[n], &b[n]);
} else if (n == 8 && dna == 0 && dnb == 0) {
- // XXX: bn_mul_comba8 could take extra args to do this well
- if (!zero) {
- bn_mul_comba8(&(t[n2]), t, &(t[n]));
- } else {
- OPENSSL_memset(&(t[n2]), 0, 16 * sizeof(BN_ULONG));
- }
+ bn_mul_comba8(&t[n2], t, &t[n]);
bn_mul_comba8(r, a, b);
- bn_mul_comba8(&(r[n2]), &(a[n]), &(b[n]));
+ bn_mul_comba8(&r[n2], &a[n], &b[n]);
} else {
- p = &(t[n2 * 2]);
- if (!zero) {
- bn_mul_recursive(&(t[n2]), t, &(t[n]), n, 0, 0, p);
- } else {
- OPENSSL_memset(&(t[n2]), 0, n2 * sizeof(BN_ULONG));
- }
+ BN_ULONG *p = &t[n2 * 2];
+ bn_mul_recursive(&t[n2], t, &t[n], n, 0, 0, p);
bn_mul_recursive(r, a, b, n, 0, 0, p);
- bn_mul_recursive(&(r[n2]), &(a[n]), &(b[n]), n, dna, dnb, p);
+ bn_mul_recursive(&r[n2], &a[n], &b[n], n, dna, dnb, p);
}
- // t[32] holds (a[0]-a[1])*(b[1]-b[0]), c1 is the sign
- // r[10] holds (a[0]*b[0])
- // r[32] holds (b[1]*b[1])
+ // t0,t1,c = r0,r1 + r2,r3 = a0*b0 + a1*b1
+ BN_ULONG c = bn_add_words(t, r, &r[n2], n2);
- c1 = (int)(bn_add_words(t, r, &(r[n2]), n2));
+ // t2,t3,c = t0,t1,c + neg*t2,t3 = (a0 - a1)*(b1 - b0) + a1*b1 + a0*b0.
+ // The second term is stored as the absolute value, so we do this with a
+ // constant-time select.
+ BN_ULONG c_neg = c - bn_sub_words(&t[n2 * 2], t, &t[n2], n2);
+ BN_ULONG c_pos = c + bn_add_words(&t[n2], t, &t[n2], n2);
+ bn_select_words(&t[n2], neg, &t[n2 * 2], &t[n2], n2);
+ OPENSSL_COMPILE_ASSERT(sizeof(BN_ULONG) <= sizeof(crypto_word_t),
+ crypto_word_t_too_small);
+ c = constant_time_select_w(neg, c_neg, c_pos);
- if (neg) {
- // if t[32] is negative
- c1 -= (int)(bn_sub_words(&(t[n2]), t, &(t[n2]), n2));
- } else {
- // Might have a carry
- c1 += (int)(bn_add_words(&(t[n2]), &(t[n2]), t, n2));
+ // We now have our three components. Add them together.
+ // r1,r2,c = r1,r2 + t2,t3,c
+ c += bn_add_words(&r[n], &r[n], &t[n2], n2);
+
+ // Propagate the carry bit to the end.
+ for (int i = n + n2; i < n2 + n2; i++) {
+ BN_ULONG old = r[i];
+ r[i] = old + c;
+ c = r[i] < old;
}
- // t[32] holds (a[0]-a[1])*(b[1]-b[0])+(a[0]*b[0])+(a[1]*b[1])
- // r[10] holds (a[0]*b[0])
- // r[32] holds (b[1]*b[1])
- // c1 holds the carry bits
- c1 += (int)(bn_add_words(&(r[n]), &(r[n]), &(t[n2]), n2));
- if (c1) {
- p = &(r[n + n2]);
- lo = *p;
- ln = lo + c1;
- *p = ln;
-
- // The overflow will stop before we over write
- // words we should not overwrite
- if (ln < (BN_ULONG)c1) {
- do {
- p++;
- lo = *p;
- ln = lo + 1;
- *p = ln;
- } while (ln == 0);
- }
- }
+ // The product should fit without carries.
+ assert(c == 0);
}
// n+tn is the word length
