暗号学入門

CTF Crypto 万能マニュアル · 古典から量子まで

暗号学（Crypto）は CTF の中で最も数学的素養が試される分野です。本記事では古典暗号から出発し、共通鍵暗号、RSA、楕円曲線、ハッシュと MAC、暗号プロトコル、エンコーディングとステガノグラフィ、サイドチャネル、そしてポスト量子暗号までを順に取り上げ、よく使われる攻撃の考え方とツールチェーンを整理します。

第1章：古典暗号への攻撃

1.1 換字暗号（Substitution Cipher）

換字暗号は古典暗号の中で最も基礎的な形式で、その核心となる考え方は、平文の各文字を固定の対応規則に従って別の文字に置き換えることです。置き換え規則の違いにより、単一換字式と多表換字式の2種類に大きく分けられます。

1.1.1 シーザー暗号（Caesar Cipher）

シーザー暗号は最も単純なシフト暗号で、アルファベットの各文字を固定の桁数 k だけ後ろ（または前）にずらします。暗号化の式は C = (P + k) mod 26、復号の式は P = (C - k) mod 26 です。

💡 攻撃方法： 鍵空間はシフト値が取り得る25通り（k=1 から 25）しかないため、シーザー暗号は総当たり攻撃（Brute Force）で一瞬にして破られます。CTF の問題では、通常は25通りのシフトをすべて試せば平文が得られます。

# Python でシーザー暗号を総当たり
for k in range(1, 26):
    plain = ''.join(
        chr((ord(c)-65-k)%26+65) if c.isupper() 
        else chr((ord(c)-97-k)%26+97) if c.islower() else c 
        for c in ciphertext
    )
    print(f"k={k}: {plain}")

1.1.2 アフィン暗号（Affine Cipher）

アフィン暗号はシーザー暗号を拡張したもので、a と b の2つの鍵を使います。暗号化の式は C = (a·P + b) mod 26 です。gcd(a, 26) = 1、すなわち a が26と互いに素であることが条件です。

💡 攻撃方法：

• 総当たり攻撃： 条件を満たす a は12通り（1,3,5,7,9,11,15,17,19,21,23,25）、b は26通りあり、鍵空間は合計312通りしかないため、総当たりは非常に容易です。
• 既知平文攻撃： 平文と暗号文の組を2つ知っていれば、連立方程式を立てて a と b を解けます。

1.1.3 単一換字暗号（Monoalphabetic Substitution）

26個の文字をランダムに26個の文字へ写像する方式で、鍵空間は 26! ≈ 4×10²⁶ です。鍵空間は巨大ですが、平文の頻度特性がそのまま残るため、頻度分析によって簡単に破られます。

💡 頻度分析攻撃（Frequency Analysis）：

1. 暗号文中に現れる各文字の頻度を数えます。
2. 暗号文の文字を頻度の高い順に並べます。
3. 英語の文字頻度表（E≈12.7%, T≈9.1%, A≈8.2%, O≈7.5%, I≈7.0%, N≈6.7%）と照らし合わせて初期対応付けを行います。
4. 2文字の組み合わせ（bigram）の頻度（TH, HE, IN, ER, AN など）や3文字の組み合わせ（trigram）の頻度（THE, AND, THA, ENT など）を組み合わせて精度を高めます。
5. 文脈の意味を利用して人手で調整し、完全な平文を徐々に復元します。

1.2 多表換字暗号

1.2.1 ヴィジュネル暗号（Vigenère Cipher）

ヴィジュネル暗号は、キーワード（鍵）を用いた多表換字式の暗号です。暗号化の際には鍵を循環的に繰り返し、各平文文字を鍵の対応する位置の文字でシーザーシフトします。暗号化の式は Cᵢ = (Pᵢ + Kᵢ) mod 26 です。

💡 カシスキー検査法（Kasiski）： 暗号文中で繰り返し現れる文字列の断片を探し、それらの間の距離を計算します。これらの距離の最大公約数（GCD）は鍵長の倍数である可能性が高いです。

💡 一致指数法（Index of Coincidence, IoC）： 一致指数とは、テキストからランダムに2文字を選んだときに同じ文字である確率を表す指標です。英語のテキストの IoC は約0.067、完全にランダムなテキストの IoC は約0.038です。

攻撃の手順：

1. 鍵長 L を推測し、暗号文を列ごとに L 個のグループへ分けます。
2. 各グループの IoC を計算し、0.067 に近ければ推測は正しいと判断します。
3. 各グループに対して個別に頻度分析（単一換字のシーザー暗号と同等）を行い、各位置のシフト量を求めます。

1.2.2 ヒル暗号（Hill Cipher）

線形代数に基づくブロック暗号で、平文を n 次元ベクトルに分割し、n×n の可逆行列を鍵として線形変換を行います。

⚠️ 既知平文攻撃： 線形独立な n 次元の平文・暗号文の組を n 組知っていれば、行列方程式を直接構成して鍵行列を解けます。これがヒル暗号の最も致命的な弱点です。

1.3 転置暗号（Transposition Cipher）

1.3.1 レールフェンス暗号（Rail Fence Cipher）

平文を「ジグザグ」状に n 行へ並べ、その後に行ごとに読み出して暗号文を得ます。鍵は行数 n です。

💡 攻撃： 取り得る行数をすべて試します（通常、問題には範囲やヒントが与えられます）。そのまま平文を再構築します。

1.3.2 列転置暗号（Columnar Transposition）

平文を固定の列数を持つ行列に行方向に書き込み、その後、鍵で指定された列の順序に従って読み出します。鍵が数字の並びであれば、数字の大小の順に各列を読み出します。

💡 攻撃： 異なる列数を試し、言語的特徴（よく現れる単語の断片など）を組み合わせて探ります。短い暗号文であれば、考えられる列の順列をすべて総当たりできます。

1.4 CTF 頻出 古典暗号クイックリファレンス

