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 +more98. C3. A1d_prvku_a_grupy'>řá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}]. +more 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 QA. Pokud má pochybnosti ohledně zdroje, musí si ověřit tento klíč. +more * Ověří, že Q_{A} \ne 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 nQ_{A}=O.

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ý. +more * 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

Vytváření podpisu

Alice zvolí prvočíslo p=23, bod G[13;16], a=1, b=1, řád n=7. ** 4a^3+27b^2 \ne 0, jde tedy o eliptickou křivku. +more * 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

Bob ověřil klíč QA. * Nyní ověří, že r,s \isin [1;n-1], tedy že 1, 3 \isin [1;6]. +more * 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

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

Reference

Kategorie:Kryptografie s veřejným klíčem