Mã Vigenère là mật mã dùng một từ khoá để mỗi chữ cái trong thư được dịch đi một số bước khác nhau, nên cùng một chữ gốc có thể biến thành nhiều chữ mã khác nhau. Nó được Giovan Battista Bellaso mô tả năm 1553, về sau mới bị gắn nhầm tên Blaise de Vigenère, và giữ biệt danh "mật mã không thể phá" cho tới khi Friedrich Kasiski công bố cách phá năm 1863 — tức gần ba thế kỷ.
Câu chuyện của nó là câu chuyện về một ý tưởng thông minh, một cái tên đặt sai, và một điểm yếu nằm ngay trong chính cái làm nên sức mạnh của nó: từ khoá lặp lại.
Vì sao cần một mật mã mới
Từ thế kỷ IX, học giả al-Kindi đã mô tả cách phá các mật mã thay thế đơn giản bằng việc đếm tần suất chữ cái. Ở mật mã Caesar hay bảng thay thế xáo trộn, mỗi chữ gốc luôn biến thành đúng một chữ mã, nên chữ thông dụng nhất của ngôn ngữ vẫn lộ ra là chữ mã xuất hiện nhiều nhất.
Đến thời Phục Hưng, các triều đình châu Âu đều có người chuyên giải thư mã của nhau. Những người làm mật mã cần một cách khiến phép đếm tần suất vô dụng. Lời giải là dùng nhiều bảng chữ thay vì một — gọi là mật mã đa bảng.
Ba người đặt nền và một cái tên sai
| Năm | Người | Đóng góp |
|---|---|---|
| Khoảng 1467 | Leon Battista Alberti (Ý) | Đĩa mã hai vòng chữ, xoay đĩa sau vài chữ để đổi bảng — ý tưởng đa bảng đầu tiên được ghi lại |
| 1508 (in 1518) | Johannes Trithemius (Đức) | Bảng vuông 26 × 26 (tabula recta), mỗi hàng là một bảng chữ dịch thêm một bước |
| 1553 | Giovan Battista Bellaso (Ý) | Dùng một từ khoá để chọn hàng trong bảng cho từng chữ — chính là "mã Vigenère" ngày nay |
| 1586 | Blaise de Vigenère (Pháp) | Viết Traicté des chiffres, mô tả một biến thể mạnh hơn dùng chính thư làm khoá (autokey) |
| Thế kỷ XIX | — | Tên Vigenère bị gắn cho cách của Bellaso, và cái tên sai ấy ở lại tới nay |
Điều trớ trêu: Vigenère thật ra mô tả một hệ mã khó phá hơn cái mang tên ông. Còn Bellaso, người nghĩ ra cách dùng từ khoá, gần như bị lãng quên ngoài giới nghiên cứu.
Cách hoạt động: Caesar luân phiên
Hãy coi mã Vigenère là nhiều mã Caesar chạy xen kẽ nhau. Từ khoá quyết định mỗi chữ dịch đi bao nhiêu bước: A = 0, B = 1, C = 2, … Z = 25.
Ví dụ với từ khoá TRANG
Thư gốc (tiếng Việt không dấu, bỏ cách): HENGAPLUCBAYGIO — "hẹn gặp lúc bảy giờ". Từ khoá TRANG được viết lặp lại cho đủ độ dài thư:
| Thư gốc | H | E | N | G | A | P | L | U | C | B | A | Y | G | I | O |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| Khoá | T | R | A | N | G | T | R | A | N | G | T | R | A | N | G |
| Bước dịch | 19 | 17 | 0 | 13 | 6 | 19 | 17 | 0 | 13 | 6 | 19 | 17 | 0 | 13 | 6 |
| Thư mã | A | V | N | T | G | I | C | U | P | H | T | P | G | V | U |
Thư mã: AVNTGICUPHTPGVU. Để ý: chữ A trong thư gốc xuất hiện hai lần và biến thành G rồi T. Chữ G thành T ở vị trí thứ tư nhưng thành G ở vị trí thứ mười ba. Phép đếm tần suất thông thường không còn bám vào đâu được — mỗi chữ gốc bị "chia" ra năm kiểu mã khác nhau.
Người nhận biết từ khoá thì làm ngược lại: lùi mỗi chữ theo đúng bước của chữ khoá tương ứng.
Bảng vuông Trithemius
Thời trước máy tính, người ta tra bằng bảng 26 × 26: hàng là chữ khoá, cột là chữ gốc, ô giao nhau là chữ mã. Hàng A là bảng chữ bình thường, hàng B dịch một bước, và cứ thế tới hàng Z. Kẻ một bảng như vậy trên giấy kẻ ô mất chừng nửa giờ, và là cách tốt để trẻ lớn hiểu "đa bảng" nghĩa là gì.
"Le chiffre indéchiffrable"
Người Pháp gọi nó là le chiffre indéchiffrable — mật mã không thể giải. Mã Vigenère khá chậm và dễ sai khi làm bằng tay, nên giới ngoại giao không phải lúc nào cũng dùng; nhiều triều đình vẫn ưa các bảng mã thay thế phức tạp hơn nhưng nhanh hơn. Dù vậy, danh tiếng "không thể phá" của nó tồn tại rất lâu.
Ngay cả năm 1868, nhà văn Lewis Carroll — tác giả Alice ở xứ sở thần tiên — còn viết một bài ngắn tên "The Alphabet-Cipher" giới thiệu đúng cách mã này và cho rằng không ai đọc được thư nếu không biết từ khoá. Lúc đó, cách phá đã được công bố năm năm.
Trong cuộc Nội chiến Hoa Kỳ (1861–1865), phe miền Nam dùng mã Vigenère với một vài từ khoá cố định; tài liệu còn lại cho thấy thư của họ thường bị phía bên kia đọc được. Dùng đi dùng lại vài từ khoá chính là cách nhanh nhất làm hỏng một hệ mã.
Cách phá: tìm độ dài từ khoá
Babbage và Kasiski
Charles Babbage, nhà toán học người Anh nổi tiếng với các cỗ máy tính toán bằng cơ khí, phá được mã Vigenère khoảng giữa những năm 1850 nhưng không công bố. Năm 1863, sĩ quan người Phổ Friedrich Kasiski in một cuốn sách nhỏ trình bày phương pháp tương tự. Vì vậy cách phá này mang tên phép thử Kasiski.
Ý tưởng chính
- Tìm đoạn lặp: trong thư dài, một cụm chữ phổ biến (như "NG" hay "THE") đôi khi rơi trùng vào cùng vị trí của từ khoá. Khi đó nó tạo ra cùng một cụm chữ mã. Tìm các cụm 3–4 chữ mã lặp lại.
- Đo khoảng cách: khoảng cách giữa hai lần lặp gần như chắc chắn là bội số của độ dài từ khoá. Nếu các khoảng cách là 15, 25, 40, thì ước chung là 5 — từ khoá có lẽ dài 5 chữ.
- Chia cột: biết độ dài 5 rồi, chia thư mã thành 5 cột: chữ 1, 6, 11…; chữ 2, 7, 12… Mỗi cột thật ra là một mã Caesar đơn giản.
- Đếm tần suất từng cột: mỗi cột đủ dài sẽ lộ chữ thông dụng nhất, từ đó suy ra bước dịch — tức một chữ của từ khoá.
Nói gọn: Vigenère chỉ là năm mã Caesar đan vào nhau. Gỡ được sợi đan là phá được.
Điều gì khiến phá dễ hay khó
| Yếu tố | Dễ phá hơn | Khó phá hơn |
|---|---|---|
| Độ dài từ khoá | Ngắn (3–5 chữ) | Dài |
| Độ dài thư | Thư dài, nhiều đoạn lặp | Thư rất ngắn |
| Từ khoá | Từ có nghĩa, đoán được | Chuỗi chữ ngẫu nhiên |
| Dùng lại khoá | Một khoá cho nhiều thư | Mỗi thư một khoá |
Khi nào Vigenère thật sự không thể phá
Đẩy bảng trên tới tận cùng: nếu từ khoá là chuỗi chữ hoàn toàn ngẫu nhiên, dài bằng chính bức thư, và chỉ dùng một lần, thì không còn đoạn lặp nào để Kasiski bám vào, mỗi cột chỉ có đúng một chữ. Về sau người ta chứng minh được bằng toán rằng cách dùng như vậy là không thể phá — gọi là "sổ dùng một lần" (one-time pad).
Cái khó nằm ở chỗ khác: phải trao cho người nhận một khoá ngẫu nhiên dài bằng mọi bức thư sẽ gửi, giữ nó bí mật, và tiêu huỷ sau khi dùng. Trên thực tế, đó là việc vô cùng phiền phức. Mã Vigenère "không thể phá" chỉ khi nó thôi không còn là Vigenère thông thường.
Góc nhìn hôm nay: tự tay làm và phá
- Làm mật thư cho nhóm bạn: chọn một từ khoá chung, mã một câu ngắn, đổi cho nhau giải. Với câu ngắn và khoá đủ dài, gần như không ai đoán được nếu không biết khoá.
- Thử làm Kasiski: mã một đoạn văn dài khoảng 300 chữ bằng từ khoá 4 chữ, đưa cho bạn khác tìm đoạn lặp và độ dài khoá. Đây là bài tập toán rất hay về ước chung lớn nhất.
- Học lập trình: viết chương trình mã hoá – giải mã Vigenère là bài tập tiếp theo tự nhiên sau Caesar.
- Đọc thêm: sách The Code Book của Simon Singh có một chương dài, dễ đọc về Vigenère và cuộc truy tìm của Babbage.
Bài học lớn nhất của mã Vigenère không nằm ở thuật toán. Nó nằm ở chỗ: một hệ mã có tiếng "không thể phá" chỉ đúng tới khi có người tìm ra điểm lặp lại. Và gần như hệ mã nào cũng có điểm lặp, nếu người dùng lười đổi khoá.
Câu hỏi thường gặp
Mã Vigenère là gì?
Mã Vigenère là mật mã đa bảng dùng một từ khoá để quyết định mỗi chữ cái trong thư dịch đi bao nhiêu bước. Vì bước dịch thay đổi theo từng chữ, cùng một chữ gốc có thể thành nhiều chữ mã khác nhau, khiến phép đếm tần suất thông thường vô dụng.
Ai phát minh mã Vigenère?
Cách mã dùng từ khoá này được Giovan Battista Bellaso mô tả năm 1553. Blaise de Vigenère viết về mật mã năm 1586 và mô tả một biến thể mạnh hơn, nhưng đến thế kỷ XIX tên ông bị gắn nhầm cho cách của Bellaso.
Mã Vigenère bị phá khi nào?
Charles Babbage phá được vào khoảng giữa những năm 1850 nhưng không công bố. Friedrich Kasiski công bố phương pháp phá năm 1863, dựa trên việc tìm các đoạn chữ mã lặp lại để suy ra độ dài từ khoá.
Mã Vigenère khác mã Caesar thế nào?
Mã Caesar dịch mọi chữ cùng một số bước, nên chỉ có 25 khoá và dễ phá bằng đếm tần suất. Mã Vigenère thay đổi bước dịch theo từng chữ của từ khoá, giống nhiều mã Caesar đan xen, nên khó phá hơn nhiều.
Làm sao giải mã Vigenère khi đã biết từ khoá?
Viết từ khoá lặp lại dưới thư mã cho đủ độ dài. Với mỗi chữ, lùi chữ mã đi số bước bằng vị trí của chữ khoá tương ứng, với A là 0, B là 1 và cứ thế. Kết quả là thư gốc.
