"Криптография и свобода" - читать интересную книгу автора (Масленников Михаил)

Глава 3. Логарифмические подстановки

В этой главе давайте отложим в сторону лирические и понятные всем отступления про обстановку в стране в то время. Мои рассуждения об этом субъективны, кто-то может соглашаться с ними, кто-то, наоборот, считать те времена образцом для подражания на фоне современной криминализации страны. В этой книге я старался следовать криптографически-философскому принципу Шеннона: в шифре чередовать не похожие друг на друга операции перемешивания и сдвига. В качестве операций сдвига – главы, отображающие общую ситуацию в СССР и в КГБ в те, теперь уже далекие времена, а в роли перемешивания выступают главы, в которых много говорится о математике, криптографии или программировании. Сейчас начнется очередная «перемешивающая» глава.

Шифратор «Ангстрем-3» был построен в полном соответствии с этим принципом Шеннона: регистр сдвига над Z/256 (операции сдвига), усложненный подстановкой из S₂₅₆, типичным перемешивающим преобразованием. Перемешивающее преобразование дает столь необходимое в криптографии размножение различий в блоках открытого текста. В общефилософских книгах по криптографии, типа упоминавшейся выше книги Брюса Шнайера «Прикладная криптография», употребляется даже термин «лавинный эффект». Вот соответствующая цитата оттуда.

Насколько я представляю себе DES, нигде, ни в одной книге, не было дано точных математических оценок этого «лавинного эффекта». DES так спроектирован и все. А почему он так спроектирован? Остается лишь догадываться, да строить статистические эксперименты, которые подтверждают: да «лавинный эффект» безусловно есть.

Вся прелесть «Ангстрема-3» в том, что в нем для оценки подобного «лавинного эффекта» на 4 факультете и в Спецуправлении еще в конце 70-х годов был разработан строгий математический аппарат, опирающийся на алгебру, на теорию групп, колец и полей. Об этих результатах я уже упоминал в предыдущей главе, посвященной шифрам на новой элементной базе, вот, вкратце, их суть.

1. В шифрах, использующих операции в кольце Z/256 и подстановки П из S₂₅₆, лавинный эффект определяется матрицей частот встречаемости разностей переходов ненулевых биграмм P(П) размера 255x255.

2. Лавинный эффект будет тем лучше, чем меньше нулей в этой матрице. Хорошими следует считать такие подстановки, матрицы которых, возведенные в квадрат, не содержат нулей.

3. При случайном и равновероятном выборе подстановки из всей симметрической группы S₂₅₆, общее количество подстановок в которой составляет огромную величину 256! – произведение всех чисел от 1 до 256, вероятность выбрать хорошую подстановку стремится к 1.

4. Существуют примеры самых плохих подстановок, это линейные подстановки.

5. Теоретически подсчитано минимально возможное количество нулей в матрице P(П).

Вопрос же о том, существуют ли подстановки с минимально возможным числом нулей в матрице P(П), оставался открытым до конца 1983 года.

*****

– Работайте дома. Если Вы будете часто здесь появляться, то диссертации не напишите.

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

Итак, мои творческие планы связаны с шифрами на новой элементной базе. Это новая тема и непаханое поле для деятельности. Основное отличие этих шифров от традиционных балалаек – наличие в них подстановки (или даже нескольких подстановок) из S₂₅₆. Эти подстановки определяют криптографические качества шифров, они же дают возможность строить очень простые и высокоскоростные схемы, поэтому фундаментальные исследования шифров на новой элементной базе нужно начинать с изучения подстановок. Нужно постараться получить наиболее полную картину их свойств, ответить на типовые вопросы, например:

– какие подстановки считать приемлемыми, а какие неприемлемыми для использования в шифрах на новой элементной базе и почему;

– как описать какие-то особенные классы подстановок и в чем будет их особенность;

– как лучше использовать подстановку в схеме, где ее целесообразнее расположить и почему;

