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

Z Wikipedie, otevřené encyklopedie
Skočit na: Navigace, Hledání

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[editovat | editovat zdroj]

Vytváření podpisu[editovat | editovat zdroj]

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 (viz sčítání bodů na eliptické křivce).

  • Alice náhodně zvolí k, k \isin [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[editovat | editovat zdroj]

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

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

  • Ověří, že r,s \isin [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á u1, u2, 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[editovat | editovat zdroj]

Vytváření podpisu[editovat | editovat zdroj]

  • Alice zvolí prvočíslo p=23, bod G[13;16], a=1, b=1, řád n=7.
  • Zvolí d_{A}=2, QA[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 \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)+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[editovat | editovat zdroj]

  • Bob ověřil klíč QA.
  • Nyní ověří, že r,s \isin [1;n-1], tedy že  1, 3 \isin [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á u1, u2, 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[editovat | editovat zdroj]

  • 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[editovat | editovat zdroj]

Reference[editovat | editovat zdroj]