気まぐれブログ(日記・技術記事・研究のことなど)

気まぐれに更新します.温かい目で見ていただければ...

暗号理論(7) ~ デジタル署名 ~

暗号技術入門 第3版

暗号技術入門 第3版

暗号技術のすべて

暗号技術のすべて

デジタル署名とは

前回の記事では, メッセージ認証コードの話をしました. メッセージ認証コードを使用することで, 送信データが改ざんされていないか, あるいはなりすましされていないかということを検証することができました.
しかし, メッセージ認証コードだけでは第三者に「このデータはこの人が送信したものだ」と証明することはできません. さらに, 否認を防止することもできません.


そもそもメッセージ認証コードでは, なぜ第三者への証明や否認を防止することができないのかというと, 二者間で「同じ共有鍵を使用しているから」です.

では, どうしたら第三者に対して証明できたり, 否認を防止することができるのでしょうか.


それは, 送信者と受信者で「違う鍵を使用する」ことで可能になります.

ここからは従来のやり方に沿って, AliceとBobのやり取りを例に説明していきます. AliceがBobにデータを送信する場合を考えましょう.
Aliceさんは事前に公開鍵と秘密鍵を用意しておきます. 次にBobさんに送信したいデータを秘密鍵で「署名」します(署名は「暗号化」と置き換えてもらっても構いません). 続いて, もとのデータと「署名」したデータをBobさんに送信します.
Bobさんは, これらを受け取り, さらにAliceさんの公開鍵を取得します. Bobさんは公開鍵を用いて署名されたデータを「検証」します(検証は「復号化」と置き換えてもらっても構いません). その結果, もとのデータと検証したデータが一致すれば, そのデータはAliceさんが送信したものだと確認することができます.


ここまではメッセージ認証コードの仕組みとそんなに変わりませんね. でもここからがメッセージ認証コードとデジタル署名の大きな違いです.

では, Bobさんが受け取ったデータが本当にAliceさんのものであるかを第三者に証明するとしましょう. どうしたらいいでしょうか.



簡単なことです. Aliceさんが送信したデータを, 検証する第三者Victorが受け取り, Aliceさんの公開鍵で正しいデータかどうかを実際に検証すればいいだけなのです.

ではどうしてVictorはそのデータがAliceさんが送信したものだと証明できるのでしょうか.


それは, 「署名データはAliceさんにしか作り出せない」からです.

秘密鍵を持っている人にしか, デジタル署名を施すことができません. なので, その人の公開鍵で実際に検証が成功すれば, データの送信者を一意に特定することができます.



これまでの記事を読んで理解が深まっていらっしゃる人は, デジタル署名の仕組みについて何か気づいたかもしれません.


デジタル署名は, 「公開鍵暗号方式と逆の関係」であるということが言えます.

公開鍵暗号とデジタル署名

公開鍵暗号方式については以下の記事を復習してください.
tomonori4565.hatenablog.com

公開鍵暗号方式では, 公開鍵を暗号化に使用し, 秘密鍵を復号化に使用していました.
デジタル署名では逆の関係になります. 秘密鍵を署名(暗号化)に使用して, 公開鍵で検証(復号化)するのです.

ここで, なぜ暗号化が署名の作成に相当して, 復号化が署名の検証に相当するのかを考えてみましょう.

公開鍵暗号方式の記事でも説明したように, 公開鍵と秘密鍵は「数学的に深い関連をもつ」鍵ペアでなければいけません. よって秘密鍵で暗号化した暗号文は, その秘密鍵とペアになっている公開鍵でしか復号化することはできないのです. そして, 正しく復号ができていれば, その公開鍵と対になっている秘密鍵で暗号化されたんだということがわかりますね.


以上からもわかるように, デジタル署名は, 「公開鍵暗号方式と逆の関係」であるということが言えるのです.

デジタル署名の方法

ここからは, どのようにデジタル署名が施されるかということについて説明していきます.

主に2通りの署名方法があります.
(1) メッセージに直接署名する方法
(2) メッセージのハッシュ値に署名する方法

今回は, 主に使用されている「(2) メッセージのハッシュ値に署名する方法」について解説していきます.

メッセージのハッシュ値に署名する方法

ここでもAliceさんがBobさんにメッセージを送信する場合を考えましょう.

