Предисловие

Нынешнему молодому поколению трудно в это поверить, но в середине 70-х годов прошлого века в СССР не было никаких компьютеров. Практически никаких, из тех, про которые можно было бы сказать, что они сделаны по-человечески. В своей книге КиС (Криптография и Свобода – см. https://mikhailmasl.livejournal.com/4852.html) я приводил пример компьютера (ни в коей мере не персонального!) Рута 110, стоявшего на первом этаже здания по адресу Большой Кисельный переулок, дом 11, в котором в то время размещался 4 (Технический) факультет Высшей Краснознаменной школы КГБ СССР имени Ф.Э.Дзержинского. Заметьте: не в комнате, а именно в здании, ибо Рута 110 занимала несколько комнат. Нас, молодых слушателей 4 факультета середины 70-х годов особенно умилял предбанничек к этому комплексу комнат, в котором требовалось перед входом в эту сокровищницу советской электроники одеть на сапоги музейные тряпочные тапочки. От пыли и грязи Рута 110 часто ломалась, да и от множества других явных и неявных причин тоже.

Уровень интеллекта и образованности большинства преподавателей 4 факультета был намного выше, чем возможности, которыми обладала Рута 110. Они прекрасно понимали, что будущее – за интегральными микросхемами, многоразрядными процессорами, за миниатюризацией и автоматизацией производства элементной базы будущих вычислительных устройств и не только вычислительных. На 4 факультете готовили специалистов-криптографов, которые в дальнейшем будут иметь дело с шифровальной техникой. Тогда, в середине 70-х, шифровальная техника в чем-то была похожа на Руту 110: громоздкая, неудобная, часто ломающаяся. А на западе уже стали появляться первые признаки научно-технической революции в виде надежной и миниатюрной микроэлектроники.

Анекдот советского времени. Военный парад на Красной площади. Перед мавзолеем проходят бронетранспортеры, пушки, танки, ракеты. И вдруг на огромном тягаче везут что-то непонятное.

Брежнев спрашивает у министра обороны

– Что это?

– Это наша большая интегральная схема, самая большая в мире!

НИР «Проба»

Первому начальнику 4 факультета Ивану Яковлевичу Верченко удалось собрать на факультете целую плеяду замечательных преподавателей, которые были нашими учителями и наставниками в середине 70-х. Иван Яковлевич надеялся, что факультет со временем должен был стать центром научной мысли в определенных областях специальных исследований.

В 1977 году под руководством замечательного преподавателя, начальника специальной кафедры СК-13 (кафедры высшей математики) доктора физико-математических наук, профессора Михаила Михайловича Глухова открыли НИР «Проба», в которой пытались применить западный прогресс в микроэлектронике для построения шифров, кардинально отличающихся от большинства советских шифров того времени. Они получили название «Шифры на новой элементной базе». В чем же заключалось это отличие? Давайте проведем небольшой экскурс в историю криптографии.

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

С появлением первых, пусть даже самых примитивных ЭВМ становится понятно, что принципы шифрования информации надо изменить. Перед шифрованием надо провести оцифровку информации, т.е. перевести всю шифруемую информацию в бинарный вид, включающий в себя только два символа: 0 и 1, а затем уже шифровать полученную бинарную информацию. Такие шифраторы в середине 70-х годов называли электронными, теории электронных шифраторов на 4 факультете была посвящена специальная дисциплина СД – 7 В. Говоря специфическим криптографическим языком, в электронных шифраторах осуществлялось преобразование символов бинарного алфавита, состоящего только из двух символов: 0 и 1. А если еще более научно – над полем Галуа GF(2) из двух элементов.

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

Обрабатывать информацию побитно – неэффективно. Гораздо более эффективно обрабатывать информацию сразу целыми векторами из N бит. Вектор из 8 бит называется байтом и принципиальным отличием микропроцессоров сразу после их появления стала обработка информации не битами, а байтами. Такие микропроцессоры получили название 8 разрядных. Довольно быстро после 8 разрядных стали появляться 16 разрядные, затем 32 разрядные. В настоящее время наиболее распространенными в компьютерах являются 64 разрядные микропроцессоры.

В НИР «Проба» была поставлена задача создания и анализа узлов для криптосхем, работающих не с битами, а с байтами. Формально каждый байт является 8 битовым вектором и с ним можно работать так же, как и раньше работали с электронными шифраторами. Но будет ли такая работа наиболее эффективной? Можно ли найти для шифраторов, работающих с байтами, специфические методы построения более высокоскоростных и более стойких шифраторов, чем традиционные электронные?

Как я писал в КиС, большинство советских шифраторов того времени состояли из «балалаек». Так криптографы прозвали типовой узел тех шифраторов, состоящий из регистра сдвига над GF(2) и его функции обратной связи. А что будет, если ячейками регистра сдвига будут не биты, а байты? Или, опять переходя к математическому языку, регистр сдвига будет над Z/256 – кольцом вычетов по модулю 256. Появляются два интересных момента.

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

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

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

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

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

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

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

Операцию сложения с переносом двух байт x и y тоже можно рассматривать как подстановку g_x ϵ S₂₅₆: g_x(y) = (x + y)mod 256. Если через g обозначить полноцикловую подстановку g = g₁ = (0,1,2,…,255), то, полагая, что g₀ – это единичная подстановка, когда все элементы отображаются сами в себя, получаем, что при любом x ϵ Z/256 g_x = g^x .

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

Предположим, что у нас есть цепочка байт x1, x2,…xk и произвольная подстановка π из S₂₅₆. Что можно сказать о подстановках g_x1π g_x2π… g_xkπ?

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

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

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

На вход узла подается входное слово – цепочка из k байт, каждый байт складывается по модулю 256 с результатом обработки предыдущих байт и заменяется по подстановке π. Таким образом, этот узел работает циклами, в каждом цикле по k тактов. Если предположить, что цепочка X = x1,x2,..,xk из k байт является ключом, то с помощью этого узла можно реализовать подстановку π1 = g_x1π g_x2π… g_xkπ, зависящую от ключа X. Результаты НИР «Проба» показывают, что таким путем можно реализовать практически любую подстановку из S₂₅₆.

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

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

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

Итак, неограниченно увеличивая k – длину входного слова, с помощью цепочек g_x1π g_x2π… g_xkπ можно получить любую подстановку из S₂₅₆. Но это – абстрактный результат, а хотелось бы знать, что за подстановки будут при каком-нибудь фиксированном k. Какими свойствами будет обладать при фиксированном k множество таких подстановок при всевозможных x1, x2,…,xk? Такое множество принято обозначать (Gπ)^k.

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