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