Ноу Інти, лекція, введення в криптографію з відкритим ключем
Анотація: У цій лекції Новомосковсктель познайомиться з найбільш важливим досягненням криптографов ХХ століття - асиметричною криптографією і дізнається, які математичні функції називаються односторонніми і як вони використовуються для шифрування, формування секретних ключів і цифрового підпису на електронних документах.
Мета лекції. Навіть поверхове знайомство з принципами шифрування з відкритим ключем.
Передумови створення методів шифрування з відкритим ключем і основні визначення
При використанні шифрування із закритим ключем виникають дві досить серйозні проблеми. Перша проблема полягає в виготовленні секретних ключів і доставці їх учасникам інформаційного обміну. При великій кількості і територіальної розподіленості учасників інформаційного обміну, що використовують канали зв'язку загального призначення, наприклад, звичайну або електронну пошту, часто буває складно гарантувати безпеку доставки такого ключа і його справжність. В "Поточні шифри і генератори псевдовипадкових чисел. Частина 2" навчального посібника проблема розподілу ключів для симетричного шифрування була докладно розглянута.
Багато криптографи працювали над вирішенням цих проблем, в результаті чого в другій половині сімдесятих років ХХ століття були розроблені принципово нові підходи, що дозволяють вирішити перераховані вище (і деякі інші) завдання. Основою послужило відкриття так званих асиметричних криптоалгоритмів. або методів, в яких процедури прямого і зворотного криптоперетворень виконуються на різних ключах і не мають між собою очевидних і легко простежуються зв'язків, які дозволили б по одному ключу визначити інший. Асиметричні алгоритми набагато більше засновані на властивостях математичних функцій, ніж алгоритми симетричного шифрування, що використовують в основному тільки операції перестановки і заміни. Великий внесок у ці дослідження внесли американські вчені У. Діффі (W. Diffie), Е. Хеллман (M. Hellman), Р. Меркль (R. Merkle). Вони першими запропонували шляхи вирішення обох завдань, які радикально відрізняються від усіх попередніх підходів до шифрування.
Асиметричні алгоритми шифрування називаються також алгоритмами з відкритим ключем. На відміну від алгоритмів симетричного шифрування (алгоритмів шифрування із закритим ключем), в яких для шифрування і розшифрування використовується один і той же ключ. в асиметричних алгоритмах один ключ використовується для шифрування, а інший, відмінний від першого, - для розшифрування. Алгоритми називаються асиметричними, так як ключі шифрування і розшифрування різні, отже, відсутня симетрія основних криптографічних процесів. Один з двох ключів є відкритим (public key) і може бути оголошений всім, а другий - закритим (private key) і повинен триматися в секреті. Який з ключів, відкритий або закритий, використовується для шифрування, а який для розшифрування, визначається призначенням криптографічного системи.
В даний час асиметричні алгоритми широко застосовуються на практиці, наприклад, для забезпечення інформаційної безпеки телекомунікаційних мереж, в тому числі мереж, що мають складну топологію; для забезпечення інформаційної безпеки в глобальній мережі Internet; в різних банківських і платіжних системах (в тому числі використовують інтелектуальні карти).
Алгоритми шифрування з відкритим ключем можна використовувати для вирішення, як мінімум. трьох завдань:
- Для шифрування переданих і збережених даних з метою їх захисту від несанкціонованого доступу.
- Для формування цифрового підпису під електронними документами.
- Для розподілу секретних ключів, які використовуються потім при шифруванні документів симетричними методами.
односторонні функції
Всі алгоритми шифрування з відкритим ключем засновані на використанні так званих односторонніх функцій. Односторонньої функцією (one-way function) називається математична функція. яку відносно легко обчислити, але важко знайти за значенням функції відповідне значення аргументу. Тобто, знаючи х легко обчислити f (x). але за відомим f (x) важко знайти підходяще значення x. Під словом "важко вирахувати" розуміють, що для цього буде потрібно не один рік розрахунків з використанням ЕОМ. Односторонні функції застосовуються в криптографії також в якості хеш-функцій (див. "Криптографічні хеш-функції"). Використовувати односторонні функції для шифрування повідомлень з метою їх захисту не має сенсу, так як назад розшифрувати зашифроване повідомлення вже не вийде. Для цілей шифрування використовуються спеціальні односторонні функції - односторонні функції з люком (або з секретом) - це особливий вид односторонніх функцій. мають певний секрет (люк), що дозволяє відносно швидко обчислити зворотне значення функції.
Для односторонньої функції з люком f справедливі наступні твердження:
- знаючи х. легко обчислити f (x),
- за відомим значенням f (x) важко знайти x,
- знаючи додатково деяку секретну інформацію, можна легко обчислити x.
Використання асиметричних алгоритмів для шифрування
У 70-х роках ХХ століття Діффі і Хеллмана запропонували принцип шифрування, заснований на використанні двох різних ключів, хоча і пов'язаних між собою, але влаштованих так, що обчислити по одному з них (відкритого) інший (закритий) практично неможливо. Цей принцип може бути використаний для вирішення проблеми постачання користувачів ключами шифрування / розшифрування, а точніше - для усунення цієї проблеми. Згідно Діффі і Хеллману попередньо розподіляються закриті ключі взагалі не повинні використовуватися для шифрування даних (так як секрет, який відомий більш ніж одній людині, - вже не секрет). Закритий ключ повинен бути відомий лише одній особі - його власнику. Такий принцип використання асиметричних алгоритмів отримав назву відкритого шифрування або шифрування з відкритим ключем.
Згідно з цим принципом, будь-який бажаючий може зашифрувати повідомлення відкритим ключем. Розшифрувати повідомлення зможе тільки власник закритого ключа. Нехай, наприклад, користувачі А і Б, які мають можливість обмінюватися електронними повідомленнями, використовують схему відкритого шифрування. Припустимо, користувач А повинен передати секретне повідомлення користувачу Б так, щоб ніхто інший не зміг його прочитати. Для цього необхідно виконати наступні дії:
- Користувач Б посилає користувачеві А свій відкритий ключ U будь-яким каналом зв'язку, наприклад, по електронній пошті.
- Користувач А шифрує своє повідомлення М отриманим відкритим ключем U і отримує зашифроване повідомлення С.
- Зашифроване повідомлення С пересилається користувачеві Б.
- Користувач Б розшифровує отримане повідомлення С своїм закритим ключем R.
Якщо операцію шифрування позначити як F. а операцію розшифрування як F-1. то схему протоколу обміну інформацією між користувачами можна зобразити, як на рис. 9.1.
Мал. 9.1. Схема відкритого шифрування
Використання відкритого шифрування знімає проблему розподілу ключів. Раніше користувачі перед обміном зашифрованими даними повинні були якимось чином по закритому каналу зв'язку узгоджувати використовуваний секретний ключ. Для цього вони могли зустрітися особисто або використовувати кур'єра. Якщо один з користувачів вважав потрібний змінити ключ. він повинен був передати на новий ключ своєму абоненту. Криптографія з відкритими ключами все спрощує. Тепер абоненти не повинні піклуватися про можливість компрометації особистого ключа. Користувачі системи зв'язку можуть абсолютно вільно обмінюватися відкритими ключами і зашифрованими ними повідомленнями. Якщо користувач надійно зберігає свій закритий ключ. ніхто не зможе прочитати повідомлення, що передаються.