Симметричные криптосистемы.

Симметричные алгоритмы – алгоритмы, где для шифрования и дешифрования используется один ключ. Вся криптостойкость симметричных алгоритмов основана на секретности симметричного ключа.

Существуют блочные и поточные шифры. В блочных шифрах открытый текст шифруется блоками фиксированной длины, а в поточных шифрах шифрование производится побитно.

DES

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

Схема DES-преобразования

Рисунок 2.1

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

(L_i, R_i) = (R_i-1, L_i-1ÅF (R_i-1, K_i)).

Общий вид цикла DES-преобразования

Рисунок 2.2

Учитывая подстановку F_i(×) и перестановку Т(×), цикл преобразования можно представить так, как это сделано на рис. 2.3. Из него видно, что каждый цикл DES представляет собой композиционный шифр с двумя последовательными преобразованиями – подстановкой F_i(×) и перестановкой Т(×) (за исключением последнего, шестнадцатого цикла, где перестановка опускается).

Один цикл DES-преобразования

Рисунок 2.3

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

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

Начальная перестановка выполняется еще до первого цикла.

Процедура преобразования ключа сводится к следующим действиям. Сначала 64-битовый ключ DES уменьшается до 56-битового ключа отбрасыванием каждого восьмого бита.

После извлечения 56-битного ключа для каждого из 16 циклов генерируется новый 48-битный подключ. Эти подключи К_i определяются следующим образом. Сначала 56-битный ключ делится на две 28-битные половины. Затем половины циклически сдвигаются влево на один или два бита в зависимости от номера цикла. Этот сдвиг показан в таблице 2.3.

Таблица 2.3

DES – сдвиг ключа в зависимости от номера цикла

После сдвига выбирается 48 бит из 56. Так как при этом не только выбирается подмножество битов, но и изменяется их порядок, эта операция получила название перестановка со сжатием. Ее результатом является набор из 48 бит.

Операция перестановки с расширением правой половины данных, R_i, от 32 до 48 битов и изменением их порядка, называется перестановкой с расширением. У этой операции две задачи: привести размер правой половины в соответствие с ключом для операции XOR и получить более длинный результат, который можно будет сжать в ходе операции подстановки.

После объединения сжатого блока с расширенным блоком с помощью операции XOR над 48-битным результатом выполняется операция подстановки. Подстановка производится в восьми блоках, или S-блоках (от substitution). У каждого S-блока есть свой 6-битный вход и 4-битный выход, всего используется восемь различных S-блоков. (Для восьми S-блоков DES потребуется 256 байтов памяти). 48 битов делятся на восемь 6-битовых подблоков. Каждый отдельный подблок обрабатывается отдельным S-блоком: первый подблок - первым S-блоком, второй – вторым S-блоком и так далее (см. рис. 2.4).

DES-подстановка при помощи S-блоков

Рисунок 2.4

Каждый S-блок представляет собой таблицу из четырех строк и шестнадцати столбцов. Каждый элемент в блоке является 4-битным столбцом. По шести входным битам S-блока определяется, под какими номерами столбцов и строк следует искать выходное значение.

Входные биты особым образом определяют элемент S-блока. Рассмотрим 6-битовый вход S-блока: b₁, b₂, b₃, b₄, b₅ и b₆. Биты b₁ и b₆ объединяются, образуя 2-битное число от 0 до 3, соответствующее строке таблицы. Средние четыре бита, с b₂ по b₅, объединяются, образуя 4-битное число от 0 до15, соответствующее столбцу таблицы. Необходимо учитывать, что строки и столбцы нумеруются с нуля, а не с единицы. В результате этой подстановки получается восемь 4-битных блоков, которые вновь объединяются в единый 32-битный блок. Этот блок поступает на вход следующего этапа – перестановки с помощью Р-блока.

32-битный выход подстановки с помощью S-блоков перетасовывается в соответствии с Р-блоком. Эта перестановка перемещает каждый входной бит в другую позицию, ни один бит не используется дважды, и ни один бит не игнорируется. Этот процесс называется прямой перестановкой, или просто перестановкой.

Наконец, результат перестановки с помощью Р-блока объединяется посредством XOR с левой половиной первоначального 64-битового блока. Затем левая и правая половины меняются местами, и начинается следующий цикл криптографического преобразования.

Заключительная перестановка является обратной по отношению к первоначальной.

Отметим, что левая и правая части не меняются местами после завершения последнего цикла DES, вместо этого объединенный блок R₁₆L₁₆ используется как вход заключительной перестановки. Перестановка половин с последующим циклическим сдвигом привела бы к точно такому же результату. Это сделано для того, чтобы алгоритм шифрования можно было использовать как для шифрования, так и для дешифрования.

Алгоритм, который создает ключ для каждого цикла, также цикличен. Ключ сдвигается направо, а число позиций сдвига равно 0, 1, 2, 2, 2, 2, 2, 2, 1, 2, 2, 2, 2, 2, 2, 1.