Шифри Сізара і Віженера: Від Аналізу Частотності до Наступу Касіскі

Зміна алфавіту

Ціфрування Цезаря, яке, як повідомляється, використовувалося Юлієм Цезарем для військової кореспонденції, полягає у зміщенні кожної літери алфавіту наперед на фіксовану кількість k: A перетворюється на D при зміщенні на 3, B – на E, і так далі, обертаючись від Z назад до A. Розшифрування відбувається шляхом зміни напір у зворотний бік на ту ж саму величину k. У нього існує рівно 25 можливих ключів (26 мінус марна зміна 0), що означає, що він практично не забезпечує реальної безпеки – комп’ютер або уважна людина можуть просто спробувати всі 25 зсувів і прочитати, який з них дає англійський текст.

Віженер: інший зсув для кожної літери

Віженерівське шифрування (XVI століття, довгий час помилково приписуване та колись називане «Le chiffre indéchiffrable») усуває слабкість однозмінного шифру шляхом повторення ключового слова під текстом і використання власної позиції літери ключового слова як зсуву для відповідної позиції.

Текст: А Т Т А К О Т Д А В Н Ключ: Л Е М О Н Л Е М О Н Л Е Шифротекст: Л Х Ф О П В Е Ф Р Н Р (кожна літера зміщена відповідно до літери ключа, розташованої поруч) C_i = (P_i + K_{i mod m}) mod 26, m = довжина ключа Оскільки зсув змінюється від літери до літери відповідно до ключового слова, одна й та сама літера в тексті шифрується в різні символи шифротексту на різних позиціях, що ускладнює монографічний шаблон частоти літер, який робить Кассірівське шифрування таким розкривним — протягом майже трьох століть воно справді стійке до неформального криптоаналізу.

plaintext:   A T T A C K A T D A W N
key:         L E M O N L E M O N L E
ciphertext:  L X F O P V E F R N H R    (each letter shifted by its aligned key letter)

C_i = (P_i + K_{i mod m}) mod 26,   m = key length

Розшифрування Цезаря: аналіз частот

Англійські літери мають відому нерівномірність у розподілі: E зустрічається приблизно 12,7% часу, T – близько 9,1%, тоді як J, Q, X та Z майже не фіксуються. При шифруванні Цезарем цей профіль частот просто зміщується на k позицій. Таким чином, нападник вимірює частоти літер у зашифрованому тексті, знаходить зсув, який найкраще узгоджує пік (зазвичай відповідність найчастішої літери в зашифрованому тексті E) із відомими англійськими статистиками, і відновлює k безпосередньо – точно так само, як автоматичне виділення частот у цьому графіку виконується в режимі реального часу.

Розшифрування Віженер: визначення довжини ключа спочатку

Віженер протистоїть простому аналізу частот на всьому шифротексті, оскільки 26 різних алфавітів зсуву переплетені. Класичний метод, Kasiski examination, замість цього шукає повторювані підрядки у шифротексті; якщо одна й та сама частина тексту (plaintext) співпадає з однією й тією ж частиною повторюваного ключа двічі, це призводить до ідентичної підрядки шифротексту, а відстань між повторами, швидше за все, є кратним довжині ключа m. Після того, як m відомо, шифротекст ділиться на m незалежних потоків зсуву Віженер (кожен m-тий символ має один і той же зсув), і звичайний аналіз частот розбиває кожен з них окремо.

Індекс перехресної побічної кількості: вимірювання 'англійськості' потоку тексту

Індекс перехресної побічної кількості (ІПК) надає більш надійний, статистичний спосіб знаходження *m*, не потребуючи пошуку повторів. Він вимірює ймовірність того, що дві випадково обрані з тексту літери є однаковими.

ІПК = ∑_{i=1}^{26} n_i(n_i - 1) / (N(N - 1)) де n_i – кількість літер *i*, N – загальна кількість літер випадковий текст (26 рівноймовірних літер): ІПК ≈ 0,038 нормальний англійський текст: ІПК ≈ 0,067 Vigenère, розділений за правильною довжиною ключа *m*: кожний з *m* потоків є однозміщеним англійським текстом, тому його ІПК наближається до 0,067; при неправильній довжині ключів потоки поводяться ближче до випадкових, і ІПК падає до 0,038. Вибір кандидатів для довжини ключа та вибір того, що дає найвищий середній ІПК у розбитих потоках, надійно визначає *m*, після чого здійснюється такий самий аналіз частот, що й руйнує шифр Цезаря, кожен з *m* потоків також руйнується по черзі – обидва напади є одним і тим самим принципом, застосованим один раз, а потім *m* разів паралельно.

IC = Σ n_i(n_i − 1) / (N(N − 1))     n_i = count of letter i, N = total letters

random text (26 equiprobable letters):  IC ≈ 0.038
normal English text:                    IC ≈ 0.067
Vigenère split at the correct key length m: each of the m streams is single-shifted
English, so its IC lands near 0.067; split at the wrong length, the streams behave
closer to random and IC drops toward 0.038.

Frequently asked questions

Спробуйте наживо

Усе, що вище, працює прямо у вашому браузері — відкрийте Caesar & Vigenère Ciphers і змінюйте параметри під час роботи. Нічого не встановлюється, нічого не завантажується на сервер, уся модель живе в одній вкладці.