公開鍵暗号
『暗号技術のすべて』の第4章を参考にしました。 この章は、公開鍵暗号について書かれています。
公開鍵暗号とは
これまでに紹介したDESやAESのような共通鍵暗号は、事前に送受信者間で共通鍵を共有しなければならないという問題がありました。こうした問題を解決する手法として提案されたのが、公開鍵暗号です。
公開鍵暗号は、通信相手の公開鍵で暗号化し、自身の秘密鍵で復号する暗号です。その名の通り、公開鍵とは公開されているので誰でも参照できます。送信者は、相手の公開鍵で平文を暗号化し、暗号文を生成します。秘密鍵は、秘密に管理されるべき鍵のことで、自身に暗号文が送られてきたら、秘密鍵を使って復号します。
このような仕組みにより鍵の共有をすることなく、Bobから送られてくるメッセージは、Aliceしか復号できないということになります。
公開鍵暗号の安全性指標
公開鍵暗号の安全性レベルは攻撃モデルと解読モデルの組み合わせで決定されます。 例えば、解読モデルが一方向性、攻撃モデルが選択平文攻撃であるとき、OW-CPA安全といいます。
攻撃モデル
選択平文攻撃（CPA）
あらかじめ選択した平文と、それに対応した暗号文を利用した攻撃。
選択暗号文攻撃（CCA）
あらかじめ選択した暗号文と、それに対応した平文を利用した攻撃。一度のみ復号オラクルにアクセスできる。
適応的選択暗号文攻撃（CCA2）
あらかじめ選択した暗号文と、それに対応した平文を利用した攻撃。いつでも復号オラクルにアクセスできる。
解読モデル
一方向性（OW）
秘密鍵を用いずに復号することは困難であること。
識別不可能性（IND）
2つの平文m0、m1のどちらかの暗号文cが与えられたとき、その暗号文がどちらの平文を暗号化したものかを識別することが不可能であること。
公開鍵に対する攻撃
公開鍵のすり替え
公開鍵が正しいか（本当に通信相手のものかどうか）をどのように保証するのかという問題があります。この問題を解決する手段として、公開鍵基盤（PKI）というものがあります。インターネット上に存在する認証局と呼ばれる機関にユーザーと公開鍵の関係を保証する証明書を発行してもらい、公開鍵を使用するユーザーは、これを参照することで、公開鍵の正当性を検証することができます。
全数探索攻撃
公開鍵暗号の秘密鍵に対して、全数探索攻撃を行ったとします。鍵長がkビットであったとしても、実際に使われている鍵は2k個よりはるかに少ないです。それは、鍵の仕様が定められているからです。 このことから、全数探索攻撃において、共通鍵暗号と公開鍵暗号の鍵長が同じであった場合、公開鍵暗号の方が検査すべき計算回数が少なくて済みます。
