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

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

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

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

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

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

(4.3)

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

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

За сучасними оцінками теорії чисел при цілому й для розкладання числа буде потрібно близько 10²³ операцій, тобто задача практично нерозв’язна.

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

.

Тоді модульна експонента з основою за модулем N являє собою функцію

,

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

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

Якщо , то, природно, .

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

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

Для відомих цілих знайти ціле число , таке, що

.

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

За сучасними оцінками теорії чисел при досить великих цілих числах A2⁶⁶⁴ й N2⁶⁶⁴ рішення задачі дискретного логарифмування (знаходження показника ступеня для відомого ) потребує близько 10²⁶ операцій, тобто ця задача має в 10³ разів більшу обчислювальну складність, ніж задача розкладання на множники. Різниця в оцінках складності задач зростає при збільшенні довжини чисел.

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

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

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

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

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

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

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

У криптосистемі RSA розглядають: відкритий ключ ; таємний ключ ; повідомлення й криптограма належать множині цілих чисел

, (4.4)

де - модуль

. (4.5)

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

Множина з операціями додавання та множення за модулем утворює арифметику за модулем .

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

(4.6)

, (4.7)

де – функція Ейлера.

Функція Ейлера вказує кількість додатних цілих чисел в інтервалі від 1 до, які взаємно прості з N

.

Умова (3.7) означає, що відкритий ключ і функція Ейлера повинні бути взаємно простими.

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

(4.8)

або

.

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

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

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

(4.9)

Обернення функції , тобто визначення значення M за відомим значенням практично не здійсненне при N2⁵¹².

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

. (4.10)

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

(4.11)

Підставляючи в (4.11) значення (4.9) і (4.10), одержуємо:

або

. (4.12)

Відповідно до теореми Ейлера, яка стверджує, що якщо , то

або

. (4.13)

Порівнюючи вираження (4.12) і (4.13), одержуємо

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

.

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

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

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

.

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