Chapter 4 密碼基礎數學II：代數結構.

Presentation on theme: "Chapter 4 密碼基礎數學II：代數結構."— Presentation transcript:

1 Chapter 4 密碼基礎數學II：代數結構

2 學習目標 回顧代數結構的概念 定義「群」並使用範例解說 定義「環」並使用範例解說 定義「體」並使用範例解說
強調在現代區塊加密法中對n 位元做加減乘除運算的能力來自於由GF(2n)所構成的有限體

3 4.1 代數結構 密碼學需要整數集以及定義這些集合的特定運算式。這些集合以及對集合元素所進行的運算合稱為代數結構。本章我們將要定義群、環以及體等三個常用的代數結構。

4 4.1 代數結構 (續) 本節討論主題： 群 環 體

5 圖 4.1 常見的代數結構

6 4.1.1 群 群（G）是一個元素的集合和一個二元運算子「 • 」的結合，滿足以下四種特性（或稱公理）。一個交換群（commutative group，或稱為 abelian group），除了滿足群的四個特性之外，還有一個額外的特性：交換性。

7 4.1.1 群 (續) 交換群的特性 封閉性 結合性 交換性 存在單位元素 存在反元素

8 圖4.2 群

9 應用 雖然一個群只有單一的運算子，但是這個運算子受到群的特性影響，使得一個群可以有一對互為逆運算的運算子。

10 範例4.1 整數餘數集合與加法運算子 G = <Zn, +>
為一交換群。我們可以對此集合的元素 執行加法與減法的運算，而結果仍為此集合的元素。

11 範例4.2 集合 Zn* 與乘法運算子可構成一交換群 G = <Zn*, ×>

12 範例4.3 以下定義一個群 G = <{a, b, c, d}, •>， 其運算如表 4.1 所示。

13 範例4.4 排列群（permutation group）是一個很有意思的例子。這個集合是所有排列方式的集合，集合 的運算是合成（composition）：先進行一種排列，之後再進行另一種排列。

14 圖 4.3 排列運算的合成 （範例 4.4）

15 表 4.2 排列群的運算表

16 範例 4.5 在前一個範例中，我們將一組排列方式加上合成運算就成為一個群。這裡隱含的意思是使用兩個連續的排列方式並不能提升加密法的安全度，我們必定可以找到一個排列方式，其效果相當於兩個排列方式的合成，因為這是群的封閉性。

17 4.1.1 群 (續) 有限群 群的秩 子群

18 範例4.6 群 H = <Z10, +> 是否為 G = <Z12, +> 的子群？
解法：答案是否定的。雖然 H 是 G 的子集合，但是這兩個群所定義的運算子並不相同。H 的運 算子是模數為 10 的加法，而 G 的運算子是模數為 12 的加法。

19 循環子群 若一個子群的每一個元素都是另一個群中某一個元素的乘冪，則此子群稱為循環子群（cyclic subgroup）。這裡乘冪的意思是重複對這個元素引用群運算： an → a • a •…• a（n 次）

20 範例4.7 群 G = <Z6, +> 可以產生四個循環子群，分別是 H1 = <{0}, +>、H2 = <{0, 2, 4}, +>、 H3 = <{0, 3}, +> 和 H4 = G。

21 範例4.8 從群 G = <Z10*, ×> 中產生的三個循環子群只有四個元素：1、3、7 和 9。這些循環子 群分別是 H1 = <{1}, ×>、H2 = <{1, 9}, ×> 和 H3 = G。

22 循環群 若一個群為本身的循環子群，則稱為循環群（cyclic group）。

23 範例4.9 群 G = <Z6, +> 為一個具有兩個生成子（g = 1 和 g = 5）的循環群。

24 Lagrange 定理 假設有一群 G， H 為其子群，令 G 和 H 的秩分別為 |G| 和 |H|。根據 Lagrange 定理，|H| 會整除 |G|。

25 元素的級數 所謂元素的級數就是這個元素所生成之循環群的秩。

