Rasterschlüssel 44

Rasterschlüssel 44 (RS44) (от  — сетка, растр и Schlüssel — ключ) — ручная техника шифрования, заменившая применявшийся прежде шифр «двойной квадрат» (). RS 44 использовался вооружёнными силами нацистской Германии, начиная с марта 1944 года.

История 
Шифр использовался низшим командованием вермахта, ввиду того, что оно не имело в распоряжении никакой шифровальной машины, в отличие от среднего и высшего командования (штабы дивизий и выше), которое пользовалось Энигмой. Для низшего командования, включавшего в себя штабы рот и батальонов и находящегося в основном на командно-наблюдательных пунктах, было необходимо применять технику шифрования текста вручную — «карандашом на бумаге». С 1941 года в сухопутных войсках стали применять шифровальную технику двойных квадратов. Ввиду постоянно угрожающей опасности вторжения с Запада, укрепляющегося осознания угрозы и необходимости иметь возможность обмениваться секретными сведениями с командно-наблюдательными пунктами, по приказу Шифровального Центра вермахта 27 марта 1944 года в сухопутных и воздушных войсках был внедрён RS 44. Начиная с 18 октября того же года, был внедрён упрощённый RS 44. Процедура была необходимой в силу того, что прежние инструкции толковались двояко, служащие допускали слишком много ошибок при шифровании, а радисты — при передаче сообщения.

Над взломом шифра в Блетчли-парке работало в разное время до 150 человек. В нём криптоаналитик Джон Тилтман прочитал десятидневный курс об уязвимостях и подходах к дешифрованию RS44. Так, по захваченным шаблонам британцам требовалось не больше часа, чтобы найти начальную клетку, оставшаяся часть расшифровывалась по рассказанному алгоритму. В августе 1944 года пришел первый успех: удалось восстановить однодневный шаблон и дешифровать 30 сообщений, присланных за сутки. Однако не всегда получалось уложиться в требуемые сроки, и информация теряла свою актуальность. В среднем, было необходимо две недели на успешную дешифровку сообщения. Американские коллеги выделили 20 служащих для взлома RS44, что было недостаточно для потока из тысячи сообщений в сутки. Таким образом считалось, что шифр нельзя взломать, пока передающая сторона не допустит ошибки, снижающей его криптостойкость.

Описание RS44

Заголовок 
Заголовок зашифрованного сообщения содержал в себе время отправления в формате ЧЧ:ММ, затем шло количество символов в сообщении — от 60 до 200, и завершал заголовок индикатор, то есть четыре неповторяющихся буквы латинского алфавита.

В случае превышения лимита символов, сообщение полагалось разбить на два независимых зашифрованных сообщения. Если же сообщение содержало меньше 60 символов, в него добавляли случайное слово (Wahlwort) или несколько слов. Чтобы отделить это слово от содержательной части послания, две последних буквы в предшествующем слове и две первых буквы в последующем по отдельности дублировались. Например, Tanneenn Das ist die geheime Nachricht ggeehen, где строка Das ist die geheime Nachricht была секретным сообщением, Tannen и gehen — случайными словами, которые перешли в Tanneenn и ggeehen соответственно.

Четыре буквы в конце заголовка являлись двумя зашифрованными и случайно выбранными биграммами, составленными из букв a, b, c, d, e. Биграммы шифровались при помощи вспомогательной таблички под решеткой (см. таблицу 1).

Каждая буква из биграммы заменялась на любую из пяти, стоящих в соответствующем столбце. Если буквы в биграммах повторялись, по тем же правилам бралась другая буква, отличная от уже взятой. На самом деле, при шифровании биграмм caeb можно взять fpgu, равно как и jmwv. Если необходимо зашифровать bddd, то можно выбрать uxln или hbrx и т. д.

При декодировании по вспомогательной табличке биграммы однозначно восстанавливаются. Таким образом, заголовок мог представлять собой строку 1804 — 113 — fpgu, что обозначало время отправки сообщения (18:04), количество символов в шифрограмме (113), тип зашифрованной биграммы (caeb).

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

Буквосочетания «ck» и «ch» заменялись на «q», умлауты тоже заменялись: ä — «ae», Ö — «oe», Ü — «ue», ß — «sz».

