• ベストアンサー

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

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

  • JZ302
  • お礼率92% (1106/1202)

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

  • ベストアンサー
回答No.2

済みません。 復号化の手順で記述誤りをしました。 (誤)6.受信者Bobは暗号化されたメッセージcを受け取り、次のような方法で復号化します。   e^d≡m(mod n) (正)6.受信者Bobは暗号化されたメッセージcを受け取り、次のような方法で復号化します。   c^d≡m(mod n) です。申し訳ありません。

JZ302
質問者

お礼

お礼が遅れてすみません。 丁寧に解説して下さってありがとうございました。 dが出なくて困っていましたので、とてもたすかります。 これからもよろしくお願いいたします。

その他の回答 (1)

回答No.1

こんにちは。 RSA暗号についてはいろいろな書物やサイトをご覧いただくとして。 RSA暗号は次のように暗号化し、復号します。 AliceからBobへ文書を送るとして 1.受信者Bobは素数p,qを選び、n=pqを計算します。 2.Bobは、l=(p-1)(q-1)を計算し、gcd(e,l)=1となるようなeを1つ選びます。 (ここでgcdとは最大公約数の意味) 3.Bobは、ed≡1(mod l),0<e<lを満たす整数dを計算します。 4.Bobは、eとnを公開し、dを秘密鍵とします。 5.送信者AliceはBobによって公開されたeとnを使ってメッセージmを次のように 暗号化します。   m^e≡c(mod n)  このcがmの暗号化メッセージです。これをBobに送ります。 6.受信者Bobは暗号化されたメッセージcを受け取り、次のような方法で復号化します。   e^d≡m(mod n) 以上をp=5,q=11,e=23の場合に当てはめてみると n=55 l=4×10=40 e=23 (gcd(23,40)=1) d=7 (23×7=161≡1(mod 40)) よって、e=23とn=55を公開鍵として、平文m=2を暗号化すると 2^23=8388608≡8(mod 55) となるので、c=8が暗号化されたメッセージです。 c=8を受け取った側は秘密鍵d=7を使って 8^7=2097152≡2(mod 55) のようにして平文2を得ます。

関連するQ&A

  • RSA(公開鍵)

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

  • RSA暗号の一般的な素数生成方法

    一般的なRSA暗号について質問です。 RSAでは鍵の生成に、大きな素数 p, q および (p-1)*(q-1)と互いに素となる素数eを使用します。 ただ、p, qの一般的に使用される桁数は1024bit(300桁超)であるため、素数の生成に非常に大きな時間がかかってしまいます。 e は3か65537を使用することで生成のための計算を省くことができますが… RSAで暗号鍵を生成する際に300桁もの素数を毎回計算して生成するのは時間がかかりすぎるため現実的ではないと思いますが、実際にはどのようにして300桁の素数を生成しているのでしょうか。 もしくは、計算済みの素数リストや固定の値を使用しているのでしょうか。 (後者はあり得ないとは思いますが…) 宜しくお願いします。

  • RSAの公開鍵

    RSAは二つの素数p、qから乗算された合成数Nと (p-1)(q-1)と互いに素な整数eを公開鍵とするそうですが、 同じ平分Mをeだけ変えてNは同じ値を使って2種類の暗号文を作った場合、 2つの暗号文が手に入れば鍵を知らなくても複合化されてしまうそうですが、 どうしてでしょうか。

  • RSA暗号

    どのトピックかがいまいちわからないのでこのトピックに質問を載せさせて頂きます。 いま、大学の課題でRSA暗号をパソコンで実装する という課題に取り組んでいます。 2桁以上の素数を選んで、その素数から暗号化鍵と復号化鍵を選んでアスキーコードを暗号化するという初歩的なものなので、実用性は全くありませんが… プログラムはできたのですが 暗号化鍵と復号化鍵を生成して 暗号化を行って複合化を行うと 元の平文に戻らない鍵のペアがあるらしいのです。 そういうときってあるのでしょうか?

  • RSA暗号についてです。

    RSA暗号についてです。 秘密鍵(p,q)=(7,17)の公開鍵の求め方、解答がわかりません。 よろしくおねがいします。 この質問に補足する

  • RSA暗号方式での平文の長さ

    現在、RSAを用いて公開鍵暗号の勉強を行っています。 そこで質問なのですが、どうして平文の長さは,鍵の長さよりも小さい必要があるのでしょうか?また、平文の長さが鍵の長さより大きくなった場合は、暗号化されないのでしょうか?よろしくおねがいします。

    • ベストアンサー
    • PHP
  • RSA暗号の解き方

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

  • 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のCプログラム

    何かC言語で書かれたRSAの一連の流れを示したものはありますか?Googleでプログラムを探しているのですがどうしてもみつかりません。プログラムとして、単純なものでよいです。ある平文に対して、はじめに2つの素数を見つけ(p,q)、鍵を生成し、暗号化をして、それを復号するというような一連の流れをC言語で見てみたいのでプログラムがありましたら教えてください。お願いします。

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

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