Tokyo Westerns CTF 3rd 2017: BabyDLP

,

寝てる間にkonjoさんが解いてくれました。

problem

素数$p$と整数$g$および暗号化oracle $\mathrm{oracle}(s) = c \equiv g^{m \oplus s} \pmod{p}$が与えられる。$m$を答えよ。

solution

$\mathrm{oracle}(2^k)$を考えると$m$の$k$-bit目に対応して$\mathrm{oracle}(0) \cdot g^{\pm 2^k}$。 これをそれぞれの$k$で試せば終わり。

$g = 2$でなくても解ける。 line = fin.readline()[:4+bits//4]は今回は何も邪魔をしない。$m$のbit数より小さい制約だと問題になる。

implementation

#!/usr/bin/env python2
from pwn import * # https://pypi.python.org/pypi/pwntools
import argparse
parser = argparse.ArgumentParser()
parser.add_argument('host', nargs='?', default='ppc2.chal.ctf.westerns.tokyo')
parser.add_argument('port', nargs='?', default=28459, type=int)
parser.add_argument('--log-level', default='debug')
args = parser.parse_args()
context.log_level = args.log_level

# params
p = 160634950613302858781995506902938412625377360249559915379491492274326359260806831823821711441204122060415286351711411013883400510041411782176467940678464161205204391247137689678794367049197824119717278923753940984084059450704378828123780678883777306239500480793044460796256306557893061457956479624163771194201
g = 2
bits = 1024

# connect
proc = remote(args.host, args.port)
def oracle(s):
    line = hex(s)[2 :]
    assert line == line[: 4 + bits // 4]
    proc.sendline(line)
    c = int(proc.recvline(), 16)  # c = pow(g, m ^ s, p)
    return c

# run
c0 = oracle(0)
m = 0
i = 1
while i <= p:
    ci = oracle(i)
    if c0 == ci * pow(g, i, p) % p:
        m |= i
    else:
        assert ci == c0 * pow(g, i, p) % p
    log.info('m = %#x', m)
    i <<= 1

# result
log.info('flag = %s', hex(m)[2 :].decode('hex'))