Осталось построить в явном виде логарифмическую подстановку. Заметим, что условие N+1 – простое число выполняется для практически очень важного случая N=256, следовательно, логарифмические подстановки заведомо существуют при N=256. Условию N+1 - простое число удовлетворяет также N=16 и именно для этого значения мы сейчас и построим логарифмические подстановки, предоставляя заинтересованному читателю возможность построить логарифмические подстановки при N=256 самостоятельно.
В качестве примитивного элемента поля GF(17) выберем θ=3, а также положим ρ=1, r=0. Составим таблицу степеней значения θ:
| i | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 |
| θi | 1 | 3 | 9 | 10 | 13 | 5 | 15 | 11 | 16 | 14 | 8 | 7 | 4 | 12 | 2 | 6 |
Используя эту таблицу, построим логарифмическую подстановку π
| х | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 |
| π(х) | 14 | 12 | 3 | 7 | 9 | 15 | 8 | 13 | 0 | 6 | 2 | 10 | 5 | 4 | 1 | 11 |
и ее матрицу Р(π)
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | |
| 1 | 0 | 1 | 2 | 1 | 1 | 2 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
| 2 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 2 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
| 3 | 2 | 1 | 0 | 1 | 1 | 1 | 1 | 1 | 1 | 2 | 1 | 1 | 1 | 1 | 1 |
| 4 | 1 | 1 | 1 | 0 | 2 | 1 | 2 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
| 5 | 1 | 1 | 1 | 2 | 0 | 1 | 1 | 1 | 2 | 1 | 1 | 1 | 1 | 1 | 1 |
| 6 | 2 | 1 | 1 | 1 | 1 | 0 | 1 | 1 | 1 | 1 | 1 | 1 | 2 | 1 | 1 |
| 7 | 1 | 1 | 1 | 2 | 1 | 1 | 0 | 1 | 1 | 1 | 2 | 1 | 1 | 1 | 1 |
| 8 | 1 | 2 | 1 | 1 | 1 | 1 | 1 | 0 | 1 | 1 | 1 | 1 | 1 | 2 | 1 |
| 9 | 1 | 1 | 1 | 1 | 2 | 1 | 1 | 1 | 0 | 1 | 1 | 2 | 1 | 1 | 1 |
| 10 | 1 | 1 | 2 | 1 | 1 | 1 | 1 | 1 | 1 | 0 | 1 | 1 | 1 | 1 | 2 |
| 11 | 1 | 1 | 1 | 1 | 1 | 1 | 2 | 1 | 1 | 1 | 0 | 2 | 1 | 1 | 1 |
| 12 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 2 | 1 | 2 | 0 | 1 | 1 | 1 |
| 13 | 1 | 1 | 1 | 1 | 1 | 2 | 1 | 1 | 1 | 1 | 1 | 1 | 0 | 1 | 2 |
| 14 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 2 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
| 15 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 2 | 1 | 1 | 2 | 1 | 0 |
Это подстановка с минимально возможным числом нулей в матрице Р(π).
Это был, пожалуй, мой самый красивый математический результат. Но, к большому сожалению, логарифмические подстановки так и не нашли достойного применения в криптографии. Почему? Да очень просто – их мало. Помните фразу про долговременные ключи-подстановки в дисковых шифраторах: «Их не опробуют. Их покупают.» Если в схемы типа «Ангстрем-3» мы будем ставить только логарифмические подстановки, то опробование всевозможных вариантов подобных подстановок сведется к опробованию всего лишь трех элементов: θ - примитивного элемента в поле Галуа GF(257), ρ - произвольного ненулевого элемента поля GF(257) и r – произвольного элемента из Z/256. Это – копейки, совершенно ничтожная, по криптографическим меркам, величина. Если же выбирать подстановку случайно и равновероятно из всей симметрической группы S256, то общее число опробуемых вариантов будет совершенно астрономической величиной 256!, намного превосходящей психологически недосягаемую в криптографии величину 10100.
Но для шифров на новой элементной базе логарифмические подстановки позволили полнее представить общую картину того «лавинного эффекта», к достижению которого так стремятся криптографы всего мира.
Для меня же это означало еще и то, что путь к защите диссертации был открыт, несмотря на пессимистические прогнозы Степанова и проповедуемый им «патриотизм к отделу». Но на Степанова они подействовали не как на ученого, а как на администратора: красивый математический результат получен вышедшим из под его контроля сотрудником «на стороне», на кафедре криптографии Высшей Школы КГБ. Незамедлительно последовали выводы: наказать, чтобы не высовывался и чтобы другим неповадно было изменять родному отделу! Впрочем, об этом чуть ниже.
События в стране стали развиваться экспоненциально быстро по сравнению с брежневским без малого 20-летним правлением.
Андропов – ЧК КПСС – дневные облавы – водка «Андроповка».
Раз в неделю мы встречались с Б.А. и я не мог сдерживать своих эмоций: раскрепощенная аспирантская обстановка, масса свободного времени, дома работается гораздо легче и продуктивнее.
– Вот подождите, поймают Вас где-нибудь в кинотеатре, на дневном сеансе, тогда и будет Вам «свободная обстановка».
Но, по правде говоря, мне это особо не грозило. Не до кинотеатров было, интересная тема диссертации, да и появилась возможность решить семейные проблемы: сидеть дома с маленьким ребенком, ибо устроить в те времена свое чадо в детский сад было, естественно, большой проблемой, а тем более в районе-новостройке.
Диссертация продвигалась достаточно быстро. После появления логарифмических подстановок стало ясно, что она выходит на финишную прямую: «Теоретико-групповые и комбинаторные методы анализа и синтеза блочных шифров, реализуемых с помощью неавтономного регулярного регистра сдвига», специальность 20.03.04 – теоретическая криптография. Б.А. меня всячески поддерживал и к концу первого аспирантского года стало ясно, что вполне реально успеть защитить диссертацию еще в аспирантуре и при этом насладиться всеми прелестями вольной жизни.
Хотя какие это прелести жизни? Утром, когда в магазине мало народу, суметь купить более-менее съедобный кусок мяса, или собирать кучу всяких справок, чтобы встать в бесконечную очередь на улучшение жилищных условий – вот типичные советские прелести. А еще моей страстью стало добывание книг, художественной литературы.
