消息认证可以保护通信双方不受第三方攻击，但不能防止通信双方之间的攻击，例如

  • A、B间共享MAC密钥K，那么B可以产生任意消息并用K计算MAC，并声称该消息来自A
  • A、B都可以否认自己曾发送过某消息，因为对方也可用密钥K伪造消息

因此在收发双方不能相互信任的情况下，就需要使用数字签名，数字签名必须具有以下特征

  • 能验证签名者的身份
  • 能检验被签消息内容的完整性
  • 签名应能由第三方验证

ElGamal数字签名

ElGamal算法首先选择大素数$q$及其原根$\alpha$

用户A生成随机整数$1<X_A<q-1$，并计算$Y_A=\alpha^{X_A}\mod q$
则A的私钥为$X_A$，公钥为${q,\alpha, Y_A}$

若A要对消息M进行签名，则步骤如下

  1. 计算消息M的Hash值$m=H(M)$，满足$0\leq m\leq q-1$
  2. 选择随机整数$1\leq K\leq q-1$满足$gcd(K,q-1)=1$
  3. 计算$R=\alpha^K \mod q$
  4. 计算$S=K^{-1}(m-X_AR)\mod(q-1)$，其中$K^{-1}$为$K$模$q-1$的逆
  5. 获得数字签名$(R,S)$

若用户B要对签名进行验证，则步骤如下

  1. 计算$V_1=\alpha^m \mod q$
  2. 计算$V_2=(Y_A)^RR^S\mod q$
  3. 若$V_1=V_2$，则签名合法

下面简单证明该验证过程的正确性，假设$V_1=V2$，则有

对两边同时取离散对数得

等式显然成立

下面讨论一个问题：发送方两次签名采用相同的K是否安全？答案是不安全

若攻击者截获了两次发送的消息$m_1,m_2$和对应签名$(R_1,S_1),(R_2,S_2)$
由于两次签名的$K$相同，因此$R_1=R_2=\alpha^K\mod q$
由于$m_1,m_2,S_1,S_2$均已知，攻击者可计算出$\frac{S_1}{S_2}=\frac{K^{-1}(m_1-X_AR)}{K^{-1}(m_2-X_AR)}=\frac{m_1-X_AR}{m_2-X_AR}$，从而直接得到私钥$X_A$

Schnorr数字签名

与ElGamal相比，Schnorr签名的主要计算量和待签消息无关，因此可以进行预计算

Schnorr首先通过如下步骤产生公/私钥

  1. 选择大素数$p,q$，满足$q$是$p-1$的素因子（一般$p$约为1024位，$q$约为$160位$）
  2. 选择整数$\alpha\in Z_p^*$使得$\alpha^q\equiv1\mod p$
  3. 选择随机整数$s$满足$0<s<q$，作为用户私钥
  4. 计算$v=\alpha^{-s}\mod p$作为用户公钥

其中参数$p,q,\alpha$均是公开的

产生签名的步骤如下

  1. 选择随机整数$r$满足$0<r<q$，并计算$x=\alpha^r \mod p$，该步骤可以预计算
  2. 将$x$附加在消息后计算Hash值$e=H(M|x)$
  3. 计算$y=(r+se)\mod q$
  4. 获得签名$(e,y)$

验证签名的步骤如下

  1. 计算$x’=\alpha^yv^e\mod p$
  2. 验证是否有$e=H(M|x’)$

其正确性不难验证：$x’\equiv \alpha^yv^e \equiv \alpha^y\alpha^{-se} \equiv \alpha^r \equiv x (\mod p)$

数字签名标准

数字签名标准DSS指NIST于1994年正式批准生效的联邦信息处理标准FIPS PUB 186，其数字签名算法为DSA，该算法只能提供数字签名，不能用于加密或密钥交换

DSA在ElGamal和Schnorr的基础上设计而成，其步骤如下

  1. 选择大素数$p,q$，满足$q$是$p-1$的素因子
  2. 选择整数$h$，满足$11$，并计算$g=h(p-1)/q\mod p$
  3. 选择随机整数$x$满足$0<x<q$，作为用户私钥
  4. 计算$y=g^x\mod p$作为用户公钥

签名过程如下

  1. 选择随机整数$k$满足$1\leq k\leq q-1$
  2. 计算$r=(g^k\mod p)\mod q$和$s=k^{-1}(H(M)+xr)\mod q$，签名为$(r,s)$

验证过程如下

  1. 计算$w=s^{-1}\mod q$
  2. 计算$u_1=H(M)w \mod q$和$u_2=rw\mod q$
  3. 计算$v=(g^{u1}y^{u2}\mod p)\mod q$并验证$v=r$

椭圆曲线数字签名

相关基础可参考博客椭圆曲线密码体制，此处椭圆曲线数字签名算法（ECDSA）使用了域$Z_p$

ECDSA有如下全局参数

  • 素数$q$
  • $Z_q$上的整数$a,b$，为椭圆曲线系数
  • 基点$G$和$G$的阶$n$

用户随机选择整数$d\in[1,n-1]$作为私钥，计算$Q=dG$作为公钥

消息签名过程如下

  1. 选择随机整数$k$满足$1\leq k\leq n-1$
  2. 计算$P=(x,y)=kG$和$r=x\mod n$，若$r=0$则重新选择$k$
  3. 计算消息的Hash值$e=H(m)$
  4. 计算$s=k^{-1}(e+dr)\mod n$，若$s=O则重新选择$k$$
  5. 获得签名$(r,s)$

消息验证过程如下

  1. 计算$w=s^{-1}\mod n$
  2. 计算$u_1=H(M)w \mod q$和$u_2=rw\mod q$
  3. 计算$X=(x,y)=u_1G+u_2Q$
  4. 若$X=O$则拒绝签名，否则计算$v=x\mod n$，若$v=r$，则接受签名