以下に署名の流れを示します.

(こちらのサイトに乗っている図が参考になるかもしれません. )
www.infraexpert.com


(1) まず, Aliceさんはメッセージのハッシュ値を計算します.

(2) 次にAliceさんはハッシュ値秘密鍵で署名(暗号化)します.

(3) Aliceさんは, もとのハッシュ値と署名データをBobに送信します.

(4) Bobさんは, 受信した署名をAliceの公開鍵で検証(復号化)します.

(5) Bobさんは, 検証データとハッシュ値を比較して, 一致するかどうかを確認します. 一致すれば検証成功です.


このような流れになっています.

デジタル署名に対する攻撃

man-in-the-middle攻撃

公開鍵暗号方式では, man-in-the-middle攻撃が脅威となりましたが, デジタル署名に対しても脅威となります(公開鍵暗号方式の逆の関係なので想像はつくと思います).

man-in-the-middle攻撃を防ぐには, 公開鍵が本当に正しい相手のものなのかを確認する必要があります. 例えば, 入手した公開鍵がAliceさんのものであるか, Bobさんが確かめるとしましょう. BobさんはAliceさんに電話をかけ, 自分が持っている公開鍵が本当にAliceさんのものなのかを確かめることができます.

では電話などでチェックできない場合はどうしたらいいのでしょうか. それは, 次回の記事で紹介する「証明書」で説明します. 証明書を用いれば, 公開鍵が正しいものかどうかを証明することができます.

デジタル署名を駆使した公開鍵暗号方式に対する攻撃

RSA暗号を用いでデジタル署名を作成しようとすると, 以下のようになります.


  m^d \ \  mod \ \  N

これは, 公開鍵暗号方式における復号操作となります. この仕組みを利用して, 公開鍵暗号方式を攻撃することができます.

攻撃者Malloryは, AliceとBobの通信を盗聴しています. Malloryはこのやり取りの内容を解読したいので, Bobにこんなメールを書きました.

Bobへ,
現在デジタル署名の実験をしているのですが, 添付データにあなたの署名をつけて返信してください.
添付データはランダムなので問題は発生しません.
Malloryより.

BobはMalloryのメールを読んで, 添付データを閲覧しましたが, メールの本文の通りランダムなデータに見えます.
しかし実際には, 添付データはAliceがBobの公開鍵で暗号化した暗号文なのです. 当然, Bobが署名をしてしまうと, もとのデータが復元されてしまうことになります.

このデータをうっかりMalloryに返信してしまうとさあ大変. Malloryは何も苦労せず平文をGetできてしまうのです. Bob本人に復号化をさせるという大胆な方式ですね.

これを防ぐには, まず公開鍵暗号方式で使用する鍵ペアと, デジタル署名で使用する鍵ペアを分けておく必要があります. 他にも, メッセージに直接署名するのではなく, ハッシュ値に署名をするなどの対策が考えられますが, 何と言っても一番の対策方法は, 意味不明なメッセージにはデジタル署名をしないということです.

デジタル署名では解決できない問題

デジタル署名によって, 改ざんやなりすまし, そして第三者に対して「このデータはこの人が送信した」ということを証明できたり, 否認防止が可能になったりします.
これで悪意ある第三者からの攻撃が来ても安心 ...



...とはなりません. 前にも言いましたが, 絶対安全な通信手段はまだまだ確立されていません.



本記事の途中でも言いましたが, デジタル署名において, 受け取った公開鍵というのは本当に正しい相手のものでしょうか. もしかしたら悪意ある攻撃者Malloryが勝手にすり替えた公開鍵かもしれません. 次の記事において, 「証明書」について説明しますが, これは受け取った公開鍵が本当に意図した人物のものなのかを確認することができます.

暗号理論(6) ~メッセージ認証コード~

暗号技術入門 第3版

暗号技術入門 第3版

暗号技術のすべて

暗号技術のすべて

メッセージ認証コードで何ができるの??

前回の記事では, 一方向ハッシュ関数について説明しました.

一方向ハッシュ関数を使用することで, メッセージが改竄されたかどうかを検出することができるというメリットがありました.
例えば, AliceさんがBobさんにメッセージを送る場合を考えます. Aliceさんはメッセージとそのハッシュ値をBobさんに送信します. Bobさんはそのメッセージのハッシュ値を求め, 送られてきたハッシュ値と一致していればメッセージが改竄されていないことがわかります.

