- •Глава 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.4. Недостатки алгоритма цифровой подписи rsa
-
Можно повторно использовать подписанный документ, так как копирование файлов в ЭВМ очень простая задача. Чтобы преодолеть этот недостаток документ должен содержать метку времени (порядковый номер), а проверяющий подпись должен создать базу данных, содержащую метки времени получаемых от отправителя документов. Тогда при повторном предъявлении документа легко обнаружить попытку обмана.
-
Отправитель сообщения может подписать сообщение, а затем отказаться от подписи, заявив, что его секретный ключ был скомпрометирован.
-
Стойкость протоколов подписи RSA основана на сложности факторизации большого натурального числа N. В 1978 году, в момент опубликования RSA, считалось, что достаточно взять . В настоящее время выбор уже не обеспечивает защиту от подделки. Таким образом, лицо, подписавшее документ в 1978 году, может сейчас отказаться от своей подписи под этим документом. Или злоумышленник может подделывать подписи под документами, датировав их 1978 годом. Такое свойство электронной цифровой подписи приводит к тому, что будущие историки не будут доверять электронным документам нашего времени.
-
При вычислении модуля N, ключей E и D для системы цифровой подписи RSA необходимо проверять большое количество дополнительных условий, что сделать практически трудно. Невыполнение любого из этих условий делает возможным фальсификацию цифровой подписи со стороны того, кто обнаружит такое невыполнение. При подписании важных документов нельзя допускать такую возможность даже теоретически.
-
Для обеспечения криптостойкости цифровой подписи RSA по отношению к попыткам фальсификации на уровне, например, национального стандарта США на шифрование информации (алгоритм DES), т.е. 1018, необходимо использовать при вычислениях N, D и E целые числа не менее 2512 (или около 10154) каждое, что требует больших вычислительных затрат, превышающих на 20-30% вычислительные затраты других алгоритмов цифровой подписи при сохранении того же уровня криптостойкости.
-
Цифровая подпись RSA уязвима к так называемой мультипликативной атаке. Иначе говоря, алгоритм цифровой подписи RSA позволяет злоумышленнику без знания секретного ключа D сформировать подписи под теми документами, у которых результат хэширования можно вычислить как произведение результатов хэширования уже подписанных документов.
Пример. Допустим, что злоумышленник может сконструировать три сообщения M1, M2 и M3, у которых хэш-значения
m1 = h(M1), m2 = h(M2), m3 = h(M3),
причем m3 = m1m2 (mod N).
Допустим также, что для двух сообщений M1 и M2 получены законные подписи
S1 = m1D (mod N) и S2 = m2D (mod N).
Тогда злоумышленник может легко вычислить подпись S3 для документа M3, даже не зная секретного ключа D:
S3 = S1S2 (mod N).
Действительно,
S1S2 (mod N) = m1Dm2D (mod N) = (m1m2)D (mod N) = m3D (mod N) = S3.
40.5. Алгоритм цифровой подписи Эль – Гамаля
Алгоритм цифровой подписи Эль – Гамаля основан на сложной вычислительной задаче дискретного логарифмирования. Для его описания напомним сначала необходимые понятия.
Вычисления в конечных полях. Поле F есть множество, на котором определены операции сложения и умножения, удовлетворяющие требованиям: ассоциативности, коммутативности, дистрибутивности, существования аддитивного 0 и мультипликативной 1, аддитивных обратных и мультипликативных обратных для всех элементов за исключением 0. Примерами простейших конечных полей являются кольца вычетов по простому модулю Z/p.
Конечное поле F(q) с конечным числом q элементов играет важную роль в криптографии. В общем случае число элементов конечного поля имеет вид
q = pn,
где p – некоторое простое число и n 1. Конечные поля называют полями Галуа и обозначают GF(pn) или GF(p) при n =1. Многие криптосистемы шифров с открытым ключом базируются на полях Галуа GF(p), где p – большое простое число.
Пример. Поле Галуа GF(5) имеет элементы 0, 1, 2, 3, 4 и описывается следующими таблицами сложения и умножения.
+ |
0 |
1 |
2 |
3 |
4 |
|
х |
1 |
2 |
3 |
4 |
0 |
0 |
1 |
2 |
3 |
4 |
|
1 |
1 |
2 |
3 |
4 |
1 |
1 |
2 |
3 |
4 |
0 |
|
2 |
2 |
4 |
1 |
3 |
2 |
2 |
3 |
4 |
0 |
1 |
|
3 |
3 |
1 |
4 |
2 |
3 |
3 |
4 |
0 |
1 |
2 |
|
4 |
4 |
3 |
2 |
1 |
4 |
4 |
0 |
1 |
2 |
3 |
|
|
|
|
|
|
Если p – простое число, то число a {1,…,p–1} является взаимно простым с p, и поэтому обратный элемент a–1 существует. Тем самым однозначно определяется операция деления.
Обозначим через GF*(p) множество всех ненулевых элементов поля GF(p). Некоторый элемент g из GF*(p) называют образующим или порождающим элементом GF*(p), если для всех a из GF*(p) найдется такое целое x, что gx = a modp. Всего имеется (p –1) образующих элементов g. Число x называют дискретным логарифмом элемента a по основанию g и модулю p. Вычисление дискретных логарифмов (когда заданы g, a и p) примерно такая же труднорешаемая задача, как и задача разложения целого числа на множители.