• Гідрологія і Гідрометрія
• Господарське право
• Економіка будівництва
• Економіка природокористування
• Економічна теорія
• Земельне право
• Історія України
• Кримінально виконавче право
• Медична радіологія
• Методи аналізу
• Міжнародне приватне право
• Міжнародний маркетинг
• Основи екології
• Предмет Політологія
• Соціальне страхування
• Технічні засоби організації дорожнього руху
• Товарознавство продовольчих товарів

Методика криптоаналізу RSA

Методи криптоаналізу RSA криптосистем

Вважається, що абсолютну частку обчислювальної складності криптоаналізу RSA становить розв’язання задачі факторизації модуля перетворення. Тому задачу криптоаналізу RSA зводять до задачі розкладання (факторизації) модуля N на два простих числа – P та Q.

Вважається [236, 422, 11, 13], що найбільш ефективною (можливо) є така методика визначення RSA особистого ключа, наприклад E_k для цифрового підпису або Dk для направленого розшифрування k – го користувача.

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

Вхідні дані – відкритий параметр – модуль перетворення N_j = P Q та відкритий ключ (сертифікат) ЦП D_i. Конфіденційними параметрами є прості числа P та Q і відповідно значення функції Ойлера:

= , (9.1)

а також особистий ключ ЦПE_i.

З урахуванням наведеного, криптоаналіз RSA може бути виконаний згідно з такою методикою.

1. Криптоаналітик відповідним чином отримує дані про RSA криптосистему.

2. Криптоаналітик отримує відповідним чином відкриті параметри та відкритий ключ (сертифікат), тобто вхідні дані, що наведені вище.

3. Здійснюється факторизація модуля перетворення відповідного користувача N_i на два прості числа P та Q. Це найскладніший етап.

4. При відомих простих числа P та Q обчислюється значення функції Ойлера

= .

5. При відомих значеннях та відкритому ключі D_i розв’язується порівняння k-користувача відносно особистого ключа E_k:

. (9.2)

Наведемо також історію розв’язання задачі факторизації. Для великих з великими простими множниками розкладання на множники є серйозною проблемою. Разючою ілюстрацією цього може служити така історія [236]. У 1977 році три винахідники алгоритму RSA наважилися запропонувати читачам популярного журналу Scientific American дешифрувати направлено зашифроване повідомлення. Мартін Гарднер опублікував у журналі Scientific American зашифровану головоломку, для розшифрування якої потрібно було факторизувати RSA модуль перетворення – таке 129-розрядне число (428 бітів) [236, 11]:

N₁₂₉ = 114381625757888867669235779976146612010218296721242362562561842935706935245733897830597123563958705058989075147599290026879543541.

Повідомлення «The magic words are squeamish ossifrage», яке потрібно було зашифрувати, спочатку було записане у вигляді цілого числа (а = 01, b = 02, c = 03, …, z = 26, прогалина, 00). Потім воно було зашифроване направлено на відкритому ключі E_k = 9007. Наведені модуль перетворення та відкритий ключ, а також додаткова інформація що, N = P×Q, де P і Q – прості числа, довжиною відповідно 64- та 65-десяткових розрядів, були опубліковані в указаному журналі.

За розшифровку цього повідомлення вони запропонували нагороду в 100 дол. За їхніми оцінками, задача не могла бути розв’язана раніше, ніж приблизно через 40 квадрильйонів років [236]. Але у квітні 1994 року D. Atkins, M. Graff, K. Lenstra і C. Leylang зажадали виплати призової суми за успішний криптоаналіз усього після восьми місяців спільної роботи в Internet. Для розв’язання задачі факторизації зазначеного модуля було використано 1600 комп’ютерів різної потужності – від найпростіших до станції Gray C90. Задача факторизації, яка вимагала близько 5000 міпсороків, була розв’язана із серпня 1993 по квітень 1994 року із застосуванням квадратичного решета. Одиницею вимірювання складності задачі в даному випадку є MIPS-рік – обсяг роботи, що виконується протягом року процесором, що здійснює обробку одного мільйона команд у секунду, що приблизно еквівалентно виконанню 3×10¹³ команд. Так, машина на базі Pentium з частотою 2000 МГц показує швидкість 500 MIPS.

Таким чином, були визначені прості конфіденційні числа P та Q, причому [236, 11]:

P = 3490529510847650949147849619903898133417764638493387843990820577,

Q = 327691329932667095499619881908344614131177642967992942539798288533.

З квітня 1996 по квітень 2003 року були розв’язані задачі для RSA-130, RSA-140, RSA-155, RSA-160. Не факторизованим залишився лише RSA-150, але він у подальшому був відкликаний з переліку задач.

Останньою з розв’язаних задач є задача для RSA-232, у якій довжина ключа дорівнює 768 бітів. Групі вчених із Германії, Нідерландів, США, Франції, Швейцарії та Японії у 2009 році вдалося дешифрувати повідомлення, що було зашифроване на ключі 768 бітів згідно із стандартом RSA. Для цього було застосоване загальне решето числового поля. Згідно даних [423], на перший крок для вибору поліномів 1 та 6 степенів було витрачено близько півроку і працювали 80 процесорів. На головний етап просіювання було потрачено близько двох років і використано сотні комп’ютерів різної потужності. Якби цю задачу розв’язували на одному процесорі AMD Optron 2.2 ГГц, то потрібно було б 1500 років його роботи. На третьому етапі обробка даних із розв’язанням задачі лінійної алгебри тривала декілька тижнів. Знаходження нетривіальних рішень здійснювалося на декількох незалежних кластерах протягом понад три місяці. Обсяг прорідженої матриці складав 192 796 550×192 795 550 елементів, причому ненульових було 27 795 115 920 елементів. Для зберігання матриці на жорсткому диску знадобилося близько 105 гігабайтів та близько 5 терабайтів для зберігання стиснутих даних при побудуванні такої матриці.

Таблиця 9.3

Прогрес у розв’язку задач факторизації модуля N

Для розкладання на множники до 1994 року застосовувався підхід, відомий як метод квадратичного решета. Для криптоаналізу RSA-130, RSA-140, RSA-155, RSA-160, RSA-174 використовувався новий алгоритм, названий методом решета в полі чисел загального вигляду, що дозволило скоротити обсяг обчислювальних зусиль майже на 10% у порівнянні з тими, що були потрібні раніше для аналізу RSA-129. Як випливає із табл. 9.3, новими успіхами факторизації стали модулі RSA-199 (663 бітів) та RSA-232 (768 бітів) [423]. Задачі факторизації RSA від RSA-270 (896 бітів) до RSA-617 (2048 бітів) залишаються відкритими, з нагородами відповідно від $ 20000 до $ 200000 [423].

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

Читайте також:

1. Апаратура і методика проведення густинного гамма-гамма-каротажу
2. Апаратура і методика проведення густинного гамма-гамма-каротажу
3. Апаратура та методика проведення газометрії свердловин в процесі буріння
4. Види вправ з лексики й методика їх проведення
5. Види та жанри образотворчого мистецтва, методика ознайомлення з ними у початковій школі.
6. Геофізичний контроль за розробкою нафтових і газових родовищ. Задачі. Методи і методика дослідження
7. Гідродинамічні аварії. Методика оцінки інженерного cтану при них і заходи захисту населення та території
8. Доходи підприємства та методика їх обчислення
9. Етапи контролю та методика їхнього здійснення. 1 страница
10. Етапи контролю та методика їхнього здійснення. 1 страница
11. Етапи контролю та методика їхнього здійснення. 2 страница
12. Етапи контролю та методика їхнього здійснення. 2 страница

Переглядів: 934