CODE BLUE CTF 2017: Common Modulus 3
problem
Common Modulus 2と同様。ただし$e_1, e_2$への乗数は$3$でなく$17$、$m$はflagそのままでなくpadding付き。
solution
Coppersmith’s attack。
非想定解として$m \cdot k^{-1}$の$17$乗根を取るというのがあったらしい。paddingが単に$k$を乗算しているだけであり$\mathrm{FLAG}^17 \lt N$なので求まってしまう。
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
assert e1 < e2
while e1:
c1, c2 = c2 * (1 / c1) ** (e2 / e1), c1
e1, e2 = e2 % e1, e1
assert e2 == 17
# Coppersmith's attack
PR.<x> = PolynomialRing(Zmod(n))
l = 32
pad = 984
f = (((bytes_to_long('CBCTF{') * 256 ** l + x) * 256 + ord('}')) * 256 ** pad) ** 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) * 256 ** pad
assert m ** e2 == c2