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{\}}^{*}\to {\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^{\prime }-s=(k^{\prime }-k)-x(e^{\prime }-e)$,

pomocí které lze při $k^{\prime }=k$ a $e\ne e^{\prime }$ 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á.