Індекс збігів

Індекс збігів — один з методів криптоаналізу шифру Віженера. Опис опублікував Вільямо Фрідман в 1920 році.

Метод ґрунтується на обчисленні ймовірності того, що два випадкові елементи тексту збіжаться. Цю ймовірність називають індексом збігів. Вільям Фрідман показав, що значення індексу збігів суттєво відрізняється для текстів різної природи. Це дозволяє спочатку визначити довжину ключа шифру, а потім знайти й сам ключ.

Поява методу індексу збігів відкрила нові можливості в криптоаналізі шифру Віженера. У порівнянні з поширеним в той час методом Казіскі, новий метод був менш трудомістким, вимагав меншої довжини тексту, був придатніший для автоматизації і менш схильний до помилок. Індекс збігів був ефективнішим і допускав аналіз шифрів з довгими ключами.

Історія

Блез Віженер представив опис простого, але стійкого шифру перед комісією Генріха III у Франції в 1586 році, й пізніше винахід шифру було присвоєно саме йому. Шифр Віженера мав репутацію виключно стійкого до «ручного» злому. Перша успішна атака на шифр Віженер була проведена Фрідріхом Казіскі в 1863 році. Його метод залишався основним методом криптоаналізу шифру Віженера аж до 1920 року, коли Вільям Фрідман опублікував монографію «Індекс збігу і його застосування в криптоаналізі» (англ. «Index of Coincidence and Its Applications in Cryptography»). Новий метод, описаний Фрідманом, пропонував більш ефективний і стійкий до помилок спосіб визначення довжини ключа. Метод індексу збігів отримав широке застосування. Пізніше він став використовуватися в криптоаналізі з допомогою машин.

Метод криптоаналізу шифру Віженера

Шифр Віженера є поліалфавітним шифром. Його криптоаналіз можна розбити на 2 етапи:

• Спочатку намагаються визначити довжину ключа. Довжина ключа задає кількість використовуваних алфавітів і період шифрування цими алфавітами. Тому на цьому етапі досліджується періодичність шифротекста;
• Після того, як знайдена довжина, приступають до пошуку конкретного виду ключа. Для цього обчислюють відносні зрушення, використовуваних алфавітів, а потім підбирають ключ перебором.

Індекс збігів

Нижче наведено формули для обчислення індексу збігів. Спочатку розглядається загальний випадок. Потім розглядаються кілька приватних випадків, у яких індекс збігів можна оцінити без аналізу тексту.

Загальний випадок

Розглянемо текст, написаний деякою мовою. Алфавіт мови будемо вважати що складається з символів. Розглянемо досить довгий рядок ${\displaystyle {\vec {x}}}$ із ${\displaystyle n}$ символів. Індексом збігу називають імовірність збігу двох довільних символів в рядку. Якщо ${\displaystyle f_{i}}$ — кількість ${\displaystyle i}$-го символу алфавіту в рядку ${\displaystyle {\vec {x}}}$, то індекс збігу обчислюється за формулою:

${\displaystyle I\left({\vec {x}}\right)=\sum \limits _{i=1}^{m}{\frac {f_{i}\left({f_{i}-1}\right)}{n\left({n-1}\right)}}}$      ${\displaystyle (1)}$

Доведення  

Будемо оцінювати вірогідність як відношення сприятливих результатів (кількість пар однакових символів в рядку) до загальної кількості випадків (кількість різних пар символів в рядку).

Кількість разних пар ${\displaystyle {\displaystyle i}}$-ого символу в рядку дорівнює: 

${\displaystyle {\displaystyle k_{i}=C_{f_{i}}^{2}={\frac {f_{i}\left({f_{i}-1}\right)}{2}}}}$

Кількість пар однакових символів в рядку:

${\displaystyle {\displaystyle k=\sum _{i=1}^{m}k_{i}=\sum _{i=1}^{m}{\frac {f_{i}\left({f_{i}-1}\right)}{2}}}}$

