Protokol digitálního podpisu s využitím eliptických křivek

Protokol digitálního podpisu s využitím eliptických křivek (The Elliptic Curve Digital Signature Algorithm, ECDSA) je varianta DSA protokolu, která využívá eliptických křivek, používá se k digitálním podpisům.

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 eliptických křivek 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ří 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ří 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

Související články

• Eliptická křivka
• Digital Signature Algorithm
• Kryptografie nad eliptickými křivkami