b25d76e55cc36fa2b9ac3babfaa03604168b7eb0
[openssl.git] / crypto / rsa / rsa_gen.c
1 /*
2  * Copyright 1995-2016 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 deprecated versions (which
12  * are compatibility wrappers using these functions) are in rsa_depr.c. -
13  * Geoff
14  */
15
16 #include <stdio.h>
17 #include <time.h>
18 #include "internal/cryptlib.h"
19 #include <openssl/bn.h>
20 #include "rsa_locl.h"
21
22 static int rsa_builtin_keygen(RSA *rsa, int bits, BIGNUM *e_value,
23                               BN_GENCB *cb);
24
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  */
32 int RSA_generate_key_ex(RSA *rsa, int bits, BIGNUM *e_value, BN_GENCB *cb)
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;
43     int bitsp, bitsq, ok = -1, n = 0;
44     BN_CTX *ctx = NULL;
45
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;
63     if (!rsa->d && ((rsa->d = BN_secure_new()) == NULL))
64         goto err;
65     if (!rsa->e && ((rsa->e = BN_new()) == NULL))
66         goto err;
67     if (!rsa->p && ((rsa->p = BN_secure_new()) == NULL))
68         goto err;
69     if (!rsa->q && ((rsa->q = BN_secure_new()) == NULL))
70         goto err;
71     if (!rsa->dmp1 && ((rsa->dmp1 = BN_secure_new()) == NULL))
72         goto err;
73     if (!rsa->dmq1 && ((rsa->dmq1 = BN_secure_new()) == NULL))
74         goto err;
75     if (!rsa->iqmp && ((rsa->iqmp = BN_secure_new()) == NULL))
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) */
139     {
140         BIGNUM *local_r0 = NULL, *pr0;
141         if (!(rsa->flags & RSA_FLAG_NO_CONSTTIME)) {
142             pr0 = local_r0 = BN_new();
143             if (local_r0 == NULL)
144                 goto err;
145             BN_with_flags(pr0, r0, BN_FLG_CONSTTIME);
146         } else {
147             pr0 = r0;
148         }
149         if (!BN_mod_inverse(rsa->d, rsa->e, pr0, ctx)) {
150             BN_free(local_r0);
151             goto err;               /* d */
152         }
153         /* We MUST free local_r0 before any further use of r0 */
154         BN_free(local_r0);
155     }
156
157     {
158         BIGNUM *local_d = NULL, *d;
159         /* set up d for correct BN_FLG_CONSTTIME flag */
160         if (!(rsa->flags & RSA_FLAG_NO_CONSTTIME)) {
161             d = local_d = BN_new();
162             if (local_d == NULL)
163                 goto err;
164             BN_with_flags(d, rsa->d, BN_FLG_CONSTTIME);
165         } else {
166             d = rsa->d;
167         }
168
169         if (   /* calculate d mod (p-1) */
170                !BN_mod(rsa->dmp1, d, r1, ctx)
171                /* calculate d mod (q-1) */
172             || !BN_mod(rsa->dmq1, d, r2, ctx)) {
173             BN_free(local_d);
174             goto err;
175         }
176         /* We MUST free local_d before any further use of rsa->d */
177         BN_free(local_d);
178     }
179
180     {
181         BIGNUM *local_p = NULL, *p;
182
183         /* calculate inverse of q mod p */
184         if (!(rsa->flags & RSA_FLAG_NO_CONSTTIME)) {
185             p = local_p = BN_new();
186             if (local_p == NULL)
187                 goto err;
188             BN_with_flags(p, rsa->p, BN_FLG_CONSTTIME);
189         } else {
190             p = rsa->p;
191         }
192         if (!BN_mod_inverse(rsa->iqmp, rsa->q, p, ctx)) {
193             BN_free(local_p);
194             goto err;
195         }
196         /* We MUST free local_p before any further use of rsa->p */
197         BN_free(local_p);
198     }
199
200     ok = 1;
201  err:
202     if (ok == -1) {
203         RSAerr(RSA_F_RSA_BUILTIN_KEYGEN, ERR_LIB_BN);
204         ok = 0;
205     }
206     if (ctx != NULL)
207         BN_CTX_end(ctx);
208     BN_CTX_free(ctx);
209
210     return ok;
211 }