namdicul's blog

気ままに更新します. CTFと暗号理論について勉強中です.

暗号理論(3) ~ 公開鍵暗号方式 ~

暗号技術入門 第3版

暗号技術入門 第3版

暗号理論入門 原書第3版

暗号理論入門 原書第3版


前回は共通鍵暗号方式について解説をしましたが, 今回は公開鍵暗号方式について説明をしていきたいと思います.

前回の記事でも紹介したように, 共通鍵暗号方式では鍵配送問題がつきものです. どのようにして受信者と送信者間で鍵を共有するかが問題となってきます.

この鍵配送問題を解決するには, 以下のような方法があります.

鍵の事前共有による解決

鍵配送問題を解決するためのもっとも簡単な手法は, 事前に安全な手段で(物理的に)鍵を共有することです. 例えば, 隣の席の人と鍵を事前共有するには, 鍵の情報が入ったUSBをそのまま物理的に手渡しすれば良いですね.

しかし, このような事前共有には限界があります. 例えば, 沖縄に住んでいるAさんが北海道に住んでいるBさんと鍵を事前共有するとします. このとき, AさんはBさんが住んでいる北海道まで移動しなければなりません.

では郵送するのはどうでしょう. これは安全な手段とは言えません. 誰かが郵送途中に鍵情報を盗もうとする人がいるかもしれないからです.

このように, 鍵の事前共有は1番安全な鍵配送手段でありますが, 使える場面は限られてきます.

鍵配布センターによる解決

各人の鍵をデータベースとして保存しておく鍵配布センターを用意することで, 鍵の事前共有が可能となります.
例えば, ある会社に鍵配布センターを用意しておき, その会社の社員それぞれの鍵をデータベースとして保存しておきます.
ここで, この会社の社員であるAさんがBさんと通信したいということになりました. Aさんは鍵配布センターに「Bさんと通信したい」と申し出ます. 鍵配布センターは, 擬似乱数生成器を使用してセッション鍵を生成し, Aさんの鍵でセッション鍵を暗号化してAさんに送信します. また, Bさんの鍵で同じセッション鍵を暗号化してBさんに送ります.
Aさん, Bさんはそれぞれ自分の鍵で暗号文を復号することができ, 同じセッション鍵を共有することができます.

このような手順でAさんとBさんは同じ鍵を事前共有することができます.


しかし, 鍵配布センターのサーバがダウンしてしまうと, 社員間で通信することができなくなってしまいます(正確には通信はできるのですが, 平文でのやりとりになってしまいます). またデータベースの情報が盗まれてしまったら, その組織間の通信内容がダダ漏れになってしまいます. 鍵配布センターを使用するときには, これらのことに気をつけなければいけません.

Diffie-Hellmanの鍵共有プロトコルによる解決

Diffie-Hellmanの鍵共有プロトコルは, 離散対数問題の計算困難性を利用した鍵共有方法です. これは別の記事で紹介します.

(2018/10/11 記事を書きました.)
tomonori4565.hatenablog.com

公開鍵暗号方式による解決

いよいよ本題です. 公開鍵暗号方式とは, 暗号化と復号化に使用する鍵が同じでない暗号方式でしたね.


具体的に見てみましょう.


データの受信者(復号化をする人)は, 公開鍵と秘密鍵を作成します. 公開鍵はその名の通り他人に知られても良い鍵です. しかし秘密鍵は絶対に他人に知られてはいけません.

データの送信者(暗号化をする人)は, 受信者から公開鍵を取得します.

f:id:tomonori4565:20180821215002p:plain

取得したら, 暗号化したいデータを公開鍵により暗号化します. そしてそのデータを受信者に送信します.

f:id:tomonori4565:20180821215156p:plain

受信者は, 暗号データを受信したら秘密鍵を使って復号化します.

f:id:tomonori4565:20180821215232p:plain

こうすることで安全にデータを送信することができます.


ここで, やりとりされているデータを盗聴し, 元データ(平文)を取得しようと試みましょう. 受信者と送信者間でやりとりされているデータは, 公開鍵と暗号化データのみです. 公開鍵のみではデータを復号化することはできないので, 秘密鍵がバレない限り元データが復元されることはありません.


公開鍵暗号方式を採用している暗号方式の代表的なものの1つはRSA暗号です.
RSA暗号については以前まとめた記事があるのでそれを参照にしてください.

tomonori4565.hatenablog.com




では公開鍵暗号方式を採用すれば, (正しく鍵の管理ができれば)絶対に平文が漏れることはないし, 安心だね!!!!



...とはならないのです. 世の中, 100%安全にデータを送信する手段は確立されていません.




次のような状況を考えてみましょう.



AさんとBさんが公開鍵暗号方式を採用してデータのやりとりを行おうとしています.
ここで, AさんがBさんに平文Aを送信する場合を考えましょう.

通信するための事前準備として, Aさんは平文A, Bさんは公開鍵Bと秘密鍵Bを持っています.

ただ, AさんとBさんの通信を盗聴する悪い人Xさんがいます.
Xさんも公開鍵Xと秘密鍵X, そして平文Xを持っています.

f:id:tomonori4565:20180821223627p:plain

まずAさんはBさんの公開鍵Bを取得しようとします.

f:id:tomonori4565:20180821223639p:plain

ここでXさんは公開鍵Bを盗み取り, Aさんの手に渡らないようにします. 代わりに, Xさんが用意した公開鍵XをAさんに送信します.
当然Aさんには, 公開鍵が途中ですり替えられていることには気づきません.

f:id:tomonori4565:20180821223647p:plain
f:id:tomonori4565:20180821223655p:plain

Aさんは公開鍵Xを使って平文Aを暗号化して, Bさんに送信しようとします(送信データを暗号文AXとします).


f:id:tomonori4565:20180821223705p:plain

Xさんはこの暗号文AXを盗み取り, Bさんの手に渡らないようにします.
暗号文AXは公開鍵Xで暗号化されているため, 秘密鍵Xによって平文Aを復号することができます.

f:id:tomonori4565:20180821223714p:plain
f:id:tomonori4565:20180821223723p:plain

さて次にXさんは平文Xを, 先ほど取得した公開鍵Bを使って暗号化して, Bさんに送信します(送信データを暗号文XBとします).


f:id:tomonori4565:20180821223731p:plain

暗号文XBは公開鍵Bで暗号化されているため, 秘密鍵Bによって平文Xを復号化することができます.

f:id:tomonori4565:20180821223739p:plain


このようにすると, AさんからBさんに送信したデータはXさんの手元にあり, Xさんが作成した悪意あるデータがBさんの手元に渡ることになります.


このように, 送信者と受信者の間のデータを盗聴し, データをすり替える攻撃手法をman-in-the-middle攻撃と言います. man-in-the-middle攻撃は, 任意の公開鍵暗号方式に対して適用可能です.

せっかく鍵配送問題が公開鍵暗号方式によって解決したのに, また新たな問題が発生してしまいましたね...


ではman-in-the-middle攻撃を防ぐにはどうしたらいいでしょうか.

先ほどの例で問題なのは, Xさんによって公開鍵がすり替えられていることをAさんが気づかないということです.
Aさんが取得した公開鍵は本当にBさんが作成したものなのか, ということを知る手段(認証といいます)が必要です.
認証については別の記事で紹介しようと思います.

暗号技術のすべて

暗号技術のすべて

暗号技術入門 第3版

暗号技術入門 第3版