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],
(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
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
Vytváření podpisu
- 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
- 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
, což lze upravit pomocí ekvivalentních úprav na ![{\displaystyle h(m)\equiv ks-rd_{A}\mod n}](https://wikimedia.org/api/rest_v1/media/math/render/svg/d0c8c0866a1b6c18b3ea3d58cd4fb66e36671926)
- vynásobíme-li obě strany kongruence w, získáme
![{\displaystyle wh(m)\equiv wks-wrd_{A}\mod n}](https://wikimedia.org/api/rest_v1/media/math/render/svg/ff7c0d826264697307e4744aa511765ee5eb0a6a)
,
, po dosazení získáváme ![{\displaystyle u_{1}\equiv wks-u_{2}d_{A}\mod n}](https://wikimedia.org/api/rest_v1/media/math/render/svg/cf9011b2c90d9e1fb587fce526506045bf4c32b5)
, z toho plyne, že
, po dosazení získáváme ![{\displaystyle u_{1}\equiv k-u_{2}d_{A}\mod n}](https://wikimedia.org/api/rest_v1/media/math/render/svg/23ba6055f6581a39bbb4ad19ab566870733a9659)
- celou kongruenci vynásobíme bodem G, získáme (po drobné ekvivalentní úpravě)
, ![{\displaystyle kG\mod n\equiv u_{1}G+u_{2}Q_{A}\mod n}](https://wikimedia.org/api/rest_v1/media/math/render/svg/0e7864ef47bab0ee5ec0a7ed173b2769b27d0035)
, QED
Související články
Reference