Перспективи розвитку та використання асиметричних алгоритмів в криптографії.

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

Введення

Коротка передісторія

Традиційно вважається, що концепція асиметричної криптографії вперше була запропонована в 1976 році Уітвелдом Діффі і Мартіном Хеллманом на національної комп'ютерної конференції [1] і опублікована в тому ж році в основоположною роботі "Нові напрямки в криптографії" [2]. До числа батьків-засновників асиметричної криптографії відносять також і Ральфа Меркль, який незалежно від Діффі і Хеллмана прийшов до тих же конструкцій, однак опублікував свої результати тільки в 1978 році [3].
На пріоритет у відкритті асиметричної криптографії претендує і Агентство національної безпеки США. У статті енциклопедії "Британіка" директор АНБ Сіммонс заявляє, що "двухключевую криптографія була відома в Агентстві за 10 років до публікації Діффі і Хеллмана "[4].

Термінологія

В даний час терміном "асиметрична криптографія" позначають велику групу механізмів, алгоритмів, протоколів та ідей, що застосовуються при розробці систем захисту інформації. Перелічимо основні з них і коротко прокоментуємо, що конкретно мається на увазі під кожним терміном (систематичний словник термінів з області асиметричної криптографії наведено в роботі [5]).
1) одностороння функція (One-way function);
2) одностороння функція з секретом (One-way trap-door function) - це деяка функція FK: X ® Y, що залежить від параметра K (її можна розглядати також як параметризрвані сімейство функцій) і що володіє наступними властивостями: a) при будь-якому значенні параметра K існує поліноміальний алгоритм обчислення значення функції в будь-якій точці FK (x) за умови, що параметр K невідомий;
б) при невідомому значенні параметра K не існує поліноміальною алгоритму інвертування функції FK;
в) при відомому значенні параметра K існує поліноміальний алгоритм інвертування функції FK (тут не обговорюється модель обчислень, в рамках якої ми говоримо про їх поліноміальними).
Поняття односторонньої функції з секретом стало вихідним для асиметричної криптографії. Власне, той факт, що для обчислення самої функції з поліноміальною складністю і для її інвертування потрібна різна вихідна інформація (тобто наявність певної асиметрії), і дав назву новому напряму в криптографії.
3) криптографічні протоколи - це така процедура взаємодії абонентів, в результаті якої вони досягають своєї мети, а їхні супротивники - не досягають. Під це неформальне визначення підпадають всі практично цікаві способи застосування асиметричної криптографії:
· протоколи відкритого розподілу ключів;
· Протоколи відкритого шифрування;
· протоколи електронного цифрового підпису;
· протоколи аутентифікації;
· "Електронні гроші" (тут, насправді, мається на увазі ціла сукупність протоколів взаємодії між різними учасниками системи).
Формальні визначення для перерахованих протоколів дані в книзі [5]. Останнім часом кількість різних типів криптографічних протоколів стрімко зростає, але, оскільки більша їх частина представляє (поки що) чисто теоретичний інтерес, ми на них зупинятися не будемо.
4) докази (інтерактивні) з нульовим розголошенням - це загальна теоретична модель, до якої в 1985-1986 роках прийшли дослідники різних криптографічних протоколів: [6], [7]).
Якісно, доказ (інтерактивне) з нульовим розголошенням можна визначити як протокол взаємодії двох абонентів: доводити (позначення - P від англійського Prover) і перевіряють (позначення - V від англійської Verifier). Абонент P хоче довести перевіряючому V, що деяке твердження S неправдиве. Протокол при цьому повинен задовольняти умовам: а) повноти - якщо S істинно, то P переконає абонента V визнати це; б) коректності - якщо S неправдиво, і P навряд чи переконає V, що S це правда, в) властивості нульового розголошення - в результаті виконання протоколу Перевіряючий V не зможе витягти ніякої додаткової інформації про те, чому S істинно (див. наприклад, [8]).
Докази з нульовим розголошенням заслуговують окремої згадки не тільки тому, що їхня ідея дозволяє з єдиної позиції поглянути на більшість криптографічних протоколів, але також і тому, що вони, очевидно, будуть основним об'єктом вивчення нового, бурхливо розвивається напрямку в математики та теоретичної криптографії. Крім того, докази з нульовим розголошенням знаходять важливі практичні сфери застосування (наприклад, в області розробки протоколів для інтелектуальних карток [5]).

