2
0

bn_mont.c 12 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467
  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. /*
  10. * Details about Montgomery multiplication algorithms can be found at
  11. * http://security.ece.orst.edu/publications.html, e.g.
  12. * http://security.ece.orst.edu/koc/papers/j37acmon.pdf and
  13. * sections 3.8 and 4.2 in http://security.ece.orst.edu/koc/papers/r01rsasw.pdf
  14. */
  15. #include "internal/cryptlib.h"
  16. #include "bn_local.h"
  17. #define MONT_WORD /* use the faster word-based algorithm */
  18. #ifdef MONT_WORD
  19. static int bn_from_montgomery_word(BIGNUM *ret, BIGNUM *r, BN_MONT_CTX *mont);
  20. #endif
  21. int BN_mod_mul_montgomery(BIGNUM *r, const BIGNUM *a, const BIGNUM *b,
  22. BN_MONT_CTX *mont, BN_CTX *ctx)
  23. {
  24. int ret = bn_mul_mont_fixed_top(r, a, b, mont, ctx);
  25. bn_correct_top(r);
  26. bn_check_top(r);
  27. return ret;
  28. }
  29. int bn_mul_mont_fixed_top(BIGNUM *r, const BIGNUM *a, const BIGNUM *b,
  30. BN_MONT_CTX *mont, BN_CTX *ctx)
  31. {
  32. BIGNUM *tmp;
  33. int ret = 0;
  34. int num = mont->N.top;
  35. #if defined(OPENSSL_BN_ASM_MONT) && defined(MONT_WORD)
  36. if (num > 1 && num <= BN_SOFT_LIMIT && a->top == num && b->top == num) {
  37. if (bn_wexpand(r, num) == NULL)
  38. return 0;
  39. if (bn_mul_mont(r->d, a->d, b->d, mont->N.d, mont->n0, num)) {
  40. r->neg = a->neg ^ b->neg;
  41. r->top = num;
  42. r->flags |= BN_FLG_FIXED_TOP;
  43. return 1;
  44. }
  45. }
  46. #endif
  47. if ((a->top + b->top) > 2 * num)
  48. return 0;
  49. BN_CTX_start(ctx);
  50. tmp = BN_CTX_get(ctx);
  51. if (tmp == NULL)
  52. goto err;
  53. bn_check_top(tmp);
  54. if (a == b) {
  55. if (!bn_sqr_fixed_top(tmp, a, ctx))
  56. goto err;
  57. } else {
  58. if (!bn_mul_fixed_top(tmp, a, b, ctx))
  59. goto err;
  60. }
  61. /* reduce from aRR to aR */
  62. #ifdef MONT_WORD
  63. if (!bn_from_montgomery_word(r, tmp, mont))
  64. goto err;
  65. #else
  66. if (!BN_from_montgomery(r, tmp, mont, ctx))
  67. goto err;
  68. #endif
  69. ret = 1;
  70. err:
  71. BN_CTX_end(ctx);
  72. return ret;
  73. }
  74. #ifdef MONT_WORD
  75. static int bn_from_montgomery_word(BIGNUM *ret, BIGNUM *r, BN_MONT_CTX *mont)
  76. {
  77. BIGNUM *n;
  78. BN_ULONG *ap, *np, *rp, n0, v, carry;
  79. int nl, max, i;
  80. unsigned int rtop;
  81. n = &(mont->N);
  82. nl = n->top;
  83. if (nl == 0) {
  84. ret->top = 0;
  85. return 1;
  86. }
  87. max = (2 * nl); /* carry is stored separately */
  88. if (bn_wexpand(r, max) == NULL)
  89. return 0;
  90. r->neg ^= n->neg;
  91. np = n->d;
  92. rp = r->d;
  93. /* clear the top words of T */
  94. for (rtop = r->top, i = 0; i < max; i++) {
  95. v = (BN_ULONG)0 - ((i - rtop) >> (8 * sizeof(rtop) - 1));
  96. rp[i] &= v;
  97. }
  98. r->top = max;
  99. r->flags |= BN_FLG_FIXED_TOP;
  100. n0 = mont->n0[0];
  101. /*
  102. * Add multiples of |n| to |r| until R = 2^(nl * BN_BITS2) divides it. On
  103. * input, we had |r| < |n| * R, so now |r| < 2 * |n| * R. Note that |r|
  104. * includes |carry| which is stored separately.
  105. */
  106. for (carry = 0, i = 0; i < nl; i++, rp++) {
  107. v = bn_mul_add_words(rp, np, nl, (rp[0] * n0) & BN_MASK2);
  108. v = (v + carry + rp[nl]) & BN_MASK2;
  109. carry |= (v != rp[nl]);
  110. carry &= (v <= rp[nl]);
  111. rp[nl] = v;
  112. }
  113. if (bn_wexpand(ret, nl) == NULL)
  114. return 0;
  115. ret->top = nl;
  116. ret->flags |= BN_FLG_FIXED_TOP;
  117. ret->neg = r->neg;
  118. rp = ret->d;
  119. /*
  120. * Shift |nl| words to divide by R. We have |ap| < 2 * |n|. Note that |ap|
  121. * includes |carry| which is stored separately.
  122. */
  123. ap = &(r->d[nl]);
  124. carry -= bn_sub_words(rp, ap, np, nl);
  125. /*
  126. * |carry| is -1 if |ap| - |np| underflowed or zero if it did not. Note
  127. * |carry| cannot be 1. That would imply the subtraction did not fit in
  128. * |nl| words, and we know at most one subtraction is needed.
  129. */
  130. for (i = 0; i < nl; i++) {
  131. rp[i] = (carry & ap[i]) | (~carry & rp[i]);
  132. ap[i] = 0;
  133. }
  134. return 1;
  135. }
  136. #endif /* MONT_WORD */
  137. int BN_from_montgomery(BIGNUM *ret, const BIGNUM *a, BN_MONT_CTX *mont,
  138. BN_CTX *ctx)
  139. {
  140. int retn;
  141. retn = bn_from_mont_fixed_top(ret, a, mont, ctx);
  142. bn_correct_top(ret);
  143. bn_check_top(ret);
  144. return retn;
  145. }
  146. int bn_from_mont_fixed_top(BIGNUM *ret, const BIGNUM *a, BN_MONT_CTX *mont,
  147. BN_CTX *ctx)
  148. {
  149. int retn = 0;
  150. #ifdef MONT_WORD
  151. BIGNUM *t;
  152. BN_CTX_start(ctx);
  153. if ((t = BN_CTX_get(ctx)) && BN_copy(t, a)) {
  154. retn = bn_from_montgomery_word(ret, t, mont);
  155. }
  156. BN_CTX_end(ctx);
  157. #else /* !MONT_WORD */
  158. BIGNUM *t1, *t2;
  159. BN_CTX_start(ctx);
  160. t1 = BN_CTX_get(ctx);
  161. t2 = BN_CTX_get(ctx);
  162. if (t2 == NULL)
  163. goto err;
  164. if (!BN_copy(t1, a))
  165. goto err;
  166. BN_mask_bits(t1, mont->ri);
  167. if (!BN_mul(t2, t1, &mont->Ni, ctx))
  168. goto err;
  169. BN_mask_bits(t2, mont->ri);
  170. if (!BN_mul(t1, t2, &mont->N, ctx))
  171. goto err;
  172. if (!BN_add(t2, a, t1))
  173. goto err;
  174. if (!BN_rshift(ret, t2, mont->ri))
  175. goto err;
  176. if (BN_ucmp(ret, &(mont->N)) >= 0) {
  177. if (!BN_usub(ret, ret, &(mont->N)))
  178. goto err;
  179. }
  180. retn = 1;
  181. bn_check_top(ret);
  182. err:
  183. BN_CTX_end(ctx);
  184. #endif /* MONT_WORD */
  185. return retn;
  186. }
  187. int bn_to_mont_fixed_top(BIGNUM *r, const BIGNUM *a, BN_MONT_CTX *mont,
  188. BN_CTX *ctx)
  189. {
  190. return bn_mul_mont_fixed_top(r, a, &(mont->RR), mont, ctx);
  191. }
  192. BN_MONT_CTX *BN_MONT_CTX_new(void)
  193. {
  194. BN_MONT_CTX *ret;
  195. if ((ret = OPENSSL_malloc(sizeof(*ret))) == NULL)
  196. return NULL;
  197. BN_MONT_CTX_init(ret);
  198. ret->flags = BN_FLG_MALLOCED;
  199. return ret;
  200. }
  201. void BN_MONT_CTX_init(BN_MONT_CTX *ctx)
  202. {
  203. ctx->ri = 0;
  204. bn_init(&ctx->RR);
  205. bn_init(&ctx->N);
  206. bn_init(&ctx->Ni);
  207. ctx->n0[0] = ctx->n0[1] = 0;
  208. ctx->flags = 0;
  209. }
  210. void BN_MONT_CTX_free(BN_MONT_CTX *mont)
  211. {
  212. if (mont == NULL)
  213. return;
  214. BN_clear_free(&mont->RR);
  215. BN_clear_free(&mont->N);
  216. BN_clear_free(&mont->Ni);
  217. if (mont->flags & BN_FLG_MALLOCED)
  218. OPENSSL_free(mont);
  219. }
  220. int BN_MONT_CTX_set(BN_MONT_CTX *mont, const BIGNUM *mod, BN_CTX *ctx)
  221. {
  222. int i, ret = 0;
  223. BIGNUM *Ri, *R;
  224. if (BN_is_zero(mod))
  225. return 0;
  226. BN_CTX_start(ctx);
  227. if ((Ri = BN_CTX_get(ctx)) == NULL)
  228. goto err;
  229. R = &(mont->RR); /* grab RR as a temp */
  230. if (!BN_copy(&(mont->N), mod))
  231. goto err; /* Set N */
  232. if (BN_get_flags(mod, BN_FLG_CONSTTIME) != 0)
  233. BN_set_flags(&(mont->N), BN_FLG_CONSTTIME);
  234. mont->N.neg = 0;
  235. #ifdef MONT_WORD
  236. {
  237. BIGNUM tmod;
  238. BN_ULONG buf[2];
  239. bn_init(&tmod);
  240. tmod.d = buf;
  241. tmod.dmax = 2;
  242. tmod.neg = 0;
  243. if (BN_get_flags(mod, BN_FLG_CONSTTIME) != 0)
  244. BN_set_flags(&tmod, BN_FLG_CONSTTIME);
  245. mont->ri = (BN_num_bits(mod) + (BN_BITS2 - 1)) / BN_BITS2 * BN_BITS2;
  246. # if defined(OPENSSL_BN_ASM_MONT) && (BN_BITS2<=32)
  247. /*
  248. * Only certain BN_BITS2<=32 platforms actually make use of n0[1],
  249. * and we could use the #else case (with a shorter R value) for the
  250. * others. However, currently only the assembler files do know which
  251. * is which.
  252. */
  253. BN_zero(R);
  254. if (!(BN_set_bit(R, 2 * BN_BITS2)))
  255. goto err;
  256. tmod.top = 0;
  257. if ((buf[0] = mod->d[0]))
  258. tmod.top = 1;
  259. if ((buf[1] = mod->top > 1 ? mod->d[1] : 0))
  260. tmod.top = 2;
  261. if (BN_is_one(&tmod))
  262. BN_zero(Ri);
  263. else if ((BN_mod_inverse(Ri, R, &tmod, ctx)) == NULL)
  264. goto err;
  265. if (!BN_lshift(Ri, Ri, 2 * BN_BITS2))
  266. goto err; /* R*Ri */
  267. if (!BN_is_zero(Ri)) {
  268. if (!BN_sub_word(Ri, 1))
  269. goto err;
  270. } else { /* if N mod word size == 1 */
  271. if (bn_expand(Ri, (int)sizeof(BN_ULONG) * 2) == NULL)
  272. goto err;
  273. /* Ri-- (mod double word size) */
  274. Ri->neg = 0;
  275. Ri->d[0] = BN_MASK2;
  276. Ri->d[1] = BN_MASK2;
  277. Ri->top = 2;
  278. }
  279. if (!BN_div(Ri, NULL, Ri, &tmod, ctx))
  280. goto err;
  281. /*
  282. * Ni = (R*Ri-1)/N, keep only couple of least significant words:
  283. */
  284. mont->n0[0] = (Ri->top > 0) ? Ri->d[0] : 0;
  285. mont->n0[1] = (Ri->top > 1) ? Ri->d[1] : 0;
  286. # else
  287. BN_zero(R);
  288. if (!(BN_set_bit(R, BN_BITS2)))
  289. goto err; /* R */
  290. buf[0] = mod->d[0]; /* tmod = N mod word size */
  291. buf[1] = 0;
  292. tmod.top = buf[0] != 0 ? 1 : 0;
  293. /* Ri = R^-1 mod N */
  294. if (BN_is_one(&tmod))
  295. BN_zero(Ri);
  296. else if ((BN_mod_inverse(Ri, R, &tmod, ctx)) == NULL)
  297. goto err;
  298. if (!BN_lshift(Ri, Ri, BN_BITS2))
  299. goto err; /* R*Ri */
  300. if (!BN_is_zero(Ri)) {
  301. if (!BN_sub_word(Ri, 1))
  302. goto err;
  303. } else { /* if N mod word size == 1 */
  304. if (!BN_set_word(Ri, BN_MASK2))
  305. goto err; /* Ri-- (mod word size) */
  306. }
  307. if (!BN_div(Ri, NULL, Ri, &tmod, ctx))
  308. goto err;
  309. /*
  310. * Ni = (R*Ri-1)/N, keep only least significant word:
  311. */
  312. mont->n0[0] = (Ri->top > 0) ? Ri->d[0] : 0;
  313. mont->n0[1] = 0;
  314. # endif
  315. }
  316. #else /* !MONT_WORD */
  317. { /* bignum version */
  318. mont->ri = BN_num_bits(&mont->N);
  319. BN_zero(R);
  320. if (!BN_set_bit(R, mont->ri))
  321. goto err; /* R = 2^ri */
  322. /* Ri = R^-1 mod N */
  323. if ((BN_mod_inverse(Ri, R, &mont->N, ctx)) == NULL)
  324. goto err;
  325. if (!BN_lshift(Ri, Ri, mont->ri))
  326. goto err; /* R*Ri */
  327. if (!BN_sub_word(Ri, 1))
  328. goto err;
  329. /*
  330. * Ni = (R*Ri-1) / N
  331. */
  332. if (!BN_div(&(mont->Ni), NULL, Ri, &mont->N, ctx))
  333. goto err;
  334. }
  335. #endif
  336. /* setup RR for conversions */
  337. BN_zero(&(mont->RR));
  338. if (!BN_set_bit(&(mont->RR), mont->ri * 2))
  339. goto err;
  340. if (!BN_mod(&(mont->RR), &(mont->RR), &(mont->N), ctx))
  341. goto err;
  342. for (i = mont->RR.top, ret = mont->N.top; i < ret; i++)
  343. mont->RR.d[i] = 0;
  344. mont->RR.top = ret;
  345. mont->RR.flags |= BN_FLG_FIXED_TOP;
  346. ret = 1;
  347. err:
  348. BN_CTX_end(ctx);
  349. return ret;
  350. }
  351. BN_MONT_CTX *BN_MONT_CTX_copy(BN_MONT_CTX *to, BN_MONT_CTX *from)
  352. {
  353. if (to == from)
  354. return to;
  355. if (!BN_copy(&(to->RR), &(from->RR)))
  356. return NULL;
  357. if (!BN_copy(&(to->N), &(from->N)))
  358. return NULL;
  359. if (!BN_copy(&(to->Ni), &(from->Ni)))
  360. return NULL;
  361. to->ri = from->ri;
  362. to->n0[0] = from->n0[0];
  363. to->n0[1] = from->n0[1];
  364. return to;
  365. }
  366. BN_MONT_CTX *BN_MONT_CTX_set_locked(BN_MONT_CTX **pmont, CRYPTO_RWLOCK *lock,
  367. const BIGNUM *mod, BN_CTX *ctx)
  368. {
  369. BN_MONT_CTX *ret;
  370. if (!CRYPTO_THREAD_read_lock(lock))
  371. return NULL;
  372. ret = *pmont;
  373. CRYPTO_THREAD_unlock(lock);
  374. if (ret)
  375. return ret;
  376. /*
  377. * We don't want to serialize globally while doing our lazy-init math in
  378. * BN_MONT_CTX_set. That punishes threads that are doing independent
  379. * things. Instead, punish the case where more than one thread tries to
  380. * lazy-init the same 'pmont', by having each do the lazy-init math work
  381. * independently and only use the one from the thread that wins the race
  382. * (the losers throw away the work they've done).
  383. */
  384. ret = BN_MONT_CTX_new();
  385. if (ret == NULL)
  386. return NULL;
  387. if (!BN_MONT_CTX_set(ret, mod, ctx)) {
  388. BN_MONT_CTX_free(ret);
  389. return NULL;
  390. }
  391. /* The locked compare-and-set, after the local work is done. */
  392. if (!CRYPTO_THREAD_write_lock(lock)) {
  393. BN_MONT_CTX_free(ret);
  394. return NULL;
  395. }
  396. if (*pmont) {
  397. BN_MONT_CTX_free(ret);
  398. ret = *pmont;
  399. } else
  400. *pmont = ret;
  401. CRYPTO_THREAD_unlock(lock);
  402. return ret;
  403. }