Factoring $n$ Given $d$

In this section, we show that finding the decryption key $d$ for an RSA cryptosystem is, in practice, at least as difficult as factoring $n$ . We give a probabilistic algorithm that given a decryption key determines the factorization of $n$ .

Consider an RSA cryptosystem with modulus $n$ and encryption key $e$ . Suppose we somehow finding an integer $d$ such that

$$a^{ed} \equiv a\pmod{n}$$

for all $a$ . Then $m=ed-1$ satisfies $a^m\equiv 1\pmod{n}$ for all $a$ that are coprime to $n$ . As we saw in Section 3.3.1, knowing $\varphi (n)$ leads directly to a factorization of $n$ . Unfortunately, knowing $d$ does not seem to lead easily to a factorization of $n$ . However, there is a probabilistic procedure that, given an $m$ such that $a^m\equiv 1\pmod{n}$ , will find a factorization of $n$ with ``high probability'' (we will not analyze the probability here).

Algorithm 3.3 (Probabilistic Algorithm to Factor $n$ )   Let $n=pq$ be the product of two distinct odd primes, and suppose $m$ is an integer such that $a^m\equiv 1\pmod{n}$ for all $a$ coprime to $n$ . This probabilistic algorithm factors $n$ with ``high probability''. In the steps below, $a$ always denotes an integer coprime to $n=pq$ .

1. [Divide out powers of 2] If $m$ is even and $a^{m/2}\equiv 1\pmod{n}$ for several randomly chosen $a$ , set $m=m/2$ , and go to step 1, otherwise let $a$ be such that $a^{m/2}\not \equiv 1\pmod{n}$ .
2. [Compute GCD] Choose a random $a$ and compute $g=\gcd(a^{m/2}-1,n)$ .
3. [Terminate?] If $g$ is a proper divisor of $n$ , output $g$ and terminate. Otherwise go to step 2.

Before giving the proof we introduce some more terminology from algebra.

Definition 3.3 (Group Homomorphism)   Let $G$ and $H$ be groups. A map $\varphi :G\to H$ is a group homomorphism if for all $a,b\in G$ we have $\varphi (ab) = \varphi (a) \varphi (b)$ . A group homomorphism is called surjective if for every $c\in H$ there is $a\in G$ such that $\varphi (a) = c$ . The kernel of a group homomorphism $\varphi :G\to H$ is the set $\ker(\varphi )$ of elements $a\in G$ such that $\varphi (a) = 1$ . A group homomorphism is injective if $\ker(\varphi ) = \{1\}$ .

Definition 3.3 (Subgroup)   If $G$ is a group and $H$ is a subset of $G$ , then $H$ is a subgroup if $H$ is a group under the group operation on $G$ .

For example, if $\varphi :G\to H$ is a group homomorphism, then $\ker(\varphi )$ is a subgroup of $G$ (see Exercise 2.21).

We now return to discussing Algorithm 3.3.5. In step 1, note that $m$ is even since $(-1)^m\equiv 1\pmod{n}$ , so it makes sense to consider $m/2$ . It is not practical to determine whether or not $a^{m/2}\equiv 1\pmod{n}$ for all $a$ , because it would require doing a computation for too many $a$ . Instead, we try a few random $a$ ; if $a^{m/2}\equiv 1\pmod{n}$ for the $a$ we check, we divide $m$ by $2$ . Also note that if there exists even a single $a$ such that $a^{m/2}\not \equiv 1\pmod{n}$ , then half the $a$ have this property, since then $a\mapsto a^{m/2}$ is a surjective homomorphism $(\mathbb{Z}/n\mathbb{Z}{})^*\rightarrow \{\pm 1\}$ and the kernel has index $2$ .

Proposition 2.5.3 implies that if $x^2\equiv 1\pmod{p}$ then $x=\pm 1\pmod{p}$ . In step 2, since $(a^{m/2})^2 \equiv 1\pmod{n}$ , we also have $(a^{m/2})^2 \equiv 1\pmod{p}$ and $(a^{m/2})^2 \equiv 1\pmod{q}$ , so $a^{m/2}\equiv \pm 1\pmod{p}$ and $a^{m/2}\equiv \pm 1\pmod{q}$ . Since $a^{m/2}\not \equiv 1\pmod{n}$ , there are three possibilities for these signs, so with probability $2/3$ , one of the following two possibilities occurs:

1.      $$a^{m/2}\equiv +1\pmod{p}$$   and$\qquad a^{m/2}\equiv -1\pmod{q}$
2.      $$a^{m/2}\equiv -1\pmod{p}$$   and$\qquad a^{m/2}\equiv +1\pmod{q}.$

The only other possibility is that both signs are $-1$ . In the first case,

$$p\mid a^{m/2}-1$$   but$$\qquad q\nmid a^{m/2}-1,$$

so $\gcd(a^{m/2}-1,pq) = p,$ and we have factored $n$ . Similarly, in the second case, $\gcd(a^{m/2}-1,pq) = q,$ and we again factor $n$ .

Example 3.3   Somehow we discover that the RSA cryptosystem with

$$n=32295194023343$$   and$$\qquad e=29468811804857$$

has decryption key $d= 11127763319273$ . We use this information and Algorithm 3.3.5 to factor $n$ . If

$$m = ed-1 = 327921963064646896263108960,$$

then $\varphi (pq)\mid m$ , so $a^m\equiv 1\pmod{n}$ for all $a$ coprime to $n$ . For each $a\leq 20$ we find that $a^{m/2}\equiv 1\pmod{n}$ , so we replace $m$ by

$$\frac{m}{2}= 163960981532323448131554480.$$

Again, we find with this new $m$ that for each $a\leq 20$ , $a^{m/2}\equiv 1\pmod{n}$ , so we replace $m$ by $81980490766161724065777240$ . Yet again, for each $a\leq 20$ , $a^{m/2}\equiv 1\pmod{n}$ , so we replace $m$ by $40990245383080862032888620$ . This is enough, since $2^{m/2} \equiv 4015382800099\pmod{n}$ . Then

$$\gcd(2^{m/2}-1,n) = \gcd(4015382800098,32295194023343) = 737531,$$

and we have found a factor of $n$ . Dividing, we find that

$$n = 737531 \cdot 43788253.$$

SAGE Example 3.3   We implement Algorithm 3.3.5 in SAGE.

sage: def crack_given_decrypt(n, m):
...    n = Integer(n); m = Integer(m);  # some type checking
...    # Step 1: divide out powers of 2
...    while True:
...        if is_odd(m): break
...        divide_out = True
...        for i in range(5):
...           a = randrange(1,n)
...           if gcd(a,n) == 1:
...              if Mod(a,n)^(m//2) != 1:
...                  divide_out = False
...                  break
...        if divide_out:
...            m = m//2
...        else:
...            break
...    # Step 2: Compute GCD
...    while True:
...        a = randrange(1,n)
...        g = gcd(lift(Mod(a, n)^(m//2)) - 1, n)
...        if g != 1 and g != n:
...            return g
...

We show how to verify Example 3.3.8 using SAGE.

sage: n=32295194023343; e=29468811804857; d=11127763319273
sage: crack_given_decrypt(n, e*d - 1)
737531
sage: factor(n)
737531 * 43788253

We try a much larger example.

sage: e = 22601762315966221465875845336488389513
sage: d = 31940292321834506197902778067109010093
sage: n = 268494924039590992469444675130990465673
sage: p = crack_given_decrypt(n, e*d - 1)
sage: p   # random output (could be other prime divisor)
13432418150982799907
sage: n % p
0