Kenji Arai / mbed-os_TYBLE16

mbed-os5 only for TYBLE16

Dependents:   TYBLE16_simple_data_logger TYBLE16_MP3_Air

features/mbedtls/mbed-crypto/src/rsa_internal.c@1:9db0e321a9f4, 2019-12-31 (annotated)

Committer:
kenjiArai
Date:
Tue Dec 31 06:02:27 2019 +0000
Revision:
1:9db0e321a9f4
Parent:
0:5b88d5760320 
updated based on mbed-os5.15.0

Who changed what in which revision?

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