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