ECDSA

Den aktuelle version af siden er endnu ikke blevet gennemgået af erfarne bidragydere og kan afvige væsentligt fra den version , der blev gennemgået den 27. april 2020; checks kræver 27 redigeringer .

ECDSA (Elliptic Curve Digital Signature Algorithm) er en offentlig nøglealgoritme , der bruges til at bygge og verificere en elektronisk digital signatur ved hjælp af elliptisk kurvekryptering .

Historie

Elliptiske kurver, som et matematisk koncept, er blevet undersøgt i lang tid, der er mange videnskabelige artikler om dette emne. Men på trods af al forskning var deres anvendelse på reelle problemer, især for kryptografi, ukendt indtil slutningen af det 20. århundrede. I 1985 foreslog Victor Miller og Neil Koblitz brugen af elliptiske kurver til kryptografi.

I 1991 blev DSA udviklet af National Institute of Standards and Technology (NIST) , bygget op omkring ideen om at bruge modulær aritmetik og det diskrete logaritmeproblem . Kort efter anmodede NIST om offentlige kommentarer til sit forslag til digitale signaturordninger [O 1] . Inspireret af denne idé foreslog Scott Vanstone i artiklen "Responses to NIST's proposal" en analog af den digitale signaturalgoritme ved hjælp af elliptisk kurvekryptografi (ECDSA).

I perioden fra 1998-2000. ECDSA er blevet vedtaget af forskellige organisationer som en standard ( ISO 14888-3, ANSI X9.62, IEEE 1363-2000, FIPS 186-2).

Ansøgning

ECDSA bruges i kryptovalutatransaktioner (såsom Bitcoin og Ethereum ) for at sikre, at midler kun kan bruges af deres retmæssige ejere [Y 1] .

Grundlæggende parametre for en elliptisk kurve

Hovedparametrene (eng. domæneparametre) for en elliptisk kurve over et begrænset felt er sættet af følgende størrelser: ${\tekststil D=(q,FR,a,b,G,n,h)}$ $\mathbb {F} _{q}$

Rækkefølgen af det endelige felt (f.eks. et simpelt endeligt felt ved , hvor og er et primtal ). $q$ $\mathbb {F} _{p}$ ${\textstyle q=p}$ ${\textstyle p>3}$
${\textstyle FR}$ (Feltrepræsentation) er en indikator, der bruges til at repræsentere de elementer, der hører til feltet . $\mathbb {F} _{q}$
To elementer i feltet, der angiver koefficienterne for ligningen for en elliptisk kurve over feltet (for eksempel ved ). ${\displaystyle a,b\in \mathbb {F} _{q))$ $E$ $\mathbb {F} _{q}$ $y^{2}=x^{3}+ax+b$ $q=p>3$
Et basispunkt, der har en prime orden . ${\textstyle G=(x_{G},y_{G})\in E(\mathbb {F} _{q})}$ $n$
Et heltal , der er en cofaktor af , hvor er rækkefølgen af kurven, der numerisk falder sammen med antallet af punkter i . ${\tekststil h}$ ${\textstyle h=\#E(\mathbb {F} _{q})/n}$ ${\tekststil \#E(\mathbb {F} _{q})}$ ${\textstyle E(\mathbb {F} _{q})}$

Parametrene skal vælges således, at den elliptiske kurve defineret over det endelige felt er modstandsdygtig over for alle kendte angreb, der gælder for ECDLP . Derudover kan der være andre restriktioner relateret til sikkerheds- eller implementeringshensyn. $\mathbb {F} _{q}$

Som regel er hovedparametrene fælles for en gruppe af enheder, men i nogle applikationer (implementeringer) kan de være specifikke for hver specifik bruger [O 2] .

ECDSA i henhold til ANSI X9.62

Til praktisk anvendelse pålægger ECDSA restriktioner på de felter, hvor elliptiske kurver er defineret. For nemheds skyld kan du overveje tilfældet med implementering af algoritmer, når er et simpelt endeligt felt, (for andre felter - tilsvarende), så har vores elliptiske ligning formen . $\mathbb {F} _{q}$ ${\textstyle y^{2}=x^{3}+ax+b}$

Algoritme til generering af grundlæggende parametre

For at undgå kendte angreb baseret på det diskrete logaritmeproblem i gruppen af punkter i en elliptisk kurve , er det nødvendigt, at antallet af punkter i den elliptiske kurve er deleligt med et tilstrækkeligt stort primtal . ANSI X9.62-standarden kræver . $E$ $n$ $n > 2^{160}$

Input : Feltrækkefølge , feltpræsentationsindikator for , - sikkerhedsniveau: og . Konklusion : De vigtigste parametre for den elliptiske kurve .

q

FR

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

L

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

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

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

Trin 1. Vælg tilfældigt verificerede elementer , der opfylder betingelsen . Trin 2. , rækkefølgen af kurven kan beregnes ved hjælp af SEA- algoritmen . Trin 3. Tjek det for et stort primtal . Hvis ikke, så gå til trin 1. Trin 4. Tjek, at . Hvis ikke, så gå til trin 1. Trin 5. Tjek, at . Hvis ikke, så gå til trin 1. Trin 6. Trin 7. Vælg et vilkårligt punkt og indstil . Gentag indtil , hvor er punktet ved uendelighed Trin 8. Vend tilbage

{\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)}

