中国剩余定理和RSA

#1 楼

好吧，CRT优化背后的想法是，如果我们知道模数$ N $的因式分解（如果我们有私钥，我们可能会分解），那么我们可以将消息$ M $分成两半（一个取模$ p $和一个模$ q $），分别计算每个模，然后重新组合它们。也就是说，我们计算：

$ m_1 =（M ^ d \ bmod N）\ bmod p =（（M \ bmod p）^ {d \ bmod p-1}）\ bmod p $

$ m_2 =（M ^ d \ bmod N）\ bmod q =（（M \ bmod q）^ {d \ bmod q-1}）\ bmod q $

（请注意，指数是对$ p-1 $和$ q-1 $取模；我们可以这样做，因为$ p $和$ q $是质数（也是费马小定理）；这是一个好的源

然后，我们将它们重新组合；也就是说，我们找到一个数字$ m $，这样：

$ m \ equiv（M ^ d \ bmod N）\ mod p $

$ m \ equiv（ M ^ d \ bmod N）\ mod q $

由于中国剩余定理（并且$ p $和$ q $是相对质数的），我们可以立即推断出：

$ m \ equiv（M ^ d \ bmod N）\ mod pq $

这正是我们要计算的内容。

现在，问题您的评论中似乎在询问此重组步骤的详细信息。

现在，实际上很容易看到算法的正确性。为了使最后一步起作用，我们需要证明我们得出了一个这样的值$ m $：

$ 0 \ le m
$ m \ equiv m_1 \ mod p $

$ m \ equiv m_2 \ mod q $

第一个条件$ 0 \ le m
对于第三个条件，这也很简单； $（m_2 +（h * q））\ bmod q = m_2 \ bmod q +（h * q）\ bmod q = m_2 \ bmod q $

第二个是一个小技巧：$（m_2 +（h * q））\ bmod p =（m_2 + q * q_ {inv} *（m_1-m_2）\ bmod p）\ bmod p =（m_2 + q * q_ {inv} *（m_1-m_2））\ bmod p $

现在，将$ q_ \ mathit {inv} $定义为乘以$ q $模$ p所得的数字$，结果为1（即$ q * q_ \ mathit {inv} \ equiv 1 \ mod p $）。现在，由于上面的方程式实际上是对$ p $进行模运算，因此我们可以将$ q * q_ \ mathit {inv} $替换为1，这样可以得到：

$ m \ bmod p =（m_2 + 1 *（m_1-m_2））\ bmod p = m_1 \ bmod p $

QED

评论

---

$ \ begingroup $
这是一个非常不错的详细证明，但我需要更多帮助来理解它：首先，您如何得出此公式：$ M_1 =（M ^ d \ bmod N）\ bmod p =（（ \ bmod p）^ {d \ mod p-1}）\ bmod p $？您能详细说明一下吗？我不明白您是如何应用费马的“小”定理来获得它的。很明显，您如何证明重组步骤的公式，但在这种情况下，我无法理解CRT的工作原理。您如何“立即推断” $ m =（M ^ d \ bmod N）\ mod pq $？
$ \ endgroup $
– Mihai Todor
2012年5月9日18:04

---

$ \ begingroup $
@MihaiTodor：好，对于第一个问题，CRT优化将$ M $分为两部分，$ M \ bmod p $和$ M \ bmod q $。然后，它计算两个半部分的RSA私有运算，即对于p端，我们计算$（（M \ bmod p）^ d）\ bmod p $。我们还注意到$ M ^ d \ equiv（M \ bmod p）^ d \ mod p $，也就是说，双方实际上都是独立的。我们进一步注意到，费马小定理意味着如果$ p $是素数，则$ a ^ b \ equiv a ^ {b \ mod p-1} \ mod p $，因此足以计算$（（M \ bmod p ）^ {d \ mod p-1}）\ bmod p $。
$ \ endgroup $
–雨披
2012年5月9日18:27

---

$ \ begingroup $
@MihaiTodor：关于第二个问题，中国剩余定理指出，如果$ p $和$ q $是相对质数，以及$ A \ equiv B \ mod p $和$ A \ equiv B \ mod q $，然后是$ A \ equiv B \ mod pq $。
$ \ endgroup $
–雨披
2012年5月9日18:29

---

