第七章数字签名密码协议..ppt

第7章 数字签字和密码协议,7.1 数字签字的基本概念 7.2 数字签字标准 7.3 其他签字方案 7.4 身份证明技术 7.5 秘密分享,7.1 数字签字的基本概念,数字签名应具有的特性： （1）签名是可信的：任何人可验证签名的有效性 （2）签名是不可伪造的：除合法签名者外，其他人伪造签名是困难的 （3）签名是不可复制的：一消息的签名不能复制为另一消息的签名 （4）签名的消息是不可改变的：经签名的消息不能被篡改 （5）签名是不可抵赖的：签名者事后不能否认自己的签名数字签名：对身份认证，保持数据完整性、不可否认性数字签名(digital signature): 用于对数字消息签名,以防消息的伪造或篡改,也可用于通信双方的身份鉴别数字签名：对身份认证，保持数据完整性、不可否认性 MAC可对身份认证，保持数据完整性，但不具有不可否认性RSA签字体制为例说明签字的产生过程 体制参数： 选两个保密的大素数p和q，计算n=p×q，φ(n)=(p-1)(q-1)； 选一整数e，满足1eφ(n)，且gcd(φ(n),e)=1； 计算d，满足d·e≡1 mod φ(n)； 以{e,n}为公开钥, {d}为秘密钥。

签字: 设消息为mZn，对其签字为 s≡md mod n 验证: 接收方在收到消息m和签字s后，验证 是否成立，若成立，则发送方的签字有效安全性：大数分解的困难性缺点： （1）对任意y Zn，任何人可计算x≡ye mod n，因此任何人可伪造对随机消息x的签名 （2）如果消息x1和x2的签名分别为y1和y2，则知道x1 , y1, x2, y2的人可伪造对消息x1 x2的签名y1 y2 （3）在RSA签名方案中，需签名的消息x Zn，所以每次只能对 位长的消息进行签名签名速度慢克服缺陷的方法：,签名之前先求消息的Hash值数字签字的一般描述： 明文消息：m 私钥：x 公钥： y 签字算法：s=Sigx(m) 验证算法：Very(s, m) 算法的安全性：从m和s难求密钥x， 或伪造消息m′，使 m′和s可被验证为真数字签字标准DSS(Digital Signature Standard)是由美国NIST公布的联邦信息处理标准FIPS PUB 186，其中采用了上一章介绍的SHA和一新的签字技术，称为DSA(Digital Signature Algorithm)。

DSS最初于1991年公布，在考虑了公众对其安全性的反馈意见后，于1993年公布了其修改版7.2 数字签字标准,DSA安全性基于求离散对数的困难性 算法描述如下：,7.2.2 数字签字算法DSA,(1) 全局公开钥 p：2L-11的任一整数 (2) 用户秘密钥x： 0xq的随机数 (3) 用户的公开钥y： y≡gx mod p数字签字算法DSA ：,,由于离散对数的困难性，敌手从r恢复k或从s恢复x都是不可行的 预计算: r的模指数运算r=(gk mod p) mod q，这一运算与待签的消息无关 用户可以预先计算出很多r和k-1以备以后的签字使用，可大大加快签字的速度基于离散对数问题的数字签字体制是数字签字体制中最为常用的一类，其中包括ElGamal签字体制、DSA签字体制、Okamoto签字体制等7.3 其他签字方案 7.3.1 基于离散对数问题的数字签字体制,1. 离散对数签字体制 ElGamal、DSA、Okamoto等签字体制都可归结为离散对数签字体制的特例 (1) 体制参数 p：大素数； q：p-1或p-1的大素因子； g：g∈RZ*p，且gq≡1(mod p)，其中g∈R Z*p表示g是从Z*p中随机选取的，其中Z*p=Zp-{0}； x：用户A的秘密钥，1xq； y：用户A的公开钥，y≡gx(mod p)。