Tilfældige verifikationsalgoritmer garanterer, at en elliptisk kurve over et begrænset felt blev genereret helt tilfældigt [O 2] .

Algoritme til generering af et nøglepar

Lad os overveje udvekslingen af beskeder mellem Alice og Bob . Tidligere, ved at bruge algoritmen til at generere hovedparametrene, opnår Alice sine hovedparametre for den elliptiske kurve. Ved at bruge følgende rækkefølge af handlinger vil Alice selv generere en offentlig og privat nøgle.

Input : Grundlæggende parametre for den elliptiske kurve . Konklusion : Offentlig nøgle- , privat nøgle- .

{\tekststil D}

Q

d

Trin 1. Vælg et tilfældigt eller pseudo-tilfældigt heltal . Trin 2. Beregn koordinaterne for et punkt på en elliptisk kurve . Trin 3. Tilbage .

d\in [1,n-1]

Q=dG

(Q,d)

Offentlig nøgle bekræftelsesalgoritme

Formålet med at kontrollere en offentlig nøgle er at bekræfte, at en offentlig nøgle har visse aritmetiske egenskaber . Succesfuld eksekvering af denne algoritme viser, at den tilsvarende private nøgle matematisk eksisterer, men garanterer ikke, at nogen ikke har beregnet den givne private nøgle, eller at den påståede ejer faktisk besidder den.

Input : Grundlæggende parametre for en elliptisk kurve , offentlig nøgle - . Konklusion : En beslutning om at acceptere eller afvise gyldigheden af den offentlige nøgle .

{\tekststil D}

Q

Q

Trin 1. Tjek at . Trin 2. Tjek hvad der er de korrekt repræsenterede elementer i , dvs. heltal tilhørende . Trin 3. Tjek, hvad der opfylder den elliptiske kurveligning defineret af feltets elementer . Trin 4. Tjek at . Trin 5. Hvis en kontrol mislykkes, så returner "Afvis", ellers "Acceptér".

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

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

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

{\tekststil [1,q-1]}

{\textstyle Q}

{\tekststil a,b}

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

Digital Signature Generation Algoritme

Alice, som har hovedparametrene for kurven og den private nøgle , ønsker at underskrive beskeden , for dette skal hun generere en signatur . $D$ $d$ $m$ $(r,s)$

I det følgende betegner en kryptografisk hashfunktion, hvis outputværdi har en bitlængde på højst (hvis denne betingelse ikke er opfyldt, kan outputværdien afkortes). Det antages, at vi arbejder med output af funktionen, der allerede er konverteret til et heltal. ${\mathcal {H}}$ $n$ ${\mathcal {H}}$

Input : Elliptisk kurve grundlæggende parametre , privat nøgle , besked . Konklusion : Underskrift .

{\tekststil D}

d

m

(r,s)

Trin 1. Vælg et tilfældigt eller pseudo-tilfældigt heltal . Trin 2. Beregn koordinaterne for punktet Trin 3. Beregn . Hvis , så gå til trin 1. Trin 4. Beregn . Trin 5 Beregn . Hvis , så gå til trin 1. Trin 6. Vend tilbage .

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)

