]>
Commit | Line | Data |
---|---|---|
2039c421 RS |
1 | /* |
2 | * Copyright 1995-2016 The OpenSSL Project Authors. All Rights Reserved. | |
0f113f3e | 3 | * |
2039c421 RS |
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 | |
d02b48c6 RE |
8 | */ |
9 | ||
0f113f3e MC |
10 | /* |
11 | * NB: these functions have been "upgraded", the deprecated versions (which | |
12 | * are compatibility wrappers using these functions) are in rsa_depr.c. - | |
13 | * Geoff | |
e9224c71 GT |
14 | */ |
15 | ||
d02b48c6 RE |
16 | #include <stdio.h> |
17 | #include <time.h> | |
b39fc560 | 18 | #include "internal/cryptlib.h" |
ec577822 | 19 | #include <openssl/bn.h> |
9862e9aa | 20 | #include "rsa_locl.h" |
d02b48c6 | 21 | |
0f113f3e MC |
22 | static int rsa_builtin_keygen(RSA *rsa, int bits, BIGNUM *e_value, |
23 | BN_GENCB *cb); | |
2814c629 | 24 | |
0f113f3e MC |
25 | /* |
26 | * NB: this wrapper would normally be placed in rsa_lib.c and the static | |
27 | * implementation would probably be in rsa_eay.c. Nonetheless, is kept here | |
28 | * so that we don't introduce a new linker dependency. Eg. any application | |
29 | * that wasn't previously linking object code related to key-generation won't | |
30 | * have to now just because key-generation is part of RSA_METHOD. | |
31 | */ | |
bcfea9fb | 32 | int RSA_generate_key_ex(RSA *rsa, int bits, BIGNUM *e_value, BN_GENCB *cb) |
0f113f3e MC |
33 | { |
34 | if (rsa->meth->rsa_keygen) | |
35 | return rsa->meth->rsa_keygen(rsa, bits, e_value, cb); | |
36 | return rsa_builtin_keygen(rsa, bits, e_value, cb); | |
37 | } | |
38 | ||
39 | static int rsa_builtin_keygen(RSA *rsa, int bits, BIGNUM *e_value, | |
40 | BN_GENCB *cb) | |
41 | { | |
42 | BIGNUM *r0 = NULL, *r1 = NULL, *r2 = NULL, *r3 = NULL, *tmp; | |
0f113f3e MC |
43 | int bitsp, bitsq, ok = -1, n = 0; |
44 | BN_CTX *ctx = NULL; | |
45 | ||
0f113f3e MC |
46 | ctx = BN_CTX_new(); |
47 | if (ctx == NULL) | |
48 | goto err; | |
49 | BN_CTX_start(ctx); | |
50 | r0 = BN_CTX_get(ctx); | |
51 | r1 = BN_CTX_get(ctx); | |
52 | r2 = BN_CTX_get(ctx); | |
53 | r3 = BN_CTX_get(ctx); | |
54 | if (r3 == NULL) | |
55 | goto err; | |
56 | ||
57 | bitsp = (bits + 1) / 2; | |
58 | bitsq = bits - bitsp; | |
59 | ||
60 | /* We need the RSA components non-NULL */ | |
61 | if (!rsa->n && ((rsa->n = BN_new()) == NULL)) | |
62 | goto err; | |
74924dcb | 63 | if (!rsa->d && ((rsa->d = BN_secure_new()) == NULL)) |
0f113f3e MC |
64 | goto err; |
65 | if (!rsa->e && ((rsa->e = BN_new()) == NULL)) | |
66 | goto err; | |
74924dcb | 67 | if (!rsa->p && ((rsa->p = BN_secure_new()) == NULL)) |
0f113f3e | 68 | goto err; |
74924dcb | 69 | if (!rsa->q && ((rsa->q = BN_secure_new()) == NULL)) |
0f113f3e | 70 | goto err; |
74924dcb | 71 | if (!rsa->dmp1 && ((rsa->dmp1 = BN_secure_new()) == NULL)) |
0f113f3e | 72 | goto err; |
74924dcb | 73 | if (!rsa->dmq1 && ((rsa->dmq1 = BN_secure_new()) == NULL)) |
0f113f3e | 74 | goto err; |
74924dcb | 75 | if (!rsa->iqmp && ((rsa->iqmp = BN_secure_new()) == NULL)) |
0f113f3e MC |
76 | goto err; |
77 | ||
78 | BN_copy(rsa->e, e_value); | |
79 | ||
80 | /* generate p and q */ | |
81 | for (;;) { | |
82 | if (!BN_generate_prime_ex(rsa->p, bitsp, 0, NULL, NULL, cb)) | |
83 | goto err; | |
84 | if (!BN_sub(r2, rsa->p, BN_value_one())) | |
85 | goto err; | |
86 | if (!BN_gcd(r1, r2, rsa->e, ctx)) | |
87 | goto err; | |
88 | if (BN_is_one(r1)) | |
89 | break; | |
90 | if (!BN_GENCB_call(cb, 2, n++)) | |
91 | goto err; | |
92 | } | |
93 | if (!BN_GENCB_call(cb, 3, 0)) | |
94 | goto err; | |
95 | for (;;) { | |
96 | /* | |
97 | * When generating ridiculously small keys, we can get stuck | |
98 | * continually regenerating the same prime values. Check for this and | |
99 | * bail if it happens 3 times. | |
100 | */ | |
101 | unsigned int degenerate = 0; | |
102 | do { | |
103 | if (!BN_generate_prime_ex(rsa->q, bitsq, 0, NULL, NULL, cb)) | |
104 | goto err; | |
105 | } while ((BN_cmp(rsa->p, rsa->q) == 0) && (++degenerate < 3)); | |
106 | if (degenerate == 3) { | |
107 | ok = 0; /* we set our own err */ | |
108 | RSAerr(RSA_F_RSA_BUILTIN_KEYGEN, RSA_R_KEY_SIZE_TOO_SMALL); | |
109 | goto err; | |
110 | } | |
111 | if (!BN_sub(r2, rsa->q, BN_value_one())) | |
112 | goto err; | |
113 | if (!BN_gcd(r1, r2, rsa->e, ctx)) | |
114 | goto err; | |
115 | if (BN_is_one(r1)) | |
116 | break; | |
117 | if (!BN_GENCB_call(cb, 2, n++)) | |
118 | goto err; | |
119 | } | |
120 | if (!BN_GENCB_call(cb, 3, 1)) | |
121 | goto err; | |
122 | if (BN_cmp(rsa->p, rsa->q) < 0) { | |
123 | tmp = rsa->p; | |
124 | rsa->p = rsa->q; | |
125 | rsa->q = tmp; | |
126 | } | |
127 | ||
128 | /* calculate n */ | |
129 | if (!BN_mul(rsa->n, rsa->p, rsa->q, ctx)) | |
130 | goto err; | |
131 | ||
132 | /* calculate d */ | |
133 | if (!BN_sub(r1, rsa->p, BN_value_one())) | |
134 | goto err; /* p-1 */ | |
135 | if (!BN_sub(r2, rsa->q, BN_value_one())) | |
136 | goto err; /* q-1 */ | |
137 | if (!BN_mul(r0, r1, r2, ctx)) | |
138 | goto err; /* (p-1)(q-1) */ | |
fd7d2520 | 139 | { |
5584f65a MC |
140 | BIGNUM *pr0 = BN_new(); |
141 | ||
142 | if (pr0 == NULL) | |
143 | goto err; | |
144 | BN_with_flags(pr0, r0, BN_FLG_CONSTTIME); | |
fd7d2520 | 145 | if (!BN_mod_inverse(rsa->d, rsa->e, pr0, ctx)) { |
5584f65a | 146 | BN_free(pr0); |
fd7d2520 MC |
147 | goto err; /* d */ |
148 | } | |
5584f65a MC |
149 | /* We MUST free pr0 before any further use of r0 */ |
150 | BN_free(pr0); | |
fd7d2520 | 151 | } |
0f113f3e | 152 | |
fd7d2520 | 153 | { |
5584f65a MC |
154 | BIGNUM *d = BN_new(); |
155 | ||
156 | if (d == NULL) | |
157 | goto err; | |
158 | BN_with_flags(d, rsa->d, BN_FLG_CONSTTIME); | |
0f113f3e | 159 | |
fd7d2520 MC |
160 | if ( /* calculate d mod (p-1) */ |
161 | !BN_mod(rsa->dmp1, d, r1, ctx) | |
162 | /* calculate d mod (q-1) */ | |
163 | || !BN_mod(rsa->dmq1, d, r2, ctx)) { | |
5584f65a | 164 | BN_free(d); |
fd7d2520 MC |
165 | goto err; |
166 | } | |
5584f65a MC |
167 | /* We MUST free d before any further use of rsa->d */ |
168 | BN_free(d); | |
fd7d2520 MC |
169 | } |
170 | ||
171 | { | |
5584f65a MC |
172 | BIGNUM *p = BN_new(); |
173 | ||
174 | if (p == NULL) | |
175 | goto err; | |
176 | BN_with_flags(p, rsa->p, BN_FLG_CONSTTIME); | |
fd7d2520 MC |
177 | |
178 | /* calculate inverse of q mod p */ | |
fd7d2520 | 179 | if (!BN_mod_inverse(rsa->iqmp, rsa->q, p, ctx)) { |
5584f65a | 180 | BN_free(p); |
fd7d2520 MC |
181 | goto err; |
182 | } | |
5584f65a MC |
183 | /* We MUST free p before any further use of rsa->p */ |
184 | BN_free(p); | |
fd7d2520 | 185 | } |
0f113f3e MC |
186 | |
187 | ok = 1; | |
188 | err: | |
0f113f3e MC |
189 | if (ok == -1) { |
190 | RSAerr(RSA_F_RSA_BUILTIN_KEYGEN, ERR_LIB_BN); | |
191 | ok = 0; | |
192 | } | |
23a1d5e9 | 193 | if (ctx != NULL) |
0f113f3e | 194 | BN_CTX_end(ctx); |
23a1d5e9 | 195 | BN_CTX_free(ctx); |
0f113f3e MC |
196 | |
197 | return ok; | |
198 | } |