Top / 素数って実社会でどう使われているの?
HTML convert time: 0.025 sec.

素数って実社会でどう使われているの?

Last-modified: 2015-03-26 (木) 21:44:49

素数って実社会でどう使われているの?

 一番身近なところで言えばみなさんがよくウェブページを利用する際に、パスワードを必要とするログインページの「暗号化」に使用されています。URLの先頭がhttpsで始まっていたり、ブラウザの端(iPhoneならURLの部分)に南京錠のマークがついていたらSSL暗号化通信をしているという目印となります。この技術には「RSA暗号」という暗号化アルゴリズムが採用されており、素数が使われています。
 その簡単な説明は次の通りです。例えば、みなさんは「31×79」を計算してくださいと言われたら紙や電卓ですぐに計算することができると思います。しかし、「2449」を素因数分解してくださいと言われたらどうでしょうか。すぐに「答えは31と79です。」と答えることはできないと思います。つまり、素数と素数の積を計算することは簡単だが、素数と素数からなる積を因数分解しなさいと言われた時に、時間がかかってしまうということです。
「RSA暗号」ではこの性質を利用しています(いま例に出したのは2桁の素数でしたがRSA暗号では約150桁程度の素数を利用しています)。約150桁の素数×約150桁の素数=約300桁の二つの素数からなる積。これは実はスーパーコンピュータを使っても膨大な時間(一時期、数百年と言われてましたが。。。)がかかります。なので数百年後に解読しても情報の価値として意味がないので、セキュリティ上安全だといわれています。もし、150桁の2つの素数からできる数をすぐに素因数分解できるような方法を見つけたら世界中の機密情報やあなたのパスワードが簡単に漏れることになります。

 ただ、時代が進むにつれて技術や考え方が進みますので、時間の問題かもしれません。。。


 参考までにwikipediaのRSA暗号[外部リンク]の解読の歴史を張っておきます。

引用開始---

RSA暗号解読コンテスト

RSA社は「RSA Factoring Challenge」を1991年から2007年まで実施し、最新の計算機環境でどの程度のビット数の整数が素因数分解可能かを調べた。

1991.04.01 RSA-100 (330ビット)

1992.04.14 RSA-110 (364ビット)

1993.06.09 RSA-120 (397ビット)

1994.04 RSA-129 (426ビット)

1996.04.10 RSA-130 (430ビット)

1999.02.02 RSA-140 (463ビット)

2004 RSA-150 (496ビット)

1999.08.22 RSA-155 (512ビット)

2003.04.01 RSA-160 (530ビット)

2009.12.29 RSA-170 (563ビット)

2003.12.03 RSA-576 (576ビット,10進174桁)

yet RSA-180 (596ビット)

yet RSA-190 (629ビット)

2005.11.02 RSA-640 (640ビット)

2005.05.09 RSA-200 (663ビット,10進200桁)

yet RSA-210 (696ビット,10進210桁)

yet RSA-704 (704ビット)

2009.12.12 RSA-768 (768ビット)

以下は未踏

RSA-896

RSA-1024

RSA-1536

RSA-2048

引用終了---参照日は2015年3月17日

読み方:ビットを10進数の桁に直す計算はビット数にlog2の値である0.3010をかけてください。
1024bit×0.3010=約300桁

次ページ:公開鍵の計算方法について知りたい人→どのように暗号化するか?
次ページ:暗号について基礎を知りたい人→暗号化とは?

執筆予定記事:150桁の素数なんて簡単に作れるの?