Просмотр кода страницы E2 (шифр)

{{Карточка блочного шифра
|название      = E2
|изображение   =
|ширина        = 275px
|создатель     = [[Nippon Telegraph and Telephone|NTT]]
|опубликован   = [[1998]]
|размер ключа  = 128 (192, 256)  [[бит]]
|размер блока  = 128 [[бит]]
|число раундов = 12
|тип           = [[Сеть Фейстеля|Ячейка Фейстеля]]
|наследник     = [[Camellia (алгоритм)|Camellia]]
}}

'''E2''' ({{lang-en|Efficient Encryption}} — эффективное шифрование) — в [[Криптография|криптографии]] семейство [[Симметричные криптосистемы|симметричных]] блочных криптоалгоритмов на основе [[Сеть Фейстеля|ячейки Фейстеля]]. E2 использует блок размером 128 [[бит]] и ключи длиной 128, 192, 256 бит. Создан в компании [[Nippon Telegraph and Telephone|NTT (Nippon Telegraph and Telephone)]] в [[1998 год]]у и был представлен на [[AES (конкурс)|AES конкурсе]]. Наследником данного шифра является шифр [[Camellia (алгоритм)|Camellia]], который также является результатом творчества компании NTT (Nippon Telegraph and Telephone).

== История ==
Шифр E2, созданный компанией NTT, был представлен на конкурсе AES вместе с другими четырнадцатью шифрами. E2 прошел тест на [[Криптографическая стойкость|криптостойкость]] успешно. Стойкость шифра E2 не повлияла на его быстродействие. E2 занял одну из лидирующих позиций как в соревновании на скорость шифрования/расшифрования, так и в быстроте формирования ключей. В частности, реализация шифра E2 ([[компилятор]] [[Borland]]) показала скорость шифрования/расшифрования 26 Мбит/сек. Впрочем, скорость свыше 25 Мбит/сек была показана и пятью другими лидерами. Несмотря на то, что показатели шифра менялись в зависимости от компилятора, платформы и логики, общая тенденция оставалась неизменной. Большинство авторов, писавших о конкурсе AES, утверждают, что E2 наряду с некоторыми другими шифрами успешно прошел первый круг. Однако E2 не попал в финал в пятерку лучших шифров. [[Национальный институт стандартов и технологий|НИСТ]] было отмечено, что несмотря на хорошие показатели скорости и отсутствие [[уязвимость (компьютерная безопасность)|уязвимостей]], требования к [[Энергонезависимая память|энергонезависимой памяти]] слишком высоки (аналогично пострадал и [[CAST-256]]).
<ref>{{статья
| автор         =
| заглавие      =
| ссылка        = http://www.nist.gov/aes/
| язык          = en
| издание       =
| год           = 1999
}}</ref>

== Алгоритм шифрования ==
<ref name="Specification of E2">
{{книга
 |автор        = Nippon Telegraph and Telephone Corporation
 |заглавие     = Specification of E2 – a 128-bit Block Cipher
 |ссылка       =
 |издание      =
 |место        =
 |издательство =
 |год          = June 14, 1998
 |страницы     = 1—14
 |страниц      = 1-14
}}
</ref>
[[Файл:Функци шифрования алгоритма шифрования E2.png|thumb]]
Работу [[алгоритм]]а [[шифрование|шифрования]] можно разделить на три основные части: IT-функция, или преобразователь начальных данных ({{lang-en|initial transformation (IT)}}), ячейка Фейстеля на базе F-функции, повторяющаяся 12 раз, и FT-функция, или преобразователь конечных данных ({{lang-en|finale transformation (FT)}}). Блок алгоритма, отвечающий за планировку [[Ключ (криптография)|ключей]] ({{lang-en|key sheduling part}}), до начала шифрования из [[Ключ (криптография)|секретного ключа]] К создает шестнадцать подключей {k1,..k16}, каждый из которых является 128-разрядным битовым [[Вектор (программирование)|вектором]] (элементом [[Конечное поле|поля Галуа]](2^128)).
Первое преобразование [[Открытый текст|открытого текста]] M производится с помощью IT-функции и двух сгенерированных ключей под номерами 13 и 14(<math>k_{13}</math> и <math>k_{14}</math>)
: M‘=IT(M,<math>k_{13}</math>,<math>k_{14}</math>)
M` разбивается на два блока <math>L_0</math> и <math>R_0</math> равной длины, каждый из элементов <math>L_{0}</math> и <math>R_{0}</math> является битовым [[Вектор (программирование)|вектором]] размерностью 64 бита. Затем выполняются 12 циклов преобразований в ячейке Фейстеля, в которой правый блок на текущей итерации цикла <math>R_r</math> определяется сложением по модулю два левой части предыдущей итерации цикла <math>R_{r-1}</math> и результата функции F, аргументами которой являются правая часть предыдущей итерации <math>R_{r-1}</math> и ключ <math>k_r</math>, а левому блоку на r шаге цикла присваивается значение правого блока на r-1 шаге. Цикл повторяется 12 раз, то есть r изменяется от 1 до 12
: <math>R_r</math> = <math>L_{r-1}</math><math>\oplus F( R_{r-1} , k_r ) </math>
: <math>L_r</math> = <math>R_{r-1}</math>.
Финальный этап шифрования — выполнение FT-функции. Результат FT-функции, аргументами которой являются [[конкатенация]] правой <math>R_{12}</math> и левой <math>L_{12}</math> частей на выходе 12 итерации ячейки Фейстеля и ключи <math> k_1 , k_2 </math>:

: <math>C = FT(C</math>`<math> ,k_{16} , k_{15} ) </math>

