1. 概述

1.1 基本概念

数字签名(Digital Signature)，也称电子签名，是指附加在某一电子文档中的一组特定的符号或代码。它利用密码技术对该电子文档进行关信息提取并进行认证形成，用于标识签发者的身份以及签发者对电子文档的认可，并能被接收者用来验证该电子文档在传输过程中是否被篡改或伪造。

为了满足在网络环境中身份认证、数据完整性和不可否认性等需求，数字签名应具有以下特点：

• 可信性信：签名使文件的接收者相信是签名者在文件上签名的。
• 不可重用性：签名不可重用，即同一消息在不同时刻的签名是有区别的。
• 不可改变性：在文件签名后，文件不能改变。
• 不可伪造性：签名能够证明是签名者而不是其他人在文件上签名，任何人都不能伪造签名。
• 不可否认性：在签名者否认自己的签名时，签名接收者可以请求可信第三方进行仲裁。

1.2 签名原理

1.2.1 形式化定义

数字签名的形式化定义如下:

(1)系统初始化

系统初始化产生签名方案的基本参数$(M,s,K,Sign,Ver)$。

其中，$M$为消息空间，$S$为签名空间，$K$为密钥空间，包含私钥和公钥，$Sign$为签名算法集合，$Ver$为签名验证算法集合。

(2)签名产生过程

对$k=(k_1,k_2)\in K$，其中$k_1$是公钥，$k_2$是私钥，签名算法$sig{n}_{k_2}:M\to S,sig{n}_{k_2}\in Sign$。

对于任意消息$m\in M$，消息签名$s=sig{n}_{k_2}(m)$, $s\in S$，形成签名消息组$(m,s)$发送给签名验证者。

(3)签名验证过程

对于$k_1\in K$，有相应的签名验证算法： v e r k 1 : M × S → { T r u e , F a l s e } ， v e r k 1 ∈ V e r ver_{k_1}:M \times S \to \{True,False\}，ver_{k_1}\in Ver verk1​​:M×S→{True,False}，verk1​​∈Ver。

签名验证者收到$(m,s)$后,计算$ve{r}_{k_1}(m,s)$,若$ve{r}_{k_1}(m,s)=True$,则签名有效，否签名无效：

$$ve{r}_{k_1}(m,s)=\{\begin{array}{ll}True,& ifs=sig{n}_{k_2}(m),\\ False& ifs\ne sig{n}_{k_2}(m)\end{array}$$

对于每一个$k\in K$，签名函数$sig{n}_{k_2}$和签名验证函数$ve{r}_{k_1}$是容易计算的。

一般情下$sig{n}_{k_2}$可公开也可不公开，并且在签名算法中要求保证私钥的安全性；而验证函数$ve{r}_{k_1}$是公开的，同时还要求对任意的消息$m$，从集合$S$中计算$s$使得$ve{r}_{k_1}(m,s)=True$是非常困难的，即攻击者对消息$m$产生有效签名$s$是不可能的。

1.2.2 签名过程

• 发送方A将消息用Hash算法产生一个消息摘要(Message Digest)
• 发送方A用自己的私钥对消息摘要进行加密，这个加密后的息摘要就是数字签名
• 发送方A将消息与签名发给接收方B
• 接收方B接收到消息及其名后，用发送方A的公钥解密这个签名，获得由发送方A生成的消息摘要
• 接收方B用发送方A所用Hash算法重新生成所获得消息的摘要，对比这两个摘要。若相同说明签名是发送方A针对这个消息的有效签名，否则签名无效。

2 基于RSA的签名方案

2.1 实现过程

（1）初始化：生成公私密钥对

选取两个大素数$p、q$(不可泄露)，计算$n=pq$及$n$的欧拉函数$\phi (n)=(p-1)(q-1)$

随机选取整数$e(1<e<\phi (n))$作为公钥，满足$gcd(e,\phi (n))=1$，即$e$与$\phi (n)$互素

使用Euclid扩展算法计算私钥：$d\equiv e^{-1}\mathrm{mod}\phi (n)$，即$e$的逆元

（2）签名过程

设待签名的消息为$m\in Z_n$，签名者利用安全的Hash函数产生消息摘要$h=H(m)$，然后计算签名：$s\equiv h^d\mathrm{mod}n$。

（3）验证过程

签名接收者收到消息$m$和签名$s$，计算消息摘要$h=H(m)$，然后，检验等式$h\mathrm{mod}n\equiv s^e\mathrm{mod}n$。若成立，则签名有效；否则签名无效。

2.2 安全性分析

RSA签名方案还存在签名可重用的问题，即对同一消息在不同时刻签名是相的。这个问题可以通过在签名中引人随机数来解决，在后面提到的数字签名方案中对此解决方法均有所体现。

3 基于离散对数的签名方案

基于离散对数问题的签名方案是数字签名方案中较常用的一类，包括ElGamal签名方案、Schnorr签名方案、DSA签名方案等。

3.1 ElGamal签名体制

T.ElGamal于1985年提出了既可以用于加密又可以用于数字签名的ElGamal密码体制。ElGamal数字签名方案的修正形式已被美国NIST作为数字签名标准(DSS,Digital Signature Standard)。ElGamal数字签名方案是一种非确定性的签名方案，即对给定的一个消息，由于选择的随机数不同而有不同的数字签名，并且验证算法能够将它们中的任何一个作为有效的签名而接受。

3.1.1 实现过程

（1）初始化：生成公私密钥对

随机选择一个大素数$p$，且要求$p-1$有大素数因子，$g\in {\mathbf{Z}}_p^{\ast }$是一个本原元（$Z_p$是一个有$p$个元素的有限域，$Z_p^{\ast }$是$Z_p$中的非零元构成的乘法群）

选择随机数$x{\in }_R{Z}_{p-1}^{\ast }$（$\ast$表示除去零元，$R$表示随机选取），计算$y\equiv g^x\mathrm{mod}p$

公钥：$(p,g,y)$

私钥：$x$

（2）签名过程

设待签名的消息为$m$，签名者利用安全的Hash函数产生消息摘要$h=H(m)$，然后选择随机数$k{\in }_R{Z}_p^{\ast }$，计算：

$$\{\begin{array}{l}r\equiv g^k\mathrm{mod}p\\ s\equiv (h-xr)k^{-1}\mathrm{mod}(p-1)\end{array}$$

对消息$m$的签名为$(r,s)$

（3）验证过程

签名接收者收到消息$m$和签名$(r,s)$，计算消息摘要$h=H(m)$，然后，检验等式$y^r{r}^s\equiv g^h\mathrm{mod}p$。若成立，则签名有效；否则签名无效。

3.1.2 安全性分析

随机数$k$的选取和保管对私钥$x$的保密性至关重要。如果$k$值泄露，则容易计算私钥$x$。

此外，随机数$k$不能重复使用，多次签名时选取的多个$k$之间应无关联，否则容易计算出私钥$x$。

随机数$k$的使用也保证了签名方案的不可重用性，不同时刻选取的随机数不同，即使对同一消息进行签名，也会产生不同的结果，避免了RSA签名中出现的签名重用问题。

3.2 Schnorr签名体制

C.Schnorr于1989年提出了Schnorr签名体制，该方案具有签名速度较快、签名长度较短等特点。

3.2.1 实现过程

（1）初始化：生成公私密钥对

随机选择一个大素数$p、q$，$q$是$p-1$的大素数因子

选择生成元$g\in {\mathbf{Z}}_p^{\ast }$，且$g^q\equiv 1\mathrm{mod}p,g\ne 1$

选择随机数$1<x<q$，计算$y\equiv g^x\mathrm{mod}p$

公钥：$(y,g,p,q)$

私钥：$x$

（2）签名过程

设待签名的消息为$m$，签名者选择随机数$1\le k\le q-1$，计算：

$$\{\begin{array}{l}r\equiv g^k\mathrm{mod}p\\ h=H(m,r)\\ s\equiv (xh+k)\mathrm{mod}q\end{array}$$

对消息$m$的签名为$(h,s)$，其中$H$为Hash函数

（3）验证过程

签名接收者收到消息$m$和签名$(e,s)$，计算$r_1\equiv g^s{y}^{-e}\mathrm{mod}p$

然后，检验等式$h=H(m,r_1)$。若成立，则签名有效；否则签名无效。

3.2.2 安全性分析

ElGamal数字签名方案中$g$为$Z_p^{\ast }$的生成元，而在Schnorr数字签名方案中通过引入素数$q$，选择$g$为$Z_p^{\ast }$的$q$阶子群的生成元。

从穷尽搜索签名者私钥的角度而言，ElGamal签名的安全性较高，因为它的生成元的阶为$p-1$，大于Schnorr签名生成元的阶$q$。除此之外，Schnorr数字签名方案的安全性与ElGamal数字签名方案相似。

3.3 DSA签名体制

1994年12月美国国家标准和技术研究所(NIST,National Institute of Standard and Technology)正式颁布了数字签名标准(DSS,Digital Signature Standard),该标准在EIGamal和Schnorr数字签名方案的基础上设计的。

由于DSS较好的兼容性和适用性，得到了广泛应用，数字签名标准DSS中的算法常称为DSA(Digital Signature Algorithm)。

(1)初始化：生成公私密钥对

随机选择大素数$p$(长度在$512$~$1024$bit)、$q$($160$bit)，$q$是$p-1$的大素数因子($p-1$能被$q$整除)。

选择$g\equiv h^{(p-1)/q}\mathrm{mod}p$，其中整数$h$满足$1<h<p-1$,且$g>1$。

选随机数$1<x<q$，计算$y\equiv g^x\mathrm{mod}p$

公钥：$(p,q,g,y)$

私钥：$x$

(2)签名过程

设待签名的消息为$m$，签名者选择随机数$k$，计算：

$$\{\begin{array}{l}r\equiv g^k\mathrm{mod}p\\ s\equiv [H(m)+xr]k^{-1}\mathrm{mod}q\end{array}$$

其中，$H$为SHA1算法。

(3)验证过程

签名接收者在收到消息$m$和签名$(r,s)$后，计算:
$$\{\begin{array}{l}w\equiv s^{-1}\mathrm{mod}q\\ u_1\equiv H(m)w\mathrm{mod}q\\ u_2\equiv rw\mathrm{mod}q\\ v\equiv (g^{u_1}{y}^{u_2}\mathrm{mod}p)\mathrm{mod}q\end{array}$$然后，检验等式$v=r$。若成立，则签名有效；否则签名无效。

3.4 离散对数签名体制

3.4.1 三种签名体制的对比

如前所述，ElGamal签名方案的提出是3种方案中最早的，也是后两种方案的基础。Schnorr签名方案可以看作ElGamal签名方案的一种变型，它缩短了签名长度。而DSA 签名方案是EGamal签名方案的另一种变型，同时也吸收了Schnorr方案的一些设计思想。

由于采用的签名算法各不相同，三种方案的签名验证等式和过程也不尽相同。根据计算量和签名长度，量对比和分析这3种方案的效率如下。其中，由于模加、模减、求逆运算所用时间远远低于求幂、乘积、Hash求值等运算所需时间，可忽略不计。

签名体制	签名	验证	签名长度
ElGamal	$T_e+T_h+2T_m$	$3T_e+T_h+T_m$	$|p|+|p-1|$
Schnorr	$T_e+T_h+T_m$	$2T_e+T_h+T_m$	$|q|+|2H(m)|$
DSA	$T_e+T_h+2T_m$	$2T_e+T_h+3T_m$	$2|q|$

其中，$T_e$：幂运算的计算量；$T_h$：散列计算的计算量；$T_m$：乘积运算的计算量。

可以看出，Schnorr方案的签名过程计算量相对较少，速度较快，尤其有些计算与消息无关，可预先完成，这也能够减少签名的时间。Schnorr方案的验证过程计算量也相对较少，生成的签名值长度也较短(取决于$|q|+|2H(m)|$)。因此，Schnorr比较适合在智能卡等环境中应用。

另外两种方案中的个别计算也可以预先进行，而RSA方案是不可预先计算的。

3.4.2 离散对数签名体制的一般形式

ElGamal、Schnorr、DSA三种签名体制都可归结为基于有限域的离散对数签名体制的特例，离散对数签名体制的一般形式总结如下:

(1)初始化

随机选择大素数$p$、$q$，$q$是$p-1$的大素数因子($p-1$能被$q$整除)

选择生成元$g\in {\mathbf{Z}}_p^{\ast }$，且$g^q\equiv 1\mathrm{mod}p,g\ne 1$

选随机数$1<x<q$，计算$y\equiv g^x\mathrm{mod}p$

公钥：$(p,q,g,y)$

私钥：$x$

(2)签名过程

设待签名的消息为$m$，签名者计算$h=H(m)$，$H$为安全的 Hash 函数

选择随机数$k$，满足$1<k<q$，计算$r\equiv g^k\mathrm{mod}p$

从方程$ak\equiv b+cx(\mathrm{mod}q)$中解出$s$。

对消息$m$的签名为$(r,s)$

方程的系数$a、b、c$有许多种不同的选择方法，可取表中某一行三个值的任意排列，$r^{\prime }\equiv r\mathrm{mod}q$。

(3)验证过程

签名接收者收到消息$m$和签名$(r,s)$后，验证$r^a\equiv g^b{y}^c\mathrm{mod}$，若成立，则签名有效；否则签名无效。

如针对上表第一行的$a,b,c$（忽略正负）的可能签名和验证等式如下：

签名等式	验证等式
$r^{\prime }k\equiv (s+mx)\mathrm{mod}q$	$r^{r^{\prime }}\equiv g^s{y}^m\mathrm{mod}p$
$r^{\prime }k\equiv (m+sx)\mathrm{mod}q$	$r^{r^{\prime }}\equiv g^m{y}^s\mathrm{mod}p$
$sk\equiv (r^{\prime }+mx)\mathrm{mod}q$	$r^s\equiv g^{r^{\prime }}{y}^m\mathrm{mod}p$
$sk\equiv (m+r^{\prime }x)\mathrm{mod}q$	$r^s\equiv g^m{y}^{r^{\prime }}\mathrm{mod}p$
$mk\equiv (s+r^{\prime }x)\mathrm{mod}q$	$r^m\equiv g^s{y}^{r^{\prime }}\mathrm{mod}p$
$mk\equiv (r^{\prime }+sx)\mathrm{mod}q$	$r^m\equiv g^{r^{\prime }}{y}^s\mathrm{mod}p$

所列6个不同的签名方案，加上负号总共是$24$个，使用列出的$a、b、c$的其他可能值则总数是$120$个。

此外，还可以定义$r$产生更多类似DSA的方案：$r\equiv (g^k\mathrm{mod}p)\mathrm{mod}q$，使用相同的签名等式。

并定义验证等式如下：$$\{\begin{array}{l}{u}_1\equiv a^{-1}b\mathrm{mod}q\\ u_2\equiv a^{-1}c\mathrm{mod}q\\ r\equiv (g^{u_1}{y}^{u_2}\mathrm{mod}p)\mathrm{mod}q\end{array}$$类似这样的处理可产生多达$13000$种变型，所有的变型具有相同的安全性，可从中选择一个容易计算的有效方案。

4. 基于椭圆曲线的签名方案

DSA(Elliptic Curve Distal Signature Algorithm)是基于椭圆曲线的公钥密码体制在数字签名中的一个实现方案，即在椭圆曲线有限域上实现DSA算法，其安全性依赖于基于椭圆曲线的有限群上的离散对数难题。

与基于RSA的数字签名和基于有限域离散对数的数字签名相比，在相同的安全强度条件下，ECDSA方案签名长度短、存储空间小、计算速度快，特别适用于计算能力和存储空间有限、带宽受限、要求高速实现的场合(如智能卡中应用)。

5. 特殊数字签名

在数字签名的实际应用当中，一些特殊的场合往往有特殊的需求。例如，为保护信息拥有者的隐私，产生了盲签名;为了实现签名权的安全传递,产生代理签名；为了实现多人对同一个消息的签名,产生了多重签名等。

5.1 代理签名

代理签名是指原始签名者把他的签名权授权给代理者，代理者代表原始签名者行使他的签名权。当验证者验证代理签名时，验证者既能验证这个签名的有效性，也能确信这个签名是原始签名者认可的签名。

(1)代理签名分类

代理签名按照原始签名者给代理签名者的授权形式可分为

• 完全委托的代理签名
• 部分授权的代理签名（非保护代理者的代理签名、保护代理者的代理签名）
• 带授权书的代理签名

完全委托的代理签名指原始签名者将他的私钥(或含私钥的物理设备)秘密交给代理签名者，代理签名者可使用这个钥签署各种消息。代理签名者生成的代理签名与原始签名者产生的签名是一样的。

部分授权的代理签名指原始签名者利用他的私钥计算出一个新的代理私钥，并通过安全通道将其交给代理签名者，代理签名者可用这个代理私钥签署消息并生成代理签名。所产生的代理签名与原始签名者利用自己的私钥生成的签名是不同的，验证者能分辨出原始签名者的签名和代理者的签名。

带授权书的代理签名指由原始签名者产生授书给代理签名者，此授权书是利用原始签名者的私钥签署产生的，除了包含某代理签名者可代理行使签名权力外，还包含一些特殊的信息，如代理期限、可签署消息的类型等。代理签名者得到授权书后，再利用自己的私钥生成代理私钥并利用这个代理私钥签署所代签的消息，并将此授权书包含在签名中，而验证者在验证代理签名时首先检查其授权书，判断代理授权是否有效。如果通过检查，则进一步验证代理签名本身的有效性。如果验证通过，为有效的代理签名，否则代理签名无效。

(2)代理签名方案

1997年，由S.Kim.S.Park和D.Won提出了一种带授权书的代理签名方案，简称KPW方案。其主要思想是代理签名者利用自己私钥和由原始签名者签名的授权书产生代理私钥来生成代理签名，其中授权书$m_w$是指包括原始签名者标识、代理签名者标识、代理权限的有效期、代理签名信息的范围等信息的文件。

除KPW代理签名方案之外，基于离散对数的代理签名方案还有1996年M.Mambo、K.Usuda 和 E.Okamoto 提出的MUO代理签名方案、1997年Petersen 和 Horster提出的PH代理签名方案等。将基于离散对数的代理签名思想移植到椭圆曲线密码体制中，又能够演变出多种基于椭圆曲线的代理签名方案。

5.2 盲签名

盲签名是D.Chaum于1982年首次提出的一种具有特殊性质的数字签名，这种签名要求签名者能够在不知道被签名文件内容的情况下对消息进行签名。
即使签名者在以后看到了被签名的消息及其签名,签名者也不能判断出这个签名是他何时为谁生成的。直观上讲,这种签名的生成过程就像签名者闭着眼睛对消息签名一样,所以形象地称为“盲”数字签名。

由于盲签名解决了人们关注的匿名性问题，广泛应用于电子货币、电子投票、电子拍卖等应用中。

(1)盲签名分类

根据“盲”程度不同，盲签名方案通常分为强盲签名、弱盲签名、部分盲签名。

设$R(m)$是将消息$m$盲化后得到的盲消息，$Sign(R(m))$是对盲消息$R(m)$的签名，$Sign(m)$是去盲后得到的真实消息$m$的签名。

强盲签名指签名者无法建立$Sign(R(m))$到$Sign(m)$的联系的签名，也称为完全盲签名。

弱盲签名指签名者仅知道$Sign(R(m))$而不知道$Sign(m)$，但一但公开$Sign(m)$，签名者就可以建立两者间的联系，即签名者能把盲签名 $Sign(R(m))$的行为与消息$m$的内容关联起来。

部分盲签名的特殊性在于除了被签名的消息$m$外还包含由消息拥有者和签名者共同产生的消息$m_1$(包括消息$m$的范围、有效期等)，在部分盲签名过程中，消息$m_1$一直是公开的，即盲化后签名为$Sign(R(m),m_1)$，最终消息拥有者获得$Sign(m,m_1)$。

(2)盲签名实现步骤

盲签名方案中，消息的拥有者即需要盲签名服务的实体A称为用户，而提供盲签名服务的实体B称为签名者。当用户A需要签名者B对消息进行签名时，按下列操作步骤来实现:

• 用户A对待签名的消息进行盲化处理，使得消息的具体内容对于签名者B而言是乱码，亦称盲消息;
• 用户A将盲消息发送给签名者B
• 签名者B对所收到的盲消息进行数字签名
• 签名者B将盲消息及其签名一起交给用户A
• 用户收到签名做去盲处理，即得到签名者B对原消息的签名并能够验证盲签名

5.3 多重数字签名

在数字签名应用中，有时需要多个用户对同一文件进行签名和认证。能够实现多个用户对同一文件进行签名的数字签名方案称为多重数字签名(Digital Multi-signature)方案。

根据不同的签名过程，多重数字签名方案可分:

• 有序多重数字签名(Se quential Multi-signature)方案
• 广播多重数字签名(Broadcasting Multi-signa ture)方案

多重数字签名(Digital Multi-signature)方案包括消息发送者(Issuer)、消息签名者(Signers)和签名验证者(Verifier)。在广播多重签名方案中还包括签名收集者(Collector)。

有序多重数字签名方案中，消息发送者规定消息签名顺序，然后将消息发送到第一个签名者，除了第一个签名者外，每一位签名者收到签名消息后首先验证上一签名的有效性，如果签名有效，将签名消息发送到下一个签名者继续签名;如果签名无效，拒绝对消息签名，终止整个签名过程。当签名验证者收到签名消息后，验证签名的有效性。典型方案为ElGamal有序多重数字签名方案

广播多重数字签名方案中，消息发送者同时将消息发送给每一位消息签名者进行名，签名者将消息签名后消息发送到签名收集者，由收集者对签名消息进行整理并发送签名验证者，签名验证者验证多重签名的有效性。典型方案为Harn广播多重数字签名方案

5.4 群签名

1991年,Chaum和Heyst首次提出群签名(Group Signature)(组签名)方案。群签名方案允许组中合法用户以用户组的名义签名，具有签名者匿名，只有权威者才能辨认签名者身份等多个特点。一般来说，群签名的参与者由群成员(签名者)、**群管理员(GC，Group Center)和签名接受者(签名验证者)**组成。

群在实际生活中有广泛的应用，如某公司董事会决定对某个职员进行处罚，并委托某个董事进行。该董事代表董事会对处罚相关事宜进行签名，需要使用群签名。这样，受罚者只知道处罚是董事会集体做出的决定，不会通过签名联系到具体办理的董事。若处罚出现争议，那么，董事会的董事长作为群管理员能够揭示签名董事的身份。

5.5 不可否认签名

普通数字签名可以复制且任何人都可验证其有效性，这对于公开性之类文件是可以的，但对一些文件如个人或公司信件、特别是有价值文件的签名，如果也可随意复制和验证，就会造成损失，这就需要不可否认签名。

不可否认签名本质的是在无签名者合作条件下不可能验证签名的有效性，从而可以防止他所签文件的复制或散布。这一性质使签名者可以控制产品的散发，在电子出版系统和知识产权保护中有所应用。

不可否认的签名由三个部分组成:签名算法、验证协议和不可否认算法。

由于这种签名需要在签名者合作下才能验证,因此这会给签名者一种“否认”机会，即在不利签名者时签名者拒绝合作以否认他曾签署消息，不可否认算法就是防止签名者的“否认”。签名者也可利用不可否认算法向法庭或公众证明一个签名确实不是来自他的，如果签名者拒绝参与或者不配合执行签名验证协议，就表明这个签名就是由他签署的。

5.6 其他数字签名

为满足不同需求和应用，还有其他多种数据签名方案，如门限数字签名(Threshold Digital Signature)、失败——停止签名（Fail-Stop Signature）、一次性签名、条件签名、前向安全签名、变色龙签名（Chameleon Signature）、同时生效签名（Concurrent Signature）。