Câu hỏi: CRY303c - Phần 2: Mật mã cổ điển

Đáp án đúng: "E". Mã thay thế đơn bảng (monoalphabetic cipher) thay mỗi chữ của bản rõ bằng đúng một chữ cố định của bản mã, nên tần suất của từng chữ được giữ nguyên, chỉ bị đổi tên. Trong văn bản tiếng Anh, chữ e là chữ xuất hiện nhiều nhất (khoảng 12–13% số chữ), vì vậy chữ w xuất hiện nhiều nhất trong bản mã của cả một cuốn sách gần như chắc chắn là ảnh của e; đây là nền tảng của thám mã tần suất (frequency analysis). "H" là chữ khá phổ biến nhưng đứng sau e, t, a, o nên không phải ứng viên đầu tiên. "L" chỉ thuộc nhóm tần suất trung bình, thấp hơn e rất nhiều. "O" thuộc nhóm phổ biến cùng t và a nhưng vẫn kém e, nên chỉ là ứng viên thử tiếp khi giả thuyết e không khớp. Văn bản càng dài thì phân bố tần suất càng sát phân bố chuẩn, nên phép đoán w ứng với e càng đáng tin.

Đáp án đúng: "3". Với mã dịch vòng (Caesar) trên bảng 26 chữ cái, dịch k vị trí và dịch k mod 26 vị trí cho cùng kết quả, vì cứ dịch đủ 26 lần là chữ cái quay về chính nó. Tính lại: 26 × 20 = 520, 523 − 520 = 3, nên 523 mod 26 = 3; ngoài ra dịch 3 vị trí sang phải tương đương dịch 26 − 3 = 23 vị trí sang trái, nên số lần dịch tối thiểu là 3. Phương án "5" ứng với khoá 525 (525 − 520 = 5), không phải 523. Phương án "7" ứng với khoá 527 (527 − 520 = 7). Phương án "9" ứng với khoá 529 (529 − 520 = 9). Bài học chính là khoá lớn hơn 26 không làm mã dịch vòng mạnh hơn: không gian khoá thật sự chỉ có 26 giá trị, nên vét cạn rất dễ.

Đáp án đúng gồm hai ý: "G" và "R". Mã Vigenère với khoá hai ký tự dùng xen kẽ hai phép dịch Caesar: chữ ở vị trí lẻ dịch theo ký tự khoá thứ nhất, chữ ở vị trí chẵn dịch theo ký tự khoá thứ hai, nên chữ e phổ biến nhất của bản rõ bị mã thành hai chữ bản mã khác nhau tuỳ vị trí chẵn lẻ, mỗi chữ gánh khoảng nửa số lần xuất hiện của e. Vì vậy hai chữ đứng đầu bảng tần suất bản mã, "R" rồi "G", là ứng viên cho e. Cần nói thẳng: dữ kiện khoá XO không khớp chính xác với bảng tần suất, vì X = 23 biến e = 4 thành (4 + 23) mod 26 = 1, tức chữ b, còn O = 14 biến e thành (4 + 14) mod 26 = 18, tức chữ s; câu này chỉ giải được bằng lập luận tần suất, và theo lập luận đó hai chữ nhiều nhất là đáp án. "Z" đứng thứ ba, hợp làm ảnh của một chữ phổ biến khác như t hay a. "Y" đứng thứ 18, là chữ hiếm trong bản mã. "E" và "T" là chữ bản rõ phổ biến, còn trong bảng bản mã chúng chỉ đứng thứ 11 và 16.

Đáp án đúng: "720". Mật mã hoán vị (Permutation Cipher) với khoá độ dài 6 chia bản rõ thành từng khối 6 ký tự rồi sắp lại vị trí theo khoá; khoá là một hoán vị của sáu vị trí, chẳng hạn [3 2 6 1 4 5], nên mỗi số từ 1 đến 6 xuất hiện đúng một lần. Số hoán vị của 6 phần tử là 6! = 1 × 2 × 3 × 4 × 5 × 6 = 720: vị trí đầu có 6 cách chọn, vị trí thứ hai còn 5, rồi 4, 3, 2, 1. "460" không phải giai thừa của số nào và không ứng với cách đếm nào. "1080" lớn hơn 6! nên đã đếm thừa các dãy có số lặp lại, vốn không phải hoán vị hợp lệ. "2048" là 2^11, kiểu đếm số khoá nhị phân 11 bit, không áp dụng cho khoá là hoán vị. Không gian 720 khoá nhỏ đến mức vét cạn tức thời, nên mật mã hoán vị đứng một mình không an toàn.

