Bài giảng An toàn an ninh thông tin - Chương 2: Các hệ mật mã - Bùi Trọng Tùng
BÀI 2.
CÁC HỆ MẬT MÃ
Bùi Trọng Tùng,
Viện Công nghệ thông tin và Truyền thông,
Đại học Bách khoa Hà Nội
1
1
Nội dung
• Mật mã (cipher) là gì?
• Nguyên tắc chung của các hệ mật mã
• Hệ mật mã khóa đối xứng
• Hệ mật mã khóa bất đối xứng
2
1
2
1. MẬT MÃ LÀ GÌ?
Bùi Trọng Tùng,
Viện Công nghệ thông tin và Truyền thông,
Đại học Bách khoa Hà Nội
3
3
1.1. Khái niệm mật mã
• Mã hóa (code): biến đổi cách thức biểu diễn thông tin
• Mật mã (cipher): mã hóa để che giấu, giữ mật thông tin
• Mật mã học (cryptography): ngành khoa học nghiên cứu
các phương pháp toán học để mã hóa giữ mật thông tin
• Thám mã (cryptoanalysis): nghiên cứu các phương pháp
toán học để phá vỡ hệ mật mã
• Là công cụ hiệu quả giải quyết bài toán AT-ANTT
Nhưng không phải là công cụ vạn năng
• Trong học phần này, chỉ đề cập đến khái niệm cơ bản và
cách thức sử dụng các phương pháp mật mã
4
2
4
Google
Mail
Truyền tin bí mật
• Bước 1: Trao đổi khóa
• Bước 2: Mã hóa dữ liệu
5
5
Lưu trữ thông tin mật
Alice
Alice
Thiết bị lưu trữ
Alice “hôm nay” truyền tin bí mật cho Alice “ngày mai”
6
3
6
Xây dựng mô hình (mật mã khóa đối xứng)
• Alice và Bob đã chia sẻ thông tin bí
Alice
Bob
mật k gọi là khóa
• Alice cần gửi cho Bob một thông điệp
m (bản rõ-plain text). Nội dung thông
điệp cần giữ bí mật trước quan sát
của Eve (kẻ tấn công, thám mã)
Mã hóa: c = E(k, m)
c: bản mã (cipher text)
• Alice gửi bản mã lên kênh truyền.
Bob và Eve đều thu được thông điệp
này. Chỉ có Bob giải mã để thu được
bản rõ
Eve
Giải mã: m = D(k, c)
• Mật mã khóa đối xứng: dùng khóa k
trong cả hai quá trình mã hóa và giải
mã
7
7
Ứng dụng của mật mã
• Giữ bí mật cho thông tin,
• …và không chỉ vậy…
• Chữ ký số(Digital Signature)
• Liên lạc ẩn danh (Anonymous Communication)
• Tiền ẩn danh (Anonymous digital cash)
• Bầu cử điện tử (E-voting)
8
4
8
Một ví dụ - Mật mã Caesar
• Julius Caesar đưa ra vào thế kỷ thứ 1
trước CN, sử dụng trong quan sự
• Ý tưởng: thay thế một ký tự (bản rõ) trong
bảng chữ cái bằng ký tự (bản mật) đứng
sau nó 3 (khóa) vị trí.
Sử dụng bảng chữ cái vòng
A D, B E, C F,..., X A, Y B, Z C
• Mô hình hóa bằng toán học(Mã dịch vòng)
Khóa 1 ≤ k ≤ 26
Mã hóa: c = (m + k) mod 26
Giải mã: m = (c − k) mod 26
Gaius Julius Caesar
• Dễ dàng bị phá ngay cả khi K thay đổi các
giá trị khác
9
9
Lịch sử phát triển của mật mã học
• Năm 300 TCN, Euclid phát hiện ra số nguyên tố, thuật
toán tìm UCLN của 2 số
• Mật mã Hy Lạp
• Năm 1640 ra đời định lý Fermat nhỏ:
ꢀꢁꢂꢃ = 1 ꢄꢅꢆ ꢇ ∀ ꢇ ꢈà ꢉố ꢊꢋꢌꢍêꢊ ꢎố, 1 ≤ ꢀ < ꢇ
ꢀ
ꢁꢂꢃ và ꢇ là 2 số nguyên tố cùng nhau
10
5
10
Lịch sử phát triển của mật mã học
• Năm 1798, Gauss tiên đoán về sự quan trọng
của việc phân tích hợp số thành các thừa số
nguyên tố
• Năm 1874, William Stanley Jevons (Anh) đưa ra
lời thách thức phân tích hợp số 8616460799.
Năm 1903 Derrick Lehmer (Mỹ) có đáp án
11
11
Lịch sử phát triển của mật mã học
• Năm 1917, Vernam cipher đưa
ra ý tưởng mật mã one-time-pad
sử dụng phép XOR nhưng chưa
được chú ý
• Chiến tranh TG lần 1: sử dụng
các biện pháp can nhiễu sóng
radio khi trao đổi thông tin
• Chiến tranh thế giới lần 2: máy
Enigma được quân phát xít sử
dụng
Bị phá mã bởi lực lượng đồng minh
12
6
12
Lịch sử phát triển của mật mã học
• Năm 1945, Claude Shannon xuất bản sách
“Communication Theory of Secrecy Systems”
• Năm 1949, Claude Shannon công bố lý thuyết Shannon
về mật mã hoàn hảo
• Năm 1976 mật mã DES ra đời
• Tháng 11/1976 Diffie và Hellman công bố bài báo “New
Directions in Cryptography” đặt nền móng cho hệ mật mã
khóa bất đối xứng
• Năm 1977, Ron Rivest, Adi Shamir, Len Adleman giới
thiệu mật mã RSA
Fun fact: Hai nhân vật Alice và Bob được giới thiệu
13
13
1.2. Một số nguyên lý chung của các hệ
mật mã
• Làm cách nào để ngăn cản kẻ khác giải mã?
• Định luật Kerckhoffs: “Một hệ mật mã cần an toàn
ngay cả khi mọi thông tin về hệ, trừ khóa bí mật,
là công khai”
• Tại sao?
14
7
14
Hệ mật hoàn hảo
• Định nghĩa: Hệ mật là hoàn hảo khi và chỉ khi ∀m và
∀c mà Pr(C = c) > 0: Pr(M = m | C = c) = Pr(M = m)
• Bổ đề: ∀ cặp m0, m1 có độ dài như nhau, ∀c
Pr(C = c | M = m0) = Pr(C = c | M = m1)
• Bản mật hoàn toàn không chứa thông tin về bản rõ
• Định lý: Một hệ mật mã là hoàn hảo thì ||K|| ≥ ||M||
15
15
Hệ mật hoàn hảo
• Thử thách tấn công biết trước bản rõ
Thử thách
Tấn công
Sinh khóa k
Sinh m0, m1
m0, m1
Chọn b ∈ {0, 1}
c* = E(k, mb)
c*
Đoán b’ ∈ {0, 1}
• Kẻ tấn công thắng nếu đoán đúng b’ = b
• Hệ mật là hoàn hảo nếu với mọi thuật toán, xác suất kẻ tấn
công đoán đúng là P = ½ không thể phân biệt được bản rõ
nào đã được mã hóa
16
8
16
Lý thuyết Shannon
• Định lý: Một hệ mật có ||M|| = ||K|| = ||C|| là hoàn
hảo khi và chỉ khi:
1. Xác suất xuất hiện của mọi giá trị khóa k là như nhau
2. Tồn tại duy nhất giá trị khóa k sao cho
c = E(k, m)
∀m, ∀c
17
17
An toàn theo tính toán
• Hệ mật hoàn hảo: An toàn vô điều kiện
• Định nghĩa 1: Kẻ tấn công có xác suất phá mã thành công
nhỏ hơn ε trong thời gian t
Có ý nghĩa thực tế, nhưng
Phụ thuộc vào sự phát triển phần cứng tính toán
• Với mọi thuật toán hiệu quả (độ phức tạp đa thức) thì xác
suất phá mã thành công ε là không đáng kể
Không phụ thuộc vào sự phát triển của phần cứng tính toán
Xác suất không đáng kể trong thực tế: ≤2-80
Xác suất đáng kể: ≥2-30
• Thử thách tấn công biết trước bản rõ: P ≤ ½ + ε
18
9
18
Lý thuyết Shannon (tiếp)
• Độ dư thừa của ngôn ngữ: Sự xuất hiện của n ký tự (n-
gram) cho phép đoán nhận đúng các ký tự xuất hiện tiếp
theo với xác xuất p nào đó.
Nếu p = 1/N : ngôn ngữ không có dư thừa. N: số ký tự trong bảng
chữ cái
Nếu p > 1/N: ngôn ngữ có dư thừa (một số ký tự là không cần thiết
sau khi n ký tự đã xuất hiện)
Định lượng: sử dụng lý thuyết thông tin
Ví dụ: tiếng Việt
• Đối với thám mã: sử dụng phương pháp vét cạn, cần phải
thu được tối thiểu u ký tự mật mã để tìm được chính xác
khóa.
u: khoảng cách unicity (unicity distance)
u càng lớn độ an toàn của hệ càng cao
19
19
Lý thuyết Shannon (tiếp)
• Tính toán khoảng cách unicity
ꢈꢏꢐ(ꢑ)
ꢌ =
ꢐ ꢒ − ꢐ(ꢄ)
ꢈꢏ: Kích thước khóa
ꢐ ꢑ , ꢐ ꢄ , ꢐ ꢒ : entropy của ký tự. Ví dụ
∑
ꢐ ꢄ = − ꢇ ꢄꢓ × ꢈꢅꢋ2(ꢇ(ꢄꢓ)): entropy của ký tự bản rõ
ꢇ ꢄꢓ : xác suất xuất hiện của ký tự trong không gian bản rõ
• Nếu khóa và bản mật xuất hiện hoàn toàn ngẫu nhiên, và
chung bảng chữ cái:
ꢈꢏꢈꢅꢋ2(ꢔ)
ꢌ =
ꢈꢅꢋ2(ꢔ) − ꢐ(ꢄ)
N: số ký tự của bảng chữ cái
• Làm thế nào để tăng độ an toàn khi sử dụng mật mã?
20
10
20
Thông tin tham khảo – Kích thước khóa
• Khóa có kích thước bao nhiêu?
Mật mã được coi là an toàn khi phương pháp vét cạn (brute-force)
là cách nhanh nhất để bẻ khóa
Mục tiêu: giảm thiểu nguy cơ bị tấn công vét cạn (đạt độ an toàn
theo tính toán)
• Bạn nghe ở đâu đó, “dễ dàng” bẻ khóa mật mã DES có
kích thước khóa 64 bit?
Năm 1999, hệ thống phá mã EFF DES (trị giá 250K$) bẻ khóa
DES trong khoảng 1 ngày
Năm 2008, hệ thống phá mã COPACOBANA (trị giá 10K$) bẻ khóa
DES trong 6,4 ngày
Sử dụng định luật Moore để tính thời gian bẻ khóa trong năm 2020
với chi phí 10K$?
21
21
Thông tin tham khảo – Kích thước khóa
• Chi phí để bẻ khóa DES (năm 2008)
64 bit: $10.000
87 bit: $100.000.000.000 (thời gian bẻ khóa không đổi)
• Cần giữ thông tin mật trong bao lâu khi hệ thống phá mã
là COPACOBANA? (năm 2008)
64 bit: 6.4 ngày
128 bit: ?
• Tham khảo kích thước khóa nên sử dụng trong tương lai
tại địa chỉ
22
11
22
Thông tin tham khảo – Kích thước khóa
23
23
Thông tin tham khảo – Thời hạn khóa
24
12
24
2. Hệ mật mã khóa đối xứng
• Symmetric cryptography, Secret-key cryptography: sử
dụng cùng một khóa khi mã hóa và giải mã.
• Được phát triển từ rất sớm
• Thuật toán mã hóa: phối hợp các toán tử
Thay thế
Đổi chỗ
XOR
• Tốc độ thực hiện các thuật toán nhanh, có thể thực hiện
bằng dễ dàng bằng phần cứng
• Một số hệ mật mã khóa đối xứng hiện đại: DES, 2DES,
3DES, AES, RC4, RC5
25
25
2.1. Sơ đồ nguyên lý
Hệ mật mã gồm:
• Bản rõ (plaintext-m): thông tin không được che dấu
• Bản mật (ciphertext-c): thông tin được che dấu
• Khóa (key- kS): giá trị đã được chia sẻ bí mật
• Mã hóa (encrypt-E): c = E(kS, m)
E là hàm ngẫu nhiên
• Giải mã (decrypt): m = D(kS, c)
D là hàm xác định
• Tính đúng đắn D(kS, E(kS, m)) = m
26
13
26
Sơ đồ chung
Khóa mã hóa và
giải mã giống nhau và
được chia sẻ trước
kS
kS
m
m
Mã hóa
Giải mã
Người
gửi
Người
nhận
c
c
Kênh truyền
Yêu cầu với kS :
- Ngẫu nhiên
- Chia sẻ một cách bí mật
*
m
Kẻ tấn
công
Thám mã
kS*
27
27
Thám mã
• Nhắc lại định luật Kerckhoffs “Một hệ mật mã cần an
toàn ngay cả khi mọi thông tin về hệ, trừ khóa bí mật,
là công khai”
Kẻ thám mã đã biết giải thuật sinh khóa, mã hóa, giải mã
• Tấn công chỉ biết bản mật:
Kẻ thám mã có các bản mật (ciphertext-only attack)
Phương pháp phá mã: thử tất cả các tổ hợp khóa có thể để
tìm ra tổ hợp khóa thích hợp. Trong trường hợp không gian
khóa lớn thì phương pháp này không thực hiện được.
Đối phương cần phải phân tích văn bản mật, thực hiện các
kiểm nghiệm thống kê để giảm số lượng trường hợp cần thử.
28
14
28
Thám mã (tiếp)
• Tấn công biết trước bản rõ (KPA: Known-Plaintext Attack)
Thử thách
Tấn công
Sinh khóa k
Sinh m0, m1
m0, m1
Chọn b ∈ {0, 1}
c* = E(k, mb)
c*
Đoán b’ ∈ {0, 1}
• Hệ mật chống lại được tấn công KPA (độ an toàn IND-KPA)
nếu với mọi thuật toán tấn công hiệu quả thì P(b’ = b) ≤ ½ + ε
29
29
Thám mã (tiếp)
• Tấn công chọn trước bản rõ (CPA: Chosen-Plaintext Attack)
Thử thách
Tấn công
Sinh khóa k
m
c
Sinh m
c = E(k, m)
Sinh m0, m1
m0, m1
Chọn b ∈ {0, 1}
c*
m’
C’
c* = E(k, mb)
Sinh m’
c’ = E(k, m’)
Đoán b’ ∈ {0, 1}
• Hệ mật chống lại được tấn công CPA (độ an toàn IND-CPA)
nếu với mọi thuật toán tấn công hiệu quả thì P(b’ = b) ≤ ½ + ε 30
15
30
Thám mã (tiếp)
• Tấn công chọn trước bản mật (CCA: Chosen-Ciphertext
Attack)
Thử thách
Tấn công
Sinh khóa k
ci, mj
Sinh ci, mj
mi = D(k, ci)
cj = E(k, mj)
mi, cj
m0, m1
c*
Sinh m0, m1
Chọn b ∈ {0, 1}
c* = E(k, mb)
Sinh c’i, m’j (c’i ≠ c*)
c’i, m’j
m’i, c’j
m’i = D(k, c’i)
c’j = E(k, m’j)
Đoán b’ ∈ {0, 1}
• Hệ mật chống lại được tấn công CCA (độ an toàn IND-CCA)
nếu với mọi thuật toán tấn công hiệu quả thì P(b’ = b) ≤ ½ + ε 31
31
2.2. MẬT MÃ CỔ ĐIỂN
32
16
32
Mật mã thay thế(Substitution cipher)
• Một/một mẫu ký tự được thay thế bằng một/một mẫu ký
tự khác.
• Mật mã Ceasar
• Mật mã dịch vòng (Shift Cipher): mã từng ký tự
Khóa: 1 ≤ k ≤ 25
Mã hóa: c = (m + k) mod 26
Giải mã: m = (c − k) mod 26
33
33
Mật mã thay thế(Substitution cipher)
• Mật mã Vigener: mã 1 khối ký tự
C R Y P T O C R Y P T
k =
(+ mod 26)
m = W H A T A N I C E D A Y T O D A Y
c = Z Z Z J U C L U D T U N W G C Q S
• Tổng quát:
Mã hóa: c[i] = (m[i] + k[i mod lenk]) mod 26
Giải mã: m[i] = (c[i] - k[i mod lenk]) mod 26
lenk: Số ký tự của khóa
34
17
34
Mật mã thay thế(Substitution cipher)
• Máy rotor (Rotor machine)
A
B
C
.
K
S
T
.
E
K
S
T
.
.
R
N
N
E
K
S
T
.
.
.
X
Y
Z
R
N
E
.
R
key
Hebern machine
35
35
Mật mã thay thế(Substitution cipher)
• Máy rotor (Rotor machine)
Enigma
Số lượng khóa?
36
18
36
Phá mã hệ mật mã thay thế
• Chỉ có bản mã: Dựa trên phương pháp thống kê
• Ví dụ: tiếng Anh
37
37
Thuộc tính thống kê của tiếng Anh
• Phân nhóm ký tự theo tần suất
I
e
II
t,a,o,i,n,s,h,r
d,l
III
IV
V
c,u,m,w,f,g,y,p,b
v,k,j,x,q,z
• Một vài mẫu ký tự có tần suất xuất hiện cao
Bigrams: th, he, in, an, re, ed, on, es, st, en at, to
Trigrams: the, ing, and, hex, ent, tha, nth, was, eth, for, dth
38
19
38
Ví dụ: Phá mã dịch vòng
YKHLBA JCZ SVIJ JZB TZVHI JCZ VHJ DR IZXKHLBA VSS
RDHEI DR YVJV LBXSKYLBA YLALJVS IFZZXC CVI
LEFHDNZY EVBLRDSY JCZ FHLEVHT HZVIDB RDH JCLI CVI
WZZB JCZ VYNZBJ DR ELXHDZSZXJHDBLXI JCZ XDEFSZQLJT
DR JCZ RKBXJLDBI JCVJ XVB BDP WZ FZHRDHEZY WT JCZ
EVXCLBZ CVI HLIZB YHVEVJLXVSST VI V HXXIKSJ DR
JCLI HZXZBJ YZNZXDFEZBJ LB JZXCBDSDAT EVBT DR JCZ
XLFCZH ITIJZEIJCVJ PZHZ DBXZ XDBILYXHZYIZKHZ
VHZBDP WHZVMVWSZ
39
39
Ví dụ: Phá mã dịch vòng
Ký tự:
Tần suất:
Ký tự:
Tần suất:
Ký tự:
Tần suất:
Ký tự:
Tần suất:
A
5
H
B
C
D
E
F
7
M
1
T
8
G
0
N
3
U
0
Z e
fJ=29, fV = 27
fJCZ = 8 ’ the’
J t, C h
V đứng riêng: V a
24 19 23 12
I
J
K
6
R
L
21
S
24 21 29
O
0
V
27
P
3
W
5
Q
1
X
11 14
Y
Z
17 12 45
Nhóm: {J, V, B, H, D, I, L, C} {t, a, o, i, n, s, h, r}
t a
JZB te? {teo, tei, ten, tes, ter}: B n
h
40
20
40
Tải về để xem bản đầy đủ
42 trang
19980
Free
Bạn đang xem 20 trang mẫu của tài liệu "Bài giảng An toàn an ninh thông tin - Chương 2: Các hệ mật mã - Bùi Trọng Tùng", để tải tài liệu gốc về máy hãy click vào nút Download ở trên
File đính kèm:
- bai_giang_an_toan_an_ninh_thong_tin_chuong_2_cac_he_mat_ma_b.pdf
