公開鍵暗号

質問

公開鍵暗号の鍵ペアを構成したい

二つの素数をP＝13、Q＝17としたときの鍵ペアを構成し、暗号化と複合化が正しく出来ることを示しなさい

よろしくお願いします

回答No.4

banakona

私の古いノートにあった事項なので間違っていたら御免。

公開鍵が５のときの秘密鍵は　５・Ｘ≡１（Ｍｏｄ１９２）
を解くことにより求める。
ユークリッドの互除法により
　　１９２＝３８×５＋２　・・・Ａ
　　　　５＝２×２＋１　　・・・Ｂ
Ｂより　１＝５－２×２　　・・・Ｃ
ＡをＢに代入　　１＝５－２×（１９２－３８×５）
これを整理すると　１＝５×７７－１９２×２
つまり　５×７７≡１（Ｍｏｄ１９２）
なので　秘密鍵は７７

試し１１を暗号化したら１６３になって、これを復号したら１１に戻ったから、あっているような気がする。

お礼

ユークリッドのやつを使わないで出した自分の値と
一致しました、大変助かりました

回答No.3

arrysthmia

公開鍵暗号といってもイロイロあるので、
具体的な暗号方式を指定しなければ、
「鍵ペアを構成」とダケ言っても、意味が無い。

公開鍵方式の暗号を、自分でひとつ発明しろ
って話なんだろうか？

お礼

RSAです
説明不足でした

回答No.2

proto

e*d - y*φ(n) = 1
を満たす、dが秘密鍵になりますね。
まず、
　　e = 5
　　φ(n) = φ(p*q) = φ(p)*φ(q) = (p-1)*(q-1) = 12*16 = 192
よって
　　5d - 192y = 1
を満たすdを求めればよい。
gcd(5,192)=1より、このようなdは存在する。

リクエストの通りユークリッドの互除法の逆からこの不定方程式を解くことを考える。
まずは普通に互除法を適用、
　　192 = 38*5 + 2　　―― (1)
　　5 = 2*2 + 1　　―― (2)
逆をやると、
　　1 = 5 - 2*2　　(∵(2)式より)
　　　= 5 - 2*(192-38*5)　　(∵(1)式より)
　　　= 77*5 - 2*192
よって、解の一つは(d,y)=(77,2)だからd=77と分かる。

一応、別解も、
　　5d - 192y = 1
　　5d ≡ 1 (mod 192)　　―― (*)
両辺に38を掛けて
　　190d ≡ 38 (mod 192)
　　-2d ≡ 38 (mod 192)
両辺に2を掛けて
　　-4d ≡ 76 (mod 192)
式(*)と片々足して
　　5d-4d = d ≡ 1+76 = 77 (mod 192)
よってd=77

お礼

別解までつけていただきありがとうございました

回答No.1

proto

よろしくお願いします、と言うが、本来解くのはあなたがすることで他人に解かせるものでもないだろう。
何か分からない部分があるのなら、質問してもらえれば答えることも出来ようが、よろしくお願いしますだけでは質問にもなっていない。

問題の内容は分かった。で、あなたからの質問は何？
とりあえず、少し教科書を読めば、鍵の生成くらいは簡単にできるのでは？

お礼

※任意の素数p＝13,q＝17を利用し、nを構成しました

補足

では質問します。

まず公開鍵を(n,e)を構成しました
n＝pq＝221、
任意の数k＝lcm{(p－1),(q－1)}
＝lcm(12,16)
＝48
gcd(e,k)＝1
e＝5,7,11,13,17.19,23,29,31,37,41,43,47
∴(n,e)＝(221,5)
ここまではできたのですが、秘密鍵dの求め方がわかりません。

ユークリッドの定理を読んでみてもいまいちです。
秘密鍵dの求め方をお分かりの方、教えてください。