離散対数問題について更に詳しく調べてみた

作成日: 2020/11/04(水)

更新日: 2021/06/20(日)

ハローワールド。

予め断っておくと、筆者はここらへんの数学を専攻していたわけでもなんでも無いので、理論に穴だらけの可能性があります。

また、私がそうなので、数学についてほとんど知らない人でもある程度理解できる内容になっています。そのつもりです。

DH法の安全性

DH法やDSAでは離散対数問題を基として、鍵交換やデジタル署名しています。
特にDH法やDSAは剰余群（剰余環）での計算の非対称性を利用しています。

DH法では公開鍵 $P$ は秘密鍵 $S$ より下記の式で導くことが出来ました。
この時 $g$ は任意の自然数、 $p$ は十分大きな素数です。具体的な値は筆者によるDH法をまとめた記事を参照ください。

\begin{aligned} P &= g ^ S \bmod p \end{aligned}

累乗の余りの計算

この $g^S$ というのはしばしば累乗、 $\bmod p$ は剰余と呼ばれます。更には、この $a \bmod b$ という式のことを「合同式」と呼んだりもするらしいです。

剰余には $(a \times b) \bmod c = ((a \bmod c) \times (b \bmod c)) \bmod c$ という性質があります。累乗でも同じようにできるため、 $g^S$ を求めてから $p$ との剰余を計算するよりかは大きな数を扱わなくて良くなる分簡単に値を求めることが出来ます。

累乗はバイナリ法と呼ばれるアルゴリズムで計算回数を抑えて計算が可能です。具体的なアルゴリズムはここでは省略するので、将来の私が書くのをまつか、グーグルで検索すると良いです。
またバイナリ法の処理で都度剰余をとってあげることで高速に累乗における余りの演算が可能です。
このバイナリ法ですが、ここでは $S$ の数、特に $S$ を2進数に直した際、1の数だけ追加で計算が発生します。1の数だけ追加で処理が走り、処理時間が変化するということは、つまりサイドチャネル攻撃^[1]に対して脆弱になってしまいます。

サイドチャネル攻撃に強いとされるアルゴリズムでは「モンゴメリ累乗余演算」と呼ばれるものがあります。「モンゴメリ乗算」または「モンゴメリ法」は巨大な数における除算を加算、減算、乗算、ビット演算のみで行う方法で、多倍長整数演算などでよく用いられるものです。
このモンゴメリ累乗余計算はバイナリ法より計算数は多くなりますが、それでも高速に求められサイドチャネル攻撃に強い攻撃です。

離散対数の計算

累乗余、つまり $P = g^S \bmod p$ の計算は高速にできるアルゴリズムがあります。
しかし、 $g, P, p$ の値がわかっているときに秘密鍵 $S$ を求めるのはどうでしょうか。

まずはpを法とする世界^[2]から離れ、 $P = g^S$ から $S$ を求めます。
これは対数で簡単に求められますね。つまり $S = \log_g P$ を求めればいいのです。とくに $P, g, S$ が全て整数である事が分かっているので、 $g$ が2の場合は $P$ を2進数に直して桁数を数えてあげれば良くて、 $g$ が任意の値でも $\log_g P = \log_2 P / \log_2 g$ という対数の性質（底の変換公式）を使えば簡単に求められます。おそらく。

しかしpを法とする世界に来ると途端に難しくなります。すなわち $P = g^S \bmod p$ となる $S$ を $P, g, p$ から計算する効率的なアルゴリズムは見つかっていません。嘘です、量子アルゴリズムの世界なら見つかってます。ipaがアルゴリズムを記載しています。私には1mmも理解できませんでした。

この時、効率的なアルゴリズム、というのは「多項式時間」で解けることを指します。対義語は「指数関数時間」です。多項式時間は要素数 $n$ に対して $\mathcal{O}(n^C)$ （ここで $C$ は定数）で解けることを指し、指数関数時間は $\mathcal{O}(C^n)$ で解けることを指します^[3]。

量子コンピューターは近年話題に尽きませんが、未だ現実的に解を得ることは出来ていません。そのため、DH法やDSAは累乗余を求めるのと離散対数を求めるのとの計算の非対称性さを基として暗号の強さを担保しています。

離散対数問題…の前に群

離散対数問題にちゃんと取り組む前に群について復習しておきます。DH法だけを学ぶためにはあまり必要はないかもしれませんが。

