この大会は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}