Break In CTF 2018 Writeup

この大会は2018/1/22 0:30(JST)～2018/1/23 0:30(JST)に開催されました。
今回もチームで参戦。結果は1300点で97チーム中9位でした。
自分で解けた問題をWriteupとして書いておきます。

Tayank and RSA (200)

公開鍵と暗号ファイルが与えられている。Fermat法でnを素因数分解し、復号する。

71877470807883123484848484849751061131101041101211007812075122115125

復号した数字は直接文字にならない。10進数で文字になるよう前から順にASCII文字に置き換えてみる。

GWJFPNS{000001KjqnhnydNxKzs}

5シフトさせると、フラグになりそう。最終的なコードは以下の通り。

from Crypto.PublicKey import RSA
import string

def isqrt(n):
    x = n
    y = (x + n // x) // 2
    while y < x:
        x = y
        y = (x + n // x) // 2
    return x

def fermat(n):
    x = isqrt(n) + 1
    y = isqrt(x * x - n)
    while True:
        w = x * x - n - y * y
        if w == 0:
            break
        elif w > 0:
            y += 1
        else:
            x += 1
    return x - y, x + y

with open('Xa5kNbw_Twins.pub', 'r') as f:
    pub_data = f.read()

with open('4vfouvg_message.txt', 'r') as f:
    c = int(f.read().strip(), 10)

pubkey = RSA.importKey(pub_data)
n = pubkey.n
e = pubkey.e
p, q = fermat(n)

a = (p - 1) * (q - 1)

x = 0
while True:
    if (a * x + 1) % e == 0:
        d = (a * x + 1) / e
        break
    x = x + 1

m = pow(c, d, n)
m = str(m)
#print m

dec = ''
code = ''
for i in range(len(m)):
    code += m[i]
    if int(code) > 31 and int(code) < 127:
        dec += chr(int(code))
        code = ''
#print dec

flag = ''
for i in range(len(dec)):
    if dec[i] in string.uppercase:
        code = ord(dec[i]) - 5
        if code < ord('A'):
            code += 26
    elif dec[i] in string.lowercase:
        code = ord(dec[i]) - 5
        if code < ord('a'):
            code += 26
    else:
        code = ord(dec[i])
    flag += chr(code)

print flag

BREAKIN{000001FelicityIsFun}