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

 

3-3 公開鑰匙的同餘算術

內容:

『同餘算術』(Modular Arithmetic是表示某一進位的運算,譬如有二進位運算、八進位運算、十六進位運算、或 n 進位運算(n 為任何數)。較常使用的同餘算術有加法、乘法和指數運算,其中同餘指數可說是同餘乘法一個特例(譬如 X3 X × X × X),但它是公鑰系統的主要運算工具。在公鑰系統中有一個重要觀念,即是『反函數』(Inverse Function,表示某數經由演算之後,是否可以由另一個數值找出原來的值。譬如 X 經由計算後得到 Y,是否可以找到另一個數 Z,再由 Y Z 計算出原來的值 X;如果可以的話,Z 便是 X 的反函數。我們試著利用各種同餘算術的推導,來找出是否具有反函數的功能(反向加法或反向乘法),再利用反函數來推論出公鑰系統的公開與私有鑰匙。反向函數又稱為『反向暗門』(Inverse Backdoor,理想狀態反向暗門必須是唯一的;因而,稱之為『單向暗門』。

3-3-1 模數

所謂『模數』(Modulo是一種除法取餘數的運算,譬如某數modulo 16modulo 10modulo 8分別表示某數除以16108的餘數,為了簡化,一般以mod表示。『模數』即是表示在某領域範圍內做運算,參與計算的運算元,以及計算後的結果都不會超過該領域範圍。譬如,modulo 8 運算,則運算元與結果都不會超過 80 ~ 7)範圍。如果運算結果超過 8,則取 8 的餘數。如此就非常接近 8 進位計算,但模數沒有進位,直接將進位部份捨棄。習慣上,我們常使用 102816 進位的運算,但在密碼學上可能採用任何數(n)進位的運算,常以 modulo n mod n 來表示。

令一個正整數 n 與整數 a,並 a 除以 n 得到商為 q,與餘數 b,之間的關係如下:

a = qn + b   0 b < nq =a/n

其中,q =a/n 表示 a/n 整除的數0 或其它大於 1 的整數);可能得到的餘數 b = {0, 1, 2, …, n-1},稱之為『完全餘數系』(Complete of Residues)。上式成立的話,可定義模數運算如下:

b a mod n

其中『≡』表示『相當於』的意思,而並非『相等』(Equal” = “;也就是說,b 的值是相當於 a 取模數 na mod n)的計算,但並非僅有 a 才可能得到 b,而可能存在其它數值。譬如,a mod 10 = 6,其中 a 可能出現的情況有:61626、、、等等;但這些數存在有一個特性 a = qn + 6q 0 或大於 1 的整數。瞭解模數運算(mod)之後,將其具有的特性歸類如下[1, 86, 121]

  • 反向性a a mod n

(驗證: 5 5 mod 10)

  • 對稱性:若 a b mod n,則 b a mod n

(驗證:5 15 mod 10 15 5 mod 10 5 = a )

  • 遞移性:若 a b mod n b c mod n,則 a c mod n

(驗證:5 15 mod 10 15 25 mod 10,則 5 25 mod 10 5 = a)

  • (a mod n) = (b mod n),可推論出 a b mod n

(驗證:(15 mod 10) = (25 mod 10),則 15 25 mod 10 5 = a)

接下來,我們利用模數特性,來推論同餘算數。

3-3-2 同餘加法

『同餘加法』(Modular Addition表示在某個領域(或稱模組,n)內執行加法運算。基本上,參與計算數值的大小應該不會超過該領域,計算後的結果也不會超過該領域(模組 n)。假設 a = 8b = 7n=13,則運算結果如下:

(a + b ) mod n = (8 + 7) mod 13 = 2

上述表示在領域 13 的同餘加法運算,基本上,運算元(a b)與計算後結果都不會超過 130 ~ 12),如果超過 13 的話,則取 13 的餘數。但許多情況下,參與計算數值的大小可能超過領域(模組 n),則取模組餘數後再計算的結果,與相加後再取模組餘數的結果相同,亦即:

[(a mod n) + (b mod n)] mod n = (a + b) mod n        式子(4.1)

吾人以 a = 16b=24n=13,驗證上述式子(1) 是否成立:

式子(4.1) 左邊 = ((16 mod 13) + (24 mod 13)) mod 13

= (3 + 11) mod 13

= 1

式子(4.2) 右邊 = (16 + 24) mod 13

= 40 mod 13

= 1

則式子(1) 左邊運算結果與右邊相同,該式子成立。此特性對我們推演 RSA 演算法很有幫助。

我們將 modulo 10 的加法,由 0 9 之間數字相加的結果顯示於圖 4-3

+

0

1

2

3

4

5

6

7

8

9

0

0

1

2

3

4

5

6

7

8

9

1

1

2

3

4

5

6

7

8

9

0

2

2

3

4

5

6

7

8

9

0

1

3

3

4

5

6

7

8

9

0

1

2

4

4

5

6

7

8

9

0

1

2

3

5

5

6

7

8

9

0

1

2

3

4

6

6

7

8

9

0

1

2

3

4

5

7

7

8

9

0

1

2

3

4

5

6

8

8

9

0

1

2

3

4

5

6

7

9

9

0

1

2

3

4

5

6

7

8

4-3 Modulo 10 的加法

接著來探討同餘加法是否具有反向函數的功能。假設以 mod 10 為例,而明文、公開鑰匙、私有鑰匙、以及密文都介於 0 ~ 9 之間。由圖 4-3 可以明顯觀察出 mod 10 具有非對稱加/解密功能,其中公開鑰匙 KU與私有鑰匙 KR之間的關係是 KU + KR = 10,且加密與解密演算法都是同餘加法運算(mod 10),下列是1 ~ 9 之間加密與解密鑰匙的配對關係:

 

公開鑰匙 (KU)

1

2

3

4

5

6

7

8

9

私有鑰匙 (KR)

9

8

7

6

5

4

3

2

1

譬如,KU = 4KR = 6、明文 P=5,則利用公開鑰匙加密得密文 C = KU +5 = 4+5 9 mod 10,再利用私有鑰匙解密,還原明文為 P = KR + 9 = 6+95 mod 10

由此可見,KU KR之間的關係是互為反向函數,亦即若以 KU加密的密文,便可以利用 KR解密回來,反之亦然。KU KR的關係如下( mod 10 為例)

KU + KR = 10

亦即:

KU + KR0 mod 10

因此,我們可以做一個簡單的結論,同餘加法具有反向函數的能力,又稱之為『加法反向』(Addition Reverse。假設同餘模數為 n,任何數值 y,與其反向元素為y-1,如果滿足『反向函數』,則兩數之間的關係為:

y + y-1 0 mod n y + y-1 mod n 0

也就是說,在任何模數(n)運算中,只要找出兩個數的和,可以整除 n 的話,則該兩數互為加法反向函數。

3-3-3 同餘乘法

『同餘乘法』(Modular Multiplication的概念如同加法一樣,在某一領域內(模組 n)執行乘法運算。基本上,運算元(ab)與運算結果都不會超過其領域,假設 a = 8b = 7n=13,則運算程序如下:

(a × b) mod n = (8 × 7) mod 13 = 56 mod 13 = 4

在許多情況下,運算元還是可能超領域。同餘乘法還是滿足,運算元取模組餘數後相乘,與相乘後再取模組餘數,兩者結果相同,亦即:

((a mod n) × (b mod n)) mod n = (a × b) mod n      (式子4.2)

吾人以 a = 16b=24n=13,驗證上述式子(1) 是否成立:

式子(4.2) 左邊 = ((16 mod 13) * (24 mod 13)) mod 13

= (3 * 11) mod 13

= 33 mod 13

= 7

式子(4.2) 右邊 = (16 * 24) mod 13

= 384 mod 13

= 7

上述左邊運算結果與右邊相同,則式子(4.2) 成立。吾人可觀察出一個重要的特性,式子(4.2) 左邊所計算處理的數值較小,相對的所需的運算量也較少。RSA 演算法大多利用此特性來減低計算量的(容後說明)。

我們也是希望由同餘乘法的特性中,尋找出有關公鑰系統的機能。首先,將 0 ~ 9 之間互相乘積的 mod 10 列於圖 4-4,再來觀察同餘乘法的特性。

×

0

1

2

3

4

5

6

7

8

9

0

0

0

0

0

0

0

0

0

0

0

1

0

1

2

3

4

5

6

7

8

9

2

0

2

4

6

8

0

2

4

6

8

3

0

3

6

9

2

5

8

1

4

7

4

0

4

8

2

6

0

4

8

2

6

5

0

5

0

5

0

5

0

5

0

5

6

0

6

2

8

4

0

6

2

8

4

7

0

7

4

1

8

5

2

9

6

3

8

0

8

6

4

2

0

8

6

4

2

9

0

9

8

7

6

5

4

3

2

1

3-2 Modulo 10 的乘法

       3-2 中,只有 {1, 3, 7, 9} 可做加/解密演算法的鑰匙(原因後述),至於公開與私有鑰匙之間的關係如下:

 

公開鑰匙 (KU)

1

3

7

9

私有鑰匙 (KR)

1

7

3

9

 

譬如,KU = 3KR = 7、明文 P=4,則利用加密程序可計算密文:

       C = KU× P = 3 × 4 2 mod 10;則密文為 2

解密程序可還原明文:

       P = KR× C = 7 × 2 4 mod 10;則明文為 4

公開鑰匙又稱為私有鑰匙的同餘乘法反元素,因此,同餘乘法也具有公開鑰匙演算法的特性。兩者之間關係為 KU× KR1 mod 10

利用同餘乘法所推演出來的反向函數,稱之為『乘法反向』(Multiplicative Reverse)。設同餘模數為 n,任何數值 y,與其反向元素為y-1,如果滿足『乘法反向』,則兩數之間的關係為:

y × y-1 1 mod n    0 < y < n0 < y-1 < n     (式子 4.3

也就是說,在任何模數(n)運算中,只要找出兩個數的乘積,除以 n 得到餘數是 1 的話,則該兩數互為加法反向函數。 式子 4.3 必須當 y ( y-1) n 互質才會成立,有關證明方面請參考[1, 86, 92],以下舉兩個例子分別說明之。

1:若 a = 3, n = 10。因為 3 10 互質,所以存在一個 b (0 < b < 10)使得

       a × b 1 mod n ( 3 × 7 1 mod 10, b = 7)

2:若 a = 5, n = 10。因為 5 10 不互質,所以找不到一個 b (0 < b < 10)滿足式子(4.1)

因此利用同餘乘法依然存在公開鑰匙系統的鑰匙配對,只要找到一個 a ( < n ) n 互質,必然存在一個 b ( < n ) 符合式子(4.1),當然若 n 是質數,則每一個a ( < n ) 皆與 n 互質。

3-3-4 同餘指數

『同餘指數』(Modular Exponentiation運算即是在某領域內(模組 n)執行指數運算。基本上,參與運算元與結果的大小都不會超過該領域,譬如 a =4b=6n=13,則運算程序如下:

ab mod n = 46 mod 13 = 4096 mod 13 = 1

吾人可以發現,指數運算不需較大的數值參與運算,就可能產生非常大的運算量,沒經過特殊方法運算,幾乎很難完成指數運算(RSA 主要運算方法)。與同餘乘法相同,數值取模組餘數後再執行運算的結果,與執行指數運算後,再取模組餘數的結果相同,亦即:

(a mod n)b mod n = ab mod n                   (式子 4.4

吾人以 a = 16b=4n=13,驗證上述式子 (4.4) 是否成立:

式子 (4.4) 左邊 = (16 mod 13)4 mod 13

= 34 mod 13

= 81 mod 13

= 3

式子 (4.4) 右邊 = 164 mod 13

= 15536 mod 13

= 3

依照上述驗證,式子 (4.4) 左邊與右邊運算結果相同,式子成立。吾人也可以發現右邊的計算量非常大,如果能轉換成左邊計算方法,將可以減低許多運算量。吾人大都利用此特性來實現 RSA 演算法。

接著,必須推演同餘指數是否具有反向暗門特性,藉此觀察是否利用它來實現非對稱密碼系統。圖 4-5 0 ~ 9 之間 mod 10 的運算結果,表內數字為 xy的結果,其中 x 為列的數字;y 是行的數字。

xy

0

1

2

3

4

5

6

7

8

9

0

 

0

0

0

0

0

0

0

0

0

1

1

1

1

1

1

1

1

1

1

1

2

1

2

4

8

6

2

4

8

6

2

3

1

3

9

7

1

3

9

7

1

3

4

1

4

6

4

6

4

6

4

6

4

5

1

5

5

5

5

5

5

5

5

5

6

1

6

6

6

6

6

6

6

6

6

7

1

7

9

3

1

7

9

3

1

7

8

1

8

4

2

6

8

4

2

6

8

9

1

9

1

9

1

9

1

9

1

9

3-3 modulo 10 的指數運算

其實指數運算表示自我函數相乘的次數,如 X3表示 X 自我相乘 3 次。同餘指數是同餘乘法運算的延伸,它的反向函數也與同餘乘法相同,如下:(公式 4.3

y × y-1 1 mod n

由圖 3-3 可以找出合乎反向暗門條件的鑰匙 KUy)與 KRy-1)如下:(n = 10

 

公開鑰匙 (KU)

1

3

7

9

私有鑰匙 (KR)

1

7

3

9

 

譬如,明文 P = 8、公開鑰匙 KU = 3、私有鑰匙 KR = 7,則加密程序為:

加密:密文 C =  = 83 2 mod 10;則密文為 2

解密程序為:

解密:明文 P =  = 27 8 mod 10;則明文為 8

同樣的,將利用私有鑰匙加密,也可利用公開鑰匙還原。吾人可證明出同餘指數運算具有反向暗門(乘法反向),兩支鑰匙之間的關連為 KU× KR1 mod 10(與同餘乘法相同)。

3-3-5 Euler’s Totient 函數

Euler’s Totient 函數 ψ(n) 是公開鑰匙演算法中重要的參數,其意思是小於 n 但與 n 互質之正整數的數目,譬如ψ(10) = 4,因為小於 10 且與 10 互質的正整數共有 4 (1, 3, 7, 9)。圖 4-6是ψ(n), 0 < n < 31, 的函數值。

n

ψ(n)

n

ψ(n)

n

ψ(n)

1

1

11

10

21

12

2

1

12

4

22

10

3

2

13

12

23

22

4

2

14

6

24

8

5

4

15

8

25

20

6

2

16

8

26

12

7

6

17

16

27

18

8

4

18

6

28

12

9

6

19

18

29

28

10

4

20

8

30

8

3-4 Euler’s Totient 函數

由圖 3-4 可以觀察出來,如果 p 為質數的話(圖中有陰影的欄位),則:

ψ(p) = p-1

譬如,p=3,則ψ(3) = 3-1=2p=19,則 ψ(19) = 18;依此類推。現在假設有兩個質數 p q,且 n = pq,則:(證明請參考 [1, 92]

       ψ(n) =ψ(pq) =ψ(p) × ψ(q) = (p-1) × (q-1)           (式子 4.7

驗證,如果 p=3q=7,所以n = 3 × 7 = 21,則:

       ψ(21) =ψ(3) × ψ(7) = (3-1) × (7-1) = 2 × 6 = 12(如同圖 4-6 所示)

我們來回顧一下ψ(n) 的特性,它代表著與 n 成為『互質』的數目。在同餘運算中,質數經由某一數運算之後,最有可能產生餘數,這也是推論公鑰演算法的最基本要素。因此,ψ(n) 的數值愈大,則可能選用的質數就愈多,以圖 4-5 為例(同餘指數運算),ψ(10) = 4,則可選用與 10 互質的數只有四個(1, 3, 5, 7,並且運算結果每 4 列便再重複。

 

主講人:粘添壽博士

 

資訊與網路安全技術