Mật mã hiện đại (2)

Mới đây mà đã gần 10 tháng kể từ ngày tôi viết phần 1 của loạt bài này. Tôi bắt đầu phần 2 này cách đây cũng khá lâu, nhưng gặp trở ngại khi viết mã LaTex trên Blogger nên cứ chần chừ rồi quên hẳn. Hồi tháng 4, anh Phan Dương Hiệu có viết một bài rất công phu về hành trình 35 năm của mật mã khóa công khai. Hôm nay ngồi đọc lại bài viết rất hay đó tự dưng tôi thấy… nao nao và quyết định là phải viết tiếp loạt bài này. Phần thứ 2 này tôi sẽ điểm lại lịch sử của mật mã. Bạn nào có cuốn KL thì có thể đọc chương 1 và chương 2. Trong hai phần tiếp theo tôi sẽ giới thiệu mã dòng (stream cipher) và mã khối (block cipher).

—-

II. Lịch sử

We stand today on the brink of a revolution in cryptography.

Whitfield Diffie và Martin Hellman đã viết đầy hứng khởi như thế trong bài báo New Directions in Cryptography công bố năm 1976. Quả đúng như vậy. Trước Diffie-Hellman, mật mã là sân chơi của quân đội, chính phủ và những tập đoàn lớn. Nếu tôi không lầm thì công trình nghiên cứu về mật mã duy nhất được phổ biến rộng rãi là cuốn The Codebreakers xuất bản lần đầu năm 1967 của David Kahn. Bài báo của Diffie-Hellman vừa khai sinh ra mật mã khóa công khai, vừa đánh dấu sự bắt đầu của mật mã hiện đại. Trong vòng vài chục năm, mật mã từ một nghệ thuật đã trở thành một ngành khoa học được giảng dạy và nghiên cứu khắp nơi trên thế giới. Các ứng dụng của mật mã không chỉ còn gói gọn trong ngành công nghiệp quốc phòng mà đã hiện diện trong mọi mặt của đời sống hàng ngày (mời bạn xem thêm bài của anh Hiệu). Mật mã hiện đại cũng là đề tài của loạt bài viết này. Tuy vậy, mật mã là một trong những nghệ thuật cổ xưa nhất của loài người với lịch sử hàng ngàn năm và tôi không thể viết về mật mã mà không giới thiệu sơ qua về lịch sử phát triển của ngành. Dẫu vậy, tôi cũng lưu ý là phần giới thiệu dưới đây chỉ là “cưỡi ngựa xem hoa”, bạn nào muốn tìm hiểu ngọn ngành thì nên đọc cuốn The Codebreakers.

Từ xa xưa, mật mã là nghệ thuật giữ bí mật nhằm giải quyết vấn đề truyền thông tin an toàn giữa người gửi và người nhận. Chẳng hạn như nhà vua cần truyền mệnh lệnh cho tướng ngoài mặt trận. Một cách đơn giản là ông ấy viết mệnh lệnh vào một lá thư, rồi gửi cho người đưa tin và người này sẽ đi từ kinh thành ra mặt trận để trao thư. Với cách làm này, ông vua không có cách nào đảm bảo được rằng chỉ có tướng quân mới xem được thư. Người đưa thư có thể phản bội, trao thư cho kẻ thù, hoặc họ cũng có thể bị kẻ thù bắt trên đường đi từ kinh thành ra mặt trận. Để giải quyết vấn đề này, nhà vua có thể sử dụng mã (cipher). Một mã thường bao gồm 2 hàm:

  • E: lập mã. Hàm này nhận vào một bản rõ (plaintext) m và một khóa (key) k rồi xuất ra một bản mã (ciphertext) c.
  • D: giải mã. Hàm này nhận vào một bản mã c và một khóa k rồi xuất ra một bản rõ m.

Các tài liệu mật mã thường gọi ông vua, tướng quân và kẻ thù trong ví dụ ở trên lần lượt là Alice, Bob và Eve, nên tôi cũng sẽ gọi như thế ở đây. Alice và Bob muốn gửi thông điệp cho nhau và không muốn Eve coi trộm. Để sử dụng được một bộ mã, Alice và Bob phải thống nhất với nhau một khóa k mà Eve không biết. Làm sao Alice và Bob làm được điều đó? Chúng ta sẽ cùng đi tìm câu trả lời khi bàn về mã hóa khóa công khai, còn bây giờ cứ giả sử là bằng cách nào đó Alice và Bob đã có chung một khóa k như thế.

1. Mã thay thế (substitution cipher)

Lập mã – Giải mã

Ý tưởng của mã thay thế rất đơn giản: thay mỗi ký tự trong m bằng một ký tự khác. Quy tắc thay thế chính là khóa k, trong đó mỗi khóa là một hoán vị của bảng chữ cái. Ví dụ:

