Алгоритм шифрования DES

Стандарт шифрования данных (DES - Data Encryption Standard) принят в США в 1977 году в качестве
федерального. В стандарт входит описание блочного шифра типа шифра Файстеля, а также различных
режимов его работы, как составной части нескольких процедур криптографического преобразования данных.
Обычно под аббревиатурой DES понимается именно блочный шифр, который в стандарте соответствует
процедуре шифрования в режиме электронной кодовой книги (ECB - Е1есtrоnic Соdеbооk Моdе). Название
вызвано тем, что любой блочный шифр является простым подстановочным шифром и в этом отношении
подобен кодовой книге
 Структура DES

1. DES представляет собой блочный шифр, он шифрует данные 64-битовыми

блоками.

2. DES является симметричным алгоритмом: для шифрования и дешифрирования

используются одинаковые алгоритм и ключ (за исключением небольших различий в
использовании ключа).
Длина ключа равна 56 битам.
Безопасность полностью определяется ключом.

3. Алгоритм представляет собой комбинацию двух основных методов шифрования:

смещения и диффузии.

Фундаментальным строительным блоком DES является применение к тексту

единичной комбинации этих методов (подстановка, а за ней – перестановка),
зависящей от ключа. Такой блок называется этапом.

4. DES состоит из 16 этапов, одинаковая комбинация методов применяется к

открытому тексту 16 раз.
Входом в блочный шифр и результатом его работы является блок длины n
- последовательность, состоящая из n бит. Число n постоянно. При
необходимости шифрования сообщения длиной, большей n, оно
разбивается на блоки, каждый из которых шифруется отдельно.
Различные режимы работы связаны с дополнительными усложнениями
блочного шифра при переходах от блока к блоку. В стандарте DES длина
блока n = 64. В режиме ECB шифрование блока открытого текста В
производится за 16 однотипных итераций, именуемых циклами
 Схема алгоритма

DES работает с 64-битовым блоком открытого текста:

1. после первоначальной перестановки
2. блок разбивается на правую и левую половины длиной по 32 бита;
3. затем выполняются 16 этапов одинаковых действий, называемых функцией f, в которых
данные объединяются с ключом;
4. после шестнадцатого этапа правая и левая половины объединяются;
5. алгоритм завершается заключительной перестановкой (обратной по отношению к
первоначальной).

На каждом этапе биты ключа сдвигаются, затем из 56 битов ключа выбирается 48 битов.

Функцией f выполняются четыре операции:

− правая половина данных увеличивается до 48 битов с помощью перестановки с
расширением,
− объединяется посредством XOR («исключающее ИЛИ», суммирование по модулю 2) с 48
битами смещенного и переставленного ключа,
− проходит через 8 S-блоков, образуя 32 новых бита,
− переставляется снова.

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

Сдвиг Сдвиг

Подстановка
в S-блоке

Перестановка в P-
блоке

Li Ri Ключ

Один этап DES

Если

Li и Ri – левая и правая половины кода − результата i-той итерации,

Ki – 48-битовый ключ для этапа i,
f – функция, выполняющая все подстановки, перестановки и XOR с ключом,
то этап можно представить как:
Li  Ri  1
Ri  Li  1  f ( Ri  1 , K i )
Биты входного блока перед первым циклом переставляются в соответствии с таблицей в ходе так
называемой начальной перестановки (IP - initial permutation). После выхода из последнего цикла L и R
переставляются местами, после чего соединяются в блок. Биты полученного блока снова переставляются в
соответствии с перестановкой IP-1, обратной начальной. Результат принимается в качестве блока
шифртекста.

Начальная перестановка IP
Перед шифрованием, в соответствии с процедурой выбора PC1 (таблица 9.2), из X выбираются 56 бит, которыми
заполняются два регистра (C и D) длиной 28 бит каждый. В дальнейшем, при входе в очередной цикл с номером i,
регистры сдвигаются циклически влево. Величина сдвига зависит от номера цикла, но является фиксированной и
заранее известна. После сдвига оба подблока объединяются в порядке (C, D). Затем, в соответствии с функцией
выбора PC2 (таблица 9.3), из них выбираются 48 бит подключа Xi. Шифрование и расшифровывание отличаются
направлением сдвигов (таблица 9.4)
На каждом цикле (рисунок 9.2) из ключа X длиной
56 бит формируется ключ Xi размером 48 бит. Сам
ключ X размещается в восьми байтовом слове,
причем восьмые разряды каждого байта являются
контрольными и в ключ не входят.
 Преобразования ключа
1. Сначала 64-битовый ключ DES уменьшается до 56-битового ключа отбрасыванием каждого восьмого бита.
(Эти биты используются только для контроля четности, позволяя проверять правильность ключа).
2. После извлечения 56-битового ключа для каждого из 16 этапов DES генерируется новый 56-битовый подключ.
Эти подключи Ki определяются следующим образом:

