- •Глава 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. Протокол электронной цифровой подписи
Основные способы нахождения обратных величин a–1 1 (mod n).
1. Проверить поочередно значения 1, 2, ..., n–1, пока не будет найден a–1 1 (mod n), такой, что a∙a–1 (mod n) 1.
2. Если известна функция Эйлера (n), то можно вычислить a–1 (mod n) a(n)–1 (mod n), используя алгоритм быстрого возведения в степень.
3. Если функция Эйлера (n) не известна, можно использовать расширенный алгоритм Евклида.
Проиллюстрируем эти способы на числовых примерах.
1. Поочередная проверка значений 1, 2, ..., n – 1, пока не будет найден x = a–1 (mod n), такой что a∙x 1 (mod n).
Пусть n = 7, a = 5. Требуется найти x = a–1 (mod n).
a∙ x 1 (mod n) или 5∙x 1 (mod 7).
Получаем x = 5–1 (mod 7) = 3. Результаты проверки сведены в таблицу.
x |
5 x |
5 x (mod 7) |
1 2 3 4 5 6 |
5 10 15 20 25 30 |
5 3 1 6 4 2 |
2. Нахождение a–1 (mod n), если известна функция Эйлера (n).
Пусть n=7, a=5. Найти x=a–1 (mod n)=5–1 (mod 7). Модуль n=7 – простое число. Поэтому функция Эйлера (n)=(7)=n–1=6. Обратная величина от 5 по mod 7
a–1 (mod n) = a(n)–1 (mod n) =
= 56–1 mod 7 = 55 mod 7 = (52 mod 7)(53 mod 7) mod 7 =
= (25 mod 7)(125 mod 7) mod 7 = (4 6) mod 7 = 24 mod 7 = 3.
Итак, x = 5–1 (mod 7) = 3.
3. Нахождение обратной величины a–1 (mod n) с помощью расширенного алгоритма Евклида.
Расширенный алгоритм Евклида для нахождения обратных элементов (относительно умножения) кольца вычетов. Алгоритм Евклида обобщают и представляют в нескольких формах, которые имеют большое практическое значение.
Форма1. В этой форме во время вычисления НОД(a,b) попутно вычисляют такие целые числа u1 и u2, что
a∙u1 + b∙u2 = НОД (a,b).
Это обобщение (расширение) алгоритма Евклида удобно описать, используя векторные обозначения. При заданных неотрицательных целых числах a и b этот алгоритм определяет вектор (u1, u2, u3), такой, что
a∙u1 + b∙u2 = u3 = НОД (a, b).
В процессе вычисления используются вспомогательные векторы (v1, v2, v3), (t1, t2, t3). Действия с векторами производятся таким образом, что в течение всего процесса вычисления выполняются соотношения
a∙t1 + b∙t2 = t3, a∙u1 + b∙u2 = u3, a∙v1 + b∙v2 = v3.
Для вычисления обратной величины a–1 (mod n) используется частный режим работы расширенного алгоритма Евклида, при котором b = n, НОД (a,n) = 1, и этот алгоритм определяет вектор (u1, u2, u3), такой, что
u3 =1, a∙u1 + n∙u2 = НОД (a,n) =1,
(a∙u1 + n∙u2) mod n a∙u1 (mod n) 1,
a–1 (mod n) u1 (mod n).
Шаги алгоритма:
1. Начальная установка.
Установить (u1, u2, u3) : = (0, 1, n),
(v1, v2, v3) : = (1, 0, a).
2. u3 =1 ?. Если u3 =1, то алгоритм заканчивается.
3. Разделить, вычесть.
Установить q : = [u3/v3].
Затем установить
(t1, t2, t3) : = (u1, u2, u3) – (v1, v2, v3)∙q,
(u1, u2, u3) : = (v1, v2, v3),
(v1, v2, v3) : = (t1, t2, t3).
Возвратиться к шагу 2.
Пусть заданы модуль n = 23 и число a = 5. Найти обратное число a–1 (mod 23), т.е. x = 5–1 (mod 23).
Используя расширенный алгоритм Евклида, выполним вычисления, записывая результаты отдельных шагов в следующей таблице.
q |
u1 |
u2 |
u3 |
v1 |
v2 |
v3 |
– 4 1 1 – |
0 1 –4 5 –9 |
1 0 1 –1 2 |
n = 23 5 3 2 1 |
1 –4 5 –9 |
0 1 –1 2 |
a = 5 3 2 1 |
При u3 =1, u1 = –9, u2 = 2
(a∙u1 + n∙u2 ) mod n = (5∙(– 9) + 23∙2) mod 23 = 5∙(– 9) mod 23 1,
a–1 (mod n) = 5–1 (mod 23) = (– 9) mod 23 = (– 9 + 23) mod 23 = 14.
Итак, x = 5–1 (mod 23) 14 (mod 23) = 14.
Форма 2. Пусть НОД(а,n)=1, a>0, n>0. Рассматривается задача поиска целочисленного решения (x,y) уравнения a∙x-n∙y=1. Для решения задачи используют сначала алгоритм Евклида:
a = n ∙q0 + r1
n = r1 ∙ q1 + r2
r1 = r2 ∙ q2 + r3
r2 = r3 ∙ q3 + r4
…………………
rk–2 = rk–1 ∙ qk-1 + rk
rk–1 = rk ∙ qk +0
Находят последовательность q0, q1, q2,…,qk. Затем рекуррентно строят P0,Р1,Р2,…,Рk и Q0,Q1,Q2,…,Qk. Полагают
P-2=0, P-1=1 и Pj=qjPj-1+ Pj-2 для j0,
Q-2=1, Q-1=0 и Qj=qjQj-1+Qj-2 для j0.
Искомые значения x, y находятся по формулам
.
Обратный элемент а-1=(modn) для числа а есть решение уравнения