开发者社区> 问答> 正文

RSA算法的攻击进度

RSA算法的攻击进度

展开
收起
知与谁同 2018-07-21 13:49:53 1368 0
1 条回答
写回答
取消 提交回答
  • 杀人者,打虎武松也。

    针对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;        }    }}

    2019-07-17 22:56:04
    赞同 展开评论 打赏
问答分类:
问答地址:
相关产品:
问答排行榜
最热
最新

相关电子书

更多
数据+算法定义新世界 立即下载
袋鼠云基于实时计算的反黄牛算法 立即下载
Alink:基于Apache Flink的算法平台 立即下载