Маркант

Маркант
Михаил Евгеньевич Масленников

В книге рассказывается о создании системы криптографической защиты банковских авизо для Центрального Банка России в 1992 году. Внедрение этой системы сразу же позволило снизить курс доллара и стабилизировать ситуацию с банковскими платежами начиная с 1 декабря 1992 года.

Михаил Масленников

Маркант

Предисловие

Нынешнему молодому поколению трудно в это поверить, но в середине 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

? S

: g

(y) = (x + y)mod 256. Если через g обозначить полноцикловую подстановку g = g

= (0,1,2,…,255), то, полагая, что g

– это единичная подстановка, когда все элементы отображаются сами в себя, получаем, что при любом x ? Z/256 g

= g

.

Множество всевозможных преобразований {g

, g

,…,g

} образуют циклическую группу, которую в НИР «Проба» было принято обозначать G = <g>, а множество {g

?, g

?,…,g

?} – через G?.

Предположим, что у нас есть цепочка байт x1, x2,…xk и произвольная подстановка ? из S

. Что можно сказать о подстановках g

? g

?… g

??