← DSP シリーズ

Cryptography & Error-Correcting Codes

動いて理解する暗号と誤り訂正

暗号誤り訂正は、まったく別の技術に見えて、じつは同じ数学——有限体(ガロア体)——の上に立っています。この全18章は、合同算術という「時計の算数」から出発し、その土台を一段ずつ積み上げて、CRC・リードソロモン・AES・RSA・楕円曲線まで一本道でつなぎます。式はすべて導出付き、全18章すべてにブラウザ上で数値を動かせるデモ(LIVE・計23点)が入っています。

第 I 部 — 数学的基盤

「有限個の要素しかない世界で、四則演算がちゃんと成り立つ」ことを、定義から順に作り上げます。ここが全部の土台です。

CH 01合同算術とユークリッドの互除法時計の算数、GCD、ベズーの等式、逆元、繰り返し二乗法。▶ LIVE ×2 CH 02群・環・体「計算できる世界」の分類学。ラグランジュの定理まで。▶ LIVE CH 03有限体 GF(p)素数個の要素で四則演算が閉じる。原始元と離散対数。▶ LIVE ×2 CH 04多項式と既約多項式GF(2) 係数の多項式、割り算、既約性の判定。▶ LIVE CH 05拡大体 GF(2^m)1 バイトが 1 つの「数」になる。α のべき表と原始多項式。▶ LIVE

第 II 部 — 誤り検出・訂正

「壊れたことに気づく」から「壊れた場所を突き止めて直す」へ。CRC は 09 章で徹底的に扱います。

CH 06誤り訂正の基礎ハミング距離、検出 d−1 / 訂正 ⌊(d−1)/2⌋、限界式。▶ LIVE CH 07線形符号生成行列・検査行列・シンドロームの三点セット。▶ LIVE CH 08ハミング符号シンドロームを整数として読むと誤り位置そのもの。▶ LIVE CH 09巡回符号と CRC多項式の割り算による誤り検出。検出能力の証明、実装パラメータ、テーブル駆動まで。▶ LIVE ×2 CH 10BCH 符号訂正能力を「設計」する。連続根と BCH 限界。▶ LIVE CH 11リード・ソロモン符号QR コード・CD・宇宙通信の主役。BM 法とチェン探索。▶ LIVE

第 III 部 — 暗号

「秘密を共有していない相手と、安全に話す」までの道のり。第 I 部の代数がそのまま効いてきます。

CH 12暗号の基礎概念と古典暗号ケルクホフスの原理、シーザー、頻度分析、ワンタイムパッド。▶ LIVE CH 13ストリーム暗号と LFSRGF(2) 上の漸化式で乱数を作る。M 系列と周期 2^L−1。▶ LIVE CH 14ブロック暗号と AESSubBytes = GF(2^8) の逆元、MixColumns = MDS 行列。▶ LIVE CH 15数論の道具オイラー φ・オイラーの定理・中国剰余定理・素数判定。▶ LIVE ×2 CH 16RSA素因数分解の困難性に賭ける。鍵生成から復号まで全手順。▶ LIVE CH 17DH と楕円曲線暗号離散対数の困難性。点の足し算で群を作る。▶ LIVE ×2 CH 18ハッシュ・MAC・デジタル署名誕生日攻撃、HMAC、署名。「改ざんされていない」の保証。▶ LIVE

近道ルート

CRC だけ知りたい01 → 04 → 09
RSA だけ知りたい01 → 15 → 16
リードソロモンまで01 → 03 → 04 → 05 → 06 → 07 → 10 → 11
ぜんぶ01 → 18(推奨)