No.313 - 高校数学で理解する公開鍵暗号の数理

No.310-311「高校数学で理解するRSA暗号の数理」の続きです。公開鍵暗号の "老舗しにせ" である RSA暗号は、1978年に MIT の研究者であったリベスト（米）、シャミア（イスラエル）、エーデルマン（米）の３人によって発明されました（RSAは３人の頭文字）。３人はこの功績によって2002年のチューリング賞を受賞しました。チューリング賞は計算機科学分野の国際学会である ACM（Association of Computing Machinary）が毎年授与している賞で、この分野では最高の栄誉とされているものです。

しかし公開鍵暗号そのもののアイデアを最初に提示したのは、スタンフォード大学の研究者だったディフィー（米）とヘルマン（米）で、1976年のことでした。２人も 2015年にチューリング賞を受賞しています。この「鍵を公開する」という、画期的というか逆転の発想である公開鍵暗号の登場以降、暗号の研究は一変してしまいました。そして RSA暗号のみならず各種の公開鍵暗号が開発され、現代のインターネットの基盤になっています。たとえばインターネットのWebサーバへのアクセス（閲覧やフォーム入力など）で使われる SSL/TSL という暗号化通信（https:// のサイトで使われる）は、まさに公開鍵方式を使っています。

今回はその公開鍵暗号を "発明した" ディフィーとヘルマンに敬意を表して、彼らが発表した内容と、その数学的背景を書いてみたいと思います。タイトルは「公開鍵暗号の数理」としましたが、あくまで公開鍵暗号の原点となったアイデアの解説です。

ACM（Association of Computing Machinary）のサイトには、歴代のチューリング賞の受賞者の紹介ページがある。2015年の受賞者はディフィーとヘルマンで、受賞理由として「公開鍵暗号の発明」と書かれている。

（https://awards.acm.org/ より）

ディフィーとヘルマンが提出したアイデアは「公開鍵を使って秘密鍵を安全に共有する」ものでした。これは「ディフィー・ヘルマンの鍵共有」と呼ばれていて、現在でも使われています。そこでまず「秘密鍵の共有」の意義を振り返ってみたいと思います。

---

秘密鍵の共有

---

古今東西、様々な暗号化方式が開発・使用されてきましたが「秘密鍵の共有による暗号」（＝共通鍵暗号）が基本です。その中でも「一回限りの乱数表」は安全（＝解読されない）と証明されている暗号です。この場合、乱数表が秘密鍵に相当します。

英大文字・小文字、数字、英文に使われる特殊文字を、$0\text{ ～ }127$ の数字でコード化するとします。いま、$n$ 文字以下の平文ひらぶんをコード化して暗号文にしたいとき、「一回限りの乱数表」として必要なのは、$0\text{ ～ }127$ の値をとる乱数が $n$ 個並んだ表です。さらに、

コード化した平文	：　$a_i$
乱数表（秘密鍵）	：　$r_i$
暗号文	：　$b_i$

$$\begin{gathered} 1\le i\le n \\ 0\le a_i\text{, }{r}_i\text{, }{b}_i\le 127 \end{gathered}$$

とするとき、「乱数 $r_i$ の値に依存して、$a_i$ を $b_i$ に１対１に変換する関数 $f$」を決めておきます。そうすると、

$b_i=f\left(a_i,r_i\right)$

の変換で暗号文 $b_i$ が得られます。この関数 $f$ は $128\times 128$ の コード変換テーブルでもいいし、$\left(a_i+r_i\right)mod128$ のような四則演算でもよい。とにかく $r_i$ が違えば別の１対１変換になる関数が条件で、そうすれば逆変換で複号化が可能です。この関数を秘密にする必要はなく、オープンにしてもかまいません。この暗号が安全な理由は、

①	秘密鍵（＝乱数表）の長さが平文と同じ
②	秘密鍵は１回限り（＝使い終わったら捨てる）

の２点によります。もちろん乱数が "真の乱数" であることも重要です。しかし、上の２点を守るためには秘密鍵（乱数表）の長さが膨大になります。使い終わった乱数表のページを破って捨てなければならないからです。そこで実用的には、暗号文のやりとりを始める前に秘密鍵を共有しておき、暗号化はその「秘密鍵にもとづいた何らかの暗号化方式」で行うことになります。こうすると平文の長さが秘密鍵より長くなるので、絶対に安全とは言えなくなります。そこで、解読しにくい（＝強度の高い）暗号化方式の必要性があり、これをめぐって様々な方式が作られてきました。

しかし問題は、最初の「秘密鍵の共有」をどうやってやるかです。結局、秘密鍵を印刷し、アタッシュケースに入れて相手に持参するというような、スパイ映画にでも出てきそうな方法しか本質的には無いわけです。どういうやり方をとるにせよ「秘密鍵の共有」には多大なコストがかかる。

No.310-311「高校数学で理解するRSA暗号の数理」で書いた公開鍵暗号の価値はそういうところにあります。つまり、RSA暗号における暗号化・複号化は巨大な数の "冪剰余" を求める計算になり、これはこれで計算機負荷が高い。そこで、まずRSA暗号を使って秘密鍵を生成・共有しておき、以降はその秘密鍵を使う高速な（＝ 計算機負荷の低い）暗号化・複号化方式で通信をするやり方が多くとられます。もちろんその秘密鍵は通信が一段落したら捨てて、次の通信では新たな秘密鍵を生成して共有するわけです。これは他の公開鍵暗号でも同じです。

その、"公開鍵を使って秘密鍵を共有する" ことを最初に提唱したのが「ディフィー・ヘルマンの鍵共有」でした。そしてこれが、そもそもの「公開鍵の発明」になりました。この鍵共有は、

盗聴されている通信路を使って情報をやりとりすることで、秘密鍵の共有を安全に実現する

ためのアルゴリズムです。どうしてそんなことができるのかが、以降です。

---

９. ディフィー・ヘルマンの鍵共有

---

ディフィー・ヘルマンの鍵共有は次のように進みます。まず「公開鍵センター」が "皆が使う公開鍵"として、

$\left(p,g\right)$

・	$p$は巨大な素数
・	$g$は小さな整数

のペアを公開しておきます。次に、$A$ さんと $B$ さんが秘密鍵を共有したい場合、

$A$ は、$1<a<\left($ p$-1\right)$ である乱数 $a$ を発生させ、$g^a\left(modp\right)$ を $A$ の公開鍵として（盗聴されている通信路を介して） $B$ に送付

します。乱数 $a$ は $A$ の秘密鍵として秘匿します。次に同様に、

$B$ は、$1<b<\left($ p$-1\right)$ である乱数 $b$ を発生させ、$g^b\left(modp\right)$ を $B$ の公開鍵として（盗聴されている通信路を介して） $A$ に送付

します。もちろん $b$ は秘匿します。そして、

