diff options
author | Niels Möller <nisse@lysator.liu.se> | 2010-05-25 17:21:19 +0200 |
---|---|---|
committer | Niels Möller <nisse@lysator.liu.se> | 2010-05-25 17:21:19 +0200 |
commit | 58d64578dc319eff8c54786df80f1d6b906ad3ec (patch) | |
tree | ead70ebc46d832f5a676a260e4c84f6f243fb707 /dsa-keygen.c | |
parent | 7dfa2498ef5237eddaf542d8664f7604e0702438 (diff) | |
download | nettle-58d64578dc319eff8c54786df80f1d6b906ad3ec.tar.gz |
(dsa_generate_keypair): Rewritten, now generating primes using
Pocklington's theorem. Takes both p_size and q_size as arguments.
Rev: nettle/dsa-keygen.c:1.4
Rev: nettle/dsa.h:1.5
Diffstat (limited to 'dsa-keygen.c')
-rw-r--r-- | dsa-keygen.c | 129 |
1 files changed, 129 insertions, 0 deletions
diff --git a/dsa-keygen.c b/dsa-keygen.c index 7871c515..1d67168c 100644 --- a/dsa-keygen.c +++ b/dsa-keygen.c @@ -27,6 +27,7 @@ # include "config.h" #endif +#include <assert.h> #include <stdlib.h> #include "dsa.h" @@ -35,6 +36,133 @@ #include "memxor.h" #include "nettle-internal.h" + +/* Valid sizes, according to FIPS 186-3 are (1024, 160), (2048. 224), + (2048, 256), (3072, 256). Currenty, we use only q_bits of 160 or + 256. */ +int +dsa_generate_keypair(struct dsa_public_key *pub, + struct dsa_private_key *key, + void *ctx, nettle_random_func random, + void *progress_ctx, nettle_progress_func progress, + unsigned p_bits, unsigned q_bits) +{ + mpz_t p0, p0q, i, r, pm1, y; + unsigned p0_bits; + unsigned a; + + switch (q_bits) + { + case 160: + if (p_bits < 512) + return 0; + break; + case 256: + if (p_bits < 1024) + return 0; + break; + default: + return 0; + } + + nettle_random_prime (pub->q, q_bits, ctx, random); + + mpz_init (p0); + p0_bits = (p_bits + 3)/2; + + nettle_random_prime (p0, p0_bits, ctx, random); + + /* Generate p = r q p0 + 1, such that 2^{n-1} < p < 2^n. + * + * Then r = (p-1) / (q p0) < (2^n-2) / (q p0) + * + * and r >= 2^{n-1} (q p0). + * + * FIXME: Check further. */ + + mpz_init (p0q); + mpz_mul (p0q, p0, pub->q); + + mpz_init_set_ui (i, 1); + mpz_mul_2exp (i, i, p_bits-2); + mpz_fdiv_q (i, i, p0q); + + mpz_init (r); + mpz_init (pm1); + mpz_init (y); + + for (;;) + { + uint8_t buf[1]; + + /* Generate r in the range i + 1 <= r <= 2*i */ + nettle_mpz_random (r, ctx, random, i); + mpz_add (r, r, i); + mpz_add_ui (r, r, 1); + + /* Set p = 2*r*q*p0 + 1 */ + mpz_mul_2exp(r, r, 1); + mpz_mul (pm1, r, p0q); + mpz_add_ui (pub->p, pm1, 1); + + assert(mpz_sizeinbase(pub->p, 2) == p_bits); + + if (!mpz_probab_prime_p (pub->p, 1)) + continue; + + random(ctx, sizeof(buf), buf); + + a = buf[0] + 2; + mpz_set_ui (y, a); + + /* Pocklington's theorem. Check + * + * a^{p-1} = 1 (mod p) + * gcd(a^{p-1} / p0, p) = 1 + */ + + mpz_powm (y, y, pm1, pub->p); + if (mpz_cmp_ui (y, 1) != 0) + continue; + + /* (p-1) / p0 = q * r */ + mpz_set_ui (y, a); + mpz_powm (y, y, pub->q, pub->p); + mpz_powm (y, y, r, pub->p); + mpz_sub_ui (y, y, 1); + mpz_gcd (y, y, pub->p); + if (mpz_cmp_ui (y, 1) == 0) + break; + } + + mpz_mul (r, r, p0); + + for (a = 2; ; a++) + { + mpz_set_ui (y, a); + mpz_powm (pub->g, y, r, pub->p); + if (mpz_cmp_ui (pub->g, 1) != 0) + break; + } + + mpz_init_set(r, pub->q); + mpz_sub_ui(r, r, 2); + nettle_mpz_random(key->x, ctx, random, r); + + mpz_add_ui(key->x, key->x, 1); + + mpz_powm(pub->y, pub->g, key->x, pub->p); + + mpz_clear (p0); + mpz_clear (p0q); + mpz_clear (r); + mpz_clear (pm1); + mpz_clear (y); + + return 1; +} +#if 0 + /* FIXME: Update for fips186-3. p,q: A.1, g: A.2, x,y: B.1, Shawe-Taylor: C.6 */ @@ -250,3 +378,4 @@ dsa_generate_keypair(struct dsa_public_key *pub, return 1; } +#endif |