Криптоанализ шифра Виженера

Шифры Виженера, подобно всем многоалфавитным шифрам, не сохраняют частоту символов. Однако Ева может использовать некоторые методы для того, чтобы расшифровать перехваченный зашифрованный текст. Криптоанализ в данном случае состоит из двух частей: находят длину ключаи потом непосредственно находят ключ.

1. Были изобретены несколько методов, чтобы найти длину ключа. Один метод рассмотрим ниже. В так называемом тесте Казиского (Kasiski)криптоаналитик в зашифрованном тексте ищет повторные сегменты по крайней мере из трех символов. Предположим, что найдены два сегмента, и расстояние между ними d. Криптоаналитик предполагает, что m делит d, где m — длина ключа. Если можно найти больше повторных сегментов с расстоянием d1, d2, …., dn, тогда НОД(d1, d2, …., dn....)/ m. Это предположение логично, потому что если два символа одинаковы и (k = 1, 2...) — символы, выделенные в исходном тексте, то одинаковы и символы, выделенные в зашифрованном тексте. Криптоаналитик использует сегменты по крайней мере из трех символов, чтобы избежать случаев, где символы имеют один и тот же ключ. Пример 4.20 может помочь нам п онять эти рассуждения.

2. После того как длина ключа была найдена, криптоаналитик использует идею, показанную в примере 4.18. Здесь зашифрованный текст делится на m различных частей и применяется метод, используемый в криптоанализе аддитивного шифра, включая атаку частоты. Каждая часть зашифрованного текста может быть расшифрована и соединена с другими, чтобы создать целый исходный текст, другие слова. Весь зашифрованный текст не сохраняет частоту отдельной буквы исходного текста, но каждая часть делает это.

Пример

Предположим, что мы перехватили следующий зашифрованный текст:

LIOMWGFEGGDVWGHHCQUCRHRWAGWIOWQLKGZETKKMEVLWPCZVG'TH VTSGXQOVGCSVETQLTJSUMVWVEUVLXEWSLGFZMVVWLGYHCUSWXQH - KVGSHEEVFLCFDGVSUMPHKIRZDMPHHBVWVWJWIXGFWLTSHGJOUEEHH- VUCFVGOWICQLIJSUXGLW

Тест Казиского на повторение сегментов на три символа приводит к результатам, показанным в таблице 4.4.

Таблица 4.4. Тест Казиского для примера 4.19
Комбинация Первое расстояние Второе расстояние Разность
JSU
SUM
VWV
MPH

Наибольший делитель - 4, что означает длину ключа, пропорциональную 4. Сначала пробуем m = 4. Делим зашифрованный текст на четыре части. Часть C1 состоит из символов 1, 5, 9...; часть C2 состоит из символов 2, 6, 10..., и так далее. Используем статистическую атаку каждой части отдельно. Перебираем расшифровывающиеся части по одному символу одновременно, чтобы получить целый исходный текст.

С1 LWGW CRAO KTEP GTQC TJVU EGVG UQGE CVPR PVJG TJEU GCJG
P1 jueu apym ircn eroa rhts thin ytra hcie ixst hcar rehe
C2 IGGG QHGW GKVC TSOS QSWV WFVY SHSV FSHZ HWWF SOHC OQSL
P2 usss ctsl swho feae ceih cete soec atnp nkhe rhck esex
C3 OFDN URWQ ZKLZ HGVV LUVL SZWH WKHF DUKD HVIW HUHF WLUW
P3 lcae rotn whiw edss irsi irh eteh retl tiid eatr airt
C4 MEVN CWIL EMWV VXGE TMEX LMLC XVEL GMIM BWHL GEVV ITX
P4 iard yseh aisr rtca piaf pwte thec arha esft erec tpt

Если исходный текст не имеет смысла, попробуем с другим m.

В рассматриваемом случае исходный текст имеет смысл (читаем по столбцам).

Julius Caesar used a cryptosystem in his wars, which is now referred to as Caesar chipper. It is an additive chipper with the key set to three. Each character in the plaintext is shift three characters to create ciphertext.

Перевод этого текста приведен ниже.

Юлий Цезарь использовал в своих войнах криптографическую систему, которая упоминается теперь как шифр Цезаря. Это аддитивный шифр с ключом, установленным на три. Каждый символ в исходном тексте сдвинут на три символа, чтобы создать зашифрованный текст.

Частотный анализ

Одним из методов вскрытия шифров является частотный анализ. Распределение букв в криптотексте сравнивается с распределением букв в алфавите исходного сообщения. Буквы с наибольшей частотой в криптотексте заменяются на букву с наибольшей частотой из алфавита. Вероятность успешного вскрытия повышается с увеличением длины криптотекста. Существуют множество различных таблиц о распределении букв в том или ином языке, но ни одна из них не содержит окончательной информации - даже порядок букв может отличаться в различных таблицах. Распределение букв очень сильно зависит от типа теста: проза, разговорный язык, технический язык и т.п.

 

 

