書こうと思って先延ばししすぎました。
Full Weak Engineer CTF 2025 Writeupです。
私が作問したCryptoと場所の特定をしたGeoGuessrシリーズ(OSINT)を解説します。
また、英語での解説も記事に書いていますので、そちらもぜひ。
https://zenn.dev/potyama/articles/fad2ebaadc04f0
OSINT
私の作問チェックは以下の通りです。
- GeoGuessr1
- GeoGuessr2
- GeoGuessr3
- GeoGuessr4
なお、本問題の作問チェック時はLLMを使わないで解いています。
GeoGuessr1
問題
この写真を撮っている人の座標を指定してください。 また、座標を直接指定すると誤差の許容範囲が表示されません。マウスクリックでご確認ください。
Please specify the coordinates of the person who took this photo. Note that if you enter the coordinates directly, the tolerance zone will not be shown. Please check it by clicking with the mouse.
解法
"KFC 1065"と調べると画像のKFCが出てきます。
後は左側に見えている看板を基に位置を特定したらOKです。
GeoGuessr2
この写真を撮っている人の座標を指定してください。 また、座標を直接指定すると誤差の許容範囲が表示されません。マウスクリックでご確認ください。
Please specify the coordinates of the person who took this photo. Note that if you enter the coordinates directly, the tolerance zone will not be shown. Please check it by clicking with the mouse.
解法
言語からドイツ語っぽい？
kaisertor frankfurtで調べると以下のインスタが出てきます。
https://www.instagram.com/kaisertor_frankfurt/?hl=en
住所が乗っているので、Google mapと写真を見ながら位置を合わせたらOKです。
GeoGuessr3
問題
この写真を撮っている人の座標を指定してください。 また、座標を直接指定すると誤差の許容範囲が表示されません。マウスクリックでご確認ください。
Please specify the coordinates of the person who took this photo. Note that if you enter the coordinates directly, the tolerance zone will not be shown. Please check it by clicking with the mouse.
解法
Phonixという店に$10と書かれていることからアメリカを予想。
また、中華街っぽい雰囲気はあるのでチャイナタウンかなと予想。
ここでGoogle レンズを使ったら
ロサンゼルスにチャイナタウンかつ写真と雰囲気が似ている場所が存在していることがわかります。
Los Angeles phoenix clothing storeと調べ、探すとここが出てきます。
https://www.google.com/maps/@34.0657151,-118.2376765,3a,85.2y,109.69h,88.9t/data=!3m7!1e1!3m5!1s9vQcvqZzG6kRXl8v_h4SQg!2e0!6shttps:%2F%2Fstreetviewpixels-pa.googleapis.com%2Fv1%2Fthumbnail%3Fcb_client%3Dmaps_sv.tactile%26w%3D900%26h%3D600%26pitch%3D1.0981144647386003%26panoid%3D9vQcvqZzG6kRXl8v_h4SQg%26yaw%3D109.69222454776005!7i16384!8i8192?entry=ttu&g_ep=EgoyMDI1MDgyNS4wIKXMDSoASAFQAw%3D%3D
後は、写真が撮られた場所にピンを指せばOKです。
GeoGuessr4
この写真を撮っている人の座標を指定してください。 また、座標を直接指定すると誤差の許容範囲が表示されません。マウスクリックでご確認ください。
Please specify the coordinates of the person who took this photo. Note that if you enter the coordinates directly, the tolerance zone will not be shown. Please check it by clicking with the mouse.
解法
左側の国旗はデンマークだが、ナンバープレートがEU圏ではない。
また、右奥にうっすらアメリカ国旗があります。
ということで、America Denmark townで調べると、Solvang Californiaと出てきました。
次に、cond st.と書かれているが、Google mapを見てみると2nd Stがあるためsecond Stであると予想しました。
後は道を精査したらここが出てきます。
https://www.google.com/maps/place/Solvang,+CA+93463,+USA/@34.5953112,-120.140825,3a,90y,279.43h,89.66t/data=!3m7!1e1!3m5!1sRblApJ--hUrxBvFFMa4qEw!2e0!6shttps:%2F%2Fstreetviewpixels-pa.googleapis.com%2Fv1%2Fthumbnail%3Fcb_client%3Dmaps_sv.tactile%26w%3D900%26h%3D600%26pitch%3D0.34343517044811733%26panoid%3DRblApJ--hUrxBvFFMa4qEw%26yaw%3D279.42647744513164!7i16384!8i8192!4m6!3m5!1s0x80e954a0fc922285:0x2d0e281b060bc156!8m2!3d34.5958201!4d-120.1376481!16zL20vMHI2NDA?entry=ttu&g_ep=EgoyMDI1MDgyNS4wIKXMDSoASAFQAw%3D%3D
今回は下側に横断歩道が見えるので、そこにピンを指せばOKです。
おまけ
LLMを使う場合
Chat GPTを使ってお願いしましょう
Crypto
私の作問は以下の通りです。
- MPKC1
- MPKC2
- Load × Limit × Loot
- Multi ﾊﾟﾜｰ RSA
MPKC1
問題
Simultaneous equations are fascinating:)
from core_lib import make_sample, make_flag, z_vector_from_t, ensure_full_rank, write_public_txt
import random
SEED = 3141592
N = 31
OUT_PATH = "public.txt"
def load_plains_and_flag(path: str):
with open(path, "r", encoding="utf-8") as f:
lines = [ln.rstrip("\n") for ln in f]
items = [ln for ln in lines if ln.strip() != ""]
if len(items) < 2:
raise ValueError("Need at least one sample line and one flag line in plain.txt")
flag = items[-1]
plains = items[:-1]
return plains, flag
def main():
rng = random.Random(SEED)
t_secret = [rng.getrandbits(1) for _ in range(N)]
Z = z_vector_from_t(t_secret)
plains, flag = load_plains_and_flag("plain.txt")
samples = []
for s in plains:
print(s)
samp = make_sample(s.encode("utf-8"), N, rng, Z)
samples.append(samp)
flag = make_flag(flag.encode("utf-8"), N, rng, Z)
write_public_txt(OUT_PATH, N, samples, flag)
print(f"[+] wrote {OUT_PATH} (N={N}, samples={len(samples)})")
if __name__ == "__main__":
main()
解法
先に謝ります。MPKC1,2は自分の実力不足です
元々は、多変数多項式暗号(MPKC)をテーマに出そうと考えていました。
MPKC2で論文実装を出そうと考えていたため、その入門として出題しました。
流れとしては、
- 秘密ビット列
t_secretを作る -
z_vector_from_t関数で秘密パラメータZを作る - plain.txtの平文行
sをmake_sample関数で暗号文に変換して集める - 3と同様の方法にてフラグを変換
といった流れです。
これは単なる線形暗号としてみることができ、かつ平文リストが公開されているので既知平文攻撃ができます。
C = P \oplus (LZ)
より、
P \oplus C = LZ
となり、未知はZのみです。
これはガウスの消去法で解けばOKです。
PATH = "public.txt"
def hex_to_bits(h):
b = bytes.fromhex(h.strip())
out = []
for v in b:
for i in range(8):
out.append((v >> (7 - i)) & 1)
return out
def bits_to_bytes(bits):
pad = (-len(bits)) % 8
bits = bits + [0] * pad
out = bytearray()
for i in range(0, len(bits), 8):
v = 0
for j in range(8):
v = (v << 1) | (bits[i + j] & 1)
out.append(v)
return bytes(out)
def parse_public_file(PATH):
with open(PATH, "r", encoding="utf-8") as f:
lines = [ln.rstrip("\n") for ln in f]
i = 0
n = None
D = None
samples = []
flag = None
def skip(k):
while k < len(lines) and (lines[k].strip() == "" or lines[k].lstrip().startswith("#")):
k += 1
return k
i = skip(i)
while i < len(lines):
ln = lines[i].strip()
if ln.startswith("N="):
n = int(ln.split("=", 1)[1]); i += 1; continue
if ln.startswith("D="):
D = int(ln.split("=", 1)[1]); i += 1; continue
if ln.startswith("SAMPLES="):
i += 1; continue
if ln == "BEGIN SAMPLE":
i += 1; i = skip(i); m = int(lines[i].split("=", 1)[1]); i += 1
i = skip(i); assert lines[i].strip() == "L:"; i += 1
L = []
for _ in range(m):
L.append(lines[i].strip()); i += 1
i = skip(i); P = lines[i].split("=", 1)[1].strip(); i += 1
i = skip(i); C = lines[i].split("=", 1)[1].strip(); i += 1
i = skip(i); assert lines[i].strip() == "END SAMPLE"; i += 1
samples.append({"m": m, "L_hex_rows": L, "P": P, "C": C})
continue
if ln == "BEGIN FLAG":
i += 1; i = skip(i); mf = int(lines[i].split("=", 1)[1]); i += 1
i = skip(i); assert lines[i].strip() == "L:"; i += 1
Lf = []
for _ in range(mf):
Lf.append(lines[i].strip()); i += 1
i = skip(i); Cf = lines[i].split("=", 1)[1].strip(); i += 1
i = skip(i); assert lines[i].strip() == "END FLAG"; i += 1
flag = {"m": mf, "L_hex_rows": Lf, "C": Cf}
continue
i += 1
return {"n": n, "D": D, "samples": samples, "flag": flag}
def solve_linear_system_f2(A, b):
m = len(A)
n = len(A[0]) if m else 0
M = [A[i][:] + [b[i] & 1] for i in range(m)]
rank = 0
piv = []
row = 0
for col in range(n):
pivot = None
for r in range(row, m):
if M[r][col] & 1:
pivot = r
break
if pivot is None:
continue
M[row], M[pivot] = M[pivot], M[row]
piv.append(col)
for r in range(m):
if r != row and (M[r][col] & 1):
for c in range(col, n + 1):
M[r][c] ^= M[row][c]
row += 1
rank += 1
if row == m:
break
for r in range(rank, m):
if all((x & 1) == 0 for x in M[r][:n]) and (M[r][n] & 1) == 1:
raise ValueError("Inconsistent")
x = [0] * n
for i in range(rank - 1, -1, -1):
col = piv[i]
s = M[i][n]
for j in range(col + 1, n):
if M[i][j] & 1:
s ^= x[j] & 1
x[col] = s & 1
return x
def decrypt_flag_from_public(PATH):
pub = parse_public_file(PATH)
D = pub["D"]
A = []
rhs = []
for s in pub["samples"]:
L_rows = [hex_to_bits(h)[:D] for h in s["L_hex_rows"]]
pt_bits = hex_to_bits(s["P"])[:s["m"]]
ct_bits = hex_to_bits(s["C"])[:s["m"]]
y_bits = [(a ^ b) & 1 for a, b in zip(pt_bits, ct_bits)]
A.extend(L_rows)
rhs.extend(y_bits)
Z = solve_linear_system_f2(A, rhs)
Lf = [hex_to_bits(h)[:D] for h in pub["flag"]["L_hex_rows"]]
y_flag = [sum((a & b) & 1 for a, b in zip(row, Z)) & 1 for row in Lf]
c_flag = hex_to_bits(pub["flag"]["C"])[:pub["flag"]["m"]]
p_flag = [(a ^ b) & 1 for a, b in zip(c_flag, y_flag)]
return bits_to_bytes(p_flag).decode("utf-8", errors="ignore")
if __name__ == "__main__":
print(decrypt_flag_from_public(PATH))
fwectf{1_w0k3_up_w1th_th3_1d34!_A3xbkTObddZ7SNLVgLBgy9uW52l0SOnrK8H}
MPKC2
問題
Let’s learn MPKC together. Let’s try to decrypt it by referring to the paper:
https://link.springer.com/chapter/10.1007/3-540-45961-8_39
解法
論文実装問題です。
Ⅱ. THE PROPOSED ASYMMETRIC CRYPTOSYSTEM に記載されているS4を実装したらOKです。
簡単な概要として、
- アフィン変換 $v = T^R(\eta)$
- $v$を分割 $\mu_1(v), \dots, \mu_d(v)$
- $\mu_i(v)$を$L_{(n_i)}$の元$z_i$に変換
- $w_i = z_i^{\bar{h}_i}$を計算
- $w_i$を$K^{n_i}$表現に戻す
- アフィン変換で戻す
といった手順を実装したらOKです。
ここでは、詳しく説明しないので、気になったらぜひ論文を読んでみてください。
from core_lib import setup_secret_general
from Crypto.Util.number import bytes_to_long, long_to_bytes
def _int_to_bits(x, Lbits):
return [int(c) for c in format(x, f'0{Lbits}b')]
def _bits_to_int(bits):
return int(''.join('1' if (b & 1) else '0' for b in bits), 2)
def _mat_inv_K(M, K):
n = len(M)
A = [row[:] + [0]*n for row in M]
for i in range(n):
A[i][n+i] = 1
r = 0
for c in range(n):
piv = None
for i in range(r, n):
if A[i][c] != 0:
piv = i; break
if piv is None:
continue
A[r], A[piv] = A[piv], A[r]
if A[r][c] != 1:
invp = K.inv(A[r][c])
A[r] = [K.mul(x, invp) for x in A[r]]
for i in range(n):
if i == r: continue
if A[i][c] != 0:
f = A[i][c]
A[i] = [K.add(A[i][j], K.mul(f, A[r][j])) for j in range(2*n)]
r += 1
if r < n:
raise ValueError("singular matrix over K")
return [row[n:] for row in A]
def _mat_apply_K(M, v, K):
n = len(M); out = [0]*n
for i in range(n):
s = 0
for j in range(n):
if M[i][j]:
s = K.add(s, K.mul(M[i][j], v[j]))
out[i] = s
return out
def _affine_apply_inv(Mb, y, K):
M, b = Mb
Minv = _mat_inv_K(M, K)
b_inv = _mat_apply_K(Minv, b, K)
x = _mat_apply_K(Minv, y, K)
return [K.add(x[i], b_inv[i]) for i in range(len(y))]
def _split_blocks(v, part):
out=[]; pos=0
for ni in part:
out.append(v[pos:pos+ni]); pos+=ni
return out
def _concat_blocks(chunks):
out=[]; [out.extend(c) for c in chunks]
return out
class _ExtElemDec:
__slots__ = ("K","n","mod","c","mask")
def __init__(self, K, n, mod, coeffs):
self.K = K; self.n = n; self.mod = mod
self.mask = (1<<K.m) - 1
if len(coeffs) != n: raise ValueError("length mismatch")
self.c = [x & self.mask for x in coeffs]
@staticmethod
def one(K, n, mod):
v = [0]*n; v[0] = 1; return _ExtElemDec(K,n,mod,v)
def copy(self): return _ExtElemDec(self.K, self.n, self.mod, self.c[:])
def mul(self, other: "_ExtElemDec") -> "_ExtElemDec":
K=self.K; n=self.n; mod=self.mod
tmp=[0]*(2*n-1)
for i,a in enumerate(self.c):
if a==0: continue
for j,b in enumerate(other.c):
if b==0: continue
tmp[i+j] = K.add(tmp[i+j], K.mul(a,b))
# Y^n = sum_{j=0}^{n-1} mod[j]*Y^j
for d in range(2*n-2, n-1, -1):
coef = tmp[d]
if coef == 0: continue
for j in range(n):
aj = mod[j]
if aj != 0:
tmp[d-n+j] = K.add(tmp[d-n+j], K.mul(coef, aj))
tmp[d] = 0
return _ExtElemDec(K, n, mod, tmp[:n])
def pow(self, e: int) -> "_ExtElemDec":
res = _ExtElemDec.one(self.K, self.n, self.mod)
base = self.copy()
ee = e
while ee:
if ee & 1:
res = res.mul(base)
base = base.mul(base)
ee >>= 1
return res
def _phi_encode(vec, block):
return _ExtElemDec(block.K, block.n, block.modulus, vec)
def _phi_decode(z):
return z.c[:]
def _egcd(a,b):
if b == 0: return (a,1,0)
g,x1,y1 = _egcd(b, a % b)
return (g, y1, x1 - (a//b)*y1)
def _modinv_int(a,m):
g,x,_ = _egcd(a,m)
if g != 1:
raise ValueError("no modular inverse")
return x % m
def _build_h_from_e_list(K, partition, e_list):
q = 1 << K.m
hs = []
for n_i, e_i in zip(partition, e_list):
order = (q ** n_i) - 1
hs.append(_modinv_int(e_i, order))
return hs
def hex_to_ct_elems(hex_str, K):
data = bytes.fromhex(hex_str)
if len(data) < 8:
raise ValueError("hex too short (missing header)")
elem_count = int.from_bytes(data[0:4], "big")
pad_bits = int.from_bytes(data[4:8], "big")
payload = data[8:]
m = K.m
Lbits = elem_count * m
Lbytes = (Lbits + 7)//8
if len(payload) != Lbytes:
if len(payload) < Lbytes:
payload = b"\x00" * (Lbytes - len(payload)) + payload
else:
raise ValueError("payload length mismatch")
payload_int = bytes_to_long(payload)
bits = _int_to_bits(payload_int, Lbits)
ct_elems = []
for i in range(0, Lbits, m):
val = 0
for j in range(m):
val = (val << 1) | bits[i+j]
ct_elems.append(val & ((1<<m)-1))
return ct_elems, pad_bits
def K_elems_to_bytes_general(elems, K, pad_bits):
m = K.m
bits = []
for a in elems:
v = a & ((1<<m)-1)
bits.extend([ (v >> (m-1-j)) & 1 for j in range(m) ])
if pad_bits:
bits = bits[:-pad_bits]
x = _bits_to_int(bits)
Lbytes = (len(bits) + 7)//8
return long_to_bytes(x, blocksize=Lbytes)
def decrypt_secret_algorithm_SA(eta, S):
K = S.K
# t^{-1}
v = _affine_apply_inv(S.t_forward, eta, K)
# per-block inverse powering
w_chunks = []
hs = _build_h_from_e_list(K, S.partition, S.e_list)
chunks = _split_blocks(v, S.partition)
for i, vec in enumerate(chunks):
block = S.blocks[i]
z = _phi_encode(vec, block)
wi = z.pow(hs[i])
ui = _phi_decode(wi)
w_chunks.append(ui)
u = _concat_blocks(w_chunks)
# s^{-1}
return _affine_apply_inv(S.s_forward, u, K)
def decrypt_from_hex_packed(hex_str, S):
ct_elems, pad_bits = hex_to_ct_elems(hex_str, S.K)
if len(ct_elems) % S.n != 0:
raise ValueError("ciphertext length not divisible by n")
rec = []
for i in range(0, len(ct_elems), S.n):
eta = ct_elems[i:i+S.n]
xi = decrypt_secret_algorithm_SA(eta, S)
rec.extend(xi)
return K_elems_to_bytes_general(rec, S.K, pad_bits)
def main():
SEED=20250829
M=8
PARTITION=[7]
BLIST=[3]
MODULI=[[1,1,0,0,0,0,0,1]]
CT_HEX = "000000460000000863306b8beb63d7f7f73160467fca983fcf637c20905e1d7ca653f4a5137d672bb8c40da87994b9cc99ff5981900ae419c270973db9b078ee1a17f5bf79da2dd5aab9bbc6d38b"
S = setup_secret_general(SEED, M, PARTITION, MODULI, b_list=BLIST)
pt = decrypt_from_hex_packed(CT_HEX, S)
print(pt.decode())
if __name__ == "__main__":
main()
fwectf{w31c0m3_t0_tH3_w0rLd_0f_mU1t1v4Ri4t3_p0LyN0m14L_CrYp70Gr4phy!}
Load × Limit × Loot
問題
Let’s pack the knapsack and go on a picnic.
import random
from math import gcd
def superincreasing(n, rng):
seq = []
total = 0
for _ in range(n):
inc = (total + rng.randrange(1<<10, 1<<12)) if total>0 else rng.randrange(1<<10, 1<<12)
nxt = total + inc + 1
seq.append(nxt)
total += nxt
return seq
def bytes_to_bits_be(bb):
bits=[]
for b in bb:
for k in range(8):
bits.append( (b >> (7-k)) & 1 )
return bits
rng = random.Random()
n = 64
w = superincreasing(n, rng)
M = (1<<128) + rng.getrandbits(8)
if M % 2 == 0:
M += 1
a = 0
while True:
a = (rng.getrandbits(127) | 1)
if gcd(a, M) == 1:
break
A = [ (a*wi) % M for wi in w ]
plaintext = b"fwectf{REDACTED_REDACTED_REDACT}"
print(len(plaintext) % 8 )
assert len(plaintext) % 8 == 0
C = []
for i in range(0, len(plaintext), 8):
bits = bytes_to_bits_be(plaintext[i:i+8])
S = sum(ai*xi for ai, xi in zip(A, bits))
C.append(S)
print("")
print(f"P = {A}")
print(f"C = {C}")
解法
ナップザック暗号です。
LLLを使った初心者問題を作りたかったから作りました。そのため、単語の頭文字をとるとLLLになります。
この問題では、公開鍵$A \equiv aw_i \pmod M$と$x_i;x_i \in$ {$0,1$}の乗算し、足し合わせます。
つまり、暗号文$C$は
C = \sum_{i=1}^{64} A_ix_i
といったsubset sum(部分和)で表されます。
さて、ここでナップザック暗号はsubset sumの密度$d < \frac{n}{\log_2 \max{A_i}} < 0.9408\dots$のとき、LLLなどの格子攻撃などが通じます。
今回$n=64, A_i \simeq 128$より、$d = \frac{64}{128} = 0.5$となるため上記の攻撃が使えるでしょう。
from sage.all import *
P = [46370304604399661103510587278608860854, 161470033739550046992102957507284694793, 30543660898063616156789781040944567751, 250664599838920908776562323596516643000, 139374138362514071242477757778171360453, 123592723058786214120596739563194410238, 211661190966175954206312604476025891883, 204127984470558401029942508675826118636, 226485320614749484977835154691419711643, 316359778276308230428825295117172452569, 223595536749391578996034934226276385201, 285194897737688239593933128294126253420, 106767966397120299297689471215328740769, 25599906753022130965000372964020080374, 99461971332517921483061891799425259113, 94027794705920646966871149109862801610, 123296061030051008330943248360079826013, 74854535529342502478954289154224576092, 224885683431821751400008043275824815646, 266096166425088007499970985584050784682, 276003343849704749424463898987980442737, 102681588182470124247526654172102644907, 81066074715052040596846980190467140543, 288564406824785492891304803256068657153, 275777490926285666099408286534129620445, 282517686156702650031304218971561203305, 303283907912734438658673255308488382253, 207124905215590627556917580593810100294, 280558080079068849809690254471376167991, 160954151682440634237745640217189791793, 97767119790212416603441928990664031378, 338144640821518318947395128924719917222, 175619923321070422554784972534849507595, 254564156262627389965162628894875365269, 196177539698888734927195275991945056566, 316218059699388548025737940688917830572, 268400154682066693679616423870021647142, 215171060317966594124409556912523500752, 260057877459608494186977306109025707665, 190102548117865681721849886759598482779, 252725419899497668403547022908880618059, 327335827827878566866970242836185642452, 188260325012018828319115719433455849371, 88483421141682536040965596554472029136, 310248075203863607523992695030757874632, 295640402932812162029270725799625344492, 70276872614365224915426973058582085536, 256094493760578638941104549543294911438, 42841363734929118457515014374580961350, 128080761902152925446804036416229034376, 180236556373329949311891716497015905345, 109842713274004118912686485592449650056, 193653151004110836304303931934828586594, 217480566371177947463788535587066608900, 85737645843034151047932615174569760367, 75130577098367771493769881166880018519, 44108879264846109022147939103515256917, 200510426260508215019844361235980313468, 57239393388118598756306963809052694810, 285120374875743578681171629134755246113, 310860836570193120117077183155691495035, 251862421155813445159906426270135772925, 301796605933628926886822581638474528587, 338556933792869391731776683003533084480]
C = [6431903975558659411995736450941742463678, 6798319334988101743518674132084696585109, 6515613864583459558948036293342639545155, 7773122108332461536899295384273685725884, 7116134977799359563372944976071555756181, 6933621053828258679307411351393495758849]
def density(a):
return RR(len(a)) / RR(Integer(max(a)).nbits())
def bits_to_bytes_be(bits):
assert len(bits) % 8 == 0
out = []
for i in range(0, len(bits), 8):
b = 0
for k in range(8):
b = (b << 1) | int(bits[i+k])
out.append(b)
return bytes(out)
def solve_subset_sum_lll(a, S, max_rows=100, use_bkz=True):
n = len(a)
bitlen = Integer(max(a)).nbits()
for delta in [-2, -1, 0, 1, 2, 3, 4]:
Q = Integer(1) << (bitlen + delta)
B = Matrix(ZZ, n+1, n+1)
for i in range(n):
B[i, i] = 2
B[i, n] = Q * a[i]
for i in range(n):
B[n, i] = 1
B[n, n] = Q * S
R = B.LLL()
for r in range(min(max_rows, R.nrows())):
v = vector(R.row(r))
if v[-1] != 0:
continue
if not all(abs(int(v[i])) == 1 for i in range(n)):
continue
bits = [ (1 - int(v[i])) // 2 for i in range(n) ]
if sum(int(ai)*bi for ai, bi in zip(a, bits)) == S:
return bits
raise RuntimeError("No short vectors found in LLL.")
print(f"density = {density(P):.6f} (< 0.94 OK)")
msg = b""
for j, S in enumerate(C):
bits = solve_subset_sum_lll(P, S)
block = bits_to_bytes_be(bits)
msg += block
print(f"[block {j}] OK ({len(bits)} bits)")
text = msg.decode("utf-8")
print("Recovered:", text)
fwectf{Hey!_This_pr0bl3m_c4n_b3_s0lv3d_w1th_LLL}
Multi ﾊﾟﾜｰ RSA
問題
ﾊﾟﾜｰ is power
from sage.all import *
from Crypto.Util.number import *
import gmpy2
import random
from sympy import nextprime
FLAG = b'fwectf{REDACTED_REDACTED_REDACTED}'
m = bytes_to_long(FLAG)
r = random.randint(5, 30)
p = getPrime(256)
q = getPrime(256)
if p < q:
p, q = q, p
N = pow(p, r) * q
phi = pow(p, r - 1) * (p - 1) * (q - 1)
e = 65537
c = pow(m, e, N)
print(f'c = {c}')
print(f'e = {e}')
print(f'N = {N}')
d1 = getPrime(2000)
d2 = nextprime(d1 + getPrime(1000))
e1 = gmpy2.invert(d1, phi)
e2 = gmpy2.invert(d2, phi)
print(f'e1 = {e1}')
print(f'e2 = {e2}')
こちらは、RSAに関する問題ですが、
N = p^r q
となるmulti power RSAがテーマとなっています。
前から$p, q$を累乗するとどうなるのかなと考えていたのでそれをテーマにしました。
また、今回はこの論文を採用し問題を作成しました。
https://eprint.iacr.org/2015/399.pdf
原理
RSAの鍵関係は通常
ed \equiv 1 \pmod {\phi(N)}
となります。今回与えられている$e_1, e_2, d_1, d_2$に対して等式にすると
\displaylines{e_1d_1 - k_1\phi(N) = 1\\e_2d_2 - k_2\phi(N) = 1}
が成立します。ここで、$\phi(N)$を打ち消しあうために、上の式に$e_2$、下の式に$e_1$をかけて引き算すると
e_1e_2(d_1 - d_2 )\equiv e_2 - e_1 \pmod {\phi(N)}
ここで、$\phi(N)$は$p^{r-1}$を因子にもつので、
e_1e_2(d_1 - d_2 )\equiv e_2 - e_1 \pmod {p^{r-1}}
と法を弱めることができます。
ここで、$x = d_1 - d_2$を根とすると、一次合同式
e_1e_2x - (e_2 - e_1) \equiv 0 \pmod {p^{r-1}}
がでてきます。
このとき、
\displaylines{|x| < N^{\alpha}\\\alpha < \frac{r(r-1)}{(r+1)^2}}
という条件を満たすとき、Lu-Zhang-Linの線形多項式版のCoppersmithで$x$を多項式時間で回収することができます。
最後に、$x$を見つけたら
g = \text{gcd}(e_1e_2x - (e_2 - e_1), N)
を計算し、以下の場合分けをすることで$p$を回収できます。
\displaylines{\text{If} (g = p^{r-1}), \text{then} (p = g^{\frac{1}{r-1}})\\\text{If} (g = p^{r}), \text{then} (p = g^{\frac{1}{r}})\\\text{If} (g = p^{r-1}q), \text{then} (p = \frac{N}{g})}
解法
原理に従って、実装します。Multi power RSAの復号手順として、$p^r, q$を別々で復号し、Hensel liftingで$p$から$p^r$に持ち上げてからCRTで$m$を得るという流れで実装しています。
from sage.all import *
from Crypto.Util.number import *
import gmpy2
def hensel_lifting(m, c, e, p, k):
assert pow(m, e, p) == int(c % p)
mk = int(m % p)
t = int(m * pow(c, -1, p) % p)
pk = int(p)
for _ in range(1, k):
pk *= p
x = int((c - pow(mk, e, pk)) % pk)
y = int((x * t * int(pow(e, -1, p))) % pk)
mk = mk + y
return mk
c = 150585797027649865489287786588283519376444271481829451206461043013638461851456443295639137583076309442211685140040715015672365662062445178352437695738282641956247465007835614325215320828570574978027697247110122408959329602493024795984675855072829968568063483443564884590062240635887431125362354037916695863432044462478632010854829416594987121310115447040797978156754180611417998692235678830822995195693412798239945582015522540243621848514340825137784617038883681762243778481350214509050715611993272169019595988822536735533532328109537622265977681155970778571399007023021359255926523887958105866659589793221135086136634321526143644058657686559455390271432068714110879919249854512706311908215475720874421301327375628026151554425480889625476443996963226739224141229051215116294621373720061550447360540466603611877916643506521674077637662746353412174577577517713229695736915310128634392507257018082205528441763251409689312355800240394928915067047489667210410718244921919018887791400482889355718347742440819608756821762567978878895290820251733297461964155473495597853211579186825851137994290776971434620034797987966563429453923909529541320143776397669267613997300604747811315937419659086723279726826646032780534551617458772078374711989147497752615265133572176138301527850632921359443303144256863024531079818868821758707284519856822245327421770110054277128452078605253184196998977317191651032204260679733274112559665428206212555513334541342029165221468784610288416686450162503789244926494714898635616996486140153083238632042007797793700563323218257129418795358543031202313561185588455593386153322727840291176790523913519542549216392301233455213647649027484109309089206606335520666724332245092640179790951481672640009520232615798668179089441370616468610644268539377884248767999193537928526046999022147158284677984579677312334741055670888654273143019369722889958102904924117413980953194821337321878279459444456391516721152204499246038472658108777670283734288457011883626451484055732662043231790974669769949105126075064121602546376952003206428494498829916276757539596132583838525916520286113969608190165961798389572158151878875500492540747108296198243292566008234833
e = 65537
N = 186468293083788781245499353512563129672312798029703904462936796596026120571080426862373632093518207360391666952453308555988614378903855020162320651304963730462668109416515599034788196838330392323014227902075936472408096760922362616639831532722796773044161215603161573173693396763848532916596270542508246600865336824042340247413113147406841036910189001075097670228541035790259078800598326610948022398352585923649531112759445985740346135428877322273556322542215020775992731058099305658619025609383729517239811673596072211108962991986901295709256060275331345666057130911453857078541419835856196753136664547254360862900351337626911283810534959854452952272035002742600178127259539214115953749657961050280108421405551206427544090699506875821129502984234774688377256310602196702176007042636404063776926466585683290760236194258669323601484216988981113466416405284959939812524546732701485183931884838692814562595191552224757937077488587067020793692692549938889591330072594717978441992795102999379303433207854356430437846345643266409739062915660544094498466397963646286252575273661019638807620280311533417717322466737567313846948246565804965079064097678541329903335139345823245801485851723772625368820657081414997271906611200756811167771754039199663511386284954358869993716532869728924931127279616476581118702229755968849120582675066084548348641091550633395996908836876499056736123107365637770245726218450365257927541692911169875941639963606762719472741281838412109552457222110661735681401203267804449363273688233013042050750830535778904458171623334164553955827238989238553731488016772701812203067882783550639709170454593937643386446256536119770989304864520889045556071269357480411824619830061505470986036143575914439137724990710287384145813135368196679314377112131761811940172598300544938844479133061210634426452190259178180635554381170513818865646521472300868854934387822644776013828828533387245770709879233807065640965155395836324727727247566385145338896343366468455003789992017616034872629717115885307603763663604867417148970196011250152501225642510419108907592141672752218085088428240372007994449852792767351434018043118658591114512322934390623465185608109909287
e1 = 41580201693720582480693330964943873953272761954440070167783695980849492986662882513949168242004211132670119356752908751569637864785219861514846064298150109789186060860480552700920272463488413243406347872787482976412247245447832054401920594283666788061207365372191406054243898945396093580724391257502862264542139892002113479274778815312220710067519175895385029728136011707878570503892737327311559220318356052978117942035853947664507847769494960999568852350903791440660149716513527902855811711244727464905711093905648316805999328017344077741109433923704200400909675649273690871091313094751105766025879326677544581537926603326267474079786157380975934855898690386484742475696802305967739089815897725317069013189207569982900053713459672998534905787251877552189174587775147542089885096510488094105071666800247101089674649502031584763839755525727965498486527987626650988652717016765563711049277022756500157982361607140778095658226557996921026130637701014127285732701887164908135560640420831336153612762215604492226275755304784484586433397754740117463505077153516054839486722481181167234229522839072562070104349846627036424367454820389259772812583287412268551592814838917235531904330269843311050451607079925393154706621947637894340627920099890436967089957279051662270031234850834868788996666439029630296451502714368722270484850158064364294201493953114172135159291698520360808866584806672889034144771436797735399804868018466668980453787245180038654345402748074831992415906097556738039279373205673388915847115097595687636844845281031267671590617631079664730977219356874731914430598632093802245785346918434058687175986926298508052091652105059279150133460800817344425839682126964963172665944796661520065067011564066759081570107543463219913557175490516674841445611024874076012796831045476624324336824144536686982822389532337716389606704464995869146017139606884400942152132650479156746875064775899199421858957623079678439410930007225084885887507916565931484847922437795803010981718194290457886234411319205609157105187496215942426263799468200530172714083518151428613800222887516185125589229285415586754359693123597271154802410446280090888946329676448819766565178085178413
e2 = 85039848098040198629810228227981333547571544556783337097791600722534400132636079696903303346248897364881224585886454806975154545966948446220731675563154086955028649334868794080881245005339585924134379510941267320612901825195331762039504494208113074000658589388417531708151776552001429290730079651850438354450134417941536114627588684047285304149442482520534706112915132300363334355877266504867840336875699380810203774027956821177301695145239460742602239474808009495484157876332743288399678455954261820744636650959513617108267284843582028632761292881550278978932484825724119492458352905716592760686190086451077741620824644825883637432247606542138083779285819850363414635029032877436967954280148470447811352539940377678100502742624065767900310440814168233290500834855710005707058159197563629326782049935503972263918251175766238816831480903704391181267515124468008074136167514887505816881460820657424954418139484799844694782547580350564364558817948882864222013820625021944986053685725745314774681293740590727701113298280323591219898133230776271582267346789673381184226867314871136250586292185846670779312885676712427749758340163573785341699633900956786017292343325059891658652266756606090187161788473402586895334792711643881433133624951181775727523533052371714916897497811035395454066372050989114435626744825554699077429987277061832895800546415012022003883511707438045038605628208211909421854504776635296074426208716798470239164727186799413913395180313824277747343105859814610954674052243548895700598370536537947368616622939415516698306638823827111837566750309493160547631614984324373110960297446703268022461052398627980535338158153120866719678508677569334532530529647580833323049593479237592627920937370843841953419429014918761884065528591917331618164304459336833062437365299224341702429186447625010865403846061689858277518844804864401686840751180716835568865211637737929233885813901317995949748419432175395134689356497511677848916131101942879850703634693483037253067856351005939346103168898195695634993164654145535921173796299479632825317904540020964320393080050237770370124344704355059640345255127574387631628640364876804621760107827456260120265498390309061
r = 5
for i in range(5, 30):
print(f"[*] Trying r = {i}")
R = Zmod(N)
e1_mod = R(e1)
e2_mod = R(e2)
x = polygen(R)
f = e1_mod * e2_mod * x - (e2_mod - e1_mod)
f = f.monic()
roots = f.small_roots(beta=((i - 1) / (i + 1) - 0.005), epsilon=0.1)
if not roots:
continue
res = gmpy2.iroot(gmpy2.gcd(int(f(roots[0])), N), i - 1)
if not res[1]:
continue
p_guess = res[0]
q_guess = N // (p_guess ** i)
if q_guess != 0:
r = i
p = p_guess
break
if not roots or not res[1]:
print("[-] No valid r found in the range.")
exit()
q = N // (p ** r)
phi_recovered = (p ** (r - 1)) * (p - 1) * (q - 1)
d_recovered = gmpy2.invert(e, phi_recovered)
dp = pow(e, -1, (p ** r - p ** (r - 1)))
dq = pow(e, -1, q - 1)
mp = pow(c, dp, p ** r)
mq = pow(c, dq, q)
mpr = hensel_lifting(mp, c, e, p, r)
m = crt([mpr, mq], [p ** r, q])
print(f'[+] Decrypted message: {long_to_bytes(m).decode()}')
fwectf{9PWRr_R54_90w3r3d_Bu7_N07_53cur3}
他の解法
Discordにてchocoruskさんが以下を説明していました。
I don't need e2 ...
If r is small, my solver don't work.
e1*d1-1=0 mod b, where b=p^(r-1), b >= N^beta, beta=(r-1)/(r+1).
If d1 (2000bits) is sufficiently smaller than N^(beta^2) (i.e., 2000<<256(r-1)^2/(r+1)), we can solve using small_roots.
https://doc.sagemath.org/html/en/reference/polynomial_rings/sage/rings/polynomial/polynomial_modn_dense_ntl.html#sage.rings.polynomial.polynomial_modn_dense_ntl.small_roots
Since N=p^r*q, r is close to N.bit_length()/256-1.
完全に勉強不足でした。
$N$が未知の因子$b \geq N^{\beta}$ならsmall_rootで探せるという意味になります。
また、引数にあるXをNoneにすると自動的に
X \approx ceil(1/2 N^{\beta^2/\delta-\epsilon})
となります。今回は、一次$f(x) = e_1x-1$より$\delta=1$なので成功にはだいたい
|d_1| < N^{\beta^2}
と考えることができます。また、$\beta$は$\beta = (r-1)/(r+1)$と考えることができるので、もし$r$が大きい場合は上記が満たされます。以上のときに$e_2$を用いなくても復号することができます。
おわりに
改めて、Writeup遅くなりました。まじごめんなさい。
Cryptoの勉強をしっかり始めてまだ半年くらいで作問しましたが色々な経験をすることができました。
FWECTFの運営メンバーと解いてくれた皆様、ありがとうございました！
また、某魔女にCryptoは簡単といわれてしまったので来年以降は難しいといえるような問題を作りつつ、より勉強になる問題を作れたらと思います！