暗号と符号

科目の概要

情報をやりとりするとき、困ることは大きく二つある。一つは、通信路が盗聴・改ざんされること。もう一つは、通信路や記録媒体が雑音で誤ることである。前者に対する数学が暗号 (cryptography) で、秘密を守り、相手が本物であることや内容が書き換えられていないことを確かめる。後者に対する数学が誤り訂正符号 (error-correcting code) で、冗長な情報を付け加えておき、誤りを検出・訂正する。Web の https 通信や電子署名、パスワードの保管は暗号の、QR コードや CD・DVD、携帯電話の通信、分散ストレージは符号の応用である。

目的は正反対に見えるが、どちらも同じ代数の上に作られている。

RSA 暗号は剰余環 $\mathbb{Z}/n\mathbb{Z}$ の上の冪乗であり、その正しさはオイラーの定理と中国剰余定理から従う（第1・2章）。
ディフィー–ヘルマン鍵共有や DSA は有限体の乗法群 $\mathbb{F}_p^\times$ の巡回部分群を、楕円曲線暗号は有限体上の楕円曲線の点の群を使う（第2〜4章）。
線形符号は $\mathbb{F}_q^n$ の部分空間であり、巡回符号は多項式環の剰余環 $\mathbb{F}_q[x]/(x^n - 1)$ のイデアルである。リード–ソロモン符号は有限体上の多項式の値の並びで、QR コードや CD は $\mathbb{F}_{2^8}$ 上のリード–ソロモン符号を使う（第5・6章）。共通鍵暗号 AES の内部でも $\mathbb{F}_{2^8}$ の演算が使われている。
格子暗号は $\mathbb{Z}^n$ の格子や、 $(\mathbb{Z}/q\mathbb{Z})[x]/(x^{256} + 1)$ のような多項式環の剰余環の上の問題を使う（第7章）。

この科目でとくに大切にするのは、安全性が何に依存しているかを数学で理解することである。暗号の主張には、性質の異なる 3 種類のものが混在している。

証明された事実：正しく復号・検証できること、符号が何個の誤りを訂正できるか、攻撃アルゴリズムの計算量、そして「この方式を破れれば、あの問題も解ける」という帰着（たとえば RSA の秘密鍵を求めることは $n$ の素因数分解と同じくらい難しい）。
仮定（予想）：素因数分解、離散対数、楕円曲線上の離散対数、格子上の問題（LWE）などが効率的には解けないこと。これらは一つも証明されていない。そもそも「一方向性関数」が存在することさえ証明されておらず、存在を証明すれば P ≠ NP も証明されることになる。
経験的な根拠：数十年にわたって多くの研究者が攻撃を試みても効率的な解法が見つかっていないこと、計算機実験の記録（たとえば 2020 年に 829 ビットの RSA の法が数体ふるい法で分解された）から見積もった、安全な鍵の長さ。

暗号の事故の多くは、数学そのものではなく、仮定が成り立たない使い方から起こる。教科書どおりの RSA をそのまま使う、乱数の質が低い、使い捨てのはずの乱数（ナンス）を使い回す、処理時間から秘密が漏れる、といった失敗を、本科目では小さい数で実際に計算して確かめる。

量子計算機の影響にも触れる。大規模な誤り耐性のある量子計算機が実現すれば、ショアのアルゴリズム（1994 年）により、素因数分解も離散対数（楕円曲線上のものを含む）も多項式時間で解け、RSA・ディフィー–ヘルマン・楕円曲線暗号はすべて破られる。共通鍵暗号やハッシュ関数に対しては、グローバーのアルゴリズムによる 2 乗程度の高速化にとどまるので、鍵やハッシュ値を長くすれば対応できる。本書の執筆時点で、実用的な鍵長の RSA や楕円曲線暗号を破れる規模の量子計算機は実現していないが、「いま暗号文を記録しておき、将来解読する」攻撃に備えて、量子計算機でも効率的な解法が知られていない問題に基づく耐量子暗号への移行が始まっている。米国の NIST は 2024 年に、格子に基づく ML-KEM・ML-DSA とハッシュ関数に基づく SLH-DSA を規格化した（FIPS 203・204・205）。ここで暗号と符号は再び出会う。一般の線形符号の復号の難しさに基づく暗号（マックエリース暗号、1978 年）も耐量子暗号の候補であり、量子計算機そのものも、大規模化には量子版の誤り訂正符号が欠かせないと考えられている。

なお本科目の目的は、暗号を自作することではない。本文の Python のコードは理解と検算のためのもので、実際のシステムでは実績のある暗号ライブラリと最新の規格を使うこと。

前提知識

