- ベストアンサー
RSA 暗号の、最も簡単な破り方は、これですね?
RSA 暗号の、最も簡単な破り方は、これですね?: 暗号文中の自然数をNとする。 1.ルートN 未満の全ての奇数nについて、nが素数か否か、AKS素数判定法で判定する。 https://ja.wikipedia.org/wiki/AKS%E7%B4%A0%E6%95%B0%E5%88%A4%E5%AE%9A%E6%B3%95 2.nが素数ならば、Nをnで割る。
- 木村 弘一(こういち)(@koitiluv1842)
- お礼率92% (25/27)
- その他([技術者向] コンピューター)
- 回答数1
- ありがとう数1
- みんなの回答 (1)
- 専門家の回答
質問者が選んだベストアンサー
いいえ、「暗号文中の自然数をNとする」というのは話の出発点が違っています。 RSA暗号の解読が難しいのは桁数の大きな数Nの素因数分解には時間がかかる(と考えられている)からですが、そのNは暗号文中ではなくて公開鍵に含まれます。暗号文中の自然数を素因数分解してもRSA暗号は破れません。 また、アルゴリズムの簡単さで言うなら試し割り法(√Nまでの値で順番に割ってみる)のほうがはるかに簡単ですし、実用上の処理速度の観点では”まだ「一般数体篩法」で因数分解した方がよい”とWikipediaのAKS素数判定法のページに書かれています。
関連するQ&A
- 学校でRSA暗号について勉強して分からないところがありましたので質問し
学校でRSA暗号について勉強して分からないところがありましたので質問します。 暗号文の作成者をAさん、復号者をBさんとします。 Aさんは暗号文と公開鍵{e,n}を一般に公開しますよね? 暗号文を復号化するには秘密鍵が必要ですが、Bさんはeとnしか分からない(一般の人と得られる情報が同じ)のにどうやって秘密鍵を作成するのですか?nのもとになっている2つの素数がわからないことには秘密鍵が作成できないとおもうのですが… RSA暗号はnの素因数分解が計算量的に困難だから安全なんですよね?Bさんはどうやって2つの素数を特定するのでしょうか? 教えてください。
- ベストアンサー
- ネットワーク
- RSA暗号についての素朴な疑問
RSA暗号について勉強中のものですが、これまでのところ (1)送信側はは公開鍵(e,n)で平文aを b = a^e mod n で暗号文bを作成する。 (2)受信側は秘密鍵dを知っており、上記暗号文bからb^d mod n で元の平文aが求まる。 (3)暗号としてのキモは、(e,n)からでは復号できない。dを求めることも困難(nの素因数分解が困難) というのが私の理解したところです。数式等もある程度理解しました。 ただ、ここで素朴な疑問があります。dをしらなくてもbのべき乗を繰り返していけば復号できるのでは?ということです。自分が送信側で平文aを暗号化してbを作る。bから bxb→b' b'xb→b'' b''xb→b''' と計算していけば平文aにたどり着くのでは? (その結果dもわかったことになる) 平文が現れたかのチェック時間は余分にかかると思いますが、dを知っていてbのd乗を計算するのと上記のように2乗、3乗...と繰り返すのと大きな違いがあるのでしょうか? 長文ですいません。
- ベストアンサー
- ネットワーク
- RSAによる暗号化について
よくRSAでの暗号化で鍵の長さが512ビットや1024ビットなどのものがありますが、これは公開鍵eと秘密鍵dと共通鍵nのどの鍵が512ビットなのでしょうか?自分の中では512ビットの鍵であれば全て(e,d,n)は512であると思っているのですが、dを計算する時(ユークリッド互除法を用いる)、どうしてもdはeやnの鍵の長さの2倍のビット長が必要な気がします。どうしてもわかりません。鍵のビット長について教えてください。お願いします。
- ベストアンサー
- ネットワーク
- RSA暗号の統計的手法による解読
RSA暗号はべき乗と剰余で暗号化するのですから、同じNとEを使い続けてたり長文を暗号化したりすると統計的手法で解読されてしまうのではないでしょうか。
- ベストアンサー
- ネットワーク
- RSA暗号に関し、素数p.qが、それぞれ5、11であり、かつ、暗号化鍵
RSA暗号に関し、素数p.qが、それぞれ5、11であり、かつ、暗号化鍵eが23のとき、復号鍵dを求める考え方の手順を教えてください。さらにこれらを使って平文2を暗号化するにはどのようにすればいいでしょうか。
- ベストアンサー
- ネットワーク
- 公開鍵暗号 RSAについて
こんにちは、 RSAの説明には、 公開鍵(a,N) 秘密鍵(b,N) N=素数c×素数d を用意した場合、a,c,dを決定できれば、bを導いて秘密鍵を導くことができます。 とあります。N、c、dの関係はわかりますが、a,bは何でしょうか?
- ベストアンサー
- ネットワーク
お礼
誠に有難う御座います!
補足
ウィキペディアによりますと、AKS は低速すぎるそうですので、以下に集成しました高速の諸・素数判定法で以て公開鍵中の n が素数か否かを判定してから・・・、という方法に訂正いたします。 https://www.google.com/search?q=okwave+%E7%B4%A0%E6%95%B0%E3%80%80%E7%94%9F%E6%88%90%E3%80%80%E5%A4%9A%E9%A0%85%E5%BC%8F%E6%99%82%E9%96%93&hl=ja&sxsrf=APwXEdfUsrQN-iqAbr3mLMk4B0O6XqwZ7Q:1684731844698&filter=0&biw=1096&bih=486&dpr=1.25