$A$ は $G_a={\left(g^b\right)}^a\left(modp\right)$ を共有の秘密鍵

$B$ は $G_b={\left(g^a\right)}^b\left(modp\right)$ を共有の秘密鍵

とします。この作り方から $G_a=G_b$ となるので、秘密鍵 $G=g^{ab}\left(modp\right)$ が共有できたことになり、以降はこれを使って暗号化通信を行います。大切なことは $A$ は $B$ の秘密鍵（$b$）を知らないし、$B$ は $A$ の秘密鍵（$a$）を知らないことです。それでも秘密鍵 $G$（$=G_a=G_b$）を共有できるわけです。

ちなみに、以上のプロセスに出てくる $g^a\left(modp\right)$ などの "冪剰余" の計算ですが、たとえ $a$ や $p$ が巨大数であっても効率的に計算できることを、No.311「高校数学で理解するRSA暗号の数理（２）」の「累乗の剰余を求めるアルゴリズム」で書きました。

以上の仕組みにおいて通信路が盗聴されたとしても安全なのは、$A$ の公開鍵 $g^a$ から $a$ を求めるのが困難なことと、同様に $g^b$ から $b$ を求めるのが困難なことです。なぜ困難かとい言うと、一つは $\mathit{p}$ が巨大な素数だからであり（10進数で数百桁か 1000桁以上）、また $\mathit{g}$ が「生成元」（原始根ともいう）だからです。

以降でその「生成元」とは何か、盗聴者が公開鍵から $A$ と $B$ の秘密鍵（$a$ と $b$）をなぜ計算できないのかという、ディフィー・ヘルマンの鍵共有の数学的背景を概観します。以下の説明では「高校数学程度の知識だけ」を前提としますが（＝ タイトルの "高校数学で理解する" の意味）、No.310-311「高校数学で理解するRSA暗号の数理」での各種説明は既知とします。特に、

合同
拡張ユークリッドの互除法
フェルマの小定理
冪剰余の計算アルゴリズム
オイラー関数

の知識を前提とします。

---

10. 有限体（${\mathbb{F}}_{\mathit{p}}$）と乗法群（${\mathbb{F}}_{\mathit{p}}^{\mathit{\ast }}$）

---

一般に加減乗除が定義された集合を "体（Field）" と言います。有理数、実数、複素数は "体" です。さらに No.310「高校数学で理解するRSA暗号の数理（１）」の終わりの方に書いたように、$p$ を素数とし、$p$ 未満の自然数と $0$ を合わせた集合も "体" となり、${\mathbb{F}}_p$ で表します。この集合は元の数が有限なので、有限体です。

${\mathbb{F}}_p$ における演算は、加算・減算・乗算については普通の整数のように行い、その答に対して$\left(modp\right)$ の演算を行って、「答と合同である ${\mathbb{F}}_p$ の元」を求めて演算結果にします（${\mathbb{F}}_p$ は、ここでは $\mathbb{Z}/p\mathbb{Z}$ で表される "整数の剰余類の集合" と同じ意味）。

除算は逆数（＝逆元）を乗算する演算で行います。${\mathbb{F}}_p$ においては 2.3b により、$0$ 以外の元に対して逆元（逆数）が存在します。2.3b を再掲すると次の通りです。

2.3b	逆数の存在：法が素数
$p$ を素数とする。$p$ 未満の自然数 $a$ に対して、 $a·b\equiv 1\left(modp\right)$ を満たす逆数 $b$ が $1\le b<p$ の範囲で一意に定まる。また、異なる $a$ に対する逆数 $b$ は異なる。

No.310 でやったように、${\mathbb{F}}_{13}$ の場合で "逆数" がどうなっているかを（＝ かけ算で $1$ になる場合を）計算してみると、

$\begin{array}{rr}1·& 1\equiv 1\left(mod13\right)\\ 2·& 7\equiv 1\left(mod13\right)\\ 3·& 9\equiv 1\left(mod13\right)\\ 4·& 10\equiv 1\left(mod13\right)\\ 5·& 8\equiv 1\left(mod13\right)\\ 6·& 11\equiv 1\left(mod13\right)\\ 7·& 2\equiv 1\left(mod13\right)\\ 8·& 5\equiv 1\left(mod13\right)\\ 9·& 3\equiv 1\left(mod13\right)\\ 10·& 4\equiv 1\left(mod13\right)\\ 11·& 6\equiv 1\left(mod13\right)\\ 12·& 12\equiv 1\left(mod13\right)\end{array}$

となります。以上のことから、${\mathbb{F}}_p$ においては加減乗除が定義できて有限体となるわけです。

ここで ${\mathbb{F}}_p$ から $0$ 元 を除いた「$p$ 未満の自然数の集合」を考えると、この集合では乗算と除算が定義できます。従って、この集合は「乗法群」になり、${\mathbb{F}}_p^{\ast }$ と表記します。ちなみに "群（group）" とは、何らかの二項演算 $\times$ があって、

（結合則）	$\left(a\times b\right)\times c=a\times \left(b\times c\right)$
（単位元）	$a\times 1=1\times a=a$ となる元 $1$ が存在
（逆元）	$a\times b=b\times a=1$ となる $b$ が、任意の $a$ について存在

の３つの条件を満たす、"演算が定義された集合" です。以降の記述は、すべて乗法群 ${\mathbb{F}}_p^{\ast }$ での演算とします。従って $\equiv$ は $=$ と書き、$\left(modp\right)$ は記述しません。

---

11. 位数（order）

---

${\mathbb{F}}_p^{\ast }$ における冪べき乗がどうなっているか、その例として ${\mathbb{F}}_{13}^{\ast }$ で計算してみます。まず、フェルマの小定理（3.1）により、${\mathbb{F}}_{13}^{\ast }$ の元 $a$ について、

$a^{12}=1$

が成り立ちます。つまり、すべての元は $12$ 乗すると $1$ になる。では、冪乗が $1$ になるためには必ず $12$ 乗しなければならないのでしょうか。ためしに $5$ の冪乗を（${\mathbb{F}}_{13}^{\ast }$ で）計算してみると、

$\begin{array}{ll}{5}^1& =5\\ 5^2& =12\\ 5^3& =8\\ 5^4& =1\\ 5^5& =5\\ 5^6& =12\\ 5^7& =8\\ 5^8& =1\\ 5^9& =5\\ 5^{10}& =12\\ 5^{11}& =8\\ 5^{12}& =1\end{array}$

となって、$5^4$ で $1$ になり、あとはそれが繰り返えされて、$5^{12}$ に至ってフェルマの小定理が示す $1$ になることがわかります。一方、$2$ の冪乗は、

