Logaritm discret pe o curbă eliptică

Logaritmul discret pe o curbă eliptică este soluția ecuației pentru cunoscut și , unde sunt punctele aparținând curbei eliptice și fiind mesajul criptat și respectiv punctul de plecare [1] . Cu alte cuvinte, este o metodă de a pirata un sistem de securitate bazat pe o curbă eliptică dată (de exemplu, standardul rus EP GOST R 34.10-2012 [2] ) și de a găsi o cheie secretă . $S=nT \pmod{m}$ $n$ $S$ $T$ $SF$

Istorie

Criptografia eliptică se referă la categoria asimetrică , adică criptarea are loc folosind o cheie publică. Acest algoritm a fost propus pentru prima dată independent de Neil Koblitz și Victor Miller în 1985 [3] . Acest lucru a fost justificat de faptul că logaritmul discret pe o curbă eliptică sa dovedit a fi mai complicat decât logaritmul discret clasic pe un câmp finit . Până acum, nu există algoritmi rapizi pentru spargerea unui mesaj criptat folosind o curbă eliptică în cazul general. Practic , vulnerabilitățile unor astfel de cifruri sunt asociate cu o serie de neajunsuri în selectarea datelor inițiale [4] .

Introducere

Această metodă se bazează pe reducerea logaritmului discret pe o curbă eliptică la logaritmul discret pe un câmp finit cu o anumită extindere a câmpului pe care a fost dată curba eliptică. Acest lucru simplifică foarte mult sarcina, deoarece în momentul de față există algoritmi subexponențiali suficient de rapizi pentru rezolvarea logaritmului discret, care au complexitate , sau algoritmul lui Pollard cu complexitate , dezvoltați pentru câmpuri finite [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})$

Teorie

Fie o curbă eliptică dată în forma Weierstrass pe un câmp finit de ordin : $E$ $F_q$ $q$

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

Să presupunem că coeficienții sunt astfel încât curba nu are singularități . Punctele curbei , împreună cu punctul de la infinit , care este elementul zero, formează un grup comutativ scris aditiv , adică pentru . De asemenea, se știe că dacă este un câmp finit, atunci ordinea unui astfel de grup , conform teoremei lui Hasse , va satisface ecuația . $a_i\în 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| \le 2 \sqrt{q}$

Fie un subgrup de puncte definite peste . Prin urmare, este un grup comutativ finit . Luați un punct care generează un grup ciclic de ordine . Adică [1] . $E(F_{q'})$ $E$ $F_{q'}\supseteq F_q$ $E(F_{q'})$ $P \in E(F_q)$ $m$ $|\langle P\rangle| = m$

Sarcina de a calcula logaritmi discreti în este următoarea. Pentru un punct dat , găsiți astfel încât . $\langle P\rangle$ $Q\in\langle P\rangle$ $n\pmod{m}$ $nP = Q$

Problema calculării logaritmilor discreti într-un câmp finit este următoarea. Fie un element primitiv al câmpului . Pentru o dată diferită de zero găsiți astfel încât [6] . $F_q$ $\alfa$ $F_q$ $\beta$ $n \pmod {(q-1)}$ $\alpha^n = \beta$

Fie LCM și o extensie de câmp astfel încât să conțină un subgrup de torsiune izomorf la , adică . Se știe că o asemenea extensie există [7] . De aici rezultă că pentru unii . În acest caz, următoarea teoremă va fi valabilă, care permite trecerea la un logaritm discret într-un câmp finit extins [6] : $(m,q)=1$ $F_{q'} \supseteq F_q$ $E(F_{q'})$ $E[m]$ $\Z/m \times \Z/m$ $E[m] = \{P, T \in E(F_{q'}): mP=0, mT=0 \}$ $q' = q^k$ $k\geqslant 1$

Teorema

Să se acorde un punct astfel încât . Atunci complexitatea calculării logaritmilor discreti în grup nu este mai mare decât complexitatea calculării logaritmilor discreti în . $T \in E(F_{q'})$ $\langle P,T\rangle = E[m]$ $\langle P\rangle$ $F_{q'}$

Pentru a utiliza această teoremă, este necesar să se cunoască gradul de extindere a câmpului $k$ peste și punctul pentru care [6] . $F_{q'}$ $F_q$ $T$ $\langle P,T\rangle = E[m]$

Cazul unei curbe eliptice suprasingulare

Pentru o curbă supersingulară , , și sunt ușor de găsit, în timp ce . Acesta a fost stabilit de Alfred Menezes , Okamoto Tatsuaki și Scott Vanstone în 1993. În articolul lor, ei au descris un algoritm probabilistic pentru calcularea unui punct auxiliar , al cărui timp mediu de rulare este limitat de un polinom în [4] . $E$ $k$ $T$ $k\le 6$ $T$ $\log{q'}$

Caz general

Fie subgrupul maxim a cărui ordine a elementelor este produsul factorilor primi . Astfel, și , unde se împarte și . În acest caz (în cazul , metoda pentru curbele supersingulare [6] poate fi adaptată pentru a găsi punctul ). Fie numărul natural minim pentru care . $G$ $E(F_{q'})$ $m$ $E[m]\subseteq G$ $G= \Z/m_1 \times \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$

Teorema

Lasă NOK . Atunci și dacă este cunoscută descompunerea în factori primi, atunci există un algoritm probabilistic pentru calcularea punctului pentru care . Timpul mediu de rulare al algoritmului este egal cu operațiile din câmp pentru o constantă și . $(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$

În cazurile în care LCM , algoritmul funcționează prea lent, sau nu funcționează deloc [6] . $(m, q-1) \neq 1$

Vezi și

Note

↑ 1 2 Semaev I. A. Despre calculul logaritmilor pe curbele eliptice . — Discret. 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 Copie de arhivă din 5 martie 2016 la Wayback Machine
↑ Jeffrey Hoffstein, Jill Pipher, Joseph H. Silverman. O introducere în criptografia matematică . — Springer. — 530 p.
↑ 1 2 Menezes A., Okamoto T., Vanstone S.,. Reducerea logaritmilor curbei eliptice la logaritmi într-un câmp finit. IEEE. — Trans. informa. Teorie, 1993. - S. 1639-1646 .
↑ Don Johnson, Alfred Menezes, Scott Vanstone. Algoritmul de semnătură digitală cu curbă eliptică (ECDSA) . — Certicom Research, Canada. Arhivat din original pe 4 martie 2016.
↑ 1 2 3 4 5 Semaev IA Despre problema reducerii calculului logaritmilor discreti pe o curbă eliptică la calculul logaritmilor discreti într-un câmp finit . — Discret. Mat., 1999. - V. 11 , nr. 3 . — S. 24–28 .
↑ Silverman JH Aritmetica curbelor eliptice. . - Springer, Berlin, 1986. - 522 p.

Literatură

Teorie

Semaev IA Despre calculul logaritmilor pe curbele eliptice . — Discret. Mat., 1996. - V. 8 , nr. 1 . — S. 65–71 .
- Supliment: Semaev I. A. Cu privire la problema reducerii calculului logaritmilor discreti pe o curbă eliptică la calculul logaritmilor discreti într-un câmp finit . — Discret. Mat., 1999. - V. 11 , nr. 3 . — S. 24–28 .
Don Johnson, Alfred Menezes, Scott Vanstone. Algoritmul de semnătură digitală cu curbă eliptică (ECDSA) . — Certicom Research, Canada. Arhivat din original pe 4 martie 2016.

Poveste

Jeffrey Hoffstein, Jill Pipher, Joseph H. Silverman. O introducere în criptografia matematică . — Springer. — 530 p.