InCTF Writeup - よっちんのブログ

この大会は2017/12/16 21:00(JST)～2017/12/17 21:00(JST)に開催されました。
今回もチームで参戦。結果は1301点で156チーム中11位でした。
自分で解けた問題をWriteupとして書いておきます。

Sanity Check (Misc 1)

freenodeで#bi0s-ctfに入る。

　　　　：
21:12 *topic : Welcome to InCTF, https://ctf.inctf.in/ | Flag for Sanity check inctf{w3lc0me_t0_inctf}

inctf{w3lc0me_t0_inctf}

Multi Layer RSA (Crypto 100)

encryption_keyの各要素の乗算結果をeと考えれば、RSA暗号になる。eが非常に大きい値になるので、Wiener Attackで復号する。

from fractions import Fraction

def egcd(a, b):
    x,y, u,v = 0,1, 1,0
    while a != 0:
        q, r = b//a, b%a
        m, n = x-u*q, y-v*q
        b,a, x,y, u,v = a,r, u,v, m,n
        gcd = b
    return gcd, x, y

def decrypt(p, q, e, c):
    n = p * q
    phi = (p - 1) * (q - 1)
    gcd, a, b = egcd(e, phi)
    d = a
    pt = pow(c, d, n)
    return hex(pt)[2:-1].decode('hex')

def continued_fractions(n,e):
    cf = [0]
    while e != 0:
        cf.append(int(n/e))
        N = n
        n = e
        e = N%e
    return cf

def calcKD(cf):
    kd = list()
    for i in range(1,len(cf)+1):
        tmp = Fraction(0)
        for j in cf[1:i][::-1]:
            tmp = 1/(tmp+j)
        kd.append((tmp.numerator,tmp.denominator))
    return kd

def int_sqrt(n):
    def f(prev):
        while True:
            m = (prev + n/prev)/2
            if m >= prev:
                return prev
            prev = m
    return f(n)

def calcPQ(a,b):
    if a*a < 4*b or a < 0:
        return None
    c = int_sqrt(a*a-4*b)
    p = (a + c) /2
    q = (a - c) /2
    if p + q == a and p * q == b:
        return (p,q)
    else:
        return None

def wiener(n,e):
    kd = calcKD(continued_fractions(n,e))
    for (k,d) in kd:
        if k == 0:
            continue
        if (e*d-1) % k != 0:
            continue
        phin = (e*d-1) / k
        if phin >= n:
            continue
        ans = calcPQ(n-phin+1,n)
        if ans is None:
            continue
        return (ans[0],ans[1])

with open('ciphertext.txt', 'r') as f:
    c = int(f.read(), 16)

with open('modulus.txt', 'r') as f:
    n = int(f.read().split(' = ')[1])

encryption_keys = [34961, 3617491, 68962801, 293200159531, 1191694878666066510321450623792489136756229172407332230462797663298426983932272792657383336660801913848162204216417540955677965706955404313949733712340714861638106185597684745174398501025724130404133569866642454996521744281284226124355987843894614599718553178595963014434904833]

e = 1
for i in encryption_keys:
    e *= i

p, q = wiener(n, e)

flag = decrypt(p, q, e, c)
print flag

inctf{w13n3r's_4774ck_s0lv3d_17_4ll_r1gh7?}

RSA 1s fun (Crypto 150)

eの値が互いに素になっていなく、最大公約数が3になっていることから、以下のように考える。

c1 = pow(flag, 3*3, n)
c2 = pow(flag, 3*41, n)

ここで平文をflag**3と考え、Common Modulus Attackを行う。復号した値の3乗根を取れば、最終的には復号できる。

import gmpy

def commom_modules_attack(c1, c2, e1, e2, n):
    gcd, s1, s2 = gmpy.gcdext(e1, e2)
    if s1 < 0:
        s1 = -s1
        c1 = gmpy.invert(c1, n)
    elif s2 < 0:
        s2 = -s2
        c2 = gmpy.invert(c2, n)
 
    v = pow(c1, s1, n)
    w = pow(c2, s2, n)
    x = (v * w) % n
    return x

with open('ciphertext.txt', 'r') as f:
    lines = f.readlines()

with open('modulus.txt', 'r') as f:
    n = int(f.read().split(' = ')[1])

c1 = int(lines[0].strip().split(':  ')[1])
c2 = int(lines[1].strip().split(':  ')[1])
e1 = 9 / 3
e2 = 123 / 3

m = commom_modules_attack(c1, c2, e1, e2, n)
m = gmpy.root(m, 3)[0]
flag = ('%x' % m).decode('hex')
print flag

inctf{n07_s0_e4sy_70_expl01t_7h1s_RSA_orIsIt?}

Crafted RSA (Crypto 200)

p, qそれぞれの素数の生成の範囲が決まっていることから、近い数値であると推測し、Fermat法で素因数分解し、復号する。

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('ciphertext.txt', 'r') as f:
    c = int(f.read(), 16)

with open('modulus.txt', 'r') as f:
    n = int(f.read().split(':  ')[1])

e = 2**16 + 1

p, q = fermat(n)

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

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

m = pow(c, d, n)

flag = ('%x' % m).decode('hex')
print flag

inctf{1_7h0ugh7_17_c4n_0nly_b3_s0lv3d_by_F3rm4t's_F4ct0r1s4710n}