1193645Ssimon/* crypto/rsa/rsa_gen.c */ 2193645Ssimon/* Copyright (C) 1995-1998 Eric Young (eay@cryptsoft.com) 3193645Ssimon * All rights reserved. 4193645Ssimon * 5193645Ssimon * This package is an SSL implementation written 6193645Ssimon * by Eric Young (eay@cryptsoft.com). 7193645Ssimon * The implementation was written so as to conform with Netscapes SSL. 8296465Sdelphij * 9193645Ssimon * This library is free for commercial and non-commercial use as long as 10193645Ssimon * the following conditions are aheared to. The following conditions 11193645Ssimon * apply to all code found in this distribution, be it the RC4, RSA, 12193645Ssimon * lhash, DES, etc., code; not just the SSL code. The SSL documentation 13193645Ssimon * included with this distribution is covered by the same copyright terms 14193645Ssimon * except that the holder is Tim Hudson (tjh@cryptsoft.com). 15296465Sdelphij * 16193645Ssimon * Copyright remains Eric Young's, and as such any Copyright notices in 17193645Ssimon * the code are not to be removed. 18193645Ssimon * If this package is used in a product, Eric Young should be given attribution 19193645Ssimon * as the author of the parts of the library used. 20193645Ssimon * This can be in the form of a textual message at program startup or 21193645Ssimon * in documentation (online or textual) provided with the package. 22296465Sdelphij * 23193645Ssimon * Redistribution and use in source and binary forms, with or without 24193645Ssimon * modification, are permitted provided that the following conditions 25193645Ssimon * are met: 26193645Ssimon * 1. Redistributions of source code must retain the copyright 27193645Ssimon * notice, this list of conditions and the following disclaimer. 28193645Ssimon * 2. Redistributions in binary form must reproduce the above copyright 29193645Ssimon * notice, this list of conditions and the following disclaimer in the 30193645Ssimon * documentation and/or other materials provided with the distribution. 31193645Ssimon * 3. All advertising materials mentioning features or use of this software 32193645Ssimon * must display the following acknowledgement: 33193645Ssimon * "This product includes cryptographic software written by 34193645Ssimon * Eric Young (eay@cryptsoft.com)" 35193645Ssimon * The word 'cryptographic' can be left out if the rouines from the library 36193645Ssimon * being used are not cryptographic related :-). 37296465Sdelphij * 4. If you include any Windows specific code (or a derivative thereof) from 38193645Ssimon * the apps directory (application code) you must include an acknowledgement: 39193645Ssimon * "This product includes software written by Tim Hudson (tjh@cryptsoft.com)" 40296465Sdelphij * 41193645Ssimon * THIS SOFTWARE IS PROVIDED BY ERIC YOUNG ``AS IS'' AND 42193645Ssimon * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 43193645Ssimon * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 44193645Ssimon * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE 45193645Ssimon * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 46193645Ssimon * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 47193645Ssimon * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 48193645Ssimon * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 49193645Ssimon * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 50193645Ssimon * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 51193645Ssimon * SUCH DAMAGE. 52296465Sdelphij * 53193645Ssimon * The licence and distribution terms for any publically available version or 54193645Ssimon * derivative of this code cannot be changed. i.e. this code cannot simply be 55193645Ssimon * copied and put under another distribution licence 56193645Ssimon * [including the GNU Public Licence.] 57193645Ssimon */ 58193645Ssimon 59193645Ssimon#include <stdio.h> 60193645Ssimon#include <string.h> 61193645Ssimon#include <time.h> 62193645Ssimon#include <openssl/err.h> 63193645Ssimon#include <openssl/bn.h> 64193645Ssimon#include <openssl/rsa.h> 65193645Ssimon 66193645Ssimon#ifndef OPENSSL_FIPS 67193645Ssimon 68193645Ssimon/* X9.31 RSA key derivation and generation */ 69193645Ssimon 70296465Sdelphijint RSA_X931_derive_ex(RSA *rsa, BIGNUM *p1, BIGNUM *p2, BIGNUM *q1, 71296465Sdelphij BIGNUM *q2, const BIGNUM *Xp1, const BIGNUM *Xp2, 72296465Sdelphij const BIGNUM *Xp, const BIGNUM *Xq1, const BIGNUM *Xq2, 73296465Sdelphij const BIGNUM *Xq, const BIGNUM *e, BN_GENCB *cb) 74296465Sdelphij{ 75296465Sdelphij BIGNUM *r0 = NULL, *r1 = NULL, *r2 = NULL, *r3 = NULL; 76296465Sdelphij BN_CTX *ctx = NULL, *ctx2 = NULL; 77193645Ssimon 78296465Sdelphij if (!rsa) 79296465Sdelphij goto err; 80193645Ssimon 81296465Sdelphij ctx = BN_CTX_new(); 82296465Sdelphij if (!ctx) 83296465Sdelphij goto err; 84296465Sdelphij BN_CTX_start(ctx); 85193645Ssimon 86296465Sdelphij r0 = BN_CTX_get(ctx); 87296465Sdelphij r1 = BN_CTX_get(ctx); 88296465Sdelphij r2 = BN_CTX_get(ctx); 89296465Sdelphij r3 = BN_CTX_get(ctx); 90193645Ssimon 91296465Sdelphij if (r3 == NULL) 92296465Sdelphij goto err; 93296465Sdelphij if (!rsa->e) { 94296465Sdelphij rsa->e = BN_dup(e); 95296465Sdelphij if (!rsa->e) 96296465Sdelphij goto err; 97296465Sdelphij } else 98296465Sdelphij e = rsa->e; 99193645Ssimon 100296465Sdelphij /* 101296465Sdelphij * If not all parameters present only calculate what we can. This allows 102296465Sdelphij * test programs to output selective parameters. 103296465Sdelphij */ 104193645Ssimon 105296465Sdelphij if (Xp && !rsa->p) { 106296465Sdelphij rsa->p = BN_new(); 107296465Sdelphij if (!rsa->p) 108296465Sdelphij goto err; 109193645Ssimon 110296465Sdelphij if (!BN_X931_derive_prime_ex(rsa->p, p1, p2, 111296465Sdelphij Xp, Xp1, Xp2, e, ctx, cb)) 112296465Sdelphij goto err; 113296465Sdelphij } 114193645Ssimon 115296465Sdelphij if (Xq && !rsa->q) { 116296465Sdelphij rsa->q = BN_new(); 117296465Sdelphij if (!rsa->q) 118296465Sdelphij goto err; 119296465Sdelphij if (!BN_X931_derive_prime_ex(rsa->q, q1, q2, 120296465Sdelphij Xq, Xq1, Xq2, e, ctx, cb)) 121296465Sdelphij goto err; 122296465Sdelphij } 123193645Ssimon 124296465Sdelphij if (!rsa->p || !rsa->q) { 125296465Sdelphij BN_CTX_end(ctx); 126296465Sdelphij BN_CTX_free(ctx); 127296465Sdelphij return 2; 128296465Sdelphij } 129193645Ssimon 130296465Sdelphij /* 131296465Sdelphij * Since both primes are set we can now calculate all remaining 132296465Sdelphij * components. 133296465Sdelphij */ 134193645Ssimon 135296465Sdelphij /* calculate n */ 136296465Sdelphij rsa->n = BN_new(); 137296465Sdelphij if (rsa->n == NULL) 138296465Sdelphij goto err; 139296465Sdelphij if (!BN_mul(rsa->n, rsa->p, rsa->q, ctx)) 140296465Sdelphij goto err; 141193645Ssimon 142296465Sdelphij /* calculate d */ 143296465Sdelphij if (!BN_sub(r1, rsa->p, BN_value_one())) 144296465Sdelphij goto err; /* p-1 */ 145296465Sdelphij if (!BN_sub(r2, rsa->q, BN_value_one())) 146296465Sdelphij goto err; /* q-1 */ 147296465Sdelphij if (!BN_mul(r0, r1, r2, ctx)) 148296465Sdelphij goto err; /* (p-1)(q-1) */ 149193645Ssimon 150296465Sdelphij if (!BN_gcd(r3, r1, r2, ctx)) 151296465Sdelphij goto err; 152193645Ssimon 153296465Sdelphij if (!BN_div(r0, NULL, r0, r3, ctx)) 154296465Sdelphij goto err; /* LCM((p-1)(q-1)) */ 155193645Ssimon 156296465Sdelphij ctx2 = BN_CTX_new(); 157296465Sdelphij if (!ctx2) 158296465Sdelphij goto err; 159193645Ssimon 160296465Sdelphij rsa->d = BN_mod_inverse(NULL, rsa->e, r0, ctx2); /* d */ 161296465Sdelphij if (rsa->d == NULL) 162296465Sdelphij goto err; 163193645Ssimon 164296465Sdelphij /* calculate d mod (p-1) */ 165296465Sdelphij rsa->dmp1 = BN_new(); 166296465Sdelphij if (rsa->dmp1 == NULL) 167296465Sdelphij goto err; 168296465Sdelphij if (!BN_mod(rsa->dmp1, rsa->d, r1, ctx)) 169296465Sdelphij goto err; 170193645Ssimon 171296465Sdelphij /* calculate d mod (q-1) */ 172296465Sdelphij rsa->dmq1 = BN_new(); 173296465Sdelphij if (rsa->dmq1 == NULL) 174296465Sdelphij goto err; 175296465Sdelphij if (!BN_mod(rsa->dmq1, rsa->d, r2, ctx)) 176296465Sdelphij goto err; 177193645Ssimon 178296465Sdelphij /* calculate inverse of q mod p */ 179296465Sdelphij rsa->iqmp = BN_mod_inverse(NULL, rsa->q, rsa->p, ctx2); 180193645Ssimon 181296465Sdelphij err: 182296465Sdelphij if (ctx) { 183296465Sdelphij BN_CTX_end(ctx); 184296465Sdelphij BN_CTX_free(ctx); 185296465Sdelphij } 186296465Sdelphij if (ctx2) 187296465Sdelphij BN_CTX_free(ctx2); 188296465Sdelphij /* If this is set all calls successful */ 189296465Sdelphij if (rsa && rsa->iqmp != NULL) 190296465Sdelphij return 1; 191193645Ssimon 192296465Sdelphij return 0; 193193645Ssimon 194296465Sdelphij} 195193645Ssimon 196296465Sdelphijint RSA_X931_generate_key_ex(RSA *rsa, int bits, const BIGNUM *e, 197296465Sdelphij BN_GENCB *cb) 198296465Sdelphij{ 199296465Sdelphij int ok = 0; 200296465Sdelphij BIGNUM *Xp = NULL, *Xq = NULL; 201296465Sdelphij BN_CTX *ctx = NULL; 202193645Ssimon 203296465Sdelphij ctx = BN_CTX_new(); 204296465Sdelphij if (!ctx) 205296465Sdelphij goto error; 206193645Ssimon 207296465Sdelphij BN_CTX_start(ctx); 208296465Sdelphij Xp = BN_CTX_get(ctx); 209296465Sdelphij Xq = BN_CTX_get(ctx); 210296465Sdelphij if (!BN_X931_generate_Xpq(Xp, Xq, bits, ctx)) 211296465Sdelphij goto error; 212193645Ssimon 213296465Sdelphij rsa->p = BN_new(); 214296465Sdelphij rsa->q = BN_new(); 215296465Sdelphij if (!rsa->p || !rsa->q) 216296465Sdelphij goto error; 217193645Ssimon 218296465Sdelphij /* Generate two primes from Xp, Xq */ 219193645Ssimon 220296465Sdelphij if (!BN_X931_generate_prime_ex(rsa->p, NULL, NULL, NULL, NULL, Xp, 221296465Sdelphij e, ctx, cb)) 222296465Sdelphij goto error; 223193645Ssimon 224296465Sdelphij if (!BN_X931_generate_prime_ex(rsa->q, NULL, NULL, NULL, NULL, Xq, 225296465Sdelphij e, ctx, cb)) 226296465Sdelphij goto error; 227193645Ssimon 228296465Sdelphij /* 229296465Sdelphij * Since rsa->p and rsa->q are valid this call will just derive remaining 230296465Sdelphij * RSA components. 231296465Sdelphij */ 232193645Ssimon 233296465Sdelphij if (!RSA_X931_derive_ex(rsa, NULL, NULL, NULL, NULL, 234296465Sdelphij NULL, NULL, NULL, NULL, NULL, NULL, e, cb)) 235296465Sdelphij goto error; 236193645Ssimon 237296465Sdelphij ok = 1; 238193645Ssimon 239296465Sdelphij error: 240296465Sdelphij if (ctx) { 241296465Sdelphij BN_CTX_end(ctx); 242296465Sdelphij BN_CTX_free(ctx); 243296465Sdelphij } 244193645Ssimon 245296465Sdelphij if (ok) 246296465Sdelphij return 1; 247193645Ssimon 248296465Sdelphij return 0; 249193645Ssimon 250296465Sdelphij} 251296465Sdelphij 252193645Ssimon#endif 253