しかしここで問題があります. 能動的攻撃者MalloryがAliceさんからのメッセージとハッシュ値を取得してBobさんの手に渡らないようにし, 代わりに全く別のメッセージとそのハッシュ値をBobさんに送ることが可能です. BobさんはAliceさんからきたと思われるメッセージのハッシュ値を求め, 送られてきたハッシュ値を比較することで改竄されているか確認します. 改竄が検出されていないことを確認し, そのメッセージを受け取ります. しかしそのメッセージはMalloryからの悪意のあるメッセージなのです.

このように, 一方向ハッシュ関数ではメッセージの改竄を検出することはできますが, なりすましを検出することはできません.


これから紹介するメッセージ認証コードは, 改竄となりすましを検出するための手段の1つです.


メッセージ認証コードは, メッセージ2者間(送信者と受信者間)の共通鍵の2つを入力とし, 固定ビット長の出力を計算する関数です.このときの出力をMACと言います.

MAC値を計算するためにはあらかじめ共通鍵を知らなければいけません. よって共通鍵を知らない人はMAC値を求めることはできません.したがって, 送信されてきたメッセージと所有している共通鍵からMAC値を求めて, それが送信されてきたMAC値と一致した場合, 正しい相手から改竄されていないメッセージが送信されてきたと思ってよいわけです.

メッセージ認証コードは, 「鍵に依存した一方向ハッシュ関数」と考えることができますね.

図で表現すると以下のようになります.
f:id:tomonori4565:20181004112027p:plain

次に, メッセージ認証コードの内部の仕組みを見ていきましょう.

メッセージ認証コードの仕組み

メッセージ認証コードは, SHA-1MD5のようなハッシュ関数を使って実現することができます. ここでは, 代表的なHMACというメッセージ認証コードの仕組みを見ていきましょう.

以下の図がHMACの仕組みです.

f:id:tomonori4565:20181004115352p:plain

先ほども言ったように, メッセージ認証コードには「メッセージ」と「共通鍵」が入力されます. まずは入力された鍵について見ていきましょう.

メッセージ認証コードの内部では一方向ハッシュ関数を使用しているため, ブロック長をそのハッシュ関数に合わせてあげる必要があります. なので必要ならば入力された鍵に0をパディングしておきます.

次に, ipadとパディングした鍵のXORを取ります(この結果をipadkeyとします). ここでipadとは「ブロック長になるまで00110110を繰り返したもの」を指します. 例えばブロック長が64ビットであった場合, ipadは「00110110」× 8ということになります.

続いて, ipadkeyとメッセージを結合させ, 一方向ハッシュ関数に入力します(この結果をhash1とします).

今度は, opadとパディングした鍵のXORを取ります(この結果をopadkeyとします). ここでopadとは「ブロック長になるまで01011100を繰り返したもの」を指します.

あとは先ほどと同様に, opadkeyとhash1を結合させて一方向ハッシュ関数に入力します. その値がMAC値となるわけです.

手順をまとめると以下の通りになります.

(1) 必要ならば鍵へのパディング
(2) パディングした鍵とipadのXORをとる(結果をipadkeyとする)
(3) メッセージとipadkeyを結合し, 一方向ハッシュ関数に入力してハッシュ値を求める(このハッシュ値をhash1とする)
(4) パディングした鍵とopadのXORをとる(結果をopadkeyとする)
(5) hash1とopadkeyを結合し, 一方向ハッシュ関数に入力してハッシュ値を求める. このハッシュ値MAC値となる.

メッセージ認証コードに対する攻撃手法

再生攻撃

例えば以下のような状況を考えましょう.

MalloryはAlice銀行とBob銀行の通信を盗聴する悪い攻撃者です. MalloryはAlice銀行に行き, Bob銀行にある自分の口座に100万円を入金します. すると, Alice銀行はBob銀行に向けて以下のようなメッセージを作成するはずです.

Bob銀行へ,

口座C-5342に100万円を入金してちょうだい.

Alice銀行より.

Alice銀行はこのメッセージのMAC値を計算して, メッセージと共にBob銀行に送信しました. Bob銀行は送信されたMAC値と, 自分で計算したMAC値が一致することを確認し, データの改竄となりすましがされていないことを確認します. そのあと, Malloryの口座に100万円を入金します.


