秘密鍵暗号と公開鍵暗号 - ト部蛸焼のブログ

最近，暗号分野の勉強をしているので，今回はそれに関する話です．

暗号
秘密鍵暗号の枠組み
公開鍵暗号の枠組み
安全性
参考文献

暗号

現代では様々な人が様々な形で情報を伝えています．その中には，誰かだけに伝えるべき秘密性の高い内容が含まれることがあります．自分の名前や年齢などの個人を特定することができる情報や自分の体重や休日の過ごし方などの社会的に知られることが憚られる情報はその例です．そんな秘密性の高い情報を相手に伝えつつも第三者には漏らさないために，暗号を使うのが有効です．

以下の説明のために，ざっと用語を定義します．

定義1. 暗号化 (encryption) ……文章を他の人に知られないような形に変換すること．暗号化する関数を $\mathrm{Enc}$ で表す．
2. 平文 (plaintext) ……暗号化する前の文．
3. 復号 (decryption) ……暗号化された文章を元の平文に戻す操作のこと．復号する関数を $\mathrm{Dec}$ で表す．
4. 鍵 (key) ……暗号化する際に使われるパラメータ．暗号の手法によっては存在しないこともある．

暗号は情報の伝達を前提としているため，その枠組みは次の図で表すことができます*1．

f:id:tobetakoyaki:20191102172532p:plain — 暗号化と復号の流れ

学問的に研究される暗号には2種類，秘密鍵暗号 (secret key cryptography) と公開鍵暗号 (public key cryptography) とがあります．詳しくみていきます．

秘密鍵暗号の枠組み

秘密鍵暗号*2は，暗号化する鍵と復号する鍵が同一の暗号のことをいいます．例えば次のVernam暗号は秘密鍵暗号の一種です．

Vernam暗号入力: 平文 $m$ ( $n$ ビット)
Step1. 乱数 $r$ を生成する*3．
Step2. 暗号化関数は*4
\begin{align}
\operatorname{Enc} (m) = m \oplus r.
\end{align}Step3. 復号関数は
\begin{align}
\operatorname{Dec} (y) = y \oplus r.
\end{align}

まずはこのプロトコルの正しさを確認します．Aさんが平文 $m$ を伝えるとき，
\begin{align}
\operatorname{Dec}(\operatorname{Enc}(m)) &= (m \oplus r) \oplus r \\
&= m \oplus (r \oplus r) \\
&= m \oplus 0 \\
&= m
\end{align}となり，Bさんが復号して得た平文はAさんが伝えたかった平文と一致します．このように暗号のプロトコルがきちんと平文を伝達することを，今後は「正当性がある」と表現することにします*5．

このVernam暗号は乱数 $r$ が秘密鍵であり，これが漏れない限りは他者に暗号文 $\operatorname{Enc} (m)$ が漏れたとしても元の平文 $m$ は特定できません．ちなみにこの暗号は後に述べる情報理論的に安全な暗号です．

Vernam暗号はなんだか強そうな安全性をもつので良さそうに見えます．しかしながら，よく考えると復号に使う乱数 $r$ を相手にどう伝えるかが問題になります．この乱数をそのまま相手に伝えようとしてみましょう．暗号化に使った乱数 $r$ は，平文と同じビット数になります*6．もし乱数をそのまま送ってしまったら，その乱数 $r$ は容易に盗み見られてしまい，簡単に暗号が破られてしまいます．これでは意味がありません．一方でこの乱数をまたVernam暗号で暗号化したら……これでは同じことの繰り返しです．どうすれば良いのでしょう．何か別の暗号の枠組みが必要になりそうです．

公開鍵暗号の枠組み

公開鍵暗号はおおよそ次の3つのステージから構成されます．

公開鍵暗号の枠組み1. 鍵生成 (key generation)
秘密鍵 (secret key) $\mathsf{sk}$ と公開鍵 (public key) $\mathsf{pk}$ を作り，公開鍵だけを公開する．

2. 暗号化 (encryption)
平文 $m$ と公開鍵 $\mathsf{pk}$ から暗号文を作る．暗号を作る関数を $\operatorname{Enc}(\mathsf{pk},m)$ と書く*7．

3. 復号 (decryption)
秘密鍵 $\mathsf{sk}$ を使って暗号文 $c$ を平文に戻す．復号を行う関数を $\operatorname{Dec}(\mathsf{sk},c)$ と書く．

公開鍵暗号にはElGamal暗号，RSA暗号，Paillier暗号などがあります．この3つはすべて代数学に基づいて構築された暗号です．

この公開鍵暗号を用いると，先ほどの共通鍵暗号のところで述べた「乱数をどう渡すか」という部分に関する一つの答えが得られます．

Aさんが平文 $m$ をなんとかしてBさんに伝えたいとします．Bさんは乱数を受け取るために，公開鍵 $\mathsf{pk}$ と秘密鍵 $\mathsf{sk}$ を作り，公開鍵を公開しました．Aさんはこの公開鍵から暗号文 $\operatorname{Enc}^{\prime}(\mathsf{pk}, r)$ *8を送ります．Bさんはこれを自分しか知らない秘密鍵 $\mathsf{sk}$ で復号します．これでAさんたちは盗聴者に知られずして乱数を共有することができました．めでたしめでたし！*9

安全性

暗号を学ぶ上で重要になる概念が「安全性 (security)」です．その安全性には次の2つの種類があります．

1つ目が情報理論的安全性 (information-theoretic security) です．暗号を破ろうとしている第三者が「平文はこれだ」と答える状況を考え，彼の解答を確率変数とみなして $Y$ とおきます．正しい平文を $m$ としたとき， $\operatorname{Enc}$ を伴う暗号方式が情報論的安全であるとは，
\begin{align}
P(Y = m\,|\, \operatorname{Enc}(m) ) = P(Y=m)
\end{align}が成り立つことを言います．標語的に言えば，「 $\operatorname{Enc}(m)$ を知っていても，当てずっぽうに平文を推測する人と正解率は変わらない」ということになります．先に述べたVernam暗号は情報理論的に安全な暗号です．

2つ目が計算量的安全性(computational security) です．これは，当てずっぽうに平文を推測する場合の計算量より小さい計算量で暗号を破ることができない場合に用いられます．しばしば問題の難しさに関する適当な仮定を伴って用いられる概念です．例えば先に紹介したEl Gamal暗号はCDH仮定*10のもとで計算量的に安全といえます．

計算量的安全性は適当な仮定のもとで保証された安全性なので，その仮定が誤りだと分かれば立ちどころに安全性が失われるものとなります．一方で，量子コンピュータによる計算が実用化されれば，今は情報理論的に安全とされている暗号も実は安全でなくなってしまう可能性もあります．量子コンピュータ技術の発展が目覚ましい現代において，この先の暗号がどうなっていくかは興味深いところですが，今回はそこには足を踏み入れないでおきます．