高次方程式と対称式による新型公開鍵暗号・デジタル署名

(量子コンピュータの実現に対抗して)

対称式が基本対称式で表されることを用いて，量 子コン ピュータの実現に対 抗できると考えられる新方式の公開鍵暗号を開発しました。Elgama暗号タイプの公開鍵暗号(Diffie-Hellman鍵共 有)で，デジタル署名にも対応しています。ある種の離散対数問題の困難性に依りますが，多次多変数方程式を解く困難性が加わっていま す。 この暗号の鍵のbit数や暗号化・復号にかかる時間は，RSA暗号やElgama暗号より若干大きい程度で，実用的な 暗号です。量子コンピュータの実現は数十年先と思われていましたが，急激な技術の進歩により数年後に実現する可能性があります。この暗号こそ，量子コン ピュータが実現された時に最適な公開鍵暗号であると考えます。
また，この暗号の特に2次式の場合で，素数ではなく，大きな合成数を法とする剰余類上に構築した，Ｎ＝pqの素因数分解できない ⇒ 離散対数問題の解は求まらないことが証明できる暗号は次のものです。ただし，量子コン ピュータには対抗できませんが，「世界最速の公開鍵暗号」です。Chebyshev2.pdf

高次方程式と対称式による公開鍵暗号（高次対称式暗号）

素数を法とする剰余 体K上のn次方程式
        xn－σ1xn －1＋σ2xn－2－σ3xn－3＋…＋ (－1)n－1σn－1x＋(－1)nσn＝0    …①
を考える。この方程式による体Kの拡大体での， ①の解をα1，α2，α3，…， αn　 とすると，①は
        (x-α1)(x-α2)(x-α3)・…・ (x-αn)＝0
となるから，σ1，σ2，σ3，…，σnはα1，α2，α3，…， αn の基本対称式である。
ここで，xnの係数が1で，α1p，α2p，α3p，…， αnpを 解とするn次方程式
       (x-α1p)(x-α2p)(x-α2p)・…・ (x-αnp)=0
の左辺の展開式をfp(x)とする。
多項式fp(x)の係数は，α1p，α2p，α3p，…， αnp の基本対称式であるからα1，α2，α3，…， αnの 対称式であり，よって，σ1，σ2，σ3，…，σn－1，σnで 表すことが できる。
したがって，p，qを異なる自然数として，f1(x)から
        fp(x)　と　fq(x)
が共に求められる。
ここで，fpq(x)を考えると，その係数はα1pq，α2pq，α3pq，…， αnpq の基本対称式であるから，α1p，α2p，α3p，…， αnp の対称式であり，したがって，fpq(x)の係数はfp(x) の係数で表すことができる。
同様に，fpq(x)の係数はfq(x) の係数で表すことができる。 すなわち
         fp(x) とqからfpq(x) を
         fq(x) とpからfpq(x) を
求めることができる。
これにより，送信者と受信者で多項式fpq(x)を共有でき，Elgamal暗号タイプの 公開鍵暗号(Diffie－Hellman鍵共有)が構成できる。

実装時には，nは3以上の素数とし，定数項(－1)nσnは-1と す る。このとき，fp(x)の定数項は常に-1である。
また，①が体Ｋ上に解を持たないようにσ1，σ2，σ3，…，σnの 値をとる。この場合でも拡大体を考えれば，①は必ず解α1，α2，α3，…， αn を持つ。

上記の暗号の実装上の問題点は，f1(x)からfp(x)　を高速に求めることであるが，実際に高速なアル ゴリズムがあり，それを実装することができた。
 
①の解の1つをαとおくと
       αn－σ1αn－1＋σ2αn －2－σ3αn－3＋…＋(－1)n－1σn－1α ＋(－1)nσn＝0
両辺にαk－ｎをかけて，変形すれば
       αk＝σ1αk－1－σ2αk －2＋σ3αk－3－…－(－1)n－1σn－1α －(－1)nσnαk－n    …②
が成り立つ。②を繰り返し用いれば，任意の自然数pについてαpはα0，α1，α2，…， αn-1 で表される。
すなわち，任意の自然数pについて αp は
        αp＝t1αn －1＋t2αn－2＋t3αn－3＋…＋tn －1α＋tn  …③
