Електронний цифровий підпис, алгоритм RSA. Приклад алгоритму шифрування rsa Rsa дешифрування

Залежно від структури використовуваних ключів методи шифрування поділяються на:

• симетричне: стороннім особам може бути відомий алгоритм шифрування, але невідома невелика порція секретної інформації - ключа, однакового для відправника та одержувача повідомлення; Приклади: DES, 3DES, AES, Blowfish, Twofish, ГОСТ 28147-89
• асиметричне шифрування: стороннім особам може бути відомий алгоритм шифрування, і, можливо, відкритий ключ, але невідомий закритий ключ, відомий тільки одержувачу. Криптографічні системи з відкритим ключем в даний час широко застосовуються в різних мережевих протоколах, зокрема, в протоколах TLS і його попереднику SSL (що лежать в основі HTTPS), а також SSH, PGP, S/MIME і т.д. використовує асиметричне шифрування - .

На даний момент асиметричне шифрування на основі відкритого ключа RSA (розшифровується, як Rivest, Shamir and Aldeman – творці алгоритму) використовує більшість продуктів на ринку інформаційної безпеки.

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

Розглянемо алгоритм RSA з практичного погляду.

Для початку необхідно згенерувати відкритий та секретні ключі:

• Візьмемо два великі прості числа p and q.
• Визначимо n, як наслідок множення p on q (n= p*q).
• Виберемо випадкове число, яке назвемо d. Це число має бути взаємно простим (не мати жодного спільного дільника, крім 1) з результатом множення (p-1)*(q-1).
• Визначимо таке число е, якого є істинним наступне співвідношення (e*d) mod ((p-1)*(q-1))=1.
• Назвемо відкритим ключем числа e і n, а секретним - d і n.

Для того, щоб зашифрувати дані з відкритого ключа (e,n), необхідно наступне:

• розбити текст, що шифрується, на блоки, кожен з яких може бути представлений у вигляді числа M(i)=0,1,2..., n-1(тобто тільки до n-1).
• зашифрувати текст, що розглядається як послідовність чисел M(i) за формулою C(i)=(M(I)^e)mod n.

Щоб розшифрувати ці дані, використовуючи секретний ключ (d,n), потрібно виконати такі обчислення: M(i) = (C(i)^d) mod n. В результаті буде отримано безліч чисел M(i), які є вихідним текстом.

Наступний приклад наочно демонструє алгоритм шифрування RSA:

Зашифруємо та розшифруємо повідомлення "САВ" за алгоритмом RSA. Для простоти візьмемо невеликі числа – це скоротить наші розрахунки.

• Виберемо p = 3 і q = 11.
• Визначимо n = 3 * 11 = 33.
• Hайдем (p-1) * (q-1) = 20. Отже, d дорівнюватиме, наприклад, 3: (d=3).
• Виберемо число е за такою формулою: (e * 3) mod 20 = 1. Значить е дорівнюватиме, наприклад, 7: (e=7).
• Представимо повідомлення, що шифрується, як послідовність чисел в діапазоні від 0 до 32 (не забувайте, що закінчується на n-1). Літера А = 1, В = 2, С = 3.

Тепер зашифруємо повідомлення, використовуючи відкритий ключ (7,33)

C1 = (3 ^ 7) mod 33 = 2187 mod 33 = 9;
C2 = (1 ^ 7) mod 33 = 1 mod 33 = 1;
C3 = (2 ^ 7) mod 33 = 128 mod 33 = 29;

Тепер розшифруємо дані, використовуючи закритий ключ (3,33).

M1 = (9 ^ 3) mod 33 = 729 mod 33 = 3 (С);
M2 = (1 ^ 3) mod 33 = 1 mod 33 = 1 (А);
M3 = (29 ^ 3) mod 33 = 24389 mod 33 = 2 (В);

Дані розшифровані!

Розглянемо роботу асиметричного RSA . Він був запропонований трьома математиками Рональдом Рівестом ( R. Rivest), Аді Шаміром ( A. Shamir) та Леонардом Адльманом ( L. Adleman) у 1978 році.

