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

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

暗号理論 [番外編] ~ ElGamal暗号 ~

暗号理論

ElGamal暗号とは

ElGamal暗号とは, 1984年にエルガマルによって提案された暗号です. ElGamal暗号は, 離散対数問題の計算困難性を安全性の担保として利用している暗号化手法になります.

事前知識

別の記事で, Diffie-Hellman鍵共有プロトコルの話をしました. Diffie-Hellman鍵共有プロトコルも, 離散対数問題の計算困難性を利用したプロトコルであるので, 一度そちらの記事を読んでいただいた方がスムーズに理解できると思います.

tomonori4565.hatenablog.com

追加で, オイラーの定理というものを紹介します. a, mは互いに素である自然数とすると, 以下が成り立ちます.


a^{\varphi(m)} \equiv 1 \ \ (mod \ \ m)

ここで, \varphiとはオイラー関数というもので, \varphi(m)は mを超えない正の整数のうちで mと互いに素であるものの個数を指します. 例えば, \varphi(8) = 4となります(8と互いに素な正の整数は1,3,5,7の4つであるため).

ElGamal暗号の仕組み

鍵生成アルゴリズム

f:id:tomonori4565:20181016163057p:plain

(1) kビットのランダムな素数 pと原始元 g \ \ (1 < g < p)を選択する.
(2) 0 \leq x \leq p-2となる整数 xをランダムに選択する.
(3) y = g^x \ mod \ pを計算する.
(4) pk = (p, g, y)を公開鍵として公開し, sk = xを秘密鍵として保管する.

暗号化アルゴリズム

f:id:tomonori4565:20181016163112p:plain

平文 m \ (0 < m < p), 公開鍵 pkを入力とします.

(1) 0 \leq r \leq p-2となる整数 rをランダムに選択する.
(2) c_1 = g^r \ mod \ p \ とc_2 = my^r \ mod \ pを計算する.
(3) c = (c_1, c_2)を暗号文として出力する.

復号化アルゴリズム

f:id:tomonori4565:20181016163122p:plain

暗号文 c, 公開鍵 pk, 秘密鍵 skを入力とします.

(1) m' = c_2c_1^{p-1-x} \ mod \ p を計算して, m'を出力する.

ElGamal暗号の正当性

ElGamal暗号において, 正当性をチェックしてみましょう.


m'
= c_2c_1^{p-1-x} \ mod \ p
= my^r \cdot g^{r(p-1-x)} \ mod \ p
= mg^{rx} \cdot g^{r(p-1-x)} \ mod \ p
= mg^{r(p-1)} \ mod \ p
= m \cdot 1^r \ mod \ p \ (\because フェルマーの小定理より)
= m \ mod \ p

したがって, m' = mとなることがわかりました.

ElGamal暗号の安全性

盗聴者には pk, cが観測可能になります．しかし， y=g^x \ mod \ p \ (y,g,pは既知)から xを求めることは，離散対数問題の計算困難性から難しいとされています．したがって，秘密鍵が漏れない限りElGamal暗号は安全であると言われています．

暗号理論 [まとめ1] ～ (2)から(8)のまとめ ～

暗号理論

これまで紹介してきた記事は1つ1つが独立している訳ではなく，それぞれ関連があります．それを1度まとめてみましょう．

共通鍵暗号方式

共通鍵暗号方式とは，暗号化と復号に同じ鍵を使用する場合のことを指します．バーナム暗号やストリーム暗号は共通鍵暗号方式と言えます．

共通鍵暗号方式のメリットは，暗号化と復号をするのにかかる時間が短いことが挙げられます．

デメリットとして，鍵配送問題が生じることが挙げられます．

公開鍵暗号方式

公開鍵暗号方式は，暗号化と復号に異なる鍵を使用する場合のことを指します．RSA暗号は公開鍵暗号方式の代表的な1つです．

公開鍵暗号方式のメリットは，鍵配送問題が解決される点が挙げられます．

デメリットとしては，メッセージデータが大きい場合には暗号化と復号に時間がかかることと，man-in-the-middle攻撃に弱いことが挙げられます．

ハイブリッド暗号システム

ハイブリッド暗号システムは，メッセージの暗号化と復号には共通鍵を使用し，共通鍵を事前に共有するために公開鍵暗号方式を使用するというシステムのことを指します．

ハイブリッド暗号システムによって，共通鍵暗号方式と公開鍵暗号方式のデメリットを，お互いのメリットで補完することが可能になります．具体的には，共通鍵暗号方式のデメリットであった鍵配送問題が公開鍵暗号方式によって解決され，公開鍵暗号方式のデメリットであった暗号化と復号に時間がかかることが，共通鍵暗号方式によって解決できるようになります．

一方向ハッシュ関数

一方向ハッシュ関数は，あるメッセージが入力されたら，固定長ビットの出力値(ハッシュ値)を得ることができる関数です．

一方向ハッシュ関数の性質として，任意のデータに対してハッシュ値を得ることができる，同じデータに対しては同じハッシュ値を得ることができる，1ビットでも違うデータに対してはまったく違うハッシュ値が出力されることなどが挙げられます．

