Diffie-Hellman鍵共有について

以下の書籍3章前半のまとめです。

クラウドを支えるこれからの暗号技術

作者:光成滋生
出版社/メーカー: 秀和システム
発売日: 2015/06/24
メディア: 単行本

1. 公開鍵暗号

前回、共通鍵暗号の課題点は「秘密鍵を安全に共有できなさそう」という点でした。どれだけ安全な共通鍵暗号であろうとも秘密鍵が盗聴されてしまえば、簡単に攻撃されてしまいます。

そこで盗聴者がいたとしても、暗号を共有するものの間でのみ（複合に必要な）何らかの値を共有できるようにする手段が必要です。それを公開鍵暗号と呼び、現在では主流の暗号方式になっています。

2. Diffie-Hellman 鍵共有

「安全に」値を共有する方法の１つであるDiffie-Hellman（DH）鍵共有について解説します。

まず公開鍵暗号を考える際に念頭に置きたいのが、演算の"一方向性" です。ここでいう "一方向性" とは、Aが与えられた時にBを求めるのは計算量的にカンタンだが、逆にBを与えられた時にAを求めるのは難しい、というような性質のことを指しています。これは、例え攻撃者に盗聴されていたとしても、計算量を盾に「安全である」と決定づけるために必要となる重要な性質です。

DH鍵共有の場合は、 mod を用いた演算に潜む"一方向性" を利用することで安全な鍵共有を実現しています。

2.1. DH鍵共有のアルゴリズム

まずはDH鍵共有のアルゴリズムを見てみましょう。ここで暗号を共有する両者を仮にAとBとし、それぞれが決めた秘密鍵を $a, b$ とするとします。

以下の条件を満たす整数 $g, p$ を平文で共有する。
$p$ の条件: 1024ビット以上の整数であり、かつ $\displaystyle q = (p-1)/2$ も素数となること
$g$ の条件: $i, \dots , q-1$ に対して $g^i \not\equiv 1\mod p$ を満たすこと
Aは $K_A := g^a \mod p$ を求めBに共有する
Bは $K_B := g^b \mod p$ を求めAに共有する
Aは $K_B^a \mod p = g^{ba} \mod p$ を求める
Bは $K_A^b \mod p = g^{ab} \mod p$ を求める

上記がDH鍵共有のアルゴリズムです。

2.2. 手計算

これだけではわかりづらいので具体的な値を入れて $g^{ab} \mod p$ を求めてみます。ここでは $g^{ab} \mod p$ の値を求める部分に焦点をおくため $p$ の条件である、「1024ビット以上」という部分は無視するとします。

それぞれ以下のように定めます。

$p=23, g=2, a = 5, b=3$

すると、以下のように $K_A$ と $K_B$ を求められます。

$K_A = 2^5\mod 23 = 32 \mod 23 \equiv 9 (\mod 23)$

$K_B = 2^3\mod 23 = 8 \mod 23 \equiv 8 (\mod 23)$

そしてこの $K_A, K_B$ が共有され、AとBはそれぞれのもつ秘密鍵を用いて $g^{ab} \mod p$ を求めます。

$K_B^a \mod p = 8^5 \mod 23 = 32768 \mod 23 \equiv 16 (\mod 23)$

$K_A^b \mod p = 9^3 \mod 23 = 729 \mod 23 \equiv 16 (\mod 23)$

以上の通り、 $g^{ab} \mod 23 = 16$ という値をAとBで共有できたことがわかります。

2.3. 軽いまとめ

公開される値は $K_A, K_B, g, p$ の4つです。逆にAとBのそれぞれしか知り得ない秘密鍵が $a, b$ の2つです。鍵共有によって、AとBは $g^{ab} \mod p$ の値を安全に共有することができるわけですが、これは公開されている値 ( $K_A, K_B, g, p$ ) からでは $a, b$ を求めることが「計算量的に」難しいという前提のもと成り立っています。