Mercurial > dropbear
comparison libtommath/bn_mp_sqrtmod_prime.c @ 1655:f52919ffd3b1
update ltm to 1.1.0 and enable FIPS 186.4 compliant key-generation (#79)
* make key-generation compliant to FIPS 186.4
* fix includes in tommath_class.h
* update fuzzcorpus instead of error-out
* fixup fuzzing make-targets
* update Makefile.in
* apply necessary patches to ltm sources
* clean-up not required ltm files
* update to vanilla ltm 1.1.0
this already only contains the required files
* remove set/get double
author | Steffen Jaeckel <s_jaeckel@gmx.de> |
---|---|
date | Mon, 16 Sep 2019 15:50:38 +0200 |
parents | 60fc6476e044 |
children | 1051e4eea25a |
comparison
equal
deleted
inserted
replaced
1654:cc0fc5131c5c | 1655:f52919ffd3b1 |
---|---|
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 * |
5 * LibTomMath is a library that provides multiple-precision | 5 * LibTomMath is a library that provides multiple-precision |
6 * integer arithmetic as well as number theoretic functionality. | 6 * integer arithmetic as well as number theoretic functionality. |
7 * | 7 * |
8 * The library is free for all purposes without any express | 8 * The library was designed directly after the MPI library by |
9 * guarantee it works. | 9 * Michael Fromberger but has been written from scratch with |
10 * additional optimizations in place. | |
11 * | |
12 * SPDX-License-Identifier: Unlicense | |
10 */ | 13 */ |
11 | 14 |
12 /* Tonelli-Shanks algorithm | 15 /* Tonelli-Shanks algorithm |
13 * https://en.wikipedia.org/wiki/Tonelli%E2%80%93Shanks_algorithm | 16 * https://en.wikipedia.org/wiki/Tonelli%E2%80%93Shanks_algorithm |
14 * https://gmplib.org/list-archives/gmp-discuss/2013-April/005300.html | 17 * https://gmplib.org/list-archives/gmp-discuss/2013-April/005300.html |
15 * | 18 * |
16 */ | 19 */ |
17 | 20 |
18 int mp_sqrtmod_prime(mp_int *n, mp_int *prime, mp_int *ret) | 21 int mp_sqrtmod_prime(const mp_int *n, const mp_int *prime, mp_int *ret) |
19 { | 22 { |
20 int res, legendre; | 23 int res, legendre; |
21 mp_int t1, C, Q, S, Z, M, T, R, two; | 24 mp_int t1, C, Q, S, Z, M, T, R, two; |
22 mp_digit i; | 25 mp_digit i; |
23 | 26 |
24 /* first handle the simple cases */ | 27 /* first handle the simple cases */ |
25 if (mp_cmp_d(n, 0) == MP_EQ) { | 28 if (mp_cmp_d(n, 0uL) == MP_EQ) { |
26 mp_zero(ret); | 29 mp_zero(ret); |
27 return MP_OKAY; | 30 return MP_OKAY; |
28 } | 31 } |
29 if (mp_cmp_d(prime, 2) == MP_EQ) return MP_VAL; /* prime must be odd */ | 32 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; | 33 if ((res = mp_jacobi(n, prime, &legendre)) != MP_OKAY) return res; |
31 if (legendre == -1) return MP_VAL; /* quadratic non-residue mod prime */ | 34 if (legendre == -1) return MP_VAL; /* quadratic non-residue mod prime */ |
32 | 35 |
33 if ((res = mp_init_multi(&t1, &C, &Q, &S, &Z, &M, &T, &R, &two, NULL)) != MP_OKAY) { | 36 if ((res = mp_init_multi(&t1, &C, &Q, &S, &Z, &M, &T, &R, &two, NULL)) != MP_OKAY) { |
34 return res; | 37 return res; |
35 } | 38 } |
36 | 39 |
37 /* SPECIAL CASE: if prime mod 4 == 3 | 40 /* SPECIAL CASE: if prime mod 4 == 3 |
38 * compute directly: res = n^(prime+1)/4 mod prime | 41 * compute directly: res = n^(prime+1)/4 mod prime |
39 * Handbook of Applied Cryptography algorithm 3.36 | 42 * Handbook of Applied Cryptography algorithm 3.36 |
40 */ | 43 */ |
41 if ((res = mp_mod_d(prime, 4, &i)) != MP_OKAY) goto cleanup; | 44 if ((res = mp_mod_d(prime, 4uL, &i)) != MP_OKAY) goto cleanup; |
42 if (i == 3) { | 45 if (i == 3u) { |
43 if ((res = mp_add_d(prime, 1, &t1)) != MP_OKAY) goto cleanup; | 46 if ((res = mp_add_d(prime, 1uL, &t1)) != MP_OKAY) goto cleanup; |
44 if ((res = mp_div_2(&t1, &t1)) != MP_OKAY) goto cleanup; | 47 if ((res = mp_div_2(&t1, &t1)) != MP_OKAY) goto cleanup; |
45 if ((res = mp_div_2(&t1, &t1)) != MP_OKAY) goto cleanup; | 48 if ((res = mp_div_2(&t1, &t1)) != MP_OKAY) goto cleanup; |
46 if ((res = mp_exptmod(n, &t1, prime, ret)) != MP_OKAY) goto cleanup; | 49 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; | 50 res = MP_OKAY; |
101 goto cleanup; | 51 goto cleanup; |
102 } | 52 } |
103 if ((res = mp_sub_d(&M, i, &t1)) != MP_OKAY) goto cleanup; | 53 |
104 if ((res = mp_sub_d(&t1, 1, &t1)) != MP_OKAY) goto cleanup; | 54 /* NOW: Tonelli-Shanks algorithm */ |
105 if ((res = mp_exptmod(&two, &t1, prime, &t1)) != MP_OKAY) goto cleanup; | 55 |
106 /* t1 = 2 ^ (M - i - 1) */ | 56 /* factor out powers of 2 from prime-1, defining Q and S as: prime-1 = Q*2^S */ |
107 if ((res = mp_exptmod(&C, &t1, prime, &t1)) != MP_OKAY) goto cleanup; | 57 if ((res = mp_copy(prime, &Q)) != MP_OKAY) goto cleanup; |
108 /* t1 = C ^ (2 ^ (M - i - 1)) mod prime */ | 58 if ((res = mp_sub_d(&Q, 1uL, &Q)) != MP_OKAY) goto cleanup; |
109 if ((res = mp_sqrmod(&t1, prime, &C)) != MP_OKAY) goto cleanup; | 59 /* Q = prime - 1 */ |
110 /* C = (t1 * t1) mod prime */ | 60 mp_zero(&S); |
111 if ((res = mp_mulmod(&R, &t1, prime, &R)) != MP_OKAY) goto cleanup; | 61 /* S = 0 */ |
112 /* R = (R * t1) mod prime */ | 62 while (mp_iseven(&Q) != MP_NO) { |
113 if ((res = mp_mulmod(&T, &C, prime, &T)) != MP_OKAY) goto cleanup; | 63 if ((res = mp_div_2(&Q, &Q)) != MP_OKAY) goto cleanup; |
114 /* T = (T * C) mod prime */ | 64 /* Q = Q / 2 */ |
115 mp_set(&M, i); | 65 if ((res = mp_add_d(&S, 1uL, &S)) != MP_OKAY) goto cleanup; |
116 /* M = i */ | 66 /* S = S + 1 */ |
117 } | 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 } | |
118 | 121 |
119 cleanup: | 122 cleanup: |
120 mp_clear_multi(&t1, &C, &Q, &S, &Z, &M, &T, &R, &two, NULL); | 123 mp_clear_multi(&t1, &C, &Q, &S, &Z, &M, &T, &R, &two, NULL); |
121 return res; | 124 return res; |
122 } | 125 } |
123 | 126 |
124 #endif | 127 #endif |
128 | |
129 /* ref: HEAD -> master, tag: v1.1.0 */ | |
130 /* git commit: 08549ad6bc8b0cede0b357a9c341c5c6473a9c55 */ | |
131 /* commit time: 2019-01-28 20:32:32 +0100 */ |