一方向ハッシュ関数を使用することでメッセージの改竄を検出することが出来ます．

しかし，一方向ハッシュ関数は「なりすまし」を検出することが出来ません．

メッセージ認証コード

メッセージ認証コードとは, 送信者と受信者間で共通鍵を共有し, データの送信者が計算したMAC値と, データの送信者が実際に計算したMAC値を確認することによって, なりすましとデータの改ざんを防ぐ仕組みのことを言います. メッセージ認証コードを使用することで, 一方向ハッシュ関数のデメリットであった「なりすましの検出が不可能であること」が解決されます.

しかし, メッセージ認証コードだけでは, 否認を防止したり第三者に証明することができません.

デジタル署名

デジタル署名とは, 送信者が送信データに署名をし, その送信データを送信者以外の人が検証できるシステムのことを指します. デジタル署名は公開鍵暗号方式の逆適用であり, 秘密鍵を使用して署名(暗号化)をし, 公開鍵を使用して検証(復号)することができます. デジタル署名によって, このデータはAさんが送ったものであるということを第三者に証明することができるので, 否認を防止することができます.

しかし, デジタル署名だけでは, 検証するにあたって公開鍵が本当に正しい相手のものなのか確認する手段がまだ確立されていません.

証明書

この公開鍵はAさんのものであると証明するものが証明書になります. この証明書のおかげで, 公開鍵が本当に正しい相手のものなのかを確認することができます.

まとめ

いかがでしょうか. 分からないことがあったら該当記事に戻っていただくか, コメントを頂けるとありがたいです.

暗号理論 [番外編] ~ Diffie-Hellman鍵共有プロトコル ~

暗号理論


共通鍵暗号方式において, 鍵共有問題は永遠のテーマでもあります. いかに安全に鍵を共有するかを議論することはとても大事なことなのです.

今回はDiffie-Hellman鍵共有プロトコルについて説明します. Diffie-Hellman鍵共有プロトコルを使用することで, 安全に鍵を配送することが可能になります.

これからDiffie-Hellman鍵共有プロトコルの仕組みを紹介していくのですが, 理解するにあたって「剰余計算(いわゆるmodの計算)」などの基本的な知識が必要となります. modの計算ができていることと, 初等整数論を理解しておくことで, 仕組みがスムーズにわかると思います. これから軽く説明したいと思います.

事前準備(初等整数論)

剰余計算

「 x \ \ mod \ \ y」とは, xをyで割ったときの余りを指します.

(例)

  • 5 mod 2 = 1
  • 10 mod 4 = 2
フェルマーの小定理

aを任意の整数, pを素数とする. 以下の公式を「フェルマーの小定理」といいます.


a^{p-1} \equiv 1 \ \ (mod \ \ p)

フェルマーの小定理は, aに関する数学的帰納法で証明できます.

位数, 原始元

フェルマーの小定理より, 「 a^{p-1} \equiv 1 \ \ (mod \ \ p) 」が成り立ちますが, 実際には, あるk (< p-1)に対して「 a^{k} \equiv 1 \ \ (mod \ \ p) 」が成り立つ場合もあります. 「 a^{k} \equiv 1 \ \ (mod \ \ p) 」が成り立つ最小のk( 1 \leq k \leq p-1)のことを, pを法とするaの位数（order）と言い,
「 order_p(a) = k」と書きます.

一方, 「 order_p(g) = p-1」を満たすgのことを, pの原始元（原始根・生成元）と言います.

(例)

  • 「 order_5(2) = 4」
  • 「 order_5(3) = 4」
  • 「 order_5(4) = 2」

したがって, 5の原始元は2, 3である.


Diffie-Hellman鍵共有プロトコルの仕組み

以下にDiffie-Hellman鍵共有プロトコルのアルゴリズムを紹介します. いつものごとく, AliceとBobがデータのやり取りをする場合を考えていきます.

(1) ランダムに大きな素数pを生成し, pの原始元g (1 < g < p)を選択して, pとgを公開します.
(2) Aliceは整数a( 1 \leq a \leq p-2)をランダムに選択し, A = g^a \ \ mod \ \ pを計算してBobに送信します.
(3) Bobは整数b( 1 \leq b \leq p-2)をランダムに選択し, B = g^b \ \ mod \ \ pを計算してAliceに送信します.
(4) Aliceは, B^a \ \ mod \ \ pを計算して出力します.
(5) Bobは, A^b \ \ mod \ \ pを計算して出力します.
(6) B^a \ \ mod \ \ pと A^b \ \ mod \ \ pは共に「 g^{ab} \ \ mod \ \ p」であり, これが鍵となる. したがってAliceとBobは鍵を共有することができます.


以下は(1)から(5)の流れです.


f:id:tomonori4565:20181011232240p:plain



Diffie-Hellman鍵共有プロトコルの安全性

Diffie-Hellman鍵共有プロトコルを攻撃する場合を考えてみましょう.
AliceとBobのやり取りを盗聴すると, 「 p」, 「 g」, 「 A」, 「 B」を取得することができます. しかし, AliceとBobがそれぞれ選択したa, bが攻撃者に漏れない限り, g^{ab} \ \ mod \ \ pを計算することは難しいのです.

