暗号理論

同義語：暗号学cryptography

概要

前提知識: 合同式, 群, 有限体, 確率空間

暗号理論（cryptography）は、通信の内容を第三者に読まれないようにし（秘匿）、改ざんやなりすましを見破れるようにする（認証）方法を、数学の言葉で定式化して調べる分野である。中心にあるのは、鍵を知る者だけが元に戻せる写像（暗号化）であり、その「安全さ」を確率と計算の手間で定義して、どの方式がどの意味で安全かを証明したり、安全さを計算の難しい問題に帰着させたりする。整数論・有限体・楕円曲線の性質が方式の材料になり、素因数分解や離散対数の算法の研究が安全さの見積もりを与える。
この記事では、まず暗号方式と完全秘匿を定義し、代表的な定理として、ワンタイムパッドが完全秘匿であることと、完全秘匿には通信文と同じだけの鍵が要るという Shannon の定理を完全に証明する。続いて、実用の暗号が拠り所にする計算量的な安全性と、公開鍵暗号を支える計算の難しい問題を一覧にし、それぞれを扱う記事を示す。最後に、学ぶ順に記事を並べる。
誤りを含む通信路で情報を正しく送る方法を調べる符号理論（誤り訂正符号、Golay符号）も「符号」を扱い、有限体を道具にするが、目的は秘匿ではなく誤りの訂正であり、別の分野である。

暗号方式と完全秘匿

暗号方式

以下、集合はすべて有限集合とする。

暗号方式

有限集合 $\mathcal K$（鍵の集合）、$\mathcal M$（平文の集合）、$\mathcal C$（暗号文 の集合）と、写像
$$ E\colon\mathcal K\times\mathcal M\to\mathcal C,\qquad D\colon\mathcal K\times\mathcal C\to\mathcal M $$
の組 $(E,D)$ で、すべての $k\in\mathcal K$、$m\in\mathcal M$ について $D(k,E(k,m))=m$ を満たすものを、$(\mathcal K,\mathcal M,\mathcal C)$ の上の 暗号方式（cipher）という。$E$ を 暗号化、$D$ を復号という。

送り手と受け手はあらかじめ同じ鍵 $k$ を共有しておき、送り手は $c=E(k,m)$ を送り、受け手は $D(k,c)=m$ で平文を得る。鍵を共有する方式なので、後で述べる公開鍵暗号と区別して 共通鍵暗号 ともいう。条件 $D(k,E(k,m))=m$ から、鍵 $k$ を固定するごとに $m\mapsto E(k,m)$ は単射である。
方式 $(E,D)$ そのものは公開されていて、秘密なのは鍵 $k$ だけだと考える。安全さは「鍵を知らない者が暗号文から何を知りうるか」で測る。

完全秘匿

$(E,D)$ を $(\mathcal K,\mathcal M,\mathcal C)$ の上の暗号方式とし、確率変数 $\mathbf k$ は $\mathcal K$ の上の一様分布に従うとする。すべての $m_0,m_1\in\mathcal M$ と $c\in\mathcal C$ について
$$ \Pr[E(\mathbf k,m_0)=c]=\Pr[E(\mathbf k,m_1)=c] $$
が成り立つとき、$(E,D)$ は 完全秘匿（perfectly secure）であるという。

左辺の確率は $\lvert\{k\in\mathcal K:E(k,m_0)=c\}\rvert/\lvert\mathcal K\rvert$ に等しいので、完全秘匿であることは「各暗号文 $c$ について、$E(k,m)=c$ となる鍵 $k$ の個数が平文 $m$ によらない」ことと同値である（BS23 Theorem 2.1、pp. 8–9）。言い換えると、暗号文の分布は平文によらないので、暗号文を見ても、どの平文が送られたかについて何も分からない。平文も確率変数で、どの平文も正の確率で現れ、鍵と独立に選ばれるときには、完全秘匿であることは平文と暗号文が独立であることと同値になる（BS23 Theorem 2.4、pp. 11–12。この記事では証明しない）。

ワンタイムパッド

長さ $L$ のビット列の集合 $\mathbb F_2^L$ を $\mathcal K=\mathcal M=\mathcal C$ とし、成分ごとの $2$ を法とする足し算（排他的論理和）$\oplus$ で
$$ E(k,m)=k\oplus m,\qquad D(k,c)=k\oplus c $$
と定める。$D(k,E(k,m))=k\oplus k\oplus m=m$ なので暗号方式である。これを ワンタイムパッド（one-time pad）という（BS23 Example 2.1、p. 6）。たとえば $L=4$、鍵 $k=0110$、平文 $m=1100$ なら暗号文は $c=1010$ で、$c\oplus k=1100$ と戻る。

