Маркант

Одним из первых и очень важным результатом НИР «Проба» было доказательство, что при случайном и равновероятном выборе ? из S

группа, порожденная множеством G?, с большой вероятностью совпадает со всей симметрической группой S

. Что это означало на практике?

Возьмем простейший типовой узел, реализованный с помощью побайтных преобразований.

Рис. 1. Типовой узел (G?)

На вход узла подается входное слово – цепочка из k байт, каждый байт складывается по модулю 256 с результатом обработки предыдущих байт и заменяется по подстановке ?. Таким образом, этот узел работает циклами, в каждом цикле по k тактов. Если предположить, что цепочка X = x1,x2,..,xk из k байт является ключом, то с помощью этого узла можно реализовать подстановку ?1 = g

? g

?… g

?, зависящую от ключа X. Результаты НИР «Проба» показывают, что таким путем можно реализовать практически любую подстановку из S

.

Здесь хотелось бы обратить внимание на то, что группа <G?> будет совпадать с S

не при любой ?. Например, если ? ? G, то это заведомо не так. Но вероятность получить «плохую» подстановку ? при ее случайном и равновероятном выборе из S

крайне мала.

А теперь давайте вернемся ко второй мировой войне и немецкому дисковому шифратору «Энигма». В нем было два типа ключей: долговременные и одноразовые. Долговременные ключи – это коммутации вращающихся роторов, а одноразовые – их начальное положение. Если коммутации вращающихся роторов неизвестны, то в этом случае криптографы бессильны. Коммутации роторов – это фактически подстановки на множестве букв немецкого алфавита. Число всевозможных подстановок в симметрической группе S

равно N! – N факториал, произведение всех чисел от 1 до N. При N = 26 имеем N! = 403 291 461 126 605 635 584 000 000 ? 4 * 10

. Если предположить, что в «Энигме» коммутации роторов выбирались случайно и равновероятно, то для перебора всевозможных значений коммутации только одного ротора потребовалась бы трудоемкость, непосильная даже для современных ЭВМ. Поэтому англичане могли читать «Энигму» только при условии, что какими-то путями им удалось захватить хотя бы один ее экземпляр и определить коммутации всех роторов.

Роторы в «Энигме» нельзя было сделать одноразовыми ключами по объективным причинам – это слишком сложно. А в НИР «Проба» показали, что в шифрах на новой элементной базе это сделать несложно.

Итак, неограниченно увеличивая k – длину входного слова, с помощью цепочек g

? g

?… g

? можно получить любую подстановку из S

. Но это – абстрактный результат, а хотелось бы знать, что за подстановки будут при каком-нибудь фиксированном k. Какими свойствами будет обладать при фиксированном k множество таких подстановок при всевозможных x1, x2,…,xk? Такое множество принято обозначать (G?)

.

Во многих криптографических задачах важную роль играет свойство 2-транзитивности некоторого множества подстановок. Множество подстановок (G?)

является 2-транзитивным, если для любых двух пар (x1,y1) и (x2,y2), таких что x1 ? y1 и x2 ? y2, найдется подстановка, переводящая пару (x1,y1) в (x2,y2).

В НИР «Проба» получили следующие результаты.

Минимальное значение k, при котором (G?)

является 2-транзитивным, равно 3.

При случайном и равновероятном выборе ? из S

с вероятностью, близкой к 1, множество (G?)

будет 2-транзитивным.

Для любой подстановки ? из S

можно определить ее так называемую матрицу частот P(?) размера 255 х 255, у которой на пересечении строки с номером i со столбцом с номером j, i,j ? {1,2,…,255}, находится число решений системы

x – y = i (mod 256)

?(x) – ?(y) = j (mod 256)

относительно неизвестных x, y ? Z/256.

В НИР «Проба» показали, что множество (G?)

является 2-транзитивным тогда и только тогда, когда возведенная в квадрат матрица P(?) не содержит нулевых элементов. Чуть позже было доказано, что при случайном и равновероятном выборе ? в матрице P(?) примерно 2/3 элементов – ненулевые, 1/3 – нули.

Темой моей дипломной работы в 1979 году было построение и анализ матриц P(?) для всех ? из симметрической группы S

. Это 8! = 40320 подстановок. Такое построение позволяло подтвердить приведенные выше теоретические результаты.

Для Руты – 110, если она к тому времени была еще жива (сейчас точно не помню), это явно непосильная задача, матрицы строились вручную. Все теоретические результаты были подтверждены.

Ангстрем – 3

После изучения в НИР «Проба» математического аппарата для шифров на новой элементной базе естественно встал вопрос о построении простейшего примера такого шифра.

Здесь мне хотелось бы сказать несколько слов о том, кто тогда, на рубеже 80-х годов прошлого века, занимался в СССР криптографией и шифрами.

Специалистов-криптографов готовили только на 4 факультете ВКШ. Их отбирали и направляли на учебу 3 ведомства: КГБ, Министерство обороны и НИИ Автоматики. После окончания 4 факультета выпускники направлялись на службу в то ведомство, которое их набирало на учебу. Выпускники от КГБ и МО становились действующими офицерами, хотя военную форму в КГБ не носили, а выпускники от НИИ Автоматики – офицерами запаса, не получающими льгот и выплат, положенных действующим офицерам, хотя во время учебы на 4 факультете были военнослужащими и ходили в военной форме. В прошлом НИИ Автоматики – спецтюрьма № 16 МВД СССР, в 1948 году преобразована в спецтюрьму № 1 МГБ СССР, эта спецтюрьма известна по роману А.И.Соженицына «В круге первом».

Разработкой новых советских шифров должно было заниматься НИИ Автоматики, а Спецуправление 8 ГУ КГБ СССР – проводить их экспертизу. В реальной жизни разработка и экспертиза тесно переплетались и превращались в совместную работу криптографов, закончивших 4 факультет.

После окончания 4 факультета в 1979 году я попал на работу в 5 (Теоретический) отдел Спецуправления 8 ГУ КГБ СССР. Там тогда тоже интересовались шифрами на новой элементной базе, поддерживали тесные связи с НИИ Автоматики. В группе Валерия Владимировича Ященко, в которую я попал, вели следующий, если так можно выразиться, «анализ идеи» построения шифра на новой элементной базе с помощью неавтономного регулярного регистра сдвига над Z/256, которую принесли в 5 отдел Владимир Владимирович Седов и Борис Владимирович Березин из НИИ Автоматики.

Рис. 2. Шифратор «Ангстрем – 3»

В этой идее самое привлекательное – простота ее реализации. В НИИ Автоматики, по-видимому, поддерживали связи с заводом «Ангстрем» в Зеленограде, который в то время являлся ведущим предприятием по выпуску советской электроники. В.В.Седов и Б.В.Березин заканчивали 4 факультет, знали о НИР «Проба» и пытались перейти от чисто абстрактных математических результатов к конкретным шифраторам. Изображенный выше неавтономный регулярный регистр сдвига над Z/256 получил название шифратор «Ангстрем – 3». Слово «Ангстрем», по-видимому, предполагало, что он будет реализован на элементной базе завода Ангстрем, а цифра 3 – что это была не первая такая попытка.

Я подробно описывал в КиС, как мне удалось взломать «Ангстрем – 3» при T = 16 и как к этому отнеслись мои новые начальники. «Ангстрем – 3» взламывался на спор, я этот спор выиграл и получил за это прибавку к жалованию. Дальше, естественно, встал вопрос: а как можно модифицировать «Ангстрем – 3» так, чтобы сделать его стойким и сохранить простоту реализации?