当前位置:首页 > 信息安全 > 正文内容

CTF中关于RSA算法的攻击方式

信息安全七星7个月前 (08-17)

RSA算法本身是安全的.

但是他的不正确用法使得RSA算法的攻击成功率提高了.

RSA算法在之前的文章中详细的介绍了.其攻击的核心就是获取两个大素数p和q.

RSA算法也是针对c, m, e, d, n, p, q这几个参数展开的.

但是题目不会直接给出, 而是以其他方式间接给出,或者要求我们获取.


一种最常见的就是给出pem文件, 我们可以通过openssl(kali自带)提取.

openssl的用法:

    密钥生成参数:

            rsa指定密钥生成(对密钥的操作)

            -inkey   指定私钥文件

            -out      指定解密后的文件

            -pubin        表示输入文件为公钥.

            -pubout     输出公钥

            -text           以明文形式输出各种参数

            -modulus   输出模数值

    从私钥中提取公钥:

        openssl rsa -pubout -in <pr.pem> -out <pu.pem>

    

    密钥加解密参数:

            rsautl  对明文和密文的操作.

            -in              输入文件
            -inkey        输入的密钥
            -encrypt    使用公钥加密
            -decrypt    使用私钥解密

    使用密钥解密文件.

            openssl rsautl -decrypt -in <input.file> -inkey <pr.pem> -out <output.file>

    使用密钥文件加密文件.

            openssl   rsautl -encrypt -in <input.file> -inkey <pr.pem> -out <output.file>



另一种则是有交互的,给一个IP,一个端口号,然后nc连接, 多轮交互,在交互中给出参数.


然后参数有了, 就开始各种各样的攻击.


一.模数分解

RSA算法题目中, 最简单的就是分解模n.

分解之后获得大素数p和q, 进而求得d.

在之前的文章中只写了RSA的理论部分,现在把代码补上.

以下写几个python脚本:


1. 已知e,p,q,求d:

def egcd(a, b):
    if a == 0:
        return (b, 0, 1)
    else:
        g, y, x = egcd(b % a, a)
        return (g, x - (b // a) * y, y)
                
def modinv(a, m):
    g, x, y = egcd(a, m)
    if g != 1:
          raise Exception('逆元不存在')
    else:
          return x % m
e = 
p =
q =
d = modinv(e, (p-1)*(q-1))


2. 已知大数n, 求p,q.

给出一个大数n, 直接分解.

利用工具:

RSATool

利用在线网站:

http://factordb.com/

分解完成之后, 就回到了上面1中的问题.


3.利用公约数

在一次加密中, 使用了两个大数n, 

并且两个n都拥有相同的素因子,那么就可以直接通过欧几里得算法直接分解.

原理:

        n1 = p * p1

        n2 = p * p2

这种题目,一般会给出很多n, 而e可能是全部相同的.

直接上代码:

def gcd(a, b):
    if a < b:
        a, b = b, a
    while b != 0:
        temp = a % b
        a = b
        b = temp
    return a

通过脚本可以得到相同的素因子, 从而得到另一个素因子.


4.yafu

针对大整数的分解有很多种算法,性能上各有优异

有Fermat方法,Pollard rho方法,试除法,以及椭圆曲线法,连分数法,二次筛选法,数域分析法等等。

其中一些方法应用在RSA的攻击上也有奇效。

在p,q的取值差异过大,或者p,q的取值过于相近的时候,

Format方法与Pollard rho方法都可以很快将n分解成功


有个工具, 叫yafu, 下面的下载地址是基于window的. 

当p和q的值相差较大或相差较小时, 可以使用这个工具.

下载地址:

yafu.zip

用法:

解压到一个目录.为了方便使用, 将yafu-x64.exe改名成yafu.exe,

然后给这个目录添加path环境.


当有一个大数:

image.png

够大吧.

新建一个记事本, 把大数放里面, 在末位记得加一个换行.

然后执行:

yafu "factor(@)"  -batchfile 1.txt

得到:

image.png

但是,原先的1.txt就没了.


二.第加密指数攻击

参数e, 也叫做加密指数. 在之前的文章中说到过, e是可以随意选取的







等待更新...


七星比特|qixingbit.com|QQ:320406741

相关文章

CVE-2019-0708_RDP漏洞利用

CVE-2019-0708_RDP漏洞利用

漏洞简介: 基于Windows系列服务器系列漏洞,在2019年5月15日被公开,级别属于高危漏洞,利用方式简单,通过3389端口,RDP协议进行攻击。这个漏洞是今年危害严重性最大的漏洞受影响...

渗透测试_权限维持

渗透测试_权限维持

前言渗透测试权限维持比较重要,所以要掌握一些重要的权限维持手段.本文讲述Windows和Linux的权限维持, 以及被攻击后的防御手段.Windows篇较为常见的提权手段ms17_058ms16_01...

XCTF_pwn新手区_level0

XCTF_pwn新手区_level0

拿到题,执行一下,然后看一下保护:程序只开了NX.这里记录一下NX:NX:NX是数据与程序的分水岭,栈溢出核心思想是通过局部变量覆盖函数返回地址来修改EIP注释1和注入 Shellcode注释2,在函...

发表评论

访客

看不清,换一张

◎欢迎参与讨论,请在这里发表您的看法和观点。