lcsig/EUCLID-ATTACK

An application of Euclidean algorithm in cryptanalysis of RSA

EUCLID-ATTACK

An implementation of EuclidAttack. Which is An application of Euclidean algorithm in cryptanalysis of RSA.

It computes the factorization of n in deterministic time O((log n)²) bit operations. In the case where the public exponent (e) has the same order of magnitude as (n) and one of the integers k = (ed − 1)/ϕ(n) and (e − k) is < n^0.25.

Theorem

1. Let p and q be two odd primes of the same bit-size L and n = pq.

2. Consider positive integers e, d with 1 < e, d < ϕ(n) such that ed ≡ 1 (mod ϕ(n)). Then (n, e) is the public key and d the private key for an RSA cryptosystem.

3. Set a = (n + 1) mod e and Δ = gcd(e, a).

4. The extended Euclidean algorithm for e and a gives integers q_i > 0 (i = 1, . . . , m) and r_i (i = 0, . . . , m + 1) such that

   1. r₀ = e
   2. r₁ = a
   3. r_m = Δ
   4. r_m+1 = 0
   5. and r_{i - 1} = r_i*q_i + r_{i + 1}, 0 < r_{i + 1} < r_i.

5. Further, there are integers s_i, t_i with |t_i| < e/r_{i - 1} and |s_i| < a/r_{i - 1} satisfying s_ie + at_i = r_i , (i = 2, . . . , m + 1).

6. Set μ_i = gcd(t_i, r_i) and t'_i = t_i/μ_i (i = 0, . . . , m + 1).

7. Let e > n/c, where c is an integer ≥ 1, and k = (ed−1)/ϕ(n).

8. Suppose that k or e−k is ≤ e^0.25/6c^0.5. Then, we have

   1. Δ < e^3/4.
   2. k = |t'_j| and p+q = (a +|t'_j|^-1) mod e, where j is such that r_j is the largest remainder < e^3/4.
   3. Or k = e − |t'_j| and p + q = (a + (e − |t'_j|) −1 ) mod e, where j is such that r_j is the largest remainder < e^3/4.

Algorithm

Input: An RSA public key (n, e) with e > n/c (Read the paper for more info about c). Output: The primes p and q.

1. Compute a = (n + 1) mod e.
2. Using the extended Euclidean algorithm for e and a, compute the biggest remainder r_j among them which are < e^3/4 and the associated integers s_j , t_j such that s_je + at_j = r_j.
3. Compute μ_j = gcd(t_j , r_j) and next t'_j = t_j/μ_j.
4. Compute B₁ = (a + |t'_j|^-1) mod e and next the solutions u₁ and v₁ of equation [X² + B₁X + n = 0]. If u₁ and v₁ are positive integers, then output (u₁ , v₁). Otherwise, go to the next step.
5. Compute B₂ = (a + (e − |t'_j|)^-1) mod e and next the solutions u₂ and v₂ of equation [X² + B₂X + n = 0]. If u₂ and v₂ are positive integers, then output (u₂ , v₂). Otherwise, output FAIL.

Paper

Poulakis, Dimitrios. (2020). An application of Euclidean algorithm in cryptanalysis of RSA. Elemente der Mathematik. 75. 114-120. 10.4171/EM/411.