Криптография и свобода
Шрифт:
Шифратор «Ангстрем-3» был построен в полном соответствии с этим принципом Шеннона: регистр сдвига над Z/256 (операции сдвига), усложненный подстановкой из S256, типичным перемешивающим преобразованием. Перемешивающее преобразование дает столь необходимое в криптографии размножение различий в блоках открытого текста. В общефилософских книгах по криптографии, типа упоминавшейся выше книги Брюса Шнайера «Прикладная криптография», употребляется даже термин «лавинный эффект». Вот соответствующая цитата оттуда.
«… Это называется лавинным эффектом. DES спроектирован
Насколько я представляю себе DES, нигде, ни в одной книге, не было дано точных математических оценок этого «лавинного эффекта». DES так спроектирован и все. А почему он так спроектирован? Остается лишь догадываться, да строить статистические эксперименты, которые подтверждают: да «лавинный эффект» безусловно есть.
Вся прелесть «Ангстрема-3» в том, что в нем для оценки подобного «лавинного эффекта» на 4 факультете и в Спецуправлении еще в конце 70-х годов был разработан строгий математический аппарат, опирающийся на алгебру, на теорию групп, колец и полей. Об этих результатах я уже упоминал в предыдущей главе, посвященной шифрам на новой элементной базе, вот, вкратце, их суть.
1. В шифрах, использующих операции в кольце Z/256 и подстановки П из S256, лавинный эффект определяется матрицей частот встречаемости разностей переходов ненулевых биграмм P(П) размера 255x255.
2. Лавинный эффект будет тем лучше, чем меньше нулей в этой матрице. Хорошими следует считать такие подстановки, матрицы которых, возведенные в квадрат, не содержат нулей.
3. При случайном и равновероятном выборе подстановки из всей симметрической группы S256, общее количество подстановок в которой составляет огромную величину 256! – произведение всех чисел от 1 до 256, вероятность выбрать хорошую подстановку стремится к 1.
4. Существуют примеры самых плохих подстановок, это линейные подстановки.
5. Теоретически подсчитано минимально возможное количество нулей в матрице P(П).
Вопрос же о том, существуют ли подстановки с минимально возможным числом нулей в матрице P(П), оставался открытым до конца 1983 года.
– Работайте дома. Если Вы будете часто здесь появляться, то диссертации не напишите.
Так напутствовал меня мой научный руководитель Б.А., который сам заканчивал 4 факультет в числе первых его выпускников, а сейчас уже защитил докторскую диссертацию и жил в мире групп, колец и полей. Это был бальзам на мою душу! Нет этого бессмысленного высиживания до 6 часов вечера, пустых разговоров ни о чем, нет смертельно опасной столовой-травиловки. Мысли раскрепощены, нет интеллектуального насилия, все проблемы, казавшиеся неразрешимыми, вдруг как-то сами стали успешно разрешаться. А что за проблемы?
Итак, мои творческие планы связаны с шифрами на новой элементной базе. Это новая тема и непаханое поле для деятельности. Основное отличие этих шифров от традиционных балалаек – наличие в них подстановки (или даже нескольких подстановок) из S256. Эти подстановки определяют криптографические качества шифров, они же дают возможность строить очень простые и высокоскоростные схемы, поэтому фундаментальные исследования шифров на новой элементной базе нужно начинать с изучения подстановок. Нужно постараться получить наиболее полную картину их свойств, ответить на типовые вопросы, например:
–
– как описать какие-то особенные классы подстановок и в чем будет их особенность;
– как лучше использовать подстановку в схеме, где ее целесообразнее расположить и почему;
И, наконец, надо попробовать дать ответ на конкретный практический вопрос: а что же делать со схемой «Ангстрем-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, т.е. является подстановкой из симметрической группы SN.
Это утверждение достаточно очевидно, поскольку Ф – примитивный элемент поля GF(N+1), т.е. множество значений Ф,Ф2,…,ФN совпадает со множеством {1,2,…,N} – мультипликативной группой поля GF(N+1), а логарифмирование – операция, обратная возведению в степень. Все проблемы с нулем подправляются вторым условием: П(х) = logФр, если Фx+roр=0.