ctf-crypto

CTF 暗号技術

CTF の暗号技術チャレンジ向けクイックリファレンスです。各手法の概要を一行で説明しています。コードを含む詳細については、関連ファイルを参照してください。

前提条件

Python パッケージ（全プラットフォーム）：

pip install pycryptodome z3-solver sympy gmpy2 hashpumpy fpylll py_ecc
# Coppersmith (optional): pip install coppersmith
# Alternative Coppersmith lib: git clone https://github.com/jvdsn/crypto-attacks ~/.ctf-tools/crypto-attacks && pip install -r ~/.ctf-tools/crypto-attacks/requirements.txt

Linux（apt）：

apt install hashcat

macOS（Homebrew）：

brew install hashcat

手動インストール：

• SageMath（任意 — レガシーな Sage フォールバックのスニペット（折りたたみセクション）でのみ使用）— Linux：apt install sagemath、macOS：brew install --cask sage
• RsaCtfTool — git clone https://github.com/RsaCtfTool/RsaCtfTool（RSA 攻撃を自動化）
• crypto-attacks（Coppersmith）— git clone https://github.com/jvdsn/crypto-attacks ~/.ctf-tools/crypto-attacks + pip install -r ~/.ctf-tools/crypto-attacks/requirements.txt（pip install coppersmith の代替）

注： gmpy2 には libgmp が必要です — Linux：apt install libgmp-dev、macOS：brew install gmp。

追加リソース

