ECDSA (anglickyElliptic Curve Digital Signature Algorithm) jealgoritmusasymetrické kryptografie proelektronický podpis, který využívákryptografii nad eliptickými křivkami. Je variantou algoritmuDSA. Z hlediskadigitálních certifikátů protokoluHTTPS (resp.TLS), který používajíwebové prohlížeče pro zabezpečený přístup kwebovým stránkám, je nástupcem metodyRSA. Na rozdíl od RSA je úspornější a rychlejší (méně výpočetně náročná a stačí jí i kratšíklíče).^[1][2]

Pokud chce Alice poslat zprávu m Bobovi, musí se nejprve domluvit na parametrech (p,a,b,G,n,h), kde p jeprvočíslo, kterým definujemetěleso, konstanty a, b z rovniceeliptické křivky, bod G na eliptické křivce, jehořád n a kofaktor h, který udává podíl počtu prvkůgrupy bodů na eliptické křivce ařádu bodu G. Alice také musí mít své klíče vhodné prokryptografii nad eliptickými křivkami skládající se ze soukromého klíče d_A, veřejného klíče Q_A, kde d_A je náhodně vybrané celé kladné číslo z intervalu [1;n-1],${\displaystyle Q_A=d_{A}G}$ (vizsčítání bodů na eliptické křivce).

• Alice náhodně zvolí k,${\displaystyle k\in [1;n-1]}$.
• Následně spočítá${\displaystyle r\equiv x_1\mathrm{mod}n}$, kde${\displaystyle kG=[x_1;y_1]}$. Pokud${\displaystyle r=0}$, musí Alice zvolit jiné k.
• Zjistíhash zprávy h(m), spočítá${\displaystyle s\equiv k^{-1}(h(m)+r{d}_A)\mathrm{mod}n}$.
• Čísla r, s tvoříelektronický podpis.

Bob musí zjistitveřejný klíč Alice Q_A. Pokud má pochybnosti ohledně zdroje, musí si ověřit tento klíč.

• Ověří, že${\displaystyle Q_A\ne O}$, kde O je bod vnekonečnu (vizeliptická křivka).
• Ověří, že bod Q_A leží naeliptické křivce.
• Ověří, že existuje číslo n takové, že${\displaystyle n{Q}_A=O}$.

Pokud vše platí, může Bob učinit následující kroky:

• Ověří, že${\displaystyle r,s\in [1;n-1]}$. Pokud nejsou, podpis je neplatný.
• Bob zjistíhash zprávy h(m).
• Spočítá${\displaystyle w\equiv s^{-1}\mathrm{mod}n}$.
• Spočítá u₁, u₂, kde${\displaystyle u_1\equiv wh(m)\mathrm{mod}n}$;${\displaystyle u_2\equiv rw\mathrm{mod}n}$.
• Následně spočítá souřadnice${\displaystyle [x_1,y_1]=u_{1}G+u_2{Q}_A\mathrm{mod}p}$.
• Podpis je platný, když${\displaystyle r=x_1}$.

• Alice zvolí prvočíslo${\displaystyle p=23}$, bod G[13;16],${\displaystyle a=1,b=1}$, řád${\displaystyle n=7}$.
  • ${\displaystyle 4a^3+27b^2\ne 0}$, jde tedy oeliptickou křivku.
• Zvolí${\displaystyle d_A=2}$, Q_A[5;19], zvolí číslo${\displaystyle k=4}$.
• Následně nalezne bod kG[17;3] (${\displaystyle kG=4G=2(2G)}$,zdvojnásobí tedy bod G, nalezne pomyslný bod R, kterýzdvojnásobí a získá hledaný bod), spočítá${\displaystyle r\equiv x_1\mathrm{mod}n\equiv 17\mathrm{mod}7\equiv 3\mathrm{mod}7}$;${\displaystyle k\ne 0}$.
• Zjistíhash zprávy h(m),${\displaystyle h(m)=5}$ (hash byl náhodně zvolen pro tento příklad), spočítá${\displaystyle s\equiv k^{-1}(h(m)+r{d}_A)\mathrm{mod}n\equiv 4^{-1}(5+3\cdot 2)\mathrm{mod}7\equiv 2(5+6)\mathrm{mod}7\equiv 1\mathrm{mod}7}$.
• Čísla${\displaystyle r\equiv 3\mathrm{mod}7}$,${\displaystyle s\equiv 1\mathrm{mod}7}$ tvoříelektronický podpis.

• Bob ověřil klíč Q_A.
• Nyní ověří, že${\displaystyle r,s\in [1;n-1]}$, tedy že${\displaystyle 1,3\in [1;6]}$.
• Bob zjistíhash zprávy h(m),${\displaystyle h(m)=5}$ (viz Alice).
• Spočítá${\displaystyle w\equiv s^{-1}\mathrm{mod}n\equiv 1^{-1}\mathrm{mod}7\equiv 1\mathrm{mod}7}$.
• Spočítá u₁, u₂, kde${\displaystyle u_1\equiv wh(m)\mathrm{mod}n\equiv 1\cdot 5\mathrm{mod}7\equiv 5\mathrm{mod}7}$;${\displaystyle u_2\equiv rw\mathrm{mod}n\equiv 3\cdot 1\mathrm{mod}7\equiv 3\mathrm{mod}7}$.
• Následně spočítá souřadnice${\displaystyle [x_1,y_1]=u_{1}G+u_2{Q}_A=5[13;16]+3[5;19]=[5;4]+[13;7]=[17;3]\mathrm{mod}23}$.
• Podpis je platný, když${\displaystyle r\mathrm{mod}7\equiv x_1\mathrm{mod}7}$,${\displaystyle 3\mathrm{mod}7\equiv 17\mathrm{mod}7}$,${\displaystyle 3\mathrm{mod}7\equiv 3\mathrm{mod}7}$, podpis je platný.

• ${\displaystyle s\equiv k^{-1}(h(m)+r{d}_A)\mathrm{mod}n}$, což lze upravit pomocí ekvivalentních úprav na${\displaystyle h(m)\equiv ks-r{d}_A\mathrm{mod}n}$
• vynásobíme-li obě stranykongruence w, získáme${\displaystyle wh(m)\equiv wks-wr{d}_A\mathrm{mod}n}$
• ${\displaystyle u_1\equiv wh(m)\mathrm{mod}n}$,${\displaystyle u_2\equiv rw\mathrm{mod}n}$, po dosazení získáváme${\displaystyle u_1\equiv wks-u_2{d}_A\mathrm{mod}n}$
• ${\displaystyle w\equiv s^{-1}\mathrm{mod}n}$, z toho plyne, že${\displaystyle ws\equiv 1\mathrm{mod}n}$, po dosazení získáváme${\displaystyle u_1\equiv k-u_2{d}_A\mathrm{mod}n}$
• celoukongruenci vynásobíme bodem G, získáme (po drobné ekvivalentní úpravě)${\displaystyle (kG\mathrm{mod}p)\mathrm{mod}n\equiv (u1G+u_2{d}_{A}G\mathrm{mod}p)\mathrm{mod}n}$,${\displaystyle kG\mathrm{mod}n\equiv u_{1}G+u_2{Q}_A\mathrm{mod}n}$
• ${\displaystyle r\equiv x_1\mathrm{mod}n}$, QED

• EdDSA

• Kryptografie s veřejným klíčem
• Kryptografie nad eliptickými křivkami

• Monitoring:Autoritní kontrola s 0 identifikátory