Bài giảng Mật mã hóa hiện đại - Chương 1: Tổng quan về mật mã hóa hiện đại - Phạm Việt Hà

Nội dung text: Bài giảng Mật mã hóa hiện đại - Chương 1: Tổng quan về mật mã hóa hiện đại - Phạm Việt Hà

1. TT CNTT HN Wednesday, April 25, 2012 MẬT MÃ HÓA HIỆN ĐẠI Chương 1: Tổng quan về mật mã hóa hiện đại TS. Phạm Việt Hà VIỆN KHOA HỌC KỸ THUẬT BƯU ĐIỆN TRUNG TÂM TƯ VẤN ĐẦU TƯ CHUYỂN GIAO CÔNG NGHỆ 1.1. Sơ lượcvề mậtmãhọc . Mật mã học (cryptography): là khoa học nghiên cứu cách ghi bí mật thông tin nhằm biến bản tin rõ thành các bản mã. . Phân tích mật mã (cryptanalysis): là khoa học nghiên cứu cách phá các hệ mật nhằm phục hồi bản rõ ban đầu từ bản mã. Việc tìm hiểu các thông tin về khóa và các phương pháp biến đổi thông tin cũng là một nhiệm vụ quan trọng của phân tích mật mã. . Kí hiệu: y = Ek(x): y là bản mã của bản rõ x qua hàm biến đổi E (hàm mã hóa) với khóa K x = Dk(y): x là bản rõ của bản mã y qua hàm biến đổi D (hàm giải mã) với khóa K VIỆN KHOA HỌC KỸ THUẬT BƯU ĐIỆN Trang 2 © 2009 | CCIT/RIPT TRUNG TÂM TƯ VẤN ĐẦU TƯ CHUYỂN GIAO CÔNG NGHỆ CCIT/RIPT 1
2. TT CNTT HN Wednesday, April 25, 2012 1.1. Sơ lượcvề mậtmãhọc . Ví dụ: + Bản rõ x: HELLOWORLD +Hàm Ek(x) = x + k mod 26 Cho k = 5 . Khi đó: bảnmãy = ek(x) = MJRRTBTWRI  H: 7 + 5 mod 26 = 12  M;  E: 4 + 5 mod 26 = 9  J;  . Ta cũng có thể suy ra bảnrõx từ bảnmãy từ hàm giải mã: dk(y) = y – k mod 26 VIỆN KHOA HỌC KỸ THUẬT BƯU ĐIỆN Trang 3 © 2009 | CCIT/RIPT TRUNG TÂM TƯ VẤN ĐẦU TƯ CHUYỂN GIAO CÔNG NGHỆ 1.1. Sơ lượcvề mậtmãhọc - Có ba phương pháp tấn công cơ bản của thám mã: + Tìm khóa vét cạn. + Phân tích thống kê. + Phân tích toán học. -Việc tấn công của thám mã có thể được thực hiện với các giả định: + Tấn công chỉ với bản mã: biết thuật toán, bản mã, dùng phương pháp thống kê xác định bản rõ + Tấn công với bản rõ đã biết: biết thuật toán, biết được bản mã/bản rõ, tấn công tìm khóa + Tấn công với các bản rõ được chọn: chọn bản rõ và nhận được bản mã, biết thuật toán, tấn công tìm khóa. + Tấn công với các bản mã được chọn: chọn bản mã và có được bản rõ tương ứng, biết thuật toán, tấn công tìm khóa VIỆN KHOA HỌC KỸ THUẬT BƯU ĐIỆN Trang 4 © 2009 | CCIT/RIPT TRUNG TÂM TƯ VẤN ĐẦU TƯ CHUYỂN GIAO CÔNG NGHỆ CCIT/RIPT 2
3. TT CNTT HN Wednesday, April 25, 2012 1.1. Sơ lượcvề mậtmãhọc - Chú ý: • Một hệ mật có thể bị phá chỉ với bản mã thường là hệ mật có độ an toàn thấp. • Một hệ mật là an toàn với kiểu tấn công có các bản rõ được chọn thường là một hệ mật có độ an toàn cao. - Khi xây dựng một hệ mật người ta thường xem xét tới các tiêu chuẩn sau: • Độ mật cần thiết. • Kích thước không gian khóa. • Tính đơn giản và tốc độ mã hóa và giải mã. • Tính lan truyền sai. • Tính mở rộng bản tin. VIỆN KHOA HỌC KỸ THUẬT BƯU ĐIỆN Trang 5 © 2009 | CCIT/RIPT TRUNG TÂM TƯ VẤN ĐẦU TƯ CHUYỂN GIAO CÔNG NGHỆ 1.2. Mộtsố khái niệmcơ bản -Bản rõ (Plaintext): Dạng ban đầu của thông báo -Bản mã (Ciphertext): Dạng mã của bản rõ ban đầu - Khóa (Key): thông tin tham số dùng để mã hóa. - Mã hóa (Encryption): Quá trình mã 1 thông báo sao cho nghĩa của nó không bị lộ ra -Giải mã (Decryption): Quá trình ngược lại biến đổi 1 thông báo đã mã ngược trở lại thành dạng thông thường. VIỆN KHOA HỌC KỸ THUẬT BƯU ĐIỆN Trang 6 © 2009 | CCIT/RIPT TRUNG TÂM TƯ VẤN ĐẦU TƯ CHUYỂN GIAO CÔNG NGHỆ CCIT/RIPT 3
4. TT CNTT HN Wednesday, April 25, 2012 1.3. Hệ thống thông tin số Ý nghĩa của khối mã bảo mật đó là bảo vệ các thông tin không bị khai thác bất hợp pháp Đầu vào rõ Bản rõ Bản mã Biến đổi Mã Mã bảo Mã A/D nguồn mật kênh Nguồn tin (tương tự tương tự – số) Từ mã được truyền Kênh truyền (tạp âm, đa đường, giao thoa, nhiễu, nghe trộm ) Biến đổi Giải mã Giải mã D/A (số - Giải mã tương tự) nguồn mật kênh Nh ận tin Đầu ra số Bản rõ Bản mã VIỆN KHOA HỌC KỸ THUẬT BƯU ĐIỆN Trang 7 © 2009 | CCIT/RIPT TRUNG TÂM TƯ VẤN ĐẦU TƯ CHUYỂN GIAO CÔNG NGHỆ 1.3. Hệ thống thông tin số . Trong hệ thống TTS, khối mã bảo mật có chức năng bảo vệ cho thông tin không bị khai thác bất hợp pháp, chống lại các tấn công sau: . Thám mã thụ động, bao gồm các hoạt động: • Thu chặn. • Dò tìm. • So sánh tương quan. • Suy diễn. . Thám mã tích cực, bao gồm các hoạt động: • Giả mạo. • Ngụy trang. • Sử dụng lại. • Sửa đổi. VIỆN KHOA HỌC KỸ THUẬT BƯU ĐIỆN Trang 8 © 2009 | CCIT/RIPT TRUNG TÂM TƯ VẤN ĐẦU TƯ CHUYỂN GIAO CÔNG NGHỆ CCIT/RIPT 4
5. TT CNTT HN Wednesday, April 25, 2012 1.4. Hệ mật hoàn thiện Có hai quan điểm về độ an toàn của một hệ mật: Độ an toàn tính toán và Độ an toàn không điều kiện . Độ an toàn tính toán: Là độ đo liên quan đến những nỗ lực tính toán cần thiết để phá một hệ mật. • Một hệ mật được coi là an toàn về mặt tính toán nếu như thuật toán tốt nhất để phá hệ mật đó cần ít nhất N phép toán, N là số rất lớn nào đó. • Tuy nhiên, chưa có một hệ mật nào thỏa mãn điều kiện này vì vậy thực tế người ta coi hệ mật là an toàn về tính toán nếu có một phương pháp tốt nhất phá hệ này cũng phải cần thời gian lớn không thể chấp nhận được. • Có một quan điểm khác chứng minh về độ an toàn tính toán đó là quy độ an toàn của một hệ mật về một bài toán đã được nghiên cứu kĩ và được coi là khó. Ví dụ chứng minh được hệ mật không, thể phân tích được thành thừa số nguyên n cho trước và đôi khi hệ mật được gọi là “an toàn chứng minh được”. VIỆN KHOA HỌC KỸ THUẬT BƯU ĐIỆN Trang 9 © 2009 | CCIT/RIPT TRUNG TÂM TƯ VẤN ĐẦU TƯ CHUYỂN GIAO CÔNG NGHỆ 1.4. Hệ mật hoàn thiện Thuật toán Để hình dung “độ phức tạp” của các thuật toán khi làm việc với các số lớn, ta xem bảng dưới đây cho khoảng thời gian cần thiết để phân tích một số nguyên n ra thừa số nguyên tố bằng thuật toán nhanh nhất được biết hiện nay: VIỆN KHOA HỌC KỸ THUẬT BƯU ĐIỆN Trang 10 © 2009 | CCIT/RIPT TRUNG TÂM TƯ VẤN ĐẦU TƯ CHUYỂN GIAO CÔNG NGHỆ CCIT/RIPT 5
6. TT CNTT HN Wednesday, April 25, 2012 1.4. Hệ mật hoàn thiện . Độ an toàn không điều kiện: Là độ đo liên quan đến độ an toàn của các hệ mật khi không có một hạn chế nào được đặt ra về khối lượng tính toán mà Oscar được phép thực hiện (trong đó Oscar là một đối phương muốn tìm ra nội dung bản rõ của bản mã chặn được song không phải là người nhận được chỉ định trước). • Một hệ mật được gọi là an toàn không điều kiện nếu nó không thể bị phá thậm chí với khả năng tính toán không hạn chế. • Kết luận: - Độ an toàn không điều kiện của một hệ mật không thể được nghiên cứu theo quan điểm độ phức tạp tính toán vì thời gian tính toán cho phép không hạn chế -Phải dựa trên cơ sở lí thuyết xác suất. VIỆN KHOA HỌC KỸ THUẬT BƯU ĐIỆN Trang 11 © 2009 | CCIT/RIPT TRUNG TÂM TƯ VẤN ĐẦU TƯ CHUYỂN GIAO CÔNG NGHỆ 1.4. Hệ mật hoàn thiện Định nghĩa 1: . X và Y là các biến ngẫu nhiên (bnn) . p(x): xác suất (xs) để X nhận giá trị x . p(y): xs để Y nhận giá trị y . p(x, y): xs đồng thời để X nhận giá trị x và Y nhận giá trị y. . p(x| y): xs để X nhận giá trị x với điều kiện (đk) Y nhận giá trị y. . X và Y được gọi là độc lập nếu p(x, y) = p(x).p(y), với | x є X và | y є Y. . Quan hệ giữa xs đồng thời và xs có điều kiện được biểu thị theo công thức sau: p(x,y) = p(x).p(y|x) = p(y).p(x|y) Định lý Bayes Nếu p(y) > 0 thì: VIỆN KHOA HỌC KỸ THUẬT BƯU ĐIỆN Trang 12 © 2009 | CCIT/RIPT TRUNG TÂM TƯ VẤN ĐẦU TƯ CHUYỂN GIAO CÔNG NGHỆ CCIT/RIPT 6
7. TT CNTT HN Wednesday, April 25, 2012 1.4. Hệ mật hoàn thiện Trong phần này, giả sử rằng một khóa cụ thể chỉ được dùng cho một bản mã và giả sử có một phân bố xác suất trên không gian bản rõ P. Kí hiệu xác suất tiên nghiệm để bản rõ xuất hiện là pP(x). Cũng giả sử rằng khóa K được chọn theo một phân bố xác suất xác định nào đó (thường thì khoá K được chọn ngẫu nhiên tuy nhiên cũng không bắt buộc), kí hiệu xác suất để khóa K được chọn là pK(K). Vì khóa K được chọn trước khi người gửi biết bản rõ nên có thể giả định rằng khóa K và bản rõ x là độc lập với nhau. Với mỗi khóa K K , thì tập các bản mã có thể nếu K là khoá được xác định như sau: Hai phân bố xác suất trên P và trên K sẽ tạo ra một phân bố xác suất trên C. Khi đó với mỗi y C ta có: Ta thấy với bất kì y C và x P , có thể tính được xác suất có điều kiện pC(y|x), xác suất y là bản mã với điều kiện x là bản rõ: Sử dụng định lí Bayes ta nhận được công thức sau: VIỆN KHOA HỌC KỸ THUẬT BƯU ĐIỆN Trang 13 © 2009 | CCIT/RIPT TRUNG TÂM TƯ VẤN ĐẦU TƯ CHUYỂN GIAO CÔNG NGHỆ 1.4. Hệ mật hoàn thiện Ví dụ: Với mỗi khóa K, thì tập các bản mã có thể: Hai phân bố xs trên P và K sẽ tạo nên phân bố xs trên C Xs có đk: Và tính được: VIỆN KHOA HỌC KỸ THUẬT BƯU ĐIỆN Trang 14 © 2009 | CCIT/RIPT TRUNG TÂM TƯ VẤN ĐẦU TƯ CHUYỂN GIAO CÔNG NGHỆ CCIT/RIPT 7
8. TT CNTT HN Wednesday, April 25, 2012 1.4. Hệ mật hoàn thiện Định nghĩa2: Một hệ mật có độ mật hoàn thiện nếu: pP(x|y) = pP(x), với mọi x thuộc P, y thuộc C Định lý: Giả sử 26 khóa trong mã dịch vòng (MDV) có xác suấtnhư nhau và bằng 1/26. Khi đó MDV sẽ có độ mật hoàn thiện với mọi phân bố xác suấtcủa bản rõ Chứng minh: Kết luận: Như vậy nếu dùng một khóa ngẫu nhiên để mã hóa mỗi kí tự của bản rõ thì mã dịch vòng là một hệ mật không phá được. VIỆN KHOA HỌC KỸ THUẬT BƯU ĐIỆN Trang 15 © 2009 | CCIT/RIPT TRUNG TÂM TƯ VẤN ĐẦU TƯ CHUYỂN GIAO CÔNG NGHỆ 1.5. Entropy - Entropy là khái niệm trong lí thuyết thông tin do Shannon đưa ra vào năm 1948. - Liên quan đến vấn đề mã thám hệ mật chỉ biết bản mã trong thời gian đủ lớn khi dùng cùng một khoá cho nhiều lần mã. -Có thể coi entropy là đại lượng đo thông tin hay còn gọi là độ bất định, nó được tính như một hàm phân bố xác suất. -Giả sử có một biến ngẫu nhiên X nhận các giá trị trên một tập hữu hạn theo một phân bố xác suất p(X). Entropy của X là thông tin thu nhận được bởi một sự kiện xảy ra tuân theo phân bố p(X) hoặc là độ bất định về kết quả khi sự kiện chưa xảy ra. Kí hiệu entropy của X là H(X). VIỆN KHOA HỌC KỸ THUẬT BƯU ĐIỆN Trang 16 © 2009 | CCIT/RIPT TRUNG TÂM TƯ VẤN ĐẦU TƯ CHUYỂN GIAO CÔNG NGHỆ CCIT/RIPT 8
9. TT CNTT HN Wednesday, April 25, 2012 1.5. Entropy Một ví dụ cụ thể là là phép tung đồng xu với phân bố xác suất là: p(mặt xấp) = p(mặt ngửa) = 1/2. Ta có thể nói rằng thông tin hay chính là entropy của phép tung đồng xu là một bit vì ta có thể mã hóa mặt xấp là 1 và mặt ngửa là 0. Tương tự entropy của n phép tung đồng xu có thể được mã hóa bằng một xâu bit có độ dài n. Một ví dụ khác phức tạp hơn, giả sử có một biến ngẫu nhiên X có thể nhận ba giá trị x1, x2, x3, với xác suất tương ứng là 1/2, 1/4, 1/4. Cách mã hóa hiệu quả nhất của 3 biến cố này là mã hóa x1 là 0, mã hóa x2 là 10, mã hóa x3 là 11. Khi đó, số bit trung bình trong phép mã hóa này là: 1/2 1 + 1/4 2 + 1/4 2 = 3/2 Nhận xét: - Từ hai ví dụ này ta thấy, một biến cố xảy ra với xác suất 2-n có thể mã hóa được bằng một xâu bit có độ dài n. VIỆN KHOA HỌC KỸ THUẬT BƯU ĐIỆN Trang 17 © 2009 | CCIT/RIPT TRUNG TÂM TƯ VẤN ĐẦU TƯ CHUYỂN GIAO CÔNG NGHỆ 1.6. Các tính chấtcủa Entropy • Trước tiên nhắclạimộtsố kiếnthức – f lồi trên khoảng I: – f lồithựcsự trên I nếu: – ĐL 5 (Bất đẳng thứcJensen) Giả sử f là mộthàmlồithựcsự và liên tục trên khoảng I, và với, 1 ≤ i ≤ n. Khi đó: trong đóxi є I, 1 ≤ i ≤ n. Ngoài ra dấu“=” xảy ra khi và chỉ khi x1 = . = xn . VIỆN KHOA HỌC KỸ THUẬT BƯU ĐIỆN Trang 18 © 2009 | CCIT/RIPT TRUNG TÂM TƯ VẤN ĐẦU TƯ CHUYỂN GIAO CÔNG NGHỆ CCIT/RIPT 9
10. TT CNTT HN Wednesday, April 25, 2012 1.6. Các tính chấtcủa Entropy • Các tính chất: – Giả sử X là mộtbiếnngẫu nhiên có phân bố xs p1, p2, , pn, trong đópi > 0, 1 ≤ i ≤ n. Khi đó H(X) ≤ log2n. Dấu“=” xảy ra khi và chỉ khi pi = 1/n, 1 ≤ i ≤ n – H(X, Y) ≤ H(X) + H(Y) Đẳng thứcxảy ra khi và chỉ khi X và Y là các biếncốđộclập. VIỆN KHOA HỌC KỸ THUẬT BƯU ĐIỆN Trang 19 © 2009 | CCIT/RIPT TRUNG TÂM TƯ VẤN ĐẦU TƯ CHUYỂN GIAO CÔNG NGHỆ 1.6. Các tính chấtcủa Entropy X và Y là hai bnn, khi đóvới giá trị xác định bấtkìy củaY, ta cómột phân bố xs có đk p(X|y). Rõ ràng là: – Ta định nghĩa entropy có điềukiện H(X| Y) là trung bình trọng sốứng với các xs p(y) của entropy H(X| y) trên mọi giá trị có thể y. – H(X| Y) được tính bằng: – H(X,Y) = H(X|Y) +H(Y) – H(X|Y) ≤ H(X), dấu“=” xảy ra khi và chỉ khi X, Y độclập VIỆN KHOA HỌC KỸ THUẬT BƯU ĐIỆN Trang 20 © 2009 | CCIT/RIPT TRUNG TÂM TƯ VẤN ĐẦU TƯ CHUYỂN GIAO CÔNG NGHỆ CCIT/RIPT 10
11. TT CNTT HN Wednesday, April 25, 2012 1.6. Các khóa giả và khoảng duy nhất Trong phầnnàyta sẽ áp dụng các kếtquả về entropy ở trên cho các hệ mật . Trướchếtta sẽ chỉ ra quan hệ giữa các entropy của các thành phần trong hệ mật. . Định lý: Giả sử (P, C, K, E, D) là mộthệ mật, khi đó: H(K|C) = H(K) +H(P) – H(C) . Khóa giả: Các khóa mà thám mã có thể rút ra nhưng không phải là khóa đúng . Ví dụ: giả sử thám mã thu được bản mã WNAJW được mã bằng phương pháp MDV. Chỉ có 2 xâu bản rõ có ý nghĩa là river và arena tương ứng với các khóa F (=5) và W (=22). Trong hai khóa này có 1 khóa đúng và khóa còn lại khóa giả. Mục đích là tìm ra giới hạn cho số trung bình các khóa giả VIỆN KHOA HỌC KỸ THUẬT BƯU ĐIỆN Trang 21 © 2009 | CCIT/RIPT TRUNG TÂM TƯ VẤN ĐẦU TƯ CHUYỂN GIAO CÔNG NGHỆ 1.6. Các khóa giả và khoảng duy nhất Giả sử (P, C, K, E, D) là hệ mật đang được sử dụng. Một xâu của bản rõ x1x2 xn sẽ được mã hóa bằng một khóa tạo ra xâu bản mã y1y2 yn. Mục đích cơ bản của thám mã là tìm ra khoá. Ta xem xét các phương pháp tấn công chỉ với bản mã, coi Oscar có khả năng tính toán vô hạn và biết bản rõ là một văn bản theo ngôn ngữ tự nhiên. Nói chung, Oscar có khả năng rút ra một số khóa nhất định (các khóa có thể hay các khóa chấp nhận được), trong đó chỉ có một khóa là đúng còn các khoá khác được gọi là khóa giả. Mục đích là ta phải tìm ra giới hạn cho số trung bình các khóa giả, để làm được điều này ta sẽ dựa vào entropy (cho một kí tự) của một ngôn ngữ tự nhiên L, kí hiệu là HL. HL là lượng thông tin trung bình trên một kí tự trong một xâu có nghĩa của bản rõ. VIỆN KHOA HỌC KỸ THUẬT BƯU ĐIỆN Trang 22 © 2009 | CCIT/RIPT TRUNG TÂM TƯ VẤN ĐẦU TƯ CHUYỂN GIAO CÔNG NGHỆ CCIT/RIPT 11
12. TT CNTT HN Wednesday, April 25, 2012 1.6. Các khóa giả và khoảng duy nhất (Chú ý một xâu ngẫu nhiên các kí tự của bảng chữ cái sẽ có entropy trên một kí tự là log226 4.70). Ta có thể lấy H(P) làm xấp xỉ bậc nhất cho HL. Nếu L là Anh ngữ, theo nghiên cứu người ta đã tính được xác suất xuất hiện của mỗi kí tự trong ngôn ngữ tiếng Anh, dựa vào đó ta tính được . Tuy nhiên các kí tự liên tiếp không độc lập với nhau và chính sự tương quan này sẽ làm giảm entropy, ví dụ trong tiếng Anh, chữ Q luôn đi kèm với chữ U. Để làm xấp xỉ bậc hai, tính entropy của phân bố xác suất của tất cả các bộ đôi rồi chia cho 2. Tổng quát ta định nghĩa Pn là biến ngẫu nhiên có phân bố xác suất là phân bố xác suất của tất cả các bộ n của bản rõ VIỆN KHOA HỌC KỸ THUẬT BƯU ĐIỆN Trang 23 © 2009 | CCIT/RIPT TRUNG TÂM TƯ VẤN ĐẦU TƯ CHUYỂN GIAO CÔNG NGHỆ 1.6. Các khóa giả . Định nghĩa: Giả sử L là một ngôn ngữ tự nhiên, entropy củaL đượcxácđịnh là lượng sau: . Độ dư của L là: . Nhậnxét: . HL đo entropy trên mỗikítự của ngôn ngữ L . RL đophần “kí tự vượttrội” là phầndư vì entropy củamột ngôn ngữ ngẫu nhiên là log2|P |. . Dựa vào giá trị củaHL ta có thểđánh giá đượclượng thông tin trung bình củamột ngôn ngữ, ví dụ vớiL làAnhngữ thì 1.0 ≤ HL ≤ 1.5. Giả sử lấyHL = 1.25 thì độ dư là 75% tức là dùng thuật toán Huffman (phép mã hóa nén) có thể tìm ra đượcmột đơn ánh cho các bộ n (n đủ lớn) mà nén vănbảntiếng Anh xuống còn 1/4 vănbảngốc VIỆN KHOA HỌC KỸ THUẬT BƯU ĐIỆN Trang 24 © 2009 | CCIT/RIPT TRUNG TÂM TƯ VẤN ĐẦU TƯ CHUYỂN GIAO CÔNG NGHỆ CCIT/RIPT 12
13. TT CNTT HN Wednesday, April 25, 2012 1.6. Khoảng duy nhất . Khoảng duy nhất của một hệ mật được định nghĩa là giá trị của n mà ứng với giá trị này, số khóa giả trung bình bằng 0 (kí hiệu giá trị này là n0). Điều đó có nghĩa n0 là độ dài trung bình cần thiết của bản mã để thám mã có thể tính toán một cách duy nhất với thời gian đủ lớn. VIỆN KHOA HỌC KỸ THUẬT BƯU ĐIỆN Trang 25 © 2009 | CCIT/RIPT TRUNG TÂM TƯ VẤN ĐẦU TƯ CHUYỂN GIAO CÔNG NGHỆ CCIT/RIPT 13