Line data Source code
1 : #include "tommath_private.h"
2 : #ifdef BN_MP_SQRTMOD_PRIME_C
3 : /* LibTomMath, multiple-precision integer library -- Tom St Denis */
4 : /* SPDX-License-Identifier: Unlicense */
5 :
6 : /* Tonelli-Shanks algorithm
7 : * https://en.wikipedia.org/wiki/Tonelli%E2%80%93Shanks_algorithm
8 : * https://gmplib.org/list-archives/gmp-discuss/2013-April/005300.html
9 : *
10 : */
11 :
12 0 : mp_err mp_sqrtmod_prime(const mp_int *n, const mp_int *prime, mp_int *ret)
13 : {
14 0 : mp_err err;
15 0 : int legendre;
16 0 : mp_int t1, C, Q, S, Z, M, T, R, two;
17 0 : mp_digit i;
18 :
19 : /* first handle the simple cases */
20 0 : if (mp_cmp_d(n, 0uL) == MP_EQ) {
21 0 : mp_zero(ret);
22 0 : return MP_OKAY;
23 : }
24 0 : if (mp_cmp_d(prime, 2uL) == MP_EQ) return MP_VAL; /* prime must be odd */
25 0 : if ((err = mp_kronecker(n, prime, &legendre)) != MP_OKAY) return err;
26 0 : if (legendre == -1) return MP_VAL; /* quadratic non-residue mod prime */
27 :
28 0 : if ((err = mp_init_multi(&t1, &C, &Q, &S, &Z, &M, &T, &R, &two, NULL)) != MP_OKAY) {
29 0 : return err;
30 : }
31 :
32 : /* SPECIAL CASE: if prime mod 4 == 3
33 : * compute directly: err = n^(prime+1)/4 mod prime
34 : * Handbook of Applied Cryptography algorithm 3.36
35 : */
36 0 : if ((err = mp_mod_d(prime, 4uL, &i)) != MP_OKAY) goto cleanup;
37 0 : if (i == 3u) {
38 0 : if ((err = mp_add_d(prime, 1uL, &t1)) != MP_OKAY) goto cleanup;
39 0 : if ((err = mp_div_2(&t1, &t1)) != MP_OKAY) goto cleanup;
40 0 : if ((err = mp_div_2(&t1, &t1)) != MP_OKAY) goto cleanup;
41 0 : if ((err = mp_exptmod(n, &t1, prime, ret)) != MP_OKAY) goto cleanup;
42 0 : err = MP_OKAY;
43 0 : goto cleanup;
44 : }
45 :
46 : /* NOW: Tonelli-Shanks algorithm */
47 :
48 : /* factor out powers of 2 from prime-1, defining Q and S as: prime-1 = Q*2^S */
49 0 : if ((err = mp_copy(prime, &Q)) != MP_OKAY) goto cleanup;
50 0 : if ((err = mp_sub_d(&Q, 1uL, &Q)) != MP_OKAY) goto cleanup;
51 : /* Q = prime - 1 */
52 0 : mp_zero(&S);
53 : /* S = 0 */
54 0 : while (MP_IS_EVEN(&Q)) {
55 0 : if ((err = mp_div_2(&Q, &Q)) != MP_OKAY) goto cleanup;
56 : /* Q = Q / 2 */
57 0 : if ((err = mp_add_d(&S, 1uL, &S)) != MP_OKAY) goto cleanup;
58 : /* S = S + 1 */
59 : }
60 :
61 : /* find a Z such that the Legendre symbol (Z|prime) == -1 */
62 0 : mp_set_u32(&Z, 2u);
63 : /* Z = 2 */
64 0 : for (;;) {
65 0 : if ((err = mp_kronecker(&Z, prime, &legendre)) != MP_OKAY) goto cleanup;
66 0 : if (legendre == -1) break;
67 0 : if ((err = mp_add_d(&Z, 1uL, &Z)) != MP_OKAY) goto cleanup;
68 : /* Z = Z + 1 */
69 : }
70 :
71 0 : if ((err = mp_exptmod(&Z, &Q, prime, &C)) != MP_OKAY) goto cleanup;
72 : /* C = Z ^ Q mod prime */
73 0 : if ((err = mp_add_d(&Q, 1uL, &t1)) != MP_OKAY) goto cleanup;
74 0 : if ((err = mp_div_2(&t1, &t1)) != MP_OKAY) goto cleanup;
75 : /* t1 = (Q + 1) / 2 */
76 0 : if ((err = mp_exptmod(n, &t1, prime, &R)) != MP_OKAY) goto cleanup;
77 : /* R = n ^ ((Q + 1) / 2) mod prime */
78 0 : if ((err = mp_exptmod(n, &Q, prime, &T)) != MP_OKAY) goto cleanup;
79 : /* T = n ^ Q mod prime */
80 0 : if ((err = mp_copy(&S, &M)) != MP_OKAY) goto cleanup;
81 : /* M = S */
82 0 : mp_set_u32(&two, 2u);
83 :
84 0 : for (;;) {
85 0 : if ((err = mp_copy(&T, &t1)) != MP_OKAY) goto cleanup;
86 0 : i = 0;
87 0 : for (;;) {
88 0 : if (mp_cmp_d(&t1, 1uL) == MP_EQ) break;
89 0 : if ((err = mp_exptmod(&t1, &two, prime, &t1)) != MP_OKAY) goto cleanup;
90 0 : i++;
91 : }
92 0 : if (i == 0u) {
93 0 : if ((err = mp_copy(&R, ret)) != MP_OKAY) goto cleanup;
94 0 : err = MP_OKAY;
95 0 : goto cleanup;
96 : }
97 0 : if ((err = mp_sub_d(&M, i, &t1)) != MP_OKAY) goto cleanup;
98 0 : if ((err = mp_sub_d(&t1, 1uL, &t1)) != MP_OKAY) goto cleanup;
99 0 : if ((err = mp_exptmod(&two, &t1, prime, &t1)) != MP_OKAY) goto cleanup;
100 : /* t1 = 2 ^ (M - i - 1) */
101 0 : if ((err = mp_exptmod(&C, &t1, prime, &t1)) != MP_OKAY) goto cleanup;
102 : /* t1 = C ^ (2 ^ (M - i - 1)) mod prime */
103 0 : if ((err = mp_sqrmod(&t1, prime, &C)) != MP_OKAY) goto cleanup;
104 : /* C = (t1 * t1) mod prime */
105 0 : if ((err = mp_mulmod(&R, &t1, prime, &R)) != MP_OKAY) goto cleanup;
106 : /* R = (R * t1) mod prime */
107 0 : if ((err = mp_mulmod(&T, &C, prime, &T)) != MP_OKAY) goto cleanup;
108 : /* T = (T * C) mod prime */
109 0 : mp_set(&M, i);
110 : /* M = i */
111 : }
112 :
113 0 : cleanup:
114 0 : mp_clear_multi(&t1, &C, &Q, &S, &Z, &M, &T, &R, &two, NULL);
115 0 : return err;
116 : }
117 :
118 : #endif
|