Перестановка ключа − формирование подключа

57, 49, 41, 33, 25, 17, 9, 1, 58, 50, 42, 34, 26, 18,
10, 2, 59, 51, 43, 35, 27, 19, 11, 3, 60, 52, 44, 36,
63, 55, 47, 39, 31, 23, 15, 7, 62, 54, 46, 38, 30, 22,
14, 6, 61, 53, 45, 37, 29, 21, 13, 5, 28, 20, 12, 4

3. Далее 56-битовый подключ делится на две 28-битовых половинки.

4. Затем эти половинки циклически сдвигаются налево на один или два бита в зависимости от этапа.

Число битов сдвига ключа в зависимости от этапа

Этап 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
Число 1 1 2 2 2 2 2 2 1 2 2 2 2 2 2 1

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

Перестановка со сжатием
14, 17, 11, 24, 1, 5, 3, 28, 15, 6, 21, 10,
23, 19, 12, 4, 26, 8, 16, 7, 27, 20, 13, 2,
41, 52, 32, 37, 47, 55, 30, 40, 51, 45, 33, 48,
44, 49, 39, 56, 34, 53, 46, 42, 50, 36, 29, 32
Шифрование и расшифровывание отличаются направлением
сдвигов (таблица 9.4)
 Перестановка с расширением
Операция расширяет правую половину данных Ri от 32 до 48 битов.
Так как при этом не просто повторяются определенные биты, но и изменяется их порядок, эта операция
называется перестановкой с расширением.
Операция решает две задачи: привести размер правой половины в соответствие с ключом для операции XOR и
получить более длинный результат, который можно будет сжать в ходе операции подстановки.

Криптографический смысл:
за счет влияния одного бита на две подстановки быстрее возрастает зависимость битов результата от битов
исходных данных.
Это называется лавинным эффектом.
Перестановка с расширением иногда называется E-блоком (от expansion).

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16

32

48

1 2 3 4 5 6 78 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24

Схема перестановки с расширением

Перестановка с расширением

32, 1, 2, 3, 4, 5, 4, 5, 6, 7, 8, 9,
8, 9, 10, 11, 12, 13, 12, 13, 14, 15, 16, 17,
16, 17, 18, 19, 20, 21, 20, 21, 22, 23, 24, 25,
24, 25, 26, 27, 28, 29, 28, 29, 30, 31, 32, 1
 Подстановка с помощью S-блоков

Подстановки производятся в восьми блоках подстановки, или S-блоках (от

substitution).

1. Каждый S-блок имеет 6-битовый вход и 4-битовый выход .

2. 48 битов делятся на восемь 6-битовых подблоков.
3. Каждый отдельный подблок обрабатывается отдельным S-блоком: первый
подблок – S-блоком 1, второй – S-блоком 2, и так далее.

48-битовый вход

S-блок S-блок S-блок S-блок S-блок S-блок S-блок S-блок

1 2 3 4 5 6 7 8

32-битовый выход

Подстановка с помощью S-блоков

Криптографическая система RSA
RSA - криптосистема с открытым ключом

Перед отправкой сообщения адресату исходный текст шифруется

открытым (общедоступным) ключом адресата. Алгоритм шифрования
построен таким образом, что расшифровывание сообщения возможно только
с использованием личного (секретного) ключа адресата.
Суть этой модели состоит в том, что ключ известен полностью только
получателю сообщения и представляет собой тройку чисел k = (е, d, n), где
подключ e служит ключом шифрования, а ключ d - ключом
расшифровывания. При этом только d является секретным (личным)
ключом. В криптосистеме с открытым ключом сообщение, предназначенное
абоненту, зашифровывается отправителем.
 Криптосистема RSA на каждом такте шифрования преобразует двоичный блок открытого текста m длины size(n),
рассматриваемый как целое число, в соответствии с формулой:
c = me(mod n).
При этом n = pq , где p и q - случайные простые числа большой разрядности, которые
уничтожаются после формирования модуля и ключей. Открытый ключ состоит из пары чисел e и n. Подключ e
выбирается как достаточно большое число из диапазона:
1 < e < φ(n), с условием:
НОД(e, j(n)) = 1, где j(n) - наименьшее общее кратное чисел p–1 и q–1.

Далее, решая в целых числах x, y уравнение

xe + yφ(n) = 1, полагается
d = х, т.е. ed = 1(mod j(n)).
При этом для всех m выполняется соотношение
med = m(mod n) ,
поэтому знание d позволяет расшифровывать криптограммы.
Чтобы гарантировать надежную защиту информации, к системам с открытым ключом предъявляются два
следующих требования.
1. Преобразование исходного текста должно исключать его восстановление на основе открытого ключа.
2. Определение закрытого ключа на основе открытого также должно быть вычислительно нереализуемым.
Алгоритмы шифрования с открытым ключом получили широкое применение в современных информационных
системах.
 Компоненты схемы RSA:
