Файл: Опорный конспект.pdf

Асиметричні криптосистеми

План

1 Концепція криптосистеми з відкритим ключем

2 Односпрямовані функції

3 Криптосистема шифрування даних RSA

4 Схема шифрування Поліга - Хеллмана

5 Алгоритм шифрування Ель Гамаля

6 Схема шифрування Рабіна

35

1 Концепція криптосистеми з відкритим ключем

Ефективними системами криптографічного захисту даних є асиметричні криптосистеми, які називають також криптосистемами з відкритим ключем. У

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

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

Узагальнена схема криптосистеми з відкритим ключем показана на рисунку 1. В цій криптосистемі застосовують два різних ключі: K A – відкритий ключ

відправника A; K B – таємний ключ одержувача В.

Генератор ключів доцільно розташовувати на стороні одержувача B, щоб не пересилати таємний ключ K A незахищеним каналом. Значення ключів K A і K B

залежать від початкового стану генератора ключів.

Розкриття таємного ключа K B за значенням відомого відкритого ключа K A

повинно бути обчислювально нерозв’язаною задачею.

відкритими.

Захист інформації в асиметричній криптосистемі засновано на таємності ключа

K B .

У.Діффі та М.Хеллман сформулювали вимоги, які забезпечують безпеку асиметричної криптосистеми:

1 Обчислення пари ключів ( K A , K B ) одержувачем B на основі початкової

умови повинно бути простим.

2 Відправник A, знаючи відкритий ключ K A і повідомлення М, може легко

обчислити криптограму

3 Одержувач В, використовуючи таємний ключ K B і криптограму C, може

легко відновити вихідне повідомлення

36

4Зловмисник, знаючи відкритий ключ K A , при спробі обчислити таємний ключ K B натрапляє на непереборну обчислювальну проблему.

5Зловмисник, знаючи пари ( K A , C), при спробі обчислити вихідне

повідомлення M натрапляє на непереборну обчислювальну проблему.

2 Односпрямовані функції

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

Нехай Х і Y – деякі довільні множини. Функція f : X Y є односпрямованою, якщо для всіх x X можна легко обчислити функцію y f (x), y Y , але для більшості y Y досить складно одержати значення x X , таке, що f (x) y (при цьому вважають, що існує принаймні одне таке значення x ).

Основним критерієм віднесення функції f до класу односпрямованих функцій є

відсутність ефективних алгоритмів зворотного перетворення Y X .

Як приклад односпрямованої функції розглянемо множення цілих чисел. Пряма задача – обчислення добутку двох дуже великих цілих чисел P й Q , тобто

знаходження значення

є простою задачею для ЕОМ.

Зворотна задача – розкладання на множники великого цілого числа, тобто знаходження дільників P і Q великого цілого числа N P * Q , є практично

нерозв’язною задачею при досить великих значеннях N .

За сучасними оцінками теорії чисел при цілому N 2664 й P Q для розкладання числа N буде потрібно близько 1023 операцій, тобто задача практично

де x – ціле число, 1 x N 1.

Існують ефективні алгоритми, що дозволяють досить швидко обчислити значення функції f A, N (x) .

Якщо y Ax , то, природно, x log A ( y) .

Тому, задачу обернення функції f A, N (x) називають задачею знаходження

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

Задача дискретного логарифмування формулюється в такий спосіб. Для відомих цілих A, N , y знайти ціле число x , таке, що

Ax (mod N) y .

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

37

За сучасними оцінками теорії чисел при досить великих цілих числах A 2664 й N 2664 рішення задачі дискретного логарифмування (знаходження показника ступеня x для відомого y ) потребує близько 1026 операцій, тобто ця задача має в

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

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

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

Функція f : X Y належить до класу односпрямованих функцій з "потаємним

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

Як приклад односпрямованої функції з "потаємним ходом" можна вказати модульну експоненту з фіксованими модулем і показником ступеня, що використовується в криптосистемі RSA. Змінна основа модульної експоненти використовується для вказівки числового значення повідомлення М або криптограми С.

3 Криптосистема шифрування даних RSA

Алгоритм RSA запропонували в 1978 р. Р.Райвест (Rivest), А.Шамір (Shamir) і А.Адлеман (Adleman). Алгоритм одержав свою назву від перших букв прізвищ його авторів. Алгоритм RSA став першим повноцінним алгоритмом з відкритим ключем, що може працювати як у режимі шифрування даних, так і у режимі електронного цифрового підпису.

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

Тут P й Q – випадкові великі прості числа. Для забезпечення максимальної безпеки вибирають P і Q однакової довжини й зберігають у секреті. Множина Z N з операціями додавання та множення за модулем N утворює

арифметику за модулем N .

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

38

Далі, використовуючи розширений алгоритм Евкліда, обчислюють таємний ключ K B , такий, що

Це можна здійснити, тому що одержувач B знає пару простих чисел P, Q і може

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

для розшифрування.

Процес зашифрування визначає криптограму C через пару ( K A , М) у відповідності

до формули (4.9).

Однак обернену задачу, тобто задачу розшифрування криптограми C, можна вирішити, використовуючи пару ( K B , C ) за формулою (4.10).

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

K A * KB n * (N) 1

або, що те саме,

K A * KB 1mod (N) .

Саме тому для обчислення таємного ключа K B використовують співвідношення

(4.8).

Таким чином, якщо криптограму

C M K A mod N

піднести до степеня K B , то в результаті відновлюється вихідний відкритий текст

М, тому що

(M K A )KB M K AKB M n* ( N ) 1 M mod N .

Отже, одержувач B, що створює криптосистему, захищає два параметри: таємний ключ K B і пару чисел P, Q , добуток яких дає значення модуля N. З

іншого боку, одержувач B відкриває значення модуля N і відкритий ключ K A . Зловмиснику відомі лише значення K A та N. Якби він зміг розкласти число N на множники P й Q, то він довідався б "потаємний хід" – трійку чисел {P,Q, K A} , обчислив значення функції Ейлера (N ) та визначив значення таємного ключа

K B .

39

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

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

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

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

2Користувач B обчислює значення модуля N згідно з (4.5).

3Користувач B обчислює функцію Ейлера (N ) й вибирає значення відкритого ключа K A з урахуванням виконання умов (4.6) і (4.7).

4Користувач B обчислює значення таємного ключа K B за формулою (4.8), використовуючи розширений алгоритм Евкліда.

5Користувач B пересилає незахищеним каналом користувачу A пару чисел (N, K A ).

Якщо користувач A має бажання передати користувачу B повідомлення М, він виконує такі

кроки.

6.Користувач A розбиває вихідний відкритий текст М на блоки, кожний з яких може бути поданий у вигляді числа M i , 0 M i N 1.

7.Користувач A шифрує текст, поданий у вигляді послідовності чисел М, за формулою

Ci M iK A mod N

і відправляє користувачеві В криптограму

C1 , C2 , C3 , ,Ci , .

8.Користувач B розшифровує прийняту криптограму C1 , C2 , C3 , ,Ci , , використовуючи таємний ключ K B , за формулою

M i CikB mod N .

40