bntest.c 50 KB

1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283848586878889909192939495969798991001011021031041051061071081091101111121131141151161171181191201211221231241251261271281291301311321331341351361371381391401411421431441451461471481491501511521531541551561571581591601611621631641651661671681691701711721731741751761771781791801811821831841851861871881891901911921931941951961971981992002012022032042052062072082092102112122132142152162172182192202212222232242252262272282292302312322332342352362372382392402412422432442452462472482492502512522532542552562572582592602612622632642652662672682692702712722732742752762772782792802812822832842852862872882892902912922932942952962972982993003013023033043053063073083093103113123133143153163173183193203213223233243253263273283293303313323333343353363373383393403413423433443453463473483493503513523533543553563573583593603613623633643653663673683693703713723733743753763773783793803813823833843853863873883893903913923933943953963973983994004014024034044054064074084094104114124134144154164174184194204214224234244254264274284294304314324334344354364374384394404414424434444454464474484494504514524534544554564574584594604614624634644654664674684694704714724734744754764774784794804814824834844854864874884894904914924934944954964974984995005015025035045055065075085095105115125135145155165175185195205215225235245255265275285295305315325335345355365375385395405415425435445455465475485495505515525535545555565575585595605615625635645655665675685695705715725735745755765775785795805815825835845855865875885895905915925935945955965975985996006016026036046056066076086096106116126136146156166176186196206216226236246256266276286296306316326336346356366376386396406416426436446456466476486496506516526536546556566576586596606616626636646656666676686696706716726736746756766776786796806816826836846856866876886896906916926936946956966976986997007017027037047057067077087097107117127137147157167177187197207217227237247257267277287297307317327337347357367377387397407417427437447457467477487497507517527537547557567577587597607617627637647657667677687697707717727737747757767777787797807817827837847857867877887897907917927937947957967977987998008018028038048058068078088098108118128138148158168178188198208218228238248258268278288298308318328338348358368378388398408418428438448458468478488498508518528538548558568578588598608618628638648658668678688698708718728738748758768778788798808818828838848858868878888898908918928938948958968978988999009019029039049059069079089099109119129139149159169179189199209219229239249259269279289299309319329339349359369379389399409419429439449459469479489499509519529539549559569579589599609619629639649659669679689699709719729739749759769779789799809819829839849859869879889899909919929939949959969979989991000100110021003100410051006100710081009101010111012101310141015101610171018101910201021102210231024102510261027102810291030103110321033103410351036103710381039104010411042104310441045104610471048104910501051105210531054105510561057105810591060106110621063106410651066106710681069107010711072107310741075107610771078107910801081108210831084108510861087108810891090109110921093109410951096109710981099110011011102110311041105110611071108110911101111111211131114111511161117111811191120112111221123112411251126112711281129113011311132113311341135113611371138113911401141114211431144114511461147114811491150115111521153115411551156115711581159116011611162116311641165116611671168116911701171117211731174117511761177117811791180118111821183118411851186118711881189119011911192119311941195119611971198119912001201120212031204120512061207120812091210121112121213121412151216121712181219122012211222122312241225122612271228122912301231123212331234123512361237123812391240124112421243124412451246124712481249125012511252125312541255125612571258125912601261126212631264126512661267126812691270127112721273127412751276127712781279128012811282128312841285128612871288128912901291129212931294129512961297129812991300130113021303130413051306130713081309131013111312131313141315131613171318131913201321132213231324132513261327132813291330133113321333133413351336133713381339134013411342134313441345134613471348134913501351135213531354135513561357135813591360136113621363136413651366136713681369137013711372137313741375137613771378137913801381138213831384138513861387138813891390139113921393139413951396139713981399140014011402140314041405140614071408140914101411141214131414141514161417141814191420142114221423142414251426142714281429143014311432143314341435143614371438143914401441144214431444144514461447144814491450145114521453145414551456145714581459146014611462146314641465146614671468146914701471147214731474147514761477147814791480148114821483148414851486148714881489149014911492149314941495149614971498149915001501150215031504150515061507150815091510151115121513151415151516151715181519152015211522152315241525152615271528152915301531153215331534153515361537153815391540154115421543154415451546154715481549155015511552155315541555155615571558155915601561156215631564156515661567156815691570157115721573157415751576157715781579158015811582158315841585158615871588158915901591159215931594159515961597159815991600160116021603160416051606160716081609161016111612161316141615161616171618161916201621162216231624162516261627162816291630163116321633163416351636163716381639164016411642164316441645164616471648164916501651165216531654165516561657165816591660166116621663166416651666166716681669167016711672167316741675167616771678167916801681168216831684168516861687168816891690169116921693169416951696169716981699170017011702170317041705170617071708170917101711171217131714171517161717171817191720172117221723172417251726172717281729173017311732173317341735173617371738173917401741174217431744174517461747174817491750175117521753175417551756175717581759176017611762176317641765176617671768176917701771177217731774177517761777177817791780178117821783178417851786178717881789179017911792179317941795179617971798179918001801180218031804180518061807180818091810181118121813181418151816181718181819182018211822182318241825182618271828182918301831183218331834183518361837183818391840184118421843184418451846184718481849185018511852185318541855185618571858185918601861186218631864186518661867186818691870187118721873187418751876187718781879188018811882188318841885188618871888188918901891189218931894189518961897189818991900190119021903190419051906190719081909191019111912191319141915191619171918191919201921192219231924192519261927192819291930193119321933193419351936193719381939194019411942194319441945194619471948194919501951195219531954195519561957195819591960196119621963196419651966196719681969197019711972197319741975197619771978197919801981198219831984198519861987198819891990199119921993199419951996199719981999200020012002200320042005200620072008200920102011201220132014201520162017201820192020202120222023202420252026202720282029203020312032
  1. /* Copyright (C) 1995-1998 Eric Young (eay@cryptsoft.com)
  2. * All rights reserved.
  3. *
  4. * This package is an SSL implementation written
  5. * by Eric Young (eay@cryptsoft.com).
  6. * The implementation was written so as to conform with Netscapes SSL.
  7. *
  8. * This library is free for commercial and non-commercial use as long as
  9. * the following conditions are aheared to. The following conditions
  10. * apply to all code found in this distribution, be it the RC4, RSA,
  11. * lhash, DES, etc., code; not just the SSL code. The SSL documentation
  12. * included with this distribution is covered by the same copyright terms
  13. * except that the holder is Tim Hudson (tjh@cryptsoft.com).
  14. *
  15. * Copyright remains Eric Young's, and as such any Copyright notices in
  16. * the code are not to be removed.
  17. * If this package is used in a product, Eric Young should be given attribution
  18. * as the author of the parts of the library used.
  19. * This can be in the form of a textual message at program startup or
  20. * in documentation (online or textual) provided with the package.
  21. *
  22. * Redistribution and use in source and binary forms, with or without
  23. * modification, are permitted provided that the following conditions
  24. * are met:
  25. * 1. Redistributions of source code must retain the copyright
  26. * notice, this list of conditions and the following disclaimer.
  27. * 2. Redistributions in binary form must reproduce the above copyright
  28. * notice, this list of conditions and the following disclaimer in the
  29. * documentation and/or other materials provided with the distribution.
  30. * 3. All advertising materials mentioning features or use of this software
  31. * must display the following acknowledgement:
  32. * "This product includes cryptographic software written by
  33. * Eric Young (eay@cryptsoft.com)"
  34. * The word 'cryptographic' can be left out if the rouines from the library
  35. * being used are not cryptographic related :-).
  36. * 4. If you include any Windows specific code (or a derivative thereof) from
  37. * the apps directory (application code) you must include an acknowledgement:
  38. * "This product includes software written by Tim Hudson (tjh@cryptsoft.com)"
  39. *
  40. * THIS SOFTWARE IS PROVIDED BY ERIC YOUNG ``AS IS'' AND
  41. * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  42. * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  43. * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
  44. * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  45. * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
  46. * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  47. * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  48. * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
  49. * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  50. * SUCH DAMAGE.
  51. *
  52. * The licence and distribution terms for any publically available version or
  53. * derivative of this code cannot be changed. i.e. this code cannot simply be
  54. * copied and put under another distribution licence
  55. * [including the GNU Public Licence.]
  56. */
  57. /* ====================================================================
  58. * Copyright 2002 Sun Microsystems, Inc. ALL RIGHTS RESERVED.
  59. *
  60. * Portions of the attached software ("Contribution") are developed by
  61. * SUN MICROSYSTEMS, INC., and are contributed to the OpenSSL project.
  62. *
  63. * The Contribution is licensed pursuant to the Eric Young open source
  64. * license provided above.
  65. *
  66. * The binary polynomial arithmetic software is originally written by
  67. * Sheueling Chang Shantz and Douglas Stebila of Sun Microsystems Laboratories.
  68. *
  69. */
  70. #include <stdio.h>
  71. #include <stdlib.h>
  72. #include <string.h>
  73. #include "e_os.h"
  74. #include <openssl/bio.h>
  75. #include <openssl/bn.h>
  76. #include <openssl/rand.h>
  77. #include <openssl/x509.h>
  78. #include <openssl/err.h>
  79. #include "../crypto/bn/bn_lcl.h"
  80. static const int num0 = 100; /* number of tests */
  81. static const int num1 = 50; /* additional tests for some functions */
  82. static const int num2 = 5; /* number of tests for slow functions */
  83. int test_add(BIO *bp);
  84. int test_sub(BIO *bp);
  85. int test_lshift1(BIO *bp);
  86. int test_lshift(BIO *bp, BN_CTX *ctx, BIGNUM *a_);
  87. int test_rshift1(BIO *bp);
  88. int test_rshift(BIO *bp, BN_CTX *ctx);
  89. int test_div(BIO *bp, BN_CTX *ctx);
  90. int test_div_word(BIO *bp);
  91. int test_div_recp(BIO *bp, BN_CTX *ctx);
  92. int test_mul(BIO *bp);
  93. int test_sqr(BIO *bp, BN_CTX *ctx);
  94. int test_mont(BIO *bp, BN_CTX *ctx);
  95. int test_mod(BIO *bp, BN_CTX *ctx);
  96. int test_mod_mul(BIO *bp, BN_CTX *ctx);
  97. int test_mod_exp(BIO *bp, BN_CTX *ctx);
  98. int test_mod_exp_mont_consttime(BIO *bp, BN_CTX *ctx);
  99. int test_mod_exp_mont5(BIO *bp, BN_CTX *ctx);
  100. int test_exp(BIO *bp, BN_CTX *ctx);
  101. int test_gf2m_add(BIO *bp);
  102. int test_gf2m_mod(BIO *bp);
  103. int test_gf2m_mod_mul(BIO *bp, BN_CTX *ctx);
  104. int test_gf2m_mod_sqr(BIO *bp, BN_CTX *ctx);
  105. int test_gf2m_mod_inv(BIO *bp, BN_CTX *ctx);
  106. int test_gf2m_mod_div(BIO *bp, BN_CTX *ctx);
  107. int test_gf2m_mod_exp(BIO *bp, BN_CTX *ctx);
  108. int test_gf2m_mod_sqrt(BIO *bp, BN_CTX *ctx);
  109. int test_gf2m_mod_solve_quad(BIO *bp, BN_CTX *ctx);
  110. int test_kron(BIO *bp, BN_CTX *ctx);
  111. int test_sqrt(BIO *bp, BN_CTX *ctx);
  112. int test_small_prime(BIO *bp, BN_CTX *ctx);
  113. int rand_neg(void);
  114. static int results = 0;
  115. static unsigned char lst[] =
  116. "\xC6\x4F\x43\x04\x2A\xEA\xCA\x6E\x58\x36\x80\x5B\xE8\xC9"
  117. "\x9B\x04\x5D\x48\x36\xC2\xFD\x16\xC9\x64\xF0";
  118. static const char rnd_seed[] =
  119. "string to make the random number generator think it has entropy";
  120. static void message(BIO *out, char *m)
  121. {
  122. fprintf(stderr, "test %s\n", m);
  123. BIO_puts(out, "print \"test ");
  124. BIO_puts(out, m);
  125. BIO_puts(out, "\\n\"\n");
  126. }
  127. int main(int argc, char *argv[])
  128. {
  129. BN_CTX *ctx;
  130. BIO *out;
  131. char *outfile = NULL;
  132. results = 0;
  133. RAND_seed(rnd_seed, sizeof rnd_seed); /* or BN_generate_prime may fail */
  134. argc--;
  135. argv++;
  136. while (argc >= 1) {
  137. if (strcmp(*argv, "-results") == 0)
  138. results = 1;
  139. else if (strcmp(*argv, "-out") == 0) {
  140. if (--argc < 1)
  141. break;
  142. outfile = *(++argv);
  143. }
  144. argc--;
  145. argv++;
  146. }
  147. ctx = BN_CTX_new();
  148. if (ctx == NULL)
  149. EXIT(1);
  150. out = BIO_new(BIO_s_file());
  151. if (out == NULL)
  152. EXIT(1);
  153. if (outfile == NULL) {
  154. BIO_set_fp(out, stdout, BIO_NOCLOSE | BIO_FP_TEXT);
  155. } else {
  156. if (!BIO_write_filename(out, outfile)) {
  157. perror(outfile);
  158. EXIT(1);
  159. }
  160. }
  161. #ifdef OPENSSL_SYS_VMS
  162. {
  163. BIO *tmpbio = BIO_new(BIO_f_linebuffer());
  164. out = BIO_push(tmpbio, out);
  165. }
  166. #endif
  167. if (!results)
  168. BIO_puts(out, "obase=16\nibase=16\n");
  169. message(out, "BN_add");
  170. if (!test_add(out))
  171. goto err;
  172. (void)BIO_flush(out);
  173. message(out, "BN_sub");
  174. if (!test_sub(out))
  175. goto err;
  176. (void)BIO_flush(out);
  177. message(out, "BN_lshift1");
  178. if (!test_lshift1(out))
  179. goto err;
  180. (void)BIO_flush(out);
  181. message(out, "BN_lshift (fixed)");
  182. if (!test_lshift(out, ctx, BN_bin2bn(lst, sizeof(lst) - 1, NULL)))
  183. goto err;
  184. (void)BIO_flush(out);
  185. message(out, "BN_lshift");
  186. if (!test_lshift(out, ctx, NULL))
  187. goto err;
  188. (void)BIO_flush(out);
  189. message(out, "BN_rshift1");
  190. if (!test_rshift1(out))
  191. goto err;
  192. (void)BIO_flush(out);
  193. message(out, "BN_rshift");
  194. if (!test_rshift(out, ctx))
  195. goto err;
  196. (void)BIO_flush(out);
  197. message(out, "BN_sqr");
  198. if (!test_sqr(out, ctx))
  199. goto err;
  200. (void)BIO_flush(out);
  201. message(out, "BN_mul");
  202. if (!test_mul(out))
  203. goto err;
  204. (void)BIO_flush(out);
  205. message(out, "BN_div");
  206. if (!test_div(out, ctx))
  207. goto err;
  208. (void)BIO_flush(out);
  209. message(out, "BN_div_word");
  210. if (!test_div_word(out))
  211. goto err;
  212. (void)BIO_flush(out);
  213. message(out, "BN_div_recp");
  214. if (!test_div_recp(out, ctx))
  215. goto err;
  216. (void)BIO_flush(out);
  217. message(out, "BN_mod");
  218. if (!test_mod(out, ctx))
  219. goto err;
  220. (void)BIO_flush(out);
  221. message(out, "BN_mod_mul");
  222. if (!test_mod_mul(out, ctx))
  223. goto err;
  224. (void)BIO_flush(out);
  225. message(out, "BN_mont");
  226. if (!test_mont(out, ctx))
  227. goto err;
  228. (void)BIO_flush(out);
  229. message(out, "BN_mod_exp");
  230. if (!test_mod_exp(out, ctx))
  231. goto err;
  232. (void)BIO_flush(out);
  233. message(out, "BN_mod_exp_mont_consttime");
  234. if (!test_mod_exp_mont_consttime(out, ctx))
  235. goto err;
  236. if (!test_mod_exp_mont5(out, ctx))
  237. goto err;
  238. (void)BIO_flush(out);
  239. message(out, "BN_exp");
  240. if (!test_exp(out, ctx))
  241. goto err;
  242. (void)BIO_flush(out);
  243. message(out, "BN_kronecker");
  244. if (!test_kron(out, ctx))
  245. goto err;
  246. (void)BIO_flush(out);
  247. message(out, "BN_mod_sqrt");
  248. if (!test_sqrt(out, ctx))
  249. goto err;
  250. (void)BIO_flush(out);
  251. message(out, "Small prime generation");
  252. if (!test_small_prime(out, ctx))
  253. goto err;
  254. (void)BIO_flush(out);
  255. #ifndef OPENSSL_NO_EC2M
  256. message(out, "BN_GF2m_add");
  257. if (!test_gf2m_add(out))
  258. goto err;
  259. (void)BIO_flush(out);
  260. message(out, "BN_GF2m_mod");
  261. if (!test_gf2m_mod(out))
  262. goto err;
  263. (void)BIO_flush(out);
  264. message(out, "BN_GF2m_mod_mul");
  265. if (!test_gf2m_mod_mul(out, ctx))
  266. goto err;
  267. (void)BIO_flush(out);
  268. message(out, "BN_GF2m_mod_sqr");
  269. if (!test_gf2m_mod_sqr(out, ctx))
  270. goto err;
  271. (void)BIO_flush(out);
  272. message(out, "BN_GF2m_mod_inv");
  273. if (!test_gf2m_mod_inv(out, ctx))
  274. goto err;
  275. (void)BIO_flush(out);
  276. message(out, "BN_GF2m_mod_div");
  277. if (!test_gf2m_mod_div(out, ctx))
  278. goto err;
  279. (void)BIO_flush(out);
  280. message(out, "BN_GF2m_mod_exp");
  281. if (!test_gf2m_mod_exp(out, ctx))
  282. goto err;
  283. (void)BIO_flush(out);
  284. message(out, "BN_GF2m_mod_sqrt");
  285. if (!test_gf2m_mod_sqrt(out, ctx))
  286. goto err;
  287. (void)BIO_flush(out);
  288. message(out, "BN_GF2m_mod_solve_quad");
  289. if (!test_gf2m_mod_solve_quad(out, ctx))
  290. goto err;
  291. (void)BIO_flush(out);
  292. #endif
  293. BN_CTX_free(ctx);
  294. BIO_free(out);
  295. EXIT(0);
  296. err:
  297. BIO_puts(out, "1\n"); /* make sure the Perl script fed by bc
  298. * notices the failure, see test_bn in
  299. * test/Makefile.ssl */
  300. (void)BIO_flush(out);
  301. ERR_print_errors_fp(stderr);
  302. EXIT(1);
  303. }
  304. int test_add(BIO *bp)
  305. {
  306. BIGNUM *a, *b, *c;
  307. int i;
  308. a = BN_new();
  309. b = BN_new();
  310. c = BN_new();
  311. BN_bntest_rand(a, 512, 0, 0);
  312. for (i = 0; i < num0; i++) {
  313. BN_bntest_rand(b, 450 + i, 0, 0);
  314. a->neg = rand_neg();
  315. b->neg = rand_neg();
  316. BN_add(c, a, b);
  317. if (bp != NULL) {
  318. if (!results) {
  319. BN_print(bp, a);
  320. BIO_puts(bp, " + ");
  321. BN_print(bp, b);
  322. BIO_puts(bp, " - ");
  323. }
  324. BN_print(bp, c);
  325. BIO_puts(bp, "\n");
  326. }
  327. a->neg = !a->neg;
  328. b->neg = !b->neg;
  329. BN_add(c, c, b);
  330. BN_add(c, c, a);
  331. if (!BN_is_zero(c)) {
  332. fprintf(stderr, "Add test failed!\n");
  333. return 0;
  334. }
  335. }
  336. BN_free(a);
  337. BN_free(b);
  338. BN_free(c);
  339. return (1);
  340. }
  341. int test_sub(BIO *bp)
  342. {
  343. BIGNUM *a, *b, *c;
  344. int i;
  345. a = BN_new();
  346. b = BN_new();
  347. c = BN_new();
  348. for (i = 0; i < num0 + num1; i++) {
  349. if (i < num1) {
  350. BN_bntest_rand(a, 512, 0, 0);
  351. BN_copy(b, a);
  352. if (BN_set_bit(a, i) == 0)
  353. return (0);
  354. BN_add_word(b, i);
  355. } else {
  356. BN_bntest_rand(b, 400 + i - num1, 0, 0);
  357. a->neg = rand_neg();
  358. b->neg = rand_neg();
  359. }
  360. BN_sub(c, a, b);
  361. if (bp != NULL) {
  362. if (!results) {
  363. BN_print(bp, a);
  364. BIO_puts(bp, " - ");
  365. BN_print(bp, b);
  366. BIO_puts(bp, " - ");
  367. }
  368. BN_print(bp, c);
  369. BIO_puts(bp, "\n");
  370. }
  371. BN_add(c, c, b);
  372. BN_sub(c, c, a);
  373. if (!BN_is_zero(c)) {
  374. fprintf(stderr, "Subtract test failed!\n");
  375. return 0;
  376. }
  377. }
  378. BN_free(a);
  379. BN_free(b);
  380. BN_free(c);
  381. return (1);
  382. }
  383. int test_div(BIO *bp, BN_CTX *ctx)
  384. {
  385. BIGNUM *a, *b, *c, *d, *e;
  386. int i;
  387. a = BN_new();
  388. b = BN_new();
  389. c = BN_new();
  390. d = BN_new();
  391. e = BN_new();
  392. BN_one(a);
  393. BN_zero(b);
  394. if (BN_div(d, c, a, b, ctx)) {
  395. fprintf(stderr, "Division by zero succeeded!\n");
  396. return 0;
  397. }
  398. for (i = 0; i < num0 + num1; i++) {
  399. if (i < num1) {
  400. BN_bntest_rand(a, 400, 0, 0);
  401. BN_copy(b, a);
  402. BN_lshift(a, a, i);
  403. BN_add_word(a, i);
  404. } else
  405. BN_bntest_rand(b, 50 + 3 * (i - num1), 0, 0);
  406. a->neg = rand_neg();
  407. b->neg = rand_neg();
  408. BN_div(d, c, a, b, ctx);
  409. if (bp != NULL) {
  410. if (!results) {
  411. BN_print(bp, a);
  412. BIO_puts(bp, " / ");
  413. BN_print(bp, b);
  414. BIO_puts(bp, " - ");
  415. }
  416. BN_print(bp, d);
  417. BIO_puts(bp, "\n");
  418. if (!results) {
  419. BN_print(bp, a);
  420. BIO_puts(bp, " % ");
  421. BN_print(bp, b);
  422. BIO_puts(bp, " - ");
  423. }
  424. BN_print(bp, c);
  425. BIO_puts(bp, "\n");
  426. }
  427. BN_mul(e, d, b, ctx);
  428. BN_add(d, e, c);
  429. BN_sub(d, d, a);
  430. if (!BN_is_zero(d)) {
  431. fprintf(stderr, "Division test failed!\n");
  432. return 0;
  433. }
  434. }
  435. BN_free(a);
  436. BN_free(b);
  437. BN_free(c);
  438. BN_free(d);
  439. BN_free(e);
  440. return (1);
  441. }
  442. static void print_word(BIO *bp, BN_ULONG w)
  443. {
  444. int i = sizeof(w) * 8;
  445. char *fmt = NULL;
  446. unsigned char byte;
  447. do {
  448. i -= 8;
  449. byte = (unsigned char)(w >> i);
  450. if (fmt == NULL)
  451. fmt = byte ? "%X" : NULL;
  452. else
  453. fmt = "%02X";
  454. if (fmt != NULL)
  455. BIO_printf(bp, fmt, byte);
  456. } while (i);
  457. /* If we haven't printed anything, at least print a zero! */
  458. if (fmt == NULL)
  459. BIO_printf(bp, "0");
  460. }
  461. int test_div_word(BIO *bp)
  462. {
  463. BIGNUM *a, *b;
  464. BN_ULONG r, s;
  465. int i;
  466. a = BN_new();
  467. b = BN_new();
  468. for (i = 0; i < num0; i++) {
  469. do {
  470. BN_bntest_rand(a, 512, -1, 0);
  471. BN_bntest_rand(b, BN_BITS2, -1, 0);
  472. } while (BN_is_zero(b));
  473. s = b->d[0];
  474. BN_copy(b, a);
  475. r = BN_div_word(b, s);
  476. if (bp != NULL) {
  477. if (!results) {
  478. BN_print(bp, a);
  479. BIO_puts(bp, " / ");
  480. print_word(bp, s);
  481. BIO_puts(bp, " - ");
  482. }
  483. BN_print(bp, b);
  484. BIO_puts(bp, "\n");
  485. if (!results) {
  486. BN_print(bp, a);
  487. BIO_puts(bp, " % ");
  488. print_word(bp, s);
  489. BIO_puts(bp, " - ");
  490. }
  491. print_word(bp, r);
  492. BIO_puts(bp, "\n");
  493. }
  494. BN_mul_word(b, s);
  495. BN_add_word(b, r);
  496. BN_sub(b, a, b);
  497. if (!BN_is_zero(b)) {
  498. fprintf(stderr, "Division (word) test failed!\n");
  499. return 0;
  500. }
  501. }
  502. BN_free(a);
  503. BN_free(b);
  504. return (1);
  505. }
  506. int test_div_recp(BIO *bp, BN_CTX *ctx)
  507. {
  508. BIGNUM *a, *b, *c, *d, *e;
  509. BN_RECP_CTX *recp;
  510. int i;
  511. recp = BN_RECP_CTX_new();
  512. a = BN_new();
  513. b = BN_new();
  514. c = BN_new();
  515. d = BN_new();
  516. e = BN_new();
  517. for (i = 0; i < num0 + num1; i++) {
  518. if (i < num1) {
  519. BN_bntest_rand(a, 400, 0, 0);
  520. BN_copy(b, a);
  521. BN_lshift(a, a, i);
  522. BN_add_word(a, i);
  523. } else
  524. BN_bntest_rand(b, 50 + 3 * (i - num1), 0, 0);
  525. a->neg = rand_neg();
  526. b->neg = rand_neg();
  527. BN_RECP_CTX_set(recp, b, ctx);
  528. BN_div_recp(d, c, a, recp, ctx);
  529. if (bp != NULL) {
  530. if (!results) {
  531. BN_print(bp, a);
  532. BIO_puts(bp, " / ");
  533. BN_print(bp, b);
  534. BIO_puts(bp, " - ");
  535. }
  536. BN_print(bp, d);
  537. BIO_puts(bp, "\n");
  538. if (!results) {
  539. BN_print(bp, a);
  540. BIO_puts(bp, " % ");
  541. BN_print(bp, b);
  542. BIO_puts(bp, " - ");
  543. }
  544. BN_print(bp, c);
  545. BIO_puts(bp, "\n");
  546. }
  547. BN_mul(e, d, b, ctx);
  548. BN_add(d, e, c);
  549. BN_sub(d, d, a);
  550. if (!BN_is_zero(d)) {
  551. fprintf(stderr, "Reciprocal division test failed!\n");
  552. fprintf(stderr, "a=");
  553. BN_print_fp(stderr, a);
  554. fprintf(stderr, "\nb=");
  555. BN_print_fp(stderr, b);
  556. fprintf(stderr, "\n");
  557. return 0;
  558. }
  559. }
  560. BN_free(a);
  561. BN_free(b);
  562. BN_free(c);
  563. BN_free(d);
  564. BN_free(e);
  565. BN_RECP_CTX_free(recp);
  566. return (1);
  567. }
  568. int test_mul(BIO *bp)
  569. {
  570. BIGNUM *a, *b, *c, *d, *e;
  571. int i;
  572. BN_CTX *ctx;
  573. ctx = BN_CTX_new();
  574. if (ctx == NULL)
  575. EXIT(1);
  576. a = BN_new();
  577. b = BN_new();
  578. c = BN_new();
  579. d = BN_new();
  580. e = BN_new();
  581. for (i = 0; i < num0 + num1; i++) {
  582. if (i <= num1) {
  583. BN_bntest_rand(a, 100, 0, 0);
  584. BN_bntest_rand(b, 100, 0, 0);
  585. } else
  586. BN_bntest_rand(b, i - num1, 0, 0);
  587. a->neg = rand_neg();
  588. b->neg = rand_neg();
  589. BN_mul(c, a, b, ctx);
  590. if (bp != NULL) {
  591. if (!results) {
  592. BN_print(bp, a);
  593. BIO_puts(bp, " * ");
  594. BN_print(bp, b);
  595. BIO_puts(bp, " - ");
  596. }
  597. BN_print(bp, c);
  598. BIO_puts(bp, "\n");
  599. }
  600. BN_div(d, e, c, a, ctx);
  601. BN_sub(d, d, b);
  602. if (!BN_is_zero(d) || !BN_is_zero(e)) {
  603. fprintf(stderr, "Multiplication test failed!\n");
  604. return 0;
  605. }
  606. }
  607. BN_free(a);
  608. BN_free(b);
  609. BN_free(c);
  610. BN_free(d);
  611. BN_free(e);
  612. BN_CTX_free(ctx);
  613. return (1);
  614. }
  615. int test_sqr(BIO *bp, BN_CTX *ctx)
  616. {
  617. BIGNUM *a, *c, *d, *e;
  618. int i, ret = 0;
  619. a = BN_new();
  620. c = BN_new();
  621. d = BN_new();
  622. e = BN_new();
  623. if (a == NULL || c == NULL || d == NULL || e == NULL) {
  624. goto err;
  625. }
  626. for (i = 0; i < num0; i++) {
  627. BN_bntest_rand(a, 40 + i * 10, 0, 0);
  628. a->neg = rand_neg();
  629. BN_sqr(c, a, ctx);
  630. if (bp != NULL) {
  631. if (!results) {
  632. BN_print(bp, a);
  633. BIO_puts(bp, " * ");
  634. BN_print(bp, a);
  635. BIO_puts(bp, " - ");
  636. }
  637. BN_print(bp, c);
  638. BIO_puts(bp, "\n");
  639. }
  640. BN_div(d, e, c, a, ctx);
  641. BN_sub(d, d, a);
  642. if (!BN_is_zero(d) || !BN_is_zero(e)) {
  643. fprintf(stderr, "Square test failed!\n");
  644. goto err;
  645. }
  646. }
  647. /* Regression test for a BN_sqr overflow bug. */
  648. BN_hex2bn(&a,
  649. "80000000000000008000000000000001"
  650. "FFFFFFFFFFFFFFFE0000000000000000");
  651. BN_sqr(c, a, ctx);
  652. if (bp != NULL) {
  653. if (!results) {
  654. BN_print(bp, a);
  655. BIO_puts(bp, " * ");
  656. BN_print(bp, a);
  657. BIO_puts(bp, " - ");
  658. }
  659. BN_print(bp, c);
  660. BIO_puts(bp, "\n");
  661. }
  662. BN_mul(d, a, a, ctx);
  663. if (BN_cmp(c, d)) {
  664. fprintf(stderr, "Square test failed: BN_sqr and BN_mul produce "
  665. "different results!\n");
  666. goto err;
  667. }
  668. /* Regression test for a BN_sqr overflow bug. */
  669. BN_hex2bn(&a,
  670. "80000000000000000000000080000001"
  671. "FFFFFFFE000000000000000000000000");
  672. BN_sqr(c, a, ctx);
  673. if (bp != NULL) {
  674. if (!results) {
  675. BN_print(bp, a);
  676. BIO_puts(bp, " * ");
  677. BN_print(bp, a);
  678. BIO_puts(bp, " - ");
  679. }
  680. BN_print(bp, c);
  681. BIO_puts(bp, "\n");
  682. }
  683. BN_mul(d, a, a, ctx);
  684. if (BN_cmp(c, d)) {
  685. fprintf(stderr, "Square test failed: BN_sqr and BN_mul produce "
  686. "different results!\n");
  687. goto err;
  688. }
  689. ret = 1;
  690. err:
  691. BN_free(a);
  692. BN_free(c);
  693. BN_free(d);
  694. BN_free(e);
  695. return ret;
  696. }
  697. int test_mont(BIO *bp, BN_CTX *ctx)
  698. {
  699. BIGNUM *a, *b, *c, *d, *A, *B;
  700. BIGNUM *n;
  701. int i;
  702. BN_MONT_CTX *mont;
  703. a = BN_new();
  704. b = BN_new();
  705. c = BN_new();
  706. d = BN_new();
  707. A = BN_new();
  708. B = BN_new();
  709. n = BN_new();
  710. mont = BN_MONT_CTX_new();
  711. if (mont == NULL)
  712. return 0;
  713. BN_zero(n);
  714. if (BN_MONT_CTX_set(mont, n, ctx)) {
  715. fprintf(stderr, "BN_MONT_CTX_set succeeded for zero modulus!\n");
  716. return 0;
  717. }
  718. BN_set_word(n, 16);
  719. if (BN_MONT_CTX_set(mont, n, ctx)) {
  720. fprintf(stderr, "BN_MONT_CTX_set succeeded for even modulus!\n");
  721. return 0;
  722. }
  723. BN_bntest_rand(a, 100, 0, 0);
  724. BN_bntest_rand(b, 100, 0, 0);
  725. for (i = 0; i < num2; i++) {
  726. int bits = (200 * (i + 1)) / num2;
  727. if (bits == 0)
  728. continue;
  729. BN_bntest_rand(n, bits, 0, 1);
  730. BN_MONT_CTX_set(mont, n, ctx);
  731. BN_nnmod(a, a, n, ctx);
  732. BN_nnmod(b, b, n, ctx);
  733. BN_to_montgomery(A, a, mont, ctx);
  734. BN_to_montgomery(B, b, mont, ctx);
  735. BN_mod_mul_montgomery(c, A, B, mont, ctx);
  736. BN_from_montgomery(A, c, mont, ctx);
  737. if (bp != NULL) {
  738. if (!results) {
  739. BN_print(bp, a);
  740. BIO_puts(bp, " * ");
  741. BN_print(bp, b);
  742. BIO_puts(bp, " % ");
  743. BN_print(bp, &mont->N);
  744. BIO_puts(bp, " - ");
  745. }
  746. BN_print(bp, A);
  747. BIO_puts(bp, "\n");
  748. }
  749. BN_mod_mul(d, a, b, n, ctx);
  750. BN_sub(d, d, A);
  751. if (!BN_is_zero(d)) {
  752. fprintf(stderr, "Montgomery multiplication test failed!\n");
  753. return 0;
  754. }
  755. }
  756. BN_MONT_CTX_free(mont);
  757. BN_free(a);
  758. BN_free(b);
  759. BN_free(c);
  760. BN_free(d);
  761. BN_free(A);
  762. BN_free(B);
  763. BN_free(n);
  764. return (1);
  765. }
  766. int test_mod(BIO *bp, BN_CTX *ctx)
  767. {
  768. BIGNUM *a, *b, *c, *d, *e;
  769. int i;
  770. a = BN_new();
  771. b = BN_new();
  772. c = BN_new();
  773. d = BN_new();
  774. e = BN_new();
  775. BN_bntest_rand(a, 1024, 0, 0);
  776. for (i = 0; i < num0; i++) {
  777. BN_bntest_rand(b, 450 + i * 10, 0, 0);
  778. a->neg = rand_neg();
  779. b->neg = rand_neg();
  780. BN_mod(c, a, b, ctx);
  781. if (bp != NULL) {
  782. if (!results) {
  783. BN_print(bp, a);
  784. BIO_puts(bp, " % ");
  785. BN_print(bp, b);
  786. BIO_puts(bp, " - ");
  787. }
  788. BN_print(bp, c);
  789. BIO_puts(bp, "\n");
  790. }
  791. BN_div(d, e, a, b, ctx);
  792. BN_sub(e, e, c);
  793. if (!BN_is_zero(e)) {
  794. fprintf(stderr, "Modulo test failed!\n");
  795. return 0;
  796. }
  797. }
  798. BN_free(a);
  799. BN_free(b);
  800. BN_free(c);
  801. BN_free(d);
  802. BN_free(e);
  803. return (1);
  804. }
  805. int test_mod_mul(BIO *bp, BN_CTX *ctx)
  806. {
  807. BIGNUM *a, *b, *c, *d, *e;
  808. int i, j;
  809. a = BN_new();
  810. b = BN_new();
  811. c = BN_new();
  812. d = BN_new();
  813. e = BN_new();
  814. BN_one(a);
  815. BN_one(b);
  816. BN_zero(c);
  817. if (BN_mod_mul(e, a, b, c, ctx)) {
  818. fprintf(stderr, "BN_mod_mul with zero modulus succeeded!\n");
  819. return 0;
  820. }
  821. for (j = 0; j < 3; j++) {
  822. BN_bntest_rand(c, 1024, 0, 0);
  823. for (i = 0; i < num0; i++) {
  824. BN_bntest_rand(a, 475 + i * 10, 0, 0);
  825. BN_bntest_rand(b, 425 + i * 11, 0, 0);
  826. a->neg = rand_neg();
  827. b->neg = rand_neg();
  828. if (!BN_mod_mul(e, a, b, c, ctx)) {
  829. unsigned long l;
  830. while ((l = ERR_get_error()))
  831. fprintf(stderr, "ERROR:%s\n", ERR_error_string(l, NULL));
  832. EXIT(1);
  833. }
  834. if (bp != NULL) {
  835. if (!results) {
  836. BN_print(bp, a);
  837. BIO_puts(bp, " * ");
  838. BN_print(bp, b);
  839. BIO_puts(bp, " % ");
  840. BN_print(bp, c);
  841. if ((a->neg ^ b->neg) && !BN_is_zero(e)) {
  842. /*
  843. * If (a*b) % c is negative, c must be added in order
  844. * to obtain the normalized remainder (new with
  845. * OpenSSL 0.9.7, previous versions of BN_mod_mul
  846. * could generate negative results)
  847. */
  848. BIO_puts(bp, " + ");
  849. BN_print(bp, c);
  850. }
  851. BIO_puts(bp, " - ");
  852. }
  853. BN_print(bp, e);
  854. BIO_puts(bp, "\n");
  855. }
  856. BN_mul(d, a, b, ctx);
  857. BN_sub(d, d, e);
  858. BN_div(a, b, d, c, ctx);
  859. if (!BN_is_zero(b)) {
  860. fprintf(stderr, "Modulo multiply test failed!\n");
  861. ERR_print_errors_fp(stderr);
  862. return 0;
  863. }
  864. }
  865. }
  866. BN_free(a);
  867. BN_free(b);
  868. BN_free(c);
  869. BN_free(d);
  870. BN_free(e);
  871. return (1);
  872. }
  873. int test_mod_exp(BIO *bp, BN_CTX *ctx)
  874. {
  875. BIGNUM *a, *b, *c, *d, *e;
  876. int i;
  877. a = BN_new();
  878. b = BN_new();
  879. c = BN_new();
  880. d = BN_new();
  881. e = BN_new();
  882. BN_one(a);
  883. BN_one(b);
  884. BN_zero(c);
  885. if (BN_mod_exp(d, a, b, c, ctx)) {
  886. fprintf(stderr, "BN_mod_exp with zero modulus succeeded!\n");
  887. return 0;
  888. }
  889. BN_bntest_rand(c, 30, 0, 1); /* must be odd for montgomery */
  890. for (i = 0; i < num2; i++) {
  891. BN_bntest_rand(a, 20 + i * 5, 0, 0);
  892. BN_bntest_rand(b, 2 + i, 0, 0);
  893. if (!BN_mod_exp(d, a, b, c, ctx))
  894. return (0);
  895. if (bp != NULL) {
  896. if (!results) {
  897. BN_print(bp, a);
  898. BIO_puts(bp, " ^ ");
  899. BN_print(bp, b);
  900. BIO_puts(bp, " % ");
  901. BN_print(bp, c);
  902. BIO_puts(bp, " - ");
  903. }
  904. BN_print(bp, d);
  905. BIO_puts(bp, "\n");
  906. }
  907. BN_exp(e, a, b, ctx);
  908. BN_sub(e, e, d);
  909. BN_div(a, b, e, c, ctx);
  910. if (!BN_is_zero(b)) {
  911. fprintf(stderr, "Modulo exponentiation test failed!\n");
  912. return 0;
  913. }
  914. }
  915. /* Regression test for carry propagation bug in sqr8x_reduction */
  916. BN_hex2bn(&a, "050505050505");
  917. BN_hex2bn(&b, "02");
  918. BN_hex2bn(&c,
  919. "4141414141414141414141274141414141414141414141414141414141414141"
  920. "4141414141414141414141414141414141414141414141414141414141414141"
  921. "4141414141414141414141800000000000000000000000000000000000000000"
  922. "0000000000000000000000000000000000000000000000000000000000000000"
  923. "0000000000000000000000000000000000000000000000000000000000000000"
  924. "0000000000000000000000000000000000000000000000000000000001");
  925. BN_mod_exp(d, a, b, c, ctx);
  926. BN_mul(e, a, a, ctx);
  927. if (BN_cmp(d, e)) {
  928. fprintf(stderr, "BN_mod_exp and BN_mul produce different results!\n");
  929. return 0;
  930. }
  931. BN_free(a);
  932. BN_free(b);
  933. BN_free(c);
  934. BN_free(d);
  935. BN_free(e);
  936. return (1);
  937. }
  938. int test_mod_exp_mont_consttime(BIO *bp, BN_CTX *ctx)
  939. {
  940. BIGNUM *a, *b, *c, *d, *e;
  941. int i;
  942. a = BN_new();
  943. b = BN_new();
  944. c = BN_new();
  945. d = BN_new();
  946. e = BN_new();
  947. BN_one(a);
  948. BN_one(b);
  949. BN_zero(c);
  950. if (BN_mod_exp_mont_consttime(d, a, b, c, ctx, NULL)) {
  951. fprintf(stderr, "BN_mod_exp_mont_consttime with zero modulus "
  952. "succeeded\n");
  953. return 0;
  954. }
  955. BN_set_word(c, 16);
  956. if (BN_mod_exp_mont_consttime(d, a, b, c, ctx, NULL)) {
  957. fprintf(stderr, "BN_mod_exp_mont_consttime with even modulus "
  958. "succeeded\n");
  959. return 0;
  960. }
  961. BN_bntest_rand(c, 30, 0, 1); /* must be odd for montgomery */
  962. for (i = 0; i < num2; i++) {
  963. BN_bntest_rand(a, 20 + i * 5, 0, 0);
  964. BN_bntest_rand(b, 2 + i, 0, 0);
  965. if (!BN_mod_exp_mont_consttime(d, a, b, c, ctx, NULL))
  966. return (00);
  967. if (bp != NULL) {
  968. if (!results) {
  969. BN_print(bp, a);
  970. BIO_puts(bp, " ^ ");
  971. BN_print(bp, b);
  972. BIO_puts(bp, " % ");
  973. BN_print(bp, c);
  974. BIO_puts(bp, " - ");
  975. }
  976. BN_print(bp, d);
  977. BIO_puts(bp, "\n");
  978. }
  979. BN_exp(e, a, b, ctx);
  980. BN_sub(e, e, d);
  981. BN_div(a, b, e, c, ctx);
  982. if (!BN_is_zero(b)) {
  983. fprintf(stderr, "Modulo exponentiation test failed!\n");
  984. return 0;
  985. }
  986. }
  987. BN_free(a);
  988. BN_free(b);
  989. BN_free(c);
  990. BN_free(d);
  991. BN_free(e);
  992. return (1);
  993. }
  994. /*
  995. * Test constant-time modular exponentiation with 1024-bit inputs, which on
  996. * x86_64 cause a different code branch to be taken.
  997. */
  998. int test_mod_exp_mont5(BIO *bp, BN_CTX *ctx)
  999. {
  1000. BIGNUM *a, *p, *m, *d, *e;
  1001. BN_MONT_CTX *mont;
  1002. a = BN_new();
  1003. p = BN_new();
  1004. m = BN_new();
  1005. d = BN_new();
  1006. e = BN_new();
  1007. mont = BN_MONT_CTX_new();
  1008. BN_bntest_rand(m, 1024, 0, 1); /* must be odd for montgomery */
  1009. /* Zero exponent */
  1010. BN_bntest_rand(a, 1024, 0, 0);
  1011. BN_zero(p);
  1012. if (!BN_mod_exp_mont_consttime(d, a, p, m, ctx, NULL))
  1013. return 0;
  1014. if (!BN_is_one(d)) {
  1015. fprintf(stderr, "Modular exponentiation test failed!\n");
  1016. return 0;
  1017. }
  1018. /* Zero input */
  1019. BN_bntest_rand(p, 1024, 0, 0);
  1020. BN_zero(a);
  1021. if (!BN_mod_exp_mont_consttime(d, a, p, m, ctx, NULL))
  1022. return 0;
  1023. if (!BN_is_zero(d)) {
  1024. fprintf(stderr, "Modular exponentiation test failed!\n");
  1025. return 0;
  1026. }
  1027. /*
  1028. * Craft an input whose Montgomery representation is 1, i.e., shorter
  1029. * than the modulus m, in order to test the const time precomputation
  1030. * scattering/gathering.
  1031. */
  1032. BN_one(a);
  1033. BN_MONT_CTX_set(mont, m, ctx);
  1034. if (!BN_from_montgomery(e, a, mont, ctx))
  1035. return 0;
  1036. if (!BN_mod_exp_mont_consttime(d, e, p, m, ctx, NULL))
  1037. return 0;
  1038. if (!BN_mod_exp_simple(a, e, p, m, ctx))
  1039. return 0;
  1040. if (BN_cmp(a, d) != 0) {
  1041. fprintf(stderr, "Modular exponentiation test failed!\n");
  1042. return 0;
  1043. }
  1044. /* Finally, some regular test vectors. */
  1045. BN_bntest_rand(e, 1024, 0, 0);
  1046. if (!BN_mod_exp_mont_consttime(d, e, p, m, ctx, NULL))
  1047. return 0;
  1048. if (!BN_mod_exp_simple(a, e, p, m, ctx))
  1049. return 0;
  1050. if (BN_cmp(a, d) != 0) {
  1051. fprintf(stderr, "Modular exponentiation test failed!\n");
  1052. return 0;
  1053. }
  1054. BN_MONT_CTX_free(mont);
  1055. BN_free(a);
  1056. BN_free(p);
  1057. BN_free(m);
  1058. BN_free(d);
  1059. BN_free(e);
  1060. return (1);
  1061. }
  1062. int test_exp(BIO *bp, BN_CTX *ctx)
  1063. {
  1064. BIGNUM *a, *b, *d, *e, *one;
  1065. int i;
  1066. a = BN_new();
  1067. b = BN_new();
  1068. d = BN_new();
  1069. e = BN_new();
  1070. one = BN_new();
  1071. BN_one(one);
  1072. for (i = 0; i < num2; i++) {
  1073. BN_bntest_rand(a, 20 + i * 5, 0, 0);
  1074. BN_bntest_rand(b, 2 + i, 0, 0);
  1075. if (BN_exp(d, a, b, ctx) <= 0)
  1076. return (0);
  1077. if (bp != NULL) {
  1078. if (!results) {
  1079. BN_print(bp, a);
  1080. BIO_puts(bp, " ^ ");
  1081. BN_print(bp, b);
  1082. BIO_puts(bp, " - ");
  1083. }
  1084. BN_print(bp, d);
  1085. BIO_puts(bp, "\n");
  1086. }
  1087. BN_one(e);
  1088. for (; !BN_is_zero(b); BN_sub(b, b, one))
  1089. BN_mul(e, e, a, ctx);
  1090. BN_sub(e, e, d);
  1091. if (!BN_is_zero(e)) {
  1092. fprintf(stderr, "Exponentiation test failed!\n");
  1093. return 0;
  1094. }
  1095. }
  1096. BN_free(a);
  1097. BN_free(b);
  1098. BN_free(d);
  1099. BN_free(e);
  1100. BN_free(one);
  1101. return (1);
  1102. }
  1103. #ifndef OPENSSL_NO_EC2M
  1104. int test_gf2m_add(BIO *bp)
  1105. {
  1106. BIGNUM *a, *b, *c;
  1107. int i, ret = 0;
  1108. a = BN_new();
  1109. b = BN_new();
  1110. c = BN_new();
  1111. for (i = 0; i < num0; i++) {
  1112. BN_rand(a, 512, 0, 0);
  1113. BN_copy(b, BN_value_one());
  1114. a->neg = rand_neg();
  1115. b->neg = rand_neg();
  1116. BN_GF2m_add(c, a, b);
  1117. /* Test that two added values have the correct parity. */
  1118. if ((BN_is_odd(a) && BN_is_odd(c))
  1119. || (!BN_is_odd(a) && !BN_is_odd(c))) {
  1120. fprintf(stderr, "GF(2^m) addition test (a) failed!\n");
  1121. goto err;
  1122. }
  1123. BN_GF2m_add(c, c, c);
  1124. /* Test that c + c = 0. */
  1125. if (!BN_is_zero(c)) {
  1126. fprintf(stderr, "GF(2^m) addition test (b) failed!\n");
  1127. goto err;
  1128. }
  1129. }
  1130. ret = 1;
  1131. err:
  1132. BN_free(a);
  1133. BN_free(b);
  1134. BN_free(c);
  1135. return ret;
  1136. }
  1137. int test_gf2m_mod(BIO *bp)
  1138. {
  1139. BIGNUM *a, *b[2], *c, *d, *e;
  1140. int i, j, ret = 0;
  1141. int p0[] = { 163, 7, 6, 3, 0, -1 };
  1142. int p1[] = { 193, 15, 0, -1 };
  1143. a = BN_new();
  1144. b[0] = BN_new();
  1145. b[1] = BN_new();
  1146. c = BN_new();
  1147. d = BN_new();
  1148. e = BN_new();
  1149. BN_GF2m_arr2poly(p0, b[0]);
  1150. BN_GF2m_arr2poly(p1, b[1]);
  1151. for (i = 0; i < num0; i++) {
  1152. BN_bntest_rand(a, 1024, 0, 0);
  1153. for (j = 0; j < 2; j++) {
  1154. BN_GF2m_mod(c, a, b[j]);
  1155. BN_GF2m_add(d, a, c);
  1156. BN_GF2m_mod(e, d, b[j]);
  1157. /* Test that a + (a mod p) mod p == 0. */
  1158. if (!BN_is_zero(e)) {
  1159. fprintf(stderr, "GF(2^m) modulo test failed!\n");
  1160. goto err;
  1161. }
  1162. }
  1163. }
  1164. ret = 1;
  1165. err:
  1166. BN_free(a);
  1167. BN_free(b[0]);
  1168. BN_free(b[1]);
  1169. BN_free(c);
  1170. BN_free(d);
  1171. BN_free(e);
  1172. return ret;
  1173. }
  1174. int test_gf2m_mod_mul(BIO *bp, BN_CTX *ctx)
  1175. {
  1176. BIGNUM *a, *b[2], *c, *d, *e, *f, *g, *h;
  1177. int i, j, ret = 0;
  1178. int p0[] = { 163, 7, 6, 3, 0, -1 };
  1179. int p1[] = { 193, 15, 0, -1 };
  1180. a = BN_new();
  1181. b[0] = BN_new();
  1182. b[1] = BN_new();
  1183. c = BN_new();
  1184. d = BN_new();
  1185. e = BN_new();
  1186. f = BN_new();
  1187. g = BN_new();
  1188. h = BN_new();
  1189. BN_GF2m_arr2poly(p0, b[0]);
  1190. BN_GF2m_arr2poly(p1, b[1]);
  1191. for (i = 0; i < num0; i++) {
  1192. BN_bntest_rand(a, 1024, 0, 0);
  1193. BN_bntest_rand(c, 1024, 0, 0);
  1194. BN_bntest_rand(d, 1024, 0, 0);
  1195. for (j = 0; j < 2; j++) {
  1196. BN_GF2m_mod_mul(e, a, c, b[j], ctx);
  1197. BN_GF2m_add(f, a, d);
  1198. BN_GF2m_mod_mul(g, f, c, b[j], ctx);
  1199. BN_GF2m_mod_mul(h, d, c, b[j], ctx);
  1200. BN_GF2m_add(f, e, g);
  1201. BN_GF2m_add(f, f, h);
  1202. /* Test that (a+d)*c = a*c + d*c. */
  1203. if (!BN_is_zero(f)) {
  1204. fprintf(stderr,
  1205. "GF(2^m) modular multiplication test failed!\n");
  1206. goto err;
  1207. }
  1208. }
  1209. }
  1210. ret = 1;
  1211. err:
  1212. BN_free(a);
  1213. BN_free(b[0]);
  1214. BN_free(b[1]);
  1215. BN_free(c);
  1216. BN_free(d);
  1217. BN_free(e);
  1218. BN_free(f);
  1219. BN_free(g);
  1220. BN_free(h);
  1221. return ret;
  1222. }
  1223. int test_gf2m_mod_sqr(BIO *bp, BN_CTX *ctx)
  1224. {
  1225. BIGNUM *a, *b[2], *c, *d;
  1226. int i, j, ret = 0;
  1227. int p0[] = { 163, 7, 6, 3, 0, -1 };
  1228. int p1[] = { 193, 15, 0, -1 };
  1229. a = BN_new();
  1230. b[0] = BN_new();
  1231. b[1] = BN_new();
  1232. c = BN_new();
  1233. d = BN_new();
  1234. BN_GF2m_arr2poly(p0, b[0]);
  1235. BN_GF2m_arr2poly(p1, b[1]);
  1236. for (i = 0; i < num0; i++) {
  1237. BN_bntest_rand(a, 1024, 0, 0);
  1238. for (j = 0; j < 2; j++) {
  1239. BN_GF2m_mod_sqr(c, a, b[j], ctx);
  1240. BN_copy(d, a);
  1241. BN_GF2m_mod_mul(d, a, d, b[j], ctx);
  1242. BN_GF2m_add(d, c, d);
  1243. /* Test that a*a = a^2. */
  1244. if (!BN_is_zero(d)) {
  1245. fprintf(stderr, "GF(2^m) modular squaring test failed!\n");
  1246. goto err;
  1247. }
  1248. }
  1249. }
  1250. ret = 1;
  1251. err:
  1252. BN_free(a);
  1253. BN_free(b[0]);
  1254. BN_free(b[1]);
  1255. BN_free(c);
  1256. BN_free(d);
  1257. return ret;
  1258. }
  1259. int test_gf2m_mod_inv(BIO *bp, BN_CTX *ctx)
  1260. {
  1261. BIGNUM *a, *b[2], *c, *d;
  1262. int i, j, ret = 0;
  1263. int p0[] = { 163, 7, 6, 3, 0, -1 };
  1264. int p1[] = { 193, 15, 0, -1 };
  1265. a = BN_new();
  1266. b[0] = BN_new();
  1267. b[1] = BN_new();
  1268. c = BN_new();
  1269. d = BN_new();
  1270. BN_GF2m_arr2poly(p0, b[0]);
  1271. BN_GF2m_arr2poly(p1, b[1]);
  1272. for (i = 0; i < num0; i++) {
  1273. BN_bntest_rand(a, 512, 0, 0);
  1274. for (j = 0; j < 2; j++) {
  1275. BN_GF2m_mod_inv(c, a, b[j], ctx);
  1276. BN_GF2m_mod_mul(d, a, c, b[j], ctx);
  1277. /* Test that ((1/a)*a) = 1. */
  1278. if (!BN_is_one(d)) {
  1279. fprintf(stderr, "GF(2^m) modular inversion test failed!\n");
  1280. goto err;
  1281. }
  1282. }
  1283. }
  1284. ret = 1;
  1285. err:
  1286. BN_free(a);
  1287. BN_free(b[0]);
  1288. BN_free(b[1]);
  1289. BN_free(c);
  1290. BN_free(d);
  1291. return ret;
  1292. }
  1293. int test_gf2m_mod_div(BIO *bp, BN_CTX *ctx)
  1294. {
  1295. BIGNUM *a, *b[2], *c, *d, *e, *f;
  1296. int i, j, ret = 0;
  1297. int p0[] = { 163, 7, 6, 3, 0, -1 };
  1298. int p1[] = { 193, 15, 0, -1 };
  1299. a = BN_new();
  1300. b[0] = BN_new();
  1301. b[1] = BN_new();
  1302. c = BN_new();
  1303. d = BN_new();
  1304. e = BN_new();
  1305. f = BN_new();
  1306. BN_GF2m_arr2poly(p0, b[0]);
  1307. BN_GF2m_arr2poly(p1, b[1]);
  1308. for (i = 0; i < num0; i++) {
  1309. BN_bntest_rand(a, 512, 0, 0);
  1310. BN_bntest_rand(c, 512, 0, 0);
  1311. for (j = 0; j < 2; j++) {
  1312. BN_GF2m_mod_div(d, a, c, b[j], ctx);
  1313. BN_GF2m_mod_mul(e, d, c, b[j], ctx);
  1314. BN_GF2m_mod_div(f, a, e, b[j], ctx);
  1315. /* Test that ((a/c)*c)/a = 1. */
  1316. if (!BN_is_one(f)) {
  1317. fprintf(stderr, "GF(2^m) modular division test failed!\n");
  1318. goto err;
  1319. }
  1320. }
  1321. }
  1322. ret = 1;
  1323. err:
  1324. BN_free(a);
  1325. BN_free(b[0]);
  1326. BN_free(b[1]);
  1327. BN_free(c);
  1328. BN_free(d);
  1329. BN_free(e);
  1330. BN_free(f);
  1331. return ret;
  1332. }
  1333. int test_gf2m_mod_exp(BIO *bp, BN_CTX *ctx)
  1334. {
  1335. BIGNUM *a, *b[2], *c, *d, *e, *f;
  1336. int i, j, ret = 0;
  1337. int p0[] = { 163, 7, 6, 3, 0, -1 };
  1338. int p1[] = { 193, 15, 0, -1 };
  1339. a = BN_new();
  1340. b[0] = BN_new();
  1341. b[1] = BN_new();
  1342. c = BN_new();
  1343. d = BN_new();
  1344. e = BN_new();
  1345. f = BN_new();
  1346. BN_GF2m_arr2poly(p0, b[0]);
  1347. BN_GF2m_arr2poly(p1, b[1]);
  1348. for (i = 0; i < num0; i++) {
  1349. BN_bntest_rand(a, 512, 0, 0);
  1350. BN_bntest_rand(c, 512, 0, 0);
  1351. BN_bntest_rand(d, 512, 0, 0);
  1352. for (j = 0; j < 2; j++) {
  1353. BN_GF2m_mod_exp(e, a, c, b[j], ctx);
  1354. BN_GF2m_mod_exp(f, a, d, b[j], ctx);
  1355. BN_GF2m_mod_mul(e, e, f, b[j], ctx);
  1356. BN_add(f, c, d);
  1357. BN_GF2m_mod_exp(f, a, f, b[j], ctx);
  1358. BN_GF2m_add(f, e, f);
  1359. /* Test that a^(c+d)=a^c*a^d. */
  1360. if (!BN_is_zero(f)) {
  1361. fprintf(stderr,
  1362. "GF(2^m) modular exponentiation test failed!\n");
  1363. goto err;
  1364. }
  1365. }
  1366. }
  1367. ret = 1;
  1368. err:
  1369. BN_free(a);
  1370. BN_free(b[0]);
  1371. BN_free(b[1]);
  1372. BN_free(c);
  1373. BN_free(d);
  1374. BN_free(e);
  1375. BN_free(f);
  1376. return ret;
  1377. }
  1378. int test_gf2m_mod_sqrt(BIO *bp, BN_CTX *ctx)
  1379. {
  1380. BIGNUM *a, *b[2], *c, *d, *e, *f;
  1381. int i, j, ret = 0;
  1382. int p0[] = { 163, 7, 6, 3, 0, -1 };
  1383. int p1[] = { 193, 15, 0, -1 };
  1384. a = BN_new();
  1385. b[0] = BN_new();
  1386. b[1] = BN_new();
  1387. c = BN_new();
  1388. d = BN_new();
  1389. e = BN_new();
  1390. f = BN_new();
  1391. BN_GF2m_arr2poly(p0, b[0]);
  1392. BN_GF2m_arr2poly(p1, b[1]);
  1393. for (i = 0; i < num0; i++) {
  1394. BN_bntest_rand(a, 512, 0, 0);
  1395. for (j = 0; j < 2; j++) {
  1396. BN_GF2m_mod(c, a, b[j]);
  1397. BN_GF2m_mod_sqrt(d, a, b[j], ctx);
  1398. BN_GF2m_mod_sqr(e, d, b[j], ctx);
  1399. BN_GF2m_add(f, c, e);
  1400. /* Test that d^2 = a, where d = sqrt(a). */
  1401. if (!BN_is_zero(f)) {
  1402. fprintf(stderr, "GF(2^m) modular square root test failed!\n");
  1403. goto err;
  1404. }
  1405. }
  1406. }
  1407. ret = 1;
  1408. err:
  1409. BN_free(a);
  1410. BN_free(b[0]);
  1411. BN_free(b[1]);
  1412. BN_free(c);
  1413. BN_free(d);
  1414. BN_free(e);
  1415. BN_free(f);
  1416. return ret;
  1417. }
  1418. int test_gf2m_mod_solve_quad(BIO *bp, BN_CTX *ctx)
  1419. {
  1420. BIGNUM *a, *b[2], *c, *d, *e;
  1421. int i, j, s = 0, t, ret = 0;
  1422. int p0[] = { 163, 7, 6, 3, 0, -1 };
  1423. int p1[] = { 193, 15, 0, -1 };
  1424. a = BN_new();
  1425. b[0] = BN_new();
  1426. b[1] = BN_new();
  1427. c = BN_new();
  1428. d = BN_new();
  1429. e = BN_new();
  1430. BN_GF2m_arr2poly(p0, b[0]);
  1431. BN_GF2m_arr2poly(p1, b[1]);
  1432. for (i = 0; i < num0; i++) {
  1433. BN_bntest_rand(a, 512, 0, 0);
  1434. for (j = 0; j < 2; j++) {
  1435. t = BN_GF2m_mod_solve_quad(c, a, b[j], ctx);
  1436. if (t) {
  1437. s++;
  1438. BN_GF2m_mod_sqr(d, c, b[j], ctx);
  1439. BN_GF2m_add(d, c, d);
  1440. BN_GF2m_mod(e, a, b[j]);
  1441. BN_GF2m_add(e, e, d);
  1442. /*
  1443. * Test that solution of quadratic c satisfies c^2 + c = a.
  1444. */
  1445. if (!BN_is_zero(e)) {
  1446. fprintf(stderr,
  1447. "GF(2^m) modular solve quadratic test failed!\n");
  1448. goto err;
  1449. }
  1450. }
  1451. }
  1452. }
  1453. if (s == 0) {
  1454. fprintf(stderr,
  1455. "All %i tests of GF(2^m) modular solve quadratic resulted in no roots;\n",
  1456. num0);
  1457. fprintf(stderr,
  1458. "this is very unlikely and probably indicates an error.\n");
  1459. goto err;
  1460. }
  1461. ret = 1;
  1462. err:
  1463. BN_free(a);
  1464. BN_free(b[0]);
  1465. BN_free(b[1]);
  1466. BN_free(c);
  1467. BN_free(d);
  1468. BN_free(e);
  1469. return ret;
  1470. }
  1471. #endif
  1472. static int genprime_cb(int p, int n, BN_GENCB *arg)
  1473. {
  1474. char c = '*';
  1475. if (p == 0)
  1476. c = '.';
  1477. if (p == 1)
  1478. c = '+';
  1479. if (p == 2)
  1480. c = '*';
  1481. if (p == 3)
  1482. c = '\n';
  1483. putc(c, stderr);
  1484. fflush(stderr);
  1485. return 1;
  1486. }
  1487. int test_kron(BIO *bp, BN_CTX *ctx)
  1488. {
  1489. BN_GENCB cb;
  1490. BIGNUM *a, *b, *r, *t;
  1491. int i;
  1492. int legendre, kronecker;
  1493. int ret = 0;
  1494. a = BN_new();
  1495. b = BN_new();
  1496. r = BN_new();
  1497. t = BN_new();
  1498. if (a == NULL || b == NULL || r == NULL || t == NULL)
  1499. goto err;
  1500. BN_GENCB_set(&cb, genprime_cb, NULL);
  1501. /*
  1502. * We test BN_kronecker(a, b, ctx) just for b odd (Jacobi symbol). In
  1503. * this case we know that if b is prime, then BN_kronecker(a, b, ctx) is
  1504. * congruent to $a^{(b-1)/2}$, modulo $b$ (Legendre symbol). So we
  1505. * generate a random prime b and compare these values for a number of
  1506. * random a's. (That is, we run the Solovay-Strassen primality test to
  1507. * confirm that b is prime, except that we don't want to test whether b
  1508. * is prime but whether BN_kronecker works.)
  1509. */
  1510. if (!BN_generate_prime_ex(b, 512, 0, NULL, NULL, &cb))
  1511. goto err;
  1512. b->neg = rand_neg();
  1513. putc('\n', stderr);
  1514. for (i = 0; i < num0; i++) {
  1515. if (!BN_bntest_rand(a, 512, 0, 0))
  1516. goto err;
  1517. a->neg = rand_neg();
  1518. /* t := (|b|-1)/2 (note that b is odd) */
  1519. if (!BN_copy(t, b))
  1520. goto err;
  1521. t->neg = 0;
  1522. if (!BN_sub_word(t, 1))
  1523. goto err;
  1524. if (!BN_rshift1(t, t))
  1525. goto err;
  1526. /* r := a^t mod b */
  1527. b->neg = 0;
  1528. if (!BN_mod_exp_recp(r, a, t, b, ctx))
  1529. goto err;
  1530. b->neg = 1;
  1531. if (BN_is_word(r, 1))
  1532. legendre = 1;
  1533. else if (BN_is_zero(r))
  1534. legendre = 0;
  1535. else {
  1536. if (!BN_add_word(r, 1))
  1537. goto err;
  1538. if (0 != BN_ucmp(r, b)) {
  1539. fprintf(stderr, "Legendre symbol computation failed\n");
  1540. goto err;
  1541. }
  1542. legendre = -1;
  1543. }
  1544. kronecker = BN_kronecker(a, b, ctx);
  1545. if (kronecker < -1)
  1546. goto err;
  1547. /* we actually need BN_kronecker(a, |b|) */
  1548. if (a->neg && b->neg)
  1549. kronecker = -kronecker;
  1550. if (legendre != kronecker) {
  1551. fprintf(stderr, "legendre != kronecker; a = ");
  1552. BN_print_fp(stderr, a);
  1553. fprintf(stderr, ", b = ");
  1554. BN_print_fp(stderr, b);
  1555. fprintf(stderr, "\n");
  1556. goto err;
  1557. }
  1558. putc('.', stderr);
  1559. fflush(stderr);
  1560. }
  1561. putc('\n', stderr);
  1562. fflush(stderr);
  1563. ret = 1;
  1564. err:
  1565. BN_free(a);
  1566. BN_free(b);
  1567. BN_free(r);
  1568. BN_free(t);
  1569. return ret;
  1570. }
  1571. int test_sqrt(BIO *bp, BN_CTX *ctx)
  1572. {
  1573. BN_GENCB cb;
  1574. BIGNUM *a, *p, *r;
  1575. int i, j;
  1576. int ret = 0;
  1577. a = BN_new();
  1578. p = BN_new();
  1579. r = BN_new();
  1580. if (a == NULL || p == NULL || r == NULL)
  1581. goto err;
  1582. BN_GENCB_set(&cb, genprime_cb, NULL);
  1583. for (i = 0; i < 16; i++) {
  1584. if (i < 8) {
  1585. unsigned primes[8] = { 2, 3, 5, 7, 11, 13, 17, 19 };
  1586. if (!BN_set_word(p, primes[i]))
  1587. goto err;
  1588. } else {
  1589. if (!BN_set_word(a, 32))
  1590. goto err;
  1591. if (!BN_set_word(r, 2 * i + 1))
  1592. goto err;
  1593. if (!BN_generate_prime_ex(p, 256, 0, a, r, &cb))
  1594. goto err;
  1595. putc('\n', stderr);
  1596. }
  1597. p->neg = rand_neg();
  1598. for (j = 0; j < num2; j++) {
  1599. /*
  1600. * construct 'a' such that it is a square modulo p, but in
  1601. * general not a proper square and not reduced modulo p
  1602. */
  1603. if (!BN_bntest_rand(r, 256, 0, 3))
  1604. goto err;
  1605. if (!BN_nnmod(r, r, p, ctx))
  1606. goto err;
  1607. if (!BN_mod_sqr(r, r, p, ctx))
  1608. goto err;
  1609. if (!BN_bntest_rand(a, 256, 0, 3))
  1610. goto err;
  1611. if (!BN_nnmod(a, a, p, ctx))
  1612. goto err;
  1613. if (!BN_mod_sqr(a, a, p, ctx))
  1614. goto err;
  1615. if (!BN_mul(a, a, r, ctx))
  1616. goto err;
  1617. if (rand_neg())
  1618. if (!BN_sub(a, a, p))
  1619. goto err;
  1620. if (!BN_mod_sqrt(r, a, p, ctx))
  1621. goto err;
  1622. if (!BN_mod_sqr(r, r, p, ctx))
  1623. goto err;
  1624. if (!BN_nnmod(a, a, p, ctx))
  1625. goto err;
  1626. if (BN_cmp(a, r) != 0) {
  1627. fprintf(stderr, "BN_mod_sqrt failed: a = ");
  1628. BN_print_fp(stderr, a);
  1629. fprintf(stderr, ", r = ");
  1630. BN_print_fp(stderr, r);
  1631. fprintf(stderr, ", p = ");
  1632. BN_print_fp(stderr, p);
  1633. fprintf(stderr, "\n");
  1634. goto err;
  1635. }
  1636. putc('.', stderr);
  1637. fflush(stderr);
  1638. }
  1639. putc('\n', stderr);
  1640. fflush(stderr);
  1641. }
  1642. ret = 1;
  1643. err:
  1644. BN_free(a);
  1645. BN_free(p);
  1646. BN_free(r);
  1647. return ret;
  1648. }
  1649. int test_small_prime(BIO *bp, BN_CTX *ctx)
  1650. {
  1651. static const int bits = 10;
  1652. int ret = 0;
  1653. BIGNUM *r;
  1654. r = BN_new();
  1655. if (!BN_generate_prime_ex(r, bits, 0, NULL, NULL, NULL))
  1656. goto err;
  1657. if (BN_num_bits(r) != bits) {
  1658. BIO_printf(bp, "Expected %d bit prime, got %d bit number\n", bits,
  1659. BN_num_bits(r));
  1660. goto err;
  1661. }
  1662. ret = 1;
  1663. err:
  1664. BN_clear_free(r);
  1665. return ret;
  1666. }
  1667. int test_lshift(BIO *bp, BN_CTX *ctx, BIGNUM *a_)
  1668. {
  1669. BIGNUM *a, *b, *c, *d;
  1670. int i;
  1671. b = BN_new();
  1672. c = BN_new();
  1673. d = BN_new();
  1674. BN_one(c);
  1675. if (a_)
  1676. a = a_;
  1677. else {
  1678. a = BN_new();
  1679. BN_bntest_rand(a, 200, 0, 0);
  1680. a->neg = rand_neg();
  1681. }
  1682. for (i = 0; i < num0; i++) {
  1683. BN_lshift(b, a, i + 1);
  1684. BN_add(c, c, c);
  1685. if (bp != NULL) {
  1686. if (!results) {
  1687. BN_print(bp, a);
  1688. BIO_puts(bp, " * ");
  1689. BN_print(bp, c);
  1690. BIO_puts(bp, " - ");
  1691. }
  1692. BN_print(bp, b);
  1693. BIO_puts(bp, "\n");
  1694. }
  1695. BN_mul(d, a, c, ctx);
  1696. BN_sub(d, d, b);
  1697. if (!BN_is_zero(d)) {
  1698. fprintf(stderr, "Left shift test failed!\n");
  1699. fprintf(stderr, "a=");
  1700. BN_print_fp(stderr, a);
  1701. fprintf(stderr, "\nb=");
  1702. BN_print_fp(stderr, b);
  1703. fprintf(stderr, "\nc=");
  1704. BN_print_fp(stderr, c);
  1705. fprintf(stderr, "\nd=");
  1706. BN_print_fp(stderr, d);
  1707. fprintf(stderr, "\n");
  1708. return 0;
  1709. }
  1710. }
  1711. BN_free(a);
  1712. BN_free(b);
  1713. BN_free(c);
  1714. BN_free(d);
  1715. return (1);
  1716. }
  1717. int test_lshift1(BIO *bp)
  1718. {
  1719. BIGNUM *a, *b, *c;
  1720. int i;
  1721. a = BN_new();
  1722. b = BN_new();
  1723. c = BN_new();
  1724. BN_bntest_rand(a, 200, 0, 0);
  1725. a->neg = rand_neg();
  1726. for (i = 0; i < num0; i++) {
  1727. BN_lshift1(b, a);
  1728. if (bp != NULL) {
  1729. if (!results) {
  1730. BN_print(bp, a);
  1731. BIO_puts(bp, " * 2");
  1732. BIO_puts(bp, " - ");
  1733. }
  1734. BN_print(bp, b);
  1735. BIO_puts(bp, "\n");
  1736. }
  1737. BN_add(c, a, a);
  1738. BN_sub(a, b, c);
  1739. if (!BN_is_zero(a)) {
  1740. fprintf(stderr, "Left shift one test failed!\n");
  1741. return 0;
  1742. }
  1743. BN_copy(a, b);
  1744. }
  1745. BN_free(a);
  1746. BN_free(b);
  1747. BN_free(c);
  1748. return (1);
  1749. }
  1750. int test_rshift(BIO *bp, BN_CTX *ctx)
  1751. {
  1752. BIGNUM *a, *b, *c, *d, *e;
  1753. int i;
  1754. a = BN_new();
  1755. b = BN_new();
  1756. c = BN_new();
  1757. d = BN_new();
  1758. e = BN_new();
  1759. BN_one(c);
  1760. BN_bntest_rand(a, 200, 0, 0);
  1761. a->neg = rand_neg();
  1762. for (i = 0; i < num0; i++) {
  1763. BN_rshift(b, a, i + 1);
  1764. BN_add(c, c, c);
  1765. if (bp != NULL) {
  1766. if (!results) {
  1767. BN_print(bp, a);
  1768. BIO_puts(bp, " / ");
  1769. BN_print(bp, c);
  1770. BIO_puts(bp, " - ");
  1771. }
  1772. BN_print(bp, b);
  1773. BIO_puts(bp, "\n");
  1774. }
  1775. BN_div(d, e, a, c, ctx);
  1776. BN_sub(d, d, b);
  1777. if (!BN_is_zero(d)) {
  1778. fprintf(stderr, "Right shift test failed!\n");
  1779. return 0;
  1780. }
  1781. }
  1782. BN_free(a);
  1783. BN_free(b);
  1784. BN_free(c);
  1785. BN_free(d);
  1786. BN_free(e);
  1787. return (1);
  1788. }
  1789. int test_rshift1(BIO *bp)
  1790. {
  1791. BIGNUM *a, *b, *c;
  1792. int i;
  1793. a = BN_new();
  1794. b = BN_new();
  1795. c = BN_new();
  1796. BN_bntest_rand(a, 200, 0, 0);
  1797. a->neg = rand_neg();
  1798. for (i = 0; i < num0; i++) {
  1799. BN_rshift1(b, a);
  1800. if (bp != NULL) {
  1801. if (!results) {
  1802. BN_print(bp, a);
  1803. BIO_puts(bp, " / 2");
  1804. BIO_puts(bp, " - ");
  1805. }
  1806. BN_print(bp, b);
  1807. BIO_puts(bp, "\n");
  1808. }
  1809. BN_sub(c, a, b);
  1810. BN_sub(c, c, b);
  1811. if (!BN_is_zero(c) && !BN_abs_is_word(c, 1)) {
  1812. fprintf(stderr, "Right shift one test failed!\n");
  1813. return 0;
  1814. }
  1815. BN_copy(a, b);
  1816. }
  1817. BN_free(a);
  1818. BN_free(b);
  1819. BN_free(c);
  1820. return (1);
  1821. }
  1822. int rand_neg(void)
  1823. {
  1824. static unsigned int neg = 0;
  1825. static int sign[8] = { 0, 0, 0, 1, 1, 0, 1, 1 };
  1826. return (sign[(neg++) % 8]);
  1827. }