Khóa:	(A -> H, B -> N, C -> D, D -> X,..., Z -> Y)
Bản rõ:	ABCZ
Bản mã: HNDY

Mã thay thế được sử dụng rộng rãi trong nhiều thế kỷ. Tương truyền rằng Julius Caesar, vị lãnh tụ lừng danh của Đế Chế La Mã, đã sử dụng một loại mã thay thế để bảo vệ tính bí mật của các văn bản quân sự.

Thám mã

Người đầu tiên đưa ra phương pháp phá các mã thay thế là Al-Kindi, một người Ả Rập sống vào thế kỷ thứ 9. Sau khi nghiên cứu kỹ lưỡng cuốn kinh Koran, Al-Kindi đã có một quan sát rất thú vị rằng trong một văn bản đủ dài, mỗi ký tự trong bộ chữ cái Ả Rập sẽ xuất hiện với tần suất tương đương với tần suất mà chúng xuất hiện trong kinh Koran. Nói cách khác, tần suất xuất hiện của các ký tự trong một văn bản là ổn định và điều này đúng không chỉ với tiếng Ả Rập mà còn đúng với tiếng Anh và nhiều ngôn ngữ khác (kể cả tiếng Việt?). Ví dụ như trong tiếng Anh, các ký tự xuất hiện nhiều nhất là “e” (12.7%), “t” (9.1%) và “a” (8.1%). Ngoài ra, tần suất của các bộ hai ký tự (digram) và bộ ba ký tự (trigram) cũng ổn định. Ví dụ như trong tiếng Anh, các bộ hai ký tự xuất hiện nhiều nhất luôn là “th”, “he”, “an” và “in” và bộ ba ký tự phổ biến nhất là “tha”.

Dựa vào quan sát này, Al-Kindi đã đề ra phương pháp thám mã phân tích tần suất (frequency analysis). Ý tưởng là tính tần suất của từng ký tự, từng bộ hai ký tự và từng bộ ba ký tự trong bản mã rồi so sánh các tần suất đó với tần suất chuẩn trong ngôn ngữ của bản rõ. Ví dụ như bản rõ là tiếng Anh và sau khi tính tần suất của các ký tự trong bản mã chúng ta nhận thấy “x” và “m” xuất hiện nhiều nhất thì “x” rất có thể là “e” và “m” có thể là “t”. Bước tiếp theo là thử thay thế “x” bằng “e” và “m” bằng “t” (cũng như các thay thế thích hợp khác) trong bản mã, rồi xem có xác định được từ hoặc cụm từ có nghĩa nào hay không.

Ngoài phương pháp thủ công này, mục 1.3 cuốn KL có mô tả một thuật toán thực hiện thám mã bằng phân tích tần suất hoàn toàn tự động. Lưu ý rằng phân tích tần suất là dạng tấn công chỉ biết bản mã (ciphertext-only attack), nghĩa là chỉ cần nhìn vào bản mã là có thể tìm được khóa và bản rõ. Đây là một tấn công rất yếu nhưng vẫn đủ mạnh để phá mã thay thế.

Bài tập 1: Tính số lượng khóa có thể có của mã thay thế vừa mô tả. Hi vọng con số này sẽ giúp bạn hiểu rằng chiều dài khóa không đảm bảo được sự an toàn của mã và đừng bao giờ xài mã có khóa dài 1 triệu bit :-).

2. Mã Vigenère

Lập mã – Giải mã

Mã Vigenère được phát minh vào khoảng thế kỷ 16. Mục tiêu của mã Vigenère rất rõ ràng: chống thám mã bằng phương pháp phân tích tần suất. Nói cách khác, tần suất của các ký tự trong bản mã phải khác với tần suất của các ký tự trong bản rõ. Để đạt được mục tiêu này, những người phát minh ra mã Vigenère đã có một ý tưởng rất hay: chọn k sao cho |k| = |m| (ký hiệu |x| chỉ chiều dài của x) và mỗi ký tự của m sẽ được mã hóa bằng một ký tự tương ứng của k. Nếu xem mỗi ký tự A-Z tương đương với 0-25 thì lập mã bằng mã Vigenère sẽ là c_i = E(k, m_i) = (m_i + k_i) \text{ mod 26} và giải mã sẽ là m_i = D(k, c_i) = (c_i - k_i) \text{ mod 26}, trong đó m = {m_0}\cdots{m_n} là bản rõ, c = {c_0}\cdots{c_n} là bản mã và k={k_0}\cdots{k_n} là khóa.

