Lines Matching full:1
21 * Setting F := lcm(P-1,Q-1), the idea is as follows:
23 * (a) For any 1 <= X < N with gcd(X,N)=1, we have X^F = 1 modulo N, so X^(F/2)
24 * is a square root of 1 in Z/NZ. Since Z/NZ ~= Z/PZ x Z/QZ by CRT and the
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
32 * roots of 1 in Z/NZ.
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).
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()
80 mbedtls_mpi_cmp_int(D, 1) <= 0 || in mbedtls_rsa_deduce_primes()
82 mbedtls_mpi_cmp_int(E, 1) <= 0 || in mbedtls_rsa_deduce_primes()
94 /* T := DE - 1 */ in mbedtls_rsa_deduce_primes()
96 MBEDTLS_MPI_CHK(mbedtls_mpi_sub_int(&T, &T, 1)); in mbedtls_rsa_deduce_primes()
103 /* After this operation, T holds the largest odd divisor of DE - 1. */ in mbedtls_rsa_deduce_primes()
110 /* Skip trying 2 if N == 1 mod 8 */ in mbedtls_rsa_deduce_primes()
112 if (N->p[0] % 8 == 1) { in mbedtls_rsa_deduce_primes()
113 attempt = 1; in mbedtls_rsa_deduce_primes()
119 /* Check if gcd(K,N) = 1 */ in mbedtls_rsa_deduce_primes()
121 if (mbedtls_mpi_cmp_int(P, 1) != 0) { in mbedtls_rsa_deduce_primes()
125 /* Go through K^T + 1, K^(2T) + 1, K^(4T) + 1, ... in mbedtls_rsa_deduce_primes()
131 for (iter = 1; iter <= order; ++iter) { in mbedtls_rsa_deduce_primes()
132 /* If we reach 1 prematurely, there's no point in mbedtls_rsa_deduce_primes()
134 if (mbedtls_mpi_cmp_int(&K, 1) == 0) { in mbedtls_rsa_deduce_primes()
138 MBEDTLS_MPI_CHK(mbedtls_mpi_add_int(&K, &K, 1)); in mbedtls_rsa_deduce_primes()
141 if (mbedtls_mpi_cmp_int(P, 1) == 1 && in mbedtls_rsa_deduce_primes()
142 mbedtls_mpi_cmp_mpi(P, N) == -1) { in mbedtls_rsa_deduce_primes()
152 MBEDTLS_MPI_CHK(mbedtls_mpi_sub_int(&K, &K, 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()
164 if (mbedtls_mpi_cmp_int(&K, 1) != 0) { in mbedtls_rsa_deduce_primes()
194 if (mbedtls_mpi_cmp_int(P, 1) <= 0 || in mbedtls_rsa_deduce_private_exponent()
195 mbedtls_mpi_cmp_int(Q, 1) <= 0 || in mbedtls_rsa_deduce_private_exponent()
203 /* Temporarily put K := P-1 and L := Q-1 */ in mbedtls_rsa_deduce_private_exponent()
204 MBEDTLS_MPI_CHK(mbedtls_mpi_sub_int(&K, P, 1)); in mbedtls_rsa_deduce_private_exponent()
205 MBEDTLS_MPI_CHK(mbedtls_mpi_sub_int(&L, Q, 1)); in mbedtls_rsa_deduce_private_exponent()
207 /* Temporarily put D := gcd(P-1, Q-1) */ in mbedtls_rsa_deduce_private_exponent()
210 /* K := LCM(P-1, Q-1) */ in mbedtls_rsa_deduce_private_exponent()
214 /* Compute modular inverse of E in LCM(P-1, Q-1) */ in mbedtls_rsa_deduce_private_exponent()
233 /* DP = D mod P-1 */ in mbedtls_rsa_deduce_crt()
235 MBEDTLS_MPI_CHK(mbedtls_mpi_sub_int(&K, P, 1)); in mbedtls_rsa_deduce_crt()
239 /* DQ = D mod Q-1 */ in mbedtls_rsa_deduce_crt()
241 MBEDTLS_MPI_CHK(mbedtls_mpi_sub_int(&K, Q, 1)); in mbedtls_rsa_deduce_crt()
245 /* QP = Q^{-1} mod P */ in mbedtls_rsa_deduce_crt()
272 * Step 1: If PRNG provided, check that P and Q are prime in mbedtls_rsa_validate_params()
298 * Step 2: Check that 1 < N = P * Q in mbedtls_rsa_validate_params()
303 if (mbedtls_mpi_cmp_int(N, 1) <= 0 || in mbedtls_rsa_validate_params()
311 * Step 3: Check and 1 < D, E < N if present. in mbedtls_rsa_validate_params()
315 if (mbedtls_mpi_cmp_int(D, 1) <= 0 || in mbedtls_rsa_validate_params()
316 mbedtls_mpi_cmp_int(E, 1) <= 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()
329 if (mbedtls_mpi_cmp_int(P, 1) <= 0 || in mbedtls_rsa_validate_params()
330 mbedtls_mpi_cmp_int(Q, 1) <= 0) { in mbedtls_rsa_validate_params()
335 /* Compute DE-1 mod P-1 */ in mbedtls_rsa_validate_params()
337 MBEDTLS_MPI_CHK(mbedtls_mpi_sub_int(&K, &K, 1)); in mbedtls_rsa_validate_params()
338 MBEDTLS_MPI_CHK(mbedtls_mpi_sub_int(&L, P, 1)); in mbedtls_rsa_validate_params()
345 /* Compute DE-1 mod Q-1 */ in mbedtls_rsa_validate_params()
347 MBEDTLS_MPI_CHK(mbedtls_mpi_sub_int(&K, &K, 1)); in mbedtls_rsa_validate_params()
348 MBEDTLS_MPI_CHK(mbedtls_mpi_sub_int(&L, Q, 1)); in mbedtls_rsa_validate_params()
382 /* Check that DP - D == 0 mod P - 1 */ in mbedtls_rsa_validate_crt()
389 MBEDTLS_MPI_CHK(mbedtls_mpi_sub_int(&K, P, 1)); in mbedtls_rsa_validate_crt()
399 /* Check that DQ - D == 0 mod Q - 1 */ in mbedtls_rsa_validate_crt()
406 MBEDTLS_MPI_CHK(mbedtls_mpi_sub_int(&K, Q, 1)); in mbedtls_rsa_validate_crt()
416 /* Check that QP * Q - 1 == 0 mod P */ in mbedtls_rsa_validate_crt()
424 MBEDTLS_MPI_CHK(mbedtls_mpi_sub_int(&K, &K, 1)); in mbedtls_rsa_validate_crt()