Code Blue CTF 2017にでた話

はじめに

このCode Blue CTF 2017が自分にとって2度目の大会だった．最初に参加したKOSEN SECCONより規模も大きく難しそうだったので始まる前は緊張した． 10時から翌日の16時まで開催された自分はCommon Modulus Attack１の1問しか解けなかった．だからCommon Modulus Attack1のwrite-upを書く．

Common Modulus Attack1のwrite-up

まずCommon Modulus AttackとはRSA公開鍵(n,e1)(n,e2)と平文Mをそれぞれの鍵で暗号化したc1,c2が与えらていて，e1とe2が互いに素だった時にこれらから平文Mを計算できるというもの． 互いに素とはe1とe2の最大公約数が1であるということを意味する．そのあと拡張ユークリッドの互除法をつかってe1x+e2y=0となるようなxとyを計算する． そして(c1のx乗)×(c2のy乗)を計算したら平文Mが求められる．自分はこれらをpythonで実装した．最後に文字列に変換すればFLAGがゲットできる．

以下がソースコード．

import gmpy
import sys
import binascii

sys.setrecursionlimit(10000000)


c1 = 
c2 =

e1 =
e2 =
n =
def egcd(a, b):
    if a == 0:
        return (b, 0, 1)
    else:
        g, y, x = egcd(b%a, a)
        return (g, x - (b // a) * y, y)

def modinv(a, m):
    g, x, y = egcd(a, m)
    return x % m

def commom_world(c1, c2, e1, e2, n):
    gcd, s1, s2 = egcd(e1, e2)
    print gcd
    print s1
    print s2
    if s1 < 0:
        s1 = -s1
        c1 = modinv(c1, n)
    elif s2 < 0:
        s2 = -s2
        c2 = modinv(c2, n)

    v = pow(c1, s1, n)
    w = pow(c2, s2, n)
    x = (v*w) % n
    return x

flag = commom_world(c1, c2, e1, e2, n)
message = binascii.unhexlify(format(flag, 'x')).decode()
print flag
print message

各変数に値を代入すれば動く．

まとめ

Code Blue CTF 2017はRSA問題が多かった気がした．そのうち1問しか解けなかったのが悔しい．これからはRSAのほかの攻撃手段や脆弱性をもっと勉強していきたい．