の形に表すことができ，右辺の係数t1，t2，t3，…，tn－1，tn を求めることができる。
巨大な自然数pに対して，αpを αn+1，αn+2，αn+3，… ，αpと逐次求めていったのでは，遅くて実際上は求められないので，バイナリー法を用いる。
αkが α0，α1，α2，…，αn-1 で表されれば，αk＋1＝αk・ α およびα2k＝(αk)2 もα0，α1，α2，…， αn-1 で表すことがでるから，バイナリー法により，任意のkについてαkをα0，α1，α2，…， αn-1 で表すことが できる。
したがって，③のt1，t2，t3，…，tn－1，tn は高速に求められる。
次に，
        Sp＝α1p＋α2p＋… ＋αnp
と する。Spは α1，α2，…，αn についての対称式である。このSpを求めたい。
③のαにα1，α2，α3，…，αnを代入して加えると
        Sp＝t1Sn －1＋t2Sn－2＋t3Sn－3＋…＋tn －1S1＋tnS0
となるから，この等式の右辺に S0 ，S1 ，S2 ，S3 ，…，Sn-1 の値と t1，t2，t3，…，tn －1，tn の値を代入すればSpの値が求められる。
さらに，③を2乗，3乗，…　としていけば
        αp，α2p，α3p，…， αnp
もα0，α1，α2，…，αn-1 の一次結合で表すことができ，その係数も求められるから，Sp ，S2p ，S3p ，…，Snp が求められる。以上より
        σ1，σ2，σ3，…， σn－1，σn と S0，S1，S2，S3，…， Sn-1 の値から Sp，S2p，S3p，…， Snp の値を 高速に求められる。   …④

さらに，基本対称式 σk (1≦k≦n)  と対称式 Sk＝α1k＋α2k＋…＋αnk (1≦k≦n) を相互に変換する，以下のニュートンの公式（アルゴリズム）を用いる。

累乗和を基本対称式から求めるアルゴリズム
        S1＝σ1
        S2＝σ1S1－2σ2
        S3＝σ1S2－σ2S1＋3σ3
          ………………
        Sn＝σ1Sn －1－σ2Sn－2＋…＋ (－1)nσn－1 S1＋(－1)n＋1nσn
    さらに，k≧n のとき
        Sk＝σ1Sk －1－σ2Sk－2＋…＋ (－1)nσn－1 Sk－n＋1＋(－1)n＋1σnSk－n   ←数列 {Sk}は， S1，S2，S3，…， Sn と，この漸化式により定義されると考えて良い

基本対称式を累乗和から求めるアルゴリズム
        σ1＝S1
        σ2＝－(S2－σ1S1)・ 2－1
        σ3＝(S3－σ1S2＋σ2S1)・ 3－1
    　　    ………………
        σn＝(－1)n＋1 {Sn－σ1Sn－1＋σ2Sn－2－… ＋(－1)n－1σn－1S1}・n－1

このアルゴリズムを用いることにより， σk (k＝1，2，3，…，n)  と Sk (k＝1，2，3，…，n)　の一方から他方が求められる。
よって，  (x-α1p)(x-α2p)(x-α2p)・…・ (x-αnp)=0  の左辺の展開式の xn-k の係数を σ(p，k) とすると
        　σ1，σ2，σ3，…， σn  →　S1，S2，S3，…，Sn 　→　Sp，S2p，S3p，…，Snp　→　σ(p，1)，σ(p，2)，σ(p，3)，…，σ(p，n)
と求めることができる。
したがって，σ(p，1)，σ(p，2)，σ(p，3)，…，σ(p，n)  の数の組をσ(p)と表すことにすると
p，qを巨大な自然数として，
       σ(1)  から σ(p)  と σ(q)　が
        σ(p)  と σ(q)  のどちらからも  σ(pq)　が
高速に求められる。

これにより次のように，Elgamal暗号が構成できる。    (以下のpとqの大きさを，共通鍵暗号と同じ128bit程度に押さえれば，極めて高速になる。)

(1)  s＝σ(1)，t＝σ(p)を受信者の公開鍵とする。pが秘密鍵である。

(2) 送信者は，文書 Mに対して秘密の乱数qを選び，sからγ＝σ(q)，tから σ(pq) を計算する。
    文書 Mを，σ(pq) を鍵として共通鍵暗号で暗号化する。
    受信者に，暗号化した文書とγ＝σ(q)を送る。

(3) 受信者は，γ＝σ(q)と秘密鍵pからσ(pq)を計算し，σ(pq)を鍵として文書を復号する。