Thực tế thì mã Vigenère có khác một chút so với mô tả ở trên của tôi: thay vì dùng một khóa k ngẫu nhiên với |k| = |m|, người ta dùng một khóa ngắn và lập đi lập lại khóa này cho đến khi dài bằng với bản rõ. Ví dụ như với m là “TANCONGNGAY” và k là “KHMT” thì mã hóa bằng mã Vigenère sẽ như sau:

Bản rõ:	TANCONGNGAY
Khóa:	KHMTKHMTKHM
Bản mã: DHZVYUSGQHK

Bài tập 2: Tìm hiểu cách phá mã Vigenère bằng phương pháp phân tích tần suất.

3. Mã máy rôtơ (rotor machines cipher)

Việc phát hiện ra điện năng vào thế kỷ thứ 19 đã dẫn đến sự ra đời của vô vàn máy móc, thiết bị chạy bằng điện và mã máy rôtơ là một trong số đó. Mã máy rôtơ là tên gọi chung của các loại mã mà quá trình lập mã và giải mã được thực hiện bởi các máy rôtơ điện. Mã máy rôtơ nổi tiếng nhất là máy Enigma, được Đức quốc xã sử dụng trong chiến tranh thế giới thứ II. Tôi sẽ không giải thích cơ chế hoạt động của mã máy rô tơ vì chúng ta sẽ không gặp lại mã này. Thay vào đó, chúng ta sẽ cùng điểm lại một chút thành tựu phá mã Enigma của phe Đồng Minh, mà người đóng góp lớn nhất chính là Alan Turing có-tầm-nhìn-thật-ngắn của chúng ta.

Quay lại năm 1940. Lúc này Pháp đã bị quân Hitler chiếm đóng và Anh là quốc gia duy nhất chống lại Phát Xít ở Tây Âu. Khả năng chiến đấu của Anh phụ thuộc vào nguồn hàng viện trợ từ Mỹ và phe Đồng Minh, được chuyển đến đảo quốc bằng những đoàn tàu hộ tống xuyên Bắc Đại Tây Dương. Những đoàn tàu này thường xuyên phải chơi trò “trốn tìm” với đám tàu ngầm U-boat của Hilter, vốn có nhiệm vụ định vị và đánh chìm tất cả những con tàu viện trợ, hòng làm cho Anh kiệt quệ rồi đầu hàng. Ai thắng ai thua trong trò “mèo vờn chuột” này rốt cuộc xoay quanh kết quả của cuộc chiến thông tin: liệu Đức quốc xã có thể định vị tàu hộ tống tốt hơn phe Đồng Minh định vị U-boat hay ngược lại?

Đức thua.

Nhưng lý do chính khiến Đức thất bại chỉ được công bố vào năm 1974: mã của hải quân Đức, chính là một loại mã Enigma, đã bị phá bởi Cục Mật Mã Ba Lan và phương pháp phá mã đã được chuyển đến Anh quốc chỉ vài tuần trước khi Phát Xít xâm lược Ba Lan vào năm 1939. Trong suốt cuộc chiến, quân Đồng Minh luôn định vị được tàu ngầm của Đức rồi hướng các đoàn tàu viện trợ đi vòng qua. Dẫu vậy chính phủ Anh không tiết lộ làm cách nào họ phá được các phiên bản mới của mã Enigma, vốn được điều chỉnh nhiều lần trong suốt cuộc chiến, cho đến tận năm 1996. Thông tin mà chính phủ Mỹ công bố vào năm đó cho thấy ngay khi chiến tranh vừa xảy ra, Alan Turing đã tham gia vào nỗ lực phá mã của Anh quốc ở Bletchley Party, nơi ông trở thành người có đóng góp lớn nhất cho sự phát triển của các kỹ thuật phá mã Engima nhanh và hiệu quả, dựa trên phương pháp của người Ba Lan. Cho đến năm 1945, tất cả các loại mã Enigma của Đức đều có thể bị giải mã trong vòng một hoặc hai ngày. Thành tựu này của Alan Turing và đồng nghiệp được tướng năm sao Dwight D. Eisenhower, chỉ huy tối cao của quân Đồng Minh ở Châu Âu, đánh giá là yếu tố quyết định dẫn đến chiến thắng cuối cùng của quân Đồng Minh.

4. Mã máy tính

Có một chi tiết thú vị mà bây giờ tôi mới nhận ra: giới làm mật mã rất nhạy bén với các phát minh quan trọng của nhân loại. Nếu như thế kỷ 19 họ tạo ra mã máy rôtơ để tận dụng điện năng thì từ giữa thế kỷ 20, họ sáng chế ra các loại mã máy tính để tận dụng… máy tính. Ba loại mã máy tính quan trọng nhất mà chúng ta sẽ tìm hiểu chi tiết trong hai phần tiếp theo là DES, RC4 và AES. Ở đây chúng ta sẽ bàn một chút về lịch sử của DES.

