(57)【要約】【課題】  楕円曲線上の点について２倍算と加算によりスカラー倍演算を行う場合に、点の加算の回数が多いと、処理時間が長くなるという問題があった。【解決手段】  数値で表される楕円曲線上の点に対して、自然数を用いて楕円曲線上におけるスカラー倍演算を実行する演算装置演算装置は、０と正のビットである１と負のビットである−１とを用いて、当該２進数表現を符号付き２進数の系列へ変換し、その系列において、長さが所定のビット長以下の部分系列であって、その部分系列の先頭ビットと最後尾ビットとが共に０でない部分系列を抽出し、部分系列が示す値がその部分系列の長さより１ビットだけ少ないビット列で表現できる場合、その系列のその部分系列の部分を、先頭ビットを０とし、その後にそのビット列を付したビット列に変換することにより系列を再変換する。【選択図】  図８
2013186202.tif 000002
【特許請求の範囲】
【請求項１】
数値で表される楕円曲線上の点に対して、自然数を用いて楕円曲線上におけるスカラー倍演算を実行する演算装置であって、
前記自然数を２進数表現し、０と正のビットである１と負のビットである−１とを用いて、当該２進数表現を符号付き２進数の系列へ変換する変換手段と、
前記系列において、長さが所定のビット長以下の部分系列であって、その部分系列の先頭ビットと最後尾ビットとが共に０でない部分系列を抽出する抽出手段と、
前記部分系列が示す値が、前記部分系列の長さより１ビットだけ少ない、０または正のビットである１もしくは負のビットである−１とからなるビット列で表現できるか否かを判定する判定手段と、
前記部分系列が示す値が前記部分系列の長さより１ビットだけ少ないビット列で表現できる場合、前記系列のその部分系列の部分を、先頭ビットを０とし、その後に前記ビット列を付したビット列に変換することにより、前記系列を再変換する再変換手段と、
前記再変換された系列に基づいて、楕円曲線上において、初期値が０である演算結果への前記数値の２進数表現の加算とその演算結果に対する２倍算とを行い、前記数値と前記自然数とのスカラー倍演算を実行する実行手段と、
を備えることを特徴とする演算装置。
【請求項２】
前記実行手段は、前記再変換された系列を前記所定のビット長より短い部分系列に分割し、分割された部分系列を単位として前記再変換された系列を読み出し、前記演算結果への読み出した部分系列が示す値と前記数値とを乗じた値の加算と、その部分系列の長さに応じた前記演算結果に対する２倍算とを行う、
ことを特徴とする請求項１に記載の演算装置。
【請求項３】
前記実行手段は、前記再変換された系列を、先頭ビットと最後尾ビットとが共に０でない第１の部分系列と、０のみからなる第２の部分系列とに分割し、読み出した部分系列が第２の部分系列である場合、その第２の部分系列の長さに応じて前記演算結果に対する２倍算を実行する、
ことを特徴とする請求項２に記載の演算装置。
【請求項４】
先頭ビットと最後尾ビットとが共に０でない前記所定のビット長より短い系列について、その系列が示す値と前記数値とのスカラー倍演算の結果を記憶する記憶手段をさらに備え、
前記実行手段は、読み出した部分系列が前記第１の部分系列であった場合、その第１の部分系列と前記数値とのスカラー倍演算の結果を前記記憶手段から読み出して前記演算結果に加算し、その第１の部分系列の長さに応じてその演算結果に対する２倍算を実行する、
ことを特徴とする請求項３に記載の演算装置。
【請求項５】
前記実行手段は、前記再変換された系列に含まれる前記第１の部分系列について、前記数値をスカラー倍演算の結果の値を予め計算し、
前記実行手段は、読み出した部分系列が前記第１の部分系列であった場合、予め計算された値を前記演算結果に加算し、その第１の部分系列の長さに応じてその演算結果に対する２倍算を実行する、
ことを特徴とする請求項３に記載の演算装置。
【請求項６】
前記符号付き２進数の系列を、前記所定のビット長より短い分割系列であって、先頭ビットと最後尾ビットとが共に０でない分割系列と、０のみからなる分割系列とに分割する分割手段をさらに備え、
前記抽出手段は、先頭ビットと最後尾ビットとが共に０でない分割系列を２つ含む３つの連続する分割系列からなる部分系列において、長さが前記所定のビット長以下である前記部分系列を抽出する、
ことを特徴とする、請求項１から５のいずれか１項に記載の演算装置。
【請求項７】
前記分割手段は、先頭ビットと最後尾ビットとが共に０でない分割系列を３つ含む５つの連続する分割系列からなる部分系列を抽出し、その３つの先頭ビットと最後尾ビットとが共に０でない分割系列のうち、２番目に出現する分割系列を、さらに先頭ビットと最後尾ビットとが共に０でない分割系列と、０のみからなる分割系列とに分割する、
ことを特徴とする、請求項６に記載の演算装置。
【請求項８】
数値で表される楕円曲線上の点に対して、自然数を用いて楕円曲線上におけるスカラー倍演算を実行する演算装置における演算方法であって、
変換手段が、前記自然数を２進数表現し、０と正のビットである１と負のビットである−１とを用いて、当該２進数表現を符号付き２進数の系列へ変換する変換工程と、
抽出手段が、前記系列において、長さが所定のビット長以下の部分系列であって、その部分系列の先頭ビットと最後尾ビットとが共に０でない部分系列を抽出する抽出工程と、
判定手段が、前記部分系列が示す値が、前記部分系列の長さより１ビットだけ少ない、０または正のビットである１もしくは負のビットである−１とからなるビット列で表現できるか否かを判定する判定工程と、
再変換手段が、前記部分系列が示す値が前記部分系列の長さより１ビットだけ少ないビット列で表現できる場合、前記系列のその部分系列の部分を、先頭ビットを０とし、その後に前記ビット列を付したビット列に変換することにより、前記系列を再変換する再変換工程と、
実行手段が、前記再変換された系列に基づいて、楕円曲線上において、初期値が０である演算結果への前記数値の２進数表現の加算とその演算結果に対する２倍算とを行い、前記数値と前記自然数とのスカラー倍演算を実行する実行工程と、
を有することを特徴とする演算方法。
【請求項９】
コンピュータを請求項１から７のいずれか１項に記載の演算装置が備える各手段として機能させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、楕円曲線上のスカラー倍演算を実行する演算装置、演算方法、およびプログラムに関する。
【背景技術】
【０００２】
スカラー倍演算（ｋＰ）は、公開鍵暗号方式の一つである楕円曲線暗号で一般的に利用されている演算である。公開鍵暗号方式とは、暗号化と復号化にそれぞれ異なる鍵を使用する暗号方式であり、データの暗号化、デジタル署名、鍵配送等で利用されている。楕円曲線暗号とは、楕円曲線を利用した公開鍵暗号方式であり、代表的なものには離散対数計算の困難性に基づくＥＣＤＳＡ署名、ＥＣＤＨ（Ｄｉｆｆｉｅ−Ｈｅｌｌｍａｎ）鍵配送方式がある。
【０００３】
スカラー倍演算（ｋＰ）とは、楕円曲線上のある点Ｐをスカラー（ｋ）倍する演算のことである。スカラーｋは、例えば公開鍵暗号における公開鍵や秘密鍵に相当する。ここで、スカラーｋは一般的に大きい値（例えば２５６ビットの値）である。このため、スカラーｋを小さい単位に分解し、小さい単位で点の２倍算（２×Ｐ）と点の加算（Ｐ＋Ｑ）および点の減算（Ｐ−Ｑ）を繰り返し実行することで、ｋＰを求める方法が一般的に用いられる。例えば演算の単位を１ビットとすると、最上位ビットから順に、ビットの値が「１」の場合に点の２倍算と点の加算を行い、ビットの値が「０」の場合に点の２倍算のみを行うことで、ｋＰが求められる。例えば、スカラーｋが１４の時のｋＰ（１４×Ｐ）は、１４を２進数で表現すると「１１１０」となるため、点の２倍算を４回、点の加算を３回行うことで求められる。より具体的には、まず「１１１０」の一番左のビットに着目すると、「１」であるため、初期値の０の２倍算を実行し、それにＰを加算して値Ｐを得る。その次のビットも「１」であるため、前のステップで算出したＰを２倍して、さらにＰを加算し、値３×Ｐを得る。同様に、次のステップでは３×Ｐを２倍した値にＰを加算して７×Ｐを得る。最後のビットに着目すると、０であるため、Ｐの加算は行わず、７×Ｐを２倍した値のみを算出し、このスカラー倍演算の最終的な解として、値１４×Ｐを得る。
【０００４】
非特許文献１には、このようなスカラー演算の手法として、ＮＡＦ＋Ｓｌｉｄｉｎｇ  Ｗｉｎｄｏｗｓ  Ｍｅｔｈｏｄ（以後、ＮＡＦ  Ｓウィンドウ法とする）が記載されている。ＮＡＦ  Ｓウィンドウ法は、演算単位を１〜ｗ（ｗはウィンドウ長）ビットの間で可変とすることで、上述の点の加算を少なくする手法の一つである。点の加算を少なくすることで処理の高速化が可能となる。
【０００５】
具体的には、まずＮＡＦアルゴリズムを適応する。ＮＡＦアルゴリズムとは、２進表記に負数も考慮することでビットが立つ割合（ハミングウェイト）を小さくする方法である。すなわち、例えばビット列「１１１１」について、「１００００−００００１」と表現できることを利用して、ビット列中の１の出現率を低減する。図２に１０進数の１１を表す２進数「１０１１」をＮＡＦ変換する例を示す。まず、２０１の下位２ビット「１１」は、「１」が連続しているため、２０２に示す通り、下位３ビット目を「１」、下位２ビット目を「０」として、最下位ビットを「−１」とする。次に、２０２の上位２ビット「１１」は、「１」が連続しているため同様に変換する。その結果、２０３で示す通り「１０−１０−１」が得られる。「１０−１０−１」は、１×２4＋０×２3−１×２2＋０×２1−１×２0＝１１である。このように、変換前と変換後のビット列は同じ値を示す。
【０００６】
次に、ＮＡＦアルゴリズムによって得られた符号付き２進数を、１からｗビットの範囲の符号付き２進数（非ゼロの数値）、もしくは０が２つ以上連続したビット列の何れかに分割する。図３（ｂ）は、図３（ａ）に示す符号付き２進数（１０進数値で２８９０１）をｗ＝３として分割した例である。図３（ｂ）の斜線（破線）で区切られた各符号付き２進数の系列ｋ１i（i＝０、１、２、、、８）は分割後の部分系列（以下、「分割系列」という）であり、分割数はｎ＝９である。特に下線箇所の非ゼロの分割系列ｋ１0、ｋ１2、ｋ１4、ｋ１6、ｋ１8を以後ウィンドウと呼ぶ。
【０００７】
最後に、分割系列ｋ１i用いて、スカラー倍演算（ｋＰ）を行う。本方式では、点の加算は前述のウィンドウの総数となるため、高速にスカラー倍演算が行える。
【先行技術文献】
【非特許文献】
【０００８】
【非特許文献１】「Ｏｎ  ｔｈｅ  Ｐｅｆｏｒｍａｎｃｅ  ｏｆ  Ｓｉｇｎａｔｕｒｅ  Ｓｃｈｅｍｅｓ  ｂａｓｅｄ  ｏｎ  Ｅｌｌｉｐｔｉｃ  Ｃｕｒｖｅｓ」、Ｅｒｉｋ  Ｄｅ  Ｗｉｎ等、１９９８年
【発明の概要】
【発明が解決しようとする課題】
【０００９】
ＮＡＦ  Ｓウィンドウ法では、点の加算はウィンドウの総数と同じである。そのため、ウィンドウの数が多い場合、処理時間が長くなるという課題があった。
【００１０】
本発明は上記課題に鑑みなされたものであり、点の加算と２倍算によりスカラー倍演算（ｋＰ）を行う場合に、点の加算の回数を減らすことで、演算における処理時間の短縮を実現する技術を提供することを目的とする。
【課題を解決するための手段】
【００１１】
上記目的を達成するため、本発明による演算装置は、数値で表される楕円曲線上の点に対して、自然数を用いて楕円曲線上におけるスカラー倍演算を実行する演算装置であって、前記自然数を２進数表現し、０と正のビットである１と負のビットである−１とを用いて、当該２進数表現を符号付き２進数の系列へ変換する変換手段と、前記系列において、長さが所定のビット長以下の部分系列であって、その部分系列の先頭ビットと最後尾ビットとが共に０でない部分系列を抽出する抽出手段と、前記部分系列が示す値が、前記部分系列の長さより１ビットだけ少ない、０または正のビットである１もしくは負のビットである−１とからなるビット列で表現できるか否かを判定する判定手段と、前記部分系列が示す値が前記部分系列の長さより１ビットだけ少ないビット列で表現できる場合、前記系列のその部分系列の部分を、先頭ビットを０とし、その後に前記ビット列を付したビット列に変換することにより、前記系列を再変換する再変換手段と、前記再変換された系列に基づいて、楕円曲線上において、初期値が０である演算結果への前記数値の２進数表現の加算とその演算結果に対する２倍算とを行い、前記数値と前記自然数とのスカラー倍演算を実行する実行手段と、を備える。
【発明の効果】
【００１２】
本発明によれば、スカラー倍演算の処理時間を短縮する演算装置、演算方法、及びプログラムを提供することができる。
【図面の簡単な説明】
【００１３】
【図１】実施形態１の情報処理装置の構成を説明する図。
【図２】ＮＡＦアルゴリズムの適応例を示す図。
【図３】実施形態１の演算過程を説明する図。
【図４】実施形態１におけるスカラー倍演算処理のフローチャート。
【図５】実施形態２の情報処理装置の構成を説明する図。
【図６】実施形態２におけるスカラー倍演算処理のフローチャート。
【図７】実施形態２の演算過程を説明する図。
【図８】実施形態１の演算過程のもう１つの例を説明する図。
【発明を実施するための形態】
【００１４】
以下、添付図面を参照して本発明の実施の形態を詳細に説明する。
【００１５】
＜＜実施形態１＞＞
（情報処理装置の構成）
図１は、本実施形態において符号付きウィンドウ結合処理を行う情報処理装置を示す図である。この情報処理装置は、例えば、ＣＰＵ、ハードディスク、メモリ等のハードウェアとＣＰＵが実行するプログラム等のソフトウェアを備え、メモリに格納されたプログラムの指示に従い動作を行うパーソナルコンピュータに相当する。情報処理装置は、入力部１０１、符号付き２進数変換部１０２、符号付きウィンドウ分割部１０３、抽出部１０４、結合部１０５、判定部１０６、再変換部１０７から構成される。
【００１６】
入力部１０１は、情報処理装置のハードディスク等に格納された自然数ｋ０を読み出す。そして、符号付き２進数変換部１０２へｋ０を渡す。符号付き２進数変換部１０２は、入力部１０１から渡された自然数ｋ０を、負の数を含む符号付き２進数ｋ１に変換する。符号付き２進数変換は、例えば、最下位ビットから最上位ビットに渡って変換を行う上述のＮＡＦアルゴリズムや、最上位ビットから最下位ビットに渡って変換を行うＭＯＦアルゴリズム等により実行される。図３（ａ）は、自然数ｋ０＝２８９０１にＮＡＦアルゴリズムを適用した際の符号付き２進数ｋ１を示す。なお、変換結果ｋ１は後述する符号付きウィンドウ分割部１０３に渡される。
【００１７】
ここで、符号付き２進数ｋ１の生成について、改めて説明する。自然数２８９０１は２進数表現では「１１１００００１１１００１０１」という１５ビットで表現される。ここで、１が連続して出現する区間を探索すると、上位３ビット（１３〜１５桁）と中間の３ビット（６〜８桁）の区間が抽出される。この３ビットの区間について、負のビットである「−１」を用いて１ビットだけ長い符号付き２進数で表現すると、それぞれ「１００−１」となる。このため、上位３ビットの区間については、その区間の左にはビットがないため、新たにビット「１」を加え、区間の最後尾ビットを「−１」とするとともに、区間の他の２ビットを「０」とする。そして中間の３ビットの区間については、その区間の左にビット「０」があるため、それを「１」とし、区間の最後尾ビットを「−１」とするとともに、区間の他の２ビットを「０」とする。このため、２８９０１は、「１００−１０００１００−１００１０１」と１６ビットで表現されることとなる。
【００１８】
また、自然数２８９０１は、ＭＯＦアルゴリズムを用いても同様に「１００−１０００１００−１００１０１」と表現される。以下、ＭＯＦアルゴリズムについての動作を説明する。ＭＯＦアルゴリズムでは、２８９０１の２進数表現を２倍し、その２倍した結果から、２進数表現を減算する。例えば、「１１１００００１１１００１０１」を２倍した「１１１００００１１１００１０１０」から「１１１００００１１１００１０１」を減算する。すると「１００−１０００１００−１０１−１１−１」が得られる。ここで「１−１」を「０１」で、「−１１」を「０−１」で表現すると、「１００−１０００１００−１００１０１」が得られる。ただし、自然数２８９０１については、ＭＯＦアルゴリズムとＮＡＦアルゴリズムによる変換結果は等しくなるが、必ず結果が等しいわけではない。例えば、自然数１０５は、２進数表現すると「１１０１００１」であるところ、ＮＡＦアルゴリズムでは「１０−１０１００１」となるが、ＭＯＦアルゴリズムでは「１００−１−１００１」となる。本発明においては、０と正のビット１と負のビット−１とを用いて自然数を表現することが重要なのであって、どのように変換するかは重要ではない。すなわち、以下では、ＮＡＦアルゴリズムを用いた場合の例について主に説明するが、符号付き２進数へのいかなる変換方法を用いても同様の方法を用いることが可能である。
【００１９】
符号付きウィンドウ分割部１０３は、符号付き２進数変換部１０２によって算出されたｋ１を、ウィンドウサイズを所定のビット長ｗとしたとき、ｗビット以下の範囲の０でない符号付き２進数、又は０が１つ以上連続したビット列の何れかに分割する。分割は例えば上述したＮＡＦ  Ｓウィンドウ法と同様に行う。なお、上述の所定のビット長以下の０でない符号付き２進数は、一番左のビットである先頭ビットと一番右のビットである最後尾ビットがそれぞれ０でないものとする。また、所定のビット長以下で、先頭ビットと最後尾ビットがそれぞれ０でなければ、その間に０が含まれていてもよい。例えば、ｗ＝３の場合、「０１１」は、「０」と「１１」とに分割されるが、「１０１」は「１」「０」「１」とはせず、「１０１」とする。図３（ｂ）は、図３（ａ）をビット長ｗ＝３で分割した例である。
【００２０】
ここで、図３（ｂ）の分割について詳細に説明する。図３（ａ）の２進数の系列の先頭ビットは１であるが、それに続くｗ−１個のビットには０しかない。このため、このビットは単独で１つの分割系列ｋ１0となる。続いて、左から２ビット目は０であり、３ビット目まで０が継続する。このため、この２ビットをまとめて、分割系列ｋ１1とする。４ビット目は−１であるが、これもそれに続くｗ−１個のビットは全て０であるため、このビットも単独で１つの分割系列ｋ１2となる。その後、５ビット目から７ビット目は０が連続するため、この３ビットをまとめて１つの分割系列ｋ１3とする。その後も同様に、１３ビット目まで分割系列が得られる。ここで、１４ビット目に着目すると、１４ビット目は１であり、それに続くｗ−１個のビットにおいて、１６ビット目に１が出現している。したがって、１４ビット目から１６ビット目までを先頭ビットと最後尾ビットが共に０でない符号付き２進数の系列として捉えることができるため、これらの３ビットをまとめて１つの分割系列ｋ１8とする。
【００２１】
図３（ｂ）の斜線（破線）によって区切られた各符号付き２進数値の系列ｋ１i（ｉ＝０、１、２、、、８）は上述の分割系列を示している。このときの分割数はｎ＝９である。図において、下線で示すゼロの列でない分割系列ｋ１0、ｋ１2、ｋ１4、ｋ１6、ｋ１8は「ウィンドウ」である。この時点において、ウィンドウは５個存在している。分割系列ｋ１iは抽出部１０４に渡される。
【００２２】
抽出部１０４は、入力された分割系列ｋ１iについて、２つのウィンドウを含むように３つの連続した分割系列ｋ１j（ｊ＝ｘ、ｘ＋１、ｘ＋２）を抽出する。例えば、図３（ｃ）の３０１で示す通り、ｋ１0、ｋ１1およびｋ１2を抽出する。抽出結果は、後述の結合部１０５に渡される。
【００２３】
結合部１０５は、抽出された分割系列ｋ１j（ｊ＝ｘ、ｘ＋１、ｘ＋２）を入力とし、結合した１つの符号付き２進数ｚ０lを得る。結合部１０５の処理内容についての詳細は後述する。符号付き２進数ｚ０lは、判定部１０６に渡される。
【００２４】
判定部１０６は、結合部１０５から渡された符号付き２進数ｚ０lを入力とし、２つのウィンドウを含むｚ０lを１つのウィンドウのみを含むｚ１lに再変換できるかを判定する。判定部１０６の処理内容についての詳細も後述する。判定結果は、後述する再変換部１０７に渡される。
【００２５】
再変換部１０７は、判定部１０６で再変換可能と判定されたｚ０lをｚ１lに再変換する。例えば、図３（ｄ）のように、図３（ｃ）のｚ０0を３０２で示すｚ１0に置き換える。再変換したｚ１lでｋ１iを置き換えることで、最終的に符号付き２進数の分割系列ｋ２mとして出力する。例えば、図３（ｅ）のように、ｋ２m（ｍ＝０、１、２、、、６）が得られる。再変換部１０７の処理内容についての詳細も後述する。
【００２６】
（情報処理装置の処理）
図４は、情報処理装置が行う処理の流れを示すフローチャートである。処理では、自然数ｋ０の入力、数値ｋ１への変換、各符号付き２進数値ｋ１iへの分割とその抽出、抽出された各数値を用いた判定および分割系列ｋ１iからｋ２mへの再変換が行われる。
【００２７】
処理が開始されると、まず、入力部１０１が、自然数ｋ０を取得する（Ｓ４０１）。自然数ｋ０は、例えば、スカラー値であり、２５６ビット長の秘密鍵である。自然数ｋ０は符号付き２進数変換部１０２へ出力される。符号付き２進数変換部１０２は、入力された自然数ｋ０を、負数を含む符号付き２進数ｋ１に変換する（Ｓ４０２）。なお、ここでの説明においては、ｋ１は、図３（ａ）で示される系列であるとする。系列ｋ１は、符号付きウィンドウ分割部１０３へ出力される。
【００２８】
符号付きウィンドウ分割部１０３は、符号付き２進数ｋ１を所定のビット長以下（１〜ｗビット）の範囲のサイズの部分系列へ分割し、分割系列ｋ１i（ｉ＝０、１、、、ｎ−１）を出力する。なお、ここでの説明では、ｗ＝３とし、ｋ１iは図３（ｂ）に示されるものであるとする。ここで、分割ビット長ｗの範囲は、情報処理装置で実行されるプログラムにより指定された値であってもよいし、情報処理装置を扱うユーザが情報処理装置が備えるユーザーインターフェース等を通して入力したものであってもよい。分割系列ｋ１iは、抽出部１０４へ出力される。
【００２９】
続いて、抽出部１０４は、２つのウィンドウを含むように、入力された分割系列ｋ１iから、３つの連続した分割系列ｋ１j（ｊ＝ｘ、ｘ＋１、ｘ＋２）を抽出する（Ｓ４０４）。例えば、図３（ｂ）の分割系列においては、部分系列３０１〜３０４が抽出される。ここで、部分系列３０１は、ウィンドウｋ１0とｋ１2とを含み、部分系列３０２は、ウィンドウｋ１4とｋ１6とを含む。また、部分系列３０３は、ウィンドウｋ１2とｋ１4とを含み、部分系列３０４は、ウィンドウｋ１6とｋ１8とを含む。なお、符号付き２進数は通常１又は−１が連続して出現することはないため、２つのウィンドウを含む部分系列は、先頭ビットと最後尾ビットが共に０でない系列となる。抽出された結果は結合部１０５へ入力される。
【００３０】
結合部１０５は、抽出部１０４で抽出された３つの連続する分割系列ｋ１jを入力とし、結合した符号付き２進数ｚ０lを得る（Ｓ４０５）。具体的には、図３（ｃ）に示す通り、ｋ１0、ｋ１1およびｋ１2に対応する４ビットをｚ０0とする。同様に、ｋ１4、ｋ１5およびｋ１6に対応する４ビットをｚ０1とする。さらに、ｋ１2、ｋ１3およびｋ１4に対応する５ビットをｚ０2とする。また、ｋ１6、ｋ１7およびｋ１8に対応する６ビットをｚ０3とする。そして、結合された符号付き２進数ｚ０lは判定部１０６へ出力される。
【００３１】
続いて、判定部１０６は、各符号付き２進数ｚ０lのビット長が所定のビット長（ｗ＋１ビット）以下であるか否かを判定する（Ｓ４０６）。少なくとも１つのｚ０lのビット長がｗ＋１ビット以下の場合（Ｓ４０６でＹｅｓ）はＳ４０７に進む。一方、全てのｚ０lのビット長がｗ＋１ビットより大きい場合（Ｓ４０６でＮｏ）は、再変換部１０７はｋ１に再変換を行わずにｋ２として出力して処理を終了する（Ｓ４１０）。例えば、図３（ｃ）の場合、ｚ０3とｚ０4はｗ＋１ビットより長いものの、ｚ０0とｚ０1は、ｗ＋１（＝４）ビット以下である。
【００３２】
Ｓ４０７では、判定部１０６が、ｗ＋１ビット以下の長さの符号付き２進数ｚ０lをそれより１ビットだけ少なく表現できるかを判定する。例えば、ｚ０lのビット長が４ビットの場合は、３ビットの２進数表現で最大値の「１１１」＝７以下であるか否かを判定する。条件を満たす場合は、２つのウィンドウを、ｗビット以下で表現される１つのウィンドウに結合することができる。なお、ｚ０lの長さががｕビットである場合、ｕ−１ビットの符号付き２進数で表現できる範囲は、−２u-1＋１から２u-1−１である。このため、ｚ０lの絶対値｜ｚ０l｜が２u-1−１以下か否かを判定する。
【００３３】
この判定においては、少なくとも１つのｌに対して｜ｚ０l｜が２u-1−１以下の場合（Ｓ４０７でＹｅｓ）はＳ４０８に進む。そして、全てのｌに対して｜ｚ０l｜が２u-1−１より大きい場合（Ｓ４０７でＮｏ）は、再変換部１０７はｋ１に対して再変換処理を行わず、ｋ２を出力して処理を終了する（Ｓ４１０）。例えば、図３（ｃ）の場合、３０１に示すｚ０0は符号付き２進数「１００−１」であり、１０進数値にすると７である。このため、２u-1−１（＝２3−１＝７）以下であるため、この判定によって処理をＳ４０８へ進める。図３以外の例では、ｕ＝５の符号付き２進数「１０００−１」は、１０進数にすると１５であり、２u-1−１（＝１５）以下であるため条件を満たす。また、ｕ＝４の符号付き２進数「−１００−１」は、１０進数にすると−９であり、その絶対値９は２u-1−１（＝７）より大きいため条件を満たさない。
【００３４】
Ｓ４０８では、再変換部１０７が、判定部１０６で再変換可能と判定されたｚ０lを再変換し、再変換後の値である符号付き２進数値ｚ１lを算出する。具体的には、ｚ１lの先頭ビットを「０」にする。そして、以降のビットの値は、ｗビットで表現される１つのウィンドウに変換する。なお、再変換前の系列に含まれる１つのウィンドウが、複数の再変換可能な部分系列ｚ１lに含まれる場合は、この時点において、いずれか１つのみを選択するようにしてもよい。また、この選択は、これより先のステップで行われてもよいし、さらに後のステップにおいて行われてもよい。
【００３５】
再変換後の値の算出においては、ｚ０lの最上位ビットが「１」の場合はｚ１lの値を「１」と「０」で２進数表現する。例えば、図３（ｃ）の場合、３０１に示すｚ０0＝ｚ０1＝「１００−１」は１０進数表現で７であるため、先頭ビットを「０」とし、以後のビットは７を２進数表現した「１１１」とする。なお、７＝１×２2＋１×２1＋１×２0）が成り立つ。このようにして、ｚ１0＝「０１１１」となる。また、ｗ＝４の場合のｚ０0＝「１０００−１」は、１０進数表現では１５であるため、先頭ビットを「０」とし、以後のビットは１５を符号付き２進数表現した「１１１１」とする。つまり、ｚ１0＝「０１１１１」となる。このようにして、Ｓ４０８では、先頭ビットが「１」の再変換可能なｚ０lについて、先頭ビットが「０」であり、その後のｗビットが「１」と「０」からなる、ｗ＋１ビットの２進数が算出される。
【００３６】
一方、ｚ０lの最上位ビットが「−１」の場合はｚ１lの値を「−１」と「０」で符号付き２進数表現する。例えば、ｗ＝３の場合のｚ０0＝「−１００１」は、１０進数表現では−７であるため、先頭ビットを「０」とし、以後のビットは−７を符号付き２進数表現した「−１−１−１」で表現する。ここで、−７＝−１×２２−１×２１−１×２０である。このようにして、Ｓ４０８では、先頭ビットが「−１」の再変換可能なｚ０lについては、先頭ビットが「０」であり、その後のｗビットが「０」と「−１」からなる、ｗ＋１ビットの符号付き２進数が算出される。
【００３７】
Ｓ４０９では、再変換部１０７が、判定部１０６で再変換可能と判定されたｚ０lをｚ１lに再変換する。具体的には、再変換部１０７が、再変換したｚ１lでｋ１iを置換する。例えば、図３の例では、ｚ０0とｚ０1の部分がそれぞれ「０１１１」に再変換され、再変換後のビット列が図３（ｄ）のようになる。なお、ウィンドウサイズｗが３であるため、スカラー倍演算処理に用いられる部分系列はｋ２m（ｍ＝０、１、２、、、６）として得られる。Ｓ４１０では、再変換部１０７が、ｋ２mを出力し、処理を終了する。例えば、図３（ｄ）の場合、ｋ２は図３（ｄ）のように表現され、下線部で示すウィンドウの数が図３（ｂ）の５個から３個へ減っていることがわかる。
【００３８】
再変換部１０７から出力されたｋ２は、例えば、楕円曲線上の点Ｐをｋ２倍するスカラー倍演算（ｋ２×Ｐ）に使用される。ここで、数値Ｐとｋ２とのスカラー倍演算処理について説明する。スカラー倍演算処理においては、演算結果の初期値を０として、楕円曲線上において、数値Ｐと再変換後のビット列の部分系列とのスカラー倍演算の結果の値を演算結果に加算すると共に２倍算を実行する。ここで、符号付き２進数で表される第１の部分系列と、０のみからなる第２の部分系列とでは、実行する処理が異なる。第１の部分系列では、その第１の部分系列の符号付き２進数が示す値と数値Ｐとスカラー倍演算の結果をそれまでの演算結果に加算して、その第１の部分系列の長さに応じて演算結果に対して２倍算を施す。一方、第２の部分系列は、その第２の部分系列が示す値は必ず０である。このため、値の加算は行わず、第２の部分系列の長さに応じて、それまでの演算結果に対して２倍算を実行するのみである。なお、０のみからなる第２の部分系列は長さが１であってもよい。すなわち、ウィンドウ以外については、０を１つ読み込むたびに、それまでの演算結果に対して２倍算を実行するようにしてもよい。
【００３９】
以下、図３（ｄ）の場合を例として、スカラー倍演算処理の例を説明する。まず、演算結果の初期値を０とする。そして、ｋ２を例えば先頭ビットから部分系列を単位として、すなわち、ｋ２m（ｍ＝０、１、２、、、６）ごとに読み出す。まず、ｋ２0は「０」であるため、演算結果に対して１回の２倍算が実行される。ただし、この時点では演算結果は初期値の０であるため、２倍算後も０である。このため、先頭ビットが０の場合は２倍算の処理を省略してもよい。続いて、ｋ２1を読み出す。ｋ２1は「１１１」であるため、数値Ｐと「１１１」とのスカラー倍演算の結果の値を演算結果に加算する。そして、ｋ２1は３ビットであったため、演算結果に対して３回だけ２倍算を実行する。続いて、ｋ２2は「０００」と３ビット連続して０であるため、それまでの演算結果に対して２倍算を３回実行する。同様に、ｋ２3は「０」であるため、それまでの演算結果に対して２倍算を１回実行する。ｋ２4は「１１１」であるため、ｋ２1のときと同様に、数値Ｐと「１１１」とのスカラー倍演算の結果の値を演算結果に加算したのちに、２倍算を３回実行する。ｋ２5は「００」であるため、演算結果に対して２回だけ２倍算を実行する。そして、ｋ２6は「１０１」であるため、「１０１」と数値Ｐとのスカラー倍演算の結果の値を演算結果へ加算する。なお、ここでは、ｋ２6がｋ２の系列の最後尾の部分系列であるため、２倍算は行わない。なお、上述の説明では、ｋ２の最上位ビットから読み出したが、最後尾ビットから読み出してもよい。
【００４０】
本実施形態について、ｋ０が８１８５であり、ｗ＝３であった場合の例を図８に示す。図８の例の場合、符号付き２進数に変換し、分割した時点において、ウィンドウ数は下線で示す３個である。そして、２つのウィンドウを含む３つの連続した分割系列は、ｋ１4〜ｋ１6で得られる。このため、ｚ０0＝「−１００１」となる。ここで、ｚ０0のビット数ｕは４であり、ｗ＋１以下である。また、｜ｚ０0｜＝｜−１×２3＋１｜＝７であるため、２u-1−１以下である。このため、ｚ０0は再変換可能と判定できる。再変換においては、ｚ０0の先頭ビットが「−１」であるため、ｚ１0においては、先頭ビットを「０」とし、以後のビットは−７を符号付き２進数表現した「−１−１−１」で表す。このため、ｚ１0＝「０−１−１−１」となる。そして、ｚ１0でｋ１4〜ｋ１6を変換して、図８（ｄ）のようなｋ２を得ることができる。なお、ｋ２においてはウィンドウ数は下線で示す２個であり、再変換前より減少していることが分かる。
【００４１】
なお、上述の説明では、抽出部１０４と結合部１０５を分けて説明したが、これらを１つにまとめて、ブロック生成部とすることができる。具体的には、ブロック生成部は、分割した複数の符号付きウィンドウから２つのウィンドウを含み最上位ビットと最下位ビットが非ゼロの数値である符号付きブロックｚ０lを生成する。ブロックは、例えば、図３（ｃ）の３０１と３０２のようなものであり、これらのブロックは、下線で示すウィンドウを２つ含み、ブロック内の最上位ビットと最下位ビットが非ゼロの数値を示していることが分かる。また、本実施形態では、再変換はＳ４０８において値を算出し、Ｓ４０９において再変換するように説明したが、予めｚ０からｚ１への再変換結果を記憶装置に記憶しておき、読みだして再変換してもよい。
【００４２】
本実施形態によれば、自然数を符号付き２進数で変換したのちの系列について、ウィンドウの数を減らすことで、スカラー倍演算における処理時間を短縮することができる。
【００４３】
ここで、楕円曲線上の点Ｐが既知の場合は、予めＰに１〜２w−１倍した結果を不図示の記憶部に格納し、ウィンドウ毎のＰの整数倍計算を省略して実演算処理を行うことができる。その結果、スカラー倍演算の高速化が可能となる。また、例えばｗ＝３の場合、演算の時点において、「００１」などは、「００」と「１」とに分割される。このため、先頭ビットと最後尾ビットとが共に０でない１〜２w−１についてのみ、数値Ｐの整数倍計算を行っておくようにしてもよい。これにより、計算結果の記憶に必要となる記憶部の容量を削減することが可能となる。例えば、ｗ＝３の場合は、「１１１」「１１」「１」「１０１」の４通りの整数倍計算を行うだけで十分となる。
【００４４】
また、楕円曲線上の点Ｐが既知でない場合でも、本実施形態でｋ２を出力した後に、ｋ２内の各ウィンドウで取りうる値のみに対して事前計算（図３の例では「１１１」と「１０１」のみに対するＰとのスカラー倍演算）を行い、実演算処理を行うことができる。その結果、無駄な事前演算処理を行うことがなくなり、スカラー倍演算のさらなる高速化が可能となる。なお、「−１−１−１」のウィンドウに対する事前計算については、「１１１」に対する事前計算結果を流用することができる。このため、「１１１」と「−１−１−１」の両方を含むｋ２に対しては、いずれか１つの事前計算のみを実行することにより、さらに無駄な計算を省略し、スカラー倍演算を高速化することが可能となる。
【００４５】
＜＜実施形態２＞＞
実施形態１では、２つの符号付きウィンドウを１つの符号付きウィンドウに結合する方法を説明した。しかしながら、例えばｗ＝３の場合に、符号付き２進数「１００−１０１００−１」を実施形態１の方法で再変換する場合、１番目から２番目に出現するウィンドウまでの系列「１００−１０１」のビット数が６ビットとなる。このように、１番目から２番目に出現するウィンドウまでの系列の長さがｗ＋１＝４ビット以下ではないため、ウィンドウを結合できない。そこで、実施形態２では、３つの符号付きウィンドウを２つの符号付きウィンドウに結合する方法を説明する。具体的には、２番目に出現するウィンドウを分割する。そして、１番目のウィンドウと２番目のウィンドウの前半および、２番目のウィンドウの後半と３番目のウィンドウがそれぞれ１つのウィンドウに結合する。なお、結合するための判定（Ｓ４０７）および再変換（Ｓ４０８）は実施形態１と同様である。
【００４６】
（情報処理装置の構成）
図５は、本実施形態において符号付きウィンドウ結合処理を実行する情報処理装置を示す図である。情報処理装置は、入力部５０１、符号付き２進数変換部５０２、符号付きウィンドウ分割部５０３、抽出部５０４、分割部５０５、結合部５０６、判定部５０７、再変換部５０８を含む。このうち、入力部５０１、符号付き２進数変換部５０２、符号付きウィンドウ分割部５０３は実施形態１と同じ処理内容であるため、ここでは説明を省略する。
【００４７】
抽出部５０４は、符号付きウィンドウ分割部５０３によって得られた分割系列ｋ１iについて、３つのウィンドウを含む５つの連続した分割系列ｋ１j（ｊ＝ｘ、ｘ＋１、ｘ＋２、ｘ＋３、ｘ＋４）を抽出する。例えば、図７（ｃ）の７０１で示す通り、ｋ１0〜ｋ１4を抽出する。そして、分割部５０５は、５つの連続した分割系列ｋ１jのうち、２番目に出現するウィンドウの値を分割する。例えば、図７（ｄ）で示す通り、２番目に出現するウィンドウの値をｋ１’2〜ｋ１’4として分割する。そして、その分割の結果を、新たに各符号付き２進数値ｋ１’i（ｉ＝０、１、２、、、６）として表現する。なお、ｋ１’0＝ｋ１0、ｋ１’1＝ｋ１1である。また、ｋ１’5＝ｋ１3、ｋ１’6＝ｋ１4である。
【００４８】
結合部５０６は、分割部５０５によって得られた各符号付き２進数値ｋ１’iを入力とし、結合した２つの符号付き２進数ｇ０l、ｈ０lを得る。結合部５０６の処理内容については、後述の情報処理装置の処理工程にて具体的に説明する。符号付き２進数ｇ０l、ｈ０lは、判定部５０７に渡される。
【００４９】
判定部５０７は、まず、２つのウィンドウを含むｇ０l、ｈ０lを、１つのウィンドウのみを含むｇ１l、ｈ１lに再変換できるかを判定する。判定部５０７の処理内容の詳細については後述する。判定結果は、再変換部５０８に渡される。再変換部５０８は、判定部５０７で再変換可能と判定されたｇ０l、ｈ０lをｇ１l、ｈ１lに再変換する。例えば、図７（ｆ）のように、図７（ｅ）のｇ０l、ｈ０lをｇ１l、ｈ１lに置き換える。再変換したｇ１l、ｈ１lでｋ１iを置き換えることで、最終的に符号付き２進数の分割系列ｋ２mとして出力する。例えば、図７（ｆ）のように、ｋ２m（ｍ＝０、１、２、３、４）が得られる。再変換部５０８の処理内容の詳細についても後述する。
【００５０】
（情報処理装置の処理）
図６は、情報処理装置が行う処理の一連の流れを示すフローチャートである。処理では、自然数ｋ０の入力、数値ｋ１への変換、各符号付き２進数値ｋ１iへの分割とその抽出、抽出された各数値を用いた判定および分割系列ｋ１iからｋ２mへの再変換が実行される。
【００５１】
なお、ここでは、図６に加えて図７を用いて、再変換処理について説明する。処理が開始されると、まず数値ｋ０を取得し（Ｓ６０１）、ｋ０を符号付き２進数にｋ１に変換する（Ｓ６０２）。図７の例では、数値ｋ０として「２３１」が入力されるものとし、図７（ａ）は、それをＮＡＦアルゴリズムで符号付き２進数に変換したものを示している。その後、実施形態１と同様に、分割ビット長ｗ以内の長さの分割系列ｋ１iに、ｋ１を分割する（Ｓ６０３）。図７（ｂ）は、分割ビット長ｗ＝３として、ｋ１を分割した結果である。
【００５２】
続いて、抽出部５０４が、３つのウィンドウを含む５つの連続した分割系列ｋ１j（ｊ＝ｘ、ｘ＋１、ｘ＋２、ｘ＋３、ｘ＋４）を抽出する（Ｓ６０４）。例えば、抽出部５０４は、図７（ｃ）の７０１で示す部分を抽出する。そして、分割部５０５が、５つの連続した分割系列ｋ１jのうち、２番目のウィンドウの値を３つに分割する（Ｓ６０５）。分割することで、１番目のウィンドウと２番目のウィンドウの前半および、２番目のウィンドウの後半と３番目のウィンドウがそれぞれ１つのウィンドウに結合するための準備をする。具体的には２番目のウィンドウｋ１x+2の先頭ビットをｋ１’x+2とし、次に１が立つまで連続した０のビット列をｋ１’x+3とする。そして、ｋ１x+2の残りをｋ１’x+4として分割する。例えば、図７（ｄ）では、２番目のウィンドウを示すｋ１2＝「−１０１」の先頭ビット「−１」をｋ１’2としている。そして、次にｋ１2の１が立つまで連続した０のビット列「０」をｋ１’3とし、ｋ１2の残り「１」をｋ１’4として分割する。このようにして、分割系列を含む新たな各符号付き２進数値ｋ１’i（ｉ＝０、１、２、、、６）は、図７（ｄ）のように表現される。
【００５３】
その後、結合部５０６は、分割部５０５によって得られた各符号付き２進数値ｋ１’iを入力とし、結合した２つの符号付き２進数ｇ０l、ｈ０lを得る（Ｓ６０６）。具体的には、具体的には図７（ｅ）に示す通り、分割部５０５が分割した最初の２進数値とそれ以前の２進数値（ｋ１’i（ｉ＝０、１、２））をｇ０0とする。そして、分割部５０５が分割した最後の２進数値とそれ以後の２進数値（ｋ１’i（ｉ＝４、５、６））をｈ０0とする。
【００５４】
符号付き２進数ｇ０l、ｈ０lを得ると、判定部５０７は、これらの符号付き２進数の各々について、ビット長がｗ＋１ビット以下か否かを判定する（Ｓ６０７）。そして、ｇ０l、ｈ０lのビット数がｗ＋１以下の場合（Ｓ６０７でＹｅｓ）は処理をＳ６０８へ進める。一方、ｇ０l、ｈ０lのビット数がｗ＋１より大きい場合（Ｓ６０７でＮｏ）は、再変換を行わないｋ１をｋ２として出力して処理を終了する（Ｓ６１０）。例えば、図７（ｅ）の場合、ｇ０ｌ、ｈ０ｌのビット数はそれぞれ４であり、ｗ＋１（＝４）以下である。
【００５５】
Ｓ６０８では、判定部５０７が、ｇ０l、ｈ０lの絶対値｜ｇ０l｜、｜ｈ０l｜がそれぞれ２w−１以下か否かを判定する。｜ｇ０l｜、｜ｈ０l｜のいずれかが２w−１以下の場合（Ｓ６０８でＹｅｓ）、処理をＳ６０９へ進める。一方、｜ｇ０l｜と｜ｈ０l｜が共に２w−１より大きい場合（Ｓ６０８でＮｏ）、再変換を行わず、ｋ１をそのままｋ２として出力して処理を終了する（Ｓ６１０）。例えば、図７（ｅ）の場合、７０３、７０４に示すｇ０l、ｈ０lは共に｜１００−１｜＝７（１０進数値）であり、２w−１（＝２3−１＝７）以下である。このため、この場合は処理をＳ６０９へ進めることとなる。
【００５６】
Ｓ６０９では、再変換部５０８は、まず、再変換可能と判定されたｇ０l、ｈ０lの再変換後の値である符号付き２進数値ｇ１l、ｈ１lを算出する。図７の場合、ｇ１l、ｈ１l＝「０１１１」となる。そして、再変換部５０８は、算出したｇ１l、ｈ１lにより、ｋ１’iを置換する。例えば、図７（ｆ）のように、ｋ２m（ｍ＝０、１、２、３）として得られる。最後に、再変換部５０８がｋ２mを出力して処理を終了する（Ｓ６１０）。例えば、図７（ｂ）の場合、ｋ２mは図７（ｆ）のように表現され、下線部で示すウィンドウの数が図７（ｂ）の３個から２個へ減っていることがわかる。
【００５７】
なお、実施形態１のあとに実施形態２を実行できることは明らかである。例えば、「１００−１０１００−１」を実施形態１（ｗ＝３ビット）で実施しようとすると、１番目から２番目のウィンドウ「１００−１０１」までのビット数が６ビットなので、ｗ＋１＝４ビット以下ではない。従って、実施形態１の条件を満たさない。そのため、実施形態２を実施する。実施形態２を実施すれば、「１００−１０１００−１」は「０１１１０１１１」となり、ウィンドウの数を３個から２個へ減らすことができる。
【００５８】
なお、上述の方法は、符号付き２進数への変換にＮＡＦアルゴリズムを用いた場合に限らず、他の方法を用いた場合であっても適用可能である。例えば、ＭＯＦアルゴリズムで自然数１０５を表した場合「１００−１−１００１」となるところ、上述の方法を用いれば、「０１１１０１１１」と表すことが可能となり、この場合、ウィンドウ数を３から２へ削減することが可能となる。
【００５９】
＜＜その他の実施形態＞＞
また、本発明は、以下の処理を実行することによっても実現される。即ち、上述した実施形態の機能を実現するソフトウェア（プログラム）を、ネットワーク又は各種記憶媒体を介してシステム或いは装置に供給し、そのシステム或いは装置のコンピュータ（またはＣＰＵやＭＰＵ等）がプログラムを読み出して実行する処理である。
【図１】
2013186202.tif 000003
【図２】
2013186202.tif 000004
【図３】
2013186202.tif 000005
【図４】
2013186202.tif 000006
【図５】
2013186202.tif 000007
【図６】
2013186202.tif 000008
【図７】
2013186202.tif 000009
【図８】
2013186202.tif 000010