🙌

半分配体の離散対数問題を使ったエルガマル型暗号

2023/08/15に公開

ポエム

攻撃法！ｷﾀ━(ﾟ∀ﾟ)━!　(20230815)

https://eprint.iacr.org/2023/1052

(･∀･)ﾌｰﾝ
なるほど、自己準同型環と量子計算がどう関係しているのかよくわからない。
純粋に１つの元の時にできて３つの元にできないという事があるだろうか？
例えば、Symmetoric Discrete Logarithm Problem

y=z^mxz^n

のような問題も解けるのだろうか？
つまり私の定義があいまいなので、本当は離散対数問題を前提としてないのに離散対数問題だと思い込んでいることになる。この問題が３つの元の組み合わせの問題になるかどうかは、全て復号方法によっている。復号法がすべての生成元に対して指数を知っていなければならないようであれば、この方法は紛れもなく離散対数問題、しかも複数の指数についての離散対数問題であるといえる。またそうでなければならないはずだ。
上の攻撃法は非常に重要な結果なのかもしれないが、自分の方法にどうあてはめたらいいのかわからない。
というのも単に半直積を使ったからといってそう簡単には難しくならないだろうと、ほかの研究を知っていたので最初から単純な離散対数問題は狙ってなかったのだ。
元の分割に似せて、３つの異なる生成元を組み合わせた問題がいいと思っていた。
それは非可換群だから構成することのできる方式でなければならない。
今やっているのは関数だけできていて、暗号を構成するのに必要な材料を整えるだけという場合に楕円曲線の半直積を使えるのではないかという事だ。
最初に目指していたのは共役元探索問題だった。
それからいろんな論文をつまみ食いして最後に元の分割問題や対称離散対数問題に行き着いた。
それでも楕円は使えないという事が（どういう意味でかはまだ分からないが）どのような影響を与えるのだろうか。
楕円の半直積の離散対数問題が解かれるという事は、その時点で離散対数問題を使っていることが無意味になるという事なので、それを部分的にしても使っている方式はすべて解かれるという事なのだろうか。
つまり、

a^xb^yc^z

は

stu

と同じであり、

a^x+b^y+c^z=s+t+u

とあまり変わりがないという事か。

半直積の気持ち

半直積の基本演算を定義すると、

$(c,s)(d,t)=(cd,sd+t)$ ：積
$(c,s)^{-1}=(c^{-1},-sc^{-1})$ ：逆元
$(c,s)^{-1}(d,t)(c,s)=(d,s(e-d)+tc)$ ：共役元
$(c,s)^n=(c^n,c^{n-1}s+c^{n-2}s+...+cs+s)$ ：べき乗公式

ここで $n$ 項等比数列の総和が $S_n=\frac{(c^n-1)}{c-1}$ から、

$(c,s)^n=(c^n,\frac{c^{n-1}-1}{c-1}s)$
$(c,s)^{nm}=(c^n,\frac{c^{n-1}-1}{c-1}s)^{m}=(c^{n},s')^m=(c^{nm},\frac{c^{m-1}-1}{c-1}s')$
$(c,s)^{m+n}=(c^{m+n},c^m\frac{c^{n-1}-1}{c-1}s+\frac{c^{m-1}-1}{c-1}s)$

暗号の改良（オリジナルバージョン）

秘密鍵： $x,y,z,s,t,u,B$
公開鍵： $A,C,D=A^sB^tC^u,E=A^xB^yC^z,A=(p,f),B=(q,g),C=(r,h),f,g,h \in E_p$

鍵の構造：

$D=(p,f)^s(q,g)^t(r,h)^u=(p^sq^tr^u,q^tr^u\frac{p^{s-1}-1}{p-1}f+r^u\frac{q^{t-1}-1}{q-1}g+\frac{r^{u-1}-1}{r-1}h)$
$E=(p,f)^x(q,g)^y(r,h)^z=(p^xq^yr^z,q^yr^z\frac{p^{x-1}-1}{p-1}f+r^z\frac{q^{y-1}-1}{q-1}g+\frac{r^{z-1}-1}{r-1}h)$