Об'єктивні потреби

Двигуном розвитку асиметричної криптографії, без сумніву, є потреби практики. У зв'язку з бурхливим розвитком інформаційних систем (в першу чергу тут слід зазначити вражаючі успіхи інженерної думки в галузі розвитку апаратних засобів), розширенням їхньої інфраструктури практичні потреби ставлять нові завдання перед розробниками криптографічних алгоритмів. На сьогоднішній день основні спонукальні мотиви розвитку асиметричної криптографії, на наш погляд, можна згрупувати наступним чином (наведена нижче класифікація відображає найбільш істотні з них і не претендує на те, щоб бути вичерпної):
- потреби, що розвиваються телекомунікаційних мереж найрізноманітнішого застосування, у тому числі мають складну топологію;
- потреби забезпечення інформаційної безпеки в глобальній мережі Internet;
- потреби банківських систем (у тому числі що використовують інтелектуальні картки);
- Потреба мислячого людства в осягненні світу.
Незважаючи на поблажливу усмішку, що спричинюється зазвичай останнім спонукальним мотивом, не можна не враховувати, що на сьогоднішній день проблеми асиметричної криптографії перетворилися на самодостатню область досліджень. Питання побудови криптографічних протоколів, доказів з нульовим розголошенням, теоретико-числові аспекти асиметричної криптографії постійно входять до числа обговорюваних проблем на ряді авторитетних щорічних наукових конференцій, з яких найбільш високим рейтингом володіють STOC (ACM Symposium on Theory of Computing) і FOCS (IEEE Annual Symposium on Foundations of Computer Science). Останнім часом до них за рівнем наближаються криптографічні конференції EUROCRYPT, ASIACRYPT і CRYPTO. Багато авторитетні вчені починають включати в коло своїх інтересів і питання криптографії. Всі ці факти необхідно враховувати при розробці проблем, що лежать на стику політики і криптографії.
Слід відзначити і що має місце, в певному сенсі, негативну тенденцію. Іноді алгоритми асиметричної криптографії намагаються використовувати там, де вони по суті не потрібні. Наприклад, часом автори не роблять відмінності між поняттями імітопріставкі і цифрового підпису.

Перспективи теоретичних досліджень асиметричних алгоритмів

загально методологічні проблеми криптографії

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

Теоретичні дослідження відомих алгоритмів

Перелік найбільш поширених асиметричних криптоалгоритмів

Перш за все назвемо найбільш поширені (найбільш часто обговорювані) алгоритми асиметричної криптографії:
1. Схема Діффі-Хеллмана в мультиплікативної групі кінцевого поля (стаття 1976 року) і в групі точок еліптичної кривої над кінцевим полем Нілу Кобліца [9].
2. Схема відкритого шифрування RSA і побудовані на її основі схеми підпису та аутентифікації [10].
3. Схеми типу Фіата-Шаміра [11].
4. Сімейство схем підписи типу Ель-Гамаля [12].
5. Схеми на основі завдання "про рюкзаку" [13].
6. Теоретико-кодові конструкції МакЕліса [14].
Названі схеми досить відомі, тому формально описувати їх не будемо (тим більше що їх опису присвячені окремі публікації). З усіма перерахованими схемами пов'язана низка теоретичних проблем. Нижче ми наведемо основні з них і зазначимо останні опубліковані досягнення по кожній.

Теоретико-сложностние проблеми:

