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(rsa->p, BN_FLG_CONSTTIME); 93 BN_set_flags(rsa->q, BN_FLG_CONSTTIME); 94 BN_set_flags(r2, BN_FLG_CONSTTIME); 95 /* generate p and q */ 96 for (;;) { 97 if (!BN_generate_prime_ex(rsa->p, bitsp, 0, NULL, NULL, cb)) 98 goto err; 99 if (!BN_sub(r2, rsa->p, BN_value_one())) 100 goto err; 101 ERR_set_mark(); 102 if (BN_mod_inverse(r1, r2, rsa->e, ctx) != NULL) { 103 /* GCD == 1 since inverse exists */ 104 break; 105 } 106 error = ERR_peek_last_error(); 107 if (ERR_GET_LIB(error) == ERR_LIB_BN 108 && ERR_GET_REASON(error) == BN_R_NO_INVERSE) { 109 /* GCD != 1 */ 110 ERR_pop_to_mark(); 111 } else { 112 goto err; 113 } 114 if (!BN_GENCB_call(cb, 2, n++)) 115 goto err; 116 } 117 if (!BN_GENCB_call(cb, 3, 0)) 118 goto err; 119 for (;;) { 120 do { 121 if (!BN_generate_prime_ex(rsa->q, bitsq, 0, NULL, NULL, cb)) 122 goto err; 123 } while (BN_cmp(rsa->p, rsa->q) == 0); 124 if (!BN_sub(r2, rsa->q, BN_value_one())) 125 goto err; 126 ERR_set_mark(); 127 if (BN_mod_inverse(r1, r2, rsa->e, ctx) != NULL) { 128 /* GCD == 1 since inverse exists */ 129 break; 130 } 131 error = ERR_peek_last_error(); 132 if (ERR_GET_LIB(error) == ERR_LIB_BN 133 && ERR_GET_REASON(error) == BN_R_NO_INVERSE) { 134 /* GCD != 1 */ 135 ERR_pop_to_mark(); 136 } else { 137 goto err; 138 } 139 if (!BN_GENCB_call(cb, 2, n++)) 140 goto err; 141 } 142 if (!BN_GENCB_call(cb, 3, 1)) 143 goto err; 144 if (BN_cmp(rsa->p, rsa->q) < 0) { 145 tmp = rsa->p; 146 rsa->p = rsa->q; 147 rsa->q = tmp; 148 } 149 150 /* calculate n */ 151 if (!BN_mul(rsa->n, rsa->p, rsa->q, ctx)) 152 goto err; 153 154 /* calculate d */ 155 if (!BN_sub(r1, rsa->p, BN_value_one())) 156 goto err; /* p-1 */ 157 if (!BN_sub(r2, rsa->q, BN_value_one())) 158 goto err; /* q-1 */ 159 if (!BN_mul(r0, r1, r2, ctx)) 160 goto err; /* (p-1)(q-1) */ 161 { 162 BIGNUM *pr0 = BN_new(); 163 164 if (pr0 == NULL) 165 goto err; 166 BN_with_flags(pr0, r0, BN_FLG_CONSTTIME); 167 if (!BN_mod_inverse(rsa->d, rsa->e, pr0, ctx)) { 168 BN_free(pr0); 169 goto err; /* d */ 170 } 171 /* We MUST free pr0 before any further use of r0 */ 172 BN_free(pr0); 173 } 174 175 { 176 BIGNUM *d = BN_new(); 177 178 if (d == NULL) 179 goto err; 180 BN_with_flags(d, rsa->d, BN_FLG_CONSTTIME); 181 182 if ( /* calculate d mod (p-1) */ 183 !BN_mod(rsa->dmp1, d, r1, ctx) 184 /* calculate d mod (q-1) */ 185 || !BN_mod(rsa->dmq1, d, r2, ctx)) { 186 BN_free(d); 187 goto err; 188 } 189 /* We MUST free d before any further use of rsa->d */ 190 BN_free(d); 191 } 192 193 { 194 BIGNUM *p = BN_new(); 195 196 if (p == NULL) 197 goto err; 198 BN_with_flags(p, rsa->p, BN_FLG_CONSTTIME); 199 200 /* calculate inverse of q mod p */ 201 if (!BN_mod_inverse(rsa->iqmp, rsa->q, p, ctx)) { 202 BN_free(p); 203 goto err; 204 } 205 /* We MUST free p before any further use of rsa->p */ 206 BN_free(p); 207 } 208 209 ok = 1; 210 err: 211 if (ok == -1) { 212 RSAerr(RSA_F_RSA_BUILTIN_KEYGEN, ERR_LIB_BN); 213 ok = 0; 214 } 215 if (ctx != NULL) 216 BN_CTX_end(ctx); 217 BN_CTX_free(ctx); 218 219 return ok; 220 } 221