ここで，③の t1，t2，t3，…，tn から④の Sp，S2p，S3p，…，Snp を 求めることは簡単にできるが，Sp，S2p，S3p，…，Snp か ら t1，t2，t3，…， tnを求めることは困難です。
通常のElgamal暗号は③の t1，t2，t3，…，tn が与えられたときにpの値を求めることが困難であること（離散対数問題）を暗号強度の根拠としていますが，この暗号の強度には
        Sp，S2p，S3p，…， Snp か ら t1，t2，t3，…，tnを 求める困難度
が加わります。Sp，S2p，S3p，…，Snp か ら t1，t2，t3，…， tn を求めるには， t1，t2，t3，…， tn についての線形でない連立方程式を解かなければならず，したがって，この暗号は強度の根拠として，多次多変数方程式を解く困難問題が加 わります。 これにより，量子コンピュータの実現に 対する耐性があると考えます。

equatiok.pdfには，ニュートンの公式の証明と，ニュートンの公式を用いて，行列の固有多項式を求めるアルゴリズムであるフレ－ム (Frame)法の証明も記述してあります。詳しくはequatiok.pdfをご覧下さい。

高次対称式暗号におけるデジタル署名

a1，a2，a3，…，an　および　b1，b2，b3，…， bnに対して，xのn2次の多項式の恒等式    (実装時にはnは素数とするので，nは3以上の奇数とする）
        (x－a1b1)・(x－ a1b2)・ (x－a1b3)・…・(x－a1bn)・ (x－a2b1)・ (x－a2b2)・(x－a2b3)・…・ (x－a2bn)・…・ (x－anbn)
                    ＝xn^2－（a1＋a2＋a3＋… ＋an)（b1＋b2＋b3＋…＋bn)xn^2 －1＋(a12b1b2＋a12b1b3＋a12b1b4＋… ＋an2bn－1bn)xn^2－2＋… －(a1a2a3…anb1b2b3…bn)n…①
を考える。
係数は a1b1，a1b2，a1b3，…， a1bn，a2b1，a2b2，a2b3，…， a2bn，…，anbn の基本対称式であるから，
        Tk＝(a1b1)k＋(a1b2)k＋(a1b3)k＋… ＋(a1bn)k＋(a2b1)k＋(a2b2)k＋(a2b3)k＋… ＋(a2bn)k＋… ＋(anbn)k
を用いて表すことができる。変形して
        Tk＝（a1k＋a2k＋a3k＋… ＋ank)（b1k＋b2k＋b3k＋… ＋bnk)
ここで，ニュートンのアルゴリズムを用いれば，多項式①の係数はすべて Tk  (k＝1，2，3，…，n2) で表され，Tk は a1，a2，a3，…， an　と　b1，b2，b3，…，bn の基本対称式で表される。多項式①の係数をa1，a2，a3，…， an　 と　b1，b2，b3，…， bn の基本対称式から求める計算量はO(n4)である。
①のxkの係数を(－1)kAn^2－kとおくと，①の右辺は
        xn^2－A1xn^2 －1＋A2xn^2－2＋…－An^2…②
となる。ただし，Akはすべて Tk で表される。
また，①の左辺は
        (x－a1b1)・(x－ a2b2)・ (x－a3b3)・…・(x－anbn)
を因数にもつ。これを展開した式を
        xn－B1xn －1＋B2xn－2＋…－Bn…③
とする。このとき，②は③で割り切れる。
特に    ak＝αkp，    bk＝αkq    とすると    akbk＝αkp＋q     (k＝1，2，3，…，n)
なり，このときも②は③で割り切れる。

その方法を示す。

デジタル署名1    (デジタル署名2に対して，高速で，署名長が短いものであり，2015年3月23日に追加)

(1)  g＝σ(1)，t＝σ(p) を送信者の公開鍵とする。pが秘密鍵である。

(2) 送信者は，文書 Mに対して，文書 Mのハッシュ値e＝h(M)を求め，さらにλ＝σ(p+e) を求める。
　 λがMの署名である。（安全のため，文書 Mにはパディングをする。）
    このとき，σ(p) とσ(e)から作られる②式がλ＝σ(p+e) による③式で割り切れる。
    送信者は，受信者に文書Mとその署名λを送る。

(3) 受信者は， ハッシュ値 e＝h(M) を求める。
    さらに，g と e から σ(e)を 求め，σ(e) とtから②式を作る。
    このとき，②式をλによる③ 式で割った余りが0となれば，文書 Mの署名が確認されたと考える。

デジタル署名2   （Elgamal署名やSchnorr署 名の変形 版のデジタル署名）     (2011年6月25日にアルゴリズムを改定)

(1)  g＝σ(1)，t＝σ(p) を送信者の公開鍵とする。pが秘密鍵である。

