ECDSA

ECDSA (Šablona:Vjazyce2) je algoritmus asymetrické kryptografie pro elektronický podpis, který využívá kryptografii nad eliptickými křivkami. Je variantou algoritmu DSA. Z hlediska digitálních certifikátů protokolu HTTPS (resp. TLS), který používají webové prohlížeče pro zabezpečený přístup k webovým stránkám, je nástupcem metody RSA. 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).

Digitální podepisování s využitím eliptických křivek

Vytváření podpisu

Pokud chce Alice poslat zprávu m Bobovi, musí se nejprve domluvit na parametrech (p,a,b,G,n,h), kde p je prvočíslo, kterým definujeme těleso, konstanty a, b z rovnice eliptické 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é pro kryptografii 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], $Q_A=d_{A}G$ (viz sčítání bodů na eliptické křivce).

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

Ověřování podpisu

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

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

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

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

Příklad

Vytváření podpisu

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

Ověřování podpisu

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

Důkaz platnosti

• $s\equiv k^{-1}(h(m)+r{d}_A)modn$, což lze upravit pomocí ekvivalentních úprav na $h(m)\equiv ks-r{d}_{A}modn$
• vynásobíme-li obě strany kongruence w, získáme $wh(m)\equiv wks-wr{d}_{A}modn$
• $u_1\equiv wh(m)modn$, $u_2\equiv rwmodn$, po dosazení získáváme $u_1\equiv wks-u_2{d}_{A}modn$
• $w\equiv s^{-1}modn$, z toho plyne, že $ws\equiv 1modn$, po dosazení získáváme $u_1\equiv k-u_2{d}_{A}modn$
• celou kongruenci vynásobíme bodem G, získáme (po drobné ekvivalentní úpravě) $(kGmodp)modn\equiv (u1G+u_2{d}_{A}Gmodp)modn$, $kGmodn\equiv u_{1}G+u_2{Q}_{A}modn$
• $r\equiv x_{1}modn$, QED

Odkazy

Související články

• EdDSA