Take the 2-minute tour ×

We know that exposing $p$, or $q$ or $\phi(n)$ results in trivial attacks on RSA since they allow us to factor $n$ and to compute the private exponent $d$.

In OpenSSL (and most RSA implementations) decryption is done via the CRT, so we store $n$ and $d$, but also store $d \bmod (p-1)$ and $d \bmod (q-1)$ as CRT exponents. Suppose these leaked... is there a practical attack?

share|improve this question
What is 'd' that you have mentioned? –  Ashwin May 14 '12 at 9:37
The $d$ is the RSA private exponent. Have a look at any exposition on RSA encryption for more details. –  Fixee May 15 '12 at 2:34

1 Answer 1

up vote 10 down vote accepted

Yes, there is a practical attack. Leaking those (or even just one of those) allows us to factor the modulus quite efficiently.

Suppose the attacker knows the values $n$, $e$ (the public exponent) and the value of $d \bmod (p-1)$ (which we will call $dp$).

Then, the attacker selects a value $m$, and then computes:

$gcd( n, m ^ {e \cdot dp-1} - 1 \bmod n)$

To see why this is likely to give us a nontrivial factor of $n$, let us consider the value of $m ^ {e \cdot dp-1} \bmod p$ (which we can do, even if we don't know the value of p). We see that this is:

$m ^ {e \cdot dp-1} \bmod p = 1$

This is because $e \cdot dp = 1 \mod (p-1)$ (and Fermat's Little Theorem).

In contrast, this same value modulo q is (with high probability, assuming $m$ was selected randomly) not 1, and so $m ^ {e \cdot dp-1} - 1 \bmod n$ will have $p$ as a factor, but not $q$. And thus,

$gcd( n, m ^ {e \cdot dp-1} - 1 \bmod n) = p$

with high probability.

share|improve this answer
Can you explain how you arrived at this (nice) solution? What was the motivation? –  Fixee Feb 22 '12 at 16:54
@Fixee: well, the standard way to factor n given the values d and e is to consider the value $m^{e \cdot d - 1} \bmod n$. Now, given the full d, that's 1 (and so for that attack given the full d, we actually look at $m^{(e \cdot d - 1) / k}$ where k are various powers of 2). However, given a partial d ($dp$), we can still consider how $m ^ {e \cdot dp - 1}$ behaves; once we consider that, the attack becomes obvious. –  poncho Feb 22 '12 at 17:44
Thanks. I had never seen this attack on $n$ when we know $e$ and $d$. –  Fixee Feb 22 '12 at 23:05

Your Answer


