ECDSA

Az oldal jelenlegi verzióját még nem ellenőrizték tapasztalt közreműködők, és jelentősen eltérhet a 2020. április 27-én felülvizsgált verziótól ; az ellenőrzések 27 szerkesztést igényelnek .

Az ECDSA (Elliptic Curve Digital Signature Algorithm) egy nyilvános kulcsú algoritmus , amelyet elektronikus digitális aláírás létrehozására és ellenőrzésére használnak elliptikus görbe kriptográfia segítségével .

Történelem

Az elliptikus görbéket, mint matematikai fogalmat régóta tanulmányozzák, számos tudományos közlemény létezik ebben a témában. Azonban minden kutatás ellenére valós problémákra, különösen a kriptográfiára való alkalmazásuk a 20. század végéig ismeretlen volt. 1985-ben Victor Miller és Neil Koblitz javasolta az elliptikus görbék használatát a kriptográfiában.

1991-ben a DSA -t a National Institute of Standards and Technology (NIST) fejlesztette ki, a moduláris aritmetika és a diszkrét logaritmus - probléma köré épülve . Nem sokkal ezután a NIST nyilvános megjegyzéseket kért a digitális aláírási sémákra vonatkozó javaslatához [O 1] . Ettől az ötlettől ihletett Scott Vanstone a "Responses to NIST's javaslat" című cikkében a digitális aláírási algoritmus analógját javasolta elliptikus görbe kriptográfiát (ECDSA) használva.

Az 1998-2000 közötti időszakban. Az ECDSA-t különböző szervezetek szabványként fogadták el ( ISO 14888-3, ANSI X9.62, IEEE 1363-2000, FIPS 186-2).

Alkalmazás

Az ECDSA-t kriptovaluta-tranzakciókban (például Bitcoin és Ethereum ) használják annak biztosítására, hogy a pénzeszközöket csak a jogos tulajdonosaik költhessék el [Y 1] .

Az elliptikus görbe alapvető paraméterei

Egy véges mező feletti elliptikus görbe fő paraméterei (eng. domain paraméterek) a következő mennyiségek halmaza: ${\textstyle D=(q,FR,a,b,G,n,h)}$ $\mathbb {F} _{q}$