Таблицы распределения букв
В русском языке
Буква Частота Буква Частота Буква Частота
а 0.062 л 0.035 ц 0.004
б 0.014 м 0.026 ч 0.012
в 0.038 н 0.053 ш 0.006
г 0.013 о 0.090 щ 0.003
д 0.025 п 0.023 ы 0.016
е 0.072 р 0.040 ъ, ь 0.014
ж 0.007 с 0.045 э 0.003
з 0.016 т 0.053 ю 0.006
и 0.062 у 0.021 я 0.018
й 0.010 ф 0.002 разделитель 0.174
к 0.028 х 0.009    
В английском языке
Буква Частота Буква Частота Буква Частота
a 0.0804 b 0.0154 c 0.0306
d 0.0399 e 0.1251 f 0.0230
g 0.0196 h 0.0549 i 0.0726
j 0.0016 k 0.0067 l 0.0414
m 0.0253 n 0.0709 o 0.0760
p 0.0200 q 0.0011 r 0.0612
s 0.0654 t 0.0925 u 0.0271
v 0.0099 w 0.0192 x 0.0019
y 0.0173 z 0.0009    

 

Используя частотный анализ текста, расшифруйте следующее сообщение: «ТПБЙ АБРЮЙ ЕДТБПРЛМ, ЦРМ Т ЙМОБ ТМАВ ПМИБЛВЮ, В Т ОБЗБ НОБПЛВЮ. НМНОМЯМТВТ ББ ЛВ ТЗСП, ЙМГЛМ МЧСРЕРЫ ЛБ НОМПРМ ЛБНОЕЮРЛЪЖ ТЗСП, В ЛВПРМЮЧСЭ КМОБЦЫ ТМ ОРС. ЦВПРМ АБРЕ ДВАСЙЪТВЭРПЮ ЛВА РБЙ, НМЦБЙС ЙМОБ ПМИБЛМБ, ЗВЗ РСАВ НМНВАВБР ПМИЫ Е МРЗСАВ МЛВ ЯБОБРПЮ?»

Используя частотный анализ текста, расшифруйте следующее сообщение: «ЗЯЗ ГВ НОЕЮРКМ ТЪЖРЕ ЮПКЪЙ БКЁЙ КЯ НОЕОМБС Е КЯПИЯБЕРЫПЮ ФМОМЩЕЙ ТЕБМЙ, НОВЗОЯПКМЖ НМАМБМЖ Е АМИСЛЪЙ КВЛМЙ. ПЯЙМВ ЗОЯПЕТМВ – ЕЙВККМ ИЯДСОКМВ КВЛМ. ЕЙ РЯЗ БЯТКМ ИЭЛСЭРПЮ ИЭБЕ, ЦРМ БЯГВ НОЕБСЙЯИЕ КЯДТЯКЕВ ХТВРЯ, – КВЛВПКМ-АМИСЛМЖ.»

Используя частотный анализ текста, расшифруйте следующее сообщение: «ХЯХХ ДРЛХХЯ –АРНЧЮЭШВЯ СБЗПХ ЁЪРПОВБ РРЗГК, ВЖНЦТОЮХВ ЦАФУМДЫНЯ ШЬЕГЕС. АРЪДЖФТУЯ МТ ГЙЁУФТРРЗЫ ДЦЗЯ-ЦОМСЗАВПДЁЪ РВЙНАР. МЩЗЭЬ ГЕПШГ ЦЧСС НВЧЯЮЯ ХЪНЛ КВТТАМ. ТХКНАПИД ФХХНЛЩЫ СРНЫВЪДЖФТ РТ НУЩРСРЪГР СМЧУЕ, ЕСЦРЭВЯРЙЙШС ООТУ НЕ АНАГ ПО УАЛБУУ ДФЩОДАМЫП. ЬЪУРЗ ОАРДЩЖ ЦЗЧУЧИ ОГЯЪДЖФТ ЕРЯАЩЫХ УЪСУИЗ Ы ЫЕЭГБСФАМТ. УУЁГ МЕНУФТ АХЪЖЭТВВКЧЮЕ ЩЕЯМБ ВДГИНГГШИ Д ВЗЦХ ТЪТЬАДИКОЮАК ТФРВМЗЦ –ЯЦЗУЪКРНДЙЮУЯ Ф ЭЕДЕПТ ТУЖХЪЧПОИ Ы ШЕЕГПНРЙ АЧЬШКСХ, ПРЧСЫ ЯЧЧЗЭНР ПЯЦРГОЛШИ ПА РЧТЙЁ Н ЛКМЕЛДЫУВЦ ЧЕЁНЗЭД Н ЕСЭТЖПДАЮУ ЖРФЖВЮШЫЭНЖВ Ц ЮЕУ, Б ДГУЁСЩУ МАСЁЮЦАСОО НЕГАЩПХ.»