26 範例4.10 在群 G = <Z6, +> 中，個別元素的級數為：ord(0) = 1，ord(1) = 6，ord(2) = 3，ord(3) = 2，ord(4) = 3，ord(5) = 6。 在群 G = <Z10*, ×> 中，個別元素的級數為：ord(1) = 1，ord(3) = 4，ord(7) = 4，ord(9) = 2。

27 4.1.2 環 環（ring）是由一個集合和兩種二元運算所構成的代數結構，記作 R = <{…}, •, □>

28 圖4.4 環

29 範例4.11 集合 Z 內含加法與乘法兩種運算，為一交換環。我們可以證明 R = <Z, +, ×>。其中 加法滿足全部五項特性，而乘法僅滿足三項特性。

30 4.1.3 體 體（field），記為 F = <{…}, •, □ >，為一交換環，其中第二種運算能夠滿足和第一種運算一樣的五項特性，唯一的例外是第一種運算的單位元素（有時候也稱為零元素）在第二種運算中沒有反元素。

31 圖4.5 體

32 有限體 蓋洛瓦（Galois）證明，如果一個體為有限體，則其元素個數為 pn，其中 p 為質數且 n 為正整數。
注意 蓋洛瓦體 GF(p n) 是一個有限體，內含 pn 個元素。

33 GF(p) 體 當 n = 1 時，我們得到 GF(p) 體。這個體可以是集合 Zp = {0, 1,…, p – 1}，內含兩種算術 運算（加法與乘法）。

34 範例4.12 在這一類中很常用到的體是 GF(2)，集合為 {0, 1}，內含加法與乘法兩種運算，參考圖4.6。

35 範例4.13 我們從集合 Z5（5 是質數）可以定義出內含加法與乘法運算子的 GF(5)，見圖 4.7。

36 表 4.3 代數結構總整理

37 4.2 GF(2n) 體 在密碼學中，我們常常要用到加減乘除等四則運算。也就是說，我們需要用到體的概 念，然而在電腦中正整數是以 n 位元字組的型態儲存。

38 4.2 GF(2n) 體 (續) 本節討論主題 多項式 使用生成子 結語

39 範例4.14 我們來定義 GF(22) 這個體，其集合由 2 位元字組所組成：{00, 01, 10, 11}。我們為 這個體重新定義加法和乘法，使得這些特性都能滿足，見圖 4.8。

40 圖 4.8 GF(22) 體的例子

41 4.2.1 多項式 一個 n – 1 階的多項式通常寫成 其中，xi 稱為第 i 項，而 ai 則稱為第 i 項的係數。

42 範例4.15 圖 4.9 說明如何使用多項式來表示一個 8 位元的字組 ( )。

43 範例4.16 要找出多項式 x5 + x2 + x 所代表的 8 位元字組，首先要將省略的項加以還原。因為n = 8，所以多項式的階數為 7。還原後的多項式為 所以這個 8 位元字組為 。

44 運算 注意 用來表示 n 位元字組的多項式使用兩個體：GF(2) 和 GF(2n) 。

45 模多項式 對於在 GF(2n) 的多項式，我們定義了一組 n 階的模多項式。這些模多項式在這裡被當作質多項式（prime polynomial），意思就是集合中沒有任何一個多項式可以將之整除。質多項式不能被 分解成 n 階以下的多項式，所以又稱為不可分解多項式（irreducible polynomial）。

46 表 4.4 不可分解多項式列表

47 加法 注意 對多項式而言，加法和乘法是完全相等的運算。

48 範例4.17 現在我們在 GF(28) 下執行 (x5 + x2 + x) ⊕ (x3 + x2 + 1)。我們在這裡使用⊕符號來代表多項式的加法。加法程序如下：

49 範例4.18 還有另外一種速解。因為在 GF(2) 下的加法相當於 XOR 運算，所以可以直接將兩 個字組做位元的 XOR 運算而得到相同的結果。以上一個範例來說，x5 + x2 + x 相當於 ，而 x3 + x 相當於 。

50 乘法 係數是在 GF(2) 下執行乘法。 xi 乘以 x j 就得到 xi+j。
相乘的結果階數可能會超過 n − 1，所以必須除以模多項式取其餘式。

