7. Криптографія з відкритим ключем. Принципи побудови криптосистем з відкритим ключем.

Розробка засобів криптографії з відкритим ключем виявилася найбільшою і, можливо, єдиною революцією у всій історії криптографії. Від самих витоків криптографії до теперішнього часу практично всі криптографічні системи базувалися на виконанні елементарних засобів підстановки і перестановки. Після тисяч років роботи з алгоритмами, які повинні були, по суті, використовуватися вручну, істотним просуванням вперед в області традиційної криптографії виявився винахід барабанних шифрувально-дешифрувальних машин. Електромеханічний барабан відкрив можливості для розробки жахливо складних систем шифрування. З появою комп'ютерів з'явилися ще більш складні системи, найбільш яскравою з яких виявився алгоритм LUCIFER фірми IBM, з якого згодом виник стандарт шифрування даних (DES). Але і барабанні шифрувальні машини, і DES, хоча і знаменували істинно значне просування у справі шифрування, в своїй основі використовували прозаїчні засоби підстановки і перестановки.

Криптографія з відкритим ключем забезпечує радикальний поворот у бік від усього, що робилося раніше. Насамперед, алгоритми криптографії з відкритим ключем використовують математичні функції, відмінні від підстановок і перестановок. Але більш важливо те, що методи криптографії з відкритим ключем є асиметричними в тому сенсі, що вони припускають використання двох різних ключів, на відміну від методів симетричного традиційного шифрування, де передбачається тільки один ключ. Як ми побачимо нижче, ідея застосування двох ключів спричинила глибокі зміни і в підходах до забезпечення конфіденційності, і в області розподілу ключів, і в процедурах аутентифікації.

Перед тим як приступити до розгляду цього питання, ми повинні сказати кілька слів про деякі з широко поширених помилок, що стосуються шифрування з відкритим ключем. Однією з таких помилок є твердження, що шифрування з відкритим ключем більш захищене від криптоаналізу, ніж традиційне шифрування. Подібну заяву було зроблено, наприклад, у знаменитій статті Гарднера (Gardner) [GARD77] з популярного журналу Scientific American. Насправді ж захист будь-якої схеми шифрування залежить від довжини ключа та обсягу обчислювальної роботи, необхідної для злому шифру. У цьому сенсі немає принципової відмінності між традиційним шифруванням і шифруванням з відкритим ключем, і жодна з цих схем не має переваги перед іншою з точки зору криптоаналізу.

Другим помилковим є твердження, що шифрування з відкритим ключем виявляється універсальним підходом, що робить традиційне шифрування безнадійно застарілим. Навпаки, зважаючи на занадто високі вимоги з боку схем шифрування з відкритим ключем до обчислювальних ресурсів, відмова від схем традиційного шифрування видається дуже малоймовірною. Як було зазначено у [DIFF88] одним з відкривачів методу шифрування з відкритим ключем, "майже повсюдно застосування шифрування з відкритим ключем обмежується сферою управління ключами і додатками цифрового підпису".

