– Какой?
– А вот, про демократический централизм.
Вот так проходила моя подготовка к вступлению в КПСС. Заявление фиолетовыми чернилами, трое рекомендующих меня преподавателей с кафедры криптографии, Костин нужный вопросик в нужное время – и за принятие меня в ряды КПСС партийное собрание 4 факультета Высшей Ордена Октябрьской Революции Краснознаменной школы КГБ СССР им. Ф.Э.Дзержинского проголосовало единогласно.
От всей дальнейшей партийной жизни на 4 факультете осталось одно воспоминание: аудитория, в которой проходили факультетские партийные собрания. К тому времени факультет расширился, очень бурно развивались кафедры, связанные с вычислительной техникой, народу на факультете заметно прибавилось по сравнению с временами Большого Кисельного. Поэтому на факультетском партсобрании в аудиторию, рассчитанную человек на 100, надо было вместить несколько большее количество коммунистов. Какая же это оказалась удача!
Дело в том, что эта аудитория была наклонным залом, идущим с нижнего этажа на верхний. Внизу был основной вход, дальше – боковые лестницы, ведущие к верхним рядам, а на самом верху – дверь, являвшаяся запасным выходом. Во время партсобраний зал переполнялся и открывали верхнюю запасную дверь, через которую не успевшие занять основных мест тащили себе из других аудиторий стулья, чтобы сидеть на них в проходах. Математическая мысль аспирантов, просидевших пару раз в этой толчее и духоте несколько часов, живо нашла оптимальное криптографическое решение.
Главное в нем было – прийти в нужное время, когда зал уже полон и надо идти за стульями. Отметившись у секретаря о своем присутствии, взгляды аспирантов тоскливо пробегали по переполненному залу и с изображением тяжкой необходимости на лице, но ликующие в душе, мы поднимались на самый верх и отправлялись на поиски дополнительных сидячих мест. Здесь тоже не нужно спешить, партсобрание – не волк, в лес не убежит, к моменту возвращения со стульями в руках забитыми оказывались и все проходы на лестнице. Оставалось (какая жалость!) сесть на принесенные стулья уже около запасной двери, но с другой ее стороны, и не с той, где зал с партсобранием. Но душой мы оставались с коммунистами факультета, с их партийной бескомпромиссностью и пламенным энтузиазмом. Иногда даже аплодировали, чтобы зал, если и не видел, то хотя бы слышал, что и за запасным выходом идет партийная жизнь. Когда же большая часть зала засыпала или просто одуревала от духоты и пустых речей, аспиранты тихонечко покидали свою обособленную галерку.
Это был 1984 год, период правления Черненко. Партия и партийные функционеры доживали свои последние золотые денечки.
Глава 3. Логарифмические подстановки
В этой главе давайте отложим в сторону лирические и понятные всем отступления про обстановку в стране в то время. Мои рассуждения об этом субъективны, кто-то может соглашаться с ними, кто-то, наоборот, считать те времена образцом для подражания на фоне современной криминализации страны. В этой книге я старался следовать криптографически-философскому принципу Шеннона: в шифре чередовать не похожие друг на друга операции перемешивания и сдвига. В качестве операций сдвига – главы, отображающие общую ситуацию в СССР и в КГБ в те, теперь уже далекие времена, а в роли перемешивания выступают главы, в которых много говорится о математике, криптографии или программировании. Сейчас начнется очередная «перемешивающая» глава.
Шифратор «Ангстрем-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+r⊕ρ), если θx+r⊕ρ≠0,
π(х) = logθρ, если θx+r⊕ρ=0,
где ρ - произвольный ненулевой элемент поля GF(N+1), r – произвольный элемент из Z/N, ⊕ - операция сложения в поле GF(N+1). Тогда преобразование π является взаимно-однозначным на множестве Z/N, т.е. является подстановкой из симметрической группы SN.
Это утверждение достаточно очевидно, поскольку θ - примитивный элемент поля GF(N+1), т.е. множество значений θ,θ