Crypto-IT

Indeks koincydencji (ang. index of coincidence) to współczynnik określający jak bardzo prawdopodobna jest sytuacja, że w trakcie porównywania dwóch dowolnych tekstów litera po literze, oba porównywane znaki będą takie same.

Wartość indeksu koincydencji wylicza się biorąc pod uwagę prawdopodobieństwo wystąpienia danej litery w tekście i określając prawdopodobieństwo porównania jej z taką samą literą w drugim tekście (które zależy oczywiście od prawdopodobieństwa pojawienia się tej litery w drugim tekście). Dla tekstu o długości N i alfabecie o długości c (przykładowo, dla języka angielskiego c = 26) wartość współczynnika koincydencji IC (Index of Coincidence) przy porównywaniu tego tekstu z nim samym, tyle że przesuniętym o losową liczbę pozycji można wyrazić wzorem:
    IC = (n₁(n₁-1) + ... + n_c(n_c-1)) / (N(N-1) / c) ,
gdzie n_i to liczba wystąpień danej litery w całym tekście. Kliknij tutaj, aby dowiedzieć się skąd ten wzór.

W szczególności, analizując częstotliwości występowania kolejnych liter w danym języku (f_i) można określić spodziewany współczynnik koincydencji dla danego języka (czyli podczas porównywania dwóch tekstów napisanych w tym samym języku):
    IC_spodziewany = (f₁² + ... + f_c²) / (1/c)

Jeżeli w danych języku wszystkie litery występowałyby jednakowo często, łatwo zauważyć, że spodziewana wartość współczynnika koincydencji wynosiłaby 1. Oczywiście, we wszystkich językach różne litery występują różnie często i dlatego współczynniki koincydencji dla poszczególnych języków różnią się między sobą. Na przykład, dla języka angielskiego ta wartość wynosi 1,73.

Można zauważyć, że indeks koincydencji wyliczony dla dwóch tekstów napisanych w różnych językach będzie zwykle zauważalnie mniejszy od spodziewanych indeksów koincydencji dla tych języków. Bierze się to stąd, że litery występujące często w jednym tekście, w drugim tekście (napisanym w innym języku) niekoniecznie muszą być równie popularne, więc prawdopodobieństwo spotkań tych samych liter w obu porównywanych tekstach jest mniejsze.

Indeks koincydencji jest wykorzystywany w kryptografii do łamania szyfrów podstawieniowych i prostych szyfrów XOR.

Przykładowo, mając wiadomość zaszyfrowaną za pomocą szyfru podstawieniowego lub szyfru XOR można wyznaczyć długość sekretnego klucza szyfrującego. Robi się to porównując zaszyfrowany tekst litera po literze (lub odpowiednio bajt po bajcie) z tym samym tekstem, tyle że przesuniętym względem początku o ilość pozycji równą aktualnie sprawdzanej długości klucza. Dla każdego sprawdzanego przypadku (czyli dla każdej długości klucza od 1 do momentu znalezienia rozwiązania) należy wyliczyć wartość indeksu koincydencji i ją zapamiętać.

Kiedy natrafi się na właściwe przesunięcie tekstów, równe długości sekretnego klucza, zniekształcenia wprowadzone przez nieznany klucz zniosą się i w ogólnym rozrachunku znikną:

• w przypadku szyfru podstawieniowego litery w górnym i dolnym tekście na odpowiadających sobie pozycjach będą przesunięte o taką samą liczbę znaków,
• w przypadku szyfru XOR modyfikacje bitów w odpowiadających sobie sprawdzanych bajtach będą takie same.

Po natrafieniu na właściwe przesunięcie, poszczególne porównywane znaki w pierwszym i drugim tekście -mimo, że nieznane- są znakami należącymi do tego samego języka, więc wyliczając dla nich współczynnik koincydencji, otrzyma się w wyniku wartość zbliżoną do wartości spodziewanej dla danego języka i znacznie odbiegającą od pozostałych, otrzymywanych wcześniej wartości współczynnika koincydencji. Podczas porównywania dwóch tekstów z niewłaściwym przesunięciem, litery (bajty) w górnym i dolnym tekście były zniekształcone inaczej, więc można przyjąć, że były zapisane w dwóch różnych językach, z różnymi częstotliwościami występowania poszczególnych liter w pierwszym i drugim tekście.

Poprawna, zauważalnie większa wartość współczynnika koincydencji będzie powtarzać się dla każdego przesunięcia tekstów, równego długości klucza lub będącego jej całkowitą wielokrotnością (ponieważ ten sam sekretny klucz powtarza się cyklicznie).

Współczynniki koincydencji można oszacować dla różnych języków, biorąc pod uwagę częstotliwości występowania liter. Oczywiście są to wartości średnie, ponieważ w poszczególnych rodzajach tekstów (teksty naukowe, literatura piękna, itd.) częstotliwości występowania konkretnych liter nieznacznie się od siebie różnią.

• język angielski - 1.73
• język rosyjski - 1.76
• język hiszpański - 1.94
• język portugalski - 1.94
• język włoski - 1.94
• język francuski - 2.02
• język niemiecki - 2.05

Czasami wartości współczynników koincydencji wygodniej jest podać bez uwzględnienia znormalizowania, zależnego od ilości liter w alfabecie. Przykładowo, dla języka angielskiego wartość współczynnika koincydencji bez normalizacji wynosi:
    1,73 / 26 = 0,067