Diskret logaritm på en elliptisk kurva

Diskret logaritm på en elliptisk kurva är lösningen av ekvationen för kända och , där är de punkter som hör till den elliptiska kurvan och är det krypterade meddelandet respektive startpunkten [1] . Det är med andra ord en metod för att hacka ett säkerhetssystem baserat på en given elliptisk kurva (till exempel den ryska standarden EP GOST R 34.10-2012 [2] ) och hitta en hemlig nyckel . $S=nT \pmod{m}$ $n$ $S$ $T$ $S,T$

Historik

Elliptisk kryptografi hänvisar till kategorin asymmetrisk , det vill säga kryptering sker med hjälp av en offentlig nyckel. Denna algoritm föreslogs först oberoende av Neil Koblitz och Victor Miller 1985 [3] . Detta motiverades av det faktum att den diskreta logaritmen på en elliptisk kurva visade sig vara mer komplicerad än den klassiska diskreta logaritmen på ett ändligt fält . Hittills finns det inga snabba algoritmer för att knäcka ett meddelande krypterat med en elliptisk kurva i det allmänna fallet. I grund och botten är sårbarheterna hos sådana chiffer förknippade med ett antal brister i valet av initialdata [4] .

Inledning

Denna metod är baserad på reduktionen av den diskreta logaritmen på en elliptisk kurva till den diskreta logaritmen på ett ändligt fält med viss förlängning av det fält på vilket den elliptiska kurvan gavs. Detta förenklar uppgiften avsevärt, eftersom det för närvarande finns tillräckligt snabba subexponentiella algoritmer för att lösa den diskreta logaritmen, som har komplexitet , eller Pollards algoritm med komplexitet , utvecklad för finita fält [5] . $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})$

Teori

Låt vara en elliptisk kurva som ges i Weierstrass-formen över ett ändligt ordningsfält : $E$ $F_q$ $q$

y^2 + a_1xy + a_3y = x^3 + a_2x^2+ a_4x + a_6

Låt oss anta att koefficienterna är sådana att kurvan inte har några singulariteter . Punkterna i kurvan , tillsammans med punkten vid oändligheten , som är nollelementet, bildar en kommutativ grupp skriven additivt , det vill säga för . Det är också känt att om är ett ändligt fält, då ordningen för en sådan grupp , enligt Hasses sats , kommer att uppfylla ekvationen . $a_i\in F_q$ $E$ $P_\infty$ $\förallt A,B \i E(F_q), A + B = B + A = C \i E(F_q)$ $F_q$ $N_q$ $|N_q-q-1| \le 2 \sqrt{q}$

