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

Slides:



Advertisements
Similar presentations
工職數學 第四冊 第一章 導 數 1 - 1 函數的極限與連續 1 - 2 導數及其基本性質 1 - 3 微分公式 1 - 4 高階導函數.
Advertisements

不定積分 不定積分的概念 不定積分的定義 16 不定積分的概念 16.1 不定積分的概念 以下是一些常用的積分公式。
大綱 1. 三角函數的導函數. 2. 反三角函數的導函數. 3. 對數函數的導函數. 4. 指數函數的導函數.
從一付卜克牌 (52 張 ) 中,任選 5 張牌,有幾種組合? 《一對》兩張相同數字的牌和三張不同數字的牌所組成 。 《兩對》有兩對兩張相同數字的牌和一張不同數字的牌所 組成。 《三條》由三張相同數字的牌和兩張不同數字的牌所組成。 《順子》連續性的五張牌所構成的牌型。含有A的五張連 續牌,A必須為首或居末位,才算是順子。
變數與函數 大綱 : 對應關係 函數 函數值 顧震宇 台灣數位學習科技股份有限公司. 對應關係 蛋餅飯糰土司漢堡咖啡奶茶 25 元 30 元 25 元 35 元 25 元 20 元 顧震宇 老師 台灣數位學習科技股份有限公司 變數與函數 下表是早餐店價格表的一部分: 蛋餅 飯糰 土司 漢堡 咖啡 奶茶.
Chapter 4 集 合.
數位邏輯設計與實習 Ch02基本邏輯閘與布林代數.
圓的一般式 內容說明: 由圓的標準式展出圓的一般式.
圓的一般式 內容說明: 由圓的標準式展出圓的一般式.
08 CSS 基本語法 8-1 CSS 的演進 8-2 CSS 樣式規則與選擇器 8-3 連結HTML 文件與CSS 樣式表
遞迴關係-爬樓梯.
分式的乘除.
第十六章 分 式 分式的乘除(1
Chapter 6 資料加密標準. 學習目標 回顧 DES 的發展歷史。 定義 DES 的基本結構。 描述 DES 建構元件的詳細情形。 描述回合金鑰產生程序。 分析 DES 。
§1 线性空间的定义与性质 ★线性空间的定义 ★线性空间的性质 ★线性空间的子空间 线性空间是线性代数的高等部分,是代数学
認識倍數(一) 設計者:建功國小 盧建宏.
第四章 數列與級數 4-1 等差數列與級數 4-2 等比數列與級數 4-3 無窮等比級數 下一頁 總目錄.
陳維魁 博士 儒林圖書公司 第九章 資料抽象化 陳維魁 博士 儒林圖書公司.
5.1 自然對數函數:微分 5.2 自然對數函數:積分 5.3 反函數 5.4 指數函數:微分與積分 5.5 一般底數的指數函數和應用 5.6 反三角函數:微分 5.7 反三角函數:積分 5.8 雙曲函數.
主題五 CPU Learning Lab.
簡易C++除錯技巧 長庚大學機械系
本章大綱 9.1 Sequence數列 9.2 Infinite Series無窮級數
4B冊 認識公倍數和最小公倍數 公倍數和最小公倍數的關係.
C語言簡介 日期 : 2018/12/2.
SQL Stored Procedure SQL 預存程序.
元素替换法 ——行列式按行(列)展开(推论)
以下這個謎題無法透過宮摒除法完成解題。 但可透過「區塊宮摒除法」或「行列摒除法」完成 By TTHsieh
十字交乘法 多項式乘積: (X + 3)×(X+2) =X2 +2X +3X + 6 =X2+ 5X + 6 因式分解:
1.3 在整除性問題之應用 附加例題 3 © 文達出版 (香港 )有限公司.
Chap3 Linked List 鏈結串列.
第一章 直角坐標系 1-1 數系的發展.
THE CHINESE UNIVERSITY OF HONG KONG EDD 5161R
Ch2多項式函數 2-2 多項式的運算與應用 影音錄製:陳清海老師 資料提供:龍騰文化事業股份有限公司.
Ch2多項式函數 2-2 多項式的運算與應用 影音錄製:陳清海老師 資料提供:龍騰文化事業股份有限公司.
基本電學 資訊科杜文淵老師.
學習單元:N6 數的性質 學習單位:N6-3 用短除法求H.C.F. 和 L.C.M. 學習重點 : 1. 複習因數分解法求
Definition of Trace Function
小學四年級數學科 8.最大公因數.
我 會 數 數.
CH05. 選擇敘述.
大綱:加減法的化簡 乘除法的化簡 去括號法則 蘇奕君 台灣數位學習科技股份有限公司
微積分網路教學課程 應用統計學系 周 章.
小數除法.
 多項式的除法 x3 + 2x2 – 5x + 6 = (x – 1)(x2 + 3x – 2) + 4 被除式 除式 商式 餘式
C qsort.
流程控制:Switch-Case 94學年度第一學期‧資訊教育 東海大學物理系.
MiRanda Java Interface v1.0的使用方法
多項式 數三甲 吳敬平.
第12讲 代数结构的概念和群 主要内容: 1.了解代数结构、半群、独异点、子代数、代数同态与同构的定义.
10394: Twin Primes ★★★☆☆ 題組:Problem Set Archive with Online Judge
※歡迎挑戰,兩人(隊)中先完成連線即算過關!
Commando War ★★☆☆☆ 題組:Problem Set Archive with Online Judge
例題 1. 多項式的排列 1-2 多項式及其加減法 將多項式 按下列方式排列: (1) 降冪排列:______________________ (2) 升冪排列:______________________ 排列 降冪:次數由高至低 升冪;次數由低至高.
1-1 二元一次式運算.
1757: Secret Chamber at Mount Rushmore
13194: DPA Number II ★★☆☆☆ 題組:Problem Set Archive with Online Judge
資料表示方法 資料儲存單位.
第一章 直角坐標系 1-3 函數及其圖形.
非負矩陣分解法介紹 報告者:李建德.
計算機程式設計 老師:謝孟諺 助教:楊斯竣.
2.1 一元一次不等式 定 義 設a、b為兩個實數。.
線段圖 台南師範學院數學系 葉啟村.
String類別 在C語言中提供兩種支援字串的方式 可以使用傳統以null結尾的字元陣列 使用string類別
10303: How Many Trees? ★★☆☆☆ 題組:Contest Archive with Online Judge
11621 : Small Factors ★★☆☆☆ 題組:Problem Set Archive with Online Judge
快取映射 之直接對映 計算整理.
§2 自由代数 定义19.7:设X是集合,G是一个T-代数,为X到G的函数,若对每个T-代数A和X到A的函数,都存在唯一的G到A的同态映射,使得=,则称G(更严格的说是(G,))是生成集X上的自由T-代数。X中的元素称为生成元。 A变, 变 变, 也变 对给定的 和A,是唯一的.
ABC ( )已知 ,則下列哪些是x6-7x5-8x4 的因 式?(複選) (A) x+1 (B) 2x+2 (C) x3(x+1)
第三章 比與比例式 3-1 比例式 3-2 連比例 3-3 正比與反比.
Presentation transcript:

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

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

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

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

圖 4.1 常見的代數結構

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

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

圖4.2 群

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

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

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

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

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

圖 4.3 排列運算的合成 (範例 4.4)

表 4.2 排列群的運算表

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

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

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

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

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

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

循環群 若一個群為本身的循環子群,則稱為循環群(cyclic group)。

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

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

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

範例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。

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

圖4.4 環

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

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

圖4.5 體

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

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

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

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

表 4.3 代數結構總整理

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

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

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

圖 4.8 GF(22) 體的例子

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

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

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

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

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

表 4.4 不可分解多項式列表

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

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

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

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

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

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

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

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

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

範例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,這是因為每一項乘積計算都要用到前一項的結果。

表 4.7 一個較有效率的多項式乘法演算法(範例 4.22) 表 4.7 一個較有效率的多項式乘法演算法(範例 4.22)

範例 4.23 將範例 4.22 的計算用 8 位元的字組重做一次。 解法:現在 P1 = 000100110,P2 = 10011110,模數為 100011010(9 個位元)。符號代表 XOR 的運 算。見表 4.8。

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

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

表 4.9 GF(23)下的加法表

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

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

範例 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 這個關係式。

範例 4.25 (續)

範例 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)

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

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