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

2.4 Euler’s theorm

Euler’s theorm

a^p-1≡1  mod p    其中p為質數     1<a<p

   

General Version of Euler’s theorm

aØ(N) ≡1   mod N    其中 N為正整數   1<a<N

Ø(N)為Euler function   即小於N且與N互質的整數個數

例如：
   Ø(5):4    (1、2、3、4)

   Ø(8):4    (1、3、5、7)

   Ø(10):4    (1、3、7、9)

   Ø(11):10    (1、2、3、4、5、6、7、8、9、10)

由以上可以得到

(1)   Ø(P) = P-1    其中P為質數

(2)   Ø(N)=(P-1) (q-1)     其中p、q為相異質數  N=p xq

證明：　　

         N=p xq

　　小於N與N不互質的正整數為 p、2p、3p..、(q-1)p  共(q-1)個

　　                                                   q、2q、3q..、(p-1)q  共(p-1)個

        小於N與N互質的正整數個數

         (N-1)-(p-1)-(q-) = pq-1-p-q+2 =(P-1) (q-1)

     Ø(N)=(P-1) (q-1)

2.3 Rabin’s Crypto System

※使用二次剩餘的近代密碼系統

系統說明如下：

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

公開N  保留P1、P2

2.      加密過程：

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

                                          M為明文 (Plaintext)

3. 解密過程：

   M≡C^(P1+1)/4   mod P1

   M≡C^(P2+1)/4   mod P2

 利用中國餘式定理 解出M

                     

例題：給定p為19  q為23  得N為 437   明文M為30

解：

　　加密

C≡M² ≡900≡26   mod 437

   解密

M²≡26   mod 19

M²≡26   mod 23

M²≡7   mod 19

M²≡3   mod 23

得

M≡+- 11   mod 19

M≡+- 16   mod 23

由上結果可知分別有四組可能

(1)

M≡11   mod 19

M≡16   mod 23

(2)

M≡11   mod 19

M≡-16   mod 23

(3)

M≡-11   mod 19

M≡16   mod 23

(4)

M≡- 11   mod 19

M≡- 16   mod 23

解第(1)組

M≡11   mod 19

M≡16   mod 23

M≡(23xa1x11+19xa2x16)    mod437

其中 4a1≡1  mod19

     19a2≡1  mod23  得 a1=5  a2=-6   帶入

M≡23x5x11+19x(-6)x16     mod437

M≡-559    mod437

M≡315    mod437  ---(1)

解第(2)組

M≡11   mod 19

M≡-16   mod 23

M≡(23xa1x11+19xa2x7)    mod437

其中 4a1≡1  mod19

     19a2≡1  mod23  得 a1=5  a2=-6   帶入

M≡23x5x11+19x(-6)x7     mod437

M≡467    mod437

M≡30   mod437  ---(2)

解第(3)組

M≡-11   mod 19

M≡16   mod 23

M≡(23xa1x8+19xa2x16)    mod437

其中 4a1≡1  mod19

     19a2≡1  mod23  得 a1=5  a2=-6   帶入

M≡23x5x8+19x(-6)x16     mod437

M≡-904   mod437

M≡407   mod437  ---(3)

解第(4)組

M≡-11   mod 19

M≡-16   mod 23

M≡(23xa1x8+19xa2x7)    mod437

其中 4a1≡1  mod19

     19a2≡1  mod23  得 a1=5  a2=-6   帶入

M≡23x5x8+19x(-6)x7     mod437

M≡122    mod437  ---(4)

由四組答案可知第(2)組M≡30   mod437  ---(2) 符合!!!!

2.2 單向函數與單向暗門函數

定義：一函數為f:x→y  稱為單向 1.對每一個x屬於x，其映像y:f(x) 容易取得 2.對每一個y屬於Y，其反映像:x:x  s.t x:f-1(x) 幾乎無法取得

單向函數 (one-way function)

單向暗門函數 (one-way trapdoor function)

	定義：一函數為f:x→y  稱為單向 1.他是單向函數 2.對每一個y屬於Y，其反映像:x:x  s.t x:f-1(x) 容易取得   若運用相對應的暗門u

 

單向函數例子有:

1.單字以第一個字母為首
2.國字以第一個注音符號為首

2.1 密碼學之分類與比較

密碼學系統通常可以根據三種不同的觀點來分類：

一、將明文轉換為密文所使用運算方法上的差異：

(1)取代(substitution)

(2)置換(transposition)

(3)相乘(product)

二、使用金鑰個數的差異：

(1)私密鑰匙(secret-key)，或傳統加密系統

(2)非對稱性或公開鑰匙加密系統

(3)雜湊(HASH)

三、處理明文方法上的差異：

(1)資料區段加密法(block cipher)

(2)資料流加密法(stream cipher)

第一大類-運算方法上的差異

(1)取代(substitution)

取代指的是明文中的每一個元素都被對應到另一個元素。

(2)置換(transposition)

