第六讲和与密钥管理

第六讲和与密钥管理第一页，共六十二页，2022年，8月28日内容ElGamalECCKeyManagement第二页，共六十二页，2022年，8月28日ELGamal公钥密码1、基本情况：①ELGamal密码建立在离散对数的困难性之上。②RSA密码建立在大合数分解的困难性之上。第三页，共六十二页，2022年，8月28日2、算法：准备：随机地选择一个大素数p，且要求p-1有大素数因子。再选择一个模p的本原元α。将p和α公开。⑴密钥生成用户随机地选择一个整数d作为自己的秘密的解密钥，1≤d≤p-2。计算y=αdmodp，取y为自己的公开的加密钥。由公开钥y

计算秘密钥d，必须求解离散对数，而这是极困难的。第四页，共六十二页，2022年，8月28日⑵加密将明文消息M（0≤M≤p-1)加密成密文的过程如下：①随机地选取一个整数k，1≤k≤p-2。②计算：U＝ykmodp；C1＝αkmodp；C2＝UMmodp；③取C＝（C1，C2）作为密文。第五页，共六十二页，2022年，8月28日⑶解密将密文（C1，C2）解密的过程如下：①计算V＝C1dmodp；②计算M＝C2

V-1modp。第六页，共六十二页，2022年，8月28日解密的可还原性可证明如下：C2

V-1modp＝(UM)V-1modp＝UM（C1d）-1modp＝UM（（αk）d）-1modp＝UM（（αd）k）-1modp＝UM（（y）k）-1modp＝UM（U）-1modp＝Mmodp第七页，共六十二页，2022年，8月28日⑷安全性由于ELGamal密码的安全性建立在GF（p）离散对数的困难性之上，而目前尚无求解GF（p）离散对数的有效算法，所以在p足够大时ELGamal密码是安全的。p应为150位以上的十进制数，而且p-1应有大素因子。加密和签名所使用的k必须是一次性的。第八页，共六十二页，2022年，8月28日如果k不是一次性的，时间长了就可能被攻击者获得。又因y是公开密钥，攻击者自然知道。于是攻击者就可以根据U＝ykmodp计算出U，进而利用Euclid算法求出U－1。又因为攻击者可以获得密文C2，于是可根据式C2＝UMmodp通过计算U－1C2得到明文M。设用同一个k加密两个不同的明文M和M’，相应的密文为（C1，C2）和（C1’，C2’）。因为C2∕C2’＝M∕M’，如果攻击者知道M，则很容易求出M’。第九页，共六十二页，2022年，8月28日⑸ELGamal密码的应用由于ELGamal密码的安全性得到世界公认，所以得到广泛的应用。著名的美国数字签名标准DSS，采用了ELGamal密码的一种变形。为了适应不同的应用，人们在应用中总结出多种不同的ELGamal密码的变形。第十页，共六十二页，2022年，8月28日1、椭圆曲线密码的一般情况受ELGamal密码启发，在其它离散对数问题难解的群中，同样可以构成ELGamal密码。于是人们开始寻找其它离散问题难解的群。研究发现，有限域GF（p）上的椭圆曲线的解点构成交换群，而且离散对数问题是难解的。于是可在此群上建立ELGamal密码，并称为椭圆曲线密码。椭圆曲线密码ECC第十一页，共六十二页，2022年，8月28日椭圆曲线密码已成为除RSA密码之外呼声最高的公钥密码之一。它密钥短、签名短，软件实现规模小、硬件实现电路省电。普遍认为，160位长的椭圆曲线密码的安全性相当于1024位的RSA密码，而且运算速度也较快。一些国际标准化组织已把椭圆曲线密码作为新的信息安全标准。如，IEEEP1363/D4，ANSIF9.62，ANSIF9.63等标准，分别规范了椭圆曲线密码在Internet协议安全、电子商务、Web服务器、空间通信、移动通信、智能卡等方面的应用。第十二页，共六十二页，2022年，8月28日第十三页，共六十二页，2022年，8月28日第十四页，共六十二页，2022年，8月28日第十五页，共六十二页，2022年，8月28日第十六页，共六十二页，2022年，8月28日椭圆曲线一般来讲，椭圆曲线的曲线方程是以下形式的三次方程：y2+axy+by=x3+cx2+dx+e其中a，b，c，d，e是满足某些简单条件的实数。定义中包括一个称为无穷点的元素，记为O。下图是椭圆曲线的两个例子。第十七页，共六十二页，2022年，8月28日椭圆曲线的两个例子第十八页，共六十二页，2022年，8月28日椭圆曲线上的加法运算定义如下：如果其上的3个点位于同一直线上，那么它们的和为O。进一步可如下定义椭圆曲线上的加法律（加法法则）：①O为加法单位元，即对椭圆曲线上任一点P，有P+O=P。②设P1=(x,y)是椭圆曲线上的一点（如上图），它的加法逆元定义为P2=-P1=(x,-y)。这是因为P1、P2的连线延长到无穷远时，得到椭圆曲线上的另一点O，即椭圆曲线上的3点P1、P2，O共线，所以P1+P2+O=O，P1+P2=O，即P2=-P1。由O+O=O，还可得O=-O第十九页，共六十二页，2022年，8月28日③设Q和R是椭圆曲线上x坐标不同的两点，Q+R的定义如下：画一条通过Q、R的直线与椭圆曲线交于P1（这一交点是惟一的，除非所做的直线是Q点或R点的切线，此时分别取P1=Q和P1=R）。由Q+R+P1=O得Q+R=-P1。④点Q的倍数定义如下：在Q点做椭圆曲线的一条切线，设切线与椭圆曲线交于点S，定义2Q=Q+Q=-S。类似地可定义3Q=Q+Q+Q+，…，等。以上定义的加法具有加法运算的一般性质，如交换律、结合律等。第二十页，共六十二页，2022年，8月28日第二十一页，共六十二页，2022年，8月28日第二十二页，共六十二页，2022年，8月28日第二十三页，共六十二页，2022年，8月28日第二十四页，共六十二页，2022年，8月28日密码中普遍采用的是有限域上的椭圆曲线，有限域上的椭圆曲线是指曲线方程定义式中，所有系数都是某一有限域GF(p)中的元素（其中p为一大素数）。其中最为常用的是由方程y2≡x3+ax+b(modp)(a,b∈GF(p),4a3+27b2(modp)≠0) 定义的曲线。设Ep(a,b)表示所定义的椭圆曲线上的点集{(x,y)|0≤x<p,0≤y<p，且x,y均为整数}并上无穷远点O有限域上的椭圆曲线第二十五页，共六十二页，2022年，8月28日Ep(a,b)上的加法定义如下：设P，Q∈Ep(a,b)，则①P+O=P。②如果P=(x,y)，那么(x,y)+(x,-y)=O，即(x,-y)是P的加法逆元，表示为-P。由Ep(a,b)的产生方式知，-P也是Ep(a,b)中的点，如下例：P=(13,7)∈E23(1,1)，-P=(13,-7)，而-7mod23≡16，所以-P=(13,16)，也在E23(1,1)中。第二十六页，共六十二页，2022年，8月28日③设P=(x1,y1)，Q=(x2,y2)，P≠-Q，则P+Q=(x3,y3)由以下规则确定： x3≡λ2-x1-x2(modp) y3≡λ(x1-x3)-y1(modp)其中第二十七页，共六十二页，2022年，8月28日倍点运算仍定义为重复加法，如4P=P+P+P+P。模除法运算：a/bmodn乘以b的逆元:a/b=a.b-1modn如果n是素数,b-1modn存在b.b-1=1modn第二十八页，共六十二页，2022年，8月28日例1.以E23(1,1)为例，设P=(3,10)，Q=(9,7)，则所以P+Q=（17,20），仍为E23(1,1)中的点。第二十九页，共六十二页，2022年，8月28日E23(1,1)第三十页，共六十二页，2022年，8月28日E23(1,1)第三十一页，共六十二页，2022年，8月28日若求2P则所以2P=(7,12)。第三十二页，共六十二页，2022年，8月28日例2：取p=11，椭圆曲线y2=x3+x+6。由于p较小，使GF(p)也较小，故可以利用穷举的方法根据y2=x3+x+6mod11求出所有解点。

