?

Log in

No account? Create an account
 
 
29 December 2016 @ 11:32 pm
Задачка: взлом имперского кода  

Создавая подстановочный шифр «СМЕРД» («смерть джедаям») для имперского флота, криптоаналитики Дарта Вейдера позаботились о том, чтобы закодированный образ буквы зависел от ее позиции в сообщении. Например, первая буква А сообщения могла бы кодироваться в Д, вторая А в Н, третья в К, четвертая снова в Н, пятая в Е и так далее. Ключ, определяющий таблицу преобразования пары (исходная буква, позиция) в закодированную букву, часто менялся, чтобы еще более затруднить расшифровку.

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

Сначала робот C-3PO обнаружил, что имперский код «антирефлексивен»: зашифрованный образ буквы никогда не совпадает с ней самой. Скажем, буква А ни при каком ключе и ни в какой позиции не будет преобразована в букву А. C-3PO привел такой пример: слово СИЛА может зашифроваться, например, в МОЩЬ, но не может превратиться в СВЕТ (С в С) или в ТЬМА (А в А).

Вскоре пришел черед отличиться роботу R2-D2. Анализируя свежий перехват имперского сообщения, он обнаружил, что зашифрованный текст именно этого сообщения обладает одним специальным свойством. Исходя из данного свойства, R2-D2 предположил возможный вариант расшифровки. Правда, коллега C-3PO подверг результат R2-D2 резкой критике за его поверхностность, бездоказательность и нестрогость. Но после того, как Люк Скайуокер перенастроил мотиватор C-3PO на увеличение значимости эвристик и правдоподобных догадок, второй робот согласился, что предположение первого, пусть и не обязательно верное, все же имеет право на существование, хотя бы в качестве смелой гипотезы. Действительно, если исходное сообщение представляет из себя ровно то, о чем подумал R2-D2, то его зашифрованный образ должен был бы обладать тем самым специальным свойством, которому удовлетворял анализируемый перехват.

Позднее среди обломков «Звезды смерти» были обнаружены накопители с архивом всех исходных имперских сообщений и их шифровок. В частности, нашлось и то сообщение, которое расшифровал R2-D2, — оказалось, что робот абсолютно правильно понял это сообщение.

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

Ответ: ЙЙЙЙЙ...ЙЙЙЙЙ, см. разбор задания.

Правильно ответили: fiviol, madam_y и ditour.


 
 
 
fiviol on March 4th, 2017 05:19 pm (UTC)
Ну ты зверь! Все же исхожу из предположения, что раз ты это загадал, то предполагаешь возможность решения задачи, а главное, был бы не против, чтобы ее кто-то решил. :) Тогда стоит попробовать, но нужно сначала уточнить условия:
1. Я правильно понимаю, что закодирован в той или иной мер осмысленный текст на русском языке?
2. Текст состоит из слов, но разбиение текста на слова пробелами не указано (пробелы между группами по пять букв не в счет, они только для удобства)?
3. Фразу "закодированный образ буквы зависел от ее позиции в сообщении" следует читать как "закодированный образ буквы зависел от ее позиции в слове сообщения"?
Иначе это правило совершенно ничего не дает - сообщение всего одно, и все "позиции" в нем разные, поэтому расшифровкой может служить произвольная последовательность букв (единственное ограничение - буквы расшифровки и шифровки должны не совпадать).
4. Подсказка про гипотезу робота R2-D2 содержит только информацию о том, что в шифровке есть некоторая особенность, не бросающаяся в глаза, но которую стоит поискать? Или я как-то эту подсказку недопонял?
(Например, если окажется, что в шифровке нет какой-то буквы - то зашифрованное сообщение состоит только из этой буквы. :))

Ба! Буквы "Й" в шифровке нет! Сдаю:
ЙЙЙЙЙ ... ЙЙЙЙЙ

Edited at 2017-03-04 05:23 pm (UTC)
ogn_slon on March 4th, 2017 06:18 pm (UTC)
ЗАЧЕТ!

