9 密码学新技术

现代密码学概论7/29/202610:56AM1江苏大学计算机科学与通信工程学院主讲人：潘森杉

第9讲密码学新技术

椭圆曲线密码介绍1985年Miller,Koblitz独立提出y2+axy+by=x3+cx2+dx+e曲线上的点连同无穷远点O的集合运算定义：若曲线三点在一条直线上,则其和为OO用作加法的单位：O=-O;P+O=P一条竖直线交X轴两点P1、P2，则P1+P2+O=O，于是P1=-P2如果两个点Q和R的X轴不同，则画一连线，得到第三点P1，则Q+R+P1=O，即Q+R=-P12倍，一个点Q的两倍是，找到它的切线与曲线的另一个交点S，于是Q+Q=2Q=-S椭圆曲线密码示意图椭圆曲线用于加密找到一个难题：考虑等式Q=kP，其中Q、P属于Ep(a,b)，k<p已知k和P，计算Q，是容易的已知Q和P，计算k，是困难的选择Ep(a,b)的元素G,使得G的阶n是一个大素数G的阶是指满足nG=O的最小n值秘密选择整数r，计算P=rG，然后公开(p,a,b,G,P)，P为公钥保密r加密M：先把消息M变换成为Ep(a,b)中一个点Pm然后，选择随机数k，计算密文Cm={kG,Pm+kP)如果k使得kG或者kP为O，则要重新选择k.解密Cm:(Pm+kP)-r(kG)=Pm+krG-rkG=Pm加密信息有扩张有限域上椭圆曲线有限域上椭圆曲线y2

x3+ax+bmodp p是奇素数,且4a3+27b2

0modp针对所有的0<=x<p，可以求出有效的y，得到曲线上的点(x,y)，其中x,y<p。记为Ep(a,b)Ep(a,b)中也包括O加法公式:P+O=P如果P=(x,y)，则P+(x,-y)=O，(x,-y)点是P的负点，记为-P。而且(x,-y)也在Ep(a,b)中如果P=(x1,y1)，Q=(x2,y2)，则P+Q=(x3,y3)为

x3=

2-x1-x2(modp)

y3=

(x1-x3)-y1(modp)

其中，如果PQ，则=(y2-y1)/(x2-x1)

如果P=Q，则=(3x12+a)/(2y1)椭圆曲线密码的安全性难点:从P和kP获得k对椭圆曲线研究的时间短椭圆曲线要求密钥长度短,速度快对比:ECCRSA

*Pollardrho分析方法KeysizeMIPS-Yrs1503.8

10102057.1

10182341.6

10285123

1047682

10810243

101112801

101415363

101620483

1020模素数的椭圆曲线定义素数p>3.E={(x,y)∈Zp×Zp|y2≡x3+ax+b(modp)，}∪{O}构成Zp上的椭圆曲线y2=x3+ax+b。其中4a3+27b2≠0modp。E上加法定义为：P+O=O+P=P(E,+)构成一个Abel群例：E是Z11上椭圆曲线y2=x3+x+6,求E。解：对每个x∈Z11,x3+x+6mod11,然后求y。根据Euler准则，测试z=x3+x+6是否为二次剩余。对素数p≡3(mod4)，二次剩余z的平方根为±z(11+1)/4mod11=±z3mod11xx3+x+6mod11是二次剩余吗y06否18否25是4，733是5，648否54是2，968否74是2，989是3，897否104是2，9E有13个点E≌Z13P=(2,7),求kP2P=P+P=(x3,y3)=(5,2)=(3·22+1)(2·7)-1mod11=2·3-1mod11=2·4mod11=8x3=82-2-2mod11=5y3=8(2-5)-7mod11=23P=(5,2)+(2,7)=(x4,y4)=(8,3)=(7-2)(2-5)-1mod11=5·8-1mod11=5·7mod11=2x3=22-5-2mod11=8y3=2(5-8)-2mod11=3

P=(2,7),2P=(5,2),3P=(8,3)依次得，4P=(10,2),5P=(3,6),6P=(7,9)7P=(7,2),8P=(3,5),9P=(10,9),10P=(8,8),11P=(5,9),12P=(2,4)例：

=(2,7)，Bob的私钥7，=7

=(7,2)

