傳統密碼技術

古典技術

現代技術

進階加密演算法特性

Key管理與亂數

AES介紹

古典技術

資訊隱藏

只利用取代技巧的加密法

只利用置換技巧的加密法

傳統加密模型（一）

Encryption

Algorithm

(e.q. DES)

Decryption

Algorithm

(reverse of

encryption

algorithm)

傳送用的密文

Plaintext

明文

Plaintext

明文

KEY

KEY

KEY:編碼與解碼都用同一個KEY，整個系統的保密性都依賴

KEY的保密（保密方法通常是公開的）

傳統加密模型（二）

信息

來源

加密演算法

密碼來源

密碼

K

解密演算法

收信端

安全的管道

X

Y

X

意圖

破密者

X

K

加密系統分類

將明文轉為密文的方法：取代（substitution）、置換（transposition）。加密運算必須是可逆的。

取代：明文中的每一個元素被對應到另一個元素

置換：將明文中的元素重新排列

Key使用的個數：

對稱的、單一鑰匙、私密鑰匙（private key）

Public key

處理明文的方式：

資料區段加密（block cipher）：一次處理一段資料

資料流加密（stream cipher）：一次處理一個元素

密碼系統的目標

達到「計算上的安全」（computationally secure)

破解密文所需的成本超過被加密訊息本身的價值

破解密文所需的時間超過這個信息的有效壽命

暴力法破解密碼所需時間，不過很多人選擇

key（密碼）並不是真的有那麼多可能性

資訊隱藏

把訊息或資料安排在看起來很正常文件中

用不可見的墨水

在字元上作記號

藏在數位相片每個像素的最低位元

藏在數位音樂每個取樣的最低位元

相較起來，要費比較大的功夫才能隱藏一點資訊。

但是擷取或檢查信息的人未必知道收發雙方正傳遞秘密信息（間諜應該很喜歡這種工具）

只利用取代技巧的加密法

Caesar加密法：每個字母用其後的第N個字母來取代，很容易用暴力法破解。

Monoalphabetic加密法：允許任意的字母取代方式，較難破解，可用語言統計來加速破解。

Playfair加密法：將雙字元明文視為單一文字，再轉為雙字元密文。這是第一次世界大戰英國陸軍標準密碼系統。

Polyalphabetic與Vigenere加密法：同時使用好幾個Monoalphabetic加密法，Vigenere用了26個Caesar加密法

相關程式 http://starbase.cs.trincoll.edu/~crypto/cryptoappletj/

只利用置換技巧的加密法

柵欄法 rail fence

旋轉機 Rotor Machines（第二次世界大戰中，德軍與日軍使用的技術）

多階段的加密會讓密碼更難破解

參考課本第二章53-56頁

現代技術

DES

Triple DES

IDEA國際資料加密演算法

Blowfish

RC5

CAST-128

RC2

DES加密法（一）

1970年代由IBM發展出來

1977年由美國國家標準局（NBS）採用為資料加密標準（DES）

2000年10月2日NIST宣佈AES（Advanced Encryption Standard)為新的資料加密標準

1997年在96天內透過網路上超過七萬台機器的合作下暴力破解了DES密碼

DES解密程序跟加密程序一樣，只是子key Kn 必須反過來。

DES加密法（二）

Initial permutation

Permuted Choice 1

Round 1

Permuted Choice 2

Left circular shift

Round 2

Permuted Choice 2

Left circular shift

Round 16

Permuted Choice 2

Left circular shift

32-bit swap

Inverse Initial

permutation

K1

K2

K16

64-bit plaintext

56-bit key

64-bit ciphertext

DES加密法（三）

R (32 bits)

E

48 bits

+

K (48 bits)

S1

P

32 bits

L (32 bits)

+

Rnext (32 bits)

Lnext (32 bits)

6bits

4bits

DES一個round的架構

S2

S3

S4

S5

S6

S7

S8

Triple DES（一）

通常使用兩把key的triple DES

C=Ek1[Dk2[Ek1[P]]] 第二次用解密的方式是為了與傳統DES相容：C=Ek1[Dk1[Ek1[P]]]=Ek1[P]

DES-E

DES-D

DES-E

明文

密文

K1

K2

K1

DES-D

DES-E

DES-D

密文