群。ここからはずいぶん数学チックとなります。このあたりは高専で少し学んだかな…という感じですね。

これらは数学の基礎の基礎となる概念とも言えるでしょう。基本的に実数とか行列とかなんとかとか色々の中から共通となるものを抜き出したもの、みたいな雰囲気でしょうか。

ここからは必要な部分だけピックアップしていくので殆どを網羅していないことに注意してください。

集合

群を学ぶ前に集合についておさらいです。

集合はものの集まりのことで、集合を構成するもののことを「要素」または「元」と呼びます。集合については下記の記号を用いて表現されます。

A \in x \text{または} x \ni A

特にDH法やDSA、RSA全体では整数全体の集合である $\mathbb{Z}$ を用いる場合が多いです。

\mathbb{Z} = \{\ldots, -3, -2, -1, 0, 1, 2, 3, \ldots\}

$\{\}$ で囲うことでも集合を表すことができます。

また、ある性質で集合を表現するときは下記のようになります。

A = \{ x \in E | P(x)\}

例えば偶数 $E$ の集合は下記のように表現できます。

E = \{ x \in \mathbb{Z} | x \bmod 2 = 0\} \\ E = \{x | x \bmod 2 = 0, x \in \mathbb{Z}\}

ちなみに集合では必ず $\forall$ や $\exists$ という記号が用いられます。それぞれ「すべての」「ある特定の」みたいなニュアンスの記号ですが、なんとなく顔文字っぽく見えるので本記事では利用しません。

部分集合

これは直感的に分かる話で、ある集合 $A$ と $B$ において集合 $B$ の任意の要素 $b$ がすべて $A$ の要素に属していた場合、 $B$ は $A$ の部分集合と呼びます。

またこのとき $A \supset B$ または $B \subset A$ と記載します。

例えば、自然数の集合 $\mathbb{N} = \{1, 2, 3, 4, \ldots \}$ の要素はすべて整数の集合 $\mathbb{Z}$ に含まれています。そのため $\mathbb{N}$ は $\mathbb{Z}$ の部分集合と呼べます。なので $\mathbb{N} \subset \mathbb{Z}$ ですね。

写像

ある集合 $A$ の要素 $a$ を別の集合 $B$ の要素 $b$ と一対一で対応させるような規則 $f$ を集合 $A$ から集合 $B$ への写像と呼びます。記号で表すと下記の様な書き方があるようです。

f: A \longrightarrow B \\ A \stackrel{f}{\longrightarrow}B \\ a \longmapsto b = f(a)

特に $A = B$ をAの変換と呼びます。例えば $\mathbb{Z}$ に対して $f(a) = -a$ とすると1は-1へ、-2は2へなるので最終的な集合は $\mathbb{Z}$ と同じになりますね。
この写像、実数の世界では関数と呼ばれることが多いですね。集合や群などは実数の世界以外へも広がるためかなり抽象的な見た目をしていますが、基本的には関数と同じものです。

$f: A \longrightarrow B$ であるとき、 $A$ の要素 $a$ が $B$ の要素 $b$ に対応するとき、 $b$ を $f$ による $a$ の像と呼びます。このとき $B$ すべての要素に紐づく必要はありませんし、 $A$ の要素 $a_1, a_2$ に対する $f(a_1), f(a_2)$ が同じ値になる可能性もあります。

直積集合

集合 $A$ と集合 $B$ のそれぞれの元、 $a, b$ をそれぞれ対にしたものを順序対 $(a, b)$ と呼びます。 $a$ を第1成分、 $b$ を第2成分とし、 $(a, b) = (c, d)$ となるには $a = c, b = d$ であると定義します。

この順序対 $(a, b)$ の全体の集合を $A$ と $B$ の直積集合と呼び、下記の式で表します。

A \times B = \{(a, b) | a \in A, b \in B\}

群

集合や写像には上記の他にも色々覚えるべきことはありますが、とりあえず「群」を学ぶためには上記だけで十分です。これ以上記載しても書いてる僕が眠くなるだけですからね。

では群の定義について見てみましょう。

群の定義

