RSA公開鍵暗号方式を使用した暗号化と復号化

花子が、どのようにして秘密鍵($d$)と公開鍵($n$と$e$)を導くのかをみ てみます。

(1)

花子は、互いに素である(1以外に公約数を持たない)2つの非常に大きな素数$p$と$q$を適当 に選択する。ここで、花子は$p$と$q$の数値を他人に絶対に秘密 にしなければならない。なぜなら、$p$と$q$の数値がわかると、 公開鍵$e$から秘密鍵$d$を計算するのは容易であるからである。

(2)

1つ目の公開鍵 $n=p\times q$を計算する。

(3)

花子は、 $(e\times d) mod  \phi_{n}=1$になるような秘密鍵$d$ を計算する。ここで、 $\phi_{n}=(p-1)\times(q-1)$であり、 $(e\times d) mod  \phi_{n}=1$という表記は、「$e\times d$を $\phi_{n}$で割った余りが1に等しい」ということを意味する。 $e$は$\phi_{n}$と互いに素になる任意の整数で、2つ目の公開鍵 として使われる。

このように、花子は、自分の秘密鍵$d$と公開鍵$n$と$e$を用意することができ ます。

次に、太郎は、花子から受け取った公開鍵$n$と$e$を使って、花子に送るメッセー ジ$M$を暗号化して、それを花子に送ります。メッセージの暗号化は、

$$C=M^{e} mod n$$

という式を使って数学的に暗号化されます。ここで、$C$が暗号化されたメッセー ジになります。

花子の公開鍵で暗号化されたメッセージを送信してもらった花子は、自分の秘密 鍵$d$と

$$M=C^{d} mod n$$

という式を使って、暗号化されたメッセージ$C$を元のメッセージ$M$に復号化で きます。

実際に簡単な整数を使って、RSA公開鍵暗号方式の例を見てみましょう。

(1)

花子は、互いに素である(1以外に公約数を持たない)2つの素数$p=11$ と$q=13$を選択したとする。($p$と$q$は非常に大きな素数でな ければならないが、ここでは、話を簡単にするため、小さな素数 を使うことにする。)

(2)

1つ目の公開鍵$n$は、 $n=p\times q=11\times13=143$になる。

(3)

$\phi_{n}=(p-1)\times (q-1)=(11-1)\times(13-1)=10\times12=120$になる。

(4)

ここで、花子は、 $\phi_{n}=120$と互いに素になる整数$e$として、 $e=7$を選択したとする。

(5)

次に、花子は、 $(e\times d) mod  \phi_{n}=1$になるような秘密鍵$d$ をみつけなければならない。$d$を1から1つずつ増加させながら、 $\phi_{n}=120$で割った余りが1になるような$d$を探していくと、 $d=103$のところで、ちょうど余りが1になる。したがって、$d=103$が 得られる。

これで、花子は、自分の秘密鍵$d=103$と公開鍵$n=143$と$e=7$を用意すること ができました。

次に、太郎は、花子にある文字を送信するため、その文字を10進数$M$に変換し ます。ここで、日本語1文字は、16ビットであるので、65,536通りの整数値をと ることができます。いま、その変換された10進数が$M=5$になったとしましょう。太郎は花子から受け取った公開鍵$n=143$と$e=7$を使って、花子に送信するメッセージ$M$ を暗号化します。$M=5$を暗号化すると、

$$C = M^{e} mod n$$

$$= 5^{7} mod 143$$

$$= 47$$

という暗号化されたメッセージ$C=47$が得られます。暗号化された整数$C=47$を 送信された花子は、自分の秘密鍵$d=103$を使って、

$$M = C^{d} mod n$$

$$= 47^{103} mod 120$$

$$= 5$$

によって$C=47$を復号化し、$M=5$を得ることができます。花子は、この10進数 $M$をそれに対応する文字に変換すれば、太郎から送信された文字を読むことが できます。ここで、$47^{103}$を電卓で計算するわけにはいきません。そこで、 $C^{d} mod n$の計算は、かけ算$C\times C$を1回繰り返すごとに$n$で割った余 りを計算し、その余りに$C$をかけた値を、さらに$n$で割った余りを計算するこ とを($d-2$)回繰り返せばよいことと同じになります。

この例では、公開鍵の数値$n=143$と$e=7$は小さい値なので、秘密鍵$d=103$は 簡単に推測できます。$n=143$を素因数分解すれば、

$$143=1\times 143$$

$$143=11\times 13$$

$$143=143\times 1$$

の3つの場合だけが得られます。これから、

$$p = 11$$

$$q = 13$$

$$\phi_{n} = (p-1)\times(q-1)=120$$

は簡単に推測することができます。$e=5$がわかっているので、 $7\times d mod \phi_{n}=1$の計算において、$d$を1から1つずつ増加させなが ら、 $\phi_{n}=120$で割った余りが1になるような$d$を探していくと、$d=103$ は簡単に得られます。つまり、秘密鍵は簡単に見破られてしまうことになります。 したがって、強い暗号にするためには、公開鍵の数値は非常に大きな数でなけれ ばなりません。RSA暗号化方式では、1024ビットの公開鍵を使うことが推奨され ています。