2026-02-21

Daily AlpacaHack B-SIDE 2/17-20 ECRSA writeup

AlpacaHackというプラットフォームでは毎日1問CTFの問題が出題されるDaily AlpacaHackという取り組みが行われています。このDaily AlpacaHackではCTFに初めて触れる初心者〜向けの問題が提供されていますが、2026年2月からはDaily AlpacaHack B-SIDEとして、腕試し問題が提供されるようになりました。

私が作問したECRSAという問題もこのB-SIDEの問題として2/17 - 20の4日間提供されていました。今見たところピックアップ期間中は40 solves、期間終了後に1 solveしていただいていました。取り組んでもらった皆様、ありがとうございます。この記事では作問者writeupとして、想定解法を説明します。

問題は次のとおりです。

import os

# secp521r1 patemeter
p = 0x01ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff
K = GF(p)
a = K(0x01fffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffc)
b = K(0x0051953eb9618e1c9a1f929a21a0b68540eea2da725b99b315f3b8b489918ef109e156193951ec7e937b1652c0bd3bb1bf073573df883d2c34f1ef451fd46b503f00)
EC = EllipticCurve(K, (a, b))

while True:
    Q = EC.random_point()
    q = int(Q.xy()[0])
    R = 2*Q
    r = int(R.xy()[0])
    if is_prime(q) and is_prime(r):
        break

n = q*r
e = 65537
m = int.from_bytes(os.environ.get("FLAG", "Alpaca{dummy}").encode(), "big")
assert m < n
c = pow(m, e, n)

print("n = {}".format(n))
print("e = {}".format(e))
print("c = {}".format(c))

secp521r1という楕円曲線上のランダムな点 $Q$ および、その2倍点 $R$ について、それぞれのx座標 $q, r$ が素数であるとき、 $n=qr, e=65537$ のRSA暗号でフラグが暗号化されています。何らかの方法でこのRSA暗号を解読し、暗号文から平文を復元できればフラグが得られます。問題名の通り、EC (Elliptic Curve = 楕円曲線)とRSA暗号を組み合わせた問題です。

フラグはRSA暗号で暗号化されているので、まずRSA暗号について考えます。RSA暗号の破り方は前提条件によって様々なものが知られていますが、この問題では $n$ の構成がランダムな素数ではなく、特別な条件をもつ素数 $q, r$ を用いて行われているので、 $n$ を素因数分解することで、RSA暗号において秘匿すべきパラメータである $n$ の素因数 $q, r$ を復元し、復号鍵 $d$ を計算することで $flag = c^d \mod n$ とフラグを求めることになりそうです。

では $n$ を素因数分解する方法について考えます。先述の通り、 $n$ は特別な関係をもつ2つの素数 $q, r$ の積なので、この2素数の関係を利用して $q, r$ を求められそうです。その関係とは、 $r$ は $q$ をx座標とする点の2倍の位置の点のx座標ですから、楕円曲線の2倍公式でその関係が表せます。

曲線 $y^2 \equiv x^3 + ax + b \mod p$ 上の点 $(x_1, y_1)$ の2倍点 $(x_2, y_2)$ を求める式

$x_2 \equiv \lambda^2 - x_1 - x_1 \mod p$
$y_2 \equiv \lambda(x_2 - x_1) + y_1 \mod p$
ただし $\lambda \equiv \frac{3x_1^2 + a}{2y_1} \mod p$

この式に $q, r$ を当てはめると $r \equiv \lambda^2 - q - q \equiv \left( \frac{3q^2 + a}{2q_y} \right) ^2 - 2q \equiv \frac{9q^4 + 6aq + a^2}{4q_y^2} - 2q \mod p$ です。

点 $Q$ のy座標は未知の値で、ここまで登場していませんでしたが便宜上 $q_y$ と表しました。楕円曲線上の点は $y^2 \equiv x^3 + ax + b \mod p$ という関係を持ちますから、先程の式の $q_y^2$ にこれを代入して $r \equiv \frac{9q^4 + 6aq^2 + a^2}{4(q^3 + aq + b)} - 2q \equiv \frac{(9q^4 + 6aq^2 + a^2) - (8q^4 + 8aq^2 + 8bq)}{4(q^3 + aq + b)} \equiv \frac{q^4 - 2aq^2 - 8bq + a^2}{4(q^3 + aq + b)} \mod p$ です*1。これで $r$ を $q$ を使って表せました。

