bntest.c 90 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602603604605606607608609610611612613614615616617618619620621622623624625626627628629630631632633634635636637638639640641642643644645646647648649650651652653654655656657658659660661662663664665666667668669670671672673674675676677678679680681682683684685686687688689690691692693694695696697698699700701702703704705706707708709710711712713714715716717718719720721722723724725726727728729730731732733734735736737738739740741742743744745746747748749750751752753754755756757758759760761762763764765766767768769770771772773774775776777778779780781782783784785786787788789790791792793794795796797798799800801802803804805806807808809810811812813814815816817818819820821822823824825826827828829830831832833834835836837838839840841842843844845846847848849850851852853854855856857858859860861862863864865866867868869870871872873874875876877878879880881882883884885886887888889890891892893894895896897898899900901902903904905906907908909910911912913914915916917918919920921922923924925926927928929930931932933934935936937938939940941942943944945946947948949950951952953954955956957958959960961962963964965966967968969970971972973974975976977978979980981982983984985986987988989990991992993994995996997998999100010011002100310041005100610071008100910101011101210131014101510161017101810191020102110221023102410251026102710281029103010311032103310341035103610371038103910401041104210431044104510461047104810491050105110521053105410551056105710581059106010611062106310641065106610671068106910701071107210731074107510761077107810791080108110821083108410851086108710881089109010911092109310941095109610971098109911001101110211031104110511061107110811091110111111121113111411151116111711181119112011211122112311241125112611271128112911301131113211331134113511361137113811391140114111421143114411451146114711481149115011511152115311541155115611571158115911601161116211631164116511661167116811691170117111721173117411751176117711781179118011811182118311841185118611871188118911901191119211931194119511961197119811991200120112021203120412051206120712081209121012111212121312141215121612171218121912201221122212231224122512261227122812291230123112321233123412351236123712381239124012411242124312441245124612471248124912501251125212531254125512561257125812591260126112621263126412651266126712681269127012711272127312741275127612771278127912801281128212831284128512861287128812891290129112921293129412951296129712981299130013011302130313041305130613071308130913101311131213131314131513161317131813191320132113221323132413251326132713281329133013311332133313341335133613371338133913401341134213431344134513461347134813491350135113521353135413551356135713581359136013611362136313641365136613671368136913701371137213731374137513761377137813791380138113821383138413851386138713881389139013911392139313941395139613971398139914001401140214031404140514061407140814091410141114121413141414151416141714181419142014211422142314241425142614271428142914301431143214331434143514361437143814391440144114421443144414451446144714481449145014511452145314541455145614571458145914601461146214631464146514661467146814691470147114721473147414751476147714781479148014811482148314841485148614871488148914901491149214931494149514961497149814991500150115021503150415051506150715081509151015111512151315141515151615171518151915201521152215231524152515261527152815291530153115321533153415351536153715381539154015411542154315441545154615471548154915501551155215531554155515561557155815591560156115621563156415651566156715681569157015711572157315741575157615771578157915801581158215831584158515861587158815891590159115921593159415951596159715981599160016011602160316041605160616071608160916101611161216131614161516161617161816191620162116221623162416251626162716281629163016311632163316341635163616371638163916401641164216431644164516461647164816491650165116521653165416551656165716581659166016611662166316641665166616671668166916701671167216731674167516761677167816791680168116821683168416851686168716881689169016911692169316941695169616971698169917001701170217031704170517061707170817091710171117121713171417151716171717181719172017211722172317241725172617271728172917301731173217331734173517361737173817391740174117421743174417451746174717481749175017511752175317541755175617571758175917601761176217631764176517661767176817691770177117721773177417751776177717781779178017811782178317841785178617871788178917901791179217931794179517961797179817991800180118021803180418051806180718081809181018111812181318141815181618171818181918201821182218231824182518261827182818291830183118321833183418351836183718381839184018411842184318441845184618471848184918501851185218531854185518561857185818591860186118621863186418651866186718681869187018711872187318741875187618771878187918801881188218831884188518861887188818891890189118921893189418951896189718981899190019011902190319041905190619071908190919101911191219131914191519161917191819191920192119221923192419251926192719281929193019311932193319341935193619371938193919401941194219431944194519461947194819491950195119521953195419551956195719581959196019611962196319641965196619671968196919701971197219731974197519761977197819791980198119821983198419851986198719881989199019911992199319941995199619971998199920002001200220032004200520062007200820092010201120122013201420152016201720182019202020212022202320242025202620272028202920302031203220332034203520362037203820392040204120422043204420452046204720482049205020512052205320542055205620572058205920602061206220632064206520662067206820692070207120722073207420752076207720782079208020812082208320842085208620872088208920902091209220932094209520962097209820992100210121022103210421052106210721082109211021112112211321142115211621172118211921202121212221232124212521262127212821292130213121322133213421352136213721382139214021412142214321442145214621472148214921502151215221532154215521562157215821592160216121622163216421652166216721682169217021712172217321742175217621772178217921802181218221832184218521862187218821892190219121922193219421952196219721982199220022012202220322042205220622072208220922102211221222132214221522162217221822192220222122222223222422252226222722282229223022312232223322342235223622372238223922402241224222432244224522462247224822492250225122522253225422552256225722582259226022612262226322642265226622672268226922702271227222732274227522762277227822792280228122822283228422852286228722882289229022912292229322942295229622972298229923002301230223032304230523062307230823092310231123122313231423152316231723182319232023212322232323242325232623272328232923302331233223332334233523362337233823392340234123422343234423452346234723482349235023512352235323542355235623572358235923602361236223632364236523662367236823692370237123722373237423752376237723782379238023812382238323842385238623872388238923902391239223932394239523962397239823992400240124022403240424052406240724082409241024112412241324142415241624172418241924202421242224232424242524262427242824292430243124322433243424352436243724382439244024412442244324442445244624472448244924502451245224532454245524562457245824592460246124622463246424652466246724682469247024712472247324742475247624772478247924802481248224832484248524862487248824892490249124922493249424952496249724982499250025012502250325042505250625072508250925102511251225132514251525162517251825192520252125222523252425252526252725282529253025312532253325342535253625372538253925402541254225432544254525462547254825492550255125522553255425552556255725582559256025612562256325642565256625672568256925702571257225732574257525762577257825792580258125822583258425852586258725882589259025912592259325942595259625972598259926002601260226032604260526062607260826092610261126122613261426152616261726182619262026212622262326242625262626272628262926302631263226332634263526362637263826392640264126422643264426452646264726482649265026512652265326542655265626572658265926602661266226632664266526662667266826692670267126722673267426752676267726782679268026812682268326842685268626872688268926902691269226932694269526962697269826992700270127022703270427052706270727082709271027112712271327142715271627172718271927202721272227232724272527262727272827292730273127322733273427352736273727382739274027412742274327442745274627472748274927502751275227532754275527562757275827592760276127622763276427652766276727682769277027712772277327742775277627772778277927802781278227832784278527862787278827892790279127922793279427952796279727982799280028012802280328042805280628072808280928102811281228132814281528162817281828192820282128222823282428252826282728282829283028312832283328342835283628372838283928402841284228432844284528462847284828492850285128522853285428552856285728582859286028612862286328642865286628672868286928702871287228732874287528762877287828792880288128822883288428852886288728882889289028912892289328942895289628972898289929002901290229032904290529062907290829092910291129122913291429152916291729182919292029212922
  1. /*
  2. * Copyright 1995-2020 The OpenSSL Project Authors. All Rights Reserved.
  3. *
  4. * Licensed under the Apache License 2.0 (the "License"). You may not use
  5. * this file except in compliance with the License. You can obtain a copy
  6. * in the file LICENSE in the source distribution or at
  7. * https://www.openssl.org/source/license.html
  8. */
  9. #include <assert.h>
  10. #include <errno.h>
  11. #include <stdio.h>
  12. #include <string.h>
  13. #ifdef __TANDEM
  14. # include <strings.h> /* strcasecmp */
  15. #endif
  16. #include <ctype.h>
  17. #include <openssl/bn.h>
  18. #include <openssl/crypto.h>
  19. #include <openssl/err.h>
  20. #include <openssl/rand.h>
  21. #include "internal/nelem.h"
  22. #include "internal/numbers.h"
  23. #include "testutil.h"
  24. #ifdef OPENSSL_SYS_WINDOWS
  25. # define strcasecmp _stricmp
  26. #endif
  27. /*
  28. * Things in boring, not in openssl. TODO we should add them.
  29. */
  30. #define HAVE_BN_PADDED 0
  31. #define HAVE_BN_SQRT 0
  32. typedef struct filetest_st {
  33. const char *name;
  34. int (*func)(STANZA *s);
  35. } FILETEST;
  36. typedef struct mpitest_st {
  37. const char *base10;
  38. const char *mpi;
  39. size_t mpi_len;
  40. } MPITEST;
  41. static const int NUM0 = 100; /* number of tests */
  42. static const int NUM1 = 50; /* additional tests for some functions */
  43. static BN_CTX *ctx;
  44. /*
  45. * Polynomial coefficients used in GFM tests.
  46. */
  47. #ifndef OPENSSL_NO_EC2M
  48. static int p0[] = { 163, 7, 6, 3, 0, -1 };
  49. static int p1[] = { 193, 15, 0, -1 };
  50. #endif
  51. /*
  52. * Look for |key| in the stanza and return it or NULL if not found.
  53. */
  54. static const char *findattr(STANZA *s, const char *key)
  55. {
  56. int i = s->numpairs;
  57. PAIR *pp = s->pairs;
  58. for ( ; --i >= 0; pp++)
  59. if (strcasecmp(pp->key, key) == 0)
  60. return pp->value;
  61. return NULL;
  62. }
  63. /*
  64. * Parse BIGNUM from sparse hex-strings, return |BN_hex2bn| result.
  65. */
  66. static int parse_bigBN(BIGNUM **out, const char *bn_strings[])
  67. {
  68. char *bigstring = glue_strings(bn_strings, NULL);
  69. int ret = BN_hex2bn(out, bigstring);
  70. OPENSSL_free(bigstring);
  71. return ret;
  72. }
  73. /*
  74. * Parse BIGNUM, return number of bytes parsed.
  75. */
  76. static int parseBN(BIGNUM **out, const char *in)
  77. {
  78. *out = NULL;
  79. return BN_hex2bn(out, in);
  80. }
  81. static int parsedecBN(BIGNUM **out, const char *in)
  82. {
  83. *out = NULL;
  84. return BN_dec2bn(out, in);
  85. }
  86. static BIGNUM *getBN(STANZA *s, const char *attribute)
  87. {
  88. const char *hex;
  89. BIGNUM *ret = NULL;
  90. if ((hex = findattr(s, attribute)) == NULL) {
  91. TEST_error("%s:%d: Can't find %s", s->test_file, s->start, attribute);
  92. return NULL;
  93. }
  94. if (parseBN(&ret, hex) != (int)strlen(hex)) {
  95. TEST_error("Could not decode '%s'", hex);
  96. return NULL;
  97. }
  98. return ret;
  99. }
  100. static int getint(STANZA *s, int *out, const char *attribute)
  101. {
  102. BIGNUM *ret;
  103. BN_ULONG word;
  104. int st = 0;
  105. if (!TEST_ptr(ret = getBN(s, attribute))
  106. || !TEST_ulong_le(word = BN_get_word(ret), INT_MAX))
  107. goto err;
  108. *out = (int)word;
  109. st = 1;
  110. err:
  111. BN_free(ret);
  112. return st;
  113. }
  114. static int equalBN(const char *op, const BIGNUM *expected, const BIGNUM *actual)
  115. {
  116. if (BN_cmp(expected, actual) == 0)
  117. return 1;
  118. TEST_error("unexpected %s value", op);
  119. TEST_BN_eq(expected, actual);
  120. return 0;
  121. }
  122. /*
  123. * Return a "random" flag for if a BN should be negated.
  124. */
  125. static int rand_neg(void)
  126. {
  127. static unsigned int neg = 0;
  128. static int sign[8] = { 0, 0, 0, 1, 1, 0, 1, 1 };
  129. return sign[(neg++) % 8];
  130. }
  131. static int test_swap(void)
  132. {
  133. BIGNUM *a = NULL, *b = NULL, *c = NULL, *d = NULL;
  134. int top, cond, st = 0;
  135. if (!TEST_ptr(a = BN_new())
  136. || !TEST_ptr(b = BN_new())
  137. || !TEST_ptr(c = BN_new())
  138. || !TEST_ptr(d = BN_new()))
  139. goto err;
  140. if (!(TEST_true(BN_bntest_rand(a, 1024, 1, 0))
  141. && TEST_true(BN_bntest_rand(b, 1024, 1, 0))
  142. && TEST_ptr(BN_copy(c, a))
  143. && TEST_ptr(BN_copy(d, b))))
  144. goto err;
  145. top = BN_num_bits(a) / BN_BITS2;
  146. /* regular swap */
  147. BN_swap(a, b);
  148. if (!equalBN("swap", a, d)
  149. || !equalBN("swap", b, c))
  150. goto err;
  151. /* conditional swap: true */
  152. cond = 1;
  153. BN_consttime_swap(cond, a, b, top);
  154. if (!equalBN("cswap true", a, c)
  155. || !equalBN("cswap true", b, d))
  156. goto err;
  157. /* conditional swap: false */
  158. cond = 0;
  159. BN_consttime_swap(cond, a, b, top);
  160. if (!equalBN("cswap false", a, c)
  161. || !equalBN("cswap false", b, d))
  162. goto err;
  163. /* same tests but checking flag swap */
  164. BN_set_flags(a, BN_FLG_CONSTTIME);
  165. BN_swap(a, b);
  166. if (!equalBN("swap, flags", a, d)
  167. || !equalBN("swap, flags", b, c)
  168. || !TEST_true(BN_get_flags(b, BN_FLG_CONSTTIME))
  169. || !TEST_false(BN_get_flags(a, BN_FLG_CONSTTIME)))
  170. goto err;
  171. cond = 1;
  172. BN_consttime_swap(cond, a, b, top);
  173. if (!equalBN("cswap true, flags", a, c)
  174. || !equalBN("cswap true, flags", b, d)
  175. || !TEST_true(BN_get_flags(a, BN_FLG_CONSTTIME))
  176. || !TEST_false(BN_get_flags(b, BN_FLG_CONSTTIME)))
  177. goto err;
  178. cond = 0;
  179. BN_consttime_swap(cond, a, b, top);
  180. if (!equalBN("cswap false, flags", a, c)
  181. || !equalBN("cswap false, flags", b, d)
  182. || !TEST_true(BN_get_flags(a, BN_FLG_CONSTTIME))
  183. || !TEST_false(BN_get_flags(b, BN_FLG_CONSTTIME)))
  184. goto err;
  185. st = 1;
  186. err:
  187. BN_free(a);
  188. BN_free(b);
  189. BN_free(c);
  190. BN_free(d);
  191. return st;
  192. }
  193. static int test_sub(void)
  194. {
  195. BIGNUM *a = NULL, *b = NULL, *c = NULL;
  196. int i, st = 0;
  197. if (!TEST_ptr(a = BN_new())
  198. || !TEST_ptr(b = BN_new())
  199. || !TEST_ptr(c = BN_new()))
  200. goto err;
  201. for (i = 0; i < NUM0 + NUM1; i++) {
  202. if (i < NUM1) {
  203. if (!(TEST_true(BN_bntest_rand(a, 512, 0, 0)))
  204. && TEST_ptr(BN_copy(b, a))
  205. && TEST_int_ne(BN_set_bit(a, i), 0)
  206. && TEST_true(BN_add_word(b, i)))
  207. goto err;
  208. } else {
  209. if (!TEST_true(BN_bntest_rand(b, 400 + i - NUM1, 0, 0)))
  210. goto err;
  211. BN_set_negative(a, rand_neg());
  212. BN_set_negative(b, rand_neg());
  213. }
  214. if (!(TEST_true(BN_sub(c, a, b))
  215. && TEST_true(BN_add(c, c, b))
  216. && TEST_true(BN_sub(c, c, a))
  217. && TEST_BN_eq_zero(c)))
  218. goto err;
  219. }
  220. st = 1;
  221. err:
  222. BN_free(a);
  223. BN_free(b);
  224. BN_free(c);
  225. return st;
  226. }
  227. static int test_div_recip(void)
  228. {
  229. BIGNUM *a = NULL, *b = NULL, *c = NULL, *d = NULL, *e = NULL;
  230. BN_RECP_CTX *recp = NULL;
  231. int st = 0, i;
  232. if (!TEST_ptr(a = BN_new())
  233. || !TEST_ptr(b = BN_new())
  234. || !TEST_ptr(c = BN_new())
  235. || !TEST_ptr(d = BN_new())
  236. || !TEST_ptr(e = BN_new())
  237. || !TEST_ptr(recp = BN_RECP_CTX_new()))
  238. goto err;
  239. for (i = 0; i < NUM0 + NUM1; i++) {
  240. if (i < NUM1) {
  241. if (!(TEST_true(BN_bntest_rand(a, 400, 0, 0))
  242. && TEST_ptr(BN_copy(b, a))
  243. && TEST_true(BN_lshift(a, a, i))
  244. && TEST_true(BN_add_word(a, i))))
  245. goto err;
  246. } else {
  247. if (!(TEST_true(BN_bntest_rand(b, 50 + 3 * (i - NUM1), 0, 0))))
  248. goto err;
  249. }
  250. BN_set_negative(a, rand_neg());
  251. BN_set_negative(b, rand_neg());
  252. if (!(TEST_true(BN_RECP_CTX_set(recp, b, ctx))
  253. && TEST_true(BN_div_recp(d, c, a, recp, ctx))
  254. && TEST_true(BN_mul(e, d, b, ctx))
  255. && TEST_true(BN_add(d, e, c))
  256. && TEST_true(BN_sub(d, d, a))
  257. && TEST_BN_eq_zero(d)))
  258. goto err;
  259. }
  260. st = 1;
  261. err:
  262. BN_free(a);
  263. BN_free(b);
  264. BN_free(c);
  265. BN_free(d);
  266. BN_free(e);
  267. BN_RECP_CTX_free(recp);
  268. return st;
  269. }
  270. static int test_mod(void)
  271. {
  272. BIGNUM *a = NULL, *b = NULL, *c = NULL, *d = NULL, *e = NULL;
  273. int st = 0, i;
  274. if (!TEST_ptr(a = BN_new())
  275. || !TEST_ptr(b = BN_new())
  276. || !TEST_ptr(c = BN_new())
  277. || !TEST_ptr(d = BN_new())
  278. || !TEST_ptr(e = BN_new()))
  279. goto err;
  280. if (!(TEST_true(BN_bntest_rand(a, 1024, 0, 0))))
  281. goto err;
  282. for (i = 0; i < NUM0; i++) {
  283. if (!(TEST_true(BN_bntest_rand(b, 450 + i * 10, 0, 0))))
  284. goto err;
  285. BN_set_negative(a, rand_neg());
  286. BN_set_negative(b, rand_neg());
  287. if (!(TEST_true(BN_mod(c, a, b, ctx))
  288. && TEST_true(BN_div(d, e, a, b, ctx))
  289. && TEST_true(BN_sub(e, e, c))
  290. && TEST_BN_eq_zero(e)))
  291. goto err;
  292. }
  293. st = 1;
  294. err:
  295. BN_free(a);
  296. BN_free(b);
  297. BN_free(c);
  298. BN_free(d);
  299. BN_free(e);
  300. return st;
  301. }
  302. static const char *bn1strings[] = {
  303. "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF",
  304. "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF",
  305. "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF",
  306. "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF",
  307. "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF",
  308. "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF",
  309. "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF",
  310. "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF00000000000000FFFFFFFF00",
  311. "0000000000000000000000000000000000000000000000000000000000000000",
  312. "0000000000000000000000000000000000000000000000000000000000000000",
  313. "0000000000000000000000000000000000000000000000000000000000000000",
  314. "0000000000000000000000000000000000000000000000000000000000000000",
  315. "0000000000000000000000000000000000000000000000000000000000000000",
  316. "0000000000000000000000000000000000000000000000000000000000000000",
  317. "0000000000000000000000000000000000000000000000000000000000000000",
  318. "00000000000000000000000000000000000000000000000000FFFFFFFFFFFFFF",
  319. NULL
  320. };
  321. static const char *bn2strings[] = {
  322. "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF",
  323. "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF",
  324. "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF",
  325. "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF",
  326. "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF",
  327. "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF",
  328. "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF",
  329. "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF00000000000000FFFFFFFF0000000000",
  330. "0000000000000000000000000000000000000000000000000000000000000000",
  331. "0000000000000000000000000000000000000000000000000000000000000000",
  332. "0000000000000000000000000000000000000000000000000000000000000000",
  333. "0000000000000000000000000000000000000000000000000000000000000000",
  334. "0000000000000000000000000000000000000000000000000000000000000000",
  335. "0000000000000000000000000000000000000000000000000000000000000000",
  336. "0000000000000000000000000000000000000000000000000000000000000000",
  337. "000000000000000000000000000000000000000000FFFFFFFFFFFFFF00000000",
  338. NULL
  339. };
  340. /*
  341. * Test constant-time modular exponentiation with 1024-bit inputs, which on
  342. * x86_64 cause a different code branch to be taken.
  343. */
  344. static int test_modexp_mont5(void)
  345. {
  346. BIGNUM *a = NULL, *p = NULL, *m = NULL, *d = NULL, *e = NULL;
  347. BIGNUM *b = NULL, *n = NULL, *c = NULL;
  348. BN_MONT_CTX *mont = NULL;
  349. int st = 0;
  350. if (!TEST_ptr(a = BN_new())
  351. || !TEST_ptr(p = BN_new())
  352. || !TEST_ptr(m = BN_new())
  353. || !TEST_ptr(d = BN_new())
  354. || !TEST_ptr(e = BN_new())
  355. || !TEST_ptr(b = BN_new())
  356. || !TEST_ptr(n = BN_new())
  357. || !TEST_ptr(c = BN_new())
  358. || !TEST_ptr(mont = BN_MONT_CTX_new()))
  359. goto err;
  360. /* must be odd for montgomery */
  361. if (!(TEST_true(BN_bntest_rand(m, 1024, 0, 1))
  362. /* Zero exponent */
  363. && TEST_true(BN_bntest_rand(a, 1024, 0, 0))))
  364. goto err;
  365. BN_zero(p);
  366. if (!TEST_true(BN_mod_exp_mont_consttime(d, a, p, m, ctx, NULL)))
  367. goto err;
  368. if (!TEST_BN_eq_one(d))
  369. goto err;
  370. /* Regression test for carry bug in mulx4x_mont */
  371. if (!(TEST_true(BN_hex2bn(&a,
  372. "7878787878787878787878787878787878787878787878787878787878787878"
  373. "7878787878787878787878787878787878787878787878787878787878787878"
  374. "7878787878787878787878787878787878787878787878787878787878787878"
  375. "7878787878787878787878787878787878787878787878787878787878787878"))
  376. && TEST_true(BN_hex2bn(&b,
  377. "095D72C08C097BA488C5E439C655A192EAFB6380073D8C2664668EDDB4060744"
  378. "E16E57FB4EDB9AE10A0CEFCDC28A894F689A128379DB279D48A2E20849D68593"
  379. "9B7803BCF46CEBF5C533FB0DD35B080593DE5472E3FE5DB951B8BFF9B4CB8F03"
  380. "9CC638A5EE8CDD703719F8000E6A9F63BEED5F2FCD52FF293EA05A251BB4AB81"))
  381. && TEST_true(BN_hex2bn(&n,
  382. "D78AF684E71DB0C39CFF4E64FB9DB567132CB9C50CC98009FEB820B26F2DED9B"
  383. "91B9B5E2B83AE0AE4EB4E0523CA726BFBE969B89FD754F674CE99118C3F2D1C5"
  384. "D81FDC7C54E02B60262B241D53C040E99E45826ECA37A804668E690E1AFC1CA4"
  385. "2C9A15D84D4954425F0B7642FC0BD9D7B24E2618D2DCC9B729D944BADACFDDAF"))))
  386. goto err;
  387. if (!(TEST_true(BN_MONT_CTX_set(mont, n, ctx))
  388. && TEST_true(BN_mod_mul_montgomery(c, a, b, mont, ctx))
  389. && TEST_true(BN_mod_mul_montgomery(d, b, a, mont, ctx))
  390. && TEST_BN_eq(c, d)))
  391. goto err;
  392. /* Regression test for carry bug in sqr[x]8x_mont */
  393. if (!(TEST_true(parse_bigBN(&n, bn1strings))
  394. && TEST_true(parse_bigBN(&a, bn2strings))))
  395. goto err;
  396. BN_free(b);
  397. if (!(TEST_ptr(b = BN_dup(a))
  398. && TEST_true(BN_MONT_CTX_set(mont, n, ctx))
  399. && TEST_true(BN_mod_mul_montgomery(c, a, a, mont, ctx))
  400. && TEST_true(BN_mod_mul_montgomery(d, a, b, mont, ctx))
  401. && TEST_BN_eq(c, d)))
  402. goto err;
  403. /* Regression test for carry bug in bn_sqrx8x_internal */
  404. {
  405. static const char *ahex[] = {
  406. "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF",
  407. "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF",
  408. "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF",
  409. "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF",
  410. "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF8FFEADBCFC4DAE7FFF908E92820306B",
  411. "9544D954000000006C0000000000000000000000000000000000000000000000",
  412. "00000000000000000000FF030202FFFFF8FFEBDBCFC4DAE7FFF908E92820306B",
  413. "9544D954000000006C000000FF0302030000000000FFFFFFFFFFFFFFFFFFFFFF",
  414. "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF01FC00FF02FFFFFFFF",
  415. "00FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF00FCFD",
  416. "FCFFFFFFFFFF000000000000000000FF0302030000000000FFFFFFFFFFFFFFFF",
  417. "FF00FCFDFDFF030202FF00000000FFFFFFFFFFFFFFFFFF00FCFDFCFFFFFFFFFF",
  418. NULL
  419. };
  420. static const char *nhex[] = {
  421. "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF",
  422. "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF",
  423. "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF",
  424. "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF",
  425. "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF8F8F8F8000000",
  426. "00000010000000006C0000000000000000000000000000000000000000000000",
  427. "00000000000000000000000000000000000000FFFFFFFFFFFFF8F8F8F8000000",
  428. "00000010000000006C000000000000000000000000FFFFFFFFFFFFFFFFFFFFFF",
  429. "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF",
  430. "00FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF",
  431. "FFFFFFFFFFFF000000000000000000000000000000000000FFFFFFFFFFFFFFFF",
  432. "FFFFFFFFFFFFFFFFFFFF00000000FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF",
  433. NULL
  434. };
  435. if (!(TEST_true(parse_bigBN(&a, ahex))
  436. && TEST_true(parse_bigBN(&n, nhex))))
  437. goto err;
  438. }
  439. BN_free(b);
  440. if (!(TEST_ptr(b = BN_dup(a))
  441. && TEST_true(BN_MONT_CTX_set(mont, n, ctx))))
  442. goto err;
  443. if (!TEST_true(BN_mod_mul_montgomery(c, a, a, mont, ctx))
  444. || !TEST_true(BN_mod_mul_montgomery(d, a, b, mont, ctx))
  445. || !TEST_BN_eq(c, d))
  446. goto err;
  447. /* Regression test for bug in BN_from_montgomery_word */
  448. if (!(TEST_true(BN_hex2bn(&a,
  449. "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF"
  450. "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF"
  451. "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF"))
  452. && TEST_true(BN_hex2bn(&n,
  453. "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF"
  454. "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF"))
  455. && TEST_true(BN_MONT_CTX_set(mont, n, ctx))
  456. && TEST_false(BN_mod_mul_montgomery(d, a, a, mont, ctx))))
  457. goto err;
  458. /* Regression test for bug in rsaz_1024_mul_avx2 */
  459. if (!(TEST_true(BN_hex2bn(&a,
  460. "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF"
  461. "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF"
  462. "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF"
  463. "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF2020202020DF"))
  464. && TEST_true(BN_hex2bn(&b,
  465. "2020202020202020202020202020202020202020202020202020202020202020"
  466. "2020202020202020202020202020202020202020202020202020202020202020"
  467. "20202020202020FF202020202020202020202020202020202020202020202020"
  468. "2020202020202020202020202020202020202020202020202020202020202020"))
  469. && TEST_true(BN_hex2bn(&n,
  470. "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF"
  471. "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF"
  472. "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF"
  473. "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF2020202020FF"))
  474. && TEST_true(BN_MONT_CTX_set(mont, n, ctx))
  475. && TEST_true(BN_mod_exp_mont_consttime(c, a, b, n, ctx, mont))
  476. && TEST_true(BN_mod_exp_mont(d, a, b, n, ctx, mont))
  477. && TEST_BN_eq(c, d)))
  478. goto err;
  479. /*
  480. * rsaz_1024_mul_avx2 expects fully-reduced inputs.
  481. * BN_mod_exp_mont_consttime should reduce the input first.
  482. */
  483. if (!(TEST_true(BN_hex2bn(&a,
  484. "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF"
  485. "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF"
  486. "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF"
  487. "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF2020202020DF"))
  488. && TEST_true(BN_hex2bn(&b,
  489. "1FA53F26F8811C58BE0357897AA5E165693230BC9DF5F01DFA6A2D59229EC69D"
  490. "9DE6A89C36E3B6957B22D6FAAD5A3C73AE587B710DBE92E83D3A9A3339A085CB"
  491. "B58F508CA4F837924BB52CC1698B7FDC2FD74362456A595A5B58E38E38E38E38"
  492. "E38E38E38E38E38E38E38E38E38E38E38E38E38E38E38E38E38E38E38E38E38E"))
  493. && TEST_true(BN_hex2bn(&n,
  494. "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF"
  495. "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF"
  496. "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF"
  497. "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF2020202020DF"))
  498. && TEST_true(BN_MONT_CTX_set(mont, n, ctx))
  499. && TEST_true(BN_mod_exp_mont_consttime(c, a, b, n, ctx, mont))))
  500. goto err;
  501. BN_zero(d);
  502. if (!TEST_BN_eq(c, d))
  503. goto err;
  504. /* Zero input */
  505. if (!TEST_true(BN_bntest_rand(p, 1024, 0, 0)))
  506. goto err;
  507. BN_zero(a);
  508. if (!TEST_true(BN_mod_exp_mont_consttime(d, a, p, m, ctx, NULL))
  509. || !TEST_BN_eq_zero(d))
  510. goto err;
  511. /*
  512. * Craft an input whose Montgomery representation is 1, i.e., shorter
  513. * than the modulus m, in order to test the const time precomputation
  514. * scattering/gathering.
  515. */
  516. if (!(TEST_true(BN_one(a))
  517. && TEST_true(BN_MONT_CTX_set(mont, m, ctx))))
  518. goto err;
  519. if (!TEST_true(BN_from_montgomery(e, a, mont, ctx))
  520. || !TEST_true(BN_mod_exp_mont_consttime(d, e, p, m, ctx, NULL))
  521. || !TEST_true(BN_mod_exp_simple(a, e, p, m, ctx))
  522. || !TEST_BN_eq(a, d))
  523. goto err;
  524. /* Finally, some regular test vectors. */
  525. if (!(TEST_true(BN_bntest_rand(e, 1024, 0, 0))
  526. && TEST_true(BN_mod_exp_mont_consttime(d, e, p, m, ctx, NULL))
  527. && TEST_true(BN_mod_exp_simple(a, e, p, m, ctx))
  528. && TEST_BN_eq(a, d)))
  529. goto err;
  530. st = 1;
  531. err:
  532. BN_MONT_CTX_free(mont);
  533. BN_free(a);
  534. BN_free(p);
  535. BN_free(m);
  536. BN_free(d);
  537. BN_free(e);
  538. BN_free(b);
  539. BN_free(n);
  540. BN_free(c);
  541. return st;
  542. }
  543. #ifndef OPENSSL_NO_EC2M
  544. static int test_gf2m_add(void)
  545. {
  546. BIGNUM *a = NULL, *b = NULL, *c = NULL;
  547. int i, st = 0;
  548. if (!TEST_ptr(a = BN_new())
  549. || !TEST_ptr(b = BN_new())
  550. || !TEST_ptr(c = BN_new()))
  551. goto err;
  552. for (i = 0; i < NUM0; i++) {
  553. if (!(TEST_true(BN_rand(a, 512, 0, 0))
  554. && TEST_ptr(BN_copy(b, BN_value_one()))))
  555. goto err;
  556. BN_set_negative(a, rand_neg());
  557. BN_set_negative(b, rand_neg());
  558. if (!(TEST_true(BN_GF2m_add(c, a, b))
  559. /* Test that two added values have the correct parity. */
  560. && TEST_false((BN_is_odd(a) && BN_is_odd(c))
  561. || (!BN_is_odd(a) && !BN_is_odd(c)))))
  562. goto err;
  563. if (!(TEST_true(BN_GF2m_add(c, c, c))
  564. /* Test that c + c = 0. */
  565. && TEST_BN_eq_zero(c)))
  566. goto err;
  567. }
  568. st = 1;
  569. err:
  570. BN_free(a);
  571. BN_free(b);
  572. BN_free(c);
  573. return st;
  574. }
  575. static int test_gf2m_mod(void)
  576. {
  577. BIGNUM *a = NULL, *b[2] = {NULL,NULL}, *c = NULL, *d = NULL, *e = NULL;
  578. int i, j, st = 0;
  579. if (!TEST_ptr(a = BN_new())
  580. || !TEST_ptr(b[0] = BN_new())
  581. || !TEST_ptr(b[1] = BN_new())
  582. || !TEST_ptr(c = BN_new())
  583. || !TEST_ptr(d = BN_new())
  584. || !TEST_ptr(e = BN_new()))
  585. goto err;
  586. if (!(TEST_true(BN_GF2m_arr2poly(p0, b[0]))
  587. && TEST_true(BN_GF2m_arr2poly(p1, b[1]))))
  588. goto err;
  589. for (i = 0; i < NUM0; i++) {
  590. if (!TEST_true(BN_bntest_rand(a, 1024, 0, 0)))
  591. goto err;
  592. for (j = 0; j < 2; j++) {
  593. if (!(TEST_true(BN_GF2m_mod(c, a, b[j]))
  594. && TEST_true(BN_GF2m_add(d, a, c))
  595. && TEST_true(BN_GF2m_mod(e, d, b[j]))
  596. /* Test that a + (a mod p) mod p == 0. */
  597. && TEST_BN_eq_zero(e)))
  598. goto err;
  599. }
  600. }
  601. st = 1;
  602. err:
  603. BN_free(a);
  604. BN_free(b[0]);
  605. BN_free(b[1]);
  606. BN_free(c);
  607. BN_free(d);
  608. BN_free(e);
  609. return st;
  610. }
  611. static int test_gf2m_mul(void)
  612. {
  613. BIGNUM *a, *b[2] = {NULL, NULL}, *c = NULL, *d = NULL;
  614. BIGNUM *e = NULL, *f = NULL, *g = NULL, *h = NULL;
  615. int i, j, st = 0;
  616. if (!TEST_ptr(a = BN_new())
  617. || !TEST_ptr(b[0] = BN_new())
  618. || !TEST_ptr(b[1] = BN_new())
  619. || !TEST_ptr(c = BN_new())
  620. || !TEST_ptr(d = BN_new())
  621. || !TEST_ptr(e = BN_new())
  622. || !TEST_ptr(f = BN_new())
  623. || !TEST_ptr(g = BN_new())
  624. || !TEST_ptr(h = BN_new()))
  625. goto err;
  626. if (!(TEST_true(BN_GF2m_arr2poly(p0, b[0]))
  627. && TEST_true(BN_GF2m_arr2poly(p1, b[1]))))
  628. goto err;
  629. for (i = 0; i < NUM0; i++) {
  630. if (!(TEST_true(BN_bntest_rand(a, 1024, 0, 0))
  631. && TEST_true(BN_bntest_rand(c, 1024, 0, 0))
  632. && TEST_true(BN_bntest_rand(d, 1024, 0, 0))))
  633. goto err;
  634. for (j = 0; j < 2; j++) {
  635. if (!(TEST_true(BN_GF2m_mod_mul(e, a, c, b[j], ctx))
  636. && TEST_true(BN_GF2m_add(f, a, d))
  637. && TEST_true(BN_GF2m_mod_mul(g, f, c, b[j], ctx))
  638. && TEST_true(BN_GF2m_mod_mul(h, d, c, b[j], ctx))
  639. && TEST_true(BN_GF2m_add(f, e, g))
  640. && TEST_true(BN_GF2m_add(f, f, h))
  641. /* Test that (a+d)*c = a*c + d*c. */
  642. && TEST_BN_eq_zero(f)))
  643. goto err;
  644. }
  645. }
  646. st = 1;
  647. err:
  648. BN_free(a);
  649. BN_free(b[0]);
  650. BN_free(b[1]);
  651. BN_free(c);
  652. BN_free(d);
  653. BN_free(e);
  654. BN_free(f);
  655. BN_free(g);
  656. BN_free(h);
  657. return st;
  658. }
  659. static int test_gf2m_sqr(void)
  660. {
  661. BIGNUM *a = NULL, *b[2] = {NULL,NULL}, *c = NULL, *d = NULL;
  662. int i, j, st = 0;
  663. if (!TEST_ptr(a = BN_new())
  664. || !TEST_ptr(b[0] = BN_new())
  665. || !TEST_ptr(b[1] = BN_new())
  666. || !TEST_ptr(c = BN_new())
  667. || !TEST_ptr(d = BN_new()))
  668. goto err;
  669. if (!(TEST_true(BN_GF2m_arr2poly(p0, b[0]))
  670. && TEST_true(BN_GF2m_arr2poly(p1, b[1]))))
  671. goto err;
  672. for (i = 0; i < NUM0; i++) {
  673. if (!TEST_true(BN_bntest_rand(a, 1024, 0, 0)))
  674. goto err;
  675. for (j = 0; j < 2; j++) {
  676. if (!(TEST_true(BN_GF2m_mod_sqr(c, a, b[j], ctx))
  677. && TEST_true(BN_copy(d, a))
  678. && TEST_true(BN_GF2m_mod_mul(d, a, d, b[j], ctx))
  679. && TEST_true(BN_GF2m_add(d, c, d))
  680. /* Test that a*a = a^2. */
  681. && TEST_BN_eq_zero(d)))
  682. goto err;
  683. }
  684. }
  685. st = 1;
  686. err:
  687. BN_free(a);
  688. BN_free(b[0]);
  689. BN_free(b[1]);
  690. BN_free(c);
  691. BN_free(d);
  692. return st;
  693. }
  694. static int test_gf2m_modinv(void)
  695. {
  696. BIGNUM *a = NULL, *b[2] = {NULL,NULL}, *c = NULL, *d = NULL;
  697. int i, j, st = 0;
  698. if (!TEST_ptr(a = BN_new())
  699. || !TEST_ptr(b[0] = BN_new())
  700. || !TEST_ptr(b[1] = BN_new())
  701. || !TEST_ptr(c = BN_new())
  702. || !TEST_ptr(d = BN_new()))
  703. goto err;
  704. if (!(TEST_true(BN_GF2m_arr2poly(p0, b[0]))
  705. && TEST_true(BN_GF2m_arr2poly(p1, b[1]))))
  706. goto err;
  707. for (i = 0; i < NUM0; i++) {
  708. if (!TEST_true(BN_bntest_rand(a, 512, 0, 0)))
  709. goto err;
  710. for (j = 0; j < 2; j++) {
  711. if (!(TEST_true(BN_GF2m_mod_inv(c, a, b[j], ctx))
  712. && TEST_true(BN_GF2m_mod_mul(d, a, c, b[j], ctx))
  713. /* Test that ((1/a)*a) = 1. */
  714. && TEST_BN_eq_one(d)))
  715. goto err;
  716. }
  717. }
  718. st = 1;
  719. err:
  720. BN_free(a);
  721. BN_free(b[0]);
  722. BN_free(b[1]);
  723. BN_free(c);
  724. BN_free(d);
  725. return st;
  726. }
  727. static int test_gf2m_moddiv(void)
  728. {
  729. BIGNUM *a = NULL, *b[2] = {NULL,NULL}, *c = NULL, *d = NULL;
  730. BIGNUM *e = NULL, *f = NULL;
  731. int i, j, st = 0;
  732. if (!TEST_ptr(a = BN_new())
  733. || !TEST_ptr(b[0] = BN_new())
  734. || !TEST_ptr(b[1] = BN_new())
  735. || !TEST_ptr(c = BN_new())
  736. || !TEST_ptr(d = BN_new())
  737. || !TEST_ptr(e = BN_new())
  738. || !TEST_ptr(f = BN_new()))
  739. goto err;
  740. if (!(TEST_true(BN_GF2m_arr2poly(p0, b[0]))
  741. && TEST_true(BN_GF2m_arr2poly(p1, b[1]))))
  742. goto err;
  743. for (i = 0; i < NUM0; i++) {
  744. if (!(TEST_true(BN_bntest_rand(a, 512, 0, 0))
  745. && TEST_true(BN_bntest_rand(c, 512, 0, 0))))
  746. goto err;
  747. for (j = 0; j < 2; j++) {
  748. if (!(TEST_true(BN_GF2m_mod_div(d, a, c, b[j], ctx))
  749. && TEST_true(BN_GF2m_mod_mul(e, d, c, b[j], ctx))
  750. && TEST_true(BN_GF2m_mod_div(f, a, e, b[j], ctx))
  751. /* Test that ((a/c)*c)/a = 1. */
  752. && TEST_BN_eq_one(f)))
  753. goto err;
  754. }
  755. }
  756. st = 1;
  757. err:
  758. BN_free(a);
  759. BN_free(b[0]);
  760. BN_free(b[1]);
  761. BN_free(c);
  762. BN_free(d);
  763. BN_free(e);
  764. BN_free(f);
  765. return st;
  766. }
  767. static int test_gf2m_modexp(void)
  768. {
  769. BIGNUM *a = NULL, *b[2] = {NULL,NULL}, *c = NULL, *d = NULL;
  770. BIGNUM *e = NULL, *f = NULL;
  771. int i, j, st = 0;
  772. if (!TEST_ptr(a = BN_new())
  773. || !TEST_ptr(b[0] = BN_new())
  774. || !TEST_ptr(b[1] = BN_new())
  775. || !TEST_ptr(c = BN_new())
  776. || !TEST_ptr(d = BN_new())
  777. || !TEST_ptr(e = BN_new())
  778. || !TEST_ptr(f = BN_new()))
  779. goto err;
  780. if (!(TEST_true(BN_GF2m_arr2poly(p0, b[0]))
  781. && TEST_true(BN_GF2m_arr2poly(p1, b[1]))))
  782. goto err;
  783. for (i = 0; i < NUM0; i++) {
  784. if (!(TEST_true(BN_bntest_rand(a, 512, 0, 0))
  785. && TEST_true(BN_bntest_rand(c, 512, 0, 0))
  786. && TEST_true(BN_bntest_rand(d, 512, 0, 0))))
  787. goto err;
  788. for (j = 0; j < 2; j++) {
  789. if (!(TEST_true(BN_GF2m_mod_exp(e, a, c, b[j], ctx))
  790. && TEST_true(BN_GF2m_mod_exp(f, a, d, b[j], ctx))
  791. && TEST_true(BN_GF2m_mod_mul(e, e, f, b[j], ctx))
  792. && TEST_true(BN_add(f, c, d))
  793. && TEST_true(BN_GF2m_mod_exp(f, a, f, b[j], ctx))
  794. && TEST_true(BN_GF2m_add(f, e, f))
  795. /* Test that a^(c+d)=a^c*a^d. */
  796. && TEST_BN_eq_zero(f)))
  797. goto err;
  798. }
  799. }
  800. st = 1;
  801. err:
  802. BN_free(a);
  803. BN_free(b[0]);
  804. BN_free(b[1]);
  805. BN_free(c);
  806. BN_free(d);
  807. BN_free(e);
  808. BN_free(f);
  809. return st;
  810. }
  811. static int test_gf2m_modsqrt(void)
  812. {
  813. BIGNUM *a = NULL, *b[2] = {NULL,NULL}, *c = NULL, *d = NULL;
  814. BIGNUM *e = NULL, *f = NULL;
  815. int i, j, st = 0;
  816. if (!TEST_ptr(a = BN_new())
  817. || !TEST_ptr(b[0] = BN_new())
  818. || !TEST_ptr(b[1] = BN_new())
  819. || !TEST_ptr(c = BN_new())
  820. || !TEST_ptr(d = BN_new())
  821. || !TEST_ptr(e = BN_new())
  822. || !TEST_ptr(f = BN_new()))
  823. goto err;
  824. if (!(TEST_true(BN_GF2m_arr2poly(p0, b[0]))
  825. && TEST_true(BN_GF2m_arr2poly(p1, b[1]))))
  826. goto err;
  827. for (i = 0; i < NUM0; i++) {
  828. if (!TEST_true(BN_bntest_rand(a, 512, 0, 0)))
  829. goto err;
  830. for (j = 0; j < 2; j++) {
  831. if (!(TEST_true(BN_GF2m_mod(c, a, b[j]))
  832. && TEST_true(BN_GF2m_mod_sqrt(d, a, b[j], ctx))
  833. && TEST_true(BN_GF2m_mod_sqr(e, d, b[j], ctx))
  834. && TEST_true(BN_GF2m_add(f, c, e))
  835. /* Test that d^2 = a, where d = sqrt(a). */
  836. && TEST_BN_eq_zero(f)))
  837. goto err;
  838. }
  839. }
  840. st = 1;
  841. err:
  842. BN_free(a);
  843. BN_free(b[0]);
  844. BN_free(b[1]);
  845. BN_free(c);
  846. BN_free(d);
  847. BN_free(e);
  848. BN_free(f);
  849. return st;
  850. }
  851. static int test_gf2m_modsolvequad(void)
  852. {
  853. BIGNUM *a = NULL, *b[2] = {NULL,NULL}, *c = NULL, *d = NULL;
  854. BIGNUM *e = NULL;
  855. int i, j, s = 0, t, st = 0;
  856. if (!TEST_ptr(a = BN_new())
  857. || !TEST_ptr(b[0] = BN_new())
  858. || !TEST_ptr(b[1] = BN_new())
  859. || !TEST_ptr(c = BN_new())
  860. || !TEST_ptr(d = BN_new())
  861. || !TEST_ptr(e = BN_new()))
  862. goto err;
  863. if (!(TEST_true(BN_GF2m_arr2poly(p0, b[0]))
  864. && TEST_true(BN_GF2m_arr2poly(p1, b[1]))))
  865. goto err;
  866. for (i = 0; i < NUM0; i++) {
  867. if (!TEST_true(BN_bntest_rand(a, 512, 0, 0)))
  868. goto err;
  869. for (j = 0; j < 2; j++) {
  870. t = BN_GF2m_mod_solve_quad(c, a, b[j], ctx);
  871. if (t) {
  872. s++;
  873. if (!(TEST_true(BN_GF2m_mod_sqr(d, c, b[j], ctx))
  874. && TEST_true(BN_GF2m_add(d, c, d))
  875. && TEST_true(BN_GF2m_mod(e, a, b[j]))
  876. && TEST_true(BN_GF2m_add(e, e, d))
  877. /*
  878. * Test that solution of quadratic c
  879. * satisfies c^2 + c = a.
  880. */
  881. && TEST_BN_eq_zero(e)))
  882. goto err;
  883. }
  884. }
  885. }
  886. if (!TEST_int_ge(s, 0)) {
  887. TEST_info("%d tests found no roots; probably an error", NUM0);
  888. goto err;
  889. }
  890. st = 1;
  891. err:
  892. BN_free(a);
  893. BN_free(b[0]);
  894. BN_free(b[1]);
  895. BN_free(c);
  896. BN_free(d);
  897. BN_free(e);
  898. return st;
  899. }
  900. #endif
  901. static int test_kronecker(void)
  902. {
  903. BIGNUM *a = NULL, *b = NULL, *r = NULL, *t = NULL;
  904. int i, legendre, kronecker, st = 0;
  905. if (!TEST_ptr(a = BN_new())
  906. || !TEST_ptr(b = BN_new())
  907. || !TEST_ptr(r = BN_new())
  908. || !TEST_ptr(t = BN_new()))
  909. goto err;
  910. /*
  911. * We test BN_kronecker(a, b, ctx) just for b odd (Jacobi symbol). In
  912. * this case we know that if b is prime, then BN_kronecker(a, b, ctx) is
  913. * congruent to $a^{(b-1)/2}$, modulo $b$ (Legendre symbol). So we
  914. * generate a random prime b and compare these values for a number of
  915. * random a's. (That is, we run the Solovay-Strassen primality test to
  916. * confirm that b is prime, except that we don't want to test whether b
  917. * is prime but whether BN_kronecker works.)
  918. */
  919. if (!TEST_true(BN_generate_prime_ex(b, 512, 0, NULL, NULL, NULL)))
  920. goto err;
  921. BN_set_negative(b, rand_neg());
  922. for (i = 0; i < NUM0; i++) {
  923. if (!TEST_true(BN_bntest_rand(a, 512, 0, 0)))
  924. goto err;
  925. BN_set_negative(a, rand_neg());
  926. /* t := (|b|-1)/2 (note that b is odd) */
  927. if (!TEST_true(BN_copy(t, b)))
  928. goto err;
  929. BN_set_negative(t, 0);
  930. if (!TEST_true(BN_sub_word(t, 1)))
  931. goto err;
  932. if (!TEST_true(BN_rshift1(t, t)))
  933. goto err;
  934. /* r := a^t mod b */
  935. BN_set_negative(b, 0);
  936. if (!TEST_true(BN_mod_exp_recp(r, a, t, b, ctx)))
  937. goto err;
  938. BN_set_negative(b, 1);
  939. if (BN_is_word(r, 1))
  940. legendre = 1;
  941. else if (BN_is_zero(r))
  942. legendre = 0;
  943. else {
  944. if (!TEST_true(BN_add_word(r, 1)))
  945. goto err;
  946. if (!TEST_int_eq(BN_ucmp(r, b), 0)) {
  947. TEST_info("Legendre symbol computation failed");
  948. goto err;
  949. }
  950. legendre = -1;
  951. }
  952. if (!TEST_int_ge(kronecker = BN_kronecker(a, b, ctx), -1))
  953. goto err;
  954. /* we actually need BN_kronecker(a, |b|) */
  955. if (BN_is_negative(a) && BN_is_negative(b))
  956. kronecker = -kronecker;
  957. if (!TEST_int_eq(legendre, kronecker))
  958. goto err;
  959. }
  960. st = 1;
  961. err:
  962. BN_free(a);
  963. BN_free(b);
  964. BN_free(r);
  965. BN_free(t);
  966. return st;
  967. }
  968. static int file_sum(STANZA *s)
  969. {
  970. BIGNUM *a = NULL, *b = NULL, *sum = NULL, *ret = NULL;
  971. BN_ULONG b_word;
  972. int st = 0;
  973. if (!TEST_ptr(a = getBN(s, "A"))
  974. || !TEST_ptr(b = getBN(s, "B"))
  975. || !TEST_ptr(sum = getBN(s, "Sum"))
  976. || !TEST_ptr(ret = BN_new()))
  977. goto err;
  978. if (!TEST_true(BN_add(ret, a, b))
  979. || !equalBN("A + B", sum, ret)
  980. || !TEST_true(BN_sub(ret, sum, a))
  981. || !equalBN("Sum - A", b, ret)
  982. || !TEST_true(BN_sub(ret, sum, b))
  983. || !equalBN("Sum - B", a, ret))
  984. goto err;
  985. /*
  986. * Test that the functions work when |r| and |a| point to the same BIGNUM,
  987. * or when |r| and |b| point to the same BIGNUM.
  988. * TODO: Test where all of |r|, |a|, and |b| point to the same BIGNUM.
  989. */
  990. if (!TEST_true(BN_copy(ret, a))
  991. || !TEST_true(BN_add(ret, ret, b))
  992. || !equalBN("A + B (r is a)", sum, ret)
  993. || !TEST_true(BN_copy(ret, b))
  994. || !TEST_true(BN_add(ret, a, ret))
  995. || !equalBN("A + B (r is b)", sum, ret)
  996. || !TEST_true(BN_copy(ret, sum))
  997. || !TEST_true(BN_sub(ret, ret, a))
  998. || !equalBN("Sum - A (r is a)", b, ret)
  999. || !TEST_true(BN_copy(ret, a))
  1000. || !TEST_true(BN_sub(ret, sum, ret))
  1001. || !equalBN("Sum - A (r is b)", b, ret)
  1002. || !TEST_true(BN_copy(ret, sum))
  1003. || !TEST_true(BN_sub(ret, ret, b))
  1004. || !equalBN("Sum - B (r is a)", a, ret)
  1005. || !TEST_true(BN_copy(ret, b))
  1006. || !TEST_true(BN_sub(ret, sum, ret))
  1007. || !equalBN("Sum - B (r is b)", a, ret))
  1008. goto err;
  1009. /*
  1010. * Test BN_uadd() and BN_usub() with the prerequisites they are
  1011. * documented as having. Note that these functions are frequently used
  1012. * when the prerequisites don't hold. In those cases, they are supposed
  1013. * to work as if the prerequisite hold, but we don't test that yet.
  1014. * TODO: test that.
  1015. */
  1016. if (!BN_is_negative(a) && !BN_is_negative(b) && BN_cmp(a, b) >= 0) {
  1017. if (!TEST_true(BN_uadd(ret, a, b))
  1018. || !equalBN("A +u B", sum, ret)
  1019. || !TEST_true(BN_usub(ret, sum, a))
  1020. || !equalBN("Sum -u A", b, ret)
  1021. || !TEST_true(BN_usub(ret, sum, b))
  1022. || !equalBN("Sum -u B", a, ret))
  1023. goto err;
  1024. /*
  1025. * Test that the functions work when |r| and |a| point to the same
  1026. * BIGNUM, or when |r| and |b| point to the same BIGNUM.
  1027. * TODO: Test where all of |r|, |a|, and |b| point to the same BIGNUM.
  1028. */
  1029. if (!TEST_true(BN_copy(ret, a))
  1030. || !TEST_true(BN_uadd(ret, ret, b))
  1031. || !equalBN("A +u B (r is a)", sum, ret)
  1032. || !TEST_true(BN_copy(ret, b))
  1033. || !TEST_true(BN_uadd(ret, a, ret))
  1034. || !equalBN("A +u B (r is b)", sum, ret)
  1035. || !TEST_true(BN_copy(ret, sum))
  1036. || !TEST_true(BN_usub(ret, ret, a))
  1037. || !equalBN("Sum -u A (r is a)", b, ret)
  1038. || !TEST_true(BN_copy(ret, a))
  1039. || !TEST_true(BN_usub(ret, sum, ret))
  1040. || !equalBN("Sum -u A (r is b)", b, ret)
  1041. || !TEST_true(BN_copy(ret, sum))
  1042. || !TEST_true(BN_usub(ret, ret, b))
  1043. || !equalBN("Sum -u B (r is a)", a, ret)
  1044. || !TEST_true(BN_copy(ret, b))
  1045. || !TEST_true(BN_usub(ret, sum, ret))
  1046. || !equalBN("Sum -u B (r is b)", a, ret))
  1047. goto err;
  1048. }
  1049. /*
  1050. * Test with BN_add_word() and BN_sub_word() if |b| is small enough.
  1051. */
  1052. b_word = BN_get_word(b);
  1053. if (!BN_is_negative(b) && b_word != (BN_ULONG)-1) {
  1054. if (!TEST_true(BN_copy(ret, a))
  1055. || !TEST_true(BN_add_word(ret, b_word))
  1056. || !equalBN("A + B (word)", sum, ret)
  1057. || !TEST_true(BN_copy(ret, sum))
  1058. || !TEST_true(BN_sub_word(ret, b_word))
  1059. || !equalBN("Sum - B (word)", a, ret))
  1060. goto err;
  1061. }
  1062. st = 1;
  1063. err:
  1064. BN_free(a);
  1065. BN_free(b);
  1066. BN_free(sum);
  1067. BN_free(ret);
  1068. return st;
  1069. }
  1070. static int file_lshift1(STANZA *s)
  1071. {
  1072. BIGNUM *a = NULL, *lshift1 = NULL, *zero = NULL, *ret = NULL;
  1073. BIGNUM *two = NULL, *remainder = NULL;
  1074. int st = 0;
  1075. if (!TEST_ptr(a = getBN(s, "A"))
  1076. || !TEST_ptr(lshift1 = getBN(s, "LShift1"))
  1077. || !TEST_ptr(zero = BN_new())
  1078. || !TEST_ptr(ret = BN_new())
  1079. || !TEST_ptr(two = BN_new())
  1080. || !TEST_ptr(remainder = BN_new()))
  1081. goto err;
  1082. BN_zero(zero);
  1083. if (!TEST_true(BN_set_word(two, 2))
  1084. || !TEST_true(BN_add(ret, a, a))
  1085. || !equalBN("A + A", lshift1, ret)
  1086. || !TEST_true(BN_mul(ret, a, two, ctx))
  1087. || !equalBN("A * 2", lshift1, ret)
  1088. || !TEST_true(BN_div(ret, remainder, lshift1, two, ctx))
  1089. || !equalBN("LShift1 / 2", a, ret)
  1090. || !equalBN("LShift1 % 2", zero, remainder)
  1091. || !TEST_true(BN_lshift1(ret, a))
  1092. || !equalBN("A << 1", lshift1, ret)
  1093. || !TEST_true(BN_rshift1(ret, lshift1))
  1094. || !equalBN("LShift >> 1", a, ret)
  1095. || !TEST_true(BN_rshift1(ret, lshift1))
  1096. || !equalBN("LShift >> 1", a, ret))
  1097. goto err;
  1098. /* Set the LSB to 1 and test rshift1 again. */
  1099. if (!TEST_true(BN_set_bit(lshift1, 0))
  1100. || !TEST_true(BN_div(ret, NULL /* rem */ , lshift1, two, ctx))
  1101. || !equalBN("(LShift1 | 1) / 2", a, ret)
  1102. || !TEST_true(BN_rshift1(ret, lshift1))
  1103. || !equalBN("(LShift | 1) >> 1", a, ret))
  1104. goto err;
  1105. st = 1;
  1106. err:
  1107. BN_free(a);
  1108. BN_free(lshift1);
  1109. BN_free(zero);
  1110. BN_free(ret);
  1111. BN_free(two);
  1112. BN_free(remainder);
  1113. return st;
  1114. }
  1115. static int file_lshift(STANZA *s)
  1116. {
  1117. BIGNUM *a = NULL, *lshift = NULL, *ret = NULL;
  1118. int n = 0, st = 0;
  1119. if (!TEST_ptr(a = getBN(s, "A"))
  1120. || !TEST_ptr(lshift = getBN(s, "LShift"))
  1121. || !TEST_ptr(ret = BN_new())
  1122. || !getint(s, &n, "N"))
  1123. goto err;
  1124. if (!TEST_true(BN_lshift(ret, a, n))
  1125. || !equalBN("A << N", lshift, ret)
  1126. || !TEST_true(BN_rshift(ret, lshift, n))
  1127. || !equalBN("A >> N", a, ret))
  1128. goto err;
  1129. st = 1;
  1130. err:
  1131. BN_free(a);
  1132. BN_free(lshift);
  1133. BN_free(ret);
  1134. return st;
  1135. }
  1136. static int file_rshift(STANZA *s)
  1137. {
  1138. BIGNUM *a = NULL, *rshift = NULL, *ret = NULL;
  1139. int n = 0, st = 0;
  1140. if (!TEST_ptr(a = getBN(s, "A"))
  1141. || !TEST_ptr(rshift = getBN(s, "RShift"))
  1142. || !TEST_ptr(ret = BN_new())
  1143. || !getint(s, &n, "N"))
  1144. goto err;
  1145. if (!TEST_true(BN_rshift(ret, a, n))
  1146. || !equalBN("A >> N", rshift, ret))
  1147. goto err;
  1148. /* If N == 1, try with rshift1 as well */
  1149. if (n == 1) {
  1150. if (!TEST_true(BN_rshift1(ret, a))
  1151. || !equalBN("A >> 1 (rshift1)", rshift, ret))
  1152. goto err;
  1153. }
  1154. st = 1;
  1155. err:
  1156. BN_free(a);
  1157. BN_free(rshift);
  1158. BN_free(ret);
  1159. return st;
  1160. }
  1161. static int file_square(STANZA *s)
  1162. {
  1163. BIGNUM *a = NULL, *square = NULL, *zero = NULL, *ret = NULL;
  1164. BIGNUM *remainder = NULL, *tmp = NULL;
  1165. int st = 0;
  1166. if (!TEST_ptr(a = getBN(s, "A"))
  1167. || !TEST_ptr(square = getBN(s, "Square"))
  1168. || !TEST_ptr(zero = BN_new())
  1169. || !TEST_ptr(ret = BN_new())
  1170. || !TEST_ptr(remainder = BN_new()))
  1171. goto err;
  1172. BN_zero(zero);
  1173. if (!TEST_true(BN_sqr(ret, a, ctx))
  1174. || !equalBN("A^2", square, ret)
  1175. || !TEST_true(BN_mul(ret, a, a, ctx))
  1176. || !equalBN("A * A", square, ret)
  1177. || !TEST_true(BN_div(ret, remainder, square, a, ctx))
  1178. || !equalBN("Square / A", a, ret)
  1179. || !equalBN("Square % A", zero, remainder))
  1180. goto err;
  1181. #if HAVE_BN_SQRT
  1182. BN_set_negative(a, 0);
  1183. if (!TEST_true(BN_sqrt(ret, square, ctx))
  1184. || !equalBN("sqrt(Square)", a, ret))
  1185. goto err;
  1186. /* BN_sqrt should fail on non-squares and negative numbers. */
  1187. if (!TEST_BN_eq_zero(square)) {
  1188. if (!TEST_ptr(tmp = BN_new())
  1189. || !TEST_true(BN_copy(tmp, square)))
  1190. goto err;
  1191. BN_set_negative(tmp, 1);
  1192. if (!TEST_int_eq(BN_sqrt(ret, tmp, ctx), 0))
  1193. goto err;
  1194. ERR_clear_error();
  1195. BN_set_negative(tmp, 0);
  1196. if (BN_add(tmp, tmp, BN_value_one()))
  1197. goto err;
  1198. if (!TEST_int_eq(BN_sqrt(ret, tmp, ctx)))
  1199. goto err;
  1200. ERR_clear_error();
  1201. }
  1202. #endif
  1203. st = 1;
  1204. err:
  1205. BN_free(a);
  1206. BN_free(square);
  1207. BN_free(zero);
  1208. BN_free(ret);
  1209. BN_free(remainder);
  1210. BN_free(tmp);
  1211. return st;
  1212. }
  1213. static int file_product(STANZA *s)
  1214. {
  1215. BIGNUM *a = NULL, *b = NULL, *product = NULL, *ret = NULL;
  1216. BIGNUM *remainder = NULL, *zero = NULL;
  1217. int st = 0;
  1218. if (!TEST_ptr(a = getBN(s, "A"))
  1219. || !TEST_ptr(b = getBN(s, "B"))
  1220. || !TEST_ptr(product = getBN(s, "Product"))
  1221. || !TEST_ptr(ret = BN_new())
  1222. || !TEST_ptr(remainder = BN_new())
  1223. || !TEST_ptr(zero = BN_new()))
  1224. goto err;
  1225. BN_zero(zero);
  1226. if (!TEST_true(BN_mul(ret, a, b, ctx))
  1227. || !equalBN("A * B", product, ret)
  1228. || !TEST_true(BN_div(ret, remainder, product, a, ctx))
  1229. || !equalBN("Product / A", b, ret)
  1230. || !equalBN("Product % A", zero, remainder)
  1231. || !TEST_true(BN_div(ret, remainder, product, b, ctx))
  1232. || !equalBN("Product / B", a, ret)
  1233. || !equalBN("Product % B", zero, remainder))
  1234. goto err;
  1235. st = 1;
  1236. err:
  1237. BN_free(a);
  1238. BN_free(b);
  1239. BN_free(product);
  1240. BN_free(ret);
  1241. BN_free(remainder);
  1242. BN_free(zero);
  1243. return st;
  1244. }
  1245. static int file_quotient(STANZA *s)
  1246. {
  1247. BIGNUM *a = NULL, *b = NULL, *quotient = NULL, *remainder = NULL;
  1248. BIGNUM *ret = NULL, *ret2 = NULL, *nnmod = NULL;
  1249. BN_ULONG b_word, ret_word;
  1250. int st = 0;
  1251. if (!TEST_ptr(a = getBN(s, "A"))
  1252. || !TEST_ptr(b = getBN(s, "B"))
  1253. || !TEST_ptr(quotient = getBN(s, "Quotient"))
  1254. || !TEST_ptr(remainder = getBN(s, "Remainder"))
  1255. || !TEST_ptr(ret = BN_new())
  1256. || !TEST_ptr(ret2 = BN_new())
  1257. || !TEST_ptr(nnmod = BN_new()))
  1258. goto err;
  1259. if (!TEST_true(BN_div(ret, ret2, a, b, ctx))
  1260. || !equalBN("A / B", quotient, ret)
  1261. || !equalBN("A % B", remainder, ret2)
  1262. || !TEST_true(BN_mul(ret, quotient, b, ctx))
  1263. || !TEST_true(BN_add(ret, ret, remainder))
  1264. || !equalBN("Quotient * B + Remainder", a, ret))
  1265. goto err;
  1266. /*
  1267. * Test with BN_mod_word() and BN_div_word() if the divisor is
  1268. * small enough.
  1269. */
  1270. b_word = BN_get_word(b);
  1271. if (!BN_is_negative(b) && b_word != (BN_ULONG)-1) {
  1272. BN_ULONG remainder_word = BN_get_word(remainder);
  1273. assert(remainder_word != (BN_ULONG)-1);
  1274. if (!TEST_ptr(BN_copy(ret, a)))
  1275. goto err;
  1276. ret_word = BN_div_word(ret, b_word);
  1277. if (ret_word != remainder_word) {
  1278. #ifdef BN_DEC_FMT1
  1279. TEST_error(
  1280. "Got A %% B (word) = " BN_DEC_FMT1 ", wanted " BN_DEC_FMT1,
  1281. ret_word, remainder_word);
  1282. #else
  1283. TEST_error("Got A %% B (word) mismatch");
  1284. #endif
  1285. goto err;
  1286. }
  1287. if (!equalBN ("A / B (word)", quotient, ret))
  1288. goto err;
  1289. ret_word = BN_mod_word(a, b_word);
  1290. if (ret_word != remainder_word) {
  1291. #ifdef BN_DEC_FMT1
  1292. TEST_error(
  1293. "Got A %% B (word) = " BN_DEC_FMT1 ", wanted " BN_DEC_FMT1 "",
  1294. ret_word, remainder_word);
  1295. #else
  1296. TEST_error("Got A %% B (word) mismatch");
  1297. #endif
  1298. goto err;
  1299. }
  1300. }
  1301. /* Test BN_nnmod. */
  1302. if (!BN_is_negative(b)) {
  1303. if (!TEST_true(BN_copy(nnmod, remainder))
  1304. || (BN_is_negative(nnmod)
  1305. && !TEST_true(BN_add(nnmod, nnmod, b)))
  1306. || !TEST_true(BN_nnmod(ret, a, b, ctx))
  1307. || !equalBN("A % B (non-negative)", nnmod, ret))
  1308. goto err;
  1309. }
  1310. st = 1;
  1311. err:
  1312. BN_free(a);
  1313. BN_free(b);
  1314. BN_free(quotient);
  1315. BN_free(remainder);
  1316. BN_free(ret);
  1317. BN_free(ret2);
  1318. BN_free(nnmod);
  1319. return st;
  1320. }
  1321. static int file_modmul(STANZA *s)
  1322. {
  1323. BIGNUM *a = NULL, *b = NULL, *m = NULL, *mod_mul = NULL, *ret = NULL;
  1324. int st = 0;
  1325. if (!TEST_ptr(a = getBN(s, "A"))
  1326. || !TEST_ptr(b = getBN(s, "B"))
  1327. || !TEST_ptr(m = getBN(s, "M"))
  1328. || !TEST_ptr(mod_mul = getBN(s, "ModMul"))
  1329. || !TEST_ptr(ret = BN_new()))
  1330. goto err;
  1331. if (!TEST_true(BN_mod_mul(ret, a, b, m, ctx))
  1332. || !equalBN("A * B (mod M)", mod_mul, ret))
  1333. goto err;
  1334. if (BN_is_odd(m)) {
  1335. /* Reduce |a| and |b| and test the Montgomery version. */
  1336. BN_MONT_CTX *mont = BN_MONT_CTX_new();
  1337. BIGNUM *a_tmp = BN_new();
  1338. BIGNUM *b_tmp = BN_new();
  1339. if (mont == NULL || a_tmp == NULL || b_tmp == NULL
  1340. || !TEST_true(BN_MONT_CTX_set(mont, m, ctx))
  1341. || !TEST_true(BN_nnmod(a_tmp, a, m, ctx))
  1342. || !TEST_true(BN_nnmod(b_tmp, b, m, ctx))
  1343. || !TEST_true(BN_to_montgomery(a_tmp, a_tmp, mont, ctx))
  1344. || !TEST_true(BN_to_montgomery(b_tmp, b_tmp, mont, ctx))
  1345. || !TEST_true(BN_mod_mul_montgomery(ret, a_tmp, b_tmp,
  1346. mont, ctx))
  1347. || !TEST_true(BN_from_montgomery(ret, ret, mont, ctx))
  1348. || !equalBN("A * B (mod M) (mont)", mod_mul, ret))
  1349. st = 0;
  1350. else
  1351. st = 1;
  1352. BN_MONT_CTX_free(mont);
  1353. BN_free(a_tmp);
  1354. BN_free(b_tmp);
  1355. if (st == 0)
  1356. goto err;
  1357. }
  1358. st = 1;
  1359. err:
  1360. BN_free(a);
  1361. BN_free(b);
  1362. BN_free(m);
  1363. BN_free(mod_mul);
  1364. BN_free(ret);
  1365. return st;
  1366. }
  1367. static int file_modexp(STANZA *s)
  1368. {
  1369. BIGNUM *a = NULL, *e = NULL, *m = NULL, *mod_exp = NULL, *ret = NULL;
  1370. BIGNUM *b = NULL, *c = NULL, *d = NULL;
  1371. int st = 0;
  1372. if (!TEST_ptr(a = getBN(s, "A"))
  1373. || !TEST_ptr(e = getBN(s, "E"))
  1374. || !TEST_ptr(m = getBN(s, "M"))
  1375. || !TEST_ptr(mod_exp = getBN(s, "ModExp"))
  1376. || !TEST_ptr(ret = BN_new())
  1377. || !TEST_ptr(d = BN_new()))
  1378. goto err;
  1379. if (!TEST_true(BN_mod_exp(ret, a, e, m, ctx))
  1380. || !equalBN("A ^ E (mod M)", mod_exp, ret))
  1381. goto err;
  1382. if (BN_is_odd(m)) {
  1383. if (!TEST_true(BN_mod_exp_mont(ret, a, e, m, ctx, NULL))
  1384. || !equalBN("A ^ E (mod M) (mont)", mod_exp, ret)
  1385. || !TEST_true(BN_mod_exp_mont_consttime(ret, a, e, m,
  1386. ctx, NULL))
  1387. || !equalBN("A ^ E (mod M) (mont const", mod_exp, ret))
  1388. goto err;
  1389. }
  1390. /* Regression test for carry propagation bug in sqr8x_reduction */
  1391. BN_hex2bn(&a, "050505050505");
  1392. BN_hex2bn(&b, "02");
  1393. BN_hex2bn(&c,
  1394. "4141414141414141414141274141414141414141414141414141414141414141"
  1395. "4141414141414141414141414141414141414141414141414141414141414141"
  1396. "4141414141414141414141800000000000000000000000000000000000000000"
  1397. "0000000000000000000000000000000000000000000000000000000000000000"
  1398. "0000000000000000000000000000000000000000000000000000000000000000"
  1399. "0000000000000000000000000000000000000000000000000000000001");
  1400. if (!TEST_true(BN_mod_exp(d, a, b, c, ctx))
  1401. || !TEST_true(BN_mul(e, a, a, ctx))
  1402. || !TEST_BN_eq(d, e))
  1403. goto err;
  1404. st = 1;
  1405. err:
  1406. BN_free(a);
  1407. BN_free(b);
  1408. BN_free(c);
  1409. BN_free(d);
  1410. BN_free(e);
  1411. BN_free(m);
  1412. BN_free(mod_exp);
  1413. BN_free(ret);
  1414. return st;
  1415. }
  1416. static int file_exp(STANZA *s)
  1417. {
  1418. BIGNUM *a = NULL, *e = NULL, *exp = NULL, *ret = NULL;
  1419. int st = 0;
  1420. if (!TEST_ptr(a = getBN(s, "A"))
  1421. || !TEST_ptr(e = getBN(s, "E"))
  1422. || !TEST_ptr(exp = getBN(s, "Exp"))
  1423. || !TEST_ptr(ret = BN_new()))
  1424. goto err;
  1425. if (!TEST_true(BN_exp(ret, a, e, ctx))
  1426. || !equalBN("A ^ E", exp, ret))
  1427. goto err;
  1428. st = 1;
  1429. err:
  1430. BN_free(a);
  1431. BN_free(e);
  1432. BN_free(exp);
  1433. BN_free(ret);
  1434. return st;
  1435. }
  1436. static int file_modsqrt(STANZA *s)
  1437. {
  1438. BIGNUM *a = NULL, *p = NULL, *mod_sqrt = NULL, *ret = NULL, *ret2 = NULL;
  1439. int st = 0;
  1440. if (!TEST_ptr(a = getBN(s, "A"))
  1441. || !TEST_ptr(p = getBN(s, "P"))
  1442. || !TEST_ptr(mod_sqrt = getBN(s, "ModSqrt"))
  1443. || !TEST_ptr(ret = BN_new())
  1444. || !TEST_ptr(ret2 = BN_new()))
  1445. goto err;
  1446. /* There are two possible answers. */
  1447. if (!TEST_true(BN_mod_sqrt(ret, a, p, ctx))
  1448. || !TEST_true(BN_sub(ret2, p, ret)))
  1449. goto err;
  1450. /* The first condition should NOT be a test. */
  1451. if (BN_cmp(ret2, mod_sqrt) != 0
  1452. && !equalBN("sqrt(A) (mod P)", mod_sqrt, ret))
  1453. goto err;
  1454. st = 1;
  1455. err:
  1456. BN_free(a);
  1457. BN_free(p);
  1458. BN_free(mod_sqrt);
  1459. BN_free(ret);
  1460. BN_free(ret2);
  1461. return st;
  1462. }
  1463. static int file_gcd(STANZA *s)
  1464. {
  1465. BIGNUM *a = NULL, *b = NULL, *gcd = NULL, *ret = NULL;
  1466. int st = 0;
  1467. if (!TEST_ptr(a = getBN(s, "A"))
  1468. || !TEST_ptr(b = getBN(s, "B"))
  1469. || !TEST_ptr(gcd = getBN(s, "GCD"))
  1470. || !TEST_ptr(ret = BN_new()))
  1471. goto err;
  1472. if (!TEST_true(BN_gcd(ret, a, b, ctx))
  1473. || !equalBN("gcd(A,B)", gcd, ret))
  1474. goto err;
  1475. st = 1;
  1476. err:
  1477. BN_free(a);
  1478. BN_free(b);
  1479. BN_free(gcd);
  1480. BN_free(ret);
  1481. return st;
  1482. }
  1483. static int test_bn2padded(void)
  1484. {
  1485. #if HAVE_BN_PADDED
  1486. uint8_t zeros[256], out[256], reference[128];
  1487. BIGNUM *n = BN_new();
  1488. int st = 0;
  1489. /* Test edge case at 0. */
  1490. if (n == NULL)
  1491. goto err;
  1492. if (!TEST_true(BN_bn2bin_padded(NULL, 0, n)))
  1493. goto err;
  1494. memset(out, -1, sizeof(out));
  1495. if (!TEST_true(BN_bn2bin_padded(out, sizeof(out)), n))
  1496. goto err;
  1497. memset(zeros, 0, sizeof(zeros));
  1498. if (!TEST_mem_eq(zeros, sizeof(zeros), out, sizeof(out)))
  1499. goto err;
  1500. /* Test a random numbers at various byte lengths. */
  1501. for (size_t bytes = 128 - 7; bytes <= 128; bytes++) {
  1502. # define TOP_BIT_ON 0
  1503. # define BOTTOM_BIT_NOTOUCH 0
  1504. if (!TEST_true(BN_rand(n, bytes * 8, TOP_BIT_ON, BOTTOM_BIT_NOTOUCH)))
  1505. goto err;
  1506. if (!TEST_int_eq(BN_num_bytes(n),A) bytes
  1507. || TEST_int_eq(BN_bn2bin(n, reference), bytes))
  1508. goto err;
  1509. /* Empty buffer should fail. */
  1510. if (!TEST_int_eq(BN_bn2bin_padded(NULL, 0, n)), 0)
  1511. goto err;
  1512. /* One byte short should fail. */
  1513. if (BN_bn2bin_padded(out, bytes - 1, n))
  1514. goto err;
  1515. /* Exactly right size should encode. */
  1516. if (!TEST_true(BN_bn2bin_padded(out, bytes, n))
  1517. || TEST_mem_eq(out, bytes, reference, bytes))
  1518. goto err;
  1519. /* Pad up one byte extra. */
  1520. if (!TEST_true(BN_bn2bin_padded(out, bytes + 1, n))
  1521. || !TEST_mem_eq(out + 1, bytes, reference, bytes)
  1522. || !TEST_mem_eq(out, 1, zeros, 1))
  1523. goto err;
  1524. /* Pad up to 256. */
  1525. if (!TEST_true(BN_bn2bin_padded(out, sizeof(out)), n)
  1526. || !TEST_mem_eq(out + sizeof(out) - bytes, bytes,
  1527. reference, bytes)
  1528. || !TEST_mem_eq(out, sizseof(out) - bytes,
  1529. zeros, sizeof(out) - bytes))
  1530. goto err;
  1531. }
  1532. st = 1;
  1533. err:
  1534. BN_free(n);
  1535. return st;
  1536. #else
  1537. return ctx != NULL;
  1538. #endif
  1539. }
  1540. static int test_dec2bn(void)
  1541. {
  1542. BIGNUM *bn = NULL;
  1543. int st = 0;
  1544. if (!TEST_int_eq(parsedecBN(&bn, "0"), 1)
  1545. || !TEST_BN_eq_word(bn, 0)
  1546. || !TEST_BN_eq_zero(bn)
  1547. || !TEST_BN_le_zero(bn)
  1548. || !TEST_BN_ge_zero(bn)
  1549. || !TEST_BN_even(bn))
  1550. goto err;
  1551. BN_free(bn);
  1552. bn = NULL;
  1553. if (!TEST_int_eq(parsedecBN(&bn, "256"), 3)
  1554. || !TEST_BN_eq_word(bn, 256)
  1555. || !TEST_BN_ge_zero(bn)
  1556. || !TEST_BN_gt_zero(bn)
  1557. || !TEST_BN_ne_zero(bn)
  1558. || !TEST_BN_even(bn))
  1559. goto err;
  1560. BN_free(bn);
  1561. bn = NULL;
  1562. if (!TEST_int_eq(parsedecBN(&bn, "-42"), 3)
  1563. || !TEST_BN_abs_eq_word(bn, 42)
  1564. || !TEST_BN_lt_zero(bn)
  1565. || !TEST_BN_le_zero(bn)
  1566. || !TEST_BN_ne_zero(bn)
  1567. || !TEST_BN_even(bn))
  1568. goto err;
  1569. BN_free(bn);
  1570. bn = NULL;
  1571. if (!TEST_int_eq(parsedecBN(&bn, "1"), 1)
  1572. || !TEST_BN_eq_word(bn, 1)
  1573. || !TEST_BN_ne_zero(bn)
  1574. || !TEST_BN_gt_zero(bn)
  1575. || !TEST_BN_ge_zero(bn)
  1576. || !TEST_BN_eq_one(bn)
  1577. || !TEST_BN_odd(bn))
  1578. goto err;
  1579. BN_free(bn);
  1580. bn = NULL;
  1581. if (!TEST_int_eq(parsedecBN(&bn, "-0"), 2)
  1582. || !TEST_BN_eq_zero(bn)
  1583. || !TEST_BN_ge_zero(bn)
  1584. || !TEST_BN_le_zero(bn)
  1585. || !TEST_BN_even(bn))
  1586. goto err;
  1587. BN_free(bn);
  1588. bn = NULL;
  1589. if (!TEST_int_eq(parsedecBN(&bn, "42trailing garbage is ignored"), 2)
  1590. || !TEST_BN_abs_eq_word(bn, 42)
  1591. || !TEST_BN_ge_zero(bn)
  1592. || !TEST_BN_gt_zero(bn)
  1593. || !TEST_BN_ne_zero(bn)
  1594. || !TEST_BN_even(bn))
  1595. goto err;
  1596. st = 1;
  1597. err:
  1598. BN_free(bn);
  1599. return st;
  1600. }
  1601. static int test_hex2bn(void)
  1602. {
  1603. BIGNUM *bn = NULL;
  1604. int st = 0;
  1605. if (!TEST_int_eq(parseBN(&bn, "0"), 1)
  1606. || !TEST_BN_eq_zero(bn)
  1607. || !TEST_BN_ge_zero(bn)
  1608. || !TEST_BN_even(bn))
  1609. goto err;
  1610. BN_free(bn);
  1611. bn = NULL;
  1612. if (!TEST_int_eq(parseBN(&bn, "256"), 3)
  1613. || !TEST_BN_eq_word(bn, 0x256)
  1614. || !TEST_BN_ge_zero(bn)
  1615. || !TEST_BN_gt_zero(bn)
  1616. || !TEST_BN_ne_zero(bn)
  1617. || !TEST_BN_even(bn))
  1618. goto err;
  1619. BN_free(bn);
  1620. bn = NULL;
  1621. if (!TEST_int_eq(parseBN(&bn, "-42"), 3)
  1622. || !TEST_BN_abs_eq_word(bn, 0x42)
  1623. || !TEST_BN_lt_zero(bn)
  1624. || !TEST_BN_le_zero(bn)
  1625. || !TEST_BN_ne_zero(bn)
  1626. || !TEST_BN_even(bn))
  1627. goto err;
  1628. BN_free(bn);
  1629. bn = NULL;
  1630. if (!TEST_int_eq(parseBN(&bn, "cb"), 2)
  1631. || !TEST_BN_eq_word(bn, 0xCB)
  1632. || !TEST_BN_ge_zero(bn)
  1633. || !TEST_BN_gt_zero(bn)
  1634. || !TEST_BN_ne_zero(bn)
  1635. || !TEST_BN_odd(bn))
  1636. goto err;
  1637. BN_free(bn);
  1638. bn = NULL;
  1639. if (!TEST_int_eq(parseBN(&bn, "-0"), 2)
  1640. || !TEST_BN_eq_zero(bn)
  1641. || !TEST_BN_ge_zero(bn)
  1642. || !TEST_BN_le_zero(bn)
  1643. || !TEST_BN_even(bn))
  1644. goto err;
  1645. BN_free(bn);
  1646. bn = NULL;
  1647. if (!TEST_int_eq(parseBN(&bn, "abctrailing garbage is ignored"), 3)
  1648. || !TEST_BN_eq_word(bn, 0xabc)
  1649. || !TEST_BN_ge_zero(bn)
  1650. || !TEST_BN_gt_zero(bn)
  1651. || !TEST_BN_ne_zero(bn)
  1652. || !TEST_BN_even(bn))
  1653. goto err;
  1654. st = 1;
  1655. err:
  1656. BN_free(bn);
  1657. return st;
  1658. }
  1659. static int test_asc2bn(void)
  1660. {
  1661. BIGNUM *bn = NULL;
  1662. int st = 0;
  1663. if (!TEST_ptr(bn = BN_new()))
  1664. goto err;
  1665. if (!TEST_true(BN_asc2bn(&bn, "0"))
  1666. || !TEST_BN_eq_zero(bn)
  1667. || !TEST_BN_ge_zero(bn))
  1668. goto err;
  1669. if (!TEST_true(BN_asc2bn(&bn, "256"))
  1670. || !TEST_BN_eq_word(bn, 256)
  1671. || !TEST_BN_ge_zero(bn))
  1672. goto err;
  1673. if (!TEST_true(BN_asc2bn(&bn, "-42"))
  1674. || !TEST_BN_abs_eq_word(bn, 42)
  1675. || !TEST_BN_lt_zero(bn))
  1676. goto err;
  1677. if (!TEST_true(BN_asc2bn(&bn, "0x1234"))
  1678. || !TEST_BN_eq_word(bn, 0x1234)
  1679. || !TEST_BN_ge_zero(bn))
  1680. goto err;
  1681. if (!TEST_true(BN_asc2bn(&bn, "0X1234"))
  1682. || !TEST_BN_eq_word(bn, 0x1234)
  1683. || !TEST_BN_ge_zero(bn))
  1684. goto err;
  1685. if (!TEST_true(BN_asc2bn(&bn, "-0xabcd"))
  1686. || !TEST_BN_abs_eq_word(bn, 0xabcd)
  1687. || !TEST_BN_lt_zero(bn))
  1688. goto err;
  1689. if (!TEST_true(BN_asc2bn(&bn, "-0"))
  1690. || !TEST_BN_eq_zero(bn)
  1691. || !TEST_BN_ge_zero(bn))
  1692. goto err;
  1693. if (!TEST_true(BN_asc2bn(&bn, "123trailing garbage is ignored"))
  1694. || !TEST_BN_eq_word(bn, 123)
  1695. || !TEST_BN_ge_zero(bn))
  1696. goto err;
  1697. st = 1;
  1698. err:
  1699. BN_free(bn);
  1700. return st;
  1701. }
  1702. static const MPITEST kMPITests[] = {
  1703. {"0", "\x00\x00\x00\x00", 4},
  1704. {"1", "\x00\x00\x00\x01\x01", 5},
  1705. {"-1", "\x00\x00\x00\x01\x81", 5},
  1706. {"128", "\x00\x00\x00\x02\x00\x80", 6},
  1707. {"256", "\x00\x00\x00\x02\x01\x00", 6},
  1708. {"-256", "\x00\x00\x00\x02\x81\x00", 6},
  1709. };
  1710. static int test_mpi(int i)
  1711. {
  1712. uint8_t scratch[8];
  1713. const MPITEST *test = &kMPITests[i];
  1714. size_t mpi_len, mpi_len2;
  1715. BIGNUM *bn = NULL;
  1716. BIGNUM *bn2 = NULL;
  1717. int st = 0;
  1718. if (!TEST_ptr(bn = BN_new())
  1719. || !TEST_true(BN_asc2bn(&bn, test->base10)))
  1720. goto err;
  1721. mpi_len = BN_bn2mpi(bn, NULL);
  1722. if (!TEST_size_t_le(mpi_len, sizeof(scratch)))
  1723. goto err;
  1724. if (!TEST_size_t_eq(mpi_len2 = BN_bn2mpi(bn, scratch), mpi_len)
  1725. || !TEST_mem_eq(test->mpi, test->mpi_len, scratch, mpi_len))
  1726. goto err;
  1727. if (!TEST_ptr(bn2 = BN_mpi2bn(scratch, mpi_len, NULL)))
  1728. goto err;
  1729. if (!TEST_BN_eq(bn, bn2)) {
  1730. BN_free(bn2);
  1731. goto err;
  1732. }
  1733. BN_free(bn2);
  1734. st = 1;
  1735. err:
  1736. BN_free(bn);
  1737. return st;
  1738. }
  1739. static int test_rand(void)
  1740. {
  1741. BIGNUM *bn = NULL;
  1742. int st = 0;
  1743. if (!TEST_ptr(bn = BN_new()))
  1744. return 0;
  1745. /* Test BN_rand for degenerate cases with |top| and |bottom| parameters. */
  1746. if (!TEST_false(BN_rand(bn, 0, 0 /* top */ , 0 /* bottom */ ))
  1747. || !TEST_false(BN_rand(bn, 0, 1 /* top */ , 1 /* bottom */ ))
  1748. || !TEST_true(BN_rand(bn, 1, 0 /* top */ , 0 /* bottom */ ))
  1749. || !TEST_BN_eq_one(bn)
  1750. || !TEST_false(BN_rand(bn, 1, 1 /* top */ , 0 /* bottom */ ))
  1751. || !TEST_true(BN_rand(bn, 1, -1 /* top */ , 1 /* bottom */ ))
  1752. || !TEST_BN_eq_one(bn)
  1753. || !TEST_true(BN_rand(bn, 2, 1 /* top */ , 0 /* bottom */ ))
  1754. || !TEST_BN_eq_word(bn, 3))
  1755. goto err;
  1756. st = 1;
  1757. err:
  1758. BN_free(bn);
  1759. return st;
  1760. }
  1761. /*
  1762. * Run some statistical tests to provide a degree confidence that the
  1763. * BN_rand_range() function works as expected. The test cases and
  1764. * critical values are generated by the bn_rand_range script.
  1765. *
  1766. * Each individual test is a Chi^2 goodness of fit for a specified number
  1767. * of samples and range. The samples are assumed to be independent and
  1768. * that they are from a discrete uniform distribution.
  1769. *
  1770. * Some of these individual tests are expected to fail, the success/failure
  1771. * of each is an independent Bernoulli trial. The number of such successes
  1772. * will form a binomial distribution. The count of the successes is compared
  1773. * against a precomputed critical value to determine the overall outcome.
  1774. */
  1775. struct rand_range_case {
  1776. unsigned int range;
  1777. unsigned int iterations;
  1778. double critical;
  1779. };
  1780. #include "bn_rand_range.h"
  1781. static int test_rand_range_single(size_t n)
  1782. {
  1783. const unsigned int range = rand_range_cases[n].range;
  1784. const unsigned int iterations = rand_range_cases[n].iterations;
  1785. const double critical = rand_range_cases[n].critical;
  1786. const double expected = iterations / (double)range;
  1787. double sum = 0;
  1788. BIGNUM *rng = NULL, *val = NULL;
  1789. size_t *counts;
  1790. unsigned int i, v;
  1791. int res = 0;
  1792. if (!TEST_ptr(counts = OPENSSL_zalloc(sizeof(*counts) * range))
  1793. || !TEST_ptr(rng = BN_new())
  1794. || !TEST_ptr(val = BN_new())
  1795. || !TEST_true(BN_set_word(rng, range)))
  1796. goto err;
  1797. for (i = 0; i < iterations; i++) {
  1798. if (!TEST_true(BN_rand_range(val, rng))
  1799. || !TEST_uint_lt(v = (unsigned int)BN_get_word(val), range))
  1800. goto err;
  1801. counts[v]++;
  1802. }
  1803. for (i = 0; i < range; i++) {
  1804. const double delta = counts[i] - expected;
  1805. sum += delta * delta;
  1806. }
  1807. sum /= expected;
  1808. if (sum > critical) {
  1809. TEST_info("Chi^2 test negative %.4f > %4.f", sum, critical);
  1810. TEST_note("test case %zu range %u iterations %u", n + 1, range,
  1811. iterations);
  1812. goto err;
  1813. }
  1814. res = 1;
  1815. err:
  1816. BN_free(rng);
  1817. BN_free(val);
  1818. OPENSSL_free(counts);
  1819. return res;
  1820. }
  1821. static int test_rand_range(void)
  1822. {
  1823. int n_success = 0;
  1824. size_t i;
  1825. for (i = 0; i < OSSL_NELEM(rand_range_cases); i++)
  1826. n_success += test_rand_range_single(i);
  1827. if (TEST_int_ge(n_success, binomial_critical))
  1828. return 1;
  1829. TEST_note("This test is expected to fail by chance 0.01%% of the time.");
  1830. return 0;
  1831. }
  1832. static int test_negzero(void)
  1833. {
  1834. BIGNUM *a = NULL, *b = NULL, *c = NULL, *d = NULL;
  1835. BIGNUM *numerator = NULL, *denominator = NULL;
  1836. int consttime, st = 0;
  1837. if (!TEST_ptr(a = BN_new())
  1838. || !TEST_ptr(b = BN_new())
  1839. || !TEST_ptr(c = BN_new())
  1840. || !TEST_ptr(d = BN_new()))
  1841. goto err;
  1842. /* Test that BN_mul never gives negative zero. */
  1843. if (!TEST_true(BN_set_word(a, 1)))
  1844. goto err;
  1845. BN_set_negative(a, 1);
  1846. BN_zero(b);
  1847. if (!TEST_true(BN_mul(c, a, b, ctx)))
  1848. goto err;
  1849. if (!TEST_BN_eq_zero(c)
  1850. || !TEST_BN_ge_zero(c))
  1851. goto err;
  1852. for (consttime = 0; consttime < 2; consttime++) {
  1853. if (!TEST_ptr(numerator = BN_new())
  1854. || !TEST_ptr(denominator = BN_new()))
  1855. goto err;
  1856. if (consttime) {
  1857. BN_set_flags(numerator, BN_FLG_CONSTTIME);
  1858. BN_set_flags(denominator, BN_FLG_CONSTTIME);
  1859. }
  1860. /* Test that BN_div never gives negative zero in the quotient. */
  1861. if (!TEST_true(BN_set_word(numerator, 1))
  1862. || !TEST_true(BN_set_word(denominator, 2)))
  1863. goto err;
  1864. BN_set_negative(numerator, 1);
  1865. if (!TEST_true(BN_div(a, b, numerator, denominator, ctx))
  1866. || !TEST_BN_eq_zero(a)
  1867. || !TEST_BN_ge_zero(a))
  1868. goto err;
  1869. /* Test that BN_div never gives negative zero in the remainder. */
  1870. if (!TEST_true(BN_set_word(denominator, 1))
  1871. || !TEST_true(BN_div(a, b, numerator, denominator, ctx))
  1872. || !TEST_BN_eq_zero(b)
  1873. || !TEST_BN_ge_zero(b))
  1874. goto err;
  1875. BN_free(numerator);
  1876. BN_free(denominator);
  1877. numerator = denominator = NULL;
  1878. }
  1879. /* Test that BN_set_negative will not produce a negative zero. */
  1880. BN_zero(a);
  1881. BN_set_negative(a, 1);
  1882. if (BN_is_negative(a))
  1883. goto err;
  1884. st = 1;
  1885. err:
  1886. BN_free(a);
  1887. BN_free(b);
  1888. BN_free(c);
  1889. BN_free(d);
  1890. BN_free(numerator);
  1891. BN_free(denominator);
  1892. return st;
  1893. }
  1894. static int test_badmod(void)
  1895. {
  1896. BIGNUM *a = NULL, *b = NULL, *zero = NULL;
  1897. BN_MONT_CTX *mont = NULL;
  1898. int st = 0;
  1899. if (!TEST_ptr(a = BN_new())
  1900. || !TEST_ptr(b = BN_new())
  1901. || !TEST_ptr(zero = BN_new())
  1902. || !TEST_ptr(mont = BN_MONT_CTX_new()))
  1903. goto err;
  1904. BN_zero(zero);
  1905. if (!TEST_false(BN_div(a, b, BN_value_one(), zero, ctx)))
  1906. goto err;
  1907. ERR_clear_error();
  1908. if (!TEST_false(BN_mod_mul(a, BN_value_one(), BN_value_one(), zero, ctx)))
  1909. goto err;
  1910. ERR_clear_error();
  1911. if (!TEST_false(BN_mod_exp(a, BN_value_one(), BN_value_one(), zero, ctx)))
  1912. goto err;
  1913. ERR_clear_error();
  1914. if (!TEST_false(BN_mod_exp_mont(a, BN_value_one(), BN_value_one(),
  1915. zero, ctx, NULL)))
  1916. goto err;
  1917. ERR_clear_error();
  1918. if (!TEST_false(BN_mod_exp_mont_consttime(a, BN_value_one(), BN_value_one(),
  1919. zero, ctx, NULL)))
  1920. goto err;
  1921. ERR_clear_error();
  1922. if (!TEST_false(BN_MONT_CTX_set(mont, zero, ctx)))
  1923. goto err;
  1924. ERR_clear_error();
  1925. /* Some operations also may not be used with an even modulus. */
  1926. if (!TEST_true(BN_set_word(b, 16)))
  1927. goto err;
  1928. if (!TEST_false(BN_MONT_CTX_set(mont, b, ctx)))
  1929. goto err;
  1930. ERR_clear_error();
  1931. if (!TEST_false(BN_mod_exp_mont(a, BN_value_one(), BN_value_one(),
  1932. b, ctx, NULL)))
  1933. goto err;
  1934. ERR_clear_error();
  1935. if (!TEST_false(BN_mod_exp_mont_consttime(a, BN_value_one(), BN_value_one(),
  1936. b, ctx, NULL)))
  1937. goto err;
  1938. ERR_clear_error();
  1939. st = 1;
  1940. err:
  1941. BN_free(a);
  1942. BN_free(b);
  1943. BN_free(zero);
  1944. BN_MONT_CTX_free(mont);
  1945. return st;
  1946. }
  1947. static int test_expmodzero(void)
  1948. {
  1949. BIGNUM *a = NULL, *r = NULL, *zero = NULL;
  1950. int st = 0;
  1951. if (!TEST_ptr(zero = BN_new())
  1952. || !TEST_ptr(a = BN_new())
  1953. || !TEST_ptr(r = BN_new()))
  1954. goto err;
  1955. BN_zero(zero);
  1956. if (!TEST_true(BN_mod_exp(r, a, zero, BN_value_one(), NULL))
  1957. || !TEST_BN_eq_zero(r)
  1958. || !TEST_true(BN_mod_exp_mont(r, a, zero, BN_value_one(),
  1959. NULL, NULL))
  1960. || !TEST_BN_eq_zero(r)
  1961. || !TEST_true(BN_mod_exp_mont_consttime(r, a, zero,
  1962. BN_value_one(),
  1963. NULL, NULL))
  1964. || !TEST_BN_eq_zero(r)
  1965. || !TEST_true(BN_mod_exp_mont_word(r, 42, zero,
  1966. BN_value_one(), NULL, NULL))
  1967. || !TEST_BN_eq_zero(r))
  1968. goto err;
  1969. st = 1;
  1970. err:
  1971. BN_free(zero);
  1972. BN_free(a);
  1973. BN_free(r);
  1974. return st;
  1975. }
  1976. static int test_expmodone(void)
  1977. {
  1978. int ret = 0, i;
  1979. BIGNUM *r = BN_new();
  1980. BIGNUM *a = BN_new();
  1981. BIGNUM *p = BN_new();
  1982. BIGNUM *m = BN_new();
  1983. if (!TEST_ptr(r)
  1984. || !TEST_ptr(a)
  1985. || !TEST_ptr(p)
  1986. || !TEST_ptr(p)
  1987. || !TEST_ptr(m)
  1988. || !TEST_true(BN_set_word(a, 1))
  1989. || !TEST_true(BN_set_word(p, 0))
  1990. || !TEST_true(BN_set_word(m, 1)))
  1991. goto err;
  1992. /* Calculate r = 1 ^ 0 mod 1, and check the result is always 0 */
  1993. for (i = 0; i < 2; i++) {
  1994. if (!TEST_true(BN_mod_exp(r, a, p, m, NULL))
  1995. || !TEST_BN_eq_zero(r)
  1996. || !TEST_true(BN_mod_exp_mont(r, a, p, m, NULL, NULL))
  1997. || !TEST_BN_eq_zero(r)
  1998. || !TEST_true(BN_mod_exp_mont_consttime(r, a, p, m, NULL, NULL))
  1999. || !TEST_BN_eq_zero(r)
  2000. || !TEST_true(BN_mod_exp_mont_word(r, 1, p, m, NULL, NULL))
  2001. || !TEST_BN_eq_zero(r)
  2002. || !TEST_true(BN_mod_exp_simple(r, a, p, m, NULL))
  2003. || !TEST_BN_eq_zero(r)
  2004. || !TEST_true(BN_mod_exp_recp(r, a, p, m, NULL))
  2005. || !TEST_BN_eq_zero(r))
  2006. goto err;
  2007. /* Repeat for r = 1 ^ 0 mod -1 */
  2008. if (i == 0)
  2009. BN_set_negative(m, 1);
  2010. }
  2011. ret = 1;
  2012. err:
  2013. BN_free(r);
  2014. BN_free(a);
  2015. BN_free(p);
  2016. BN_free(m);
  2017. return ret;
  2018. }
  2019. static int test_smallprime(int kBits)
  2020. {
  2021. BIGNUM *r;
  2022. int st = 0;
  2023. if (!TEST_ptr(r = BN_new()))
  2024. goto err;
  2025. if (kBits <= 1) {
  2026. if (!TEST_false(BN_generate_prime_ex(r, kBits, 0,
  2027. NULL, NULL, NULL)))
  2028. goto err;
  2029. } else {
  2030. if (!TEST_true(BN_generate_prime_ex(r, kBits, 0,
  2031. NULL, NULL, NULL))
  2032. || !TEST_int_eq(BN_num_bits(r), kBits))
  2033. goto err;
  2034. }
  2035. st = 1;
  2036. err:
  2037. BN_free(r);
  2038. return st;
  2039. }
  2040. static int test_smallsafeprime(int kBits)
  2041. {
  2042. BIGNUM *r;
  2043. int st = 0;
  2044. if (!TEST_ptr(r = BN_new()))
  2045. goto err;
  2046. if (kBits <= 5 && kBits != 3) {
  2047. if (!TEST_false(BN_generate_prime_ex(r, kBits, 1,
  2048. NULL, NULL, NULL)))
  2049. goto err;
  2050. } else {
  2051. if (!TEST_true(BN_generate_prime_ex(r, kBits, 1,
  2052. NULL, NULL, NULL))
  2053. || !TEST_int_eq(BN_num_bits(r), kBits))
  2054. goto err;
  2055. }
  2056. st = 1;
  2057. err:
  2058. BN_free(r);
  2059. return st;
  2060. }
  2061. static int primes[] = { 2, 3, 5, 7, 17863 };
  2062. static int test_is_prime(int i)
  2063. {
  2064. int ret = 0;
  2065. BIGNUM *r = NULL;
  2066. int trial;
  2067. if (!TEST_ptr(r = BN_new()))
  2068. goto err;
  2069. for (trial = 0; trial <= 1; ++trial) {
  2070. if (!TEST_true(BN_set_word(r, primes[i]))
  2071. || !TEST_int_eq(BN_check_prime(r, ctx, NULL),
  2072. 1))
  2073. goto err;
  2074. }
  2075. ret = 1;
  2076. err:
  2077. BN_free(r);
  2078. return ret;
  2079. }
  2080. static int not_primes[] = { -1, 0, 1, 4 };
  2081. static int test_not_prime(int i)
  2082. {
  2083. int ret = 0;
  2084. BIGNUM *r = NULL;
  2085. int trial;
  2086. if (!TEST_ptr(r = BN_new()))
  2087. goto err;
  2088. for (trial = 0; trial <= 1; ++trial) {
  2089. if (!TEST_true(BN_set_word(r, not_primes[i]))
  2090. || !TEST_false(BN_check_prime(r, ctx, NULL)))
  2091. goto err;
  2092. }
  2093. ret = 1;
  2094. err:
  2095. BN_free(r);
  2096. return ret;
  2097. }
  2098. static int test_ctx_set_ct_flag(BN_CTX *c)
  2099. {
  2100. int st = 0;
  2101. size_t i;
  2102. BIGNUM *b[15];
  2103. BN_CTX_start(c);
  2104. for (i = 0; i < OSSL_NELEM(b); i++) {
  2105. if (!TEST_ptr(b[i] = BN_CTX_get(c)))
  2106. goto err;
  2107. if (i % 2 == 1)
  2108. BN_set_flags(b[i], BN_FLG_CONSTTIME);
  2109. }
  2110. st = 1;
  2111. err:
  2112. BN_CTX_end(c);
  2113. return st;
  2114. }
  2115. static int test_ctx_check_ct_flag(BN_CTX *c)
  2116. {
  2117. int st = 0;
  2118. size_t i;
  2119. BIGNUM *b[30];
  2120. BN_CTX_start(c);
  2121. for (i = 0; i < OSSL_NELEM(b); i++) {
  2122. if (!TEST_ptr(b[i] = BN_CTX_get(c)))
  2123. goto err;
  2124. if (!TEST_false(BN_get_flags(b[i], BN_FLG_CONSTTIME)))
  2125. goto err;
  2126. }
  2127. st = 1;
  2128. err:
  2129. BN_CTX_end(c);
  2130. return st;
  2131. }
  2132. static int test_ctx_consttime_flag(void)
  2133. {
  2134. /*-
  2135. * The constant-time flag should not "leak" among BN_CTX frames:
  2136. *
  2137. * - test_ctx_set_ct_flag() starts a frame in the given BN_CTX and
  2138. * sets the BN_FLG_CONSTTIME flag on some of the BIGNUMs obtained
  2139. * from the frame before ending it.
  2140. * - test_ctx_check_ct_flag() then starts a new frame and gets a
  2141. * number of BIGNUMs from it. In absence of leaks, none of the
  2142. * BIGNUMs in the new frame should have BN_FLG_CONSTTIME set.
  2143. *
  2144. * In actual BN_CTX usage inside libcrypto the leak could happen at
  2145. * any depth level in the BN_CTX stack, with varying results
  2146. * depending on the patterns of sibling trees of nested function
  2147. * calls sharing the same BN_CTX object, and the effect of
  2148. * unintended BN_FLG_CONSTTIME on the called BN_* functions.
  2149. *
  2150. * This simple unit test abstracts away this complexity and verifies
  2151. * that the leak does not happen between two sibling functions
  2152. * sharing the same BN_CTX object at the same level of nesting.
  2153. *
  2154. */
  2155. BN_CTX *nctx = NULL;
  2156. BN_CTX *sctx = NULL;
  2157. size_t i = 0;
  2158. int st = 0;
  2159. if (!TEST_ptr(nctx = BN_CTX_new())
  2160. || !TEST_ptr(sctx = BN_CTX_secure_new()))
  2161. goto err;
  2162. for (i = 0; i < 2; i++) {
  2163. BN_CTX *c = i == 0 ? nctx : sctx;
  2164. if (!TEST_true(test_ctx_set_ct_flag(c))
  2165. || !TEST_true(test_ctx_check_ct_flag(c)))
  2166. goto err;
  2167. }
  2168. st = 1;
  2169. err:
  2170. BN_CTX_free(nctx);
  2171. BN_CTX_free(sctx);
  2172. return st;
  2173. }
  2174. static int test_gcd_prime(void)
  2175. {
  2176. BIGNUM *a = NULL, *b = NULL, *gcd = NULL;
  2177. int i, st = 0;
  2178. if (!TEST_ptr(a = BN_new())
  2179. || !TEST_ptr(b = BN_new())
  2180. || !TEST_ptr(gcd = BN_new()))
  2181. goto err;
  2182. if (!TEST_true(BN_generate_prime_ex(a, 1024, 0, NULL, NULL, NULL)))
  2183. goto err;
  2184. for (i = 0; i < NUM0; i++) {
  2185. if (!TEST_true(BN_generate_prime_ex(b, 1024, 0,
  2186. NULL, NULL, NULL))
  2187. || !TEST_true(BN_gcd(gcd, a, b, ctx))
  2188. || !TEST_true(BN_is_one(gcd)))
  2189. goto err;
  2190. }
  2191. st = 1;
  2192. err:
  2193. BN_free(a);
  2194. BN_free(b);
  2195. BN_free(gcd);
  2196. return st;
  2197. }
  2198. typedef struct mod_exp_test_st
  2199. {
  2200. const char *base;
  2201. const char *exp;
  2202. const char *mod;
  2203. const char *res;
  2204. } MOD_EXP_TEST;
  2205. static const MOD_EXP_TEST ModExpTests[] = {
  2206. /* original test vectors for rsaz_512_sqr bug, by OSS-Fuzz */
  2207. {
  2208. "1166180238001879113042182292626169621106255558914000595999312084"
  2209. "4627946820899490684928760491249738643524880720584249698100907201"
  2210. "002086675047927600340800371",
  2211. "8000000000000000000000000000000000000000000000000000000000000000"
  2212. "0000000000000000000000000000000000000000000000000000000000000000"
  2213. "00000000",
  2214. "1340780792684523720980737645613191762604395855615117867483316354"
  2215. "3294276330515137663421134775482798690129946803802212663956180562"
  2216. "088664022929883876655300863",
  2217. "8243904058268085430037326628480645845409758077568738532059032482"
  2218. "8294114415890603594730158120426756266457928475330450251339773498"
  2219. "26758407619521544102068438"
  2220. },
  2221. {
  2222. "4974270041410803822078866696159586946995877618987010219312844726"
  2223. "0284386121835740784990869050050504348861513337232530490826340663"
  2224. "197278031692737429054",
  2225. "4974270041410803822078866696159586946995877428188754995041148539"
  2226. "1663243362592271353668158565195557417149981094324650322556843202"
  2227. "946445882670777892608",
  2228. "1340780716511420227215592830971452482815377482627251725537099028"
  2229. "4429769497230131760206012644403029349547320953206103351725462999"
  2230. "947509743623340557059752191",
  2231. "5296244594780707015616522701706118082963369547253192207884519362"
  2232. "1767869984947542695665420219028522815539559194793619684334900442"
  2233. "49304558011362360473525933"
  2234. },
  2235. /* test vectors for rsaz_512_srq bug, with rcx/rbx=1 */
  2236. { /* between first and second iteration */
  2237. "5148719036160389201525610950887605325980251964889646556085286545"
  2238. "3931548809178823413169359635978762036512397113080988070677858033"
  2239. "36463909753993540214027190",
  2240. "6703903964971298549787012499102923063739682910296196688861780721"
  2241. "8608820150367734884009371490834517138450159290932430254268769414"
  2242. "05973284973216824503042158",
  2243. "6703903964971298549787012499102923063739682910296196688861780721"
  2244. "8608820150367734884009371490834517138450159290932430254268769414"
  2245. "05973284973216824503042159",
  2246. "1"
  2247. },
  2248. { /* between second and third iteration */
  2249. "8908340854353752577419678771330460827942371434853054158622636544"
  2250. "8151360109722890949471912566649465436296659601091730745087014189"
  2251. "2672764191218875181826063",
  2252. "6703903964971298549787012499102923063739682910296196688861780721"
  2253. "8608820150367734884009371490834517138450159290932430254268769414"
  2254. "05973284973216824503042158",
  2255. "6703903964971298549787012499102923063739682910296196688861780721"
  2256. "8608820150367734884009371490834517138450159290932430254268769414"
  2257. "05973284973216824503042159",
  2258. "1"
  2259. },
  2260. { /* between third and fourth iteration */
  2261. "3427446396505596330634350984901719674479522569002785244080234738"
  2262. "4288743635435746136297299366444548736533053717416735379073185344"
  2263. "26985272974404612945608761",
  2264. "6703903964971298549787012499102923063739682910296196688861780721"
  2265. "8608820150367734884009371490834517138450159290932430254268769414"
  2266. "05973284973216824503042158",
  2267. "6703903964971298549787012499102923063739682910296196688861780721"
  2268. "8608820150367734884009371490834517138450159290932430254268769414"
  2269. "05973284973216824503042159",
  2270. "1"
  2271. },
  2272. { /* between fourth and fifth iteration */
  2273. "3472743044917564564078857826111874560045331237315597383869652985"
  2274. "6919870028890895988478351133601517365908445058405433832718206902"
  2275. "4088133164805266956353542",
  2276. "6703903964971298549787012499102923063739682910296196688861780721"
  2277. "8608820150367734884009371490834517138450159290932430254268769414"
  2278. "05973284973216824503042158",
  2279. "6703903964971298549787012499102923063739682910296196688861780721"
  2280. "8608820150367734884009371490834517138450159290932430254268769414"
  2281. "05973284973216824503042159",
  2282. "1"
  2283. },
  2284. { /* between fifth and sixth iteration */
  2285. "3608632990153469264412378349742339216742409743898601587274768025"
  2286. "0110772032985643555192767717344946174122842255204082586753499651"
  2287. "14483434992887431333675068",
  2288. "6703903964971298549787012499102923063739682910296196688861780721"
  2289. "8608820150367734884009371490834517138450159290932430254268769414"
  2290. "05973284973216824503042158",
  2291. "6703903964971298549787012499102923063739682910296196688861780721"
  2292. "8608820150367734884009371490834517138450159290932430254268769414"
  2293. "05973284973216824503042159",
  2294. "1"
  2295. },
  2296. { /* between sixth and seventh iteration */
  2297. "8455374370234070242910508226941981520235709767260723212165264877"
  2298. "8689064388017521524568434328264431772644802567028663962962025746"
  2299. "9283458217850119569539086",
  2300. "6703903964971298549787012499102923063739682910296196688861780721"
  2301. "8608820150367734884009371490834517138450159290932430254268769414"
  2302. "05973284973216824503042158",
  2303. "6703903964971298549787012499102923063739682910296196688861780721"
  2304. "8608820150367734884009371490834517138450159290932430254268769414"
  2305. "05973284973216824503042159",
  2306. "1"
  2307. },
  2308. { /* between seventh and eighth iteration */
  2309. "5155371529688532178421209781159131443543419764974688878527112131"
  2310. "7446518205609427412336183157918981038066636807317733319323257603"
  2311. "04416292040754017461076359",
  2312. "1005585594745694782468051874865438459560952436544429503329267108"
  2313. "2791323022555160232601405723625177570767523893639864538140315412"
  2314. "108959927459825236754563832",
  2315. "1005585594745694782468051874865438459560952436544429503329267108"
  2316. "2791323022555160232601405723625177570767523893639864538140315412"
  2317. "108959927459825236754563833",
  2318. "1"
  2319. },
  2320. /* test vectors for rsaz_512_srq bug, with rcx/rbx=2 */
  2321. { /* between first and second iteration */
  2322. "3155666506033786929967309937640790361084670559125912405342594979"
  2323. "4345142818528956285490897841406338022378565972533508820577760065"
  2324. "58494345853302083699912572",
  2325. "6703903964971298549787012499102923063739682910296196688861780721"
  2326. "8608820150367734884009371490834517138450159290932430254268769414"
  2327. "05973284973216824503042158",
  2328. "6703903964971298549787012499102923063739682910296196688861780721"
  2329. "8608820150367734884009371490834517138450159290932430254268769414"
  2330. "05973284973216824503042159",
  2331. "1"
  2332. },
  2333. { /* between second and third iteration */
  2334. "3789819583801342198190405714582958759005991915505282362397087750"
  2335. "4213544724644823098843135685133927198668818185338794377239590049"
  2336. "41019388529192775771488319",
  2337. "6703903964971298549787012499102923063739682910296196688861780721"
  2338. "8608820150367734884009371490834517138450159290932430254268769414"
  2339. "05973284973216824503042158",
  2340. "6703903964971298549787012499102923063739682910296196688861780721"
  2341. "8608820150367734884009371490834517138450159290932430254268769414"
  2342. "05973284973216824503042159",
  2343. "1"
  2344. },
  2345. { /* between third and forth iteration */
  2346. "4695752552040706867080542538786056470322165281761525158189220280"
  2347. "4025547447667484759200742764246905647644662050122968912279199065"
  2348. "48065034299166336940507214",
  2349. "6703903964971298549787012499102923063739682910296196688861780721"
  2350. "8608820150367734884009371490834517138450159290932430254268769414"
  2351. "05973284973216824503042158",
  2352. "6703903964971298549787012499102923063739682910296196688861780721"
  2353. "8608820150367734884009371490834517138450159290932430254268769414"
  2354. "05973284973216824503042159",
  2355. "1"
  2356. },
  2357. { /* between forth and fifth iteration */
  2358. "2159140240970485794188159431017382878636879856244045329971239574"
  2359. "8919691133560661162828034323196457386059819832804593989740268964"
  2360. "74502911811812651475927076",
  2361. "6703903964971298549787012499102923063739682910296196688861780721"
  2362. "8608820150367734884009371490834517138450159290932430254268769414"
  2363. "05973284973216824503042158",
  2364. "6703903964971298549787012499102923063739682910296196688861780721"
  2365. "8608820150367734884009371490834517138450159290932430254268769414"
  2366. "05973284973216824503042159",
  2367. "1"
  2368. },
  2369. { /* between fifth and sixth iteration */
  2370. "5239312332984325668414624633307915097111691815000872662334695514"
  2371. "5436533521392362443557163429336808208137221322444780490437871903"
  2372. "99972784701334569424519255",
  2373. "6703903964971298549787012499102923063739682910296196688861780721"
  2374. "8608820150367734884009371490834517138450159290932430254268769414"
  2375. "05973284973216824503042158",
  2376. "6703903964971298549787012499102923063739682910296196688861780721"
  2377. "8608820150367734884009371490834517138450159290932430254268769414"
  2378. "05973284973216824503042159",
  2379. "1"
  2380. },
  2381. { /* between sixth and seventh iteration */
  2382. "1977953647322612860406858017869125467496941904523063466791308891"
  2383. "1172796739058531929470539758361774569875505293428856181093904091"
  2384. "33788264851714311303725089",
  2385. "6703903964971298549787012499102923063739682910296196688861780721"
  2386. "8608820150367734884009371490834517138450159290932430254268769414"
  2387. "05973284973216824503042158",
  2388. "6703903964971298549787012499102923063739682910296196688861780721"
  2389. "8608820150367734884009371490834517138450159290932430254268769414"
  2390. "05973284973216824503042159",
  2391. "1"
  2392. },
  2393. { /* between seventh and eighth iteration */
  2394. "6456987954117763835533395796948878140715006860263624787492985786"
  2395. "8514630216966738305923915688821526449499763719943997120302368211"
  2396. "04813318117996225041943964",
  2397. "1340780792994259709957402499820584612747936582059239337772356144"
  2398. "3721764030073546976801874298166903427690031858186486050853753882"
  2399. "811946551499689575296532556",
  2400. "1340780792994259709957402499820584612747936582059239337772356144"
  2401. "3721764030073546976801874298166903427690031858186486050853753882"
  2402. "811946551499689575296532557",
  2403. "1"
  2404. }
  2405. };
  2406. static int test_mod_exp(int i)
  2407. {
  2408. const MOD_EXP_TEST *test = &ModExpTests[i];
  2409. int res = 0;
  2410. BIGNUM* result = NULL;
  2411. BIGNUM *base = NULL, *exponent = NULL, *modulo = NULL;
  2412. char *s = NULL;
  2413. if (!TEST_ptr(result = BN_new())
  2414. || !TEST_true(BN_dec2bn(&base, test->base))
  2415. || !TEST_true(BN_dec2bn(&exponent, test->exp))
  2416. || !TEST_true(BN_dec2bn(&modulo, test->mod)))
  2417. goto err;
  2418. if (!TEST_int_eq(BN_mod_exp(result, base, exponent, modulo, ctx), 1))
  2419. goto err;
  2420. if (!TEST_ptr(s = BN_bn2dec(result)))
  2421. goto err;
  2422. if (!TEST_mem_eq(s, strlen(s), test->res, strlen(test->res)))
  2423. goto err;
  2424. res = 1;
  2425. err:
  2426. OPENSSL_free(s);
  2427. BN_free(result);
  2428. BN_free(base);
  2429. BN_free(exponent);
  2430. BN_free(modulo);
  2431. return res;
  2432. }
  2433. static int test_mod_exp_consttime(int i)
  2434. {
  2435. const MOD_EXP_TEST *test = &ModExpTests[i];
  2436. int res = 0;
  2437. BIGNUM* result = NULL;
  2438. BIGNUM *base = NULL, *exponent = NULL, *modulo = NULL;
  2439. char *s = NULL;
  2440. if (!TEST_ptr(result = BN_new())
  2441. || !TEST_true(BN_dec2bn(&base, test->base))
  2442. || !TEST_true(BN_dec2bn(&exponent, test->exp))
  2443. || !TEST_true(BN_dec2bn(&modulo, test->mod)))
  2444. goto err;
  2445. BN_set_flags(base, BN_FLG_CONSTTIME);
  2446. BN_set_flags(exponent, BN_FLG_CONSTTIME);
  2447. BN_set_flags(modulo, BN_FLG_CONSTTIME);
  2448. if (!TEST_int_eq(BN_mod_exp(result, base, exponent, modulo, ctx), 1))
  2449. goto err;
  2450. if (!TEST_ptr(s = BN_bn2dec(result)))
  2451. goto err;
  2452. if (!TEST_mem_eq(s, strlen(s), test->res, strlen(test->res)))
  2453. goto err;
  2454. res = 1;
  2455. err:
  2456. OPENSSL_free(s);
  2457. BN_free(result);
  2458. BN_free(base);
  2459. BN_free(exponent);
  2460. BN_free(modulo);
  2461. return res;
  2462. }
  2463. static int file_test_run(STANZA *s)
  2464. {
  2465. static const FILETEST filetests[] = {
  2466. {"Sum", file_sum},
  2467. {"LShift1", file_lshift1},
  2468. {"LShift", file_lshift},
  2469. {"RShift", file_rshift},
  2470. {"Square", file_square},
  2471. {"Product", file_product},
  2472. {"Quotient", file_quotient},
  2473. {"ModMul", file_modmul},
  2474. {"ModExp", file_modexp},
  2475. {"Exp", file_exp},
  2476. {"ModSqrt", file_modsqrt},
  2477. {"GCD", file_gcd},
  2478. };
  2479. int numtests = OSSL_NELEM(filetests);
  2480. const FILETEST *tp = filetests;
  2481. for ( ; --numtests >= 0; tp++) {
  2482. if (findattr(s, tp->name) != NULL) {
  2483. if (!tp->func(s)) {
  2484. TEST_info("%s:%d: Failed %s test",
  2485. s->test_file, s->start, tp->name);
  2486. return 0;
  2487. }
  2488. return 1;
  2489. }
  2490. }
  2491. TEST_info("%s:%d: Unknown test", s->test_file, s->start);
  2492. return 0;
  2493. }
  2494. static int run_file_tests(int i)
  2495. {
  2496. STANZA *s = NULL;
  2497. char *testfile = test_get_argument(i);
  2498. int c;
  2499. if (!TEST_ptr(s = OPENSSL_zalloc(sizeof(*s))))
  2500. return 0;
  2501. if (!test_start_file(s, testfile)) {
  2502. OPENSSL_free(s);
  2503. return 0;
  2504. }
  2505. /* Read test file. */
  2506. while (!BIO_eof(s->fp) && test_readstanza(s)) {
  2507. if (s->numpairs == 0)
  2508. continue;
  2509. if (!file_test_run(s))
  2510. s->errors++;
  2511. s->numtests++;
  2512. test_clearstanza(s);
  2513. }
  2514. test_end_file(s);
  2515. c = s->errors;
  2516. OPENSSL_free(s);
  2517. return c == 0;
  2518. }
  2519. typedef enum OPTION_choice {
  2520. OPT_ERR = -1,
  2521. OPT_EOF = 0,
  2522. OPT_STOCHASTIC_TESTS,
  2523. OPT_TEST_ENUM
  2524. } OPTION_CHOICE;
  2525. const OPTIONS *test_get_options(void)
  2526. {
  2527. static const OPTIONS test_options[] = {
  2528. OPT_TEST_OPTIONS_WITH_EXTRA_USAGE("[file...]\n"),
  2529. { "stochastic", OPT_STOCHASTIC_TESTS, '-', "Run stochastic tests" },
  2530. { OPT_HELP_STR, 1, '-',
  2531. "file\tFile to run tests on. Normal tests are not run\n" },
  2532. { NULL }
  2533. };
  2534. return test_options;
  2535. }
  2536. int setup_tests(void)
  2537. {
  2538. OPTION_CHOICE o;
  2539. int n, stochastic = 0;
  2540. while ((o = opt_next()) != OPT_EOF) {
  2541. switch (o) {
  2542. case OPT_STOCHASTIC_TESTS:
  2543. stochastic = 1;
  2544. break;
  2545. case OPT_TEST_CASES:
  2546. break;
  2547. default:
  2548. case OPT_ERR:
  2549. return 0;
  2550. }
  2551. }
  2552. n = test_get_argument_count();
  2553. if (!TEST_ptr(ctx = BN_CTX_new()))
  2554. return 0;
  2555. if (n == 0) {
  2556. ADD_TEST(test_sub);
  2557. ADD_TEST(test_div_recip);
  2558. ADD_TEST(test_mod);
  2559. ADD_TEST(test_modexp_mont5);
  2560. ADD_TEST(test_kronecker);
  2561. ADD_TEST(test_rand);
  2562. ADD_TEST(test_bn2padded);
  2563. ADD_TEST(test_dec2bn);
  2564. ADD_TEST(test_hex2bn);
  2565. ADD_TEST(test_asc2bn);
  2566. ADD_ALL_TESTS(test_mpi, (int)OSSL_NELEM(kMPITests));
  2567. ADD_TEST(test_negzero);
  2568. ADD_TEST(test_badmod);
  2569. ADD_TEST(test_expmodzero);
  2570. ADD_TEST(test_expmodone);
  2571. ADD_ALL_TESTS(test_smallprime, 16);
  2572. ADD_ALL_TESTS(test_smallsafeprime, 16);
  2573. ADD_TEST(test_swap);
  2574. ADD_TEST(test_ctx_consttime_flag);
  2575. #ifndef OPENSSL_NO_EC2M
  2576. ADD_TEST(test_gf2m_add);
  2577. ADD_TEST(test_gf2m_mod);
  2578. ADD_TEST(test_gf2m_mul);
  2579. ADD_TEST(test_gf2m_sqr);
  2580. ADD_TEST(test_gf2m_modinv);
  2581. ADD_TEST(test_gf2m_moddiv);
  2582. ADD_TEST(test_gf2m_modexp);
  2583. ADD_TEST(test_gf2m_modsqrt);
  2584. ADD_TEST(test_gf2m_modsolvequad);
  2585. #endif
  2586. ADD_ALL_TESTS(test_is_prime, (int)OSSL_NELEM(primes));
  2587. ADD_ALL_TESTS(test_not_prime, (int)OSSL_NELEM(not_primes));
  2588. ADD_TEST(test_gcd_prime);
  2589. ADD_ALL_TESTS(test_mod_exp, (int)OSSL_NELEM(ModExpTests));
  2590. ADD_ALL_TESTS(test_mod_exp_consttime, (int)OSSL_NELEM(ModExpTests));
  2591. if (stochastic)
  2592. ADD_TEST(test_rand_range);
  2593. } else {
  2594. ADD_ALL_TESTS(run_file_tests, n);
  2595. }
  2596. return 1;
  2597. }
  2598. void cleanup_tests(void)
  2599. {
  2600. BN_CTX_free(ctx);
  2601. }