CTF_RSA1

Author: 张浩森 Date: Jul 7, 2018 Updated On: Jul 7, 2018
Categories:
Tags:

一个自己没有做出来的CTF CryptoRSA题

这个题其实很简单,水题,太基础了。不过自己编程能力也是差,写不出脚本,找网上能跑的脚本也找不到。

记录下来思路,以后肯定能碰到类似的题目。

题目:

1
2
3
4
n=0x1fb18fb44f4449f45ea938306c47b91f64b6c176bd24dbb35aa876f73859c90f0e1677d07430a1188176bc0b901ca7b01f6a99a7df3aec3dd41c3d80f0d17292e43940295b2aa0e8e5823ffcf9f5f448a289f2d3cb27366f907ee62d1aaeba490e892dc69dacbafa941ab7be809e1f882054e26add5892b1fcf4e9f1c443d93bf
e=0xe42a12145eaa816e2846200608080305c99468042450925789504307cbc54a20ed7071b68b067b703a1679d861795542f8cbd2d1cb4d3847d0940cac018cdb0fa729571afbe10c1b8be2dd8acd99ee48b77d53c435b9c2fed59e12e02ad8cfc2bcc46ad85534c266dcc1f3a1a03d87118eaf3f5b3eeeb3be84ad023a4bf34939
c=0xd19d63015bdcb0b61824237b5c67cb2ef09af0c6cd30e193ff9683357b1e45ab4df607b8c1e0b96cafc49a84d7e655c3ce0f71b1d217eec9ca6cdfa57dd3dc92533b79431aa8a7d6ca67ac9cdd65b178a5a96ab7ce7bf88440f4a9b9d10151b0c942a42fdab9ea2c2f0c3706e9777c91dcc9bbdee4b0fb7f5d3001719c1dd3d3
Tell me the msg.

一、RSA原理

RSA是一种非对称加密方式,一般用来做身份认证。

原理如下:

首先选择两个大素数:pq,计算出模数N = p * q

计算φ = (p - 1)*(q - 1)φ称为N的欧拉函数,信息安全数学基础有学到。欧拉函数,即小于N的正整数中与N互质的整数个数。两个数互质就是这两个数的公因数只有1。

这里有一个定理:若一个正整数能够分解出两个素数的乘积,那么这个数的欧拉函数值为这两个素数减一相乘。

然后选择一个e,这个e必须与φ互质,且1<e<φ

然后取eφ下的逆元dd满足e * d ≡ 1 mod φ

公钥和私钥的定义如下:

1
2
3
(N,e):公钥

(N,d):私钥

加解密过程如下:

对明文A进行加密:B ≡ A ^ e (mod N) 或 B = pow(A,e,N),得到的B即为密文

对密文B进行解密,A ≡ B ^ d (mod N) 或 A = pow(B,d,N),得到的A即为明文

1
2
3
4
5
6
7
p 和 q :大整数N的两个因子(factor)

N:大整数N,我们称之为模数(modulus)

e 和 d:互为逆元的两个指数(exponent)

A(一般是c) 和 B(一般是m):分别是密文和明文,这里一般指的是一个十进制的数

公钥是可以公开,私钥是绝对不能公开的。RSA的安全性在于此数学难题:想要分解N成两个素数是及其困难的,在量子计算机还没有成熟的今天,这个是及其困难的。

如果想要由公钥计算出私钥,必须知道pq计算N的欧拉函数φ,一般在利用pq生成秘钥对之后,必须销毁。所以RSA基于大素数分解的数学难题,安全性目前得到保证,广泛应用。

然而即便RSA算法目前来说是安全可靠的,但是错误的应用场景,错误的环境配置,以及错误的使用方法,都会导致RSA的算法体系出现问题,从而也派生出针对各种特定场景下的RSA攻击方法。

N必须要足够的长,目前计算机的计算能力越来越高,目前长度4096bit以上的N才被认为是安全的。

二、本题做法

在CTF中有关RSA的题,首先应该看有没有办法或者可能性分解N,比如跑脚本、利用miseve、yafu等等工具。

pq相差过大或者过于接近时,yafu这个工具都可以很快的将N分解,其原理是Format方法与Pollard rho方法。

本题中N的长度很大,所以放弃直接分解Npq的思路,利用避开分解因子攻击RSA的方法。

因为这里的e也很大,经过了解可以利用低解密指数攻击:

识别可以利用低解密指数攻击的方式就看给的e是否很大就可以了。如果看起来很大,那么利用低解密指数攻击方法有很大成功的可能性。

工具:https://github.com/pablocelayes/rsa-wiener-attack

原理在这个github仓库里有。我看不懂。

这里直接用RSAwienerHacker.py就可以,改一下我们要传入的参数为题目中给的参数,即Ned初始化为0 就可以。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
'''
Created on Dec 14, 2011

@author: pablocelayes
'''

import ContinuedFractions, Arithmetic, RSAvulnerableKeyGenerator

