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