第三十三页，共六十二页，2022年，8月28日

xx3+x+6mod11是否模11平方剩余y06No18No25Yes4,733Yes5,648No54Yes2,968No74Yes2,989Yes3,897No104Yes2,9第三十四页，共六十二页，2022年，8月28日G＝（2，7），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）。第三十五页，共六十二页，2022年，8月28日从例子可以看出，加法运算在E23(1,1)中是封闭的，且能验证还满足交换律。对一般的Ep(a,b)，可证其上的加法运算是封闭的、满足交换律，同样还能证明其上的加法逆元运算也是封闭的，所以Ep(a,b)是一个加法交换群。除了GF(p)上的椭圆曲线外,还有定义在GF(2m)上的椭圆曲线。这两种椭圆曲线都可以构成安全的椭圆曲线密码。第三十六页，共六十二页，2022年，8月28日为使用椭圆曲线构造密码体制，需要找出椭圆曲线上的数学困难问题。①椭圆曲线群上的离散对数问题在例2中椭圆曲线上的解点所构成的交换群恰好是循环群，但是一般并不一定。于是我们希望从中找出一个循环子群E1。可以证明当循环子群E1的阶∣E1∣是足够大的素数时，这个循环子群中的离散对数问题是困难的。椭圆曲线密码第三十七页，共六十二页，2022年，8月28日设P和Q是椭圆曲线上的两个解点，t为一正整数，且0≤t<∣E1∣。对于给定的P和t，计算tP＝Q是容易的。但若已知P和Q点，要计算出t则是极困难的。这便是椭圆曲线群上的离散对数问题，简记为ECDLP(EllipticCurveDiscreteLogarithmProblem)。除了几类特殊的椭圆曲线外，对于一般ECDLP目前尚没有找到有效的求解方法。于是可以在这个循环子群E1中建立任何基于离散对数困难性的密码，并称这个密码为椭圆曲线密码。第三十八页，共六十二页，2022年，8月28日②椭圆曲线密码T=<p,a,b,G,n,h>p,a,b,G,n是公开的参数；p为大于3素数，p确定了有限域GF（p）；元素a,b∈GF(p),a和b确定了椭圆曲线；G为循环子群E1的生成元点，n为素数且为生成元G的阶，G和n确定了循环子群E1；h=|E|/n，并称为余因子，h将交换群E和循环子群联系起来。第三十九页，共六十二页，2022年，8月28日②椭圆曲线密码密钥：用户的私钥定义为一个随机数d，d∈{0,1,2,···,n-1}。用户的公开钥定义为Q点，Q=dG。第四十页，共六十二页，2022年，8月28日设d为用户私钥，Q为公钥，将Q存入PKDB。设要加密的明文数据为M，将M划分为一些较小的数据块，M=[m1，m2，···，mt]，其中0≤mi<n。第四十一页，共六十二页，2022年，8月28日加密过程：A把M加密发给BA查PKDB，查到B的公开密钥QB。A选择一个随机数k，且k∈{0,1,2,···,n-1}。A计算点X1：（x1，y1）=kG。A计算点X2：（x2，y2）=kQB，如果分量x2=O，则转2)。A计算密文C=mix2modn。A发送加密数据（X1，C）给B。第四十二页，共六十二页，2022年，8月28日解密过程：用户B用自己的私钥dB求出点X2：dBX1=dB（kG）=k(dBG)=kQB