$\begin{array}{ll}{2}^1& =2\\ 2^2& =4\\ 2^3& =8\\ 2^4& =3\\ 2^5& =6\\ 2^6& =12\\ 2^7& =11\\ 2^8& =9\\ 2^9& =5\\ 2^{10}& =10\\ 2^{11}& =7\\ 2^{12}& =1\end{array}$

となり、フェルマの小定理が示す $a^{12}=1$ より小さな冪乗では $1$ になりません。この "冪乗に関する元の振る舞いの違い" が以降のテーマです。

位数の定義

"冪乗に関する元の振る舞いの違い" を表すために、${\mathbb{F}}_p^{\ast }$ の各元に対して「位数（order）」を定義します。

11.1	位数の定義
${\mathbb{F}}_p^{\ast }$ の元 $a$ について、 $a^k=1$ となる最小の $k$ を $a$ の "位数（order）" と言う。

フェルマの小定理により $a^{p-1}=1$ であることが保証されているので、すべての元について何らかの位数が定義できます。先ほどの ${\mathbb{F}}_{13}^{\ast }$ の例だと、

$5$ の位数は $4$
$2$ の位数は $12$

です。位数になりうる数は、最小 $1$（$a=1$ の場合）、最大 $\left(p-1\right)$ の間で、次のようになります。

11.2	位数がとりうる値
$d$ が ${\mathbb{F}}_p^{\ast }$ のある元の位数とすると、$d$ は $\left(p-1\right)$ の約数である。

なぜなら、元 $a$ の位数が $d$ であるとき、$a$ の冪乗を順々に作っていくと $d$ 乗ごとに $1$ になります。一方、フェルマの小定理によって $a$ の $\left(p-1\right)$ 乗は必ず $1$ になるので、$d$ が $\left(p-1\right)$ の約数でないと矛盾が生じます。つまり、位数のバリエーションは $\left(p-1\right)$ の約数の個数しかありません。

このことは直感的理解が可能ですが、次の命題はステップを踏んだ証明が必要です。

位数が $\mathit{d}$ の元の個数

11.3
$\left(p-1\right)$ の約数の一つ $d$ の位数をもつ ${\mathbb{F}}_p^{\ast }$ の元があったとすると、位数 $d$ の元は $\phi \left(d\right)$ 個ある。$\phi \left(d\right)$ はオイラー関数。

これは、$\left(p-1\right)$ の約数 $d$ について、$d$ の位数をもつ ${\mathbb{F}}_p^{\ast }$ の元が $\phi \left(d\right)$ 個あることを主張するものではありません。そうではなく、もし位数 $\mathit{d}$ の元があったとしたら、そのような元は $\phi \left(d\right)$ 個あると言っています。11.3 を証明するために、位数 $\mathit{d}$ の元 $\mathit{a}$ があったとして、その $a$ の冪乗からなる次の数列を作ってみます。

$a^1\text{, }{a}^2\text{, }{a}^3\dots a^d\left(=1\right)$

以降、これを、

$a^k\left(1\le k\le d\right)$

と表記し、この $d$ 個の数列の性質を調べます。

11.3a
$a^k\left(1\le k\le d\right)$ の $d$ 個の元はすべて異なる。

$1\le i\text{, }j\le d$ として、もし

$a^j=a^i$

となったとします。両辺を $a^i$ で割ると（＝ $a^i$ の逆元を乗算すると）、

$a^{j-i}=1$

となりますが、$\left(j-i\right)<d$ なので、これは「$a$ 冪乗が $1$ になる最小の冪数が $d$」という位数の定義に反します。従って $a^k\left(1\le k\le d\right)$ はすべて異なっています。

11.3b
$a^k\left(1\le k\le d\right)$ の $d$ 個の元は、すべて $d$ 乗 すると $1$ になる。

これは ${\left(a^k\right)}^d={\left(a^d\right)}^k=1$ ということです。

11.3c
$d$ 乗 すると $1$ になる ${\mathbb{F}}_p^{\ast }$ の元は、$a^k\left(1\le k\le d\right)$ がそのすべてである。

$d$ 乗 すると $1$ になる元は $x^d=1$ という ${\mathbb{F}}_p^{\ast }$ における式を満たします。これはすなわち、有限体 ${\mathbb{F}}_p$ における $d$ 次方程式 $x^d-1=0$ の解です。

一般に、有限体 ${\mathbb{F}}_p$ において「$n$次方程式の解の数は高々 $n$個」という命題が成立します。数学的帰納法で考えると、まず1次方程式、$a_{1}x+a_0=0$ の解が1個なのは明らかなので $n=k$ の時に命題が成り立つと仮定します。そして $\left(k+1\right)$ 次多項式を、

とし、方程式 が解 $\alpha$ をもったとします。すると なので、 を $k$次多項式として、

と表現できます。なぜなら $\left(1\le i\le k+1\right)$ の範囲で、

$$\begin{gathered} x^i-{\alpha }^i= \\ \left(x-\alpha \right)\text{(}{x}^{i-1}+{\alpha }^1{x}^{i-2}+\text{ ⋯} \\ +{\alpha }^{i-2}x+{\alpha }^{i-1}\text{)} \end{gathered}$$

の因数分解が成り立つからです。帰納法の仮定により方程式 の解の数は高々 $k$個です。つまり 方程式 の解の数は高々 $k+1$ 個であり、命題は $n=k+1$ でも成立して帰納法による証明ができました。従って有限体 ${\mathbb{F}}_p$ における $d$ 次方程式 $x^d-1=0$ の解は 高々 $d$ 個です。

$a^k\left(1\le k\le d\right)$ は、

・	$d$ 個の、すべてが相異なる元であり（11.3a）
・	$d$ 乗すれば $1$（11.3b）

でした。このような元は ${\mathbb{F}}_p^{\ast }$ の中に高々 $d$ 個しかありません。従って、$d$ 乗 すると $1$ になる ${\mathbb{F}}_p^{\ast }$ の元は $a^k\left(1\le k\le d\right)$ の $d$ 個がそのすべてということになります。

11.3d
${\mathbb{F}}_p^{\ast }$ において位数 $d$ の元があったとしたら、それは $a^k\left(1\le k\le d\right)$ の中に含まれている。

位数 $d$ の元は $d$ 乗すると $1$ になります。一方、11.3c より $d$ 乗すると $1$ になる元は $a^k\left(1\le k\le d\right)$ がそのすべてです。つまり位数 $d$ の元があったとしたら、それは $a^k\left(1\le k\le d\right)$ に含まれることになります。

これはもちろん、$a^k\left(1\le k\le d\right)$ のすべての元の位数が $d$ ということではありません。各元の位数は $d$ かもしれないが、そうでない（＝ 位数が $d$ より小さい）かもしれない。ここで、$a^k\left(1\le k\le d\right)$ の各元の位数は次のように分類できます。