Trong những năm 1970, nhận thấy cần phải có một mã tiêu chuẩn để mã hóa dữ liệu của chính phủ cũng như dùng trong thương mại, Viện Công Nghệ và Tiêu Chuẩn Quốc Gia (NIST) của Mỹ, với sự tư vấn của Cục An Ninh Quốc Gia (NSA), tổ chức một cuộc thi để tìm ra loại mã phù hợp nhất. Cuộc thi lần thứ nhất thất bại thảm hại khi không có mã nào đạt tiêu chuẩn và NIST phải tổ chức thêm một cuộc thi khác vào mùa thu năm 1974. Lần này IBM nộp mã Lucifer, một loại mã được phát triển bởi Horst Fiestel, Don Coppersmith và đồng nghiệp trong thời gian đó. Lucifer là một mã khối, có chiều dài khóa là 128-bit và chiều dài khối là 128-bit, nhưng NSA chỉ chấp nhận Lucifer sau khi thực hiện hai điều chỉnh:

  • NSA muốn giảm chiều dài khóa từ 128-bit xuống còn 48-bit. IBM không đồng ý, họ nghĩ tối thiểu phải là 64-bit. Cuối cùng hai bên đều nhượng bộ và chấp nhận khóa có chiều dài 56-bit.
  • NSA điều chỉnh lại các hộp thay thế (S-box), một thành phần rất quan trọng trong cấu trúc của Lucifer. Lúc bấy giờ nhiều cryptographer tên tuổi, kể cả bộ đôi ma thuật Whitfield Diffie và Martin Hellman đều lên tiếng phản đối sự điều chỉnh này, vì họ ngờ rằng NSA đã cài một “cửa hậu” vào Lucifer, làm giảm đi sự an toàn của Lucifer. Sự thật về những hộp S-box bí ẩn này chỉ được phơi bày khi phương pháp thám mã vi phân được công bố vào những năm 90 của thế kỷ trước. Lúc bấy giờ người ta mới nhận ra rằng, sự điều chỉnh của NSA thật ra đã làm gia tăng sức mạnh của Lucifer, khiến cho mã này không bị phá vỡ dễ dàng bởi thám mã vi phân.

Với hai điều chỉnh này, Lucifer được NIST chuẩn hóa thành DES. DES và phiên bản cải tiến Triple-DES được sử dụng rất rộng rãi. Hạn chế lớn nhất của DES là khóa quá ngắn và hạn chế lớn nhất của Triple-DES là tốc độ thực thi. Năm 1997, NIST lại tổ chức một cuộc thi để tìm một mã thay thế DES và kết quả là Rijndael, một mã của hai cryptographer người Bỉ chiến thắng và sau đó được chuẩn hóa thành AES. Chúng ta sẽ tìm hiểu chi tiết về AES khi nói về mã khối.

III. Khoa học mật mã

Như chúng ta đã thấy, mật mã có lịch sử kéo dài ngàn hàng năm và đã được sử dụng trong nhiều sự kiện quan trọng của nhân loại. Tuy vậy cho đến tận chiến tranh thế giới II, hầu hết các loại mã mà con người tạo ra đều đã bị phá vỡ hoàn toàn, trừ mã One-Time Pad (OTP), được phát minh năm 1917 bởi Gilbert Vernam, một kỹ sư làm việc ở Bell Labs thuộc AT&T. Dẫu vậy, trong nhiều năm liền, không một ai biết OTP thực sự an toàn đến mức nào, cho đến năm 1949, khi công trình Communication Theory of Secrecy Systems của Claude Shannon được công bố rộng rãi. Trong bài báo đó, Claude Shannon đã đặt nền móng cho lý thuyết mật mã hiện đại khi lần đầu tiên đưa ra định nghĩa toán học của khái niệm an toàn và chứng minh được OTP an toàn theo định nghĩa đó.

Để hiểu công trình của Shannon, trước tiên chúng ta cần định nghĩa khái niệm mã.

1. Định nghĩa mã

Một mã xác định trên (K, M, C) là một cặp hai thuật toán “hiệu quả” (E, D) trong đó:

{E}: {K} \times {M} \rightarrow {C},

{D}: {K} \times {C} \rightarrow {M}

