crypto/rsa/rsa_chk.c

   1 /* ====================================================================
   2  * Copyright (c) 1999 The OpenSSL Project.  All rights reserved.
   3  *
   4  * Redistribution and use in source and binary forms, with or without
   5  * modification, are permitted provided that the following conditions
   6  * are met:
   7  *
   8  * 1. Redistributions of source code must retain the above copyright
   9  *    notice, this list of conditions and the following disclaimer.
  10  *
  11  * 2. Redistributions in binary form must reproduce the above copyright
  12  *    notice, this list of conditions and the following disclaimer in
  13  *    the documentation and/or other materials provided with the
  14  *    distribution.
  15  *
  16  * 3. All advertising materials mentioning features or use of this
  17  *    software must display the following acknowledgment:
  18  *    "This product includes software developed by the OpenSSL Project
  19  *    for use in the OpenSSL Toolkit. (http://www.OpenSSL.org/)"
  20  *
  21  * 4. The names "OpenSSL Toolkit" and "OpenSSL Project" must not be used to
  22  *    endorse or promote products derived from this software without
  23  *    prior written permission. For written permission, please contact
  24  *    openssl-core@OpenSSL.org.
  25  *
  26  * 5. Products derived from this software may not be called "OpenSSL"
  27  *    nor may "OpenSSL" appear in their names without prior written
  28  *    permission of the OpenSSL Project.
  29  *
  30  * 6. Redistributions of any form whatsoever must retain the following
  31  *    acknowledgment:
  32  *    "This product includes software developed by the OpenSSL Project
  33  *    for use in the OpenSSL Toolkit (http://www.OpenSSL.org/)"
  34  *
  35  * THIS SOFTWARE IS PROVIDED BY THE OpenSSL PROJECT ``AS IS'' AND ANY
  36  * EXPRESSED OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  37  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
  38  * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL THE OpenSSL PROJECT OR
  39  * ITS CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
  40  * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
  41  * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
  42  * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  43  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
  44  * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
  45  * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED
  46  * OF THE POSSIBILITY OF SUCH DAMAGE.
  47  * ====================================================================
  48  */
  49
  50 #include <openssl/bn.h>
  51 #include <openssl/err.h>
  52 #include "rsa_locl.h"
  53
  54 int RSA_check_key(const RSA *key)
  55 {
  56     return RSA_check_key_ex(key, NULL);
  57 }
  58
  59 int RSA_check_key_ex(const RSA *key, BN_GENCB *cb)
  60 {
  61     BIGNUM *i, *j, *k, *l, *m;
  62     BN_CTX *ctx;
  63     int r;
  64     int ret = 1;
  65
  66     if (!key->p || !key->q || !key->n || !key->e || !key->d) {
  67         RSAerr(RSA_F_RSA_CHECK_KEY_EX, RSA_R_VALUE_MISSING);
  68         return 0;
  69     }
  70
  71     i = BN_new();
  72     j = BN_new();
  73     k = BN_new();
  74     l = BN_new();
  75     m = BN_new();
  76     ctx = BN_CTX_new();
  77     if (i == NULL || j == NULL || k == NULL || l == NULL ||
  78         m == NULL || ctx == NULL) {
  79         ret = -1;
  80         RSAerr(RSA_F_RSA_CHECK_KEY_EX, ERR_R_MALLOC_FAILURE);
  81         goto err;
  82     }
  83
  84     /* p prime? */
  85     r = BN_is_prime_ex(key->p, BN_prime_checks, NULL, cb);
  86     if (r != 1) {
  87         ret = r;
  88         if (r != 0)
  89             goto err;
  90         RSAerr(RSA_F_RSA_CHECK_KEY_EX, RSA_R_P_NOT_PRIME);
  91     }
  92
  93     /* q prime? */
  94     r = BN_is_prime_ex(key->q, BN_prime_checks, NULL, cb);
  95     if (r != 1) {
  96         ret = r;
  97         if (r != 0)
  98             goto err;
  99         RSAerr(RSA_F_RSA_CHECK_KEY_EX, RSA_R_Q_NOT_PRIME);
 100     }
 101
 102     /* n = p*q? */
 103     r = BN_mul(i, key->p, key->q, ctx);
 104     if (!r) {
 105         ret = -1;
 106         goto err;
 107     }
 108
 109     if (BN_cmp(i, key->n) != 0) {
 110         ret = 0;
 111         RSAerr(RSA_F_RSA_CHECK_KEY_EX, RSA_R_N_DOES_NOT_EQUAL_P_Q);
 112     }
 113
 114     /* d*e = 1  mod lcm(p-1,q-1)? */
 115
 116     r = BN_sub(i, key->p, BN_value_one());
 117     if (!r) {
 118         ret = -1;
 119         goto err;
 120     }
 121     r = BN_sub(j, key->q, BN_value_one());
 122     if (!r) {
 123         ret = -1;
 124         goto err;
 125     }
 126
 127     /* now compute k = lcm(i,j) */
 128     r = BN_mul(l, i, j, ctx);
 129     if (!r) {
 130         ret = -1;
 131         goto err;
 132     }
 133     r = BN_gcd(m, i, j, ctx);
 134     if (!r) {
 135         ret = -1;
 136         goto err;
 137     }
 138     r = BN_div(k, NULL, l, m, ctx); /* remainder is 0 */
 139     if (!r) {
 140         ret = -1;
 141         goto err;
 142     }
 143
 144     r = BN_mod_mul(i, key->d, key->e, k, ctx);
 145     if (!r) {
 146         ret = -1;
 147         goto err;
 148     }
 149
 150     if (!BN_is_one(i)) {
 151         ret = 0;
 152         RSAerr(RSA_F_RSA_CHECK_KEY_EX, RSA_R_D_E_NOT_CONGRUENT_TO_1);
 153     }
 154
 155     if (key->dmp1 != NULL && key->dmq1 != NULL && key->iqmp != NULL) {
 156         /* dmp1 = d mod (p-1)? */
 157         r = BN_sub(i, key->p, BN_value_one());
 158         if (!r) {
 159             ret = -1;
 160             goto err;
 161         }
 162
 163         r = BN_mod(j, key->d, i, ctx);
 164         if (!r) {
 165             ret = -1;
 166             goto err;
 167         }
 168
 169         if (BN_cmp(j, key->dmp1) != 0) {
 170             ret = 0;
 171             RSAerr(RSA_F_RSA_CHECK_KEY_EX, RSA_R_DMP1_NOT_CONGRUENT_TO_D);
 172         }
 173
 174         /* dmq1 = d mod (q-1)? */
 175         r = BN_sub(i, key->q, BN_value_one());
 176         if (!r) {
 177             ret = -1;
 178             goto err;
 179         }
 180
 181         r = BN_mod(j, key->d, i, ctx);
 182         if (!r) {
 183             ret = -1;
 184             goto err;
 185         }
 186
 187         if (BN_cmp(j, key->dmq1) != 0) {
 188             ret = 0;
 189             RSAerr(RSA_F_RSA_CHECK_KEY_EX, RSA_R_DMQ1_NOT_CONGRUENT_TO_D);
 190         }
 191
 192         /* iqmp = q^-1 mod p? */
 193         if (!BN_mod_inverse(i, key->q, key->p, ctx)) {
 194             ret = -1;
 195             goto err;
 196         }
 197
 198         if (BN_cmp(i, key->iqmp) != 0) {
 199             ret = 0;
 200             RSAerr(RSA_F_RSA_CHECK_KEY_EX, RSA_R_IQMP_NOT_INVERSE_OF_Q);
 201         }
 202     }
 203
 204  err:
 205     BN_free(i);
 206     BN_free(j);
 207     BN_free(k);
 208     BN_free(l);
 209     BN_free(m);
 210     BN_CTX_free(ctx);
 211     return (ret);
 212 }