Раздел 5, вопрос 4. (49, Зюляркина) Системы шифрования с открытым ключом. Алгоритм RSA. (Лаптева)

Несимметричные системы: открытый и закрытый ключи.

( X , Y, f_K1 , g_K2 , K1, K2 )

Криптосистема называется несимметричной, если не существует эффективного алгоритма нахождения ключа K2 по известному ключу К1 (если нет алгоритма нахождения функции g_K2 по известной функции f_K1).

Общие идеи криптографических систем с открытым ключом:

1. маскировка   выделенной простой задачи под задачу   без эффективного решения;
2. использование          односторонних функций-ловушек.

Подробнее:

Существует трудноразрешимая задача З, для которой нет алгоритма подбора решений за приемлемое время. Из этой задачи З выделяется легкая подзадача ПЗ, которую можно решить за удовлетворительное время. Из ПЗ получаем новую задачу НЗ, похожую на З (маскировка). Как попасть из НЗ в ПЗ знает только человек с ключом.

(Источник: лекции Зюляркиной Н.Д.)

+

Не нужно предварительно передавать секретный ключ

Секретный ключ известен только одной стороне

Можно не менять ключи долгое время

-

Медленно работает

Увеличенный размер ключей

Примеры: 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=x^e (mod n) х, y из Zn

Дешифрование: y->y^c=x (mod n)

//Шифрование и расшифровка возведением в степень по модулю n

Доказательство на основе малой теоремы Ферма (которая состоит в следующем: a^p-1 при делении нацело на p даёт в остатке 1)

(Источник: лекции Зюляркиной Н.Д. + википедия)