RSA 演算法

資訊與網路安全技術：第三章現代公開鑰匙系統上一頁 下一頁

3-4 RSA 演算法

內容：

3-4 RSA 演算法

3-4-1 RSA 演算法的基本概念

3-4-2 推演 M ≡ M^ed mod n

3-4-3 推演結果歸類

3-4-4 驗證推演結果

3-5 RSA 安全性

RSA 的名稱是由 Rivest、Shamir 與 Adleman 三人的名字共同組合而成。雖然 Diffie 與 Hellman 提出只要能找出單向暗門的數學函數，便能解決公鑰密碼學的問題。但真正提出解決方案的是由 Rivest、Shamir 與 Adleman 等三人，也因此定名為『RSA 演算法』（RSA Algorithm）。

依據 RSA 演算法特點，大多運用於密鑰交換與數位簽章兩大方面。其實 RSA 演算法也可以用來加密與解密功能，達成訊息隱密性傳輸的功能。但它為了提供安全性，鑰匙長度都較長，執行加密與解密時，需耗費較長的時間，因此對於大量資料傳輸並不適合。

利用 RSA 鑰匙加密的特點是，『明文的長度不可以超過鑰匙長度』（根據不同補齊方式，能夠加密的長度也不一樣），訊息經由加密編碼後的密文與鑰匙長度相同。如果針對大量資料加密的話，則需將明文依照鑰匙長度（如 1024 或 2048 bits）分割成若干個區塊，分別加密後再組合成密文序列。解密處理也是相同，分段解密後再組合回原明文格式。

RSA 演算法配合雜湊演算法執行數位簽章就容易多了，原始文件經由雜湊演算法（SHA1、MD5）編碼後，產生 160 位元或 128 位元，再經由 RSA 私有鑰匙（簽署）或公開鑰匙（驗證）加密，所耗費的時間就較短。

3-4-1 RSA 演算法的基本概念

RSA 演算法是利用同餘指數，推演出公開與私有鑰匙配對，並能完全合乎單向暗門的需求。RSA 演算法同樣使用區塊加密法，且鑰匙與區塊明文的長度必須相同（一般情況下都使用 512 個位元的長度）。明文區塊被加密成相同長度的密文區塊，每一區塊的數值小於某個整數 n，表示區塊的大小必須小於或等於log₂(n)位元，若區塊大小為 k 個位元，則 2^k < n < 2^k+1。對於明文 M 與密文區塊 C 來說，其加密與解密程序為：

C ≡ M^e mod n

M ≡ C^d mod n ≡(M^e)^d mod n ≡ M^ed mod n

其中 n 為加密者與解密者雙方都知道的數值，但加密者必須知道數值 e，而只有解密者知道另一個數值 d，我們以 K_U = {e, n}為公開鑰匙，以 K_R = {d, n} 為私有鑰匙；兩把鑰匙可以相互加密或解密。

3-4-2 推演 M ≡ M^ed mod n

為了滿足上述 RSA 演算法的特性，必須合乎下列條件：

必須找出 e、d 與 n 的值，使得對所有 M < n 來說，都能滿足 M^ed≡ M mod n。
對任何 M < n 而言，計算 M^e與 C^d都必須非常容易。
如果給定 e 與 n，要計算出 d 是非常困難的。

第一個問題是主要的關鍵，M^ed≡ M mod n 的意思是 M^ed除以 n 所得到的餘數是 M；而 M^ed是 M 經由加密後 M^e再解密運算 C^d後所得到的明文，依照 Euler 定理（式子 4.9，條件 m 與 n 互質）：

m^ψ(n)+1 ≡ m mod n

我們給定兩個質數 p 與 q，以及兩個整數 n (=p × q) 與 m，其中 0 < m < n，則下列關係式必然成立：（引用式子 4.7）

m^ψ(n)+1 = m^(p-1)(q-1)+1≡ m mod n

接著，討論質數 p 與 q 的關係。依照 Euler 定理，m 必須與 n 成為互質（gcd(m, n) = 1），則上述的式子成立；又 n = pq，是否表示 p 與 m、或 q 與 m 也成為互質？但 a 與 m 成為互質的話，p 與 q 兩者之間必定至少有一個數，必須與 m 成為互質。因此，假設如下：

