会社の同僚の方とたまに自然科学研究会なるものを開催しております.
自然科学のあるテーマに沿って自由にプレゼンするものです.
第二回では私は「生活の中の数学」というテーマでプレゼンしました.

今回は,数学がネット社会の安全を支えていることを紹介します.

安全なネット

インターネットの登場により生活が豊かになった分,ネットの中では悪意を持った人の攻撃,情報の盗み見,情報の改ざんが問題になっています.こうしたネットの脅威から我々の情報を守るために,暗号化ということを行います.

ユーザーとお店側で,あらかじめ暗号化用の鍵を共有しておく.情報を送信する時は,この鍵で暗号化する.情報をもらった方は同じ鍵で複合（暗号を解くこと）すれば中身が読める.

こうすれば,悪意を持った第三者がインターネット上で情報を盗み見ようとしても鍵が無く中身を見られないため安心です.

しかし,この方法には一つ難点があります.

それは,

そもそも鍵をどのように共有すれば良いか

ということ.

鍵を共有する時に,その鍵そのものを盗み取られたら意味がありません…
鍵さえ共有できれば後は安全に通信できるのに…

この問題は「鍵の配送問題」と呼ばれ,暗号の有史以来ずっと研究者の頭を悩ませてきた問題だそうです.

画期的なアイデア

さて,1976年にディフィーとヘルマンは画期的なアイデアを提案しました.それは,

鍵を公開する

というもの.そして,

公開した鍵では暗号化だけはできるが,複合には別の鍵（秘密の鍵）が必要

というもの.

こうすれば,たとえ公開鍵が漏れても,情報の暗号化にしか使えず,複合をすることはできません.

ただ,次の課題として異なる鍵で開け閉めができるのでしょうか.

素因数分解の困難性を利用

ここに数学が活用されています.特に永らく役に立たないと思われていた整数論が今のインターネット社会を支えているということは大変喜ばしいものです.

どういうことかというと,素因数分解の困難性が使われているのです.

暗号化するだけは簡単：公開鍵
複合かするのは困難：秘密鍵

という関係が,次に似ています.

数を掛け算するのは簡単：掛け算
数を素因数分解するのは困難：素因数分解

具体的な動きとしては,まず送りたい情報（平文）としてP=3とします.
鍵を作るために,ある２つの素数の掛け算 7 × 13 = 91を考えます.

ここで,2つの素数7と１３は秘密とします.

7と13が与えられれば,掛けて91を作ることは簡単ですが,91を素因数分解しろと言われると一瞬分かりません.91くらいであれば暗算でも問題なくできますが,
これが巨大な素数同士の掛け算となると素因数分解できないという意味です.例えば,27383の素因数分解は,と聞かれるとすぐには分かりません.答えは139×197です.

さて,この与えられた91から,91以下で91と互いに素な数の個数を求めLとします.この計算には公式があり,素因数分解の7,13を知っていればすぐに計算できます.$$L = (7-1)(13-1) = 72$$

この91と素な数の個数Lから公開鍵と秘密鍵を作ります.

公開鍵：（91 , 5）
5はLと互いに素な数（つまり,法72の既約剰余類群の元）

秘密鍵：（91 , 29）
29は法Lで5の逆元

このように鍵を作ることで,次のように平文３の暗号化と復号化を行うことができます.

暗号化：\(C = P^5 = 3^5 = 61\mod(91) \)
復号化：\(C^{29} = 61^{29} = 3\mod(91) \)

何でこのように計算ができるかというと,剰余群を計算しているからです.

ある素数\(p,q\)に対して,\(N = pq\)とする.
このとき\(N\)以下の数で\(N\)と互いに素な数の個数はオイラー関数を用いて表すと$$L =\phi(N) = (p-1)(q-1)$$

平文\(P \in \mathbb{Z}/N\mathbb{Z}^× \)
暗号文\(C = P^u \in \mathbb{Z}/N\mathbb{Z}^× \)

このとき,
復号化\(C^v = P^{uv} = P \in \mathbb{Z}/N\mathbb{Z}^× \)

つまり,$$P^{uv} = P \in \mathbb{Z}/N\mathbb{Z}^×$$となる\(u,v\)を見つければ良いことになります.

ここで剰余類群\(\mathbb{Z}/N\mathbb{Z}^× \)の位数は\(L=\phi(N)\)より$$P^{\phi(N)}\equiv 1 \mod(N)$$が成り立ちます.

この式の両辺を適当に整数\(k\)乗して,さらに\(P\)を掛けると,$$P^{\phi(N)・k+1}\equiv P \mod(N)$$

先ほどの式と指数を比べると,$$uv = \phi(N)・k+1$$

式変形すると,$$uv – \phi(N)・k = 1$$

今,\(u\)として\(\phi(N)\)と互いに素な数をとると（これが先ほどの例の５）,次の一次不定方程式を解けばいいことになります.

$$ux+\phi(N)y=1$$

そして,これはEuclidの互除法で解くことができ,その結果,\(x\)として\(\phi(N)\)を法とした\(u\)の逆元（先ほどの例の29）が得られるわけです.

実際にはどのくらいの大きさの素数が使われているかというと,RSA-129という規格だと次のようです.これは既に素因数分解ができてしまっているようですが,いずれにしても大きな素数が使われています.

==================================

クリックで応援よろしくお願いします.

にほんブログ村