Diszkrét logaritmus elliptikus görbén

A diszkrét logaritmus elliptikus görbén az ismert és -re vonatkozó egyenlet megoldása , ahol az elliptikus görbéhez tartozó pontok, amelyek a titkosított üzenet , illetve a kiindulási pont [1] . Más szóval, ez egy módszer egy biztonsági rendszer feltörésére egy adott elliptikus görbe alapján (például az orosz szabvány EP GOST R 34.10-2012 [2] ) és titkos kulcs megtalálása . $S=nT \pmod{m}$ $n$ $S$ $T$ $UTCA$

Történelem

Az elliptikus kriptográfia az aszimmetrikus kategóriára utal , vagyis a titkosítás nyilvános kulcs használatával történik. Ezt az algoritmust először egymástól függetlenül Neil Koblitz és Victor Miller javasolta 1985-ben [3] . Ezt az indokolta, hogy az elliptikus görbén a diszkrét logaritmus bonyolultabbnak bizonyult, mint a klasszikus diszkrét logaritmus véges téren . Eddig általános esetben nem léteztek gyors algoritmusok az elliptikus görbével titkosított üzenetek feltörésére. Alapvetően az ilyen titkosítások sebezhetősége számos hiányossággal jár a kezdeti adatok kiválasztásában [4] .

Bevezetés

Ez a módszer egy elliptikus görbe diszkrét logaritmusának redukálásán alapul egy véges mező diszkrét logaritmusára, annak a mezőnek a kiterjesztésével , amelyen az elliptikus görbét adtuk. Ez nagymértékben leegyszerűsíti a feladatot, hiszen a diszkrét logaritmus megoldására jelenleg kellően gyors szubexponenciális algoritmusok léteznek , amelyek komplexitása , vagy a véges mezőkre kifejlesztett Pollard-féle komplexitású algoritmus [ 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})$

Elmélet

Legyen a Weierstrass alakban megadott elliptikus görbe egy véges rendmező felett : $E$ $F_q$ $q$

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

Tegyük fel, hogy az együtthatók olyanok, hogy a görbének nincs szingularitása . A görbe pontjai a végtelen ponttal együtt , amely a nulla elem, additívan írt kommutatív csoportot alkotnak , azaz -re . Az is ismert, hogy ha véges mező, akkor egy ilyen csoport sorrendje Hasse tétele szerint kielégíti az egyenletet . $a_i\in F_q$ $E$ $P_\infty$ $\minden 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}$

