ぺんぎんさんのおうち

日本語勉強中のドイツ産ペンギンがいろんなことを書く

CODEBLUE CTF [Write-up]

CODEBLUE CTFにHarekazeとして参加し、最終的に1480p取得し17位でした。
そのうち僕は2問解いて231p入れました。
以下Write-upです。

Common Modulus 1 (98)
同じ平文mを、異なるe1,e2と同一のnを使って暗号化しています。
RSAに対するCommon Modulus Attackが使えますね。
solverはももテクさんからお借りしました。
http://inaz2.hatenablog.com/entry/2016/01/15/011138

import gmpy

def common_modulus_attack(c1, c2, e1, e2, n):
    gcd, s1, s2 = gmpy.gcdext(e1, e2)
    print(gcd, s1, s2)
    if s1 < 0:
        s1 = -s1
        c1 = gmpy.invert(c1, n)
    elif s2 < 0:
        s2 = -s2
        c2 = gmpy.invert(c2, n)
    v = pow(c1, s1, n)
    w = pow(c2, s2, n)
    m = (v * w) % n
    return m

for line in open("params"):
    exec(line)
    ```
    c1 = 
    c2 = 
    e1 = 
    e2 = 
    n = n1 or n2 (n1==n2)
    ```


print(hex(common_modulus_attack(c1,c2,e1,e2,n)))


Common Modulus 2 (133)
先ほどとは違い, e = 3 * get_random_prime(20) 適当な素数を取得してから3倍しています。
本来であれば

GCD(e1, e2) = 1 

になるところ、*3したことで

GCD(e1, e2) = 3

になっています。
ここで、Common Modulus Attackの復号の式は

c1 = m^e1 mod n
c2 = m^e2 mod n

このとき、e1 * s + e2 * t = GCD(e1, e2) = 1 
となる組み合わせ (s, t) をみつける

c1^s * c2^t = (m^e1)^s * (m^e2)^t mod n
                = m ^(e1*s) * m ^ (e2*t) mod n
                = m ^ (e1*s + e2*t) mod n
                = m ^ 1 mod n
                = m

今回は

GCD(e1, e2) = 3

なので、最終的に得られるのは

c1^s * c2^t = m ^ 3

となります。あとはmの三乗根を取ればフラグです。

import gmpy
import binascii
def common_modulus_attack(c1, c2, e1, e2, n):
    gcd, s1, s2 = gmpy.gcdext(e1, e2)
    #print(gcd, s1, s2)
    if s1 < 0:
        s1 = -s1
        c1 = gmpy.invert(c1, n)
    elif s2 < 0:
        s2 = -s2
        c2 = gmpy.invert(c2, n)
    v = pow(c1, s1, n)
    w = pow(c2, s2, n)
    m = (v * w) % n
    return m

for line in open("params"):
    exec(line.strip())
    ```
    c1 = 
    c2 = 
    e1 = 
    e2 = 
    n = n1 or n2 (n1==n2)
    ```

m = common_modulus_attack(c1,c2,e1,e2,n1)
m = gmpy.root(m,3)[0]

print(binascii.unhexlify(hex(m)[2:]))

xs + yt = GCD(x, y) = 1 のとき、
cxs + cyt = GCD(x, y) = c
が成り立つので(今回の場合はc=3)、例えばe1, e2 を3で割ってもgcdが1になるだけで s, t は変わりません。
何かるんじゃないかとこれでずっと悩んでいました。