CTFZone 2017 Writeup

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

MPRSA (CRYPTO)

Multi-Prime RSAの問題。まず素因数分解したいが、factordbではできなかった。
暗号化のプログラムから、deltaの値(5～15)は総当たりで素数の構成を作り、nと同じ値になるものを探す。数時間かかったが、次のようなプログラムで素因数を割り出すことができた。ちなみに delta=14の場合に該当するnが見つかった。

from gmpy2 import next_prime

def compute_module(primes):
    n = 1
    for prime in primes:
        n *= prime
    return n

with open('public.txt', 'r') as f:
    data = f.read()

n = int(data.split('\n')[1].split(' = ')[1])

delta = 14
p = 177739015005173300000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000

adjust = pow(2, 1024)
p0 = p
while True:
    #print p
    P = [next_prime(p)]
    for i in range(1, 4):
        P.append(next_prime(P[i-1] * delta))
    mul = compute_module(P)
    print mul
    if mul == n:
        print 'P[0] =', P[0]
        print 'P[1] =', P[1]
        print 'P[2] =', P[2]
        print 'P[3] =', P[3]
        break
    else:
        diff = n - mul
        if diff < 0:
            if adjust == 1:
                print 'Not Found (delta = %d)' % delta
                break
            else:
                adjust /= 2
                p = p0
        else:
            p0 = p
            p = next_prime(p + adjust)

素因数分解の結果は以下の通り。

P[0] = 177739015005173306533752250332928388271426563815093455666936081629571193511808970499241559574326686383600364964248435983786753776661738101198468295487687752622214814554023747926012377837938347566934895426939099916675611018615527164379921811922640194594903892753383803569371101697376356302460080232868430713251
P[1] = 2488346210072426291472531504660997435799971893411308379337105142813996709165325586989381834040573609370405109499478103773014552873264333416778556136827628536711007403756332470964173289731136865937088535977147398833458554260617380301318905366916962724328654498547373249971195423763268988234441123260158029986729
P[2] = 34836846941013968080615441065253964101199606507758317310719471999395953928314558217851345676568030531185671532992693452822203740225700667834899785915586799513954103652588654593498426056235916123119239503680063583668419759648643324218464675136837478140601162979663225499596735932685765835282175725642212419814243
P[3] = 487715857174195553128616174913555497416794491108616442350072607991543354996403815049918839471952427436599401461897708339510852363159809349688597002818215193195357451136241164308977964787302825723669353051520890171357876635081006539058505451915724693968416281715285156994354303057600721693950460158990973877400281

この結果から、Muti-Prime RSAの復号プログラムを書く。

import gmpy

def chinese_remainder(n, a):
    sum = 0
    prod = reduce(lambda a, b: a*b, n)

    for n_i, a_i in zip(n, a):
        p = prod / n_i
        sum += a_i * gmpy.invert(p, n_i) * p
    return sum % prod

with open('data.enc', 'r') as f:
    c = int(f.read())

with open('public.txt', 'r') as f:
    pub = f.read()

e = int(pub.split('\n')[0].split(' = ')[1])
n = int(pub.split('\n')[1].split(' = ')[1])

primes = [
    177739015005173306533752250332928388271426563815093455666936081629571193511808970499241559574326686383600364964248435983786753776661738101198468295487687752622214814554023747926012377837938347566934895426939099916675611018615527164379921811922640194594903892753383803569371101697376356302460080232868430713251,
    2488346210072426291472531504660997435799971893411308379337105142813996709165325586989381834040573609370405109499478103773014552873264333416778556136827628536711007403756332470964173289731136865937088535977147398833458554260617380301318905366916962724328654498547373249971195423763268988234441123260158029986729,
    34836846941013968080615441065253964101199606507758317310719471999395953928314558217851345676568030531185671532992693452822203740225700667834899785915586799513954103652588654593498426056235916123119239503680063583668419759648643324218464675136837478140601162979663225499596735932685765835282175725642212419814243,
    487715857174195553128616174913555497416794491108616442350072607991543354996403815049918839471952427436599401461897708339510852363159809349688597002818215193195357451136241164308977964787302825723669353051520890171357876635081006539058505451915724693968416281715285156994354303057600721693950460158990973877400281]

n_ary = []
a_ary = []
for p in primes:
    phi = p - 1
    d = gmpy.invert(e, phi)
    mk = pow(c, d, p)
    n_ary.append(p)
    a_ary.append(mk)

m = chinese_remainder(n_ary, a_ary)
flag = ('%x' % m).decode('hex')
print flag

実行結果は次の通り。

Mr.D (12:10):
Okey, see you later ;)

Mr.D (19:30):
So can you help me?

Anonymous (19:31):
Yeah, we will have 10,000 falsified voters. Transfer 100000$ to my bank account: ctfzone{3177809746931830}

ctfzone{3177809746931830}