Rasterschlüssel 44

Rasterschlüssel 44 (RS44) (от нем. Raster — сетка, растр и Schlüssel — ключ) — ручная техника шифрования, заменившая применявшийся прежде шифр «двойной квадрат» (нем. Doppelkastenschlü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).

Таблица 1 (биграммная)

a	b	c	d	e
y	v	f	x	g
q	u	j	r	c
s	k	t	b	w
p	h	d	n	a
m	o	i	l	e

Каждая буква из биграммы заменялась на любую из пяти, стоящих в соответствующем столбце. Если буквы в биграммах повторялись, по тем же правилам бралась другая буква, отличная от уже взятой. На самом деле, при шифровании биграмм 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' по специальной табличке:

Таблица 2 (географическая)

a

b

c

d

e

f

g

h

i

j

k

l

m

n

o

p

q

r

s

t

u

v

w

x

y

z

z

d

x

o

f

b

u

k

h

p

l

j

y

m

e

t

a

q

v

n

s

w

g

r

i

c

c

m

r

z

i

k

x

p

h

j

l

q

v

g

a

d

f

o

s

u

y

b

w

n

e

t

Получаем:

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-й.

Таблица 3

24	25	1	2	3	4	5	6
appz	reie	gee	nswog	nsuia	mhatq	bmzzk	tusrmal
7	8	9	10	11	12	13	14
mzltg	te	tr	eerq	spteqk	es	naerb	ealu
15	16	17	18	19	20	21	22
xtxee	eeosrez	erboiqex	nerva	tae	tqe	rinsq	wztl
23
itbre

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

Таблица 4

appzr	eiege	enswo	gnsui	amhat
qbmzz	ktusr	malmz	ltgte	treer
qspte	qkesn	aerbe	aluxt	xeeee
osrez	erboi	qexne	rvata	etqer
insq	wztlit	bre

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

Расшифровка сообщения

Смотрим в заголовок:

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 утра с восемью танками с юго-запада)

Перехваченное зашифрованное сообщение:

Таблица 5 (шифротекст)

NLTIQ	NEATE	TSEAI	EHNRU	FRMNS	ERTUI
TIWFZ	DFFDP	VENEI	FQSEA	UGXA

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

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

Таблица 6

Позиция	1	2	3	4	5	6	7	8	9	10
Строка 1	F	E	I	N	D	G	R	E	I	F
Строка 2	T	S	E	I	T	E	L	F	X	V
Строка 3	I	E	R	F	U	E	N	F	U	H

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

Таблица 6.1

Строка 1	F	E	I	N	D	G	R	E	I	F
Строка 2	T	S	E	I	T	E	L	F	X	V

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

Таблица 6.2

Строка 1	F	E	I	N	D	G	R	E	I	F
Строка 2	T	S	E	I	T	E	L	F	X	V

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

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

Таблица 7

порядковый номер буквы	1	2	3	4	5	6	7	8	9	10
Строка 1	F	E	I	N	D	G	R	E	I	F
Парная буква 1		T	E	E	F	X
Парная буква 2		I	T	L

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

Таблица 8 (меню)

2	3	4	5	6
1	3	6	8	9
4	5	7

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

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

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

Таблица 9

1

2

3

4

5

6

7

8

9

10

порядковый номер пустой ячейки в ряду № 33

@

@

@

@

@

@

@

@

@

@

@

@

@

@

@

шаблонный ряд № 33

@

@

@

@

@

@

@

@

@

@

@

@

@

@

@

шаблонный ряд № 3

1

2

3

4

5

6

7

8

9

10

порядковый номер пустой ячейки в ряду № 3

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

Таблица 9.1

4	5	6
7	8	9

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

Таблица 8.1

2	3	4	5	6
1	3	6	8	9
4	5	7

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

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

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

Таблица 10

@

@

@

F

@

@

@

@

E

@

@

I

@

N

@

D

@

@

G

R

@

E

I

@

F

T

@

S

@

E

I

@

T

@

E

@

@

@

L

@

F

@

@

X

@

V

@

@

@

@

I

@

E

R

@

F

@

U

@

@

E

@

N

@

@

F

@

@

@

U

@

H

@

@

@

Q

R

M

Q

I

A

A

A

Q

T

D

A

F

N

W

A

T

T

T

R

R

R

N

N

N

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

Таблица 11

@

@

@

F

@

@

@

@

E

@

@

I

@

N

@

D

@

@

G

R

@

E

I

@

F

T

@

S

@

E

I

@

T

@

E

@

@

@

L

@

F

@

@

X

@

V

@

@

@

@

I

@

E

R

@

F

@

U

@

@

E

@

N

@

@

F

@

@

@

U

@

H

@

@

@

@

@

R

M

@

@

@

I

T

@

A

Q

@

T

@

@

P

@

A

@

@

N

@

@

@

@

Z

@

N

A

Q

@

@

S

@

U

@

E

@

@

D

@

W

@

@

E

@

@

@

@

@

@

@

@

@

S

T

@

@

A

@

N

@

@

@

@

@

@

@

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

ЛитератураПравить

• Friedrich L. Bauer. Entzifferte Geheimnisse. Methoden und Maximen der Kryptologie. — 3-e изд. — Springer, 2000. — ISBN 3-540-67931-6.
• Michael J. Cowan. Rasterschlüssel 44 — The Epitome of hand Field Ciphers. — Cryptologia, 2004. — С. 115-148. — doi:10.1080/0161-110491892827.
• Oberkommando der Wehrmacht. Schlüsselanleitung zum Rasterschlüssel 44 (RS 44) Schlüsselanleitung zum Rasterschlüssel 44 (RS 44)  // получено с Foundation for German communication and related technologies : рассекреченный документ. — Ag WNV/Fu I, 1944.
• John H. Tiltman. Schlüsselanleitung zum Rasterschlüssel 44 (RS 44)  // National Security Agency, Technical Journals : статья. — 1957—1965. — С. 100—105, редактированные.
• John F. Clabby. Brigadier John Tiltman — A Giant Amoung Cryptanalysts // National Security Agency, Center for Cryptologic History, Cryptologic Heritage : статья. — 2007.

• Heinz Ulbricht. Die Chiffriermaschine Enigma — trügerische Sicherheit: ein Beitrag zur Geschichte der Nachrichtendienste // University of Braunschweig - Institute of Technology : диссертация. — 2005. Архивировано 1 декабря 2015 года.

• Klaus Schmeh. Codeknacker gegen Codemacher. Die faszinierende Geschichte der Verschlüsselung. — 2-e изд. — Herdecke: W3L-Verlag, 2008. — ISBN 978-3-937137-89-6.

• Joachim Beckh. Blitz & Anker: Informationstechnik — Geschichte und Hintergründe, том 2. — BoD GmbH, 2005. — ISBN 978-3833429972.