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     /*
  47      * When generating ridiculously small keys, we can get stuck
  48      * continually regenerating the same prime values.
  49      */
  50     if (bits < 16) {
  51         ok = 0;             /* we set our own err */
  52         RSAerr(RSA_F_RSA_BUILTIN_KEYGEN, RSA_R_KEY_SIZE_TOO_SMALL);
  53         goto err;
  54     }
  55
  56     ctx = BN_CTX_new();
  57     if (ctx == NULL)
  58         goto err;
  59     BN_CTX_start(ctx);
  60     r0 = BN_CTX_get(ctx);
  61     r1 = BN_CTX_get(ctx);
  62     r2 = BN_CTX_get(ctx);
  63     r3 = BN_CTX_get(ctx);
  64     if (r3 == NULL)
  65         goto err;
  66
  67     bitsp = (bits + 1) / 2;
  68     bitsq = bits - bitsp;
  69
  70     /* We need the RSA components non-NULL */
  71     if (!rsa->n && ((rsa->n = BN_new()) == NULL))
  72         goto err;
  73     if (!rsa->d && ((rsa->d = BN_secure_new()) == NULL))
  74         goto err;
  75     if (!rsa->e && ((rsa->e = BN_new()) == NULL))
  76         goto err;
  77     if (!rsa->p && ((rsa->p = BN_secure_new()) == NULL))
  78         goto err;
  79     if (!rsa->q && ((rsa->q = BN_secure_new()) == NULL))
  80         goto err;
  81     if (!rsa->dmp1 && ((rsa->dmp1 = BN_secure_new()) == NULL))
  82         goto err;
  83     if (!rsa->dmq1 && ((rsa->dmq1 = BN_secure_new()) == NULL))
  84         goto err;
  85     if (!rsa->iqmp && ((rsa->iqmp = BN_secure_new()) == NULL))
  86         goto err;
  87
  88     if (BN_copy(rsa->e, e_value) == NULL)
  89         goto err;
  90
  91     /* generate p and q */
  92     for (;;) {
  93         if (!BN_generate_prime_ex(rsa->p, bitsp, 0, NULL, NULL, cb))
  94             goto err;
  95         if (!BN_sub(r2, rsa->p, BN_value_one()))
  96             goto err;
  97         if (!BN_gcd(r1, r2, rsa->e, ctx))
  98             goto err;
  99         if (BN_is_one(r1))
 100             break;
 101         if (!BN_GENCB_call(cb, 2, n++))
 102             goto err;
 103     }
 104     if (!BN_GENCB_call(cb, 3, 0))
 105         goto err;
 106     for (;;) {
 107         do {
 108             if (!BN_generate_prime_ex(rsa->q, bitsq, 0, NULL, NULL, cb))
 109                 goto err;
 110         } while (BN_cmp(rsa->p, rsa->q) == 0);
 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 *pr0 = BN_new();
 141
 142         if (pr0 == NULL)
 143             goto err;
 144         BN_with_flags(pr0, r0, BN_FLG_CONSTTIME);
 145         if (!BN_mod_inverse(rsa->d, rsa->e, pr0, ctx)) {
 146             BN_free(pr0);
 147             goto err;               /* d */
 148         }
 149         /* We MUST free pr0 before any further use of r0 */
 150         BN_free(pr0);
 151     }
 152
 153     {
 154         BIGNUM *d = BN_new();
 155
 156         if (d == NULL)
 157             goto err;
 158         BN_with_flags(d, rsa->d, BN_FLG_CONSTTIME);
 159
 160         if (   /* calculate d mod (p-1) */
 161                !BN_mod(rsa->dmp1, d, r1, ctx)
 162                /* calculate d mod (q-1) */
 163             || !BN_mod(rsa->dmq1, d, r2, ctx)) {
 164             BN_free(d);
 165             goto err;
 166         }
 167         /* We MUST free d before any further use of rsa->d */
 168         BN_free(d);
 169     }
 170
 171     {
 172         BIGNUM *p = BN_new();
 173
 174         if (p == NULL)
 175             goto err;
 176         BN_with_flags(p, rsa->p, BN_FLG_CONSTTIME);
 177
 178         /* calculate inverse of q mod p */
 179         if (!BN_mod_inverse(rsa->iqmp, rsa->q, p, ctx)) {
 180             BN_free(p);
 181             goto err;
 182         }
 183         /* We MUST free p before any further use of rsa->p */
 184         BN_free(p);
 185     }
 186
 187     ok = 1;
 188  err:
 189     if (ok == -1) {
 190         RSAerr(RSA_F_RSA_BUILTIN_KEYGEN, ERR_LIB_BN);
 191         ok = 0;
 192     }
 193     if (ctx != NULL)
 194         BN_CTX_end(ctx);
 195     BN_CTX_free(ctx);
 196
 197     return ok;
 198 }