0
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

@potyamaaaain†限界開発鯖†

Daily AlpacaHack: CopperCopperCopper Writeup

0
Last updated at Posted at 2026-02-21

CopperCopperCopper

見て！アルパカがいるよ！ C(・´(ェ)｀・)u

import os
from Crypto.Util.number import getPrime, bytes_to_long

FLAG = os.environ.get("FLAG", "Alpaca{ffffakeflagggg}")

KBITS = 200  # unknown lower bits of p

p = getPrime(512)
q = getPrime(512)
N = p * q
e = 65537

m = bytes_to_long(FLAG.encode())
c = pow(m, e, N)

pbar = p & (~((1 << KBITS) - 1))

print("N =", N)
print("e =", e)
print("c =", c)
print("pbar =", pbar)
print("kbits =", KBITS)

この問題で学ぶ事

  • $p$ の 上位ビットが既知（下位ビットが未知）という状況が、RSA の素因数分解に直結することを理解する
  • SageMath の small_roots を使って、Coppersmith's Attackを使えるようにする

解法

問題概要

今回の問題コードを見ると、 素数$p$ の下位 $kbits = 200$ ビットを 0 に丸めたpbar = p & (~((1 << KBITS) - 1))を提供しています。

素数$p$ を

$$
p = 2^k \cdot t + r,\quad 0 \le r < 2^k
$$

と書きます。
ただし、$t$は商で$t = \left\lfloor \dfrac{p}{2^k} \right\rfloor$、$r$は余りで$r = p \bmod 2^k$を表しています。

このとき

$$
p_{\mathrm{bar}} = 2^k \cdot t
$$

とすると、

$$
p = p_{\mathrm{bar}} + x\quad 0 \le x < 2^k
$$
と表せます。

Coppersmith's Attackの原理

このセクションは論文を引用しながら解説しているため、初心者の方や苦手意識のある方は、最後の2文だけ読んでいただければ大丈夫です！

