(现代密码学原理与实践)第5章签名与认证

证算法为
(5-10)
其中:
e1=h(m)s-1 mod q, e2=rs-1 mod q
(5-11)
第5章签名与认证
实际上，由k={h(m)+xr}s-1 mod q知:
DSS的公布引起了学术界和商业界的激烈反应: 赞成的人 认为它长度小、速度快、成本低，对金融业特别有用；反对 的人则认为它不与国际标准(以RSA为标准的ISO、CCITT、 SWIFT等)兼容。从技术上讲，s不能等于零，要加以排除，否 则危及安全性。
则理论上可以推知
成立的概率为
它表明，如果B想用其他d值来否认y是他的签名，其结果就
很难使等式成立(立刻会被发现)。因此，B能愚弄A的概率只
有 。只要q充分大，B就没有理由否认自己的签名。
第5章签名与认证
5.1.5群签名
1991年，Chaum和VanHeyst基于以下问题提出群签名 (GroupSignature)方案:
第5章签名与认证
第5章 签名与认证
1. 数字签名 2. 单向散列(Hash)函数 3. 身份识别 4. 消息认证码(MAC) 习题 5 实践练习 5
第5章签名与认证
信息技术带来现代社会变革的一个重大方面是电子商务, 它极大地促进了传统商务模式的改变和结构的更新。而电子商 务的发展, 对信息安全技术又提出了多方位的新要求, 主要表 现在形形色色的签名与认证需求方面。密码技术近年来的巨大 发展, 也正集中体现在这些方面。
杂性要求；α∈ 是 域中q次单位元根, 1≤α≤q-1 。设G表示阶为q的 的乘法子群，且定义:
K={(p,α,β,a):β=αa mod p} 其中, 私有密钥为a；公开密钥为p、α、β
。
第5章签名与认证
签名算法
B掌握私钥a，欲对x签名，x∈G，则可计算
:
y=Sig a(x)=xa mod p
y∈G
签名算法
用私钥“加密”明文x, 得到的结果y叫做x的签名, 即
验证算法
Sig (x)=xd mod n=y Ver (y)=ye mod n≡x
(5-1) (5-2)
第5章签名与认证
首先y只能是x的签名(是x的加密结果)，它不能用于其他文档 ；其次，y是用发信人的私钥“加密”所得，别人做不出这样的 签名。任何人都可以用发信人的公钥解出x，与原来的x对照，即 可证明以上两点。
5.1.3DSS 数字签名标准(DSS)是美国国家标准和技术研究所(NIST)于 1991年8月公布的标准。它所采用的算法叫DSA, 实际上是 ElGamal的变形, 签名中用的是明文的信息摘要。 系统参数 p是一个512~1024位的大素数, 它满足离散对数难解问题；
q是160位的素数,且q|p-1; g∈ 是Zp域中q次单位元根。定义 K={(p,q,g,y,x}: y=gx mod p}, h(·)为公开的Hash函数。取公 钥k1=(p,q,g,y);私有密钥k2=(x)。
(5-5)
ks=(m-xr) mod (p-1)
即
ks=λ(p-1)+(m-xr)
于是有
gks=gλ(p-1)+(m-xr) = gλ(p-1)g(m-xr)
利用欧拉定理gp-1mod p=1, 就有 gλ(p-
第5章签名与认证
所以 gks=g(m-xr) mod p 因此有 yrrs=gxrgks=gxrg(m-xr)mod p=gm mod p 使用ElGamal方案应注意三方面的情况: 随机数k不能泄露，否则用x=(m-sk)r-1 mod p就可以在已知明文 的情况下窃取私钥。 k应当每次都不同，否则，若 m1=xr+ks1 mod (p-1),m2=xr+ks2 mod (p-1)两式相减得 m1-m2=k(s1-s2) mod (p-1)
一个公司所属各部门的计算机联网工作，各部门的打印机也 联在网上。打印时，应先确定是本公司的人才可以使用，然 而又要求不暴露用户的姓名。另一方面，如果打印机使用太 频繁时，主管者应能够查出是谁打印了这么多东西。
第5章签名与认证
这样做的不安全之处在于如果窃听者C收到(z,y)，它可以用 自己的密文z′=EB (x′)替代z，并对z′作自己的签名: SigC(z 再用y′代替y。而B收到(z′,y′)后，可能会做出发信人是C的误 因为用C的公钥(eC ,n′)能够证明签名 VerC(z′,y′),即 =z 从而相信了C发来的密文x′，结果受了骗。
第5章签名与认证
5.1.4不可否认签名方案 不可否认签名方案与一般的签名方案相比较, 最根本的特 点是如果没有签名者的合作, 签名就无法得到验证。这就 防止了未经签名者同意就随意复制他的签名文件进行电子 分发的可能性。有了这样的前提, 一旦验证通过, 签名者 也就没有理由否认。 一个不可否认签名由签名算法、验证算法和否认协议三部 分组成。 系统参数 设p=2q+1是一个大素数, 这里q是素数且符合离散对数复
第5章签名与认证
5.1数字签名
A收到B以明文方式送来的信息后，A如何 鉴别是B所发而非别人伪造或篡改的呢？又 如公钥密码系统中，各用户从网络上获取对 方的公开密钥，如何保证它没有被篡改或替 代呢？倘若C用自己的公钥替换了B的公钥 ，那么它就可以用自己的私钥解读所有人发 给B的密文。再如，单钥体系中，A.B两方 均掌握密钥K，如果没有签名，一旦发生争 议就说不清楚，因为B可以修改A发来的密 文，A也可以自己修改原文以赖账，法律上
第5章签名与认证
(5)签名是不可抵赖的，存在某种方法充分证明该签名确为 发信人所为。
用发信人私钥加密所发信件得到的密文，就是具有上述特 征的一种数字签名。
为了适应多种不同的用途，为了使用起来更方便更安全， 滋生出了一系列不同形式的数字签名，下文将陆续介绍。它们 在电子商务和信息网络中发挥着不可替代的作用。
缺乏判定谁是谁非的凭证。
第5章签名与认证
由于电子文档的易拷贝性和可粘贴性，使机械地照搬手写签名 到电子文档上的做法失效，必须引入功能相似，但方式不同的 有效认证方式。 数字签名是含有发送方身份的一段数字或代码串。它应有以下 特征: 签名是可以验证的，收到签名的人容易由签名确定来信人。 签名是不可伪造的，除了签名者之外的任何人无法实现这个签 名。 签名是不可重用的，一个签名只对一个文件生效，无法用于其 他文件。 签名是不可改变的，一旦签名发出便不能再作修改。
系统参数
p是大素数, g 的一个生成元(即本原根)。定义密钥为 是 K={(p,g,y,x): y=gx mod p}，x∈
其中，公开密钥k1为y、p、g；私有密钥k2
为x。签名算法
签名者拥有(k1k2)=(p，g，y，x)，随机数 和待签消息
k∈
m。生成的Si签g 名(为m,k)=(r,s) 这里,对r和s有
第5章签名与认证
sx=(mrk+1) mod (p-1) ys=rmrg mod p
(r+m)x=(k+s) mod (p-1) y(m+r)=rgs
mod p x=［(m+r)k+s］mod (p-1)
y=r(m+r)gs mod p sx=［k+(m+r)］mod
(p-1) ys=rg(m+r) mod p x=［sk+(r+m)
统，又不能为其他明文生成签名，仅此而已。所以，它并不 能对ElGamal构成威胁。
为了把明文与签名结合起来，可以有多种方式，前面所讲 的方式是: ks=(m-xr) mod (p-1)其验证方程是 yrrs=gm mod p 其他方式及其验证方程列举如下:
第5章签名与认证
mx=(rk+s) mod (p-1) ym=rrgs mod p mx=(sk+r) mod (p-1) ym=rsgr mod p rx=(mk+s) mod (p-1) yr=rmgs mod p rx=(sk+m) mod (p-1) yr=rsgm mod p sx=(rk+m) mod (p-1) ys=rrgm mod p sx=(mk+r) mod (p-1) ys=rmgr mod p sx=(k+mr) mod (p-1) ys=rgmr mod p mrx=(k+s) mod (p-1) ymr=rgs mod p x=(mrk+s) mod (p-1) y=rmrgs mod p x=(sk+rm) mod (p-1) y=rsgmr mod p rmx=(sk+1) mod (p-1) ymr=rsg mod p
第5章签名与认证
设d=gcd{s1-s2,p-1}, 因为d|(p-1)且d|(s1-s2),于是d|(m1m2)定义
则有
,且
， 那么:
从而通过验证r=gk mod p就可以确定k。
第5章签名与认证
(3)由于验证只是核实等式yrrs=gm mod p是否成立，因此可 考虑通过伪造能使上式成立的(r,s)来攻击。然而它的作用只不 过对给定明文m又作了一个能通过认可的签名，既没有破译系
通常不仅要认证签名，还要加密明文，不让合法收信人以外 的其他人看到明文x，这就要进行双重“加密”。如A给B发信， 有两种方案:
(1)先加密再签名: A做z=EB(x)，y=SigA(z)的运算，把(z,y) 传输给B；B收到(z,y)后，用自己的私钥解读密文,即做x=DB(z) 的运算，再用A的公钥验证签名VerA(z,y)，看是否满足 =z。
和e2都能自恰。证明如下:
ห้องสมุดไป่ตู้
第5章签名与认证
因为
所以
不可否认签名方案的安全性分析
首先, A是验证了
后, 才同意接收y
作为x的签名的, 理论上可以推知y≠xa mod p情况下
的概率只有 , 因此一个伪造的签名能使A相信的概率只 有。
第5章签名与认证
其次，若y=xa mod p且A遵守否认协议，但存在d和d′使:
(5-3)
r=gk mod p, s=(m-xr)k-1 mod (p-1)(5-4)
随机数k用以生成签名中的r部分, 而明文用以生成
签名中的部分。
第5章签名与认证
验证算法
验证者有公钥k1=(p, g, y), 收到的明文m和签名(r,s), 从而验证算法为
Ver (r,s)=yrrs≡gm mod p 实际上, 因为
］mod (p-1) y=rsg(m+r) mod p
(r+m)x=(sk+1) mod (p-1) y(m+r) =rsg
mod p sx=［(r+m)k+1］mod (p-1)
ys=r(m+r)g mod p
通式是:
Ax=Bk+C mod (p-1)
yA=rBgC mod p
(5-6)
第5章签名与认证
第5章签名与认证
签名算法
签名者拥有私钥x, 对于随机数 k∈成的签名为
和待签消息m∈ , 生
(m,k)=(r,s)
(5-7)
这里:
r=(gk mod p) mod q(必然小于160位)
(5-8)
s={h(m)+xr}k-1 mod q(必然小于160位) (5-9) 验证算法 验证者有公钥k1=(p，g，y)，收到的明文m和签名(r,s)，验
数字签名的主要功能有: (1)识别来信(函)的正确信源。 (2)验证发信人的合法身份 。 (3)检查信函内容的完整性。 (4)获得行为不可否认的证据 。 (5)标示知识产权的印记。
第5章签名与认证
5.1.1RSA签名体系
RSA签名体系与RSA加密算法相同, 但用法不同。系统参数
取两个大素数p和q, 计算n=p·q和 (n)=(p-1)(q-1), 随机 选择整数d使gcd(d, (n))=1, 求出模 (n)的逆元e, 使它 满足 ed=1 mod (n)。取公开密钥为k1=(n, e)；私有密钥为 k2=(p,q,d)
y就是B对x的签名。
(5-12)
验证协议 (1) A欲验证签名, 可任意选取
e1,e2∈把它传给B。
。计算c=
mod
(2) B计算 (3) A接收d并验证
, 并传回A。 mod p。
(5-13)
如果成立，便有充分必要的理由认为y是B对x的一条有效的
签名。因为B用自己的私钥参与了验证过程，使A任意地选取e1
(2) 先签名再加密: A先做SigA(x)=y的运算，再做连明文带 签名一起加密EB(x,y)=z的运算，发送z给B；B收到z后先解密得到 签名，再进行验证。
这种方案中，窃听者C即使收到z，也因无A的私钥而不能 解译，所以比较安全。
第5章签名与认证
5.1.2ElGamal签名方案
1985年, ElGamal基于离散对数提出了一种签名方案。