公開鍵暗号方式の暗号化と復号化

公開鍵暗号方式の暗号化と復号化がどのように行われているのか頭の整理のためにまとめておく。

今回はキーペアの生成が済んでいる前提で、その後の暗号化や復号化が背景でどの様に計算されているのかにフォーカスしてまとめてみようと思います。

キーペアの生成方法やその証明については別記事でまとめようと思います。

暗号化と復号化の基本的な考え方

暗号化したい平文（値）を X としたとき、以下の性質を持つ e,d,N を決める。

ただし、$X < N$とする。

$$X^{ed} \equiv X \pmod{N}$$

これは合同式と言って、$X^{ed}$と$X$を$N$で割ったあまりが等しいことを意味する。

もう少し言い換えると、、$X^{ed}$を$N$で割るとあまりが$X$に戻る性質があるという事です。

$$X^{ed} \mod{N} = {(X^e)}^d \mod{N} \\ = {(X^e \mod{N}) }^d \mod{N} ・・・① \\$$

この式は ① の変形から分かるように以下の２つの操作に切り分けることが出来る。

$$C = X^e\mod{N} ・・・② \\ {C}^d\mod{N} = X ・・・③$$

② の操作が暗号化と言え$C$は暗号文です。
③ の操作が復号化と言えます。

ここで暗号化に使った$(e, N)$が俗に言う公開鍵で、$(d, N)$が秘密鍵です。

この暗号化と復号化の流れは以下の式のように逆にもできます。

$$C = X^d\mod{N} \\ {C}^e\mod{N} = X$$

公開鍵暗号方式の説明でよく、公開鍵で暗号化したものは秘密鍵で復号化でき、秘密鍵で暗号化したものは公開鍵で復号化できるという説明があるが、これは式を見れば一目瞭然ですね。

この様に、難しそうに聞こえる暗号化の技術ですが、実はシンプルな合同式の性質に基づいて成立しているアルゴリズムです。

① の式変形の補足

以下の等式が成り立つロジックを説明します。

$$X^{ed} \mod{N} = {(X^e)}^d \mod{N} \\ = {(X^e \mod{N}) }^d \mod{N} ・・・① \\$$

簡単にするために以下の式で証明をします。

$$a^k \mod{n} = (a \mod{n})^k \mod{n}・・・④$$

$$r = a\mod{n}・・・⑤とすると$$

$$a = nq+r$$

$$a^k = {(nq+r)}^k$$

二項定理により

$$a^k = \sum_{i=0}^k {}_k C_i {(nq)}^i\times{r^{k-i}}$$

ここで、右辺は$i=0$のときの$r^k$のとき以外は$n$の倍数なので$\pmod{n}$においては無視できます。すなわち

$$a^k \equiv r^k \pmod{n}$$

⑤ より$r = a\mod{n}$なので

$$a^k \equiv {(a\mod{n})}^k \pmod{n}$$

よって ④ は証明された。

おわりに

今回は、公開鍵と秘密鍵が生成済みの前提で、平文の暗号化と復号化の裏側の計算がどの様に行われているのかをみていきました。

次回は、そもそもこれらのキーペアはどの様に生成するのかと、生成ロジックの証明にフォーカスして記事をまとめようと思います。