И, наконец, надо попробовать дать ответ на конкретный практический вопрос: а что же делать со схемой «Ангстрем-3»? Как ее модернизировать, чтобы, сохранив простоту и высокую скорость реализации, обеспечить гарантированную стойкость?

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

Для начала мы попытались описать какой-нибудь класс подстановок П, для которого было бы гарантировано, что показатель 2-транзитивности множества GП минимален и равен 3. Я надеюсь, что читатель припоминает упоминавшуюся ранее в этой книге матрицу частот встречаемости разностей переходов ненулевых биграмм P(П) и условие достижения 2-транзитивности за 3 шага: эта матрица, возведенная в квадрат, не должна содержать нулей. Я пытался описать класс подстановок, у которых полностью ненулевые средние строка и столбец, наличие такого «креста» дает гарантию того, что квадрат матрицы будет полностью положительным, без нулей. Б.А. сразу же стал пытаться найти и пристроить к этой ситуации какие-то аналогии из известных ему экзотических групп. Несколько попыток оказались безрезультатными и моей задачей было обоснование того, что этот класс групп совсем непригоден. Своего рода тотальное опробование всех подстановок, каким-то пусть даже косвенным образом связанных с изначальными. Б.А., как умудренный опытом рыболов, выискивал места, где могли водиться хорошие подстановки, а я закидывал в этих местах свою блесну.

И вот однажды клюнула такая подстановка, о которой даже сейчас, спустя 20 лет, я вспоминаю с нескрываемым удовольствием. Читатель, наверное, помнит про мое обещание привести один очень красивый результат про подстановки с минимальным числом нулей в матрице P(П). Настало время исполнить обещанное.

Пусть N – такое число, что N+1 – простое, Ф - примитивный элемент в поле Галуа GF(N+1), т.е. образующий элемент циклической мультипликативной группы этого поля.

Пусть П - преобразование множества Z/N вида:

П(х) = log_Ф(Ф^x+roр), если Ф^x+roр0,

П(х) = log_Фр, если Ф^x+roр=0,

где р - произвольный ненулевой элемент поля GF(N+1), r – произвольный элемент из Z/N, o - операция сложения в поле GF(N+1). Тогда преобразование П является взаимно-однозначным на множестве Z/N, т.е. является подстановкой из симметрической группы S_N.

Это утверждение достаточно очевидно, поскольку Ф - примитивный элемент поля GF(N+1), т.е. множество значений Ф,Ф²,…,Ф^N совпадает со множеством {1,2,…,N} – мультипликативной группой поля GF(N+1), а логарифмирование – операция, обратная возведению в степень. Все проблемы с нулем подправляются вторым условием: П(х) = log_Фр, если Ф^x+roр=0.

Такие подстановки естественно назвать логарифмическими, а точку х₀, при которой П(х₀) = log_Фр – выколотой точкой логарифмической подстановки П.

Здесь и всюду далее нам будут встречаться два разных типа арифметических операций сложения и вычитания: в кольце Z/N и в поле GF(N+1). Операции в кольце Z/N будем обозначать обычными символами “+” и “-“, а операции в поле GF(N+1) – o и ㊀ соответственно.

Теорема 1.

Пусть П – логарифмическая подстановка, х₁х₂, х₁,х₂ ЄZ/N, i – произвольный ненулевой элемент кольца Z/N.

Тогда если ни одна из точек х₁+i,x₁,х₂+i,x₂ не является выколотой, то П(х₁+i)- П(x₁) П(х₂+i)- П(x₂).

Доказательство.

Предположим, что П(х₁+i)- П(x₁)= П(х₂+i)- П(x₂), тогда Ф^{П(х1+i)- П(x1)}=Ф^{П(х2+i)- П(x2)}.

Поскольку все точки не являются выколотыми, то отсюда вытекает, что (Ф^х1+i+roр)(Ф^х2+roр)=(Ф^х2+i+roр)(Ф^х1+roр).

Раскрывая скобки и сокращая одинаковые члены в левой и правой частях равенства, получаем

р (Ф^x1+i+roФ^x2+r)= р(Ф^x2+i+roФ^x1+r)