Đáp án đúng: "This cipher transforms a plaintext alphabet to distinct ciphertext alphabets with long enough plaintext inputs". Câu hỏi tìm phát biểu SAI. Khoá Vigenère dài 1 nghĩa là mọi chữ đều dịch cùng một lượng 24, nên chỉ có một bảng chữ bản mã duy nhất: đây là mã đơn bảng, bản rõ dài bao nhiêu thì mỗi chữ vẫn chỉ ứng với một chữ cố định và tần suất không bị san phẳng; nói nó tạo ra nhiều bảng chữ bản mã khác nhau (đặc trưng của mã đa bảng) là sai. Các phát biểu kia đều đúng nên không được chọn: "c = (p+24) mod 26" là định nghĩa trực tiếp với Y = 24; "c = (p-2) mod 26" tương đương vì 24 ≡ −2 (mod 26), ví dụ p = 0 (chữ a) cho (0 + 24) mod 26 = 24 và (0 − 2) mod 26 = 24, đều là chữ y; khoá YYY lặp lại cùng phép dịch 24 ở mọi vị trí nên "equivalent to the Vigenère cipher using a key of length 3" đúng; và một phép dịch cố định chính là "The cipher is equivalent to a Caesar Cipher".

Đáp án đúng: "20". Mã hoán vị (Permutation Cipher, một dạng mã chuyển vị) chia bản rõ thành từng khối 5 ký tự rồi sắp xếp lại vị trí các ký tự trong khối theo khoá [5 3 2 1 4]; nó chỉ đổi chỗ chứ không thay ký tự này bằng ký tự khác. Vì thế mỗi chữ E trong bản rõ vẫn là một chữ E trong bản mã, chỉ nằm ở vị trí khác, nên 20 chữ E vào thì 20 chữ E ra; đây cũng là lý do phân tích tần suất lộ ngay mã chuyển vị, vì phân bố chữ cái giống hệt ngôn ngữ gốc. Phương án "0" sai vì không có bước thay thế nào xoá chữ E. Phương án "1" sai vì hoán vị không gộp các chữ trùng lại. Phương án "Depends on the plaintext" sai vì số lần xuất hiện được bảo toàn với mọi bản rõ, không phụ thuộc nội dung.

Đáp án đúng: "True". Mã dùng một lần (one-time pad) dùng một khoá ngẫu nhiên thật, dài ít nhất bằng thông điệp, XOR với bản rõ để mã hoá; người nhận giữ đúng bản khoá ấy và XOR lại để giải mã. Khoá chỉ được dùng một lần rồi huỷ. Shannon chứng minh hệ này đạt bí mật hoàn hảo: với mỗi bản mã, mọi bản rõ cùng độ dài đều có khả năng như nhau, nên kẻ tấn công không học được gì kể cả có sức tính vô hạn. Điều kiện bắt buộc là khoá ngẫu nhiên thật và không bao giờ dùng lại; dùng lại khoá thì XOR hai bản mã sẽ khử khoá và lộ XOR hai bản rõ. Phát biểu mô tả đúng khoá ngẫu nhiên, riêng tư, dùng một lần và người nhận giải mã bằng bản khoá khớp, nên "False" bị loại.

Đáp án đúng: "False". One-time pad (sổ dùng một lần) đạt bí mật hoàn hảo (perfect secrecy) theo Shannon: bản mã c = p ⊕ k không tiết lộ gì về bản rõ, với điều kiện khoá ngẫu nhiên thật, dài ít nhất bằng thông điệp và không bao giờ dùng lại. Chính các điều kiện này làm nó không thực tế để dùng phổ biến: mã hoá 1 GB dữ liệu phải có 1 GB khoá ngẫu nhiên thật, phải chuyển khoá đó tới bên kia qua một kênh an toàn từ trước (nếu có kênh như vậy thì gửi luôn dữ liệu), rồi lưu trữ và huỷ khoá sau một lần dùng; dùng lại khoá hai lần thì c1 ⊕ c2 = p1 ⊕ p2 và bí mật sụp đổ. Vì thế hệ thống thực tế dùng mã khối như AES hay mã dòng với khoá ngắn, còn one-time pad chỉ dùng ở vài kênh rất đặc thù. Phát biểu "True" sai vì nhầm an toàn lý thuyết với tính phổ biến trong thực tế.