Låta vara en undergrupp av punkter definierade över . Det är alltså en finit kommutativ grupp. Ta en punkt som genererar en cyklisk ordningsgrupp . Det är [1] . $E(F_{q'})$ $E$ $F_{q'}\supseteq F_q$ $E(F_{q'})$ $P \in E(F_q)$ $m$ $|\langle P\rangle| = m$

Uppgiften att beräkna diskreta logaritmer i är följande. För en given punkt , hitta sådan att . $\langle P\rangle$ $Q\in\langle P\rangle$ $n\pmod{m}$ $nP = Q$

Problemet med att beräkna diskreta logaritmer i ett ändligt fält är som följer. Låt vara en primitiv del av fältet . För en given icke-noll hitta sådan att [6] . $F_q$ $\alfa$ $F_q$ $\beta$ $n \pmod {(q-1)}$ $\alpha^n = \beta$

Låt LCM och en fältförlängning vara sådan att den innehåller en torsionsundergrupp som är isomorf till , det vill säga . Det är känt att en sådan förlängning finns [7] . Av detta följer att för vissa . I det här fallet kommer följande sats att gälla, som tillåter övergång till en diskret logaritm i ett utökat ändligt fält [6] : $(m,q)=1$ $F_{q'} \supseteq F_q$ $E(F_{q'})$ $E[m]$ $\Z/m \ gånger \Z/m$ $E[m] = \{P, T \in E(F_{q'}): mP=0, mT=0 \}$ $q' = q^k$ $k\geqslant 1$

Sats

Låt en poäng ges sådan att . Då är komplexiteten för att beräkna diskreta logaritmer i gruppen inte större än komplexiteten för att beräkna diskreta logaritmer i . $T \in E(F_{q'})$ $\langle P,T\rangle = E[m]$ $\langle P\rangle$ $F_{q'}$

För att använda detta teorem är det nödvändigt att känna till graden av utvidgning av fältet $k$ över och den punkt för vilken [6] . $F_{q'}$ $F_q$ $T$ $\langle P,T\rangle = E[m]$

Fallet med en supersingular elliptisk kurva

För en supersingular kurva , , och är lätt att hitta, medan . Detta etablerades av Alfred Menezes , Okamoto Tatsuaki och Scott Vanstone 1993. I sin artikel beskrev de en probabilistisk algoritm för att beräkna en hjälppunkt , vars genomsnittliga gångtid begränsas av ett polynom i [4] . $E$ $k$ $T$ $k\le 6$ $T$ $\log{q'}$

Allmänt fall

Låt vara den maximala undergruppen vars ordning av element är produkten av primtalsfaktorer . Således, och , där delar och . I detta fall (i fallet kan metoden för supersingularkurvor [6] anpassas för att hitta punkten ). Låta vara det lägsta naturliga antalet som . $G$ $E(F_{q'})$ $m$ $E[m]\subseteq G$ $G= \Z/m_1 \ gånger \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$

Sats

Låt NOK . Sedan och om nedbrytningen till primtalsfaktorer är känd, så finns det en probabilistisk algoritm för att beräkna punkten för vilken . Den genomsnittliga körtiden för algoritmen är lika med operationer i fält för en konstant och . $(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\högerpil\infty$

I de fall LCM , fungerar algoritmen för långsamt, eller fungerar inte alls [6] . $(m, q-1) \neq 1$

Se även

Anteckningar

↑ 1 2 Semaev I. A. Om beräkningen av logaritmer på elliptiska kurvor . - Diskret. Mat., 1996. - V. 8 , nr. 1 . — S. 65–71 .
↑ EP GOST R 34.10-2012 http://www.altell.ru/legislation/standards/gost-34.10-2012.pdf Arkivexemplar daterad 5 mars 2016 på Wayback Machine
↑ Jeffrey Hoffstein, Jill Pipher, Joseph H. Silverman. En introduktion till matematisk kryptografi . — Springer. — 530 sid.
↑ 1 2 Menezes A., Okamoto T., Vanstone S.,. Reducering av elliptiska kurvlogaritmer till logaritmer i ett ändligt fält. IEEE. — Trans. underrätta. Theory, 1993. - S. 1639-1646 .
↑ Don Johnson, Alfred Menezes, Scott Vanstone. The Elliptic Curve Digital Signature Algorithm (ECDSA) . — Certicom Research, Kanada. Arkiverad från originalet den 4 mars 2016.
↑ 1 2 3 4 5 Semaev IA På frågan om att reducera beräkningen av diskreta logaritmer på en elliptisk kurva till beräkningen av diskreta logaritmer i ett ändligt fält . - Diskret. Mat., 1999. - V. 11 , nr. 3 . — S. 24–28 .
↑ Silverman JH The Arithmetic of Elliptic Curves. . - Springer, Berlin, 1986. - 522 sid.

Litteratur

Teori

Semaev IA Om beräkning av logaritmer på elliptiska kurvor . - Diskret. Mat., 1996. - V. 8 , nr. 1 . — S. 65–71 .
- Tillägg: Semaev I. A. På frågan om att reducera beräkningen av diskreta logaritmer på en elliptisk kurva till beräkningen av diskreta logaritmer i ett ändligt fält . - Diskret. Mat., 1999. - V. 11 , nr. 3 . — S. 24–28 .
Don Johnson, Alfred Menezes, Scott Vanstone. The Elliptic Curve Digital Signature Algorithm (ECDSA) . — Certicom Research, Kanada. Arkiverad från originalet den 4 mars 2016.

Berättelse

Jeffrey Hoffstein, Jill Pipher, Joseph H. Silverman. En introduktion till matematisk kryptografi . — Springer. — 530 sid.