close

Вход

Забыли?

вход по аккаунту

?

Свойства некоторых алгоритмов шифрования Фейстеля относительно двух групп сплетения.

код для вставкиСкачать
ПРИКЛАДНАЯ ДИСКРЕТНАЯ МАТЕМАТИКА
2008
Математические методы криптографии
№ 2(2)
УДК 519.7
СВОЙСТВА НЕКОТОРЫХ АЛГОРИТМОВ ШИФРОВАНИЯ ФЕЙСТЕЛЯ
ОТНОСИТЕЛЬНО ДВУХ ГРУПП СПЛЕТЕНИЯ1
М.А. Пудовкина
Московский инженерно-физический институт (государственный университет)
E-mail: maricap@rambler.ru
Одной из наиболее часто встречающихся конструкций, применяемой при синтезе блочных алгоритмов
шифрования, является схема Фейстеля. В работе исследуются свойства некоторых алгоритмов шифрования на основе схемы Фейстеля относительно двух групп сплетений. Описаны слабости такого класса алгоритмов шифрования.
Ключевые слова: алгоритм шифрования Фейстеля, сплетения групп подстановок, импримитивная
группа.
Одной из наиболее часто встречающихся конструкций, применяемых при синтезе блочных алгоритмов
шифрования, является схема Фейстеля. Напомним (см., например, [1]), что схема Фейстеля задается преобразованием g πk : Vm × Vm → Vm × Vm , g πk : (α, β) → (β, βπk ⊕ α) , где Vm – множество всех m-мерных двоичных
векторов над полем GF(2), πk:Vm→ Vm, k∈Vm, ⊕ – операция векторного сложения в Vm. Преобразование πk зависит от ключа k. Алгоритмы шифрования на основе схемы Фейстеля будем называть алгоритмами шифрования Фейстеля.
Групповые свойства алгоритмов шифрования Фейстеля приведены, например, в работах [2 – 4]. Так, в [4]
рассматривался случай, когда подстановка πk принадлежит импримитивной группе, и строилась система
блоков импримитивности для алгоритма шифрования DES с измененными s-боксами.
Две импримитивные группы S2 ∫ S2n −1 и S2n −1 ∫ S2 большого порядка, которые максимально близки к
примитивным группам, неоднократно возникали в различных смежных областях, например в работе [5] при
классификации групп автоморфизмов графов орбиталов подсхем схемы Хемминга и в работе [6]. Поэтому
представляет интерес рассмотреть свойства алгоритмов шифрования Фейстеля с подстановкой πk, принадлежащей двум этим группам.
В данной работе исследуются свойства алгоритмов шифрования Фейстеля таких, что
{
}
π ∈ S2 ∫ S2m −1 , S2m −1 ∫ S2 , а β
πk
∈ {(β ⊕ k )π , βπ ⊕ k} для всех k, β∈Vm. Описаны слабости такого класса алго-
ритмов шифрования. Получено, что если π ∈ S2m −1 ∫ S2 , то по шифртексту возможно получить некоторую
информацию об открытом тексте без знания ключа. Если же π ∈ S2 ∫ S2m −1 , то на множестве ключей можно
ввести отношение эквивалентности, и задача определения ключа сводится к проблеме нахождения какогонибудь представителя из класса эквивалентности, которому принадлежит ключ.
Всюду ниже придерживаемся следующих обозначений: S(X) – симметрическая группа подстановок на
множестве X, N – множество натуральных чисел; m∈N; n = 2m; a, b = a, a + 1,..., b , a < b;
Φ n = { f π ∈ S (Vm × Vm ) | f π : (α, β) → (β, βπ ⊕ α)} – множество алгоритмов шифрования Фейстеля; e – тождественная подстановка, gs =s–1gs для подстановок g, s∈S(X).
Будем отождествлять 2-адическое представление элемента a с представлением его в виде двоичного вектора.
1. Свойства алгоритмов шифрования Фейстеля относительно группы S2 ∫ S m −1
2
Если подстановка π∈S(Vm) фиксирована, f πk ∈ Φ n и α
πk
∈ {(α ⊕ k )π , α π ⊕ k } для любого α∈Vm, то будем
использовать обозначение fk = fπk.
Рассмотрим двоичную последовательность a = a1a2 ,...,
⎧1, если i ≡ 1, 2 (mod3),
ai = ⎨
⎩0, если i ≡ 0 (mod3),
являющуюся решением рекуррентного соотношения ai = ai–1⊕ ai–2 в GF(2), a0 = 0, a1 = 1, i = 2, 3, …
1
Работа выполнена при поддержке гранта Президента РФ НШ №4.2008.10.
Свойства некоторых алгоритмов шифрования Фейстеля
Утверждение 1. Пусть π ∈ S2 ∫ S2m −1 , f k ∈ Φ n , α
πk
59
∈ {(α ⊕ k )π , α π ⊕ k } для любого k∈Vm. Тогда
1) πk ∈ S2 ∫ S2m −1 для любого k∈Vm;
l
2) (α, β)
∏ f k ⊕θi
i =1 i
l
где l∈N,
∏ f ki
(α, β)i =1
l −1
l
⎛
⎞
= ⎜ α (l ) ⊕ ∑ al −i θi , β(l ) ⊕ ∑ al −i +1θi ⎟ ,
⎝
⎠
i =1
i =1
(1)
= (α (l ) , β(l ) ) и θi ∈ {0,1} , i = 1, l .
Доказательство. 1) Включение s ∈ S2 ∫ S2m −1 выполняется тогда и только тогда, когда (α ⊕ 1) s = α s ⊕ 1
для любого α∈Vm. Очевидно, что (α ⊕ 1)π ⊕ k = (α ⊕ k ) π ⊕ 1 для любого k∈Vm. Следовательно,
πk ∈ S2 ∫ S2m −1 .
2) Пусть θi ∈ {0,1} , i = 1, 2,… Рассмотрим последовательность yi = yi–1 ⊕ yi–2 ⊕ θi, y0 = y–1=0, i = 1, 2, …
i
Методом математической индукции нетрудно показать, что yi = ∑ ai − j +1θ j .
j =1
Равенство
l
(α, β)
∏ f k ⊕θi
i =1 i
(
= α (l ) ⊕ yl −1 , β(l ) ⊕ yl
)
доказывается применением метода математической индукции с учетом следующих соотношений:
⎧⎪(β, ((k ⊕ θ1 ) ⊕ β)π ⊕ α)
f
π
π
= (β, β k ⊕ α ⊕ θ1 ) =
(α, β) k ⊕θ1 = β, β k ⊕θ1 ⊕ α = ⎨
π
⎪⎩(β, (β ⊕ (k ⊕ θ1 )) ⊕ α)
)
(
f
= (α (1) , β(1) ⊕ θ1 ) = (α (1) ⊕ y0 , β(1) ⊕ y1 ) = (α ⊕ θ1 , β) k ,
2
∏ f k ⊕θ
i
i
(α, β)i =1
= (β
πk
1
⊕ α ⊕ θ1 , (β
πk
1
⊕ α)
πk
2
⊕ β ⊕ θ1 ⊕ θ2 ) = (α (2) ⊕ y1 , β(2) ⊕ y2 ).
Утверждение доказано.
Ключи, принадлежащие одному блоку импримитивности
Ak = {k , k ⊕ 1} , k ∈ {0, 2m −1 − 1} , группы
S2 ∫ S2m −1 , будем называть 1-эквивалентными; также ключи k ( j ) = (k1( j ) ,..., kl( j ) ) ∈ Vml , j = 1, 2, будем назы-
вать 1-эквивалентными, если ki(1) , ki(2) – 1-эквивалентны для любого i ∈ {1, l} . Очевидно, что отношение
1-эквивалентности на множестве Vml является отношением эквивалентности.
Предположим, что для l-раундового алгоритма шифрования Фейстеля с раундовыми функциями
f πk , i = 1, l , удовлетворяющими условиям утверждения 1, ключи k1, …, kl выбираются случайно независимо
i
и равновероятно из Vm. Опишем эквивалентные ключи такого алгоритма, где ключи считаются эквивалентными в смысле стандартного определения (см., например, [7]).
Следствие 1. Пусть выполнены условия утверждения 1, l ≥ 2, k = (k1 ,..., kl ) ∈ Vml . Пусть также
θ = (θ1, …, θl), θ′ = (θ′1, …, θ′l) – произвольные векторы из {0,1}l . Тогда ключи k + θ, k + θ′ эквивалентны,
l −1
если выполняются равенства: ∑ al −i (θi ⊕ θi′ ) = 0 и θl = θ′l. Число эквивалентных ключей, являющихся также
1-эквивалентными, равно 2l–2.
i =1
l −1
Доказательство. Условия ∑ al −i (θi ⊕ θi′ ) = 0 и θl = θ′l непосредственно следуют из равенства (1). Подi =1
считаем число эквивалентных ключей, являющихся также 1-эквивалентными, равное числу решений уравl −1
нения ∑ al −i θ i = 0 , и θ l = 0 , где θ i = θi ⊕ θi′ ∈ {0,1} . Поскольку число нулей в последовательности
i =1
l − 1⎥
⎢ l − 1 ⎥ , то число решений уравнения l −1 a θ = 0 равно
l
1
−
−
a1, …, al–1 равно ⎢⎢
,
а
число
единиц
–
∑ l −i i
⎢⎣ 3 ⎥⎦
⎣ 3 ⎥⎦
i =1
⎢ l −1⎥
⎢⎣ 3 ⎥⎦
2
l −1⎥
l −1− ⎢⎢
−1
3 ⎥⎦
⎣
⋅2
= 2l − 2 . Следствие доказано.
60
М.А. Пудовкина
Следующий алгоритм при фиксированном открытом тексте (α1, β1), …, (αt, βt)∈V2m и соответствующем
шифртексте (α1(l ) , β1(l ) ),..., (αt(l ) , βt(l ) ) , l ≥ 1, полученном на неизвестном ключе k = (k1 ,..., kl ) ∈ Vml , позволяет
уменьшить трудоемкость определения ключа k по сравнению с полным перебором.
Пусть i ≥ 1. На i-м этапе опробования по схеме выбора без возвращения из множества всех блоков имA = { A(k ), k = 0, 2m −1}
примитивности
k1(i ) = k
(i )
( i ) ,..., kl
r1
=k
rl(i )
упорядоченно
выбираем
l
, где k (ji ) – j-й опробуемый ключ на i-м этапе, k
A(rj(i ) ) , j = 1, l . Если (α j , β j )
f (i ) (i )
k ...k
1
l
блоков,
r j(i )
r1(i ) , ..., rl(i ) .
– произвольный элемент из
= (α (jl ,i ) , β(jl ,i ) ) ∈ (α (jl ) , β(jl ) ), (α (jl ) , β(jl ) ) + 1 , где f
{
Полагаем
}
i
k1( i ) ...kl( i )
=∏ f
j =1
k (ji )
, для
любого j ∈ {1, l} , то найден представитель k (i ) = (k1(i ) ,..., kl(i ) ) класса 1-эквивалентности, содержащего истинный ключ. В противном случае переходим к этапу i+1.
Из следствия 1 следует способ нахождения ключа из класса эквивалентности, содержащего истинный
ключ, по данному представителю k (i ) = (k1(i ) ,..., kl(i ) ) класса 1-эквивалентности, которому принадлежит k.
Для этого
- если β(jl ) = β(jl ,i ) , то полагаем kl = kl(i ) , иначе kl = kl(i ) + 1 ;
- если α (jl ) = α (jl ,i ) , то полагаем kl −1 = kl(−i )1 , иначе kl −1 = kl(−i )1 + 1 ;
- полагаем k j = k (ji ) , j = 1, l − 2 .
Трудоемкость предложенного алгоритма равна 2l(m–1) э.о. и в 2l раз меньше трудоемкости полного перебора, равной 2lm э.о., где э.о. – элементарная операция.
2. Свойства алгоритмов шифрования Фейстеля относительно группы S2n −1 ∫ S2
f
π
Пусть (α, β) k = (β, α ⊕ β k ) . Для векторов (α, β)∈Vm, удовлетворяющих сравнению ||α|| ≡ ||β|| (mod2), будем использовать обозначение α∼2β. Также обозначим
f
→(α ′, β′),
(α, β) ⎯⎯
если (α, β) f = (α (l ) , β(l ) ) , f∈Φn, и α(l) ∼2α′ , β(l) ∼2 β′.
Утверждение 2. Пусть π ∈ S2m −1 ∫ S2 , f k ∈ Φ n , α
πk
∈ {(α ⊕ k )π , α π ⊕ k } для любого k∈Vm. Тогда для лю-
бого натурального числа l и любых k1, …, kl∈Vm справедливо включение:
3
⎛ l
⎞
1. ⎜ ∏ f k j ⎟ ∈ S2n −1 ∫ S2 , если l ≡/ 0 (mod3) .
⎝ j =1
⎠
2
⎛ l
⎞
2. ⎜ ∏ f k j ⎟ ∈ S2n −1 ∫ S2 , если l ≡ 0 (mod3).
⎝ j =1
⎠
Доказательство. Методом математической индукции нетрудно показать, что для любого i ∈ N справедливы равенства:
f k ... f k
1
3⋅i →(α ⊕ w(3i ) (k ,..., k ), β ⊕ w(3i ) ( k ,..., k )),
(α, β) ⎯⎯⎯⎯⎯
1
3i
1
3i
1
2
f k ... f k
(3i +1)
1
3⋅i +1 →(β ⊕ w(3i +1) (k ,..., k
(α, β) ⎯⎯⎯⎯⎯⎯
(k1 ,..., k3i +1 )),
1
3i +1 ), α ⊕ β ⊕ w2
1
f k ... f k
(3i + 2)
1
3⋅i + 2 →(α ⊕ β ⊕ w(3i + 2) ( k ,..., k
(α, β) ⎯⎯⎯⎯⎯⎯
(k1 ,..., k3i + 2 )),
1
3i + 2 ), α ⊕ w2
1
i +v)
где w(3
: Vm3i + v → {0,1} – некоторые аффинные функции, v∈{0, 1, 2}, j∈{1, 2}.
j
Рассмотрим три случая. Если l ≡ 0 (mod3), то
f k ... f k
f k ... f k
1
1
l
l
(α, β) ⎯⎯⎯⎯→
(α ⊕ w1(l ) (k1 ,..., kl ), β ⊕ w2(l ) (k1 ,..., kl )) ⎯⎯⎯⎯→
(α ⊕ w1(l ) (k1 ,..., kl ) ⊕ w1(l ) (k1 ,..., kl ), β ⊕ w2(l ) (k1 ,..., kl ) ⊕ w2(l ) (k1 ,..., kl )) ∼ 2 (α, β).
61
Свойства некоторых алгоритмов шифрования Фейстеля
Если l ≡ 1 (mod3), то
f k ... f k
f k ... f k
1
1
l
l
(α, β) ⎯⎯⎯⎯→
(β ⊕ w1(l ) (k1 ,..., kl ), α ⊕ β ⊕ w2(l ) (k1 ,..., kl )) ⎯⎯⎯⎯→
(α ⊕ β ⊕ w2(l ) (k1 ,..., kl ) ⊕ w1(l ) (k1 ,..., kl ),
f k ... f k
1
l
w1(l ) (k1 ,..., kl ) ⊕ α ) ⎯⎯⎯⎯→
( w1(l ) (k1 ,..., kl ) ⊕ w1(l ) (k1 ,..., kl ) ⊕ α, α ⊕ β ⊕ w2(l ) (k1 ,..., kl ) ⊕ w1(l ) (k1 ,..., kl ) ⊕
⊕ w1(l ) (k1 ,..., kl ) ⊕ α ⊕ w2(l ) (k1 ,..., kl )) ∼ 2 (α, β).
Если l ≡ 2 (mod3), то
f k ... f k
f k ... f k
1
1
l
l
(α, β) ⎯⎯⎯⎯→
(α ⊕ β ⊕ w1(l ) (k1 ,..., kl ), α ⊕ w2(l ) (k1 ,..., kl )) ⎯⎯⎯⎯→
(β ⊕ w2(l ) (k1 ,..., kl ),
f k ... f k
1
l
α ⊕ β ⊕ w1(l ) (k1 ,..., kl ) ⊕ w2(l ) (k1 ,..., kl )) ⎯⎯⎯⎯→
(α, β).
Утверждение доказано.
Пусть g k = f k1 ... f kl , где преобразования f k j удовлетворяют условию утверждения 2 для всех j ∈ {1, l} ,
l ≥ 1. Пусть также (α1,β1), …, (αt, βt) – неизвестный открытый текст длины t ≥ 1, (α1(l ) , β1(l ) ),...., (αt(l ) , βt(l ) ) – известный шифртескт, где (αi(l ) , βi(l ) ) = (αi , βi )
gk
, i = 1, t .
Из утверждения 2 следует, что без знания ключа по известному шифртексту (α1(l ) , β1(l ) ),..., (αt(l ) , βt(l ) )
можно получить следующую информацию об открытом тексте:
g 2
g
k
k
1) если l ≡ 0 (mod3), то (α, β) ⎯⎯⎯
→(α, β) и (αi(l ) , βi(l ) ) ⎯⎯→
(αi , βi ) для любого i = {1, t} ;
g 3
g 2
k
k
2) если l ≡/ 0 (mod3) , то (α, β) ⎯⎯⎯
→(α, β) и (αi(l ) , βi(l ) ) ⎯⎯⎯
→(αi , βi ) для любого i = {1, t} ;
3) если l ≡ 2 (mod3), то βi(l ) ⊕ β(jl ) ∼ 2 αi ⊕ α j
и βi(l ) ⊕ β(jl ) ⊕ α i(l ) ⊕ α (jl ) ∼ 2 βi ⊕ β j
для любой пары
i, j ∈ {1, t} ;
4) если l ≡ 1 (mod3), то α i(l ) ⊕ α (jl ) ∼ 2 βi ⊕ β j , и βi(l ) ⊕ β(jl ) ⊕ α i(l ) ⊕ α (jl ) ∼ 2 α i ⊕ α j для любой пары
i, j ∈ {1, t} ;
5) если l ≡ 0 (mod3), то αi(l ) ∼ 2 αi , βi(l ) ∼ 2 βi для любого i ∈ {1, t} .
Утверждение 3. Для любых подстановок s = (s1, s2)∈S(Vm)×S(Vm), π∈S(Vm), справедливо равенство
)
(
−1
−1 s2 ⎞
s
⎛ −1
(α, β) f π = ⎜ βs2 s1 , βs2 π ⊕ α s1
⎟.
⎝
⎠
Доказательство следует из равенств
−1
−1 f π s
−1
−1
−1 s
−1
−1
s
⎛ −1
= β s2 , β s2 π + α s1
= ⎜ βs2 s1 , βs2 π + α s1
(α, β) f π = α s1 , β s2
⎝
(
)
)
(
(
)
s2
⎞
⎟.
⎠
Следствие 2. В условиях утверждения 2, если s2 −1s1 ∈ S2m −1 ∫ S2 и (α + β) s2 ∼ 2 α s2 ⊕ β s2 для любых
α, β∈Vm, то
fs
(
π⎯
(α, β) ⎯⎯
→ β, β s2
−1πs
2
)
⊕α .
В частности, если s2 ∈ S2m −1 ∫ S 2 или s2∈GLm, то соотношение (α ⊕ β) s2 ∼ 2 α s2 ⊕ βs2 справедливо для
любых α, β∈Vm.
Доказательство следует из утверждения 3.
ЛИТЕРАТУРА
1. Schneier B. Applied Cryptography, Protocols, Algorithms, and Source Code in C. Second edition. New York: John Wiley and
Sons, 1996.
2. Pieprzyk J., Zhang X.M. Permutation generators of alternating groups // AUSCRYPT'90. 1990, LNCS 453.
3. Caranti A., Volta F.D., Sala M., Villani F. Imprimitive permutations groups generated by the round functions of key-alternating block ciphers and truncated differential cryptanalysis // Workshop on Coding and Cryptography, UC Cork. 2005.
4. Paterson K.G. Imprimitive Permutation Groups and Trapdoors in Iterated Block Ciphers // FSE'99. 1999. LNCS 1636.
5. Погорелов Б.А., Пудовкина М.А. Подметрики метрики Хемминга и преобразования, распространяющие искажения в
заданное число раз // Труды по дискретной математике, АК РФ. 2007. Т. 10.
6. Погорелов Б.А., Пудовкина М.А. Линейные структуры групп подстановок векторных пространств // Труды 3-й Междунар. конф. «Проблемы безопасности и противодействия терроризму, 2007». М.: МЦНМО, 2008.
7. Фомичев В.М. Дискретная математика и криптология. М.: ЗАО «Диалог-МИФИ», 2003.
Документ
Категория
Без категории
Просмотров
4
Размер файла
908 Кб
Теги
сплетением, шифрование, алгоритм, группы, свойства, некоторые, двух, относительные, фейстеля
1/--страниц
Пожаловаться на содержимое документа