Giải thích phân tích tần suất

Suốt nhiều thế kỷ, cách tốt nhất để giấu một thông điệp là thay mỗi chữ cái trong bảng chữ cái bằng một chữ khác. Số khóa khả dĩ lớn đến mức thiên văn, nên mật mã trông như không thể phá. Thế nhưng một học giả ở Baghdad vào thế kỷ thứ chín đã tìm ra điểm yếu của nó: một ngôn ngữ dùng một số chữ cái thường xuyên hơn hẳn những chữ khác, và hoán đổi bao nhiêu cũng không giấu được điều đó. Phân tích tần suất đã biến việc phá mã từ chuyện đoán mò thành một phương pháp, và đến nay nó vẫn là điều đầu tiên mà bất kỳ ai cũng thử với một mật mã mới.

Biểu đồ cột các chữ cái mã từ phổ biến nhất đến ít phổ biến nhất, đối chiếu với tần suất của tiếng Anh, phía trên một bản mã mà những chữ cái đầu tiên đã được giải
Biểu đồ cột các chữ cái mã từ phổ biến nhất đến ít phổ biến nhất, đối chiếu với tần suất của tiếng Anh, phía trên một bản mã mà những chữ cái đầu tiên đã được giải

Mật mã thay thế

Một mật mã thay thế đơn giản thay mỗi chữ cái trong bảng chữ cái bằng một chữ khác theo một bảng cố định: chẳng hạn A thành Q, B thành W, và cứ thế, mỗi chữ cái được dùng một lần. Bảng đó chính là khóa. Khác với mật mã Caesar, vốn chỉ dịch bảng chữ cái và có 25 khóa, mật mã thay thế có thể dùng bất kỳ thứ tự nào của các chữ cái: 26! khóa, khoảng 4 × 10²⁶. Ngay cả một máy tính thử một tỷ khóa mỗi giây cũng sẽ cần hơn mười tỷ năm để thử hết.

Phát hiện của al-Kindi

Khoảng năm 850, nhà triết học Ả Rập Abu Yusuf al-Kindi đã viết một chuyên luận về việc giải mã các thông điệp bí mật, bản mô tả cổ nhất được biết đến về phân tích tần suất. Lời khuyên của ông là lấy một văn bản dài trong cùng ngôn ngữ, đếm xem mỗi chữ cái xuất hiện bao nhiêu lần, rồi đếm các chữ cái của thông điệp bí mật và ghép chúng với nhau: chữ thường gặp nhất với chữ thường gặp nhất, chữ kế tiếp với chữ kế tiếp. Các học giả nghiên cứu kinh Qur'an đã đếm chữ cái và từ ngữ qua nhiều thế hệ, và có lẽ ý tưởng này nảy sinh từ đó.

Chữ cái, cặp chữ và từ

Trong tiếng Anh, khoảng 12,7% chữ cái là E, 9% là T và 8% là A, còn Z chỉ xuất hiện một lần trong hơn một nghìn chữ cái. Số đếm của từng chữ chỉ cho biết hướng đúng, nhất là với văn bản ngắn, nên người phá mã tận dụng mọi mẫu hình họ tìm được. Từ một chữ cái là A hoặc I. Các cặp chữ phổ biến nhất là TH, HE, IN và ER, và các chữ cái đôi phổ biến nhất là LL, EE, SS và OO. Sau Q hầu như luôn là U. Một từ ba chữ cái hay gặp nhiều khả năng là THE, và khi đã biết T, H và E, những từ như THAT và THERE sẽ tự hiện ra. Mỗi ngôn ngữ có dấu vân tay riêng: E còn chiếm ưu thế hơn nữa trong tiếng Đức và tiếng Hà Lan, còn trong tiếng Bồ Đào Nha thì A dẫn đầu.

Mật mã chết người của một nữ hoàng

Năm 1586, Mary, Nữ hoàng Scotland, khi đang bị giam ở Anh, đã trao đổi thư mã hóa với Anthony Babington, người đang âm mưu giải thoát bà và giết Nữ hoàng Elizabeth I. Những bức thư được tuồn ra ngoài trong các thùng bia, nhưng chúng đã đi qua tay trùm mật vụ của Elizabeth là Francis Walsingham, người có chuyên gia phá mã Thomas Phelippes đã phá được mật mã, một phép thay thế có thêm vài ký hiệu cho các từ thông dụng, bằng phân tích tần suất. Những bức thư đã giải mã chứng minh vai trò của Mary trong âm mưu, và bà bị xử tử vào tháng 2 năm 1587.

Che giấu tần suất