2) 签字: 对于待签字的消息m，A执行以下步骤： ① 计算m的杂凑值H(m) ② 选择随机数k：1kq，计算r≡gk(mod p) ③ 从签字方程ak≡b+cx(mod q)中解出s 下表给出了这些可能选择中的一小部分，以(r, s)作为产生的数字签字3) 签字: 接收方在收到消息m和签字(r, s)后，可以按照以下验证方程检验：,,2. ElGamal签字体制 体制参数: p：大素数； g：Z*p的一个生成元； x：用户A的秘密钥， x∈RZ*p； y：用户A的公开钥， y≡gx(mod p)3. Schnorr签字体制 体制参数: p：大素数，p≥2512； q：大素数，q|(p-1)，q≥2160； g：g∈RZ*p,且gq≡1(mod p)； x：A的秘密钥，1xq； y：A的公开钥，y≡gx(mod p)4. Neberg-Rueppel签字体制 该体制是一个消息恢复式签字体制，即验证人可从签字中恢复出原始消息，因此签字人不需要将被签消息发送给验证人 体制参数: p：大素数； q：大素数，q|(p-1)； g：g∈RZ*p，且gq≡1(mod p)； x：A的秘密钥，x∈RZ*p； y：A的公开钥，y≡gx(mod p)。

Neberg-Rueppel签字体制,5. Okamoto签字体制 体制参数: p：大素数，且p≥2512; q：大素数，q|(p-1)，且q≥2140； g1, g2：两个阶为q的元素, x1, x2：用户A的秘密钥，两个小于q的随机数； y：用户A的公开钥， Okamoto签字体制,设n是一个大合数，找出n的所有素因子是一个困难问题，称之为大数分解问题7.3.2 基于大数分解问题的数字签字体制,在很多情况下，用户都需证明自己的身份，如登录计算机系统、存取电子银行中的账目数据库、从自动出纳机ATM取款等 传统的方法：使用通行字或个人身份识别号PIN来证明自己的身份 缺点：检验用户通行字或PIN的人或系统可使用用户的通行字或PIN冒充用户7.4 身份证明技术,身份证明技术，可使用户在不泄露自己的通行字或PIN的情况下向他人证实自己的身份交互证明系统由两方参与 证明者P （prover） 验证者V （verifier） P知道某一秘密（如公钥密码体制的秘密钥或一平方剩余x的平方根），P希望使V相信自己的确掌握这一秘密 交互证明比较典型的方式：每轮V都向P发出一询问，P向V做出一应答。

所有轮执行完后，V根据P是否在每一轮对自己发出的询问都能正确应答，以决定是否接受P的证明交互证明系统,交互证明和数学证明的区别： 数学证明的证明者可自己独立地完成证明，而交互证明是由P产生证明、V验证证明的有效性来实现，因此双方之间通过某种信道的通信是必需的 交互证明系统须满足以下要求： ① 完备性：若P知道某一秘密，V将接受P的证明 ② 正确性：如果P能以一定的概率使V相信P的证明，则P知道相应的秘密在交互证明系统中，设P知道某一秘密，并向V证明自己掌握这一秘密，但又不向V泄露这一秘密，这就是最小泄露证明 进一步，如果V除了知道P能证明某一事实外，不能得到其他任何信息，则称P实现了零知识证明，相应的协议称为零知识证明协议零知识证明,例 下图表示一个简单的迷宫，C与D之间有一道门，需要知道秘密口令才能将其打开P向V证明自己能打开这道门，但又不愿向V泄露秘密口令零知识证明协议示例,零知识证明协议示例,可采用如下协议： ① V在协议开始时停留在位置A ② P一直走到迷宫深处，随机选择位置C或位置D ③ P消失后，V走到位置B，然后命令P从某个出口返回位置B ④ P服从V的命令，必要时利用秘密口令打开C与D之间的门。

