Chỉ số trùng hợp

Trong mật mã học, chỉ số trùng hợp là kỹ thuật đặt hai văn bản bên cạnh nhau và đếm số lần mỗi chữ cái xuất hiện cùng một vị trí trong hai văn bản. Bảng tỉ lệ số lần trùng hợp của mỗi chữ cái trong bảng so với tổng số lần trùng hợp gọi là bảng chỉ số trùng hợp, được dùng trong việc phân tích mật mã. Kỹ thuật được nhà mật mã học Mỹ William F. Friedman phát minh^[1]).

Ứng dụng

Kỹ thuật chỉ số trùng hợp được dùng để phân tích văn bản ngôn ngữ tự nhiên cũng như phân tích các văn bản mật mã. Dù chỉ có văn bản mật mã, các trùng hợp ngẫu nhiên trong văn bản vẫn xảy ra do ảnh hưởng từ trùng hợp trong thông điệp gốc. Ví dụ trong trường hợp phân tích mật mã Vigenère, đối với bản mã tạo ra do kỹ thuật mã hóa dùng nhiều bảng chữ cái lặp lại, nếu sắp xếp bản mã vào một ma trận, tỷ lệ trùng hợp ngẫu nhiên trong mỗi cột sẽ đạt cao nhất khi bề ngang của ma trận là bội của chiều dài khóa, nhờ đó ta có thể đoán được độ dài từ khóa của mật mã.

Chỉ số trùng hợp cũng được dùng để xác định hai văn bản có phải được viết bằng cùng một ngôn ngữ và bảng chữ cái hay không. (Kỹ thuật đã từng được sử dụng để nghiên cứu mật mã kinh thánh). Chỉ số này sẽ cao hơn rõ rệt so với chỉ số trùng hợp của hai văn bản khác ngôn ngữ, hay khác bảng chữ cái, hay văn bản sai ngữ pháp.

Để hiểu rõ tại sao, ta xét một "bảng chữ cái" chỉ có hai ký tự A và B. Giả sử rằng trong "ngôn ngữ" mà ta đang xét, chữ A được dùng 75%, chữ B được sử dụng 25%. Đặt hai văn bản của ngôn ngữ này bên cạnh nhau, các cặp ký tự cùng vị trí sẽ là:

Cặp ký tự	Xác suất
AA	56.25%
BB	6.25%
AB	18.75%
BA	18.75%

Như vậy, xác suất "trùng hợp" là 62.5% (56.25% AA + 6.25% BB).

Xét trường hợp cả hai văn bản trên đều được mã hóa bằng kỹ thuật mã hóa thay thế dùng một bảng chữ cái, với hai ký tự A và B thay thế cho nhau:

Cặp ký tự	Xác suất
AA	6.25%
BB	56.25%
AB	18.75%
BA	18.75%

Xác suất trùng hợp trong trường hợp này vẫn là 62.5% (6.25% AA + 56.25% BB), giống như trong "văn bản thô". Như vậy văn bản mới từ bảng chữ cái tạo ra bằng phép thay thế vẫn giữ những tính chất cũ đặc thù của ngôn ngữ đó.

Bây giờ xét trường hợp chỉ một trong hai thông điệp được mã hóa bằng mật mã trên ((A,B)→(B,A)). Dưới đây là bảng xác suất mới:

Cặp ký tự	Xác suất
AA	18.75%
BB	18.75%
AB	56.25%
BA	6.25%

Khái quát

Ví dụ

Tham khảo

1. Friedman, W.F. (1922). “The index of coincidence and its applications in cryptology”. Department of Ciphers. Publ 22. Geneva, Illinois, USA: Riverbank Laboratories. OCLC 55786052. The original application ignored normalization.

Đọc thêm

• Topics in cryptography