暗号には素数

質問

情報セキュリティ対策として、
暗号には大きな素数が使われていると聞きました。

大きな数ではダメなのでしょうか？
素数にこだわる理由を、簡単に教えていただければと思います。

図々しい質問ですが、
簡単な例や素人に教えるつもりで（可能であれば）
お願いします。

以下、引用---------
二つの素数を掛けて上の数を求めるのは、 根気さえあれば、今、あなたが机上で計算することもできるというのに、 逆に、上の数を下のニつの素数に分解するのは 1600 台のコンピュータを並列処理してやっと求められたというのですから…。

--------

暗号（復号化）という手順が分からないせいで、色々疑問があるのですが。
素数をかけあわせた数を暗号に使う？かけあわせた数は素数ではなくなると思いますが。
その数を素数に分解するのに大変だから意味があるのでしょうか？分解した２つの数を何に使うのでしょうか？
分解するのは、いつも２つの素数？

回答No.3

山田 太郎（@testman199）

No1さんの回答がシンプルで分かりやすいのではないでしょうか。

ちなみに素数以外でも計算は成り立ちますが、
素因数分解すると、元の数を絞り込みできますので
解読しやすい暗号として無意味なものになります

回答No.2

hanabutako

> 大きな数ではダメなのでしょうか？

大きいか否かが問題なのではなく、ある数学的な性質を満たすか否かが問題です。自然数の計算だけで暗号を作る場合、素数を使わないとその数学的な性質を満たせないので素数を使っていると思います。
素数を使っていない場合、同じアルゴリズムで計算しても特定のデータを暗号化したら、復号できなくなるでしょう。

逆に言えば、その数学的性質を満たせば自然数の四則演算をベースにした暗号を作る必要はありません。近年では、自然数の演算の代わりに楕円曲線上の点の移動を演算だと見立てた楕円曲線暗号というものが登場し、これは当然素数を使っていません。

なお、"大きな"素数を必要とする理由は、あなたも書いている通りです。小さかったら、簡単に調べられてしまいますので、暗号としての強度を保つことができません。

> 素数をかけあわせた数を暗号に使う？かけあわせた数は素数ではなくなると思いますが。

素数を掛けあわせた数を暗号に使うというのはRSA暗号のことを指していると思いますが、なぜそれをやるかといえば、そうやって暗号化をする仕組みになっているからです。

具体的にどうやって暗号化、復号するか興味があればこれを御覧ください。
http://ja.wikipedia.org/wiki/RSA%E6%9A%97%E5%8F%B7

単に掛け算をして割り算のあまりをとっているだけなので、計算自体は小学校3年までの算数の知識があればできます。
実際に計算して、体験できるサイトも有るようです。
http://herb.h.kobe-u.ac.jp/RSA.html

なぜその仕組みになっているかは、そうすることで数学的な性質を満たし、一意に復号できるからとしか言えないでしょうね。これ以上の突っ込んだ理解をするには整数論を勉強する必要があると思います。

> その数を素数に分解するのに大変だから意味があるのでしょうか？分解した２つの数を何に使うのでしょうか？

この暗号の強度は素数の積から素数を求めるのが難しいことに依存しています。RSA暗号の公開鍵は素数の積を含みますから、積から簡単に元の数を求められると、簡単に秘密鍵を計算されてしまいます。

pとqをそれぞれ素数とした時、pqをpとqに分解できれば、(p-1)(q-1)を簡単に得られますから、公開鍵に含まれるeの逆数dを簡単に得られ、復号の鍵が得られてしまいます。

> 分解するのは、いつも２つの素数？

分解するというのが何をしたいのかわかりませんが、RSA暗号の公開鍵は2つの素数の積とeからなりますね。
RSA暗号の仕組みがそうなっていますから、RSA暗号を使うとしたらそうなります。

回答No.1

Kon1701

暗号にはいろんな方式があります。そのひとつがRSAで、ご質問のとおり非常に大きな素数を使っています。
この暗号は、まさに”その数を素数に分解するのに大変だから意味がある”となります。素数２つからその積を求めるのは簡単ですが、積から元の素数２つを求める素因数分解が非常に時間がかかることを利用しています。
暗号化や復号のアルゴリズムですが、私には簡単に説明することは無理ですので、RSAで検索してみてください。

なお、最近は間違って使われることも多くなりましたが、本来は暗号化と復号です。復号化とは言いません。