Mercurial > dropbear

comparison libtommath/bn_mp_sqrtmod_prime.c @ 1739:13d834efc376 fuzz

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