- •Глава 36. Схемы шифрования rsa, Эль Гамаля, Полига-Хеллмана
- •Часть 5. Шифры с открытым ключом шифрования
- •Глава 36.
- •36.1. Основные понятия модулярной арифметики
- •Основные способы нахождения обратных величин a–1 1 (mod n).
- •36.2. Криптосистема шифрования данных rsa
- •X((Pх)) y (modQ).
- •36.3. Схема шифрования Эль Гамаля
- •36.4. Схема шифрования Полига-Хеллмана
- •Глава 37.
- •Глава 38.
- •38.1. Основные принципы построения протоколов идентификации и аутентификации
- •Доказательство проверяемого a:
- •38.3. Типовые схемы идентификации и аутентификации пользователя информационной системы
- •38.4. Особенности применения пароля для аутентификации пользователя
- •38.5. Взаимная проверка подлинности пользователей
- •38.6. Протоколы идентификации с нулевой передачей знаний
- •38.7. Упрощенный вариант схемы идентификации с нулевой передачей знаний. Протокол Фиата-Шамира
- •38.8. Параллельная схема идентификации с нулевой передачей знаний (с нулевым раскрытием)
- •38.9. Модифицированный протокол Фиата-Шамира
- •38.10. Схема идентификации Шнорра
- •38.11. Схема идентификации Гиллоу-Куискуотера
- •38.12. Способ проверки подлинности, где не требуется предъявлять секретный пароль
- •38.13. Проверка подлинности с помощью систем шифрования с открытым ключом
- •38.14. Биометрическая идентификация и аутентификация пользователя
- •Глава 39.
- •39.1. Основные понятия
- •39.4. Однонаправленные хэш-функции
- •Схемы безопасного хэширования, у которых длина хэш-значения равна длине блока
- •39.5. Отечественный стандарт хэш-функции
- •Глава 40.
- •40.1. Электронная цифровая подпись для аутентификации данных
- •40.2. Алгоритмы электронной цифровой подписи
- •40.3. Алгоритм цифровой подписи rsa
- •Обобщенная схема цифровой подписи rsa
- •40.4. Недостатки алгоритма цифровой подписи rsa
- •40.5. Алгоритм цифровой подписи Эль – Гамаля
- •40.6. Цифровая подпись Эль-Гамаля
- •40.7. Особенности протокола Эль-Гамаля
- •40.8. Алгоритм цифровой подписи dsa
- •40.10. Цифровые подписи с дополнительными функциональными свойствами
- •40.11. Алгоритм неоспоримой цифровой подписи д.Чома
- •40.12. Протокол подписи, позволяющий отправителю сообщения не предоставлять право получателю доказывать справедливость своей подписи
- •Глава 41.
- •41.1. Генерация ключей
- •41.2. Концепция иерархии ключей
- •41.3. Распределение ключей
- •41.4. Протокол аутентификации и распределения ключей для симметричных криптосистем
- •41.5. Протокол для асимметричных криптосистем с использованием сертификатов открытых ключей
- •41.6. Использование криптосистемы с открытым ключом для шифрования и передачи секретного ключа симметричной криптосистемы
- •Длины ключей для симметричных и асимметричных криптосистем при одинаковой их криптостойкости
- •41.7. Использование системы открытого распределения ключей Диффи-Хеллмана
- •41.8. Протокол skip управления криптоключами
- •Глава 42.
- •42.1. Основные понятия конечных полей
- •42.2. Криптографические протоколы. Протокол Диффи-Хеллмана
- •42.3. Протокол электронной цифровой подписи
40.8. Алгоритм цифровой подписи dsa
Американский стандарт цифровой подписи состоит из трех частей: алгоритма хэширования SHA (Secure Hash Algorithm), алгоритм порождения параметров p, q и алгоритм подписи DSA (Digital Signature Algorithm). Алгоритм цифровой подписи DSA (Digital Signature Algorithm) используется в стандарте цифровой подписи DSS (Digital Signature Standard).
Отправитель и получатель электронного документа используют при вычислении большие простые числа: g и p по L бит каждое (512 L 1024); q – простой делитель числа (p –1), число q имеет длину 160 бит (делитель). Числа g, p, q являются открытыми и могут быть общими для всех пользователей сети.
Отправитель выбирает случайное целое число x, 1< x< q. Число x является секретным ключом отправителя для формирования электронной цифровой подписи.
Затем отправитель вычисляет значение
y = gx mod p.
Число y является открытым ключом для проверки подписи отправителя. Число y передается всем получателям документов.
Этот алгоритм также предусматривает использование односторонней функции хэширования h(·). В стандарте DSS определен так называемый алгоритм безопасного хэширования SHA (Secure Hash Algorithm).
Для того чтобы подписать документ M, отправитель хэширует его в целое хэш-значение m:
m = H(M), 1< m < q,
затем генерирует случайное целое число k, 1< k< q, и вычисляет число r:
r = (gk mod p) mod q.
Затем отправитель вычисляет с помощью секретного ключа x целое число s:
s = mod q.
Пара чисел r и s образует цифровую подпись (r ,s)
под документом M.
Таким образом, подписанное сообщение представляет собой тройку чисел [M, r, s].
Получатель подписанного сообщения [M, r, s] проверяет выполнение условий
0 < r < q,
0 < s < q
и отвергает подпись, если хотя бы одно из этих условий не выполнено.
Затем получатель вычисляет значение
w = mod q,
и хэш-значение
m = H(M),
а затем числа
u1 = (m∙ w) mod q,
u2 = (r∙ w) mod q.
Далее получатель с помощью открытого ключа y вычисляет значение
v = (() mod p) mod q
и проверяет выполнение условия
v = r.
Если условие v = r выполняется, тогда подпись (r,s) под документом M признается получателем подлинной.
Доказано, что последнее равенство будет выполняться тогда, и только тогда, когда подпись (r,s) под документом M получена с помощью именно с того секретного ключа x, из которого был получен открытый ключ y. Таким образом, можно надежно удостовериться, что отправитель сообщения владеет именно данным секретным ключом x (не раскрывая при этом значения ключа x) и что данный документ M подписал именно отправитель
По сравнению с алгоритмом цифровой подписи Эль–Гамаля алгоритм DSA имеет следующие основные преимущества:
1. При любом допустимом уровне стойкости, т.е. при любой паре чисел g и p (от 512 до 1024 бит), числа q, x, r, s имеют длину по 160 бит, сокращая длину подписи до 320 бит.
2. Большинство операций с числами k, r, s, x при вычислении подписи производится по модулю числа q длиной 160 бит, что сокращает время вычисления подписи.
3. При проверке подписи большинство операций с числами u1, u2, v, w также производится по модулю числа q длиной 160 бит, что сокращает объем памяти и время вычисления.
Недостатком алгоритма DSA является то, что при подписывании и при проверке подписи приходится выполнять сложные операции деления по модулю q:
s = (mod q), w = (mod q),
что не позволяет получать максимальное быстродействие.
Следует отметить, что реальное исполнение алгоритма DSA может быть ускорено с помощью выполнения предварительных вычислений. Заметим, что значение r не зависит от сообщения M и его хэш-значения m. Можно заранее создать строку случайных значений k и затем для каждого из этих значений вычислить значения r. Можно также заранее вычислить обратные значения k–1 для каждого из значений k. Затем, при поступлении сообщения M, можно вычислить значение s для данных значений r и k–1. Эти предварительные вычисления значительно ускоряют работу алгоритма DSA.
Стойкость алгоритма подписи DSA определяется сложностью решения задачи дискретного логарифмирования в подгруппе порядка q. Для ее решения можно применить два подхода.
Во-первых, можно вычислить дискретные логарифмы y, g по основанию R, где , использовав какой-либо современный вариант индекс – метода (смотри раздел, посвященный дискретным логарифмам). Например, метод решета числового поля или линейное решето. Отсюда легко найти логарифм y по основанию q, то есть секретный ключ x.
Во-вторых, можно использовать -метод Полларда и его распараллеливание (см. тот же раздел) для прямого вычисления x. При выборе величины q надо учитывать оба подхода.
При анализе алгоритма подписи Эль–Гамаля мы видели, что централизованное порождение параметров может быть опасно. Это было учтено при разработке стандарта США. Помимо простых чисел p и q пользователю предоставляют значения S, C параметров алгоритма выработки этих p и q. Зная S, C, пользователь может проверить действительно ли числа p,q были получены с помощью этого алгоритма. Приведем теперь сам алгоритм.
Входные данные алгоритма. Число L, где и . Пусть , где . Выходные данные алгоритма. Простое число p длины L бит, простое число q длины 160 бит, двоичная последовательность S и число C, .
Шаг 1. Выбрать произвольную последовательность бит S, длина g которой не менее 160.
Шаг 2. Вычислить . Таким образом, U – вектор длины 160. Здесь SHA(S) есть результат применения алгоритма SHA.
Шаг 3. Образовать q, установив первый и 160-й бит U в 1. Таким образом, q – нечетное число длиной 160 бит.
Шаг 4. Проверить q на простоту.
Шаг 5. Если q составное, то перейти на шаг 1. Если q простое, то перейти на шаг 6.
Шаг 6. Положить C=0, N=2.
Шаг 7. Вычислить при всех k, .
Шаг 8. Пусть W целое число
длины не более L-1 бит. Положить . Таким образом, X – число, длина которого в точности равна L бит.
Шаг 9. Положить . Тогда .
Шаг 10. Если , то перейти к шагу 13.
Шаг 11. Проверить p на простоту.
Шаг 12. Если p простое, то перейти к шагу 15. В противном случае, перейти на шаг 13.
Шаг 13. Положить C:=C+1 и N:=N+n+1.
Шаг 14. Если C=4096, то перейти на шаг 1. В противном случае перейти к шагу 7.
Шаг 15. Сохранить числа p, q, C и последовательность S. Закончить алгоритм.
Заметим, что для проверки простоты чисел p, q рекомендуется использовать вероятностный тест, то есть тест типа Монте–Карло с вероятностью ошибки не более 2-80.
40.9. Отечественный стандарт цифровой подписи
Отечественный стандарт цифровой подписи обозначается как ГОСТ Р 34.10-94. Алгоритм цифровой подписи, определяемый этим стандартом, концептуально близок к алгоритму DSA. В нем используются следующие параметры:
p – большое простое число длиной от 509 до 512 бит либо от 1020 до 1024 бит;
q – простой сомножитель числа (p –1), имеющий длину 254 – 256 бит.
a – любое число, меньшее (p –1), причем такое, что aq mod p=1;
x – некоторое число, меньшее q;
y = aх mod p.
Кроме того, этот алгоритм использует однонаправленную хэш-функцию H(x). Стандарт ГОСТ Р 34.11-94 определяет хэш-функцию, основанную на использовании стандартного симметричного алгоритма ГОСТ 28147-89.
Первые три параметра p, q и a являются открытыми и могут быть общими для всех пользователей сети. Число x является секретным ключом. Число y является открытым ключом.
Чтобы подписать некоторое сообщение m, а затем проверить подпись, выполняются следующие шаги.
1. Пользователь A генерирует случайное число k, причем k < q.
2. Пользователь А вычисляет значения
r = (ak mod p) mod q,
s = (x∙ r + k (H(m))) mod q.
Если H(m) mod q=0, то значение H(m) mod q принимают равным единице. Если r=0, то выбирают другое значение k и начинают снова.
Цифровая подпись представляет собой два числа:
r mod 2256 и s mod 2256.
Пользователь А отправляет эти числа пользователю В.
3. Пользователь В проверяет полученную подпись,
вычисляя
v = H(m)q–2 mod q,
z1 = (s∙v) mod q,
z2 = ((q – r)∙v) mod q,
u = ( mod p) mod q.
Если u = r, то подпись считается верной.
Различие между этим алгоритмом и алгоритмом DSA заключается в том, что в DSA
s = (k–1 (x∙ r + (H(m)))) mod q,
что приводит к другому уравнению верификации.
Следует также отметить, что в отечественном стандарте ЭЦП параметр q имеет длину 256 бит. Западных криптографов вполне устраивает q длиной примерно 160 бит. Различие в значениях параметра q является отражением стремления разработчиков отечественного стандарта к получению более безопасной подписи. Этот стандарт вступил в действие с начала 1995 г.