crypto/rsa/rsa_gen.c

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