Лекція №18. МЕХАНІЗМИ ЗАХИСТУ ІНФОРМАЦІЇ ВІД НСД. Вступ до криптології

План

1. Основні кроки виконання методу RSA.

2. Актуальність проблеми використання криптографічних методів в інформаційних системах.

3. Криптографія.

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

5. Основні напрямки використання криптографічних методів.

6. Основні розділи сучасної криптографії.

Відкритий ключ k_e вибирають випадковим чином так, щоб виконувалися умови

1<k_e£φ(Ν), НЗД(k_e,φ(Ν))=1,

φ(N)=(P-1)(Q-1),

де φ(Ν) – функція Эйлера.

Функція Эйлера φ(Ν) указує кількість позитивних цілих чисел в інтервалі від 1 до Ν, що взаємно прості з N.

Друга з зазначених вище умов означає, що відкритий ключ k_e і функція Эйлера φ(Ν) повинні бути взаємно простими. Далі, використовуючи розширений алгоритм Евкліда, обчислюють секретний ключ k_d, такий, що

k_ek_d=1 mod φ(Ν)

або k_d=k_e^-1 mod ((P-1)(Q-1)).

Це можна здійснити, тому що одержувач знає пару простих чисел (P,Q) і може легко знайти φ(Ν). Помітимо, що k_e і N повинні бути взаємно простими.

Відкритий ключ k_e використовують для шифрування даних, а секретний ключ k_d – для розшифрування.

Перетворення шифрування визначає криптограму С через пару (відкритий ключ k_e, повідомлення М) у відповідності з наступною формулою

C=E_k(M)=M^k_e mod N.

Як алгоритм швидкого обчислення значення використовують ряд послідовних зведень у квадрат цілого Μ і множень на Μ з приведенням за модулем N.

Обертання функції C=M^k_e mod N, тобто визначення значення Μ за відомим значенням С, k_e і Ν, практично не здійсненно при Ν@2⁵¹².

Однак зворотну задачу, тобто задачу розшифрування криптограми С, можна вирішити, використовуючи пару (секретний ключ k_d, криптограма С) за наступною формулою

Μ=D_k(C)=C^k_d mod N.

Процес розшифрування можна записати так

D_k(E_k(M))=M.

Таким чином, одержувач, що створює криптосистему, захищає два параметри: 1) секретний ключ k_d і 2) пару чисел (P,Q), добуток яких дає значення модуля N. З іншого боку, одержувач відкриває значення модуля N і відкритий ключ k_e.

Супротивникові відомі лише значення k_e і N. Якби він зміг розкласти число N на множники Ρ і Q, то він довідався б “потайний хід” – трійку чисел {Р,Q,k_d}, обчислив значення функції Эйлера φ(N)=(P-1)(Q-1) і визначив значення секретного ключа k_d.

Однак, як уже відзначалося, розкладання дуже великого N на множники обчислювально не здійсненно (за умови, що довжини обраних Ρ і Q складають не менш 100 десяткових знаків).

Розглянемо процедури шифрування і розшифрування в криптосистемі RSA.

Припустимо, що користувач А хоче передати користувачеві В повідомлення в зашифрованому виді, використовуючи криптосистему RSA. У такому випадку користувач А виступає в ролі відправника повідомлення, а користувач В – у ролі одержувача. Розглянемо послідовність дій користувача В и користувача А.

1. Користувач В вибирає два довільних великих простих числа Р і Q.

2. Користувач В обчислює значення модуля Ν=Ρ*Q.

3. Користувач В обчислює функцію Эйлера φ(N)=(P-1)(Q-1) і вибирає випадковим чином значення відкритого ключа k_e з урахуванням виконання умов 1<k_e£φ(Ν), НЗД(k_e,φ(Ν))=1.

4. Користувач В обчислює значення секретного ключа k_d, використовуючи розширений алгоритм Евкліда при рішенні порівняння k_ek_d=1 mod φ(Ν).

5. Користувач В пересилає користувачеві А пару чисел (N,k_e) по незахищеному каналі.

Якщо користувач А хоче передати користувачеві В повідомлення М, він виконує наступні кроки.

6. Користувач А розбиває вихідний відкритий текст Μ на блоки, кожний з яких може бути представлений у виді числа M_i=0,1,2,...,Ν-1.

