楕円スカラー倍演算装置、方法及びプログラム
【課題】標数３の有限体Ｆ３＾ｍ上定義されたｐｒｏｊｅｃｔｉｖｅ座標上の超特異楕円曲線Ｅ（Ｆ３＾ｍ）上の点Ｐ（Ｘ１，Ｙ１，１）の楕円スカラー倍演算において行われる楕円加算を効率良く行う。
【解決手段】ある乗数（例えばＺ２）について乗算する際に生成された事前演算結果（Ｚ２’）を記憶しておき、その乗数と同一の乗数（Ｚ２）について多項式乗算をする際に既に生成されたその事前演算結果（Ｚ２’）を再利用する。これにより、同一の乗数についての再度事前演算をする処理を省くことができる。したがって、楕円加算を効率良く行うことができる。
【解決手段】ある乗数（例えばＺ２）について乗算する際に生成された事前演算結果（Ｚ２’）を記憶しておき、その乗数と同一の乗数（Ｚ２）について多項式乗算をする際に既に生成されたその事前演算結果（Ｚ２’）を再利用する。これにより、同一の乗数についての再度事前演算をする処理を省くことができる。したがって、楕円加算を効率良く行うことができる。
【発明の詳細な説明】
【技術分野】
【０００１】
この発明は、暗号技術に関し、特にＩＤベース暗号等において楕円曲線上の点を楕円スカラー倍演算する技術に関する。
【背景技術】
【０００２】
情報通信技術に不可欠な技術として公開鍵暗号技術が知られている。しかし、ＲＳＡなどの公開鍵暗号は、公開鍵の管理が煩雑で管理コストが高いといった問題がある。近年、このような問題を解決する技術として任意のビット列であるID∈{0,1}*を公開鍵として用いるＩＤベース暗号が提案された（例えば、非特許文献１参照）。
【０００３】
ＩＤベース暗号では、任意のビット列であるID∈{0,1}*を楕円曲線上の点に変換し、この楕円曲線上でペアリング演算や楕円スカラー倍演算などを行って暗号化処理や秘密鍵生成処理を行う。近年、ペアリング演算を高速に行える楕円曲線として、標数３の有限体Ｆ３＾ｍ上で定義された超特異（Supersingular）楕円曲線が注目されている。
【０００４】
楕円スカラー倍演算は、楕円三倍算と楕円加算とを用いて行われる。楕円三倍算と楕円加算とを用いて楕円曲線Ｅ（Ｆ３＾ｍ）上の点Ｐ∈Ｅ（Ｆ３＾ｍ）をｎ倍する楕円スカラー倍演算アルゴリズムの例を以下に示す（例えば、非特許文献１参照。）。ｎは、ｎ＝Σｉ＝０Ｌ−１ｎｉ３ｉとして三進数で展開されるとする。この例では、「３．」において楕円三倍算が行われ、「４．」「５．」において楕円加算が行われている。
【０００５】
［楕円スカラー倍演算アルゴリズム］
１．Ｔ←Ｐ
２．ｆｏｒ ｉ＝Ｌ−２ ｄｏｗｎ ｔｏ ０ ｄｏ
３． Ｔ←［３］Ｔ
４． ｉｆ ｎｉ＝１ ｔｈｅｎ Ｔ←Ｔ＋Ｐ
５． ｉｆ ｎｉ＝−１ ｔｈｅｎ Ｔ←Ｔ−Ｐ
６．ｔｈｅｎ Ｔ
【０００６】
従来から行われている、プロジェクティブ座標上において点Ｐ（Ｘ１，Ｙ１，１）と点Ｑ（Ｘ２，Ｙ２，Ｚ２）とを楕円加算して点Ｒ（Ｘ３，Ｙ３，Ｚ３）を求める楕円加算アルゴリズムの例を以下に挙げる（例えば、非特許文献２参照。）。
１．Ａ＝Ｘ１Ｚ２−Ｘ２
２．Ｂ＝Ｙ１Ｚ２−Ｙ２
３．Ｃ＝Ａ３
４．Ｄ＝Ｃ２−Ｂ２Ｚ２
５．Ｘ３＝Ｘ２Ｃ−ＡＤ
６．Ｙ３＝ＢＤ−Ｙ２Ｃ
７．Ｚ３＝ＣＺ２
【先行技術文献】
【非特許文献】
【０００７】
【非特許文献１】Roberto M. Avanzi, Henri Cohen, Christophe Doche, Gerhard Frey, Tanja Lange, Kim Nguyen, Frederik Vercauteren, “Handbook of Elliptic and Hyperelliptic Curve Cryptography”, Henri Cohen, Gerhard Frey, Christophe Doche, 7/19/2005
【非特許文献２】Paulo S. L. M. Barreto1, Hae Y. Kim1, Ben Lynn2, and Michael Scott3, “Efficient Algorithms for Pairing-Based Cryptosystems”
【発明の概要】
【発明が解決しようとする課題】
【０００８】
ＩＤベース暗号においては、楕円スカラー倍演算を高速に行うことが求められており、そのために楕円加算を高速に行う必要がある。しかしながら、上記楕円加算アルゴリズムを効率的に行う技術は知られていなかった。
【課題を解決するための手段】
【０００９】
ある乗数について乗算する際に生成された事前演算結果を記憶しておき、その乗数と同一の乗数について多項式乗算をする際に既に生成されたその事前演算結果を再利用する。
【発明の効果】
【００１０】
既に生成された事前演算結果を再利用することにより、同一の乗数についての再度事前演算結果を求める処理を省くことができる。したがって、楕円加算の処理速度が上がり、楕円スカラー倍演算の処理速度も上がる。
【図面の簡単な説明】
【００１１】
【図１】第一演算部の例の機能ブロック図。
【図２】第二演算部の例の機能ブロック図。
【図３】第三演算部の例の機能ブロック図。
【図４】第四演算部の例の機能ブロック図。
【図５】第五演算部の例の機能ブロック図。
【図６】第六演算部の例の機能ブロック図。
【図７】第七演算部の例の機能ブロック図。
【図８】この発明による楕円スカラー倍演算装置の例の機能ブロック図。
【図９】事前演算結果を例示する図。
【図１０】この発明による乗算スケジュールを示す図。
【発明を実施するための形態】
【００１２】
［有限体乗算について］
標数３の基礎体Ｆ３＝｛０，１，２｝のｍ次拡大体である有限体Ｆ３＾ｍについての多項式乗算
Ｃ（ｘ）＝Ａ（ｘ）・Ｂ（ｘ）
を例に挙げて説明をする。有限体乗算とは、入力Ａ（ｘ），Ｂ（ｘ）∈Ｆ３＾ｍから、出力Ｃ（ｘ）∈Ｆ３＾ｍを求めることをいう。ここで、標数３の有限体Ｆ３＾ｍの元Ａ（ｘ），Ｂ（ｘ），Ｃ（ｘ）は、コンピュータ上では基礎体Ｆ３の元を係数とする多項式として次のように表される。楕円曲線Ｅ（Ｆ３＾ｍ）上の点Ｐ（Ｘ１，Ｙ１，Ｚ１）、点Ｑ（Ｘ２，Ｙ２，Ｚ２）、点Ｒ（Ｘ３，Ｙ３，Ｚ３）の各座標の値Ｘ１，Ｙ１，１，Ｘ２，Ｙ２，Ｚ２，Ｘ３，Ｙ３，Ｚ３も同様に、コンピュータ上では基礎体Ｆ３の元を係数とする多項式として表される。ここで、ｉ＝０，…，ｍ−１として、ａｉ∈Ｆ３，ｂｉ∈Ｆ３，ｃｉ∈Ｆ３である。
【００１３】
Ａ（ｘ）＝ａ０＋ａ１ｘ＋ａ２ｘ２＋…＋ａｍ−１ｘｍ−１
Ｂ（ｘ）＝ｂ０＋ｂ１ｘ＋ｂ２ｘ２＋…＋ｂｍ−１ｘｍ−１
Ｃ（ｘ）＝ｃ０＋ｃ１ｘ＋ｃ２ｘ２＋…＋ｃ２ｍ−２ｘ２ｍ−２
【００１４】
この有限体乗算は、いわゆるＷｉｎｄｏｗ法等の手法によって高速処理が可能となる。Ｗｉｎｄｏｗ法は、Ａ（ｘ）に対して事前演算を行い事前演算結果を求め、その事前演算結果を用いてＢ（ｘ）の走査時に複数の係数ｂｉを同時に確認して加算を行うアルゴリズムのことである。ここで、１度に確認する係数の個数Ｗｓを、（ｂｉ＋ｗｓ−１，ｂｉ＋ｗｓ−２，…，ｂｉ）をウィンドウサイズＷｓとする。Ｗｉｎｄｏｗ法は、（１）事前演算と、（２）多項式演算と、（３）リダクションの３段階からなる。
【００１５】
Ａ（ｘ）に対する事前演算とは、項数ＷｓのＷｓ−１次多項式
Ｗ（ｘ）＝ｗ０＋ｗ１ｘ＋ｗ２ｘ２＋…＋ｗＷｓ−１ｘＷｓ−１（ｗｉ∈｛０，１，２｝）
のすべての組合せのそれぞれに対して、Ａ（ｘ）×Ｗ（ｘ）の結果を求めることをいう。言い換えると、有限体Ｆ３を基礎体とするｍ次拡大体Ｆ３＾ｍの元であり多項式で表現されるＡ（ｘ）を、その有限体Ｆ３の元を係数とする項数Ｗｓの各多項式Ｗ（ｘ）と演算することである。ある係数ｗｉ∈｛０，１，２｝の組｛ｗ０，ｗ１，ｗ２，…，ｗＷｓ−１｝についてのＡ（ｘ）×Ｗ（ｘ）の事前演算結果をＡ’［ｗ０，ｗ１，ｗ２，…，ｗＷｓ−１］∈Ｆ３＾ｍとする。この演算により、例えば、図９に例示するような事前演算結果を得ることができる。このように事前演算結果とは、Ｗｓ個の係数の各組と、その演算結果とを対応づけたものである。換言すると、事前演算結果とは、項数Ｗｓの各多項式と、その演算結果を対応づけたものである。
【００１６】
次に、事前演算結果を用いた多項式乗算について説明をする。ｍ次多項式であるＢ（ｘ）は、項数Ｗｓの多項式に分割される。より詳細には、項数Ｗｓの多項式に分割された後に、項数Ｗｓの分割された各多項式は共通するｘの累乗で括られる。
【００１７】
B(x)= (b0+b1x+b2x2+…+bWs-1xWs-1)
+(bWs+b+Ws+1x+bWs+2x2+…+b2Ws-1xWs-1)xWs
…
+(bm-Ws+bm-Ws+1x+bm-Ws+2x2+…+bm-1xm-1)xm-Ws
【００１８】
この場合、Ａ（ｘ）・Ｂ（ｘ）を以下のように書くことができる。
A(x)・B(x)= A(x)・(b0+b1x+b2x2+…+bWs-1xWs-1)
+A(x)・(bWs+b+Ws+1x+bWs+2x2+…+b2Ws-1xWs-1)xWs
…
+A(x)・(bm-Ws+bm-Ws+1x+bm-Ws+2x2+…+bm-1xWs-1)xm-Ws
【００１９】
事前演算において、Ａ（ｘ）と項数Ｗｓの各多項式Ｗ（ｘ）との積は計算してあるので、事前演算結果を参照することにより、Ａ（ｘ）と分割された項数Ｗｓの各多項式との積は容易に求めることができる。すなわち、分割された項数Ｗｓの多項式のＷｓ個の係数の組に対応する演算結果を参照する。そして、その分割された項数Ｗｓの多項式が、ｘの累乗で括ったものであれば、その演算結果にそのｘの累乗をかけることにより、Ａ（ｘ）と分割された項数Ｗｓの各多項式との積を求めることができる。
【００２０】
A(x)・B(x)= A[b0,b1,b2,…,bWs-1]
+A[bWs,bWs+1,bWs+2,…,b2Ws-1]xWs
…
+A[bm-Ws,bm-Ws+1,bm-Ws+2,…,bm-1]xm-Ws
【００２１】
このようにして求まったＡ（ｘ）と分割された項数Ｗｓの各多項式との積を加算することにより、Ｃ（ｘ）＝Ａ（ｘ）・Ｂ（ｘ）が計算される。
【００２２】
リダクションとは、基礎体Ｆ３から拡大体Ｆ３＾ｍを作るために定義した既約多項式ｆ（ｘ）でＣ（ｘ）を割った余りを求めることである。リダクションは演算結果であるＣ（ｘ）に対して行うだけではなく、Ａ（ｘ）×Ｂ（ｘ）の演算過程で適宜行ってもよい。
Ｗｉｎｄｏｗ法は、参考文献１に詳しく説明がされている。
【００２３】
〔参考文献１〕
川原祐人、他３名、「ηＴペアリングの高速ソフトウェア実装」、ＳＣＩＳ２００７、２００７、２００７年１月２３日−６日
【００２４】
［実施形態］
この発明による楕円スカラー倍演算装置の一実施形態を説明する。
ＩＤベース暗号で用いられるＩＤは、ハッシュ関数等でａｆｆｉｎｅ座標上の点（Ｘ１，Ｙ１）にまず変換される。しかし、ａｆｆｉｎｅ座標においては、逆元の計算に時間がかかることが知られている。したがって、この発明では、楕円スカラー倍演算を高速に行うために、点（Ｘ１，Ｙ１）をａｆｆｉｎｅ座標上からｐｒｏｊｅｃｔｉｖｅ座標上に変換した点Ｐ（Ｘ１，Ｙ１，１）について楕円スカラー倍演算を行うことにする。この発明による楕円スカラー倍演算装置は、入力されたａｆｆｉｎｅ座標とｐｒｏｊｅｃｔｉｖｅ座標とを互いに変換する座標変換部５００（図８）を有していても良い。
【００２５】
ｐｒｏｊｅｃｔｉｖｅ座標は、射影座標ともいう。予めＺが定められており、ａｆｆｉｎｅ座標の点（Ｘ，Ｙ）の各成分をＺ倍して、Ｚ成分を付加することにより、ａｆｆｉｎｅ座標の点（Ｘ，Ｙ）をｐｒｏｊｅｃｔｉｖｅ座標の点（Ｘ・Ｚ，Ｙ・Ｚ，Ｚ）に変換することができる。逆にｐｒｏｊｅｃｔｉｖｅ座標の点（Ｘ，Ｙ，Ｚ）のＸＹ成分をそれぞれＺで割り、Ｚ成分を削除することにより、ｐｒｏｊｅｃｔｉｖｅ座標の点（Ｘ，Ｙ，Ｚ）をａｆｆｉｎｅ座標の点（Ｘ／Ｚ，Ｙ／Ｚ）に変換することができる。この発明では、ａｆｆｉｎｅ座標の点（Ｘ１，Ｙ１）は、Ｚ１＝１として、ｐｒｏｊｅｃｔｉｖｅ座標の点Ｐ（Ｘ１，Ｙ１，１）に変換されている。
【００２６】
楕円スカラー倍演算は、楕円三倍算と楕円加算とを用いて行われる。楕円三倍算と楕円加算とを用いて楕円曲線Ｅ（Ｆ３＾ｍ）上の点Ｐ∈Ｅ（Ｆ３＾ｍ）をｎ倍する楕円スカラー倍演算アルゴリズムの例を以下に示す（例えば、非特許文献１参照。）。ｎは、ｎ＝Σｉ＝０Ｌ−１ｎｉ３ｉとして三進数で展開されるとする。この例では、「３．」において楕円三倍算が行われ、「４．」「５．」において楕円加算が行われている。
【００２７】
［楕円スカラー倍演算アルゴリズム］
１．Ｔ←Ｐ
２．ｆｏｒ ｉ＝Ｌ−２ ｄｏｗｎ ｔｏ ０ ｄｏ
３． Ｔ←［３］Ｔ
４． ｉｆ ｎｉ＝１ ｔｈｅｎ Ｔ←Ｔ＋Ｐ
５． ｉｆ ｎｉ＝−１ ｔｈｅｎ Ｔ←Ｔ−Ｐ
６．ｔｈｅｎ Ｔ
【００２８】
この発明では、「４．」「５．」において行われる楕円加算を効率良く行うことにより、楕円スカラー倍演算全体の処理速度を上げようとする。以下、点Ｐ（Ｘ１，Ｙ１，１）∈Ｅ（Ｆ３＾ｍ）と点Ｑ（Ｘ２，Ｙ２，Ｚ２）∈Ｅ（Ｆ３＾ｍ）とを楕円加算して、点Ｒ（Ｘ３，Ｙ３，Ｚ３）∈Ｅ（Ｆ３＾ｍ）を効率良く求める方法について説明する。Ｘ１，Ｙ１，Ｘ２，Ｙ２，Ｚ２，Ｘ３，Ｙ３，Ｚ３のそれぞれは、有限体Ｆ３＾ｍの元である。上記のようにＺ１＝１であり、楕円スカラー倍演算を行う対象である点が点Ｐ（Ｘ１，Ｙ１，１）である場合には、非特許文献２に記載されている下記の楕円加算は、図１０に示した乗算スケジュールにより効率良く行うことができる。
【００２９】
１．Ａ＝Ｘ１Ｚ２−Ｘ２
２．Ｂ＝Ｙ１Ｚ２−Ｙ２
３．Ｃ＝Ａ３
４．Ｄ＝Ｃ２−Ｂ２Ｚ２
５．Ｘ３＝Ｘ２Ｃ−ＡＤ
６．Ｙ３＝ＢＤ−Ｙ２Ｃ
７．Ｚ３＝ＣＺ２
【００３０】
＜ステップＳ１＞
第一演算部１（図１）は、Ｚ２についての事前演算結果Ｚ２’を求め、その事前演算結果Ｚ２’を用いてＸ１Ｚ２について多項式乗算することにより、Ａ＝Ｘ１Ｚ２−Ｘ２を演算する（ステップＳ１）。第一演算部１は、第一事前演算部１１、第一事前演算結果記憶部１２、第一多項式乗算部１３及び第一加算部１４を備える。
【００３１】
まず、第一事前演算部１１は、Ｚ２についての事前演算を行い事前演算結果Ｚ２’を生成する。事前演算結果Ｚ２’は、第一事前演算結果記憶部１２に記憶される。第一多項式乗算部１３は、第一事前演算結果記憶部１２から読み込んだ事前演算結果Ｚ２’を用いて、Ｘ１Ｚ２を多項式乗算する。生成されたＸ１Ｚ２は、第一加算部に送られる。第一加算部１４は、生成されたＸ１Ｚ２とＸ２とを用いて、Ａ＝Ｘ１Ｚ２−Ｘ２を演算する。
【００３２】
＜ステップＳ２＞
第二演算部２（図２）は、事前演算結果Ｚ２’を用いてＹ１Ｚ２について多項式乗算することにより、Ｂ＝Ｙ１Ｚ２−Ｙ２を演算する（ステップＳ２）。
【００３３】
第二多項式乗算部２１は、第一事前演算結果記憶部１２から読み込んだ事前演算結果Ｚ２’を用いて、Ｙ１Ｚ２について多項式乗算する。生成されたＹ１Ｚ２は、第二加算部２２に送られる。第二加算部２２は、生成されたＹ１Ｚ２とＹ２とを用いて、Ｂ＝Ｙ１Ｚ２−Ｙ２を演算する。
【００３４】
＜ステップＳ３＞
第三演算部３（図３）は、Ｃ＝Ａ３を演算する（ステップＳ３）。楕円三乗算はフロベニウスマップを用いて高速に演算することができる。
【００３５】
＜ステップＳ４＞
第四演算部４（図４）は、Ｂについての事前演算結果Ｂ’を求め、その事前演算結果Ｂ’を用いてｔ１＝Ｂ２を多項式乗算し、上記事前演算結果Ｚ２’を用いてｔ１Ｚ２を多項式乗算することにより、Ｄ＝Ｃ−Ｂ２Ｚ２を演算する（ステップＳ４）。
【００３６】
第四事前演算部４１は、Ｂについての事前演算を行い事前演算結果Ｂ’を生成する。事前演算結果Ｂ’は、第四事前演算結果記憶部４２に記憶される。第四Ａ多項式乗算部４３は、事前演算結果Ｂ’を用いて、Ｂ２を演算する。第四Ｂ多項式乗算部４４は、第一事前演算結果記憶部１２から読み込んだＺ２’とＢ２とを用いて、Ｂ２Ｚ２について多項式乗算を行う。第四加算部４５は、生成されたＢ２Ｚ２とＣとを用いて、Ｄ＝Ｃ−Ｂ２Ｚ２を演算する。
【００３７】
＜ステップＳ５＞
第五演算部５（図５）は、Ｃについての事前演算結果Ｃ’を求め、その事前演算結果Ｃ’を用いてＸ２Ｃを多項式乗算し、Ａ又はＤについての事前演算結果Ａ’又はＤ’を求め、その事前演算結果Ａ’又はＤ’を用いてＡＤを多項式乗算することにより、Ｘ３＝Ｘ２Ｃ−ＡＤを演算する（ステップＳ５）。
【００３８】
第五Ａ事前演算部５１は、Ｃについて事前演算を行い事前演算結果Ｃ’を求める。事前演算結果Ｃは、第五Ａ事前演算結果記憶部５２に記憶される。第五Ａ多項式乗算部５３は、第五Ａ事前演算結果記憶部５２から読み込んだＣ’を用いて、Ｘ２Ｃについて多項式乗算を行う。Ｘ２Ｃは、第五加算部５７に送られる。
【００３９】
第五Ｂ事前演算部５４は、Ａ又はＤについて事前演算を行い、事前演算結果Ａ’又は事前演算結果Ｄ’を生成する。事前演算結果Ａ’又は事前演算結果Ｄ’は、第五Ｂ事前演算結果記憶部５５に記憶させる。第五Ｂ多項式乗算部５６は、第五Ｂ事前演算結果記憶部５５から読み込んだ事前演算結果Ａ’又はＤ’を用いて、ＡＤについて多項式乗算する。ＡＤは、第五加算部５７に送られる。
第五加算部５７は、Ｘ３Ｃ及びＡＤを用いて、Ｘ３＝Ｘ２Ｃ−ＡＤを演算する。
【００４０】
＜ステップＳ６＞
第六演算部６（図６）は、事前演算結果Ｂ’又はＤ’を用いてＢＤを多項式乗算し、上記事前演算結果Ｃ’を用いてＹ２Ｃを多項式乗算することにより、Ｙ３＝ＢＤ−Ｙ２Ｃを演算する（ステップＳ６）。
【００４１】
第六Ａ多項式乗算部６１は、第四事前演算結果記憶部４２から読み込んだ事前演算結果Ｂ’を用いて、ＢＤについて多項式乗算する。ＢＤは、第六加算部６３に送られる。なお、図６において破線で示すように、第六Ａ多項式乗算部６１は、第五Ｂ事前演算結果記憶部５５から読み込んだ事前演算結果Ｄ’を用いて、ＢＤについて多項式乗算してもよい。
【００４２】
第六Ｂ多項式乗算部６２は、第五Ａ事前演算結果記憶部５２から読み込んだ事前演算結果Ｃ’を用いて、Ｙ２Ｃについて多項式乗算する。Ｙ２Ｃは、第六加算部６３に送られる。
第六加算部６３は、ＢＤとＹ２Ｃを用いて、Ｙ３＝ＢＤ−Ｙ２Ｃを演算する。
【００４３】
＜ステップＳ７＞
第七演算部７（図７）は、事前演算結果Ｚ２’又はＣ’を用いて、ＣＺ２を多項式乗算することにより、Ｚ３＝ＣＺ２を演算する（ステップＳ７）。
【００４４】
第七多項式乗算部７１は、ＣＺ２を多項式乗算する際に、第一事前演算結果記憶部１２から読み込んだ事前演算結果Ｚ２’を用いても良いし、図７に破線で示すように、第五Ａ事前演算結果記憶部５２から読み込んだ事前演算結果Ｃ’を用いてもよい。
【００４５】
なお、リダクションについてはふれていないが、リダクション部４００（図１０）が適宜所定の既約多項式ｆ（ｘ）を用いてリダクションを行うものとする。
【００４６】
このように、ある乗数について乗算する際に生成された事前演算結果を記憶しておき、その乗数と同一の乗数について多項式乗算をする際に既に生成されたその事前演算結果を再利用することにより、事前演算の回数を少なくすることができる。
【００４７】
従来は、多項式乗算をする度に事前計算を行っていた。したがって、事前演算は、多項式乗算の回数と同一の回数である９回行っていた。この発明により、図１０に示すように事前演算の回数は４回となる。したがって、楕円加算の処理速度、ひいては楕円スカラー倍演算の処理速度が従来よりも上がる。
【００４８】
なお、点Ｐ（Ｘ１，Ｙ１，Ｚ１）∈Ｅ（Ｆ３＾ｍ）を３倍した点Ｒ（Ｘ３，Ｙ３，Ｚ３）を求める楕円三倍算アルゴリズムを以下に例示する。ｂは±１である。楕円三倍算部２００はこのアルゴリズムを実行することにより楕円三倍算を行う。
１．Ｘ３＝Ｘ１９−ｂＺ１９
２．Ｙ３＝−Ｙ１９
３．Ｚ３＝−Ｚ１９
【００４９】
楕円スカラー倍演算装置は、単一の事前演算部１０１、事前演算結果記憶部１０２、多項式乗算部１０３及び加算部１０４を有していても良い。この場合の楕円スカラー倍演算装置の機能ブロック図を図８に例示する。楕円スカラー倍演算装置は、楕円加算部１００、楕円三倍算部２００、記憶部３０１、通信部３０２、及び、各部の動作を制御する制御部３０３、リダクション部４００を備える。また、楕円加算部１００は、事前演算部１０１、事前演算結果記憶部１０２、多項式乗算部１０３及び加算部１０４を備える。
【００５０】
この場合、事前演算部１０１が第一事前演算部１１、第四事前演算部４１、第五Ａ事前演算部５１及び第五Ｂ事前演算部５４として機能し、事前演算結果記憶部１０２が、第一事前演算結果記憶部１２、第四事前演算結果記憶部４２、第五Ａ事前演算結果記憶部５２及び第五Ｂ事前演算結果記憶部５５として機能し、多項式乗算部１０３が第一多項式乗算部１３、第二多項式乗算部２１、第四Ａ多項式乗算部４３、第四Ｂ多項式乗算部４４、第五Ａ多項式乗算部５３、第五Ｂ多項式乗算部５６、第六Ａ多項式乗算部６１、第六Ｂ多項式乗算部６２及び第七多項式乗算部７１として機能し、加算部１０４が第一加算部１４、第二加算部２２、第四加算部４５、第五加算部５７及び第六加算部６３として機能する。
【００５１】
各部間で直接データがやり取りされてもよいし、記憶部３０１を介してデータがやり取りされてもよい。
【００５２】
楕円スカラー倍演算装置は、コンピュータによって実現することができる。この場合、これらの装置がそれぞれ有すべき機能の処理内容はプログラムによって記述される。そして、このプログラムをコンピュータで実行することにより、これらの装置における各処理機能が、コンピュータ上で実現される。
【００５３】
この処理内容を記述したプログラムは、コンピュータで読み取り可能な記録媒体に記録しておくことができる。また、この形態では、コンピュータ上で所定のプログラムを実行させることにより、これらの装置を構成することとしたが、これらの処理内容の少なくとも一部をハードウェア的に実現することとしてもよい。
【００５４】
この発明は、上述の実施形態に限定されるものではなく、本発明の趣旨を逸脱しない範囲で適宜変更が可能である。
【符号の説明】
【００５５】
１ 第一演算部
２ 第二演算部
３ 第三演算部
４ 第四演算部
５ 第五演算部
６ 第六演算部
７ 第七演算部
１００ 楕円加算部
１０１ 事前演算部
１０２ 事前演算結果記憶部
１０３ 多項式乗算部
１０４ 加算部
２００ 楕円三倍算部
【技術分野】
【０００１】
この発明は、暗号技術に関し、特にＩＤベース暗号等において楕円曲線上の点を楕円スカラー倍演算する技術に関する。
【背景技術】
【０００２】
情報通信技術に不可欠な技術として公開鍵暗号技術が知られている。しかし、ＲＳＡなどの公開鍵暗号は、公開鍵の管理が煩雑で管理コストが高いといった問題がある。近年、このような問題を解決する技術として任意のビット列であるID∈{0,1}*を公開鍵として用いるＩＤベース暗号が提案された（例えば、非特許文献１参照）。
【０００３】
ＩＤベース暗号では、任意のビット列であるID∈{0,1}*を楕円曲線上の点に変換し、この楕円曲線上でペアリング演算や楕円スカラー倍演算などを行って暗号化処理や秘密鍵生成処理を行う。近年、ペアリング演算を高速に行える楕円曲線として、標数３の有限体Ｆ３＾ｍ上で定義された超特異（Supersingular）楕円曲線が注目されている。
【０００４】
楕円スカラー倍演算は、楕円三倍算と楕円加算とを用いて行われる。楕円三倍算と楕円加算とを用いて楕円曲線Ｅ（Ｆ３＾ｍ）上の点Ｐ∈Ｅ（Ｆ３＾ｍ）をｎ倍する楕円スカラー倍演算アルゴリズムの例を以下に示す（例えば、非特許文献１参照。）。ｎは、ｎ＝Σｉ＝０Ｌ−１ｎｉ３ｉとして三進数で展開されるとする。この例では、「３．」において楕円三倍算が行われ、「４．」「５．」において楕円加算が行われている。
【０００５】
［楕円スカラー倍演算アルゴリズム］
１．Ｔ←Ｐ
２．ｆｏｒ ｉ＝Ｌ−２ ｄｏｗｎ ｔｏ ０ ｄｏ
３． Ｔ←［３］Ｔ
４． ｉｆ ｎｉ＝１ ｔｈｅｎ Ｔ←Ｔ＋Ｐ
５． ｉｆ ｎｉ＝−１ ｔｈｅｎ Ｔ←Ｔ−Ｐ
６．ｔｈｅｎ Ｔ
【０００６】
従来から行われている、プロジェクティブ座標上において点Ｐ（Ｘ１，Ｙ１，１）と点Ｑ（Ｘ２，Ｙ２，Ｚ２）とを楕円加算して点Ｒ（Ｘ３，Ｙ３，Ｚ３）を求める楕円加算アルゴリズムの例を以下に挙げる（例えば、非特許文献２参照。）。
１．Ａ＝Ｘ１Ｚ２−Ｘ２
２．Ｂ＝Ｙ１Ｚ２−Ｙ２
３．Ｃ＝Ａ３
４．Ｄ＝Ｃ２−Ｂ２Ｚ２
５．Ｘ３＝Ｘ２Ｃ−ＡＤ
６．Ｙ３＝ＢＤ−Ｙ２Ｃ
７．Ｚ３＝ＣＺ２
【先行技術文献】
【非特許文献】
【０００７】
【非特許文献１】Roberto M. Avanzi, Henri Cohen, Christophe Doche, Gerhard Frey, Tanja Lange, Kim Nguyen, Frederik Vercauteren, “Handbook of Elliptic and Hyperelliptic Curve Cryptography”, Henri Cohen, Gerhard Frey, Christophe Doche, 7/19/2005
【非特許文献２】Paulo S. L. M. Barreto1, Hae Y. Kim1, Ben Lynn2, and Michael Scott3, “Efficient Algorithms for Pairing-Based Cryptosystems”
【発明の概要】
【発明が解決しようとする課題】
【０００８】
ＩＤベース暗号においては、楕円スカラー倍演算を高速に行うことが求められており、そのために楕円加算を高速に行う必要がある。しかしながら、上記楕円加算アルゴリズムを効率的に行う技術は知られていなかった。
【課題を解決するための手段】
【０００９】
ある乗数について乗算する際に生成された事前演算結果を記憶しておき、その乗数と同一の乗数について多項式乗算をする際に既に生成されたその事前演算結果を再利用する。
【発明の効果】
【００１０】
既に生成された事前演算結果を再利用することにより、同一の乗数についての再度事前演算結果を求める処理を省くことができる。したがって、楕円加算の処理速度が上がり、楕円スカラー倍演算の処理速度も上がる。
【図面の簡単な説明】
【００１１】
【図１】第一演算部の例の機能ブロック図。
【図２】第二演算部の例の機能ブロック図。
【図３】第三演算部の例の機能ブロック図。
【図４】第四演算部の例の機能ブロック図。
【図５】第五演算部の例の機能ブロック図。
【図６】第六演算部の例の機能ブロック図。
【図７】第七演算部の例の機能ブロック図。
【図８】この発明による楕円スカラー倍演算装置の例の機能ブロック図。
【図９】事前演算結果を例示する図。
【図１０】この発明による乗算スケジュールを示す図。
【発明を実施するための形態】
【００１２】
［有限体乗算について］
標数３の基礎体Ｆ３＝｛０，１，２｝のｍ次拡大体である有限体Ｆ３＾ｍについての多項式乗算
Ｃ（ｘ）＝Ａ（ｘ）・Ｂ（ｘ）
を例に挙げて説明をする。有限体乗算とは、入力Ａ（ｘ），Ｂ（ｘ）∈Ｆ３＾ｍから、出力Ｃ（ｘ）∈Ｆ３＾ｍを求めることをいう。ここで、標数３の有限体Ｆ３＾ｍの元Ａ（ｘ），Ｂ（ｘ），Ｃ（ｘ）は、コンピュータ上では基礎体Ｆ３の元を係数とする多項式として次のように表される。楕円曲線Ｅ（Ｆ３＾ｍ）上の点Ｐ（Ｘ１，Ｙ１，Ｚ１）、点Ｑ（Ｘ２，Ｙ２，Ｚ２）、点Ｒ（Ｘ３，Ｙ３，Ｚ３）の各座標の値Ｘ１，Ｙ１，１，Ｘ２，Ｙ２，Ｚ２，Ｘ３，Ｙ３，Ｚ３も同様に、コンピュータ上では基礎体Ｆ３の元を係数とする多項式として表される。ここで、ｉ＝０，…，ｍ−１として、ａｉ∈Ｆ３，ｂｉ∈Ｆ３，ｃｉ∈Ｆ３である。
【００１３】
Ａ（ｘ）＝ａ０＋ａ１ｘ＋ａ２ｘ２＋…＋ａｍ−１ｘｍ−１
Ｂ（ｘ）＝ｂ０＋ｂ１ｘ＋ｂ２ｘ２＋…＋ｂｍ−１ｘｍ−１
Ｃ（ｘ）＝ｃ０＋ｃ１ｘ＋ｃ２ｘ２＋…＋ｃ２ｍ−２ｘ２ｍ−２
【００１４】
この有限体乗算は、いわゆるＷｉｎｄｏｗ法等の手法によって高速処理が可能となる。Ｗｉｎｄｏｗ法は、Ａ（ｘ）に対して事前演算を行い事前演算結果を求め、その事前演算結果を用いてＢ（ｘ）の走査時に複数の係数ｂｉを同時に確認して加算を行うアルゴリズムのことである。ここで、１度に確認する係数の個数Ｗｓを、（ｂｉ＋ｗｓ−１，ｂｉ＋ｗｓ−２，…，ｂｉ）をウィンドウサイズＷｓとする。Ｗｉｎｄｏｗ法は、（１）事前演算と、（２）多項式演算と、（３）リダクションの３段階からなる。
【００１５】
Ａ（ｘ）に対する事前演算とは、項数ＷｓのＷｓ−１次多項式
Ｗ（ｘ）＝ｗ０＋ｗ１ｘ＋ｗ２ｘ２＋…＋ｗＷｓ−１ｘＷｓ−１（ｗｉ∈｛０，１，２｝）
のすべての組合せのそれぞれに対して、Ａ（ｘ）×Ｗ（ｘ）の結果を求めることをいう。言い換えると、有限体Ｆ３を基礎体とするｍ次拡大体Ｆ３＾ｍの元であり多項式で表現されるＡ（ｘ）を、その有限体Ｆ３の元を係数とする項数Ｗｓの各多項式Ｗ（ｘ）と演算することである。ある係数ｗｉ∈｛０，１，２｝の組｛ｗ０，ｗ１，ｗ２，…，ｗＷｓ−１｝についてのＡ（ｘ）×Ｗ（ｘ）の事前演算結果をＡ’［ｗ０，ｗ１，ｗ２，…，ｗＷｓ−１］∈Ｆ３＾ｍとする。この演算により、例えば、図９に例示するような事前演算結果を得ることができる。このように事前演算結果とは、Ｗｓ個の係数の各組と、その演算結果とを対応づけたものである。換言すると、事前演算結果とは、項数Ｗｓの各多項式と、その演算結果を対応づけたものである。
【００１６】
次に、事前演算結果を用いた多項式乗算について説明をする。ｍ次多項式であるＢ（ｘ）は、項数Ｗｓの多項式に分割される。より詳細には、項数Ｗｓの多項式に分割された後に、項数Ｗｓの分割された各多項式は共通するｘの累乗で括られる。
【００１７】
B(x)= (b0+b1x+b2x2+…+bWs-1xWs-1)
+(bWs+b+Ws+1x+bWs+2x2+…+b2Ws-1xWs-1)xWs
…
+(bm-Ws+bm-Ws+1x+bm-Ws+2x2+…+bm-1xm-1)xm-Ws
【００１８】
この場合、Ａ（ｘ）・Ｂ（ｘ）を以下のように書くことができる。
A(x)・B(x)= A(x)・(b0+b1x+b2x2+…+bWs-1xWs-1)
+A(x)・(bWs+b+Ws+1x+bWs+2x2+…+b2Ws-1xWs-1)xWs
…
+A(x)・(bm-Ws+bm-Ws+1x+bm-Ws+2x2+…+bm-1xWs-1)xm-Ws
【００１９】
事前演算において、Ａ（ｘ）と項数Ｗｓの各多項式Ｗ（ｘ）との積は計算してあるので、事前演算結果を参照することにより、Ａ（ｘ）と分割された項数Ｗｓの各多項式との積は容易に求めることができる。すなわち、分割された項数Ｗｓの多項式のＷｓ個の係数の組に対応する演算結果を参照する。そして、その分割された項数Ｗｓの多項式が、ｘの累乗で括ったものであれば、その演算結果にそのｘの累乗をかけることにより、Ａ（ｘ）と分割された項数Ｗｓの各多項式との積を求めることができる。
【００２０】
A(x)・B(x)= A[b0,b1,b2,…,bWs-1]
+A[bWs,bWs+1,bWs+2,…,b2Ws-1]xWs
…
+A[bm-Ws,bm-Ws+1,bm-Ws+2,…,bm-1]xm-Ws
【００２１】
このようにして求まったＡ（ｘ）と分割された項数Ｗｓの各多項式との積を加算することにより、Ｃ（ｘ）＝Ａ（ｘ）・Ｂ（ｘ）が計算される。
【００２２】
リダクションとは、基礎体Ｆ３から拡大体Ｆ３＾ｍを作るために定義した既約多項式ｆ（ｘ）でＣ（ｘ）を割った余りを求めることである。リダクションは演算結果であるＣ（ｘ）に対して行うだけではなく、Ａ（ｘ）×Ｂ（ｘ）の演算過程で適宜行ってもよい。
Ｗｉｎｄｏｗ法は、参考文献１に詳しく説明がされている。
【００２３】
〔参考文献１〕
川原祐人、他３名、「ηＴペアリングの高速ソフトウェア実装」、ＳＣＩＳ２００７、２００７、２００７年１月２３日−６日
【００２４】
［実施形態］
この発明による楕円スカラー倍演算装置の一実施形態を説明する。
ＩＤベース暗号で用いられるＩＤは、ハッシュ関数等でａｆｆｉｎｅ座標上の点（Ｘ１，Ｙ１）にまず変換される。しかし、ａｆｆｉｎｅ座標においては、逆元の計算に時間がかかることが知られている。したがって、この発明では、楕円スカラー倍演算を高速に行うために、点（Ｘ１，Ｙ１）をａｆｆｉｎｅ座標上からｐｒｏｊｅｃｔｉｖｅ座標上に変換した点Ｐ（Ｘ１，Ｙ１，１）について楕円スカラー倍演算を行うことにする。この発明による楕円スカラー倍演算装置は、入力されたａｆｆｉｎｅ座標とｐｒｏｊｅｃｔｉｖｅ座標とを互いに変換する座標変換部５００（図８）を有していても良い。
【００２５】
ｐｒｏｊｅｃｔｉｖｅ座標は、射影座標ともいう。予めＺが定められており、ａｆｆｉｎｅ座標の点（Ｘ，Ｙ）の各成分をＺ倍して、Ｚ成分を付加することにより、ａｆｆｉｎｅ座標の点（Ｘ，Ｙ）をｐｒｏｊｅｃｔｉｖｅ座標の点（Ｘ・Ｚ，Ｙ・Ｚ，Ｚ）に変換することができる。逆にｐｒｏｊｅｃｔｉｖｅ座標の点（Ｘ，Ｙ，Ｚ）のＸＹ成分をそれぞれＺで割り、Ｚ成分を削除することにより、ｐｒｏｊｅｃｔｉｖｅ座標の点（Ｘ，Ｙ，Ｚ）をａｆｆｉｎｅ座標の点（Ｘ／Ｚ，Ｙ／Ｚ）に変換することができる。この発明では、ａｆｆｉｎｅ座標の点（Ｘ１，Ｙ１）は、Ｚ１＝１として、ｐｒｏｊｅｃｔｉｖｅ座標の点Ｐ（Ｘ１，Ｙ１，１）に変換されている。
【００２６】
楕円スカラー倍演算は、楕円三倍算と楕円加算とを用いて行われる。楕円三倍算と楕円加算とを用いて楕円曲線Ｅ（Ｆ３＾ｍ）上の点Ｐ∈Ｅ（Ｆ３＾ｍ）をｎ倍する楕円スカラー倍演算アルゴリズムの例を以下に示す（例えば、非特許文献１参照。）。ｎは、ｎ＝Σｉ＝０Ｌ−１ｎｉ３ｉとして三進数で展開されるとする。この例では、「３．」において楕円三倍算が行われ、「４．」「５．」において楕円加算が行われている。
【００２７】
［楕円スカラー倍演算アルゴリズム］
１．Ｔ←Ｐ
２．ｆｏｒ ｉ＝Ｌ−２ ｄｏｗｎ ｔｏ ０ ｄｏ
３． Ｔ←［３］Ｔ
４． ｉｆ ｎｉ＝１ ｔｈｅｎ Ｔ←Ｔ＋Ｐ
５． ｉｆ ｎｉ＝−１ ｔｈｅｎ Ｔ←Ｔ−Ｐ
６．ｔｈｅｎ Ｔ
【００２８】
この発明では、「４．」「５．」において行われる楕円加算を効率良く行うことにより、楕円スカラー倍演算全体の処理速度を上げようとする。以下、点Ｐ（Ｘ１，Ｙ１，１）∈Ｅ（Ｆ３＾ｍ）と点Ｑ（Ｘ２，Ｙ２，Ｚ２）∈Ｅ（Ｆ３＾ｍ）とを楕円加算して、点Ｒ（Ｘ３，Ｙ３，Ｚ３）∈Ｅ（Ｆ３＾ｍ）を効率良く求める方法について説明する。Ｘ１，Ｙ１，Ｘ２，Ｙ２，Ｚ２，Ｘ３，Ｙ３，Ｚ３のそれぞれは、有限体Ｆ３＾ｍの元である。上記のようにＺ１＝１であり、楕円スカラー倍演算を行う対象である点が点Ｐ（Ｘ１，Ｙ１，１）である場合には、非特許文献２に記載されている下記の楕円加算は、図１０に示した乗算スケジュールにより効率良く行うことができる。
【００２９】
１．Ａ＝Ｘ１Ｚ２−Ｘ２
２．Ｂ＝Ｙ１Ｚ２−Ｙ２
３．Ｃ＝Ａ３
４．Ｄ＝Ｃ２−Ｂ２Ｚ２
５．Ｘ３＝Ｘ２Ｃ−ＡＤ
６．Ｙ３＝ＢＤ−Ｙ２Ｃ
７．Ｚ３＝ＣＺ２
【００３０】
＜ステップＳ１＞
第一演算部１（図１）は、Ｚ２についての事前演算結果Ｚ２’を求め、その事前演算結果Ｚ２’を用いてＸ１Ｚ２について多項式乗算することにより、Ａ＝Ｘ１Ｚ２−Ｘ２を演算する（ステップＳ１）。第一演算部１は、第一事前演算部１１、第一事前演算結果記憶部１２、第一多項式乗算部１３及び第一加算部１４を備える。
【００３１】
まず、第一事前演算部１１は、Ｚ２についての事前演算を行い事前演算結果Ｚ２’を生成する。事前演算結果Ｚ２’は、第一事前演算結果記憶部１２に記憶される。第一多項式乗算部１３は、第一事前演算結果記憶部１２から読み込んだ事前演算結果Ｚ２’を用いて、Ｘ１Ｚ２を多項式乗算する。生成されたＸ１Ｚ２は、第一加算部に送られる。第一加算部１４は、生成されたＸ１Ｚ２とＸ２とを用いて、Ａ＝Ｘ１Ｚ２−Ｘ２を演算する。
【００３２】
＜ステップＳ２＞
第二演算部２（図２）は、事前演算結果Ｚ２’を用いてＹ１Ｚ２について多項式乗算することにより、Ｂ＝Ｙ１Ｚ２−Ｙ２を演算する（ステップＳ２）。
【００３３】
第二多項式乗算部２１は、第一事前演算結果記憶部１２から読み込んだ事前演算結果Ｚ２’を用いて、Ｙ１Ｚ２について多項式乗算する。生成されたＹ１Ｚ２は、第二加算部２２に送られる。第二加算部２２は、生成されたＹ１Ｚ２とＹ２とを用いて、Ｂ＝Ｙ１Ｚ２−Ｙ２を演算する。
【００３４】
＜ステップＳ３＞
第三演算部３（図３）は、Ｃ＝Ａ３を演算する（ステップＳ３）。楕円三乗算はフロベニウスマップを用いて高速に演算することができる。
【００３５】
＜ステップＳ４＞
第四演算部４（図４）は、Ｂについての事前演算結果Ｂ’を求め、その事前演算結果Ｂ’を用いてｔ１＝Ｂ２を多項式乗算し、上記事前演算結果Ｚ２’を用いてｔ１Ｚ２を多項式乗算することにより、Ｄ＝Ｃ−Ｂ２Ｚ２を演算する（ステップＳ４）。
【００３６】
第四事前演算部４１は、Ｂについての事前演算を行い事前演算結果Ｂ’を生成する。事前演算結果Ｂ’は、第四事前演算結果記憶部４２に記憶される。第四Ａ多項式乗算部４３は、事前演算結果Ｂ’を用いて、Ｂ２を演算する。第四Ｂ多項式乗算部４４は、第一事前演算結果記憶部１２から読み込んだＺ２’とＢ２とを用いて、Ｂ２Ｚ２について多項式乗算を行う。第四加算部４５は、生成されたＢ２Ｚ２とＣとを用いて、Ｄ＝Ｃ−Ｂ２Ｚ２を演算する。
【００３７】
＜ステップＳ５＞
第五演算部５（図５）は、Ｃについての事前演算結果Ｃ’を求め、その事前演算結果Ｃ’を用いてＸ２Ｃを多項式乗算し、Ａ又はＤについての事前演算結果Ａ’又はＤ’を求め、その事前演算結果Ａ’又はＤ’を用いてＡＤを多項式乗算することにより、Ｘ３＝Ｘ２Ｃ−ＡＤを演算する（ステップＳ５）。
【００３８】
第五Ａ事前演算部５１は、Ｃについて事前演算を行い事前演算結果Ｃ’を求める。事前演算結果Ｃは、第五Ａ事前演算結果記憶部５２に記憶される。第五Ａ多項式乗算部５３は、第五Ａ事前演算結果記憶部５２から読み込んだＣ’を用いて、Ｘ２Ｃについて多項式乗算を行う。Ｘ２Ｃは、第五加算部５７に送られる。
【００３９】
第五Ｂ事前演算部５４は、Ａ又はＤについて事前演算を行い、事前演算結果Ａ’又は事前演算結果Ｄ’を生成する。事前演算結果Ａ’又は事前演算結果Ｄ’は、第五Ｂ事前演算結果記憶部５５に記憶させる。第五Ｂ多項式乗算部５６は、第五Ｂ事前演算結果記憶部５５から読み込んだ事前演算結果Ａ’又はＤ’を用いて、ＡＤについて多項式乗算する。ＡＤは、第五加算部５７に送られる。
第五加算部５７は、Ｘ３Ｃ及びＡＤを用いて、Ｘ３＝Ｘ２Ｃ−ＡＤを演算する。
【００４０】
＜ステップＳ６＞
第六演算部６（図６）は、事前演算結果Ｂ’又はＤ’を用いてＢＤを多項式乗算し、上記事前演算結果Ｃ’を用いてＹ２Ｃを多項式乗算することにより、Ｙ３＝ＢＤ−Ｙ２Ｃを演算する（ステップＳ６）。
【００４１】
第六Ａ多項式乗算部６１は、第四事前演算結果記憶部４２から読み込んだ事前演算結果Ｂ’を用いて、ＢＤについて多項式乗算する。ＢＤは、第六加算部６３に送られる。なお、図６において破線で示すように、第六Ａ多項式乗算部６１は、第五Ｂ事前演算結果記憶部５５から読み込んだ事前演算結果Ｄ’を用いて、ＢＤについて多項式乗算してもよい。
【００４２】
第六Ｂ多項式乗算部６２は、第五Ａ事前演算結果記憶部５２から読み込んだ事前演算結果Ｃ’を用いて、Ｙ２Ｃについて多項式乗算する。Ｙ２Ｃは、第六加算部６３に送られる。
第六加算部６３は、ＢＤとＹ２Ｃを用いて、Ｙ３＝ＢＤ−Ｙ２Ｃを演算する。
【００４３】
＜ステップＳ７＞
第七演算部７（図７）は、事前演算結果Ｚ２’又はＣ’を用いて、ＣＺ２を多項式乗算することにより、Ｚ３＝ＣＺ２を演算する（ステップＳ７）。
【００４４】
第七多項式乗算部７１は、ＣＺ２を多項式乗算する際に、第一事前演算結果記憶部１２から読み込んだ事前演算結果Ｚ２’を用いても良いし、図７に破線で示すように、第五Ａ事前演算結果記憶部５２から読み込んだ事前演算結果Ｃ’を用いてもよい。
【００４５】
なお、リダクションについてはふれていないが、リダクション部４００（図１０）が適宜所定の既約多項式ｆ（ｘ）を用いてリダクションを行うものとする。
【００４６】
このように、ある乗数について乗算する際に生成された事前演算結果を記憶しておき、その乗数と同一の乗数について多項式乗算をする際に既に生成されたその事前演算結果を再利用することにより、事前演算の回数を少なくすることができる。
【００４７】
従来は、多項式乗算をする度に事前計算を行っていた。したがって、事前演算は、多項式乗算の回数と同一の回数である９回行っていた。この発明により、図１０に示すように事前演算の回数は４回となる。したがって、楕円加算の処理速度、ひいては楕円スカラー倍演算の処理速度が従来よりも上がる。
【００４８】
なお、点Ｐ（Ｘ１，Ｙ１，Ｚ１）∈Ｅ（Ｆ３＾ｍ）を３倍した点Ｒ（Ｘ３，Ｙ３，Ｚ３）を求める楕円三倍算アルゴリズムを以下に例示する。ｂは±１である。楕円三倍算部２００はこのアルゴリズムを実行することにより楕円三倍算を行う。
１．Ｘ３＝Ｘ１９−ｂＺ１９
２．Ｙ３＝−Ｙ１９
３．Ｚ３＝−Ｚ１９
【００４９】
楕円スカラー倍演算装置は、単一の事前演算部１０１、事前演算結果記憶部１０２、多項式乗算部１０３及び加算部１０４を有していても良い。この場合の楕円スカラー倍演算装置の機能ブロック図を図８に例示する。楕円スカラー倍演算装置は、楕円加算部１００、楕円三倍算部２００、記憶部３０１、通信部３０２、及び、各部の動作を制御する制御部３０３、リダクション部４００を備える。また、楕円加算部１００は、事前演算部１０１、事前演算結果記憶部１０２、多項式乗算部１０３及び加算部１０４を備える。
【００５０】
この場合、事前演算部１０１が第一事前演算部１１、第四事前演算部４１、第五Ａ事前演算部５１及び第五Ｂ事前演算部５４として機能し、事前演算結果記憶部１０２が、第一事前演算結果記憶部１２、第四事前演算結果記憶部４２、第五Ａ事前演算結果記憶部５２及び第五Ｂ事前演算結果記憶部５５として機能し、多項式乗算部１０３が第一多項式乗算部１３、第二多項式乗算部２１、第四Ａ多項式乗算部４３、第四Ｂ多項式乗算部４４、第五Ａ多項式乗算部５３、第五Ｂ多項式乗算部５６、第六Ａ多項式乗算部６１、第六Ｂ多項式乗算部６２及び第七多項式乗算部７１として機能し、加算部１０４が第一加算部１４、第二加算部２２、第四加算部４５、第五加算部５７及び第六加算部６３として機能する。
【００５１】
各部間で直接データがやり取りされてもよいし、記憶部３０１を介してデータがやり取りされてもよい。
【００５２】
楕円スカラー倍演算装置は、コンピュータによって実現することができる。この場合、これらの装置がそれぞれ有すべき機能の処理内容はプログラムによって記述される。そして、このプログラムをコンピュータで実行することにより、これらの装置における各処理機能が、コンピュータ上で実現される。
【００５３】
この処理内容を記述したプログラムは、コンピュータで読み取り可能な記録媒体に記録しておくことができる。また、この形態では、コンピュータ上で所定のプログラムを実行させることにより、これらの装置を構成することとしたが、これらの処理内容の少なくとも一部をハードウェア的に実現することとしてもよい。
【００５４】
この発明は、上述の実施形態に限定されるものではなく、本発明の趣旨を逸脱しない範囲で適宜変更が可能である。
【符号の説明】
【００５５】
１ 第一演算部
２ 第二演算部
３ 第三演算部
４ 第四演算部
５ 第五演算部
６ 第六演算部
７ 第七演算部
１００ 楕円加算部
１０１ 事前演算部
１０２ 事前演算結果記憶部
１０３ 多項式乗算部
１０４ 加算部
２００ 楕円三倍算部
【特許請求の範囲】
【請求項１】
標数３の有限体Ｆ３＾ｍ上定義されたｐｒｏｊｅｃｔｉｖｅ座標上の超特異楕円曲線上の点Ｐ（Ｘ１，Ｙ１，１）の楕円スカラー倍演算を、楕円三倍算と楕円加算とを用いて行う楕円スカラー倍演算装置において、
上記楕円加算は、上記超特異楕円曲線上の、点Ｐ（Ｘ１，Ｙ１，１）と点（Ｘ２，Ｙ２，Ｚ２）とを加算した点（Ｘ３，Ｙ３，Ｚ３）を演算するものであり、
Ｚ２についての事前演算結果Ｚ２’を求め、その事前演算結果Ｚ２’を用いてＸ１Ｚ２について多項式乗算することにより、Ａ＝Ｘ１Ｚ２−Ｘ２を演算する第一演算部と、
上記事前演算結果Ｚ２’を用いてＹ１Ｚ２について多項式乗算することにより、Ｂ＝Ｙ１Ｚ２−Ｙ２を演算する第二演算部と、
Ｃ＝Ａ３を演算する第三演算部と、
Ｂについての事前演算結果Ｂ’を求め、その事前演算結果Ｂ’を用いてｔ１＝Ｂ２を多項式乗算し、上記事前演算結果Ｚ２’を用いてｔ１Ｚ２を多項式乗算することにより、Ｄ＝Ｃ−Ｂ２Ｚ２を演算する第四演算部と、
Ｃについての事前演算結果Ｃ’を求め、その事前演算結果Ｃ’を用いてＸ２Ｃを多項式乗算し、Ａ又はＤについての事前演算結果Ａ’又はＤ’を求め、その事前演算結果Ａ’又はＤ’を用いてＡＤを多項式乗算することにより、Ｘ３＝Ｘ２Ｃ−ＡＤを演算する第五演算部と、
上記事前演算結果Ｂ’又はＤ’を用いてＢＤを多項式乗算し、上記事前演算結果Ｃ’を用いてＹ２Ｃを多項式乗算することにより、Ｙ３＝ＢＤ−Ｙ２Ｃを演算する第六演算部と、
上記事前演算結果Ｚ２’又はＣ’を用いて、ＣＺ２を多項式乗算することにより、Ｚ３＝ＣＺ２を演算する第七演算部と、
を含む楕円スカラー倍演算装置。
【請求項２】
標数３の有限体Ｆ３＾ｍ上定義されたｐｒｏｊｅｃｔｉｖｅ座標上の超特異楕円曲線上の点Ｐ（Ｘ１，Ｙ１，１）の楕円スカラー倍演算を、楕円三倍算と楕円加算とを用いて行う楕円スカラー倍演算方法において、
上記楕円加算は、上記超特異楕円曲線上の、点Ｐ（Ｘ１，Ｙ１，１）と点（Ｘ２，Ｙ２，Ｚ２）とを加算した点（Ｘ３，Ｙ３，Ｚ３）を演算するものであり、
Ｚ２についての事前演算結果Ｚ２’を求め、その事前演算結果Ｚ２’を用いてＸ１Ｚ２について多項式乗算することにより、Ａ＝Ｘ１Ｚ２−Ｘ２を演算する第一演算ステップと、
上記事前演算結果Ｚ２’を用いてＹ１Ｚ２について多項式乗算することにより、Ｂ＝Ｙ１Ｚ２−Ｙ２を演算する第二演算ステップと、
Ｃ＝Ａ３を演算する第三演算ステップと、
Ｂについての事前演算結果Ｂ’を求め、その事前演算結果Ｂ’を用いてｔ１＝Ｂ２を多項式乗算し、上記事前演算結果Ｚ２’を用いてｔ１Ｚ２を多項式乗算することにより、Ｄ＝Ｃ−Ｂ２Ｚ２を演算する第四演算ステップと、
Ｃについての事前演算結果Ｃ’を求め、その事前演算結果Ｃ’を用いてＸ２Ｃを多項式乗算し、Ａ又はＤについての事前演算結果Ａ’又はＤ’を求め、その事前演算結果Ａ’又はＤ’を用いてＡＤを多項式乗算することにより、Ｘ３＝Ｘ２Ｃ−ＡＤを演算する第五演算ステップと、
上記事前演算結果Ｂ’又はＤ’を用いてＢＤを多項式乗算し、上記事前演算結果Ｃ’を用いてＹ２Ｃを多項式乗算することにより、Ｙ３＝ＢＤ−Ｙ２Ｃを演算する第六演算ステップと、
上記事前演算結果Ｚ２’又はＣ’を用いて、ＣＺ２を多項式乗算することにより、Ｚ３＝ＣＺ２を演算する第七演算ステップと、
を含む楕円スカラー倍演算方法。
【請求項３】
請求項１に記載の楕円スカラー倍演算装置としてコンピュータを機能させるための楕円スカラー倍演算プログラム。
【請求項１】
標数３の有限体Ｆ３＾ｍ上定義されたｐｒｏｊｅｃｔｉｖｅ座標上の超特異楕円曲線上の点Ｐ（Ｘ１，Ｙ１，１）の楕円スカラー倍演算を、楕円三倍算と楕円加算とを用いて行う楕円スカラー倍演算装置において、
上記楕円加算は、上記超特異楕円曲線上の、点Ｐ（Ｘ１，Ｙ１，１）と点（Ｘ２，Ｙ２，Ｚ２）とを加算した点（Ｘ３，Ｙ３，Ｚ３）を演算するものであり、
Ｚ２についての事前演算結果Ｚ２’を求め、その事前演算結果Ｚ２’を用いてＸ１Ｚ２について多項式乗算することにより、Ａ＝Ｘ１Ｚ２−Ｘ２を演算する第一演算部と、
上記事前演算結果Ｚ２’を用いてＹ１Ｚ２について多項式乗算することにより、Ｂ＝Ｙ１Ｚ２−Ｙ２を演算する第二演算部と、
Ｃ＝Ａ３を演算する第三演算部と、
Ｂについての事前演算結果Ｂ’を求め、その事前演算結果Ｂ’を用いてｔ１＝Ｂ２を多項式乗算し、上記事前演算結果Ｚ２’を用いてｔ１Ｚ２を多項式乗算することにより、Ｄ＝Ｃ−Ｂ２Ｚ２を演算する第四演算部と、
Ｃについての事前演算結果Ｃ’を求め、その事前演算結果Ｃ’を用いてＸ２Ｃを多項式乗算し、Ａ又はＤについての事前演算結果Ａ’又はＤ’を求め、その事前演算結果Ａ’又はＤ’を用いてＡＤを多項式乗算することにより、Ｘ３＝Ｘ２Ｃ−ＡＤを演算する第五演算部と、
上記事前演算結果Ｂ’又はＤ’を用いてＢＤを多項式乗算し、上記事前演算結果Ｃ’を用いてＹ２Ｃを多項式乗算することにより、Ｙ３＝ＢＤ−Ｙ２Ｃを演算する第六演算部と、
上記事前演算結果Ｚ２’又はＣ’を用いて、ＣＺ２を多項式乗算することにより、Ｚ３＝ＣＺ２を演算する第七演算部と、
を含む楕円スカラー倍演算装置。
【請求項２】
標数３の有限体Ｆ３＾ｍ上定義されたｐｒｏｊｅｃｔｉｖｅ座標上の超特異楕円曲線上の点Ｐ（Ｘ１，Ｙ１，１）の楕円スカラー倍演算を、楕円三倍算と楕円加算とを用いて行う楕円スカラー倍演算方法において、
上記楕円加算は、上記超特異楕円曲線上の、点Ｐ（Ｘ１，Ｙ１，１）と点（Ｘ２，Ｙ２，Ｚ２）とを加算した点（Ｘ３，Ｙ３，Ｚ３）を演算するものであり、
Ｚ２についての事前演算結果Ｚ２’を求め、その事前演算結果Ｚ２’を用いてＸ１Ｚ２について多項式乗算することにより、Ａ＝Ｘ１Ｚ２−Ｘ２を演算する第一演算ステップと、
上記事前演算結果Ｚ２’を用いてＹ１Ｚ２について多項式乗算することにより、Ｂ＝Ｙ１Ｚ２−Ｙ２を演算する第二演算ステップと、
Ｃ＝Ａ３を演算する第三演算ステップと、
Ｂについての事前演算結果Ｂ’を求め、その事前演算結果Ｂ’を用いてｔ１＝Ｂ２を多項式乗算し、上記事前演算結果Ｚ２’を用いてｔ１Ｚ２を多項式乗算することにより、Ｄ＝Ｃ−Ｂ２Ｚ２を演算する第四演算ステップと、
Ｃについての事前演算結果Ｃ’を求め、その事前演算結果Ｃ’を用いてＸ２Ｃを多項式乗算し、Ａ又はＤについての事前演算結果Ａ’又はＤ’を求め、その事前演算結果Ａ’又はＤ’を用いてＡＤを多項式乗算することにより、Ｘ３＝Ｘ２Ｃ−ＡＤを演算する第五演算ステップと、
上記事前演算結果Ｂ’又はＤ’を用いてＢＤを多項式乗算し、上記事前演算結果Ｃ’を用いてＹ２Ｃを多項式乗算することにより、Ｙ３＝ＢＤ−Ｙ２Ｃを演算する第六演算ステップと、
上記事前演算結果Ｚ２’又はＣ’を用いて、ＣＺ２を多項式乗算することにより、Ｚ３＝ＣＺ２を演算する第七演算ステップと、
を含む楕円スカラー倍演算方法。
【請求項３】
請求項１に記載の楕円スカラー倍演算装置としてコンピュータを機能させるための楕円スカラー倍演算プログラム。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【公開番号】特開２０１０−１６４８７８（Ｐ２０１０−１６４８７８Ａ）
【公開日】平成２２年７月２９日（２０１０．７．２９）
【国際特許分類】
【出願番号】特願２００９−８５７７（Ｐ２００９−８５７７）
【出願日】平成２１年１月１９日（２００９．１．１９）
【出願人】（０００００４２２６）日本電信電話株式会社 (13,992)
【Ｆターム（参考）】
【公開日】平成２２年７月２９日（２０１０．７．２９）
【国際特許分類】
【出願日】平成２１年１月１９日（２００９．１．１９）
【出願人】（０００００４２２６）日本電信電話株式会社 (13,992)
【Ｆターム（参考）】
[ Back to top ]