summaryrefslogtreecommitdiff
path: root/src/lib/libssl/src/crypto/bn/bn_sqrt.c
diff options
context:
space:
mode:
Diffstat (limited to 'src/lib/libssl/src/crypto/bn/bn_sqrt.c')
-rw-r--r--src/lib/libssl/src/crypto/bn/bn_sqrt.c76
1 files changed, 41 insertions, 35 deletions
diff --git a/src/lib/libssl/src/crypto/bn/bn_sqrt.c b/src/lib/libssl/src/crypto/bn/bn_sqrt.c
index e2a1105dc8..6beaf9e5e5 100644
--- a/src/lib/libssl/src/crypto/bn/bn_sqrt.c
+++ b/src/lib/libssl/src/crypto/bn/bn_sqrt.c
@@ -1,4 +1,4 @@
1/* crypto/bn/bn_mod.c */ 1/* crypto/bn/bn_sqrt.c */
2/* Written by Lenka Fibikova <fibikova@exp-math.uni-essen.de> 2/* Written by Lenka Fibikova <fibikova@exp-math.uni-essen.de>
3 * and Bodo Moeller for the OpenSSL project. */ 3 * and Bodo Moeller for the OpenSSL project. */
4/* ==================================================================== 4/* ====================================================================
@@ -65,14 +65,12 @@ BIGNUM *BN_mod_sqrt(BIGNUM *in, const BIGNUM *a, const BIGNUM *p, BN_CTX *ctx)
65 * using the Tonelli/Shanks algorithm (cf. Henri Cohen, "A Course 65 * using the Tonelli/Shanks algorithm (cf. Henri Cohen, "A Course
66 * in Algebraic Computational Number Theory", algorithm 1.5.1). 66 * in Algebraic Computational Number Theory", algorithm 1.5.1).
67 * 'p' must be prime! 67 * 'p' must be prime!
68 * If 'a' is not a square, this is not necessarily detected by
69 * the algorithms; a bogus result must be expected in this case.
70 */ 68 */
71 { 69 {
72 BIGNUM *ret = in; 70 BIGNUM *ret = in;
73 int err = 1; 71 int err = 1;
74 int r; 72 int r;
75 BIGNUM *b, *q, *t, *x, *y; 73 BIGNUM *A, *b, *q, *t, *x, *y;
76 int e, i, j; 74 int e, i, j;
77 75
78 if (!BN_is_odd(p) || BN_abs_is_word(p, 1)) 76 if (!BN_is_odd(p) || BN_abs_is_word(p, 1))
@@ -85,9 +83,11 @@ BIGNUM *BN_mod_sqrt(BIGNUM *in, const BIGNUM *a, const BIGNUM *p, BN_CTX *ctx)
85 goto end; 83 goto end;
86 if (!BN_set_word(ret, BN_is_bit_set(a, 0))) 84 if (!BN_set_word(ret, BN_is_bit_set(a, 0)))
87 { 85 {
88 BN_free(ret); 86 if (ret != in)
87 BN_free(ret);
89 return NULL; 88 return NULL;
90 } 89 }
90 bn_check_top(ret);
91 return ret; 91 return ret;
92 } 92 }
93 93
@@ -103,23 +103,16 @@ BIGNUM *BN_mod_sqrt(BIGNUM *in, const BIGNUM *a, const BIGNUM *p, BN_CTX *ctx)
103 goto end; 103 goto end;
104 if (!BN_set_word(ret, BN_is_one(a))) 104 if (!BN_set_word(ret, BN_is_one(a)))
105 { 105 {
106 BN_free(ret); 106 if (ret != in)
107 BN_free(ret);
107 return NULL; 108 return NULL;
108 } 109 }
110 bn_check_top(ret);
109 return ret; 111 return ret;
110 } 112 }
111 113
112#if 0 /* if BN_mod_sqrt is used with correct input, this just wastes time */
113 r = BN_kronecker(a, p, ctx);
114 if (r < -1) return NULL;
115 if (r == -1)
116 {
117 BNerr(BN_F_BN_MOD_SQRT, BN_R_NOT_A_SQUARE);
118 return(NULL);
119 }
120#endif
121
122 BN_CTX_start(ctx); 114 BN_CTX_start(ctx);
115 A = BN_CTX_get(ctx);
123 b = BN_CTX_get(ctx); 116 b = BN_CTX_get(ctx);
124 q = BN_CTX_get(ctx); 117 q = BN_CTX_get(ctx);
125 t = BN_CTX_get(ctx); 118 t = BN_CTX_get(ctx);
@@ -131,6 +124,9 @@ BIGNUM *BN_mod_sqrt(BIGNUM *in, const BIGNUM *a, const BIGNUM *p, BN_CTX *ctx)
131 ret = BN_new(); 124 ret = BN_new();
132 if (ret == NULL) goto end; 125 if (ret == NULL) goto end;
133 126
127 /* A = a mod p */
128 if (!BN_nnmod(A, a, p, ctx)) goto end;
129
134 /* now write |p| - 1 as 2^e*q where q is odd */ 130 /* now write |p| - 1 as 2^e*q where q is odd */
135 e = 1; 131 e = 1;
136 while (!BN_is_bit_set(p, e)) 132 while (!BN_is_bit_set(p, e))
@@ -149,9 +145,9 @@ BIGNUM *BN_mod_sqrt(BIGNUM *in, const BIGNUM *a, const BIGNUM *p, BN_CTX *ctx)
149 if (!BN_rshift(q, p, 2)) goto end; 145 if (!BN_rshift(q, p, 2)) goto end;
150 q->neg = 0; 146 q->neg = 0;
151 if (!BN_add_word(q, 1)) goto end; 147 if (!BN_add_word(q, 1)) goto end;
152 if (!BN_mod_exp(ret, a, q, p, ctx)) goto end; 148 if (!BN_mod_exp(ret, A, q, p, ctx)) goto end;
153 err = 0; 149 err = 0;
154 goto end; 150 goto vrfy;
155 } 151 }
156 152
157 if (e == 2) 153 if (e == 2)
@@ -182,15 +178,8 @@ BIGNUM *BN_mod_sqrt(BIGNUM *in, const BIGNUM *a, const BIGNUM *p, BN_CTX *ctx)
182 * November 1992.) 178 * November 1992.)
183 */ 179 */
184 180
185 /* make sure that a is reduced modulo p */
186 if (a->neg || BN_ucmp(a, p) >= 0)
187 {
188 if (!BN_nnmod(x, a, p, ctx)) goto end;
189 a = x; /* use x as temporary variable */
190 }
191
192 /* t := 2*a */ 181 /* t := 2*a */
193 if (!BN_mod_lshift1_quick(t, a, p)) goto end; 182 if (!BN_mod_lshift1_quick(t, A, p)) goto end;
194 183
195 /* b := (2*a)^((|p|-5)/8) */ 184 /* b := (2*a)^((|p|-5)/8) */
196 if (!BN_rshift(q, p, 3)) goto end; 185 if (!BN_rshift(q, p, 3)) goto end;
@@ -205,12 +194,12 @@ BIGNUM *BN_mod_sqrt(BIGNUM *in, const BIGNUM *a, const BIGNUM *p, BN_CTX *ctx)
205 if (!BN_sub_word(t, 1)) goto end; 194 if (!BN_sub_word(t, 1)) goto end;
206 195
207 /* x = a*b*t */ 196 /* x = a*b*t */
208 if (!BN_mod_mul(x, a, b, p, ctx)) goto end; 197 if (!BN_mod_mul(x, A, b, p, ctx)) goto end;
209 if (!BN_mod_mul(x, x, t, p, ctx)) goto end; 198 if (!BN_mod_mul(x, x, t, p, ctx)) goto end;
210 199
211 if (!BN_copy(ret, x)) goto end; 200 if (!BN_copy(ret, x)) goto end;
212 err = 0; 201 err = 0;
213 goto end; 202 goto vrfy;
214 } 203 }
215 204
216 /* e > 2, so we really have to use the Tonelli/Shanks algorithm. 205 /* e > 2, so we really have to use the Tonelli/Shanks algorithm.
@@ -297,11 +286,11 @@ BIGNUM *BN_mod_sqrt(BIGNUM *in, const BIGNUM *a, const BIGNUM *p, BN_CTX *ctx)
297 /* x := a^((q-1)/2) */ 286 /* x := a^((q-1)/2) */
298 if (BN_is_zero(t)) /* special case: p = 2^e + 1 */ 287 if (BN_is_zero(t)) /* special case: p = 2^e + 1 */
299 { 288 {
300 if (!BN_nnmod(t, a, p, ctx)) goto end; 289 if (!BN_nnmod(t, A, p, ctx)) goto end;
301 if (BN_is_zero(t)) 290 if (BN_is_zero(t))
302 { 291 {
303 /* special case: a == 0 (mod p) */ 292 /* special case: a == 0 (mod p) */
304 if (!BN_zero(ret)) goto end; 293 BN_zero(ret);
305 err = 0; 294 err = 0;
306 goto end; 295 goto end;
307 } 296 }
@@ -310,11 +299,11 @@ BIGNUM *BN_mod_sqrt(BIGNUM *in, const BIGNUM *a, const BIGNUM *p, BN_CTX *ctx)
310 } 299 }
311 else 300 else
312 { 301 {
313 if (!BN_mod_exp(x, a, t, p, ctx)) goto end; 302 if (!BN_mod_exp(x, A, t, p, ctx)) goto end;
314 if (BN_is_zero(x)) 303 if (BN_is_zero(x))
315 { 304 {
316 /* special case: a == 0 (mod p) */ 305 /* special case: a == 0 (mod p) */
317 if (!BN_zero(ret)) goto end; 306 BN_zero(ret);
318 err = 0; 307 err = 0;
319 goto end; 308 goto end;
320 } 309 }
@@ -322,10 +311,10 @@ BIGNUM *BN_mod_sqrt(BIGNUM *in, const BIGNUM *a, const BIGNUM *p, BN_CTX *ctx)
322 311
323 /* b := a*x^2 (= a^q) */ 312 /* b := a*x^2 (= a^q) */
324 if (!BN_mod_sqr(b, x, p, ctx)) goto end; 313 if (!BN_mod_sqr(b, x, p, ctx)) goto end;
325 if (!BN_mod_mul(b, b, a, p, ctx)) goto end; 314 if (!BN_mod_mul(b, b, A, p, ctx)) goto end;
326 315
327 /* x := a*x (= a^((q+1)/2)) */ 316 /* x := a*x (= a^((q+1)/2)) */
328 if (!BN_mod_mul(x, x, a, p, ctx)) goto end; 317 if (!BN_mod_mul(x, x, A, p, ctx)) goto end;
329 318
330 while (1) 319 while (1)
331 { 320 {
@@ -342,7 +331,7 @@ BIGNUM *BN_mod_sqrt(BIGNUM *in, const BIGNUM *a, const BIGNUM *p, BN_CTX *ctx)
342 { 331 {
343 if (!BN_copy(ret, x)) goto end; 332 if (!BN_copy(ret, x)) goto end;
344 err = 0; 333 err = 0;
345 goto end; 334 goto vrfy;
346 } 335 }
347 336
348 337
@@ -373,6 +362,22 @@ BIGNUM *BN_mod_sqrt(BIGNUM *in, const BIGNUM *a, const BIGNUM *p, BN_CTX *ctx)
373 e = i; 362 e = i;
374 } 363 }
375 364
365 vrfy:
366 if (!err)
367 {
368 /* verify the result -- the input might have been not a square
369 * (test added in 0.9.8) */
370
371 if (!BN_mod_sqr(x, ret, p, ctx))
372 err = 1;
373
374 if (!err && 0 != BN_cmp(x, A))
375 {
376 BNerr(BN_F_BN_MOD_SQRT, BN_R_NOT_A_SQUARE);
377 err = 1;
378 }
379 }
380
376 end: 381 end:
377 if (err) 382 if (err)
378 { 383 {
@@ -383,5 +388,6 @@ BIGNUM *BN_mod_sqrt(BIGNUM *in, const BIGNUM *a, const BIGNUM *p, BN_CTX *ctx)
383 ret = NULL; 388 ret = NULL;
384 } 389 }
385 BN_CTX_end(ctx); 390 BN_CTX_end(ctx);
391 bn_check_top(ret);
386 return ret; 392 return ret;
387 } 393 }
generated by cgit v1.2.3-55-g6feb (git 2.39.1) at 2025-04-26 15:08:13 +0000