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

TT CNTT HN Wednesday, April 25, 2012 CCIT/RIPT 1 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Ệ TS. Phạm Việt Hà MẬT MÃ HÓA HIỆN ĐẠI Chương 1: Tổng quan về mật mã hóa hiện đại Trang 2 © 2009 | CCIT/RIPT 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ược về mật mã 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 TT CNTT HN Wednesday, April 25, 2012 CCIT/RIPT 2 Trang 3 © 2009 | CCIT/RIPT 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ược về mật mã học  Ví dụ: + Bản rõ x: HELLOWORLD + Hàm Ek(x) = x + k mod 26 Cho k = 5  Khi đó: bản mã 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ản rõ x từ bản mã y từ hàm giải mã: dk(y) = y – k mod 26 Trang 4 © 2009 | CCIT/RIPT 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ược về mật mã 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 TT CNTT HN Wednesday, April 25, 2012 CCIT/RIPT 3 Trang 5 © 2009 | CCIT/RIPT 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ược về mật mã 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. Trang 6 © 2009 | CCIT/RIPT 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.2. Một số khái niệm cơ 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. TT CNTT HN Wednesday, April 25, 2012 CCIT/RIPT 4 Trang 7 © 2009 | CCIT/RIPT 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.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 Bản mã Từ mã được truyền Nguồn tin tương tự Đầu vào rõ Bản mã Bản rõ Biến đổi A/D (tương tự – số) Mã nguồn Mã bảo mật Mã kênh Kênh truyền (tạp âm, đa đường, giao thoa, nhiễu, nghe trộm ) Nhận tin Đầu ra số Bản rõ Biến đổi D/A (số - tương tự) Giải mã nguồn Giải mã mật Giải mã kênh Trang 8 © 2009 | CCIT/RIPT 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.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. TT CNTT HN Wednesday, April 25, 2012 CCIT/RIPT 5 Trang 9 © 2009 | CCIT/RIPT 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.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”. Trang 10 © 2009 | CCIT/RIPT 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.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: TT CNTT HN Wednesday, April 25, 2012 CCIT/RIPT 6 Trang 11 © 2009 | CCIT/RIPT 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.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. Trang 12 © 2009 | CCIT/RIPT 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.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ì: TT CNTT HN Wednesday, April 25, 2012 CCIT/RIPT 7 Trang 13 © 2009 | CCIT/RIPT 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.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: Trang 14 © 2009 | CCIT/RIPT 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.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: TT CNTT HN Wednesday, April 25, 2012 CCIT/RIPT 8 Trang 15 © 2009 | CCIT/RIPT 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.4. Hệ mật hoàn thiện Định nghĩa 2: 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ất như 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ất củ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. Trang 16 © 2009 | CCIT/RIPT 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.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). TT CNTT HN Wednesday, April 25, 2012 CCIT/RIPT 9 Trang 17 © 2009 | CCIT/RIPT 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.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. Trang 18 © 2009 | CCIT/RIPT 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Ệ • Trước tiên nhắc lại một số kiến thức – f lồi trên khoảng I: – f lồi thực sự trên I nếu: – ĐL 5 (Bất đẳng thức Jensen) Giả sử f là một hàm lồi thực sự 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 . 1.6. Các tính chất của Entropy TT CNTT HN Wednesday, April 25, 2012 CCIT/RIPT 10 Trang 19 © 2009 | CCIT/RIPT 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Ệ • Các tính chất: – Giả sử X là một biến ngẫ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ức xảy ra khi và chỉ khi X và Y là các biến cố độc lập. 1.6. Các tính chất của Entropy Trang 20 © 2009 | CCIT/RIPT 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Ệ X và Y là hai bnn, khi đó với giá trị xác định bất kì y của Y, ta có một phân bố xs có đk p(X|y). Rõ ràng là: – Ta định nghĩa entropy có điều kiệ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 độc lập 1.6. Các tính chất của Entropy TT CNTT HN Wednesday, April 25, 2012 CCIT/RIPT 11 Trang 21 © 2009 | CCIT/RIPT 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Ệ Trong phần này ta sẽ áp dụng các kết quả về entropy ở trên cho các hệ mật  Trước hết ta 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ột hệ 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ả 1.6. Các khóa giả và khoảng duy nhất Trang 22 © 2009 | CCIT/RIPT 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Ệ 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õ x1x2xn sẽ được mã hóa bằng một khóa tạo ra xâu bản mã y1y2yn. 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õ. 1.6. Các khóa giả và khoảng duy nhất TT CNTT HN Wednesday, April 25, 2012 CCIT/RIPT 12 Trang 23 © 2009 | CCIT/RIPT 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Ệ (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õ 1.6. Các khóa giả và khoảng duy nhất Trang 24 © 2009 | CCIT/RIPT 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Ệ  Định nghĩa: Giả sử L là một ngôn ngữ tự nhiên, entropy của L được xác định là lượng sau:  Độ dư của L là:  Nhận xét:  HL đo entropy trên mỗi kí tự của ngôn ngữ L  RL đo phần “kí tự vượt trội” là phần dư vì entropy của một ngôn ngữ ngẫu nhiên là log2|P |.  Dựa vào giá trị của HL ta có thể đánh giá được lượng thông tin trung bình của một ngôn ngữ, ví dụ với L là Anh ngữ thì 1.0 ≤ HL ≤ 1.5. Giả sử lấy HL = 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 được một đơn ánh cho các bộ n (n đủ lớn) mà nén văn bản tiếng Anh xuống còn 1/4 văn bản gốc 1.6. Các khóa giả TT CNTT HN Wednesday, April 25, 2012 CCIT/RIPT 13 Trang 25 © 2009 | CCIT/RIPT 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Ệ  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. 1.6. Khoảng duy nhất