25
$\begingroup$

In the public-key system RSA scheme, each user holds beyond a public modulus $m$ a public exponent, $e$, and a private exponent, $d$.

Suppose that Bob's private exponent is learned by other users. Rather than generating a new modulus, Bob decides to generate just a new public and a new private exponent $e'$ and $d'$.

Is this safe for Bob?

$\endgroup$

4 Answers 4

29
$\begingroup$

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:

  1. Compute $k = ed-1$

  2. 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.

  3. Pick a random $x\,|\,2 \leq x < N$

  4. Compute the sequence $s = x^{\frac k 2}, x^{\frac k 4}, \dots, x^{\frac k {2^t}} \pmod{N}$

  5. 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$.

  6. 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.

$\endgroup$
5
  • $\begingroup$ $\phi(N)$ should be replaced with $\:\operatorname{L}\hspace{-0.02 in}\operatorname{cm}(\hspace{.04 in}p\hspace{-0.04 in}-\hspace{-0.05 in}1,q\hspace{-0.04 in}-\hspace{-0.05 in}1)\;$. $\;\;\;$ $\endgroup$
    – user991
    Feb 26, 2014 at 20:49
  • $\begingroup$ @RickyDemer: Several steps of the process rely on Euler's theorem holding, but I'm only aware of that holding for $\phi{N}$. Does it also hold for $Lcm(p−1,q−1)$? This is one part of RSA that I have never quite grokked... $\endgroup$ Feb 27, 2014 at 12:57
  • $\begingroup$ Anyways, nice answer @RobertMason $\endgroup$
    – DrLecter
    Feb 28, 2014 at 17:54
  • $\begingroup$ I've updated it to use $\lambda(N)$ instead of $\phi(N)$ - thanks for the note. $\endgroup$ Feb 28, 2014 at 17:54
  • $\begingroup$ In remove_even(), I understand that t is the exponent of 2 and thus increments each time r is right-shifted. However, is it necessary to compute and return this variable? It is only returned to the calling function and not used within remove_even() or the calling function. $\endgroup$
    – Carl Knox
    Jan 27, 2017 at 16:40
7
$\begingroup$

No, it isn't safe. Knowing the private exponent $d$ (and a corresponding public key) allows factoring the modulus $m$, and this allows retrieving all other private exponents (given the public ones).

Bob should generate a new modulus, this is not that expensive. Also, Bob should revoke his old public key, if it is registered anywhere.

$\endgroup$
3
$\begingroup$

The answer of @robert-mason is good but rather large.

Here is the algorithm and the proof just after.

…

…

Source of the proof here (at the end of part 1).

$\endgroup$
2
  • 1
    $\begingroup$ From which paper did you take that screenshot? (I'm asking, because we tend to cite the source for copyright reasons.) $\endgroup$
    – e-sushi
    Sep 8, 2017 at 11:42
  • 1
    $\begingroup$ I made the content of the first picture and test it on an example, the source of the second picture is at the end of my answer. $\endgroup$ Sep 8, 2017 at 15:20
2
$\begingroup$

There's a much simpler way to factor $n$ when you know $d$ at least when $e$ is small (like when it is usually 65537). You know that $ed = 1 \, (\textrm{mod} \,\phi)$. Since you know $e$ and $d$ you can calculate $S = ed - 1$ and this number must be divisible by $\phi$ due to the first equation. Note that the magnitiude of this value is around 65537 times the modulus (since $d$ is the same magnitude as the modulus). Also note that $\phi$ is of the same magnitude as the modulus. Hence, $S$ must actually a small multiple of $\phi$. So you can simply try divisors $k=1,\ldots,$ until you find one that divides $S$ then try and calculate the "candidate" $\phi' = S/k$. Now from this $\phi'$ you can easily solve for $p$ and $q$ using your knowledge $pq = n$ and $(p-1)(q-1) = \phi'$, just using substitution and the usual formula for quadratic equations. Note that you may have to go through some "wrong" $k$'s (and wrong $\phi'$s), this happens when you hit a $k$ that isn't the true factor but just happens to divide the true factor or perhaps $\phi$ itself - it will divide $S$ but will lead to a wrong $\phi'$. In that case, just continue trying $k$'s because the right one must be less than $ \approx 65537$ so there's not that many to try.

$\endgroup$
3
  • 1
    $\begingroup$ I don't see him saying $\;\; e\hspace{-0.03 in}\cdot \hspace{-0.03 in}d \: \equiv \: 1 \pmod{\phi} \;\;$ anywhere. $\;\;\;\;$ RSA only requires that $\;\; e\hspace{-0.03 in}\cdot \hspace{-0.03 in}d \: \equiv \: 1 \: \pmod{\lambda} \:\:\:$. $\;\;\;\;$ $\endgroup$
    – user991
    Feb 27, 2014 at 1:08
  • $\begingroup$ @Ricky: Not sure what you mean? In my comment, $\phi$ is the size of the multiplicative group modulo $n$, i.e. $\phi = (p-1)(q-1)$ for the standard RSA setup with two primes. In almost all cases in practice, $e$ is fixed at $65537$ and $d$ is taken to be the multiplicative inverse of $e$ modulo $\phi$, that is $ed = 1 \, (\textrm{mod} \, \phi)$ (if it exists - otherwise new primes are generated). $\endgroup$
    – Morty
    Feb 27, 2014 at 4:52
  • 1
    $\begingroup$ I'm saying that one could choose $d$ to be a multiplicative inverse of $e$ modulo $\:\operatorname{L}\hspace{-0.03 in}\operatorname{cm}\hspace{.02 in}(\hspace{.04 in}p\hspace{-0.04 in}-\hspace{-0.05 in}1,q\hspace{-0.04 in}-\hspace{-0.05 in}1)\:$,$\:$ so if your argument requires that they be multiplicative inverses modulo $\phi$, then you should give that as an assumption rather than an automatic fact. $\;\;\;\;$ $\endgroup$
    – user991
    Feb 27, 2014 at 5:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.