Введення
Протягом багатьох століть людство використовувало криптографічні методи для захисту інформації при її передачі та зберігання. Приблизно до кінця 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, GJ Simmons (eds.) Public-Key Cryptography: State of the Art and Future Directions. EISS 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] RLRivest, 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] CPSchnorr. 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.