網路與多媒體實驗 第一組報告 B88901166 鄧鎮海 B87409003 葉穎達 　好孩子的 　　 密碼學教室 網路與多媒體實驗 第一組報告 　　B88901166 　鄧鎮海　B87409003 葉穎達　

摘要 什麼是密碼學? 密碼從頭說—定義與理論 牛刀小試—基本的加解密方式 好孩子原則 AES Reference

以下省略… 什麼是密碼學？ 灰姑娘的故事： 很久很久以前，有一個女孩子名字叫做仙度瑞拉… 從此，仙度瑞拉與王子過著快樂的日子。 可喜可賀，可喜可賀！

密碼從頭說—演出人員 plaintext (舞會中的灰姑娘) ciphertext (平常的灰姑娘) cryptographer　(南瓜仙女) enemy　(壞心後母三人組) enciphering、encryption　(12點整的南瓜魔法) deciphering、decryption　(試穿玻璃鞋) keyspace K　(各式各樣的玻璃鞋) key pair (e , d )　(灰姑娘的腳ㄚ，玻璃鞋)

密碼從頭說—基本理論 基本原則—向量空間的轉換 定義：一個密碼系統，由一個加密轉換關係 之集合{Ee : e  K } ，以及一個對應的 {Dd : d  K } 所構成。

密碼從頭說—基本理論 enciphering ƒ:M S deciphering ƒ-1:S M

密碼兩國論 對稱式(單鍵) : (e.g. AES、DES、3DES) 定義 ： 如果在一個密碼系統中，對每一對鑰匙 　　　　　（e , d ），只要知道鍵值 d（e），即可 　　　　　經由「簡易計算」求出另一鍵值 e（d） 　　　　　，則稱此系統為對稱式加密系統。 Encryption Decryption Key generator Message Public channel Terminal (receiver) Terminal (transmitter) Secret channel

密碼兩國論 非對稱式(公開金鑰) : (e.g. RSA、ECC) 定義：一個密碼系統，若對每一對鑰匙（e , d ） 　　　　合 d 不可能經由 e 計算而得之特性，則稱 　　　　之為非對稱式密碼系統。 Encryption Decryption Key generator Message Public channel Terminal (transmitter) Terminal (receiver)

牛刀小試 —The Hill Cipher 定義：對已知之 r, n  N， 令 K = { e  Mrr (Z/nZ)：A is invertible }，且集合 M = C = (Z/nZ)。則對 m  M, e K ，定義 Ee(m) = me , 以及 Dd(c) = ce−¹ , 其中 c  C . r

The Hill Cipher (Cont.) ( ) ( ) ( ) ( ) Example: e = 1 4 c = e­¹ = 15 6 2 3 16 5 Ee (12,0)=(12,0) 1 4 = (12,22) 2 3 Dd(12,22)=(12,22) 15 6 = (12,0) 16 5 ( ) ( ) ( ) ( )

牛刀再試—Permutation Ciphers 定義：一個對稱式區塊編碼系統，每一區塊長 　　　　度為 r 若其鍵值空間（keyspace）K 　　　　是{1,2,…,r}所有可能排列的集合，則 　　　　稱此系統為排列編碼(Permutation 　　　　Ciphers)系統。

Permutation Ciphers (Cont.) Example: 好 孩 子 密 碼 學 e = 1 2 3 4 5 6 2 3 6 1 4 5 孩 子 學 好 密 碼 ( )

牛刀三試—Rabin Public-Key 鑰匙產生機制： 隨機產生二個相異質數 p，q 。 計算 n = p‧q之值。 n 即為公開金鑰，(p，q)即為私密金鑰。 Example: p = 31 , q = 167 　n = p‧q = 5177 公開金鑰 n = 5177 私密金鑰 (p，q)

The Rabin Public-key (Cont.) 取得B方公開金鑰 n。 將所要傳送之訊息，以{0,1,…,n-1}之間數值加以轉換，得到 m。 計算 c ≡ m² (mod n)。 將 c 傳送給B方。 Example: 欲傳送之訊息 m = 101110 重覆後3位得 m`= 101110110 = (374)10。 (m`)² = 374² ≡ 97 (mod 5177)。

The Rabin Public-key (Cont.) 解密過程： 在模數 n 結構下，尋找四個 m，符合m² ≡ c。 所求之訊息，即為四個數值之一。 Example: 在模數 5177 結構下，符合m² ≡ 97 之值有 　3133 = 110000111101 , 2044 = 11111111100 　374 = 101110110 , 4803 = 1001011000011 只有374符合所求(後三位重覆)

小心壞孩子 好孩子原則 沒有破解不了的演算法 常用演算法都已經公開 投入資源是否合 理

控制演算法的複雜度 好孩子原則 家裡大門有20道鎖 想想John Nash的下場

好孩子原則 慎選你的朋友

保管好你的鑰匙 好孩子原則 一把鎖一把鑰匙 一把鎖很多把鑰匙 很多把鎖很多鑰匙 很多把鎖一把鑰匙

一個加密演算法的例子 運算簡易,速度快,安全性高, 符合好孩子加密原則 Advanced Encryption Standard:由NSA ， 即美國國家安全局所提出 特點: 運算簡易,速度快,安全性高, 符合好孩子加密原則

Step 1. ByteSub Transformation 簡單的MAPPING,得到可逆的排列結果 a0 a4 a8 a12 a1 a5 a9 a13 a2 a6 a10 a14 a3 a7 a11 a15 b0 b4 b8 b12 b1 b5 b9 b13 b2 b6 b10 b14 b3 b7 b11 b15

Step 2: ShiftRow Operation ShiftRow: circularly rotate each row of state array simple wiring a0 a4 a8 a12 a1 a5 a9 a13 a2 a6 a10 a14 a3 a7 a11 a15 ShiftRow a0 a4 a8 a12 a5 a9 a13 a1 a10 a14 a2 a6 a15 a3 a7 a11

Step 3: MixColumn Transformation MixColumn  Matrix multiplication of state array columns a4 a5 a6 a7 b4 b5 b6 b7 a0 a4 a8 a12 a1 a5 a9 a13 a2 a6 a10 a14 a3 a7 a11 a15 b0 b4 b8 b12 b1 b5 b9 b13 b2 b6 b10 b14 b3 b7 b11 b15 C(x) mod x4+1

Step 4: Round Key Addition KeyAdd: byte-by-byte XOR of round key and statebi=ai^ki a0 a4 a8 a12 a1 a5 a9 a13 a2 a6 a10 a14 a3 a7 a11 a15 k0 k4 k8 k12 k1 k5 k9 k13 k2 k6 k10 k14 k3 k7 k11 k15 b0 b4 b8 b12 b1 b5 b9 b13 b2 b6 b10 b14 b3 b7 b11 b15 =

Reference An Introduction to Cryptography 密碼學與網路安全 Richard A. Mollin 密碼學與網路安全 Discrete and Combination Mathematics “Advanced Encryption Standard (AES)”, Federal Information Processing Standards Publication 197 (FIPS 197), Nov 26, 2001.

Matlatb Simulation Demo