RSA算法實現

$$ m^{ed} \equiv m \bmod n $$ $ n =pq $ ，所以根據中國剩餘定理它等價於 $$ m^{ed} \equiv m \bmod 𝑝, m^{ed} \equiv m \bmod q $$ 在哪裡 $ n=p\cdot q $

那麼根據中國剩餘定理，2 是如何從 1 得出的呢？我知道中文算法，但是怎麼做 $ m^{ed} \equiv m \bmod p $ 和 $ q $ 來？

觀察任何 $ n $ , $ l $ ， 只要 $ l | n $ , 任何等價物 $ a \equiv b \pmod n $ 還擁有mod $ l $ : $ a \equiv b \pmod l $ . 要完全看到這一點，我們可以寫

$$ \begin{align*} a &\equiv b \pmod n \ \Leftrightarrow \ a &= b + kn \&=b + ktl \quad(\text{since } l|n\text{, so } n = tl)\ \Rightarrow\ a &\equiv b \pmod l \end{align*} $$

所以你可以解決 $ m^e \pmod p \equiv a $ 和 $ m^e \pmod q \equiv b $ , 然後用CRT得到 $ m \pmod n $ .

正如上面提到的@fgrieu，

• CRT 聲明：如果 m 和 n 是兩個整數，使得 gcd(m,n)=1 那麼我們有

-$$ { f: Z_{mn} -> Z_m \cdot Z_n} $$ 被定義為 $ {f(x)=(x mod m, x mod n)} $ 是環同構

-$$ {Phi(mn)=Phi(m)Phi(n)} $$

引用自：https://crypto.stackexchange.com/questions/86790