RSA算法描述

2．RSA算法 RSA算法需要以下相关的数学概念： 素数：素数是一个比1大，其因子只有1和它本身，没有其它数可以整除它的数。素数是无限的。例如，2，3，5，7……等。 两个数互为素数：指的是它们除了1之外没有共同的因子。也可以说这两个数的最大公因子是1。例如，4和9，13和27等。 模运算：如A模N运算，它给出了A的余数，余数是从0到N-1的某个整数，这种运算称为模运算。 RSA加密算法的过程如下： （1）取两个随机大素数p和q（保密） （2）计算公开的模数r=pq(公开) （3）计算秘密的欧拉函数ϕ (r) =（p-1）(q-1)（保密），两个素数p和q不再需要，应该丢弃，不要让任何人知道。 （4）随机选取整数e，满足gcd(e, ϕ (r))=1(公开e，加密密钥) （5）计算d，满足de≡1(mod ϕ (r))(保密d，解密密钥，陷门信息) （6）将明文x（其值的范围在0到r-1之间）按模为r自乘e次幂以完成加密操作，从而产生密文y（其值也在0到r-1范围内） y=xe (mod r) （7）将密文y按模为r自乘d次幂，完成解密操作 x=yd (mod r) 下面用一个简单的例子来说明RSA公开密钥密码算法的工作原理。 取两个素数p=11，q=13，p和q的乘积为r=p×q=143，算出秘密的欧拉函数ϕ (r)=(p-1)×(q-1)=120，再选取一个与ϕ (r)=120互质的数，例如e=7，作为公开密钥，e的选择不要求是素数，但不同的e的抗攻击性能力不一样，为安全起见要求选择为素数。对于这个e值，可以算出另一个值d=103，d是私有密钥，满足e×d=1 mod ϕ (r)，其实7×103=721除以120确实余1。欧几里德算法可以迅速地找出给定的两个整数a和b的最大公因数gcd（a，b），并可判断a与b是否互素，因此该算法可用来寻找解密密钥。 120=7×17+1 1=120-7×17 mod 120=120-7×(-120+17) mod 120==120+7×103 mod 120 (n,e) 这组数公开，(n,d)这组数保密。 设想需要发送信息x=85。利用(n,e)=(143,7)计算出加密值： y= xe (mod r)=857 mod 143=123 收到密文y=123后，利用 (n,d)=(143,103)计算明文： x=yd (mod r) =123103mod 143=85 加密信息x（二进制表示）时，首先把x分成等长数据块 x1 ,x2,..., xi ，块长s，其中 2s ≤ n，s尽可能的大。对应的密文是： yi = xie ( mod r ) 解密时作如下计算： xi = yid ( mod r ) RSA算法中的难点有以下几点： （1）大数的运算 上百位大数之间的运算是实现RSA算法的基础，因此程序 设计 领导形象设计圆作业设计ao工艺污水处理厂设计附属工程施工组织设计清扫机器人结构设计 语言本身提供的加减乘除及取模算法都不能使用，否则会产生溢出，必须重新编制算法。在编程中要注意进位和借位，并定义几百位的大数组来存放产生的大数。 （2）素数的产生 Hadamard证明，当X变得很大时，从2到X区间的素数数目π(X)与X/ln(X)的比值趋近于1，即： 如果在2到X之间随机选取一个整数，其为素数的概率大约为1/ln(X)。对于1024位的模数r=pq，p和q将选取为512位的素数。一个随机选取的512位整数为素数的概率大约为1/ln2512≈ 1/355。 目前，适用于RSA算法的最实用的素数生成办法是概率测试法。该法的思想是随机产生一个大奇数，然后测试其是否满足一定的条件，如满足，则该大奇数可能是素数，否则是合数，经过充分多次运行该算法，把合数判断为素数的概率可以降低到任何所期望的值以下。如solovay和strassen的简明素性概率检测法。目前也存在多项式时间的确定性算法来判断一个数是否为素数。 （3）高次幂剩余的运算 要计算xe mod r，因x、e、r都是大数而不能采用先高次幂再求剩余的 方法 快递客服问题件处理详细方法山木方法pdf计算方法pdf华与华方法下载八字理论方法下载 来处理，而要采用平方取模的算法，即每一次平方或相乘后，立即取模运算。设e可表示为： e = bk 2k + bk-1 2k-1 + ... + bi 2i + ... + b2 22 + b1 2 + b0 　 那么有如下的计算xe算法： Square-and-Multiply(x,e,r) Z=1 For i=k downto 0 Do z=z*z mod r if bi=1 then z=z*x mod r Return(z) 　 RSA的安全性在理论上存在一个空白，即不能确切知道它的安全性能如何。我们能够做出的结论是：对RSA的攻击的困难程度不比大数分解更难，因为一旦分解出r的因子p、q，就可以攻破RSA密码体制。对RSA的攻击是否等同于大数分解一直未能得到理论上的证明，因为没能证明破解RSA就一定需要作大数分解。目前，RSA的一些变种算法已被证明等价于大数分解。不管怎样，分解n是最显然的攻击方法。1977年，《科学美国人》杂志悬赏征求分解一个129位十进数(426比特)，直至1994年3月才由Atkins等人在Internet上动用了1600台计算机，前后花了八个月的时间才找出答案。现在，人们已能分解155位（十进制）的大素数。因此，模数n必须选大一些，因具体适用情况而定。 若r=pq被因子分解，则RSA便被击破。 因为若p，q已知，则ϕ (r) =（p-1）(q-1)便可算出。解密密钥d关于e满足： de≡1(mod ϕ (r) ) 故d便也不难求出。因此RSA的安全依赖于因子分解的困难性。目前因子分解数度最快的方法，其时间复杂度为exp(sqrt(ln(n)lnln(n)))。 RSA实验室认为，512比特的r已不够安全。他们建议，现在的个人应用需要用768比特的r，公司要用1024比特的r，极其重要的场合应该用2048比特的r。 总之，随着硬件资源的迅速发展和因数分解算法的不断改进，为保证RSA公开密钥密码体制的安全性，最实际的做法是不断增加模r的位数。 为了安全起见，对p，q还要求：p，q长度差异不大；p-1和q-1有大素数因子；（p-1，q-1）很小。满足这些条件的素数称作安全素数。 其他的安全问题包括： （1）公共模数攻击。每个人具有相同的r，但有不同的指数e和d，这是不安全的。 （2）低加密指数攻击。如果选择了较低的e值，虽然可以加快计算速度，但存在不安全性。 （3）低解密指数攻击。如果选择了较低的d值，这是不安全的。 （4）选择密文攻击。如A想让T对一个T不愿意签名的消息m’签名，A首先选择一个任意值x，计算y=xe（mod r），然后要求T对m=ym’签名，A最后计算(md mod r)x-1 mod r =( ym’) d x-1mod r= m’d mod r。记住不要对别人提交的随机消息进行签名。 RSA的缺点主要有： （1）产生密钥很麻烦，受到素数产生技术的限制，因而难以做到一次一密。 （2）分组长度太大，为保证安全性，n 至少也要 600 bits以上，使运算代价很高，尤其是速度较慢，较对称密码算法慢几个数量级；且随着大数分解技术的发展，这个长度还在增加，不利于数据格式的 标准 excel标准偏差excel标准偏差函数exl标准差函数国标检验抽样标准表免费下载红头文件格式标准下载 化。目前，SET(Secure Electronic Transaction)协议中要求CA采用2048比特长的密钥，其他实体使用1024比特的密钥。 （3）RSA的速度由于进行的都是大数计算，使得RSA最快的情况也比DES慢上100倍，无论是软件还是硬件实现。速度一直是RSA的缺陷。一般来说只用于少量数据加密。RSA与DES的优缺点正好互补。RSA的密钥很长，加密速度慢，而采用DES，正好弥补了RSA的缺点。即DES用于明文加密，RSA用于DES密钥的加密。由于DES加密速度快，适合加密较长的报文；而RSA可解决DES密钥分配的问题。美国的保密增强邮件（PEM）就是采用了RSA和DES结合的方法，目前已成为E-MAIL保密通信标准。