Асиметричні методи шифрування. Основи модульної арифметики. Алгоритм шифрування з відкритим ключем RSA
До теперішнього часу ми розглядали симетричні методи шифрування. Але з появою мережі Інтернет та широким застосуванням криптозахисту інформації у комерційній діяльності виникла так звана проблема розподілу ключів. Проблема пов’язана зі значними незручностями, що виникають генерації, роздаванні, доставці, обліку та заміні секретних ключів. Крім того, ці операції вимагають значних затрат [21]. Зрозуміло, що державні органи, які забезпечують криптографічний захист інформації найвищого грифу таємності, не зважають а ні на вартість, а ні на незручності, та користуються разовими шифроблокнотами. Але для комерційного використання слід було відшукати нові, менш вартісні, але стійкі методи шифрування, які б дозволяли уникнути цієї проблеми. Ті ж самі проблеми виникли і у військових, які вже у 70-их роках минулого сторіччя передбачаючи бурхливий розвиток мікроелектроніки, розуміли, що в майбутньому ця проблема стане на шляху розвитку військових польових систем зв’язку.
Так виникла ідея асиметричного шифрування. Спочатку ідея була реалізована англійцями, але вони це зберігали у секреті. Вже після повторного винайдення методу американськими вченими Діффі, Хеллманом та Мерклем та після винайдення алгоритму RSA Ріверсом, Шаміром та Адлеманом стало відомо, що і метод, і аналогічний алгоритм були винайдені раніше англійськими вченими Еллісом, Коксом та Уильямсоном, які працювали у державній установі Великобританії, яка займається питаннями криптографічного захисту інформації.
Асиметричні методи шифрування передбачають у своєму алгоритмі використання двох ключів: відкритого й секретного. При цьому шифрування відбувається з використанням відкритого ключа, що надається для широкого користування отримувачем шифрованої інформації, а розшифрування – з використанням секретного ключа, що зберігається отримувачем криптограм у таємниці.
Але сама ідея була настільки незвичайна, що було необхідно спочатку довести можливість її реалізації. Тобто, як кажуть математики, довести теорему існування. Вона була доведена наступним чином.
Припустимо, що існують два абоненти, що листуються: абонент А та абонент В. Але їм відомо, що поштовий співробітник читає їх листи. Тому починають свої листи відправляти у металевій коробці. Листування ведеться наступним чином: абонент А навішує на коробку свій замок та відправляє до абонента В. Ключ від замку залишається у абонента А. Абонент В отримує коробку, навішує на неї свій замок, та відправляє коробку до абоненту А. Абонент В ключ від другого замку залишає у себе. Абонент А отримує коробку, знімає свій замок та відправляє коробку абоненту В. Абонент В отримує коробку, знімає свій замок та отримує повідомлення.
У алгоритму є два недоліки. Перший з них видний одразу – це необхідність двох додаткових пересилань. На жаль, є ще і другий – значно гірший недолік: в реальному шифруванні такий алгоритм працювати не може, оскільки при перешифруванні (навішення другого замка) перше розшифрування має проводитися останнім ключем (першим потрібно зняти замок, навішаний абонентом В). Але теорема існування була доведена.
Спосіб реалізації ідеї треба було шукати у математичній площині. І вона була знайдена у теорії чисел.
Для розуміння реалізації ідеї нам необхідно розглянути деякі її положення. Існують так звані оборотні та необоротні функції. Що це за поняття?
Розглянемо функцію
Можемо ми, знаючи значення Сзнайти значення n? Можемо. Дійсно
.
Отже, ця функція є оборотною.
Але існує клас функцій, де однозначно обчислити оборотне значення або неможливо, або вкрай важко. Цей клас функцій існує у так званій модульній (або модулярній) арифметиці, яка відноситься до теорії чисел. Розглянемо простий приклад.
Припустимо, зараз 9 година ранку. Ви домовляєтеся про зустріч через 6 годин. На який час ви будете домовлятися? Можна сказати: зустрічаємося о 15 годині, а можна й о 3 годині дня. Виникає питання – чому можна назвати один і той же час двома різними способами, але обидва значення будуть правильними? Подивимося на циферблат годинника – на ньому 12 значень для відліку годин. А тепер проведемо нескладні арифметичні розрахунки:
9 + 6 = 15,
а
15 – 12 = 3.
Але ці 3 години можна отримати іншим способом:
15|12
- 1
12
Інакше кажучи, ми отримане число годин 15 ділимо на модуль циферблату 12 та отримуємо залишок 3. У математиці це записується як
15 = 3(mod 12),
що означає, що число 15 дорівнює залишку 3 за модулем 12.
Залишок у модульній арифметиці прийнято називати “лишок” (російською – вычет).
Але можна легко переконатися, що і число 39 буде записано таким же чином
39 = 3(mod 12),
і число
51 = 3(mod 12)
і так далі.
Отже однозначно з’ясувати за лишком та модулем, яке число малося на увазі (не знаючи цього числа) неможливо, тобто функція є необоротною.
Головна теорема модульної арифметики стверджує, що будь-яке число може бути записане через його лишок за будь-яким модулем.
Друга теорема:
Арифметичні операції з числами, записаними за одним модулем, проводяться як звичайні арифметичні операції з їх лишками.
Наслідок з цієї теореми:
Якщо арифметичні операції з лишками за одним модулем призводять до отримання лишку, що ділиться на модуль без залишку, то отриманий лишок за цим модулем дорівнює нулю.
Дійсно, ми можемо записати
6(mod 12) + 3(mod 12) = 9(mod 12),
але
6(mod 12) + 3(mod 12) + 3(mod 12) = 12(mod 12) = 0(mod 12).
При цьому і
24(mod 12) = 0(mod 12), і 36(mod 12) = 0(mod 12), і т.д.
Аналогічно проводять операції множення, ділення, віднімання, возведення у ступень і т.д.
А далі, ознайомившись з правилами модульної арифметики, ми можемо розглянути шифрування за алгоритмом RSA [21].
Наприклад, абонент А хоче отримувати на свою адресу зашифровані повідомлення. Для цього він має опублікувати, наприклад, у телефонному довіднику, свій відкритий ключ. Як він його отримує? Користуючись спеціальною програмою шифрування за алгоритмом RSA він обирає два простих числа - p і q (напам’ятаємо, що прості числа, це числа, що діляться лише на себе та на одиницю). Умови вибору цих чисел:
p > q
і ці числа мають бути дуже великі. Але для простоти розрахунків ми обираємо числа
p = 17, q = 11.
Це секретний (закритий) ключ абонента А.
З закритого ключа абонент А розраховує відкритий ключ:
N = p•q = 17х11 = 187.
Крім числа N у відкритий ключ входить число e, яке обирається абонентом А за наступних умов:
е має бути простим числом та менше від q;
лишок k від операції (p – 1) • (q – 1) = k(mod e) не має дорівнювати нулю, тобто k ≠ 0.
Інакше кажучи, число, отримане з перемноження цих чисел, на має ділитися без залишку на е.
Для нашого випадку обираємо е = 7. Перевіряємо: 16х10 = 160, на 7 не ділиться.
Абонент А публікує свій відкритий ключ
N = 187
e = 7.
Абонент В хоче відправити абоненту А шифроване повідомлення. Зрозуміло, що відкрите повідомлення складається з окремих літер. Але абонент для шифрування користується комп’ютером. У комп’ютері кожна літера відповідає певному двійковому числу у відповідності до кодів ASCII.
Для кожної літери шифрування відбувається за формулою
С = Me (mod N),
де
М – літера, яку необхідно зашифрувати,
С – результат шифрування.
Припустимо, відкритим ключем абонента А шифрується буква Х. У ASCII коді ця літера відповідає числу 1011000, що дорівнює числу 88 у десятковому коді.
Тоді результат шифрування можна записати як
Сх = 887 (mod 187) = 881 (mod 187) x 882 (mod 187) x 884 (mod 187) =
= 88 (mod 187) х 7744 (mod 187) х 59969536 (mod 187) = 88 x 77 x 132 (mod 187) = 894432 (mod 187) = 11 (mod 187).
Абонент В відправляє повідомлення С = 11. Модуль повідомляти не треба, абоненту А він відомий.
Абонент А починає розшифрування. Але для цього йому потрібно розрахувати ще одне число d. Він обчислює його з чисел свого секретного ключа за відомим алгоритмом Евкліда
e•d = 1 [mod (p – 1) • (q – 1)]
(Увага! У формулі є лишок 1).
Для нашого випадку
7d = 1 (mod 160)
Звідки
d = 161 : 7 = 23.
Розшифрування ведеться за формулою
М = Сd (mod N).
Для нашого випадку
М = 1123 (mod 187) = [ 111 (mod 187) x 112 (mod 187) x 114 (mod 187) x 1116 (mod 187) ] = 11 x 121 х 55 x 154 (mod 187) = 88 (mod 187).
Лишок 88 відповідає літері Х.