(57)【要約】【課題】高速な暗号方式における超楕円曲線のスカラー倍演算装置を提供する。【解決手段】超楕円曲線に付随するヤコビ多様体の元Dのスカラー倍を計算する際に、事前計算において、独立に計算できる2つの計算を1組にして、それぞれの計算に1回ずつ含まれる逆元計算をモンゴメリートリックを用いて削減し、内部的に計算する必要のある整数k(=2s+h(h,sは整数))倍を[k]D=[2s]D+[h]Dを計算するのではなく[k]D=[2s-1]D+([2s-1]D+[h]D)を計算することにより2倍算を加算に置き換える、という2つの改良を行うことにより定義体上の乗算及び逆元計算回数を削減を行い、種数2の超楕円曲線に最適なスカラー倍演算装置を構成する。【選択図】図３
2004205869.tif 000002
【特許請求の範囲】
【請求項１】
超楕円曲線スカラー倍演算装置であって、
演算対象となる超楕円曲線および演算対象データの入力を受け付ける入力部と、
超楕円曲線の情報を保持する超楕円曲線情報保持部と、
演算対象データを保持する演算対象データ保持部と、
加算演算部および2倍算演算部を備え、スカラー倍演算方法を行うスカラー倍演算部と、
演算結果を保持する演算結果保持部と、
演算結果を出力する出力部を備える超楕円曲線スカラー倍演算装置。
【請求項２】
請求項1記載の超楕円曲線スカラー倍演算装置であって、
有限体上定義される種数2の超楕円曲線に付随するヤコビ多様体上のスカラー倍を高速に計算することを特徴とする超楕円曲線スカラー倍演算装置。
【請求項３】
請求項1記載の超楕円曲線スカラー倍演算装置であって、
超楕円曲線に付随するヤコビ多様体の元Dに対して、
D,3[D],[5]D,[7]D,[9]D,[11]D,[13]D,[15]D
を事前計算することを特徴とする超楕円曲線スカラー倍演算装置。
【請求項４】
請求項1記載の超楕円曲線スカラー倍演算装置であって、
事前計算において独立に計算できる2つの演算に対して、モンゴメリートリックを適用することにより定義体上の逆元計算回数を削減することを特徴とする超楕円曲線スカラー倍演算装置。
【請求項５】
請求項1記載の超楕円曲線スカラー倍演算装置であって、
超楕円曲線に付随するヤコビ多様体の元Dのスカラー倍を計算する際に、
整数k(=2s+h(h,sは整数))倍を
[k]D=[2s-1]D+([2s-1]D+[h]D)
を計算することにより求めることを特徴とする超楕円曲線スカラー倍演算装置。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
この発明は情報セキュリティ技術としての暗号技術に関するものであり、特に、有限体上の種数2の超楕円曲線を用いて実現する暗号及びデジタル署名技術において必要なスカラー倍演算装置に関するものである。
【０００２】
【従来の技術】
非特許文献1には、より高い安全性が期待できる暗号化方法として超楕円曲線に付随するヤコビ多様体の離散対数問題に基づく暗号化及び復号化装置が提案されている。
【０００３】
有限体Fq上の超楕円曲線とは、方程式y2+h(x)y=f(x)を満たす点(x,y)の集合として定義される。ただし、f(x)は有限体Fq上のモニックな2g+1次多項式、h(x)は有限体Fq上のg次以下の多項式、またgを超楕円曲線の種数と呼ぶ。
【０００４】
超楕円曲線上の因子は超楕円曲線C上の点Piの形式和D=ΣnPPiを用いて表すことができる。ここでnPは整数でいくつかのnPは0であるとする。
【０００５】
次に-P=(x,-y)をP=(x,y)の共役と呼ぶ。互いに共役となる点を含まない因子を半被約因子と呼び、k=ΣnPを因子の重みと呼ぶ。半被約因子の内
k≦gであるものを被約因子と呼ぶ。超楕円曲線Cに付随するヤコビ多様体JC(Fq) とは、被約因子の集合で, 被約因子に対して後述する加算演算および単位元を定義することにより群構造を与えることができる。
【０００６】
また、因子の表現方法として多項式のペアを用いる方法が知られている。非特許文献2によると、任意の因子D=ΣnPPは以下の条件を満たす2つの有限体Fq上の多項式a,bを用いて表すことができる。
(1)  a:モニック多項式
(2)  deg(b)<deg(a)
(3)  b2+hb≡f mod a
またDが被約因子である場合は条件(2)がdeg(b)<deg(a)≦gに置き換わる。これ以後、因子DをFq上の多項式の組(a,b)を用いて表す。このとき、ヤコビ多様体JC(Fq)の単位元Oは(1,0)と表される。
【０００７】
超楕円曲線上の因子に対しては加算及び2倍算が定義できる。
【０００８】
超楕円を種数2の曲線y2=x5+Ax4+Bx3+Cx2+Dx+E
（A,B,C,D,E∈Fq(qは3以上の素数pの冪)）に制限した場合の加算および2倍算アルゴリズムは、非特許文献3に詳しく述べられている。
【０００９】
以下、文献3に基づき、最も一般的な因子の組合せに対する加算アルゴリズムの概略を示す。
【００１０】
入力: 重みが2の被約因子D1=(a1,b1),D2=(a2,b2)
出力: 被約因子D3=(a3,b3)=D1+D2
ただし、ai=x2+six+ti,bi=uix+vi,
(si,ti,ui,vi∈Fq),a1,a2は共通因子を持たず、
b1,≠-b2, b1≠0,b2≠0を満たしているとする。
【００１１】
ステップ1: rを計算する。
【００１２】
ステップ2: I≡r/a1 mod a2 を計算する。
【００１３】
ステップ3: H≡(b2-b1)I mod a2を計算する。
【００１４】
ステップ4: 中間データの計算
α1=1/rh1,α2=rα,α3=h12α1 β=rα2,γ=β2をそれぞれ計算する。
【００１５】
ステップ5: Hをモニック化する。
【００１６】
ステップ6: J=Ha1を計算する。
【００１７】
ステップ7:
a3=(H(J+2βb1))/a2-γ(f-b12)/a1a2を計算する。
【００１８】
ステップ9: b3≡-(α3J+b1) mod a3を計算する。
【００１９】
上記アルゴリズムの演算コストは非特許文献3によると有限体Fq上の逆元計算のコストをI、乗算の計算コストをMとした場合1I+25Mとなる。
【００２０】
次に非特許文献3による、2倍演算方法を示す。
【００２１】
入力: 重みが2の被約因子D1=(a1,b1)、ただしgcd(a1,b1)=1.
出力: 被約因子D3=(a3,b3)=2D1
ステップ1: rを計算する。
【００２２】
ステップ2: I≡2rb1 mod a1を計算する。
【００２３】
ステップ3: H≡(f-b12)/a1 mod a1を計算する。
【００２４】
ステップ4: J≡IH mod a1の計算
ステップ5: 演算法の選択する。
【００２５】
Jの1次の係数j1が0であればステップ11に進み、そうでなければステップ6に進む。
【００２６】
ステップ6: 中間データを計算する。
【００２７】
α1=1/2(rj1),α2=2rα1,α3=j12α1,
β=j12α1,γ=β2をそれぞれ計算する。
【００２８】
ステップ7: Jをモニック化する。
【００２９】
ステップ8: K=Ja1を計算する。
【００３０】
ステップ9: a3=((Ja1+βb1)2-f)/a12を計算する。
【００３１】
ステップ10: b3≡-(α3K+b1) mod a3を計算し、ステップ14に進む。
【００３２】
ステップ11: K=J/(2r)を計算する。
【００３３】
ステップ12: a3を計算する。
ステップ13: b3を計算し、ステップ14に進む。
【００３４】
ステップ14: D3=(a3,b3)を出力する。
【００３５】
2倍算アルゴリズムの計算コストは1I+29M,種数2の超楕円曲線をy2=x5+Bx3+Cx2+Dx+Eに制限した場合1I+27Mとなる。
【００３６】
また、上記アルゴリズムは非特許文献4において標数2の場合に拡張されている。
【００３７】
この場合の最も一般的な因子の組に対する演算コストは、標数3以上の場合と同じく加算
1I+25M,2倍算1I+27Mである。
【００３８】
有限体Fq上で定義された超楕円曲線の離散対数問題とは、超楕円曲線に付随するヤコビ多様体JC(Fq)の位数が大きな素数で割り切れる場合にヤコビ多様体JC(Fq)に含まれる元D0をベースポイントとする。このとき、ヤコビ多様体JC(Fq)に含まれる元をD1に対して、
D1=[k]D0=D0+D0+…+Do(k回加算)
となる整数kが存在するならば、kを求めよという問題である。
【００３９】
暗号の安全性は多くの元を有するヤコビ多様体に対して上記問題が非常に難しいことに依存する。
【００４０】
次に上記超楕円曲線に付随するヤコビ多様体上の離散対数問題を応用した暗号化方式をまず述べる。
(1)  鍵生成
入力:超楕円曲線C,ベースポイントD0,D0の位数n
出力:鍵ペア(ds,Dp)
ステップ1: ランダムに1<d<nを満たすdsを選択し秘密鍵とする。
【００４１】
ステップ2: Dp=[ds]D0を計算し公開鍵とする。
【００４２】
ステップ3: 鍵ペア(ds,Dp)を出力する。
(2)  暗号化
入力: 超楕円曲線C,ベースポイントD,Dの位数n,公開鍵Dp,平文m
出力: 暗号文(C1,C2)
ステップ1: ランダムに1<r<nを満たすrを選択する。
【００４３】
ステップ2: C1=[r]D0を計算する。
【００４４】
ステップ3: C2=m+[r]Dpを計算する。
【００４５】
ステップ4: 暗号文(C1,C2)を出力する。
(3)  復号化
入力: 超楕円曲線C,ベースポイントD,Dの位数n,秘密鍵ds,
暗号文(C1,C2)
出力: 復号文m
ステップ1: m=C2-[ds]C1を計算する。
【００４６】
ステップ2: mを復号文として出力する。
【００４７】
上記従来例でわかるように、超楕円曲線を用いた暗号化方式では、固定点および任意点のスカラー倍演算が必要である。
【００４８】
上記k倍演算は加算演算、2倍演算を組み合わせることにより非特許文献5で示されている以下の方法で計算できる。
【００４９】
従来例1
入力: 被約因子D0,
整数k=k0+k1m+…+kd-1md-1,kj∈{0,1,…,m-1}
(0≦j≦d-1),m=2r.
出力: D1=[k]D0
ステップ1: 事前計算
ステップ1.1: D[1]=D0,D[2]=[2]D0とおく。
【００５０】
ステップ1.2: iが1から(m-2)までD[2i+1]=D[2i-1]+D[2]を計算する。
【００５１】
ステップ1.3: D1=(1,0)(=無限遠点)とおく。
【００５２】
ステップ2: メインループ
ステップ2.1: j=d-1とおく。
【００５３】
ステップ2.2: kj≠0であればステップ2.3に進み、そうでなければステップ2.6に進む。
【００５４】
ステップ2.3: kj=2shを満たす整数sと奇数hを求める。
ステップ2.4: r-s回の2倍算を行い
D1=[2r-s]D1を計算する。
【００５５】
ステップ2.5: D1=D1+D[h]を計算しステップ2.7に進む。
【００５６】
ステップ2.6: s=rとおく。
【００５７】
ステップ2.7: D1=[2s]D1を計算する。
【００５８】
ステップ2.8: j=j-1を計算する。
【００５９】
ステップ2.9: j≠-1であればステップ2.2に戻りj=-1であればステップ2.10に進む。
【００６０】
ステップ2.10: 演算結果としてD1を出力する。
【００６１】
楕円曲線を用いた場合、上記アルゴリズムの事前計算ステップの高速計算法が以下に示す非特許文献6に示されている。
【００６２】
このアルゴリズムは、楕円曲線上の加算及び2倍算にそれぞれ1回ずつ含まれる逆元計算の回数をモンゴメリートリックを用いて削減することにより高速化を図るものである。
【００６３】
最初にモンゴメリトリックの説明を非特許文献7に基づき行う。
【００６４】
モンゴメリートリック
入力: a1,a2,…,an
出力: a1,a2,…,anの逆元 a1-1,a2-1,…,an-1
ステップ1: c1=a1おく。
【００６５】
ステップ2: iが2からnまでステップ2.1を繰り返す。
【００６６】
ステップ2.1: ci=ci-1aiを計算する。
【００６７】
ステップ3: u=cn-1を計算する。
【００６８】
ステップ4: i=nとおきi<0となるまで以下のステップを繰り返す。
【００６９】
ステップ4.1: ai-1=ci-1uを計算する。
【００７０】
ステップ4.2: u=uaiを計算する。
【００７１】
ステップ4.3: i=i-2を計算する。
【００７２】
ステップ5: a1-1=uを計算する。
【００７３】
ステップ6: a1-1,a2-1,…,an-1を出力する。
【００７４】
モンゴメリートリックの計算コストは
1I+(3n-3)Mで、一般的に1Iは30M程度に相当することが知られているため、n回逆元計算することに比べて大幅な高速化が達成できる。
【００７５】
次に、Affine座標を用いた楕円曲線上の加算及び2倍算にそれぞれ1回ずつ逆元計算が用いられることを利用した高速事前計算法を非特許文献6に基づき示す。
【００７６】
従来例2: 高速事前計算法
入力: 楕円曲線上の点P,m=2r.
出力: P,[2]P,[3]P,[5]P,…,[m-3]P,[m-1]P.
ステップ1: [2]Pを計算する。
【００７７】
ステップ2: i=1からi=r-2までステップ2.1および2.2を繰り返す。
【００７８】
ステップ2.1: ([2i+1]P,[2i+3]P,…,
([2i+1-1]P,([2i+1]P)をモンゴメリートリックを用いることにより1回の逆元計算で計算する。計算方法はまずi=1の場合に、P+[2]P,[2][2]Pの計算がそれぞれ独立に計算できることを利用して、それぞれに1回ずつ含まれる逆元計算をモンゴメリートリックを用いて1回にまとめることにより([3]P,[4]P)の計算を行う。i=2のステップでは、i=1の場合と同様に([5]P,[7]P,[8]P)をP+[4]P,[3]P+[4]P,[2][4]P)を計算することにより逆元計算1回で求める。以下、各Iごとに同様の計算を繰り返す。
【００７９】
ステップ2.2: i=i+1を計算する。
【００８０】
ステップ3: ステップ2.1と同様の手法を用いて([2r-1+1]P,
[2r-1+3]P,…,[2r-1]P)を計算する。
【００８１】
ステップ4:
P,[2]P,[3]P,[5]P,…,[m-3]P,[m-1]Pを出力する。
【００８２】
以上の高速事前計算法は超楕円曲線においても加算及び2倍算において逆元計算が1回含まれるため適用可能である。
【００８３】
【非特許文献１】
Neal Koblitz, 「Neal Koblitz, Hyperelliptic Crypto Systems」,1989年, J.Crypto, 1989, p139-150
【非特許文献２】
D.Mumford, 「Tate lectures on theta II」,Birkhauser, 1984年, volume 43 of Progr.Math.
【非特許文献３】
高橋昌史, 「種数2の超楕円曲線の改良について」 2002年,Proc of SCIS2002 Vol1,p155-160
【非特許文献４】
杉崎大樹、松尾和人、趙晋輝、辻井重男、「標数2の有限体上の超楕円曲線に対するHarley加算アルゴリズムの拡張」、電子情報通信学会2002年 ISEC-2002-9, p49-56
【非特許文献５】
I. Blake G. Seroussi and N. Smart, 「Elliptic Curvesin Cryptography」, Canbridge U.P, 1998年London Mathematical Society Lecture Note Series, no.265
【非特許文献６】
H.Cohen, A.Miyaji and T.Ono, 「Efficient elliptic curve exponentiation using mixed coordinates」, Springer-Verlag, 1998年, Proceedings Asiacrypt'98, Lecture Notes in Computer Science 1514, p51-65
【非特許文献７】
H.Cohen, 「A course in computational algebraic number theory」, Springer-Verlag, 1993年, GTM 138
【００８４】
【発明が解決しようとする課題】
超楕円曲線を用いた暗号方式では、スカラー倍演算を行う演算装置が必須である。特に任意点のスカラー倍演算は、暗号処理において負荷が大きいため、これを高速に行う必要がある。
【００８５】
スカラー倍演算は加算と2倍算の組合せで構成される。加算と2倍算の組合せには自由度があり、例えばDの9倍を考えると
(1)  [9]D=[8]D+D
(2)  [9]D=[4]D+([4]D+D)
(3)  [9]D=[3]D+[2]([3]D)
などの計算方法が考えられる。
【００８６】
次に総演算回数を考えると(1)の場合[8(=23)]Dの計算は2倍算3回で行えるため加算1回と2倍算3回の計4回,(2)の場合は加算2回と2倍算2回の計4回、(3)の場合は加算2回と2倍算2回の計4回となり総演算数が同じでも、中で行われる加算及び2倍算の回数は異なる。このため、加算と2倍算の間に処理時間の差がある場合、処理時間が短い演算が多く現れる計算方法を用いることによりスカラー倍演算を行うことができる。
【００８７】
従来例1のスカラー倍演算法は主に楕円曲線上の点のスカラー倍演算の高速化を目的に作られている。楕円曲線暗号を構成する上で最も一般的に使われている射影座標上の加算及び2倍算は加算が16M(標数3以上)または20M(標数2),2倍算が10Mと加算に比べて2倍算が高速である。このためスカラー倍演算を行う場合、加算と2倍算の回数の総数が同じアルゴリズムを用いるとするならば、2倍算の回数が多いアルゴリズムを用いるほうがスカラー倍演算は高速に実現できる。
【００８８】
しかし、種数2の超楕円曲線上の因子の加算および2倍算のように加算アルゴリズムの方が高速である場合は加算および2倍算の総数が同じであれば、より多く加算を用いるアルゴリズムを用いることが望ましい。
【００８９】
また、従来例2で示した高速事前計算法についても、本来の事前計算では必要のない4倍,8倍,…,2r-1倍の計算が必要となるという問題がある。Affine座標を用いた楕円曲線の場合は加算が1I+3M,2倍算が1I+4Mと逆元計算以外の演算の比率が小さいため無駄な点を計算したとしても、逆元計算削減の効果の方が大きいが種数2の超楕円曲線の場合、逆元以外の計算の負荷も大きいため、そのまま適応するのでは高速化の効果を得ることはできない。
【００９０】
【課題を解決するための手段】
本発明は、種数2の超楕円曲線上の演算の場合等、加算が2倍算に比べて高速である場合において、できる限り2倍算の代わりに加算を用いることにより、スカラー倍算の処理時間の短縮を行う。
【００９１】
具体的には整数kが2s+h(h,sは整数)と表されている場合、Dのk倍を従来例に基づき[k]D=[2s]D+[h]Dを計算するのでなく
[k]D=[2s-1]D+([2s-1]D+[h]D)を計算することにより2倍算の回数を削減できることをうまく用いて、2倍算演算回数の少ないスカラー倍演算装置を構成する。また、事前計算方法を改良し従来例に比べて無駄な点の計算回数の少ない、より高速な事前計算を行う。これらの改良により高速な暗号装置を提供する。
【００９２】
より具体的には、本発明は、超楕円曲線スカラー倍演算装置であって、演算対象となる超楕円曲線および演算対象データを入力する入力部と、超楕円曲線の情報を保持する超楕円曲線情報保持部と、演算対象データを保持する演算対象データ保持部と、スカラー倍演算方法を行うスカラー倍演算部と、スカラー倍演算部において内部的に用いられる加算演算部および2倍算演算部と、演算結果を保持する演算結果保持部と、演算結果を出力する出力部を備えることを特徴とする。
【００９３】
さらに、本発明は、有限体上定義される種数2の超楕円曲線に付随するヤコビ多様体上のスカラー倍を高速に計算することを特徴とする。
【００９４】
また、本発明は、超楕円曲線に付随するヤコビ多様体の元Dに対して,
D,3[D],[5]D,[7]D,[9]D,[11]D,[13]D,[15]Dを事前計算することを特徴とする。
【００９５】
また、本発明は、事前計算において独立に計算できる2つの演算に対してモンゴメリートリックを適用することにより定義体上の逆元計算回数を削減することを特徴とする。
【００９６】
また、本発明は、超楕円曲線に付随するヤコビ多様体の元Dのスカラー倍を計算する際に、内部的に計算する必要のある整数
k(=2s+h(h,sは整数))倍を
[k]D=[2s-1]D+([2s-1]D+[h]D)を計算することにより求めることを特徴とする。
【００９７】
【発明の実施の形態】
図1は本実施形態における超楕円曲線スカラー倍演算装置(以下演算装置)101の機能構成図である。演算装置101は、制御演算部102およびデータ保持部103から構成される。
【００９８】
制御演算部102は、種数2の超楕円曲線のパラメータ、定義体情報、ヤコビ多様体上の点D0及び整数kを入力し、演算結果として[k]D0を出力する入出力部104、超楕円曲線スカラー倍演算装置101全体を制御する制御部105、スカラ倍演算を行うスカラー倍演算部106、スカラー倍演算部106を構成する整数kを16進展開する16進展開部107、ヤコビ多様体の元の演算を行う超楕円曲線演算部108から構成される。さらに超楕円曲線演算部は加算部109および2倍算部110から構成される。
【００９９】
データ保持部103は入出力部104により入力された演算対象データであるヤコビ多様体の元D0および整数kを保持する演算対象データ保持部111、超楕円曲線のパラメータ、定義体情報を保持する超楕円曲線情報保持部112、スカラー倍演算を行う際の事前計算結果を保持する事前計算結果保持部113,スカラー倍演算部106で用いられる中間データを保持する中間データ保持部114、制御演算部102で計算された演算結果を保持する演算結果保持部115から構成される。次に各々の動作は制御部105により制御されているものとして動作の流れを説明する。
【０１００】
入出力部104により入力された演算対象データ、超楕円曲線パラメータ、定義体情報は演算対象データ保持部111、超楕円曲線情報保持部112に保持される。
【０１０１】
次にスカラー倍演算部106において演算対象データ保持部111、超楕円曲線情報保持部112で保持されている情報を用いて、事前計算を行う、事前計算結果は事前計算結果保持部113において保持される。次に事前計算結果保持部113において保持されている事前計算結果を用いてスカラー倍演算部106においてスカラー倍を行う。事前計算およびスカラー倍演算における中間演算結果は必要に応じて中間データ保持部114において保持される。スカラー倍演算は図2に示すフローチャートに従って行われるものとする。
【０１０２】
最後に超楕円曲線スカラー倍演算装置101は入出力装置104により種数2の超楕円曲線パラメータy2+h(x)y=f(x),定義体情報,演算結果[k]D0を出力する。
【０１０３】
上記の演算装置は,CPUとメモリと、ハードディスク装置やその他の外部記憶装置と、キーボードなどの入力装置と、ディスプレイなどの出力装置と、外部記憶装置や入出力装置とのインターフェースを備えた、一般的な構成を有する情報処理装置上に構築することができる。
【０１０４】
演算部102の各処理部104〜110は、CPUがメモリにロードされたプログラム(コードまたはモジュールともいう)を実行することで、情報処理装置上に具現化されるプロセスとして実現される。また、メモリや外部記憶装置がデータ保持部103の各保持部111〜115として使用される。
【０１０５】
上述した各プログラムは、予め外部記憶装置に記憶され、必要に応じてメモリ上にロードされ、CPUにより実行される。上記プログラムは、可搬性の記憶媒体、例えばCD-ROMを扱う外部記憶装置を解して、必要に応じて、可搬性の記憶媒体からメモリにロードされても良いし、一旦、外部記憶装置を介して、可搬性の記憶媒体から外部記憶装置から外部記憶装置にインストールされた後、必要に応じて、外部記憶装置からメモリにロードされても良いし、さらには、図示していないネットワーク接続装置を介して、ネットワーク上の情報処理装置が読み取り可能な媒体の一種である伝送信号により、一旦外部記憶装置にダウンロードされてからメモリにロードされても良いし、あるいは、直接、ネットワーク経由でメモリにロードされても良い。
【０１０６】
次に図2〜4を用いて本実施の形態及び動作を詳細に説明する。
【０１０７】
図2は図1において行われている処理を説明するフローチャートである。
【０１０８】
<ステップ201>
図2において定義体入力部201は超楕円曲線の情報として定義体となる有限体Fq及び種数2の超楕円曲線y2+h(x)y=f(x)を入力として受け付ける。
【０１０９】
ここで有限体Fqの情報は、
(1)素体の場合有限体の位数として3以上の素数q
(2)拡大体の場合はq=pnを満たす素数p（標数と呼ぶ）および拡大次数n。
【０１１０】
<ステップ202>
演算対象データであるヤコビ多様体の元D0=(a0,b0),整数kを入力する。
【０１１１】
ここでヤコビ多様体の元D0は種数2の超楕円曲線を
y2+h(x)y=f(x) (deg(f)=5,deg(h)≦2)とおいた場合
deg(bi)<deg(ai)≦2 (ai,bi∈Fq[x]) およ
びbi2+hbi≡f mod aiを満たす多項式の組
(ai,bi)で表されるものとする。
【０１１２】
<ステップ202>
kD0を計算する。
【０１１３】
<ステップ203>
演算結果D3=(a3,b3)を出力する。
【０１１４】
上記ステップ202を、図3に示すスカラー倍演算部107の動作説明フローチャートを用いて詳細に説明を行う。なおヤコビ多様体の元の加算および2倍算は文献1および2に従い計算を行う。
【０１１５】
(1) 事前計算
<ステップ301>
整数kをk0+k1m+…+kd-1md-1,
kj∈{0,1,…,m-1} (0≦j≦d-1),m=16の形で表現する。
【０１１６】
<ステップ302>
D[1]=D0,D[2]=[2]D0とおく。
【０１１７】
<ステップ303>
(D[3],D[4])=([3]D,[4]D)を[3]D=D+[2]D、[4]D=[2]D[2]を計算することにより求める。ただしそれぞれの計算で1回ずつ計算の必要のある逆元計算はモンゴメリートリックを用いて2回必要な逆元計算を1回に削減する。
【０１１８】
<ステップ304>
(D[5],D[7])=(D[3]+D[2],D[3]+D[4]),
(D[9],D[11])=(D[7]+D[2],D[7]+D[4]),
(D[13],D[15])=(D[11]+D[2],D[15]+D[4])
をそれぞれ計算する。なおそれぞれの組に対してステップ303で説明したモンゴメリートリックを利用した手法を適応することにより1組あたり1回の逆元計算で計算を行う。
【０１１９】
<ステップ305>
j=d-1,D1=(1,0)(=無限遠点)とおく。
【０１２０】
(2) メインループ
<ステップ306>
kj≠0であればステップ307に進み、そうでなければステップ311に進む。
【０１２１】
<ステップ307>
kj=2shを満たす整数sと奇数hを求める。
【０１２２】
<ステップ308>
4-s-1回の2倍算を行いD1=[24-s-1]D1を計算する。
【０１２３】
<ステップ309>
D2=D1+D[h]を計算する。
【０１２４】
<ステップ310>
D1=D1+D2を計算しステップ313に進む。
【０１２５】
<ステップ311>
s=4とおく。
【０１２６】
<ステップ312>
D1=[2s]D1を計算する。
【０１２７】
<ステップ313>
j=j-1を計算する。
【０１２８】
<ステップ314>
j≠-1であればステップ306に戻りj=-1であればステップ315に進む。
【０１２９】
<ステップ315>
演算結果としてD1を出力する。
【０１３０】
次に本実施形態における鍵生成装置について説明する。
【０１３１】
図4は鍵生成装置を示している。
【０１３２】
鍵生成装置401は、制御演算部402およびデータ保持部403から構成される。
【０１３３】
制御演算部402は、超楕円曲線
y2+h(x)y=f(x)、ベースポイントD0及びその位数n、定義体情報を入力し、生成された鍵情報を出力する入出力部404、鍵生成装置401全体を制御する制御部405、乱数を生成する乱数生成部406、ベースポイントの整数倍を計算する超楕円曲線スカラー倍演算部407から構成される。
【０１３４】
データ保持部403は入出力部により入力された超楕円曲線のパラメータ、ベースポイント及びその位数、定義体情報を保持する超楕円曲線情報保持部408、制御演算部で生成された鍵情報及び超楕円曲線の情報を保持する鍵情報保持部409から構成される。次に各々の動作は制御部405により制御されているものとして動作の流れを説明する。
【０１３５】
入出力部404により入力された超楕円曲線パラメータ、ベースポイントD0及びその位数n、定義体情報は超楕円曲線情報保持部408と鍵情報保持部409に保持される。
【０１３６】
次に乱数生成部406において0<ds<n(nはベースポイントD0の位数)を満たす乱数dsを生成しこれを秘密鍵として鍵情報保持部409で保持する。
【０１３７】
次に超楕円曲線スカラー倍演算部407においてベースポイントD0のds倍Dp=[ds]D0を超楕円曲線演算部を用いて計算し公開鍵とし鍵情報保持部409で保持する。
【０１３８】
最後に鍵発行装置401は入出力装置404により超楕円曲線y2+h(x)y=f(x),ベースポイントD0,D0の位数n,定義体情報,秘密鍵ds及び公開鍵Dpを出力する。
【０１３９】
次に本実施形態における暗号化装置について説明する。
【０１４０】
図5は暗号化装置を示している。
【０１４１】
暗号化装置501は、制御演算部502およびデータ保持部503から構成される。
【０１４２】
制御演算部502は、超楕円曲線情報を入力し、生成された暗号文を出力する入出力部504、暗号化装置501全体を制御する制御部505、暗号化処理を行う暗号処理部506、また暗号処理部は乱数を生成する乱数生成部507、ヤコビ多様体の元の整数倍を計算する超楕円曲線スカラー倍演算部508から構成される。
【０１４３】
データ保持部503は入出力部504により入力された暗号化の対象である平文情報を保持する平文情報保持部509、同様に入出力部により入力された種数2の超楕円曲線y2+h(x)y=f(x)、ベースポイントD0及びその位数n、定義体情報を保持する超楕円曲線情報保持部510、暗号化に用いる公開鍵を保持する鍵情報保持部511、制御演算部で生成された暗号文を保持する暗号文保持部512から構成される。次に各々の動作は制御部505により制御されているものとして動作の流れを説明する。
【０１４４】
入出力部504により入力された平文情報は平文情報保持部509に保持される。
【０１４５】
入出力部504により入力された超楕円曲線、ベースポイント及びその位数、定義体情報は超楕円曲線情報保持部510に保持される。
【０１４６】
入出力部504により入力された公開鍵情報は公開鍵情報保持部512に保持される。
【０１４７】
次に暗号化処理部506において平文情報保持部509、超楕円曲線情報保持部510、公開鍵情報保持部511で保持されている情報を用いて暗号化処理を行い暗号文を作成する。暗号化処理は図6に示すフローチャートに従って行われるものとする。
【０１４８】
最後に暗号化処理部506で作成された暗号文を暗号文情報保持部512に保持するとともに入出力部504より出力する。
【０１４９】
次の図6は図5の暗号処理部506で行われる暗号化処理のフローチャートを示す。以下公開鍵をDp,ヤコビ多様体のベースポイントを
D0,その位数をnとして説明を行う。
【０１５０】
<ステップ601>
0<r<nを満たす乱数rを選択する。
【０１５１】
<ステップ602>
暗号化対象の平文をmとしてC1=[r]D0及び
C2=[r]Dp+mを計算する。
【０１５２】
<ステップ603>
(C1,C2)を暗号文として出力する。
【０１５３】
次に本実施形態における復号化装置について説明する。
【０１５４】
図7は復号化装置を示している。
【０１５５】
復号化装置701は、制御演算部702およびデータ保持部703から構成される。
【０１５６】
制御演算部702は、超楕円曲線情報及び復号化対象の暗号文を入力し、復号された平文を出力する入出力部704、復号化装置701全体を制御する制御部705、復号化処理を行う復号処理部706、また復号処理部はヤコビ多様体の元の整数倍を計算する超楕円曲線スカラー倍演算部707から構成される。
【０１５７】
データ保持部703は入出力部704により入力された復号化の対象である暗号文情報を保持する暗号文情報保持部708、同様に入出力部704により入力された超楕円曲線y2+h(x)y=f(x)、ベースポイントD0及びその位数n、定義体情報を保持する超楕円曲線情報保持部709、復号化に用いる秘密鍵を保持する秘密鍵情報保持部710、復号化処理部706で復号された平文を保持する平文情報保持部711から構成される。次に各々の動作は制御部705により制御されているものとして動作の流れを説明する。
【０１５８】
入出力部704により入力された暗号文情報は暗号文情報保持部708に保持される。
【０１５９】
入出力部704により入力された超楕円曲線パラメータ、ベースポイント及びその位数、定義体情報は超楕円曲線情報保持部709に保持される。
【０１６０】
入出力部704により入力された秘密鍵情報は秘密鍵情報保持部710に保持される。
【０１６１】
次に復号化処理部において暗号文情報保持部708、超楕円曲線情報保持部709、秘密鍵情報保持部710で保持されている情報を用いて復号化処理を行い復号文を作成する。復号化処理は図8に示すフローチャートに従って行われるものとする。
【０１６２】
最後に復号化処理部706で復号された平文を平文情報保持部711に保持するとともに入出力部704より出力する。
【０１６３】
次の図8は図7の復号処理部706で行われる復号化処理のフローチャートを示す。以下秘密鍵をds,復号化対象の暗号文を(C1,C2)として説明を行う。
【０１６４】
<ステップ801>
暗号文(C1,C2)およびxから、m=C2-[ds]C1を計算する。
【０１６５】
<ステップ802>
mを平文として出力する。
【０１６６】
以上、説明を行ったように本実施形態では、超楕円曲線に付随するヤコビ多様体の元Dのスカラー倍を計算する際に、
(1)  事前計算において、独立に計算できる2つの計算を1組にして、それぞれの計算に1つ含まれる逆元計算をモンゴメリートリックを用いて削減する。
(2)  内部的に計算する必要のある整数
k(=2s+h(h,sは整数))倍を
[k]D=[2s]D+[h]Dを計算するのではなく
[k]D=[2s-1]D+([2s-1]D+[h]D)を計算することにより2倍算を加算に置き換える。
【０１６７】
の2つの改良を行うことにより定義体上の乗算及び逆元計算回数を削減を行った。
【０１６８】
次に、以上の工夫の具体的効果を示す。定義体上の乗算コストをM,逆元計算コストをIとした場合において、(1)を適用した事前計算の演算コストは、5I+239Mとなる。一般的には1Iは30M程度であるため、演算コストは389M程度となる。同様に従来例の事前計算部分の演算コストは442M,従来例2の高速事前計算法の演算法の演算コストは492Mとなり、従来例に比べて高速であることが示される。
【０１６９】
(2)の効果については、種数2の超楕円曲線に付随するヤコビ多様体の元Dのk倍を考えた場合、kがKビットとすれば従来例に比べて最大K/4-1回の2倍算を加算に置き換えることが可能になり、例えば種数2の超楕円曲線の場合、定義体上の乗算を最大K/2-2回削減できる。
【０１７０】
【発明の効果】
本発明により高速な暗号方式を可能にする超楕円曲線暗号装置を提供できる。
【図面の簡単な説明】
【図１】本実施例のシステム機能構成図である。
【図２】本実施例の動作説明フローチャートである。
【図３】本実施例によるヤコビ多様体上のスカラー倍演算動作説明フローチャートである。
【図４】本実施例を用いた鍵生成装置の構成図である。
【図５】本実施例を用いた暗号化装置の構成図である。
【図６】本実施例を用いた暗号化装置の動作説明フローチャートである。
【図７】本実施例を用いた復号化装置の構成図である。
【図８】本実施例を用いた復号化装置の動作説明フローチャートである。
【符号の説明】
101:超楕円曲線スカラー倍演算装置、102:制御演算部、103:データ保持部、104:入出力部、105:制御部、106:スカラー倍演算部、107:16進展開部、108:超楕円曲線演算部、109:加算演算部、110:2倍算演算部、111:演算対象データ保持部、112:超楕円曲線情報保持部、113:事前計算データ保持部、114:中間データ保持部、115:演算結果保持部、401:鍵生成装置、402:制御演算部、403:データ保持部、404:入出力部、405:制御部、406:乱数生成部、407:超楕円曲線スカラー倍演算部、408:超楕円曲線情報保持部、409:鍵情報保持部、501:暗号化装置、502:制御演算部、503:データ保持部、504:入出力部、505:制御部、506:暗号処理部、507:乱数処理部、508:超楕円曲線スカラー倍演算部、509:平文情報保持部、510:超楕円曲線情報保持部、512:公開鍵情報保持部、513:暗号文情報保持部、701:復号化装置、702:制御演算部、703:データ保持部、704:入出力部、705:制御部、706:復号処理部、707:超楕円曲線スカラー倍演算部、708:暗号文情報保持部、709:超楕円曲線情報保持部、710:公開鍵情報保持部、711:平文情報保持部。
【図１】
2004205869.tif 000003
【図２】
2004205869.tif 000004
【図３】
2004205869.tif 000005
【図４】
2004205869.tif 000006
【図５】
2004205869.tif 000007
【図６】
2004205869.tif 000008
【図７】
2004205869.tif 000009
【図８】
2004205869.tif 000010