Chapter 1: 概論 1.1 密碼學術語簡介及假設

Presentation on theme: "Chapter 1: 概論 1.1 密碼學術語簡介及假設"— Presentation transcript:

1 Chapter 1: 概論 1.1 密碼學術語簡介及假設
密碼學(Cryptology)一詞乃為希臘字根"隱藏" (Kryptós) 及 "訊息" (lógos) 組合而成，現泛 指所有有關研究秘密通訊之學問(包括如何達到秘密通訊及破解秘密)。 國際密碼研究學會 (International Association for Cryptologic Research) 簡稱IACR。 IACR於1981年成立 現每年五月於歐洲舉辦一次學術研討會，稱為EUROCRYPT。 每年八月於美國舉辦學術研討會，稱為CRYPTO 每兩年於亞洲舉辦ASIACRYPT。 Cryptology可分為兩個領域： 密碼學 (Cryptography) 破密學 (Cryptanalysis)

2 資訊安全 = 資訊加密 ? 鳳遊禾蔭鳥飛去 馬走蘆邊草不生 k Julius Caesar: k = 3 -k 西方
Ek(x) = x + k mod 26 Dk(y) = y - k mod 26 西方 -k 紀曉嵐(清朝): 鳳遊禾蔭鳥飛去 馬走蘆邊草不生 東方 狹義： 保護資訊（密碼學） 廣義： 達成資訊的安全性、完整性、可用性 （密碼學＋應用系統＋系統環境） 安全性：防制非法揭露或得到資料 完整性：防制非法更改資料 可用性：防制系統拒絕合法之存取資料

3 荷蘭人Kerckhoff ( ) 曾對密碼系統做了下列假設： 一密碼系統之安全性必須僅依賴其解密金匙，亦即在一個密碼系統中除解密金匙外，其餘的加／解密 器等方法，均應假設為破密者完全知道。 祇有在這個假設下，破密者若仍無法破解密碼系統，此系統方有可能被稱為安全。

4 密碼系統提供下列功能： 1. 秘密性 (Secrecy or Privacy)：防止非法的接收者發現明文。 2. 鑑定性 (Authenticity)：確定資訊來源的合法性，亦即此資訊確實是由發送方所傳 送。而非別人偽造，或利用以前的訊息來重送。 3. 完整性 (Integrity)：確定資訊沒有被有意或無意的更改，及被部份取代、加入或刪 除等等。 4. 不可否認性 (Nonrepudiation)：發送方在事後，不可否認其傳送過之資訊。 傳統的密碼學往往僅注重資訊的秘密性。但近代密碼學認為資訊的鑑定性、完整性 及不可否認性，在商業上的應用比秘密性更重要。

5 Secret key cryptosystems vs Public key Cryptosystems
If k1=k2  symmetric key cryptosystem (對稱), one-key system, secret key system (私密密碼系統) 例子: DES, AES, webmail ID/ password, GSM pin Authentication, privacy, integrity 缺點: 金鑰分配, 金鑰管理, 無法達成不可否認性 If k1≠k2  asymmetric key cryptosystem (非對稱式), two-key system, public key system 例子: RSA, Elgamal, D-H key Authentication, privacy, integrity, non-repudiation 缺點: 速度慢

6 秘密金匙密碼系統具有下列缺點： 收發雙方如何獲得其加密金匙及解密金匙﹖這個問題稱為金匙分配問題。若收發雙 方互不認識時，此問題尤其嚴重。 當我們暫不考慮金匙分配問題時，可假設發送方與接收方有一條安全通道 (Secure Channel) 來傳遞金匙。較完整的秘密金匙密碼系統如圖1.2所示。 圖1.2： 秘密金匙密碼系統方塊圖

7 3. 金匙的數目太大： 若網路中有n人，則每一人必須擁有n-1把金匙。網路中共需有{n(n-1)}/2把不同的 金匙。當n等於1000時，每人須保管999把金匙。網路中，共需有499500把不同的 金匙。如何管理這麼多的金匙，也是一大問題。 4. 無法達到不可否認性服務

8 Public key cryptosystem
加密C=Ek1(M) 簽章S=Ek2(M)

