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

$T+T=S$

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

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

Історія

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

Вступ

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

Теорія

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

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

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

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

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

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

Теорема

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

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

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

Для суперсингулярної кривої $E$, $k$ і $T$ легко знайти, при цьому $k\le 6$. Це 1993 року встановили Шаблон:Нп, Окамото Тацуакі та Шаблон:Нп. У статті вони описали ймовірнісний алгоритм обчислення допоміжної точки $T$, середній час роботи якого обмежено поліномом від $\log q^{\prime }$.

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

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

Теорема

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

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

Див. також

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

Література

Теорія

• Шаблон:Стаття
  • Доповнення: Шаблон:Стаття
• Шаблон:Стаття

Історія

• Шаблон:Книга