Đáp án đúng: "False". Phát biểu gán mỗi chữ cái bản rõ với đúng một chữ cái bản mã cố định duy nhất, đó là mô tả của mã đơn bảng (monoalphabetic cipher): chữ E lúc nào cũng thành cùng một chữ, nên phân tích tần suất phá được dễ dàng. Mã đa bảng (polyalphabetic cipher) như Vigenère dùng nhiều bảng thay thế luân phiên theo vị trí hay theo khoá, nên cùng một chữ cái bản rõ có thể thành nhiều chữ cái bản mã khác nhau; ví dụ với khoá XO, chữ A ở vị trí lẻ dịch 23 thành X, còn ở vị trí chẵn dịch 14 thành O. Nhờ đó phân bố tần suất của bản mã bị làm phẳng, khó phá hơn mã đơn bảng. Vì mệnh đề mô tả ánh xạ cố định một đổi một, nó sai với mã đa bảng, nên "True" bị loại.

Đáp án đúng: "E". Trong mã thay thế đơn bảng (monoalphabetic cipher), mỗi chữ bản rõ luôn được thay bằng cùng một chữ bản mã, nên chữ nào phổ biến trong bản rõ thì ảnh của nó phổ biến đúng bằng chừng ấy trong bản mã. Chữ e là chữ thường gặp nhất trong tiếng Anh (khoảng 12–13% số chữ), vì vậy chữ a xuất hiện nhiều nhất trong bản mã một cuốn sách dài nên được đoán là ảnh của e; người thám mã đặt giả thuyết này trước rồi kiểm bằng các chữ ghép phổ biến như the. "H" phổ biến vừa phải, đứng sau e, t, a, o. "L" chỉ ở nhóm trung bình, tần suất chưa bằng một phần ba của e. "O" là chữ phổ biến nhưng vẫn kém e, chỉ là giả thuyết thử tiếp nếu e không khớp.

Đáp án đúng: "False". Bí mật hoàn hảo của one-time pad đòi khoá ngẫu nhiên thật, dài bằng thông điệp và mọi chuỗi khoá có xác suất như nhau. Ở đây khoá 1 KB được sinh tất định từ hạt giống (seed) chỉ 1 byte, nên dù dài 1 KB nó chỉ có thể là một trong 2^8 = 256 chuỗi khác nhau, thay vì 2^8192 chuỗi (1 KB = 1024 byte = 8192 bit) mà bí mật hoàn hảo cần. Entropy thật của khoá chỉ là 8 bit: kẻ tấn công thử 256 hạt giống là tìm ra khoá. Việc giữ kín thuật toán sinh khoá vi phạm nguyên lý Kerckhoffs, vì an toàn không được dựa vào sự bí mật của thuật toán. Việc vượt qua bộ kiểm tra ngẫu nhiên của NIST chỉ cho thấy đầu ra trông ngẫu nhiên về thống kê, không làm tăng entropy. Đây là một mã dòng giả ngẫu nhiên rất yếu, không phải one-time pad thật, nên chọn "True" là sai.

Đáp án đúng: "120". Mật mã hoán vị với khoá độ dài 5 sắp lại vị trí năm ký tự trong mỗi khối theo một hoán vị như [3 2 1 4 5], trong đó mỗi số từ 1 đến 5 dùng đúng một lần. Số khoá là số hoán vị của 5 phần tử: 5! = 5 × 4 × 3 × 2 × 1 = 120, vì vị trí đầu có 5 cách chọn, vị trí thứ hai còn 4, rồi 3, 2 và 1. "5" chỉ là độ dài khoá, giống như chỉ đếm các phép dịch vòng chứ không phải mọi cách sắp xếp. "24" là 4! = 24, quên mất một vị trí. "32" là 2^5, cách đếm khoá nhị phân 5 bit, không áp dụng cho khoá là hoán vị. Với 120 khoá, kẻ tấn công vét cạn trong chớp mắt, nên hoán vị chỉ có ích khi kết hợp với phép thế trong mật mã tích.