次の定理は、ワンタイムパッドを任意の有限群に広げた形で述べる。$\mathbb F_2^L$ の足し算の場合がワンタイムパッドであり、$\mathbb Z/n\mathbb Z$ の足し算の場合は文字を $n$ 個の数で表した「加法的な」ワンタイムパッドである（BS23 Example 2.4、p. 7）。

ワンタイムパッドの完全秘匿

$G$ を有限群とし、$\mathcal K=\mathcal M=\mathcal C=G$、$E(k,m)=km$、$D(k,c)=k^{-1}c$ とおく。このとき $(E,D)$ は完全秘匿な暗号方式である。とくにワンタイムパッドは完全秘匿である。

鍵がただ一つに決まる

$D(k,E(k,m))=k^{-1}km=m$ なので $(E,D)$ は暗号方式である。$m,c\in G$ を固定すると、$E(k,m)=c$、すなわち $km=c$ を満たす $k\in G$ は $k=cm^{-1}$ のただ一つである。よって $\mathbf k$ が $G$ の上で一様なら
$$ \Pr[E(\mathbf k,m)=c]=\frac{1}{\lvert G\rvert} $$
であり、右辺は $m$ によらない。したがって完全秘匿の条件が成り立つ。ワンタイムパッドは $G=\mathbb F_2^L$（演算は $\oplus$、逆元は自分自身）の場合である。$\square$

Shannon の定理

ワンタイムパッドでは鍵が平文と同じ長さである。この長さは完全秘匿のためには削れない。

Shannonの定理

暗号方式 $(E,D)$ が完全秘匿なら $\lvert\mathcal K\rvert\ge\lvert\mathcal M\rvert$ である。

復号で届く平文を数える

$\lvert\mathcal K\rvert<\lvert\mathcal M\rvert$ と仮定して矛盾を導く。$k_0\in\mathcal K$、$m_0\in\mathcal M$ を一つずつとり、$c=E(k_0,m_0)$ とおく。暗号文 $c$ をすべての鍵で復号して得られる平文の集合
$$ S=\{D(k,c):k\in\mathcal K\} $$
の元の個数は $\lvert\mathcal K\rvert$ 以下なので、仮定から $\lvert S\rvert<\lvert\mathcal M\rvert$ であり、$S$ に入らない平文 $m_1\in\mathcal M$ がある。
もしある鍵 $k$ で $E(k,m_1)=c$ なら、$m_1=D(k,E(k,m_1))=D(k,c)\in S$ となって $m_1$ の選び方に反する。よって $E(k,m_1)=c$ となる鍵はなく、$\Pr[E(\mathbf k,m_1)=c]=0$ である。一方、$E(k_0,m_0)=c$ なので $\Pr[E(\mathbf k,m_0)=c]\ge1/\lvert\mathcal K\rvert>0$ である。2 つの確率が異なるので、$(E,D)$ は完全秘匿ではない。$\square$

この定理は BS23 Theorem 2.5（pp. 12–13）にあり、Shannon による。証明は背理法で、平文の候補を鍵の個数より多くは「隠せない」ことを使っている。

文字をずらす暗号

英字 26 文字を $\mathbb Z/26\mathbb Z$ の元 $0,1,\dots,25$ で表し、長さ $L$ の文字列を $(\mathbb Z/26\mathbb Z)^L$ の元とみる。鍵 $k\in\mathbb Z/26\mathbb Z$ を 1 つ選んで全部の文字を $k$ だけずらす方式 $E(k,(m_1,\dots,m_L))=(m_1+k,\dots,m_L+k)$ では、鍵が $26$ 個しかなく平文が $26^L$ 個あるので、$L\ge2$ なら thm-crypto-shannon により完全秘匿ではない。実際、暗号文の隣り合う 2 文字の差 $(m_2+k)-(m_1+k)=m_2-m_1$ は平文の差そのものである。文字ごとに独立な鍵 $k_1,\dots,k_L$ でずらす方式は、$G=(\mathbb Z/26\mathbb Z)^L$ の場合の thm-crypto-otp であり、完全秘匿である。

鍵を 2 度使うと完全秘匿でない

