bn_lib.c 21 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602603604605606607608609610611612613614615616617618619620621622623624625626627628629630631632633634635636637638639640641642643644645646647648649650651652653654655656657658659660661662663664665666667668669670671672673674675676677678679680681682683684685686687688689690691692693694695696697698699700701702703704705706707708709710711712713714715716717718719720721722723724725726727728729730731732733734735736737738739740741742743744745746747748749750751752753754755756757758759760761762763764765766767768769770771772773774775776777778779780781782783784785786787788789790791792793794795796797798799800801802803804805806807808809810811812813814815816817818819820821822823824825826827828829830831832833834835836837838839840841842843844845846847848849850851852853854
  1. /* crypto/bn/bn_lib.c */
  2. /* Copyright (C) 1995-1998 Eric Young (eay@cryptsoft.com)
  3. * All rights reserved.
  4. *
  5. * This package is an SSL implementation written
  6. * by Eric Young (eay@cryptsoft.com).
  7. * The implementation was written so as to conform with Netscapes SSL.
  8. *
  9. * This library is free for commercial and non-commercial use as long as
  10. * the following conditions are aheared to. The following conditions
  11. * apply to all code found in this distribution, be it the RC4, RSA,
  12. * lhash, DES, etc., code; not just the SSL code. The SSL documentation
  13. * included with this distribution is covered by the same copyright terms
  14. * except that the holder is Tim Hudson (tjh@cryptsoft.com).
  15. *
  16. * Copyright remains Eric Young's, and as such any Copyright notices in
  17. * the code are not to be removed.
  18. * If this package is used in a product, Eric Young should be given attribution
  19. * as the author of the parts of the library used.
  20. * This can be in the form of a textual message at program startup or
  21. * in documentation (online or textual) provided with the package.
  22. *
  23. * Redistribution and use in source and binary forms, with or without
  24. * modification, are permitted provided that the following conditions
  25. * are met:
  26. * 1. Redistributions of source code must retain the copyright
  27. * notice, this list of conditions and the following disclaimer.
  28. * 2. Redistributions in binary form must reproduce the above copyright
  29. * notice, this list of conditions and the following disclaimer in the
  30. * documentation and/or other materials provided with the distribution.
  31. * 3. All advertising materials mentioning features or use of this software
  32. * must display the following acknowledgement:
  33. * "This product includes cryptographic software written by
  34. * Eric Young (eay@cryptsoft.com)"
  35. * The word 'cryptographic' can be left out if the rouines from the library
  36. * being used are not cryptographic related :-).
  37. * 4. If you include any Windows specific code (or a derivative thereof) from
  38. * the apps directory (application code) you must include an acknowledgement:
  39. * "This product includes software written by Tim Hudson (tjh@cryptsoft.com)"
  40. *
  41. * THIS SOFTWARE IS PROVIDED BY ERIC YOUNG ``AS IS'' AND
  42. * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  43. * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  44. * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
  45. * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  46. * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
  47. * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  48. * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  49. * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
  50. * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  51. * SUCH DAMAGE.
  52. *
  53. * The licence and distribution terms for any publically available version or
  54. * derivative of this code cannot be changed. i.e. this code cannot simply be
  55. * copied and put under another distribution licence
  56. * [including the GNU Public Licence.]
  57. */
  58. #ifndef BN_DEBUG
  59. # undef NDEBUG /* avoid conflicting definitions */
  60. # define NDEBUG
  61. #endif
  62. #include <assert.h>
  63. #include <limits.h>
  64. #include <stdio.h>
  65. #include "cryptlib.h"
  66. #include "bn_lcl.h"
  67. const char BN_version[] = "Big Number" OPENSSL_VERSION_PTEXT;
  68. /* This stuff appears to be completely unused, so is deprecated */
  69. #ifndef OPENSSL_NO_DEPRECATED
  70. /*-
  71. * For a 32 bit machine
  72. * 2 - 4 == 128
  73. * 3 - 8 == 256
  74. * 4 - 16 == 512
  75. * 5 - 32 == 1024
  76. * 6 - 64 == 2048
  77. * 7 - 128 == 4096
  78. * 8 - 256 == 8192
  79. */
  80. static int bn_limit_bits = 0;
  81. static int bn_limit_num = 8; /* (1<<bn_limit_bits) */
  82. static int bn_limit_bits_low = 0;
  83. static int bn_limit_num_low = 8; /* (1<<bn_limit_bits_low) */
  84. static int bn_limit_bits_high = 0;
  85. static int bn_limit_num_high = 8; /* (1<<bn_limit_bits_high) */
  86. static int bn_limit_bits_mont = 0;
  87. static int bn_limit_num_mont = 8; /* (1<<bn_limit_bits_mont) */
  88. void BN_set_params(int mult, int high, int low, int mont)
  89. {
  90. if (mult >= 0) {
  91. if (mult > (int)(sizeof(int) * 8) - 1)
  92. mult = sizeof(int) * 8 - 1;
  93. bn_limit_bits = mult;
  94. bn_limit_num = 1 << mult;
  95. }
  96. if (high >= 0) {
  97. if (high > (int)(sizeof(int) * 8) - 1)
  98. high = sizeof(int) * 8 - 1;
  99. bn_limit_bits_high = high;
  100. bn_limit_num_high = 1 << high;
  101. }
  102. if (low >= 0) {
  103. if (low > (int)(sizeof(int) * 8) - 1)
  104. low = sizeof(int) * 8 - 1;
  105. bn_limit_bits_low = low;
  106. bn_limit_num_low = 1 << low;
  107. }
  108. if (mont >= 0) {
  109. if (mont > (int)(sizeof(int) * 8) - 1)
  110. mont = sizeof(int) * 8 - 1;
  111. bn_limit_bits_mont = mont;
  112. bn_limit_num_mont = 1 << mont;
  113. }
  114. }
  115. int BN_get_params(int which)
  116. {
  117. if (which == 0)
  118. return (bn_limit_bits);
  119. else if (which == 1)
  120. return (bn_limit_bits_high);
  121. else if (which == 2)
  122. return (bn_limit_bits_low);
  123. else if (which == 3)
  124. return (bn_limit_bits_mont);
  125. else
  126. return (0);
  127. }
  128. #endif
  129. const BIGNUM *BN_value_one(void)
  130. {
  131. static BN_ULONG data_one = 1L;
  132. static BIGNUM const_one = { &data_one, 1, 1, 0, BN_FLG_STATIC_DATA };
  133. return (&const_one);
  134. }
  135. int BN_num_bits_word(BN_ULONG l)
  136. {
  137. static const char bits[256] = {
  138. 0, 1, 2, 2, 3, 3, 3, 3, 4, 4, 4, 4, 4, 4, 4, 4,
  139. 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5,
  140. 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6,
  141. 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6,
  142. 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
  143. 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
  144. 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
  145. 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
  146. 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
  147. 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
  148. 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
  149. 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
  150. 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
  151. 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
  152. 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
  153. 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
  154. };
  155. #if defined(SIXTY_FOUR_BIT_LONG)
  156. if (l & 0xffffffff00000000L) {
  157. if (l & 0xffff000000000000L) {
  158. if (l & 0xff00000000000000L) {
  159. return (bits[(int)(l >> 56)] + 56);
  160. } else
  161. return (bits[(int)(l >> 48)] + 48);
  162. } else {
  163. if (l & 0x0000ff0000000000L) {
  164. return (bits[(int)(l >> 40)] + 40);
  165. } else
  166. return (bits[(int)(l >> 32)] + 32);
  167. }
  168. } else
  169. #else
  170. # ifdef SIXTY_FOUR_BIT
  171. if (l & 0xffffffff00000000LL) {
  172. if (l & 0xffff000000000000LL) {
  173. if (l & 0xff00000000000000LL) {
  174. return (bits[(int)(l >> 56)] + 56);
  175. } else
  176. return (bits[(int)(l >> 48)] + 48);
  177. } else {
  178. if (l & 0x0000ff0000000000LL) {
  179. return (bits[(int)(l >> 40)] + 40);
  180. } else
  181. return (bits[(int)(l >> 32)] + 32);
  182. }
  183. } else
  184. # endif
  185. #endif
  186. {
  187. #if defined(THIRTY_TWO_BIT) || defined(SIXTY_FOUR_BIT) || defined(SIXTY_FOUR_BIT_LONG)
  188. if (l & 0xffff0000L) {
  189. if (l & 0xff000000L)
  190. return (bits[(int)(l >> 24L)] + 24);
  191. else
  192. return (bits[(int)(l >> 16L)] + 16);
  193. } else
  194. #endif
  195. {
  196. #if defined(SIXTEEN_BIT) || defined(THIRTY_TWO_BIT) || defined(SIXTY_FOUR_BIT) || defined(SIXTY_FOUR_BIT_LONG)
  197. if (l & 0xff00L)
  198. return (bits[(int)(l >> 8)] + 8);
  199. else
  200. #endif
  201. return (bits[(int)(l)]);
  202. }
  203. }
  204. }
  205. int BN_num_bits(const BIGNUM *a)
  206. {
  207. int i = a->top - 1;
  208. bn_check_top(a);
  209. if (BN_is_zero(a))
  210. return 0;
  211. return ((i * BN_BITS2) + BN_num_bits_word(a->d[i]));
  212. }
  213. void BN_clear_free(BIGNUM *a)
  214. {
  215. int i;
  216. if (a == NULL)
  217. return;
  218. bn_check_top(a);
  219. if (a->d != NULL) {
  220. OPENSSL_cleanse(a->d, a->dmax * sizeof(a->d[0]));
  221. if (!(BN_get_flags(a, BN_FLG_STATIC_DATA)))
  222. OPENSSL_free(a->d);
  223. }
  224. i = BN_get_flags(a, BN_FLG_MALLOCED);
  225. OPENSSL_cleanse(a, sizeof(BIGNUM));
  226. if (i)
  227. OPENSSL_free(a);
  228. }
  229. void BN_free(BIGNUM *a)
  230. {
  231. if (a == NULL)
  232. return;
  233. bn_check_top(a);
  234. if ((a->d != NULL) && !(BN_get_flags(a, BN_FLG_STATIC_DATA)))
  235. OPENSSL_free(a->d);
  236. if (a->flags & BN_FLG_MALLOCED)
  237. OPENSSL_free(a);
  238. else {
  239. #ifndef OPENSSL_NO_DEPRECATED
  240. a->flags |= BN_FLG_FREE;
  241. #endif
  242. a->d = NULL;
  243. }
  244. }
  245. void BN_init(BIGNUM *a)
  246. {
  247. memset(a, 0, sizeof(BIGNUM));
  248. bn_check_top(a);
  249. }
  250. BIGNUM *BN_new(void)
  251. {
  252. BIGNUM *ret;
  253. if ((ret = (BIGNUM *)OPENSSL_malloc(sizeof(BIGNUM))) == NULL) {
  254. BNerr(BN_F_BN_NEW, ERR_R_MALLOC_FAILURE);
  255. return (NULL);
  256. }
  257. ret->flags = BN_FLG_MALLOCED;
  258. ret->top = 0;
  259. ret->neg = 0;
  260. ret->dmax = 0;
  261. ret->d = NULL;
  262. bn_check_top(ret);
  263. return (ret);
  264. }
  265. /* This is used both by bn_expand2() and bn_dup_expand() */
  266. /* The caller MUST check that words > b->dmax before calling this */
  267. static BN_ULONG *bn_expand_internal(const BIGNUM *b, int words)
  268. {
  269. BN_ULONG *A, *a = NULL;
  270. const BN_ULONG *B;
  271. int i;
  272. bn_check_top(b);
  273. if (words > (INT_MAX / (4 * BN_BITS2))) {
  274. BNerr(BN_F_BN_EXPAND_INTERNAL, BN_R_BIGNUM_TOO_LONG);
  275. return NULL;
  276. }
  277. if (BN_get_flags(b, BN_FLG_STATIC_DATA)) {
  278. BNerr(BN_F_BN_EXPAND_INTERNAL, BN_R_EXPAND_ON_STATIC_BIGNUM_DATA);
  279. return (NULL);
  280. }
  281. a = A = (BN_ULONG *)OPENSSL_malloc(sizeof(BN_ULONG) * words);
  282. if (A == NULL) {
  283. BNerr(BN_F_BN_EXPAND_INTERNAL, ERR_R_MALLOC_FAILURE);
  284. return (NULL);
  285. }
  286. #ifdef PURIFY
  287. /*
  288. * Valgrind complains in BN_consttime_swap because we process the whole
  289. * array even if it's not initialised yet. This doesn't matter in that
  290. * function - what's important is constant time operation (we're not
  291. * actually going to use the data)
  292. */
  293. memset(a, 0, sizeof(BN_ULONG) * words);
  294. #endif
  295. #if 1
  296. B = b->d;
  297. /* Check if the previous number needs to be copied */
  298. if (B != NULL) {
  299. for (i = b->top >> 2; i > 0; i--, A += 4, B += 4) {
  300. /*
  301. * The fact that the loop is unrolled
  302. * 4-wise is a tribute to Intel. It's
  303. * the one that doesn't have enough
  304. * registers to accomodate more data.
  305. * I'd unroll it 8-wise otherwise:-)
  306. *
  307. * <appro@fy.chalmers.se>
  308. */
  309. BN_ULONG a0, a1, a2, a3;
  310. a0 = B[0];
  311. a1 = B[1];
  312. a2 = B[2];
  313. a3 = B[3];
  314. A[0] = a0;
  315. A[1] = a1;
  316. A[2] = a2;
  317. A[3] = a3;
  318. }
  319. /*
  320. * workaround for ultrix cc: without 'case 0', the optimizer does
  321. * the switch table by doing a=top&3; a--; goto jump_table[a];
  322. * which fails for top== 0
  323. */
  324. switch (b->top & 3) {
  325. case 3:
  326. A[2] = B[2];
  327. case 2:
  328. A[1] = B[1];
  329. case 1:
  330. A[0] = B[0];
  331. case 0:
  332. ;
  333. }
  334. }
  335. #else
  336. memset(A, 0, sizeof(BN_ULONG) * words);
  337. memcpy(A, b->d, sizeof(b->d[0]) * b->top);
  338. #endif
  339. return (a);
  340. }
  341. /*
  342. * This is an internal function that can be used instead of bn_expand2() when
  343. * there is a need to copy BIGNUMs instead of only expanding the data part,
  344. * while still expanding them. Especially useful when needing to expand
  345. * BIGNUMs that are declared 'const' and should therefore not be changed. The
  346. * reason to use this instead of a BN_dup() followed by a bn_expand2() is
  347. * memory allocation overhead. A BN_dup() followed by a bn_expand2() will
  348. * allocate new memory for the BIGNUM data twice, and free it once, while
  349. * bn_dup_expand() makes sure allocation is made only once.
  350. */
  351. #ifndef OPENSSL_NO_DEPRECATED
  352. BIGNUM *bn_dup_expand(const BIGNUM *b, int words)
  353. {
  354. BIGNUM *r = NULL;
  355. bn_check_top(b);
  356. /*
  357. * This function does not work if words <= b->dmax && top < words because
  358. * BN_dup() does not preserve 'dmax'! (But bn_dup_expand() is not used
  359. * anywhere yet.)
  360. */
  361. if (words > b->dmax) {
  362. BN_ULONG *a = bn_expand_internal(b, words);
  363. if (a) {
  364. r = BN_new();
  365. if (r) {
  366. r->top = b->top;
  367. r->dmax = words;
  368. r->neg = b->neg;
  369. r->d = a;
  370. } else {
  371. /* r == NULL, BN_new failure */
  372. OPENSSL_free(a);
  373. }
  374. }
  375. /*
  376. * If a == NULL, there was an error in allocation in
  377. * bn_expand_internal(), and NULL should be returned
  378. */
  379. } else {
  380. r = BN_dup(b);
  381. }
  382. bn_check_top(r);
  383. return r;
  384. }
  385. #endif
  386. /*
  387. * This is an internal function that should not be used in applications. It
  388. * ensures that 'b' has enough room for a 'words' word number and initialises
  389. * any unused part of b->d with leading zeros. It is mostly used by the
  390. * various BIGNUM routines. If there is an error, NULL is returned. If not,
  391. * 'b' is returned.
  392. */
  393. BIGNUM *bn_expand2(BIGNUM *b, int words)
  394. {
  395. bn_check_top(b);
  396. if (words > b->dmax) {
  397. BN_ULONG *a = bn_expand_internal(b, words);
  398. if (!a)
  399. return NULL;
  400. if (b->d)
  401. OPENSSL_free(b->d);
  402. b->d = a;
  403. b->dmax = words;
  404. }
  405. /* None of this should be necessary because of what b->top means! */
  406. #if 0
  407. /*
  408. * NB: bn_wexpand() calls this only if the BIGNUM really has to grow
  409. */
  410. if (b->top < b->dmax) {
  411. int i;
  412. BN_ULONG *A = &(b->d[b->top]);
  413. for (i = (b->dmax - b->top) >> 3; i > 0; i--, A += 8) {
  414. A[0] = 0;
  415. A[1] = 0;
  416. A[2] = 0;
  417. A[3] = 0;
  418. A[4] = 0;
  419. A[5] = 0;
  420. A[6] = 0;
  421. A[7] = 0;
  422. }
  423. for (i = (b->dmax - b->top) & 7; i > 0; i--, A++)
  424. A[0] = 0;
  425. assert(A == &(b->d[b->dmax]));
  426. }
  427. #endif
  428. bn_check_top(b);
  429. return b;
  430. }
  431. BIGNUM *BN_dup(const BIGNUM *a)
  432. {
  433. BIGNUM *t;
  434. if (a == NULL)
  435. return NULL;
  436. bn_check_top(a);
  437. t = BN_new();
  438. if (t == NULL)
  439. return NULL;
  440. if (!BN_copy(t, a)) {
  441. BN_free(t);
  442. return NULL;
  443. }
  444. bn_check_top(t);
  445. return t;
  446. }
  447. BIGNUM *BN_copy(BIGNUM *a, const BIGNUM *b)
  448. {
  449. int i;
  450. BN_ULONG *A;
  451. const BN_ULONG *B;
  452. bn_check_top(b);
  453. if (a == b)
  454. return (a);
  455. if (bn_wexpand(a, b->top) == NULL)
  456. return (NULL);
  457. #if 1
  458. A = a->d;
  459. B = b->d;
  460. for (i = b->top >> 2; i > 0; i--, A += 4, B += 4) {
  461. BN_ULONG a0, a1, a2, a3;
  462. a0 = B[0];
  463. a1 = B[1];
  464. a2 = B[2];
  465. a3 = B[3];
  466. A[0] = a0;
  467. A[1] = a1;
  468. A[2] = a2;
  469. A[3] = a3;
  470. }
  471. /* ultrix cc workaround, see comments in bn_expand_internal */
  472. switch (b->top & 3) {
  473. case 3:
  474. A[2] = B[2];
  475. case 2:
  476. A[1] = B[1];
  477. case 1:
  478. A[0] = B[0];
  479. case 0:;
  480. }
  481. #else
  482. memcpy(a->d, b->d, sizeof(b->d[0]) * b->top);
  483. #endif
  484. a->top = b->top;
  485. a->neg = b->neg;
  486. bn_check_top(a);
  487. return (a);
  488. }
  489. void BN_swap(BIGNUM *a, BIGNUM *b)
  490. {
  491. int flags_old_a, flags_old_b;
  492. BN_ULONG *tmp_d;
  493. int tmp_top, tmp_dmax, tmp_neg;
  494. bn_check_top(a);
  495. bn_check_top(b);
  496. flags_old_a = a->flags;
  497. flags_old_b = b->flags;
  498. tmp_d = a->d;
  499. tmp_top = a->top;
  500. tmp_dmax = a->dmax;
  501. tmp_neg = a->neg;
  502. a->d = b->d;
  503. a->top = b->top;
  504. a->dmax = b->dmax;
  505. a->neg = b->neg;
  506. b->d = tmp_d;
  507. b->top = tmp_top;
  508. b->dmax = tmp_dmax;
  509. b->neg = tmp_neg;
  510. a->flags =
  511. (flags_old_a & BN_FLG_MALLOCED) | (flags_old_b & BN_FLG_STATIC_DATA);
  512. b->flags =
  513. (flags_old_b & BN_FLG_MALLOCED) | (flags_old_a & BN_FLG_STATIC_DATA);
  514. bn_check_top(a);
  515. bn_check_top(b);
  516. }
  517. void BN_clear(BIGNUM *a)
  518. {
  519. bn_check_top(a);
  520. if (a->d != NULL)
  521. memset(a->d, 0, a->dmax * sizeof(a->d[0]));
  522. a->top = 0;
  523. a->neg = 0;
  524. }
  525. BN_ULONG BN_get_word(const BIGNUM *a)
  526. {
  527. if (a->top > 1)
  528. return BN_MASK2;
  529. else if (a->top == 1)
  530. return a->d[0];
  531. /* a->top == 0 */
  532. return 0;
  533. }
  534. int BN_set_word(BIGNUM *a, BN_ULONG w)
  535. {
  536. bn_check_top(a);
  537. if (bn_expand(a, (int)sizeof(BN_ULONG) * 8) == NULL)
  538. return (0);
  539. a->neg = 0;
  540. a->d[0] = w;
  541. a->top = (w ? 1 : 0);
  542. bn_check_top(a);
  543. return (1);
  544. }
  545. BIGNUM *BN_bin2bn(const unsigned char *s, int len, BIGNUM *ret)
  546. {
  547. unsigned int i, m;
  548. unsigned int n;
  549. BN_ULONG l;
  550. BIGNUM *bn = NULL;
  551. if (ret == NULL)
  552. ret = bn = BN_new();
  553. if (ret == NULL)
  554. return (NULL);
  555. bn_check_top(ret);
  556. l = 0;
  557. n = len;
  558. if (n == 0) {
  559. ret->top = 0;
  560. return (ret);
  561. }
  562. i = ((n - 1) / BN_BYTES) + 1;
  563. m = ((n - 1) % (BN_BYTES));
  564. if (bn_wexpand(ret, (int)i) == NULL) {
  565. if (bn)
  566. BN_free(bn);
  567. return NULL;
  568. }
  569. ret->top = i;
  570. ret->neg = 0;
  571. while (n--) {
  572. l = (l << 8L) | *(s++);
  573. if (m-- == 0) {
  574. ret->d[--i] = l;
  575. l = 0;
  576. m = BN_BYTES - 1;
  577. }
  578. }
  579. /*
  580. * need to call this due to clear byte at top if avoiding having the top
  581. * bit set (-ve number)
  582. */
  583. bn_correct_top(ret);
  584. return (ret);
  585. }
  586. /* ignore negative */
  587. int BN_bn2bin(const BIGNUM *a, unsigned char *to)
  588. {
  589. int n, i;
  590. BN_ULONG l;
  591. bn_check_top(a);
  592. n = i = BN_num_bytes(a);
  593. while (i--) {
  594. l = a->d[i / BN_BYTES];
  595. *(to++) = (unsigned char)(l >> (8 * (i % BN_BYTES))) & 0xff;
  596. }
  597. return (n);
  598. }
  599. int BN_ucmp(const BIGNUM *a, const BIGNUM *b)
  600. {
  601. int i;
  602. BN_ULONG t1, t2, *ap, *bp;
  603. bn_check_top(a);
  604. bn_check_top(b);
  605. i = a->top - b->top;
  606. if (i != 0)
  607. return (i);
  608. ap = a->d;
  609. bp = b->d;
  610. for (i = a->top - 1; i >= 0; i--) {
  611. t1 = ap[i];
  612. t2 = bp[i];
  613. if (t1 != t2)
  614. return ((t1 > t2) ? 1 : -1);
  615. }
  616. return (0);
  617. }
  618. int BN_cmp(const BIGNUM *a, const BIGNUM *b)
  619. {
  620. int i;
  621. int gt, lt;
  622. BN_ULONG t1, t2;
  623. if ((a == NULL) || (b == NULL)) {
  624. if (a != NULL)
  625. return (-1);
  626. else if (b != NULL)
  627. return (1);
  628. else
  629. return (0);
  630. }
  631. bn_check_top(a);
  632. bn_check_top(b);
  633. if (a->neg != b->neg) {
  634. if (a->neg)
  635. return (-1);
  636. else
  637. return (1);
  638. }
  639. if (a->neg == 0) {
  640. gt = 1;
  641. lt = -1;
  642. } else {
  643. gt = -1;
  644. lt = 1;
  645. }
  646. if (a->top > b->top)
  647. return (gt);
  648. if (a->top < b->top)
  649. return (lt);
  650. for (i = a->top - 1; i >= 0; i--) {
  651. t1 = a->d[i];
  652. t2 = b->d[i];
  653. if (t1 > t2)
  654. return (gt);
  655. if (t1 < t2)
  656. return (lt);
  657. }
  658. return (0);
  659. }
  660. int BN_set_bit(BIGNUM *a, int n)
  661. {
  662. int i, j, k;
  663. if (n < 0)
  664. return 0;
  665. i = n / BN_BITS2;
  666. j = n % BN_BITS2;
  667. if (a->top <= i) {
  668. if (bn_wexpand(a, i + 1) == NULL)
  669. return (0);
  670. for (k = a->top; k < i + 1; k++)
  671. a->d[k] = 0;
  672. a->top = i + 1;
  673. }
  674. a->d[i] |= (((BN_ULONG)1) << j);
  675. bn_check_top(a);
  676. return (1);
  677. }
  678. int BN_clear_bit(BIGNUM *a, int n)
  679. {
  680. int i, j;
  681. bn_check_top(a);
  682. if (n < 0)
  683. return 0;
  684. i = n / BN_BITS2;
  685. j = n % BN_BITS2;
  686. if (a->top <= i)
  687. return (0);
  688. a->d[i] &= (~(((BN_ULONG)1) << j));
  689. bn_correct_top(a);
  690. return (1);
  691. }
  692. int BN_is_bit_set(const BIGNUM *a, int n)
  693. {
  694. int i, j;
  695. bn_check_top(a);
  696. if (n < 0)
  697. return 0;
  698. i = n / BN_BITS2;
  699. j = n % BN_BITS2;
  700. if (a->top <= i)
  701. return 0;
  702. return (((a->d[i]) >> j) & ((BN_ULONG)1));
  703. }
  704. int BN_mask_bits(BIGNUM *a, int n)
  705. {
  706. int b, w;
  707. bn_check_top(a);
  708. if (n < 0)
  709. return 0;
  710. w = n / BN_BITS2;
  711. b = n % BN_BITS2;
  712. if (w >= a->top)
  713. return 0;
  714. if (b == 0)
  715. a->top = w;
  716. else {
  717. a->top = w + 1;
  718. a->d[w] &= ~(BN_MASK2 << b);
  719. }
  720. bn_correct_top(a);
  721. return (1);
  722. }
  723. void BN_set_negative(BIGNUM *a, int b)
  724. {
  725. if (b && !BN_is_zero(a))
  726. a->neg = 1;
  727. else
  728. a->neg = 0;
  729. }
  730. int bn_cmp_words(const BN_ULONG *a, const BN_ULONG *b, int n)
  731. {
  732. int i;
  733. BN_ULONG aa, bb;
  734. aa = a[n - 1];
  735. bb = b[n - 1];
  736. if (aa != bb)
  737. return ((aa > bb) ? 1 : -1);
  738. for (i = n - 2; i >= 0; i--) {
  739. aa = a[i];
  740. bb = b[i];
  741. if (aa != bb)
  742. return ((aa > bb) ? 1 : -1);
  743. }
  744. return (0);
  745. }
  746. /*
  747. * Here follows a specialised variants of bn_cmp_words(). It has the
  748. * property of performing the operation on arrays of different sizes. The
  749. * sizes of those arrays is expressed through cl, which is the common length
  750. * ( basicall, min(len(a),len(b)) ), and dl, which is the delta between the
  751. * two lengths, calculated as len(a)-len(b). All lengths are the number of
  752. * BN_ULONGs...
  753. */
  754. int bn_cmp_part_words(const BN_ULONG *a, const BN_ULONG *b, int cl, int dl)
  755. {
  756. int n, i;
  757. n = cl - 1;
  758. if (dl < 0) {
  759. for (i = dl; i < 0; i++) {
  760. if (b[n - i] != 0)
  761. return -1; /* a < b */
  762. }
  763. }
  764. if (dl > 0) {
  765. for (i = dl; i > 0; i--) {
  766. if (a[n + i] != 0)
  767. return 1; /* a > b */
  768. }
  769. }
  770. return bn_cmp_words(a, b, cl);
  771. }