Під простим числомбудемо розуміти таке число, яке ділиться тільки на 1 і на себе. Евклід у своїх «Початках» показав, що для будь-якого простого числа є більша проста кількість, тобто кількість простих чисел нескінченно.

Доказ.Припустимо, що існує найбільш проста кількість p, визначимо добуток всіх простих чисел P=2∙3∙5∙7∙…∙p.

Розглянемо число P+1. Воно чи саме є простим числом більшим pабо добутком простих чисел, які більші P. Ми дійшли протиріччя, отже кількість простих чисел нескінченна.

2∙3+1=7; 2∙3∙5+1=31; 2∙3∙5∙7+1=211;

2∙3∙5∙7∙11+1=2311; 2∙3∙5∙7∙11∙13+1=30031=59∙509.

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

Зрештою, під результатом операції i mod jбудемо рахувати залишок від цілісного поділу iна j.Щоб використати алгоритм RSA, треба спочатку згенерувати відкритий та секретний ключі, виконавши наступні кроки.

1. Виберемо два дуже великі прості числа рі q.

2. Визначимо nяк результат множення рна q (n = p · q).

3. Виберемо велике випадкове число, яке назвемо d. Це число має бути взаємно простим із результатом множення (Р - 1) · (Q - 1).

4. Визначимо таке число едля якого є істинним наступне співвідношення (е · d) mod ((p - 1) · (q - 1)) = 1.

5. Назвемо відкритим ключем числа еі n, а секретним ключем – числа dі n.

Тепер, щоб зашифрувати дані за відомим ключем ( е, n), необхідно зробити таке:

– розбити текст, що шифрується, на блоки, кожен з яких може бути представлений у вигляді числа M(i);

– зашифрувати текст, що розглядається як послідовність чисел M(i)за формулою З(i) = (M(i) e) mod n. Щоб розшифрувати ці дані, використовуючи секретний ключ (d, n),необхідно виконати такі обчислення: M(i)=(C(i) d) mod n. В результаті буде отримано безліч чисел M(i),які є вихідний текст.

Алгоритм RSA заснований на одній із доведених теорем Ейлера, окремий випадок якої стверджує, що якщо число nпредставимо у вигляді двох простих чисел pі q, то для будь-кого xмає місце рівність

x (p-1)(q-1) mod n = 1.

Для дешифрування RSA-повідомлень скористаємося цією формулою. Для цього зведемо обидві її частини до ступеня (- y):

(x(-y)(p-1)(q-1)) mod n= 1 (-y) = 1.

Тепер помножимо обидві її частини на x:

(x(-y)(p-1)(q-1)+1) mod n = 1· x = x.

Згадаймо тепер, як створювалися відкритий та закритий ключі. Ми підбирали dтаке, що

e·d+(p-1)(q-1) ·y = 1,

e d = (-y) (p-1) (q-1) +1.

Отже, в останньому виразі попереднього абзацу ми можемо замінити показник ступеня на число (e d).Отримуємо (x e · d) mod n = x. Щоб прочитати повідомлення c i = ((m i) e)mod nдостатньо звести його до ступеня dза модулем m:

((c i) d) mod n = ((mi) e · d) mod n = mi.

Наведемо простий приклад використання методу RSA для шифрування повідомлення CAB. Для простоти будемо використовувати дуже малі числа (на практиці використовуються великі числа).

1. Виберемо р= 3і q= 11.

2. Визначимо n= 3· 11=33.

3. Знайдемо (р-1) (q-1) = 20. Як dвиберемо будь-яке число, яке є взаємно простим з 20, наприклад d= 3.

4. Виберемо число е. Як таке число може бути взято будь-яке число, для якого задовольняється співвідношення (е· 3) mod 20 = 1,
наприклад, 7.