Цифры записывались полными немецкими словами, за исключением 2 — «zwo», а не «zwei».

Римские цифры обозначились приставкой «roem». Например, IV — «roemeinsfuenf».

Числительные назывались по цифре, исключения составляли следующие числа:

10, 11, 20, 30, 40, 50, 60 ,70 ,80, 90, 100, 1000 — писались в соответствии с оговорёнными правилами написания букв и буквосочетаний.

12 уже писалось как «eins zwo», 0850 — «nullaqtfuenfnull».

Если стояло больше одного нуля подряд, то происходила замена 00 — «zenta», 000 — «mille», 0000 — «miria». Например, 800 000 — «aqtzentamille или aqtmillezenta».

Знаки пунктуации следовало заменять следующими словами:
 кавычки (Klammer) — «klam»;

 вопросительный знак (Fragezeichen) — «fraq»;

 запятая (Komma) — «koma»;

 точка (Punkt) — «stop».
Пробел — «x» — использовался только в целях однозначно определить написанное или при необходимости записать время. В этом случае следовало разделять часы и минуты символом «x». Во всех остальных случаях текст шифровался без промежутков.

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

Шифрование сообщения

Выбор начальной клетки 

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

Структура трафарета 
Служащие, которые должны были шифровать текст, получали шаблонный трафарет, который заменяли ежедневно. Трафареты выдавались партиями по 31-32 штуки на следующий месяц в середине текущего, однако напрямую служащим они попадали в руки в день (в крайнем случае за день до) отправки сообщения. Трафарет состоял из 25 столбцов и 24 строк. Каждая строчка должна была содержать ровно 10 пустых клеток, расположенных случайно. Строчки нельзя было повторять, равно как и столбцы. Оставшиеся клетки полностью закрашивались. Подготовленный текст сообщения вписывался только в белые клетки, слева направо. Начальная клетка была зашифрована в биграмме заголовка сообщения. В случае, если начальная клетка оказывалась чёрной, запись начинались с ближайшей правой белой клетки трафарета. Если текст сообщения доходил до конца трафарета, то его продолжение нужно было писать начиная с самой первой пустой клетки сверху.

Составление итоговой шифрограммы 
Начальная колонка (пронумерованный столбец в трафарете) служила индикатором того, откуда после нанесения текста на трафарет следовало начинать списывать символы в итоговое сообщение. За её номер отвечали две цифры часов отправки сообщения. Возьмём указанный ранее заголовок:

1804—113 — fpgu

Очевидно, номер начальной колонки — 18. Далее необходимо отсчитать вправо от указанного столбца количество столбцов, равное следующей сумме: это сумма цифр минут и количества символов сообщения. Для упомянутого заголовка посчитаем: (0+4) + (1+1+3) = 9. Двигаемся от 18 колонки на 9 позиций вправо, учитывая, что 18-я колонка отвечает за «раз». Таким образом, попадаем в колонку 24, и с этого столбца списываем сверху вниз буквы. Так и списывается, сначала 24-я колонка, потом 25-я, а затем пишется с 1-й по 23-ю.

Итоговое зашифрованное сообщение составлялось из блоков по пять букв.

После изменений от 18 октября 1944 года, вместо числа, отвечающего за часы отправки, в качестве определяющего начальную колонку стали использовать дополнительную. Она записывалась в конце заголовка.

Шифрование сообщения
Пусть текстом исходного сообщения является следующее:

 Panzervormarsch bei Prochorowka beginnt am 1. September um 2:00 Uhr. Artilleriebeschuß ist erwartet

(перевод: Танковое наступление под Прохоровкой начинается первого сентября в два часа ночи. Ожидается артобстрел)

Выполняем подготовку текста, заменяем 'ch' на 'q', '2' на 'zwo', 'ß''' на 'sz', ставим 'x' между часами и минутами, точку заменяем на 'stop'. Теперь шифруем название места 'Prochorowka' по специальной табличке:

Получаем:

 panzervormarsq bei aa tqexkeqeglz tqexkeqeglz ee beginnt am ersten September um zwo x zenta uhr stop Artilleriebesqusz ist erwartet

