第六讲 Elgaml和ECC与密钥管理.ppt

1、公钥密码体制（2）,计算机学院 孟博 ,内 容,ElGamal ECC Key Management,ELGamal公钥密码,1、基本情况： ELGamal密码建立在离散对数的困难性之上。 RSA密码建立在大合数分解的困难性之上。,2、算法： 准备：随机地选择一个大素数p，且要求p-1有大素数因子。再选择一个模p的本原元。将p和公开。 密钥生成 用户随机地选择一个整数d作为自己的秘密的解密钥， 1dp-2 。 计算y=d mod p，取y为自己的公开的加密钥。 由公开钥y 计算秘密钥d，必须求解离散对数，而这是极困难的。, 加密 将明文消息M（0Mp-1)加密成密文的过程如下： 随机地选取一个

2、整数k，1kp-2。 计算： U y k mod p； C1k mod p； C2UM mod p； 取 C（C1 ，C2）作为密文。, 解密 将密文（C1 ，C2）解密的过程如下： 计算VC1 d mod p； 计算MC2 V -1 mod p。,解密的可还原性可证明如下： C2 V-1 mod p (UM)V-1 mod p UM（C1 d）-1 mod p UM（k）d）-1 mod p UM（d）k）-1 mod p UM（y）k）-1 mod p UM（U）-1 mod p M mod p, 安全性 由于ELGamal密码的安全性建立在GF（p）离散对数的困难性之上，而目前尚无求解G

3、F（p）离散对数的有效算法，所以在p足够大时ELGamal密码是安全的。 p应为150位以上的十进制数，而且p-1应有大素因子。 加密和签名所使用的k必须是一次性的。,如果k不是一次性的，时间长了就可能被攻击者获得。又因y是公开密钥，攻击者自然知道。于是攻击者就可以根据Uy k mod p计算出U，进而利用Euclid算法求出U1。又因为攻击者可以获得密文C2，于是可根据式C2UM mod p通过计算U1C2得到明文M。 设用同一个k加密两个不同的明文M和M，相应的密文为（C1 ，C2）和（C1，C2）。因为C2C2 MM，如果攻击者知道M，则很容易求出M。, ELGamal密码的应用 由于E

4、LGamal密码的安全性得到世界公认，所以得到广泛的应用。著名的美国数字签名标准DSS，采用了ELGamal密码的一种变形。 为了适应不同的应用，人们在应用中总结出多种不同的ELGamal密码的变形。,1、椭圆曲线密码的一般情况 受ELGamal密码启发，在其它离散对数问题难解的群中，同样可以构成ELGamal密码。于是人们开始寻找其它离散问题难解的群。 研究发现，有限域GF（p）上的椭圆曲线的解点构成交换群，而且离散对数问题是难解的。于是可在此群上建立ELGamal密码，并称为椭圆曲线密码。,椭圆曲线密码ECC,椭圆曲线密码已成为除RSA密码之外呼声最高的公钥密码之一。它密钥短、签名短，软件

5、实现规模小、硬件实现电路省电。普遍认为，160位长的椭圆曲线密码的安全性相当于1024位的RSA密码，而且运算速度也较快。 一些国际标准化组织已把椭圆曲线密码作为新的信息安全标准。如，IEEE P1363/D4，ANSI F9.62，ANSI F9.63等标准，分别规范了椭圆曲线密码在Internet协议安全、电子商务、Web服务器、空间通信、移动通信、智能卡等方面的应用。,椭圆曲线,一般来讲，椭圆曲线的曲线方程是以下形式的三次方程： y2+axy+by=x3+cx2+dx+e 其中a，b，c，d，e是满足某些简单条件的实数。定义中包括一个称为无穷点的元素，记为O。下图是椭圆曲线的两个例子。,

6、椭圆曲线的两个例子,椭圆曲线上的加法运算定义如下： 如果其上的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, 设Q和R是椭圆曲线上x坐标不同的两点，Q+R的定义如下： 画一条通过Q、R的直线与椭圆曲线交于P1（

7、这一交点是惟一的，除非所做的直线是Q点或R点的切线，此时分别取P1=Q和P1=R）。由Q+R+P1=O得Q+R=-P1。 点Q的倍数定义如下： 在Q点做椭圆曲线的一条切线，设切线与椭圆曲线交于点S，定义2Q=Q+Q=-S。类似地可定义3Q=Q+Q+Q+，等。 以上定义的加法具有加法运算的一般性质，如交换律、结合律等。,密码中普遍采用的是有限域上的椭圆曲线，有限域上的椭圆曲线是指曲线方程定义式中，所有系数都是某一有限域GF(p)中的元素（其中p为一大素数）。其中最为常用的是由方程 y2x3+ax+b(mod p) (a,bGF(p),4a3+27b2(mod p)0) 定义的曲线。设Ep(a,b

8、)表示所定义的椭圆曲线上的点集(x,y)|0 xp,0yp，且x,y均为整数并上无穷远点O,有限域上的椭圆曲线,Ep(a,b)上的加法定义如下： 设P，QEp(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)，而-7 mod 2316，所以 -P=(13, 16)，也在E23(1,1)中。, 设P=(x1,y1)，Q=(x2,y2)，P-Q，则P+Q=(x3,y3)由以下规则确定：

9、x32-x1-x2(mod p) y3(x1-x3)-y1(mod p) 其中,倍点运算仍定义为重复加法，如4P=P+P+P+P。 模除法运算： a/b mod n 乘以b的逆元: a/b = a.b-1 mod n 如果n是素数, b-1 mod n 存在 b.b-1 = 1 mod n,例1. 以E23(1,1)为例，设P=(3,10)，Q=(9,7)，则 所以P+Q=（17,20），仍为E23(1,1)中的点。,E23(1,1),E23(1,1),若求2P则 所以2P=(7,12)。,例2：取p=11，椭圆曲线y2=x3 +x+6 。由于p较小，使GF(p)也较小，故可以利用穷举的方法根