Поскольку р - ненулевой элемент, то отсюда вытекает, что

Ф^x1+r(Фⁱ㊀ 1)= Ф^x2+r(Фⁱ㊀ 1)

Поскольку i – произвольный ненулевой элемент Z/N, а Ф - примитивный элемент GF(N+1), то Фⁱ1, откуда вытекает, что х₁=х₂.■

Теорема 2. Пусть П – логарифмическая подстановка.

Тогда для любого ненулевого значения iЄZ/N\{0} из условия, что ни одна из точек x, x+i не является выколотой вытекает, что П(х+i)- П(x)  i.

Доказательство.

Пусть П(х+i)- П(x) = i. Тогда Ф^{П(х+i)- П(x)}= Фⁱ, откуда Ф^x+r+ioр=Фⁱ(Ф^x+roр), следовательно, р=рФⁱ. Отсюда следует, что i=0. ■

Раскинулось поле широко! Операции возведения в степень и логарифмирования в конечном поле позволили ловко избавиться от неопределенности в разности значений подстановки и легко, просто элементарно решить задачу построения матрицы P(П) с минимальным числом нулей. Заметим, что если в определении логарифмических подстановок отказаться от условия, что р - произвольный ненулевой элемент поля GF(N+1), то при р=0 мы получаем обычные линейные подстановки, у которых число нулей в P(П) максимально!

Осталось совсем чуть-чуть: разобраться с выколотой точкой.

Для произвольного ненулевого фиксированного iЄZ/N рассмотрим отображение множества Z/N в Z/N вида:

M_i(х) = П(х+i)- П(х),

где П - логарифмическая подстановка. Тогда, в силу теоремы 1, количество различных значений в множестве {M_i(х), xЄZ/N\{x₀,x₀-i}}равно мощности этого множества, т.е.N-2, причем, в силу теоремы 2, это множество в точности совпадает с {Z/N\{i}}. В частности, при любом iN/2 существует такое значение х, xЄZ/N\{x₀,x₀-i}, что M_i(х)=N/2.

Теорема 3. Пусть П – логарифмическая подстановка.

Тогда если при некотором iN/2 в i-ой строке матрицы P(П) справедливо p_iN/2gt;1, то эта строка не содержит нулевых элементов.

Доказательство.

В силу теоремы 2 достаточно доказать, что p_ii0. Условие p_iN/2gt;1означает, что либо M_i(х₀)=N/2, либо M_i(х₀-i)=N/2. Зафиксируем то, которое равно N/2, а другое оставшееся значение обозначим через M. Суммируя, как и ранее мы уже делали в этой книге, значения M_i(х) по всем xЄZ/N, получаем:

N/2(N-1) – i + M + N/2 = 0.

Отсюда вытекает, что M=i, следовательно, p_ii0. ■

По коням! Пора заняться средней строчкой.

Начнем с самого любимого элемента – p_N/2,N/2. Ранее мы уже отмечали, что этот элемент должен быть всегда четным (рассуждения для случая N=2ⁿ легко обобщаются для произвольного четного N). Следовательно, в логарифмической подстановке возможны только два значения p_N/2,N/2: 0 или 2. Допустим, что p_N/2,N/2=2. В силу теоремы 2 эти значения может давать только выколотая точка x₀ и x₀+N/2, т.е.

П(х₀+N/2)- П(х₀)= П(х₀+N/2+N/2)- П(х₀+N/2)= П(х₀)- П(х₀+N/2)=N/2.

Отсюда вытекает, что 2П(х₀+N/2)=2П(х₀).

Рассмотрим два случая.

1. р=1, следовательно, П(х₀)=0. Тогда П(х₀+N/2)=N/2. Имеем:

Ф^П(х0+N/2)= Ф^N/2 Ф^x0+N/2+roр=Ф^N/2  Ф^N/2(1㊀ Ф^x0+r)= р  Ф^N/2(1oр)= р 2Ф^N/2 = 1.

Возводя обе части последнего равенства в квадрат и учитывая, что Ф^N=1, получаем такое равенство возможно только в тривиальном поле из 3 элементов.

