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], ${\displaystyle Q_{A}=d_{A}G}$ (viz sčí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}\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)+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 ${\displaystyle 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 ${\displaystyle nQ_{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}\mod n}$.
• Spočítá u₁, u₂, kde ${\displaystyle u_{1}\equiv wh(m)\mod n}$; ${\displaystyle u_{2}\equiv rw\mod n}$.
• Následně spočítá souřadnice ${\displaystyle [x_{1},y_{1}]=u_{1}G+u_{2}Q_{A}\mod p}$.
• Podpis je platný, když ${\displaystyle r=x_{1}}$.

Příklad

Vytváření podpisu

• 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}\neq 0}$, jde tedy o eliptickou 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}\mod n\equiv 17\mod 7\equiv 3\mod 7}$; ${\displaystyle k\neq 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)+rd_{A})\mod n\equiv 4^{-1}(5+3\cdot 2)\mod 7\equiv 2(5+6)\mod 7\equiv 1\mod 7}$.
• Čísla ${\displaystyle r\equiv 3\mod 7}$, ${\displaystyle s\equiv 1\mod 7}$ tvoří podpis.

Ověřování podpisu

• 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}\mod n\equiv 1^{-1}\mod 7\equiv 1\mod 7}$.
• Spočítá u₁, u₂, kde ${\displaystyle u_{1}\equiv wh(m)\mod n\equiv 1\cdot 5\mod 7\equiv 5\mod 7}$; ${\displaystyle u_{2}\equiv rw\mod n\equiv 3\cdot 1\mod 7\equiv 3\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]\mod 23}$.
• Podpis je platný, když ${\displaystyle r\mod 7\equiv x_{1}\mod 7}$, ${\displaystyle 3\mod 7\equiv 17\mod 7}$, ${\displaystyle 3\mod 7\equiv 3\mod 7}$, podpis je platný.

Důkaz platnosti

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

Související články

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

Reference