公開鍵 概説

Takami Torao #DLP #DH #ElGamal #ECDH #RSA #RSA-FDH #DSA
  • このエントリーをはてなブックマークに追加

概要

公開鍵アルゴリズムは秘密鍵と公開鍵のペアを利用した暗号アルゴリズム。安全でない通信チャンネルを用いて参加者の間で安全な暗号化通信を行うための基本的な部品として使用することができる。公開鍵アルゴリズムを応用した技術として鍵交換、暗号、電子署名が広く使われている。

依拠 鍵交換 公開鍵暗号 電子署名
ペアリング
楕円曲線 ECDH 鍵交換 楕円曲線暗号 ECDSA 署名, ed25519署名
有限体 DH 鍵交換 ElGamal 暗号 ElGamal 署名, DSA 署名
素因数分解 RSA 暗号 RSA 署名

離散対数問題を利用している Diffie-Hellman や ElGamal のアルゴリズムは、同じ離散対数問題を利用する楕円曲線を用いたアルゴリズムに比較的容易に置き換えることができる。

離散対数

冪余剰

被除数 \(a\)、除数 \(m \gt 0\) をそれぞれ整数とし、\(0 \le r \lt m\) の下で \(a = qm + r\) となるような整数 \(q, r\) をそれぞれ商、剰余と呼ぶ。剰余 \(r\) はいわば \(a\) を \(m\) で割った余りであり \(r = a \bmod m\) と表す (\(a\) が負値であっても \(0 \le r \lt m\) の範囲とする点に注意)。また、\(m\) に対する \(a\) と \(b\) の剰余が等しいとき \(a \equiv b \pmod{m}\) と表す。

剰余に対する加法・乗法の剰余は、その被除数に対する同じ演算の剰余と等しい。つまり: \[ \begin{eqnarray*} ((a \bmod m) + (b \bmod m)) \bmod m & = & (a + b) \bmod m \nonumber \\ ((a \bmod m) \times (b \bmod m)) \bmod m & = & (a \times b) \bmod m \end{eqnarray*} \] 加法・乗法が可能な集合は(かん)である。従って剰余の集合 \(\{0,\ldots,m-1\}\) を 剰余環と呼び \(\mathbb{Z}/m\mathbb{Z}\) (または \(\mathbb{Z}_m\)) と表す。剰余環のサイズは \(|\mathbb{Z}/m\mathbb{Z}|=m\) である。

剰余環は乗算を繰り返すことでべき乗を計算することができる。ここで \(2^a \bmod m\) について考えると、まず \(a=0\) の時に 1 であり、\(a\) が増加するにつれ \(a=m-1\) で再び 1 となり、以後 \(2(m-1), 3(m-1), \ldots\) のたびに 1 となることを繰り返すことが分かる。つまり \(m-1\) ごとに同じ値を繰り返すことから以下の式が成り立つ。\[ 2^a = 2^{q(m-1)+r} = 2^{q(m-1)} \times 2^r \equiv 2^r \pmod{m} \]

例えば \(2^{16}\) は \(2^{2 \times 6 + 4} \equiv 2^4 \pmod{7}\)、つまり \(2^{16} \bmod 7 = 2^4 \bmod 7 = 2\) である。これは \(2^{16}\) を計算して剰余を求めるよりも遙かに容易に答えを導くことができる。

\(g^a \bmod p\) のような計算式は冪余剰 (modular exponentiation) と呼ばれ、巨大な数であっても効率的に計算することができる。\(g\) を大きくする必要はなく、一般には小さな整数 \(2, 3, \ldots\) である。

計算量と多項式時間

手動での計算ステップを踏まえて算法の計算量を考える。\(a\) と \(b\) を 2 進数で展開される自然数とし、それぞれの 2 進長さを \(m_a\), \(m_b\) とする。単一ビットの和を \(O(1)\) としたとき:

  • 加法: \(O(\max(m_a, m_b))\)
  • 乗法: \(O(m_a m_b)\)
  • 除法: \(a \div b\) で商 \(q\) と剰余を求めるとき \(O(m_b q)\)

あるアルゴリズムに整数 \(z_1, \ldots, z_n\) を入力したときの実行時間が \(O(m_{z_1}^{e_1}m_{z_2}^{e_2}\ldots m_{z_n}^{e_n})\) で表される場合、そのアルゴリズムは多項式時間 (polynomial time) であると言い、そのアルゴリズムは 効率的であると認識されている。現実的な計算上は \(O\) の係数と指数 \(e_i\) が小さい場合に実用面で効率的といえる。ここで \(e_i\) は負でない整数を表している。