Digital signaturverifikationsalgoritme

For at bekræfte Alices signatur af beskeden modtager Bob en autentisk kopi af hendes grundlæggende kurveparametre og deres tilhørende offentlige nøgle . $(r, s)$ $m$ $D$ $Q$

Input : Elliptisk kurve grundlæggende parametre , offentlig nøgle , besked , signatur . Konklusion : Beslutning om at acceptere eller afvise underskriften.

{\tekststil D}

Q

m

(r,s)

Trin 1. Tjek, at der er heltal, der tilhører . Hvis en validering mislykkes, skal du returnere "Afvis". Trin 2 Beregn . Trin 3 Beregn . Trin 4 Beregn og . Trin 5. Beregn koordinaterne for punktet . Trin 6. Hvis , så returner "Afvis". Ellers beregn . Trin 7. Hvis , så returner "Accepter", ellers "Afvis"

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

Bevis på arbejdet med den digitale signaturverifikationsalgoritme

Lad signaturen for beskeden virkelig blive genereret af Alice, i dette tilfælde . Permutationen giver følgende: $(r,s)$ $m$ $s=k^{-1}(e+dr){\bmod {n))$

k ≡ s − en ( e + d r ) mod n ≡ ( s − en e + s − en d r ) mod n ≡ ( w e + w d r ) mod n ≡ ( u en + u 2 d ) mod n {\displaystyle k\equiv s^{-1}(e+dr){\bmod {n}}\equiv (s^{-1}e+s^{-1}dr){\bmod {n}} \equiv (vi+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 (vi+wdr){\bmod {n}}\equiv (u_{1}+u_{2}d){\bmod {n}}$

Vi opnår således , som skulle bevises. ${\textstyle X=(x_{2},y_{2})=u_{1}G+u_{2}Q=(u_{1}+u_{2}d)G=kG}$ ${\textstyle v=r}$

ECDSA-eksempel

I dette eksempel [O 1] vil vi kun beskrive meningsfulde beregningstrin i algoritmerne, idet det antages, at alle kontroller kan udføres uden en tekstbeskrivelse.

1. Ved at bruge algoritmen til at generere hovedparametrene får vi følgende værdier: , elliptisk kurve , og basispunkt med orden . $p=114973$ $E:y^{2}=x^{3}-3x+69424$ $G=(11570.42257)$ $n=114467$

2. Generer et par nøgler i overensstemmelse med nøglepargenereringsalgoritmen : vælg , derefter . $d=86109$ $Q=dG=(6345.28549)$

Trin 1. Vælg . Trin 2. Beregn koordinaterne for punktet .

d=86109\in [1,114466]

Q=dG=(6345.28549)

3. Ved at bruge den digitale signaturgenereringsalgoritme signerer vi meddelelsen angivet som tekst med hash-funktionsværdien . ${\textstyle m=worldof}$ $e={\mathcal {H}}(m)=1789679805$

Trin 1. Vælg . Trin 2. Beregn koordinaterne for punktet . Trin 3. Beregn . Trin 4. Beregn .

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. Kontroller ægtheden af signaturen for meddelelsen ved hjælp af den digitale signaturverifikationsalgoritme . $(r, s)$ $m$

Trin 1. Beregn . Trin 2. Beregn og . Trin 3. Beregn koordinaterne for punktet . Trin 4. Beregn . Trin 5. Kontrol . Vi accepterer underskrift.

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

Sikkerhed

D. Brown (Daniel RL Brown) beviste, at ECDSA-algoritmen ikke er mere sikker end DSA . Han formulerede en sikkerhedsbegrænsning på ECDSA, der førte til følgende konklusion: "Hvis en elliptisk kurvegruppe kan modelleres af hovedgruppen, og dens hashfunktion opfylder et vist veluddannet gæt, så er ECDSA modstandsdygtig over for et matchet klartekstangreb med eksisterende forfalskning " [Y 2] .

Styrken af krypteringsalgoritmen er baseret på det diskrete logaritmeproblem i gruppen af punkter i en elliptisk kurve . I modsætning til det simple diskrete logaritmeproblem og heltalsfaktoriseringsproblemet er der ingen subeksponentiel algoritme for det diskrete logaritmeproblem på punktgruppen af en elliptisk kurve. Af denne grund er "effekten pr. nøglebit" betydeligt højere i en algoritme, der bruger elliptiske kurver [E 3] .

Det betyder, at betydeligt mindre parametre kan bruges i elliptisk kurvekryptering end i andre offentlige nøglesystemer såsom RSA og DSA , men med et tilsvarende sikkerhedsniveau. For eksempel bitstørrelsen af nøgler : En 160-bit nøgle ville svare til nøgler med et 1024-bit modul i RSA og DSA på et sammenligneligt sikkerhedsniveau (mod kendte angreb).

Fordelene ved mindre parameterstørrelser (især nøgler) inkluderer algoritmeudførelseshastighed, effektiv brug af energi, båndbredde, hukommelse. De er især vigtige for applikationer på enheder med begrænsede muligheder, såsom smart cards [O 2] .

Praktisk implementering

Der er mange softwareimplementeringer af elliptiske kurver over begrænsede felter. De fleste af disse implementeringer er fokuseret på en enkelt applikation, såsom udvikling af en hurtig implementering af ECDSA for et specifikt målfelt [O 3] .

Noter

Hovedkilder

↑ 1 2 Liao HZ, Shen YY On the Elliptic Curve Digital Signature Algorithm . " Tunghai Science " (2006). Hentet 28. september 2022. Arkiveret fra originalen 28. september 2022. (ubestemt)
↑ 1 2 3 Hankerson D., Menezes AJ, Vanstone S. Guide to elliptic curve cryptography . " Springer Science & Business Media" (2006). Hentet 28. september 2022. Arkiveret fra originalen 18. marts 2022. (ubestemt)
↑ Lopez J., Dahab R. En oversigt over elliptisk kurvekryptografi . Institut for Computing. State University of Campinas" (2000). Hentet 29. september 2022. Arkiveret fra originalen 29. september 2022. (ubestemt)

Yderligere kilder

↑ Mayer H. ECDSA sikkerhed i bitcoin og ethereum: en forskningsundersøgelse . " CoinFaabrik " (28. juni 2016). Hentet 28. september 2022. Arkiveret fra originalen 22. januar 2022. (ubestemt)
↑ D. Brown. Generiske grupper, kollisionsmodstand og ECDSA . " Koder og kryptografi " (26. februar 2002). Hentet 27. november 2008. Arkiveret fra originalen 27. februar 2012. (ubestemt)
↑ Korzhev V. Digital signatur. Elliptiske kurver . " Åbne systemer " (8. august 2002). Hentet 16. november 2008. Arkiveret fra originalen 31. december 2012. (ubestemt)

Links

Neal Koblitz og Alfred Menezes (1995). — Endnu et kig på generiske grupper. Hentet 27. november 2008. Arkiveret fra originalen 27. februar 2012. (ubestemt)

Offentlig nøgle kryptosystemer

Algoritmer

Faktorisering af heltal	Benalo kryptosystem Bluma - Goldwasser Cayley Purser Damgorda - Eureka GMR Goldwasser - Micali Nakasha - Stern betalingsmodtager Rabin RSA Okamoto - Uchiyama Schmidt-Samoa
Diskret logaritme	BLS Cramer - Shoup Diffie-Hellman protokol DSA ECDH Kurve25519 X448 ECDSA EdDSA Ed25519 Ed448 ECMQV Krypteret nøgleudveksling Ordning af ElGamal underskriftsordning MQV Schnorr ordning SPEKE SRP STS
Kryptografi på gitter	NTRUEncrypt NTRUSign Læringsbaseret nøgleudveksling med fejl Signaturbaseret træning med fejl i ringen LYKKELIGHED Nyt håb
Andet	AE CEILIDH EPOC Skjulte feltligninger IES Lamports underskrift McEliece Merkle-Hellman rygsæk kryptosystem Naccache-Stern rygsæk kryptosystem Tre trins protokol XTR

Teori

Standarder

CRYPTREC
IEEE P1363
NESSIE
NSA Suite B
Post kvantekryptering

Emner

Elektronisk signatur
OAEP
Fingeraftryk
PKI
web af tillid
Nøglestørrelse
Identitetsbaseret kryptografi
Postkvantekryptografi
OpenPGP-kort