9 破密者以其在密碼系統中所獲得的資訊，依其層次可以有下列三種可能的破解方式：
密文攻擊法 (Ciphertext-OnlyAttack)：破密者祇能截收到密文C，欲由密文直接破解出明 文。 2. 已知明文攻擊法 (Known-Plaintext Attack)：破密者擁有一些明文─密文對{m1,c1}， {m2,c2}，…，{mi,ci}，欲由這些明文─密文對，求出解密金匙k2，或求出下一個密文Ci+1。 明文攻擊法中，假設破密者對其所擁有之明文─密文對裡的明文 (或密文)，並無選擇或 控制的能力。例如，破密者可從通道中得到一些密文c1 ,c2 , ... , ci。他當時雖無從得知對 應之明文m1 ,m2 , ... , mi。但過些時日這些明文可能因為時限已過，不需再隱藏秘密，而 被解密公佈出來。如此破密者就可獲得這些明文─密文對。 3. 選擇文攻擊 (Chosen-TextAttack)：在選擇文攻擊時，假設破密者對明文 (或密文) 可以有選 擇或控制的能力。因此他可選擇一些他認為最容易破解之明文一密文對而對密碼系統加 以攻擊。此攻擊方式又分為： 選擇明文攻擊 (Chosen-Plaintext Attack)：破密者可選擇明文 m1 , m2 , ... , mi ，由密碼系統 將之加密為C1 , C2 , ... , Ci， 並送回給破密者。破密者據此進行攻擊。 選擇密文攻擊 (Chosen-Ciphertext Attack)：破密者選擇一些密文，而密碼系統將之解密 為明文 (可能並無任何意義)，並送回給破密者。破密者據此進行攻擊。 雖然很多密碼系統，均希望破密者最多祇能利用密文攻擊法攻擊此系統。但現在的密碼系統 至少必須禁得起選擇文攻擊，方可稱得上安全。尤其是公開金匙密碼系統 (如下一節所 述)。由於加密金匙是公開的，任何人均可利用加密金匙將任何明文加密以獲得密文，以 進行選擇明文攻擊。

10 Ciphertext-only attack Eve: {c1,…,cn}  K or m1,…,mn
Known-plaintext attack Eve:(m1,c1),…,(mn,cn)}  K or mn+1 Chosen-plaintext attack Chosen-ciphertext attack m1,…,mn System Eve: K or mn+1 Eve c1,…,cn m1,…,mn System Eve: K or mn+1 Eve c1,…,cn

11 Secret key, master key vs Session key ()

12 Discrete Logarithm Problem (DLP)
y x  y=f(x)=gx :指數函數 y=f(x)=gx  x : 對數函數 x y=f(x)=gx mod p, g, p  x : 離散對數函數(DLP)  NP problem y x p-1

13 Factor Problem (FAC) Given N=p*q, where p and q are large primes
 It is hard (infeasible) to find p or q

14 Diffie Hellman key agreement protocol 1976
未曾謀面的兩人，是可以透過公眾通道，以獲得祇有他們兩人才知道的共同金匙。 Diffie-Hellman Key (D.-H. Key) A B Y1=gx1 mod p Y1 Y2=gx2 mod p Y2 KAB=(Y1)x2 =gx1x2 mod p KAB=(Y2)x1

15 公開金匙密碼系統 缺點: 加解密運算複雜，且速度緩慢。
以著名的公開金匙系統RSA，與秘密金匙系統DES (Data Encryption Standard，數據加密標準) 比較，兩者相差將近 1000倍。 混合型密碼系統 (Hybrid Cryptosystem): 因此，有人建議利用公開金匙系統達成數位簽署，及解決秘 密金匙密碼系統之金匙分配問題。而以秘密金匙密碼系統， 對明文加解密，達到秘密性功能。此種密碼系統稱為。

16 理論安全及實際安全 一密碼系統之安全性很難用理論證明 (事實上證明其為安全很難， 但若此系統不安全，則證明其為不安全很容易)。 Shannon 1949年 理論安全絕對安全 (Perfect Security ) ：指不管破密者截獲多少密 文C，並對之加以分析，其結果是與直接猜明文m是一樣的。 Shannon 用理論證明一密碼系統欲達理論安全，必須加密金匙的 長度大於或等於明文的長度。亦即金匙祇用一次，用完即丟。 此種系統稱為一次活頁 (One-Time Pad)系統。此乃沿用二次大戰 時間諜們均派給一本活頁紙 一般認為不適合於實際應用場合。 實際安全(Practical Security) 或計算上安全 (Computational Security): 若一系統之W(n)大到使得具有有限計算能力及記憶體的破密 者﹐無法在合理的時間內破解此系統 W(n) ：所有破解此密碼系統方法中最佳方法所需的最少次數。 已知n位元密文時

