首页
论坛
课程
招聘
[原创]CTF中RSA的一些攻击思路
2019-9-2 22:58 18079

[原创]CTF中RSA的一些攻击思路

2019-9-2 22:58
18079

本文简略总结了前人的一些RSA攻击思路,代码或来源于网上或本人原创
并已在GitHub上开源,github地址
https://github.com/yifeng-lee/RSA-In-CTF
同时exp也附于附件上

关于RSA算法

RSA加密算法是一种非对称加密算法,1977年由Ron Rivest、Adi Shamir和Leonard Adleman一起提出的,算法安全性依赖于极大整数做因数分解的难度

RSA算法加解密实现

1.随意选择两个大素数pq,且p不等于q,计算N=p*q

 

2.计算n的欧拉函数φ(n) = (p-1)(q-1)(常用phi(n)表示φ(n)

 

3.选择一个整数e,满足1< e < φ(n),且e与φ(n) 互质(e通常取65537)

 

4.计算模反元素ded ≡ 1 (mod φ(n)) 即求解ex + φ(n)y = 1方程组(利用扩展欧几里得算法可以求出d

 

d = gmpy2.invert(e, (p-1)*(q-1))

 

5.得到公钥(N,e)私钥(N,d)

 

6.加密 c = pow(m,e,N)

 

7.解密 m = pow(c,d,N)

RSA在CTF中的攻击方法

gmpy2 安装

sudo apt install libmpc-dev

pip/pip3 install gmpy2

sage安装

https://mirrors.tuna.tsinghua.edu.cn/sagemath/linux/64bit/index.html

明文解密

模互素

d = gmpy2.invert(e,(p-1) * (q-1))

 

m = gmpy2.powmod(c,d,n)

模不互素

第一种情况

 

给出 p,q,c,e且gcd(e, (p-1)*(q-1))非常小(可能为3)

 

example:

 

p,q = 3881, 885445853681787330351086884500131209939

 

c = 1926041757553905692219721422025224638913707

 

e = 33

 

第二种情况

 

给出n1,n2,e1,e2,c1,c2求满足以下式子

 

assert p = gcd(n1,n2)

 

assert pow(flag,e1,n1)==c1

 

assert pow(flag,e2,n2)==c2

 

assert gcd(e1,(p1-1) (q1-1))==gcd(e2,(p2-1) (q2-1))

0x01、低加密指数攻击

m ^ e = kn + c 其中一般 e = 3,k比较小(k小于10亿爆破时间一般小于半小时)

0x02、低加密指数广播攻击

c1 ≡ m^e mod n1

 

c2 ≡ m^e mod n2

 

……

 

ce ≡ m^e mod ne

 

如以上所示,e比较小,题目给出n[e]和c[e],且m相同,利用中国剩余定理可以求m

0x03、低解密指数攻击

与低加密指数攻击相反,需要满足e非常大,接近于N

0x04、共模攻击

c1 ≡ m^e1 mod n

 

c2 ≡ m^e2 mod n

 

如以上使用了相同的模数N对相同的明文进行加密

0x05、Boneh and Durfee attack

e 非常大接近于N,跟低解密指数攻击类似,比低解密指数攻击更强,可以解决d<N的0.292次方的问题

0x06、Coppersmith攻击:已知p的高位攻击

知道p的高位为p的位数的约1/2时即可

0x07、Coppersmith攻击:已知明文高位攻击

0x08、Coppersmith攻击:已知d的低位攻击

如果知道d的低位,低位约为n的位数的1/4就可以恢复d

0x09、Coppersmith攻击:明文高位相同

0x0A、已知dp或dq(dp = d mod p-1,dq = d mod q-1)

0x0B、Least Significant Bit Oracle Attack

0x0C、其他思路

给出两组数据

 

n1,c1,e1,n2,c2,e2且无以上特征可尝试gcd(n1,n2)得到公因子(存在的话)

 

给出一组数据

 

n1,c1,e1

 

尝试yafu或http://www.factordb.com分解n(p,q相差过大或过小yafu可分解成功)

 

给出如下数据

 

p,q,nextprime(p),nextprime(q)

 

n1 = p * q

 

n2 = nextprime(p) * nextprime(q)

 

n = n1 * n2

 

用yafu分解n可得到

 

n3 = p * nextprime(q)

 

n4 = q * nextprime(p)

参考文献

https://www.tr0y.wang/2017/11/06/CTFRSA/index.html
http://inaz2.hatenablog.com/entry/2016/01/20/022936


2021 KCTF 秋季赛 防守篇-征题倒计时(11月14日截止)!

上传的附件:
收藏
点赞4
打赏
分享
最新回复 (5)
雪    币: 7109
活跃值: 活跃值 (196)
能力值: ( LV12,RANK:256 )
在线值:
发帖
回帖
粉丝
丿feng 活跃值 3 2019-9-3 00:49
2
0
每一种攻击方法都附有对应exp,因篇幅问题以附件形式上传
雪    币: 5205
活跃值: 活跃值 (961)
能力值: ( LV12,RANK:204 )
在线值:
发帖
回帖
粉丝
堂前燕 活跃值 1 2019-9-3 08:22
3
0
mark
雪    币: 15496
活跃值: 活跃值 (20951)
能力值: (RANK:75 )
在线值:
发帖
回帖
粉丝
Editor 活跃值 2019-9-6 14:43
4
0
mark,感谢分享!
雪    币: 218
能力值: ( LV1,RANK:0 )
在线值:
发帖
回帖
粉丝
Cheney辰星 活跃值 2020-10-22 11:18
5
0
观摩大佬。
雪    币: 174
活跃值: 活跃值 (34)
能力值: ( LV2,RANK:10 )
在线值:
发帖
回帖
粉丝
zer0_1s 活跃值 2020-11-12 14:48
6
0
rsa自学++
游客
登录 | 注册 方可回帖
返回