Федеральный стандарт США — DES

Стандарт шифрования данных DES (Data Encryption Standard), который ANSI называет алгоритмом шифрования данных DEA (Data Encryption Algorithm), a ISO — DEA-1, за 20 лет стал мировым стандартом. За годы своего существования он выдержал натиск различных атак и при известных ограничениях все еще считается криптостойким.

DES представляет собой блочный шифр, шифрующий данные 64-битовыми блоками. С одного конца алгоритма вводится 64-битовый блок открытого текста, а с другого конца выходит 64-битовый блок шифротекста. DES является симметричным алгоритмом: для шифрования и дешифрования используются одинаковые алгоритм и ключ (за исключением небольших различий в использовании ключа). Длина ключа равна 56 битам. (Ключ обычно представляется 64-битовым числом, но каждый восьмой бит используется для проверки четности и игнорируется. Биты четности являются наименьшими значащими битами байтов ключа.) Ключ, который может быть любым 56-битовым числом, можно изменить в любой момент времени.

Криптостойкость полностью определяется ключом. Фундаментальным строительным блоком DES является комбинация подстановок и перестановок. DES состоит из 16 циклов.

Oбщий вид цикла преобразования:

Если L_i и R_i — левая и правая половины, полученные в результате i-й итерации, K_i — 48-битный ключ для цикла i, а f — функция, выполняющая все подстановки, перестановки и XOR с ключом, то один цикл преобразования можно представить как:

(L_i, R_i) = (R_i−1,L_i−1) ⊕ f(R_i−1, K)

Учитывая подстановку F_i(*) и перестановку Т(*), цикл преобразования можно представить так, как это сделано на рис.

Видно, что каждый цикл DES представляет собой композиционный шифр с двумя последовательными преобразованиями — подстановкой F_i(*) и перестановкой Т(*) (за исключением последнего, шестнадцатого цикла, где перестановка опускается).

Подстановка:

(L_i, R_i) = (R_i−1, L_i−1) ⊕ f(R_i−1, K)

является инволюцией, так как

F_i(F_i(L_i−1, R_i−1)) = F_i(R_i−1, L_i−1) ⊕ (f(R_i−1, K_i))) = (R_i−1, L_i−1⊕(f(R_i−1, K_i)) ⊕ (f(R_i−1, K_i))) = (L_i−1, R_i−1)

А подстановка

T(L_i′, R_i′) = (R_i′, L_i′),

так же является инволюцией, так как

T(T(L_i′, R_i′)) = T(R_i′, L_i′) = L_i′, R_i′

Если обозначить начальную и завершающую перестановки как (IP) и (IР)⁻¹, то прямое DES-преобразование (шифрование) реализует функцию:

DES = (IP)F₁TF₂T…F₁₅TF₁₆(IP)⁻¹,

а обратное DES-преобразование (дешифрование) реализует функцию:

DES⁻¹ = (IP)⁻¹F₁₆TF₁₅T…F₂TF₁(IP).

Таким образом, DES является шифром Фейстеля и сконструирован так, чтобы выполнялось полезное свойство: для шифрования и дешифрования используется один и тот же алгоритм. Единственное отличие состоит в том, что ключи должны использоваться в обратном порядке.

То есть если при шифровании использовались ключи K₁, K₂, K₃, …, K₁₆, то ключами дешифрования будут K₁₆, K₁₅, K₁₄, …, K₁. Алгоритм использует только стандартную арифметику 64-битовых чисел и логические операции, поэтому легко реализуется на аппаратном уровне.

DES работает с 64-битовым блоком открытого текста. После первоначальной перестановки блок разбивается на правую и левую половины длиной по 32 бита. Затем выполняется 16 преобразований (функция f), в которых данные объединяются с ключом. После шестнадцатого цикла правая и левая половины объединяются, и алгоритм завершается заключительной перестановкой (обратной по отношению к первоначальной). На каждом цикле (см. рис.) биты ключа сдвигаются, и затем из 56 битов ключа выбираются 48 битов. Правая половина данных увеличивается до 48 битов с помощью перестановки с расширением, объединяется посредством XOR с 48 битами смещенного и переставленного ключа, проходит через 8 S-блоков, образуя 32 новых бита, и переставляется снова. Эти четыре операции и выполняются функцией f.

Затем результат функции f объединяется с левой половиной с помощью другого XOR. В итоге этих действий появляется новая правая половина, а старая правая становится новой левой половиной. Эти действия повторяются 16 раз, образуя 16 циклов DES.