Bài giảng Mật mã học - Chương 1: Giới thiệu Mã hoá cổ điển

t kế cơ điện dùng rôto tương tự như
máy Enigma, song với nhiều nâng cấp
hơn.
ATMMT - TNNQ 14
Máy 
Enigma
2. Lịch sử của mật mã
15
Máy Enigma
16
Máy TypeX
2. Lịch sử của mật mã
Máy Sigaba
17
2. Lịch sử của mật mã
• Mật mã học hiện đại
 Cha đẻ của mật mã học hiện đại là Claude
Shannon.
 Tiêu chuẩn mật mã hóa dữ liệu (Data
Encryption Standard) là một phương thức mã
hoá được công bố tại Mỹ vào ngày 17.03.1975.
 Với chiều dài khoá chỉ là 56-bit, DES đã được
chứng minh là không đủ sức chống lại những
tấn công kiểu vét cạn (brute force attack - tấn
công dùng bạo lực).
18
2. Lịch sử của mật mã
• Mật mã học hiện đại
 Năm 2001, DES đã chính thức được thay thế bởi AES
(Advanced Encryption Standard - Tiêu chuẩn mã hóa
tiên tiến).
 Trước thời kỳ này, hầu hết các thuật toán mật mã hóa
hiện đại đều là những thuật toán khóa đối xứng
(symmetric key algorithms), trong đó cả người gửi và
người nhận phải dùng chung một khóa, và cả hai người
đều phải giữ bí mật về khóa này.
 Đối với mật mã hóa dùng khóa bất đối xứng, người ta
phải có một cặp khóa có quan hệ toán học để dùng
trong thuật toán, một dùng để mã hóa và một dùng để
giải mã. Phổ biến nhất là mã hoá RSA.
ATMMT - TNNQ 19
2. Lịch sử của mật mã
• Mật mã học hiện đại
20
2. Lịch sử của mật mã
• Mật mã học hiện đại
Mã hoá RSA
21
3. Các giải thuật mã hoá cổ điển
• Các yêu cầu cơ bản đối với giải thuật mật
mã hoá là:
 Có tính bảo mật cao
 Công khai, dễ hiểu. Khả năng bảo mật
được chốt vào khoá chứ không vào bản
thân giải thuật.
 Có thể triển khai trên các thiết bị điện tử.
22
3. Các giải thuật mã hoá cổ điển
1. Mã thay thế đơn giản (Substitution Cipher)
• Trong phép này, khoá là một hoán vị h của bảng
chữ cái Z và mỗi ký hiệu của thông báo được thay
thế bằng ảnh của nó qua hoán vị h.
• Khoá thường được biểu diễn bằng một chuỗi 26 ký
tự. Có 26! (≈ 4.1026) hoán vị (khoá)
• Ví dụ: khoá là chuỗi UXEOS, ký hiệu A trong
thông báo sẽ được thay bằng U, ký hiệu B sẽ được
thay bằng X
•  Phá mã?
23
3. Các giải thuật mã hoá cổ điển
1. Mã thay thế đơn giản (Substitution Cipher)
• Chọn một hoán vị p: Z26  Z26 làm khoá.
• VD: 
 Mã hoá
ep(a)=X
 Giải mã