しかし, この一連のやり取りをMalloryは盗聴します. つまり, Alice銀行からBob銀行へ送信されたメッセージと正しいMAC値を盗聴して手元に保存しておきます. そしてメッセージと正しいMAC値をBob銀行へ向けて100回送信します.


するとどうなるでしょうか.


100回送信されたデータは全て同じものであり, メッセージに対する正しいMAC値が存在しているので, Bob銀行はこれらの送信されたデータは, 全てAlice銀行から送信された, データの改竄やなりすましがされていないデータだと判断してしまうのです.


すると結果的にはMalloryの口座に一億円が振り込まれてしまうことになりますね.


このような攻撃手法を「再生攻撃」と言います.

では再生攻撃を防ぐためにはどうしたら良いでしょうか. ここでは複数の手段を紹介します.


(1) データにシーケンス番号を含める.
送信メッセージにシーケンス番号という, 送信するごとに毎回1増加する番号を含めておきます. すると, メッセージ内容が一緒でも, MAC値が違ってくるので再生攻撃はできなくなります. ただ, 通信相手ごとにシーケンス番号を記憶しておく必要があるというデメリットもあります.

(2) タイムスタンプの使用
送信メッセージに現在時刻を掲載しておくことで, 再生攻撃を防ぐことができます. 過去のデータが送られてきた場合には, MAC値が正しくても無効なデータと判断します. こうすることで再生攻撃を防ぐことができます. しかし, 通信相手と自分の時計を一致させておかないと, 有効であるはずの送信データが無効になってしまう場合があります. また, 通信状態も加味して時間に余裕を持たせる必要があるので, 再生攻撃の余地が残ってしまいます.

(3) nonce
使い捨てのランダムな数値のことをnonceと言います. 受信者から送信者に向けてnonceを渡すことで, 同じメッセージでも毎回違ったMAC値を計算させることができます. しかし, 通信データ量が多くなってしまうのがデメリットです.

メッセージ認証コードでは防げない問題

三者に対する証明

メッセージ認証コードによって, なりすましとデータの改竄を検出できるようになりました. 従って, AliceからBobへデータを送信した際には, Bobは「Aliceがこのデータを送信したんだ」と解釈できるようになりました.

しかし, 第三者Victorに「Aliceがこのデータを送信したんだ」と証明することはできません. なぜならVictorは「いやいや, このデータはBobが作ったんじゃないの?」と考えることができるからです.

それもそのはず, AliceとBobは同じ共有鍵を所有しているので, BobがAliceと同じデータを作成することは「可能」なのです!

メッセージ認証コードを使用すれば, 通信し合っている2者間では, 送信されたデータは送信者Aliceのものだと解釈できます. 同じ共有鍵を使用している者のうち, その1人は自分だからです. しかし, 第三者に「このデータは送信者Aliceが本当に作成したものなんだ」と証明することは残念ながらできないのです.

次の記事で紹介する「デジタル署名」を使用すれば, 第三者に対する証明が可能となります.

否認防止

否認とは, データを送信したのちに「そんなデータ送ってないわ」と主張することを指します.

例えば, AliceがBobに「10000円貸して」というデータを送信したとします. BobはAliceに, 「なんで10000円が必要なんだい?」と尋ねます. そこでAliceは, 「そんなデータ送ってないわ」と主張できます. これを否認と言います.

メッセージ認証コードを用いただけでは, 否認を防ぐことはできません. 先ほども述べたように, 第三者に対して「このデータは本当にAliceが送ったものなんだ」と主張することはできないからです.

同様の理由で, デジタル署名を用いれば, 否認を防止することができます.

暗号技術入門 第3版

暗号技術入門 第3版

暗号技術のすべて

暗号技術のすべて

プロ野球データ解析 その3

データ解析作業に大分慣れてきました. 

 

本日は奪三振率についてデータ解析を実行してみました. やっぱりピッチャーって三振を奪ったときが一番かっこいいですし, 奪三振をたくさん取れるって魅力的ですよね...

 

前回同様, 2009年から2018年9月7日現在までの奪三振数と奪三振率をまとめてみました.

 

結果は以下の通りです.

 

f:id:tomonori4565:20180908002301p:plain

