|
1436
|
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 is free for all purposes without any express |
|
|
9 * guarantee it works. |
|
|
10 */ |
|
|
11 |
|
|
12 /* Tonelli-Shanks algorithm |
|
|
13 * https://en.wikipedia.org/wiki/Tonelli%E2%80%93Shanks_algorithm |
|
|
14 * https://gmplib.org/list-archives/gmp-discuss/2013-April/005300.html |
|
|
15 * |
|
|
16 */ |
|
|
17 |
|
|
18 int mp_sqrtmod_prime(mp_int *n, mp_int *prime, mp_int *ret) |
|
|
19 { |
|
|
20 int res, legendre; |
|
|
21 mp_int t1, C, Q, S, Z, M, T, R, two; |
|
|
22 mp_digit i; |
|
|
23 |
|
|
24 /* first handle the simple cases */ |
|
|
25 if (mp_cmp_d(n, 0) == MP_EQ) { |
|
|
26 mp_zero(ret); |
|
|
27 return MP_OKAY; |
|
|
28 } |
|
|
29 if (mp_cmp_d(prime, 2) == MP_EQ) return MP_VAL; /* prime must be odd */ |
|
|
30 if ((res = mp_jacobi(n, prime, &legendre)) != MP_OKAY) return res; |
|
|
31 if (legendre == -1) return MP_VAL; /* quadratic non-residue mod prime */ |
|
|
32 |
|
|
33 if ((res = mp_init_multi(&t1, &C, &Q, &S, &Z, &M, &T, &R, &two, NULL)) != MP_OKAY) { |
|
|
34 return res; |
|
|
35 } |
|
|
36 |
|
|
37 /* SPECIAL CASE: if prime mod 4 == 3 |
|
|
38 * compute directly: res = n^(prime+1)/4 mod prime |
|
|
39 * Handbook of Applied Cryptography algorithm 3.36 |
|
|
40 */ |
|
|
41 if ((res = mp_mod_d(prime, 4, &i)) != MP_OKAY) goto cleanup; |
|
|
42 if (i == 3) { |
|
|
43 if ((res = mp_add_d(prime, 1, &t1)) != MP_OKAY) goto cleanup; |
|
|
44 if ((res = mp_div_2(&t1, &t1)) != MP_OKAY) goto cleanup; |
|
|
45 if ((res = mp_div_2(&t1, &t1)) != MP_OKAY) goto cleanup; |
|
|
46 if ((res = mp_exptmod(n, &t1, prime, ret)) != MP_OKAY) goto cleanup; |
|
|
47 res = MP_OKAY; |
|
|
48 goto cleanup; |
|
|
49 } |
|
|
50 |
|
|
51 /* NOW: Tonelli-Shanks algorithm */ |
|
|
52 |
|
|
53 /* factor out powers of 2 from prime-1, defining Q and S as: prime-1 = Q*2^S */ |
|
|
54 if ((res = mp_copy(prime, &Q)) != MP_OKAY) goto cleanup; |
|
|
55 if ((res = mp_sub_d(&Q, 1, &Q)) != MP_OKAY) goto cleanup; |
|
|
56 /* Q = prime - 1 */ |
|
|
57 mp_zero(&S); |
|
|
58 /* S = 0 */ |
|
|
59 while (mp_iseven(&Q) != MP_NO) { |
|
|
60 if ((res = mp_div_2(&Q, &Q)) != MP_OKAY) goto cleanup; |
|
|
61 /* Q = Q / 2 */ |
|
|
62 if ((res = mp_add_d(&S, 1, &S)) != MP_OKAY) goto cleanup; |
|
|
63 /* S = S + 1 */ |
|
|
64 } |
|
|
65 |
|
|
66 /* find a Z such that the Legendre symbol (Z|prime) == -1 */ |
|
|
67 if ((res = mp_set_int(&Z, 2)) != MP_OKAY) goto cleanup; |
|
|
68 /* Z = 2 */ |
|
|
69 while(1) { |
|
|
70 if ((res = mp_jacobi(&Z, prime, &legendre)) != MP_OKAY) goto cleanup; |
|
|
71 if (legendre == -1) break; |
|
|
72 if ((res = mp_add_d(&Z, 1, &Z)) != MP_OKAY) goto cleanup; |
|
|
73 /* Z = Z + 1 */ |
|
|
74 } |
|
|
75 |
|
|
76 if ((res = mp_exptmod(&Z, &Q, prime, &C)) != MP_OKAY) goto cleanup; |
|
|
77 /* C = Z ^ Q mod prime */ |
|
|
78 if ((res = mp_add_d(&Q, 1, &t1)) != MP_OKAY) goto cleanup; |
|
|
79 if ((res = mp_div_2(&t1, &t1)) != MP_OKAY) goto cleanup; |
|
|
80 /* t1 = (Q + 1) / 2 */ |
|
|
81 if ((res = mp_exptmod(n, &t1, prime, &R)) != MP_OKAY) goto cleanup; |
|
|
82 /* R = n ^ ((Q + 1) / 2) mod prime */ |
|
|
83 if ((res = mp_exptmod(n, &Q, prime, &T)) != MP_OKAY) goto cleanup; |
|
|
84 /* T = n ^ Q mod prime */ |
|
|
85 if ((res = mp_copy(&S, &M)) != MP_OKAY) goto cleanup; |
|
|
86 /* M = S */ |
|
|
87 if ((res = mp_set_int(&two, 2)) != MP_OKAY) goto cleanup; |
|
|
88 |
|
|
89 res = MP_VAL; |
|
|
90 while (1) { |
|
|
91 if ((res = mp_copy(&T, &t1)) != MP_OKAY) goto cleanup; |
|
|
92 i = 0; |
|
|
93 while (1) { |
|
|
94 if (mp_cmp_d(&t1, 1) == MP_EQ) break; |
|
|
95 if ((res = mp_exptmod(&t1, &two, prime, &t1)) != MP_OKAY) goto cleanup; |
|
|
96 i++; |
|
|
97 } |
|
|
98 if (i == 0) { |
|
|
99 if ((res = mp_copy(&R, ret)) != MP_OKAY) goto cleanup; |
|
|
100 res = MP_OKAY; |
|
|
101 goto cleanup; |
|
|
102 } |
|
|
103 if ((res = mp_sub_d(&M, i, &t1)) != MP_OKAY) goto cleanup; |
|
|
104 if ((res = mp_sub_d(&t1, 1, &t1)) != MP_OKAY) goto cleanup; |
|
|
105 if ((res = mp_exptmod(&two, &t1, prime, &t1)) != MP_OKAY) goto cleanup; |
|
|
106 /* t1 = 2 ^ (M - i - 1) */ |
|
|
107 if ((res = mp_exptmod(&C, &t1, prime, &t1)) != MP_OKAY) goto cleanup; |
|
|
108 /* t1 = C ^ (2 ^ (M - i - 1)) mod prime */ |
|
|
109 if ((res = mp_sqrmod(&t1, prime, &C)) != MP_OKAY) goto cleanup; |
|
|
110 /* C = (t1 * t1) mod prime */ |
|
|
111 if ((res = mp_mulmod(&R, &t1, prime, &R)) != MP_OKAY) goto cleanup; |
|
|
112 /* R = (R * t1) mod prime */ |
|
|
113 if ((res = mp_mulmod(&T, &C, prime, &T)) != MP_OKAY) goto cleanup; |
|
|
114 /* T = (T * C) mod prime */ |
|
|
115 mp_set(&M, i); |
|
|
116 /* M = i */ |
|
|
117 } |
|
|
118 |
|
|
119 cleanup: |
|
|
120 mp_clear_multi(&t1, &C, &Q, &S, &Z, &M, &T, &R, &two, NULL); |
|
|
121 return res; |
|
|
122 } |
|
|
123 |
|
|
124 #endif |