thỏa điều kiện \forall{m} \in {M}, \forall{k} \in {K}: {D_k(E_k(m)) = m} (gọi là điều kiện nhất quán). Có hai điểm cần lưu ý:

  • Tôi để chữ “hiệu quả” trong ngoặc kép vì từ này có nghĩa khác nhau với những người khác nhau. Trong định nghĩa này, một thuật toán có thể được xem là “hiệu quả” khi nó có thời gian thực thi và yêu cầu bộ nhớ tương đương với DES.
  • Nếu như D luôn là thuật toán xác định (deterministic algorithm) thì E thường là một thuật toán ngẫu nhiên (randomized algorithm). Nghĩa là E thường sử dụng yếu tố ngẫu nhiên như một phần của thuật toán để đảm bảo rằng khi mã hóa hai lần một bản rõ giống nhau, chúng ta sẽ thu được hai bản mã hoàn toàn khác nhau.

Bài tập 3: Quân ta đang ở chiến trường. Mỗi ngày bộ chỉ huy sẽ gửi ra một lệnh cho biết hôm đó quân ta sẽ làm gì. Chỉ có hai lệnh: “TAN CONG” hoặc “PHONG THU”. Do quân địch cũng có thể nghe lén sóng radio, nên để cho an toàn, bộ chỉ huy sử dụng một mã X để bảo vệ quá trình gửi và nhận lệnh. Mã X này có thuật toán lập mã E hoàn toàn xác định, nghĩa là bản rõ giống nhau sẽ tạo ra bản mã giống nhau. Tất cả các lệnh đều được mã hóa bằng cùng một khóa duy nhất. Chứng minh rằng ngay trong ngày thứ hai, quân địch đã có thể đoán trước chiến thuật của quân ta.

2. One-Time Pad (OTP)

Vernam tạo ra mã OTP khi tìm cách cải tiến mã Vigenère, nên ý tưởng của OTP khá giống với ý tưởng của Vigenère mà tôi mô tả ở trên, cụ thể như sau:

  • {M} = {C} = {K} = \{0, 1\}^{n}. OTP xem bản rõ là một chuỗi bit “0101010101…” và mỗi khóa là một chuỗi bit ngẫu nhiên có chiều dài bằng với bản rõ.
  • Lập mã: {C} := E(k, m) = {k} \oplus {m}. Phép XOR thực chất là phép cộng modulo 2 khi thực hiện trên các chuỗi bit.
  • Giải mã: {D} := D(k, c) = {k} \oplus {c}.

Ví dụ:

Bản rõ:	10110010010
Khóa:	01101010101
Bản mã: 11011000111

Chúng ta có thể dễ dàng kiểm chứng rằng OTP thỏa yêu cầu nhất quán của một mã. Một trong những lợi thế của OTP là tốc độ thực thi rất nhanh, còn bất lợi duy nhất là chiều dài khóa phải bằng chiều dài của bản rõ. Bất lợi này làm cho OTP gần như trở thành vô dụng, bởi vì nếu như Alice và Bob đã có một cách để trao đổi khóa an toàn, thì họ đã có thể dùng ngay cách đó để trao đổi bản rõ luôn. Tuy vậy OTP vẫn được sử dụng trong thực tế và chúng ta sẽ còn gặp lại mã này trong bài sau khi bàn về mã dòng. Như đã nói ở trên, trong nhiều năm liền không ai phá được mã OTP nhưng cũng không ai chứng minh được rằng OTP là an toàn. Nhưng… an toàn là gì? Chúng ta đề cập nhiều đến khái niệm này mà không có một định nghĩa cụ thể. Đây là một thiếu sót rất lớn, bởi lẽ chỉ khi nào chúng ta định nghĩa được khái niệm an toàn của mã thì khi đó mật mã mới có thể trở thành một ngành khoa học.

3. Định nghĩa mã an toàn:

Muốn định nghĩa được mã an toàn, trước tiên chúng ta phải xác định được khả năng của kẻ tấn công Eve, nghĩa là xác định Eve có thể thực hiện được dạng tấn công nào. Có nhiều dạng tấn công và chúng ta sẽ tìm hiểu chi tiết về chúng trong các bài tới. Từ đây đến cuối bài, chúng ta sẽ giả định là kẻ tấn công chỉ thực hiện được dạng tấn công yếu nhất là tấn công biết bản mã (ciphertext-only attack) bằng cách nghe lén (eavesdropping). Quay lại câu hỏi chính, thế nào là một mã an toàn? Sau đây là một vài ý kiến phổ biến:

  1. Mã an toàn là mã mà Eve không thể lấy được khóa.
  2. Mã an toàn là mã mà Eve không thể giải mã toàn bộ bản rõ.
  3. Mã an toàn là mã mà Eve không thể giải mã được bất kỳ bit nào của bản rõ.

