1
Lecture 1: Mật mã cổ điển
1. Giới thiệu
2. Định nghĩa một hệ mật
3. Các tính chất của một hệ mật mã
4. Số học modulo m
5. Mã dịch vòng (shift cipher)
6. Mã thay thế
7. Mã Affine
8. Mã Vigenère
9. Mã Hill
10.Mã hoán vị (MHV)
11.Các hệ mã dòng
2
Giới thiệu
•Mục đích cơ bản của mật mã là tạo ra khả năng liên lạc trên một
kênh không an toàn cho hai người sử dụng (tạm gọi là Alice và
Bob) sao cho đối phương (Oscar) không thể hiểu được thông tin
được truyền đi.
• Kênh này có thể là một đường dây điện thoại hoặc một mạng máy
tính. Thông tin mà Alice muốn gửi cho Bob (bản rõ) có thể là một
văn bản tiếng Anh, Việt, các dữ liệu bằng số hoặc bất cứ tài liệu ở
dạng nào. Alice sẽ mã hoá bản rõ bằng một khoá đã được xác định
trước và gửi bản mã trên kênh.
• Đối phương Oscar giả sử có bản mã thu trộm được trên kênh song
không thể xác định nội dung của bản rõ, nhưng Bob (người đã biết
khoá mã) có thể giải mã và thu được bản rõ (nội dung của tài liệu).
3
Định nghĩa một hệ mật mã
•Một hệ mật là một bộ 5 (P,C,K,E,D) thoả mãn các điều
kiện sau:

phải có
khả năng tính toán được một cách hiệu quả.
2. Đối phương dựa trên xâu bản mã phải không có khả
năng xác định khoá k đã dùng hoặc không có khả năng xác
định được xâu bản rõ x.
6
Số học modulo m
•Giả sử a và b là các số nguyên và m là một số nguyên
dương. Khi đóta viết a ≡ b (mod m) nếu m chia hết cho
(b-a). Mệnh đề a ≡ b (mod m) được gọi là "a đồng dư với
b theo modulo m".
• Phân tích a và b theo m như sau:
¾a = q
1
m + r
1
và b = q
2
m + r
2
trong đó0 ≤ r
1
≤ m-1 và 0
≤ r
2
≤ m-1. (chú ý: r
1
và r
2
là không âm)

Số học modulo m – ví dụ
•Vídụ tính 11× 13 trong Z
16
tương tự như với các số
nguyên ta có:
–11 ×13 = 143.
– Để rút gọn 143 theo modulo 16, ta thực hiện phép chia
bình thường: 143 = 8 × 16 + 15,
–Bởi vậy 143 mod 16 = 15 trong Z
16
.
•
9
Số học modulo m–tính chất của các phép toán
1. Phép cộng là đóng, tức với bất kì a,b ∈ Zm ,a +b ∈ Zm
2. Phép cộng là giao hoán, tức là với a,b bất kì ∈ Zm: a+b = b+a
3. Phép cộng là kết hợp, tức là với bất kì a,b,c ∈ Zm: (a+b)+c =
a+(b+c)
4. 0 là phần tử đơn vị của phép cộng, có nghĩa là với a bất kì ∈ Zm:
a+0 = 0+a = a
5. Phần tử nghịch đối của phép cộng của phần tử bất kì (a ∈ Zm ) là
m-a, nghĩa là a+(m-a) = (m-a)+a = 0 với bất kì a ∈ Zm .
6. Phép nhân là đóng, tức là với a,b bất kì ∈ Zm, ab ∈ Zm .
7. Phép nhân là giao hoán, nghĩa là với a,b bất kì ∈ Zm, ab = ba
8. Phép nhân là kết hợp, nghĩa là với a,b,c ∈ Zm , (ab)c = a(cb)
9. 1 là phần tử đơn vị của phép nhân, tức là với bất kỳ a ∈ Zm: a×1 =
1×a = a
10. Phép nhân có tính chất phân phối đối với phép cộng, tức là đối với
a,b,c ∈ Zm , (a+b)c = (ac)+(bc) và a(b+c) = (ab) + (ac)
10

