Михаил Масленников - Криптография и свобода
Это утверждение достаточно очевидно, поскольку θ - примитивный элемент поля GF(N+1), т.е. множество значений θ,θ2,…,θN совпадает со множеством {1,2,…,N} – мультипликативной группой поля GF(N+1), а логарифмирование – операция, обратная возведению в степень. Все проблемы с нулем подправляются вторым условием: π(х) = logθρ, если θx+r⊕ρ=0.
Такие подстановки естественно назвать логарифмическими, а точку х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,x1,х2+i,x2 не является выколотой, то π(х1+i)- π(x1)≠ π(х2+i)- π(x2).
Доказательство.
Предположим, что π(х1+i)- π(x1)= π(х2+i)- π(x2), тогда θπ(х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{x0,x0-i}}равно мощности этого множества, т.е.N-2, причем, в силу теоремы 2, это множество в точности совпадает с {Z/N{i}}. В частности, при любом i≠N/2 существует такое значение х, x∈Z/N{x0,x0-i}, что μi(х)=N/2.
Теорема 3. Пусть π – логарифмическая подстановка.
Тогда если при некотором i≠N/2 в i-ой строке матрицы P(π) справедливо piN/2>1, то эта строка не содержит нулевых элементов.
Доказательство.
В силу теоремы 2 достаточно доказать, что pii≠0. Условие piN/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, следовательно, pii≠0. ■
По коням! Пора заняться средней строчкой.
Начнем с самого любимого элемента – pN/2,N/2. Ранее мы уже отмечали, что этот элемент должен быть всегда четным (рассуждения для случая N=2n легко обобщаются для произвольного четного N). Следовательно, в логарифмической подстановке возможны только два значения pN/2,N/2: 0 или 2. Допустим, что pN/2,N/2=2. В силу теоремы 2 эти значения может давать только выколотая точка x0 и x0+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 элементов.
Следовательно, во всех реальных практически значимых случаях pN/2,N/2=0. Тогда найдется по крайней мере одна строка i, в которой pN/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. Составим таблицу степеней значения θ:
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Это подстановка с минимально возможным числом нулей в матрице Р(π).