暗号名	特徴	攻撃方法
豚小屋暗号（Pigpen）	記号による置換、豚小屋のような形	表を参照して置換
ベーコン暗号（Bacon）	5ビットの2進符号、A/B の2種類の書体	書体の違いや2つの状態を識別
モールス信号（Morse）	点と線の組み合わせ	表を参照して翻訳
キーボード暗号	キーボードの位置や形を利用	キーボード配列を観察
質屋暗号（当舗暗号）	漢字の画数に含まれる「口」の数	「口」の数を数える
与佛論禅	特定サイトのエンコーディング	オンラインデコードツールを使う
核心価値観エンコード	12個の単語による符号化	表を参照、またはオンラインツール
百家姓エンコード	姓と符号の対応	表を参照してデコード
アトバシュ暗号（Atbash）	アルファベットの先頭と末尾を対応	固定の写像で置換
ROT13	13シフトのシーザー暗号	もう一度 ROT13 すれば復号できる
ポリュビオス方陣	5×5 の座標による符号化	座標から文字を復元
ADFGX/ADFGVX	第一次大戦のドイツ軍暗号、換字と転置の組合せ	まず転置を破り、次に換字を破る
Playfair	5×5 行列、2文字単位の換字	頻度分析＋既知平文

第2章：共通鍵暗号への攻撃

2.1 ブロック暗号の基礎

ブロック暗号は平文を固定長のブロック（64ビットや128ビットなど）に分割し、鍵を用いて各ブロックを独立に暗号化します。代表的なブロック暗号には DES（64ビットブロック）、3DES、AES（128ビットブロック）などがあります。

2.2 ブロック暗号の動作モードへの攻撃

2.2.1 ECB モードへの攻撃（Electronic Codebook）

ECB モードは最も単純なブロック暗号の動作モードで、各平文ブロックを独立に暗号化します。その最大の弱点は、同じ平文ブロックは常に同じ暗号文ブロックを生成することです。

⚠️ 攻撃手段：

• パターン認識： 平文に繰り返しがあれば、暗号文にも繰り返しブロックが現れ、平文の構造情報が漏れます。
• ブロック置換攻撃： 攻撃者は鍵を知らなくても、暗号文のブロックAをブロックBに置き換えることで、復号時に平文ブロックを置き換えられます。たとえば、ユーザーAの暗号化された残高ブロックをユーザーBの残高ブロックに置き換える、といったことが可能です。
• 並べ替え攻撃： 暗号文ブロックの順序を並べ替えると、復号後の平文のブロック順序もそれに応じて変わります。

✅ CTF の実例： ECB 暗号化の Oracle が与えられ、任意の平文を投入できる場合、平文ブロックを1バイトずつ構築し、暗号文ブロックを比較することで未知の平文を1バイトずつ復元できます（選択平文攻撃に類似）。

2.2.2 CBC モードへの攻撃（Cipher Block Chaining）

CBC モードでは、各平文ブロックは暗号化の前に直前の暗号文ブロックと XOR されます。最初のブロックには初期化ベクトル（IV）を使います。暗号化の式は Cᵢ = E_K(Pᵢ ⊕ Cᵢ₋₁)、復号の式は Pᵢ = D_K(Cᵢ) ⊕ Cᵢ₋₁ です。

Padding Oracle 攻撃

PKCS#7 パディングを使う場合、復号後の最後のブロックでパディングが正当かどうかが検査されます。パディングが不正であれば、サーバーは異なるエラーメッセージ（「パディングエラー」と「復号エラー」など）を返す可能性があります。

⚠️ 攻撃の原理：

1. 攻撃者は暗号文 C = [IV, C₁, C₂, ..., Cₙ] を傍受します。
2. 最後の暗号文ブロック Cₙ に対して中間ブロック C'ₙ₋₁ を構成し、D_K(Cₙ) ⊕ C'ₙ₋₁ の最後のバイトが 0x01（正当なパディング）になるようにします。
3. C'ₙ₋₁ の最後のバイトを走査し（256通り）、サーバーの応答を観察して、パディングが正当になる値を見つけます。
4. これにより D_K(Cₙ) の最後のバイトを計算できます。
5. この手順を繰り返し、鍵を知ることなく平文全体を1バイトずつ復元します！

# Padding Oracle 攻撃の擬似コード
for byte_pos in reversed(range(block_size)):
    for guess in range(256):
        crafted = modify_iv_to_produce_padding(ciphertext, known_bytes, guess, byte_pos)
        if oracle(crafted) == "VALID_PADDING":
            known_bytes[byte_pos] = guess ^ padding_value
            break

CBC ビットフリッピング攻撃（Bit Flipping Attack）

Pᵢ = D_K(Cᵢ) ⊕ Cᵢ₋₁ であるため、Cᵢ₋₁ のあるビットを変更すると、Pᵢ の対応するビットが反転します。

💡 攻撃： 攻撃者が平文のある部分の内容を知っていれば、直前の暗号文ブロックの対応するビットを反転させることで、次のブロックの復号結果を正確に制御できます。認証の回避（"admin=false" を "admin=true" に変えるなど）によく使われます。

2.2.3 CTR モードへの攻撃（Counter Mode）

CTR モードはブロック暗号をストリーム暗号に変換し、鍵ストリームを生成して平文と XOR します。暗号化の式は Cᵢ = Pᵢ ⊕ E_K(Nonce || Counterᵢ) です。

⚠️ 攻撃：

• Nonce の再利用： 2回の暗号化で同じ Nonce と同じ鍵を使うと、C₁ ⊕ C₂ = P₁ ⊕ P₂ になります。一方の平文を知っていれば、もう一方の平文を直接求められます。
• ビットフリッピング： ストリーム暗号と同様に、攻撃者は暗号文のビットを反転でき、平文の対応するビットが反転します。

2.2.4 OFB / CFB モードへの攻撃

OFB モードと CFB モードにも CTR と同様の問題があります。鍵ストリームの再利用は平文の漏洩を招き、ビットフリッピング攻撃も成立します。

2.3 ストリーム暗号への攻撃

2.3.1 ワンタイムパッド（One-Time Pad, OTP）の誤用

OTP は理論上完全秘匿性を持ちますが、それは鍵が真にランダムであること、鍵長が平文以上であること、鍵を決して再利用しないこと、という前提があってのことです。

⚠️ 鍵再利用攻撃： 2つの平文 P₁ と P₂ を同じ鍵 K で暗号化すると、C₁ ⊕ C₂ = P₁ ⊕ P₂ になります。英語テキストの冗長性（スペース文字の XOR 特性など）を利用して、2つの平文を復元できます。

2.3.2 LFSR への攻撃

線形帰還シフトレジスタ（LFSR）は多くのストリーム暗号の中核部品です。LFSR の線形性のため、少数の平文・暗号文の組が分かれば、連立一次方程式を解いて初期状態を復元できます。

