Применение NP-полных задач в ассиметрично-ключевой криптографии (стр. 3 из 6)
5. «Лазейка» в односторонней функции
Главная идея асимметрично-ключевой криптографии – понятие «лазейки» в односторонней функции.
Хотя понятие функции знакомо из математики, мы дадим неофициальное определение здесь. Функция – правило, по которому связывают (отображают) один элемент во множестве A, называемый доменом, и один элемент во множестве B, называемый диапазоном, как показано на рис.3.
Рис. 3. Функция отображения домена в диапазон
Обратимая функция– функция, которая связывает каждый элемент в диапазоне с точно одним элементом в домене.
Односторонняя функция– функция, которая обладает следующими двумя свойствами:
1. f вычисляется просто. Другими словами, при данном x может быть легко вычислен y = f (x).
2. f -1 вычисляется трудно. Другими словами, при данном y, вычислить x= f ~1 (y) неосуществимо.
«Лазейка» в односторонней функции – односторонняя функция с третьим свойством:
3. При данном y и ловушке (секретной) x может быть легко вычислен.
Пример 1
Когда n является большим,
– односторонняя функция. Обратите внимание, что в этой функции x – кортеж (p, q) двух простых чисел, а y в данном случае– это n. При заданных p и q всегда просто вычислить n. При данном n очень трудно вычислить p и q. Это – проблема разложения на множители. В этом случае для нахождения функции f -1 нет решения с полиномиальным временем.Пример 2
Когда n является большим, функция y = xk mod n – «лазейка» в односторонней функции. При заданных x, k и n просто вычислить y, используя алгоритм быстрого возведения в степень. При заданных y, k и n очень трудно вычислить y. Это – проблема дискретного логарифма. В этом случае нет решения с полиномиальным временем для функции f -1. Однако если мы знаем «лазейку» и k’ , такое, что
, мы можем использовать x = yk mod n, чтобы найти x. Это – известный алгоритм (RSA – Riverst-Shamir-Adelman), который будет рассмотрен позже.6. Криптографическая система RSA
Самый общий алгоритм открытого ключа доступа – криптографическая система RSА, названная по имени его изобретателей Ривеста, Шамира, Эделмана (Rivest, Shamir и Adelman).
RSА использует два типа ключей – e и d, где e – открытый, a d – секретный. Предположим, что P – исходный текст и C – зашифрованный текст. Алиса использует C = Pe mod n, чтобы создать зашифрованный текст C из исходного текста P; Боб использует P = Cd mod n, чтобы извлечь исходный текст (файл), переданный Алисой. Модулей n создается очень большое количество с помощью процесса генерации ключей, который мы обсудим позже.
Для шифрования и дешифрования применяют возведение в степень по модулю. При использовании быстрого алгоритма возведение в степень по модулю выполнимо в полиномиальное время. Однако нахождение модульного логарифма так же сложно, как и разложение числа по модулю. Для него нет алгоритма с полиномиальным временем. Это означает, что Алиса может зашифровать сообщение общедоступным ключом (e) в полиномиальное время. Боб также может расшифровать его в полиномиальное время (потому что он знает d). Но Ева не может расшифровать это сообщение, потому что она должна была бы вычислить корень e-той степени из C с использованием модульной арифметики. Рис. 4 показывает идею RSA.
Рис. 4 Сложность операций в RSA
Другими словами, Алиса использует одностороннюю функцию (возведение в степень по модулю) с лазейкой, известной только Бобу. Ева не знает лазейку, поэтому не может расшифровать сообщение. Если когда-нибудь найдут полиномиальный алгоритм для модуля вычисления корня e-той степени из n, то возведение в степень по модулю n не будет больше односторонней функцией.
Рис. 5 показывает общую идею процедуры, используемой в RSA.
RSA использует возведение в степень по модулю для шифрования/дешифрования. Для того чтобы атаковать закрытый текст, Ева должна вычислить
Рис. 5 Шифрование, дешифрование и генерация ключей в RSA
RSA использует две алгебраических структуры: кольцо и группу.
Кольца шифрования/дешифрования. Шифрование и дешифрование сделаны с использованием коммутативного кольца
с двумя арифметическими операциями: сложение и умножение. В RSA это кольцо общедоступно, потому что модуль n общедоступен. Любой может послать сообщение Бобу, используя это кольцо для шифрования.Группы генерирования ключей. RSA использует мультипликативную группу
для генерации ключей. Группа поддерживает только умножение и деление (мультипликативную инверсию), которые необходимы для того, чтобы создать открытые и секретные ключи. Эту группу надо скрыть, потому что ее модуль 
является секретным. Мы увидим, что если Ева найдет этот модуль, она сможет легко атаковать криптографическую систему.RSA использует две алгебраических структуры: открытое кольцо R = < Zn, +, × > и секретную группу G = < Z 
(n)*, × >.
Алгоритм создания открытого и секретного ключей.
• Выбираются два случайных простых числа p и q
• Вычисляется их произведение n=p*q, которое называется модулем.
• Вычисляется значение функции Эйлера от числа n:
φ(n)=(p-1)(q-1)
• Выбирается открытый ключ е с учетом условий:
1<e<φ(n), НОД(е,φ(n))=1
• Определяется секретный ключ d, удовлетворяющего условию:
e*d≡1 (modφ(n)), где d<n
• Пара P=(e,n) публикуется в качестве открытого ключа RSA
• Пара S=(d,n) играет роль секретного ключа RSA и держится в секрете
Боб использует шаги, показанные в данном алгоритме, чтобы создать свои открытый и секретный ключи. После генерации ключей Боб объявляет кортеж (e, n) как свой открытый ключ доступа: Боб сохраняет d как свой секретный ключ. Боб может отказаться от p, q и
; они не могут изменить его секретный ключ, не изменяя модуль. Для безопасности рекомендуется размер для каждого простого p или q – 512 бит (почти 154 десятичные цифры). Это определяет размер модуля, n 1024 бита (309 цифр).В RSA кортеж (e, n) – открытый ключ доступа; целое число d – секретный ключ.
Алгоритм шифрования сообщения P
· Разбиваем исходный текст на блоки P1, P2, …, Pm
· Шифруем текст сообщения в виде последовательности блоков
Cj= Pjеmod n( j =1,n)
Алгоритм расшифрования
Чтобы расшифровать эти данные, используя секретный ключ (d,n), необходимо выполнить следующие вычисления: Pj= Cjdmodn ( j =1,n) В результате будет получено множество чисел P(j), которые представляют собой исходный текст.
В RSA p и q должны быть по крайней мере 512 битов; n должны быть по крайней мере 1024 бит.
Пример 3
Боб выбирает 7 и 11 как p и q и вычисляет
. Значение 
или 60. Теперь он выбирает два ключа, e и d, из Z60*. Если он выбирает e = 13, то d = 37. Обратите внимание, что 
(они инверсны друг другу). Теперь предположим, что Алиса хочет передать исходный текст 5 Бобу. Она использует общедоступный ключ 13, чтобы зашифровать 5.Исходный текст:5
C = 513 = 26 mod 77
Зашифрованный текст: 26
Боб получает зашифрованный текст 26 и использует секретный ключ 37, чтобы расшифровать зашифрованный текст.
Зашифрованный текст: 26
P = от 2637 до 5 mod 77
Исходный текст 5
Переданный Алисой текст получен Бобом как исходный текст 5.
Пример 4
Теперь предположим, что другой человек, Джон, хочет передать сообщение Бобу. Джон может использовать открытый ключ доступа, объявленный Бобом (вероятно, на его сайте), – 13; исходный текст Джона – 63. Джон делает следующие вычисления:
Исходный текст: 63
C = 6313 = 28 mod 77
Зашифрованный текст: 28
Боб получает зашифрованный текст 28 и использует свой секретный ключ 37, чтобы расшифровать зашифрованный текст.
Зашифрованный текст: 28
P = 2837 = 63 mod 77
Исходный текст: 63
Пример 5
Дженнифер создает пару ключей для себя. Она выбирает p = 397 и q = 401. Она вычисляет
. Затем она вычисляет 
. Затем она выбирает e = 343 и d = 12007. Покажите, как Тэд может передать сообщение «No» Дженнифер, если он знает e и n.Решение
Предположим, что Тэд хочет передать сообщение «No» Дженнифер. Он изменяет каждый символ на число (от 00 до 25), сопоставляет каждой букве число, содержащее две цифры. Затем он связывает два кодированных символа и получает четырехзначное число. Исходный текст – 1314. Затем Тэд использует e и n, чтобы зашифровать сообщение. Зашифрованный текст 1314343 = 33677 mod 159197. Дженнифер получает сообщение 33677 и использует d ключ дешифрования, чтобы расшифровать это сообщение: 3367712007 = 1314 mod 159197. Затем Дженнифер расшифровывает 1314 как сообщение «No». Рисунок 14.7 показывает этот процесс.