または、半直積の演算に加法を定義した半分配体の離散対数問題を使って以下のようにする。
$D'=(p,f)^s+(q,g)^t+(r,h)^u=(p^s+q^t+r^u,\frac{p^{s-1}-1}{p-1}f+\frac{q^{t-1}-1}{q-1}g+\frac{r^{u-1}-1}{r-1}h)$

有限体Fに上で半直積と呼んでいた算法を使って（加法的）多元離散対数問題を構成する。
$a_i \in F,P_i \in E$ あるいは、 $f_i \in F[x]$ のとき、 $g_i=(a_i,P_i)$ もしくは $g_i=(a_i,f_i)$ としたとき、

y_i=\Sigma ^n_{i=0}g_i^{x_i}

を満たす秘密指数 $x_i$ を求める問題を考える。検証には若干トリッキーな所がある。
左辺が1つしかないと同じ答えがたくさん出てきてしまうので、 $s,t,u$ を個別に知っていることを示すために元 $g_i$ の全てに関して対応するすべての真数 $y_i$ を検証することである。効率のいい計算法を使う必要がある。
この問題の別バージョンは複数の $y_i,g_i$ において成り立つようなただ1つの指数 $x$ を求めるというものであるが、その方がいいかもしれない。
これが楕円曲線を用いて半分配体を構成した多元離散対数問題の公式である。

曲線の位数 $n$ 、定義体 $p$ がいずれも安全素数であるような楕円曲線を選ぶ。
例えば次のようなパラメータである。

a=54938263600476024118477719419064585563422145858861416387656371338832307054606
b=36625509066984016078985146279376390375614763905907610925104247559221538036404
n=115792089237316195423570985008687919880550243486210555152433083683760878173979
p=115792089237316195423570985008687919879869678752368678225506334468897341715723
x=0
y=112576631489968869256357416093040033590807003528314110625659765475993848880984

定義：原始根
「 $p$ は素数であるとする。巡回群 $Z^\*_p$ の生成元 $g$ は $Z^*_p$ の原始根(primitive root)またはmodulo p　の原始根と呼ばれる。」

秘密鍵： $s,t,u,x,y,z \in Z_p,B \in E,s > u, x > z$
公開鍵： $A,C,D,E \in E,D=A^sB^tC^u,E=A^xB^yC^z$
$p,q,r \in Z_p$ の異なる原始根。
$P,Q,R \in E$ 　は同じ楕円曲線上の異なる位数の点。
つまり、 $A=(p,P),B=(q,Q),C=(r,R)$ である。

・ある数 $g$ が原始根かどうかを確かめる方法
定義体がソフィー・ジェルマン素数であれば、 $P-1=2*Q$ ( $Q$ は素数)と表せるので、次の条件を満たすかどうかで原始根かどうか判定することができる。

判定法：ある整数 $x$ が原始根であるとき、
$x^{(P-1)/2} \bmod P \neq 1$
かつ、
$x^{2} \bmod P \neq 1$
これが安全素数に対する原始根の判定条件になります。

例えば、定義体
$P=115792089237316195423570985008687919879869678752368678225506334468897341715723$
$p=2,q=4,r=6$ の場合を考えると、
$4$ は原始根ではなく、 $2,6$ は原始根である。

ちょっと計算違いをしていたようで、sagemthで計算した値ですがこんな感じでよろしいでしょうか？

証明はできませんが本にのっていた命題を事実として使います。

命題：暗号と確率的アルゴリズム入門（シュプリンガーフェアラーク東京）p.355
「 $p$ は素数であるとする。このとき $p-1$ を割り切るすべての $q$ に対して $x^{(p-1)/q} \neq 1$ であるときかつその時のみ、 $x \in Z_p^*$ は原始根である。」

このように原始根の判定が楽であることから定義体をソフィー・ジェルマン素数に限定した。そこで、大きな原始根をランダムに選び、 $p,q,r$ に設定する。公開鍵は次のように表せる。