Những người tạo mật mã đã chống trả. Mật mã đồng âm cho mỗi chữ cái phổ biến nhiều ký hiệu, để mọi ký hiệu xuất hiện với tần suất gần như nhau. Các ký hiệu rỗng, vô nghĩa, được rải khắp văn bản để làm rối việc đếm. Câu trả lời thực sự đến cùng các mật mã đa bảng như mật mã Vigenère của thế kỷ 16, vốn chuyển đổi giữa nhiều bảng chữ cái trong quá trình mã hóa, khiến một chữ cái gốc trở thành nhiều chữ cái mã khác nhau. Nó đứng vững cho đến khi Charles Babbage và Friedrich Kasiski chỉ ra vào thế kỷ 19 cách tìm độ dài của khóa rồi áp dụng phân tích tần suất cho từng bảng chữ cái riêng biệt.

Máy tính giải cryptogram thế nào

Một chương trình cũng không thể thử mọi khóa, nhưng nó có thể leo. Nó bắt đầu từ một phỏng đoán, chấm điểm kết quả theo mức độ giống ngôn ngữ, thường là theo mức phổ biến của các nhóm từ hai đến bốn chữ cái, rồi hoán đổi các cặp chữ trong khóa, giữ lại mỗi phép hoán đổi làm tăng điểm. Khi không phép hoán đổi nào giúp được nữa, nó xáo khóa và bắt đầu leo lại, luôn giữ kết quả tốt nhất. Phương pháp này, gọi là leo đồi (hill climbing), giải một mật mã thay thế vài trăm chữ cái trong một phần nhỏ của giây, và các biến thể của nó đã phá được những mật mã lịch sử từng làm khó con người suốt nhiều thế kỷ.

Phân tích tần suất ngày nay

Các mật mã hiện đại như AES được thiết kế để bản mã trông hoàn toàn ngẫu nhiên: mọi giá trị byte xuất hiện thường xuyên như nhau, và cùng một thông điệp được mã hóa khác đi mỗi lần. Phân tích tần suất không có chỗ bám vào chúng. Dù vậy, ý tưởng ấy vẫn sống tiếp: thống kê ngôn ngữ giúp nhận ra khi nào một bản giải mã là đúng, phá mật mã trong các câu đố và trò chơi phòng thoát hiểm, và đọc những bức thư mã hóa cũ tìm thấy trong các kho lưu trữ. Năm 2023, những bức thư của Mary, Nữ hoàng Scotland, đã thất lạc suốt nhiều thế kỷ được giải mã nhờ sự trợ giúp của máy tính.

Tự khám phá

Hãy mở công cụ phân tích tần suất để có một đoạn văn đã mã hóa bằng tiếng Anh, tiếng Đức, tiếng Pháp, tiếng Tây Ban Nha, tiếng Ý, tiếng Bồ Đào Nha hoặc tiếng Hà Lan. So sánh số lần xuất hiện của chữ cái với ngôn ngữ trên biểu đồ, dùng các manh mối về cặp chữ, chữ cái đôi và từ ngắn, rồi điền khóa từng chữ một. Gợi ý và Kiểm tra giúp bạn khi bị bí, còn trình giải cho thấy cách leo đồi làm nốt phần việc.

Câu hỏi thường gặp

Vì sao E là chữ cái phổ biến nhất trong tiếng Anh?

Vì nó xuất hiện trong nhiều từ thông dụng nhất, như THE, BE, HE, WE và ARE, và trong các đuôi từ phổ biến như -ED và -ES. Hầu hết các ngôn ngữ châu Âu đều có chung đặc điểm này: E cũng dẫn đầu trong tiếng Pháp, tiếng Đức, tiếng Hà Lan và tiếng Tây Ban Nha.

Phân tích tần suất có phá được mọi mật mã không?

Không. Nó phá được những mật mã trong đó mỗi chữ cái gốc luôn được thay bằng cùng một ký hiệu. Những mật mã thay đổi phép thay thế trong quá trình mã hóa, hoặc các mật mã hiện đại làm việc trên bit thay vì chữ cái, cần những phương pháp khác hoặc hoàn toàn không thể phá.

Câu đố cryptogram là gì?

Một câu trích dẫn hoặc một câu văn được mã hóa bằng phép thay thế đơn giản, in ra để người đọc giải bằng tay. Cryptogram đã xuất hiện trên báo chí từ thế kỷ 19 và được giải đúng theo cách công cụ này cho thấy: bắt đầu với các từ ngắn và những chữ cái phổ biến nhất.

Những bức thư thất lạc của Mary, Nữ hoàng Scotland, đã được giải mã như thế nào?

Năm 2023, George Lasry, Norbert Biermann và Satoshi Tomokiyo xác định 57 bức thư mã hóa trong một thư viện Pháp là của bà. Mật mã dùng gần 200 ký hiệu, nên họ kết hợp thuật toán leo đồi trên máy tính, vốn gợi ý nghĩa khả dĩ của nhiều ký hiệu, với công việc thủ công tỉ mỉ cho phần còn lại.

Sẵn sàng thử chưa?

Mở PictorX trong trình duyệt — không cần cài đặt, không cần thẻ tín dụng để bắt đầu.

Mở công cụ phân tích tần suất