(57)【要約】【課題】楕円曲線暗号のペアリング計算を高速で行う。【解決手段】図３のペアリング演算のプログラムにおいて、関数ＴＤＢＬを定義して、楕円２倍算の計算過程で得られる値を用いてペアリング演算における直線ｌ１，ｌ２の方程式の係数の計算を行う。また、関数ＴＡＤＤを定義して、楕円加算の計算過程で得られる値を用いてペアリング演算の直線ｌ１，ｌ２の方程式の係数の計算を行う。【選択図】      図３
2004177673.tif 000002
【特許請求の範囲】
【請求項１】
楕円曲線上の点に対するペアリングを用いた暗号を処理するペアリング暗号装置において、
有限体上の楕円曲線と、楕円曲線上の点を記憶する記憶手段と、
楕円２倍算または楕円加算の計算過程で得られる値を記憶し、記憶してある値を用いてペアリング演算の直線の方程式の係数を計算する演算手段とを備えるペアリング暗号装置
【請求項２】
楕円曲線上の点に対するペアリングを用いた暗号を処理するペアリング暗号装置において、
有限体上の楕円曲線と、楕円曲線上の点を記憶する記憶手段と、
ペアリング演算の中間計算に用いられる直線の方程式を展開した式の一部の計算結果を記憶しておき、記憶してある計算結果を用いて直線の方程式の計算を行う演算手段とを備えるペアリング暗号装置。
【請求項３】
前記演算手段は、有限体上の４つの要素（Ｘ：Ｙ：Ｚ：Ｚ＾２）（＾：べき乗を表す）の組で１つの点の座標を表した簡約座標を用いてペアリング演算の計算を行う請求項１または２記載のペアリング暗号装置。
【請求項４】
前記演算手段は、楕円曲線上の点Ｑ＋Ｓの座標を（ｘＱＳ，ｙＱＳ）、点Ｓの座標を（ｘＳ，ｙＳ）、楕円曲線上の点Ｔと点Ｐを結ぶ直線の方程式をｌ１、点Ｔ＋Ｐを通るｘ軸に垂直な直線の方程式をｌ２としたときに、ｘＱＳ×ｘＳと、ｙＱＳ×ｘＳの値を事前に計算して記憶しておき、記憶してあるｘＱＳ×ｘＳと、ｙＱＳ×ｘＳの値を用いて、ペアリング演算のｌ１（Ｑ＋Ｓ）×ｌ２（Ｓ）／（ｌ１（Ｓ）×ｌ２（Ｑ＋Ｓ））の計算を行う請求項１，２または３記載のペアリング暗号装置。
【請求項５】
楕円曲線上の点に対するペアリングを用いた暗号の演算プログラムであって、
有限体上の楕円曲線と、楕円曲線上の点を記憶手段に記憶させ、
ペアリング演算の中間計算に用いられる直線の方程式を展開した式の一部の計算結果を保持しておき、保持した計算結果を用いてペアリング演算の計算を演算手段に実行させるペアリング暗号演算プログラム。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、楕円曲線上のペアリング暗号装置、ペアリング暗号計算方法及びそのプログラムに関する。
【０００２】
【従来の技術】
楕円曲線上のペアリングを用いた暗号（以下、ペアリング暗号）は公開鍵暗号の１つであり、秘密共有、署名、認証などの暗号プリミティブから構成されている。これらプリミティブにおいて、楕円曲線上のペアリングと呼ばれる演算は共通して使用され、かつ暗号処理の中心となる。このことから、ペアリング暗号を実装する上で、ペアリング演算の高速化を実現する技術は必要不可欠である。
【０００３】
ペアリング暗号の例として、大岸・境・笠原による秘密共有プリミティブに関する文献１を参照して説明する。
センターは楕円曲線Ｅを定めて公開するとともに、センターの秘密鍵としてスカラーｓ（ｓは整数）を定める。ユーザーＡはセンターに個人情報ＰＡ（ＰＡは楕円曲線Ｅ上の点）を登録し、秘密鍵ＱＡ＝ｓ×ＰＡ（ＱＡは楕円曲線Ｅ上の点）を秘密裏に受け取る。同様に、ユーザーＢはセンターに個人情報ＰＢ（ＰＢは楕円曲線Ｅ上の点）を登録し、秘密鍵ＱＢ＝ｓ×ＰＢ（ＱＢは楕円曲線Ｅ上の点）を秘密裏に受け取る。個人情報はすべてのユーザーに公開される。ユーザーＡとユーザーＢが秘密共有を行う場合、ユーザーＡはユーザーＢとの共有情報ＫＡＢを、
ＫＡＢ＝（ＱＡ，ＰＢ）＋（ＰＢ，ＱＡ）
＝（ｓ×ＰＡ，ＰＢ）＋（ＰＢ，ｓ×ＰＡ）
＝（ＰＡ，ＰＢ）＾ｓ＋（ＰＢ，ＰＡ）＾ｓ
によって求める。ここで（Ｐ，Ｑ）は点Ｐと点Ｑのペアリングを表す。また＾はべき乗を表す。ユーザーＢはユーザーＡとの共有情報ＫＢＡを、
ＫＢＡ＝（ＱＢ，ＰＡ）＋（ＰＡ，ＱＢ）
＝（ｓ×ＰＢ，ＰＡ）＋（ＰＡ，ｓ×ＰＢ）
＝（ＰＢ，ＰＡ）＾ｓ＋（ＰＡ，ＰＢ）＾ｓ
によって求める。このときＫＡＢ＝ＫＢＡとなることから、ユーザーＡとユーザーＢの間で秘密情報が共有されたことになる。このようにして大岸・境・笠原方式によるペアリング暗号は秘密共有を行う。
【０００４】
ペアリング暗号では楕円曲線上のペアリングと呼ばれる演算を使用する。以下、楕円曲線について説明する。
ｐを５以上の素数、ｍを１以上の整数とすると、要素数ｑ＝ｐ＾ｍの有限体ＧＦ（ｑ）上の楕円曲線とは、方程式
Ｅ：ｙ＾２＝ｘ＾３＋ａ×ｘ＋ｂ
を満たす点（ｘ，ｙ）の集合上に、無限遠点と呼ばれる点∞を加えた集合のことをいう。無限遠点∞を０と表すこともある。ここでａ，ｂ，ｘ，ｙは有限体ＧＦ（ｑ）の要素である。楕円曲線上の点は（ｘ，ｙ）のような座標形式（アファイン座標）で表現できるが、無限遠点∞は（ｘ，ｙ）のような座標形式で表現することができない唯一の点である。このように、アファイン座標では無限遠点以外の点はＧＦ（ｑ）の２つの要素の組として表される。
【０００５】
楕円曲線Ｅ上の点の間には、以下のようにして点の加算と呼ばれる演算が定義できる。
ＰをＧＦ（ｑ）上の楕円曲線Ｅ上の点とする。以下のようにＰの逆元−Ｐを定義する。
【０００６】
（１）Ｐ＝∞ならば−Ｐ＝∞
（２）Ｐ≠∞ならばＰ＝（ｘ，ｙ）としたときに、−Ｐ＝（ｘ，−ｙ）
Ｐ１，Ｐ２をＧＦ（ｑ）上の楕円曲線Ｅ上の２点とする。以下のようにしてＰ１とＰ２の和Ｐ３＝Ｐ１＋Ｐ２を定義する。
【０００７】
（１）Ｐ１＝∞ならばＰ３＝Ｐ２
（２）Ｐ２＝∞ならばＰ３＝Ｐ１
（３）Ｐ１＝−Ｐ２ならばＰ３＝∞
（４）Ｐ１≠−Ｐ２ならばＰ１＝（ｘ１，ｙ１），Ｐ２＝（ｘ２，ｙ２），
Ｐ３＝（ｘ３，ｙ３）としたときに、
ｘ３＝λ＾２−ｘ１−ｘ２，      ｙ３＝−λ×ｘ３−ν，
ただし
λ＝（ｙ２−ｙ１）／（ｘ２−ｘ１），ν＝（ｙ１×ｘ２−ｙ２×ｘ１）／（ｘ２−ｘ１）・・・・・・：Ｐ１≠Ｐ２のとき
λ＝（３×ｘ１＾２＋ａ）／（２×ｙ１），ν＝（−ｘ１＾３＋ａ×ｘ１＋２×ｂ）／（２×ｙ１）・・・：Ｐ１＝Ｐ２のとき
とする。Ｐ１≠Ｐ２のときに、Ｐ１＋Ｐ２を計算することを楕円加算、Ｐ１＝Ｐ２のときにＰ１＋Ｐ２＝２×Ｐ１を計算することを楕円２倍算という。楕円加算・楕円２倍算は、有限体ＧＦ（ｑ）での加減算・乗算・平方算・逆元計算の組み合わせによって計算される。
【０００８】
図９及び図１０は、楕円加算と楕円２倍算の説明図である。楕円加算は、図９に示されるように、楕円曲線上の点Ｐ１＝（ｘ１，ｙ１）とＰ２＝（ｘ２，ｙ２）とを結ぶ直線と楕円曲線との交点を、ｘ軸で折り返した点Ｐ３＝Ｐ１＋Ｐ２＝（ｘ３，ｙ３）として定義される。楕円２倍算は、図１０に示されるように、楕円曲線上の点Ｐ１＝（ｘ１，ｙ１）の接線と楕円曲線との交点を、ｘ軸で折り返した点Ｐ４＝Ｐ１＋Ｐ１＝２×Ｐ１＝（ｘ４，ｙ４）として定義される。
【０００９】
有限体ＧＦ（ｑ）上の楕円曲線Ｅと、曲線上の点Ｐと、整数（スカラーとも呼ぶ）ｄに対して、点ｄ×Ｐ＝Ｐ＋Ｐ＋…＋Ｐ（ｄ個の和）を計算することをスカラー倍算という。スカラー倍算は、楕円加算、楕円２倍算の組み合わせによって実現される。スカラー倍点ｄ×Ｐの計算は、ｄの２進展開
ｄ＝ｄ［ｎ−１］×２＾（ｎ−１）＋ｄ［ｎ−２］×２＾（ｎ−２）＋・・・＋ｄ［１］×２＋ｄ［０］
を利用して行われることが多い。
【００１０】
図１１は、従来のスカラー倍算アルゴリズム１を示す図である。図１１において、ステップＳ１で変数Ｑ［０］の初期値をＰとし、ステップＳ３で点Ｑ［０］の楕円２倍算を実行し、演算結果をＱ［０］に格納する。そしてｄ［ｉ］＝＝１であれば、ステップＳ５で、Ｑ［０］と点Ｐの楕円加算を実行し、演算結果をＱ［０］に格納する。
【００１１】
楕円曲線におけるスカラー倍計算は、楕円加算と楕円２倍算と呼ばれる演算の組み合わせで実現されるため、全体の計算時間はこれら演算の計算回数として評価される。さらに楕円加算、楕円２倍算の計算時間は、有限体ＧＦ（ｑ）における乗算、平方算、逆元計算の計算時間の和によって評価される。これは実際の楕円加算、楕円２倍算、スカラー倍算の計算が、有限体における加減算・乗算・平方算・逆元計算の組み合わせで計算され、多くの場合、加減算の計算時間はその他の計算時間に比べて無視できるほど短いからである。
【００１２】
有限体ＧＦ（ｑ）での逆元の計算時間は、乗算・平方算の計算時間に比べて非常に大きい。このため、楕円曲線の点を表現する上でヤコビアン座標が使用されることがある。ヤコビアン座標では、点は（Ｘ：Ｙ：Ｚ）のような有限体ＧＦ（ｑ）の３つの要素の組み合わせで表される。ただし（Ｘ：Ｙ：Ｚ）とｒ≠０であるＧＦ（ｑ）の要素ｒに対し（ｒ＾２×Ｘ：ｒ＾３×Ｙ：ｒ×Ｚ）は同じ点と考える。楕円曲線はヤコビアン座標では、ｘ＝Ｘ／Ｚ＾２，ｙ＝Ｙ／Ｚ＾３を代入して、
Ｅ：Ｙ＾２＝Ｘ＾３＋ａ×Ｘ×Ｚ＾４＋ｂ×Ｚ＾６
となる。ヤコビアン座標を用いると、楕円曲線上の点は（Ｘ：Ｙ：Ｚ）のような座標形式で表現することができる。無限遠点は∞＝（０：１：０）となる。このように、ヤコビアン座標では楕円曲線上の全ての点はＧＦ（ｑ）の３つの要素の組として表される。
【００１３】
ヤコビアン座標において、楕円加算に必要な計算時間は１２Ｍ＋４Ｓ、楕円２倍算に必要な計算時間は４Ｍ＋６Ｓである。特に入力点の一方のＺ座標が１の場合、楕円加算に必要な計算時間は８Ｍ＋３Ｓとなる。
【００１４】
ヤコビアン座標ではＺ座標の２乗や３乗が必要となるため、これらの値を座標の値として保持する座標（チュドノフスキー・ヤコビアン座標）が使用されることがある。チュドノフスキー・ヤコビアン座標では、点は（Ｘ：Ｙ：Ｚ：Ｚ２：Ｚ３）のような有限体ＧＦ（ｑ）の５つの要素の組み合わせで表され、Ｚ２＝Ｚ＾２、Ｚ３＝Ｚ＾３となっている。ただしＸ，Ｙ，Ｚはヤコビアン座標として考える。無限遠点は∞＝（０：１：０：０：０）となる。このように、チュドノフスキー・ヤコビアン座標では楕円曲線上の全ての点はＧＦ（ｑ）の５つの要素の組として表される。
【００１５】
チュドノフスキー・ヤコビアン座標において、楕円加算に必要な計算時間は１１Ｍ＋３Ｓ、楕円２倍算に必要な計算時間は５Ｍ＋６Ｓである。特に入力点の一方のＺ座標が１の場合、楕円加算に必要な計算時間は８Ｍ＋３Ｓとなる。
【００１６】
次に楕円曲線上のペアリングについて説明する。Ｅを有限体ＧＦ（ｑ）上の楕円曲線とする。ｌを楕円曲線Ｅの点の個数（曲線の位数といい＃Ｅとかく）の約数とし、ｋとして、ｌがｑ＾ｋ−１の約数となるような最小の自然数を選ぶ。このとき楕円曲線Ｅの有限体ＧＦ（ｑ）上の点Ｐと有限体ＧＦ（ｑ＾ｋ）上の点Ｑに対するｌ次のペアリング（Ｐ，Ｑ）とは、ＰとＱに対して１のｌ乗根のなす集合の要素を対応させる演算であって、以下の条件を満たす。
【００１７】
（Ｐ１＋Ｐ２，Ｑ）＝（Ｐ１，Ｑ）×（Ｐ２，Ｑ）
（Ｐ，Ｑ１＋Ｑ２）＝（Ｐ，Ｑ１）×（Ｐ，Ｑ２）
全てのＰに対して、Ｑ＝∞のとき、（Ｐ，Ｑ）＝１
ペアリングの具体的な例としてベイユ・ペアリングとテイト・ペアリングが知られている。以下では断りのない限りテイト・ペアリングを使用する。
【００１８】
次にテイト・ペアリングの計算方法について説明する。
楕円曲線Ｅの有限体ＧＦ（ｑ）上の点Ｐと有限体ＧＦ（ｑ＾ｋ）上の点Ｑに対するテイト・ペアリングは
（Ｐ，Ｑ）＝（ｆｐ（Ｑ＋Ｓ）／ｆｐ（Ｓ））＾（（ｑ＾ｋ―１）／ｌ）
と表せる。ここで関数ｆｐは、有限体ＧＦ（ｑ＾ｋ）上の点を入力とし、１のｌ乗根の集合の要素を出力する関数であり、以下の式で表せる。
【００１９】
ｆｐ（Ｑ＋Ｓ）＝Π［ｌ１（Ｑ＋Ｓ）／ｌ２（Ｑ＋Ｓ）］
ｆｐ（Ｓ）＝Π［ｌ１（Ｓ）／ｌ２（Ｓ）］
点Ｓは、有限体ＧＦ（ｑ＾ｋ）上の点、ｌ１は点Ｔと点Ｐを結ぶ直線（Ｔ＝Ｐの場合は、点Ｔの接線）の方程式であり、ｌ２はＴ＋Ｐ（Ｔ＝Ｐの場合にはＴ＋Ｔ）を通るｘ軸に垂直な直線の方程式を表す。また、Πは、ある条件を満たす直線の方程式の積を計算することを表す。
【００２０】
【非特許文献１】
大岸聖史，境隆一，笠原正雄，「楕円曲線上のＩＤ  情報に基づく鍵共有法に関する考察」，電子情報通信学会技術報告書，ＩＳＥＣ  ９９−５７、１９９９年１１月
【００２１】
【発明が解決しようとする課題】
ペアリング暗号が現実社会において広く用いられるためには、処理時間および実装上必要となるリソース（メモリ・回路量等）の低減が求められる。ペアリング暗号ではペアリングと呼ばれる演算が共通して使用され、処理全体における比重も高いため、この部分の性能向上が全体の性能向上に直結する。ペアリング暗号処理においてペアリング計算の比重は高いため、さらなる高速化が望まれている。
【００２２】
しかしながら、楕円曲線暗号の計算に使用されている座標は、楕円曲線のスカラー倍算の高速演算を目的としているため、ペアリングの計算には必ずしも最適ではなかった。
【００２３】
本発明の課題は、ペアリング暗号におけるペアリング計算を高速に行うことである。
【００２４】
【課題を解決するための手段】
本発明は、楕円曲線上の点に対するペアリングを用いた暗号を処理するペアリング暗号装置において、有限体上の楕円曲線と、楕円曲線上の点を記憶する記憶手段と、楕円２倍算または楕円加算の計算過程で得られる値を記憶し、記憶してある値を用いてペアリング演算の直線の方程式の係数を計算する演算手段とを備える。
【００２５】
この発明によれば、楕円２倍算または楕円加算の計算過程で得られる値を用いて、ペアリング演算の直線の方程式の係数を計算することができるので、ペアリング演算の計算時間を短縮することができる。
【００２６】
他の発明は、楕円曲線上の点に対するペアリングを用いた暗号を処理するペアリング暗号装置において、有限体上の楕円曲線と、楕円曲線上の点を記憶する記憶手段と、ペアリング演算の中間計算に用いられる直線の方程式を展開した式の一部の計算結果を記憶しておき、記憶してある計算結果を用いて直線の方程式の計算を行う演算手段とを備える。
【００２７】
例えば、楕円曲線上の点Ｔと点Ｐとを結ぶ直線の方程式をｌ１，点Ｔ＋Ｐを通りｘ軸に垂直な直線の方程式をｌ２とし、有限体上の点Ｑ＋Ｓ、点Ｓとしたときに、ペアリング演算の中間計算に用いられる直線の方程式とは、ｌ１（Ｑ＋Ｓ）×ｌ２（Ｓ）と、ｌ１（Ｓ）×ｌ２（Ｑ＋Ｓ）である。
【００２８】
この発明によれば、ペアリング演算の中間計算に用いられる直線の方程式を展開した式の一部の計算結果を利用して方程式の計算を行うことで計算時間を短縮できる。
【００２９】
上記の発明において、前記演算手段は、有限体上の４つの要素（Ｘ：Ｙ：Ｚ：Ｚ＾２）の組で１つの点の座標を表した簡約座標を用いてペアリング演算の計算を行う。このように簡約座標を用いてペアリング演算の計算を行うことで計算時間を短縮できる。
【００３０】
上記の発明において、演算手段は、楕円曲線上の点Ｑ＋Ｓの座標を（ｘＱＳ，ｙＱＳ）、点Ｓの座標を（ｘＳ，ｙＳ）、楕円曲線上の点Ｔと点Ｐを結ぶ直線の方程式をｌ１、点Ｔ＋Ｐを通るｘ軸に垂直な直線の方程式をｌ２としたときに、ｘＱＳ×ｘＳと、ｙＱＳ×ｘＳの値を事前に計算して記憶しておき、記憶してあるｘＱＳ×ｘＳと、ｙＱＳ×ｘＳの値を用いて、ペアリング演算のｌ１（Ｑ＋Ｓ）×ｌ２（Ｓ）及びｌ１（Ｓ）×ｌ２（Ｑ＋Ｓ）の計算を行うようにしても良い。
【００３１】
上記のように構成することで、ペアリング演算におけるｌ１（Ｑ＋Ｓ）×ｌ２（Ｓ）とｌ１（Ｓ）×ｌ２（Ｑ＋Ｓ）の計算時間を短縮することができる。
上記の発明において、演算手段は、点Ｔの座標Ｔ＝（Ｘ１：Ｙ１：Ｚ１）、点Ｔ＋Ｔの座標Ｔ＋Ｔ＝（Ｘ４：Ｙ４：Ｚ４）、点Ｔ＋Ｔを結ぶ直線ｌ１、点Ｔ＋Ｔを通るｘ軸に垂直な直線ｌ２としたときに、楕円２倍算の計算過程で計算されるＺ１＾２と３×Ｘ１＾２＋ａ×Ｚ１＾４とを用いて直線ｌ１，ｌ２の方程式の係数の計算を行うようにしてもよい。
【００３２】
このように構成することで、ペアリング演算における楕円２倍算の直線の方程式ｌ１，ｌ２の係数の計算時間を短縮できる。
また、上記の発明において、演算手段は、点Ｔの座標Ｔ＝（Ｘ１：Ｙ１：Ｚ１）、点Ｔ＋Ｐの座標Ｔ＋Ｐ＝（Ｘ３：Ｙ３：Ｚ３）、点Ｔ＋Ｐを結ぶ直線ｌ１、点Ｔ＋Ｐを通るｘ軸に垂直な直線ｌ２としたときに、楕円加算の計算過程で計算されるＺ３＾２とＹ２×Ｚ１＾３−Ｙ１とを用いて、直線ｌ１，ｌ２の方程式の係数の計算を行うようにしても良い。
【００３３】
このように構成することで、ペアリング演算における楕円加算の直線ｌ１，ｌ２の方程式の係数の計算時間を短縮できる。
なお、記憶手段は、例えば、図１の記憶部１５、あるいは記憶部１５とレジスタ１４に対応し、演算手段は、図１の演算部１２または演算器１３に対応する。
【００３４】
【発明の実施の形態】
以下、本発明の実施の形態を、図面を参照しながら説明する。実施の形態のペアリング暗号装置は、パーソナルコンピュータ、ＩＣカード（スマートカード）等に内蔵されたＩＣチップ、携帯電話、携帯情報端末装置、ＤＶＤプレーヤ等からなり、演算を行うプロセッサを有している。
【００３５】
図１は、本発明に係るペアリング暗号装置１１の要部の構成を示す図である。実施の形態のペアリング暗号装置１１の演算部１２は、演算器（ＣＰＵ）１３と、複数のレジスタからなるレジスタ１４とからなり、演算結果は再びレジスタ１４に入力される。記憶部１５は、ハードディスク、メモリ等からなり、後述する楕円曲線暗号のスカラー倍算の演算プログラムが記憶される。演算部１２は、記憶部１５に記憶されているプログラムを実行し、ペアリング暗号の演算等を行う。
【００３６】
以下の説明では、本発明に係るペアリング暗号の演算方法を、素体ＧＦ（ｑ）（ｑ＝ｐ＾ｍ、ｐは５以上の素数、ｍは１以上の自然数）上の楕円曲線に適用した場合について説明する。
【００３７】
ＧＦ（ｑ）上の円曲線Ｅは、以下の式で表せる。
Ｅ：ｙ＾２＝ｘ＾３＋ａ×ｘ＋ｂ
ここでａ，ｂ，ｘ，ｙはＧＦ（ｑ）の要素で、４×ａ＾３＋２７×ｂ＾２≠０を満たす。
【００３８】
図２は、一般的なテイト・ペアリングのアルゴリズムであるミラー・アルゴリズム（以下、アルゴリズム２という）のプログラムを示す図であり、図３は、そのアルゴリズム２を改良した本発明の第１の実施の形態のアルゴリズム（改良ミラー・アルゴリズム）（以下、アルゴリズム３という）のプログラムを示す図である。
【００３９】
先ず、図２に示すアルゴリズム２を説明する。図２のプログラムは、ｎビットの整数ｌと、楕円曲線上の点Ｐ、Ｑ、Ｓの座標を入力し、点Ｐと点Ｑのペアリング演算（Ｐ、Ｑ）の結果を出力するものである。
【００４０】
変数Ｔを記憶するレジスタ（以下、レジスタＴいう）に点Ｐの座標を格納し、関数ｆを格納するレジスタ（以下、レジスタｆという）に初期値として「１」を格納する（図２，Ｓ１１）。
【００４１】
次に、変数ｉをｎ−１〜０まで順に変化させ、以下の処理を実行する（図２，Ｓ１２）。
楕円２倍算Ｔ＝Ｔ＋Ｔを計算し、楕円２倍算の直線ｌ１，ｌ２の方程式の係数を計算する（図２，Ｓ１３）。
【００４２】
ここで、ｌ１は、点Ｔと点Ｐを結ぶ直線の方程式であり、ｌ２は、Ｔ＋Ｔの点を通るｘ軸に垂直な直線の方程式を表す。
次に、ステップＳ１４において、ｆ＝ｆ＾２×ｌ１（Ｑ＋Ｓ）×ｌ２（Ｓ）／ｌ１（Ｓ）／ｌ２（Ｑ＋Ｓ）を計算する。
【００４３】
整数ｌのｉビット目の値ｌ［ｉ］が「１」か否かを判別する（図２，Ｓ１５）。ｌ［ｉ］＝１であれば、次のステップＳ１６に進み、楕円加算Ｔ＋Ｐを計算し、楕円加算Ｔ＋Ｐの直線ｌ１，ｌ２の方程式の係数を計算する。
【００４４】
次に、ステップＳ１７において、ｆ＝ｆ×ｌ１（Ｑ＋Ｓ）×ｌ２（Ｓ）／ｌ１（Ｓ）／ｌ２（Ｑ＋Ｓ）を計算する。その後、ステップＳ１２に戻り、ｉ＝０まで処理を繰り返す。
【００４５】
ステップＳ１２〜Ｓ１７の処理が終了したなら、ステップＳ１８に進み、上記の処理で求めたｆの値からｆ＝ｆ＾｛（ｑ＾ｋ−１）／ｌ｝を計算する。
上記のミラー・アルゴリズムを改良したものが、図３に示す本発明の第１の実施の形態のアルゴリズム３である。以下の説明では、図２のプログラムと異なる部分について説明する。
【００４６】
第１の実施の形態のアルゴリズム３は、図２のテイト・ペアリングの演算のプログラムにおいて、楕円２倍算の計算と、楕円２倍算の直線ｌ１，ｌ２の方程式の係数の計算と、楕円加算の計算と、楕円加算の直線ｌ１，ｌ２の方程式の係数の計算において、共通する中間変数の計算を１度だけ行うようにしたものである。そのため、アルゴリズム３のプログラムにおいては、楕円２倍算と直線ｌ１，ｌ２の方程式の計算を共通する中間変数を用いて行う関数ＴＤＢＬと、楕円加算と直線ｌ１，ｌ２の方程式の計算を共通する中間変数を用いて行う関数ＴＡＤＤとを定義している。
【００４７】
図３のステップＳ２１及びＳ２２の処理は、図２のステップＳ１１及びＳ１２の処理と同じである。
次のステップＳ２３において、関数ＴＤＢＬを呼び出し、変数Ｔで指定される点の楕円２倍算と、直線ｌ１、ｌ２の方程式の係数の計算を行い、計算算結果を変数Ｔ、ｌ１，ｌ２に対応するレジスタに格納する。
【００４８】
次のステップＳ２４において、ｆ＝ｆ＾２×ｌ１（Ｑ＋Ｓ）×ｌ２（Ｓ）／ｌ１（Ｓ）／ｌ２（Ｑ＋Ｓ）を計算する。
ステップＳ２５において、ｌ［ｉ］＝１と判別されたときには、次のステップＳ２６に進み、関数ＴＡＤＤを呼び出し、楕円加算Ｔ＋Ｐと直線ｌ１，ｌ２の方程式の係数の計算を行う。
【００４９】
次のステップＳ２７において、ｆ＝ｆ×ｌ１（Ｑ＋Ｓ）×ｌ２（Ｓ）／ｌ１（Ｓ）／ｌ２（Ｑ＋Ｓ）を計算する。
ステップＳ２８及びＳ２９の処理は、図２のステップＳ１８及びＳ１９と同じである。
【００５０】
次に、図４は、図３のプログラムの楕円２倍算と直線ｌ１，ｌ２の方程式の係数を計算する関数ＴＤＢＬのプログラムを示す図である。
この第１の実施の形態においては、有限体ＧＦ（ｑ）の５つの要素（Ｘ：Ｙ１：Ｚ：Ｚ２：Ｚ３）で点の座標を表すチュドノフスキー・ヤコビアン座標を簡略化した簡約チュドノフスキー・ヤコビアン座標を用いる。簡約チュドノフスキー・ヤコビアン座標（以下、簡約座標という）とは、有限体ＧＦ（ｑ）の４つの要素（Ｘ：Ｙ：Ｚ：Ｚ２）で点の座標を表したものである。なお、Ｚ２＝Ｚ＾２である。
【００５１】
関数ＴＤＢＬの計算において、直線ｌ１，ｌ２の方程式は、点Ｔと、楕円２倍算により得られる点Ｔ＋Ｔの座標を、それぞれＴ＝（Ｘ１：Ｙ１：Ｚ１）、Ｔ＋Ｔ＝（Ｘ４：Ｙ４：Ｚ４）としたときに、以下のように表せる。
【００５２】
ｌ１：（Ｚ４×Ｚ１＾２×ｙ−２×Ｙ１＾２）−（３×Ｘ１＾２＋ａ×Ｚ１＾４）×（Ｚ１＾２×ｘ−Ｘ１）＝０  ・・・・（１）
ｌ２：Ｚ４＾２×ｘ−Ｘ４＝０    ・・・・（２）
図４の関数ＴＤＢＬのプログラムは、簡約座標で表した点Ｔの座標（Ｘ１：Ｙ１：Ｚ１：Ｚ１２）と、定数ａを入力し、楕円２倍算により得られる点２×Ｔ（＝Ｔ＋Ｔ）の座標（Ｘ４：Ｙ４：Ｚ４：Ｚ４２）と、楕円２倍算の直線ｌ１，ｌ２の方程式の係数Ａ，Ｂ，Ｃ，Ｄ，Ｅを出力するものである。
【００５３】
図４のステップＳ３１以降の処理で楕円２倍算の計算を行う。先ず、点ＴのＸ座標Ｘ１の平方算を計算し、計算結果を変数Ｘ１２としてレジスタ（以下、レジスタＸ１２という）に格納する（図４，Ｓ３２）。次に、点ＴのＹ座標Ｙ１の平方算を計算し、計算結果を変数Ｙ１２としてレジスタ（以下、レジスタＹ１２という）に格納する（図４，Ｓ３３）。
【００５４】
次に、ステップＳ３３で計算したレジスタＹ１２の平方算を計算し、計算結果を変数Ｙ１４としてレジスタＹ１４に格納する（図４，Ｓ３４）。次に、点ＴのＺ座標の平方Ｚ１２の平方算を計算し、計算結果をレジスタＺ１４に格納する（図４，Ｓ３５）。以下、計算結果は、それぞれの変数に対応するレジスタに格納されるものとする。
【００５５】
次に、３×Ｘ１２＋ａ×Ｚ１４の計算、すなわち、３×Ｘ１＾２＋ａ×Ｚ１＾４を計算し、計算結果をレジスタＭに格納する（図４，Ｓ３６）。
次に、４×Ｘ１×Ｙ１２の計算，すなわち、４×Ｘ１×Ｙ１＾２を計算し、計算結果をレジスタＳに格納する（図４，Ｓ３７）。
【００５６】
次に、Ｍ＾２−２×Ｓの計算、すなわち、レジスタＭの２乗からレジスタＳを２倍した値を減算し、結果をレジスタＸ４に格納する（図４，Ｓ３８）。
次に、Ｍ×（Ｓ−Ｘ４）−８×Ｙ１４の計算、すなわち、レジスタＳからレジスタＸ４を減算した値とレジスタＭとを乗算し、その計算結果から８×Ｙ１＾４を減算し、その結果をレジスタＹ４に格納する（図４，Ｓ３９）。
【００５７】
次に、２×Ｙ１×Ｚ１の計算結果をレジスタＺ４に格納する（図４，Ｓ４０）。
次に、ステップＳ４０で求めたレジスタＺ４の平方算を計算し、計算結果をレジスタＺ４２に格納する（図４，Ｓ４１）。
【００５８】
上記の処理により、楕円２倍算２×Ｔにより得られる点のＸ座標Ｘ４，Ｙ座標Ｙ４，Ｚ座標Ｚ４，Ｚ座標の平方Ｚ４２を計算することができる。
次に、ステップＳ４２以降の処理で直線ｌ１，ｌ２の方程式の係数を計算する。
【００５９】
最初に、−Ｍ×Ｚ１２の計算、すなわち、−（３×Ｘ１＾２＋ａ×Ｚ１＾２）×Ｚ１＾２を計算し、計算結果をレジスタＡに格納する（図４，Ｓ４３）。このステップＳ４３の処理により、レジスタＡには、−（３×Ｘ１＾２×Ｚ１＾２＋ａ×Ｚ１＾６）が格納される。
【００６０】
次に、Ｚ４×Ｚ１２の計算、すなわち、レジスタＺ４とレジスタＺ１２とを乗算し、乗算結果をレジスタＢに格納する（図４，Ｓ４４）。このステップＳ４４の処理により、レジスタＢには、Ｚ４×Ｚ１＾２が格納される。
【００６１】
次に、−２×Ｙ１２＋Ｍ×Ｘ１の計算、すなわち、レジスタＹ１２に−２を乗算した結果と、レジスタＭと点ＴのＸ座標Ｘ１とを乗算した結果を加算し、計算結果をレジスタＣに格納する（図４，Ｓ４５）。このステップＳ４５の処理により、レジスタＣには、−２×Ｙ１＾２＋（３×Ｘ１＾２＋ａ×Ｚ１＾４）×Ｘ１が格納される。
【００６２】
次に、レジスタＺ４２の値をレジスタＤに格納する（図４，Ｓ４６）。このステップＳ４６の処理により、レジスタＤには、Ｚ４＾２が格納される。
最後に、レジスタＸ４の負の値をレジスタＥに格納する（図４，Ｓ４７）。
【００６３】
上述した関数ＴＤＢＬのプログラムは、楕円２倍算の計算過程で得られるＺ１＾２，Ｙ１＾２、Ｍ＝３×Ｘ１＾２＋ａ×Ｚ１＾４をレジスタに記憶しておき、それらのレジスタの値を用いて直線ｌ１，ｌ２の方程式の係数Ａ，Ｂ，Ｃ，Ｄ，Ｅを計算しているので係数Ａ〜Ｅを計算するための計算時間を大幅に短縮することができる。
【００６４】
上述した関数ＴＤＢＬを、ヤコビアン座標を用いて計算した場合には、楕円２倍算の計算に４回の乗算と６回の平方算とで、４Ｍ＋６Ｓの計算時間を必要とする。直線ｌ１，ｌ２の方程式の係数の計算は、楕円２倍算の計算過程でＺ１＾２，Ｙ１＾２，（３×Ｘ１＾２＋ａ×Ｚ１＾４）が計算されることから、Ｚ４×Ｚ１＾２，（３×Ｘ１＾２＋ａ×Ｚ１＾４）×Ｚ１＾２，（３×Ｘ１＾２＋ａ×Ｚ１＾４）×Ｘ１，Ｚ４＾２を計算すればよいので、３Ｍ＋１Ｓの計算時間が必要となる。従って、合計で４Ｍ＋６Ｓ＋３Ｍ＋１Ｓ＝７Ｍ＋７Ｓの計算時間が必要となる。
【００６５】
また、チュドノフスキー・ヤコビアン座標を用いて計算した場合には、楕円２倍算の計算に５回の乗算と６回の平方算で５Ｍ＋６Ｓの計算時間を必要とする。直線ｌ１．ｌ２の方程式の係数の計算は、Ｚ１＾２，Ｙ１＾２，（３×Ｘ１＾２＋ａ×Ｚ１＾４），Ｚ４＾２が計算されていることから、Ｚ４×Ｚ１＾２，（３×Ｘ１＾２＋ａ×Ｚ１＾４）×Ｚ１＾２，（３×Ｘ１＾２＋ａ×Ｚ１＾４）×Ｘ１を計算すればよいので、これに３Ｍの計算時間を必要とする。従って、合計で５Ｍ＋６Ｓ＋３Ｍ＝８Ｍ＋６Ｓの計算時間を必要とする。
【００６６】
これに対して、関数ＴＤＢＬを簡約座標を用いて計算した場合には、楕円２倍算の計算４Ｍ＋６Ｓの計算時間を必要とし、直線の方程式の係数の計算は、Ｚ１＾２，Ｙ１＾２，（３×Ｘ１＾２＋ａ×Ｚ１＾４），Ｚ４＾２が楕円２倍算の計算過程で計算されていることから、Ｚ４×Ｚ１＾２，（３×Ｘ１＾２＋ａ×Ｚ１＾４）×Ｚ１＾２，（３×Ｘ１＾２＋ａ×Ｚ１＾４）×Ｘ１を計算すればよいので、その計算時間は３Ｍとなる。従って、合計で４Ｍ＋６Ｓ＋３Ｍ＝７Ｍ＋６Ｓの計算時間となる。
【００６７】
以上のことから、簡約座標を用いることで関数ＴＤＢＬの計算時間を、ヤコビアン座標による計算時間に比べて約６．３％、チュドノフスキー・ヤコビアン座標による計算時間に比べて約７．８％高速にできる。よって、関数ＴＤＢＬの計算にＧＦ（ｑ）の４つの要素の組（Ｘ：Ｙ：Ｚ：Ｚ＾２）で表した簡約座標を用いることで楕円２倍算と直線ｌ１，ｌ２の方程式の係数の計算時間を短縮することができる。
【００６８】
次に、図５は、図３のプログラムのステップＳ２６の関数ＴＡＤＤのプログラムを示す図である。
関数ＴＡＤＤの計算において、ヤコビアン座標における点Ｔの座標をＴ＝（Ｘ１：Ｙ１：Ｚ１）、点Ｐの座標をＰ＝（Ｘ２：Ｙ２：１）、楕円加算Ｔ＋Ｐにより得られる点の座標Ｔ＋Ｐ＝（Ｘ３：Ｙ３：Ｚ３）としたときに、楕円加算の直線ｌ１，ｌ２の方程式は、以下のように表せる。
ｌ１：Ｚ３×（ｙ−Ｙ２）−（Ｙ２×Ｚ１＾３−Ｙ１）×（ｘ−Ｘ２）＝０  ・・・・（３）
ｌ２：Ｚ３＾２×ｘ−Ｘ３＝０  ・・・（４）
上記の直線ｌ１，ｌ２の方程式の係数を以下のようにする。
【００６９】
ｌ１：Ａ×ｘ＋Ｂ×ｙ＋Ｃ
ｌ２：Ｄ×ｘ＋Ｅ
図５のプログラムは、簡約座標における点Ｔと点Ｐの座標Ｔ＝（Ｘ１：Ｙ１：Ｚ１：Ｚ１２）、Ｐ＝（Ｘ２：Ｙ２：１：１）を入力し、楕円加算Ｔ＋Ｐにより得られる点の座標Ｔ＋Ｐ＝（Ｘ３：Ｙ３：Ｚ３：Ｚ３２）と、ｌ１，ｌ２の方程式の係数Ａ，Ｂ，Ｃ，Ｄ，Ｅを出力するものである。
【００７０】
図５のステップＳ５１以降の処理で楕円加算の計算を行う。
最初に、点ＴのＸ座標Ｘ１をレジスタＵ１に格納する（図５，Ｓ５２）。次に、点ＰのＸ座標Ｘ２と、点ＴのＺ座標の平方Ｚ１２を乗算し、乗算結果をレジスタＵ２に格納する（図５，Ｓ５３）。
【００７１】
次に、点ＴのＹ座標Ｙ１をレジスタＳ１に格納する（図５，Ｓ５４）。次に、Ｙ２×Ｚ１×Ｚ１２の計算、すなわち、点ＰのＹ座標Ｙ２と、点ＴのＺ座標Ｚ１とＺ座標の平方Ｚ１２とを乗算し、計算結果をレジスタＳ２に格納する（図５，Ｓ５５）。
【００７２】
次に、レジスタＵ２からレジスタＵ１の値を減算し、減算結果をレジスタＨに格納する（図５，Ｓ５６）。
次に、Ｓ２−Ｓ１の計算、すなわち、レジスタＳ２のＹ２×Ｚ１＾３からレジスタＳ１のＹ１を減算し、減算結果をレジスタＲに格納する（図５，Ｓ５７）。
【００７３】
次に、レジスタＨの平方算を計算し、計算結果をレジスタＨ２に格納する（図５，Ｓ５８）。
次に、レジスタＨ２とレジスタＨを乗算し、乗算結果をレジスタＨ３に格納する）（図５，Ｓ５９）。
【００７４】
次に、レジスタＵ１とレジスタＨ２を乗算し、乗算結果をレジスタＵ１Ｈ２に格納する（図５，Ｓ６０）。
次に、−Ｈ３−２×Ｕ１Ｈ１＋Ｒ＾２の計算を行い、計算結果をレジスタＸ３に格納する（図５，Ｓ６１）。
【００７５】
次に、−Ｓ１×Ｈ３＋Ｒ×（Ｕ１Ｈ２−Ｘ３）の計算を行い、計算結果をレジスタＹ３に格納する（図５，Ｓ６２）。
次に、点ＴのＺ座標Ｚ１とレジスタＨとを乗算し、乗算結果をレジスタＺ３に格納する（図５，Ｓ６３）。
【００７６】
次に、レジスタＺ３の平方算を計算し、計算結果をレジスタＺ３２に格納する（図５，Ｓ６４）。
上述した処理により簡約座標において、楕円加算Ｔ＋Ｐにより得られる点の座標Ｔ＋Ｐ＝（Ｘ３：Ｙ３：Ｚ３：Ｚ３２＝Ｚ３＾２）を計算することができる。
【００７７】
ステップＳ６５以降の処理で直線ｌ１，ｌ２の方程式の係数の計算を行う。
先ず、レジスタＲの負の値をレジスタＡに格納する（図５，Ｓ６６）。このステップＳ６６の処理により、レジスタＡには、−（Ｙ２×Ｚ１＾３−Ｙ１）が格納される。
【００７８】
次に、レジスタＺ３の値をレジスタＢに格納する（図５，Ｓ６７）。次に、−Ｚ３×Ｙ２＋Ｒ×Ｘ２の計算、すなわち、レジスタＺ３の負の値とレジスタＹ２の乗算結果と、レジスタＲとレジスタＸ２の乗算結果を加算し、加算結果をレジスタＣに格納する（図５，Ｓ６８）。このステップＳ６８の処理により、レジスタＣには、“−Ｚ３×Ｙ２＋（Ｙ２×Ｚ１＾３−Ｙ１）×Ｘ２”が格納される。
【００７９】
次に、レジスタＺ３２の値をレジスタＤに格納する（図５，Ｓ６９）。このステップＳ６９の処理により、レジスタＤには、Ｚ３＾２が格納される。
最後に、レジスタＸ３の負の値をレジスタＥに格納する（図５，Ｓ７０）。
【００８０】
楕円加算の計算において、”Ｙ２×Ｚ１＾３−Ｙ１（レジスタＲ）”と、Ｚ３＾２（レジスタＺ３２）が計算されているので、直線ｌ１の方程式の係数Ａは、レジスタＲの負の値を求めることで計算できる。また、係数Ｂは、レジスタＺ３の値から求めることができる。また、係数Ｃは、レジスタＺ３とレジスタＹ２の乗算結果とレジスタＲとレジスタＸ２の乗算結果を加算することにより計算できる。さらに、直線ｌ２の係数Ｄは、レジスタＺ３２の値から求めることができ、係数Ｅは、レジスタＸ３の負の値から求めることができる。
【００８１】
従って、楕円加算の計算過程で得られる”Ｙ２×Ｚ１＾３−Ｙ１”とＺ３＾２をレジスタに保持しておき、それらの値を直線ｌ１，ｌ２の方程式の係数の計算に利用することで、２回の乗算、つまり２Ｍの計算時間で係数の計算を行うことができる。また、楕円加算の計算は、８Ｍ＋３Ｓの計算時間で計算することができるので、簡約座標を用いて関数ＴＡＤＤの計算を行った場合、合計で８Ｍ＋３Ｓ＋２Ｍ＝１０Ｍ＋３Ｓの計算時間で良い。
【００８２】
一方、ヤコビアン座標またはチュドノフスキー・ヤコビアン座標を用いて関数ＴＡＤＤの計算を行った場合には、楕円加算の計算に８Ｍ＋３Ｓの計算時間を必要とし、直線ｌ１，ｌ２の方程式の係数の計算は、Ｙ２×Ｚ１＾３−Ｙ１が楕円加算の計算過程で計算されていることから、Ｚ３×Ｙ２と、（Ｙ２×Ｚ１＾３−Ｙ１）×Ｘ２と、Ｚ３＾３の計算をすればよく、これに２Ｍ＋１Ｓの計算時間が必要となる。従って、関数ＴＡＤＤの計算に合計で８Ｍ＋３Ｓ＋２Ｍ＋１Ｓ＝１０Ｍ＋４Ｓの計算時間を必要とする。
【００８３】
関数ＴＡＤＤを簡約座標を用いて計算した場合の計算時間と、ヤコビアン及びチュドノフスキー・ヤコビアン座標を用いて計算した場合の計算時間を比較すると、前者の計算時間は、後者の計算時間に比べて約６，１％高速になる。従って、楕円加算と直線ｌ１，ｌ２の方程式の係数を求める関数ＴＡＤＤの計算を高速するためには簡約座標を用いることが好ましい。
【００８４】
次に、ペアリング演算の中間計算に用いる直線の方程式を展開した式を用いて計算時間を短縮する本発明の第２の実施の形態について説明する。
楕円２倍算Ｔ＋Ｔに対応する直線ｌ１，ｌ２の方程式は、前述したようにヤコビアン座標（または簡約座標）において、以下のように表せる。
【００８５】
ｌ１：（Ｚ４×Ｚ１＾２×ｙ−２×Ｙ１＾２）−（３×Ｘ１＾２＋ａ×Ｚ１＾４）×（Ｚ１＾２×ｘ−Ｘ１）＝０  ・・・・・（１）
ｌ２：Ｚ４＾２×ｘ−Ｘ４＝０  ・・・・・・（２）
楕円２倍算Ｔ＋Ｔに対応する関数ｆの計算では、図３のステップＳ２４の関数ｆの計算式に示されるように、ｌ１（Ｑ＋Ｓ）×ｌ２（Ｓ）とｌ１（Ｓ）×ｌ２（Ｑ＋Ｓ）を計算する必要がある。直線ｌ１，ｌ２の方程式の係数が与えられた場合に、関数ｆを上記の方程式に基づいて直接計算すると、値の代入に２×３×ｋ×Ｍ、関数ｆの更新に４Ｍｋ＋２Ｓｋの計算時間が必要となる。ここで、Ｍｋ、Ｓｋは、有限体ＧＦ（ｑ＾ｋ）における乗算、平方算の計算時間を表し、通常は、１Ｍｋ＝ｋ＾２×Ｍ、１Ｓｋ＝ｋ＾２×Ｓとなる。よって、必要な計算時間の合計は、２×３×ｋ×Ｍ＋４Ｍｋ＋２Ｓｋ＝（４×ｋ＾２＋６×ｋ）×Ｍ＋２×ｋ＾２×Ｓとなる。
【００８６】
ｌ１の右辺をＡｘ＋Ｂｙ＋Ｃ、ｌ２の右辺の式をＤｘ＋Ｅとおくと、
ｌ１（Ｑ＋Ｓ）×ｌ２（Ｓ）＝Ａ×Ｄ×（ｘＱＳ×ｘＳ）＋Ｂ×Ｄ×（ｙＱＳ×ｘＳ）＋Ａ×Ｅ×ｘＱＳ＋Ｂ×Ｅ×ｙＱＳ＋Ｃ×Ｄ×ｘＳ＋Ｃ×Ｅ  ・・（５）
ｌ１（Ｓ）×ｌ２（Ｑ＋Ｓ）＝Ａ×Ｄ×（ｘＱＳ×ｘＳ）＋Ｂ×Ｄ×（ｙＱＳ×ｘＳ）＋Ａ×Ｅ×ｘＳ＋Ｂ×Ｅ×ｙＳ＋Ｃ×Ｄ×ｘＱＳ＋Ｃ×Ｅ・・（６）
となる。ここで、ｘＱ，ｙＱ，ｘＱＳ，ｙＱＳ、ｘＳ，ｙＳは、それぞれ、アファイン座標における点Ｑの座標Ｑ＝（ｘＱ，ｙＱ）、点Ｑ＋Ｓの座標Ｑ＋Ｓ＝（ｘＱＳ，ｙＱＳ）、点Ｓの座標Ｓ＝（ｘＳ，ｙＳ）として、ペアリング計算の入力値として与えられる。
【００８７】
従って、ｌ１（Ｑ＋Ｓ）×ｌ２（Ｓ）及びｌ１（Ｓ）×ｌ２（Ｑ＋Ｓ）を上記（５）式及び（６）式のように展開し、ｘＱＳ×ｘＳ、ｙＱＳ×ｘＳの値を事前に計算しておけば、図３のアルゴリズム３のプログラムのステップＳ２４及びＳ２７の関数ｆの計算時間を短縮することができる。
【００８８】
図６及び図７のプログラムは、上述した考え基づいて作成したプログラムである。図６のプログラムは、図３のステップＳ２４の関数ｆを計算する処理の詳細なフローチャートである。
【００８９】
図６のプログラムは、レジスタｆ１，ｆ２，Ａ，Ｂ，Ｃ，Ｄ，Ｅ，ｘＱＳ，ｙＱＳ，ｘＳ，ｙＳ，ｘＱＳｘＳ，ｘＳｙＱＳ，ｘＱＳｙＳに格納されている値を取得し、計算結果をｆ１，ｆ２として出力するものである。
【００９０】
レジスタＡとレジスタＤに格納されている直線ｌ１，ｌ２の方程式の係数Ａ、Ｄを乗算し、乗算結果をレジスタＡＤに格納する（図６，Ｓ８１）。
次に、レジスタＢとレジスタＤに格納されている直線ｌ１，ｌ２の方程式の係数ＢとＤを乗算して、乗算結果をレジスタＢＤに格納する（図６，Ｓ８２）。
【００９１】
次に、レジスタＡとレジスタＥに格納されている方程式の係数ＡとＥを乗算して、乗算結果をレジスタＡＥに格納する（図６，Ｓ８３）。
次に、レジスタＢとレジスタＥに格納されている方程式の係数ＢとＥを乗算し、乗算結果をレジスタＢＥに格納する（図６，Ｓ８４）。
【００９２】
次に、レジスタＣとレジスタＤに格納されている方程式の係数ＣとＤを乗算し、乗算結果をレジスタＣＤに格納する（図６，Ｓ８５）。
次に、レジスタＣとレジスタＥに格納されている方程式の係数ＣとＥを乗算して、乗算結果をレジスタＣＥに格納する（図６，Ｓ８６）。
【００９３】
次に、レジスタＡＤとレジスタｘＱＳｘＳとを乗算し、乗算結果をレジスタＴに格納する（図６，Ｓ８７）。このステップＳ８７の処理により、レジスタＴには、Ａ×Ｄ×ｘＱＳ×ｘＳが格納される。
【００９４】
次に、レジスタＢＤとレジスタｘＳｙＱＳの乗算と、レジスタＡＥとレジスタｘＱＳの乗算と、レジスタＢＥとレジスタｙＱＳの乗算と、レジスタＣＤとレジスタｘＳの乗算を行い、それらの計算結果とレジスタＴとレジスタＣＥとを加算し、その計算結果をレジスタＴ１に格納する（図６，Ｓ８８）。
【００９５】
次に、レジスタＢＤとレジスタｘＱＳｙＳの乗算と、レジスタＡＥとレジスタｘＳの乗算と、レジスタＢＥとレジスタｙＳの乗算と、レジスタＣＤとレジスタｘＱＳの乗算を行い、それらの計算結果とレジスタＴとレジスタＣＥとを加算し、その計算結果をレジスタＴ２に格納する（図６，Ｓ８９）。
【００９６】
次に、レジスタｆ１の平方算を計算し、その計算結果とレジスタＴ１とを乗算し、乗算結果をレジスタｆ１に格納する（図６，Ｓ９０）。
次に、レジスタｆ２の平方算を計算し、その計算結果とレジスタＴ２とを乗算し、乗算結果をレジスタｆ２に格納する（図６，Ｓ９１）。
【００９７】
なお、図６のプログラムの処理を、変数ｉ＝０となるまで実行した後、ｆ＝ｆ１／ｆ２を計算することで関数ｆを求める。
図６のプログラムによれば、ｘＱＳ×ｘＳとｙＱＳ×ｘＳの値を事前に計算しておき、ｌ１（Ｑ＋Ｓ）×ｌ２（Ｓ）及びｌ１（Ｓ）×ｌ２（Ｑ＋Ｓ）を計算する計算式を上記のｘＱＳ×ｘＳとｙＱＳ×ｘＳに基づいて展開した式を用いることで、ｌ１（Ｑ＋Ｓ）×ｌ２（Ｓ）の計算時間は、係数Ａ〜Ｅの代入に６Ｍ、座標値の代入に５ｋＭとなる。また、ｌ１（Ｓ）×ｌ２（Ｑ＋Ｓ）の計算時間は、座標値の代入に４ｋＭ、ｆ１，ｆ２の更新に２Ｍｋ＋２Ｓｋとなる。さらに、ｆの更新２Ｍｋ＋２Ｓｋが必要となる。
【００９８】
従って、従来の計算方法で直接計算した場合の計算時間が（４×ｋ＾２＋６×ｋ）×Ｍ＋２×ｋ＾２×Ｓであったのに対して、第２の実施の形態の楕円２倍算の中間計算で用いる方程式を展開した式を用いた場合の計算時間は、（２×ｋ＾２＋９×ｋ＋６）×Ｍ＋２×ｋ＾２×Ｓで良い。よって、ペアリング演算における楕円２倍算の関数ｆの計算時間を短縮することができる。
【００９９】
次に、図７は、図３のアルゴリズム３のステップＳ２７の関数ｆを計算するプログラムを示す図である。
図７のプログラムは、レジスタｆ１，ｆ２，Ａ，Ｂ，Ｃ，Ｄ，Ｅ，ｘＱＳ，ｙＱＳ，ｘＳ，ｙＳ，ｘＱＳｘＳ，ｘＳｙＱＳ，ｘＱＳｙＳに格納されている値を取得して、ｆ１，ｆ２の計算結果を出力するものである。
【０１００】
図７において、ステップＳ１０１〜Ｓ１０７までの処理は、上述した図６のステップＳ８１〜Ｓ８７の処理と同じである。
また、図７のステップＳ１０８及びＳ１０９の処理も、図６のステップＳ８８及び８９の処理と同じである。
【０１０１】
上記のステップＳ１０８の処理により、レジスタＴ１には、ｌ１（Ｑ＋Ｓ）×ｌ２（Ｓ）に対応する値が格納される。また、ステップＳ１０９の処理により、レジスタＴ２には、ｌ１（Ｓ）×ｌ２（Ｑ＋Ｓ）に対応する値が格納される。
【０１０２】
次に、レジスタｆ１とレジスタＴ１を乗算し、乗算結果をレジスタｆ１に格納する（図７，Ｓ１１０）。
次に、レジスタｆ２とレジスタＴ２を乗算し、乗算結果をレジスタｆ２に格納する（図７，Ｓ１１１）。
【０１０３】
図７のプログラムを変数ｉ＝０となるまで実行した後、ｆ＝ｆ１／ｆ２を計算して関数ｆを求める。
図７のプログラムによれば、ｘＱＳ×ｘＳとｙＱＳ×ｘＳの値を事前に計算しておき、関数ｆを計算する計算式をｘＱＳ×ｘＳとｙＱＳ×ｘＳに基づいて展開した式を用いることで、計算時間を、２×Ｍｋ＋９×ｋ×Ｍ＋６×Ｍ＝（２×ｋ＾２＋９×ｋ＋６）×Ｍに削減することができる。
【０１０４】
従って、方程式を直接計算する従来の計算方法を用いた場合に、４Ｍｋ＋６×ｋ×Ｍ＝（４×ｋ＾２＋６×ｋ）の計算時間が必要なのに対して、第２の実施の形態の楕円加算の関数ｆの中間計算で用いられる方程式を展開した式を用いた場合には、（２×ｋ＾２＋９×ｋ＋６）×Ｍの計算時間でよい。よって、ペアリング演算において、楕円加算の関数ｆの計算時間を短縮することができる。
【０１０５】
なお、上述した実施例では、図３のアルゴリズム３に第１の実施の形態の計算方法と第２の実施の形態の計算方法の両方を適用する場合について説明したが、何れか一方のみを適用してプログラムを作成しても良い。その場合、ペアリング計算の計算時間は、第１の実施の形態による計算時間の短縮効果または第２の実施の形態による計算時間の短縮効果の一方を得ることができる。
【０１０６】
ここで、上述した実施の形態のペアリング暗号の演算プログラムを実行するペアリング暗号装置のハードウェア構成の一例を図８を参照して説明する。このペアリング暗号装置は、例えば、パーソナルコンピュータ等の情報処理装置により実現できる。
【０１０７】
ＣＰＵ２３は、上述した演算プログラム等を実行する。ＲＯＭ２４にはＢＩＯＳ等の制御プログラムが格納される。ＲＡＭ（メモリ）２６は、演算に使用される各種のレジスタとして使用される。記憶装置２５には、楕円曲線暗号の演算プログラム等が格納される。
【０１０８】
記録媒体読み取り装置２７は、ＣＤＲＯＭ、ＤＶＤ、フレキシブルディスク、ＩＣカード等の可搬記録媒体２８の読み取り、あるいは書き込みを行う装置である。
【０１０９】
入力装置２９は、キーボード等のデータを入力する装置である。通信インタフェース３０は、インターネット等のネットワーク３１に接続するための装置であり、この装置を介してネットワーク上の情報提供者３２のサーバからプログラムをダウンロードすることができる。なお、ＣＰＵ２２，ＲＡＭ２４，外部記憶装置２５等はバス２２により接続されている。
【０１１０】
本発明は、楕円曲線暗号の暗号化及び解読を行う専用の装置に限らず、ＩＣカード、ＤＶＤ装置、携帯電話機、パーソナルコンピュータ等の種々の製品に適用できる。
【０１１１】
（付記１）  楕円曲線上の点に対するペアリングを用いた暗号を処理するペアリング暗号装置において、
有限体上の楕円曲線と、楕円曲線上の点を記憶する記憶手段と、
楕円２倍算または楕円加算の計算過程で得られる値を記憶し、記憶してある値を用いてペアリング演算の直線の方程式の係数を計算する演算手段とを備えるペアリング暗号装置。
【０１１２】
（付記２）  楕円曲線上の点に対するペアリングを用いた暗号を処理するペアリング暗号装置において、
有限体上の楕円曲線と、楕円曲線上の点を記憶する記憶手段と、
ペアリング演算の中間計算で用いる直線の方程式を展開した式の一部の計算結果を記憶し、記憶してある計算結果を用いて直線の方程式の計算を行う演算手段とを備えるペアリング暗号装置。
【０１１３】
（付記３）  前記演算手段は、有限体上の４つの要素（Ｘ：Ｙ：Ｚ：Ｚ＾２）（＾：べき乗を表す）の組で１つの点の座標を表した簡約座標を用いてペアリング演算の計算を行う付記１または２記載のペアリング暗号装置。
【０１１４】
（付記４）  前記演算手段は、楕円曲線上の点Ｑ＋Ｓの座標を（ｘＱＳ，ｙＱＳ）、点Ｓの座標を（ｘＳ，ｙＳ）、楕円曲線上の点Ｔと点Ｐを結ぶ直線の方程式をｌ１、点Ｔ＋Ｐを通るｘ軸に垂直な直線の方程式をｌ２としたときに、ｘＱＳ×ｘＳと、ｙＱＳ×ｘＳの値を事前に計算して記憶しておき、記憶してあるｘＱＳ×ｘＳと、ｙＱＳ×ｘＳの値を用いて、ペアリング演算のｌ１（Ｑ＋Ｓ）×ｌ２（Ｓ）／（ｌ１（Ｓ）×ｌ２（Ｑ＋Ｓ））の計算を行う付記１または２記載のペアリング暗号装置。
【０１１５】
（付記５）  楕円曲線上の点に対するペアリングを用いた暗号の演算プログラムであって、
有限体上の楕円曲線と、楕円曲線上の点を記憶手段に記憶させ、
ペアリング演算の中間計算に用いる直線の方程式を展開した式の一部の計算結果を保持しておき、保持した計算結果を用いてペアリング演算の計算を演算手段に実行させるペアリング暗号演算プログラム。
【０１１６】
（付記６）  前記演算手段は、点Ｔの座標Ｔ＝（Ｘ１：Ｙ１：Ｚ１）、点Ｔ＋Ｔの座標Ｔ＋Ｔ＝（Ｘ４：Ｙ４：Ｚ４）、点Ｔ＋Ｔを結ぶ直線ｌ１、点Ｔ＋Ｔを通るｘ軸に垂直な直線ｌ２としたときに、楕円２倍算の計算過程で計算されるＺ１＾２と３×Ｘ１＾２＋ａ×Ｚ１＾４とを用いて直線ｌ１，ｌ２の方程式の係数の計算を行う付記１〜５の何れかに記載のペアリング暗号装置。
【０１１７】
（付記７）  前記演算手段は、点Ｔの座標Ｔ＝（Ｘ１：Ｙ１：Ｚ１）、点Ｔ＋Ｐの座標Ｔ＋Ｐ＝（Ｘ３：Ｙ３：Ｚ３）、点Ｔ＋Ｐを結ぶ直線ｌ１、点Ｔ＋Ｐを通るｘ軸に垂直な直線ｌ２としたときに、楕円加算の計算過程で計算されるＺ３＾２とＹ２×Ｚ１＾３−Ｙ１とを用いて、直線ｌ１，ｌ２の方程式の係数の計算を行う付記１〜５の何れかに記載のペアリング暗号装置。
【０１１８】
（付記８）  前記演算手段は、点Ｔの座標Ｔ＝（Ｘ１：Ｙ１：Ｚ１）、点Ｔ＋Ｐの座標Ｐ＋Ｔ＝（Ｘ３：Ｙ３：Ｚ３）、点Ｔ＋Ｔの座標Ｔ＋Ｔ＝（Ｘ４：Ｙ４：Ｚ４）とし、点Ｔ＋Ｐを結ぶ直線ｌ１（Ｐ＝Ｔのときには点Ｔの接線）、点Ｔ＋Ｐ（または点Ｔ＋Ｔ）を通るｘ軸に垂直な直線ｌ２としたときに、楕円２倍算の計算過程で計算されるＺ１＾２と３×Ｘ１＾２＋ａ×Ｚ１＾４とを用いて楕円２倍算における直線ｌ１．ｌ２の方程式の係数の計算を行い、楕円加算の計算過程で計算されるＺ３＾２とＹ２×Ｚ１＾３−Ｙ１とを用いて、楕円加算における直線ｌ１，ｌ２の方程式の係数の計算を行う付記１〜５の何れかに記載のペアリング暗号装置。
【０１１９】
（付記９）  楕円曲線上の点に対するペアリングを用いた暗号のペアリング暗号プログラムであって、
有限体上の楕円曲線と、楕円曲線上の点を記憶手段に記憶させ、
楕円２倍算または楕円加算の計算過程で得られる値を記憶し、記憶してある値を用いてペアリング演算の直線の方程式の係数を演算手段に計算させるペアリング暗号演算プログラム。
【０１２０】
（付記１０）  有限体上の４つの要素（Ｘ：Ｙ：Ｚ：Ｚ＾２）（＾：べき乗を表す）の組で１つの点の座標を表した簡約座標を用いてペアリング演算の計算を行わせる付記５または９記載のペアリング暗号演算プログラム。
【０１２１】
（付記１１）  楕円曲線上の点Ｑ＋Ｓの座標を（ｘＱＳ，ｙＱＳ）、点Ｓの座標を（ｘＳ，ｙＳ）、楕円曲線上の点Ｔと点Ｐを結ぶ直線の方程式をｌ１、点Ｔ＋Ｐを通るｘ軸に垂直な直線の方程式をｌ２としたときに、ｘＱＳ×ｘＳと、ｙＱＳ×ｘＳの値を事前に計算して記憶させ、記憶してあるｘＱＳ×ｘＳと、ｙＱＳ×ｘＳの値を用いて、ペアリング演算のｌ１（Ｑ＋Ｓ）×ｌ２（Ｓ）／（ｌ１（Ｓ）×ｌ２（Ｑ＋Ｓ））の計算を行わせる付記５、９または１０記載のペアリング暗号演算プログラム。
【０１２２】
（付記１２）  点Ｔの座標Ｔ＝（Ｘ１：Ｙ１：Ｚ１）、点Ｔ＋Ｔの座標Ｔ＋Ｔ＝（Ｘ４：Ｙ４：Ｚ４）、点Ｔ＋Ｔを結ぶ直線ｌ１、点Ｔ＋Ｔを通るｘ軸に垂直な直線ｌ２としたときに、楕円２倍算の計算過程で計算されるＺ１＾２と３×Ｘ１＾２＋ａ×Ｚ１＾４とを用いて直線ｌ１．ｌ２の方程式の計算を行わせる付記５、９〜１１の何れかに記載のペアリング暗号演算プログラム。
【０１２３】
（付記１３）  点Ｔの座標Ｔ＝（Ｘ１：Ｙ１：Ｚ１）、点Ｔ＋Ｐの座標Ｔ＋Ｐ＝（Ｘ３：Ｙ３：Ｚ３）、点Ｔ＋Ｐを結ぶ直線ｌ１、点Ｔ＋Ｐを通るｘ軸に垂直な直線ｌ２としたときに、楕円加算の計算過程で計算されるＺ３＾２とＹ２×Ｚ１＾３−Ｙ１とを用いて、直線ｌ１，ｌ２の方程式の計算を行わせる付記５、９〜１１の何れかに記載のペアリング暗号演算プログラム。
【０１２４】
（付記１４）  点Ｔの座標Ｔ＝（Ｘ１：Ｙ１：Ｚ１）、点Ｔ＋Ｐの座標Ｐ＋Ｔ＝（Ｘ３：Ｙ３：Ｚ３）、点Ｔ＋Ｔの座標Ｔ＋Ｔ＝（Ｘ４：Ｙ４：Ｚ４）とし、点Ｔ＋Ｐを結ぶ直線ｌ１（Ｐ＝Ｔのときには点Ｔの接線）、点Ｔ＋Ｐ（または点Ｔ＋Ｔ）を通るｘ軸に垂直な直線ｌ２としたときに、楕円２倍算の計算過程で計算されるＺ１＾２と３×Ｘ１＾２＋ａ×Ｚ１＾４とを用いて楕円２倍算における直線ｌ１．ｌ２の方程式の係数の計算を行い、楕円加算の計算過程で計算されるＺ３＾２とＹ２×Ｚ１＾３−Ｙ１とを用いて、楕円加算における直線ｌ１，ｌ２の方程式の係数の計算を行わせる付記５、９〜１１の何れかに記載のペアリング暗号演算プログラム。
【０１２５】
【発明の効果】
本発明によれば、ペアリング暗号におけるペアリング計算を高速化できる。また、楕円２倍算または楕円加算の計算過程で得られる値を用いてペアリング演算に用いられる直線の方程式の係数を計算することで計算時間を短縮できる。また、ペアリング演算の中間計算に用いられる直線の方程式を展開した式の一部の値を予め計算しておくことで計算時間を短縮できる。
【図面の簡単な説明】
【図１】実施の形態のペアリング暗号装置の要部の構成を示す図である。
【図２】アルゴリズム２のプログラムを示す図である。
【図３】アルゴリズム３のプログラムを示す図である。
【図４】第１の実施の形態の関数ＴＤＢＬのプログラムを示す図である。
【図５】第１の実施の形態の関数ＴＡＤＤのプログラムを示す図である。
【図６】第２の実施の形態の関数ｆのプログラムを示す図である。
【図７】第２の実施の形態の関数ｆのプログラムを示す図である。
【図８】ハードウェア環境を示す図である。
【図９】楕円加算の説明図である。
【図１０】楕円２倍算の説明図である。
【図１１】アルゴリズム１のプログラムを示す図である。
【符号の説明】
１１      ペアリング暗号装置
１２      演算部
１３      演算器
１４      レジスタ
１５      記憶部
２３      ＣＰＵ
２４      ＲＯＭ
２５      記憶装置
２６      ＲＡＭ
２７      記録媒体読み取り装置
２９      入出力装置
【図１】
2004177673.tif 000003
【図２】
2004177673.tif 000004
【図３】
2004177673.tif 000005
【図４】
2004177673.tif 000006
【図５】
2004177673.tif 000007
【図６】
2004177673.tif 000008
【図７】
2004177673.tif 000009
【図８】
2004177673.tif 000010
【図９】
2004177673.tif 000011
【図１０】
2004177673.tif 000012
【図１１】
2004177673.tif 000013