1、第九章 公钥密码学 对称密码体制的缺陷：1）密钥分配问题密钥分配问题 通信双方要进行加密通信，需要通过秘密的安全信道协商加密密钥，而这种安全信道可能很难实现；2）密钥管理问题密钥管理问题 在有多个用户的网络中，任何两个用户之间都需要有共享的秘密钥，当网络中的用户 n 很大时，需要管理的密钥数目是非常大 2/)1(nn。3）没有签名功能：没有签名功能：当主体 A 收到主体 B 的电子文挡（电子数据）时，无法向第三方证明此电子文档确实来源于 B。9.1公钥密码学思想 n定义9.1.1一个公钥密码体制是这样的一个5元组M,C,K，EK，DK，且满足如下的条件：n1.M是可能消息的集合；n2.C是可能
2、的密文的集合；n3.密钥空间K是一个可能密钥的有限集；n4对每一个K=K1，K2 K，都对应一个加密算法EK1 E,EK1:MC和解密算法DK2 D,DK2:C M,满足对于任意的m M,都有c=EK1（m）,m=DK2(c)=DK2(EK1（m）)=m；n5对于所有的KK，在已知E的情况下推出D是计算上不可能的；n对每一个K K，函数EK1和DK2都是多项式时间可计算的函数。EK1是一个公开函数,K1 称作公钥；而DK2是一个秘密函数，K2称作私钥，由用户秘密地保存。npublic-key/two-key/asymmetricpublic-key/two-key/asymmetric 包括两
3、个密钥:n公开密钥(a public-key)public-key),可以被任何人知道,用于加密或验证签名n私钥(private-key)private-key),只能被消息的接收者或签名者知道,用于解密或签名n加密或验证签名者不能解密或多或生成签名.n是密码学几千年历史中最有意义的结果3.公钥加密方案4.公钥密码理论n由私钥及其他密码信息容易计算出公开密钥(a polynomial time(P-time)problem)n由公钥及算法描述,计算私钥是难的(an NP-time problem)n因此,公钥可以发布给其他人(wishing to communicate securely wi
4、th its owner)n密钥分配问题不是一个容易的问题(the key distribution problem)5.公钥算法分类nPublic-Key Distribution Schemes(PKDS)w用于交换秘密信息(依赖于双方主体)w常用于对称加密算法的密钥nPublic Key Encryption(PKE)w用于加密任何消息 w任何人可以用公钥加密消息 w私钥的拥有者可以解密消息 w任何公钥加密方案能够用于密钥分配方案PKDS w许多公钥加密方案也是数字签名方案nSignature Schemes w用于生成对某消息的数字签名w私钥的拥有者生成数字签名w任何人可以用公钥验证签
5、名 6.公钥的安全性n依赖于足够大大的困难性差别n类似与对称算法,穷搜索在理论上是能够破解公钥密码 exhaustive searchexhaustive search n但实际上,密钥足够长(512bits)n一般情况下,有一些已知的困难问题(hardhard problem”n要求足够大的密钥长度(512 bits)n导致加密速度比对称算法慢 2.RSA(Rivest,Shamir,Adleman)n使用最广泛的公钥加密算法nRivest,Shamir&Adleman(RSA)in 1977 nR L Rivest,A Shamir,L Adleman,On Digital Signatu
6、res and Public Key Cryptosystems,Communications of the ACM,vol 21 no 2,pp120-126,Feb 1978 n 3.RSA Setupn每个用户生成自己的公钥私钥对:n选择两个随机大素数(100 digit),p,q n计算模数 N=p.q n选择一个随机加密密钥匙 e:eN,gcd(e,(N)=1 n解下列同余方程,求解密密钥 d:ne.d=1 mod(N)and 0=d=N n公开加密密钥:Kr=er,Nr n保存其解密似钥:nK-1r=d,p,q 4。RSA 参数选择n需要选择足够大的素数 p,q n通常选择小的加密
7、指数e,且与(N)互素ne 对所有用户可以是相同的 n最初建议使用e=3n现在3太小n常使用 e=216-1=65535 n解密指数比较大5.RSA Usage n要加密消息 M，发送者要得到接收者的公钥Kr=er,Nr n计算:C=Mer mod Nr,where 0=MN n为解密 C，接收者使用私钥n K-1r=d,p,q n计算:M=Cd mod Nr 6.RSA理论理论nRSA 基于Fermats Theorem:nif N=pq where p,q are primes,then:X(N)=1 mod N nfor all x not divisible by p or q,ie
8、gcd(x,(N)=1 nwhere(N)=(p-1)(q-1)n但在 RSA 中，e&d 是特殊选择的nie e.d=1 mod(N)或e.d=1+R(N)nhence have:M=Cd=Me.d=M1+R(N)=M1.(M(N)R=M1.(1)R=M1 mod N n 8。RSA举例例子：例子：1.选素数选素数p=47和和q71，得，得n=3337,(n)=46703220；2.选择选择e=79，求得私钥，求得私钥d=e-1 1019(mod 3220）。）。3.公开公开n=3337和和e=79.4.现要发送明文现要发送明文688，计算：，计算：68879(mod 3337)=15705
9、.收到密文收到密文1570后，用私钥后，用私钥d1019进行解密：进行解密：15701019（mod 3337)=6889。RSA 安全性安全性 nRSA 安全性基于计算(N)的困难性 n要求分解模N 10.RSA的实现问题的实现问题n需要计算模 300 digits(or 1024+bits)的乘法n计算机不能直接处理这么大的数n（计算速度很慢）n需要考虑其它技术，加速RSA的实现11.RSA 的快速实现的快速实现n加密很快，指数小n解密比较慢，指数较大n利用中国剩余定理CRT，nCRT 对RSA解密算法生成两个解密方程（利用M=Cd mod R）n即:M1=M mod p=(C mod p
10、)d mod(p-1)n M2=M mod q=(C mod q)d mod(q-1)n解方程 M=M1 mod p n M=M2 mod q n具有唯一解（利用CRT）：n:M=(M2+q-M1)u mod q p+M1n 其中 p.u mod q=1 9.2.3概率素性检测概率素性检测 n定义9.2.3：如果P是素数，且a小于p,如果至少存在一个x 1，p-1满足x2a(modp)，则我们称a是模p的二次剩余（quadratic residue）。n定义9.2.4：设p是一奇素数，对任何a0,我们定义勒让德符号（Legendre symbol）L(a,p)为 0 如果a 0(modp)L(
11、a,p)=1 如果a是模p的二次剩余 -1 如果a是p的非二次剩余n定理9.2.1（欧拉准则）：设p是素数，那么x是模p的二次剩余当且仅当 x(P-1)/2 1(modp)n推论9.2.1：假设p是素数，那么L(a,p)a(P-1)/2(modp)n定义9.2.5：雅可比符号（Jacobi symbol）,记作J(a,n),是勒让德符号的一般化表示，它定义在任意正整数a和奇整数n上。设n的素数因子分解式为pe1pek,则J(a，n)=L(a，p1)e1 L(a，p)ek 对一个奇整数n的Solovay-strassen素性测试 1.选择一随机整数a，满足a 1,n-12.如果J(a,n)=a(
12、n-1)/2modn 则回答“n是素数”否则 回答“n是合数”7.Diffie-Hellman 密钥分配方案密钥分配方案n公钥密码问世 nDiffie&Hellman in 1976:n密钥交换的实际方法 n公钥方案概念的提出nW Diffie,M E Hellman,New directions in Cryptography,IEEE Trans.Information Theory,IT-22,pp644-654,Nov 1976 nJames Ellis(UK CESG)在案970年曾提出此概念12。El Gamal 公钥加密方案公钥加密方案nDiffie-Hellman key di
13、stribution scheme 的变形n能够用于安全交换密钥npublished in 1985 by ElGamal:nT.ElGamal,A Public Key Cryptosystem and a Signature Scheme Based on Discrete Logarithms,IEEE Trans.Information Theory,vol IT-31(4),pp469-472,July 1985.n安全性是基于离散对数 n缺点：增加了消息长度（2倍）13 密钥建立n密钥生成：密钥生成：n选取一个大素数p及本原元a mod pn接收者 Bob有一个密秘钥 xB n计算
14、 yB=axB mod p n 14.El Gamal 加密加密n为加密 M n发送者选择随机数k,0=k=p-1 n计算消息密钥 K:nK=yBk mod p n计算密文对:C=C1,C2 nC1=ak mod p nC2=K.M mod p n发送到接收者nk 需要永久保密 15.El Gamal 解密解密n首先计算 message key K nK=C1xB mod p=ak.xB mod p n计算明文:nM=C2.K-1 mod p 16.El Gamal Examplen选择 p=97 及本原根 a=5 nrecipient Bob 选择 秘密钥xB=58&计算并发布公钥yB=55
15、8=44 mod 97 nAlice 要加密 M=3 to Bob n首先得到 Bob的公开密钥 yB=44 n选择随机 k=36 计算:K=4436=75 mod 97 n计算密文对:nC1=536=50 mod 97 nC2=75.3 mod 97=31 mod 97 n发送 50,31 to Bob nBob 恢复 message key K=5058=75 mod 97 nBob 计算 K-1=22 mod 97 nBob 恢复明文 M=31.22=3 mod 97 9.3.1离散对数问题算法离散对数问题算法 9.4 基于纠错码的公钥密码体制基于纠错码的公钥密码体制n纠错码理论中的NP
16、C问题。n问题1 陪集重量问题 n问题2 重量分布问题 n问题3 最小距离问题 n当前关于建立基于纠错码的密码体制很多是基于传统的Hamming距离的。9.5椭圆曲线公钥体制 1椭圆曲线 n定义9.5.1：设p是一个大于3的素数，在Zp上的椭圆曲线y2=x3+ax+b 由一个基于同余式y2=x3+ax+b modp的解集（x，y）Zp*Zp和一个称为无穷远点的特定点O组成，这里的a,b Zp是二个满足4a+27b0 modp 的常数。椭圆曲线上的运算n设P=(x1,y1)E,Q=(x2,y2)E,若 x1=x2且y1=-y2,那么 P+Q=O;否则P+Q=(x3,y3),这里的x3=2-x1-
17、x2,y3=(x1-x3)-y1.x3=QPyaxQxxyy如果如果121121223P2椭圆曲线密码体制 定理9.5.1（Hasse定理）：如果E是定义在域GF(q)上的椭圆曲线，N是E上的点(x,y)GF(q)的数目，则qqN2|)1(|椭圆曲线密码体制有如下的一些特点：n1.在安全性相当的前提下,可使用较短的密钥.n2.椭圆曲线密码体制是建立在一个不同于大整数分解及素域乘法群离散对数问题的数学难题之上.n 3 椭圆曲线资源丰富,同一个有限域上存在着大量不同的椭圆曲线,这为安全性增加了额外的保证。n4.在执行速度方面,椭圆曲线密码体制较对应的离散对数体制要快,且在签名和解密方面较RSA 快
18、,但在签名验证和加密方面较RSA 慢.n5椭圆曲线密码体制的安全性分析成果并不丰硕.也许这可视为椭圆曲线密码体制具有高强度的一种证据,因此,大多数密码学家对这种密码体制的前景持乐观态度.9.6其他公开密钥密码体制其他公开密钥密码体制 9.6.1Goldwasser-Micali概率公开密钥概率公开密钥密码系统密码系统 Goldwasser-Micali概率公开密钥密码系统概率公开密钥密码系统的安全性分析与讨论的安全性分析与讨论 n对于攻击者来说，当他截获到密文(C1,C2,Ck)时，他能求出J(Ci,n)，但当mi=0，J(Ci,n)=J(xi2,n)=1，当mi=1,J(yxi2,n)=J(
19、y,n)J(xi2,n)=1,攻击者无法获得其它的任何信息，而对A来说，因为他拥有私有密钥p和q ，可求出J(Ci,p)，J(Ci,q),从而得到明文。n从传输效率来看，由于明文对应至1,n-1之间，故其效率为，|n|为n的长度。效率非常差。9.6.2Merkle-Hellman背包公背包公钥密码体制钥密码体制 9.6.3有限自动机公开密钥密码有限自动机公开密钥密码体制体制 n此类体制是基于分解两个有限自动机的合成也是困难的而构造的，尤其是当其中的一个或两个为非线性时，难度就会更大。小结n公钥密码学是现代密码学的很重要的组成部分，本章主要介绍了公钥密码的思想和几种基于计算复杂性的公钥密码体制。n公钥密码的思想nRSA体制n基于纠错码的公钥密码体制n基于椭圆曲线的公钥密码体制。
