2.5 RSA 密碼系統

　　RSA加密演算法是一種非對稱加密演算法。在公鑰加密標準和電子商業中RSA被廣泛使用。RSA是1977年由羅納德·李維斯特（Ron Rivest）、阿迪·薩莫爾（Adi Shamir）和倫納德·阿德曼（Leonard Adleman）一起提出的。當時他們三人都在麻省理工學院工作。RSA就是他們三人姓氏開頭字母拼在一起組成的。

1973年，在英國政府通訊總部工作的數學家克利福德·柯克斯（Clifford Cocks）在一個內部文件中提出了一個相應的演算法，但他的發現被列入機密，一直到1997年才被發表。

　　對極大整數做因數分解的難度決定了RSA演算法的可靠性。換言之，對一極大整數做因數分解愈困難，RSA演算法愈可靠。假如有人找到一種快速因數分解的演算法的話，那麼用RSA加密的信息的可靠性就肯定會極度下降。但找到這樣的演算法的可能性是非常小的。今天只有短的RSA鑰匙才可能被強力方式解破。到2008年為止，世界上還沒有任何可靠的攻擊RSA演算法的方式。只要其鑰匙的長度足夠長，用RSA加密的信息實際上是不能被解破的。但在分布式計算和量子計算機理論日趨成熟的今天，RSA加密安全性受到了挑戰。

系統說明如下：

1.  選兩個大質數P1、P2  得N= P1xP2    

選e 使(Ø(N),e) =1 (互質)

    　N、e 為公開鑰匙

2. 找d   使 d≡e^-1    mod Ø(N)   其中Ø(N)=(P-1) (q-1)

   　 d為祕密鑰匙

3.加密過程：

　 C≡M^e    mod N   其中C為密文 (Ciphertext)

                         M為明文 (Plaintext)

4.解密過程：

   C^d≡M    mod N



補充: 
　　RSA簽章法為第一個提出具有訊息回復(message recovery)功能的數位簽章法。此外，RSA的加密與簽署動作正好相反。用接收方的公鑰來加密，用自己的私鑰來解密；用自己的私鑰來簽署；用簽署者的公鑰來驗證簽章。為了增加安全度，訊息簽署前可以先經過一個單向雜湊函數h的轉換再進行簽署。

證明：C^d≡M    mod N

已知C≡M^e    mod N　

C^d≡(M^e )^d   mod N　

因ed≡1   modØ(N)

得ed = kØ(N) +1 

C^d≡M^{e d}   mod N　
C^d≡M^{kØ(N) +1}    mod N　
C^d≡M^kØ(N)  xM  mod N　

其中M^kØ(N) ≡1  mod N

得C^d≡M  mod N    故得證




系統圖如下：

例題：已知明文M為688   p為47   q為71  N=3337

解：

　　選e =79　　　使得d≡e^-1    mod Ø(N) 得d為1019

   

    加密： C≡688⁷⁹ ≡1570   mod 3337

    解密： M≡1570¹⁰¹⁹           mod 3337

    　可得 M=688