== Алгоритм расшифрования ==
[[Файл:Функци расшифрования алгоритма шифрования E2.png|thumb]]
Расшифрование происходит по схеме, аналогичной шифрованию. Работу [[алгоритм]]а [[Шифр|расшифрования]], можно разделить на три
основные части: IT-функция (начальное преобразование — {{lang-en|initial information (IT)}}), 12 циклов ячейки Фейстеля с F-функцией
и в конце FT-функция ({{lang-en|finale transformation (FT)}}). Блок алгоритма, отвечающий за планировку ключей ({{lang-en|key scheduling}}), из [[Ключ (криптография)|секретного ключа]] непосредственно перед шифрованием генерирует 16 подключей {<math>k_1,k_2,\dots,k_{16}</math>}, которые являются [[бит]]овыми [[Вектор (программирование)|векторами]] размерностью 128 (элементом поля Галуа GF(2^128)).
На первом этапе происходит выполнение IT-функции, аргументами которой являются криптограмма С и два подключа <math>{k_{15},k_{16}}</math>

: <math>C</math>`<math>=IT( C, k_{16}, k_{15})</math>
Результат IT-функции C` разбивается на 2 равные части по 64 бита(половина блока): правую и левую (<math>R_{12},L_{12}</math>). Далее выполняются 12 циклов ячейки Фейстеля на базе F-Функции (<math> r </math> меняется от 12 до 1).