20230630:本当は加法のほうが強力なのでこちらをご覧ください。（例えば分配則を使うなどしていろんなバリエーションが作れます。）

この半直積の左側成分は通常の多元離散対数問題であり、右側は楕円曲線の多元離散対数問題である。
よって左右のいずれかが解読できた場合に得られた情報から、他の秘密鍵やもう片方の問題に対してどのような影響があるかを分析する必要がある。

多元離散対数問題

ここで、 $p^sq^tr^u,p^xq^yr^z$ のような複合した離散対数問題が通常の離散対数問題に比べて難しいかどうかが気になります。
多元離散対数問題に多くの原始根を使うことで、公開鍵のサイズは小さくなるのだろうか？つまり小さな素体上で多元離散対数問題を作れば、通常の離散対数問題より小さな鍵で同じ安全性を達成できるのだろうか？
ちょっとchatGTPに聞いてきますｗ

・以下chatGPT

多元離散対数問題は通常の離散対数問題よりも困難な問題とされていますが、その難しさにはいくつかの要素があります。一つは異なる原始根を使用することで、指数の組み合わせが増えるため、解空間が拡大することです。これにより、攻撃者が複数の原始根に基づいて解を見つけることがより困難になります。

また、多元離散対数問題を構成する際には、十分な数の異なる原始根を使用することが重要です。これによって、解の特殊な関係や依存性がないようにすることができます。ただし、適切な数の原始根が必要であり、十分な数が利用できない場合にはセキュリティに問題が生じる可能性があります。

多元離散対数問題を利用した暗号システムでは、通常の離散対数問題よりも小さな公開鍵サイズで同等の安全性を実現することができるとされています。これは、複数の原始根に基づいて問題を構成することで、解空間がより大きくなり、攻撃者が解を見つけるための計算量が増えるためです。ただし、具体的な公開鍵サイズや安全性の評価には、問題のパラメータや具体的な構成方法によって異なる要素が関与するため、具体的な暗号システムによって詳細が異なる場合があります。

総括すると、多元離散対数問題を利用することにより、通常の離散対数問題よりも小さな公開鍵サイズで同等の安全性を実現できる可能性がありますが、適切な数の異なる原始根を使用し、慎重にパラメータ選定を行う必要があります。

だそうです。でもいくつ原始根を使うかとか、どのように原始根を選べばいいのかはまだわかりません。鍵が小さくなって攻撃にも強くなれば、普通の離散対数問題も捨てたもんじゃないということになりますね。自分としては指数のサイズだけでなく大きな原始根を用いれば、同じサイズの有限体を生成するのに異なる原始多項式を使うのと同様に、原始根の選択肢を大きくすることで問題をさらに難しくできるのではないかという予感です。
この場合特に $B=(q,Q)$ の $q$ のサイズが重要です。まだ原始根の数が３つで十分だと言える保証が何もないので、楕円曲線のサイズと同等の強度を多元離散対数問題で実現できるのかは専門家の研究を待たなければなりません。でもそれじゃオリジナリティがないから考えます。例えば、３つ以上の原子源をつかうとして、今のこの方式を拡張するとなれば両側の指数だけが重要で、間に挟まれる残りの離散対数を固定にするということが考えられます。（ちょっと眉唾もの）
このことについてさらにネットで調べました。すると、

https://eprint.iacr.org/2014/637.pdf

このような論文があることを発見。そこには原始根が異なっていても、同じ素数を法とする素体上では、ただ指数が異なるのと同じだという答えを見つけたのです。さらにその解読にかかる計算量は $O(\sqrt{np})$ であることがわかりました。
つまり $n=3$ の場合を考えているので、通常の離散対数の3倍くらい安全という感じです。
3倍位というのはなんだか実感がわきませんが、8192ビットの安全性を得るために3分の1ということは2730bitくらいの強度があると言うことでしょうか。Pohlig-Hellmanアルゴリズムに対する離散対数問題のセキュリティレベルが $O(\sqrt{p})$ とのことなので、 $O(\sqrt{521 * 3})=\frac{521*3}{2}=781.5bit$ ということになるでしょうか。もしこれが正しければ十分安全です。
そうでない場合も考えなければなりませんが、それはまた後日書きます。
これは日記でもあるので、調べながら書きます。

