bn_sqr.c 5.4 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239
  1. /*
  2. * Copyright 1995-2018 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. /* r must not be a */
  12. /*
  13. * I've just gone over this and it is now %20 faster on x86 - eay - 27 Jun 96
  14. */
  15. int BN_sqr(BIGNUM *r, const BIGNUM *a, BN_CTX *ctx)
  16. {
  17. int ret = bn_sqr_fixed_top(r, a, ctx);
  18. bn_correct_top(r);
  19. bn_check_top(r);
  20. return ret;
  21. }
  22. int bn_sqr_fixed_top(BIGNUM *r, const BIGNUM *a, BN_CTX *ctx)
  23. {
  24. int max, al;
  25. int ret = 0;
  26. BIGNUM *tmp, *rr;
  27. bn_check_top(a);
  28. al = a->top;
  29. if (al <= 0) {
  30. r->top = 0;
  31. r->neg = 0;
  32. return 1;
  33. }
  34. BN_CTX_start(ctx);
  35. rr = (a != r) ? r : BN_CTX_get(ctx);
  36. tmp = BN_CTX_get(ctx);
  37. if (rr == NULL || tmp == NULL)
  38. goto err;
  39. max = 2 * al; /* Non-zero (from above) */
  40. if (bn_wexpand(rr, max) == NULL)
  41. goto err;
  42. if (al == 4) {
  43. #ifndef BN_SQR_COMBA
  44. BN_ULONG t[8];
  45. bn_sqr_normal(rr->d, a->d, 4, t);
  46. #else
  47. bn_sqr_comba4(rr->d, a->d);
  48. #endif
  49. } else if (al == 8) {
  50. #ifndef BN_SQR_COMBA
  51. BN_ULONG t[16];
  52. bn_sqr_normal(rr->d, a->d, 8, t);
  53. #else
  54. bn_sqr_comba8(rr->d, a->d);
  55. #endif
  56. } else {
  57. #if defined(BN_RECURSION)
  58. if (al < BN_SQR_RECURSIVE_SIZE_NORMAL) {
  59. BN_ULONG t[BN_SQR_RECURSIVE_SIZE_NORMAL * 2];
  60. bn_sqr_normal(rr->d, a->d, al, t);
  61. } else {
  62. int j, k;
  63. j = BN_num_bits_word((BN_ULONG)al);
  64. j = 1 << (j - 1);
  65. k = j + j;
  66. if (al == j) {
  67. if (bn_wexpand(tmp, k * 2) == NULL)
  68. goto err;
  69. bn_sqr_recursive(rr->d, a->d, al, tmp->d);
  70. } else {
  71. if (bn_wexpand(tmp, max) == NULL)
  72. goto err;
  73. bn_sqr_normal(rr->d, a->d, al, tmp->d);
  74. }
  75. }
  76. #else
  77. if (bn_wexpand(tmp, max) == NULL)
  78. goto err;
  79. bn_sqr_normal(rr->d, a->d, al, tmp->d);
  80. #endif
  81. }
  82. rr->neg = 0;
  83. rr->top = max;
  84. rr->flags |= BN_FLG_FIXED_TOP;
  85. if (r != rr && BN_copy(r, rr) == NULL)
  86. goto err;
  87. ret = 1;
  88. err:
  89. bn_check_top(rr);
  90. bn_check_top(tmp);
  91. BN_CTX_end(ctx);
  92. return ret;
  93. }
  94. /* tmp must have 2*n words */
  95. void bn_sqr_normal(BN_ULONG *r, const BN_ULONG *a, int n, BN_ULONG *tmp)
  96. {
  97. int i, j, max;
  98. const BN_ULONG *ap;
  99. BN_ULONG *rp;
  100. max = n * 2;
  101. ap = a;
  102. rp = r;
  103. rp[0] = rp[max - 1] = 0;
  104. rp++;
  105. j = n;
  106. if (--j > 0) {
  107. ap++;
  108. rp[j] = bn_mul_words(rp, ap, j, ap[-1]);
  109. rp += 2;
  110. }
  111. for (i = n - 2; i > 0; i--) {
  112. j--;
  113. ap++;
  114. rp[j] = bn_mul_add_words(rp, ap, j, ap[-1]);
  115. rp += 2;
  116. }
  117. bn_add_words(r, r, r, max);
  118. /* There will not be a carry */
  119. bn_sqr_words(tmp, a, n);
  120. bn_add_words(r, r, tmp, max);
  121. }
  122. #ifdef BN_RECURSION
  123. /*-
  124. * r is 2*n words in size,
  125. * a and b are both n words in size. (There's not actually a 'b' here ...)
  126. * n must be a power of 2.
  127. * We multiply and return the result.
  128. * t must be 2*n words in size
  129. * We calculate
  130. * a[0]*b[0]
  131. * a[0]*b[0]+a[1]*b[1]+(a[0]-a[1])*(b[1]-b[0])
  132. * a[1]*b[1]
  133. */
  134. void bn_sqr_recursive(BN_ULONG *r, const BN_ULONG *a, int n2, BN_ULONG *t)
  135. {
  136. int n = n2 / 2;
  137. int zero, c1;
  138. BN_ULONG ln, lo, *p;
  139. if (n2 == 4) {
  140. # ifndef BN_SQR_COMBA
  141. bn_sqr_normal(r, a, 4, t);
  142. # else
  143. bn_sqr_comba4(r, a);
  144. # endif
  145. return;
  146. } else if (n2 == 8) {
  147. # ifndef BN_SQR_COMBA
  148. bn_sqr_normal(r, a, 8, t);
  149. # else
  150. bn_sqr_comba8(r, a);
  151. # endif
  152. return;
  153. }
  154. if (n2 < BN_SQR_RECURSIVE_SIZE_NORMAL) {
  155. bn_sqr_normal(r, a, n2, t);
  156. return;
  157. }
  158. /* r=(a[0]-a[1])*(a[1]-a[0]) */
  159. c1 = bn_cmp_words(a, &(a[n]), n);
  160. zero = 0;
  161. if (c1 > 0)
  162. bn_sub_words(t, a, &(a[n]), n);
  163. else if (c1 < 0)
  164. bn_sub_words(t, &(a[n]), a, n);
  165. else
  166. zero = 1;
  167. /* The result will always be negative unless it is zero */
  168. p = &(t[n2 * 2]);
  169. if (!zero)
  170. bn_sqr_recursive(&(t[n2]), t, n, p);
  171. else
  172. memset(&t[n2], 0, sizeof(*t) * n2);
  173. bn_sqr_recursive(r, a, n, p);
  174. bn_sqr_recursive(&(r[n2]), &(a[n]), n, p);
  175. /*-
  176. * t[32] holds (a[0]-a[1])*(a[1]-a[0]), it is negative or zero
  177. * r[10] holds (a[0]*b[0])
  178. * r[32] holds (b[1]*b[1])
  179. */
  180. c1 = (int)(bn_add_words(t, r, &(r[n2]), n2));
  181. /* t[32] is negative */
  182. c1 -= (int)(bn_sub_words(&(t[n2]), t, &(t[n2]), n2));
  183. /*-
  184. * t[32] holds (a[0]-a[1])*(a[1]-a[0])+(a[0]*a[0])+(a[1]*a[1])
  185. * r[10] holds (a[0]*a[0])
  186. * r[32] holds (a[1]*a[1])
  187. * c1 holds the carry bits
  188. */
  189. c1 += (int)(bn_add_words(&(r[n]), &(r[n]), &(t[n2]), n2));
  190. if (c1) {
  191. p = &(r[n + n2]);
  192. lo = *p;
  193. ln = (lo + c1) & BN_MASK2;
  194. *p = ln;
  195. /*
  196. * The overflow will stop before we over write words we should not
  197. * overwrite
  198. */
  199. if (ln < (BN_ULONG)c1) {
  200. do {
  201. p++;
  202. lo = *p;
  203. ln = (lo + 1) & BN_MASK2;
  204. *p = ln;
  205. } while (ln == 0);
  206. }
  207. }
  208. }
  209. #endif