Початок асиметричним шифрам було покладено в 1976 році в роботі Уитфилда Діффі і Мартіна Хеллмана «Нові напрямки в сучасній криптографії». Вони запропонували систему обміну загальним секретним ключем (див. Діффі-Хеллмана криптосистема) на основі проблеми дискретного логарифма. Взагалі, в основу відомих асиметричних криптосистем кладеться одна зі складних математичних проблем, яка дозволяє будувати односторонні функції та функції-пастки. Наприклад, криптосистема Ривеста-Шаміра-Адельмана використовує проблему факторизации великих чисел, а криптосистеми Меркля-Хеллмана і Хору-Ривеста спираються на так звану задачу про укладання рюкзака [7].
Діффі і Хеллман досягли значних результатів, запропонувавши спосіб вирішення обох завдань, який радикально відрізняється від усіх попередніх підходів до шифрування.
Опис RSA було опубліковано в 1977 році Рональдом Райвест (Ronald Linn Rivest), Аді Шамір (Adi Shamir) і Леонардом Адлеманом (Leonard Adleman) з Массачусетського Технологічного Інституту (MIT).
Британський математик Кліффорд Кокс (Clifford Cocks), що працював в центрі урядового зв'язку (GCHQ) Великобританії, описав аналогічну систему в 1973 році у внутрішніх документах центру, але ця робота не була розкрита до 1977 року і Райвест, Шамір і Адлеман розробили RSA незалежно від роботи Кокса.
У 1983 році MIT був виданий патент № 4405829 США, термін дії якого закінчився 21 вересня 2000 року.
Безпека алгоритму RSA заснована на труднощі завдання розкладання на множники. Алгоритм використовує два ключі - відкритий (public) і секретний (private), разом відкритий і відповідний йому секретний ключі утворюють пару ключів (keypair). Відкритий ключ не потрібно зберігати в таємниці, він використовується для шифрування даних. Якщо повідомлення було зашифровано відкритим ключем, то розшифрувати його можна тільки відповідним секретним ключем.
Для того, щоб згенерувати пару ключів виконуються наступні дії:
· Вибираються два великих випадкових простих числа і
· Обчислюється їх добуток
· Обчислюється Функція Ейлера
· Вибирається ціле таке, що й взаємно просте з
За допомогою розширеного алгоритму Евкліда знаходиться число таке, що це означає, що при деякому цілому.
Число називається модулем, а числа і - відкритою і секретної експонентами, відповідно. Пара чисел є відкритою частиною ключа, а - секретною. Числа і після генерації пари ключів можуть бути знищені, але, ні в якому разі не повинні бути розкриті.
Для того, щоб зашифрувати повідомлення обчислюється.
Число використовується як шифртекста. Для розшифрування потрібно обчислити.
Неважко переконатися, що при розшифровуванні ми відновимо вихідне повідомлення:
(2.1)
З умови випливає, що для деякого цілого, отже, Згідно з теоремою Ейлера <# «26» src=«doc_zip29.jpg» />, Тому
На випадкові прості числа <# «9» height="12" src=«doc_zip32.jpg» /> І накладаються наступні додаткові обмеження:
· і не повинні бути занадто близькі один до одного, інакше можна буде їх знайти, використовуючи метод факторизації Ферма. Однак, якщо обидва простих числа і були згенеровані незалежно, то це обмеження з величезною ймовірністю автоматично виконується.
· Необхідно вибирати «сильні» прості числа...
