CODE BLUE CTF 2017: Common Modulus 2

,

https://ctftime.org/task/4873

実質WA。

problem

Common Modulus 1と同様。ただし$e_1, e_2$は共に素数に$3$を掛けたもの。

solution

平文$m$に対するCoppersmith’s attack。$e = 3$と小さいので$|x| \lt N^{\frac{1}{3}}$であり、求まる。

想定解は単に$3$乗根取るだけ。

implementation

#!/usr/bin/env sagemath
import ast
from Crypto.Util.number import long_to_bytes, bytes_to_long

# input
with open('transcript.txt') as fh:
    n, e1 = ast.literal_eval(fh.readline().split(': ')[1].replace('L', ''))
    c1 = Zmod(n)(fh.readline().split('=')[1])
    fh.readline()
    n, e2 = ast.literal_eval(fh.readline().split(': ')[1].replace('L', ''))
    c2 = Zmod(n)(fh.readline().split('=')[1])

# Euclidean algorithm
c1, c2 = c2, c1
e1, e2 = e2, e1
assert e1 < e2
while e1:
    c1, c2 = c2 * (1 / c1) ** (e2 / e1), c1
    e1, e2 = e2 % e1, e1
assert e2 == 3

# Coppersmith's attack
PR.<x> = PolynomialRing(Zmod(n))
for l in range(64):
    f = (bytes_to_long('CBCTF{') * 256 ** (l + 1) + x * 256 + ord('}')) ** e2 - c2
    f = f.monic()
    for x in f.small_roots(X=256 ** l, beta=0.5):
        flag = 'CBCTF{' + long_to_bytes(x) + '}'

        # output
        print(flag)
        m = bytes_to_long(flag)
        assert m ** e2 == c2