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

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

Введення

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

Традиційно вважається, що концепція асиметричної криптографії вперше була запропонована в 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