Раздел 5, вопрос 4. (49, Зюляркина) Системы шифрования с открытым ключом. Алгоритм RSA. (Лаптева)
Несимметричные системы: открытый и закрытый ключи.
( X , Y, fK1 , gK2 , K1, K2 )
Криптосистема называется несимметричной, если не существует эффективного алгоритма нахождения ключа K2 по известному ключу К1 (если нет алгоритма нахождения функции gK2 по известной функции fK1).
Общие идеи криптографических систем с открытым ключом:
Подробнее:
Существует трудноразрешимая задача З, для которой нет алгоритма подбора решений за приемлемое время. Из этой задачи З выделяется легкая подзадача ПЗ, которую можно решить за удовлетворительное время. Из ПЗ получаем новую задачу НЗ, похожую на З (маскировка). Как попасть из НЗ в ПЗ знает только человек с ключом.
(Источник: лекции Зюляркиной Н.Д.)
+
Не нужно предварительно передавать секретный ключ
Секретный ключ известен только одной стороне
Можно не менять ключи долгое время
-
Медленно работает
Увеличенный размер ключей
Примеры: RSA, система Дэффи-Хэллмана
(Источник: ответы Володи)
RSA (Rivest-Shamir-Adleman) — криптографический алгоритм с открытым ключом, основывающийся на вычислительной сложности задачи факторизации больших целых чисел.
2 случайных простых не равных числа p и q
n = p * q => разложение n на простые множители известно, но не разглашается
Функция Эйлера Ф(n) = Ф(pq)=(p-1)(q-1) // Ф — это «фи», символ φ
e принадлежит Z*Ф(n)
НОД(e, Ф(n)), взаимно простое с Ф(n) - открытая экспонента
К1=(n,e) - открытый ключ RSA
с = e-1 (mod Ф(n) ) -- секретная экспонента
К2=(n,c) - секретный ключ
Х,У (исходный текст и шифр-текст) — последовательности из Zn
Шифрование: x->y=xe (mod n) х, y из Zn
Дешифрование: y->yc=x (mod n)
//Шифрование и расшифровка возведением в степень по модулю n
Доказательство на основе малой теоремы Ферма (которая состоит в следующем: ap-1 при делении нацело на p даёт в остатке 1)
(Источник: лекции Зюляркиной Н.Д. + википедия)