11.3e
$\gcd \left(j,d\right)\ne 1$ である $$ j$\left(1\le j\le d\right)$ をとると、$a^j$ の位数は $d$ より小さい。

$\gcd \left(j,d\right)=c>1$ とします。すると、２つの数 $s$ と $t$ を選んで、

$$\begin{gathered} j=cs\left(s<j\right) \\ d=ct\left(t<d\right) \end{gathered}$$

と書き表せます。ここで、$a^j$ の $t$ 乗をとると、

${\left(a^j\right)}^t=a^{cst}={\left(a^d\right)}^s=1$

となり、$a^j$ の位数は $t$ 以下であることが分かりますが、$t<d$ だったので、$a^j$ の位数は $d$ より小さいことになります。

11.3f
$\gcd \left(j,d\right)=1$ である $$ j$\left(1\le j<d\right)$ をとると、$a^j$ の位数は $d$ である。

${\left(a^j\right)}^k\left(1\le k\le d\right)$ がどうなるかを調べます。まず、$k=d$ のときは、11.3b により ${\left(a^j\right)}^k=1$ です。

次に $1\le k<d$ の場合ですが、このとき $jk$ は $d$ の倍数とはなりません。なぜなら、もし $d$ の倍数だとすると $d|\left(jk\right)$ ですが、$j$ と $d$ は互いに素なため、1.3a により $d|k$ となって矛盾が生じるからです。従って、ある数 $s$ と $t$ を選んで。

$jk=td+s\left(0<s<d\right)$

と表すことができます。そうすると、

$$\begin{gathered} {\left(a^j\right)}^k=a^{td+s} \\ \phantom{{\left(a^j\right)}^k}={\left(a^d\right)}^t·a^s \\ \phantom{{\left(a^j\right)}^k}=a^s\ne 1 \end{gathered}$$

となります。$s<d$ なので位数の定義により $a^s$ は $1$ にはならないのです。まとめると、

$$\begin{gathered} {\left(a^j\right)}^k\ne 1\left(1\le k<d\right) \\ {\left(a^j\right)}^k=1\left(k=d\right) \end{gathered}$$

となり、定義により $a^j$ の位数は $d$ です。結局、11.3e と 11.3f により、次のことが分かります。

11.3g
$a^k\left(1\le k\le d\right)$ の中には 位数 $d$ の元が $\phi \left(d\right)$ 個ある。

11.3e と 11.3f により、$\gcd \left(j,d\right)=1$ である $$ j$\left(1\le j<d\right)$ の場合だけ（＝ $j$ が $d$ と素なときだけ）$a^j$ の位数は $d$ であり、それ以外の $a^j$ の位数は $d$ より小さいことが分かりました。オイラー関数の定義から、$\mathit{d}$ 以下で $\mathit{d}$ と素な数は $\mathit{\phi }\mathit{}\left(\mathit{d}\right)$ 個です。つまり 11.3g が成り立ちます。

---

以上の 11.3d と 11.3g、つまり、${\mathbb{F}}_p^{\ast }$ の元 $a$ の位数を $d$ とするとき、

11.3d

${\mathbb{F}}_p^{\ast }$ において位数 $d$ の元があったとしたら、それは $a^k\left(1\le k\le d\right)$ の中に含まれる。

11.3g

$a^k\left(1\le k\le d\right)$ の中には 位数 $d$ の元が $\phi \left(d\right)$ 個ある。

の２つから、

11.3

$\left(p-1\right)$ の約数の一つ $d$ の位数をもつ ${\mathbb{F}}_p^{\ast }$ の元があったとすると、位数 $d$ の元は $\phi \left(d\right)$ 個ある。

が証明できました。

---

ここまでの考察を次のようにまとめることができます。

・	${\mathbb{F}}_p^{\ast }$ の各元の位数は $\left(p-1\right)$ の約数である（11.2）
・	位数 $d$ の元の個数は $\phi \left(d\right)$ か $0$ である（11.3）。

