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 ${\displaystyle G}$ řádu ${\displaystyle q}$ a její generátor ${\displaystyle g}$.
• Uživatelé určí kryptografickou hašovací funkci ${\displaystyle H:\{0,1\}^{*}\rightarrow \mathbb {Z} _{q}}$.

Generování klíčů

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

Podpis

Pro danou zprávu ${\displaystyle M}$:

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

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

Ověření podpisu

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

Pokud ${\displaystyle 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 ${\displaystyle k}$, jinak může útočník zjistit hodnotu soukromého klíče. V případě Schnorrova podpisu mu k tomu poslouží rovnost

${\displaystyle s'-s=(k'-k)-x(e'-e)}$,

pomocí které lze při ${\displaystyle k'=k}$ a ${\displaystyle e\neq e'}$ hodnotu ${\displaystyle x}$ získat velice snadno. Kromě toho existují podobně fungující útoky i pro případy, kdy ${\displaystyle k}$ sice nejsou stejná, ovšem nejsou ani zcela náhodná a je nasbírán dostatečný počet ${\displaystyle 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.