Вибір параметрів шифру RSA і можливі наслідки

Під катом описані приклади вибору «поганих» парметров шифру RSA.
 
Процитуємо авторів навчального посібника «Основи криптографії» А.П. Алфьоров, А.Ю. Зубов, А.С. Кузьмін, А.В. Черьомушкін, Москва. «Геліос АРВ», 2001р., На сторінці 316:
 
«Слід підкреслити необхідність дотримання обережності у виборі модуля RSA (числа n ) для кожного з кореспондентів мережі. У зв'язку з цим можна сказати наступне. Читач може самостійно переконатися в тому, що знаючи одну з трьох величин p , q або φ (n) , можна легко знайти секретний ключ RSA… ».
 
Доповнимо цей текст. При невдалому виборі модуля шифру RSA, як це зроблено в прикладі посібники, що наводиться нижче, можна дешифрувати текст і без наявності секретного ключа, тобто не знаючи жодної з трьох названих величин.
 
Для цього достатньо розташовувати зашифрованим текстом, заданих модулем шифру n , відкритим ключем е шифру і виконати всього три кроки атаки «Безключове читання». Після четвертого атакуючого кроку встановлюється, що на попередньому кроці був отриманий вихідний текст, він може бути прочитаний. Покажемо, наскільки просто це робиться.
 
Спочатку наведемо сам приклад зі стор 313-315 з названого посібники.
 <habracut/>
 Приклад
 Шифрування короткого початкового текстового повідомлення: RSA .
Одержувач встановлює шифр з характеристиками n = pq = 527 , де р = 17 , q = 31 і φ (n) = (р -1) (q — 1) = 480 . В якості відкритого ключа е вибрано число, взаємно просте з φ (n) , е = 7 . Для цього числа за допомогою розширеного алгоритму Евкліда знайдені цілі числа u і v , що задовольняють співвідношенню е ∙ u + φ (n) ∙ v = 1 :
 
 480 = 7 ∙ 68 +4,
7 = 4 ∙ 1 +3,
4 = 3 ∙ 1 +1,
1 = 4-3 ∙ 1 = 4 — (7-4 ∙ 1) ∙ 1 = 4 ∙ 2-7 ∙ 1 = (480-7 ∙ 68) ∙ 2-7 ∙ 1 = 480 ∙ 2-7 ∙ 137,
v = 2, u = -137
.
 
Оскільки -137 ≡ 343 (mod480) , то d = 343 .
 
Перевірка: 7 ∙ 343 = 2401 ≡ 1 (mod480) .
 
Текстове повідомлення представляється у вигляді послідовності чисел, що містяться в інтервалі [0, 526] . Для цього літери R , S і A кодуються пятіразрядний двійковими числами. Використовуються порядкові номери цих букв в англійському алфавіті при їх двійковому поданні:
 
 R = 18 10 = (10010) 2 , S = 19 10 = (10011) 2 , A = 1 10 = (00001) 2 .
 
Тоді RSA = (100101001100001) 2 . Розбиття тексту на блоки обмеженої довжини дає уявлення з двох блоків: RSA = (100101001), (100 001) = (М 1 = 297, М 2 = 33) .
 
Послідовно шифруються блоки вихідного тексту М 1 = 297 , М 2 = 33 :
 y 1 = Е k 1 ) = М 1 e ≡ 297 7 (mod527) = 474 .
 
Тут скористалися тим, що:
 
 297 7 = ((297 2 ) 3 ) 297 ≡ (mod527) = (200 3 (mod527) 297) (mod527) = 474 ,
 y 2 = Е k 2 ) = M 2 e ≡ 33 7 (mod527) = 407 .
 
Шифрований текст, як і вихідний, отримуємо у вигляді двох блоків: у 1 = 474 ; у 2 = 407 .
 
 Розшифрування представляється послідовністю дій D k (y i ) = (y i ) d = (y i ) 343 (mod 527) , i = 1,2 .
 
