Monoalphabetic substitution cipher là gì

Presentation on theme: "Chương II 2 MÃ HÓA (Cryptography) Mã hóa đối xứng SYMMETRIC CIPHERS."— Presentation transcript:

1 Chương II 2 MÃ HÓA (Cryptography) Mã hóa đối xứng SYMMETRIC CIPHERS

2 NỘI DUNG Giới thiệu Những khái niệm cơ bản về mã hóa
Hàm cửa lật một chiều và mã công khai Một số mã công khai thông dụng Nguyên lý thiết kế mã đối xứng Một số mã đối xứng thông dụng Trần Thị Kim Chi

3 Giới thiệu MẬT THƯ 1: 45, 24, 34 – 12, , 35, 11, 34 – 31, 15, 45 (Chapter 1: Overview – Cryptography and Network Security Principles and Practice, 5th Edition) Trần Thị Kim Chi

4 Giới thiệu MẬT THƯ 2: TÍ VỀ - TUẤT THƯƠNG – HỢI NHẤT – SỬU HƯỚNG – DẬU YÊU –DẦN MẬT – MẸO TRỜI – TỊ SẼ - MÙI NGƯỜI – NGỌ THẤY – THÂN BẠN (Chapter 1: Overview – Cryptography and Network Security Principles and Practice, 5th Edition) Trần Thị Kim Chi

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 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 đó. (Chapter 1: Overview – Cryptography and Network Security Principles and Practice, 5th Edition) Trần Thị Kim Chi

6 Các khái niệm cơ bản Kỹ thuật mật mã (cryptology) là ngành khoa học nghiên cứu 2 lĩnh vực: mã hóa (cryptography) và phân tích mật mã (cryptanalysis codebreaking) 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 (Chapter 1: Overview – Cryptography and Network Security Principles and Practice, 5th Edition) Trần Thị Kim Chi

7 Khái niệm mã hóa Mật mã học (cryptography) là ngành khoa học nghiên cứu các phương pháp và kỹ thuật đảm bảo an toàn và bảo mật dữ liệu trong việc truyền tin. Ứng dụng của mật mã: Trong các cơ quan chính phủ: bảo vệ thông tin mật, các thông tin quân sự, ngoại giao, … Trong lĩnh vực kinh tế: bảo mật thông tin tài khoản ngân hàng, giao dịch thanh toán, thông tin khách hàng, … Trong y tế: bảo vệ thông tin cá nhân, Trong bảo vệ thông tin cá nhân: thông tin riêng tư, tài khoản , an toàn trên mạng xã hội, … (Chapter 1: Overview – Cryptography and Network Security Principles and Practice, 5th Edition) Trần Thị Kim Chi

8 Khái niệm mã hóa Phân tích mật mã (cryptanalysis): ngành khoa học nghiên cứu các phương pháp, kỹ thuật nhằm phá vỡ hệ thống mã hóa. Trong sự phát triển của mật mã thì lĩnh vực mật mã và phân tích mật mã phát triển song hành với nhau, tuy nhiên trong học tập, nghiên cứu thì lĩnh vực mật mã học được quan tâm rộng rãi hơn do các ứng dụng thực tiễn, hiệu quả mà nó đem lại. (Chapter 1: Overview – Cryptography and Network Security Principles and Practice, 5th Edition) Trần Thị Kim Chi

9 Khái niệm mã hóa Giao thức mật mã (cryptographic protocol) là tập hợp các quy tắc, trình tự thực hiện sơ đồ mã hóa. Độ an toàn của hệ mã hóa: là khả năng chống lại việc thám mã, trong nhiều trường hợp được tính bằng số phép toán cần thực hiện để thám mã sử dụng thuật toán tối ưu nhất. Hệ thống mật mã (cryptosystem) là hệ thống đảm bảo an toàn dữ liệu sử dụng công cụ mã hóa. Hệ thống mật mã bao gồm: sơ đồ, giao thức mật mã, quy tắc tạo và phân phối khóa. Khái niệm hệ thống mật mã có thể hiểu đơn giản hơn là bao gồm: thuật toán (algorithm) và giá trị mật (key). (Chapter 1: Overview – Cryptography and Network Security Principles and Practice, 5th Edition) Trần Thị Kim Chi

