ふるつき

v(*'='*)v かに

HackTM CTF Quals 2023 writeup - d-phi-enc

HackTM CTF Quals 2023 に参加していました。今年の運営はあのy011d4さんが所属するWreckTheLineということで期待していましたが、想像を超える質と難易度のCrypto問題セットでした。

私はぼこぼこにされて全然解けませんでした。得意技であるところのFranklin-Reiter's related message attackとか、グレブナー基底やresultantを使って式を整理する技が活躍する問題でちゃんと技を発動できなかったのが悔やまれます。

唯一解けたd-phi-encも得意技が使えればもっとスマートに解けていそうでしたが、なんか力技で解いてしまったのでそのwriteupです。

問題概要

問題はすでに以下のリポジトリで公開されていますが、改めて掲載するとこういう感じです。

github.com

from Crypto.Util.number import bytes_to_long, getStrongPrime

from secret import flag

assert len(flag) == 255
e = 3
p = getStrongPrime(1024, e=e)
q = getStrongPrime(1024, e=e)
n = p * q
phi = (p - 1) * (q - 1)
d = pow(e, -1, phi)
enc_d = pow(d, e, n)
enc_phi = pow(phi, e, n)
enc_flag = pow(bytes_to_long(flag), e, n)
print(f"{n = }")
print(f"{enc_d = }")
print(f"{enc_phi = }")
print(f"{enc_flag = }")

 e=3RSAで、 d, \phiを暗号化したものが一緒に与えられている点がユニークです。初見の感想は「へーこれ解けるの」でした*1

 d \phiを暗号化したものが渡されていることからRSAの情報準同型性を使いそう、 e=3と小さいので ed = 1 + k\phiとかいた時の kが小さく全探索できそう、などに思い至ります*2

近似パート

とりあえず k=2を決め打ってしまいます。 ed = 1 + k\phiにわかっている値を代入すると 3d = 1 + 2\phiです。 \phi = n - (p + q) + 1で、ごく大雑把に \phi \approx nと思うと d \approx \frac{2n}{3} + 1です。 \phi nとの差は p + qの約1024bitですから、 dは上位1000bitくらいが一致し、下位 1024bit程度が不明な近似になっています。もうちょっと頑張れば大体 nの半分以下のサイズと言えるのでCoppersmithなどで dを求めることができそうです

もうちょっと頑張るパートは全探索ってやつをやります

立式パート

 dの上位bitがわかっているといえばpbctf2020 | Special Giftですが、今回は eが小さいので \mod eの式で解くことは難しそうです。 s = p + qとおいて e(d' + \alpha) \equiv 1 + 2*(-s + 1) \mod nのmultivariate coppersmithはできるか怪しいです。

そこで今回は与えられている E(d) = d^3 \pmod n, E(\phi) = \phi^3 \pmod nを使います。

 ed - 1 = 2\phiを全部 e=3RSAで暗号化したと思うと 27E(d) - 27d^2 + 9d - 1 \equiv 8E(\phi) \mod nです。この式では未知数は dだけなので、先ほどの近似を使えば d = d' + \alpha とかいて1024bit未満の未知数 \alphaはCoppersmith's methodで求められそうです。

solver

from Crypto.Util.number import bytes_to_long, getStrongPrime
from tqdm import tqdm


e = 3
n = ...
enc_d = ...
enc_phi = ...
enc_flag = ..


tt = n // 3
d_ = 2*tt + 1
unknown_bits = 1025
guess_size = 10
known_d = (d_ >> unknown_bits) << unknown_bits

PR.<lower_d> = PolynomialRing(Zmod(n))

for a in tqdm(range(2**guess_size)):
    d = known_d + (a << (unknown_bits - guess_size)) + lower_d
    f = (8*enc_phi - 27*enc_d) - (-27*d**2 + 9*d - 1)
    f = f.monic()

    roots = f.small_roots(X=2**(unknown_bits - guess_size), beta=1, epsilon=1/7)
    if len(roots):
        d = known_d + (a << (unknown_bits - guess_size)) + roots[0]
        m = pow(enc_flag, d, n)
        print(bytes.fromhex(hex(m)[2:]))

感想

なんでこんなゴリ押ししてしまったんや……。解けてよかったです

*1:だいたいこういうことを言っているときはこういう問題設定が解けることに感動しています

*2:今思うとここまで考えて \phiに関するFranklin-Reiterに辿り着かないことあるんだ……という感じですね