m = pc，其中 c 為任何整數。
gcd(m, p)≠1 與 gcd(m, q) =1。

由條件 (2) 是假設 m 與 p 之間不構成互質，因此存在著 m = pc 的關係；另外假設 m 與 q 之間構成互質關係。如果 gcd(m, q) = 1。依照 Euler 定理，下列式子一定成立：（式子 4.8）

m^ψ(q) ≡ 1 mod q

接著，再利用同餘運算的規則：（備註：1^k = 1）

[m^ψ(q)]^ψ(q)≡ 1 mod q

m^ψ(p)×ψ(q) ≡ 1 mod q

m^(p-1)^×(q-1) ≡ 1 mod q；又ψ(n) = (p-1)×(q-1) 則：

m^ψ(n) ≡ 1 mod q

上述式子表示存在一個 k 的關係，而 k 為任何數值的整數：

m^ψ(n) = 1 + kq

等號雙邊同乘以 m，並且 m = pc（假設條件 (1)）與 n = pq，則：

m^ψ(n)+1 = m + ckpq = m + ckn

所以

m^ψ(n)+1 ≡ m mod n

由此可見，只要 gcd(m, q) =1 成立的話，則上式成立；因此，不管m與n是否互質，下列式子必然成立：

m^k^ψ(n)+1 = m^{k(p-1)(q-1)+1}≡ m mod n （式子 4.10）

驗證如下：

m^ψ(n) ≡ 1 mod n

[m^ψ(n)]^k≡ 1 mod n

m^k^ψ(n) ≡ 1 mod n

m^k^ψ(n)+1 = m^{k(p-1)(q-1)+1}≡ m mod n

我們可以回到 M^ed≡ M mod n 的推演，只要：

ed = kψ(n) +1

則下列式子就成立：

M^ed≡ M mod n

所以：

ed ≡ 1 mod ψ(n)

d ≡ e^-1 mod ψ(n)

由此可以大略了解 e、d 與 n 之間的關係。意即在取ψ(n) 的同餘運算之下，e 與 d 互為乘法反函數。又 ed ≡ 1 mod ψ(n) 表示 e 與 d 中必須有一個數與ψ(n) 互質，才可以成立；意即需要：

gcd(ψ(n), e) =1 或

gcd(ψ(n), d) =1；兩條件之一成立。

一般將選用互質的數（如 e）當作公開鑰匙，而不一定成為互質的數（如 d）做為私有鑰匙。

3-4-3 推演結果歸類

經過上述的推論之後，我們可以將 RSA 演算法的相關參數歸類如下：

p 與 q 兩質數：自行選擇的私有值。
n=pq：計算而得的公開值，並且求出 ψ(n) = (p-1)(q-1) 的值。
選擇 e，需滿足 gcd(ψ(n), e)=1；1 < e <ψ(n)：自選公開值。
d ≡ e^-1 mod ψ(n)：計算而得的私有值。

公開鑰匙由 {e, n} 所組成，而私有鑰匙則由 {d, n} 組成，e 與 d 之間的關係是：

ed ≡ 1 mod ψ(n)

則 ed = kψ(n) +1，又依照 Euler 定理（式子 4.6）：

M^k^ψ(n)+1 ≡ M^{k(p-1)(q-1)+1}≡ M mod n

因此，可以證明出下式：

M^ed = M^k^ψ(n)+1

M^ed≡ M mod n

得到上式之後，可將 RSA 演算法的運作程序歸類如下（同餘指數運算）：

明文區塊：M

公開鑰匙：{e, n}

私有鑰匙：{d, n}

加密編碼：C ≡ M^e mod n

解密編碼：M ≡ C^d mod n ≡ (M^e)^d mod n ≡ M^ed mod n ≡ M mod n

3-4-4 驗證推演結果

接下來，我們用一個範例說明公開鑰匙與私有鑰匙的產生方式，如下：

選定兩個質數，p = 7、q = 17。
計算 n = pq = 7 × 17 = 119。
計算ψ(n) = (p-1) × (q-1) = 6 × 16 = 96。
選定 e，但必須滿足 gcd(e, ψ(n)) =1，假設選擇 e =5，因與 96 互質。