f:id:tomonori4565:20180908002304p:plain

 

またしても問題です!!!

 

今回は難易度をあげてみました. 奪三振率が高い上位5人を当ててみてください!!!

わかった人はコメントよろしくです^^

 

現在はNPBに属していない人も含まれているので, 注意してくださいね〜〜.

 

 

 

さて前回のクイズの正解を言いますね.

tomonori4565.hatenablog.com

 

負け数については,1位はヤクルトの石川投手, 2位はロッテの涌井投手, 

 

WHIPについては, 1位はダルビッシュ有投手, 2位は田中将大投手でした〜〜!!

 

さて, これまでやってきたことはただ単にデータをまとめてソートするだけでしたが, これからは, 例えばWHIPと勝利数の関係, 奪三振率と防御率の関係などをグラフ化していきたいなと思っております. 

 

みなさん暇つぶしがてら読んでいただけると幸いです^^

 

プロ野球データ解析 その2

久しぶりにデータ解析を.

 

前回同様に, プロ野球Freakというサイトから投手データを引っ張ってきて, データ処理を実行しました.

 

 

今回は2009年〜2018年9月5日現在の投手データから, 負け数とWHIPをまとめて表にしました.

 

負け数に関する結果は以下の通りです ↓↓↓

 

f:id:tomonori4565:20180906001948p:plain

 

突然ですが問題です!!

 

黒塗りに当てはまる選手(トップ2)は誰でしょうか??

 

わかった人はコメントくださいね^^

 

ちなみにヒントは, 

(1) 1位はセ・リーグ, 左P

(2) 2位はパ・リーグ, 右P

です.

 

当然ですが, 負け数が多い = ヘボピッチャーでは無いですからね〜〜.

 

以下はWHIPに関するデータです ↓↓↓

 

f:id:tomonori4565:20180906010039p:plain

f:id:tomonori4565:20180906010041p:plain

 

 

WHIPはあまり知られていない指標ですが, 1投球回あたり何人の走者を出したかを表す数値です. 

WHIPは, (与四球数 + 被安打数) / 投球回で計算できます.

 

さてここでもクイズです.

黒塗りに入る選手(トップ2)は誰でしょう??

 

ヒントとしては, 2人とも2018年現在NPBに所属していない選手です.

また, 上の表は2009年〜2018年9月5日現在までで総投球回が500以上の人のみを表示しています. 

 

勝ち数や負け数は運によるところも割とあるわけですが, WHIPは投手そのものの能力を評価するための基準となります. 

 

github.com

 

 

暗号理論(5) ~ 一方向ハッシュ関数 ~

暗号技術入門 第3版

暗号技術入門 第3版

暗号技術のすべて

暗号技術のすべて

一方向ハッシュ関数とは

前回の記事で, ハイブリッド暗号システムを紹介しました.

ハイブリッド暗号システムとは, 公開鍵暗号方式のデメリットの1つである「処理速度が遅い」ことを解決するための手法でありました.

また公開鍵暗号方式のもう一つのデメリットとして, 「man-in-the-middle攻撃に弱い」ことが挙げられます. これの対処法として, 「認証」というものが使われることを説明しました.


これから認証の話に入っていくのですが, その前に「正真性のチェック」をする手段である「一方向ハッシュ関数」について説明していこうと思います.

正真性とは, そのデータが本来のものである(本物である)という性質のことです.

例えば, Aliceさんが以下のような平文Aを作成したとします.

親愛なるBobへ

愛しています.
Aliceより.

Aliceさんは平文AをUSBに保存して, 自分の引き出しに入れておきました.

そして後日, この平文AをBobさんに送ることにしました.
このとき, 平文Aが

親愛なるBobへ

愛しています.
Aliceより.

となっていたら, 平文Aは正真性をもつと言えます.

一方, 悪意のある第三者Malloryが, USBを盗んで平文Aを以下のように書き換えたとします.

親愛なるBobへ

大嫌いです.
Aliceより.

このとき, 平文Aは正真性を持たないと言えます.


ではAliceさんが, この平文Aは正真性をもつかどうかを調べるにはどうしたらいいでしょうか.

1つの方法として, データをコピーしておき, 安全な場所に保存しておくことが挙げられます.
そして後日作業をするときに, コピー元のデータとコピーしたデータを比較して, 一致していたら正真性をもつことが言えます.