04-algebra 第1章整数と合同式：合同式、中国剰余定理、オイラーの定理、原始根、平方剰余。全章の土台である。
04-algebra 第2章群の基礎：巡回群、元の位数、ラグランジュの定理（第1〜4章）。
04-algebra 第5章環とイデアル：剰余環、多項式環、中国剰余定理の環版（第6・7章）。
04-algebra 第8章体の拡大：有限体の存在と一意性、乗法群の巡回性（第4〜7章）。
04-algebra 第11章有限体（発展）：既約多項式と原始多項式、 $\mathbb{F}_{2^8}$ などでの具体的な計算、CRC と AES の有限体。第6章を読む前にあると望ましい。
線形代数：行列・ベクトル空間・線形写像（02-linear-algebra 第1章〜第3章）。第3章（二次ふるい法での $\mathbb{F}_2$ 上の一次従属）と第5〜7章で使う。線形符号は有限体上のベクトル空間の部分空間として、格子は $\mathbb{R}^n$ の離散的な部分群として扱う。
楕円曲線：第4章では、21-elliptic-curves 第2章群法則と第4章有限体上の楕円曲線の結果（加法公式、ハッセの定理）を、主張として引用して使う。21 を読んでいなくても第4章は読めるが、証明を知りたい読者は 21 を参照のこと。
確率：有限集合の上の一様分布、独立性、条件付き確率とベイズの定理、期待値程度（ミラー–ラビン法の誤り確率や誕生日攻撃で使う）。高校の確率（P6）で足り、測度論は使わない。
証明の読み書きと集合・写像・同値関係の言葉（00-foundations）。

この科目の記法

NOTATION.md の約束に加えて、次の記法を使う。符号の章（第5・6章）で使う記号はその章で定義する。

記号	意味
$\ell(n)$	正の整数 $n$ のビット長 $\lfloor \log_2 n \rfloor + 1$ （第1章）
$a \bmod n$	$a$ を $n$ で割った余り（ $0$ 以上 $n$ 未満の整数）
$\mathbb{Z}/n\mathbb{Z}$ 、 $(\mathbb{Z}/n\mathbb{Z})^\times$	法 $n$ の剰余環、その単元群（ $0, 1, \dots, n - 1$ を代表元とする）
$\mathbb{F}_q$ 、 $\mathbb{F}_q^\times$	$q$ 元体、その乗法群（ $\mathbb{F}_p = \mathbb{Z}/p\mathbb{Z}$ ）
$\varphi(n)$ 、 $\lambda(n)$	オイラー関数、カーマイケル関数（ $n = pq$ なら $\lambda(n) = \operatorname{lcm}(p - 1, q - 1)$ ）
$\log$ 、 $\log_2$	自然対数、2 を底とする対数
$\lbrace 0, 1 \rbrace^\ell$ 、 $\oplus$	長さ $\ell$ のビット列全体、ビットごとの排他的論理和
$(n, e)$ 、 $d$	RSA の公開鍵と秘密鍵
$G = \langle g \rangle$	離散対数を考える巡回群とその生成元（多くは素数位数 $q$ ）

到達目標

学習時間の目安と進め方

全体で 60〜80 時間（1 章あたり 8〜11 時間）を目安とする。学部 3〜4 年の半期から通年の講義に相当する。
章の依存関係はおおよそ次のとおりである。
- 第1章 → 第2章 → 第3章（暗号の整数論。この順に読むこと）
- 第3章 → 第4章（第4章は第3章の汎用的な攻撃と鍵長の表を使う。楕円曲線の理論の部分は 21-elliptic-curves の結果を引用する）
- 第5章 → 第6章（符号理論。第5章は有限体と線形代数だけで読めるので、符号に関心がある読者は第1章を読まずに第5章から始めてよい）
- 第7章は第1〜3章のあとに読む（格子の部分では線形代数を使う）
定理を読んだら、小さい数で実際に計算してみること。本文の数値例（ $n = 3233$ の RSA、 $p = 467$ のディフィー–ヘルマンなど）はすべて計算機で確かめてあるので、手計算と Python（または PARI/GP）の両方で再現するとよい。攻撃も、小さい数で一度自分で実行してみると、なぜ危ないのかが実感できる。
各章では、完全な証明をつけた定理と、主張だけを述べた定理（素数定理、ショアのアルゴリズム、ランダムオラクルモデルでの安全性証明など）を区別している。また「仮定のもとでの安全性」と「証明された正しさ」を混同しないように読んでほしい。
各章の「実務では」の囲みには、その数学が実際にどう使われ、どこで失敗しやすいかを書いた。推奨鍵長や規格は改訂されるので、実務で使うときは最新の規格（NIST の FIPS・SP、IETF の RFC、日本では CRYPTREC の暗号リスト）を確認すること。
演習問題は ★ をすべて解いてから ★★ に進むとよい。小さい数で暗号化・署名・攻撃をする問題と、「この設計のどこが危ないか」を問う問題を含めている。

参考文献

暗号