💡 Berlekamp-Massey アルゴリズム： 2進系列が与えられたとき、このアルゴリズムは O(n²) 時間でその系列を生成する最短の LFSR を見つけられます。2n ビットの鍵ストリームが分かれば、n 段 LFSR の帰還多項式を復元できます。

2.3.3 RC4 への攻撃

RC4 は広く使われているストリーム暗号ですが、複数の統計的偏りが存在します。

• 初期バイトの偏り： 鍵ストリームの2バイト目 S[1] は0に偏る傾向があります（確率は1/256 ではなく約1/128）。
• Fluhrer-Mantin-Shamir 攻撃（FMS）： WEP における IV の弱点を突く攻撃で、特定の IV を持つパケットを大量に収集して鍵を復元します。
• Bar Mitzvah 攻撃： RC4 鍵ストリームの統計的弱点を利用した受動的な復号を行います。

2.4 鍵に関連する攻撃

2.4.1 中間一致攻撃（Meet-in-the-Middle）

二重暗号化 C = E_K₂(E_K₁(P)) に対して、攻撃者は次のことができます。

1. 考えられるすべての E_K₁(P) を計算して保存します（表1）。
2. 考えられるすべての D_K₂(C) を計算して保存します（表2）。
3. 表1と表2の積集合を探し、(K₁, K₂) を得ます。

時間計算量は O(|K|²) から O(|K|) に下がり、空間計算量は O(|K|) です。

2.4.2 スライド攻撃（Slide Attack）

周期的なラウンド関数を持つ暗号（各ラウンドで同じ副鍵を使うなど）に対して、「スライド対」を見つけることで鍵を復元します。ラウンド数は多いがラウンド関数が弱い暗号に適しています。

2.4.3 関連鍵攻撃（Related-Key Attack）

攻撃者が、異なるが関連のある鍵（鍵が既知の定数だけ異なるなど）で暗号化した結果を取得でき、鍵同士の関係を利用して攻撃の複雑度を下げます。

2.5 AES 固有の攻撃

2.5.1 AES 不可能差分攻撃

AES において一部の差分伝播経路の確率が0であるという性質を利用し、排除法によって鍵候補の範囲を絞り込みます。

2.5.2 AES キャッシュタイミング攻撃

AES の S-box 参照操作はメモリ上の参照テーブルにアクセスします。キャッシュアクセス時間を測定することで S-box のインデックスを推測し、ひいては鍵を復元できます。

第3章：RSA 公開鍵暗号への攻撃大全

3.1 RSA の基礎の復習

RSA の安全性は大きな整数の素因数分解の困難性に基づいています。鍵生成：

1. 2つの大きな素数 p と q を選び、n = p × q を計算します。
2. オイラー関数 φ(n) = (p-1)(q-1) を計算します。
3. 公開鍵指数 e（通常は65537）を選び、gcd(e, φ(n)) = 1 を満たすようにします。
4. 秘密鍵 d ≡ e⁻¹ mod φ(n) を計算します。

暗号化：C ≡ Mᵉ mod n；復号：M ≡ Cᵈ mod n。

3.2 素因数分解攻撃

3.2.1 小さな素因子への攻撃

n の因子の1つが小さい場合（10⁶ 未満など）、試し割り法で高速に分解できます。

from sympy import factorint
n = ...  # 与えられた modulus
factors = factorint(n)  # 小さな因子による分解を自動で試みる

3.2.2 Fermat の分解法

p と q が非常に近い場合（|p-q| が小さい場合）、Fermat の方法を使えます。

n = p×q = ((p+q)/2)² - ((p-q)/2)² = a² - b²

a = ⌈√n⌉ から始めて増やしながら、a² - n が完全平方数かどうかを調べます。

import gmpy2
n = ...
a = gmpy2.isqrt(n)
if a*a < n: a += 1
while not gmpy2.is_square(a*a - n):
    a += 1
b = gmpy2.isqrt(a*a - n)
p, q = a + b, a - b

3.2.3 Pollard's p-1 アルゴリズム

p-1 が小さな素因子しか持たない場合（すなわち p-1 が B-smooth である場合）、a^(B!) mod n を計算し GCD を利用して因子を見つけられます。

def pollard_p1(n, B=10**5):
    a = 2
    for j in range(2, B):
        a = pow(a, j, n)
        d = gmpy2.gcd(a-1, n)
        if 1 < d < n:
            return d
    return None

3.2.4 Pollard's Rho アルゴリズム

Floyd の循環検出法を用い、擬似乱数列によって法 n の下で衝突を探します。期待時間計算量は O(n^(1/4)) です。

def pollard_rho(n):
    if n % 2 == 0: return 2
    x, y, c = 2, 2, 1
    f = lambda x: (pow(x, 2, n) + c) % n
    d = 1
    while d == 1:
        x = f(x)
        y = f(f(y))
        d = gmpy2.gcd(abs(x-y), n)
    return d if d != n else None

3.2.5 ECM（楕円曲線法）

中程度の大きさの因子（10進で20〜50桁）に対して、ECM は最も有効な手法の1つです。楕円曲線群上の演算を利用して因子を探します。

3.2.6 二次篩法（Quadratic Sieve, QS）

100桁未満の整数の分解に適しています。x² ≡ y² mod n を満たす数の組を探すことで n を分解します。

3.2.7 一般数体篩法（General Number Field Sieve, GNFS）

現在知られている最速の古典的な整数分解アルゴリズムで、100桁以上の大きな整数に適しています。時間計算量は L_n[1/3, c] です。

3.3 小さな公開鍵指数への攻撃

3.3.1 小さな e への攻撃（e=3）

e=3 かつ M³ < n のとき、暗号文の立方根を直接取って平文を得られます：M = ⌊C^(1/3)⌋。

3.3.2 放送攻撃（Håstad's Attack）

同じ平文 M を、同じ e と異なる n₁, n₂, ..., nₑ で暗号化し、かつ Mᵉ < n₁×n₂×...×nₑ である場合、中国剰余定理（CRT）を使って Mᵉ を復元し、さらに e 乗根を取ります。

from functools import reduce

def crt(moduli, remainders):
    total = 0
    prod = reduce(lambda a, b: a*b, moduli)
    for m, r in zip(moduli, remainders):
        p = prod // m
        total += r * pow(p, -1, m) * p
    return total % prod