明文

K1

K2

K1

Encryption

Decryption

Triple DES（二）

使用三把key的triple DES

C=Ek3[Dk2[Ek1[P]]] K3=K2 或K1=K2的狀況下與傳統單一DES相容。

PGP與S/MIME使用三key的 triple DES

IDEA加密法（一）

由瑞士聯邦技術協會發展出來

Key 長度為128 bit，加密的資料區段為64 bit

特點：key比較長，可以對抗暴力破解法

混淆（讓文字統計特徵不見）與擴散度（明文與key中的某一位元都影響密文中的許多位元）不錯

解密方法與加密方法相同，只有subkey選取方式不同（同一套系統可以加解密）

IDEA加密法（二）

Round 1

Round 2

Round 8

Output Transformation

X1

X2

X3

X4

64位元明文

W11

W12

W13

W14

W21

W22

W23

W24

W71

W72

W73

W74

W81

W82

W83

W84

Y1

Y2

Y3

Y4

64位元密文

K1

K6

K7

K12

K43

K48

K49

K52

Subkey Generator

128位元KEY

K1

K52

16bits

16bits

W81

W82

W83

W84

Y1

Y2

Y3

Y4

K49

K50

K51

K52

Output Transformation

X1

X2

X3

X4

K1

K2

K3

K4

K6

K5

W11

W12

W13

W14

一個round的構造

XOR

Mod 216的加法

Mod 216+1的乘法

Blowfish加密法（一）

由Bruce Schneier 發展出來

特性

快速：用32位元的處理器來加密一位元組只需18個時脈

小巧：記憶體5K以下就能運作

簡單：架構簡單易於實作

可變的安全性：key長度可變，可由32到448位元

將64位元明文區段加密成64位元的密文區段

subkey的產生比較複雜，不適用於key常常變化的場合，通常subkey計算完後就存起來，所以需要4K的記憶體來存subkey

Blowfish加密法（二）

S1

S2

S3

S4

+

+

P1

L0

R0

L1

R1

64 bit明文

S1

S2

S3

S4

+

+

P16

L16

R16

P18

P17

64 bit密文

32bit

32bit

8bit

32bit

32bit

XOR

+

ADD

解密時只要subkey

順序反過來即可

Blowfish加密法（三）

Blowfish很難破解（可能是這幾種傳統加密法中最難破解的）

執行速度：加密一byte所需要的時脈週期

Blowfish	18

RC5	23

DES	45

IDEA	50

Triple-DES	108

RC5加密法（一）

由Ron Rivest所發展出來

明文區段位元數可變(16,32,64)，適合於字元長度不同的處理器

可變的回合數(0-255)與key長度(0-255 byte)

簡單且記憶體的需求少

已經被RSA公司納入產品：BSAFE、JSAFE、S/MAIL

