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

Предположим, что π(х₁+i)- π(x₁)= π(х₂+i)- π(x₂), тогда θ^{π(х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(θⁱ⊖ 1)= θ^x2+r(θⁱ⊖ 1)

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

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

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

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

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

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

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

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

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

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

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

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

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

В силу теоремы 2 достаточно доказать, что p_ii≠0. Условие p_iN/2>1означает, что либо μ_i(х₀)=N/2, либо μ_i(х₀-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). Следовательно, в логарифмической подстановке возможны только два значения p_N/2,N/2: 0 или 2. Допустим, что p_N/2,N/2=2. В силу теоремы 2 эти значения может давать только выколотая точка x₀ и 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+r⊕ρ=θ^N/2 ⇒ θ^N/2(1⊖ θ^x0+r)= ρ ⇒ θ^N/2(1⊕ρ)= ρ⇒ 2θ^N/2 = 1.

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

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

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

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

ρ=2^-1

С учетом условия π(х₀) =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}⊕ρ₁), где ρ₁ = (⊖ ρ)θ^-r. Следовательно, π^-1π(х) = log_θ(θ^{π (х)-r}⊕ρ₁). При этом θ^{π (х)-r}⊕ρ₁=(θ^x+r⊕ρ)θ^-r⊕ρ₁=θ^x ≠ 0. Для случая х=х₀ справедливо: π(х₀)= log_θρ, при этом θ^x0=(⊖ ρ)θ^-r, откуда х₀ = π^-1π(х₀) = log_θ((⊖ ρ)θ^-r) = log_θρ₁