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

Дискретне логарифмування на еліптичній кривій — розв'язування рівняння $S=nT{\pmod {m}}$ відносно $n$ за відомих $S$ і $T$, де $S,T$ — точки, що належать еліптичній кривій і є зашифрованим повідомленням і початковою точкою відповідно. Інакше кажучи, це метод злому системи безпеки, заснованої на даній еліптичній кривій (наприклад, російський стандарт ЕП ГОСТ Р 34.10-2012), та знаходження секретного ключа.

$T+T=S$

В цьому випадку розв'язком рівняння $S=nT$ є $n=2$

Історія

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

Вступ

Метод ґрунтується на зведенні дискретного логарифму на еліптичній кривій до дискретного логарифму в скінченному полі з деяким розширенням поля, на якому задано еліптичну криву. Це значно полегшує задачу, оскільки існують досить швидкі субекспоненційні алгоритми розв'язування дискретного логарифму, які мають складність $O\left(\exp \left(c\left(\ln p\right)^{k}\left(\ln \ln p\right)^{k-1}\right)\right)$, або $\rho$ -алгоритм Полларда зі складністю $O({\sqrt {\pi p/2}})$, розроблені для скінченних полів.

Теорія

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

$y^{2}+a_{1}xy+a_{3}y=x^{3}+a_{2}x^{2}+a_{4}x+a_{6}$

Припустимо, що коефіцієнти $a_{i}\in F_{q}$ такі, що крива немає особливостей. Точки кривої $E$ разом із нескінченно віддаленою точкою $P_{\infty }$, яка є нульовим елементом, утворюють комутативну групу, записувану адитивно, тобто для $\forall A,B\in E(F_{q}),A+B=B+A=C\in E(F_{q})$. Також відомо, що якщо $F_{q}$ — скінченне поле, то порядок такої групи $N_{q}$ за теоремою Гассе задовольнятиме рівняння $|N_{q}-q-1|\leq 2{\sqrt {q}}$.

Нехай $E(F_{q'})$ — підгрупа точок $E$, визначених над $F_{q'}\supseteq F_{q}$. Отже, $E(F_{q'})$ — скінченна комутативна група. Візьмемо точку $P\in E(F_{q})$, що породжує циклічну групу порядку $m$. Тобто $|\langle P\rangle |=m$.

Задача обчислення дискретних логарифмів $\langle P\rangle$ полягає в тому, щоб для цієї точки $Q\in \langle P\rangle$ знайти $n{\pmod {m}}$ таке, що $nP=Q$.

Завдання обчислення дискретних логарифмів у скінченному полі $F_{q}$ полягає в такому. Нехай $\alpha$ — примітивний елемент поля $F_{q}$. Для даного ненульового $\beta$ знайти $n{\pmod {(q-1)}}$ таке, що $\alpha ^{n}=\beta$.

Нехай НСК $(m,q)=1$ та розширення поля $F_{q'}\supseteq F_{q}$ таке, що $E(F_{q'})$ містить підгрупу кручення $E[m]$, ізоморфну $\mathbb {Z} /m\times \mathbb {Z} /m$, тобто $E[m]=\{P,T\in E(F_{q'}):mP=0,mT=0\}$. Відомо, що таке розширення існує. З цього випливає, що $q'=q^{k}$ для деякого $k\geqslant 1$. У цьому випадку виконуватиметься така теорема, що дозволяє перейти до дискретного логарифму в розширеному скінченному полі:

Теорема

Нехай задано точку $T\in E(F_{q'})$ таку, що $\langle P,T\rangle =E[m]$. Тоді складність обчислення дискретних логарифмів у групі $\langle P\rangle$ не вища від складності обчислення дискретних логарифмів у $F_{q'}$.

Щоб скористатися цією теоремою, необхідно знати степінь $k$ розширення поля $F_{q'}$ над $F_{q}$ і точку $T$, для якої $\langle P,T\rangle =E[m]$.

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

Для суперсингулярної кривої $E$, $k$ і $T$ легко знайти, при цьому $k\leq 6$. Це 1993 року встановили Альфред Менезес, Окамото Тацуакі та Скотт Ванстоун. У статті вони описали ймовірнісний алгоритм обчислення допоміжної точки $T$, середній час роботи якого обмежено поліномом від $\log {q'}$.

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

Нехай $G$ — максимальна підгрупа $E(F_{q'})$ порядок елементів якої є добутком простих множників $m$. Таким чином, $E[m]\subseteq G$ і $G=\mathbb {Z} /m_{1}\times \mathbb {Z} /m_{2}$, де $m$ ділить $m_{1}$ і $m_{2}$. При цьому $m_{1}\neq m_{2}$ (в разі $m_{1}=m_{2}$, під знаходження точки $T$ можна адаптувати метод для суперсингулярних кривих). Нехай $l$ — найменше натуральне число, для якого виконується $q^{l}\equiv 1{\pmod {m}}$.

Теорема

Нехай НСК $(m,q-1)=1$. Тоді $k=l$ і, якщо відомий розклад $m$ на прості множники, то є ймовірнісний алгоритм обчислення точки $T\in E(F_{q'})$, для якої $\langle P,T\rangle =E[m]$. Середній час роботи алгоритму дорівнює $O(log^{c}{q'})$ операцій у полі $F_{q'}$ для деякого сталого $c$ і $m\rightarrow \infty$.

У випадках, коли НСК $(m,q-1)\neq 1$, алгоритм працює надто повільно, або не працює зовсім.

Див. також

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

Література

Теорія

• Семаев И. А. О вычислении логарифмов на эллиптических кривых. — Дискрет. матем., 1996. — Т. 8, вып. 1 (21 апреля). — С. 65–71.
  • Доповнення: Семаев И. А. К вопросу о сведении вычисления дискретных логарифмов на эллиптической кривой к вычислению дискретных логарифмов в конечном поле. — Дискрет. матем., 1999. — Т. 11, вип. 3 (21 квітня). — С. 24–28.
• Don Johnson, Alfred Menezes, Scott Vanstone. The Elliptic Curve Digital Signature Algorithm (ECDSA). — Certicom Research, Canada. Архівовано з джерела 4 березня 2016.

Історія

• Jeffrey Hoffstein, Jill Pipher, Joseph H. Silverman. An Introduction to Mathematical Cryptography. — Springer. — 530 с.