Daily AlpacaHack Week5 (2025-12-29 ~ 2026-1-4)

Daily AlpacaHack の Writeup.
(2025/12/29 - 2026/1/4)

後から解いたものなど含むまとめ.

one-p-rsa (Crypto, 2025/12/29)

• 一つの素数を用いた RSA 暗号
• 暗号鍵について $p-1$ の逆元を $d$ とすると以下が成立する ($k$ は整数)

$$ed = k(p-1) + 1$$

• 暗号文 $c$ について $d$ 乗すると以下となる

$$c^d = (m^e)^d = m^{ed} = m^{k(p-1)+1}$$

• フェルマーの小定理より以下が成立

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

• よって $d$ が復号鍵となっていることが分かる

$$m^{k(p-1)} m \equiv m \mod p$$

• python で解読しフラグ獲得

from Crypto.Util.number import *

with open("chall.txt", "r") as f:
    p, e, ct = [int(x.split()[-1].strip()) for x in f.readlines()]
    
d = inverse(e, p-1)
m = pow(ct, d, p)

print(m)
flag = long_to_bytes(m)
print(flag)
        

RBG (Crypto, 2025/12/30)

• 難しくて自分では解けず Writeup を参照した (参考元)

• 以下で自分で解釈して解いた道筋を記述する

• 今回は線形合同法 (Linear congruential generator, LCG) を用いて暗号鍵 $e$ が複数生成されている

• 線形合同法の式が提供されたコードに存在

• 複数の暗号の逆元の計算から切片の部分 (1337) が算出できることが推測される

• 暗号鍵の漸化式は以下となる

$$e_{l+1} = 3e_l + 1337 + k_l N$$

• $l, l+1$ 番目の暗号を用いて切片の部分と $N$ の部分を取り出す

$$m_{l+1}(m_l^3)^-1 \equiv m^{1337+k_l N} \mod N$$

• ここで $k_l$ は $0$ から $3$ までのどれかである

• $1337$ と $N$ の関係について拡張ユークリッドの互除法で以下を算出する

$$1337a + Nb = 1$$

• $k_l=0, 1$ の場合の数字を取り出すことができた場合, $m^{1337} = A, m^{1337-N} = B$ とした時に以下が成立

$$A^{a+b} B^{-b} \equiv m^{1337(a+b)-1337b+bN} \equiv m^{1337a + bN} \equiv m \mod N$$

• よって $k_l=0, 1$ の場合の数字を取り出すことができればフラグ獲得となる
• 今回は 13 回分の暗号文があるため各回における $m_{l+1}(m_l^3)^{-1}$ を算出したところ 3 種類の数が取得できた
• $k_l=3$ となるには $e > N-445$ という条件を満たす必要があり, 素数が十分大きければ $k_l=3$ となる可能性は非常に少ないため, 取得できた 3 種類は $k_l=0,1,2$ のどれかであると考えられる
• 総当たりで試してフラグ獲得

from Crypto.Util.number import *
import gmpy2
import itertools

with open("./output.txt", "r") as f:
    out_lines = f.readlines()
    N = int(out_lines[0].split()[-1].strip())
    outs = [int(x.strip()) for x in out_lines[1::]]
    
m1337knN_list = []
for i in range(1,13):
    m1337knN_list.append(outs[i] * inverse(pow(outs[i-1], 3, N), N) % N)
    
kn_list = list(set(m1337knN_list))

g, x, y = gmpy2.gcdext(1337, N)

if g != 1:
    print("not coprime:", g)
    exit()
    
for p in itertools.permutations(range(3)):
    tmp_m = pow(kn_list[p[0]], x+y, N) * pow(kn_list[p[1]], -y, N) % N
    print(long_to_bytes(tmp_m))
        

108 (Misc, 2025/12/31)

• フラグは Cookie に存在した

Happy New Year (Misc, 2026/1/1)

• "Alpaca" Hack という名前をそのまま小文字でフラグにする

super-tomato (Crypto, 2026/1/2)

• 別々の素数 $a, p$ について $a^k \equiv 1 \mod p$ となる $k$ を与えればフラグ獲得
• フェルマーの小定理より $k = p - 1$ で条件を満たす

from pwn import *

_, host, port = "nc 34.170.146.252 35506".split()
sh = remote(host, port)

prompt = sh.recvuntil("here is my 🍅:".encode())
print(prompt.decode())

p = int(sh.recvline().decode().strip())

d = p - 1

prompt = sh.recvuntil("what is your 🍅>".encode())
print(prompt.decode())

sh.sendline(str(d).encode())

sh.interactive()
        

Ruby Flag Checker (Rev, 2026/1/3)

• Ruby で作られたフラグチェッカーが渡される
• Prime::Generator23 という関数で作られた数列とフラグを XOR 演算し, 出力を比較している
• ドキュメント を調べたところ 2 と 3 で割り切れない数字を小さい順に並べる関数らしいので, 同様のものを実装し python でデコード

def primes(n):
    res = [2, 3]
    x = 3
    while len(res) < n:
        x += 1
        if x % 2 != 0 and x % 3 != 0:
            res.append(x)
    return res

prime23 = primes(23)

enced = b"Coufhlj@bixm|UF\\JCjP^P<"

plain = bytes(p ^ c for p, c in zip(prime23, enced)).decode("ascii")
print(plain)
        

Fushigi Crawler (Web, 2026/1/4)

• コードを読んだところクローラーのアプリケーションらしい
• リクエストヘッダーにフラグを持った状態で指定した URL にアクセスするらしいので, webhook.site で作った URL にリクエストを飛ばすことでヘッダーにあるフラグを確認・取得できた

import requests
import json

url = "http://34.170.146.252:38098/api/crawl-request"
data = json.dumps({"url": "$URL"}) # https://webhook.site/
headers = {"Content-Type": "application/json"}
res = requests.post(url, data=data, headers=headers)