3. Асиметричні алгоритми шифрування

Асиметричні алгоритми для шифрування інформації викоритстовують ключову пару <КО, КС>, де КО – відкритий (public) ключ, КС – секретний (private) ключ. Між відкритим і секретним ключем існує взаємно однозначна відповідність. Тобто, якщо змінити відкритий ключ, то зміниться секретний, і навпаки, якщо знінити секретний ключ, то зміниться відкритий. Якщо інформацію шифрувати відкритим ключем, то розшифровувати треба секретним, і навпаки, якщо шифрувати секретним, то розшифровувати треба відкритим. Відкритий ключ може бути опублікований для використання всіма користувачами системи обміну інформацією. Часто асиметричні алгоритми шифрування називають шифрами з відкритим ключем.

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

1. Асиметричний алгоритм 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 обмежує область їх застосування, але не перекреслює їх цінність.