Реалізація криптоалгоритму RSA

МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ НАЦІОНАЛЬНИЙ АВІАЦІЙНИЙ УНІВЕРСИТЕТ

ІНСТИТУТ КОМПЮТЕРНИХ ІНФОРМАЦІЙНИХ ТЕХНОЛОГІЙ КАФЕДРА ЗАСОБІВ ЗАХИСТУ ІНФОРМАЦІЇ

Контрольна робота з дисципліни «Архітектура та програмування мікропроцесорів»

на тему: «Реалізація криптоалгоритму RSA»

Виконала:

Агафонова О.Ю.

Київ — 2014р.

Зміст Вступ

1. Опис алгоритму RSA

2. Алгоритм створення відкритого і секретного ключів

3. Шифрування і розшифрування (приклад)

4. Алгоритм шифрування сеансового ключа

5. Коректність схеми RSA

6. Цифровий підпис

7. Використання китайської теореми про залишки для прискорення розшифрування

8. Криптоаналіз RSA

9. Атаки на алгоритм RSA

10. Застосування RSA

Список використаної літератури

Вступ

RSA (абревіатура від прізвищ Rivest, Shamir і Adleman) — криптографічний алгоритм з відкритим ключем, що грунтується на обчислювальній складності задачі факторизації великих цілих чисел. Криптосистема RSA стала першою системою, придатної і для шифрування, і для цифрового підпису. Алгоритм використовується у великому числі криптографічних додатків, включаючи PGP, S/ MIME, TLS / SSL, IPSEC / IKE та інших.

Історія виникнення алгоритму RSA.

Опублікована в листопаді 1976 стаття Уитфилда Діффі і Мартіна Хеллмана «Нові напрямки в криптографії» (англ. New Directions in Cryptography) перевернула уявлення про криптографічних системах, заклавши основи криптографії з відкритим ключем. Розроблений згодом алгоритм Діффі - Хеллмана дозволяв двом сторонам отримати загальний секретний ключ, використовуючи незахищений канал зв’язку. Однак цей алгоритм не вирішував проблему аутентифікації. Без додаткових коштів користувачі не могли бути впевнені, з ким саме вони згенерували загальний секретний ключ.

Вивчивши цю статтю, троє вчених Рональд Ривест, Аді Шамір і Леонард Адлеман з Массачусетського технологічного інституту (MIT) приступили до пошуків математичної функції, яка б дозволяла реалізувати сформульовану Уітфілд Діффі і Мартіном Хеллманом модель криптографічного системи з відкритим ключем. Після роботи над більш ніж 40 можливими варіантами, їм вдалося знайти алгоритм, заснований на розходженні в тому, наскільки легко знаходити великі прості числа і наскільки складно розкладати на множники твір двох великих простих чисел, що отримав згодом назву RSA. Система була названа за першими літерами прізвищ її творців.

У серпні 1977 в колонці «Математичні ігри» Мартіна Гарднера в журналі Scientific American, з дозволу Рональда Ривеста з’явилося перше опис криптосистеми RSA. Читачам також було запропоновано дешифрувати англійську фразу, зашифровану описаним алгоритмом:

В якості відкритих параметрів системи були використані числа n = 1 143 816 6 879 541 (129 десяткових знаків, 425 біт, також відоме як RSA-129) і e = 9007. За розшифровку була обіцяна нагорода в 100 доларів США. За заявою Ривеста, для факторизації числа треба було б більше 40 квадрильйонів років. Проте трохи більше ніж через 15 років, 3 вересня 1993 було оголошено про старт проекту розподілених обчислень з координацією через електронну пошту по знаходженню сомножителей числа RSA- 129 і рішенням головоломки. Протягом півроку більше 600 добровольців з 20 країн жертвували процесорний час 1600 машин (дві з яких були факс-машинами). В результаті були знайдені прості множники і розшифровано вихідне повідомлення, яке являє собою фразу «THE MAGIC WORDS ARE SQUEAMISH OSSIFRAGE (англ.)» («Чарівні слова — це бридливий ягнятник»). Отриману нагороду переможці пожертвували в фонд вільного програмного забезпечення.

Після публікації Мартіна Гарднера повний опис нової криптосистеми будь-який бажаючий міг отримати, виславши поштою запит Рональду Ривеста, з доданим конвертом із зворотною адресою і марками на 35 центів Повний опис нової криптосистеми було опубліковано в журналі «Communications of the ACM «в лютому 1978 року.

Заявка на патент була подана 14 грудня 1977, в якості власника був вказаний MIT. Патент 4 405 829 був виданий 20 вересня 1983, а 21 вересня 2000 термін його дії закінчився. Однак за межами США у винахідників патенту на алгоритм не було, так як у більшості країн його необхідно було отримати до першої публікації.

У 1982 році Ривест, Шамір і Адлеман організували компанію RSA Data Security (англ.) (зараз — підрозділ EMC). У 1989 році RSA, разом з симетричним шифром DES, згадується в RFC 1115, тим самим починаючи використання алгоритму в зародження мережі Internet, а в 1990 році використовувати алгоритм починає міністерство оборони США.