M_e = crt([n1, n2, n3], [c1, c2, c3])
M = gmpy2.iroot(M_e, 3)[0]  # 立方根を開く

3.3.3 Franklin-Reiter 関連メッセージ攻撃

2つの平文 M₁ と M₂ が線形関係 M₂ = f(M₁)（M₂ = a·M₁ + b など）を満たし、同じ (n, e) で暗号化されている場合、e=3 のとき平文を直接復元できます。

3.3.4 Coppersmith 攻撃

Coppersmith の手法は、多項式時間で法 n の下での小さい根を見つけることができます。

💡 適用場面：

• 部分メッセージの漏洩： 平文の最上位ビットや最下位ビットが分かっていれば、残りの部分を復元できます。
• stereotyped messages： 平文の形式が M = pad || m で m が小さい場合、m を復元できます。
• 小さな秘密指数： d < n^0.292 のとき、Boneh-Durfee の拡張によって d を復元できます。

# SageMath の Coppersmith を使う
# M = known_prefix * 2^k + x が既知として、小さい根 x を求める
PR.<x> = PolynomialRing(Zmod(n))
f = (known_prefix * 2^k + x)^e - c
roots = f.small_roots(X=2^k, beta=1)

3.4 秘密鍵の復元攻撃

3.4.1 Wiener 攻撃

秘密鍵が d < n^0.25 / 3 のとき、e/n の連分数展開によって d を復元できます。

💡 原理： e/n ≈ e/φ(n) = k/d（ある小さな整数 k について）。したがって k/d は e/n の収束子であり、連分数アルゴリズムで見つけられます。

from fractions import Fraction

def wiener_attack(e, n):
    cont = continued_fraction(e/n)
    convergents = cont.convergents()
    for k_d in convergents:
        k, d = k_d.numerator(), k_d.denominator()
        if k == 0: continue
        phi = (e*d - 1)//k
        s = n - phi + 1
        disc = s*s - 4*n
        if disc >= 0:
            sqrt_disc = gmpy2.isqrt(disc)
            if sqrt_disc*sqrt_disc == disc:
                p = (s + sqrt_disc)//2
                q = (s - sqrt_disc)//2
                if p*q == n:
                    return d, p, q
    return None

3.4.2 Boneh-Durfee 攻撃

Wiener 攻撃の拡張で、d < n^0.292 のときに有効です。格子基底縮小（LLL）アルゴリズムを用いて2次元格子の中で短いベクトルを探します。

3.5 共通 modulus と共通因子への攻撃

3.5.1 共通 modulus 攻撃（Common Modulus Attack）

同じ平文 M を、同じ n と互いに素な e₁, e₂ で暗号化して C₁, C₂ を得た場合、拡張ユークリッドアルゴリズムで a·e₁ + b·e₂ = 1 となる a, b を見つけ、M = C₁ᵃ × C₂ᵇ mod n を計算できます。

def common_modulus_attack(c1, c2, e1, e2, n):
    g, a, b = extended_gcd(e1, e2)
    if a < 0:
        c1 = pow(c1, -1, n)
        a = -a
    if b < 0:
        c2 = pow(c2, -1, n)
        b = -b
    return (pow(c1, a, n) * pow(c2, b, n)) % n

3.5.2 共通因子攻撃（GCD Attack / Common Factor Attack）

複数の RSA の modulus が1つの素因子を共有している場合（n₁ = p×q₁, n₂ = p×q₂ など）、gcd(n₁, n₂) = p を計算するだけで分解できます。

# 一括 GCD 攻撃（大量の modulus に対して）
def batch_gcd_attack(moduli):
    from math import gcd
    for i in range(len(moduli)):
        for j in range(i+1, len(moduli)):
            g = gcd(moduli[i], moduli[j])
            if g > 1:
                return i, j, g
    return None

3.6 選択暗号文攻撃

3.6.1 Bleichenbacher 攻撃（PKCS#1 v1.5 Padding Oracle）

RSA 暗号化で PKCS#1 v1.5 パディングを使う場合への攻撃です。サーバーが復号後にパディング形式を検査し、形式が誤っているときに異なるエラーメッセージを返すなら、攻撃者は次のことができます。

1. 倍数 s を選び、C' = C × sᵉ mod n を構成します。
2. C' をサーバーへ送り、パディング検査を通過するかどうかを観察します。
3. 二分探索によって平文が存在する区間を徐々に狭め、最終的に平文を完全に復元します。

3.6.2 ROBOT 攻撃

Bleichenbacher 攻撃の現代的変種で、TLS における RSA 鍵交換の実装を狙います。2017年に発見され、複数の主要な TLS ライブラリに影響しました。

3.7 サイドチャネルと実装への攻撃

3.7.1 タイミング攻撃

冪剰余演算における条件分岐（Montgomery 還元など）により、実行時間が鍵のビットに依存します。復号時間を精密に測定することで、秘密鍵 d を1ビットずつ復元できます。

3.7.2 故障注入攻撃（Fault Injection）

電圧・クロック・レーザーによる故障注入で、冪剰余演算に計算誤りを引き起こします。たとえば Cᵈ mod n の途中のステップで誤りが生じて M' が得られた場合、gcd(M - M', n) が因子の情報を漏らす可能性があります。

3.7.3 ROCA 攻撃（Return of Coppersmith's Attack）

2017年に発見されました。一部のハードウェアセキュリティキー（YubiKey など）が弱い乱数生成器で RSA 素数を生成していたため、素数が特定の構造を持っていました。Coppersmith の手法を利用して、こうした弱い鍵を効率的に分解できます。

3.8 特殊なシナリオへの攻撃

3.8.1 小さな復号指数と CRT

中国剰余定理（CRT）で復号を高速化する際、一方の素数のパラメータ計算が誤っていると、1回の誤った結果から p と q を復元できます。

3.8.2 部分的な鍵漏洩攻撃

秘密鍵 d の一部のビット（最上位ビットの半分など）が分かっていれば、格子法を用いて完全な秘密鍵を復元できます。

3.8.3 RSA 盲署名攻撃

サーバーが任意のメッセージに対して RSA 盲署名を行う場合（メッセージをハッシュしてから署名する）、攻撃者は特殊なメッセージを構成してハッシュ検査を回避し、悪意あるメッセージに対する正当な署名を得られます。

