Індекс збігів — один з методів криптоаналізу шифру Віженера. Опис опублікував Вільямо Фрідман в 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 {\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}}$досліджено і відоме, що дозволяє розрахувати значення індексу збігів відкритого тексту для різних мов.

Нарешті, нехай ${\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}$. Як згадувалося вище, на основі цих значень взаємний індекс збігів може бути обчислений для будь-якого зсуву.

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

Розіб'ємо текст ${\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.

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

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

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

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

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

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

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

• 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