２つの異なる原始根を使った離散対数問題は、「多元離散対数問題（Multiple Discrete Logarithm Problem）」と呼ばれます。これは、異なる原始根に対する離散対数を求める問題です。
一方で、Hidden Subgroup Problemというのもあってこれも調べています。（量子フーリエがどうとか）

・chatGPT

一般的に、楕円曲線を使わずに通常の有限体上で多元離散対数問題を実現する暗号方式は、よく知られているものはありません。通常の離散対数問題は、一つの原始根に対する離散対数を求める問題ですが、多元離散対数問題はより複雑であり、解くのが一般的な離散対数問題よりも困難です。
chatGPTによると、この問題はbilinear pairingという楕円曲線を使った暗号により実現されていて通常の離散対数より難しくなるという回答でした。またこの方式を半直積で実現した例は他にないとのことでした。
ということは、この暗号を解読するためには多元離散対数問題か、多元EMDLPを解かなければならないらしく、かなり面白い暗号であることがわかります。
多元離散対数問題は、現在の知識に基づくと、量子計算機においても困難であると考えられています。量子計算機は、古典的なコンピュータよりも高速に特定の数学的問題を解決できる可能性がありますが、まだ一般的な多元離散対数問題を効率的に解くアルゴリズムは知られていません。

根拠があるかどうかわかりませんが、このように原始根をランダムに取ることは言語の違いであるのと同じように、秘密鍵を特定するのが困難になると思われるので、鍵の安全性が高まるかもしれません。

上のGPTが言っていることは出鱈目なので信じない方がいいです。