• classic-ciphers.md - 古典暗号：Vigenere（＋Kasiski 検定）、Atbash、換字ホイール、XOR の各種方式（＋複数バイトの頻度分析）、決定論的 OTP、カスケード XOR、ブック暗号、OTP 鍵の再利用／多重パッド、可変長同音換字、格子置換暗号の鍵空間削減、画像ベースの Caesar シフト暗号、ファイル形式のヘッダーを利用した XOR 鍵の復元
• modern-ciphers.md - 現代暗号への攻撃：AES（CFB-8、ECB の漏えい）、CBC-MAC/OFB-MAC、パディングオラクル、S-box の衝突、GF(2) 消去法、LCG の部分出力復元、合成法の法上のアフィン暗号、導出鍵を使った AES-GCM、AES-GCM のノンス再利用（禁止されている攻撃）、Ascon 系の縮約ラウンド差分解読、独自線形 MAC の偽造、CBC パディングオラクル（全ブロックの復号）、Bleichenbacher RSA PKCS#1 v1.5 パディングオラクル（ROBOT）、誕生日攻撃／中間者攻撃、CRC32 衝突を利用した署名偽造、ゼロ化オラクルによるバイト単位の AES 鍵復元、エラーメッセージ復号オラクルによる AES-CBC 暗号文の偽造
• modern-ciphers-2.md - 現代暗号への攻撃（第 2 部）：Blum-Goldwasser ビット拡張オラクル、ハッシュの長さ拡張、圧縮オラクル（CRIME 型）、サイクル検出によるハッシュ関数の時間逆転、OFB モードの可逆 RNG を使った逆方向復号、公開鍵ハッシュ XOR による脆弱な鍵導出、HMAC-CRC の線形性攻撃、OFB モードでの DES 弱鍵、SRP プロトコルのバイパス、改変 AES S-Box の総当たり、縮約ラウンド AES への square 攻撃、AES-ECB のバイト単位選択平文攻撃、AES-ECB のカットアンドペーストによるブロック操作、AES-CBC IV のビット反転による認証バイパス、Rabin LSB パリティオラクル、PBKDF2 の事前ハッシュバイパス、fastcol による MD5 マルチ衝突
• modern-ciphers-3.md - 現代暗号への攻撃（第 3 部）：独自ハッシュ状態の逆転、小さなペイロードに対する CRC32 の総当たり、ノイズを含む RSA LSB オラクルの誤り訂正、スポンジハッシュの MITM 衝突、CBC IV の偽造＋ブロック切り詰め、パディングオラクルから CBC ビット反転 RCE への攻撃、SPN S-box の交差攻撃、タイムスタンプをシードにした PRNG からの AES-CFB IV 復元、3 ラウンド XOR プロトコルの鍵相殺、AES-CBC UnicodeDecodeError サイドチャネルオラクル、XOR 集約ハッシュバイパスのための SHA-256 基底攻撃、XOR ブロック相殺による独自 MAC の偽造、XOR＋加算演算による HMAC 鍵の復元
• modern-ciphers-4.md - 現代暗号への攻撃（第 4 部）：$2^{130}-5$ 上の ChaCha20-Poly1305 ノンス再利用の禁止攻撃（RFC 8439、CTR $C_1\oplus C_2=P_1\oplus P_2$、galois/sympy による Poly1305 $\sum c_i r^{n-i}$、$ad=""$ の 2 メッセージベクトル）、分割格子を使った分割オラクル／鍵コミット型 AEAD、スポンジの一般性（SHA-3/Keccak の $0x06$ 対 $0x01$、Ascon/Gimli/Sparkle のレート／容量／ラウンド／パディング表＋エンディアンのワークフロー）、eSTREAM Trivium の 1152 ラウンドのウォームアップと立方体攻撃の概要（Grain）
• stream-ciphers.md - ストリーム暗号への攻撃：LFSR（Berlekamp-Massey、相関攻撃、既知平文、Galois 対 Fibonacci、自己相関による Galois タップの復元）、RC4 の第 2 バイトバイアス、連続するバイトの XOR 相関
• rsa-attacks.md - RSA への攻撃：小さな e（立方根）、共通法、Wiener 攻撃、Pollard の p-1 法、Hastad ブロードキャスト攻撃、線形パディングを使った Hastad 攻撃（Coppersmith）、Franklin-Reiter 関連メッセージ攻撃（e=3）、Coppersmith による線形関係にある素数への攻撃、Fermat 法／連続する素数、マルチプライム、数字制限、Coppersmith による構造化素数への攻撃、Manger オラクル、多項式ハッシュ
• rsa-attacks-2.md - RSA への攻撃（特殊な攻撃）：RSA の p=q 検証バイパス、cube root と CRT で gcd(e,phi)>1 の場合、phi(n) の倍数からの因数分解、乗法準同型性を使った署名偽造、基数表現による脆弱な鍵生成、gcd(e,phi)>1 の RSA における指数の縮約、バッチ GCD による共通素因数の因数分解、dp/dq/qinv からの部分鍵復元、RSA-CRT 故障攻撃、準同型復号オラクルのバイパス、小さな素数による CRT 分解、Montgomery 還元のタイミング攻撃、Bleichenbacher による低指数署名偽造、e=1 と細工した法による RSA 署名バイパス
• ecc-attacks.md - ECC への攻撃：小部分群、不正曲線、Smart 攻撃（異常曲線、Sage コード付き）、フォールトインジェクション、clock group DLP、Pohlig-Hellman、ECDSA のノンス再利用、Ed25519 のトーションサイドチャネル、DSA のノンス再利用、k 生成時の MD5 衝突による DSA 鍵復元、X25519 の低位点＋全ゼロチェック
• dh-attacks.md - 古典的な有限体 DH：自明な g（0/1/p-1）、p-1 が平滑な場合の Pohlig-Hellman、小部分群への拘束／CRT による Lim-Lee 静的鍵復元、静的鍵と一時鍵の違い＋Logjam ダウングレードのトリアージ
• zkp-and-advanced.md - ZKP／グラフ 3 彩色、Z3 ソルバーガイド、ガーブルド回路、Shamir SSS、バイグラム制約の求解、競合状態、Groth16 のセットアップ破損、DV-SNARG 偽造、順列復元のための KZG ペアリングオラクル、Shamir SSS で再利用された多項式係数
• prng.md - PRNG への攻撃（基礎編）：MT19937、トークン予測のための GF(2) マジック行列による MT の浮動小数点数の復元、LCG、GF(2) 行列 PRNG、Z3 による V8 XorShift128+ Math.random の状態復元、ミドルスクエア法、決定論的 RNG の山登り法、ランダムモードオラクル、時刻ベースのシード、ctypes による C srand/rand の同期、パスワードクラッキング、ロジスティック写像のカオス PRNG
• prng-attacks.md - PRNG への攻撃（CTF 時代、2017 年以降）：部分和による MT シード復元、MT19937 の制約伝播、Z3 による Rule 86 セルオートマトンの逆転、Java LCG の部分 modulo 中間一致攻撃、モジュラー逆元による LCG の逆方向ステップ、LFSR のビット折り畳みによる ASCII パリティ、Z3 の求解時間タイミングオラクル、randcrack による DSA k の予測、フォーマット文字列による PRNG シードオフセット、NTP に汚染された PRNG UUID XOR
• historical.md - 歴史的暗号（Lorenz SZ40/42、ブック暗号の実装）
• advanced-math.md - 高度な数学的攻撃（同種写像、Pohlig-Hellman、一般的な DLP に対するベビーステップ・ジャイアントステップ（BSGS）、LLL、LLL による Merkle-Hellman ナップサック、Howgrave-Graham による Coppersmith hg_matrix -> IntegerMatrix -> LLL -> sympy Poly（beta=0.5、モニック判定、dim>100 では flatter を任意で使用）、四元数 RSA、GF(2)[x] CRT、S-box 衝突コード、LWE 格子 CVP 攻撃、素数でない法上のアフィン暗号、GF(2) 線形代数による内省的 CRC）
• lattice-and-lwe.md - 格子攻撃のトリアージとワークフロー：LLL/BKZ/Babai、部分的または偏ったノンスからの HNP、切り詰められた LCG 状態の復元、LWE の埋め込みと CVP、Ring-LWE／Module-LWE の識別、NTRU 格子 B=[[qI 0],[H I]]（ネガサイクリック、BKZ、中心化した g）、GGH 埋め込み [[B 0],[c lambda]] での lambda 探索、Mersenne AJPS p=2^n-1 n=11213 w=10 6x6 s=5、BDD の述語／LadderLeak（署名 100 件超、1～4 ビット）、直交格子、部分和／ナップサック、よくある失敗パターン
• post-quantum.md - 耐量子暗号の識別：ML-KEM（Kyber）k=2/3/4 q=3329 etau dv、ML-DSA、Falcon、Module-LWE の平坦化、FO 故障オラクル、NTT、Kannan/Bai-Galbraith/Arora-Ge/estimator の判断木、Mersenne AJPS の詳細
• exotic-crypto.md - 風変わりな代数構造（組紐群 DH／Alexander 多項式、単調関数の反転、トロピカル半環の剰余、Paillier 暗号系、ハミング符号の螺旋インターリーブ、ElGamal の普遍再暗号化、FPE Feistel の総当たり、二十面体対称群暗号、Goldwasser-Micali の複製オラクル）
• exotic-crypto-2.md - 風変わりな代数構造（第 2 部、2017 年以降）：BB-84 QKD MITM、ElGamal の自明な DLP（B=p-1）、準同型な倍加による Paillier LSB オラクル、差分プライバシーのノイズ相殺、準同型暗号のビット抽出、Jordan 標準形による行列上の ElGamal、Pollard による OSS 署名偽造、秘密鍵なしでの Cayley-Purser 復号、BIP39 の部分ニーモニックチェックサム総当たり、Asmuth-Bloom CRT しきい値復元、多項式素数を使った Rabin、LCG 周期検出、Vandermonde 多項式係数の復元

