椭圆曲线密码

密码学（第九讲）公开密钥密码（2）张焕国武汉大学计算机学院目录1、密码学的基本概念2、古典密码3、数据加密标准（DES）4、高级数据加密标准（AES）5、中国商用密码（SMS4）6、分组密码的应用技术7、序列密码8、习题课：复习对称密码9、公开密钥密码（1）目录10、公开密钥密码（2）11、数字签名（1）12、数字签名（2）13、HASH函数14、认证15、密钥管理16、PKI技术17、习题课：复习公钥密码18、总复习/检查：综合实验一、ELGamal公钥密码的基本情况1、基本情况：①ELGamal密码是除了RSA密码之外最有代表性的公开密钥密码。②RSA密码建立在大合数分解的困难性之上。③ELGamal密码建立在离散对数的困难性之上。一、ELGamal公钥密码的基本情况2、离散对数问题：①设p为素数，则模p的剩余构成有限域：Fp={0,1,2,…,p-1}Fp的非零元构成循环群Fp*Fp*={1,2,…,p-1}={α，α2，α3，，αp-1}，则称α为Fp*的生成元或模p的本原元。②求α的摸幂运算为:y=αxmodp，1≤x≤p-1,一、ELGamal公钥密码的基本情况2、离散对数问题：求对数X的运算为x=logαy，1≤x≤p-1由于上述运算是定义在模p有限域上的，所以称为离散对数运算。③从x计算y是容易的。可是从y计算x就困难得多，利用目前最好的算法，对于小心选择的p将至少需用O(p½)次以上的运算，只要p足够大，求解离散对数问题是相当困难的。二、ELGamal公钥密码准备：随机地选择一个大素数p，且要求p-1有大素数因子。再选择一个模p的本原元α。将p和α公开。⑴密钥生成用户随机地选择一个整数d作为自己的秘密的解密钥，2≤d≤p-2。计算y=αdmodp，取y为自己的公开的加密钥。由公开钥y计算秘密钥d，必须求解离散对数，而这是极困难的。二、ELGamal公钥密码⑵加密将明文消息M（0≤M≤p-1)加密成密文的过程如下：①随机地选取一个整数k，2≤k≤p-2。②计算：U＝ykmodp；C1＝αkmodp；C2＝UMmodp；③取C＝（C1，C2）作为的密文。二、ELGamal公钥密码⑶解密将密文（C1，C2）解密的过程如下：①计算V＝C1dmodp；②计算M＝C2V-1modp。二、ELGamal公钥密码解密的可还原性可证明如下：C2V-1modp＝(UM)V-1modp＝UM（C1d）-1modp＝UM（（αk）d）-1modp＝UM（（αd）k）-1modp＝UM（（y）k）-1modp＝UM（U）-1modp＝Mmodp二、ELGamal公钥密码⑷安全性由于ELGamal密码的安全性建立在GF（p）离散对数的困难性之上，而目前尚无求解GF（p）离散对数的有效算法，所以在p足够大时ELGamal密码是安全的。为了安全p应为150位以上的十进制数，而且p-1应有大素因子。为了安全加密和签名所使用的k必须是一次性的。d和k都不能太小。二、ELGamal公钥密码⑷安全性如果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’。二、ELGamal公钥密码⑸ELGamal密码的应用由于ELGamal密码的安全性得到世界公认，所以得到广泛的应用。著名的美国数字签名标准DSS，采用了ELGamal密码的一种变形。为了适应不同的应用，人们在应用中总结出18种不同的ELGamal密码的变形。二、ELGamal公钥密码⑸ELGamal密码的应用①加解密速度快由于实际应用时ELGamal密码运算的素数p比RSA要小，所以ELGamal密码的加解密速度比RSA稍快。②随机数源由ELGamal密码的解密钥d和随机数k都应是高质量的随机数。因此，应用ELGamal密码需要一个好的随机数源，也就是说能够快速地产生高质量的随机数。③大素数的选择为了ELGamal密码的安全，p应为150位（十进制数）以上的大素数，而且p-1应有大素因子。三、椭圆曲线密码1、椭圆曲线密码的一般情况受ELGamal密码启发，在其它离散对数问题难解的群中，同样可以构成ELGamal密码。于是人们开始寻找其它离散问题难解的群。研究发现，有限域GF（p）上的椭圆曲线的解点构成交换群，而且离散对数问题是难解的。于是可在此群上建立ELGamal密码，并称为椭圆曲线密码。三、椭圆曲线密码1、椭圆曲线密码的一般情况椭圆曲线密码已成为除RSA密码之外呼声最高的公钥密码之一。它密钥短、签名短，软件实现规模小、硬件实现电路省电。普遍认为，160位长的椭圆曲线密码的安全性相当于1024位的RSA密码，而且运算速度也较快。三、椭圆曲线密码1、椭圆曲线密码的一般情况一些国际标准化组织已把椭圆曲线密码作为新的信息安全标准。如，IEEEP1363/D4，ANSIF9.62，ANSIF9.63等标准，分别规范了椭圆曲线密码在Internet协议安全、电子商务、Web服务器、空间通信、移动通信、智能卡等方面的应用。三、椭圆曲线密码2、椭圆曲线设p是大于3的素数，且4a3+27b2≠0modp，称y2=x3+ax+b，a,b∈GF(p)为GF（p）上的椭圆曲线。由椭圆曲线可得到一个同余方程：y2=x3+ax+bmodp其解为一个二元组x,y，x,y∈GF(p)，将此二元组描画到椭圆曲线上便为一个点，于是又称其为解点。三、椭圆曲线密码2、椭圆曲线为了利用解点构成交换群，需要引进一个O元素，并定义如下的加法运算：①定义单位元引进一个无穷点O（∞，∞），简记为0，作为0元素。O（∞，∞）＋O（∞，∞）＝0＋0＝0。并定义对于所有的解点P（x，y），P（x，y）+O＝O+P（x，y）＝P（x，y）。三、椭圆曲线密码2、椭圆曲线②定义逆元素设P（x1，y1）和Q（x2，y2）是解点，如果x1=x2且y1=-y2，则P（x1，y1）＋Q（x2，y2）＝0。这说明任何解点R（x，y）的逆就是R（x，-y）。注意：规定无穷远点的逆就是其自己。O（∞，∞）＝-O（∞，∞）三、椭圆曲线密码2、椭圆曲线③定义加法设P(x1，y1)≠Q(x2，y2)，且P和Q不互逆，则P（x1，y1）＋Q（x2，y2）＝R（x3，y3）。其中x3=λ2-x1-x2，y3=λ(x1–x3)-y1，λ=（y2-y1）/(x2-x1）。三、椭圆曲线密码2、椭圆曲线③定义加法当P（x1，y1）=Q(x2，y2)时P（x1，y1）＋Q(x2，y2)＝2P（x1，y1）＝R（x3，y3）。其中x3=λ2-2x1，y3=λ(x1–x3)-y1，λ=（3x12+a）/（2y1）。三、椭圆曲线密码2、椭圆曲线作集合E={全体解点，无穷点O}。可以验证，如上定义的集合E和加法运算构成加法交换群。复习：群的定义G是一个非空集，定义了一种运算，且运算是自封闭的；运算满足结合律；G中有单位元；G中的元素都有逆元；三、椭圆曲线密码3、椭圆曲线解点加法运算的几何意义：设P（x1，y1）和Q（x2，y2）是椭圆曲线的两个点，则连接P（x1，y1）和Q（x2，y2）的直线与椭圆曲线的另一交点关于横轴的对称点即为P（x1，y1）+Q（x2，y2）点。三、椭圆曲线密码3、椭圆曲线解点加法运算的几何意义：xy0PQP+Q三、椭圆曲线密码4、举例：取p=11，椭圆曲线y2=x3+x+6。由于p较小，使GF(p)也较小，故可以利用穷举的方法根据y2=x3+x+6mod11求出所有解点。复习：平方剩余设p为素数，如果存在一个正整数x，使得x2=amodp,则称a是模p的平方剩余。三、椭圆曲线密码xx3+x+6mod11是否模11平方剩余y06No18No25Yes4,733Yes5,648No54Yes2,968No74Yes2,989Yes3,897No104Yes2,9三、椭圆曲线密码根据表可知全部解点集为：(2，4),(2，7),(3，5),(3，6),(5，2),(5，9),(7，2),(7，9),(8，3),(8，8),(10，2),(10，9)。再加上无穷远点O，共13的点构成一个加法交换群。由于群的元素个数为13，而13为素数，所以此群是循环群，而且任何一个非O元素都是生成元。三、椭圆曲线密码由于是加法群，n个元素G相加，G+G+...+G＝nG。我们取G＝（2，7）为生成元，具体计算加法表如下：2G=（2，7）+（2，7）=（5，2）因为λ=（3×22+1）（2×7）-1mod11=2×3-1mod11=2×4mod11=8。于是，x3=82-2×2mod11=5，y3=8（2-5）-7mod11=2。三、椭圆曲线密码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），13G＝O（∞，∞）。三、椭圆曲线密码除了GF(p)上的椭圆曲线，外还有定义在GF(2m)上的椭圆曲线。这两种椭圆曲线都可以构成安全的椭圆曲线密码。在上例中，由于p较小，使GF(p)也较小，故可以利用穷举的方法求出所有解点。但是，对于一般情况要确切计算椭圆曲线解点数N的准确值比较困难。N满足以下不等式P+1-2P1/2≤N≤P+1+2P1/2。三、椭圆曲线密码5、椭圆曲线密码ELGamal密码建立在有限域GF（p）的乘法群的离散对数问题的困难性之上。而椭圆曲线密码建立在椭圆曲线群的离散对数问题的困难性之上。两者的主要区别是其离散对数问题所依赖的群不同。因此两者有许多相似之处。三、椭圆曲线密码5、椭圆曲线密码①椭圆曲线群上的离散对数问题在上例中椭圆曲线上的解点所构成的交换群恰好是循环群，但是一般并不一定。于是我们希望从中找出一个循环子群E1。可以证明当循环子群E1的阶n是足够大的素数时，这个循环子群中的离散对数问题是困难的。三、椭圆曲线密码5、椭圆曲线密码①椭圆曲线群上的离散对数问题设P和Q是椭圆曲线上的两个解点，t为一正整数，且1≤tn。对于给定的P和t，计算tP＝Q是容易的。但若已知P和Q点，要计算出t则是极困难的。这便是椭圆曲线群上的离散对数问题，简记为ECDLP(EllipticCurveDiscreteLogarithmProblem)。三、椭圆曲线密码5、椭圆曲线密码①椭圆曲线群上的离散对数问题除了几类特殊的椭圆曲线外，对于一般ECDLP目前尚没有找到有效的求解方法。于是可以在这个循环子群E1中建立任何基于离散对数困难性的密码，并称这个密码为椭圆曲线密码。三、椭圆曲线密码②椭圆曲线密码T=p,a,b,G,n,hp为大于3素数，p确定了有限域GF（p）；元素a,b∈GF(p),a和b确定了椭圆曲线；G为循环子群E1的生成元点，n为素数且为生成元G的阶，G和n确定了循环子群E1；h=|E|/n，并称为余因子，h将交换群E和循环子群联系起来。三、椭圆曲线密码②椭圆曲线密码密钥：用户的私钥定义为一个随机数d，d∈{1,2,···,n-1}。用户的公开钥定义为Q点，Q=dG。三、椭圆曲线密码②椭圆曲线密码设d为用户私钥，Q为公钥，将Q存入PKDB。设要加密的明文数据为M，将M划分为一些较小的数据块，M=[m1，m2，···，mt]，其中0≤min。三、椭圆曲线密码②椭圆曲线密码加密过程：A把M加密发给B⑴A查PKDB，查到B的公开密钥QB。⑵A选择一个随机数k，且k∈{1,2,···,n-1}。⑶A计算点X1（x1，y1）=kG。⑷A计算点X2（x2，y2）=kQB，如果分