namdicul's blog

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

暗号理論 [番外編] ~ 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