通常用 RC5-32/12/16(明文區段32 bit 12 回合 key 16 byte）

RC5加密法（二）

+

+

<<<

+

2wbit明文

+

<<<

+

+

Round 1

S[1]

S[0]

S[3]

S[2]

+

<<<

+

<<<

+

+

Round r

S[2r+1]

S[2r]

2wbit密文

-

+

>>>

-

2wbit明文

+

>>>

-

-

Round 1

S[1]

S[0]

S[3]

S[2]

+

>>>

+

>>>

-

-

Round r

S[2r+1]

S[2r]

2wbit密文

+

Add

-

減法

+

XOR

<<<

Left circular

rotation

>>>

Right circular

rotation

加密

解密

Key將被轉換為

2r+2把subkey

CAST-128加密法

CAST是由Carlisle Adams與Stafford Tavares所發展出來的演算法。

key長度由40-128 bits（每次增減8 bits）

PGP也使用CAST

CAST共有16個回合，輸入64bit明文區段，輸出64bit密文區段。

CAST每回合用兩個key：一個32 bits，一個 5 bits。

加解密函數的運作方式與第幾回合相關

參考課本4.5節

RC2加密法

由Ron Rivest所發展出來

明文密文區段位元數都是64

key長度可變:8-1024 bits

適合用16位元微處理器實作

Key長度 40,64,128 bits的RC2已經用在S/MIME協定中

具有選擇性的key-weekening程序

進階對稱式資料加密法特性

Key長度可變：Blowfish,RC5,CAST-128,RC2

混合運算:IDEA,Blowfish,RC5,CAST-128,RC2

與資料(RC5)或key(CAST-128)相關的移位輪轉運算

與key相關的S 盒:Blowfish

冗長的key產生方式:Blowfish

可變的F:CAST-128

可變的明文、密文區段:RC5

可變的回合數:RC5

同時改變兩段資料:IDEA,Blowfish,RC5

Key管理（一）

一個密碼系統的強度在於分送key的技術，假設A,B要通訊

A選好key，手動送交B

第三者選好key，手動送交A,B

A,B使用之前通訊的舊key，將新key加密送給對方

A,B可與第三者做保密的通訊，則第三者可用此保密的通訊管道傳送key給A,B雙方

Key distribution center

Master key:user與中心交換session key用的key

Session key：user通訊時使用的key，用完即捨棄

Session key的生命週期：太長容易被破，太短則浪費時間

KEY管理（二）

典型案例:

Ka:A與KDC的key

Kb:B與KDC的key

Ks:session key

KDC

發起人A

收信者B

1.A要求KDC給予session key

並提供亂數N1

2.KDC用Ka加密，提供Ks並附

帶原始的請求信息供A確認信

息來自KDC(依賴N1)

並提供用Kb加密的Ks與A的

資料

3.A存下Ks並把Kb加密的資料

送給B

4.B送用Ks加密的亂數N2給A

5.A回應用Ks加密的信息f(N2)

(對N2做一點處理）給B

1Request||N1

2.EKa[Ks||Request||N1||EKb(Ks,IDA)]

3.EKb[Ks,IDA]

4.EKs[N2]

5.EKs[f(N2)]

亂數產生器（一）

亂數（random number）：隨機性、不可預測性

隨機性：平均分佈、獨立性（數字不能由其他數字推導而得）

不可預測性：下一個數字無法由前一個數字推導而得

虛擬亂數（pseudorandom number):並非真正的亂數，是由明確的演算法產生，所以不是隨機的。但可以通過很多合理的隨機測試。

目前最廣泛使用的亂數產生器是Linear congruential method (線性同餘法）

亂數產生器（二）

Linear congruential method(線性同餘法）：

Xn+1=(aXn+c)mod m

X0 :啟始值、seed

函數必須是全週期函數（重複前必須產生0到m間所有的數字）

產生的序列看起來要像是隨機的

要有效率

常用：Xn+1=(16807Xn)mod (2^31-1)

不過seed X0選定後，後面的數字都已經決定了

m>0

0<=a<m

0<=c<m

0<=X0<m

亂數產生器（三）

ANSI X9.11

DTi:64bits日期時間

Vi:Seed

Ri:第i個亂數

K1,K2:key of Triple-DES

加密演

算法

計數器

Master

Key

亂數

EDE

EDE

EDE

K1,K2

DTi

Vi

Ri

Vi+1

簡單的密碼方法亂數

產生器

亂數產生器（四）

Blum Blum Shub(BBS)產生器

取兩大質數 p,q p,q除以4都要餘3

n=pq 再選定一個與n互質的亂數s，使p,q都不是s的因數

演算法：

X0=S2 mod n

Xi=(Xi-1)2 mod n

Bi=Xi mod 2

AES 介紹（一）

2000年10月2日NIST宣佈Rijndael為AES （Advanced Encryption Standard)新的資料加密標準。

key長度可變、明文區段可變。Key與明文區段可以分別被定義為128,196,256 bits。

不需要快速的硬體，也不需要大量的記憶體（可以實作在smart card上）。回合轉換可以平行處理。

Nb可由資料區塊長度除以32位元求得，也就是把資料分割成Nb個區塊。

Nk可由Key長度除以32位元求得，也就是把Key分割成Nk個32位元的sub-Key。

參考http://dado.thu.edu.tw/research/p1/Rijndael加密法.htm

AES 介紹（二）

運算的回合數(Nr)是由Nb及Nk所決定的

加密演算法是由一個initial Round Key addition，Nr-1個回合運算，及一個final round所組成

缺點：加解密使用不同的表格與編碼，且解密速度比加密慢。

傳統密碼技術

tjm

1998-09-08T14:53:16