Михаил Масленников - Криптография и свобода

Такие подстановки естественно назвать логарифмическими , а точку х 0, при которой π(х 0) = log θρ – выколотой точкой логарифмической подстановки π.

Здесь и всюду далее нам будут встречаться два разных типа арифметических операций сложения и вычитания: в кольце Z/N и в поле GF(N+1). Операции в кольце Z/N будем обозначать обычными символами “+” и “-“, а операции в поле GF(N+1) – ⊕ и ⊖ соответственно.

Теорема 1.

Пусть π – логарифмическая подстановка, х 1≠х 2, х 1,х 2∈ Z/N, i – произвольный ненулевой элемент кольца Z/N.

Тогда если ни одна из точек х 1+i,x 1,х 2+i,x 2не является выколотой, то π(х 1+i)- π(x 1)≠ π(х 2+i)- π(x 2).

Доказательство.

Предположим, что π(х 1+i)- π(x 1)= π(х 2+i)- π(x 2), тогда θ π(х1+i)- π(x1)=θ π(х2+i)- π(x2).

Поскольку все точки не являются выколотыми, то отсюда вытекает, что (θ х1+i+r⊕ρ)(θ х2+r⊕ρ)=(θ х2+i+r⊕ρ)(θ х1+r⊕ρ).

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

ρ (θ x1+i+r⊕θ x2+r)= ρ(θ x2+i+r⊕θ x1+r)

Поскольку ρ - ненулевой элемент, то отсюда вытекает, что

θ x1+r(θ i⊖ 1)= θ x2+r(θ i⊖ 1)

Поскольку i – произвольный ненулевой элемент Z/N, а θ - примитивный элемент GF(N+1), то θ i≠1, откуда вытекает, что х 1=х 2.■

Теорема 2. Пусть π – логарифмическая подстановка.

Тогда для любого ненулевого значения i∈Z/N\{0} из условия, что ни одна из точек x, x+i не является выколотой вытекает, что π(х+i)- π(x) ≠ i.

Доказательство.

Пусть π(х+i)- π(x) = i. Тогда θ π(х+i)- π(x)= θ i, откуда θ x+r+i⊕ρ=θ i(θ x+r⊕ρ)ρ, следовательно, ρ=ρθ i. Отсюда следует, что i=0. ■

Раскинулось поле широко! Операции возведения в степень и логарифмирования в конечном поле позволили ловко избавиться от неопределенности в разности значений подстановки и легко, просто элементарно решить задачу построения матрицы P(π) с минимальным числом нулей. Заметим, что если в определении логарифмических подстановок отказаться от условия, что ρ - произвольный ненулевой элемент поля GF(N+1), то при ρ=0 мы получаем обычные линейные подстановки, у которых число нулей в P(π) максимально!

Осталось совсем чуть-чуть: разобраться с выколотой точкой.

Для произвольного ненулевого фиксированного i∈Z/N рассмотрим отображение множества Z/N в Z/N вида:

μ i(х) = π(х+i)- π(х),

где π - логарифмическая подстановка. Тогда, в силу теоремы 1, количество различных значений в множестве {μ i(х), x∈Z/N\{x 0,x 0-i}}равно мощности этого множества, т.е.N-2, причем, в силу теоремы 2, это множество в точности совпадает с {Z/N\{i}}. В частности, при любом i≠N/2 существует такое значение х, x∈Z/N\{x 0,x 0-i}, что μ i(х)=N/2.

Теорема 3. Пусть π – логарифмическая подстановка.

Тогда если при некотором i≠N/2 в i-ой строке матрицы P(π) справедливо p iN/2>1, то эта строка не содержит нулевых элементов.

Доказательство.

В силу теоремы 2 достаточно доказать, что p ii≠0. Условие p iN/2>1означает, что либо μ i(х 0)=N/2, либо μ i(х 0-i)=N/2. Зафиксируем то, которое равно N/2, а другое оставшееся значение обозначим через μ. Суммируя, как и ранее мы уже делали в этой книге, значения μ i(х) по всем x∈Z/N, получаем:

N/2(N-1) – i + μ + N/2 = 0.

Отсюда вытекает, что μ=i, следовательно, p ii≠0. ■

По коням! Пора заняться средней строчкой.

Начнем с самого любимого элемента – p N/2,N/2. Ранее мы уже отмечали, что этот элемент должен быть всегда четным (рассуждения для случая N=2 nлегко обобщаются для произвольного четного N). Следовательно, в логарифмической подстановке возможны только два значения p N/2,N/2: 0 или 2. Допустим, что p N/2,N/2=2. В силу теоремы 2 эти значения может давать только выколотая точка x 0и x 0+N/2, т.е.

π(х 0+N/2)- π(х 0)= π(х 0+N/2+N/2)- π(х 0+N/2)= π(х 0)- π(х 0+N/2)=N/2.

Отсюда вытекает, что 2π(х 0+N/2)=2π(х 0).

Рассмотрим два случая.

1. ρ=1, следовательно, π(х 0)=0. Тогда π(х 0+N/2)=N/2. Имеем:

θ π(х0+N/2)= θ N/2⇒ θ x0+N/2+r⊕ρ=θ N/2⇒ θ N/2(1⊖ θ x0+r)= ρ ⇒ θ N/2(1⊕ρ)= ρ⇒ 2θ N/2= 1.

Возводя обе части последнего равенства в квадрат и учитывая, что θ N=1, получаем такое равенство возможно только в тривиальном поле из 3 элементов.

2. ρ≠1, следовательно, π(х 0) =N/2, π(х 0+N/2)=0, откуда

θ π(х0+N/2)= 1⇒ θ x0+N/2+r⊕ρ=1 ⇒ ρ(1⊖ θ N/2)= 1 ⇒ θ N/2= 1⊖ ρ -1.

Возводя это равенство в квадрат, получаем значение ρ:

ρ=2 -1

С учетом условия π(х 0) =N/2 получаем: log θ2 -1= N/2, откуда 2 -1=θ N/2⇒2 -2=1. Такое также возможно только в тривиальном поле из 3 элементов.

Следовательно, во всех реальных практически значимых случаях p N/2,N/2=0. Тогда найдется по крайней мере одна строка i, в которой p N/2,i≥2, и по теореме 3 в ней не будет нулей. Общее число нулей в такой матрице, с учетом уже упоминавшейся ее симметричности, будет равно N-3. Это минимально возможное количество нулей и оно оказалось достижимым!

Заметим, что подстановка, обратная к логарифмической, также будет логарифмической. Действительно, если π(х) = log θ(θ x+r⊕ρ), то θ π (х)= θ x+r⊕ρ, откуда

х= log θ(θ π (х)-r⊕ρ 1), где ρ 1= (⊖ ρ)θ -r. Следовательно, π -1π(х) = log θ(θ π (х)-r⊕ρ 1). При этом θ π (х)-r⊕ρ 1=(θ x+r⊕ρ)θ -r⊕ρ 1=θ x≠ 0. Для случая х=х 0справедливо: π(х 0)= log θρ, при этом θ x0=(⊖ ρ)θ -r, откуда х 0= π -1π(х 0) = log θ((⊖ ρ)θ -r) = log θρ 1

Осталось построить в явном виде логарифмическую подстановку. Заметим, что условие N+1 – простое число выполняется для практически очень важного случая N=256, следовательно, логарифмические подстановки заведомо существуют при N=256. Условию N+1 - простое число удовлетворяет также N=16 и именно для этого значения мы сейчас и построим логарифмические подстановки, предоставляя заинтересованному читателю возможность построить логарифмические подстановки при N=256 самостоятельно.

В качестве примитивного элемента поля GF(17) выберем θ=3, а также положим ρ=1, r=0. Составим таблицу степеней значения θ:

Используя эту таблицу, построим логарифмическую подстановку π

и ее матрицу Р(π)

Это подстановка с минимально возможным числом нулей в матрице Р(π).