公钥密码系统

三．公钥密码系统•公钥密码的观点是由Diffie和Hellman于1976年在们的论文“密码学的新方向”一文中首次提出的。他们指明了实现在某些已知的数学难解问题上建立密码的具体途径。随后Rivest,Shamir和Adleman于1977年提出第一个比较完善的RSA公钥密码系统。RSA既可以用于保密也可以用于签名。公钥密码系统是计算复杂性理论发展的必然产物。私钥（对称）密码系统的缺陷之一是通信双方在进行保密通信之前需要通过安全通道传送密这点在实际中是非常困难的。而公钥密码系统可使通信双方无须事先传送密钥就可以建立保密通信。公钥密码系统的出现为解决私钥密码系统的密钥分配问题开辟了一条宽广的道路。•在公钥密码系统中每个实体都有自己的公钥和相应的私钥。在安全系统中已知公钥推算出私钥在计算上是困难的。公钥密码系统的加密变换和解密变换分别用和表示。任何实体B要向实体A发送信息m的步骤如下:实体B首先获得实体A的真实公钥的拷贝(AuthenticCopy)实体B计算密文并发送给实体A。实体A使用自己的私钥，计算解密密文恢复明文。这里公钥不需要保密，但要保证它的真实性，即确实是实体A掌握的私钥所对应的公钥。“提供真实的公钥”比“安全地分配密钥”实现起来要容易得多。这是公钥密码系统的主要优点。),(AAen)(mEcAe)(cDmAd),(AAen•公钥密码系统的主要目的是提供保密性，它不能提供数据源认证(DataOriginAuthentication)和数据完整性(DataIntegrity)。数据源认证是指：指定的数据是在以前的某个时间确实是由真正的源创建的。数据完整性是指：真正的源创建该数据后经过传输或储存没有发生改变。数据源认证和数据完整性要由其它技术来提供（如：消息认证码、数字签名）•从本质上来看，公钥密码比私钥密码（如：DES、IDEA、RC5等）加密的速度要慢。通常公钥密码用在:传送密钥。以后用该密钥作为私钥密码系统的密钥来加密大量数据在数据完整性和认证中使用加密少量数据•公钥解密也可以提供认证保证（如：在实体认证协议、带认证的密钥协建立协议等）。公钥加密中必须有办法让发送消息的人得到想要发送到的那个人的公钥的真实拷贝。否则的话就会受到伪装攻击。在实践中有很多方法分发真实的公钥，如：使用可信的公共文件、使用在线可信服务器、使用离线服务器和认证。建立在不同计算问题之上的其它几个公钥密码系统是•Merkle-HellmanKnapsack(1978)本系统及相关系统基于“子集和”问题的困难性。然而已证明除Chor-Rivest系统外各种knapsack系统都是不安全的•McEliece(1978)McEliece密码系统基于代数编码系统。•ElGamal(1985)它基于有限域中离散对数问题的困难性•椭圆曲线椭圆曲线密码系统是用椭圆曲线上运算代替有限域上运算来实现已有的公钥密码系统。它的特点是运行速度快、密钥长度短•从抽象的观点来看，公钥密码系统是一种单向陷门函数。我们说一个函数是单向函数(OneWayFunction)是指：对它的定义域中的任意元素都容易计算其函数值，反过来对值域中几乎所有元素确定它的原象都是不可行的。如果掌握某些辅助信息就容易由值域元素确定它的原象，那么这种单向函数叫单向陷门函(TrapdoorOneWayFunction)。这里辅助信息就是陷门。例如：p和q是两个大素数，n=p.q，e是正整数，是单向陷门函数，其陷门是nnZZf:nxxfemod)()(mod1ned。3.1RSA系统和素因子分解•3.1.1RSA密码系统简介•3.1.2RSA密码系统描述•3.1.3RSA实现•3.1.4RSA在实现时要注意的问题•3.1.6有关算法•3.1.7因子分解3.1.1RSA密码系统简介•RSA是使用最广泛的公钥密码系统。它可以用在保密性和数字签名。•1976年Diffie&Hellman提出公钥密码系统的思想•1977年由Rivest,Shamir,Adleman首次实现了著名的RSA密码系统，它的安全基于大整数素因子分解的困难性上。3.1.2RSA密码系统描述•每个实体有自己的公钥(n,e)及私钥p,q,d，其中n=p.q是两个大素数之积,。实体B加密消息,将密文在公开信道上传送给实体A。实体A接到密文后对其解密。加密算法实体B做如下动作1.得到实体A的真实公钥(n,e)2.把消息表示成整数m,0≤m≤n-13.使用平方—乘积算法，计算4.将密文发送给实体A解密算法实体A接受到密文C，使用私钥d计算,)(mod1ndeCnmmEekmod)(nCCDmdkmod)(nZm证明：对任何有这里要证明首先证明对,显然有当时,由Fermat定理知同理推出最后得到nZmmmEDkk))((mnmmEDedkkmod))((pmmedmodmp|pmmedmod01),gcd(pmpmmmmqvpedmod)()1(1qmmedmodnmmedmod3.1.3RSA实现1密钥生成每个实体A建立他的RSA公钥和相应的私钥a.生成两个大的随机素数p和q，并且位长大体相同b.计算n=p.q，c.选择随机数e,,（推出是奇数）d.求，即用扩展的Euclidean算法求的解d（推出也是奇数）e.公布实体A的公钥（n,e），由实体A秘密保存私钥p,q,dqp)1)(1()(qpn)(0ne1))(,gcd(ne)(mod1ned1)(xnde2加密和解密的有效性若能分解n，就能由e公钥计算出私钥d。为此应n=p.q足够长。当前整数素因子分解算法能分解十进制数长度是130，故选取的素数p和q应该是100的十进制数。目前RSA的一些硬件实现使用512bit的n（相当154位十进制数，所以不能提供长期的安全性），速度达600Kbit/秒。由于二次筛法、数域筛法等因子分解算法的出现，我们推荐768bit，长期安全应该使用1024bit。粗略地说，RSA硬件实现比DES硬件实现慢1500倍。RSA软件实现比DES软件实现慢100倍。为了加速解密，实体A不是简单平方-乘积算法计算，而是利用p，q计算nCdmodqCCpCCmodmod21)1(mod)1(mod21qddpdd令，，用中国剩余定理解求出明文m。这样速度可以提高4~8倍。pCmdmod111qCmdmod222qmmpmmmodmod213RSA安全性分析首先我们研究如下事实的等价性a.计算b.求1模n非平凡二次方根c.分解的素因子由此看出攻击RSA可能采取的方法,上述事实的等价性分析如下：①已知n和由定义n=p.q和得知的它的两个根为p和q，即能分解n。实际上知道就可以从公钥e计算出私钥d。)(n)(n)1)(1()(qpn0)1)((2npnnp)(n②已知n=p.q的素因子p,q，中元素1是模p二次剩余，它的两个二次方根为1，p-1。中元素1是模q二次剩余，它的两个二次方根为1，q-1。用中国剩余定理求解下面4个同余方程组得到4个模n同余解z，它们必是(1,n-1,x,n-x)使。其中x,n-x是模n非平凡二次方根*pZ*qZqzpzmod1mod1qzpzmod1mod1qzpzmod1mod1qzpzmod1mod1nzmod12例如：求出z=1,z=92,z=311,z=402,z=92,311为1模403的非平凡二次方根。反过来,已知1的模n非平凡二次方根,即知道且,显然。4033113n31mod113mod1zz31mod113mod1zz31mod113mod1zz31mod113mod1zz1xnxmod12nxmod12nxxmod0)1)(1(用Euclidean算法在多项式时间内能求出或，它们就是p或q，故能分解n。例如：,x=92,311为1模403的非平凡二次方根。gcd(92+1,403)=31,gcd(92-1,403)=13。gcd(311+1,403)=13,gcd(311-1,403)=31),1gcd(nx),1gcd(nx4033113n3.1.4RSA在实现时要注意的问题1.在构造n时应选择p和q使得p-1和q-1有大的素因子。一般选择p和(p-1)/2均是素数的p。2.每个用户必须有自己的模数n，用户之间不要共享n。这里有两个原因:1某中心选择公用的RSA模数n，然后把分发给众多用户。由任何一对都能分解模数n。从而本质上任何用户都可以求出共享该模数的每个用户的解密密钥。2如果用户1公钥为,用户2公钥为,其中。用户3要把同一个消息x发送给用户1和用户2，它们分别为，。),(iide),(iideid1,en2,en1),gcd(21eenxyemod11nxyemod22窃听者截获就可以计算出x。其步骤是：a.计算b.计算2111modeeh2112/)1(eehhnyyxhhmod121213RSA的同态性质(HomomorphicProperty)RSA的同态性质是指乘积的密文是密文的乘积，即的密文其中对手想解开密文但是不让实体A知道m于是对手随机选择整数并用代替来掩盖明文m.让实体A对解密得到21mmmnCCCmod21nmCemod11nmCemod22nmCemod*nZxnxCCemod~C~nCmdmod~~对手再计算出明文对待这种选择密文攻击，实践中可以通过在明文消息中强行加入某个结构来解决。如果密文C解密后不具有这种结构，则实体A发现是欺骗行为而拒绝C。这种做法以很高的概率使不具有这种精心选择的结构，从而对手取不到。4小的加密指数为了增强加密的有效性，希望选择较小的加密指数e（如=3）.一组实体可以有相同的加密指数，前面说过每个实体必须有自己各不相同的模数。如果相同的消息要送给多个实体的话，就不应该使小的加密指数nxmmmod~1C~m~例如：实体A要送给m三个不同实体，他们的公钥分别是,,,其中互素对手窃取到密文使用中国剩余定理解下面同余方程组得到x并求它的三次方根就恢复明文m。)3,(1n)3,(2n)3,(3n3,2,1nnnm3213nnnm31,mod3inmCii321,,nnn332211modmodmodnCxnCxnCx为了防止这类攻击，在加密前把随机生成的字符串附在明文的后面.这个过程叫“消息加盐”(Saltingthemessage).对于小的消息m和e，也可以采用加盐的办法。小的加密指数对于小的明文（）也存在问题。对手只需计算密文的e次方根就能恢复明文。选择小的e或选择e的二进制表示中1的位数少。好处是可以加速加密算法。在实际使用中一般取e=3或者。5消息隐藏问题如果，则明文加密后没有被隐藏。不难看出共有个消息未被隐藏（≥9）nmeenm1216enmmemod)1,1gcd(1)1,1gcd(1qepe为此我们最好选取安全素数，即对于素数p，(p-1)/2也是素数。如果p和q是随机素数，e也是随机选的（或选择e比较小如e=3或），则一般RSA加密未隐藏的消息所占比例小的可以忽略不计。1216e3.1.6有关算法扩展的辗转相除法、求逆、中国剩余定理等算法已经在前面介绍过。现在给出求幂的算法和素性测试算法。1）求幂的算法（平方—乘积法）输入，，的二进制表示为输出，如果，则返回值。如果，则对做如果则nZank00121kkkkkkttnakmod1b0kbaA10kabti,,2,1nAAmod21iknbAbmod*例如：求这里，最后求出=7。计算过程中各参数列表如下0123110139131631010717mod3111011