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

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

– как описать какие-то особенные классы подстановок и в чем будет их особенность;

– как лучше использовать подстановку в схеме, где ее целесообразнее расположить и почему;

И, наконец, надо попробовать дать ответ на конкретный практический вопрос: а что же делать со схемой «Ангстрем-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р).

Раскрывая скобки и сокращая одинаковые члены в левой и правой частях равенства, получаем


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