git.zerfleddert.de Git - proxmark3-svn/blob - common/mbedtls/rsa_internal.c

   1 /*
   2  *  Helper functions for the RSA module
   3  *
   4  *  Copyright (C) 2006-2017, ARM Limited, All Rights Reserved
   5  *  SPDX-License-Identifier: GPL-2.0
   6  *
   7  *  This program is free software; you can redistribute it and/or modify
   8  *  it under the terms of the GNU General Public License as published by
   9  *  the Free Software Foundation; either version 2 of the License, or
  10  *  (at your option) any later version.
  11  *
  12  *  This program is distributed in the hope that it will be useful,
  13  *  but WITHOUT ANY WARRANTY; without even the implied warranty of
  14  *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  15  *  GNU General Public License for more details.
  16  *
  17  *  You should have received a copy of the GNU General Public License along
  18  *  with this program; if not, write to the Free Software Foundation, Inc.,
  19  *  51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
  20  *
  21  *  This file is part of mbed TLS (https://tls.mbed.org)
  22  *
  23  */
  24
  25 #if !defined(MBEDTLS_CONFIG_FILE)
  26 #include "mbedtls/config.h"
  27 #else
  28 #include MBEDTLS_CONFIG_FILE
  29 #endif
  30
  31 #if defined(MBEDTLS_RSA_C)
  32
  33 #include "mbedtls/rsa.h"
  34 #include "mbedtls/bignum.h"
  35 #include "mbedtls/rsa_internal.h"
  36
  37 /*
  38  * Compute RSA prime factors from public and private exponents
  39  *
  40  * Summary of algorithm:
  41  * Setting F := lcm(P-1,Q-1), the idea is as follows:
  42  *
  43  * (a) For any 1 <= X < N with gcd(X,N)=1, we have X^F = 1 modulo N, so X^(F/2)
  44  *     is a square root of 1 in Z/NZ. Since Z/NZ ~= Z/PZ x Z/QZ by CRT and the
  45  *     square roots of 1 in Z/PZ and Z/QZ are +1 and -1, this leaves the four
  46  *     possibilities X^(F/2) = (+-1, +-1). If it happens that X^(F/2) = (-1,+1)
  47  *     or (+1,-1), then gcd(X^(F/2) + 1, N) will be equal to one of the prime
  48  *     factors of N.
  49  *
  50  * (b) If we don't know F/2 but (F/2) * K for some odd (!) K, then the same
  51  *     construction still applies since (-)^K is the identity on the set of
  52  *     roots of 1 in Z/NZ.
  53  *
  54  * The public and private key primitives (-)^E and (-)^D are mutually inverse
  55  * bijections on Z/NZ if and only if (-)^(DE) is the identity on Z/NZ, i.e.
  56  * if and only if DE - 1 is a multiple of F, say DE - 1 = F * L.
  57  * Splitting L = 2^t * K with K odd, we have
  58  *
  59  *   DE - 1 = FL = (F/2) * (2^(t+1)) * K,
  60  *
  61  * so (F / 2) * K is among the numbers
  62  *
  63  *   (DE - 1) >> 1, (DE - 1) >> 2, ..., (DE - 1) >> ord
  64  *
  65  * where ord is the order of 2 in (DE - 1).
  66  * We can therefore iterate through these numbers apply the construction
  67  * of (a) and (b) above to attempt to factor N.
  68  *
  69  */
  70 int mbedtls_rsa_deduce_primes( mbedtls_mpi const *N,
  71                      mbedtls_mpi const *E, mbedtls_mpi const *D,
  72                      mbedtls_mpi *P, mbedtls_mpi *Q )
  73 {
  74     int ret = 0;
  75
  76     uint16_t attempt;  /* Number of current attempt  */
  77     uint16_t iter;     /* Number of squares computed in the current attempt */
  78
  79     uint16_t order;    /* Order of 2 in DE - 1 */
  80
  81     mbedtls_mpi T;  /* Holds largest odd divisor of DE - 1     */
  82     mbedtls_mpi K;  /* Temporary holding the current candidate */
  83
  84     const unsigned char primes[] = { 2,
  85            3,    5,    7,   11,   13,   17,   19,   23,
  86           29,   31,   37,   41,   43,   47,   53,   59,
  87           61,   67,   71,   73,   79,   83,   89,   97,
  88          101,  103,  107,  109,  113,  127,  131,  137,
  89          139,  149,  151,  157,  163,  167,  173,  179,
  90          181,  191,  193,  197,  199,  211,  223,  227,
  91          229,  233,  239,  241,  251
  92     };
  93
  94     const size_t num_primes = sizeof( primes ) / sizeof( *primes );
  95
  96     if( P == NULL || Q == NULL || P->p != NULL || Q->p != NULL )
  97         return( MBEDTLS_ERR_MPI_BAD_INPUT_DATA );
  98
  99     if( mbedtls_mpi_cmp_int( N, 0 ) <= 0 ||
 100         mbedtls_mpi_cmp_int( D, 1 ) <= 0 ||
 101         mbedtls_mpi_cmp_mpi( D, N ) >= 0 ||
 102         mbedtls_mpi_cmp_int( E, 1 ) <= 0 ||
 103         mbedtls_mpi_cmp_mpi( E, N ) >= 0 )
 104     {
 105         return( MBEDTLS_ERR_MPI_BAD_INPUT_DATA );
 106     }
 107
 108     /*
 109      * Initializations and temporary changes
 110      */
 111
 112     mbedtls_mpi_init( &K );
 113     mbedtls_mpi_init( &T );
 114
 115     /* T := DE - 1 */
 116     MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &T, D,  E ) );
 117     MBEDTLS_MPI_CHK( mbedtls_mpi_sub_int( &T, &T, 1 ) );
 118
 119     if( ( order = (uint16_t) mbedtls_mpi_lsb( &T ) ) == 0 )
 120     {
 121         ret = MBEDTLS_ERR_MPI_BAD_INPUT_DATA;
 122         goto cleanup;
 123     }
 124
 125     /* After this operation, T holds the largest odd divisor of DE - 1. */
 126     MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( &T, order ) );
 127
 128     /*
 129      * Actual work
 130      */
 131
 132     /* Skip trying 2 if N == 1 mod 8 */
 133     attempt = 0;
 134     if( N->p[0] % 8 == 1 )
 135         attempt = 1;
 136
 137     for( ; attempt < num_primes; ++attempt )
 138     {
 139         mbedtls_mpi_lset( &K, primes[attempt] );
 140
 141         /* Check if gcd(K,N) = 1 */
 142         MBEDTLS_MPI_CHK( mbedtls_mpi_gcd( P, &K, N ) );
 143         if( mbedtls_mpi_cmp_int( P, 1 ) != 0 )
 144             continue;
 145
 146         /* Go through K^T + 1, K^(2T) + 1, K^(4T) + 1, ...
 147          * and check whether they have nontrivial GCD with N. */
 148         MBEDTLS_MPI_CHK( mbedtls_mpi_exp_mod( &K, &K, &T, N,
 149                              Q /* temporarily use Q for storing Montgomery
 150                                 * multiplication helper values */ ) );
 151
 152         for( iter = 1; iter <= order; ++iter )
 153         {
 154             /* If we reach 1 prematurely, there's no point
 155              * in continuing to square K */
 156             if( mbedtls_mpi_cmp_int( &K, 1 ) == 0 )
 157                 break;
 158
 159             MBEDTLS_MPI_CHK( mbedtls_mpi_add_int( &K, &K, 1 ) );
 160             MBEDTLS_MPI_CHK( mbedtls_mpi_gcd( P, &K, N ) );
 161
 162             if( mbedtls_mpi_cmp_int( P, 1 ) ==  1 &&
 163                 mbedtls_mpi_cmp_mpi( P, N ) == -1 )
 164             {
 165                 /*
 166                  * Have found a nontrivial divisor P of N.
 167                  * Set Q := N / P.
 168                  */
 169
 170                 MBEDTLS_MPI_CHK( mbedtls_mpi_div_mpi( Q, NULL, N, P ) );
 171                 goto cleanup;
 172             }
 173
 174             MBEDTLS_MPI_CHK( mbedtls_mpi_sub_int( &K, &K, 1 ) );
 175             MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &K, &K, &K ) );
 176             MBEDTLS_MPI_CHK( mbedtls_mpi_mod_mpi( &K, &K, N ) );
 177         }
 178
 179         /*
 180          * If we get here, then either we prematurely aborted the loop because
 181          * we reached 1, or K holds primes[attempt]^(DE - 1) mod N, which must
 182          * be 1 if D,E,N were consistent.
 183          * Check if that's the case and abort if not, to avoid very long,
 184          * yet eventually failing, computations if N,D,E were not sane.
 185          */
 186         if( mbedtls_mpi_cmp_int( &K, 1 ) != 0 )
 187         {
 188             break;
 189         }
 190     }
 191
 192     ret = MBEDTLS_ERR_MPI_BAD_INPUT_DATA;
 193
 194 cleanup:
 195
 196     mbedtls_mpi_free( &K );
 197     mbedtls_mpi_free( &T );
 198     return( ret );
 199 }
 200
 201 /*
 202  * Given P, Q and the public exponent E, deduce D.
 203  * This is essentially a modular inversion.
 204  */
 205 int mbedtls_rsa_deduce_private_exponent( mbedtls_mpi const *P,
 206                                          mbedtls_mpi const *Q,
 207                                          mbedtls_mpi const *E,
 208                                          mbedtls_mpi *D )
 209 {
 210     int ret = 0;
 211     mbedtls_mpi K, L;
 212
 213     if( D == NULL || mbedtls_mpi_cmp_int( D, 0 ) != 0 )
 214         return( MBEDTLS_ERR_MPI_BAD_INPUT_DATA );
 215
 216     if( mbedtls_mpi_cmp_int( P, 1 ) <= 0 ||
 217         mbedtls_mpi_cmp_int( Q, 1 ) <= 0 ||
 218         mbedtls_mpi_cmp_int( E, 0 ) == 0 )
 219     {
 220         return( MBEDTLS_ERR_MPI_BAD_INPUT_DATA );
 221     }
 222
 223     mbedtls_mpi_init( &K );
 224     mbedtls_mpi_init( &L );
 225
 226     /* Temporarily put K := P-1 and L := Q-1 */
 227     MBEDTLS_MPI_CHK( mbedtls_mpi_sub_int( &K, P, 1 ) );
 228     MBEDTLS_MPI_CHK( mbedtls_mpi_sub_int( &L, Q, 1 ) );
 229
 230     /* Temporarily put D := gcd(P-1, Q-1) */
 231     MBEDTLS_MPI_CHK( mbedtls_mpi_gcd( D, &K, &L ) );
 232
 233     /* K := LCM(P-1, Q-1) */
 234     MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &K, &K, &L ) );
 235     MBEDTLS_MPI_CHK( mbedtls_mpi_div_mpi( &K, NULL, &K, D ) );
 236
 237     /* Compute modular inverse of E in LCM(P-1, Q-1) */
 238     MBEDTLS_MPI_CHK( mbedtls_mpi_inv_mod( D, E, &K ) );
 239
 240 cleanup:
 241
 242     mbedtls_mpi_free( &K );
 243     mbedtls_mpi_free( &L );
 244
 245     return( ret );
 246 }
 247
 248 /*
 249  * Check that RSA CRT parameters are in accordance with core parameters.
 250  */
 251 int mbedtls_rsa_validate_crt( const mbedtls_mpi *P,  const mbedtls_mpi *Q,
 252                               const mbedtls_mpi *D,  const mbedtls_mpi *DP,
 253                               const mbedtls_mpi *DQ, const mbedtls_mpi *QP )
 254 {
 255     int ret = 0;
 256
 257     mbedtls_mpi K, L;
 258     mbedtls_mpi_init( &K );
 259     mbedtls_mpi_init( &L );
 260
 261     /* Check that DP - D == 0 mod P - 1 */
 262     if( DP != NULL )
 263     {
 264         if( P == NULL )
 265         {
 266             ret = MBEDTLS_ERR_RSA_BAD_INPUT_DATA;
 267             goto cleanup;
 268         }
 269
 270         MBEDTLS_MPI_CHK( mbedtls_mpi_sub_int( &K, P, 1 ) );
 271         MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &L, DP, D ) );
 272         MBEDTLS_MPI_CHK( mbedtls_mpi_mod_mpi( &L, &L, &K ) );
 273
 274         if( mbedtls_mpi_cmp_int( &L, 0 ) != 0 )
 275         {
 276             ret = MBEDTLS_ERR_RSA_KEY_CHECK_FAILED;
 277             goto cleanup;
 278         }
 279     }
 280
 281     /* Check that DQ - D == 0 mod Q - 1 */
 282     if( DQ != NULL )
 283     {
 284         if( Q == NULL )
 285         {
 286             ret = MBEDTLS_ERR_RSA_BAD_INPUT_DATA;
 287             goto cleanup;
 288         }
 289
 290         MBEDTLS_MPI_CHK( mbedtls_mpi_sub_int( &K, Q, 1 ) );
 291         MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &L, DQ, D ) );
 292         MBEDTLS_MPI_CHK( mbedtls_mpi_mod_mpi( &L, &L, &K ) );
 293
 294         if( mbedtls_mpi_cmp_int( &L, 0 ) != 0 )
 295         {
 296             ret = MBEDTLS_ERR_RSA_KEY_CHECK_FAILED;
 297             goto cleanup;
 298         }
 299     }
 300
 301     /* Check that QP * Q - 1 == 0 mod P */
 302     if( QP != NULL )
 303     {
 304         if( P == NULL || Q == NULL )
 305         {
 306             ret = MBEDTLS_ERR_RSA_BAD_INPUT_DATA;
 307             goto cleanup;
 308         }
 309
 310         MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &K, QP, Q ) );
 311         MBEDTLS_MPI_CHK( mbedtls_mpi_sub_int( &K, &K, 1 ) );
 312         MBEDTLS_MPI_CHK( mbedtls_mpi_mod_mpi( &K, &K, P ) );
 313         if( mbedtls_mpi_cmp_int( &K, 0 ) != 0 )
 314         {
 315             ret = MBEDTLS_ERR_RSA_KEY_CHECK_FAILED;
 316             goto cleanup;
 317         }
 318     }
 319
 320 cleanup:
 321
 322     /* Wrap MPI error codes by RSA check failure error code */
 323     if( ret != 0 &&
 324         ret != MBEDTLS_ERR_RSA_KEY_CHECK_FAILED &&
 325         ret != MBEDTLS_ERR_RSA_BAD_INPUT_DATA )
 326     {
 327         ret += MBEDTLS_ERR_RSA_KEY_CHECK_FAILED;
 328     }
 329
 330     mbedtls_mpi_free( &K );
 331     mbedtls_mpi_free( &L );
 332
 333     return( ret );
 334 }
 335
 336 /*
 337  * Check that core RSA parameters are sane.
 338  */
 339 int mbedtls_rsa_validate_params( const mbedtls_mpi *N, const mbedtls_mpi *P,
 340                                  const mbedtls_mpi *Q, const mbedtls_mpi *D,
 341                                  const mbedtls_mpi *E,
 342                                  int (*f_rng)(void *, unsigned char *, size_t),
 343                                  void *p_rng )
 344 {
 345     int ret = 0;
 346     mbedtls_mpi K, L;
 347
 348     mbedtls_mpi_init( &K );
 349     mbedtls_mpi_init( &L );
 350
 351     /*
 352      * Step 1: If PRNG provided, check that P and Q are prime
 353      */
 354
 355 #if defined(MBEDTLS_GENPRIME)
 356     if( f_rng != NULL && P != NULL &&
 357         ( ret = mbedtls_mpi_is_prime( P, f_rng, p_rng ) ) != 0 )
 358     {
 359         ret = MBEDTLS_ERR_RSA_KEY_CHECK_FAILED;
 360         goto cleanup;
 361     }
 362
 363     if( f_rng != NULL && Q != NULL &&
 364         ( ret = mbedtls_mpi_is_prime( Q, f_rng, p_rng ) ) != 0 )
 365     {
 366         ret = MBEDTLS_ERR_RSA_KEY_CHECK_FAILED;
 367         goto cleanup;
 368     }
 369 #else
 370     ((void) f_rng);
 371     ((void) p_rng);
 372 #endif /* MBEDTLS_GENPRIME */
 373
 374     /*
 375      * Step 2: Check that 1 < N = P * Q
 376      */
 377
 378     if( P != NULL && Q != NULL && N != NULL )
 379     {
 380         MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &K, P, Q ) );
 381         if( mbedtls_mpi_cmp_int( N, 1 )  <= 0 ||
 382             mbedtls_mpi_cmp_mpi( &K, N ) != 0 )
 383         {
 384             ret = MBEDTLS_ERR_RSA_KEY_CHECK_FAILED;
 385             goto cleanup;
 386         }
 387     }
 388
 389     /*
 390      * Step 3: Check and 1 < D, E < N if present.
 391      */
 392
 393     if( N != NULL && D != NULL && E != NULL )
 394     {
 395         if ( mbedtls_mpi_cmp_int( D, 1 ) <= 0 ||
 396              mbedtls_mpi_cmp_int( E, 1 ) <= 0 ||
 397              mbedtls_mpi_cmp_mpi( D, N ) >= 0 ||
 398              mbedtls_mpi_cmp_mpi( E, N ) >= 0 )
 399         {
 400             ret = MBEDTLS_ERR_RSA_KEY_CHECK_FAILED;
 401             goto cleanup;
 402         }
 403     }
 404
 405     /*
 406      * Step 4: Check that D, E are inverse modulo P-1 and Q-1
 407      */
 408
 409     if( P != NULL && Q != NULL && D != NULL && E != NULL )
 410     {
 411         if( mbedtls_mpi_cmp_int( P, 1 ) <= 0 ||
 412             mbedtls_mpi_cmp_int( Q, 1 ) <= 0 )
 413         {
 414             ret = MBEDTLS_ERR_RSA_KEY_CHECK_FAILED;
 415             goto cleanup;
 416         }
 417
 418         /* Compute DE-1 mod P-1 */
 419         MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &K, D, E ) );
 420         MBEDTLS_MPI_CHK( mbedtls_mpi_sub_int( &K, &K, 1 ) );
 421         MBEDTLS_MPI_CHK( mbedtls_mpi_sub_int( &L, P, 1 ) );
 422         MBEDTLS_MPI_CHK( mbedtls_mpi_mod_mpi( &K, &K, &L ) );
 423         if( mbedtls_mpi_cmp_int( &K, 0 ) != 0 )
 424         {
 425             ret = MBEDTLS_ERR_RSA_KEY_CHECK_FAILED;
 426             goto cleanup;
 427         }
 428
 429         /* Compute DE-1 mod Q-1 */
 430         MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &K, D, E ) );
 431         MBEDTLS_MPI_CHK( mbedtls_mpi_sub_int( &K, &K, 1 ) );
 432         MBEDTLS_MPI_CHK( mbedtls_mpi_sub_int( &L, Q, 1 ) );
 433         MBEDTLS_MPI_CHK( mbedtls_mpi_mod_mpi( &K, &K, &L ) );
 434         if( mbedtls_mpi_cmp_int( &K, 0 ) != 0 )
 435         {
 436             ret = MBEDTLS_ERR_RSA_KEY_CHECK_FAILED;
 437             goto cleanup;
 438         }
 439     }
 440
 441 cleanup:
 442
 443     mbedtls_mpi_free( &K );
 444     mbedtls_mpi_free( &L );
 445
 446     /* Wrap MPI error codes by RSA check failure error code */
 447     if( ret != 0 && ret != MBEDTLS_ERR_RSA_KEY_CHECK_FAILED )
 448     {
 449         ret += MBEDTLS_ERR_RSA_KEY_CHECK_FAILED;
 450     }
 451
 452     return( ret );
 453 }
 454
 455 int mbedtls_rsa_deduce_crt( const mbedtls_mpi *P, const mbedtls_mpi *Q,
 456                             const mbedtls_mpi *D, mbedtls_mpi *DP,
 457                             mbedtls_mpi *DQ, mbedtls_mpi *QP )
 458 {
 459     int ret = 0;
 460     mbedtls_mpi K;
 461     mbedtls_mpi_init( &K );
 462
 463     /* DP = D mod P-1 */
 464     if( DP != NULL )
 465     {
 466         MBEDTLS_MPI_CHK( mbedtls_mpi_sub_int( &K, P, 1  ) );
 467         MBEDTLS_MPI_CHK( mbedtls_mpi_mod_mpi( DP, D, &K ) );
 468     }
 469
 470     /* DQ = D mod Q-1 */
 471     if( DQ != NULL )
 472     {
 473         MBEDTLS_MPI_CHK( mbedtls_mpi_sub_int( &K, Q, 1  ) );
 474         MBEDTLS_MPI_CHK( mbedtls_mpi_mod_mpi( DQ, D, &K ) );
 475     }
 476
 477     /* QP = Q^{-1} mod P */
 478     if( QP != NULL )
 479     {
 480         MBEDTLS_MPI_CHK( mbedtls_mpi_inv_mod( QP, Q, P ) );
 481     }
 482
 483 cleanup:
 484     mbedtls_mpi_free( &K );
 485
 486     return( ret );
 487 }
 488
 489 #endif /* MBEDTLS_RSA_C */