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