第4章 公開暗号鍵方式(RSA方式)

 

第3章では19という共通のキーを使うことによって通信文が正しく

復号されるのをみました。

もしキーが送信側と受信側で共通でなくても正しく復号できるとしたら

いろいろ便利なことがあります。例えば送信側のキーは

「中村さんに送信するときに皆が用いる、公開されたキーである」

と考えます。そして受信側のキーは中村さんだけが知っている秘密の

キーであるとします。すると誰でもが中村さんに文を暗号化して送る

ことができますが、他の人は秘密のキーの方は知りませんので、その

文を解読することはできません。解読できるのは中村さんだけです。

これはキー(秘密の)を相手に届けなくてもいいし、また相手に教え

なくてもいいので、それだけ安全な暗号方式なのです。これを

公開暗号鍵方式(public cryptogram

key system)といいます。

前節と同様に2つの素数p、q(p≠q)に対し

E×D≡1 (mod (p−1)(q−1))

となるキーEとDを求めます。このときEを送信側のキーとして

用います(公開キー,public key)。Dは受信側のキー

といて用います(秘密キー, secret key)。

暗号化と復号化の方法はN=p×qとして、第1章、第2章で述べた

方法と同じです。すると前節と同じような理由で、元の文が復元できる

ことが証明されます。

このようなフェルマーの小定理に立脚した公開鍵方式をRSA方式

といいます。

例 p=11、q=37とする。N=407。

公開キーは7、秘密キーは103。すると

(M103≡ M (mod N)

より具体的には通信文234について

234≡234×234≡155×218

≡ 9 (mod 407)

即ち9が暗号文。そして

103≡234 (mod 407)

が元の文。

――――――――

注意 ここでNすなわち407にあたる数も(公開キー7と同様に)

公開されています。したがってそれがRSA方式によるものであると

わかっており、また407=11×37であるとわかってしまえば、

7x≡1 (mod (11−1)(37−1)) (3)

なるxを解けばそれが秘密キーになるのです。

一般にはNとして数十桁から数百桁の数を使いますので、それを

二つの素数に素因子分解するのは容易でないことが知られています。

しかしひとたび2つの素数pとqがみつかってしまえば(3)の方程式を解くのはそれほどむずかしくはないのです。

最後のテストではNが小さい場合(Nをproductと呼んでいます)公開キーから秘密キーを割り出す問題も出ます(勿論Nが小さい場合)。

 

Back