www.wikidata.uk-ua.nina.az

RSA абревіатура від прізвищ Rivest Shamir та Adleman криптографічний алгоритм з відкритим ключем що базується на обчислю

RSA

RSA (абревіатура від прізвищ Rivest, Shamir та Adleman) — криптографічний алгоритм з відкритим ключем, що базується на обчислювальній складності задачі факторизації великих цілих чисел.

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

Історія Редагувати

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

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

В 1983 році був виданий патент 4405829 [ 16 жовтня 2007 у Wayback Machine.] США, термін дії якого минув 21 вересня 2000 року.

Опис алгоритму Редагувати

Вікіпідручник має книгу на тему
Розв'язник вправ по дискретній математиці/Кодування/Алгоритм RSA

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

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

Розповсюдження ключів Редагувати

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

Генерація ключів Редагувати

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

  1. Вибираються два великі прості числа і приблизно 512 біт завдовжки кожне
  2. Обчислюється їх добуток
  3. Обчислюється функція Ейлера
  4. Вибирається ціле число таке, що та взаємно просте з
  5. За допомогою розширеного алгоритму Евкліда знаходиться число таке, що

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

Шифрування Редагувати

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

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

Розшифрування Редагувати

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

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

З умови

випливає, що

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

тому

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

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

Приклад Редагувати

Етап Опис операції Результат операції
Генерація ключів Обрати два простих різних числа
Обчислити добуток
Обчислити функцію Ейлера
Обрати відкриту експоненту
Обчислити секретну експоненту
Опублікувати відкритий ключ
Зберегти секретний ключ
Шифрування Обрати текст для шифрування
Обчислити шифротекст
Розшифрування Обчислити вихідне повідомлення

Цифровий підпис Редагувати

Див. також: Електронний цифровий підпис

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

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

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

Генерація простих чисел Редагувати

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

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

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

Доповнення повідомлень Редагувати

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

  • значення і дадуть при шифруванні шифротексти 0 і 1 при будь-яких значеннях і .
  • при малому значенні відкритого показника (, наприклад) можлива ситуація, коли виявиться, що . Тоді , і зловмисник легко зможе відновити вихідне повідомлення, обчисливши корінь ступеня з .
  • оскільки RSA є детермінованим алгоритмом, тобто не використовує випадкових значень у процесі роботи, то зловмисник може використати атаку з обраним відкритим текстом.

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

Вибір значення відкритого показника Редагувати

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

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

Вибір значення секретного показника Редагувати

Значення секретного показника повинне бути досить великим. У 1990 році Міхаель Вінер (Michael J. Wiener) показав, що якщо і , то є ефективний спосіб обчислити по і . Однак, якщо значення вибирається невеликим, то виявляється досить великим і проблеми не виникає.

Довжина ключа Редагувати

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

Проблеми реалізації Редагувати

ROCA Редагувати

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

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

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

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

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

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

Див. також Редагувати

Примітки Редагувати

  1. The RSA one way permutation Textbook RSA is insecure [ 30 листопада 2012 у Wayback Machine.] на сайті Стенфордського університету (англ.)
  2. ↑ Dan Goodin (Oct 16 2017). . Ars Technica. Архів оригіналу за 19 жовтня 2018. Процитовано 17 квітня 2021. 
  3. Matus Nemec, Marek Sys, Petr Svenda, Dusan Klinec, Vashek Matyas (2017). The Return of Coppersmith's Attack: Practical Factorization of Widely Used RSA Moduli. 24th ACM Conference on Computer and Communications Security (CCS'2017) (ACM): 1631–1648. ISBN 978-1-4503-4946-8. doi:10.1145/3133956.3133969. 
  4. Kaspar Korjus (30 жовтня 2017). . Архів оригіналу за 4 травня 2021. Процитовано 17 квітня 2021. 
  5. . CRoCS Wiki. Архів оригіналу за 23 березня 2021. Процитовано 19 жовтня 2017. 

