蒙哥馬利乘法與 CR T
我試圖了解如何在 RSA 私鑰操作中使用蒙哥馬利乘法： $ X \equiv a^{e} \pmod{n} $ 在哪裡 $ a $ 是消息， $ e $ 是指數， $ n $ 是模數。
使用來自Montgomery Reduction的算法（使用 $ r=2^k $ ， 在哪裡 $ k $ 是模數的位長 $ n $ ):
ModExp(a; e; n) { n is an odd number } Step 1. Compute n' using the extended Euclid algorithm. Step 2. a_hat := a*r (mod n) Step 3. x_hat := 1*r (mod n) Step 4. for i = k-1 down to 0 do Step 5. x_hat := MonPro(x_hat; x_hat) Step 6. if e(i) = 1 then x_hat := MonPro(a_hat; x_hat) Step 7. x := MonPro(x_hat; 1) Step 8. return x MonPro(a_hat;b_hat) Step 1. t := a_hat*b_hat Step 2. m := t*n' (mod r) Step 3. u := (t + m*n)/r Step 4. if u >= n then return u-n else return u現在，模數 $ n $ 在 RSA 中總是很奇怪，因為它是從滿足第一個要求的素數生成的。另外，據我了解，為了使蒙哥馬利形式成為可能，底座的尺寸 $ a $ 一定是 $ a < n $ . 幸運的是，在 RSA 中，這也適用，因為消息/簽名不能長於模數。
但是，這就是我卡住的地方。我通過將模冪運算替換為加速版本，將硬體加速添加到預先存在的 RSA 庫 (mbedTLS) 中。只要不使用中國剩餘定理，它就可以很好地工作。我還沒有完全掌握 CRT，但我知道它允許我們通過將消息分成兩個操作並縮小模數大小來執行更快的解密：
$$ 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 $$
取自：中國剩餘定理和RSA
問題是，消息長度現在比模數長 $ p $ 和 $ q $ . 所以現在，這將違反蒙哥馬利形式的要求，即 $ (aR)*mod(N) $ , $ a $ 一定是 $ a < N $ .
我已經到處搜尋了一種進行蒙哥馬利模冪運算的方法，以防 $ a > N $ ，但他們都表示輸入 $ a $ 小於 $ N $ . 我似乎無法理解如何使用輸入大小比模數更大的蒙哥馬利形式來執行 modexp。
我在想也許你可以分塊 $ a $ 成二元組 $ bitlen(N) $ 有某種進位進入下一組，但我不知道你將如何在進行平方的內循環中混合。是否可以對其進行修改，使其變為：
modexp(a[0:len(n)], e, n) ... modexp(a[len(n):len(a)], e, n)並以某種方式將它們組合成一個 len(n) 的輸出？我真的迷失在理解它背後的數學。
問題是，消息長度現在比模數長 $ p $ 和 $ q $
這不是真的。在裡面 $ p $ 跟踪，你在提高 $ M \bmod p $ 對權力 $ d \bmod p-1 $ ; 我們有 $ M \bmod p < p $ ; 也就是說，我們取冪的值小於 $ p $ ，作為蒙托馬利乘法的結果。以同樣的方式， $ q $ track 也滿足了那方面的要求，所以一切正常。