数字签名

一、问题由来

哈希函数用于验证消息的完整性，数字签名用于验证消息来源。
仅仅使用哈希函数进行消息认证，可以防止第三方篡改消息内容，但不能防止通信双方中的某一方对另一方的欺骗和伪造。例如，采用消息认证码（MAC）的方式，B伪造一个消息，并使用与A共享的密钥产生该消息的认证码，并声称该消息来自A；由于B有可能伪造A发送的消息，A就可以对自己发送过的消息予以否认。
在网络应用中，凡是要解决伪造、抵赖、冒充、篡改与身份鉴别的问题，都可以运用数字签名来处理。

数字签名具备的特性
精确性：签名和文档一一对应。
唯一性：私钥签名，公钥验证。
时效性：在签名后附加时间戳。（互联网上有时间服务器，用它获取时间。）

由加密算法产生数字签名
单钥加密：保密性和认证性，但是可以假冒身份。
公钥加密：发送方私钥加密（签名），接收方公钥解密（验证）。

由签名算法产生数字签名
输入消息M和密钥K，数字签名$S=Sig_k(M)$
验证：$S=Sig_k(M)$时通过验证，$S\neq Sig_k(M)$时不通过。
算法的安全性在于难以推断出密钥或伪造一个消息$M'$使得$S=Sig_k(M')$.

另外，在实际应用数字签名时，加ID才能识别不同发送方。
$ID_{A}||M||sig_{k}(H(M))$

二、由加密算法产生数字签名

1.直接执行的数字签名

直接明文签名
只有A能够知道sk_A，所以在传输过程中无法篡改明文。
只进行私钥签名没有提供保密性，任何人都可以获得A的公钥，在验证签名的同时进行解密而获得明文。

改进：先私钥签名，再公钥加密。提供了机密性。

消息摘要签名
在实际应用中明文太长，加密时开销较大，所以把明文M转换为摘要$H(m)$。
A -> B: $m||E_{SK_a}[H(m)]$
这样做直接把明文暴露在外了，对于需要保密的消息还需要再做一次加密。
A -> B:$ E_{k}[m||E_{SK_a}[H(m)]]$ 或 A -> B: $E_{k}[m]||E_{SK_a}[H(m)]$
前者对整个部分加密，开销稍大，但是破解也稍难。

直接执行的数字签名的不足
1.验证依赖于发送方的私有密钥
发送方可能会声称其私有密钥丢失或被窃，从而别人伪造了他的签名；
对此的策略可以是：被签名的消息包含一个由公正的第三方生成的时间戳；要求密钥一旦泄露，立即报告给授权中心——CRL列表宣告密钥失效。
2.“向前”不安全性
密钥在时间T被窃取，敌手可以伪造早于或等于时间T的时间戳。

2.可仲裁数字签名：

不允许个人打时间戳，只能由仲裁者打。所有的通信参与者必须绝对相信仲裁者。
（然而实际应用中在互联网上很难找到受信任的第三方。）现有的可信第三方有CFCA等。

单密钥可仲裁数字签名(仲裁者可获知消息)
发送者、接收者分别与仲裁者共享密钥$k_{ax}$、$k_{bx}$
Alice计算$H(m)$和$S = E_{k\_ax}[ID_{Alice}||H(m)]$，并将$ID_{a}||m||S$发送给仲裁者；
仲裁者X解密S，要验证消息内容的完整性和消息来源。仲裁者利用$m$重新计算$H'(m)$,验证是否等于$H(m)$；验证$ID_{a}$与$ID_{Alice}$是否相等。
仲裁者X计算$E_{k\_bx}[ID_{Alice}||m||E_{k\_ax}[ID_{Alice}||H(m)]||T]$，并将结果发送给接收者Bob；
接收者Bob解密仲裁者X发来的消息，并将m和签名保存起来。$E_{k\_ax}[ID_{Alice}||H(m)]$需要$E_{k\_ax}$，Bob解不开，作为证据保留。

在仲裁者解密Alice的消息这一步中，仲裁者是能够知道明文内容的。于是产生了问题：
1.出于隐私不希望仲裁者知道消息；2.无法区分消息密级；3.仲裁者被买通而篡改消息。