しかしこれはナンセンスです.
そもそも安全な場所に保存することができるならば, 正真性をチェックする必要がありません. さらにデータが巨大であった場合, コピーするにも, データを比較するにも時間がかかってしまいます.



ここで一方向ハッシュ関数の登場です.

一方向ハッシュ関数に対して入力データを与えると, ハッシュ値と呼ばれる固定バイト長の出力データを得ることができます.

f:id:tomonori4565:20180823202559p:plain

任意長のどんなデータも一方向ハッシュ関数に入力すれば, 固定バイト長のハッシュ値を得ることができます.

f:id:tomonori4565:20180823202750p:plain

また, 似ているデータが存在したとしても, そのハッシュ値は全く違うものになります.

例えば, パスワード「abcde」のハッシュ値(ここでは6バイトとします)が「15 0E 46 72 AD B8」だとしても,
パスワード「abcdf」のハッシュ値は「43 71 3E DD 96 CA」のように全く違うものになります.


このようにデータのハッシュ値を求めておいて, 次に利用するときにもう一度ハッシュ値を求めて, それらが一致するかどうかをチェックすることで, 正真性をチェックすることができます.


一方向ハッシュ関数がもつべき性質

次に, 一方向ハッシュ関数がもつべき性質について説明します.



一方向ハッシュ関数がもつべき性質は以下のものが挙げられます.

  1. 任意長のメッセージから固定長のハッシュ値を計算する
  2. ハッシュ値を高速に計算できる
  3. メッセージが異なればハッシュ値も高確率で異なる


3番に注目してみましょう.

メッセージが1ビットでも異なれば, ハッシュ値は高確率で異なる値を取らないといけません. そうでないと正真性を確認することができないからです.
2つの異なるメッセージが同じハッシュ値をもつことを衝突と言います.

1番で述べたようにハッシュ値は固定データ長なので, 取りうる値の個数は有限です. 例えばハッシュ値が80ビット長だとしたら,  2^{80}個のハッシュ値が存在します. しかし入力されるデータの個数は 2^{80}個以上なので, 鳩の巣原理より, 必ず同じハッシュ値をもつものが存在します.
つまり衝突は免れないのです!!


衝突がおきにくい性質のことを「衝突耐性」と言います.
衝突耐性には2種類あって, 弱衝突耐性強衝突耐性があります.


弱衝突耐性とは, あるメッセージのハッシュ値が与えられて, 同じハッシュ値を持つ別のメッセージを見つけ出すことが非常に困難な性質のことを言います.
強衝突耐性とは, ハッシュ値が一致するような異なる2つのメッセージを見つけ出すことが非常に困難である性質のことを言います.このとき, ハッシュ値はどの値をとっても構いません.


暗号技術で用いる一方向ハッシュ関数は, 弱衝突耐性と強衝突耐性の2つを持ち合わせる必要があります.

一方向性とは

一方向ハッシュ関数の「一方向」とはどういう意味でしょうか.

これは, あるデータからハッシュ値を計算することはできるが, ハッシュ値からあるデータを復元することはできないという意味です.
窓ガラスを割ると破片が飛び散りますが, その破片から窓ガラスを復元することはできませんね. それと同じことです.

一方向性は非常に重要な性質で, 今後「パスワードを元にした暗号化」や「擬似乱数生成器」を紹介するときに一方向性という概念を使用します.

一方向ハッシュ関数の応用例

一方向ハッシュ関数には以下のような応用例があります.

  • ソフトウェアの改竄検出

これは最初に説明しましたね. 途中で文書が書き換えられていた場合は, 異なるハッシュ値が得られる可能性が高くなってしまい, 改竄検出されてしまいます.

これらは別の記事でそれぞれ紹介したいと思います.

一方向ハッシュ関数への攻撃

これまで紹介したきた暗号技術には, それぞれ攻撃手法が存在しました. 一方向ハッシュ関数にはどのような攻撃手法が存在するでしょうか.
なかなか想像しにくいですね. 衝突耐性が強ければ同じハッシュ関数を求めることも難しいです.

ですが, 現段階では2つの攻撃手法が存在します. それらを紹介します.

弱衝突性を破る攻撃 (ブルート・フォース・アタック)

