Bài giảng Tổng quan về Mã hóa thông tin môn Bảo mật thông tin | Đại học Bách Khoa Hà Nội

2023 ThS. Nguyễn Chí Hiếu 2023 Nội dung
1. Giới thiệu về Mã hóa thông tin 2. Phân loại hệ mã
3. Thám mã và tính an toàn của một hệ mã
4. Một số hệ mã cổ điển 2023
An toàn bảo mật Hệ thống thông tin 2 1 2023 1.Tổng quan về Mã hóa thông tin  2023
An toàn bảo mật Hệ thống thông tin 3
1. Giới thiệu về mã hóa thông tin
 Khoa học mật mã (cryptology)
 Nghiên cứu các phương pháp toán học nhằm bảo mật thông tin
 Gồm hai lĩnh vực chính:  Mã hóa (cryptography)  Thám mã (cryptanalysis) 2023
An toàn bảo mật Hệ thống thông tin 4 2 2023
1. Giới thiệu về mã hóa thông tin  Hệ mã (cryptosystem)
 Là một bộ gồm 5 thành phần (𝒫, 𝒞, 𝒦 , ℰ, 𝒟) thỏa các điều kiện sau: P C K E D Tập hữu hạn Tập hữu hạn Tập hữu hạn Hàm mã hóa Hàm giải mã văn bản văn bản các khóa (encrypt) (decrypt) (plain text) (cipher text) (key) 2023
An toàn bảo mật Hệ thống thông tin 5
1. Giới thiệu về mã hóa thông tin  Hệ mã (cryptosystem)
 Là một bộ gồm 5 thành phần (𝒫, 𝒞, 𝒦 , ℰ, 𝒟) thỏa các điều kiện sau:
 Với mỗi khóa 𝑘 ∈ 𝒦 , tồn tại 𝑒 ∈ ℰ và 𝑑 ∈ 𝒟, ta định
nghĩa 𝑒 : 𝒫 → 𝒞 và 𝑑 : 𝒞 → 𝒫 là hàm mã hóa và giải
mã tương ứng thỏa điều kiện 𝒟 (ℰ (𝑥)) = 𝑥, ∀𝑥 ∈ 𝒫 2023
An toàn bảo mật Hệ thống thông tin 6 3 2023
1. Giới thiệu về mã hóa thông tin  Hệ mã (cryptosystem)
 Là một bộ gồm 5 thành phần (𝒫, 𝒞, 𝒦 , ℰ, 𝒟) thỏa các điều kiện sau:
 Với mỗi khóa 𝑘 ∈ 𝒦 , tồn tại 𝑒 ∈ ℰ và 𝑑 ∈ 𝒟, ta định
nghĩa 𝑒 : 𝒫 → 𝒞 và 𝑑 : 𝒞 → 𝒫 là hàm mã hóa và giải
mã tương ứng thỏa điều kiện 𝒟 (ℰ (𝑥)) = 𝑥, ∀𝑥 ∈ 𝒫 2023
An toàn bảo mật Hệ thống thông tin 7
1. Giới thiệu về mã hóa thông tin
 Ý nghĩa của việc mã hóa thông tin
 Tính bí mật (confidentiality): giữ thông tin bí mật, ngoại trừ
người được cấp quyền
 Tính toàn vẹn (integrity): bảo đảm thông tin không bị thay đổi.
 Tính xác thực (authentication): người gửi (hoặc người nhận) có
thể chứng minh đúng họ đã gửi hoặc nhận thông tin
 Tính không chối bỏ (non-repudiation): người gửi hoặc nhận sau
này không thể chối bỏ việc đã gửi hoặc nhận thông tin 2023
An toàn bảo mật Hệ thống thông tin 8 4 2023 2.Phân loại hệ mã  2023
An toàn bảo mật Hệ thống thông tin 9 2.Phân loại hệ mã
 Theo phương pháp biến đổi bản rõ thành bản mã
 Thay thế (substitution): các ký tự bản rõ sẽ được thay bởi một số ký tự khác
 Hoán vị (permutation): các ký tự của bản rõ sẽ được thay
bởi những ký tự tại vị trí khác trong bản rõ
 Thay thế - Hoán vị (substitution – permutation): kết hợp cả hai phương pháp 2023