A végső mező sorrendje (például egy egyszerű véges mező at , ahol és egy prímszám ). $q$ $\mathbb {F} _{p}$ ${\textstyle q=p}$ ${\textstyle p>3}$
${\textstyle FR}$ (Mezőábrázolás) egy mutató , amely a mezőhöz tartozó elemek megjelenítésére szolgál . $\mathbb {F} _{q}$
A mező két eleme, amelyek a mező feletti elliptikus görbe egyenletének együtthatóit határozzák meg (például at ). ${\displaystyle a,b\in \mathbb {F} _{q))$ $E$ $\mathbb {F} _{q}$ $y^{2}=x^{3}+ax+b$ $q=p>3$
Egy alappont , amelynek elsődleges sorrendje van . ${\textstyle G=(x_{G},y_{G})\in E(\mathbb {F} _{q})}$ $n$
Egy egész szám , amely kofaktora , ahol a görbe sorrendje, amely számszerűen egybeesik a pontok számával . ${\textstyle h}$ ${\textstyle h=\#E(\mathbb {F} _{q})/n}$ ${\textstyle \#E(\mathbb {F} _{q})}$ ${\textstyle E(\mathbb {F} _{q})}$

A paramétereket úgy kell megválasztani, hogy a véges mező felett meghatározott elliptikus görbe ellenálljon az ECDLP -re alkalmazható összes ismert támadásnak . Ezenkívül biztonsági vagy megvalósítási megfontolások vonatkozhatnak más korlátozásokra is. $\mathbb {F} _{q}$

Általános szabály, hogy a fő paraméterek az entitások egy csoportjára vonatkoznak, de egyes alkalmazásokban (implementációkban) minden egyes felhasználóra jellemzőek lehetnek [O 2] .

ECDSA az ANSI X9.62 szerint

A gyakorlati alkalmazás érdekében az ECDSA korlátozásokat ír elő azokra a mezőkre, amelyekben elliptikus görbéket határoznak meg. Az egyszerűség kedvéért vegyük figyelembe az algoritmusok megvalósításának esetét, amikor egy egyszerű véges mező, (más mezőkhöz hasonlóan), akkor az elliptikus egyenletünk a formát veszi fel . $\mathbb {F} _{q}$ ${\textstyle y^{2}=x^{3}+ax+b}$

Algoritmus az alapvető paraméterek generálásához

Az elliptikus görbe pontjainak csoportjában a diszkrét logaritmuson alapuló ismert támadások elkerülése érdekében szükséges, hogy az elliptikus görbe pontjainak száma kellően nagy prímszámmal osztható legyen . Az ANSI X9.62 szabvány megköveteli . $E$ $n$ $n > 2^{160}$

Bevitel : Mezősorrend , mezőbemutató jelző a , - biztonsági szint: és . Következtetés : Az elliptikus görbe fő paraméterei .

q

FR

{\textstyle \mathbb {F} _{q))

L

{\textstyle 160\leqslant L\leqslant [\log _{2}q]}

{\textstyle 2^{L}\geqslant 4{\sqrt {q))}

{\textstyle D=(q,FR,a,b,G,n,h)}

1. lépés: Válassza ki a véletlenszerűen ellenőrzött elemeket , amelyek megfelelnek a feltételnek . A 2. lépésben a görbe sorrendje kiszámítható a SEA algoritmussal . 3. lépés : Ellenőrizze, hogy van-e nagy prímszám . Ha nem, akkor folytassa az 1. lépéssel. 4. lépés. Ellenőrizze, hogy . Ha nem, akkor folytassa az 1. lépéssel. 5. lépés . Ellenőrizze, hogy . Ha nem, akkor folytassa az 1. lépéssel. 6. lépés. 7. lépés : Válasszon egy tetszőleges pontot , és állítsa be a . Ismételje addig, amíg , hol van a pont a végtelenben 8. lépés. Vissza

{\textstyle a,b\in \mathbb {F} _{q))

4a^{3}+27b^{2}\not \equiv 0{\bmod {q))

{\textstyle N:=\#E(\mathbb {F} _{q})}

{\textstyle N{\bmod {n}}=0}

n\geqslant 2^{L}

q^{k}-1{\bmod {n}}=0

\forall k\in [1,20]

n\neq q

h:=N/n

{\textstyle G^{'}\in E(\mathbb {F} _{q})}

{\textstyle G:=hG^{'}}

{\textstyle G\neq {\mathcal {O}}}

\mathcal{O}

{\textstyle (q,FR,a,b,G,n,h)}

A véletlenszerű ellenőrző algoritmusok garantálják, hogy egy véges mező feletti elliptikus görbe abszolút véletlenszerűen jött létre [O 2] .

Algoritmus kulcspár generálására

Nézzük az Alice és Bob közötti üzenetváltást . Korábban a fő paraméterek generálására szolgáló algoritmus segítségével Alice megkapta az elliptikus görbe fő paramétereit. A következő műveletsor segítségével Alice létrehoz egy nyilvános és privát kulcsot.

Bemenet : Az elliptikus görbe alapvető paraméterei . Következtetés : Nyilvános kulcs - , privát kulcs - .

{\textstyle D}

K

d

1. lépés: Válasszon egy véletlenszerű vagy pszeudo-véletlen egész számot . 2. lépés Számítsa ki egy pont koordinátáit egy elliptikus görbén . 3. lépés: Vissza .

d\in [1,n-1]

Q=dG

{\megjelenítési stílus (Q,d)}

Nyilvános kulcs ellenőrző algoritmus

A nyilvános kulcsok ellenőrzésének célja annak megerősítése, hogy egy nyilvános kulcs rendelkezik-e bizonyos aritmetikai tulajdonságokkal . Ennek az algoritmusnak a sikeres végrehajtása bizonyítja, hogy a hozzá tartozó privát kulcs matematikailag létezik, de nem garantálja, hogy valaki nem számította ki az adott privát kulcsot, vagy hogy az igényelt tulajdonos valóban rendelkezik vele.

Bemenet : Elliptikus görbe alapvető paraméterei , nyilvános kulcs- . Következtetés : Döntés a nyilvános kulcs érvényességének elfogadásáról vagy elutasításáról .

{\textstyle D}

K

K

1. lépés Ellenőrizze, hogy . 2. lépés. Ellenőrizze, hogy mik a helyesen ábrázolt elemek , pl. -hez tartozó egész számok . 3. lépés Ellenőrizze, hogy mi felel meg a mező elemei által meghatározott elliptikus görbe egyenletnek . 4. lépés Ellenőrizze, hogy . 5. lépés: Ha valamelyik ellenőrzés sikertelen, akkor adja vissza az "Elutasítás"-t, ellenkező esetben az "Elfogadás"-t.

{\textstyle Q\neq {\mathcal {O}}}

{\textstyle (x_{G},y_{G})}

{\textstyle \mathbb {F} _{q))

{\textstyle [1,q-1]}

{\textstyle Q}

{\textstyle a,b}

{\textstyle nQ={\mathcal {O}}}

Digitális aláírás generálási algoritmus

Alice, aki rendelkezik a görbe és a privát kulcs fő paramétereivel, alá akarja írni az üzenetet , ehhez aláírást kell generálnia . $D$ $d$ $m$ $(r,s)$

A következőkben olyan kriptográfiai hash függvényt jelöl, amelynek kimeneti értéke legfeljebb bithosszú (ha ez a feltétel nem teljesül, akkor a kimeneti érték csonkolható). Feltételezzük, hogy a függvény már egész számmá konvertált kimenetével dolgozunk. ${\mathcal {H}}$ $n$ ${\mathcal {H}}$

Bemenet : Elliptikus görbe alapvető paraméterei , privát kulcs , üzenet . Következtetés : Aláírás .

{\textstyle D}

d

m

(r,s)

1. lépés: Válasszon egy véletlenszerű vagy pszeudo-véletlen egész számot . 2. lépés Számítsa ki a pont koordinátáit 3. lépés. Számítsa ki . Ha , akkor folytassa az 1. lépéssel. 4. lépés: Számítsa ki . 5. lépés Számítsa ki . Ha , akkor folytassa az 1. lépéssel. 6. lépés : Visszatérés .

k\in [1,n-1]

kQ=(x_{1},y_{1}).

r=x_{1}{\bmod {n))

r=0

e={\mathcal {H}}(m)

s=k^{-1}(e+dr){\bmod {n))

s=0

(r,s)

Digitális aláírás ellenőrzési algoritmus

Annak ellenőrzésére, hogy Alice aláírta- e az üzenetet , Bob megkapja az alapvető görbeparaméterek és a hozzájuk tartozó nyilvános kulcs hiteles másolatát . $(r, s)$ $m$ $D$ $K$

Bemenet : Elliptikus görbe alapvető paraméterei , nyilvános kulcs , üzenet , aláírás . Következtetés : Döntés az aláírás elfogadásáról vagy elutasításáról.

{\textstyle D}

K

m

(r,s)

1. lépés: Ellenőrizze, hogy a következőhöz tartozó egész számok-e . Ha valamelyik érvényesítés sikertelen, adja vissza az „Elutasítás” parancsot. 2. lépés Számítsa ki . 3. lépés Számítsa ki . 4. lépés Számítsa ki és . 5. lépés Számítsa ki a pont koordinátáit . 6. lépés : Ha , akkor adja vissza az "Elutasítás" parancsot. Ellenkező esetben számolj . 7. lépés : Ha , akkor adja vissza az "Elfogadás", ellenkező esetben az "Elutasítás" lehetőséget.

r,s

[1,n-1]

e={\mathcal {H}}(m)

w=s^{-1}{\bmod {n))

u_{1}=ew{\bmod {n))

u_{2}=rw{\bmod {n))

X=(x_{2},y_{2})=u_{1}G+u_{2}Q

X={\mathcal {O}}

v=x_{2}{\bmod {n))

v = r

A digitális aláírás ellenőrző algoritmus működésének igazolása

Az üzenet aláírását valóban Alice generálja, jelen esetben . A permutáció a következőket adja: $(r,s)$ $m$ $s=k^{-1}(e+dr){\bmod {n))$

k ≡ s − egy ( e + d r ) mod n ≡ ( s − egy e + s − egy d r ) mod n ≡ ( w e + w d r ) mod n ≡ ( u egy + u 2 d ) mod n {\displaystyle k\equiv s^{-1}(e+dr){\bmod {n}}\equiv (s^{-1}e+s^{-1}dr){\bmod {n}} \equiv (we+wdr){\bmod {n}}\equiv (u_{1}+u_{2}d){\bmod {n}}} $k\equiv s^{-1}(e+dr){\bmod {n}}\equiv (s^{-1}e+s^{-1}dr){\bmod {n}} \equiv (we+wdr){\bmod {n}}\equiv (u_{1}+u_{2}d){\bmod {n}}$

Így megkapjuk tehát a , amit bizonyítani kellett. ${\textstyle X=(x_{2},y_{2})=u_{1}G+u_{2}Q=(u_{1}+u_{2}d)G=kG}$ ${\textstyle v=r}$

ECDSA példa

Ebben a példában [O 1] csak az algoritmusok értelmes számítási lépéseit írjuk le, feltételezve, hogy minden ellenőrzés elvégezhető szöveges leírás nélkül.

1. A fő paraméterek generálására szolgáló algoritmus segítségével a következő értékeket kapjuk: , elliptikus görbe és bázispont sorrenddel . $p=114973$ $E:y^{2}=x^{3}-3x+69424$ $G=(11570.42257)$ $n=114467$

2. Hozzon létre egy kulcspárt a kulcspár-generáló algoritmusnak megfelelően : válassza a lehetőséget , majd a lehetőséget . $d=86109$ $Q=dG=(6345.28549)$

1. lépés Válassza a lehetőséget . 2. lépés Számítsa ki a pont koordinátáit .

d=86109\in [1,114466]

Q=dG=(6345.28549)

3. A digitális aláírás generáló algoritmus segítségével a szövegként megadott üzenetet a hash függvény értékével írjuk alá . ${\textstyle m=worldof}$ $e={\mathcal {H}}(m)=1789679805$

1. lépés Válassza a lehetőséget . 2. lépés Számítsa ki a pont koordinátáit . 3. lépés: Számítsa ki . 4. lépés: Számítsa ki .

k=84430\in [1.114466]

kG=(x_{1},y_{1})=(11705,10585)

{\textstyle r=x_{1}{\bmod {n}}=11705{\bmod {1}}14973=31167}

{\textstyle s=k^{-1}(e+dr){\bmod {n}}=84430^{-1}(1789679805+86109\cdot 31167){\bmod {1}}14973=82722}

4. Ellenőrizze az üzenet aláírásának hitelességét a digitális aláírás-ellenőrző algoritmus segítségével . $(r, s)$ $m$

1. lépés: Számolja ki . 2. lépés Számítsa ki és . 3. lépés Számítsa ki a pont koordinátáit . 4. lépés: Számítsa ki . 5. lépés: Ellenőrzés . Az aláírást elfogadjuk.

w=s^{-1}{\bmod {n}}=82722^{-1}{\bmod {1}}14973=83035

u_{1}=ew{\bmod {n}}=1789679805\cdot 83035{\bmod {1}}14973=71001

u_{2}=rw{\bmod {n}}=31167\cdot 83035{\bmod {1}}14973=81909

X=u_{1}G+u_{2}Q=(66931.53304)+(88970.41780)=(31167.31627)

v=x_{2}{\bmod {n}}=31167{\bmod {1}}14973=31167

v=r=31167

Biztonság

D. Brown (Daniel RL Brown) bebizonyította, hogy az ECDSA algoritmus nem biztonságosabb, mint a DSA . Megfogalmazta az ECDSA biztonsági megszorítását, amely a következő következtetéshez vezetett: "Ha egy elliptikus görbe csoportot a főcsoport modellezhet, és a hash függvénye kielégít egy bizonyos megalapozott sejtést, akkor az ECDSA ellenáll a megfelelő szöveges támadásnak , ha létező hamisítás. " [Y 2] .

A titkosítási algoritmus erőssége egy elliptikus görbe pontcsoportjában a diszkrét logaritmus problémán alapul . Ellentétben az egyszerű diszkrét logaritmus problémával és az egész számok faktorizációs problémájával , az elliptikus görbe pontcsoportján nincs szubexponenciális algoritmus a diszkrét logaritmus feladatra. Emiatt a "kulcsbitenkénti teljesítmény" lényegesen magasabb egy elliptikus görbéket használó algoritmusban [E 3] .

Ez azt jelenti, hogy lényegesen kisebb paraméterek használhatók az elliptikus görbe kriptográfiában, mint más nyilvános kulcsú rendszerekben, mint például az RSA és a DSA , de ezzel egyenértékű biztonsági szint mellett. Például a kulcsok bitmérete : A 160 bites kulcs az RSA és DSA 1024 bites modulusú kulcsaival egyenértékű, hasonló biztonsági szinten (ismert támadások ellen).

A kisebb paraméterméretek (különösen a kulcsok) előnyei közé tartozik az algoritmus végrehajtási sebessége, a hatékony energiafelhasználás, a sávszélesség és a memória. Különösen fontosak a korlátozott képességű eszközökön, például intelligens kártyákon [O 2] történő alkalmazásoknál .

Gyakorlati megvalósítás

A véges mezők feletti elliptikus görbék számos szoftveres megvalósítása létezik. A legtöbb ilyen implementáció egyetlen alkalmazásra összpontosul, mint például az ECDSA gyors implementációjának fejlesztése egy adott célterületre [O 3] .

Jegyzetek

Fő források

↑ 1 2 Liao HZ, Shen YY Az elliptikus görbén digitális aláírási algoritmus . " Tunghai tudomány " (2006). Letöltve: 2022. szeptember 28. Az eredetiből archiválva : 2022. szeptember 28.. (határozatlan)
↑ 1 2 3 Hankerson D., Menezes AJ, Vanstone S. Guide to elliptic curve cryptography . " Springer Science & Business Media" (2006). Letöltve: 2022. szeptember 28. Az eredetiből archiválva : 2022. március 18. (határozatlan)
↑ Lopez J., Dahab R. Az elliptikus görbe titkosításának áttekintése . Számítástechnikai Intézet. Campinas Állami Egyetem" (2000). Letöltve: 2022. szeptember 29. Az eredetiből archiválva : 2022. szeptember 29. (határozatlan)

További források

↑ Mayer H. ECDSA biztonság a bitcoinban és az ethereumban: kutatási felmérés . " CoinFaabrik " (2016. június 28.). Letöltve: 2022. szeptember 28. Az eredetiből archiválva : 2022. január 22. (határozatlan)
↑ D. Brown. Általános csoportok, ütközésállóság és ECDSA . " Kódok és kriptográfia " (2002. február 26.). Letöltve: 2008. november 27. Az eredetiből archiválva : 2012. február 27.. (határozatlan)
↑ Korzsev V. Digitális aláírás. Elliptikus görbék . " Open Systems " (2002. augusztus 8.). Letöltve: 2008. november 16. Az eredetiből archiválva : 2012. december 31.. (határozatlan)

Linkek

Neal Koblitz és Alfred Menezes (1995). – Újabb pillantás az általános csoportokra. Letöltve: 2008. november 27. Az eredetiből archiválva : 2012. február 27.. (határozatlan)

Nyilvános kulcsú kriptorendszerek

Algoritmusok

Egész számok faktorizálása	Benalo kriptorendszer Bluma – Goldwasser Cayley Purser Damgorda – Eureka GMR Goldwasser – Micali Nakasha – Stern paye Rabin RSA Okamoto – Uchiyama Schmidt-Szamoa
Diszkrét logaritmus	BLS Cramer – Shoup Diffie-Hellman protokoll DSA ECDH Görbe 25519 X448 ECDSA EdDSA Ed25519 Ed448 ECMQV Titkosított kulcscsere ElGamal séma aláírási séma MQV Schnorr-séma SPEKE SRP STS
Kriptográfia rácsokon	NTRUEncrypt NTRUSign Tanulás alapú kulcscsere hibákkal Aláírás alapú edzés hibákkal a ringben BOLDOGSÁG Új remény
Egyéb	AE CEILIDH EPOC Rejtett mező egyenletek IES Lamport aláírása McEliece Merkle-Hellman háti kriptorendszer Naccache–Stern háti kriptorendszer Három lépéses protokoll XTR

Elmélet

Szabványok

CRYPTREC
IEEE P1363
NESSIE
NSA Suite B
Posztkvantum kriptográfia

Témák

Elektronikus aláírás
OAEP
Ujjlenyomat
PKI
a bizalom hálója
Kulcsméret
Identitás alapú kriptográfia
Posztkvantum kriptográfia
OpenPGP kártya