ふるつき

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

Daily AlpacaHackに挑戦するつくよみちゃん

という動画シリーズを最近投稿している。

www.nicovideo.jp

Daily AlpacaHackという、毎日初心者向けの問題を1問出題してくれる常設型のCTFイベントがあって、その問題を大体毎日解いて、動画にして投稿している。 解いている様子を画面録画して、画面右下にゆっくりつくよみちゃんが登場し、そのとき考えていたことや喋っていたことを喋ってくれて、字幕がついている。なんとなくBGMもついている、みたいな単純な動画をアップロードしてる。

初心者の人にとっては他人が解いている風景が動画という形式でもれなく示されて、考えていることが常に喋られているというのは嬉しいのではないかと思っていて、自分の取り組みがDaily AlpacaHackの盛り上がりに寄与できていたら嬉しい。

これをやってるのはなんとなくできそうだったからだけど、実際仕組みを組んでみたら結構簡単にできて感動したので、仕組みを紹介。

ざっくりこういう感じ。

graph TD
    A[OBS Studio: 録画データ] --> B[OpenAI Whisper: 文字起こし]
    B --> C[SRTファイル: 手動修正]
    C --> D[SHAREVOX: 音声生成]
    C --> E[SHAREVOX: 母音・発話時間取得]
    F[PSDファイル: イラスト素材] --> G[表情合成処理]
    E --> G
    D --> H[ffmpeg: 合成処理]
    A --> H
    C --> H
    G --> H
    H --> I[完成動画]

    style A fill:#f9f,stroke:#333
    style I fill:#bbf,stroke:#333
    style H fill:#ff9,stroke:#333

録画・文字起こし・音声合成……みたいな難しいところは全部既存のアプリケーションがなんとかしてくれて、自分はちょっと高級なffmpegのwrapperを書いたら完了。ffmpegの扱いもAIに聞いたらよく、良い時代。Whisperみたいな高級書き起こしツールが登場してくれたおかげで、自分は適当にマイクに向かって喋りながら問題を解いておいたらある程度意味の通る台本ができあがっているので、修正の手間はほとんどない。10年前にこれを作るのは簡単ではなかっただろうな。

ただ不満もあって、今改善したいのは文字起こしが画面というか実際の発話に比べてちょっと早すぎるのと文字起こしの精度がわるいこと。だけど、これは自分の努力では難しくて、Whisperの進歩に頼ることになりそう。

個人的にはSHAREVOX（VOICEVOXのフォーク？　つくよみちゃんの音声が入ってるのはこっちだった）のAPIで発話の長さや母音が取れたのが面白かった。これを元にゆっくりつくよみちゃん素材のPSDから口の形を合成する、みたいなこともできて楽しい。しかしこういうのはよくみる動画とかでもやられている気がするので、自分で作らなくてもなんかツールがあったんっだろうと思っている。

作ってて一番苦労したのは動画の合成部分で、最初はmoviepyを使ってこのフレームはこの表情で音声はこれ、みたいなのを指示していたんだけど、フレームごとにループしてffmpegに入力する、というのをpythonでやると遅すぎて、30分の動画の合成に10時間くらいかかっていた。これはpythonのソースコードをclaude codeに読ませて「Goにして。並列化できるところは並列化して」と言ったら改善した。Goで書かれたffmpegのwrapperができあがり、30分の動画も1時間ちょっとで出力されるくらいになった。

一応作ったコードも公開しておきます。アセットはリポジトリに含めてないのにソースコードにベタ書きしてるから、適宜フォントやBGM、ゆっくりつくよみちゃん素材をいい感じの場所に配置してもらう必要がある。

https://github.com/theoremoon/yukkuri-tsukuyomi-chan-jikkyogithub.com

seiga.nicovideo.jp

これでだれでもゆっくりつくよみちゃん実況がつくれます。でもそれよりDaily AlpacaHackを解いてほしい。解けなかったらつくよみちゃんが解いている動画をみてupsolveしてください。動画がわかりにくかったら教えてください。よろしくお願いします。

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年に読み始めて面白かったWeb小説

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

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

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