ReactOS 0.4.15-dev-8348-gc1b9bb5
rsa_internal.c
Go to the documentation of this file.
1/*
2 * Helper functions for the RSA module
3 *
4 * Copyright The Mbed TLS Contributors
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 */
47
48#if !defined(MBEDTLS_CONFIG_FILE)
49#include "mbedtls/config.h"
50#else
51#include MBEDTLS_CONFIG_FILE
52#endif
53
54#if defined(MBEDTLS_RSA_C)
55
56#include "mbedtls/rsa.h"
57#include "mbedtls/bignum.h"
59
60/*
61 * Compute RSA prime factors from public and private exponents
62 *
63 * Summary of algorithm:
64 * Setting F := lcm(P-1,Q-1), the idea is as follows:
65 *
66 * (a) For any 1 <= X < N with gcd(X,N)=1, we have X^F = 1 modulo N, so X^(F/2)
67 * is a square root of 1 in Z/NZ. Since Z/NZ ~= Z/PZ x Z/QZ by CRT and the
68 * square roots of 1 in Z/PZ and Z/QZ are +1 and -1, this leaves the four
69 * possibilities X^(F/2) = (+-1, +-1). If it happens that X^(F/2) = (-1,+1)
70 * or (+1,-1), then gcd(X^(F/2) + 1, N) will be equal to one of the prime
71 * factors of N.
72 *
73 * (b) If we don't know F/2 but (F/2) * K for some odd (!) K, then the same
74 * construction still applies since (-)^K is the identity on the set of
75 * roots of 1 in Z/NZ.
76 *
77 * The public and private key primitives (-)^E and (-)^D are mutually inverse
78 * bijections on Z/NZ if and only if (-)^(DE) is the identity on Z/NZ, i.e.
79 * if and only if DE - 1 is a multiple of F, say DE - 1 = F * L.
80 * Splitting L = 2^t * K with K odd, we have
81 *
82 * DE - 1 = FL = (F/2) * (2^(t+1)) * K,
83 *
84 * so (F / 2) * K is among the numbers
85 *
86 * (DE - 1) >> 1, (DE - 1) >> 2, ..., (DE - 1) >> ord
87 *
88 * where ord is the order of 2 in (DE - 1).
89 * We can therefore iterate through these numbers apply the construction
90 * of (a) and (b) above to attempt to factor N.
91 *
92 */
94 mbedtls_mpi const *E, mbedtls_mpi const *D,
96{
97 int ret = 0;
98
99 uint16_t attempt; /* Number of current attempt */
100 uint16_t iter; /* Number of squares computed in the current attempt */
101
102 uint16_t order; /* Order of 2 in DE - 1 */
103
104 mbedtls_mpi T; /* Holds largest odd divisor of DE - 1 */
105 mbedtls_mpi K; /* Temporary holding the current candidate */
106
107 const unsigned char primes[] = { 2,
108 3, 5, 7, 11, 13, 17, 19, 23,
109 29, 31, 37, 41, 43, 47, 53, 59,
110 61, 67, 71, 73, 79, 83, 89, 97,
111 101, 103, 107, 109, 113, 127, 131, 137,
112 139, 149, 151, 157, 163, 167, 173, 179,
113 181, 191, 193, 197, 199, 211, 223, 227,
114 229, 233, 239, 241, 251
115 };
116
117 const size_t num_primes = sizeof( primes ) / sizeof( *primes );
118
119 if( P == NULL || Q == NULL || P->p != NULL || Q->p != NULL )
121
122 if( mbedtls_mpi_cmp_int( N, 0 ) <= 0 ||
123 mbedtls_mpi_cmp_int( D, 1 ) <= 0 ||
124 mbedtls_mpi_cmp_mpi( D, N ) >= 0 ||
125 mbedtls_mpi_cmp_int( E, 1 ) <= 0 ||
126 mbedtls_mpi_cmp_mpi( E, N ) >= 0 )
127 {
129 }
130
131 /*
132 * Initializations and temporary changes
133 */
134
135 mbedtls_mpi_init( &K );
137
138 /* T := DE - 1 */
141
142 if( ( order = (uint16_t) mbedtls_mpi_lsb( &T ) ) == 0 )
143 {
145 goto cleanup;
146 }
147
148 /* After this operation, T holds the largest odd divisor of DE - 1. */
150
151 /*
152 * Actual work
153 */
154
155 /* Skip trying 2 if N == 1 mod 8 */
156 attempt = 0;
157 if( N->p[0] % 8 == 1 )
158 attempt = 1;
159
160 for( ; attempt < num_primes; ++attempt )
161 {
162 mbedtls_mpi_lset( &K, primes[attempt] );
163
164 /* Check if gcd(K,N) = 1 */
166 if( mbedtls_mpi_cmp_int( P, 1 ) != 0 )
167 continue;
168
169 /* Go through K^T + 1, K^(2T) + 1, K^(4T) + 1, ...
170 * and check whether they have nontrivial GCD with N. */
172 Q /* temporarily use Q for storing Montgomery
173 * multiplication helper values */ ) );
174
175 for( iter = 1; iter <= order; ++iter )
176 {
177 /* If we reach 1 prematurely, there's no point
178 * in continuing to square K */
179 if( mbedtls_mpi_cmp_int( &K, 1 ) == 0 )
180 break;
181
182 MBEDTLS_MPI_CHK( mbedtls_mpi_add_int( &K, &K, 1 ) );
184
185 if( mbedtls_mpi_cmp_int( P, 1 ) == 1 &&
186 mbedtls_mpi_cmp_mpi( P, N ) == -1 )
187 {
188 /*
189 * Have found a nontrivial divisor P of N.
190 * Set Q := N / P.
191 */
192
194 goto cleanup;
195 }
196
197 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_int( &K, &K, 1 ) );
198 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &K, &K, &K ) );
200 }
201
202 /*
203 * If we get here, then either we prematurely aborted the loop because
204 * we reached 1, or K holds primes[attempt]^(DE - 1) mod N, which must
205 * be 1 if D,E,N were consistent.
206 * Check if that's the case and abort if not, to avoid very long,
207 * yet eventually failing, computations if N,D,E were not sane.
208 */
209 if( mbedtls_mpi_cmp_int( &K, 1 ) != 0 )
210 {
211 break;
212 }
213 }
214
216
217cleanup:
218
219 mbedtls_mpi_free( &K );
221 return( ret );
222}
223
224/*
225 * Given P, Q and the public exponent E, deduce D.
226 * This is essentially a modular inversion.
227 */
229 mbedtls_mpi const *Q,
230 mbedtls_mpi const *E,
231 mbedtls_mpi *D )
232{
233 int ret = 0;
234 mbedtls_mpi K, L;
235
236 if( D == NULL || mbedtls_mpi_cmp_int( D, 0 ) != 0 )
238
239 if( mbedtls_mpi_cmp_int( P, 1 ) <= 0 ||
240 mbedtls_mpi_cmp_int( Q, 1 ) <= 0 ||
241 mbedtls_mpi_cmp_int( E, 0 ) == 0 )
242 {
244 }
245
246 mbedtls_mpi_init( &K );
248
249 /* Temporarily put K := P-1 and L := Q-1 */
252
253 /* Temporarily put D := gcd(P-1, Q-1) */
255
256 /* K := LCM(P-1, Q-1) */
259
260 /* Compute modular inverse of E in LCM(P-1, Q-1) */
262
263cleanup:
264
265 mbedtls_mpi_free( &K );
267
268 return( ret );
269}
270
271/*
272 * Check that RSA CRT parameters are in accordance with core parameters.
273 */
275 const mbedtls_mpi *D, const mbedtls_mpi *DP,
276 const mbedtls_mpi *DQ, const mbedtls_mpi *QP )
277{
278 int ret = 0;
279
280 mbedtls_mpi K, L;
281 mbedtls_mpi_init( &K );
283
284 /* Check that DP - D == 0 mod P - 1 */
285 if( DP != NULL )
286 {
287 if( P == NULL )
288 {
290 goto cleanup;
291 }
292
296
297 if( mbedtls_mpi_cmp_int( &L, 0 ) != 0 )
298 {
300 goto cleanup;
301 }
302 }
303
304 /* Check that DQ - D == 0 mod Q - 1 */
305 if( DQ != NULL )
306 {
307 if( Q == NULL )
308 {
310 goto cleanup;
311 }
312
316
317 if( mbedtls_mpi_cmp_int( &L, 0 ) != 0 )
318 {
320 goto cleanup;
321 }
322 }
323
324 /* Check that QP * Q - 1 == 0 mod P */
325 if( QP != NULL )
326 {
327 if( P == NULL || Q == NULL )
328 {
330 goto cleanup;
331 }
332
333 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &K, QP, Q ) );
334 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_int( &K, &K, 1 ) );
336 if( mbedtls_mpi_cmp_int( &K, 0 ) != 0 )
337 {
339 goto cleanup;
340 }
341 }
342
343cleanup:
344
345 /* Wrap MPI error codes by RSA check failure error code */
346 if( ret != 0 &&
349 {
351 }
352
353 mbedtls_mpi_free( &K );
355
356 return( ret );
357}
358
359/*
360 * Check that core RSA parameters are sane.
361 */
363 const mbedtls_mpi *Q, const mbedtls_mpi *D,
364 const mbedtls_mpi *E,
365 int (*f_rng)(void *, unsigned char *, size_t),
366 void *p_rng )
367{
368 int ret = 0;
369 mbedtls_mpi K, L;
370
371 mbedtls_mpi_init( &K );
373
374 /*
375 * Step 1: If PRNG provided, check that P and Q are prime
376 */
377
378#if defined(MBEDTLS_GENPRIME)
379 /*
380 * When generating keys, the strongest security we support aims for an error
381 * rate of at most 2^-100 and we are aiming for the same certainty here as
382 * well.
383 */
384 if( f_rng != NULL && P != NULL &&
385 ( ret = mbedtls_mpi_is_prime_ext( P, 50, f_rng, p_rng ) ) != 0 )
386 {
388 goto cleanup;
389 }
390
391 if( f_rng != NULL && Q != NULL &&
392 ( ret = mbedtls_mpi_is_prime_ext( Q, 50, f_rng, p_rng ) ) != 0 )
393 {
395 goto cleanup;
396 }
397#else
398 ((void) f_rng);
399 ((void) p_rng);
400#endif /* MBEDTLS_GENPRIME */
401
402 /*
403 * Step 2: Check that 1 < N = P * Q
404 */
405
406 if( P != NULL && Q != NULL && N != NULL )
407 {
409 if( mbedtls_mpi_cmp_int( N, 1 ) <= 0 ||
410 mbedtls_mpi_cmp_mpi( &K, N ) != 0 )
411 {
413 goto cleanup;
414 }
415 }
416
417 /*
418 * Step 3: Check and 1 < D, E < N if present.
419 */
420
421 if( N != NULL && D != NULL && E != NULL )
422 {
423 if ( mbedtls_mpi_cmp_int( D, 1 ) <= 0 ||
424 mbedtls_mpi_cmp_int( E, 1 ) <= 0 ||
425 mbedtls_mpi_cmp_mpi( D, N ) >= 0 ||
426 mbedtls_mpi_cmp_mpi( E, N ) >= 0 )
427 {
429 goto cleanup;
430 }
431 }
432
433 /*
434 * Step 4: Check that D, E are inverse modulo P-1 and Q-1
435 */
436
437 if( P != NULL && Q != NULL && D != NULL && E != NULL )
438 {
439 if( mbedtls_mpi_cmp_int( P, 1 ) <= 0 ||
440 mbedtls_mpi_cmp_int( Q, 1 ) <= 0 )
441 {
443 goto cleanup;
444 }
445
446 /* Compute DE-1 mod P-1 */
448 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_int( &K, &K, 1 ) );
451 if( mbedtls_mpi_cmp_int( &K, 0 ) != 0 )
452 {
454 goto cleanup;
455 }
456
457 /* Compute DE-1 mod Q-1 */
459 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_int( &K, &K, 1 ) );
462 if( mbedtls_mpi_cmp_int( &K, 0 ) != 0 )
463 {
465 goto cleanup;
466 }
467 }
468
469cleanup:
470
471 mbedtls_mpi_free( &K );
473
474 /* Wrap MPI error codes by RSA check failure error code */
476 {
478 }
479
480 return( ret );
481}
482
483int mbedtls_rsa_deduce_crt( const mbedtls_mpi *P, const mbedtls_mpi *Q,
484 const mbedtls_mpi *D, mbedtls_mpi *DP,
485 mbedtls_mpi *DQ, mbedtls_mpi *QP )
486{
487 int ret = 0;
488 mbedtls_mpi K;
489 mbedtls_mpi_init( &K );
490
491 /* DP = D mod P-1 */
492 if( DP != NULL )
493 {
496 }
497
498 /* DQ = D mod Q-1 */
499 if( DQ != NULL )
500 {
503 }
504
505 /* QP = Q^{-1} mod P */
506 if( QP != NULL )
507 {
509 }
510
511cleanup:
512 mbedtls_mpi_free( &K );
513
514 return( ret );
515}
516
517#endif /* MBEDTLS_RSA_C */
#define N
Definition: crc32.c:57
unsigned short int uint16_t
Definition: acefiex.h:54
Multi-precision integer library.
int mbedtls_mpi_sub_mpi(mbedtls_mpi *X, const mbedtls_mpi *A, const mbedtls_mpi *B)
Perform a signed subtraction of MPIs: X = A - B.
int mbedtls_mpi_sub_int(mbedtls_mpi *X, const mbedtls_mpi *A, mbedtls_mpi_sint b)
Perform a signed subtraction of an MPI and an integer: X = A - b.
int mbedtls_mpi_add_int(mbedtls_mpi *X, const mbedtls_mpi *A, mbedtls_mpi_sint b)
Perform a signed addition of an MPI and an integer: X = A + b.
int mbedtls_mpi_is_prime_ext(const mbedtls_mpi *X, int rounds, int(*f_rng)(void *, unsigned char *, size_t), void *p_rng)
Miller-Rabin primality test.
#define MBEDTLS_ERR_MPI_BAD_INPUT_DATA
Definition: bignum.h:66
int mbedtls_mpi_exp_mod(mbedtls_mpi *X, const mbedtls_mpi *A, const mbedtls_mpi *E, const mbedtls_mpi *N, mbedtls_mpi *_RR)
Perform a sliding-window exponentiation: X = A^E mod N.
int mbedtls_mpi_div_mpi(mbedtls_mpi *Q, mbedtls_mpi *R, const mbedtls_mpi *A, const mbedtls_mpi *B)
Perform a division with remainder of two MPIs: A = Q * B + R.
int mbedtls_mpi_lset(mbedtls_mpi *X, mbedtls_mpi_sint z)
Store integer value in MPI.
int mbedtls_mpi_cmp_mpi(const mbedtls_mpi *X, const mbedtls_mpi *Y)
Compare two MPIs.
int mbedtls_mpi_mod_mpi(mbedtls_mpi *R, const mbedtls_mpi *A, const mbedtls_mpi *B)
Perform a modular reduction. R = A mod B.
void mbedtls_mpi_init(mbedtls_mpi *X)
Initialize an MPI context.
size_t mbedtls_mpi_lsb(const mbedtls_mpi *X)
Return the number of bits of value 0 before the least significant bit of value 1.
int mbedtls_mpi_mul_mpi(mbedtls_mpi *X, const mbedtls_mpi *A, const mbedtls_mpi *B)
Perform a multiplication of two MPIs: X = A * B.
#define MBEDTLS_MPI_CHK(f)
Definition: bignum.h:74
int mbedtls_mpi_inv_mod(mbedtls_mpi *X, const mbedtls_mpi *A, const mbedtls_mpi *N)
Compute the modular inverse: X = A^-1 mod N.
void mbedtls_mpi_free(mbedtls_mpi *X)
This function frees the components of an MPI context.
int mbedtls_mpi_cmp_int(const mbedtls_mpi *X, mbedtls_mpi_sint z)
Compare an MPI with an integer.
int mbedtls_mpi_shift_r(mbedtls_mpi *X, size_t count)
Perform a right-shift on an MPI: X >>= count.
int mbedtls_mpi_gcd(mbedtls_mpi *G, const mbedtls_mpi *A, const mbedtls_mpi *B)
Compute the greatest common divisor: G = gcd(A, B)
#define D(d)
Definition: builtin.c:4557
#define NULL
Definition: types.h:112
#define P(row, col)
static const WCHAR E[]
Definition: oid.c:1253
static void cleanup(void)
Definition: main.c:1335
GLuint GLdouble GLdouble GLint GLint order
Definition: glext.h:11194
#define T
Definition: mbstring.h:31
#define L(x)
Definition: ntvdm.h:50
This file provides an API for the RSA public-key cryptosystem.
#define MBEDTLS_ERR_RSA_KEY_CHECK_FAILED
Definition: rsa.h:77
#define MBEDTLS_ERR_RSA_BAD_INPUT_DATA
Definition: rsa.h:74
Context-independent RSA helper functions.
int mbedtls_rsa_deduce_private_exponent(mbedtls_mpi const *P, mbedtls_mpi const *Q, mbedtls_mpi const *E, mbedtls_mpi *D)
Compute RSA private exponent from prime moduli and public key.
int 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)
Check validity of core RSA parameters.
int mbedtls_rsa_deduce_primes(mbedtls_mpi const *N, mbedtls_mpi const *E, mbedtls_mpi const *D, mbedtls_mpi *P, mbedtls_mpi *Q)
Compute RSA prime moduli P, Q from public modulus N=PQ and a pair of private and public key.
int 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)
Generate RSA-CRT parameters.
int 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)
Check validity of RSA CRT parameters.
Configuration options (set of defines)
MPI structure.
Definition: bignum.h:211
mbedtls_mpi_uint * p
Definition: bignum.h:214
int ret