$n$ を改めて記述し直すと $n \equiv qr \equiv q\frac{q^4 - 2aq^2 - 8bq + a^2}{4(q^3 + aq + b)} \mod p$ であり、式変形して $n*4(q^3 + aq + b) - q(q^4 - 2aq^2 - 8bq + a^2) \equiv 0 \mod p$ です。この多項式の未知変数は $q$ のみなので、簡単に根を求めることができます。 $q$ が求まれば $r = \frac{n}{q}$ などとして $r$ も求められ、 $n$ が素因数分解できるので、この問題を解くことができます。

これまでの流れをSageMathのスクリプトに落とし込むと、次のようになります。

p = 0x01ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff
K = GF(p)
a = K(0x01fffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffc)
b = K(0x0051953eb9618e1c9a1f929a21a0b68540eea2da725b99b315f3b8b489918ef109e156193951ec7e937b1652c0bd3bb1bf073573df883d2c34f1ef451fd46b503f00)
EC = EllipticCurve(K, (a, b))

f = open("./output.txt")
n = int(f.readline().split(" = ")[1].strip())
e = int(f.readline().split(" = ")[1].strip())
c = int(f.readline().split(" = ")[1].strip())


PR.<x> = PolynomialRing(GF(p))
# rx = (x^4 - 2*a*x^2 - 8*b*x + a^2)/(4*x^3 + 4*a*x + 4*b)
# n = x * rx

f = n*(4*x^3 + 4*a*x + 4*b) - (x^4 - 2*a*x^2 - 8*b*x + a^2)*x
for root in f.roots():
    q = int(root[0])
    if n % q == 0:
        r = n // q
        d = pow(e, -1, (q-1)*(r-1))
        m = pow(c, d, n)
        print(bytes.fromhex(hex(m)[2:]))
        quit()

今回の問題は、RSA暗号における $n$ の素因数について、 $n=qr$ に加えてその2数が楕円曲線の2倍公式においても関係を持っているので2式2変数の連立方程式を解くことでその値を求められる、という問題でした。

RSA、楕円曲線における基礎的な知識とSageMathに式を解かせる知識があれば簡単に解ける問題として、そもそもはDaily AlpacaHack開始くらいのタイミングでmediumくらいの難易度でどうか、と提案したものが「これはVery Hardですね」と断罪されて出題できず、B面が新設されたことで出題してもらえるようになったものでした。知識があれば簡単ではあるものの、その知識をCTF初心者の頃はまったく知らなかったり、見たことがあっても問題に還元できなかったということを忘れていましたね……。

とはいえこのように頭を捻らないと解けない問題ではなく、知識を以てすれば赤子の手を捻って解けるような問題ですので、Very Hardのような難易度設定に臆せず取り組んでもらえたら嬉しいです。

*1:当然こんな計算を手でする必要はなく、前提となる条件の式をSageMathやWolframなどに突っ込めばよいです

2025-12-30

2025年に読み始めて面白かったWeb小説

kotatsugameリスペクトです。もはや何をリスペクトしていたのか忘れているんですが、多分kotatsugameさんが週記やtwitterで面白い作品を次々とシェアされている様子に感銘を受けて、一年に一度くらいやるか、と思って書き始めたのが最初なのではないか。

というわけで過去記事もあります。

2025年はあまりWeb小説読んでない。代わりにBaldur's Gate 3とELDENRING NIGHTREIGNをよくやっていました。あと以前から読んでるやつで引き続きめっちゃ面白いやつとか展開がいい感じのやつとかも紹介したいけどレギュレーション違反になるので以前のエントリも読んでください。

