第三十三个知识点：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 eq hat{S_1} mod p)同时(S_2 = hat{S_2})。这意味着(S = hat{S} mod q)，但是(S eq hat{S} mod p)。因此，
因此N就被轻易的分解了。这表明，一个错误的签名，模N可以很容易分解。
[1] - http://en.wikipedia.org/wiki/RSA_(cryptosystem)
[2] - http://en.wikipedia.org/wiki/Chinese_remainder_theorem