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 | |
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 | |