bn_recp.c 4.4 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192
  1. /*
  2. * Copyright 1995-2018 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. void BN_RECP_CTX_init(BN_RECP_CTX *recp)
  12. {
  13. memset(recp, 0, sizeof(*recp));
  14. bn_init(&(recp->N));
  15. bn_init(&(recp->Nr));
  16. }
  17. BN_RECP_CTX *BN_RECP_CTX_new(void)
  18. {
  19. BN_RECP_CTX *ret;
  20. if ((ret = OPENSSL_zalloc(sizeof(*ret))) == NULL)
  21. return NULL;
  22. bn_init(&(ret->N));
  23. bn_init(&(ret->Nr));
  24. ret->flags = BN_FLG_MALLOCED;
  25. return ret;
  26. }
  27. void BN_RECP_CTX_free(BN_RECP_CTX *recp)
  28. {
  29. if (recp == NULL)
  30. return;
  31. BN_free(&recp->N);
  32. BN_free(&recp->Nr);
  33. if (recp->flags & BN_FLG_MALLOCED)
  34. OPENSSL_free(recp);
  35. }
  36. int BN_RECP_CTX_set(BN_RECP_CTX *recp, const BIGNUM *d, BN_CTX *ctx)
  37. {
  38. if (!BN_copy(&(recp->N), d))
  39. return 0;
  40. BN_zero(&(recp->Nr));
  41. recp->num_bits = BN_num_bits(d);
  42. recp->shift = 0;
  43. return 1;
  44. }
  45. int BN_mod_mul_reciprocal(BIGNUM *r, const BIGNUM *x, const BIGNUM *y,
  46. BN_RECP_CTX *recp, BN_CTX *ctx)
  47. {
  48. int ret = 0;
  49. BIGNUM *a;
  50. const BIGNUM *ca;
  51. BN_CTX_start(ctx);
  52. if ((a = BN_CTX_get(ctx)) == NULL)
  53. goto err;
  54. if (y != NULL) {
  55. if (x == y) {
  56. if (!BN_sqr(a, x, ctx))
  57. goto err;
  58. } else {
  59. if (!BN_mul(a, x, y, ctx))
  60. goto err;
  61. }
  62. ca = a;
  63. } else
  64. ca = x; /* Just do the mod */
  65. ret = BN_div_recp(NULL, r, ca, recp, ctx);
  66. err:
  67. BN_CTX_end(ctx);
  68. bn_check_top(r);
  69. return ret;
  70. }
  71. int BN_div_recp(BIGNUM *dv, BIGNUM *rem, const BIGNUM *m,
  72. BN_RECP_CTX *recp, BN_CTX *ctx)
  73. {
  74. int i, j, ret = 0;
  75. BIGNUM *a, *b, *d, *r;
  76. BN_CTX_start(ctx);
  77. d = (dv != NULL) ? dv : BN_CTX_get(ctx);
  78. r = (rem != NULL) ? rem : BN_CTX_get(ctx);
  79. a = BN_CTX_get(ctx);
  80. b = BN_CTX_get(ctx);
  81. if (b == NULL)
  82. goto err;
  83. if (BN_ucmp(m, &(recp->N)) < 0) {
  84. BN_zero(d);
  85. if (!BN_copy(r, m)) {
  86. BN_CTX_end(ctx);
  87. return 0;
  88. }
  89. BN_CTX_end(ctx);
  90. return 1;
  91. }
  92. /*
  93. * We want the remainder Given input of ABCDEF / ab we need multiply
  94. * ABCDEF by 3 digests of the reciprocal of ab
  95. */
  96. /* i := max(BN_num_bits(m), 2*BN_num_bits(N)) */
  97. i = BN_num_bits(m);
  98. j = recp->num_bits << 1;
  99. if (j > i)
  100. i = j;
  101. /* Nr := round(2^i / N) */
  102. if (i != recp->shift)
  103. recp->shift = BN_reciprocal(&(recp->Nr), &(recp->N), i, ctx);
  104. /* BN_reciprocal could have returned -1 for an error */
  105. if (recp->shift == -1)
  106. goto err;
  107. /*-
  108. * d := |round(round(m / 2^BN_num_bits(N)) * recp->Nr / 2^(i - BN_num_bits(N)))|
  109. * = |round(round(m / 2^BN_num_bits(N)) * round(2^i / N) / 2^(i - BN_num_bits(N)))|
  110. * <= |(m / 2^BN_num_bits(N)) * (2^i / N) * (2^BN_num_bits(N) / 2^i)|
  111. * = |m/N|
  112. */
  113. if (!BN_rshift(a, m, recp->num_bits))
  114. goto err;
  115. if (!BN_mul(b, a, &(recp->Nr), ctx))
  116. goto err;
  117. if (!BN_rshift(d, b, i - recp->num_bits))
  118. goto err;
  119. d->neg = 0;
  120. if (!BN_mul(b, &(recp->N), d, ctx))
  121. goto err;
  122. if (!BN_usub(r, m, b))
  123. goto err;
  124. r->neg = 0;
  125. j = 0;
  126. while (BN_ucmp(r, &(recp->N)) >= 0) {
  127. if (j++ > 2) {
  128. BNerr(BN_F_BN_DIV_RECP, BN_R_BAD_RECIPROCAL);
  129. goto err;
  130. }
  131. if (!BN_usub(r, r, &(recp->N)))
  132. goto err;
  133. if (!BN_add_word(d, 1))
  134. goto err;
  135. }
  136. r->neg = BN_is_zero(r) ? 0 : m->neg;
  137. d->neg = m->neg ^ recp->N.neg;
  138. ret = 1;
  139. err:
  140. BN_CTX_end(ctx);
  141. bn_check_top(dv);
  142. bn_check_top(rem);
  143. return ret;
  144. }
  145. /*
  146. * len is the expected size of the result We actually calculate with an extra
  147. * word of precision, so we can do faster division if the remainder is not
  148. * required.
  149. */
  150. /* r := 2^len / m */
  151. int BN_reciprocal(BIGNUM *r, const BIGNUM *m, int len, BN_CTX *ctx)
  152. {
  153. int ret = -1;
  154. BIGNUM *t;
  155. BN_CTX_start(ctx);
  156. if ((t = BN_CTX_get(ctx)) == NULL)
  157. goto err;
  158. if (!BN_set_bit(t, len))
  159. goto err;
  160. if (!BN_div(r, NULL, t, m, ctx))
  161. goto err;
  162. ret = len;
  163. err:
  164. bn_check_top(r);
  165. BN_CTX_end(ctx);
  166. return ret;
  167. }