У листопаді 1993 року відкрито публікується версія 1.5 стандарту PKCS1 (англ.), що описує застосування RSA для шифрування і створення електронного підпису. Останні версії стандарту також доступні у вигляді RFC (RFC 2 313 — 1.5, 1993 рік; RFC 2437 — 2.0, 1998 рік; RFC 3447 — 2.1, 2002 рік).

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

алгоритм ключ шифрування електронний

1. Опис алгоритму RSA

Криптографічні системи з відкритим ключем використовують так звані односторонні функції, які мають наступну властивість:

* Якщо відомо, то обчислити відносно просто

* Якщо відомо, то для обчислення немає простого (ефективного) шляху.

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

В основу криптографічного системи з відкритим ключем RSA покладена складність завдання факторизації твори двох великих простих чисел. Для шифрування використовується операція зведення в ступінь по модулю великого числа. Щоб дешифрувати за розумний час (зворотної операції) необхідно вміти обчислювати функцію Ейлера від даного великого числа, для чого необхідно знати розкладання числа на прості множники.

У криптографічного системі з відкритим ключем кожен учасник має в своєму розпорядженні як відкритим ключем (англ. public key), так і закритим ключем (англ. private key). У криптографічного системі RSA кожен ключ складається з пари цілих чисел. Кожен учасник створює свій відкритий і закритий ключ самостійно. Закритий ключ кожен з них тримає в секреті, а відкриті ключі можна повідомляти кому завгодно або навіть публікувати їх. Відкритий і закритий ключі кожного учасника обміну повідомленнями в криптосистеме RSA утворюють «узгоджену пару» в тому сенсі, що вони є взаємно зворотними, тобто:

допустимих пар відкритого та закритого ключів

відповідні функції шифрування і розшифрування такі, що повідомлень, де — безліч допустимих повідомлень,

2. Алгоритм створення відкритого і секретного ключів

RSA-ключі генеруються таким чином:

1. Вибираються два різних випадкових простих числа і заданого розміру (наприклад, 1024 біта кожне).

2. Обчислюється їх добуток, яке називається модулем.

3. Обчислюється значення функції Ейлера від числа :

4. Вибирається ціле число (), взаємно просте зі значенням функції. Звичайно як беруть прості числа, що містять невелику кількість одиничних біт в двійковій запису, наприклад, прості числа Ферма 17, 257 або 65 537.

· Число називається відкритою експонентою (public exponent)

· Час, необхідний для шифрування з використанням швидкого зведення в ступінь, пропорційно числу одиничних біт в .

· Занадто малі значення, наприклад 3, потенційно можуть послабити безпеку схеми RSA.

5. Обчислюється число, мультиплікативно зворотне до числа по модулю, тобто число, яке задовольняє умові:

· Число називається секретної експонентою. Зазвичай, воно обчислюється за допомогою розширеного алгоритму Евкліда.

6. Пара публікується як відкритого ключа RSA (RSA public key).

7. Пара грає роль закритого ключа RSA (RSA private key) і тримається в секреті.

3. Шифрування і розшифрування (приклад) Припустимо, Боб хоче послати Алісі повідомлення .

Повідомленнями є цілі числа в інтервалі від до, т. е. .

4. Алгоритм шифрування сеансового ключа Найбільш використовуваним в даний час є змішаний алгоритм шифрування, в якому спочатку шифрується сеансовий ключ, а потім вже з його допомогою учасники шифрують свої повідомлення симетричними системами. Після завершення сеансу сеансовий ключ як правило знищується.

Алгоритм шифрування сеансового ключа виглядає наступним чином:

У разі, коли сеансовий ключ більше, ніж модуль сеансовий ключ розбивають на блоки потрібної довжини (у разі потреби доповнюють нулями) і шифрують кожен блок.

5. Коректність схеми RSA

Рівняння і, на яких заснована схема RSA, визначають взаємно зворотні перетворення безлічі

6. Цифровий підпис

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

Припустимо, що Алісі (стороні) потрібно відправити Бобу (стороні) повідомлення, підтверджене електронним цифровим підписом.

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

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

Зауважимо, що підписане повідомлення НЕ зашифровано. Воно пересилається в початковому вигляді і його вміст не захищене від порушення конфіденційності. Шляхом спільного застосування представлених вище схем шифрування і цифрового підпису в системі RSA можна створювати повідомлення, які будуть і зашифровані, і містити цифровий підпис. Для цього автор спочатку повинен додати до повідомлення свою цифровий підпис, а потім — зашифрувати вийшла в результаті пару (що складається з самого повідомлення і підписи до нього) за допомогою відкритого ключа належить одержувачу. Одержувач розшифровує отримане повідомлення за допомогою свого секретного ключа. Якщо проводити аналогію з пересилкою звичайних паперових документів, то цей процес схожий на те, як якби автор документа поставив під ним свій друк, а потім поклав його в паперовий конверт і запечатав, з тим щоб конверт був роздрукований лише тією людиною, кому адресоване повідомлення.

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

