summaryrefslogtreecommitdiff
path: root/src/lib/libcrypto/bn/bn_sqrt.c
diff options
context:
space:
mode:
authortb <>2023-04-11 10:08:44 +0000
committertb <>2023-04-11 10:08:44 +0000
commit2fc970f40eeb1044a661fa924f93ab9668d3910c (patch)
tree1a8331f19d48335fd135b93854c36f2ea3244918 /src/lib/libcrypto/bn/bn_sqrt.c
parent8ba2869b3fad78a19522d1476fb6f12dc9bee1c3 (diff)
downloadopenbsd-2fc970f40eeb1044a661fa924f93ab9668d3910c.tar.gz
openbsd-2fc970f40eeb1044a661fa924f93ab9668d3910c.tar.bz2
openbsd-2fc970f40eeb1044a661fa924f93ab9668d3910c.zip
Add a new implementation of BN_mod_sqrt()
This is a reimplementation from scratch of the Tonelli-Shanks algorithm based on Henri Cohen "A Course in Computational Algebraic Number Theory", Springer GTM 138, section 1.5.1. It is API compatible with the previous implementation, so no documentation change is required. Contrary to the old implementation, this does not have any infinite loops and has various additional sanity checks to prevent misbehavior in case the input modulus is not a prime. It contains extensive comments and the individual parts of the algorithm are split into digestible chunks instead of having one huge function. One difference of note is that it BN_mod_sqrt() now always returns the smaller of the two possible answers. In other words, while its core is non-deterministic, its answer is not. ok jsing
Diffstat (limited to 'src/lib/libcrypto/bn/bn_sqrt.c')
-rw-r--r--src/lib/libcrypto/bn/bn_sqrt.c409
1 files changed, 0 insertions, 409 deletions
diff --git a/src/lib/libcrypto/bn/bn_sqrt.c b/src/lib/libcrypto/bn/bn_sqrt.c
deleted file mode 100644
index 3d9f017f59..0000000000
--- a/src/lib/libcrypto/bn/bn_sqrt.c
+++ /dev/null
@@ -1,409 +0,0 @@
1/* $OpenBSD: bn_sqrt.c,v 1.16 2023/03/27 10:25:02 tb Exp $ */
2/* Written by Lenka Fibikova <fibikova@exp-math.uni-essen.de>
3 * and Bodo Moeller for the OpenSSL project. */
4/* ====================================================================
5 * Copyright (c) 1998-2000 The OpenSSL Project. All rights reserved.
6 *
7 * Redistribution and use in source and binary forms, with or without
8 * modification, are permitted provided that the following conditions
9 * are met:
10 *
11 * 1. Redistributions of source code must retain the above copyright
12 * notice, this list of conditions and the following disclaimer.
13 *
14 * 2. Redistributions in binary form must reproduce the above copyright
15 * notice, this list of conditions and the following disclaimer in
16 * the documentation and/or other materials provided with the
17 * distribution.
18 *
19 * 3. All advertising materials mentioning features or use of this
20 * software must display the following acknowledgment:
21 * "This product includes software developed by the OpenSSL Project
22 * for use in the OpenSSL Toolkit. (http://www.openssl.org/)"
23 *
24 * 4. The names "OpenSSL Toolkit" and "OpenSSL Project" must not be used to
25 * endorse or promote products derived from this software without
26 * prior written permission. For written permission, please contact
27 * openssl-core@openssl.org.
28 *
29 * 5. Products derived from this software may not be called "OpenSSL"
30 * nor may "OpenSSL" appear in their names without prior written
31 * permission of the OpenSSL Project.
32 *
33 * 6. Redistributions of any form whatsoever must retain the following
34 * acknowledgment:
35 * "This product includes software developed by the OpenSSL Project
36 * for use in the OpenSSL Toolkit (http://www.openssl.org/)"
37 *
38 * THIS SOFTWARE IS PROVIDED BY THE OpenSSL PROJECT ``AS IS'' AND ANY
39 * EXPRESSED OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
40 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
41 * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE OpenSSL PROJECT OR
42 * ITS CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
43 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
44 * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
45 * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
46 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
47 * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
48 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED
49 * OF THE POSSIBILITY OF SUCH DAMAGE.
50 * ====================================================================
51 *
52 * This product includes cryptographic software written by Eric Young
53 * (eay@cryptsoft.com). This product includes software written by Tim
54 * Hudson (tjh@cryptsoft.com).
55 *
56 */
57
58#include <openssl/err.h>
59
60#include "bn_local.h"
61
62/*
63 * Returns 'ret' such that ret^2 == a (mod p), if it exists, using the
64 * Tonelli-Shanks algorithm following Henri Cohen, "A Course in Computational
65 * Algebraic Number Theory", algorithm 1.5.1, Springer, Berlin, 1996.
66 *
67 * Note: 'p' must be prime!
68 */
69
70BIGNUM *
71BN_mod_sqrt(BIGNUM *in, const BIGNUM *a, const BIGNUM *p, BN_CTX *ctx)
72{
73 BIGNUM *ret = in;
74 int err = 1;
75 int r;
76 BIGNUM *A, *b, *q, *t, *x, *y;
77 int e, i, j;
78
79 if (!BN_is_odd(p) || BN_abs_is_word(p, 1)) {
80 if (BN_abs_is_word(p, 2)) {
81 if (ret == NULL)
82 ret = BN_new();
83 if (ret == NULL)
84 goto end;
85 if (!BN_set_word(ret, BN_is_bit_set(a, 0))) {
86 if (ret != in)
87 BN_free(ret);
88 return NULL;
89 }
90 return ret;
91 }
92
93 BNerror(BN_R_P_IS_NOT_PRIME);
94 return (NULL);
95 }
96
97 if (BN_is_zero(a) || BN_is_one(a)) {
98 if (ret == NULL)
99 ret = BN_new();
100 if (ret == NULL)
101 goto end;
102 if (!BN_set_word(ret, BN_is_one(a))) {
103 if (ret != in)
104 BN_free(ret);
105 return NULL;
106 }
107 return ret;
108 }
109
110 BN_CTX_start(ctx);
111 if ((A = BN_CTX_get(ctx)) == NULL)
112 goto end;
113 if ((b = BN_CTX_get(ctx)) == NULL)
114 goto end;
115 if ((q = BN_CTX_get(ctx)) == NULL)
116 goto end;
117 if ((t = BN_CTX_get(ctx)) == NULL)
118 goto end;
119 if ((x = BN_CTX_get(ctx)) == NULL)
120 goto end;
121 if ((y = BN_CTX_get(ctx)) == NULL)
122 goto end;
123
124 if (ret == NULL)
125 ret = BN_new();
126 if (ret == NULL)
127 goto end;
128
129 /* A = a mod p */
130 if (!BN_nnmod(A, a, p, ctx))
131 goto end;
132
133 /* now write |p| - 1 as 2^e*q where q is odd */
134 e = 1;
135 while (!BN_is_bit_set(p, e))
136 e++;
137 /* we'll set q later (if needed) */
138
139 if (e == 1) {
140 /* The easy case: (|p|-1)/2 is odd, so 2 has an inverse
141 * modulo (|p|-1)/2, and square roots can be computed
142 * directly by modular exponentiation.
143 * We have
144 * 2 * (|p|+1)/4 == 1 (mod (|p|-1)/2),
145 * so we can use exponent (|p|+1)/4, i.e. (|p|-3)/4 + 1.
146 */
147 if (!BN_rshift(q, p, 2))
148 goto end;
149 q->neg = 0;
150 if (!BN_add_word(q, 1))
151 goto end;
152 if (!BN_mod_exp_ct(ret, A, q, p, ctx))
153 goto end;
154 err = 0;
155 goto vrfy;
156 }
157
158 if (e == 2) {
159 /* |p| == 5 (mod 8)
160 *
161 * In this case 2 is always a non-square since
162 * Legendre(2,p) = (-1)^((p^2-1)/8) for any odd prime.
163 * So if a really is a square, then 2*a is a non-square.
164 * Thus for
165 * b := (2*a)^((|p|-5)/8),
166 * i := (2*a)*b^2
167 * we have
168 * i^2 = (2*a)^((1 + (|p|-5)/4)*2)
169 * = (2*a)^((p-1)/2)
170 * = -1;
171 * so if we set
172 * x := a*b*(i-1),
173 * then
174 * x^2 = a^2 * b^2 * (i^2 - 2*i + 1)
175 * = a^2 * b^2 * (-2*i)
176 * = a*(-i)*(2*a*b^2)
177 * = a*(-i)*i
178 * = a.
179 *
180 * (This is due to A.O.L. Atkin,
181 * <URL: http://listserv.nodak.edu/scripts/wa.exe?A2=ind9211&L=nmbrthry&O=T&P=562>,
182 * November 1992.)
183 */
184
185 /* t := 2*a */
186 if (!BN_mod_lshift1_quick(t, A, p))
187 goto end;
188
189 /* b := (2*a)^((|p|-5)/8) */
190 if (!BN_rshift(q, p, 3))
191 goto end;
192 q->neg = 0;
193 if (!BN_mod_exp_ct(b, t, q, p, ctx))
194 goto end;
195
196 /* y := b^2 */
197 if (!BN_mod_sqr(y, b, p, ctx))
198 goto end;
199
200 /* t := (2*a)*b^2 - 1*/
201 if (!BN_mod_mul(t, t, y, p, ctx))
202 goto end;
203 if (!BN_sub_word(t, 1))
204 goto end;
205
206 /* x = a*b*t */
207 if (!BN_mod_mul(x, A, b, p, ctx))
208 goto end;
209 if (!BN_mod_mul(x, x, t, p, ctx))
210 goto end;
211
212 if (!bn_copy(ret, x))
213 goto end;
214 err = 0;
215 goto vrfy;
216 }
217
218 /* e > 2, so we really have to use the Tonelli/Shanks algorithm.
219 * First, find some y that is not a square. */
220 if (!bn_copy(q, p)) /* use 'q' as temp */
221 goto end;
222 q->neg = 0;
223 i = 2;
224 do {
225 /* For efficiency, try small numbers first;
226 * if this fails, try random numbers.
227 */
228 if (i < 22) {
229 if (!BN_set_word(y, i))
230 goto end;
231 } else {
232 if (!BN_pseudo_rand(y, BN_num_bits(p), 0, 0))
233 goto end;
234 if (BN_ucmp(y, p) >= 0) {
235 if (p->neg) {
236 if (!BN_add(y, y, p))
237 goto end;
238 } else {
239 if (!BN_sub(y, y, p))
240 goto end;
241 }
242 }
243 /* now 0 <= y < |p| */
244 if (BN_is_zero(y))
245 if (!BN_set_word(y, i))
246 goto end;
247 }
248
249 r = BN_kronecker(y, q, ctx); /* here 'q' is |p| */
250 if (r < -1)
251 goto end;
252 if (r == 0) {
253 /* m divides p */
254 BNerror(BN_R_P_IS_NOT_PRIME);
255 goto end;
256 }
257 } while (r == 1 && ++i < 82);
258
259 if (r != -1) {
260 /* Many rounds and still no non-square -- this is more likely
261 * a bug than just bad luck.
262 * Even if p is not prime, we should have found some y
263 * such that r == -1.
264 */
265 BNerror(BN_R_TOO_MANY_ITERATIONS);
266 goto end;
267 }
268
269 /* Here's our actual 'q': */
270 if (!BN_rshift(q, q, e))
271 goto end;
272
273 /* Now that we have some non-square, we can find an element
274 * of order 2^e by computing its q'th power. */
275 if (!BN_mod_exp_ct(y, y, q, p, ctx))
276 goto end;
277 if (BN_is_one(y)) {
278 BNerror(BN_R_P_IS_NOT_PRIME);
279 goto end;
280 }
281
282 /* Now we know that (if p is indeed prime) there is an integer
283 * k, 0 <= k < 2^e, such that
284 *
285 * a^q * y^k == 1 (mod p).
286 *
287 * As a^q is a square and y is not, k must be even.
288 * q+1 is even, too, so there is an element
289 *
290 * X := a^((q+1)/2) * y^(k/2),
291 *
292 * and it satisfies
293 *
294 * X^2 = a^q * a * y^k
295 * = a,
296 *
297 * so it is the square root that we are looking for.
298 */
299
300 /* t := (q-1)/2 (note that q is odd) */
301 if (!BN_rshift1(t, q))
302 goto end;
303
304 /* x := a^((q-1)/2) */
305 if (BN_is_zero(t)) { /* special case: p = 2^e + 1 */
306 if (!BN_nnmod(t, A, p, ctx))
307 goto end;
308 if (BN_is_zero(t)) {
309 /* special case: a == 0 (mod p) */
310 BN_zero(ret);
311 err = 0;
312 goto end;
313 } else if (!BN_one(x))
314 goto end;
315 } else {
316 if (!BN_mod_exp_ct(x, A, t, p, ctx))
317 goto end;
318 if (BN_is_zero(x)) {
319 /* special case: a == 0 (mod p) */
320 BN_zero(ret);
321 err = 0;
322 goto end;
323 }
324 }
325
326 /* b := a*x^2 (= a^q) */
327 if (!BN_mod_sqr(b, x, p, ctx))
328 goto end;
329 if (!BN_mod_mul(b, b, A, p, ctx))
330 goto end;
331
332 /* x := a*x (= a^((q+1)/2)) */
333 if (!BN_mod_mul(x, x, A, p, ctx))
334 goto end;
335
336 while (1) {
337 /* Now b is a^q * y^k for some even k (0 <= k < 2^E
338 * where E refers to the original value of e, which we
339 * don't keep in a variable), and x is a^((q+1)/2) * y^(k/2).
340 *
341 * We have a*b = x^2,
342 * y^2^(e-1) = -1,
343 * b^2^(e-1) = 1.
344 */
345
346 if (BN_is_one(b)) {
347 if (!bn_copy(ret, x))
348 goto end;
349 err = 0;
350 goto vrfy;
351 }
352
353 /* Find the smallest i with 0 < i < e such that b^(2^i) = 1. */
354 for (i = 1; i < e; i++) {
355 if (i == 1) {
356 if (!BN_mod_sqr(t, b, p, ctx))
357 goto end;
358 } else {
359 if (!BN_mod_sqr(t, t, p, ctx))
360 goto end;
361 }
362 if (BN_is_one(t))
363 break;
364 }
365 if (i >= e) {
366 BNerror(BN_R_NOT_A_SQUARE);
367 goto end;
368 }
369
370 /* t := y^2^(e - i - 1) */
371 if (!bn_copy(t, y))
372 goto end;
373 for (j = e - i - 1; j > 0; j--) {
374 if (!BN_mod_sqr(t, t, p, ctx))
375 goto end;
376 }
377 if (!BN_mod_mul(y, t, t, p, ctx))
378 goto end;
379 if (!BN_mod_mul(x, x, t, p, ctx))
380 goto end;
381 if (!BN_mod_mul(b, b, y, p, ctx))
382 goto end;
383 e = i;
384 }
385
386vrfy:
387 if (!err) {
388 /* verify the result -- the input might have been not a square
389 * (test added in 0.9.8) */
390
391 if (!BN_mod_sqr(x, ret, p, ctx))
392 err = 1;
393
394 if (!err && 0 != BN_cmp(x, A)) {
395 BNerror(BN_R_NOT_A_SQUARE);
396 err = 1;
397 }
398 }
399
400end:
401 if (err) {
402 if (ret != NULL && ret != in) {
403 BN_free(ret);
404 }
405 ret = NULL;
406 }
407 BN_CTX_end(ctx);
408 return ret;
409}
generated by cgit v1.2.3-55-g6feb (git 2.39.1) at 2025-10-08 02:10:12 +0000