5  *  SPDX-License-Identifier: Apache-2.0 OR GPL-2.0-or-later
21  * Setting F := lcm(P-1,Q-1), the idea is as follows:
25  *     square roots of 1 in Z/PZ and Z/QZ are +1 and -1, this leaves the four
26  *     possibilities X^(F/2) = (+-1, +-1). If it happens that X^(F/2) = (-1,+1)
27  *     or (+1,-1), then gcd(X^(F/2) + 1, N) will be equal to one of the prime
31  *     construction still applies since (-)^K is the identity on the set of
34  * The public and private key primitives (-)^E and (-)^D are mutually inverse
35  * bijections on Z/NZ if and only if (-)^(DE) is the identity on Z/NZ, i.e.
36  * if and only if DE - 1 is a multiple of F, say DE - 1 = F * L.
39  *   DE - 1 = FL = (F/2) * (2^(t+1)) * K,
43  *   (DE - 1) >> 1, (DE - 1) >> 2, ..., (DE - 1) >> ord
45  * where ord is the order of 2 in (DE - 1).
51                               mbedtls_mpi const *E, mbedtls_mpi const *D,  in mbedtls_rsa_deduce_primes()  argument
59     uint16_t order;    /* Order of 2 in DE - 1 */  in mbedtls_rsa_deduce_primes()
61     mbedtls_mpi T;  /* Holds largest odd divisor of DE - 1     */  in mbedtls_rsa_deduce_primes()
75     if (P == NULL || Q == NULL || P->p != NULL || Q->p != NULL) {  in mbedtls_rsa_deduce_primes()
80         mbedtls_mpi_cmp_int(D, 1) <= 0 ||  in mbedtls_rsa_deduce_primes()
81         mbedtls_mpi_cmp_mpi(D, N) >= 0 ||  in mbedtls_rsa_deduce_primes()
94     /* T := DE - 1 */  in mbedtls_rsa_deduce_primes()
95     MBEDTLS_MPI_CHK(mbedtls_mpi_mul_mpi(&T, D,  E));  in mbedtls_rsa_deduce_primes()
103     /* After this operation, T holds the largest odd divisor of DE - 1. */  in mbedtls_rsa_deduce_primes()
112     if (N->p[0] % 8 == 1) {  in mbedtls_rsa_deduce_primes()
142                 mbedtls_mpi_cmp_mpi(P, N) == -1) {  in mbedtls_rsa_deduce_primes()
159          * we reached 1, or K holds primes[attempt]^(DE - 1) mod N, which must  in mbedtls_rsa_deduce_primes()
160          * be 1 if D,E,N were consistent.  in mbedtls_rsa_deduce_primes()
162          * yet eventually failing, computations if N,D,E were not sane.  in mbedtls_rsa_deduce_primes()
179  * Given P, Q and the public exponent E, deduce D.
185                                         mbedtls_mpi *D)  in mbedtls_rsa_deduce_private_exponent()  argument
190     if (D == NULL || mbedtls_mpi_cmp_int(D, 0) != 0) {  in mbedtls_rsa_deduce_private_exponent()
203     /* Temporarily put K := P-1 and L := Q-1 */  in mbedtls_rsa_deduce_private_exponent()
207     /* Temporarily put D := gcd(P-1, Q-1) */  in mbedtls_rsa_deduce_private_exponent()
208     MBEDTLS_MPI_CHK(mbedtls_mpi_gcd(D, &K, &L));  in mbedtls_rsa_deduce_private_exponent()
210     /* K := LCM(P-1, Q-1) */  in mbedtls_rsa_deduce_private_exponent()
212     MBEDTLS_MPI_CHK(mbedtls_mpi_div_mpi(&K, NULL, &K, D));  in mbedtls_rsa_deduce_private_exponent()
214     /* Compute modular inverse of E in LCM(P-1, Q-1) */  in mbedtls_rsa_deduce_private_exponent()
215     MBEDTLS_MPI_CHK(mbedtls_mpi_inv_mod(D, E, &K));  in mbedtls_rsa_deduce_private_exponent()
226                            const mbedtls_mpi *D, mbedtls_mpi *DP,  in mbedtls_rsa_deduce_crt()  argument
233     /* DP = D mod P-1 */  in mbedtls_rsa_deduce_crt()
236         MBEDTLS_MPI_CHK(mbedtls_mpi_mod_mpi(DP, D, &K));  in mbedtls_rsa_deduce_crt()
239     /* DQ = D mod Q-1 */  in mbedtls_rsa_deduce_crt()
242         MBEDTLS_MPI_CHK(mbedtls_mpi_mod_mpi(DQ, D, &K));  in mbedtls_rsa_deduce_crt()
245     /* QP = Q^{-1} mod P */  in mbedtls_rsa_deduce_crt()
260                                 const mbedtls_mpi *Q, const mbedtls_mpi *D,  in mbedtls_rsa_validate_params()  argument
278      * rate of at most 2^-100 and we are aiming for the same certainty here as  in mbedtls_rsa_validate_params()
311      * Step 3: Check and 1 < D, E < N if present.  in mbedtls_rsa_validate_params()
314     if (N != NULL && D != NULL && E != NULL) {  in mbedtls_rsa_validate_params()
315         if (mbedtls_mpi_cmp_int(D, 1) <= 0 ||  in mbedtls_rsa_validate_params()
317             mbedtls_mpi_cmp_mpi(D, N) >= 0 ||  in mbedtls_rsa_validate_params()
325      * Step 4: Check that D, E are inverse modulo P-1 and Q-1  in mbedtls_rsa_validate_params()
328     if (P != NULL && Q != NULL && D != NULL && E != NULL) {  in mbedtls_rsa_validate_params()
335         /* Compute DE-1 mod P-1 */  in mbedtls_rsa_validate_params()
336         MBEDTLS_MPI_CHK(mbedtls_mpi_mul_mpi(&K, D, E));  in mbedtls_rsa_validate_params()
345         /* Compute DE-1 mod Q-1 */  in mbedtls_rsa_validate_params()
346         MBEDTLS_MPI_CHK(mbedtls_mpi_mul_mpi(&K, D, E));  in mbedtls_rsa_validate_params()
373                              const mbedtls_mpi *D,  const mbedtls_mpi *DP,  in mbedtls_rsa_validate_crt()  argument
382     /* Check that DP - D == 0 mod P - 1 */  in mbedtls_rsa_validate_crt()
390         MBEDTLS_MPI_CHK(mbedtls_mpi_sub_mpi(&L, DP, D));  in mbedtls_rsa_validate_crt()
399     /* Check that DQ - D == 0 mod Q - 1 */  in mbedtls_rsa_validate_crt()
407         MBEDTLS_MPI_CHK(mbedtls_mpi_sub_mpi(&L, DQ, D));  in mbedtls_rsa_validate_crt()
416     /* Check that QP * Q - 1 == 0 mod P */  in mbedtls_rsa_validate_crt()