cryptography

暗号技術

対象範囲

CTF およびペネトレーションテストでの実践的な暗号解読を扱います。暗号プリミティブの構造（独自ハッシュ、部分的な情報漏えい、関連する素数、不適切な乱数生成器、弱いモード）を利用することで、総当たりより高速な解法が可能かを見極め、可能な限り純粋な Python でその解法を実装します。RSA 系の代数的な因数分解、格子法／AGCD による復元、「複雑そうに見える」独自暗号の GF(2) 線形な崩壊、位数が滑らかな群での DLP、差分フォールト攻撃、非素数法上での Shamir 方式の秘密分散復元を扱います。SageMath や記号ソルバーを使う前に、必ずソースを読んで線形性や代数的構造がないか確認してください。

使用する場面

• 課題やターゲットが独自の暗号方式（独自ハッシュ、独自ブロック暗号、独自実装の鍵導出）を使用しており、アフィン／GF(2) 線形な崩壊を調べる必要がある場合。
• RSA 系プリミティブに構造化された素数（p = a·r + b、phi(n) が完全平方数、複数素数のヒントファイル、共通因数）が含まれる場合。
• サービスが選択暗号文／選択入力オラクルを公開しており、パディングオラクル、位数が滑らかな群での DLP、または Bleichenbacher 方式の復元が疑われる場合。
• AES に対するフォールト注入（同じ鍵での正常な暗号文とフォールトを含む暗号文 — Piret-Quisquater DFA）。
• Shamir 秘密分散や、非素数法を使うしきい値方式（付値を追跡しながらラグランジュ補間を用いる 2 進的な復元）。

参考資料

• reference/lattice-attacks.md — AGCD 格子法、判別式が平方数の場合の因数分解、位数が滑らかな群での DLP、Piret-Quisquater DFA。
• reference/linear-secret-recovery.md — 列ごとの線形復元による、独自ハッシュ／暗号の GF(2) アフィンな崩壊。