Контрольное задание

1. Ознакомиться с примером дешифрования шифра простой замены, приведенным в методических указаниях.

2. Дешифровать выданный преподавателем шифртекст, зашифрованный методом простой замены. Оформить и сдать преподавателю результаты работы в табличном виде по следующей форме:

Наименование шифра:…………………………………………

Шифртекст:……………………………………………………..

Ключ……………………………………………………………

Открытый текст……………………………………………….

Тема 6 Вскрытие многоалфавитных шифров.

Цель занятия: ознакомление с методами дешифрования многоалфавитных шифров перестановки

Шифр Гронсфельда вскрывается довольно легко, если учесть следующее обстоятельство: так как цифр всего 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

л

ю

у

и

и

м

л

и

И

сообщение

?

о

?

?

р

?

?

н

?

?

?

?

к

?

?

Т

?

?

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

(1₁1₂;) P(1₄1₅) P (1₇1₈)Р(1₁₀1₁₁)P(1₁₃1₁₄)P(1₁₆1₁₇)

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

р(0)=р(ФО)Р(ИР)Р(ИН)р(С)p(ИТ)=43

р(1)=р(УО)Р(ЭР)р(ЗН)р(Р )p(ЗК)p(ЗТ)=23

р(2)=р(ТО)Р(ЖР)р(ЖН)р(П )p(ЖК)p(ЖТ)=27

р (3) =р(СО)Р(ЕР)Р(ЕН)р(О)p(ЕК)p(ЕТ)=50

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

Ключ

3

1

?

3

1

?

3

1

?

3

1

?

3

1

?

3

1

?

3

Вариант 0

ж

ь

с

х

ф

С

Вариант 1

о

е

р

ы

н

р

ф

к

у

т

Р

Вариант 2

д

ъ

п

у

т

П

Вариант 3

с

г

е

щ

е

о

о

т

е

с

е

о

О

Вариант 4

в

ш

н

с

р

Н

Вариант 5

б

ч

м

р

п

М

Вариант 6

а

ц

л

п

о

Л

Вариант 7

х

к

о

н

К

Вариант 8

я

ф

й

н

м

Й

Вариант 9

ю

у

и

м

л

И

сообщение

с

о

?

е

р

?

е

н

?

о

?

е

к

?

е

т

о

?

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

сообщение	с	о	в	е	р	ш	е	н	н	о		с	е	к	р	е	т	н	О
Ключ	3	1	4	3	1	4	3	1	4	3	1	4	3	1	4	3	1	4	3

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

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

Шифровка ДДЯ Л ЫСЫ ШНМРКЮЮПЩБЬИЬМЫМТАНЭХЦК

Сообщение ????????????????????????? ТРОЦКИЙ

Ключ ????????????????????????? НАС ЗЛ О Б

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

ВЛАСТЬ ТРОЦКИЙ

Такая расшифровка вряд ли заняла бы вместе с составлением сопроводительной записки более часа времени. Ну, а предположим, что отправитель неизвестен? И это не беда, хотя потребует больше времени. Несложно перебрать несколько возможных имен, а в случае неудачи придется подставлять в разные места часто употребляемые слова текста и ключа — ТОВАРИЩ, ВЛАСТЬ, ВОССТАНИЕ. Отгадав одно из двух — текст или ключ, сразу получим второе.

Вот как немцы описали вскрытие ручных шифров советской группы шпионов "Красная Капелла", полностью уничтожить которую Мюллер, Канарис и Шелленберг не смогли, несмотря на многие аресты ее участников с начала и до конца войны;" Тем временем математический отдел разведки и служба дешифровки Главного командования вермахта лихорадочно работала над найденным в особ­няке наполовину обуглившимся обрывком зашифрованного текста радиопередачи. Они пришли к выводу, что ключ к шифру находится в тексте какой-то французской книги¹. Из крошечного обрывка сожженного листка бумаги специалисты после кропотливых исследований сумели реконструировать слово ПРОКТОР. Теперь, следовало выяснить, в каких книгах встречается это ключевое слово. Через три месяца мы разыскали эту книгу. Тогда специалисты отдела расшифровки Главного командования вермахта принялись за работу, чтобы раскусить шифр. Они смогли расшифровать обнаруженные в Брюсселе и перехваченные заново радиопередачи."

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

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

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

Шифровка GE JEASGDXV

Сообщение MR ALXANDER

Ключ UN JTDSTATE

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

Попробуем теперь сделать выводы из рассмотренных примеров: что помогает и что мешает раскалыванию шифров. Помогает криптографической атаке на шифр в основном то обстоятельство, что буквы и слова в тексте взаимосвязаны. Так, например, было несложно отгадать слово АК-КУ?А?НО и даже по фрагменту НАС ЗЛОБ определить песню, откуда он взят. Такая внутренняя зависимость участков текста друг от друга — свойство естественного языка и от него никуда не денешься. Хотя были и есть языки с гораздо меньшей зависимостью, чем у русского языка, но не заставишь же их использовать для того, чтобы ре­шить проблемы шифрования. Другой помощник криптоаналитика — малое число вариантов соответствия текста шифровке при незнании ключа. Так в шифре Гронсфельда букве шифровки могут соответствовать лишь 10 букв из текста, а в шифре перестановки бит и того меньше, в среднем 7. Способствует вскрытию шифра и малая длина ключа — вряд ли так легко мы разделались бы с шифром Гронсфельда, если длина ключа превышала длину сообщения. И, в конце концов, почему же так просто был вскрыт многоалфавитный шифр замены? Ведь у него и число вариантов для отгадывания было велико, и ключ длинный. Причина успеха его взлома заключается в сильной зависимости ключа, текста и шифровки меж собой. Шифровка известна всегда. Поэтому сначала, мы угадали кусок текста и сразу же за это в награду получили кусок ключа. По этому куску ключа удалось восстановить весь ключ целиком.