1. Проблема еквівалентності завдання Діффі-Хеллмана і завдання логарифмування у відповідній групі.
Практично очевидно, що завдання Діффі-Хеллмана не складніше завдання логарифмування (якщо ми вміємо логаріфміровать, то система відкритого розподілу ключів Діффі-Хеллмана нестійка). Хоча більшість дослідників схиляється до думки, що ці завдання еквівалентні, питання про те, чи вірно зворотне, на сьогоднішній день відкрито. Еквівалентність, при деяких додаткових умовах, довели Маурер [15] і ден Бур [16]. З вітчизняних дослідників сильний результат з даної проблематики отриманий М. А. Черепневим, якому вдалося побудувати субекспоненціальний алгоритм відомості задачі дискретного логарифмування в простому кінцевому полі до задачі Діффі-Хеллмана. Найбільш ж близькі до вирішення проблеми швейцарські вчені [17].
2. Проблема еквівалентності завдання компрометації схеми Ель-Гамаля і завдання логарифмування.
3. Проблема еквівалентності завдання розтину системи RSA і завдання факторизації цілих чисел (під секретним ключем розуміється експонента e).
Задача визначення секретного ключа тут еквівалентна факторизації, тим не менше, питання про еквівалентність Безключове читання і факторизації відкритий. У той же час відомі окремі випадки, коли завдання вирішується легко (випадок, так званих, "слабких ключів").
4. Проблема побудови стійких (доказовою) криптографічних протоколів у припущенні про існування тих чи інших криптографічних примітивів.
Основна маса публікацій з теоретико-сложностним проблем криптографії належить саме до цієї тематики.

Теоретико-числові проблеми

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

.
Слід відзначити, що багато хто з асимптотичних оцінок носять евристичний характер, частина з яких доведена в припущенні істинності гіпотези (розширеної) Рімана. Ряд дослідників проводять роботи за суворим доказу цих евристичних оцінок.
Як і раніше, актуальною залишається завдання отримання не асимптотичних, а точних оцінок трудомісткості для ряду розроблених алгоритмів.

1. Задача обчислення дискретного логарифма в мультиплікативної групі кінцевого поля

Практично відразу після опублікування роботи У. Діффі і М. Хеллмана Дж. Поллард публікує імовірнісні алгоритми рішення задачі дискретного логарифмування, що мають кореневу оцінку складності і не потребують великого обсягу пам'яті [18]. Цей метод називають r-методом Полларда (варіація методу - l-метод Полларда, загальна ідея відома також під назвою "baby step, giant step").
Надалі основні ідеї побудови ефективних алгоритмів для вирішення задачі дискретного логарифмування були пов'язані з, так званим, методом решета. Довгий час асимптотично найбільш ефективним (асимптотична оцінка складності -
, залишався метод Д. Копперсміта, А. Одлижко, Р. Шреппеля [19]. Метод був реалізований і застосований для логарифмування в простих полях при p довжиною до 67 десяткових знаків.
Останнім істотним досягненням у цій галузі є метод решета числового поля Д. Гордона [20]. Асимптотичні методи більш ефективний, ніж усі попередні: оцінка його трудомісткості . Однак його практична реалізація складніше: поки є повідомлення, що цим методом вдалося вирішити задачу дискретного логарифмування в простому полі при p довжиною 40 десяткових знаків. Для цього фахівцям німецького університету Universitat des Saarlandes в Саарбрюккене потрібні були 21 годину роботи робочої станції Sparc і 40 хвилин роботи суперкомп'ютера Cray [21]. За останніми даними 1997 німецьким дослідникам вдалося реалізувати процедуру логарифмування для чисел довжиною 85 десяткових знаків.
За кожним з названих методів стоїть цілий спектр їх модифікацій і варіантів. З вітчизняних дослідників, які працюють у цьому напрямку необхідно назвати О. М. Василенка та І. А. Семаєва. У тезах виступів останнього на конференціях з теорії чисел і її додатків (Тула, Воронеж) містяться вельми цікаві нові ідеї у розвиток методу решета.
Дослідники постійно роблять спроби пошуку принципово інших підходів (відмінних від ідей методу решета) до задачі дискретного логарифмування. З опублікованого тут слід згадати роботи, пов'язані зі спробою використання приватних Ферма [22], [23], однак, поки успішне логарифмуванню цим методом вимагає більшого обсягу інформації, ніж "класична" постановка задачі.
Також слід згадати про те, що з середини 1997 року в науковому середовищі циркулюють чутки про те, що російському вченому С. А. Степанову вдалося побудувати поліноміальний алгоритм дискретного логарифмування. Однак, аж до сьогоднішнього дня переконливі підтвердження цьому факту немає, втім, як і переконливі спростування.

