bn_sqrt.c revision 109998
1/* crypto/bn/bn_mod.c */ 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 "cryptlib.h" 59#include "bn_lcl.h" 60 61 62BIGNUM *BN_mod_sqrt(BIGNUM *in, const BIGNUM *a, const BIGNUM *p, BN_CTX *ctx) 63/* Returns 'ret' such that 64 * ret^2 == a (mod p), 65 * using the Tonelli/Shanks algorithm (cf. Henri Cohen, "A Course 66 * in Algebraic Computational Number Theory", algorithm 1.5.1). 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 */ 71 { 72 BIGNUM *ret = in; 73 int err = 1; 74 int r; 75 BIGNUM *b, *q, *t, *x, *y; 76 int e, i, j; 77 78 if (!BN_is_odd(p) || BN_abs_is_word(p, 1)) 79 { 80 if (BN_abs_is_word(p, 2)) 81 { 82 if (ret == NULL) 83 ret = BN_new(); 84 if (ret == NULL) 85 goto end; 86 if (!BN_set_word(ret, BN_is_bit_set(a, 0))) 87 { 88 BN_free(ret); 89 return NULL; 90 } 91 return ret; 92 } 93 94 BNerr(BN_F_BN_MOD_SQRT, BN_R_P_IS_NOT_PRIME); 95 return(NULL); 96 } 97 98 if (BN_is_zero(a) || BN_is_one(a)) 99 { 100 if (ret == NULL) 101 ret = BN_new(); 102 if (ret == NULL) 103 goto end; 104 if (!BN_set_word(ret, BN_is_one(a))) 105 { 106 BN_free(ret); 107 return NULL; 108 } 109 return ret; 110 } 111 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); 123 b = BN_CTX_get(ctx); 124 q = BN_CTX_get(ctx); 125 t = BN_CTX_get(ctx); 126 x = BN_CTX_get(ctx); 127 y = BN_CTX_get(ctx); 128 if (y == NULL) goto end; 129 130 if (ret == NULL) 131 ret = BN_new(); 132 if (ret == NULL) goto end; 133 134 /* now write |p| - 1 as 2^e*q where q is odd */ 135 e = 1; 136 while (!BN_is_bit_set(p, e)) 137 e++; 138 /* we'll set q later (if needed) */ 139 140 if (e == 1) 141 { 142 /* The easy case: (|p|-1)/2 is odd, so 2 has an inverse 143 * modulo (|p|-1)/2, and square roots can be computed 144 * directly by modular exponentiation. 145 * We have 146 * 2 * (|p|+1)/4 == 1 (mod (|p|-1)/2), 147 * so we can use exponent (|p|+1)/4, i.e. (|p|-3)/4 + 1. 148 */ 149 if (!BN_rshift(q, p, 2)) goto end; 150 q->neg = 0; 151 if (!BN_add_word(q, 1)) goto end; 152 if (!BN_mod_exp(ret, a, q, p, ctx)) goto end; 153 err = 0; 154 goto end; 155 } 156 157 if (e == 2) 158 { 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 /* 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 */ 193 if (!BN_mod_lshift1_quick(t, a, p)) goto end; 194 195 /* b := (2*a)^((|p|-5)/8) */ 196 if (!BN_rshift(q, p, 3)) goto end; 197 q->neg = 0; 198 if (!BN_mod_exp(b, t, q, p, ctx)) goto end; 199 200 /* y := b^2 */ 201 if (!BN_mod_sqr(y, b, p, ctx)) goto end; 202 203 /* t := (2*a)*b^2 - 1*/ 204 if (!BN_mod_mul(t, t, y, p, ctx)) goto end; 205 if (!BN_sub_word(t, 1)) goto end; 206 207 /* x = a*b*t */ 208 if (!BN_mod_mul(x, a, b, p, ctx)) goto end; 209 if (!BN_mod_mul(x, x, t, p, ctx)) goto end; 210 211 if (!BN_copy(ret, x)) goto end; 212 err = 0; 213 goto end; 214 } 215 216 /* e > 2, so we really have to use the Tonelli/Shanks algorithm. 217 * First, find some y that is not a square. */ 218 if (!BN_copy(q, p)) goto end; /* use 'q' as temp */ 219 q->neg = 0; 220 i = 2; 221 do 222 { 223 /* For efficiency, try small numbers first; 224 * if this fails, try random numbers. 225 */ 226 if (i < 22) 227 { 228 if (!BN_set_word(y, i)) goto end; 229 } 230 else 231 { 232 if (!BN_pseudo_rand(y, BN_num_bits(p), 0, 0)) goto end; 233 if (BN_ucmp(y, p) >= 0) 234 { 235 if (!(p->neg ? BN_add : BN_sub)(y, y, p)) goto end; 236 } 237 /* now 0 <= y < |p| */ 238 if (BN_is_zero(y)) 239 if (!BN_set_word(y, i)) goto end; 240 } 241 242 r = BN_kronecker(y, q, ctx); /* here 'q' is |p| */ 243 if (r < -1) goto end; 244 if (r == 0) 245 { 246 /* m divides p */ 247 BNerr(BN_F_BN_MOD_SQRT, BN_R_P_IS_NOT_PRIME); 248 goto end; 249 } 250 } 251 while (r == 1 && ++i < 82); 252 253 if (r != -1) 254 { 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)) goto end; 266 267 /* Now that we have some non-square, we can find an element 268 * of order 2^e by computing its q'th power. */ 269 if (!BN_mod_exp(y, y, q, p, ctx)) goto end; 270 if (BN_is_one(y)) 271 { 272 BNerr(BN_F_BN_MOD_SQRT, BN_R_P_IS_NOT_PRIME); 273 goto end; 274 } 275 276 /* Now we know that (if p is indeed prime) there is an integer 277 * k, 0 <= k < 2^e, such that 278 * 279 * a^q * y^k == 1 (mod p). 280 * 281 * As a^q is a square and y is not, k must be even. 282 * q+1 is even, too, so there is an element 283 * 284 * X := a^((q+1)/2) * y^(k/2), 285 * 286 * and it satisfies 287 * 288 * X^2 = a^q * a * y^k 289 * = a, 290 * 291 * so it is the square root that we are looking for. 292 */ 293 294 /* t := (q-1)/2 (note that q is odd) */ 295 if (!BN_rshift1(t, q)) goto end; 296 297 /* x := a^((q-1)/2) */ 298 if (BN_is_zero(t)) /* special case: p = 2^e + 1 */ 299 { 300 if (!BN_nnmod(t, a, p, ctx)) goto end; 301 if (BN_is_zero(t)) 302 { 303 /* special case: a == 0 (mod p) */ 304 if (!BN_zero(ret)) goto end; 305 err = 0; 306 goto end; 307 } 308 else 309 if (!BN_one(x)) goto end; 310 } 311 else 312 { 313 if (!BN_mod_exp(x, a, t, p, ctx)) goto end; 314 if (BN_is_zero(x)) 315 { 316 /* special case: a == 0 (mod p) */ 317 if (!BN_zero(ret)) goto end; 318 err = 0; 319 goto end; 320 } 321 } 322 323 /* b := a*x^2 (= a^q) */ 324 if (!BN_mod_sqr(b, x, p, ctx)) goto end; 325 if (!BN_mod_mul(b, b, a, p, ctx)) goto end; 326 327 /* x := a*x (= a^((q+1)/2)) */ 328 if (!BN_mod_mul(x, x, a, p, ctx)) goto end; 329 330 while (1) 331 { 332 /* Now b is a^q * y^k for some even k (0 <= k < 2^E 333 * where E refers to the original value of e, which we 334 * don't keep in a variable), and x is a^((q+1)/2) * y^(k/2). 335 * 336 * We have a*b = x^2, 337 * y^2^(e-1) = -1, 338 * b^2^(e-1) = 1. 339 */ 340 341 if (BN_is_one(b)) 342 { 343 if (!BN_copy(ret, x)) goto end; 344 err = 0; 345 goto end; 346 } 347 348 349 /* find smallest i such that b^(2^i) = 1 */ 350 i = 1; 351 if (!BN_mod_sqr(t, b, p, ctx)) goto end; 352 while (!BN_is_one(t)) 353 { 354 i++; 355 if (i == e) 356 { 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)) goto end; 361 } 362 363 364 /* t := y^2^(e - i - 1) */ 365 if (!BN_copy(t, y)) goto end; 366 for (j = e - i - 1; j > 0; j--) 367 { 368 if (!BN_mod_sqr(t, t, p, ctx)) goto end; 369 } 370 if (!BN_mod_mul(y, t, t, p, ctx)) goto end; 371 if (!BN_mod_mul(x, x, t, p, ctx)) goto end; 372 if (!BN_mod_mul(b, b, y, p, ctx)) goto end; 373 e = i; 374 } 375 376 end: 377 if (err) 378 { 379 if (ret != NULL && ret != in) 380 { 381 BN_clear_free(ret); 382 } 383 ret = NULL; 384 } 385 BN_CTX_end(ctx); 386 return ret; 387 } 388