digitální podpis pomocí eliptických křivek

ECDSA

2 min čtení
V 20 jazycích

ECDSA (anglicky Elliptic Curve Digital Signature Algorithm) 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}\mod n$ , 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)+rd_{A})\mod n$ .
Čí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}\neq 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 $nQ_{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}\mod n$ .
Spočítá u₁, u₂, kde $u_{1}\equiv wh(m)\mod n$ ; $u_{2}\equiv rw\mod n$ .
Následně spočítá souřadnice $[x_{1},y_{1}]=u_{1}G+u_{2}Q_{A}\mod p$ .
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}\neq 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}\mod n\equiv 17\mod 7\equiv 3\mod 7$ ; $k\neq 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)+rd_{A})\mod n\equiv 4^{-1}(5+3\cdot 2)\mod 7\equiv 2(5+6)\mod 7\equiv 1\mod 7$ .
Čísla $r\equiv 3\mod 7$ , $s\equiv 1\mod 7$ 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}\mod n\equiv 1^{-1}\mod 7\equiv 1\mod 7$ .
Spočítá u₁, u₂, kde $u_{1}\equiv wh(m)\mod n\equiv 1\cdot 5\mod 7\equiv 5\mod 7$ ; $u_{2}\equiv rw\mod n\equiv 3\cdot 1\mod 7\equiv 3\mod 7$ .
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]\mod 23$ .
Podpis je platný, když $r\mod 7\equiv x_{1}\mod 7$ , $3\mod 7\equiv 17\mod 7$ , $3\mod 7\equiv 3\mod 7$ , podpis je platný.

Důkaz platnosti

$s\equiv k^{-1}(h(m)+rd_{A})\mod n$ , což lze upravit pomocí ekvivalentních úprav na $h(m)\equiv ks-rd_{A}\mod n$
vynásobíme-li obě strany kongruence w, získáme $wh(m)\equiv wks-wrd_{A}\mod n$
$u_{1}\equiv wh(m)\mod n$ , $u_{2}\equiv rw\mod n$ , po dosazení získáváme $u_{1}\equiv wks-u_{2}d_{A}\mod n$
$w\equiv s^{-1}\mod n$ , z toho plyne, že $ws\equiv 1\mod n$ , po dosazení získáváme $u_{1}\equiv k-u_{2}d_{A}\mod n$
celou kongruenci vynásobíme bodem G, získáme (po drobné ekvivalentní úpravě) $(kG\mod p)\mod n\equiv (u{1}G+u_{2}d_{A}G\mod p)\mod n$ , $kG\mod n\equiv u_{1}G+u_{2}Q_{A}\mod n$
$r\equiv x_{1}\mod n$ , QED