第4章：楕円曲線暗号への攻撃

4.1 ECC の基礎

楕円曲線暗号（ECC）は楕円曲線離散対数問題（ECDLP）の困難性に基づいています。楕円曲線 E 上の点 P と Q = d·P が与えられたとき、整数 d を求めることは困難です。

4.2 離散対数への攻撃

4.2.1 大步小步法（Baby-Step Giant-Step, BSGS）

時間計算量と空間計算量はいずれも O(√n) です。位数があまり大きくない群に適しています。

def bsgs(P, Q, order):
    m = int(gmpy2.isqrt(order)) + 1
    baby = {j*P: j for j in range(m)}
    mP = m * P
    for i in range(m):
        point = Q - i * mP
        if point in baby:
            return i * m + baby[point]
    return None

4.2.2 ECDLP に対する Pollard's Rho

楕円曲線上でランダムウォークを用いて衝突を探します。期待時間計算量は O(√n) ですが、空間計算量は O(1) だけです。

4.2.3 Pohlig-Hellman アルゴリズム

群の位数 n が小さな素数の積 n = p₁^e₁ × p₂^e₂ × ... に分解できる場合、各部分群で個別に離散対数を解き、中国剰余定理で結果を組み合わせられます。

⚠️ CTF の要点： 楕円曲線の位数が滑らかな数（smooth number）、すなわちすべての素因子が小さい場合、Pohlig-Hellman は多項式時間で ECDLP を破れます！

4.3 弱い曲線への攻撃

4.3.1 異常曲線攻撃（Anomalous Curve Attack）

楕円曲線の位数が #E(F_p) = p（つまり曲線が anomalous である）場合、ECDLP は多項式時間で解けます。この攻撃は Semaev、Satoh-Araki、Smart がそれぞれ独立に発見しました。

4.3.2 MOV 攻撃（Menezes-Okamoto-Vanstone）

Weil ペアリングや Tate ペアリングを利用し、楕円曲線上の離散対数問題を有限体の乗法群へ写像します。埋め込み次数（embedding degree）k が小さい場合（k ≤ 6 など）、有限体上で指数計算法（Index Calculus）を使って解けるため、ECDLP を直接攻撃するよりはるかに容易です。

⚠️ 防御： 実際の応用では埋め込み次数の大きな曲線を選ぶべきです（標準曲線 secp256k1 の埋め込み次数は約 10⁷⁵）。

4.3.3 特異曲線攻撃

判別式が Δ = 0 の場合、曲線は特異であり、加法群や乗法群へ写像できるため、ECDLP は容易になります。

4.4 ECDSA 署名への攻撃

4.4.1 Nonce 再利用攻撃

ECDSA 署名では、署名のたびに異なる乱数 k を使わなければなりません。2回の署名で同じ k を使うと：

s₁ = k⁻¹(H(m₁) + r·d)
s₂ = k⁻¹(H(m₂) + r·d)

2式を引くと d が消去でき、k を直接解いて、さらに秘密鍵 d を解けます。

def ecdsa_nonce_reuse(r, s1, s2, h1, h2, n):
    k = ((h1 - h2) * pow(s1 - s2, -1, n)) % n
    d = ((s1 * k - h1) * pow(r, -1, n)) % n
    return k, d

4.4.2 Nonce 偏り攻撃（Nonce Bias / Lattice Attack）

k の一部のビットが既知であるか、偏りが存在する場合（偏りのある乱数生成器で生成された場合など）、格子法（LLL）を用いて秘密鍵を復元できます。たとえば k の最上位ビットが既知である場合や、k が一定のしきい値より小さい場合、格子を構成して LLL アルゴリズムを適用できます。

4.4.3 署名の可鍛性（Signature Malleability）

(r, s) が有効な署名ならば、(r, -s mod n) も有効な署名になります。一部の実装ではリプレイ攻撃につながる可能性があります。

4.5 ECC 実装への攻撃

4.5.1 点検証の欠如への攻撃

実装が入力点を曲線上にあるか検証しない場合、攻撃者は曲線上にない点を送り、誤った点演算を利用して秘密鍵の情報を漏洩させられます（Invalid Curve Attack など）。

4.5.2 Small Subgroup 攻撃

低次の点をサーバーへ送ることで、共有鍵を非常に小さな部分群に限定させ、総当たりで復元できるようにします。

第5章：ハッシュ関数と MAC への攻撃

5.1 ハッシュ関数への攻撃

5.1.1 衝突攻撃（Collision Attack）

H(M₁) = H(M₂) となる異なる2つのメッセージ M₁ ≠ M₂ を見つけます。n ビットのハッシュに対して、誕生日攻撃の計算量は約 2^(n/2) です。

⚠️ MD5 の衝突： MD5 は128ビットのハッシュで、理論上の安全性は64ビット相当です。しかし Wang Xiaoyun が2004年に実用的な MD5 の衝突手法を発見し、現在では秒単位で衝突を生成できます。

5.1.2 長さ拡張攻撃（Length Extension Attack）

Merkle-Damgård 構造のハッシュ（MD5、SHA-1、SHA-256 など）に対する攻撃です。H(secret || message) と message の長さが分かっていれば、secret を知らなくても H(secret || message || padding || append) を計算できます。

💡 影響を受ける： MD5, SHA-1, SHA-224, SHA-256, SHA-384, SHA-512 影響を受けない： SHA-3 (Keccak), BLAKE2, HMAC

# hashpumpy で Length Extension Attack を行う
import hashpumpy
new_hash, new_data = hashpumpy.hashpump(
    original_hash, original_data, 
    data_to_append, key_length
)

5.1.3 ハッシュ長さ拡張の CTF での悪用

自作の MAC 構築 MAC = H(secret || message) でよく見られます。攻撃者は次のことができます。

1. 正当なリクエスト (message, MAC) を傍受します。
2. 新しいメッセージ message' = message || padding || evil_command を構成します。
3. secret を知らなくても新しい MAC' を計算します。
4. サーバーが MAC' の検証を通過し、evil_command を実行します。

5.1.4 プレフィックス衝突攻撃

2つのメッセージ M₁ と M₂ を構成し、任意のプレフィックス P に対して H(P || M₁) = H(P || M₂) となるようにします。MD5 には実用的なプレフィックス衝突ツール（HashClash など）があります。

5.2 MAC への攻撃

5.2.1 HMAC の安全性