An toàn bảo mật Hệ thống thông tin 10 5 2023 2.Phân loại hệ mã
 Theo số lượng khóa sử dụng
 Mã hóa đối xứng (bí mật): 1 khóa
 Mã hóa phi đối xứng (công khai): nhiều khóa 2023
An toàn bảo mật Hệ thống thông tin 11 2.Phân loại hệ mã
 Theo số lượng ký tự bản rõ được mã hóa trong cùng thời điểm
 Nhóm các ký tự bản rõ: mã khối (block cipher)
 Lần lượt từng ký tự bản rõ: mã dòng (stream cipher) 2023
An toàn bảo mật Hệ thống thông tin 12 6 2023 2.Phân loại hệ mã
 Theo số lượng ký tự bản rõ được mã hóa trong cùng thời điểm
 Nhóm các ký tự bản rõ: mã khối (block cipher)
 Lần lượt từng ký tự bản rõ: mã dòng (stream cipher) 2023
An toàn bảo mật Hệ thống thông tin 13 3.Thám mã và
tính an toàn của một hệ mã  2023
An toàn bảo mật Hệ thống thông tin 14 7 2023 Thám mã
 Thám mã (cryptanalysis) là ngành học nghiên cứu các
phương pháp để giải mã các bản mã đã được mã hóa
bởi một hệ mã nào đó. 2023
An toàn bảo mật Hệ thống thông tin 15 Thám mã
 Các phương pháp thám mã:
 Tấn công chỉ biết bản mã (ciphertext-only attack)
 Tấn công biết cả bản rõ (known-plaintext attack)
 Tấn công có bản rõ được chọn (chosen-plaintext attack)
 Tấn công có bản mã được chọn (chosen-ciphertext attack)  … 2023
An toàn bảo mật Hệ thống thông tin 16 8 2023 Thám mã
 Thám mã (cryptanalysis) là ngành học nghiên cứu các phương pháp
để giải mã các bản mã đã được mã hóa bởi một hệ mã nào đó.
 Các phương pháp thám mã: 
Tấn công chỉ biết bản mã (ciphertext-only attack) 
Tấn công biết cả bản rõ (known-plaintext attack) 
Tấn công có bản rõ được chọn (chosen-plaintext attack) 
Tấn công có bản mã được chọn (chosen-ciphertext attack)  … 2023
An toàn bảo mật Hệ thống thông tin 17
Tính an toàn của một hệ mã
 An toàn vô điều kiện: hệ mã bí mật hoàn toàn
 An toàn được chứng minh
 An toàn được tính toán 2023
An toàn bảo mật Hệ thống thông tin 18 9 2023
4.Một số hệ mã cổ điển  2023
An toàn bảo mật Hệ thống thông tin 19
4.Một số hệ mã cổ điển
 Các hệ mã cổ điển gồm một số nhóm sau:
 Mã hóa thay thế (substitution cipher)
 Mã hóa chuyển vị (permutation cipher) 2023
An toàn bảo mật Hệ thống thông tin 20 10 2023
4.Một số hệ mã cổ điển
 Cho 𝒫 = 𝒞 = 𝒦 = ℤ , với mọi phép hoán vị 𝜎 ∈ 𝒦,
hàm mã hóa và giải mã được định nghĩa như sau: ℰ (𝑥) = 𝜎(𝑥), 𝒟 (𝑦) = 𝜎 (𝑦)
với 𝑥 ∈ 𝒫, 𝑦 ∈ 𝒞 và 𝜎
là hoán vị ngược của 𝜎. 2023
An toàn bảo mật Hệ thống thông tin 21
4.1.Mã hóa thay thế (substitution cipher)
 Các phương pháp mã hóa thay thế:
 Mã hóa dịch chuyển (shift cipher)  Mã hóa affine  Mã hóa Hill 2023
An toàn bảo mật Hệ thống thông tin 22 11 2023 Mã hóa dịch chuyển
 Các ký tự được xoay vòng 𝑘 vị trí trong bảng chữ cái.
 Cho 𝒫 = 𝒞 = 𝒦 = ℤ ,
