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

 

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

Спочатку розглянемо процедуру створення ключової пари
<КО, КС> алгоритму RSA. Щоб створити ключову пару користувач A виконує такі дії:

1. Вибирає два довільних великих простих числа Р і Q.

2. Обчислює значення модуля N = Р * Q.

3. Обчислює функцію Ейлера φ(N)=(P-1)(Q-1).

4. Вибирає випадковим чином значення відкритого ключа КО з урахуванням виконання таких умов:

1<KO<φ (N), HСД (KO,φ(N))=1,

де HСД (KO,φ(N)) – найбільший спільний дільник чисел KO і
φ(N).

5. Обчислює значення секретного ключа KC, вирішуючи порівняння

KO*KC ≡1 (mod N).

Відмітимо, що умови вибору відкритого ключа забезпечують існування єдиного розв’язку порівняння.

 

Потім користувач А пересилає користувачу В пару чисел (N,KO) по незахищеному каналу зв’язку.

Шифрування інформації відкритим ключем може здійснюватись наступним чином. Користувач В розбиває вихідний відкритий текст на блоки, кожен з яких може бути представлений у вигляді числа P_i (1<P_i<N, i=1,..,n). Потім користувач В послідовность чисел P_i шифрує за формулою

С_і = P_i^KO(mod N), (i=1,..,n).

С₁, …,С_n – шифр-текст.

Користувач A розшифровує шифр-текст С₁, …,С_n, використовуючи секретний ключ KC за формулою

P_і = C_i ^KС (mod N), (i=1,..,n).

У результаті буде отримана послідовність чисел P_i, які являють собою вихідний відкритий текст.

Щоб алгоритм RSA мав практичну цінність, необхідно мати можливість без істотних витрат генерувати великі прості числа, вміти оперативно обчислювати значення ключів KO і KC.

Розглянемо приклад. Для простоти обчислень будуть використовуватися невеликі числа. Для створення ключової пари <КО, КС> алгоритму RSA користувач A виконує таке:

1. Вибирає, припустимо, P = 3 і Q = 11.

2. Обчислює модуль N = P*Q = 3*11 = 33.

3. Обчислює значення функції Ейлера для N = 33: φ(N)=(P-1)(Q-1)= φ(33) = (Р -1)(Q -1) = 2*10 = 20.

4. Вибирає відкритий ключ KO як довільне число з урахуванням виконання умов:

1<KO<φ(N)=20, HСД (KO,φ (N))=1.

Нехай KO = 7.

5. Обчислює секретний ключа KC, вирішуючи порівняння
7 *KC ≡1 (mod (20)). Розвязком є KC = 3.

Далі користувач А пересилає користувачу В по незахищеному каналу зв’язку пару чисел (N = 33, KO = 7).

Нехай користувач В хоче зашифрувати для користувача А текст CAB. Тоді йому треба виконати таке:

1. Текст CAB представляється послідовністю чисел 4,2,3 (кожна літера замінюється її номером в англійському алфавіті), Тоді P₁ = 4, P₂ = 2, P₃ = 3.

2. Шифрування здійснюється відкритим ключем KO = 7 за формулою C_i = P_i ^KO(mod N). Тобто

С₁ = 4⁷ (mod 33) = 16384 (mod 33) = 16,

C₂ =2⁷ (mod 33) =128 (mod 33) =29,

C₃ = 3⁷ (mod 33) =2187 (mod 33) = 9.

Таким чином, шифр-текст С₁, C₂,C₃ є таким: 16,29,9.

Користувач А розшифровує шифр-текст С₁,C₂,C₃, використовуючи секретний ключ KC = 3, за формулою P_і = C_i^KС (mod N):

P₁ = 16³ (mod 33) = 4096 (mod 33) = 4,

P₂ =29³ (mod 33) =24389 (mod 33) =2,

P₃ = 9³ (mod 33) =729 (mod 33) = 3.

 

Безпека алгоритму RSA базується на труднощах факторизації (розкладанні на множники) великих чисел. Останні публікації пропонують застосовувати числа (модуль N) довжиною не менш 250 – 300 десяткових розрядів [9,10.11,12].

