본문 바로가기

CTFs/MMA 2016

[MMA 2016] crypto : Twin Primes

Twin Primes

주어진 파일은 암호화 하는 파이썬 스크립트 하나와 각각 n 과 e 값이 적혀있는 2개의 파일과 암호화 된 파일이 주어졌다.


주어진 암호화 스크립트를 보니 일단 Twin Primes(일명 쌍둥이소수) 를 생성하고 이 값들을 이용해서 2개의 키들을 만든다.

첫번 째 키에서는 각각 다른 쌍둥이 소수 p, q 가 사용되었고

두번 째 키에서는 사전에 구해놓은 쌍둥이 소수인 (p+2), (q+2) 가 사용되었다.

E 값은 0x10001(65537) 로 주워 졌으니 각 키에 대한 정보를 써 보면

1
2
3
4
5
6
7
8
9
10
11
12
13
- Key 1
p1 = p
q1 = q
n1 = p*q
d1 = inverse(e, (p - 1)(q - 1))
= 0x10001
 
- Key 2
p2 = p + 2
q2 = q + 2
n2 = (p + 2)(q + 2)
d2 = inverse(e, (p + 1)(q + 1))
= 0x10001
cs


하지만 여기서 주어진 값들은 n1, n2 이다. 하지만 Key1, 2 에서 p, q 값들은 서로 쌍둥이 소수기 때문에 손쉽게 d을 구할 수 있다.

나머지 자세한 설명은 코드로 대체

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
from Crypto.Util.number import *
import Crypto.PublicKey.RSA as RSA
 
= 65537
n1 = 19402643768027967294480695361037227649637514561280461352708420192197328993512710852087871986349184383442031544945263966477446685587168025154775060178782897097993949800845903218890975275725416699258462920097986424936088541112790958875211336188249107280753661467619511079649070248659536282267267928669265252935184448638997877593781930103866416949585686541509642494048554242004100863315220430074997145531929128200885758274037875349539018669336263469803277281048657198114844413236754680549874472753528866434686048799833381542018876362229842605213500869709361657000044182573308825550237999139442040422107931857506897810951
n2 = 19402643768027967294480695361037227649637514561280461352708420192197328993512710852087871986349184383442031544945263966477446685587168025154775060178782897097993949800845903218890975275725416699258462920097986424936088541112790958875211336188249107280753661467619511079649070248659536282267267928669265252935757418867172314593546678104100129027339256068940987412816779744339994971665109555680401467324487397541852486805770300895063315083965445098467966738905392320963293379345531703349669197397492241574949069875012089172754014231783160960425531160246267389657034543342990940680603153790486530477470655757947009682859
cipher = 7991219189591014572196623817385737879027208108469800802629706564258508626010674513875496029177290575819650366802730803283761137036255380767766538866086463895539973594615882321974738140931689333873106124459849322556754579010062541988138211176574621668101228531769828358289973150393343109948611583609219420213530834364837438730411379305046156670015024547263019932288989808228091601206948741304222197779808592738075111024678982273856922586615415238555211148847427589678238745186253649783665607928382002868111278077054871294837923189536714235044041993541158402943372188779797996711792610439969105993917373651847337638929
 
p_q = ((n2 - n1) / 2- 2
d1 = inverse(e, n1 - p_q + 1)
d2 = inverse(e, n1 + p_q + 1)
 
print "e) : " + hex(e)
print "p+q : " + hex(p_q)
print "n1) pq : " + hex(n1)
print "d1) (p-1)(q-1) : " + hex(d1)
print "n2) pq : " + hex(n2)
print "d2) (p+1)(q+1) : " + hex(d2)
print "Cipher : " + hex(cipher)
 
# http://nmichaels.org/rsa.py
# TWCTF{3102628d7059fa267365f8c37a0e56cf7e0797ef}
'''
0x54 0x57 0x43 0x54 0x46 0x7b 0x33 0x31 0x30 0x32 0x36
0x32 0x38 0x64 0x37 0x30 0x35 0x39 0x66 0x61 0x32 0x36 
0x37 0x33 0x36 0x35 0x66 0x38 0x63 0x33 0x37 0x61 0x30 
0x65 0x35 0x36 0x63 0x66 0x37 0x65 0x30 0x37 0x39 0x37 
0x65 0x66 0x7d 0x0a 0x00 0xa0 0xdf 0xdd 0xeb 0x2a 0xc0 
0xfd 0x93 0x09 0x4c 0xe4 0x08 0x30 0xdc 0xd4 0xaa 0xe2 
0x7f 0xd2 0x3c 0x80 0x35 0xec 0x53 0xb2 0x17 0x45 0x24 
0x4b 0x0a 0x9e 0xe8 0xfc 0x17 0x34 0x9e 0x08 0x68 0x6a 
0x40 0xe8 0x2d 0xc1 0xbe 0xd9 0x48 0x27 0x28 0x19 0x13 
0x1b 0x62 0xe7 0x15 0xe0 0xfc 0xe9 0x90 0x8e 0xfa 0xeb 
0xac 0xc2 0x61 0xea 0xb0 0xc5 0xc7 0x44 0x6d 0xb6 0x5a 
0x0e 0x87 0x4c 0xca 0x94 0x16 0x61
'''
cs


Flag : TWCTF{3102628d7059fa267365f8c37a0e56cf7e0797ef}

'CTFs > MMA 2016' 카테고리의 다른 글

[MMA 2016] pwnable : judgement  (0) 2016.09.06
[MMA 2016] crypto : Super Express  (0) 2016.09.05
[MMA 2016] forensic : Rescue Data 1 : deadnas  (2) 2016.09.05
[MMA 2016] misc : ninth  (0) 2016.09.05
[MMA 2016] misc : glance  (0) 2016.09.05