với mọi khóa 𝑘 ∈ 𝒦, 0 ≤ 𝑘 ≤ 25, hàm mã hóa và giải
mã được định nghĩa như sau:
ℰ (𝑥) = (𝑥 + 𝑘) 𝑚𝑜𝑑 26,
𝒟 (𝑦) = (𝑦 − 𝑘 ) 𝑚𝑜𝑑 26
với 𝑥 ∈ 𝒫 và 𝑦 ∈ 𝐶. 2023
An toàn bảo mật Hệ thống thông tin 23 Mã hóa dịch chuyển  Mã hóa Caesar là một
trường hợp đặc biệt của
mã hóa dịch chuyển với 𝑘 = 3. 2023
An toàn bảo mật Hệ thống thông tin 24 12 2023 Mã hóa dịch chuyển
 Ví dụ: Cho bảng chữ cái tiếng Anh và bản rõ
𝑝=“nhap mon ma hoa”, tìm bản mã 𝑐. 0 1 2 3 4 5 6 7 8 9 10 11 12 A B C D E F G H I J K L M 13 14 15 16 17 18 19 20 21 22 23 24 25 N O P Q R S T U V W X Y Z
 Giải mã tìm bản rõ của từ: ALQ FKDR PRL QJXRL 2023
An toàn bảo mật Hệ thống thông tin 25 Mã hóa dịch chuyển  Tính chất
 Công khai thuật toán mã hóa và giải mã  Chỉ có 26 khóa
 Biết được ngôn ngữ của bản rõ  Nhận xét
 Dễ bị tấn công bởi các phương pháp tấn công vét cạn (brute-force attack) 2023
An toàn bảo mật Hệ thống thông tin 26 13 2023 Mã hóa dịch chuyển  Tính chất
 Công khai thuật toán mã hóa và giải mã  Chỉ có 26 khóa
 Biết được ngôn ngữ của bản rõ  Nhận xét
 Dễ bị tấn công bởi các phương pháp tấn công vét cạn (brute-force attack) 2023
An toàn bảo mật Hệ thống thông tin 27 Mã hóa Vigenere
 Là phương pháp mã hóa sử dụng khóa là một nhóm gồm nhiều ký tự.
 Cho 𝒫 = 𝒞 = 𝒦 = ℤ , 𝑘 = (𝑘 , 𝑘 , … , 𝑘 ) ∈ 𝒦 và
𝑛 > 0, hàm mã hóa và giải mã định nghĩa như sau:
ℰ (𝑥 ) = (𝑥 + 𝑘 ) 𝑚𝑜𝑑 26,
𝒟 (𝑦 ) = (𝑦 − 𝑘 ) 𝑚𝑜𝑑 26
với 𝑥 ∈ 𝒫 và ∀𝑦 ∈ 𝒞. 2023
An toàn bảo mật Hệ thống thông tin 28 14 2023 Mã hóa Vigenere  Mã hóa Vigenere  Hình vuông Vigenère
 Sử dụng 26 bảng ký tự
mật mã (mỗi bảng tương ứng một dòng)
 Cần xác định bảng nào được sử dụng 2023
An toàn bảo mật Hệ thống thông tin 29 Mã hóa Vigenere  Ví dụ: Cho trước  Bản rõ p = ATTACK AT DAWN  Khóa 𝑘 = CAT  Bản mã ? 2023
An toàn bảo mật Hệ thống thông tin 30 15 2023 Mã hóa Vigenere A T T A C K A T D A W N C A T C A T C A T C A T C T M C C D C T W C W G 2023
An toàn bảo mật Hệ thống thông tin 31 Mã hóa Vigenere ? ? ? ? ? ? ? ? ? ? ? ? C A T C A T C A T C A T C T M C C D C T W C W G 2023
An toàn bảo mật Hệ thống thông tin 32 16 2023 Mã hóa Vigenere  Nhận xét
 Thám mã trong trường hợp khóa gồm nhiều ký tự? 2023
An toàn bảo mật Hệ thống thông tin 33 Mã hóa Affine  Cho 𝒫 = 𝒞 = ℤ ,
và 𝒦 = {(𝑎, 𝑏) ∈ ℤ × ℤ : gcd (𝑎, 26) = 1}.
 Với mọi 𝑘 = (𝑎, 𝑏) ∈ 𝒦, hàm mã hóa và giải mã được định nghĩa như sau:
𝐸 𝑥 = 𝑎𝑥 + 𝑏 𝑚𝑜𝑑 26, 𝒟 (𝑦) = 𝑎
(𝑦 − 𝑏 ) 𝑚𝑜𝑑 26
với 𝑥 ∈ 𝒫 và 𝑦 ∈ 𝒞 2023
An toàn bảo mật Hệ thống thông tin 34 17 2023 Mã hóa Affine  Cho 𝒫 = 𝒞 = ℤ ,
và 𝒦 = {(𝑎, 𝑏) ∈ ℤ × ℤ : gcd (𝑎, 26) = 1}.
 Với mọi 𝑘 = (𝑎, 𝑏) ∈ 𝒦, hàm mã hóa và giải mã được định nghĩa như sau: ℰ
𝑥 = 𝑎𝑥 + 𝑏 𝑚𝑜𝑑 26, 𝒟 (𝑦) = 𝑎
(𝑦 − 𝑏 ) 𝑚𝑜𝑑 26
với 𝑥 ∈ 𝒫 và 𝑦 ∈ 𝒞 2023
An toàn bảo mật Hệ thống thông tin 35 Mã hóa Affine
 Tìm nghịch đảo modulo của 𝑛
 Cho một số nguyên a, ta gọi 𝑎
là nghịch đảo modulo 𝑛 của
𝑎 nếu thỏa điều kiện 𝑎𝑎 ≡ 1 𝑚𝑜𝑑 𝑛.
 Cho 𝑎 , 𝑛 ∈ 𝑁 ∗, nếu gcd (𝑎, 𝑛) = 1 thì tìm được hai số nguyên
𝑥 và 𝑦 thỏa điều kiện sau: 𝑎𝑥 + 𝑛𝑦=1 ⟺
𝑎𝑥 ≡ 1 𝑚𝑜𝑑 𝑛 ⟺ 𝑥 ≡ 𝑎 𝑚𝑜𝑑 𝑛 2023
An toàn bảo mật Hệ thống thông tin 36 18 2023 Mã hóa Affine
 Cho 𝑎 = 3 và 𝑛 = 26, áp dụng thuật toán Eulcid mở
rộng tính được nghịch đảo modulo 𝑛 của 𝑎 là 𝑎 = 9.  Do đó, ta có 𝑥 ≡ 𝑎 𝑚𝑜𝑑 26 ≡ 9 𝑚𝑜𝑑 26 2023
An toàn bảo mật Hệ thống thông tin 37 0 1 2 3 4 5 6 7 8 9 10 11 12 Mã hóa Affine A B C D E F G H I J K L M 13 14 15 16 17 18 19 20 21 22 23 24 25 N O P Q R S T U V W X Y Z
 Ví dụ: Cho bản rõ 𝑝 = 𝑎𝑓𝑓𝑖𝑛𝑒 và một cặp khóa
(𝑎, 𝑏) = (3,5), tìm bản mã 𝑐.  Hàm mã hóa
ℰ (𝑥) = (3𝑥 + 5) 𝑚𝑜𝑑 26 2023
An toàn bảo mật Hệ thống thông tin 38 19 2023 0 1 2 3 4 5 6 7 8 9 10 11 12 Mã hóa Affine A B C D E F G H I J K L M 13 14 15 16 17 18 19 20 21 22 23 24 25 N O P Q R S T U V W X Y Z  Hàm mã hóa
ℰ (𝑥) = (3𝑥 + 5) 𝑚𝑜𝑑 26 p a f f i n e x 0 5 5 8 13 4 (3x+5) mod 26 5 20 20 3 18 17 c F U U D S R 2023
An toàn bảo mật Hệ thống thông tin 39 0 1 2 3 4 5 6 7 8 9 10 11 12 Mã hóa Affine A B C D E F G H I J K L M 13 14 15 16 17 18 19 20 21 22 23 24 25 N O P Q R S T U V W X Y Z  Hàm giải mã
𝒟 𝑦 = 9 𝑦 − 5 𝑚𝑜𝑑 26 c F U U D S R y 5 20 20 3 18 17 9(y-5) mod 26 0 5 5 8 13 4 p a f f i n e 2023
An toàn bảo mật Hệ thống thông tin 40 20