namdicul's blog

気ままに更新します. CTFについて勉強中です.

プロ野球データ解析 その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の鍵共有プロトコルは, 離散対数問題の計算困難性を利用した鍵共有方法です. これは別の記事で紹介します.

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

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


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


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

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

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版

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

気分転換がてらプロ野球データ解析をやってみた.

 

プロ野球データFreakというサイトからデータを引っ張ってきて, データ処理をしてみました. 今回は2009年から2018年(8月19日現在)までの投手データを処理し, 勝利数をまとめました.

 

結果はこちら ↓↓↓

 

f:id:tomonori4565:20180819154607p:plain

 

こう見ると, やっぱり毎年良い成績を残し続けるのは難しいとわかりますね...

 

コードは以下のURLより取得できます.

github.com

 

また, コードを書くにあたって以下のサイトを大分参考にさせていただきましたm(__)m

qiita.com

 

また暇なときにプロ野球に関するデータ解析を進めていこうかなと思います. 

何か欲しいデータ等があったら教えて欲しいです. 

 

 

暗号技術入門 第3版

暗号技術入門 第3版

 

 

 

暗号技術のすべて

暗号技術のすべて

 

 

 

暗号理論(2) 〜 共通鍵暗号方式 〜

暗号技術入門 第3版

暗号技術入門 第3版

暗号技術のすべて

暗号技術のすべて


続いては, 共通鍵暗号方式について説明したいと思います. 



暗号方式には主に「共通鍵暗号方式」と「公開鍵暗号方式」に分類することができます. この記事では, 共通鍵暗号方式と公開鍵暗号方式の違いを説明し, 共通鍵暗号方式の代表的な例であるXORを用いた暗号方式, 使い捨てパッド(ワンタイムパッド), DESなどについて説明していこうと思います.

共通鍵暗号方式

共通鍵暗号方式とは, 暗号化と復号化に同じ鍵を用いることです. データの送信者と受信者が同じ鍵を持つことで簡単に共通鍵暗号方式を実現することができます.

f:id:tomonori4565:20180521155637j:plain
共通鍵暗号方式の概略図

共通鍵暗号方式は実現が簡単で運用しやすいのがメリットですが, もしこの共通鍵がデータのやり取りをする以外の者に知られてしまった場合, 簡単に復号化されてしまいます. また, データのやり取りをする両者が事前に共通鍵を共有できていればいいのですが, 実際にデータのやり取りをする人は面識のない人であることが多いです. よって, やり取りをする相手に共通鍵を渡さなければいけないのですが, その共通鍵をそのままネット上で渡そうとすると, 他者に鍵が知れ渡ってしまいます. このように共通鍵暗号方式では, 鍵配送問題が生じてきてしまいます.

公開鍵暗号方式

公開鍵暗号方式は, 暗号化と復号化で違う鍵を使用する暗号方式です.

f:id:tomonori4565:20180521155735j:plain
公開鍵暗号方式の概略図

公開鍵暗号方式では, 暗号化するための鍵(公開鍵)は全員に公開します. つまり公開鍵は誰でも入手することができます. しかし, 復号化するための鍵(秘密鍵) は復号化する人しか持ってはいけません. こうすることで, 共通鍵暗号方式のときに生じた鍵配送問題が解決されます.

XORによる共通鍵暗号方式の実現

ここでは, XOR(排他的論理和)を共通鍵として用いた共通鍵暗号方式を考えます.

XORとは演算子の1つで, 以下のような計算をします.


0 XOR 0 = 0
0 XOR 1 = 1
1 XOR 0 = 1
1 XOR 1 = 0

例えば, 01001100 XOR 10101010の計算結果は, 「11100110」になります.


ここで, 平文Aをビット列01001101, 共通鍵keyをビット列11110000とします. Aとkeyを用いて暗号文Bを計算してみると,


A XOR key = 01001101 XOR 11110000 = 10111101

つまり, B=10111101となりました. これで暗号化は完了です.


では, 復号化する場合はどのようにすれば良いでしょうか.




実は, B XOR keyを計算することによって, 平文Aを得ることができます.


B XOR key = 10111101 XOR 11110000 = 01001101

このように, 平文A=01001101を復元することができました.




以上のように, XOR演算を用いることで, 共通鍵暗号方式を実現することができます.

絶対に解読できない使い捨てパッド(ワンタイムパッド)

タイトルをみてびっくりされた方も多いのではないでしょうか. 暗号理論の世界では, 絶対に解読できない「使い捨てパッド(ワンタイムパッド)」というものが存在します.


使い捨てパッドとは, XOR演算を用いた暗号化方式です. 先ほどと同様のことを実行するので, そこまで複雑ではありません.

まず, "onetime"という平文Aを使い捨てパッドを用いて暗号化してみようと思います. まず, "onetime"という文字列をASCIIコードに直します.


A = 01101111 01101110 01100101 01110100 01101001 01101101 01100101

ここで, 使い捨てパッドの鍵keyを以下のように定義します.


key = 00011111 00001111 00001001 00010011 00000011 00001001 00010010

すると, 暗号文Bは以下のように計算できます.


B = A XOR key = 01110000 01100001 01101100 01100111 01101010 01100100 01110111

このBを文字列に直すと, "palgjdw"となります.


ではいま, 暗号文Bだけが与えられている状況を考えます. もちろん, keyやAは知りません.
このとき, 元の平文Aを得るためにはどのようなことをすれば良いでしょうか.


この前の記事でブルート・フォース・アタックについては説明しました. 今回もこの解読方法を使えば(かなり時間はかかりますが)復号できそうです. 試してみましょう.



