公钥密码1RSA及其原理

5.0引言5.1公钥密码的理论基础5.2RSA公钥密码5.2.2RSA公钥密码体制5.2.3RSA的安全性讨论5.2.4模n求逆的方法5.2.5模n的大数幂乘的快速算法5.2.6因子分解5.3大素数的生成第五章公钥密码第五章公钥密码1976年，W.Diffie和M.E.Hellman首先提出了公钥密码学。在公钥密码体制中，加密密钥（Publickey)和解密密钥(privatekey)是不一样的，由两者任何一个不能推出另一个，本章介绍RSA公钥密码体制，ElGamal公钥密码体制,Menezes-Vanstone公钥密码体制以及一些相关知识。第五章公钥密码5.1公钥密码的理论基础公钥密码的理论基础是单向函数。定义5.1设是一个函数。如果对任意给定的，计算使得是容易的，但对任意给定的，计算使是难解的，即求的逆函数是难解的，则称是一个单向函数（one-wayfunction)。定义.2设是一个函数，是与有关的一个参数，对任意给定的，计算使得是容易的，如果当不知参数时，计算的逆函数是难解的，但当知道参数时，计算的逆函数是容易的，则称是一个陷门单向函数（trapdoorone-wayfunction),参数称为陷门。在公钥密码中，加密变换是一个陷门单向函数。fxy)(xfyxyxf)(fffffffxyy)(xfytttt5.2RSA公钥密码5.2.1基本的数论知识定义5.3设都是整数。如果则称和模同余，记为，称为这个同余式的模。mba,,)(|bamabmm)(modmba同余的性质：nbdacndbcandcnbamod2mod1mod,mod）（）（则设ndbdamod3）（),(modmod4ndnbandbda则，若）（nbandmod互素时，与特别当5.2RSA公钥密码5.2.1基本的数论知识定义5.3设都是整数。如果则称和模同余，记为，称为这个同余式的模。定理5.1(中国剩余定理)设是两两互素的正整数，设是整数。则同余方程组模有唯一解mba,,)(|bamabmm)(modmbarmmm,...,,21raaa,...,,21rimaxii,...,2,1),(modrmmmM...21MyMaxriiiimod1其中.,...,2,1,mod,/1rimMymMMiiiii证明：对任意，rj1考虑).(mod),(mod1.,...,2,1,modiiiiiiiijiiimayMamyMjirimyMa所以时，因为当）的一个解。是同余方程组（即因此，时，所以时，因为当1.5,...,2,1),(mod),(mod0|11riiiijjriiiijiiiijyMarjmayMamyMaMmji下面我们来证明式（5.2）是同余方程组（5.1)的模唯一解，假设和是同余方程组（5.1)的两个解，即1x2xM,,...,2,1),(mod;,,...,2,1),(mod21rimaxrimaxiiiiEuler函数则,,...,2,1),(mod021rimxxi即.,...,2,1),(|21rixxmi因为两两互素，所以rmmm,...,,21),(|),(|212121xxMxxmmmr即故).(mod21Mxx因此，式（5.2）是同余方程组(5.1)的模唯一解。M定义5.4设n是一个正整数。1),gcd(,10)(:nxnxxndef称为Euler函数。Euler函数是定义在正整数集合上的函数。由定义可以立即得出，如果p是一个素数，则1)(pp定理5.2定理5.2如果)()().212121nnnnnn（互素，则和),(mod),(mod,0221121nrxnrxnnx设对任意的证明：.,.,,.,,0,021212121212211）是一一对应的与数对（因此以唯一确定则根据中国剩余定理可反过来，给定，则可以唯一确定然给定所得余数，显分别除和实际上就是用和其中rrxxrrrrxxnnrrnrnr1212121nxnnxnnxnn与都互素，和与互素当且仅当与互素，所以和因为.,2211212122112互素与互素，与）的个数，其中个数等于数对（的互素的数互素，因此，与与互素并且与都互素当且仅当和nrnrrrxnnnrnrn，所以互素的数的个数为，与的个数为互素的数因为与)()(22111nnnrn).()()()()(21212121nnnnnnxnn，即的个数为互素的数与定理5.3定理5.3如果,...2121sspppn).11)...(11)(11()(,...,,,...,,212121ssspppnnppp为正整数，则为素数，其中证明首先证明对于任意素数和任意正整数有p).11()(ppp的非负倍数为的小于互素的倍数或者与或者是对于任意的ppppxpx.,0,)1(,...,2,01pppp，数为互素的非负的整数的个并与因此，小于个共ppp.1根据定理5.2，我们有).11(1pppp).11)...(11)(11()11()...11()11()()...()()(212211212121sssspppnpppppppppnss定理5.4（Euler定理）定理5.4（Euler定理）)(mod1,1),gcd()(nxnxyxn则都是正整数，如果和设).(mod),(mod,...,,.,...,,0,,...,.21212,1nrrnxrxrnxrxrxrnxnrrrnrrrknjijikkk则必然有互素，如果也都与互素，所以与因为互素互不相同并且都与设）（证明：设).(mod......,.,...,,mod,...,mod,mod,...,,.2121212121nrrrrrrxrrrnxrnxrnxrnxrxrxrkkkkkk于是两两不同余，模因此，这与假设相矛盾).(mod1,...,,21nxnrrrkk互素，所以都与因为Fermat定理推论5.1(Fermat定理)).(mod11),gcd(1pxpxppxp则，是素数并且都是正整数，如果和设定理5.5(Fermat定理)设x和p都是正整数，则).(modpxxp证明因为p是素数，所以x或者与p互素或者是p的倍数，如果x与p互素，则由推论5.1知结论显然成立。如果x是p的倍数则也是p的倍数，因此,结论也成立。px).(mod0)(modppxxp5.2.2RSA公钥密码体制5.2.2RSA公钥密码体制RonRivest、AdiShamir以及LeonardAdleman于1978年提出了RSA公钥密码体制。RSA公钥密码体制描述如下：.mod,)6(.mod,)5(.)).((mod1,)4(.,1))(,gcd(),(1,)3(.)1)(1()(2)1(ncmZcnmcZmdndedeneneeqpnpqnqpdnen明文为解密变换：对密文密文为加密变换：对明文是保密的解密密钥满足计算公开的加密密钥是满足随机选取正整数（保密）（公开），）计算（（保密）。和选取两个大素数RSA合理性证明RSA合理性证明例5.1练习5.2.3RSA的安全性讨论5.2.3RSA的安全性讨论RSA公钥密码体制的安全性是基于大整数的素分解问题的难解性。随着计算能力的持续增长和因子分解算法的不断完善，为保证RSA的安全性，在实际应用中选取的素数p和q越来越大，现在来看，n的长度为1024位至2048位是比较合理的。注意以下事实：RSA的安全性除了指定n的大小之外，p和q的选取应做如下限制：应该很小。）（。都应该包含大的素因子和）（的长度应该相差不大。和)1,1gcd(3112)1(qpqpqp5.2.4模n求逆的方法1.求两个正整数的最大公因子gcd(n,u)的Euclid算法如下：.)2(,,0)4.),gcd(,0)3(.,)2(,,)1(2212212121步转第则如果（则如果rnnnrnunrqnnrnnqunnn扩展的Euclid算法存在正整数a和b,使得.),gcd(bnauun扩展的Euclid算法如下：.)2(.,,.,,,,,0)4.,,),gcd(,0)3(.,)2(.0,0,0,1,,)1(12122121222212222121221121步转第则如果（则如果tbqbbbbttaqaaaatrnnnrbbaanunrqnnrnnqbabaunnn定理5.6定理5.6设是一个正整数，n}.1,...,3,2,1,0{nZn.1),gcd(1mod,,nunuvZvZunn的充分必要条件是使得存在对于证明必要性。显然，对任意存在整数使得nZbq.mod,1qnbunbunqnbu.1),gcd(,1mod,.1mod,,1mod),(),gcd(.1),gcd(nunuvZvnbuZbnbuqnbunununn必然有则使得因此，如果存在都有即对任意所以因为假设充分性.假设则存在整数使得1),gcd(unba和.1mod.1),gcd(naunubnau于是.1mod,modnuvnav则令模n求逆的算法求模n求逆的算法如下：.)2(.,,,,,0)3.,)2(.1,0,,)1(1212222121212121步转第则如果（tbqbbbbtrnnnrqnnrnnqbbunnn.mod,1)5(.,1)4(222nbnunnun的逆元为模则如果不存在逆元模则如果故2735mod)8(35mod1315.2.5模n的大数幂乘的快速算法5.2.5模n的大数幂乘的快速算法模n的大数幂乘的快速算法如下：.)2(,mod)(,1)5.3,mod)(,2)4(.)5(,02mod)3(0)2(.1,,)1(步转第（）步转到第（步则转到第如果，结束，则输出结果如果ncacbbnaaabbbcbcrbxa例5.3计算.12mod322912mod8112mod9912mod81912mod9912mod)81(912mod)9(9mod9912mod)9(8112mod)9(9912mod)9(912mod)81(912mod)9(912mod)9(912mod)9(12mod)3(12mod3222244455521011112225.2.6因子分解J.M.Pollard(1974):p-1因子分解法：警告！由P-1因子分解算法可以看出，在RSA公钥密码体制中，大素数p和q的选取应满足p-1和q-1都至少有一个大的素因子。否则n可被分解，RSA被破译。5.3大素数的生成本节介绍快速生成大素数的一些常用基本方法5.3.1素数的分布素数的分布极不均匀，素数越大分布越稀疏。定理5.7存在无穷多个素数.证明假设正整数中只有个素数，设为k.,...,21,kppp.,,.,,...,,.,1,,....,...,2,1,,1,1...2121.,...,2121素数有无穷多个因此相矛盾个素数这与只有都不相同与故素数相矛盾是这与所以以及否则由于，一定有一个素因子不是素数，则如果个素数的假设相矛盾，都不相同，这与只有与是素数，则显然。如果则令kppppppnpppppkipppnnkpppnnnpppnkkikk定理5.8（素数定理）的素数的个数，则为不大于设xxx)(,0.1ln)(limxxxx由此可见,大素数是相当稀疏的.素数定理5.3.2Legendre符号和Jacob