Итак, во-первых, если кусок ключа можно было получить, отгадав лишь очень большую часть текста или перебрав множество вариантов, то этот номер не прошел бы. Во-вторых, это не дело, когда по малому участку ключа удается угадать весь ключ. Будь ключ представлен не осмысленным текстом, а случайным, то этого не удалось бы. Во всех современных системах шифрования открытый текст обязательно сжимается перед шифрованием. Сжимать шифрованный текст слишком поздно, так как шифровки почти несжимаемы. Кроме экономии места под хранение и времени передачи, сжатие еще и повышает стойкость шифра. Многие атаки на шифр осуществляются поиском фрагмента открытого текста в шифровке. Если отрытый текст перед шифрованием был сжат, то эти атаки затруднены и потери времени на сжатие окупаются.

Теперь давайте пофантазируем, как составить нераскрываемый шифр. Если мы возьмем за основу многоалфавитный шифр замены, то это будет неплохой выбор, он многовариантен и к нему так просто не подступишься. Однако ключ для шифров­ки должен быть очень хорош: бесконечной длины и, конечно же, несмысловой. Можно схитрить и составить ключ из текста, беря из него лишь каждую третью букву, ведь по фрагменту ДНВТДМИН никогда не скажешь, что он взят из той же "Варшавянки". Еще лучше, если сообщение зашифровано дважды разными ключами и шифрами разных типов. Да­лее, скверно, когда символы всегда находятся в том же месте в шифровке, что и в сообщении — на подпись, заголовок или другой известный фраг­мент текста может начаться атака. Поэтому вместе с заменой применим простой шифр двойной пере­становки — пусть взломщики поищут, где теперь находится подпись. Таким способом, комбинируя шифр перестановки с многоалфавитным шифром замены при хорошем ключе, можно получить вполне приемлемый ручной шифр, вскрыть который будет очень непросто или вообще невозможно.

Но необходимо предостеречь от одной широко распространенной ошибки. Насколько осложнится вскрытие сообщения, если его зашифровать несколько раз одним ключом? Ответ естественный, хотя для многих и неожиданный, взлом вряд ли станет сложнее. Во времена Второй мировой войны английским криптографам не давал покоя простой немецкий полицейский шифр. Из-за краткости сообщений его чтение удавалось далеко не всегда и, как правило, с большими трудностями. Немецкие криптографы об этом не знали, решив улучшить шифр, как бы удвоив примененный ключ. Так вот, после такого "усложнения" вскрытие шифровок стало легким и приятным. В аналогичном случае, имевшем место некогда в известной фирме, текст был зашифрован дважды. Шифровка криптоаналитиком была восстановлена из свободных кластеров на рабочей дискете, а в директории остались следы от двойного шифрования и длины двух файлов типа bak того же сообщения. Из этих следов и сопоставления длин шифровки с длинами файлов стало ясно, что текст зашифрован дважды. По заголовку файла была определена программа шифрования. Так как во второй раз был зашифрован и текст сообщения, и заголовок файла шифровки, содержание которого отчасти известно, то найти второй ключ удалось просто подбором, потому что он был всего из 5 букв по имени владельца. Первый ключ был угадан после этого сразу же, так как стало ясно пристрастие автора файла к собственному имени. Из этого следует правило, никогда не шифровать одно сообщение дважды одним и тем же ключом. Применение нескольких разных ключей порой оправдано, если не из-за увеличения стойкости шифра, то хотя бы как свидетельство о согласии нескольких отправителей шифровки или одновременном присутствии нужных получателей сообщения.

Лучшие известные криптографические системы, преимущественно принадлежащие правительствам, практически невозможно вскрыть. Однако все государства теми или иными путями пытаются сдержать и даже запретить свободное использование криптографии, как вызывающее головную боль у их секретных служб. В то время, как ЦРУ в США призывает фирмы шире использовать шифрование, то АНБ пытается ограничить длину ключа 40 битами. В последнем случае возможен даже пря­мой перебор ключей, если использовать достаточно мощную ЭВМ. По оценкам специалистов, раскалывание шифра алгоритма RC—4 с ключом из 40 бит, широко используемого в сети Internet, потребует около 100 MIPS³⁶ лет. Раньше считалось, что меньше, чем за 6 месяцев работы суперкомпьютера, такой шифр вскрыт не будет. Эта оценка была проверена практически и оказалось, что 120 рабочих станций с двумя суперкомпьютерами параллельного действия взломали ключ за 8 дней. Цена такого раскалывания достаточно высока и превы­шает $10000, что впрочем сильно зависит от эффективности алгоритма атаки. Поэтому проблемы криптоанализа еще долгое время будут весьма актуальны.