bn_lib.c 18 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602603604605606607608609610611612613614615616617618619620621622623624625626627628629630631632633634635636637638639640641642643644645646647648649650651652653654655656657658659660661662663664665666667668669670671672673674675676677678679680681682683684685686687688689690691692693694695696697698699700701702703704705706707708709710711712713714715716717718719720721722723724725726727728729730731732733734735736737738739740741742743744745746747748749750751752753754755756757758759760761762763764765766767768769770771772773774775776777778779780781782783784785786787788789790791792793794795796797798799800801802803804805806807808809810811812813814815816817818819820821822823824825826827828829830831832833834835836837838839840841842843844845
  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. /* For a 32 bit machine
  71. * 2 - 4 == 128
  72. * 3 - 8 == 256
  73. * 4 - 16 == 512
  74. * 5 - 32 == 1024
  75. * 6 - 64 == 2048
  76. * 7 - 128 == 4096
  77. * 8 - 256 == 8192
  78. */
  79. static int bn_limit_bits=0;
  80. static int bn_limit_num=8; /* (1<<bn_limit_bits) */
  81. static int bn_limit_bits_low=0;
  82. static int bn_limit_num_low=8; /* (1<<bn_limit_bits_low) */
  83. static int bn_limit_bits_high=0;
  84. static int bn_limit_num_high=8; /* (1<<bn_limit_bits_high) */
  85. static int bn_limit_bits_mont=0;
  86. static int bn_limit_num_mont=8; /* (1<<bn_limit_bits_mont) */
  87. void BN_set_params(int mult, int high, int low, int mont)
  88. {
  89. if (mult >= 0)
  90. {
  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. {
  98. if (high > (int)(sizeof(int)*8)-1)
  99. high=sizeof(int)*8-1;
  100. bn_limit_bits_high=high;
  101. bn_limit_num_high=1<<high;
  102. }
  103. if (low >= 0)
  104. {
  105. if (low > (int)(sizeof(int)*8)-1)
  106. low=sizeof(int)*8-1;
  107. bn_limit_bits_low=low;
  108. bn_limit_num_low=1<<low;
  109. }
  110. if (mont >= 0)
  111. {
  112. if (mont > (int)(sizeof(int)*8)-1)
  113. mont=sizeof(int)*8-1;
  114. bn_limit_bits_mont=mont;
  115. bn_limit_num_mont=1<<mont;
  116. }
  117. }
  118. int BN_get_params(int which)
  119. {
  120. if (which == 0) return(bn_limit_bits);
  121. else if (which == 1) return(bn_limit_bits_high);
  122. else if (which == 2) return(bn_limit_bits_low);
  123. else if (which == 3) return(bn_limit_bits_mont);
  124. else return(0);
  125. }
  126. #endif
  127. const BIGNUM *BN_value_one(void)
  128. {
  129. static BN_ULONG data_one=1L;
  130. static BIGNUM const_one={&data_one,1,1,0,BN_FLG_STATIC_DATA};
  131. return(&const_one);
  132. }
  133. char *BN_options(void)
  134. {
  135. static int init=0;
  136. static char data[16];
  137. if (!init)
  138. {
  139. init++;
  140. #ifdef BN_LLONG
  141. BIO_snprintf(data,sizeof data,"bn(%d,%d)",
  142. (int)sizeof(BN_ULLONG)*8,(int)sizeof(BN_ULONG)*8);
  143. #else
  144. BIO_snprintf(data,sizeof data,"bn(%d,%d)",
  145. (int)sizeof(BN_ULONG)*8,(int)sizeof(BN_ULONG)*8);
  146. #endif
  147. }
  148. return(data);
  149. }
  150. int BN_num_bits_word(BN_ULONG l)
  151. {
  152. static const char bits[256]={
  153. 0,1,2,2,3,3,3,3,4,4,4,4,4,4,4,4,
  154. 5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,
  155. 6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,
  156. 6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,
  157. 7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,
  158. 7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,
  159. 7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,
  160. 7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,
  161. 8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,
  162. 8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,
  163. 8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,
  164. 8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,
  165. 8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,
  166. 8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,
  167. 8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,
  168. 8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,
  169. };
  170. #if defined(SIXTY_FOUR_BIT_LONG)
  171. if (l & 0xffffffff00000000L)
  172. {
  173. if (l & 0xffff000000000000L)
  174. {
  175. if (l & 0xff00000000000000L)
  176. {
  177. return(bits[(int)(l>>56)]+56);
  178. }
  179. else return(bits[(int)(l>>48)]+48);
  180. }
  181. else
  182. {
  183. if (l & 0x0000ff0000000000L)
  184. {
  185. return(bits[(int)(l>>40)]+40);
  186. }
  187. else return(bits[(int)(l>>32)]+32);
  188. }
  189. }
  190. else
  191. #else
  192. #ifdef SIXTY_FOUR_BIT
  193. if (l & 0xffffffff00000000LL)
  194. {
  195. if (l & 0xffff000000000000LL)
  196. {
  197. if (l & 0xff00000000000000LL)
  198. {
  199. return(bits[(int)(l>>56)]+56);
  200. }
  201. else return(bits[(int)(l>>48)]+48);
  202. }
  203. else
  204. {
  205. if (l & 0x0000ff0000000000LL)
  206. {
  207. return(bits[(int)(l>>40)]+40);
  208. }
  209. else return(bits[(int)(l>>32)]+32);
  210. }
  211. }
  212. else
  213. #endif
  214. #endif
  215. {
  216. #if defined(THIRTY_TWO_BIT) || defined(SIXTY_FOUR_BIT) || defined(SIXTY_FOUR_BIT_LONG)
  217. if (l & 0xffff0000L)
  218. {
  219. if (l & 0xff000000L)
  220. return(bits[(int)(l>>24L)]+24);
  221. else return(bits[(int)(l>>16L)]+16);
  222. }
  223. else
  224. #endif
  225. {
  226. #if defined(THIRTY_TWO_BIT) || defined(SIXTY_FOUR_BIT) || defined(SIXTY_FOUR_BIT_LONG)
  227. if (l & 0xff00L)
  228. return(bits[(int)(l>>8)]+8);
  229. else
  230. #endif
  231. return(bits[(int)(l )] );
  232. }
  233. }
  234. }
  235. int BN_num_bits(const BIGNUM *a)
  236. {
  237. int i = a->top - 1;
  238. bn_check_top(a);
  239. if (BN_is_zero(a)) return 0;
  240. return ((i*BN_BITS2) + BN_num_bits_word(a->d[i]));
  241. }
  242. void BN_clear_free(BIGNUM *a)
  243. {
  244. int i;
  245. if (a == NULL) return;
  246. bn_check_top(a);
  247. if (a->d != NULL)
  248. {
  249. OPENSSL_cleanse(a->d,a->dmax*sizeof(a->d[0]));
  250. if (!(BN_get_flags(a,BN_FLG_STATIC_DATA)))
  251. OPENSSL_free(a->d);
  252. }
  253. i=BN_get_flags(a,BN_FLG_MALLOCED);
  254. OPENSSL_cleanse(a,sizeof(BIGNUM));
  255. if (i)
  256. OPENSSL_free(a);
  257. }
  258. void BN_free(BIGNUM *a)
  259. {
  260. if (a == NULL) return;
  261. bn_check_top(a);
  262. if ((a->d != NULL) && !(BN_get_flags(a,BN_FLG_STATIC_DATA)))
  263. OPENSSL_free(a->d);
  264. if (a->flags & BN_FLG_MALLOCED)
  265. OPENSSL_free(a);
  266. else
  267. {
  268. #ifndef OPENSSL_NO_DEPRECATED
  269. a->flags|=BN_FLG_FREE;
  270. #endif
  271. a->d = NULL;
  272. }
  273. }
  274. void BN_init(BIGNUM *a)
  275. {
  276. memset(a,0,sizeof(BIGNUM));
  277. bn_check_top(a);
  278. }
  279. BIGNUM *BN_new(void)
  280. {
  281. BIGNUM *ret;
  282. if ((ret=(BIGNUM *)OPENSSL_malloc(sizeof(BIGNUM))) == NULL)
  283. {
  284. BNerr(BN_F_BN_NEW,ERR_R_MALLOC_FAILURE);
  285. return(NULL);
  286. }
  287. ret->flags=BN_FLG_MALLOCED;
  288. ret->top=0;
  289. ret->neg=0;
  290. ret->dmax=0;
  291. ret->d=NULL;
  292. bn_check_top(ret);
  293. return(ret);
  294. }
  295. /* This is used both by bn_expand2() and bn_dup_expand() */
  296. /* The caller MUST check that words > b->dmax before calling this */
  297. static BN_ULONG *bn_expand_internal(const BIGNUM *b, int words)
  298. {
  299. BN_ULONG *A,*a = NULL;
  300. const BN_ULONG *B;
  301. int i;
  302. bn_check_top(b);
  303. if (words > (INT_MAX/(4*BN_BITS2)))
  304. {
  305. BNerr(BN_F_BN_EXPAND_INTERNAL,BN_R_BIGNUM_TOO_LONG);
  306. return NULL;
  307. }
  308. if (BN_get_flags(b,BN_FLG_STATIC_DATA))
  309. {
  310. BNerr(BN_F_BN_EXPAND_INTERNAL,BN_R_EXPAND_ON_STATIC_BIGNUM_DATA);
  311. return(NULL);
  312. }
  313. a=A=(BN_ULONG *)OPENSSL_malloc(sizeof(BN_ULONG)*words);
  314. if (A == NULL)
  315. {
  316. BNerr(BN_F_BN_EXPAND_INTERNAL,ERR_R_MALLOC_FAILURE);
  317. return(NULL);
  318. }
  319. #if 1
  320. B=b->d;
  321. /* Check if the previous number needs to be copied */
  322. if (B != NULL)
  323. {
  324. for (i=b->top>>2; i>0; i--,A+=4,B+=4)
  325. {
  326. /*
  327. * The fact that the loop is unrolled
  328. * 4-wise is a tribute to Intel. It's
  329. * the one that doesn't have enough
  330. * registers to accomodate more data.
  331. * I'd unroll it 8-wise otherwise:-)
  332. *
  333. * <appro@fy.chalmers.se>
  334. */
  335. BN_ULONG a0,a1,a2,a3;
  336. a0=B[0]; a1=B[1]; a2=B[2]; a3=B[3];
  337. A[0]=a0; A[1]=a1; A[2]=a2; A[3]=a3;
  338. }
  339. switch (b->top&3)
  340. {
  341. case 3: A[2]=B[2];
  342. case 2: A[1]=B[1];
  343. case 1: A[0]=B[0];
  344. case 0: /* workaround for ultrix cc: without 'case 0', the optimizer does
  345. * the switch table by doing a=top&3; a--; goto jump_table[a];
  346. * which fails for top== 0 */
  347. ;
  348. }
  349. }
  350. #else
  351. memset(A,0,sizeof(BN_ULONG)*words);
  352. memcpy(A,b->d,sizeof(b->d[0])*b->top);
  353. #endif
  354. return(a);
  355. }
  356. /* This is an internal function that can be used instead of bn_expand2()
  357. * when there is a need to copy BIGNUMs instead of only expanding the
  358. * data part, while still expanding them.
  359. * Especially useful when needing to expand BIGNUMs that are declared
  360. * 'const' and should therefore not be changed.
  361. * The reason to use this instead of a BN_dup() followed by a bn_expand2()
  362. * is memory allocation overhead. A BN_dup() followed by a bn_expand2()
  363. * will allocate new memory for the BIGNUM data twice, and free it once,
  364. * while bn_dup_expand() makes sure allocation is made only once.
  365. */
  366. #ifndef OPENSSL_NO_DEPRECATED
  367. BIGNUM *bn_dup_expand(const BIGNUM *b, int words)
  368. {
  369. BIGNUM *r = NULL;
  370. bn_check_top(b);
  371. /* This function does not work if
  372. * words <= b->dmax && top < words
  373. * because BN_dup() does not preserve 'dmax'!
  374. * (But bn_dup_expand() is not used anywhere yet.)
  375. */
  376. if (words > b->dmax)
  377. {
  378. BN_ULONG *a = bn_expand_internal(b, words);
  379. if (a)
  380. {
  381. r = BN_new();
  382. if (r)
  383. {
  384. r->top = b->top;
  385. r->dmax = words;
  386. r->neg = b->neg;
  387. r->d = a;
  388. }
  389. else
  390. {
  391. /* r == NULL, BN_new failure */
  392. OPENSSL_free(a);
  393. }
  394. }
  395. /* If a == NULL, there was an error in allocation in
  396. bn_expand_internal(), and NULL should be returned */
  397. }
  398. else
  399. {
  400. r = BN_dup(b);
  401. }
  402. bn_check_top(r);
  403. return r;
  404. }
  405. #endif
  406. /* This is an internal function that should not be used in applications.
  407. * It ensures that 'b' has enough room for a 'words' word number
  408. * and initialises any unused part of b->d with leading zeros.
  409. * It is mostly used by the various BIGNUM routines. If there is an error,
  410. * NULL is returned. If not, 'b' is returned. */
  411. BIGNUM *bn_expand2(BIGNUM *b, int words)
  412. {
  413. bn_check_top(b);
  414. if (words > b->dmax)
  415. {
  416. BN_ULONG *a = bn_expand_internal(b, words);
  417. if(!a) return NULL;
  418. if(b->d) OPENSSL_free(b->d);
  419. b->d=a;
  420. b->dmax=words;
  421. }
  422. /* None of this should be necessary because of what b->top means! */
  423. #if 0
  424. /* NB: bn_wexpand() calls this only if the BIGNUM really has to grow */
  425. if (b->top < b->dmax)
  426. {
  427. int i;
  428. BN_ULONG *A = &(b->d[b->top]);
  429. for (i=(b->dmax - b->top)>>3; i>0; i--,A+=8)
  430. {
  431. A[0]=0; A[1]=0; A[2]=0; A[3]=0;
  432. A[4]=0; A[5]=0; A[6]=0; A[7]=0;
  433. }
  434. for (i=(b->dmax - b->top)&7; i>0; i--,A++)
  435. A[0]=0;
  436. assert(A == &(b->d[b->dmax]));
  437. }
  438. #endif
  439. bn_check_top(b);
  440. return b;
  441. }
  442. BIGNUM *BN_dup(const BIGNUM *a)
  443. {
  444. BIGNUM *t;
  445. if (a == NULL) return NULL;
  446. bn_check_top(a);
  447. t = BN_new();
  448. if (t == NULL) return NULL;
  449. if(!BN_copy(t, a))
  450. {
  451. BN_free(t);
  452. return NULL;
  453. }
  454. bn_check_top(t);
  455. return t;
  456. }
  457. BIGNUM *BN_copy(BIGNUM *a, const BIGNUM *b)
  458. {
  459. int i;
  460. BN_ULONG *A;
  461. const BN_ULONG *B;
  462. bn_check_top(b);
  463. if (a == b) return(a);
  464. if (bn_wexpand(a,b->top) == NULL) return(NULL);
  465. #if 1
  466. A=a->d;
  467. B=b->d;
  468. for (i=b->top>>2; i>0; i--,A+=4,B+=4)
  469. {
  470. BN_ULONG a0,a1,a2,a3;
  471. a0=B[0]; a1=B[1]; a2=B[2]; a3=B[3];
  472. A[0]=a0; A[1]=a1; A[2]=a2; A[3]=a3;
  473. }
  474. switch (b->top&3)
  475. {
  476. case 3: A[2]=B[2];
  477. case 2: A[1]=B[1];
  478. case 1: A[0]=B[0];
  479. case 0: ; /* ultrix cc workaround, see comments in bn_expand_internal */
  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 = (flags_old_a & BN_FLG_MALLOCED) | (flags_old_b & BN_FLG_STATIC_DATA);
  511. b->flags = (flags_old_b & BN_FLG_MALLOCED) | (flags_old_a & BN_FLG_STATIC_DATA);
  512. bn_check_top(a);
  513. bn_check_top(b);
  514. }
  515. void BN_clear(BIGNUM *a)
  516. {
  517. bn_check_top(a);
  518. if (a->d != NULL)
  519. memset(a->d,0,a->dmax*sizeof(a->d[0]));
  520. a->top=0;
  521. a->neg=0;
  522. }
  523. BN_ULONG BN_get_word(const BIGNUM *a)
  524. {
  525. if (a->top > 1)
  526. return BN_MASK2;
  527. else if (a->top == 1)
  528. return a->d[0];
  529. /* a->top == 0 */
  530. return 0;
  531. }
  532. int BN_set_word(BIGNUM *a, BN_ULONG w)
  533. {
  534. bn_check_top(a);
  535. if (bn_expand(a,(int)sizeof(BN_ULONG)*8) == NULL) return(0);
  536. a->neg = 0;
  537. a->d[0] = w;
  538. a->top = (w ? 1 : 0);
  539. bn_check_top(a);
  540. return(1);
  541. }
  542. BIGNUM *BN_bin2bn(const unsigned char *s, int len, BIGNUM *ret)
  543. {
  544. unsigned int i,m;
  545. unsigned int n;
  546. BN_ULONG l;
  547. BIGNUM *bn = NULL;
  548. if (ret == NULL)
  549. ret = bn = BN_new();
  550. if (ret == NULL) return(NULL);
  551. bn_check_top(ret);
  552. l=0;
  553. n=len;
  554. if (n == 0)
  555. {
  556. ret->top=0;
  557. return(ret);
  558. }
  559. i=((n-1)/BN_BYTES)+1;
  560. m=((n-1)%(BN_BYTES));
  561. if (bn_wexpand(ret, (int)i) == NULL)
  562. {
  563. if (bn) BN_free(bn);
  564. return NULL;
  565. }
  566. ret->top=i;
  567. ret->neg=0;
  568. while (n--)
  569. {
  570. l=(l<<8L)| *(s++);
  571. if (m-- == 0)
  572. {
  573. ret->d[--i]=l;
  574. l=0;
  575. m=BN_BYTES-1;
  576. }
  577. }
  578. /* need to call this due to clear byte at top if avoiding
  579. * having the top bit set (-ve number) */
  580. bn_correct_top(ret);
  581. return(ret);
  582. }
  583. /* ignore negative */
  584. int BN_bn2bin(const BIGNUM *a, unsigned char *to)
  585. {
  586. int n,i;
  587. BN_ULONG l;
  588. bn_check_top(a);
  589. n=i=BN_num_bytes(a);
  590. while (i--)
  591. {
  592. l=a->d[i/BN_BYTES];
  593. *(to++)=(unsigned char)(l>>(8*(i%BN_BYTES)))&0xff;
  594. }
  595. return(n);
  596. }
  597. int BN_ucmp(const BIGNUM *a, const BIGNUM *b)
  598. {
  599. int i;
  600. BN_ULONG t1,t2,*ap,*bp;
  601. bn_check_top(a);
  602. bn_check_top(b);
  603. i=a->top-b->top;
  604. if (i != 0) return(i);
  605. ap=a->d;
  606. bp=b->d;
  607. for (i=a->top-1; i>=0; i--)
  608. {
  609. t1= ap[i];
  610. t2= bp[i];
  611. if (t1 != t2)
  612. return((t1 > t2) ? 1 : -1);
  613. }
  614. return(0);
  615. }
  616. int BN_cmp(const BIGNUM *a, const BIGNUM *b)
  617. {
  618. int i;
  619. int gt,lt;
  620. BN_ULONG t1,t2;
  621. if ((a == NULL) || (b == NULL))
  622. {
  623. if (a != NULL)
  624. return(-1);
  625. else if (b != NULL)
  626. return(1);
  627. else
  628. return(0);
  629. }
  630. bn_check_top(a);
  631. bn_check_top(b);
  632. if (a->neg != b->neg)
  633. {
  634. if (a->neg)
  635. return(-1);
  636. else return(1);
  637. }
  638. if (a->neg == 0)
  639. { gt=1; lt= -1; }
  640. else { gt= -1; lt=1; }
  641. if (a->top > b->top) return(gt);
  642. if (a->top < b->top) return(lt);
  643. for (i=a->top-1; i>=0; i--)
  644. {
  645. t1=a->d[i];
  646. t2=b->d[i];
  647. if (t1 > t2) return(gt);
  648. if (t1 < t2) return(lt);
  649. }
  650. return(0);
  651. }
  652. int BN_set_bit(BIGNUM *a, int n)
  653. {
  654. int i,j,k;
  655. if (n < 0)
  656. return 0;
  657. i=n/BN_BITS2;
  658. j=n%BN_BITS2;
  659. if (a->top <= i)
  660. {
  661. if (bn_wexpand(a,i+1) == NULL) return(0);
  662. for(k=a->top; k<i+1; k++)
  663. a->d[k]=0;
  664. a->top=i+1;
  665. }
  666. a->d[i]|=(((BN_ULONG)1)<<j);
  667. bn_check_top(a);
  668. return(1);
  669. }
  670. int BN_clear_bit(BIGNUM *a, int n)
  671. {
  672. int i,j;
  673. bn_check_top(a);
  674. if (n < 0) return 0;
  675. i=n/BN_BITS2;
  676. j=n%BN_BITS2;
  677. if (a->top <= i) return(0);
  678. a->d[i]&=(~(((BN_ULONG)1)<<j));
  679. bn_correct_top(a);
  680. return(1);
  681. }
  682. int BN_is_bit_set(const BIGNUM *a, int n)
  683. {
  684. int i,j;
  685. bn_check_top(a);
  686. if (n < 0) return 0;
  687. i=n/BN_BITS2;
  688. j=n%BN_BITS2;
  689. if (a->top <= i) return 0;
  690. return((a->d[i]&(((BN_ULONG)1)<<j))?1:0);
  691. }
  692. int BN_mask_bits(BIGNUM *a, int n)
  693. {
  694. int b,w;
  695. bn_check_top(a);
  696. if (n < 0) return 0;
  697. w=n/BN_BITS2;
  698. b=n%BN_BITS2;
  699. if (w >= a->top) return 0;
  700. if (b == 0)
  701. a->top=w;
  702. else
  703. {
  704. a->top=w+1;
  705. a->d[w]&= ~(BN_MASK2<<b);
  706. }
  707. bn_correct_top(a);
  708. return(1);
  709. }
  710. void BN_set_negative(BIGNUM *a, int b)
  711. {
  712. if (b && !BN_is_zero(a))
  713. a->neg = 1;
  714. else
  715. a->neg = 0;
  716. }
  717. int bn_cmp_words(const BN_ULONG *a, const BN_ULONG *b, int n)
  718. {
  719. int i;
  720. BN_ULONG aa,bb;
  721. aa=a[n-1];
  722. bb=b[n-1];
  723. if (aa != bb) return((aa > bb)?1:-1);
  724. for (i=n-2; i>=0; i--)
  725. {
  726. aa=a[i];
  727. bb=b[i];
  728. if (aa != bb) return((aa > bb)?1:-1);
  729. }
  730. return(0);
  731. }
  732. /* Here follows a specialised variants of bn_cmp_words(). It has the
  733. property of performing the operation on arrays of different sizes.
  734. The sizes of those arrays is expressed through cl, which is the
  735. common length ( basicall, min(len(a),len(b)) ), and dl, which is the
  736. delta between the two lengths, calculated as len(a)-len(b).
  737. All lengths are the number of BN_ULONGs... */
  738. int bn_cmp_part_words(const BN_ULONG *a, const BN_ULONG *b,
  739. int cl, int dl)
  740. {
  741. int n,i;
  742. n = cl-1;
  743. if (dl < 0)
  744. {
  745. for (i=dl; i<0; i++)
  746. {
  747. if (b[n-i] != 0)
  748. return -1; /* a < b */
  749. }
  750. }
  751. if (dl > 0)
  752. {
  753. for (i=dl; i>0; i--)
  754. {
  755. if (a[n+i] != 0)
  756. return 1; /* a > b */
  757. }
  758. }
  759. return bn_cmp_words(a,b,cl);
  760. }