System32.kr [RSA102] 풀이

files → Crypto → RSA → RSA102

system32.kr의 rsa102 풀이입니다.

문제 내용입니다.

n : 17492679505633780091591558120277848189

e : 65537

c : 494188309631797349948909951854662875

rsa101에서 주어졌던 p와 q대신에 n이 있네요

n을 인수분해 해줍니다.

https://www.wolframalpha.com/input/?i=factorize+17492679505633780091591558120277848189

2071997351323275967 * 8442423680928995267 이렇게 인수분해가 된 것을 가져다가 rsatool.py을 이용해 d값을 구해줍니다.

mandu@mandu-VirtualBox:~/ex_code$ python rsatool.py -p 2071997351323275967 -q 8442423680928995267 -e 65537

Using (p, q) to initialise RSA instance

n = 17492679505633780091591558120277848189 (0xd28f7afd537f18bb9fd4b093834b07d)

e = 65537 (0x10001)

d = 7016876749372208745463430686590847805 (0x54766bbe8cacd20a60d747bcc474b3d)

p = 2071997351323275967 (0x1cc1369cf52c92bf)

q = 8442423680928995267 (0x7529839ba11e57c3)

d와 n을 이용해서 c를 복호화합니다. c^d mod N [modular Exponentiation]

def powermod3(a, b, n):
    r = 1
    while b > 0:
        if b & 1 == 1:
            r = r * a % n
        b /= 2
        a = a * a % n
    return r
 
#c^d mod N
#a^b mod c
a = 494188309631797349948909951854662875
b = 7016876749372208745463430686590847805
c = 17492679505633780091591558120277848189
 
print powermod3(a, b, c)

mandu@mandu-VirtualBox:~/ex_code$ python modular_Exponentiation.py 

21756137322202345153308749949

복호화된 21756137322202345153308749949을 hex값으로 바꿔주고

https://www.mobilefish.com/services/big_number/big_number.php

464C41477B325F737465707D

아스키로 바꿔주면

https://codebeautify.org/hex-string-converter

FLAG{2_step}

플래그가 나옵니다.

[N 인수분해 사이트를 몰랐다가 최근에 찾아내고, 이 문제가 지금 생각나서 풀이 작성해보았습니다.. 24/02/2019]