Substance

❯ ls -la
total 20
drwxr-xr-x 2 nabeen nabeen 4096 Feb 10 22:36 .
drwxr-xr-x 4 nabeen nabeen 4096 Feb 10 22:33 ..
-rw-r--r-- 1 nabeen nabeen  253 Jan 31 23:05 chal.py
-rw-r--r-- 1 nabeen nabeen  158 Jan 31 23:05 output.txt

import os
from random import randint

flag = int.from_bytes(os.getenv("FLAG", "Alpaca{REDACTED}").encode(), "big")
print(flag * randint(2, 2026) * randint(2, 2026) * randint(2, 2026))
print(flag * randint(2, 2026) * randint(2, 2026) * randint(2, 2026))

70430356624056699219964353455091734195306937238245707901514922333654568000660
5585179348150525015655680494025565656820428601640301759505137819334580532521858

import math

# 出力ファイルから2行の数値を読み込む
c1, c2 = map(int, open("output.txt").read().split())
print(f"c1 {c1}")
print(f"c2 {c2}")

# 共有因子（flagを含む）を取り出す
g = math.gcd(c1, c2)
print(f"g {g}")

# g = flag だった場合はそこで終了
if g.to_bytes((g.bit_length() + 7) // 8, "big").decode("utf-8", errors="ignore").startswith("Alpaca{"):
    print(g.to_bytes((g.bit_length() + 7) // 8, "big").decode("utf-8", errors="ignore"))
    raise SystemExit

# g に含まれる小素因数（<=2026）を収集
factors = {}
n = g
p = 2
while p <= 2026:
    while n % p == 0:
        factors[p] = factors.get(p, 0) + 1
        n //= p
    p += 1
print(f"小素因数の個数 {sum(factors.values())}")

# 小素因数の約数を列挙（kの候補）
divs = [1]
for p, e in factors.items():
    divs = [d * (p ** k) for d in divs for k in range(e + 1)]
divs = [d for d in divs if d <= 2026 ** 3]
print(f"約数の数 {len(divs)}")

# 各候補で復号してフラグを探す
for d in divs:
    if (g // d).to_bytes(((g // d).bit_length() + 7) // 8, "big").decode("utf-8", errors="ignore").startswith("Alpaca{"):
        print((g // d).to_bytes(((g // d).bit_length() + 7) // 8, "big").decode("utf-8", errors="ignore"))
        break
else:
    # 見つからなければ通知
    print("見つかりませんでした")