暗号には素数が大活躍 – わたしたちの安全は素数が守る

現在、メールや電話などの情報伝達の暗号化には素数が使われています。素数が私たちの情報を守っていると言っても過言ではありません。
では、どのように暗号に素数が使われているのでしょうか。なぜ、素数でなければならないのでしょうか。素数のどんなところが暗号に適しているのでしょうか。
そんな疑問を分かりやすく解説します。
素数が私たちの情報を守っている
人間の社会は情報の伝達技術において、ここ数百年、数十年で劇的に変化し続けています。
家にいても、外出してても、どこからでも電話やメールを使って人と連絡をとることができます。これは20年前までは考えられなかったことです。携帯電話なんてものはなかったからです。
わたしが小学生の頃(1990年代)は友達との待ち合わせはある意味賭けでした。万が一、友達が約束の時間に約束の場所へ来なくても友達がどこにいるのかを確認するすべがないのです。数十分待っても来ないときは、直接、友達の家まで探しに行くしかありません。
今は、携帯電話ですぐに解決ですよね。
これだけ、テクノロジーが発達した現代は便利ではありますが、それを逆手にとり犯罪をしようとする人たちも現れました。
例えば、メールや電話の内容を傍受(他人間の通信を盗み取ること)して、個人情報やプライバシーを侵害しようとする人たちが現れたのです。
情報漏洩問題は、最近でもよくニュースになっていますよね。
通常は、こんなことが起こりえないようにわたしたちの通信は暗号化によって守られています。
そして、暗号化には素数がもつ特殊な性質が使用されているのです。私たちのプライバシーは素数があったからこそ守ることができているといっても過言ではありません。
スポンサーリンク
暗号と暗号化とは
まず暗号と暗号化について簡単に説明します。
暗号とは、”ある特定の人にしか分からない文字や記号などの組み合わせ”のことです。そして、暗号を作ることを暗号化すると言います。
よく宝探しアドベンチャー映画などで宝のありかを示した暗号が登場しますよね。暗号の内容を理解するには、暗号を解くためのキーが必要です。
このキーを持っている人しか暗号を解読することができません。
これは、現代の通信においても同様です。通信は暗号化され電気信号として送られますが、その電気信号は受け取ろうと思えば、誰でも受信できます。
しかし、キーを持たなければ、暗号を解読できないので何の情報かは分かりません。キーは正式な受信者(送信者が送りたい人)のみが分かっています。
これによって、わたしたちは安心して情報を送ったり受け取ったりできているのです。大事なことは、
キーを持たなければ、暗号を解読できない(メールの内容が分からない)
ということです。
暗号を作るうえで大事な素数の性質
素数とは、自分と1以外の数で割り切れない数のことです。例えば、13は素数です。1と13以外では、割ることができませんからね。
そして、暗号を作る上で知っておかないといけない素数の性質が三つあります。それは、
- 二つの素数同士の掛け算でできた数の因数はその二つしかない
- 素数の掛け算は簡単に計算できるけど、分解は難しい
- 素数が現れるのに法則性がない
です。これだけでは分かりにくいと思いますので、一つずつ見ていきましょう。まったく難しくないので安心してください。
二つの素数同士の掛け算でできた数の因数はその二つしかない
まずは、一つ目の、
二つの素数同士の掛け算でできた数の因数はその二つしかない
ということですが、例えば二つの素数7と13があったとします。この二つの素数同士を掛けた数は、
$$7 \times 11 = 77$$
ですね。すると、この77という数字を分解して掛け算で表すとき、
$$77 \rightarrow 7 \times 11$$
のように、7と11しか使うことができないということです。当たり前のことですね。
しかし、これが素数でない場合はこうはならないのです。例えば、6と14の掛け算を考えてみましょう。これらは素数ではないですね。
この二つの数を掛けると、
$$6 \times 14 = 84$$
となります。84を二つの数の掛け算で表そうと思ったら、
\begin{align}
84 & \rightarrow 2 \times 42 \\
84 & \rightarrow 4 \times 21 \\
84 & \rightarrow 6 \times 14 \\
84 & \rightarrow 7 \times 12
\end{align}
というふうに複数の表現方法がありますよね。後に説明しますが、これだと暗号として利用するには都合が悪いんです。だから”素数”が必要なんですね。
素数の掛け算は簡単に計算できるけど、分解は難しい
例えば、二つの素数”101″と”103″を掛けた数字を作るとします。これは簡単で、
$$101 \times 103 = 10403$$
ですね。
では逆に、”10403″という数を先に知らされて、「この数を作った二つの素数はなんですか?」と聞かれたどうでしょうか?難しいですよね。
実際に暗号に使用する数字は、これはパソコンで計算させたとしても、何年もかかるようなもっともっと桁の大きい数です。
つまり、
- 二つの素数から数字を作るのは簡単
- 作られた数字を二つの素数に分解するのは難しい
この二つが暗号化に重要な素数の性質です。
素数が現れるのに法則性がない
そして、暗号を作る上で重要なもう一つの素数の性質が、
素数が現れるのに法則性がない
ということです。
これは、数字を小さい方から確認していったとき、次に素数となる数字はやってみなきゃ分からないということです。
初めの素数は、2です。それ以降は、
3, 5, 7, 11, 13, 17, …, 5153,…
と永遠に続きますが、では”5153″の次の素数が何でしょう?
これは、実際に5153より先の数字を割れる数があるかどうか一つ一つチェックしていかないと分かりません。
「素数は100個飛ばしだから、次の素数は6479だ!」という考え方ができないのですね。これが、”素数が現れるのに法則性がない”というものです。
これも素数を暗号に使う重要な理由です。
スポンサーリンク
実際に素数はどのように暗号に使われているの?
では、いよいよ本題です。実際に素数はどのように暗号に使われているのでしょうか?
自分が情報(メール)を受け取る側となって考えていきましょう。
まず、自分がメールを受け取りたい場合は、暗号化に使う数字をバラまきます。これは、二つの素数を掛けて作られた数です。例えばその数字を、
6533708287
とします。この数字はどんな人でも知ることができます。
ただし、この数字を作っている二つの素数は自分しか知りませんし、すでに説明したように、この数からその二つの数を知ることは非常に難しいです。
「私にメールを送りたい人は、この数字を使って暗号化してください」と指示します。
すると、メールを送りたい人達はこの数字を使ってメッセージを暗号化し、自分に送ってきます。
つまり、上の数字は南京錠のようなものです。メッセージを送る人たちは鍵をかけることだけができます。
自分がメッセージを受け取ると、数字を作っている二つの素数を使って暗号を解読します。この二つの素数は”100043″と”65309″ですが、これは自分しか知りません。これが、南京錠の鍵の役割をはたしています。
なので、悪い人が自分へのメッセージを盗み見ようとしても、鍵(二つの素数)が分からないため見ることはできないのです。
元の数字”6533708287″から推測しようにも、この数から二つの素数を見つけ出すのは非常に難しいため、ほとんど不可能なのです。
これが、素数を使った暗号の仕組みです。
素数の性質はどこで使った?
”暗号を作るうえで大事な素数の性質”で説明した三つの性質、
- 二つの素数同士の掛け算でできた数の因数はその二つしかない
- 素数の掛け算は簡単に計算できるけど分解は難しい
- 素数が現れるのに法則性がない
はどのように重要だったか分かりましたか?
二つ目の、
素数の掛け算は簡単に計算できるけど分解は難しい
という性質は、分かりやすかったと思います。
南京錠を作るのは簡単だけど、それを開ける鍵を作るのは難しいということですね。”すぐに作れて、しかも性能がいい”ということです。
では、一つ目の、
二つの素数同士の掛け算でできた数の因数はその二つしかない
というのは、どうでしょう。
これは、”一つの南京錠に対して一パターンしか開くカギを作れない”ということです。
前に見たように、素数以外の数を掛けて作った数は、いくつも掛け算パターンがありましたよね。
それでは、色々な鍵で一つの南京錠を開けることができてしまい、鍵を作りやすくなってしまいます。
最後の三つ目、
素数が現れるのに法則性がない
というのはどこで使っているのでしょう?
これも鍵を作りにくくしているのです。今まで素数を見つけるのにしらみつぶしにチェックしなければならなかったもにが、もし素数が現れるのに法則性があると一気に鍵を作りやすくなってしまいます。
素数の法則性は未だに見つかっていませんが、もし法則性が見つかってしまうと、数学発展という意味ではすごい快挙ですが、暗号がすべて破られ大混乱になるでしょう。
もちろん、見つけた数学者はそんな安易に世間に公開はしないでしょうが、これまで主流だった暗号化の方法が見直されることになるでしょう。
スポンサーリンク
まとめ
- 暗号化には素数が持つ独特の性質が利用されている
- 暗号化に素数が利用される理由は、以下の三つである
- 二つの素数同士の掛け算でできた数の因数はその二つしかない
- 素数の掛け算は簡単に計算できるけど分解は難しい
- 素数が現れるのに法則性がない
- 受信者は暗号化するための数字(南京錠)だけを配り、解読するための数字(鍵)は自分だけが持つようにすることで安全に情報の送受信を行う
ディスカッション
コメント一覧
7×13=91ですから91は素数じゃありませんよ
ご指摘ありがとうございます。
修正いたしました。
Please display the prime number of the next cipher.
Can it be deciphered?
素数の暗号とかあまり意味ないと思う。
三角関数と同じで一度計算で求めておいた表を使えば、比較的簡単に探せる。
結局のところ素数表を整備可能な国という機関にとって暗号足りえない。
認証局は通信が始まったことを監視しているし、そこに素数表があれば電文の入手だけですべて監視可能だろう。