Взлом многоалфавитных шифров

adm  •  15 April, 2008

Шифр Гронсфельда вскрывается довольно легко, если учесть следующее обстоятельство: так как цифр всего 10, то имеется лишь 10 вариантов прочтения каждой буквы. Выпишем их столбцами так, что одной строке соответствуют буквы одного значения ключа. Номер варианта будет определяться цифрой ключа от 0 до 9. При этом получим таблицу, правильно выбрав по одной букве из каждой колонки которой можно получить исходный текст:


ключ ???????????????????
вариант 0 ФПЖИСЬИОССАХИЛФИУСС
вариант 1 УОЕЗРЫЗНРР ФЗКУЗТРР
вариант 2 ТНДЖПЪЖМППЯУЖЙТЖСПП
вариант 3 СМГЕОЩЕЛООЮТЕИСЕРОО
вариант 4 РЛВДНШДКННЭСДЗРДПНН
вариант 5 ПКБГМЧГЙММЬРГЖПГОММ
вариант 6 ОЙАВЛЦВИЛЛЫПВЕОВНЛЛ
вариант 7 НИ БКХБЗККЪОБДНБМКК
вариант 8 МЗЯАЙФАЖЙЙЩНАГМАЛЙЙ
вариант 9 ЛЖЮ ИУ ЕИИШМ ВЛ КИИ
сообщение ???????????????????


Предположение 1.

Если прочесть исходный текст напрямую не удалось, то попробуем немного порассуждать. Самый частый символ текста - пробел, а разбиение фразы на слова порой может оказать большую помощь в расшифровке, как это уже было в случае вскрытия шифра решетки. Так как длина шифровки равна 19 символам, то она состоит из двух или трех слов, разделенных пробелами. Хорошее положение для пробела дает лишь вариант 1, а другие варианты, 7 и 9 или их сочетания маловероятны. Поэтому будем считать, что текст шифровки разбивается на два слова: ФПХИСЫЮСС ХИЛФИУСС. Из этого следует, что в 11 позиции текста стоит пробел и в той же позиции ключа находится цифра 1.

Предположение 2.

У выделенных слов шифровки одинаковое окончание ее, и, весьма вероятно, что период ключа делит 9 - длину второго слова вместе с пробелом. Будем считать, что в этом случае одинаковые окончания слов (Одинаковые окончания часто появляются из-за согласования слов в предложениях на русском языке. Это хорошо видно в поговорках: одИН в поле не воИН, наняЛСЯ - продаЛСЯ.) текста попали на одинаковые участки ключа и дали одинаковые символы шифровки. На первый взгляд может показаться, что это слишком маловероятно, чтобы встречаться в практике. Однако таких находок, помогающих расшифровке, всегда бывает предостаточно в сообщениях большой длины и, порой, приходится жалеть скорее об их обилии, чем отсутствии. Если нет никаких идей о длине ключа, не беда - ее можно подобрать вслепую. Итак, есть два выбора для периода ключа: 3 и 9. Попробуем период длины 3:
ключ ?1??1??1??1??1??1??
вариант 0 Ф ЖИ ЬИ СС ХИ ФИ СС
вариант 1 УОЕЗРЫЗНРР ФЗКУЗТРР
вариант 2 Т ДЖ ЪЖ ПП УЖ ТЖ ПП
вариант 3 С ГЕ ЩЕ ОО ТЕ СЕ ОО
вариант 4 Р БД ШД НН СД РД НН
вариант 5 П БГ ЧГ ММ РГ ПГ ММ
вариант 6 О АВ ЦБ ЛЛ ПВ ОВ ЛЛ
вариант 7 Н Б ХБ КК ОБ НБ КК
вариант 8 М ЯА ФА ЙЙ НА МА ЙЙ
вариант 9 Л Ю У ИИ МЛ ИИ
сообщение ?о??р??н?? ??к??т??