離散対数問題

剰余環でべき乗の剰余を求めることが容易であるのに対して、何乗したら目的の値となるかを求めるのは困難であることが知られている。\(g\), \(p\), \(g^a \bmod p\) が与えられたときに \(a\) を求めることを離散対数問題 (DLP; discrete logarithm problem) と呼ぶ。

一般に以下の条件を満たす DLP を現在のコンピュータで解くのは現実的ではないと考えられている。

  1. \(p\) が 1024 ビット以上の素数であり、\(p-1\) の約数の中に \(p\) に近いサイズの素数 \(q\) が存在する。
  2. \(i=1,\ldots,q-1\) に対して \(g\) は \(g^i \not\equiv 1 \bmod p\) となる値である。

\((p,q,g)\) の組を DH パラメータや DH 群などと呼ぶ。

Diffie-Hellman 鍵共有

Diffie-Hellman 鍵共有 (DH key exchange) は end-to-end で鍵を交換するアルゴリズム。剰余のべき乗計算は容易だが離散対数問題 (DLP) は困難であるという非対称性を利用して1 A と B の間で秘密の鍵を共有する。

この DH 鍵共有のアルゴリズムはしばしば Fig 1 のようなインクの混ぜ合わせによって双方で共通の色を作る操作で説明されている。

  1. 整数 \(p, g\) を 2 者間で取り決める (これらは平文で公開されていても良い)。
  2. A: 秘密鍵 \(S_a\) を決め、公開鍵 \(P_a = g^{S_a} \bmod p\) を計算して B に渡す。
  3. B: 秘密鍵 \(S_b\) を決め、公開鍵 \(P_b = g^{S_b} \bmod p\) を計算して A に渡す。
  4. A: 秘密鍵 \(S_a\) と B の公開鍵 \(P_b\) を使って \(P_b^{S_a} = (g^{S_b})^{S_a} \bmod p\) を計算する。
  5. B: 秘密鍵 \(S_b\) と A の公開鍵 \(P_a\) を使って \(P_a^{S_b} = (g^{S_a})^{S_b} \bmod p\) を計算する。
  6. A と B は \(g^{S_a S_b} \bmod p\) という共通の値を共有した。
Fig 1. インクの色の混ぜ合わせによる DH 鍵共有の説明

\(p, g\) を知っている攻撃者が A の公開鍵 \(P_a\) を盗聴したとしても DLP により秘密鍵 \(S_a\) を算出することは困難である。従って \(P_a\) と \(P_b\) を盗聴できても共通の値 \(g^{S_a S_b}\) を算出することはできず \(g^{S_a S_b}\) は A と B のみが知り得る情報である。

\(g\), \(p\), \(g^a \bmod p\), \(g^b \bmod p\) が与えられたとき \(g^{ab} \bmod p\) を求めることを DH 問題 (Diffie-Hellman problem) と呼び、DH 問題が現実的なコンピュータの計算能力で解くことが困難であるという仮定CDH 仮定 (computational Diffie-Hellman assumption) と呼ぶ。したがってより正確には "攻撃者は CDH 仮定の下で \(g^{S_a S_b}\) を得ることが困難である" と言える。

一般に DH 鍵共有ではセキュリティを確保するためにモジュラス \(p\) は少なくとも 2048 ビット長であることが推奨されるが、ベース \(g\) は小さな値でもよい。

DH 鍵共有は攻撃者の盗聴に対しては耐性を持つが、通信相手の身元を検証できない場合に中間者攻撃が可能となり安全ではない。このような Anonymous Diffie-Hellman は使用してはならず、通常は証明書付きの公開鍵を使用して通信相手の身元を検証できるようにしなければならない。

ElGamal 暗号

ElGamal 暗号は 1984 年に考案された CDH 仮定に基づいた公開鍵暗号方式。公開鍵で暗号化した暗号文は秘密鍵でしか復号化できず、同じ平文に対して毎回異なる暗号文が生成される。

鍵生成

大きな素数 \(p\) と原始根 \(g \bmod p\) を選択して暗号スキームのパラメータとして公開する。ランダムに \(a \in \{0, \ldots, p-2\}\) を選択して秘密鍵とし、\(A = g^a \bmod p\) を公開鍵とする。

