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

У 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. У загальному випадку виконання алгоритму Евкліда можна описати так.
Кількість т кроків алгоритму Евкліда визначена нерівністю т 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 складається з елементів х, взаємно простих з п і лише з них: {х 1, то х не має оберненого елемента за модулем n, оскільки и х mod n є числом вигляду wx- vn, а, отже, ділиться на р.
Нехай ц(п) - кількість натуральних чисел, які менші від п і взаємно прості з n. Функцію ц називають функцією Ейлера. Якщо р - просте число, то ц(р) - р - 1. Легко перевірити, що коли р, q (р ? q) - прості числа, то ц(pq) = (р - l)(g - 1). Це випливає з того, що числа, які мають спільні з pq дільники, відмінні від 1, - це числа вигляду р, 2p,...,p(q-1),q,2q,..,q(p-1).
Твердження 3.3. (Вираз для функції Ейлера). Нехай п - натуральне число і нехай, де р1...,рl - прості числа. Тоді ц(п) = п{1 - 1/р1)...(1 - 1/рl).
Наприклад, нехай l = 1 (n = рб). Тоді числа, що менші або дорівнюють п і не взаємно прості з п, - це числа вигляду р, 2р, Зр, ..., ра; ра = ра-1 р. Отже, кількість цих чисел ра-1 Звідси випливає, що ц(ра) -ра - ра-1 = ра (1 - 1 / р).
Твердження 3.4. (Ейлер, 1763 p.). Для взаємно простих цілого х і натурального п виконується конгруенція хц(n)= 1 (mod n).
Оскільки для простого числа р ц(р) =р - 1, то отримуємо таке твердження.
Твердження 3.5. (мала теорема Ферма, 1640p.). Якщо р - просте число і ціле х не ділиться на р, то хp-1= 1 (mod p).
Приклад 3.5. Перевірити виконання конгруенції 4130= 1 (mod 31). Маємо таке:
1) 412(mod31) ?l02(mod31) ? 7(mod31);
414(mod 31) ? 72(mod 31) ? 18(mod 31);
418(mod31) ?182(mod31) ?14(mod31);
4116(mod 31) ? 142(mod 31) ? 10(mod 31);
2) оскільки 30 = 16 + 8 + 4 + 2, то 4130(mod 31) ? (4116418414412)(mod 31) ? (101418'7)(mod 31) ? 17640(mod 31) ? (569-31 + I)(mod31) ?l.
Твердження 3.6. (Китайська теорема про залишки, І ст. до н. є.). Нехай n1,n2 -взаємно прості цілі числа, а x1, х2- довільні цілі числа. Тоді існує лише одне таке число x що х?х1 (mod n1), х?x2(mod п2).
Справді, якщо НСД(n1,n2)= 1> то u1n1-u2n2 =1 де u1,u2 - цілі числа. Маємо u1n1 ?l(mod п2) і и2п2 ? l(mod n1). Звідси отримуємо х = x2 и1п1- x1 и2п2 оскільки х?-x1u2n2(mod n1) ?x1(mod n1), x?-x2u1n1(mod n2) ?x2(mod n2).
Приклад 3.6. Визначити таке ціле число х, що х= 100(mod 211) та as 10(mod 79).
З алгоритму Евкліда випливає 1 = 3*211-879. Маємо n1 =211, и1=3, n2 = 79, и2 = 8, а звідси отримуємо х = 10*3*211 – 8*79 = -56870. Оскільки -56870 (mod 211*79) = -56780(mod 16669) == 9806, то х = 9806.
Порядком елемента х є Zp* називають таке найменше натуральне число к, що xk=1(тоd р).
Нехай G довільна не порожня підмножина множини Zp*. Елемент g є G назива-ють твірною множини G, якщо для кожного х є G знайдеться таке натуральне число i, для якого х = gi(mod p). Зрозуміло, що порядок твірної множини G збігається з кіль-кістю елементів у множині G.
Твердження 3.7. Нехай р — просте число. Тоді існує твірна g множини Zp*,. Оскільки у множині Zp* є р- 1 елементів, то елементи
g° mod p? 1, g1 mod p, g2 mod p, g2 mod p, ... , gp-2 mod p
є попарно різними елементами множини Zp*.
Є багато твірних у множині Zp*. Якщо g є твірною, то й gi є твірною, коли НСД(i,р- 1)=1.
Приклад 3.7. Нехай р = 23. Тоді g = 5 є твірною в Z23*,.
Справді, 50 mod 23 = 1, 51 mod 23 = 5, 52 mod 23 = 2, 53 mod 23 ? 2-5 ?10. Насту-пні степені числа g = 5 за модулем р = 23 такі: 4, 20, 8, 17, 16, 11, 9, 22, 18, 21, 13, 19, З, 15.6,7,12,14.
З малої теореми Ферма випливає, що для кожного х є Z*23 виконується конгру-енція х22 =1 (mod 23).
Нехай р - просте число, і нехай р -1 = qa1...qa1 , де q1, ..., ql - прості числа. Тоді число g буде твірною множини Zp*., якщо для кожного 1 <і 2 - просте число, х є N, р не ділить х та у2 = x(mod р). Тоді
у = ±xm+l (mod р)є Zр* при = 4m + 3;
у = ±xm+l(mod р) при р = 8т+ 5 та x2m+l ? 1 (mod p);
у = ±xm+l 22m+l(mod p) при p=8m+ 5 ma x2m+1 ?-l (mod p).
Тести простоти
Розглянемо таку задачу, яка виникає в разі побудови криптографічних систем з відкритим ключем. Маємо натуральне число л. Треба перевірити, чи п є простим чис-лом. Алгоритми розв'язування цієї задачі називають тестами простоти. їх поділяють на дві групи: ймовірнісні та детерміновані.
Спочатку розглянемо ймовірнісні тести. Ці тести простоти потребують менших обчислювальних затрат, проте дають відповідь щодо простоти числа з певною похиб-кою, ймовірність якої можна оцінити.
На підставі малої теореми Ферма wp-1 = l(mod р) для кожного простого р і w < p. Кажемо, що w < п є основою простоти для п (або в іншій термінології: п є простим за основою w), якщо wp-1 = l(mod n). У випадку, якщо п - просте число, всі числа w < п є основами простоти для п.
Тест Ферма: к разів незалежно виконуємо тест (к вибирає користувач):
вибираємо випадкове число w 1, то л є складеним числом;
обчислюємо u = wn-1(mod n);
якщо u?1,то п є складеним числом.
Якщо під час жодного з k тестів не ствердимо, що п- складене число, то відпо-відь звучить так: "п є простим числом".
Твердження 3.10. Нехай S позначає множину чисел, взаємно простих з п. Тоді zoo кожен елемент S є основою простоти для п, або щонайменше половина елементів
- с основами простоти для п.
Із твердження 3.10 випливає таке: якщо для складеного числа п існує число w, що не є основою простоти для л, то з імовірністю 1/2 в одиничному тесті знайдемо число, гкі не є основою простоти для л. Ймовірність для k спроб становить 1/2 .
Проблема полягає в тому, що існують складені числа п, для яких усі елементи S є основами простоти для п. Для них тест Ферма завжди дає хибну відповідь. Такі числа називають числами Кармайкла. Найменшим з них є число 561 = 3* 11* 17. Лише порівняно недавно (1994) доведено, що множина таких чисел нескінченна. Складено таблицю для всіх чисел Кармайкла, менших від числа 25- 109.
Тест Ферма можна модифікувати так, щоб отримати справді ймовірнісний тест простоти чисел.
Тест Міллера-Рабіна дослідження числа п на простоту. Нехай п – 1=28* т, де 28
- найвищий степінь двійки, який ділить п-1, т непарне. Нехай k - задане натуральне число. Незалежно k разів виконуємо тест:
вибираємо випадково число х у межах: 1 < х 2) тоді і тільки тоді є простим, якщо числоLk-1 i ділиться на Mk де L1 = 4, Ln+1 = Ln2-2, (L2 = 14, L3 = 194, L4 = 37634,...).
Зазначимо, що прості числа вигляду 2k- 1 (k також є простим числом) називають числами Мерсена, а прості числа вигляду 2k + 1 (к = 2т) - числами Ферма.
Афінні шифри
Найпростішими представниками асиметричних алгоритмів є афінні шифри. Нехай п - кількість літер абетки, нумерація яких починається від 0. Тоді можна збудувати такі шифри.
Шифр зсуву.
Ключ: s:0?s?n.
Шифрування. У повідомленні кожну літеру х заміняють на
Е(х) ? (х + s)mod n.
Дешифрування. У криптограмі кожну літеру х' заміняють на
D(x’)?(x’+s’)mod n,
де s' = п - s є ключем дешифрування.
Лінійний шифр.
Ключ: а:0 аn оскільки Тоді біт in можна легко обчислити. Знайшовши in, отримуємо к' = к – іn аn і суперзростаючий вектор (a1 ...,an-1). Криптограма к' відповідає цьому вектору та явному тексту i1,…,in-1. Аналогічно, як і раніше, тепер можемо знайти in-1. Повторюємо ці дії доти, доки не отримаємо всі біти ij.
Як уже зазначено, описаний алгоритм не можна застосовувати на практиці, бо знайдено метод дешифрування за прийнятний час без знання таємного ключа. Це не означає, що знайдено алгоритм, який за прийнятний час розв'язує NР-повну задачу про вкладання рюкзака.
Алгоритм, що зламує шифр заповнення рюкзаків, працює лише для спеціальних векторів, отриманих із суперзростаючих векторів. Для довільних векторів надалі не відомо жодного ефективного методу.
Додамо, що існує алгоритм шифрування (Хор-Райвест), який ґрунтується на проблемі заповнення рюкзака, та досі не розкритий.
Криптосистема RSA
Система шифрування з відкритим ключем RSA запропонована 1977 р. Назва сис-теми утворена з початкових букв прізвищ її авторів (R.Rivest, A.Shamir і L.Adleman).
Ця система є криптосистемою, стійкість якої ґрунтується на складності розв'язу-вання задачі розкладу числа на прості співмножники.
Система RSA потребує для реалізації значну кількість арифметичних операцій. Тому швидкість шифрування й дешифрування для неї є значно нижчою (приблизно у : 000 разів), ніж для симетричного шифру DES.
Специфічні застосування RSA. Нехай ключ К1 є приватним, а ключ К2 - пуб-лічним ключем деякої особи А. Завдяки виконанню умови
DK1(EK2(x)) = EK1(DK2(x)) = х ту саму пару ключів К1, К2 можна використати з різною метою.
Шифрування кореспонденції. Нехай особа В хоче надіслати лист М особі А. З цією метою В обчислює Ек2(М) і надсилає результат А. Особа А отримує ЕК1(М) й обчислює DK1(Ek2(M)) = М. Не знаючи ключа К1, практично неможливо дешифрувати Еk2(М). А тому лише особа А може прочитати призначений їй лист від особи В.
Підтвердження. Нехай особа А хоче розіслати повідомлення Т, підтверджуючи водночас, що є його автором. Для цього А шифрує Т як ЕК1{Т). Кожен адресат дешифрує повідомлення за допомогою публічного ключа К2 як Dk2 (Ek1 (T)) = Т.
Алгоритм RSA
Нехай маємо певну систему з великою кількістю користувачів, і кожен з них може надіслати таємне повідомлення до іншого. Одиницями явного тексту є цілі числа з вибраного користувачем діапазону. Повідомлення може складатися з блоків літер абет-ки, наприклад, української. Кожна літера відображена своїм номером у абетці (нагаду-ємо, що нумерацію літер починають з нуля). Водночас зазначимо, що повідомлення не обов'язково повинно бути текстом. Це може бути будь-яка інформація: звуковий сиг-нал, зображення (світлина чи фільм), база даних тощо. На практиці одиниці явного тексту мають приблизно від 200 до 600 десяткових знаків.
Кожен користувач діє так.
Вибір ключа. Випадково вибирає два великі прості числа р і q та обчислює їхній добуток п = pq. Випадково вибирає число e таке, що e < ф(п) - (р - 1)(q - 1), де ф(п) - значення функції Ейлера для п. Число є повинно бути того самого порядку, що й число п і, крім того, числа e та ф(п) повинні бути взаємно простими: НСД (e, ф(п)) = 1. Інакше кажучи, е є Z* ф(n). За допомогою алгоритму Евкліда обчислює число d, що задовольняє умову
ed l(mod ф(п)).
У цьому разі, пара е, п є утвореним публічним ключем, а число d - утвореним приватним ключем в алгоритмі RSA.
Шифрування. Шифрувати можна числа з проміжку 0 < т 0. Зазначимо, що алгоритми, склад-ність яких оцінюють подібним способом, називають субекспоненційними.
У табл. 3.3 наведено значення величин L(k) залежно від кількості бітів k числа п, де MIPS година означає продуктивність 1 000 000 команд за секунду упродовж 1 год (3.1*1013 команд).
Автори алгоритму RSA як приклад зашифрували 1977 р. англійське повідомлен-ня the magic words are squeamish ossifrage (магічні слова до нудоти закостенілі). На початку кожна англійська буква була замінена її номером в англійській абетці - так отримано це повідомлення т у цифровій формі. Як публічний ключ вибрано число п з 129 десятковими розрядами та число є - 9007. Ці два числа та зашифроване за їхньою допомогою повідомлення т були опубліковані. Крім того, повідомлено, що число п є добутком двох простих чисел з 64 та 65 десятковими знаками, відповідно. Тому, хто перший дешифрує згадану фразу, обіцяли символічну нагороду у 100 дол. США.
Тільки через 17 років (у 1994 р.) це повідомлення дешифрували. Факторизація розклад) числа п, яке було добутком двох різних простих чисел, потребувала величез-них затрат. Роботою керували чотири автори проекту Д.Аткінс, М.Графф, А.Ленстра та Л.Лейланд, які провели попередню теоретичну підготовку з приблизно 600 доброволь-лями. Ці люди працювали 220 днів і використали 1600 комп'ютерів, пов'язаних мере-жею Internet.
У 1991 р. фірма RSA Data Security (тепер RSA Security) почала проводити кон-курси із розкладу чисел на прості множники (RSA Factoring Challenge), які стали одним з найбільших випробувальних полігонів застосувань методів факторизації.
Від часу запровадження цих конкурсів було розкладено понад тисячу чисел, що дало змогу створити одну з найбільших колекцій результатів факторизації. Автори, що 5рали в них участь, подали вичерпну інформацію про використані методи.
Найвагомішим нині результатом є факторизація так званого числа RSA-155 з 155 десятковими розрядами. Виставлені на конкурс числа позначають RSA-XXXX, де ХХХХ дорівнює довжині числа в бітах. Факторизацію завершено 1999 р. після семи місяців роботи. Керівниками проекту були А.Ленстра та Х.Ріеле. Обчислення виконували на 300 робочих станціях і персональних комп'ютерах. Розклад заданого 512-бітового числа є важливим у тому сенсі, що 512 бітів - загальноприйнятий розмір ключа для шифрування переважної більшості комерційної інформації, яка надходить через електронну пошту. Водночас практичне значення розкладу числа RSA-155 не треба перебільшувати. Результат вражає, проте ціна зламування 512-бітового ключа надто висока, щоб охочі могли широко застосовувати цю техніку. Його необхідно розглядати ік сигнал про важливість вибору достатньо великих за розміром ключів. Фірма RSA Security ще задовго до описаної факторизації рекомендувала розміри ключів щонайменше 768 бітів.
Сьогодні вважають, що 512-бітовий ключ забезпечує слабкий захист інформації, 1024-бітовий ключ дає змогу досить надійно захистити інформацію для більшості за-стосувань, а 2048-бітовий ключ - такий, що гарантує захист на десятки років.
Як приклад, наведемо число RSA-155 у вигляді добутку двох простих співмнож-ників:
де обидва співмножники мають по 78 десяткових розрядів.
Інформацію про конкурси RSA Factoring Challenges можна знайти за адресою. Уявлення про числа, виставлені на конкурс RSA Challenge, дає табл. З.4.
Наведемо для прикладу інформацію про найменше RSA-576 та найбільше RSA-2048 числа, виставлені на конкурс. Уважають, що для розкладу числа RSA-576 потрібно приблизно один рік, а до часу факторизації числа RSA-2048 минуть десятки років.
Число RSA-576 має 174 десяткові розряди, а його значення дорівнює
188198812920607963838697239461650439807163563379417382700763356422988859715234665485319060606504743045317388011303396716199692321205734031879550656996 221305168759307650257059.
У цьому разі сума десяткових розрядів становить 785, а розмір винагороди за його розклад - 10 000 дол. США.
\
Число RSA-2048 має 617 десяткових розрядів, і винагорода за його факторизацію становить 200 000 дол. США:
Виставлені на конкурс числа отримані за допомогою процедури, яка гарантує, що дільники кожного з чисел не можуть бути отримані інакше як унаслідок факторизації відповідного числа. У цьому разі ніхто, в тому числі й співробітники фірми RSA Security, не знають дільників конкурсних чисел.
Генерування відбувалося на переносному персональному комп'ютері Compaq без будь-якого його приєднання до мережі таким способом. Спочатку утворено 30 000 випадкових бітів за допомогою апаратного генератора випадкових чисел, приєднаного до паралельного порту комп'ютера. Утворені випадкові біти використано як паростки для програми генерування пар ключів RSA. Приватну частину пар ключів знищено, а публічну частину перетворено у відповідний формат і виставлено на сторінці Інтернету. Після цього твердий диск комп'ютера знищено.
У табл. 3.5 наведено оцінку ресурсів, що потрібні для розкладання за один рік чисел з різною кількістю бітів. Під машиною мають на увазі комп'ютер 500 MHz Pentium (або подібний) з відповідною оперативною пам'яттю.
Як видно з табл. 3.5, для розкладання 760-бітового числа упродовж одного року потрібно 215 000 машин класу Pentium, кожна з яких має 4 Гбайтів оперативної пам'яті. Наведені оцінки ґрунтуються на найліпших сьогодні алгоритмах розкладання. Можливо, що будуть розроблені нові підходи, які дадуть змогу зменшити як кількість комп'ютерів, так і обсяг пам'яті кожної машини.
Криптосистема Рабіна
Система Рабіна (1979) є криптосистемою, стійкість якої ґрунтується на складнос-ті розв'язування задачі розкладу числа на прості співмножники.
Вибір ключа. Випадковим способом вибирають два великі прості числа р і q та обчислюють їхній добуток п=рq. У криптосистемі Рабіна число п є публічним ключем, а пара чисел p,q — приватним ключем.
Шифрування. Шифрувати можна число (блок тексту) 0 ?m? п:
Е(т) = т2 mod n.
Тоді для блока явного тексту отримаємо криптограму
с = Е(т).
Дешифрування. Число т є квадратним коренем з с = Е(т) за модулем п.
Результати дають ефективний алгоритм добування всіх (відомо, що їх є чотири) квадратних коренів за модулем п, який вико-ристовує співмножники р і q (тобто таємний ключ).
Ця система має ту ваду, що під час дешифрування отримують чотири різні ко-рені. У цьому разі тільки один із них відповідає явному тексту. Після відшукання всіх чотирьох коренів із них вибирають той, який є числовим еквівалентом осмисленого тексту.
Зазначимо, що система Рабіна не допускає однозначного дешифрування, однак її можна зробити такою шляхом простої модифікації. Однозначності можна досягти шля-хом передавання разом із криптотекстом деякої додаткової незашифрованої інформації. Це справді необхідно, коли шифрують не текстову, а суто числову інформацію.
Приклад 3.15. Нехай р = 59 і q = 71. Тоді число п = 4189 є публічним ключем. Розглянемо шифрування повідомлення новий пароль - скеля. Ігноруючи тире та пропус-ки між словами і нумеруючи літери української абетки (починаючи з нуля), переводимо наше повідомлення в числовий вигляд.
З огляду на величину и зашифровуємо повідомлення, розбиваючи його на блоки по чотири цифри в кожному: 1718 0210 1319 0020 1815 3021 1406 1532. Обчислюємо
Отримано криптотекст 2468 2210 1326 0400 1671 2799 3817 1184.
Проілюструємо тепер процес дешифрування у вибраній системі Рабіна.
Нехай маємо криптотекст 02250557 і хочемо його розшифрувати. З огляду на значення публічного ключа розіб'ємо криптотекст на два 4-цифрові блоки. Першим розшифруємо блок 0225.
Обчислимо хp = 255(mod 59) = 48 та хq = 255(mod 71) = 12. Із твердження 3.9 ви-пливає ) yp = ±4814+1(mod59) = (15,44), (p=4*14+3); yq= ±1217+1(mod 71) = (15,56), (q= 4* 17 + 3). На підставі китайської теореми про залишки отримаємо таке число z1 = 15, що 15 = 15(mod 59) та 15 = 15(mod 71). Для залишків (15, 56) маємо z2= 2257. Оскільки п = 4189, то –z1 = 4189 - 15 = 4174 і -z2 = 4189 - 2257 = 1932.
Отримано чотири тексти: 0015; 2257; 4174; 1932. Українській абетці відповідають лише комбінації 0015 ("ал") та 1932 ("пя").
Аналогічно розшифруємо блок 0557 і отримаємо комбінацію 2230 („ть"). Отже, було зашифровано повідомлення п 'ять.
З наведеної вище конструкції алгоритму Рабіна зрозуміло, що задача зламування цієї криптосистеми є задачею добування квадратного кореня з числа за модулем. Ця задача має таку ж обчислювальну складність, як і задача розкладу числа на прості множники.
Криптосистема Ель-Гамаля
Система Ель-Гамаля (1985) є криптосистемою, стійкість якої грунтується на складності розв'язування задачі дискретного логарифмування в скінченному полі.
Вибір ключів. Випадково вибирають таке просте число р, що обчислення лога-рифма за модулем р (тобто отримання для заданого числа : 0<<p такого степеня i, що ai (mod р), де а - твірна множини Zp*) практично важко реалізувати.
Далі випадково вибирають число g таке, щоб 1 < g < р - 1 і g було того самого порядку, що й числа в Zр* (в ідеальному випадку елемент g є твірною для Zр*). Відшу-кують такі числа а і h, що 1 < а < р - 1 та h = ga mod p.
Числа р, g, h є публічним ключем.
Число а є приватним ключем.
Шифрування. Шифрувати можна числа 0 < т < р. Виконують такі кроки:
вибирають випадкове число r так, щоб 1 < r 3 - просте число, і нехай а та b - такі елементи кільця Zp, що 4а3+ 27b2 0. Еліптичною кривою Е над кільцем Zp називають множину розв'язків (х,у) рівняння
у2 =x3 + ах + b
разом з додатковою точкою в нескінченності О.
Задамо бінарну операцію на множині Е з використанням адитивного запису так:
0 + 0 = 0;
для довільних елементів x, у з множини Е:
(х, у) + О= (х, у);
для довільних елементів х1, у1 з множини Е (у1 0):
(x1,y1)+ (x1,y1)=2-2x1, (x1-x2)-y1), =(3x12+a)(2y1)-1;
для елементів x1,y1,x2,y2 з множини Е(x1x2)
(x1,y1)+ (x1,y1)=(x3,y3), x3=2-x1-x2, y3= (x1-x3)-y1, =(y2-y1)(x2-x1)-1;
Множина точок еліптичної кривої Е із заданою таким способом операцією утво-рює абелеву групу.
Зазначимо, що аналогічно можна означити еліптичні криві над скінченими по-лями характеристики 2.
Користуючись операцією додавання точок на кривій, природним способом визна-чають операцію множення точки кривої на довільне ціле число n:
пР = Р + Р + Р+...+Р, Р є Е,
де додавання виконують и разів.
Збудована функція пР є односторонньою функцією, на підставі якої можна ство-рити криптографічну систему. Зазначимо, що для обчислення за оптимальним алгорит-мом функції пР потрібно не більше, ніж 2 log2 n операцій додавання. Опишемо крипто-графічний протокол формування ключа, аналогічний до відомого протоколу Діффі-Хелмана.
Для налагодження захищеного зв'язку два користувачі А і В спільно вибирають еліптичну криву Е і точку Р на ній. Кожний із користувачів вибирає своє секретне ціле число. Нехай це будуть числа а і b, відповідно. Сторона А обчислює вираз аР, а сторона В - вираз bР. Сторони обмінюються обчисленими значеннями. У цьому разі параметри самої кривої, координати точки на ній і значення добутків аР, bР є загальнодоступними і можуть бути передані по відкритих лініях зв'язку. Користувач А множить отримане значення на а, а, відповідно, користувач В множить отримане значення на b. У результа-ті обидві сторони мають одне й те саме значення: а(bР) = b{аР) - аbР (координати точ-ки аbР). Отримане значення аbР є секретним і може бути використане для формування ключа шифрування. Зловмиснику для відтворення ключа необхідно розв'язати складну з обчислювального погляду задачу визначення чисел а і b, знаючи дані про Е, Р, аР, bР.
У загальному випадку задача криптоаналізу системи, побудованої на еліптичних кривих, рівносильна розв'язуванню такої задачі. Задано еліптичну криву Е, точку РєЕ на цій кривій та добуток пР; визначити число п. Усі відомі сьогодні алгоритми роз-в'язування цієї задачі є складними.
Еліптичні криві можна застосувати й для утворення цифрових підписів. Виявляється, що замість того, щоб розглядати кільця Zp, можна використати еліптичні криві над полем Zp-, де р' є значно меншим простим числом. Наприклад, алгоритм DSA використовує елемент g

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

Внимание, отключите Adblock

Вы посетили наш сайт со включенным блокировщиком рекламы!
Ссылка для скачивания станет доступной сразу после отключения Adblock!

Скачать