欢迎来到 黑吧安全网 聚焦网络安全前沿资讯,精华内容,交流技术心得!

记一次RSA破解

来源:本站整理 作者:佚名 时间:2018-04-12 TAG: 我要投稿

最近好久没更新博客,因为在忙着考雅思还有一直也在看CTF(=_=上个星期玩了一下腾讯的CTF……这酸爽,我一直都认为比赛是最容易提升自己实力的一种途径,上次比赛也发现了自己的不足,继续努力吧少年),今天看了一天的RSA算法。以前在上课的时候,记得老师光讲这个算法就讲了有两堂课。现在在看一下其实也不是很难(别骗自己了=_=),所以写这篇文章记录一下,顺便加深一下自己的印象。
0×1
首先开始之前我们要补充一下关于RSA的一些常识。
(1)选择一对不同的、足够大的素数p,q。
(2)计算n=pq。
(3)计算f(n)=(p-1)(q-1),同时对p, q严加保密,不让任何人知道。
(4)找一个与f(n)互质的数e,且1
(5)计算d,使得de≡1 modf(n)。这个公式也可以表达为(d*e-1)% f(n)=0
     这里要解释一下,≡是数论中表示同余的符号。公式中,≡符号的左边必须和符号右边同余,也就是两边模运算结果相同。
     显而易见,不管f(n)取什么值,符号 右边1 mod f(n)的结果都等于1;符号的左边d与e的乘积做模运算后的结果也必须等于1。
     这就需要计算出d的值,让这个同余等式能够成立。
(6)公钥KU=(e,n),私钥KR=(d,n)。
(7)加密时,先将明文变换成0至n-1的一个整数M。若明文较长,可先分割成适当的组,然后再进行交换。设密文为C,
     则加密过程为:C≡M^e(mod n)。
(8)解密过程为:M≡C^d(mod n)。
同余:数论中的重要概念。给定一个正整数m,如果两个整数a和b满足(a-b)能够被m整除,即(a-b)/m得到一个整数,那么就称整数a与b对模m同余。
记作a≡b(mod m)。对模m同余是整数的一个等价关系。
有了上面的RSA基础可以知道RSA中的。
p: 第一个大素数
q: 第二个大素数
模数n: n = p*q
f(n):  (p-1)*(q-1)
公钥指数e: 与 f(n)互质, 且 1
私钥指数d: 满足e * d ≡ 1 (mod f(n))
公钥 = {n, e},一般公开
私钥 = {d, e}
0×2
就拿实验吧上面的一个题做这个例子吧因为最近也一直在玩CTF。
http://ctf5.shiyanbar.com/crypto/RSAROLL.txt
第一行我们看到了这样一组数,直觉告诉我们这个很有可能是公钥(当然也不排除出题师傅直接把私钥给你,这样出题师傅是不是就太可爱了呀)。
{920139713,19}
根据我们上面补充的知识知道要按照步骤来获取私钥。
(1)   n = 920139713  e =19
(2)   这时候我们要将整数n分解为两个素数,我们可以使用在线网站直接来获取。
http://www.factordb.com/index.php
当然我们可以写代码来实现
如下:defdivde(n):
        start =2
        whilestart sqrt(n):
        if (n%start==0):
            record = start
            print(“大整数可以分解为:”,str(start),str(int(n/base)))
            break
         base+=1
         return (start,int(n/base))
(3)   经过上面的操作我们可以获得
p = 18443,q =49891,f(n) = (p-1)*(q-1)/p,q 是上n分解的两个质数,f(n)是欧拉函数
(4)   根据我们现在已经获得的条件以及前面补充的RSA知识我们知道只要找到一个满足e * d ≡ 1 (mod f(n)) 这个方程式的d,我们就成功获取的私钥(于是我就自己写了一个函数跑了一下,跑了好长时间仍然没有结果,在我快要放弃的时候我忽然想到了gmpy2,其中有一个神奇的函数)
(g,d,_) = gcdext(e,f(n)) //不知道为什么是这种格式但是它的效果是与e * d ≡ 1 (mod f(n)) 使用此函数只用了不到一秒的时间就获得了私钥d= 96849619
(5)   至此成功拿到了私钥,剩下的就剩解密密文
利用pow(i,d,n))解密密文//这里的i就是密文,d是我们刚才获取的私钥,n公钥如下图一

图一获取的是ASCII
(6)   最后将ASCII转化为相应的字符 (这里我用了自己写的一个小脚本工具)

图二将ASCII转化为字符
0×3代码部分
#-*- coding:utf-8 -*-
from gmpy2 import *
from Crypto.Util.number import *
利用gmpy2中的gcdext()函数实现的功能是 (d*e-1)% f(n)=0从而获取私钥d
 
def decrypt():
   flag = ''
    n= 920139713
    e=19
    p= 18443
    q= 49891
   phi_n = (p-1)*(q-1)
   (g,d,_) = gcdext(e,phi_n)  #利用此函数可以获取私钥d值
   print("Privcate key:",str(g),str(d))
   plaintext =""" 704796792
                    752211152
                    274704164

[1] [2]  下一页

【声明】:黑吧安全网(http://www.myhack58.com)登载此文出于传递更多信息之目的,并不代表本站赞同其观点和对其真实性负责,仅适于网络安全技术爱好者学习研究使用,学习中请遵循国家相关法律法规。如有问题请联系我们,联系邮箱admin@myhack58.com,我们会在最短的时间内进行处理。
  • 最新更新
    • 相关阅读
      • 本类热门
        • 最近下载