10 Sơ đồ mã hóa Kênh không an toàn (Insecure channel) Dữ liệu gốc
(Plaintext, Cleartext) Mã hóa (Encrypt) Giải mã (Decrypt) Dữ liệu gốc Bản mã (Ciphertext) (Chapter 1: Overview – Cryptography and Network Security Principles and Practice, 5th Edition) Mô hình toán học tổng quát: Mã hóa: C=E(P) Giải mã: P=D(C), với Plaintext (P), Encrypt (E), Ciphertext (C), Decrypt (D) Trần Thị Kim Chi

11 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 (Chapter 1: Overview – Cryptography and Network Security Principles and Practice, 5th Edition) Trần Thị Kim Chi

12 Mô hình đơn giản của Mật Mã
(Chapter 1: Overview – Cryptography and Network Security Principles and Practice, 5th Edition) Trần Thị Kim Chi

13 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” (Chapter 1: Overview – Cryptography and Network Security Principles and Practice, 5th Edition) Trần Thị Kim Chi

14 Hệ thống mã hóa 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ã (Chapter 1: Overview – Cryptography and Network Security Principles and Practice, 5th Edition) Trần Thị Kim Chi

15 Phân loại mã hóa Theo thời gian có thể chia mật mã thành:
Mã hóa cổ điển (classical cryptographic) Mã hóa hiện đại (modern cryptography) Ngoài ra, dựa theo cách thức xử lý dữ liệu đầu (data input) vào người ta phân chia thành 2 loại: Mã hóa khối (block cipher): xử lý dữ liệu đầu vào theo khối tại một thời điểm, cho kết quả theo một khối dữ liệu ở đầu ra. Mã hóa luồng (stream cipher): xử lý tuần tự các phần tử liên tục ở đầu vào và cho kết quả từng phần tử ở đầu ra tại một thời điểm. (Chapter 1: Overview – Cryptography and Network Security Principles and Practice, 5th Edition) Trần Thị Kim Chi

16 Phân loại mã hóa Mã hóa cổ điển (classical cryptographic): đây là kỹ thuật được hình thành từ xa xưa, dựa trên ý tưởng bên gởi sử dụng thuật toán mã hóa cổ điển dựa trên hai kỹ thuật cơ bản: thay thế (substitution) và hoán vị (transposition), bên nhận dựa vào thuật toán của bên gởi để giải mã mà không cần dùng khóa. Do đó, độ an toàn của kỹ thuật này không cao do chỉ dựa vào sự che giấu thuật toán, hiện nay mã hóa cổ điển ít được sử dụng trong thực tế. (Chapter 1: Overview – Cryptography and Network Security Principles and Practice, 5th Edition) Trần Thị Kim Chi

17 Phân loại mã hóa Mã hóa hiện đại (modern cryptography): mã hóa đối xứng (symmetric cipher, secret key cryptography – 1 khóa), bất đối xứng (asymmetric cipher, public key cryptography – 2 khóa), hàm băm (hash functions – không có khóa). (Chapter 1: Overview – Cryptography and Network Security Principles and Practice, 5th Edition) Trần Thị Kim Chi

18 Mã hóa cổ điển (classical cryptographic)
Mã hóa cổ điển dựa trên kỹ thuật thay thế (thay thế kí tự hoặc các kí tự này bằng kí tự hoặc các kí tự khác tương ứng) và hoán vị (thay đổi trật tự, vị trí các ký tự) trong văn bản gốc. Các kỹ thuật này có thể áp dụng đối với một ký tự (monoalphabetic) hoặc nhiều ký tự (polyalphabetic) tùy vào mục đích sử dụng. Các loại mã hóa cổ điển: Mã Caesar (Caesar cipher) Mã hóa đơn bảng (Monoalphabetic Substitution Cipher) Mã hóa Vigenère Cipher (Vigenère cipher) Mã Playfair One-Time Pad Mã hàng rào sắt (rail fence cipher) Trần Thị Kim Chi

19 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

20 Caesar Cipher Ví dụ: Trần Thị Kim Chi