Định nghĩa thứ nhất là một ngộ nhận thường gặp khi sử dụng mã. Mục tiêu tối thượng của mã là bảo vệ bản rõ, chứ không phải để bảo vệ khóa (bảo vệ khóa cũng chỉ là để bảo vệ bản rõ). Ví dụ như xét I là mã cơ sở (identity cipher) với E(k, m) = m, nghĩa là I không làm gì cả, nhưng I vẫn an toàn theo định nghĩa thứ nhất vì không có cách nào lấy được khóa.

Định nghĩa thứ hai tốt hơn định nghĩa thứ nhất nhưng rõ ràng vẫn không đạt yêu cầu. Không ai muốn sử dụng một mã X khiến kẻ tấn công giải mã được dầu chỉ một bit thông tin. Vậy định nghĩa thứ ba có đạt yêu cầu hay không? Đây là một định nghĩa tốt, dẫu vậy có nhiều trường hợp kẻ tấn công không thu được bất kỳ bit nào của bản rõ nhưng vẫn tính toán được một thuộc tính nào đó của bản rõ và như thế là đủ để phá hủy tính bí mật của bản rõ, ví dụ như ở trường hợp ở bài tập số 3. Nói cách khác, mã an toàn là mã mà kẻ tấn công không tính được bất kỳ hàm nào của bản rõ. Đây là một định nghĩa rất mạnh và chúng ta sẽ còn trở lại định nghĩa này trong thời gian tới. Trong phần tiếp theo chúng ta sẽ tìm hiểu định nghĩa an toàn theo cách của Claude Shannon.

4. An toàn tuyệt đối (perfect secrecy)

Claude Shannon là cha đẻ của lý thuyết thông tin nên định nghĩa mã an toàn của ông cũng mang “màu sắc” lý thuyết này. Shannon cho rằng một mã là an toàn tuyệt đối nếu như bản mã không tiết lộ bất kỳ “thông tin” nào về bản rõ. Để hiểu ý tưởng của Shannon, chúng ta hãy giả định rằng Eve biết được phân bố xác suất trên M, nghĩa là Eve biết rõ xác suất được gửi ra ngoài của các bản rõ khác nhau. Ví dụ như Eve biết Alice chỉ gửi một trong hai bản rõ m_0 là “TAN CONG” và m_1 là “PHONG THU”. Ngoài ra Eve còn biết xác suất mà Alice gửi m_0 là 0.6 và xác suất gửi m_1 là 0.4. Rồi Eve thấy một bản mã c được gửi từ Alice đến cho Bob. Shannon nói rằng mã mà Alice và Bob sử dụng là an toàn tuyệt đối nếu như việc biết thêm c không làm thay đổi khả năng của Eve. Nói cách khác, c không tiết lộ bất kỳ thông tin gì về bản rõ được gửi đi, bởi vì có biết c hay không thì Eve vẫn chỉ biết xác suất Alice gửi m_0 là 0.6 và m_1 là 0.4.

Để tiện việc chứng minh các bổ đề, chúng ta sẽ không dùng định nghĩa nguyên thủy của Shannon mà sẽ sử dụng một định nghĩa tương đương như sau (xem bổ đề 2.3 cuốn KL):

An toàn tuyệt đối

Một mã (E, D) trên (K, M, C) là an toàn tuyệt đối nếu và chỉ nếu {\forall} {m_0}, {m_1} \in {M} thỏa |{m_0}| = |{m_1}|{\forall} {c} \in {C}, ta có Pr[E(k, m_0) = c] = Pr[E(k, m_1) = c], trong đó k được chọn ngẫu nhiên (uniformly) từ K (ký hiệu là {k} \overset{R}{\leftarrow} {K}).

Chúng ta cần điều kiện |{m_0}| = |{m_1}| vì các mã thường tiết lộ chiều dài của bản rõ. Định nghĩa này có thể hiểu như sau: nếu khóa k được chọn ngẫu nhiên thì xác suất để m_0 mã hóa thành một bản mã c nào đó sẽ bằng với xác suất để m_1 mã hóa thành chính bản mã đó. Nghĩa là nếu chỉ nhìn vào một bản mã thì không có cách nào biết được nguồn gốc của nó. Nói cách khác, việc quan sát được c không giúp cho Eve biết được bản rõ là m_0 hay m_1 hay m_i với i bất kỳ.

Như vậy, định nghĩa của Shannon chỉ ra rằng một mã an toàn tuyệt đối sẽ không thể bị phá bằng tấn công chỉ biết bản mã, bất chấp kẻ tấn công có sức mạnh như thế nào. Đây cũng là một điểm thú vị cho thấy các mã được sử dụng trong các bộ phim Hollywood thường không phải là mã an toàn tuyệt đối, vì nhân vật chính thường giải mã thành công chỉ bằng cách nhìn chằm chằm vào bản mã (ví dụ như John Nash trong phim A Beautiful Mind).