Đáp án đúng: "AFXULB". Mã Vigenère cộng từng chữ cái bản rõ với chữ cái khoá lặp lại, theo modulo 26 với A = 0. Khoá XO cho các độ dịch 23, 14 luân phiên. Tính lại: D(3) + 23 = 26 mod 26 = 0 ra chữ A; R(17) + 14 = 31 mod 26 = 5 ra F; A(0) + 23 = 23 ra X; G(6) + 14 = 20 ra U; O(14) + 23 = 37 mod 26 = 11 ra L; N(13) + 14 = 27 mod 26 = 1 ra B, được AFXULB. "RFOUCB" là kết quả khi dịch mọi chữ 14 vị trí, tức dùng khoá chỉ có chữ O, nên đúng ở vị trí chẵn nhưng sai ở vị trí lẻ, ví dụ chữ đầu ra R thay vì chữ A. "AOXDLK" là khi dịch mọi chữ 23 vị trí, tức khoá chỉ có chữ X, nên đúng vị trí lẻ nhưng sai vị trí chẵn. "ROODCK" là khi dùng khoá đảo thứ tự thành OX, nên sai ở mọi vị trí.

Đáp án đúng: "False". Mã dùng một lần đạt bí mật hoàn hảo chỉ khi khoá ngẫu nhiên thật, dài bằng thông điệp và mỗi khoá có xác suất như nhau. Ở đây 1KB = 1024 × 8 = 8192 bit nên cần 2^8192 khoá đều nhau, nhưng khoá lại do một thuật toán tất định sinh ra từ hạt giống dài 18; thuật toán tất định thì hạt giống quyết định hoàn toàn khoá, nên số khoá có thể xuất hiện không vượt số hạt giống, chẳng hạn chỉ 2^18 nếu hạt dài 18 bit, và kẻ tấn công có thể vét cạn hạt giống. Đó là bộ sinh số giả ngẫu nhiên, tức một mã dòng, không phải mã dùng một lần. Giữ kín thuật toán là an ninh nhờ che giấu, trái nguyên lý Kerckhoffs, và qua được bài kiểm tra giả ngẫu nhiên của NIST chỉ cho thấy đầu ra trông ngẫu nhiên, không biến nó thành ngẫu nhiên thật. Vì vậy "True" bị loại.

Đáp án đúng: "True". Claude Shannon chứng minh one-time pad đạt bảo mật hoàn hảo (perfect secrecy): bản mã không tiết lộ bất cứ thông tin nào về bản rõ, tức xác suất của mỗi bản rõ khi đã thấy bản mã bằng đúng xác suất ban đầu. Điều kiện là khoá thật sự ngẫu nhiên, dài ít nhất bằng thông điệp và chỉ dùng một lần; khi đó với mỗi bản mã, mọi bản rõ cùng độ dài đều có đúng một khoá biến nó thành bản mã ấy, nên vét cạn vô ích. Dùng lại khoá hai lần thì XOR hai bản mã khử mất khoá và bảo mật sụp đổ. "False" sai vì đây là kết quả đã được chứng minh, không phải giả thuyết.

Đáp án đúng: "3". Mã dịch vòng trên 26 chữ cái chỉ phụ thuộc k mod 26, và số lần dịch tối thiểu là phần dư đó hoặc 26 trừ đi phần dư, lấy số nhỏ hơn. Cần nói thẳng chỗ tranh cãi: với đúng con số in là 532 thì 26 × 20 = 520, 532 − 520 = 12, và 26 − 12 = 14 lớn hơn, nên số lần dịch tối thiểu là 12, không phương án nào khớp. Cùng câu hỏi gốc dùng khoá 523, và 523 − 520 = 3; bốn phương án cũng khớp đúng dãy 523, 525, 527, 529 mod 26, nên khoá ở đây nhiều khả năng bị in đảo hai chữ số cuối của 523, và đáp án được chốt là 3. "5" ứng với khoá 525 (525 − 520 = 5). "7" ứng với khoá 527 (527 − 520 = 7). "9" ứng với khoá 529 (529 − 520 = 9). Không cái nào ứng với 523.