⑤ P和V重复以上过程n次协议中，如果P不知道秘密口令，就只能从来路返回B，而不能走另外一条路此外，P每次猜对V要求走哪一条路的概率是1/2，因此每一轮中P能够欺骗V的概率是1/2假定n取16，则执行16轮后，P成功欺骗V的概率是1/216=1/65536于是，如果P16次都能按V的要求返回，V即能证明P确实知道秘密口令还可以看出，V无法从上述证明过程中获取丝毫关于P的秘密口令的信息，所以这是一个零知识证明协议1. 协议及原理 设n=pq，p和q是两个不同的大素数 x是模n的平方剩余，y是x的平方根 n和x是公开的，而p、q和y是保密的 y：证明者P的秘密 证明者P和验证者V通过交互证明协议，P向V证明自己掌握秘密y，从而证明了自己的身份7.4.1 简化的Fiat-Shamir身份识别方案,协议如下： ① P随机选r(0rn)，计算a≡r2 mod n，将a发送给V ② V随机选e∈{0,1}，将e发送给P ③ P计算b≡rye mod n，即e=0时，b=r；e=1时，b=ry mod n将b发送给V ④ 若b2≡axe mod n，V接受P的证明在协议的前3步，P和V之间共交换了3个消息，这3个消息的作用分别是： 第1个消息是P用来声称自己知道a的平方根； 第2个消息e是V的询问，如果e=0，P必须展示a的平方根，即r，如果e=1，P必须展示被加密的秘密，即ry mod n； 第3个消息b是P对V询问的应答。

2. 协议的完备性、正确性和安全性 (1) 完备性 如果P和V遵守协议，且P知道y，则应答b≡rye mod n应是模n下axe的平方根 在协议的第④步V接受P的证明，所以协议是完备的2) 正确性 假冒的证明者E可以1/2的概率骗得V接受自己的证明： ① E随机选r(0rn)和 ，计算 将a发送给V ② V随机选e∈{0,1}，将e发送给E ③ E将r发送给V根据协议的第④步，V的验证方程是 ，当 时，验证方程成立，V接受E的证明，即E欺骗成功 因 的概率是1/2，所以E欺骗成功的概率是1/2 另一方面，1/2是E能成功欺骗的最好概率 否则假设E以大于1/2的概率使V相信自己的证明，那么E知道一个a，对这个a他可正确地应答V的两个询问e=0和e=1，意味着E能计算b21≡a mod n和b22≡ax mod n，即 ，因此E由 即 可求得x的平方根y，矛盾3) 安全性 协议的安全性可分别从证明者P和验证者V的角度来考虑 考虑V的安全性假冒的证明者E欺骗V成功的概率是1/2，对V来说，这个概率太大了。

为减小这个概率，可将协议重复执行多次，设执行t次，则欺骗者欺骗成功的概率将减小到2-t考虑P的安全性因为V的询问是在很小的集合{0,1}中选取的，V没有机会产生其他信息，而P发送给V的信息仅为P知道x的平方根这一事实，因此V无法得知x的平方根1. 协议及原理 在简化的Fiat-Shamir身份识别方案中，验证者V接受假冒的证明者证明的概率是1/2，为减小这个概率，将证明者的秘密改为由随机选择的t个平方根构成的一个向量 y=(y1,y2,…,yt)， 模数n和向量x=(y21,y22,…,y2t)是公开的，其中n仍是两个不相同的大素数的乘积7.4.2 Fiat-Shamir身份识别方案,协议： ① P随机选r(0rn)，计算a≡r2 mod n，将a发送给V ② V随机选e=(e1,e2,…,et)，其中ei∈{0,1}(i=1,2,…,t)，将e发送给P ③ P计算 ，将b发送给V ④ 若 ，V拒绝P的证明，协议停止 ⑤ P和V重复以上过程k次2. 协议的完备性、正确性和安全性 (1) 完备性 若P和V遵守协议，则V接受P的证明2) 正确性 如果假冒者E欺骗V成功的概率大于2-kt，意味着E知道a，能正确地应答V的两个询问: e=(e1,e2,…,et)和e=(f1,f2, …,ft) 。

E能计算两个不同的值:,(3) 安全性 。