Частотний аналіз (криптологія)
Частотний аналіз, частотний криптоаналіз — метод криптоаналізу, який ґрунтується на частоті появи знаків шифротексту. Власне — на припущенні про існування нетривіального статистичного розподілу окремих символів і їх послідовностей як у відкритому тексті, так і в шифротексті, який, з точністю до заміни символів, буде зберігатися в процесі шифрування і дешифрування. Спрощено, частотний аналіз передбачає, що частота появи заданої літери алфавіту в досить довгих текстах одна і та ж для різних текстів однієї мови. При цьому у випадку моноалфавітного шифрування якщо в шифротексті буде символ з аналогічною ймовірністю появи, то можна припустити, що він і є зазначеною зашифрованою буквою. Аналогічні міркування застосовуються до біграм (двобуквених послідовностей), триграм і т.д. у разі поліалфавітного шифрів.
Історія
Метод частотного криптоаналізу відомий з IX-го століття (роботи Аль-Кінді), хоча найвідомішим випадком його застосування в реальному житті, можливо, є дешифровка єгипетських ієрогліфів Жаном-Франсуа Шампольйоном у 1822 році. У художній літературі найвідомішими згадками є оповідання «Золотий жук» Едгара По, «Танцюючі чоловічки» Конан Дойля, а також роман «Діти капітана Гранта» Жюль Верна.
Починаючи з середини XX століття більшість використовуваних алгоритмів шифрування розробляються стійкими до частотного криптоаналізу, тому він застосовується, в основному, для навчання.
Приклад
Припустимо, отримано наступний шифротекст:
3j sdms, ne lebe4cwn6
d6y6 yc de5rki,
76m6h 7n6ls 1rmeje5e,
yc 4jmcvyi drkiw,
oef kcyr 1rmejeleki,
i hyilme, i jmszi
fske 4rhye, fske zsnr,
3j m646 m64szrw.
3j ley676 q sjmcvyr
s 7ryaa dem6
jme4 4emexs... enewhi 3
i kcyr i 5emr -
476 lejrys i lekrys
he 7cde5e fe5c
dekrnr7n…
lebe4cwn6 nc 47nc4cwn6,
jcwhcyr lem4in6
i 4mcxe2 qke2 jme4'2
4ek2 ejmelin6.
i d6y6 4 76d'v 46krjiw,
4 76d'v 4ekpyiw, ye4iw,
y6 qcfshpn6 led'3ysnr
y6qkrd nrbrd 7ke4ed.
Полічивши повторення кожного знака та відсортувавши за спаданням, отримаємо послідовність:
e6r4yimcknsjdl7wh3f5qv2bzax1pogtu ,
де "е"- зустрічається 44 рази,"6"-25 раз і т.д.
Еталонна послідовність для української мови виглядає так:
оанвиіетклрсудмпбгзяєжїйхцчшщьюф.
Таким чином припускаємо, що знак "е" у шифротексті відповідає літері "о" відкритого тексту, "6" відповідає "а", "r" відповідає "н" і т.д.
Отримаємо гаданий відкритий текст:
гс руер, ло дойовтпла
уаиа ит уоянкі,
маеаб младр шнеосояо,
ит всетжиі ункіп,
ьоз ктин шнеосодокі,
і биідео, і серхі
зрко внбио, зрко хрлн,
гс еава еаврхнп.
гс доиама є рсетжин
р мницц уоеа
сеов воеочр... огопбі г
і ктин і яоен -
вма доснир і докнир
бо мтуояо зоят
уокнлнмг…
дойовтпла лт вмлтвтпла,
стпбтин доевіла
і ветчої єкої сеов'ї
вокї осеоділа.
і уаиа в мау'ж вакнсіп,
в мау'ж вокщиіп, иовіп,
иа єтзрбщла доу'гирлн
иаєкну лнйну мковоу.
Як бачимо, він все одно не читається.
Вихід
Існують декілька шляхів виходу з такого становища:
1. Переставляти знаки послідовності доти, доки не отримаємо осмислений відкритий текст. На сучасних комп'ютерах це легко реалізується, але потребує великої кількості обчислень, що не раціонально. (скажімо необхідно переставити 15 символів, що потребує 15 ! операцій (порядок 1012)).
2. Метод словника. Ефективніший метод ніж попередній. Полягає в тому, що вибирається слово і перевіряються поєднані з ним слова. Наприклад, слово "дойовтпга" (4 те слово). Якщо припустити, що літери "о" та "в" вибрані правильно, залишається знайти в словнику слово яке містить 2 та 4-ту літери "о" та 5-ту літеру "в": " *о*ов**** ", таких слів буде небагато. Знайшовши це слово, отримуємо більше літер, які використовуємо для наступних слів.
Література
- С.Коутинхо. Введение в теорию чисел. Алгоритм RSA. Москва: Постмаркет, 2001. - 328 с.