dp(A)=d
24
3. Các giải thuật mã hoá cổ điển
2. Mã thay thế n-gram
• Thay vì thay thế các ký tự, người ta có
thể thay thế cho từng cụm 2 ký tự
(diagram), 3 ký tự (trigram) hoặc tổng
quát cho từng cụm n ký tự (n-gram).
• Với bảng chữ cái gồm 26 ký tự tiếng
Anh thì phép thay thế n-gram sẽ có khoá
là một hoán vị của 26n n-gram khác
nhau.
•  Phá mã?
25
3. Các giải thuật mã hoá cổ điển
2. Mã thay thế n-gram
Trong trường hợp diagram thì hoán vị gồm
262 diagram và có thể biểu diễn bằng một
dãy 2 chiều 26x26 trong đó các hàng biểu
diễn ký hiệu đầu tiên, các cột biểu diễn ký
hiệu thứ hai, nội dung của các ô biểu diễn
chuỗi thay thế. A B 
A EG RS
B BO SC
26
3. Các giải thuật mã hoá cổ điển
3. Mã hoán vị bậc d (Permutation Cypher)
• Đối với một số nguyên dương d bất kỳ, chia
thông báo m thành từng khối có chiều dài
d. Rồi lấy một hoán vị h của 1, 2, , d và
áp dụng h vào mỗi khối.
• Ví dụ: nếu d=5 và h=(4 1 3 2 5), hoán vị (1
2 3 4 5) sẽ được thay thế bằng hoán vị mới
(4 1 3 2 5).
27
3. Các giải thuật mã hoá cổ điển
3. Mã hoán vị bậc d
• Ví dụ: ta có thông báo
m = JOHN IS A GOOD ACTOR
Qua phép mã hoá này m sẽ trở thành
chuỗi mật mã c sau:
c = NJHO AI S DGOO OATCR
•  Phá mã?
28
3. Các giải thuật mã hoá cổ điển
4. Mã dịch chuyển (Shift Cypher)
Vigenère và Caesar
• Trong phương pháp Vigenère, khoá bao
gồm một chuỗi có d ký tự. Chúng được viết
lặp lại bên dưới thông báo và được cộng
modulo 26. Các ký tự trắng được giữ
nguyên không cộng.
• Nếu d=1 thì khoá chỉ là một ký tự đơn và
được gọi là phương pháp Caesar (được
đưa ra sử dụng đầu tiên bởi Julius Caesar).
•  Phá mã?
29
Ví dụ: 
Plaintext: CRYPTOGRAPHY
Ciphertext: HWDUYTLWFUMD (Shift of 5)
C=(p+5) mod 26
The classic Caesar Shift chart
30
Mã dịch chuyển – Shift Cypher
31
Ví dụ: 
Từ khoá: CHIFFRE
Mã hoá: VIGENERE
Kết quả: XPOJSVVG
Vigenère 
Encryption –
Block Cypher 
(1523 – 1596)
32
3. Các giải thuật mã hoá cổ điển
5. One - time Pad:
h e l p n e e d e d
001 000 010 100 101 000 000 011 000 011
e=000 h=001 l=010 d=011 p=100 n=101 a=110 
Encryption: Plaintext  Key = Ciphertext
111 101 110 101 111 100 000 101 110 000
110 101 100 001 010 100 000 110 110 011
a n p h l p e a a d
Plaintext:
Key:
Ciphertext:
33
3. Các giải thuật mã hoá cổ điển
6. Mã tuyến tính (Affine Cipher)
Mã tuyến tính là mã thay thế có dạng:
e(x) = ax + b (mod 26), với a, b  Z26.
Nếu a = 1 ta có mã dịch chuyển.
Giải mã: Tìm x?
y = ax + b (mod 26)
ax = y – b (mod 26)
x = a-1(y – b) (mod 26).
34
3. Các giải thuật mã hoá cổ điển
7. Mã Playfair
Mật mã đa ký tự (mỗi lần mã hoá 2 ký tự liên tiếp nhau)
Giải thuật dựa trên một ma trận các chữ cái n×n (n=5 hoặc
n=6) được xây dựng từ một khóa (chuỗi các ký tự).
Xây dựng ma trận khóa:
 Lần lượt thêm từng ký tự của khóa vào ma trận.
 Nếu ma trận chưa đầy, thêm các ký tự còn lại trong bảng
chữ cái vào ma trận theo thứ tự A – Z.
 I và J xem như 1 ký tự.
 Các ký tự trong ma trận khoá không được trùng nhau.