Hagy egy részcsoportja pontok felett meghatározott . Tehát véges kommutatív csoport. Vegyünk egy pontot , amely egy ciklikus sorrendi csoportot generál . Azaz [1] . $E(F_{q'})$ $E$ $F_{q'}\supseteq F_q$ $E(F_{q'})$ $P \in E(F_q)$ $m$ $|\langle P\rangle| = m$

A diszkrét logaritmusok kiszámításának feladata a következő. Adott ponthoz keressen olyat, hogy . $\langle P\rangle$ $Q\in\langle P\rangle$ $n\pmod{m}$ $nP = Q$

A diszkrét logaritmusok véges mezőben történő kiszámításának problémája a következő. Legyen a mező primitív eleme . Adott nullától eltérő leletre úgy, hogy [6] . $F_q$ $\alpha$ $F_q$ $\beta$ $n \pmod {(q-1)}$ $\alpha^n = \beta$

Legyen az LCM és egy mezőbővítmény olyan, hogy tartalmazzon egy torziós alcsoportot , amely izomorf -ra , azaz . Ismeretes, hogy létezik ilyen kiterjesztés [7] . Ebből az következik, hogy egyesek számára . Ebben az esetben a következő tétel érvényesül, amely lehetővé teszi a diszkrét logaritmusra való átlépést kiterjesztett véges mezőben [6] : $(m, q) = 1$ $F_{q'} \supseteq F_q$ $E(F_{q'})$ $E[m]$ $\Z/m \szer \Z/m$ $E[m] = \{P, T \in E(F_{q'}): mP=0, mT=0 \}$ $q' = q^k$ $k\geqslant 1$

Tétel

Adjunk egy pontot úgy , hogy . Ekkor a diszkrét logaritmusok kiszámításának bonyolultsága a csoportban nem nagyobb, mint a diszkrét logaritmusok kiszámításának bonyolultsága a -ban . $T \in E(F_{q'})$ $\langle P,T\rangle = E[m]$ $\langle P\rangle$ $F_{q'}$

Ennek a tételnek a használatához ismerni kell a mező kiterjesztésének mértékét $k$ és azt a pontot , amelyre [6] . $F_{q'}$ $F_q$ $T$ $\langle P,T\rangle = E[m]$

Egy szuperszinguláris elliptikus görbe esete

Szinguláris feletti görbe esetén a , és könnyen megtalálhatók, míg . Ezt Alfred Menezes , Okamoto Tatsuaki és Scott Vanstone alapította 1993-ban. Cikkükben egy valószínűségi algoritmust írtak le egy segédpont kiszámítására , amelynek átlagos futási idejét egy polinom korlátozza a [4]-ben . $E$ $k$ $T$ $k\le 6$ $T$ $\log{q'}$

Általános eset

Legyen az a maximális részcsoport , amelynek elemeinek sorrendje a prímtényezők szorzata . Így, és , ahol osztja és . Ebben az esetben (az esetben a szuperszinguláris görbék módszere [6] adaptálható a pont megkeresésére ). Legyen az a minimális természetes szám, amelyre . $G$ $E(F_{q'})$ $m$ $E[m]\subseteq G$ $G= \Z/m_1 \szor \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$

Tétel

Legyen NOK . Ekkor és ha ismert a prímtényezőkre való bontás , akkor létezik egy valószínűségi algoritmus annak a pontnak a kiszámítására, amelyre . Az algoritmus átlagos futási ideje megegyezik a terepen végzett műveletekkel valamilyen állandó és . $(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$

Azokban az esetekben, amikor LCM , az algoritmus túl lassan, vagy egyáltalán nem működik [6] . $(m, q-1) \neq 1$

Lásd még

Jegyzetek

↑ 1 2 Semaev I. A. Az elliptikus görbék logaritmusainak kiszámításáról . - Diszkrét. Mat., 1996. - V. 8 , sz. 1 . – S. 65–71 .
↑ EP GOST R 34.10-2012 http://www.altell.ru/legislation/standards/gost-34.10-2012.pdf Archív másolat 2016. március 5-én a Wayback Machine -nél
↑ Jeffrey Hoffstein, Jill Pipher, Joseph H. Silverman. Bevezetés a matematikai kriptográfiába . — Springer. — 530 p.
↑ 1 2 Menezes A., Okamoto T., Vanstone S.,. Elliptikus görbe logaritmusainak redukálása véges mező logaritmusaira. IEEE. — Transz. tájékoztatni. Elmélet, 1993. - S. 1639-1646 .
↑ Don Johnson, Alfred Menezes, Scott Vanstone. Az elliptikus görbe digitális aláírási algoritmusa (ECDSA) . – Certicom Research, Kanada. Az eredetiből archiválva: 2016. március 4.
↑ 1 2 3 4 5 Semaev IA Arról a kérdésről, hogy az elliptikus görbén lévő diszkrét logaritmusok számítását a véges mezőben lévő diszkrét logaritmusok kiszámítására lehet redukálni . - Diszkrét. Mat., 1999. - V. 11 , sz. 3 . – S. 24–28 .
↑ Silverman JH Az elliptikus görbék aritmetikája. . - Springer, Berlin, 1986. - 522 p.

Irodalom

Elmélet

Semaev IA Az elliptikus görbék logaritmusainak kiszámításáról . - Diszkrét. Mat., 1996. - V. 8 , sz. 1 . – S. 65–71 .
- Kiegészítés: Semaev I. A. Az elliptikus görbén lévő diszkrét logaritmusok számításának a véges mezőben történő diszkrét logaritmusok kiszámítására való redukálásáról . - Diszkrét. Mat., 1999. - V. 11 , sz. 3 . – S. 24–28 .
Don Johnson, Alfred Menezes, Scott Vanstone. Az elliptikus görbe digitális aláírási algoritmusa (ECDSA) . – Certicom Research, Kanada. Az eredetiből archiválva: 2016. március 4.

Sztori

Jeffrey Hoffstein, Jill Pipher, Joseph H. Silverman. Bevezetés a matematikai kriptográfiába . — Springer. — 530 p.