什么是Schnorr

来源：密码学引论 / digital_signature/Schnorr/什么是Schnorr.md

Q:什么是Schnorr签名 Schnorr 签名是一种基于离散对数困难问题的数字签名方案。它由 Schnorr 提出，具有结构简单、签名长度较短、效率较高等特点。Schnorr 签名可以看作是许多现代签名方案的重要基础，例如一些椭圆曲线签名方案也采用了类似思想。

设 (G) 是一个阶为 (q) 的循环群，(g) 是生成元。签名者选择私钥：

\[ x \in \mathbb{Z}_q \]

对应公钥为：

\[ y = g^x \]

其中 (x) 是私钥，(y) 是公钥。

对消息 (m) 进行签名时，签名者随机选择一个临时随机数：

\[ k \in \mathbb{Z}_q \]

计算：

\[ r = g^k \]

然后计算挑战值：

\[ e = H(r,m) \]

其中 (H) 是哈希函数。接着计算：

\[ s = k - ex \pmod q \]

最终签名为：

\[ (e,s) \]

验证时，验证者利用公钥 (y)、消息 (m) 和签名 ((e,s))，计算：

\[ r' = g^s y^e \]

然后检查：

\[ e \stackrel{?}{=} H(r',m) \]

如果等式成立，则签名有效。

其正确性来自：

\[ g^s y^e = g^{k-ex}(g^x)^e = g^{k-ex+ex} = g^k = r \]

所以验证者能够重新得到签名时的 (r)，从而验证签名的合法性。

因此，Schnorr 签名是一种利用离散对数困难问题构造的数字签名算法，其核心思想是通过随机数、哈希挑战和私钥响应生成签名，并由公钥验证签名的正确性。