Schnorrův podpis

Schnorrův podpis je v kryptografii označení schématu digitálního podpisu navrženého v letech 1989–1991 německým matematikem Clausem Schnorrem. Podobně jako algoritmus DSA ze stejné doby je toto schéma založeno na obtížnosti hledání diskrétního logaritmu v obecných grupách.

Schéma

Výběr parametrů

• Uživatelé určí grupu $G$ řádu $q$ a její generátor $g$.
• Uživatelé určí kryptografickou hašovací funkci $H:\{0,1\}^{*}\rightarrow \mathbb {Z} _{q}$.

Generování klíčů

• Uživatel si náhodně zvolí svůj nenulový soukromý klíč $x\in \mathbb {Z} _{q}$.
• Veřejným klíčem uživatele je pak hodnota $y=g^{x}$.

Podpis

Pro danou zprávu $M$:

• je náhodně zvoleno nenulové $k\in \mathbb {Z} _{q}$
• je spočítáno $r=g^{k}$
• je spočítáno $e=H(r\parallel M)$, kde $\parallel$ značí sřetězení, a $r$ a $M$ jsou brány jako bitové řetězce
• je spočítáno $s=k-xe$

Podpisem je pak pár $(s,e)$, kde $s,e\in \mathbb {Z} _{q}$.

Ověření podpisu

• Je spočítáno $r_{v}=g^{s}y^{e}$
• Je spočítáno $e_{v}=H(r_{v}\parallel M)$

Pokud $e_{v}=e$, pak je podpis správný.

Bezpečnost

Podobně jako u principiálně příbuzných schémat DSA, ECDSA a ElGamal je důležité nepoužívat opakovaně stejnou hodnotu $k$, jinak může útočník zjistit hodnotu soukromého klíče. V případě Schnorrova podpisu mu k tomu poslouží rovnost

$s'-s=(k'-k)-x(e'-e)$,

pomocí které lze při $k'=k$ a $e\neq e'$ hodnotu $x$ získat velice snadno. Kromě toho existují podobně fungující útoky i pro případy, kdy $k$ sice nejsou stejná, ovšem nejsou ani zcela náhodná a je nasbírán dostatečný počet $k$, která jsou určitým způsobem podobná.

Reference

V tomto článku byl použit překlad textu z článku Schnorr signature na anglické Wikipedii.