2. Завдання розкладання цілих чисел на множники

У порівнянні із завданням дискретного логарифмування завдання факторизації чисел або розкладання їх на множники має більш тривалу історію, відому зазвичай з античних часів від Ератосфена (приблизно 284 - 202 рр.. до н.е.), а в подальшому пов'язану з іменами таких великих математиків, як Фібоначчі (приблизно 1180-1250 рр..), Ферма (1601-1665 рр..), Ейлер (1707-1783 рр..), Лежандр (1752-1833 рр..), Гаус (1777-1855 рр..). У більшості випадків вдається розкласти число на множники за допомогою пробних поділів на першому (маленькі) прості числа. Завдання стає змістовною, коли потрібно розкласти число, яке дорівнює добутку двох великих простих чисел (наприклад, число Блюма). У 70-х роках був запропонований (p-1)-метод Полларда [24], ефективний для випадку, коли p-1 розкладається на маленькі прості множники, де p - один з дільників факторізуемого числа. Незабаром, як розвиток даного рішення з'явився (p +1)-метод Полларда. Наступним кроком у цьому напрямку стала ідея використання псевдовипадкових відображень (r-метод Полларда). Цим методом було розкладено на множники 8-е число Ферма ( - число довжиною 77 десяткових знаків). Подальший розвиток цих ідей вилилося в методи з використанням групи точок еліптичної кривий [25].
На сьогоднішній день, як і для задачі дискретного логарифмування, основні просування в проблемі факторизації пов'язані з розвитком методів решета, в яких виділяють наступні етапи розвитку: методи лінійного решета, методи квадратичного решета [26] і метод решета числового поля [27], [28]. Сьогодні практично найбільш ефективним для факторизації чисел довжиною до 130 десяткових знаків залишається метод квадратичного решета. Його асимптотична оцінка трудомісткості - , де . Саме цим методом було вирішено запропонований Райвестом практичний приклад розтину системи RSA [29], для чого потрібно було розкласти на множники число довжиною 129 десяткових знаків.
Методи решета числового поля асимптотично більш ефективні (оцінка трудомісткості: ), але, застосовуються тільки для чисел виду n = re-s, де r і s порівняно малі. На практиці вважається, що розглядаються методи варто застосовувати для чис?? л з інтервалу 10130 Як вже було сказано вище, нові ідеї у розвиток методу решета містяться в роботах І. А. Семаєва, що дозволяє сподіватися на подальший прогрес в даній проблематиці.

3. Завдання побудови великих простих чисел з деякими додатковими умовами

Для потреб практичної криптографії актуальна проблема побудови швидких алгоритмів знаходження "випадкових" простих чисел заданої довжини. Швидкість роботи алгоритмів побудови великих простих чисел важлива для систем, що використовують схему RSA, так як ключами в них власне і є великі прості числа. Зазвичай в цих алгоритмах реалізується будь-яка модифікація "решета" з подальшою перевіркою чисел на простоту. При цьому використовується той факт, що прості числа розташовані досить "густо": результати про щільність розподілу простих чисел серед натуральних утворюють окремий напрямок в теорії чисел. Зокрема для функції p (x), яка дорівнює кількості простих чисел менших x, має місце асимптотична рівність:.
На сьогодні відомо досить багато алгоритмів перевірки чисел на простоту: як правило, відповідь на це питання дає вже мала теорема Ферма. Проблема полягає в доказі того, що перевіряє число дійсно є простим. Незважаючи на те, що більшість із таких алгоритмів має субекспоненціальную оцінку складності, на практиці вони показують цілком прийнятну швидкість роботи. З вітчизняних учених істотний внесок у цю проблематику вніс Ю. В. Нестеренко [22].
Існують імовірнісні алгоритми, що мають Поліноміальні оцінки складності [30]: докладні огляди публікацій з цієї теми підготовлені О. Н. Василенко.
Важливою особливістю відомих методів дискретного логарифмування є істотна залежність їх трудомісткості від потужності простого поля, в якому вирішується задача. Звідси виникає необхідність розробки як алгоритму перевірки простого числа на "слабкість", так і алгоритму, що дозволяє гарантовано уникати побудови "слабких" чисел. Більш докладно ці питання розглянуті в [31].

