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

 

3-4 RSA 演算法

內容:

  • 3-4 RSA 演算法

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

    • 3-4-2 推演 M ≡ Med mod n

    • 3-4-3 推演結果歸類

    • 3-4-4 驗證推演結果

  •  3-5 RSA 安全性

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

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

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

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

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

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

C Me mod n

M Cd mod n (Me)d mod n Med mod n

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

3-4-2 推演 M Med mod n

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

  • 必須找出 ed n 的值,使得對所有 M < n 來說,都能滿足 Med M mod n

  • 對任何 M < n 而言,計算 Me Cd都必須非常容易。

  • 如果給定 e n,要計算出 d 是非常困難的。

第一個問題是主要的關鍵,Med M mod n 的意思是 Med除以 n 所得到的餘數是 M;而 Med M 經由加密後 Me再解密運算 Cd後所得到的明文,依照 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

接著,再利用同餘運算的規則:(備註:1k = 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 成立的話,則上式成立;因此,不管mn是否互質,下列式子必然成立:

mkψ(n)+1 = mk(p-1)(q-1)+1 m mod n              (式子 4.10

驗證如下:

mψ(n) 1 mod n

[mψ(n)]k 1 mod n

mkψ(n) 1 mod n

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

我們可以回到 Med M mod n 的推演,只要:

ed = kψ(n) +1

則下列式子就成立:

Med M mod n

所以:

ed 1 mod ψ(n)

d e-1 mod ψ(n)

由此可以大略了解 ed 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)=11 < e <ψ(n):自選公開值。

    • d e-1 mod ψ(n):計算而得的私有值。

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

 ed 1 mod ψ(n)

ed = kψ(n) +1,又依照 Euler 定理(式子 4.6):

Mkψ(n)+1 Mk(p-1)(q-1)+1 M mod n

因此,可以證明出下式:

Med = Mkψ(n)+1

Med M mod n

得到上式之後,可將 RSA 演算法的運作程序歸類如下(同餘指數運算):

明文區塊:M

公開鑰匙:{e, n}

私有鑰匙:{d, n}

加密編碼:C Me mod n

解密編碼:M Cd mod n (Me)d mod n Med mod n M mod n

3-4-4 驗證推演結果

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

  • 選定兩個質數,p = 7q = 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, .. 開始測試)

經過上述推演得到:

公開鑰匙:KU = {e, n} = {5, 119}

私有鑰匙:KR = {d, n} = {77, 119}

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

加密編碼:C Me mod n 195 mod 119 66 mod 119,則密文為 66

演算過程如下:

192 = 361 4 mod 119

194 4 × 4 = 16 16 mod 119

195 = 194× 19116 × 19 = 304 66 mod 119

解密編碼:M Cd mod n 6677 mod 119 19 mod 119,則明文為 19

演算過程如下:

662 = 72 mod 119

664 = 72 × 72 = 5184 = 67 mod 119

668 = 67 × 67 = 4489 = 86 mod 119

6616 = 86 × 86 = 7396 = 18 mod 119

6632 = 18 × 18 = 324 = 86 mod 119

6664 = 86 × 86 = 7396 = 18 mod 119

6677 = 6664× 668× 664× 66 = 6845256 = 19 mod 119

3-5 RSA 安全性

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

  • 暴力攻擊法:嘗試所有可能的鑰匙。任何一種密碼演算法都可以被暴力攻擊破解,唯一克服的方法是增加鑰匙的長度。RSA 也是以增加鑰匙長度來克服暴力攻擊。

  • 數學攻擊法:既然 RSA 演算法是利用數學理論推導出來,所以也一定可以利用數學方法來破解;雖然目前無法百分之一百的成功,但相信新的數學方法被推演出來時,可能致使 RSA 變得不堪一擊。目前大多採用因數分解法來攻擊 [122]

如果要增加鑰匙長度,e d 的位元數當然是愈大愈好,則相對應的 pq 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 的選擇是介於 1075 10100之間,且 n = pq,符合此條件的 p q 也許很多,所以目前大多採用『二次篩選法』(Quadratic Sieve)與『一般數域篩選法』(Generalized Number Field Sieve)等兩種因數分解方法。我們無法說 RSA 演算法是絕對安全,但以目前來講,它還是安全的。

主講人:粘添壽博士

 

資訊與網路安全技術