(57)【特許請求の範囲】
【請求項１】
Fqを要素数qの有限体とし、q=2mとし、mを自然数とし、Fq上で定義された楕円曲線Eをy2+xy=x3+ax2+bとし、この楕円曲線Eに対応してFqn上で定義されたツイスト楕円曲線Etをy2+xy=x3+(a+c)x2+bとし、nを自然数とし、a,b∈Fqとし、cをc∈FqnであってFqnにおける非平方とした場合における、Fqn上の有理点P(xp,yp)∈Etの入力を受け付ける有理点入力手段と、
α∈Fq2nがα2+α+c=0を満たすものとし、σ1をFq2n上の(x,y)∈Etから(x,y+αx)∈Eへ移す写像とし、πqをFq上の(x,y)∈Eから(xq,yq)∈Eへ移すフロベニウス写像とし、σ2をFq2n上の(x,y)∈Eから(x,y+αx)∈Etへ移す写像とし、πqtを、Fq2n上の(x,y)∈Etを写像σ1によって移し、その像をフロベニウス写像πqによって移し、さらにその像を写像σ2によって移す写像とした場合における、前記有理点入力手段において入力された前記有理点P(xp,yp)∈Etの写像πqtによる像(πqt)Pを算出する自己準同写像演算手段と、
前記有理点入力手段において入力された前記有理点P(xp,yp)∈Etのk倍点であるkPのフロベニウス展開式(d0+d1πqt+…+dm-1(πqt)m-1)Pに、前記自己準同写像演算手段によって算出された前記像(πqt)Pを代入し、kPを算出するスカラー倍演算手段と、
を有することを特徴とする楕円曲線上スカラー倍演算装置。
【請求項２】
前記自己準同写像演算手段は、
【数１】
0004184120.tif 000012
の演算を行って定数emを算出する第１の定数演算手段と、
1≦j≦m-1を満たす全ての自然数jについて、前記第１の定数演算手段によって算出された定数emを用いて
【数２】
0004184120.tif 000013
の演算を行い、Fqn上の有理点P(xp,yp)∈Etの写像(πqt)jによる像(πqt)jPを算出する写像演算手段と、
を有する手段であり、
前記スカラー倍演算手段は、
kPのフロベニウス展開(d0+d1πqt+…+dm-1(πqt)m-1)Pの各定数diを、0≦i≦m-1について算出する第２の定数演算手段と、
前記第２の定数演算手段において算出された定数diと、前記写像演算手段において算出された前記像(πqt)jPとを用い、(d0+d1πqt+…+dm-1(πqt)m-1)Pの演算を行ってkＰを算出する展開式演算手段と、
を有することを特徴とする請求項１記載の楕円曲線上スカラー倍演算装置。
【請求項３】
前記自己準同写像演算手段は、
前記写像演算手段による処理の前に、
【数３】
0004184120.tif 000014
の演算によって定数hを算出する第３の定数演算手段をさらに有し、
前記写像演算手段は、
前記第３の定数演算手段によって算出された定数hを用いて
【数４】
0004184120.tif 000015
の演算を行い、前記像(πqt)jPを算出する手段であること、
を特徴とする請求項２記載の楕円曲線上スカラー倍演算装置。
【請求項４】
前記第２の定数演算手段は、
Rを前記ツイスト楕円曲線Et上の任意の点とし、Oを無限遠点とした場合における((πqt)2-w(πqt)+q)R=Oを満たすw、前記ｋ、及び前記要素数qの入力を受け付けるパラメータ入力手段と、
変数z1に前記ｋを代入し、変数i1、変数z2、及びすべてのi2(i2=0,1,...,m-1)の変数di2に０を代入する変数初期化手段と、
m≦i1≦2m-1を満たした場合、変数z3に(x mod q)-qの演算結果を代入し、nを((πqt)n+1)R=Oを満たす自然数とした場合における、d(i1 mod n)にd(i1 mod n)-z3の演算結果を代入し、m≦i1≦2m-1を満たさなかった場合、変数z3に(x mod q)の演算結果を代入し、d(i1 mod n)にd(i1 mod n)+z3の演算結果を代入する第１の変数代入手段と、
変数z4に(z1-z3)/qを代入し、変数z1にwz4+z2を代入し、z2に-z4を代入し、i1にi1+1を代入する第２の変数代入手段と、
z1=z2となった場合に、各di1の値を前記定数diとして出力する定数出力手段と、
を有することを特徴とする請求項２又は３の何れかに記載の楕円曲線上スカラー倍演算装置。
【請求項５】
請求項１から４何れかに記載された楕円曲線上スカラー倍演算装置としてコンピュータを機能させるためのプログラム。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
この発明は、楕円曲線上でのスカラー倍演算を行う楕円曲線上スカラー倍演算装置、及びその機能をコンピュータ上で実行させる楕円曲線上スカラー倍演算プログラムに関し、特に、標数２の有限体におけるツイスト楕円曲線上でのスカラー倍演算を行う楕円曲線上スカラー倍演算装置、及びその機能をコンピュータ上で実行させる楕円曲線上スカラー倍演算プログラムに関する。
【０００２】
【従来の技術】
情報通信ネットワークの進展が進む昨今、電子情報の秘匿や認証に必要な暗号技術は不可欠な要素である。そして、この暗号技術の安全性と高速化の向上が今後の重大な課題となっている。
そのような中、電子商取引の時代を担う次世代暗号として楕円曲線暗号が注目を集めている。楕円曲線暗号は、楕円曲線上の離散対数問題の求解困難性を根拠に安全性を確保する暗号方式の一種であり、素因数分解の困難性を安全性の根拠にするＲＳＡ暗号等と比べ、遥かに短い鍵長で同等の安全性強度を実現することができるものである。
しかし、この楕円曲線暗号も、処理能力が制限されるスマートカードや、大量の暗号処理が行われるサーバ装置等においては、処理速度や安全性の面で課題があり、その高速化・安全性の研究が世界中で展開されている。
【０００３】
一般に、楕円曲線暗号を実現する場合、その処理時間のほとんどは楕円曲線上のスカラー倍演算に費やされる。すなわち、楕円曲線暗号に用いられる「楕円曲線上の離散対数問題」とは、楕円曲線上の点Pとそのスカラー倍の点kPが与えられた時、スカラー値kを求める問題をいい、「楕円曲線上の点」とは、楕円曲線の定義方程式をみたす数の組をいうが、この楕円曲線上の離散対数問題生成時に行われるスカラー倍演算kPを高速化することが、楕円曲線暗号の高速化を実現することとなる。
通常、スカラー倍演算kPは、楕円曲線上の加法や２倍算を繰り返すことによって行われる。ここで、「楕円曲線上の加法」とは、楕円曲線上の点全体で定義された、無限遠点を単位元とした加法演算をいい、「楕円曲線上の２倍算」とは、同じ点同士の楕円曲線上の加法をいう。そして、この楕円曲線上の２点の加法は、これら２点を通る直線が再び楕円曲線と交わる他の点と、ｘ軸に関して対称な点を加法結果の点とする演算であり、楕円曲線上の点の２倍算は、この点の楕円曲線上の接線が再び楕円曲線と交わる他の点と、ｘ軸に関して対称な点を２倍算結果の点とする演算である。
【０００４】
また、スカラー倍演算kPを高速演算する方法として、フロベニウス（Frobenius）写像を用いる方法がある。ここで、「フロベニウス写像」とは、要素数qの有限体Fq上で定義された楕円曲線上の点P＝(x，y)に対する自己準同型写像（(x，y) → (xq，yq)）をいう。そして、このフロベニウス写像をπqとすると、(πq2-wπq+q)P=O (-2√q≦w≦2√q)を満たすことが知られており、この場合、スカラー倍演算kPは、kP=(d0+d1πq+…+dm-1(πq)m-1)Pと展開（フロベニウス展開）できることが知られている（非特許文献１参照。）。なお、Oは無限遠点を示す。この場合、スカラー倍演算kPの演算は、展開式(d0+d1πq+…+dm-1(πq)m-1)Pの各要素の置き換えのみによって行うことができ、楕円曲線上の加法や２倍算によって演算を行う場合に比べ、一般に処理を高速化することができる。
また、非特許文献２では、標数５以上の場合において、Ｆqn上で定義された有理点の数が素数となる楕円曲線上で、高速演算可能な自己準同型の写像を求め、ツイスト楕円曲線上でのスカラー倍算に、このフロベニウス展開を用いる方法が開示されている。以下に、その内容を概説する。なお、「標数」とは、有限体Ｆqの要素数qがq=βmと表される場合におけるβの値をいい、一般にその数は素数である。
【０００５】
この非特許文献２の場合、Ｆq上で楕円曲線E:y2=x3+ax+bが定義され、Ｆqn上でツイスト楕円曲線Et:y2=x3+ac2x+bc3が定義されている（a,b∈Ｆq、c∈ＦqnはＦqnで非平方）。ここで、「ツイスト楕円曲線」とは、Ｆqn上では楕円曲線Eと非同型であるが、Ｆq2n上では楕円曲線Eと同型となる曲線をいい、各楕円曲線Eにそれぞれ対応する関係にあるものである。
そして、写像πqtを、
【数５】
0004184120.tif 000002
のように定義し、この定義より、ツイスト楕円曲線Et上の点P(x,y)∈Ｆqnの写像πqtによる像は、Pπqt=(c1-qxq,c3(1-q)/2yq)となる。ここで、σ1はＦq2n上で同型となるツイスト楕円曲線Etから楕円曲線EへのＦq2n上での写像であり、フロベニウス写像πqは、楕円曲線E上での自己準同型の写像であり、σ2はＦq2n上で同型となる楕円曲線Eからツイスト楕円曲線EtへのＦq2n上での写像である。従って、この写像πqtは、ツイスト楕円曲線Et上の点をツイスト楕円曲線Et上に写す自己準同型の写像である。なお、E(Ｆq2n)、Et(Ｆq2n)は、Ｆq2n上で定義された楕円曲線E、ツイスト楕円曲線Etをそれぞれ示す。
また、この写像πqtは、((πqt)2-wπqt+q)R=O (-2√q≦w≦2√q)を満たすため、ツイスト楕円曲線Et上のスカラー倍演算kPは、kP=(d0+d1πqt+…+dm-1(πq)m-1)Pとフロベニウス展開でき（非特許文献１参照。）、前述のような高速演算が可能となる。なお、Rはツイスト楕円曲線Et上の任意の点を意味する。
【０００６】
【非特許文献１】
J.A.Solinas, "An Improved Algorithm for Arithmetic on a Family of Elliptic Curves", Advances in Cryptology-CRYPTO'97, Lecture Notes in Computer Science 1294, pp.357-371, Springer, 1997.
【非特許文献２】
T.Iijima, K.Matsuo, J.Chao, S.Tsujii, "Construction of Frobenius maps of twists elliptic curves and its application to elliptic scalar multiplication", scis2002.
【０００７】
【発明が解決しようとする課題】
しかし、非特許文献２の方法は、標数５以上であることを前提としており、標数２の場合に適用できないという問題点がある。
つまり、非特許文献２の方法は、標数５以上であることを前提に定義されたツイスト楕円曲線上でのスカラー倍演算の高速化を目的としたものであり、この方法を標数２であることを前提に定義されたツイスト楕円曲線上でのスカラー倍演算に適用することはできない。そのため、非特許文献２の方法を、２進数としての取扱いが必要なワイヤードロジック等によって直接的に実現することはできない。
この発明はこのような点に鑑みてなされたものであり、標数２の場合において、ツイスト楕円曲線上のスカラー倍演算を高速化することが可能な楕円曲線上スカラー倍演算装置を提供することを目的とする。
また、この発明の他の目的は、標数２の場合において、ツイスト楕円曲線上のスカラー倍演算を高速化する機能をコンピュータ上で実行させるための楕円曲線上スカラー倍演算プログラムを提供することである。
【０００８】
【課題を解決するための手段】
この発明では上記課題を解決するために、まず、有理点入力手段において、Fqn上の有理点P(xp,yp)∈Etの入力を受け付ける。なお、ここでは、Fqを要素数qの有限体とし、q=2mとし、mを自然数とし、Fq上で定義された楕円曲線Eをy2+xy=x3+ax2+bとし、この楕円曲線Eに対応してFqn上で定義されたツイスト楕円曲線Etをy2+xy=x3+(a+c)x2+bとし、nを自然数とし、a,b∈Fqとし、cをc∈FqnであってFqnにおける非平方としている。
次に、自己準同写像演算手段において、有理点入力手段において入力された有理点P(xp,yp)∈Etの写像πqtによる像(πqt)Pを算出する。なお、ここでは、α∈Fq2nがα2+α+c=0を満たすものとし、σ1をFq2n上の(x,y)∈Etから(x,y+αx)∈Eへ移す写像とし、πqをFq上の(x,y)∈Eから(xq,yq)∈Eへ移すフロベニウス写像とし、σ2をFq2n上の(x,y)∈Eから(x,y+αx)∈Etへ移す写像とし、πqtを、Fq2n上の(x,y)∈Etを写像σ1によって移し、その像をフロベニウス写像πqによって移し、さらにその像を写像σ2によって移す写像としている。
そして、有理点入力手段において入力された有理点P(xp,yp)∈Etのk倍点であるkPのフロベニウス展開式(d0+d1πqt+…+dm-1(πqt)m-1)Pに、自己準同写像演算手段によって算出された像(πqt)Pを代入し、kPを算出する。
【０００９】
ここで、σ1はＦq2n上で同型となるツイスト楕円曲線Etから楕円曲線EへのＦq2n上での写像であり、フロベニウス写像πqは、楕円曲線E上での自己準同型の写像であり、σ2はＦq2n上で同型となる楕円曲線Eからツイスト楕円曲線EtへのＦq2n上での写像である。従って、この写像πqtは、ツイスト楕円曲線Et上の点をツイスト楕円曲線Et上に写す自己準同型の写像である。
また、この写像πqtは、((πqt)2-wπqt+q)R=O (-2√q≦w≦2√q)を満たすため、ツイスト楕円曲線Et上のスカラー倍演算kPは、この写像πqtを用い、kP=(d0+d1πqt+…+dm-1(πq)m-1)Pとフロベニウス展開できる（非特許文献１参照。）。なお、Rはツイスト楕円曲線Et上の任意の点を意味し、Oは無限遠点を意味する。
従って、このスカラー倍演算kPの演算は、展開式(d0+d1πqt+…+dm-1(πq)m-1)Pの各要素の置き換えのみによって行うことができ、楕円曲線上の加法や２倍算によって演算を行う場合に比べ、一般に処理を高速化することができる。
【００１０】
【発明の実施の形態】
以下、この発明の実施の形態を図面を参照して説明する。
なお、以下では、まず、この形態の全体について説明し、その後、その詳細について説明を行っていく。
図１は、公知のコンピュータに所定のプログラムが実行されることによって構成される、楕円曲線上スカラー倍演算装置１の全体構成を例示した機能ブロック図である。以下、この図に沿って、楕円曲線上スカラー倍演算装置１の全体構成及び処理動作を説明する。なお、以下の説明では、Fqは要素数qの有限体を表すものとし、この例では、標数２の場合を取り上げるためq=2mとする（mは自然数）。また、標数２においてFq上で定義された楕円曲線Eをy2+xy=x3+ax2+bとし、この楕円曲線Eに対応してFqn上で定義されたツイスト楕円曲線Etをy2+xy=x3+(a+c)x2+bとする（nは自然数、a,b∈Fq、cはc∈FqnであってFqnにおける非平方の数）。さらに、α∈Fq2nはα2+α+c=0を満たすものとし、kはスカラー値を表すものとし、E(Ｆq)、Et(Ｆq)は、Ｆq上で定義された楕円曲線E、ツイスト楕円曲線Etをそれぞれ示すものとする。
【００１１】
楕円曲線上スカラー倍演算装置１によってスカラー倍演算を行う場合、まず、有理点入力部１０によって、Fqn上の有理点P(xp,yp)∈Etの入力を受け付け、入力された有理点P(xp,yp)を自己準同写像演算部２０に送る。
有理点P(xp,yp)が送られた自己準同写像演算部２０は、この有理点P(xp,yp)の以下の写像πqtによる像(πqt)Pを算出する。
【数６】
0004184120.tif 000003
ここで、写像πqtは、Fq2n上の(x,y)∈Etを写像σ1によって移し、その像をフロベニウス写像πqによって移し、さらにその像を写像σ2によって移す写像である。また、σ1は、Fq2n上の(x,y)∈Etを(x,y+αx)∈Eへ移す写像であり、πqは、Fq上の(x,y)∈Eを(xq,yq)∈Eへ移すフロベニウス写像であり、σ2は、Fq2n上の(x,y)∈Eを(x,y+αx)∈Etへ移す写像である。そして、σ1はＦq2n上で同型となるツイスト楕円曲線Etから楕円曲線EへのＦq2n上での写像であり、フロベニウス写像πqは、楕円曲線E上での自己準同型の写像であり、σ2はＦq2n上で同型となる楕円曲線Eからツイスト楕円曲線EtへのＦq2n上での写像である。従って、この写像πqtは、ツイスト楕円曲線Et上の点をツイスト楕円曲線Et上に写す自己準同型の写像である。
【００１２】
この写像πqtにおける有理点P(xp,yp)の像(πqt)Pを求めるために、まず、有理点P(xp,yp)の写像σ1による像を求めると、(xp,yp+αxp)となる。そして、そのフロベニウス写像πqによる像は((xp)q,(yp)q+αq(xp)q)となり、さらにその写像σ2による像は((xp)q,(yp)q+(αq+α)・(xp)q)となる。
ここで、q=2mであるため、em=αq+αおくと、emは
【数７】
0004184120.tif 000004
のように変換できる。そして、このemを用い、像(πqt)P=((xp)q,(yp)q+em・(xp)q)…(1)と表すことができる。
また、有理点P(xp,yp)に写像πqtをj回適用すると、その像(πqt)jPは、
【数８】
0004184120.tif 000005
となる。以下に、その証明を示す。
【００１３】
j=１のときは、その代入結果は(πqt)P=((xp)q,(yp)q+em・(xp)q)となるため、成立することは自明である。また、j=Lで成立すると仮定すると
【数９】
0004184120.tif 000006
が成立し、式（１）より
【数１０】
0004184120.tif 000007
が成立する。これによりj=L+1でも成立することがいえるため、全ての自然数ｊについて成立することがいえる〔証明終わり〕。
自己準同写像演算部２０では、式（２）を用いて、1≦j≦m-1を満たす全ての自然数jについて像(πqt)jPを演算し、その結果をスカラー倍演算部３０に送る。
【００１４】
この演算結果を受け取ったスカラー倍演算部３０は、有理点入力部１０において入力された有理点P(xp,yp)∈Etのk倍点であるkPのフロベニウス展開式(d0+d1πqt+…+dm-1(πqt)m-1)Pに、自己準同写像演算部２０によって算出された像(πqt)jPを代入し、kPを算出する。
すなわち、式（２）で表される像(πqt)jPは、((πqt)2-wπqt+q)R=O (-2√q≦w≦2√q)、及び ((πqt)n+1)R=O を満たすことになるが（R:ツイスト楕円曲線Et上の任意の点、O：無限遠点）、この場合、非特許文献１に示したように、ツイスト楕円曲線Et上のスカラー倍演算kPは、kP=(d0+d1πqt+…+dm-1(πq)m-1)Pとフロベニウス展開できる。そのため、自己準同写像演算部２０から受け取った(πqt)jP (1≦j≦m-1)の演算結果と、後述するアルゴリズムで求めた定数di(0≦i≦m-1)とを用いてdi(πqt)iP (1≦j≦m-1)を計算し、それらを足し合わせることによりkPを高速に求めることができる。
【００１５】
次に、この形態の詳細について説明する。
図２の（ａ）は、この形態の楕円曲線上スカラー倍演算装置１のハードウェア構成を例示したブロック図である。
図２の（ａ）に例示するように、この例の楕円曲線上スカラー倍演算装置１は、キーボード等の入力装置１ａ、液晶ディスプレイ等の出力装置１ｂ、ＣＰＵ（Central Processing Unit）１ｃ、ハードディスク等の記憶装置１ｄ、及び入力装置１ａ、出力装置１ｂ、ＣＰＵ１ｃ、記憶装置１ｄ間をデータのやり取りが可能なように接続するバス１ｅを有しており、記憶装置１ｄに記憶された所定のプログラムをＣＰＵ１ｃで実行することにより、その処理機能を実現する。
図２の（ｂ）は、図２の（ａ）に例示したハードウェア上で所定のプログラムを実行させることにより実現される自己準同写像演算部２０の機能構成の詳細を、図３は、スカラー倍演算部３０の機能構成の詳細を、それぞれ例示した図であり、図４は、楕円曲線上スカラー倍演算装置１の処理機能を説明するためのフローチャートである。以下、これらの図を用いて、楕円曲線上スカラー倍演算装置１の構成、及び処理機能の説明を行っていく。
【００１６】
楕円曲線上スカラー倍演算装置１においてスカラー倍演算を行う場合、まず、有理点入力部１０において、Fqn上の有理点P(xp,yp)∈Etの入力を受け付け、入力された有理点P(xp,yp)を自己準同写像演算部２０の写像演算部２４に送る（ステップＳ１）。
次に、自己準同写像演算部２０の定数演算部２２において、レジスタ２１からパラメータc,mを読み出す。なお、このパラメータcは、ツイスト楕円曲線Et（y2+xy=x3+(a+c)x2+b）の定数cであり、パラメータmは、有限体Fqの要素数q=2mを特定する自然数ｍであり、これらは予めレジスタ２１に格納されたデータである。パラメータc,mを読み出した定数演算部２２は、これらのパラメータc,mを
【数１１】
0004184120.tif 000008
に代入して定数emを算出し、算出した定数emを定数演算部２３に送る（ステップＳ２）。
【００１７】
定数emを受け取った定数演算部２３は、レジスタ２１からパラメータqを読み出す。なお、このパラメータqは、有限体Fqの要素数qであり、予めレジスタ２１に格納されたデータである。パラメータqを読み出した定数演算部２３は、受け取った定数emと、読み出したパラメータqとを
【数１２】
0004184120.tif 000009
に代入して定数hを演算し、その演算結果である定数hを、パラメータqとともに写像演算部２４に送る（ステップＳ３）。
写像演算部２４では、ステップＳ１で有理点入力部１０から送られた有理点P(xp,yp)と、ステップＳ３で定数演算部２３から送られた定数h、及びパラメータqを
【数１３】
0004184120.tif 000010
に代入して演算を行い、1≦j≦m-1を満たす全ての自然数jについて像(πqt)jPを算出する（ステップＳ４）。なお、この演算は、1≦j≦m-1を満たす全ての自然数jについて、定数演算部２２によって算出された定数emを用いて
【数１４】
0004184120.tif 000011
の演算を行い、Fqn上の有理点P(xp,yp)∈Etの写像(πqt)jによる像(πqt)jPを算出することに該当する。また、写像演算部２４で算出された像(πqt)jPは、スカラー倍演算部３０の展開式演算部３１に送られる。
【００１８】
次に、スカラー倍演算部３０のパラメータ入力部３２ａにおいて、Rをツイスト楕円曲線Et上の任意の点とし、Oを無限遠点とした場合における((πqt)2-w(πqt)+q)R=Oを満たすw、スカラー値ｋ、要素数qの入力を受け付け、入力したこれらの情報をレジスタ３２ｂに格納する（ステップＳ５）。
その後、変数初期化部３２ｃにおいて、レジスタ３２ｂから、変数i1,di2,z1,z2、及び定数kを読み出し、変数z1にｋを代入し、変数i1、変数z2、及びすべて変数di2(∀i2)に０を代入する（ステップＳ６）。なお、レジスタ３２ｂには、変数z1,z2,z3,z4,i1,i2,di1、前述の定数q,m,k,w、有限体Fqnの要素数を特定し、((πqt)n+1)R=Oを満たす自然数nが格納されているものとする。
次に、比較部３２ｄにおいて、レジスタ３２ｂから変数z1,z2を読み出し、読み出した変数がz1=z2となるか否かを判断し（ステップＳ７）、z1,z2となっていなかった場合、ステップＳ８の処理に進む。
【００１９】
ステップＳ８では、変数代入部３２ｅにおいて、まず、レジスタ３２ｂから定数q,m,di1、及び変数i1,z1,z3を読み出し、m≦i1≦2m-1を満たすか否かを判断する。そして、m≦i1≦2m-1を満たした場合、z3に(z1mod q)-qを、d(i1 mod n)にd(i1 mod n)-z3を代入し（ステップＳ９）、満たさなかった場合、z3に(z1mod q)を、d(i1 mod n)にd(i1 mod n)+z3を代入する（ステップＳ１０）。
これらの代入結果z3,d(i1 mod n)はレジスタ３２ｂに格納され、次に、変数代入部３２ｇにおいて、レジスタ３２ｂから定数q,n,w、及び変数di1,i1,z1,z2,z3,z4を読み出し、変数z4に(z1-z3)/qを代入し、変数z1にwz4+z2を代入し、z2に-z4を代入し、i1にi1+1を代入する（ステップＳ１１）。代入結果i1,z1,z2,z4は、レジスタ３２ｂに格納され、再び、ステップＳ７の処理に戻る。
【００２０】
ステップＳ７の処理において、比較部３２ｄがz1=z2であると判断した場合、比較部３２ｄは、その旨の情報を定数出力部３２ｈに送り、定数出力部３２ｈは、レジスタ３２ｂに格納されている変数di1を読み出し、各di1の値を定数diとして展開式演算部３１に出力する（ステップＳ１２）。なお、以上で説明したパラメータ入力部３２ａ、レジスタ３２ｂ、変数初期化部３２ｃ、比較部３２ｄ、変数代入部３２ｅ、３２ｇ、及び定数出力部３２ｈは、kPのフロベニウス展開(d0+d1πqt+…+dm-1(πqt)m-1)Pの各定数diを0≦i≦m-1について算出する定数演算部３２を構成することになる。
定数演算部３２において算出され、出力された定数di（ステップＳ５〜ステップＳ１２）と、自己準同像算出部２０の写像演算部２４において算出された像(πqt)jP（ステップＳ４）とを受け取った展開式演算部３１は、これらのデータを用い、(d0+d1πqt+…+dm-1(πqt)m-1)Pの演算を行ってkPを算出し、その演算結果kPを出力する（ステップＳ１３）。
【００２１】
このように、本形態では、有理点入力手段である有理点入力部１０において、Fqn上の有理点P(xp,yp)∈Etの入力を受け付け、自己準同写像演算手段である自己準同写像演算部２０において、α∈Fq2nがα2+α+c=0を満たすものとし、σ1をFq2n上の(x,y)∈Etから(x,y+αx)∈Eへ移す写像とし、πqをFq上の(x,y)∈Eから(xq,yq)∈Eへ移すフロベニウス写像とし、σ2をFq2n上の(x,y)∈Eから(x,y+αx)∈Etへ移す写像とし、πqtを、Fq2n上の(x,y)∈Etを写像σ1によって移し、その像をフロベニウス写像πqによって移し、さらにその像を写像σ2によって移す写像とした場合における、有理点入力部１０において入力された有理点P(xp,yp)∈Etの写像πqtによる像(πqt)Pを算出する。そして、スカラー倍演算手段であるスカラー倍演算部３０において、有理点入力部１０において入力された有理点P(xp,yp)∈Etのk倍点であるkPのフロベニウス展開式(d0+d1πqt+…+dm-1(πqt)m-1)Pに、自己準同写像演算部２０によって算出された像(πqt)Pを代入し、kPを算出することとした。
【００２２】
ここで、前述のように、この写像πqtは、ツイスト楕円曲線Et上の点をツイスト楕円曲線Et上に写す自己準同型の写像である。また、この写像πqtは、((πqt)2-wπqt+q)R=O (-2√q≦w≦2√q)を満たすため、ツイスト楕円曲線Et上のスカラー倍演算kPは、この写像πqtを用い、kP=(d0+d1πqt+…+dm-1(πq)m-1)Pとフロベニウス展開できる。従って、この標数２におけるスカラー倍演算kPの演算は、展開式(d0+d1πqt+…+dm-1(πq)m-1)Pの各要素の置き換えのみによって行うことができ、楕円曲線上の加法や２倍算によって演算を行う場合に比べ、一般に処理を高速化することができる。
【００２３】
また、この形態では、自己準同写像演算部２０は、式（３）の演算を行って定数emを算出する第１の定数演算手段である定数演算部２２、及び、1≦j≦m-1を満たす全ての自然数jについて、第１の定数演算部によって算出された定数emを用いて式（６）の演算を行い、Fqn上の有理点P(xp,yp)∈Etの写像(πqt)jによる像(πqt)jPを算出する写像演算部２４を有することとした。さらに、スカラー倍演算部３０は、kPのフロベニウス展開(d0+d1πqt+…+dm-1(πqt)m-1)Pの各定数diを、0≦i≦m-1について算出する第２の定数演算手段である定数演算部３２、及び、定数演算部３２において算出された定数diと、写像演算部において算出された像(πqt)jPとを用い、(d0+d1πqt+…+dm-1(πqt)m-1)Pの演算を行ってkＰを算出する展開式演算手段である展開式演算部３１を有することとした。そのため、定数演算部３２において算出された定数di、及び写像演算部において算出された像(πqt)jPを展開式(d0+d1πqt+…+dm-1(πq)m-1)Pへの各要素に代入するのみで、標数２におけるツイスト楕円曲線Et上のスカラー倍kPを高速に求めることができる。
【００２４】
さらに、自己準同写像演算部２０は、写像演算部２４による処理の前に、式（４）の演算によって定数hを算出する第３の定数演算手段である定数演算部２３を有し、写像演算部２４は、定数演算部２３によって算出された定数hを用いて式（５）の演算を行い、像(πqt)jPを算出することとした。この場合、式（５）に示すように、(πqt)j写像の演算コストは、Fqn上のq乗の演算を２j回（xpqをj回、ypqをj回）、乗算１回、加算１回のみである。そして、Fqn上のq乗は一般に高速に演算できる。そのため、(πqt)j写像の演算コストは、楕円曲線上の加算等に比べると誤差の範囲となり、標数２におけるツイスト楕円曲線Et上のスカラー倍kPの演算をより高速に行うことが可能となる。
【００２５】
また、第２の定数演算部３２は、Rをツイスト楕円曲線Et上の任意の点、Oを無限遠点とした場合における((πqt)2-w(πqt)+q)R=Oを満たすw、前述したｋ及び要素数qの入力を受け付けるパラメータ入力手段であるパラメータ入力部３２ａ、変数z1にｋを代入し、変数i1、変数z2、及びすべてのi2の変数di2に０を代入する変数初期化手段である変数初期化部３２ｃ、m≦i1≦2m-1を満たした場合、変数z3に(x mod q)-qの演算結果を代入し、d(i1 mod n)にd(i1 mod n)-z3の演算結果を代入し、m≦i1≦2m-1を満たさなかった場合、変数z3に(x mod q)の演算結果を代入し、d(i1 mod n)にd(i1 mod n)+z3の演算結果を代入する第１の変数代入手段である変数代入部３２ｅ、変数z4に(z1-z3)/qを代入し、変数z1にwz4+z2を代入し、z2に-z4を代入し、i1にi1+1を代入する第２の変数代入手段である変数代入部３２ｇ、及びz1=z2となった場合に、各di1の値を定数diとして出力する定数出力手段である定数出力部３２ｈを有することとした。そのため、これらを用いたステップＳ５〜Ｓ１３の処理により、kPのフロベニウス展開(d0+d1πqt+…+dm-1(πqt)m-1)Pの各定数diを容易に求めることができ、標数２におけるツイスト楕円曲線Et上のスカラー倍kPを高速に求めることができる。
【００２６】
なお、この発明は上述の実施の形態に限定されるものではない。例えば、この形態では、ステップＳ３において式（４）を用いて定数hを算出し、その定数hを式（５）に代入することによって像(πqt)jPを算出したが（ステップＳ４）、定数hを求めず、式（３）と式（６）の演算のみで像(πqt)jPを算出することとしてもよい。
また、この実施の形態では、楕円曲線上スカラー倍演算装置の処理機能を、コンピュータに所定のプログラムを実行させることにより実現する構成としたが、これらの処理機能の少なくとも一部を電子回路によってハードウェア的に実現することとしてもよい。
また、上述の実施の形態で述べたように、上記の処理機能は、コンピュータによって実現することができる。この場合、楕円曲線上スカラー倍演算装置が有すべき機能の処理内容はプログラムによって記述され、このプログラムをコンピュータで実行することにより、上記処理機能をコンピュータ上で実現することができる。
【００２７】
また、この処理内容を記述したプログラムは、コンピュータで読み取り可能な記録媒体に記録しておくことができる。コンピュータで読み取り可能な記録媒体としては、例えば、磁気記録装置、光ディスク、光磁気記録媒体、半導体メモリ等どのようなものでもよいが、具体的には、例えば、磁気記録装置として、ハードディスク装置、フレキシブルディスク、磁気テープ等を、光ディスクとして、ＤＶＤ（Digital Versatile Disc）、ＤＶＤ−ＲＡＭ（Random Access Memory）、ＣＤ−ＲＯＭ（Compact Disc Read Only Memory）、ＣＤ−Ｒ（Recordable）／ＲＷ（ReWritable）等を、光磁気記録媒体として、ＭＯ（Magneto-Optical disc）等を、半導体メモリとしてＥＥＰ−ＲＯＭ（Electronically Erasable and Programmable-Read Only Memory）等を用いることができる。また、このプログラムの流通は、例えば、そのプログラムを記録したＤＶＤ、ＣＤ−ＲＯＭ等の可搬型記録媒体を販売、譲渡、貸与等することによって行う。さらに、このプログラムをサーバコンピュータの記憶装置に格納しておき、ネットワークを介して、サーバコンピュータから他のコンピュータにそのプログラムを転送することにより、このプログラムを流通させる構成としてもよい。
【００２８】
このようなプログラムを実行するコンピュータは、例えば、まず、可搬型記録媒体に記録されたプログラムもしくはサーバコンピュータから転送されたプログラムを、一旦、自己の記憶装置に格納する。そして、処理の実行時、このコンピュータは、自己の記録媒体に格納されたプログラムを読み取り、読み取ったプログラムに従った処理を実行する。また、このプログラムの別の実行形態として、コンピュータが可搬型記録媒体から直接プログラムを読み取り、そのプログラムに従った処理を実行することしてもよく、さらに、このコンピュータにサーバコンピュータからプログラムが転送されるたびに、逐次、受け取ったプログラムに従った処理を実行することとしてもよい。また、サーバコンピュータから、このコンピュータへのプログラムの転送は行わず、その実行指示と結果取得のみによって処理機能を実現する、いわゆるＡＳＰ（Application Service Provider）型のサービスによって、上述の処理を実行する構成としてもよい。
なお、上記におけるプログラムとは、電子計算機に対する指令であって、一の結果を得ることができるように組合されたものをいい、その他電子計算機による処理の用に供する情報であってプログラムに準ずるものをも含むものとする。
【００２９】
【発明の効果】
以上説明したようにこの発明では、有理点入力部において、Fqを要素数qの有限体とし、q=2mとし、mを自然数とし、Fq上で定義された楕円曲線Eをy2+xy=x3+ax2+bとし、この楕円曲線Eに対応してFqn上で定義されたツイスト楕円曲線Etをy2+xy=x3+(a+c)x2+bとし、nを自然数とし、a,b∈Fqとし、cをc∈FqnであってFqnにおける非平方とした場合における、Fqn上の有理点P(xp,yp)∈Etの入力を受け付ける。次に、自己準同写像演算部において、α∈Fq2nがα2+α+c=0を満たすものとし、σ1をFq2n上の(x,y)∈Etから(x,y+αx)∈Eへ移す写像とし、πqをFq上の(x,y)∈Eから(xq,yq)∈Eへ移すフロベニウス写像とし、σ2をFq2n上の(x,y)∈Eから(x,y+αx)∈Etへ移す写像とし、πqtを、Fq2n上の(x,y)∈Etを写像σ1によって移し、その像をフロベニウス写像πqによって移し、さらにその像を写像σ2によって移す写像とした場合における、有理点入力部において入力された有理点P(xp,yp)∈Etの写像πqtによる像(πqt)Pを算出する。そして、有理点入力部において入力された有理点P(xp,yp)∈Etのk倍点であるkPのフロベニウス展開式(d0+d1πqt+…+dm(πqt)m-1)Pに、自己準同写像演算部によって算出された像(πqt)Pを代入し、kPを算出する。
【００３０】
ここで、写像πqtは、標数２の場合において、ツイスト楕円曲線Et上の点をツイスト楕円曲線Et上に写す自己準同型の写像であり、((πqt)2-wπqt+q)R=O (-2√q≦w≦2√q)を満たすものである。従って、標数２の場合におけるツイスト楕円曲線Et上のスカラー倍演算kPは、kP=(d0+d1πqt+…+dm(πq)m-1)Pとフロベニウス展開でき、この各要素の置き換えのみによって、このスカラー倍演算kPを行うことができる。その結果、標数２の場合において、ツイスト楕円曲線上のスカラー倍演算を高速化することができる。
【図面の簡単な説明】
【図１】楕円曲線上スカラー倍演算装置の全体構成を例示した機能ブロック図。
【図２】（ａ）は、この形態の楕円曲線上スカラー倍演算装置１のハードウェア構成を例示したブロック図であり、（ｂ）は、自己準同写像演算部の機能構成の詳細を例示した図である。
【図３】スカラー倍演算部の機能構成の詳細を例示した図。
【図４】楕円曲線上スカラー倍演算装置の処理機能を説明するためのフローチャート。
【符号の説明】
１  楕円曲線上スカラー倍演算装置
１０  有理点入力部
２０  自己準同像算出部
３０  スカラー倍算出部
【図１】
0004184120.tif 000016
【図２】
0004184120.tif 000017
【図３】
0004184120.tif 000018
【図４】
0004184120.tif 000019