I am trying to understand the Boneh-DeMillo-Lipton fault attack on RSA CRT signature.

Suppose that we sign a message $m$ with RSA-CRT :

$d_p = d \bmod (p-1)$ and $d_q = d \bmod (q-1)$

$s_p = h(m)^{d_p} \bmod p$ and $s_q \not= h(m)^{d_q} \bmod q$ where $h$ is a hash function

By CRT we get $s$ the signature modulo $n=pq$

I don't understand the following assertion :

As $s^e \equiv h(m) \pmod p$ but $s^e \not \equiv h(m) \pmod q$ we can factorize $n$ by $p=GCD(s^e - h(m), n)$.

Can somebody explain to me why $p$ is the greatest common divisor between $s^e - h(m)$ and $n$?


1 Answer 1


$q$ does not divide $s^e-h(m)$, but $p$ does, so since the gcd must divide both $s^e-h(m)$ and $n$ it's $p$. To be even more explicit, we know that $p$ divides both $s^e-h(m)$ and $n$. The only larger divisor of $n$ that is also divisible by $p$ is $n$ itself, but if $n$ would divide $s^e-h(m)$, then $q$ would also divide $s^e-h(m)$, which we already assumed does not hold.


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.