Михаил Масленников - Криптография и свобода

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

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

– Мы постарались придумать максимально простую для реализации криптосхему. Вы можете прикинуть оценки ее стойкости?

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

Здесь я вынужден извиниться перед читателем этой книги, не имевшим ранее никаких дел с математикой. Сейчас придется немного залезть в теорию групп и теорию подстановок, со своими специфическими терминами: симметрическая группа, циклическая подстановка, свойство 2-транзитивности и т.п. Может быть неискушенный читатель пробежит эту часть «по-диагонали», не вдаваясь особо в подробности и не забивая себе в голову всех этих премудростей. Но в математике, как и в любой другой области науки, иногда удается получить красивый результат, и, чтобы оценить его красоту, надо немного вникнуть в детали, подробности, предшествующие его получению. Так что читатель, окунувшийся в начинающиеся ниже математические дебри (не такие уж и сложные, как может показаться на первый взгляд!), в конце концов будет вознагражден одной красивой «изюминкой».

Большинство традиционных электронных шифраторов реализовано с помощью «балалаек», работающих с битами. В этих «балалайках» в ячейки регистра сдвига могут быть записаны только два элемента – 0 или 1, такой регистр сдвига называется регистром сдвига над полем GF(2) - полем Галуа из двух элементов. Операции с битами тоже весьма простые: сложение и умножение по модулю 2, а также отрицание. Все методы анализа подобных «балалаек» ориентированы на двоичные операции, на операции в поле GF(2).

Если же мы вместо битов переходим к байтам, то появляется много нового. Традиционные операции с байтами можно осуществлять несколькими способами. Например, сложение и вычитание могут быть с переносом или без переноса, т.е. или это будут операции в кольце вычетов по модулю 256, или покоординатное сложение бит. Но самое интересное обобщение происходит с операцией отрицания. Отрицание (инверсия) бита – это фактически подстановка на множестве из 2 элементов. Когда всего 2 элемента, то мощность симметрической группы S2 составляет всего 2! = 2, всего две подстановки: тривиальная единичная (ничего не меняется) и инверсия, когда 0 переходит в 1, а 1 – в 0. Мощность же симметрической группы S256 составляет 256! – совершенно фантастическое число. Введение подстановки в регистр сдвига, работающий с байтами, а не с битами, переворачивает все привычные методы криптографического анализа. Совершенно другие операции, а следовательно, нужны и другие подходы к анализу и оценке стойкости таких схем, чем те, которые использовались в традиционных двоичных «балалайках».

С чего начала кафедра математики на 4 факультете? С самого простейшего преобразования, осуществляемого с n-мерными двоичными векторами, с преобразования типа (Gπ)k, где G – группа, порожденная циклическим сдвигом (G = <g>, g =(0,1,…,2n-1)-циклическая подстановка), π - некоторая фиксированная подстановка из S2n, а k – некоторое целое число.

Если здесь перейти от математических терминов из теории групп к обычной криптографической терминологии, то преобразование типа (Gπ)k – это следующий узел.

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

Кафедра начала с изучения группы <g, π >, т.е. группы, порожденной двумя подстановками: циклическим сдвигом g и фиксированной произвольной подстановкой π. Это естественное обобщение преобразования (Gπ)k, предельный случай. Свойства группы <g, π > дают ответ на вопрос, что в принципе можно ожидать от нашего преобразования при увеличении длины k до бесконечности. Можем ли мы таким путем получить все подстановки или же есть какие-то запреты?

Оказалось, что если случайно и равновероятно выбрать из всей симметрической группы фиксированную подстановку π, то с вероятностью, близкой к 1, группа <g, π > будет совпадать со всей симметрической группой, т.е. запретов не будет. Те подстановки π, для которых это не так, очень часто легко определяются, например, π=g, а также любая линейная подстановка, реализующая преобразование вида π(x) = ax+b, где a и b – фиксированные элементы из Z/2n.

Дальше, естественно, стали возникать вопросы: а как скоро мы сможем достичь симметрической группы? Какова будет мощность слоя (Gπ)k при некотором значении k, например, при k=2 или при k=3? При каком k множество (Gπ)k станет 2-транзитивным, т.е. по имеющимся в нем подстановкам любая пара (y1,y2), в которой y1≠y2, сможет перейти в любую пару (z1,z2), в которой z1≠z2? Что в общем случае можно будет сказать про обобщение 2-транзитивности – m-транзитивность?

За свойство 2-транзитивности взялись основательно, чувствовалось, что здесь могут быть интересные криптографические зацепки: если 2-транзитивность отсутствует, то появляются запреты переходов биграмм текста, широкое поле деятельности для криптоаналитика. Например, если π - упомянутая выше линейная подстановка, то для любой пары (y1,y2) будет справедливо соотношение:

π(y1)- π(y2) = (ay1+b) - (ay2+b) = a(y1-y2)

В этом случае при применении подстановки π сохраняется соотношение между разностями знаков, а поэтому кратной транзитивности заведомо не будет.

А если π - не линейная, а произвольная подстановка? При каком минимальном значении k множество (Gπ)k может достичь свойства 2-транзитивности? Всего имеется 2n(2n-1) различных пар (z1,z2), в которых z1≠z2, а количество различных подстановок в (Gπ)k не превосходит (2n)k. Следовательно, свойства 2-транзитивности можно достичь только при k≥2. Можно ли при k=2?

Рассмотрим множество подстановок (Gπ)2. Это множество реализует всевозможные преобразования произвольного значения t в значение s по формуле s = π (π (t+x1)+x2) при всевозможных x1,x2. Если бы это множество было 2-транзитивным, то для любых заранее фиксированных s1,s2, t1,t2 , в которых s1≠s2 и t1≠t2, система уравнений:

s1 = π (π (t1+x1)+x2)

s2 = π (π (t2+x1)+x2)

имела бы решение относительно x1,x2, а, следовательно, поскольку π - подстановка, то и система

s1 = π (t1+x1)+x2 (1)

s2 = π (t2+x1)+x2

имела бы решение для любых заранее фиксированных s1,s2, t1,t2, в которых s1≠s2 и t1≠t2

Отсюда, вычитая одно уравнение из другого, мы приходим к одной очень важной криптографической характеристики подстановки π - матрице частот встречаемости разностей переходов ненулевых биграмм P(π) размера (2n-1)x(2n-1), а именно, на пересечении i-ой строки и j-го столбца в этой матрице стоит значение pij - число решений системы уравнений относительно x и y:

x-y = i (2)

π(x) - π(y) = j

где i, j ≠ 0.

Если при каких-то i, j ≠ 0 pij =0, то это означает, что при заранее фиксированных s1,s2, t1,t2, в которых s1≠s2 и t1≠t2, а также t1-t2 = i, s1-s2 = j, система (1) заведомо не имеет решения, ибо в противном случае имела бы решение и система (2).