Câu hỏi hiển nhiển bây giờ là: có mã nào là an toàn tuyệt đối hay không? Rất may câu trả lời là có.

4.1 Bổ đề “tin tốt”

OTP là an toàn tuyệt đối.

Chứng minh:

Xét một bản rõ bất kỳ {m} \in {M}. Với mọi bản mã {c} \in {C}, ta có Pr[OTP(k, {m}) = {c}] = Pr[{k} \oplus {m} = {c}] = Pr[{k} = {m} \oplus {c}] = \frac{1}{|K|}. Điều này đúng với \forall{m} \in {M} nên \forall {m_0}, {m_1} \in {M} và {\forall} {c} \in {C}, ta có Pr[E(k, m_0) = c] = Pr[E(k, m_1) = c]. Vậy OTP là an toàn tuyệt đối theo định nghĩa.

Như vậy chúng ta đã tìm được một mã an toàn tuyệt đối, loạt bài này coi như đã “thành công tốt đẹp” rồi. Chưa đâu! Còn nhớ ở trên chúng ta nói OTP có một vấn đề làm cho nó trở nên vô dụng đó là chiều dài khóa lớn hơn hoặc bằng chiều dài bản rõ. Shannon chứng minh rằng không chỉ OTP mà tất cả mã an toàn tuyệt đối đều có tính chất này. Tôi gọi đây là bổ đề “tin xấu” bởi lẽ nó làm tiêu tan hi vọng về một sự an toàn tuyệt đối của tất cả chúng ta :-(.

4.2 Bổ đề “tin xấu”

Một mã là an toàn tuyệt đối phải có |K| \geq |M|. Nói cách khác chiều dài khóa phải lớn hơn hoặc bằng chiều dài bản rõ.

Bài tập 5: chứng minh bổ đề “tin xấu”.

Câu hỏi bây giờ là: có cách nào giải quyết khuyết điểm của OTP hay không? Chúng ta sẽ tìm câu trả lời trong phần kế tiếp khi bàn về mã dòng (đọc KL 61-77).

Chủ đề : Bảo mật và mật mã học, Toán Ứng DụngBookmark the permalink. Trackbacks are closed, but you can post a comment.

20 Comments

  1. vdkhai
    Posted 27/10/2011 at 1:13 pm | Permalink

    Anh Thái có lời giải của các bài tập trong cuốn KL không? Nếu có anh có thể chia sẻ được không ạ, vì sau khi chứng minh xong không biết mình có hiểu đúng chưa và có nhiều bài chưa chứng minh được thì có thể tham khảo 😀

    Cảm ơn anh.

    • Posted 27/10/2011 at 1:20 pm | Permalink

      Tôi không có. Bạn có thể gửi lời giải của bạn lên đây ;-).

      • vdkhai
        Posted 28/10/2011 at 5:07 am | Permalink

        Chào anh Thái,

        Tại sao trong các thí nghiệm (giả định) về tính không thể phân biệt (indistinguishability experiment) lại bắt buộc |m0|=|m1|, vì trong thực tế vẫn tồn tại những hàm f thỏa |f(m0)|=|f(m1)| với mọi m0, m1, |m0|#|m1| (ví dụ các hàm băm) và khi đó vẫn không biết c = f(m0) hay c = f(m1).
        Điển hình là các bài tập 3.3, 3.4 trang 106.

        • homotopie
          Posted 28/10/2011 at 7:08 am | Permalink

          Về mặt định tính, điều này là do : trong bản mã bao giờ cũng chứa các thông tin về bản gốc, do vậy để khôi phục được bản gốc khi nhận được bản mã (và biết khóa) thì phải có một giới hạn nào đó về tương quan độ dài giữa bản mã và bản gốc. Ví dụ, một bản gốc dài 1 triệu octet, mà khi nhận được bản mã chỉ có 1 octet, thì kiểu gì thì kiểu cũng không thể khôi phục được bản gốc, nói cách khác là thông tin đã bị mất đi trong quá trình mã hóa.
          Do vậy để tránh việc người tấn công có thể dựa vào điều này để đoán ra bản rõ thì cần yêu cầu các bản rõ phải có lượng thông tin như nhau (nói một cách gần đúng là chiều dài như nhau). Ví dụ : người tấn công gửi đi 2 bản tin : một bản dài một triệu octet, một bản dài 1 octet. Chỉ cần dựa vào chiều dài bản mã là có thể đoán ra ngay bản gốc tương ứng là gì.
          Trường hợp hàm băm không thuộc định nghĩa trên vì các hàm băm làm mất thông tin của bản rõ (từ mã băm không thể khôi phục lại bản rõ).

        • vdkhai
          Posted 28/10/2011 at 8:08 am | Permalink

          Chào bạn homotopie,

          Ý của bạn là nếu D(E(m))=m thì |E(m)|>=m (tức là lượng thông tin chứa trong bản mã phải >= lượng thông tin chứa trong bản rõ thì mới có thể khôi phục lại được bản rõ – để không mất thông tin). Điều này là tiền đề hay có chứng minh hình thức nào không bạn?

        • Posted 01/11/2011 at 12:13 am | Permalink

          Yêu cầu về chiều dài của bản rõ phải bằng nhau thì trong bài viết tôi cũng đã có giải thích. Lý do đơn giản là hầu hết các hệ mã đều tiết lộ chiều dài của bản rõ. Bài tập 3.3 là để chứng minh điểm này. Còn bài tập 3.4 muốn cho thấyđây chỉ là một giới hạn về mặt kỹ thuật mà thôi; chúng ta vẫn có thể xây dựng được những hệ mã chấp nhận các bản rõ có chiều dài tùy ý.

        • vdkhai
          Posted 02/11/2011 at 10:13 am | Permalink

          Chào anh Thái,

          Xét một hệ mã bất kỳ (G, E, D)
          Nếu cho |m0|=1, 1<=|E(k,m0)|<=p(n) và |m1|=p(n)+1 (n là tham số đầu vào, có thể là chiều dài khóa)
          thì có thể suy ra p(n)+1<=|E(k,m1)|<=p(n)[p(n)+1] được không?

  2. Posted 27/10/2011 at 6:45 pm | Permalink

    Bác Thái,

    “hai ký tự (digram)” hình như phải là *bi*gram.

    Nguyên

  3. homotopie
    Posted 27/10/2011 at 7:24 pm | Permalink

    Em xin giải bài tập 5.
    Gọi các biến ngẫu nhiên đặc trưng cho bản rõ, bản mã, và khóa lần lượt là M, C, K.
    Ta có các tính chất sau :
    I(M,C) = 0 (điều kiện cho sécurité parfaite)
    H(M|C,K) = 0 (điều kiện cần cho việc giải mã – biết khóa và biết bản mã thì suy được bản rõ)
    Ta suy ra :
    H(M,C,K) = H(K,C) + H(M|K,C) = H(K) + H(C) – I(K,C)
    Mặt khác :
    H(M,C,K) = H(M) + H(C|M) + H(K|C,M) = H(M) + H(C) + H(K|C,M)
    Do vậy :
    H(K) = H(M) + I(K,C) + H(K|C,M)
    Tức là : H(K) > H(M), nếu có giả sử là M tuân theo loi uniform, ta suy ra chiều dài khóa phải lớn hơn nhiều dài bản mã.

    • Posted 27/10/2011 at 8:03 pm | Permalink

      I với H là gì vậy bạn?

      • homotopie
        Posted 28/10/2011 at 2:35 am | Permalink

        Mấy cái ký hiệu này hay dùng trong lý thuyết thông tin ạ.
        I(X,Y) là information mutuelle của X và Y.
        H(X) là entropie của X.

  4. tdcuong
    Posted 31/10/2011 at 3:29 pm | Permalink

    Rivest cho rằng machine learning và crypto là 2 ngành anh em với nhau :))

  5. tdcuong
    Posted 31/10/2011 at 3:29 pm | Permalink

    Rivest cho rằng machine learning và crypto là 2 ngành anh em với nhau .

  6. sontran
    Posted 04/05/2012 at 4:29 am | Permalink

    một bức thư mới được declassified của John Nash
    posted in
    class of rivest

  7. Dacky
    Posted 12/06/2013 at 8:45 pm | Permalink

    Mình tìm ko thấy phần 3 nhỉ!?

  8. ngo quy
    Posted 18/07/2014 at 12:32 am | Permalink

    Anh thai co the noi ro cho e cai phan |k| nghia la gi duoc khong a. E la linh moi nen khong biet a thong cam. Trong phan nay co nhieu cai duong nhu chi danh cho nhung nguoi biet het cac ki tu, ki hieu, chinh vi the nen a co the chu thich cac ki tu va ki hieu duoc khong a, e cam on

  9. T.
    Posted 08/01/2017 at 7:04 am | Permalink

    Tôi mới đọc bài này của anh Thái gần đây, và không cho rằng mật mã là yếu tố quyết định dẫn đến chiến thắng phát xít Đức. Ở đây, tôi nghĩ truyền thông Anh và phương Tây hình như đang cố gắng hạ thấp vai trò của Hồng Quân. Máu của người dân Liên Xô mới là nguyên nhân chính dẫn đến thắng lợi !

Post a Comment

Your email is never published nor shared. Required fields are marked *

You may use these HTML tags and attributes <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>

*
*