51 範例4.19 計 算 在 GF(28) 下 (x5 + x2 + x) ⊕ (x7 + x4 + x3 + x2 + x) 的 結 果， 不 可 分 解 多 項 式 為(x8 + x4 + x3 + x + 1)。這裡我們用⊕符號來代表兩個多項式相乘。 解法 要得到最後的結果，必須將相乘後的 12 階多項式除以 8 階的模多項式，然後得到餘式。這個 過程也和代數的作法相同，但是要記住現在加法和減法的結果相同。圖 4.10 是除法的過程。

52 圖 4.10 係數在 GF(2) 之下的多項式除法

53 範例4.20 在 GF(24) 下，找出多項式 (x2 + 1) 對模多項式 (x4 + x + 1) 的乘法反元素。

54 範例4.21 在 GF(28) 下，找出 (x5) 模 (x8 + x4 + x3 + x + 1) 的反元素。

55 使用電腦執行乘法運算 在電腦上實作時會使用另一個較好的演算法，它將一個已經分解的多項式重複乘上 x。

56 範例4.22 計算在 GF(28) 下，P1= (x5 + x2 + x) 乘以 P2 = (x7 + x4 + x3 + x2 + x) 的結果，使用不可分解多項式 (x8 + x4 + x3 + x + 1)。 解法：計算的過程列在表4.7。我們先分別算出x0、x1、x2、x3、x4以及x5乘以P2的結果。可以在表中看到，雖然只需要三項，我們還是把xm ⊕ P2的乘積從m = 0算到m = 5，這是因為每一項乘積計算都要用到前一項的結果。

57 表 4.7 一個較有效率的多項式乘法演算法（範例 4.22）
表 4.7　一個較有效率的多項式乘法演算法（範例 4.22）

58 範例 4.23 將範例 4.22 的計算用 8 位元的字組重做一次。 解法：現在 P1 = ，P2 = ，模數為 （9 個位元）。符號代表 XOR 的運 算。見表 4.8。

59 表 4.8　使用 n 位元字組做乘法運算的快速演算法

60 範例 4.24 GF(23) 的體共有 8 個元素。以下我們用不可分解多項式 (x3 + x2 + 1) 列出這個體的加 法和乘法表。該表同時列出 3 位元字組以及多項式的表示法。要注意的是，3 階多項式一共有兩個 不可分解多項式。另一個式子 (x3 + x + 1) 會得到完全不同的乘法表。表 4.9 列出所有的加法運算。

61 表 4.9 GF(23)下的加法表

62 表 4.10 在 GF(23)下對不可分解多項式 (x3 + x2 + 1) 的乘法表

63 4.2.2 使用生成子 有時候使用生成子比較容易找出 GF(2n) 的所有元素。

64 範例 4.25 使用不可分解多項式 f (x) = x4 + x + 1 找出 GF(24) 的所有元素。
解法：0、g0、g1、g2 和 g3 這幾個元素很容易找出來，因為它們剛好就是 0、1、x2 和 x3 的 4 位元 表示式（不需使用多項式除法）。接下來，g4 到 g14（代表 x4 到 x14）等元素就需要用到指定的不可分 解多項式來做除法了。為了要避免多項式除法，我們利用 f (g) = g4 + g + 1 = 0 這個關係式。

65 範例 4.25 (續)

66 範例 4.26 以下我們展示加法和減法運算的結果： a. g3 + g12 + g7 = g3 + (g3 + g2 + g + 1) + (g3 + g + 1) = g3 + g2 → (1100) b. g3 − g6 = g3 + g6 = g3 + (g3 + g2) = g2 → (0100)

67 範例 4.27 以下我們展示乘法和除法運算的結果： a. g9 × g11 = g20 = g20 mod 15 = g5 = g2 + g → (0110) b. g3 / g8 = g3 × g7 = g10 = g2 + g + 1 → (0111)

68 4.2.3 結語 有限體 GF(2n) 可以用來定義 n 位元字組的加減乘除等四則運算。唯一的限制是當除數為零時，結果沒有定義。