HMAC は安全な MAC 構築です：HMAC(K, M) = H((K' ⊕ opad) || H((K' ⊕ ipad) || M))。長さ拡張攻撃の影響を受けません。

5.2.2 タイミング攻撃（Timing Attack on MAC Comparison）

サーバーが == で MAC を1バイトずつ比較し、不一致時に早期に失敗を返す場合、比較時間から最初に一致しなかったバイトの位置が漏れます。攻撃者は正しい MAC を1バイトずつ推測できます。

✅ 防御： 定数時間の比較関数（hmac.compare_digest や crypto.timing_safe_equal など）を使います。

5.2.3 CBC-MAC への攻撃

単純な CBC-MAC（メッセージを CBC 暗号化して最後のブロックを取る方式）には複数の攻撃があります。

• メッセージ拡張： M の MAC が T であるとき、M || (T ⊕ M_next) の MAC が予測できます。
• 並べ替え攻撃： 同じ鍵で CBC 暗号化と CBC-MAC の両方を行うと、重大なセキュリティ問題が存在します。

✅ 安全な変種： CMAC、OMAC、PMAC など。

5.3 パスワードハッシュへの攻撃

5.3.1 レインボーテーブル攻撃

ソルトなしのパスワードハッシュに対する攻撃です。大量のハッシュチェーンを事前計算し、時間を空間に置き換えることで、短時間でハッシュ値を逆引きできます。

✅ 防御： ランダムなソルト（salt）と低速なハッシュ関数（bcrypt、scrypt、Argon2 など）を使います。

5.3.2 パスワードハッシュ比較のタイミング攻撃

MAC のタイミング攻撃と同様に、パスワードハッシュの比較が定数時間でない場合、情報が漏れる可能性があります。

第6章：暗号プロトコルへの攻撃

6.1 Diffie-Hellman 鍵交換への攻撃

6.1.1 小群攻撃（Small Subgroup Attack）

攻撃者が一方に低次の元を送り、共有鍵を小さな部分群に限定させます。実装が受け取った元の位数を検証しない場合、共有鍵を総当たりできます。

6.1.2 Logjam 攻撃

2015年に発見された攻撃で、512ビット以下の弱い DH パラメータを使う TLS 接続を狙います。512ビット素体上の離散対数を事前計算しておくことで、リアルタイムに接続をダウングレードし、セッション鍵を復元できます。

6.1.3 悪意あるパラメータ攻撃

攻撃者が DH パラメータを制御できる場合、離散対数が容易に計算できる特殊な p（p-1 が小さな素因子しか持たないなど）を選べます。

6.2 TLS/SSL への攻撃

6.2.1 BEAST 攻撃

TLS 1.0 の CBC モードに対する攻撃です。IV の予測可能性（IV＝直前の暗号文ブロック）を利用し、選択平文攻撃によって Cookie を1バイトずつ復元します。

6.2.2 CRIME 攻撃

TLS 圧縮（DEFLATE）の副作用を利用します。攻撃者は平文の一部を制御し、圧縮後の暗号文の長さの変化を観察することで、機密情報（Cookie など）を1バイトずつ復元します。

6.2.3 BREACH 攻撃

CRIME の HTTP 層における変種で、HTTP レスポンスの圧縮を狙います。TLS 圧縮が無効化されていても、HTTP 圧縮は依然として悪用できます。

6.2.4 POODLE 攻撃

SSL 3.0 のパディング Oracle に対する攻撃です。SSL 3.0 がパディングを検証しない弱点を利用し、JavaScript と組み合わせて HTTPS リクエスト中の機密データを1バイトずつ復号します。

6.2.5 Heartbleed

主には実装上の脆弱性ですが、暗号プロトコル実装における深刻な問題です。OpenSSL のハートビート拡張が境界チェックを行っていなかったため、サーバーのメモリ上の秘密鍵やパスワードなどの機密情報を読み出せました。

6.3 リプレイ攻撃と中間者攻撃

6.3.1 リプレイ攻撃（Replay Attack）

正当なメッセージを傍受して再送します。防御方法には、タイムスタンプ、乱数（nonce）、シーケンス番号、ワンタイムトークンなどがあります。

6.3.2 中間者攻撃（Man-in-the-Middle）

攻撃者が通信する双方の間に割り込み、メッセージを改竄する可能性があります。認証を行わない場合（DH のみを使い公開鍵を検証しないなど）、MITM 攻撃に対して脆弱です。

6.4 ゼロ知識証明への攻撃

6.4.1 Fiat-Shamir ヒューリスティックの不適切な使用

対話型ゼロ知識証明を非対話型に変換する際、チャレンジ値をハッシュで計算せず固定または予測可能な値にすると、攻撃者は証明を偽造できます。

第7章：エンコーディング、ステガノグラフィ、その他

7.1 エンコーディングの一族

7.1.1 Base シリーズ

エンコーディング	特徴	識別方法
Base64	A-Z, a-z, 0-9, +/, = パディング	よくある、= で終わる
Base32	A-Z, 2-7, = パディング	すべて大文字または数字
Base16 (Hex)	0-9, A-F	純粋な16進数
Base58	ビットコインアドレス、0/O/I/l を含まない	紛らわしい文字がない
Base85 (Ascii85)	!, -, ~ などの文字	<~ ~> で囲まれる
Base91	拡張 ASCII 文字集合	よりコンパクト
Base100	Emoji 絵文字	すべて emoji

7.1.2 URL エンコーディング / HTML 実体参照エンコーディング

URL エンコーディングは %XX 形式を使い、HTML 実体参照は &#DD; または &name; を使います。

7.1.3 Unicode ステガノグラフィ

• ゼロ幅文字： ゼロ幅スペース（U+200B）、ゼロ幅非接合子（U+200C）、ゼロ幅接合子（U+200D）を使って情報を隠せます。
• 同形異義文字： 異なる Unicode 文字で似た字形を表します（Cyrillic の а と Latin の a など）。
• 不可視文字： 右から左へのマーク（U+202E）などの制御文字。

7.2 ステガノグラフィ（Steganography）

7.2.1 LSB ステガノグラフィ（Least Significant Bit）

画像のピクセル値の最下位ビットに情報を隠します。24ビット BMP 画像では、各ピクセルに3ビットの情報を隠せます。

💡 検出： Chi-Square 検定、RS 分析、視覚的攻撃（LSB プレーンを表示する）。