---

切り替えの判断

• 本当の障害がバイナリ、難読化されたクライアント、または特殊な VM の理解である場合は、/ctf-reverse に切り替えてください。
• 復号を始める前のパケットの切り出し、ディスクの復旧、またはステガノグラフィーの抽出が課題の大部分を占める場合は、/ctf-forensics に切り替えてください。
• 暗号の部分を解いた後、脆弱なネットワークサービスに対するエクスプロイトを実装するだけのタスクである場合は、/ctf-pwn または /ctf-web に切り替えてください。
• 暗号の課題に敵対的機械学習、モデル抽出、またはニューラルネットワークベースの暗号が含まれる場合は、/ctf-ai-ml に切り替えてください。
• 実際には真の暗号解読ではなく、エンコーディングパズル、難解暗号、またはポリグロットのトリックが課題である場合は、/ctf-misc に切り替えてください。

クイックスタートコマンド

# Identify cipher type
python3 -c "from Crypto.Util.number import *; n=<N>; print(f'bits={n.bit_length()}')"

# RSA quick check
python3 -c "from sympy import factorint; print(factorint(<n>))"  # Small factors?
openssl rsa -pubin -in key.pub -text -noout  # Extract n, e from PEM

# Quick factorization tools
python3 RsaCtfTool.py -n <n> -e <e> --uncipher <c>

# XOR analysis
python3 -c "from pwn import xor; print(xor(bytes.fromhex('<hex>'), b'flag{'))"

# Hash identification
hashid '<hash>'
hashcat --identify '<hash>'

# Quick factorization (sympy, primary)
python3 -c "from sympy import factorint; print(factorint(<n>))"
# Sage alternative: sage -c "print(factor(<n>))"

古典暗号

• シーザー暗号: 頻度分析、または26個の鍵を総当たり
• ヴィジュネル暗号: フラグ形式のプレフィックスを使った既知平文攻撃で、(ct - pt) mod 26 から鍵を導出します。鍵長が不明な場合はカシスキ検定を使用します（繰り返しパターンの距離の GCD）。
• Atbash: A<->Z の置換です。チャレンジ名に「Abashed」のヒントがないか確認します。
• 換字ホイール: 内側と外側のアルファベットの対応関係について、すべての回転を総当たりします。
• マルチバイト XOR: 暗号文を鍵の位置ごとに分割し、各列を個別に頻度分析します。英語の文字頻度に基づいてスコア付けします（スペース = 0x20）。
• カスケード XOR: 最初のバイトを総当たりします（256回の試行）。残りは決定論的に続きます。
• XOR 回転（2のべき乗）: 偶数ビットと奇数ビットは混ざらないため、候補となる状態は4つだけです。
• 弱い XOR 検証: 1バイト XOR チェックの通過率は 1/256 です。十分な予算があれば総当たりします。
• 決定論的 OTP: 既知平文 XOR でキーストリームを復元し、負荷分散されたバックエンドを照合します。
• OTP 鍵の再利用（多数回パッド）: C1 XOR C2 XOR known_P = unknown_P。既知の平文がない場合は、クリブドラッギングを行います。
• 同音換字（可変長）: 複数文字の暗号文グループが単一の平文文字に対応します。サブ n-gram の頻度が同一の n-gram を見つけ、記号に置き換えてから単一アルファベット換字として解読します。classic-ciphers.md を参照してください。
• グリッド転置暗号: 行と列を独立して並べ替える 5x5 グリッドでは、鍵空間は 5! x 5! = 14,400 に縮小されます。ミリ秒単位で総当たりできます。classic-ciphers.md を参照してください。
• 画像ベースのシーザーシフト: ピクセルの行または列を帯ごとのオフセットでシフトします。元の画像とシフト後の画像を比較し、シフト量から ASCII エンコードされたフラグを抽出します。classic-ciphers.md を参照してください。
• ポリュビオスの正方形暗号: 5x5 グリッドで文字のペアを平文に対応させます。数字や座標が位置を符号化します。classic-ciphers.md を参照してください。
• ファイル形式ヘッダーを利用した XOR 鍵の復元: ファイルは PDF/PNG/ZIP を名乗っているのに、file が「data」と報告する場合があります。先頭のバイトを想定されるマジックバイトと XOR して、繰り返し鍵を導出します。末尾の構造（%%EOF、IEND マーカー）を使って鍵を延長します。classic-ciphers.md を参照してください。

コード例の全体については、classic-ciphers.md を参照してください。

現代暗号の攻撃

