Mae向きなブログ

Mae向きな情報発信を続けていきたいと思います。

RSA暗号系、電子署名

暗号技術に最初に興味を持ったのは、学生時代を終えようとしていた頃(20年近く前)だったと思います。当時はMew*1+PGPというソフトウェアを使いこなすだけで精一杯で、暗号の理論・仕組みについては全く理解できていませんでした。

のちに『[asin:978-4797322972:title]』を通して、暗号学者の道具箱に入っている6つの技術(対称暗号、公開鍵暗号、一方向ハッシュ関数、メッセージ認証コード、デジタル署名、擬似乱数発生器)が絶妙に関連しあって暗号技術が成り立っていること、RSAの鍵ペアの生成の過程が意外とシンプルなこと、シンプルにも関わらずインターネット上のセキュリティを保つためにはなくてはならない技術であること、それが中学1年生のときに習った素因数分解の困難さを利用していることなどを知ってとても感動したことを覚えています。

そして再びRSA暗号について学ぶ機会が巡ってきたのですが、今回、オイラー{\phi}関数が果たす役割について理解できたことによって、より鍵生成の過程について納得*2できるようになったのではと思います。

練習問題8.2

問2

ショーンは素数{p_s=38490587}および{q_s=38490587}を指数{e_s=7349}とともに使います。ショーンの公開鍵および秘密鍵を求めなさい。

問3

ブランドンは素数{p_b=2748401}および{q_b=157849763}を指数{e_b=9587}とともに使います。ブランドンの公開鍵および秘密鍵を求めなさい。

問4

ブランドンはメッセージ{1234567890}をショーンに送りたいとし、ショーンの公開鍵と秘密鍵を使います。ショーンが受信するメッセージは何なるでしょうか?

問5

問4のメッセージを、ショーンはどうやって復号するのか示しなさい。

解答

$ ruby rsa.rb
ショーンの公開鍵:(7349, 37847755706513)
ショーンの秘密鍵:(28526126032457, 37847755706513)
ブランドンの公開鍵:(9587, 433834446478963)
ブランドンの秘密鍵:(394147974342523, 433834446478963)
ショーンが受信するメッセージ(暗号化+署名):386686175803129
ショーンが受信するメッセージ(平文)        :1234567890

*1:http://www.mew.org/ja/

*2:以前は、p-1,q-1って何と思っていました。