=X2：（x2，y2）对C解密，得到明文mi=Cx2–1modn。第四十三页，共六十二页，2022年，8月28日椭圆曲线密码体制的优点安全性高密钥量小实现相同安全性条件下，ECC所需密钥量远下雨有限域上离散对数问题的公钥体制的密钥量灵活性好通过改变参数可以获得不同的曲线，具有丰富的群结构和多选择性第四十四页，共六十二页，2022年，8月28日RSA/DSA5127681024204821000ECC106132160211600第四十五页，共六十二页，2022年，8月28日KeyManagement

public-keyencryptionhelpsaddresskeydistributionproblemshavetwoaspectsofthis:

distributionofpublickeys

useofpublic-keyencryptiontodistributesecretkeys第四十六页，共六十二页，2022年，8月28日DistributionofPublicKeysSeveraltechniquescanbegroupedintothefollowinggeneralschemes:publicannouncementpubliclyavailabledirectorypublic-keyauthoritypublic-keycertificates第四十七页，共六十二页，2022年，8月28日Public-KeyAuthority

improvesecuritybytighteningcontroloverdistributionofkeysfromdirectory

haspropertiesofdirectory

andrequiresuserstoknowpublickeyforthedirectory

thenusersinteractwithdirectorytoobtainanydesiredpublickeysecurely

doesrequirereal-timeaccesstodirectorywhenkeysareneeded第四十八页，共六十二页，2022年，8月28日Figure10.3

PublicKeydistributionScenario第四十九页，共六十二页，2022年，8月28日Public-KeyCertificates

certificatesallowkeyexchangewithoutreal-timeaccesstopublic-keyauthority

acertificatebindsidentitytopublickeyusuallywithotherinfosuchasperiodofvalidity,rightsofuseetcwithallcontentssignedbyatrustedPublic-KeyorCertificateAuthority(CA)canbeverifiedbyanyonewhoknowsthepublic-keyauthoritiespublic-key第五十页，共六十二页，2022年，8月28日Figure10.4

ExchangeofPublicKeyCertificates第五十一页，共六十二页，2022年，8月28日Public-KeyDistributionofSecretKeys

usepreviousmethodstoobtainpublic-key

canuseforsecrecyorauthentication

butpublic-keyalgorithmsareslow

sousuallywanttouseprivate-keyencryptiontoprotectmessagecontents

henceneedasessionkey

haveseveralalternativesfornegotiatingasuitablesession第五十二页，共六十二页，2022年，8月28日SecretKeyDistributionwithConfidentialityandAuthentication

proposedbyNeedhamandSchroederin1978Protectionagainstbothactiveandpassiveattacks第五十三页，共六十二页，2022年，8月28日Figure10.6PublicKeyDistributionofSecretKeyswithConfidentialityandAuthentication第五十四页，共六十二页，2022年，8月28日firstpublic-keytypeschemeproposedbyDiffie&Hellmanin1976alongwiththeexpositionofpublickeyconceptsnote:nowknowthatWilliamson(UK)secretlyproposedtheconceptin1970isapracticalmethodforpublicexchangeofasecretkey

usedinanumberofcommercialproductsDiffie-HellmanKeyExchange第五十五页，共六十二页，2022年，8月28日apublic-keydistributionschemecannotbeusedtoexchangeanarbitrarymessageratheritcanestablishacommonkeyknown