• AES-ECB： ブロックのシャッフル、バイト単位の選択平文によるサフィックス復元（1バイトあたり256回のクエリ、ツール：FeatherDuster ecb_cpa_decrypt）；画像のECBは視覚的なパターンを保持します。ECBのカットアンドペースト：暗号文ブロックをつなぎ合わせ、JSONフィールド（例：is_admin: true）を偽造します。modern-ciphers-2.mdを参照してください。
• AES-CBC： ビットフリッピングで平文を変更し、パディングオラクルで鍵なしに復号します。IVのビットフリップ：IVの特定のビットを反転させ、最初の平文ブロックを変更します（MACは不要です）。modern-ciphers-2.mdを参照してください。
• CBCのIV偽造＋ブロック切り詰め： IVのバイトをXORして復号後のブロック0を変更し、末尾の暗号文ブロックを削除します（CBCには長さの完全性検証がありません）。MACが暗号文に埋め込まれている場合、認証済みトークンを偽造できます。modern-ciphers-3.mdを参照してください。
• パディングオラクルからCBCビットフリップによるRCE： パディングオラクル（平文を復元）とCBCのビットフリッピング（シェルのメタ文字を挿入）を組み合わせ、暗号化パラメーター経由のコマンドインジェクションを実現します。modern-ciphers-3.mdを参照してください。
• AES-CFB-8： 8ビットのフィードバックと固定IVにより、既知の16バイトを使って状態を再構築できます
• CBC-MAC/OFB-MAC： XORキーストリームによる署名偽造：new_sig = old_sig XOR block_diff
• Sボックスの衝突： 非置換Sボックス（len(set(sbox)) < 256）では、4,097回のクエリで鍵を復元できます
• GF(2)消去法： 線形ハッシュ関数（XOR＋ローテーション）は、GF(2)上のガウス消去法で解けます
• パディングオラクル： 直前のブロックを変更し、パディングの有効性を検査することで、バイト単位に復号します
• LFSRストリーム暗号： Berlekamp-Massey法で2Lビットのキーストリームからフィードバック多項式を復元できます。相関攻撃では、偏りのある結合関数を持つ複合生成器を破れます
• ガロアLFSRのタップ復元： 既知のファイルヘッダー（PNG/PDF/ZIP）と暗号文をXORしてキーストリームを取得します。Nビットのウィンドウに分割し、LSB=1の遷移について(state >> 1) XOR next_stateを計算すると、タップマスクを直接復元できます。自己相関をスライドさせて正しい長さを見つけます。stream-ciphers.mdを参照してください。
• 可逆RNGを使ったOFB： どのブロックでも既知平文があればRNGの状態が漏えいします。状態遷移が全単射なら、RNGを逆向きに実行してすべてのブロックを復号できます。modern-ciphers-2.mdを参照してください。
• 脆弱な鍵導出（公開鍵ハッシュのXOR）： SHA256(public_key) XOR seedから導出されるAES鍵は、秘密鍵なしで完全に復元できます。「ハイブリッド」RSA+AESでも安全性は得られません。modern-ciphers-2.mdを参照してください。
• HMAC-CRCの線形性： CRCはGF(2)上で線形であるため、HMAC-CRC鍵は1組のメッセージとMACから、多項式演算を使って復元できます。modern-ciphers-2.mdを参照してください。
• OFBにおけるDESの弱鍵： DESの弱鍵4個では暗号化が自己逆になります。OFBのキーストリームは周期2で繰り返されるため、16バイトの繰り返しXORに帰着します。modern-ciphers-2.mdを参照してください。
• スクエア攻撃（ラウンド数を削減したAES）： 4ラウンドAESは積分暗号解析で破れます。256個の平文からなるラムダ集合を使い、XOR和が0になる判別法によって最終ラウンド鍵のバイトを推測します。modern-ciphers-2.mdを参照してください。
• AES-GCMのノンス再利用（禁止された攻撃）： 同じノンスを使うと、CTRキーストリームが再利用され、GF(2^128)上の多項式因数分解によってGHASH認証鍵を復元できます。ツール：nonce-disrespect。modern-ciphers.mdを参照してください。
• SRPプロトコルのバイパス： A = 0またはA = nを送ると共有秘密が0になり、パスワード検証を完全にバイパスできます。modern-ciphers-2.mdを参照してください。
• 変更されたAES Sボックスの総当たり： 出力が16種類しかない独自Sボックスでは、鍵のエントロピーが低下し、ラウンドごとに鍵バイトを総当たりできます。modern-ciphers-2.mdを参照してください。
• RabinのLSBパリティオラクル： LSBオラクルを使うと、c = m^2 mod nのRabin暗号文から、乗法準同型性（c * 4 mod nで平文が2倍になる）により、log2(n)回のクエリで二分探索による平文復元が可能です。modern-ciphers-2.mdを参照してください。
• ノイズのあるRSA LSBオラクルの誤り訂正： LSBオラクルに断続的な誤りがある場合、標準的な攻撃を実行してから出力の文字セットを調べます。誤りが発生した位置でオラクルの結果を反転させることで、残りの復号結果を修正できます。modern-ciphers-3.mdを参照してください。
• PBKDF2のプリハッシュバイパス： HMACは64バイトを超える鍵を事前にハッシュします（SHA-1/SHA-256のブロックサイズ）。元のパスワードが64バイトを超える場合、passwordの代わりにSHA1(password)でログインします。modern-ciphers-2.mdを参照してください。
• MD5マルチコリジョン（fastcol）： fastcolを連鎖して実行すると、MD5が同一の2^k個のファイルを生成できます。Merkle-Damgard構成では、衝突は追加されたサフィックスにも伝播します。modern-ciphers-2.mdを参照してください。
• 独自ハッシュの状態逆算： 反復型ハッシュが中間状態を漏えいする場合、状態更新式を逆算してブロックごとのハッシュ値を分離し、各4バイトブロックを個別に総当たりできます。modern-ciphers-3.mdを参照してください。
• CRC32の総当たり（小さなペイロード）： ZIPのCRC32ヘッダーは暗号化されていません。保存されたCRC32と照合し、印字可能な文字列をすべて試すことで、小さなファイル（≤ 6バイト）の内容を総当たりできます。modern-ciphers-3.mdを参照してください。
• XORブロックの相殺による独自MAC偽造： MAC鍵ストリームが周期的に繰り返される場合、埋め草ブロックがXORで相殺されるように3つのクエリを作成し、任意の対象コマンドのMACを偽造できます。modern-ciphers-3.mdを参照してください。
• HMAC鍵の復元（XOR＋加算演算）： sha256((key XOR msg) + msg)を使う脆弱なHMACでは、鍵のビットが漏えいします。msg=0でsha256(key)が得られ、msg=2^iで一致すれば鍵のビットiがセットされています。modern-ciphers-3.mdを参照してください。
• AES-CBC暗号文の偽造（エラーメッセージオラクル）： サーバーはエラーメッセージで復号済みバイトを漏えいします。ゼロブロックを送って中間状態を取得し、目的の平文とXORして、ブロック単位で暗号文を偽造します。modern-ciphers.mdを参照してください。 完全なコード例については、modern-ciphers.md と modern-ciphers-2.md を参照してください。