7.2.2 音声ステガノグラフィ

• LSB 音声： 画像の LSB と同様に、サンプル値の最下位ビットを変更します。
• スペクトルステガノグラフィ： 周波数領域に情報を埋め込み、FFT/DFT 変換後に係数を変更します。
• エコーステガノグラフィ： エコーを導入して情報を符号化します。

7.2.3 ファイル形式のステガノグラフィ

• データの追記： ファイル末尾にデータを付加します（画像の後に zip を付けるなど）。
• ファイルの連結： ファイル形式の寛容性を利用し、複数形式のファイルを構成します。
• EXIF データ： 画像のメタデータに情報を隠します。

7.3 よくある CTF エンコーディングパズル

7.3.1 マンチェスター符号 / 差動マンチェスター符号

デジタル通信における回線符号で、CTF では波形やビット列の形で出題されることがあります。

7.3.2 回線符号の識別

エンコーディング	特徴
NRZ	高=1, 低=0
NRZI	レベル反転=1, 変化なし=0
Manchester	立ち上がりエッジ=0, 立ち下がりエッジ=1（またはその逆）
Differential Manchester	ビット開始位置で反転=0, 反転なし=1

7.3.3 基数変換と独自エンコーディング

CTF では独自の基数や混合エンコーディングがよく出題されます。たとえば：

• 文字列を2進数に変換してから、区切り直して解釈する。
• 非標準の文字集合を使って置換する。
• 多層にネストしたエンコーディング（Base64 → Hex → Base32 → ...）。

第8章：サイドチャネルと実装への攻撃

8.1 タイミング攻撃（Timing Attack）

操作の実行時間を精密に測定することで鍵の情報を推測します。Kocher が1996年に最初に提唱しました。

8.1.1 平方乗算の冪剰余に対するタイミング攻撃

冪剰余演算の平方乗算法では、鍵ビットが1のときに乗算を実行し、0のときは実行しません。時間差を測定することで鍵を1ビットずつ復元できます。

✅ 防御： 定数時間アルゴリズム（always square-and-multiply）、Montgomery ladder、ブラインディング技術。

8.2 キャッシュ攻撃（Cache Attack）

8.2.1 Flush+Reload

CPU キャッシュの共有特性を利用します。攻撃者は：

1. 対象のメモリ行をキャッシュからフラッシュします。
2. 対象プロセスの実行を待ちます。
3. リロードしてアクセス時間を測定します。時間が短ければ、対象プロセスがそのメモリ行にアクセスしたことを意味します。

8.2.2 Prime+Probe

攻撃者は自分のデータでキャッシュセットを埋め（prime）、対象の実行を待ってから、自分のデータへの再アクセス時間を測定します（probe）。時間が長くなれば、対象がそのキャッシュセットにアクセスしたことを意味します。

8.3 消費電力分析（Power Analysis）

8.3.1 単純消費電力分析（SPA）

消費電力のトレースを直接観察し、異なる操作（乗算と加算など）を識別します。RSA の平方乗算法では、SPA によって鍵ビットがはっきりと見えます。

8.3.2 差分消費電力分析（DPA）

大量の消費電力トレースを収集し、統計的手法（差分など）で鍵に関連する情報を抽出します。ノイズが大きくても有効に機能します。

8.4 故障注入（Fault Injection）

8.4.1 電圧/クロックグリッチ

電源電圧やクロック周波数を瞬間的に変化させ、プロセッサに命令をスキップさせたり誤った結果を生じさせたりします。

8.4.2 RSA 故障攻撃

CRT-RSA の復号過程で、一方の素数の法の下での計算が誤ると（m_p は正しいが m_q が誤っているなど）、誤った結果 m' は m' ≡ m mod p だが m' ≢ m mod q を満たすため、gcd(m'ᵉ - c, n) が因子の情報を漏らす可能性があります。

8.4.3 AES 故障攻撃

AES の最終ラウンドに故障を注入すると、最終ラウンドの副鍵を復元できます。特定のラウンドに故障を注入することで、すべてのラウンド鍵を1ラウンドずつ復元できます。

第9章：ポスト量子暗号と最先端の攻撃

9.1 量子計算が暗号学に与える脅威

9.1.1 Shor のアルゴリズム

量子アルゴリズムで、整数分解と離散対数問題を多項式時間で解けます。n ビットの整数に対して、Shor のアルゴリズムは約 O(n³) の量子ゲート操作と O(n) の量子ビットを必要とします。

⚠️ 影響： RSA、DSA、ECDSA、ECDH、DH など、整数分解や離散対数に基づくすべての暗号システム。

9.1.2 Grover のアルゴリズム

量子探索アルゴリズムで、総当たり探索の計算量を O(N) から O(√N) に下げられます。共通鍵暗号にとっては、実効鍵長が半分になることを意味します（AES-256 が AES-128 程度に落ちるなど）。

9.2 ポスト量子暗号（PQC）

9.2.1 格子暗号（Lattice-Based）

格子上の困難問題に基づきます：最短ベクトル問題（SVP）と最近ベクトル問題（CVP）。代表的なアルゴリズム：NTRU、Kyber、Dilithium。

💡 格子攻撃： LLL アルゴリズムや BKZ アルゴリズムは格子基底縮小に使われます。CTF では低次元格子上の隠れた数問題（HNP）や近似 CVP 問題に出会うことがあります。

9.2.2 符号暗号（Code-Based）

誤り訂正符号の困難問題に基づきます。代表的なアルゴリズム：McEliece、Classic McEliece。

9.2.3 多変数暗号（Multivariate）

有限体上の多変数二次方程式系を解くことの困難性に基づきます。代表的なアルゴリズム：Rainbow、UOV。

9.2.4 ハッシュ署名（Hash-Based）

ハッシュ関数の安全性に基づきます。代表的なアルゴリズム：Lamport、Winternitz、SPHINCS+。

9.3 格子暗号への CTF 攻撃

9.3.1 隠れた数問題（Hidden Number Problem, HNP）

tᵢ と MSB_k(tᵢ·x mod p) が与えられたとき、x を復元します。格子上の CVP 問題に変換できます。

9.3.2 ECDSA への格子攻撃

ECDSA 署名における nonce k に偏りがある場合（最上位ビットが既知など）、格子を構成して LLL を用いることで秘密鍵を復元できます。

