ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 05.06.2024
Просмотров: 76
Скачиваний: 0
У результаті буде отримана послідовність чисел M i , які являють собою вихідне
повідомлення М. Щоб алгоритм RSA мав практичну цінність, необхідно мати можливість без істотних витрат генерувати великі прості числа, вміти оперативно обчислювати значення ключів K A та K B .
Наприклад, виконаємо шифрування повідомлення “Буду завтра”.
Нехай P=59, Q=61. Тоді N P * Q 59 * 61 3599 , а (2773) 3480 . Виберемо як відкритий ключ K A довільне число з урахуванням виконання умов (4.6) і (4.7). Нехай K A 53 . Згідно (4.8) таємний ключ KВ 197 .
Подамо повідомлення як послідовність цілих чисел у діапазоні від 1 до 32. Нехай
A – 01, Б – 02, В – 03, ..., Я – 32.
Тоді повідомлення “Буду завтра” буде подано у вигляді
02 20 05 20 08 01 03 19 17 01.
Розбиваємо повідомлення на блоки по чотири цифри
0220 0520 0801 0319 1701
і кодуємо кожен блок:
C1 22053 mod 3599 0099, C2 52053 mod 3599 3273, C3 80153 mod 3599 2050, C4 31953 mod 3599 0719,
C5 170153 mod 3599 1664.
У результаті одержимо шифр 0099 3273 2050 0719 1664.
Для відновлення вихідного тексту необхідно обчислити модульну експоненту, підвівши зашифроване значення Ci в степінь K В за модулем N:
M1 99197 mod 3599 0220, M 2 3273197 mod 3599 0520, M 3 2050197 mod 3599 0801, M 4 719197 mod 3599 0319, M 5 1664197 mod 3599 1701.
Таким чином, отримали відновлене вихідне повідомлення
0220 0520 0801 0319 1701.
Криптосистеми RSA реалізуються як апаратним, так і програмним шляхом. Для апаратної реалізації операцій зашифрування та розшифрування RSA розроблені спеціальні процесори. Ці процесори, реалізовані на надвеликих інтегральних схемах, дозволяють виконувати операції RSA, пов’язані з піднесенням великих чисел у колосально великий ступінь за модулем N, за відносно короткий час.
Слід відзначити, що і апаратна, і програмна реалізації алгоритму RSA в декілька сот разів повільніші від реалізацій симетричних криптосистем. Мала швидкодія криптосистеми RSA обмежує сферу її застосування, але не перекреслює її цінність.
Безпека й швидкодія криптосистеми RSA
Безпека алгоритму RSA базується на труднощах розв’язання задачі факторизації великих чисел, що є добутками двох великих простих чисел. Дійсно, крипостійкість алгоритму RSA визначається тим, що після формування таємного ключа K B й відкритого ключа K A "стираються" значення простих чисел P й Q, і
тоді винятково важко визначити таємний ключ K B за відкритим ключем K A ,
41
оскільки для цього необхідно розв’язати задачу знаходження дільників P та Q модуля N.
Розкладання величини N на прості множники Р і Q дозволяє обчислити функцію(N ) (P 1)(Q 1) , а потім визначити таємне значення K B , використовуючи
рівняння (4.8).
Іншим можливим способом криптоаналізу алгоритму RSA є безпосереднє обчислення або підбір значення функції (N ) . Якщо встановлено значення (N ) ,
то співмножники P й Q обчислюються досить просто. Справді, нехай x P Q N 1 (N ),
y (P Q)2 (P Q)2 4 * N.
Знаючи (N), можна визначити х і потім y; знаючи х та y, можна визначити числа
P і Q з таких співвідношень:
|
1 |
|
|
|
1 |
|
|
|
|
P |
(x |
y ), Q |
(x y ) . |
||||||
2 |
2 |
||||||||
|
|
|
|
|
|
|
Однак ця атака не простіша задачі факторизації модуля N.
Задача факторизації є задачею, яка важко розв’язується для великих значень модуля N.
Спочатку автори алгоритму RSA пропонували для обчислення модуля N вибирати прості числа P й Q випадковим чином, по 50 десяткових розрядів кожне. Вважалося, що такі великі числа N дуже важко розкласти на прості множники. Один з авторів алгоритму RSA, Р.Райвест, вважав, що розкладання на прості множники числа з майже 130 десяткових цифр, наведеного в їхній публікації, зажадає більше 40 квадрильйонів років машинного часу. Однак цей прогноз не виправдався через порівняно швидкий прогрес обчислювальної потужності комп’ютерів, а також поліпшення алгоритмів факторизації.
Один з найбільш швидких алгоритмів, відомих у цей час, алгоритм NFS (Number Field Sieve) може виконати факторизацію великого числа N (із числом десяткових розрядів більше 120) за число кроків, оцінюваних величиною
1 |
2 |
e2(ln N )3 (ln(lnN )) 3
У 1994 р. було факторизовано число з 129 десятковими цифрами. Це вдалося здійснити математикам А.Ленстра й М.Манассі за допомогою організації розподілених обчислень на 1600 комп’ютерах, об’єднаних мережею, протягом восьми місяців. На думку А.Ленстра та М.Манассі, їхня робота компрометує криптосистеми RSA і створює більшу погрозу їхнім подальшим застосуванням. Тепер розроблювачам криптоалгоритмів з відкритим ключем на базі RSA доводиться уникати застосування чисел довжиною менше 200 десяткових розрядів. Останні публікації пропонують застосовувати для цього числа довжиною не менше 300 десяткових розрядів.
4 Схема шифрування Поліга - Хеллмана
Схема шифрування Поліга - Хеллмана подібна RSA. Розглянута схема не є симетричним алгоритмом, оскільки використовуються різні ключі для шифрування та розшифрування. З іншого боку її не можна віднести й до класу криптосистем з відкритим ключем, тому що ключі шифрування та розшифрування легко виходять один з одного. Обидва ключі (відкритий і таємний) необхідно тримати в таємниці.
Аналогічно схемі RSA криптограма C і відкритий текст M визначаються зі співвідношень:
42
C M K A mod N , |
(4.14) |
M C K B mod N , |
(4.15) |
де
K A * KB 1mod(деяке складене число) . (4.16)
На відміну від алгоритму RSA у цій схемі число N не визначається через два великих простих числа; число N повинне залишатися частиною таємного ключа. Якщо хто-небудь довідається значення K A та N, він зможе обчислити значення
K B .
Не знаючи значень K A або K B , зловмисник буде змушений обчислювати значення
K A (log M C) mod N .
Відомо, що це є важкою задачею. Схема шифрування Поліга - Хеллмана запатентована в США [9] і Канаді.
5 Алгоритм шифрування Ель Гамаля
Алгоритм Ель Гамаля, розроблено в 1985 р., може бути використаний як для шифрування, так і для цифрових підписів. Безпека схеми Ель Гамаля обумовлена складністю обчислення дискретних логарифмів у кінцевому полі.
Для того щоб генерувати пари ключів (відкритий ключ K A і таємний ключ K B ),
спочатку вибирають деяке велике просте число P і велике ціле число G степені якого за модулем P породжують велику кількість елементів множини Z P ,
причому G P . Числа P й G можуть бути поширені серед групи користувачів. Потім вибирають випадкове ціле число K B , причому KB P . Число K B є таємним
ключем і повинне зберігатися в секреті. Далі обчислюють відкритий ключ K A
K |
A |
G KB mod P . |
(4.17) |
|
|
|
|
|
|
Для того, щоб зашифрувати повідомлення М, вибирають випадкове ціле число K , |
||||
що задовольняє такі умови: |
|
|||
1 K P 1, |
(4.18) |
|||
НОД (K , (P 1)) 1 . |
(4.19) |
|||
Потім обчислюють числа |
|
|||
a G K mod P, |
(4.20) |
|||
b K |
K * M mod P. |
(4.21) |
||
|
|
|
A |
|
Пари чисел (а,b) є шифротекстом. Помітимо, що довжина шифротексту вдвічі більша довжини вихідного відкритого тексту М.
Для того щоб розшифрувати шифротекст (а,b), обчислюють
M |
b |
mod P . |
(4.22) |
|
|||
|
a K B |
|
Довести, що співвідношення (4.22) справедливо, можна виходячи з (3.17) , (3.20) і (3.21), оскільки
b |
|
K A K *M |
|
(G K B ) K * M |
|
G K B *K * M |
M mod P . |
a K B |
a K B |
(G K ) K B |
|
||||
|
|
|
G K *K B |
Наприклад, виберемо Р = 17, G = 5, таємний ключ K B = 2. Обчислюємо
K A G KB mod P 52 mod 17 8 .
Отже, відкритий ключ K A = 8.
Нехай повідомлення М = {Д}={5}.
Виберемо деяке випадкове число K = 3. Перевіримо умову (3.19) дійсно НСД (3,16) =1. Обчислюємо пари чисел а та b:
43
aG K mod P 53 mod 17 125 6 mod 17,
bK A K * M mod P 83 * 5 mod 17 2560 10 mod 17.
Таким чином, шифротекстом для літери Д є пара чисел (6,10).
Виконаємо розшифрування цього шифротексту. Обчислюємо повідомлення М, використовуючи таємний ключ K B
M |
b |
mod P |
10 |
mod 17 . |
|
a K B |
62 |
||||
|
|
|
Вираз
M 1062 mod 17
можна подати у вигляді
62 * M 10 mod 17 .
Розв’язуючи дане порівняння, знаходимо М = 5.
Уреальних схемах шифрування необхідно використовувати як модуль P велике ціле просте число, що має у двійковому поданні довжину від 512 до 1024 бітів.
Усистемі Ель Гамаля відкритого шифрування той самий ступінь захисту, що для алгоритму RSA з модулем N з 200 знаків, досягається вже при модулі P в 150 знаків. Це дозволяє в 5-7 разів збільшити швидкість обробки інформації. Але у такому варіанті відкритого шифрування немає підтвердження достеменності повідомлень.
Система Ель Гамаля не позбавлена певних недоліків. Серед них можна зазначити такі:
1 Відсутність семантичної стійкості. Якщо G – примітивний елемент множини Z P ,
то за поліноміальний час можна визначити чи є деяке число x квадратичним
відрахуванням. Це робиться піднесенням числа x у степінь |
p 1 |
за модулем P |
|||
2 |
|
||||
|
|
|
|
|
|
|
( p 1) |
|
|
|
|
x 2 mod P . |
|
|
|
Якщо результат дорівнює 1, то х – квадратичне відрахування за модулем Р, якщо –1 , то х – квадратичне невирахування. Далі пасивний зловмисник перевіряє, чи є GK і G K A квадратичними відрахуваннями. G K *K A буде квадратичним відрахуванням тоді й тільки тоді, коли і GK , і G K A будуть квадратичними відрахуваннями. Якщо це так, то K * M mod P буде квадратичним відрахуванням тоді й тільки тоді,
коли саме повідомлення М буде квадратичним відрахуванням. Тобто пасивний зловмисник одержує деяку інформацію про вихідний текст, маючи лише шифрований текст і відкритий ключ одержувача.
2 Подільність шифру. Якщо дано шифрований текст (a, b), можна одержати інший шифрований текст, змінивши тільки другу частину повідомлення. Справді, помноживши b на GU (U 0), можна одержати шифротекст для іншого вихідного повідомлення M M * GU .
6 Схема шифрування Рабіна
Схема Рабіна була розроблена в 1979 році й може застосовуватися тільки для шифрування даних. Безпека алгоритму спирається на складність пошуку коренів за модулем складеного числа.
Для генерації ключів вибирається пара простих чисел p, q , таких що
p 3 mod 4,
(4.23)
q 3 mod 4.
Ці прості числа і є таємним ключем. Відкритим ключем є число
44