›
›

An toán thông tin - Chương 2: Mã hóa

pdf 166 trang vanle 4830
Download
Bạn đang xem 20 trang mẫu của tài liệu "An toán thông tin - Chương 2: Mã hóa", để tải tài liệu gốc về máy bạn click vào nút DOWNLOAD ở trên

Tài liệu đính kèm:

  • pdfan_toan_thong_tin_chuong_2_ma_hoa.pdf

Nội dung text: An toán thông tin - Chương 2: Mã hóa

  1. 2 (Cryptography) Mã hóa đối xứng SYMMETRIC CIPHERS
  2. NỘI DUNG 1. Giới thiệu 2. Những khái niệm cơ bản về mã hóa 3. Hàm cửa lật một chiều và mã công khai 4. Một số mã công khai thông dụng 5. Nguyên lý thiết kế mã đối xứng 6. Một số mã đối xứng thông dụng Trần Thị Kim Chi 1-2
  3. Giới thiệu Trần Thị Kim Chi 1-3
  4. Giới thiệu Trần Thị Kim Chi 1-4
  5. Vấn Đề đặt ra • Tại sao chúng ta cần mã hóa? • Mã hóa là một phương pháp hỗ trợ rất tốt cho trong việc chống lại những truy cập bất hợp pháp tới dữ liệu được truyền đi qua các kênh truyền thông. • Mã hoá sẽ khiến cho nội dung thông tin được truyền đi dưới dạng mờ và không thể đọc được đối với bất kỳ ai cố tình muốn lấy thông tin đó. Trần Thị Kim Chi 1-5
  6. Mật mã học là gì? • Mật mã học bao gồm hai lĩnh vực : mã hóa (cryptography) và thám mã (cryptanalysis codebreaking) trong đó: • Mã hóa: nghiên cứu các thuật toán và phương thức để đảm bảo những bí mật và xác thực của thông tin gồm các hệ mã mật, các hàm băm, các hệ chư ký điện số, các cơ chế phân phối, quản lý khóa và các giao thức mật mã. • Thám mã: Nghiên cứu các phương pháp phá mã hoặc tạo mã giả gồm các phương pháp thám mã , các phương pháp giả mạo chư ký, các phương pháp tấn • công ,các hàm băm và các giao thức mật mã Trần Thị Kim Chi 1-6
  7. Mật Mã là gì? • Mật mã (Cryptography) là ngành khoa học nghiên cứu các kỹ thuật toán học nhằm cung cấp các dịch vụ bảo vệ thông tin. • W. Stallings (2003), Cryptography and Network Security: Principles and Practice, Third Edition, Prentice Hall Trần Thị Kim Chi 1-7
  8. Mật Mã là gì? • Cách hiểu truyền thống: giữ bí mật nội dung trao đổi GỬI và NHẬN trao đổi với nhau trong khi TRUNG GIAN tìm cách “nghe lén” Trần Thị Kim Chi 1-8
  9. Một số vấn đề trong bảo vệ thông tin • Bảo mật thông tin (Secrecy): đảm bảo thông tin được giữ bí mật. • Toàn vẹn thông tin (Integrity): bảo đảm tính toàn vẹn thông tin trong liên lạc hoặc giúp phát hiện rằng thông tin đã bị sửa đổi. • Xác thực (Authentication): xác thực các đối tác trong liên lạc và xác thực nội dung thông tin trong liên lạc. • Chống lại sự thoái thác trách nhiệm (Non-repudiation): đảm bảo một đối tác bất kỳ trong hệ thống không thể từ chối trách nhiệm về hành động mà mình đã thực hiện • Chống lặp lại: Không cho phép bên thứ ba copy lại văn bản và gửi nhiều lần đến người nhận mà người gửi không hề hay biết. Trần Thị Kim Chi 1-9
  10. Những khái niệm cơ bản về mã hóa • Văn bản gốc (plaintext) là văn bản ban đầu có nội dung có thể đọc được và cần được bảo vệ. • Văn bản mã hóa (ciphertext) là văn bản sau khi mã hóa, nội dung không thể đọc được. • Mã hóa (encryption) là quá trình chuyển văn bản rõ thành văn bản mã hóa. Giải mã (decryption) là quá trình đưa văn bản mã hóa về lại văn bản gốc ban đầu • Hệ thống mã hóa (cryptosystem) • Cryptosystem = encryption + decryption algorithms • Khóa (key) được sử dụng trong quá trình mã hóa và giải mã Trần Thị Kim Chi 1-10
  11. Những khái niệm cơ bản về mã hóa • Ví dụ: SKC với nguyên tắc dời vị trí Nội dung gốc : “Hello everybody” Mã hóa : dời nội dung sang phải – Keycode =1 “Lfmmp fxfsacpea” Giải mã : dời nội dung sang trái – Keycode =1 “Hello everybody” Trần Thị Kim Chi 1-11
  12. Hệ thống mã hóa Trần Thị Kim Chi 1-12
  13. Phân loại mã hóa • Hệ thống mã hóa đối xứng (Symmetric cryptosystem) là hệ thống mã hóa sử dụng một khóa bí mật chia sẻ (shared-secret-key) cho cả hai quá trình mã hóa và giải mã. • Hệ thống mã hóa bất đối xứng (Asymmetric cryptosystem) là hệ thống mã hóa sử dụng một khóa công khai (public key) và một khóa bí mật (private key) cho quá trình mã hóa và giải mã. • Hệ thống mã hóa bất đối xứng còn được gọi là hệ thống mã hóa khóa công khai (public-key cryptosystem) Trần Thị Kim Chi 1-13
  14. Phân loại mã hóa Trần Thị Kim Chi 1-14
  15. Phân loại các thuật toán mật mã • Các thuật toán mã hóa khóa bí mật (hệ mã mật khóa bí mật hay khóa đối xứng SKC (Symmetric Key Cryptosytems), ví dụ : Caesar, DES, AES • Các thuật toán mã hóa khóa công khai (các hệ mã khóa công khai PKC )(Public Key Cryptosystems). Còn gọi là các hệ mã khóa bất đối xứng (Asymmetric Key Cryptosytems). Khóa sử dụng cho các thuật toán này là 2 khóa : Public Key và Private key • Các thuật toán tạo chữ ký số (Digital Signature Algorithms) : RSA, ElGammma • Các hàm băm (Hash functions). Trần Thị Kim Chi 1-15
  16. Mã hoá đối xứng input : văn bản thuần tuý Văn bản mật mã output : văn bản thuần tuý “An intro to “AxCvGsmWe#4^,s “An intro to PKI and few dgfMwir3:dkJeTsY8 PKI and few deploy hints” R\s@!q3%” deploy hints” DE DE S S Mã hoá Giải mã Hai khoá giống nhau
  17. Mã hoá đối xứng • Các khoá giống nhau được sử dụng cho việc mã hoá và giải mã • Thuật toán mã hoá sử dụng khoá đối xứng thường được biết đến là DES (Data Encryption Standard) • Các thuật toán mã hoá đối xứng khác được biết đến như: -Triple DES, DESX, GDES, RDES - 168 bit key -RC2, RC4, RC5 - variable length up to 2048 bits -IDEA - basis of PGP - 128 bit key
  18. Mã hoá bất đối xứng input : văn bản thuần tuý Văn bản mật mã output : văn bản thuần tuý “An intro to “Py75c%bn&*)9|f “An intro to PKI and few De^bDzjF@g5=& PKI and few deploy hints” nmdFgegMs” deploy hints” RSA RSA Mã hoá Giải mã Hai khoá khác nhau
  19. Mã hoá bất đối xứng • Các khoá dùng cho mã hoá và giải mã khác nhau nhưng cùng một mẫu và là cặp đôi duy nhất(khoá private/public) • Khoá private chỉ được biết đến bởi người gửi • Khoá public được biết đến bởi nhiều người hơn nó được sử dụng bởi những nhóm người đáng tin cậy đã được xác thực • Thuật toán mã hoá sử dụng khoá bất đối xứng thường được biết đến là RSA (Rivest,Shamir and Adleman 1978)
  20. Hàm băm • Một hàm băm H nhận được một thông báo m với một độ dài bất kỳ từ đầu vào và đưa ra một xâu bít h có độ dài cố định ở đầu ra h = H(m). • Hàm băm là một hàm một chiều, điều đó có nghĩa là ta không thể tính toán được đầu vào m nếu biết đầu ra h. • Thuật toán sử dụng hàm băm thường được biết đến là MD5
  21. Tạo ra chữ ký số Thông báo hoặc File Thông báo sau khi luật hoá Chữ ký số This is the (Typically 128 bits) document created by Gianni Py75c%bn 3kJfgf*£$& RSA SHA, MD5 Phát sinh Mã hoá hàm băm bất đối xứng priv Signatory's private key Signed Document
  22. Xác thực quyền • Xác minh quyền hạn của các thành viên tham gia truyền thông • Phương pháp phổ biến: • Sử dụng Password : để xác thực người sử dụng
  23. Xác thực quyền • Sử dụng Kerberos: phương thức mã hoá và xác thực trong AD của công nghệ Window • Sử dụng Secure Remote Password (SRP): là một giao thức để xác thực đối với các truy cập từ xa • Sử dụng Hardware Token • Sử dụng SSL/TLS Certificate Based Client Authentication: sử dụng SSL/TLS để mã hoá, xác thực trong VPN, Web • Sử dụng X.509 Public Key • Sử dụng PGP Public Key • Sử dụng SPKI Public Key • Sử dụng XKMS Public Key. • Sử dụng XML Digital Signature
  24. Tiêu chuẩn đánh giá hệ mật mã • Độ an toàn: Một hệ mật được đưa vào sử dụng điều đầu tiên phải có độ an toàn cao. • Chúng phải có phương pháp bảo vệ mà chỉ dựa trên sự bí mật của các khoá, còn thuật toán thì công khai. Tại một thời điểm, độ an toàn của một thuật toán phụ thuộc: Nếu chi phí hay phí tổn cần thiết để phá vỡ một thuật toán lớn hơn giá trị của thông tin đã mã hóa thuật toán thì thuật toán đó tạm thời được coi là an toàn. Nếu thời gian cần thiết dùng để phá vỡ một thuật toán là quá lâu thì thuật toán đó tạm thời được coi là an toàn. Nếu lượng dữ liệu cần thiết để phá vỡ một thuật toán quá lơn so với lượng dữ liệu đã được mã hoá thì thuật toán đó tạm thời được coi là an toàn • Bản mã C không được có các đặc điểm gây chú ý, nghi ngờ.
  25. Tiêu chuẩn đánh giá hệ mật mã • Tốc độ mã và giải mã: Khi đánh giá hệ mật mã chúng ta phải chú ý đến tốc độ mã và giải mã. Hệ mật tốt thì thời gian mã và giải mã nhanh. • Phân phối khóa: Một hệ mật mã phụ thuộc vào khóa, khóa này được truyền công khai hay truyền khóa bí mật. Phân phối khóa bí mật thì chi phí sẽ cao hơn so với các hệ mật có khóa công khai. Vì vậy đây cũng là một tiêu chí khi lựa chọn hệ mật mã.
  26. Một số ứng dụng của mã hóa trong security Một số ứng dụng của mã hoá trong đời sống hằng ngày nói chung và trong lĩnh vực bảo mật nói riêng. Đó là: • Securing Email • Authentication System • Secure E-commerce • Virtual Private Network • Wireless Encryption
  27. SYMMETRIC CIPHERS (Mã hóa đối xứng)
  28. Nội Dung 1. Mã cổ điển (Classical Encryption) 2. Mã dòng (Stream Ciphers) và Mã khối (Block Ciphers) 3. Mã DES (Data Encryption Standard) 4. Mã hiện đại AES (Advanced Encryption Standard) 5. Các mô hình ứng dụng mã khối ( Cryptography and Network Security: Principles and Practices (3rd Ed.) – Chapter 2, 3, 5, 6) Trần Thị Kim Chi 1-28
  29. Mã cổ điển (Classical Encryption) 1.Khái niệm về Mã đối xứng (Symmetric Cipher) 2. Một số mã đối xứng nổi tiếng Trần Thị Kim Chi 1-29
  30. Khái niệm về Mã đối xứng Symmetric Ciper • Là hệ thống mã hóa sử dụng một khóa bí mật chia sẻ (shared-secret-key) cho cả hai quá trình mã hóa và giải mã Trần Thị Kim Chi 1-30
  31. Khái niệm về Mã đối xứng Symmetric Ciper Mô hình trên gồm 5 yếu tố: • Bản rõ P (plaintext) • Thuật toán mã hóa E (encrypt algorithm) • Khóa bí mật K (secret key) • Bản mã C (ciphertext) • Thuật toán giải mã D (decrypt algorithm) • Trong đó: C = E (P, K) P = D (C, K) • Thuật toán mã hóa và giải mã sử dụng chung một khóa, thuật toán giải mã là phép toán ngược của thuật toán mã hóa mô hình trên được gọi là phương pháp mã hóa đối xứng. Trần Thị Kim Chi 1-31
  32. Khái niệm mã đối xứng • Bản rõ X (Plaintext): được gọi là bản tin gốc. Đây là dữ liệu ban đầu ở dạng rõ. Bản rõ có thể được chia nhỏ có kích thước phù hợp. ˗ Thuật toán mã hóa (Encryption algorithm): là thuật toán được sử dụng để mã hóa (thay thế hoặc biến đổi) bản rõ • Khóa bí mật (Secret key): Khóa bí mật được đưa vào thuật toán mã hóa. Khóa này là giá trị độc lập với bản rõ và thuật toán mã hóa. Thuật toán sẽ tạo ra đầu ra (input) khác nhau tùy thuộc vào khóa đặc biệt được dùng tại thời điểm đó. Các kỹ thuật thay thế (substitution) và hoán vị (transformation) được thực hiện bởi thuật toán tùy thuộc vào khóa (key) Trần Thị Kim Chi 1-32
  33. Khái niệm mã đối xứng • Bản mã (Ciphertext): Thông tin, dữ liệu đã được mã hoá ở dạng mờ. Nó tùy thuộc vào plain text và secret key. Cho trước một thông điệp, 2 khóa khác nhau thì sẽ tạo ra được hai bản mã khác nhau. Bản mã là một dòng dữ liệu ngẫu nhiên và nó bền vững và khó hiểu. • Thuật tóan giải mã (Decryption algorithm): Thuật toán giải mã (Decryption algorithm): đây là thực chất là thuật toán mã hóa chạy theo chiều ngược lại. Nó lấy ciphertext và secret key để tạo ra plaintext gốc. • Người gửi/Người nhận (Sender/recipient): Người gửi/Người nhận dữ liệu Trần Thị Kim Chi 1-33
  34. Mô hình mã đối đối xứng Trần Thị Kim Chi 1-34
  35. Mô hình mã đối đối xứng • 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 “nguyenthanhnhut” “SOUDHSMGXSGSGUM” Trần Thị Kim Chi 1-35
  36. Đặc tính của mã đối xứng • Thuật toán mã hóa và giải mã sử dụng chung một khóa, thuật toán giải mã là phép toán ngược của thuật toán mã hóa. Vì vậy mô hình trên được gọi là phương pháp mã hóa đối xứng. • Đặc tính của mã đối xứng: • Khóa phải được giữ bí mật giữa người gởi và người nhận, khóa phải được chuyển một cách an toàn từ người gởi đến người nhận. • Một hệ mã hóa đối xứng phải có tính an toàn. An toàn khi và chỉ khi nó không thể bị phá mã (điều kiện lý tưởng) hoặc thời gian phá mã là bất khả thi. Trần Thị Kim Chi 1-36
  37. Đặc tính của mã đối xứng Câu hỏi: 1.Nếu đã có một kênh an toàn để chuyển khóa như vậy thì tại sao không dùng kênh đó để chuyển bản tin, tại sao cần đến chuyện mã hóa? Câu trả lời là nội dung bản tin thì có thể rất dài, còn khóa thì thường là ngắn. Ngoài ra một khóa còn có thể áp dụng để truyền tin nhiều lần. Do đó nếu chỉ chuyển khóa trên kênh an toàn thì đỡ tốn kém chi phí. Trần Thị Kim Chi 1-37
  38. Kỹ thuật mã hóa (Cryptography) Hệ thống mã hóa được đặc trưng bởi: • Kỹ thuật được sử dụng để chuyển đổi bản rõ thành bản mã. Tất cả các thuật toán được dựa vào 2 kỹ thuật cơ bản: (a) Phép thế (substitution): dùng từng ký tự (hay từng nhóm ký tự) trong bản rõ được thay thế bằng một ký tự (hay một nhóm ký tự) khác để tạo ra bản mã. Bên nhận chỉ cần đảo ngược trình tự thay thế trên bản mã để có được bản rõ ban đầu. (b) Hoán vị (transposition): Các ký tự trong bản rõ được giữ nguyên, chúng chỉ được sắp xếp lại vị trí để tạo ra bản mã. Yêu cầu cơ bản là không có thông tn nào bị mất (có nghĩa là tất cả các thao thác có thể đảo ngược). Trần Thị Kim Chi 1-38
  39. Kỹ thuật mã hóa (Cryptography) • Số khóa được người gửi và người nhận dùng khi mã hóa. • Một khóa duy nhất: Mã đối xứng/ Mã khóa đơn/ Mã khóa bí mật khóa/ Mã hóa thông thường (symmetric, single-key, secret-key, or conventional encryption) • Hai khóa: Mã hóa bất đối xứng/ mã hóa hai khóa/ Mã hóa khóa công khai (asymmetric, two-key, or public-key encryption) Trần Thị Kim Chi 1-39
  40. Kỹ thuật mã hóa (Cryptography) • Cách mà bản rõ được xử lý: • Khối (block cipher): dữ liệu được chia thành từng khối có kích thước xác định và áp dụng thuật toán mã hóa với tham số cho từng khối. • Dòng (stream cipher): từng phần tử ở đầu vào được xử lý liên tục tạo phần tử đầu ra tương ứng. Trần Thị Kim Chi 1-40
  41. Kỹ thuật mã hóa (Cryptography) Ví dụ: Bảng sau đây biểu diễn một thuật toán mã hóa theo khối Theo bảng này, dữ liệu plaintext 010100110111 sẽ đươc mã hóa thành: 010 100 110 111 111 011 000 101 theo key=1 010 100 110 111 100 011 011 111 theo key=4 Ở đây số lượng khóa là 5, do 22 < 5 < 23 nên cần 3 bit để biểu diễn và lưu giữ khóa, tức là kich thước khóa là 3. Đồng thời kích thước khối cũng là 3. Trần Thị Kim Chi 1-41
  42. Phá mã (Cryptanalysis) • Hai cách tiếp cận tấn công mã đối xứng: • Phân tích mật mã (cryptanalysis attack) hay còn gọi “tấn công dùng thuật toán”: dựa trên thuật thoán và một số đặc trưng chung về bản rõ hoặc vài cặp mậu bản rõ – bản mã. Kiểu tấn công này khai thác các đặc trưng của thuật toán để tìm bản rõ cụ thể hoặc tìm kiếm khóa. • Tấn công vén cạn (Brute-force attack): Kẻ tấn công tìm cách thử mọi khóa có thể trên bản mã cho đến khi nhận được bản rõ. Trung bình cần thử một nữa số khóa. Trần Thị Kim Chi 1-42
  43. Phân tích mật mã (Cryptanalysis) • Các kiểu tấn công phân tích mật mã • Biết thuật toán và bản mã xác định bản rõ. • „Biết thuật toán, biết được bản mã/bản rõ tìm khóa. • „Chọn bản rõ và nhận được bản mã, biết thuật toán tìm khóa. • „Chọn bản mã và có được bản rõ tương ứng, biết thuật toán tìm khóa Trần Thị Kim Chi 1-43
  44. Vét cạn (Brute-force) • Về mặt lý thuyết phương pháp này luôn thực hiện được, do có thể tiến hành thử từng khóa, mà số khóa là hữu hạn. • Phần lớn công sức của các tấn công đều tỷ lệ thuận với kích thước khoá. Khóa càng dài thời gian tìm kiếm càng lâu và thường tăng theo hàm mũ. • „Ta có thể giả thiết là kẻ thám mã có thể dựa vào đặc trưng về ngữ cảnh để nhận biết được bản rõ. Trần Thị Kim Chi 1-44
  45. Vét cạn (Brute-force) • Trong phương pháp Ceasar, lý do mà phương pháp này kém an toàn là ở chỗ khóa k chỉ có 25 giá trị, do đó kẻ phá mã có thể thử được hết tất cả các trường hợp của khóa rất nhanh chóng. Phương pháp tấn công này được gọi là phương pháp vét cạn khóa (bruteforce attack). • Chỉ cần nới rộng miền giá trị của khóa thì có thể tăng thời gian phá mã đến một mức độ được coi là bất khả thi. Bảng dưới đây liệt kê một số ví dụ về thời gian phá mã trung bình tương ứng với kích thước của khóa. Trần Thị Kim Chi 45
  46. Một số mã đối xứng nổi tiếng • Một số mã áp dụng phép thay thế: • Mã Caesar (Caesar Cipher) • Mã hóa đơn bản (Monoalphabetic Ciphers) • Mã Playfair (Playfair Cipher) • Mã One-Time Pad (OTP) • Một số mã áp dụng phép hoán vị Trần Thị Kim Chi 1-46
  47. Caesar Cipher • Thế kỷ thứ 3 trước công nguyên, Julius Ceasar đưa ra phương pháp mã hóa này. • Thay thế mỗi ký tự trong bản rõ bằng ký tự đứng sau nó k vị trí trong bảng chữ cái. Giả sử chọn k=3, ta có bảng chuyển đổi: Trần Thị Kim Chi 1-47
  48. Caesar Cipher • Ví dụ: Trần Thị Kim Chi 1-48
  49. Caesar Cipher • Gán cho mỗi chữ cái một con số nguyên từ 0 đến 25: • Với mỗi ký tự trong P thay bằng chữ mã hóa C, trong đó: C = (P + k) mod 26 (mod: phép chia lấy số dư) • Và quá trình giải mã đơn giản là: P = (C – k) mod 26 • k được gọi là khóa. • Hiện nay, mã Ceasar không được xem là an toàn. Trần Thị Kim Chi 1-49
  50. Caesar Cipher • Giả sử có bản tin gốc (bản rõ): meet me after the toga party • Mã hóa bản gốc trên? • Giả sử bạn có được bản mã PHHW PH DIWHU WKH WRJD SDUWB và biết được phương pháp mã hóa và giải mã là phép cộng trừ modulo 26 Bạn có suy ra được bản gốc không? Trần Thị Kim Chi 1-50
  51. Caesar Cipher • Trong 25 trường hợp trên, chỉ có trƣờng hợp k=3 thì bản giải mã tương ứng là có ý nghĩa. • Do đó đối thủ có thể chắc chắn rằng “meet me after the toga party” là bản rõ ban đầu. Trần Thị Kim Chi 1-51
  52. Caesar Cipher Với bản chữ cái Tiếng Việt (29 ký tự) với khóa là 3: • Gán cho mỗi chữ cái một con số nguyên từ 0 đến 28: • Phương pháp Ceasar biểu diễn tiếng Việt nhƣ sau: với mỗi chữ cái p thay bằng chữ mã hóa C, trong đó: C = (p + k) mod 29 • Và quá trình giải mã đơn giản là: p = (C – k) mod 29 Trần Thị Kim Chi 1-52
  53. Caesar Cipher Code Java private String encryptMessage(String msg, int k) { String result = ""; for (int i = 0; i < msg.length(); i++) result += encryptChar(msg.charAt(i), k); return result; } private char encryptChar(char c, int k) { if (Character.isLetter(c)) return (char) ('A' + (c - 'A' + k) % 26); //'A'=65 else return c; } • Nếu giải mã: encryptMessage(msg,26Trần Thị Kim Chi -k); 1-53
  54. Caesar Cipher Trần Thị Kim Chi 1-54
  55. Caesar Cipher 1. Giải mã bản mã sau, giả sử mã hóa Ceasar được sử dụng để mã hóa với k=3: IRXUVFRUHDQGVHYHQBHDUVDJR 2. Khóa • Plain(a): abcdefghijklmnopqrstuvwxyz • Cipher(b): DKVQFIBJWPESCXHTMYAUOLRGZN Mã hóa: • Plaintext: ifwewishtoreplaceletters • Ciphertext: WIRFRWAJUHYFTSDVFSFUUFYA Trần Thị Kim Chi 1-55
  56. Mã hóa đơn bảng (Monoalphabetic Substitution Cipher) • Phương pháp đơn bảng tổng quát hóa phương pháp Ceasar bằng cách dòng mã hóa không phải là một dịch chuyển k vị trí của các chữ cái A, B, C, nữa mà là một hoán vị của 26 chữ cái này. Lúc này mỗi hoán vị được xem như là một khóa. • Việc mã hóa được tiến hành bằng cách thay thế một chữ cái trong bản rõ thành một chữ cái trong bản mã, nên phương pháp này được gọi là phương pháp thay thế. Plain: abcdefghijklmnopqrstuvwxyz Cipher: DKVQFIBJWPESCXHTMYAUOLRGZN Plaintext: ifwewishtoreplaceletters Ciphertext: WIRFRWAJUHYFTSDVFSFUUFYATrần Thị Kim Chi 1-56
  57. Monoalphabetic Ciphers • Số lượng hoán vị của 26 chữ cái là 26! (tương đương với số khóa). • Vì 26! là một con số khá lớn tấn công phá mã vét cạn khóa là bất khả thi (6400 thiên niên kỷ với tốc độ thử khóa là 109 khóa/giây). • phương pháp này được xem là một phương pháp mã hóa an toàn trong suốt 1000 năm sau công nguyên. • Ví dụ: • Chữ ban đầu: a b c d e f g h i j k l m n o p q r s t u v w x y z • Khóa : Z P B Y J R S K F L X Q N W V D H M G U T O I A E C • Như vậy bản rõ meet me after the toga party • được mã hóa thành: NJJU NJ ZRUJM UKJ UVSZ DZMUE Trần Thị Kim Chi 1-57
  58. Monoalphabetic Ciphers • Tuy nhiên vào thế kỷ thứ 9, một nhà hiền triết người Ả Rập tên là Al-Kindi đã phát hiện ra một phương pháp phá mã khả thi khác. Phương pháp phá mã này dựa trên nhận xét sau: • Trong ngôn ngữ tiếng Anh, tần suất sử dụng của các chữ cái không đều nhau, chữ E được sử dụng nhiều nhất, còn các chữ ít được sử dụng thường là Z, Q, J. Tương tự như vậy, đối với cụm 2 chữ cái (digram), cụm chữ TH được sử dụng nhiều nhất. • Nếu chữ E được thay bằng chữ K thì tần suất xuất hiện của chữ K trong bản mã là 13.05%. Đây chính là cơ sở để thực hiện phá mã. Trần Thị Kim Chi 1-58
  59. Monoalphabetic Ciphers Tần suất của chữ tiếng anh Trần Thị Kim Chi 1-59
  60. Monoalphabetic Ciphers Tần suất của chữ tiếng anh Trần Thị Kim Chi 1-60
  61. Ví dụ khám mã Cho bản mã: UZQSOVUOHXMOPVGPOZPEVSGZWSZOPFPESXUDBMETSXAIZ VUEPHZHMDZSHZOWSFPAPPDTSVPQUZWYMXUZUHSX EPYEPOPDZSZUFPOMBZWPPDPTGUDTMOHMQ • Đếm tần suất ký tự Số lần xuất hiện của các digram (xuất hiện từ 2 lần trở lên) là: Trần Thị Kim Chi 1-61
  62. Ví dụ khám mã • Do đó ta có thể đoán P là mã hóa của e, Z là mã hóa của t. Vì TH có tần suất cao nhất • trong các digram nên trong 4 digram ZO, ZS, ZU, ZW có thể đoán ZW là th. • Chú ý rằng trong dòng thứ nhất có cụm ZWSZ, nếu giả thiết rằng 4 chữ trên thuộc một từ thì từ đó có dạng th_t, từ đó có thể kết luận rằng S là mã hóa của a (vì từ THAT có tần suất xuất hiện cao). • Như vậy đến bước này, ta đã phá mã được như sau: Trần Thị Kim Chi 1-62
  63. Ví dụ khám mã Suy luận tiếp tục ta có được bản rõ Trần Thị Kim Chi 1-63
  64. Bài tập phá mã sử dụng bảng tần suất Bài 1 The following shows a plaintext and its corresponding ciphertext. The cipher is probably monoalphabetic because both l’s (els) are encrypted as O’s. Bài 2 The following shows a plaintext and its corresponding ciphertext. The cipher is not monoalphabetic because each l (el) is encrypted by a different character. Trần Thị Kim Chi 1-64
  65. Bài tập phá mã sử dụng bảng tần suất Bài 3 Use the additive cipher with key = 15 to encrypt the message “hello”. Solution We apply the encryption algorithm to the plaintext, character by character:
  66. Bài tập phá mã sử dụng bảng tần suất Bài 4 Use the additive cipher with key = 15 to decrypt the message “WTAAD”. Solution We apply the decryption algorithm to the plaintext character by character:
  67. Example 3.5 Eve has intercepted the ciphertext “UVACLYFZLJBYL”. Show how she can use a brute-force attack to break the cipher. Solution Eve tries keys from 1 to 7. With a key of 7, the plaintext is “not very secure”, which makes sense. 3.67
  68. 3.2.1 Continued Table 3.1 Frequency of characters in English Table 3.2 Frequency of diagrams and trigrams 3.68
  69. 3.2.1 Continued Example 3.6 Eve has intercepted the following ciphertext. Using a statistical attack, find the plaintext. Solution When Eve tabulates the frequency of letters in this ciphertext, she gets: I =14, V =13, S =12, and so on. The most common character is I with 14 occurrences. This means key = 4. 3.69
  70. Bài tập phá mã sử dụng bảng tần suất “YIFQFMZRWQFYVECFMDZPCVMRZWNMDZV EJBTXCDDUMJ NDIFEFMDZCDMQZKCEYFCJMYRNCWJCSZRE XCHZUNMXZ NZUCDRJXỷYMTMEYIFZWDYVZVYFZUMRZCR WNZDZJT XZWGCHSMRNMDHNCMFQCHZJMXJZWIEJYU CFWDINZDIR ” Trần Thị Kim Chi 1-70
  71. Mã Playfair • Được biết như là mã thay thế đa ký tự • Được đề xuất bởi Charles Wheatstone, được mang tên của người bạn Baron Playfair • Mã hóa Playfair xem hai ký tự đứng sát nhau là một đơn vị mã hóa, hai ký tự này được thay thế cùng lúc bằng hai ký tự khác. Trần Thị Kim Chi 1-71
  72. Playfair Cipher • Dựa trên ma trận 5 ×5 của các ký tự được xây dựng bằng từ khóa (keyword) • Trong ma trận trên, khóa là từ MONARCHY được điền vào các dòng đầu của bảng, các chữ cái còn lại của bảng chữ cái được điền tiếp theo một cách tuần tự. Riêng hai chữ I, J được điền vào cùng một ô Trần Thị Kim Chi 1-72
  73. Mã Playfair • Bản rõ được mã hóa một lần 2 ký tự theo quy tắc sau: 1. Cặp hai ký tự giống nhau xuất hiện trong bản rõ sẽ được tách ra bởi 1 ký tự lọc, chẳng hạn như x. Ví dụ trước khi mã hóa “balloon” sẽ được biến đổi thành “balxloxon”. 2. Hai ký tự trong cặp đều rơi vào cùng một hàng, thì mã mỗi ký tự bằng ký tự bên phải nó trong cùng hàng của ma trận khóa, nếu nó là phần tử cuối của hàng thì vòng sang ký tự đầu cùng của hàng, chẳng hạn “ar” mã hóa thành “rm” Trần Thị Kim Chi 1-73
  74. Mã Playfair 3. Hai ký tự mà rơi vào cùng một cột thì nó được mã bằng ký tự ngay dưới, nếu nó ở cuối cột thì vòng sang ký tự ở đầu cột, chẳng hạn “mu” được mã hóa thành “CM”, ov được mã hóa thành HO 4. Trong trường hợp khác, mỗi ký tự của bản rõ trong một cặp được thay bởi ký tự nằm cùng hàng với nó và cột là cùng cột với ký tự cùng cặp. Chẳng hạn, “hs”mã thành “bp”, và“ea”mã thành “im”hoặc “jm” • Trong các trường hợp còn lại, hai ký tự được mã hóa sẽ tạo thành đường chéo của một hình chữ nhật và được thay bằng 2 ký tự trên đường chéo kia. Ví dụ: hs trở thành BP (B cùng dòng với H và P cùng dòng với S); ea trở thành IM (hoặc JM) Trần Thị Kim Chi 1-74
  75. Playfair Cipher • An toàn được cải tiếng hơn với mã hóa đơn bản (simple monoalphabetic ciphers) • Chỉ xét trên 26 ký tự thì mã khóa Playfair có 26x26=676 cặp ký tự. các cặp ký tự này ít bị chênh lệch về tần suất hơn so với sự chênh lệnh tần suất của từng ký tự. Ngoài ra số lượng các cặp ký tự nhiều hơn cũng làm cho việc phá mã tầnsuất khó khăn hơn. Đây chính là lý do mà người ta tin rằng mã hóa Playfair không thể bị phá và được quân đội Anh sử dụng trong chiến tranh thế giới lần thứ nhất. • Tuy nhiên, nó có thể bị bẻ khoá nếu cho trước vài trăm chữ, vì bản mã vẫn còn chứa nhiều cấu trúc của bản rõ. Trần Thị Kim Chi 1-75
  76. Bài tập Mã Playfair Figure 3.13 An example of a secret key in the Playfair cipher Example 3.15 Let us encrypt the plaintext “hello” using the key in Figure 3.13. Trần Thị Kim Chi 1-76
  77. Bài tập Mã Playfair • Hãy tìm hiểu quá trình mã hóa và giải mã bằng phương pháp mã Playfair Bản rõ P= “Dai hoc su pham” Khóa K=tinhoc Trần Thị Kim Chi 1-77
  78. One-Time Pad (OTP) • One-Time Pad – bộ đệm một lần, Được đề xuất bởi Joseph Mauborgne • Một khóa ngẫu nhiên có chiều dài bằng chiều dài của bản rõ, mỗi khóa dùng một lần • Khó bẻ khóa vì không có quan hệ nào giữa bản rõ và bản mã. • Ví dụ mã hóa bản tin “wearediscoveredsaveyourself” • Bản tin P: wearediscoveredsaveyourself • Khóa K1: FHWYKLVMKVKXCVKDJSFSAPXZCVP • Bản mã C: LWPOODEMJFBTZNVJNJQOJORGGU • Dùng K1 để giải mã thì ta được: “wearediscoveredsaveyourself” Trần Thị Kim Chi 1-78
  79. One-Time Pad (OTP) Xét hai trường hợp giải mã bản mã trên với 2 khóa khác nhau •Trường hợp 1: • Bản mã C: LWPOODEMJFBTZNVJNJQOJORGGU • Khóa K2: IESRLKBWJFCIFZUCJLZXAXAAPSY • Bản giải mã: theydecidedtoattacktomorrow (they decided to attack tomorrow) •Trường hợp 2: • Bản mã C: LWPOODEMJFBTZNVJNJQOJORGGU • Khóa K3: FHAHDDRAIQFIASJGJWQSVVBJAZB • Bản giải mã: wewillmeetatthepartytonight (we will meet at the party tonight) Trần Thị Kim Chi 1-79
  80. Mã hàng rào sắt (rail fence cipher) • Đây là một mã dung phép hoán vị hoặc chuyển vị, vì vậy gọi là mã hoán vị hoặc mã chuyển vị (classical transposition or permutation ciphers) • Thực hiện xáo trộn thứ tự các ký tự trong bản rõ. Do thứ tự của các ký tự bị mất đi nên người đọc không thể hiểu được ý nghĩa của bản tin dù các chữ đó không thay đổi. • Đơn giản nhất của mã hóa kiểu này là mã rail fence cipher Trần Thị Kim Chi 1-80
  81. Rail Fence Cipher • Ghi các ký tự trong bản rõ theo từng hàng rào, sau đó kết xuất bản mã dựa trên cột. • Ví dụ: bản rõ “meet me after the toga party” với hành rào sắt độ sâu là 2 (Tách bản rõ thành 2 hàng) • Ví dụ: bản rõ “meet me at the toga party” được viết thành m e m a t r h t g p r y e t e f e t e o a a t • Cho bản mã MEMATRHTGPRYETEFETEOAATTrần Thị Kim Chi 1-81
  82. Rail Fence cipher • Để an toàn hơn nữa, có thể áp dụng phương pháp hoán vị 2 lần (double transposition), tức sau khi hoán vị lần 1, ta lại lấy kết quả đó hoán vị thêm một lần nữa. • Để phá mã phương pháp hoán vị 2 lần không phải là chuyện dễ dàng vì rất khó đoán ra được quy luật hoán vị. • Ngoài ra không thể áp dụng được phương pháp phân tích tần suất chữ cái giống như phương pháp thay thế vì tần suất chữ cái của bản rõ và bản mã là giống nhau. Trần Thị Kim Chi 1-82
  83. Các kỹ thuật hoán vị - nâng cao • bản rõ được viết trên một h.nh chữ nhật và đọc theo cột. Thứ tự các cột trở thành khóa của giải thuật. • Ví dụ • Key 4 1 2 5 3 6 • bản rõ m e e t m e a t t h e t o g a p a r t y x y z w • bản mật etgyetaxmeazmaotthpyetrw • Để tăng độ mật, có thể áp dụng hoán vị nhiều lần Trần Thị Kim Chi 1-83
  84. Các kỹ thuật hoán vị - nâng cao Ví dụ: mật mã playfair • Bản rõ: hide the gold in the tree stump • Bản mật: BM OD ZB XD NA BE KU DM UI XM MO UV IF Trần Thị Kim Chi 1-84
  85. Tóm tắt • Các phương pháp mã hóa cổ điển thường dựa trên hai phương thức. 1. Dùng phương pháp thay thế một chữ cái trong bản rõ thành một chữ cái khác trong bản mã (substitution). Các mã hóa dùng phương thức này là mã hóa Ceasar, mã hóa thay thế đơn bảng, đa bảng, one-time pad. 2. Dùng phương pháp hoán vị để thay đổi thứ tự ban đầu của các chữ cái trong bản rõ (Rail Fence) Trần Thị Kim Chi 85
  86. Câu hỏi 1. Tại sao khi gửi bản mã trên kênh truyền thì không sợ bị lộ thông tin? 2. Khóa là gì? Tại sao cần giữ bí mật khóa chỉ có người gửi và người nhận biết? 3. Tại sao lại gửi khóa qua kênh an toàn mà không gửi trực tiếp bản rõ trên kênh an toàn? 4. Phá mã khác giải mã ở điểm nào? 5. Phá mã theo hình thức vét cạn khóa thực hiện như thế nào? Cần làm gì để chống lại hình thức phá mã theo vét cạn khóa? 6. Các phương pháp Ceasar, mã hóa đơn bảng, đa bảng, one- time pad dùng nguyên tắc gì để mã hóa? 7. Phương pháp hoán vị dùng nguyên tắc gì để mã hóa? 8. Tại sao phương pháp mã hóa đơn bảng có thể bị tấn công phá mã dùng thống kê tần suất? Trần Thị Kim Chi 86
  87. Bài tập 1. Giải mã bản mã sau, giả sử mã hóa Ceasar được sử dụng để mã hóa với k=3: IRXUVFRUHDQGVHYHQBHDUVDJR 2. Mã hóa bản rõ sau: „enemy coming‟, dùng phương pháp mã hóa thay thế đơn bảng với khóa hoán vị K là: IAUTMOCSNREBDLHVWYFPZJXKGQ 3. Mã hóa thông điệp sau bằng phương pháp hoán vị: we are all together biết khóa 24153 4. Phá mã bản mã sau, giả sử mã hóa Ceasar được sử dụng: CSYEVIXIVQMREXIH Trần Thị Kim Chi 87
  88. Bài tập 5. Phá mã bản mã sau (tiếng Anh), biết phương pháp mã hóa sử dụng là phương pháp thay thế đơn bảng: GBSXUCGSZQGKGSQPKQKGLSKASPCGBGBKGUKGCEUKUZKGGBSQEICA CGKGCEUERWKLKUPKQQGCIICUAEUVSHQKGCEUPCGBCGQOEVSHUNSU GKUZCGQSNLSHEHIEEDCUOGEPKHZGBSNKCUGSUKUASERLSKASCUGB SLKACRCACUZSSZEUSBEXHKRGSHWKLKUSQSKCHQTXKZHEUQBKZAEN NSUASZFENFCUOCUEKBXGBSWKLKUSQSKNFKQQKZEHGEGBSXUCGSZQ GKGSQKUZBCQAEIISKOXSZSICVSHSZGEGBSQSAHSGKHMERQGKGSKR EHNKIHSLIMGEKHSASUGKNSHCAKUNSQQKOSPBCISGBCQHSLIMQGKG SZGBKGCGQSSNSZXQSISQQGEAEUGCUXSGBSSJCQGCUOZCLIENKGCA USOEGCKGCEUQCGAEUGKCUSZUEGBHSKGEHBCUGERPKHEHKHNSZKGG KAD Trần Thị Kim Chi 88
  89. Bài tập 6. Phá mã bản mã sau (tiếng Anh), biết phương pháp mã hóa sử dụng là phương pháp thay thế đơn bảng: GBSXUCGSZQGKGSQPKQKGLSKASPCGBGBKGUKGCEUKUZKGGBSQEICA CGKGCEUERWKLKUPKQQGCIICUAEUVSHQKGCEUPCGBCGQOEVSHUNSU GKUZCGQSNLSHEHIEEDCUOGEPKHZGBSNKCUGSUKUASERLSKASCUGB SLKACRCACUZSSZEUSBEXHKRGSHWKLKUSQSKCHQTXKZHEUQBKZAEN NSUASZFENFCUOCUEKBXGBSWKLKUSQSKNFKQQKZEHGEGBSXUCGSZQ GKGSQKUZBCQAEIISKOXSZSICVSHSZGEGBSQSAHSGKHMERQGKGSKR EHNKIHSLIMGEKHSASUGKNSHCAKUNSQQKOSPBCISGBCQHSLIMQGKG SZGBKGCGQSSNSZXQSISQQGEAEUGCUXSGBSSJCQGCUOZCLIENKGCA USOEGCKGCEUQCGAEUGKCUSZUEGBHSKGEHBCUGERPKHEHKHNSZKGG KAD Trần Thị Kim Chi 89
  90. Bài tập 7. Xét bản mã được mã hóa bằng phương pháp One-Time Pad như sau: KITLKE. Nếu bản rõ là „thrill‟ thì khóa là gì? Nếu bản rõ là „tiller‟ thì khóa là gì? 8. Một trường hợp tổng quát của mã hóa Ceasar là mã Affine, trong đó ký tự p được mã hóa thành ký tự C theo công thức: C = E(p, [a, b]) = (ap + b) mod 26 • Một yêu cầu của thuật toán mã hóa là tính đơn ánh, tức nếu p≠q thì E(p) ≠E(q). Mã Affine không phải là đơn ánh với mọi a. Ví dụ, với a=2, b=3 thì E(0) = E(13) = 3. a) Có điều kiện gì đặt ra cho b hay không? Tại sao? b) Xác định những giá trị của a làm cho mã Affine không đơn ánh. Trần Thị Kim Chi 90
  91. Mã dòng (Stream Block) và Mã khối (Block Ciphers) 2.1 Khái niệm 2.2 Mã Feistel (Feistel Cipher) Trần Thị Kim Chi 1-91
  92. Khái niệm • Mã dòng (stream cipher) là một kỹ thuật mã hóa mà mã hóa một dòng dữ liệu số một bit hoặc một byte tại một thời điểm. • Mã khối (block cipher) là một cơ chế mã hóa/giải mã mà trong đó một khối của bản rõ được xử lý như một thổng thể và dùng để tạo ra khối bản mã có độ dài bằng nhau. Thông thường kích cở khổi là 64 hoặc 128 bit được sử dụng. Trần Thị Kim Chi 1-92
  93. Khái niệm • Mã dòng (stream cipher) là một kỹ thuật mã hóa mà mã hóa một dòng dữ liệu số một bit hoặc một byte tại một thời điểm. • Mã khối (block cipher) là một cơ chế mã hóa/giải mã mà trong đó một khối của bản rõ được xử lý như một thổng thể và dùng để tạo ra khối bản mã có độ dài bằng nhau. Thông thường kích cở khổi là 64 hoặc 128 bit được sử dụng. Trần Thị Kim Chi 1-93
  94. Các hệ mã dòng Định nghĩa Mật mã dòng là một bộ (P,C,K,L,F,E,D) thoả mãn dược các điều kiện sau: 1. P là một tập hữu hạn các bản rõ có thể. 2. C là tập hữu hạn các bản mã có thể. 3. K là tập hữu hạn các khoá có thể ( không gian khoá) 4. L là tập hữu hạn các bộ chữ của dòng khoá. 5. F = (f1 f2 ) là bộ tạo dòng khoá. Với i 1 fi : K P i -1 L 6. Với mỗi z L có một quy tắc mã ez E và một quy tắc giải mã tương ứng dz D . ez : P C và dz : C P là các hàm thoả mãn dz(ez(x))= x với mọi bản rõ x P.
  95. Các hệ mã dòng • Các mã dòng thường được mô tả trong các bộ chữ nhị phân tức là P= C=L= Z2. Trong trường hợp này, các phép toán mã và giải mã là phép cộng theo modulo 2.
  96. Stream Ciphers và Block Ciphers Trần Thị Kim Chi 1-96
  97. Stream Ciphers Mã dòng có các đặc tính sau: • Kích thước một đơn vị mã hóa: gồm k bít. Bản rõ được chia thành các đơn vị mã hóa: • Một bộ sinh dãy số ngẫu nhiên: dùng một khóa K ban đầu để sinh ra các số ngẫu nhiên có kích thước bằng kích thước đơn vị mã hóa: • Mỗi số ngẫu nhiên được XOR với đơn vị mã hóa của bản rõ để có được bản mã. Trần Thị Kim Chi 1-97
  98. Stream Ciphers • Quá trình giải mã được thực hiện ngược lại, bản mã C được XOR với dãy số ngẫu nhiên S để cho ra lại bản rõ ban đầu: • Trong ví dụ trên đơn vị mã hóa có chiều dài k = 4 bít, n = 3: Trần Thị Kim Chi 1-98
  99. Các hệ mã dòng • Chú ý: Nếu ta coi "0" biểu thị giá trị "sai" và "1" biểu thị giá trị "đúng" trong đại số Boolean thì phép cộng theo moulo 2 sẽ ứng với phép hoặc loại trừ (XOR). • Bảng chân lý phép cộng theo modul 2 giống như bảng chân lý của phép toán XOR
  100. Các hệ mã dòng • Hàm mã hóa và giải mã được thực hiện bởi cùng một phép toán là phép cộng theo modulo 2(hay phép XOR) • Vì: • Trong đó với zi=0 và zi=1 thì
  101. Các hệ mã dòng • Ví dụ: mã hóa ký tự ‘A’ bởi Alice • Ký tự ‘A’ trong bảng mã ASCII được tướng ứng với mã 6510=10000012 được mã hóa bởi hệ khóa z1, ,z7=0101101 • Hàm mã hóa: • Hàm giải mã:
  102. Mã khối (Block Cipher) Mã khối an toàn lý tưởng • Phép toán XOR có một hạn chế là chỉ cần biết một cặp khối bản rõ và bản mã, người ta có thể dễ dàng suy ra được khóa và dùng khóa đó để giải các khối bản mã khác (knownplaintext attack). : Nếu biết bản mã c0 = 1010 có bản rõ tương ứng là p0 = 1111, thì có thể dễ dàng suy ra khóa là 0101. Trần Thị Kim Chi 1-102
  103. Stream Ciphers và Block Ciphers Trần Thị Kim Chi 1-103
  104. Mã khối (Block Cipher) • Do đó để chống phá mã trong trường hợp known-plaintext hay choosen-plaintext, chỉ có thể là làm cho P và C không có mối liên hệ toán học. Điều này chỉ có thể thực hiện được nếu ta lập một bản tra cứu ngẫu nhiên giữa bản rõ và bản mã. Trần Thị Kim Chi 1-104
  105. Mã Feistel (Feistel Cipher) • Được đề xuất bởi Horst Feistel • Bản rõ sẽ được biến đổi qua một số vòng để cho ra bản mã cuối cùng • Trong đó bản rõ P và các bản mã Ci được chia thành nửa trái và nửa phải: P = (L0, R0) ;Ci = (Li, Ri) i = 1, 2, n Trần Thị Kim Chi 1-105
  106. Mã Feistel (Feistel Cipher) • Quy tắc biến đổi các nửa trái phải này qua các vòng được thực hiện như sau: Li = Ri-1 ; Ri = Li-1  F(Ri-1, Ki) •Ki là một khóa con cho vòng thứ i. Khóa con này được sinh ra từ khóa K ban đầu theo một thuật toán sinh khóa con (key schedule): K K1 K2 Kn •F là một hàm mã hóa dùng chung cho tất cả các vòng. Hàm F đóng vai trò như là phép thay thế còn việc hoán đổi các nửa trái phải có vai trò hoán vị. • Bản mã C được tính từ kết xuất của vòng cuối cùng: Trần Thị Kim Chi 1-106
  107. Mã Feistel (Feistel Cipher) • Sơ đồ tính toán của hệ mã Feistel Trần Thị Kim Chi 1-107
  108. Feistel Cipher • Để giải mã quá trình được thực hiện qua các vòng theo thứ tự ngược lại: C Ln,Rn Ri-1= Li (theo mã hóa Li = Ri-1 ) Li-1 = Ri  F(Ri-1, Ki) (theo mã hóa Ri = Li-1  F(Ri-1, Ki) ) Và cuối cùng bản rõ là P = (L0, R0). Sơ đồ tính toán của hệ mã Feistel Trần Thị Kim Chi 1-108
  109. Feistel Cipher Việc thực hiện chính xác một mã Feistel tùy thuộc vào: • Kích cở khối (Block size): Kích cở khối càng lớn có nghĩa là bảo mật càng cao, nhưng tốc độ mã hóa/giải mã (encryption/decryption) giảm (block size: 64 bits). • Kích cở của khóa (Key size): Khóa càng dài thì bảo mật càng cao nhưng cũng giảm tốc độ mã hóa/giải mã. Bảo mật cao có nghĩa là kháng cự lại được tấn công vét cạn (brute-force attacks) và sự hổn độn (Key size: 128 bits). Trần Thị Kim Chi 1-109
  110. Feistel Cipher • Số dòng (Number of rounds): Bản chất thuật toán mã Feistel là một dòng duy nhất là đã cung cấp đầy đủ tính an toàn nhưng nếu số vòng càng tang thì tính an toàn càng cao. (thông thường 16 vòng). • Thuật toán pháp sinh khóa con (Subkey generation algorithm): Thuật toán càng phức tạp thì sẽ khó khan hơn trong việc khám mã. • Hàm vòng F (Round function F): Càng phức tạp thì đề kháng càng cao đối với khám mã Trần Thị Kim Chi 1-110
  111. Mã DES (Data Encryption Standard) • Phát hành 1977, chuẩn hóa 1979. • Là mã thuộc hệ mã Feistel gồm 16 vòng, ngoài ra DES có thêm một hoán vị khởi tạo trước khi vào vòng 1 và một hoán vị khởi tạo sau vòng 16 • Kích thước của khối là 64 bít. • Ví dụ bản tin “meetmeafterthetogaparty” biểu diễn theo mã ASCII thì mã DES sẽ mã hóa làm 3 lần, mỗi lần 8 chữ cái (64 bít): meetmeaf - tertheto - gaparty. • Kích thước khóa là 56 bít • Mỗi vòng của DES dùng khóa con có kích thước 48 bít được trích ra từ khóa chính. Trần Thị Kim Chi 1-111
  112. Đặc điểm của thuật toán DES • DES là thuật toán mã hóa khối, độ dài mỗi khối là 64 bit . • Khóa dùng trong DES có độ dài toàn bộ là 64 bit. Tuy nhiên chỉ có 56 bit thực sự được sử dụng; 8 bit còn lại chỉ dùng cho việc kiểm tra. • Des xuất ra bãn mã 64 bit. • Thuật toán thực hiện 16 vòng • Mã hoá và giải mã được sử dụng cùng một khoá. • DES được thiết kế để chạy trên phần cứng. 64 bit M 64 bit C DES Encryption 56 bits
  113. Mô tả thuật toán
  114. Mô tả thuật toán
  115. Các vòng Feistel của mã DES Plaintext (64 bit) Key 56 bit giao hoán thuận giao hoán K vòng 1 1 giao hoán dịch vòng trái K vòng 2 2 giao hoán dịch vòng trái . . . . . . K vòng n n giao hoán dịch vòng trái hoán đổi 32 bit giao hoán nghịch Cipher (64 bit) Trần Thị Kim Chi 1-115
  116. Cấu trúc một vòng của mã DES Li-1 Ri-1 mở rộng g/hoán 48 bit K x i 48 bit hộp S 32 bit giao hoán 32 bit x Li Ri Trần Thị Kim Chi 1-116
  117. Cấu trúc một vòng của mã DES Trần Thị Kim Chi 1-117
  118. Mô tả thuật toán Thuật toán được thực hiện trong 3 giai đoạn: 1. Cho bản rõ x (64bit) được hoán vị khởi tạo IP (Initial Permutation) tạo nên xâu bit x0. x0=IP(x)=L0R0 L0 là 32 bit đầu tiên của x0. R0 là 32 bit cuối của x0.
  119. Mô tả thuật toán Bộ chuyển vị IP Hoán vị khởi đầu nhằm đổi chỗ khối dữ liệu vào , thay đổi vị trí của các bít trong khối dữ liệu vào. Ví dụ, hoán vị khởi đầu chuyển bít 1 thành bít 58, bít 2 thành bít 50, bít 3 thành bít 42, 58 50 42 34 26 18 10 2 60 52 44 36 28 20 12 4 62 54 46 38 30 22 14 6 64 56 48 40 32 24 16 8 57 49 41 33 25 17 9 1 59 51 43 35 27 19 11 3 61 53 45 37 29 21 13 5 63 55 47 39 31 23 15 7
  120. Mô tả thuật toán 2. Từ L0 và R0 sẽ lặp 16 vòng, tại mỗi vòng tính: Li=Ri-1 Ri=Li-1f(Ri-1,Ki) với i= 1, 2, ,16 với:  là phép XOR của hai xâu bit: 0  0=0 , 1  1=0 1  0=1, 0  1=1 f là hàm mà ta sẽ mô tả sau. Ki là các xâu có độ dài 48 bit được tính như là các hàm của khóa K. K1 đến K16 lập nên một lịch khóa.
  121. Mô tả thuật toán Hoán vị IP-1 4 8 4 1 5 2 6 3 0 8 6 6 4 4 2 3. Tại vòng thứ 16, R16 đổi 3 7 4 1 5 2 6 3 chỗ cho L16. Sau đó 9 7 5 5 3 3 1 ghép 2 nửa R16, L16 cho 3 6 4 1 5 2 6 3 đi qua hoàn vị nghịch đảo 8 6 4 4 2 2 0 của hoàn vị IP sẽ tính 3 5 4 1 5 2 6 2 7 5 3 3 1 1 9 được bản mã. Bản mã 3 4 4 1 5 2 6 2 cũng có độ dài 64 bít. 6 4 2 2 0 0 8 3 3 4 11 5 1 5 2 5 3 1 9 9 7 3 2 4 1 5 1 5 2 4 2 0 0 8 8 6 3 1 4 9 4 1 5 2 3 1 9 7 7 5
  122. Mô tả thuật toán Hàm f Sơ đồ tính hàm f(Ri-1,Ki)
  123. Hàm f Hàm f lấy đối số đầu là xâu nhập Ri-1 (32 bit) đối số thứ hai là Ki (48 bit) và tạo ra xâu xuất có độ dài 32 bit. Các bước sau được thực hiện. 1. Đối số đầu Ri-1 sẽ được “mở rộng” thành xâu có độ dài 48 bit tương ứng với hàm mở rộng E cố định. E(Ri) bao gồm 32 bit từ Ri, được hoán vị theo một cách thức xác định, với 16 bit được tạo ra 2 lần.
  124. Hàm f 32 1 2 3 4 5 4 5 6 7 8 9 8 9 10 11 12 13 12 13 14 15 16 17 16 17 18 19 20 21 20 21 22 23 24 25 24 25 26 27 28 29 28 29 30 31 32 1 Hàm mở rộng E
  125. Hàm f 2. Tính E(Ri-1)  Ki kết quả được một khối có độ dài 48 bit. Khối này sẽ được chia làm 8 khối B=B1B2B3B4B5B6B7B8. Mỗi khối này có độ dài là 6 bít. 3. Bước kế tiếp là cho các khối Bi đi qua hộp Si sẽ biến một khối có độ dài 6 bit thành một khối Ci có độ dài 4 bít.
  126. S-box • Mỗi hộp S-box là một bảng gồm 4 hàng và 16 cột được đánh số từ 0. Như vậy mỗi hộp S có hàng 0,1,2,3. Cột 0,1,2, ,15. Mỗi phần tử của hộp là một số 4 bít. Sáu bít vào hộp S sẽ xác định số hàng và số cột để tìm kết quả ra. • Mỗi khối Bi có 6 bít kí hiệu là b1, b2, b3, b4, b5 và b6. Bít b1 và b6 được kết hợp thành một số 2 bít, nhận giá trị từ 0 đến 3, tương ứng với một hàng trong bảng S. Bốn bít ở giữa, từ b2 tới b5, được kết hợp thành một số 4 bít, nhận giá trị từ 0 đến 15, tương ứng với một cột trong bảng S.
  127. S-box Ví dụ: Ta có B1=011000 thì b1b6=00 (xác định r=0), b2b3b4b5=1100 (xác định c=12), từ đó ta tìm được phần tử ở vị trí (0,12) > S1(B1)=0101 (tương ứng với số 5). b2b3b4b5=1100 b1b6=00 14 4 13 1 2 15 11 8 3 10 6 12 5 9 0 7 0 15 7 4 14 2 13 1 10 6 12 11 9 5 3 8 4 1 14 8 13 6 2 11 15 12 9 7 3 10 5 0 15 12 8 2 4 9 1 7 5 11 3 14 10 0 6 13 Hộp S1 - Mỗi xâu xuất 4 bit của các hộp S được đưa vào các Cj tương ứng: Cj = Sj(Bj) (1<=j<=8).
  128. Hàm f 4. Xâu bit C = C1C2C3C4C5C6C7C8 có độ dài 32 bit được hoán vị tương ứng với hoán vị cố định P. Kết quả có P(C)= f(R ,K ). i i 16 7 20 21 29 12 28 17 1 15 23 26 Hoán vị P 5 18 31 10 2 8 24 14 32 27 3 9 19 13 30 6 22 11 4 25
  129. Khóa K - K là một xâu có độ dài 64 bit trong đó 56 bit dùng làm khóa và 8 bit dùng để kiểm tra sự bằng nhau (phát hiện lỗi). - Các bit ở các vị trí 8, 16, , 64 được xác định, sao cho mỗi byte chứa số lẻ các số 1, vì vậy từng lỗi có thể được phát hiện trong mỗi 8 bit. - Các bit kiểm tra sự bằng nhau là được bỏ qua khi tính lịch khóa.
  130. Sơ đồ tính khóa K1, K2, , K16
  131. Khóa K Quá trình tạo các khóa con (subkeys) từ khóa K được mô tả như sau: Cho khóa K 64 bit, loại bỏ các bit kiểm tra và hoán vị các bit còn lại của K tương ứng với hoán vị cố định PC-1. Ta viết PC1(K) = C0D0, với C0 bao gồm 28 bít đầu tiên của PC-1(k) và D0 là 28 bit còn lại.
  132. Khóa K Các hoán vị cố định PC-1 và PC-2:
  133. Giải mã • Việc giải mã dùng cùng một thuật toán như việc mã hoá. • Để giải mã dữ liệu đã được mã hoá, quá trình giống như mã hoá được lặp lại nhưng các chìa khoá phụ được dùng theo thứ tự ngược lại từ K16 đến K1, nghĩa là trong bước 2 của quá trình mã hoá dữ liệu đầu vào ở trên Ri-1 sẽ được XOR với K17-i chứ không phải với Ki.
  134. Đặc điểm của mã DES Tính chất bù của mã DES: DES có tính chất bù: trong đó : Ā là phần bù của A theo từng bít (1 thay bằng 0 và ngược lại). EK là bản mã hóa của E với khóa K. P và C là văn bản rõ (trước khi mã hóa) và văn bản mã (sau khi mã hóa). Do tính bù, ta có thể giảm độ phức tạp của tấn công duyệt toàn bộ xuống 2 lần (tương ứng với 1 bít) với điều kiện là ta có thể lựa chọn bản rõ.
  135. Đặc điểm của mã DES Các khóa yếu trong mã Des: Ngoài ra DES còn có 4 khóa yếu (weak keys). Khi sử dụng khóa yếu thì mã hóa (E) và giải mã (D) sẽ cho ra cùng kết quả: EK(EK(P)) = P or equivalently, EK = DK Bên cạnh đó, còn có 6 cặp khóa nửa yếu (semi-weak keys). Mã hóa với một khóa trong cặp, K1, tương đương với giải mã với khóa còn lại, K2: EK1(EK2(P))=P or equivalently EK1=DK2 Tuy nhiên có thể dễ dàng tránh được những khóa này khi thực hiện thuật toán, có thể bằng cách thử hoặc chọn khóa một cách ngẫu nhiên. Khi đó khả năng chọn phải khóa yếu là rất nhỏ.
  136. Đặc điểm của mã DES Triple DES: Triple-DES chính là DES với hai chìa khoá 56 bit. Cho một bản tin cần mã hoá, chìa khoá đầu tiên được dùng để mã hoá DES bản tin đó. Kết quả thu được lại được cho qua quá trình giải mã DES nhưng với chìa khoá là chìa khoá thứ hai. Bản tin sau qua đã được biến đổi bằng thuật toán DES hai lần như vậy lại được mã hoá DES một lần nữa với chìa khoá đầu tiên để ra được bản tin mã hoá cuối cùng. Quá trình mã hoá DES ba bước này được gọi là Triple- DES.
  137. Bài tập .Cho bản rõ mang nội dung: x=“0123D56789ABCDE8”. .Cho khoá K=183457799B3CDFF2 Trong hệ cơ số 16, Thực hiện mã hóa văn bản rõ trên theo thuật toán DES
  138. Độ an toàn của DES • Tấn công vét cạn khóa (Brute Force Attack) • Khóa của DES: 56 bít nên để tiến hành vét cạn khóa cần kiểm tra 256 khóa khác nhau. rất lớn • 1998, tổ chức Electronic Frontier Foundation (EFF) thông báo đã xây dựng được một thiết bị phá mã DES gồm nhiều máy tính chạy song song, trị giá khoảng 250.000$. Thời gian thử khóa là 3 ngày. • Hiện nay mã DES vẫn còn được sử dụng trong thương mại, tuy nhiên người ta đã bắt đầu áp dụng những phương pháp mã hóa khác có chiều dài khóa lớn hơn (128 bít hay 256 bít) như TripleDES hoặc AES. Trần Thị Kim Chi 142
  139. Độ an toàn của DES • Phá mã DES theo phương pháp vi sai (differential cryptanalysis): • Năm 1990 Biham và Shamir đã giới thiệu phương pháp phá mã vi sai. Phương pháp vi sai tìm khóa ít tốn thời gian hơn brute-force. Tuy nhiên phương pháp phá mã này lại đòi hỏi phải có 247 cặp bản rõ - bản mã được lựa chọn (chosen-plaintext). Vì vậy phương pháp này là bất khả thi dù rằng số lần thử có thể ít hơn phương pháp brute-force. Trần Thị Kim Chi 143
  140. Độ an toàn của DES • Phá mã DES theo phương pháp thử tuyến tính (linear cryptanalysis) • Năm 1997 Matsui đưa ra phương pháp phá mã tuyến tính. Trong phương pháp này, cần phải biết trước 243 cặp bản rõ-bản mã (known-plaintext). Tuy nhiên 243 cũng là một con số lớn nên phá mã tuyến tính cũng không phải là một phương pháp khả thi. Trần Thị Kim Chi 144
  141. Mã Triple DES • Một trong những cách để khắc phục yếu điểm kích thước khóa ngắn của mã hóa DES là sử dụng mã hóa DES nhiều lần với các khóa khác nhau cho cùng một bản tin. Đơn giản nhất là dùng DES hai lần với hai khóa khác nhau, cách thức này được gọi là Double DES C=E(E(P, K1),K2) • Điều này giống như là Double DES dùng một khóa có kích thước là 112 byte, chỉ có một hạn chế là tốc độ chậm hơn DES vì phải dùng DES hai lần. Tuy nhiên người ta đã tìm • Một phương pháp tấn công Double DES có tên gọi là gặp- nhau-ở-giữa (meet-in-the middle).Đây là một phương pháp tấn công chosen-plaintext. Trần Thị Kim Chi 145
  142. Mã Triple DES • Nếu dùng DES ba lần với ba khóa khác nhau, cách thức này được gọi là Triple DES: C=E(E(E(P, K1),K2),K3) • Chiều dài khóa là 168 bít sẽ gây phức tạp hơn nhiều cho việc phá mã bằng phương pháp tấn công gặp- nhau-ở-giữa. Trong thực tế người ta chỉ dùng Triple DES với hai khóa K1, K2 mà vẫn đảm bảo độ an toàn cần thiết. C=E(E(E(P, K1),K2),K1) Trần Thị Kim Chi 146
  143. Mã AES (Advanced Encryption Standard) • Thập niên 90, nhận thấy nguy cơ của mã hóa DES là kích thước khóa ngắn, có thể bị phá mã trong tương lai gần, Cục tiêu chuẩn quốc gia Hoa Kỳ đã kêu gọi xây dựng một phương pháp mã hóa mới. Cuối cùng một thuật toán có tên là Rijndael được chọn và đổi tên thành Andvanced Encryption Standard hay AES. • Khóa có kích thước 256 bít là “an toàn mãi mãi” bất kể những tiến bộ trong ngành kỹ thuật máy tính. • AES là thuật toán mã hóa đối xứng dạng khối 128-bit Trần Thị Kim Chi 1-147
  144. Mã AES (Advanced Encryption Standard) • Như DES, mã AES là mã khối, nhiều vòng, nhưng mã AES không phải là một mã Feistel. Thuật toán AES khá phức tạp. • Đặc điểm chính của AES: • Cho phép lựa chọn kích thước khối mã hóa là 128, 192 hay 256 bít. • Cho phép lựa chọn kích thước của khóa một cách độc lập với kích thước khối: là 128, 192 hay 256 bít. • Số lượng vòng có thể thay đổi từ 10 đến 14 vòng tùy thuộc vào kích thước khóa. Trần Thị Kim Chi 1-148
  145. Mã AES (Advanced Encryption Standard) • Độ an toàn của AES làm cho AES được sử dụng ngày càng nhiều và trong tương lai sẽ chiếm vai trò của DES và Triple DES. Trần Thị Kim Chi 1-149
  146. Các mô hình ứng dụng mã khối • Mã khối (như mã DES) được áp dụng để mã hóa một khối dữ liệu có kích thước xác định. Để mã hóa một bản tin dài, bản tin được chia ra thành nhiều khối (P=P0P1P2 Pn-1) và áp dụng mã khối cho từng khối một. Có nhiều mô hình áp dụng mã khối là • Electronic Code Book (ECB) • Cipher Block Chaining Mode (CBC) • Cipher Feedback Mode (CTR) • Output Feedback Mode (OFB) • Counter Mode Trần Thị Kim Chi 1-150
  147. Electronic Code Book (ECB) • Mã hóa từng khối riêng lẻ Trần Thị Kim Chi 1-151
  148. Cipher Block Chaining Mode • Sử dụng đoạn mã hoá của block trước, trong quá trình mã hoá Trần Thị Kim Chi 1-152
  149. Cipher Feedback Mode • Chế độ mã phản hồi: s bit mã hóa trước được đưa vào thanh ghi đầu vào hiện thời Trần Thị Kim Chi 1-153
  150. Cipher Feedback Mode Trần Thị Kim Chi 1-154
  151. Output Feedback Mode • Chế độ mã phản hồi đầu ra: s bit trái đầu ra trước được đưa vào thanh ghi đầu vào hiện thời Trần Thị Kim Chi 1-155
  152. Counter Mode • XOR mỗi khối nguyên bản với 1 giá trị thanh đếm mã hóa Trần Thị Kim Chi 1-156
  153. Counter Mode Trần Thị Kim Chi 1-157
  154. Câu hỏi và bài tập 1. Mã hóa đối xứng hiện đại và mã hóa đối xứng cổ điển khác nhau ở điểm nào. 2. Mã dòng hoạt động dựa trên nguyên tắc thay thế hay hoán vị? 3. Hệ mã Fiestel có thuận lợi gì trong việc thực hiện mã khối? 4. Tại sao mã hóa DES lại dùng các phép biến đổi phức tạp chỉ để mã hóa một khối 64 bít? Trần Thị Kim Chi 158
  155. Câu hỏi và bài tập 1. Khái niệm mã hóa, tại sao phải mã hóa thông tin khi truyền tin trên mạng? 2. Khái niệm mã hóa đối xứng, cơ chế, các thành phần của hệ mã hóa đối xứng. 3. Tại sao gửi bản mã (cipher) trên kê truyền thì không sợ bị lộ thông tin? 4. Khóa là gì? Tại sao cần giữ bí mật khóa chỉ có người gửi và người nhận biết? 5. Khám mã khác giải mã ở điểm nào? 6. Khám mã theo hình thức vét cạn khóa thực hiện như thể nào? Cần làm gì để chống lại hình thức Trần Thị Kim Chi khám mã theo kiểu vét cạn khóa? 159
  156. Câu hỏi và bài tập 7. Các phương pháp Ceasar, mã hóa đơn bảng, đa bảng, one- time pad dùng nguyên tắc gì để mã hóa? 8. Mã hóa bản rõ “DAI HOC CONG NGHIEP”, dùng phương pháp mã hóa Ceasar với k=3 9. Giải mã bản mã sau, giải sự mã hóa Ceasar được sử dụng để mã hóa với k=3 IRXUVFRUHDQGVHYHQBHDUVDJR 7. Mã hóa bản rõ “DAI HOC CONG NGHIEP”, dùng phương pháp mã hóa thay thể đơn bản (Monoalphabetic Ciphers) với khóa hoán vị K là: IAUTMOCSNREBDLHVWYFPZJXKGQ 8. Mã hóa bản rõ “DAI HOC CONG NGHIEP”, dùng phương pháp mã hóa Playfair với khóa k là “monarchy”. 9. Bài tập trang 59 (File BaiGiangATTT.pdf) Trần Thị Kim Chi 160
  157. Câu hỏi và bài tập Example 6.1 Find the output of the initial permutation box when the input is given in hexadecimal as: Solution Only bit 25 and bit 64 are 1s; the other bits are 0s. In the final permutation, bit 25 becomes bit 64 and bit 63 becomes bit 15. The result is
  158. Câu hỏi và bài tập Example 6.2 Prove that the initial and final permutations are the inverse of each other by finding the output of the final permutation if the input is Solution The input has only two 1s; the output must also have only two 1s. Using Table 6.1, we can find the output related to these two bits. Bit 15 in the input becomes bit 63 in the output. Bit 64 in the input becomes bit 25 in the output. So the output has only two 1s, bit 25 and bit 63. The result in hexadecimal is
  159. Câu hỏi và bài tập The input to S-box 1 is 100011. What is the output? Solution If we write the first and the sixth bits together, we get 11 in binary, which is 3 in decimal. The remaining bits are 0001 in binary, which is 1 in decimal. We look for the value in row 3, column 1, in Table 6.3 (S-box 1). The result is 12 in decimal, which in binary is 1100. So the input 100011 yields the output 1100.
  160. Câu hỏi và bài tập The input to S-box 8 is 000000. What is the output? Solution If we write the first and the sixth bits together, we get 00 in binary, which is 0 in decimal. The remaining bits are 0000 in binary, which is 0 in decimal. We look for the value in row 0, column 0, in Table 6.10 (S-box 8). The result is 13 in decimal, which is 1101 in binary. So the input 000000 yields the output 1101. 6.164
  161. Câu hỏi và bài tập What is the probability of randomly selecting a weak, a semi- weak, or a possible weak key? Solution DES has a key domain of 256. The total number of the above keys are 64 (4 + 12 + 48). The probability of choosing one of these keys is 8.8 × 10−16, almost impossible.