集合 $G$ の直積集合 $G \times G$ からGへの写像が1つ与えられているとする（ $G \times G \longrightarrow G$ ）。この写像を $G$ の2項演算と呼ぶ。 $G \times G$ の元 $(a, b)$ のこの写像による像を $a$ と $b$ の積と呼び、記号 $a \circ b$ または $ab$ を表す。このとき、集合 $G$ に1つの2項演算（単純に演算と呼ぶこともある）が与えられると呼び、 $(G, \circ)$ と表す。

ちなみに演算が明らかである場合は単に $G$ と記載される場合があります。

集合 $G$ に1つの演算が与えられていて、次の条件を満たす場合、 $G$ はこの演算に関して群をなす、または群であるという。
1. 結合律： $G$ の中の任意の元 $a, b, c$ に対して常に $(a\circ b) \circ c = a \circ (b \circ c)$ が成立する。
2. 単位元： $G$ の中の任意の元 $a$ に対して $a \circ e = e \circ a = a$ を満たす特別な元 $e$ が存在する。この時aは可逆であると呼ぶ。
3. 逆元： $G$ の中の任意の元 $a$ に対して $a \circ b = b \circ a = e$ を満たす $b$ が存在する。

3.の逆元の存在ですが、この逆元 $b$ は $a$ が決まれば一位に決まります。またこの逆元を $a^{-1}$ と表記します。

ちなみに、1だけを満たす集合を「半群」、1と2を満たす集合を「モノイド」と呼びます。なんかH(askell)な気持ちになりますね。自然数の積は1を単位元としたモノイドです。

これに加えて「交換法則： $G$ の中の任意の元 $a, b$ に対して $a \circ b = b \circ a$ を満たす」が成り立つ場合は、アーベル群（可換群）と呼びます。しばしば加法群と呼ばれてします。

巡回群

任意の群 $G$ のある要素 $a$ を選択します。その $a$ と演算 $\circ$ のみで生成される群を巡回群と呼びます。…なにそれ。

すなわち

C = \{ \ldots, a ^ {-3}, a^ {-2}, a ^ {-1}, a^{0} = e, a, a^2, a^3, \ldots \}

ということです。

例えば $a^3 = a \circ a \circ a$ であり、 $a^{-2} =(a \circ a)^{-1} = a^{-1} \circ a^{-1}$ となります。

ちなみにこの要素 $a$ のことを生成元と呼びます。

例えば群 $(\mathbb{Z}(\text{整数}), +)$ は要素1を生成元とした巡回群です。 $a^3 = 1 + 1 + 1 = 3$ （ここで $a^3$ は3回「かける」ではなく3回「演算、つまり $+$ をすること」になることに注意）ですし、 $a^{-2} = 1^{-1} + 1^{-1} = -1 + -1 = -2$ となり、無限に繰り返すことで整数となりますね。

ちなみに無限に続くときは無限巡回群、有限の場合は有限巡回群と呼ばれます。

位数 vs 位数

巡回群から少しだけ離れて、位数について。群の中には2つの異なる「位数」が存在します。実際には「群の位数」と「元の位数」ですが。

「群の位数」は群の要素の数です。
「元の位数」はその元を何回演算することで単位元になるか、の「何回」の回数です。

ここで、生成元を複素数 $i$ とし、演算を「 $\times$ 」つまり「かける」とした巡回群 $C$ を考えてみましょう。こうなりますね。

C = \{i, -1, -i, 1\}

単位元は「1」であることは自明かと思います。

このとき「群の位数」は4です。要素数は4つなので。
次に元の位数ですがこれは元によって異なります。 $i$ の場合はiを4回演算することで単位元の1になります。-1では2回、-iでは3回なのでそれぞれ2, 3が元の位数となります。単位元の場合は演算をする必要がないので0です。

生成元の位数 = 郡の位数となりますので、もしかしたら位数自体はあまり区別されるものではないかもしれません。

ちなみに無限巡回群では位数は「無限」です。

準同型写像

今度は写像に戻ります。

準同型写像（じゅんどうけいしゃぞう）はある群 $(G, \circ)$ の任意の元 $a, b$ に対して下記を満たす写像 $f : G \longrightarrow G'$ のことです。

f(a\circ b) = f(a)\circ f(b) \\

単射・全射・同型写像

じゃあ同型写像もあるのかと思いますが、当然存在します（言葉的にね？）。

その前に準同型写像の中で更に2つの性質で分けて考えます。下記では群 $G, G'$ と準同型写像 $f: G \longrightarrow G'$ を暗に利用します。