少し詳しく書いていきます。
最も基本的な形（一変数）では、次の問題を考えます[1]。

  • 整数 $N$ と、多項式 $f(x)\in\mathbb{Z}[x]$が与えられる。
    • (簡単のため、$\delta=\deg f$としておく）
    • $\deg f$は、degree(次数)の略で$f(x)$で一番大きい指数。
  • 次を満たす整数 $x_0$ を見つけたい:

$$
f(x_0)\equiv 0 \pmod N,\qquad |x_0|<X
$$

Coppersmith の（代表的な）定理は、$f$ が monic多項式（最高次係数が1の多項式）であれば、$|x_0|$ が十分小さいときに $x_0$ を多項式時間で見つけられるという内容です。

RSA 由来の攻撃では、合同が成立する法が $N$ そのものではなく、$N$ の未知の大きい約数になることが多いです[2]。
そのため実際には次のようになります。

  • $b\mid N$ は未知だが十分大きいとし、下界 $b\ge N^{\beta}$ が分かっているとする1
  • 次を満たす小さい $x_0$ を見つけたい：

$$
f(x_0)\equiv 0 \pmod b,\qquad |x_0|<X
$$

この状況でも Coppersmithの定理が適用でき、$b\ge N^\beta$ という未知の約数が十分大きいという仮定を使って、小さい根が回収できる範囲を評価できます [2]。
見通しとしては、$f$ が monic で次数 $\delta$ のとき、任意の定数 $\varepsilon>0$ に対して

$$
|x_0|\le N^{\left(\tfrac{\beta^2}{\delta}\right)-\varepsilon}
$$

程度まで回収可能となります。

今回の例では $p\approx N^{1/2}$ なので $\beta\approx 1/2$、さらに $f$ が一次なら $\delta=1$ です。すると境界は

$$
|x_0|\le N^{\left(\tfrac{\left(\frac{1}{2}\right)^2}{1}\right)-\varepsilon}=N^{\frac{1}{4}-\varepsilon}
$$

となります。

以上から、
今回の問題は素数$p$の上位bitが$n$のbit数の$1/4$、すなわち$p$のbit数の$1/2$程度わかっているとき、$f(x) = 0 \pmod b$の解を求めることで$f(x)$の値、つまり$p$を求めることができます。

解法

$p,q$ はどちらも 512-bit なので

$$
p \approx q \approx \sqrt{N} \approx N^{1/2}
$$

と見なすことができます。

今回 $\mathrm{bitlen}(N)\approx 1024$ なので

$$
N^{1/4} \approx 2^{1024/4} = 2^{256}
$$

一方で

$$
|x| < 2^{200} < 2^{256} \approx N^{1/4}
$$

なので、Coppersmith's Attackで解けることがわかります。
さて、
$$
f(x) = p_{\mathrm{bar}} + x
$$

と置いたとき、真の解 $x=x_0$ では

$$
f(x_0)=p_{\mathrm{bar}}+x_0=p
$$
となります。
従って

$$
f(x_0) \equiv 0 \pmod p
$$

が成立します。
さらに、$p | N$ なので「$N$ の未知因数 $p$ を法とする合同式の小さい根」という形になり、Coppersmith's Attackで $|x_0|<2^{200}$ を求めることができます。

その後

$$
q = \frac{N}{p}
$$

で因数分解が完了し、求めることができます。

解法コード

SageMathを使ってsolverを書く場合、以下のようなコードになります。

from Crypto.Util.number import long_to_bytes


def load_params(path="output.txt"):
    data = {}
    for line in open(path, "r", encoding="utf-8"):
        line = line.strip()
        if not line or " = " not in line:
            continue
        k, v = line.split(" = ", 1)
        data[k.strip()] = Integer(v.strip())
    return data

params = load_params()
N = params["N"]
e = params["e"]
c = params["c"]
pbar = params["pbar"]
kbits = params["kbits"]

PR.<x> = PolynomialRing(Zmod(N))
f = x + pbar
roots = f.small_roots(X=2 ** kbits, beta=0.3)

if not roots:
    print("no roots found")
else:
    p = pbar + Integer(roots[0])
    if N % p != 0:
        print("root found but not a factor")
    else:
        q = N // p
        d = inverse_mod(e, (p - 1) * (q - 1))
        m = power_mod(c, d, N)
        print(long_to_bytes(int(m)).decode())

このコードを実行する場合は、sol.sageといったsageファイルに保存を行い、
sage sol.sageと実行しましょう。
ただし、素のsageにはpycryptodomeはインストールされていないため、もしインストールしていない場合は下記コマンドを実行してください[3]。

sage -pip install pycryptodome

また、Pythonコードでsageライブラリをimportする方法もあるでしょう。その場合、以下のコードになります。

from sage.all import *
from Crypto.Util.number import long_to_bytes


def load_params(path="output.txt"):
    data = {}
    with open(path, "r", encoding="utf-8") as f:
        for line in f:
            line = line.strip()
            if not line or " = " not in line:
                continue
            k, v = line.split(" = ", 1)
            data[k.strip()] = Integer(v.strip())
    return data

params = load_params()

N = params["N"]
e = params["e"]
c = params["c"]
pbar = params["pbar"]
kbits = params["kbits"]

PR = PolynomialRing(Zmod(N), names=("x"))
(x) = PR.gen()

f = x + pbar
roots = f.small_roots(X=2 ** int(kbits), beta=0.3)

if not roots:
    print("no roots found")
    exit(1)

p = Integer(pbar) + Integer(roots[0])
if N % p != 0:
    print("root found but not a factor")
    exit(1)

q = N // p
d = inverse_mod(e, (p - 1) * (q - 1))
m = power_mod(c, d, N)

flag = long_to_bytes(int(m))
print(flag.decode())

これを実行する場合は、sol.pyといったファイル名で保存を行い、sage -python sol.pyを実行してください。

最後に、sageのsmall_roots関数以外でも実装されていることがあります。例えば、下記リポジトリは多変数多項式用のCopperSmithを使えます。
https://github.com/keeganryan/cuso

もし、これを使ったコードの場合以下のように書けます。

from sage.all import var
import cuso
from Crypto.Util.number import long_to_bytes


def load_params(path="output.txt"):
    data = {}
    for line in open(path, "r", encoding="utf-8"):
        line = line.strip()
        if not line or " = " not in line:
            continue
        k, v = line.split(" = ", 1)
        data[k.strip()] = int(v.strip())
    return data


params = load_params()
N = params["N"]
e = params["e"]
c = params["c"]
pbar = params["pbar"]
kbits = params["kbits"]

x = var("x")
f = x + pbar
roots = cuso.find_small_roots(
    [f],
    bounds={x: (0, 2 ** kbits)},
    modulus="p",
    modulus_multiple=N,
    modulus_lower_bound=2 ** ((N.bit_length() // 2) - 1),
)

if not roots:
    print("no roots found")
else:
    p = pbar + int(roots[0][x])
    if N % p != 0:
        print("root found but not a factor")
    else:
        q = N // p
        d = pow(e, -1, (p - 1) * (q - 1))
        m = pow(c, d, N)
        print(long_to_bytes(m).decode())

以上のコードを実行することにより、フラグを得られます。
Flag: Alpaca{Th3_C0pp3r5m17h_m37h0d_w45_pr0p053d_by_D0n_C0pp3r5m17h:)}

最後に

この問題は$p$ の上位ビット漏えい + Coppersmith's Attackを使うと気づければ、SageMath の small_roots を呼ぶ形の実装例がすでに公開されているため、solver 自体は既存のものを参考にしやすい部類です。
たとえば inaz2 さんの記事では、$p$ を復元する流れが具体的な Sage スクリプト付きで説明されています [4]。

一方で、Coppersmith を含む格子系の Crypto はなぜ動くのかを納得するまでに、整数論・多項式環・格子・LLL など周辺の数学が広く、最初はとっつきにくいと感じる人も少なくないと思います。
近年は LLM を含む AI ツールも身近になってきたので、証明や導出をいきなり完走しようとせず、「この式変形は何を使っている？」「このパラメータは何を意味する？」のように疑問を小さく分解し、AI に投げたり、友達と会話しながら一つずつ整理していくのが学びやすいはずです。
私が作問する問題も基本的には「1 問に 1 技術」を意識して、解いた後に何かしら持ち帰れるような題材を入れていきたいと思っています。今回のように難しく感じる問題でも、ぜひ挑戦してみてください！

おまけ

  • copperが3つある
    copperをLEET表記するとC0pp3rとなるので3つ書いてます。
  • 問題文のアルパカ
    C(・´(ェ)｀・)uですが、手をCとuにして、Cuすなわち銅にしてました。

参考文献

[1] https://link.springer.com/chapter/10.1007/3-540-68339-9_14
[2] https://link.springer.com/chapter/10.1007/3-540-68339-9_16
[3] https://github.com/alpacahack/resources/blob/main/resources/SageMath.md#sagemath-%E3%81%A7%E3%81%AE-pip-install
[4] https://inaz2.hatenablog.com/entry/2016/01/20/022936

  1. $N$の未知の約数$b$があり、ただし$b$が十分大きくて$b \ge N^{\beta}$だと分かっている ↩

0
0
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
0
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?