AlpacaHack Round 3 (Crypto)へ参加しました。そのwrite-up記事です。

コンテスト概要

2024/09/15(日) 12:00 +09:00 - 09/15(日) 18:00 +09:00の6時間開催でした。他ルールはコンテストページから引用します:

AlpacaHack Round 3 (Crypto) へようこそ！
AlpacaHack は個人戦の CTF を継続して開催する新しいプラットフォームです。

AlpacaHack Round 3 は AlpacaHack で行われる 3 回目の CTF で、Crypto カテゴリから 4 問が出題されます。 幅広い難易度の問題が出題されるため、初心者を含め様々なレベルの方に楽しんでいただけるようになっています。

これらの問題は xornet と keymoon によって作成されました！

参加方法
- 右上の「Sign Up」ボタンから AlpacaHack のユーザー登録をしてください。
- 登録完了後、このページの「Register」ボタンを押して CTF の参加登録をしてください。

注意事項
- AlpacaHack は個人戦のCTFプラットフォームであるため、チームでの登録は禁止しています。
- 問題は運営が想定した難易度の順に並んでいます。
- 問題の配点は解いた人数に応じて変動します。
  - 全てのアナウンスは AlpacaHack の Discord サーバー で行われます。
  - アナウンスは本サービス上でも行うことがありますが、Discord サーバーが主な連絡手段となります。
- 問題が発生した場合、#ticket チャンネルから連絡してください。ただし、問題のヒントは提供しません。

Round 2同様に 問題は運営が想定した難易度の順に並んでいます となっており、並び順で想定難易度が示されました。

結果

正の得点を得ている91人中、104点で49位でした:

また、Certificate箇所から順位の証明書も表示できます:

環境

WindowsのWSL2(Ubuntu 24.04)を使って取り組みました。

Windows

c:\>ver

Microsoft Windows [Version 10.0.19045.4894]

c:\>wsl -l -v
  NAME                   STATE           VERSION
* Ubuntu-24.04           Running         2
  docker-desktop-data    Running         2
  kali-linux             Stopped         2
  docker-desktop         Running         2
  Ubuntu-22.04           Running         2

c:\>

他ソフト

Visual Studio Code Version: 1.93.1 (system setup)

WSL2(Ubuntu 24.04)

$ cat /proc/version
Linux version 5.15.153.1-microsoft-standard-WSL2 (root@941d701f84f1) (gcc (GCC) 11.2.0, GNU ld (GNU Binutils) 2.37) #1 SMP Fri Mar 29 23:14:13 UTC 2024
$ cat /etc/os-release
PRETTY_NAME="Ubuntu 24.04.1 LTS"
NAME="Ubuntu"
VERSION_ID="24.04"
VERSION="24.04.1 LTS (Noble Numbat)"
VERSION_CODENAME=noble
ID=ubuntu
ID_LIKE=debian
HOME_URL="https://www.ubuntu.com/"
SUPPORT_URL="https://help.ubuntu.com/"
BUG_REPORT_URL="https://bugs.launchpad.net/ubuntu/"
PRIVACY_POLICY_URL="https://www.ubuntu.com/legal/terms-and-policies/privacy-policy"
UBUNTU_CODENAME=noble
LOGO=ubuntu-logo
$ python3 --version
Python 3.12.3
$ python3 -m pip show pip | grep Version:
Version: 24.0
$ python3 -m pip show pycryptodome | grep Version:
Version: 3.20.0
$ python3 -m pip show sympy | grep Version:
Version: 1.12
$

解けた問題

[Crypto] qrime (91 solves, 104 points)

not crime and prime

配布ファイルとして、問題本体のchall.pyと、その出力のchall.txtがありました。chall.pyは次の内容でした:

import os
from Crypto.Util.number import bytes_to_long, getRandomNBitInteger, isPrime

def nextPrime(n):
    while not isPrime(n := n + 1):
        continue
    return n

def gen():
    while True:
        q = getRandomNBitInteger(256)
        r = getRandomNBitInteger(256)
        p = q * nextPrime(r) + nextPrime(q) * r
        if isPrime(p) and isPrime(q):
            return p, q, r

flag = os.environ.get("FLAG", "fakeflag").encode()
m = bytes_to_long(flag)

p, q, r = gen()
n = p * q

phi = (p - 1) * (q - 1)
e = 0x10001
d = pow(e, -1, phi)
c = pow(m, e, n)

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

$p$ は $q$ と $r$ から計算されること、 $r$ は出力に含まれているため既知であることが分かります。 $n$ を開くと次のようになります:

$\begin{eqnarray} n &=& p*q \\ &=& q*(q * \text{nextPrime}(r) + \text{nextPrime}(q) * r) \end{eqnarray}$

ここで、 $r$ と $\text{nextPrime}(r)$ は既知です。 $q$ は未知ですが狭義単調増加、 $\text{nextPrime}(q)$ も未知ですが広義単調増加です。そのため全体として $n$ は $q$ について狭義単調増加となります。このことを使って、二分探索で $q$ を求められます。

ちなみにここで「nextPrime関数箇所はなんとなく手書きよりも既存パッケージを使いたい、調べるとsympy.nextprimeがあるのでそれを使おう」と思ったのですが、sympy.nextprimeの戻り値の型ヒントがint | array[int] | Noneだったのでものすごく使いづらかったです……。書いたソルバーです:

#!/usr/bin/env python3

import ast

import sympy
from Crypto.Util.number import long_to_bytes

with open("chall.txt") as f:
    n = ast.literal_eval(f.readline().split("=")[1])
    e = ast.literal_eval(f.readline().split("=")[1])
    c = ast.literal_eval(f.readline().split("=")[1])
    r = ast.literal_eval(f.readline().split("=")[1])


def bin_search(n: int, r: int) -> int:
    low = 0
    high = 1 << 256
    mid = 0
    while low < high:
        mid = (low + high) // 2
        q = mid
        p: int = q * sympy.nextprime(r) + sympy.nextprime(q) * r  # type: ignore
        # print((n - (p * q)))
        if p * q >= n:
            high = mid
        else:
            low = mid + 1
    return mid


q = bin_search(n, r)
print(f"{q = }")
assert n % q == 0
p = n // q
phi = (p - 1) * (q - 1)
d = pow(e, -1, phi)
p = pow(c, d, n)
print(long_to_bytes(p))

実行しました:

$ time ./solve.py
q = 57138703210086603216917938147752779170509477993762976004506899310197198907231
b'Alpaca{q_and_r_have_nothing_to_do_with_QR_code}'
./solve.py  1.81s user 0.04s system 99% cpu 1.858 total
$

フラグを入手できました: Alpaca{q_and_r_have_nothing_to_do_with_QR_code}

感想

長らく思っていることですけれど、Cryptoジャンルでは解くために数学の力が必要になることも多い印象です。概念、用語、手法の理解が重要ですね……。
TeXを久しぶりに書こうとするたびに、記法を忘れているので毎回調べている気がします。

プログラム系統備忘録ブログ

記事中のコードは自己責任の下でご自由にどうぞ。

AlpacaHack Round 3 (Crypto) write-up