Совместное использование симметричных и асимметричных шифров

 

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

При анализе системы, в которой совместно используются несколько алгоритмов, принято оценивать сложность ее взлома по сложности взлома самого слабого звена. В литературе [9] приводится примерное соответствие длин ключей для алгоритма симметричного шифрования (атака производится путем перебора ключевого множества) и алгоритма RSA, обеспечивающих сопоставимую стойкость. Например, 64-битному ключу симметричного шифрования примерно соответствует 512-битный ключ RSA, а 128-битному – ключ RSA длиной более 2300 бит.

 

Хэш-функции

В рассмотренных в разделе 2.4 алгоритмах формирования ЭЦП длина подписи получается равной или даже большей, чем длина самого сообщения. Очевидно, что удостоверять подобным образом большой документ неудобно. Поэтому подписывается, как правило, не само сообщение, а его «дайджест» – значение фиксированной длины, зависящее от подписываемого сообщения. Для формирования дайджеста используется хэш-функция (от англ. «hash function») – односторонняя функция, преобразующая строку произвольной длины в строку фиксированной длины. В криптографии используются хэш-функции 2 классов:

- хэш-функции без ключа;

- хэш-функции с ключом.

 

Хэш-функции без ключа

 

Хэш-функции без ключа делятся на слабые и сильные. Слабой хэш-функцией называется односторонняя функция H(x),удовлетворяющая следующим условиям:

1) аргумент может быть строкой бит произвольной длины;

2) значение функции H(x) должно быть строкой бит фиксированной длины;

3) значение H(x) легко вычислить;

4) для любого фиксированного аргумента x вычислительно невозможно найти другой x’ x, такой что H(x’)=H(x).

Пара значений x’ x: H(x’)=H(x) называется коллизией хэш-функции.

Сильной хэш-функцией называется односторонняя функция H(x),удовлетворяющая условиям 1) – 3) и последнему условию в следую-щей формулировке:

5) вычислительно невозможно любую пару значений x’ x, таких

что H(x’)=H(x).

Любая сильная хэш-функция соответствует и требованиям для слабой, обратное в общем случае неверно. Для иллюстрации различия в сложности поиска коллизий слабой и сильной хэш-функции рассмотрим атаку с использованием «парадокса дней рождения»¹. Зафиксируем значение аргумента x, и будем перебирать случайным образом x’ x в поисках ситуации, когда H(x’)=H(x). Если предположить, что значения хэш-функции равномерно распределены, а число возможных значений H(x) равно N, то потребуется в среднем перебор N / 2вариантов.Если же мы захотим найти какую-либо коллизию вообще, то задача оказывается проще: с вероятностью 0,63 для определения нужной пары значений потребуется опробовать N вариантов.

Чтобы минимизировать стоимость создания криптографических хэш-функций, разработчики часто используют один из существующих алгоритмов шифрования. Пусть E(m,k) обозначает шифрование сообщения m на ключе k, а v₀ – стартовый вектор. Представим кэшируемое сообщение M в виде последовательности блоков m₁, …, m_t и будем их использовать в качестве раундовых ключей. Тогда H(m) вычисляется следующим образом:

 

h0 = v0,
h i = E(h i-1,mi), i = 1t,	(2.24)
H(m) = h t.

 

Однако в варианте с использованием в качестве E(m,k) алгоритма DES, хэш-функция оказалась недостаточно стойкой из-за подверженности атаке, основанной на «парадоксе дней рождения». И было предложено улучшить эту схему, например, следующим образом:

h 0 = v0,
h i = E(h i-1,mi)h i-1,i=1t,	(2.25)
H(m) = h t.
Существует и ряд специально разработанных	алгоритмов хе-
ширования, один из которых – SHA-1.

 

Алгоритм SHA-1

 

 

Алгоритм SHA (Secure Hash Algorithm) разработан в США как часть стандарта SHS (Secure Hash Standard), опубликованного в 1993 году. Но в нем были обнаружены уязвимости, которые привели к необходимости модифицировать алгоритм. Через два года была опубликована новая версия – SHA-1, получившая на сегодняшний день широкое распространение.

