git.sur5r.net Git - freertos/blob - FreeRTOS-Labs/Source/mbedtls/library/rsa_internal.c

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