bn_mod.c 4.4 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201
  1. /*
  2. * Copyright 1998-2016 The OpenSSL Project Authors. All Rights Reserved.
  3. *
  4. * Licensed under the OpenSSL license (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_lcl.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 (!(BN_mod(r, m, d, ctx)))
  18. return 0;
  19. if (!r->neg)
  20. return 1;
  21. /* now -|d| < r < 0, so we have to set r := r + |d| */
  22. return (d->neg ? BN_sub : BN_add) (r, r, d);
  23. }
  24. int BN_mod_add(BIGNUM *r, const BIGNUM *a, const BIGNUM *b, const BIGNUM *m,
  25. BN_CTX *ctx)
  26. {
  27. if (!BN_add(r, a, b))
  28. return 0;
  29. return BN_nnmod(r, r, m, ctx);
  30. }
  31. /*
  32. * BN_mod_add variant that may be used if both a and b are non-negative and
  33. * less than m
  34. */
  35. int BN_mod_add_quick(BIGNUM *r, const BIGNUM *a, const BIGNUM *b,
  36. const BIGNUM *m)
  37. {
  38. if (!BN_uadd(r, a, b))
  39. return 0;
  40. if (BN_ucmp(r, m) >= 0)
  41. return BN_usub(r, r, m);
  42. return 1;
  43. }
  44. int BN_mod_sub(BIGNUM *r, const BIGNUM *a, const BIGNUM *b, const BIGNUM *m,
  45. BN_CTX *ctx)
  46. {
  47. if (!BN_sub(r, a, b))
  48. return 0;
  49. return BN_nnmod(r, r, m, ctx);
  50. }
  51. /*
  52. * BN_mod_sub variant that may be used if both a and b are non-negative and
  53. * less than m
  54. */
  55. int BN_mod_sub_quick(BIGNUM *r, const BIGNUM *a, const BIGNUM *b,
  56. const BIGNUM *m)
  57. {
  58. if (!BN_sub(r, a, b))
  59. return 0;
  60. if (r->neg)
  61. return BN_add(r, r, m);
  62. return 1;
  63. }
  64. /* slow but works */
  65. int BN_mod_mul(BIGNUM *r, const BIGNUM *a, const BIGNUM *b, const BIGNUM *m,
  66. BN_CTX *ctx)
  67. {
  68. BIGNUM *t;
  69. int ret = 0;
  70. bn_check_top(a);
  71. bn_check_top(b);
  72. bn_check_top(m);
  73. BN_CTX_start(ctx);
  74. if ((t = BN_CTX_get(ctx)) == NULL)
  75. goto err;
  76. if (a == b) {
  77. if (!BN_sqr(t, a, ctx))
  78. goto err;
  79. } else {
  80. if (!BN_mul(t, a, b, ctx))
  81. goto err;
  82. }
  83. if (!BN_nnmod(r, t, m, ctx))
  84. goto err;
  85. bn_check_top(r);
  86. ret = 1;
  87. err:
  88. BN_CTX_end(ctx);
  89. return ret;
  90. }
  91. int BN_mod_sqr(BIGNUM *r, const BIGNUM *a, const BIGNUM *m, BN_CTX *ctx)
  92. {
  93. if (!BN_sqr(r, a, ctx))
  94. return 0;
  95. /* r->neg == 0, thus we don't need BN_nnmod */
  96. return BN_mod(r, r, m, ctx);
  97. }
  98. int BN_mod_lshift1(BIGNUM *r, const BIGNUM *a, const BIGNUM *m, BN_CTX *ctx)
  99. {
  100. if (!BN_lshift1(r, a))
  101. return 0;
  102. bn_check_top(r);
  103. return BN_nnmod(r, r, m, ctx);
  104. }
  105. /*
  106. * BN_mod_lshift1 variant that may be used if a is non-negative and less than
  107. * m
  108. */
  109. int BN_mod_lshift1_quick(BIGNUM *r, const BIGNUM *a, const BIGNUM *m)
  110. {
  111. if (!BN_lshift1(r, a))
  112. return 0;
  113. bn_check_top(r);
  114. if (BN_cmp(r, m) >= 0)
  115. return BN_sub(r, r, m);
  116. return 1;
  117. }
  118. int BN_mod_lshift(BIGNUM *r, const BIGNUM *a, int n, const BIGNUM *m,
  119. BN_CTX *ctx)
  120. {
  121. BIGNUM *abs_m = NULL;
  122. int ret;
  123. if (!BN_nnmod(r, a, m, ctx))
  124. return 0;
  125. if (m->neg) {
  126. abs_m = BN_dup(m);
  127. if (abs_m == NULL)
  128. return 0;
  129. abs_m->neg = 0;
  130. }
  131. ret = BN_mod_lshift_quick(r, r, n, (abs_m ? abs_m : m));
  132. bn_check_top(r);
  133. BN_free(abs_m);
  134. return ret;
  135. }
  136. /*
  137. * BN_mod_lshift variant that may be used if a is non-negative and less than
  138. * m
  139. */
  140. int BN_mod_lshift_quick(BIGNUM *r, const BIGNUM *a, int n, const BIGNUM *m)
  141. {
  142. if (r != a) {
  143. if (BN_copy(r, a) == NULL)
  144. return 0;
  145. }
  146. while (n > 0) {
  147. int max_shift;
  148. /* 0 < r < m */
  149. max_shift = BN_num_bits(m) - BN_num_bits(r);
  150. /* max_shift >= 0 */
  151. if (max_shift < 0) {
  152. BNerr(BN_F_BN_MOD_LSHIFT_QUICK, BN_R_INPUT_NOT_REDUCED);
  153. return 0;
  154. }
  155. if (max_shift > n)
  156. max_shift = n;
  157. if (max_shift) {
  158. if (!BN_lshift(r, r, max_shift))
  159. return 0;
  160. n -= max_shift;
  161. } else {
  162. if (!BN_lshift1(r, r))
  163. return 0;
  164. --n;
  165. }
  166. /* BN_num_bits(r) <= BN_num_bits(m) */
  167. if (BN_cmp(r, m) >= 0) {
  168. if (!BN_sub(r, r, m))
  169. return 0;
  170. }
  171. }
  172. bn_check_top(r);
  173. return 1;
  174. }