单密钥可仲裁数字签名(仲裁者不能获知消息)
发送者、接收者共享密钥$k_{ab}$，发送者、接收者分别与仲裁者共享密钥$k_{ax}$、$k_{bx}$.
Alice计算$E_{k\_ab}(m)、E_{k\_ax}[ID_{Alice}||H(E_{k\_ab}(m))]$，并将如下消息发送给仲裁者：
$ID_{a}||E_{k\_ab}(m)||E_{k\_ax}[ID_{Alice}||H(E_{k\_ab}(m))]$ ；
仲裁者X解密签名，解开$E_{k\_ax}[ID_{Alice}||H(E_{k\_ab}(m))]$，验证$ID_{Alice}$和$E_{k\_ab}(m)$；
仲裁者X计算$E_{k\_bx}[ID_{Alice}||E_{k\_ab}[m]||E_{k\_ax}[ID_{Alice}||H(E_{k\_ab}(m))]||T]$，并将结果发送给接收者Bob；
接收者Bob解密仲裁者X发来的消息，并将m和签名保存起来。

单密钥签名方案的弊端：
1、仲裁者可以联手发送者进行否认；
2、仲裁者可以联手接收者进行伪造。

双密钥可仲裁数字签名(仲裁者不能获知消息)
发送者、接收者分别拥有公私钥对($sk_{Alice}, pk_{Alice}$)、($sk_{Bob}, pk_{Bob}$).
Alice计算$S = E_{sk_{Alice}}[ID_{Alice}||E_{pk_{Bob}}(E_{sk_{Alice}}(m))]$，并将$ID_{a}||S$发送给仲裁者；
仲裁者X检查Alice的公私钥对的有效性；仲裁者可以通过$E_{pk_{Alice}}$解出$ID_{Alice}||E_{pk_{Bob}}(E_{sk_{Alice}}(m))$,验证$ID_{a}==ID_{Alice}$.
仲裁者X计算$E_{sk_{x}}[ID_{Alice}||E_{pk_{Bob}}(E_{sk_{Alice}}(m))||T]$，并将结果发送给接收者Bob；用服务器的私钥签名，Bob可以拿到公钥。
接收者Bob解密仲裁者X发来的消息，并将$m$和签名保存起来。

双密钥可仲裁数字签名的优势
通信之前各方无需共享任何信息，避免了合谋攻击；
即使Alice的私钥被窃取，只要仲裁者的私钥未被窃取，时间戳就不能被伪造；
消息对除Alice和Bob之外的所有人保持机密性。

三、数字签名标准：DSS

DSS是数字签名标准，DSA是数字签名算法。
DSA是ElGamal公钥算法变体，其安全性基于计算离散对数的难度。

1.DSA工作原理

初始化
1.选择一个素数$p$，两个随机数$q$和$g$
$2^{L-1} < p < 2^{L}， 512 ≤ L≤ 1024$，并且$L \% 64 = 0$；
$q$是$p-1$的素因子，$ 2^{159} < q < 2^{160}$；$g ≡ h^{\frac{p-1}{q}} (mod\quad p)$，$h$是一个整数，$1 < h < p - 1,g(mod\quad p) > 1$.
2.公私钥对(PK, SK)
SK是随机整数， $0 < SK < q，PK≡ g^{SK} (mod\quad p)$.
3.秘密参数k
k是随机整数，0 < k < q，每次签名重新生成k。

签名
发送方随机选择秘密参数k；
计算$r ≡ (g^{k} (mod\quad p)) (mod\quad q)$；
计算$s ≡ (k^{-1} (H(m) + SKr)) (mod\quad q)$;
$H(m)$是使用SHA-1生成的m的散列码
(r, s)作为对消息m的数字签名。

签名验证
接收者接收到$<m, r, s>$;
接收者验证： $0 < r < q, 0 < s < q$；
计算
$w ≡ s^{-1} (mod\quad q)$
$u_1 ≡ [H(m)w] (mod\quad q)$
$u_2 ≡ [rw] (mod\quad q)$
$v ≡[(g^{u1}PK^{u2}) (mod\quad p)] (mod\quad q)$.
如果$v = r$，则签名验证通过，否则签名不可信。

$v = r$是一致性比对，按位比较。

四、特殊数字签名(仅作了解)

不可否认数字签名
在无签字者的配合下不可能验证签字的有效性，应用于电子出版领域的知识/版权保护。

盲签名
第三方生成签名时造成了信息泄露。
签名者把明文消息m通过盲变换为m’，隐藏了明文m的内容；
将m’给签字者(仲裁者)进行签名，得到签名结果s(m’)；
签名者取回s(m’)，采用解盲变处理得到s(m)，即m的签名。

应用于选举投票、电子现金等等。

对明文消息的盲变换：
$sig(m)=s1$;
$sig(rm)=s2$;
$sig(r)=s3$;
需要满足结构：$s2=s1*s3$；$s2*s3^{-1}=s1$.