Так как ячейка caeb — чёрная, двигаемся вправо до deeb. Начиная с этой ячейки вписываем подготовленный текст. Так доходим до крайней правой нижней cbec, и затем продолжаем сверху, с dacb. Таким образом, последняя буква попадает в aaae. Теперь вспоминаем номер начальной колонки — 18+9 = 24, и списываем со столбца 24 все буквы, начиная с верхней. Повторяем с 25-й, затем 1-я, 2-я и так до 23-й.

Последний шаг — разбиваем на группы по 5 букв:

Остается записать заголовок и зашифрованное сообщение готово.

 Расшифровка сообщения
Смотрим в заголовок:
 18:04 113 fpgu

При помощи вспомогательной таблицы 1, fpgu однозначно дает caeb. На трафарете ищется эта ячейка, и начиная с ближайшей правой пустой отсчитывается 113 ячеек. Так как ячеек гарантировано по 10 в каждой строке, несложно найти сразу конечную (содержащую последний символ сообщения) ячейку: 3 + 11*10 — то есть 3 ячейки в строке eb, далее 11 строк, полностью заполненных символами. Таким образом, получаем, что aaae — последняя ячейка, содержащая символ. Все остальные — заведомо пустые (строки с be до ячейки caeb) — вычеркиваются.

Далее вычисляем начальную колонку: 18 со сдвигом на (0+4+1+1+3) — 24-я. Теперь из зашифрованного сообщения посимвольно вписываем буквы в пустые незачеркнутые ячейки с самой верхней, то есть вписываем a, p, p, z. Далее ищем 25-ю колонку, повторяем действия, 1-ю, 2-ю и так далее. Когда все буквы вписаны в ячейки, возвращаемся к начальной и справа налево списываем текст. Осталось только расшифровать название географического места. Оно зашифровано между буквами aa и ee. Каждому символу из tqexkeqeglz поставлен в соответствие один символ из специальной таблицы 2, и, аналогично биграммам в заголовке, мы получаем Prochorowka. Повторяющееся слово Prochorowka и выделительные биграммы aa и ee удаляются из расшифрованного сообщения, производятся мелкие замены букв и умлаутов, и расшифрованное сообщение готово.

 Криптостойкость 
Шифр считался вычислительно стойким в годы войны. Статистика тех лет показала, что за апрель 1945 года из 12 000 полученных сообщений только 3 500 удалось прочесть, что составляет 29 %, в то время как аналогичные показатели для Энигмы были равны 79 %.

К факторам уязвимости можно отнести следующие:
 Человеческий фактор: ошибки во время шифрования приводили к тому, что исправленное сообщение приходилось посылать снова с использованием того же шаблона. Послание отличалось от предыдущего всего несколькими символами. Менялась только начальная клетка.
 Захват шаблонов: в случае попадания ключа в руки союзников, все сообщения расшифровывались по описанному алгоритму с использованием захваченного образца, пока передающая сторона не меняла его на новый.
 Ограниченность ресурсов: для изготовления шаблона использовалось 36 различных готовых шаблонных рядов с 10 пустыми клетками в каждом. Из них было необходимо изготовить трафарет, состоящий из 24 строчек. Это приводило к повторам в новых экземплярах шаблонов.
Считалось, что для успешной дешифровки сообщения нужно было знать минимум 30-40 символов исходного текста. Для сравнения, 8-20 букв было достаточно для взлома Энигмы при помощи Turing Bombe.

Рассмотрим атаку на шифр на конкретном примере. Исходное сообщение после предварительного шифрования:

 Feind greift seit elf x vier fuenf uhr mit aqt panz naq suedwest an(Перевод: Враг нападёт в 11:45 утра с восемью танками с юго-запада)Перехваченное зашифрованное сообщение:

Допустим, нам каким-то образом удалось узнать, что враг нападет в 11:45 утра. Тогда первыми 30 символами в исходного сообщения будут: Feind greift seit elf x vier fuenf uh. Будем использовать их как шпаргалку.

Предположим, что сообщение начиналось с первой пустой клетки в строке. В противном случае, все дальнейшие шаги следует проделать вновь, рассматривая вторую пустую клетку как начальную и так далее до десятой. Запишем буквы в таблицу по 10 символов в строке (так как строка содержала именно столько пустых клеток):