5. Представимо повідомлення, що шифрується, як послідовність цілих чисел в діапазоні 0...32. Нехай літера Азображається числом 1, літера У- Числом 2, а буква З- Числом 3. Тоді повідомлення можна представити у вигляді послідовності чисел 312. Зашифруємо повідомлення, використовуючи ключ (7, 33):

З(1)=(З 7) mod 33 = 2187 mod 33 = 9,

З(2) = (1 7) mod 33 = 1 mod 33 = 1,

З(З) = (2 7) mod 33 = 128 mod 33 = 29.

6. Спробуємо розшифрувати повідомлення (9, 1, 29), отримане в результаті зашифрування за відомим ключем, на основі секретного ключа (3, 33):

M(1) = (9 3) mod 33 = 729 mod 33 = 3,

М(2) = (1 3) mod 33 = 1 mod 33 = 1,

М(З) = (29 3) mod 33 = 24 389 mod 33 = 2.

Таким чином, в результаті розшифровування повідомлення отримано вихідне повідомлення CAB.

p align="justify"> Криптостійкість алгоритму RSA ґрунтується на припущенні, що виключно важко визначити секретний ключ по відомому відкритому, оскільки для цього необхідно вирішити задачу про існування дільників цілого числа. Це завдання не допускає в даний час ефективного (поліноміального) рішення. У зв'язку з цим для ключів, що складаються з 200 двійкових цифр (а саме такі числа рекомендується використовувати), традиційні методи пошуку дільників вимагають виконання величезної кількості операцій (близько 10 23).

Криптосистема RSA використовується в різних платформах і в багатьох галузях. Вона вбудовується в багато комерційних продуктів, кількість яких постійно збільшується. Її використовують операційні системи Microsoft, Apple, Sun та Novell. В апаратному виконанні алгоритм RSA застосовується у захищених телефонах, на мережевих платах Ethernet, на смарт-картах, широко використовується у криптографічному обладнанні фірми Zaxus (Rasal). Крім того, алгоритм входить до складу всіх основних протоколів для захищених комунікацій Internet, у тому числі S/MIME, SSL і S/WAN, а також використовується в багатьох установах, наприклад, в урядових службах, більшості корпорацій, державних лабораторіях та університетах .

Технологію шифрування RSA BSAFE використовують понад 500 мільйонів користувачів по всьому світу. Так як у більшості випадків при цьому використовується алгоритм RSA, то його можна вважати найбільш поширеною криптосистемою загального ключа у світі, і ця кількість має явну тенденцію до збільшення в міру зростання користувачів Internet.

Алгоритм шифрування з відкритим ключем RSAбув запропонований одним із перших наприкінці 70-х років ХХ століття. Його назва складена з перших букв прізвищ авторів: Р.Райвеста (R.Rivest), А.Шаміра (A.Shamir) та Л.Адлемана (L.Adleman). Алгоритм RSA є, напевно, найбільш популярним і широко застосовуваним асиметричним алгоритмому криптографічних системах.

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

1. Завдання перевірки числа на простоту є порівняно легким;
2. завдання розкладання чисел виду n = pq (р та q - прості числа); на множники є дуже важкою, якщо ми знаємо тільки n, а р і q - великі числа (це так зване завдання факторизації, докладніше про неї див. "Основні положення теорії чисел, що використовуються в криптографії з відкритим ключем").

Алгоритм RSA є блоковим алгоритмом шифрування, де зашифровані і незашифровані дані повинні бути представлені у вигляді цілих чисел між 0 і n -1 для деякого n .

Шифрування

Отже, розглянемо алгоритм. Нехай абонент А хоче передати зашифроване повідомлення абоненту Б. У цьому випадку абонент Б повинен підготувати пару (відкритий ключ; закритий ключ) та надіслати свій відкритий ключ користувачу А.

Першим етапом є генерація відкритого та закритого ключів. Для цього спочатку вибираються два великі прості числа Р і Q . Потім обчислюється добуток N:

Після цього визначається допоміжне число f:

f = (Р – l) (Q – 1).

Потім випадково вибирається число d< f и взаимно простое с f .