2. р1, следовательно, П(х₀) =N/2, П(х₀+N/2)=0, откуда

Ф^П(х0+N/2)= 1 Ф^x0+N/2+roр=1  р(1㊀ Ф^N/2)= 1  Ф^N/2= 1㊀ р^-1.

Возводя это равенство в квадрат, получаем значение р:

р=2^-1

С учетом условия П(х₀) =N/2 получаем: log_Ф2^-1 = N/2, откуда 2^-1 =Ф^N/22^-2 =1. Такое также возможно только в тривиальном поле из 3 элементов.

Следовательно, во всех реальных практически значимых случаях p_N/2,N/2=0. Тогда найдется по крайней мере одна строка i, в которой p_N/2,i2, и по теореме 3 в ней не будет нулей. Общее число нулей в такой матрице, с учетом уже упоминавшейся ее симметричности, будет равно N-3. Это минимально возможное количество нулей и оно оказалось достижимым!

Заметим, что подстановка, обратная к логарифмической, также будет логарифмической. Действительно, если П(х) = log_Ф(Ф^x+roр), то Ф^{П (х)}= Ф^x+roр, откуда

х= log_Ф(Ф^{П (х)-r}oр₁), где р₁ = (㊀ р)Ф^-r. Следовательно, П^-1П(х) = log_Ф(Ф^{П (х)-r}oр₁). При этом Ф^{П (х)-r}oр₁=(Ф^x+roр)Ф^-roр₁=Ф^x  0. Для случая х=х₀ справедливо: П(х₀)= log_Фр, при этом Ф^x0=(㊀ р)Ф^-r, откуда х₀ = П^-1П(х₀) = log_Ф((㊀ р)Ф^-r) = log_Фр₁

Осталось построить в явном виде логарифмическую подстановку. Заметим, что условие N+1 – простое число выполняется для практически очень важного случая N=256, следовательно, логарифмические подстановки заведомо существуют при N=256. Условию N+1 - простое число удовлетворяет также N=16 и именно для этого значения мы сейчас и построим логарифмические подстановки, предоставляя заинтересованному читателю возможность построить логарифмические подстановки при N=256 самостоятельно.

В качестве примитивного элемента поля GF(17) выберем Ф=3, а также положим р=1, r=0. Составим таблицу степеней значения Ф:

Используя эту таблицу, построим логарифмическую подстановку П

и ее матрицу Р(П)

Это подстановка с минимально возможным числом нулей в матрице Р(П).

Это был, пожалуй, мой самый красивый математический результат. Но, к большому сожалению, логарифмические подстановки так и не нашли достойного применения в криптографии. Почему? Да очень просто – их мало. Помните фразу про долговременные ключи-подстановки в дисковых шифраторах: «Их не опробуют. Их покупают.» Если в схемы типа «Ангстрем-3» мы будем ставить только логарифмические подстановки, то опробование всевозможных вариантов подобных подстановок сведется к опробованию всего лишь трех элементов: Ф - примитивного элемента в поле Галуа GF(257), р - произвольного ненулевого элемента поля GF(257) и r – произвольного элемента из Z/256. Это – копейки, совершенно ничтожная, по криптографическим меркам, величина. Если же выбирать подстановку случайно и равновероятно из всей симметрической группы S₂₅₆, то общее число опробуемых вариантов будет совершенно астрономической величиной 256!, намного превосходящей психологически недосягаемую в криптографии величину 10¹⁰⁰.

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

Для меня же это означало еще и то, что путь к защите диссертации был открыт, несмотря на пессимистические прогнозы Степанова и проповедуемый им «патриотизм к отделу». Но на Степанова они подействовали не как на ученого, а как на администратора: красивый математический результат получен вышедшим из под его контроля сотрудником «на стороне», на кафедре криптографии Высшей Школы КГБ. Незамедлительно последовали выводы: наказать, чтобы не высовывался и чтобы другим неповадно было изменять родному отделу! Впрочем, об этом чуть ниже.