I had a similar problem, and it took me a long time to figure out all the math, as some of the proofs can be rather terse. So, I took it upon myself to write a full explanation of how to factor N, without all the symbols and relying on a bit less prior knowledge.
This is an application of the shared modulus attack explained by Boneh in his analysis of RSA attacks.
Anyway, such a system is not safe. If you know a valid $e$ and $d$, you can factor $N$.
Stated more formally, given $(e, d, N)$, where $N = pq$ for some primes $p$ and $q$,
and $ed \equiv 1 \bmod{\lambda(N)}$, one can easily find $p$ and $q$.
Note: $\lambda(N)$ is the Carmichael function. If you're used to seeing RSA described in terms of $\phi(N)$, this is very similar. Carmichael's theorem is a generalization of Euler's theorem stating:
$$\forall a\,|\,\gcd(a,N)=1,\; a^{\lambda(N)} \equiv 1 \pmod{N}$$
where $\lambda(N)$ is the smallest integer that makes this statement true. For $N=pq$, this number is just $\DeclareMathOperator{\lcm}{lcm}\lcm(p-1,q-1)$. It is also true that $\lambda(N)\,|\,\phi(N)$, so the use of $\lambda(N)$ instead of $\phi(N)$ when describing RSA is just a generalization.
First, a few facts. Consider solving the equation:
$$\begin{aligned}
y^2 & \equiv 1 \bmod{N} \\
y^2 - 1 & \equiv 0 \bmod{N} \\
(y+1)(y-1) & \equiv 0 \bmod{N} \\
\end{aligned}$$
i.e. computing the square root of one. Now, note that $p\,|\,N$ and
$q\,|\,N$. Since the zero product property
holds in modular arithmetic when the modulus is prime, it is true that:
$$y \equiv \pm 1 \bmod{p} \;\, \text{and} \;\, y \equiv \pm 1 \bmod{q}$$
Therefore, we know:
$$\begin{aligned}
y \equiv 1 \bmod{p} & \, \text{or} \;\, y \equiv -1 \bmod{p} \\
y \equiv 1 \bmod{q} & \, \text{or} \;\, y \equiv -1 \bmod{q}\end{aligned}$$
This gives two choices of remainder for each factor of N. From this, you
can construct four systems of equations by picking one value from each factor.
Each of these systems of equations has a unique solution modulo $N$ (by
the Chinese Remainder Theorem).
However, not all solutions are created equal. Consider:
$$\begin{aligned}
y & \equiv 1 \bmod{p} \\
y & \equiv 1 \bmod{q}\end{aligned}$$
This has a solution $y = 1$, which is trivial. The solution where both
remainders are $-1$ is also trivial ($y = N - 1$), and is also not
useful. However, now consider the following case:
$$\begin{aligned}
y & \equiv 1 \bmod{p} \\
y & \equiv -1 \bmod{q}\end{aligned}$$
This has a non-trivial solution. Furthermore, if you know this solution,
you can factor $N$ by noting that $y - 1 \equiv 0 \bmod{p}$, so
$p\,|\,y-1$. Since $p\,|\,N$ also, it is easy to find $p$ by computing
$\gcd(y-1, N)$. The same can be said of the symmetric system of
equations swapping $p$ and $q$. Since $p$ and $q$ are interchangeable,
this has the same result.
We also know that any root that is non-trivial (i.e. is not 1 or -1) must
come from one of the two non-trivial cases we looked at because we know that
the solutions to these equations are unique. This means that the above logic
works for any non-trivial root we may find.
Thus, we have fact 1: if $y$ is a non-trivial square root of one modulo
$N$, where $N$ is the product of two primes, one of the factors of $N$
is $\gcd(y-1, N)$.
The second is much simpler:
$$\begin{aligned}
a^b & = c \\
a^{{\frac b 2} + {\frac b 2}} & = c \\
a^{\frac b 2} a^{\frac b 2} & = c \\
(a^{\frac b 2})^2 & = c\end{aligned}$$
This is fact 2: given $a$, $b$, and $c$ such that $a^b = c$, the square root of $c$
is $a^{\frac b 2}$. This is easy to compute as long as b is even (i.e.
$2\,|\,b$).
Now for the actual attack. To begin, note that
$ed - 1 \equiv 0 \bmod{\lambda(N)}$. This value is important, so let
$k = ed - 1$. Because it is congruent to zero, $\lambda(N)\,|\,k$.
Furthermore, $2\,|\,\lambda(N)$, so $2\,|\,k$. Then $k$ can be written in
the form $k = 2^t r$ for some odd number $r$ with $t > 0$.
Then, picking any arbitrary $x$ (i.e. $\forall x\,|\,2 \leq x < N$):
$$x^k \equiv x^{k \, \bmod{\lambda(N)}} \equiv x^0 \equiv 1 \pmod{N}$$
Applying fact 2, we can find the square root of one modulo $N$ by
computing $x^{\frac k 2} \bmod{N}$. There are now several possibilities:
The result is $1$. This is a trivial solution. However, if the
exponent is even then it is possible to try again, dividing the
exponent by two again. If the exponent is odd, then pick a new $x$,
and try the attack again.
The result is $N-1$ i.e. $-1$. This is a trivial solution. Unlike in
the previous case, dividing the exponent by two again will not yield
a square root of one, but rather a square root of negative one.
Thus, pick a new $x$ and try again.
The result is neither of the above. This is a non-trivial solution.
All that remains is to factor $N$ by applying fact 1.
In other words, the algorithm can be stated as:
Compute $k = ed-1$
Determine the exponent of $2$, $t$, in the factorization of $k$,
i.e. factor $k$ into the form $k = 2^t r$ with $t > 0$ and $r$ odd.
Pick a random $x\,|\,2 \leq x < N$
Compute the sequence
$s = x^{\frac k 2}, x^{\frac k 4}, \dots, x^{\frac k {2^t}} \pmod{N}$
Determine the first index $i$ such that $s_i \neq \pm 1$ and
$s_{i-1} = 1$
If no such index exists, choose a new $x$ and try again.
Otherwise, let $p = \gcd(s_i - 1, N)$ and $q = \frac N p$.
Done.
The attack relies on the fact that you can easily generate numbers that
are congruent to one modulo $N$. Additionally, it is easy to take the
square root of these numbers by dividing the exponent by two. There is a
chance that taking this square root yields a non-trivial square root of
one modulo $N$, which allows you to easily compute a factor of $N$ by
using the euclidean algorithm. This is a probabilistic algorithm,
in that it relies on the solution being non-trivial. If no non-trivial
solution is found, the algorithm needs to start over with a new $x$.
The chance of obtaining a non-trivial solution is an important
consideration when using this algorithm. So to determine this
probability, consider an approach which picks random $x$ modulo $N$.
$x^e$ for some exponent $e$, then, is also random. Also note
that, for any given modulus $m$, the set of integers are evenly
distributed modulo $m$ among the set of positive integers less than $m$;
i.e: $$P(x^e \equiv 1 \bmod{m}) = P(x^e \equiv m-1 \equiv -1 \bmod{m})$$
The proof for fact 1 requires the solution of a system of two
equations, each of which is “picked” from two possible equations. There
are four possible systems of equations, and each is equally likely because
of the equal distribution of numbers mod $m$. Therefore,
the probability that the $x$ satisfies any one of these system is
$\frac 1 4 = 25\%$. Since two of these systems yield non-trivial
solutions, the probability of a non-trivial solution given a random $x$
is $50\%$. This probability is improved by continuing to calculate
square roots in the case that $\sqrt{x^e} \equiv 1 \bmod{m}$. However,
since this number is related to the previous number in the sequence, one
can no longer make a strict randomness argument that the next term in
the sequence also has a $50\%$ chance of being non-trivial. You can say,
though, that:
$$P(\exists \, \text{non-trivial solution in $s$}) \geq 50\%$$ for the
definition of $s$ given in the algorithm description above. Therefore,
the generation of a constant, finite number of sequences from random
values of $x$ can provide an arbitrarily high probability of yielding a
non-trivial solution.
Since computation of the entire sequence $s$ does not guarantee a higher
probability of finding a non-trivial solution, it is reasonable to
wonder why you should bother computing the entire sequence. However, it
is easy to get the entire sequence “for free” when computing
$x^{\frac k 2}$. By partially factoring $k$ into $2^t r$, $s$ can be
recursively defined as:
$$\begin{aligned}
s_t & = x^r \\
s_i & = s_{i+1}^2\end{aligned}$$
Note that this recursive definition defines the sequence back-to-front,
so in the process of computing $s_1$, one also computes all other terms
of the sequence. This squaring is the same computation the
pow-mod operation
would do anyway, so there is no added complexity in computing
the additional terms of the sequence.
Here, then, is code (in python) that performs the above partial factorization:
# Returns a tuple (r, t) | n = r*2^t
# Complexity O(lg n)*
def remove_even(n):
if n == 0:
return (0, 0)
r = n
t = 0
while (r & 1) == 0:
t = t + 1
r = r >> 1
return (r, t)
This can be implemented in $\Theta(\lg n)$ time. This implementation
does repetitive shifting, so in the worst case runs in
$\Theta((\lg n)^2)$ time. An implementation could achieve optimal time
by iterating through the bits of $n$ instead of doing repetitive shifts;
however, this is more difficult with python longs so this approach was
used for clarity.
This code will generate terms of the sequence $s$ until it finds a
nontrivial square root of one modulo $N$:
# Returns a non-trivial sqrt(1) mod N, or None
# Arguments:
# x: random integer 2 <= x < N
# k: multiple of lambda(N)
# N: modulus
# Complexity O((lg n)^3)
def get_root_one(x, k, N):
(r, t) = remove_even(k)
oldi = None
i = pow(x, r, N)
while i != 1:
oldi = i
i = (i*i) % N
if oldi == N-1:
return None #trivial
return oldi
In the worst case, this computes $x^k$ using the square-and-multiply
method, which is $O((\lg N)^3)$. As stated earlier, the probability of
the function returning a value (vice ‘None’), is at least $50\%$ for
random $x$.
Finally, here is some code to actually factor the modulus, given a valid
RSA key:
import random
import fractions
# Returns a tuple (p, q) that are
# the prime factors of N, given an
# RSA key (e, d, N)
def factor_rsa(e, d, N):
k = e*d - 1
y = None
while not y:
x = random.randrange(2, N)
y = get_root_one(x, k, N)
p = fractions.gcd(y-1, N)
q = N // p
return (p, q)
This algorithm runs in probabilistic polynomial time (ZPP). For example,
the probability of this algorithm succeeding after 14 iterations or less
is larger than $99.99\%$. Computing $k$ is $O((\lg N)^2)$, the
probabilistic portion is $O((\lg N)^3)$, and the euclidean algorithm to
compute the greatest common divisor is $O((\lg N)^3)$ as well.
Therefore, the entire algorithm will run in (probabilistic)
$O((\lg N)^3)$ time.
Finally, here is an example of running this algorithm to factor an RSA
modulus:
# A 98 and 99 bit prime.
p = 633825300114114700748351602573
q = 316912650057057350374175800819
N = p*q
print("RSA Modulus (p,q, N):")
print((p, q, N))
# A valid keypair mod N
e = 262139
d = 9451846527955896036458759652560972624637617897909079398699
print("Factoring N...")
print(rsa.factor_rsa(e, d, N))
This runs quite quickly, and demonstrates the algorithm does correctly
factor N. Note that the order of the factors changes from run to run,
depending on which root is found first. The order of the two factors
does not matter, though, so this is algorithm is sufficient for the
purposes of attacking a shared modulus cryptosystem.
To return to the original problem, if Bob shares his first private key,
and all his keys share a modulus, then Mallory can factor the modulus
using this algorithm. Once
the modulus is factored, she can compute $\phi(N)=(p-1)(q-1)$. With
knowledge of $\phi(N)$, computing the modular multiplicative inverse of
the other public keys (i.e. the corresponding private keys) is a simple
application of the extended euclidean algorithm.