Обчислення зведення в ступінь d більш зручно проводити, попередньо представляючи показник ступеня сумою ступенів числа 2 , а саме: 343 = 256 +64 +16 +4 +2 +1 .
 
Використовуючи це подання показника ступеня d = 343 , отримуємо:
 
 474 2 ≡ 174 (mod527),
474 4 ≡ 237 (mod527),
474 8 ≡ 307 (mod527),
474 16 ≡ 443 (mod527),
474 32 ≡ 205 (mod527),
474 64 ≡ 392 (mod527),
474 128 ≡ 307 (mod527),
474 256 ≡ 443 (mod527),

і остаточно 474 343 (mod527) = (443 ∙ 392 ∙ 443 ∙ 237 ∙ 174 ∙ 474) (mod527) = 297 .
 
Аналогічно обчислюється значення 407 343 (mod527) = 33 .
 
Перехід до буквеного поданням розшифрованого повідомлення дає: RSA .
 
Після розгляду прикладу в посібнику наводяться міркування про стійкість системи RSA. Підкреслюється необхідність дотримання обережності у виборі модуля шифру RSA (числа n ) для кожного з кореспондентів мережі. Вказується на неприпустимість ігнорування вимог до вибираним характеристикам системи шифрування. Серед таких вимог, на жаль, не вказано то, порушення якого ілюструє наведений приклад.
 
 Атака на шифр RSA
Розглянемо приклад атаки на шифр RSA. Скористаємося даними прикладу, наведеного на сторінці 313-315 в навчальному посібнику «Основи криптографії» А.П. Алфьоров, А.Ю. Зубов, А.С. Кузьмін, А.В. Черьомушкін, Москва. «Геліос АРВ», 2001.
 
Невдалість (неприпустимість) обраних параметрів системи в цьому прикладі легко показується обчисленнями, що реалізовують атаку Безключове читання вихідного тексту. Сутність такої атаки полягає в наступному. Задані відкритий ключ шифру RSA (е = 7 , n = 527 ) і шифрований текст. У прикладі шифрований текст представлений двома блоками у = (у 1 = 474, у 2 = 407) .
 
Кожен шифрований блок атакується індивідуально, спочатку атакуємо у 1 = 474 , після його дешифрування, атакуємо другий блок у 2 = 407 .
 
Далі формується шляхом багаторазового зашифрування із збереженням результатів двох послідовних кроків алгоритму атаки та з використанням відкритого ключа послідовність числових значень у i , у 1 = у наявний шифрований текст.
 
В алгоритмі атаки на шифрований текст визначається такий номер кроку j , для якого y i e j (mod n) = (y i e j-1 (mod n)) e (mod n) = y i , i> 1 . З останнього співвідношення бачимо, що при зведенні в ступінь е значення (y i e j-1 (mod n)) виходить початковий шіфoртекст y i = у 1 .
 
Але це і означає, що на цьому кроці шифрувався відкритий текст. Безпосередніми обчисленнями (їх виявляється зовсім небагато) з використанням екранного калькулятора знаходимо те значення j , при якому цикл шифрування завершується значенням y 1 , з якого цикл і був розпочатий.
 
 Атака на перший блок у 1 = 474 шифртекста.
 Крок 1 : 474 7 (mod527) = 382 ;
 Крок 2 : 382 7 (mod527) = 423 ;
 Крок 3 : 423 7 (mod527) = 297 ;
 Крок 4 : на цьому кроці шифрується вже знайдений вихідний текст, але його необхідно виконати, так як атакуючий вихідного тексту не знає. Ознакою завершення атаки є збіг початкового значення шифртекста (474 ) і результату 4-го кроку зашифрування. Саме такий збіг і має місце.
 
 297 7 (mod527) = 474 отримали початковий (перший) блок шифртекста. Атака на перший блок завершена успішно у 1 = 474 . Попередній результат кроку 3 дорівнює відкритому тексту М 1 = 297 .
 
