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

  • Alice náhodně zvolí k, .
  • Následně spočítá , kde . Pokud , musí Alice zvolit jiné k.
  • Zjistí hash zprávy h(m), spočítá .
  • Čí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íč.

  • Ověří, že , 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 .

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

  • Ověří, že . Pokud nejsou, podpis je neplatný.
  • Bob zjistí hash zprávy h(m).
  • Spočítá .
  • Spočítá u1, u2, kde ; .
  • Následně spočítá souřadnice .
  • Podpis je platný, když .

Příklad[editovat | editovat zdroj]

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

  • Alice zvolí prvočíslo , bod G[13;16], , řád .
    • , jde tedy o eliptickou křivku.
  • Zvolí , QA[5;19], zvolí číslo .
  • Následně nalezne bod kG[17;3] (, zdvojnásobí tedy bod G, nalezne pomyslný bod R, který zdvojnásobí a získá hledaný bod), spočítá ; .
  • Zjistí hash zprávy h(m), (hash byl náhodně zvolen pro tento příklad), spočítá .
  • Čísla , tvoří podpis.

Ověřování podpisu[editovat | editovat zdroj]

  • Bob ověřil klíč QA.
  • Nyní ověří, že , tedy že .
  • Bob zjistí hash zprávy h(m), (viz Alice).
  • Spočítá .
  • Spočítá u1, u2, kde ; .
  • Následně spočítá souřadnice .
  • Podpis je platný, když , , , podpis je platný.

Důkaz platnosti[editovat | editovat zdroj]

  • , což lze upravit pomocí ekvivalentních úprav na
  • vynásobíme-li obě strany kongruence w, získáme
  • , , po dosazení získáváme
  • , z toho plyne, že , po dosazení získáváme
  • celou kongruenci vynásobíme bodem G, získáme (po drobné ekvivalentní úpravě) ,
  • , QED

Související články[editovat | editovat zdroj]

Reference[editovat | editovat zdroj]