• ベストアンサー

RSA 暗号の、最も簡単な破り方は、これですね？

RSA 暗号の、最も簡単な破り方は、これですね？： 暗号文中の自然数をNとする。 １．ルートN 未満の全ての奇数ｎについて、ｎが素数か否か、ＡＫＳ素数判定法で判定する。 https://ja.wikipedia.org/wiki/AKS%E7%B4%A0%E6%95%B0%E5%88%A4%E5%AE%9A%E6%B3%95 ２．ｎが素数ならば、Ｎをｎで割る。

回答 全件
ベストアンサー
いいえ、「暗号文中の自然数をNとする」というのは話の出発点が違っていま…

質問者が選んだベストアンサー

  • ベストアンサー
  • _kappe_
  • ベストアンサー率68% (1521/2215)
回答No.1

いいえ、「暗号文中の自然数をNとする」というのは話の出発点が違っています。 RSA暗号の解読が難しいのは桁数の大きな数Nの素因数分解には時間がかかる（と考えられている）からですが、そのNは暗号文中ではなくて公開鍵に含まれます。暗号文中の自然数を素因数分解してもRSA暗号は破れません。 また、アルゴリズムの簡単さで言うなら試し割り法（√Nまでの値で順番に割ってみる）のほうがはるかに簡単ですし、実用上の処理速度の観点では”まだ「一般数体篩法」で因数分解した方がよい”とWikipediaのAKS素数判定法のページに書かれています。

koitiluv1842
質問者

お礼

誠に有難う御座います！

koitiluv1842
質問者

補足

ウィキペディアによりますと、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

全文を見る
すると、全ての回答が全文表示されます。
  1. カテゴリ
  2. [技術者向] コンピューター
  3. その他([技術者向] コンピューター)

関連するQ&A

  • 学校でRSA暗号について勉強して分からないところがありましたので質問し

    学校でRSA暗号について勉強して分からないところがありましたので質問します。 暗号文の作成者をAさん、復号者をBさんとします。 Aさんは暗号文と公開鍵｛e,n｝を一般に公開しますよね？ 暗号文を復号化するには秘密鍵が必要ですが、Bさんはeとnしか分からない（一般の人と得られる情報が同じ）のにどうやって秘密鍵を作成するのですか？nのもとになっている2つの素数がわからないことには秘密鍵が作成できないとおもうのですが… RSA暗号はnの素因数分解が計算量的に困難だから安全なんですよね？Bさんはどうやって２つの素数を特定するのでしょうか？ 教えてください。

  • RSA暗号についての素朴な疑問

    RSA暗号について勉強中のものですが、これまでのところ （１）送信側はは公開鍵(e,n)で平文aを b = a^e mod n で暗号文bを作成する。 （２）受信側は秘密鍵dを知っており、上記暗号文bからb^d mod n で元の平文aが求まる。 （３）暗号としてのキモは、(e,n)からでは復号できない。dを求めることも困難（nの素因数分解が困難） というのが私の理解したところです。数式等もある程度理解しました。 ただ、ここで素朴な疑問があります。dをしらなくてもbのべき乗を繰り返していけば復号できるのでは？ということです。自分が送信側で平文aを暗号化してbを作る。bから　bxb→b'　b'xb→b''　b''xb→b''' 　と計算していけば平文aにたどり着くのでは？　（その結果dもわかったことになる） 平文が現れたかのチェック時間は余分にかかると思いますが、dを知っていてbのd乗を計算するのと上記のように２乗、３乗...と繰り返すのと大きな違いがあるのでしょうか？ 長文ですいません。

  • RSAによる暗号化について

    よくRSAでの暗号化で鍵の長さが512ビットや1024ビットなどのものがありますが、これは公開鍵eと秘密鍵dと共通鍵nのどの鍵が512ビットなのでしょうか？自分の中では512ビットの鍵であれば全て（e,d,n）は512であると思っているのですが、dを計算する時（ユークリッド互除法を用いる）、どうしてもdはeやnの鍵の長さの2倍のビット長が必要な気がします。どうしてもわかりません。鍵のビット長について教えてください。お願いします。

  • RSA暗号解読

    1バイト毎にe=11,n=377でRSA暗号で暗号化し、その結果を4バイトでファイルに出力した。 　　　　　　　　0034　 d=23,n=377でこの暗号化された情報を複合化したいのですがどう計算していけば良いのか分かりません。 途中の計算を書いてまとめたいので解読プログラムを使うこともできません。 0x34を16進数から10進数にして23乗するところまで何とかいきました。この後の計算を教えていただけませんか?

  • RSA暗号の統計的手法による解読

    RSA暗号はべき乗と剰余で暗号化するのですから、同じＮとＥを使い続けてたり長文を暗号化したりすると統計的手法で解読されてしまうのではないでしょうか。

  • RSA暗号に関し、素数p.qが、それぞれ5、11であり、かつ、暗号化鍵

    RSA暗号に関し、素数p.qが、それぞれ5、11であり、かつ、暗号化鍵eが23のとき、復 号鍵dを求める考え方の手順を教えてください。さらにこれらを使って平文2を暗号化するにはどのようにすればいいでしょうか。

  • RSA(公開鍵)

    a=2, b=3として以下の方法(RSA)で公開鍵、秘密鍵を作成し、平文４を暗号化したいのですが、暗号化しても４のままになってしまいます。これって暗号化されているのでしょうか？どなたかわかる方がいましたらよろしくお願いします。 １－二つの素数を決める。これをa,bとする。 ２－a*b=c (cを合成数） ３－d=(a-1)(b-1)という自然数dを求める ４－f*e/dで余りが１となるようなfを求める。(秘密鍵) 暗号文 =M(平文)^e / c の余り。

  • 公開鍵暗号　RSAについて

    こんにちは、 RSAの説明には、 公開鍵(a,N) 秘密鍵(b,N) N＝素数ｃ×素数ｄ を用意した場合、a,c,dを決定できれば、ｂを導いて秘密鍵を導くことができます。 とあります。N、ｃ、ｄの関係はわかりますが、a,bは何でしょうか？

  • RSA暗号の解き方

    素数 P=5 Q=11 であり、N=55となります。公開鍵e=3と定義します。一般解d=27となります。 さらに、自然数m=20となります。 (1)自然数mを公開鍵（e,N)を使って暗号Yを求めてください。 (2)さらに、秘密鍵（d,N）を使って暗号Yを復号化し、mと一致することを確認してください。

  • ＲＳＡ

    ＲＳＡでプログラムするときに、例えば、「ＡＢＣ」という平分は「010203」となりますよね？そのあと、暗号化する前に２進数にもどすのでしょうか？この場合、「０１０２０３」は「000100100011」となるのか、「10011111011011(ｎは10203以上の時)」となるのか教えてください。

印刷不良　縦線が入る
このQ&Aのポイント
  • 印刷すると縦線が入るのでドラムユニットを交換しましたが改善されません
  • 印刷すると縦線が入ってしまうトラブルに対して、ドラムユニットの交換を試みましたが改善されませんでした。
  • ブラザー製の印刷機を使用している際に、印刷すると縦線が入る問題が発生しました。ドラムユニットの交換を試したものの、問題は解消されませんでした。
回答を見る

注目のQ&A

カテゴリ

専門家に質問してみよう

職業から探して質問する

あなたにピッタリな商品が見つかる！ OKWAVEセレクト

質問する