加密：ek(x,k)=(k(2,7),x+k(7,2))，x∈E,0≤k≤12解密：dk(y1,y2)=y2-7y1明文x=(10,9)，随机选k=3y1=3(2,7)=(8,3)y2=(10,9)+3(7,2)=(10,9)+(3,5)=(10,2)密文y=((8,3),(10,2))x=(10,2)-7(8,3)=(10,2)-(3,5)=(10,2)+(3,6)=(10,9)例：域F7上的椭圆曲线y2=x3-2x-3，P=(3,2)是其上的一点，求：10P。解：2P=(3,2)+(3,2)=(2,6)3P=P+2P=(3,2)+(2,6)=(4,2)4P=P+3P=(0,5)5P=(5,0)6P=(0,2)7P=(4,5)8P=(2,1)9P=(3,5)10P=P+9P=(3,2)+(3,5)=O椭圆曲线上的密码在椭圆曲线上构成的Abel群Ep(a,b)上考虑Q=kP，P,Q∈E，k<p.由k,P易求Q，但由P、Q求k则是困难的，称为椭圆曲线上的离散对数问题。Diffie-Hellman密钥交换取素数p≈2180,a,b，得椭圆曲线及E

取E的一个生成元G(x1,y1),要求G的阶是一个非常大的素数，公开G，E。

A与B间密钥交换：A选一个小于n的数nA作为秘密钥，由PA=nAG产生E上的点PA作为公钥；B类似选取秘钥nB，公钥PB；A，B分别由K=nAPB和K=nBPA产生双方共享的秘密密钥。ElGamal密码体制Ep(a,b)，将明文m嵌入到曲线上得Pm，对Pm加密取生成元G，公开Ep(a,b),GA选nA作为秘钥，以PA=nAG作为公钥B想向A发送消息Pm，可选随机数k，产生密文Cm=(kG,Pm+kPA)=(y1,y2)A收到后解密

Pm=y2-nAy1(=(Pm+kPA)-nAkG=Pm+k(nAG)-nAkG)攻击者想由Cm得Pm，必须知道k，只有通过G，kG，求k.同基于有限域上ElGamal密码体制比较，ECC具有优点：安全性高，密钥量小，灵活性好双线性对双线性映射定义：设G1是由P生成的循环加法群，其阶数为素数q，G2是一个阶为q的循环乘法群。双线性映射是指具有下列性质的映射e：G1×G1→G2；(1)双线性。对所有的P,Q∈G1和a,b∈Zq*，e(aP,bQ)=e(abP,Q)=e(P,abQ)=e(P,Q)ab(2)非退化。存在一个P∈G1，满足e(P,P)≠1。(3)可计算。对P,Q∈G1，存在一个有效的算法计算e(P,Q)。计算机科学系15双线性对的密码应用代理签名盲签名先将要隐蔽的文件放进信封里，当文件在一个信封中时，任何人都不能读它。对文件签名就是通过在信封中放一张复写纸，当签名者在信封上签名时，他的签名便会透过复写纸签到文件上。盲签名是一种特殊的数字签名，它与通常的数字签名的不同之处在于，签名者并不知道他所要签发文件的具体内容。正是这一点，使得盲签名这种技术可广泛应用于许多领域，如电子投票系统和电子现金系统等。群签名在群签名中，群成员可以用群体的定义进行匿名签名，验证时能够验证签名者为群成员所签，而不能确定具体成员信息，称这个性质为群签名的匿名性。与其他数字签名一样，群签名是可以公开验证的，而且可以只用单个群公钥进行验证。其次，群签名的匿名性是相对的，当出现争议时，可以由群管理员打开签名，揭示签名人身份，使得签名人不得不承认其签名，称这种性质为群签名的可追踪性。计算机科学系16量子计算机大数分解、离散对数问题在量子计算机下已不困难2000个Qubit的量子计算机能在1秒内分解1个129位数分解成64位素数×65位素数Grover算法、Shor算法量子计算机上，Shor算法分解整数N只要多项式时间O((logN)3)RSA、ECC安全性受到威胁计算机科学系17加拿大D-Wave公司研发的量子计算机量子密码能实现无条件安全（1999年被提出）利用信息载体（例如光子等粒子）的量子特性，以量子态作为符号的密码1984年，量子密钥分配概