This is the latest in a series of blog posts to address the list of '52 Things Every PhD Student Should Know To Do Cryptography': a set of questions compiled to give PhD candidates a sense of what they should know by the end of their first year. In this blog post we discuss a possible attack on RSA-CRT.
Note: This follows the paper by Dan Boneh, Richard A. DeMillo, Richard J. Lipton: On the importance of Eliminating Errors in Cryptographic Computations.
In the 52 Things: Number 21 blog post, it discusses how the Chinese Remainder theorem method can improve the performance of RSA. Here we show that if the hardware (or software) used to implement RSA produces errors or faults from time to time, then an attack can be used to break RSA with high probability.
RSA[1] was one of the first practical public key cryptosystems used for secure data transmission. Developed by Rivest, Shamir and Adleman in 1977, it is based on the difficulty of factoring the product of two large prime numbers. Direct attacks on RSA involve trying to factorise the modulus. Boneh, DeMillo and Lipton wanted to find an attack on RSA that avoids directly factoring the modulus. They show that erroneous cryptographic values jeopardise security by enabling an attacker to expose secret information. We are going to look specifically at the attack on RSA-CRT.
First, a brief description of RSA. Formally, let $N=pq$ be the product of two large prime numbers each $\frac{n}{2}$ bits long. If we have a message $x \in \mathbb{Z}_N$, we encrypt the message using a secret signing exponent $d$ by $S=x^d \textrm{ mod } N$. The modular exponentiation of $x$ is computationally expensive. For a more efficient implementation we can first compute $S_1 = x^d \textrm{ mod } p$ and $S_2 = x^d \textrm{ mod } q$, then use the Chinese Remainder Theorem (CRT)[2] to construct the signature $S = x^d \textrm{ mod } N$.
It can be shown that this RSA with CRT scheme is particularly susceptible to software or hardware errors. If we contain two signatures of the same message. One signature being the correct one, the other the faulty signature. Once again, letting $x \in \mathbb{Z}_N$ be the message and $S = x^d \textrm{ mod } N$ being the correct signature. Then $\hat{S}$ be a faulty signature. From above, $S$ is computed by first finding $S_1$ and $S_2$. Similarly, $\hat{S}$ is computed by first finding $\hat{S}_1$ and $\hat{S}_2$, suppose that the error occurred while computing only one of $\hat{S_1}, \hat{S_2}$. If we assume the fault occurred while computing $\hat{S}_1$ but no error occurred during the computation of $\hat{S}_2$, i.e. $S_1 \neq \hat{S}_1 \textrm{ mod } p$ and $\hat{S}_2 = S_2$ This means that $S = \hat{S} \textrm{ mod } q$ but $S \neq \hat{S} \textrm{ mod }p$. Therefore, $$ \textrm{gcd}(S - \hat{S}, N) = q $$ so N can be factored easily. This shows that with one faulty signature, the modulus N can be easily factored.
Note: This follows the paper by Dan Boneh, Richard A. DeMillo, Richard J. Lipton: On the importance of Eliminating Errors in Cryptographic Computations.
In the 52 Things: Number 21 blog post, it discusses how the Chinese Remainder theorem method can improve the performance of RSA. Here we show that if the hardware (or software) used to implement RSA produces errors or faults from time to time, then an attack can be used to break RSA with high probability.
RSA[1] was one of the first practical public key cryptosystems used for secure data transmission. Developed by Rivest, Shamir and Adleman in 1977, it is based on the difficulty of factoring the product of two large prime numbers. Direct attacks on RSA involve trying to factorise the modulus. Boneh, DeMillo and Lipton wanted to find an attack on RSA that avoids directly factoring the modulus. They show that erroneous cryptographic values jeopardise security by enabling an attacker to expose secret information. We are going to look specifically at the attack on RSA-CRT.
First, a brief description of RSA. Formally, let $N=pq$ be the product of two large prime numbers each $\frac{n}{2}$ bits long. If we have a message $x \in \mathbb{Z}_N$, we encrypt the message using a secret signing exponent $d$ by $S=x^d \textrm{ mod } N$. The modular exponentiation of $x$ is computationally expensive. For a more efficient implementation we can first compute $S_1 = x^d \textrm{ mod } p$ and $S_2 = x^d \textrm{ mod } q$, then use the Chinese Remainder Theorem (CRT)[2] to construct the signature $S = x^d \textrm{ mod } N$.
It can be shown that this RSA with CRT scheme is particularly susceptible to software or hardware errors. If we contain two signatures of the same message. One signature being the correct one, the other the faulty signature. Once again, letting $x \in \mathbb{Z}_N$ be the message and $S = x^d \textrm{ mod } N$ being the correct signature. Then $\hat{S}$ be a faulty signature. From above, $S$ is computed by first finding $S_1$ and $S_2$. Similarly, $\hat{S}$ is computed by first finding $\hat{S}_1$ and $\hat{S}_2$, suppose that the error occurred while computing only one of $\hat{S_1}, \hat{S_2}$. If we assume the fault occurred while computing $\hat{S}_1$ but no error occurred during the computation of $\hat{S}_2$, i.e. $S_1 \neq \hat{S}_1 \textrm{ mod } p$ and $\hat{S}_2 = S_2$ This means that $S = \hat{S} \textrm{ mod } q$ but $S \neq \hat{S} \textrm{ mod }p$. Therefore, $$ \textrm{gcd}(S - \hat{S}, N) = q $$ so N can be factored easily. This shows that with one faulty signature, the modulus N can be easily factored.
[1] - http://en.wikipedia.org/wiki/RSA_(cryptosystem)
[2] - http://en.wikipedia.org/wiki/Chinese_remainder_theorem
No comments:
Post a Comment