2
0

bn_lib.c 27 KB

12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182838485868788899091929394959697989910010110210310410510610710810911011111211311411511611711811912012112212312412512612712812913013113213313413513613713813914014114214314414514614714814915015115215315415515615715815916016116216316416516616716816917017117217317417517617717817918018118218318418518618718818919019119219319419519619719819920020120220320420520620720820921021121221321421521621721821922022122222322422522622722822923023123223323423523623723823924024124224324424524624724824925025125225325425525625725825926026126226326426526626726826927027127227327427527627727827928028128228328428528628728828929029129229329429529629729829930030130230330430530630730830931031131231331431531631731831932032132232332432532632732832933033133233333433533633733833934034134234334434534634734834935035135235335435535635735835936036136236336436536636736836937037137237337437537637737837938038138238338438538638738838939039139239339439539639739839940040140240340440540640740840941041141241341441541641741841942042142242342442542642742842943043143243343443543643743843944044144244344444544644744844945045145245345445545645745845946046146246346446546646746846947047147247347447547647747847948048148248348448548648748848949049149249349449549649749849950050150250350450550650750850951051151251351451551651751851952052152252352452552652752852953053153253353453553653753853954054154254354454554654754854955055155255355455555655755855956056156256356456556656756856957057157257357457557657757857958058158258358458558658758858959059159259359459559659759859960060160260360460560660760860961061161261361461561661761861962062162262362462562662762862963063163263363463563663763863964064164264364464564664764864965065165265365465565665765865966066166266366466566666766866967067167267367467567667767867968068168268368468568668768868969069169269369469569669769869970070170270370470570670770870971071171271371471571671771871972072172272372472572672772872973073173273373473573673773873974074174274374474574674774874975075175275375475575675775875976076176276376476576676776876977077177277377477577677777877978078178278378478578678778878979079179279379479579679779879980080180280380480580680780880981081181281381481581681781881982082182282382482582682782882983083183283383483583683783883984084184284384484584684784884985085185285385485585685785885986086186286386486586686786886987087187287387487587687787887988088188288388488588688788888989089189289389489589689789889990090190290390490590690790890991091191291391491591691791891992092192292392492592692792892993093193293393493593693793893994094194294394494594694794894995095195295395495595695795895996096196296396496596696796896997097197297397497597697797897998098198298398498598698798898999099199299399499599699799899910001001100210031004100510061007100810091010101110121013101410151016101710181019102010211022102310241025102610271028102910301031103210331034103510361037103810391040104110421043104410451046104710481049105010511052105310541055105610571058105910601061106210631064106510661067106810691070107110721073107410751076107710781079108010811082108310841085108610871088108910901091109210931094109510961097109810991100110111021103110411051106110711081109111011111112111311141115111611171118111911201121112211231124112511261127112811291130113111321133113411351136113711381139114011411142114311441145114611471148
  1. /*
  2. * Copyright 1995-2023 The OpenSSL Project Authors. All Rights Reserved.
  3. *
  4. * Licensed under the Apache License 2.0 (the "License"). You may not use
  5. * this file except in compliance with the License. You can obtain a copy
  6. * in the file LICENSE in the source distribution or at
  7. * https://www.openssl.org/source/license.html
  8. */
  9. #include <assert.h>
  10. #include <limits.h>
  11. #include "internal/cryptlib.h"
  12. #include "internal/endian.h"
  13. #include "bn_local.h"
  14. #include <openssl/opensslconf.h>
  15. #include "internal/constant_time.h"
  16. /* This stuff appears to be completely unused, so is deprecated */
  17. #ifndef OPENSSL_NO_DEPRECATED_0_9_8
  18. /*-
  19. * For a 32 bit machine
  20. * 2 - 4 == 128
  21. * 3 - 8 == 256
  22. * 4 - 16 == 512
  23. * 5 - 32 == 1024
  24. * 6 - 64 == 2048
  25. * 7 - 128 == 4096
  26. * 8 - 256 == 8192
  27. */
  28. static int bn_limit_bits = 0;
  29. static int bn_limit_num = 8; /* (1<<bn_limit_bits) */
  30. static int bn_limit_bits_low = 0;
  31. static int bn_limit_num_low = 8; /* (1<<bn_limit_bits_low) */
  32. static int bn_limit_bits_high = 0;
  33. static int bn_limit_num_high = 8; /* (1<<bn_limit_bits_high) */
  34. static int bn_limit_bits_mont = 0;
  35. static int bn_limit_num_mont = 8; /* (1<<bn_limit_bits_mont) */
  36. void BN_set_params(int mult, int high, int low, int mont)
  37. {
  38. if (mult >= 0) {
  39. if (mult > (int)(sizeof(int) * 8) - 1)
  40. mult = sizeof(int) * 8 - 1;
  41. bn_limit_bits = mult;
  42. bn_limit_num = 1 << mult;
  43. }
  44. if (high >= 0) {
  45. if (high > (int)(sizeof(int) * 8) - 1)
  46. high = sizeof(int) * 8 - 1;
  47. bn_limit_bits_high = high;
  48. bn_limit_num_high = 1 << high;
  49. }
  50. if (low >= 0) {
  51. if (low > (int)(sizeof(int) * 8) - 1)
  52. low = sizeof(int) * 8 - 1;
  53. bn_limit_bits_low = low;
  54. bn_limit_num_low = 1 << low;
  55. }
  56. if (mont >= 0) {
  57. if (mont > (int)(sizeof(int) * 8) - 1)
  58. mont = sizeof(int) * 8 - 1;
  59. bn_limit_bits_mont = mont;
  60. bn_limit_num_mont = 1 << mont;
  61. }
  62. }
  63. int BN_get_params(int which)
  64. {
  65. if (which == 0)
  66. return bn_limit_bits;
  67. else if (which == 1)
  68. return bn_limit_bits_high;
  69. else if (which == 2)
  70. return bn_limit_bits_low;
  71. else if (which == 3)
  72. return bn_limit_bits_mont;
  73. else
  74. return 0;
  75. }
  76. #endif
  77. const BIGNUM *BN_value_one(void)
  78. {
  79. static const BN_ULONG data_one = 1L;
  80. static const BIGNUM const_one =
  81. { (BN_ULONG *)&data_one, 1, 1, 0, BN_FLG_STATIC_DATA };
  82. return &const_one;
  83. }
  84. /*
  85. * Old Visual Studio ARM compiler miscompiles BN_num_bits_word()
  86. * https://mta.openssl.org/pipermail/openssl-users/2018-August/008465.html
  87. */
  88. #if defined(_MSC_VER) && defined(_ARM_) && defined(_WIN32_WCE) \
  89. && _MSC_VER>=1400 && _MSC_VER<1501
  90. # define MS_BROKEN_BN_num_bits_word
  91. # pragma optimize("", off)
  92. #endif
  93. int BN_num_bits_word(BN_ULONG l)
  94. {
  95. BN_ULONG x, mask;
  96. int bits = (l != 0);
  97. #if BN_BITS2 > 32
  98. x = l >> 32;
  99. mask = (0 - x) & BN_MASK2;
  100. mask = (0 - (mask >> (BN_BITS2 - 1)));
  101. bits += 32 & mask;
  102. l ^= (x ^ l) & mask;
  103. #endif
  104. x = l >> 16;
  105. mask = (0 - x) & BN_MASK2;
  106. mask = (0 - (mask >> (BN_BITS2 - 1)));
  107. bits += 16 & mask;
  108. l ^= (x ^ l) & mask;
  109. x = l >> 8;
  110. mask = (0 - x) & BN_MASK2;
  111. mask = (0 - (mask >> (BN_BITS2 - 1)));
  112. bits += 8 & mask;
  113. l ^= (x ^ l) & mask;
  114. x = l >> 4;
  115. mask = (0 - x) & BN_MASK2;
  116. mask = (0 - (mask >> (BN_BITS2 - 1)));
  117. bits += 4 & mask;
  118. l ^= (x ^ l) & mask;
  119. x = l >> 2;
  120. mask = (0 - x) & BN_MASK2;
  121. mask = (0 - (mask >> (BN_BITS2 - 1)));
  122. bits += 2 & mask;
  123. l ^= (x ^ l) & mask;
  124. x = l >> 1;
  125. mask = (0 - x) & BN_MASK2;
  126. mask = (0 - (mask >> (BN_BITS2 - 1)));
  127. bits += 1 & mask;
  128. return bits;
  129. }
  130. #ifdef MS_BROKEN_BN_num_bits_word
  131. # pragma optimize("", on)
  132. #endif
  133. /*
  134. * This function still leaks `a->dmax`: it's caller's responsibility to
  135. * expand the input `a` in advance to a public length.
  136. */
  137. static ossl_inline
  138. int bn_num_bits_consttime(const BIGNUM *a)
  139. {
  140. int j, ret;
  141. unsigned int mask, past_i;
  142. int i = a->top - 1;
  143. bn_check_top(a);
  144. for (j = 0, past_i = 0, ret = 0; j < a->dmax; j++) {
  145. mask = constant_time_eq_int(i, j); /* 0xff..ff if i==j, 0x0 otherwise */
  146. ret += BN_BITS2 & (~mask & ~past_i);
  147. ret += BN_num_bits_word(a->d[j]) & mask;
  148. past_i |= mask; /* past_i will become 0xff..ff after i==j */
  149. }
  150. /*
  151. * if BN_is_zero(a) => i is -1 and ret contains garbage, so we mask the
  152. * final result.
  153. */
  154. mask = ~(constant_time_eq_int(i, ((int)-1)));
  155. return ret & mask;
  156. }
  157. int BN_num_bits(const BIGNUM *a)
  158. {
  159. int i = a->top - 1;
  160. bn_check_top(a);
  161. if (a->flags & BN_FLG_CONSTTIME) {
  162. /*
  163. * We assume that BIGNUMs flagged as CONSTTIME have also been expanded
  164. * so that a->dmax is not leaking secret information.
  165. *
  166. * In other words, it's the caller's responsibility to ensure `a` has
  167. * been preallocated in advance to a public length if we hit this
  168. * branch.
  169. *
  170. */
  171. return bn_num_bits_consttime(a);
  172. }
  173. if (BN_is_zero(a))
  174. return 0;
  175. return ((i * BN_BITS2) + BN_num_bits_word(a->d[i]));
  176. }
  177. static void bn_free_d(BIGNUM *a, int clear)
  178. {
  179. if (BN_get_flags(a, BN_FLG_SECURE))
  180. OPENSSL_secure_clear_free(a->d, a->dmax * sizeof(a->d[0]));
  181. else if (clear != 0)
  182. OPENSSL_clear_free(a->d, a->dmax * sizeof(a->d[0]));
  183. else
  184. OPENSSL_free(a->d);
  185. }
  186. void BN_clear_free(BIGNUM *a)
  187. {
  188. if (a == NULL)
  189. return;
  190. if (a->d != NULL && !BN_get_flags(a, BN_FLG_STATIC_DATA))
  191. bn_free_d(a, 1);
  192. if (BN_get_flags(a, BN_FLG_MALLOCED)) {
  193. OPENSSL_cleanse(a, sizeof(*a));
  194. OPENSSL_free(a);
  195. }
  196. }
  197. void BN_free(BIGNUM *a)
  198. {
  199. if (a == NULL)
  200. return;
  201. if (!BN_get_flags(a, BN_FLG_STATIC_DATA))
  202. bn_free_d(a, 0);
  203. if (a->flags & BN_FLG_MALLOCED)
  204. OPENSSL_free(a);
  205. }
  206. void bn_init(BIGNUM *a)
  207. {
  208. static BIGNUM nilbn;
  209. *a = nilbn;
  210. bn_check_top(a);
  211. }
  212. BIGNUM *BN_new(void)
  213. {
  214. BIGNUM *ret;
  215. if ((ret = OPENSSL_zalloc(sizeof(*ret))) == NULL)
  216. return NULL;
  217. ret->flags = BN_FLG_MALLOCED;
  218. bn_check_top(ret);
  219. return ret;
  220. }
  221. BIGNUM *BN_secure_new(void)
  222. {
  223. BIGNUM *ret = BN_new();
  224. if (ret != NULL)
  225. ret->flags |= BN_FLG_SECURE;
  226. return ret;
  227. }
  228. /* This is used by bn_expand2() */
  229. /* The caller MUST check that words > b->dmax before calling this */
  230. static BN_ULONG *bn_expand_internal(const BIGNUM *b, int words)
  231. {
  232. BN_ULONG *a = NULL;
  233. if (words > (INT_MAX / (4 * BN_BITS2))) {
  234. ERR_raise(ERR_LIB_BN, BN_R_BIGNUM_TOO_LONG);
  235. return NULL;
  236. }
  237. if (BN_get_flags(b, BN_FLG_STATIC_DATA)) {
  238. ERR_raise(ERR_LIB_BN, BN_R_EXPAND_ON_STATIC_BIGNUM_DATA);
  239. return NULL;
  240. }
  241. if (BN_get_flags(b, BN_FLG_SECURE))
  242. a = OPENSSL_secure_zalloc(words * sizeof(*a));
  243. else
  244. a = OPENSSL_zalloc(words * sizeof(*a));
  245. if (a == NULL)
  246. return NULL;
  247. assert(b->top <= words);
  248. if (b->top > 0)
  249. memcpy(a, b->d, sizeof(*a) * b->top);
  250. return a;
  251. }
  252. /*
  253. * This is an internal function that should not be used in applications. It
  254. * ensures that 'b' has enough room for a 'words' word number and initialises
  255. * any unused part of b->d with leading zeros. It is mostly used by the
  256. * various BIGNUM routines. If there is an error, NULL is returned. If not,
  257. * 'b' is returned.
  258. */
  259. BIGNUM *bn_expand2(BIGNUM *b, int words)
  260. {
  261. if (words > b->dmax) {
  262. BN_ULONG *a = bn_expand_internal(b, words);
  263. if (!a)
  264. return NULL;
  265. if (b->d != NULL)
  266. bn_free_d(b, 1);
  267. b->d = a;
  268. b->dmax = words;
  269. }
  270. return b;
  271. }
  272. BIGNUM *BN_dup(const BIGNUM *a)
  273. {
  274. BIGNUM *t;
  275. if (a == NULL)
  276. return NULL;
  277. bn_check_top(a);
  278. t = BN_get_flags(a, BN_FLG_SECURE) ? BN_secure_new() : BN_new();
  279. if (t == NULL)
  280. return NULL;
  281. if (!BN_copy(t, a)) {
  282. BN_free(t);
  283. return NULL;
  284. }
  285. bn_check_top(t);
  286. return t;
  287. }
  288. BIGNUM *BN_copy(BIGNUM *a, const BIGNUM *b)
  289. {
  290. int bn_words;
  291. bn_check_top(b);
  292. bn_words = BN_get_flags(b, BN_FLG_CONSTTIME) ? b->dmax : b->top;
  293. if (a == b)
  294. return a;
  295. if (bn_wexpand(a, bn_words) == NULL)
  296. return NULL;
  297. if (b->top > 0)
  298. memcpy(a->d, b->d, sizeof(b->d[0]) * bn_words);
  299. a->neg = b->neg;
  300. a->top = b->top;
  301. a->flags |= b->flags & BN_FLG_FIXED_TOP;
  302. bn_check_top(a);
  303. return a;
  304. }
  305. #define FLAGS_DATA(flags) ((flags) & (BN_FLG_STATIC_DATA \
  306. | BN_FLG_CONSTTIME \
  307. | BN_FLG_SECURE \
  308. | BN_FLG_FIXED_TOP))
  309. #define FLAGS_STRUCT(flags) ((flags) & (BN_FLG_MALLOCED))
  310. void BN_swap(BIGNUM *a, BIGNUM *b)
  311. {
  312. int flags_old_a, flags_old_b;
  313. BN_ULONG *tmp_d;
  314. int tmp_top, tmp_dmax, tmp_neg;
  315. bn_check_top(a);
  316. bn_check_top(b);
  317. flags_old_a = a->flags;
  318. flags_old_b = b->flags;
  319. tmp_d = a->d;
  320. tmp_top = a->top;
  321. tmp_dmax = a->dmax;
  322. tmp_neg = a->neg;
  323. a->d = b->d;
  324. a->top = b->top;
  325. a->dmax = b->dmax;
  326. a->neg = b->neg;
  327. b->d = tmp_d;
  328. b->top = tmp_top;
  329. b->dmax = tmp_dmax;
  330. b->neg = tmp_neg;
  331. a->flags = FLAGS_STRUCT(flags_old_a) | FLAGS_DATA(flags_old_b);
  332. b->flags = FLAGS_STRUCT(flags_old_b) | FLAGS_DATA(flags_old_a);
  333. bn_check_top(a);
  334. bn_check_top(b);
  335. }
  336. void BN_clear(BIGNUM *a)
  337. {
  338. if (a == NULL)
  339. return;
  340. bn_check_top(a);
  341. if (a->d != NULL)
  342. OPENSSL_cleanse(a->d, sizeof(*a->d) * a->dmax);
  343. a->neg = 0;
  344. a->top = 0;
  345. a->flags &= ~BN_FLG_FIXED_TOP;
  346. }
  347. BN_ULONG BN_get_word(const BIGNUM *a)
  348. {
  349. if (a->top > 1)
  350. return BN_MASK2;
  351. else if (a->top == 1)
  352. return a->d[0];
  353. /* a->top == 0 */
  354. return 0;
  355. }
  356. int BN_set_word(BIGNUM *a, BN_ULONG w)
  357. {
  358. bn_check_top(a);
  359. if (bn_expand(a, (int)sizeof(BN_ULONG) * 8) == NULL)
  360. return 0;
  361. a->neg = 0;
  362. a->d[0] = w;
  363. a->top = (w ? 1 : 0);
  364. a->flags &= ~BN_FLG_FIXED_TOP;
  365. bn_check_top(a);
  366. return 1;
  367. }
  368. typedef enum {BIG, LITTLE} endianness_t;
  369. typedef enum {SIGNED, UNSIGNED} signedness_t;
  370. static BIGNUM *bin2bn(const unsigned char *s, int len, BIGNUM *ret,
  371. endianness_t endianness, signedness_t signedness)
  372. {
  373. int inc;
  374. const unsigned char *s2;
  375. int inc2;
  376. int neg = 0, xor = 0, carry = 0;
  377. unsigned int i;
  378. unsigned int n;
  379. BIGNUM *bn = NULL;
  380. /* Negative length is not acceptable */
  381. if (len < 0)
  382. return NULL;
  383. if (ret == NULL)
  384. ret = bn = BN_new();
  385. if (ret == NULL)
  386. return NULL;
  387. bn_check_top(ret);
  388. /*
  389. * If the input has no bits, the number is considered zero.
  390. * This makes calls with s==NULL and len==0 safe.
  391. */
  392. if (len == 0) {
  393. BN_clear(ret);
  394. return ret;
  395. }
  396. /*
  397. * The loop that does the work iterates from least to most
  398. * significant BIGNUM chunk, so we adapt parameters to transfer
  399. * input bytes accordingly.
  400. */
  401. if (endianness == LITTLE) {
  402. s2 = s + len - 1;
  403. inc2 = -1;
  404. inc = 1;
  405. } else {
  406. s2 = s;
  407. inc2 = 1;
  408. inc = -1;
  409. s += len - 1;
  410. }
  411. /* Take note of the signedness of the input bytes*/
  412. if (signedness == SIGNED) {
  413. neg = !!(*s2 & 0x80);
  414. xor = neg ? 0xff : 0x00;
  415. carry = neg;
  416. }
  417. /*
  418. * Skip leading sign extensions (the value of |xor|).
  419. * This is the only spot where |s2| and |inc2| are used.
  420. */
  421. for ( ; len > 0 && *s2 == xor; s2 += inc2, len--)
  422. continue;
  423. /*
  424. * If there was a set of 0xff, we backtrack one byte unless the next
  425. * one has a sign bit, as the last 0xff is then part of the actual
  426. * number, rather then a mere sign extension.
  427. */
  428. if (xor == 0xff) {
  429. if (len == 0 || !(*s2 & 0x80))
  430. len++;
  431. }
  432. /* If it was all zeros, we're done */
  433. if (len == 0) {
  434. ret->top = 0;
  435. return ret;
  436. }
  437. n = ((len - 1) / BN_BYTES) + 1; /* Number of resulting bignum chunks */
  438. if (bn_wexpand(ret, (int)n) == NULL) {
  439. BN_free(bn);
  440. return NULL;
  441. }
  442. ret->top = n;
  443. ret->neg = neg;
  444. for (i = 0; n-- > 0; i++) {
  445. BN_ULONG l = 0; /* Accumulator */
  446. unsigned int m = 0; /* Offset in a bignum chunk, in bits */
  447. for (; len > 0 && m < BN_BYTES * 8; len--, s += inc, m += 8) {
  448. BN_ULONG byte_xored = *s ^ xor;
  449. BN_ULONG byte = (byte_xored + carry) & 0xff;
  450. carry = byte_xored > byte; /* Implicit 1 or 0 */
  451. l |= (byte << m);
  452. }
  453. ret->d[i] = l;
  454. }
  455. /*
  456. * need to call this due to clear byte at top if avoiding having the top
  457. * bit set (-ve number)
  458. */
  459. bn_correct_top(ret);
  460. return ret;
  461. }
  462. BIGNUM *BN_bin2bn(const unsigned char *s, int len, BIGNUM *ret)
  463. {
  464. return bin2bn(s, len, ret, BIG, UNSIGNED);
  465. }
  466. BIGNUM *BN_signed_bin2bn(const unsigned char *s, int len, BIGNUM *ret)
  467. {
  468. return bin2bn(s, len, ret, BIG, SIGNED);
  469. }
  470. static int bn2binpad(const BIGNUM *a, unsigned char *to, int tolen,
  471. endianness_t endianness, signedness_t signedness)
  472. {
  473. int inc;
  474. int n, n8;
  475. int xor = 0, carry = 0, ext = 0;
  476. size_t i, lasti, j, atop, mask;
  477. BN_ULONG l;
  478. /*
  479. * In case |a| is fixed-top, BN_num_bits can return bogus length,
  480. * but it's assumed that fixed-top inputs ought to be "nominated"
  481. * even for padded output, so it works out...
  482. */
  483. n8 = BN_num_bits(a);
  484. n = (n8 + 7) / 8; /* This is what BN_num_bytes() does */
  485. /* Take note of the signedness of the bignum */
  486. if (signedness == SIGNED) {
  487. xor = a->neg ? 0xff : 0x00;
  488. carry = a->neg;
  489. /*
  490. * if |n * 8 == n|, then the MSbit is set, otherwise unset.
  491. * We must compensate with one extra byte if that doesn't
  492. * correspond to the signedness of the bignum with regards
  493. * to 2's complement.
  494. */
  495. ext = (n * 8 == n8)
  496. ? !a->neg /* MSbit set on nonnegative bignum */
  497. : a->neg; /* MSbit unset on negative bignum */
  498. }
  499. if (tolen == -1) {
  500. tolen = n + ext;
  501. } else if (tolen < n + ext) { /* uncommon/unlike case */
  502. BIGNUM temp = *a;
  503. bn_correct_top(&temp);
  504. n8 = BN_num_bits(&temp);
  505. n = (n8 + 7) / 8; /* This is what BN_num_bytes() does */
  506. if (tolen < n + ext)
  507. return -1;
  508. }
  509. /* Swipe through whole available data and don't give away padded zero. */
  510. atop = a->dmax * BN_BYTES;
  511. if (atop == 0) {
  512. if (tolen != 0)
  513. memset(to, '\0', tolen);
  514. return tolen;
  515. }
  516. /*
  517. * The loop that does the work iterates from least significant
  518. * to most significant BIGNUM limb, so we adapt parameters to
  519. * transfer output bytes accordingly.
  520. */
  521. if (endianness == LITTLE) {
  522. inc = 1;
  523. } else {
  524. inc = -1;
  525. to += tolen - 1; /* Move to the last byte, not beyond */
  526. }
  527. lasti = atop - 1;
  528. atop = a->top * BN_BYTES;
  529. for (i = 0, j = 0; j < (size_t)tolen; j++) {
  530. unsigned char byte, byte_xored;
  531. l = a->d[i / BN_BYTES];
  532. mask = 0 - ((j - atop) >> (8 * sizeof(i) - 1));
  533. byte = (unsigned char)(l >> (8 * (i % BN_BYTES)) & mask);
  534. byte_xored = byte ^ xor;
  535. *to = (unsigned char)(byte_xored + carry);
  536. carry = byte_xored > *to; /* Implicit 1 or 0 */
  537. to += inc;
  538. i += (i - lasti) >> (8 * sizeof(i) - 1); /* stay on last limb */
  539. }
  540. return tolen;
  541. }
  542. int BN_bn2binpad(const BIGNUM *a, unsigned char *to, int tolen)
  543. {
  544. if (tolen < 0)
  545. return -1;
  546. return bn2binpad(a, to, tolen, BIG, UNSIGNED);
  547. }
  548. int BN_signed_bn2bin(const BIGNUM *a, unsigned char *to, int tolen)
  549. {
  550. if (tolen < 0)
  551. return -1;
  552. return bn2binpad(a, to, tolen, BIG, SIGNED);
  553. }
  554. int BN_bn2bin(const BIGNUM *a, unsigned char *to)
  555. {
  556. return bn2binpad(a, to, -1, BIG, UNSIGNED);
  557. }
  558. BIGNUM *BN_lebin2bn(const unsigned char *s, int len, BIGNUM *ret)
  559. {
  560. return bin2bn(s, len, ret, LITTLE, UNSIGNED);
  561. }
  562. BIGNUM *BN_signed_lebin2bn(const unsigned char *s, int len, BIGNUM *ret)
  563. {
  564. return bin2bn(s, len, ret, LITTLE, SIGNED);
  565. }
  566. int BN_bn2lebinpad(const BIGNUM *a, unsigned char *to, int tolen)
  567. {
  568. if (tolen < 0)
  569. return -1;
  570. return bn2binpad(a, to, tolen, LITTLE, UNSIGNED);
  571. }
  572. int BN_signed_bn2lebin(const BIGNUM *a, unsigned char *to, int tolen)
  573. {
  574. if (tolen < 0)
  575. return -1;
  576. return bn2binpad(a, to, tolen, LITTLE, SIGNED);
  577. }
  578. BIGNUM *BN_native2bn(const unsigned char *s, int len, BIGNUM *ret)
  579. {
  580. DECLARE_IS_ENDIAN;
  581. if (IS_LITTLE_ENDIAN)
  582. return BN_lebin2bn(s, len, ret);
  583. return BN_bin2bn(s, len, ret);
  584. }
  585. BIGNUM *BN_signed_native2bn(const unsigned char *s, int len, BIGNUM *ret)
  586. {
  587. DECLARE_IS_ENDIAN;
  588. if (IS_LITTLE_ENDIAN)
  589. return BN_signed_lebin2bn(s, len, ret);
  590. return BN_signed_bin2bn(s, len, ret);
  591. }
  592. int BN_bn2nativepad(const BIGNUM *a, unsigned char *to, int tolen)
  593. {
  594. DECLARE_IS_ENDIAN;
  595. if (IS_LITTLE_ENDIAN)
  596. return BN_bn2lebinpad(a, to, tolen);
  597. return BN_bn2binpad(a, to, tolen);
  598. }
  599. int BN_signed_bn2native(const BIGNUM *a, unsigned char *to, int tolen)
  600. {
  601. DECLARE_IS_ENDIAN;
  602. if (IS_LITTLE_ENDIAN)
  603. return BN_signed_bn2lebin(a, to, tolen);
  604. return BN_signed_bn2bin(a, to, tolen);
  605. }
  606. int BN_ucmp(const BIGNUM *a, const BIGNUM *b)
  607. {
  608. int i;
  609. BN_ULONG t1, t2, *ap, *bp;
  610. bn_check_top(a);
  611. bn_check_top(b);
  612. i = a->top - b->top;
  613. if (i != 0)
  614. return i;
  615. ap = a->d;
  616. bp = b->d;
  617. for (i = a->top - 1; i >= 0; i--) {
  618. t1 = ap[i];
  619. t2 = bp[i];
  620. if (t1 != t2)
  621. return ((t1 > t2) ? 1 : -1);
  622. }
  623. return 0;
  624. }
  625. int BN_cmp(const BIGNUM *a, const BIGNUM *b)
  626. {
  627. int i;
  628. int gt, lt;
  629. BN_ULONG t1, t2;
  630. if ((a == NULL) || (b == NULL)) {
  631. if (a != NULL)
  632. return -1;
  633. else if (b != NULL)
  634. return 1;
  635. else
  636. return 0;
  637. }
  638. bn_check_top(a);
  639. bn_check_top(b);
  640. if (a->neg != b->neg) {
  641. if (a->neg)
  642. return -1;
  643. else
  644. return 1;
  645. }
  646. if (a->neg == 0) {
  647. gt = 1;
  648. lt = -1;
  649. } else {
  650. gt = -1;
  651. lt = 1;
  652. }
  653. if (a->top > b->top)
  654. return gt;
  655. if (a->top < b->top)
  656. return lt;
  657. for (i = a->top - 1; i >= 0; i--) {
  658. t1 = a->d[i];
  659. t2 = b->d[i];
  660. if (t1 > t2)
  661. return gt;
  662. if (t1 < t2)
  663. return lt;
  664. }
  665. return 0;
  666. }
  667. int BN_set_bit(BIGNUM *a, int n)
  668. {
  669. int i, j, k;
  670. if (n < 0)
  671. return 0;
  672. i = n / BN_BITS2;
  673. j = n % BN_BITS2;
  674. if (a->top <= i) {
  675. if (bn_wexpand(a, i + 1) == NULL)
  676. return 0;
  677. for (k = a->top; k < i + 1; k++)
  678. a->d[k] = 0;
  679. a->top = i + 1;
  680. a->flags &= ~BN_FLG_FIXED_TOP;
  681. }
  682. a->d[i] |= (((BN_ULONG)1) << j);
  683. bn_check_top(a);
  684. return 1;
  685. }
  686. int BN_clear_bit(BIGNUM *a, int n)
  687. {
  688. int i, j;
  689. bn_check_top(a);
  690. if (n < 0)
  691. return 0;
  692. i = n / BN_BITS2;
  693. j = n % BN_BITS2;
  694. if (a->top <= i)
  695. return 0;
  696. a->d[i] &= (~(((BN_ULONG)1) << j));
  697. bn_correct_top(a);
  698. return 1;
  699. }
  700. int BN_is_bit_set(const BIGNUM *a, int n)
  701. {
  702. int i, j;
  703. bn_check_top(a);
  704. if (n < 0)
  705. return 0;
  706. i = n / BN_BITS2;
  707. j = n % BN_BITS2;
  708. if (a->top <= i)
  709. return 0;
  710. return (int)(((a->d[i]) >> j) & ((BN_ULONG)1));
  711. }
  712. int BN_mask_bits(BIGNUM *a, int n)
  713. {
  714. int b, w;
  715. bn_check_top(a);
  716. if (n < 0)
  717. return 0;
  718. w = n / BN_BITS2;
  719. b = n % BN_BITS2;
  720. if (w >= a->top)
  721. return 0;
  722. if (b == 0)
  723. a->top = w;
  724. else {
  725. a->top = w + 1;
  726. a->d[w] &= ~(BN_MASK2 << b);
  727. }
  728. bn_correct_top(a);
  729. return 1;
  730. }
  731. void BN_set_negative(BIGNUM *a, int b)
  732. {
  733. if (b && !BN_is_zero(a))
  734. a->neg = 1;
  735. else
  736. a->neg = 0;
  737. }
  738. int bn_cmp_words(const BN_ULONG *a, const BN_ULONG *b, int n)
  739. {
  740. int i;
  741. BN_ULONG aa, bb;
  742. if (n == 0)
  743. return 0;
  744. aa = a[n - 1];
  745. bb = b[n - 1];
  746. if (aa != bb)
  747. return ((aa > bb) ? 1 : -1);
  748. for (i = n - 2; i >= 0; i--) {
  749. aa = a[i];
  750. bb = b[i];
  751. if (aa != bb)
  752. return ((aa > bb) ? 1 : -1);
  753. }
  754. return 0;
  755. }
  756. /*
  757. * Here follows a specialised variants of bn_cmp_words(). It has the
  758. * capability of performing the operation on arrays of different sizes. The
  759. * sizes of those arrays is expressed through cl, which is the common length
  760. * ( basically, min(len(a),len(b)) ), and dl, which is the delta between the
  761. * two lengths, calculated as len(a)-len(b). All lengths are the number of
  762. * BN_ULONGs...
  763. */
  764. int bn_cmp_part_words(const BN_ULONG *a, const BN_ULONG *b, int cl, int dl)
  765. {
  766. int n, i;
  767. n = cl - 1;
  768. if (dl < 0) {
  769. for (i = dl; i < 0; i++) {
  770. if (b[n - i] != 0)
  771. return -1; /* a < b */
  772. }
  773. }
  774. if (dl > 0) {
  775. for (i = dl; i > 0; i--) {
  776. if (a[n + i] != 0)
  777. return 1; /* a > b */
  778. }
  779. }
  780. return bn_cmp_words(a, b, cl);
  781. }
  782. /*-
  783. * Constant-time conditional swap of a and b.
  784. * a and b are swapped if condition is not 0.
  785. * nwords is the number of words to swap.
  786. * Assumes that at least nwords are allocated in both a and b.
  787. * Assumes that no more than nwords are used by either a or b.
  788. */
  789. void BN_consttime_swap(BN_ULONG condition, BIGNUM *a, BIGNUM *b, int nwords)
  790. {
  791. BN_ULONG t;
  792. int i;
  793. bn_wcheck_size(a, nwords);
  794. bn_wcheck_size(b, nwords);
  795. condition = ((~condition & ((condition - 1))) >> (BN_BITS2 - 1)) - 1;
  796. t = (a->top ^ b->top) & condition;
  797. a->top ^= t;
  798. b->top ^= t;
  799. t = (a->neg ^ b->neg) & condition;
  800. a->neg ^= t;
  801. b->neg ^= t;
  802. /*-
  803. * BN_FLG_STATIC_DATA: indicates that data may not be written to. Intention
  804. * is actually to treat it as it's read-only data, and some (if not most)
  805. * of it does reside in read-only segment. In other words observation of
  806. * BN_FLG_STATIC_DATA in BN_consttime_swap should be treated as fatal
  807. * condition. It would either cause SEGV or effectively cause data
  808. * corruption.
  809. *
  810. * BN_FLG_MALLOCED: refers to BN structure itself, and hence must be
  811. * preserved.
  812. *
  813. * BN_FLG_SECURE: must be preserved, because it determines how x->d was
  814. * allocated and hence how to free it.
  815. *
  816. * BN_FLG_CONSTTIME: sufficient to mask and swap
  817. *
  818. * BN_FLG_FIXED_TOP: indicates that we haven't called bn_correct_top() on
  819. * the data, so the d array may be padded with additional 0 values (i.e.
  820. * top could be greater than the minimal value that it could be). We should
  821. * be swapping it
  822. */
  823. #define BN_CONSTTIME_SWAP_FLAGS (BN_FLG_CONSTTIME | BN_FLG_FIXED_TOP)
  824. t = ((a->flags ^ b->flags) & BN_CONSTTIME_SWAP_FLAGS) & condition;
  825. a->flags ^= t;
  826. b->flags ^= t;
  827. /* conditionally swap the data */
  828. for (i = 0; i < nwords; i++) {
  829. t = (a->d[i] ^ b->d[i]) & condition;
  830. a->d[i] ^= t;
  831. b->d[i] ^= t;
  832. }
  833. }
  834. #undef BN_CONSTTIME_SWAP_FLAGS
  835. /* Bits of security, see SP800-57 */
  836. int BN_security_bits(int L, int N)
  837. {
  838. int secbits, bits;
  839. if (L >= 15360)
  840. secbits = 256;
  841. else if (L >= 7680)
  842. secbits = 192;
  843. else if (L >= 3072)
  844. secbits = 128;
  845. else if (L >= 2048)
  846. secbits = 112;
  847. else if (L >= 1024)
  848. secbits = 80;
  849. else
  850. return 0;
  851. if (N == -1)
  852. return secbits;
  853. bits = N / 2;
  854. if (bits < 80)
  855. return 0;
  856. return bits >= secbits ? secbits : bits;
  857. }
  858. void BN_zero_ex(BIGNUM *a)
  859. {
  860. a->neg = 0;
  861. a->top = 0;
  862. a->flags &= ~BN_FLG_FIXED_TOP;
  863. }
  864. int BN_abs_is_word(const BIGNUM *a, const BN_ULONG w)
  865. {
  866. return ((a->top == 1) && (a->d[0] == w)) || ((w == 0) && (a->top == 0));
  867. }
  868. int BN_is_zero(const BIGNUM *a)
  869. {
  870. return a->top == 0;
  871. }
  872. int BN_is_one(const BIGNUM *a)
  873. {
  874. return BN_abs_is_word(a, 1) && !a->neg;
  875. }
  876. int BN_is_word(const BIGNUM *a, const BN_ULONG w)
  877. {
  878. return BN_abs_is_word(a, w) && (!w || !a->neg);
  879. }
  880. int BN_is_odd(const BIGNUM *a)
  881. {
  882. return (a->top > 0) && (a->d[0] & 1);
  883. }
  884. int BN_is_negative(const BIGNUM *a)
  885. {
  886. return (a->neg != 0);
  887. }
  888. int BN_to_montgomery(BIGNUM *r, const BIGNUM *a, BN_MONT_CTX *mont,
  889. BN_CTX *ctx)
  890. {
  891. return BN_mod_mul_montgomery(r, a, &(mont->RR), mont, ctx);
  892. }
  893. void BN_with_flags(BIGNUM *dest, const BIGNUM *b, int flags)
  894. {
  895. dest->d = b->d;
  896. dest->top = b->top;
  897. dest->dmax = b->dmax;
  898. dest->neg = b->neg;
  899. dest->flags = ((dest->flags & BN_FLG_MALLOCED)
  900. | (b->flags & ~BN_FLG_MALLOCED)
  901. | BN_FLG_STATIC_DATA | flags);
  902. }
  903. BN_GENCB *BN_GENCB_new(void)
  904. {
  905. BN_GENCB *ret;
  906. if ((ret = OPENSSL_malloc(sizeof(*ret))) == NULL)
  907. return NULL;
  908. return ret;
  909. }
  910. void BN_GENCB_free(BN_GENCB *cb)
  911. {
  912. if (cb == NULL)
  913. return;
  914. OPENSSL_free(cb);
  915. }
  916. void BN_set_flags(BIGNUM *b, int n)
  917. {
  918. b->flags |= n;
  919. }
  920. int BN_get_flags(const BIGNUM *b, int n)
  921. {
  922. return b->flags & n;
  923. }
  924. /* Populate a BN_GENCB structure with an "old"-style callback */
  925. void BN_GENCB_set_old(BN_GENCB *gencb, void (*callback) (int, int, void *),
  926. void *cb_arg)
  927. {
  928. BN_GENCB *tmp_gencb = gencb;
  929. tmp_gencb->ver = 1;
  930. tmp_gencb->arg = cb_arg;
  931. tmp_gencb->cb.cb_1 = callback;
  932. }
  933. /* Populate a BN_GENCB structure with a "new"-style callback */
  934. void BN_GENCB_set(BN_GENCB *gencb, int (*callback) (int, int, BN_GENCB *),
  935. void *cb_arg)
  936. {
  937. BN_GENCB *tmp_gencb = gencb;
  938. tmp_gencb->ver = 2;
  939. tmp_gencb->arg = cb_arg;
  940. tmp_gencb->cb.cb_2 = callback;
  941. }
  942. void *BN_GENCB_get_arg(BN_GENCB *cb)
  943. {
  944. return cb->arg;
  945. }
  946. BIGNUM *bn_wexpand(BIGNUM *a, int words)
  947. {
  948. return (words <= a->dmax) ? a : bn_expand2(a, words);
  949. }
  950. void bn_correct_top_consttime(BIGNUM *a)
  951. {
  952. int j, atop;
  953. BN_ULONG limb;
  954. unsigned int mask;
  955. for (j = 0, atop = 0; j < a->dmax; j++) {
  956. limb = a->d[j];
  957. limb |= 0 - limb;
  958. limb >>= BN_BITS2 - 1;
  959. limb = 0 - limb;
  960. mask = (unsigned int)limb;
  961. mask &= constant_time_msb(j - a->top);
  962. atop = constant_time_select_int(mask, j + 1, atop);
  963. }
  964. mask = constant_time_eq_int(atop, 0);
  965. a->top = atop;
  966. a->neg = constant_time_select_int(mask, 0, a->neg);
  967. a->flags &= ~BN_FLG_FIXED_TOP;
  968. }
  969. void bn_correct_top(BIGNUM *a)
  970. {
  971. BN_ULONG *ftl;
  972. int tmp_top = a->top;
  973. if (tmp_top > 0) {
  974. for (ftl = &(a->d[tmp_top]); tmp_top > 0; tmp_top--) {
  975. ftl--;
  976. if (*ftl != 0)
  977. break;
  978. }
  979. a->top = tmp_top;
  980. }
  981. if (a->top == 0)
  982. a->neg = 0;
  983. a->flags &= ~BN_FLG_FIXED_TOP;
  984. bn_pollute(a);
  985. }