Дискретне логарифмування на еліптичній кривій

метод злому системи безпеки, заснованої на еліптичній кривій

Дискретне логарифмування на еліптичній кривій — розв'язування рівняння відносно за відомих і , де  — точки, що належать еліптичній кривій і є зашифрованим повідомленням і початковою точкою відповідно[1]. Інакше кажучи, це метод злому системи безпеки, заснованої на даній еліптичній кривій (наприклад, російський стандарт ЕП ГОСТ Р 34.10-2012), та знаходження секретного ключа.

В цьому випадку розв'язком рівняння є

Історія ред.

Еліптична криптографія відноситься до асиметричної криптографії, тобто шифрування відбувається за допомогою відкритого ключа. Вперше цей алгоритм 1985 року незалежно запропонували Ніл Коблиць[en] та Віктор Міллер[en][2]. Це було обґрунтовано тим, що дискретний логарифм на еліптичній кривій виявився складнішим від класичного дискретного логарифму на скінченному полі. Донині немає швидких алгоритмів зламу повідомлення, зашифрованого за допомогою еліптичної кривої, у загальному випадку. Вразливості таких шифрів пов'язані переважно з низкою недоліків при доборі початкових даних[3].

Вступ ред.

Метод ґрунтується на зведенні дискретного логарифму на еліптичній кривій до дискретного логарифму в скінченному полі з деяким розширенням поля, на якому задано еліптичну криву. Це значно полегшує задачу, оскільки існують досить швидкі субекспоненційні алгоритми розв'язування дискретного логарифму, які мають складність  , або   -алгоритм Полларда зі складністю  , розроблені для скінченних полів[4].

Теорія ред.

Нехай   — еліптична крива, задана у формі Веєрштраса, над скінченним полем   порядку  :

 

Припустимо, що коефіцієнти   такі, що крива немає особливостей. Точки кривої   разом із нескінченно віддаленою точкою  , яка є нульовим елементом, утворюють комутативну групу, записувану адитивно, тобто для  . Також відомо, що якщо   — скінченне поле, то порядок такої групи   за теоремою Гассе задовольнятиме рівняння  .

Нехай   — підгрупа точок  , визначених над  . Отже,   — скінченна комутативна група. Візьмемо точку  , що породжує циклічну групу порядку  . Тобто  [1].

Задача обчислення дискретних логарифмів   полягає в тому, щоб для цієї точки   знайти   таке, що  .

Завдання обчислення дискретних логарифмів у скінченному полі   полягає в такому. Нехай   — примітивний елемент поля  . Для даного ненульового   знайти   таке, що  [5].

Нехай НСК   та розширення поля   таке, що   містить підгрупу кручення  , ізоморфну  , тобто  . Відомо, що таке розширення існує[6]. З цього випливає, що   для деякого  . У цьому випадку виконуватиметься така теорема, що дозволяє перейти до дискретного логарифму в розширеному скінченному полі[5]:

Теорема ред.

Нехай задано точку   таку, що  . Тоді складність обчислення дискретних логарифмів у групі   не вища від складності обчислення дискретних логарифмів у  .

Щоб скористатися цією теоремою, необхідно знати степінь   розширення поля   над   і точку  , для якої  [5].

Випадок суперсингулярної еліптичної кривої ред.

Для суперсингулярної кривої  ,   і   легко знайти, при цьому  . Це 1993 року встановили Альфред Менезес[en], Окамото Тацуакі та Скотт Ванстоун[en]. У статті вони описали ймовірнісний алгоритм обчислення допоміжної точки  , середній час роботи якого обмежено поліномом від  [3].

Загальний випадок ред.

Нехай   — максимальна підгрупа   порядок елементів якої є добутком простих множників  . Таким чином,   і  , де   ділить   і  . При цьому   (в разі  , під знаходження точки   можна адаптувати метод для суперсингулярних кривих[5]). Нехай   — найменше натуральне число, для якого виконується  .

Теорема ред.

Нехай НСК  . Тоді   і, якщо відомий розклад   на прості множники, то є ймовірнісний алгоритм обчислення точки  , для якої  . Середній час роботи алгоритму дорівнює   операцій у полі   для деякого сталого   і  .

У випадках, коли НСК  , алгоритм працює надто повільно, або не працює зовсім[5].

Див. також ред.

Примітки ред.

  1. а б Семаев И. А. О вычислении логарифмов на эллиптических кривых. — Дискрет. матем., 1996. — Т. 8, вип. 1 (10 лютого). — С. 65–71.
  2. Jeffrey Hoffstein, Jill Pipher, Joseph H. Silverman. An Introduction to Mathematical Cryptography. — Springer. — 530 с.
  3. а б Menezes A., Okamoto T., Vanstone S.,. Reducing elliptic curve logarithms to logarithms in a finite field. IEEE. — Trans. Inform. Theory, 1993. — 10 лютого. — С. 1639—1646.
  4. Don Johnson, Alfred Menezes, Scott Vanstone. The Elliptic Curve Digital Signature Algorithm (ECDSA). — Certicom Research, Canada. Архівовано з джерела 4 березня 2016.
  5. а б в г д Семаев И. А. К вопросу о сведении вычисления дискретных логарифмов на эллиптической кривой к вычислению дискретных логарифмов в конечном поле. — Дискрет. матем., 1999. — Т. 11, вип. 3 (10 лютого). — С. 24–28.
  6. Silverman J. H. The Arithmetic of Elliptic Curves. — Springer, Berlin, 1986. — 522 с.

Література ред.

Теорія
Історія