ng 3
ươ ệ ậ
ố ứ
Ch H m t mã đ i x ng
ệ
ị
3.1. Đ nh nghĩa h mã
ả ộ ộ 5 (P,C,K,E,D) tho mãn
ạ
ả
ợ
ượ
c g i là không gian b n rõ.
đ
ượ
ạ
ậ
ả
M t h m t mã là m t b ệ các đi u ki n sau: ữ ộ ậ ◦ P là m t t p h p h u h n các b n rõ (PlainText), nó ả ọ ◦ C là t p các h u h n các b n mã (Crypto), nó còn đ
c
ả
ọ
ữ g i là không gian các b n mã. ạ
ữ
ọ
◦ K là t p h u h n các khoá hay còn g i là không gian
ọ ọ
ả
ậ khoá. ộ ◦ E: m t ánh x ộ ◦ D: m t ánh x
ạ KxP vào C, g i là phép l p m t mã. ậ ạ KxC vào P, g i là phép gi
ậ i mã.
ộ ệ ậ ề
ạ ệ ậ
Phân lo i h m t mã
ể ề
ố ứ ệ ộ ự D a vào cách truy n khóa có th phân thành: H mã đ i x ng: dùng chung m t khóa cho quá
i mã.
trình mã hóa và gi ấ ố ứ ệ ả ả H mã b t đ i x ng: khóa mã hóa và gi i mã
khác nhau.
Ngoài ra còn có: h mã c đi n, h mã hi n đ i,
ổ ể ệ ệ ạ
ệ mã dòng, mã kh i. ố
ệ
ẩ
Tiêu chu n đánh giá h mã
ể ệ ậ ườ i ta th ng đánh giá
ậ
ỉ ự
ả
ể
ờ
ế
ả t dk thì không có kh
ộ ườ Đ đánh giá h m t mã ng thông qua các chính sách sau: Đ an toàn: an toàn tính toán
ả i mã
◦ Ch d a vào khóa, công khai thu t toán ◦ B n mã C không có đi m chú ý, gây nghi ng ◦ e(K)=C, d(M)=P. khi không bi C.ừ năng tìm M t ộ ố T c đ mã và gi Phân ph i khóa
ố
ố ứ
Mô hình mã hóa đ i x ng
ố ứ
ể
ặ
ệ Đ c đi m h mã đ i x ng
Khóa ph i gi
ả ữ ườ ở ậ i g i và ng
bí m t gi a ng ả ườ ể ậ
ữ i nh n, hay nói cách khác ph i có kênh chuy n khóa an toàn.
ượ ệ Tính an toàn h mã đ i x ng: đ
ưở c g i là an toàn ặ ờ ọ ng) ho c th i gian
ả ố ứ ể khi không th phá mã (lý t ấ phá mã là b t kh thi.
3.2. Mã Ceasar
ậ ượ ị ủ Hàm l p mã c a mã Ceasar đ ư c đ nh nghĩa nh
sau:
Hàm gi sau:
ả ủ ượ ị i mã c a mã Ceasar đ ư c đ nh nghĩa nh
Mã Ceasar
Mã Ceasar(tt)
ươ ố ư ữ ữ ứ ả B ng t ng ng gi a ch cái và các s d theo
A
B
C
D
E
F
G
H
I
J
K
L
M
0
1
2
3
4
5
6
7
8
9
10
11
12
N
O
P
Q
R
S
T
U
V W X
Y
Z
13
14
15
16
17
18
19
20
21
22
23
24
25
modulo 26.
Ví dụ
wewillmeetatmidnight
ế
ả
ớ
ạ
ả
ố
Cho b n r (plaintext): Dãy s t 22 4 22 8 11 11 12 4 4 19 0 19 12 8 3 13 8 6 7 19 q N u mã hóa v i k=11 thì b n mã là: 7 15 7 19 22 22 23 15 15 4 11 4 23 19 14 24 19 17 18 4 B n mã cu i cùng có d ng:
HPHTWWXPPELEXTOYTRSE
ứ ả ỏ ố ươ ng ng là:
ậ
Nh n xét
ễ ử ụ ◦ D s d ng
ễ
◦ Thám mã cùng khá d dàng.
ử
ố
S khóa c n th là 25 ầ
ả
ậ
ả
ế
Gi
i thu t mã hóa và gi
i mã đã bi
t
ữ
ế
Ngôn ng plaintext đã bi
ễ t và d đoán.
không an toàn
ế ơ
ả
3.3. Mã thay th đ n b ng (Monoalphabetic Substitution Cipher)
Ví dụ
V i phép hoán v
ớ ị (cid:0) cho b ng sau: ả
ế (cid:0) :
V i h m t mã thay th khóa B n r : hengapnhauvaochieuthubay B n mã: ghsoxlsgxuexfygzhumgunxd
ớ ệ ậ ả ỏ ả
ậ
Nh n xét
ố
ằ ự ị S hoán v khóa: 26! Thám mã b ng duy t t t c các khóa không th c
≈ ệ ấ ả 6.4x1012 năm).
ự ng pháp thám mã d a vào t n su t xu t ể ầ ữ có th đoán đ ượ ấ ấ ả c b n rõ
ượ ≈ ế t (26! 4.1026 ươ ộ M t ph ệ ủ hi n c a các ch cái ừ ả b n mã. t không đ c coi là an toàn
Mã affine(nhân và c ng)ộ
∈ ặ ố ớ Không gian khóa là các c p s (a, b) Z262 v i
gcd(a,b)=1.
Không gian khóa s có: ậ Hàm l p mã:
∅ ẽ (26)*26=12*26=312
Hàm gi
ả i mã:
Ví dụ
ả ỏ hengapnhauchieuthubay
B n r : Dãy s t
ố ươ ứ ng ng:
ớ ượ ả Mã hóa v i khóa k=(5,6) ta đ c b n mã:
patkgdtpgchgyqpuacxpclgw
ế
ự
3.4 Mã thay th đa ký t
ề
ưở Mã Hill Là mã nhi u ký t Ý t
ự ng chính: dùng m ký t ự ả ự ả ỏ ế ế b n r k ti p nhau và ệ ế b n mã. Vi c thay th này đ
ị ươ ế ở ỗ c ự
ượ ế thay th m ký t xác đ nh b i m ph đ
khóa là ma tr n c p mxm.
ượ ng trình tuy n tính, m i ký t ị ố c gán cho 1 giá tr s . ậ ấ
Mã Hill(tt)
Mã Hill đ
ượ ư ị c đ nh nghĩa nh sau:
ả
ị
T
TC
A
(cid:0)
ậ Cách tính ma tr n ngh ch đ o C (
)
ij
ji
1 kdet
...
a n 1
n
a 11 a
a 12 a
a
...
ể
k
det
Tri n khai theo dòng p
Aa pj
pj
(cid:0) (cid:0) (cid:0)
...
j
1
21 ... a
22 ... a
n 2 ... a
...
n
nn
n 1
2
n
ể
ộ
Tri n khai theo c t q
(cid:0)
Ho c:ặ
k
det
iq Aa iq
(cid:0) (cid:0)
i
1
(cid:0)
i
j
)1(
.
V i:ớ
A ij
iA det ỏ
ộ
j ),( B dòng I, c t j
(cid:0) (cid:0) (cid:0)
Ví dụ
11
8
V i m=2, k=
(cid:0) (cid:0) ớ
(cid:0) (cid:0)
7
3 ả ỏ (9, 20), (11, 24) ả
B n r july B n mã: ek (x1,…,xm)=(x1,…,xm)*k mod 26
(cid:0) (cid:0)
(cid:0) (cid:0)
x
9
20
99(
72,60
140
)
)4,3(
(cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0)
11 3
8 7
(cid:0) (cid:0)
11
8
(cid:0) (cid:0)
x
11
24
121(
88,72
)168
)22,11(
(cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0)
3
7
(cid:0) (cid:0)
B n mã: DELW
ả
ậ
ả
ị
Tính ma tr n ngh ch đ o
(cid:0) (cid:0)
K=
(cid:0) (cid:0)
11 3
8 7
(cid:0) (cid:0)
Tính det(k)=11*78*3=1(mod 26) b
d
1
k
k
det(
*)
c
a
(cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0)
7
18
7
8
(cid:0) (cid:0) (cid:0) (cid:0) (cid:0)
23
11
3
11
(cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0)
ả
Gi
i mã
dk (y1, …,ym)=(y1,…,ym)*k1 mod 26
7
18
(cid:0) (cid:0)
x
43
9(
)20
(cid:0) (cid:0) (cid:0) (cid:0) (cid:0)
23
11
(cid:0) (cid:0)
7
18
(cid:0) (cid:0)
x
11
22
11
(cid:0) (cid:0) (cid:0) (cid:0)
(cid:0)24
(cid:0) (cid:0)
23
11
(cid:0) (cid:0)
ậ
Nh n xét
ệ t b n mã thì vi c thám mã khó khăn.
ệ ế Ø N u ch bi ế Ø N u bi t khác
ặ i d ng m c p phân bi ả ỉ ế ả ế ả ỏ ướ ạ t b n r d ả ỏ ủ nhau c a b n r và b n mã.
Ø Xj=(xj1,xj2,…,xjm)(j=1…m) Ø Yj=(yj1,…,yjm) ậ Ø Ma tr n khóa kmxm có th đ
ả ả
ØK=x1 *y(x kh đ o) ế
ể ượ ừ c tính t ậ ma tr n x,y
Ø N u x không kh đ o thì c tìm m c p b n r khác
ả ỏ ả ả ặ ố
ế
ả
ừ ự ệ ộ
3.5 Mã thay th đa b ng vigenere ự Th c hi n trên t ng b m ký t
Ví dụ
V i m=6, k=(2, 8, 15, 7, 4, 17)
ớ
ậ
Nh n xét
Đ mã hóa b n tin c n có khóa có chi u dài b ng
ề ả ằ ầ
ể ả
ng v i m t ch cái trong b n rõ có th có nhi u
ể ả
ữ ố
ệ ấ ề phá mã b ng th ng kê ằ c.
Phá mã đ i v i mã vigenere d a trên s l p l
b n tin. ứ ộ ớ ữ ả ch cái trong b n mã ượ ể ự ầ t n su t không th th c hi n đ ự
ố ớ ừ ể ụ ề đ đoán chi u dài khóa, t
ầ ầ ỗ ự ặ ạ i đó tách ượ c mã
ằ ừ ủ c a c m t ả b n mã thành các ph n mà m i ph n đ ả hóa b ng PP đ n b ng.
ơ Không an toàn
3.6 Mã hoán vị
ứ ự ể ượ ữ ả các ch cái trong b n rõ đ đ c
ả ộ Xáo tr n th t b n mã.
ể ự ề ầ ể ệ ị ự Có th th c hi n hoán v nhi u l n đ tăng s
ứ ạ ệ ph c t p cho vi c phân tích mã.
3.7 Mã dòng (stream cipher)
B n rõ đ
ả ượ ị ơ c chia thành các đ n v mã hóa k bit:
ừ ầ khóa K ban đ u có
P p0p1p2.. Pn1 (pi: k bit) ố M t b sinh s ng n nhiên t ằ ẫ ơ ướ ị c b ng đ n v mã hóa:
ớ ơ ị ủ ộ ộ kích th StreamCipher(K) S= s0s1s2… sn1 (si : k bit) ả M i s ng n ngiên xor v i đ i v mã hóa c a b n
ể ượ ả ỗ ố rõ đ đ ẫ c b n mã.
Quá trình gi
ả ượ ự ệ mã đ c th c hi n ng ượ ạ c l i
Mô hình mã dòng
ậ
Nh n xét
T
ự ư ng t nh mã Vigenere hay mã Onetime
ươ Pad. ể ọ ộ
ẫ ọ
ấ ủ Đi m quan tr ng nh t c a mã dòng là b sinh ế ế ả ả
ả ằ ẫ ộ ố
khóa ng n nhiên. N u ch n khóa ngăn thì không ự ế . đ m b o an toàn, n u khóa dài thì không th c t ể Do đó, b sinh s ng n nhiên ph i cân b ng đi m này.
Mã A5/1
ạ ạ ệ ả ả
Dùng trong m ng đi n tho i GMS đ m b o b o ạ m t trong quá trình liên l c gi a ĐT và tr m thu phát vô tuy n.ế ị
ậ ả ạ ữ
Đ n v mã hóa: 1bit ố B sinh s : 0 ho c 1 đ s d ng trong phép xor.
ể ử ụ ơ ộ ặ
Tiny A5/1
ộ
B sinh s g m 3 thanh X(6 bit), Y(8 bit), Z(9 bit), c phân b vào thanh
ượ ố
ượ ế ắ ỗ c bi n đ i qua qui t c sau:
ố ồ ề khóa có chi u dài 23 bit đ ghi: KXYZ. Các thanh ghi đ
Ví d : x=100101, t=1
ụ x= 110010
ị ế ố
Ta đ nh nghĩa hàm “chi m đa s ” nh sau: ế ố ứ
ượ c lai.
T i b
ư maj(x1, y3, z3) =0 n u có hai bit 0, ng ạ ướ c sinh s th i,
Bit si đ ượ
ượ ứ ể ả ớ
c XOR v i bit th i trong b n rõ đ có ứ ả c bit th i trong b n mã. đ
ụ
Ví d : P=111, khóa: 100101. 01001110.100110000
A5/1
Mã dòng A5/1
Mã RC4
ậ ữ ệ
ể ả ữ ứ Dùng trong giao th c SSL đ b o m t d li u ề ả i gi a Web Server và
ệ trong quá trình truy n t trình duy t web
Dùng trong mã hóa WEP c a m ng Wireless
ủ ạ
LAN.
Tiny RC4
ị ơ
Đ n v mã hóa: 3bit ỗ Dùng 2 m ng S và T, m i m ng 8 s nguyên 3bit
ả ả ố
ừ (t
ừ ố
Khóa là m t dãy N s 3bit (N t B sinh s : m i l n sinh ra 3bit đ s d ng trong
ế 1 đ n 7). ể ử ụ ỗ ầ ộ
ế 0 đ n 7). ộ ố phép XOR.
Tiny RC4 (tt)
ở ạ ạ Giai đo n kh i t o
ự
ầ ử ủ
ượ
ị ẫ
c a S đ
c hoán v l n
ầ ử khóa, các ph n t ộ ứ
ẫ
D a trên ph n t ớ nhau v i m c đ ng u nhiên nào đó
Tiny RC4 (tt)
Ví d : mã hóa b n rõ: P= 001000110, K={2, 1, 3}
ụ ả
ượ
Khi i=7 ta đ
c S= 6 0 7 1 2 3 5 4
Tiny RC4 (tt) ạ ố Giai đo n sinh s
ượ
ỗ ướ
ầ ử
ố
ế ụ S ti p t c đ ể
ủ
ọ
ị ạ c hoán v . T i m i b ố ượ
ố
ể
c ch n đ tính ra s k 3bit là s đ
c sinh s hai ph n t ị ớ ơ c dùng đ XOR v i đ n v
ả
ầ ử Các ph n t ượ c a S đ ủ mã hóa c a b n rõ.
ụ ướ
Tiny RC4 (tt). Xét ví d tr
c
ả
ậ
ừ
⊕ V y b n mã C= 001.000.110 101.001.111 = 100.001.001 (t
EBB)
RC4
T
ố
ự ư ặ ớ nh Tiny RC4 v i các đ c tính sau:
ố
ừ 256.
1 ể ử ụ
◦ Đ n v mã hóa: 1byte ồ ◦ M ng S và T g m 256 s 8bit ộ ◦ Khóa K là m t dãy s nguyên 8bit t ố ỗ ầ ◦ B sinh s m i l n sinh 1byte đ s d ng trong phép
ộ XOR.
ượ ng t ị ơ ả
Quá trình sinh s trong RC4 là ng u nhiên, khó đoán ủ
ẫ
ộ ả ướ ầ ậ c đ b o m t cao theo tinh th n c a
ố ạ ượ tr c nên đ t đ mã OneTime Pad.
Mã RC4 hoàn toàn th c hi n đ ộ ử
ượ ự ố c trên s nguyên
ệ ơ ố ố 1byte, t c đ x lý nhanh h n mã kh i
3.8 Mã kh iố
Phép toán XOR có h n ch là ch c n bi
ế ặ ế
ả ố t c p kh i i ta có th d dàng suy ra
ví d :ụ
ạ ườ ả b n rõ và b n mã, ng ể ả khóa và dùng khóa đ gi ỉ ầ ể ễ ố i các kh i mã khác.
N u c=1010, p=1111 thì k= 0101
ế
ố
ưở
Mã kh i an toàn lý t
ng
ố ể ợ ng h p knownplaintext
ườ Đ ch ng phá mã trong tr ỉ ể
ậ ố
hay choosenplaintext, ch có th làm cho p và c ứ ả ọ L p b ng tra c u không có m i liên h toán h c ả ng n nhiên b n rõb n mã.
ầ ặ ả ả ệ ả ế ấ ả Mu n phá mã c n bi t c các c p b n rõb n t t
N u ch n kh i có kích th
ọ ố ẫ ố mã. ế
ế ả
ườ ả ố ướ c 64bit thì s dòng b ng khóa là 264 không th n m h t b ng khóa đ i v i ố ớ ể ắ ng
ưở i phá mã. mã kh i an toàn lý t ố ng
ạ
M ng SPN
ự ế ố ko th xd mã kh i an toàn tuy t đ i.
ế ợ ắ
ả ệ ố ề c ng n + k t h p nhi u ị an
ưở ắ ố ể Trong th c t ướ Dùng khóa có kích th ơ mã hóa đ n gi n (phép th , phép hoán v ) ỉ toàn s p x mã kh i lý t ế ng.
ạ
M ng SPN (tt)
ệ ế ợ ạ ặ
Vi c k t h p các hàm Sbox và Pbox t o hai đ c tính quan tr ng là: tính khu ch tán và tính gây nhi u.ễ
ế ọ
Tính khu ch tán: 1bit b n rõ là nh h ả c các bít b n mã (Sbox, Pbox).
ế ả ả ưở ế ấ ng đ n t t
Tính gây nhi u: là ph c t p hóa m i liên quan
ứ ạ ố ả ễ
ữ ả gi a b n mã và khóa (Sbox).
Mô hình mã hóa Feistel
ế ợ ế ề ấ Do Horst Feistel đ xu t: k t h p phép th và
ế ổ ộ ố ể hoán v .ị B n rõ đ t đ i qua m t s vòng đ cho ra
ả ượ ữ ượ c bi ố b n mã cu i cùng. B n rõ P và b n mã C đ c chia thành hai n a Li
ượ ả ả ả và Ri Khóa ki đ ậ c sinh ra theo thu t toán sinh khóa
con
F là hàm mã hóa dùng chung cho t ư
ấ ả t c các vòng,
ế ệ
ư ữ ả ổ F đóng vai trò nh phép thay th , còn vi c hoán ị đ i các n a trái ph i có vai trò nh hoán v .
Mô hình mã hóa Feistel
Mã Tiny DES
ề ủ
Ti n thân là mã Lucifer c a IBM ệ ộ Là mã thu c h mã Feistel 3 vòng ố Kích th c kh i là 8bit Kích th c khóa 8bit ỗ M i vòng dùng khoa con 6bit
ướ ướ
Các vòng Tiny DES
ủ
ấ
C u trúc 1 vòng c a Tiny DES
ậ
Thu t toán sinh khóa con
Khóa K 8 bít ban đ u đ
ử ầ ượ c chia thành 2 n a trái ph i
ướ ỗ ử
ể ượ ị ả ạ c 4 bít. T i vòng c d ch vòng trái 1 bít đ có
c d ch vòng trái 2
i vòng th 3
ượ ị T i vòng th hai KL1 và KR1 đ ạ c KL2 và KR2. T i vòng t ượ ị ạ ể ứ c d ch vòng trái 1 bít đ có KL3 và
Cu i cùng khóa Ki c a m i vòng đ
KL0 và KR0, m i n a có kích th ứ ấ th nh t KL0 và KR0 đ ượ c KL1 và KR1. đ ứ ạ ượ ể bít đ có đ KL2 và KR2 đ KR3. ố ủ ằ
ị
ượ ạ c t o ra b ng ủ ả ồ ế
ỗ cách hoán v và nén (compress) 8 bít c a KLi và KRi (k0k1k2k3k4k5k6k7) thành k t qu g m 6 bít : k5k1k3k2k7k0.
ủ
ộ
Đ an toàn c a DES
ấ
1. T n công vét c n khóa: vì khóa DES có đ dài 56bit, nên đ t n công vét c n khóa c n ki m tra 256 khóa khác nhau.
ạ ể ấ ộ ể ầ ạ
2. Phá mã DES theo PP vi sai: đòi h i 247 c p b n
ặ ả
ả ự ả
3. Phá mã theo PP th tuy n tính: c n bi ả
ế ướ t tr c
ả ả ặ ỏ ọ b t kh thi. ấ rõ, b n mã l a ch n ầ ế ử không kh thi. 243 c p b n rõb n mã
Triple DES
ử ụ ề ầ
ễ ớ S d ng DES nhi u l n v i khóa khác nhau. C=E(D(E(P, K1), K2) K1) Khi K1 = K2 =K thì Triple suy di n thành DES.
Advanced Encryption Standard (AES)
ặ
ướ ọ ớ ậ Là thu t toán mã hóa Rijndael ố ướ Kích th c kh i mã 128, 192 ho c 256 bit ộ ậ ự Cho phép l a ch n kích th c khóa đ c l p v i
ướ kích th
S vòng có th thay đ i t
ố ố ể ế 10 đ n 14 vòng tùy
ướ ộ c kh i: 128, 192 hay 256 bit. ổ ừ c khóa. thu c vào kích th
ứ
ự ủ
ố ứ ả
ự
Tính ch ng th c c a mã hóa ố ứ đ i x ng (authentication) ệ ự ậ Mã hóa đ i x ng th c hi n tính b o m t. Đ i v i tính ch ng th c thì sao? Mã hóa đ i x ng
ử ố ớ ể
ạ ạ ố có th ch ng l m o danh hay phát l ố ứ ứ ệ ổ ạ ấ i t n công s a đ i thông đi p, ệ i thông đi p hay không?
??? Có, gi
ả i thích
ố
ừ
ố
ả ậ
ả ả ố ch i.
ị ế ộ ệ
Tính không t ch i (non ủ repudiation) c a mã hóa đ i ố ứ ả ư Mã hóa đ i x ng đ m b o tính b o m t nh ng x ngứ ừ ả không đ m b o tính không t Nguyên nhân: khóa bí m t Kậ ể N u K b ti t l
thì không th qui trách nhi m cho
ế ai.
ổ
ậ ằ
ả ử ườ
Trao đ i khóa bí m t b ng TTPP khóa Gi s có N ng
ổ ữ ệ i dùng, trao đ i d li u b ng mã ầ ậ ằ ố ứ c n N(N1)/2 khóa bí m t. hóa đ i x ng
Key Distribution Center – KDC
ườ ậ ớ ỗ M i ng
ỉ ầ ổ ữ ệ ườ ể ớ i dùng ch c n 1 khóa bí m t v i KDC, i dùng do
còn khóa đ trao đ i d li u v i ng KDC cung c p.ấ
Trao đ i khóa bí m t dùng KDC
ậ ổ
