2 * Helper functions for the RSA module
4 * Copyright (C) 2006-2017, ARM Limited, All Rights Reserved
5 * SPDX-License-Identifier: GPL-2.0
7 * This program is free software; you can redistribute it and/or modify
8 * it under the terms of the GNU General Public License as published by
9 * the Free Software Foundation; either version 2 of the License, or
10 * (at your option) any later version.
12 * This program is distributed in the hope that it will be useful,
13 * but WITHOUT ANY WARRANTY; without even the implied warranty of
14 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15 * GNU General Public License for more details.
17 * You should have received a copy of the GNU General Public License along
18 * with this program; if not, write to the Free Software Foundation, Inc.,
19 * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
21 * This file is part of mbed TLS (https://tls.mbed.org)
25 #if !defined(MBEDTLS_CONFIG_FILE)
26 #include "mbedtls/config.h"
28 #include MBEDTLS_CONFIG_FILE
31 #if defined(MBEDTLS_RSA_C)
33 #include "mbedtls/rsa.h"
34 #include "mbedtls/bignum.h"
35 #include "mbedtls/rsa_internal.h"
38 * Compute RSA prime factors from public and private exponents
40 * Summary of algorithm:
41 * Setting F := lcm(P-1,Q-1), the idea is as follows:
43 * (a) For any 1 <= X < N with gcd(X,N)=1, we have X^F = 1 modulo N, so X^(F/2)
44 * is a square root of 1 in Z/NZ. Since Z/NZ ~= Z/PZ x Z/QZ by CRT and the
45 * square roots of 1 in Z/PZ and Z/QZ are +1 and -1, this leaves the four
46 * possibilities X^(F/2) = (+-1, +-1). If it happens that X^(F/2) = (-1,+1)
47 * or (+1,-1), then gcd(X^(F/2) + 1, N) will be equal to one of the prime
50 * (b) If we don't know F/2 but (F/2) * K for some odd (!) K, then the same
51 * construction still applies since (-)^K is the identity on the set of
54 * The public and private key primitives (-)^E and (-)^D are mutually inverse
55 * bijections on Z/NZ if and only if (-)^(DE) is the identity on Z/NZ, i.e.
56 * if and only if DE - 1 is a multiple of F, say DE - 1 = F * L.
57 * Splitting L = 2^t * K with K odd, we have
59 * DE - 1 = FL = (F/2) * (2^(t+1)) * K,
61 * so (F / 2) * K is among the numbers
63 * (DE - 1) >> 1, (DE - 1) >> 2, ..., (DE - 1) >> ord
65 * where ord is the order of 2 in (DE - 1).
66 * We can therefore iterate through these numbers apply the construction
67 * of (a) and (b) above to attempt to factor N.
70 int mbedtls_rsa_deduce_primes( mbedtls_mpi
const *N
,
71 mbedtls_mpi
const *E
, mbedtls_mpi
const *D
,
72 mbedtls_mpi
*P
, mbedtls_mpi
*Q
)
76 uint16_t attempt
; /* Number of current attempt */
77 uint16_t iter
; /* Number of squares computed in the current attempt */
79 uint16_t order
; /* Order of 2 in DE - 1 */
81 mbedtls_mpi T
; /* Holds largest odd divisor of DE - 1 */
82 mbedtls_mpi K
; /* Temporary holding the current candidate */
84 const unsigned char primes
[] = { 2,
85 3, 5, 7, 11, 13, 17, 19, 23,
86 29, 31, 37, 41, 43, 47, 53, 59,
87 61, 67, 71, 73, 79, 83, 89, 97,
88 101, 103, 107, 109, 113, 127, 131, 137,
89 139, 149, 151, 157, 163, 167, 173, 179,
90 181, 191, 193, 197, 199, 211, 223, 227,
91 229, 233, 239, 241, 251
94 const size_t num_primes
= sizeof( primes
) / sizeof( *primes
);
96 if( P
== NULL
|| Q
== NULL
|| P
->p
!= NULL
|| Q
->p
!= NULL
)
97 return( MBEDTLS_ERR_MPI_BAD_INPUT_DATA
);
99 if( mbedtls_mpi_cmp_int( N
, 0 ) <= 0 ||
100 mbedtls_mpi_cmp_int( D
, 1 ) <= 0 ||
101 mbedtls_mpi_cmp_mpi( D
, N
) >= 0 ||
102 mbedtls_mpi_cmp_int( E
, 1 ) <= 0 ||
103 mbedtls_mpi_cmp_mpi( E
, N
) >= 0 )
105 return( MBEDTLS_ERR_MPI_BAD_INPUT_DATA
);
109 * Initializations and temporary changes
112 mbedtls_mpi_init( &K
);
113 mbedtls_mpi_init( &T
);
116 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &T
, D
, E
) );
117 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_int( &T
, &T
, 1 ) );
119 if( ( order
= (uint16_t) mbedtls_mpi_lsb( &T
) ) == 0 )
121 ret
= MBEDTLS_ERR_MPI_BAD_INPUT_DATA
;
125 /* After this operation, T holds the largest odd divisor of DE - 1. */
126 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( &T
, order
) );
132 /* Skip trying 2 if N == 1 mod 8 */
134 if( N
->p
[0] % 8 == 1 )
137 for( ; attempt
< num_primes
; ++attempt
)
139 mbedtls_mpi_lset( &K
, primes
[attempt
] );
141 /* Check if gcd(K,N) = 1 */
142 MBEDTLS_MPI_CHK( mbedtls_mpi_gcd( P
, &K
, N
) );
143 if( mbedtls_mpi_cmp_int( P
, 1 ) != 0 )
146 /* Go through K^T + 1, K^(2T) + 1, K^(4T) + 1, ...
147 * and check whether they have nontrivial GCD with N. */
148 MBEDTLS_MPI_CHK( mbedtls_mpi_exp_mod( &K
, &K
, &T
, N
,
149 Q
/* temporarily use Q for storing Montgomery
150 * multiplication helper values */ ) );
152 for( iter
= 1; iter
<= order
; ++iter
)
154 /* If we reach 1 prematurely, there's no point
155 * in continuing to square K */
156 if( mbedtls_mpi_cmp_int( &K
, 1 ) == 0 )
159 MBEDTLS_MPI_CHK( mbedtls_mpi_add_int( &K
, &K
, 1 ) );
160 MBEDTLS_MPI_CHK( mbedtls_mpi_gcd( P
, &K
, N
) );
162 if( mbedtls_mpi_cmp_int( P
, 1 ) == 1 &&
163 mbedtls_mpi_cmp_mpi( P
, N
) == -1 )
166 * Have found a nontrivial divisor P of N.
170 MBEDTLS_MPI_CHK( mbedtls_mpi_div_mpi( Q
, NULL
, N
, P
) );
174 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_int( &K
, &K
, 1 ) );
175 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &K
, &K
, &K
) );
176 MBEDTLS_MPI_CHK( mbedtls_mpi_mod_mpi( &K
, &K
, N
) );
180 * If we get here, then either we prematurely aborted the loop because
181 * we reached 1, or K holds primes[attempt]^(DE - 1) mod N, which must
182 * be 1 if D,E,N were consistent.
183 * Check if that's the case and abort if not, to avoid very long,
184 * yet eventually failing, computations if N,D,E were not sane.
186 if( mbedtls_mpi_cmp_int( &K
, 1 ) != 0 )
192 ret
= MBEDTLS_ERR_MPI_BAD_INPUT_DATA
;
196 mbedtls_mpi_free( &K
);
197 mbedtls_mpi_free( &T
);
202 * Given P, Q and the public exponent E, deduce D.
203 * This is essentially a modular inversion.
205 int mbedtls_rsa_deduce_private_exponent( mbedtls_mpi
const *P
,
206 mbedtls_mpi
const *Q
,
207 mbedtls_mpi
const *E
,
213 if( D
== NULL
|| mbedtls_mpi_cmp_int( D
, 0 ) != 0 )
214 return( MBEDTLS_ERR_MPI_BAD_INPUT_DATA
);
216 if( mbedtls_mpi_cmp_int( P
, 1 ) <= 0 ||
217 mbedtls_mpi_cmp_int( Q
, 1 ) <= 0 ||
218 mbedtls_mpi_cmp_int( E
, 0 ) == 0 )
220 return( MBEDTLS_ERR_MPI_BAD_INPUT_DATA
);
223 mbedtls_mpi_init( &K
);
224 mbedtls_mpi_init( &L
);
226 /* Temporarily put K := P-1 and L := Q-1 */
227 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_int( &K
, P
, 1 ) );
228 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_int( &L
, Q
, 1 ) );
230 /* Temporarily put D := gcd(P-1, Q-1) */
231 MBEDTLS_MPI_CHK( mbedtls_mpi_gcd( D
, &K
, &L
) );
233 /* K := LCM(P-1, Q-1) */
234 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &K
, &K
, &L
) );
235 MBEDTLS_MPI_CHK( mbedtls_mpi_div_mpi( &K
, NULL
, &K
, D
) );
237 /* Compute modular inverse of E in LCM(P-1, Q-1) */
238 MBEDTLS_MPI_CHK( mbedtls_mpi_inv_mod( D
, E
, &K
) );
242 mbedtls_mpi_free( &K
);
243 mbedtls_mpi_free( &L
);
249 * Check that RSA CRT parameters are in accordance with core parameters.
251 int mbedtls_rsa_validate_crt( const mbedtls_mpi
*P
, const mbedtls_mpi
*Q
,
252 const mbedtls_mpi
*D
, const mbedtls_mpi
*DP
,
253 const mbedtls_mpi
*DQ
, const mbedtls_mpi
*QP
)
258 mbedtls_mpi_init( &K
);
259 mbedtls_mpi_init( &L
);
261 /* Check that DP - D == 0 mod P - 1 */
266 ret
= MBEDTLS_ERR_RSA_BAD_INPUT_DATA
;
270 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_int( &K
, P
, 1 ) );
271 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &L
, DP
, D
) );
272 MBEDTLS_MPI_CHK( mbedtls_mpi_mod_mpi( &L
, &L
, &K
) );
274 if( mbedtls_mpi_cmp_int( &L
, 0 ) != 0 )
276 ret
= MBEDTLS_ERR_RSA_KEY_CHECK_FAILED
;
281 /* Check that DQ - D == 0 mod Q - 1 */
286 ret
= MBEDTLS_ERR_RSA_BAD_INPUT_DATA
;
290 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_int( &K
, Q
, 1 ) );
291 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &L
, DQ
, D
) );
292 MBEDTLS_MPI_CHK( mbedtls_mpi_mod_mpi( &L
, &L
, &K
) );
294 if( mbedtls_mpi_cmp_int( &L
, 0 ) != 0 )
296 ret
= MBEDTLS_ERR_RSA_KEY_CHECK_FAILED
;
301 /* Check that QP * Q - 1 == 0 mod P */
304 if( P
== NULL
|| Q
== NULL
)
306 ret
= MBEDTLS_ERR_RSA_BAD_INPUT_DATA
;
310 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &K
, QP
, Q
) );
311 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_int( &K
, &K
, 1 ) );
312 MBEDTLS_MPI_CHK( mbedtls_mpi_mod_mpi( &K
, &K
, P
) );
313 if( mbedtls_mpi_cmp_int( &K
, 0 ) != 0 )
315 ret
= MBEDTLS_ERR_RSA_KEY_CHECK_FAILED
;
322 /* Wrap MPI error codes by RSA check failure error code */
324 ret
!= MBEDTLS_ERR_RSA_KEY_CHECK_FAILED
&&
325 ret
!= MBEDTLS_ERR_RSA_BAD_INPUT_DATA
)
327 ret
+= MBEDTLS_ERR_RSA_KEY_CHECK_FAILED
;
330 mbedtls_mpi_free( &K
);
331 mbedtls_mpi_free( &L
);
337 * Check that core RSA parameters are sane.
339 int mbedtls_rsa_validate_params( const mbedtls_mpi
*N
, const mbedtls_mpi
*P
,
340 const mbedtls_mpi
*Q
, const mbedtls_mpi
*D
,
341 const mbedtls_mpi
*E
,
342 int (*f_rng
)(void *, unsigned char *, size_t),
348 mbedtls_mpi_init( &K
);
349 mbedtls_mpi_init( &L
);
352 * Step 1: If PRNG provided, check that P and Q are prime
355 #if defined(MBEDTLS_GENPRIME)
356 if( f_rng
!= NULL
&& P
!= NULL
&&
357 ( ret
= mbedtls_mpi_is_prime( P
, f_rng
, p_rng
) ) != 0 )
359 ret
= MBEDTLS_ERR_RSA_KEY_CHECK_FAILED
;
363 if( f_rng
!= NULL
&& Q
!= NULL
&&
364 ( ret
= mbedtls_mpi_is_prime( Q
, f_rng
, p_rng
) ) != 0 )
366 ret
= MBEDTLS_ERR_RSA_KEY_CHECK_FAILED
;
372 #endif /* MBEDTLS_GENPRIME */
375 * Step 2: Check that 1 < N = P * Q
378 if( P
!= NULL
&& Q
!= NULL
&& N
!= NULL
)
380 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &K
, P
, Q
) );
381 if( mbedtls_mpi_cmp_int( N
, 1 ) <= 0 ||
382 mbedtls_mpi_cmp_mpi( &K
, N
) != 0 )
384 ret
= MBEDTLS_ERR_RSA_KEY_CHECK_FAILED
;
390 * Step 3: Check and 1 < D, E < N if present.
393 if( N
!= NULL
&& D
!= NULL
&& E
!= NULL
)
395 if ( mbedtls_mpi_cmp_int( D
, 1 ) <= 0 ||
396 mbedtls_mpi_cmp_int( E
, 1 ) <= 0 ||
397 mbedtls_mpi_cmp_mpi( D
, N
) >= 0 ||
398 mbedtls_mpi_cmp_mpi( E
, N
) >= 0 )
400 ret
= MBEDTLS_ERR_RSA_KEY_CHECK_FAILED
;
406 * Step 4: Check that D, E are inverse modulo P-1 and Q-1
409 if( P
!= NULL
&& Q
!= NULL
&& D
!= NULL
&& E
!= NULL
)
411 if( mbedtls_mpi_cmp_int( P
, 1 ) <= 0 ||
412 mbedtls_mpi_cmp_int( Q
, 1 ) <= 0 )
414 ret
= MBEDTLS_ERR_RSA_KEY_CHECK_FAILED
;
418 /* Compute DE-1 mod P-1 */
419 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &K
, D
, E
) );
420 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_int( &K
, &K
, 1 ) );
421 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_int( &L
, P
, 1 ) );
422 MBEDTLS_MPI_CHK( mbedtls_mpi_mod_mpi( &K
, &K
, &L
) );
423 if( mbedtls_mpi_cmp_int( &K
, 0 ) != 0 )
425 ret
= MBEDTLS_ERR_RSA_KEY_CHECK_FAILED
;
429 /* Compute DE-1 mod Q-1 */
430 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &K
, D
, E
) );
431 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_int( &K
, &K
, 1 ) );
432 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_int( &L
, Q
, 1 ) );
433 MBEDTLS_MPI_CHK( mbedtls_mpi_mod_mpi( &K
, &K
, &L
) );
434 if( mbedtls_mpi_cmp_int( &K
, 0 ) != 0 )
436 ret
= MBEDTLS_ERR_RSA_KEY_CHECK_FAILED
;
443 mbedtls_mpi_free( &K
);
444 mbedtls_mpi_free( &L
);
446 /* Wrap MPI error codes by RSA check failure error code */
447 if( ret
!= 0 && ret
!= MBEDTLS_ERR_RSA_KEY_CHECK_FAILED
)
449 ret
+= MBEDTLS_ERR_RSA_KEY_CHECK_FAILED
;
455 int mbedtls_rsa_deduce_crt( const mbedtls_mpi
*P
, const mbedtls_mpi
*Q
,
456 const mbedtls_mpi
*D
, mbedtls_mpi
*DP
,
457 mbedtls_mpi
*DQ
, mbedtls_mpi
*QP
)
461 mbedtls_mpi_init( &K
);
466 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_int( &K
, P
, 1 ) );
467 MBEDTLS_MPI_CHK( mbedtls_mpi_mod_mpi( DP
, D
, &K
) );
473 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_int( &K
, Q
, 1 ) );
474 MBEDTLS_MPI_CHK( mbedtls_mpi_mod_mpi( DQ
, D
, &K
) );
477 /* QP = Q^{-1} mod P */
480 MBEDTLS_MPI_CHK( mbedtls_mpi_inv_mod( QP
, Q
, P
) );
484 mbedtls_mpi_free( &K
);
489 #endif /* MBEDTLS_RSA_C */