一、基本知识

1.1 概述

Schnorr签名算法最初是由德国密码学家ClausSchnorr于2008年提出的，在密码学中，它是一种数字签名方案，以其简单高效著称，其安全性基于某些离散对数问题的难处理性。

1.2 椭圆曲线上的计算

密码学中，常用以下形式的椭圆曲线：$E:y^2=x^3+ax+b(modp)$ 同时要求$4a^3+27b^2\ne 0$。其中p为一个大素数，a、b、x和y均在有限域$GF(p)$中，即从{0,1,⋅⋅⋅,p−1}\{0,1,···,p-1\}{0,1,⋅⋅⋅,p−1}中取值。该曲线常用$E_p(a,b)$表示。若该曲线上只有有限个离散点，设为N个，则椭圆曲线的阶为N。N越大，椭圆曲线安全性越高。椭圆曲线的阶可通过schoof算法计算求得。
椭圆曲线$E:y^2=x^3-x+1$图形如下：

加法规则

椭圆曲线$E_p(a,b)$在如下定义的加法规则构成Abel群（交换群）。

• $O+O=O$
• $\forall P=(x,y)\in E_p(a,b)$，有$P+O=O+P=P$
• $\forall P=(x,y)\in E_p(a,b)$，有$P+(-P)=O$，$P$的逆为$-P=(x,-y)$
• $\forall P=(x_1,y_1),Q=(x_2,y_2)\in E_p(a,b)$，则 $P+Q=R=(x_3,y_3)\in E_p(a,b)$，其中$x_3={\lambda }^2-x_1-x_2,y_3=\lambda (x_1-x_3)-y_1$。

• 相同点相加计算R点
  • 不同点相加计算R点
    

乘法规则

• $\forall k\in Z,\forall P\in E_p(a,b)$，有$kP=P+\cdot \cdot \cdot +P(k个P相加)$；
• $\forall s,t\in Z,\forall P\in E_p(a,b)$，有$(s+t)P=sP+tP,s(tP)=(st)P$

除了无限远的点$O$外，椭圆曲线$E$任何可以生成所有点的点都可视为$E$的生成元，但并非$E$上所有点都可为生成元。
如何选取生成元

• 首先分解椭圆曲线阶$n=r\times p$，p需要足够大。
• 令$k=n/p$，随机选取 $X\in E_p(a,b)$，计算$G=k\cdot X$
• 若$G\ne O$，则$G$可为生成元否则重新选择$X$再次计算。

二、算法细节

2.1 公私钥产生算法（$KeyGen$）：

• 选择一条椭圆曲线$E_p(a,b)$ 和基点$G$；
• 选择私钥$d_A$（$d_A<n$，$n$为该$G$的阶），利用基点$G$计算公钥$Q_A=d_A\cdot G$；

2.2 签名生成算法（$Sign$）

• 选择一个随机整数$k(k<n)$;
• 计算点$R=k\cdot G=(x_1,y_1)$；
• 计算$\sigma =k+hash(m||R)\cdot d_A(modn)$；
• 得到签名$s=(R,\sigma )$;

2.3 签名验证算法（Verify）：

• 验证等式：$\sigma \cdot G\equiv hash(m||R)\cdot Q_A+R$；
• 如果等式成立输出1，否则输出0。

Schnorr签名除了上面一种形式外，还有另外一种形式。

2.4 签名生成算法（$Sign$）

• 选择一个随机整数$k(k<n)$;
• 计算点$R=k\cdot G=(x_1,y_1)$；
• 计算$\alpha =hash(m||R)$
• 计算$\sigma =k+hash(m||R)\cdot d_A(modn)$；
• 得到签名$s=(\alpha ,\sigma )$;

2.5 签名验证算法（Verify）：

• 计算$R^{{}^{\prime }}=\sigma \cdot G-\alpha \cdot Q_A$
• 验证等式：$hash(m||R^{{}^{\prime }})\equiv \alpha$；
• 如果等式成立输出1，否则输出0。