Сложение байт можно проводить как покоординатное сложение по модулю 2 без переноса, а можно как сложение в кольце Z/256 – с переносом;

К содержимому ячейки можно применять подстановку из симметрической группы S256.

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

Сейчас результаты НИР «Проба» позволяют понять, чем же интересовались в середине 70-х годов прошлого века советские криптографы, каковы были тогда основные направления развития криптографии, как специфического раздела математики. Я, естественно, не могу в точности помнить все эти результаты, полученные свыше 40 лет назад, но постараюсь здесь вкратце описать их общими словами.

Ключевым словом в НИР «Проба» было слово подстановка. В математике так принято называть взаимно-однозначное отображение некоторого множества в себя. Множество всевозможных подстановок принято называть симметрической группой. Так, любая подстановка из симметрической группы S256 – это взаимно-однозначное отображение кольца вычетов Z/256 в себя.

Имея всего 256 байт памяти легко реализовать на них любую подстановку ? из S256. Для этого для любого x ? Z/256 в ячейку памяти по адресу x надо записать значение ?(x).

В алгебре под произведением подстановок понимают их последовательное применение слева направо.

Операцию сложения с переносом двух байт x и y тоже можно рассматривать как подстановку gx ? S256: gx(y) = (x + y)mod 256. Если через g обозначить полноцикловую подстановку g = g1 = (0,1,2,…,255), то, полагая, что g0 – это единичная подстановка, когда все элементы отображаются сами в себя, получаем, что при любом x ? Z/256 gx = gx .

Множество всевозможных преобразований {g0, g1,…,g255} образуют циклическую группу, которую в НИР «Проба» было принято обозначать G = <g>, а множество {g0?, g1?,…,g255?} – через G?.

Предположим, что у нас есть цепочка байт x1, x2,…xk и произвольная подстановка ? из S256. Что можно сказать о подстановках gx1? gx2?… gxk??

Одним из первых и очень важным результатом НИР «Проба» было доказательство, что при случайном и равновероятном выборе ? из S256 группа, порожденная множеством G?, с большой вероятностью совпадает со всей симметрической группой S256. Что это означало на практике?

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

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

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

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

А теперь давайте вернемся ко второй мировой войне и немецкому дисковому шифратору «Энигма». В нем было два типа ключей: долговременные и одноразовые. Долговременные ключи – это коммутации вращающихся роторов, а одноразовые – их начальное положение. Если коммутации вращающихся роторов неизвестны, то в этом случае криптографы бессильны. Коммутации роторов – это фактически подстановки на множестве букв немецкого алфавита. Число всевозможных подстановок в симметрической группе SN равно N! – N факториал, произведение всех чисел от 1 до N. При N = 26 имеем N! = 403 291 461 126 605 635 584 000 000 ? 4 * 1026. Если предположить, что в «Энигме» коммутации роторов выбирались случайно и равновероятно, то для перебора всевозможных значений коммутации только одного ротора потребовалась бы трудоемкость, непосильная даже для современных ЭВМ. Поэтому англичане могли читать «Энигму» только при условии, что какими-то путями им удалось захватить хотя бы один ее экземпляр и определить коммутации всех роторов.

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

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

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

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

Минимальное значение k, при котором (G?)k является 2-транзитивным, равно 3.

При случайном и равновероятном выборе ? из S256 с вероятностью, близкой к 1, множество (G?)3 будет 2-транзитивным.