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

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

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

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

Традиционно вважається, що концепцію асиметричної криптографії уперше було запропонована в 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, що якийсь твердження P. S істинно. Протокол у своїй повинен відповідати умовам: а) повноти — якщо P. S істинно, то P переконає абонента V визнати це; б) коректності - якщо P. S брехливо, то P навряд чи переконає V, що P. S істинно; в) властивості нульового розголошення — у виконання протоколу Перевіряючий V зможе витягти ніякої додаткової інформації у тому, чому P. 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 рр.). У багатьох випадків вдається розкласти число на множники з допомогою пробних ділень у перші (маленькі) прості числа. Завдання стає змістовної, коли потрібно розкласти число, однакову твору двох великих простих чисел (наприклад, число Блюма). У 1970;х роках було запропоновано (p-1)-метод Полларда [24], ефективний для випадку, коли p-1 розкладається на маленькі прості множники, де p — одне із делителей факторизуемого числа. Невдовзі, як розвиток цього рішення з’явився (p+1)-метод Полларда. Таким кроком у цьому напрямі стала ідея використання псевдослучайных відбиття (r-метод Полларда). Цим методом було розкладено на множники 8-ое число Ферма (— число довжиною 77 десяткових знаків). Подальший розвиток цих ідей перетворилася на методи з використанням групи точок еліптичної кривою [25]. Сьогодні, як й у завдання дискретного логарифмирования, основні щодо проблемі факторизации пов’язані з недостатнім розвитком методів решета, у яких виділяють такі етапи розвитку: методи лінійного решета, методи квадратичного решета [26] і метод решета числового поля [27], [28]. Сьогодні найефективнішим для факторизации чисел довжиною до 130 десяткових знаків залишається метод квадратичного решета. Його асимптотическая оцінка трудомісткості -, где. Саме цим методом було вирішено запропонований Райвестом практичний приклад розтину системи RSA [29], навіщо знадобилося розкласти на множники число довжиною 129 десяткових знаків. Методи решета числового поля асимптотически ефективніші (оцінка трудоемкости:), але застосовні лише чисел виду n=re-s, де r і p. s порівняно малі. На практиці вважається, що аналізовані методи треба використовувати для чисел з інтервалу 10 130.