Современные информационные технологии/4.Информационная безопасность.

Пархоменко І.І., к.т.н., Столяр Д. В.

Національний авіаційний університет, Україна.

ЗАХИСТ ТЕКСТОВИХ ПОВІДОМЛЕНЬ ПІД ЧАС ОБМІНУ НА ОСНОВІ КРИПТОСИСТЕМИ RSA

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

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

Одним з таких алгоритмів є криптосистема RSA. Вона є найпершою криптографічною системою з відкритим ключем серед тих, що були запропоновані у відкритій літературі загалом.

Вперше опис RSA було опубліковано у 1977 році Рональдом Райвестом, Аді Шаміром і Леонардом Адлеманом з Масачусетського Технологічного Інституту (MIT), які є основоположниками даного алгоритму[7].

Висвітлення теоретичних аспектів з даної теми знаходимо у працях науковців кінця ХХ – початку ХХІ століть. Серед них виділяємо напрацювання Ж. Брассара [1], С. Коутинхо [3], Ж. Земора [2], С. Яна [4], В. Ященка [5] та інших. На сучасному етапі алгоритм RSA широко використовується на практиці у програмах, які виконують передачу даних по незахищеному каналу.

Метою даної статті є розгляд криптосистеми RSA, а саме опис та аналіз системи захисту текстових повідомлень під час обміну.

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

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

Для генерації пари ключів беруться два великих випадкових простих числа p та q. З метою максимальної крипостійкості p і q вибираються рівної довжини. Потім обчислюється їх добуток n = p*q (n називається модулем). Далі випадковим чином вибирається число e (ключ шифрування), що задовольняє умові: 1 <e <(p - 1) * (q - 1) і не має спільних дільників окрім 1 (взаємно просте) з числом φ(n)=(p-1)*(q-1).

Нарешті розширений алгоритм Евкліда використовується для обчислення ключа дешифрування d, такого, що ed = 1 mod φ(n) [8]. Число d таке, що (ed - 1) ділиться на (p - 1) (q-1).

Для шифрування повідомлення m необхідно виконати його розбивку на блоки, кожний з яких менше n (для двійкових даних вибирається найбільша ступінь числа 2, менша n).

Шифрування зводитися до обчислення : c_i=m_i^e mod n.

При дешифруванні для кожного зашифрованого блоку c_i обчислюється m_i = c_i^d mod n.

Останнє справедливо, так як c_i^d = (m_i^e)^d = m_i^ed = m_i^kφ(n)+1 = m_i*1 = m_i.

Всі обчислення виконуються за mod n. Повідомлення може бути зашифроване за допомогою d, а дешифровано за допомогою e.

Передбачається, що криптостійкість RSA залежить від проблеми розкладання на множники великих чисел. Проте ніколи не було доведено математично, що потрібно n розкласти на множники, щоб відновити m по с та e. Не виключено, що може бути відкритий зовсім інший спосіб криптоаналізу RSA. Однак, якщо цей новий спосіб дозволить криптоаналітику отримати d, він також може бути використаний для розкладання на множники великих чисел. Також можна атакувати RSA, вгадавши значення (p-1) (q-1). Однак цей метод не простіше розкладання n на множники. При використанні RSA розкриття навіть кількох бітів інформації з шифротексту не легше, ніж дешифрування всього повідомлення. Самою очевидною атакою на RSA є розкладання n на множники. Будь-який супротивник зможе отримати відкритий ключ e та модуль n. Щоб знайти ключ дешифрування d, супротивник повинен розкласти n на множники. Криптоаналітик може перебирати всі можливі d, поки не підбере правильне значення. Але подібна силова атака навіть менш ефективна, ніж спроба розкладання n на множники. У 1993 р. був запропонований метод криптоаналізу, заснований на малій теоремі Ферма. На жаль, цей метод виявився повільнішим за розкладання на множники. Існує ще одна проблема. Більшість загальноприйнятих тестів встановлює простоту числа з певною ймовірністю. Що станеться якщо p або q виявиться складовим? Тоді у модуля n буде три або більше дільників. Відповідно деякі дільники будуть менше рекомендованої величини, що, у свою чергу відкриває можливості для атаки шляхом факторизації модуля. Інша небезпека полягає в генерації псевдопростих чисел (чисел Кармайкла), що задовольняють тестам на простоту, але при цьому не є простими. Однак імовірність генерації таких чисел дуже мала. На практиці, послідовно застосовуючи набір різних тестів на простоту, можна звести ймовірність генерації складеного числа до необхідного мінімуму.

Розглянемо роботу алгоритму RSA на конкретному прикладі. Вибираємо два прості числа p = 7; q = 17 (на практиці ці числа у багато разів довше). У цьому випадку n = p * q дорівнюватиме 119. Тепер необхідно вибрати e, вибираємо e = 5. Наступний крок пов'язаний з формуванням числа d так, щоб d * e = 1 mod [(p-1) (q-1)]. d = 77 (використаний розширений алгоритм Евкліда) [8]. d - секретний ключ, а e і n характеризують відкритий ключ. Нехай текст, який нам потрібно зашифрувати представляється M = “RSA”. Цей текст представляємо у вигляді масиву чисел які отримуємо з початкового тексту, застосувавши таблицю ASCII. Отримаємо масив M={82, 83, 65}. С_i=M_i^e mod n. Масив зашифрованого тесту матиме наступний вигляд C={80, 104, 46}. Перетворивши за таблицею ASCII цей масив отримаємо C=”Ph.”. Цей "текст" може бути посланий відповідному адресату. Одержувачу для дешифрування отриманого повідомлення потрібно знову перетворити повідомлення в масив і використати М_i = C_i^d mod n. У результаті виходить M = {82, 83, 65}.

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

Список літературних джерел

1. Брассар Ж. Современная криптология. Руководство / Ж. Брассар. – М.: Полимед, 1999. – 176 с.

2. Земор Ж. Курс криптографии / Ж. Земор. – Ижевск: РХД, 2006. – 256 с.

3. Коутинхо С. Введение в теорию чисел. Алгоритм RSA / С. Коутинхо. – М.: Постмаркет, 2001. – 328 с.

4. Ян С. Криптоанализ RSA / С. Ян. – Ижевск: РХД, 2011. – 312 с.

5. Ященко В. В. Введение в криптографію / В. В. Ященко. – М.: МЦНМО, 2012. – 348 с.

6. Gardner, M., “A new kind of cipher the would take millions of years to breake”, Scientific American, August 1977, pp 120-124.

7. Rivest, R., Shamir, A., Adleman, L. "A Method for Obtaining Digital Signatures and Public-Key Cryptosystems", Communications of the ACM, vol. 21, 1978, pp. 120–126.

8. Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, Second Edition. MIT Press and McGraw-Hill, 2001. ISBN 0-262-03293-7. Pages 859—861 of section 31.2: Greatest common divisor