RSA 攻撃

• Small e with small message: eth 根を取る
• Common modulus: 拡張 GCD 攻撃
• Wiener's attack: 小さな d
• Fermat factorization: p と q が近い
• Pollard's p-1: p-1 がスムーズ
• Hastad's broadcast: 同じメッセージ、複数の e=3 暗号化
• Consecutive primes: q = next_prime(p); sqrt(N) 未満の最初の素数を探す
• Multi-prime: sympy で N を素因数分解; すべての因数から phi を計算
• Restricted-digit primes: LSB から桁ごとに、modular pruning を用いて素因数分解
• Coppersmith structured primes: 部分的に既知の素数; coppersmith ライブラリによる small_roots（詳細では Sage フォールバック）
• Manger oracle (simplified): フェーズ1の倍化 + フェーズ2の二分探索; 64 ビット鍵で約 128 クエリ
• Manger on RSA-OAEP (timing): Python の or の短絡評価により、Y != 0 のときに高コストな PBKDF2 がスキップされ、fast/slow のタイミングオラクルが生じます。完全な3ステップ攻撃（1024 ビット RSA で約 1024 イテレーション）。既知の fast/slow サンプルでタイミングの境界をキャリブレーションします。
• Polynomial hash (trivial root): 多項式ハッシュで g(0) = 0; msg = 0 (mod P) となるようサフィックスを作成し、署名 = 0
• Polynomial CRT in GF(2)[x]: 約 20 個の剰余 r = flag mod f を収集し、互いに素なものをフィルタリングして CRT で結合
• Affine over composite modulus: 各素因数体での CRT; 素数ごとに Gauss-Jordan
• RSA p=q validation bypass: p=q に設定すると、サーバーが p*(p-1) ではなく誤った phi=(p-1)^2 を計算します; 復号テストが失敗し、暗号文が漏洩します
• RSA cube root CRT (gcd(e,phi)>1): すべての素数が ≡ 1 mod e のとき、nthroot_mod で素数ごとに eth 根を計算し、CRT の組み合わせを列挙します（小さな k なら 3^k が実行可能）
• Factoring from phi(n) multiple: phi(n) の任意の倍数（例: e*d-1）は、Miller-Rabin の平方根テクニックによる素因数分解を可能にします; 試行ごとに確率 ≥ 1/2 で成功
• Weak keygen via base representation: 素数 p = kp*B + tp（kp が小さい）は n に混合基数構造を生み出します; kp*kq（2^24）を総当たりして素因数分解
• RSA with gcd(e,phi)>1 (exponent reduction): e' = e/g に縮約し、d' = e'^(-1) mod phi を計算し、m^g まで部分復号してから、整数上で g 乗根を取ります
• RSA partial key recovery (dp/dq/qinv): 部分的な PEM 漏洩から得た CRT 指数により、O(e) で素数の復元が可能です: k を反復し、(dp*e-1)/k+1 が素数かどうかを確認します。詳細は rsa-attacks-2.md を参照してください。
• RSA-CRT fault attack: 単一の故障した CRT 署名は gcd(s^e - m, n) によって因数を漏洩します（Bellcore 攻撃）。詳細は rsa-attacks-2.md を参照してください。
• RSA homomorphic decryption bypass: 乗法的準同型性により、c * r^e mod n でオラクルに問い合わせて c を復号し、その結果を r で割ることができます。詳細は rsa-attacks-2.md を参照してください。
• RSA small prime CRT decomposition: n が多くの小さな素因数を持つ場合、試し割りで素因数分解し、素数ごとに m mod p_i を解き、CRT で結合します。詳細は rsa-attacks-2.md を参照してください。
• Hastad broadcast with linear padding (Coppersmith): e 人の受信者がそれぞれ暗号化前に既知のアフィン変換 a_i*m+b_i を適用する場合、CRT + Coppersmith の small_roots で m を復元します。詳細は rsa-attacks.md を参照してください。
• RSA Montgomery reduction timing attack: Montgomery 乗算で漏洩した余分な減算の回数が、統計的な相関により MSB から LSB へ秘密鍵のビットを明らかにします。詳細は rsa-attacks-2.md を参照してください。
• Bleichenbacher low-exponent signature forgery: e=3 のとき、正しいパディングプレフィックスを持つ値の立方根を計算して PKCS#1 v1.5 署名を偽造します; 末尾のゴミが残りを吸収します。詳細は rsa-attacks-2.md を参照してください。
• Franklin-Reiter related message attack (e=3): パディングの差が既知である m+pad1 と m+pad2 の2つの暗号文; Zmod(n) での多項式 GCD により m を直接復元します。詳細は rsa-attacks.md を参照してください。
• RSA signature bypass (e=1, crafted modulus): 検証器がユーザー提供の (n, e) を受け入れます; e=1 および n = sig - PKCS1_pad(msg) に設定すると、pow(sig, 1, n) が期待されるパディング済みハッシュと等しくなります。詳細は rsa-attacks-2.md を参照してください。
• Coppersmith on linearly-related primes: 既知の k に対して q ~ k*p のとき、q ~ sqrt(k*n) と近似し、誤差項に対して Coppersmith の small_roots を使用します。Fermat 素因数分解を連続しない素数に一般化したものです。詳細は rsa-attacks.md を参照してください。 完全なコード例については、rsa-attacks.md と advanced-math.md を参照してください。

楕円曲線攻撃

