Перегляд вихідного коду сторінки Алгоритм RSA

'''RSA'''&nbsp;— [[шифрування|криптографічна]] система з відкритим ключем.

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

== Історія ==
Опис RSA було опубліковано у [[1977]] році [[Райвест, Рональд|Рональдом Райвестом]] (Ronald Linn Rivest), [[Шамір, Аді|Аді Шаміром]] (Adi Shamir) і [[Адлеман, Леонард|Леонардом Адлеманом]] (Leonard Adleman) з Масачусетського Технологічного Інституту (MIT).

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

В [[1983]] році був виданий [http://v3.espacenet.com/textdoc?DB=EPODOC&IDX=US4405829 патент 4405829] США, термін дії якого минув 21 вересня 2000 року.

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

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

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

Число <math>n\,</math> називається модулем, а числа <math>e\,</math> і <math>d\,</math>&nbsp;— відкритою й секретною експонентами, відповідно. Пари чисел <math>(n,\,e)</math> є відкритою частиною ключа, а <math>(n,\,d)</math>&nbsp;— секретною. Числа <math>p\,</math> і <math>q\,</math> після генерації пари ключів можуть бути знищені, але в жодному разі не повинні бути розкриті.

=== Шифрування й розшифрування ===
Для того, щоб зашифрувати повідомлення <math>m<n\,</math> обчислюється
: <math>c=m^e\bmod\,n \,</math>.
Число <math>c\,</math> і використовується в якості шифртексту.
Для розшифрування потрібно обчислити
: <math>m=c^d\bmod\,n \,</math>.
Неважко переконатися, що при розшифруванні ми відновимо вихідне повідомлення:

: <math>c^d\equiv (m^e)^d\equiv m^{ed}\pmod n\,</math>

З умови

: <math>ed\equiv 1\pmod{\varphi(n)}</math>

виходить, що

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

Згідно [[Теорема Ейлера|теореми Ейлера]]:
: <math>m^{\varphi(n)}\equiv 1\pmod n</math>,
тому
: <math>m^{k\varphi(n)+1}\equiv m \pmod n</math>
: <math>c^d\equiv m\pmod n\,</math>

=== Цифровий підпис ===
RSA може використовуватися не тільки для шифрування, але й для цифрового підпису. Підпис <math>s\,</math> повідомлення <math>m\,</math> обчислюється з використанням секретного ключа за формулою:
: <math>s=m^d\bmod\ n\,</math>
Для перевірки правильності підпису потрібно переконатися, що виконується рівність
: <math>m=s^e\bmod\ n\,</math>

== Деякі особливості алгоритму ==
=== Генерація простих чисел ===
Для знаходження двох великих [[просте число|простих чисел]] <math>p\,</math> і <math>q\,</math>, при генерації ключа, звичайно використовуються ймовірносні тести чисел на простоту, які дозволяють швидко виявити й відкинути [[складне число|складні числа]].

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

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

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

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

=== Вибір значення відкритого показника ===
RSA працює значно повільніше симетричних алгоритмів. Для підвищення швидкості шифрування відкритий показник <math>e\,</math> вибирається невеликим, звичайно 3, 17 або 65537. Ці числа у двійковому вигляді містять тільки по двох одиниці, що зменшує число необхідних операцій множення при піднесенні до степеня. Наприклад, для піднесення числа <math>m\,</math> до степеня 17 потрібно виконати тільки 5 операцій множення:
: <math>m^2= m\cdot m</math>
: <math>m^4=m^2\cdot m^2</math>
: <math>m^8=m^4\cdot m^4</math>
: <math>m^{16}=m^8\cdot m^8</math>
: <math>m^{17}=m^{16}\cdot m</math>

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

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

== Довжина ключа ==
Число ''n'' повинне мати розмір не менше 512 біт. У даний момент (2007 рік) система шифрування на основі RSA вважається надійною, починаючи з величини N в 1024 біта.

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

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