Число різних пар символів в рядку:

${\displaystyle {\displaystyle K=C_{n}^{2}={\frac {n\left({n-1}\right)}{2}}}}$

Звідси отримуємо:

${\displaystyle {\displaystyle I\left({\vec {x}}\right)={\frac {k}{K}}=\sum \limits _{i=1}^{m}{\frac {f_{i}\left({f_{i}-1}\right)}{n\left({n-1}\right)}}}}$

Відкритий текст

Припустимо, рядок ${\displaystyle {\vec {x}}}$ є відкритим текстом або отриманий з нього простою перестановкою. У цьому випадку індекс збігів зручно виразити через ймовірності появи ${\displaystyle i}$-го символу. Позначимо їх ${\displaystyle p_{i}}$. Тоді отримаємо наступну формулу:

${\displaystyle I\left({\vec {x}}\right)=\sum \limits _{i=1}^{m}p_{i}^{2}}$      ${\displaystyle (2)}$

Оскільки величини ${\displaystyle p_{i}}$ мають цілком певні значення, то для відкритого тексту індекс збігів не залежить від його змісту, а залежить тільки від мови, якою написаний текст. До того, значення ${\displaystyle p_{i}}$досліджено і відоме, що дозволяє розрахувати значення індексу збігів відкритого тексту для різних мов.

Мова	Індекс збігів
російська	0.0553[1]
англійська	0.0644[1] 0.0667[2]
італійська	0.0738[2]
іспанська	0.0775[2]
німецький	0.0762[2]
французька	0.0778[2]
ведійський санскрит	0.021076696
пракрит	0.046635758
класичний санскрит	0.045567736
гінді	0.041837864
урду	0.057535302

Випадковий рядок

Нарешті, нехай ${\displaystyle {\vec {x}}}$ — випадковий рядок. Тоді ймовірність появи кожного символу дорівнює

${\displaystyle p_{i}={\frac {1}{m}}}$

Використовуючи формулу ${\displaystyle (2)}$, отримаємо:

${\displaystyle I\left({\vec {x}}\right)=\sum _{i=1}^{m}{1 \over m^{2}}={1 \over m}}$      ${\displaystyle (3)}$

Цією формулою можна користуватися для оцінки індексу збігів поліалфавітного шифру. Для англійської мови індекс збігів поліалфавітного шифру складе 0,03856, для російського (без букви «ё») — 0,03125.

Значення індексу збігів для відкритого тексту і для поліалфавітного шифру істотно розрізняються. Це дозволяє, знаючи індекс збігів, визначити, отриманий текст із відкритого простою перестановкою, чи є поліалфавитним шифром.

Взаємний індекс збігів

Загальний випадок

Ще одним важливим поняттям є взаємний індекс збігів.