• 小部分群攻撃： 曲線の位数に小さな因数がないか確認します。Pohlig-Hellman + CRT を使用します
• 不正な曲線攻撃： 検証が行われていない場合、より弱い曲線上の点を送信します
• 特異曲線： 判別式 = 0 の場合、DLP は加法群または乗法群に写像されます
• Smart の攻撃： 異常曲線（位数 = p）では、p 進リフトにより O(1) で DLP を解けます
• ベビーステップ・ジャイアントステップ（BSGS）： 一般的な DLP を O(sqrt(n)) の時間と空間で解きます。位数が滑らかな群（p-1 または曲線の位数のすべての因数が小さい群）では、Pohlig-Hellman と組み合わせます。sympy/fpylll の BSGS+Pohlig-Hellman（Sage の代替案は統合済み）については、advanced-math.md を参照してください。
• フォールトインジェクション： 正常な出力と故障した出力を比較し、鍵のビットを1つずつ復元します
• クロック群（x^2+y^2=1）： 位数 = p+1（p-1 ではありません！）。p+1 が滑らかな場合は Pohlig-Hellman を使用します
• アイソジェニー： モジュラ多項式を使ってグラフを探索し、LCA を使って経路を探索します
• ECDSA のノンス再利用： 2つの署名で同じ r を使うと、モジュラー演算によってノンス k と秘密鍵 d が漏えいします。r の値が繰り返されていないか確認してください
• 組みひも群 DH： Alexander 多項式は組みひもの連結に対して乗法的なため、Eve は公開鍵から共有秘密を計算できます。exotic-crypto.md を参照してください
• Ed25519 の捩れ点サイドチャネル： 鍵導出で key = master * uid mod l を使用すると、余因子 h=8 によって秘密スカラーのビットが漏えいします。2 の累乗を照会し、y 座標の整合性を確認します
• トロピカル半環の剰余： トロピカル（min-plus）DH は破られています。残差 b* = max(Mb[i] - M[i][j]) により、公開行列から共有秘密を直接復元できます
• FPE Feistel の総当たり攻撃： 16ビットのラウンド鍵を使う形式保持暗号は総当たりで解読できます。残りのアフィン GF(2) 混合層はガウス消去法で解けます。exotic-crypto.md を参照してください
• 二十面体対称性暗号： 12面体の面の置換は位数120の群を形成します。API をプローブしてすべての置換のルックアップテーブルを作成し、目に見える面のパターンと照合します。exotic-crypto.md を参照してください
• Goldwasser-Micali 複製オラクル： GM は暗号文ごとに1ビットを暗号化します。1つの暗号文の値を N 回再利用して N ビット鍵にすると、すべてゼロまたはすべて1の鍵を強制でき、ハッシュオラクルで識別できます。128回の照会で AES 鍵全体を復元できます。exotic-crypto.md を参照してください
• DSA のノンス再利用： 2つの DSA 署名で同じ r を使うと、ECDSA のノンス再利用と同じ式で秘密鍵が漏えいします。ecc-attacks.md を参照してください。
• DSA の限定 k 総当たり攻撃： ノンス k が小さい場合（例：20ビット）、すべての k 値を総当たりし、既知の r が得られる値を確認します。ecc-attacks.md を参照してください。
• ECC の共有素因数 GCD 攻撃： 複数の ECC 曲線が法の素因数を共有している場合、gcd(n1, n2) から共有素因数が明らかになります。ecc-attacks.md を参照してください。
• k 生成時の MD5 衝突による DSA 鍵の復元： ノンス k が MD5(prefix+counter) から導出される場合、fastcoll で MD5 のプレフィックス衝突を生成してノンスを再利用させ、その後、標準的な方法で秘密鍵を復元します。ecc-attacks.md を参照してください。
• BB-84 QKD の MITM 攻撃： 古典チャネルが認証されていない BB-84 シミュレーションでは、完全な MITM 攻撃が可能です。両者と個別に鍵をネゴシエートし、一方に定数値を強制します。exotic-crypto-2.md を参照してください。

コード例の全容については、ecc-attacks.md、advanced-math.md、exotic-crypto.md を参照してください。

ディフィー・ヘルマン攻撃

• 自明な g： まず g = 0, 1, p-1 と、相手の値 A = 0, 1, p-1, p を試します。範囲チェックが行われていない場合、既知の定数を共有秘密として得られます。詳細は dh-attacks.md を参照してください。
• ポーリグ・ヘルマン： p-1 を素因数分解します。p-1 の素因数が小さい場合、各部分群で BSGS を使って完全な離散対数問題（DLP）を解き、CRT で統合できます。詳細は dh-attacks.md を参照してください。
• 小部分群への閉じ込め／リム・リー攻撃： 静的鍵を使い、p-1 に小さな因数がある場合、位数 r の元を送信し、MAC／復号オラクルで b mod r を総当たりし、r_i ごとに CRT を適用します。詳細は dh-attacks.md を参照してください。
• X25519 の低位数点： コファクターが 8 でクランプ処理が行われるため、位数の小さい u は必ず全ゼロの K を生成します。u = 0, 1 は必ず試してください。全ゼロチェックがない場合、1～2 回のクエリで破れます。詳細は ecc-attacks.md を参照してください。

格子／LWE 攻撃