Числа d та N будуть відкритим ключем користувача, а значення е – закритим ключем.

Таким чином, на цьому етапі користувача має бути інформація, зазначена в наступній таблиці:

Оскільки користувач Б хоче отримати зашифроване повідомлення від користувача А, то користувач Б повинен відправити свій відкритий ключ (d, N) користувачу А. Числа Р і Q більше не потрібні, проте їх не можна нікому повідомляти; найкраще їх взагалі забути.

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

Другий етап – шифрування даних. Якщо абонент А хоче передати деякі дані абоненту Б, він має подати своє повідомлення у цифровому вигляді та розбити його на блоки m 1 , m 2 , m 3 , ... , де m i< N . Зашифроване повідомлення складатиметься з блоків з i.

Абонент А шифрує кожен блок свого повідомлення за формулою

c i = m i d mod N

використовуючи відкриті параметрикористувача Б, і пересилає зашифроване повідомлення С = (з 1, 2, 3, ...) по відкритій лінії.

Абонент Б, який отримав зашифроване повідомлення, розшифровує всі блоки отриманого повідомлення за формулою

Всі розшифровані блоки будуть такими ж, як і вихідні від користувача А.

Зловмисник, який перехоплює всі повідомлення і знає всю відкриту інформацію, зможе знайти вихідне повідомлення при великих значеннях Р і Q .

Приклад обчислень за алгоритмом

Нехай користувач А хоче передати користувачеві Б повідомлення. У цьому випадку спочатку користувач повинен підготувати відкритий і закритий ключі. Нехай їм вибрано, наприклад, такі параметри:

Р = 3, Q = 11, N = 3×11 = 33.

Тоді f = (Р - l) (Q - 1) = (3-1) (11-1) = 20.

Потім користувач Б вибирає будь-яке число d , що не має спільних дільників f (це необхідно для того, щоб зашифроване повідомлення можна потім однозначно відновити). Нехай d = 13 . Це число буде одним із компонентів відкритого ключа.

Криптосистема RSA кожному такті шифрування перетворює двійковий блок відкритого тексту m довжини size(n), що розглядається як ціле число, відповідно до формули: c = m e (mod n).

У цьому n = pq , де p і q – випадкові прості числа великої розрядності, які знищуються після формування модуля та ключів. Відкритий ключ складається з кількох чисел e і n . Підключ e вибирається як досить велике число з діапазону 1< e < φ(n), с условием: НОД(e, j(n)) = 1, где j(n) - наименьшее общее кратное чисел p–1 и q–1. Далі, вирішуючи у цілих числах x, y рівняння xe + yφ(n) = 1, належить d = х, тобто. ed = 1(j(n)). При цьому всім m виконується співвідношення m ed = m(n) , тому знання d дозволяє розшифровувати криптограми.

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

1. Перетворення вихідного тексту повинно виключати його відновлення на основі відкритого ключа.

2. Визначення закритого ключа на основі відкритого також має бути обчислювально нереалізованим. При цьому бажана точна нижня оцінка складності (кількості операцій) розкриття шифру.

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

Розглянемо побудову криптосистеми RSA простому прикладі.

1. Виберемо p = 3 та q = 11.

2. Визначимо n = 3 ∙ 11 = 33.

3. Знайдемо j(n) = (p - 1) (q - 1) = 20.

5. Виберемо число d, яке задовольняє 7d = 1(mod 20).

Легко побачити, що d = 3 (mod 20).

Представимо повідомлення, що шифрується, як послідовність цілих чисел за допомогою відповідності: А = 1, B = 2, С = 3, ..., Z = 26. Оскільки size(n) = 6 , то наша криптосистема може зашифровувати букви латинського алфавіту, що розглядаються як блоки, Опублікуємо відкритий ключ (e, n) = (7, 33) і запропонуємо іншим учасникам системи секретного зв'язку зашифровувати за його допомогою повідомлення, що направляються на нашу адресу. Нехай таким повідомленням буде CAB , яке у вибраному нами кодуванні набуває вигляду (3, 1, 2). Відправник повинен зашифрувати кожен блок і відправити зашифроване повідомлення на нашу адресу:

RSA(C) = RSA(3) = 3 7 = 2187 = 9(mod 33);
RSA(A) = RSA(1) = 1 7 = 1(mod 33);
RSA(B) = RSA(1) = 2 7 = 128 = 29(mod 33).

Отримавши зашифроване повідомлення (9, 1, 29), ми зможемо розшифрувати його на основі секретного ключа (d, n) = (3, 33), зводячи кожен блок у ступінь d = 3:

9 3 = 729 = 3 (mod 33);
1 3 = 1(mod 33);
29 3 = 24 389 = 2 (mod 33).

Для нашого прикладу легко знайти секретний ключ. Насправді це неможливо, т.к. для використання практично рекомендуються нині такі значення size(n) :

· 512-768 біт - для приватних осіб;

· 1024 біт – для комерційної інформації;

· 2048 біт - для таємної інформації.

Приклад реалізації алгоритму RSA представлений у лістингах 18.1 та 18.2 (компілятори – Delphi, FreePascal).

Лістинг 18.1.Приклад реалізації алгоритму RSA мовою Pascal

program Rsa;
($APPTYPE CONSOLE)
($IFDEF FPC)
($MODE DELPHI)
($ENDIF)

uses SysUtils, uBigNumber;

//Генератор випадкових чисел

var t: array of Byte;
var pos: Integer;
var cbox: array of Byte =
(237, 240, 161, 1, 130, 141, 205, 98, 27, 169, 181, 202, 173, 47, 114, 224, 35, 183, 79, 82, 153, 220, 172, 22, 17, 11, 200, 131, 14, 154, 167, 91, 250, 31, 213, 112, 126, 241, 236, 155, 198, 96, 87, 143, 244, 151, 134, 38, 129, 233, 186, 101, 41, 94, 231, 115, 113, 199, 51, 145, 229, 37, 69, 180, 85, 33, 207, 163, 102, 187, 4, 89, 7, 44, 75, 88, 81, 120, 10, 232, 221, 168, 230, 158, 247, 211, 216, 156, 95, 64, 242, 215, 77, 165, 122, 5, 15, 119, 100, 43, 34, 48, 30, 39, 195, 222, 184, 92, 78, 135, 103, 166, 147, 32, 60, 185, 26, 251, 214, 90, 139, 45, 73, 150, 97, 116, 136, 68, 219, 248, 191, 192, 16, 8, 243, 50, 132, 105, 62, 201, 204, 65, 0, 99, 182, 121, 194, 108, 160, 170, 56, 226, 206, 254, 117, 178, 9, 197, 234, 127, 58, 171, 40, 29, 177, 142, 3, 228, 188, 162, 212, 157, 49, 175, 174, 140, 70, 106, 123, 66, 196, 246, 179, 42, 218, 71, 217, 227, 18, 164, 24, 67, 159, 25, 111, 255, 193, 245, 2, 238, 133, 21, 137, 152, 109, 148, 63, 124, 203, 104, 54, 55, 223, 80, 107, 210, 225, 149, 252, 76, 12, 189, 93, 46, 23, 13, 36, 209, 61, 249, 110, 144, 86, 52, 253, 72, 28, 53, 57, 125, 59, 235, 84, 128, 208, 146, 20, 74, 6, 239, 190, 83, 19, 138, 118, 176);