4. Задача обчислення дискретного логарифма в групі точок еліптичної кривої над кінцевим полем

Крім методів, які можна застосувати для логарифмування у довільній кінцевої групі, тут відомі роботи І. А. Семаєва [32], в одній з яких розглядається метод, ідейно близький методам логарифмування в кінцевому полі Адлеман Л. [33]. В іншій роботі для еліптичних кривих спеціального виду (накладаються деякі умови на модуль арифметики і на потужність групи точок) І. А. Сема вказав спосіб відомості з поліноміальною складністю завдання логарифмування в групі точок еліптичної кривої до задачі логарифмування в деякому розширенні простого поля. При цьому використовується, так зване, спаровування Вейля, після чого можна застосовувати відомі субекспоненціальние методи. Аналогічні результати були опубліковані і за кордоном [34].

5. Задача обчислення потужності групи точок еліптичної кривої над кінцевим полем

Точні формули для потужностей груп точок еліптичної кривий відомі тільки для досить вузького класу кривих. На практиці актуальна завдання побудови систем асиметричної криптографії, де сама крива є "довготривалим" ключем. Таким чином виникає проблема побудови ефективних алгоритмів обчислення потужності групи точок еліптичної кривий довільного виду. Тут відомий імовірнісний алгоритм Шенкса [35], грунтується на ідеї типу "baby step, giant step". Метод має оцінку складності, де q - потужність кінцевого поля. З детермінованих алгоритмів відомий метод СКУФ [36], що базується на використанні ендоморфізма Фробеніуса і має оцінку складності, де q - потужність кінцевого поля. Однак для практичних обчислень метод, очевидно, мало придатний. Гарний огляд з цього питання містяться в роботі Х. В. Ленстрой молодшого [37].

6. Проблема ефективної реалізації теоретико-числових схем асиметричної криптографії

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

4. Задача про "рюкзаку"

Повідомлення про те, що схема Меркль-Хеллмана (нагадаємо, що вона розроблена в 1978 році) зламана, у відкритій пресі з'явилося в 1984 році [39].
Тоді Меркль публікує схему типу "рюкзак" з декілька ітерацій, але і цей варіант був зламаний [40], після чого Меркль заплатив Шамір і Брікеллю 100 $ і 1000 $ відповідно, обіцяні їм тим, хто зламає системи.
У 1984 році Шор і Райвест розробляють свій варіант схеми на "рюкзаку", у якому не використовується операція модульного множення. Його допрацьована версія опублікована в 1988 році [41]. З використанням алгоритмів приведення цілочисельних грат, Шнорр і Хернер в 1995 році знайшли підходи до розкриття і цієї системи при деяких параметрах (але не тих, які рекомендували використовувати Шор і Райвест) [42].

Перспективи розробки нових алгоритмів

