bn_mod.c 8.0 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333
  1. /*
  2. * Copyright 1998-2021 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 "internal/cryptlib.h"
  10. #include "bn_local.h"
  11. int BN_nnmod(BIGNUM *r, const BIGNUM *m, const BIGNUM *d, BN_CTX *ctx)
  12. {
  13. /*
  14. * like BN_mod, but returns non-negative remainder (i.e., 0 <= r < |d|
  15. * always holds)
  16. */
  17. if (r == d) {
  18. ERR_raise(ERR_LIB_BN, ERR_R_PASSED_INVALID_ARGUMENT);
  19. return 0;
  20. }
  21. if (!(BN_mod(r, m, d, ctx)))
  22. return 0;
  23. if (!r->neg)
  24. return 1;
  25. /* now -|d| < r < 0, so we have to set r := r + |d| */
  26. return (d->neg ? BN_sub : BN_add) (r, r, d);
  27. }
  28. int BN_mod_add(BIGNUM *r, const BIGNUM *a, const BIGNUM *b, const BIGNUM *m,
  29. BN_CTX *ctx)
  30. {
  31. if (!BN_add(r, a, b))
  32. return 0;
  33. return BN_nnmod(r, r, m, ctx);
  34. }
  35. /*
  36. * BN_mod_add variant that may be used if both a and b are non-negative and
  37. * less than m. The original algorithm was
  38. *
  39. * if (!BN_uadd(r, a, b))
  40. * return 0;
  41. * if (BN_ucmp(r, m) >= 0)
  42. * return BN_usub(r, r, m);
  43. *
  44. * which is replaced with addition, subtracting modulus, and conditional
  45. * move depending on whether or not subtraction borrowed.
  46. */
  47. int bn_mod_add_fixed_top(BIGNUM *r, const BIGNUM *a, const BIGNUM *b,
  48. const BIGNUM *m)
  49. {
  50. size_t i, ai, bi, mtop = m->top;
  51. BN_ULONG storage[1024 / BN_BITS2];
  52. BN_ULONG carry, temp, mask, *rp, *tp = storage;
  53. const BN_ULONG *ap, *bp;
  54. if (bn_wexpand(r, mtop) == NULL)
  55. return 0;
  56. if (mtop > sizeof(storage) / sizeof(storage[0])) {
  57. tp = OPENSSL_malloc(mtop * sizeof(BN_ULONG));
  58. if (tp == NULL)
  59. return 0;
  60. }
  61. ap = a->d != NULL ? a->d : tp;
  62. bp = b->d != NULL ? b->d : tp;
  63. for (i = 0, ai = 0, bi = 0, carry = 0; i < mtop;) {
  64. mask = (BN_ULONG)0 - ((i - a->top) >> (8 * sizeof(i) - 1));
  65. temp = ((ap[ai] & mask) + carry) & BN_MASK2;
  66. carry = (temp < carry);
  67. mask = (BN_ULONG)0 - ((i - b->top) >> (8 * sizeof(i) - 1));
  68. tp[i] = ((bp[bi] & mask) + temp) & BN_MASK2;
  69. carry += (tp[i] < temp);
  70. i++;
  71. ai += (i - a->dmax) >> (8 * sizeof(i) - 1);
  72. bi += (i - b->dmax) >> (8 * sizeof(i) - 1);
  73. }
  74. rp = r->d;
  75. carry -= bn_sub_words(rp, tp, m->d, mtop);
  76. for (i = 0; i < mtop; i++) {
  77. rp[i] = (carry & tp[i]) | (~carry & rp[i]);
  78. ((volatile BN_ULONG *)tp)[i] = 0;
  79. }
  80. r->top = mtop;
  81. r->flags |= BN_FLG_FIXED_TOP;
  82. r->neg = 0;
  83. if (tp != storage)
  84. OPENSSL_free(tp);
  85. return 1;
  86. }
  87. int BN_mod_add_quick(BIGNUM *r, const BIGNUM *a, const BIGNUM *b,
  88. const BIGNUM *m)
  89. {
  90. int ret = bn_mod_add_fixed_top(r, a, b, m);
  91. if (ret)
  92. bn_correct_top(r);
  93. return ret;
  94. }
  95. int BN_mod_sub(BIGNUM *r, const BIGNUM *a, const BIGNUM *b, const BIGNUM *m,
  96. BN_CTX *ctx)
  97. {
  98. if (!BN_sub(r, a, b))
  99. return 0;
  100. return BN_nnmod(r, r, m, ctx);
  101. }
  102. /*
  103. * BN_mod_sub variant that may be used if both a and b are non-negative,
  104. * a is less than m, while b is of same bit width as m. It's implemented
  105. * as subtraction followed by two conditional additions.
  106. *
  107. * 0 <= a < m
  108. * 0 <= b < 2^w < 2*m
  109. *
  110. * after subtraction
  111. *
  112. * -2*m < r = a - b < m
  113. *
  114. * Thus it takes up to two conditional additions to make |r| positive.
  115. */
  116. int bn_mod_sub_fixed_top(BIGNUM *r, const BIGNUM *a, const BIGNUM *b,
  117. const BIGNUM *m)
  118. {
  119. size_t i, ai, bi, mtop = m->top;
  120. BN_ULONG borrow, carry, ta, tb, mask, *rp;
  121. const BN_ULONG *ap, *bp;
  122. if (bn_wexpand(r, mtop) == NULL)
  123. return 0;
  124. rp = r->d;
  125. ap = a->d != NULL ? a->d : rp;
  126. bp = b->d != NULL ? b->d : rp;
  127. for (i = 0, ai = 0, bi = 0, borrow = 0; i < mtop;) {
  128. mask = (BN_ULONG)0 - ((i - a->top) >> (8 * sizeof(i) - 1));
  129. ta = ap[ai] & mask;
  130. mask = (BN_ULONG)0 - ((i - b->top) >> (8 * sizeof(i) - 1));
  131. tb = bp[bi] & mask;
  132. rp[i] = ta - tb - borrow;
  133. if (ta != tb)
  134. borrow = (ta < tb);
  135. i++;
  136. ai += (i - a->dmax) >> (8 * sizeof(i) - 1);
  137. bi += (i - b->dmax) >> (8 * sizeof(i) - 1);
  138. }
  139. ap = m->d;
  140. for (i = 0, mask = 0 - borrow, carry = 0; i < mtop; i++) {
  141. ta = ((ap[i] & mask) + carry) & BN_MASK2;
  142. carry = (ta < carry);
  143. rp[i] = (rp[i] + ta) & BN_MASK2;
  144. carry += (rp[i] < ta);
  145. }
  146. borrow -= carry;
  147. for (i = 0, mask = 0 - borrow, carry = 0; i < mtop; i++) {
  148. ta = ((ap[i] & mask) + carry) & BN_MASK2;
  149. carry = (ta < carry);
  150. rp[i] = (rp[i] + ta) & BN_MASK2;
  151. carry += (rp[i] < ta);
  152. }
  153. r->top = mtop;
  154. r->flags |= BN_FLG_FIXED_TOP;
  155. r->neg = 0;
  156. return 1;
  157. }
  158. /*
  159. * BN_mod_sub variant that may be used if both a and b are non-negative and
  160. * less than m
  161. */
  162. int BN_mod_sub_quick(BIGNUM *r, const BIGNUM *a, const BIGNUM *b,
  163. const BIGNUM *m)
  164. {
  165. if (r == m) {
  166. ERR_raise(ERR_LIB_BN, ERR_R_PASSED_INVALID_ARGUMENT);
  167. return 0;
  168. }
  169. if (!BN_sub(r, a, b))
  170. return 0;
  171. if (r->neg)
  172. return BN_add(r, r, m);
  173. return 1;
  174. }
  175. /* slow but works */
  176. int BN_mod_mul(BIGNUM *r, const BIGNUM *a, const BIGNUM *b, const BIGNUM *m,
  177. BN_CTX *ctx)
  178. {
  179. BIGNUM *t;
  180. int ret = 0;
  181. bn_check_top(a);
  182. bn_check_top(b);
  183. bn_check_top(m);
  184. BN_CTX_start(ctx);
  185. if ((t = BN_CTX_get(ctx)) == NULL)
  186. goto err;
  187. if (a == b) {
  188. if (!BN_sqr(t, a, ctx))
  189. goto err;
  190. } else {
  191. if (!BN_mul(t, a, b, ctx))
  192. goto err;
  193. }
  194. if (!BN_nnmod(r, t, m, ctx))
  195. goto err;
  196. bn_check_top(r);
  197. ret = 1;
  198. err:
  199. BN_CTX_end(ctx);
  200. return ret;
  201. }
  202. int BN_mod_sqr(BIGNUM *r, const BIGNUM *a, const BIGNUM *m, BN_CTX *ctx)
  203. {
  204. if (!BN_sqr(r, a, ctx))
  205. return 0;
  206. /* r->neg == 0, thus we don't need BN_nnmod */
  207. return BN_mod(r, r, m, ctx);
  208. }
  209. int BN_mod_lshift1(BIGNUM *r, const BIGNUM *a, const BIGNUM *m, BN_CTX *ctx)
  210. {
  211. if (!BN_lshift1(r, a))
  212. return 0;
  213. bn_check_top(r);
  214. return BN_nnmod(r, r, m, ctx);
  215. }
  216. /*
  217. * BN_mod_lshift1 variant that may be used if a is non-negative and less than
  218. * m
  219. */
  220. int BN_mod_lshift1_quick(BIGNUM *r, const BIGNUM *a, const BIGNUM *m)
  221. {
  222. if (!BN_lshift1(r, a))
  223. return 0;
  224. bn_check_top(r);
  225. if (BN_cmp(r, m) >= 0)
  226. return BN_sub(r, r, m);
  227. return 1;
  228. }
  229. int BN_mod_lshift(BIGNUM *r, const BIGNUM *a, int n, const BIGNUM *m,
  230. BN_CTX *ctx)
  231. {
  232. BIGNUM *abs_m = NULL;
  233. int ret;
  234. if (!BN_nnmod(r, a, m, ctx))
  235. return 0;
  236. if (m->neg) {
  237. abs_m = BN_dup(m);
  238. if (abs_m == NULL)
  239. return 0;
  240. abs_m->neg = 0;
  241. }
  242. ret = BN_mod_lshift_quick(r, r, n, (abs_m ? abs_m : m));
  243. bn_check_top(r);
  244. BN_free(abs_m);
  245. return ret;
  246. }
  247. /*
  248. * BN_mod_lshift variant that may be used if a is non-negative and less than
  249. * m
  250. */
  251. int BN_mod_lshift_quick(BIGNUM *r, const BIGNUM *a, int n, const BIGNUM *m)
  252. {
  253. if (r != a) {
  254. if (BN_copy(r, a) == NULL)
  255. return 0;
  256. }
  257. while (n > 0) {
  258. int max_shift;
  259. /* 0 < r < m */
  260. max_shift = BN_num_bits(m) - BN_num_bits(r);
  261. /* max_shift >= 0 */
  262. if (max_shift < 0) {
  263. ERR_raise(ERR_LIB_BN, BN_R_INPUT_NOT_REDUCED);
  264. return 0;
  265. }
  266. if (max_shift > n)
  267. max_shift = n;
  268. if (max_shift) {
  269. if (!BN_lshift(r, r, max_shift))
  270. return 0;
  271. n -= max_shift;
  272. } else {
  273. if (!BN_lshift1(r, r))
  274. return 0;
  275. --n;
  276. }
  277. /* BN_num_bits(r) <= BN_num_bits(m) */
  278. if (BN_cmp(r, m) >= 0) {
  279. if (!BN_sub(r, r, m))
  280. return 0;
  281. }
  282. }
  283. bn_check_top(r);
  284. return 1;
  285. }