Частотний аналіз (криптологія)

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до: навігація, пошук

Частотний аналіз, частотний криптоаналіз - метод криптоаналізу, який ґрунтується на частоті появи знаків шифротексту. Власне - на припущенні про існування нетривіального статистичного розподілу окремих символів і їх послідовностей як у відкритому тексті, так і в шифротексті, який, з точністю до заміни символів, буде зберігатися в процесі шифрування і дешифрування. Спрощено, частотний аналіз передбачає, що частота появи заданої літери алфавіту в досить довгих текстах одна і та ж для різних текстів однієї мови. При цьому у випадку моноалфавітного шифрування якщо в шифротексті буде символ з аналогічною ймовірністю появи, то можна припустити, що він і є зазначеною зашифрованою буквою. Аналогічні міркування застосовуються до біграм (двобуквених послідовностей), триграм і т.д. у разі поліалфавітного шифрів.

Історія[ред.ред. код]

Метод частотного криптоаналізу відомий з IX-го століття (роботи Ал-Кінді), хоча найвідомішим випадком його застосування в реальному житті, можливо, є дешифровка єгипетських ієрогліфів Ж.-Ф. Шампольон у 1822 році. У художній літературі найвідомішими згадками є оповідання «Золотий жук» Едгара По, «Танцюючі чоловічки» Конан Дойля, а також роман «Діти капітана Гранта» Жюль Верна.

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

Приклад[ред.ред. код]

Припустимо, отримано наступний шифротекст:

nj sdms, ne lebe4cwn6

d6y6 yc de5rki,

76m6h 7n6ls 1rmeje5e,

yc 4jmcvyi drkiw,

oef kcyr 1rmejeleki,

i hyilme, i jmszi

fske 4rhye, fske zsnr,

nj m646 m64szrw.

nj ley676 q sjmcvyr

s 7ryaa dem6

jme4 4emexs... enewhi n

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'nysnr

y6qkrd nrbrd 7ke4ed.

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

e6r4yimcknsjdl7whnf5qv2bzax1pogtu

де "е"- зустрічається 44 рази,"6"-25 раз і т.д.

Еталонна послідовність для української мови виглядає так:

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

Таким чином припускаємо що знак "е" у шифротексті відповідає літері "о" відкритого тексту, "6" відповідає "а", "r" відповідає "н" і т.д.

Отримаємо гаданий відкритий текст:

гс руер, го дойовтпга

уаиа ит уоянкі,

маеаб мгадр шнеосояо,

ит всетжиі ункіп,

ьоз ктин шнеосодокі,

і биідео, і серхі

зрко внбио, зрко хргн,

гс еава еаврхнп.

гс доиама є рсетжин

р мницц уоеа

сеов воеочр... огопбі г

і ктин і яоен -

вма доснир і докнир

бо мтуояо зоят

уокнгнмг…

дойовтпга гт вмгтвтпга,

стпбтин доевіга

і ветчої єкої сеов'ї

вокї осеодіга.

і уаиа в мау'ж вакнсіп,

в мау'ж вокщиіп, иовіп,

иа єтзрбщга доу'гиргн

иаєкну гнйну мковоу.

Як бачимо, він все одно не читається.

Вихід

Існують декілька шляхів виходу з такого становища:

1. Переставляти знаки послідовності доти, доки не отримаємо осмислений відкритий текст. На сучасних комп'ютерах це легко реалізується, але потребує великої кількості обчислень, що не раціонально. (скажімо необхідно переставити 15 символів, що потребує 15 ! операцій (порядок 1012)).

2. Метод словника. Ефективніший метод ніж попередній. Полягає в тому, що вибирається слово і перевіряються поєднані з ним слова. Наприклад, слово "дойовтпга" (4 те слово). Якщо припустити, що літери "о" та "в" вибрані правильно, залишається знайти в словнику слово яке містить 2 та 4-ту літери "о" та 5-ту літеру "в": " *о*ов**** ", таких слів буде небагато. Знайшовши це слово, отримуємо більше літер, які використовуємо для наступних слів.

Література[ред.ред. код]

  • С.Коутинхо. Введение в теорию чисел. Алгоритм RSA. Москва: Постмаркет, 2001. - 328 с.

Посилання[ред.ред. код]

Частотний криптоаналіз