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

質問

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

回答No.2

ichhabehunger · ベストアンサー

済みません。
復号化の手順で記述誤りをしました。

（誤）６．受信者Bobは暗号化されたメッセージcを受け取り、次のような方法で復号化します。
　　e^d≡m(mod n)

（正）６．受信者Bobは暗号化されたメッセージcを受け取り、次のような方法で復号化します。
　　c^d≡m(mod n)

です。申し訳ありません。

お礼

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

回答No.1

ichhabehunger

こんにちは。

RSA暗号についてはいろいろな書物やサイトをご覧いただくとして。

RSA暗号は次のように暗号化し、復号します。

AliceからBobへ文書を送るとして
１．受信者Bobは素数p,qを選び、n=pqを計算します。
２．Bobは、l=(p-1)(q-1)を計算し、gcd(e,l)=1となるようなeを１つ選びます。
（ここでgcdとは最大公約数の意味）
３．Bobは、ed≡1(mod l),0<e<lを満たす整数dを計算します。
４．Bobは、eとnを公開し、dを秘密鍵とします。
５．送信者AliceはBobによって公開されたeとnを使ってメッセージmを次のように
暗号化します。
　　m^e≡c(mod n)　　このcがmの暗号化メッセージです。これをBobに送ります。
６．受信者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を得ます。