Розглянемо два рядки ${\displaystyle {\vec {x}}}$ і ${\displaystyle {\vec {y}}}$ з довжинами ${\displaystyle n}$ і ${\displaystyle n'}$ відповідно. Алфавіт, як і колись, складається з ${\displaystyle m}$ символів. Взаємним індексом збігів цих рядків називають імовірність того, що символ, випадково вибраний з першого рядка, збіжиться з випадково вибраними символом другого рядка. Нехай ${\displaystyle f_{i},g_{i}}$ — кількість ${\displaystyle i}$-го символу алфавіту в першому і другому рядках відповідно. Тоді взаємний індекс збігів буде дорівнювати:

${\displaystyle MI\left({{\vec {x}},{\vec {y}}}\right)={\sum \limits _{i=1}^{m}{\frac {f_{i}g_{i}}{nn'}}}}$      ${\displaystyle (4)}$

Доказ цієї формули аналогічний до доведення формули ${\displaystyle (1)}$.

Рядки зі зсувом

Практично важливим для методу індексу збігів є приватний випадок, коли обидва рядки, отримані зрушенням алфавіту відкритого тексту. Позначимо ${\displaystyle p_{i}}$ — ймовірності появи ${\displaystyle i}$-го символу в рядку ${\displaystyle {\vec {x}}}$, ${\displaystyle s}$ — зсув алфавіту рядка ${\displaystyle {\vec {y}}}$ щодо алфавіту рядка ${\displaystyle {\vec {x}}}$ (вліво). Тоді ймовірності появи ${\displaystyle {\vec {x}}}$-го символу алфавіту в рядку ${\displaystyle {\vec {y}}}$ рівні ${\displaystyle p_{i+s}}$ (використовується нумерація алфавіту рядка ${\displaystyle {\vec {x}}}$). Для взаємного індексу збігів отримуємо наступну формулу:

${\displaystyle MI\left({{\vec {x}},{\vec {y}}}\right)=\sum \limits _{i=1}^{m}{p_{i}p_{i+s}}}$      ${\displaystyle (5)}$

Зауважимо, що так як циклічний зсув, то

${\displaystyle \sum \limits _{i=1}^{m}{p_{i}p_{i+s}}=\sum \limits _{i=1}^{m}{p_{i-s}p_{i}}=\sum \limits _{i=1}^{m}{p_{i+m-s}p_{i}}}$

та взаємний індекс збігів для зрушень ${\displaystyle s}$ і ${\displaystyle m-s}$ приймає одне й те ж значення.

Нижче наведені значення взаємного індексу збігів в залежності від зсуву для російської та англійської мов. Значення наведені для зрушень від ${\displaystyle 0}$ до ${\displaystyle m/2}$. Як згадувалося вище, на основі цих значень взаємний індекс збігів може бути обчислений для будь-якого зсуву.

Для російської мови: Зсув Взаємний індекс 0 0,0553 1 0,0366 2 0,0345 3 0,0400 4 0,0340 5 0,0360 6 0,0326 7 0,0241 8 0,0287 9 0,0317 10 0,0265 11 0,0251 12 0,0244 13 0,0291 14 0,0322 15 0,0244 16 0,0249

Для англійської мови: Зсув Взаємний індекс 0 0,0644 1 0,0394 2 0,0319 3 0,0345 4 0,0436 5 0,0332 6 0,0363 7 0,0389 8 0,0338 9 0,0342 10 0,0378 11 0,0440 12 0,0387 13 0,0428

Зазначимо, що при нульовому зсуві взаємний індекс збігів помітно більший, ніж при ненульових зрушеннях. А значить, по відомому значенню взаємного індексу збігів можна зробити висновок, є зрушення алфавітів рядків нульовим, або немає.

Алгоритм знаходження довжини ключа

Розіб'ємо текст ${\displaystyle x_{1}}$ ${\displaystyle x_{2}}$ ${\displaystyle ...}$ ${\displaystyle x_{n}}$ на стовпчики розміру ${\displaystyle t}$.

${\displaystyle x_{1}}$ ${\displaystyle x_{t+1}}$ ${\displaystyle x_{2t+1}}$ ${\displaystyle ...}$

${\displaystyle x_{2}}$ ${\displaystyle x_{t+2}}$ ${\displaystyle x_{2t+2}}$ ${\displaystyle ...}$

${\displaystyle ...}$  ${\displaystyle ...}$  ${\displaystyle ...}$  ${\displaystyle ...}$

${\displaystyle x_{t}}$  ${\displaystyle x_{2t}}$  ${\displaystyle x_{3t}}$  ${\displaystyle ...}$

Якщо ${\displaystyle t}$ кратна довжині ключа, то кожні два елементи тексту, віддалені один від одного на ${\displaystyle a\times t}$ позицій, ${\displaystyle a\in N}$, зашифровані одним і тим же алфавітом. А це означає, що кожен рядок у виписаній вище таблиці отриманий із відкритого тексту перестановкою. Якщо ж ${\displaystyle t}$ не кратна довжині ключа, то рядки є поліалфавітним шифром.

Раніше було показано, що індекс збігів для перестановки відкритого тексту й для поліалфавитного шифру помітно відрізняється. Таким чином, перебираючи різні значення ${\displaystyle t}$ і обчислюючи для кожного з них індекс збігів, ми можемо виділити ті ${\displaystyle t}$, які кратні довжині ключа. Визначити довжину ключа за цими даними не становить труда.

Алгоритм знаходження ключа

Припустимо, ми визначили довжину ключа ${\displaystyle t}$. Знайдемо тепер сам ключ.

Знову випишемо текст у стовпці розміру ${\displaystyle t}$.

${\displaystyle x_{1}}$ ${\displaystyle x_{t+1}}$ ${\displaystyle x_{2t+1}}$ ${\displaystyle ...}$

${\displaystyle x_{2}}$ ${\displaystyle x_{t+2}}$ ${\displaystyle x_{2t+2}}$ ${\displaystyle ...}$

${\displaystyle ...}$  ${\displaystyle ...}$  ${\displaystyle ...}$  ${\displaystyle ...}$

${\displaystyle x_{t}}$  ${\displaystyle x_{2t}}$  ${\displaystyle x_{3t}}$  ${\displaystyle ...}$

Розглянемо два рядки цієї таблиці. Зсунемо алфавіт одного з рядків на ${\displaystyle s}$ символи і обчислимо взаємний індекс збігів отриманих рядків. Оскільки кожен із цих двох рядків отриманий зрушенням алфавіту відкритого тексту, то максимум взаємного індексу збігів буде спостерігатися при нульовому кінцевому відносному зсуві.

Тому застосовується наступний алгоритм: обчислюється взаємний індекс збігів для різних ${\displaystyle s}$, шукається значення ${\displaystyle s}$, при якому взаємний індекс збігів максимальний. Тоді початковий відносний зсув рядків буде дорівнювати ${\displaystyle s}$ (${\displaystyle m}$ — розмір алфавіту). Обчислюються відносні зрушення між усіма парами рядків. Оскільк зрушення рядків таблиці відповідають зрушенням букв ключа, то залишається перебрати ${\displaystyle m}$ можливих ключів і вибрати з них найбільш правдоподібний.

Приклад використання

Нехай дано деякий текст, зашифрований шифром Віженера. Знайдемо ключове слово і прочитаємо відкритий текст.

влцдутжбюцхъяррмшбрхцэооэцгбрьцмйфктъъюьмшэсяцпунуящэйтаьэдкцибр
ьцгбрпачкъуцпъбьсэгкцъгуущарцёэвърюуоюэкааэбрняфукабъарпяъафкъиьжяффнйо
яфывбнэнфуюгбрьсшьжэтбэёчюъюръегофкбьчябашвёэуъъюаднчжчужцёэвлрнчулб
юпцуруньъшсэюъзкцхъяррнрювяспэмасчкпэужьжыатуфуярюравртубурьпэщлафоуф
бюацмнубсюкйтаьэдйюнооэгюожбгкбрънцэпотчмёодзцвбцшщвщепчдчдръюьскасэг
ъппэгюкдойрсрэвоопчщшоказръббнэугнялёкьсрбёуыэбдэулбюасшоуэтъшкрсдугэфл
бубуъчнчтртпэгюкиугюэмэгюккъъпэгяапуфуэзьрадзьжчюрмфцхраююанчёчюъыхьъ
цомэфъцпоирькнщпэтэузуябащущбаыэйчдфрпэцъьрьцъцпоилуфэдцойэдятррачкубу
фнйтаьэдкцкрннцюабугюуубурьпйюэъжтгюркующоъуфъэгясуоичщщчдцсфырэдщэ
ъуяфшёчцюйрщвяхвмкршрпгюопэуцчйтаьэдкцибрьцыяжтюрбуэтэбдуящэубъибрюв
ъежагибрбагбрымпуноцшяжцечкфодщоъчжшйуъцхчщвуэбдлдъэгясуахзцэбдэулькнъ
щбжяцэьрёдъьвювлрнуяфуоухфекьгцчччгэъжтанопчынажпачкъуъмэнкйрэфщэъьбуд
эндадъярьеюэлэтчоубъцэфэвлнёэгфдсэвэёкбсчоукгаутэыпуббцчкпэгючсаъбэнэфърк
ацхёваетуфяепьрювържадфёжбьфутощоявьъгупчршуитеачйчирамчюфчоуяюонкяжы
кгсцбрясшчйотъъжрсщчл

Зважаючи на те, що повний алгоритм пошуку довжини ключа є дуже громіздким, обчислимо індекс збігів тільки для ${\displaystyle t=5}$ і переконаємося, що довжина ключа дійсно дорівнює 5.

втхмцццтмцяаццацсъавоаябяъфянюстюебаудуву...
лжъшэгмъшпщьигчпэгръюэфъъиффэгшбъгьшънжлл...
цбябобйъэуээббкъгуцрэбуааьнынбьэюочвъчцрб...
дюррорфюснйдрръбкуёюкркрфжйвфржёрфяёюжёню...
уцрхэькьяуткьпуьцщэуанапкяобуьэчъкбэачэчп...

Значення індексу збігів для кожного з рядків:

Рядок	Індекс збігів
1	0.05676
2	0.05896
3	0.06340
4	0.05810
5	0.07230

Процес пошуку відносних зсувів рядків також наведемо в стислому вигляді:

Знайдене ключове слово: «слово».

Після розшифровки отримуємо наступний відкритий текст:

развебытьздоровымтожесамоечтонебытьбольнымопределенноздоровьеэтонечтоболь
шеедлянасфизическоездоровьеэтоисостояниеиспособностьиэнергиязаниматьсятемчт
онамнеобходимополучатьприэтомудовольствиеивыздоравливатьбезвсякойпомощиз
доровьепарадоксальновынеможетенепосредственнозаставитьсебястатьздоровымвам
остаетсятольконаблюдатьзатемкакудивительнаяспособностьвашегоорганизмаисцеля
тьсебяначинаетдействоватьсамасобойивашебогатствоилибедностьжестокостьилидоб
родетельностьнеимеютздесьповидимомуникакогозначенияздоровьеэтонечтопозитив
ноеононеозначаетотказотудовольствияздоровьеявляетсяестественнымследствиемна
шегообразажизнивзаимоотношенийдиетыокружающейобстановкиздоровьеэтонепре
дметсобственностиэтопроцессэтоточтомыделаемрезультатнашихмыслейичувствэтоо
бразсуществованияинтересночтонаправлениемедицинскихисследованийвсебольшеи
большеотклоняетсявсторонутойобластикотораядосихпорсчиталасьсферойдеятельно
стипсихологовисейчасужетруднопровестичеткиеразграничениямеждуфизическимии
ментальнымифакторамизаболеваний

Примітки

1. Пилиди, 2009, с. 55.
2. Friedman, 1938, с. 117.

Див. також

• Поліалфавітний шифр
• Метод Казіскі
• Автокореляційний метод

Література

• William Frederick Friedman. Military Cryptanalysis. Part II. Simpler vrieties of polyalphabetic substitution systems. — Washington : United States goverment printing office, 1938. — 120 p. Архівовано вересень 11, 2010 на сайті Wayback Machine.
• Пилиди В. С. Криптография. Вводные главы. — Ростов-на-Дону : ЮФУ, 2009. — 110 с.
• Бауэр Ф., Расшифрованные секреты. Методы и принципы криптологии: Пер. сангл. - М.: Мир, 2007. - 550 с. — ISBN 5-03-003551-6
• Жданов О.Н., Куденкова И.А. Криптоанализ классических шифров — Красноярск 2008