Розкриття теми криптографії про відкритих ключах необхідно почати з історичного шляху виникнення даної задачі. Whitfield Diffie і Martin Hellman були першими, хто задався питанням про відкритому способі передачі ключів. Сталося це в 1976 році. У публікації були зроблені перші спроби розібратися з виниклою проблемою. Їх рішення не було позбавлене недоліків, однак поклало початок зовсім іншого способу мислення у сфері шифрованого передачі даних.
Передумови створення алгоритму Діффі-Хеллмана
Автентифікація та шифрування до цього моменту були можливі лише за допомогою загального секретного ключа. З розвитком технологій питання ставав більш гострим. Якщо 10 людям необхідний передавати дані між собою за небезпечним каналах, їм потрібно обмінюватися паролями один з одним. Дана задача виглядає цілком реальною. Навіть з урахуванням необхідності їх оновлення. Адже для 10 друзів знадобиться всього 45 секретних ключів. А якщо контактів буде 100? Знадобиться 4950 паролів. Ситуація наростає як сніжний ком.
Головним досягненням Діффі і Хеллмана стала правильна постановка питання і дотепна відповідь на нього. Вони припустили, що дані можна шифрувати одним способом, а розшифрування – іншим. Тобто мати 2 ключа. Той, що використовується для шифрування, можна залишити відкритим. Таким чином будь-яка людина зможе зашифрувати повідомлення, але розшифрувати зможуть лише володарі другого секретного ключа. Але як реалізувати алгоритм передачі такого ключа? Вчені змогли частково і на це дати відповідь.
Коротка математика: групи
Алгоритм або протокол Діффі-Хеллмана (далі DH) працює за допомогою простих чисел. Нехай а – це достатньо велике число, що належить безлічі простих чисел. Алгоритм передбачає використання числа розміром 250-500 байт. Нехай Zа – мультиплікативна група кільця відрахувань по модулю а, яка буде використана алгоритмом шифрування Діффі-Хеллмана. Вона складається з безлічі чисел 1, …, a-1.
Візьмемо якийсь елемент b з групи Zа і розглянемо нескінченну послідовність 1, b, b2, b3, b4, … З того факту, що група Za за визначенням є кінцевим безліччю, рано чи пізно розглянута послідовність {b} почне повторюватися. Покладемо bi = bj (i < j).
Тепер розділимо кожну частину рівності, bi (за модулем a) і отримаємо bj-i = 1. Це означає, що існує таке число k = j-i, для якого вірно bk = 1 (mod a). Найменше число k, для якого виконується дана рівність, називається порядком числа b. Щоб уникнути непорозуміння з іншою спеціальною літературою для пояснення системи Діффі-Хеллмана використовуються стандартні математичні позначення.
Таким чином, зводячи число b, називається твірним елементом, ступінь, ми отримуємо послідовність чисел (множина) 1, …, bk-1 . Кількість елементів цієї множини в точності дорівнює k.
Властивість множення за модулем a свідчить, що існує хоча б одне число b, яке породжує всі елементи групи Z*a . Інакше кажучи, існує число, для якого вірно k = a – 1. Дана властивість дозволяє представити числа групи Z*a у вигляді 1, b, b2, … ba-2 . Таке число b називається примітивним числом групи.
Надалі за ознаками групи легко доводиться, що безліч, породжене числом b, також є групою і успадковує всі властивості груп. Іншими словами, операції в межах породженої групи або підгрупи можна проводити точно таким же чином, як в групі з модуля a.
Розглянемо твердження. Для будь-якого елемента b його порядок є дільником числа a-1. Це легко показати. Нехай a=7. Число b = 3 – примітивне, т. к. 1, …, b5 = 1, 3, 2, 6, 4, 5. Тоді число h = 2 буде породжувати підгрупу 1, …, h2 = 1, 2, 4, так як h3 = 23 mod 7 = 1. h = 6 породжує підгрупу 1, 6. Розміри груп дорівнюють 3 і 2, відповідно. Очевидно, що вони є дільниками числа a-1 = 6.
Перший алгоритм DH
У початковій версії алгоритм працював за наступною схемою. Вибираються велике число a з безлічі простих і примітивний елемент b, породжує Z*a. Обидва числа a і b являють собою відкритий ключ, вони відомих усьому, в тому числі і зловмисникам. Як же тоді приховати повідомлення?
Саме на цьому кроці Діффі і Хеллман придумали дуже дотепний хід. Нехай у нас є дві людини, що між собою: А і Б. Спочатку А вибирає випадкове число x з Z*a , що є еквівалентом вибору числа з {1, …, a-1}. Потім він обчислює значення за формулою (bx mod a) і відправляє його Б. В свою чергу Б вибирає деяке число y з того ж безлічі, обчислює значення (mod by a) і відправляє результат назад А.
Таким хитрим способом виходить, що секретний ключ виглядає bxy . Завдяки властивості ступенів, яке свідчить gxy = (gy)x, співрозмовник А може обчислити потрібне значення і розшифрувати пересланную йому інформацію. І точно так само це значення обчислює співрозмовник Б. Таким чином, обидва мають однаковий секретний ключ.
Які проблеми відчуває зловмисник при такому обміні інформацією? Він може перехопити числа gx і gy. І навіть при знанні відкритих ключів задача обчислення gxy не є тривіальною, оскільки поки що не існує ефективного алгоритму пошуку потрібного значення в розподілі ключів Діффі-Хеллмана. Ця задача відома під назвою “проблема обчислення дискретного логарифма”.
Атака посередника
Однією з слабкостей первинного алгоритму Діффі-Хеллмана є його незахищеність проти атак посередника. Що це означає? Співрозмовник А знає, що він спілкується з якимсь обличчям, але конкретно з ким – він поняття не має. Таким чином, зловмисник може вклинитися в передачу інформації і імітувати співрозмовника Б при спілкуванні з А, і навпаки. Жоден з них не зможе запідозрити недобре.
Існує лише одна область застосування, при якій атаки на алгоритм Діффі-Хеллмана виключені. Це телефон і відеозв’язок. Тут співрозмовники здатні пізнати один одного, тому посередник не зможе втрутитися.
Підводні камені
Крім атаки посередника протокол DH таїть в собі масу інших проблем. Наприклад, одним з недоліків є випадок, коли в ролі утворює числа a виступає не примітив. Тоді він породжує лише підгрупу. Через звуження кількість можливих варіантів зловмиснику відкривається можливість їх перебору.
Проблем із-за цього недоліку можна уникнути, якщо кожен із співрозмовників перед початком обміну даними буде перевіряти, що числа a і b обрані правильно. Тобто a є простим числом, а b – примітивом. Однак коли справа доходить до дотримання безпеки допомогою виконання певних одноманітних необов’язкових кроків, користувачі часто їх ігнорують.
Інша серйозна проблема виникає на основі підгруп за модулем a. Якщо зловмисник вирішить поміняти gx на 1, щоб полегшити собі процес підслуховування, користувачі зможуть легко його знайти, перевіривши число на відповідність. Однак, якщо він замінить ключ числом з низьким порядком, користувачі не зможуть нічого запідозрити. А так як кількість елементів у множині з низьким порядком буде невелика, то зловмиснику для розшифровки потрібно буде перебирати невелику кількість варіантів.
Надійність простих чисел
В алгоритмі DH використовується велике і надійне число з безлічі простих. Як саме його вибрати? Розберемо по кроках.
Отриманий таким чином набір (a, k, b) може вважатися достатнім для використання в алгоритмі обміну ключами Діффі-Хеллмана. Відповідно, одержувачу повідомлення також потрібно перевірити значення, яке має бути ступенем b, і переконатися (наприклад, функцією символу Лежандра), що вона потрапляє в безліч, породжене числом b.
Використання підгруп
Головним мінусом вищеописаного алгоритму є недостатня ефективність. Припустимо, що довжина простого числа a дорівнює n біт, значить, k – n-1 біт. Виходить, всі ступені будуть мати довжину n-1. Тоді операція зведення в ступінь в середньому буде складатися з 3n/2 множень на a mod. Це досить великий процес.
Для того щоб впоратися з цією проблемою, було вирішено застосовувати підгрупи меншого розміру. Який виграш в продуктивності в такому випадку? Якщо число a складається з 2000 біт, тоді для обчислення bx потрібно 3000 операцій множення. Завдяки використанню підгруп, це число може бути скорочено до ~400. Це суттєве збільшення ефективності алгоритму робить можливим його всебічне застосування. Наприклад, алгоритм Діффі-Хеллмана з трьома і більше учасниками.
Якою повинна бути довжина числа a
Правильний підбір розмірів параметрів алгоритму Діффі-Хеллмана — завдання досить складне. Вимогою у світі криптографії є, наприклад, умову, щоб для злому системи зловмиснику знадобилося не менше 2128 кроків. Якщо в алгоритми симетричного шифрування дотримуватися подібна вимога досить легко, то в алгоритми з відкритим ключем це є реальною проблемою. Якщо дотримуватися вищеназване вимога, то довжина a повинна складатися щонайменше з 850 байт.
На практиці такий розмір створює великі проблеми продуктивності в системі, т. к. операції з відкритим ключем виконуються набагато довше, ніж, наприклад, у симетричних шифрованиях з ключами 128 або 256 біт. Тоді як бути? Мінімальна довжина відкритого ключа повинна починатися від 2048 біт. Хоча чим довший ключ, тим вище рівень безпеки. Слід розглядати в першу чергу можливості продуктивності системи і її вартість. Якщо вона дозволяє використовувати ключ розмірами 4096 біт, потрібно це робити.
Як проводиться оцінка необхідного рівня безпеки
Розміри ключів у симетричних шифрованиях залишаються незмінними (128, 256 біт) все життя системи, тоді як розміри відкритого ключа завжди являють собою змінну величину. Якщо потрібно розробити систему, яка повинна використовуватися 30 років і зберігати дані в секреті не менше 20 років після виведення системи з використання, то розмір ключа симетричного шифрування спочатку повинен бути достатньо великим, щоб захищати систему наступні 50 років.
З-за очевидних проблем продуктивності, з-за того, що в алгоритм Діффі-Хеллмана шифрування відбувається значно більшим числом операцій, вимоги до відкритих ключів відрізняються. Він залишається дійсним протягом одного року і захищає дані наступні 20 років, тобто в загальній складності використовується 21 рік. Зважаючи на його змінного розміру ключ кожен рік може бути змінена і створюватися все більш довгим, щоб забезпечити необхідний рівень безпеки.
Так, наприклад, найкращі оцінки показують, що ключ довжиною 256 байт здатний забезпечити захист даних на ~20 років, довжиною 384 байт – 35 років, а при довжині 512 байт – 47 років і т. д. Число 6800 біт, що гарантує, що зловмисникові потрібно 2128 кроків для його злому, отримано з таких оцінок. Однак це лише прогноз, довіряти яким потрібно з великою обережністю. Можна досить точно передбачити розвиток подій на 10 років вперед, але на 50 – це фантастика.
Практичні рекомендації
Наведемо кілька практичних порад щодо використання протоколу DH. Вибирати в якості k слід просте число розміром 256 біт. Це мінімум, який здатен забезпечити хоч скільки-то адекватний рівень безпеки проти атак. В якості a вибрати число, яке мало б вигляд Na+1, де N – деяке ціле число. Про розміри числа a було сказано раніше. Після цього вибирається випадкове число b і перевіряється на кілька умов. По-перше, воно не може бути одиницею. По-друге, bk = 1.
У свою чергу, будь-який учасник спілкування повинен переконатися в наступному:
- a і k – прості числа, довжина k складає 256 біт, довжина p досить велика.
- число k є дільником a-1.
- b не дорівнює 1 і bk = 1.
Ці умови слід перевіряти навіть при беззастережному довірі до джерела.
Висновок
Алгоритм DH є дотепним рішенням однією з серйозних проблем і донині активно використовується в модифікованому під сучасні вимоги безпеки вигляді в різних протоколах. Алгоритм Діффі-Хеллмана, наприклад, використовується в деяких частинах реалізації IKE. Проте її застосування повинно бути методичним і акуратним зважаючи на наявність очевидних проблем і серйозних підводних каменів.
