NSAによる電文の解読？

Question

NSAがアシュロン（阿修羅の兄弟か？）とかいうシステムで世界中の市民の通信を傍受しているようです。
しかし、RSA方式の公開鍵暗号で暗号化してある私の電文はさすがのNSAも解読でいきないですよね？

RSAで暗号化した私の電文を解読するには、桁数の大きな素数を発見する必要があって、そのためには最高速のスーパーコンピューターを使っても何年もの計算時間が必要なんですよね？

上記の理解が正しいかどうか教えてください。

なぜ、NSAの傍受で通信のコンテクストがバレルと騒いでいるのか理解できません。

FEX2053 · Accepted Answer

>毎日のように私の女房に「アメリカ政府を爆破せよ」と伝えても、
>なにも引っかからず、イスラム原理主義者と今日の天気について
>チャットしていればNSAからにらまれてしまうということですか

はい、そのとおりです。

暗号は何もRSA暗号のようなものだけでなく、真珠湾攻撃の
「ニイタカヤマノボレ」のような、すでにお互いに「このメッセージは
こういう意味がある」と事前に取り決めるようなものもあります。
そういう暗号は、はたから見ていると「暗号だ」とは気づかないん
ですね。

「ニューヨークは雨のようです」（ニューヨークは警戒が厳しい）
「だとするとワシントンの方が天気がいいですかね？」（ワシントンは
警戒が緩い）
「そうですね。週末はワシントンで会いましょうか」（テロはワシントン
ですることにします）

みたいな「暗号に全く見えない暗号」ってのもあるんです。

ですので、重要なことは「誰と誰が親密で、いつ通信を交わしたか」
なんですよ。別のルートで「こいつはテロリスト」と「アタリ」がついた
場合、その交友関係をすべて洗い出し、いつ通信が増えたかで、
テロ実行の警戒を深める・・・というやり方とかに使うんですね。

何度も言いますが、「内容は重要じゃない」んですよ。

alice_44 · Answer

RSA が素因数分解にちゃんと依存していることの検証については、
証明はされていないが、多くの人が信じている…ということなんでしょう。
のどかな話ですね。

stomachman · Answer

NPC(Non-deterministic Polynimial Complete)であるナップザック問題を使った暗号は解けちゃった。ラップトップPCで解く所を学会で実演デモされたんです。この暗号は実は本当の意味でのナップザック問題を使っておらず、暗号化アルゴリズムの都合に合わせて改変したナップザック問題を使ったためにNPCではなくなってしまった、というのが解読された原因でした。当然、その直後から「同じNPCであるRSAはまさかそういうマヌケなことやってないよな」という確認はあちこちでなされている。
　なので、もしRSAが解けたとすると、それはNP=Pが証明されたということに違いない。NP=Pってのは喩えれば「初めて入る迷路でも、目隠ししたまま一度も迷わずに必ず最短距離で抜けられる方法が分かった」というようなことなんです。そんなの誰も信じてないし、これまでに手がかりになりそうな定理・理論ももちろんなく、全然カスリもしていない。それが証明されたとなればとんでもない大発見。「有名な数学の難問が100年越しで決着した」とかいうようなノドカな話とは全く違って、実用上重要な非常に多くの問題が一気に解決する。ワープエンジンやタイムマシンにも匹敵するぐらいの大発明です。スパイ活動の都合ごときの理由で隠しておけるようなもんじゃないでしょう。

ちうわけで、ま、暗号が解読されているという話ではないと思います。「通信のコンテクストが…」なんてもってまわった表現は、ANo.1でご指摘の通り「ダレからダレへ、いつ、どこからどこへ、どのぐらいの分量の通信をしたか」ということを指していると思いますよ。

alice_44 · Answer

＞ RSAで暗号化した私の電文を解読するには、桁数の大きな素数を発見する必要があって

この部分は、本当なんですかね？
バックドアが無いことをちゃんと検証したという話は、聞かないが。

FEX2053 · Answer

いや、必要なデータは「誰が、いつ、どこへ、どの程度のデータを
送ったか」で、それが分かれば「誰と誰が友人で親密かどうか」
が全部わかっちゃいます。

内容も、暗号化されていれば、それは「秘密の通信だ」と白状して
いるようなもんですからね。

宛先などヘッダー部分は暗号化されてない（暗号化すると相手に
届かない）ので、別に暗号なんぞ解読する必要はないんです。

NSAによる電文の解読？

>毎日のように私の女房に「アメリカ政府を爆破せよ」と伝えても、

RSA が素因数分解にちゃんと依存していることの検証については、

NPC(Non-deterministic Polynimial Complete)であるナップザック問題を使った暗号は解けちゃった。

＞ RSAで暗号化した私の電文を解読するには、桁数の大きな素数を発見する必要があって

いや、必要なデータは「誰が、いつ、どこへ、どの程度のデータを

似たような質問が見つかりました

関連するカテゴリからQ&Aを探す

デイリーランキングこのカテゴリの人気デイリーQ&Aランキング

マンスリーランキングこのカテゴリの人気マンスリーQ&Aランキング

　NPC(Non-deterministic Polynimial Complete)であるナップザック問題を使った暗号は解けちゃった。