Нарешті, вважається, що розподіл ключів при шифруванні з відкритим ключем є тривіальним завданням в порівнянні з досить заплутаною процедурою квитування (підтвердження встановлення зв'язку), використовуваної у випадку традиційного шифрування. Насправді у випадку шифрування з відкритим ключем для цього потрібен спеціальний протокол, власне кажучи, що припускає існування деякого центрального агента, а застосовувані у своїй процедури є ні більш простими, ні більш ефективними, ніж ті, які потрібні для традиційного шифрування (див. , наприклад, відповідний розділ в [NEED78]).

Чимало результатів теорії криптосистем на основі шифрування з відкритим ключем випливають з результатів теорії чисел. Якщо ви досить підготовлені, щоб розібратися в системах криптографії, представлених в цьому розділі, глибокого розуміння відповідних результатів теорії чисел вам не буде потрібно. Однак для кращого з'ясування суті алгоритмів шифрування все ж потрібно розуміння деяких результатів теорії чисел.

Принципи побудови криптосистем з відкритим ключем

Ідея застосування методів криптографії з відкритим ключем виникла із спроб знайти рішення двох з найбільш складних проблем, що виникають при використанні традиційного шифрування. Першою проблемою є розподіл ключів, яке вже розглядалося в певних деталях раніше.

Як ви вже бачили, розподіл ключів при традиційному шифруванні вимагає, щоб обидві приймаючі участь у обміні даними сторони або (1) вже мали загальний ключ, який якимось чином був ним доставлений, або (2) використовували послуги деякого центру розподілу ключів. Уітфідц Діффі (Whitfield Diffie), один з відкривачів методу шифрування з відкритим ключем (разом з Мартіном Хеллманом (Martin Hellman), обидва в той час працювали в Станфордському університеті), вважав, що друга з цих вимог суперечить самій сутності криптографії - можливості забезпечити повну секретність вашої власної кореспонденції. Як він зауважив в [DIFF88], "Який сенс має розробка неприступної криптосистеми, якщо її користувачі повинні використовувати свої секретні ключі спільно з деяким центром розподілу ключів, який може бути скомпрометований або зломщиком, або судовим рішенням?"

Другою проблемою, яку сформулював Діффі і яка, очевидно, не пов'язана з першою, є проблема "цифрових підписів". Якщо використання криптографії отримало дуже широке поширення, і не тільки в галузі військової справи, а й в області комерції і приватних комунікацій, то електронні повідомлення і документи потребують еквівалентах підписів, що використовуються в паперових документах. Інакше кажучи, чи можна розробити метод, за допомогою якого обидві сторони могли б переконатися в тому, що цифрове повідомлення було відправлено цією конкретною особою? Ця вимога виявляється дещо ширше, ніж вимога аутентифікації.

Діффі і Хеллман прийшли до свого відкриття в 1976 році [DIFF76a, b], розробивши метод, за допомогою якого вирішувалися обидві вищезгадані проблеми і який радикально відрізнявся від усіх відомих раніше підходів в криптографії за всю її чотирьохтисячолітню історію.

Алгоритми шифрування з відкритим ключем залежать від одного ключа для шифрування і іншого, пов'язаного з першим, ключа для дешифрування. Ці алгоритми мають наступну важливу особливість.

■ З точки зору обчислень нереально визначити ключ дешифрування, знаючи тільки використовуваний криптографічний алгоритм і ключ шифрування.

Крім того, деякі алгоритми (наприклад, RSA) мають таку властивість.

■ Будь-який з цих двох пов'язаних ключів може служити для шифрування, і тоді інший може застосовуватися для дешифрування.

На рис. 7.1. показана загальна схема процесу шифрування з відкритим ключем (порівняйте з рис. 2.1), яка виглядає наступним чином.

1. Кожна кінцева система в мережі генерує пару ключів для шифрування і дешифрування одержуваних повідомлень.

2. Кожна з систем публікує свій ключ шифрування, розміщуючи його ключ у відкритому для всіх реєстрі або файлі. Цей і є відкритий ключ. Другий ключ, відповідний відкритого, залишається в особистому володінні.

3. Якщо користувач А збирається послати повідомлення користувачу В, він шифрує повідомлення, використовуючи відкритий ключ користувача В.

4. Коли користувач В отримає повідомлення, він дешифрує його за допомогою свого особистого ключа. Інший одержувач не зможе дешифрувати повідомлення, оскільки особистий ключ B знає тільки В.

В рамках цього підходу всі учасники мають доступ до відкритих ключів, а особисті ключі генеруються на місці кожним учасником для себе і тому їх ніколи не доводиться розподіляти. До тих пір поки системі вдається зберігати свій особистий ключ в секреті, вхідні повідомлення виявляються захищеними. В будь-який момент система може змінити свій особистий ключ і опублікувати відповідний йому відкритий ключ, який замінює старий відкритий ключ.

У табл. 7.1 порівнюються деякі важливі характеристики традиційного шифрування і шифрування з відкритим ключем. Щоб розрізняти ці два підходи, ми будемо називати ключі, призначені для традиційного шифрування, секретними ключами. Два ключа, за допомогою яких здійснюється шифрування з відкритим ключем, називатимуться, відповідно, відкритим ключем і особистим ключем. Особистий ключ, звичайно ж, теж повинен зберігатися в секреті, але називається особистим ключем, а не секретним ключем щоб уникнути плутанини з ключем схеми традиційного шифрування.

Рис. 7.1. Шифрування з вікдритим ключем

Таблиця 7.1. Традиційне шифрування і шифрування з відкритим ключем

Традиційне шифрування	Шифрування з відкритим ключем
Необхідно для роботи	Необхідно для роботи
Один алгоритм з одним і тим же ключем служить і для шифрування, і для дешифрування Відправник і одержувач повинні використовувати однакові алгоритм і ключ	І для шифрування, і для дешифрування використовується алгоритм, але два ключа: один ключ для шифрування, а інший - для дешифрування Відправник і одержувач повинні мати по одному з пари відповідних ключів (не один і той же)
Необхідно для захисту	Необхідно для захисту
Ключ повинен зберігатися в секреті Повинно бути неможливо або, принаймні, практично неможливо розшифрувати повідомлення за відсутності додаткової інформації Знання алгоритму та наявності зразків шифрованого тексту має бути недостатньо для того, щоб відновити ключ	Один з двох ключів повинен зберігатися в секреті Повинно бути неможливо або, принаймні, практично неможливо розшифрувати повідомлення за відсутності додаткової інформації Знання алгоритму і одного з ключів і наявності зразків шифрованого тексту має бути недостатньо для того, щоб відновити другий ключ

Давайте розглянемо основні елементи схеми шифрування з відкритим ключем більш докладно, використовуючи рис. 7.2 (порівняйте з рис. 2.2 в розділі 2). Отже, є деякий джерело повідомлень А, що створює повідомлення X = [X₁, Х₂, ..., Х_M] у вигляді відкритого тексту. Всі М елементів X є буквами деякого кінцевого алфавіту. Повідомлення адресовано одержувачу В. Адресат В генерує пов'язану пару ключів: відкритий ключ KU_b і особистий ключ KR_b. Ключ KRb залишається відомим тільки користувачеві В, тоді як ключ KU_b публічно доступний і, таким чином, виявляється доступним відправнику А.

Маючи повідомлення X і ключ шифрування KU_b в якості вхідних даних, відправник А формує шифрований текст Y = [Y₁, Y₂, ..., Y_N] наступним чином:

Y = E_KUb(X)

Передбачуваний одержувач, володіючи відповідним особистим ключем, зможе звернути це перетворення:

X = D_KRb(Y).

Противник, спостерігаючи Y і маючи доступ до KU_b, але не до KR_b або X, повинен буде намагатися відновити X та / або KR_b. Передбачається, що противник знає алгоритми шифрування (Е) і дешифрування (D). Якщо противника цікавить тільки дане конкретне повідомлення, то він зосередить свої зусилля на відновленні X за допомогою отримання оцінок для відкритого тексту. Але часто противник буває зацікавлений у можливості читання і наступних повідомлень. У такому випадку буде зроблена спроба відновити ключ KR_b шляхом генерування для нього оцінки KR_b.

Рис. 7.2. Криптосистема з відкритим ключем: захист

Ми вже згадували вище, що будь-який з двох зв'язаних ключів може застосовуватися для шифрування, при цьому передбачається, що інший буде служити для дешифрування. Це дає можливість реалізувати різні криптографічні схеми. І якщо схема, показана на рис. 7.2, забезпечує конфіденційність, то рис. 7.1 (б) і рис. 7.3 показують, як використовувати шифрування з відкритим ключем для аутентифікації:

У цьому випадку відправник А готує повідомлення адресату В і перед відправленням шифрує це повідомлення за допомогою особистого ключа користувача А. Одержувач В може дешифрувати це повідомлення, використовуючи відкритий ключ А. Зважаючи на те що повідомлення було зашифровано особистим ключем відправника А, тільки він і міг підготувати це повідомлення. Тому в даному випадку все шифрування повідомлення виступає в якості цифрового підпису. Крім того, неможливо змінити повідомлення без доступу до особистого ключа користувача А, тому повідомлення вирішує і завдання ідентифікації відправника, і завдання підтвердження цілісності даних.

У схемі, про яку йде мова, шифрується все повідомлення, яке, хоч і ідентифікує відправника, і підтверджує цілісність вмісту, вимагає досить багато пам'яті. Кожен документ, щоб його можна було використовувати, повинен зберігатися у вигляді відкритого тексту. Ще один екземпляр документа повинен зберігатися у вигляді шифрованого тексту, щоб у разі спору можна було б відновити джерело і вміст оригіналу. Більш ефективним способом досягнення того ж результату є шифрування невеликого блоку бітів, що є функцією документа. Такий блок, званий аутентифікатором (authenticator), повинен мати таку властивість, щоб не можна було змінити документ без зміни аутентифікатора. Якщо аутентифікатор буде зашифрований з використанням особистого ключа відправника, він служитиме підписом, що засвідчує джерело, вміст і порядок відправки повідомлень.

Важливо підкреслити, що тільки що описаний процес шифрування не забезпечує конфіденційності. Це означає, що пересланому таким чином повідомленню гарантований захист від зміни, але не від перехоплення. Це очевидно в тому випадку, коли для форматування підпису використовується тільки частина повідомлення, оскільки тоді залишок повідомлення передається відкритим текстом. Але навіть у випадку повністю зашифрованого повідомлення, як показано на рис. 7.3, конфіденційність не забезпечується зважаючи на те, що будь-який сторонній спостерігач може розшифрувати передане повідомлення за допомогою відкритого ключа відправника.

Однак, можна забезпечити як аутентифікацію, так і конфіденційність повторним використанням схеми шифрування з відкритим ключем (рис. 7.4):

У даному випадку ми починаємо, як і колись, з шифрування повідомлення допомогою особистого ключа відправника. Це забезпечує цифровий підпис. Потім ми шифруємо результат знову, але вже використовуючи відкритий ключ одержувача. Кінцевий шифрований текст зможе дешифрувати тільки передбачуваний адресат, оскільки тільки він один має відповідний особистий ключ. Таким чином, конфіденційність забезпечується. Незручність цього підходу полягає в тому, що алгоритм шифрування з відкритим ключем, який виявляється досить складним, повинен при кожній передачі даних застосовуватися чотири рази, а не два.

Рис. 7.3 Криптосистема з відкритим ключем: аутентифікація

Рис.7.4 Криптосистема з відкритим ключем: захист і аутентифікація

Застосування криптосистем з відкритим ключем

Перш ніж перейти до наступних питань, необхідно роз'яснити один аспект криптосистем з відкритим ключем, який в іншому випадку може породити непорозуміння. Криптосистеми з відкритим ключем характеризуються використанням криптографічного алгоритму з двома ключами, один з яких залишається в особистому користуванні, а другий відкритий для всіх. Залежно від програми відправник використовує або свій особистий ключ, або відкритий ключ одержувача, або ж обидва, якщо потрібно виконати якусь спеціальну криптографічну функцію. У найширших межах використання криптосистем з відкритим ключем можна віднести до трьох категорій.

• Шифрування / дешифрування. Відправник шифрує повідомлення з використанням відкритого ключа одержувача.

• Цифровий підпис. Відправник "підписує" повідомлення за допомогою свого особистого ключа. Підпис виходить в результаті застосування криптографічного алгоритму до повідомлення або до невеликого блоку даних, що є функцією повідомлення.

• Обмін ключами. Дві сторони взаємодіють, щоб обмінятися сеансовим ключем. При цьому можливо декілька різних підходів, які передбачають застосування особистих ключів однієї або обох сторін.

Одні алгоритми підходять для всіх трьох типів застосування, тоді як інші призначені тільки для однієї або двох з цих категорій, можливості їх застосування зазначені в табл. 7.2.

Таблиця 7.2. Застосування криптосистем з відкритим ключем

Алгоритм	Шифрування / дешифрування	Цифровий підпис	Обмін ключами
RSA	Так	Так	Так
Діффі-Хеллмана	Ні	Ні	Так
DSS	Ні	Так	Ні

Умови застосування методів криптографії з відкритим ключем

Криптосистема, варіанти якої показані на рис. 7.2-7.4, залежить від криптографічного алгоритму, що припускає застосування двох пов'язаних ключів. Діффі і Хеллман припустили без доказу, що такі алгоритми існують. Однак вони вказали умови, яким повинні задовольняти такі алгоритми [DIFF76b].

1. Для сторони B процес генерування пари ключів (відкритий ключ KU_b, особистий ключ KR_b) не повинен викликати обчислювальних труднощів.

2. Для відправника А не повинен викликати обчислювальних труднощів процес створення шифрованого тексту за наявності відкритого ключа та повідомлення М, яке потрібно зашифрувати:

3. Для отримувача В не повинен викликати обчислювальних труднощів процес дешифрування отриманого шифрованого тексту за допомогою особистого ключа з метою відновлення оригінального повідомлення:

4. Для противника має бути неможливим з точки зору обчислювальних можливостей відновлення особистого ключа KR_b з наявного відкритого ключа KU_b.

5. Для противника має бути неможливим з точки зору обчислювальних можливостей відновлення оригінального повідомлення М з наявних відкритого ключа KU_b і шифрованого тексту C.

До цих вимог можна додати ще одне, яке, хоча і представляється, загалом, корисним, не є необхідним для всіх додатків, що реалізують криптосистеми з відкритим ключем.

6. Функції шифрування і дешифрування можуть застосовуватися в будь-якому порядку:

Перераховані вимоги у своїй сукупності досить складні для виконання, що, очевидно, підтверджується тим, що за кілька десятиліть, що минули з часу відкриття методу криптографії з відкритим ключем, тільки один такий алгоритм отримав широке визнання.

Перед тим як приступити до роз'яснення причин, за якими ці вимоги виявляються складними для виконання, давайте спробуємо представити їх в деякому більш зручному вигляді. Ці вимоги зводяться до необхідності знаходження деякої односторонньої функції з лазівкою. Односторонньої функцією називається функція, що відображає свої аргументи на деякий діапазон значень так, що кожне значення функції має унікальне зворотне значення, при цьому значення функції вирахувати легко, а зворотні - практично неможливо.

Y = f(X) обчислюється легко

X = f ^-1(X) практично не піддається обчисленню

У загальному випадку термін "легко обчислювана" означає, що проблема вирішується за поліноміальний час, що розглядається як функція довжини значення, що вводиться. Так, якщо довжина значення, що вводиться дорівнює n бітів, то час, необхідний для обчислення функції пропорційно n^a, де a є фіксованою константою. Такі алгоритми називаються алгоритмами, що належать класу Р. Термін "практично необчислюваний" позначає більш розмите поняття. У загальному випадку можна сказати, що функція є практично необчислюваною, якщо зусилля по її обчисленню зростають швидше, ніж поліноміальна функція від довжини значення, що вводиться. Наприклад, якщо вводиться значення має довжину n бітів і час, необхідний для обчислення функції, пропорційно 2ⁿ, то така функція вважається практично необчислюваною. На жаль, для кожного конкретного алгоритму дуже непросто з'ясувати, чи відображає цей алгоритм зазначену ступінь складності. До того ж у визначенні звичайного поняття обчислювальної складності алгоритму розглядаються оцінки складності або в найгіршому випадку, або в середньому. Для криптографії ці оцінки марні, криптографія вимагає практичної необчислюваності зворотної функції майже для будь-якого значення, що вводиться, а не для найгіршого або середнього випадку. Короткий огляд понять, про які тут йдеться, дається в доповненні 6A.

Повернемося до визначення односторонньої функції з лазівкою - така функція передбачається легко обчислюваною в одному напрямку і практично необчислюваною в іншому у відсутності додаткової інформації. При наявності додаткової інформації зворотна функція може бути обчислена за поліноміальний час. Підводячи підсумок, можна сказати так: односторонні функції з лазівкою є такими оборотними функціями f_k, для яких

Y = f_k(X) обчислюється легко, якщо відомі k і X

X = f_k^-1 (Y) обчислюється легко, якщо відомі k і Y

X = f_k^-1(Y) практично не піддається обчисленню,

якщо Y відомо, а k - ні.

Таким чином, для розробки практично застосовної схеми шифрування з відкритим ключем потрібно знайти підходящу односторонню функцію з лазівкою.

Криптоаналіз схем шифрування з відкритим ключем

Як і у випадку традиційного шифрування, схема шифрування з відкритим ключем уразлива з точки зору аналізу з перебором всіх ключів. І контрзаходи тут ті ж - використання довгих ключів. Проте в даному випадку є й інші варіанти захисту. Криптосистеми з відкритим ключем залежать від деякої оборотної математичної функції зі спеціальними властивостями. Складність обчислення такого роду функцій може залежати не лінійно від числа бітів у ключі, а рости більш швидко. Тому довжина ключа повинна бути досить великою для того, щоб зробити аналіз з перебором всіх ключів практично нездійсненним, але досить малої для того, щоб на практиці можна було використовувати операції шифрування і дешифрування. Пропоновані для використання на практиці довжини ключів, звичайно ж, забезпечують практичну неефективність аналізу з перебором всіх ключів, але при цьому швидкість шифрування / дешифрування виявляється занадто повільної для того, щоб відповідні алгоритми можна було рекомендувати для універсального застосування. Тому, як уже згадувалося вище, шифрування з відкритим ключем в даний час обмежується областями управління ключами і додатками цифрового підпису.

Іншою формою атаки є спроба знайти спосіб обчислення особистого ключа за відомим відкритому ключу. На сьогоднішній день немає математичного доказу неможливості такої форми атаки ні для одного алгоритму шифрування з відкритим ключем. З цієї точки зору будь-який конкретний алгоритм даного типу, включаючи широко поширений алгоритм RSA, виявляється не вселяючим довіри. А історія криптографії показує, що проблема, яка здається нерозв'язною, може виявитися цілком вирішуваною, якщо подивитися на неї з деякої іншої, абсолютно нової точки зору.

Нарешті, існує форма атаки, застосовна тільки до систем з відкритим ключем. Ця форма, по суті, є формою аналізу з імовірним текстом повідомлення. Припустимо, наприклад, що має бути відправлено повідомлення, що складається виключно з 56-бітового ключа DES. Противник може зашифрувати всі можливі ключі, використовуючи відкритий ключ, що дозволить йому дешифрувати подібне повідомлення за допомогою простого порівняння зразків з переданим шифрованим текстом. У даному випадку не має значення, наскільки велика довжина ключа схеми шифрування з відкритим ключем - аналіз зводиться до простого перебору 56-бітових ключів. Можливості такого роду аналізу можна перешкодити приєднанням до таких простих повідомленнями випадкових бітів