Дискретне логарифмування на еліптичній кривій — розв'язування рівняння відносно за відомих і , де — точки, що належать еліптичній кривій і є зашифрованим повідомленням і початковою точкою відповідно. Інакше кажучи, це метод злому системи безпеки, заснованої на даній еліптичній кривій (наприклад, російський стандарт ЕП ГОСТ Р 34.10-2012), та знаходження секретного ключа.
Історія Еліптична криптографія відноситься до асиметричної криптографії, тобто шифрування відбувається за допомогою відкритого ключа. Вперше цей алгоритм 1985 року незалежно запропонували та . Це було обґрунтовано тим, що дискретний логарифм на еліптичній кривій виявився складнішим від класичного дискретного логарифму на скінченному полі. Донині немає швидких алгоритмів зламу повідомлення, зашифрованого за допомогою еліптичної кривої, у загальному випадку. Вразливості таких шифрів пов'язані переважно з низкою недоліків при доборі початкових даних.
Вступ Метод ґрунтується на зведенні дискретного логарифму на еліптичній кривій до дискретного логарифму в скінченному полі з деяким розширенням поля, на якому задано еліптичну криву. Це значно полегшує задачу, оскільки існують досить швидкі субекспоненційні алгоритми розв'язування дискретного логарифму, які мають складність , або -алгоритм Полларда зі складністю , розроблені для скінченних полів.
Теорія Нехай — еліптична крива, задана у формі Веєрштраса, над скінченним полем порядку :
Припустимо, що коефіцієнти такі, що крива немає особливостей. Точки кривої разом із нескінченно віддаленою точкою , яка є нульовим елементом, утворюють комутативну групу, записувану адитивно, тобто для . Також відомо, що якщо — скінченне поле, то порядок такої групи за теоремою Гассе задовольнятиме рівняння .
Нехай — підгрупа точок , визначених над . Отже, — скінченна комутативна група. Візьмемо точку , що породжує циклічну групу порядку . Тобто .
Задача обчислення дискретних логарифмів полягає в тому, щоб для цієї точки знайти таке, що .
Завдання обчислення дискретних логарифмів у скінченному полі полягає в такому. Нехай — примітивний елемент поля . Для даного ненульового знайти таке, що .
Нехай НСК та розширення поля таке, що містить підгрупу кручення , ізоморфну , тобто . Відомо, що таке розширення існує. З цього випливає, що для деякого . У цьому випадку виконуватиметься така теорема, що дозволяє перейти до дискретного логарифму в розширеному скінченному полі:
Теорема Нехай задано точку таку, що . Тоді складність обчислення дискретних логарифмів у групі не вища від складності обчислення дискретних логарифмів у .
Щоб скористатися цією теоремою, необхідно знати степінь розширення поля над і точку , для якої .
Випадок суперсингулярної еліптичної кривої Для суперсингулярної кривої , і легко знайти, при цьому . Це 1993 року встановили , Окамото Тацуакі та . У статті вони описали ймовірнісний алгоритм обчислення допоміжної точки , середній час роботи якого обмежено поліномом від .
Загальний випадок Нехай — максимальна підгрупа порядок елементів якої є добутком простих множників . Таким чином, і , де ділить і . При цьому (в разі , під знаходження точки можна адаптувати метод для суперсингулярних кривих). Нехай — найменше натуральне число, для якого виконується .
Теорема Нехай НСК . Тоді і, якщо відомий розклад на прості множники, то є ймовірнісний алгоритм обчислення точки , для якої . Середній час роботи алгоритму дорівнює операцій у полі для деякого сталого і .
У випадках, коли НСК , алгоритм працює надто повільно, або не працює зовсім.
Див. також Дискретний логарифм Еліптична криптографія Теорія груп
Примітки
Література
Теорія
Доповнення:
Історія