第5章(RSA公钥密码体制).ppt

第第5章章 RSA公钥密码体制公钥密码体制开课学院：数学学院开课学院：数学学院主讲教师：朱文余主讲教师：朱文余Email:第5章 RSA公钥密码体制5.1 概论概论5.2 计算复杂性理论计算复杂性理论5.3 必备的数论知识必备的数论知识5.4 RSA 公钥系统公钥系统5.5 RSA 公钥系统的一种改进方案公钥系统的一种改进方案5.6 大素数的产生大素数的产生5.7因数分解因数分解5.8对对RSA 体制中小指数的攻击体制中小指数的攻击5.9 Rabin密码体制密码体制5.10 RSA 在有限域在有限域Fp上多项式上的推广上多项式上的推广5.1概论1.传统密码在密钥分配及管理上是极其困难的;2.在商业上有时不可能作到通信双方事先预约使用相同的密钥.单钥密码体制在进行密钥分配时，要求通信双方或者已经有一个共享的密钥，或者可借助于一个密钥分配中心。对第一个要求，常常可用人工方式传送双方最初共享的密钥，这种方法成本很高，而且还完全依赖信使的可靠性。第二个要求则完全依赖于密钥分配中心的可靠性。第二个问题数字签名考虑的是如何为数字化的消息或文件提供一种类似于为书面文件手书签字的方法。1976年W.Diffie和M.Hellman对解决上述两个问题有了突破，从而提出了公钥密码体制。于是公钥密码体制的概念是在解决单钥密码体制中最难解决的两个问题时提出的，这两个问题是密钥分配和数字签名。公钥密码算法的最大特点是采用两个相关密钥将加密和解密能力分开，其中一个密钥是公开的，称为公开密钥，简称公开钥，用于加密；另一个密钥是为用户专用，因而是保密的，称为秘密密钥，简称秘密钥，用于解密。因此公钥密码体制也称为双钥密码体制。算法有以下重要特性：已知密码算法和加密密钥，求解密密钥在计算上是不可行的。公钥密码体制的原理图5.1是公钥体制加密的框图，加密过程有以下几步：要求接收消息的一方，产生一对用来加密和解密的密钥，如图中的接收者B，产生一对密钥Keb，Kdb，其中Keb是公开钥，Kdb是秘密钥。接收方B将加密密钥（Keb）予以公开。另一密钥则被保密（Kdb）。A要想向B发送消息m，则使用B的公开钥加密m，表示为c=Em,Keb,其中c是密文，E是加密算法。B收到密文c后，用自己的秘密钥Kdb解密，表示为m=Dc,Kdb，其中D是解密算法。图5.1 公钥体制加密的框图因为只有B知道Kdb，所以其他人都无法对c解密。公钥加密算法不仅能用于加、解密，还能用于对发方A发送的消息m提供认证，用户A用自己的秘密钥Kda对m加密，表示为c=Em,Kdb将c发往B。B用A的公开钥Kea对c解密，表示为m=Dc,Kea公钥密码算法应满足以下要求:接收方B产生密钥对（公开钥Keb和秘密钥Kdb）在计算上是容易的。发方A用收方的公开钥对消息m加密以产生密文c，即c=Em,Keb在计算上是容易的。收方B用自己的秘密钥对c解密，即m=Dc,Kdb在计算上是容易的。公钥密码算法应满足的要求 敌手由B的公开钥Keb求秘密钥Kdb在计算上是不可行的。敌手由密文c和B的公开钥Keb恢复明文m在计算上是不可行的。加、解密次序可换，即EkebDkdb(m)=DkdbEkeb(m)其中最后一条虽然非常有用，但不是对所有的算法都作要求。以上要求的本质之处在于要求一个陷门单向函数。单向函数是两个集合X、Y之间的一个映射，使得Y中每一元素y都有惟一的一个原像xX，且由x易于计算它的像y，由y计算它的原像x是不可行的。这里所说的易于计算是指函数值能在其输入长度的多项式时间内求出，即如果输入长n比特，则求函数值的计算时间是na的某个倍数，其中a是一固定的常数。这时称求函数值的算法属于多项式类P，否则就是不可行的。例如，函数的输入是n比特，如果求函数值所用的时间是2n的某个倍数，则认为求函数值是不可行的。注意这里的易于计算和不可行两个概念与计算复杂性理论中复杂度的概念极为相似，然而又存在着本质的区别。在复杂性理论中，算法的复杂度是以算法在最坏情况或平均情况时的复杂度来度量的。而在此所说的两个概念是指算法在几乎所有情况下的情形。称一个函数是陷门单向函数，是指该函数是易于计算的，但求它的逆是不可行的，除非再已知某些附加信息。当附加信息给定后，求逆可在多项式时间完成。总结为：陷门单向函数是一族可逆函数fk，满足 Y=fk(X)易于计算（当k和X已知时）。X=f-1k(Y)易于计算（当k和Y已知时）。X=f-1k(Y)计算上是不可行的（当Y已知但k未知时）。因此，研究公钥密码算法就是要找出合适的陷门单向函数。5.2计算复杂性理论计算复杂性理论是分析密码技术的计算要求和研究破译密码的固有难度的基础.用于破译密码算法的计算复杂性,决定了该密码的强度.算法的计算复杂性是用该算法所需的计算时间(T)和存储空间(S)要求来度量的.计算时间和存储空间通常理解为所需输入数据的长度n的函数f(n),表示用”大O”表示法:,若存在满足下面要求的常数c和 ,使得例:设f(n)=8n+10,那么f(n)=O(n),因为8n+109n,当n10.一般地,若f(n)是下面形式的多项式:式中t为常数,那么有即忽略全部常数和低阶项.通常,算法按其时间和空间的复杂性进行分类,如果一个算法的复杂性是不依赖于n:O(1),常数级的;多项式时间算法:指数时间算法:,式中t为常数,f(n)是n的函数.任何密码算法的一个基本要求是:加解密只需要多项式时间的代价,破译需要指数时间的代价.书上表5-1给出了不同的算法簇的运行时间.5.2.2问题复杂性和NP完全wP-问题:可利用确定性算法在多项式时间内可解决.wNP问题(整数分解):可利用非确定性算法在多项式时间内可解决,或者给定一个解,判断这个解是否正确可在多项式时间内可解决.wNP完全问题(背包问题):NP问题中最困难的问题.-矩阵覆盖问题.数论是密码学特别是公钥密码学的基本工具，本章首先介绍密码学中常用的一些数论知识，然后介绍公钥密码体制的基本概念和几种重要算法。5.3 数论简介 5.3.1同余方程和中国剩余定理同余方程同余方程定理定理5.1 同余式 有解的充要条件是 ,其中d=(a,m),且对于模m有d个解.推论推论:设(a,m)=1,则同余式 恰有唯一解 .定理定理5.2 下面两个同余式有一个共同解的充要条件是定理5.3 联立同余式有一个共同解的充要条件是中国剩余定理是数论中最有用的一个工具，定理说如果已知某个数关于一些两两互素的数的同余类集，就可重构这个数。例如：Z10中每个数都可从这个数关于2和5（10的两个互素的因子）的同余类重构。比如已知x关于2和5的同余类分别是0和3，即x mod 20，x mod 53。可知是偶数且被5除后余数是3，所以可得8是满足这一关系的惟一的x。中国剩余定理定理4.5（中国剩余定理）设m1,m2,mk是两两互素的正整数，则一次同余方程组对模M有惟一解:其中ei满足证明：设 ,i=1,2,k，由Mi的定义得Mi与mi是互素的，可知Mi在模mi下有惟一的乘法逆元，即满足 的ei是惟一的。下面证明对i1,2,k，上述x满足ai(mod mi)x。注意到当ji时，mi|Mj，即Mj0(mod mi)。所以(Mjej mod mj)mod mi (Mj mod mi)(ej mod mj)mod mi)mod mi 0而(Mi(ei mod mi)mod mi(Miei)mod mi1所以x(mod mi)ai，即ai(mod mi)x下面证明方程组的解是惟一的。设x是方程组的另一解，即xai(mod mi)(i=1,2,k)由xai(mod mi)得x-x0(mod mi)，即mi|(x-x)。再根据mi两两互素，有M|(x-x)，即x-x0(mod M)，所以x(mod M)=x(mod M)。(证毕)中国剩余定理提供了一个非常有用的特性，即在模M下可将非常大的数x由一组小数(a1,a2,ak)表达。例4.4 由以下方程组求x。解：M=2357=210，M1=105，M2=70，M3=42，M4=30,易求e1M-11 mod 21,e2M-12mod 31,e3M-13 mod 53,e4M-14 mod 74,所以x mod 210(10511+7012+4233+3045)mod 210173，或写成x173 mod 210。例4.5 将973 mod 1813由模数分别为37和49的两个数表示。解：取x=973,M=1813,m1=37,m2=49。由a1973 mod m111,a2973 mod m342得x在模37和模49下的表达为（11,42）。5.3.2欧几里得算法欧几里得算法就是1.2.2中介绍的辗转相除法,利用欧几里得算法可以迅速地找出给定的两个整数a和b的最大公因数(a,b).在求得(a,b)的同时,还能给出满足(a,b)=ua+vb的两个常数u,v,当(a,b)=1时,利用欧几里得算法可找出两个常数u,v满足ua+vb=1,于是可得欧几里得（Euclid）算法是数论中的一个基本算法，是求两个正整数的最大公因子的简化过程。而推广的Euclid算法不仅可求两个正整数的最大公因子，而且当两个正整数互素时，还可求出其中一个数关于另一个数的乘法逆元。例 求gcd(1769,550)。gcd(1769,550)=1，550-1 mod 1769=550。5.3.3Wilson定理Wilson定理给出p是素数的一个 充要条件,此定理在理论上具有比较重要的价值.定理(Wilson):p是素数的充要条件是5.3.4欧拉函数设n是一正整数，小于n且与n互素的正整数的个数称为n的欧拉函数，记为(n)。例如：(6)=2，(7)=6，(8)=4。若n是素数，则显然有(n)=n-1。定义定义5.1 欧拉函数 是一个定义在正整数上的函数,的值等于序列0,1,2,m-1中与m互素的数的个数.定理定理5.4 若 和 互素,则定理定理5.5 若则定理5.6（Euler）若a和n互素，则a(n)1 mod n。证明：设R=x1,x2,x(n)是由小于n且与n互素的全体数构成的集合，aR=ax1 mod n,ax2 mod n,ax(n)mod n，对aR中任一元素axi mod n，因a与n互素，x1与n互素，所以axi与n互素，且axi mod nn，因此axi mod nR，所以aRR。又因aR中任意两个元素都不相同，否则axi mod n=axj mod n，由a与n互素知a在 mod n下有乘法逆元，得xi=xj。所以|aR|=|R|，得aR=R，所以 ，,，由每一xi与n互素，知 与n互素，在 mod n下有乘法逆元。所以a(n)1 mod n。(证毕）定理4.2(Fermat)若p是素数，a是正整数且gcd(a,p)=1，则ap-11 mod p。Fermat定理也可写成如下形式：设p是素数，a是任一正整数，则apa mod p。设p是一素数，a是小于p的正整数，称a是p的平方剩余，如果方程x2a(mod p)有解。否则称为非平方剩余。5.3.5 平方剩余和Jacobi符号例如：x21 mod 7有解x=1，x=6；x22 mod 7有解x=3，x=4；x23 mod 7无解；x24 mod 7有解x=2，x=5；x25 mod 7无解；x26 mod 7无解。可见共有3个数（1、2、4）是模7的平方剩余，且每个平方剩余都有两个平方根（即例中的x）。容易证明，模p的平方剩余的个数为(p-1)/2，且与模p的非平方剩余的个数相等。如果a是模p的一个平方剩余，那么a恰有两个平方根，一个在0到(p-1)/2之间，另一个在(p-1)/2到(p-1)之间。引理:若p是奇素数,则x2a(mod p)或无解或有两个模p不同余的解.定理5.8若p是奇素数,则整数1,2,p-1中正好有(p-1)/2个模p的平方剩余,其余的(p-1)/2个是模p的非平方剩余.定义5.3 设p是奇素数，a是一整数，勒让德符号 的定义如下：称符号 为Legendre符号。例如：定理5.9(欧拉准则)计算 有一个简单公式：例如：p=23，a=5，a(p-1)/2 mod p511 mod p=-1，所以5不是模23的平方剩余。Legendre符号有以下性质：定理5.10 设p是奇素数，a和b都不能被p除尽，则 若ab mod p，则证明从略。于是,对于任意整数n,总可表为于是而 ,所以对于任给一个整数n,计算 时,只需计算下面的三种值其中q是奇素数.定理5.11 p是任意奇素数,定理5.12 p是任意奇素数,定理5.13 p,q是两个不同的奇素数,以下定义的Jacobi符号是Legendre符号的推广。定义定义4.2 设n是正整数，且 ，定义Jacobi符号为其中右端的符号是Legendre符号。当n为素数时，Jacobi符号就是Legendre符号。Jacobi符号有以下性质：定理定理4.8 设n是正合数，a和b是与n互素的整数，则 若ab mod n，则对一些特殊的a，Jacobi符号可如下计算：定理定理4.9（Jacobi符号的互反律）设m、n均为大于2的奇数，则若mn3 mod 4，则 ；否则 。以上性质表明：为了计算Jacobi符号（包括Legendre符号作为它的特殊情形），并不需要求素因子分解式。例如105虽然不是素数，在计算Legendre符号 时，可以先把它看作Jacobi符号来计算，由上述两个定理得一般在计算 时，如果有必要，可用m mod n代替m，而互反律用以减小 的分母。可见，引入Jacobi符号对计算Legendre符号是十分方便的，但应强调指出Jacobi符号和Legendre符号的本质差别是：Jacobi符号 不表示方程x2a mod n是否有解。比如n=p1p2，a关于p1和p2都不是平方剩余，即x2a mod p1和x2a mod p2都无解，由中国剩余定理知x2a mod n也无解。但是，由于 ,所以 。即x2a mod n虽无解，但Jacobi符号 却为1。例例 考虑方程x22 mod 3599，由于3599=5961，所以方程等价于方程组由于 ，所以方程组无解，但Jacobi符号RSA算法是1978年由R.Rivest,A.Shamir和L.Adleman提出的一种用数论构造的、也是迄今为止理论上最为成熟完善的公钥密码体制，该体制已得到广泛的应用。5.4 RSA算法1.密钥的产生 选两个保密的大素数p和q。计算n=pq，(n)=(p-1)(q-1),其中(n)是n的欧拉函数值。选一整数e，满足1e(n)，且gcd(n),e)=1。计算d，满足de1 mod(n),即d是e在模(n)下的乘法逆元，因e与(n)互素，由模运算可知，它的乘法逆元一定存在。以e,n为公开钥,d,n为秘密钥。5.4.1 算法描述2.加密加密时首先将明文比特串分组，使得每个分组对应的十进制数小于n，即分组长度小于log2n。然后对每个明文分组m，作加密运算：cme mod n3.解密对密文分组的解密运算为：mcd mod n下面证明RSA算法中解密过程的正确性。证明：由加密过程知cme mod n，所以cd mod nmed mod nm1 mod(n)mod nmk(n)+1 mod n下面分两种情况：m与n互素，则由Euler定理得m(n)1 mod n,mk(n)1 mod n,mk(n)+1m mod n即cd mod nm。gcd(m,n)1，先看gcd(m,n)=1的含义，由于n=pq，所以gcd(m,n)=1意味着m不是p的倍数也不是q的倍数。因此gcd(m,n)1意味着m是p的倍数或q的倍数，不妨设m=xp，其中x为一正整数。此时必有gcd(m,q)=1，否则m也是q的倍数，从而是pq的倍数，与mn=pq矛盾。由gcd(m,q)=1及Euler定理得m(q)1 mod q，所以mk(q)1 mod q,mk(q)(p)1 mod q,mk(n)1 mod q因此存在一整数r，使得mk(n)=1+rq，两边同乘以m=xp得mk(n)+1=m+rxpq=m+rxn即mk(n)+1m mod n，所以cd mod nm。(证毕)例 选p=7，q=17。求n=pq=119，(n)=(p-1)(q-1)=96。取e=5，满足1e(n)，且gcd(n),e)=1。确定满足de=1 mod 96且小于96的d，因为775=385=496+1，所以d为77，因此公开钥为5，119，秘密钥为77，119。设明文m=19，则由加密过程得密文为c195 mod 1192476099 mod 11966解密为6677mod 119191.RSA的加密与解密过程RSA的加密、解密过程都为求一个整数的整数次幂，再取模。如果按其含义直接计算，则中间结果非常大，有可能超出计算机所允许的整数取值范围。如上例中解密运算6677 mod 119，先求6677再取模，则中间结果就已远远超出了计算机允许的整数取值范围。而用模运算的性质：(ab)mod n=(a mod n)(b mod n)mod n就可减小中间结果。RSA算法中的计算问题再者，考虑如何提高加、解密运算中指数运算的有效性。例如求x16，直接计算的话需做15次乘法。然而如果重复对每个部分结果做平方运算即求x，x2，x4，x8，x16则只需4次乘法。求am可如下进行，其中a，m是正整数：将m表示为二进制形式bk bk-1b0，即m=bk2k+bk-12k-1+b12+b0因此例如：19=124+023+022+121+120，所以a19=(a1)2a0)2a0)2a1)2a1从而可得以下快速指数算法_平方-和-乘法：z=1；For i=k downto 0 d0 z=(zz)mod n;if bi=1 then z=(za)mod nreturn z.其中z是中间结果，z的终值即为所求结果。例5.10 求152013 mod 2537。将13表示为1101，i=3,z=1*1*1520=1520(mod2537),i=2,z=1520*1520*1520=1268(mod2537),i=1,z=1268*1268=1903(mod2537),i=0,z=1903*1903*1520=95(mod2537),所以152013 mod 2537=95。RSA密钥的产生产生密钥时，需要考虑两个大素数p、q的选取，以及e的选取和d的计算。因为n=pq在体制中是公开的，因此为了防止敌手通过穷搜索发现p、q，这两个素数应是在一个足够大的整数集合中选取的大数。如果选取p和q为10100左右的大素数，那么n的阶为10200，每个明文分组可以含有664位（102002664），即83个8比特字节，这比DES的数据分组（8个8比特字节）大得多，这时就能看出RSA算法的优越性了。因此如何有效地寻找大素数是第一个需要解决的问题。寻找大素数时一般是先随机选取一个大的奇数（例如用伪随机数产生器），然后用素性检验算法检验这一奇数是否为素数，如果不是则选取另一大奇数，重复这一过程，直到找到素数为止。素性检验算法通常都是概率性的，但如果算法被多次重复执行，每次执行时输入不同的参数，算法的检验结果都认为被检验的数是素数，那么就可以比较有把握地认为被检验的数是素数。例如后面将介绍的Miller-Rabin算法。可见寻找大素数是一个比较繁琐的工作。然而在RSA体制中，只有在产生新密钥时才需执行这一工作。p和q决定出后，下一个需要解决的问题是如何选取满足1eq，由(n)=(p-1)(q-1)，则有p+q=n-(n)+1以及由此可见，由p、q确定(n)和由(n)确定p、q是等价的。为保证算法的安全性，还对p和q提出以下要求：（1）|p-q|要大如果|p-q|小，则 也小，因此，稍大于n。可得n的如下分解步骤：顺序检查大于 的每一整数x，直到找到一个x使得x2-n是某一整数（记为y）的平方。由x2-n=y2，得n=(x+y)(x-y)。(2)p-1和q-1的最大公约数d=(p-1,q-1)应尽量的小.否则,将有 个整数b,使得n对基b是伪素数,这就增大了将n因数分解的可能性.(3)p-1和q-1都应有大素因子,p+1和q+1都应有大素因子,否则就容易因数分解.综合上述,我们定义强素数p如下:条件(1):条件(2):其中r,s,t,p均为大素数.此外,还因为RSA算法存在着可能的重复加密攻击法。设攻击者截获密文c，可如下进行重复加密：若 ，即 ，则有 ，即 ，所以在上述重复加密的倒数第2步就已恢复出明文m，这种攻击法只有在t较小时才是可行的。为抵抗这种攻击，p、q的选取应保证使t很大。设m在模n下阶为k，由 得 ，所以k|(et-1)，即et1(mod k)，t取为满足上式的最小值（为e在模k下的阶）。又当e与k互素时t|(k)。为使t大，k就应大且(k)应有大的素因子。又由k|(n)，所以为使k大，p-1和q-1都应有大的素因子。此外，研究结果表明，如果en且d1,如果一个合数如果一个合数n满足满足则称则称n是一个以是一个以a为底的伪素数为底的伪素数.定理定理:对每一个整数对每一个整数a1,均有无限多个以均有无限多个以a为底的伪素数为底的伪素数.w以a为底的伪素数虽然有无穷多个,但在某 一区间内,比素数少得多.例如,小于109的素数有50847543个,但仅有5597个以2为底的伪素数.只有685个小于109的伪素数n,同时满足以2,3,5为底的伪素数.95产生素数的方法可分为以下两类:1.确定性素数产生法:(1)基于Pocklington定理的确定性素数产生方法,它需要已知n-1的部分素因子.定理5.20(Pocklington定理)设n=RF+1,这里是不同的素数,若存在a满足:那么n的每一素因子p都有p=F*m+1的形式,m大于等于1,于是若 ,则n为素数.(2)基于Lucas定理的确定性素数产生方法,它需要已知n-1的全部素因子.定理5.21(Lucas定理)设n为正整数,若存在a满足:问题给定一个整数n,如何有效的判定n为素数.Efficiently=in time a polynomial in number of digits=(log n)c for some constant c素数判定有多项式时间算法吗?一直以来是一个颇受关注的问题.试除法用小于等于 n1/2的每一个整数试除.大约在 230 BC时就知道(Sieve of Eratosthenes)所需计算时间:O(n1/2).当n是合数时也可以得到n的一个因子.试除法速度太慢w对于大整数利用试除法判定是不可能的.例如:对于一个100位的大整数,需要 1050 次除法.有更快的判定素数的方法吗?w虽然做过很多尝试,在AKS算法出现之前都没能获得成功.For example,Wilson(18th century)showed:N is prime iff(n-1)!=-1(mod n)This requires n-3 multiplicationsFermat定理if n is prime then for any a:an=a(mod n).It is easy to check:Compute a2,square it to a4,square it to a8,Needs only O(log n)multiplications.能否利用Fermat定理判定素数?wFor a“few”as test if an=a(mod n);wif yes,output PRIME else output COMPOSITE.但是没能成功For n=561=3*11*17,all as satisfy the equation!PRIMES in P(almost)w1983 Adleman,Pomerance,and Rumely 给出了一个确定性算法所需计算时间为O(log n)c log log log n).PRIMES is in P 直到2002年，由Manindra Agrawal,Neeraj Kayal and Nitin Saxena提出的AKS算法，才为我们提供了一个可以在多项式时间内完成对指定数进行素数判定的确定性算法，该算法的运行时间为 .主要想法:w想法还是源于 Fermats 定理.w然而:如果直接模 n(ring Z/nZ)运算没有很好的结果可以利用.于是将环扩展到更大的环上希望有更好的结果可以利用.最终考虑多项式模 n 和 Xr1,即环Z/nZX/(Xr-1).推广的fermat定理如果n是素数,则对任意的a有:(X+a)n=Xn+a(mod n,Xr-1).Proof:If n is prime,n divides for every i,0 i n.If n is composite,then n does not divide for any prime p dividing n.一个可能的测试如果对于任意给定的n,都存在一个小 r 和很少的 a,满足推广的fermat定理,要是能判定出n是素数,则可得到一个好的素性判定方法,这就是AKS算法.w很容易证明:如果选择一个合适的小”r”,对每一个0 a 1w if()输出合数；w r=2；w while(rn)w if(gcd(n,r)1)输出合数;w if(r素数)w 设q为r-1的最大素因子；如果如果 break；r=r+1；for a=1 to s=如果如果 输出合数；输出合数；输出素数输出素数；2.素数判定的概率多项式算法w在这之后不久,Rabin 修改 Millers 的算法得到了一个概率多项式算法.当n是合数时,只以很小的概率出错.w1973 Solovay-Strassen也得到了一个概率多项式算法.当n是合数时,也只以很小的概率出错.下面介绍这两种常用的概率算法:概率性素数产生法w这一类算法研究较多,是当今生成大素数的主要算法.w(1)Solovay-Strassen素性测试w定义定义5.6 设n为奇数,(b,n)=1,若定理定理5.22设n为奇合数,则在 中至少有一半的整数b使Solovay-Strassen素性测试算法如下:1)从 中随机且均匀地产生一数a;2)计算gcda,n;3)若gcda,n1,则n非素数;4)计算5)若(2)Miller-Rabin素性测试w定义5.7设n为正整数,其中l是非负整数,m是正奇数,若存在正整数a,使得定理定理5.23 若p是素数,a是正整数,(p,a)=1,则p关于a通过Miller检验.Miller-Rabin素性测试如下():1)在1,2,n-1中随机均匀地产生一数b;2),若z=1或z=n-1,则n通过测试,结束;3)若j=l,则n非素数,结束,否则转4);4),若z=n-1,则n通过测试,结束,否则转3).定理定理5.24 若n是奇合数,则n通过以b为基的Miller-Rabin测试的数目最多为RSA存在以下两种攻击，并不是因为算法本身存在缺陷，而是由于参数选择不当造成的。1.共模攻击在实现RSA时，为方便起见，可能给每一用户相同的模数n，虽然加解密密钥不同，然而这样做是不行的。5.8对RSA中小指数的攻击设两个用户的公开钥分别为e1和e2，且e1和e2互素（一般情况都成立），明文消息是m，密文分别是c1me1(mod n)c2me2(mod n)敌手截获c1和c2后，可如下恢复m。用推广的Euclid算法求出满足re1+se2=1的两个整数r和s，其中一个为负，设为r。再次用推广的Euclid算法求出c-11，由此得(c-11)-rcs2m(mod n)。2.低解密指数攻击低解密指数攻击对RSA低解密指数d的攻击,主要是Wiener的工作.1990年,Wiener利用数论中连分数的一个基本性质,证明了如下的结果:定理定理5.28 设n=pq,e是加密指数,d是解密指数,如果则密码分析者可通过n,e,有效的求出d.3.低加密指数攻击低加密指数攻击假定将RSA算法同时用于多个用户（为讨论方便，以下假定3个），然而每个用户的加密指数（即公开钥）都很小。设3个用户的模数分别为ni(i=1,2,3)，当ij时，gcd(ni,nj)=1，否则通过gcd(ni,nj)有可能得出ni和nj的分解。设明文消息是m，密文分别是c1m3(mod n1)c2m3(mod n2)c3m3(mod n3)由中国剩余定理可求出m3(mod n1n2n3)。由于m3n1n2n3，可直接由m3开立方根得到m。一般地结论:定理定理5.30 设k个部门的k个RSA公钥密码体制为:,i=1,k,如果k大于等于e,当向k个部门同时发明文m,并用每个部门的对m加密,则密码分析者可通过任意的e个密文有效的求出m.证明:略.(利用孙子定理).对RSA密码体制，n被分解成功，该体制便被破译，即破译RSA的难度不超过大整数的分解。但还不能证明破译RSA和分解大整数是等价的，虽然这一结论已得到普遍共识。Rabin密码体制已被证明对该体制的破译与分解大整数一样困难。5.9 Rabin密码体制密码体制Rabin密码体制是对RSA的一种修正，它有以下两个特点：它不是以一一对应的陷门单向函数为基础，对同一密文，可能有两个以上对应的明文;破译该体制等价于对大整数的分解。RSA中选取的公开钥e满足1e(n)，且gcd(e,(n)=1。Rabin密码体制则取e=2。1.密钥的产生随机选择两个大素数p、q，满足pq3 mod 4，即这两个素数形式为4k+3；计算n=pq。以n作为公开钥，p、q作为秘密钥。2.加密cm2 mod n其中m是明文分组，c是对应的密文分组。3.解密解密就是求c模n的平方根，即解x2c mod n，由中国剩余定理知解该方程等价于解方程组由于pq3 mod 4，下面将看到，方程组的解可容易地求出，其中每个方程都有两个解，即xm mod p,x-m mod pxm mod q,x-m mod q经过组合可得4个同余方程组由中国剩余定理可解出每一方程组的解，共有4个，即每一密文对应的明文不惟一。为了有效地确定明文,可在m中加入某些信息,如发送者的身份号、接收者的身份号、日期、时间等。下面证明，当pq3 mod 4，两个方程x2c mod p,x2c mod q的平方根都可容易地求出。由p3 mod 4得，p+1=4k，即(p+1)/4是一整数。因c是模p的平方剩余，故所以 和 是方程x2c mod p的两个根。同理 和 是方程x2c mod q的两个根。下面讨论，求解方程x2a mod n与分解n是等价的，所以破译Rabin密码体制的困难程度等价于大整数n的分解。设n是两个大素数p和q的乘积。设a是模n的平方剩余，即存在x使得x2a mod n成立，于是a既是模p的平方剩余，又是模q的平方剩余，所以存在y、z，使得(y)2a mod p,(z)2a mod q，因此xy mod p,xz mod q由中国剩余定理可求得a mod n的4个平方根，记为u mod n和w mod n，且uw mod n。以上结果表明，已知n的分解n=pq，且a是模n的平方剩余，就可求得a mod n的4个平方根。下面考虑相反的问题，即已知a mod n的两个不同的平方根（u mod n和w mod n，且uw mod n），就可分解n。事实上由u2w2 mod n得(u+w)(u-w)0 mod n，但n不能整除u+w也不能整除u-w，所以必有p|(u+w),q|(u-w)或p|(u-w),q|(u+w)所以gcd(n,u+w)=p,gcd(n，u-w)=q或gcd(n,u-w)=p,gcd(n,u+w)=q因此得到了n的分解式。将以上讨论总结为：定理定理 求解方程x2a mod n与分解n是等价的。5.10 RSA在有限域在有限域Fp上多项式上的推广上多项式上的推广w1.最高公因式的概念w2.同余w3.完全剩余系w4.缩系w5.欧拉函数159w定理定理5.32 设f(x)是Fp上的n次多项式,其标准分解为 为不可约多项式,且 的次数为 则有1605.10.2 RSA在Fp上的多项式上的推广161162Fp上的多项式相乘，就是求Fp上的序列的卷积，它也可用快速数论变换来计算然而，Berlekamp曾经给出Fpx上n次多项式分解的算法,其计算量为 ,这样对给定的p而言,这一算法确实给出了Fpx多项式分解的多项式算法,因此,这个密码体制是不安全的.但当p很大时,实际分解Fpx上的多项式依然十分困难,因此,仍可以构作安全的密码体制.这个例子告诉我们,理论上,可以认为具有多项式时间的算法是有效的,但在实际问题中往往不是这样.163