Сообщение, не относящиеся к теме

Історія

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

Британський математик Кліфорд Кокс (Clifford Cocks), що працював в центрі урядового зв'язку (GCHQ) Великобританії, описав аналогічну систему в 1973 році у внутрішніх документах центру, але ця робота не була розкрита до 1997 року, тож Райвест, Шамір і Адлеман розробили RSA незалежно від роботи Кокса.

В 1983 році був виданий патент 4405829 США, термін дії якого минув 21 вересня 2000 року.
Опис алгоритму

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

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

вибираються два великі прості числа p\, і q\, приблизно 512 біт завдовжки кожне
обчислюється їх добуток n=pq \,
обчислюється функція Ейлера \varphi(n)=(p-1)(q-1)
вибирається ціле e\, таке, що 1<e<\varphi(n) та e\, взаємно просте з \varphi(n)
за допомогою розширеного алгоритму Евкліда знаходиться число d\, таке, що ed\equiv 1\pmod{\varphi(n)}

Число n\, називається модулем, а числа e\, і d\, — відкритою й секретною експонентами (англ. encryption and decryption exponents), відповідно. Пари чисел (n,\,e) є відкритою частиною ключа, а (n,\,d) — секретною. Числа p\, і q\, після генерації пари ключів можуть бути знищені, але в жодному разі не повинні бути розкриті.
Шифрування й розшифрування

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

c=m^e\bmod\,n \,.

Число c\, і використовується в якості шифртексту. Для розшифрування потрібно обчислити

m=c^d\bmod\,n \,.

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

c^d\equiv (m^e)^d\equiv m^{ed}\pmod n\,

З умови

ed\equiv 1\pmod{\varphi(n)}

випливає, що

ed=k\varphi(n)+1 для деякого цілого k\,, отже
m^{ed}\equiv m^{k\varphi(n)+1}\pmod n

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

m^{\varphi(n)}\equiv 1\pmod n,

тому

m^{k\varphi(n)+1}\equiv m \pmod n
c^d\equiv m\pmod n\,

RSA припущення — RSA є односторонньою переставкою, тобто для будь-якого дієвого алгоритму A:

Pr[A(n,e,c)=c^{1/e}] нехтовно мала, що означає неможливість обернення RSA без секретної інформації — d.

Наведений вище варіант шифрування називається підручник RSA (англ. textbook RSA) і є цілком уразливим[1]. В жодному разі його не можна використовувати в криптосистемах.
Цифровий підпис

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

s=m^d\bmod\ n\,

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

m=s^e\bmod\ n\,

Деякі особливості алгоритму
Генерація простих чисел

Для знаходження двох великих простих чисел p\, і q\,, при генерації ключа, звичайно використовуються ймовірносні тести чисел на простоту, які дозволяють швидко виявити й відкинути складені числа.

Для генерації p\, і q\, необхідно використовувати криптографічно надійний генератор випадкових чисел. У порушника не має бути можливості одержати будь-яку інформацію про значення цих чисел.

p\, і q\, не повинні бути занадто близькими одне до одного, інакше можна буде знайти їх використовуючи метод факторизації Ферма. Крім того, необхідно вибирати «сильні» прості числа, щоб не можна було скористатися p-1 алгоритмом Поларда.
Доповнення повідомлень

При практичному використанні необхідно деяким чином доповнювати повідомлення. Відсутність доповнень може призвести до деяких проблем:

значення m=0\, і m=1\, дадуть при зашифруванні шифртексти 0 і 1 при будь-яких значеннях e\, і n\,.
при малому значенні відкритого показника (e=3\,, наприклад) можлива ситуація, коли виявиться, що m^e<n\,. Тоді c=m^e\bmod\ n=m^e\,, і зловмисник легко зможе відновити вихідне повідомлення обчисливши корінь ступеня e\, з c\,.
оскільки RSA є детермінованим алгоритмом, тобто не використовує випадкових значень у процесі роботи, то зловмисник може використати атаку з обраним відкритим текстом.

Для розв'язання цих проблем повідомлення доповнюються перед кожним зашифруванням деяким випадковим значенням. Доповнення виконується таким чином, щоб гарантувати, що m\neq0\,, m\neq1\, і m^e>n\,. Крім того, оскільки повідомлення доповнюється випадковими даними, то зашифровуючи той самий відкритий текст ми щораз будемо одержувати інше значення шифртексту, що робить атаку з обраним відкритим текстом неможливою.
Вибір значення відкритого показника

RSA працює значно повільніше симетричних алгоритмів. Для підвищення швидкості шифрування відкритий показник e\, вибирається невеликим, звичайно 3, 17 або 65537 (2 обрати не можна, бо e\, повинно бути взаємно простим із \varphi(n)=(p-1)(q-1)). Ці числа у двійковому вигляді містять тільки по дві одиниці, що зменшує число необхідних операцій множення при піднесенні до степеня. Наприклад, для піднесення числа m\, до степеня 17 потрібно виконати тільки 5 операцій множення:

m^2= m\cdot m
m^4=m^2\cdot m^2
m^8=m^4\cdot m^4
m^{16}=m^8\cdot m^8
m^{17}=m^{16}\cdot m

Вибір малого значення відкритого показника може призвести до розкриття повідомлення, якщо воно відправляється відразу декільком одержувачам, але ця проблема вирішується за рахунок доповнення повідомлень.
Вибір значення секретного показника

Значення секретного показника d\, повинне бути досить великим. У 1990 році Міхаель Вінер (Michael J. Wiener) показав, що якщо q<p<2q\, і d<n^{\frac14}/3, то є ефективний спосіб обчислити d\, по n\, і e\,. Однак, якщо значення e\, вибирається невеликим, те d\, виявляється досить великим і проблеми не виникає.
Довжина ключа

Число n повинне мати розмір не менше 512 біт. На 2007 рік система шифрування на основі RSA вважалась надійною, починаючи з величини N в 1024 біта.
Застосування RSA

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

Через низьку швидкість шифрування (близько 30 кбіт/сек при 512 бітному ключі на процесорі 2 ГГц), повідомлення звичайно шифрують за допомогою продуктивніших симетричних алгоритмів з випадковим ключем (сеансовий ключ), а за допомогою RSA шифрують лише цей ключ.