1 /* $OpenBSD: bn_sqrt.c,v 1.9 2017/01/29 17:49:22 beck 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_lcl.h" 61 62 BIGNUM * 63 BN_mod_sqrt(BIGNUM *in, const BIGNUM *a, const BIGNUM *p, BN_CTX *ctx) 64 /* Returns 'ret' such that 65 * ret^2 == a (mod p), 66 * using the Tonelli/Shanks algorithm (cf. Henri Cohen, "A Course 67 * in Algebraic Computational Number Theory", algorithm 1.5.1). 68 * 'p' must be prime! 69 */ 70 { 71 BIGNUM *ret = in; 72 int err = 1; 73 int r; 74 BIGNUM *A, *b, *q, *t, *x, *y; 75 int e, i, j; 76 77 if (!BN_is_odd(p) || BN_abs_is_word(p, 1)) { 78 if (BN_abs_is_word(p, 2)) { 79 if (ret == NULL) 80 ret = BN_new(); 81 if (ret == NULL) 82 goto end; 83 if (!BN_set_word(ret, BN_is_bit_set(a, 0))) { 84 if (ret != in) 85 BN_free(ret); 86 return NULL; 87 } 88 bn_check_top(ret); 89 return ret; 90 } 91 92 BNerror(BN_R_P_IS_NOT_PRIME); 93 return (NULL); 94 } 95 96 if (BN_is_zero(a) || BN_is_one(a)) { 97 if (ret == NULL) 98 ret = BN_new(); 99 if (ret == NULL) 100 goto end; 101 if (!BN_set_word(ret, BN_is_one(a))) { 102 if (ret != in) 103 BN_free(ret); 104 return NULL; 105 } 106 bn_check_top(ret); 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)) goto end; /* use 'q' as temp */ 221 q->neg = 0; 222 i = 2; 223 do { 224 /* For efficiency, try small numbers first; 225 * if this fails, try random numbers. 226 */ 227 if (i < 22) { 228 if (!BN_set_word(y, i)) 229 goto end; 230 } else { 231 if (!BN_pseudo_rand(y, BN_num_bits(p), 0, 0)) 232 goto end; 233 if (BN_ucmp(y, p) >= 0) { 234 if (p->neg) { 235 if (!BN_add(y, y, p)) 236 goto end; 237 } else { 238 if (!BN_sub(y, y, p)) 239 goto end; 240 } 241 } 242 /* now 0 <= y < |p| */ 243 if (BN_is_zero(y)) 244 if (!BN_set_word(y, i)) 245 goto end; 246 } 247 248 r = BN_kronecker(y, q, ctx); /* here 'q' is |p| */ 249 if (r < -1) 250 goto end; 251 if (r == 0) { 252 /* m divides p */ 253 BNerror(BN_R_P_IS_NOT_PRIME); 254 goto end; 255 } 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 { 307 if (!BN_nnmod(t, A, p, ctx)) 308 goto end; 309 if (BN_is_zero(t)) { 310 /* special case: a == 0 (mod p) */ 311 BN_zero(ret); 312 err = 0; 313 goto end; 314 } else if (!BN_one(x)) 315 goto end; 316 } else { 317 if (!BN_mod_exp_ct(x, A, t, p, ctx)) 318 goto end; 319 if (BN_is_zero(x)) { 320 /* special case: a == 0 (mod p) */ 321 BN_zero(ret); 322 err = 0; 323 goto end; 324 } 325 } 326 327 /* b := a*x^2 (= a^q) */ 328 if (!BN_mod_sqr(b, x, p, ctx)) 329 goto end; 330 if (!BN_mod_mul(b, b, A, p, ctx)) 331 goto end; 332 333 /* x := a*x (= a^((q+1)/2)) */ 334 if (!BN_mod_mul(x, x, A, p, ctx)) 335 goto end; 336 337 while (1) { 338 /* Now b is a^q * y^k for some even k (0 <= k < 2^E 339 * where E refers to the original value of e, which we 340 * don't keep in a variable), and x is a^((q+1)/2) * y^(k/2). 341 * 342 * We have a*b = x^2, 343 * y^2^(e-1) = -1, 344 * b^2^(e-1) = 1. 345 */ 346 347 if (BN_is_one(b)) { 348 if (!BN_copy(ret, x)) 349 goto end; 350 err = 0; 351 goto vrfy; 352 } 353 354 355 /* find smallest i such that b^(2^i) = 1 */ 356 i = 1; 357 if (!BN_mod_sqr(t, b, p, ctx)) 358 goto end; 359 while (!BN_is_one(t)) { 360 i++; 361 if (i == e) { 362 BNerror(BN_R_NOT_A_SQUARE); 363 goto end; 364 } 365 if (!BN_mod_mul(t, t, t, p, ctx)) 366 goto end; 367 } 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 386 vrfy: 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 400 end: 401 if (err) { 402 if (ret != NULL && ret != in) { 403 BN_clear_free(ret); 404 } 405 ret = NULL; 406 } 407 BN_CTX_end(ctx); 408 bn_check_top(ret); 409 return ret; 410 } 411