1 // SPDX-License-Identifier: BSD-2-Clause
2 /* LibTomCrypt, modular cryptographic library -- Tom St Denis
3 *
4 * LibTomCrypt is a library that provides various cryptographic
5 * algorithms in a highly modular and flexible manner.
6 *
7 * The library is free for all purposes without any express
8 * guarantee it works.
9 */
10 #include "tomcrypt_private.h"
11
12 /**
13 @file dsa_generate_pqg.c
14 DSA implementation - generate DSA parameters p, q & g
15 */
16
17 #ifdef LTC_MDSA
18
19 /**
20 Create DSA parameters (INTERNAL ONLY, not part of public API)
21 @param prng An active PRNG state
22 @param wprng The index of the PRNG desired
23 @param group_size Size of the multiplicative group (octets)
24 @param modulus_size Size of the modulus (octets)
25 @param p [out] bignum where generated 'p' is stored (must be initialized by caller)
26 @param q [out] bignum where generated 'q' is stored (must be initialized by caller)
27 @param g [out] bignum where generated 'g' is stored (must be initialized by caller)
28 @return CRYPT_OK if successful, upon error this function will free all allocated memory
29 */
_dsa_make_params(prng_state * prng,int wprng,int group_size,int modulus_size,void * p,void * q,void * g)30 static int _dsa_make_params(prng_state *prng, int wprng, int group_size, int modulus_size, void *p, void *q, void *g)
31 {
32 unsigned long L, N, n, outbytes, seedbytes, counter, j, i;
33 int err, res, mr_tests_q, mr_tests_p, found_p, found_q, hash;
34 unsigned char *wbuf, *sbuf, digest[MAXBLOCKSIZE];
35 void *t2L1, *t2N1, *t2q, *t2seedlen, *U, *W, *X, *c, *h, *e, *seedinc;
36
37 /* check size */
38 if (group_size >= LTC_MDSA_MAX_GROUP || group_size < 1 || group_size >= modulus_size) {
39 return CRYPT_INVALID_ARG;
40 }
41
42 /* FIPS-186-4 A.1.1.2 Generation of the Probable Primes p and q Using an Approved Hash Function
43 *
44 * L = The desired length of the prime p (in bits e.g. L = 1024)
45 * N = The desired length of the prime q (in bits e.g. N = 160)
46 * seedlen = The desired bit length of the domain parameter seed; seedlen shallbe equal to or greater than N
47 * outlen = The bit length of Hash function
48 *
49 * 1. Check that the (L, N)
50 * 2. If (seedlen <N), then return INVALID.
51 * 3. n = ceil(L / outlen) - 1
52 * 4. b = L- 1 - (n * outlen)
53 * 5. domain_parameter_seed = an arbitrary sequence of seedlen bits
54 * 6. U = Hash (domain_parameter_seed) mod 2^(N-1)
55 * 7. q = 2^(N-1) + U + 1 - (U mod 2)
56 * 8. Test whether or not q is prime as specified in Appendix C.3
57 * 9. If qis not a prime, then go to step 5.
58 * 10. offset = 1
59 * 11. For counter = 0 to (4L- 1) do {
60 * For j=0 to n do {
61 * Vj = Hash ((domain_parameter_seed+ offset + j) mod 2^seedlen
62 * }
63 * W = V0 + (V1 *2^outlen) + ... + (Vn-1 * 2^((n-1) * outlen)) + ((Vn mod 2^b) * 2^(n * outlen))
64 * X = W + 2^(L-1) Comment: 0 <= W < 2^(L-1); hence 2^(L-1) <= X < 2^L
65 * c = X mod 2*q
66 * p = X - (c - 1) Comment: p ~ 1 (mod 2*q)
67 * If (p >= 2^(L-1)) {
68 * Test whether or not p is prime as specified in Appendix C.3.
69 * If p is determined to be prime, then return VALID and the values of p, qand (optionally) the values of domain_parameter_seed and counter
70 * }
71 * offset = offset + n + 1 Comment: Increment offset
72 * }
73 */
74
75 seedbytes = group_size;
76 L = (unsigned long)modulus_size * 8;
77 N = (unsigned long)group_size * 8;
78
79 /* XXX-TODO no Lucas test */
80 #ifdef LTC_MPI_HAS_LUCAS_TEST
81 /* M-R tests (when followed by one Lucas test) according FIPS-186-4 - Appendix C.3 - table C.1 */
82 mr_tests_p = (L <= 2048) ? 3 : 2;
83 if (N <= 160) { mr_tests_q = 19; }
84 else if (N <= 224) { mr_tests_q = 24; }
85 else { mr_tests_q = 27; }
86 #else
87 /* M-R tests (without Lucas test) according FIPS-186-4 - Appendix C.3 - table C.1 */
88 if (L <= 1024) { mr_tests_p = 40; }
89 else if (L <= 2048) { mr_tests_p = 56; }
90 else { mr_tests_p = 64; }
91
92 if (N <= 160) { mr_tests_q = 40; }
93 else if (N <= 224) { mr_tests_q = 56; }
94 else { mr_tests_q = 64; }
95 #endif
96
97 if (N <= 256) {
98 hash = register_hash(&sha256_desc);
99 }
100 else if (N <= 384) {
101 hash = register_hash(&sha384_desc);
102 }
103 else if (N <= 512) {
104 hash = register_hash(&sha512_desc);
105 }
106 else {
107 return CRYPT_INVALID_ARG; /* group_size too big */
108 }
109
110 if ((err = hash_is_valid(hash)) != CRYPT_OK) { return err; }
111 outbytes = hash_descriptor[hash]->hashsize;
112
113 n = ((L + outbytes*8 - 1) / (outbytes*8)) - 1;
114
115 if ((wbuf = XMALLOC((n+1)*outbytes)) == NULL) { err = CRYPT_MEM; goto cleanup3; }
116 if ((sbuf = XMALLOC(seedbytes)) == NULL) { err = CRYPT_MEM; goto cleanup2; }
117
118 err = mp_init_multi(&t2L1, &t2N1, &t2q, &t2seedlen, &U, &W, &X, &c, &h, &e, &seedinc, NULL);
119 if (err != CRYPT_OK) { goto cleanup1; }
120
121 if ((err = mp_2expt(t2L1, L-1)) != CRYPT_OK) { goto cleanup; }
122 /* t2L1 = 2^(L-1) */
123 if ((err = mp_2expt(t2N1, N-1)) != CRYPT_OK) { goto cleanup; }
124 /* t2N1 = 2^(N-1) */
125 if ((err = mp_2expt(t2seedlen, seedbytes*8)) != CRYPT_OK) { goto cleanup; }
126 /* t2seedlen = 2^seedlen */
127
128 for(found_p=0; !found_p;) {
129 /* q */
130 for(found_q=0; !found_q;) {
131 if (prng_descriptor[wprng]->read(sbuf, seedbytes, prng) != seedbytes) { err = CRYPT_ERROR_READPRNG; goto cleanup; }
132 i = outbytes;
133 if ((err = hash_memory(hash, sbuf, seedbytes, digest, &i)) != CRYPT_OK) { goto cleanup; }
134 if ((err = mp_read_unsigned_bin(U, digest, outbytes)) != CRYPT_OK) { goto cleanup; }
135 if ((err = mp_mod(U, t2N1, U)) != CRYPT_OK) { goto cleanup; }
136 if ((err = mp_add(t2N1, U, q)) != CRYPT_OK) { goto cleanup; }
137 if (!mp_isodd(q)) mp_add_d(q, 1, q);
138 if ((err = mp_prime_is_prime(q, mr_tests_q, &res)) != CRYPT_OK) { goto cleanup; }
139 if (res == LTC_MP_YES) found_q = 1;
140 }
141
142 /* p */
143 if ((err = mp_read_unsigned_bin(seedinc, sbuf, seedbytes)) != CRYPT_OK) { goto cleanup; }
144 if ((err = mp_add(q, q, t2q)) != CRYPT_OK) { goto cleanup; }
145 for(counter=0; counter < 4*L && !found_p; counter++) {
146 for(j=0; j<=n; j++) {
147 if ((err = mp_add_d(seedinc, 1, seedinc)) != CRYPT_OK) { goto cleanup; }
148 if ((err = mp_mod(seedinc, t2seedlen, seedinc)) != CRYPT_OK) { goto cleanup; }
149 /* seedinc = (seedinc+1) % 2^seed_bitlen */
150 if ((i = mp_unsigned_bin_size(seedinc)) > seedbytes) { err = CRYPT_INVALID_ARG; goto cleanup; }
151 zeromem(sbuf, seedbytes);
152 if ((err = mp_to_unsigned_bin(seedinc, sbuf + seedbytes-i)) != CRYPT_OK) { goto cleanup; }
153 i = outbytes;
154 err = hash_memory(hash, sbuf, seedbytes, wbuf+(n-j)*outbytes, &i);
155 if (err != CRYPT_OK) { goto cleanup; }
156 }
157 if ((err = mp_read_unsigned_bin(W, wbuf, (n+1)*outbytes)) != CRYPT_OK) { goto cleanup; }
158 if ((err = mp_mod(W, t2L1, W)) != CRYPT_OK) { goto cleanup; }
159 if ((err = mp_add(W, t2L1, X)) != CRYPT_OK) { goto cleanup; }
160 if ((err = mp_mod(X, t2q, c)) != CRYPT_OK) { goto cleanup; }
161 if ((err = mp_sub_d(c, 1, p)) != CRYPT_OK) { goto cleanup; }
162 if ((err = mp_sub(X, p, p)) != CRYPT_OK) { goto cleanup; }
163 if (mp_cmp(p, t2L1) != LTC_MP_LT) {
164 /* p >= 2^(L-1) */
165 if ((err = mp_prime_is_prime(p, mr_tests_p, &res)) != CRYPT_OK) { goto cleanup; }
166 if (res == LTC_MP_YES) {
167 found_p = 1;
168 }
169 }
170 }
171 }
172
173 /* FIPS-186-4 A.2.1 Unverifiable Generation of the Generator g
174 * 1. e = (p - 1)/q
175 * 2. h = any integer satisfying: 1 < h < (p - 1)
176 * h could be obtained from a random number generator or from a counter that changes after each use
177 * 3. g = h^e mod p
178 * 4. if (g == 1), then go to step 2.
179 *
180 */
181
182 if ((err = mp_sub_d(p, 1, e)) != CRYPT_OK) { goto cleanup; }
183 if ((err = mp_div(e, q, e, c)) != CRYPT_OK) { goto cleanup; }
184 /* e = (p - 1)/q */
185 i = mp_count_bits(p);
186 do {
187 do {
188 if ((err = rand_bn_bits(h, i, prng, wprng)) != CRYPT_OK) { goto cleanup; }
189 } while (mp_cmp(h, p) != LTC_MP_LT || mp_cmp_d(h, 2) != LTC_MP_GT);
190 if ((err = mp_sub_d(h, 1, h)) != CRYPT_OK) { goto cleanup; }
191 /* h is randon and 1 < h < (p-1) */
192 if ((err = mp_exptmod(h, e, p, g)) != CRYPT_OK) { goto cleanup; }
193 } while (mp_cmp_d(g, 1) == LTC_MP_EQ);
194
195 err = CRYPT_OK;
196 cleanup:
197 mp_clear_multi(t2L1, t2N1, t2q, t2seedlen, U, W, X, c, h, e, seedinc, NULL);
198 cleanup1:
199 XFREE(sbuf);
200 cleanup2:
201 XFREE(wbuf);
202 cleanup3:
203 return err;
204 }
205
206 /**
207 Generate DSA parameters p, q & g
208 @param prng An active PRNG state
209 @param wprng The index of the PRNG desired
210 @param group_size Size of the multiplicative group (octets)
211 @param modulus_size Size of the modulus (octets)
212 @param key [out] Where to store the created key
213 @return CRYPT_OK if successful.
214 */
dsa_generate_pqg(prng_state * prng,int wprng,int group_size,int modulus_size,dsa_key * key)215 int dsa_generate_pqg(prng_state *prng, int wprng, int group_size, int modulus_size, dsa_key *key)
216 {
217 int err;
218
219 LTC_ARGCHK(key != NULL);
220 LTC_ARGCHK(ltc_mp.name != NULL);
221
222 /* init mp_ints */
223 if ((err = mp_init_multi(&key->p, &key->g, &key->q, &key->x, &key->y, NULL)) != CRYPT_OK) {
224 return err;
225 }
226 /* generate params */
227 err = _dsa_make_params(prng, wprng, group_size, modulus_size, key->p, key->q, key->g);
228 if (err != CRYPT_OK) {
229 goto cleanup;
230 }
231
232 key->qord = group_size;
233
234 return CRYPT_OK;
235
236 cleanup:
237 dsa_free(key);
238 return err;
239 }
240
241 #endif
242
243 /* ref: $Format:%D$ */
244 /* git commit: $Format:%H$ */
245 /* commit time: $Format:%ai$ */
246