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