35
3. Các giải thuật mã hoá cổ điển
7. Mã Playfair
Giải thuật mã hóa:
• Mã hóa từng cặp 2 ký tự liên tiếp nhau.
• Nếu dư 1 ký tự, thêm ký tự “x” vào cuối.
• Nếu 2 ký tự nằm cùng dòng, thay thế bằng 2 ký tự tương ứng
bên phải. Ký tự ở cột cuối cùng được thay bằng ký tự ở cột đầu
tiên.
• Nếu 2 ký tự nằm cùng cột được thay thế bằng 2 ký tự bên
• dưới. Ký tự ở hàng cuối cùng được thay thế bằng ký tự ở hàng
trên cùng
• Nếu 2 ký tự lập thành hình chữ nhật được thay thế bằng 2 ký tự
tương ứng trên cùng dòng ở hai góc còn lại.
36
3. Các giải thuật mã hoá cổ điển
7. Mã Playfair
37
3. Các giải thuật mã hoá cổ điển
7. Mã Playfair
38
3. Các giải thuật mã hoá cổ điển
8. Mã Hill
Giải thuật mã hóa:
• Sử dụng m ký tự liên tiếp của plaintext và thay thế bằng m
ký tự trong ciphertext với một phương trình tuyến tính trên
các ký tự được gán giá trị lần lượt là A=01, B=02, ,
Z=26.
• Chọn ma trận vuông Hill (ma trận H) làm khoá.
• Mã hoá từng chuỗi n ký tự trên plaintext (vector P) với n là
kích thước ma trận vuông Hill.
• C = HP mod 26
• P = H-1Cmod 26
39
3. Các giải thuật mã hoá cổ điển
8. Mã Hill
40
3. Các giải thuật mã hoá cổ điển
8. Mã Hill
41
3. Các giải thuật mã hoá cổ điển
8. Mã Hill
42
3. Các giải thuật mã hoá cổ điển
9. Phương pháp phá mã cổ điển:
• Dựa vào đặc điểm ngôn ngữ.
• Dựa vào tần suất xuất hiện của các chữ
cái trong bảng chữ cái thông qua thống
kê từ nhiều nguồn văn bản khác nhau,
dựa vào số lượng các ký tự trong bảng
mã để xác định thông báo đầu vào.
43
Tần suất của các ký tự trong ngôn ngữ tiếng Anh
44
4. Bẻ gãy một hệ thống mật mã
• Những chuyên gia mật mã hay những kẻ tấn
công thường được giả thiết biết đầy đủ thông tin
về hàm mã hoá e và hàm giải mã d.
• Các chuyên gia này cũng có thể có thêm nhiều
thông tin hỗ trợ như các thống kê về ngôn ngữ,
kiến thức về ngữ cảnh...
• Với một chuỗi mật mã nào đó, họ thiếu khoá k
để có thể sử dụng d để giải mã c một cách
chính xác.
45
4. Bẻ gãy một hệ thống mật mã
46
4. Bẻ gãy một hệ thống mật mã
Các khả năng tấn công trên hệ thống: 
47
4. Bẻ gãy một hệ thống mật mã
Các khả năng tấn công trên hệ thống:
• Tấn công chỉ dựa trên chuỗi mật mã (crytogram-only
attack): đối phương chỉ biết một vài mẫu chuỗi mật mã c.
• Tấn công dựa trên văn bản đã biết (known-plaintext
attack): Trong trường hợp này những người tấn công
được giả thiết là đã biết một độ dài đáng kể của văn bản
thông báo và chuỗi mật mã tương ứng, và từ đó cố gắng
tìm ra khoá.
• Tấn công dựa trên văn bản được chọn (chosen-plaintext
attack): những người tấn công có thể đã có được một số
lượng tuỳ ý của các cặp thông báo và chuỗi mật mã tương
ứng (m, c).
48
4. Bẻ gãy một hệ thống mật mã
Các khả năng tấn công trên hệ thống: 
Kiểu tấn công Đối phương nắm được
ciphertext only attack Chỉ văn bản mã c
known plaintext attack Cả văn bản nguồn p và văn bản mã c
chosen plaintext attack
Đột nhập được vào máy mã hoá. Tự 
chọn văn bản p và mã hoá lấy được văn 
bản mã c tương ứng.
chosen ciphertext attack
Đột nhập được vào máy giải mã. Tự 
chọn văn bản mã c và giải mã lấy được 
văn bản p tương ứng.
49
4. Bẻ gãy một hệ thống mật mã
Key size (bits)
Number of 
alternative keys
Time required at 1 
decryption/ms
Time required at 106
decryption/ms
32 232 = 4.3 x 109 231 ms = 35.8 
minutes
2.15 milliseconds
56 256 = 7.2 x 1016 255 ms = 1142 years 10.01 hours
128 2128 = 3.4 x 1038 2127 ms = 5.4 x 1024
years
5.4 x 1018 years
168 2168 = 3.7 x 1050 2167 ms = 5.9 x 1036
years
5.9 x 1030 years
26 characters 
(permutation)
26! = 4 x 1026 2 x 
1026 ms
= 6.4 x 1012
years
6.4 x 106 years
Thời gian trung bình để tìm khoá theo kiểu vét cạn
50
4. Bẻ gãy một hệ thống mật mã
Thời gian trung bình để tìm khoá theo kiểu vét cạn
ATMMT - TNNQ 51
4. Bẻ gãy một hệ thống mật mã
Công cụ phân tích Cryptool
ATMMT - TNNQ 52
5. Bài tập
1. Giải thích cơ chế của việc bẻ gãy mật mã của hệ 
thống sau:
53
5. Bài tập
2. Tìm mã hoá của các ký số 1-9:
• Mỗi biểu tượng trong số chín biểu tượng xuất
hiện trong mảng dưới đây () mã
hóa duy nhất một trong các chữ số 1 đến 9.
• Cột ngoài cùng bên phải là các tổng số ở mỗi
hàng
• Hàng dưới cùng cho các tổng số ở mỗi cột.
• Một dấu hỏi có thể đại diện cho bất kỳ một hoặc
hai chữ số và không nhất thiết phải cùng một số
trong mỗi trường hợp.
54
6. Bài tập
2. Tìm mã hoá của các ký số 1-9:
55
5. Bài tập
3. Sử dụng công cụ Cryptool
• Cryptool là một ứng dụng miễn phí chạy
trên Windows, thường được sử dụng để
phân tích các giải thuật mã hoá. Phiên bản
hiện nay là 1.4.31.
• Địa chỉ download Cryptool:
56
5. Bài tập
4. Nêu cơ chế hoạt động và viết ứng dụng cho 
phép mã hoá và giải mã với những giải thuật 
mã hoá sau:
• Vigenère
• Hill.
• Affine
• Playfair
• Solitaire