Практично використовуються алгоритми асиметричної криптографії засновані на двох завданнях: дискретного логарифмування і факторизації. Існують різні думки про можливість вирішення цих завдань у майбутньому і про те, як швидко це може статися. Тому для фахівців у галузі захисту інформації постійно залишається актуальною задача розробки альтернативних систем. При цьому головними залишаються проблеми існування односторонньої функції та функції з секретом. Тут слід виділити наступні напрямки досліджень.
1. Глобальна теоретична ідея побудови нових асиметричних криптосистем полягає в спробі породження функцій з секретом за допомогою "маскування" простих завдань під складні (NP-повні). Було запропоновано багато варіантів, але всі вони виявилися нестійкими.
2. Отримані результати щодо розкриття деяких варіантів кріптосхеми на основі задачі про "рюкзаку" сформували в середовищі криптографів-практиків скептичне ставлення до всіх подібних схем. У той же час, формально схема Шора-Райвеста НЕ зламана до цього дня.
Ряд криптографів-теоретиків вважають завдання про "рюкзаку" однією з найбільших перспективних для побудови алгоритмів асиметричної криптографії, оскільки "складність" закладена в самій її природі. Крім того, у разі успехатакой схемою, очевидно, не буде рівних по ефективності (швидкості роботи).
3. Схема відкритого розподілу ключів з використанням некоммутатівних груп була запропонована лабораторією МГУ з математичних проблем криптографії в 1993 році, що стало принципово новим підходом до цього завдання. Однак до сьогоднішнього дня практично реалізованих схем, заснованих на цих ідеях, не запропоновано.
4. Після того, як Сидельников і Шестаков, використовуючи швидкі алгоритми декодування, показали, що одна зі схем типу МакЕліса (схема Нідеррайтера) -- нестійка, було запропоновано ряд варіантів схеми на основі теоретико-кодових конструкцій. Практичного застосування не знайшла ні один з них або через свою громіздкість, або в силу того, що її стійкість викликає великі сумніви у фахівців.
5. Реалізація протоколів асиметричної криптографії (в першу чергу, схем електронного цифрового підпису) з використанням традиційних криптографічних схем. Цей напрямок, на наш погляд, не заслужено перебуває в тіні. Теоретична можливість побудови таких систем показана Лампортом, Наором і Юнгом. Відома також цікава стаття Березина і Дорошкевича [43], де наведено схеми ЕЦП, засновані на симетричних алгоритмах. Крім того, корпорація IBM у деяких з розроблених нею банківських систем реалізує схеми ЕЦП на основі алгоритму DES з використанням захищених модулів.
6. З початку 90-х років широко обговорюється можливість реалізації протоколів асиметричної криптографії на основі квантово-механічних ефектів [44], [45].

Перспективи практичного застосування асиметричних алгоритмів

Юридичні питання використання асиметричних алгоритмів у системах

Питання патентної чистоти

Більшість алгоритмів асиметричної криптографії захищено патентами. При розгляді цього питання слід мати на увазі, що в відповідно до законодавства США патенти в цій країні видаються строком на 17 років без права їх відновлення. Крім того, патентодержатель, що порушив справа про захист своїх прав на даний патент і не зумів виграти справу, автоматично втрачає всі права з даного патенту.
Схема Меркль-Хеллмана ( "рюкзак"):

країна № патенту коли запатентований
США 4218582 19 серпня 1984
(закінчився 19 серпня 1997)
Голландія 7810063 10 квітня 1979
Великобританія 2006580 2 травня 1979
2006580 18 серпня 1982
Німеччина 2843583 10 травня 1979
2843583 3 червня 1982
2857905 15 липня 1982
Швеція 7810478 14 травня 1979
Франція 2405532 8 червня 1979
Канада 1128159 20 червня 1982
Італія 1099780 28 вересня 1985
Швейцарія 63416114 14 січня 1983
Схема RSA запатентована тільки в США: патент № 4,405,829 від 20 вересня 1983 року, термін дії закінчується 20 вересня 2000 року. Запатентовані також деякі модифікації даної схеми: наприклад, схема Полига-Хеллмана має патент США № 4,424,414 від 8 січня 1984 року (ця модифікація запатентована також і в Канаді).
Схема Ель-Гамаля не запатентовано, однак деякі організації вважають, що патент на схему Діффі-Хеллмана покриває і всі модифікації схеми Ель-Гамаля.
Схема Діффі-Хеллмана (власники патенту - Діффі, Хеллман, Меркль): патент США № 4,200,770 від 29 квітня 1980 року (закінчився 29 квітня 1997); патент Канади № 1,121,480 від 6 квітня 1982 року.
Схема Шнорр: патент США № 4,995,082 від 19 лютого 1991 року (закінчується 19 лютого 2008 року). Крім США, цей алгоритм запатентований також у низці інших країн.
Схема DSA (стандарт США на ЕЦП): формальний власник патенту - Девід Кравітц (колишній співробітник АНБ, см. [46]): патент США № 5,231,668 від 27 липня 1993 року. Проте, права на цей алгоритм оскаржують Діффі, Хеллман, Меркль і Шнорр.
Схема Фіата-Шаміра: патент США № 4,748,668 від 31 травня 1988 року.
Держателем п'яти з вище наведених патентів є група Public Key Partners, спеціально створена компаніями RSA Data Security Inc. (65% акцій) і Caro-Kahn Inc. (35% акцій):