置換是將明文中的元素重新排列。

(3)相乘(Product)

以取代與置換為基礎構成的複雜組合，以達到更複雜的相乘效果。

第二大類-金鑰個數的差異

(1)對稱性密碼學

加密與解密使用同一把金鑰稱之，又稱為單一或私密鑰匙(secret-key)，或傳統加密系統。

(2)非對稱性或公開鑰匙加密系統

加密與解密使用一對金鑰稱之

(3)不需要金鑰的加密技術稱為雜湊(HASH)

第三大類-處理明文方法的差異

(1)資料區段加密法(block cipher)

將明文分成數個n個字元或位元的區段，並且對每一個區段資料應用相同的演算法則和鑰匙，數學式表示為(M為明文，分割成M1、M2… Mn區段)

如E(M,K)=E(M1,K)E(M2,K)… ..E(Mn,K)

(2)資料流加密法(stream cipher)

資料流加密並不會將明文切分為區段，而是一次加密資料流的一個位元或是位元組。常見的作法是將較短的加密鑰匙延展成為無限長、近似亂碼的一長

串金鑰串流(keystream)，再將金鑰串流和原始資料（plain text）經過XOR運算後，產生密文資料（cipher text）。

比較對稱性密碼學與非對稱性密碼學

對稱性密碼學又稱為傳統或秘密金鑰(Symmetric Encryption)

(1)訊息的加密和解密採用相同的金鑰

(2)需要傳送和接收雙方均擁有相同的一把金鑰

優點：

1.較快速

2.如果使用足夠大的金鑰，將難以破解。

缺點：

1.需要有一個安全性機制將金鑰安全性的分送至交易的雙方。

2.提供私密性(Confidential)的安全性能力，無法提供不可否認的能力

非對稱性密碼學(Asymmetric Encryption)

每個使用者擁有一對金鑰-公開金鑰和私密金鑰(public keyand a private key)，訊息由其中一把金鑰加密後，必需由另一把金鑰予以解密，公開金鑰可以被廣泛的發佈，而私密金鑰必需隱密的加以保存。

優點：

1.公開鑰匙可以公開分送

2.提供私密性、驗證與不可否認性等服務

缺點：

1.效率較差

比較圖

	對稱性	非對稱性
其他名稱	秘密金鑰加密法	公開金鑰加密法
加解密的鑰匙是否相同	相同	不同
鑰匙是否公開	不可	公開鑰匙可公開 秘密鑰匙不可公開
鑰匙保管問題	如果與N個人交換訊息需保管N把鑰匙	無論與多少人交換訊息只需保管自己的秘密鑰匙
加解密速度	快	慢
應用	e-mail	數位簽章

第二章- 密碼學 介紹

何謂密碼學！？由希臘文“kryptos” (隱藏) 和“graphein” (寫字)組成，代表"隱藏的字"。密碼學為一種利用數學方法來對資料加密和解密的科學。密碼系統是由明文、加密演算法、金鑰、解密演算法及密文組合而成。

明文(Plaintext)　 →加密前的原始資料，為加密演算法的輸入，解密

演算法的輸出。

密文(Ciphertext) →加密之後的資料，為加密演算法的輸出，解密演

算法的輸入。

加密演演算法(Encryption Algorithm)

利用密鑰對明文進行加密的編碼動作的演算法。

解密演算法(Decryption Algorithm)

利用金鑰對密文進行解密的解碼動作的演算法。

解密(Decipher)

將密文還原為明文的過程。

密碼破解(Cryptanalysis)

不需經由加密金鑰或使用偽造金鑰即能夠將密文解原還為明文稱之。

※加密技術的強度指的是密碼破解所需要花費的時間與資源。加密技術強度的高低通常牽涉到下列的因素：

(1)演算法強度

(2)金鑰保護機制

(3)金鑰的長度

※密碼系統的安全與否的衡量標準在於破解者需要花費多少時間以及多少成本才能夠破解。

(1)破解所需要的成本高於該訊息的價值

(2)破解所需要的時間超過該金鑰的壽命

※密碼破解技術分為下列幾種：

(1)只知密文破解(Ciphertext Only Attack)

破解者藉由蒐集所有可能的密文以找出明文或金鑰。

(2)已知明文破解(Known Plaintext Attack)

破解者藉由已知的明文與其相對應的密文以找出金鑰。

(3)選擇明文破解(Chosen Plaintext Attack)

攻擊者利用特殊方法將明文發送給傳送端，再由傳送者取得加密後的密文(即破解者可以控制明文與其相對應的密文) ，以找出加密金鑰。

(4)選擇密文破解(Chosen Ciphertext Attack)

攻擊者利用特殊方法將密文發送給接收端，再由接收者取得解密後的明文(即破解者可以控制密文與其相對應的明文) ，以找出加密金鑰。

(5)暴力破解法(Brute-Force Attack)

破解者嘗試所有可能的私密金鑰來攻擊密碼系統。