26
)
– Nhận xét: Trong trường hợp K = 3, hệ mật mã thường
được gọi là mã Caesar đã từng được Julius Caesar sử
dụng.
12
Mã dịch vòng (shift cipher)
• Ta sẽ sử dụng MDV (với modulo 26) để mã hoá một văn
bản tiếng Anh thông thường bằng cách thiết lập sự tương
ứng giữa các kí tự và các thặng dư theo modulo 26 như
sau: A ↔ 0,B ↔ 1, . . ., Z ↔ 25. Vì phép tương ứng này
còn dùng trong một vài ví dụ nên ta sẽ ghi lại để còn tiện
dùng sau này, ta có bảng ánh xạ chi tiết sau:
13
Mã dịch vòng (shift cipher) - ví dụ
•Giả sử khoá cho mã dịch vòng là k = 11 và bản rõ là:
wewillmeetatmidnight
• Trước tiên biến đổi bản rõ thành dãy các số nguyên nhờ
dùng phép tương ứng trên. Ta có:
w-22 e-4 w-22 i-8 l-11 l-11 m-12 e-4 e-4 t-19
a-0 t-19 m-12 i-8 d-3 n-13 i-8 g-6 h-7 t-19
•sau đócộng 11 vào mỗi giá trị rồi rút gọn tổng theo
modulo 26 (công thức e
k
(x) = x +k mod 26):
7 15 7 19 22 22 23 15 15 4
114231914241917184
•Cuối cùng biến đổi dãy số nguyên này thành các kí tự thu
được bản mã sau: HPHTWWXPPELEXTOYTRSE
14

e w x m x g l m r x m q i w e z i w r m r i
d v w l w f k l q w l p h v o d y h v q l q h
c u v k v e j k p v k o g u c x g u p k p g
b t u j u d i j o u j n f t b w f o j o f
17
Mã thay thế
•Hệ mật mã thay thế được định nghĩa như sau:
– P =C = Z
26
;
–tập khóa K chứa mọi hoán vị có thể của 26 kí hiệu 0,1, .
. . , 25.
–Với mỗi phép hoán vị π∈K, ta định nghĩa:
•e
π
(x) = π(x)
và
•d
π
(y) = π
-1
(y), trong đó π
-1
là hoán vị ngược của π.
18
Mã thay thế -Ví dụ
•Vídụ về phép hoán vị ngẫu nhiên π tạo nên một hàm mã
hoá
•Như vậy, e
π

• Để giải mã được, yêu cầu hàm Affine phải là đơn ánh. Nói
cách khác, với bất kỳ y ∈ Z
26
, ta muốn có đồng nhất thức
sau: ax + b ≡ y (mod 26) phải có nghiệm x duy nhất.
21
Mã Affine - lập mã
• Đồng dư thức: ax + b ≡ y (mod 26), tương đương với:
–ax ≡ y-b (mod 26)
– Vì y thay đổi trên Z
26
nên y-b cũng thay đổi trên Z
26
.
Bởi vậy, ta chỉ cần nghiên cứu phương trình đồng dư:
–ax ≡ y (mod 26) (y∈ Z
26
).
•Phương trình này có một nghiệm duy nhất x đối với mỗi y
khi và chỉ khi UCLN(a,26) = 1:
–Giả thiết 1: UCLN(a,26) = d >1. Khi đó, đồng dư thức
ax ≡ 0 (mod 26) sẽ có ít nhất hai nghiệm phân biệt
trong Z
26
là x = 0 và x = 26/d. Trong trường hợp này,
e(x) = ax + b mod 26 không phải là một hàm đơn ánh
và bởi vậy nó không thể là hàm mã hoá hợp lệ.
22
Mã Affine - lập mã - Ví dụ
•Với a=4, ta có:

25
Mã Affine - Ví dụ
•Vì26 = 2 ×13 nên các giá trị a ∈ Z
26
thoả mãn
UCLN(a,26) = 1 là a = 1, 3, 5, 7, 9, 11, 15, 17, 19, 21, 23
và 25. (tổng cộng có 12 giá trị có thể cho a)
•Tham số b có thể là một phần tử bất kỳ trong Z
26
. Như
vậy, mã Affine có 12 × 26 = 312 khoá có thể (dĩ nhiên
con số này quá nhỏ để bảo đảm an toàn).