RSA (CONTINUED): WHEN THE EXPONENT IS LEAKED

MATH 195

We prove the following fact:

Claim. There is a fact algorithm that given n > 1 odd and given m ∈ ℤ_{>0} satisfying

∀a ∈ (ℤ/nℤ)^{∗} : a^{m} = 1,

‘in practice’ factors n completely into primes.

We do so via factoring by means of square roots of 1. Suppose that we have a nonstupid way of generating elements x ∈ ℤ/nℤ such that x^{2} = 1 (mod n) (i.e. x ≠ 1, −1). Namely, x^{2} ≡ 1 (mod n) implies that

n | (x^{2} − 1) = (x + 1)(x − 1)

so n | gcd(n, x+1) gcd(n, x−1). Since x ≠ 1, −1, this ‘in practice’ gives a nontrivial factorization of n.

Example. For n = 35, x = 29 gives 26^{2} = 841 ≡ 1 (mod 35), and indeed

35 = n | gcd(35, 30) gcd(35, 28) = 5 · 7.

Theorem. Suppose n is a positive odd integer. Then

#{x ∈ ℤ/nℤ : x^{2} ≡ 1 (mod n)} = 2^{t}

where t is the number of distinct prime factors of n.

The proof of this involves the Chinese remainder theorem. Factor for example n = 45 = 3^{2} · 5. The roots are then the unique solutions to x ≡ ±1 (mod 3) and x ≡ ±1 (mod 5). For example, x ≡ 1 (mod 3), x ≡ 1 (mod 5) gives x ≡ 1 (mod 45), whereas x ≡ 1 (mod 3) and x ≡ −1 (mod 5) gives x ≡ 19 (mod 45) and 19^{2} = 361 ≡ 1 (mod 45).

Here, then, is the algorithm in the claim.

(1) Write m = 2^{k} · u where u is odd and k ≥ 1. [Note: m is even, take a = −1.]

(2) Pick a ∈ ℤ/nℤ, a ≠ 0, at random.

(3) Compute a^{u} ∈ ℤ/nℤ. If a^{u} ≡ 1, pronounce failure and go back to the previous step.

(4) [Suppose a^{u} ≠ 1.] By repeated squarings, compute a^{2u} = (a^{u})^{2}, a^{2^{2}u} = (a^{2u})^{2}, and so on, until for the first time we have a^{2^{i}u} = 1. [Note: If a ∈ (ℤ/nℤ)^{∗} then this happens for i = k and maybe earlier.]

(5) Put x = a^{2^{i−1}u}. [Note i ≥ 1.] [Then x ≠ 1, x^{2} = 1.] If x = −1, pronounce failure and go back to (2).

(6) [Now x ≠ −1.] Compute gcd(n, x + 1) = n_{+}, gcd(n, x − 1) = n_{−}. Then n = n_{+}n_{−} is a nontrivial factorization, and n_{+} and n_{−} can be factored recursively. [With the same m.] (7) If no i < k can be found in (4), then compute gcd(a, n) [it is > 1 and < n]

This is some of the material covered March 5, in Math 195: Cryptography, taught by Hendrik Lenstra, prepared by John Voight jvoight@math.berkeley.edu.

and factor gcd(a, n) and n/ gcd(a, n) recursively.

(8) If ‘many’ choices of a lead to failure in (3) or (5), then ‘most likely’ n is of the form p^{ℓ} with p prime and ℓ ≥ 1.

The heuristics in (8) are explained by the following theorem:

Theorem. Suppose n has at least 2 distinct (odd) prime factors (so t ≥ 2). Then the number of a ∈ ℤ/nℤ such that a ≠ 0, a leads to failure in (3) or (5) above has

\frac{#\{a ∈ ℤ/nℤ : a ≠ 0, a fails\}}{n − 1} < \frac{1}{2}.