• 迅速な見極め： チャレンジで、隠された値が小さい、疎である、偏りがある、または一部しか漏えいしていないという条件付きで、法を使った線形方程式が与えられた場合は、まず格子問題として検討します。詳細は lattice-and-lwe.md を参照してください。
• LLL／BKZ／ババイ： fpylll の LLL.reduction／BKZ.reduction／GSO.Mat.babai／CVP.closest_vector（詳細にある Sage の Matrix(ZZ).LLL()／M.BKZ のフォールバック）を使います。まず LLL を試し、あと一歩で解けそうな場合は BKZ に移行し、近似 CVP にはババイを使います。詳細は lattice-and-lwe.md を参照してください。
• ノンスの一部漏えいから HNP を解く： ECDSA／Schnorr のノンスの一部漏えいまたは偏りは、しばしば Hidden Number Problem の格子問題に帰着できます。方程式を正規化し、誤差の範囲を限定してから格子を簡約します。必要に応じて、残り数ビットを総当たりします。詳細は lattice-and-lwe.md を参照してください。
• 切り詰められた LCG の状態復元： アフィン漸化式から上位ビットまたは下位ビットが漏えいしている場合、その問題は HNP を別の形で表したものにすぎないことがよくあります。各状態を observed * 2^t + hidden と表し、隠された小さな補正値を求めます。詳細は lattice-and-lwe.md を参照してください。
• CVP（ババイ）による LWE： [q*I | 0; A^T | I] から格子を構成し、fpylll の GSO.Mat.babai または CVP.closest_vector を使って最も近いベクトルを求め、三値集合 {-1,0,1} に射影します。サーバーの説明と実際のエンコードでエンディアンが一致しているか確認してください。
• Ring-LWE／Module-LWE の見極め： 多項式構造や反巡回構造は難しそうに見えますが、多くの CTF では係数が非常に小さい、表現にバグがある、または十分な情報が漏えいしているなどの理由で、通常の LWE に単純化できます。詳細は lattice-and-lwe.md を参照してください。
• 直交格子： 隠された部分集合や部分空間の問題では、まず直交格子を復元し、その補空間から実際の二値基底または短い基底を再構成する必要がある場合があります。詳細は lattice-and-lwe.md を参照してください。
• 近似 GCD に対する LLL： fpylll の LLL.reduction（詳細にある Sage の Matrix(ZZ).LLL() をフォールバックとして使用）を使います。格子内の短いベクトルから隠れた因数が分かります。
• 部分和／ナップサック： 二値ナップサックや密度の低い部分和問題は、今も格子攻撃の定番です。標準基底を構成し、最後の座標がゼロの簡約後の行を探します。詳細は lattice-and-lwe.md を参照してください。
• 多層チャレンジ： 幾何 → 部分空間の復元 → LWE → AES-GCM 復号という連鎖

LWE を解くコード例は advanced-math.md、攻撃の選択、埋め込み、失敗モードの見極めについては lattice-and-lwe.md を参照してください。

ZKP と制約解決

• ZKP の不正行為： 不可能な問題（3-coloring K4）では、ハッシュ衝突を見つけるか、PRNG のソルトを予測します
• グラフの 3 彩色： nx.coloring.greedy_color(G, strategy='saturation_largest_first')
• Z3 ソルバー： ビット単位の処理には BitVec、任意精度の処理には Int を使用します。BPF/SECCOMP フィルターの解決にも使えます
• ガーブリング回路（free XOR）： 真理値表の 3 つのエントリーを XOR してグローバルデルタを復元します
• バイグラム置換： 既知の平文構造に対するオートマトン制約とともに OR-Tools CP-SAT を使用します
• トライグラム分解： n を法とする位置ごとに、独立した単一換字式暗号になります
• シャミア秘密分散（決定的係数）： 1 つのシェアとシード付き RNG から、秘密を変数とする一変数方程式が得られます
• 競合状態（TOCTOU）： 同期した同時リクエストにより、counter < N のチェックを回避できます
• Groth16 の壊れたセットアップ（delta==gamma）： 簡単に偽造できます。A=alpha、B=beta、C=-vk_x となります。まず検証器の定数を必ず確認してください
• Groth16 証明のリプレイ： 制約のない nullifier と追跡機能がない状態では、セットアップトランザクションから無限にリプレイできます
• DV-SNARG の偽造： 検証器オラクルにアクセスできる場合、制約のないペアから秘密の v 値を学習し、CRS エントリーの相殺によって偽造できます
• シャミア秘密分散での多項式係数の再利用： すべての秘密バイトに同じ乱数係数を使うと、シェアを減算することで乱数成分がすべて相殺され、平文の差分だけが残ります。zkp-and-advanced.mdを参照してください。

コード例とソルバーのパターンについては、zkp-and-advanced.mdを参照してください。

最新の暗号攻撃（追加）

• 合成法におけるアフィン暗号： c = A*x+b (mod M)。M は合成数（例：65=5*13）です。ワンホットベクトルを使って選択平文から復元し、素因数ごとに CRT で逆変換します。modern-ciphers.mdを参照してください。
• カスタム線形 MAC の偽造： 秘密ブロックに対して線形な XOR ベースの署名です。約 5 組の既知ペアから秘密を復元し、ターゲット向けに偽造します。modern-ciphers.mdを参照してください。
• Manger オラクル（RSA のしきい値）： RSA の乗法性と m*s < 2^128 の二分探索を利用します。AES キーの復元には約 128 回のクエリが必要です。
• バイト単位のゼロ化オラクルを使った AES キーの復元： キースロットのインデックス処理における整数オーバーフローにより、バイトを選択的にゼロ化できます。1 バイトずつ総当たりします（1 バイトあたり 256 通り、合計 4096 通り）。modern-ciphers.mdを参照してください。

GF(2) 線形代数による自己参照 CRC

自己参照 CRC：CRC が自身と一致する ASCII 文字列を見つけます。CRC は GF(2) 上で線形なので、制約は解ける線形方程式系になります。表示可能な ASCII の範囲になるよう自由変数を選びます。advanced-math.mdを参照してください。

CBC パディングオラクル攻撃

サーバーがパディングの有効・無効を明らかにするため、鍵なしで任意の CBC 暗号文を復号できます。16 バイトブロックあたり約 4096 回のクエリが必要です。PadBuster または Python ライブラリの padding-oracle を使用してください。modern-ciphers.mdを参照してください。

