Лекція 14. Rsa і цифровий підпис

RSA — криптографічна система з відкритим ключем.

RSA став першим алгоритмом такого типу, придатним і для шифрування і для цифрового підпису. Алгоритм використовується у великій кількості криптографічних застосунків.

Опис алгоритму

Безпека алгоритму RSA побудована на принципі складності факторизації. Алгоритм використовує два ключі — відкритий (public) і секретний (private), разом відкритий і відповідний йому секретний ключі утворюють пари ключів (keypair). Відкритий ключ не потрібно зберігати в таємниці, він використовується для шифрування даних. Якщо повідомлення було зашифровано відкритим ключем, то розшифрувати його можна тільки відповідним секретним ключем.

Генерація ключів

• Для того, щоб згенерувати пари ключів виконуються наступні дії:

• вибираються два великих простих числа и

• обчислюється їх добуток 

• обчислюється Функція Ейлера 

• вибирається ціле таке, щотавзаємно просте з

• за допомогою розширеного алгоритма Евкліда знаходиться число таке, що

Число називається модулем, а числаі— відкритою й секретною експонентами, відповідно. Пари чиселє відкритою частиною ключа, а— секретною. Числаіпісля генерації пари ключів можуть бути знищені, але в жодному разі не повинні бути розкриті.

Шифрування й розшифрування

Для того, щоб зашифрувати повідомлення обчислюється

.

Число і використовується в якості шифртексту.

Для розшифрування потрібно обчислити

.

Неважко переконатися, що при розшифруванні ми відновимо вихідне повідомлення:

З умови

виходить, що

 для деякого цілого , отже

Згідно теореми Ейлера:

,

тому

Цифровий підпис

RSA може використовуватися не тільки для шифрування, але й для цифрового підпису. Підпис повідомленняобчислюється з використанням секретного ключа за формулою:

Для перевірки правильності підпису потрібно переконатися, що виконується рівність