21 Caesar Cipher Để tấn công hệ mật Caesar có thể sử dụng một số kỹ thuật sau: Vét cạn (brute-force): thử tất cả các khả năng biến đổi có thể xảy ra để tìm được quy tắc thay thế, do hệ mã Caesar chỉ có 26 ký tự (tương ứng 25 quy tắc - khóa) nên việc giải mã không mất nhiều thời gian trong điều kiện hiện nay. Tần số xuất hiện kí tự (Character frequencies): dựa vào thống kê xuất hiện của các kí tự trong bản mã, đối chiếu với bảng tần số được khảo sát trước của từng ngôn ngữ. Trần Thị Kim Chi

22 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

23 Caesar Cipher Áp dụng mật mã Ceasar mật mã hóa các bản rõ
Bài tập: Áp dụng mật mã Ceasar mật mã hóa các bản rõ sau với khóa k = 4 actions speak louder than words 2. Đoán khóa k và giải mật cho bản mật sau: ST RFS HFS XJWAJ YBT RFXYJWX 15 Trần Thị Kim Chi

24 Caesar Cipher 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. Trần Thị Kim Chi

25 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

26 Caesar Cipher Ví dụ:Bảng chữ cái tiếng Anh có 26 ký tự: ABCDEFGHIJKLMNOPQRSTUVWXYZ Mã hóa kí tự x với khoảng cách dịch chuyển 1 đoạn n=13 theo qui tắc sau:y=(x+13) mod 26 Giải mã: x=(y-13) mod 26 Mã hóa chuỗi ký tự sau theo qui tắc trên: GUIDELINES FOR TERM PAPERS Kết quả: THVQRYVARF SBE GREZ CNCREF Trần Thị Kim Chi

27 Caesar Cipher Ví dụ Use the additive cipher with key = 15 to encrypt the message “hello”. Solution We apply the encryption algorithm to the plaintext, character by character: Trần Thị Kim Chi

28 Caesar Cipher Ví dụ Use the additive cipher with key = 15 to decrypt the message “WTAAD”. Solution We apply the decryption algorithm to the plaintext character by character: Trần Thị Kim Chi

29 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

30 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

31 Caesar Cipher Code Java Nếu giải mã: encryptMessage(msg,26-k);
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,26-k); Trần Thị Kim Chi

32 Caesar Cipher Trần Thị Kim Chi

33 Caesar Cipher 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

34 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: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 CipherD K V Q F I B J W P E S C X H T M Y A U O L R G Z N Plaintext: ifwewishtoreplaceletters Ciphertext: WIRFRWAJUHYFTSDVFSFUUFYA Trần Thị Kim Chi

