7
$\begingroup$

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?

$\endgroup$
2
  • $\begingroup$ What is 'd' that you have mentioned? $\endgroup$ Commented May 14, 2012 at 9:37
  • $\begingroup$ The $d$ is the RSA private exponent. Have a look at any exposition on RSA encryption for more details. $\endgroup$ Commented May 15, 2012 at 2:34

1 Answer 1

11
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ Can you explain how you arrived at this (nice) solution? What was the motivation? $\endgroup$ Commented Feb 22, 2012 at 16:54
  • 1
    $\begingroup$ @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. $\endgroup$ Commented Feb 22, 2012 at 17:44
  • $\begingroup$ Thanks. I had never seen this attack on $n$ when we know $e$ and $d$. $\endgroup$ Commented Feb 22, 2012 at 23:05

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.