Bleichenbacher RSA パディングオラクル（ROBOT）

RSA PKCS#1 v1.5 のパディング検証オラクルを利用して、適応的な選択暗号文攻撃で平文を復元します。RSA-2048 では約 10K 回のクエリが必要です。タイミングを通じて TLS の実装に影響します。modern-ciphers.mdを参照してください。

バースデー攻撃／中間一致攻撃

n ビットのハッシュ衝突は約 2^(n/2) 回の試行で見つかります。中間一致攻撃では、二重暗号化を O(2^(2k)) ではなく O(2^k) で破ります。modern-ciphers.mdを参照してください。

• スポンジハッシュの中間一致衝突： スポンジのレートが状態サイズより小さい場合、制御されていない状態バイトを利用して中間一致攻撃を実行できます。制御されていないバイトをキーに順方向の暗号化結果を事前計算し、一致する結果を逆方向に探索します。計算量を 2^48 から 2^24 に削減できます。modern-ciphers-3.mdを参照してください。

CRC32 衝突ベースの署名偽造（iCTF 2013）

CRC32 は線形です。任意のターゲット CRC32 に強制するために選んだ 4 バイトを追加すれば、秘密情報なしで CRC32(msg || secret) の署名を偽造できます。modern-ciphers.md を参照してください。

Blum-Goldwasser ビット拡張オラクル（PlaidCTF 2013）

オラクルへのクエリごとに暗号文を 1 ビットずつ拡張し、パリティを通じて平文を漏えいさせます。BBS の二乗系列を操作して、有効な拡張暗号文を生成します。modern-ciphers-2.md を参照してください。

ハッシュ長拡張攻撃

Merkle-Damgard ハッシュ（hash(SECRET || user_data)）の特性を悪用し、任意のデータを追加して、秘密情報を知らずに有効なハッシュを計算します。hashpump または hashpumpy を使用します。modern-ciphers-2.md を参照してください。

圧縮オラクル（CRIME 形式）

暗号化前の圧縮により、暗号文の長さの変化を通じて平文が漏えいします。選択した平文を送信すると、一致する n-gram はより短く圧縮されます。CRIME／BREACH と同じ種類の攻撃です。modern-ciphers-2.md を参照してください。

RC4 の第 2 バイトの偏り

RC4 の 2 番目の出力バイトは 0x00 に偏っています（確率は 1/128、対して 1/256）。約 2048 個のサンプルで、RC4 とランダムデータを判別できます。stream-ciphers.md を参照してください。

RSA の乗法準同型性を利用した署名偽造

パディングなしの RSA では、S(a) * S(b) mod n = S(a*b) mod n が成り立ちます。オラクルがターゲットメッセージをブラックリストに登録している場合、その因数に署名して乗算します。rsa-attacks-2.md を参照してください。

よくあるパターン

• RSA の基本： phi = (p-1)*(q-1)、d = inverse(e, phi)、m = pow(c, d, n)。rsa-attacks.md に完全な例があります。
• XOR： from pwn import xor; xor(ct, key)。XOR の各種手法については classic-ciphers.md を参照してください。

ctypes による C の srand/rand の予測（L3akCTF 2024、MireaCTF）

パターン： バイナリがキーや XOR マスクに srand(time(NULL)) と rand() を使用しています。Python の random モジュールは異なる PRNG を使用します。ctypes.CDLL('./libc.so.6') を使って C の srand(int(time())) と rand() を直接呼び出し、正確な系列を再現します。XOR 復号の例とタイミングに関するヒントは prng.md を参照してください。

V8 XorShift128+（Math.random）の状態復元

パターン： V8 JavaScript エンジンは Math.random() に xs128p PRNG を使用します。Math.floor(CONST * Math.random()) の連続した出力を 5～10 個与えると、Z3 QF_BV ソルバーで内部状態（state0、state1）を復元し、将来の値を予測できます。値は逆順（LIFO キャッシュ）にする必要があります。ツール：d0nutptr/v8_rand_buster。prng.md を参照してください。

浮動小数点出力からの MT 状態復元（PHD CTF Quals 2012）

パターン： サーバーが random.random() の浮動小数点値を公開しています。標準的な untemper には 624 個の 32 ビット整数が必要ですが、浮動小数点値から得られる有効なビットはそれぞれ約 8 ビットだけです。事前計算された GF(2) のマジック行列（not_random ライブラリ）を使うと、3360 個以上の浮動小数点値から MT の完全な状態を復元できます。random.random() から導出されるパスワードリセットトークン、セッション ID、CSRF トークンの予測に利用できます。prng.md を参照してください。

カオス PRNG（ロジスティック写像）

• ロジスティック写像： x = r * x * (1 - x)、r ≈ 3.99-4.0。高精度の小数を総当たりしてシードを復元します
• キーストリーム： 各反復で struct.pack("<f", x) を実行し、暗号文と XOR します

完全なコードは prng.md を参照してください。

SPN S ボックス交差攻撃

分割統治による SPN の鍵復元です。各 S ボックスの位置を個別に攻撃し、複数の平文と暗号文の組み合わせで有効な鍵候補を絞り込みます。指数的な鍵空間を、独立したサブキーの探索に分割します。modern-ciphers-3.md を参照してください。

便利なツール

• Python： pip install pycryptodome z3-solver sympy gmpy2
• SageMath（任意の代替手段）： sage -python script.py — Sage の代替手段に縮約したものに限ります
• RsaCtfTool： python RsaCtfTool.py -n <n> -e <e> --uncipher <c> — RSA 攻撃スイートを自動実行します（Wiener、Hastad、Fermat、Pollard など多数の攻撃を試します）
• quipqiup.com： 換字式暗号の自動解読ツール（頻度分析と単語パターン分析）