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