• ベストアンサー

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

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

質問者が選んだベストアンサー

  • ベストアンサー
回答No.4

こんばんわ。 基本的には#1さんと#2さんが書かれている通りですが、詳しい説明は参考URLがわかりやすいです。要するに、巨大な素数同士を掛け合わせる計算は一瞬でも、その結果としてできたさらに巨大な数字を2つの素数に効率的に素因数分解するアルゴリズムがなく、膨大なコンピュータリソースをつぎ込んでも現実的な時間で素因数分解が完了しないからです。 ちなみに、もし効率的に巨大な数を素因数分解する方法が"発見"されたら、その瞬間に現在インターネット上で利用されている暗号の多くは破たんします。そのため、素数に頼らない暗号(楕円曲線暗号とか)の研究開発も進められていますが、現時点ではRSA暗号(巨大な素数の掛け算を利用した暗号方式の中でもっとも広く利用されている暗号方式)を置き換えるに至っていません。 ちなみに、現在夢のコンピューターと言われている量子コンピュータを利用した巨大な数の素因数分解を瞬時でできるアルゴリズムはすでに完成しています。これは"ショアのアルゴリズム"と呼ばれており、現在のコンピュータでは数千年かかる素因数分解が、遅くとも数時間で完了することが証明されています。 もっとも量子コンピュータが完成したら、原理的に盗聴が不可能な量子暗号が利用できるようになる(簡単に言うと、盗聴のために観測した瞬間にデータが壊れる)ので、そう遠くない未来に技術的には絶対に安全な通信ができるようになるでしょう。

参考URL:
http://www.maitou.gr.jp/rsa/rsa14.php
cawbridge2013
質問者

お礼

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

その他の回答 (3)

  • notnot
  • ベストアンサー率47% (4835/10236)
回答No.3

ストレートに答えると、公開鍵暗号を実用的に実現するのに、他に手段が無いから。 「なぜ海外旅行に飛行機を使うのですか?」と同じレベルの質問。 公開鍵暗号とはなにかついては、検索すればいくらでも情報があるので、説明は処略します。

回答No.2

素数は規則性がなく、ひたすら順番に素因数で割って調べるしかない。 従い時間がかかるので、解読が難しい。 見つける事が難しい素数を更に掛けるわけで、 その答えを見つけるには、さらに多大な時間が掛かる訳です。 素数は無限にある事は簡単な証明があります。 紀元前数学者のユークリッドが証明しています。 (最大公約数を求めるユークリッドの互除法なんかで有名ですよね) とある暗号は数百桁の素数を掛け合わせて使っているようですね。 (出典:科学雑誌 NEWTON 2013年4月号   NEWTONとは何の関係もありませんけど、多分  バックナンバーがまだあるでしょうから・・・  でも図書館にもまだあるかな?・・・) これだけでも大変ですけど、これを解読するには・・・ ということだそうです。

回答No.1

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

関連するQ&A

  • 2進数の掛け算の問題がわかりません

    →1011.1 ×101.1  ̄ ̄ ̄ ̄ この2進数の掛け算の解き方が分かりません 誰か教えていただけないでしょうか?

  • 暗号には素数

    情報セキュリティ対策として、 暗号には大きな素数が使われていると聞きました。 大きな数ではダメなのでしょうか? 素数にこだわる理由を、簡単に教えていただければと思います。 図々しい質問ですが、 簡単な例や素人に教えるつもりで(可能であれば) お願いします。 以下、引用--------- 二つの素数を掛けて上の数を求めるのは、 根気さえあれば、今、あなたが机上で計算することもできるというのに、 逆に、上の数を下のニつの素数に分解するのは 1600 台のコンピュータを並列処理してやっと求められたというのですから…。 -------- 暗号(復号化)という手順が分からないせいで、色々疑問があるのですが。 素数をかけあわせた数を暗号に使う?かけあわせた数は素数ではなくなると思いますが。 その数を素数に分解するのに大変だから意味があるのでしょうか?分解した2つの数を何に使うのでしょうか? 分解するのは、いつも2つの素数?

  • 2進数の掛け算ができません

    初めまして。2進数の掛け算で困っています。よろしくお願いします。 10進数で2*(-3)=-6ですが、これを3bitの2進数で行ないたいと思います。 すると、010*101(2の補数)=01010となります。 -6は10(2の補数)となるはずですが答えが異なります。 符号拡張というものがあるということで、次はそれで行なってみます。 010*1101(符号を拡張した2の補数)=011010となります。 答えが異なります。ますますわけがわかりません。 ---------- 次に10進数で(-1)*(-1)=1ですが、これを2bitの2進数で行ないたいと思います。 すると、11(2の補数)*11(2の補数)=1001となります。 1は1となるはずですが答えが異なります。 符号拡張というものがあるということで、次はそれで行なってみます。 111(符号を拡張した2の補数)*111(符号を拡張した2の補数)=110001となります。 答えが異なります。ますますわけがわかりません。 ---------- 話は変わるのですが、 Nビット×Mビット=N×Mビットになる とのことです。これも理解できません。 どなたかご教授をお願いしますm(__)m

  • 暗号と素数の関連について

    先月辺りのニュースで50万桁目の素数が発見されたようです。その記事の最後に「これで暗号の解析が容易になる」と言うようなコメントが載っておりました。これについて言及は全くされていませんでしたので、素数と暗号との関係性が全くつかめません。どなたかなぜ素数が発券されると暗号解読に役に立つのか、お分かりになる方がいらっしゃいましたら教えてください。

  • かけ算について・・

    2けたの数を かけ算する場合、 ひっさんせずに、早く 解けるやりかたってありますか?

  • 掛け算はどんな時に使うのか

    掛け算が使える時と、使えない時について教えてください。 掛け算は同じ数がいくつかある時の合計を求めるもので、ひとつのまとまり×いくつ分の式で求められるものだと解釈しているのですが、具体的にどんな時に掛け算が使えて、どんな時に使えないのですか?(文章題などで)詳しく教えていただきたいですm(_ _)m

  • おもしろいかけ算

    6年生用の算数の教科書に「おもしろいかけ算」というのがありました。 そこには、十の位が等しく、一の位の数の和が10になる2桁同士のかけ算は簡単にしてできます。 と書いてありました。 そこにかいてあった図は、多分、十等一和だと思うのですが、この計算術は、どうして十の位と十の位をかける時、+1をするのでそしょうか。 すいません。意味が全然分からないと思うので例をだします。            53×57=3021               || (5+1)×5 と 3×7 =の答えをならべて、3021 どうして、1をたすのでしょうか。後、どうして十の位だけ1をたすのでしょうか。 早急に教えてくださいw よろしくお願いします

  • 掛け算の筆算

    掛け算の筆算で上の数からかけるか下の数からかけるかどちらの方が好きですか?また普段どちらを使いますか?

  • Excel2000掛け算をしたい

    お世話になっております。 掛け算をしたいんです。初心者でわからないのでおしえてください その関数を知りたいのです。 たとえばある数 「1」に×1024×8というようにかけたいんです。 (つまり 1×1024×8) どうすればいいでしょうか?

  • RSA暗号に関し、素数p.qが、それぞれ5、11であり、かつ、暗号化鍵

    RSA暗号に関し、素数p.qが、それぞれ5、11であり、かつ、暗号化鍵eが23のとき、復 号鍵dを求める考え方の手順を教えてください。さらにこれらを使って平文2を暗号化するにはどのようにすればいいでしょうか。