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

  • Вид работы:
    Контрольная работа
  • Предмет:
    Информационное обеспечение, программирование
  • Язык:
    Украинский
    ,
    Формат файла:
    MS Word
    521,2 Кб
  • Опубликовано:
    2015-06-05
Вы можете узнать стоимость помощи в написании студенческой работы.
Помощь в написании работы, которую точно примут!

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

МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ

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

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

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









Контрольна робота

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

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


Виконала:

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




Київ - 2014р.

Зміст

Вступ

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

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

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

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

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

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

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

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

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

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

Вступ

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

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

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

Вивчивши цю статтю, троє вчених Рональд Ривест <#"785028.files/image001.gif"> допустимих пар відкритого та закритого ключів

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

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

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

1.      Вибираються два різних випадкових простих числа <#"785028.files/image010.gif"> і заданого розміру (наприклад, 1024 біта <#"785028.files/image012.gif">, яке називається модулем.

.        Обчислюється значення функції Ейлера <#"785028.files/image013.gif">:


4.      Вибирається ціле число (), взаємно просте <#"785028.files/image017.gif">. Звичайно як беруть прості числа, що містять невелику кількість одиничних біт в двійковій запису <#"785028.files/image015.gif"> називається відкритою експонентою (public exponent)

·              Час, необхідний для шифрування з використанням швидкого зведення в ступінь <#"785028.files/image015.gif">.

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

.        Обчислюється число , мультиплікативно <#"785028.files/image015.gif">по модулю , тобто число, яке задовольняє умові:

·              Число називається секретної експонентою. Зазвичай, воно обчислюється за допомогою розширеного алгоритму Евкліда <#"785028.files/image020.gif">публікується як відкритого ключа RSA (RSA public key).

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


Припустимо, Боб хоче послати Алісі повідомлення .

Повідомленнями є цілі числа <#"785028.files/image023.gif">до , т.е. .


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

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

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



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

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

Рівняння і , на яких заснована схема RSA, визначають взаємно зворотні перетворення <#"785028.files/image034.gif">

 

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


Система RSA може використовуватися не тільки для шифрування, але і для цифрового підпису <#"785028.files/image036.gif">) потрібно відправити Бобу (стороні ) повідомлення , підтверджене електронним цифровим підписом <#"785028.files/image038.gif">


Оскільки цифровий підпис <#"785028.files/image036.gif">може переслати стороні електронний чек. Після того як сторона перевірить підпис боку на чеку, вона може передати його в свій банк, службовці якого також мають можливість перевірити підпис і здійснити відповідну грошову операцію.

Зауважимо, що підписане повідомлення НЕ зашифровано <#"785028.files/image041.gif">представляє основну обчислювальну складність. Це завдання може бути вирішена за допомогою алгоритму швидкого зведення в ступінь <#"785028.files/image042.gif">потрібно операцій множення за модулем  <#"785028.files/image020.gif">і закритий ключ задовольняють співвідношенням , . Тоді в процесах їх застосування виконується відповідно і  умножений по модулю.

Алгоритм RSA набагато повільніше, ніж AES <#"785028.files/image010.gif">і в розкладанні відомі зашифровувати [ відомі власнику закритого ключа! <#"785028.files/image049.gif">


Оскільки і  - числа порядку на ці дії буде потрібно два потенцирования з показником 512 знаків за модулем 512-бітового числа. Це істотно швидше, ніж одне потенцирование з 1024-бітовим показником за модулем числа з 1024 двійковими знаками. Далі залишилося відновити по і що можна зробити за допомогою китайської теореми про залишки <#"785028.files/image054.gif">.

Для обчислення по відомим потрібно знайти такий , щоб

тобто


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

для деякого .

У 2010 році групі вчених з Швейцарії, Японії, Франції, Нідерландів, Німеччини та США вдалося успішно обчислити дані, зашифровані за допомогою криптографічного ключа стандарту RSA довжиною 768 біт. Знаходження простих співмножників здійснювалося загальним методом решета числового поля <#"785028.files/image060.gif">можна визначити за поліноміальний час за допомогою атаки Вінера, [18] <#"785028.files/image061.gif">

Оскільки НОД то підходяща дріб в розкладанні дробу в безперервну <#"785028.files/image065.gif">

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

 

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


Система RSA використовується для захисту програмного забезпечення та в схемах цифрового підпису <http://ru.wikipedia.org/wiki/%D0%AD%D0%BB%D0%B5%D0%BA%D1%82%D1%80%D0%BE%D0%BD%D0%BD%D0%B0%D1%8F_%D1%86%D0%B8%D1%84%D1%80%D0%BE%D0%B2%D0%B0%D1%8F_%D0%BF%D0%BE%D0%B4%D0%BF%D0%B8%D1%81%D1%8C>.

Також вона використовується у відкритій системі шифрування PGP <http://ru.wikipedia.org/wiki/PGP> та інших системах шифрування (наприклад, DarkCryptTC і формат xdc) у поєднанні з симетричними алгоритмами <http://ru.wikipedia.org/wiki/%D0%A1%D0%B8%D0%BC%D0%BC%D0%B5%D1%82%D1%80%D0%B8%D1%87%D0%BD%D1%8B%D0%B9_%D0%B0%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC_%D1%88%D0%B8%D1%84%D1%80%D0%BE%D0%B2%D0%B0%D0%BD%D0%B8%D1%8F>.

Через низьку швидкість шифрування (близько 30 кбіт / с при 512 бітному ключі на процесорі 2 ГГц), повідомлення зазвичай шифрують за допомогою більш продуктивних симетричних алгоритмів з випадковим ключем (сеансовий ключ), а за допомогою RSA шифрують лише цей ключ, таким чином реалізується гібридна криптосистема <http://ru.wikipedia.org/wiki/%D0%93%D0%B8%D0%B1%D1%80%D0%B8%D0%B4%D0%BD%D0%B0%D1%8F_%D0%BA%D1%80%D0%B8%D0%BF%D1%82%D0%BE%D1%81%D0%B8%D1%81%D1%82%D0%B5%D0%BC%D0%B0>. Такий механізм має потенційні уразливості зважаючи на необхідність використовувати криптостійкий генератор випадкових чисел <http://ru.wikipedia.org/wiki/%D0%93%D0%B5%D0%BD%D0%B5%D1%80%D0%B0%D1%82%D0%BE%D1%80_%D1%81%D0%BB%D1%83%D1%87%D0%B0%D0%B9%D0%BD%D1%8B%D1%85_%D1%87%D0%B8%D1%81%D0%B5%D0%BB> для формування випадкового сеансового ключа симетричного шифрування і ефективно протистоїть атакам симетричний криптоалгоритм (на даний час широке застосування знаходять AES <http://ru.wikipedia.org/wiki/Advanced_Encryption_Standard>, IDEA <http://ru.wikipedia.org/wiki/IDEA>, Serpent <http://ru.wikipedia.org/wiki/Serpent>, Twofish <http://ru.wikipedia.org/wiki/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.

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

.        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.

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

Похожие работы на - Реалізація криптоалгоритму RSA

 

Не нашли материал для своей работы?
Поможем написать уникальную работу
Без плагиата!