例えば以下のような状況を考えてみましょう.

AliceさんBobさんに電子ラブレターを書こうと思っています. そしてその電子ラブレターを12/25(クリスマス)にBobさんに送信しようと思っています.
12/24(クリスマスイブ)の夜, Aliceさんは電子ラブレターを作成し, PC内に保存しておきました.
ラブレターの本文には, 「Bobへ. あなたのことをとても愛しているわ. Aliceより」
そしてそのデータのハッシュ値をUSBに保存しておき, USBは安全な場所に保管しておきました. そしてAliceさんは寝床につきました.

その後, Aliceさん宅にEveさんが泥棒しに入り, PC内の電子ラブレターを書き換えようと思いました.
Eveさんは悪いやつなので, ラブレターを「Bobのことなんて大嫌い」というような要旨に書き換えようと思いました.

しかし, ただ書き換えてもいけません. なぜならAliceさんは元データのハッシュ値を持っているので, 書き換えてもハッシュ値が違う可能性が高いからです.

そこでEveさんは「Bobのことなんて大嫌い」というような要旨の文章を大量に機械的に作成しました.
例えば,
「Bobへ. あなたなんて大嫌い. Aliceより」
「Bobへ. Bobなんて大嫌い. Aliceより」
「Bobへ. あなたなんて大嫌いだわ. Aliceより」
「Bobへ. あなたなんて大嫌いよ. Aliceより」
「Bobへ. 大嫌いよ, あなたなんて. Aliceより」
「Bobへ. 大嫌い, Bobなんて. Aliceより」
「Bobへ. 顔も見たくないわ. Aliceより」
「Bobへ. 大嫌い, 顔も見たくない. Aliceより」
などなど...


そこで, たまたま元データとハッシュ値が同じである文章が作成できたとします.
Eveさんは悪い笑みを浮かべながらそのデータに書き換え, 家を後にしました.

そして12/25当日, AliceさんはBobさんに書き換えられたデータを送信してしまいました.

返事を待っていたのに, Aliceはずっと返事を得られないまま, 今後Bobと連絡を取れなくなってしまいました...


このように似ている文章を大量に作成し, 同じハッシュ値のものを見つけることによる攻撃が可能です.
いわゆる「ブルート・フォース・アタック」ですね.
この手法は, 一方向ハッシュ関数の「弱衝突耐性」を破ろうとする攻撃です.


強衝突耐性を破る攻撃 (誕生日攻撃)

上と似たストーリーを考えます.
悪いEveさんは, あらかじめハッシュ値が同じである2つの文章を作成しました. その2つの内容は,
「Bobへ. 愛しているわ. Aliceより」... (1)
というものと,
「Bobへ. 大嫌い, 顔も見たくない. Aliceより」 ... (2)
というものです.

そしてEveは(1)の文章とそのハッシュ値をAliceに送信します. Aliceはそのハッシュ値が正しいものかを実際に計算することで確認できます.
そしてその後, Eveは(1)の文章を(2)にすり替えます.

こうすることで, (2)の文章をBobあてに送ってしまうことで, 上のストーリーと同じ悲劇が実現されてしまいます.


このように, 同じハッシュ値をもつ2つの文章を事前に用意することによる攻撃を誕生日攻撃ということがあります. 誕生日攻撃は, 一方向ハッシュ関数の「強衝突耐性」を破ろうとする攻撃です.

一方向ハッシュ関数で解決できない問題

一方向ハッシュ関数は, 正真性をチェックするためにとても有効な手段であることがわかりました. しかしこれだけでは不十分です.
例えば, 能動的攻撃者MalloryがAliceのふりをして, Bobにメッセージとハッシュ関数の両方を送る場合を考えます.
Bobはメッセージのハッシュ値を実際に計算し, 送られてきたハッシュ値と比較して一致することが確認できれば正真性をチェックすることができます.

しかし, 送られてきたメッセージは実際にはAliceさんが送ったものではありません.
このように, メッセージの正真性をチェックすることはできても, 本当に意図した人物からのメッセージなのかということはチェックできません.
意図した人物からのメッセージなのかをチェックすることを認証と言います.

認証を行うための技術として, 「メッセージ認証コード」と「デジタル証明書」があります. これらは別の記事で紹介したいと思います.


暗号技術入門 第3版

