密碼系統 RSA 攻防

目錄

• 簡介
• 金鑰產生 Key generation
• 加密
• 解密 Decryption
• 正確性 Correctness
• RSA加密加速
• RSA加密攻擊
  • 弱參數攻擊 Weak Parameter Attack
  • 共同模數攻擊 Common Modulus Attack
  • 低指數攻擊 Low Exponent Attack
  • 選定密文攻擊 Chosen Ciphertext Attack

簡介

NIST美國國家標準與科技機構發起的Public Key公開金鑰加解密系統競賽，RSA (Rivest–Shamir–Adleman)加密演算法由三位密碼學家共同研究出來在1973年發表，最終獲選最早為公開金鑰系統標準之一，雖然後來英國Government Communications Headquarters(GCHQ)國家通訊總部說他們的英國密碼學家早在1970年就已經研究出Non-Secret Encryption這種非對稱式加解密系統，但不管怎麼說，RSA在當時算是非常突破性的成果。

金鑰產生 Key generation

首先選擇兩個隨機的大質數和，通常教科書或老師說要取大質數

那怎樣的質數才算大？

參考量測整數複雜度之後討論都使用多少bit長度為單位，以及和這兩個大質數的長度要很接近，用來計算: 並且 ，如上所說挑選出來的是的長度。

可以參考Euler’s Totient Function尤拉函數，目的是為了找所有與互質的數，和挑質數的原因在於在之下，每一個數都會跟互質，同樣的在之下每一個數也都會跟互質，這樣乘出來群的範圍就會是最大的。

接著隨機挑選一個並且，這個e之後就會用來當作公鑰，接著使用公鑰計算私鑰:

，就是的乘法反元素，如此一來，公鑰就是，而私鑰就是。

加密

選一個想要加密的明文Message :

: 加密時使用接收者的公鑰進行加密。

解密 Decryption

接收者收到傳輸者加密過後的密文 Ciphertext :

: 解密時接者者使用只有自己知道的私鑰進行解密。

正確性 Correctness

私鑰是由公鑰所計算得來的，可以調換成，原因是使用費馬小定理Fermat’s Little Theorem:

，為非零整數，為質數。

以及中國餘式定理Chinese Remainder Theorem:

如果以及代表，為互質的兩數。

所以需要證明的是

如前面中國餘式定理所述可以拆成以及使得可以成立，再者使得

可以將在modular運算看成，必須大於0。

同理在也可行:

得證以及所以

RSA加密加速

非對稱式加密系統的安全性都倚靠數學難題，而計算這些金鑰大多使用軟體像是openssl等，當然也有像是特殊的加解密硬體機器可以使用，一台也不便宜，所以幾乎都是企業才會去採購，故網路上的伺服器幾乎都是使用軟體的方法在計算，但在網路上每秒有多少組金鑰對正在產生，而軟體的計算速度也不能太慢，故可以使用一些小方法來提昇效率。

像是使用特殊的，通常會是，再將轉換成二進制，使用square-multiply algorithm來加快計算速度。

舉例使用square-multiply algorithm計算只需要少量的乘法就可以。

另外就是透過中國餘式定理Chinese Remainder Theorem的isomorphism特性計算:

首先設定其中

接著預先計算以及

就可以計算

軟體的話可以利用平行運算分別計算以及

RSA加密攻擊

弱參數攻擊 Weak Parameter Attack

是假設私鑰挑選的值: 以及沒有挑選大質數以及數值很小，跟很接近的話代表也會很小，而會比再大一些，至少，所以會比大一些。

首先我們計算是取得這個之後看是不是一個平方數，如果是的話有可能會是，如果是一個平方數的話，可以看成是n分解成

針對弱參數的對策就是的bit數應該要比在少一些，不能夠讓bit數太接近。

共同模數攻擊 Common Modulus Attack

假設一組用來產生兩對金鑰給兩個使用者:

可以使用其中一對的金鑰去搜尋另一對的金鑰，假設今天知道user1的金鑰要猜user2的私鑰:

，就是

以及假設一個同時被這兩個使用者加密，竊聽者可以取得跟，可以計算用來:

，當然先決條件是:

，並且

針對共同模數攻擊的對策是盡量不要使用同一個群產生太多把金鑰對，以及盡量不要加密同一個明文太多次。

低指數攻擊 Low Exponent Attack

在早期許多伺服器使用當作公開金鑰，但風險就是如果只要被三個使用者用來加密的話，竊聽者可以取得這些密文:

前面提到使用中國餘式定理CRT可以計算共同的數，

而使用三次方根演算法就能快速解開取得了。

針對低指數攻個的對策就是不要挑選太小。

選定密文攻擊 Chosen Ciphertext Attack

這種攻擊方法需要倚靠Oracle讓攻擊者可以取得明文密文對，可以將oracle想成一張很大的表，系統提供一個Decryption Oracle 給這oracle一個使用者自己挑選的密文，oracle會回傳一個，唯一的限制就是攻擊者不能要求解開真正想知道的明文密文對，攻擊者只能挑選想破解的密文之外的其他密文，擁有解密oracle後攻擊者要如何攻擊？

透過原本的關聯性計算，

詢問oracle ，這個

最後計算

透過mask掉原本的得到拿去詢問oracle後再使用攻擊者自己挑選的還原得到想要攻擊的的，而這種選定密文攻擊有兩種型態:

1. Non-adaptive chosen ciphertext attakc(CCA1): 攻擊者把想要詢問的密文一次挑選出來，只能針對oracle詢問一次，無法依靠上一次詢問的結果來調整下一次詢問的選擇。
2. Adaptive chosen ciphertext attack(CCA2): 攻擊者在多項式時間內可以一次一次的詢問oracle，不限詢問次數，可以透過前一次的詢問來調整下一次的詢問選擇。

如此可見CCA2的安全性等級是最高的，所以看paper在證明密碼系統的安全性時雖然作者會寫有CCA的安全性，但需要讀者再去檢查一下oracle的等級，看是達到CCA1還是CCA2的安全性。

針對RSA選定密文攻擊方法是採用使用random oracle model來抵抗CCA2的攻擊。