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 dA, veřejného klíče QA, kde dA je náhodně vybrané celé kladné číslo z intervalu [1;n-1], Q A = d A G {\displaystyle Q_{A}=d_{A}G} (viz sčítání bodů na eliptické křivce).

  • Alice náhodně zvolí k, k ∈ [ 1 ; n − 1 ] {\displaystyle k\in [1;n-1]} .
  • Následně spočítá r ≡ x 1 mod n {\displaystyle r\equiv x_{1}\mod n} , kde k G = [ x 1 ; y 1 ] {\displaystyle kG=[x_{1};y_{1}]} . Pokud r = 0 {\displaystyle r=0} , musí Alice zvolit jiné k.
  • Zjistí hash zprávy h(m), spočítá s ≡ k − 1 ( h ( m ) + r d A ) mod n {\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 QA. Pokud má pochybnosti ohledně zdroje, musí si ověřit tento klíč.

  • Ověří, že Q A ≠ O {\displaystyle Q_{A}\neq O} , kde O je bod v nekonečnu (viz eliptická křivka).
  • Ověří, že bod QA leží na eliptické křivce.
  • Ověří, že existuje číslo n takové, že n Q A = O {\displaystyle nQ_{A}=O} .

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

  • Ověří, že r , s ∈ [ 1 ; n − 1 ] {\displaystyle r,s\in [1;n-1]} . Pokud nejsou, podpis je neplatný.
  • Bob zjistí hash zprávy h(m).
  • Spočítá w ≡ s − 1 mod n {\displaystyle w\equiv s^{-1}\mod n} .
  • Spočítá u1, u2, kde u 1 ≡ w h ( m ) mod n {\displaystyle u_{1}\equiv wh(m)\mod n} ; u 2 ≡ r w mod n {\displaystyle 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 {\displaystyle [x_{1},y_{1}]=u_{1}G+u_{2}Q_{A}\mod p} .
  • Podpis je platný, když r = x 1 {\displaystyle r=x_{1}} .

Příklad

Vytváření podpisu

  • Alice zvolí prvočíslo p = 23 {\displaystyle p=23} , bod G[13;16], a = 1 , b = 1 {\displaystyle a=1,b=1} , řád n = 7 {\displaystyle n=7} .
    • 4 a 3 + 27 b 2 ≠ 0 {\displaystyle 4a^{3}+27b^{2}\neq 0} , jde tedy o eliptickou křivku.
  • Zvolí d A = 2 {\displaystyle d_{A}=2} , QA[5;19], zvolí číslo k = 4 {\displaystyle k=4} .
  • Následně nalezne bod kG[17;3] ( k G = 4 G = 2 ( 2 G ) {\displaystyle kG=4G=2(2G)} , zdvojnásobí tedy bod G, nalezne pomyslný bod R, který zdvojnásobí a získá hledaný bod), spočítá r ≡ x 1 mod n ≡ 17 mod 7 ≡ 3 mod 7 {\displaystyle r\equiv x_{1}\mod n\equiv 17\mod 7\equiv 3\mod 7} ; k ≠ 0 {\displaystyle k\neq 0} .
  • Zjistí hash zprávy h(m), h ( m ) = 5 {\displaystyle h(m)=5} (hash byl náhodně zvolen pro tento příklad), spočítá s ≡ k − 1 ( h ( m ) + r d A ) mod n ≡ 4 − 1 ( 5 + 3 ⋅ 2 ) mod 7 ≡ 2 ( 5 + 6 ) mod 7 ≡ 1 mod 7 {\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 r ≡ 3 mod 7 {\displaystyle r\equiv 3\mod 7} , s ≡ 1 mod 7 {\displaystyle s\equiv 1\mod 7} tvoří podpis.

Ověřování podpisu

  • Bob ověřil klíč QA.
  • Nyní ověří, že r , s ∈ [ 1 ; n − 1 ] {\displaystyle r,s\in [1;n-1]} , tedy že 1 , 3 ∈ [ 1 ; 6 ] {\displaystyle 1,3\in [1;6]} .
  • Bob zjistí hash zprávy h(m), h ( m ) = 5 {\displaystyle h(m)=5} (viz Alice).
  • Spočítá w ≡ s − 1 mod n ≡ 1 − 1 mod 7 ≡ 1 mod 7 {\displaystyle w\equiv s^{-1}\mod n\equiv 1^{-1}\mod 7\equiv 1\mod 7} .
  • Spočítá u1, u2, kde u 1 ≡ w h ( m ) mod n ≡ 1 ⋅ 5 mod 7 ≡ 5 mod 7 {\displaystyle u_{1}\equiv wh(m)\mod n\equiv 1\cdot 5\mod 7\equiv 5\mod 7} ; u 2 ≡ r w mod n ≡ 3 ⋅ 1 mod 7 ≡ 3 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 [ 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 {\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ž r mod 7 ≡ x 1 mod 7 {\displaystyle r\mod 7\equiv x_{1}\mod 7} , 3 mod 7 ≡ 17 mod 7 {\displaystyle 3\mod 7\equiv 17\mod 7} , 3 mod 7 ≡ 3 mod 7 {\displaystyle 3\mod 7\equiv 3\mod 7} , podpis je platný.

Důkaz platnosti

  • s ≡ k − 1 ( h ( m ) + r d A ) mod n {\displaystyle s\equiv k^{-1}(h(m)+rd_{A})\mod n} , což lze upravit pomocí ekvivalentních úprav na h ( m ) ≡ k s − r d A mod n {\displaystyle h(m)\equiv ks-rd_{A}\mod n}
  • vynásobíme-li obě strany kongruence w, získáme w h ( m ) ≡ w k s − w r d A mod n {\displaystyle wh(m)\equiv wks-wrd_{A}\mod n}
  • u 1 ≡ w h ( m ) mod n {\displaystyle u_{1}\equiv wh(m)\mod n} , u 2 ≡ r w mod n {\displaystyle u_{2}\equiv rw\mod n} , po dosazení získáváme u 1 ≡ w k s − u 2 d A mod n {\displaystyle u_{1}\equiv wks-u_{2}d_{A}\mod n}
  • w ≡ s − 1 mod n {\displaystyle w\equiv s^{-1}\mod n} , z toho plyne, že w s ≡ 1 mod n {\displaystyle ws\equiv 1\mod n} , po dosazení získáváme u 1 ≡ k − u 2 d A mod n {\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ě) ( k G mod p ) mod n ≡ ( u 1 G + u 2 d A G mod p ) mod n {\displaystyle (kG\mod p)\mod n\equiv (u{1}G+u_{2}d_{A}G\mod p)\mod n} , k G mod n ≡ u 1 G + u 2 Q A mod n {\displaystyle kG\mod n\equiv u_{1}G+u_{2}Q_{A}\mod n}
  • r ≡ x 1 mod n {\displaystyle r\equiv x_{1}\mod n} , QED

Související články

Reference