date : `17.02
Fady assumed this time that you will be so n00b to tell what encryption he is using
he send the following note to his friend in plain sight :
rsa 알고리즘을 통해 암호화 된 데이터를 복호화 해야 하는 문제이다. 제공되는 파일의 내용은 다음과 같이 구성되어 있다.
p=0xa6055ec186de51800ddd6fcbf0192384ff42d707a55f57af4fcfb0d1dc7bd97055e8275cd4b78ec63c5d592f567c66393a061324aa2e6a8d8fc2a910cbee1ed9
q=0xfa0f9463ea0a93b929c099320d31c277e0b0dbc65b189ed76124f5a1218f5d91fd0102a4c8de11f28be5e4d0ae91ab319f4537e97ed74bc663e972a4a9119307
e=0x6d1fdab4ce3217b3fc32c9ed480a31d067fd57d93a9ab52b472dc393ab7852fbcb11abbebfd6aaae8032db1316dc22d3f7c3d631e24df13ef23d3b381a1c3e04abcc745d402ee3a031ac2718fae63b240837b4f657f29ca4702da9af22a3a019d68904a969ddb01bcf941df70af042f4fae5cbeb9c2151b324f387e525094c41
c=0x7fe1a4f743675d1987d25d38111fae0f78bbea6852cba5beda47db76d119a3efe24cb04b9449f53becd43b0b46e269826a983f832abb53b7a7e24a43ad15378344ed5c20f51e268186d24c76050c1e73647523bd5f91d9b6ad3e86bbf9126588b1dee21e6997372e36c3e74284734748891829665086e0dc523ed23c386bb520
이전에 공부를 했지만 매번 까먹는 rsa. 정리가 필요한듯 하다.
서로소인 p,q를 가지고 공개키 e, 개인키 d를 만들어 내고 이를 이용하여 데이터를 암호화 한다.
rsa의 원리는 다음과 같다.
- 서로소인 임의의 p, q를 정한다. 큰 수를 사용한다.
- n = p * q
- phi = (p-1) * (q-1)
- phi보다 작고 phi와 서로소인 수 e를 찾는다.
- d*e (mod n) = 1 인 정수 d를 구한다.
d를 구할때 유클리드 호제법을 사용하며, c = msg ^ e (mod n) == msg ^ d (mod n)이 성립됨을 알아야 한다.
사용한 소스코드는 다음과 같다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
|
def rsa(c, e, p, q):
from Crypto.PublicKey import RSA
import gmpy2
c = long(c, 16)
e = long(e, 16)
p = long(p, 16)
q = long(q, 16)
phi = (p-1)*(q-1)
n = p*q
d = long(gmpy2.invert(e,phi))
key = RSA.construct((n, e, d))
m = key.decrypt(c)
return hex(d), hex(n), hex(m)
rsa.__doc__ = "return d, n, m\nd : Exponente\nn : Modulo\nm : msg\nc = msg ^ e (mod n) | msg = c ^ d (mod n)\nrefer : http://ronins.team/alexctf_cr3_what_is_this_encryption/"
|
gmpy2.invert함수는 d*e == 1 (mod n)을 구해 주는 함수이다.
1
2
3
4
5
6
7
8
9
10
|
from my imoprt rsa
p="0xa6055ec186de51800ddd6fcbf0192384ff42d707a55f57af4fcfb0d1dc7bd97055e8275cd4b78ec63c5d592f567c66393a061324aa2e6a8d8fc2a910cbee1ed9"
q="0xfa0f9463ea0a93b929c099320d31c277e0b0dbc65b189ed76124f5a1218f5d91fd0102a4c8de11f28be5e4d0ae91ab319f4537e97ed74bc663e972a4a9119307"
e="0x6d1fdab4ce3217b3fc32c9ed480a31d067fd57d93a9ab52b472dc393ab7852fbcb11abbebfd6aaae8032db1316dc22d3f7c3d631e24df13ef23d3b381a1c3e04abcc745d402ee3a031ac2718fae63b240837b4f657f29ca4702da9af22a3a019d68904a969ddb01bcf941df70af042f4fae5cbeb9c2151b324f387e525094c41"
c="0x7fe1a4f743675d1987d25d38111fae0f78bbea6852cba5beda47db76d119a3efe24cb04b9449f53becd43b0b46e269826a983f832abb53b7a7e24a43ad15378344ed5c20f51e268186d24c76050c1e73647523bd5f91d9b6ad3e86bbf9126588b1dee21e6997372e36c3e74284734748891829665086e0dc523ed23c386bb520"
res = rsa(c,e,p,q)
print res[2][2:-1].decode('hex')
## ALEXCTF{RS4_I5_E55ENT1AL_T0_D0_BY_H4ND}
|
cs |
Flag : ALEXCTF{RS4_I5_E55ENT1AL_T0_D0_BY_H4ND}
'CTF | wargame' 카테고리의 다른 글
| Alexctf / unVM me (파이썬 디컴파일 uncompyle, md5 해쉬데이터 조회) (0) | 2017.03.11 |
|---|---|
| Alexctf / math bot (반복 소켓 연산) (0) | 2017.03.11 |
| Alexctf / poor rsa (공개키를 이용한 rsa 개인키 복호화) (0) | 2017.03.11 |
| codegate 2017 / RamG-thunder (우회 리버싱) (0) | 2017.03.10 |
| nullcon17 / Programming Question 1 (픽셀 데이터 -> png 변환) (0) | 2017.03.10 |