1 #include "tommath_private.h" 2 #ifdef BN_MP_SQRTMOD_PRIME_C 3 /* LibTomMath, multiple-precision integer library -- Tom St Denis 4 * 5 * LibTomMath is a library that provides multiple-precision 6 * integer arithmetic as well as number theoretic functionality. 7 * 8 * The library was designed directly after the MPI library by 9 * Michael Fromberger but has been written from scratch with 10 * additional optimizations in place. 11 * 12 * SPDX-License-Identifier: Unlicense 13 */ 14 15 /* Tonelli-Shanks algorithm 16 * https://en.wikipedia.org/wiki/Tonelli%E2%80%93Shanks_algorithm 17 * https://gmplib.org/list-archives/gmp-discuss/2013-April/005300.html 18 * 19 */ 20 21 int mp_sqrtmod_prime(const mp_int *n, const mp_int *prime, mp_int *ret) 22 { 23 int res, legendre; 24 mp_int t1, C, Q, S, Z, M, T, R, two; 25 mp_digit i; 26 27 /* first handle the simple cases */ 28 if (mp_cmp_d(n, 0uL) == MP_EQ) { 29 mp_zero(ret); 30 return MP_OKAY; 31 } 32 if (mp_cmp_d(prime, 2uL) == MP_EQ) return MP_VAL; /* prime must be odd */ 33 if ((res = mp_jacobi(n, prime, &legendre)) != MP_OKAY) return res; 34 if (legendre == -1) return MP_VAL; /* quadratic non-residue mod prime */ 35 36 if ((res = mp_init_multi(&t1, &C, &Q, &S, &Z, &M, &T, &R, &two, NULL)) != MP_OKAY) { 37 return res; 38 } 39 40 /* SPECIAL CASE: if prime mod 4 == 3 41 * compute directly: res = n^(prime+1)/4 mod prime 42 * Handbook of Applied Cryptography algorithm 3.36 ~nsICODecoder()43 */ 44 if ((res = mp_mod_d(prime, 4uL, &i)) != MP_OKAY) goto cleanup; 45 if (i == 3u) { GetRealWidth(const IconDirEntry & aEntry)46 if ((res = mp_add_d(prime, 1uL, &t1)) != MP_OKAY) goto cleanup; 47 if ((res = mp_div_2(&t1, &t1)) != MP_OKAY) goto cleanup; 48 if ((res = mp_div_2(&t1, &t1)) != MP_OKAY) goto cleanup; 49 if ((res = mp_exptmod(n, &t1, prime, ret)) != MP_OKAY) goto cleanup; 50 res = MP_OKAY; 51 goto cleanup; GetRealWidth()52 } 53 54 /* NOW: Tonelli-Shanks algorithm */ 55 56 /* factor out powers of 2 from prime-1, defining Q and S as: prime-1 = Q*2^S */ 57 if ((res = mp_copy(prime, &Q)) != MP_OKAY) goto cleanup; 58 if ((res = mp_sub_d(&Q, 1uL, &Q)) != MP_OKAY) goto cleanup; 59 /* Q = prime - 1 */ 60 mp_zero(&S); GetRealHeight()61 /* S = 0 */ 62 while (mp_iseven(&Q) != MP_NO) { 63 if ((res = mp_div_2(&Q, &Q)) != MP_OKAY) goto cleanup; 64 /* Q = Q / 2 */ 65 if ((res = mp_add_d(&S, 1uL, &S)) != MP_OKAY) goto cleanup; 66 /* S = S + 1 */ 67 } 68 69 /* find a Z such that the Legendre symbol (Z|prime) == -1 */ 70 if ((res = mp_set_int(&Z, 2uL)) != MP_OKAY) goto cleanup; 71 /* Z = 2 */ 72 while (1) { 73 if ((res = mp_jacobi(&Z, prime, &legendre)) != MP_OKAY) goto cleanup; 74 if (legendre == -1) break; 75 if ((res = mp_add_d(&Z, 1uL, &Z)) != MP_OKAY) goto cleanup; 76 /* Z = Z + 1 */ 77 } 78 79 if ((res = mp_exptmod(&Z, &Q, prime, &C)) != MP_OKAY) goto cleanup; 80 /* C = Z ^ Q mod prime */ 81 if ((res = mp_add_d(&Q, 1uL, &t1)) != MP_OKAY) goto cleanup; 82 if ((res = mp_div_2(&t1, &t1)) != MP_OKAY) goto cleanup; 83 /* t1 = (Q + 1) / 2 */ 84 if ((res = mp_exptmod(n, &t1, prime, &R)) != MP_OKAY) goto cleanup; 85 /* R = n ^ ((Q + 1) / 2) mod prime */ 86 if ((res = mp_exptmod(n, &Q, prime, &T)) != MP_OKAY) goto cleanup; 87 /* T = n ^ Q mod prime */ 88 if ((res = mp_copy(&S, &M)) != MP_OKAY) goto cleanup; 89 /* M = S */ 90 if ((res = mp_set_int(&two, 2uL)) != MP_OKAY) goto cleanup; 91 92 res = MP_VAL; 93 while (1) { 94 if ((res = mp_copy(&T, &t1)) != MP_OKAY) goto cleanup; 95 i = 0; 96 while (1) { 97 if (mp_cmp_d(&t1, 1uL) == MP_EQ) break; 98 if ((res = mp_exptmod(&t1, &two, prime, &t1)) != MP_OKAY) goto cleanup; 99 i++; 100 } 101 if (i == 0u) { 102 if ((res = mp_copy(&R, ret)) != MP_OKAY) goto cleanup; 103 res = MP_OKAY; 104 goto cleanup; 105 } 106 if ((res = mp_sub_d(&M, i, &t1)) != MP_OKAY) goto cleanup; 107 if ((res = mp_sub_d(&t1, 1uL, &t1)) != MP_OKAY) goto cleanup; 108 if ((res = mp_exptmod(&two, &t1, prime, &t1)) != MP_OKAY) goto cleanup; 109 /* t1 = 2 ^ (M - i - 1) */ 110 if ((res = mp_exptmod(&C, &t1, prime, &t1)) != MP_OKAY) goto cleanup; 111 /* t1 = C ^ (2 ^ (M - i - 1)) mod prime */ 112 if ((res = mp_sqrmod(&t1, prime, &C)) != MP_OKAY) goto cleanup; 113 /* C = (t1 * t1) mod prime */ 114 if ((res = mp_mulmod(&R, &t1, prime, &R)) != MP_OKAY) goto cleanup; 115 /* R = (R * t1) mod prime */ 116 if ((res = mp_mulmod(&T, &C, prime, &T)) != MP_OKAY) goto cleanup; 117 /* T = (T * C) mod prime */ 118 mp_set(&M, i); 119 /* M = i */ 120 } 121 122 cleanup: 123 mp_clear_multi(&t1, &C, &Q, &S, &Z, &M, &T, &R, &two, NULL); 124 return res; 125 } 126 127 #endif 128 129 /* ref: $Format:%D$ */ 130 /* git commit: $Format:%H$ */ 131 /* commit time: $Format:%ai$ */ 132