公钥密码(中Elgamal)

密码学第十讲公钥密码——[e-mail]武汉大学2第十讲公钥密码单向陷门函数ELGamal密码椭圆曲线密码椭圆曲线椭圆曲线密码单向函数是满足下列性质的函数：每个函数值都存在唯一的逆，并且计算函数值是容易的但求逆却是不可行的：已知X，求Y=f(X)容易已知Y，求X=f-1(Y)不可行单向函数单向函数是求逆困难的函数，而单向陷门函数(Trapdoorone-wayfunction)，是在不知陷门信息下求逆困难的函数，当知道陷门信息后，求逆是易于实现的。单向限门函数是一族可逆函数fk，满足1.y=fk(x)易于计算（当k和x已知）2.x=fk-1(y)易于计算（当k和y已知）3.x=fk-1(y)计算上不可行（y已知但k未知）研究公钥密码算法就是找出合适的单向限门函数单向陷门函数背包问题(Knapsackproblem)已被攻破大整数分解问题(TheIntegerFactorizationProblem)RSA密码离散对数问题有限域的乘法群上的离散对数问题(TheDiscreteLogarithmProblem)——ElGamal密码定义在有限域的椭圆曲线上的离散对数问题(TheEllipticCurveDiscreteLogarithmProblem)——ECC密码公钥密码基于的数学难题理论上：不能证明单向函数一定存在；实际上：只要函数的单向性足够工程应用就行；实际上已找到的单向性足够的函数有：①合数的因子分解问题大素数的乘积容易计算（pqn），而大合数的因子分解困难(npq)。②有限域上的离散对数问题有限域上大素数的幂乘容易计算（abc），而对数计算困难(logacb)。单向函数研究现状合数的因子分解问题单向函数研究现状有限域上的离散对数问题例如GF(19)中模19的整数幂单向函数研究现状1、基本情况：ELGamal密码是除了RSA密码之外最有代表性的公开密钥密码。ELGamal密码建立在离散对数的困难性之上。RSA密码建立在大合数分解的困难性之上。ELGamal公钥密码的基本情况2、离散对数问题：①设p为素数，则模p的剩余构成域：Fp={0,1,2,…,p-1}Fp的非零元构成循环群Fp*Fp*={α，α2，α3，，αp-1}，则称α为Fp*的生成元或模p的本原元(根)。②设p为素数，α为模p的本原元，α的幂乘运算为Y=αXmodp，1≤X≤p-1,则称X为以α为底的模p的对数。离散对数问题有限域上的离散对数问题例如GF(19)中模19的整数幂离散对数问题12离散对数问题2、离散对数问题：求解对数X的运算为X=logαY，1≤X≤p-1由于上述运算是定义在模p有限域上的，所以称为离散对数运算。③从X计算Y是容易的。可是从Y计算X就困难得多，利用目前最好的算法O(exp((lnp)1/3ln(lnp)2/3)，对于安全选择的p将至少需用p1/2次以上的运算，只要p足够大，求解离散对数问题是相当困难的。离散对数问题（备注）算法复杂度：例如：离散对数问题15离散对数问题(DiscreteLogarithmProblem)，简称DLPGivenα,y,p,tofindxs.t.αx=y(modp)e.g.α=2,y=3,p=23,x=？α=2,y=97206,p=136943,x=？离散对数问题16离散对数问题(DiscreteLogarithmProblem)，简称DLPGivenα,y,p,tofindxs.t.αx=y(modp)e.g.α=2,y=3,p=23,x=8α=2,y=97206,p=136943,x=70469离散对数问题171985年，ElGamal在Differ-Hellman密钥交换协议基础上改进而来依赖数学难题：DLP(DiscreteLogarithmProblem)ELGamal公钥密码18算法生成密钥对GenKeyPair加密Encrypt解密DecryptELGamal公钥密码19准备阶段：随机地选择一个大素数p，且要求p-1有大素数因子。再选择一个模p的本原元α。将p和α公开。⑴密钥生成用户随机地选择一个整数d作为自己的秘密的解密钥，2≤d≤p-2。计算y=αdmodp，取y为自己的公开的加密钥。由公开钥y计算秘密钥d，必须求解离散对数，而这是极困难的。ELGamal公钥密码20算法GenKeyPair模块Givensystemparametersα,p(21023p21024)Randomgeneratedy=αd(modp)PublicKey:yPrivateKey:dELGamal公钥密码21⑵加密将明文消息M（0≤M≤p-1)加密成密文的过程如下：随机地选取一个整数k，2≤k≤p-2。计算：U＝ykmodp；C1＝αkmodp；C2＝UMmodp；取C＝（C1，C2）作为的密文。ELGamal公钥密码22算法Encrypt模块Givensystemparametersα,pGivenPublicKey:yPlainText:MRandomchoosekCipherText:C=αk(modp),M*yk(modp)ELGamal公钥密码23⑶解密将密文（C1，C2）解密的过程如下：计算V＝C1dmodp；计算M＝C2V-1modp。ELGamal公钥密码24算法Decrypt模块Givensystemparametersα,pGivenPrivateKey:xCipherText:C=c1,c2PlainText:M=c2/c1d(modp)ELGamal公钥密码25算法可还原性证明C2V-1modp＝(UM)V-1modp＝UM（C1d）-1modp＝UM（（αk）d）-1modp＝UM（（αd）k）-1modp＝UM（（y）k）-1modp＝UM（U）-1modp＝MmodpELGamal公钥密码26安全性直接破解ElGamal加密机制的唯一方法是获取yk，（如果存在其他方法也能破解ElGamal加密机制得到明文，则等同于获取了yk）ELGamal公钥密码27安全性获取yk的直接攻击方法攻击1——由于y是公开的，计算yk需要k，需解DLP：k=logac1攻击2——由于c1是公开的，计算yk=c1d需要d，需解DLP：d=logay由于DLP问题是难解的，所以上述两种方法都无效ELGamal公钥密码28安全性针对k重复使用的攻击方法攻击1（假设攻击者掌握k）如果k不是一次性的，时间长了就可能被攻击者获得。又因y是公开密钥，攻击者自然知道。于是攻击者就可以根据U＝ykmodp计算出U，进而利用Euclid算法求出U－1。又因为攻击者可以获得密文C2，于是可根据式C2＝UMmodp通过计算U－1C2得到明文M。攻击2设用同一个k加密两个不同的明文M和M’，相应的密文为（C1，C2）和（C1’，C2’）。因为yk不变，所以C2∕C2’＝M∕M’，如果攻击者知道M，则很容易求出M’。ELGamal公钥密码29安全性其它攻击方法假如两个明文采用相同的随机数k加密，则通过其密文可以容易推导出两个明文的相互关系。所以要保证加密者所使用的随机数发生器的安全性如果p不够大，则DLP问题将因为密钥空间太小而变得容易解。所以，要对p进行认真的选择加密者在使用接收者的公钥时，应设法确认该公钥是对应着该接收者，否则可能造成应该接收的人无法正常接收，而其他人可以解密ELGamal公钥密码30安全性由于ELGamal密码的安全性建立在GF（p）离散对数的困难性之上，而目前尚无求解GF（p）离散对数的有效算法，所以在p足够大时ELGamal密码是安全的。为了安全p应为150位以上的十进制数，而且p-1应有大素因子。为了安全加密和签名所使用的k必须是一次性的。ELGamal公钥密码31ELGamal密码的应用由于ELGamal密码的安全性得到世界公认，所以得到广泛的应用。著名的美国数字签名标准DSS，采用了ELGamal密码的一种变形。为了适应不同的应用，人们在应用中总结出18种不同的ELGamal密码的变形。（p173-175）ELGamal公钥密码32ElGamal与RSA比较ELGamal公钥密码33椭圆曲线密码的一般情况受ELGamal密码启发，在其它离散对数问题难解的群中，同样可以构成ELGamal密码。于是人们开始寻找其它离散问题难解的群。研究发现，有限域GF（p）上的椭圆曲线的解点构成交换群，而且离散对数问题是难解的。于是可在此群上建立ELGamal密码，并称为椭圆曲线密码。椭圆曲线密码34椭圆曲线密码的一般情况椭圆曲线密码已成为除RSA密码之外呼声最高的公钥密码之一。它密钥短、签名短，软件实现规模小、硬件实现电路省电。普遍认为，160位长的椭圆曲线密码的安全性相当于1024位的RSA密码，而且运算速度也较快。椭圆曲线密码35RSA和ECC的比较RSA和ECC安全模长的比较椭圆曲线密码361985年，NealKoblitz和VictorMiller分别独立地提出了椭圆曲线密码体制多数公钥密码(RSA,DH)使用非常大的数或多项式，给密钥和信息的存储和处理带来很大的运算量椭圆曲线是一个代替，可以用更小的尺寸得到同样的安全性ANSI、IEEE、ISO和NIST都制定了ECC标准草案椭圆曲线密码37椭圆曲线密码的一般情况一些国际标准化组织已把椭圆曲线密码作为新的信息安全标准。如，IEEEP1363/D4，ANSIF9.62，ANSIF9.63等标准，分别规范了椭圆曲线密码在Internet协议安全、电子商务、Web服务器、空间通信、移动通信、智能卡等方面的应用。椭圆曲线密码38椭圆曲线椭圆曲线不是椭圆！费马大定理：当n2且xyz≠0时，xn+yn=zn没有正整数解n=2时，上式有无穷组整数解，例如勾股定理定义“同余数”：正整数n为“同余数”(CongruentNumber)，如果它是一个有理直角三角形的面积。如5、6、7都是“同余数”椭圆曲线密码39椭圆曲线n为“同余数”的条件是下列方程组有有理解：a2+b2=c2（1）ab/2=n（2）由(1)/4±(2)得:令，则求“同余数”的问题转化为：寻找有理数x，使得等差数列x-n，x，x+n都是平方数。那么也是平方数，记为椭圆曲线密码2222()()abcn22()cx32()()xnxxnxnx232yxnx40椭圆曲线“勾股定理”-“同余数”-椭圆曲线椭圆曲线一般形式（Weierstrass方程）当特征为2时，可化简为当特征大于3时，可化简为椭圆曲线密码23213246yaxyayxaxaxa232yxyxaxb23yxaxb41椭圆曲线设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)，将此二元组描画到椭圆曲线上便为一个点，于是又称其为解点。椭圆曲线密码复习：代数结构椭圆曲线密码43椭圆曲线交换群封闭性：结合律：单位元：逆元：交换律：椭圆曲线密码,aGbGabG()()abcabc00aaa()()0aaaaabba44椭圆曲线椭圆曲线密码45椭圆曲线为了利用解点构成交换群，需要引进一个O元素，并定义如下的加法运算：①定义单位元引进一个无穷点O（∞，∞），简记为0，作为0元素。O（∞，∞）＋O（∞，∞）＝0＋0＝0。并定义对于所有的解点P（x，y），P（x，y）+O＝O+P（x，y）＝P（x，y）。椭圆曲线密码46椭圆曲线定义如下的加法