暗号化

平文 \(m\) の暗号化を考える。まずランダムに \(b \in \{0,\ldots,p-2\}\) を選択し、暗号スキームのパラメータ \(p\), \(g\) を使って \(B = g^b \bmod p\) を計算する。次に公開鍵 \(A\) から \(C = m A^b \bmod p = m g^{ab} \bmod p\) を計算し \((B,C)\) を暗号文とする。

復号化

秘密鍵 \(a\) と暗号文 \((B,C)\) より、以下のように \(p\), \(g\), \(a\), \(b\) を打ち消すことで下の平文 \(m\) を復号化することができる。\[ \begin{equation} \frac{C}{B^a} = \frac{m A^g \bmod p}{(g^b)^a \bmod p} = \frac{m g^{ab} \bmod p}{g^{ab} \bmod p} = m \label{decrypt} \end{equation} \]

CDH 仮定より暗号文 \((B,C)\) から \(a\), \(b\), \(m\) を推測することは困難であり、また \(b\) のランダム性により同一の \(m\) であっても生成される暗号文は毎回違うものとなる。ただし式 (\(\ref{decrypt}\)) より、暗号文 \((B,C)\) を得た中間者が \((B,nC)\) にすり替えた場合、復号者は \(m\) ではなく \(nm\) を "正しく" 得ることとなる。つまり、ElGamal 暗号は中間者から通信内容を秘匿するが内容を操作することが可能であり頑強性や非展開性が欠落している。

DSA 署名

DSA (digigal sigunature algorithm) は ElGamal 署名の改良版として開発され 1993 年に標準化された電子署名アルゴリズム。RSA 署名より

鍵生成
ハッシュ関数 \(H\) と DH パラメータとなる大きな素数 \(p\)、およびハッシュ関数の出力と同じサイズの \(q\) を取り決める。生成元の \(g\) は \(g^q \equiv 1 \bmod p\) であり、\(p-1\) は \(q\) で割り切れるとする。\(0 \lt x \lt q\) となる秘密鍵 \(x\) をランダムに選択し、公開鍵を \(y = g^x \bmod p\) とする。
署名
整数 \(k\) をランダムに選択する。メッセージ \(m\) に対して署名 \((r,s)\) を以下のように算出する (\(r=0\) または \(s=0\) の場合は \(k\) を再選択する)。\[ \begin{eqnarray*} r & = & (g^k \bmod p) \bmod q \\ s & = & \frac{H(m)+xr}{k} \bmod q \end{eqnarray*} \]
検証
\(0 \lt r \lt q\), \(0 \lt s \lt q\) でなければ署名は無効。\[ \begin{eqnarray*} w & = & \frac{1}{s} \bmod q = \frac{k}{H(m)+xr} \bmod q \\ u_1 & = & w H(m) \bmod q \\ u_2 & = & rw \bmod q \\ v & = & (g^{u_1} y^{u_2} \bmod p) \bmod q \end{eqnarray*} \] を算出し、\(g^{u_1} y^{u_2} = g^{wH(m)} g^{wrx} = g^{w(H(m)+xr)} = g^k\) より \(v = (g^k \bmod p) \bmod q = r\) が成り立つことから \(v = r\) であれば署名は有効である。

RSA 暗号

RSA 公開鍵暗号 (RSA public-key encryption) は大きな数の素因数分解の困難性を利用した公開鍵暗号。最初の実用的な公開鍵暗号で 2000 年に特許が切れている。より鍵の小さい楕円曲線暗号に置き換えられつつあるが現在においても広く利用されている。

RSA 暗号のアルゴリズムは以下の定理に基づいている。

定理. \((n,e)\) を公開鍵、\(d\) をそれに対応する秘密鍵としたとき、任意の整数 \(0 \le m \lt n\) に対して以下の式が成り立つ (\(e\), \(p\), \(n\) の定義は鍵生成参照)。\[ \begin{equation} (m^e)^d \bmod n = m \label{theorem} \end{equation} \]