17 單向函數及單向暗門函數 定義(1)：單向函數(One-way Function) } 一函數f若滿足下列二條件，則f稱為單向函數(註)。
1. 對於所有屬於f之域的任一x，可以很容易算出f(x)＝ y。 2. 對於幾乎所有(Almost All)屬於f 之範圍的任一y，則在計算上不可能(Computationally Infeasible)求 出x使得y= f(x)。 定義(2)：單向暗門函數 (One-way Trapdoor Function) 一“可逆”函數Ｆ若滿足下列二條件，則Ｆ稱為單向暗門函數。 1. 對於所有屬於Ｆ之域的任一x，可以很容易算出Ｆ(x) = y。 2. 對於幾乎所有屬於Ｆ之範圍的任一y，則在計算上除非獲得暗門，否則不可能求出x，使得x = F - 1(y)，F –1為Ｆ之逆函數。但若有一額外資料z(稱為暗門)，則可以很容易求出x= F -1 (y)。 註：一函數f: X→Y，是指將所有x X值對映至f(x)=y Y，Ｘ稱為f 之域(Domain)，Ｙ稱為f 之範圍 (Range)。

18 滿足赫序函數的條件 單向特性(One-Way) (1).赫序函數必需對任意長度的明文，產生固定長度的赫序函數值
(2).對任意的明文m，赫序函數值h(m)可借由軟/硬體很容易的得到 安全性保障 (3) Pre-image resistant: 由 x=h(m) ，計算 m  不可行 (4) second-image resistant: 由 y=h(m1)及 m1，計算m2 使得 h(m1)=h(m2) 不可行 (5) Collision resistant: 任選 m1≠m2, 使得h(m1)=h(m2)計算上不可行 (1)-(4):弱赫序函數；★(1)-(5):強赫序函數

19 MD5 designed by Ronald Rivest (the R in RSA)
latest in a series of MD2, MD4 produces a 128-bit hash value until recently was the most widely used hash algorithm in recent times have both brute-force & cryptanalytic concerns specified as Internet standard RFC1321

20 MD5 Overview

21 Other Secure HASH functions
SHA-1 MD5 RIPEMD-160 Digest length 160 bits 128 bits Basic unit of processing 512 bits Number of steps 80 (4 rounds of 20) 64 (4 rounds of 16) 160 (5 paired rounds of 16) Maximum message size 264-1 bits

22 Why hash needs these properties?
如果不滿足 pre-image resiatant, (y=h(x)  x) M||h(M||K) B A Eve can derive K 如果不滿足 second-image resistant, (y=h(x)  x’≠x but h(x)=h(x’) M||h(M||K) Bank A Eve can replace with M’||h(M||K) 如果不滿足 collision resistant, (x’≠x  h(x)=h(x’)) If A signs on M and sends (S=EPrA(h(M)), he can later claim it should be (M’, S)

23 王小雲 王小雲 (英：Xiaoyun Wang)於1966年生於中國山東省諸城。她在1987年取得學士學位，1990年取得碩士學位，並於1993年取得山東大學博士學位。畢業後，王小雲於1993年起於山東大學數學系任教，至1995年昇至助理教授一職，並於2001年正式成為教授。現今王小雲在山東大學數學及系統科學系出任研究員及教授。 2004年的國際密碼討論年會 (CRYPTO)尾聲，王小雲及其研究同工展示了MD5、SHA-0及其他相關雜湊函數的雜湊衝撞。所謂雜湊衝撞指兩個完全不同的訊息經雜湊函數計算得出完全相同的雜湊值。跟據鴿巢原理，以有長度限制的雜湊函數計算沒有長度限制的訊息是必然會有衝撞情況出現的。可是，一直以來，電腦保安專家都認為要任意製造出衝撞需時太長，在實際情況上不可能發生。然而，王小雲等的發現打破這個必然性。由於這個發現的突破，王小雲等人受與會群聚的熱烈鼓掌。 2005年2月，王小雲與其同工提出SHA-1雜湊函數的雜湊衝撞。由於SHA-1雜湊函數被廣泛應用於現今的主流電腦保安產品，其影響可想而知。王小雲所提的雜湊衝撞演算法只需少於269步驟，遠少於一直以為所需的280步。 2005年8月，王小雲、姚期智，以及姚期智妻子儲楓(即為Knuth起名高德納的人)聯手於國際密碼討論年會尾聲部份提出SHA-1雜湊函數雜湊衝撞演算法的改良版。此改良版使破解SHA-1時間縮短為263步（原來需要280步）

24 What is the impact? Finding collusions requires less steps, but finding the pre-image is still hard?

25 指數函數 (Exponentiation Function)
令G為有限的乘法群，且g G。指數函數Ex(g)=gx G。 通常我們令G={1,2,…,p-1}，其中p為質數，則Ex(g)=gx mod p 稱為指數函數。 指數函數具有下列特性： 週期性 令序列<Ex(g)>=｛g0,g1,g2,…｝為g所產生(Generate)之序列。 因為G為有限群，Ex(g)不可能不重覆，所以為週期性序列。 當存在最小正整數T，使得ET(g)=gT=1=g0時，我們稱T為g在G中之序(Order)。

26 例六：令p=11，g=2，則序列<Ex(g)>={20,21,22,23,…,2g}={1,2,4,8,5,10,9,7,3,6} 如下列所示
20=1 mod 11，26=9 mod 11 ， 21=2 mod 11，27=7 mod 11 ， 22=4 mod 11，28=3 mod 11 ， 23=8 mod 11，29=6 mod 11 ， 24=5 mod 11，210=1 mod 11 ， 25=10 mod 11。 ∴ T=10 。

27 原根(Primitive Root) 若g G之序T=p-1，則g稱為模p之原根。 當g為模p之原根時，由g所產生之序列<Ex(g)>具有最大週期。 換句話說，具有較高的安全性。 理論證明，對於所有質數p，其原根必定存在。 當g為模p之原根且a與p-1互質時，則ga mod p亦必為模p之原根。 因此，模p之原根個數等於 (p-1)，其中 (p-1)稱為尤拉商數(Euler Totient Function)。表示不大於p-1﹐且與p-1互質之正整數的個數。 例七：在例六中 (10)=4 (事實上與10互質之正整數為1 ,3 ,7 ,9)，因此p=11時共有4 個原根。我們已知2為模11之原根，則21=2 ,23=8 , 27=7 , 29=6，因此2 ,8 ,7 ,6均 為模11之原根。 例七告訴我們，當我們已找到模p之一原根時，則我們可很輕易找到模p之所有原根。 但問題是如何找到第一個模p之原根？尤其是當p很大時。

28 3) 交換律 (Commutative Property)
4) 非對稱性(Asymmetric Property) 5) 乘法反元素 若T為g之序，則對於所有0 <x<T，(gx)*(gT-x)=1。 (gx) (gT-x)互為反元素 gT-1=g-1。 6) 乘法性(Multiplicative Property)