# SageMath: ECDSA nonce bias lattice attack
# 複数の署名の (h, r, s) が既知で、k の一部のビットが既知と仮定
M = Matrix(ZZ, [...])  # 格子を構築
L = M.LLL()
# 短ベクトルに秘密鍵の情報が含まれる

9.4 準同型暗号への攻撃

9.4.1 ノイズ管理への攻撃

部分的準同型暗号（Paillier など）や完全準同型暗号（FHE）はノイズ管理に依存しています。ノイズの増加がしきい値を超えると、復号結果が誤ります。

9.4.2 鍵復元攻撃

一部の準同型暗号方式では、特定のパラメータ選択の下で鍵復元の脆弱性が存在する可能性があります。

第10章：CTF 実戦のツールチェーンとクイックリファレンス

10.1 必須ツール

ツール	用途	リンク/コマンド
SageMath	数学計算、格子基底縮小、数論	sage
Python + gmpy2	大きな整数の演算、剰余演算	pip install gmpy2
PyCryptodome	暗号ライブラリ	pip install pycryptodome
openssl	証明書、暗号化・復号	openssl
hashcat	パスワードハッシュの解読	hashcat
John the Ripper	パスワード解読	john
zsteg	PNG/BMP の LSB ステガノグラフィ	gem install zsteg
steghide	音声/画像のステガノグラフィ	steghide
binwalk	ファイルの抽出、解析	binwalk -e file
foremost	ファイルの復元	foremost -i file
RsaCtfTool	RSA 攻撃の自動化	github.com/Ganapati/RsaCtfTool
factordb	オンラインの因子データベース	factordb.com
Alpertron ECM	オンラインの整数分解	alpertron.com.ar/ECM.HTM
CyberChef	エンコーディング変換の万能ツール	gchq.github.io/CyberChef
hashpumpy	ハッシュ長さ拡張攻撃	pip install hashpumpy
pwntools	CTF の対話とエクスプロイト	pip install pwntools

10.2 RSA 攻撃の決定木

n, e, c が与えられた:
│
├─ n は素因数分解できる？
│  ├─ はい → φ(n) を直接計算し、d を求めて復号
│  └─ いいえ → 次へ
│
├─ e が小さい？（e=3 など）
│  ├─ はい → 直接開平、放送攻撃、Franklin-Reiter を試す
│  └─ いいえ → 次へ
│
├─ 複数の (n,e) の組があり、n に共通因子がある？
│  ├─ はい → GCD 攻撃で n を分解
│  └─ いいえ → 次へ
│
├─ e/n の連分数の収束子に k/d がある？
│  ├─ はい → Wiener 攻撃
│  └─ いいえ → 次へ
│
├─ 平文の一部が既知？
│  ├─ はい → Coppersmith 法
│  └─ いいえ → 次へ
│
├─ Padding Oracle がある？
│  ├─ はい → Bleichenbacher 攻撃
│  └─ いいえ → より高度な格子法が必要かもしれない

10.3 よくある CTF Crypto 問題のクイックリファレンス

問題の特徴	攻撃の考え方	ツール/スクリプト
暗号文が与えられ、古典暗号のヒントがある	頻度分析、Kasiski、IoC	Python スクリプト
n, e, c が与えられ、e が小さい	小さな e 攻撃、放送攻撃	gmpy2.iroot, crt
複数の n が与えられる	GCD 攻撃、共通 modulus 攻撃	math.gcd
e, n が与えられ、e が大きい	Wiener 攻撃、Boneh-Durfee	SageMath + LLL
暗号化 Oracle が与えられる	Padding Oracle、選択平文	pwntools
ハッシュ値と長さ拡張のヒントが与えられる	長さ拡張攻撃	hashpumpy
画像/音声ファイルが与えられる	LSB、スペクトル、EXIF、データ追記	zsteg, binwalk, steghide
ECC のパラメータと点が与えられる	BSGS、Pohlig-Hellman、MOV	SageMath
ECDSA の署名ペアが与えられる	Nonce 再利用、格子攻撃	SageMath
多層エンコーディング	1層ずつデコード	CyberChef

10.4 Python クイックリファレンスコード集

10.4.1 拡張ユークリッドアルゴリズム

def egcd(a, b):
    if a == 0:
        return (b, 0, 1)
    else:
        g, y, x = egcd(b % a, a)
        return (g, x - (b // a) * y, y)

def modinv(a, m):
    g, x, y = egcd(a, m)
    if g != 1:
        raise Exception('modular inverse does not exist')
    else:
        return x % m

10.4.2 中国剰余定理

def crt(a, m):
    # a: 剰余のリスト, m: 法のリスト
    from functools import reduce
    M = reduce(lambda x, y: x*y, m)
    result = 0
    for ai, mi in zip(a, m):
        Mi = M // mi
        result += ai * Mi * pow(Mi, -1, mi)
    return result % M

10.4.3 高速な素因数分解の試み

from sympy import factorint, isprime
from gmpy2 import isqrt, gcd

def factor_small(n):
    # 小さな因子で試し割り
    for p in [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31]:
        while n % p == 0:
            return p
    return None

def fermat_factor(n):
    a = isqrt(n) + 1
    b2 = a*a - n
    while not is_square(b2):
        a += 1
        b2 = a*a - n
    b = isqrt(b2)
    return (a+b, a-b)

10.4.4 楕円曲線の基本演算（SageMath）

# 曲線を定義
p = ...  # 素体
a, b = ..., ...  # 曲線パラメータ
E = EllipticCurve(GF(p), [a, b])

# 点を定義
P = E(x, y)
n = P.order()  # 点の位数

# BSGS
Q = d*P  # 既知
k = discrete_log(Q, P, operation='+')

結び

🎯 暗号攻撃は絶えず進化し続ける分野です。古典暗号の頻度分析から、現代 RSA の格子攻撃、そして量子計算がもたらすパラダイムシフトまで、あらゆる攻撃手法は暗号実装に潜む弱点を明らかにしてくれます。CTF 競技会でこれらの攻撃技術を身につけることは、問題を素早く解く助けになるだけでなく、暗号の設計原理とセキュリティ境界を深く理解することにもつながります。

覚えておいてください： 最良の防御は攻撃を理解することです。攻撃手段を深く身につけてこそ、本当に安全な暗号システムを設計できます。

— CTF の戦場での健闘を祈ります！🏁