Embed:
(wiki syntax)
Show/hide line numbers
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 if( f_rng != NULL && P != NULL && 00355 ( ret = mbedtls_mpi_is_prime( P, f_rng, p_rng ) ) != 0 ) 00356 { 00357 ret = MBEDTLS_ERR_RSA_KEY_CHECK_FAILED; 00358 goto cleanup; 00359 } 00360 00361 if( f_rng != NULL && Q != NULL && 00362 ( ret = mbedtls_mpi_is_prime( Q, f_rng, p_rng ) ) != 0 ) 00363 { 00364 ret = MBEDTLS_ERR_RSA_KEY_CHECK_FAILED; 00365 goto cleanup; 00366 } 00367 #else 00368 ((void) f_rng); 00369 ((void) p_rng); 00370 #endif /* MBEDTLS_GENPRIME */ 00371 00372 /* 00373 * Step 2: Check that 1 < N = P * Q 00374 */ 00375 00376 if( P != NULL && Q != NULL && N != NULL ) 00377 { 00378 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &K, P, Q ) ); 00379 if( mbedtls_mpi_cmp_int( N, 1 ) <= 0 || 00380 mbedtls_mpi_cmp_mpi( &K, N ) != 0 ) 00381 { 00382 ret = MBEDTLS_ERR_RSA_KEY_CHECK_FAILED; 00383 goto cleanup; 00384 } 00385 } 00386 00387 /* 00388 * Step 3: Check and 1 < D, E < N if present. 00389 */ 00390 00391 if( N != NULL && D != NULL && E != NULL ) 00392 { 00393 if ( mbedtls_mpi_cmp_int( D, 1 ) <= 0 || 00394 mbedtls_mpi_cmp_int( E, 1 ) <= 0 || 00395 mbedtls_mpi_cmp_mpi( D, N ) >= 0 || 00396 mbedtls_mpi_cmp_mpi( E, N ) >= 0 ) 00397 { 00398 ret = MBEDTLS_ERR_RSA_KEY_CHECK_FAILED; 00399 goto cleanup; 00400 } 00401 } 00402 00403 /* 00404 * Step 4: Check that D, E are inverse modulo P-1 and Q-1 00405 */ 00406 00407 if( P != NULL && Q != NULL && D != NULL && E != NULL ) 00408 { 00409 if( mbedtls_mpi_cmp_int( P, 1 ) <= 0 || 00410 mbedtls_mpi_cmp_int( Q, 1 ) <= 0 ) 00411 { 00412 ret = MBEDTLS_ERR_RSA_KEY_CHECK_FAILED; 00413 goto cleanup; 00414 } 00415 00416 /* Compute DE-1 mod P-1 */ 00417 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &K, D, E ) ); 00418 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_int( &K, &K, 1 ) ); 00419 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_int( &L, P, 1 ) ); 00420 MBEDTLS_MPI_CHK( mbedtls_mpi_mod_mpi( &K, &K, &L ) ); 00421 if( mbedtls_mpi_cmp_int( &K, 0 ) != 0 ) 00422 { 00423 ret = MBEDTLS_ERR_RSA_KEY_CHECK_FAILED; 00424 goto cleanup; 00425 } 00426 00427 /* Compute DE-1 mod Q-1 */ 00428 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &K, D, E ) ); 00429 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_int( &K, &K, 1 ) ); 00430 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_int( &L, Q, 1 ) ); 00431 MBEDTLS_MPI_CHK( mbedtls_mpi_mod_mpi( &K, &K, &L ) ); 00432 if( mbedtls_mpi_cmp_int( &K, 0 ) != 0 ) 00433 { 00434 ret = MBEDTLS_ERR_RSA_KEY_CHECK_FAILED; 00435 goto cleanup; 00436 } 00437 } 00438 00439 cleanup: 00440 00441 mbedtls_mpi_free( &K ); 00442 mbedtls_mpi_free( &L ); 00443 00444 /* Wrap MPI error codes by RSA check failure error code */ 00445 if( ret != 0 && ret != MBEDTLS_ERR_RSA_KEY_CHECK_FAILED ) 00446 { 00447 ret += MBEDTLS_ERR_RSA_KEY_CHECK_FAILED; 00448 } 00449 00450 return( ret ); 00451 } 00452 00453 int mbedtls_rsa_deduce_crt( const mbedtls_mpi *P, const mbedtls_mpi *Q, 00454 const mbedtls_mpi *D, mbedtls_mpi *DP, 00455 mbedtls_mpi *DQ, mbedtls_mpi *QP ) 00456 { 00457 int ret = 0; 00458 mbedtls_mpi K; 00459 mbedtls_mpi_init( &K ); 00460 00461 /* DP = D mod P-1 */ 00462 if( DP != NULL ) 00463 { 00464 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_int( &K, P, 1 ) ); 00465 MBEDTLS_MPI_CHK( mbedtls_mpi_mod_mpi( DP, D, &K ) ); 00466 } 00467 00468 /* DQ = D mod Q-1 */ 00469 if( DQ != NULL ) 00470 { 00471 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_int( &K, Q, 1 ) ); 00472 MBEDTLS_MPI_CHK( mbedtls_mpi_mod_mpi( DQ, D, &K ) ); 00473 } 00474 00475 /* QP = Q^{-1} mod P */ 00476 if( QP != NULL ) 00477 { 00478 MBEDTLS_MPI_CHK( mbedtls_mpi_inv_mod( QP, Q, P ) ); 00479 } 00480 00481 cleanup: 00482 mbedtls_mpi_free( &K ); 00483 00484 return( ret ); 00485 } 00486 00487 #endif /* MBEDTLS_RSA_C */
Generated on Tue Jul 12 2022 12:22:19 by
1.7.2