暗号技術入門 第3版

暗号技術のすべて

暗号技術のすべて

暗号理論(4) ~ ハイブリッド暗号システム ~

暗号技術入門 第3版

暗号技術入門 第3版

暗号理論入門 原書第3版

暗号理論入門 原書第3版


前回の記事では公開鍵暗号方式について説明しました.

以前に公開鍵暗号方式のデメリットの1つとして, 「man-in-the-middle攻撃に弱い」というものを挙げました. この問題を解決するには, 公開鍵の「認証」が必要となります.

しかしもう1つ, 大きなデメリットがあります. それは, 「処理速度がかなり遅い」ということです.
このデメリットを解決するための技術が, これから紹介する「ハイブリッド暗号システム」です.

「ハイブリッド」と聞いたとき, 皆さんは最初に何を思い浮かべますか?


きっと多くの人が「ハイブリッド車」を思い浮かべるのではないでしょうか.


そもそもハイブリッド(hybrid)とは複数の方式を組み合わせた工業製品のことを指します. ハイブリッド車は「2つの動力(エンジンとモーター)を組み合わせて走る車」という意味ですね. なぜ2つの動力を組み合わせるのかというと, 電気自動車の欠点である低出力を, ガソリンエンジンまたはディーゼルエンジンで補完することができるからですね. 一方のデメリットを他方のメリットで相互的に補完するために複合化しているわけです.

ではハイブリッド暗号システムとは, 何を組み合わせてできた暗号方式なのでしょうか.



答えは, 「共通鍵暗号方式と公開鍵暗号方式」です.



ではハイブリッド暗号システムの仕組みを具体的にみていきましょう.


AさんがBさんに平文Aを送信する場合を考えます.
Aさんは平文Aと共通鍵(セッション鍵)を持ちます. Bさんは公開鍵Bと秘密鍵Bをセットで持ちます.

f:id:tomonori4565:20180822211226p:plain

AさんはBさんから公開鍵を取得します.

f:id:tomonori4565:20180822211251p:plain
f:id:tomonori4565:20180822211312p:plain

共通鍵を使って平文Aを暗号化します(これを平文Aの暗号文とします).
さらに公開鍵を使って共通鍵を暗号化します(これを共通鍵の暗号文とします).

f:id:tomonori4565:20180822211533p:plain

Aさんは2つの暗号文をBさんに送信します.

f:id:tomonori4565:20180822211607p:plain
f:id:tomonori4565:20180822211622p:plain

Bさんは秘密鍵を使って共通鍵を復号することができます.
さらにその共通鍵を使って平文Aを復号することができます.

f:id:tomonori4565:20180822211719p:plain
f:id:tomonori4565:20180822211728p:plain

これでAさんからBさんへ平文Aを送信することができました.



これでハイブリッド暗号システムの仕組みの解説は終わるのですが, なぜ共通鍵で平文を暗号化して, さらに公開鍵で共通鍵を暗号化する必要があるのでしょうか. いきなり平文を公開鍵で暗号化して, それを相手に送信し, 受信者が秘密鍵で復号化するという仕組み(まさに公開鍵暗号方式そのもの)ではいけないのでしょうか.


ここで, 公開鍵暗号方式共通鍵暗号方式のメリットとデメリットをまとめてみましょう.

鍵配送問題が解決できる

平文(元データ)のデータサイズが大きくなればなるほど暗号化と復号化に時間がかかる.

高速に暗号化と復号化ができる
鍵サイズが小さい

鍵配送問題が生じる



共通鍵のサイズが小さいので公開鍵暗号方式を採用してもそれほど暗号化と復号化に時間がかからなくなり, また公開鍵暗号方式を採用することで鍵配送問題が解決できます. さらに平文の暗号化と復号化は共通鍵暗号方式を採用しているので, 平文のデータサイズが大きくても高速に暗号化と復号化をすることができます.

このように, ハイブリッド暗号システムを採用することで, お互いのデメリットをお互いのメリットで補完することができるのです.


ハイブリッド暗号システムは暗号ソフトウェアであるPGPや, Webの暗号通信で使われているSSL/TLSで使用されています.

暗号技術入門 第3版

暗号技術入門 第3版

暗号理論入門 原書第3版

暗号理論入門 原書第3版

暗号理論(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版