(備註：由 3, 5, 7, … 質數開始測試是否滿足)

尋找 d，其中d < 96且必須滿足 de ≡1 mod 96。本範例找到 d = 77，因為 77×5 = 385 ≡1 mod 96。

(備註：de/96 = 商 .. 餘數 1，則 d×5 = (96×y) +1，由 y=1, 2, 3, .. 開始測試)

經過上述推演得到：

公開鑰匙：K_U = {e, n} = {5, 119}

私有鑰匙：K_R = {d, n} = {77, 119}

我們用一個明文 M=19，來測試加密與解密的運作程序，如下：

加密編碼：C ≡ M^e mod n ≡ 19⁵ mod 119 ≡ 66 mod 119，則密文為 66。

演算過程如下：

19² = 361 ≡ 4 mod 119

19⁴≡ 4 × 4 = 16 ≡ 16 mod 119

19⁵ = 19⁴× 19¹≡16 × 19 = 304 ≡ 66 mod 119

解密編碼：M ≡ C^d mod n ≡ 66⁷⁷ mod 119 ≡ 19 mod 119，則明文為 19。

演算過程如下：

66² = 72 mod 119

66⁴ = 72 × 72 = 5184 = 67 mod 119

66⁸ = 67 × 67 = 4489 = 86 mod 119

66¹⁶ = 86 × 86 = 7396 = 18 mod 119

66³² = 18 × 18 = 324 = 86 mod 119

66⁶⁴ = 86 × 86 = 7396 = 18 mod 119

66⁷⁷ = 66⁶⁴× 66⁸× 66⁴× 66 = 6845256 = 19 mod 119

3-5 RSA 安全性

攻擊 RSA 演算法有兩種主要的方法：

暴力攻擊法：嘗試所有可能的鑰匙。任何一種密碼演算法都可以被暴力攻擊破解，唯一克服的方法是增加鑰匙的長度。RSA 也是以增加鑰匙長度來克服暴力攻擊。
數學攻擊法：既然 RSA 演算法是利用數學理論推導出來，所以也一定可以利用數學方法來破解；雖然目前無法百分之一百的成功，但相信新的數學方法被推演出來時，可能致使 RSA 變得不堪一擊。目前大多採用因數分解法來攻擊 [122]。

如果要增加鑰匙長度，e 與 d 的位元數當然是愈大愈好，則相對應的 p、q 與 n 的數值也必須選擇很大的值。如此一來，所需的計算量變得非常的複雜，系統執行速度也會變慢。至於因數分解法，可有下列三種攻擊法：

將 n 分解成兩個質因數 p 與 q，如此便可以計算出ψ(n) = (p-1)(q-1)，因為一般 e 都採用某一固定值（如 e =3），接著就可以計算出 d ≡ e^-1 mod ψ(n)。
由 n 計算出 ψ(n)，而不必先算出 p 和 q，也可以尋找出 d ≡ e^-1 mod ψ(n)。
直接找出 d，而不必先計算出 ψ(n)。

基本上，還是利用分解因數，由 n 來找出 p 與 q 的攻擊方法比較可行。由上一節的分析，大略可以了解 p 與 q 的選擇是介於 10⁷⁵到 10¹⁰⁰之間，且 n = pq，符合此條件的 p 與 q 也許很多，所以目前大多採用『二次篩選法』（Quadratic Sieve）與『一般數域篩選法』（Generalized Number Field Sieve）等兩種因數分解方法。我們無法說 RSA 演算法是絕對安全，但以目前來講，它還是安全的。

翻轉工作室：粘添壽

資訊與網路安全技術

第一章安全性資訊系統簡介
第二章傳統秘密鑰匙系統
第三章現代公開鑰匙系統
- 3-1 公開鑰匙系統簡介
- 3-2 公開鑰匙的數學基礎
- 3-3 公開鑰匙的同餘算術
- 3-4 RSA 演算法
- 3-5 RSA 安全性
- 3-6 Diffie-Hellman 鑰匙交換
- 3-7 公鑰系統之應用

翻轉電子書系列：