| 1 | /* |
| 2 | * Copyright (c) 1997-1999 The Stanford SRP Authentication Project |
| 3 | * All Rights Reserved. |
| 4 | * |
| 5 | * Permission is hereby granted, free of charge, to any person obtaining |
| 6 | * a copy of this software and associated documentation files (the |
| 7 | * "Software"), to deal in the Software without restriction, including |
| 8 | * without limitation the rights to use, copy, modify, merge, publish, |
| 9 | * distribute, sublicense, and/or sell copies of the Software, and to |
| 10 | * permit persons to whom the Software is furnished to do so, subject to |
| 11 | * the following conditions: |
| 12 | * |
| 13 | * The above copyright notice and this permission notice shall be |
| 14 | * included in all copies or substantial portions of the Software. |
| 15 | * |
| 16 | * THE SOFTWARE IS PROVIDED "AS-IS" AND WITHOUT WARRANTY OF ANY KIND, |
| 17 | * EXPRESS, IMPLIED OR OTHERWISE, INCLUDING WITHOUT LIMITATION, ANY |
| 18 | * WARRANTY OF MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE. |
| 19 | * |
| 20 | * IN NO EVENT SHALL STANFORD BE LIABLE FOR ANY SPECIAL, INCIDENTAL, |
| 21 | * INDIRECT OR CONSEQUENTIAL DAMAGES OF ANY KIND, OR ANY DAMAGES WHATSOEVER |
| 22 | * RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER OR NOT ADVISED OF |
| 23 | * THE POSSIBILITY OF DAMAGE, AND ON ANY THEORY OF LIABILITY, ARISING OUT |
| 24 | * OF OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. |
| 25 | * |
| 26 | * In addition, the following conditions apply: |
| 27 | * |
| 28 | * 1. Any software that incorporates the SRP authentication technology |
| 29 | * must display the following acknowlegment: |
| 30 | * "This product uses the 'Secure Remote Password' cryptographic |
| 31 | * authentication system developed by Tom Wu (tjw@CS.Stanford.EDU)." |
| 32 | * |
| 33 | * 2. Any software that incorporates all or part of the SRP distribution |
| 34 | * itself must also display the following acknowledgment: |
| 35 | * "This product includes software developed by Tom Wu and Eugene |
| 36 | * Jhong for the SRP Distribution (http://srp.stanford.edu/srp/)." |
| 37 | * |
| 38 | * 3. Redistributions in source or binary form must retain an intact copy |
| 39 | * of this copyright notice and list of conditions. |
| 40 | */ |
| 41 | |
| 42 | #include <stdio.h> |
| 43 | |
| 44 | #include "t_defines.h" |
| 45 | #include "t_pwd.h" |
| 46 | #include "t_read.h" |
| 47 | #include "bn.h" |
| 48 | #include "bn_lcl.h" |
| 49 | #include "bn_prime.h" |
| 50 | |
| 51 | #define TABLE_SIZE 32 |
| 52 | |
| 53 | static int witness(BIGNUM *w, const BIGNUM *a, const BIGNUM *a1, |
| 54 | const BIGNUM *a1_odd, int k, BN_CTX *ctx, BN_MONT_CTX *mont); |
| 55 | |
| 56 | /* |
| 57 | * This is the safe prime generation logic. |
| 58 | * To generate a safe prime p (where p = 2q+1 and q is prime), we start |
| 59 | * with a random odd q that is one bit shorter than the desired length |
| 60 | * of p. We use a simple 30-element sieve to filter the values of q |
| 61 | * and consider only those that are 11, 23, or 29 (mod 30). (If q were |
| 62 | * anything else, either q or p would be divisible by 2, 3, or 5). |
| 63 | * For the values of q that are left, we apply the following tests in |
| 64 | * this order: |
| 65 | * |
| 66 | * trial divide q |
| 67 | * let p = 2q + 1 |
| 68 | * trial divide p |
| 69 | * apply Fermat test to q (2^q == 2 (mod q)) |
| 70 | * apply Fermat test to p (2^p == 2 (mod p)) |
| 71 | * apply real probablistic primality test to q |
| 72 | * apply real probablistic primality test to p |
| 73 | * |
| 74 | * A number that passes all these tests is considered a safe prime for |
| 75 | * our purposes. The tests are ordered this way for efficiency; the |
| 76 | * slower tests are run rarely if ever at all. |
| 77 | */ |
| 78 | |
| 79 | static int |
| 80 | trialdiv(x) |
| 81 | const BigInteger x; |
| 82 | { |
| 83 | static int primes[] = { /* All odd primes < 256 */ |
| 84 | 3, 5, 7, 11, 13, 17, 19, 23, 29, |
| 85 | 31, 37, 41, 43, 47, 53, 59, 61, 67, |
| 86 | 71, 73, 79, 83, 89, 97, 101, 103, |
| 87 | 107, 109, 113, 127, 131, 137, 139, 149, 151, |
| 88 | 157, 163, 167, 173, 179, 181, 191, 193, 197, |
| 89 | 199, 211, 223, 227, 229, 233, 239, 241, 251 |
| 90 | }; |
| 91 | static int nprimes = sizeof(primes) / sizeof(int); |
| 92 | int i; |
| 93 | |
| 94 | for(i = 0; i < nprimes; ++i) { |
| 95 | if(BigIntegerModInt(x, primes[i]) == 0) |
| 96 | return primes[i]; |
| 97 | } |
| 98 | return 1; |
| 99 | } |
| 100 | |
| 101 | /* x + sieve30[x%30] == 11, 23, or 29 (mod 30) */ |
| 102 | |
| 103 | static int sieve30[] = |
| 104 | { 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, |
| 105 | 1, 12, 11, 10, 9, 8, 7, 6, 5, 4, |
| 106 | 3, 2, 1, 6, 5, 4, 3, 2, 1, 12 |
| 107 | }; |
| 108 | |
| 109 | /* Find a Sophie-Germain prime between "lo" and "hi". NOTE: this is not |
| 110 | a "safe prime", but the smaller prime. Take 2q+1 to get the safe prime. */ |
| 111 | |
| 112 | static void |
| 113 | sophie_germain(q, lo, hi) |
| 114 | BigInteger q; /* assumed initialized */ |
| 115 | const BigInteger lo; |
| 116 | const BigInteger hi; |
| 117 | { |
| 118 | BigInteger m, p, r; |
| 119 | char parambuf[MAXPARAMLEN]; |
| 120 | int foundprime = 0; |
| 121 | int i, mod30; |
| 122 | |
| 123 | m = BigIntegerFromInt(0); |
| 124 | BigIntegerSub(m, hi, lo); |
| 125 | i = (BigIntegerBitLen(m) + 7) / 8; |
| 126 | t_random(parambuf, i); |
| 127 | r = BigIntegerFromBytes(parambuf, i); |
| 128 | BigIntegerMod(r, r, m); |
| 129 | |
| 130 | BigIntegerAdd(q, r, lo); |
| 131 | if(BigIntegerModInt(q, 2) == 0) |
| 132 | BigIntegerAddInt(q, q, 1); /* make q odd */ |
| 133 | |
| 134 | mod30 = BigIntegerModInt(q, 30); /* mod30 = q % 30 */ |
| 135 | |
| 136 | BigIntegerFree(m); |
| 137 | m = BigIntegerFromInt(2); /* m = 2 */ |
| 138 | p = BigIntegerFromInt(0); |
| 139 | |
| 140 | while(BigIntegerCmp(q, hi) < 0) { |
| 141 | if(trialdiv(q) < 2) { |
| 142 | BigIntegerMulInt(p, q, 2); /* p = 2 * q */ |
| 143 | BigIntegerAddInt(p, p, 1); /* p += 1 */ |
| 144 | if(trialdiv(p) < 2) { |
| 145 | BigIntegerModExp(r, m, q, q); /* r = 2^q % q */ |
| 146 | if(BigIntegerCmpInt(r, 2) == 0) { /* if(r == 2) */ |
| 147 | BigIntegerModExp(r, m, p, p); /* r = 2^p % p */ |
| 148 | if(BigIntegerCmpInt(r, 2) == 0) { /* if(r == 2) */ |
| 149 | if(BigIntegerCheckPrime(q) && BigIntegerCheckPrime(p)) { |
| 150 | ++foundprime; |
| 151 | break; |
| 152 | } |
| 153 | } |
| 154 | } |
| 155 | } |
| 156 | } |
| 157 | |
| 158 | i = sieve30[mod30]; |
| 159 | BigIntegerAddInt(q, q, i); /* q += i */ |
| 160 | mod30 = (mod30 + i) % 30; |
| 161 | } |
| 162 | |
| 163 | /* should wrap around on failure */ |
| 164 | if(!foundprime) { |
| 165 | fprintf(stderr, "Prime generation failed!\n"); |
| 166 | exit(1); |
| 167 | } |
| 168 | |
| 169 | BigIntegerFree(r); |
| 170 | BigIntegerFree(m); |
| 171 | BigIntegerFree(p); |
| 172 | } |
| 173 | |
| 174 | _TYPE( struct t_confent * ) |
| 175 | t_makeconfent(tc, nsize) |
| 176 | struct t_conf * tc; |
| 177 | int nsize; |
| 178 | { |
| 179 | BigInteger n, g, q, t, u; |
| 180 | |
| 181 | t = BigIntegerFromInt(0); |
| 182 | u = BigIntegerFromInt(1); /* u = 1 */ |
| 183 | BigIntegerLShift(t, u, nsize - 2); /* t = 2^(nsize-2) */ |
| 184 | BigIntegerMulInt(u, t, 2); /* u = 2^(nsize-1) */ |
| 185 | |
| 186 | q = BigIntegerFromInt(0); |
| 187 | sophie_germain(q, t, u); |
| 188 | |
| 189 | n = BigIntegerFromInt(0); |
| 190 | BigIntegerMulInt(n, q, 2); |
| 191 | BigIntegerAddInt(n, n, 1); |
| 192 | |
| 193 | /* Look for a generator mod n */ |
| 194 | g = BigIntegerFromInt(2); |
| 195 | while(1) { |
| 196 | BigIntegerModExp(t, g, q, n); /* t = g^q % n */ |
| 197 | if(BigIntegerCmpInt(t, 1) == 0) /* if(t == 1) */ |
| 198 | BigIntegerAddInt(g, g, 1); /* ++g */ |
| 199 | else |
| 200 | break; |
| 201 | } |
| 202 | BigIntegerFree(t); |
| 203 | BigIntegerFree(u); |
| 204 | BigIntegerFree(q); |
| 205 | |
| 206 | tc->tcbuf.modulus.data = tc->modbuf; |
| 207 | tc->tcbuf.modulus.len = BigIntegerToBytes(n, tc->tcbuf.modulus.data); |
| 208 | BigIntegerFree(n); |
| 209 | |
| 210 | tc->tcbuf.generator.data = tc->genbuf; |
| 211 | tc->tcbuf.generator.len = BigIntegerToBytes(g, tc->tcbuf.generator.data); |
| 212 | BigIntegerFree(g); |
| 213 | |
| 214 | tc->tcbuf.index = 1; |
| 215 | return &tc->tcbuf; |
| 216 | } |
| 217 | |
| 218 | _TYPE( struct t_confent * ) |
| 219 | t_makeconfent_c(tc, nsize) |
| 220 | struct t_conf * tc; |
| 221 | int nsize; |
| 222 | { |
| 223 | BigInteger g, n, p, q, j, k, t, u; |
| 224 | int psize, qsize; |
| 225 | |
| 226 | psize = nsize / 2; |
| 227 | qsize = nsize - psize; |
| 228 | |
| 229 | t = BigIntegerFromInt(1); /* t = 1 */ |
| 230 | u = BigIntegerFromInt(0); |
| 231 | BigIntegerLShift(u, t, psize - 3); /* u = t*2^(psize-3) = 2^(psize-3) */ |
| 232 | BigIntegerMulInt(t, u, 3); /* t = 3*u = 1.5*2^(psize-2) */ |
| 233 | BigIntegerAdd(u, u, t); /* u += t [u = 2^(psize-1)] */ |
| 234 | j = BigIntegerFromInt(0); |
| 235 | sophie_germain(j, t, u); |
| 236 | |
| 237 | k = BigIntegerFromInt(0); |
| 238 | if(qsize != psize) { |
| 239 | BigIntegerFree(t); |
| 240 | t = BigIntegerFromInt(1); /* t = 1 */ |
| 241 | BigIntegerLShift(u, t, qsize - 3); /* u = t*2^(qsize-3) = 2^(qsize-3) */ |
| 242 | BigIntegerMulInt(t, u, 3); /* t = 3*u = 1.5*2^(qsize-2) */ |
| 243 | BigIntegerAdd(u, u, t); /* u += t [u = 2^(qsize-1)] */ |
| 244 | } |
| 245 | sophie_germain(k, t, u); |
| 246 | |
| 247 | p = BigIntegerFromInt(0); |
| 248 | BigIntegerMulInt(p, j, 2); /* p = 2 * j */ |
| 249 | BigIntegerAddInt(p, p, 1); /* p += 1 */ |
| 250 | |
| 251 | q = BigIntegerFromInt(0); |
| 252 | BigIntegerMulInt(q, k, 2); /* q = 2 * k */ |
| 253 | BigIntegerAddInt(q, q, 1); /* q += 1 */ |
| 254 | |
| 255 | n = BigIntegerFromInt(0); |
| 256 | BigIntegerMul(n, p, q); /* n = p * q */ |
| 257 | BigIntegerMul(u, j, k); /* u = j * k */ |
| 258 | |
| 259 | BigIntegerFree(p); |
| 260 | BigIntegerFree(q); |
| 261 | BigIntegerFree(j); |
| 262 | BigIntegerFree(k); |
| 263 | |
| 264 | g = BigIntegerFromInt(2); /* g = 2 */ |
| 265 | |
| 266 | /* Look for a generator mod n */ |
| 267 | while(1) { |
| 268 | BigIntegerModExp(t, g, u, n); /* t = g^u % n */ |
| 269 | if(BigIntegerCmpInt(t, 1) == 0) |
| 270 | BigIntegerAddInt(g, g, 1); /* ++g */ |
| 271 | else |
| 272 | break; |
| 273 | } |
| 274 | |
| 275 | BigIntegerFree(u); |
| 276 | BigIntegerFree(t); |
| 277 | |
| 278 | tc->tcbuf.modulus.data = tc->modbuf; |
| 279 | tc->tcbuf.modulus.len = BigIntegerToBytes(n, tc->tcbuf.modulus.data); |
| 280 | BigIntegerFree(n); |
| 281 | |
| 282 | tc->tcbuf.generator.data = tc->genbuf; |
| 283 | tc->tcbuf.generator.len = BigIntegerToBytes(g, tc->tcbuf.generator.data); |
| 284 | BigIntegerFree(g); |
| 285 | |
| 286 | tc->tcbuf.index = 1; |
| 287 | return &tc->tcbuf; |
| 288 | } |
| 289 | |
| 290 | _TYPE( struct t_confent * ) |
| 291 | t_newconfent(tc) |
| 292 | struct t_conf * tc; |
| 293 | { |
| 294 | tc->tcbuf.index = 0; |
| 295 | tc->tcbuf.modulus.data = tc->modbuf; |
| 296 | tc->tcbuf.modulus.len = 0; |
| 297 | tc->tcbuf.generator.data = tc->genbuf; |
| 298 | tc->tcbuf.generator.len = 0; |
| 299 | return &tc->tcbuf; |
| 300 | } |
| 301 | |
| 302 | _TYPE( void ) |
| 303 | t_putconfent(ent, fp) |
| 304 | const struct t_confent * ent; |
| 305 | FILE * fp; |
| 306 | { |
| 307 | char strbuf[MAXB64PARAMLEN]; |
| 308 | |
| 309 | fprintf(fp, "%d:%s:", ent->index, |
| 310 | t_tob64(strbuf, ent->modulus.data, ent->modulus.len)); |
| 311 | fprintf(fp, "%s\n", |
| 312 | t_tob64(strbuf, ent->generator.data, ent->generator.len)); |
| 313 | } |
| 314 | |
| 315 | int |
| 316 | BigIntegerBitLen(b) |
| 317 | BigInteger b; |
| 318 | { |
| 319 | return BN_num_bits(b); |
| 320 | } |
| 321 | |
| 322 | int |
| 323 | BigIntegerCheckPrime(n) |
| 324 | BigInteger n; |
| 325 | { |
| 326 | BN_CTX * ctx = BN_CTX_new(); |
| 327 | int rv = BN_is_prime(n, 25, NULL, ctx, NULL); |
| 328 | BN_CTX_free(ctx); |
| 329 | return rv; |
| 330 | } |
| 331 | |
| 332 | unsigned int |
| 333 | BigIntegerModInt(d, m) |
| 334 | BigInteger d; |
| 335 | unsigned int m; |
| 336 | { |
| 337 | return BN_mod_word(d, m); |
| 338 | } |
| 339 | |
| 340 | void |
| 341 | BigIntegerMod(result, d, m) |
| 342 | BigInteger result, d, m; |
| 343 | { |
| 344 | BN_CTX * ctx = BN_CTX_new(); |
| 345 | BN_mod(result, d, m, ctx); |
| 346 | BN_CTX_free(ctx); |
| 347 | } |
| 348 | |
| 349 | void |
| 350 | BigIntegerMul(result, m1, m2) |
| 351 | BigInteger result, m1, m2; |
| 352 | { |
| 353 | BN_CTX * ctx = BN_CTX_new(); |
| 354 | BN_mul(result, m1, m2, ctx); |
| 355 | BN_CTX_free(ctx); |
| 356 | } |
| 357 | |
| 358 | void |
| 359 | BigIntegerLShift(result, x, bits) |
| 360 | BigInteger result, x; |
| 361 | unsigned int bits; |
| 362 | { |
| 363 | BN_lshift(result, x, bits); |
| 364 | } |
| 365 | |
| 366 | int BN_is_prime(const BIGNUM *a, int checks, void (*callback)(int,int,void *), |
| 367 | BN_CTX *ctx_passed, void *cb_arg) |
| 368 | { |
| 369 | return BN_is_prime_fasttest(a, checks, callback, ctx_passed, cb_arg, 0); |
| 370 | } |
| 371 | |
| 372 | int BN_is_prime_fasttest(const BIGNUM *a, int checks, |
| 373 | void (*callback)(int,int,void *), |
| 374 | BN_CTX *ctx_passed, void *cb_arg, |
| 375 | int do_trial_division) |
| 376 | { |
| 377 | int i, j, ret = -1; |
| 378 | int k; |
| 379 | BN_CTX *ctx = NULL; |
| 380 | BIGNUM *A1, *A1_odd, *check; /* taken from ctx */ |
| 381 | BN_MONT_CTX *mont = NULL; |
| 382 | const BIGNUM *A = NULL; |
| 383 | |
| 384 | if (checks == BN_prime_checks) |
| 385 | checks = BN_prime_checks_for_size(BN_num_bits(a)); |
| 386 | |
| 387 | /* first look for small factors */ |
| 388 | if (!BN_is_odd(a)) |
| 389 | return(0); |
| 390 | if (do_trial_division) |
| 391 | { |
| 392 | for (i = 1; i < NUMPRIMES; i++) |
| 393 | if (BN_mod_word(a, primes[i]) == 0) |
| 394 | return 0; |
| 395 | if (callback != NULL) callback(1, -1, cb_arg); |
| 396 | } |
| 397 | |
| 398 | if (ctx_passed != NULL) |
| 399 | ctx = ctx_passed; |
| 400 | else |
| 401 | if ((ctx=BN_CTX_new()) == NULL) |
| 402 | goto err; |
| 403 | BN_CTX_start(ctx); |
| 404 | |
| 405 | /* A := abs(a) */ |
| 406 | if (a->neg) |
| 407 | { |
| 408 | BIGNUM *t; |
| 409 | if ((t = BN_CTX_get(ctx)) == NULL) goto err; |
| 410 | BN_copy(t, a); |
| 411 | t->neg = 0; |
| 412 | A = t; |
| 413 | } |
| 414 | else |
| 415 | A = a; |
| 416 | A1 = BN_CTX_get(ctx); |
| 417 | A1_odd = BN_CTX_get(ctx); |
| 418 | check = BN_CTX_get(ctx); |
| 419 | if (check == NULL) goto err; |
| 420 | |
| 421 | /* compute A1 := A - 1 */ |
| 422 | if (!BN_copy(A1, A)) |
| 423 | goto err; |
| 424 | if (!BN_sub_word(A1, 1)) |
| 425 | goto err; |
| 426 | if (BN_is_zero(A1)) |
| 427 | { |
| 428 | ret = 0; |
| 429 | goto err; |
| 430 | } |
| 431 | |
| 432 | /* write A1 as A1_odd * 2^k */ |
| 433 | k = 1; |
| 434 | while (!BN_is_bit_set(A1, k)) |
| 435 | k++; |
| 436 | if (!BN_rshift(A1_odd, A1, k)) |
| 437 | goto err; |
| 438 | |
| 439 | /* Montgomery setup for computations mod A */ |
| 440 | mont = BN_MONT_CTX_new(); |
| 441 | if (mont == NULL) |
| 442 | goto err; |
| 443 | if (!BN_MONT_CTX_set(mont, A, ctx)) |
| 444 | goto err; |
| 445 | |
| 446 | for (i = 0; i < checks; i++) |
| 447 | { |
| 448 | if (!BN_pseudo_rand(check, BN_num_bits(A1), 0, 0)) |
| 449 | goto err; |
| 450 | if (BN_cmp(check, A1) >= 0) |
| 451 | if (!BN_sub(check, check, A1)) |
| 452 | goto err; |
| 453 | if (!BN_add_word(check, 1)) |
| 454 | goto err; |
| 455 | /* now 1 <= check < A */ |
| 456 | |
| 457 | j = witness(check, A, A1, A1_odd, k, ctx, mont); |
| 458 | if (j == -1) goto err; |
| 459 | if (j) |
| 460 | { |
| 461 | ret=0; |
| 462 | goto err; |
| 463 | } |
| 464 | if (callback != NULL) callback(1,i,cb_arg); |
| 465 | } |
| 466 | ret=1; |
| 467 | err: |
| 468 | if (ctx != NULL) |
| 469 | { |
| 470 | BN_CTX_end(ctx); |
| 471 | if (ctx_passed == NULL) |
| 472 | BN_CTX_free(ctx); |
| 473 | } |
| 474 | if (mont != NULL) |
| 475 | BN_MONT_CTX_free(mont); |
| 476 | |
| 477 | return(ret); |
| 478 | } |
| 479 | |
| 480 | static int witness(BIGNUM *w, const BIGNUM *a, const BIGNUM *a1, |
| 481 | const BIGNUM *a1_odd, int k, BN_CTX *ctx, BN_MONT_CTX *mont) |
| 482 | { |
| 483 | if (!BN_mod_exp_mont(w, w, a1_odd, a, ctx, mont)) /* w := w^a1_odd mod a */ |
| 484 | return -1; |
| 485 | if (BN_is_one(w)) |
| 486 | return 0; /* probably prime */ |
| 487 | if (BN_cmp(w, a1) == 0) |
| 488 | return 0; /* w == -1 (mod a), 'a' is probably prime */ |
| 489 | while (--k) |
| 490 | { |
| 491 | if (!BN_mod_mul(w, w, w, a, ctx)) /* w := w^2 mod a */ |
| 492 | return -1; |
| 493 | if (BN_is_one(w)) |
| 494 | return 1; /* 'a' is composite, otherwise a previous 'w' would |
| 495 | * have been == -1 (mod 'a') */ |
| 496 | if (BN_cmp(w, a1) == 0) |
| 497 | return 0; /* w == -1 (mod a), 'a' is probably prime */ |
| 498 | } |
| 499 | /* If we get here, 'w' is the (a-1)/2-th power of the original 'w', |
| 500 | * and it is neither -1 nor +1 -- so 'a' cannot be prime */ |
| 501 | return 1; |
| 502 | } |
| 503 | |
| 504 | int BN_mod_exp_mont(BIGNUM *rr, BIGNUM *a, const BIGNUM *p, |
| 505 | const BIGNUM *m, BN_CTX *ctx, BN_MONT_CTX *in_mont) |
| 506 | { |
| 507 | int i,j,bits,ret=0,wstart,wend,window,wvalue; |
| 508 | int start=1,ts=0; |
| 509 | BIGNUM *d,*r; |
| 510 | BIGNUM *aa; |
| 511 | BIGNUM val[TABLE_SIZE]; |
| 512 | BN_MONT_CTX *mont=NULL; |
| 513 | |
| 514 | bn_check_top(a); |
| 515 | bn_check_top(p); |
| 516 | bn_check_top(m); |
| 517 | |
| 518 | if (!(m->d[0] & 1)) |
| 519 | { |
| 520 | return(0); |
| 521 | } |
| 522 | bits=BN_num_bits(p); |
| 523 | if (bits == 0) |
| 524 | { |
| 525 | BN_one(rr); |
| 526 | return(1); |
| 527 | } |
| 528 | BN_CTX_start(ctx); |
| 529 | d = BN_CTX_get(ctx); |
| 530 | r = BN_CTX_get(ctx); |
| 531 | if (d == NULL || r == NULL) goto err; |
| 532 | |
| 533 | /* If this is not done, things will break in the montgomery |
| 534 | * part */ |
| 535 | |
| 536 | if (in_mont != NULL) |
| 537 | mont=in_mont; |
| 538 | else |
| 539 | { |
| 540 | if ((mont=BN_MONT_CTX_new()) == NULL) goto err; |
| 541 | if (!BN_MONT_CTX_set(mont,m,ctx)) goto err; |
| 542 | } |
| 543 | |
| 544 | BN_init(&val[0]); |
| 545 | ts=1; |
| 546 | if (BN_ucmp(a,m) >= 0) |
| 547 | { |
| 548 | if (!BN_mod(&(val[0]),a,m,ctx)) |
| 549 | goto err; |
| 550 | aa= &(val[0]); |
| 551 | } |
| 552 | else |
| 553 | aa=a; |
| 554 | if (!BN_to_montgomery(&(val[0]),aa,mont,ctx)) goto err; /* 1 */ |
| 555 | |
| 556 | window = BN_window_bits_for_exponent_size(bits); |
| 557 | if (window > 1) |
| 558 | { |
| 559 | if (!BN_mod_mul_montgomery(d,&(val[0]),&(val[0]),mont,ctx)) goto err; /* 2 */ |
| 560 | j=1<<(window-1); |
| 561 | for (i=1; i<j; i++) |
| 562 | { |
| 563 | BN_init(&(val[i])); |
| 564 | if (!BN_mod_mul_montgomery(&(val[i]),&(val[i-1]),d,mont,ctx)) |
| 565 | goto err; |
| 566 | } |
| 567 | ts=i; |
| 568 | } |
| 569 | |
| 570 | start=1; /* This is used to avoid multiplication etc |
| 571 | * when there is only the value '1' in the |
| 572 | * buffer. */ |
| 573 | wvalue=0; /* The 'value' of the window */ |
| 574 | wstart=bits-1; /* The top bit of the window */ |
| 575 | wend=0; /* The bottom bit of the window */ |
| 576 | |
| 577 | if (!BN_to_montgomery(r,BN_value_one(),mont,ctx)) goto err; |
| 578 | for (;;) |
| 579 | { |
| 580 | if (BN_is_bit_set(p,wstart) == 0) |
| 581 | { |
| 582 | if (!start) |
| 583 | { |
| 584 | if (!BN_mod_mul_montgomery(r,r,r,mont,ctx)) |
| 585 | goto err; |
| 586 | } |
| 587 | if (wstart == 0) break; |
| 588 | wstart--; |
| 589 | continue; |
| 590 | } |
| 591 | /* We now have wstart on a 'set' bit, we now need to work out |
| 592 | * how bit a window to do. To do this we need to scan |
| 593 | * forward until the last set bit before the end of the |
| 594 | * window */ |
| 595 | j=wstart; |
| 596 | wvalue=1; |
| 597 | wend=0; |
| 598 | for (i=1; i<window; i++) |
| 599 | { |
| 600 | if (wstart-i < 0) break; |
| 601 | if (BN_is_bit_set(p,wstart-i)) |
| 602 | { |
| 603 | wvalue<<=(i-wend); |
| 604 | wvalue|=1; |
| 605 | wend=i; |
| 606 | } |
| 607 | } |
| 608 | |
| 609 | /* wend is the size of the current window */ |
| 610 | j=wend+1; |
| 611 | /* add the 'bytes above' */ |
| 612 | if (!start) |
| 613 | for (i=0; i<j; i++) |
| 614 | { |
| 615 | if (!BN_mod_mul_montgomery(r,r,r,mont,ctx)) |
| 616 | goto err; |
| 617 | } |
| 618 | |
| 619 | /* wvalue will be an odd number < 2^window */ |
| 620 | if (!BN_mod_mul_montgomery(r,r,&(val[wvalue>>1]),mont,ctx)) |
| 621 | goto err; |
| 622 | |
| 623 | /* move the 'window' down further */ |
| 624 | wstart-=wend+1; |
| 625 | wvalue=0; |
| 626 | start=0; |
| 627 | if (wstart < 0) break; |
| 628 | } |
| 629 | if (!BN_from_montgomery(rr,r,mont,ctx)) goto err; |
| 630 | ret=1; |
| 631 | err: |
| 632 | if ((in_mont == NULL) && (mont != NULL)) BN_MONT_CTX_free(mont); |
| 633 | BN_CTX_end(ctx); |
| 634 | for (i=0; i<ts; i++) |
| 635 | BN_clear_free(&(val[i])); |
| 636 | return(ret); |
| 637 | } |
| 638 | |
| 639 | BN_ULONG BN_mod_word(const BIGNUM *a, BN_ULONG w) |
| 640 | { |
| 641 | #ifndef BN_LLONG |
| 642 | BN_ULONG ret=0; |
| 643 | #else |
| 644 | BN_ULLONG ret=0; |
| 645 | #endif |
| 646 | int i; |
| 647 | |
| 648 | w&=BN_MASK2; |
| 649 | for (i=a->top-1; i>=0; i--) |
| 650 | { |
| 651 | #ifndef BN_LLONG |
| 652 | ret=((ret<<BN_BITS4)|((a->d[i]>>BN_BITS4)&BN_MASK2l))%w; |
| 653 | ret=((ret<<BN_BITS4)|(a->d[i]&BN_MASK2l))%w; |
| 654 | #else |
| 655 | ret=(BN_ULLONG)(((ret<<(BN_ULLONG)BN_BITS2)|a->d[i])% |
| 656 | (BN_ULLONG)w); |
| 657 | #endif |
| 658 | } |
| 659 | return((BN_ULONG)ret); |
| 660 | } |
| 661 | |
| 662 | static int bnrand(int pseudorand, BIGNUM *rnd, int bits, int top, int bottom) |
| 663 | { |
| 664 | unsigned char *buf=NULL; |
| 665 | int ret=0,bit,bytes,mask; |
| 666 | |
| 667 | if (bits == 0) |
| 668 | { |
| 669 | BN_zero(rnd); |
| 670 | return 1; |
| 671 | } |
| 672 | |
| 673 | bytes=(bits+7)/8; |
| 674 | bit=(bits-1)%8; |
| 675 | mask=0xff<<bit; |
| 676 | |
| 677 | buf=(unsigned char *)malloc(bytes); |
| 678 | if (buf == NULL) |
| 679 | { |
| 680 | goto err; |
| 681 | } |
| 682 | |
| 683 | /* make a random number and set the top and bottom bits */ |
| 684 | /* this ignores the pseudorand flag */ |
| 685 | |
| 686 | t_random(buf, bytes); |
| 687 | |
| 688 | if (top) |
| 689 | { |
| 690 | if (bit == 0) |
| 691 | { |
| 692 | buf[0]=1; |
| 693 | buf[1]|=0x80; |
| 694 | } |
| 695 | else |
| 696 | { |
| 697 | buf[0]|=(3<<(bit-1)); |
| 698 | buf[0]&= ~(mask<<1); |
| 699 | } |
| 700 | } |
| 701 | else |
| 702 | { |
| 703 | buf[0]|=(1<<bit); |
| 704 | buf[0]&= ~(mask<<1); |
| 705 | } |
| 706 | if (bottom) /* set bottom bits to whatever odd is */ |
| 707 | buf[bytes-1]|=1; |
| 708 | if (!BN_bin2bn(buf,bytes,rnd)) goto err; |
| 709 | ret=1; |
| 710 | err: |
| 711 | if (buf != NULL) |
| 712 | { |
| 713 | memset(buf,0,bytes); |
| 714 | free(buf); |
| 715 | } |
| 716 | return(ret); |
| 717 | } |
| 718 | |
| 719 | /* BN_pseudo_rand is the same as BN_rand, now. */ |
| 720 | |
| 721 | int BN_pseudo_rand(BIGNUM *rnd, int bits, int top, int bottom) |
| 722 | { |
| 723 | return bnrand(1, rnd, bits, top, bottom); |
| 724 | } |
| 725 | |
| 726 | #define MONT_WORD /* use the faster word-based algorithm */ |
| 727 | |
| 728 | int BN_mod_mul_montgomery(BIGNUM *r, BIGNUM *a, BIGNUM *b, |
| 729 | BN_MONT_CTX *mont, BN_CTX *ctx) |
| 730 | { |
| 731 | BIGNUM *tmp,*tmp2; |
| 732 | int ret=0; |
| 733 | |
| 734 | BN_CTX_start(ctx); |
| 735 | tmp = BN_CTX_get(ctx); |
| 736 | tmp2 = BN_CTX_get(ctx); |
| 737 | if (tmp == NULL || tmp2 == NULL) goto err; |
| 738 | |
| 739 | bn_check_top(tmp); |
| 740 | bn_check_top(tmp2); |
| 741 | |
| 742 | if (a == b) |
| 743 | { |
| 744 | if (!BN_sqr(tmp,a,ctx)) goto err; |
| 745 | } |
| 746 | else |
| 747 | { |
| 748 | if (!BN_mul(tmp,a,b,ctx)) goto err; |
| 749 | } |
| 750 | /* reduce from aRR to aR */ |
| 751 | if (!BN_from_montgomery(r,tmp,mont,ctx)) goto err; |
| 752 | ret=1; |
| 753 | err: |
| 754 | BN_CTX_end(ctx); |
| 755 | return(ret); |
| 756 | } |
| 757 | |
| 758 | int BN_from_montgomery(BIGNUM *ret, BIGNUM *a, BN_MONT_CTX *mont, |
| 759 | BN_CTX *ctx) |
| 760 | { |
| 761 | int retn=0; |
| 762 | |
| 763 | #ifdef MONT_WORD |
| 764 | BIGNUM *n,*r; |
| 765 | BN_ULONG *ap,*np,*rp,n0,v,*nrp; |
| 766 | int al,nl,max,i,x,ri; |
| 767 | |
| 768 | BN_CTX_start(ctx); |
| 769 | if ((r = BN_CTX_get(ctx)) == NULL) goto err; |
| 770 | |
| 771 | if (!BN_copy(r,a)) goto err; |
| 772 | n= &(mont->N); |
| 773 | |
| 774 | ap=a->d; |
| 775 | /* mont->ri is the size of mont->N in bits (rounded up |
| 776 | to the word size) */ |
| 777 | al=ri=mont->ri/BN_BITS2; |
| 778 | |
| 779 | nl=n->top; |
| 780 | if ((al == 0) || (nl == 0)) { r->top=0; return(1); } |
| 781 | |
| 782 | max=(nl+al+1); /* allow for overflow (no?) XXX */ |
| 783 | if (bn_wexpand(r,max) == NULL) goto err; |
| 784 | if (bn_wexpand(ret,max) == NULL) goto err; |
| 785 | |
| 786 | r->neg=a->neg^n->neg; |
| 787 | np=n->d; |
| 788 | rp=r->d; |
| 789 | nrp= &(r->d[nl]); |
| 790 | |
| 791 | /* clear the top words of T */ |
| 792 | #if 1 |
| 793 | for (i=r->top; i<max; i++) /* memset? XXX */ |
| 794 | r->d[i]=0; |
| 795 | #else |
| 796 | memset(&(r->d[r->top]),0,(max-r->top)*sizeof(BN_ULONG)); |
| 797 | #endif |
| 798 | |
| 799 | r->top=max; |
| 800 | n0=mont->n0; |
| 801 | |
| 802 | #ifdef BN_COUNT |
| 803 | printf("word BN_from_montgomery %d * %d\n",nl,nl); |
| 804 | #endif |
| 805 | for (i=0; i<nl; i++) |
| 806 | { |
| 807 | #ifdef __TANDEM |
| 808 | { |
| 809 | long long t1; |
| 810 | long long t2; |
| 811 | long long t3; |
| 812 | t1 = rp[0] * (n0 & 0177777); |
| 813 | t2 = 037777600000l; |
| 814 | t2 = n0 & t2; |
| 815 | t3 = rp[0] & 0177777; |
| 816 | t2 = (t3 * t2) & BN_MASK2; |
| 817 | t1 = t1 + t2; |
| 818 | v=bn_mul_add_words(rp,np,nl,(BN_ULONG) t1); |
| 819 | } |
| 820 | #else |
| 821 | v=bn_mul_add_words(rp,np,nl,(rp[0]*n0)&BN_MASK2); |
| 822 | #endif |
| 823 | nrp++; |
| 824 | rp++; |
| 825 | if (((nrp[-1]+=v)&BN_MASK2) >= v) |
| 826 | continue; |
| 827 | else |
| 828 | { |
| 829 | if (((++nrp[0])&BN_MASK2) != 0) continue; |
| 830 | if (((++nrp[1])&BN_MASK2) != 0) continue; |
| 831 | for (x=2; (((++nrp[x])&BN_MASK2) == 0); x++) ; |
| 832 | } |
| 833 | } |
| 834 | bn_fix_top(r); |
| 835 | |
| 836 | /* mont->ri will be a multiple of the word size */ |
| 837 | #if 0 |
| 838 | BN_rshift(ret,r,mont->ri); |
| 839 | #else |
| 840 | ret->neg = r->neg; |
| 841 | x=ri; |
| 842 | rp=ret->d; |
| 843 | ap= &(r->d[x]); |
| 844 | if (r->top < x) |
| 845 | al=0; |
| 846 | else |
| 847 | al=r->top-x; |
| 848 | ret->top=al; |
| 849 | al-=4; |
| 850 | for (i=0; i<al; i+=4) |
| 851 | { |
| 852 | BN_ULONG t1,t2,t3,t4; |
| 853 | |
| 854 | t1=ap[i+0]; |
| 855 | t2=ap[i+1]; |
| 856 | t3=ap[i+2]; |
| 857 | t4=ap[i+3]; |
| 858 | rp[i+0]=t1; |
| 859 | rp[i+1]=t2; |
| 860 | rp[i+2]=t3; |
| 861 | rp[i+3]=t4; |
| 862 | } |
| 863 | al+=4; |
| 864 | for (; i<al; i++) |
| 865 | rp[i]=ap[i]; |
| 866 | #endif |
| 867 | #else /* !MONT_WORD */ |
| 868 | BIGNUM *t1,*t2; |
| 869 | |
| 870 | BN_CTX_start(ctx); |
| 871 | t1 = BN_CTX_get(ctx); |
| 872 | t2 = BN_CTX_get(ctx); |
| 873 | if (t1 == NULL || t2 == NULL) goto err; |
| 874 | |
| 875 | if (!BN_copy(t1,a)) goto err; |
| 876 | BN_mask_bits(t1,mont->ri); |
| 877 | |
| 878 | if (!BN_mul(t2,t1,&mont->Ni,ctx)) goto err; |
| 879 | BN_mask_bits(t2,mont->ri); |
| 880 | |
| 881 | if (!BN_mul(t1,t2,&mont->N,ctx)) goto err; |
| 882 | if (!BN_add(t2,a,t1)) goto err; |
| 883 | BN_rshift(ret,t2,mont->ri); |
| 884 | #endif /* MONT_WORD */ |
| 885 | |
| 886 | if (BN_ucmp(ret, &(mont->N)) >= 0) |
| 887 | { |
| 888 | BN_usub(ret,ret,&(mont->N)); |
| 889 | } |
| 890 | retn=1; |
| 891 | err: |
| 892 | BN_CTX_end(ctx); |
| 893 | return(retn); |
| 894 | } |
| 895 | |
| 896 | void BN_MONT_CTX_init(BN_MONT_CTX *ctx) |
| 897 | { |
| 898 | ctx->ri=0; |
| 899 | BN_init(&(ctx->RR)); |
| 900 | BN_init(&(ctx->N)); |
| 901 | BN_init(&(ctx->Ni)); |
| 902 | ctx->flags=0; |
| 903 | } |
| 904 | |
| 905 | BN_MONT_CTX *BN_MONT_CTX_new(void) |
| 906 | { |
| 907 | BN_MONT_CTX *ret; |
| 908 | |
| 909 | if ((ret=(BN_MONT_CTX *)malloc(sizeof(BN_MONT_CTX))) == NULL) |
| 910 | return(NULL); |
| 911 | |
| 912 | BN_MONT_CTX_init(ret); |
| 913 | ret->flags=BN_FLG_MALLOCED; |
| 914 | return(ret); |
| 915 | } |
| 916 | |
| 917 | void BN_MONT_CTX_free(BN_MONT_CTX *mont) |
| 918 | { |
| 919 | if(mont == NULL) |
| 920 | return; |
| 921 | |
| 922 | BN_free(&(mont->RR)); |
| 923 | BN_free(&(mont->N)); |
| 924 | BN_free(&(mont->Ni)); |
| 925 | if (mont->flags & BN_FLG_MALLOCED) |
| 926 | free(mont); |
| 927 | } |
| 928 | |
| 929 | int BN_MONT_CTX_set(BN_MONT_CTX *mont, const BIGNUM *mod, BN_CTX *ctx) |
| 930 | { |
| 931 | BIGNUM Ri,*R; |
| 932 | |
| 933 | BN_init(&Ri); |
| 934 | R= &(mont->RR); /* grab RR as a temp */ |
| 935 | BN_copy(&(mont->N),mod); /* Set N */ |
| 936 | |
| 937 | #ifdef MONT_WORD |
| 938 | { |
| 939 | BIGNUM tmod; |
| 940 | BN_ULONG buf[2]; |
| 941 | |
| 942 | mont->ri=(BN_num_bits(mod)+(BN_BITS2-1))/BN_BITS2*BN_BITS2; |
| 943 | BN_zero(R); |
| 944 | BN_set_bit(R,BN_BITS2); /* R */ |
| 945 | |
| 946 | buf[0]=mod->d[0]; /* tmod = N mod word size */ |
| 947 | buf[1]=0; |
| 948 | tmod.d=buf; |
| 949 | tmod.top=1; |
| 950 | tmod.dmax=2; |
| 951 | tmod.neg=mod->neg; |
| 952 | /* Ri = R^-1 mod N*/ |
| 953 | if ((BN_mod_inverse(&Ri,R,&tmod,ctx)) == NULL) |
| 954 | goto err; |
| 955 | BN_lshift(&Ri,&Ri,BN_BITS2); /* R*Ri */ |
| 956 | if (!BN_is_zero(&Ri)) |
| 957 | BN_sub_word(&Ri,1); |
| 958 | else /* if N mod word size == 1 */ |
| 959 | BN_set_word(&Ri,BN_MASK2); /* Ri-- (mod word size) */ |
| 960 | BN_div(&Ri,NULL,&Ri,&tmod,ctx); /* Ni = (R*Ri-1)/N, |
| 961 | * keep only least significant word: */ |
| 962 | mont->n0=Ri.d[0]; |
| 963 | BN_free(&Ri); |
| 964 | } |
| 965 | #else /* !MONT_WORD */ |
| 966 | { /* bignum version */ |
| 967 | mont->ri=BN_num_bits(mod); |
| 968 | BN_zero(R); |
| 969 | BN_set_bit(R,mont->ri); /* R = 2^ri */ |
| 970 | /* Ri = R^-1 mod N*/ |
| 971 | if ((BN_mod_inverse(&Ri,R,mod,ctx)) == NULL) |
| 972 | goto err; |
| 973 | BN_lshift(&Ri,&Ri,mont->ri); /* R*Ri */ |
| 974 | BN_sub_word(&Ri,1); |
| 975 | /* Ni = (R*Ri-1) / N */ |
| 976 | BN_div(&(mont->Ni),NULL,&Ri,mod,ctx); |
| 977 | BN_free(&Ri); |
| 978 | } |
| 979 | #endif |
| 980 | |
| 981 | /* setup RR for conversions */ |
| 982 | BN_zero(&(mont->RR)); |
| 983 | BN_set_bit(&(mont->RR),mont->ri*2); |
| 984 | BN_mod(&(mont->RR),&(mont->RR),&(mont->N),ctx); |
| 985 | |
| 986 | return(1); |
| 987 | err: |
| 988 | return(0); |
| 989 | } |
| 990 | |
| 991 | BIGNUM *BN_value_one(void) |
| 992 | { |
| 993 | static BN_ULONG data_one=1L; |
| 994 | static BIGNUM const_one={&data_one,1,1,0}; |
| 995 | |
| 996 | return(&const_one); |
| 997 | } |
| 998 | |
| 999 | /* solves ax == 1 (mod n) */ |
| 1000 | BIGNUM *BN_mod_inverse(BIGNUM *in, BIGNUM *a, const BIGNUM *n, BN_CTX *ctx) |
| 1001 | { |
| 1002 | BIGNUM *A,*B,*X,*Y,*M,*D,*R=NULL; |
| 1003 | BIGNUM *T,*ret=NULL; |
| 1004 | int sign; |
| 1005 | |
| 1006 | bn_check_top(a); |
| 1007 | bn_check_top(n); |
| 1008 | |
| 1009 | BN_CTX_start(ctx); |
| 1010 | A = BN_CTX_get(ctx); |
| 1011 | B = BN_CTX_get(ctx); |
| 1012 | X = BN_CTX_get(ctx); |
| 1013 | D = BN_CTX_get(ctx); |
| 1014 | M = BN_CTX_get(ctx); |
| 1015 | Y = BN_CTX_get(ctx); |
| 1016 | if (Y == NULL) goto err; |
| 1017 | |
| 1018 | if (in == NULL) |
| 1019 | R=BN_new(); |
| 1020 | else |
| 1021 | R=in; |
| 1022 | if (R == NULL) goto err; |
| 1023 | |
| 1024 | BN_zero(X); |
| 1025 | BN_one(Y); |
| 1026 | if (BN_copy(A,a) == NULL) goto err; |
| 1027 | if (BN_copy(B,n) == NULL) goto err; |
| 1028 | sign=1; |
| 1029 | |
| 1030 | while (!BN_is_zero(B)) |
| 1031 | { |
| 1032 | if (!BN_div(D,M,A,B,ctx)) goto err; |
| 1033 | T=A; |
| 1034 | A=B; |
| 1035 | B=M; |
| 1036 | /* T has a struct, M does not */ |
| 1037 | |
| 1038 | if (!BN_mul(T,D,X,ctx)) goto err; |
| 1039 | if (!BN_add(T,T,Y)) goto err; |
| 1040 | M=Y; |
| 1041 | Y=X; |
| 1042 | X=T; |
| 1043 | sign= -sign; |
| 1044 | } |
| 1045 | if (sign < 0) |
| 1046 | { |
| 1047 | if (!BN_sub(Y,n,Y)) goto err; |
| 1048 | } |
| 1049 | |
| 1050 | if (BN_is_one(A)) |
| 1051 | { if (!BN_mod(R,Y,n,ctx)) goto err; } |
| 1052 | else |
| 1053 | { |
| 1054 | goto err; |
| 1055 | } |
| 1056 | ret=R; |
| 1057 | err: |
| 1058 | if ((ret == NULL) && (in == NULL)) BN_free(R); |
| 1059 | BN_CTX_end(ctx); |
| 1060 | return(ret); |
| 1061 | } |
| 1062 | |
| 1063 | int BN_set_bit(BIGNUM *a, int n) |
| 1064 | { |
| 1065 | int i,j,k; |
| 1066 | |
| 1067 | i=n/BN_BITS2; |
| 1068 | j=n%BN_BITS2; |
| 1069 | if (a->top <= i) |
| 1070 | { |
| 1071 | if (bn_wexpand(a,i+1) == NULL) return(0); |
| 1072 | for(k=a->top; k<i+1; k++) |
| 1073 | a->d[k]=0; |
| 1074 | a->top=i+1; |
| 1075 | } |
| 1076 | |
| 1077 | a->d[i]|=(((BN_ULONG)1)<<j); |
| 1078 | return(1); |
| 1079 | } |
| 1080 | |
| 1081 | |