Оскільки генерація ключів відбувається значно рідше операцій, що реалізують шифрування, розшифрування, а також створення і перевірку цифрового підпису, задача обчислення представляє основну обчислювальну складність. Це завдання може бути вирішена за допомогою алгоритму швидкого зведення в ступінь. З використанням цього алгоритму для обчислення потрібно операцій множення за модулем ^[17].

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

Таким чином час виконання операцій зростає із збільшенням кількості ненульових бітів у двійковому поданні відкритої експоненти e. Щоб збільшити швидкість шифрування, значення e часто вибирають рівним 17, 257 або 65 537 — простим числам, двійкове подання яких містить лише дві одиниці: 17 ₁₀ = 10 001 ₂, 257 ₁₀ = 100 000 001 ₂, 65 537 ₁₀ = 10 000 000 000 000 000 ₂ (прості числа Ферма).

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

Алгоритм RSA набагато повільніше, ніж AES та інші алгоритми, які використовують симетричні блокові шифри.

7. Використання китайської теореми про залишки для прискорення розшифрування При расшифрованні або підписуванні повідомлення в алгоритмі RSA показник обчислюється мірою буде досить великим числом (порядку 1000 біт). Тому потрібне алгоритм, який скорочує кількість операцій. Оскільки числа і в розкладанні відомі зашифровувати ^{[ відомі власнику закритого ключа! ]}, то можна обчислити:

Оскільки і - числа порядку на ці дії буде потрібно два потенцирования з показником 512 знаків за модулем 512-бітового числа. Це істотно швидше, ніж одне потенцирование з 1024-бітовим показником за модулем числа з 1024 двійковими знаками. Далі залишилося відновити по і що можна зробити за допомогою китайської теореми про залишки. ^[18]

8. Криптоаналіз RSA

Стійкість алгоритму грунтується на складності обчислення зворотної функції до функції шифрування

.

Для обчислення по відомим потрібно знайти такий, щоб тобто Обчислення зворотного елемента по модулю не є складним завданням, проте зловмисникові невідомо значення. Для обчислення функції Ейлера від відомого числа необхідно знати розкладання цього числа на прості множники. Перебування таких множників і є складним завданням, а знання цих множників — «потайними дверцями» (backdoor), яка використовується для обчислення власником ключа. Існує безліч алгоритмів для знаходження простих співмножників, так званої факторизації, найшвидший з яких на сьогоднішній день — загальний метод решета числового поля, швидкість якого для k-бітного цілого числа становить для деякого .

У 2010 році групі вчених з Швейцарії, Японії, Франції, Нідерландів, Німеччини та США вдалося успішно обчислити дані, зашифровані за допомогою криптографічного ключа стандарту RSA довжиною 768 біт. Знаходження простих співмножників здійснювалося загальним методом решета числового поля. ^[20] За словами дослідників, після їх роботи в якості надійної системи шифрування можна розглядати тільки RSA-ключі довжиною 1024 біта і більше. Причому від шифрування ключем довжиною в 1024 біт варто відмовитися в найближчі три-чотири роки. З 31 грудня 2013 браузери Mozilla перестануть підтримувати сертифікати засвідчують центрів з ключами RSA менше 2048 біт.

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

9. Атаки на алгоритм RSA

У деяких додатках потрібно прискорити процес розшифрування в алгоритмі RSA. Тому вибирається невелика розшифровує експонента. У разі коли розшифровує експонента можна визначити за поліноміальний час за допомогою атаки Вінера, ^[18] що спирається на безперервні дробу.

Оскільки НОД то підходяща дріб в розкладанні дробу в безперервну. Таким чином, можна дізнатися що розшифровує експоненту, по черзі підставляючи знаменники відповідних дробів у вираз:

для деякого випадкового числа Отримавши рівність, знайдемо Загальне число відповідних дробів, яке доведеться перевірити оцінюється як

10. Застосування RSA

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

Також вона використовується у відкритій системі шифрування PGP та інших системах шифрування (наприклад, DarkCryptTC і формат xdc) у поєднанні з симетричними алгоритмами.

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

Список використаної літератури

1. Bakhtiari M., Maarof MA Serious Security Weakness In RSA Cryptosystem / /IJCSI International Journal of Computer Science. — January 2012. — В. 1, № 3. — Т. 9. -ISSN 1694−0814.

2. Whitfield Diffie, Martin E. Hellman. New Directions in Cryptography (англ.) / / IEEE Transactions on Information Theory. — Nov. 1976. — Т. IT-22. — С. 644−654.

3. A Quarter Century Of Recreational Mathematics, by Martin Gardner (англ.).Scientific American. — «Ronald L. Rivest of the Massachusetts Institute of Technology allowed me to be the first to reveal-in the August 1977 column-the» publickey «cipher system that he co-invented» Перевірено 3 березня 2012. Фотогалерея з першоджерела 23 червня 2012.

4. Перейти до:1 2 Martin Gardner. Mathematical Games: A new kind of cipher that would take millions of years to break (англ.) / / Scientific American. — 1977.

5. Bruce Schneier. Factoring — State of the Art and Predictions (англ.) (12 February 1995). Перевірено 3 березня 2012. Фотогалерея з першоджерела 23 червня 2012.