rsa_internal.c

00001 /*
00002  *  Helper functions for the RSA module
00003  *
00004  *  Copyright (C) 2006-2017, ARM Limited, All Rights Reserved
00005  *  SPDX-License-Identifier: Apache-2.0
00006  *
00007  *  Licensed under the Apache License, Version 2.0 (the "License"); you may
00008  *  not use this file except in compliance with the License.
00009  *  You may obtain a copy of the License at
00010  *
00011  *  http://www.apache.org/licenses/LICENSE-2.0
00012  *
00013  *  Unless required by applicable law or agreed to in writing, software
00014  *  distributed under the License is distributed on an "AS IS" BASIS, WITHOUT
00015  *  WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
00016  *  See the License for the specific language governing permissions and
00017  *  limitations under the License.
00018  *
00019  *  This file is part of mbed TLS (https://tls.mbed.org)
00020  *
00021  */
00022 
00023 #if !defined(MBEDTLS_CONFIG_FILE)
00024 #include "mbedtls/config.h"
00025 #else
00026 #include MBEDTLS_CONFIG_FILE
00027 #endif
00028 
00029 #if defined(MBEDTLS_RSA_C)
00030 
00031 #include "mbedtls/rsa.h"
00032 #include "mbedtls/bignum.h"
00033 #include "mbedtls/rsa_internal.h"
00034 
00035 /*
00036  * Compute RSA prime factors from public and private exponents
00037  *
00038  * Summary of algorithm:
00039  * Setting F := lcm(P-1,Q-1), the idea is as follows:
00040  *
00041  * (a) For any 1 <= X < N with gcd(X,N)=1, we have X^F = 1 modulo N, so X^(F/2)
00042  *     is a square root of 1 in Z/NZ. Since Z/NZ ~= Z/PZ x Z/QZ by CRT and the
00043  *     square roots of 1 in Z/PZ and Z/QZ are +1 and -1, this leaves the four
00044  *     possibilities X^(F/2) = (+-1, +-1). If it happens that X^(F/2) = (-1,+1)
00045  *     or (+1,-1), then gcd(X^(F/2) + 1, N) will be equal to one of the prime
00046  *     factors of N.
00047  *
00048  * (b) If we don't know F/2 but (F/2) * K for some odd (!) K, then the same
00049  *     construction still applies since (-)^K is the identity on the set of
00050  *     roots of 1 in Z/NZ.
00051  *
00052  * The public and private key primitives (-)^E and (-)^D are mutually inverse
00053  * bijections on Z/NZ if and only if (-)^(DE) is the identity on Z/NZ, i.e.
00054  * if and only if DE - 1 is a multiple of F, say DE - 1 = F * L.
00055  * Splitting L = 2^t * K with K odd, we have
00056  *
00057  *   DE - 1 = FL = (F/2) * (2^(t+1)) * K,
00058  *
00059  * so (F / 2) * K is among the numbers
00060  *
00061  *   (DE - 1) >> 1, (DE - 1) >> 2, ..., (DE - 1) >> ord
00062  *
00063  * where ord is the order of 2 in (DE - 1).
00064  * We can therefore iterate through these numbers apply the construction
00065  * of (a) and (b) above to attempt to factor N.
00066  *
00067  */
00068 int mbedtls_rsa_deduce_primes( mbedtls_mpi const *N,
00069                      mbedtls_mpi const *E, mbedtls_mpi const *D,
00070                      mbedtls_mpi *P, mbedtls_mpi *Q )
00071 {
00072     int ret = 0;
00073 
00074     uint16_t attempt;  /* Number of current attempt  */
00075     uint16_t iter;     /* Number of squares computed in the current attempt */
00076 
00077     uint16_t order;    /* Order of 2 in DE - 1 */
00078 
00079     mbedtls_mpi T;  /* Holds largest odd divisor of DE - 1     */
00080     mbedtls_mpi K;  /* Temporary holding the current candidate */
00081 
00082     const unsigned char primes[] = { 2,
00083            3,    5,    7,   11,   13,   17,   19,   23,
00084           29,   31,   37,   41,   43,   47,   53,   59,
00085           61,   67,   71,   73,   79,   83,   89,   97,
00086          101,  103,  107,  109,  113,  127,  131,  137,
00087          139,  149,  151,  157,  163,  167,  173,  179,
00088          181,  191,  193,  197,  199,  211,  223,  227,
00089          229,  233,  239,  241,  251
00090     };
00091 
00092     const size_t num_primes = sizeof( primes ) / sizeof( *primes );
00093 
00094     if( P == NULL || Q == NULL || P->p  != NULL || Q->p  != NULL )
00095         return( MBEDTLS_ERR_MPI_BAD_INPUT_DATA );
00096 
00097     if( mbedtls_mpi_cmp_int( N, 0 ) <= 0 ||
00098         mbedtls_mpi_cmp_int( D, 1 ) <= 0 ||
00099         mbedtls_mpi_cmp_mpi( D, N ) >= 0 ||
00100         mbedtls_mpi_cmp_int( E, 1 ) <= 0 ||
00101         mbedtls_mpi_cmp_mpi( E, N ) >= 0 )
00102     {
00103         return( MBEDTLS_ERR_MPI_BAD_INPUT_DATA );
00104     }
00105 
00106     /*
00107      * Initializations and temporary changes
00108      */
00109 
00110     mbedtls_mpi_init( &K );
00111     mbedtls_mpi_init( &T );
00112 
00113     /* T := DE - 1 */
00114     MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &T, D,  E ) );
00115     MBEDTLS_MPI_CHK( mbedtls_mpi_sub_int( &T, &T, 1 ) );
00116 
00117     if( ( order = (uint16_t) mbedtls_mpi_lsb( &T ) ) == 0 )
00118     {
00119         ret = MBEDTLS_ERR_MPI_BAD_INPUT_DATA;
00120         goto cleanup;
00121     }
00122 
00123     /* After this operation, T holds the largest odd divisor of DE - 1. */
00124     MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( &T, order ) );
00125 
00126     /*
00127      * Actual work
00128      */
00129 
00130     /* Skip trying 2 if N == 1 mod 8 */
00131     attempt = 0;
00132     if( N->p [0] % 8 == 1 )
00133         attempt = 1;
00134 
00135     for( ; attempt < num_primes; ++attempt )
00136     {
00137         mbedtls_mpi_lset( &K, primes[attempt] );
00138 
00139         /* Check if gcd(K,N) = 1 */
00140         MBEDTLS_MPI_CHK( mbedtls_mpi_gcd( P, &K, N ) );
00141         if( mbedtls_mpi_cmp_int( P, 1 ) != 0 )
00142             continue;
00143 
00144         /* Go through K^T + 1, K^(2T) + 1, K^(4T) + 1, ...
00145          * and check whether they have nontrivial GCD with N. */
00146         MBEDTLS_MPI_CHK( mbedtls_mpi_exp_mod( &K, &K, &T, N,
00147                              Q /* temporarily use Q for storing Montgomery
00148                                 * multiplication helper values */ ) );
00149 
00150         for( iter = 1; iter <= order; ++iter )
00151         {
00152             /* If we reach 1 prematurely, there's no point
00153              * in continuing to square K */
00154             if( mbedtls_mpi_cmp_int( &K, 1 ) == 0 )
00155                 break;
00156 
00157             MBEDTLS_MPI_CHK( mbedtls_mpi_add_int( &K, &K, 1 ) );
00158             MBEDTLS_MPI_CHK( mbedtls_mpi_gcd( P, &K, N ) );
00159 
00160             if( mbedtls_mpi_cmp_int( P, 1 ) ==  1 &&
00161                 mbedtls_mpi_cmp_mpi( P, N ) == -1 )
00162             {
00163                 /*
00164                  * Have found a nontrivial divisor P of N.
00165                  * Set Q := N / P.
00166                  */
00167 
00168                 MBEDTLS_MPI_CHK( mbedtls_mpi_div_mpi( Q, NULL, N, P ) );
00169                 goto cleanup;
00170             }
00171 
00172             MBEDTLS_MPI_CHK( mbedtls_mpi_sub_int( &K, &K, 1 ) );
00173             MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &K, &K, &K ) );
00174             MBEDTLS_MPI_CHK( mbedtls_mpi_mod_mpi( &K, &K, N ) );
00175         }
00176 
00177         /*
00178          * If we get here, then either we prematurely aborted the loop because
00179          * we reached 1, or K holds primes[attempt]^(DE - 1) mod N, which must
00180          * be 1 if D,E,N were consistent.
00181          * Check if that's the case and abort if not, to avoid very long,
00182          * yet eventually failing, computations if N,D,E were not sane.
00183          */
00184         if( mbedtls_mpi_cmp_int( &K, 1 ) != 0 )
00185         {
00186             break;
00187         }
00188     }
00189 
00190     ret = MBEDTLS_ERR_MPI_BAD_INPUT_DATA;
00191 
00192 cleanup:
00193 
00194     mbedtls_mpi_free( &K );
00195     mbedtls_mpi_free( &T );
00196     return( ret );
00197 }
00198 
00199 /*
00200  * Given P, Q and the public exponent E, deduce D.
00201  * This is essentially a modular inversion.
00202  */
00203 int mbedtls_rsa_deduce_private_exponent( mbedtls_mpi const *P,
00204                                          mbedtls_mpi const *Q,
00205                                          mbedtls_mpi const *E,
00206                                          mbedtls_mpi *D )
00207 {
00208     int ret = 0;
00209     mbedtls_mpi K, L;
00210 
00211     if( D == NULL || mbedtls_mpi_cmp_int( D, 0 ) != 0 )
00212         return( MBEDTLS_ERR_MPI_BAD_INPUT_DATA );
00213 
00214     if( mbedtls_mpi_cmp_int( P, 1 ) <= 0 ||
00215         mbedtls_mpi_cmp_int( Q, 1 ) <= 0 ||
00216         mbedtls_mpi_cmp_int( E, 0 ) == 0 )
00217     {
00218         return( MBEDTLS_ERR_MPI_BAD_INPUT_DATA );
00219     }
00220 
00221     mbedtls_mpi_init( &K );
00222     mbedtls_mpi_init( &L );
00223 
00224     /* Temporarily put K := P-1 and L := Q-1 */
00225     MBEDTLS_MPI_CHK( mbedtls_mpi_sub_int( &K, P, 1 ) );
00226     MBEDTLS_MPI_CHK( mbedtls_mpi_sub_int( &L, Q, 1 ) );
00227 
00228     /* Temporarily put D := gcd(P-1, Q-1) */
00229     MBEDTLS_MPI_CHK( mbedtls_mpi_gcd( D, &K, &L ) );
00230 
00231     /* K := LCM(P-1, Q-1) */
00232     MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &K, &K, &L ) );
00233     MBEDTLS_MPI_CHK( mbedtls_mpi_div_mpi( &K, NULL, &K, D ) );
00234 
00235     /* Compute modular inverse of E in LCM(P-1, Q-1) */
00236     MBEDTLS_MPI_CHK( mbedtls_mpi_inv_mod( D, E, &K ) );
00237 
00238 cleanup:
00239 
00240     mbedtls_mpi_free( &K );
00241     mbedtls_mpi_free( &L );
00242 
00243     return( ret );
00244 }
00245 
00246 /*
00247  * Check that RSA CRT parameters are in accordance with core parameters.
00248  */
00249 int mbedtls_rsa_validate_crt( const mbedtls_mpi *P,  const mbedtls_mpi *Q,
00250                               const mbedtls_mpi *D,  const mbedtls_mpi *DP,
00251                               const mbedtls_mpi *DQ, const mbedtls_mpi *QP )
00252 {
00253     int ret = 0;
00254 
00255     mbedtls_mpi K, L;
00256     mbedtls_mpi_init( &K );
00257     mbedtls_mpi_init( &L );
00258 
00259     /* Check that DP - D == 0 mod P - 1 */
00260     if( DP != NULL )
00261     {
00262         if( P == NULL )
00263         {
00264             ret = MBEDTLS_ERR_RSA_BAD_INPUT_DATA;
00265             goto cleanup;
00266         }
00267 
00268         MBEDTLS_MPI_CHK( mbedtls_mpi_sub_int( &K, P, 1 ) );
00269         MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &L, DP, D ) );
00270         MBEDTLS_MPI_CHK( mbedtls_mpi_mod_mpi( &L, &L, &K ) );
00271 
00272         if( mbedtls_mpi_cmp_int( &L, 0 ) != 0 )
00273         {
00274             ret = MBEDTLS_ERR_RSA_KEY_CHECK_FAILED;
00275             goto cleanup;
00276         }
00277     }
00278 
00279     /* Check that DQ - D == 0 mod Q - 1 */
00280     if( DQ != NULL )
00281     {
00282         if( Q == NULL )
00283         {
00284             ret = MBEDTLS_ERR_RSA_BAD_INPUT_DATA;
00285             goto cleanup;
00286         }
00287 
00288         MBEDTLS_MPI_CHK( mbedtls_mpi_sub_int( &K, Q, 1 ) );
00289         MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &L, DQ, D ) );
00290         MBEDTLS_MPI_CHK( mbedtls_mpi_mod_mpi( &L, &L, &K ) );
00291 
00292         if( mbedtls_mpi_cmp_int( &L, 0 ) != 0 )
00293         {
00294             ret = MBEDTLS_ERR_RSA_KEY_CHECK_FAILED;
00295             goto cleanup;
00296         }
00297     }
00298 
00299     /* Check that QP * Q - 1 == 0 mod P */
00300     if( QP != NULL )
00301     {
00302         if( P == NULL || Q == NULL )
00303         {
00304             ret = MBEDTLS_ERR_RSA_BAD_INPUT_DATA;
00305             goto cleanup;
00306         }
00307 
00308         MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &K, QP, Q ) );
00309         MBEDTLS_MPI_CHK( mbedtls_mpi_sub_int( &K, &K, 1 ) );
00310         MBEDTLS_MPI_CHK( mbedtls_mpi_mod_mpi( &K, &K, P ) );
00311         if( mbedtls_mpi_cmp_int( &K, 0 ) != 0 )
00312         {
00313             ret = MBEDTLS_ERR_RSA_KEY_CHECK_FAILED;
00314             goto cleanup;
00315         }
00316     }
00317 
00318 cleanup:
00319 
00320     /* Wrap MPI error codes by RSA check failure error code */
00321     if( ret != 0 &&
00322         ret != MBEDTLS_ERR_RSA_KEY_CHECK_FAILED &&
00323         ret != MBEDTLS_ERR_RSA_BAD_INPUT_DATA )
00324     {
00325         ret += MBEDTLS_ERR_RSA_KEY_CHECK_FAILED;
00326     }
00327 
00328     mbedtls_mpi_free( &K );
00329     mbedtls_mpi_free( &L );
00330 
00331     return( ret );
00332 }
00333 
00334 /*
00335  * Check that core RSA parameters are sane.
00336  */
00337 int mbedtls_rsa_validate_params( const mbedtls_mpi *N, const mbedtls_mpi *P,
00338                                  const mbedtls_mpi *Q, const mbedtls_mpi *D,
00339                                  const mbedtls_mpi *E,
00340                                  int (*f_rng)(void *, unsigned char *, size_t),
00341                                  void *p_rng )
00342 {
00343     int ret = 0;
00344     mbedtls_mpi K, L;
00345 
00346     mbedtls_mpi_init( &K );
00347     mbedtls_mpi_init( &L );
00348 
00349     /*
00350      * Step 1: If PRNG provided, check that P and Q are prime
00351      */
00352 
00353 #if defined(MBEDTLS_GENPRIME)
00354     /*
00355      * When generating keys, the strongest security we support aims for an error
00356      * rate of at most 2^-100 and we are aiming for the same certainty here as
00357      * well.
00358      */
00359     if( f_rng != NULL && P != NULL &&
00360         ( ret = mbedtls_mpi_is_prime_ext( P, 50, f_rng, p_rng ) ) != 0 )
00361     {
00362         ret = MBEDTLS_ERR_RSA_KEY_CHECK_FAILED;
00363         goto cleanup;
00364     }
00365 
00366     if( f_rng != NULL && Q != NULL &&
00367         ( ret = mbedtls_mpi_is_prime_ext( Q, 50, f_rng, p_rng ) ) != 0 )
00368     {
00369         ret = MBEDTLS_ERR_RSA_KEY_CHECK_FAILED;
00370         goto cleanup;
00371     }
00372 #else
00373     ((void) f_rng);
00374     ((void) p_rng);
00375 #endif /* MBEDTLS_GENPRIME */
00376 
00377     /*
00378      * Step 2: Check that 1 < N = P * Q
00379      */
00380 
00381     if( P != NULL && Q != NULL && N != NULL )
00382     {
00383         MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &K, P, Q ) );
00384         if( mbedtls_mpi_cmp_int( N, 1 )  <= 0 ||
00385             mbedtls_mpi_cmp_mpi( &K, N ) != 0 )
00386         {
00387             ret = MBEDTLS_ERR_RSA_KEY_CHECK_FAILED;
00388             goto cleanup;
00389         }
00390     }
00391 
00392     /*
00393      * Step 3: Check and 1 < D, E < N if present.
00394      */
00395 
00396     if( N != NULL && D != NULL && E != NULL )
00397     {
00398         if ( mbedtls_mpi_cmp_int( D, 1 ) <= 0 ||
00399              mbedtls_mpi_cmp_int( E, 1 ) <= 0 ||
00400              mbedtls_mpi_cmp_mpi( D, N ) >= 0 ||
00401              mbedtls_mpi_cmp_mpi( E, N ) >= 0 )
00402         {
00403             ret = MBEDTLS_ERR_RSA_KEY_CHECK_FAILED;
00404             goto cleanup;
00405         }
00406     }
00407 
00408     /*
00409      * Step 4: Check that D, E are inverse modulo P-1 and Q-1
00410      */
00411 
00412     if( P != NULL && Q != NULL && D != NULL && E != NULL )
00413     {
00414         if( mbedtls_mpi_cmp_int( P, 1 ) <= 0 ||
00415             mbedtls_mpi_cmp_int( Q, 1 ) <= 0 )
00416         {
00417             ret = MBEDTLS_ERR_RSA_KEY_CHECK_FAILED;
00418             goto cleanup;
00419         }
00420 
00421         /* Compute DE-1 mod P-1 */
00422         MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &K, D, E ) );
00423         MBEDTLS_MPI_CHK( mbedtls_mpi_sub_int( &K, &K, 1 ) );
00424         MBEDTLS_MPI_CHK( mbedtls_mpi_sub_int( &L, P, 1 ) );
00425         MBEDTLS_MPI_CHK( mbedtls_mpi_mod_mpi( &K, &K, &L ) );
00426         if( mbedtls_mpi_cmp_int( &K, 0 ) != 0 )
00427         {
00428             ret = MBEDTLS_ERR_RSA_KEY_CHECK_FAILED;
00429             goto cleanup;
00430         }
00431 
00432         /* Compute DE-1 mod Q-1 */
00433         MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &K, D, E ) );
00434         MBEDTLS_MPI_CHK( mbedtls_mpi_sub_int( &K, &K, 1 ) );
00435         MBEDTLS_MPI_CHK( mbedtls_mpi_sub_int( &L, Q, 1 ) );
00436         MBEDTLS_MPI_CHK( mbedtls_mpi_mod_mpi( &K, &K, &L ) );
00437         if( mbedtls_mpi_cmp_int( &K, 0 ) != 0 )
00438         {
00439             ret = MBEDTLS_ERR_RSA_KEY_CHECK_FAILED;
00440             goto cleanup;
00441         }
00442     }
00443 
00444 cleanup:
00445 
00446     mbedtls_mpi_free( &K );
00447     mbedtls_mpi_free( &L );
00448 
00449     /* Wrap MPI error codes by RSA check failure error code */
00450     if( ret != 0 && ret != MBEDTLS_ERR_RSA_KEY_CHECK_FAILED )
00451     {
00452         ret += MBEDTLS_ERR_RSA_KEY_CHECK_FAILED;
00453     }
00454 
00455     return( ret );
00456 }
00457 
00458 int mbedtls_rsa_deduce_crt( const mbedtls_mpi *P, const mbedtls_mpi *Q,
00459                             const mbedtls_mpi *D, mbedtls_mpi *DP,
00460                             mbedtls_mpi *DQ, mbedtls_mpi *QP )
00461 {
00462     int ret = 0;
00463     mbedtls_mpi K;
00464     mbedtls_mpi_init( &K );
00465 
00466     /* DP = D mod P-1 */
00467     if( DP != NULL )
00468     {
00469         MBEDTLS_MPI_CHK( mbedtls_mpi_sub_int( &K, P, 1  ) );
00470         MBEDTLS_MPI_CHK( mbedtls_mpi_mod_mpi( DP, D, &K ) );
00471     }
00472 
00473     /* DQ = D mod Q-1 */
00474     if( DQ != NULL )
00475     {
00476         MBEDTLS_MPI_CHK( mbedtls_mpi_sub_int( &K, Q, 1  ) );
00477         MBEDTLS_MPI_CHK( mbedtls_mpi_mod_mpi( DQ, D, &K ) );
00478     }
00479 
00480     /* QP = Q^{-1} mod P */
00481     if( QP != NULL )
00482     {
00483         MBEDTLS_MPI_CHK( mbedtls_mpi_inv_mod( QP, Q, P ) );
00484     }
00485 
00486 cleanup:
00487     mbedtls_mpi_free( &K );
00488 
00489     return( ret );
00490 }
00491 
00492 #endif /* MBEDTLS_RSA_C */