Cs-cipher (фр. Chiffrement Symètrique , симметричный шифр) — симметричный 64 битный
[ 1] блочный алгоритм шифрования данных
[ 2] , использующий длину ключа до 128 бит[ 1] . По принципу работы является 8 раундовой SP-сетью [ 3] .
История
Cs-cipher разработали в 1998 году Жак Штерн (англ. Jacques Stern ) и Серж Водене (англ. Serge Vaudenay )
[ 4] при поддержке Compagnie des Signaux [ 5] . Он был представлен в качестве кандидата в проекте NESSIE в рамках программы Европейской комиссии IST (англ. Information Societies Technology , информационные общественные технологии) в конкурсной группе 64-битных блочных шифров[ 6] . Несмотря на то, что при исследовании не было обнаружено уязвимостей[ 7] , шифр не был выбран для 2 фазы проекта[ 8] , потому что оказался самым медленным в своей группе[ 7] .
Основные обозначения
Используемые функции
Для начала обозначим следующие обозначения:
P
(
x
)
=
z
l
∥
z
r
{\displaystyle P(x)=z_{l}\parallel z_{r}}
- независимая перестановка 8-битных строк [ 9] . Определяется как трех-раундовая сеть Фейстеля [ 10] :
8-битная входная строка делится на две 4-битных
x
=
x
l
∥
x
r
{\displaystyle x=x_{l}\parallel x_{r}}
y
=
x
l
⊕
f
(
x
r
)
{\displaystyle y=x_{l}\oplus f(x_{r})}
z
r
=
x
r
⊕
g
(
y
)
{\displaystyle z_{r}=x_{r}\oplus g(y)}
z
l
=
y
⊕
f
(
z
r
)
{\displaystyle z_{l}=y\oplus f(z_{r})}
Результатом является строка
z
=
z
l
∥
z
r
{\displaystyle z=z_{l}\parallel z_{r}}
Функции
f
(
x
)
{\displaystyle f(x)}
и
g
(
x
)
{\displaystyle g(x)}
задаются таблицей:
таблица
f
(
x
)
{\displaystyle f(x)}
и
g
(
x
)
{\displaystyle g(x)}
x
0
1
2
3
4
5
6
7
8
9
a
b
c
d
e
f
f
(
x
)
{\displaystyle f(x)}
f
d
b
b
7
5
7
7
e
d
a
b
e
d
e
f
g
(
x
)
{\displaystyle g(x)}
a
6
0
2
b
e
1
8
d
4
5
3
f
c
7
9
В конечном итоге
P
(
x
)
{\displaystyle P(x)}
задается с помощью таблицы[ 11] :
таблица
P
(
x
)
{\displaystyle P(x)}
xy
.0
.1
.2
.3
.4
.5
.6
.7
.8
.9
.a
.b
.c
.d
.e
.f
0.
29
0d
61
40
9c
eb
9e
8f
1f
85
5f
58
5b
01
39
86
1.
97
2e
d7
d6
35
ae
17
16
21
b6
69
4e
a5
72
87
08
2.
3c
18
e6
e7
fa
ad
b8
89
b7
00
f7
6f
73
84
11
63
3.
3f
96
7f
6e
bf
14
9d
ac
a4
0e
7e
f6
20
4a
62
30
4.
03
c5
4b
5a
46
a3
44
65
7d
4d
3d
42
79
49
1b
5c
5.
f5
6c
b5
94
54
ff
56
57
0b
f4
43
0c
4f
70
6d
0a
6.
e4
02
3e
2f
a2
47
e0
c1
d5
1a
95
a7
51
5e
33
2b
7.
5d
d4
1d
2c
ee
75
ec
dd
7c
4c
a6
b4
78
48
3a
32
8.
98
af
c0
e1
2d
09
0f
1e
b9
27
8a
e9
bd
e3
9f
07
9.
b1
ea
92
93
53
6a
31
10
80
f2
d8
9b
04
36
06
8e
a.
be
a9
64
45
38
1c
7a
6b
f3
a1
f0
cd
37
25
15
81
b.
fb
90
e8
d9
7b
52
19
28
26
88
fc
d1
e2
8c
a0
34
c.
82
67
da
cb
c7
41
e5
c4
c8
ef
db
c3
cc
ab
ce
ed
d.
d0
bb
d3
d2
71
68
13
12
9a
b3
c2
ca
de
77
dc
df
e.
66
83
bc
8d
60
c6
22
23
b2
8b
91
05
76
cf
74
c9
f.
aa
f1
99
a8
59
50
3b
2a
fe
f9
24
b0
ba
fd
f8
55
Например
P
(
{\displaystyle P(}
26
16
)
{\displaystyle _{16})}
:
y
=
{\displaystyle y=}
2
16
⊕
f
(
{\displaystyle _{16}\oplus f(}
6
16
)
=
{\displaystyle _{16})=}
2
16
⊕
{\displaystyle _{16}\oplus }
7
16
=
{\displaystyle _{16}=}
5
16
{\displaystyle _{16}}
z
r
=
{\displaystyle z_{r}=}
6
16
⊕
g
(
y
)
=
{\displaystyle _{16}\oplus g(y)=}
6
16
⊕
{\displaystyle _{16}\oplus }
e
16
=
8
{\displaystyle _{16}=8}
z
l
=
y
⊕
f
(
z
r
)
=
{\displaystyle z_{l}=y\oplus f(z_{r})=}
5
16
⊕
{\displaystyle _{16}\oplus }
e
16
=
{\displaystyle _{16}=}
b
16
{\displaystyle _{16}}
Итого:
P
(
{\displaystyle P(}
26
16
)
=
{\displaystyle _{16})=}
b8
16
{\displaystyle _{16}}
P
8
(
x
)
=
P
(
x
63..56
)
∥
P
(
x
55..48
)
∥
P
(
x
47..40
)
∥
P
(
x
39..32
)
∥
P
(
x
31..24
)
∥
P
(
x
23..16
)
∥
P
(
x
15..8
)
∥
P
(
x
7..0
)
{\displaystyle P^{8}(x)=P(x_{63..56})\parallel P(x_{55..48})\parallel P(x_{47..40})\parallel P(x_{39..32})\parallel P(x_{31..24})\parallel P(x_{23..16})\parallel P(x_{15..8})\parallel P(x_{7..0})}
[ 9] - преобразование 64-битной строки, используется для генерации ключей и в раундовой функции
T
(
z
)
=
z
63
∥
z
55
∥
⋯
∥
z
7
∥
z
62
∥
z
54
∥
⋯
∥
z
0
{\displaystyle T(z)=z_{63}\parallel z_{55}\parallel \dots \parallel z_{7}\parallel z_{62}\parallel z_{54}\parallel \dots \parallel z_{0}}
- битовая транспозиция , в данном случае транспонирование матрицы [ 9] , составленной из 8 битных строк, используется при генерации ключей. На вход функция принимает 64-битную строку
R
l
(
x
)
{\displaystyle R_{l}(x)}
- функция циклического битового сдвига влево, в данном случае принимает 8-битную строку:
R
(
x
7
∥
x
6
∥
x
5
∥
x
4
∥
x
3
∥
x
2
∥
x
1
∥
x
0
)
=
x
6
∥
x
5
∥
x
4
∥
x
3
∥
x
2
∥
x
1
∥
x
0
∥
x
7
{\displaystyle R(x_{7}\parallel x_{6}\parallel x_{5}\parallel x_{4}\parallel x_{3}\parallel x_{2}\parallel x_{1}\parallel x_{0})=x_{6}\parallel x_{5}\parallel x_{4}\parallel x_{3}\parallel x_{2}\parallel x_{1}\parallel x_{0}\parallel x_{7}}
φ
(
x
)
=
(
R
l
(
x
)
∧
55
16
)
⊕
x
{\displaystyle \varphi (x)=(R_{l}(x)\land 55_{16})\oplus x}
- преобразование[ 12] , используется в раундовой функции. На вход принимает 8-битную строку, если упростить получим[ 12] :
φ
(
x
7
∥
x
6
∥
x
5
∥
x
4
∥
x
3
∥
x
2
∥
x
1
∥
x
0
)
=
x
7
∥
(
x
6
⊕
x
5
)
∥
x
5
∥
(
x
4
⊕
x
3
)
∥
x
3
∥
(
x
2
⊕
x
1
)
∥
x
1
∥
(
x
0
⊕
x
7
)
{\displaystyle \varphi (x_{7}\parallel x_{6}\parallel x_{5}\parallel x_{4}\parallel x_{3}\parallel x_{2}\parallel x_{1}\parallel x_{0})=x_{7}\parallel (x_{6}\oplus x_{5})\parallel x_{5}\parallel (x_{4}\oplus x_{3})\parallel x_{3}\parallel (x_{2}\oplus x_{1})\parallel x_{1}\parallel (x_{0}\oplus x_{7})}
ϕ
′
(
x
)
=
(
R
l
(
x
)
∧
a
a
16
)
⊕
x
{\displaystyle \phi ^{'}(x)=(R_{l}(x)\land aa_{16})\oplus x}
- преобразование[ 13] , используется при расшифровке. На вход принимает 8-битную строку
M
(
x
)
{\displaystyle M(x)}
- преобразование, используется в раундовой функции[ 12] , берет на вход 16-битные строки
x
=
x
l
∥
x
r
{\displaystyle x=x_{l}\parallel x_{r}}
, результатом является 16-битная строка
M
(
x
)
=
y
l
∥
y
r
{\displaystyle M(x)=y_{l}\parallel y_{r}}
, в свою очередь:
y
l
=
P
(
φ
(
x
l
)
⊕
x
r
)
{\displaystyle y_{l}=P(\varphi (x_{l})\oplus x_{r})}
y
r
=
P
(
R
l
(
x
l
)
⊕
x
r
)
{\displaystyle y_{r}=P(R_{l}(x_{l})\oplus x_{r})}
M
−
1
(
y
l
∥
y
r
)
{\displaystyle M^{-1}(y_{l}\parallel y_{r})}
- преобразование, используется при расшифровке[ 13] , берет на вход 16-битные строки
y
=
y
l
∥
y
r
{\displaystyle y=y_{l}\parallel y_{r}}
, результатом является 16-битная строка
M
−
1
(
y
)
=
x
l
∥
x
r
{\displaystyle M^{-1}(y)=x_{l}\parallel x_{r}}
, в свою очередь:
x
l
=
ϕ
′
(
P
(
y
l
)
⊕
P
(
y
r
)
)
{\displaystyle x_{l}=\phi ^{'}(P(y_{l})\oplus P(y_{r}))}
x
r
=
R
l
(
x
l
)
⊕
P
(
y
r
)
{\displaystyle x_{r}=R_{l}(x_{l})\oplus P(y_{r})}
F
c
i
(
x
)
=
T
(
P
8
(
x
⊕
c
i
)
)
{\displaystyle F_{c_{i}}(x)=T(P^{8}(x\oplus c^{i}))}
- используется для генерации ключей[ 9]
Константы алгоритма
Ниже представлен список констант, заданных создателями алгоритма:
c
=
{\displaystyle c=}
b7e151628aed2a6a
16
{\displaystyle _{16}}
[ 14] , требуется для раундовой функции
c
′
=
{\displaystyle c^{'}=}
bf7158809cf4f3c7
16
{\displaystyle _{16}}
[ 14] , требуется для раундовой функции
c
0
=
{\displaystyle c^{0}=}
290d61409ceb9e8f
16
{\displaystyle _{16}}
[ 9] , требуется для генерации ключей
c
1
=
{\displaystyle c^{1}=}
1f855f585b013986
16
{\displaystyle _{16}}
[ 9] , требуется для генерации ключей
c
2
=
{\displaystyle c^{2}=}
972ed7d635ae1716
16
{\displaystyle _{16}}
[ 9] , требуется для генерации ключей
c
3
=
{\displaystyle c^{3}=}
21b6694ea5728708
16
{\displaystyle _{16}}
[ 9] , требуется для генерации ключей
c
4
=
{\displaystyle c^{4}=}
3c18e6e7faadb889
16
{\displaystyle _{16}}
[ 9] , требуется для генерации ключей
c
5
=
{\displaystyle c^{5}=}
b700f76f73841163
16
{\displaystyle _{16}}
[ 9] , требуется для генерации ключей
c
6
=
{\displaystyle c^{6}=}
3f967f6ebf149dac
16
{\displaystyle _{16}}
[ 9] , требуется для генерации ключей
c
7
=
{\displaystyle c^{7}=}
a40e7ef6204a6230
16
{\displaystyle _{16}}
[ 9] , требуется для генерации ключей
c
8
=
{\displaystyle c^{8}=}
03c54b5a46a34465
16
{\displaystyle _{16}}
[ 9] , требуется для генерации ключей
Генерация ключей
Если секретный ключ, используемый в шифре меньше 128 бит, то первые биты заполняются нулями
[ 1] , поэтому в дальнейшем будем считать секретный ключ 128 битным.
Алгоритм генерации ключей
Согласно следующему алгоритму в шифре из 128-битного ключа генерируется 9 подключей
k
0
,
k
1
,
.
.
.
,
k
8
{\displaystyle k^{0},k^{1},...,k^{8}}
размером 64 бита:
первоначально ключ делится на две 64 битные половины[ 2] , таким образом мы получаем начальные параметры:
k
=
k
−
1
∥
k
−
2
{\displaystyle k=k^{-1}\parallel k^{-2}}
Для генерации последующих ключей используется рекуррентная формула[ 2] :
k
i
=
k
i
−
2
⊕
F
c
i
(
k
i
−
1
)
{\displaystyle k^{i}=k^{i-2}\oplus F_{c^{i}}(k^{i-1})}
Пример генерации ключей
Рассмотрим пример генерации ключей, описанный создателями CS-cipher[ 13] . В нем используется секретный ключ
k
=
{\displaystyle k=}
0123456789abcdeffedcba9876543210
16
{\displaystyle _{16}}
.
Согласно рассмотренному выше, получаем начальные параметры для генерирования раундовых ключей:
k
−
1
=
{\displaystyle k^{-1}=}
0123456789abcdef
16
{\displaystyle _{16}}
k
−
2
=
{\displaystyle k^{-2}=}
fedcba9876543210
16
{\displaystyle _{16}}
Рассмотрим подробно генерацию ключа
k
0
{\displaystyle k^{0}}
:
k
0
=
k
−
2
⊕
F
c
0
(
k
−
1
)
=
k
−
2
⊕
T
(
P
8
(
k
−
1
⊕
c
0
)
)
=
{\displaystyle k^{0}=k^{-2}\oplus F_{c_{0}}(k^{-1})=k^{-2}\oplus T(P^{8}(k^{-1}\oplus c^{0}))=}
=
k
−
2
⊕
T
(
P
8
(
{\displaystyle =k^{-2}\oplus T(P^{8}(}
0123456789abcdef
16
⊕
{\displaystyle _{16}\oplus }
290d61409ceb9e8f
16
)
)
=
{\displaystyle _{16}))=}
=
k
−
2
⊕
T
(
{\displaystyle =k^{-2}\oplus T(}
b711fa89ae0394e4
16
)
=
{\displaystyle _{16})=}
fedcba9876543210
16
⊕
{\displaystyle _{16}\oplus }
bb21a9e2388bacd4
16
{\displaystyle _{16}}
Конечный результат работы алготитма генерации:
k
0
=
{\displaystyle k^{0}=}
45fd137a4edf9ec4
16
{\displaystyle _{16}}
k
1
=
{\displaystyle k^{1}=}
1dd43f03e6f7564c
16
{\displaystyle _{16}}
k
2
=
{\displaystyle k^{2}=}
ebe26756de9937c7
16
{\displaystyle _{16}}
k
3
=
{\displaystyle k^{3}=}
961704e945bad4fb
16
{\displaystyle _{16}}
k
4
=
{\displaystyle k^{4}=}
0b60dfe9eff473d4
16
{\displaystyle _{16}}
k
5
=
{\displaystyle k^{5}=}
76d3e7cf52c466cf
16
{\displaystyle _{16}}
k
6
=
{\displaystyle k^{6}=}
75ec8cef767d3a0d
16
{\displaystyle _{16}}
k
7
=
{\displaystyle k^{7}=}
82da3337b598fd6d
16
{\displaystyle _{16}}
k
8
=
{\displaystyle k^{8}=}
fbd820da8dc8af8c
16
{\displaystyle _{16}}
Шифрование
Краткое описание зашифровки
Каждый раунд шифровки начинается с операции XOR над входящей 64-битной строкой и подключа. Затем 64-битная строка разделяется на 4 16-битных строки, над которыми происходит нелинейное преобразование(
M
(
x
)
{\displaystyle M(x)}
). После этого строки снова делятся, на этот раз в результате получается 8 8-битных строк, которые затем переставляются. Данные действия повторяются еще дважды в каждом раунде, разница лишь в том, что операция XOR происходит с заданными константами, а не со сгенерированным ключом. После последнего раунда следует дополнительная операция XOR с оставшимся сгенерированным ключом[ 3] .
Формальное описание алгоритма
Первоначально определим:
m
i
{\displaystyle m^{i}}
- 64-битная строка, приходит на вход раундовой функции
R
(
x
)
{\displaystyle R(x)}
в
i
{\displaystyle i}
итерации
t
i
=
t
63..56
i
∥
t
55..48
i
∥
t
47..40
i
∥
t
39..32
i
∥
t
31..24
i
∥
t
23..16
i
∥
t
15..8
i
∥
t
7..0
i
{\displaystyle t^{i}=t_{63..56}^{i}\parallel t_{55..48}^{i}\parallel t_{47..40}^{i}\parallel t_{39..32}^{i}\parallel t_{31..24}^{i}\parallel t_{23..16}^{i}\parallel t_{15..8}^{i}\parallel t_{7..0}^{i}}
- временное 64-битное значение, вычисленное на
i
{\displaystyle i}
шаге раундовой функции
S
{\displaystyle S}
- 64-битная строка, конечный зашифрованный текст
Раундовая функции
R
(
x
)
{\displaystyle R(x)}
Раундовая функция состоит из следующих действий[ 15] :
t
1
=
x
{\displaystyle t^{1}=x}
t
2
=
M
(
t
63..48
1
)
∥
M
(
t
47..32
1
)
∥
M
(
t
31..16
1
)
∥
M
(
t
15..0
1
)
{\displaystyle t^{2}=M(t_{63..48}^{1})\parallel M(t_{47..32}^{1})\parallel M(t_{31..16}^{1})\parallel M(t_{15..0}^{1})}
t
3
=
t
63..56
2
∥
t
47..40
2
∥
t
31..24
2
∥
t
15..8
2
∥
t
55..48
2
∥
t
39..32
2
∥
t
23..16
2
∥
t
7..0
2
{\displaystyle t^{3}=t_{63..56}^{2}\parallel t_{47..40}^{2}\parallel t_{31..24}^{2}\parallel t_{15..8}^{2}\parallel t_{55..48}^{2}\parallel t_{39..32}^{2}\parallel t_{23..16}^{2}\parallel t_{7..0}^{2}}
t
4
=
t
3
⊕
c
{\displaystyle t^{4}=t^{3}\oplus c}
t
5
=
M
(
t
63..48
4
)
∥
M
(
t
47..32
4
)
∥
M
(
t
31..16
4
)
∥
M
(
t
15..0
4
)
{\displaystyle t^{5}=M(t_{63..48}^{4})\parallel M(t_{47..32}^{4})\parallel M(t_{31..16}^{4})\parallel M(t_{15..0}^{4})}
t
6
=
t
63..56
5
∥
t
47..40
5
∥
t
31..24
5
∥
t
15..8
5
∥
t
55..48
5
∥
t
39..32
5
∥
t
23..16
5
∥
t
7..0
5
{\displaystyle t^{6}=t_{63..56}^{5}\parallel t_{47..40}^{5}\parallel t_{31..24}^{5}\parallel t_{15..8}^{5}\parallel t_{55..48}^{5}\parallel t_{39..32}^{5}\parallel t_{23..16}^{5}\parallel t_{7..0}^{5}}
t
7
=
t
6
⊕
c
′
{\displaystyle t^{7}=t^{6}\oplus c^{'}}
t
8
=
M
(
t
63..48
7
)
∥
M
(
t
47..32
7
)
∥
M
(
t
31..16
7
)
∥
M
(
t
15..0
7
)
{\displaystyle t^{8}=M(t_{63..48}^{7})\parallel M(t_{47..32}^{7})\parallel M(t_{31..16}^{7})\parallel M(t_{15..0}^{7})}
m
i
+
1
=
t
9
=
t
63..56
8
∥
t
47..40
8
∥
t
31..24
8
∥
t
15..8
8
∥
t
55..48
8
∥
t
39..32
8
∥
t
23..16
8
∥
t
7..0
8
{\displaystyle m^{i+1}=t^{9}=t_{63..56}^{8}\parallel t_{47..40}^{8}\parallel t_{31..24}^{8}\parallel t_{15..8}^{8}\parallel t_{55..48}^{8}\parallel t_{39..32}^{8}\parallel t_{23..16}^{8}\parallel t_{7..0}^{8}}
Зашифровывание
Зашифрование состоит из 8 раундов, конечный 64-битный зашифрованный текст
S
{\displaystyle S}
можно вычислить из фрагмента открытого текста
m
{\displaystyle m}
по формуле[ 9] :
S
=
k
8
⊕
R
(
k
7
⊕
…
R
(
k
1
⊕
R
(
k
0
⊕
m
)
…
)
{\displaystyle S=k^{8}\oplus R(k^{7}\oplus \dots R(k^{1}\oplus R(k^{0}\oplus m)\dots )}
Где
R
(
x
)
{\displaystyle R(x)}
— раундовая функция[ 10] , описана выше.
Пример зашифровывания открытого текста
Рассмотрим пример зашифровывания открытого текста, описанный создателями CS-cipher[ 13] . В нем используется следующие секретный ключ и открытый текст:
m
0
=
{\displaystyle m^{0}=}
0123456789abcdef
16
{\displaystyle _{16}}
k
=
{\displaystyle k=}
0123456789abcdeffedcba9876543210
16
{\displaystyle _{16}}
Секретный ключ соответствует вышележащему примеру генерации раундовых ключей, то есть раундовые ключи были подсчитаны выше:
k
0
=
{\displaystyle k^{0}=}
45fd137a4edf9ec4
16
{\displaystyle _{16}}
k
1
=
{\displaystyle k^{1}=}
1dd43f03e6f7564c
16
{\displaystyle _{16}}
k
2
=
{\displaystyle k^{2}=}
ebe26756de9937c7
16
{\displaystyle _{16}}
k
3
=
{\displaystyle k^{3}=}
961704e945bad4fb
16
{\displaystyle _{16}}
k
4
=
{\displaystyle k^{4}=}
0b60dfe9eff473d4
16
{\displaystyle _{16}}
k
5
=
{\displaystyle k^{5}=}
76d3e7cf52c466cf
16
{\displaystyle _{16}}
k
6
=
{\displaystyle k^{6}=}
75ec8cef767d3a0d
16
{\displaystyle _{16}}
k
7
=
{\displaystyle k^{7}=}
82da3337b598fd6d
16
{\displaystyle _{16}}
k
8
=
{\displaystyle k^{8}=}
fbd820da8dc8af8c
16
{\displaystyle _{16}}
Промежуточные результаты для вычисления
m
1
{\displaystyle m^{1}}
:
t
3
=
{\displaystyle t^{3}=}
d85c19785690b0e3
16
{\displaystyle _{16}}
t
6
=
{\displaystyle t^{6}=}
0f4bfb9e2f8ac7e2
16
{\displaystyle _{16}}
Получим следующие значения на раундах:
m
1
=
{\displaystyle m^{1}=}
c3feb96c0cf4b649
16
{\displaystyle _{16}}
m
2
=
{\displaystyle m^{2}=}
3f54e0c8e61a84d1
16
{\displaystyle _{16}}
m
3
=
{\displaystyle m^{3}=}
b15cb4af3786976e
16
{\displaystyle _{16}}
m
4
=
{\displaystyle m^{4}=}
76c122b7a562ac45
16
{\displaystyle _{16}}
m
5
=
{\displaystyle m^{5}=}
21300b6ccfaa08d8
16
{\displaystyle _{16}}
m
6
=
{\displaystyle m^{6}=}
99b8d8ab9034ec9a
16
{\displaystyle _{16}}
m
7
=
{\displaystyle m^{7}=}
a2245ba3697445d2
16
{\displaystyle _{16}}
В итоге получили следующий зашифрованный текст:
S
=
{\displaystyle S=}
88fddfbe954479d7
16
{\displaystyle _{16}}
Расшифровывание
Расшифровывание состоит из 8 раундов, обратных зашифровыванию[ 16] . Важно, что алгоритм расшифровки использует сгенерированные ключи в обратном порядке, т. е.
k
8
,
k
7
,
k
6
,
k
5
,
k
4
,
k
3
,
k
2
,
k
1
,
k
0
{\displaystyle k^{8},k^{7},k^{6},k^{5},k^{4},k^{3},k^{2},k^{1},k^{0}}
[ 2] . Перед началом происходит операция
m
0
=
S
⊕
k
8
{\displaystyle m^{0}=S\oplus k^{8}}
.
Для удобства и соответствия обозначений, еще раз укажем:
i
{\displaystyle i}
- номер итерации: от 0 до 7 включительно - всего 8 раундов
m
i
{\displaystyle m^{i}}
- 64-битная строка, приходит на вход обратной к раундовой функции
R
−
1
(
x
)
{\displaystyle R^{-1}(x)}
в
i
{\displaystyle i}
итерации,
m
8
{\displaystyle m^{8}}
- открытый текст
k
7
−
i
{\displaystyle k^{7-i}}
- 64-битный сгенерированный ключ, приходит на вход обратной к раундовой функции
R
−
1
(
x
)
{\displaystyle R^{-1}(x)}
в
i
{\displaystyle i}
итерации
t
i
=
t
63..56
i
∥
t
55..48
i
∥
t
47..40
i
∥
t
39..32
i
∥
t
31..24
i
∥
t
23..16
i
∥
t
15..8
i
∥
t
7..0
i
{\displaystyle t^{i}=t_{63..56}^{i}\parallel t_{55..48}^{i}\parallel t_{47..40}^{i}\parallel t_{39..32}^{i}\parallel t_{31..24}^{i}\parallel t_{23..16}^{i}\parallel t_{15..8}^{i}\parallel t_{7..0}^{i}}
- временное 64-битное значение, вычисленное на
i
{\displaystyle i}
шаге обратной к раундовой функции.
Для каждого раунда вызывается следующая последовательность действий[ 13] :
t
1
=
m
63..56
i
∥
m
31..24
i
∥
m
55..48
i
∥
m
23..16
i
∥
m
47..40
i
∥
m
15..8
i
∥
m
39..32
i
∥
m
7..0
i
{\displaystyle t^{1}=m_{63..56}^{i}\parallel m_{31..24}^{i}\parallel m_{55..48}^{i}\parallel m_{23..16}^{i}\parallel m_{47..40}^{i}\parallel m_{15..8}^{i}\parallel m_{39..32}^{i}\parallel m_{7..0}^{i}}
t
2
=
M
−
1
(
t
63..48
1
)
∥
M
−
1
(
t
47..32
1
)
∥
M
−
1
(
t
31..16
1
)
∥
M
−
1
(
t
15..0
1
)
{\displaystyle t^{2}=M^{-1}(t_{63..48}^{1})\parallel M^{-1}(t_{47..32}^{1})\parallel M^{-1}(t_{31..16}^{1})\parallel M^{-1}(t_{15..0}^{1})}
t
3
=
t
2
⊕
c
′
{\displaystyle t^{3}=t^{2}\oplus c^{'}}
t
4
=
t
63..56
3
∥
t
31..24
3
∥
t
55..48
3
∥
t
23..16
3
∥
t
47..40
3
∥
t
15..8
3
∥
t
39..32
3
∥
t
7..0
3
{\displaystyle t^{4}=t_{63..56}^{3}\parallel t_{31..24}^{3}\parallel t_{55..48}^{3}\parallel t_{23..16}^{3}\parallel t_{47..40}^{3}\parallel t_{15..8}^{3}\parallel t_{39..32}^{3}\parallel t_{7..0}^{3}}
t
5
=
M
−
1
(
t
63..48
4
)
∥
M
−
1
(
t
47..32
4
)
∥
M
−
1
(
t
31..16
4
)
∥
M
−
1
(
t
15..0
4
)
{\displaystyle t^{5}=M^{-1}(t_{63..48}^{4})\parallel M^{-1}(t_{47..32}^{4})\parallel M^{-1}(t_{31..16}^{4})\parallel M^{-1}(t_{15..0}^{4})}
t
6
=
t
5
⊕
c
{\displaystyle t^{6}=t^{5}\oplus c}
t
7
=
t
63..56
6
∥
t
31..24
6
∥
t
55..48
6
∥
t
23..16
6
∥
t
47..40
6
∥
t
15..8
6
∥
t
39..32
6
∥
t
7..0
6
{\displaystyle t^{7}=t_{63..56}^{6}\parallel t_{31..24}^{6}\parallel t_{55..48}^{6}\parallel t_{23..16}^{6}\parallel t_{47..40}^{6}\parallel t_{15..8}^{6}\parallel t_{39..32}^{6}\parallel t_{7..0}^{6}}
t
8
=
M
−
1
(
t
63..48
7
)
∥
M
−
1
(
t
47..32
7
)
∥
M
−
1
(
t
31..16
7
)
∥
M
−
1
(
t
15..0
7
)
{\displaystyle t^{8}=M^{-1}(t_{63..48}^{7})\parallel M^{-1}(t_{47..32}^{7})\parallel M^{-1}(t_{31..16}^{7})\parallel M^{-1}(t_{15..0}^{7})}
m
i
+
1
=
t
9
=
t
8
⊕
k
7
−
i
{\displaystyle m^{i+1}=t^{9}=t^{8}\oplus k^{7-i}}
Статистическая оценка зашифрованных данных
В ходе участия в проекте NESSIE были проведены множество статистических тестов над зашифрованными данными[ 17] , в том числе:
В результате тестирования шифра не было обнаружено его отклонений от случайного распределения[ 23] .
Криптоанализ
Марковский шифр
Предположим, у нас есть
r
{\displaystyle r}
раундовый шифр, зашифрованный текст можно получить по формуле:
S
=
E
n
c
(
x
)
=
(
ρ
r
∘
.
.
.
∘
ρ
1
)
(
x
)
{\displaystyle S=Enc(x)=(\rho _{r}\circ ...\circ \rho _{1})(x)}
, в котором каждый раунд
ρ
i
{\displaystyle \rho _{i}}
использует свой ключ
k
i
{\displaystyle k_{i}}
.
Тогда Марковским шифром называется шифр, для которого для любого раунда
i
{\displaystyle i}
и любых
x
{\displaystyle x}
,
a
{\displaystyle a}
и
b
{\displaystyle b}
выполнено[ 24] :
P
r
k
i
[
ρ
i
(
x
⊕
a
)
⊕
ρ
i
(
x
)
=
b
]
=
P
r
k
i
,
X
[
ρ
i
(
X
⊕
a
)
⊕
ρ
i
(
X
)
=
b
]
{\displaystyle Pr_{k_{i}}[\rho _{i}(x\oplus a)\oplus \rho _{i}(x)=b]=Pr_{k_{i},X}[\rho _{i}(X\oplus a)\oplus \rho _{i}(X)=b]}
Определение анализируемого шифра
В ходе анализа используется модифицированный шифр CS-cipher, называемый в дальнейшем CSC.
Он получается из шифра CS-cipher следующей заменой:
для шифровки CS-cipher использует следующую последовательность ключей и констант:
k
0
,
c
,
c
′
,
k
1
,
c
,
c
′
,
.
.
.
,
k
7
,
c
,
c
′
,
k
8
{\displaystyle k^{0},c,c^{'},k^{1},c,c^{'},...,k^{7},c,c^{'},k^{8}}
. Для удобства переобозначим их как
k
0
,
k
1
,
.
.
.
,
k
24
{\displaystyle k_{0},k_{1},...,k_{24}}
.
По определению[ 25] CSC получается из CS-cipher заменой полученной с помощью генерации ключей и констант последовательности
k
0
,
k
1
,
.
.
.
,
k
24
{\displaystyle k_{0},k_{1},...,k_{24}}
на 1600-битный случайный ключ
k
=
(
k
0
,
k
1
,
.
.
.
,
k
24
)
{\displaystyle k=(k_{0},k_{1},...,k_{24})}
с равномерным распределением.
Полученный шифр CSC является 24 раундовым блочным Марковским шифром[ 26] .
Устойчивость к атакам
Для шифра CSC были доказаны:
Поэтому предполагается, что CS-cipher:
Реализация
Существует реализации данного алгоритма шифрования на С[ 31] ( предоставлена авторами):
# define CSC_C10 0xbf
# define CSC_C11 0x71
# define CSC_C12 0x58
# define CSC_C13 0x80
# define CSC_C14 0x9c
# define CSC_C15 0xf4
# define CSC_C16 0xf3
# define CSC_C17 0xc7
uint8 tbp[256]={
0x29,0x0d,0x61,0x40,0x9c,0xeb,0x9e,0x8f,
0x1f,0x85,0x5f,0x58,0x5b,0x01,0x39,0x86,
0x97,0x2e,0xd7,0xd6,0x35,0xae,0x17,0x16,
0x21,0xb6,0x69,0x4e,0xa5,0x72,0x87,0x08,
0x3c,0x18,0xe6,0xe7,0xfa,0xad,0xb8,0x89,
0xb7,0x00,0xf7,0x6f,0x73,0x84,0x11,0x63,
0x3f,0x96,0x7f,0x6e,0xbf,0x14,0x9d,0xac,
0xa4,0x0e,0x7e,0xf6,0x20,0x4a,0x62,0x30,
0x03,0xc5,0x4b,0x5a,0x46,0xa3,0x44,0x65,
0x7d,0x4d,0x3d,0x42,0x79,0x49,0x1b,0x5c,
0xf5,0x6c,0xb5,0x94,0x54,0xff,0x56,0x57,
0x0b,0xf4,0x43,0x0c,0x4f,0x70,0x6d,0x0a,
0xe4,0x02,0x3e,0x2f,0xa2,0x47,0xe0,0xc1,
0xd5,0x1a,0x95,0xa7,0x51,0x5e,0x33,0x2b,
0x5d,0xd4,0x1d,0x2c,0xee,0x75,0xec,0xdd,
0x7c,0x4c,0xa6,0xb4,0x78,0x48,0x3a,0x32,
0x98,0xaf,0xc0,0xe1,0x2d,0x09,0x0f,0x1e,
0xb9,0x27,0x8a,0xe9,0xbd,0xe3,0x9f,0x07,
0xb1,0xea,0x92,0x93,0x53,0x6a,0x31,0x10,
0x80,0xf2,0xd8,0x9b,0x04,0x36,0x06,0x8e,
0xbe,0xa9,0x64,0x45,0x38,0x1c,0x7a,0x6b,
0xf3,0xa1,0xf0,0xcd,0x37,0x25,0x15,0x81,
0xfb,0x90,0xe8,0xd9,0x7b,0x52,0x19,0x28,
0x26,0x88,0xfc,0xd1,0xe2,0x8c,0xa0,0x34,
0x82,0x67,0xda,0xcb,0xc7,0x41,0xe5,0xc4,
0xc8,0xef,0xdb,0xc3,0xcc,0xab,0xce,0xed,
0xd0,0xbb,0xd3,0xd2,0x71,0x68,0x13,0x12,
0x9a,0xb3,0xc2,0xca,0xde,0x77,0xdc,0xdf,
0x66,0x83,0xbc,0x8d,0x60,0xc6,0x22,0x23,
0xb2,0x8b,0x91,0x05,0x76,0xcf,0x74,0xc9,
0xaa,0xf1,0x99,0xa8,0x59,0x50,0x3b,0x2a,
0xfe,0xf9,0x24,0xb0,0xba,0xfd,0xf8,0x55,
};
void enc_csc(uint8 m[8],uint8* k)
{
uint8 tmpx,tmprx,tmpy;
int i;
#define APPLY_M(cl,cr,adl,adr) \
code=tmpx=m[adl]^cl; \
code=tmprx=(tmpx<<1)^(tmpx>>7); \
code=tmpy=m[adr]^cr; \
code=m[adl]=tbp[(tmprx&0x55)^tmpx^tmpy]; \
code=m[adr]=tbp[tmprx^tmpy];
for(code=i=0;i<8;i++,k+=8)
{
APPLY_M(k[0],k[1],0,1)
APPLY_M(k[2],k[3],2,3)
APPLY_M(k[4],k[5],4,5)
APPLY_M(k[6],k[7],6,7)
APPLY_M(CSC_C00,CSC_C01,0,2)
APPLY_M(CSC_C02,CSC_C03,4,6)
APPLY_M(CSC_C04,CSC_C05,1,3)
APPLY_M(CSC_C06,CSC_C07,5,7)
APPLY_M(CSC_C10,CSC_C11,0,4)
APPLY_M(CSC_C12,CSC_C13,1,5)
APPLY_M(CSC_C14,CSC_C15,2,6)
APPLY_M(CSC_C16,CSC_C17,3,7)
}
for(code=i=0;i<8;i++)
code=m[i]^=k[i];
}
код алгоритма шифровки на С
Также авторами собрана статистика скорости зашифровки данных, оказавшаяся быстрее DES [ 5] :
Скорость зашифровки данных CS-cipher
платформа
тактовая частота
скорость шифровки
VLSI 1216nand 1mm
230 МГц
73 Мбит/с
VLSI 30000nand 15mm
230 МГц
2 Гбит/с
standard C 32bits
133 МГц
2 Мбит/с
bit slice (Pentium)
133 МГц
11 Мбит/с
bit slice (Alpha)
300 МГц
196 Мбит/с
Pentium assembly code
133 МГц
8 Мбит/с
6805 assembly code
4 МГц
20 Кбит/с
Дальнейшее развитие
На основе CS-cipher в 2004 году Томом Ст. Денис был разработан 128-битный шифр
C
S
2
{\displaystyle CS^{2}}
-cipher
[ 32] .
Полученный шифр был проверен и оказался устойчивым к:
Примечания
↑ 1 2 3 A first report on CS-Cipher, 2001 , p. 1.
↑ 1 2 3 4 Cs-Cipher, 1998 , p. 190.
↑ 1 2 NESSIE Public Report D14, 2001 , p. 6.
↑ Cs-Cipher, 1998 , p. 189.
↑ 1 2 Cs-Cipher, 1998 , p. 201.
↑ NESSIE D20-NESSIE security report, 2003 , pp. 4.
↑ 1 2 NESSIE Public Report D18, 2002 , p. 1.
↑ NESSIE D20-NESSIE security report, 2003 , p. 77.
↑ 1 2 3 4 5 6 7 8 9 10 11 12 13 14 Cs-Cipher, 1998 , p. 192.
↑ 1 2 Cs-Cipher, 1998 , p. 195.
↑ Cs-Cipher, 1998 , p. 196.
↑ 1 2 3 Cs-Cipher, 1998 , p. 194.
↑ 1 2 3 4 5 Cs-Cipher, 1998 , p. 197.
↑ 1 2 Cs-Cipher, 1998 , p. 193.
↑ Cs-Cipher, 1998 , pp. 193-195.
↑ Cs-Cipher, 1998 , pp. 196-197.
↑ The Statistical Evaluation, 2002 , pp. 1, 4, 7-16, 18, 21, 22-29.
↑ The Statistical Evaluation, 2002 , pp. 10, 24.
↑ The Statistical Evaluation, 2002 , pp. 12, 25.
↑ The Statistical Evaluation, 2002 , pp. 13, 26.
↑ 1 2 The Statistical Evaluation, 2002 , pp. 9, 23.
↑ The Statistical Evaluation, 2002 , pp. 8, 21.
↑ The Statistical Evaluation, 2002 , p. 30.
↑ On the security of CS-cipher, 1999 , p. 262.
↑ On the security of CS-cipher, 1999 , p. 266.
↑ On the security of CS-cipher, 1999 , p. 267.
↑ 1 2 On the security of CS-cipher, 1999 , p. 269.
↑ On the security of CS-cipher, 1999 , p. 270.
↑ 1 2 Security against impossible differential cryptanalysis, 2008 , p. 10.
↑ 1 2 3 On the security of CS-cipher, 1999 , p. 272.
↑ Cs-Cipher, 1998 , pp. 203-204.
↑ The CS2 Block Cipher, 2004 , p. 1.
↑ The CS2 Block Cipher, 2004 , p. 8.
↑ 1 2 The CS2 Block Cipher, 2004 , p. 9.
Литература
Bart Van Rompay, Vincent Rijmen, Jorge Nakahara Jr. A first report on CS-Cipher, Hierocrypt, Grand Cru, SAFER++ and SHACAL*† NES/DOC/KUL/WP3/006/1 (англ.) . — Katholieke Universiteit Leuven, ESAT-COSIC, 2001. — March.
Fast Software Encryption: 5th International Workshop (англ.) / Vaudenay S. — Paris, France, 1998. — P. 189-204. — 342 p.
Preneel, B. et al. NESSIE D20-NESSIE security report (англ.) . — 2003. — 342 p.
Raddum H. The Statistical Evaluation of the NESSIE Submission CS-cipher NES/DOC/UIB/WP3/010 (англ.) . — 2002.