第二章 數與密碼 課前指引 本章中，我們僅針對較基本與現常用資訊軟體有直接關係的數論與常用密碼機制演算法部份做介紹。

Presentation on theme: "第二章 數與密碼 課前指引 本章中，我們僅針對較基本與現常用資訊軟體有直接關係的數論與常用密碼機制演算法部份做介紹。"— Presentation transcript:

1 第二章 數與密碼 課前指引 本章中，我們僅針對較基本與現常用資訊軟體有直接關係的數論與常用密碼機制演算法部份做介紹。

2 章節大綱 2-1 基本數論 2-2 中國餘數定理 2-3 密碼系統 2-4 結語 備註：可依進度點選小節

3 2-1 基本數論(一) 模數運算 模數算數( Modular Arithmetic)
在密碼學中的理論一般是以模數運算(Modular Operation)為基礎以對訊息進行安全機則的演算法設計。 定理1：模數算術的性質：+,-,*

4 2-1 基本數論(二) 平方再乘法(Square-multiplication Method )

5 2-1 基本數論(二) 數論(一) 同餘 定理2(尤拉函數)
令a,b,n為整數，其中，n≠0，a≡nb意為a-b=kn，k為常數。藉此我們亦可以a與b同餘於整數n說明其意。 殘剩集合(Residue Set) 反元素 定理2(尤拉函數) n 6 7 8 9 10 11 12 質因數分解 2*3 23 32 2*5 22*3 ψ(n) 2 4

6 2-1 基本數論(二) 數論(二) 定理3(費馬小定理，Fermat’s little theorem) 定理4(尤拉廣義定理)
定理5(質數，因為質數的神秘與 “獨立性”，正好符合密碼研究裡的安全訴求。)： 在整數系中，質數的個數為無窮的。

7 2-1 基本數論(二) 數論(三) Finite Field，有限場其意為一個定義域的組成元素為有限個，我們稱這種定義「場」(Field)，且這些有限元素的個數稱為維度(Order)。 定理6： 維度 p=qn , n>1 的有限場，若q為質數，則稱為Galois Field (高斯有限場)。一般以GF(p)或者Fp來加以表示(在整數系中一般Zp表示)。

8 2-1 基本數論(二) 數論(三) 一般而言，對於GF(qn)有兩種運用: n=1 與n>1
n=1， GF(p)=GF(q) ，即用於一般的數字運算系統mod p。 n>1， GF(p)=GF(qn) 。因此，GF(qn) 表示在最高項為 ”n-1” 的多項式f(x)係數皆mod q。

9 2-2 中國餘式定理(一) CRT在現代資訊/網路安全與密碼學(加密與解密技巧)的應用亦是扮演極重要的角色。本節的編排定位在對此一定理作概念性/傳載性的介紹與基本原理說明，讀者在未來的需求應用可輔以本節的介紹取其所需。 「今有物不知其數，三三數之賸(剩)二，五五數之賸(剩)三，七七數之賸(剩)二，問物為何？」。這個問題俗稱為「韓信點兵」，也就是數論中的「不定方程問題」(Indeterminate equations)。

10 2-2 中國餘式定理(二) 定理7(中國餘式定理)
令 r1, r2 ,…, rn 為整數。則存在一整數C滿足下列的條件: r1C (mod p1), r2C (mod p2), …,與 rn C (mod pn)， 其中 ：

11 2-3 密碼系統(一) 四大功能 秘密性(Secrecy) 鑑定性(Authentication) 完整性(Integrity)
不可否認性(Non-Repudiation)

12 2-3 密碼系統(二) 通訊方式 點對點加密(End-to-End)

13 2-3 密碼系統(三) 連結加密(Link Enctyption)

14 2-4 結語 本章期藉由所安排數論基礎知識的瞭解，採循序漸進的方式作介紹，相信讀者對於模數世界的運作，應能有較深的認知與學習，也因此對現代密碼的數學基礎/應用不再陌生。

15 本章結束 Q&A討論時間