1 /* $OpenBSD: bn_sqrt.c,v 1.5 2014/07/11 08:44:48 jsing 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 BNerr(BN_F_BN_MOD_SQRT, 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(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(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 ? BN_add : BN_sub)(y, y, p)) 235 goto end; 236 } 237 /* now 0 <= y < |p| */ 238 if (BN_is_zero(y)) 239 if (!BN_set_word(y, i)) 240 goto end; 241 } 242 243 r = BN_kronecker(y, q, ctx); /* here 'q' is |p| */ 244 if (r < -1) 245 goto end; 246 if (r == 0) { 247 /* m divides p */ 248 BNerr(BN_F_BN_MOD_SQRT, BN_R_P_IS_NOT_PRIME); 249 goto end; 250 } 251 } 252 while (r == 1 && ++i < 82); 253 254 if (r != -1) { 255 /* Many rounds and still no non-square -- this is more likely 256 * a bug than just bad luck. 257 * Even if p is not prime, we should have found some y 258 * such that r == -1. 259 */ 260 BNerr(BN_F_BN_MOD_SQRT, BN_R_TOO_MANY_ITERATIONS); 261 goto end; 262 } 263 264 /* Here's our actual 'q': */ 265 if (!BN_rshift(q, q, e)) 266 goto end; 267 268 /* Now that we have some non-square, we can find an element 269 * of order 2^e by computing its q'th power. */ 270 if (!BN_mod_exp(y, y, q, p, ctx)) 271 goto end; 272 if (BN_is_one(y)) { 273 BNerr(BN_F_BN_MOD_SQRT, BN_R_P_IS_NOT_PRIME); 274 goto end; 275 } 276 277 /* Now we know that (if p is indeed prime) there is an integer 278 * k, 0 <= k < 2^e, such that 279 * 280 * a^q * y^k == 1 (mod p). 281 * 282 * As a^q is a square and y is not, k must be even. 283 * q+1 is even, too, so there is an element 284 * 285 * X := a^((q+1)/2) * y^(k/2), 286 * 287 * and it satisfies 288 * 289 * X^2 = a^q * a * y^k 290 * = a, 291 * 292 * so it is the square root that we are looking for. 293 */ 294 295 /* t := (q-1)/2 (note that q is odd) */ 296 if (!BN_rshift1(t, q)) 297 goto end; 298 299 /* x := a^((q-1)/2) */ 300 if (BN_is_zero(t)) /* special case: p = 2^e + 1 */ 301 { 302 if (!BN_nnmod(t, A, p, ctx)) 303 goto end; 304 if (BN_is_zero(t)) { 305 /* special case: a == 0 (mod p) */ 306 BN_zero(ret); 307 err = 0; 308 goto end; 309 } else if (!BN_one(x)) 310 goto end; 311 } else { 312 if (!BN_mod_exp(x, A, t, p, ctx)) 313 goto end; 314 if (BN_is_zero(x)) { 315 /* special case: a == 0 (mod p) */ 316 BN_zero(ret); 317 err = 0; 318 goto end; 319 } 320 } 321 322 /* b := a*x^2 (= a^q) */ 323 if (!BN_mod_sqr(b, x, p, ctx)) 324 goto end; 325 if (!BN_mod_mul(b, b, A, p, ctx)) 326 goto end; 327 328 /* x := a*x (= a^((q+1)/2)) */ 329 if (!BN_mod_mul(x, x, A, p, ctx)) 330 goto end; 331 332 while (1) { 333 /* Now b is a^q * y^k for some even k (0 <= k < 2^E 334 * where E refers to the original value of e, which we 335 * don't keep in a variable), and x is a^((q+1)/2) * y^(k/2). 336 * 337 * We have a*b = x^2, 338 * y^2^(e-1) = -1, 339 * b^2^(e-1) = 1. 340 */ 341 342 if (BN_is_one(b)) { 343 if (!BN_copy(ret, x)) 344 goto end; 345 err = 0; 346 goto vrfy; 347 } 348 349 350 /* find smallest i such that b^(2^i) = 1 */ 351 i = 1; 352 if (!BN_mod_sqr(t, b, p, ctx)) 353 goto end; 354 while (!BN_is_one(t)) { 355 i++; 356 if (i == e) { 357 BNerr(BN_F_BN_MOD_SQRT, BN_R_NOT_A_SQUARE); 358 goto end; 359 } 360 if (!BN_mod_mul(t, t, t, p, ctx)) 361 goto end; 362 } 363 364 365 /* t := y^2^(e - i - 1) */ 366 if (!BN_copy(t, y)) 367 goto end; 368 for (j = e - i - 1; j > 0; j--) { 369 if (!BN_mod_sqr(t, t, p, ctx)) 370 goto end; 371 } 372 if (!BN_mod_mul(y, t, t, p, ctx)) 373 goto end; 374 if (!BN_mod_mul(x, x, t, p, ctx)) 375 goto end; 376 if (!BN_mod_mul(b, b, y, p, ctx)) 377 goto end; 378 e = i; 379 } 380 381 vrfy: 382 if (!err) { 383 /* verify the result -- the input might have been not a square 384 * (test added in 0.9.8) */ 385 386 if (!BN_mod_sqr(x, ret, p, ctx)) 387 err = 1; 388 389 if (!err && 0 != BN_cmp(x, A)) { 390 BNerr(BN_F_BN_MOD_SQRT, BN_R_NOT_A_SQUARE); 391 err = 1; 392 } 393 } 394 395 end: 396 if (err) { 397 if (ret != NULL && ret != in) { 398 BN_clear_free(ret); 399 } 400 ret = NULL; 401 } 402 BN_CTX_end(ctx); 403 bn_check_top(ret); 404 return ret; 405 } 406