риq — два простых числа (секретные, выбираются),
п = pq (открытое, вычисляется),
такое е, что (ф(n), е) = 1, 1 < е < ф(n) (открытое, выбирается),
d ≡ e -1 (mod ф(п)) (секретное, вычисляется).
Личный ключ складывается из {d, n}, а открытый — из {е,
n}.

Алгоритм RSA
Вычисление ключей

Выбор р, q р и q должны быть простыми

Вычисление n=pхq
Вычисление ф(п) = (p-1)(q-1)

Выбор целого е (ф(n), e) = 1, 1 < е < ф(n)
Вычисление d d ≡ e -1 mod ф(n)
Открытый ключ KU = {e, n}
Личный ключ KR = {d, n}
Шифрование

Открытый текст: M<n

Шифрованный текст: C = Me (mod n)

Дешифрование

Открытый текст: C
Дешифрованный текст: M = Cd (mod n)
 Рассмотрим построение криптосистемы RSA на простом примере.
1. Выберем p = 3 и q = 11.
2. Определим n = 3 · 11 = 33.
3. Найдем j(n) = (p – 1)(q – 1) = 20.
4. Выберем e, взаимно простое с 20, например, e = 7.
5. Выберем число d, удовлетворяющее 7d = 1(mоd 20).
Легко увидеть, что d = 3(mоd 20).
Существование числа d, удовлетворяющего условию шага 5, следует из теоремы Евклида: для любых целых чисел a и
b найдутся целые числа x и y, такие, что ax + by = НОД(a,b). Расширенный алгоритм Евклида позволяет эффективно
вычислить это число d.
Представим шифруемое сообщение как последовательность целых чисел с помощью соответствия: А = 1, B = 2, С =
3, ..., Z = 26. Поскольку size(n) = 6, то наша криптосистема в состоянии зашифровывать буквы латинского алфавита,
рассматриваемые как блоки, Опубликуем открытый ключ (e, n) = (7, 33) и предположим прочим участникам системы
секретной связи зашифровывать с его помощью сообщения, направляемые в наш адрес. Пусть таким сообщением будет
CAB, которое в выбранной нами кодировке принимает вид (3, 1, 2). Отправитель должен зашифровать каждый блок и
отправить зашифрованное сообщение в наш адрес:
RSA(C) = RSA(3) = 37 = 2187 = 9(mod 33);
RSA(A) = RSA(1) = 17 = 1(mod 33);
RSA(B) = RSA(1) = 27 = 128 = 29(mod 33).
Получив зашифрованное сообщение (9, 1, 29), мы сможем его расшифровать
на основе секретного ключа (d, n) = (3, 33), возводя каждый блок в степень d = 3:
93 = 729 = 3(mоd 33);
13 = 1(mоd 33);
293 = 24389 = 2(mоd 33).
 Пример 2
Боб выбирает 7 и 11 как p и q и вычисляет n=7x11 = 77.
Значение j(n) = (7-1)x(11-1) = 60. Боб выбирает два ключа,
e и d. e должно быть взаимно простое с j(n). d и e инверсны
по модулю j(n). Боб выбирает e=13, то d=37. Обратите
внимание что e*d mod 60 = 1 (они инверсны друг другу.
Предположим, что Алиса хочет передать исходный текст 5
Бобу. Она использует общедоступный ключ 13, чтобы
зашифровать сообщение 5.
Боб получает зашифрованный текст 26 и использует секретный ключ 37, чтобы
расшифровать зашифрованный текст
Цифровая подпись RSA
Первый этап – генерация цифровой подписи:
1) Возьмем открытый текст 𝑚.
2) Для создания подписи, обозначаемой 𝑠 , необходимо
воспользоваться сгенерированным ранее закрытым ключом:

3) Передаем пару {𝑠, 𝑚}, состоящую из подписи и открытого текста.

Второй этап – проверка неизменности сообщения с помощью
электронной подписи:
4) Используя полученную подпись и открытый ключ, сгенерируем
прообраз текста 𝑚, обычно обозначаемый 𝑚′

2) Сравниваем прообраз𝑚′ и сам текст 𝑚, тем самым выясняя

подлинность подписи и целостность текста
Если m ≡ m′, то подпись считается правильной..
Алгоритм с закрытым текстом Данный способ предоставляет большую защиту,
однако требует дополнительных вычислений. Алгоритм:
1) Отправитель шифрует исходный текст алгоритмом RSA с помощью открытого
ключа получателя.
2) Далее отправитель должен сгенерировать цифровую подпись с помощью
своего закрытого ключа.
3) Шифруем полученную подпись открытым ключом получателя.
4) Отправляем зашифрованный текст и подпись.
5) Получатель расшифровывает текст и подпись с помощью своего закрытого
ключа.
6) С помощью расшифрованной подписи и открытого ключа получателя создаем
прообраз исходного текста.
7) Сравниваем прообраз и исходный текст.