еяких додаткових умовах, довели Маурер [15] і ден Бур [16]. З вітчизняних дослідників сильний результат з даної проблематики отриманий М. А. Черепневим, якому вдалося побудувати субекспоненціальное алгоритм відомості задачі дискретного логарифмування в простому кінцевому полі до задачі Діффі-Хеллмана. Найбільш ж близькі до вирішення проблеми швейцарські вчені [17].
2. Проблема еквівалентності завдання компрометації схеми Ель-Гамаля і завдання логарифмування.
3. Проблема еквівалентності завдання розтину системи RSA і завдання факторизації цілих чисел (під секретним ключем розуміється експонента e).
Завдання визначення секретного ключа тут еквівалентна факторизації, тим не менше, питання про еквівалентність Безключове читання і факторизації відкритий. У Водночас відомі окремі випадки, коли завдання вирішується легко (випадок, так званих, "слабких ключів").
4. Проблема побудови стійких (доказовою) криптографічних протоколів у припущенні про існування тих чи інших криптографічних примітивів.
Основна маса публікацій з теоретико-сложностним проблем криптографії належить саме до цієї тематики. p> Теоретико-числові проблеми
Далі, приводячи субекспоненціальное асимптотичні оцінки складності алгоритмів, будемо традиційно користуватися наступним позначенням:
.
Слід зазначити, що багато з асимптотичних оцінок носять евристичний характер, частина з яких доведена в припущенні істинності гіпотези (розширеної) Рімана. Ряд дослідників проводять роботи за суворим доведенню цих евристичних оцінок.
Як і раніше актуальною залишається завдання отримання не асимптотичних, а точних оцінок трудомісткості для ряду розроблених алгоритмів. p> 1. Задача обчислення дискретного логарифма в мультиплікативної групі кінцевого поля
Практично відразу після опублікування роботи У. Діффі і М. Хеллмана Дж. Поллард публікує імовірнісні алгоритми розв'язання задачі дискретного логарифмування, що мають кореневу оцінку складності і не потребують великого обсягу пам'яті [18]. Цей метод називають r-методом Полларда (варіація методу - l-метод Полларда, загальна ідея відома також під назвою "baby step, giant step").
Надалі основні ідеї побудови ефективних алгоритмів для вирішення задачі дискретного логарифмування були пов'язані з, так званим, методом решета. Довгий час асимптотично найбільш ефективним (асимптотична оцінка складності -
, залишався метод Д. Копперсміта, А. Одлижко, Р. Шреппеля [19]. Метод був реалізований і застосований для логарифмування в простих полях при p довжиною до 67 десяткових знаків.
Останнім істотним досягненням у цій галузі є метод решета числового поля Д. Гордона [20]. Асимптотично метод більш ефективний, ніж усі попередні: оцінка його трудомісткості. Однак його практична реалізація складніше: поки є повідомлення, що цим методом вдалося вирішити завдання дискретного логарифмування в простому полі при p довжиною 40 десяткових знаків. Для цього фахівцям німецьког...