ここで 位数 $d$ の元の個数を $\mathrm{\#ord}\left(d\right)$ と書くことにします。$\mathrm{\#ord}\left(d\right)=\phi \left(d\right)$、もしくは $\mathrm{\#ord}\left(d\right)=0$ です。$d$ は $\left(p-1\right)$ の約数 のどれかでした。この記号を使うと次の通りとなります。

11.4
${\displaystyle \sum _{d|\left(p-1\right)}}\mathrm{\#ord}\left(d\right)=p-1$ ・  $\mathrm{\#ord}\left(d\right)$ は位数 $d$ の元の個数で、$\phi \left(d\right)$ か $0$ のとちらか。 ・  $d|\left(p-1\right)$ は、$\left(p-1\right)$ を割り切る $d$（＝ $p-1$ の約数である $d$）の全部についての総和をとる意味。

${\mathbb{F}}_p^{\ast }$ の元のすべてに位数が定義できます。ということは ${\mathbb{F}}_p^{\ast }$ の元を位数によってグループに分類できます。従って、各グループの元の個数の総和をとると、${\mathbb{F}}_p^{\ast }$ の元の個数である $p-1$ になる。11.4 の総和の式はそのことを言っています。

---

そこで次に、$\left(p-1\right)$ の個々の約数 $d$ について $\mathrm{\#ord}\left(d\right)$ が $\phi \left(d\right)$ か $0$ かが問題になりますが、それは次の「オイラー関数の総和定理」から分かります。

オイラー関数の総和定理

11.5	オイラー関数の総和
$N$ を任意の自然数とするとき、 ${\displaystyle \sum _{d|N}}\phi \left(d\right)=N$ が成り立つ。$d|N$ は $N$ の約数 $d$ すべてについての総和をとる。

この "総和定理" は、特に ${\mathbb{F}}_p^{\ast }$ や位数とは関係がなく、自然数一般についての定理です。この定理を証明する前提として、次の２つに注意します。まず、２つの自然数 $a$ と $b$ の最大公約数を $\gcd \left(a,b\right)$ とすると、

${\displaystyle \frac{a}{\gcd \left(a,b\right)}}$ と ${\displaystyle \frac{b}{\gcd \left(a,b\right)}}$ は互いに素

です。これは最大公約数の定義そのものであり、そういう風に決めたのが最大公約数でした。２番目に、$N$ の約数の一つが $a$ だとすると $N=a·b$ と表せますが、当然、$b$ も $N$ の約数の一つです。いま、$N$ が $r$ 個の約数をもつとします。すると、

$a_i\left(1\le i\le r\right)$ が $N$ のすべての約数であれば、$b_i={\displaystyle \frac{N}{a_i}}\left(1\le i\le r\right)$ も $N$ のすべての約数であり、つまり $b_i$ は $a_i$ を並び替えたものである

と言えます。この２つを前提に、まず $N=12$ の場合で考えます。いま、$1$ から $12$ の $12$ 個の整数を「$12$との最大公約数で分類する」ことを考えます。$12$ の約数 $d$ は、$1$、$2$、$3$、$4$、$6$、$12$ の $6$ つです。従って $1$ から $12$ の数を、$S_1,S_2,S_3,S_4,S_6,S_{12}$ の $6$ つのグループに分類します。すると各グループに含まれる整数は、

$\begin{array}{ll}{S}_1& =[ 1,5,7,11 ]\\ S_2& =[ 2,10 ]\\ S_3& =[ 3,9 ]\\ S_4& =[ 4,8 ]\\ S_6& =[ 6 ]\\ S_{12}& =[ 12 ]\end{array}$

となります。いま、各グループに含まれる整数の個数を ${\mathrm{\#S}}_d$ で表して、各グループの個数がどうなるかを見ていきます。まず、

${\mathrm{\#S}}_1=\phi \left(12\right)$

です。$S_1$ に含まれるのは、$12$との最大公約数が $1$ の整数（＝ $12$ と素な整数）なので、オイラー関数の定義により ${\mathrm{\#S}}_1$ は $\phi \left(12\right)=4$ です。

次に、$S_2$ に含まれる整数 $[ 2,10 ]$を、$12$ との最大公約数の $2$ で割り算した $[ 1,5 ]$ を考えると、これらの整数は $12$ を $2$ で割り算した $6$ と互いに素です。これは上に書いたように最大公約数の定義そのものです。従って、

${\mathrm{\#S}}_2=\phi \left(6\right)$

となります。同様にして、残りのグループについては、

$\begin{array}{ll}{\mathrm{\#S}}_3& =\phi \left(4\right)\\ {\mathrm{\#S}}_4& =\phi \left(3\right)\\ {\mathrm{\#S}}_6& =\phi \left(2\right)\\ {\mathrm{\#S}}_{12}& =\phi \left(1\right)\end{array}$

となります。$S_d$ は $12$個 の整数を分類したものだったので、そこに含まれる整数の総数は $12$ です。これにより、

$$\begin{gathered} \phi \left(12\right)+\phi \left(6\right)+\phi \left(4\right)+ \\ \phi \left(3\right)+\phi \left(2\right)+\phi \left(1\right)=12 \end{gathered}$$

が証明できました。これを総和の記号で書くと、

${\displaystyle \sum _{d|12}}\phi \left(d\right)=12$

です。

---

以上の説明では $N=12$ としましたが、$12$ という数に特別な意味はありません。従って、一般の $N$ の場合にも同様に証明ができます。

$N$ が $r$ 個の約数をもつとし、それらを $a_i\left(1\le i\le r\right)$ とします。集合 $S$ の元を $1$ から $N$ の 整数 $N$ 個とし、これらの $S$ の元を「$N$ との最大公約数で $r$ 個の部分集合に分ける」ことを考えます。つまり、$S$ の部分集合 $S_i\left(1\le i\le r\right)$ を、

$S_i$：$N$ との最大公約数が $a_i$ である $S$ の元の集合

とします。このとき $S_i$ の任意の元を $k$ とすると、最大公約数の定義により、

${\displaystyle \frac{k}{a_i}}$ は ${\displaystyle \frac{N}{a_i}}$ と互いに素

になります。そもそも、そのような元 $k$ を集めたのが $S_i$ なのでした。このことから、

$S_i$ の元の個数は、${\displaystyle \frac{N}{a_i}}$ と素である $S$ の元の個数

ということになります。${\mathit{S}}_{\mathit{i}}$ の元の個数を ${\mathit{\#S}}_{\mathit{i}}$ と書くと、

${\mathrm{\#S}}_i=\phi \left({\displaystyle \frac{N}{a_i}}\right)$

になります。ここで $b_i$ を、

$b_i={\displaystyle \frac{N}{a_i}}\left(1\le i\le r\right)$

と定義すると、

${\mathrm{\#S}}_i=\phi \left(b_i\right)$

となりますが、上に書いたように、この $b_i$ は $r$ 個の $N$ の約数のすべてであり、つまり $a_i$ を並び替えたものです。

ここで上式の両辺の $1$ から $r$ までの総和をとります。まず左辺の総和ですが、$S_i$ は $S$ を分類したものだったので、${\mathrm{\#S}}_i$ の総和は $S$ の元の総数である $N$ と等しくなります。つまり左辺の総和は、

${\displaystyle \sum _{i=1}^r}{\mathrm{\#S}}_i=N$

です。一方、右辺の総和は、

$\begin{array}{ll}{\displaystyle \sum _{i=1}^r}\phi \left(b_i\right)& ={\displaystyle \sum _{i=1}^r}\phi \left(a_i\right)\\ & ={\displaystyle \sum _{d|N}}\phi \left(d\right)\end{array}$

です。以上の左辺と右辺の総和が等しいことにより、11.5 の

${\displaystyle \sum _{d|N}}\phi \left(d\right)=N$

が証明できました。

位数 $\mathit{d}$ の元の存在定理

11.5 の "オイラー関数の総和定理" と 11.4 を合わせると、次の命題が証明できます。

11.6
${\mathbb{F}}_p^{\ast }$ において、$\left(\mathit{p}\mathit{-}\mathit{1}\right)$ の約数 $\mathit{d}$ のすべてについて位数 $\mathit{d}$ をもつ元が存在し、その個数は $\mathit{\phi }\mathit{}\left(\mathit{d}\right)$ 個である。

11.4 を振り返ってみると、

${\displaystyle \sum _{d|\left(p-1\right)}}\mathrm{\#ord}\left(d\right)=p-1$

・	$\mathrm{\#ord}\left(d\right)$ は位数 $d$ の元の個数で、$\phi \left(d\right)$ か $0$

でした。しかし 11.5 のオイラー関数の総和定理で $N=p-1$ とおくと、

${\displaystyle \sum _{d|\left(p-1\right)}}\phi \left(d\right)=p-1$

となります。これが何を意味するかというと、

${\mathbb{F}}_p^{\ast }$ においては、$\left(p-1\right)$ の約数 $d$ のすべてについて、位数 $d$ をもつ元の個数が $0$ になることはない。位数 $d$ をもつ元の個数は $\phi \left(d\right)$ 個である

ということです。ある位数 $d$ をもつ元の個数が $0$ だとするとオイラーの総和定理（11.5）が成り立たなくなるからです。位数 $d$ をもつ元の個数は $\phi \left(d\right)$ 個しかあり得ない。つまり、$\#ord\left(d\right)=\phi \left(d\right)$ です。これで 11.6 の証明ができました。この 11.6 から生成元の存在が証明でき、その個数が分かります。

---

12. 生成元と離散対数

---

11.6 からすぐに、次の「生成元の存在定理」が成り立ちます。これは19世紀ドイツの大数学者、ガウスが証明したものです。

12.1	生成元の存在
${\mathbb{F}}_p^{\ast }$ においては、位数が $\left(p-1\right)$ の元 $g$ が $\phi \left(p-1\right)$ 個存在する。 $g^k\left(1\le k\le p-1\right)$ はすべて相違し、総数が $\left(p-1\right)$ 個である ${\mathbb{F}}_p^{\ast }$ の元のすべてを尽くす。この $g$ を ${\mathbb{F}}_p^{\ast }$ の生成元（generator）と呼ぶ。

11.6 によると、$\left(p-1\right)$ の約数 $d$ のすべてについて位数 $d$ をもつ元が存在します。$\left(p-1\right)$ の約数の一つが $\left(p-1\right)$ なので、位数が $\left(p-1\right)$ の元が必ず存在します。これが生成元で、その個数は $\phi \left(p-1\right)$ です。

生成元は原始根（primitive root）とも言います。「11. 位数（order）」の最初に書いた例だと、${\mathbb{F}}_{13}^{\ast }$ において $2$ の位数は $12$ であり、生成元（の一つ）なのでした。計算してみると $6$、$7$、$11$ も生成元で、${\mathbb{F}}_{13}^{\ast }$ の生成元の個数は、合計 $\phi \left(12\right)=4$ です。

とにかく、${\mathbb{F}}_p^{\ast }$ の任意の元（＝ $\mathit{1}$ から $\mathit{p}\mathit{-}\mathit{1}$ の元）は生成元 $\mathit{g}$ の冪乗で表現でるきるわけです。つまり、次が成り立ちます。

12.2	離散対数
$g$ を ${\mathbb{F}}_p^{\ast }$ の生成元とする。${\mathbb{F}}_p^{\ast }$ の任意の元 $a$ について、 $g^b=a$ となる元 $b$ が一意に定まる。$b$ を $a$ の離散対数と呼び、 ${log}_g$ a$=b$ で表す。$g$ は離散対数の "底" である。

対数は普通、実数で定義されるものですが、${log}_g$ a$$ はそれと同等のことを整数で定義しています。実数は連続値ですが、整数は離散値をとります。そのため「離散対数」の呼び名があります。

実数の対数を計算する手法はいろいろありますが（初等的にはマクローリン級数など）、離散対数を計算する効率的手法は知られていません。特に、${\mathbb{F}}_p^{\ast }$ において $p$ が巨大な素数だと、実質的に計算が不可能になります。ここが、ディフィー・ヘルマンの鍵共有が成り立つ原理です。ディフィー・ヘルマンの鍵共有を、振り返ってみると次の通りです。まず、

$\left(p,g\right)$

・	$p$は巨大な素数
・	$g$は小さな生成元

のペアを「皆が使う公開鍵」として公開しておきます。演算は ${\mathbb{F}}_p^{\ast }$ で行います。$A$ さんと $B$ さんが秘密鍵を共有したい場合、

$A$ は $1<a<\left($ p$-1\right)$ である乱数 $a$ を発生させ、$g^a$ を $A$ の公開鍵として（盗聴されている通信路を介して） $B$ に送付

します。乱数 $a$ は $A$ の秘密鍵として秘匿します。次に同様に、

$B$ は $1<b<\left($ p$-1\right)$ である乱数 $b$ を発生させ、$g^b$ を $B$ の公開鍵として（盗聴されている通信路を介して） $A$ に送付

します。もちろん $b$ は秘匿します。そして、

$A$ は $G_a={\left(g^b\right)}^a$ を共有の秘密鍵

$B$ は $G_b={\left(g^a\right)}^b$ を共有の秘密鍵

とします。この作り方から $G_a=G_b$ となるので、秘密鍵 $G=g^{ab}$を共有できたことになり、以降はこれを使って暗号化通信を行います。$g$ が生成元であるため、$g^a$ や $g^b$ は、

$1<g^a\text{, }{g}^b<\left(p-1\right)$ の範囲に "バラける"

ことになります。「$g$ は小さな生成元」と書きましたが、生成元はたくさんあり（$\phi \left(p-1\right)$ 個もある！）、${\mathbb{F}}_{13}^{\ast }$ の場合のように $2$ が生成元となる場合が多い。その場合は $g=2$ として問題ありません（小さい生成元の方が実用的には冪剰余を計算しやすい。特に $2$）。生成元として $2$ を選んだとしても、巨大な数で冪乗をすると結果が "バラける" ことが数学的に保証されているからです。

離散対数を計算する効率的な手法は知られていないため、$p$ が 10進数で数百桁とか1000桁以上の数だと、$g^a$ や $g^b$ から $a$ や $b$ を知ることが実質的に不可能になります。これがディフィー・ヘルマンの鍵共有の原理です。

---

13. 生成元を使った暗号化通信

---

ディフィー・ヘルマンの鍵共有の原理を暗号化通信に使うこともできます（ElGamal 暗号）。まず、

$\left(p,g\right)$

・	$p$は巨大な素数
・	$g$は生成元

のペアを「皆が使う公開鍵」として公開しておきます。以下の演算はすべて ${\mathbb{F}}_p^{\ast }$ で行います。$B$ さんから $A$ さんにメッセージを暗号化して送りたい場合、次のようにします。平文を $\mathbb{P}$、暗号文を $\mathbb{C}$ とします。

$A$ は $1<a<\left($ p$-1\right)$ である乱数 $a$ を発生させ、$g^a$ を $A$ の公開鍵として $B$ に送付、ないしは公開

します。乱数 $a$ は $A$ の秘密鍵として秘匿します。$B$ がメッセージ $\mathbb{P}$ を暗号文にして $A$ に送る場合、

$B$ は（暗号文を送るたびに）$1<k<\left($ p$-1\right)$ である乱数 $k$ を発生させ、$\mathbb{C}=\left(g^k\text{, }\mathbb{P}·g^{ak}\right)$ を生成して $A$ に送付

します。$\mathbb{C}$ を受け取ると、

$A$ は $g^k$ と自分の秘密鍵 $a$ から $g^{ak}$ を計算できます。これを使ってメッセージ $\mathbb{P}$ を復号化

します。複号化は $g^{ak}$ の逆数（逆元）を乗算しますが、No.310 の「拡張ユークリッドの互除法」の 2.3a に書いたように、逆数の計算はたとえ $g^{ak}$ や $p$ が巨大数であっても効率的に可能です。

この暗号では暗号文を $\mathbb{P}·g^{ak}$ というようにシンプルに作っているので、$B$ はメッセージを送るたびに「１回限りの秘密鍵」である $k$ をランダムに発生させる必要があります。$B$ が自分の秘密鍵 $b$ と公開鍵 $g^b$ を持っていたとしても、それとは別にする必要がある。$k=b$ というように固定的にすると、複数の暗号文から盗聴者に容易に $g^{ab}$ を知られてしまいます。

これは「離散対数暗号」と呼ばれているものの一つの例ですが、ディフィー・ヘルマンの鍵共有と、暗号文の伝達を同時に行うものと言えます。

---

14. 生成元であることの証明

---

「ディフィー・ヘルマンの鍵共有」や「離散対数暗号」を実現するためには、巨大な素数 $p$ に対する ${\mathbb{F}}_p^{\ast }$ の生成元（のどれか）を知らなければなりません。これはどのように可能でしょうか。まず、

・	生成元は位数が $\left(p-1\right)$ の元であり 12.1
・	位数は $\left(p-1\right)$ の約数に限られる 11.2

ので、$\left(p-1\right)$ の素因数分解ができたとすると約数が分かり、位数の候補がリストアップできます。

一般に $d$ が 元 $a$（$\ne 1$。以降、$a\ne 1$ とします）の位数であることの証明は手間がかかります。$a$ の $d$ 乗が $1$ になったとしても $d$ が $a$ の位数だとは限りません。$d$ よりも小さな数 $e$ で $a^e=1$ となるかもしれないからです。しかし、$\mathit{d}$ が $\mathit{a}$ の位数ではないことは簡単に証明できます。

$a^d\ne 1$

を示せばよいからです。従って、$a$ が ${\mathbb{F}}_p^{\ast }$ の生成元であることを示すためには、$\left(p-1\right)$ の約数のうち $\left(p-1\right)$ 以外のすべての約数 $d$ について、$a^d\ne 1$ であることを示せればよい。すると消去法で、$a$ の位数は $\left(p-1\right)$ になります。この考えに基づき、簡単のために ${\mathbb{F}}_{73}^{\ast }$ で考えると、

$p-1=72=2^3·3^2$

なので $\left(p-1\right)$ の約数は $1$ と $72$ を含めて $4\times 3=12$ 個あります。従って $72$ と $1$ を除いた $10$ 個の約数 $d$ について

$a^d\ne 1$

であれば、$a$ の位数は $72$ しかありえず、$a$ は ${\mathbb{F}}_{73}^{\ast }$ の生成元です。しかし実は、これでは「計算のやりすぎ」になります。この場合、

$$\begin{gathered} a^{24}\ne 1 \\ {a}^{36}\ne 1 \end{gathered}$$

の２つだけが成り立てば、$a$ の位数は $72$ になります。なぜかというと、一般に次の命題が成立するからです。

14.1
${\mathbb{F}}_p^{\ast }$ において、$d$ が $\mathit{a}$ の位数ではないとすると、$\mathit{d}$ の任意の約数 $\mathit{e}$ も $\mathit{a}$ の位数ではない。

$e$ が $d$ の約数だとすると、ある数 $k$ があって $d=ke$ と表せます。このとき、

$a^e=1$ であるなら
$a^d=a^{ke}={\left(a^e\right)}^k=1$

です。このことの対偶をとると

$a^d\ne 1$ であるなら
$a^e\ne 1$

となり、これはつまり、

$d$ が $a$ の位数でないなら、$d$ の任意の約数 $e$ も $a$ の位数ではない

ことを意味します。$p-1=72$ の場合、$72$ を除く $72$（$=2^3·3^2$）の約数は、すべて $24$（$=2^3·3^1$） か $36$（$=2^2·3^2$）のどちらかの（あるいは両方の）約数になります。従って、

$$\begin{gathered} a^{24}\ne 1 \\ {a}^{36}\ne 1 \end{gathered}$$

が示せれば、$72$ を除く $72$ のすべての約数 $d$ について、

$a^d\ne 1$

となり、$d$ は $a$ の位数ではありません。この結果、$a$ の位数は $72$ しかあり得ず、$a$ は ${\mathbb{F}}_{73}^{\ast }$ の生成元であることになります。以上の考察を一般化すると、次の命題が成立します。

14.2
$p$ を素数とし、$\left(p-1\right)$ の素因数分解を、$q_i\left(1\le i\le r\right)$ を素因数として、 $p-1={q_1}^{{\alpha }_1}{q_2}^{{\alpha }_2}\dots {q_r}^{{\alpha }_r}$ と表す。ここで、 $m_i={\displaystyle \frac{p-1}{q_i}}$ とおくと、もし $1$ から $r$ までのすべての $i$ について、 $g^{m_i}\ne 1\left(1\le i\le r\right)$ が成り立つなら、$g$ は ${\mathbb{F}}_p^{\ast }$ の生成元である。

$\left(p-1\right)$ の約数で、$\left(p-1\right)$ 以外の任意の約数を $d$ とし、

$d={q_1}^{{\beta }_1}{q_2}^{{\beta }_2}\dots {q_r}^{{\beta }_r}$

と表します。ここで ${\beta }_i$ は、

$0\le {\beta }_i\le {\alpha }_i\left(1\le i\le r\right)$

です。そうすると、$d$ は $\left(p-1\right)$以外の$\left(p-1\right)$ の約数なので、

$d$ の素因数分解の中には、${\beta }_k<{\alpha }_k$ となる $k\left(1\le k\le r\right)$ が少なくとも１つある

ことになります。なぜなら、もしそのような $k$ がなければ $d=p-1$ だからです。そのような $k$ について、命題 14.2 で定義した、

$m_k={\displaystyle \frac{p-1}{q_k}}$

に着目すると、$d$ は $m_k$ の約数になります。なぜなら、$d$ と $m_k$ の「素因数ごとの冪乗数」を比較してみると、

${\beta }_i\le {\alpha }_i\left(1\le i\le r\text{, }i\ne k\right)$
${\beta }_k\le {\alpha }_k-1$ （仮定により ${\beta }_k<{\alpha }_k$ だから）

であり、$d$ のすべての素因数の冪乗数は $m_k$ の素因数の冪乗数以下です。つまり $m_k$ は $d$ で割り切れ、$d$ は $m_k$ の約数ということになります。

一方、命題 14.2 の仮定により、

$g^{m_k}\ne 1$

なので $m_k$ は $g$ の位数ではありません。従って、$m_k$ の約数である $d$ も 14.1 により $g$ の位数とはなりません。

$d$ は $\left(p-1\right)$ 以外の任意の$\left(p-1\right)$ の約数でした。ということは、$\left(p-1\right)$ 以外の $\left(p-1\right)$ の約数は $g$ の位数ではない。つまり消去法で、$g$ の位数は $\left(p-1\right)$ であり、$g$ は ${\mathbb{F}}_p^{\ast }$ の生成元であることが証明されました。

実際に生成元を求める

${\mathbb{F}}_p^{\ast }$ の元 $g$ をとったとき、それが生成元かどうかは 14.2 によって確かめることができます。しかしここで問題は、実用的なディフィー・ヘルマンの鍵共有では $p$ が巨大な素数であり、$\left(p-1\right)$ の素因数分解が実質的に不可能なことです。巨大数の素因数分解が困難なことは、まさにRSA暗号（No.310-311「高校数学で理解するRSA暗号の数理」）が成立する根拠でした。

そこで実際に生成元を求めるためには、$p$ を "作為的に" 決める必要があります。まず前提となるのは、ある数 $p$ が素数であるかどうかの判定法は種々あって（ミラー = ラビン素数判定法、など）、$p$ が巨大数であっても判定可能なことです。この前提のもとに、簡単な方法の例を一つあげますと、次の関係にあるような３つの数 $p$、$q$、$e$ を決めます。

$p=eq+1$

・	$p$、$q$ は巨大素数
・	$e$ は小さな偶数

$p$ と $q$ は10進数で数百桁から1000桁以上の巨大素数（＝ 奇数）、$e$ はたとえば$100$ 以下の（もっと絞れば $10$ 以下の）偶数です。具体的には、まず $q$ をランダムに選んで素数判定をし、素数であれば 次に $e$ を選んで $p$ が素数かどうかを判定するというプロセスになります。

こうすると $\left(p-1\right)$ の素因数分解は簡単にできるので、${\mathbb{F}}_p^{\ast }$ の任意の元 $g$ が生成元かどうかは 14.2 で判定できます。具体的には $g=2$ から始めて 順次 $g$ を増やしていって生成元を探索することになるでしょう。

以上は一つの例ですが、実際に実務で使う $p$ と $g$ については $g=2$ であると、コンピュータによる計算上、都合がよいわけです。従って、$2$ が生成元になる前提で $p$ を探索することになるでしょう。

---

ちなみに、現在、ディフィー・ヘルマンの鍵共有が実際に使われている例をあげておきます。インターネットを介してリモートのコンピュータ同士が安全に通信するための SSH（Secure Shell）という規格がありますが、そこで使われている公開鍵の一つ "diffie-hellman-group14-sha1"（2048ビットの素数 $p$ と生成元 $g$）を次に掲げます。これはインターネットの規格文書（RFC）に記載されています（RFC3526。16進表示）。この $p$ は $p=2q+1$ の形の素数で、10進では617桁です（ [...] はガウス記号で ... を超えない最大の整数）。

diffie-hellman-group14-sha1（2048bit）

p = $2^{2048}-2^{1984}-1+$$2^{64}\left(\left[2^{1918}\pi \right]+124476\right)$
=  3231700 6071311007
3003389139 2642382824 8817941241 1402391128 4200975140
0741706634 3542226196 8941736356 9347117901 7379097041
9175460587 3209195028 8537589861 8562215321 2175412514
9017745202 7023579607 8236248884 2461894775 8764110592
8646099411 7232454266 2252219323 0540919037 6805242355
1912567971 5870117001 0580558776 5103886184 7280257976
0549035697 3256152616 7081339361 7995413364 7655916036
8317896729 0731783845 8968063967 1900977202 1941686472
2587103141 1336429319 5361934716 3653320971 7077448227
9885885653 6920864529 6636077250 2689555059 2836275112
1174096972 9980684105 5435958486 6583291642 1362182310
7899099944 8652468262 4169720359 1185250704 5361090559

=
FFFFFFFF FFFFFFFF C90FDAA2 2168C234 C4C6628B 80DC1CD1
29024E08 8A67CC74 020BBEA6 3B139B22 514A0879 8E3404DD
EF9519B3 CD3A431B 302B0A6D F25F1437 4FE1356D 6D51C245
E485B576 625E7EC6 F44C42E9 A637ED6B 0BFF5CB6 F406B7ED
EE386BFB 5A899FA5 AE9F2411 7C4B1FE6 49286651 ECE45B3D
C2007CB8 A163BF05 98DA4836 1C55D39A 69163FA8 FD24CF5F
83655D23 DCA3AD96 1C62F356 208552BB 9ED52907 7096966D
670C354E 4ABC9804 F1746C08 CA18217C 32905E46 2E36CE3B
E39E772C 180E8603 9B2783A2 EC07A28F B5C55DF0 6F4C52C9
DE2BCBF6 95581718 3995497C EA956AE5 15D22618 98FA0510
15728E5A 8AACAA68 FFFFFFFF FFFFFFFF

g = 2

---

ディフィー・ヘルマンの鍵共有の安全性ですが、離散対数問題を効率的に解くアルゴリズムはないと、数学的に証明されているわけではありません。ただ、RSA暗号の根拠になっている素因数分解のアルゴリズムと同じように、こういった数論の極めて基本的で、昔からある普遍的な問題は、世界の多くの数学者が関わってきています。それでも効率的に解くアルゴリズムは知られていません。ブログのタイトルを「高校数学で理解する」とましたが、そのような基礎的な数学しか使っていないからこそ暗号が成り立っている。そう言えると思います。

---

ディフィー・ヘルマンの鍵共有は公開鍵暗号の発端となったものですが、上にあげたように現在でも使われています（DHと略記される）。ただ、公開鍵暗号の優秀性は、「解読の困難性」と「暗号化・複号化計算の容易性」という二律背反の要求をいかに両立させるかにあります。その意味で、ディフィー・ヘルマン以降、各種の公開鍵暗号が開発されてきました。離散対数問題を使った暗号で言うと、よく使われるのは "楕円暗号（楕円曲線暗号）" です。これは「楕円曲線上の有理点がつくる "加法群" での離散対数問題」を利用した暗号です。しかし基本的な考え方はディフィー・ヘルマンの鍵共有と同じです。その意味で、公開鍵暗号の発端となった発明の意義は、今も続いているのでした。

---

まとめ

---

以上の 「ディフィー・ヘルマンの鍵共有」をまとめると、次のようになるでしょう。

◆	公開鍵暗号の発端となった "ディフィー・ヘルマンの鍵共有" は、離散対数問題を解く困難さ（＝実質的に不可能）を根拠とする暗号である。
◆	"ディフィー・ヘルマンの鍵共有" は、有限体（乗法群）やその生成元の存在など（ガウスにさかのぼる）数論の基本のところをベースにできている。
◆	RSA暗号（No.310-311）から通して振り返ってみると、そこでの前提知識は加減乗除と冪乗のルール程度であり、そこから論理を積み重ねていって公開鍵暗号の成立性が証明できる。つまり高校数学程度の知識があれば十分理解できる。

No.310-311 のRSA暗号と同じく、この最後の点がこの記事の目的なのでした。

---

---

タグ：RSA暗号 オイラー関数 有限体 位数 乗法群 オイラー関数の総和 公開鍵暗号 ディフィー・ヘルマンの鍵共有 生成元 素数 冪乗 逆元 離散対数 楕円曲線暗号 ガウス