diff options
author | Bernd Edlinger <bernd.edlinger@hotmail.de> | 2019-07-10 15:52:36 +0200 |
---|---|---|
committer | Bernd Edlinger <bernd.edlinger@hotmail.de> | 2019-07-24 14:59:52 +0200 |
commit | ddd16c2fe988ed9fdd5118c2f2617745438fd675 (patch) | |
tree | 08eb4554b256062b40bbc9885edf2153c2b87fcf /crypto/dh/dh_gen.c | |
parent | 8e747338593f3bafe9798226cddf4edf36bc2de9 (diff) |
Change DH parameters to generate the order q subgroup instead of 2q
This avoids leaking bit 0 of the private key.
Backport-of: #9363
Reviewed-by: Kurt Roeckx <kurt@roeckx.be>
(Merged from https://github.com/openssl/openssl/pull/9435)
Diffstat (limited to 'crypto/dh/dh_gen.c')
-rw-r--r-- | crypto/dh/dh_gen.c | 52 |
1 files changed, 24 insertions, 28 deletions
diff --git a/crypto/dh/dh_gen.c b/crypto/dh/dh_gen.c index 887fc4c3ae..1262d4e155 100644 --- a/crypto/dh/dh_gen.c +++ b/crypto/dh/dh_gen.c @@ -30,30 +30,29 @@ int DH_generate_parameters_ex(DH *ret, int prime_len, int generator, /*- * We generate DH parameters as follows - * find a prime q which is prime_len/2 bits long. - * p=(2*q)+1 or (p-1)/2 = q - * For this case, g is a generator if - * g^((p-1)/q) mod p != 1 for values of q which are the factors of p-1. - * Since the factors of p-1 are q and 2, we just need to check - * g^2 mod p != 1 and g^q mod p != 1. + * find a prime p which is prime_len bits long, + * where q=(p-1)/2 is also prime. + * In the following we assume that g is not 0, 1 or p-1, since it + * would generate only trivial subgroups. + * For this case, g is a generator of the order-q subgroup if + * g^q mod p == 1. + * Or in terms of the Legendre symbol: (g/p) == 1. * * Having said all that, * there is another special case method for the generators 2, 3 and 5. - * for 2, p mod 24 == 11 - * for 3, p mod 12 == 5 <<<<< does not work for safe primes. - * for 5, p mod 10 == 3 or 7 + * Using the quadratic reciprocity law it is possible to solve + * (g/p) == 1 for the special values 2, 3, 5: + * (2/p) == 1 if p mod 8 == 1 or 7. + * (3/p) == 1 if p mod 12 == 1 or 11. + * (5/p) == 1 if p mod 5 == 1 or 4. + * See for instance: https://en.wikipedia.org/wiki/Legendre_symbol * - * Thanks to Phil Karn for the pointers about the - * special generators and for answering some of my questions. - * - * I've implemented the second simple method :-). - * Since DH should be using a safe prime (both p and q are prime), - * this generator function can take a very very long time to run. - */ -/* - * Actually there is no reason to insist that 'generator' be a generator. - * It's just as OK (and in some sense better) to use a generator of the - * order-q subgroup. + * Since all safe primes > 7 must satisfy p mod 12 == 11 + * and all safe primes > 11 must satisfy p mod 5 != 1 + * we can further improve the condition for g = 2, 3 and 5: + * for 2, p mod 24 == 23 + * for 3, p mod 12 == 11 + * for 5, p mod 60 == 59 */ static int dh_builtin_genparams(DH *ret, int prime_len, int generator, BN_GENCB *cb) @@ -84,17 +83,14 @@ static int dh_builtin_genparams(DH *ret, int prime_len, int generator, if (generator == DH_GENERATOR_2) { if (!BN_set_word(t1, 24)) goto err; - if (!BN_set_word(t2, 11)) + if (!BN_set_word(t2, 23)) goto err; g = 2; } else if (generator == DH_GENERATOR_5) { - if (!BN_set_word(t1, 10)) + if (!BN_set_word(t1, 60)) goto err; - if (!BN_set_word(t2, 3)) + if (!BN_set_word(t2, 59)) goto err; - /* - * BN_set_word(t3,7); just have to miss out on these ones :-( - */ g = 5; } else { /* @@ -102,9 +98,9 @@ static int dh_builtin_genparams(DH *ret, int prime_len, int generator, * not: since we are using safe primes, it will generate either an * order-q or an order-2q group, which both is OK */ - if (!BN_set_word(t1, 2)) + if (!BN_set_word(t1, 12)) goto err; - if (!BN_set_word(t2, 1)) + if (!BN_set_word(t2, 11)) goto err; g = generator; } |