По суті в кільці лишків за модулем n = 527 реалізувався короткий цикл обробки вирахування r = 297 по модулю n = 527 . Це записується так y i = у 1 = 297 . Формуємо статечні відрахування (((297 7 (mod527)) 7 (mod527)) 7 (mod527)) 7 = 297 .
 
 Атака на другий блок у 2 = 407 шифртекста.
 Крок 1 : 407 7 (mod527) = 16 ;
 Крок 2 : 16 7 (mod527) = 101 ;
 Крок 3 : 101 7 (mod527) = 33 ;
 Крок 4 : 33 7 (mod527) = 407 .
 
Знову на третьому кроці отримано блок вихідного тексту (М 2 = 33 ), але атакуючому це невідомо, і він виконує наступний (четвертий крок), результат якого (407 ) збігається з початковим Шифртекст у 2 = 407 .
 
По суті в кільці лишків за модулем n = 527 реалізувався короткий цикл обробки вирахування r = 33 по модулю n = 527 . Це записується так y i = у 2 = 33 . Формуємо статечні відрахування ((33 7 (mod527)) 7 (mod527)) 7 (mod527) = 33 .
 
Результат атаки (вихідний текст М 1 = 297 , М 2 = 33 ) отриманий триразовим шифруванням заданого шифртекста. Більший успіх для атакуючого шифртекст важко уявити.
 
Продовжуючи обговорення питання про вибір модуля та інших параметрів шифру, можна додати, що модуль шифру (n = 527 ) деякі вихідні тексти взагалі не дозволяє шифрувати. При цьому вибір значення відкритого ключа е великої ролі не грає. Існують значення вихідних текстів, які взагалі неможливо зашифрувати обраним шифром з модулем n = 527 .
 
Ні на одному із заданих е не вдається зашифрувати вихідні тексти, подаються числами 187 , 341 , 154 і 373 .
 
 Приклад (неможливість шифрування значень деяких вихідних текстів)
Нехай вихідні тексти представлені чотирма блоками y = (y 1 = 154, y 2 = 187, y 3 = 341, y 4 = 373) . Експонента е відкритого ключа шифру може бути будь-яким взаємно простим числом з функцією Ейлера φ (n) = φ (527) = 480 . Втім, для розглянутого випадку відкритий ключ е може бути заданий довільно. Дійсно, нехай е = 2, 4, 7, 9, 17, 111 тоді:
 
 154 2 (mod527) = 1 ;
 154 4 (mod527) = 1 ;
 154 7 (mod527) = 154 ;
 154 9 (mod527) = 154 ;
 154 17 (mod527) = 154 ;
 154 111 (mod527) = 154 ;
 187 2 (mod527) = 187 ;
 187 4 (mod527) = 187 ;
 187 7 (mod527) = 187 ;
 187 9 (mod527) = 187 ;
 187 17 (mod527) = 187 ;
 187 111 (mod527) = 187 ;
 341 2 (mod527) = 341 ;
 341 4 (mod527) = 1 ;
 341 7 (mod527) = 341 ;
 341 9 (mod527) = 341 ;
 341 17 (mod527) = 341 ;
 341 111 (mod527) = 341 ;
 373 2 (mod527) = 1 ;
 373 4 (mod527) = 373 ;
 373 7 (mod527) = 373 ;
 373 9 (mod527) = 373 ;
 373 17 (mod527) = 373 ;
 373 111 (mod527) = 373 .
 
З розглянутого прикладу випливає простий висновок. Дійсно, до вибору параметрів процесу шифрування треба підходити дуже уважно і проводити ретельний попередній аналіз таких параметрів. Як це робити — окреме питання, і в рамках цієї роботи він не розглядається.

Джерело: Хабрахабр

0 коментарів

Тільки зареєстровані та авторизовані користувачі можуть залишати коментарі.