Индекс на съвпадението
Методът се основава на изчисляване на вероятността два произволни текстови елемента да съвпаднат. Тази вероятност се нарича индекс на съвпадение. Уилям Фридман показа, че стойностите на индекса на съвпадение се различават значително за текстове от различно естество. Това ви позволява първо да определите дължината на шифриращия ключ и след това да намерите самия ключ.
Появата на метода на индекса на съвпадение отвори нови възможности в криптоанализа на шифъра на Виженер. В сравнение с обичайния по това време метод Kasiska, новият метод беше по-малко трудоемък, изискваше по-малко текст, беше по-податлив на автоматизация и по-малко податлив на грешки. Индексът на съвпадение беше по-ефективен и позволи анализ на шифри с дълги ключове.
Съдържание
- Първо се опитват да определят дължината на ключа. Дължината на ключа определя броя на използваните азбуки и периода на криптиране с тези азбуки. Следователно на този етап се изследва периодичността на шифрования текст;
- След като дължината бъде намерена, те започват да търсят определен тип ключ. За целта се изчисляват относителните измествания на използваните азбуки и след това ключът се избира чрез груба сила.
По-долу са дадени формулите за изчисляване на индекса на попадение. Първо се разглежда общият случай. След това разглеждаме няколко специални случая, в които индексът на съвпадение може да бъде оценен без анализ на текста.
Общ случай
Ще оценим вероятността като съотношението на благоприятните резултати (броя двойки идентични знаци в низ) към общия брой резултати (броя различни двойки знаци в низ).
Брой двойки еднакви знаци в низ:
Брой отделни двойки знаци в низ:
обикновен текст
| български | 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 |
случаен низ
Тази формула може да се използва за оценка на индекса на съвпадение на многоазбучен шифър. За английския език индексът на съвпаденията на многоазбучния шифър ще бъде 0,03856, за българския (без буквата "ё") - 0,03125.
Стойностите на индекса на съвпадение за обикновен текст и за многоазбучен шифър са значително различни. Това позволява, като се знае индексът на съвпаденията, да се определи дали текстът е получен от отворен чрез проста пермутация или е полиазбучен шифър.
Друга важна концепция еиндексът на взаимно съответствие.
Общ случай
Доказателството на тази формула е подобно на доказателството на формула (1).
Линии със смяна
Имайте предвид, че оттогава тогава смяната е циклична
По-долу са дадени стойностите на индекса на взаимно съответствие в зависимост от смяната за българския и английския език. Стойностите са дадени за смени от 0 до 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 |
| единадесет | 0,0251 |
| 12 | 0,0244 |
| 13 | 0,0291 |
| 14 | 0,0322 |
| 15 | 0,0244 |
| 16 | 0,0249 |
Обърнете внимание, че при нулево изместване индексът на взаимно съвпадение е забележимо по-голям, отколкото при ненулеви измествания. И така, според известната стойност на взаимния индекс на съвпаденията, можем да заключим дали отместването на низовите азбуки е нула или не.
По-рано беше показано, че индексът на съвпаденията за пермутация на обикновен текст и за многоазбучен шифър е забележимо различен. По този начин, чрез итериране на различни стойности на t и изчисляване за всяка от тях на индекса на съвпаденията, можем да изберем онези t, които са кратни на дължината на ключа. Не е трудно да се определи дължината на ключа от тези данни.
Нека напишем текста отново в колони с размер t .
Нека бъде даден текст, шифрован с шифъра на Виженер. Намерете ключовата дума и прочетете открития текст.
Поради факта, че пълният алгоритъм за намиране на дължината на ключа е изключително тромав, ние изчисляваме индекса на попадение само за t = 5 и се уверяваме, че дължината на ключа наистина е равна на 5.
Съпоставете стойностите на индекса за всеки от редовете:
| 1 | 0,05676 |
| 2 | 0,05896 |
| 3 | 0,06340 |
| 4 | 0,05810 |
| 5 | 0,07230 |
Процесът на търсене на относителни отмествания на редовете също е обобщен:
| 1 | — | — |
| 2 | 6 | 0,05494 |
| 3 | 3 | 0,05798 |
| 4 | 16 | 0,06068 |
| 5 | 3 | 0,06045 |
Намерена ключова дума: "дума".
След дешифрирането получаваме следния обикновен текст: