密码学备忘录-数字签名

数字签名的作用是证明数字信息或文件在被签署时没有被有意或无意地修改。

数字签名通过生成信息或文件的唯一哈希值并使用发件人的私钥对其进行加密来实现。

1. 诉求

  • 真实性
  • 完整性
  • 不可抵赖性

2. 消息签名的两种方法

  • 对消息整体签名

  • 对消息摘要签名

  • 先签名后加密

3. 对称密码签名vs 公钥密码体制签名 vs 专门的数字签名算法

对称

  • Alice可以假称密钥丢失否认签名，Bob可以冒充Alice签名
  • 不适用于多人系统
    公钥
  • 计算量大，速度慢
  • 不验证签名就无法获得消息明文，不适用于特殊场合

3.1. 直接数字签名 Direct Digital Signature

  • 不涉及第三方
  • 假设接收者有发送者公钥
  • 可以假称私钥丢失
  • RSA可实现
  • ElGamal数字签名方案
    • 并非Elgamal加密逆过程
    • the difficulty of a certain problem in G related to computing discrete logarithms.
stepscalc
Key generationN bit prime p
Hash H, with result length L
generator生成元g,随机数x
公钥β,私钥x		β=$g^x$ mod p
Key distribution签名者需要透过可信任的管道发布公钥y，并且安全地保护x不被其他人知道-
Signing1.随机数k={1,p-2},必须保密,不可重用 2.签名为( r , s ) 组合,当r或者s为0时重选k$r=g^k\bmod{p}$
$s=(H(m)-xr)k^{-1} \bmod{(p-1)}$
Verifying验证 ( r , s )是消息m的有效签名$g^{H(m)}\equiv β^r · r^s \bmod{p}$
  • Schnorr signature
    • security is based on the intractability of certain discrete logarithm problems
    • 安全性是基于某些离散对数问题的不可控性
    • 注意运用到了哈希

3.2. Digital Signature Standard(DSS)

  • 用SHA
  • 公钥
  • DSS is the standard, DSA is the algorithm
    • DSA只能作为签名，不能作为加密，也不能进行密钥交换，但要比RSA快

3.2.1. Digital Signature Algorithm(DSA)

  • DSA（Digital Signature Algorithm）是Schnorr和ElGamal签名算法的变种，被美国NIST作为DSS(DigitalSignature Standard)
stepscalc
Key generation1. 预先拥有公钥参数（p,q,g） 6. 用户选择private，并计算public2. 160bit prime q 3. large prime p, p={$2^{L-1},2^{L}$}, L={512,1024} 4. choose h, h={1,p} 5. find g=$h^{(p-1)/q}\bmod{p}$ 7.pri=random x, x<q 8. pub:$y=g^x\bmod{p}$
Key distribution签名者需要透过可信任的管道发布公钥y，并且安全地保护x不被其他人知道-
Signing1.随机数k={1,q-1,必须保密,不可重用 2.签名为( r , s ) 组合,当r或者s为0时重选k$r=(g^k\bmod{p})\bmod{q}$
$s=(H(m)+xr)K^{-1}\bmod{q}$
Verifying验证 ( r , s )是消息m的有效签名,此时v=r

3.3. Key Wrapping

  • 密钥封装结构是一类对称加密算

    • first cipher block affected by only first data block
    • last data block affects only last cipher block

  • 在增强混淆扩散的同时，还提供了签名效果

  • 64 bit authentication block, A

  • 64 bit data blocks, P

3.4. RSA–PSS Digital Signatures

  • 原生RSA选择密文攻击，因为C(M1)xC(M2)=C(M1M2)
  • 在对消息M生成RSA-PSS签名的第一阶段处理过程是由M生成固定长度的消息摘要，成为消息编码（EM）
  • 形成签名
    • $s=EM^d\bmod{n}$
    • (d,e)为私钥

3.5. Elliptic Curve Digital Signatures Algorithm（ECDSA）

ECDSA是ECC与DSA的结合，整个签名过程与DSA类似，所不一样的是签名中采取的算法为ECC，最后签名出来的值也是分为r,s

签名

  • 在 {1,…,n−1} 范围内选取一个随机数 k（n 是子群的阶）
  • 计算点 P = kG（G 是子群的基点）
  • 计算数字 r = xp mod n （xp 是 p 的 x 轴坐标）
  • 如果 r = 0，另选一个 k 并重新计算
  • 计算 s = $k^{-1}$ (z + rdA) mod n（dA 是 Alice 的私钥，k-1 是 k mod n 的乘法逆元）
  • 如果 s = 0，另选一个 k 并重新计算(r, s) 就是签名。

验证

  • 计算整数 μ1 = s-1z mod n
  • 计算整数 μ2 = s-1r mod n
  • 计算点 P = μ1G + μ2HA 只有当 r = xP mod n 的时候，签名才被成功验证

3.6. 仲裁数字签名

签名方的签名报文首先送给仲裁者A，仲裁者对报文和签名进行测试以检验出处和内容，然后注上日期和仲裁说明后发给接收方

采用公钥

签名可重用问题

  • 在签名中引入随机数
  • 对同一消息在不同时刻签名是相同的

4. 特殊签名

4.1. 盲签名

  • 不想让签名者知道文件的内容同时又对文件签名，称为盲签名(Blind Signature)

强盲签名(完全盲签名)

  • 通常人们把盲变换看作是信封，盲化文件就是对文件加个信封，而去掉盲因子的过程就是打开信封。
    • 文件在信封中时无人能读它，而在盲文件上签名相当于在复写纸信封上签名，从而得到了对真文件(信封内)的签名。

过程

  • 盲变换:A将要签名的文件与一个随机数相乘，该随机数称为盲因子。这实际上完成了对原文件的隐藏，隐藏完的文件被称为盲文件。
  • A将盲文件送给B
  • 签名:B对该文件签名。
  • 解盲变换:A对签过名的盲文件除以所用的盲因子，就得到了B对原文件的签名。

4.2. 多重数字签名

  • 能够实现多个用户对同一文件进行签名的数字签名方案称为多重数字签名(Digital Multi-signature)方案
    • 有序多重数字签名(Sequential Multi-signature)
    • 广播多重数字签名(Broadcasting Multi-signature)