Khác biệt giữa bản sửa đổi của “Chỉ số trùng hợp”
Nội dung được xóa Nội dung được thêm vào
Dòng 8:
==Ứ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à:
{| class="wikitable"
|-
! Pair
! Probability
|-
| AA
| 56.25%
|-
| BB
| 6.25%
|-
| AB
| 18.75%
|-
| BA
| 18.75%
|-
|}
Overall, the probability of a "coincidence" is 62.5% (56.25% for AA + 6.25% for BB).
Now consider the case when ''both'' messages are encrypted using the simple monoalphabetic [[substitution cipher]] which replaces A with B and vice versa:
{| class="wikitable"
|-
! Pair
! Probability
|-
| AA
| 6.25%
|-
| BB
| 56.25%
|-
| AB
| 18.75%
|-
| BA
| 18.75%
|-
|}
The overall probability of a coincidence in this situation is 62.5% (6.25% for AA + 56.25% for BB), exactly the same as for the unencrypted "plaintext" case. In effect, the new alphabet produced by the substitution is just a uniform renaming of the original character identities, which does not affect whether they match.
Now suppose that only ''one'' message (say, the second) is encrypted using the same substitution cipher (A,B)→(B,A). The following pairs can now be expected:
{| class="wikitable"
|-
! Pair
! Probability
|-
| AA
| 18.75%
|-
| BB
| 18.75%
|-
| AB
| 56.25%
|-
| BA
| 6.25%
|-
|}
==Khái quát==
| |||