Таблица существенно поредела, но остается все-таки сложной для непосредственного прочтения (Криптоаналитики вряд ли сочтут прямое чтение ее сложным, так как достаточно перебрать лишь 100 вариантов для двух оставшихся цифр ключа вручную за несколько минут.). Поэтому попробуем подобрать символ ключа, стоящий в первой позиции, перебрав 10 вариантов. Так как ключ длиной 3 циклически повторяется, то этот же символ стоит в 4, 7, 10, 13, 16 и 19 позициях ключа. Вероятность варианта для первой цифры ключа равна произведению вероятностей биграмм, состоящих из символа по этому варианту расшифровки и следующего за ним, уже известного символа. Если Li - буква текста, стоящая на месте i, то вероятность одного из 10 вариантов:

р (L1L2) p(L4L5) р(L7L8) p(L10L11) p(L13L14) p(L16L17)

Для вычисления вероятности биграмм воспользуемся таблицей из приложения. Поскольку в ней даны логарифмы вероятностей биграмм, то их достаточно суммировать. В результате для вариантов от 0 до 3 имеем такие численные значения вероятностей:

р(0)=р(ФО)р(ИР)р(ИН)р(С )р(ИК)р(ИТ)=43
р(1)=р(УО)р(ЗР)р(ЗН)р(Р )р(ЗК)р(ЗТ)=23
р(2)=р(ТО)р(ЖР)р(ЖН)р(П )р(ЖК)р(ЖТ)=27
р(3)=р(СО)р(ЕР)р(ЕН)р(О )р(ЕК)р(ЕТ)=50

В результате для первой цифры ключа получается наиболее вероятным 3 вариант расшифровки. Это дает следующую таблицу:

ключ 31?31?31?31?31?31?3
вариант 0 Ж Ь С Х Ф С
вариант 1 ОЕ РЫ HP Ф КУ ТР
вариант 2 Д Ъ П У Т П
вариант 3 С ГЕ ЩЕ ОО ТЕ С ОО
вариант 4 в т н с р н
вариант 5 Б Ч М Р П М
вариант 6 А Ц Л П О Л
вариант 7 Х К О Н К
вариант 8 Я Ф Й Н М Й
вариант 9 Ю У И М Л И
сообщение СО?ЕР?ЕН?0 ?ЕК?РТ?0


Теперь сообщение читается совсем просто. Достаточно выбрать одну из 10 строк с вариантом для 3 цифры ключа. В результате получим ключ и текст сообщения:
сообщение: СОВЕРШЕННО СЕКРЕТНО
ключ: 3143143143143143143

В принципе есть возможность чтения шифра Гронсфельда напрямую, анализом таблицы возможных замен, даже если ключ длинный. При достаточно большой длине текста в таблице будут несложно прочитываемые участки. Использование ЭВМ для подключения к криптографической атаке на этот шифр априорных знаний о чередовании русских букв в тексте обычно позволяет без труда читать подобные шифровки.

При многоалфавитной замене с длинным ключом использованный для взлома шифра Гронсфельда прием уже не подходит. Однако известно, что шифры русских революционеров цифирная палата легко читала. Как же это удавалось сделать - черная магия? Все гораздо проще. Приведем короткий пример: перехвачена шифровка, вероятным автором которой является Троцкий. Известно также, что аналогичные шифровки делались методом сложной замены и в качестве ключа использовались тексты революционных песен, а иногда стихотворения Пушкина, Лермонтова и Некрасова. Так как отправитель Троцкий, то естественно предположить, что сообщение оканчивается подписью ТРОЦКИЙ с предыдущим пробелом. Подставив ее в шифровку вместо ключа, получим кусок настоящего ключа.

Шифровка ДДЯ Л ЫСЫ ШНМРКЮЮЩДБЬИЬМЫМТАНЭХЦК
Сообщение ????????????????????????? ТРОЦКИЙ
Ключ ?????????????????????????НАС ЗЛОБ

Не напоминает ли фрагмент НАС ЗЛОБ какойто известный текст? Не правда ли, очень похоже на слова, переведенной Кржижановским песни польского восстания 1863 года, называемой "Варшавянкой"? Теперь, подставив разгаданный ключ в виде текста песни: ВИХРИ ВРАЖДЕБНЫЕ ВЕЮТ НАД НАМИ ТЕМНЫЕ СИЛЫ НАС ЗЛОБ, можно вскpыть само сообщение:

ОБЫВАТЕЛИ СПАЛИ НЕ ЗНАЯ ЧТО МЕНЯЕТСЯ
ВЛАСТЬ ТРОЦКИЙ

Такая расшифровка вряд ли заняла бы вместе с составлением сопроводительной записки более часа времени. Ну, а предположим, что отправитель неизвестен? И это не беда, хотя потребует больше времени. Несложно перебрать несколько возможных имен, а в случае неудачи придется подставлять в разные места часто употребляемые слова текста и ключа - ТОВАРИЩ, ВЛАСТЬ, ВОССТАНИЕ. Отгадав одно из двух - текст или ключ, сразу получим второе. Вот как немцы описали вскрытие ручных шифров советской группы шпионов "Красная Капелла", полностью уничтожить которую Мюллер, Канарис и Шелленберг не смогли, несмотря на многие аресты ее участников с начала и до конца войны: "Тем временем математический отдел разведки и служба расшифровки Главного командования вермахта лихорадочно работала над найденным в особняке наполовину обуглившимся обрывком зашифрованного текста радиопередачи. Они пришли к выводу, что ключ к шифру находится в тексте какой-то французской книги (Язык сообщения и тип шифра стали известны после того, как арестованная бельгийская консьержка на допросах сообщила о пристрастии агентов "Красной Капеллы" к чтению французских романов, часть названий которых она вспомнила.). Из крошечного обрывка сожженного листка бумаги специалисты после кропотливых исследований сумели реконструировать слово ПРОКТОР. Теперь, следовало выяснить, в каких книгах встречается это ключевое слово. Через три месяца мы разыскали эту книгу. Тогда специалисты отдела расшифровки Главного командования вермахта принялись за работу, чтобы раскусить шифр. Они смогли расшифровать обнаруженные в Брюсселе и перехваченные заново радиопередачи."

Еще один короткий пример вскрытия многоалфавитного шифра замены приведем из-за его занимательной истории. Писатель Эдгар По считал себя непревзойденным криптоаналитиком. Ему принадлежит дерзкое высказывание: ".можно смело утверждать, что человеческий гений не в силах составить шифр, раскрыть который оказалось бы не под силу человеческому гению". Поэтому в 1839 году он бросил вызов читателям Журнала "Alexander's Weekly Messenger", утверждая, что расколет любой их шифр замены. Некто Калп в 1840 году прислал ему такой текст шифровки:

GE JEASGDXV, ZIJ GL MW, LAAM, XZY. . .

Эдгар По, предполагавший, что будет предложен шифр простой замены, счел пример Калпа "мешаниной случайных букв". Однако в 1975 году слушатели лекций по криптологии Винкель и Листер расшифровали его, предположив многоалфавитную замену вместо простой. Скорее всего они начали с первых двух слов, увидев в них искаженное имя получателя ALEXANDER как ALXANDER:

Шифpовка GE JEASGDXV
Сообщение MR ALXANDER
Ключ UN JTDSTATE

Полученная частная расшифровка была очень похожа на фразу UNITED STATES и, повторяя ее циклически, они вскрыли весь текст шифровки. Стало ясно, что даже если бы дилетант По и знал о многоалфавитных шифрах, то взламывание текста-шифровки Калпа представляло собой серьезную задачу: одна буква в шифровке была пропущена, а 15 искажены скорее всего по вине наборщика. Этот пример показывает, что ошибки в шифровании способны озадачить не только криптоаналитика, но и легального получателя сообщения, обладающего ключом. Ведь из-за пропущенной пятой буквы текста шифровки весь ее остаток был нечитаемым!

Комментарии

Нет комментариев. Вы можете быть первым!

Оставить комментарий


Warning: Parameter 1 to NP_Captcha::event_FormExtra() expected to be a reference, value given in /home/bh52645/public_html/hacktheplanet.ru/nucleus/libs/MANAGER.php on line 370