процедура InicMyRandom;
var i: Integer;
var s:string;
begin
WriteLn("Введіть будь-який текст для ініціалізації генератора
випадкових чисел (до 256 символів):");
ReadLn(s);
i:= 1;
while (i<=255) and (i<=Length(s)) do

Електронний цифровий підпис (ЕЦП) - реквізит електронного документа, призначений для посвідчення джерела даних та захисту електронного документа від підробки.

Загальна схема

Схема електронного підпису зазвичай включає:

• алгоритм генерації ключових пар користувача;
• функцію обчислення підпису;
• функцію перевірки підпису.

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

Нині детерміновані схеми мало використовуються.

Функція перевірки підпису перевіряє, чи цей підпис відповідає цьому документу та відкритому ключу користувача. Відкритий ключ користувача доступний всім, тому будь-хто може перевірити підпис під даним документом.

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

Захищеність

Цифровий підпис забезпечує:

• Посвідчення джерела документа. Залежно від деталей визначення документа може бути підписано такі поля, як «автор», «внесені зміни», «мітка часу» тощо.
• Захист від змін документа. При будь-якій випадковій чи навмисній зміні документа (або підпису) зміниться хеш, отже, підпис стане недійсним.
• Неможливість відмовитися від авторства. Так як створити коректний підпис можна лише знаючи закритий ключ, а він відомий тільки власнику, то власник не може відмовитися від свого підпису під документом.

Можливі такі загрози цифровому підпису:

• Зловмисник може спробувати підробити підпис для вибраного ним документа.
• Зловмисник може спробувати підібрати документ до цього підпису, щоб підпис до нього підходив.
• Зловмисник може спробувати підробити підпис для будь-якого документа.

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

Тим не менш, можливі ще такі загрози системам цифрового підпису:

• Зловмисник, який викрав закритий ключ, може підписати будь-який документ від імені власника ключа.
• Зловмисник може обманом змусити власника підписати будь-який документ, наприклад, використовуючи протокол сліпого підпису.
• Зловмисник може підмінити відкритий ключ власника (див. управління ключами) на власний, видаючи себе за нього.

Алгоритми ЕЦП

• Американські стандарти електронного цифрового підпису: DSA, ECDSA

• Російські стандарти електронного цифрового підпису: ГОСТ Р 34.10-94 (нині діє), ГОСТ Р 34.10-2001
• Український стандарт електронного цифрового підпису: ДСТУ 4145-2002
• Стандарт PKCS#1 описує, зокрема, схему електронного цифрового підпису на основі алгоритму RSA

Керування ключами

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

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

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

Опис алгоритму RSA

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

Історія

Британський математик Кліффорд Кокс (Clifford Cocks), який працював у центрі урядового зв'язку (GCHQ) Великобританії, описав аналогічну систему у 1973 році у внутрішніх документах центру, але ця робота не була розкрита до 1977 року і Райвест, Шамір та Адлеман розробили RSA незалежно від роботи Коксу.

У 1983 році MIT був виданий патент 4405829 США, термін дії якого минув 21 вересня 2000 року.

Опис алгоритму

Безпека алгоритму RSA полягає в труднощі завдання розкладання на множники. Алгоритм використовує два ключі - відкритий (public) і секретний (private), разом відкритий та відповідний йому секретний ключі утворюють пару ключів (keypair). Відкритий ключ не потрібно зберігати в таємниці, він використовується для зашифрування даних. Якщо повідомлення було зашифровано відкритим ключем, розшифрувати його можна лише відповідним секретним ключем.

Генерація ключів

Для того, щоб згенерувати пару ключів виконуються такі дії:

1. Вибираються два великі прості числа і

2. Обчислюється їх твір

3. Обчислюється Функція Ейлера

4. Вибирається ціле таке, що і взаємно просте з

5. За допомогою розширеного алгоритму Евкліда знаходиться число таке, що

Число і використовується як шифртекст. Для розшифрування слід обчислити

Неважко переконатися, що під час розшифрування ми відновимо вихідне повідомлення:

З умови

слід, що

для деякого цілого , отже

Відповідно до теореми Ейлера:

Деякі особливості алгоритму

Генерація простих чисел

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

· При малому значенні відкритого показника (наприклад) можлива ситуація, коли виявиться, що . Тоді, і порушник легко зможе відновити вихідне повідомлення обчисливши корінь ступеня.

· Оскільки RSA є детермінованим алгоритмом, тобто. не використовує випадкових значень у процесі роботи, то порушник може використати атаку з вибраним відкритим текстом.

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

Вибір значення відкритого показника

RSA працює значно повільніше за симетричні алгоритми. Для підвищення швидкості шифрування відкритий показник вибирається невеликим, зазвичай 3, 17 або 65537. Ці числа в двійковому вигляді містять тільки дві одиниці, що зменшує кількість необхідних операцій множення при зведенні в ступінь. Наприклад, для зведення числа в ступінь 17 потрібно виконати лише 5 операцій множення:

має бути досить великим. В 1990 Міхаель Вінер (Michael J. Wiener) показав, що якщо вибирається невеликим, то виявляється досить великим і проблеми не виникає.

Довжина ключа

Число nповинно мати розмір не менше ніж 512 біт. В даний момент система шифрування на основі RSA вважається надійною, починаючи з розміру N 1024 біта.

Застосування RSA

Система RSA використовується для захисту програмного забезпечення та у схемах цифрового підпису. Також вона використовується у відкритій системі шифрування PGP.

Через низьку швидкість шифрування (близько 30 кбіт/с при 512 бітному ключі на процесорі 2 ГГц) повідомлення зазвичай шифрують за допомогою більш продуктивних симетричних алгоритмів з випадковим ключем ( сеансовий ключ), а за допомогою RSA шифрують лише цей ключ.

ІІ. Реалізація

Для прикладу було реалізовано програму для цифрового підписання файлів та перевірки підписів. Використовувався алгоритм RSA та сертифікати X.509. Сертифікат користувача вибирається із сховища сертифікатів windows.

Цифрові підписи зберігаються у файлі xml з ім'ям<имя исходного файла>.sig.xml

Фрагменти коду

public class Signature

private X509Certificate2 certificate;

private DateTime date;

private byte signedHash;

public X509Certificate2 Certificate

get (return certificate;)

set (certificate = value;)

public DateTime Date

get ( return date; )

set ( date = value; )

public void Sign(string input, X509Certificate2 cert)

this.certificate = новий X509Certificate2(cert);

date = DateTime.Now;

signedHash = ((RSACryptoServiceProvider)cert.PrivateKey).SignData(Utils.StringToBytes(stringToEncrypt),new MD5CryptoServiceProvider());

public bool IsValid(string input)

string stringToEncrypt = input + date.Ticks;

return ((RSACryptoServiceProvider)certificate.PublicKey.Key).VerifyData(Utils.StringToBytes(stringToEncrypt),new MD5CryptoServiceProvider(), signedHash);

public byte SignedHash

get ( return signedHash; )

set ( signedHash = value; )

void DisplaySignatureList()

FileSignatures fileSignatures = ReadSignatures(GetSignaturesFileName(fileNameTextBox.Text));

signatureListTextBox.Text = "";

foreach (Signature signaure in fileSignatures.Signaures)

string row="";

row+= signaure.Certificate.Subject;

row+=" "+signaure.Date.ToString();

string hash = GetFileHash(fileNameTextBox.Text);

bool valid = signaure.IsValid(hash);

row = "v" + row;

row = "x" + row;

signatureListTextBox.Text += row+"\r\n";

ІІІ. Література

1. С. Бернет, С. Пейн: Криптографія. Офіційний посібник RSA Security – М. «Біном», 2002
2. В. Зима: Безпека глобальних мережевих технологій - "БХВ-Петербург", 2003
3. Венбо Мао Сучасна криптографія: теорія та практика = Modern Cryptography: Theory and Practice. - М.: "Вільямс", 2005. - С. 768. ISBN 0-13-066943-1
4. Нільс Фергюсон, Брюс Шнайєр Практична криптографія: Practical Cryptography: Designing and Implementing Secure Cryptographic Systems. - М.: "Діалектика", 2004. - С. 432. ISBN 0-471-22357-3
5. Шнайєр, Брюс. Прикладна криптографія. Протоколи, алгоритми, вихідні тексти мовою Сі - М.: Видавництво ТРІУМФ, 2002 - 816с.: іл. ISBN 5-89392-055-4