bntest.c 69 KB

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