WhiteHat Grand Prix 2016 Writeup

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

Banh cuon (Cryptography 200)

RSA暗号の問題。素因数分解した結果が提示されているので、それを元に復号するプログラムを作成する。

import gmpy2
import binascii

e = 65537
p1 = 346284627819235013
p2 = 48108377392359593329
p3 = 91836381613824658927
p4 = 37252538404847211828439
p5 = 27262151738933289423634232512139
p = 1553762687409601943499178289783616523235812050573150316009646301542436391128879624646734300008782361965139513359
q = 18393926378291118190346463738382882261613293132387833409
c = 12682879488984861193795141642779903374526316499885184966492486107034525136565770064564244757954564431956497062324291051476829691654157833815737932841382692373398780347

def factorize(N):
    tmp = N

    primes = [p1, p2, p3, p4, p5, q]
    factors = []
    for p in primes:
        if tmp == 1:
            break
        cnt = gmpy2.mpz(0)
        while tmp % p == 0:
            tmp /= p
            cnt += 1
        if cnt > 0:
            factors.append([gmpy2.mpq(p), cnt])
    if tmp != 1:
        return None
    return factors

def find_phi(N):
    factors = factorize(N)
    if factors is None:
        return None
    phi = gmpy2.mpq(N)
    for f in factors:
        phi = phi * (1 - 1 / f[0])
    return phi

def solve():
    N = gmpy2.mpz(str(p*q))
    C = gmpy2.mpz(str(c))
    E = gmpy2.mpz(str(e))
    
    phi = gmpy2.mpz(find_phi(N))
    if phi is None:
        print 'Failed to factorize N'
        return None

    d = gmpy2.invert(E, phi)
    m = gmpy2.powmod(C, d, N)   
    return binascii.unhexlify(gmpy2.digits(m, 16))
    
def main():
    gmpy2.get_context().precision=1000
    result = solve()
    if result is None:
        print 'Failed!'
        return
    print result
    
if __name__ == "__main__":
    main()

実行すると、以下の通り表示された。
Yup! WhiteHat{ff94658cf7612e7f68de6d960caf6f9b92e8a4a4}!

WhiteHat{ff94658cf7612e7f68de6d960caf6f9b92e8a4a4}