おはようございます。
(実は、夜中にこの記事を書いているのですが、なんとなく今回は「おはよう」で初めてみました(笑))
ここまでの解説で、次の前提・重要事項が成り立てば、「鍵の配送問題」が発生しない理想の暗号「公開鍵暗号」ができることを見てきました。
前提：ある方法で、メッセージ\(M\)と、公開鍵(\(p\))と、秘密鍵(\(s\))と、謎の数字(\(n\))を作成する。
重要事項その1：「メッセージ(\(M\))を\(p\)乗して\(n\)で割った余り」を暗号とする。(例え\(p\)や\(n\)を知っていたとしても、暗号から元の(\(M\))を推測することはできない)
重要事項その2：暗号を\(s\)乗して\(n\)で割った余りは、元のメッセージ\(M\)に等しくなる
今回は、これらの前提・重要事項を成立させるための重要な理論を解説します。
ここでは、まず、「オイラーの定理」について説明してみましょう。
スイス人のオイラーさんが発見した事実は次のようなことです。
\(n\)が自然数で、\(M\)と\(n\)が互いに共通の約数をもたないとき、次の式が成り立つ。
$$ M^{\phi(n)}=1 \pmod n $$
成り立つっていわれても・・・。意味がわかんなーい。
ですよね。ひとつずつ、解説します。
まずは、これらの単語の解説からしていきます。
まず、「オイラーの定理」に出てくる「約数」について知りましょう。
「約数」は、その数字以下の「正の整数」で、その数字を割り切ることができる数字です。
例えば、「6」という数字を考えると、「6」以下の「正の整数」は「1,2,3,4,5,6」がありますが、その中でも「6」を割り切ることができるのは「1,2,3,6」になるので、「6」の約数は「1」と「2」と「3」と「6」です。
「15」という数字を考えると、「15」以下の正の整数は「1,2,3,4,5,6,7,8,9,10,11,12,13,14,15」がありますが、その中でも「15」を割り切ることができるのは「1,3,5,15」になるので、「15」の約数は「1」と「3」と「5」と「15」です。
次に、「共通の約数を持たない」というのは、2つの数字があったとき、それぞれの数字の「約数」を比較すると、1以外に、同じ約数をもたないということです。
例えば、「12」と「8」は共通の約数を持つでしょうか？
「12」の約数は「12,6,4,3,2,1」ですね。そして、「8」の約数は「8,4,2,1」です。
「12」と「8」は、1以外に共通の約数があります（「4」と「2」ですね）。
次に、「15」と「14」は共通の約数を持つでしょうか？
「15」の約数は「15,5,3,1」ですね。そして、「14」の約数は「14,7,2,1」です。
「15」と「14」には1以外の共通の約数がないですね。こういう1以外の共通の約数を持たない数字を「互いに素」とも呼びます。
「15」と「14」は「互いに素」という使い方をしますよ。
そして、「素数」の説明です。
「素数」というのは、「約数」がない整数のことを言います。
但し、どんな数字でも、その数字自体と「1」は約数になるので、その数字自体と「1」以外の約数がない数字を「素数」といいます。
例えば、「15」の約数は「15,5,3,1」なので、その数字自体(15)と「1」以外にも「5,3」を約数に持つので「素数」ではありません。
でも、「17」の約数は「17,1」だけです。その数字自体と「1」以外の約数を持ちませんね。なので、「17」は素数です。
この「素数」は、2,3,5,7,11,13,17,19,23・・・と無限にあることが知られています。
最後に、「\(\phi(n)\)」の説明をしましょう。
この不可思議な記号は「トーシェント関数」と呼ばれるもので、「\(\phi(n)\)」は「ファイ エヌ」と読みます。
見た目は強そうですが、実は大して難しくない関数です。
この\(\phi(n)\)は、\(1\)から\(n\)までの数で\(n\)と互いに素となる数字の「個数」を指します。
具体例を見れば、わかりやすいですね。
例えば、\(\phi(10)\)というのは、\(1\)から\(10\)までの数で\(10\)と互いに素となる数字の「個数」を指します。
\(1\)から\(10\)までの数は「1,2,3,4,5,6,7,8,9,10」があります。
この中で、10と互いに素（1を除いて、10の約数と同じ約数を持たない）な数字は、「1,3,7,9」です。
なので、互いに素となる数字の「個数」は4になります。
よって、「\(\phi(10)=4\)」となります。
他の例を挙げると、\(\phi(13)\)というのは、\(1\)から\(13\)までの数で\(13\)と互いに素となる数字の「個数」を指します。
\(1\)から\(13\)までの数は「1,2,3,4,5,6,7,8,9,10,11,12,13」があります。
この中で、13と互いに素（1を除いて、13の約数と同じ約数を持たない）な数字は、「1,2,3,4,5,6,7,8,9,10,11,12」です。(13の約数に13も含まれますので、13はダメです)
なので、互いに素となる数字の「個数」は12になります。
よって、「\(\phi(13)=12\)」となります。
13の例でわかるように、素数(\(p\)とします)は約数を\(1\)と\(p\)しか持たないので、\(1\)～\((p-1)\)までの数字全てが\(p\)と「互いに素」になります。
なので「\(\phi(p)=p-1\)」になるのです。
\(n\)が自然数で、\(M\)と\(n\)が互いに共通の約数をもたないとき、次の式が成り立つ。
$$ M^{\phi(n)}=1 \pmod n $$ 今度は、ちょっと意味が分かりますよね。
「\(M\)と\(n\)が互いに共通の約数をもたない」というのは、\(M\)の約数と\(n\)の約数に同じものが一つもないときということを言っていますね。
例えば、「\(n=14\)」で、「\(M=20\)」だとダメです。
だって、「\(n\)の約数は、1,2,7」で、「\(M\)の約数は、1,2,4,5,10,20」なので、\(n\)と\(M\)は共通の約数「2」をもってしまいます。
例えば、「\(n=21\)」で、「\(M=16\)」なら大丈夫です。
共通の約数を持たないからですね。
そして、このことが事実だったとしたら、それが「公開鍵暗号」とどういう関係があるのでしょうか？
次回以降は、これらのことを明らかにしていきます！どんどん、核心に迫っていくので、期待してください。
(実は、夜中にこの記事を書いているのですが、なんとなく今回は「おはよう」で初めてみました(笑))
ここまでの解説で、次の前提・重要事項が成り立てば、「鍵の配送問題」が発生しない理想の暗号「公開鍵暗号」ができることを見てきました。
前提：ある方法で、メッセージ\(M\)と、公開鍵(\(p\))と、秘密鍵(\(s\))と、謎の数字(\(n\))を作成する。
重要事項その1：「メッセージ(\(M\))を\(p\)乗して\(n\)で割った余り」を暗号とする。(例え\(p\)や\(n\)を知っていたとしても、暗号から元の(\(M\))を推測することはできない)
重要事項その2：暗号を\(s\)乗して\(n\)で割った余りは、元のメッセージ\(M\)に等しくなる
今回は、これらの前提・重要事項を成立させるための重要な理論を解説します。
「オイラーの定理」を知ろう！
以前の解説で、「共通鍵暗号」には「オイラーの定理」が使われているという説明をしました。ここでは、まず、「オイラーの定理」について説明してみましょう。
スイス人のオイラーさんが発見した事実は次のようなことです。
\(n\)が自然数で、\(M\)と\(n\)が互いに共通の約数をもたないとき、次の式が成り立つ。
$$ M^{\phi(n)}=1 \pmod n $$
成り立つっていわれても・・・。意味がわかんなーい。
ですよね。ひとつずつ、解説します。
「オイラーの定理」に出てくる用語を知ろう
「オイラーの定理」には日常会話で絶対に使わないであろう、「約数」「共通の約数を持たない」「素数」「\(\phi(n)\)」という宇宙語がでてきます。まずは、これらの単語の解説からしていきます。
まず、「オイラーの定理」に出てくる「約数」について知りましょう。
「約数」は、その数字以下の「正の整数」で、その数字を割り切ることができる数字です。
例えば、「6」という数字を考えると、「6」以下の「正の整数」は「1,2,3,4,5,6」がありますが、その中でも「6」を割り切ることができるのは「1,2,3,6」になるので、「6」の約数は「1」と「2」と「3」と「6」です。
「15」という数字を考えると、「15」以下の正の整数は「1,2,3,4,5,6,7,8,9,10,11,12,13,14,15」がありますが、その中でも「15」を割り切ることができるのは「1,3,5,15」になるので、「15」の約数は「1」と「3」と「5」と「15」です。
次に、「共通の約数を持たない」というのは、2つの数字があったとき、それぞれの数字の「約数」を比較すると、1以外に、同じ約数をもたないということです。
例えば、「12」と「8」は共通の約数を持つでしょうか？
「12」の約数は「12,6,4,3,2,1」ですね。そして、「8」の約数は「8,4,2,1」です。
「12」と「8」は、1以外に共通の約数があります（「4」と「2」ですね）。
次に、「15」と「14」は共通の約数を持つでしょうか？
「15」の約数は「15,5,3,1」ですね。そして、「14」の約数は「14,7,2,1」です。
「15」と「14」には1以外の共通の約数がないですね。こういう1以外の共通の約数を持たない数字を「互いに素」とも呼びます。
「15」と「14」は「互いに素」という使い方をしますよ。
そして、「素数」の説明です。
「素数」というのは、「約数」がない整数のことを言います。
但し、どんな数字でも、その数字自体と「1」は約数になるので、その数字自体と「1」以外の約数がない数字を「素数」といいます。
例えば、「15」の約数は「15,5,3,1」なので、その数字自体(15)と「1」以外にも「5,3」を約数に持つので「素数」ではありません。
でも、「17」の約数は「17,1」だけです。その数字自体と「1」以外の約数を持ちませんね。なので、「17」は素数です。
この「素数」は、2,3,5,7,11,13,17,19,23・・・と無限にあることが知られています。
最後に、「\(\phi(n)\)」の説明をしましょう。
この不可思議な記号は「トーシェント関数」と呼ばれるもので、「\(\phi(n)\)」は「ファイ エヌ」と読みます。
見た目は強そうですが、実は大して難しくない関数です。
この\(\phi(n)\)は、\(1\)から\(n\)までの数で\(n\)と互いに素となる数字の「個数」を指します。
具体例を見れば、わかりやすいですね。
例えば、\(\phi(10)\)というのは、\(1\)から\(10\)までの数で\(10\)と互いに素となる数字の「個数」を指します。
\(1\)から\(10\)までの数は「1,2,3,4,5,6,7,8,9,10」があります。
この中で、10と互いに素（1を除いて、10の約数と同じ約数を持たない）な数字は、「1,3,7,9」です。
なので、互いに素となる数字の「個数」は4になります。
よって、「\(\phi(10)=4\)」となります。
他の例を挙げると、\(\phi(13)\)というのは、\(1\)から\(13\)までの数で\(13\)と互いに素となる数字の「個数」を指します。
\(1\)から\(13\)までの数は「1,2,3,4,5,6,7,8,9,10,11,12,13」があります。
この中で、13と互いに素（1を除いて、13の約数と同じ約数を持たない）な数字は、「1,2,3,4,5,6,7,8,9,10,11,12」です。(13の約数に13も含まれますので、13はダメです)
なので、互いに素となる数字の「個数」は12になります。
よって、「\(\phi(13)=12\)」となります。
13の例でわかるように、素数(\(p\)とします)は約数を\(1\)と\(p\)しか持たないので、\(1\)～\((p-1)\)までの数字全てが\(p\)と「互いに素」になります。
なので「\(\phi(p)=p-1\)」になるのです。
もう一度、「オイラーの定理」に戻ろう
さぁ、「約数」「共通の約数を持たない」「素数」「\(\phi(n)\)」についてわかったところで、もう一度「オイラーの定理」を見てみましょう。\(n\)が自然数で、\(M\)と\(n\)が互いに共通の約数をもたないとき、次の式が成り立つ。
$$ M^{\phi(n)}=1 \pmod n $$ 今度は、ちょっと意味が分かりますよね。
「\(M\)と\(n\)が互いに共通の約数をもたない」というのは、\(M\)の約数と\(n\)の約数に同じものが一つもないときということを言っていますね。
例えば、「\(n=14\)」で、「\(M=20\)」だとダメです。
だって、「\(n\)の約数は、1,2,7」で、「\(M\)の約数は、1,2,4,5,10,20」なので、\(n\)と\(M\)は共通の約数「2」をもってしまいます。
例えば、「\(n=21\)」で、「\(M=16\)」なら大丈夫です。
共通の約数を持たないからですね。
次回のお知らせ
オイラーさんを疑うわけではないのですが、なんで、\(M^{\phi(n)}=1 \pmod n\)が成り立つのでしょうか？そして、このことが事実だったとしたら、それが「公開鍵暗号」とどういう関係があるのでしょうか？
次回以降は、これらのことを明らかにしていきます！どんどん、核心に迫っていくので、期待してください。