10、据y2=x3 +x+6 mod 11求出所有解点。,x x3+x+6 mod 11 是否模11平方剩余 y 0 6 No 1 8 No 2 5 Yes 4,7 3 3 Yes 5,6 4 8 No 5 4 Yes 2,9 6 8 No 7 4 Yes 2,9 8 9 Yes 3,8 9 7 No 10 4 Yes 2,9,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）。,从例子可以看出，加法运算在E2

11、3(1,1)中是封闭的，且能验证还满 足交换律。对一般的Ep(a,b)，可证其上的加法运算是封闭的、满 足交换律，同样还能证明其上的加法逆元运算也是封闭的，所以 Ep(a,b)是一个加法交换群。 除了GF(p)上的椭圆曲线外,还有定义在GF(2m)上的椭圆曲线。这两 种椭圆曲线都可以构成安全的椭圆曲线密码。,为使用椭圆曲线构造密码体制，需要找出椭圆曲线上的数学困 难问题。 椭圆曲线群上的离散对数问题 在例2中椭圆曲线上的解点所构成的交换群恰好是循环群，但是一 般并不一定。于是我们希望从中找出一个循环子群E1 。可以证明 当循环子群E1 的阶E1是足够大的素数时，这个循环子群中的 离散对数问题是

12、困难的。,椭圆曲线密码,设P和Q是椭圆曲线上的两个解点，t 为一正整数，且0tE1。对于给定的P和t，计算tPQ是容易的。但若已知P和Q点，要计算出t则是极困难的。这便是椭圆曲线群上的离散对数问题，简记为ECDLP(Elliptic Curve Discrete Logarithm Problem)。 除了几类特殊的椭圆曲线外，对于一般ECDLP目前尚没有找到有效的求解方法。于是可以在这个循环子群E1中建立任何基于离散对数困难性的密码，并称这个密码为椭圆曲线密码。,椭圆曲线密码 T= p,a,b,G,n是公开的参数； p为大于3素数，p确定了有限域GF（p）； 元素a,bGF(p),a和b确定

13、了椭圆曲线； G为循环子群E1的生成元点，n为素数且为生成元G的阶，G和n确定了循环子群E1； h=|E|/n，并称为余因子，h将交换群E和循环子群联系起来。,椭圆曲线密码 密钥： 用户的私钥定义为一个随机数d， d0,1,2,n-1。 用户的公开钥定义为Q点， Q=dG 。,设d为用户私钥，Q为公钥，将Q存入PKDB。 设要加密的明文数据为M，将M划分为一些较小的数据块，M=m1 ，m2 ， ，mt，其中0mi n 。,加密过程：A把M加密发给B A查PKDB，查到B的公开密钥QB 。 A选择一个随机数k，且k0,1,2,n-1。 A计算点X1 ：（x1 ，y1）=kG 。 A计算点X2 ：

14、（x2 ，y2）=kQB ，如果分量x2=O，则转2)。 A计算密文 C = mi x2 mod n 。 A发送加密数据（X1，C）给B。,解密过程： 用户B用自己的私钥dB 求出点X2 ： dBX1 = dB（kG） = k(dB G) = k QB = X2 ：（x2 ，y2） 对C解密，得到明文mi =C x2 1 mod n 。,椭圆曲线密码体制的优点,安全性高 密钥量小 实现相同安全性条件下，ECC所需密钥量远下雨有限域上离散 对数问题的公钥体制的密钥量 灵活性好 通过改变参数可以获得不同的曲线，具有丰富的群结构和多选择性,Key Management,public-key encr

15、yption helps address key distribution problems have two aspects of this: distribution of public keys use of public-key encryption to distribute secret keys,Distribution of Public Keys,Several techniques can be grouped into the following general schemes : public announcement publicly available direct

16、ory public-key authority public-key certificates,Public-Key Authority,improve security by tightening control over distribution of keys from directory has properties of directory and requires users to know public key for the directory then users interact with directory to obtain any desired public ke

17、y securely does require real-time access to directory when keys are needed,Figure 10.3 Public Key distribution Scenario,Public-Key Certificates,certificates allow key exchange without real-time access to public-key authority a certificate binds identity to public key usually with other info such as

18、period of validity, rights of use etc with all contents signed by a trusted Public-Key or Certificate Authority (CA) can be verified by anyone who knows the public-key authorities public-key,Figure 10.4 Exchange of Public Key Certificates,Public-Key Distribution of Secret Keys,use previous methods t

19、o obtain public-key can use for secrecy or authentication but public-key algorithms are slow so usually want to use private-key encryption to protect message contents hence need a session key have several alternatives for negotiating a suitable session,Secret Key Distribution with Confidentiality an

20、d Authentication,proposed by Needham and Schroeder in 1978 Protection against both active and passive attacks,Figure 10.6 Public Key Distribution of Secret Keys with Confidentiality and Authentication,first public-key type scheme proposed by Diffie & Hellman in 1976 along with the exposition of publ

21、ic key concepts note: now know that Williamson (UK) secretly proposed the concept in 1970 is a practical method for public exchange of a secret key used in a number of commercial products,Diffie-Hellman Key Exchange,a public-key distribution scheme cannot be used to exchange an arbitrary message rather it can establish a common key known only to the two participants value of key depends on the participants (and their private and public key informat