RSA

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

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

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

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

Припустимо, що Боб хотів би відправити повідомлення M Алісі. Спочатку він перетворює M в ціле число m так, щоб 0 ≤ m < n за допомогою узгодженого оборотного протоколу, відомого як схеми доповнення. Потім він обчислює зашифрований текст c, використовуючи відкритий ключ Аліси e, за допомогою рівняння:

${\displaystyle c=m^{e}{\bmod {\,}}n\,}$.

Це може бути зроблено досить швидко, навіть для 500-бітних чисел, з використанням модульного зведення в ступінь. Потім Боб передає c Алісі.

Для розшифрування повідомлення Боба m Алісі потрібно обчислити таку рівність:

${\displaystyle m=c^{d}{\bmod {\,}}n\,}$.

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

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

З умови

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

випливає, що

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

${\displaystyle m^{ed}\equiv m^{k\varphi (n)+1}{\pmod {n}}}$

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

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

тому

${\displaystyle m^{k\varphi (n)+1}\equiv m{\pmod {n}}}$

${\displaystyle c^{d}\equiv m{\pmod {n}}\,}$

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

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

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

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

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

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

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

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

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

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

${\displaystyle m^{2}=m\cdot m}$

${\displaystyle m^{4}=m^{2}\cdot m^{2}}$

${\displaystyle m^{8}=m^{4}\cdot m^{4}}$

${\displaystyle m^{16}=m^{8}\cdot m^{8}}$

${\displaystyle m^{17}=m^{16}\cdot m}$

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

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

В жовтні 2017 року міжнародна група дослідників (Словаччина, Чехія, Велика Британія, Італія) оприлюднили доповідь про виявлену ними вразливість в алгоритмі генератора псевдовипадкових чисел в криптографічній бібліотеці компанії Infeneon. Дана вразливість виникає при роботі бібліотеки на смарт-картах та в подібних вбудованих системах. Виявлені вади роблять практично досяжною факторизацію використаних при генерації пари ключів простих чисел. Зловмисник має можливість відновити секретний ключ за відкритим ключем жертви[2][3].

Станом на 2017 рік дослідники оцінюють витрати у найгіршому випадку для атаки методом Коперсміта проти ключа розміром 2048-біт 17 днів за $40 300 та $76 за 45 хвилин для ключа розміром 1024-біт (для орендованого кластера з тисячі вузлів на Amazon Web Service). В середньому витрати будуть вдвічі менші. При цьому, ключ розміром 4096 біт виявився слабшим за ключ розміром 3072 біт, для якого атака лишається практично важкою[2].

Дослідники також створили алгоритм для перевірки ключа на вразливість до виявленої ними атаки. Перевірка потребує близько 1 мілісекунди на сучасному процесорі[2].

Вразливі ключі були виявлені у низці продуктів та інтернет-проектах. В тому числі, було виявлено понад 750 000 вразливих до атаки смарт-карт системи електронного громадянства Естонії, ключах Yubikey 4, тощо[2]. 1 листопада 2017 року Естонія розпочала процес оновлення цифрових посвідчень з переходом на використання алгоритмів криптографії на еліптичних кривих[4].

Вражена бібліотека пройшла сертифікацію NIST FIPS 140-2 Level 2 та Common Criteria, а вразливість була присутня в ній з 2012 року[2].

Виявлена вада отримала назву ROCA та код CVE-2017-15361[5].