35 Monoalphabetic Ciphers
Số lượng hoán vị của 26 chữ cái là 26! =4x1026(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

36 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

37 Monoalphabetic Ciphers
Tần suất của chữ tiếng anh This graph is based on counts done at ADFA in the late 1980's, and used to develop the tables published in Seberry & Pieprzyk [SEBE89]. Note that all human languages have varying letter frequencies, though the number of letters and their frequencies varies. Seberry & Pieprzyk [SEBE89] Appendix A has graphs for 20 languages (most European & Japanese & Malay). Trần Thị Kim Chi

38 Monoalphabetic Ciphers
Tần suất của chữ tiếng anh This graph is based on counts done at ADFA in the late 1980's, and used to develop the tables published in Seberry & Pieprzyk [SEBE89]. Note that all human languages have varying letter frequencies, though the number of letters and their frequencies varies. Seberry & Pieprzyk [SEBE89] Appendix A has graphs for 20 languages (most European & Japanese & Malay). Trần Thị Kim Chi

39 Số lần xuất hiện của các digram (xuất hiện từ 2 lần trở lên) là:
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

40 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

41 Ví dụ khám mã Suy luận tiếp tục ta có được bản rõ Trần Thị Kim Chi

42 Bài tập phá mã sử dụng bảng tần suất
Mã hoá bản rõ: illustrate sử dụng mã thay thế với khoá là 1 hoán vị bất kì sau: CiperText: ZBBUVMCXMH Trang 12

43 Bài tập phá mã sử dụng bảng tần suất
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.

44 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

45 Mã hóa Vigenère Cipher (Vigenère cipher)
Thế kỷ thứ 15, một nhà ngoại giao người Pháp tên là Vigenere đã tìm ra phương án mã hóa thay thế đa bảng. Mã hóa Vigenere được hình thành trên mã hóa Caesar có sử dụng khóa (chuỗi các chữ cái) trên văn bản gốc (gồm các chữ cái). Mã hóa Vigenere là sự kết hợp của nhiều phép mã hóa Caesar với các bước dịch chuyển khác nhau. Để mã hóa, sử dụng bảng mã Vigenere (Hình x) với cột dọc là chuỗi khóa (khóa được lặp đi lặp lại để chiều dài tương ứng với văn bản gốc), cột ngang – văn bản gốc, giao giữa kí tự tương ứng cột chứa khóa và văn bản gốc chính là kí tự mã của thuật toán.

46 Mã hóa Vigenère Cipher (Vigenère cipher)
Trần Thị Kim Chi

47 Mã hóa Vigenère Cipher (Vigenère cipher)
Ví dụ: bản tin: “We are discovered, save yourself” và khóa là từ DECEPTIVE, ta mã hóa nhƣ sau: Ứng với với chữ w trong bản rõ là chữ D trong khóa, nên dòng mã hóa thứ 4 ứng với khóa D trong bảng Vigenere được chọn. Do đó chữ w được mã hóa thành chữ Z. Tương tự như vậy cho các chữ còn lại. Trong ví dụ trên, các chữ e trong bản rõ đƣợc mã hóa tương ứng thành I, T, G, T, H, M trong bản mã. Do đó phƣơng pháp phá mã dựa trên thống kê tần suất chữ cái là không thực hiện được. Trong 3 thế kỷ sau đó mã hóa Vigenere được xem là mã hóa không thể bị phá. Trần Thị Kim Chi

48 Mã hóa Vigenère Cipher (Vigenère cipher)
Độ an toàn của mã hóa Vigenere phụ thuộc vào độ dài của khóa. Khi đó, kẻ tấn công sẽ các định chiều dài của khóa trước khi thực hiện các bước tiếp theo, như việc phân tích tần số cho các bản mã Caesar khác nhau. . Trần Thị Kim Chi

49 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

50 Mã Playfair Mật mã đa ký tự (mỗi lần mã 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 5×5 đượ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 la xem như 1 ký tự Các ký tự trong ma trận không được trùng nhau 2. Mật mã hóa 3. Giải mật mã. Trần Thị Kim Chi

51 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

52 Mã Playfair Bản rõ được mã hóa một lần 2 ký tự theo quy tắc sau:
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

53 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

54 Playfair Cipher Phá mã An toàn được cải tiến 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

55 Mã Playfair Ví dụ 2: 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õ: DHKHMT10A Khóa: smythework Trần Thị Kim Chi

56 Bài tập Mã Playfair Figure An example of a secret key in the Playfair cipher Bài tập 1 Let us encrypt the plaintext “hello” using the key in Figure 3.13. Trần Thị Kim Chi

57 Bài tập Mã Playfair 1. Mật mã hóa bản rõ sau:
hide the gold in the tree stump 2. 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

58 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: F H W Y K L V M K V K X C V K D J S F S A P X Z C V P Bản mã C: LWPOODEMJFBTZNVJNJQOJORGGU Dùng K1 để giải mã thì ta được: “wearediscoveredsaveyourself” Trần Thị Kim Chi

59 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: Khóa K3: FHAHDDRAIQFIASJGJWQSVVBJAZB Bản giải mã: wewillmeetatthepartytonight (we will meet at the party tonight) Trần Thị Kim Chi

60 One-Time Pad (OTP) Trong cả hai trường hợp trên thì bản giải mã đều có ý nghĩa. Nếu người phá mã thực hiện phá mã vét cạn thì sẽ tìm được nhiều khóa ứng với nhiều bản tin có ý nghĩa => không biết được bản tin nào là bản rõ. Điều này chứng minh phương pháp One-Time Pad là phương pháp mã hóa an toàn tuyệt đối. Để phương pháp One-Time Pad là an toàn tuyệt đối thì mỗi khóa chỉ được sử dụng một lần. Nếu một khóa được sử dụng nhiều lần thì cũng không khác gì việc lặp lại một từ trong khóa (ví dụ khóa có từ DECEPTIVE được lặp lại).

61 One-Time Pad (OTP) Thực tế:
Phương pháp One-Time Pad không có ý nghĩa sử dụng thực tế. Vì chiều dài khóa bằng chiều dài bản tin, mỗi khóa chỉ sử dụng một lần, nên thay vì truyền khóa trên kênh an toàn thì có thể truyền trực tiếp bản rõ mà không cần quan tâm đến vấn đề mã hóa.

62 Mã hàng rào sắt (rail fence cipher)
Đây là một mã dùng 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

63 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. Sau đó đọc bảng mã theo từng hàng 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ã MEMATRHTGPRYETEFETEOAAT Trần Thị Kim Chi

64 Rail Fence cipher Ví dụ bản rõ “attackpostponeduntilthisnoon” được viết lại thành bảng 4 x 7 như sau: Khi kết xuất theo từng cột thì có được bản mã: “AODHTSUITTNSAPTNCOIOKNLOPETN” Trần Thị Kim Chi

65 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

66 Rail Fence cipher Một cơ chế phức tạp hơn là chúng ta có thể hoán vị các cột trước khi kết xuất bản mã. Ví dụ chọn một khóa là MONARCH, ta có thể hoán vị các cột: Bản rõ “attackpostponeduntilthisnoon” và có được bản mã: “APTNKNLOPETNAODHTTNSTSUICOIO”. Việc giải mã được tiến hành theo thứ tự ngược lại.

67 Rail Fence cipher Để an toàn hơn nữa => hoán vị 2 lần (double transposition): Sau khi hoán vị lần 1, ta lấy kết quả đó hoán vị lần nữa: Và cuối cùng bản mã là: “NTTCNASILOTOAODSTETIPPHUKNNO” 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ị. 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.

68 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ụ: bản rõ “meet me at the toga party” Key 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

69 Các kỹ thuật hoán vị - nâng cao
Bài tập: Ví dụ: mật mã 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

70 Rail Fence Cipher Bài tập: bản rõ “attack at midnight” với hành rào sắt độ sâu là 2 Trần Thị Kim Chi

71 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. 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. 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

72 Câu hỏi Tại sao khi gửi bản mã trên kênh truyền thì không sợ bị lộ thông tin? 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? 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? Phá mã khác giải mã ở điểm nào? 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? 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? Phương pháp hoán vị dùng nguyên tắc gì để mã hóa? 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

73 Bài tập 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 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

74 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 USOEGCKGCEUQCGAEUGKCUSZUEGBHSKGEHBCUGERPKHEHKHNSZKGGKAD Trần Thị Kim Chi

75 Bài tập 6. 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

76 Mã hóa hiện đại (modern cryptography)
Mã hóa hiện đại (modern cryptography): mã hóa đối xứng (symmetric cipher, secret key cryptography – 1 khóa), bất đối xứng (asymmetric cipher, public key cryptography – 2 khóa), hàm băm (hash functions – không có khóa). (Chapter 1: Overview – Cryptography and Network Security Principles and Practice, 5th Edition) Trần Thị Kim Chi

77 Mã hóa hiện đại (modern cryptography)
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) (Chapter 1: Overview – Cryptography and Network Security Principles and Practice, 5th Edition) Trần Thị Kim Chi

78 Mã hóa hiện đại (modern cryptography)
(Chapter 1: Overview – Cryptography and Network Security Principles and Practice, 5th Edition) Trần Thị Kim Chi

79 Mã hóa đối xứng (symmetric cipher)
Sơ đồ mã hóa đối xứng Secret Key Plaintext Message Encryption Algorithm Decryption Transmitted Ciphertext (Chapter 1: Overview – Cryptography and Network Security Principles and Practice, 5th Edition) Một số thuật toán mã hóa đối xứng: DES, AES, Blowfish, RC5, RC6 …

80 Mã hóa đối xứng (symmetric cipher)
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 PKI and few deploy hints” “An intro to PKI and few deploy hints” DES DES Mã hoá Giải mã Hai khoá giống nhau

81 Phân loại 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 tổ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

82 Stream Ciphers và Block Ciphers
Trần Thị Kim Chi

83 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

84 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ụ p= đơn vị mã hóa có chiều dài k = 4 bít, n = 3: Ví dụ này không phải là mã dòng vì s0, s1, s2 lặp lại khóa K Trần Thị Kim Chi

85 Stream Ciphers Đối với mã dòng, các số si được sinh ra phải đảm bảo một độ ngẫu nhiên nào đó (chu kỳ tuần hoàn dài): Điểm quan trọng nhất của các mã dòng là bộ sinh số ngẫu nhiên Trần Thị Kim Chi

86 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ụ p= đơn vị mã hóa có chiều dài k = 4 bít, n = 3, với các khóa phát sinh ngẫu nhiên sau: s0=0101, s1=1010, s2=1100, s3=0011 Cho biết kết quả sau khi mã hóa Trần Thị Kim Chi

87 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 modulo 2 giống như bảng chân lý của phép toán XOR

88 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ì

89 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= được mã hóa bởi hệ khóa z1,…,z7= Hàm mã hóa: Hàm giải mã:

90 Mã khối (Block Cipher) Trong máy tính các chữ cái được biểu diễn bằng mã ASCII. Trong bản tin nhị phân cũng tồn tại một số đặc tính thống kê nào đó mà người phá mã có thể tận dụng để phá bản mã, dù rằng bản mã bây giờ tồn tại dưới dạng nhị phân. Mã hóa hiện đại quan tâm đến vấn đề chống phá mã trong các trường hợp biết trước bản rõ (known-plaintext), hay bản rõ được lựa chọn (chosen-plaintext). Trần Thị Kim Chi

91 Mã khối (Block Cipher) Ví dụ: chúng ta sử dụng bản rõ là các chữ cái
của một ngôn ngữ gồm có 8 chữ cái A, B, C, D, E, F, G, H trong đó mỗi chữ cái được biểu diễn bằng 3 bít. Như vậy nếu có bản rõ là ’head’ thì biểu diễn nhị phân tương ứng là: Giả sử dùng một khóa K gồm 4 bít 0101 để mã hóa bản rõ trên bằng phép XOR : Trong phép mã hóa trên, đơn vị mã hóa không phải là một chữ cái mà là một khối 4 bít. Để giải mã, lấy bản mã XOR một lần nữa với khóa thì có lại bản rõ ban đầu. Trần Thị Kim Chi

92 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

93 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ã. đây là mã khối an toàn lý tưởng vì Người gởi cũng như người nhận phải biết toàn bộ bảng trên để mã hóa và giải mã Không khả thi vì kích thước khối lớn thì số dòng của bảng khóa cũng lớn và gây trở ngại cho việc lưu trữ cũng như trao đổi khóa giữa người gởi và người nhận Trần Thị Kim Chi

94 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

95 Giới thiệu một số thuật toán
Mã Feistel (Feistel Cipher) Mã DES (Data Encryption Standard) Mã Triple DES Mã AES (Advanced Encryption Standard) RC 4, RC 5, RC 6 (Rivest Cipher 4,5,6 ) Skipjack Blowfish CAST-128 Trần Thị Kim Chi

96 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

97 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: C = Cn = (Ln, Rn) Trần Thị Kim Chi

98 Mã Feistel (Feistel Cipher)
Sơ đồ tính toán của hệ mã Feistel Không gian khóa, hóan vị, thay thế chổ nào? Trần Thị Kim Chi

99 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

100 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

101 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 tăng thì tính an toàn càng cao. (thông thường 16 vòng). Thuật toán phát sinh khóa con (Subkey generation algorithm): Thuật toán càng phức tạp thì sẽ khó khăn hơn trong việc thá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 thám mã. Trần Thị Kim Chi

102 Feistel Cipher Ưu điểm:
Quá trình mã hóa và giải mã trùng nhau, chỉ khác nhau ở thứ tự khóa con, điều này sẽ tiết kiệm được nữa tài nguyên khi thực hiện thuật toán trên phần cứng. Hàm F có thể chọn với độ khó bất kỳ, vì không phải tìm hàm nghịch. Trần Thị Kim Chi

103 Feistel Cipher Nhược điểm:
Vì mỗi vòng mã chỉ thực hiện biến đổi nữa khối dữ liệu, nên cần số vòng mã hóa lớn để đảm bảo độ an toàn của hệ mật, điều này làm giảm đáng kể tốc độ mã. Ngoài ra xây dựng trên cơ sở mạng Feistel tồn tại lớp khóa tương đương, nên làm không gian khóa giảm đi một nữa. Trần Thị Kim Chi

104 Mã DES (Data Encryption Standard)
DES được công nhận vào năm 1977 bởi Viện nghiên cứu quốc gia về chuẩn của Mỹ (NIST –National Institut of Standards and Technology), 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. Trần Thị Kim Chi

105 Đặc điểm của thuật toán DES
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. 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. Des xuất ra bãn mã 64 bit. 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. DES Encryption 64 bit M 64 bit C 56 bits

106 Mô tả thuật toán

107 Các vòng Feistel của mã DES
Trần Thị Kim Chi

108 Các vòng Feistel của mã DES

109 Cấu trúc một vòng của mã DES
< bit------> Li-1 mở rộng g/hoán hộp S giao hoán Ri-1 x Ki Li Ri bit bit Trần Thị Kim Chi

110 Mô tả thuật toán DES nhận vào một thông điệp M 64 bit, một khóa K 56 bit và cho ra một bảng mã C 64 bit. Bước 1: áp dụng một phép hoán vị( bit khởi tạo IP vào M cho ra M’: M’=IP(M). Bước hai, chia M’ thành hai phần: nửa trái L0 =32 bit và nửa phải R0=32 bit. Bước ba, thi hành các phép toán sau với i = 1, 2,…16 (có 16 vòng). Li = Ri-1 Ri = Li-1  f(Ri-1, Ki) Cuối cùng hoán vị với phép hoán vị( IP-1) để được bản mã cuối cùng C.

111 Mô tả thuật toán Thuật toán được thực hiện trong 3 giai đoạn:
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.

112 Mô tả thuật toán Hoán vị khởi tạo và hoán vị kết thúc:
Ta đánh số các bít của khối 64 bít theo thứ tự từ trái sang phải là 0, 1, …, 62, 63: Hoán vị khởi tạo sẽ hoán đổi các bít theo quy tắc sau :

113 Mô tả thuật toán Hoán vị kết thúc hoán đổi các bít theo quy tắc sau:
Hoán vị kết thúc chính là hoán vị nghịch đảo của hoán vị khởi tạo. Đối với knownplaintext hay chosen-plaintext attack, hoán vị khởi tạo và hoán vị kết thúc không có ý nghĩa bảo mật, sự tồn tại của hai hoán vị trên được nhận định là do yếu tố lịch sử.

114 Cấu trúc một vòng của mã DES
Trần Thị Kim Chi

115 Mô tả thuật toán Li=Ri-1 Ri=Li-1f(Ri-1,Ki) với i= 1, 2,…,16
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.

116 Mô tả thuật toán Hoán vị IP-1
Tại vòng thứ 16, R16 đổi chỗ cho L16. Sau đó ghép 2 nửa R16, L16 cho đi qua hoán vị nghịch đảo của hoàn vị IP sẽ tính được bản mã. Bản mã cũng có độ dài 64 bít. 40 8 48 16 56 24 64 32 39 7 47 15 55 23 63 31 38 6 46 14 54 22 62 30 37 5 45 13 53 21 61 29 36 4 44 12 52 20 60 28 35 3 43 11 51 19 59 27 34 2 42 10 50 18 58 26 33 1 41 9 49 17 57 25

117 Mô tả thuật toán Sơ đồ tính hàm f(Ri-1,Ki) Hàm f

118 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. Đố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.

119 Hàm f 32 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 Hàm mở rộng E

120 Hàm f 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. 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.

121 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.

122 S-box Ví dụ: Ta có B1= 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 7 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).

123 S-box

124 S-box

125 S-box

126 S-box

127 Hàm f 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(Ri,Ki). 16 7 20 21 29 12 28 17 1 15 23 26 5 18 31 10 2 8 24 14 32 27 3 9 19 13 30 6 22 11 4 25 Hoán vị P

128 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.

129 Sơ đồ tính khóa K1, K2, …, K16

130 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.

131 Khóa K Các hoán vị cố định PC-1 và PC-2:

132 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.

133 Đặ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õ.

134 Đặ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ỏ.

135 Đặ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.

136 Độ 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 $. 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

137 Độ 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

138 Độ 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

139 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

140 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

141 Mã AES (Advanced Encryption Standard)
Tiêu chuẩn mã hóa tiên tiến (Advanced Encryption Standard - AES) được giới thiệu vào năm 2001 bởi NIST với mục đích thay thế DES có nhiều hạn chế, và được sử dụng rộng rãi trong các ứng dụng hiện nay, thuật toán được thiết kế bởi Joan Daemen và Vincent Rijmen với tên gọi ban đầu là Rijndael. 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

142 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

143 Mã AES (Advanced Encryption Standard)
Trần Thị Kim Chi

144 Mã AES (Advanced Encryption Standard)
Quá trình mã hóa bao gồm 4 bước: B1: AddRoundKey - mỗi byte của khối được kết hợp với khóa con, các khóa con này được tạo ra từ quá trình tạo khóa con Rijndael. Add round key transformation

145 Mã AES (Advanced Encryption Standard)
B2: SubBytes - đây là quá trình thay thế trong đó mỗi byte sẽ được thay thế bằng một byte khác theo bảng tra. Substitute byte transformation

146 Mã AES (Advanced Encryption Standard)
B3: ShiftRows - đổi chỗ, các hàng trong khối được dịch vòng. Shift row transformation

147 Mã AES (Advanced Encryption Standard)
B4: MixColumns - quá trình trộn làm việc theo các cột trong khối theo một chuyển đổi tuyến tính. Tại chu trình cuối thì MixColumns được thay thế bằng AddRoundKey Mix column transformation

148 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

149 Ưu và nhược điểm của mã hóa đối xứng
Ưu điểm: độ an toàn cao (phụ thuộc vào thuật toán và khóa), quá trình mã hóa và giải mã nhanh do đó mã hóa đối xứng được sử dụng phổ biến trong việc truyền dữ liệu. Trần Thị Kim Chi

150 Ưu và nhược điểm của mã hóa đối xứng
. Hạn chế: Một số vấn đề cần quan tâm của hệ thống mã hóa đối xứng liên quan đến khóa, bao gồm: Do quá trình mã hóa và giải mã sử dụng chung một khóa nên khóa (secret key) sử dụng cần phải được bảo quản an toàn tuyệt đối. Vấn đề phân phối khóa Vấn đề quản lý khóa (với hệ thống có n nút khác nhau thì số lượng khóa cần thiết cho hệ thống là n(n+1)/2 Không cung cấp tính chống thoái thác thông tin Trần Thị Kim Chi

151 Câu hỏi và bài tập 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. Mã dòng hoạt động dựa trên nguyên tắc thay thế hay hoán vị? Hệ mã Fiestel có thuận lợi gì trong việc thực hiện mã khối? 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

152 Câu hỏi và bài tập 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? 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. Tại sao gửi bản mã (cipher) trên kê truyền thì không sợ bị lộ thông tin? 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? Khám mã khác giải mã ở điểm nào? 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 khám mã theo kiểu vét cạn khóa? Trần Thị Kim Chi

153 Câu hỏi và bài tập 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? Mã hóa bản rõ “DAI HOC CONG NGHIEP”, dùng phương pháp mã hóa Ceasar với k=3 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 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 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”. Bài tập trang 59 (File BaiGiangATTT.pdf) Trần Thị Kim Chi

154 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

155 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

156 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 So the input yields the output 1100.

157 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 yields the output 1101.

158 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 ( ). The probability of choosing one of these keys is 8.8 × 10−16, almost impossible.

159 THANKS YOU

Mã hóa thay thế đơn bằng là gì?

Mà thay thế Substitution Cipher là gì?

Mà có điện là gì?

Mà hoán vị là gì?