なぜインターネットの暗号は素数の掛け算を主に使うの

質問

なぜインターネットの暗号は素数の掛け算を主に使うのでしょう？

回答No.4

日吉 龍（@VDSL） · ベストアンサー

こんばんわ。

基本的には#1さんと#2さんが書かれている通りですが、詳しい説明は参考URLがわかりやすいです。要するに、巨大な素数同士を掛け合わせる計算は一瞬でも、その結果としてできたさらに巨大な数字を2つの素数に効率的に素因数分解するアルゴリズムがなく、膨大なコンピュータリソースをつぎ込んでも現実的な時間で素因数分解が完了しないからです。

ちなみに、もし効率的に巨大な数を素因数分解する方法が"発見"されたら、その瞬間に現在インターネット上で利用されている暗号の多くは破たんします。そのため、素数に頼らない暗号(楕円曲線暗号とか)の研究開発も進められていますが、現時点ではRSA暗号(巨大な素数の掛け算を利用した暗号方式の中でもっとも広く利用されている暗号方式)を置き換えるに至っていません。

ちなみに、現在夢のコンピューターと言われている量子コンピュータを利用した巨大な数の素因数分解を瞬時でできるアルゴリズムはすでに完成しています。これは"ショアのアルゴリズム"と呼ばれており、現在のコンピュータでは数千年かかる素因数分解が、遅くとも数時間で完了することが証明されています。

もっとも量子コンピュータが完成したら、原理的に盗聴が不可能な量子暗号が利用できるようになる(簡単に言うと、盗聴のために観測した瞬間にデータが壊れる)ので、そう遠くない未来に技術的には絶対に安全な通信ができるようになるでしょう。

参考URL：

http://www.maitou.gr.jp/rsa/rsa14.php

お礼

回答ありがとうございます。

ショアのアルゴリズムという理論が発見されているなら、アメリカは量子コンピューターで日夜素数を使った暗号を解読しているのでは・・・

回答No.3

notnot

ストレートに答えると、公開鍵暗号を実用的に実現するのに、他に手段が無いから。
「なぜ海外旅行に飛行機を使うのですか？」と同じレベルの質問。

公開鍵暗号とはなにかついては、検索すればいくらでも情報があるので、説明は処略します。

回答No.2

housyasei-usagi

素数は規則性がなく、ひたすら順番に素因数で割って調べるしかない。
従い時間がかかるので、解読が難しい。

見つける事が難しい素数を更に掛けるわけで、
その答えを見つけるには、さらに多大な時間が掛かる訳です。

素数は無限にある事は簡単な証明があります。
紀元前数学者のユークリッドが証明しています。
（最大公約数を求めるユークリッドの互除法なんかで有名ですよね）

とある暗号は数百桁の素数を掛け合わせて使っているようですね。
（出典：科学雑誌　ＮＥＷＴＯＮ　２０１３年４月号　
　ＮＥＷＴＯＮとは何の関係もありませんけど、多分
　バックナンバーがまだあるでしょうから・・・
　でも図書館にもまだあるかな？・・・）

これだけでも大変ですけど、これを解読するには・・・
ということだそうです。

回答No.1

山田 太郎（@testman199）

因数に大きな素数を含む数の素因数分解は
コンピュータを使っても時間がかかるから