Получая на входе сообщение произвольной длины менее 2⁶⁴ бит, SHA-1 формирует 160-битное выходное сообщение (дайджест). Вначале преобразуемое сообщение M дополняется до длины, кратной 512 битам. Заполнитель формируется следующим образом: в конец пре-образуемого сообщения добавляется 1, потом – столько нулей, сколь-ко необходимо для получения сообщения, которое на 64 бита короче, чем кратное 512, после чего добавляют 64-битное представление длины исходного сообщения. Например, если сообщение длиной 800 бит, то 801-й бит =1, потом добавляем нули до 960 бит, после чего – в оставшихся 64-разрядах записывается число «800», в итоге хэшируем 1024-битное сообщение. Общая схема преобразования представлена на Рисунок 2.18. Перед началом преобразований инициализируется пять 32-битных переменных:

A =0x67452301; B =0xEFCDAB89; C =0x98BADCFE; D =0x10325476; E =0xC3D2E1F0.

Эти значения присваиваются также переменным a₀, b₀, c₀, d₀, e₀. Преобразование производится над блоком сообщения размером 512 бит в 80 раундов. В процессе преобразования используются следующие нелинейные функции f_t:

f_t(X,Y,Z)=(X Y) ((X) Z) для t =0…19;

f_t(X,Y,Z)=X Y Z для t =20…39 и t =60…79;

f_t(X,Y,Z)=(X Y) (X Z) (Y Z) для t =40…59.

 

Рисунок 2.18 - Схема раунда алгоритма SHA-1

 

В процессе преобразования используются четыре константы:

K_t =0x5A827999 для t =0…19;

K_t =0x6ED9EBA1 для t =20…39;

K_t =0x8F1BBCDC для t =40…59;

K_t =0xCA62C1D6 для t =60…79.

Блок исходного сообщения M представляется в виде 16-ти 32-разрядных подблоков M0, …, M15, которые используются для формирования значений Wt:
Wt = Mt	для t =0…15;
Wt =(Wt-3Wt-8Wt-14Wt-16)<<<1	для t =16…79.

 

Обозначение «<<< X» – циклический сдвиг влево на X разрядов, «+» – сложение по модулю 2³².

После преобразования очередного 512-битного блока, полученные значения a, b, c, d, e складываются со значениями A, B, C, D, E соответственно, и начинается обработка следующего блока (или полученное значение в виде сцепления a, b, c, d, e подается на выход, если обработанный блок был последним).

Таким образом, на выходе получаем 160-битный дайджест исходного сообщения.

 

Хэш-функции с ключом

 

Хэш-функцией с ключом называется односторонняя функция H(k,x) со следующими свойствами:

- аргумент x функции H(k,x) может быть строкой бит произвольной длины;

- значение функции должно быть строкой бит фиксированной длины;

- при любых данных k и x легко вычислить H(k,x);

- для любого x должно быть практически невозможно вычислить

H(k,x),не зная k;

- должно быть практически невозможно определить k, даже при большом числе известных пар {x, H(k,x)} или вычислить по этой информации H(k,x’) для x’ x.

Часто такие функции также называются кодами аутентифика

ции сообщений (англ. «Message Authentication Code»,сокр.MAC).В

отечественной литературе используется также термин имитозащитная вставка (или просто имитовставка).

Хэш-функцию с ключом можно построить на базе криптографической хэш-функции без ключа или алгоритма шифрования.

Пусть H(x) – хэш-функция без ключа. Можно внедрить ключ в процесс хэширования, и получить хэш-функцию с ключом H(k,x). Ниже представлены возможные варианты построения:

 

H(k,x) = H(k|x),

H(k,x) = H(x|k), (2.28) H(k,x) = H(k₁|x|k₂), где k=k₁|k₂.

Символ | в (2.28) обозначает конкатенацию, объединение строк аргументов.

Другой пример – построение хэш-функции с помощью шифра DES. Входной текст m разбивается на блоки m₁,,m_t по 64 бита, ко-торые преобразуются следующим образом (k – ключ шифрования):

c₀=0,

 

c_i=DES_k(m_i c_i-1), i=1,,t, H(k,m)= c_t