第三十三个知识点：Bellcore攻击是如何攻击使用CRT的RSA的?

注意：这篇博客是由follow论密码计算中消除错误的重要性（On the importance of Eliminating Errors in Cryptographic Computations.）这篇论文。作者是Dan Boneh，Richard A. DeMillo,，Richard J. Lipton。

在52件事里，第21篇博客中，讨论了中国剩余定理如何提升RSA性能的问题。这里我们展示如果一个被用于实现RSA的硬件时不时的产生一些错误，那么有一个高概率成功的攻击攻破RSA。

RSA[1]是第一个用于安全数据传输的实用公钥密码系统。RSA在1977年被Rivest，Shamir和Adleman提出。他是基于分解两个大素数的困难性问题。（其实不是，需要更紧的问题。）对RSA的直接攻击包括试图分解模数。Boneh, DeMillo和Lipton想找到一种攻击RSA的方法来避免直接分解模量。它们表明，错误的密码值会让攻击者暴露秘密信息，从而危及安全。我们主要看一看对RSA-CRT的攻击。

首先给出RSA简要的描述。正式的，让\(N = pq\)是两个大素数的产生，每一个n/2bit长。如果我们有一个消息\(x \in Z_N\)，我们加密消息使用一个密钥\(d\)，通过\(S = x^d \mod N\)。\(x\) 模指数运算代价很高。为了一个有效率的实现，我们使用中国剩余定理(CRT)[2]。我们先计算\(S_1 = x^d \mod p\)然后计算\(S_2 = x^d \mod q\)，然后使用中国剩余定理构造\(S = x^d \mod N\)。

可以看出，这种带有CRT方案的RSA特别容易出现软件或硬件错误。如果我们有两个签名，一个是正确的签名，一个是错误的签名。另外，我们让\(x \in Z_N\)是消息，然后\(S = x^d \mod N\)是正确的签名。然后\(\hat{S}\)是错误的签名。现在\(S\)先被\(S_1\)和\(S_2\) 计算。相似的\(\hat{S}\)也会首先计算\(\hat{S_1}\)和\(\hat{S_2}\)，假设错误只会发生在两个变量中的一个，如果我们假设错误发生在\(\hat{S_1}\)中，但是没有发生在\(\hat{S_2}\)中。例如\(S_1 \neq \hat{S_1} \mod p\)同时\(S_2 = \hat{S_2}\)。这意味着\(S = \hat{S} \mod q\)，但是\(S \neq \hat{S} \mod p\)。因此，
\[ gcd(S-\hat{S},N) = q \]
因此N就被轻易的分解了。这表明，一个错误的签名，模N可以很容易分解。

[1] - http://en.wikipedia.org/wiki/RSA_(cryptosystem)

[2] - http://en.wikipedia.org/wiki/Chinese_remainder_theorem