「パン工場の手伝いをしている錠前サオリだ」【完結】 - ハーメルン
芸術的で文化的な異世界生活を目指して - ハーメルン
- とても好き
このまま僕らは大人になれないまま - ハーメルン
魔術師クノンは見えている
- 漫画の1巻を読んで面白かったので全部読んだ。漫画も全部買った。好きな世界と好きな登場人物たちです
九つの塔。救世の勇者。おまけに悪役面おじさん。 - ハーメルン
異世界転生周回プレイもの - ハーメルン
- これもかなり好き
ダブルスチール【完結】 - ハーメルン
- よくできてた。満足感のある作品
魔法使い♯ちゃんの世界最適化計画 - ハーメルン
- めっちゃ面白い。更新を楽しみにしています
塵埃の魔法少女【完結】 - ハーメルン
墜星は暗路を行く - ハーメルン
俺の切り札は光らない - ハーメルン
わたしはあなたの耳鳴り（田村らさ） - カクヨム
- 2025年で一番面白かった。もっと読まれるべきだと思うのでみんな読みに行ってください
男娼マエストロと栄光の少女たち - ハーメルン
- 2024年から読んでるはずだが去年の一覧になかったので。最近また更新があってうれしい
【完結】うお……貞操逆転世界魔法少女物はちょっと盛りすぎ…… - ハーメルン
異世界転生ダンジョンマスター　温泉ダンジョンを作る
晴嵐 - ハーメルン
- この人のバンドリの二次創作作品をずっと読んでる。はやく原作を履修するべきだが、二次創作だけでかなり満足できている

2025-07-27

SECCON Beginners CTF 2025 writeup

SECCON Beginners CTF 2025のCrypto問題のwriteupです。

seesaw
01-Translator
elliptic4b
Golden Ticket
mathmyth

seesaw

import os
from Crypto.Util.number import getPrime

FLAG = os.getenv("FLAG", "ctf4b{dummy_flag}").encode()
m = int.from_bytes(FLAG, 'big')

p = getPrime(512)   
q = getPrime(16)
n = p * q
e = 65537
c = pow(m, e, n)

print(f"{n = }")
print(f"{c = }")

qが16bit程度しかないので素因数分解できます。↓のscriptではlimit書いてるけどいらないと思う

f = open("output.txt")

n = int(f.readline().strip().split(" = ")[1])
c = int(f.readline().strip().split(" = ")[1])

((p, _), (q, _)) = factor(n, limit=2**17)
d = pow(65537, -1, (p-1)*(q-1))
m = pow(c, d, n)

print(bytes.fromhex(hex(m)[2:]))

01-Translator

import os
from Crypto.Cipher import AES
from Crypto.Util.Padding import pad
from Crypto.Util.number import bytes_to_long


def encrypt(plaintext, key):
    cipher = AES.new(key, AES.MODE_ECB)
    return cipher.encrypt(pad(plaintext.encode(), 16))

flag = os.environ.get("FLAG", "CTF{dummy_flag}")
flag_bin = f"{bytes_to_long(flag.encode()):b}"
trans_0 = input("translations for 0> ")
trans_1 = input("translations for 1> ")
flag_translated = flag_bin.translate(str.maketrans({"0": trans_0, "1": trans_1}))
key = os.urandom(16)
print("ct:", encrypt(flag_translated, key).hex())

フラグがサーバ側でバイナリ文字列に変換されたあと、更にユーザの入力に応じて0 1 をそれぞれ好きな文字列に置換できます。その後置換後の文字列をAESのECBモードで暗号化されたものが渡されます。

ECBモードをみると、同じ平文ブロックを暗号化すると同じ暗号文になるという性質を思い出すので、これを利用したくなります。具体的には0, 1 をそれぞれ適当な1ブロックに置換すると、暗号文全体は0 を暗号化したブロックと1を暗号化したブロックからなり、その2種類だけ*1となるので平文を復元できます。

from ptrlib import Socket, chunks


# sock = Socket("nc localhost 9999")
sock = Socket("nc 01-translator.challenges.beginners.seccon.jp 9999")

sock.sendlineafter("0> ", "0" * 16)
sock.sendlineafter("1> ", "1" * 16)