(2) 送信者は，文書 Mに対して秘密の乱数qを選び，次の計算をする。
            γ＝σ(q)
            e＝h(M，γ) 　（文書 Mとγを結合した文書のハッシュ値）
            δ＝q－pe
    このとき，pe+δ＝qであるから，σ(pe) とσ(δ)から作られる②式がγ＝σ(q) による③式で割り切れる。
    送信者は，受信者に文書Mとその署名(γ，δ) を送る。

(3) 受信者は， ハッシュ値 e＝h(M，γ) を求める。
    さらに，ｔ と e から σ(pe)，g とδから σ(δ) を求め，σ(pe) とσ(δ)から②式を作る。
    このとき，②式をγによる③ 式で割った余りが0となれば，文書 Mの署名が確認されたと考える。

注    nは3以上の素数とし，定数項(－1)nσnは-1と す る。
方程式     xn－σ1xn －1＋σ2xn－2－σ3xn－3＋…＋(－ 1)n－1σn－1x－1＝0
の両辺をxnで割り，1/x＝t と置くと
         tn－σn－1tn －1＋σn－2tn－2－σn－3tn－3＋… ＋(－ 1)n－1σ1t－1＝0
元の方程式と係数の並びが逆になる。
よって，ニュートンのアルゴリズムにおいて，σ0，σ1，σ2，…， σn －1，σn をσn，σn－1，σn－2，…， σ1，σ0 に置き換え，S1，S2，S3，… を S－1，S－2，S－3，… に置き換えた等式が成り立つ。σn－1，σn －2，…， σ（ｎ＋1）/2については，これ を用いて求めると，デジタル署名において計算量は約1/2となり，並列化が可能なため計算時間は，そのさらに1/2にできる。

高次対称式暗号の特徴

  1. この暗号は，素 体Kの数の組 σ＝（σ1，σ2，σ3，…， σn－1）  と自然数p から数の組 （σ1,p，σ2,p，σ3,p，…，σn－1,p）  への写像 f(σ，p) と考えら れます。このとき f(f(σ，p)，q)＝f(σ，pq) が成り立ちますが，f(σ，p) と f(σ，p) から f(σ，p+q) は求まりません。したがって，Elgamal暗号(Diffie -Hellman鍵共有)は構成できますが， 通常のElgamal暗号に対する効率的な暗号解読法は無力となります。 さらに，量子コンピュータに対して耐性があると考えられます。
  2. Elgamal暗号と同様の指数の計算の後に，後処理が加わるため，通常のElgamal暗号に比べて同じbit長ならば，若干暗号化が遅く なります。
  3. 計算量は，n次方程式の場合単純な方法ではO(n3)となります。そのため，全体の計算量はO(bit数3) となります。
  4. n次方程式の場合，鍵のbit数は，実装する体のbit数の約n－1倍となります。
  5. この暗号を効率的に解くには，多次多変数方程式を解く必要があると思われますので，多次多変数公開鍵暗号と考えられま す。ただし，安全のためにnは100以上とするのがよいと思われます。
  6. 上記のデジタル署名1の署名長は公開鍵長と同じで，デジタル署名2の署名長は公開鍵長より長い。また，計算にはO(n3) とO(n4)の部 分がありますが，O(n4)の部分の係数が小さいのでnが100程度であれば十分な速度がでます。
  7. 特許は申請しておらず，したがって，アルゴリズムは自由に使えます。
高次対称式暗号とそのデジタル署名を，13bit×103次方程式の場合に実装してみました。
以下は，3次式までのもので，上記の暗号を考え付く元になったものです。あくまでも参考のためだけに残しています。

この暗号は指数時間でしか解けな いと考えます。 この暗号こそ，量子コンピュータが実現して，RSA暗号，Elgamal暗号，楕円曲線暗号が滅びたときにも生き残ると考えられる「世界最強 の公開鍵暗号」です。

著書「16歳のセアラが挑んだ世界最強の暗号」で有名な「セアラの暗号」にも，「解読不能は数学的に証明済み」と主張した「CAB方式の暗号」にも脆弱性 がありました。     Sarah.pdf    CAB.pdf
この暗号にも，このような脆弱性がある可能性はあります。理論や実装に間違いや欠陥を見つけられた方や，世界最強の公開鍵暗号でないと思う方，こんな暗号 は簡単に解けると思う方は，メールにてお知らせ頂ければ幸 甚です。
MAIL.PNG - 671BYTES
(メールアドレスは，スパムメール対策のために画像になっています。)
最初のページ に戻る