Только что ты взломал код знаменитой немецкой шифровальной машины "энигма". Точнее, один из кодов одной из сетей "энигм" на одном из этапов Второй мировой войны. Еще точнее, не взломал код одним этим решением, но сделал существенный шаг ко взлому, и несколько таких шагов в итоге привели к вскрытию кода той конкретной сети. Я постарался приблизительно смоделировать условие одной задачи из серии дешифровальных задач, которые были решены сотрудниками Блечли Парка (британская дешифровальная служба) в 1941 г. В итоге были прочтены секретные радиограммы Оси, и это внесло важный вклад в победу союзников в морском сражении у мыса Матапан. Ты можешь законным образом немного почувствовать себя Аланом Тьюрингом! :)

(На самом деле, я не уверен, что Тьюринг участвовал в дешифровке именно этой серии коммуникаций, -- кажется, именно в этой не участвовал, эта была работа другой дешифровальной команды; но чем-то подобным Тьюринг в Блечли Парке занимался, и очень успешно, -- вне всяких сомнений. Я потом, если соберусь с силами, напишу пост об этом, тема того стоит.)
madam_y on March 6th, 2017 12:00 am (UTC)
Ййййй.....ййййй
ogn_slon on March 6th, 2017 07:47 am (UTC)
Верно (по модулю регистра - все буквы должны быть заглавными, но это несущественная деталь).
madam_y on March 6th, 2017 07:52 am (UTC)
Да. (Ночью, с телефона...)
ogn_slon on March 6th, 2017 08:08 am (UTC)
Причина признана уважительной. :)
ditour on March 6th, 2017 06:27 am (UTC)
Если я правильно понял условие, то единственное не зависящее от ключа "специальное свойство", которое приходит в голову, объясняется, скорее всего, отсутствием в русской раскладке для имперской клавиатуры буквы "й" ;)))
ogn_slon on March 6th, 2017 07:52 am (UTC)
Типа того, да. То есть, как минимум, направление мысли верное.

Традиция спортивных интеллектуальных игр "Что? Где? Когда?" требует "удерживать форму вопроса" - то есть ответ ожидается в той форме, в которой он запрашивался, чтобы не было сомнений, что все правильно понято и решено. У нас тут, конечно, не спортивное "Что? Где? Когда?", но в разгадывании задачек участвуют в том числе и чегекашники, и мы эти спортивные правила стараемся соблюдать. Соответственно:

В качестве ответа следует сдать первую и последнюю пятибуквенные группы расшифрованного сообщения, разделенные многоточием, например: АБВГД...ЕЖЗИЙ.

Итак, развивая и логически завершая вашу мысль, ответом будет?.. :)
ditour on March 6th, 2017 08:44 pm (UTC)
"ЙЙЙЙЙ...ЙЙЙЙЙ" совместимо с шифровкой при любом ключе.
ogn_slon on March 6th, 2017 08:53 pm (UTC)
Верно, зачет. И это -- реальная история, по модулю точности воспоминаний авторши мемуара, которая, с ее слов, дешифровала именно такое сообщение "энигмы" (но алфавит был, конечно, латинский).

Edited at 2017-03-06 10:35 pm (UTC)
ogn_slon on March 6th, 2017 09:08 pm (UTC)
Упс, виноват, был невнимателен. Зачет-то в силе, ваш ответ правильный. Но дополнительное утверждение, которое вы записали после ответа -- не совсем корректно, разумеется, я сразу не обратил внимания. Иначе бы та историческая дешифровка ничего не дала Блечли Парку. :) А на самом деле, если я правильно помню, благодаря той дешифровке была вычислена коммутация одного из роторов "энигмы" -- единственного неизвестного ротора в той сети на тот момент. Чтение последующих сообщений сети стало делом техники. Конечно, мой "руссифицированный" текст шифровки не воспроизводит работу "энигмы" при каком-либо реальном наборе роторов. Но в шифровке из исторического эпизода "энигма" была настоящая, естественно! Я потом постараюсь сделать пост на этот счет, если снова разыщу свои источники.
ditour on March 6th, 2017 09:40 pm (UTC)
Уточню - свойство "отсутствие Й" сохраняется при любом ключе ;)))
ogn_slon on March 6th, 2017 09:53 pm (UTC)
Ок, к такой формулировке претензий, естественно, нет. :)