1つは単射です。これは $f$ が必ず一位の $G'$ の元に紐づくことです。すなわち $G$ と $G'$ を一対一で対応させる写像です。これは $G'$ の元の中には紐付かない元があっても問題ありません。すなわち $G$ の位数 $\leqq$ $G'$ の位数となります。

次に全射です。これは $G$ を射影した結果 $G'$ となるものです。これは $G'$ のある元に2つ以上対応する $G$ の元があっても問題ありません。すなわち $G$ の位数 $\geqq$ $G'$ の位数となります。

同型写像は上の2つをミックスしたものです。全単射とも呼ばれます。すなわち $G$ と $G'$ の要素が一対一でひも付き、要素に過不足がない状態です。

同型写像は $G$ の元から $G'$ の元に一対一でかつ過不足無く紐づく為、 $G'$ から $G$ を求めるための逆関数の存在も存在します。存在するはずです。

剰余類群

Wikipediaの離散対数問題の記事や、その他様々なWeb上の記事を見ると $\mathbb{Z} / n\mathbb{Z}$ という記載があります。具体的な名称が色々あり「nを法とした整数の加法群」だったり「整数の加法群」だったり「循環加法群」って呼ばれているものです。これが、今回ここまで長々と記載してきたものの着地点の1つです。

$\mathbb{Z}/n\mathbb{Z}$ （ここでは剰余類群と読んでおくことにします）は下記のように求めていきます。

剰余類

まず剰余類とはなんぞ、という話です。難しい書き方は下記になります。

$m \in \mathbb{Z}$ とします。このとき $\mathbb{Z}$ の空ではない部分集合 $R$ において

$a, b \in R \text{のとき} a \equiv b \bmod m$
$a \in R \text{かつ} a \equiv c \bmod m \text{のとき}c\in R$

を満たすとき、 $R$ を剰余類と呼びます。

簡単に記載すると、これは $m$ で割ったあまりの集合です。また、mで割ったあまりの集合は加法において群となります（ $\bmod m$ の中で）。剰余群または剰余類群とも呼ばれます。ここに「mを法とする」と付く場合もありますが。
この剰余類は $\mathbb{Z}/m\mathbb{Z}$ とも記載されます。mで割ってる感じが出てわかりやすいですね。また、 $Z_m$ と記載されたり、 $m$ が素数である場合 $F(m)$ や $GF(m)$ と記載される場合もあります^[4]。

既約剰余類群

mを法とする剰余類の中で、積（ $\times$ ）において可逆である元 = 逆元を持つ元の集合のことを既約剰余類と呼びます。 $(\mathbb{Z}/m\mathbb{Z})^\times$ と表現します（ｍを法とした場合）。右上は演算を表しているので人によっては $\ast$ だったり $\bullet$ だったり $\circ$ だったりするかもしれません。またそれらは乗法において群となるため、それを既約剰余類群と呼びます。

パッと想像するのは難しいかと思いますが、適当な値で考えてみます。

$m = 6$ とします。そうなると既約剰余類群は $(Z/6Z)^\times$ と表現できますね。

まず剰余類 $Z/6Z$ を書き出してみます。アマノジャクだから $\{6, 7, 8, 9, 10, 11\}$ と書いても一応定義的には間違っていません。

Z/6Z = \{0, 1, 2, 3, 4, 5\}

次にそれぞれの要素が可逆であるかどうかを確認してみます。この時演算はただの乗算ではなくm(=6)を法とした乗算です。すなわち $(a \times b) \bmod 6$ となります。ちなにみに当然ですが単位元は1です。

以下の式はすべて6を法とするため $\bmod 6$ を省いて記載します。

\begin{aligned} 0 \times b &= 1\text{となる}b\text{はない}\rightarrow\text{可逆ではない} \\ 1 \times b &= 1\text{となる}b = 1 \rightarrow\text{可逆である（単位元は常に可逆である）} \\ 2 \times b &= 1\text{となる}b\text{はない}\rightarrow\text{可逆ではない} \\ 3 \times b &= 1\text{となる}b\text{はない}\rightarrow\text{可逆ではない} \\ 4 \times b &= 1\text{となる}b\text{はない}\rightarrow\text{可逆ではない} \\ 5 \times b &= 1\text{となる}b=5\rightarrow\text{可逆}\\ \end{aligned}\\ \therefore (Z/6Z)^\times = \{1, 5\}