J. Hoffstein, J. Pipher, J. H. Silverman, An Introduction to Mathematical Cryptography (Springer) 数学科の学部生向けに、離散対数とディフィー–ヘルマン、素因数分解と RSA、デジタル署名、楕円曲線暗号、格子暗号を、証明と計算例つきで扱う。本科目の暗号の部分の主な参考書。
D. R. Stinson, M. B. Paterson, Cryptography: Theory and Practice (CRC Press) シャノンの理論、ブロック暗号、ハッシュ関数、RSA、離散対数、署名、鍵共有から耐量子暗号まで、暗号全般を扱う定番の教科書。
J. Katz, Y. Lindell, Introduction to Modern Cryptography (CRC Press) 安全性の定義（識別不可能性など）と帰着による安全性証明を厳密に扱う。第2章の安全性の定義の先を学ぶのに最適。
N. Koblitz, A Course in Number Theory and Cryptography (Springer) 暗号に必要な整数論（有限体、平方剰余、素数判定、素因数分解）と公開鍵暗号、楕円曲線を簡潔に扱う。第1〜4章の副読本に。
A. J. Menezes, P. C. van Oorschot, S. A. Vanstone, Handbook of Applied Cryptography (CRC Press) 暗号のアルゴリズムを網羅した事典的な本。1996 年刊で規格の記述は古いが、多倍長演算・素数判定・鍵共有などのアルゴリズムの正確な記述の参照先として有用。
R. Crandall, C. Pomerance, Prime Numbers: A Computational Perspective (Springer) 素数判定（ミラー–ラビン法、AKS 法など）と素因数分解（二次ふるい法、数体ふるい法など）のアルゴリズムを詳しく扱う。第1・3章の発展に。
岡本龍明・山本博資『現代暗号』（産業図書）公開鍵暗号を中心に、現代暗号の理論を数理的な基礎から解説する日本語の教科書。
結城浩『暗号技術入門』（SB クリエイティブ）数式をほとんど使わずに、共通鍵暗号・公開鍵暗号・ハッシュ関数・署名・証明書・TLS など暗号技術の全体像を解説する。本科目の数学が実務のどこで使われているかをつかむのに向く。

符号

F. J. MacWilliams, N. J. A. Sloane, The Theory of Error-Correcting Codes (North-Holland) 符号理論の古典的な大著。線形符号・巡回符号・BCH 符号・リード–ソロモン符号などを網羅する。
R. M. Roth, Introduction to Coding Theory (Cambridge University Press) 有限体上の代数的な符号とその復号（リード–ソロモン符号のリスト復号を含む）を現代的に扱う大学院向けの教科書。第6章の発展に。
J. H. van Lint, Introduction to Coding Theory (Springer) 数学者向けに簡潔にまとめた符号理論の教科書。限界式や完全符号などを扱う。
今井秀樹『符号理論』（電子情報通信学会）符号理論の標準的な日本語の教科書。代数的な符号と復号法を工学的な応用とともに扱う。

格子

D. Micciancio, S. Goldwasser, Complexity of Lattice Problems: A Cryptographic Perspective (Springer) 最短ベクトル問題・最近ベクトル問題などの格子問題の計算量と、その暗号への応用を扱う。第7章の発展に。

規格（いずれも改訂されうるので、使うときは最新版を確認すること）

NIST FIPS 186-5（デジタル署名の規格。RSA・ECDSA・EdDSA）、NIST SP 800-186（楕円曲線のパラメータ）
NIST FIPS 203（ML-KEM）・FIPS 204（ML-DSA）・FIPS 205（SLH-DSA）：2024 年に制定された耐量子暗号の規格
IETF RFC 7748（X25519・X448）、RFC 8032（EdDSA）

次に学ぶもの

21-elliptic-curves 楕円曲線：第4章で引用した群法則とハッセの定理の証明、楕円曲線上の離散対数への攻撃や楕円曲線法による素因数分解、同種写像暗号（第5章）。楕円曲線の整数論そのものへの入口でもある。
15-algebraic-number-theory 代数的整数論：数体ふるい法は、代数体の整数環に含まれる環 $\mathbb{Z}[\alpha]$ （整数環そのものとは限らない）での分解と、整数環のイデアルの素イデアル分解（第1章・第2章）を背景にしている。格子の幾何は第3章数の幾何学で扱われる。格子暗号でよく使われる環 $\mathbb{Z}[x]/(x^n + 1)$ （ $n$ は 2 のべき）は、1 の原始 $2n$ 乗根で生成される円分体の整数環に同型であり、円分体は第4章で扱われる。
04-algebra 第11章有限体：まだ読んでいなければ。有限体上の多項式の因数分解のアルゴリズムや、AES・CRC・リード–ソロモン符号の有限体の計算を詳しく学べる。
05-complex-analysis 第8章ゼータ関数と素数定理：第1章で主張だけを使った素数定理の証明。リーマン予想とその一般化は、素数の分布の精密な評価や、決定的な素数判定の理論（一般化リーマン予想のもとでのミラーの判定法）にも関わる。
11-probability 確率論：情報理論（シャノンの通信路符号化定理）や乱択アルゴリズムの解析を厳密に扱うための確率論。