Trường Đại Học Công Nghệ Thông Tin Khoa Mạng Máy Tính và Truyền Thông
AN TOÀN MẠNG MÁY TÍNH
ThS. Tô Nguyễn Nhật Quang
NỘI DUNG MÔN HỌC 2
1. Tổng quan 2. a. Các phần mềm gây hại – Trojan
- Các phần mềm gây hại – Virus 3. Các giải thuật mã hoá dữ liệu 4. Mã hoá khoá công khai và quản lý khoá 5. Chứng thực dữ liệu 6. Một số giao thức bảo mật mạng 7. Bảo mật mạng không dây 8. Bảo mật mạng ngoại vi
ATMMT - TNNQ
BÀI 3
CÁC GIẢI THUẬT MÃ HOÁ DỮ LIỆU
Các giải thuật mã hoá dữ liệu
1. Giới thiệu về mật mã hoá 2. Lịch sử của mật mã 3. Giải thuật mã hoá cổ điển 4. Giải thuật mã hoá hiện đại 5. Bẻ gãy một hệ thống mật mã 6. Bài tập
ATMMT - TNNQ 4
1. Giới thiệu về mật mã hoá
• Giới thiệu
▪ Mật mã hoá được sử dụng kể từ cổ đại cho đến tận ngày nay.
▪ Hiện nay, các giao dịch tài chính, chuyển khoản, mua sắm hàng hoá, thư từ, tài liệu… được thực hiện nhiều qua môi trường mạng đòi hỏi dữ liệu phải được bảo mật tốt => phải được mã hoá.
ATMMT - TNNQ 5
1. Giới thiệu về mật mã hoá
ATMMT - TNNQ 6
1. Giới thiệu về mật mã hoá
• Một số khái niệm
▪ Thông báo, văn bản: là một chuỗi hữu hạn các ký hiệu lấy từ một bảng chữ cái Z nào đó và được ký hiệu là m.
▪ Mật mã hoá: là việc biến đổi một thông báo sao cho nó không thể hiểu nổi đối với bất kỳ người khác ngoài người nhận được mong muốn.
▪ Phép mật mã hoá thường được ký hiệu là e(m), với m là thông báo cần mã hoá.
ATMMT - TNNQ 7
1. Giới thiệu về mật mã hoá
• Một số khái niệm
▪ Khoá: là một thông số đầu vào của phép mã hoá hoặc giải mã. Khoá dùng để mã hoá ký hiệu là ke, khoá dùng để giải mã ký hiệu là kd.
▪ Chuỗi mật mã: là chuỗi nguỵ trang, tức là chuỗi thông báo qua phép mật mã hoá và thường được ký hiệu là c: c=e(m,ke).
▪ Phép giải mã d(c,kd) là quá trình xác định thông báo gốc (m) từ chuỗi mật mã c và khoá giải mã kd, và thường được ký hiệu là d(c,kd): d(c,kd)=m.
ATMMT - TNNQ 8
1. Giới thiệu về mật mã hoá
ATMMT - TNNQ 9
1. Giới thiệu về mật mã hoá
ATMMT - TNNQ 10
2. Lịch sử của mật mã • Mật mã học là ngành có lịch sử hàng ngàn năm. • Mật mã học cổ điển với bút và giấy. • Mật mã học hiện đại với điện cơ, điện tử, máy tính. • Sự phát triển của mật mã học đi liền với sự phát triển
của phá mã (thám mã):
▪ Phát hiện ra bức điện Zimmermann khiến Hoa Kỳ tham gia Thế chiến I
▪ Việc phá mã thành công hệ thống mật mã của Đức Quốc xã góp phần đẩy nhanh thời điểm kết thúc thế chiến II.
• Hai sự kiện khiến cho mật mã học trở nên đại chúng:
▪ Sự xuất hiện của tiêu chuẩn mật mã hóa DES.
▪ Sự ra đời của các kỹ thuật mật mã hóa khóa công khai.
ATMMT - TNNQ 11
2. Lịch sử của mật mã
• Mật mã học cổ điển
▪ Các chữ tượng hình không tiêu chuẩn tìm thấy trên các bức tượng Ai Cập cổ đại (cách đây khoảng 4500 năm tr.CN).
▪ Mã hóa thay thế bảng chữ cái đơn giản như mật mã hóa Atbash (khoảng năm 500- 600 tr.CN).
▪ Người La Mã xây dựng mật mã Caesar.
ATMMT - TNNQ 12
2. Lịch sử của mật mã
• Mật mã học trong thế chiến thứ 2
▪ Người Đức sử dụng rộng rãi một hệ thống máy rôto cơ điện tử có tên gọi là máy Enigma.
▪ Phe Đồng minh sử dụng máy TypeX của Anh và máy SIGABA của Mỹ, đều là những thiế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 13
2. Lịch sử của mật mã
Máy Enigma
ATMMT - TNNQ 14
Máy Enigma 15
ATMMT - TNNQ
2. Lịch sử của mật mã
Máy Sigaba
Máy TypeX
ATMMT - TNNQ 16
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).
ATMMT - TNNQ 17
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 18
2. Lịch sử của mật mã
• Mật mã học hiện đại
ATMMT - TNNQ 19
2. Lịch sử của mật mã
• Mật mã học hiện đại
Mã hoá RSA 20
ATMMT - TNNQ
3. 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ử.
ATMMT - TNNQ 21
3. 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ã?
ATMMT - TNNQ 22
3. 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
ATMMT - TNNQ 23
3. 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ã?
ATMMT - TNNQ 24
3. 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 …
ATMMT - TNNQ 25
3. 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
- 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).
ATMMT - TNNQ 26
3. 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ã?
ATMMT - TNNQ 27
3. 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ã?
ATMMT - TNNQ 28
Ví dụ: The classic Caesar Shift chart Plaintext: CRYPTOGRAPHY
Ciphertext: HWDUYTLWFUMD (Shift of 5)
C=(p+5) mod 26 ATMMT - TNNQ 29
Mã dịch chuyển – Shift Cypher 30
ATMMT - TNNQ
Vigenère 31 Encryption – Block Cypher (1523 – 1596)
Ví dụ: Từ khoá: CHIFFRE Mã hoá: VIGENERE Kết quả: XPOJSVVG
ATMMT - TNNQ
3. Giải thuật mã hoá cổ điển
5. One - time Pad:
e=000 h=001 l=010 d=011 p=100 n=101 a=110
Encryption: Plaintext Key = Ciphertext
he l pneeded
Plaintext:
001 000 010 100 101 000 000 011 000 011
Key: 111 101 110 101 111 100 000 101 110 000
110 101 100 001 010 100 000 110 110 011
Ciphertext:
anph l peaad
ATMMT - TNNQ 32
3. Giải thuật mã hoá cổ điển 33
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).
ATMMT - TNNQ
3. 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.
34
3. 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.
35
3. Giải thuật mã hoá cổ điển
7. Mã Playfair
36
3. Giải thuật mã hoá cổ điển
7. Mã Playfair
37
3. 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
38
3. Giải thuật mã hoá cổ điển
8. Mã Hill
39
3. Giải thuật mã hoá cổ điển
8. Mã Hill
40
3. Giải thuật mã hoá cổ điển
8. Mã Hill
41
3. 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.
ATMMT - TNNQ 42
Tần suất của các ký tự trong ngôn ngữ tiếng Anh 43
ATMMT - TNNQ
4. Giải thuật mã hoá hiện đại
• Thường sử dụng mã khối kết hợp với các phép hoán vị và thay thế.
• Việc biến đổi văn bản được thực hiện nhiều lần trong một số vòng lặp.
• Khoá con của các vòng lặp sẽ khác nhau và được sinh ra từ khoá ban đầu.
• Phổ biến có DES, AES, RSA...
ATMMT - TNNQ 44
4. Giải thuật mã hoá hiện đại
1. Phân loại
• Mã hoá khoá đối xứng (symmetric): ▪ Block ciphers: mã hoá các khối có chiều dài cố định 64 bit hoặc 128 bit. Phổ biến có IDEA, RC2, DES, Triple DES, Rijndael (AES), MARS, RC6, Serpent, Twofish, DESX, DESL, DESXL. ▪ Stream ciphers: mã hoá từng bit của thông điệp. Đại diện là RC4.
• Mã hoá khoá bất đối xứng (asymmetric): RSA
ATMMT - TNNQ 45
4. Giải thuật mã hoá hiện đại
2. Chuẩn mã hoá dữ liệu DES
• DES (Data Encryption Standard) được sử dụng rộng rãi trên thế giới.
• Dùng khoá có độ dài 56 bit để mã hoá các khối dữ liệu 64 bit.
• Cả bên mã hoá lẫn bên giải mã đều dùng chung một khoá và DES thuộc vào hệ mã khoá bí mật.
• Xét về độ an toàn, hiện nay 3DES (một cải tiến của DES) được đánh giá là có độ an toàn cao vì độ dài khoá của nó gấp 3 lần so với DES.
ATMMT - TNNQ 46
4. Giải thuật mã hoá hiện đại
2. Chuẩn mã hoá dữ liệu DES
ATMMT - TNNQ 47
Giải thuật mã hoá DES
2. Chuẩn mã hoá dữ liệu DES
• 17.03.1975: DES được công bố để công chúng đóng góp ý kiến.
• 11.1976: DES được phê chuẩn làm tiêu chuẩn chính thức.
• 1992: Biham và Shamir công bố một phương thức tấn công thám mã vi sai với độ phức tạp thấp hơn tấn công bạo lực (trên lý thuyết). Kiểu tấn công này đòi hỏi người tấn công lựa chọn 247 văn bản rõ (một điều kiện không thực tế).
• 06.1997: Lần đầu tiên, dự án DESCHALL đã phá vỡ được một bản tin mã hoá bằng DES.
48
Giải thuật mã hoá DES
2. Chuẩn mã hoá dữ liệu DES
• 07.1998: Thiết bị thám mã Deep Crack của tổ chức Electronic Frontier Foundation phá được một khoá của DES trong vòng 56 giờ.
• 01.1999: Deep Crack cùng với distributed.net phá được DES trong 22 giờ 15 phút.
• 25.10.1999: Triple DES được khuyến cáo sử dụng cho các hệ thống quan trọng.
• 26.05.2002: AES trở thành tiêu chuẩn thay thế cho DES.
49
Giải thuật mã hoá DES
Giải thuật: • Sử dụng một khoá K tạo ra n khoá con K1, K2, …, Kn. • Hoán vị dữ liệu. • Thực hiện n vòng lặp. Tại mỗi vòng lặp:
▪ Dữ liệu được chia thành hai phần ▪ Áp dụng phép toán thay thế lên một phần, phần còn lại giữ
nguyên. ▪ Hoán vị hai phần cho nhau.
• Hoán vị dữ liệu.
50