Proof. \(ed \equiv 1 \pmod{(p-1)(q-1)}\) より、\(ed = l (p-1)(q-1) + 1\) となる整数 \(l\) が存在する。よって \[ (m^e)^d = m^{ed} = m^{(p-1)(q-1)+1} = m(m^{(p-1)(q-1)})^l \] と表すことができる。ここでフェルマーの小定理「\(p\) を素数とし \(a\) を \(p\) の倍数でない整数とするとき \(a^{p-1} \equiv 1 \pmod{p}\) となる」より。\[ \begin{eqnarray*} (m^e)^d & = & m(m^{(p-1)})^{l(q-1)} \equiv m \pmod{p} \\ & = & m(m^{(q-1)})^{l(p-1)} \equiv m \pmod{q} \end{eqnarray*} \] \(0 \le m \lt n\) であり、\(p\) と \(q\) は互いに異なる素数であることから定理 (\(\ref{theorem}\)) が成り立つ。

以下に RSA 暗号の鍵生成、暗号化、復号化の手順を示す。

鍵生成

公開鍵 \((n,e)\) と秘密鍵 \(d\) を以下のように求める。

  1. ランダムに 2 つの素数 \(p\) と \(q\) を選択し、それらの積 \(n=pq\) を計算する。
  2. \(1 \lt e \le \varphi(n)\) かつ \(\gcd(e, (p-1)(q-1))=1\) となる自然数 \(e\) を選択する。
  3. \(1 \lt d \lt (p-1)(q-1)\) かつ \(de \equiv 1 \pmod{(p-1)(q-1)}\) となる自然数 \(d\) を選択する。

\(n\) を RSA モジュラス (RSA-modulus)、\(e\) を暗号化指数 (encryption exponent)、\(d\) を復号化指数 (decryption exponent) と呼ぶ。\(e\) は常に奇数である。

暗号化

公開鍵 \((n,e)\) を使用して平文 \(0 \le m \lt n\) を \(c = m^e \bmod n\) で暗号化する。この計算には拘束指数計算法を使用することができる。

バイト配列やアルファベットのような \(N\) 種類の集合 \(\{0,\ldots,N-1\}\) の任意の列にブロック暗号のように使用するには、それらを基数 \(N\) の数値表現と見なし、\(n\) より小さくなるブロックに分割した単位で暗号化を行う (端数は CBC のようなパディングを使用する)。対象とするメッセージは \(0 \le m \le N^k-1 \lt n\) となることから、ブロックの単位となる桁数 \(k\) は \(n\) を基数 \(N\) で表現したときの桁数となり \(k=\lfloor \log_N n \rfloor\) で表すことができる。これより \(m = \sum_{i=1}^k m_i N^{k-i}\) となり求めた暗号値 \(c = m^e \bmod n\) を再び \(N\) 進数で表した \(c = \sum_{i=1}^k c_i N^{k-i}\) となるような \(c_i\) の並びが暗号値の表現となる。

復号化
暗号文 \(c=m^e \bmod n\) より、秘密鍵 \(d\) を使用して \[ c^d \bmod n = (m^e \bmod n)^d \bmod n = (m^e)^d \bmod n = m \] を計算して平文 \(m\) を得る。

RSA-FDH 署名

FDH (full-domain hash) とはハッシュ値が公開鍵と同じ長さとなるハッシュ関数のこと。RSA-FDH 署名は RSA 暗号と FDH 関数を使用して署名を生成する。この署名は RSA 仮定と \(H\) のランダムオラクルモデルの下で安全である。

鍵生成
RSA 暗号と同様に秘密鍵 \(d\)、公開鍵 \((n,e)\) を作成する。また full-domain ハッシュ関数を \(H\) とする。
署名
メッセージ \(m\) のハッシュ値 \(H(m)\) に対して秘密鍵 \(d\) を使った署名 \(s = H(m)^d \bmod n\) を算出する。
検証
署名 \(s\) に対して \(H(m) \equiv s^e \pmod{n}\) が成り立てば署名が正しいことが検証できる。

RSA-FDH 署名は簡単だが \(n\) が大きくなるに伴ってハッシュ値も大きくなるためあまり計算効率は良くない。より効率的な署名アルゴリズムに RSA-PSS 署名 (probabilistic signature scheme) がある。

参考文献

  1. 辻井重男, 笠原正雄, 有田正剛, 境隆一, 只木孝太郎, 趙晋輝, 松尾和人, "暗号理論と楕円曲線", 森北出版 (2008)
  2. J.A. ブーフマン, "暗号理論入門 原書第3版, 丸善出版 (2012)
  3. 光成滋生, "クラウドを支えるこれからの暗号技術", 秀和システム (2015)