RSA算法的数论基础分析

RSA算法的数论基础分析摘要：RSA算法作为目前使用最广泛的一种非对称密码算法，应用广泛，RSA主要用来加密比较简短的数据，而加密大量数据的是对称密码，而对称密码的密钥传递则需要非对称密码算法来实现，RSA算法采用的单向函数是整数因式分解问题。两个大素数相乘在计算上是非常简单的，但对于其乘积结果进行因式分解确是非常困难的，在论证RSA的安全性方面，数论知识在RSA中发挥着至关重要的作用。关键词：RSA算法数论RSA加密和解密都是在Zn（剩余类集）中完成的，模运算在其中发挥着核心作用，使用RSA算法的具体过程如下：选择两个大素数p和q，计算n=pq，计算s=(p-1)(q-1),任意选择一个满足以下两个条件的e，第一个是0es,第二个是gcd（e，s）=1，即e和s互素，找到e之后计算满足以下条件的私钥d，这个条件就是de=1mods，这样最终得到三个数：n、d、e，下面就要利用公钥对于明文x进行加密，密文y=xemodn,然后在利用密钥d进行解密，x=ydmodn，在对称加密中：ne两个数构成公钥，可以告诉别人；d构成私钥，自己保留，不让任何人知道。给别人发送的信息使用e加密，只要别人能用d解开就证明信息是你发送的，构成了签名机制。别人给你发送信息时使用d加密，这样只有拥有e的你能够对其解密。对于RSA算法应该满足以下几点：1.对于给定的公钥e和n，确定私钥d在计算上必须是不可行的，这一点肯定是满足的，因为这是所有密码算法的特点，利用大素数分解的难题来实现私钥d的难计算性来实现密钥的难计算性。2.由于明文x唯一地取决于模数n的大小，所以一次RSA加密的位数不能超过n的位长度（也就是把n用二进制表示的长度），3.计算xemodn和ydmodn应该相对简单，计算一个数对于n的余数比较简单，但是计算Xe和Yd只利用乘法是比较困难的，先进行平方运算在进行乘法运算使X和Y的指数达到e和d是需要进行很多乘法运算，因为为了保证密码的安全性通常情况下选择的e或者d其中之一会在1024到3072位之间或者更大，如果只进行一次平方，以后的运算都靠乘法，至少要进行21024或更多次的乘法。聪明的人类发明了一种平方乘算法，利用指数的2进制表示形式，依据一定的规则，可以对于一个底数轻松地计算它的任意阶幂，而且很容易用代码实现。4.给定一个n应该对应很多公钥和私钥对，避免攻击者发起蛮力攻击，找到一个满足条件的n也是数论关注的内容，密钥生成过程中的p和q的积就是RSA的模数n，并且它们的长度应该都是n的位长度的一半，最通用的方法就是随机生成整数，并检查它们的素性，为了使该方法可行，我们必须关注两个问题，经过多少次测试才可以找到这个素数，以及检查一个随机整数是不是素数的速度。随着数值的增加，素数的密度变得稀疏，随机选择的一个整数b为素数的概率遵循一个著名的素数理论，而且接近1/ln𝑏,并且只检查奇数会使得概率加倍，也就是2/ln𝑏,要做的另一个步骤是如何确定随机生成的整数b是不是素数，最直接的想法是对被测整数进行因式分解，但是由于p和q太大，但是我们关注的是这个数是不是素数，而不是它是否可以分解，这里就只介绍一种方法Miller-Rabin素性测试，基于以下定理（给定一个奇素数b，b−1=2𝑢𝑟，其中r是奇数，如果可以找到一个整数a，使得𝑎𝑟≠1𝑚𝑜𝑑𝑏，并且𝑎𝑟2𝑗≠𝑏−1𝑚𝑜𝑑𝑏，对所有的j={0,1,2，……,u-1}都成立，则b是一个合数，否则它可能是一个素数）RSA的安全性在于对于一个大数n，没有有效的方法能够将其分解，从而在已知n,e的情况下无法获得d；同样在已知n,d的情况下无法求得e。最常见的情况是随机产生一个对称加密的密钥，然后使用对称加密算法对信息加密，之后用RSA对刚才的加密密钥进行加密。当前小于1024位的N已经被证明是不安全的，自己使用中不要使用小于1024位的RSA，最好使用2048位的。此外简单介绍几个有关于RSA的数论知识，主要是费马小定理和扩展的欧几里得算法。假设a为一个整数，p为一个素数，则ap=amodp，也可以表示成以下形式，ap-1=1modp，还可以转化成乘法逆元的定义a-1=ap-2modp，将费马小定理的模数推广到任何整数模，即p不是素数，gcd（a，m）=1，则有𝑎𝜑(𝑚)=1𝑚𝑜𝑑𝑚，还有扩展的欧几里得算法，除了用来计算gcd之外，还能计算以下形式的线性组合：gcd（r0，r1）=sr0+tr1，也就是辗转相除法的变形形式。参考文献：1.深入浅出密码学——常用加密技术原理与应用（安全技术经典译丛），作者（美）帕尔，（美）佩尔茨尔著，马小婷译，清华大学出版社，2012-9-12.数论和密码学教程作者（美）科布科茨著，世界图书出版公司，2008-1-1