Асиметричні алгоритми

У 1976 р. відкрито новий етап розвитку криптографії. Для новітньої криптографії характерна поява принципово нових криптографічних задач, а також принципово нових методів розв'язування класичних задач. Тому часто говорять про революцію в галузі криптографії. Поступ, що відбувся, пов'язаний з іменами американських математиків Вайтфілда Діффі та Мартіна Хелмана, а також Ральфа Меркле, які розвинули ідеологію відкритого ключа.

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

Криптосистему з відкритим ключем характеризують три процедури: утворення

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

Теоретичні основи

Нехай n - довільне натуральне число, а х- ціле число. Для цілого числа х є Z

через х mod n позначимо залишок від ділення числа х на число n. Запишемо х?у(mod n), якщо х mod n ? y mod n, і казатимемо, що х і у конгруентні (порівняльні) за модулем n. Наприклад, 100 mod 11?l, -8 mod 10 ? 2. Множину (0, 1, ..., n- 1) усіх можливих невід'ємних залишків за модулем п позначимо через Zn. Уважаємо, що х є оберненим елементом до у за модулем п, якщо х?у (mod n). У цій ситуації запишемо x = y-1(mod n). Множину елементів із Zn, для яких існують обернені в Zn, позначимо через Z*n і назвемо ці елементи оборотними за модулем п. У множині Zn можна виконувати дві операції: х є сумою елементів у і z за модулем п, якщо у + z ? x(mod n); х є добутком елементів y і z за модулем п, якщо yz?x(mod n). Якщо п є складеним числом: n= pq, то добуток pq дорівнює нулю в Zn: pq ? 0(mod n). Позначення а Р b означає, що а ділить b. Для цілих чисел а і b через НСД(a, b) позначимо їхній найбільший спільний дільник - найбільше з-поміж таких с, що одно-часно с Р а і с Р b (хоча б одне із чисел а і b вважають відмінним від нуля). Найменше натуральне число, яке ділиться на кожне із невід'ємних цілих чисел р1,р2,…,pk, нази-вають їхнім найменшим спільним кратним і позначають

НСК(ри р2,..., рк).

Твердження 3.1. Такі умови еквівалентні:

1)х ? y(mod n);

2) х - у + kn, де k ціле число;

3)n(х-у).

Конгруенція має такі властивості:

якщо x1 ? y1(mod п) і х2 ? y2(mod n), то x1 + х2 ? y1 + y2(mod n);

якщо x1 ? y1(mod n) i x2 = y2(mod п), то х1 х2 = у1 y2(mod n).

Приклад 3.1. Довести, що число 73524 ділиться на 11.

Очевидно, що 10?-l(mod II). На підставі наведених вище властивостей конгру-енції отримуємо 100?l(mod 11), 1000 ? -1 (mod 11), 10000?l(mod 11). Звідси 20?-2(mod 11), 500?5(mod 11), 3000 ? -3(mod 11), 70000?7(mod 11). Послідовне дода-вання дає 73520?7(mod 11). Тоді 73520 + 4 ?1 + 4 ?0(mod 11).

Розглянемо алгоритм Евкліда (III ст. до н. є.) отримання найбільшого спільного дільника натуральних чисел а і b.

Алгоритм опирається на вирази

НСД(а, b) = НСД(a, a mod b) для a>b; (3.1)

НСД(а, 0) = а. (3.2)

Приклад 3. 2. Знайти НСД(211, 79). Послідовно застосуємо рівність (3.1), доки не отримаємо (3.2):

Отже, НСД(211, 79) = НСД(79, 53) = НСД(53, 26) = НСД(26, 1) = НСД(1, 0) = 1. У загальному випадку виконання алгоритму Евкліда можна описати так.

Кількість т кроків алгоритму Евкліда визначена нерівністю т < 2 log 2 b + 1. Під час виконання алгоритму Евкліда можна знайти такі цілі числа х, у, які задо-вольняють діофантове рівняння ах - by = 1, де а і b взаємно прості: НСД(а, Ь) = 1, а>0, b > 0.

Нехай , де

Тоді (3.3)

Отже, числа х, у, визначені рівностями (3.3), є цілочисловими розв'язками діофантового рівняння.

Описані обчислення зручно виконувати за допомогою табл. З.1.

Приклад 3.3. Визначити такі цілі числа x, у, що 17х - 13у = 1. Маємо

Заповнивши табл. 3.1, отримаємо

Звідси k = 2; x = (-1)k-1 Qk-1 = Q1=-3, y = (-l)k-1, Pk-1=-P1=-4. Легко перевіpити, що 17-(-3)-13-(-4)=1.

Приклад 3.4. (Отримання обернених елементів у Zn). Знайти 8-1 mod 35, тобто розв'язати порівняння 8x?l(mod 35).

Останнє порівняння рівносильне діофантовому рівнянню 8x + 35y= 1, зв'язок якого знаходимо, користуючись алгоритмом Евкліда. Із цього алгоритму випливає

3 = 2-1 + 1 q3=1;

2=1-2+0 q4=1;

Заповнивши табл. 3.1, отримаємо

Маємо k = А; х?(-1)k-1; Qk-1 = Q3 = -13 (mod 35) = 22 (mod 35). Легко перевірити, що 8·22 = 176 = 35·5 + 1?1 (mod 35).

Твердження 3.2. Нехай Z*n - множина оборотних елементів за модулем п. Тоді

множина Z*n складається з