def hack_RSA(e,n):
'''
Finds d knowing (e,n)
applying the Wiener continued fraction attack
'''
frac = ContinuedFractions.rational_to_contfrac(e, n)
convergents = ContinuedFractions.convergents_from_contfrac(frac)

for (k,d) in convergents:

#check if d is actually the key
if k!=0 and (e*d-1)%k == 0:
phi = (e*d-1)//k
s = n - phi + 1
# check if the equation x^2 - s*x + n = 0
# has integer roots
discr = s*s - 4*n
if(discr>=0):
t = Arithmetic.is_perfect_square(discr)
if t!=-1 and (s+t)%2==0:
print("Hacked!")
return d

# TEST functions

def test_hack_RSA():
print("Testing Wiener Attack")
times = 1

while(times>0):
#e,n,d = RSAvulnerableKeyGenerator.generateKeys(1024)
n=0x1fb18fb44f4449f45ea938306c47b91f64b6c176bd24dbb35aa876f73859c90f0e1677d07430a1188176bc0b901ca7b01f6a99a7df3aec3dd41c3d80f0d17292e43940295b2aa0e8e5823ffcf9f5f448a289f2d3cb27366f907ee62d1aaeba490e892dc69dacbafa941ab7be809e1f882054e26add5892b1fcf4e9f1c443d93bf
e=0xe42a12145eaa816e2846200608080305c99468042450925789504307cbc54a20ed7071b68b067b703a1679d861795542f8cbd2d1cb4d3847d0940cac018cdb0fa729571afbe10c1b8be2dd8acd99ee48b77d53c435b9c2fed59e12e02ad8cfc2bcc46ad85534c266dcc1f3a1a03d87118eaf3f5b3eeeb3be84ad023a4bf34939
d=0
print("(e,n) is (", e, ", ", n, ")")
print("d = ", d)

hacked_d = hack_RSA(e, n)

if d == hacked_d:
print("Hack WORKED!")
else:
print("Hack FAILED")

print("d = ", d, ", hacked_d = ", hacked_d)
print("-------------------------")
times -= 1

if __name__ == "__main__":
#test_is_perfect_square()
#print("-------------------------")
test_hack_RSA()

跑出来之后的结果:

1
2
3
4
5
6
7
8
~/Desktop/rsa-wiener-attack-master ⌚ 22:02:30
$ python RSAwienerHacker.py
Testing Wiener Attack
('(e,n) is (', 160222447153262895889250928158012827757109871196102040037421857250766491575699886894325697077956068896677359953037375582060511979328323570880578946073240834317364119936983046746942944368567355131867682895196198904859001202051459879133425754080440276218324680838480108302184726980362910704693149535052743526713L, ', ', 356096033429997161372356441930246707554046995590506452306084931488519008238592151695866774341246347160182054216879883209187019942641996111166252052256475412435016177136773967956292472785118669272929844214105480922945372638910276569650465033695573697459823872295312452877368652943145314840314022954151337366463L, ')')
('d = ', 0)
Hacked!
Hack FAILED
('d = ', 0, ', hacked_d = ', 731297L)

可以看到d被解出来为731297。

然后就知道了N,d,也就相当于知道的私钥。

解密就可以了:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
~/Desktop/rsa-wiener-attack-master ⌚ 22:12:00
$ python
Python 2.7.15 (default, May 1 2018, 16:44:08)
[GCC 4.2.1 Compatible Apple LLVM 9.1.0 (clang-902.0.39.1)] on darwin
Type "help", "copyright", "credits" or "license" for more information.
>>> c=0xd19d63015bdcb0b61824237b5c67cb2ef09af0c6cd30e193ff9683357b1e45ab4df607b8c1e0b96cafc49a84d7e655c3ce0f71b1d217eec9ca6cdfa57dd3dc92533b79431aa8a7d6ca67ac9cdd65b178a5a96ab7ce7bf88440f4a9b9d10151b0c942a42fdab9ea2c2f0c3706e9777c91dcc9bbdee4b0fb7f5d3001719c1dd3d3
>>>
>>> n=0x1fb18fb44f4449f45ea938306c47b91f64b6c176bd24dbb35aa876f73859c90f0e1677d07430a1188176bc0b901ca7b01f6a99a7df3aec3dd41c3d80f0d17292e43940295b2aa0e8e5823ffcf9f5f448a289f2d3cb27366f907ee62d1aaeba490e892dc69dacbafa941ab7be809e1f882054e26add5892b1fcf4e9f1c443d93bf
>>> d=731297
>>> m=pow(c,d,n)
>>> m
38321129004205530330779911668681589489034853148078444L
>>> hex(m)[2:len(hex(m))-1]
'666c61673173483372335f645f69737430736d61316c'
>>> print 'sctf{'+hex(m)[2:len(hex(m))-1].decode('hex')+'}'
sctf{flag1sH3r3_d_ist0sma1l}
>>>

解出来的十进制明文那里不太明白问什么会有个L,没想明白为啥要转成hex编码,解码的时候还要把0x和L去掉,可能是因为hex(m)的类型是个str。

Flag:sctf{flag1sH3r3_d_ist0sma1l}