$ \ begingroup $
非常感谢。我可以看到您对这一主题的知识确实很好，但是我正在看两本有关CRT的书籍，而我却看不到您上面介绍的这个简单陈述是如何得出的。 CRT指出存在r个线性同余系统的解决方案，并且是唯一的模n，其中$ n = \ prod_ {i = 0} ^ rn_i $，但是您如何使用它呢？ Wikipedia上的“一般情况”没有帮助：en.wikipedia.org/wiki/Chinese_remainder_theorem#General_case
$ \ endgroup $
– Mihai Todor
2012年5月9日18:48

---

$ \ begingroup $
@MihaiTodor：设置$ r = 2 $，$ n_0 = p $，$ n_1 = q $。现在，CRT说，给定$ B \ bmod p $和$ B \ bmod q $（$ 0 \ le B $ \ endgroup $
–雨披
2012年5月9日18:56

---

#2 楼

真正让我了解RSA-CRT的是JohannGroßschädl的第3节：“中国剩余定理及其在高速RSA加密芯片中的应用” [1]。以下是该部分的摘要。


$ \ newcommand {\ qinv} {q _ {\ text {inv}}} $$
让$ M $作为消息，$ C $密文，$ N = PQ $ RSA模数和$ D $解密密钥。
您不想做的是计算$ C ^ D $，因为$ D $很大，并对$ N $进行模运算，因为$ N $很大。

中国剩余定理（CRT）允许您使用$ M_P $和$ M_Q $定义如下的$ M $：
$$ M_P = M \ bmod P $$
$$ M_Q = M \ bmod Q $$

好是，可以计算$ M_P $和$ M_Q $比$ C ^ D $快得多的方式；实际上：

\开始{对齐}
M_P＆= M \ bmod P \\
＆=（C ^ D \ bmod N）\ bmod P \\
＆= C ^ D \ bmod P＆\ text {（因为$ N = PQ $）} \\
＆= C ^ {D \ bmod（P-1）} \ bmod P＆\ text {（费马小定理）}
\ end {aligned}

让$ D_P = D \ bmod（P-1）$。您可以在密钥生成过程中计算$ D_P $，而在解密过程中计算以下内容：只需$ M_Q $。

实际上，您甚至可以进一步优化：

$$ M_P = C_P ^ {D_P} \ bmod P，\\
\ text {with} C_P = C \ bmod P。$$

现在，我认为大多数解释中缺少的主要内容是：如果您有通用的CRT算法，就可以完成。只要将$ M_P $和$ M_Q $（以及$ P $和$ Q $）提供给CRT算法，您就会得到$ M $。


重新搜索“带CRT的RSA”要比这复杂得多，您还需要计算其他值，例如$ \ qinv $和$ h $等。 />
这些计算与CRT相对应，但是在RSA解密的特殊情况下可以进行优化。
如果使用我们已经介绍的优化方法将通用CRT算法（Wikipedia）应用于RSA解密，则将获得以下信息： 1} \ bmod P）+ C_Q ^ {D_Q} P（P ^ {-1} \ bmod Q））\ bmod N $$

如[1]注意，您可以将此公式转换为使用Fermat的Little定理以更少的运算量计算同一件事： ^ {Q-1} \ bmod Q））\ bmod N $$

带有$ Q ^ {P-1} \ bmod P $和$ P ^ {Q-1} \ bmod Q $可以预先计算。


Wikipedia中给出的算法是不同的，并且我没有逐步说明如何从常规CRT公式中获得该结果。
但是确实如此，正如雨披在他的回答的第二部分中所示，如果您检查的话，它是可行的： ）（M_P-M_Q）\ bmod P）; $$ then

$$ M'\ bmod Q = M_Q ~~~~ \ text {（平凡）} $$

和

\开始{对齐}
M'\ bmod P＆= M_Q \ bmod P +（M_P-M_Q）\ bmod P \\
＆= M_P \ bmod P \\
＆= M_P。
\ end {aligned}

所以$ M'$是$ M $，QED 。

后一种计算$ M $的方法可能比前一种更快，因为您没有前一种方法中存在的最终约简模$ N $。


参考文献

[1] JohannGroßschädl：“中国余数定理及其在高速RSA加密芯片中的应用”。 ACSAC 2000：384-393 https://www.acsac.org/2000/papers/48.pdf（DOI：10.1109/ACSAC.2000.898893；DBLP：conf/acsac/Grossschadl00）

#3 楼

关于以上解释与维基百科的中国剩余定理和各种软件库的特殊应用之间的区别，第二算法在PKCS＃1标准和相关的RFC中给出。

RSA Inc.标准的PDF版本在其参考文献中引用了Garner算法。