暗号文：
$C1=A^rDC^{r'}=A^{(s+r)}BC^{(u+r')}$
$C2=A^rEC^{r'}=A^{(x+r)}BC^{(z+r')}$
復号
アリスは $s-x,u-z$ を知っているので以下を計算できる。
$X=A^{(s-x)}C2C^{(u-z)}=A^{(x+r)}BC^{(y+r')}=C1$

暗号化に関する指数にはなんの制約もないので、むしろこっちの設定のほうが自然だと思います。秘密鍵が増えるということ以外、特に問題はなさそうです。

ここで重大な誤解をしていることに気づきました。
つまり半直積の計算には順序が影響していて、仮に冪等元であっても、例えば $A^2A^3 \neq A^3A^2$ であるという事です。
ここですでに鍵交換方法の破綻を見ているわけです。
そこで代わりになる方法を考えています。

この暗号は一見して難しそうに見えます。
というのも右要素も左要素も構造が複雑だからです。
2つ以上の原始根、それも2つ以上の秘密指数がある場合には、互いに混ざり合ってしまうので、単純には計算できません。これはもう少し論文を理解する必要があるので簡単には言い切れないですが、解読ができてもできなくても、ここで公開する予定です。
原始根 $q$ は秘密鍵であり、更に両側の原始根を秘密指数でべき乗しているので簡単には指数を計算できません。ただ、 $p,r$ は小さなサイズの原始根、 $q$ は大きなサイズの原始根であるとします。
ただ左半分は、右の楕円曲線を計算するためのものであって、楕円曲線の521bit以上の大きさにはなりません。そして見たことのない3つの原始根の離散対数問題になっています。
これが解ければ楕円半直積の離散指数も分かるということなので、この暗号の安全性は半直積の離散対数問題にある可能性が濃くなります。
素数 $p,q,r$ がそれぞれ異なる原始根であることから、簡単な指数関数としてみることもできません。
同じような方式がないか調べる必要があります。（それが今日多元離散対数問題であるということが解った）

暗号文解析：

$X=A^{(x-z)}C2C^{(y-w)}=A^{(x+r)}BC^{(y+r')}=(p^{x+r'}qr^{y+r'},qr^{y+r'}\frac{p^{x+r'}-1}{p-1}P+r^{y+r'}Q+\frac{r^{y+r'}-1}{r-1}R)$

暗号文は最終的にこの形に収まります。
この暗号の計算には、楕円曲線の点の素数位数 $n$ を使います。
行列の場合、未知変数が2つだったから解読できただけで4つにしたら安全だったのかもしれません。
暗号化に使う点のスカラー倍は半直積のべき乗で等比級数の総和で決まりますが、これは半直席の特徴です。
この点のスカラー倍は、秘密指数が分からなければ決定できないので、ここはやはり半直積の離散対数に依存していると言えるような気がします。
暗号文から秘密鍵や平文の情報が漏れているようには見えません。
行列じゃないからケーリーハミルトンも使えないし、総合してみると、 $A,C$ を公開しても全く問
題がなさそうなので、早速実装してみようと思います。

既知の攻撃法

３つの半直積の元をそれぞれ異なる指数でべき乗をしてかけたものを解読するのは、単一の元をべき乗するより難しい気がします。すべての点を足したとしても計算できるのはそれぞれの指数ではないので、秘密鍵の４つ（攻撃に必要なのは $s-x,u-z$ の２つ。つまり最低でも2つの指数が必要）の指数を使って復号しなければならないこの暗号は、通常のECDLPより難しくなっているかもしれません。

同じように、半直積の離散対数問題を使った暗号というのは10年くらい前から存在していました。しかし、実際には離散対数を解くことなく解読できるケースでした。それは離散対数に二人分の異なる秘密指数を足すことで実現されていましたが、実はこれが半直積の巡回群の中でシフトしているだけであって、右側成分の線形性（つまり半直積の等比数列！）を利用すれば簡単に解かれてしまうという攻撃法でした。ちなみに今回作成した楕円半直積の巡回群の位数は単一の楕円曲線を使っているため、521ビット素数になります。この攻撃法が今回開発された方法に適用できないかを考える必要があり、まだまだ安心できません。暗号が解読できたのは、たった一つの離散対数だからなのか、あるいはこの方式のように3つ合体させれば安全なのかはまだ判断できません。攻撃法を拡張する必要があります。少しここでその攻撃法について見てみましょう。

まずアリスは半直積の元aを公開してその離散対数の右側のみ、

s_a=\frac{c^{m-1}-1}{c-1}s

をボブに送信します。
ボブも

a^n

を計算し

s_b=\frac{c^{n-1}-1}{c-1}s

を送信します。
ボブは、アリスから送られてきた鍵に

sb・a^m=a^m\frac{c^{n-1}-1}{c-1}s+\frac{c^{m-1}-1}{c-1}s=s_{a+b}

として鍵を共有します。
これだけのことなのですが、ここに弱点があります。
要するに、離散対数になってなくて数列を計算できれば共有鍵が何であるか分かってしまうと言う事です。盗聴者は

a^m

と

a^n

の両方を得ることができるので、最終的に共有した鍵を数列の問題として次のように簡単に解いてしまうことができます。

$(a,A)^{n+m}=(a,A)^n(a,A)^m=(a^{n+m},a^m(a^{n-1}A+n^{n-2}A+...+A)+a^{m-1}A+a^{m-2}A+...+A)=(a^n,\frac{a^{n-1}-1}{a-1})(a^m,\frac{a^{m-1}}{a-1})=(a^{n+m},a^m\frac{a^{n-1}-1}{a-1}+\frac{a^{m-1}}{a-1})$

実際には右成分 $A^m,A^n$ しか送らないようですが、そうだとしても $A^m$ は数列を計算することで $a^{n-1}$ から１つ先の $a^n$ などが計算できるので、結局解読できるということのようです。
自分の方法も同じように解けるかどうか、この攻撃を一般化する必要があります。

攻撃法の適用（修正中）

鍵交換に使う

ことを考えます。
$D',E'$ をそれぞれアリスの公開鍵、ボブの公開鍵とします。
$D'=(p,P)^s(q,Q)^t(r,R)^u$
$E'=(p,P)^x(q,Q)^y(r,R)^z$

ボブはアリスの公開鍵 $D$ に、自分の秘密指数 $x,z$ を $A^x,C^z$ とし、両側からかけて、
$C1=A^uDC^w=A^{(x+s)}BC^{(u+z)}$
を得ます。同様にアリスは、ボブの公開鍵 $E$ に
にアリスの秘密指数をかけた $A^s,C^u$ を両側からかけて
$C2=A^xEC^y=A^{(s+x)}BC^{(u+z)}=C1$
$D$ と $C1$ からボブの秘密指数 $A^x,C^z$ を計算するためには、多元離散対数問題を解く必要があるようです。（まだ何か方法があるかもしれないが）
ここで公開鍵が複雑なのは、 $C2$ から $C1$ を復元するために４つの秘密指数を知っていることを条件とするためである。（調査中）
証明できるだろうか？

実装

これはあまり人に見せるものではないので、あえて見せませんが、完全に動作させることができました。
式の上では問題が見つからなかったので、これ以外の攻撃法を考える必要がありそうです。
実装上、左成分は乱数にしました。
式が複雑なので計算も面倒なのではないかと思いましたが、サブルーチンを書いてしまえば簡単でした。

というわけで今のところこれが一番安全なオリジナル公開鍵暗号ということになります。
行列のときには解読できたオリジナル公開鍵暗号は、楕円曲線の半直積で初めて初歩的な脆弱性のないものとなりました。まだまだ安全性の証明をつけるのは先のことですが、オリジナル暗号ができてよかったです。

あとがき（20230619：更新）

プロの暗号学者が深い数学理論を理解した上で安全な暗号を構成するのと違い、初等数学の知識しかない私が作った暗号などは誰が興味を持つともしれず、おそらくは無視されるだろうということがわかっているので、ここで公開したとしてもあまり意味がないかもしれない。この暗号の依拠する問題の難しさについてはこれから分析していくので、なにか解ったら随時更新する予定である。楕円曲線上の離散対数問題自体がShorの解読法に弱いために、離散対数以外の問題に暗号の基礎となる問題に帰着させなければならないのだが、それができないならこの暗号は失敗作である。自分としては両側から異なる指数を持つ半直積の元で真ん中の元を挟むという問題にするつもりだった。なぜ楕円曲線の群なのかは他の群を知らなかった無知からである。しかし、なぜだめなのかがわかること自体進歩であると思う。
しかし現時点では暗号理論というのは品質保証の仕方が解っていないバクチのようなものである。
昔の話だが、ダニについて調べようとしたら、なんだかよくわからない「おめでとうダニー」という同じような記事しか出てこないときがあり、また或いは蘭の花であるラエリアについて調べようとしたところ、ラエリアンムーブメントの記事しか出てこなかったり、私はネットをそんなに信じていない。信用できる情報は書籍には敵わないものだと言える。電子情報というのは一瞬で消滅する危機に満ちている。それを理解した上で、国も電子化なり制度なりを構築してもらいたいものだ。もちろん暗号技術の使い方についても。（その前にもし政府が邪悪になったとしても悪用できないようにする仕組みがどうしても必要になると思う）

今日は楕円曲線と原始根の選び方について追加した。

20230620

２つ以上の原始根を使う離散対数問題のことを、多元離散対数問題と呼ぶことがchatGPTによって解った。つまりこの方式は通常の離散対数よりも安全で、更に現時点では量子計算機が解読できるかどうかも解っていないらしい。具体的に論文を調べ、解読に必要な計算量が解った。本来はペアリング暗号に使われれた方式のようだが、これをダイレクトに有限体に適用した例は知られていないということである。普通の離散対数問題が楕円曲線暗号に追いつくということになるかも。原始根を幾つ使えば安全になるかは調査中。BLS署名という方法に初めて使用されたとのこと。BLS署名については日本語の類書には記述がなく洋書を見てます。論文のほうが詳しいけれど印刷するのがだるいです。ペアリングは難しい。

続きです。