Криптография и свобода - Масленников Михаил (читать книги онлайн полные версии txt) 📗

Это был 1984 год, период правления Черненко. Партия и партийные функционеры доживали свои последние золотые денечки.

Глава 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_Фр – выколотой точкой логарифмической подстановки П.