29 快速指數運算演算法存在 當x很大時，存在一種快速指數運算演算法，稱為平方再乘法(Square and Multiply)。當x以二 進位表示時為n位元，即x=(xn-1 ,xn-2 , ... , x1 ,x0)，則可利用以下方法求Ex(g)=gx，其中 xi 0 ,1，0 i n-1 ， 。 此方法共需n-1次平方及 個乘法，其中 為x以二進位表示時1 的個數。平均而言 ， (x在二進位表示時有 個０及 個１)。因此，當x為n位元時，平均需要1.5n-2個乘 法(平方算成一次乘法)。

30 金匙分配系統 (金匙分配協定，Key Distribution System or Protocol，KDS)
金匙分配系統之目的，在於使未曾謀面的兩人能共享 (分配) 一秘密金匙。 一般金匙分配系統，是指能使兩人分配一共用秘密金匙。 會議金匙分配系統(Conference-Key Distribution System，CKDS): 若一金匙分配系統， 能使多人 (超過兩人) 同時共享一秘密金匙，則此系統稱為。 信賴的金匙分配中心 (Trusted-Key Distribution Center，TKDC) ： 金匙分配系統有兩 種型式，即為有第三者協助及不需第三者協助之金匙分配系統。有第三者協助之金匙 分配系統，其第三者必須為可信賴的，我們稱之為可。

31 以指數函數實現 ElGamal 公開金匙分配系統
與PKDS系統相同，令本系統中存在一大質數p及模p之原根g。 1.使用者i任選其私有秘密金匙xi，並求出其公開金匙 2. 使用者j任選一亂數 r 並利用使用者i之公開金匙求出 ， 並將密文C=(C1 , C2)送給使用者i。 3. 使用者i收到密文後，利用其秘密金匙xi求出

32 ElGamal 公開金匙分配系統的特性 1. 本系統為機率式的密碼系統
所謂機率式的密碼系統，是指對同一接收者之公開金匙而言，相同的明文，在不同時間加 密時，可得不同的密文。 與機率式密碼系統相對應的，是確定式密碼系統。典型的確定式密碼系統如RSA。在確定 式密碼系統，相同的明文在不同時間加密一定得相同的密文。 機率式密碼系統之缺點是會產生資料擴充 (Data Expansion)。 2. 本系統加密快，但解密則較慢 本系統加密時可利用事先算(Precomputation)技術以加快加密運算。因為亂數r與明文m無關，發 送方可先計算C1及yir並將之儲存。當明文m輸入時，則僅需要一次乘法即可求出C2。但在解密 時則需要兩次指數運算。