CODEBLUE CTF 2017 Common Modulus 1~3

common_modulus_1_solver.py

# coding:utf-8
# CODEBLUE CTF 2017 Common Modulus 1
from m1z0r3.crypro import *

def main():
    ts_data = open("transcript.txt").read()
    ts_data = ts_data.split("\n")
    n1, e1 = eval(ts_data[0].split(":")[-1])
    c1 = long(ts_data[1].split("=")[-1])
    n2, e2 = eval(ts_data[3].split(":")[-1])
    c2 = long(ts_data[4].split("=")[-1])
    neclist = [[n1,e1,c1],[n2,e2,c2]]
    print common_modulus_attack(neclist)
    # CBCTF{6ac2afd2fc108894db8ab21d1e30d3f3}

if __name__ == "__main__":
    main()

common_modulus_2_solver.py

# coding:utf-8
# CODEBLUE CTF 2017 Common Modulus 2
from m1z0r3.crypro import l2b, b2l,egcd, modinv
import gmpy

def cma(neclist):
    n1, e1, c1 = neclist[0]
    n2, e2, c2 = neclist[1]
    _,a1,a2 = egcd(e1,e2)
    
    if a1<0:
        tmp = a1
        a1 = a2
        a2 = tmp
        tmp = e1
        e1 = e2
        e2 = tmp
        tmp = c1
        c1 = c2
        c2 = tmp

    n = neclist[1][0]
    ic2 = modinv(c2,n) # Because we can't calc modinv of negative integer.
    m = ( pow(c1,a1,n)*pow(ic2,-a2,n) ) % n
    m = gmpy.root(m,3)[0]
    return l2b(m)

def main():
    ts_data = open("transcript.txt").read()
    ts_data = ts_data.split("\n")
    n1, e1 = eval(ts_data[0].split(":")[-1])
    c1 = long(ts_data[1].split("=")[-1])
    n2, e2 = eval(ts_data[3].split(":")[-1])
    c2 = long(ts_data[4].split("=")[-1])
    neclist = [[n1,e1,c1],[n2,e2,c2]]
    print cma(neclist)
    # CBCTF{d65718235c137a94264f16d3a51fefa1}



if __name__ == "__main__":
    main()

common_modulus_3_solver.py

# coding:utf-8
# CODEBLUE CTF 2017 Common Modulus 1

from m1z0r3.crypro import l2b, b2l,egcd, modinv
import gmpy

def cma(neclist):
    n1, e1, c1 = neclist[0]
    n2, e2, c2 = neclist[1]
    _,a1,a2 = egcd(e1,e2)

    if a1<0:
        tmp = a1
        a1 = a2
        a2 = tmp
        tmp = e1
        e1 = e2
        e2 = tmp
        tmp = c1
        c1 = c2
        c2 = tmp

    n = neclist[1][0]
    ic2 = modinv(c2,n) # Because we can't calc modinv of negative integer.
    m = ( pow(c1,a1,n)*pow(ic2,-a2,n) ) % n
    return m

def main():
    ts_data = open("transcript.txt").read()
    ts_data = ts_data.split("\n")
    n1, e1 = eval(ts_data[0].split(":")[-1])
    c1 = long(ts_data[1].split("=")[-1])
    n2, e2 = eval(ts_data[3].split(":")[-1])
    c2 = long(ts_data[4].split("=")[-1])
    assert n1 == n2
    neclist = [[n1,e1,c1],[n2,e2,c2]]
    m =  cma(neclist) # m^17 mod N -> (flag * 2^x)^17 mod N -> (flag^17 * 2^17x) mod N -> flag ^17 mod N

    print "Brute force..."
    for i in xrange(1,9000):
        a = pow(2,17*i,n1)
        tmp = gmpy.invert(a,n1)
        flag17 = (m * tmp) % n1
        flag = gmpy.root(flag17, 17)[0]
        if "CBCTF" in l2b(flag):
            print "Detect"
            print l2b(flag) # CBCTF{b5c96e00cb90d11ec6eccdc58ef0272d}
            break


if __name__ == "__main__":
    main()

Common Modulus 1

二つのexponent(e1, e2)が互いに素の関係にあるので、Common Modulus Attackをやれば解ける。
具体的には、互いに素であれば、a1*e1 + a2*e2 = 1 となるようなa1, a2が見つかるので、
二つの暗号文をC1, C2, 共通のModulusをnとし、
C1^a1 * C2^a2 mod n
を計算する。
C1^a1 * C2^a2 ≡ m^(a1*e1) * m^(a2*e2) ≡ m^(a1*e1 + a2*e2) ≡ m (mod n)
となるため、平文m を求めることができる。

Common Modulus 2

二つのexponentが互いに素ではなく、最大公約数として3を持つように作られている。
従って、拡張ユークリッドの互除法を用いれば
a1*e1 + a2*e2 = 3
となるようなa1, a2を見つけることができる。
Common Modulus 1の式に当てはめると、m ^ 3 (mod n)を求めることができる。
今回 m が小さく、m^3 < nであるため、単に3乗根を取ることで 平文mが求まる。

Common Modulus 3

ここまでの原理でいくと、m^17 (mod n)が求まり、17乗根を取ることで平文mが求まりそうである。
しかしながら、今回の平文はflagだけでなく、末尾に0パディングが付与され、m^17 > nとなってしまい、
正確な平文mを求めることができない。
そこで、今回のパディング形式はflagを2^xビットシフトしていることと同じであることに着目する。
flagの2^xビットシフトは、flag * 2^xと同じであるため、以下のように書くことができる。
C1^a1 * C2^a2 ≡ m^17 ≡ (flag * 2*x)^17 ≡ flag^17 * (2^17)^x (mod n)
従って、nを法とした時の(2^17)^x の逆元を求めて上の式にかければ、 flag^17 (mod n)
を得ることが可能。flagがnに比べて小さいので、flag^17 < nとなり、17乗根を取ればflagが求まる。
x は総当たりするか、前問のフラグの長さを見て決め打ちする。