Шифрування даних

Відкритий ключ обчислюється з секретного: kl = f (k2). Асиметричні алгоритми шифрування засновані на застосуванні односпрямованих функцій. Згідно з визначенням функція y = f (x) є односпрямованої, якщо її можна легко обчислити для всіх можливих варіантів x, а для більшості можливих значень y досить складно обчислити таке значення x, при якому y = f (x).

Прикладом односпрямованої функції може служити множення двох великих чисел: N = S х G. Само по собі, з точки зору математики, таке множення є простою операцію. Однак зворотна операція (розкладання N на два великих множника), звана також факторизації, за сучасними тимчасовим оцінками являє собою досить складну математичну задачу.

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

Алгоритм Діффі-Хеллмана. У 1976 році Уітфілд Діффі (Whitfield Diffie) і Мартін Хеллман (Martin Hellman) розробили свою систему шифрування з відкритим ключем. Система Діффі-Хеллмана розроблялася для вирішення проблеми поширення ключів при використанні систем шифрування з секретними ключами. Ідея полягала в тому, щоб застосовувати безпечний метод узгодження секретного ключа без передачі ключа будь-яким іншим способом. Отже, необхідно було знайти безпечний спосіб отримання секретного ключа за допомогою того ж методу зв'язку, для якого розроблялася захист. Суть алгоритму Діффі-Хеллмана полягає в наступному. Припустимо, що двох точках (S1 і S2) потрібно встановити між собою безпечне з'єднання, для якого необхідно узгодити ключ шифрування.

| S1 і S2 приймають до використання два великих цілих числа a і b, причому 1 <a <b.

| S1 вибирає випадкове число i і обчислює I = ai? mod b. S1 передає I абоненту S2.

| S2 вибирає випадкове число j і обчислює J = aj? mod b. S2 передає J абоненту S1.

| S1 обчислюєk1 = Ji? modb.

| S2 обчислюєk2 = Ij? modb.

Маємо k1 = k2 = ai? j х mod b, отже, k1 і k2 є секретними ключами, призначеними для використання при передачі інших даних.

Навіть якщо допустити, що зловмисникові якимсь чином вдасться прослухати переданий трафік, то йому будуть відомі a, b, I і J. Проте залишаються в секреті i і j. Рівень безпеки системи залежить від складності знаходження i при відомому I = ai? mod b. Це завдання називається завданням дискретного логарифмування і вважається дуже складною (тобто за допомогою сучасного обчислювального обладнання її вирішити практично неможливо), якщо числа дуже великі. Отже, a і b необхідно вибирати дуже ретельно. Наприклад, обидва числа b і (b – 1) / 2 повинні бути простими і мати довжину не менше 512 біт. Рекомендована довжина чисел становить 1024 біта.

Алгоритм RSA був розроблений в 1978 році трьома співавторами і отримав свою назву за першими літерами прізвищ розробників (Rivest, Shamir, Adleman). В основі стійкості алгоритму варто складність факторизации великих чисел і обчислення дискретних логарифмів. Основний параметр алгоритму RSA – модуль системи N, по якому проводяться всі обчислення в системі, а N = R х S (R і S – секретні випадкові прості великі числа, зазвичай однаковою розмірності).

Секретний ключ k2 вибирається випадковим чином і повинен відповідати таким умовам: 1 <k2 <F (N) і НСД (k2, F (N)) = 1, де НСД – найбільший спільний дільник. Іншими словами, k1 повинен бути взаємно простим із значенням функції Ейлера F (N), причому останнє дорівнює кількості позитивних цілих чисел в діапазоні від 1 до N, взаємно простих з N, і обчислюється як F (N) = (R – 1)? (S – 1).

Відкритий ключ kl обчислюється зі співвідношення (k2 х kl) = 1? mod F (N). Для цього використовується узагальнений алгоритм Евкліда (алгоритм обчислення найбільшого загального дільника). Зашифровки блоку даних M за алгоритмом RSA виконується наступним чином: C = Mkl? mod N. Оскільки в реальній криптосистеме з використанням RSA число k1 дуже велике (в даний час його розмірність може доходити до 2048 біт), пряме обчислення Mk1 нереально. Для його отримання застосовується комбінація багаторазового зведення M в квадрат з перемножением результатів. Звернення даної функції при великих размерностях нездійсненно; іншими словами, неможливо знайти M за відомим C, N і kl. Однак, маючи секретний ключ k2, за допомогою нескладних перетворень можна обчислити M = Ck2? mod N. Очевидно, що, крім власне секретного ключа, необхідно забезпечувати секретність параметрів R і S. Якщо зловмисник добуде їх значення, то зможе обчислити і секретний ключ k2.

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