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     BN_copy(rsa->e, e_value);
  79
  80     /* generate p and q */
  81     for (;;) {
  82         if (!BN_generate_prime_ex(rsa->p, bitsp, 0, NULL, NULL, cb))
  83             goto err;
  84         if (!BN_sub(r2, rsa->p, BN_value_one()))
  85             goto err;
  86         if (!BN_gcd(r1, r2, rsa->e, ctx))
  87             goto err;
  88         if (BN_is_one(r1))
  89             break;
  90         if (!BN_GENCB_call(cb, 2, n++))
  91             goto err;
  92     }
  93     if (!BN_GENCB_call(cb, 3, 0))
  94         goto err;
  95     for (;;) {
  96         /*
  97          * When generating ridiculously small keys, we can get stuck
  98          * continually regenerating the same prime values. Check for this and
  99          * bail if it happens 3 times.
 100          */
 101         unsigned int degenerate = 0;
 102         do {
 103             if (!BN_generate_prime_ex(rsa->q, bitsq, 0, NULL, NULL, cb))
 104                 goto err;
 105         } while ((BN_cmp(rsa->p, rsa->q) == 0) && (++degenerate < 3));
 106         if (degenerate == 3) {
 107             ok = 0;             /* we set our own err */
 108             RSAerr(RSA_F_RSA_BUILTIN_KEYGEN, RSA_R_KEY_SIZE_TOO_SMALL);
 109             goto err;
 110         }
 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 *local_r0 = NULL, *pr0;
 141         if (!(rsa->flags & RSA_FLAG_NO_CONSTTIME)) {
 142             pr0 = local_r0 = BN_new();
 143             if (local_r0 == NULL)
 144                 goto err;
 145             BN_with_flags(pr0, r0, BN_FLG_CONSTTIME);
 146         } else {
 147             pr0 = r0;
 148         }
 149         if (!BN_mod_inverse(rsa->d, rsa->e, pr0, ctx)) {
 150             BN_free(local_r0);
 151             goto err;               /* d */
 152         }
 153         /* We MUST free local_r0 before any further use of r0 */
 154         BN_free(local_r0);
 155     }
 156
 157     {
 158         BIGNUM *local_d = NULL, *d;
 159         /* set up d for correct BN_FLG_CONSTTIME flag */
 160         if (!(rsa->flags & RSA_FLAG_NO_CONSTTIME)) {
 161             d = local_d = BN_new();
 162             if (local_d == NULL)
 163                 goto err;
 164             BN_with_flags(d, rsa->d, BN_FLG_CONSTTIME);
 165         } else {
 166             d = rsa->d;
 167         }
 168
 169         if (   /* calculate d mod (p-1) */
 170                !BN_mod(rsa->dmp1, d, r1, ctx)
 171                /* calculate d mod (q-1) */
 172             || !BN_mod(rsa->dmq1, d, r2, ctx)) {
 173             BN_free(local_d);
 174             goto err;
 175         }
 176         /* We MUST free local_d before any further use of rsa->d */
 177         BN_free(local_d);
 178     }
 179
 180     {
 181         BIGNUM *local_p = NULL, *p;
 182
 183         /* calculate inverse of q mod p */
 184         if (!(rsa->flags & RSA_FLAG_NO_CONSTTIME)) {
 185             p = local_p = BN_new();
 186             if (local_p == NULL)
 187                 goto err;
 188             BN_with_flags(p, rsa->p, BN_FLG_CONSTTIME);
 189         } else {
 190             p = rsa->p;
 191         }
 192         if (!BN_mod_inverse(rsa->iqmp, rsa->q, p, ctx)) {
 193             BN_free(local_p);
 194             goto err;
 195         }
 196         /* We MUST free local_p before any further use of rsa->p */
 197         BN_free(local_p);
 198     }
 199
 200     ok = 1;
 201  err:
 202     if (ok == -1) {
 203         RSAerr(RSA_F_RSA_BUILTIN_KEYGEN, ERR_LIB_BN);
 204         ok = 0;
 205     }
 206     if (ctx != NULL)
 207         BN_CTX_end(ctx);
 208     BN_CTX_free(ctx);
 209
 210     return ok;
 211 }