Математика / Реферат: Складність методів вирішення проблеми дискретного логарифмування в групі точок еліптичної кривої

Реферат: Складність методів вирішення проблеми дискретного логарифмування в групі точок еліптичної кривої

Знаходимо

Перевіряємо

Таким чином

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

де – випадкові цілі числа з інтервалу .

Під час використання формул даного виду можна зменшити складність криптоаналізу. Крім того це дозволяє ефективно розпаралелити процес знаходження коефіцієнтів та , для яких виконується вимога , як мінімум на процесів.

Стійкість заснована на складності розв’язання задачі дискретного логарифмування. У порівнянні з більше ранніми прототипами - криптосистемами Діффі-Хеллмана й Ель-Гамала - вони дають істотний виграш у криптостійкості, або практично на порядок дозволяють скоротити розмір поля при порівняній стійкості. Відомо, що порядку 160 біт порівнянний щодо безпеки з RSA і криптосистемою Eль-Гамала з розміром ключа 1024 біт, причому цей виграш прогресує зі збільшенням довжини ключа.

Щоб оцінити складність (Elliptic Curve Discrete Logarithm Problem ), уявімо на хвилину, що піщина з лінійним розміром 0,1 мм є однією з точок ЕСС . Якої величини буде планета, складена з таких піщин? Якщо -радіус планети в кілометрах, то й км. Це приблизно в раз перевищує радіус нашої планети. Серед цього вражаючого числа піщин потрібно знайти одну. Це й буде розв’язком, порівнянним за складністю з для із числом точок порядку .

Практично обчислювальна складність вимірюється в MIPS-роках (MIPS – Million Instructions per Second - мільйон інструкцій за секунду ). Під однією операцією тут розуміють одне додавання точок кривої. Оцінки часу рішення за допомогою -методу Полларда залежно від розміру поля й порядку криптосистеми наведено в таблиці 2

Проблема дискретного логарифмування на еліптичній кривій формулюється в такий спосіб: відома точка G криптосистеми простого порядку й точка Необхідно знайти ціле число

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