Текст книги "Криптография и свобода"
Автор книги: Михаил Масленников
сообщить о нарушении
Текущая страница: 11 (всего у книги 23 страниц)
Глава 2. Каждый чекист – коммунист
Если раньше, в период моей учебы в качестве слушателя 4 факультета, основными единицами измерения нашей жизни были «учебная группа» и «начальник курса», то теперь, попав почти через три года после окончания факультета на него снова в качестве аспиранта, я одновременно попал в иное измерение, где основными понятиями были уже «кафедра» и «инспектор отдела аспирантуры». Вот тут самое время познакомить читателя с этими изначальными, иногда математическими, а иногда и нет, понятиями.
На 4 факультете было несколько профильных кафедр, из которых наиболее видное и значимое место занимали кафедра математики и кафедра криптографии. Впоследствии к этим двум лидерам примкнула еще кафедра вычислительной техники, но это все же произошло несколько позже, а тогда, в середине 80-х годов, соотношение было именно таким. Очень многие преподаватели с этих кафедр сами в прошлом окончили 4 факультет и насквозь пропитались теми традициями, которые были заложены его основателями, поэтому мое появление в качестве аспиранта кафедры криптографии не было для меня какой-то резкой сменой обстановки: многие знакомые лица, бывшие сокурсники – теперь уже аспиранты. На кафедре криптографии было около 10 аспирантов-очников, каждое ведомство: 8 ГУ, 16 управление КГБ, Министерство обороны – каждый год направляло в среднем по одному человеку на учебу в трехгодичную очную аспирантуру, а кафедра математики старалась отбирать себе аспирантов из наиболее способных слушателей, заканчивающих факультет. Аспиранты этих двух кафедр составляли, как правило, свободолюбивое сообщество, жившее по университетским традициям, не всегда совпадавшими с распоряжениями начальника той или иной кафедры, к примеру, с распоряжением отмечаться каждый день в специальном журнале прихода и ухода, или с распоряжением ходить в военной форме. Практически у всех аспирантов кафедры криптографии военная форма (облегченный вариант) висела на вешалке в аспирантской комнате и в редкие присутственные дни там же происходило переодевание, ибо желающих разгуливать в военной форме по городу практически не было.
У аспирантов теоретически было два начальства: руководство кафедры и руководство специального отдела аспирантуры, которому должны были подчиняться вообще все аспиранты Высшей школы КГБ, в которую в те времена 4 факультет, еще не добившийся тогда независимости, входил на правах «союзной республики». Но поскольку 4 факультет составлял все же сравнительно небольшую часть всей Высшей школы, то и отдел аспирантуры интересовался аспирантами-математиками «сквозь пальцы», ограничивая, как правило, свое влияние тем, что мы должны были раз в месяц посещать проводимое им общее собрание аспирантов Высшей школы, да присутствием на 4 факультете специального инспектора отдела аспирантуры. Но этот человек сильно отличался от прежнего, знакомого уже читателю, нашего бывшего начальника курса Чуды тем, что до мозга костей был бюрократом, которого не интересовало ничего, кроме выполнения индивидуального плана работы аспиранта-очника. Тут уже не было таких красочных афоризмов, такого страстного желания сделать невозможное – из математиков – хороших военных, одна лишь скучная повседневность:
– Сколько процентов диссертации у Вас готово?
Так что такой начальник справедливо считался аспирантами, прошедшими чудесную школу, несерьезным, а руководству кафедры всегда была готова отмазка: «Мы подчиняемся распорядку, установленному отделом аспирантуры». Вот она, долгожданная свобода!
Но аспиранты по-прежнему оставались военнослужащими, офицерами и получали соответствующее денежное довольствие. Аспирантура называлась целевая, на практике это означало, что то подразделение, которое направило офицера в очную аспирантуру, сохраняло за ним все денежное довольствие – оклады по должности и званию, ежегодную компенсацию за неиспользованную военную форму, тринадцатую зарплату, компенсацию за продовольственные пайки и может быть даже что-то еще, что сейчас, по истечении 20 лет с того времени, я уже мог и подзабыть. Все вместе аспирантское денежное довольствие получалось по тем советским временам достаточно приличным: где-то около 300 рублей в месяц, при этом появлялась масса свободного времени, фактически не было ежедневного обязательного отбывания в аспирантуре, все офицерские мероприятия вроде суточных нарядов и партийных собраний были разовыми и казались не слишком обременительными. Про партийные собрания, да и вообще про партийную жизнь в специфических условиях КГБ, стоит, пожалуй, сказать несколько слов подробнее.
По определению, данному кем-то из революционных вождей, все офицеры КГБ должны были быть коммунистами. Офицер КГБ, достигавший предельного комсомольского возраста, чуть ли не автоматом принимался в КПСС, случаи отказа означали почти что измену Родине и, поэтому, на практике были только в очень экзотических ситуациях. По крайней мере. в 8 ГУ и в Высшей школе КГБ таких ситуаций (беспартийный офицер) я сейчас вспомнить не могу. Какой в этом был смысл? По-видимому, дополнительный рычаг влияния на человека. Любое движение по службе, защита диссертации, оформление в загранкомандировку и всякое иное действие офицера всегда сопровождались написанием служебно-партийной характеристики, в которой непременно должна была присутствовать фраза: «Делу Коммунистической Партии и социалистической Родине предан». Эта фраза была одним из многочисленных социалистических обрядов, которым, по большому счету, мало кто придавал значение, но в конечном итоге смысл был один: без положительной служебно-партийной характеристики в КГБ работать нельзя. Но, помимо обрядов, для чего еще нужна была партийная организация, например, в Теоретическом отделе Спецуправления? Тут я постараюсь привести на этот счет свои «заметки фенолога», хотя этот вопрос также иногда дискутировался между любителями дискуссий и споров, но, правда, в те времена не особо шибко.
Во-первых, в любом научном, да и не только научном, коллективе всегда есть какие-то конфликтующие группы, непримиримые оппоненты, вечно всем недовольные, просто любители поговорить. Обычно выяснением отношений занимаются в курилках, в каких-то изолированных местах, по дороге на работу и с работы, иногда даже в выходные дни, особенно если на эти дни выпадает субботник или воскресник. Но это все – товарищеские игры, неофициальные выступления, тренировочные матчи. Партийное собрание – это официальный чемпионат отдела, со своей турнирной таблицей – протоколами партийных собраний, регулярно подшиваемыми в специальное дело. Не всякий прием, отрабатываемый в тренировочных матчах, может затем быть с успехом использован в официальных встречах, но общий показатель настроений в умах сотрудников Теоретического отдела Спецуправления протоколы партийных собраний отражали достаточно верно. А судейская коллегия – руководство отдела, отдел кадров – затем всегда могла выставить свои, финальные оценки и назвать имена победителей и проигравших.
Во-вторых, над руководством отдела стоит руководство Спецуправления, которому, в свою очередь, нужно оценивать руководителей отделов и для такой оценки есть очень простой и понятный критерий – количество «черных шаров», поданных против начальника отдела на закрытых выборах в партбюро. Здесь несколько слов для современных читателей о том, что такое партбюро. Все сотрудники отдела, достигшие (или даже еще не достигшие, но очень шустрые) предельного комсомольского возраста – 28 лет, были коммунистами. А коммунисты, согласно Уставу КПСС, образовывали на каждом предприятии первичную партийную организацию, которая обязательно раз в месяц проводила партийное собрание, а раз в год выбирала тайным голосованием партбюро – наиболее достойных коммунистов, которые затем руководили всей партийной работой в течение года. Что такое партийная работа? Это, в первую очередь, подготовка месячных партийных собраний (чтобы дискуссия на них велась в рамках заданной темы и в пределах партийных приличий), а также составление многочисленных планов и отчетов, направляемых в вышестоящие партийные инстанции. Во-вторых, это сбор партийных взносов, превращавшийся в стихийное бедствие для сотрудников, сидящих в одной комнате с осуществлявшим этот сбор секретарем партбюро. В Теоретическом отделе Спецуправления к партийной работе неизбежно примыкали различные криптографические дискуссии, выносимые затем на очередное партсобрание, поэтому начальник отдела по определению должен был состоять в партбюро.
При социализме всенародные выборы депутатов были безальтернативными, за кандидатов нерушимого блока коммунистов и беспартийных всегда голосовало 99,99% избирателей (марксистско-ленинская философия учит, что развитие происходит по спирали, все повторяется, но на более высоком уровне). Однако выборы в партийное бюро Теоретического отдела Спецуправления хоть и были всегда безальтернативными, но «черных шаров» Степанову на них кидали достаточно. Начальник отдела – это арбитр в различных внутриотдельских спорах, если все 100% сотрудников им довольны, то это означает одно – он не имеет собственной точки зрения и соглашается со всеми. Но если количество «черных шаров» приближается к 25%, то это означает, что авторитаризм начальника перевалил через опасную черту. Вот на таких простых и понятных критериях строилась вертикаль власти в Спецуправлении, да и, наверное, во всем КГБ. А партийная организация играла в этом случае роли «измерительного прибора».
Ну и, наконец, третья, но по значимости едва ли не основная роль партийной организации – устрашающая. Любой проступок офицера всегда приводил к разбору его персонального дела на партбюро или партсобрании. Правда, в Теоретическом отделе народ был слишком интеллигентный и до задержания милицией в пьяном виде дело обычно не доходило. А вот на 4 факультете и коммунистов было поболее, и «истинных» начальников хватало, и закалка у них была покрепче, рабоче-крестьянская, так что там уж бывало и ловили по пьянке, и аморальное поведение встречалось, и даже совершалось самое большое преступление – потеря офицерского удостоверения. Вот тут-то уж и разворачивалась вовсю работа партийной организации.
У меня, да и, наверное, у любого другого нормального человека, партийные собрания, если на них не было каких-то экзотических подробностей, вызывали скуку и сон. Но, к счастью, в период моего первого пребывания в отделе Степанова, я еще не дорос до партийного уровня и ходил в комсомольских штанишках – там тоже были собрания, но покороче и поспокойнее. Однако перспектива защиты диссертации и дальнейшего служебного роста привели меня в партийные ряды по категории «шустрый», т.е. чуть раньше положенных 28 лет.
Вступление в партию очень красочно описал Михаил Шолохов в «Поднятой целине», мне тут посоперничать с признанным мастером социалистического реализма явно не удастся. Одно утешает – здесь у нас как бы разные весовые категории. Он описывал вступление в тяжеловесную ВКП(б) времен тридцатых годов, мое же вступление – в легкую весовую категорию КПСС середины 80-х, да и герой Шолохова был абстрактный, комплексное число с ненулевой мнимой частью, а мои воспоминания – самые что ни на есть действительные, я бы даже сказал рациональные значения.
Итак, вступление в КПСС начинается с заявления и рекомендаций, причем все это добро надо написать обязательно перьевой ручкой с фиолетовыми чернилами. Партийная загадка: почему именно фиолетовыми, а не синими, которые более распространены? Нет рационального ответа, по умолчанию предполагаем, что фиолетовые чернила дольше сохраняются в партийных архивах для потомков из третьего тысячелетия, поэтому поиск фиолетовых чернил в советских канцелярских магазинах можно считать первым партийным поручением. Выполнено.
Далее. Текст заявления. Подавляя голос внутреннего разума, приходится писать: «Прошу принять меня в члены КПСС. Хочу быть в первых рядах строителей коммунизма. Устав и Программу КПСС признаю и обязуюсь выполнять». Хорошее это дело – первые ряды строителей коммунизма. Только в соответствии с признаваемой мною Программой КПСС коммунизм должен был быть построен еще 1980 году, а я датирую свое заявление 1983 годом. Три года уже живем при коммунизме? А как выполнять такую Программу? И что делают первые ряды строителей того, что уже построено? Наверное, как и на любой советской стройке – сдали объект, а потом еще три года устраняют недоделки. Но это такие всеобщие партийные игры, видишь черное – пиши белое, иначе не видать защиты диссертации. Да бог с ним, с этим коммунизмом, пусть себе будет, как в сказке про Илью Муромца, уже тридцать лет и три года. Когда эту Программу КПСС принимали, я даже в детский садик еще не ходил и кукурузу за полярным кругом не сеял, нет моей вины в том, что теперь, 22 года спустя, надо писать фиолетовыми чернилами, что признаешь и обязуешься выполнять разные глупости.
Ну а Устав КПСС, продекларированные в нем демократический централизм (современное название – властная вертикаль) и выборность снизу доверху (или сверху донизу, сейчас уже не упомнишь, вроде все-таки снизу, хотя по жизни чаще сверху), все это запоминать? Хороший человек был Костя Максимов, веселый, компанейский, а один абзац из Устава еще можно запомнить.
– Костя, задай мне вопросик по Уставу на партсобрании.
– Какой?
– А вот, про демократический централизм.
Вот так проходила моя подготовка к вступлению в КПСС. Заявление фиолетовыми чернилами, трое рекомендующих меня преподавателей с кафедры криптографии, Костин нужный вопросик в нужное время – и за принятие меня в ряды КПСС партийное собрание 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+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.
Такие подстановки естественно назвать логарифмическими, а точку х, при которой П(х) = logФр – выколотой точкой логарифмической подстановки П.
Здесь и всюду далее нам будут встречаться два разных типа арифметических операций сложения и вычитания: в кольце Z/N и в поле GF(N+1). Операции в кольце Z/N будем обозначать обычными символами “+” и “-“, а операции в поле GF(N+1) – o и ㊀ соответственно.
Теорема 1.
Пусть П – логарифмическая подстановка, х1х2, х1,х2 ЄZ/N, i – произвольный ненулевой элемент кольца Z/N.
Тогда если ни одна из точек х1+i,x1,х2+i,x2 не является выколотой, то П(х1+i)– П(x1) П(х2+i)– П(x2).
Доказательство.
Предположим, что П(х1+i)– П(x1)= П(х2+i)– П(x2), тогда ФП(х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(Фi㊀ 1)= Фx2+r(Фi㊀ 1)
Поскольку i – произвольный ненулевой элемент Z/N, а Ф – примитивный элемент GF(N+1), то Фi1, откуда вытекает, что х1=х2.■
Теорема 2. Пусть П – логарифмическая подстановка.
Тогда для любого ненулевого значения iЄZ/N{0} из условия, что ни одна из точек x, x+i не является выколотой вытекает, что П(х+i)– П(x) i.
Доказательство.
Пусть П(х+i)– П(x) = i. Тогда ФП(х+i)– П(x)= Фi, откуда Фx+r+ioр=Фi(Фx+roр), следовательно, р=рФi. Отсюда следует, что i=0. ■
Раскинулось поле широко! Операции возведения в степень и логарифмирования в конечном поле позволили ловко избавиться от неопределенности в разности значений подстановки и легко, просто элементарно решить задачу построения матрицы P(П) с минимальным числом нулей. Заметим, что если в определении логарифмических подстановок отказаться от условия, что р – произвольный ненулевой элемент поля GF(N+1), то при р=0 мы получаем обычные линейные подстановки, у которых число нулей в P(П) максимально!
Осталось совсем чуть-чуть: разобраться с выколотой точкой.
Для произвольного ненулевого фиксированного iЄZ/N рассмотрим отображение множества Z/N в Z/N вида:
Mi(х) = П(х+i)– П(х),
где П – логарифмическая подстановка. Тогда, в силу теоремы 1, количество различных значений в множестве {Mi(х), xЄZ/N{x,x-i}}равно мощности этого множества, т.е.N-2, причем, в силу теоремы 2, это множество в точности совпадает с {Z/N{i}}. В частности, при любом iN/2 существует такое значение х, xЄZ/N{x,x-i}, что Mi(х)=N/2.
Теорема 3. Пусть П – логарифмическая подстановка.
Тогда если при некотором iN/2 в i-ой строке матрицы P(П) справедливо piN/2>1, то эта строка не содержит нулевых элементов.
Доказательство.
В силу теоремы 2 достаточно доказать, что pii0. Условие piN/2>1означает, что либо Mi(х)=N/2, либо Mi(х-i)=N/2. Зафиксируем то, которое равно N/2, а другое оставшееся значение обозначим через M. Суммируя, как и ранее мы уже делали в этой книге, значения Mi(х) по всем xЄZ/N, получаем:
N/2(N-1) – i + M + N/2 = 0.
Отсюда вытекает, что M=i, следовательно, pii0. ■
По коням! Пора заняться средней строчкой.
Начнем с самого любимого элемента – pN/2,N/2. Ранее мы уже отмечали, что этот элемент должен быть всегда четным (рассуждения для случая N=2n легко обобщаются для произвольного четного N). Следовательно, в логарифмической подстановке возможны только два значения pN/2,N/2: 0 или 2. Допустим, что pN/2,N/2=2. В силу теоремы 2 эти значения может давать только выколотая точка x0 и 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/22-2 =1. Такое также возможно только в тривиальном поле из 3 элементов.
Следовательно, во всех реальных практически значимых случаях pN/2,N/2=0. Тогда найдется по крайней мере одна строка i, в которой pN/2,i2, и по теореме 3 в ней не будет нулей. Общее число нулей в такой матрице, с учетом уже упоминавшейся ее симметричности, будет равно N-3. Это минимально возможное количество нулей и оно оказалось достижимым!
Заметим, что подстановка, обратная к логарифмической, также будет логарифмической. Действительно, если П(х) = logФ(Фx+roр), то ФП (х)= Фx+roр, откуда
х= logФ(ФП (х)-roр1), где р1 = (㊀ р)Ф-r. Следовательно, П-1П(х) = logФ(ФП (х)-roр1). При этом ФП (х)-roр1=(Фx+roр)Ф-roр1=Фx 0. Для случая х=х справедливо: П(х)= logФр, при этом Фx0=(㊀ р)Ф-r, откуда х = П-1П(х) = logФ((㊀ р)Ф-r) = logФр1
Осталось построить в явном виде логарифмическую подстановку. Заметим, что условие 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. Это – копейки, совершенно ничтожная, по криптографическим меркам, величина. Если же выбирать подстановку случайно и равновероятно из всей симметрической группы S256, то общее число опробуемых вариантов будет совершенно астрономической величиной 256!, намного превосходящей психологически недосягаемую в криптографии величину 10100.
Но для шифров на новой элементной базе логарифмические подстановки позволили полнее представить общую картину того «лавинного эффекта», к достижению которого так стремятся криптографы всего мира.
Для меня же это означало еще и то, что путь к защите диссертации был открыт, несмотря на пессимистические прогнозы Степанова и проповедуемый им «патриотизм к отделу». Но на Степанова они подействовали не как на ученого, а как на администратора: красивый математический результат получен вышедшим из-под его контроля сотрудником «на стороне», на кафедре криптографии Высшей Школы КГБ. Незамедлительно последовали выводы: наказать, чтобы не высовывался и чтобы другим неповадно было изменять родному отделу! Впрочем, об этом чуть ниже.
