Elliptic Curve Digital Signature Algorithm

(Presmerované z ECDSA)

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

upraviť

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

upraviť
  • 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 = x1 mod n, kde x1 = kG, ak r = 0 proces sa opakuje
  • 4. vypočítame s = k−1(e + rd) mod n, ak s = 0 proces sa opakuje
  • 5. výstupný podpis S = (r, s)

Overovacia operácia

upraviť
  • 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−1 mod n
  • 4. vypočítame: u1 = ew mod n a u2 = rw mod n
  • 5. vypočítame: R = (xR, yR) = u1 G + u2 Q , [R ≠ Ό] inak sa procedúra opakuje
  • 6. vypočítame: v = xR (mod n)
  • 7. porovná či r = v, ak áno operácia je validná

Pozri aj

upraviť

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

Referencie

upraviť
  • [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