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