Elliptic Curve Digital Signature Algorithm

**Elliptic Curve Digital Signature Algorithm (ECDSA)** je variant podpisovej schémy DSA (Digital Signature Algorithm) s dodatkom 
na základe ECC. Je navrhnutý tak, aby bol existenčne nefalšovatelný.

## Nastavenie systému
Zadefinujeme si subjekty:
* **U** – signer
* **V** – verifier
* **M** – message
* **S** - signature

V skutočnosti platí, že hneď po podpísaní správy *M* každý subjekt *V* s kópiou *U* verejného kľúča môže overiť daný podpis *S*.

Predpokladajme, že *Alice (U)* chce poslať podpísanú správu *Bobovi (V)*.

Subjekty *U* a *V* musia vykonať nasledujúci postup pre prípravu využitia *ECDSA*:
* jednotka *U* by mala určiť, ktoré z podporovaných hašovacich funkcií je potrebné použiť pre generovanie podpisu.
* jednotka *U* by mala stanoviť domenové parametre eliptických kriviek **T=(p, a, b, G, n, h)** or **(m, f(x), a, b,G, n, h)** pre požadovanú úroveň zabezpečenia.
* subjekt *V (Bob)* by mal získať autentickým spôsobom hašovaciu funkciu a doménový parameter *T*, aby *V* mohol určiť, či doménové parametre sú platné pre krivku pomocou jednej z vybraných metód.
* jednotka *U* by mala vytvoriť kľúčový pár eliptických kriviek **(d, Q)** v spojení s *T* pre použitie v podpisovej schéme. Kľúčový pár tvorí verejný kľúč *Q* a privátny kľúč *d*.
* subjekt *V* by mal získať autentickým spôsobom *Alicin* verejný kľúč **Q**.

## Podpisová operácia
* **Input:** Vstupná správa **M**, ktorá je správa určená pre podpis a Alicin privátny kľúč **d**.
* **Output:** Podpis **S=(r, s)**, zložený z dvoch celočíselných sekvencií **r** a **s**.

Na vytvorenie podpisu *S* z *M* použije *Alica (U)* *Signture Generation Algorithm*: 
* 1. použijeme hašovaciu funkciu, ktorú sme zvolili na výpočet celočíselnej hash hodnoty: **e=HASH(M)**
* 2. vyberieme náhodné číslo **k** z intervalu **[1, n – 1]**.
* 3. vypočítame  **r = x<sub>1</sub> mod n**, kde **x<sub>1</sub> = kG**, ak *r = 0* proces sa opakuje
* 4. vypočítame  **s = k<sup>−1</sup>(e + rd) mod n**, ak *s = 0* proces sa opakuje
* 5. výstupný podpis **S = (r, s)**

## Overovacia operácia
* **Input:** pre overenie podpisu potrebuje *Bob* poznať  svoju kópiu *Alicinho* verejného kľúča **Q**, pôvodnú správu **M** a podpis **S**.
* **Output:** Údaj o tom, či podpis *S* bol overený, teda či správa *M* je **true**  alebo **false**.

Ak *Bob* nemá dôveru v kľúč **Q**, musí si ho potvrdiť:
* Overí si, či **Q** nie je rovná **Ό** , inak sú jeho súradnice platné.
* Overí si, či **Q** leží na danej krivke.
* 1.Overí si, či **nQ = Ό**, kde Ό je náš bod v nekonečno na krivke.

Následne pre overenie podpisu *S* sa použije *Signature Verification Algorithm*:
* 1. overuje, či **r** a **s** sú celé čísla v intervale **[1, n - 1]**. Ak nie, podpis je neplatný a overovanie je zastavené
* 2. použijeme hašovaciu funkciu na výpočet celočíselnej hash hodnoty **e = HASH(M)**
* 3. vypočítame: **w = s<sup>−1</sup> mod n**
* 4. vypočítame:  **u<sub>1</sub> = ew mod n**  a  **u<sub>2</sub> = rw mod n**
* 5. vypočítame:  **R = (x<sub>R</sub>, y<sub>R</sub>) = u<sub>1</sub> G + u<sub>2</sub> Q** , *[R ≠ Ό]* inak sa procedúra opakuje
* 6. vypočítame:  **v = x<sub>R</sub> (mod n)**
* 7. porovná či **r = v**, ak áno operácia je validná

## Pozri aj
Podrobnejší opis a význam jednotlivých parametrov a ich generovanie pozri v článku Kryptografia na báze eliptických kriviek. 

## Referencie

* [1] Brown, D.: Elliptic Curve Cryptography, 2009.
* [2] Don, J., Menezes, A.: The Elliptic Curve Digital Signature Algorithm, Canada, 2000.
* [3] Locke, G., Gallagher, P., Digital Signature Standard, FIPS PUB 186-3, NIST,USA, 2009

Kategória:Kryptografia