7. Користувач А шифрує текст, представлений у виді послідовності чисел М_i, за формулою C_i=E_k(M_i)=M^k_ie mod N і відправляє криптограму С₁, С₂, ..., C_n користувачеві В.

8. Користувач В розшифровує прийняту криптограму С₁, С₂, ..., C_n.

використовуючи секретний ключ k_d, по формулі Μ_i=D_k(C_i)=C^k_id mod N.

У результаті буде отримана послідовність чисел М_i, що являють собою вихідне повідомлення М. Щоб алгоритм RSA мав практичну цінність, необхідно мати можливість без істотних витрат генерувати великі прості числа, вміти оперативно обчислювати значення ключів k_e і k_d.

Для прикладу зашифруємо повідомлення «САВ». Для простоти будемо використовувати маленькі числа (на практиці застосовуються набагато більші).

1. Виберемо P=3 і Q=11.

2. Визначимо N=3*11=33.

3. Знайдемо (P-1)(Q-1)=20. Отже, у якості k_d візьмемо взаємно просте з 20, наприклад, k_d=3.

4. Виберемо число k_e. Як таке число може бути узяте будь-яке число, для якого задовольняється співвідношення (k_e*3) (mod 20) = 1, наприклад, 7.

5. Представимо повідомлення, яке потрібно шифрувати, як послідовність цілих чисел за допомогою відображення: А®1, В®2, С®3. Тоді повідомлення приймає вид (3,1,2). Зашифруємо повідомлення за допомогою ключа {k_e,N}={7,33}.

ШТ1 = (3⁷) (mod 33) = 2187 (mod 33) = 9,

ШТ2 = (1⁷) (mod 33) = 1 (mod 33) = 1,

ШТ3 = (2⁷) (mod 33) = 128 (mod 33) = 29.

6. Розшифруємо отримане зашифроване повідомлення (9,1,29) на основі закритого ключа {k_d,N}={3,33}. Отримаємо вихідний текст:

ВТ1 = (9³) (mod 33) = 729 (mod 33) = 3,

ВТ2= (1³) (mod 33) = 1 (mod 33) = 1,

ВТ3 = (29³) (mod 33) = 24389 (mod 33) = 2.

Отже, у реальних системах алгоритм RSA реалізується в такий спосіб: кожен користувач вибирає два великих простих числа, і відповідно до описаного вище алгоритмом вибирає два простих числа k_e і k_d. Як результат множення перших двох чисел (P і Q) установлюється N.

Пара {k_e,N} утворить відкритий ключ, а {k_d,N} – закритий (хоча можна взяти і навпаки).

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

Безпека алгоритму RSA базується на труднощі вирішення задачі факторизації великих чисел, що є добутками двох великих простих чисел. Дійсно, криптостійкість алгоритму RSA визначається тим, що після формування секретного ключа k_d і відкритого ключа k_e «стираються» значення простих чисел Ρ і Q, і тоді винятково важко визначити секретний ключ k_d по відкритому ключі k_e, оскільки для цього необхідно вирішити задачу перебування дільників Ρ і Q модуля N. Розкладання величини N на прості множники Ρ і Q дозволяє обчислити функцію φ(Ν)=(Ρ-1)(Q-1) і потім визначити секретне значення k_d.

Задача факторизації є важко розв'язною задачею для великих значень модуля N. Спочатку автори алгоритму RSA пропонували для обчислення модуля N вибирати прості числа Р і Q випадковим чином, по 50 десяткових розрядів кожне. Вважалося, що такі великі числа N дуже важко розкласти на прості множники. Один з авторів алгоритму RSA, Р.Райвест, думав, що розкладання на прості множники числа з майже 130 десяткових цифр, приведеного в їхній публікації, вимагатиме більш 40 квадрильйонів років машинного часу. Однак цей прогноз не виправдався через порівняно швидкий прогрес комп'ютерів і їхньої обчислювальної потужності, а також поліпшення алгоритмів факторизації.

У 1994 році було факторизовано число з 129 десятковими цифрами. Це удалося здійснити математикам А.Ленстра і М.Манассі за допомогою організації розподілених обчислень на 1600 комп'ютерах, об'єднаних мережею, протягом восьми місяців. На думку А.Ленстра і М.Манассі, їхня робота компрометує криптосистеми RSA і створює велику загрозу їх подальшим застосуванням. Тепер розроблювачам криптоалгоритмів з відкритим ключем на базі RSA приходиться уникати застосування чисел довжиною менш 200 десяткових розрядів. Самі останні публікації пропонують застосовувати для цього числа довжиною не менш 250-300 десяткових розрядів.