ct = sock.recvlineafter("ct:").decode().strip()
cs = chunks(ct, 32)

flag = 0
for c in cs[:-1]:  # last block is padding
    if c == cs[0]:
        flag = flag*2 + 1
    else:
        flag = flag*2
print(bin(flag))
print(bytes.fromhex(hex(flag)[2:]))

elliptic4b

import os
import secrets
from fastecdsa.curve import secp256k1
from fastecdsa.point import Point

flag = os.environ.get("FLAG", "CTF{dummy_flag}")
y = secrets.randbelow(secp256k1.p)
print(f"{y = }")
x = int(input("x = "))
if not secp256k1.is_point_on_curve((x, y)):
    print("// Not on curve!")
    exit(1)
a = int(input("a = "))
P = Point(x, y, secp256k1)
Q = a * P
if a < 0:
    print("// a must be non-negative!")
    exit(1)
if P.x != Q.x:
    print("// x-coordinates do not match!")
    exit(1)
if P.y == Q.y:
    print("// P and Q are the same point!")
    exit(1)
print("flag =", flag)

ランダムな $y$ が渡されて、 $P = (x, y)$ がsecp256k1 上の点になるように $x$ を渡した後、 $Q = aP$ が $P$ と異なる $x$ 座標を持ち、 $P$ と同じ $y$ 座標をもつように $a$ をうまく選べれば勝ち、となります。

まず $y$ 座標から $x$ 座標を求める必要がありますが、これは楕円曲線の式 $y^2 \equiv x^3 + ax + b \mod p$ を満たすように式に $a, b, y$ を代入して $x$ を求めればよいです。

続いていい $a$ を求めます。まずそもそも同一の楕円曲線上にy座標が同じでx座標が異なる2つの点が存在するのか、という話ですが、存在します。平面座標上での楕円曲線の形を思い出すと $P$ と $-P$ がまさにそういう点ですね。もはや常識。

