No.313 - 高校数学で理解する公開鍵暗号の数理 [科学]
No.310-311「高校数学で理解するRSA暗号の数理」の続きです。公開鍵暗号の "老舗" である RSA暗号は、1978年に MIT の研究者であったリベスト(米)、シャミア(イスラエル)、エーデルマン(米)の3人によって発明されました(RSAは3人の頭文字)。3人はこの功績によって2002年のチューリング賞を受賞しました。チューリング賞は計算機科学分野の国際学会である ACM(Association of Computing Machinary)が毎年授与している賞で、この分野では最高の栄誉とされているものです。
しかし公開鍵暗号そのもののアイデアを最初に提示したのは、スタンフォード大学の研究者だったディフィー(米)とヘルマン(米)で、1976年のことでした。2人も 2015年にチューリング賞を受賞しています。この「鍵を公開する」という、画期的というか逆転の発想である公開鍵暗号の登場以降、暗号の研究は一変してしまいました。そして RSA暗号のみならず各種の公開鍵暗号が開発され、現代のインターネットの基盤になっています。たとえばインターネットのWebサーバへのアクセス(閲覧やフォーム入力など)で使われる SSL/TSL という暗号化通信(https:// のサイトで使われる)は、まさに公開鍵方式を使っています。
今回はその公開鍵暗号を "発明した" ディフィーとヘルマンに敬意を表して、彼らが発表した内容と、その数学的背景を書いてみたいと思います。タイトルは「公開鍵暗号の数理」としましたが、あくまで公開鍵暗号の原点となったアイデアの解説です。
ディフィーとヘルマンが提出したアイデアは「公開鍵を使って秘密鍵を安全に共有する」ものでした。これは「ディフィー・ヘルマンの鍵共有」と呼ばれていて、現在でも使われています。そこでまず「秘密鍵の共有」の意義を振り返ってみたいと思います。
秘密鍵の共有
古今東西、様々な暗号化方式が開発・使用されてきましたが「秘密鍵の共有による暗号」(=共通鍵暗号)が基本です。その中でも「一回限りの乱数表」は安全(=解読されない)と証明されている暗号です。この場合、乱数表が秘密鍵に相当します。
英大文字・小文字、数字、英文に使われる特殊文字を、 の数字でコード化するとします。いま、 文字以下の平文をコード化して暗号文にしたいとき、「一回限りの乱数表」として必要なのは、 の値をとる乱数が 個並んだ表です。さらに、
とするとき、「乱数 の値に依存して、 を に1対1に変換する関数 」を決めておきます。そうすると、
の変換で暗号文 が得られます。この関数 は の コード変換テーブルでもいいし、 のような四則演算でもよい。とにかく が違えば別の1対1変換になる関数が条件で、そうすれば逆変換で複号化が可能です。この関数を秘密にする必要はなく、オープンにしてもかまいません。この暗号が安全な理由は、
の2点によります。もちろん乱数が "真の乱数" であることも重要です。しかし、上の2点を守るためには秘密鍵(乱数表)の長さが膨大になります。使い終わった乱数表のページを破って捨てなければならないからです。そこで実用的には、暗号文のやりとりを始める前に秘密鍵を共有しておき、暗号化はその「秘密鍵にもとづいた何らかの暗号化方式」で行うことになります。こうすると平文の長さが秘密鍵より長くなるので、絶対に安全とは言えなくなります。そこで、解読しにくい(=強度の高い)暗号化方式の必要性があり、これをめぐって様々な方式が作られてきました。
しかし問題は、最初の「秘密鍵の共有」をどうやってやるかです。結局、秘密鍵を印刷し、アタッシュケースに入れて相手に持参するというような、スパイ映画にでも出てきそうな方法しか本質的には無いわけです。どういうやり方をとるにせよ「秘密鍵の共有」には多大なコストがかかる。
No.310-311「高校数学で理解するRSA暗号の数理」で書いた公開鍵暗号の価値はそういうところにあります。つまり、RSA暗号における暗号化・複号化は巨大な数の "冪剰余" を求める計算になり、これはこれで計算機負荷が高い。そこで、まずRSA暗号を使って秘密鍵を生成・共有しておき、以降はその秘密鍵を使う高速な(= 計算機負荷の低い)暗号化・複号化方式で通信をするやり方が多くとられます。もちろんその秘密鍵は通信が一段落したら捨てて、次の通信では新たな秘密鍵を生成して共有するわけです。これは他の公開鍵暗号でも同じです。
その、"公開鍵を使って秘密鍵を共有する" ことを最初に提唱したのが「ディフィー・ヘルマンの鍵共有」でした。そしてこれが、そもそもの「公開鍵の発明」になりました。この鍵共有は、
ためのアルゴリズムです。どうしてそんなことができるのかが、以降です。
9. ディフィー・ヘルマンの鍵共有
ディフィー・ヘルマンの鍵共有は次のように進みます。まず「公開鍵センター」が "皆が使う公開鍵"として、
のペアを公開しておきます。次に、 さんと さんが秘密鍵を共有したい場合、
します。乱数a は A の秘密鍵として秘匿します。次に同様に、
B は、1 < b < p - 1 である乱数 b を発生させ、g b mod p を B の公開鍵として(盗聴されている通信路を介して) A に送付
します。もちろんb は秘匿します。そして、
A は G a = g b a mod p を共有の秘密鍵
B は G b = g a b mod p を共有の秘密鍵
とします。この作り方からG a = G b となるので、秘密鍵 G = g a ⁢ b mod p が共有できたことになり、以降はこれを使って暗号化通信を行います。大切なことは A は B の秘密鍵(b )を知らないし、B は A の秘密鍵(a )を知らないことです。それでも秘密鍵 G (= G a = G b )を共有できるわけです。
以上の仕組みにおいて通信路が盗聴されたとしても安全なのは、A の公開鍵 g a から a を求めるのが困難なことと、同様に g b から b を求めるのが困難なことです。なぜ困難かとい言うと、一つは p が巨大な素数だからであり(10進数で数百桁か 1000桁以上)、また g が「生成元」(原始根ともいう)だからです。
以降でその「生成元」とは何か、盗聴者が公開鍵からA と B の秘密鍵(a と b )をなぜ計算できないのかという、ディフィー・ヘルマンの鍵共有の数学的背景を概観します。以下の説明では「高校数学程度の知識だけ」を前提としますが(= タイトルの "高校数学で理解する" の意味)、No.310-311「高校数学で理解するRSA暗号の数理」での各種説明は既知とします。特に、
の知識を前提とします。
10. 有限体(F p )と乗法群(F p ∗ )
一般に加減乗除が定義された集合を "体(Field)" と言います。有理数、実数、複素数は "体" です。さらに No.310「高校数学で理解するRSA暗号の数理(1)」の終わりの方に書いたように、p を素数とし、p 未満の自然数と 0 を合わせた集合も "体" となり、F p で表します。この集合は元の数が有限なので、有限体です。
F p における演算は、加算・減算・乗算については普通の整数のように行い、その答に対してmod p の演算を行って、「答と合同である F p の元」を求めて演算結果にします(F p は、ここでは Z / p Z で表される "整数の剰余類の集合" と同じ意味)。
除算は逆数(=逆元)を乗算する演算で行います。F p においては 2.3b により、0 以外の元に対して逆元(逆数)が存在します。2.3b を再掲すると次の通りです。
No.310 でやったように、F 13 の場合で "逆数" がどうなっているかを(= かけ算で 1 になる場合を)計算してみると、
1 · 1 ≡ 1 mod 13
2 · 7 ≡ 1 mod 13
3 · 9 ≡ 1 mod 13
4 · 10 ≡ 1 mod 13
5 · 8 ≡ 1 mod 13
6 · 11 ≡ 1 mod 13
7 · 2 ≡ 1 mod 13
8 · 5 ≡ 1 mod 13
9 · 3 ≡ 1 mod 13
10 · 4 ≡ 1 mod 13
11 · 6 ≡ 1 mod 13
12 · 12 ≡ 1 mod 13
となります。以上のことから、F p においては加減乗除が定義できて有限体となるわけです。
ここでF p から 0 元 を除いた「p 未満の自然数の集合」を考えると、この集合では乗算と除算が定義できます。従って、この集合は「乗法群」になり、F p ∗ と表記します。ちなみに "群(group)" とは、何らかの二項演算 × があって、
の3つの条件を満たす、"演算が定義された集合" です。以降の記述は、すべて乗法群F p ∗ での演算とします。従って ≡ は = と書き、mod p は記述しません。
11. 位数(order)
F p ∗ における冪乗がどうなっているか、その例として F 13 ∗ で計算してみます。まず、フェルマの小定理(3.1)により、F 13 ∗ の元 a について、
a 12 = 1
が成り立ちます。つまり、すべての元は12 乗すると 1 になる。では、冪乗が 1 になるためには必ず 12 乗しなければならないのでしょうか。ためしに 5 の冪乗を(F 13 ∗ で)計算してみると、
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
となって、5 4 で 1 になり、あとはそれが繰り返えされて、5 12 に至ってフェルマの小定理が示す 1 になることがわかります。一方、2 の冪乗は、
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
となり、フェルマの小定理が示すa 12 = 1 より小さな冪乗では 1 になりません。この "冪乗に関する元の振る舞いの違い" が以降のテーマです。
"冪乗に関する元の振る舞いの違い" を表すために、F p ∗ の各元に対して「位数(order)」を定義します。
フェルマの小定理によりa p - 1 = 1 であることが保証されているので、すべての元について何らかの位数が定義できます。先ほどの F 13 ∗ の例だと、
5 の位数は 4
2 の位数は 12
です。位数になりうる数は、最小1 (a = 1 の場合)、最大 p - 1 の間で、次のようになります。
なぜなら、元a の位数が d であるとき、a の冪乗を順々に作っていくと d 乗ごとに 1 になります。一方、フェルマの小定理によって a の p - 1 乗は必ず 1 になるので、d が p - 1 の約数でないと矛盾が生じます。つまり、位数のバリエーションは p - 1 の約数の個数しかありません。
このことは直感的理解が可能ですが、次の命題はステップを踏んだ証明が必要です。
これは、p - 1 の約数 d について、d の位数をもつ F p ∗ の元が φ ⁡ d 個あることを主張するものではありません。そうではなく、もし位数 d の元があったとしたら、そのような元は φ ⁡ d 個あると言っています。11.3 を証明するために、位数 d の元 a があったとして、その a の冪乗からなる次の数列を作ってみます。
a 1 , a 2 , a 3 … a d = 1
以降、これを、
a k 1 ≤ k ≤ d
と表記し、このd 個の数列の性質を調べます。
1 ≤ i , j ≤ d として、もし
a j = a i
となったとします。両辺をa i で割ると(= a i の逆元を乗算すると)、
a j - i = 1
となりますが、j - i < d なので、これは「a 冪乗が 1 になる最小の冪数が d 」という位数の定義に反します。従って a k 1 ≤ k ≤ d はすべて異なっています。
これはa k d = a d k = 1 ということです。
d 乗 すると 1 になる元は x d = 1 という F p ∗ における式を満たします。これはすなわち、有限体 F p における d 次方程式 x d - 1 = 0 の解です。
一般に、有限体F p において「n 次方程式の解の数は高々 n 個」という命題が成立します。数学的帰納法で考えると、まず1次方程式、a 1 ⁢ x + a 0 = 0 の解が1個なのは明らかなので n = k の時に命題が成り立つと仮定します。そして k + 1 次多項式を、
f k + 1 ⁡ x = a k + 1 ⁢ x k + 1 + a k ⁢ x k + ⋯
+ a 1 ⁢ x + a 0 a k + 1 ≠ 0
とし、方程式f k + 1 ⁡ x = 0 が解 α をもったとします。すると f k + 1 ⁡ α = 0 なので、g k ⁡ x を k 次多項式として、
f k + 1 ⁡ x = f k + 1 ⁡ x - f k + 1 ⁡ α
= x - α ⁢ g k ⁡ x
と表現できます。なぜなら1 ≤ i ≤ k + 1 の範囲で、
x i - α i =
x - α ⁢ ( x i - 1 + α 1 ⁢ x i - 2 + ⋯
+ α i - 2 ⁢ x + α i - 1 )
の因数分解が成り立つからです。帰納法の仮定により方程式g k ⁡ x = 0 の解の数は高々 k 個です。つまり 方程式 f k + 1 ⁡ x = 0 の解の数は高々 k + 1 個であり、命題は n = k + 1 でも成立して帰納法による証明ができました。従って有限体 F p における d 次方程式 x d - 1 = 0 の解は 高々 d 個です。
a k 1 ≤ k ≤ d は、
でした。このような元はF p ∗ の中に高々 d 個しかありません。従って、d 乗 すると 1 になる F p ∗ の元は a k 1 ≤ k ≤ d の d 個がそのすべてということになります。
位数d の元は d 乗すると 1 になります。一方、11.3c より d 乗すると 1 になる元は a k 1 ≤ k ≤ d がそのすべてです。つまり位数 d の元があったとしたら、それは a k 1 ≤ k ≤ d に含まれることになります。
これはもちろん、a k 1 ≤ k ≤ d のすべての元の位数が d ということではありません。各元の位数は d かもしれないが、そうでない(= 位数が d より小さい)かもしれない。ここで、a k 1 ≤ k ≤ d の各元の位数は次のように分類できます。
gcd ⁡ j d = c > 1 とします。すると、2つの数 s と t を選んで、
j = c ⁢ s s < j
d = c ⁢ t t < d
と書き表せます。ここで、a j の t 乗をとると、
a j t = a c ⁢ s ⁢ t =
a d s = 1
となり、a j の位数は t 以下であることが分かりますが、t < d だったので、a j の位数は d より小さいことになります。
a j k 1 ≤ k ≤ d がどうなるかを調べます。まず、k = d のときは、11.3b により a j k = 1 です。
次に1 ≤ k < d の場合ですが、このとき j ⁢ k は d の倍数とはなりません。なぜなら、もし d の倍数だとすると d | j ⁢ k ですが、j と d は互いに素なため、1.3a により d | k となって矛盾が生じるからです。従って、ある数 s と t を選んで。
j ⁢ k = t ⁢ d + s 0 < s < d
と表すことができます。そうすると、
a j k
= a t ⁢ d + s
a j k
= a d t · a s
a j k
= a s ≠ 1
となります。s < d なので位数の定義により a s は 1 にはならないのです。まとめると、
a j k ≠ 1
1 ≤ k < d
a j k = 1
k = d
となり、定義によりa j の位数は d です。結局、11.3e と 11.3f により、次のことが分かります。
11.3e と 11.3f により、gcd ⁡ j d = 1 である j 1 ≤ j < d の場合だけ(= j が d と素なときだけ)a j の位数は d であり、それ以外の a j の位数は d より小さいことが分かりました。オイラー関数の定義から、d 以下で d と素な数は φ ⁡ d 個です。つまり 11.3g が成り立ちます。
以上の 11.3d と 11.3g、つまり、F p ∗ の元 a の位数を d とするとき、
11.3d
F p ∗ において位数 d の元があったとしたら、それは a k 1 ≤ k ≤ d の中に含まれる。
11.3g
a k 1 ≤ k ≤ d の中には 位数 d の元が φ ⁡ d 個ある。
の2つから、
11.3
p - 1 の約数の一つ d の位数をもつ F p ∗ の元があったとすると、位数 d の元は φ ⁡ d 個ある。
が証明できました。
ここまでの考察を次のようにまとめることができます。
ここで 位数d の元の個数を #ord ⁡ d と書くことにします。#ord ⁡ d = φ ⁡ d 、もしくは #ord ⁡ d = 0 です。d は p - 1 の約数 のどれかでした。この記号を使うと次の通りとなります。
F p ∗ の元のすべてに位数が定義できます。ということは F p ∗ の元を位数によってグループに分類できます。従って、各グループの元の個数の総和をとると、F p ∗ の元の個数である p - 1 になる。11.4 の総和の式はそのことを言っています。
そこで次に、p - 1 の個々の約数 d について #ord ⁡ d が φ ⁡ d か 0 かが問題になりますが、それは次の「オイラー関数の総和定理」から分かります。
この "総和定理" は、特にF p ∗ や位数とは関係がなく、自然数一般についての定理です。この定理を証明する前提として、次の2つに注意します。まず、2つの自然数 a と b の最大公約数を gcd ⁡ a b とすると、
a gcd ⁡ a b と b gcd ⁡ a b は互いに素
です。これは最大公約数の定義そのものであり、そういう風に決めたのが最大公約数でした。2番目に、N の約数の一つが a だとすると N = a · b と表せますが、当然、b も N の約数の一つです。いま、N が r 個の約数をもつとします。すると、
a i 1 ≤ i ≤ r が N のすべての約数であれば、b i = N a i 1 ≤ i ≤ r も N のすべての約数であり、つまり b i は a i を並び替えたものである
と言えます。この2つを前提に、まず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 つのグループに分類します。すると各グループに含まれる整数は、
S 1 = 1 5 7 11
S 2 = 2 10
S 3 = 3 9
S 4 = 4 8
S 6 = 6
S 12 = 12
となります。いま、各グループに含まれる整数の個数を#S d で表して、各グループの個数がどうなるかを見ていきます。まず、
#S 1 = φ ⁡ 12
です。S 1 に含まれるのは、12 との最大公約数が 1 の整数(= 12 と素な整数)なので、オイラー関数の定義により #S 1 は φ ⁡ 12 = 4 です。
次に、S 2 に含まれる整数 2 10 を、12 との最大公約数の 2 で割り算した 1 5 を考えると、これらの整数は 12 を 2 で割り算した 6 と互いに素です。これは上に書いたように最大公約数の定義そのものです。従って、
#S 2 = φ ⁡ 6
となります。同様にして、残りのグループについては、
#S 3 = φ ⁡ 4
#S 4 = φ ⁡ 3
#S 6 = φ ⁡ 2
#S 12 = φ ⁡ 1
となります。S d は 12 個 の整数を分類したものだったので、そこに含まれる整数の総数は 12 です。これにより、
φ ⁡ 12 + φ ⁡ 6 + φ ⁡ 4 +
φ ⁡ 3 + φ ⁡ 2 + φ ⁡ 1
= 12
が証明できました。これを総和の記号で書くと、
∑
d | 12
φ ⁡ d = 12
です。
以上の説明ではN = 12 としましたが、12 という数に特別な意味はありません。従って、一般の N の場合にも同様に証明ができます。
N が r 個の約数をもつとし、それらを a i 1 ≤ i ≤ r とします。集合 S の元を 1 から N の 整数 N 個とし、これらの S の元を「N との最大公約数で r 個の部分集合に分ける」ことを考えます。つまり、S の部分集合 S i 1 ≤ i ≤ r を、
S i :N との最大公約数が a i である S の元の集合
とします。このときS i の任意の元を k とすると、最大公約数の定義により、
k a i は
N a i と互いに素
になります。そもそも、そのような元k を集めたのが S i なのでした。このことから、
S i の元の個数は、N a i と素である S の元の個数
ということになります。S i の元の個数を #S i と書くと、
#S i = φ ⁡ N a i
になります。ここでb i を、
b i = N a i 1 ≤ i ≤ r
と定義すると、
#S i = φ ⁡ b i
となりますが、上に書いたように、このb i は r 個の N の約数のすべてであり、つまり a i を並び替えたものです。
ここで上式の両辺の1 から r までの総和をとります。まず左辺の総和ですが、S i は S を分類したものだったので、#S i の総和は S の元の総数である N と等しくなります。つまり左辺の総和は、
∑
i = 1
r
#S i = N
です。一方、右辺の総和は、
∑
i = 1
r
φ ⁡ b i
=
∑
i = 1
r
φ ⁡ a i
=
∑
d | N
φ ⁡ d
です。以上の左辺と右辺の総和が等しいことにより、11.5 の
∑
d | N
φ ⁡ d = N
が証明できました。
11.5 の "オイラー関数の総和定理" と 11.4 を合わせると、次の命題が証明できます。
11.4 を振り返ってみると、
∑
d | p - 1
#ord ⁡ d = p - 1
でした。しかし 11.5 のオイラー関数の総和定理でN = p - 1 とおくと、
∑
d | p - 1
φ ⁡ d = p - 1
となります。これが何を意味するかというと、
F p ∗ においては、p - 1 の約数 d のすべてについて、位数 d をもつ元の個数が 0 になることはない。位数 d をもつ元の個数は φ ⁡ d 個である
ということです。ある位数d をもつ元の個数が 0 だとするとオイラーの総和定理(11.5)が成り立たなくなるからです。位数 d をもつ元の個数は φ ⁡ d 個しかあり得ない。つまり、#ord ⁡ d = φ ⁡ d です。これで 11.6 の証明ができました。この 11.6 から生成元の存在が証明でき、その個数が分かります。
12. 生成元と離散対数
11.6 からすぐに、次の「生成元の存在定理」が成り立ちます。これは19世紀ドイツの大数学者、ガウスが証明したものです。
11.6 によると、p - 1 の約数 d のすべてについて位数 d をもつ元が存在します。p - 1 の約数の一つが p - 1 なので、位数が p - 1 の元が必ず存在します。これが生成元で、その個数は φ ⁡ p - 1 です。
生成元は原始根(primitive root)とも言います。「11. 位数(order)」の最初に書いた例だと、F 13 ∗ において 2 の位数は 12 であり、生成元(の一つ)なのでした。計算してみると 6 、7 、11 も生成元で、F 13 ∗ の生成元の個数は、合計 φ ⁡ 12 = 4 です。
とにかく、F p ∗ の任意の元(= 1 から p - 1 の元)は生成元 g の冪乗で表現でるきるわけです。つまり、次が成り立ちます。
対数は普通、実数で定義されるものですが、log g ⁡ a はそれと同等のことを整数で定義しています。実数は連続値ですが、整数は離散値をとります。そのため「離散対数」の呼び名があります。
実数の対数を計算する手法はいろいろありますが(初等的にはマクローリン級数など)、離散対数を計算する効率的手法は知られていません。特に、F p ∗ において p が巨大な素数だと、実質的に計算が不可能になります。ここが、ディフィー・ヘルマンの鍵共有が成り立つ原理です。ディフィー・ヘルマンの鍵共有を、振り返ってみると次の通りです。まず、
p g
のペアを「皆が使う公開鍵」として公開しておきます。演算はF p ∗ で行います。A さんと B さんが秘密鍵を共有したい場合、
A は 1 < a < p - 1 である乱数 a を発生させ、g a を A の公開鍵として(盗聴されている通信路を介して) B に送付
します。乱数a は A の秘密鍵として秘匿します。次に同様に、
B は 1 < b < p - 1 である乱数 b を発生させ、g b を B の公開鍵として(盗聴されている通信路を介して) A に送付
します。もちろんb は秘匿します。そして、
A は G a = g b a を共有の秘密鍵
B は G b = g a b を共有の秘密鍵
とします。この作り方からG a = G b となるので、秘密鍵 G = g a ⁢ b を共有できたことになり、以降はこれを使って暗号化通信を行います。g が生成元であるため、g a や g b は、
1 < g a , g b < p - 1 の範囲に "バラける"
ことになります。「g は小さな生成元」と書きましたが、生成元はたくさんあり(φ ⁡ p - 1 個もある!)、F 13 ∗ の場合のように 2 が生成元となる場合が多い。その場合は g = 2 として問題ありません(小さい生成元の方が実用的には冪剰余を計算しやすい。特に 2 )。生成元として 2 を選んだとしても、巨大な数で冪乗をすると結果が "バラける" ことが数学的に保証されているからです。
離散対数を計算する効率的な手法は知られていないため、p が 10進数で数百桁とか1000桁以上の数だと、g a や g b から a や b を知ることが実質的に不可能になります。これがディフィー・ヘルマンの鍵共有の原理です。
13. 生成元を使った暗号化通信
ディフィー・ヘルマンの鍵共有の原理を暗号化通信に使うこともできます(ElGamal 暗号)。まず、
p g
のペアを「皆が使う公開鍵」として公開しておきます。以下の演算はすべてF p ∗ で行います。B さんから A さんにメッセージを暗号化して送りたい場合、次のようにします。平文を P 、暗号文を C とします。
A は 1 < a < p - 1 である乱数 a を発生させ、g a を A の公開鍵として B に送付、ないしは公開
します。乱数a は A の秘密鍵として秘匿します。B がメッセージ P を暗号文にして A に送る場合、
B は(暗号文を送るたびに)1 < k < p - 1 である乱数 k を発生させ、C = g k , P · g a ⁢ k を生成して A に送付
します。C を受け取ると、
A は g k と自分の秘密鍵 a から g a ⁢ k を計算できます。これを使ってメッセージ P を復号化
します。複号化はg a ⁢ k の逆数(逆元)を乗算しますが、No.310 の「拡張ユークリッドの互除法」の 2.3a に書いたように、逆数の計算はたとえ g a ⁢ k や p が巨大数であっても効率的に可能です。
この暗号では暗号文をP · g a ⁢ k というようにシンプルに作っているので、B はメッセージを送るたびに「1回限りの秘密鍵」である k をランダムに発生させる必要があります。B が自分の秘密鍵 b と公開鍵 g b を持っていたとしても、それとは別にする必要がある。k = b というように固定的にすると、複数の暗号文から盗聴者に容易に g a ⁢ b を知られてしまいます。
これは「離散対数暗号」と呼ばれているものの一つの例ですが、ディフィー・ヘルマンの鍵共有と、暗号文の伝達を同時に行うものと言えます。
14. 生成元であることの証明
「ディフィー・ヘルマンの鍵共有」や「離散対数暗号」を実現するためには、巨大な素数p に対する F p ∗ の生成元(のどれか)を知らなければなりません。これはどのように可能でしょうか。まず、
ので、p - 1 の素因数分解ができたとすると約数が分かり、位数の候補がリストアップできます。
一般にd が 元 a (≠ 1 。以降、a ≠ 1 とします)の位数であることの証明は手間がかかります。a の d 乗が 1 になったとしても d が a の位数だとは限りません。d よりも小さな数 e で a e = 1 となるかもしれないからです。しかし、d が a の位数ではないことは簡単に証明できます。
a d ≠ 1
を示せばよいからです。従って、a が F p ∗ の生成元であることを示すためには、p - 1 の約数のうち p - 1 以外のすべての約数 d について、a d ≠ 1 であることを示せればよい。すると消去法で、a の位数は p - 1 になります。この考えに基づき、簡単のために F 73 ∗ で考えると、
p - 1 = 72 = 2 3 · 3 2
なのでp - 1 の約数は 1 と 72 を含めて 4 × 3 = 12 個あります。従って 72 と 1 を除いた 10 個の約数 d について
a d ≠ 1
であれば、a の位数は 72 しかありえず、a は F 73 ∗ の生成元です。しかし実は、これでは「計算のやりすぎ」になります。この場合、
a 24 ≠ 1
a 36 ≠ 1
の2つだけが成り立てば、a の位数は 72 になります。なぜかというと、一般に次の命題が成立するからです。
e が d の約数だとすると、ある数 k があって d = k ⁢ e と表せます。このとき、
a e = 1 であるなら
a d = a k ⁢ e = a e k = 1
です。このことの対偶をとると
a d ≠ 1 であるなら
a e ≠ 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 )のどちらかの(あるいは両方の)約数になります。従って、
a 24 ≠ 1
a 36 ≠ 1
が示せれば、72 を除く 72 のすべての約数 d について、
a d ≠ 1
となり、d は a の位数ではありません。この結果、a の位数は 72 しかあり得ず、a は F 73 ∗ の生成元であることになります。以上の考察を一般化すると、次の命題が成立します。
p - 1 の約数で、p - 1 以外の任意の約数を d とし、
d =
q 1 β 1 ⁢
q 2 β 2 ⁢ …
q r β r
と表します。ここでβ i は、
0 ≤ β i ≤ α i
1 ≤ i ≤ r
です。そうすると、d は p - 1 以外のp - 1 の約数なので、
d の素因数分解の中には、β k < α k となる k 1 ≤ k ≤ r が少なくとも1つある
ことになります。なぜなら、もしそのようなk がなければ d = p - 1 だからです。そのような k について、命題 14.2 で定義した、
m k = p - 1 q k
に着目すると、d は m k の約数になります。なぜなら、d と m k の「素因数ごとの冪乗数」を比較してみると、
β i ≤ α i 1 ≤ i ≤ r , i ≠ k
β k ≤ α k - 1 (仮定により β k < α k だから)
であり、d のすべての素因数の冪乗数は m k の素因数の冪乗数以下です。つまり m k は d で割り切れ、d は m k の約数ということになります。
一方、命題 14.2 の仮定により、
g m k ≠ 1
なのでm k は g の位数ではありません。従って、m k の約数である d も 14.1 により g の位数とはなりません。
d は p - 1 以外の任意のp - 1 の約数でした。ということは、p - 1 以外の p - 1 の約数は g の位数ではない。つまり消去法で、g の位数は p - 1 であり、g は F p ∗ の生成元であることが証明されました。
F p ∗ の元 g をとったとき、それが生成元かどうかは 14.2 によって確かめることができます。しかしここで問題は、実用的なディフィー・ヘルマンの鍵共有では p が巨大な素数であり、p - 1 の素因数分解が実質的に不可能なことです。巨大数の素因数分解が困難なことは、まさにRSA暗号(No.310-311「高校数学で理解するRSA暗号の数理」)が成立する根拠でした。
そこで実際に生成元を求めるためには、p を "作為的に" 決める必要があります。まず前提となるのは、ある数 p が素数であるかどうかの判定法は種々あって(ミラー = ラビン素数判定法、など)、p が巨大数であっても判定可能なことです。この前提のもとに、簡単な方法の例を一つあげますと、次の関係にあるような3つの数 p 、q 、e を決めます。
p = e ⁢ q + 1
p と q は10進数で数百桁から1000桁以上の巨大素数(= 奇数)、e はたとえば100 以下の(もっと絞れば 10 以下の)偶数です。具体的には、まず q をランダムに選んで素数判定をし、素数であれば 次に e を選んで p が素数かどうかを判定するというプロセスになります。
こうするとp - 1 の素因数分解は簡単にできるので、F p ∗ の任意の元 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 = 2 ⁢ q + 1 の形の素数で、10進では617桁です( [...] はガウス記号で ... を超えない最大の整数)。
diffie-hellman-group14-sha1(2048bit)
p =2 2048 - 2 1984 - 1 + 2 64 ⁢ 2 1918 ⁢ π + 124476
= 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と略記される)。ただ、公開鍵暗号の優秀性は、「解読の困難性」と「暗号化・複号化計算の容易性」という二律背反の要求をいかに両立させるかにあります。その意味で、ディフィー・ヘルマン以降、各種の公開鍵暗号が開発されてきました。離散対数問題を使った暗号で言うと、よく使われるのは "楕円暗号(楕円曲線暗号)" です。これは「楕円曲線上の有理点がつくる "加法群" での離散対数問題」を利用した暗号です。しかし基本的な考え方はディフィー・ヘルマンの鍵共有と同じです。その意味で、公開鍵暗号の発端となった発明の意義は、今も続いているのでした。
まとめ
以上の 「ディフィー・ヘルマンの鍵共有」をまとめると、次のようになるでしょう。
No.310-311 のRSA暗号と同じく、この最後の点がこの記事の目的なのでした。
しかし公開鍵暗号そのもののアイデアを最初に提示したのは、スタンフォード大学の研究者だったディフィー(米)とヘルマン(米)で、1976年のことでした。2人も 2015年にチューリング賞を受賞しています。この「鍵を公開する」という、画期的というか逆転の発想である公開鍵暗号の登場以降、暗号の研究は一変してしまいました。そして RSA暗号のみならず各種の公開鍵暗号が開発され、現代のインターネットの基盤になっています。たとえばインターネットのWebサーバへのアクセス(閲覧やフォーム入力など)で使われる SSL/TSL という暗号化通信(https:// のサイトで使われる)は、まさに公開鍵方式を使っています。
今回はその公開鍵暗号を "発明した" ディフィーとヘルマンに敬意を表して、彼らが発表した内容と、その数学的背景を書いてみたいと思います。タイトルは「公開鍵暗号の数理」としましたが、あくまで公開鍵暗号の原点となったアイデアの解説です。
![]() |
ACM(Association of Computing Machinary)のサイトには、歴代のチューリング賞の受賞者の紹介ページがある。2015年の受賞者はディフィーとヘルマンで、受賞理由として「公開鍵暗号の発明」と書かれている。 |
ディフィーとヘルマンが提出したアイデアは「公開鍵を使って秘密鍵を安全に共有する」ものでした。これは「ディフィー・ヘルマンの鍵共有」と呼ばれていて、現在でも使われています。そこでまず「秘密鍵の共有」の意義を振り返ってみたいと思います。
秘密鍵の共有
古今東西、様々な暗号化方式が開発・使用されてきましたが「秘密鍵の共有による暗号」(=共通鍵暗号)が基本です。その中でも「一回限りの乱数表」は安全(=解読されない)と証明されている暗号です。この場合、乱数表が秘密鍵に相当します。
英大文字・小文字、数字、英文に使われる特殊文字を、 の数字でコード化するとします。いま、 文字以下の平文をコード化して暗号文にしたいとき、「一回限りの乱数表」として必要なのは、 の値をとる乱数が 個並んだ表です。さらに、
: | |
: | |
: |
とするとき、「乱数 の値に依存して、 を に1対1に変換する関数 」を決めておきます。そうすると、
の変換で暗号文 が得られます。この関数 は の コード変換テーブルでもいいし、 のような四則演算でもよい。とにかく が違えば別の1対1変換になる関数が条件で、そうすれば逆変換で複号化が可能です。この関数を秘密にする必要はなく、オープンにしてもかまいません。この暗号が安全な理由は、
秘密鍵(=乱数表)の長さが平文と同じ | |
秘密鍵は1回限り(=使い終わったら捨てる) |
の2点によります。もちろん乱数が "真の乱数" であることも重要です。しかし、上の2点を守るためには秘密鍵(乱数表)の長さが膨大になります。使い終わった乱数表のページを破って捨てなければならないからです。そこで実用的には、暗号文のやりとりを始める前に秘密鍵を共有しておき、暗号化はその「秘密鍵にもとづいた何らかの暗号化方式」で行うことになります。こうすると平文の長さが秘密鍵より長くなるので、絶対に安全とは言えなくなります。そこで、解読しにくい(=強度の高い)暗号化方式の必要性があり、これをめぐって様々な方式が作られてきました。
しかし問題は、最初の「秘密鍵の共有」をどうやってやるかです。結局、秘密鍵を印刷し、アタッシュケースに入れて相手に持参するというような、スパイ映画にでも出てきそうな方法しか本質的には無いわけです。どういうやり方をとるにせよ「秘密鍵の共有」には多大なコストがかかる。
No.310-311「高校数学で理解するRSA暗号の数理」で書いた公開鍵暗号の価値はそういうところにあります。つまり、RSA暗号における暗号化・複号化は巨大な数の "冪剰余" を求める計算になり、これはこれで計算機負荷が高い。そこで、まずRSA暗号を使って秘密鍵を生成・共有しておき、以降はその秘密鍵を使う高速な(= 計算機負荷の低い)暗号化・複号化方式で通信をするやり方が多くとられます。もちろんその秘密鍵は通信が一段落したら捨てて、次の通信では新たな秘密鍵を生成して共有するわけです。これは他の公開鍵暗号でも同じです。
その、"公開鍵を使って秘密鍵を共有する" ことを最初に提唱したのが「ディフィー・ヘルマンの鍵共有」でした。そしてこれが、そもそもの「公開鍵の発明」になりました。この鍵共有は、
盗聴されている通信路を使って情報をやりとりすることで、秘密鍵の共有を安全に実現する
ためのアルゴリズムです。どうしてそんなことができるのかが、以降です。
9. ディフィー・ヘルマンの鍵共有
ディフィー・ヘルマンの鍵共有は次のように進みます。まず「公開鍵センター」が "皆が使う公開鍵"として、
は巨大な素数 | |
は小さな整数 |
のペアを公開しておきます。次に、 さんと さんが秘密鍵を共有したい場合、
は、 である乱数 a を発生させ、g a mod p を A の公開鍵として(盗聴されている通信路を介して) B に送付
します。乱数
します。もちろん
とします。この作り方から
ちなみに、以上のプロセスに出てくる g a mod p などの "冪剰余" の計算ですが、たとえ a や p が巨大数であっても効率的に計算できることを、No.311「高校数学で理解するRSA暗号の数理(2)」の「累乗の剰余を求めるアルゴリズム」で書きました。
以上の仕組みにおいて通信路が盗聴されたとしても安全なのは、
以降でその「生成元」とは何か、盗聴者が公開鍵から
の知識を前提とします。
10. 有限体(
一般に加減乗除が定義された集合を "体(Field)" と言います。有理数、実数、複素数は "体" です。さらに No.310「高校数学で理解するRSA暗号の数理(1)」の終わりの方に書いたように、
除算は逆数(=逆元)を乗算する演算で行います。
2.3b | 逆数の存在:法が素数 |
を満たす逆数 |
No.310 でやったように、
となります。以上のことから、
ここで
の3つの条件を満たす、"演算が定義された集合" です。以降の記述は、すべて乗法群
11. 位数(order)
が成り立ちます。つまり、すべての元は
となって、
となり、フェルマの小定理が示す
位数の定義 |
"冪乗に関する元の振る舞いの違い" を表すために、
11.1 | 位数の定義 |
となる最小の |
フェルマの小定理により
です。位数になりうる数は、最小
11.2 | 位数がとりうる値 |
|
なぜなら、元
このことは直感的理解が可能ですが、次の命題はステップを踏んだ証明が必要です。
位数が |
11.3 | |
|
これは、
以降、これを、
と表記し、この
11.3a | |
|
となったとします。両辺を
となりますが、
11.3b | |
|
これは
11.3c | |
|
一般に、有限体
とし、方程式
と表現できます。なぜなら
の因数分解が成り立つからです。帰納法の仮定により方程式
でした。このような元は
11.3d | |
|
位数
これはもちろん、
11.3e | |
|
と書き表せます。ここで、
となり、
11.3f | |
|
次に
と表すことができます。そうすると、
となります。
となり、定義により
11.3g | |
|
11.3e と 11.3f により、
以上の 11.3d と 11.3g、つまり、
11.3d
11.3g
の2つから、
11.3
が証明できました。
ここまでの考察を次のようにまとめることができます。
ここで 位数
11.4 | |||||
|
そこで次に、
オイラー関数の総和定理 |
11.5 | オイラー関数の総和 |
が成り立つ。 |
この "総和定理" は、特に
です。これは最大公約数の定義そのものであり、そういう風に決めたのが最大公約数でした。2番目に、
と言えます。この2つを前提に、まず
となります。いま、各グループに含まれる整数の個数を
です。
次に、
となります。同様にして、残りのグループについては、
となります。
が証明できました。これを総和の記号で書くと、
です。
以上の説明では
とします。このとき
になります。そもそも、そのような元
ということになります。
になります。ここで
と定義すると、
となりますが、上に書いたように、この
ここで上式の両辺の
です。一方、右辺の総和は、
です。以上の左辺と右辺の総和が等しいことにより、11.5 の
が証明できました。
位数 |
11.5 の "オイラー関数の総和定理" と 11.4 を合わせると、次の命題が証明できます。
11.6 | |
|
11.4 を振り返ってみると、
でした。しかし 11.5 のオイラー関数の総和定理で
となります。これが何を意味するかというと、
ということです。ある位数
12. 生成元と離散対数
11.6 からすぐに、次の「生成元の存在定理」が成り立ちます。これは19世紀ドイツの大数学者、ガウスが証明したものです。
12.1 | 生成元の存在 |
|
11.6 によると、
生成元は原始根(primitive root)とも言います。「11. 位数(order)」の最初に書いた例だと、
とにかく、
12.2 | 離散対数 |
となる元 で表す。 |
対数は普通、実数で定義されるものですが、
実数の対数を計算する手法はいろいろありますが(初等的にはマクローリン級数など)、離散対数を計算する効率的手法は知られていません。特に、
のペアを「皆が使う公開鍵」として公開しておきます。演算は
します。乱数
します。もちろん
とします。この作り方から
ことになります。「
離散対数を計算する効率的な手法は知られていないため、
13. 生成元を使った暗号化通信
ディフィー・ヘルマンの鍵共有の原理を暗号化通信に使うこともできます(ElGamal 暗号)。まず、
のペアを「皆が使う公開鍵」として公開しておきます。以下の演算はすべて
します。乱数
します。
します。複号化は
この暗号では暗号文を
これは「離散対数暗号」と呼ばれているものの一つの例ですが、ディフィー・ヘルマンの鍵共有と、暗号文の伝達を同時に行うものと言えます。
14. 生成元であることの証明
「ディフィー・ヘルマンの鍵共有」や「離散対数暗号」を実現するためには、巨大な素数
ので、
一般に
を示せばよいからです。従って、
なので
であれば、
の2つだけが成り立てば、
14.1 | |
|
です。このことの対偶をとると
となり、これはつまり、
ことを意味します。
が示せれば、
となり、
14.2 | |
と表す。ここで、 とおくと、もし が成り立つなら、 |
と表します。ここで
です。そうすると、
ことになります。なぜなら、もしそのような
に着目すると、
であり、
一方、命題 14.2 の仮定により、
なので
実際に生成元を求める |
そこで実際に生成元を求めるためには、
こうすると
以上は一つの例ですが、実際に実務で使う
ちなみに、現在、ディフィー・ヘルマンの鍵共有が実際に使われている例をあげておきます。インターネットを介してリモートのコンピュータ同士が安全に通信するための SSH(Secure Shell)という規格がありますが、そこで使われている公開鍵の一つ "diffie-hellman-group14-sha1"(2048ビットの素数
diffie-hellman-group14-sha1(2048bit)
p =
= 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暗号と同じく、この最後の点がこの記事の目的なのでした。
2021-06-12 12:59
nice!(0)