HackTM CTF Quals 2023 に参加していました。今年の運営はあのy011d4さんが所属するWreckTheLineということで期待していましたが、想像を超える質と難易度のCrypto問題セットでした。
私はぼこぼこにされて全然解けませんでした。得意技であるところのFranklin-Reiter's related message attackとか、グレブナー基底やresultantを使って式を整理する技が活躍する問題でちゃんと技を発動できなかったのが悔やまれます。
唯一解けたd-phi-encも得意技が使えればもっとスマートに解けていそうでしたが、なんか力技で解いてしまったのでそのwriteupです。
問題概要
問題はすでに以下のリポジトリで公開されていますが、改めて掲載するとこういう感じです。
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 = }")
のRSAで、を暗号化したものが一緒に与えられている点がユニークです。初見の感想は「へーこれ解けるの」でした*1。
やを暗号化したものが渡されていることからRSAの情報準同型性を使いそう、と小さいのでとかいた時のが小さく全探索できそう、などに思い至ります*2。
近似パート
とりあえずを決め打ってしまいます。にわかっている値を代入するとです。で、ごく大雑把にと思うとです。のとの差はの約1024bitですから、は上位1000bitくらいが一致し、下位bit程度が不明な近似になっています。もうちょっと頑張れば大体の半分以下のサイズと言えるのでCoppersmithなどでを求めることができそうです
もうちょっと頑張るパートは全探索ってやつをやります
立式パート
の上位bitがわかっているといえばpbctf2020 | Special Giftですが、今回はが小さいのでの式で解くことは難しそうです。とおいてのmultivariate coppersmithはできるか怪しいです。
そこで今回は与えられているを使います。
を全部のRSAで暗号化したと思うとです。この式では未知数はだけなので、先ほどの近似を使えば とかいて1024bit未満の未知数は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:]))
感想
なんでこんなゴリ押ししてしまったんや……。解けてよかったです