Алгоритм RSA

Опис RSA було опубліковано у 1977 році Рональдом Райвестом, Аді Шаміром і Леонардом Адлеманом з Масачусетського Технологічного Інституту (MIT).
Безпека алгоритму RSA побудована на принципі складності факторизації цілих чисел.

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

Криптостійкість алгоритму RSA ґрунтується на складності розкладання на множники великих чисел, а саме — на винятковій складності завдання визначити секретний ключ на підставі відкритого, так як для цього буде потрібно вирішити задачу про існування дільників цілого числа. Найбільш криптостійкі системи використовують 1024-бітові і великі числа.

Алгоритм складається з наступних кроків:

Крок 1.

Я підготовлюю публічний і приватний ключі.

Для цього обираю p і q. Нехай p=3 і q=11.

Для обчислення n множу p і q. Тому n=33.

Потім обчислюю φ за функцією Ейлера. (p-1) × (q-1)=2*10=20. Тому φ=20.

Далі з вибираю експонетну. Нехай е=3.

Відкритими ключами є {е, n} = {3, 33}. Відкритий ключ я відправляю партнерові.

Потім я маю отримати закритий ключ.  

Для цього знаходжу d з рівності e*d mod φ=1. Підставляю 3*d mod20=1. Тобто 3*d/20=… (остача 1).  Тут d=7.

Пара {d, n} = {7, 33} – закритий ключ. Його потрібно тримати в секреті. Тільки я зможу розшифрувати те, що було зашифровано відкритим ключем.

Крок 2.

Тепер Таня-партнер знає мій відкритий ключ {e, n} = {3, 33} і шифрує повідомлення. Нариклад, повідомлення Р, при Р<n. Нехай P=25.

При цьому, Таня здійснює шифрування за формулою:

Е= Р^еmod n

Е=25³mod33=15625mod33 і це = остачі від ділення 15625 на 33 = 16. Тобто Е=16 Таня відправляє мені.

Крок 3.

Я отримала дані, відправлені партером ( E = 16 ) і маю закритий ключ {d, n} = {7, 33}  і починаю розшифровку за формулою:

Р1=Е^d mod n=16⁷ mod33= 268435456 mod33 і це = остачі від ділення 268435456 на 33. Тобто Р1=25

Порівняння алгоритмів RSA та Деффі – Хеллмана

RSA — криптографічна система з відкритим ключем. RSA став першим алгоритмом такого типу, придатним і для шифрування і для цифрового підпису.  Безпека алгоритму RSA заснована на труднощі вирішення задачі розкладання чисел на прості множники. Основними перевагами RSA є:

1) алгоритмRSA є асиметричним, тобто він полягає в поширенні відкритих ключів у мережі. Це дозволяє кільком користувачам обмінюватися інформацією, по незахищеним каналів зв’язку;

2) користувач сам може змінювати як числа, і відкритий і закритий ключ на власний розсуд, потім він має поширити відкритий ключ у мережі. Це дає можливість збільшити криптостійкість.

Основні недоліки:

невисока швидкість роботи. АлгоритмRSA працює повільніше симетричного алгоритмуDES.

Алгоритм Діффі-Хеллмана (англ. Diffie-Hellman, DH) — алгоритм, що дозволяє двом сторонам отримати загальний секретний ключ, використовуючи незахищений від прослуховування, але захищений від підміни, канал зв’язку. Цей ключ може бути використаний для шифрування подальшого обміну за допомогою алгоритму симетричного шифрування.

Алгоритм Деффі-Хеллмана генерує секретний ключ для симетричного шифрування (“секретний ключ”).

Алгоритм RSA генерує пару секретний/відкритий ключ для асиметричного шифрування (“відкритий ключ”).