このように, 「 g^{x} \ \ mod \ \ p」から xを簡単に計算するアルゴリズムは, いまだに発見されていません. これは, 有限体の上の「離散対数問題」と呼ばれています.


つまり, Diffie-Hellman鍵共有プロトコルの安全性は, 離散対数問題の計算困難性によって保たれていることになるわけです.

Diffie-Hellman鍵共有プロトコルに対する攻撃手法

Diffie-Hellman鍵共有プロトコルに対する攻撃手法の1つとして, man-in-the-middle攻撃が挙げられます.

例えば, 攻撃者Malloryが公開情報 p, gを取得し, 自分が選択した x, yを用いて g^{x} \ \ mod \ \ pと g^{y} \ \ mod \ \ pを作成します.
AliceがBobに g^{a} \ \ mod \ \ pを送信するとき, Malloryはこっそり g^{x} \ \ mod \ \ pとすり替えます. さらに, BobがAliceに g^{b} \ \ mod \ \ pを送信するとき, Malloryはこっそり g^{y} \ \ mod \ \ pとすり替えます. すると, Aliceの手元には g^{ay} \ \ mod \ \ p, Bobの手元には g^{bx} \ \ mod \ \ pが存在することになり, Malloryの手元には g^{ay} \ \ mod \ \ pと g^{bx} \ \ mod \ \ pの両方が存在することになります. したがって, MalloryはAliceに対してはBobに, Bobに対してはAliceになりすますことが可能になるのです.

この攻撃に対しては, デジタル署名や証明書などの対策が必要になってきます. これに関しては以下の記事を参考にしてください.

tomonori4565.hatenablog.com
tomonori4565.hatenablog.com

暗号理論(8) ~ 証明書 ~

暗号理論

暗号技術入門 第3版

暗号技術入門 第3版

暗号技術のすべて

暗号技術のすべて

証明書とは

前回では, デジタル署名について紹介しました. デジタル署名によって, なりすましやデータの改ざんを検出できたり, 送信データが正しい相手のものなのかを検証できるようになりました.

しかし, 受け取った公開鍵が本当に正しい相手のものなのかを検証する手段は依然として確立されていません. それを検証するために「(公開鍵)証明書」を使用します.

証明書を使用するまでの手順

証明書は信頼できる第三者機関が作成する必要があります. この第三者機関を「Trent」と命名しましょう.

例によってAliceがBobにメッセージを送信する場合を考えていきましょう.

(1) 公開鍵の登録
Bobはまず自分の公開鍵を認証局Trentに登録する必要があります. 登録する際には, 定められた「運用規定」にしたがって本人確認をする必要があります. 例えば, メールによる本人確認, 実際にBobが認証局を訪れて対面することによる本人確認などがあります.

(2) 証明書の作成
本人確認によりBobであることが確認できたら, TrentはBobの公開鍵にデジタル署名をします. もちろん, デジタル署名をする際にはTrent自身の秘密鍵が必要なので, あらかじめ用意しておきます(同時にTrentの公開鍵も用意しておきます). 証明書には, Bobの公開鍵とTrentによるデジタル署名が存在しています.

(3) 証明書の取得
AliceはBobに対してメッセージを送りたいので, Bobの公開鍵が必要になります. その際に, AliceはTrentから証明書を取得し, Trentの公開鍵で検証をします. 検証に成功すれば, 証明書に含まれているBobの公開鍵が正しいものであるとわかります.

このようにして, AliceはBobの正しい公開鍵を入手することができます.

公開鍵基盤(PKI)

公開鍵基盤(以下, PKI)とは, 公開鍵を効果的に使うために定められた規格や仕様の総称を指します.

PKIの構成要素は主に3つあります.

(1) 利用者
ここでいう利用者とは, 公開鍵を登録しようとしている人と, 公開鍵を利用しようとしている人の両方を指します.

(2) 認証局
認証局では, 証明書の管理を行います.

(3) リポジトリ
リポジトリとは, 証明書を保存し, PKIの利用者が証明書を入手できるようにしたデータベースのことを指します.

証明書に対する攻撃

証明書に対してもいくつかの攻撃手法が考えられます.

認証局へ登録する前に公開鍵を攻撃する

認証局に登録されてしまったら攻撃は難しくなるので, 登録する前にman-in-the-middle攻撃などを仕掛けることができます.
この攻撃を防ぐためには, Bobが公開鍵を認証局に登録する際に, 認証局の公開鍵を作成してBobの公開鍵を暗号化することが有効です.

攻撃者自身が認証局になる攻撃

認証局は信頼ある第三者機関によって営まれなければならないのですが, この認証局が悪意ある第三者であることを偽ることができれば, 攻撃者自身が認証局になりえます. こうすれば悪意ある攻撃がいくらでも可能になってしまいます.
こうなることを防ぐには, 信頼できない認証局は使用しないことが大切です.

暗号理論(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-1やMD5のようなハッシュ関数を使って実現することができます. ここでは, 代表的な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と勝利数の関係, 奪三振率と防御率の関係などをグラフ化していきたいなと思っております. 

 

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