Phép thử Kasiski

Quan sát mà phương pháp dựa vào

Mã Vigenère dịch mỗi chữ cái đi một lượng khác nhau, chạy vòng theo một từ khóa. Điều đó đánh bại việc đếm chữ cái, vì cùng một chữ cái bản rõ trở thành những chữ cái bản mã khác nhau tùy vị trí. Nhưng khóa thì lặp lại, và sự lặp lại rò rỉ ra ngoài.

Giả sử từ THE xuất hiện hai lần trong bản rõ, và tình cờ cả hai lần đều khớp với cùng ba chữ cái của khóa. Cả hai mã hóa ra cùng ba chữ cái bản mã. Khoảng cách giữa chúng, đếm theo chữ cái, khi đó là một số nguyên vòng khóa: một bội số của độ dài khóa.

Một sự trùng hợp như vậy chứng minh được rất ít. Hàng chục sự trùng hợp, phân tích ra thừa số và cộng dồn, thì chỉ thẳng vào độ dài.

Công cụ này đo cái gì

Mọi chuỗi có độ dài bạn chọn mà xuất hiện quá một lần đều được thu thập kèm vị trí. Với mỗi chuỗi, mọi khoảng cách từng cặp đều được tính, chứ không chỉ khoảng hở giữa các lần liền kề, vì ba lần xuất hiện mang ba mẩu bằng chứng và chỉ lấy khoảng hở liền kề là vứt đi một mẩu.

Sau đó mỗi độ dài khóa ứng viên nhận hai con số: nó chia hết bao nhiêu khoảng cách, và bao nhiêu chuỗi lặp khác nhau đã góp ít nhất một trong số đó. Việc xếp hạng dùng con số thứ nhất, đã hiệu chỉnh cho ngẫu nhiên. Con số thứ hai nằm bên cạnh và được cố ý giữ ngoài điểm số, vì nó là một phán đoán chứ không phải phép tính: một chuỗi lắm lời lặp tám lần sẽ thổi phồng số khoảng cách mà không thêm bằng chứng độc lập nào, trong khi ba chuỗi khác nhau cùng đồng ý về một thừa số là ba sự trùng hợp riêng biệt cùng chỉ một hướng. Nếu độ dài được gợi ý chỉ dựa vào một chuỗi duy nhất, đó chính là con số nên khiến bạn nghi ngờ.

Cái bẫy của các ước

Đây là chỗ nhiều người vấp, và nó là số học chứ không phải mật mã học. Nếu 12 chia hết một khoảng cách thì 2, 3, 4 và 6 cũng chia hết. Mọi ước của độ dài khóa thật đều thừa hưởng trọn điểm của nó, nên một bảng xếp theo hậu thuẫn luôn đưa các thừa số nhỏ nhất lên đầu, bất kể khóa thật ra là gì.

Cách sửa cũng là số học. Hãy tính phí mỗi thừa số theo phần hậu thuẫn mà ngẫu nhiên cho không: 2 chia hết một nửa của bất kỳ tập khoảng cách nào, nên phải chia đôi con số thô của nó trước khi đặt cạnh một thừa số chỉ chia hết một phần sáu. Hiệu chỉnh như vậy thì độ dài khóa thật vượt lên trên chính các ước của nó, vì một ước chỉ mang phần bằng chứng của riêng mình. Hiệu chỉnh thêm cả nhiễu mà một thừa số được phép có, vốn tăng theo thừa số, thì độ dài thật cũng vượt lên trên các bội của nó. Còn lại một quy tắc duy nhất không có giá trị nào chỉnh tay: trong mọi họ ước và bội, giữ lại thành viên mạnh nhất. Bảng đếm đầy đủ vẫn nằm bên dưới để bạn có thể không đồng ý: nếu độ dài được gợi ý chỉ có một chuỗi hậu thuẫn trong khi một thừa số khác được sáu chuỗi hậu thuẫn, thừa số đó đáng để nhìn lại.