№ патенту Коли виданий Автори Що запатентовано
4,200,770 29.03.80 Hellman, Diffie, Merkle відкрите розподіл ключів Діффі-Хеллмана
4,218,582 19.08.80 Hellman, Merkle "рюкзак" Меркль-Хеллмана
4,405,829 20.09.83 Rivest, Shamir, Adleman схема RSA
4,424,414 03.03.84 Hellman, Pohlig схема Полига-Хеллмана
4,995,082 19.02.91 Schnorr підпис Шнорр

Експортно-імпортні обмеження

Уряди низки країн відносять криптографію до військових технологій. Контролем за експортом криптографічних засобів в США займаються дві урядові відомства: Bureau of Export Administration (BXA) in the Department of Commerce, керується у своїй діяльності серією законодавчих актів під загальною назвою Export Administration Regulations (EAR) і Office of Defense Trade Controls (DTC) in the State Department, керівними документами для якого є серія законодавчих актів під загальною назвою International Traffic in Arms Regulations (ITAR). Поширення криптографічних засобів також підпадає під обмеження CoCom (Coordinating Committee for Multilateral Export Controls).
Обмеження стосуються схем "стійкою" (strong) криптографії. Для систем з відкритим ключем до таких відносять схеми з довжиною ключа більше 512 біт (для порівняння - для симетричних криптоалгоритмів нижня межа довжини ключа обчислюється 40 бітами). Однак, при розгляді питання про видачу дозволу на експорт розглядається все-таки не сам криптографічний алгоритм, а то програма, в рамках якого він працює. Так, звичайно дають дозвіл на експорт стійких криптографічних засобів, що використовуються в
· фінансових додатках;
· додатках, призначених тільки для виконання процедури розшифрування;
· Додатках, що працюють з даними, представленими в аналоговій формі;
· системах персоналізації інтелектуальних карток;
· Системах контролю доступу;
· системах аутентифікації;
· програмне забезпечення, що виконує захист від вірусів.
Можливо, у зв'язку з програмою "депозиту ключів", частина законодавчих актів США в цій області буде найближчим часом переглянуто.

Проблема переходу на юридично значущі електронні документи

У зв'язку з розробкою алгоритмів електронного цифрового підпису постає проблема переходу на юридично значущі електронні документи. Ця завдання пов'язана з великими організаційно технічними та правовими проблемами. Проте переваги такого підходу отримують все більше визнання у світі. Так, в серпні 1997 року в Італії набув чинності "Закон Бассаніні" № 59/97 від 15.03.97, який зобов'язує всі державні органи до 31.12.98 бути готовими для роботи з електронними документами. Аналогічний законопроект внесено до США конгресменами А. Ішу і Б. Тозін.
Комісія ООН з міжнародного торгового законодавства ініціювала створення моделі закону про безпечне електронної торгівлі, включаючи закон про електронний цифрового підпису.

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

Закордонні та міжнародні стандарти на алгоритми асиметричної криптографії

1. У США питаннями стандартизації криптоалгоритмів займається Національний інститут стандартів і технології (NIST - National Institute of Standards and Technology) - один з підрозділів US Department of Commerce. До 1988 року NIST називався National Bureau of Standards. Відповідно до законом від 1987 року Computer Security Act (Public Law 100-235) NIST зобов'язаний координувати свою діяльність з питань захисту інформації з АНБ США. До асиметричним алгоритмами, стандартизованим NIST, відноситься американський стандарт на цифровий підпис DSA.

2. Міжнародна організація по стандартам ISO в середині 80-х років прийняла рішення, по-перше, займатися не стандартизацією алгоритмів, а тільки їх реєстрацією і, по-друге, приймати до розгляду тільки алгоритми шифрування. В даний час з алгоритмів асиметричної криптографії в ISO зареєстровано лише схема LUC (деякий узагальнення схеми RSA, де замість експоненти застосовані підстановки поліноми). Крім алгоритмів ISO зареєструвала ряд що використовуються в мережах протоколів (X.509 - протокол обчислення сертифіката та ін)