Теперь будем искать вертикальные последовательности между строками, эквивалентные биграммам из зашифрованного сообщения (таблица 5). Такие вертикальные последовательности (связки) между i-ой буквой верхней строчки и k-ой буквой нижней строчки значили, что i-ая белая клетка шаблонного ряда верхней строчки находилась в той же позиции, что и k-ая белая клетка ряда нижней строчки. Опыт и наработки в области криптоанализа данного шифра позволяют полагать, что достаточно взять 4 буквы, лежащие строкой ниже. Для первой нашей буквы F:

Выпишем из Таблицы 5 все биграммы, начинающиеся на F (FR FD FQ) и сравним с FT FS FE и FI из таблицы 6.1. Совпадений нет. Тогда идем дальше с буквой Е:

Из таблицы 5: ET EA EH ER EN EI, из таблицы 6.2: ES EE EI ET. Сравниваем, получаем, что ET и EI совпадают. Запоминаем их, позже запишем их в таблицу 7.

Так продолжаем аналогично далее до последнего символа первой строки, буквы F. Запишем все совпавшие биграммы в таблицу таким образом, что под каждой буквой первой строки будет стоять буква из совпавшей биграммы, если таковая имеется:

Далее преобразуем эту таблицу в так называемое «меню». В первую строку меню запишем порядковый номер буквы из первой строки в том случае, если ей сопоставлена какая-либо парная буква. Вторая и третьи строки меню будут содержать те порядковые номера букв из таблицы 7, которыми они обладали в таблице 6. То есть у буквы F нет парной, значит единицу не пишем. У буквы E под номером 2 парная T, которая имеет номер 1 из таблицы 6, и буква I, имеющая номер 4 из таблицы 6, и так далее. Таким образом получаем:

Теперь необходимо воспользоваться еще одной уязвимостью — захваченными шаблонами и шаблонными рядами. Открываем наш каталог шаблонных рядов, где каждый ряд, состоящий из 25 клеток, 10 из которых — пустые, имеет порядковый номер.

Подбираем пары рядов так, чтобы все столбцы из пустых клеток совпадали по номерам с меню.

Обозначим закрашенную ячейку символом «@».

Четвертая (среди белых) по порядку белая клетка верхней строчки находится над седьмой белой клеткой нижней строчки, пятая — над восьмой, шестая — над девятой. Получаем:

Сравниваем с меню, убеждаемся, что условие выполнено. Значит, пара 33-3 шаблонных рядов наш кандидат на верное расположение двух строк относительно друг друга. Назовем это набором.

Так продолжаем сопоставлять ряды, получаем в итоге вариант с 11 наборами.

Подытожим: проделав все описанные выше шаги для строк 1 и 2 из таблицы 6, мы получили 11 наборов. Теперь следует проделать все заново для строк 1 и 3, а затем и строк 2 и 3 из таблицы 6. Находим из трех вариантов наборов такие, которые бы принадлежали каждому варианту. В нашем случае, таким будет набор 33-3-12.

Значит, мы определились с тем, как будут выглядеть первые три строки трафарета. Впишем туда известные нам символы. Затем, в строку ниже, под столбец известного текста, будем писать те буквы, которые следуют за сочетанием букв столбца в зашифрованном сообщении из таблицы 5. То есть для первого столбца, TI, из таблицы 6 видим сочетания TIQ и TIW, значит выписываем Q и W, для SE — SER и SEA и так далее до конца.

Так как по смыслу враг атаковал в 11.45 часов, значит в урезанном слове uhr не хватает буквы R. С нее и начнется четвертая строка. Далее, мы можем предположить, что будут зашифрованы данные по количеству атакующих единиц. Видим буквы M I T A Q T, что значит mit aqt, с восемью. Получается, что 1+6 пустых клеток уже заняты, значит осталось еще 3. Замечаем буквы A и N, которые наводят на мысль о слове PANZ, что значит panzern — танки''. Так мы определили места для всех пустых клеток. Затем просто находим подходящий шаблонный ряд из нашего каталога. Эта операция продолжается, пока мы не получаем следующее:

Сообщение полностью расшифровано и часть шаблона восстановлена, что поможет быстрее расшифровывать другие сообщения того же дня.

Примечания

Литература 
 
 
 
 
 

 

 

 
Криптография
Шифры