<< 戻る

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

ハローワールド

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

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

DH法の安全性

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

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

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

累乗の余りの計算

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

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

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

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

離散対数の計算

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

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

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

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

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

離散対数問題…の前に群

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

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

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

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

集合

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

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

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

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

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

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

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

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

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

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

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

部分集合

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

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

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

写像

ある集合AAの要素aaを別の集合BBの要素bbと一対一で対応させるような規則ffを集合AAから集合BBへの写像と呼びます。記号で表すと下記の様な書き方があるようです。

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

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

f:ABf: A \longrightarrow Bであるとき、AAの要素aaBBの要素bbに対応するとき、bbffによるaaと呼びます。このときBBすべての要素に紐づく必要はありませんし、AAの要素a1,a2a_1, a_2に対するf(a1),f(a2)f(a_1), f(a_2)が同じ値になる可能性もあります。

直積集合

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

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

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

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

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

群の定義

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

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

  1. 集合GGに一つの演算が与えられていて、次の条件を満たす場合、GGはこの演算に関して群をなす、または群であるという。

    1. 結合律: GGの中の任意の元a,b,ca, b, cに対して常に(ab)c=a(bc)(a\circ b) \circ c = a \circ (b \circ c)が成立する。
    2. 単位元: GGの中の任意の元aaに対してae=ea=aa \circ e = e \circ a = aを満たす特別な元eeが存在する。この時aは可逆であると呼ぶ。
    3. 逆元: GGの中の任意の元aaに対してab=ba=ea \circ b = b \circ a = eを満たすbbが存在する。

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

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

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

巡回群

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

すなわち

C={,a3,a2,a1,a0=e,a,a2,a3,}C = \{ \ldots, a ^ {-3}, a^ {-2}, a ^ {-1}, a^{0} = e, a, a^2, a^3, \ldots \}

ということです。

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

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

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

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

位数 vs 位数

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

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

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

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

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

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

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

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

準同型写像

今度は写像に戻ります。

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

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

単射・全射・同型写像

じゃあ同型写像もあるのかと思いますが、当然存在します。

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

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

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

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

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

剰余類群

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

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

剰余類

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

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

  • a,bRのときabmodma, b \in R \text{のとき} a \equiv b \bmod m
  • aRかつacmodmのときcRa \in R \text{かつ} a \equiv c \bmod m \text{のとき}c\in R

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

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

既約剰余類群

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

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

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

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

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

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

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

0×b=1となるbはない可逆ではない1×b=1となるb=1可逆である(単位元は常に可逆である)2×b=1となるbはない可逆ではない3×b=1となるbはない可逆ではない4×b=1となるbはない可逆ではない5×b=1となるb=5可逆(Z/6Z)×={1,5}\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,)(G, \circ)の要素aaにおいてab=0a\circ b = 0となる00を除く要素bbが存在するということです。2であれば3((2×3)mod6=0(2\times3) \bmod 6 = 0)だったり、4であれば3であったりします。

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

本章の参考文献

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

離散対数問題

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

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

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

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

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

最後に

力尽きた。


  1. サイドチャネル攻撃は暗号装置を外部から物理的手段で観察することで鍵などの情報を取得しようとする攻撃。バイナリ法の場合は秘密鍵SSを2進数に直したときの1の数だけ追加で計算が発生することから、処理時間を計測することで秘密鍵SSを類推する攻撃とります。。
    処理時間に対するサイドチャネル攻撃はタイミング攻撃とも呼ばれます。 ↩︎

  2. modn\bmod nのことをしばしばnを法とすると記載されます。かっこいいですね。 ↩︎

  3. 当ブログではじめてで言葉なので注釈を入れておきます。O\mathcal{O}はオーダー記号、またはランダウの記号と呼ばれざっくりとした計算量を求めるのに利用します。特にコンピューターの世界ではアルゴリズムの有用性の指標であり、特にソートの分野ではよく見ますね。
     簡単にいれば、要素数nnの増加量とともに増えていく計算量の指標で、O(n2)\mathcal{O}(n^2)はnが増えていくとnの2乗のペースで計算量が増えていくというものです。
    例えば連続した2つの要素an,an+1a_n, a_{n + 1}があった場合 ana_nのほうが大きければ要素を交換する、というアルゴリズムであるバブルソートは、純粋に作るとO(n2)\mathcal{O}(n^2)です。また最も高速であるクイックソートは平均計算量がO(nlogn)\mathcal{O}(nlog_n)です(データの並びが悪いとO(n2)\mathcal{O}(n^2)となります)。
    ここで注意する必要があるのはオーダーが同じだから同じ計算量であるとか、オーダーが小さいから早い、というわけではないです。例えばクイックソートに1年でお株を奪われてしまった高速ソートの一つである「ヒープソート」もO(nlogn)\mathcal{O}(nlog_n)ですが、クイックソートよりは遅いとされています。
    また、クイックソートも十分に大きな要素数では高速ですが、前準備がある為要素数が十分に小さければバブルソートの方が早くなります。
    ちなみにクイックソートは要素のグループを細かく分けて分けて分けて…とやっていくのですが、十分小さくなったらバブルソートでソートすることでさらなる高速化が出来ます。 ↩︎

  4. F(m)F(m)GF(m)GF(m)は有限やガロアと呼ばれるものです。 ↩︎