Криптосистеми RSA реалізуються як апаратним, так і програмним шляхом.

Для апаратної реалізації операцій зашифрування і розшифрування RSA розроблені спеціальні процесори. Ці процесори, реалізовані на зверхвеликих інтегральних схемах, дозволяють виконувати операції RSA, зв'язані зі зведенням великих чисел у колосально великий ступінь за модулем N, за відносно короткий час. І все-таки апаратна реалізація RSA приблизно в 1000 разів повільніше апаратної реалізації симетричного криптоалгоритму DES.

Програмна реалізація RSA приблизно в 100 разів повільніше програмної реалізації DES. З розвитком технології ці оцінки можуть трохи змінюватися, але асиметрична криптосистема RSA ніколи не досягне швидкодії симетричних криптосистем.

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

Можливість гарантовано оцінити захищеність алгоритму RSA стала однієї з причин популярності цієї СВК на тлі десятків інших схем. Тому алгоритм RSA використовується в банківських комп'ютерних мережах, особливо для роботи з видаленими клієнтами (обслуговування кредитних карток).

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

Додамо декілька слів про найбільш відомі інші алгоритми шифрування. Стандарт шифрування даних DES (Data Encryption Standard) опублікований у 1977 р. Національним бюро стандартів США. Стандарт DES призначений для захисту від несанкціонованого доступу до важливого, але несекретної інформації в державних і комерційних організаціях США. Алгоритм, покладений в основу стандарту, поширювався досить швидко, і вже в 1980 році був схвалений Національним інститутом стандартів і технологій США (NIST). З цього моменту DES перетворюється в стандарт не тільки за назвою (Data Encryption Standard) але і фактично. З'являються програмне забезпечення і спеціалізовані мікроеом, призначені для шифрування і розшифрування інформації в мережах передачі даних.

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

•використовується тільки один ключ довжиною 56 біт;

•зашифрувавши повідомлення за допомогою одного пакета програм, для розшифровки можна використовувати будь-який інший пакет програм, що відповідає стандартові DES;

•відносна простота алгоритму забезпечує високу швидкість обробки;

•досить висока стійкість алгоритму.

Спочатку метод, що лежить в основі стандарту DES, був розроблений фірмою IBM для своїх цілей і реалізований у виді системи «Люцифер». Система «Люцифер» заснована на комбінуванні методів підстановки і перестановки і складається з послідовності блоків, що чергується, перестановки і підстановки. У ній використовувався ключ довжиною 128 біт, що керував станами блоків перестановки і підстановки. Система «Люцифер» виявилася досить складною для практичної реалізації через відносно малу швидкість шифрування (2190 байт програмна реалізація, 96970 байт/с – апаратна реалізація).

В даний час блоковий алгоритм DES вважається відносно безпечним алгоритмом шифрування. Він піддавався ретельному криптоаналізу протягом 20 років, і самим практичним способом його виламування є метод перебору всіх можливих варіантів ключа. Ключ DES має довжину 56 біт, тому існує 2⁵⁶ можливих варіантів такого ключа. Якщо припустити, що суперкомп'ютер може випробувати мільйон варіантів ключа за секунду, то буде потрібно 2285 років для перебування правильного ключа. Якби ключ мав довжину 128 біт, то треба було б 10²⁵ років (для порівняння: вік Всесвіту близько 10¹⁰ pоків).

У Росії встановлений єдиний алгоритм криптографічного перетворення даних для систем обробки інформації в мережах ЕОМ, окремих обчислювальних комплексах і ЕОМ, що визначається ДСТ 28147-89. Стандарт обов'язковий для організацій, підприємств і установ, що застосовують криптографічний захист даних, збережених і переданих у мережах ЕОМ, в окремих обчислювальних комплексах і ЕОМ.

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

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

Контрольні запитання

1. Наведіть основні кроки виконання методу RSA.

2. Чому проблема використання криптографічних методів в інформаційних системах стала особливо актуальною?

3. Що таке криптографія?

4. Що таке криптоаналіз?

5. Визначте основні напрямки використання криптографічних методів.

6. Основні розділи сучасної криптографії.