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

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

${\displaystyle T+T=S}$

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

Історія

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

Вступ

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

Теорія

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

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

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

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

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

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

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

Теорема

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

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

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

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

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

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

Теорема

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

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

Див. також

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