Infobahn CTF 2025「YAOL」Crypto Writeup

こちらはYuruvent Advent Calendar 2025 5日目の記事です️

はじめに

CTFでCryptoをメインに解いているのだが、面白いなと思うCrypto問題を見つけたので共有します。

問題

概要

CTF名: Infobahn CTF 2025
ジャンル: Crypto
問題名: YAOL
Solves: 63
URL: https://github.com/infobahnctf/CTF-2025/tree/main/crypto/YAOL

print(pow(5, int.from_bytes(b"infobahn{redacted}") , 1630517278473550194282041875833486355623215533573046940060264097136914038603536518992736923653676649116183817847560673180565058236761676707835672941973386700920193823734995675702699))
# 1205311994677213080553672976329272430376280336788757947479560449449519106113423651935986946100928433620706242735988889202701964570414180506408210904986303602097717823742023879116357

以下の式と計算結果のみです。

$$c = 5^{\mathrm{flag}} \mod N$$

解説

factorDBで見てみると、$N$の値は

$$1176996401679752890373209353249071857076030810114990527710899^3$$

であることがわかる。

ここで、Felmatの小定理から

$$x^{p-1} \equiv 1 \mod p$$

となる。
$ord = p-1$とすると、

$$c = c^{p-1} \equiv 1 \mod p^3 \\ g = 5^{p-1} \equiv 1 \mod p^3$$

となります。よって

$$c \equiv 1 \mod p \\ g \equiv 1 \mod p$$

と考えることができ、

$$c = c^{p-1} \equiv (5^m)^{p-1} = (5^{p-1})^m = g^m \mod p^3$$

となるので、p進対数で解くことができます。
p進体$\mathbb{Q}_p$とすると、$\mathbb{Q}_p$上で、

$$c = g^m$$

とみなせます。
これにp進対数を取ると、

$$\log(c) = \log(g^m) = m \log(g)$$

となり、

$$m = \frac{\log(c)}{\log(g)}$$

と考えることができ、フラグを取得できます。

解答コード

from sage.all import *
from Crypto.Util.number import long_to_bytes

N = ZZ(1630517278473550194282041875833486355623215533573046940060264097136914038603536518992736923653676649116183817847560673180565058236761676707835672941973386700920193823734995675702699)

p = N.nth_root(3)
Fp = Zmod(p**3)
ord = (p - 1)

c = pow(1205311994677213080553672976329272430376280336788757947479560449449519106113423651935986946100928433620706242735988889202701964570414180506408210904986303602097717823742023879116357, ord, N)
g = pow(5, ord, N)

FQp = Qp(p, 3)
FQp_c = FQp(c).log()
FQp_g = FQp(g).log()

print(long_to_bytes(ZZ(FQp_c/FQp_g)).decode())

infobahn{Eric_Bach_is0m0rph1sms_fr0m_1984!}