ちなみにですが、可逆ではない要素はすべて零因子です。零因子は群 $(G, \circ)$ の要素 $a$ において $a\circ b = 0$ となる $0$ を除く要素 $b$ が存在するということです。2であれば3( $(2\times3) \bmod 6 = 0$ )だったり、4であれば3であったりします。

既約剰余類であるには元 $a$ が法である $m$ と互いに素である必要があります。すなわち割り切れない数であり、最大公約数が1となる必要があります。また0だけは必ず既約剰余類にはなりません。

本章の参考文献

新妻弘, 木村哲三.(2007).「群・環・体入門」第10版. 共立出版株式会社.

離散対数問題

離散対数問題の定義を書くまでの前提知識が多すぎる。

離散対数の定義は次のようになります。

任意の素数 $p$ と生成元 $g$ により生成される巡回群 $(G, \circ)$ を考える。この時、 $(\mathbb{Z}/p\mathbb{Z})^\times \longrightarrow G$ への同型写像を $f$ とする。この $f$ の逆写像 $log_g: G\longrightarrow (\mathbb{Z}/p\mathbb{Z})^\times$ を計算する問題のことを離散対数問題と呼ぶ。

DH法では秘密鍵 $S$ を利用して $g^S \bmod p$ で公開鍵を計算しました。この $S$ は2以上 $p$ 未満の任意の数と記載していましたが、正確には $S \in (\mathbb{Z}/p\mathbb{Z})^\times$ となります。ただし1は単位元であり、 $g$ がそのまま出てきてしまうため実質的に省かれています。 $p$ が素数の場合は実質的に同じです。
また、 $f$ は $f(x) = g^x \bmod p$ です。そしてこの逆関数 $f^{-1}$ こそ $f^{-1}(y) = log_{g}y \bmod p = log_{g}(f(x)) \bmod p$ です。

ここまで来ると十分に一般化されたので、この $f$ が楕円曲線の何らかの処理にすればそのまま楕円曲線における離散対数問題になります。私も調べてないので詳しくはないですが、楕円曲線では $G$ が加法群になるので見かけは全く異なります。

最後に

力尽きた。

サイドチャネル攻撃は暗号装置を外部から物理的手段で観察することで鍵などの情報を取得しようとする攻撃。バイナリ法の場合は秘密鍵 $S$ を2進数に直したときの1の数だけ追加で計算が発生することから、処理時間を計測することで秘密鍵 $S$ を類推する攻撃とります。
処理時間に対するサイドチャネル攻撃はタイミング攻撃とも呼ばれます。 ↩︎
$\bmod n$ のことをしばしばnを法とすると記載されます。かっこいいですね。 ↩︎
当ブログではじめてで言葉なので注釈を入れておきます。 $\mathcal{O}$ はオーダー記号、またはランダウの記号と呼ばれざっくりとした計算量を求めるのに利用します。特にコンピューターの世界ではアルゴリズムの有用性の指標であり、特にソートの分野ではよく見ますね。
　簡単にいれば、要素数 $n$ の増加量とともに増えていく計算量の指標で、 $\mathcal{O}(n^2)$ はnが増えていくとnの2乗のペースで計算量が増えていくというものです。
例えば連続した2つの要素 $a_n, a_{n + 1}$ があった場合 $a_n$ のほうが大きければ要素を交換する、というアルゴリズムであるバブルソートは、純粋に作ると $\mathcal{O}(n^2)$ です。また最も高速であるクイックソートは平均計算量が $\mathcal{O}(nlog_n)$ です（データの並びが悪いと $\mathcal{O}(n^2)$ となります）。
ここで注意する必要があるのはオーダーが同じだから同じ計算量であるとか、オーダーが小さいから早い、というわけではないです。例えばクイックソートに1年でお株を奪われてしまった高速ソートの1つである「ヒープソート」も $\mathcal{O}(nlog_n)$ ですが、クイックソートよりは遅いとされています。
また、クイックソートも十分に大きな要素数では高速ですが、前準備がある為要素数が十分に小さければバブルソートの方が早くなります。
ちなみにクイックソートは要素のグループを細かく分けて分けて分けて…とやっていくのですが、十分小さくなったらバブルソートでソートすることでさらなる高速化が出来ます。 ↩︎
$F(m)$ や $GF(m)$ は有限体やガロア体と呼ばれるものです。 ↩︎