МАРКАНТ. НИР "Проба"
Первому начальнику 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 - с переносом;
К содержимому ячейки можно применять подстановку из симметрической группы 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 = , а множество {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.
Здесь хотелось бы обратить внимание на то, что группа будет совпадать с 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-транзитивным.
Для любой подстановки π из S256 можно определить ее так называемую матрицу частот 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π)3 является 2-транзитивным тогда и только тогда, когда возведенная в квадрат матрица P(π) не содержит нулевых элементов. Чуть позже было доказано, что при случайном и равновероятном выборе π в матрице P(π) примерно 2/3 элементов - ненулевые, 1/3 - нули.
Темой моей дипломной работы в 1979 году было построение и анализ матриц P(π) для всех π из симметрической группы S8. Это 8! = 40320 подстановок. Такое построение позволяло подтвердить приведенные выше теоретические результаты.
Для Руты - 110, если она к тому времени была еще жива (сейчас точно не помню), это явно непосильная задача, матрицы строились вручную. Все теоретические результаты были подтверждены.
Оглавление
Полностью книга МАРКАНТ опубликована на Литрес