ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 08.11.2023
Просмотров: 291
Скачиваний: 4
ВНИМАНИЕ! Если данный файл нарушает Ваши авторские права, то обязательно сообщите нам.
2.4.4. Криптографическая система Эль–Гамаля
В 1984 году американским исследователем египетского проис- хождения Тахером Эль–Гамалем (Taher Elgamal) были опубликованы алгоритмы шифрования с открытым ключом и ЭЦП, получившие его имя. Криптографическая система Эль–Гамаля использует ту же мате-
77 матическую основу, что и рассмотренная ранее схема распределения ключей Диффи–Хеллмана: в качестве односторонней функции в этой криптосистеме используется возведение в степень по модулю боль- шого простого числа.
Алгоритм шифрования строится следующим образом.
Выбирается большое простое число р такое, что разложение числа (р–1) содержит большой простой множитель, а также число а такое,что1 < а < (p–1) и a — первообразный корень по модулю p.
Получатель сообщения генерирует ключевую пару: случайным образом выбирает секретный ключ x (0 < x < р) и вычисляет откры- тый ключ
p
a
y
x
mod
Для шифрования сообщения М (0 ≤ М < р), отправитель должен выполнить следующие действия.
1. Выбрать случайное число k такое, что 1 < k < p–1, НОД(k,р–
1)=1.
2. Вычислить вспомогательное значение
p
y
r
k
mod
3. Рассчитать значение криптограммы, состоящее из двух ча- стей:
p
a
c
k
mod
1
,
p
rM
с
mod
2
Надо отметить, что в [10] приводится вариация данного алго- ритма, где вторая часть криптограммы рассчитывается как
M
r
с
'
2
, где
— побитное сложение по модулю 2.
Рассмотрим процесс расшифровки. Для того чтобы по c
2
опре- делить M, получателю потребуется рассчитать значение r. С учетом того, что ему известен секретный ключ x и значение c
1
, это становится возможным:
p
r
a
c
x
k
x
mod
)
(
1
. Тогда
p
c
c
r
c
M
x
mod
)
(
1 1
2 1
2
Или для варианта со сложением по модулю 2:
p
c
c
M
x
mod
1
'
2
При использовании шифра Эль–Гамаля требуется, чтобы выби- раемое в процессе шифрования число k каждый раз менялось. В про- тивном случае, если сообщения М и М' предназначены одному полу- чателю, и нарушитель смог узнать одно из них, то ему не составит
78 труда рассчитать и второе. Пусть, например, нарушитель знает сооб- щение M, соответствующие ему криптограммы c
1
и c
2
, и криптограм- мы c
1
' и с
2
'. Из-за того, что k и ключи не менялись, будут совпадать r и
r', c
1
и с
1
'. М' нарушитель может рассчитать как:
p
r
c
M
mod
1 2
;
p
Mc
c
r
c
M
mod
'
'
'
1 2
2 1
2
.
(2.25).
Рассмотрим теперь предложенный Эль–Гамалем алгоритм
электронной цифровой подписи. Надо отметить, что он получил ши- рокое распространение и на его базе был разработан американский стандарт ЭЦП DSA (англ. «Digital Signature Algorithm»).
Как и при шифровании, стороны согласуют параметры a и p.
После этого отправитель выбирает секретный ключ x и рассчитывает открытый ключ
p
a
y
x
mod
Подписываемое сообщение M должно удовлетворять условию
0
M < p. Подписью абонента служит пара чисел r и s(0
r < p,
0
s < p),которые удовлетворяют соотношению:
p
r
y
a
s
r
M
mod
(2.26).
Получатель, знающий сообщение и открытый ключ, может про- верить выполнение этого равенства. Но только владелец секретного ключа x может правильно рассчитать значения r и s.Для этого он вы- полняет следующие действия.
1. Выбирает случайное число k: 1 < k < p–1, НОД(k,р–1)=1.
2. Вычисляет
p
a
r
k
mod
3. Вычисляет s из уравнения
)
1
mod(
p
ks
xr
M
. Это уравне- ние получено, основываясь на доказанном в теории числе утвержде- нии: если p — простое, a — целое, 1 < a
(в этом случае, a и p бу- дут и взаимно просты), то
p
a
a
y
x
mod
равносильно
)
1
mod(
p
y
x
для любых целых неотрицательных x, y. Таким обра- зом,
)
1
mod(
)
(
1
p
k
xr
M
s
. При выполнении условия НОД(k,р–
1)=1, s существует и единственно.
79
Отправитель передает сообщение с подписью (M,r,s) получате- лю, который, пользуясь соотношением (2.26), может проверить ЭЦП.
При применении алгоритма ЭЦП Эль–Гамаля, также как и в случае шифрования, недопустимо использовать одно и то же значение
k для подписи двух разных сообщений.
2.4.5. Совместное использование симметричных
и асимметричных шифров
Основным достоинством криптографических алгоритмов с от- крытым ключом является возможность решения таких задач, как рас- пределение ключа по небезопасному каналу, аутентификации сооб- щения и отправителя и т. д. В то же время асимметричные шифры ра- ботают существенно более медленно, чем симметричные. Это связано с необходимостью производить операции над сверхбольшими числа- ми. Поэтому симметричные и асимметричные алгоритмы часто ис- пользуют вместе — для распределения ключей и ЭЦП используют криптографию с открытым ключом, данные шифруют с помощью симметричных алгоритмов.
При анализе системы, в которой совместно используются не- сколько алгоритмов, принято оценивать сложность ее взлома по сложности взлома самого слабого звена. В литературе [9] приводится примерное соответствие длин ключей для алгоритма симметричного шифрования (атака производится путем перебора ключевого множе- ства) и алгоритма RSA, обеспечивающих сопоставимую стойкость.
Например, 64-битному ключу симметричного шифрования примерно соответствует 512-битный ключ RSA, а 128-битному — ключ RSA длиной более 2300 бит.
2.5. ХЭШ-ФУНКЦИИ
В рассмотренных в разделе 2.4 алгоритмах формирования ЭЦП длина подписи получается равной или даже большей, чем длина са- мого сообщения. Очевидно, что удостоверять подобным образом большой документ неудобно. Поэтому подписывается, как правило,
80 не само сообщение, а его «дайджест» — значение фиксированной длины, зависящее от подписываемого сообщения. Для формирования дайджеста используется хэш-функция (от англ. «hash function») — од- носторонняя функция, преобразующая строку произвольной длины в строку фиксированной длины. В криптографии используются хэш- функции 2 классов:
- хэш-функции без ключа;
- хэш-функции с ключом.
2.5.1. Хэш-функции без ключа
Хэш-функции без ключа делятся на слабые и сильные. Слабой
хэш-функцией называется односторонняя функция 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 и последнему условию в следующей формулировке:
4’) вычислительно невозможно любую пару значений x’
x, та- ких что H(x’)=H(x).
Любая сильная хэш-функция соответствует и требованиям для слабой, обратное в общем случае неверно. Для иллюстрации различия в сложности поиска коллизий слабой и сильной хэш-функции рас- смотрим атаку с использованием «парадокса дней рождения»
1
. За-
1
Парадокс дней рождения — известный пример из теории вероятности — утверждение, что если дана группа из 23 или более человек, то вероятность
81 фиксируем значение аргумента x и будем перебирать случайным об- разом x’
x в поисках ситуации, когда H(x’)=H(x). Если предполо- жить, что значения хэш-функции равномерно распределены, а число возможных значений H(x) равно N, то потребуется в среднем перебор
2
/
N
вариантов. Если же мы захотим найти какую-либо коллизию во- обще, то задача оказывается проще: с вероятностью 0,63 для опреде- ления нужной пары значений потребуется опробовать N вариантов.
Чтобы минимизировать стоимость создания криптографических хэш-функций, разработчики часто используют один из существую- щих алгоритмов шифрования. Пусть E(m,k) обозначает шифрование сообщения m на ключе k, а v
0
— стартовый вектор. Представим хэши- руемое сообщение M в виде последовательности блоков m
1
, …, m
t
и будем их использовать в качестве раундовых ключей. Тогда H(m) вы- числяется следующим образом:
h
0
= v
0
,
h
i
= E(h
i-1
,m
i
), i = 1
t ,
(2.27)
H(m) = h
t
.
Однако в варианте с использованием в качестве E(m,k) алгорит- ма DES, хэш-функция оказалась недостаточно стойкой из-за подвер- женности атаке, основанной на «парадоксе дней рождения». И было предложено улучшить эту схему, например, следующим образом:
h
0
= v
0
,
h
i
= E(h
i-1
,m
i
)
h
i-1
,
i=1
t,
(2.28)
H(m) = h
t
.
Существует и ряд специально разработанных алгоритмов хе- ширования, один из которых — SHA-1. того, что хотя бы у двух из них дни рождения (число и месяц) совпадут, превышает 1/2. Данное утверждение кажется противоречащим здравому смыслу, так как вероятность одному родиться в определенный день года довольно мала, а вероятность того, что двое родились в конкретный день
— еще меньше.
82
2.5.2. Алгоритм SHA-1
Алгоритм SHA (Secure Hash Algorithm) разработан в США как часть стандарта SHS (Secure Hash Standard), опубликованного в 1993 году. Но в нем были обнаружены уязвимости, которые привели к необходимости модифицировать алгоритм. Через два года была опуб- ликована новая версия — SHA-1, получившая на сегодняшний день широкое распространение.
Получая на входе сообщение произвольной длины менее 2 64
бит,
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
0
, b
0
, c
0
, d
0
, e
0
Преобразование производится над блоком сообщения размером 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.
83
Рис. 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- разрядных подблоков M
0
, …, M
15
, которые используются для форми- рования значений W
t
:
W
t
=M
t
для t = 0–15;
W
t
=(W
t-3
W
t-8
W
t-14
W
t-16
)<<<1 для t = 16–79.
Обозначение «<<< X» — циклический сдвиг влево на X разря- дов, «+» — сложение по модулю 2 32
После преобразования очередного 512-битного блока получен- ные значения a, b, c, d, e складываются со значениями A, B, C, D, E соответственно, и начинается обработка следующего блока (или по- лученное значение в виде сцепления a, b, c, d, e подается на выход, если обработанный блок был последним).
Таким образом, на выходе получаем 160-битный дайджест ис- ходного сообщения.
2.5.3. Хэш-функции с ключом
Хэш-функцией с ключом называется односторонняя функция
H(k,x) со следующими свойствами:
e
t
d
t
c
t
b
t
a
t
e
t+1
d
t+1
c t+1
b
t+1
a
t+1
f
t
<<<
30
<<<
5
W
t
K
t
+
+
+
+
84
- аргумент 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.29)
H(k,x) = H(k
1
|x|k
2
), где k = k
1
|k
2
Символ | в (2.28) обозначает конкатенацию, объединение строк аргументов.
Другой пример — построение хэш-функции с помощью шифра
DES. Входной текст m разбивается на блоки m
1
,
,m
t
по 64 бита, ко- торые преобразуются следующим образом (k — ключ шифрования):
c
0
=0,
c
i
=DES
k
(m
i
c
i-1
), i=1,
,t,
(2.30)
H(k,m)= c
t
.
85
2.6. ИНФРАСТРУКТУРА ОТКРЫТЫХ КЛЮЧЕЙ.
ЦИФРОВЫЕ СЕРТИФИКАТЫ
Использование методов асимметричной криптографии сделало возможным безопасный обмен криптографическими ключами между отправителем и получателем, которые никогда друг друга не встреча- ли и, возможно, находятся за многие километры друг от друга.
Но возникает другая проблема — как убедиться в том, что име- ющийся у Вас открытый ключ другого абонента на самом деле при- надлежит ему. Иными словами, возникает проблема аутентификации ключа. Без этого на криптографический протокол может быть осу- ществлена атака типа «человек посередине» (англ. «man in the middle»).
Идею данной атаки поясняет следующий пример. Абонент A
(Алиса) хочет послать абоненту B (Боб) зашифрованное сообщение и берет его отрытый ключ из общедоступного справочника. Но, на са- мом деле, ранее нарушитель E (Ева) подменил в справочнике откры- тый ключ Боба своим открытым ключом. Теперь Ева может расшиф- ровать те сообщения, которые Алиса формирует для Боба, ознако- миться с их содержимым, возможно, зашифровать их на настоящем ключе Боба и переслать ему (рис. 2.19).
Рис. 2.19. Атака типа «man in the middle»
Избежать подобной атаки можно, подтвердив подлинность ис- пользуемого ключа. Но Алиса и Боб лично никогда не встречались и передать, например, дискету с ключом из рук в руки не могут. Поэто-
Алиса посылает Бобу кон- фиденциальное письмо, за- шифровав его на подменен- ном Евой ключе
Алиса
Ева
Ознакомившись с содержимым письма, Ева пересылает письмо
Бобу, зашифровав его на уже подлинном ключе Боба
Боб
86 му решение задачи подтверждения подлинности берет на себя третья доверенная сторона — некий арбитр, которому доверяют оба абонен- та. Заверяется ключ с помощью цифрового сертификата.
На самом деле, подобный способ применяется и вне компью- терных систем. Когда для подтверждения подлинности человека ис- пользуется паспорт, то в роли третьей доверенной стороны выступает государство (от имени которого действовали в выдавшем паспорт от- деле милиции).
Но вернемся к цифровым сертификатам. Для подтверждения подлинности открытых ключей создается инфраструктура открытых ключей (англ. «Public Key Infrastructure», сокр. PKI). PKI представляет собой набор средств, мер и правил, предназначенных для управления ключами, политикой безопасности и обменом защищенными сообще- ниями. Структура PKI представлена на рис. 2.20.
Рис. 2.20. Структура PKI
Рис. 2.21. Иерархия центров сертификации и клиентов
CA_1 = ROOT
CA_2
CA_3
CA_4
Cl_1
Cl_2
Cl_3
Cl_4
Пользователь
Центр регистрации
Каталог сертификатов
Центр сертификации
Агенты PKI
В 1984 году американским исследователем египетского проис- хождения Тахером Эль–Гамалем (Taher Elgamal) были опубликованы алгоритмы шифрования с открытым ключом и ЭЦП, получившие его имя. Криптографическая система Эль–Гамаля использует ту же мате-
77 матическую основу, что и рассмотренная ранее схема распределения ключей Диффи–Хеллмана: в качестве односторонней функции в этой криптосистеме используется возведение в степень по модулю боль- шого простого числа.
Алгоритм шифрования строится следующим образом.
Выбирается большое простое число р такое, что разложение числа (р–1) содержит большой простой множитель, а также число а такое,что1 < а < (p–1) и a — первообразный корень по модулю p.
Получатель сообщения генерирует ключевую пару: случайным образом выбирает секретный ключ x (0 < x < р) и вычисляет откры- тый ключ
p
a
y
x
mod
Для шифрования сообщения М (0 ≤ М < р), отправитель должен выполнить следующие действия.
1. Выбрать случайное число k такое, что 1 < k < p–1, НОД(k,р–
1)=1.
2. Вычислить вспомогательное значение
p
y
r
k
mod
3. Рассчитать значение криптограммы, состоящее из двух ча- стей:
p
a
c
k
mod
1
,
p
rM
с
mod
2
Надо отметить, что в [10] приводится вариация данного алго- ритма, где вторая часть криптограммы рассчитывается как
M
r
с
'
2
, где
— побитное сложение по модулю 2.
Рассмотрим процесс расшифровки. Для того чтобы по c
2
опре- делить M, получателю потребуется рассчитать значение r. С учетом того, что ему известен секретный ключ x и значение c
1
, это становится возможным:
p
r
a
c
x
k
x
mod
)
(
1
. Тогда
p
c
c
r
c
M
x
mod
)
(
1 1
2 1
2
Или для варианта со сложением по модулю 2:
p
c
c
M
x
mod
1
'
2
При использовании шифра Эль–Гамаля требуется, чтобы выби- раемое в процессе шифрования число k каждый раз менялось. В про- тивном случае, если сообщения М и М' предназначены одному полу- чателю, и нарушитель смог узнать одно из них, то ему не составит
78 труда рассчитать и второе. Пусть, например, нарушитель знает сооб- щение M, соответствующие ему криптограммы c
1
и c
2
, и криптограм- мы c
1
' и с
2
'. Из-за того, что k и ключи не менялись, будут совпадать r и
r', c
1
и с
1
'. М' нарушитель может рассчитать как:
p
r
c
M
mod
1 2
;
p
Mc
c
r
c
M
mod
'
'
'
1 2
2 1
2
.
(2.25).
Рассмотрим теперь предложенный Эль–Гамалем алгоритм
электронной цифровой подписи. Надо отметить, что он получил ши- рокое распространение и на его базе был разработан американский стандарт ЭЦП DSA (англ. «Digital Signature Algorithm»).
Как и при шифровании, стороны согласуют параметры a и p.
После этого отправитель выбирает секретный ключ x и рассчитывает открытый ключ
p
a
y
x
mod
Подписываемое сообщение M должно удовлетворять условию
0
M < p. Подписью абонента служит пара чисел r и s(0
r < p,
0
s < p),которые удовлетворяют соотношению:
p
r
y
a
s
r
M
mod
(2.26).
Получатель, знающий сообщение и открытый ключ, может про- верить выполнение этого равенства. Но только владелец секретного ключа x может правильно рассчитать значения r и s.Для этого он вы- полняет следующие действия.
1. Выбирает случайное число k: 1 < k < p–1, НОД(k,р–1)=1.
2. Вычисляет
p
a
r
k
mod
3. Вычисляет s из уравнения
)
1
mod(
p
ks
xr
M
. Это уравне- ние получено, основываясь на доказанном в теории числе утвержде- нии: если p — простое, a — целое, 1 < a
(в этом случае, a и p бу- дут и взаимно просты), то
p
a
a
y
x
mod
равносильно
)
1
mod(
p
y
x
для любых целых неотрицательных x, y. Таким обра- зом,
)
1
mod(
)
(
1
p
k
xr
M
s
. При выполнении условия НОД(k,р–
1)=1, s существует и единственно.
79
Отправитель передает сообщение с подписью (M,r,s) получате- лю, который, пользуясь соотношением (2.26), может проверить ЭЦП.
При применении алгоритма ЭЦП Эль–Гамаля, также как и в случае шифрования, недопустимо использовать одно и то же значение
k для подписи двух разных сообщений.
2.4.5. Совместное использование симметричных
и асимметричных шифров
Основным достоинством криптографических алгоритмов с от- крытым ключом является возможность решения таких задач, как рас- пределение ключа по небезопасному каналу, аутентификации сооб- щения и отправителя и т. д. В то же время асимметричные шифры ра- ботают существенно более медленно, чем симметричные. Это связано с необходимостью производить операции над сверхбольшими числа- ми. Поэтому симметричные и асимметричные алгоритмы часто ис- пользуют вместе — для распределения ключей и ЭЦП используют криптографию с открытым ключом, данные шифруют с помощью симметричных алгоритмов.
При анализе системы, в которой совместно используются не- сколько алгоритмов, принято оценивать сложность ее взлома по сложности взлома самого слабого звена. В литературе [9] приводится примерное соответствие длин ключей для алгоритма симметричного шифрования (атака производится путем перебора ключевого множе- ства) и алгоритма RSA, обеспечивающих сопоставимую стойкость.
Например, 64-битному ключу симметричного шифрования примерно соответствует 512-битный ключ RSA, а 128-битному — ключ RSA длиной более 2300 бит.
2.5. ХЭШ-ФУНКЦИИ
В рассмотренных в разделе 2.4 алгоритмах формирования ЭЦП длина подписи получается равной или даже большей, чем длина са- мого сообщения. Очевидно, что удостоверять подобным образом большой документ неудобно. Поэтому подписывается, как правило,
80 не само сообщение, а его «дайджест» — значение фиксированной длины, зависящее от подписываемого сообщения. Для формирования дайджеста используется хэш-функция (от англ. «hash function») — од- носторонняя функция, преобразующая строку произвольной длины в строку фиксированной длины. В криптографии используются хэш- функции 2 классов:
- хэш-функции без ключа;
- хэш-функции с ключом.
2.5.1. Хэш-функции без ключа
Хэш-функции без ключа делятся на слабые и сильные. Слабой
хэш-функцией называется односторонняя функция 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 и последнему условию в следующей формулировке:
4’) вычислительно невозможно любую пару значений x’
x, та- ких что H(x’)=H(x).
Любая сильная хэш-функция соответствует и требованиям для слабой, обратное в общем случае неверно. Для иллюстрации различия в сложности поиска коллизий слабой и сильной хэш-функции рас- смотрим атаку с использованием «парадокса дней рождения»
1
. За-
1
Парадокс дней рождения — известный пример из теории вероятности — утверждение, что если дана группа из 23 или более человек, то вероятность
81 фиксируем значение аргумента x и будем перебирать случайным об- разом x’
x в поисках ситуации, когда H(x’)=H(x). Если предполо- жить, что значения хэш-функции равномерно распределены, а число возможных значений H(x) равно N, то потребуется в среднем перебор
2
/
N
вариантов. Если же мы захотим найти какую-либо коллизию во- обще, то задача оказывается проще: с вероятностью 0,63 для опреде- ления нужной пары значений потребуется опробовать N вариантов.
Чтобы минимизировать стоимость создания криптографических хэш-функций, разработчики часто используют один из существую- щих алгоритмов шифрования. Пусть E(m,k) обозначает шифрование сообщения m на ключе k, а v
0
— стартовый вектор. Представим хэши- руемое сообщение M в виде последовательности блоков m
1
, …, m
t
и будем их использовать в качестве раундовых ключей. Тогда H(m) вы- числяется следующим образом:
h
0
= v
0
,
h
i
= E(h
i-1
,m
i
), i = 1
t ,
(2.27)
H(m) = h
t
.
Однако в варианте с использованием в качестве E(m,k) алгорит- ма DES, хэш-функция оказалась недостаточно стойкой из-за подвер- женности атаке, основанной на «парадоксе дней рождения». И было предложено улучшить эту схему, например, следующим образом:
h
0
= v
0
,
h
i
= E(h
i-1
,m
i
)
h
i-1
,
i=1
t,
(2.28)
H(m) = h
t
.
Существует и ряд специально разработанных алгоритмов хе- ширования, один из которых — SHA-1. того, что хотя бы у двух из них дни рождения (число и месяц) совпадут, превышает 1/2. Данное утверждение кажется противоречащим здравому смыслу, так как вероятность одному родиться в определенный день года довольно мала, а вероятность того, что двое родились в конкретный день
— еще меньше.
82
2.5.2. Алгоритм SHA-1
Алгоритм SHA (Secure Hash Algorithm) разработан в США как часть стандарта SHS (Secure Hash Standard), опубликованного в 1993 году. Но в нем были обнаружены уязвимости, которые привели к необходимости модифицировать алгоритм. Через два года была опуб- ликована новая версия — SHA-1, получившая на сегодняшний день широкое распространение.
Получая на входе сообщение произвольной длины менее 2 64
бит,
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
0
, b
0
, c
0
, d
0
, e
0
Преобразование производится над блоком сообщения размером 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.
83
Рис. 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- разрядных подблоков M
0
, …, M
15
, которые используются для форми- рования значений W
t
:
W
t
=M
t
для t = 0–15;
W
t
=(W
t-3
W
t-8
W
t-14
W
t-16
)<<<1 для t = 16–79.
Обозначение «<<< X» — циклический сдвиг влево на X разря- дов, «+» — сложение по модулю 2 32
После преобразования очередного 512-битного блока получен- ные значения a, b, c, d, e складываются со значениями A, B, C, D, E соответственно, и начинается обработка следующего блока (или по- лученное значение в виде сцепления a, b, c, d, e подается на выход, если обработанный блок был последним).
Таким образом, на выходе получаем 160-битный дайджест ис- ходного сообщения.
2.5.3. Хэш-функции с ключом
Хэш-функцией с ключом называется односторонняя функция
H(k,x) со следующими свойствами:
e
t
d
t
c
t
b
t
a
t
e
t+1
d
t+1
c t+1
b
t+1
a
t+1
f
t
<<<
30
<<<
5
W
t
K
t
+
+
+
+
84
- аргумент 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.29)
H(k,x) = H(k
1
|x|k
2
), где k = k
1
|k
2
Символ | в (2.28) обозначает конкатенацию, объединение строк аргументов.
Другой пример — построение хэш-функции с помощью шифра
DES. Входной текст m разбивается на блоки m
1
,
,m
t
по 64 бита, ко- торые преобразуются следующим образом (k — ключ шифрования):
c
0
=0,
c
i
=DES
k
(m
i
c
i-1
), i=1,
,t,
(2.30)
H(k,m)= c
t
.
85
2.6. ИНФРАСТРУКТУРА ОТКРЫТЫХ КЛЮЧЕЙ.
ЦИФРОВЫЕ СЕРТИФИКАТЫ
Использование методов асимметричной криптографии сделало возможным безопасный обмен криптографическими ключами между отправителем и получателем, которые никогда друг друга не встреча- ли и, возможно, находятся за многие километры друг от друга.
Но возникает другая проблема — как убедиться в том, что име- ющийся у Вас открытый ключ другого абонента на самом деле при- надлежит ему. Иными словами, возникает проблема аутентификации ключа. Без этого на криптографический протокол может быть осу- ществлена атака типа «человек посередине» (англ. «man in the middle»).
Идею данной атаки поясняет следующий пример. Абонент A
(Алиса) хочет послать абоненту B (Боб) зашифрованное сообщение и берет его отрытый ключ из общедоступного справочника. Но, на са- мом деле, ранее нарушитель E (Ева) подменил в справочнике откры- тый ключ Боба своим открытым ключом. Теперь Ева может расшиф- ровать те сообщения, которые Алиса формирует для Боба, ознако- миться с их содержимым, возможно, зашифровать их на настоящем ключе Боба и переслать ему (рис. 2.19).
Рис. 2.19. Атака типа «man in the middle»
Избежать подобной атаки можно, подтвердив подлинность ис- пользуемого ключа. Но Алиса и Боб лично никогда не встречались и передать, например, дискету с ключом из рук в руки не могут. Поэто-
Алиса посылает Бобу кон- фиденциальное письмо, за- шифровав его на подменен- ном Евой ключе
Алиса
Ева
Ознакомившись с содержимым письма, Ева пересылает письмо
Бобу, зашифровав его на уже подлинном ключе Боба
Боб
86 му решение задачи подтверждения подлинности берет на себя третья доверенная сторона — некий арбитр, которому доверяют оба абонен- та. Заверяется ключ с помощью цифрового сертификата.
На самом деле, подобный способ применяется и вне компью- терных систем. Когда для подтверждения подлинности человека ис- пользуется паспорт, то в роли третьей доверенной стороны выступает государство (от имени которого действовали в выдавшем паспорт от- деле милиции).
Но вернемся к цифровым сертификатам. Для подтверждения подлинности открытых ключей создается инфраструктура открытых ключей (англ. «Public Key Infrastructure», сокр. PKI). PKI представляет собой набор средств, мер и правил, предназначенных для управления ключами, политикой безопасности и обменом защищенными сообще- ниями. Структура PKI представлена на рис. 2.20.
Рис. 2.20. Структура PKI
Рис. 2.21. Иерархия центров сертификации и клиентов
CA_1 = ROOT
CA_2
CA_3
CA_4
Cl_1
Cl_2
Cl_3
Cl_4
Пользователь
Центр регистрации
Каталог сертификатов
Центр сертификации
Агенты PKI