SECCON 2023 CTF writeup (plai_n_rsa)

問題

problem.py

import os

from Crypto.Util.number import bytes_to_long, getPrime

flag = os.getenvb(b"FLAG", b"SECCON{THIS_IS_FAKE}")
assert flag.startswith(b"SECCON{")
m = bytes_to_long(flag)
e = 0x10001
p = getPrime(1024)
q = getPrime(1024)
n = p * q
e = 65537
phi = (p-1)*(q-1)
d = pow(e, -1, phi)
hint = p+q
c = pow(m,e,n)

print(f"e={e}")
print(f"d={d}")
print(f"hint={hint}")
print(f"c={c}")

output.txt

e=65537
d=15353693384417089838724462548624665131984541847837698089157240133474013117762978616666693401860905655963327632448623455383380954863892476195097282728814827543900228088193570410336161860174277615946002137912428944732371746227020712674976297289176836843640091584337495338101474604288961147324379580088173382908779460843227208627086880126290639711592345543346940221730622306467346257744243136122427524303881976859137700891744052274657401050973668524557242083584193692826433940069148960314888969312277717419260452255851900683129483765765679159138030020213831221144899328188412603141096814132194067023700444075607645059793
hint=275283221549738046345918168846641811313380618998221352140350570432714307281165805636851656302966169945585002477544100664479545771828799856955454062819317543203364336967894150765237798162853443692451109345096413650403488959887587524671632723079836454946011490118632739774018505384238035279207770245283729785148
c=8886475661097818039066941589615421186081120873494216719709365309402150643930242604194319283606485508450705024002429584410440203415990175581398430415621156767275792997271367757163480361466096219943197979148150607711332505026324163525477415452796059295609690271141521528116799770835194738989305897474856228866459232100638048610347607923061496926398910241473920007677045790186229028825033878826280815810993961703594770572708574523213733640930273501406675234173813473008872562157659306181281292203417508382016007143058555525203094236927290804729068748715105735023514403359232769760857994195163746288848235503985114734813

考察

よくある問題(普通のRSA暗号)では $e$ と $n$ が与えられて $d$ が分からないことが多いが、今回は最初に $d$ が与えられていて $n$ が分からないというちょっと変わった問題である。

$e, d$ の関係式から、 $ed \equiv 1 \mod (p-1)(q-1)$ ということがわかる。つまり、ある整数 $k$ を使って、 $de - 1 = k(p-1)(q-1)$ とおくことができる。
その $k$ を求めることができれば、 $n = pq$ であることと $p + q$ が与えらえてこることで $n$ が求められる。

解法

$\log_2 (de - 1) = 2062.9$ で、対する $n$ は 2048 bit 程度の数になるので、求めるべき $k$ は 14 ビット程度で表される数となる。その程度であれば全通り試せば解けそう。

solve.py

e=65537
d=15353693384417089838724462548624665131984541847837698089157240133474013117762978616666693401860905655963327632448623455383380954863892476195097282728814827543900228088193570410336161860174277615946002137912428944732371746227020712674976297289176836843640091584337495338101474604288961147324379580088173382908779460843227208627086880126290639711592345543346940221730622306467346257744243136122427524303881976859137700891744052274657401050973668524557242083584193692826433940069148960314888969312277717419260452255851900683129483765765679159138030020213831221144899328188412603141096814132194067023700444075607645059793
hint=275283221549738046345918168846641811313380618998221352140350570432714307281165805636851656302966169945585002477544100664479545771828799856955454062819317543203364336967894150765237798162853443692451109345096413650403488959887587524671632723079836454946011490118632739774018505384238035279207770245283729785148
c=8886475661097818039066941589615421186081120873494216719709365309402150643930242604194319283606485508450705024002429584410440203415990175581398430415621156767275792997271367757163480361466096219943197979148150607711332505026324163525477415452796059295609690271141521528116799770835194738989305897474856228866459232100638048610347607923061496926398910241473920007677045790186229028825033878826280815810993961703594770572708574523213733640930273501406675234173813473008872562157659306181281292203417508382016007143058555525203094236927290804729068748715105735023514403359232769760857994195163746288848235503985114734813
kphi = d * e - 1

def solve(k: int):
    if kphi % k != 0:
        return

    n = (kphi // k) + hint  - 1
    m = pow(c,d,n)
    flag = m.to_bytes(256, byteorder="big")
    if b"SECCON{" in flag:
        print(flag.decode("utf-8"))

for i in range(1, 66000):
    try:
        solve(i)
    except:
        pass

実際にプログラムを書いて、無事解くことができた！

おわりに

SECCON 参加3回目にして、初めて問題が解けた。ようやく一歩進めてよかった。
今まで解けなくても1問は writeup を書いていたが、今回バイト列と文字列の変換方法で参考にすることができ書いておいてよかったと思った。

https://zenn.dev/firedial/articles/7a7d6ac3e53fa4