rsa_gen.c revision 314125
1104828Stjr/* crypto/rsa/rsa_gen.c */ 2268571Spfg/* Copyright (C) 1995-1998 Eric Young (eay@cryptsoft.com) 3128004Stjr * All rights reserved. 4104828Stjr * 5104828Stjr * This package is an SSL implementation written 6227753Stheraven * by Eric Young (eay@cryptsoft.com). 7227753Stheraven * The implementation was written so as to conform with Netscapes SSL. 8227753Stheraven * 9227753Stheraven * This library is free for commercial and non-commercial use as long as 10227753Stheraven * the following conditions are aheared to. The following conditions 11104828Stjr * apply to all code found in this distribution, be it the RC4, RSA, 12104828Stjr * lhash, DES, etc., code; not just the SSL code. The SSL documentation 13104828Stjr * included with this distribution is covered by the same copyright terms 14104828Stjr * except that the holder is Tim Hudson (tjh@cryptsoft.com). 15104828Stjr * 16104828Stjr * Copyright remains Eric Young's, and as such any Copyright notices in 17104828Stjr * the code are not to be removed. 18104828Stjr * If this package is used in a product, Eric Young should be given attribution 19104828Stjr * as the author of the parts of the library used. 20104828Stjr * This can be in the form of a textual message at program startup or 21104828Stjr * in documentation (online or textual) provided with the package. 22104828Stjr * 23104828Stjr * Redistribution and use in source and binary forms, with or without 24104828Stjr * modification, are permitted provided that the following conditions 25104828Stjr * are met: 26104828Stjr * 1. Redistributions of source code must retain the copyright 27104828Stjr * notice, this list of conditions and the following disclaimer. 28104828Stjr * 2. Redistributions in binary form must reproduce the above copyright 29104828Stjr * notice, this list of conditions and the following disclaimer in the 30104828Stjr * documentation and/or other materials provided with the distribution. 31104828Stjr * 3. All advertising materials mentioning features or use of this software 32104828Stjr * must display the following acknowledgement: 33128004Stjr * "This product includes cryptographic software written by 34104828Stjr * Eric Young (eay@cryptsoft.com)" 35104828Stjr * The word 'cryptographic' can be left out if the rouines from the library 36121893Stjr * being used are not cryptographic related :-). 37132687Stjr * 4. If you include any Windows specific code (or a derivative thereof) from 38121893Stjr * the apps directory (application code) you must include an acknowledgement: 39104828Stjr * "This product includes software written by Tim Hudson (tjh@cryptsoft.com)" 40128004Stjr * 41121893Stjr * THIS SOFTWARE IS PROVIDED BY ERIC YOUNG ``AS IS'' AND 42129153Stjr * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 43104828Stjr * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 44172619Sache * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE 45172619Sache * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 46142654Sphantom * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 47142654Sphantom * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 48142654Sphantom * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 49142654Sphantom * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 50142654Sphantom * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 51142654Sphantom * SUCH DAMAGE. 52142654Sphantom * 53142654Sphantom * The licence and distribution terms for any publically available version or 54142654Sphantom * derivative of this code cannot be changed. i.e. this code cannot simply be 55142654Sphantom * copied and put under another distribution licence 56121893Stjr * [including the GNU Public Licence.] 57128004Stjr */ 58129336Stjr 59129336Stjr/* 60129336Stjr * NB: these functions have been "upgraded", the deprecated versions (which 61128004Stjr * are compatibility wrappers using these functions) are in rsa_depr.c. - 62128004Stjr * Geoff 63104828Stjr */ 64227753Stheraven 65104828Stjr#include <stdio.h> 66104828Stjr#include <time.h> 67227753Stheraven#include "cryptlib.h" 68227753Stheraven#include <openssl/bn.h> 69227753Stheraven#include <openssl/rsa.h> 70227753Stheraven#ifdef OPENSSL_FIPS 71227753Stheraven# include <openssl/fips.h> 72227753Stheravenextern int FIPS_rsa_x931_generate_key_ex(RSA *rsa, int bits, BIGNUM *e, 73227753Stheraven BN_GENCB *cb); 74172661Sache#endif 75172661Sache 76172661Sachestatic int rsa_builtin_keygen(RSA *rsa, int bits, BIGNUM *e_value, 77172661Sache BN_GENCB *cb); 78172661Sache 79227753Stheraven/* 80104828Stjr * NB: this wrapper would normally be placed in rsa_lib.c and the static 81104828Stjr * implementation would probably be in rsa_eay.c. Nonetheless, is kept here 82104828Stjr * so that we don't introduce a new linker dependency. Eg. any application 83104828Stjr * that wasn't previously linking object code related to key-generation won't 84142654Sphantom * have to now just because key-generation is part of RSA_METHOD. 85128004Stjr */ 86128004Stjrint RSA_generate_key_ex(RSA *rsa, int bits, BIGNUM *e_value, BN_GENCB *cb) 87128004Stjr{ 88129336Stjr#ifdef OPENSSL_FIPS 89128004Stjr if (FIPS_mode() && !(rsa->meth->flags & RSA_FLAG_FIPS_METHOD) 90128004Stjr && !(rsa->flags & RSA_FLAG_NON_FIPS_ALLOW)) { 91142654Sphantom RSAerr(RSA_F_RSA_GENERATE_KEY_EX, RSA_R_NON_FIPS_RSA_METHOD); 92121893Stjr return 0; 93128004Stjr } 94104828Stjr#endif 95128004Stjr if (rsa->meth->rsa_keygen) 96129336Stjr return rsa->meth->rsa_keygen(rsa, bits, e_value, cb); 97121893Stjr#ifdef OPENSSL_FIPS 98104828Stjr if (FIPS_mode()) 99128004Stjr return FIPS_rsa_x931_generate_key_ex(rsa, bits, e_value, cb); 100128004Stjr#endif 101129336Stjr return rsa_builtin_keygen(rsa, bits, e_value, cb); 102128155Stjr} 103128155Stjr 104128155Stjrstatic int rsa_builtin_keygen(RSA *rsa, int bits, BIGNUM *e_value, 105128155Stjr BN_GENCB *cb) 106128004Stjr{ 107128004Stjr BIGNUM *r0 = NULL, *r1 = NULL, *r2 = NULL, *r3 = NULL, *tmp; 108128004Stjr BIGNUM local_r0, local_d, local_p; 109128004Stjr BIGNUM *pr0, *d, *p; 110128004Stjr int bitsp, bitsq, ok = -1, n = 0; 111128004Stjr BN_CTX *ctx = NULL; 112121893Stjr 113121893Stjr ctx = BN_CTX_new(); 114121893Stjr if (ctx == NULL) 115104828Stjr goto err; 116129336Stjr BN_CTX_start(ctx); 117104828Stjr r0 = BN_CTX_get(ctx); 118129336Stjr r1 = BN_CTX_get(ctx); 119129336Stjr r2 = BN_CTX_get(ctx); 120129336Stjr r3 = BN_CTX_get(ctx); 121129336Stjr if (r3 == NULL) 122129336Stjr goto err; 123129336Stjr 124129336Stjr bitsp = (bits + 1) / 2; 125129336Stjr bitsq = bits - bitsp; 126129336Stjr 127129336Stjr /* We need the RSA components non-NULL */ 128104828Stjr if (!rsa->n && ((rsa->n = BN_new()) == NULL)) 129129336Stjr goto err; 130129336Stjr if (!rsa->d && ((rsa->d = BN_new()) == NULL)) 131268571Spfg goto err; 132268571Spfg if (!rsa->e && ((rsa->e = BN_new()) == NULL)) 133268571Spfg goto err; 134268571Spfg if (!rsa->p && ((rsa->p = BN_new()) == NULL)) 135268571Spfg goto err; 136268571Spfg if (!rsa->q && ((rsa->q = BN_new()) == NULL)) 137129336Stjr goto err; 138129336Stjr if (!rsa->dmp1 && ((rsa->dmp1 = BN_new()) == NULL)) 139129336Stjr goto err; 140129336Stjr if (!rsa->dmq1 && ((rsa->dmq1 = BN_new()) == NULL)) 141129336Stjr goto err; 142129336Stjr if (!rsa->iqmp && ((rsa->iqmp = BN_new()) == NULL)) 143129336Stjr goto err; 144129336Stjr 145129336Stjr if (BN_copy(rsa->e, e_value) == NULL) 146129336Stjr goto err; 147129336Stjr 148129336Stjr /* generate p and q */ 149129336Stjr for (;;) { 150129336Stjr if (!BN_generate_prime_ex(rsa->p, bitsp, 0, NULL, NULL, cb)) 151129336Stjr goto err; 152129336Stjr if (!BN_sub(r2, rsa->p, BN_value_one())) 153129336Stjr goto err; 154129336Stjr if (!BN_gcd(r1, r2, rsa->e, ctx)) 155129336Stjr goto err; 156129336Stjr if (BN_is_one(r1)) 157129336Stjr break; 158104828Stjr if (!BN_GENCB_call(cb, 2, n++)) 159104828Stjr goto err; 160104828Stjr } 161104828Stjr if (!BN_GENCB_call(cb, 3, 0)) 162104828Stjr goto err; 163104828Stjr for (;;) { 164129336Stjr /* 165129336Stjr * When generating ridiculously small keys, we can get stuck 166129336Stjr * continually regenerating the same prime values. Check for this and 167129336Stjr * bail if it happens 3 times. 168129336Stjr */ 169121893Stjr unsigned int degenerate = 0; 170104828Stjr do { 171104828Stjr if (!BN_generate_prime_ex(rsa->q, bitsq, 0, NULL, NULL, cb)) 172104828Stjr goto err; 173104828Stjr } while ((BN_cmp(rsa->p, rsa->q) == 0) && (++degenerate < 3)); 174121893Stjr if (degenerate == 3) { 175121893Stjr ok = 0; /* we set our own err */ 176104828Stjr RSAerr(RSA_F_RSA_BUILTIN_KEYGEN, RSA_R_KEY_SIZE_TOO_SMALL); 177104828Stjr goto err; 178121893Stjr } 179104828Stjr if (!BN_sub(r2, rsa->q, BN_value_one())) 180129336Stjr goto err; 181129336Stjr if (!BN_gcd(r1, r2, rsa->e, ctx)) 182129336Stjr goto err; 183129336Stjr if (BN_is_one(r1)) 184129336Stjr break; 185129336Stjr if (!BN_GENCB_call(cb, 2, n++)) 186129336Stjr goto err; 187121893Stjr } 188104828Stjr if (!BN_GENCB_call(cb, 3, 1)) 189104828Stjr goto err; 190104828Stjr if (BN_cmp(rsa->p, rsa->q) < 0) { 191121893Stjr tmp = rsa->p; 192121893Stjr rsa->p = rsa->q; 193121893Stjr rsa->q = tmp; 194287393Sbapt } 195265361Spfg 196265361Spfg /* calculate n */ 197265361Spfg if (!BN_mul(rsa->n, rsa->p, rsa->q, ctx)) 198265361Spfg goto err; 199265361Spfg 200265361Spfg /* calculate d */ 201121893Stjr if (!BN_sub(r1, rsa->p, BN_value_one())) 202121893Stjr goto err; /* p-1 */ 203129336Stjr if (!BN_sub(r2, rsa->q, BN_value_one())) 204129336Stjr goto err; /* q-1 */ 205104828Stjr if (!BN_mul(r0, r1, r2, ctx)) 206104828Stjr goto err; /* (p-1)(q-1) */ 207142654Sphantom if (!(rsa->flags & RSA_FLAG_NO_CONSTTIME)) { 208132687Stjr pr0 = &local_r0; 209132687Stjr BN_with_flags(pr0, r0, BN_FLG_CONSTTIME); 210132687Stjr } else 211132687Stjr pr0 = r0; 212132687Stjr if (!BN_mod_inverse(rsa->d, rsa->e, pr0, ctx)) 213132687Stjr goto err; /* d */ 214132687Stjr 215132687Stjr /* set up d for correct BN_FLG_CONSTTIME flag */ 216132687Stjr if (!(rsa->flags & RSA_FLAG_NO_CONSTTIME)) { 217132687Stjr d = &local_d; 218132687Stjr BN_with_flags(d, rsa->d, BN_FLG_CONSTTIME); 219132687Stjr } else 220132687Stjr d = rsa->d; 221132687Stjr 222132687Stjr /* calculate d mod (p-1) */ 223132687Stjr if (!BN_mod(rsa->dmp1, d, r1, ctx)) 224132687Stjr goto err; 225132687Stjr 226132687Stjr /* calculate d mod (q-1) */ 227132687Stjr if (!BN_mod(rsa->dmq1, d, r2, ctx)) 228132687Stjr goto err; 229132687Stjr 230132687Stjr /* calculate inverse of q mod p */ 231132687Stjr if (!(rsa->flags & RSA_FLAG_NO_CONSTTIME)) { 232132687Stjr p = &local_p; 233132687Stjr BN_with_flags(p, rsa->p, BN_FLG_CONSTTIME); 234132687Stjr } else 235132687Stjr p = rsa->p; 236132687Stjr if (!BN_mod_inverse(rsa->iqmp, rsa->q, p, ctx)) 237132687Stjr goto err; 238132687Stjr 239132687Stjr ok = 1; 240132687Stjr err: 241132687Stjr if (ok == -1) { 242132687Stjr RSAerr(RSA_F_RSA_BUILTIN_KEYGEN, ERR_LIB_BN); 243132687Stjr ok = 0; 244132687Stjr } 245132687Stjr if (ctx != NULL) { 246132687Stjr BN_CTX_end(ctx); 247132687Stjr BN_CTX_free(ctx); 248132687Stjr } 249132687Stjr 250132687Stjr return ok; 251132687Stjr} 252132687Stjr