1 /*
2 * Copyright 1995-2020 The OpenSSL Project Authors. All Rights Reserved.
3 *
4 * Licensed under the OpenSSL license (the "License"). You may not use
5 * this file except in compliance with the License. You can obtain a copy
6 * in the file LICENSE in the source distribution or at
7 * https://www.openssl.org/source/license.html
8 */
9
10 /*
11 * NB: These functions have been upgraded - the previous prototypes are in
12 * dh_depr.c as wrappers to these ones. - Geoff
13 */
14
15 #include <stdio.h>
16 #include "internal/cryptlib.h"
17 #include <openssl/bn.h>
18 #include "dh_local.h"
19
20 static int dh_builtin_genparams(DH *ret, int prime_len, int generator,
21 BN_GENCB *cb);
22
DH_generate_parameters_ex(DH * ret,int prime_len,int generator,BN_GENCB * cb)23 int DH_generate_parameters_ex(DH *ret, int prime_len, int generator,
24 BN_GENCB *cb)
25 {
26 if (ret->meth->generate_params)
27 return ret->meth->generate_params(ret, prime_len, generator, cb);
28 return dh_builtin_genparams(ret, prime_len, generator, cb);
29 }
30
31 /*-
32 * We generate DH parameters as follows
33 * find a prime p which is prime_len bits long,
34 * where q=(p-1)/2 is also prime.
35 * In the following we assume that g is not 0, 1 or p-1, since it
36 * would generate only trivial subgroups.
37 * For this case, g is a generator of the order-q subgroup if
38 * g^q mod p == 1.
39 * Or in terms of the Legendre symbol: (g/p) == 1.
40 *
41 * Having said all that,
42 * there is another special case method for the generators 2, 3 and 5.
43 * Using the quadratic reciprocity law it is possible to solve
44 * (g/p) == 1 for the special values 2, 3, 5:
45 * (2/p) == 1 if p mod 8 == 1 or 7.
46 * (3/p) == 1 if p mod 12 == 1 or 11.
47 * (5/p) == 1 if p mod 5 == 1 or 4.
48 * See for instance: https://en.wikipedia.org/wiki/Legendre_symbol
49 *
50 * Since all safe primes > 7 must satisfy p mod 12 == 11
51 * and all safe primes > 11 must satisfy p mod 5 != 1
52 * we can further improve the condition for g = 2, 3 and 5:
53 * for 2, p mod 24 == 23
54 * for 3, p mod 12 == 11
55 * for 5, p mod 60 == 59
56 *
57 * However for compatibility with previous versions we use:
58 * for 2, p mod 24 == 11
59 * for 5, p mod 60 == 23
60 */
dh_builtin_genparams(DH * ret,int prime_len,int generator,BN_GENCB * cb)61 static int dh_builtin_genparams(DH *ret, int prime_len, int generator,
62 BN_GENCB *cb)
63 {
64 BIGNUM *t1, *t2;
65 int g, ok = -1;
66 BN_CTX *ctx = NULL;
67
68 ctx = BN_CTX_new();
69 if (ctx == NULL)
70 goto err;
71 BN_CTX_start(ctx);
72 t1 = BN_CTX_get(ctx);
73 t2 = BN_CTX_get(ctx);
74 if (t2 == NULL)
75 goto err;
76
77 /* Make sure 'ret' has the necessary elements */
78 if (!ret->p && ((ret->p = BN_new()) == NULL))
79 goto err;
80 if (!ret->g && ((ret->g = BN_new()) == NULL))
81 goto err;
82
83 if (generator <= 1) {
84 DHerr(DH_F_DH_BUILTIN_GENPARAMS, DH_R_BAD_GENERATOR);
85 goto err;
86 }
87 if (generator == DH_GENERATOR_2) {
88 if (!BN_set_word(t1, 24))
89 goto err;
90 if (!BN_set_word(t2, 11))
91 goto err;
92 g = 2;
93 } else if (generator == DH_GENERATOR_5) {
94 if (!BN_set_word(t1, 60))
95 goto err;
96 if (!BN_set_word(t2, 23))
97 goto err;
98 g = 5;
99 } else {
100 /*
101 * in the general case, don't worry if 'generator' is a generator or
102 * not: since we are using safe primes, it will generate either an
103 * order-q or an order-2q group, which both is OK
104 */
105 if (!BN_set_word(t1, 12))
106 goto err;
107 if (!BN_set_word(t2, 11))
108 goto err;
109 g = generator;
110 }
111
112 if (!BN_generate_prime_ex(ret->p, prime_len, 1, t1, t2, cb))
113 goto err;
114 if (!BN_GENCB_call(cb, 3, 0))
115 goto err;
116 if (!BN_set_word(ret->g, g))
117 goto err;
118 ok = 1;
119 err:
120 if (ok == -1) {
121 DHerr(DH_F_DH_BUILTIN_GENPARAMS, ERR_R_BN_LIB);
122 ok = 0;
123 }
124
125 BN_CTX_end(ctx);
126 BN_CTX_free(ctx);
127 return ok;
128 }
129