3. Компанія RSA Data Security, Inc. робить активні спроби введення де-факто промислових стандартів на власні криптографічні алгоритми - так званих Public-Key Cryptography Standards (PKCS), що описують інтерфейси, формати подання даних і алгоритми (всього 12 стандартів, прийнятих з 1993 по 1995 роки). Порядок прийняття та перегляду стандартів PKCS відступає від прийнятих норм розгляду документів такого роду. PKCS по інтерфейсу сумісні з X.509 частково.

4. Європейське Співтовариство (ЄС) організувало власну програму Research and Development in Advanced Communication Technologies (RACE). У неї увійшли 6 основних Європейських центрів з криптографії: Center for Mathematics and Computer Science (Amsterdam), Siemens AG, Philips Crypto BV, Royal PTT Nederland NV (PTT Research), Katholieke Universiteit Leuven, Aarhus Universitet. У червні 1992 прийняті стандарти RACE Integrity Primitives Evaluation (RIPE) і Integrity Primitives, що спираються на схему RSA.

Застосування в мережі Internet

1. Для алгоритмів шифрування, аутентифікації, контролю цілісності повідомлень та управління ключами в мережі Internet прийняті стандарти Internet Privacy-Enhanced Mail standards (PEM). Ці протоколи розроблені в рамках груп Internet Resources Task Force (IRTF) і Privacy and Security Research Group (PSRG), потім передані Internet Engineering Task Force (IETF) PEM Working Group і, нарешті, прийняті Internet Architecture Board (IAB). Протоколи опубліковані в серії Request for Comment (RFC). PEM підтримують протокол X.509 і алгоритм RSA (для ключів довжиною до 1024 біт). Існує також військовий аналог PEM, розроблений АНБ США наприкінці 80-х років (Message Security Protocol - MSP).

2. Створена в березні 1996 року фірма Pretty Good Privacy, Inc. для розповсюдження комерційних версій, розробленого Філіпом Ціммерманом програмного продукту PGP, робить активні спроби щодо введення де-факто в якості стандарту в Internet свого алгоритму, який є, по суті, алгоритмом RSA з довжиною ключа - 2047 біт). Сьогодні складно передбачати подальший розвиток сит?? родної асоціації, оскільки PGP, Inc. змушена обговорювати проекти впровадження в свої алгоритми процедур депонування ключів, що неминуче підриває довіру до системи в цілому з боку користувачів.

Комерційні галузі застосування

Алгоритм RSA, ліцензований групою Public Key Partners, використовується багатьма великими компаніями: IBM, Microsoft, Lotus, Apple, Novell, Digital, National Semiconductor, AT & T, Sun. Ліцензію для внутрішньокорпоративного використання схеми RSA мають також Boeing, Shell Oil, DuPont, Raytheon, Citicorp, TRW Corporation, причому остання компанія придбала ліцензію тільки після судового розгляду в 1992 році.

Державні області застосування

Алгоритми асиметричної криптографії (зокрема, схема відкритого розподілу ключів) реалізовані в телефонній апаратурі серії STU (Secure Telephone Unit): STU-II, STU-III.
В останні кілька років у США ведеться активна політична боротьба навколо спроб примусового впровадження в мережі зв'язку Clipper Chip (також званого MYK-78T). Основні проблеми тут пов'язані з процедурою депонування ключів. Нам же хотілося лише згадати, що Clipper Chip дозволяє виконувати і деякі протоколи асиметричної криптографії.

Застосування асиметричних алгоритмів в Росії

ГОСТ 34.10-94
Потреби практики підштовхнули Росію до розробки та опублікуванню власного стандарту на ЕЦП.

Перспективні вітчизняні розробки
З вітчизняних комерційних засобів захисту інформації, що реалізують алгоритми асиметричної криптографії, найбільш відома на ринку "Верба-О" московського відділення Пензенського науково-дослідного електротехнічного інституту [47]. На свою роль на цьому ринку претендують і деякі інші комерційні фірми, наприклад, ЛАН-крипт. Однак, як правило, у цих фірм не відрегульовані юридичні питання їх діяльності, а криптографічні якості їх продуктів далеко не безперечні.

Симетрична або асиметрична криптографія?

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