Криптография и свобода

ОглавлениеДобавить в закладки К обложке

Следовательно, во всех реальных практически значимых случаях pN/2,N/2=0. Тогда найдется по крайней мере одна строка i, в которой pN/2,i2, и по теореме 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.

Но для шифров на новой элементной базе логарифмические подстановки позволили полнее представить общую картину того «лавинного эффекта», к достижению которого так стремятся криптографы всего мира.

Для меня же это означало еще и то, что путь к защите диссертации был открыт, несмотря на пессимистические прогнозы Степанова и проповедуемый им «патриотизм к отделу». Но на Степанова они подействовали не как на ученого, а как на администратора: красивый математический результат получен вышедшим из-под его контроля сотрудником «на стороне», на кафедре криптографии Высшей Школы КГБ. Незамедлительно последовали выводы: наказать, чтобы не высовывался и чтобы другим неповадно было изменять родному отделу! Впрочем, об этом чуть ниже.


-= 77 =-
Регистрация.
Забыли пароль?
Логин
Пароль
Запомнить меня