例えば, key = 00011011 00000100 00010101 00010000 00000101 00010110 00010011として, B XOR keyを計算して, 平文Aを求めると,
A = 01101011 01100101 01111001 01110111 01101111 01110010 01100100 となり, これを文字列に直すと"keyword"という意味のある平文が得られました.

ということで, 今回ブルート・フォース・アタックが成功しました...




という風にはならないのです.

もともと平文Aはonetimeでしたよね. ですので今回の場合は復号失敗となってしまうのです.


使い捨てパッドは, ブルート・フォース・アタックによっていつかは元の平文Aを得ることができます. しかしいくら復号したとしても, どの場合が復号成功がわからないのです. なので, 使い捨てパッドは絶対に解読できないのです.


ピンと来ない方もいると思うので, もう少し説明しましょう.

先ほどの例で, key色々変えていくことによって, 7文字の文字列をたくさん生成することができます. 例えば, "morning", "evening", "goodbye"といった英単語を得ることができるし, "abcdefg", "fffffff"といった規則正しい文字列も得ることができます. これらは全て「意味のある文字列」の可能性があります. なので, 一意にこれといった復号化をすることが絶対にできないのです.


こういった意味で使い捨てパッドは理論的に解読不可能なわけです.

使い捨てパッドが使われない理由

では, 全ての暗号化方式に使い捨てパッドを利用すればいいではないかという疑問が生まれます.
実は, 使い捨てパッドには非常にデメリットが多いのです.


1. 鍵配送問題
共通鍵暗号方式には鍵配送問題はつきものです.
いくら暗号文から元の平文を絶対に復号できないとしても, 鍵自体がバレてしまったら元も子もないわけです. 鍵を安全に相手に送る方法が必要なわけです.

2. 鍵の保存問題
もし鍵をしっかり保存できるのであれば, もともと暗号化方式など必要ないですよね. だって平文も同じように管理すれば良いのですから.

3. 鍵の再利用
「使い捨て」とあるように, 使い捨てパッドは再利用できません. 再利用すると, 過去に行った通信内容がバレてしまいます.

他にも, 「鍵の同期」, 「鍵の生成」問題などがあります.

DES (Data Encryption Standard)

DESは, 世界中の政府や銀行などで広く用いられてきた共通鍵暗号方式です. しかし, 現在では使用されていません. ブルート・フォース・アタックで解読されてしまうためです.

DESの暗号化と復号化

f:id:tomonori4565:20180608222838j:plain
DESの全体像

DESは, 64ビットの平文を56ビットの鍵を用いて64ビットの暗号文に暗号化するアルゴリズムです. 復号化するときも同様で, 同じ鍵を利用して64ビットの平文に復号化します.

先ほど, 鍵は56ビットと言いましたが, 規格上は64ビットとなっています. これは, 誤り検出のビットが7ビットおきに入っているからです.


DESは, 64ビットの平文をまとめて暗号化します. このまとまりのことを「ブロック」と言います.
DESのように, ブロック単位で暗号化と復号化をする暗号アルゴリズムのことを「ブロック暗号」といいます.

平文が64ビット以上ある場合は, 平文をブロック単位に分割してそれぞれを暗号化することになります. この繰り返して暗号化する方法のことを「モード」と言います.

Feistel network(ファイステルネットワーク)とは

DESはファイステル構造という基本構造をなしています.

f:id:tomonori4565:20180608224804p:plain
ファイステル構造

ファイルテルネットワークでは, 暗号化のステップ(これをラウンドと言います)を何度も繰り返す仕組みを取っています. DESでは, ラウンドを16回繰り返すことになっています.


ここで, ファイステルネットワークについて解説していきたいと思います. 手順は以下の通りです.

ファイステルネットワークにおける暗号化

(1) 64ビットの入力を半分に分割し, 右と左に分ける.
それぞれ32ビットずつになります.

(2) 右をそのまま暗号文(右)に送る.
何も暗号化する必要はありません.

(3) 右をラウンド関数に送り, サブ鍵を用いて暗号処理をし, 出力する.
具体的には, 32ビットの右を48ビットに拡大し, サブ鍵とXORを取ります. この結果48ビットのXOR暗号文を8つのSボックス(それぞれ6ビット)に分割し, 6ビットを4ビットに縮小することによって32ビットの出力を計算します(これについては, また機会があるときに詳しく説明したいと思います).

(4) fの出力と平文の左のXORを取ることによって暗号文(左)を計算する.



この(1)から(4)の流れが1ラウンドとなります. これを16回繰り返すわけですが, このままだと右は暗号化されないことになってしまいます. これではまずいですね.

ですので, 2ラウンド目の入力は, 1ラウンド目の出力の左右を入れ替えたものを入力します. 同様に3ラウンド目の入力は, 2ラウンド目の出力の左右を入れ替えたものを入力し, 4ラウンド目の入力は, 3ラウンド目の出力の左右を入れ替えたものを入力します.

ファイステルネットワークにおける復号化

では復号化はどうやればいいのでしょうか.

実は, 暗号化と全く逆のことをしてやればOKです.


なぜこれで良いのかというのは, XORの性質を考えると当然ですね.

ファイステルネットワークの性質

(1) 好きなだけラウンド数を増やすことができる.

(2) ラウンド関数fにどんな関数を使っても復号化である.

(3) 暗号化と復号化が同じ構造で実現できる.


暗号技術入門 第3版

暗号技術入門 第3版

暗号技術のすべて

暗号技術のすべて