资源描述
2024/7/7现代密码学理论与实践-101/59本章要点v公钥密码方案是安全的，仅当公钥的真实性能够得到保证。公钥证书方案提供了必要的安全性。v一个简单的公钥算法是Diffie-Hellman密钥交换协议。这个协议使得通信双方利用基于离散对数问题的公钥算法建立秘密密钥。这个协议是安全的，仅当通信双方的真实性能够得到保证。v椭圆曲线算术可以用来开发许多椭圆曲线密码ECC方案，包括密钥交换，加密和数字签名。v就ECC而言，椭圆曲线算术是指使用定义在有限域上的椭圆曲线方程。方程里的系数和变量都是域里的元素。已经开发了很多使用Zp和GF(2m)的方案。2024/7/7现代密码学理论与实践-102/59v公开密码的主要作用之一就是解决密钥分配问题，公钥密码实际上可以用于以下两个不同的方面公钥的分配公钥密码用于传统密码体制的密钥分配v几种公钥分配方法公开发布、公开可访问的目录公钥授权、公钥证书v公钥的公开发布用户将他的公钥发送给另一通信方，或者广播给通信各方，比如在电子邮件后附上PGP密钥，或者发布到邮件列表上最大问题在于任何人都可以伪造这种公钥的发布10.1.1 密钥管理之公钥的分配2024/7/7现代密码学理论与实践-103/59自由的公钥发布2024/7/7现代密码学理论与实践-104/59v维护一个动态可访问的公钥目录可以获得更大程度的安全性v一个可信实体或组织负责这个公开目录的维护和分配目录包含name,public-key等项每一通信方通过目录管理员以安全的方式注册一个公钥通信方在任何时刻可以用新的密钥替代当前的密钥目录定期更新目录可通过电子方式访问v一旦攻击者获得目录管理员私钥，则可传递伪造的公钥，可以假冒任何通信方以窃取消息，或者修改已有的记录公开可访问的目录2024/7/7现代密码学理论与实践-105/59公开可访问的目录2024/7/7现代密码学理论与实践-106/59vA发送带有时间戳的消息给公钥管理员,请求B的当前公钥v管理员给A发送用其私钥KRauth加密的消息,A用管理员的公钥解密，可以确信该消息来自管理员：B的公钥KUb，用来加密；原始请求，A可以验证其请求未被修改；原始时间戳,A可以确定收到的不是来自管理员的旧消息。vA保存B的公钥,并用它对包含A的标识IDA和Nonce1的消息加密,然后发送给BvB以同样方式从管理员处得到A的公钥vB用KUa对A的N1和B的N2加密,发送给AvA用B的公钥对N2加密并发送给B,使B相信其通信伙伴是A公钥授权2024/7/7现代密码学理论与实践-107/59公钥分配方案2024/7/7现代密码学理论与实践-108/59v有了公钥证书使得不通过实时访问公钥授权部门而实现公钥交换成为可能v公钥证书将一个通信方的身份与他的公开密钥绑定在一起，通常还包括有效期和使用方法等v证书的所有内容必须经由可信公钥授权方或者证书授权方签名后方可生效v知道公钥授权当局公开密钥的任何人都可以验证一个用户的公开密钥证书的有效性 v对于申请者A，管理员提供的证书为：CA=EKRauth T,IDA,KUav其他人读取并验证：DKUauthCA=DKUauth EKRauth T,IDA,KUa=(T,IDA,KUa)10.1.2 公钥证书2024/7/7现代密码学理论与实践-109/59公钥证书的交换2024/7/7现代密码学理论与实践-1010/59v采用前述方法获得的公开密钥可以用于保密和认证之需v公钥密码算法速度较慢，因此更适合作为传统密码中实现秘密密钥分配的一种手段v因此，需要产生会话密码来加密v已经有一些方法用来协商适当的会话密钥10.1.3 利用公钥密码分配传统密码体制的密钥2024/7/7现代密码学理论与实践-1011/59一种简单的秘密密钥分配方法vMerkle在1979提出一种简单的方法A产生公/私钥对PUa,PRa,将含有PUa和标识IDA的消息发给BB产生秘密密钥(会话密钥)Ks,并用A的公钥加密后发给AA解密D(PRa,E(PUa,Ks),得到Ks,这样双方即可通信v这个协议不安全，因为会受到中间人攻击2024/7/7现代密码学理论与实践-1012/59具有保密性和真实性的密钥分配2024/7/7现代密码学理论与实践-1013/5910.2 Diffie-Hellman密钥交换vDiffie和Hellman在1976年首次提出了公钥算法，给出了公钥密码学的定义，该算法通常被称为Diffie-Hellman密钥交换算法vDiffie-Hellman密钥交换算法是一种公钥分发机制它不是用来加密消息的所生成的是通信双方共享的会话密钥，必须保密，其值取决于通信双方的私钥和公钥信息vDiffie-Hellman密钥交换算法是基于有限域GF中的指数运算的(模一素数或多项式)vDiffie-Hellman密钥交换算法的安全性依赖于求解离散对数问题DLP2024/7/7现代密码学理论与实践-1014/59离散对数问题Discrete Logarithm Problemv如果a是素数p的一个原根(本原元素)，则a mod p,a2 mod p,.,ap-1 mod p，生成模p的完全剩余集1,2,.,p-1对于所有素数，其原根必定存在，即对于一个整数b和素数p的一个原根a，可以找到唯一的指数i,使得 b=ai mod p,其中 0=i=p-1指数i称为b的以a为基数的模p的离散对数或者指数。v离散对数密码体制的安全性基于DLP问题,在已知C和P的情况下,由d求M很容易,由M求d很困难,d=logCM in GF(P),最快的算法需要T=exp(ln(P)lnln(P)1/2)次运算。当P是200位时,T=2.7x1011,如果1s解一次,需要23天；如果P=664位,则T=1.2x1023,约1012天或2.739x109年,约2.7亿年.只要P足够大,可以达到足够安全。2024/7/7现代密码学理论与实践-1015/59Diffie-Hellman Key Exchangev通信双方约定一个大素数(或多项式)p,和模p的一个素根v各方产生公开密钥选择一个秘密钥(数值)，如xA p，xB p 计算公钥,如yA=xA mod p,yB=xB mod p,并相互交换 v双方共享的会话密钥KAB可以如下算出 KAB=xA.xB mod p =yAxB mod p (which B can compute)=yBxA mod p (which A can compute)vKAB是双方用对称密码通信时共享的密钥v如果双方继续通信，可以继续使用这个密钥，除非他们要选择新的密钥v攻击者如果想要获得x,则必须解决DLP问题2024/7/7现代密码学理论与实践-1016/59Diffie-Hellman ExamplevUsers Alice&Bob who wish to swap keysvAgree on prime p=353 and =3vSelect random secret keys:A chooses xA=97,B chooses xB=233vCompute public keys:yA=397 mod 353=40(Alice)yB=3233 mod 353=248 (Bob)vCompute shared session key as:KAB=yBxA mod 353=24897 mod 353=160(Alice)KAB=yAxB mod 353=40233 mod 353=160(Bob)2024/7/7现代密码学理论与实践-1017/5910.2.2 Diffie-Hellman密钥交换协议v本协议不能抵抗中间人攻击2024/7/7现代密码学理论与实践-1018/59v假设A和B互相通信，共享大素数p，本原元素，0mp-1v加密：A选择k0,p-1,k的作用其实即为xA,A访问公共区域找到B的公开密钥YB=xB mod p,计算：K=(YB)k mod p,即K=xBk mod pc1=k mod pc2=mK mod p密文即为(c1,c2)v解密：B首先恢复K：K=c1xB mod P=kxB mod p然后恢复m：m=c2/K mod P=c2K-1 mod p基于DLP的概率密码系统ElGamal Cryptosystem2024/7/7现代密码学理论与实践-1019/59这里特别注意，k不能重复使用，如果(1)c1,1=k mod pc2,1=m1K mod p(2)c1,2=k mod pc2,2=m2K mod p得：m1/m2=c2,1/c2,2 mod p.如果m1已知，m2即可算出。vElGamal密码体制是概率密码体制，同样的明文每次加密得到不同的密文,因为每次随机选择k。vElGamal密码体制加密效率是50%，因为密文大小是明文的两倍。vElGamal密码体制的破译难度同Diffie-Hellman的方法,即基于DLP，离散对数问题，最快的算法需要T=exp(ln(p)lnln(p)1/2)次运算。ElGamal Cryptosystem2024/7/7现代密码学理论与实践-1020/59例：P=17,=3,xA=2,xB=5,m=11,m从A发送到B,A选择k=7.求：密文(c1,c2)并解密加密：YA=xA mod P=32 mod 17=9YB=xB mod P=35 mod 17=5K=(YB)k mod P=57 mod 17=10c1=k mod P=37 mod 17=11c2=mK mod P=10 x11 mod 17=8所以，密文C=(c1,c2)=(11,8)解密：K=c1xB mod P=115 mod 17=10c2=mK mod P=10m mod 17=8m=c2/K mod P=c2K-1 mod PK K-1 mod P=1，即10 K-1 mod 17=1，得K-1=12所以，明文m=c2K-1 mod P=8x12 mod 17=11ElGamal Cryptosystem2024/7/7现代密码学理论与实践-1021/5910.3 椭圆曲线算术v椭圆曲线密码编码学ECC使用椭圆曲线密码系统ECC,可以达到如RSA,D-H同样的安全但位数要小得多。v椭圆曲线并非椭圆,它指的是由Weierstrass威尔斯特拉斯方程所确定的平面曲线：y2+axy+by=x3+cx2+dx+e一般形式：y2=x3+ax+b满足上述方程的数偶(x,y)称为椭圆曲线E上的点。同时定义无穷点(point at infinity)或零点(zero point)的O。2024/7/7现代密码学理论与实践-1022/59实数域上的椭圆曲线v一般形式v具有不同根的条件v例子2024/7/7现代密码学理论与实践-1023/59椭圆曲线举例 (a)y2=x3-x (b)y2=x3+x+12024/7/7现代密码学理论与实践-1024/59单位元和逆元v逆元：P(x,-y)=P(x,y)关于X轴对称点。vP+P=Ov单位元 P+O=P2024/7/7现代密码学理论与实践-1025/59v如果椭圆曲线上的三个点处于一条直线上,那么它们的和为O。加法规则：1.O是加法的单位元(additive identity),O=O；对于椭圆曲线上的任一点P,有 P+O=P。2.一条垂直线与曲线相交于P1=(x,y)和P2=(x,y),也相交于无穷点O,有P1+P2+O=O和 P1=P2。3.对具有不同的x坐标的Q和R相加,在它们之间画一条直线求出第三个交点P1,这种交点是唯一的。因为Q+R+P1=O,因此Q+R=P14.对点Q加倍,画一切线求出另一交点S,则Q+Q=2Q=S5.一条椭圆曲线上的一点P被一个正整数k相乘的乘法被定义为k个P的相加椭圆曲线上的形式加法2024/7/7现代密码学理论与实践-1026/59椭圆曲线的加法v椭圆曲线上的点集及其上的加法操作构成一个群v点集椭圆曲线上的所 有点和无穷点v操作点加法 R=P+Q（或 R=P*Q）2024/7/7现代密码学理论与实践-1027/59点的累加v二倍过点P(x,y)的切线R=P+P2024/7/7现代密码学理论与实践-1028/59反复累加kP=P+P或写为：2024/7/7现代密码学理论与实践-1029/59数学描述v直线g:y=sx+y0 其中：与曲线相交：(sx+y0)2=x3+ax+bR点坐标：2024/7/7现代密码学理论与实践-1030/59数学描述2024/7/7现代密码学理论与实践-1031/59有限域上的椭圆曲线Finite Elliptic Curvesv可以将椭圆曲线定义于有限域GFP上 y2=x3+ax+b mod pp是一个素数,并且0,1,p-1是模p加的交换群(Abelian)；1,p-1是模p乘的交换群v椭圆曲线密码系统采用变量和系数有限的曲线来实现2024/7/7现代密码学理论与实践-1032/59v定义在Zp上的素曲线(prime curves)Ep(a,b)使用三次方程，变量和系数取自集合0,1,p-1,模p运算最适合用软件实现v定义在GF(2n)上的二元曲线E2n(a,b)变量和系数取自GF(2n),模素多项式(二进制多项式)最适合硬件实现vEp(a,b)表示满足下列条件的模p椭圆群,群中元素(x,y)是满足如下方程的小于p的非负整数另外加上无穷点O：y2 mod p=(x3+ax+b)mod p.v例如：p=23,有4a3+27b2=4x13+27x12 mod 23=80,满足条件(这里a,b=1)两种有限域上的椭圆曲线2024/7/7现代密码学理论与实践-1033/59椭圆曲线E23(1,1)上的点v对于每个满足0 xp的x,计算y2=x3+x+1 mod pv对于上一步得到的每个结果确定它是否有一个模p的平方根,如果没有,在E23(1,1)中就没有具有这个x值的点；如果有,就有两个满足平方根运算的y值(除非这个值是单个的y值0)。这些(x,y)就是E23(1,1)上的点2024/7/7现代密码学理论与实践-1034/59椭圆曲线E23(1,1)上的点2024/7/7现代密码学理论与实践-1035/59椭圆曲线上的点v在GF11上找出满足椭圆曲线方程的点P(x,y):y2=x3+x+6 mod 11v有12个点,加上无穷远点O共有n=13个元素2024/7/7现代密码学理论与实践-1036/59椭圆曲线点加运算v将y2=x3+x+6 mod 11上的点(2,4)反复累加v计算2P=P+P（或记为 P2=P*P)v计算3P=P+P+P=2P+P（或记为P3=P*P*P=P2*P)v所有运算均在GF11上进行2024/7/7现代密码学理论与实践-1037/59椭圆曲线点加运算v取P(2,4),计算2P=P+P（或记为P2=P*P)v再计算3P=P+P+P=2P+P（或记为P3=P2*P)2024/7/7现代密码学理论与实践-1038/59GF(2n)上的椭圆曲线v有限域GF(2n)由2n个元素及定义在多项式上的加法和乘法运算组成v给定某n,对于GF(2n)上的椭圆曲线，使用变元和系数均在GF(2n)上取值的三次方程，且利用GF(2n)中的算术运算规则来进行计算v可以证明，GF(2n)上适合椭圆曲线密码应用的三次方程与Zp上的三次方程有所不同，形为 y2+xy=x3+ax2+b 其中变元x和y以及系数a和b是GF(2n)中的元素，计算在GF(2n)中进行2024/7/7现代密码学理论与实践-1039/59GF(2n)上的椭圆曲线v考虑所有整数对(x,y)和无穷远点O组成的集合E2n(a,b)v例如，使用不可约多项式f(x)=x4+x+1(10011)定义的有限域GF(24)，其生成元g满足f(g)=0,即g1=0010,g4=g+1,或二进制0011,g5=(g4)(g)=g2+g=0110g0=0001g4=0011g8=0101g12=1111g1=0010g5=0110g9=1010g13=1101g2=0100g6=1100g10=0111g14=1001g3=1000g7=1011g11=1110g15=00012024/7/7现代密码学理论与实践-1040/59GF(2n)上的椭圆曲线v例如，考虑椭圆曲线y2+xy=x3+g4x2+1,a=g4=0011,b=g0=0001,满足该方程的一个点(x,y)为(g5,g3)：(g3)2+(g5)(g3)=(g5)3+(g4)(g5)2+1g6+g8=g15+g14+11100+0101=0001+1001+00011001=10012024/7/7现代密码学理论与实践-1041/592024/7/7现代密码学理论与实践-1042/59v大多数公开密钥密码系统如RSA,D-H都使用具有非常大数目的整数或多项式，计算量大，密钥和报文存储量也极大。使用椭圆曲线密码系统ECC，可以达到同样安全但位数要小得多。vECC的加类似于模乘，ECC的重复加类似于模指数vECC需要有对应于DLP的难解问题Q=kP,Q,P属于Ep(a,b),kP给定k,P,容易计算Q=kP但是给定Q,P,求k难这就是椭圆曲线对数问题10.4 椭圆曲线密码学2024/7/7现代密码学理论与实践-1043/59椭圆曲线对数问题v给定曲线 y2=x3+ax+b mod p 以及其上一点P，我们可以 通过连续自加k-1次计算 Q=kP,(或Q=Pk)。目前存在这样的快速算法。v问题：当Q已知时能否计算k?v答案：这是一个被称为椭圆 曲线对数的难题。2024/7/7现代密码学理论与实践-1044/59椭圆曲线密码学v例：E23(9,17),即y2=(x3+9x+7)mod 23,以P=(16,5)为底的Q=(4,5)的离散对数k为多少？v可以通过穷举攻击方法，多次计算P的倍数直至找到Q为止，这样P=(16,5);2P=(20,20);3P=(14,14);4P=(19,20);5P=(13,10);6P=(7,3);7P=(8,7);8P=(12,17);9P=(4,5)v所以,以P=(16,5)为底的Q=(4,5)的离散对数k为9v实际应用中，k的值非常大，穷举攻击不可行2024/7/7现代密码学理论与实践-1045/59椭圆曲线密码学v椭圆曲线密码系统的定义域标识：定义椭圆曲线采用的有限域椭圆曲线：系数a和b基准点(base)：指定的椭圆曲线上的点P阶(order)：P点的阶n，使得nP=Ov椭圆曲线公钥系统EP(a,b),GFPBase point P(x,y)选择 e 作为私有密钥 公开密钥为Q=eP2024/7/7现代密码学理论与实践-1046/5910.4.1Diffie-Hellman的椭圆曲线实现v选定椭圆曲线上一点G vA、B分别随机选取a,b并保密vA QA=aG B QB=bGvA:Q=a(QB)=abG vB:Q=b(QA)=baG=abG 2024/7/7现代密码学理论与实践-1047/592024/7/7现代密码学理论与实践-1048/59v类似于D-H，ECC也可以实现密钥交换v用户选择合适的ECC,Ep(a,b)v选择基点G=(x1,y1),满足nG=O的最小n是一个大素数vA和B之间的密钥交换如下A和B选择私钥nAn,nBn计算公钥PA=nAG,PB=nBGA与B交换PA 和 PB计算共享密钥K=nAPB=nBPA,因为K=nAnBG，所以这两个密钥是一样的。ECC与Diffie-Hellman密钥交换的类比2024/7/7现代密码学理论与实践-1049/59用ECC实现Diffie-Hellman密钥交换v例如Ep(0,-4),即 y2=x3-4,G=(2,2),p=211,n=240;计算 240G=OnA=121,PA=121(2,2)=(115,48)nB=203,PB=203(2,2)=(130,203)K=121(130,203)=203(115,48)=(161,69)2024/7/7现代密码学理论与实践-1050/59Massey-Omura公钥体制v在GF(q)上,用户A的加密、解密密钥为eA,dA gcd(eA,q-1)=1,eAdA=1 mod(q-1)v同样,用户B的加密、解密密钥为eB,dB gcd(eB,q-1)=1,eBdB=1 mod(q-1)vA将消息m发送给B:A meA B meA eB (meA eB)da =meB B:(meB)dB=m 2024/7/7现代密码学理论与实践-1051/59Massey-Omura在椭圆曲线上实现vm嵌入椭圆曲线上的点Pmvn：椭圆曲线上的点数(已知大素数)v用户随机选择e：1en,gcd(e,n)=1,ed=1 mod nvA将消息m发送给B：A eAPm B eBeAPm dA(eBeAPm)=eBPm B:dB(eBPm)=Pm2024/7/7现代密码学理论与实践-1052/59ElGamal算法在椭圆曲线上实现vE(a,b),base point G 属于EvA选择a并保密,0an，n为G的阶(order)aG公开vB向A发送消息m B将m嵌入点Pm，选择随机数k,A (kG,Pm+k(aG)B A：Pm=Pm+k(aG)a(kG)本质上：A,B共享秘密akG2024/7/7现代密码学理论与实践-1053/59v首先将明文消息m编码为x-y的点Pm,点Pm就是要进行加密和解密的,不能简单地把消息编码为点的x坐标或y坐标，因为并不是所有的坐标都在Eq(a,b)中。v类似于D-H密钥交换，加解密系统也需要点G和椭圆群Eq(a,b)这些参数。v用户A选择私钥nAn,并产生公钥PA=nAG v用户B选择私钥nBn,并产生公钥PB=nBG vAB:Pm vA随机选择一个正整数k,加密点Pm产生密文：Cm=kG,Pm+kPBvB解密Cm,计算：Pm+kPBnB(kG)=Pm+k(nBG)nB(kG)=Pm10.4.2 椭圆曲线加/解密2024/7/7现代密码学理论与实践-1054/59ECC Encryption/Decryptionv例如,Ep(-1,188),即y2=x3-x+188,G=(0,376),p=751A要向B发送消息 Pm=(562,201)A首先随机选择k=386,并获得B的公钥PB=(201,5)计算kG=386(0,376)=(676,558)Pm+kPB=(562,201)+386(201,5)=(385,328)这样,密文即为 Cm=kG,Pm+kPB=(676,558),(385,328)vB要解密Pm+kPBnB(kG)=Pm+k(nBG)nB(kG)=Pm2024/7/7现代密码学理论与实践-1055/59vECC的安全性是建立在由kP和P确定k的难度之上的，即椭圆曲线对数问题elliptic curve logarithm problem，Pollard rho方法是已知求椭圆曲线对数问题的最快方法。v相比FAC，可以使用比RSA短得多的密钥v在密钥长度相同时，ECC与RSA所执行的计算量也差不多v与具有同等安全性的RSA相比，由于ECC使用的密钥更短，所以ECC所需的计算量比RSA少椭圆曲线密码的安全性2024/7/7现代密码学理论与实践-1056/59椭圆曲线密码与RSA的效率比较2024/7/7现代密码学理论与实践-1057/59Equivalent Cryptographic Strength2024/7/7现代密码学理论与实践-1058/59第10章习题v第四版：1,7,8,10,11,12,13,16v提示：16题可以利用如下列表vDue:Nov.20,2012 2G=(5,2)3G=(8,3)4G=(10,2)5G=(3,6)6G=(7,9)7G=(7,2)8G=(3,5)9G=(10,9)10G=(8,8)11G=(5,9)12G=(2,4)13G=(2,7)
展开阅读全文