Криптографія з відкритим ключем: від теорії до стандарту
Введення
Протягом багатьох століть людство використовувало криптографічні методи для захисту інформації при її передачі та зберіганні. Приблизно до кінця
XIX ст. ці методи стали об'єктом математичного вивчення. Галузь математики, що вивчає захист інформації, яка традиційно називається кріптологія [cryptology] і
підрозділяється на криптографію [cryptography], що займається розробкою нових методів і обгрунтуванням їх коректності, і криптоаналіз [cryptanalysis], завдання
якого - інтенсивне вивчення існуючих методів, часто з метою реального розкриття секретів іншого боку. Криптографія та криптоаналіз перебувають у тісному
взаємодії один з одним і з практичними потребами і розвиваються паралельно закритими урядовими організаціями багатьох держав і
міжнародній науковій спільноті.
В даний час існують тисячі криптографічних систем, реалізованих як програмно, так і апаратно. Серед них можна виділити системи, сам
криптографічний принцип роботи яких тримається в секреті, як, наприклад, мікросхема Clipper, пропонована урядом США як
криптографічного стандарту для телекомунікацій, і системи, алгоритм яких відкритий, а секретної є тільки певна, як правило невелика, порція
інформації, яка називається (секретним) ключем [(secret) key] - до них відноситься більшість систем, реалізованих програмно і призначених для широкого
використання. Надалі ми будемо розглядати тільки системи другого типу.
У системі даного типу завдання розтину системи, тобто порушення захисту інформації без попереднього знання ключа, як правило, теоретично
можна вирішити за наявності у розкриває боку необмежених обчислювальних ресурсів. З математичної точки зору надійність криптографічного системи
визначається складністю вирішення цього завдання з урахуванням реальних обчислювальних ресурсів потенційної розкриває боку. З організаційної точки зору
має значення співвідношення вартості потенційного розтину та цінності захищається інформації.
Математичне дослідження надійності криптографічних систем утруднено відсутністю універсального математичного поняття складності. З цієї причини
надійність більшості криптографічних систем в даний час неможливо не тільки довести, але навіть адекватно сформулювати. Як правило, застосування тієї
чи іншої криптографічного системи засноване на результати багаторічного практичного криптоаналізу систем даного типу, в тій чи іншій мірі
підкріплених математичним обгрунтуванням. Це обгрунтування може зводити завдання розкриття цієї криптосистеми до якої-небудь задачі теорії чисел, або
комбінаторики, рішення якої вважається реально не здійсненним, або, що краще, до класу NP-повних задач, зводиться до якого є
"Еталоном" практичної нерозв'язності. У той же час, поняття практичної нерозв'язності для конкретних практичних завдань не є чітко визначеним
або стабільним, завдяки розвитку обчислювальної техніки і методів криптоаналізу.
Криптографія з симетричним ключем
Довгий час традиційної криптографічного схемою була схема з симетричним ключем [symmetric key, dual key]. У цій схемі є один ключ, який
бере участь у шифрування і дешифрування інформації. Шифруюча процедура за допомогою ключа виробляє ряд дій над вихідними даними, дешифруються
процедура за допомогою того ж ключа виробляє зворотні дії над кодом. Дешифрування коду без ключа передбачається практично нездійсненним. Якщо зашифрована
таким чином інформація передається по звичайному, тобто незахищеному, каналу зв'язку, один і той же ключ повинен бути у відправника та одержувача, внаслідок
чого виникає необхідність у додатковому захищеному каналі для передачі ключа, підвищується вразливість системи і збільшуються організаційні труднощі.
До класу алгоритмів з симетричним ключем відноситься метод "одноразового блокнота" [one-time pad], що полягає в побітового складання ( "гамування")
шіфруемого тексту з випадковою послідовністю бітів - ключем (див. [S94]). Довжина ключа повинна збігатися з довжиною шіфруемого тексту і кожен відрізок ключа
повинен використовуватися одноразово; в іншому випадку текст легко піддається несанкціонованої розшифровці. При виконанні ж цих умов даний метод
є єдиним методом, теоретично стійким проти криптоаналізу противника з необмеженими обчислювальними ресурсами. Незважаючи на це, в
даний час метод "одноразового блокнота" практично не застосовується через організаційні труднощі, пов'язані з генерацією, передачею і зберіганням
використовуваних в ньому наддовгих ключів.
Іншим прикладом схеми з симетричним ключем може служити алгоритм DES (Data Encryption Standard), прийнятий 23 листопада 1976 в якості офіційного
криптографічного стандарту США для захисту некритичною [unclassified] інформації (див. [S94], с.219-243). У стандарт було включено положення про
обов'язкової ресертифікація (перегляді) алгоритму кожні п'ять років; остання така ресертифікація відбулася в 1992 р. На думку експертів, у зв'язку з
певними успіхами в криптоаналіз DES і появою нових методів шифрування з симетричним ключем, алгоритм може не бути ресертіфіцірован на
наступний п'ятирічний термін. Тим не менше, DES як і раніше вважається криптографічно стійким алгоритмом і залишається найпоширенішою схемою
шифрування з симетричним ключем.
Російський стандарт на криптографію з симетричним ключем визначений ГОСТ 28147-89 "Системи обробки інформації. Захист криптографічний. Алгоритм
криптографічного перетворення ", який був введений в дію 1 липня 1990 На відміну від DES, стандарт містить вказівку на те, що він" за своїм
можливостями не накладає обмежень на ступінь секретності інформації, що захищається ". У загальних рисах алгоритм ГОСТ 28147 аналогічний DES, але є ряд
істотних відмінностей, як, наприклад, довжина ключа і трактування вмісту вузлів заміни [у схемі DES званих "S-boxes"]. У той час, як заповнення вузлів
заміни DES оптимізована з точки зору криптографічного стійкості і явно зазначено в стандарті, заповнення вузлів заміни ГОСТ 28147 "є секретним
елементом і поставляється в установленому порядку ". Враховуючи, що воно в той же час "є довгостроковим ключовим елементом, загальним для мережі ЕОМ", і що
"Встановлений порядок" поставки може не передбачати криптографічну оптимізацію, цей пункт стандарту є одним з його слабких місць,
утрудняє реалізацію і не сприяє криптографічного стійкості. Однак при завданні оптимізованих значень для вузлів заміни криптографічний
стійкість алгоритму можна порівняти зі стійкістю DES.
Криптографія з відкритим ключем
У 1976 р. У. Діффі і М. Хеллманом [DH76] було запропоновано новий тип криптографічного системи - система з відкритим ключем [public key
cryptosystem]. У схемі з відкритим ключем є два ключі, відкритий [public] і секретний [private, secret], обрані таким чином, що їх послідовне
застосування до масиву даних залишає цей масив без змін. Шифруюча процедура використовує відкритий ключ, дешифруються - секретний. Дешифрування коду
без знання секретного ключа практично нездійсненно; зокрема, практично нерозв'язна завдання обчислення секретного ключа по відомому відкритому ключу.
Основна перевага криптографії з відкритим ключем - спрощений механізм обміну ключами. При здійсненні комунікації по каналу зв'язку передається
тільки відкритий ключ, що робить можливим використання з цією метою звичайного каналу і усуває потребу в спеціальному захищеному каналі для передачі
ключа.
З появою систем з відкритим ключем поняття про захист інформації, а разом з ним функції криптографії значно розширилися. Якщо раніше основний
завданням криптографічних систем вважалося надійне шифрування інформації, в даний час область застосування криптографії включає також цифровий підпис
(аутентифікацію), ліцензування, нотарізацію (засвідчення), розподілене керування, схеми голосування, електронні гроші і багато
інше (див. [BFS91], ч.7, [S94], ч.1). Найбільш поширені функції криптографічних систем з відкритим ключем - шифрування і цифровий підпис,
причому роль цифрового підпису останнім часом зросла в порівнянні з традиційним шифруванням: деякі з систем з відкритим ключем підтримують цифрову
підпис, але не підтримують шифрування.
Цифровий підпис використовується для аутентифікації текстів, що передаються по телекомунікаційним каналам. Вона аналогічна звичайної рукописної підпису та
володіє її основними властивостями: засвідчує, що підписаний текст виходить саме від особи, що поставив підпис, і не дає самому цій особі можливості
відмовитися від зобов'язань, пов'язаних з підписаним текстом. Цифровий підпис є невелика кількість додаткової інформації, що передається
разом з підписаних текстом. На відміну від шифрування, при формуванні підпису використовується секретний ключ, а під час перевірки - відкритий.
Через особливості алгоритмів, що лежать в основі систем з відкритим ключем, їх швидкодію при обробці одиничного блоку інформації звичайно в десятки раз
менше, ніж швидкодія систем з симетричним ключем на блоці тієї ж довжини. Для підвищення ефективності систем з відкритим ключем часто застосовуються
змішані методи, що реалізують криптографічні алгоритми обох типів. При шифрування інформації вибирається випадковий симетричний ключ, викликається
алгоритм з симетричним ключем для шифрування вихідного тексту. а потім система з відкритим ключем для шифрування симетричного ключа. За
комунікаційного каналу передається текст, зашифрований симетричним ключем, і симетричний ключ, зашифрований відкритим ключем. Для розшифровки дії
виробляються у зворотному порядку: спочатку за допомогою секретного ключа одержувача розшифровується симетричний ключ, а потім за допомогою симетричного ключа --
отриманий через зашифрований текст. Для формування електронного підпису по підписує текст обчислюється його односпрямований хеш-функція
(дайджест) [one-way hash function, digest], що представляє собою один короткий блок інформації, що характеризує весь текст в цілому; завдання відбудови
тексту за його хеш-функції або підбору іншого тексту, що має ту ж хеш-функцію, практично нерозв'язна. При безпосередньому формуванні
підпису, замість шифрування особистим ключем кожного блоку тексту секретний ключ застосовується тільки до хеш-функції; по каналу передається сам текст і
сформована підпис хеш-функції. Для перевірки підпису знову обчислюється хеш-функція від отриманого по каналу тексту, після чого за допомогою відкритого
ключа перевіряється, що підпис відповідає саме даному значенням хеш-функції. Алгоритми обчислення односпрямований хеш-функцій, як правило,
логічно тісно пов'язані з алгоритмами шифрування з симетричним ключем.
Описані гібридні методи шифрування і цифрового підпису поєднують в собі ефективність алгоритмів з симетричним ключем і властивість незалежності від
додаткових секретних каналів для передачі ключів, притаманне алгоритмів з відкритим ключем. Криптографічний стійкість конкретного гібридного методу
визначається стійкістю слабкішого ланки в ланцюзі, що складається з алгоритмів з симетричним і з відкритим ключем, вибраних для його реалізації.
Система RSA
У 1978 р. Р. Рівестом, А. Шамір і Л. Адлеман [RSA78] створили першу криптосистем з відкритим ключем для шифрування і цифрового підпису, що отримала назву RSA
(за першими літерами прізвищ авторів). Система описується в термінах елементарної теорії чисел. Її надійність обумовлюється практично нерозв'язні завдання
розкладання великого натурального числа на прості множники. Сучасний стан алгоритмів факторизації (розкладання на множники) дозволяє вирішувати
це завдання для чисел довжиною до 430 біт; виходячи з цього, ключ завдовжки в 512 біт вважається надійним для захисту даних на строк до 10 років, а в 1024 біта - безумовно
надійним. Довжина підпису в системі RSA збігається з довжиною ключа.
Незважаючи на те, що відсутній математично доведений зведення завдання розкриття RSA до задачі розкладання на множники, а також задачі розкладання на
множники до класу NP-повних задач, система витримала випробування практикою і є визнаним стандартом de-facto в промисловій криптографії, а також
офіційним стандартом ряду міжнародних організацій. З іншого боку, вільне розповсюдження програмного забезпечення, заснованого на RSA,
обмежене тим, що алгоритм RSA захищений у США поруч патентів.
Проект DSS
У 1991 р. в США був опублікований проект федерального стандарту цифрового підпису - DSS (Digital Signature Standard, [DSS91], див. також [S94],
с.304-314), що описує систему цифрового підпису DSA (Digital Signature Algorithm). Одним з основних критеріїв при створенні проекту була його патентна
чистота.
Пропонований алгоритм DSA, має, як і RSA, теоретико-числовий характер, і заснований на криптографічного системі Ель-Гамаля [E85] у варіанті Шнорр [S89].
Його надійність заснована на практичній нерозв'язності певного окремого випадку задачі обчислення дискретного логарифма. Сучасні методи вирішення цієї
завдання мають приблизно ту ж ефективність, що і методи розв'язання задачі факторизації; у зв'язку з цим пропонується використовувати ключі довжиною від 512 до
1024 біт з тими ж характеристиками надійності, що і в системі RSA. Довжина підпису в системі DSA менше, ніж у RSA, і становить 320 біт.
З моменту опублікування проект отримав багато критичних відгуків (див., напр., [R92]), багато з яких були враховані при його доопрацюванні. Одним з
головних аргументів проти DSA є те, що, на відміну від загальної задачі обчислення дискретного логарифма, її окремий випадок, використаний у даній
схемою, мало вивчений і, можливо, має істотно меншу складність розтину. Крім того, стандарт не специфікує спосіб отримання псевдовипадкових чисел,
що використовуються при формуванні цифрового підпису, і не вказує на те, що цей елемент алгоритму є одним з найбільш критичних з криптографічного
стійкості.
Опції DSA обмежені тільки цифровим підписом, система принципово не призначена для шифрування даних. По швидкодії система DSA порівнянна з
RSA при формуванні підпису, але істотно (в 10-40 разів) поступається їй при перевірці підпису.
Разом з проектом DSS опублікований проект стандарту SHS (Secure Hash Standard), що описує односпрямований хеш-функцію SHA (Secure Hash
Algorithm), рекомендовану для використання разом з DSA (див. [S94], с.333-336). Хеш-функція SHA є модифікацією алгоритму MD4, добре
відомого в криптографічного літературі.
Російський стандарт цифрового підпису
У 1993 р. в Росії було видано два державних стандарту "Процедури вироблення і перевірки електронного цифрового підпису на базі асиметричного
криптографічного алгоритму "і" Функція хешування ", під загальним заголовком" Інформаційна технологія. Криптографічний захист інформації ".
Стандарт "Процедури вироблення і перевірки електронного цифрового підпису ..." багато в чому схожий зі своїм американським аналогом DSS. Для формування та перевірки
цифрового підпису в ньому використовується той же алгоритм Ель-Гамаля і Шнорр, що і в DSS, з незначними модифікаціями. Є два альтернативних довжини ключа,
512 і 1024 біт; довжина підпису становить 512 біт.
Для генерації ключів запропоновано низку нових алгоритмів. Ключі, що отримуються за допомогою цих алгоритмів, мають спеціальний вид, що потенційно може спростити
завдання розтину системи в порівнянні з DSS. Критика DSS, пов'язана з недостатньо розробленим теоретичним обгрунтуванням алгоритму, у разі
росийского стандарту кілька пом'якшується тим, що елемент ключа q вибирається більш довгим, ніж у DSA. Критика. пов'язана з відсутністю специфікації на
спосіб отримання псевдовипадкових чисел, залишається в силі.
Як і DSS, російський стандарт визначає тільки алгоритм цифрового підпису, але не шифрування. Швидкодія обох алгоритмів приблизно збігається.
Стандарт "Функція хешування" призначений для використання разом зі стандартом "Процедури вироблення і перевірки цифрового підпису" і являє
собою оригінальний алгоритм, заснований на методі кодування із симетричнимключем ГОСТ 28147. Стандарт не містить криптографічного обгрунтування
вибраного алгоритму і не коригує ГОСТ 28147 в частині заповнення вузлів заміни.
Незважаючи на зазначені недоліки, система, описана в російському стандарті, застосовується в багатьох областях, особливо для комерційних додатків.
Програмна криптографічний система ТерКріпт
Санкт-петербурзьким МГП "терки" розроблена криптографічний система ТерКріпт, що представляє собою комплекс програм на мові C стандарту ANSI.
Система реалізує в повному обсязі алгоритми DES, ГОСТ 28147, RSA, DSS/SHS і російських криптографічних стандартів. Алгоритми реалізовані на основі загальних
процедур теорії чисел, що використовують сучасні теоретико-числові методи для досягнення максимальної ефективності. Є спеціальна версія системи,
оптимізована для роботи на персональних комп'ютерах IBM AT 286, 386, 486.
Література
[BFS91] Th.Beth, M. Frisch, G.J. Simmons (eds.) Public-Key Cryptography: State of the Art and Future Directions. E.I.S.S. Workshop - Oberwolfach,
Germany, July 1991 - Final Report. Lecture Notes in Computer Science, V.578.
[DH76] W. Diffie, M. Hellman. New Directions in Cryptography. IEEE Trans. Inform. Theory, IT-22, No.6 (1976), pp.644-654.
[DSS92] The Digital Signature Standard Proposed by NIST. CACM, V.35 (1992), No.7, pp.36-40.
[E85] T. ElGamal. A Public-Key Cryptosystem and a Signature Scheme Based on Discrete Logarithms. IEEE Trans. Inform. Theory, IT-31 (1985), pp.469-472.
[R92] Responses to NIST's Proposal. CACM, V.35 (1992), No.7, pp 41-54.
[RSA78] R. L. Rivest, A. Shamir, L. Adleman. A Method for Obtaining Digital Signatures and Public-Key Cryptosystems. CACM, V.21 (1978), No.2, pp.120-126.
[S94] B. Schneier. Applied Cryptography: Protocols, Algorithms and Source Code in C. John Wiley & Sons, Inc., 1994.
[S89] C. P. Schnorr. Efficient Identification and Signatures for Smart Cards. Advances in Cryptology: Proceedings of Crypto'89, G. Brassard (ed). Lecture
Notes in Computer Science, V.435, pp.239-251.