Đáp án đúng gồm ba ý: "If we replace the Caesar Cipher with a Monalphabetic Cipher, then A is harder to crack by an attacker (who does not know the key).", "The ordering between the Caesar and the Permutation does not matter within the product cipher, so we can decrypt in any order." và "Letter Z appeared the most in the ciphertext, so it must be mapped from the latter E.". Caesar thay từng chữ theo một phép dịch, hoán vị độ dài 5 chỉ đổi chỗ chữ trong mỗi khối 5, nên hai phép giao hoán: dịch rồi đổi chỗ hay đổi chỗ rồi dịch đều cho cùng bản mã, giải theo thứ tự nào cũng được. Hoán vị không đổi số lần xuất hiện của từng chữ và Caesar chỉ đổi tên chữ, nên tần suất đơn chữ được giữ: trong một cuốn sách tiếng Anh dài, chữ nhiều nhất trong bản mã ứng với e. Thay Caesar (26 khoá) bằng thế đơn bảng (26! ≈ 4 × 10^26 khoá) làm hệ mã tích khó phá hơn hẳn. Ngược lại, "The letter-pair/ digram AX appeared the most in the ciphertext" sai vì hoán vị xé các cặp chữ liền nhau, tần suất cặp như th không còn giữ. Còn "If we another Caesar Cipher encryption in the product cipher" không tăng an toàn vì dịch k1 rồi k2 chỉ là một phép dịch (k1 + k2) mod 26, không gian khoá vẫn là 26.

Đáp án đúng gồm hai ý: "V" và "F". Vigenère với khoá hai chữ dùng xen kẽ hai bảng Caesar: chữ ở vị trí lẻ dịch theo chữ khoá thứ nhất, chữ ở vị trí chẵn dịch theo chữ khoá thứ hai. Trong mỗi nửa văn bản, e vẫn là chữ nhiều nhất, nên e bị biến thành đúng hai chữ bản mã khác nhau, mỗi chữ chiếm khoảng một nửa số lần xuất hiện của e, và hai chữ đó phải đứng đầu bảng tần suất. Bảng đã sắp giảm dần mở đầu bằng hai chữ này nên chọn chúng. Cần nói thẳng: bảng in có chữ lặp (năm chữ xuất hiện hai lần) và khoá XO không khớp chính xác, vì X dịch 23 và O dịch 14 sẽ biến e (vị trí 4) thành (4 + 23) mod 26 = 1 là b, và (4 + 14) mod 26 = 18 là s; do đó câu chỉ giải được bằng lập luận tần suất. "E" sai vì e chỉ giữ nguyên khi chữ khoá là a (dịch 0), và trong bảng nó chỉ đứng thứ 19. "Y" không có mặt trong bảng tần suất. "R" chỉ đứng giữa bảng, ở vị trí thứ 12, không phải chữ nhiều nhất.

Đáp án đúng: "676". Khoá Vigenère dài cố định 2 ký tự, mỗi ký tự là một trong 26 chữ cái tiếng Anh và được chọn độc lập, nên theo quy tắc nhân số khoá khác nhau là 26 × 26 = 26^2 = 676 (từ AA tới ZZ, trong đó XO chỉ là một khoá). Với khoá dài k thì số khoá là 26^k, tăng theo cấp số mũ. "26" là số khoá khi khoá dài 1, tương đương mã Caesar. "52" = 26 × 2, cộng số lựa chọn của hai vị trí thay vì nhân. "1352" = 676 × 2, nhân đôi không có cơ sở, như thể đếm thêm một biến thể cho mỗi khoá.

Đáp án đúng: "26". Bản mã QNGWFWD thuộc mật mã Caesar (mã dịch), chỉ có 26 khoá dịch từ 0 đến 25. Quên khoá thì phải vét cạn: thử dịch ngược bản mã theo từng khoá rồi xem kết quả nào thành từ có nghĩa. Trong trường hợp xấu nhất, khoá đúng là khoá thử sau cùng, nên phải giải mã đủ 26 lần (nếu bỏ khoá 0 vì giữ nguyên bản rõ thì còn 25 lần, vẫn gần nhất với 26). "1" là trường hợp may mắn nhất, trúng ngay lần đầu. "13" là số lần thử trung bình 26 / 2, không phải trường hợp xấu nhất. "52" gấp đôi số khoá, có thể do tính riêng chữ hoa và chữ thường, nhưng Caesar trên bảng 26 chữ cái chỉ có 26 phép dịch. Không gian khoá nhỏ như vậy là lý do Caesar bị phá tức thời bằng vét cạn.