Chebyshev多項式による公開鍵暗号

安全で高速なチェビシェフ多項式型公開鍵暗号

Chebyshev多項式によるElGamal暗号型の公開鍵暗号を，方程式による拡大体の観点から見直し，合成数を法とすると，Rabin暗号と同じく，安全性の根拠を大きな合成数の素因数分解の困難さとすることができることを示しました。
条件を満たす公開鍵においては，「離散対数問題の解が求まれば，Ｎ＝pqを素因数分解できる」ことが証明できる暗号です。
したがって，その対偶
    Ｎ＝pqの素因数分解できない ⇒ 離散対数問題の解は求まらない
が示されたことになります。これは，Rabin 暗号やEPOC 暗号と似た性質であり，この暗号の安全性を示すものといえます。
ただし，離散対数問題を解かずに，直接にDH問題が解かれる可能性は否定できません。
また，素数を法とする場合は，有限体上のElGamal暗号と同じ安全性しかないことも示されますので，N＝pqの素因数分解が求まり，かつ，素数を法とする有限体上の離散対数問題が解ければ，この暗号が解けることになります。

p，qを素数としてN＝pqとするとき，公開鍵は次の漸化式により第m項k_mを高速に求めることによって作られます。
    k₀＝2，k₁＝k，    k_i+2＝k・ k_i+1-k_i　mod N　…①
kとk_mが公開鍵で，p，q，mが秘密鍵です。 k_m+1は公開鍵ではありません。
暗号化は，nを乱数として①によりk_nを求め，さらに次の漸化式により第n項K_nを高速に求めることによってなされます。
    K₀＝2，K₁＝k_m，    K_i+2＝k_m・ K_i+1-K_i　mod N
このとき，K_n＝k_mnが成り立ちます，

暗号化・復号時間は，共に通常のElGamal暗号の4/3倍かかります。また，中国人剰余定理を用いた場合，RSA暗号の復号時間と比べても4/3倍かかります。
しかし，指数法則　a^r・a^s＝a^r+s に対応する法則が使えないため，有限体上のElGamal暗号および楕円曲線暗号に対する高速解読法がすべて無効となります。
したがって，冪乗の指数のビット数を共通鍵暗号程度（楕円曲線暗号の1/2程度）にしても，安全性が損なわれることはなく，2048bitの暗号で冪乗の指数を112bit程度に小さくとれるものと思われます。
さらに，下記の「ElGamal暗号の復号の高速化法」を用いて冪乗の指数を極端に小さくすれば，復号が桁違いに高速になり，暗号化と復号を総合すると，Chebyshev多項式によるElGamal暗号型が「世界最速の公開鍵暗号」となります。
また，このとき，デジタル署名では，RSA署名と比べて署名生成が3.4倍ほど高速となり，署名長はRSA署名と同じです。

この公開鍵暗号は，安全性と復号速度の両面で，「RSA 暗号を超える公開鍵暗号」です。

解説　安全で高速なチェビシェフ多項式型公開鍵暗号　Chebyshev2.pdf

証明の欠陥を見つけられた場合は，メールにて以下にお知らせ頂ければ幸甚に存じます。 (メールアドレスは，スパムメール対策のために画像になっています。)
MAIL.PNG - 671BYTES

ElGamal暗号の復号の高速化法
冪乗の指数を128bit程度に小さくするのは抵抗があるかもしれません。そこで，中国人剰余定理を用いて，ElGamal暗号の復号を高速化する方法を開発しました。これにより，復号は桁違いに高速になります。
鍵作成
・素数p，qを秘密鍵として N＝pq を計算する。
（このとき，通常はNと同じ程度のbit数の乱数mを秘密鍵として，公開鍵を N，a ， a^m mod N とするが，これを次のように変える。）
・a1＝a mod p，a2＝a mod q とする。そして，小さな自然数 m1，m2 （m1≠m2）を秘密鍵として，b1＝a^m1mod p と b2＝a^m2mod q を計算する。
・中国人剰余定理により，b mod p＝b1 かつ b mod q＝b2 を満たすbを求め，N，a，bを公開鍵とする。
（このとき，a^m mod N ＝b を満たすmは，条件によっては存在しないが，存在するときはNと同じbit数程度の大きな自然数になる。）
暗号処理
・自然数の乱数nを生成する。
・c＝aⁿmod N と d＝bⁿ mod N を計算する。
・dから共通鍵を作成し，共通鍵暗号でメッセージMを暗号化してM’を得る。
・c，M’を受信者に送信する。
復号処理
・c1＝c mod p と c2＝c mod q を計算し，さらに，x1＝c1^m1 mod p と x2＝c2^m2 mod q を計算する。
・中国人剰余定理により，y mod p＝x1 かつ y mod q＝x2 を満たすzを求める。このとき，y＝dが成り立つ。
・yから共通鍵を作成し，共通鍵暗号でメッセージM’を復号してMを得る。

課題は，自然数 m1，m2 （m1≠m2）を安全性を保ちながらどれだけ小さくできるかです。

「ElGamal暗号の復号の高速化法」が実際に動作することを確認するための十進BASICでのコードと出力結果を示します。この復号の高速化法は，チェビシェフ多項式型公開鍵暗号にも適用できます。

!Chebyshev多項式暗号
LET p=8423 !安全素数
LET q=7823
LET a=27246964 !公開鍵
LET a1=MOD(a,p)
LET a2=MOD(a,q)
LET m1=55 !秘密の乱数
LET m2=77

LET b1=Chebyshev(a1,m1,p)
LET b2=Chebyshev(a2,m2,q)
LET b=Chinese(b1,b2,p,q) !公開鍵を作成

LET m=Chinese(m1,m2,p-1,q-1) !周期から指数を求める。これで求まらない場合もある。
PRINT m
PRINT Chebyshev(a,m,p*q),b !一致を確認

LET n=123456 !秘密の乱数
LET c=Chebyshev(a,n,p*q)
LET d=Chebyshev(b,n,p*q)

LET x1=Chebyshev(MOD(c,p),m1,p)
LET x2=Chebyshev(MOD(c,q),m2,q)
LET x=Chinese(x1,x2,p,q)

PRINT d,x !一致を確認

END

EXTERNAL FUNCTION ruijyou(a,r,N) !累乗の計算
LET s=1
FOR i=1 TO r
   LET s=MOD(s*a,N)
NEXT I
LET ruijyou=s
END function

EXTERNAL FUNCTION Chebyshev(k,r,N) !漸化式の第r項の計算
LET s=2
LET t=k
FOR i=2 TO r
   LET x=MOD(k*t-s,N)
   LET s=t
   LET t=x
NEXT I
LET Chebyshev=t
END function

EXTERNAL FUNCTION Chinese(a1,a2,p,q) !中国人剰余定理
CALL ExGCD(p,q,s,t,c)
LET x=a1*t*q+a2*s*p
LET Chinese=MOD(x/c,p*q/c)
End function

EXTERNAL SUB ExGCD(a,b,s,t,c) !拡張ユークリッドの互除法（再帰版）
IF b=0 THEN
   LET s=1
   LET t=0
   LET c=a
ELSE
   LET q=INT(a/b)
   LET r=MOD(a,b)
   CALL ExGCD(b,r,s1,t1,c)
   LET s=t1
   LET t=s1-t1*q
END IF
END SUB

32829011
57600579                57600579
22400245                22400245

最初のページに戻る