ワンタイムパッドの同じ鍵 $k\in\mathbb F_2^L$ で 2 つの平文 $m,m'$ を暗号化すると、暗号文の和は $c\oplus c'=m\oplus m'$ となり、鍵を知らなくても平文の和が分かる。2 つの平文の組をまとめて 1 つの平文とみると、これは $\mathcal K=\mathbb F_2^L$、$\mathcal M=\mathcal C=(\mathbb F_2^L)^2$、$E(k,(m,m'))=(k\oplus m,k\oplus m')$ の暗号方式であり、$\lvert\mathcal K\rvert=2^L<2^{2L}=\lvert\mathcal M\rvert$ なので、thm-crypto-shannon により完全秘匿ではない。実際、$L=1$ で暗号文 $(0,0)$ になるのは平文 $(0,0)$（鍵 $0$）と $(1,1)$（鍵 $1$）だけで、平文 $(0,1)$ からは決して現れない（BS23 §3.3.1、p. 53 も参照）。

計算量的な安全性

Shannon の定理により、短い鍵で長い通信を完全秘匿にすることはできない。そこで実用の暗号では、敵の計算の手間に上限があると考え、「計算の手間が現実的な範囲の敵には、暗号文から平文についての情報がほとんど得られない」ことを安全さの定義にする。これを 意味的安全性（semantic security）という。完全秘匿では 2 つの平文の暗号文の分布が一致することを求めたのに対し、意味的安全性では、効率のよい算法がその 2 つの分布を見分けられる確率の差が無視できるほど小さいことを求める（BS23 §2.2 の Attack Game 2.1 と Definition 2.2、pp. 13–16）。
このときの安全さは、多くの場合「方式を破る効率のよい算法があれば、ある計算の難しい問題を効率よく解く算法が作れる」という形の帰着で示される。たとえば公開鍵暗号の記事では、ElGamal 暗号の意味的安全性を Diffie–Hellman 型の問題の難しさに、Rabin 暗号の一方向性を素因数分解に帰着させている。一方で、こうした問題が本当に難しいことは証明されていない。鍵を知る者だけが簡単に逆を計算できる「落とし戸つきの一方向関数」が存在するかどうか自体が未解決の問題である（Sil09 §XI.4、p. 376）。計算の手間の扱いは計算量理論、P対NP問題とつながっている。
意味的安全性は暗号化を確率的にすることを求める場合がある。同じ平文をいつも同じ暗号文にする決定的な公開鍵暗号は、意味的に安全でない（公開鍵暗号の定理「決定的な暗号化は意味的に安全でない」）。

公開鍵暗号と計算の難しい問題

共通鍵暗号では、通信する 2 人が前もって秘密の鍵を共有しなければならない。公開鍵暗号 では、暗号化の鍵（公開鍵）を誰にでも公開し、復号の鍵（秘密鍵）だけを受け手が持つ。公開鍵から秘密鍵を求めることが計算上難しくなるように、計算の難しい問題を使って鍵を作る。考え方は Diffie と Hellman が 1976 年に示し、最初の実用的な方式は翌年の RSA 暗号である（Sil09 §XI.4、p. 376）。秘密鍵で作り公開鍵で確かめる 電子署名 も同じ問題の上に作られる。

計算の難しい問題	その上に作られる方式	知られている解き方（古典的な計算機）	記事
合成数 $n=pq$ の素因数分解	RSA 暗号、Rabin 暗号	平滑数を使う準指数時間の算法（二次ふるい法、数体ふるい法）	RSA暗号, 公開鍵暗号, 素因数分解
法 $p$ の乗法群での離散対数	Diffie–Hellman 鍵共有、ElGamal 暗号	一般の群に効く約 $\sqrt N$ 回の算法と、整数の分解を使う準指数時間の指数計算法	離散対数, Diffie–Hellman鍵共有, 指数計算法
楕円曲線の有理点の群での離散対数	楕円曲線 Diffie–Hellman、ECDSA 署名	多くの曲線では一般の群の算法（約 $\sqrt N$ 回）しか知られていない	楕円曲線暗号
平方根の計算 $x^2\equiv a\pmod n$	Rabin 暗号	$n$ の素因数分解が分かれば解け、逆に平方根を求める手順から $n$ の素因数が得られる	公開鍵暗号

表の $N$ は群の位数である。素因数分解と法 $p$ の離散対数の準指数時間の算法は、どちらも小さな素数だけで割り切れる数（平滑数）の分布を使う（Sho08 第 15 章、pp. 399–420）。法 $p$ の乗法群と楕円曲線の群は、どちらも位数がおよそ $p$ の有限アーベル群だが、前者では整数の素因数分解を使う指数計算法が働くため、同じ安全さを得るのに楕円曲線のほうがずっと小さな $p$ で済むと考えられている（Ste17 §6.4.3、p. 139、BS23 Chapter 15 冒頭、p. 615）。また、十分大きな量子計算機があれば、素因数分解と離散対数はどちらも桁数の多項式時間で解けることが Shor によって示されている（Ste17 p. 8 と §3.2.1、p. 53。この記事では扱わない）。
方式の作り方と安全さの証明には、整数論の次の結果が繰り返し使われる。

法 $n$ の冪 $a^e\bmod n$ は反復二乗法により $e$ の桁数に比例する回数の掛け算で計算できる。暗号化・復号・鍵共有のどれもこれに頼っている。
RSA 暗号の復号の正しさは Fermatの小定理と中国剰余定理による。鍵を作るには大きな素数が要り、それは Miller–Rabin素数判定法のような確率的な素数判定で見つける。
有限体の乗法群が巡回群であること（有限体の定理「有限体の乗法群の構造」）が、離散対数を定義できる理由である。素数位数の部分群を使うのは、位数の小さな素因数から情報が漏れるのを防ぐためである（Diffie–Hellman鍵共有、離散対数の定理「Pohlig–Hellman の帰着」）。
楕円曲線の点の個数は Hasse の定理により $p+1$ に近い（楕円曲線の定理「Hasse の定理」）。

暗号の道具

暗号方式そのもののほかに、次の道具が暗号理論の対象になる。

道具	求められる性質	記事
ハッシュ関数	長い入力を短い値に写し、同じ値をもつ 2 つの入力（衝突）を見つけるのが難しい	ハッシュ関数
擬似乱数生成器	短い種から長い列を作り、効率のよい算法には一様乱数と見分けられない	擬似乱数
鍵共有	公開の通信路だけで 2 人が共通の秘密の値を得る	Diffie–Hellman鍵共有
電子署名	秘密鍵を持つ者だけが作れ、誰でも公開鍵で確かめられる	楕円曲線暗号（ECDSA）

擬似乱数生成器はワンタイムパッドの鍵を短い種から作る道具として使え、こうして作る暗号はストリーム暗号と呼ばれる。安全な擬似乱数生成器があれば、この暗号は（完全秘匿ではないが）意味的に安全である（BS23 §3.2 と Theorem 3.1、pp. 48–49）。

反例

thm-crypto-otp の仮定を 1 つずつ外すと、完全秘匿は成り立たなくなる。

外す条件	反例	成り立たなくなること
鍵を $G$ の上で一様に選ぶ	$G=\mathbb F_2$ で、鍵 $0$ を確率 $3/4$、鍵 $1$ を確率 $1/4$ で選ぶ	暗号文の分布が平文によらない
鍵の集合が $G$ 全体	$G=\mathbb Z/4\mathbb Z$ で、鍵を $\{0,2\}$ から一様に選び $E(k,m)=k+m$ とする	暗号文の分布が平文によらない
1 つの鍵で暗号化する平文は 1 つ	同じ鍵で 2 つの平文を暗号化する（ex-crypto-two-time）	暗号文から平文について何も分からない

反例の確認

1 行目：暗号文が $0$ になる確率は、平文 $0$ なら鍵 $0$ の確率 $3/4$、平文 $1$ なら鍵 $1$ の確率 $1/4$ で、異なる。暗号文 $0$ を見た敵は平文 $0$ と推測して、正しい確率が上がる。2 行目：平文 $0$ の暗号文は $\{0,2\}$ に、平文 $1$ の暗号文は $\{1,3\}$ に入るので、暗号文の偶奇から平文の偶奇が分かる。鍵が $2$ 個で平文が $4$ 個なので、thm-crypto-shannon からも完全秘匿でないことが分かる。3 行目は ex-crypto-two-time のとおりで、暗号文の和が平文の和になる。
なお thm-crypto-shannon の逆は成り立たない。$\mathcal K=\mathcal M=\mathcal C=\mathbb F_2$ で鍵を無視する方式 $E(k,m)=m$、$D(k,c)=c$ は、鍵の個数は平文の個数と等しいが、暗号文が平文そのものなので完全秘匿ではない。鍵の個数は完全秘匿の必要条件にすぎず、鍵の使い方が大事である。