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

[[Файл:Shifrovannyi-tonnel-dlya-obsheniya-cherez-VK-(RSA--GreaseMonkey)-2-ukr.jpg|thumb|468x468px]]
'''RSA''' (абревіатура від прізвищ [[Рональд Рівест|Rivest]], [[Аді Шамір|Shamir]] та [[Леонард Адлеман|Adleman]])&nbsp;— криптографічний алгоритм з відкритим ключем, що базується на обчислювальній складності задачі [[факторизація|факторизації]] великих цілих чисел.

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

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

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

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

== Опис алгоритму ==
{{Wikibooks|Розв'язник вправ по дискретній математиці/Кодування/Алгоритм RSA}}
Алгоритм RSA складається з 4 етапів: генерації ключів, шифрування, розшифрування та розповсюдження ключів.

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

=== Розповсюдження ключів ===

Для того, щоб [[Аліса і Боб|Боб]] міг відправити свої секретні повідомлення, [[Аліса і Боб|Аліса]] передає свій відкритий ключ {{math|(''n'', ''e'')}} Бобу через надійний, але не обов'язково секретний маршрут. Секретний ключ {{math|''d''}} ніколи не розповсюджується.

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

# Вибираються два великі [[просте число|прості числа]] <math>p\,</math> і <math>q\,</math> приблизно 512 біт завдовжки кожне
# Обчислюється їх добуток <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;— відкритою й секретною експонентами ({{lang-en|'''e'''ncryption and '''d'''ecryption exponents}}), відповідно. Пари чисел <math>(n,\,e)</math> є відкритою частиною ключа, а <math>(n,\,d)</math>&nbsp;— секретною. Числа <math>p\,</math> і <math>q\,</math> після генерації пари ключів можуть бути знищені, але в жодному разі не повинні бути розкриті.

=== Шифрування ===
Припустимо, що Боб хотів би відправити повідомлення {{mvar|M}} Алісі.
Спочатку він перетворює {{mvar|M}} в ціле число {{mvar|m}} так, щоб {{math|0 ≤ ''m'' < ''n''}} за допомогою узгодженого оборотного протоколу, відомого як схеми доповнення. Потім він обчислює зашифрований текст {{mvar|c}}, використовуючи відкритий ключ Аліси {{mvar|e}}, за допомогою рівняння:
: <math>c=m^e\bmod\,n \,</math>.
Це може бути зроблено досить швидко, навіть для 500-бітних чисел, з використанням модульного зведення в ступінь. Потім Боб передає {{mvar|c}} Алісі.

=== Розшифрування ===
Для розшифрування повідомлення Боба {{mvar|m}} Алісі потрібно обчислити таку рівність:
: <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 припущення'''&nbsp;— RSA є [[Одностороння функція з секретом|односторонньою перестановкою]], тобто для будь-якого дієвого алгоритму A [[ймовірність]]
: <math>Pr[A(n,e,c)=c^{1/e}]</math> дуже мала, що означає неможливість обернення RSA без секретної інформації&nbsp;— <math>d</math>.

Наведений вище варіант шифрування називається ''RSA з підручника'' ({{lang-en|textbook RSA}})<ref>[http://crypto.stanford.edu/~dabo/courses/cs255_winter00/RSA.pdf The RSA one way permutation Textbook RSA is insecure] на сайті [[Стенфордський університет|Стенфордського університету]] {{ref-en}}</ref> і є цілком уразливим. В жодному разі його не можна використовувати в криптосистемах.

=== Приклад ===
{| class="wikitable" style="width: 100%"
!Етап
!Опис операції
!Результат операції
|-
!rowspan="7"| Генерація [[Ключ (криптографія)|ключів]]
|Обрати два простих різних числа
|
: <math>p=3557</math>,
: <math>q=2579</math>
|-
|Обчислити добуток
|
: <math> n = p \cdot q = 3557 \cdot 2579 = 9173503</math>
|-
|Обчислити функцію Ейлера
|
: <math>\varphi(n) = (p-1) (q-1) = 9167368</math>
|-
|Обрати відкриту експоненту
|
: <math> e = 3</math>
|-
|Обчислити секретну експоненту
|
: <math> d = e^{-1} \mod \varphi(n)</math>
: <math> d = 6111579</math>
|-
|Опублікувати ''відкритий ключ''
|
: <math>\{e, n\} = \{3,9173503 \}</math>
|-
|Зберегти ''секретний ключ''
|
: <math>\{d, n\} = \{6111579, 9173503 \}</math>
|-
!rowspan="2"|Шифрування
|Обрати текст для шифрування
|
: <math>m = 111111</math>
|-
|Обчислити шифротекст
|
: <math>\begin{align}
c &= E(m) \\
 &= m^e \mod n \\
 &= 111111^3   \mod 9173503 \\
 &= 4051753
\end{align}</math>
|-
! Розшифрування
| Обчислити вихідне повідомлення
|
: <math>\begin{align}
m &= D(c) = \\
  &= c^d \mod n \\
  &= 4051753^{6111579} \mod 9173503 \\
  &= 111111
\end{align}</math>
|}

== Цифровий підпис ==
{{Seealso|електронний цифровий підпис}}

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

{{дослівний переклад|url=https://studfiles.net/preview/5163175/page:3}}

== Швидкість роботи алгоритму RSA ==

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

У практичних додатках для відкритого ключа зазвичай обирається відносно невеликий показник, а часто групи користувачів використовують один і той же відкритий показник, але кожен з різним модулем. Якщо відкритий показник незмінний, вводяться деякі обмеження на головні співмножники (фактори) модуля. При цьому шифрування даних йде швидше, ніж розшифровка, а перевірка підпису&nbsp;— швидше, ніж підписання.

Якщо k&nbsp;— кількість бітів у модулі, то зазвичай в алгоритмах, що використовуються для RSA, кількість кроків, необхідна для виконання операції з відкритим ключем, пропорційна другій степені k, кількість кроків для операцій секретного ключа&nbsp;— третій степені k, кількість кроків для операції створення ключів&nbsp;— четвертій степені k.

Методи «швидкого множення»&nbsp;— наприклад, методи основані на швидкому перетворенні Фур'є&nbsp;— виконуються меншою кількістю кроків. Проте вони не набули широкого поширення через складність програмного забезпечення, а також тому, що з типовими розмірами ключів вони фактично працюють повільніше. Однак продуктивність та ефективність програм і обладнання, які реалізовують алгоритм RSA, швидко збільшується.

Алгоритм RSA набагато повільніший, ніж DES та інші алгоритми блокового шифрування. Програмна реалізація DES працює швидше принаймні в 100 разів і від 1,000 до 10,000&nbsp;— в апаратній реалізації (в залежності від конкретного пристрою). Завдяки проведенню розробок, швидкість алгоритму RSA, ймовірно, прискориться, але одночасно прискориться і робота алгоритмів блокового шифрування.

== Деякі особливості алгоритму ==

=== Генерація простих чисел ===
Для знаходження двох великих [[просте число|простих чисел]] <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 (2 обрати не можна, бо <math>e\,</math> повинно бути взаємно простим із <math>\varphi(n)=(p-1)(q-1)</math>). Ці числа у двійковому вигляді містять тільки по дві одиниці, що зменшує число необхідних операцій множення при піднесенні до степеня. Наприклад, для піднесення числа <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 використовують для захисту програмного забезпечення та у схемах [[Електронний цифровий підпис|цифрового підпису]]. Зокрема, її використовують у відкритій системі шифрування [[PGP]]{{fact}}.

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

На практиці криптосистема RSA часто використовується разом з криптографічною системою секретного ключа типу [[Data Encryption Standard|DES]] для шифрування повідомлення ключем RSA за допомогою цифрового конверта{{fact}}:
: Припустимо, що Аліса посилає зашифроване повідомлення Бобу. Спочатку вона шифрує повідомлення за алгоритмом DES, скориставшись випадково обраним ключем DES і потім шифрує ключ DES відкритими ({{lang-en|public}}) ключем RSA Боба. Повідомлення зашифроване ключем DES і ключ DES зашифрований у свою чергу ключем RSA разом формують цифровий конверт RSA і надсилаються Бобу. Отримавши цифровий конверт, Боб розшифровує ключ [[Data Encryption Standard|DES]] за допомогою свого секретного ({{lang-en|private}}) ключа RSA, а потім використовує ключ [[Data Encryption Standard|DES]], щоб розшифрувати саме повідомлення{{fact}}.

Криптосистема RSA використана у різних продуктах, на різних платформах і у багатьох галузях. Криптосистема RSA вбудована в комерційні продукти, число яких постійно зростає. Також її використовують операційні системи [[Microsoft]], [[Apple Inc.|Apple]], Sun і Novell. В апаратному виконанні RSA алгоритм застосований в захищених телефонах, на мережних платах [[Ethernet]], на смарт-картах, широко використовується в криптографічному обладнанні. Крім того, алгоритм входить до складу всіх основних протоколів для захищених комунікацій Internet, в тому числі [[S/MIME]], [[SSL]], [[S/WAN]], також використаний в багатьох установах, наприклад, в урядових службах, у більшості корпорацій, в державних лабораторіях і університетах. На осінь 2000 року технології з застосуванням алгоритму RSA були ліцензовані понад 700 компаніями{{fact}}.

=== Проблеми реалізації ===

==== ROCA ====
{{Main|ROCA}}
В жовтні 2017 року міжнародна група дослідників ([[Словаччина]], [[Чехія]], [[Велика Британія]], [[Італія]]) оприлюднили доповідь про виявлену ними вразливість в алгоритмі [[Генератор псевдовипадкових чисел|генератора псевдовипадкових чисел]] в криптографічній бібліотеці компанії Infeneon. Дана вразливість виникає при роботі бібліотеки на смарт-картах та в подібних вбудованих системах. Виявлені вади роблять практично досяжною [[Факторизація цілих чисел|факторизацію]] використаних при генерації пари ключів [[Просте число|простих чисел]]. Зловмисник має можливість відновити секретний ключ за відкритим ключем жертви<ref name="at.16.10.2017"/><ref name="2017-ccs-nemec">{{cite journal
 | author        = Matus Nemec, Marek Sys, Petr Svenda, Dusan Klinec, Vashek Matyas
 | title         = The Return of Coppersmith's Attack: Practical Factorization of Widely Used RSA Moduli
 | journal       = 24th ACM Conference on Computer and Communications Security (CCS'2017)
 | year          = 2017
 | pages         = 1631-1648
 | isbn          = 978-1-4503-4946-8
 | publisher     = ACM
 | doi           = 10.1145/3133956.3133969
}}</ref>.

Станом на 2017 рік дослідники оцінюють витрати у найгіршому випадку для атаки [[метод Коперсміта|методом Коперсміта]] проти ключа розміром 2048-біт 17 днів за ${{formatnum:40300}} та $76 за 45 хвилин для ключа розміром 1024-біт (для орендованого кластера з тисячі вузлів на [[Amazon Web Service]]). В середньому витрати будуть вдвічі менші. При цьому, ключ розміром 4096 біт виявився слабшим за ключ розміром 3072 біт, для якого атака лишається практично важкою<ref name="at.16.10.2017"/>.

Дослідники також створили алгоритм для перевірки ключа на вразливість до виявленої ними атаки. Перевірка потребує близько 1 мілісекунди на сучасному процесорі<ref name="at.16.10.2017"/>.

Вразливі ключі були виявлені у низці продуктів та інтернет-проектах. В тому числі, було виявлено понад {{formatnum:750000}} вразливих до атаки смарт-карт системи [[електронне громадянство Естонії|електронного громадянства Естонії]], ключах Yubikey 4, тощо<ref name="at.16.10.2017">{{cite web | url = https://arstechnica.com/information-technology/2017/10/crypto-failure-cripples-millions-of-high-security-keys-750k-estonian-ids/ | title = Millions of high-security crypto keys crippled by newly discovered flaw | author = Dan Goodin | date = Oct 16 2017 | publisher = Ars Technica }}</ref>. 1 листопада 2017 року Естонія розпочала процес оновлення цифрових посвідчень з переходом на використання алгоритмів [[Еліптична криптографія|криптографії на еліптичних кривих]]<ref>{{cite web | url = https://medium.com/e-residency-blog/estonia-is-enhancing-the-security-of-its-digital-identities-361b9a3c9c52 | title = Estonia is enhancing the security of its digital identities | author = Kaspar Korjus | date = 30 жовтня 2017 }}</ref>.

Вражена бібліотека пройшла сертифікацію [[Національний інститут стандартів і технології|NIST]] [[Федеральні стандарти обробки інформації|FIPS]] 140-2 Level 2 та [[Common Criteria]], а вразливість була присутня в ній з 2012 року<ref name="at.16.10.2017"/>.

Виявлена вада отримала назву ROCA та код CVE-2017-15361<ref>{{cite web | url = https://crocs.fi.muni.cz/public/papers/rsa_ccs17 | title = ROCA: Vulnerable RSA generation (CVE-2017-15361) | publisher = CRoCS Wiki | accessdate = 19 жовтня 2017 }}</ref>.

== Див. також ==
* [[Одностороння функція з секретом]]
* [[Асиметричні алгоритми шифрування]]
* [[Обмін ключами]]
* [[Протокол Діффі-Геллмана]]
* [[Теорія складності обчислень]]

== Примітки ==
{{reflist}}

== Література ==

* {{книга
|автор        = Menezes A. J., van Oorschot P. C., Vanstone S. A.
|назва        = Handbook of Applied Cryptography
|рік          = 1996
|видавництво  = CRC Press
|allpages     = 794
}} ([http://labit501.upct.es/~fburrull/docencia/SeguridadEnRedes/teoria/bibliography/HandbookOfAppliedCryptography_AMenezes.pdf pdf])
* {{книга
|автор        = Брассар Ж.
|назва        = Современная криптология
|оригінал     = Modern Cryptology: A Tutorial
|рік          = 1999
|місто        = {{Comment|М.|Москва}}
|видавництво  = Полимед
|сторінок     = 176
}}
* {{книга
|автор        = Земор Ж.
|назва        = Курс криптографии
|оригінал     = Cours de cryptographie
|рік          = 2006
|місто        = Ижевск
|видавництво  = РХД 
|сторінок     = 256
}}
* {{книга
|автор        = Коутинхо С.
|назва        = Введение в теорию чисел. Алгоритм RSA
|оригінал     = The Mathematics of Ciphers: Number Theory and RSA Cryptography
|рік          = 2001
|місто        = {{Comment|М.|Москва}}
|видавництво  = Постмаркет
|сторінок     = 328
}}
* {{книга
|автор        = ван Тилборг Х. К. А.
|назва        = Основы криптологии
|оригінал     = Fundamentals of Cryptology
|рік          = 2006
|місто        = {{Comment|М.|Москва}}
|видавництво  = Мир
|сторінок     = 472
}}
* {{книга
|автор        = Ян С.
|назва        = Криптоанализ RSA
|оригінал     = Cryptanalytic Attacks on RSA
|рік          = 2011
|місто        = Ижевск
|видавництво  = РХД
|сторінок     = 312
}}
* {{книга
|автор        = Ященко В. В.
|назва        = Введение в криптографию
|рік          = 2012
|місто        = {{Comment|М.|Москва}}
|видавництво  = МЦНМО
|сторінок     = 348
}} ([http://cryptography.ru/wp-content/uploads/2013/09/intro_to_crypto.pdf pdf])


{{Crypto-stub}}
{{refimprove|date=січень 2017}}
{{Крипто навігація}}
{{ВП-портали|Програмування|Інформаційні технології}}

[[Категорія:Асиметричні алгоритми шифрування]]