RSA算法的数论基础

RSA算法的数论基础一、公钥密码体制基础一个好的密码体系的必要条件是合法用户能够很容易对秘密消息进行加密和解密，而这些过程对于其他人则是非常难的。公钥密码体制的实现基于单向陷门函数。单向陷门函数：设f是一个函数，t是与f有关的一个参数。对于任意给定的x，计算y，使得y=f(x)是容易的。如果当不知道参数t时，计算f的逆函数-1f是难解的。但当知道参数t时，计算f的逆函数-1f是容易的。则称f是一个单向陷门函数，参数t称为陷门。二、RSA算法的安全基础计算机科学家Rivest、Shamir和Adleman提出了基于素性检测和整数分解的第一个使用公钥密码体制。算法的安全性建立这一数论难题基础上：将两个大素数相乘是容易计算的，而将该乘积分解成两个大素数因子是困难的。素性检测问题：检测n的素性的最好额判定算法运行时间为nclogloglognlog，关于输入长度nlog呈超越多项式速度增长。整数因子分解问题：分解一个一般的整数n的最好的算法运行时间为3231nloglognloge，关于输入长度nlog呈亚指数速度增长。三、RSA算法实现的基础定理算术基本定理：任何大于1的整数n能被因式分解为如下唯一形式：n=p1p2…pl(p1,p2，…，pl为素数）费马小定理：若p是素数，a与p互素，则pmod1a1-p欧拉定理：欧拉函数n表示不大于n且与n互素的正整数的个数。当n是素数，1-nn。qpn,p,q均为素数时，则1-q1-pqpn对于互素的a和n，有nmod1an四、RSA算法的实现1.密钥的产生①选两个互异的大素数p和q。②计算n=p×q，φ(n)=(p-1)(q-1)，其中φ(n)是n的欧拉函数值。③选一随机整数e，满足1eφ(n)，且gcd(φ(n),e)=1。④计算d，满足d·e≡1modφ(n)，即d是e在模φ(n)下的乘法逆元，因e与φ(n)互素，由模运算可知，它的乘法逆元一定存在。⑤以{e,n}为公开钥,{d,p,q}为秘密钥。2.加密加密时首先将明文比特串分组，使得每个分组对应的十进制数小于n，即分组长度小于n2log。然后对每个明文m，作加密运算：nmodmce3.解密对密文分组的解密运算为：nmodcmd五、证明RSA算法中解密过程的正确性设p，q是不同的素数，n=pq记φ(n)=(p-1)(q-1),如果e，d是与φ(n)互素的两个正整数（e,dφ(n)),并满足ed≡1(modφ(n)),则对于每个整数x,都有nmodxxed。分析：为了证明nmodxxed，只要证明φ(n)是x-xed的因数即可。又因为n=pq，而p，q都是素数，故只要证明p和q都是x-xed的因数即可，即pmodxxed（1）qmodxxed（2）证明：证明式1，若p是x的因数则式1必然成立若p不是x的因数，则由ed≡1(modφ(n))得ed-1=k(p-1)(q-1),k为任意整数则1-qk1-p11-pkedxxxxq根据费马小定理因为x与p互素所以pmod1x1-p所以pmodxxxx1-qk1-ped同理可证qmodxxed即证nmodxxed六、RSA算法中的计算问题1.模运算性质RSA的加密、解密过程的运算都为求一个整数的整数次幂，再取模。如果按其含义直接计算，则中间结果非常大，有可能超出计算机所允许的整数取值范围。而用模运算的性质：(a×b)modn=[(amodn)×(bmodn)]modn就可减小中间结果。2.模重复平方计算法例如求16x，直接计算的话需做15次乘法。然而如果重复对每个部分结果做平方运算即求x，2x，4x，8x，16x则只需4次乘法。3、乘法逆元的求法（欧几里德算法）整数e，满足1eφ(n)，且gcd(φ(n),e)=1计算d，满足d·e≡1modφ(n)，即d是e在模φ(n)下的乘法逆元，因e与φ(n)互素，它的乘法逆元一定存在。求法可用欧几里得算法。七、素性判定在建立RSA密码的过程中，需要生成大量的随机素数，一般是先生成大量的随机整数，再通过算法检测其是否为素数。判别给定的正整数是否素数简称素性判定。举例Miller-Rabin素性检验：给定奇整数3n和安全参数k写t21-ns，其中t为奇整数1.随机选取整数b，2-nb22.计算nmodbrt03.(a)如果1r0或1-nr0，则通过检验，可能为素数。回到1.继续选取另一个随机整数b，2-nb2(b）否则，有1r0以及1-nr0，计算nmodrr2014.(a)如果1-nr1，则通过检验，可能为素数。回到1.继续选取另一个随机整数b，2-nb2(b）否则，有1-nr1，计算nmodrr212如此继续下去。需要检测多少个随机整数（特定）才能找到一个素数。定义x为不超过x的素数的个数，素数定理：1Inxxxlimx在1~x中随机选取一个整数，其为素数的概率大约为1/Inx。八、因子分解分解任意正整数n是，要寻找n的一个非平凡因子。对RSA的公开模数n，找到其任意一个非平凡因子即意味这彻底分解n和该RSA密码的破解。举例Pollardp-1分解算法：1.选择一个界B2.选择一个整数k，k是大部分b的乘积满足Bb3.选择一个随机整数2-na24.计算nmodark5.计算d=gcd(r-1,n)6.如果1dn，d就是n的非平凡因子；如果d=1或d=n就回到2.九、RSA算法的安全性如果RSA的模数n被成功地分解为p×q，则获得φ(n)=(p-1)(q-1)，从而攻击者能够从公钥e解出d，即nmoded-1，则攻击成功。随着人类计算能力的不断提高，原来被认为是不可能分解的大数已被成功分解。因此，RSA算法的安全要求：n的长度在1024－2048比特p和q的长度相差不能太多p-1和q-1都应该包含大的素数因子p-1和q-1的最大公因子要尽可能小十、读书感悟在对RSA算法这一问题进行查资料时，我发现它的算法竟都是我们学过的知识，只不过将其都结合了起来。信安数学课程中的书本知识和课堂内容都应用在了RSA算法实现中，所有基本定理甚至与各种证明与判定几乎都在课本中有所体现。在之前了解到RSA的时候，还不能理解它是如何实现的，而在学习了数论基础后，竟能对其的算法实现更为明了。这样的读书学习更让我对课本上知识点的运用和理解有所提高，收获丰富。