Література Редагувати

  • Menezes A. J., van Oorschot P. C., Vanstone S. A. Handbook of Applied Cryptography. — CRC Press, 1996. — 794 p. (pdf [ 20 квітня 2015 у Wayback Machine.])
  • Брассар Ж. Современная криптология = Modern Cryptology: A Tutorial. — М. : Полимед, 1999. — 176 с.
  • Земор Ж. Курс криптографии = Cours de cryptographie. — Ижевск : РХД, 2006. — 256 с.
  • Коутинхо С. Введение в теорию чисел. Алгоритм RSA = The Mathematics of Ciphers: Number Theory and RSA Cryptography. — М. : Постмаркет, 2001. — 328 с.
  • ван Тилборг Х. К. А. Основы криптологии = Fundamentals of Cryptology. — М. : Мир, 2006. — 472 с.
  • Ян С. Криптоанализ RSA = Cryptanalytic Attacks on RSA. — Ижевск : РХД, 2011. — 312 с.
  • Ященко В. В. Введение в криптографию. — М. : МЦНМО, 2012. — 348 с. (pdf [ 20 березня 2014 у Wayback Machine.])


Це незавершена стаття з криптографії.
Ви можете допомогти проєкту, виправивши або дописавши її.
Ця стаття потребує додаткових посилань на джерела для поліпшення її перевірності. Будь ласка, допоможіть удосконалити цю статтю, додавши посилання на надійні (авторитетні) джерела. Зверніться на сторінку обговорення за поясненнями та допоможіть виправити недоліки.
Матеріал без джерел може бути піддано сумніву та вилучено. (січень 2017)
Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри
Дата публікації:
RSA abreviatura vid prizvish Rivest Shamir ta Adleman kriptografichnij algoritm z vidkritim klyuchem sho bazuyetsya na obchislyuvalnij skladnosti zadachi faktorizaciyi velikih cilih chisel RSA stav pershim algoritmom takogo tipu pridatnim i dlya shifruvannya i dlya cifrovogo pidpisu Algoritm zastosovuyetsya do velikoyi kilkosti kriptografichnih zastosunkiv Zmist 1 Istoriya 2 Opis algoritmu 2 1 Rozpovsyudzhennya klyuchiv 2 2 Generaciya klyuchiv 2 3 Shifruvannya 2 4 Rozshifruvannya 2 5 Priklad 3 Cifrovij pidpis 4 Deyaki osoblivosti algoritmu 4 1 Generaciya prostih chisel 4 2 Dopovnennya povidomlen 4 3 Vibir znachennya vidkritogo pokaznika 4 4 Vibir znachennya sekretnogo pokaznika 5 Dovzhina klyucha 5 1 Problemi realizaciyi 5 1 1 ROCA 6 Div takozh 7 Primitki 8 LiteraturaIstoriya RedaguvatiOpis RSA bulo opublikovano u 1977 roci Ronaldom Rajvestom Adi Shamirom i Leonardom Adlemanom z Massachusetskogo tehnologichnogo institutu MIT Britanskij matematik Kliford Koks en angl Clifford Cocks sho pracyuvav v centri uryadovogo zv yazku GCHQ Velikoyi Britaniyi opisav analogichnu sistemu v 1973 roci u vnutrishnih dokumentah centru ale cya robota ne bula rozkrita do 1997 roku tozh Rajvest Shamir i Adleman rozrobili RSA nezalezhno vid roboti Koksa V 1983 roci buv vidanij patent 4405829 Arhivovano 16 zhovtnya 2007 u Wayback Machine SShA termin diyi yakogo minuv 21 veresnya 2000 roku Opis algoritmu RedaguvatiVikipidruchnik maye knigu na temu Rozv yaznik vprav po diskretnij matematici Koduvannya Algoritm RSAAlgoritm RSA skladayetsya z 4 etapiv generaciyi klyuchiv shifruvannya rozshifruvannya ta rozpovsyudzhennya klyuchiv Bezpeka algoritmu RSA pobudovana na principi skladnosti faktorizaciyi cilih chisel Algoritm vikoristovuye dva klyuchi vidkritij public i sekretnij private razom vidkritij i vidpovidnij jomu sekretnij klyuchi utvoryuyut pari klyuchiv keypair Vidkritij klyuch ne potribno zberigati v tayemnici vin vikoristovuyetsya dlya shifruvannya danih Yaksho povidomlennya bulo zashifrovano vidkritim klyuchem to rozshifruvati jogo mozhna tilki vidpovidnim sekretnim klyuchem Rozpovsyudzhennya klyuchiv Redaguvati Dlya togo shob Bob mig vidpraviti svoyi sekretni povidomlennya Alisa peredaye svij vidkritij klyuch n e Bobu cherez nadijnij ale ne obov yazkovo sekretnij marshrut Sekretnij klyuch d nikoli ne rozpovsyudzhuyetsya Generaciya klyuchiv Redaguvati Dlya togo shob zgeneruvati pari klyuchiv vikonuyutsya taki diyi Vibirayutsya dva veliki prosti chisla p displaystyle p nbsp i q displaystyle q nbsp priblizno 512 bit zavdovzhki kozhne Obchislyuyetsya yih dobutok n p q displaystyle n pq nbsp Obchislyuyetsya funkciya Ejlera f n p 1 q 1 displaystyle varphi n p 1 q 1 nbsp Vibirayetsya cile chislo e displaystyle e nbsp take sho 1 lt e lt f n displaystyle 1 lt e lt varphi n nbsp ta e displaystyle e nbsp vzayemno proste z f n displaystyle varphi n nbsp Za dopomogoyu rozshirenogo algoritmu Evklida znahoditsya chislo d displaystyle d nbsp take sho e d 1 mod f n displaystyle ed equiv 1 pmod varphi n nbsp Chislo n displaystyle n nbsp nazivayetsya modulem a chisla e displaystyle e nbsp i d displaystyle d nbsp vidkritoyu j sekretnoyu eksponentami angl encryption and decryption exponents vidpovidno Pari chisel n e displaystyle n e nbsp ye vidkritoyu chastinoyu klyucha a n d displaystyle n d nbsp sekretnoyu Chisla p displaystyle p nbsp i q displaystyle q nbsp pislya generaciyi pari klyuchiv mozhut buti znisheni ale v zhodnomu razi ne povinni buti rozkriti Shifruvannya Redaguvati Pripustimo sho Bob hotiv bi vidpraviti povidomlennya M Alisi Spochatku vin peretvoryuye M v cile chislo m tak shob 0 m lt n za dopomogoyu uzgodzhenogo oborotnogo protokolu vidomogo yak shemi dopovnennya Potim vin obchislyuye zashifrovanij tekst c vikoristovuyuchi vidkritij klyuch Alisi e za dopomogoyu rivnyannya c m e mod n displaystyle c m e bmod n nbsp Ce mozhe buti zrobleno dosit shvidko navit dlya 500 bitnih chisel z vikoristannyam modulnogo zvedennya v stupin Potim Bob peredaye c Alisi Rozshifruvannya Redaguvati Dlya rozshifruvannya povidomlennya Boba m Alisi potribno obchisliti taku rivnist m c d mod n displaystyle m c d bmod n nbsp Nevazhko perekonatisya sho pri rozshifruvanni vidnovitsya vihidne povidomlennya c d m e d m e d mod n displaystyle c d equiv m e d equiv m ed pmod n nbsp Z umovi e d 1 mod f n displaystyle ed equiv 1 pmod varphi n nbsp viplivaye sho e d k f n 1 displaystyle ed k varphi n 1 nbsp dlya deyakogo cilogo k displaystyle k nbsp otzhe m e d m k f n 1 mod n displaystyle m ed equiv m k varphi n 1 pmod n nbsp Zgidno z teoremoyu Ejlera m f n 1 mod n displaystyle m varphi n equiv 1 pmod n nbsp tomu m k f n 1 m mod n displaystyle m k varphi n 1 equiv m pmod n nbsp c d m mod n displaystyle c d equiv m pmod n nbsp RSA pripushennya RSA ye odnostoronnoyu perestanovkoyu tobto dlya bud yakogo diyevogo algoritmu A jmovirnist P r A n e c c 1 e displaystyle Pr A n e c c 1 e nbsp duzhe mala sho oznachaye nemozhlivist obernennya RSA bez sekretnoyi informaciyi d displaystyle d nbsp Navedenij vishe variant shifruvannya nazivayetsya RSA z pidruchnika angl textbook RSA 1 i ye cilkom urazlivim V zhodnomu razi jogo ne mozhna vikoristovuvati v kriptosistemah Priklad Redaguvati Etap Opis operaciyi Rezultat operaciyiGeneraciya klyuchiv Obrati dva prostih riznih chisla p 3557 displaystyle p 3557 nbsp q 2579 displaystyle q 2579 nbsp Obchisliti dobutok n p q 3557 2579 9173503 displaystyle n p cdot q 3557 cdot 2579 9173503 nbsp Obchisliti funkciyu Ejlera f n p 1 q 1 9167368 displaystyle varphi n p 1 q 1 9167368 nbsp Obrati vidkritu eksponentu e 3 displaystyle e 3 nbsp Obchisliti sekretnu eksponentu d e 1 mod f n displaystyle d e 1 pmod varphi n nbsp d 6111579 displaystyle d 6111579 nbsp Opublikuvati vidkritij klyuch e n 3 9173503 displaystyle e n 3 9173503 nbsp Zberegti sekretnij klyuch d n 6111579 9173503 displaystyle d n 6111579 9173503 nbsp Shifruvannya Obrati tekst dlya shifruvannya m 111111 displaystyle m 111111 nbsp Obchisliti shifrotekst c E m m e mod n 111111 3 mod 9173503 4051753 displaystyle begin aligned c amp E m amp m e mod n amp 111111 3 mod 9173503 amp 4051753 end aligned nbsp Rozshifruvannya Obchisliti vihidne povidomlennya m D c c d mod n 4051753 6111579 mod 9173503 111111 displaystyle begin aligned m amp D c amp c d mod n amp 4051753 6111579 mod 9173503 amp 111111 end aligned nbsp Cifrovij pidpis RedaguvatiDiv takozh Elektronnij cifrovij pidpis RSA mozhe vikoristovuvatisya ne tilki dlya shifruvannya ale j dlya cifrovogo pidpisu Pidpis s displaystyle s nbsp povidomlennya m displaystyle m nbsp obchislyuyetsya z vikoristannyam sekretnogo klyucha za formuloyu s m d mod n displaystyle s m d bmod n nbsp Dlya perevirki pravilnosti pidpisu potribno perekonatisya sho vikonuyetsya rivnist m s e mod n displaystyle m s e bmod n nbsp Deyaki osoblivosti algoritmu RedaguvatiGeneraciya prostih chisel Redaguvati Dlya znahodzhennya dvoh velikih prostih chisel p displaystyle p nbsp i q displaystyle q nbsp pri generaciyi klyucha zvichajno vikoristovuyutsya jmovirnisni testi chisel na prostotu yaki dozvolyayut shvidko viyaviti j vidkinuti skladeni chisla Dlya generaciyi p displaystyle p nbsp i q displaystyle q nbsp neobhidno vikoristovuvati kriptografichno nadijnij generator vipadkovih chisel U porushnika ne maye buti mozhlivosti oderzhati bud yaku informaciyu pro znachennya cih chisel p displaystyle p nbsp i q displaystyle q nbsp ne povinni buti zanadto blizkimi odne do odnogo inakshe mozhna bude znajti yih vikoristovuyuchi metod faktorizaciyi Ferma Krim togo neobhidno vibirati silni prosti chisla shob ne mozhna bulo skoristatisya p 1 algoritmom Polarda Dopovnennya povidomlen Redaguvati Pri praktichnomu vikoristanni neobhidno deyakim chinom dopovnyuvati povidomlennya Vidsutnist dopovnen mozhe prizvesti do deyakih problem znachennya m 0 displaystyle m 0 nbsp i m 1 displaystyle m 1 nbsp dadut pri shifruvanni shifroteksti 0 i 1 pri bud yakih znachennyah e displaystyle e nbsp i n displaystyle n nbsp pri malomu znachenni vidkritogo pokaznika e 3 displaystyle e 3 nbsp napriklad mozhliva situaciya koli viyavitsya sho m e lt n displaystyle m e lt n nbsp Todi c m e mod n m e displaystyle c m e bmod n m e nbsp i zlovmisnik legko zmozhe vidnoviti vihidne povidomlennya obchislivshi korin stupenya e displaystyle e nbsp z c displaystyle c nbsp oskilki RSA ye determinovanim algoritmom tobto ne vikoristovuye vipadkovih znachen u procesi roboti to zlovmisnik mozhe vikoristati ataku z obranim vidkritim tekstom Dlya rozv yazannya cih problem povidomlennya dopovnyuyutsya pered kozhnim shifruvannyam deyakim vipadkovim znachennyam Dopovnennya vikonuyetsya takim chinom shob garantuvati sho m 0 displaystyle m neq 0 nbsp m 1 displaystyle m neq 1 nbsp i m e gt n displaystyle m e gt n nbsp Krim togo oskilki povidomlennya dopovnyuyetsya vipadkovimi danimi to shifrovuyuchi toj samij vidkritij tekst mi shoraz budemo oderzhuvati inshe znachennya shifrotekstu sho robit ataku z obranim vidkritim tekstom nemozhlivoyu Vibir znachennya vidkritogo pokaznika Redaguvati RSA pracyuye znachno povilnishe simetrichnih algoritmiv Dlya pidvishennya shvidkosti shifruvannya vidkritij pokaznik e displaystyle e nbsp vibirayetsya nevelikim zvichajno 3 17 abo 65537 2 obrati ne mozhna bo e displaystyle e nbsp povinno buti vzayemno prostim iz f n p 1 q 1 displaystyle varphi n p 1 q 1 nbsp Ci chisla u dvijkovomu viglyadi mistyat tilki po dvi odinici sho zmenshuye chislo neobhidnih operacij mnozhennya pri pidnesenni do stepenya Napriklad dlya pidnesennya chisla m displaystyle m nbsp do stepenya 17 potribno vikonati tilki 5 operacij mnozhennya m 2 m m displaystyle m 2 m cdot m nbsp m 4 m 2 m 2 displaystyle m 4 m 2 cdot m 2 nbsp m 8 m 4 m 4 displaystyle m 8 m 4 cdot m 4 nbsp m 16 m 8 m 8 displaystyle m 16 m 8 cdot m 8 nbsp m 17 m 16 m displaystyle m 17 m 16 cdot m nbsp Vibir malogo znachennya vidkritogo pokaznika mozhe prizvesti do rozkrittya povidomlennya yaksho vono vidpravlyayetsya vidrazu dekilkom oderzhuvacham ale cya problema virishuyetsya za rahunok dopovnennya povidomlen Vibir znachennya sekretnogo pokaznika Redaguvati Znachennya sekretnogo pokaznika d displaystyle d nbsp povinne buti dosit velikim U 1990 roci Mihael Viner Michael J Wiener pokazav sho yaksho q lt p lt 2 q displaystyle q lt p lt 2q nbsp i d lt n 1 4 3 displaystyle d lt n frac 1 4 3 nbsp to ye efektivnij sposib obchisliti d displaystyle d nbsp po n displaystyle n nbsp i e displaystyle e nbsp Odnak yaksho znachennya e displaystyle e nbsp vibirayetsya nevelikim to d displaystyle d nbsp viyavlyayetsya dosit velikim i problemi ne vinikaye Dovzhina klyucha RedaguvatiChislo n povinne mati rozmir ne menshe 512 bit Na 2007 rik sistema shifruvannya na osnovi RSA vvazhalas nadijnoyu pochinayuchi z velichini N v 1024 biti Problemi realizaciyi Redaguvati ROCA Redaguvati Dokladnishe ROCAV zhovtni 2017 roku mizhnarodna grupa doslidnikiv Slovachchina Chehiya Velika Britaniya Italiya oprilyudnili dopovid pro viyavlenu nimi vrazlivist v algoritmi generatora psevdovipadkovih chisel v kriptografichnij biblioteci kompaniyi Infeneon Dana vrazlivist vinikaye pri roboti biblioteki na smart kartah ta v podibnih vbudovanih sistemah Viyavleni vadi roblyat praktichno dosyazhnoyu faktorizaciyu vikoristanih pri generaciyi pari klyuchiv prostih chisel Zlovmisnik maye mozhlivist vidnoviti sekretnij klyuch za vidkritim klyuchem zhertvi 2 3 Stanom na 2017 rik doslidniki ocinyuyut vitrati u najgirshomu vipadku dlya ataki metodom Kopersmita proti klyucha rozmirom 2048 bit 17 dniv za 40 300 ta 76 za 45 hvilin dlya klyucha rozmirom 1024 bit dlya orendovanogo klastera z tisyachi vuzliv na Amazon Web Service V serednomu vitrati budut vdvichi menshi Pri comu klyuch rozmirom 4096 bit viyavivsya slabshim za klyuch rozmirom 3072 bit dlya yakogo ataka lishayetsya praktichno vazhkoyu 2 Doslidniki takozh stvorili algoritm dlya perevirki klyucha na vrazlivist do viyavlenoyi nimi ataki Perevirka potrebuye blizko 1 milisekundi na suchasnomu procesori 2 Vrazlivi klyuchi buli viyavleni u nizci produktiv ta internet proektah V tomu chisli bulo viyavleno ponad 750 000 vrazlivih do ataki smart kart sistemi elektronnogo gromadyanstva Estoniyi klyuchah Yubikey 4 tosho 2 1 listopada 2017 roku Estoniya rozpochala proces onovlennya cifrovih posvidchen z perehodom na vikoristannya algoritmiv kriptografiyi na eliptichnih krivih 4 Vrazhena biblioteka projshla sertifikaciyu NIST FIPS 140 2 Level 2 ta Common Criteria a vrazlivist bula prisutnya v nij z 2012 roku 2 Viyavlena vada otrimala nazvu ROCA ta kod CVE 2017 15361 5 Div takozh RedaguvatiOdnostoronnya funkciya z sekretom Asimetrichni algoritmi shifruvannya Obmin klyuchami Protokol Diffi Gellmana Teoriya skladnosti obchislenPrimitki Redaguvati The RSA one way permutation Textbook RSA is insecure Arhivovano 30 listopada 2012 u Wayback Machine na sajti Stenfordskogo universitetu angl a b v g d Dan Goodin Oct 16 2017 Millions of high security crypto keys crippled by newly discovered flaw Ars Technica Arhiv originalu za 19 zhovtnya 2018 Procitovano 17 kvitnya 2021 Matus Nemec Marek Sys Petr Svenda Dusan Klinec Vashek Matyas 2017 The Return of Coppersmith s Attack Practical Factorization of Widely Used RSA Moduli 24th ACM Conference on Computer and Communications Security CCS 2017 ACM 1631 1648 ISBN 978 1 4503 4946 8 doi 10 1145 3133956 3133969 Kaspar Korjus 30 zhovtnya 2017 Estonia is enhancing the security of its digital identities Arhiv originalu za 4 travnya 2021 Procitovano 17 kvitnya 2021 ROCA Vulnerable RSA generation CVE 2017 15361 CRoCS Wiki Arhiv originalu za 23 bereznya 2021 Procitovano 19 zhovtnya 2017 Literatura RedaguvatiMenezes A J van Oorschot P C Vanstone S A Handbook of Applied Cryptography CRC Press 1996 794 p pdf Arhivovano 20 kvitnya 2015 u Wayback Machine Brassar Zh Sovremennaya kriptologiya Modern Cryptology A Tutorial M Polimed 1999 176 s Zemor Zh Kurs kriptografii Cours de cryptographie Izhevsk RHD 2006 256 s Koutinho S Vvedenie v teoriyu chisel Algoritm RSA The Mathematics of Ciphers Number Theory and RSA Cryptography M Postmarket 2001 328 s van Tilborg H K A Osnovy kriptologii Fundamentals of Cryptology M Mir 2006 472 s Yan S Kriptoanaliz RSA Cryptanalytic Attacks on RSA Izhevsk RHD 2011 312 s Yashenko V V Vvedenie v kriptografiyu M MCNMO 2012 348 s pdf Arhivovano 20 bereznya 2014 u Wayback Machine nbsp Ce nezavershena stattya z kriptografiyi Vi mozhete dopomogti proyektu vipravivshi abo dopisavshi yiyi Cya stattya potrebuye dodatkovih posilan na dzherela dlya polipshennya yiyi perevirnosti Bud laska dopomozhit udoskonaliti cyu stattyu dodavshi posilannya na nadijni avtoritetni dzherela Zvernitsya na storinku obgovorennya za poyasnennyami ta dopomozhit vipraviti nedoliki Material bez dzherel mozhe buti piddano sumnivu ta vilucheno sichen 2017 Otrimano z https uk wikipedia org w index php title RSA amp oldid 35715052