: <math>L_{r-1} = R_{r} \oplus F(L_r,k_r)</math>
: <math>R_{r-1} = L_r</math>
По завершении последнего цикла ячейки Фейстеля осуществляется конкатенация половинок блока (<math>L_0,R_0</math>). И в конце — финальное преобразование: выполняется [[FT-функция]], аргументами которой являются результат конкатенации <math>M</math>` и два ключа <math>k_{13},k_{14}</math>. Результатом выполнения [[FT-функции]] является открытый текст <math>M</math>.

: <math>M = FT(M,k_{13},k_{14})</math>

== Генератор ключей (Планировщик ключей) ==
На основе [[Ключ (криптография)|секретного ключа]] <math>K=(K_1,K_2,K_3,K_4)</math> (<math>K_i</math> {<math>i=1;2;3;4</math>} имеет размерность половины блока, то есть 64 бита и является аргументом для функций шифрования и расшифрования) генерируются подключи <math>ki</math> {i=1;2…16} (битовые [[Вектор (программирование)|вектора]] размерности 128) с помощью G-функции и S-функции. Процедура генерации ключей остается почти неизменной, если длина секретного ключа равна 128, 192 или 256 бит. Если заданная длина 128 бит, в качестве значений <math> K_3,K_4 </math> выбираются константы следующим образом: <math> K_3=S(S(S(v_{-1})))</math> , <math>K_4=S(S(S(S(v_{-1}))))</math>. Если длина ключа 192 бита, значение ключа — <math>K_4=S(S(S(S(v_{-1}))))</math>, где S() — S-функция.

== Элементарные функции ==

=== F-функция ===
[[Файл:F-функция алгоритма шифрования E2.png|thumb]]
: <math>F\colon H \times H^{2} \to H</math>

: <math>(X,(K^{(1)},K^{(2)})) \to Y = BRL(S(P S(X \oplus K^{(1)})) \oplus K^{(2)}))</math>
BRS(),S(),P() — соответственно BRS-функция, S-функция, P-функция; X,Y — слова двоичного алфавита размерностью 64 бита (половина блока); <math>K^{(1)},K^{(2)}</math> — ключи размерностью 128 бит каждый. H — [[пространство]] размерности 64 бита.

Суть F-функции — преобразование слов бинарного алфавита размерности 64 бита при заданном ключе размерности 128 бит. Результат преобразования — слово бинарного алфавита размерности 64 бита.

=== IT-Функция (функция начальной обработки) ===
IT-функция или преобразователь начальных данных:

: <math>IT\colon H^{2} \times H^{2} \times H^{2} \to H</math>

: <math>(X,A,B) \to Y = BP((X\oplus A) \otimes B)</math>
H — пространство слов бинарного алфавита размерности 64 бит; X,A,B — бинарные слова размерности 128 бит; BP() — BP-функция; <math>\otimes</math> — [[бинарная операция]].

=== FT-Функция (функция завершающего преобразования) ===
FT-функция или преобразователь конечных данных:

: <math>FT\colon H^{2} \times H^{2} \times H^{2} \to H</math>

: <math>(X,A,B) \to Y = BP^{-1}((X de B) \oplus A)</math>.
H — пространство слов бинарного алфавита размерности 64 бит; X,A,B — бинарные слова размерности 128 бит; <math>BP^{-1}</math>() — [[Обратная функция|функция, обратная]] BP-функции; <math>de</math> — бинарная операция de.

FT-функция — это функция, обратная IT-функции:

: <math>X=FT(IT(X,A,B),A,B)</math>.

=== BRL-Функция ===
BRL-функция({{lang-en|byte rotate left function}}), или [[Битовый сдвиг|циклический сдвиг]] влево, — составляющая часть F-функции:

: <math>BRL\colon H \to H</math>

: <math>(b1,b2,b3, \dots b8) \to (b2,b3, \dots b8,b1) </math>
<math>b_i</math> {<math>i=1 \dots 8</math>} — бинарное слово размерности 8 бит([[байт]]) или, иными словами, элемент поля Галуа <math>GF(2)^{8}</math>.

=== S-Функция ===
S-функция — часть F-функции, которая определяется [[s-box]]:

: <math>S\colon H \to H</math>

: <math>(x_1,x_2, \dots x_8) \to (s(x_1),s(x_2), \dots s(x_8)) </math>.

=== Структура [[S-box]] ===
S-box, использующийся в S-функции, определяется следующим образом:

: <math>s:B \to B</math>
: <math>x \to Affine(Power(x,127),97,255)</math>,

: где <math>Power(x,e)=x^{e} in GF(2^8)</math>
: <math>Affine(y,a,b)=a*y+b(mod 2^8 Z)</math>
Не возбраняется при расчетах пользоваться таблицами c уже вычисленными значениями s(x). То есть <math>s(0)=225, s(1)=66, \dots , s(16)=204, \dots , s(255)=42.</math>

{| class="wikitable" align="center" style="text-align:center; width:100%;"
|+ Таблица вычисленных значений s-box:
| 225 || 66 || 62 || 129 || 78 || 23 || 158 || 253 || 180 || 63 || 44 || 218 || 49 || 30 || 224 || 65
|-
| 204 || 243 || 130 || 125 || 124 || 18 || 142 || 187 || 228 || 88 || 21 || 213 || 111 || 233 || 76 || 75
|-
| 53 || 123 || 90 || 154 || 144 || 69 || 188 || 248 || 121 || 214 || 27 || 136 || 2 || 171 || 207 || 100
|-
| 9 || 12 || 240 || 1 || 164 || 176 || 246 || 147 || 67 || 99 || 134 || 220 || 17 || 165 || 131 || 139
|-
| 201 || 208 || 25 || 149 || 106 || 161 || 92 || 36 || 110 || 80 || 33 || 128 || 47 || 231 || 83 || 15
|-
| 145 || 34 || 4 || 237 || 166 || 72 || 73 || 103 || 236 || 247 || 192 || 57 || 206 || 242 || 45 || 190
|-
| 93 || 28 || 227 || 135 || 7 || 13 || 122 || 244 || 251 || 50 || 245 || 140 || 219 || 143 || 37 || 150
|-
| 168 || 234 || 205 || 51 || 101 || 84 || 6 || 141 || 137 || 10 || 94 || 217 || 22 || 14 || 113 || 108
|-
| 11 || 255 || 96 || 210 || 46 || 211 || 200 || 85 || 194 || 35 || 183 || 116 || 226 || 155 || 223 || 119
|-
| 43 || 185 || 60 || 98 || 19 || 229 || 148 || 52 || 177 || 39 || 132 || 159 || 215 || 81 || 0 || 97
|-
| 173 || 133 || 115 || 3 || 8 || 64 || 239 || 104 || 254 || 151 || 31 || 222 || 175 || 102 || 232 || 184
|-
| 174 || 189 || 179 || 235 || 198 || 107 || 71 || 169 || 216 || 167 || 114 || 238 || 29 || 126 || 170 || 182
|-
| 117 || 203 || 212 || 48 || 105 || 32 || 127 || 55 || 91 || 157 || 120 || 163 || 241 || 118 || 250 || 5
|-
| 61 || 58 || 68 || 87 || 59 || 202 || 199 || 138 || 24 || 70 || 156 || 191 || 186 || 56 || 86 || 26
|-
| 146 || 77 || 38 || 41 || 162 || 152 || 16 || 153 || 112 || 160 || 197 || 40 || 193 || 109 || 20 || 172
|-
| 249 || 95 || 79 || 196 || 195 || 209 || 252 || 221 || 178 || 89 || 230 || 181 || 54 || 82 || 74 || 42
|-
|}

=== P-Функция ===
P-функция — составляющая часть F-функции

: <math>P\colon H \to H</math>

: <math>\begin{pmatrix} z_{1} \\ \vdots \\ z_{8} \end{pmatrix} \to \begin{pmatrix} z^{|}_{1} \\ \vdots \\ z^{|}_{8} \end{pmatrix} =P \begin{pmatrix} z_{1} \\ \vdots \\ z_{8} \end{pmatrix} </math>

P — матрица преобразования описывающая P-функцию

: <math>P = \begin{pmatrix} 0 & 1 & 1 & 1 & 1 & 1 & 1 & 0 \\ 1 & 0 & 1 & 1 & 0 & 1 & 1 & 1 \\ 1 & 1 & 0 & 1 & 1 & 0 & 1 & 1\\ 1 & 1 & 1 & 0 & 1 & 1 & 0 & 1\\ 1 & 1 & 0 & 1 & 1 & 1 & 0 & 0 \\ 1 & 1 & 1 & 0 & 0 & 1 & 1 & 0\\0 & 1 & 1 & 1 & 0 & 0 & 1 & 1 \\ 1 & 0 & 1 & 1 & 1 & 0 & 0 & 1 \end{pmatrix}</math>

=== G-Функция ===
[[Файл:G-функция алгоритма шифрования E2.png|thumb]]
G — функция осуществляет следующее отображение:

: <math>G \colon H^{4} \times H  \to H^4 \times ( \! H^4 \times H )</math>

: <math> ( \! ( \! X_1 , X_2 , X_3 , X_4 ) \! , U_0) \to ( \! ( \! U_1 , U_2 , U_3 , U_4 \! ), ( \!( \! Y_1 , Y_2 , Y_3 , Y_4 ), V \!) \! )</math> , где

: <math> Y_i = \! f(X_i) (i = \! 1 , 2 , 3 , 4) </math>

: <math> U_i = \! f(U_{i-1}) \oplus Y_i (i = \! 1 , 2 , 3 , 4) </math>

: <math> V = \! U_4 </math>

: <math>f()</math> — f-функция.

=== f-функция ===
f-функция необходима для вычисления G-функции.
f-функция определяется следующим образом:

: <math>f \colon H \to H</math>

: <math>X \to P(S(X))</math> , где
P() — P-функция, S() — S-функция.

=== Бинарный оператор <math>\otimes</math> ===
Бинарный оператор <math>\otimes</math> определяется следующим образом:

: <math>Y = \! X \otimes B (X , Y , B ) \in H^2 </math>, где

: <math> (x_1 , x_2 , x_3 , x_4)=X (x_i \in W, i=1,2,3,4) </math>

: <math> (b_1 , b_2 , b_3 , b_4)=B (b_i \in W, i=1,2,3,4) </math>

: <math>y_i = \! x_i(b_i \lor 1) mod 2^{32} Z (i=1,2,3,4)</math>

: <math> Y = (y_1, y_2, y_3 , y_4) </math>

: <math>\lor 1</math> — логическое побитовое сложение (логическое «или») с 1 в [[Кольцо (математика)|кольце]] <math>2^{32}Z</math>.

=== Бинарный оператор de ===
Бинарный оператор de определяется следующим образом:

: <math>Y = \! X de B (X , Y , B \in H^2)</math> , где

: <math> (y_1 , y_2 , y_3 , y_4)=Y (y_i \in W, i=1,2,3,4) </math>

: <math> (b_1 , b_2 , b_3 , b_4)=B (b_i \in W, i=1,2,3,4) </math>

: <math>x_i = \! y_i(b_i \lor 1) mod 2^{32} Z (i=1,2,3,4)</math>

: <math> X = (x_1, x_2, x_3 , x_4) </math>

: <math>\lor 1</math> — логическое побитовое сложение (логическое «или») с 1 в кольце <math>2^{32}Z</math>.

=== BP-функция ===
BP- функция, или функция перестановки байтов ({{lang-en|byte permutation}}), является частью IT-функции и FT — функции. Она определяется следующим образом:

: <math>BP:W^{4} \to W^{4}</math>

: <math>(x_1 , x_2 , x_3 , x_4) \to (y_1 , y_2 , y_3 , y_4) </math> ,где

: <math>(x_i^{(1)} , x_i^{(2)} , x_i^{(3)} , x_i^{(4)}) = \! x_i (x_i^j \in B {i=1,2,3,4; j=1,2,3,4})</math>

: <math>y_i = (x_i^{(1)}, x_{i+1}^{(2)}, x_{i+2}^{(3)}, x_{i+3}^{(4)}) (i=1,2,3,4)</math>

: <math>Y = (y_1, y_2, y_3, y_4)</math>.
Обратное к BP — преобразованию, или BP^{-1}, вычисляется следующим образом:
: <math>BP^{-1}:W^{4} \to W^{4}</math>

: <math>(y_1 , y_2 , y_3 , y_4) \to (x_1 , x_2 , x_3 , x_4) </math> ,где

: <math>(y_i^{(1)} , y_i^{(2)} , y_i^{(3)} , y_i^{(4)}) = \! y_i (y_i^j \in B {i=1,2,3,4; j=1,2,3,4})</math>

: <math>x_i = (y_i^{(1)}, y_{i+1}^{(2)}, y_{i+2}^{(3)}, y_{i+3}^{(4)}) (i=1,2,3,4)</math>

: <math>Y = (y_1, y_2, y_3, y_4)</math>.

[[Файл:BP-функция шифр E2.png|thumb]]

== Криптоанализ алгоритма ==
Сотрудниками компании Information Technology R&D Center Mitsubishi Electric Corporation Мицуру Мацуи (''Mitsuru Matsui'') и Тосио Токита (''Toshio Tokita'') была обнаружена нестойкость шифра к [[дифференциальный криптоанализ|дифференциальному криптоанализу]].<ref name="Cryptanalysis of a Reduced Version of the Block Cipher E2">
{{книга
 |автор        = Mitsuru Matsui and Toshio Tokita
 |заглавие     = Сryptanalysis of a Reduced Version of the Block Cipher E2"
 |ссылка       =
 |издание      =
 |место        =
 |издательство =
 |год          =
 |страницы     =
 |страниц      =
}}
</ref> Несмотря на это шифр (использующий 12 циклов шифрования) остается стойким с практической точки зрения. Хотя Мицуру Мацуи и Тосио Токита удалось показать, что уровень безопасность шифра E2 с меньшим числом циклов шифрования существенно ниже того, что заявлено разработчиками.

== Недостатки шифра ==
Высокие требования к энергонезависимой памяти.

== См. также ==
* [[Camellia (алгоритм)|Camellia]]
* [[Блочный шифр]]
* [[Сеть Фейстеля|Ячейка Фейстеля]]
* [[AES (конкурс)]]

== Примечания ==
{{примечания}}

== Ссылки ==
* [http://www.ntt.co.jp/index_e.html Официальный сайт компании Nippon Telegraph and Telephone]
* [http://www.nist.gov Сайт The National Institute of Standards and Technology ]

{{симметричные криптоалгоритмы}}

[[Категория:Блочные шифры]]