ということは $a = -1$ とすれば良さそうですが、入力の制約により $a$ はnon negativeな値である必要があるのでかわりに $-1 \pmod{\#E}$ を利用します（ $\#E$ は楕円曲線 $E$ の位数）

from ptrlib import Socket

p = 0xfffffffffffffffffffffffffffffffffffffffffffffffffffffffefffffc2f
K = GF(p)
a = K(0x0000000000000000000000000000000000000000000000000000000000000000)
b = K(0x0000000000000000000000000000000000000000000000000000000000000007)
E = EllipticCurve(K, (a, b))
G = E(0x79be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798, 0x483ada7726a3c4655da4fbfc0e1108a8fd17b448a68554199c47d08ffb10d4b8)
E.set_order(0xfffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd0364141 * 0x1)

PR.<x> = PolynomialRing(K)

while True:
    # sock = Socket("nc localhost 9999")
    sock = Socket("nc elliptic4b.challenges.beginners.seccon.jp 9999")
    y = int(sock.recvlineafter("y = "))
    f = y**2 - (x**3 + a*x + b)
    roots = f.roots() 
    if len(roots) != 0:
        break

x = roots[0][0]
G1 = E((x, y))

inv = Zmod(E.order())(-1)
G2 = inv *G1
assert G1[0] == G2[0]

sock.sendlineafter("x = ", str(x))
sock.sendlineafter("a = ", str(inv))
sock.interactive()

Golden Ticket

問題のスクリプトはやや長いので省略。encryption ticketを利用するとEnc(key, iv, input || pad) がえられるオラクルが利用でき、decryption ticketを利用するとDec(key, iv, input || pad)が得られるオラクルが利用できます。Enc, Dec AES-CBCによる暗号化・復号で、どちらもinput は16バイト（1ブロック）までで、それぞれ3回まで利用できます。

目的は 6ブロックのランダムな文字列 challenge に対して、Dec(key, iv', payload) == challenge となるような iv', payload を求めることです。

まずはivを求めます。ここで2回オラクルを使う方法を考えていて時間を溶かしていたけど、input == padとなるようにinputを決めて（つまり input = 0x10101010...10）decryption ticketを利用すると、1ブロック目は 0x1010...10 をAESで復号したものにIVをXORした値、2ブロック目は 0x1010...10 をAESで復号したものに1ブロック目の平文、0x1010...10 をXORした値、となります。

ここからは $Enc, Dec$ はAESによる1ブロックのみの暗号化を表すことにすると、1ブロック目は $Dec(0x1010...10) \oplus IV$ 、2ブロック目は $Dec(0x1010...10) \oplus 0x1010...10$ となります。2ブロック目の結果から $Dec(0x1010...10)$ がわかるので、1ブロック目の結果にXORすると $IV$ が手に入ります。

$IV$ がわかったので、これを利用してencryption ticketやdecryption ticketを利用すると何ができるかを考えます。encryption ticketを利用するとCBCモードの復号における前ブロックの暗号文 $c_{i - 1}$ が決まっているとき、そのブロックの復号結果を望む値 $t_{i}$ にするような暗号文のブロック $c_{i}$ を求めることができます。

また、decryption ticketを利用すると、CBCモードのそのブロックの暗号文 $c_{i}$ が決まっているとき、そのブロックの復号結果を望む値 $t_{i}$ にするような前の暗号文のブロック $c_{i}$ を求めることができます。

あとはこのパーツを組み合わせて6ブロックを作ればよいです。ここはencryptioin oracleとdecryption oracleの並べ方……みたいな話題はあるのですが、考えるときは↓みたいな図を書いてDec→DecとかEnc→Encという並べ方が良さそう、みたいなことを考えるものの、説明のときはスクリプトを見るのが早そうなのでそれを貼るだけにします

△を決めると▲が求められるという順番なので、▲が重複してはいけない……のように考えていた図

from ptrlib import Socket, chunks, xor

# sock = Socket("nc localhost 9999")
sock = Socket("nc golden-ticket.challenges.beginners.seccon.jp 9999")

def get_challenge():
    sock.sendlineafter("> ", "3")
    chal = bytes.fromhex(sock.recvlineafter("challenge:").decode().strip())
    sock.sendlineafter("answer> ", "00")
    return chunks(chal, 16)

def enc_oracle(payload: bytes):
    sock.sendlineafter("> ", "1")
    sock.sendlineafter("pt> ", payload.hex())
    pt = bytes.fromhex(sock.recvlineafter("ct: ").decode().strip())
    return chunks(pt, 16)


def dec_oracle(payload: bytes):
    sock.sendlineafter("> ", "2")
    sock.sendlineafter("ct> ", payload.hex())
    pt = bytes.fromhex(sock.recvlineafter("pt: ").decode().strip())
    return chunks(pt, 16)


# find IV
dec16_iv, dec16_16 = dec_oracle(bytes([16] * 16))
dec16 = xor(dec16_16, bytes([16] * 16))
iv = xor(dec16_iv, dec16)
print(f"iv={iv.hex()}")

# define utilities which use IV
def find_c_from_prev_c(prev_c: bytes, t: bytes):
    """
    find c_{i} from c_{i-1} and t_{i}
    which satisfies Dec(c_{i}) ^ c_{i-1} = t_{i}
    use 1 encryption ticket
    """
    x, _ = enc_oracle(xor(xor(prev_c, t), iv))
    return x

def find_prev_c_from_c(c: bytes, t: bytes):
    """
    find c_{i-1} from c_{i} and t_{i}
    which satisfies Dec(c_{i}) ^ c_{i-1} = t_{i}
    using 1 decryption ticket
    """
    x, _ = dec_oracle(c)
    return xor(xor(x, iv), t)



# get challenge
T_1, T_2, T_3, T_4, T_5, T_6 = get_challenge()

# we fix C_3 = 0x1010...10 and C_2 = Dec(0x1010...10) ^ T_3
C_3 = bytes([16] * 16)
C_2 = xor(dec16, T_3)
C_1 = find_prev_c_from_c(C_2, T_2)
IV_ = find_prev_c_from_c(C_1, T_1)

C_4 = find_c_from_prev_c(C_3, T_4)
C_5 = find_c_from_prev_c(C_4, T_5)
C_6 = find_c_from_prev_c(C_5, T_6)

# get golden ticket
payload = IV_ + C_1 + C_2 + C_3 + C_4 + C_5 + C_6
sock.sendlineafter("> ", "3")
sock.sendlineafter("answer> ", payload.hex())
print(sock.recvline().decode().strip())  # expect: Correct!

# find the flag
sock.sendlineafter("> ", "4")
sock.interactive()

ticketの数がぎりぎりに調整されていて、よくできた問題だと思います。今回のセットで一番面白い問題でした。

mathmyth

RSAで280bitの $q$ に対して、 $p$ は224bitの素数 $r$ , $r_2 = r + \alpha$ , 512bitの乱数 $s$ を用いて $p = q^2r_2 + rs$ と表される素数で、 $n = pq, e, c, r$ が与えられる、という問題です。

$n$ を展開すると $q^3r_2 + qrs$ となって $q^3$ の影響が大きそうです。 $r \simeq r_2$ なので $r$ で割っておいて $q' = \left(\frac{n}{r}\right)^{1/3}$ とすると $q \approx q'$ が成り立ちます。

どのくらい近いのか手元で適当な値を生成して実験すると $d = q' - q$ は大体240bit程度ということがわかります*2。この値は $r$ と割と大きさが近いので $d_r = d \mod r$ を考えると、 $d = d_r + rk$ を満たすような $k$ はせいぜい10bitかそこらです。つまり、 $d \mod r$ を求められたら $d$ を探索し、そこから $q = q' - d$ と計算できそうです。

では $d \mod r$ を計算できるのかというと、 $q'$ は知っているので $q \mod r$ がわかればよいです。これは $n \mod r$ を考えると $n \equiv q^3\alpha \mod r$ 、更に $\alpha$ は求められるので $\alpha^{-1}$ をかけてこれの影響も消して $q^3 \mod r$ 、 $r$ は素因数が小さくて素因数分解できるので三乗根が計算できて $q \mod r$ ……と求められます。

f = open("output.txt")

n = int(f.readline().strip().split(" = ")[1])
e = int(f.readline().strip().split(" = ")[1])
c = int(f.readline().strip().split(" = ")[1])
r = int(f.readline().strip().split(" = ")[1])

r2 = next_prime(r)
a = r2 - r

# calculate q mod r
q3r = n % r * Zmod(r)(a).inverse()  # q^3 mod r

ns = ecm.factor(r)
all_roots = []
for p in ns:
    roots = GF(p)(q3r).nth_root(3, all=True)
    all_roots.append([int(root) for root in roots])

import itertools
root_combinations = list(itertools.product(*all_roots))
q_r_list = [crt(list(c), ns) for c in root_combinations]

# calculate q_max - q under mod r
# q_max - q mod r = q_max - q - k*r with small k
# because q_max - q is approximately 250bit, r is 224 bit
q_max = floor((Integer(n) / r)**(1/3))

for q_r in q_r_list:
    q_delta_r = (q_max - q_r) % r
    print(q_max)
    print(q_delta_r)

    # find k and solve q_max - q = q_delta_r + k*r for q
    for k in range(2048):
        q = q_max - (int(q_delta_r) + k*r)
        if n % q == 0:
            print(f"[+] {q=}")
            break
    else:
        continue

    p = n // q
    d = pow(e, -1, (p-1)*(q-1))
    m = pow(c, d, n)

    print(bytes.fromhex(hex(m)[2:]))

これもなかなかおもしろかったのですが、フラグでAIに解かれた、と書いてあってそれに対してどのように考えているのか、なぜわざわざそのような文言のフラグにしたのか、この問題のdifficultyがhardであることとなにか関係があるのかが気になりました。Beginnersくらいの問題はAIが全部解けちゃうよね、ということでしょうか*3

*1:厳密には末尾にパディングブロック

*2:なんか理屈を考えてもわかる気がしますが、実験しがち

*3:最近のAIの演繹上手具合を見ると、究極的には人間とうまく対話したらすべての問題が解けそうですが……

ふるつき

v('=')v 記事がよかったらスターつけていってください