RSA реалізуються як апаратним, так і програмним шляхом. Апаратна реалізація RSA приблизно в 1000 разів повільніше апаратної реалізації симетричного алгоритма шифрування DES. Програмна реалізація RSA приблизно в 100 разів повільніше програмної реалізації DES[9,10,11]. З розвитком технології ці оцінки можуть трохи змінюватися, але асиметрична криптосистема RSA ніколи не досягне швидкодії симетричних криптосистем. Слід зазначити, що мала швидкодія криптосистем RSA обмежує область їх застосування, але не перекреслює їх цінність.

 

3.2 Алгоритм Діфі-Хелмана

 

Алгоритм відкритого розподілу ключів Діфі-Хелмана був запропонований у 1976 році. Цей алгоритм був першим алгоритмом з відкритим ключем [9,10,11]. Його безпека обумовлена труднощами обчислення дискретних логарифмів у скінченному полі, на відміну від легкості дискретного зведення в степінь у тому ж скінченному полі.

Припустимо, що два користувачі А і В хочуть організувати захищений комунікаційний канал. Обидві сторони заздалегідь вибирають велике просте число N і число g (1 ≤ g ≤ N-1), яке є первісним коренем по модулю N, тобто його степені

g¹, g², g³,…,g^N-1

є різними по модулю N. Наприклад. Нехай N=7. Тоді g=3 є первісним коренем по модулю 7, тому що

3¹=3≡3 (mod 7),

3²=9≡2 (mod 7),

3³=27≡6 (mod 7),

3⁴=81≡4 (mod 7),

3⁵=243≡5 (mod 7),

3⁶=729≡1 (mod 7).

Ці два цілих числа N і g є спільними для всіх користувачів комп'ютерної системи і їх не треба зберігати в секреті. Алгоритм складається з наступних кроків.

1.	Спочатку користувачі А і В незалежно один від одного вибирають власні секретні ключі KCA і KCB (KCA і KCB – випадкові великі цілі числа, що зберігаються користувачами А і В у секреті).
2.	Далі користувач А обчислює відкритий ключ КОA=gKCA (mod N), а користувач В – відкритий ключ КОB=gKCB (mod N).
3.	Потім користувачі А і В обмінюються відкритими ключами КОA і КОB по незахищеному каналу.
4.	Нарешті користувачі А і В обчислюють спільний секретний ключ. Користувач А обчислює К= (КОB)КCA = (gKCB) КCA(mod N), а користувач В: К' = (КОA)КCB = (gKCA) КCB(mod N). При цьому К = К', тому що (gKCB) КCA = (gKCA) КCB(mod N).

 

Ключ К може використовуватися в якості спільного секретного ключа симетричної криптосистеми.

Зловмисник, перехопивши значення N, g, КО_A і КО_B, теж хотів би знайти ключ К. Очевидний шлях для вирішення цієї задачі складається в обчисленні такого значення КС_A по N, g, КО_A, що

g^KС_A mod N = КО_A.

Оскільки в цьому випадку, обчисливши КС_A можна знайти

К= (КО_B)^КС_A (mod N).

Однак знаходження КС_А по N, g і КО_A – задача дискретного логарифмування в скінченному полі, яка вважається практично нерозв'язною [9,11].

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

Для розподілу секретних ключів між користувачами розподіленої інформаційної системи можна використовувати і алгоритм RSA. Перевага методу Діфі-Хелмана в порівнянні з методом RSA полягає в тім, що формування загального секретного ключа відбувається в сотні разів швидше. У системі RSA генерація нових секретних і відкритих ключів заснована на генерації нових простих чисел, що займає багато часу [9,11].

Приклад. Виберемо модуль N = 19, а первісним коренем по модулю N = 19 число g = 2. Припустимо, що користувачі А і В вибрали своїми секретними ключами КC_А =3 і КC_B =6. Щоб мати спільний секретний ключ К, вони обчислюють спочатку значення своїх відкритих ключів:

КО_A=g^KC_A (mod N)=2³=8=8 (mod 19),

КО_B=g^KC_B (mod N)=2⁵=32=13 (mod 19).

Після того, як користувачі А і В обміняються значеннями КО_A=8 і КО_B=13, вони обчислюють спільний секретний ключ

К= (КО_B)^КCA (mod N)=13³=2197=12 (mod 19),

К' = (КО_A)^КCB (mod N)=8⁵=32768 =12 (mod 19).

Отже, спільний секретний ключ К=12.

 

Контрольні завдання