🪴 あやめHex

# これはなに？

CTF のライブラリ/知識集らしいです。なぜか CTF より競プロや雑学の方が多い。 (現在は LYT に近い思想で書いてる。)

競プロはライブラリ化されたものがよく出回ってるけど、CTF の方はほとんど閉じた場所でしか共有されてないよな～と思ったのであんこ(将来的に traP の CTF 班)が CTF に関するライブラリや CTF に必要な知識をまとめたものです。編集したい方は大歓迎です！気軽にプルリク投げてください～

説明を読めば機能最小限の同じものを自作できること以上、研究的な部分は自分が面白いとか知識が整理されたなとか思えば載せます。

これらは CC0 ライセンスとします。自由にコピペして OK です！ TODO: ライセンス

# 競プロ

テンプレート
Python
Rust

# データ構造

UnionFind
- ポテンシャル付きUnionFind
- 永続UnionFind
BIT (Binary-Indexed-Tree) / Fenwick Tree
Sparse Table
セグメント木
- 遅延セグメント木
- Segment Tree Beats
平方分割, パケット法
平衡二分探索木
- 赤黒木 RBST
- AVL木
- Splay木
- Treap
Wavelet Matrix
Wavelet Tree
slope trick
コンテナ
- List
- Map
- Set
- Unorderd Map
- Unordered Set

# グラフ

グラフ
- 最短経路問題
  - 単一始点最短路 $O(E\log V)$ (Dijkstra)
    - k-最短路 $O(kE\log V)$ (Dijkstra)
  - 単一始点最短路 $O(EV)$ (Bellman-Ford)
    - 負閉路検出 $O(EV)$ (Bellman-Ford)
  - 全点対間最短路 $O(V^3)$ (Floyd Warshall)
  - 全点対間最短路 $O((V + E)V\log V)$ (Johnson)
- 閉路検出
- 全域木
  - 最小全域森 $O(E\log V)$ (Prim)
  - 最小全域森 $O(E\log V)$ (Kruskal)
- フロー
  - 最大流 $O(V^2E)$ (Dinic)
  - 最大流 $O(E\times\mathrm{maxFlow})$ (Ford Fulkerson)
  - 最小費用流
  - 燃やす埋める
- 強連結成分分解
- Dilworth の定理
- 最大クリーク
- 最大独立集合
- Functional Graph
- トポロジカルソート
- 2-SAT
ツリー
- 木の直径
- 木の重心
- 重心分解
- HL分解
- オイラーツアー
- 最小共通祖先

# 算数

Bit Trick
数論
- 拡張 Euclid の互除法
- 数論的関数/進数変換
- 素数
  - 素因数分解
  - 高速素因数分解 (Pollard-$\rho$法/Millar-Rabin)
  - 素数列挙 (エラトステネスの篩)
  - 素数判定
  - 素数テーブル
- 剰余
  - Modint
  - 任意Modint
- 中国剰余定理
- floor sum
- 二分探索
- 三分探索
有理数
行列
高速フーリエ変換 (FFT)
- 任意mod畳み込み
- 高速ゼータ変換/高速メビウス変換
- Karatsuba 法
形式的冪級数 (FPS)
- 数論変換 (NTT)
- 多項式GCD
- 多項式補間
スライド最小値

# 探索

深さ優先探索
幅優先探索
座標圧縮
枝刈り
A*
IDA*
α-β 探索

# 幾何

幾何ライブラリ
凸包
偏角ソート

# 文字列

Z algorithm
Rabin-Karp 法
最長増加部分列
ローリングハッシュ
接尾辞配列
Boyer-Moore
LL(1) parser
Aho-Corasick

# 典型

しゃくとり法
動的計画法
集合の整数表現
最小値の最大化
半分全列挙
行列累乗
数え上げ
- 包除原理
- 対称性
Grundy 数

# ヒューリスティック

# Pwn

使用言語はPythonまたはC言語です。

Linux Userland
- テンプレート
- pwn を解く為に必要なステップ
- 脆弱性とセキュリティ機構
- Stack Exploit
- Format String Attack
- GOT overwrite
- glibc
  - glibc heap
  - _IO_FILE
- Heap Exploit
  - 脆弱性とセキュリティ機構
  - First Fit
  - Double Free
  - Forging chunks
  - Unlink Exploit
  - Shrinking Free Chunks
  - tcache poisoning
  - fastbin attack
  - overlapping chunks
  - mmap overlapping chunks
  - House of XXX
    - House of Orange
    - House of Botcake
    - House of Spirit
    - House of Lore
    - House of Storm
    - House of Force
Linux Kernel
- テンプレート
- Kernel Code Reading
  - セキュリティ機構
  - カーネルモジュール
- Heap Spray
- Dirty Pipe
- Race Condition
Windows Userland
Windows Kernel
VM Escape
- Container Escape
Automatic Exploit Generation

