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

質問

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

回答No.5

hie_yas · ベストアンサー

> 平木教授は「このやり方で難しい暗号の解読も可能になる」と今回の研究の意義を話している。

なるほど．これって，書き方が悪くてわかりにくいですが，平木教授は，「素数の研究って意義ありますか？」という質問に対して「RSA暗号を解読する研究とも関連しているよ」とお答えになったのではないかと推測します．ところが，記者があまり理解できず，「素数の研究が進めばRSA暗号とか破れるかも」という研究の意義を「メルセンヌ素数が見つかれば暗号が破られる」と誤解したのではないでしょうか．

お礼

私の勘違いだと思い当惑しておりました。
日本語のプロではなくてはいけないはずの
新聞記者がわかったつもりになって
記事を書いてはいけませんよね。
ご指摘、ありがとうございました。

回答No.6

tatsumi01

No. 2 で「この記事は何かのの勘違いでしょう」と書いたものです。
No. 4 さんへの補足質問で「私の勘違いだと、指摘されるとは思わなかった」と書いておられますが、もちろん greet さんの勘違いとは思ってません。「ニュース記事」の間違いです。
昔のネットニュースでは「『書き込み』と書くな、『記事』と書け」と、厳しくやられたものですが、もしかして greet さんもネットニュース世代でしょうか。
なお、RAS 暗号解読の困難性については No. 4 の hie_yas さんが補足してくださったので安心しました。

お礼

「書き込み」と「記事」とで、厳しい区別が
昔にあったことは知りませんでした。
何年か前の映画ですが「ビューティフルマインド」とう映画がありました。それには天才数学者が軍の暗号を解くシーンがいくつもありましたが、暗号解読は映画の中の世界だけかと思っておりました。しかし、みなさまからのご回答により、暗号について理解が深まりました。ニュースのわからなかった点を聞いてよかったです。度重なるご回答ありがとうございました。

回答No.4

hie_yas

質問者さんの指摘の通り，大きなメルセンヌ素数が見つかると素因数分解を安全性の論拠とする暗号の解読に役立つということの関連性はないと思います．つまり，素因数分解しやすくなる，などということはないでしょう．

で，私の回答は，実はNo.3さんの回答の補足です．というか，違いますので(^^;

RSA暗号は素因数分解の困難さを論拠にする暗号の一つです(他にもRabin暗号などが素因数分解の困難さを論拠にしています)．

まず，p,qという大きな素数をランダムに選びます．それを掛け合わせて n = p×qという合成数を作ります．RSA暗号は，この合成数nを入手しても，p,qを簡単に素因数分解できないことを用いて暗号を構成しています．
つまり，p×qは簡単に計算できるけれど，逆にnからp,qは簡単に素因数分解できないという一方向性を用いているのです．
現在ではnの長さが1024ビット程度になると，まず素因数分解は不可能とされています．

素因数分解を安全性の論拠とする暗号では，この合成数nを公開し，これを使って暗号化します．できあがった暗号文は，実際にp,qを知っている人だけ(あるいはp,qを知る人だけが知り得る情報を知っている人だけ)が，復号することができるように構成します．
ので，No.3さんの素因数分解が楽というのは間違いです．また，RSA暗号ではφ(n) = (p-1)×(q-1)を確かに用いるのですが，これを素因数分解することはありません．

参考URL：

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

補足

過去最大の素数発見、パソコン７万台結び９１０万ケタ
　米国のセントラルミズーリ州立大は、同大の数学者と化学者の２人が、過去最大の素数を発見したと発表した。

　素数は、１とそれ自身の数字以外に約数がない数字。同大などによると、２人が発見した素数は９１５万２０５２ケタで、昨年２月に記録された７８１万６２３０ケタを大幅に上回った。今回の素数「３１５４……３８７１」を新聞のページ全体に印刷すると、約７２６ページ分になる。

　２人は、世界の約７万台のパソコンを結んだネットワークを駆使して膨大な計算を実施、先月中旬に最大素数の発見にこぎつけたという。

　東京大学の平木敬教授（コンピューター科学）によると、大きなケタ数の素数を求めるには、２を何乗かした数から１を引いた数の中から探していく方法が一般的。様々なテストで素数の候補を絞り込んでいき、その数が割り切れないことを多数のコンピューターで計算し確認する。

　平木教授は「このやり方で難しい暗号の解読も可能になる」と今回の研究の意義を話している。

（2006年1月6日13時56分 読売新聞）
以上引用ですが、私が理解できなかったのは平木教授の根拠です。私の勘違いだと、指摘されるとは思わなかったので、最初から載せればよかったです。

回答No.3

nadja

tatsumi01さんの回答で少し補足を。

素数同士の掛け算は実は簡単に素因数分解できてしまいます。
ためしに11かける13を行ってみてください。
それを逆に素因数分解するのは簡単ですね。

RSAの素因数の積とは、厳密に言えば、「素因数引く1した数同士をかける」ということです。そうすると大体素数じゃない同士の掛け算になりますね。

そうするとたとえば上の例で、11-1=10と13-1=12の積は120です。これを元の素因数に戻すことは、できるかって言うと、61かける3というのも出てくるはずなので、11と13を見つけることはできないし、この素数の組の組み合わせも、素数の数が大きくなればそれだけ増えてしまうので、実際問題難しい(計算量爆発というのかな)といわれています。

これが暗号の解読の難しさを保証しているという根拠のひとつになっているのです。

しかし現存のコンピュータではこの暗号解読は難しいのですが、巷ではやっている「量子コンピュータ」だとこれが簡単に解けるみたいです。「Shorの素因数分解」というので検索してみてください。いろいろと出てくると思います。

では

回答No.2

tatsumi01

その記事は何かの勘違いでしょう。
現在のＲＳＡ暗号では、二つの素数を掛けた積を暗号の鍵に使います。この積で決る二つの数を公開して、それで暗号化します。解読は、元の二つの素数を知っていれば簡単にできます。
じゃあ、誰だって暗号を解読できるではないかと思いますが、実は積が与えられても素因数分解するには天文学的な時間がかかるとされています。この仮定が崩れれば別ですが、大きい素数が見つかったからといって、素因数分解ができるわけではないので、解読が容易にはなりません。
ＲＳＡ暗号で使う素数は、１００ケタ程度の大きい数です。

回答No.1

neKo_deux

暗号の作成、解読に素因数分解を利用します。
こちらの解説なんか、参考になるハズ。(十分難しいですが…)

サルにもわかるRSA暗号:素因数分解の難しさ
http://www.maitou.gr.jp/rsa/
http://www.maitou.gr.jp/rsa/rsa13.php

お礼

理解するのは時間がかかりそうですが、少しずつでも読みすすめていきたいと思います。ありがとうございました。