针对RSA最流行的攻击一般是基于大数因数分解。1999年,RSA-155(512bits)被成功分解,花了五个月时间(约8000 MIPS 年)和224 CPU hours 在一台有3.2G中央内存的Cray C916计算机上完成。
2002年,RSA-158也被成功因数分解。
2009年12月12日,编号为 RSA-768 (768bits,232 digits)数也被成功分解。
北京时间2013年2月15日上午消息,据《纽约时报》周二报道,欧美数学家和密码学家偶然发现,被全世界广泛应用的公钥加密算法RSA存在漏洞。
他们发现,在700万个实验样本中有2.7万个公钥并不是按理论随机产生的。也就是说,或许有人可以找出产生公钥的秘密质数。
该研究项目是由美国独立密码学家James P.Hughes和荷兰数学家Arjen K. Lenstra牵头的。他们的报告称:“我们发现绝大多数公钥都是按理论产生的,但是每一千个公钥中会有两个存在安全隐患。”
报告称,为防止有人利用该漏洞,有问题的公钥已从公众访问的数据库中移除。为确保系统的安全性,网站需要在终端做出改变。
公式和定理
数和互为素数
任何大于1的整数a能被因式分解为如下唯一形式:
a=p1p2…pl(p1,p2,…,pl为素数)
二、模运算
①{[a(mod n)]×[b(mod n)]}modn≡(a×b)(mod n)
②如果(a×b)=(a×c)(mod n),a与n互素,则
b=c(mod n)
三、费马定理
若p是素数,a与p互素,则
a^(p-1)≡1 (mod p)
四、欧拉定理
欧拉函数φ(n)表示不大于n且与n互素的正整数的个数。
当n是素数,φ(n)=n-1。n=pq,p,q均为素数时,则φ(n)= φ(p)φ(q)=(p-1)(q-1)。
对于互素的a和n,有a^φ(n)≡1(mod n)
如何利用计算机程序从公钥e,以及φ(n)求得私钥d?
问题可以化为求: e *x +φ(n)* y = 1 类型的方程,利用扩展欧几里得算法求解
(下面是该问题的java实现) //例子为算47 * x + 30 * y ==1 的解public class Exercise{ public static void main(String[] args) { int[] p = new int[2]; int a = 47; int b = 30; RSA(a,b,p); System.out.print("p[0] is: " + p[0] + ";p[1] is:" + p[1]);//p1为私钥 } public static int[] RSA(int a,int b,int[] p)//这里假设a > b { if(a%b == 1) { p[0] = 1; p[1] = -(a - 1) / b; return p; } else { RSA(b,a % b,p); int t = p[0]; p[0] = p[1]; p[1] = t - (a / b) * p[1]; return p; } }}
版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。