# Crypto

それぞれの暗号自体を取り扱うのではなく、Cryptoの背景にある理論を取り扱っていきます。使用言語はPythonまたはSageMathです。

SageMathチートシート
暗号構成基盤
- 攻撃者から守る為に
- Diffie-Hellman 鍵交換
- Fiat-Shamir 変換
  - Schnorr 署名
  - Frozen Heart
- Lamport 署名
- ゼロ知識証明
- Fujisaki-Okamoto Transformation
- 準同型暗号
格子
- Gram-Schmidt
- SVP (Shortest Vector Problem)
  - Lagrange 基底簡約 (Gauss 基底簡約)
  - サイズ基底簡約
  - LLL 基底簡約
  - BKZ 基底簡約 / HKZ 基底簡約
  - Kannan’s embedding method
- CVP (Closest Vector Problem)
  - Babai’s Algorithm
- Merkle-Hellmanナップサック暗号
  - LO法
  - CLOS法
- LWE (Learning with Errors) 暗号
  - LWE
    - BDD (Bounded Distance Decoding) Attack
    - SIS (Short Integer Solution) Attack
    - BKW Attack
    - Arora-Ge Attack
  - Ring-LWE
  - Module-LWE
    - CRYSTALS
  - LWR
- TFHE (Torus Fully Homomorphic Encryption)
多項式
- Coppersmith Method
- グレブナー基底
- 終結式
- MQ 問題
- Matsumoto-Imai 暗号 / HFE 暗号
- NTRU 暗号
- Rainbow 署名
- UOV 署名 / QR-UOV 署名
数論
- ディオファントス方程式
  - 二平方和
  - ペル方程式
- 離散対数問題 (DLP)
  - Baby-step Giant-step
  - Pollard’s rho 法
  - 指数計算法 (Index Calculus Algorithm)
  - 数体ふるい法
  - Pohlig-Hellman
RSA暗号
楕円曲線暗号
- 楕円曲線
  - Millar のアルゴリズム
  - Schoof のアルゴリズム
  - Tate pairing / Weil pairing
  - ECFFT
  - 超楕円曲線
- 攻撃
  - Pohlig-Hellman Attack
  - MOV/FR Reduction
  - SSSA Attack
  - Invalid Curve Attack
  - GHS Attack
  - Dual EC DRBG
  - Attacks on SIKE
AES
- Padding Oracle Attack
- BEAST Attack
- Lucky Thirteen Attack
- POODLE Attack
- ghash
- Integral Cryptanalysis
その他の暗号
Hash
- 誕生日攻撃
- Differencial cryptanalysis
疑似乱数生成器 (PRNG)
- Xorshift
- Mersenne twister
ブロックチェーン
- Flash Loan Attack
参考文献

# Web

Webに関してはよわよわなので読み込むと良いかもしれない資料リストを集めています。(これ読むといいよみたいなのがあったら教えてくださると助かります！)

# Misc

CTF の3大分野以外をまとめます.

Forensics
- Windows
OSINT
Reversing
- 表層解析
- 静的解析
  - Ghidra
- 動的解析
  - Fuzzing
  - シンボリック実行
- マルウェア
バイナリフォーマット探検隊
- ASCII
- Unicode
- ELF
- FAT32
- ext4
- ZIP
- JPEG
ピッキング
Tamper Evident
Social Engineering
Car Hacking
Pyjail

# コンピュータ・アーキテクチャ

数学
- 命題論理
- 意味論
物理
- 航空技術
回路
- 回路素子
- アナログ回路
  - 抵抗とコンデンサ
  - 昇圧チョッパ回路
  - マルチバイブレータ回路
  - 発振回路
    - コルピッツ発振回路
  - 電源
  - パワエレ
  - ノイズキャンセリング
  - センサー・アクチュエータ
    - モーター
    - Hブリッジ回路
    - PWM制御
    - ゲートドライバ
      - FETのオン抵抗, デッドタイム、昇圧回路
    - TA7291P, TB6643KQ, L298N
- デジタル回路
  - 遅延回路 + シュミットトリガ
  - キーボード
  - AVLライタ
  - 論理回路
    - ラッチ
    - フリップフロップ
  - マイコン
  - 通信
プロセッサ
- LSI
- Spectre / Meltdown
- HIEE; Hardware-assisted Isolated Execution Environments
  - TEE; Trusted Execution Environment
  - TPM; Trusted Platform Module
  - DRM; Digital Rights Management
  - DAA; Direct Anonymous Attestation
- rootkit
論理
マイクロアーキテクチャ
アーキテクチャ
仮想化技術
OS
- 略語
- スケジューラ
- BIOS/UEFI
- ACPI
- NIC
サーバー
ネットワーク
- SDR