Custome built dladdr() for AIX.
[openssl.git] / crypto / rsa / rsa_gen.c
1 /*
2  * Copyright 1995-2018 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     unsigned long error = 0;
46
47     /*
48      * When generating ridiculously small keys, we can get stuck
49      * continually regenerating the same prime values.
50      */
51     if (bits < 16) {
52         ok = 0;             /* we set our own err */
53         RSAerr(RSA_F_RSA_BUILTIN_KEYGEN, RSA_R_KEY_SIZE_TOO_SMALL);
54         goto err;
55     }
56
57     ctx = BN_CTX_new();
58     if (ctx == NULL)
59         goto err;
60     BN_CTX_start(ctx);
61     r0 = BN_CTX_get(ctx);
62     r1 = BN_CTX_get(ctx);
63     r2 = BN_CTX_get(ctx);
64     r3 = BN_CTX_get(ctx);
65     if (r3 == NULL)
66         goto err;
67
68     bitsp = (bits + 1) / 2;
69     bitsq = bits - bitsp;
70
71     /* We need the RSA components non-NULL */
72     if (!rsa->n && ((rsa->n = BN_new()) == NULL))
73         goto err;
74     if (!rsa->d && ((rsa->d = BN_secure_new()) == NULL))
75         goto err;
76     if (!rsa->e && ((rsa->e = BN_new()) == NULL))
77         goto err;
78     if (!rsa->p && ((rsa->p = BN_secure_new()) == NULL))
79         goto err;
80     if (!rsa->q && ((rsa->q = BN_secure_new()) == NULL))
81         goto err;
82     if (!rsa->dmp1 && ((rsa->dmp1 = BN_secure_new()) == NULL))
83         goto err;
84     if (!rsa->dmq1 && ((rsa->dmq1 = BN_secure_new()) == NULL))
85         goto err;
86     if (!rsa->iqmp && ((rsa->iqmp = BN_secure_new()) == NULL))
87         goto err;
88
89     if (BN_copy(rsa->e, e_value) == NULL)
90         goto err;
91
92     BN_set_flags(r2, BN_FLG_CONSTTIME);
93     /* generate p and q */
94     for (;;) {
95         if (!BN_generate_prime_ex(rsa->p, bitsp, 0, NULL, NULL, cb))
96             goto err;
97         if (!BN_sub(r2, rsa->p, BN_value_one()))
98             goto err;
99         ERR_set_mark();
100         if (BN_mod_inverse(r1, r2, rsa->e, ctx) != NULL) {
101             /* GCD == 1 since inverse exists */
102             break;
103         }
104         error = ERR_peek_last_error();
105         if (ERR_GET_LIB(error) == ERR_LIB_BN
106             && ERR_GET_REASON(error) == BN_R_NO_INVERSE) {
107             /* GCD != 1 */
108             ERR_pop_to_mark();
109         } else {
110             goto err;
111         }
112         if (!BN_GENCB_call(cb, 2, n++))
113             goto err;
114     }
115     if (!BN_GENCB_call(cb, 3, 0))
116         goto err;
117     for (;;) {
118         do {
119             if (!BN_generate_prime_ex(rsa->q, bitsq, 0, NULL, NULL, cb))
120                 goto err;
121         } while (BN_cmp(rsa->p, rsa->q) == 0);
122         if (!BN_sub(r2, rsa->q, BN_value_one()))
123             goto err;
124         ERR_set_mark();
125         if (BN_mod_inverse(r1, r2, rsa->e, ctx) != NULL) {
126             /* GCD == 1 since inverse exists */
127             break;
128         }
129         error = ERR_peek_last_error();
130         if (ERR_GET_LIB(error) == ERR_LIB_BN
131             && ERR_GET_REASON(error) == BN_R_NO_INVERSE) {
132             /* GCD != 1 */
133             ERR_pop_to_mark();
134         } else {
135             goto err;
136         }
137         if (!BN_GENCB_call(cb, 2, n++))
138             goto err;
139     }
140     if (!BN_GENCB_call(cb, 3, 1))
141         goto err;
142     if (BN_cmp(rsa->p, rsa->q) < 0) {
143         tmp = rsa->p;
144         rsa->p = rsa->q;
145         rsa->q = tmp;
146     }
147
148     /* calculate n */
149     if (!BN_mul(rsa->n, rsa->p, rsa->q, ctx))
150         goto err;
151
152     /* calculate d */
153     if (!BN_sub(r1, rsa->p, BN_value_one()))
154         goto err;               /* p-1 */
155     if (!BN_sub(r2, rsa->q, BN_value_one()))
156         goto err;               /* q-1 */
157     if (!BN_mul(r0, r1, r2, ctx))
158         goto err;               /* (p-1)(q-1) */
159     {
160         BIGNUM *pr0 = BN_new();
161
162         if (pr0 == NULL)
163             goto err;
164         BN_with_flags(pr0, r0, BN_FLG_CONSTTIME);
165         if (!BN_mod_inverse(rsa->d, rsa->e, pr0, ctx)) {
166             BN_free(pr0);
167             goto err;               /* d */
168         }
169         /* We MUST free pr0 before any further use of r0 */
170         BN_free(pr0);
171     }
172
173     {
174         BIGNUM *d = BN_new();
175
176         if (d == NULL)
177             goto err;
178         BN_with_flags(d, rsa->d, BN_FLG_CONSTTIME);
179
180         if (   /* calculate d mod (p-1) */
181                !BN_mod(rsa->dmp1, d, r1, ctx)
182                /* calculate d mod (q-1) */
183             || !BN_mod(rsa->dmq1, d, r2, ctx)) {
184             BN_free(d);
185             goto err;
186         }
187         /* We MUST free d before any further use of rsa->d */
188         BN_free(d);
189     }
190
191     {
192         BIGNUM *p = BN_new();
193
194         if (p == NULL)
195             goto err;
196         BN_with_flags(p, rsa->p, BN_FLG_CONSTTIME);
197
198         /* calculate inverse of q mod p */
199         if (!BN_mod_inverse(rsa->iqmp, rsa->q, p, ctx)) {
200             BN_free(p);
201             goto err;
202         }
203         /* We MUST free p before any further use of rsa->p */
204         BN_free(p);
205     }
206
207     ok = 1;
208  err:
209     if (ok == -1) {
210         RSAerr(RSA_F_RSA_BUILTIN_KEYGEN, ERR_LIB_BN);
211         ok = 0;
212     }
213     if (ctx != NULL)
214         BN_CTX_end(ctx);
215     BN_CTX_free(ctx);
216
217     return ok;
218 }