情報処理装置およびその方法
【課題】 NAF Sウィンドウ法に必要な倍算テーブルの総数よりも少ない倍算テーブル数でスカラ倍演算を行う。
【解決手段】 変換部11は、スカラを入力し、スカラを符号付き二進法の、負数を含む数値に変換する。初期分割部12は、数値を1ビットから最大分割ビット長wの範囲の複数の数値に分割する。選択部13は、複数の数値から特定の数値を選択する。数列算出部14は、選択された数値の絶対値を含み、項の総数が前記最大分割ビット長wの関数である閾値よりも少ない数列を取得する。再分割部15は、複数の数値の絶対値のうち数列に含まれない数値を1ビットから前記最大分割ビット長wの範囲の複数の数値に再分割する。倍算テーブル算出部16は、数列に含まれる2以上の各項をスカラに含む倍算テーブルを算出する。スカラ倍演算部17は、分割された複数の数値、再分割された複数の数値、および、倍算テーブルを用いてスカラ倍演算を行う。
【解決手段】 変換部11は、スカラを入力し、スカラを符号付き二進法の、負数を含む数値に変換する。初期分割部12は、数値を1ビットから最大分割ビット長wの範囲の複数の数値に分割する。選択部13は、複数の数値から特定の数値を選択する。数列算出部14は、選択された数値の絶対値を含み、項の総数が前記最大分割ビット長wの関数である閾値よりも少ない数列を取得する。再分割部15は、複数の数値の絶対値のうち数列に含まれない数値を1ビットから前記最大分割ビット長wの範囲の複数の数値に再分割する。倍算テーブル算出部16は、数列に含まれる2以上の各項をスカラに含む倍算テーブルを算出する。スカラ倍演算部17は、分割された複数の数値、再分割された複数の数値、および、倍算テーブルを用いてスカラ倍演算を行う。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、スカラ倍演算を行う情報処理に関する。
【背景技術】
【０００２】
スカラ倍演算は、公開鍵暗号方式の一つである楕円曲線暗号において利用される演算である。公開鍵暗号方式は、暗号化と復号にそれぞれ異なる鍵を使用する暗号方式であり、データの暗号化、ディジタル署名、鍵配送などで利用される。楕円曲線暗号は、楕円曲線を利用した公開鍵暗号方式であり、離散対数計算の困難性に基づく、ECDSA署名、ECDH鍵配送方式などが代表例である。なお、ECDSAは「elliptic curve digital signature algorithm」の、ECDHは「elliptic curve Diffie-Hellman」の略称である。
【０００３】
スカラ倍演算(xP)は、楕円曲線上のある点Pをスカラ(x)倍する演算のことである。公開鍵暗号ではスカラxに大きな値（例えば256ビットの値）をとる。このため、スカラxを小さい単位に分解し、小さい単位で点の二倍算(2P)、点の加算(P+Q)、および、点の減算(P-Q)を繰り返し実行して、xPを求める方法が一般に用いられる。例えば、スカラx=15の場合、P→2P→…→14P→15Pのように、点Pを14回繰り返し加算することでxP=15Pが得られる。別の方法として、P→2P→4P→8P→16P→15Pのように、点の二倍算（例えば2P×2P=4P）と、点の減算（例えば16P-P=15P）を組み合わせてもxP=15Pを得ることができる。後者は、四回の二倍算と、一回の減算で済むため、前者よりも高速な演算が可能である。
【０００４】
P→2P→…→14P→15Pや、P→2P→4P→8P→16P→15Pのような計算過程のスカラに現れる数列「1, 2, …, 14, 15」や「1, 2, 4, 8, 16, 15」を加算減算鎖と呼ぶ。加算減算鎖は、スカラ値がxの場合、a1=1から始まり、an=xで終わる数列である。数列を構成する各数値aiは、それ以前の二項の和または差になる、つまりai=aj±ak(j, k＜i)になる性質をもつ。
【０００５】
上述したx=15の場合、a1=1から始まり、an=15で終わる加算減算鎖は複数存在する。スカラ倍演算は、上述した加算減算鎖が最短になる構成であれば、二倍算、加算、減算の演算回数が最小になり、その結果、演算も最速になる。しかし、そのような加算減算鎖を見つけるアルゴリズムは知られていない。従って、加算減算鎖をできるだけ短くするようなアルゴリズムが望まれる。
【０００６】
非特許文献1は、加算減算鎖を短くすることができる手法の一つであるNAF+Sliding Window Method（以後、NAF Sウィンドウ法）を開示する。なお、NAFは「non-adjacent form」の略語である。まず、スカラ倍演算に使用する後述する倍算テーブルFkP（Fk=3, …, 2{2w-(-1)w}/3-1、wはウィンドウ長）を計算し、各FkPをメモリに格納する。FkPの総数は{2w-(-1)w}/3-1個である。なお、xPの演算過程には1Pも含まれるが、1P=Pであり、1Pの計算とメモリは必要としない。入力をP、x、w、FkPとし、出力QがxPになるアルゴリズムは次のとおりである。
xにNAFアルゴリズムを適用し、y（ビット長λ）に変換する；
Q = ∞；（無限遠点）
for (i=λ-1; i--; 0) {
Q = 2L(Fk)×Q； # 処理3-1
if (yi ≠ 0) Q = Q + FkP； # 処理3-2
i = i - L(Fk)； # L(Fk)はFkのビット長
}
ここで、Fkは、yiから始まり、yj=1になる中の最長のビット列の値(Fk = yi yi-1 … yj)（ただし、i-j＋1≦wの条件を満たす）。
【０００７】
上述のNAFアルゴリズムは以下のとおりである。なお、入力をx、出力をy（Σi=0,…,λ-1yi×2i）（yi∈{0, 1, -1}）とする。
i = 0；
while (x ≧ 1) {
if (xは奇数) {
yi = 2 - (x mod 4)；
x = x - yi；
} else { ； # xは偶数
yi = 0；
}
x = x/2；
i++；
}
【０００８】
上述のFkは負の値もとり得る。楕円曲線暗号では、Fkが負の値の場合のFkPは、Fkが正の値の場合のFkPから容易に求められる。例えば、素体上の楕円曲線の場合、点P=(x, y)のときは点-P=(x, -y)になる。同様に、2の拡大体上の楕円曲線の場合、点P=(x, y)のときは点-P=(x, x+y)になる。このため、Fkが負の値の倍算テーブルFkP [Fk=-3, …, -2{2w-(-1)w}/3-1]は、事前に算出した倍算テーブルFkPから容易に作成することができる。つまり、追加の演算、追加のメモリは不要である。
【０００９】
図1によりx=55（ウィンドウ長3ビット）の場合にNAF Sウィンドウ法を使ってxPを演算する過程を説明する。まず、上述のNAFアルゴリズムによりy=(1 0 0 -1 0 0 -1)になる。次に、図1(a)に示す事前演算処理によって倍算テーブルFkPを計算する。そして、図1(b)に示す実演算処理により55Pを計算する。この場合、加算減算鎖は「1→2→3→4→5→8→7→14→28→56→55」である。数列内の数値2、3、5が倍算テーブルを算出するために必要になる。
【００１０】
NAF Sウィンドウ法は、上述のアルゴリズムの処理3-2における点の加算回数を最大で1/wに低減し、xPを演算するための処理時間を短縮する。一方で、スカラxの値によって、実演算処理に使用しない倍算テーブルFkPがX個発生する。つまり、総数{2w-(-1)w}/3-1個の倍算テーブルのうち、X個の倍算テーブルを計算する処理時間と当該倍算テーブルを格納するメモリ領域に無駄が生じる場合がある。
【００１１】
例えば、図1に示す実演算処理の例において、yi='10-1'、'-101'に対応する数列Fk=3の倍算テーブル3P、yi='101'、'-10-1'に対応する数列Fk=5の倍算テーブル5Pは使用されない。言い替えれば、数列Fk=1、2に対応する倍算テーブルP、2Pを除く、総数{23-(-1)3}/3-1=2個の倍算テーブルのうち、二つの倍算テーブルが無駄である。
【００１２】
なお、数列1、2を含む倍算テーブルFkPの総数は{23-(-1)3}/3+1である。また、'10-1'、'-101'、'-10-1'を十進数で表現すると次のようになる。
'10-1' = 1×22 + 0×21 + (-1)×20 = 4 + 0 - 1 = 3、
'-101' = -1×22 + 0×21 + 1×20 = -4 + 0 +1 = -3、
'-10-1' = -1×22 + 0×21 + (-1)×20 = -4 + 0 - 1 = -5。
【先行技術文献】
【特許文献】
【００１３】
【特許文献１】特開2005-316038号公報
【非特許文献】
【００１４】
【非特許文献１】Erik De Win, Serge Mister, Bart Preneel, Michael J. Wiener「On the Peformance of Signature Schemes Based on Elliptic Curves」ANTS 1998年、252-266頁
【非特許文献２】Cetin Kaya Koc「High Speed RSA Implementation」RSA Laboratories, RSA Data Security, Inc.、Ver. 2.0、1994年11月
【発明の概要】
【発明が解決しようとする課題】
【００１５】
本発明は、NAF Sウィンドウ法に必要な倍算テーブルの総数よりも少ない倍算テーブル数でスカラ倍演算を行うことを目的とする。
【課題を解決するための手段】
【００１６】
本発明は、前記の目的を達成する一手段として、以下の構成を備える。
【００１７】
本発明にかかる情報処理は、楕円曲線上の点のスカラ倍演算を行う情報処理であって、スカラ（正の整数）を入力し、前記スカラを符号付き二進法の、負数を含む数値に変換し、前記数値を1ビットから最大分割ビット長wの範囲の複数の数値に分割し、前記複数の数値から特定の数値を選択し、前記選択された数値の絶対値を含み、項の総数が前記最大分割ビット長wの関数である閾値よりも少ない数列を取得し、前記複数の数値の絶対値のうち前記数列に含まれない数値を1ビットから前記最大分割ビット長wの範囲の複数の数値に再分割し、前記数列に含まれる2以上の各項をスカラに含む倍算テーブルを算出し、前記分割された複数の数値、前記再分割された複数の数値、および、前記倍算テーブルを用いて前記スカラ倍演算を行うことを特徴とする。
【発明の効果】
【００１８】
本発明によれば、NAF Sウィンドウ法に必要な倍算テーブルの総数よりも少ない倍算テーブル数でスカラ倍演算を行うように、スカラを再分割することができる。その結果、倍算テーブルを計算するための処理時間や倍算テーブルを格納するメモリ領域を削減することができ、NAF Sウィンドウ法よりも高速かつ省メモリでスカラ倍演算を行うことができる。
【図面の簡単な説明】
【００１９】
【図１】x=55（ウィンドウ長3ビット）の場合にNAF Sウィンドウ法を使ってxPを演算する過程を説明する図。
【図２】本実施例の楕円曲線上のスカラ倍演算を実行する情報処理装置の構成例を示すブロック図。
【図３】スカラの分割を説明する図。
【図４】スカラの分割、数列の選択、数列に基づく倍算テーブルの生成、スカラ倍演算までの一連の流れを説明するフローチャート。
【図５】本実施例のスカラ倍演算の過程を説明する図。
【図６】実施例2の楕円曲線上のスカラ倍演算を実行する情報処理装置の構成例を示すブロック図。
【図７】実施例2のスカラの分割、数列の選択、数列に基づく倍算テーブルの生成、スカラ倍演算までの一連の流れを説明するフローチャート。
【図８】実施例3の楕円曲線上のスカラ倍演算を実行する情報処理装置の構成例を示すブロック図。
【図９】実施例3のスカラの分割、数列の選択、数列に基づく倍算テーブルの生成、スカラ倍演算までの一連の流れを説明するフローチャート。
【発明を実施するための形態】
【００２０】
以下、本発明にかかる実施例の情報処理を図面を参照して詳細に説明する。
【実施例１】
【００２１】
［装置の構成］
図2のブロック図により本実施例の楕円曲線上のスカラ倍演算を実行する情報処理装置の構成例を示す。情報処理装置は、例えばCPU、ハードディスクドライブのような記憶装置、ROM、RAMのようなメモリなどのハードウェアを備える。そして、CPUが記憶装置やメモリに格納されたプログラムを実行することによりスカラ倍演算などの情報処理を行うコンピュータ装置である。
【００２２】
変換部11は、記憶装置などに格納された数値x（正の整数）を読み出し、数値xを符号付き二進法の、負数を含む数値yに変換する。数値xは、例えば公開鍵暗号における公開鍵や秘密鍵に該当する。公開鍵や秘密鍵は、予め記憶装置などに格納されたものを用いてもよいし、情報処理装置を扱うユーザが情報処理装置のユーザインタフェイスなどを介して入力してもよい。
【００２３】
符号付き二進法の数値への変換方法は、例えば、最下位ビットから最上位ビットに亘って変換を行うNAFアルゴリズムや、特許文献1に示される最上位ビットから最下位ビットに亘って変換を行うMOFアルゴリズムなどがある。なお、MOFは「mutual opposite form」の略語である。
【００２４】
図3によりスカラの分割を説明する。図3(a)は数値x=11957708941720303968251にNAFアルゴリズムを適用して得られる符号付き二進法の数値yを示す。初期分割部12は、変換部11が出力する符号付き二進法の数値yを入力し、1から最大分割ビット長wビットの範囲で符号付き二進法の数値yを分割する。
【００２５】
分割処理には、例えば非特許文献2の17-18頁に記載された方法を適用する。当該文献は、決定されたビット長固定で分割するconstant length nonzero windows (CLNW)、可変長かつ指定されたビット長を最大の分割長とするvariable length nonzero windows (VLNW)を記載する。上述したNAF Sウィンドウ法ではVLNWを使用する。図3(b)は、図3(a)に示す符号付き二進法の数値yをVLNW（ビット長5）を用いて分割した例を示す。以下では、図3(b)においてアポストロフィ「'」で括り、下線を施した数値を符号付き二進法の各数値yiとして説明する。
【００２６】
選択部13は、初期分割部12が分割した各数値yiのうち、特定の数値yxを選択する。数列算出部14は、選択部13の選択結果に基づき、|yx|を含む数列Fk（|yx|⊂Fk：k = 1, 2, …, m）を算出する。
【００２７】
再分割部15は、初期分割部12から分割結果yiを、数列算出部14から数列Fkを入力して、数列Fkに含まれない数値yiについて、1から最大分割ビット長wビットの範囲で複数の数値yj（yj⊂Fk：j = 1, 2, …）に再分割する。なお、再分割後の各数値yjは、必ず数列Fkに含まれる。
【００２８】
倍算テーブル算出部16は、数列算出部14から入力した数列Fkに基づき、数列FkのF2からFmまでの各項（つまり、2以上の項）をスカラに含む倍算テーブルFkPを算出する。
【００２９】
スカラ倍演算部17は、再分割部15から分割結果yiと再分割結果yjを、倍算テーブル算出部16から倍算テーブルFkPを入力して、点Pのスカラ倍Q=xPを演算する。スカラ倍演算は、楕円曲線上の点Qnを2λ倍する倍算演算Qn+1=2λ×Qnと、楕円曲線上の点Qn+1と倍算テーブルFkPの加算演算または減算演算Qn+2=Qn+1±FkPを繰り返し実行する。
【００３０】
［スカラ倍演算処理］
図4のフローチャートによりスカラの分割、数列の選択、数列に基づく倍算テーブルの生成、スカラ倍演算までの一連の流れを説明する。
【００３１】
変換部11は、スカラ倍演算のスカラxを入力する(S41)。スカラxは、上述したように、例えば256ビット長の秘密鍵である。変換部11は、スカラxを符号付き二進法の、負数を含む数値yに変換する(S42)。ここでは図3(a)に示す符号付き二進法の数値yが得られたとする。
【００３２】
次に、初期分割部12は、1から最大分割ビット長wビットの範囲で数値yを数値yiに分割する(S43)。ここでは図3(b)に示す分割結果が得られたとする。なお、分割ビット長の範囲は、情報処理装置が実行するプログラムによって指定される場合、情報処理装置を扱うユーザが情報処理装置のユーザインタフェイスなどを介して指定する場合などがある。
【００３３】
次に、選択部13は、初期分割部12によって分割された各数値yiから特定の数値yxを選択する(S44)。例えば、最も出現頻度が高い数値を選択する。図3(b)の例においては|(101/-10-1)|=5の出現頻度（三回）が最も高い。なお、数値の選択は、二番目に出現頻度の高い数値を選択する、情報処理装置が実行するプログラムによって指定された特定の値を選択するなど、任意の方法でよい。
【００３４】
次に、数列算出部14は、選択部13が選択した数値の絶対値|yx|を含む数列Fk（|yx|⊂Fk：k = 1, 2, …, m）を算出する(S45)。ここでいう数列は、上述した加算減算鎖を指す。数列の算出には所定のアルゴリズムを用いる。非特許文献2の22頁、26頁には、binary method（バイナリ法）、octal method（オクタル法）、factor method（ファクタ法）、booth algorithm（ブースアルゴリズム）などが記載されている。例えば、数値の絶対値|yx|=5にオクタル法を適用した場合、「5」を含む数列Fkとして「1, 2, 3, 4, 5」が算出される。
【００３５】
次に、数列算出部14は、算出した数列Fkの項の総数mが最大分割ビット長wの関数である閾値{2w-(-1)w}/3+1未満か否かを判定する(S46)。上述の数列Fkの場合、項の総数mは5である。図3(b)の例は分割長が1から5ビット、つまりw=5であり、閾値{25-(-1)5}/3+1=12になる。項の総数m＜閾値の場合は算出した数列Fkが再分割部15、倍算テーブル算出部16に出力する。一方、項の総数m≧閾値の場合は、処理をステップS45に戻し、他の数列算出方式により数列Fkを算出する。
【００３６】
再分割部15は、数列Fkを入力すると、初期分割部12から入力される各数値yiが数列Fkに含まれるか否かを判定する(S47)。数列Fkに含まれない数値yiが存在する場合、再分割部15は、当該数値yiを1からw-1ビットの範囲で複数の数値yj（yj⊂Fk：j = 1, 2, …）に再分割する(S48)。例えば、図3(b)に示す例では|100-1|=7、|-10-10-1|=21、|-100-1|=9が数列Fk「1, 2, 3, 4, 5」に含まれない。そこで、当該数値yiを、分割長の上限をw-1ビットにしてVLNWを用いて再分割し、処理をステップS47に戻す。
【００３７】
ステップS47とS48を繰り返すと、最終的に、図3(c)に示す分割結果が得られる。各数値yiは、それぞれ1=|(1/-1)|、3=|(10-1/-101)|、5=|(101/-10-1)|の何れかであり、yi⊂Fkを満たす。
【００３８】
次に、倍算テーブル算出部16は、数列算出部14が算出した数列Fkに基づき、数列FkのF2からFmまでの各項をスカラに含む倍算テーブルFkPを算出する(S49)。なお、算出された各FkPはメモリに格納される。
【００３９】
図5により本実施例のスカラ倍演算の過程を説明する。図5(a)は数列Fk「1, 2, 3, 4, 5」（Fk：k = 1, 2, 3, 4, 5：F1=1, F2=2, F3=3, F4=4, F5=5）から倍算テーブルFkPを算出する過程（事前演算処理）を示す。
【００４０】
加算減算鎖の性質、つまりai=aj±ak（j, k ＜ i）により、倍算テーブルの数値FiPは、それ以前に算出した数値の加減算FjP±FkPにより演算可能である。なお、数列の種類によらず、必ずF1=1とF2=2は存在するが、1P=Pであるため、Pの計算とメモリは必要としない。
【００４１】
スカラ倍演算部17は、再分割部15から入力した分割結果yiと再分割結果yj、および、メモリに格納された倍算テーブルFkPを用いてスカラ倍演算を行う(S50)。分割結果Wn（yi, yj⊂Wn）は、図3(c)のように表現されるものとする。入力をP、Wn、FkPとし、出力QがxPになるアルゴリズムは以下のとおりである。
Q = ∞；（無限遠点）
for (i = n-1; i--; 0) {
if (Wi = 0) Q = 2L(Wi)×Q； #処理3-1
if (Wi ≠ 0) {
Q = 2L(Wi)×Q； #処理3-1
Q = Q ± FkP; #処理3-2
}
}
ここで、L(Wi)はWiのビット長。
【００４２】
図5(b)はスカラx=11957708941720303968251の場合に、実施例の処理により11957708941720303968251P（Wn：n = 0, …, 26）を演算する過程（実演算処理）を示す。
【００４３】
NAF Sウィンドウ法は、{2w-(-1)w}/3＋1個（数列1、2を含む）の倍算テーブルFkPの候補をとる。一方、本実施例は、{2w-(-1)w}/3+1個よりも少ない倍算テーブルFkPの候補によりスカラ倍演算を行うために、スカラを再分割する。従って、本実施例のスカラ倍演算においては、NAF Sウィンドウ法に比べて、倍算テーブルFkPの候補を計算するための処理時間やメモリ領域を削減して、NAF Sウィンドウ法よりも高速かつ省メモリでスカラ倍演算を行うことができる。
【００４４】
また、削減した処理時間を有効活用するために、初期分割ビット長（1からwビット）の範囲を長くとることで、スカラ倍演算に必要な点の加算回数を低減することができる。これにより、全体のスカラ倍演算処理時間の削減が可能になる。
【００４５】
なお、上述した処理工程のうち、ステップS49とS50を除く各ステップは、スカラ倍演算のスカラxのみで処理可能である。上述したように、スカラxは、通常、公開鍵や秘密鍵であり、暗号処理中に鍵生成・鍵交換が必要な場合を除き、事前に取得することができる情報である。言い替えれば、スカラ倍演算の処理時間に影響を与えることなく、ステップS41からS48までの処理が実行可能である。
【実施例２】
【００４６】
以下、本発明にかかる実施例2の情報処理を説明する。なお、実施例2において、実施例1と略同様の構成については、同一符号を付して、その詳細説明を省略する。
【００４７】
［装置の構成］
図6のブロック図により実施例2の楕円曲線上のスカラ倍演算を実行する情報処理装置の構成例を示す。実施例2の情報処理装置は、実施例1の数列Fkを算出する数列算出部14の代わりに、複数の数列Fkを予め格納する数列格納部21を有する。さらに、選択部13から入力した数値を含む数列Fkを数列格納部21に格納された数列から選択する数列選択部22を有する。
【００４８】
数列格納部21は、数列Fk（Fk：k=1, 2, …, m）を複数格納する。なお、格納する数列Fkは、上述した加算減算鎖であり、項の総数mが{2w-(-1)w}/3+1個よりも少ない条件を満たす。
【００４９】
数列選択部22は、選択部13から入力した選択結果（数値yx）に基づき、数列格納部21に格納された複数の数列Fkから、|yx|を含む数列Fk（|yx|⊂Fk）を選択し、選択した数列Fkを再分割部15、倍算テーブル算出部16に出力する。
【００５０】
［スカラ倍演算処理］
図7のフローチャートにより実施例2のスカラの分割、数列の選択、数列に基づく倍算テーブルの生成、スカラ倍演算までの一連の流れを説明する。なお、ステップS41からS44、S47からS50の処理は、実施例1と同様の処理であり、その詳細説明を割愛する。
【００５１】
数列選択部22は、選択部103から入力した選択結果（数値yx）に基づき、数列格納部21に格納された複数の数列Fkから、|yx|を含む、項の総数が最小の数列Fk（|yx|⊂Fk）を選択する(S75)。
【００５２】
実施例1と同様に、図3(b)の符号付き二進法の数値yiから、数値yxとして5=|(101/-10-1)|が選択されたものとする。数列選択部22は、数列格納部21に格納された複数の数列Fkから、「5」を含む数列として「1, 2, 3, 5」を選択したとものとする。なお、上述したように、数列Fk「1, 2, 3, 5」は項の総数は4であり、{25-(-1)5}/3+1=12（最大分割長5ビット）よりも少ない条件を満す。
【００５３】
数列選択部22が選択する数列Fk「1, 2, 3, 5」は、実施例1においてオクタル法を用いて算出される数列Fk「1, 2, 3, 4, 5」よりも項数が少ない。図5に示す演算を考えると、図5(b)に示す実演算処理にかかる演算コストは実施例1と同様であり、図5(a)に示す事前演算処理における倍算テーブルFkPを求める演算コストは、「4P」の演算が不要な分、低下する。つまり、実施例2によれば、数列Fkの選択における柔軟性が向上し、選択した数列Fkによって、倍算テーブルFkPを計算する事前演算処理の時間やメモリ領域を削減することができる。
【実施例３】
【００５４】
以下、本発明にかかる実施例3の情報処理を説明する。なお、実施例3において、実施例1、2と略同様の構成については、同一符号を付して、その詳細説明を省略する。
【００５５】
［装置の構成］
図8のブロック図により実施例3の楕円曲線上のスカラ倍演算を実行する情報処理装置の構成例を示す。実施例3の情報処理装置は、演算方式が異なる二つのスカラ倍演算方式それぞれの総スカラ倍演算回数を計算する演算回数計算部31と、計算結果に応じて、スカラ倍演算回数がより少ないスカラ倍演算方式を選択的に実行する演算方式制御部32を有する。
【００５６】
演算回数計算部31は、再分割部15から分割結果yi、yjを入力し、数列算出部204から数列Fkを入力する。そして、入力した分割結果yi、yjおよび数列Fkに基づき、本実施例のスカラ倍演算による総スカラ倍演算回数と、例えばNAF Sウィンドウ法を用いるスカラ倍演算による総スカラ倍演算回数を計算する。
【００５７】
演算方式制御部32は、演算回数計算部31の計算結果に基づき、スカラ倍演算回数がより少ないスカラ倍演算方式を選択するとともに、数列算出部204に新たな数列Fk'を算出させ、スカラの分割処理をやり直す。
【００５８】
第一の演算部であるスカラ倍演算部17は本実施例のスカラ倍演算を実行し、第二の演算部であるスカラ倍演算部33はNAF Sウィンドウ法を用いるスカラ倍演算を実行する。なお、第二のスカラ倍演算部33が実行するスカラ倍演算は、NAF Sウィンドウ法に限らず、本実施例のスカラ倍演算の方法と異なるスカラ倍演算を行えばよい。
【００５９】
［スカラ倍演算処理］
図9のフローチャートにより実施例3のスカラの分割、数列の選択、数列に基づく倍算テーブルの生成、スカラ倍演算までの一連の流れを説明する。なお、ステップS41からS48の処理は、実施例1と同様の処理であり、その詳細説明を割愛する。
【００６０】
演算回数計算部208は、再分割部15から入力した分割結果yi、yj、および、数列算出部14から入力した数列Fkに基づき、第一のスカラ倍演算部17の総スカラ倍演算回数N1を計算する(S91)。そして、第二のスカラ倍演算部33の総スカラ倍演算回数N2を計算する(S92)。
【００６１】
総スカラ倍演算回数の計算は、倍算テーブル算出部16、第一のスカラ倍演算部17と同じアルゴリズムについて、実際の演算を行わずに、アルゴリズムにおけるスカラ倍演算の総数をカウントすることで実現する。例えば、11957708941720303968251P(Wn：n=0, …, 26)、数列Fk「1, 2, 3, 5」の場合、スカラ倍演算（倍算と加算または減算）の総数はN1=89になる。また、例えば、11957708941720303968251PにNAF Sウィンドウ法をウィンドウ長5ビットで適用した場合、スカラ倍演算の総数はN2=93になる。
【００６２】
次に、演算方法制御部32は、総スカラ倍演算回数N1とN2を比較する(S93)。第一のスカラ倍演算部17の総スカラ倍演算回数の方が少ない（N1＜N2）場合、実施例1と同様に、倍算テーブル算出部17による事前演算処理(S94)と、第一のスカラ倍演算部17による実演算処理(S95)が実行される。なお、ステップS94とS95の処理は、図4に示すステップS49とS50の処理と同様であり、その詳細説明を省略する。
【００６３】
一方、N1≧N2の場合、演算方法制御部32は、算出可能なすべての数列候補Fkを算出したか否かを数列算出部14に問い合わせる(S96)。未算出の数列候補Fkがある場合は、処理をステップS45に戻して、数列算出部14に別の数列算出方法を用いて新たな数列Fk'を算出させる。算出可能なすべての数列候補Fkが算出されると、第二のスカラ倍演算部33は、スカラ倍演算を実行する(S98)。
【００６４】
このように、本実施例のスカラ倍演算の演算コスト(N1)と他の方式のスカラ倍演算の演算コスト(N2)を比較してN1≧N2場合は、新たな数列を算出して処理をやり直す。ステップS95からS92の処理を繰り返し、算出可能なすべての数列候補Fkを算出しても、N1≧N2の場合は他の方式のスカラ倍演算を実行する。言い替えれば、スカラ倍演算に必要な総演算コストを、他の方式のスカラ倍演算を適用する場合にかかる総演算コスト以下に抑えることが可能である。
【００６５】
上記の説明においては、実施例1の構成に演算回数計算部31と演算方法制御部32を追加する例を説明したが、実施例2の構成に演算回数計算部31と演算方法制御部32を追加する構成も実現可能である。その場合、ステップS96の処理は、数列選択部22に、数列格納部21に格納されたすべての数列Fkを選択したか否かを問い合わせることになる。
【００６６】
［変形例］
●数列Fkの選択方法
上記では、数値|yx|を含む数列Fk（yx⊂Fk）の選択を説明したが、数値yxは複数あってもよい。例えば、図3(b)に示す例では、5=|(101/-10-1)|だけでなく7=|100-1|も含む数列Fk（例えば「1, 2, 3, 5, 7」）を選択するようにすれば、より効率的に数列Fkを選択する処理になる。
【００６７】
●スカラxの分割処理方法
上記では、スカラxをVLNWで分割または再分割する例を説明した。分割または再分割に用いる分割アルゴリズムは毎回異なってもよい。
【００６８】
例えば、ウィンドウ長4ビットで、選択した数値が「9」、選択した数列Fkが「1, 2, 4, 5, 10, 11, 9」の場合を考える。NAFアルゴリズムでウィンドウ長4ビットの場合、分割された各数値は-9から9の範囲に収まる。上述した実施例では、1からwビットの範囲で再分割を行うため、数値11='10101'は、5='101'と1='1'に再分割される。しかし、上記の数列Fkは「11」を含み、数値11のまま演算を行えばスカラ倍演算回数を一回削減することができる。つまり、ウィンドウ長を4ビットから5ビットに拡張すれば、再分割を行わなくてもよい。
【００６９】
このように、数列Fkに適応して分割アルゴリズムを変えることにより、スカラ倍演算回数の削減が可能になる。
【００７０】
［その他の実施例］
また、本発明は、以下の処理を実行することによっても実現される。即ち、上述した実施形態の機能を実現するソフトウェア（プログラム）を、ネットワーク又は各種記憶媒体を介してシステム或いは装置に供給し、そのシステムあるいは装置のコンピュータ（又はCPUやMPU等）がプログラムを読み出して実行する処理である。
【技術分野】
【０００１】
本発明は、スカラ倍演算を行う情報処理に関する。
【背景技術】
【０００２】
スカラ倍演算は、公開鍵暗号方式の一つである楕円曲線暗号において利用される演算である。公開鍵暗号方式は、暗号化と復号にそれぞれ異なる鍵を使用する暗号方式であり、データの暗号化、ディジタル署名、鍵配送などで利用される。楕円曲線暗号は、楕円曲線を利用した公開鍵暗号方式であり、離散対数計算の困難性に基づく、ECDSA署名、ECDH鍵配送方式などが代表例である。なお、ECDSAは「elliptic curve digital signature algorithm」の、ECDHは「elliptic curve Diffie-Hellman」の略称である。
【０００３】
スカラ倍演算(xP)は、楕円曲線上のある点Pをスカラ(x)倍する演算のことである。公開鍵暗号ではスカラxに大きな値（例えば256ビットの値）をとる。このため、スカラxを小さい単位に分解し、小さい単位で点の二倍算(2P)、点の加算(P+Q)、および、点の減算(P-Q)を繰り返し実行して、xPを求める方法が一般に用いられる。例えば、スカラx=15の場合、P→2P→…→14P→15Pのように、点Pを14回繰り返し加算することでxP=15Pが得られる。別の方法として、P→2P→4P→8P→16P→15Pのように、点の二倍算（例えば2P×2P=4P）と、点の減算（例えば16P-P=15P）を組み合わせてもxP=15Pを得ることができる。後者は、四回の二倍算と、一回の減算で済むため、前者よりも高速な演算が可能である。
【０００４】
P→2P→…→14P→15Pや、P→2P→4P→8P→16P→15Pのような計算過程のスカラに現れる数列「1, 2, …, 14, 15」や「1, 2, 4, 8, 16, 15」を加算減算鎖と呼ぶ。加算減算鎖は、スカラ値がxの場合、a1=1から始まり、an=xで終わる数列である。数列を構成する各数値aiは、それ以前の二項の和または差になる、つまりai=aj±ak(j, k＜i)になる性質をもつ。
【０００５】
上述したx=15の場合、a1=1から始まり、an=15で終わる加算減算鎖は複数存在する。スカラ倍演算は、上述した加算減算鎖が最短になる構成であれば、二倍算、加算、減算の演算回数が最小になり、その結果、演算も最速になる。しかし、そのような加算減算鎖を見つけるアルゴリズムは知られていない。従って、加算減算鎖をできるだけ短くするようなアルゴリズムが望まれる。
【０００６】
非特許文献1は、加算減算鎖を短くすることができる手法の一つであるNAF+Sliding Window Method（以後、NAF Sウィンドウ法）を開示する。なお、NAFは「non-adjacent form」の略語である。まず、スカラ倍演算に使用する後述する倍算テーブルFkP（Fk=3, …, 2{2w-(-1)w}/3-1、wはウィンドウ長）を計算し、各FkPをメモリに格納する。FkPの総数は{2w-(-1)w}/3-1個である。なお、xPの演算過程には1Pも含まれるが、1P=Pであり、1Pの計算とメモリは必要としない。入力をP、x、w、FkPとし、出力QがxPになるアルゴリズムは次のとおりである。
xにNAFアルゴリズムを適用し、y（ビット長λ）に変換する；
Q = ∞；（無限遠点）
for (i=λ-1; i--; 0) {
Q = 2L(Fk)×Q； # 処理3-1
if (yi ≠ 0) Q = Q + FkP； # 処理3-2
i = i - L(Fk)； # L(Fk)はFkのビット長
}
ここで、Fkは、yiから始まり、yj=1になる中の最長のビット列の値(Fk = yi yi-1 … yj)（ただし、i-j＋1≦wの条件を満たす）。
【０００７】
上述のNAFアルゴリズムは以下のとおりである。なお、入力をx、出力をy（Σi=0,…,λ-1yi×2i）（yi∈{0, 1, -1}）とする。
i = 0；
while (x ≧ 1) {
if (xは奇数) {
yi = 2 - (x mod 4)；
x = x - yi；
} else { ； # xは偶数
yi = 0；
}
x = x/2；
i++；
}
【０００８】
上述のFkは負の値もとり得る。楕円曲線暗号では、Fkが負の値の場合のFkPは、Fkが正の値の場合のFkPから容易に求められる。例えば、素体上の楕円曲線の場合、点P=(x, y)のときは点-P=(x, -y)になる。同様に、2の拡大体上の楕円曲線の場合、点P=(x, y)のときは点-P=(x, x+y)になる。このため、Fkが負の値の倍算テーブルFkP [Fk=-3, …, -2{2w-(-1)w}/3-1]は、事前に算出した倍算テーブルFkPから容易に作成することができる。つまり、追加の演算、追加のメモリは不要である。
【０００９】
図1によりx=55（ウィンドウ長3ビット）の場合にNAF Sウィンドウ法を使ってxPを演算する過程を説明する。まず、上述のNAFアルゴリズムによりy=(1 0 0 -1 0 0 -1)になる。次に、図1(a)に示す事前演算処理によって倍算テーブルFkPを計算する。そして、図1(b)に示す実演算処理により55Pを計算する。この場合、加算減算鎖は「1→2→3→4→5→8→7→14→28→56→55」である。数列内の数値2、3、5が倍算テーブルを算出するために必要になる。
【００１０】
NAF Sウィンドウ法は、上述のアルゴリズムの処理3-2における点の加算回数を最大で1/wに低減し、xPを演算するための処理時間を短縮する。一方で、スカラxの値によって、実演算処理に使用しない倍算テーブルFkPがX個発生する。つまり、総数{2w-(-1)w}/3-1個の倍算テーブルのうち、X個の倍算テーブルを計算する処理時間と当該倍算テーブルを格納するメモリ領域に無駄が生じる場合がある。
【００１１】
例えば、図1に示す実演算処理の例において、yi='10-1'、'-101'に対応する数列Fk=3の倍算テーブル3P、yi='101'、'-10-1'に対応する数列Fk=5の倍算テーブル5Pは使用されない。言い替えれば、数列Fk=1、2に対応する倍算テーブルP、2Pを除く、総数{23-(-1)3}/3-1=2個の倍算テーブルのうち、二つの倍算テーブルが無駄である。
【００１２】
なお、数列1、2を含む倍算テーブルFkPの総数は{23-(-1)3}/3+1である。また、'10-1'、'-101'、'-10-1'を十進数で表現すると次のようになる。
'10-1' = 1×22 + 0×21 + (-1)×20 = 4 + 0 - 1 = 3、
'-101' = -1×22 + 0×21 + 1×20 = -4 + 0 +1 = -3、
'-10-1' = -1×22 + 0×21 + (-1)×20 = -4 + 0 - 1 = -5。
【先行技術文献】
【特許文献】
【００１３】
【特許文献１】特開2005-316038号公報
【非特許文献】
【００１４】
【非特許文献１】Erik De Win, Serge Mister, Bart Preneel, Michael J. Wiener「On the Peformance of Signature Schemes Based on Elliptic Curves」ANTS 1998年、252-266頁
【非特許文献２】Cetin Kaya Koc「High Speed RSA Implementation」RSA Laboratories, RSA Data Security, Inc.、Ver. 2.0、1994年11月
【発明の概要】
【発明が解決しようとする課題】
【００１５】
本発明は、NAF Sウィンドウ法に必要な倍算テーブルの総数よりも少ない倍算テーブル数でスカラ倍演算を行うことを目的とする。
【課題を解決するための手段】
【００１６】
本発明は、前記の目的を達成する一手段として、以下の構成を備える。
【００１７】
本発明にかかる情報処理は、楕円曲線上の点のスカラ倍演算を行う情報処理であって、スカラ（正の整数）を入力し、前記スカラを符号付き二進法の、負数を含む数値に変換し、前記数値を1ビットから最大分割ビット長wの範囲の複数の数値に分割し、前記複数の数値から特定の数値を選択し、前記選択された数値の絶対値を含み、項の総数が前記最大分割ビット長wの関数である閾値よりも少ない数列を取得し、前記複数の数値の絶対値のうち前記数列に含まれない数値を1ビットから前記最大分割ビット長wの範囲の複数の数値に再分割し、前記数列に含まれる2以上の各項をスカラに含む倍算テーブルを算出し、前記分割された複数の数値、前記再分割された複数の数値、および、前記倍算テーブルを用いて前記スカラ倍演算を行うことを特徴とする。
【発明の効果】
【００１８】
本発明によれば、NAF Sウィンドウ法に必要な倍算テーブルの総数よりも少ない倍算テーブル数でスカラ倍演算を行うように、スカラを再分割することができる。その結果、倍算テーブルを計算するための処理時間や倍算テーブルを格納するメモリ領域を削減することができ、NAF Sウィンドウ法よりも高速かつ省メモリでスカラ倍演算を行うことができる。
【図面の簡単な説明】
【００１９】
【図１】x=55（ウィンドウ長3ビット）の場合にNAF Sウィンドウ法を使ってxPを演算する過程を説明する図。
【図２】本実施例の楕円曲線上のスカラ倍演算を実行する情報処理装置の構成例を示すブロック図。
【図３】スカラの分割を説明する図。
【図４】スカラの分割、数列の選択、数列に基づく倍算テーブルの生成、スカラ倍演算までの一連の流れを説明するフローチャート。
【図５】本実施例のスカラ倍演算の過程を説明する図。
【図６】実施例2の楕円曲線上のスカラ倍演算を実行する情報処理装置の構成例を示すブロック図。
【図７】実施例2のスカラの分割、数列の選択、数列に基づく倍算テーブルの生成、スカラ倍演算までの一連の流れを説明するフローチャート。
【図８】実施例3の楕円曲線上のスカラ倍演算を実行する情報処理装置の構成例を示すブロック図。
【図９】実施例3のスカラの分割、数列の選択、数列に基づく倍算テーブルの生成、スカラ倍演算までの一連の流れを説明するフローチャート。
【発明を実施するための形態】
【００２０】
以下、本発明にかかる実施例の情報処理を図面を参照して詳細に説明する。
【実施例１】
【００２１】
［装置の構成］
図2のブロック図により本実施例の楕円曲線上のスカラ倍演算を実行する情報処理装置の構成例を示す。情報処理装置は、例えばCPU、ハードディスクドライブのような記憶装置、ROM、RAMのようなメモリなどのハードウェアを備える。そして、CPUが記憶装置やメモリに格納されたプログラムを実行することによりスカラ倍演算などの情報処理を行うコンピュータ装置である。
【００２２】
変換部11は、記憶装置などに格納された数値x（正の整数）を読み出し、数値xを符号付き二進法の、負数を含む数値yに変換する。数値xは、例えば公開鍵暗号における公開鍵や秘密鍵に該当する。公開鍵や秘密鍵は、予め記憶装置などに格納されたものを用いてもよいし、情報処理装置を扱うユーザが情報処理装置のユーザインタフェイスなどを介して入力してもよい。
【００２３】
符号付き二進法の数値への変換方法は、例えば、最下位ビットから最上位ビットに亘って変換を行うNAFアルゴリズムや、特許文献1に示される最上位ビットから最下位ビットに亘って変換を行うMOFアルゴリズムなどがある。なお、MOFは「mutual opposite form」の略語である。
【００２４】
図3によりスカラの分割を説明する。図3(a)は数値x=11957708941720303968251にNAFアルゴリズムを適用して得られる符号付き二進法の数値yを示す。初期分割部12は、変換部11が出力する符号付き二進法の数値yを入力し、1から最大分割ビット長wビットの範囲で符号付き二進法の数値yを分割する。
【００２５】
分割処理には、例えば非特許文献2の17-18頁に記載された方法を適用する。当該文献は、決定されたビット長固定で分割するconstant length nonzero windows (CLNW)、可変長かつ指定されたビット長を最大の分割長とするvariable length nonzero windows (VLNW)を記載する。上述したNAF Sウィンドウ法ではVLNWを使用する。図3(b)は、図3(a)に示す符号付き二進法の数値yをVLNW（ビット長5）を用いて分割した例を示す。以下では、図3(b)においてアポストロフィ「'」で括り、下線を施した数値を符号付き二進法の各数値yiとして説明する。
【００２６】
選択部13は、初期分割部12が分割した各数値yiのうち、特定の数値yxを選択する。数列算出部14は、選択部13の選択結果に基づき、|yx|を含む数列Fk（|yx|⊂Fk：k = 1, 2, …, m）を算出する。
【００２７】
再分割部15は、初期分割部12から分割結果yiを、数列算出部14から数列Fkを入力して、数列Fkに含まれない数値yiについて、1から最大分割ビット長wビットの範囲で複数の数値yj（yj⊂Fk：j = 1, 2, …）に再分割する。なお、再分割後の各数値yjは、必ず数列Fkに含まれる。
【００２８】
倍算テーブル算出部16は、数列算出部14から入力した数列Fkに基づき、数列FkのF2からFmまでの各項（つまり、2以上の項）をスカラに含む倍算テーブルFkPを算出する。
【００２９】
スカラ倍演算部17は、再分割部15から分割結果yiと再分割結果yjを、倍算テーブル算出部16から倍算テーブルFkPを入力して、点Pのスカラ倍Q=xPを演算する。スカラ倍演算は、楕円曲線上の点Qnを2λ倍する倍算演算Qn+1=2λ×Qnと、楕円曲線上の点Qn+1と倍算テーブルFkPの加算演算または減算演算Qn+2=Qn+1±FkPを繰り返し実行する。
【００３０】
［スカラ倍演算処理］
図4のフローチャートによりスカラの分割、数列の選択、数列に基づく倍算テーブルの生成、スカラ倍演算までの一連の流れを説明する。
【００３１】
変換部11は、スカラ倍演算のスカラxを入力する(S41)。スカラxは、上述したように、例えば256ビット長の秘密鍵である。変換部11は、スカラxを符号付き二進法の、負数を含む数値yに変換する(S42)。ここでは図3(a)に示す符号付き二進法の数値yが得られたとする。
【００３２】
次に、初期分割部12は、1から最大分割ビット長wビットの範囲で数値yを数値yiに分割する(S43)。ここでは図3(b)に示す分割結果が得られたとする。なお、分割ビット長の範囲は、情報処理装置が実行するプログラムによって指定される場合、情報処理装置を扱うユーザが情報処理装置のユーザインタフェイスなどを介して指定する場合などがある。
【００３３】
次に、選択部13は、初期分割部12によって分割された各数値yiから特定の数値yxを選択する(S44)。例えば、最も出現頻度が高い数値を選択する。図3(b)の例においては|(101/-10-1)|=5の出現頻度（三回）が最も高い。なお、数値の選択は、二番目に出現頻度の高い数値を選択する、情報処理装置が実行するプログラムによって指定された特定の値を選択するなど、任意の方法でよい。
【００３４】
次に、数列算出部14は、選択部13が選択した数値の絶対値|yx|を含む数列Fk（|yx|⊂Fk：k = 1, 2, …, m）を算出する(S45)。ここでいう数列は、上述した加算減算鎖を指す。数列の算出には所定のアルゴリズムを用いる。非特許文献2の22頁、26頁には、binary method（バイナリ法）、octal method（オクタル法）、factor method（ファクタ法）、booth algorithm（ブースアルゴリズム）などが記載されている。例えば、数値の絶対値|yx|=5にオクタル法を適用した場合、「5」を含む数列Fkとして「1, 2, 3, 4, 5」が算出される。
【００３５】
次に、数列算出部14は、算出した数列Fkの項の総数mが最大分割ビット長wの関数である閾値{2w-(-1)w}/3+1未満か否かを判定する(S46)。上述の数列Fkの場合、項の総数mは5である。図3(b)の例は分割長が1から5ビット、つまりw=5であり、閾値{25-(-1)5}/3+1=12になる。項の総数m＜閾値の場合は算出した数列Fkが再分割部15、倍算テーブル算出部16に出力する。一方、項の総数m≧閾値の場合は、処理をステップS45に戻し、他の数列算出方式により数列Fkを算出する。
【００３６】
再分割部15は、数列Fkを入力すると、初期分割部12から入力される各数値yiが数列Fkに含まれるか否かを判定する(S47)。数列Fkに含まれない数値yiが存在する場合、再分割部15は、当該数値yiを1からw-1ビットの範囲で複数の数値yj（yj⊂Fk：j = 1, 2, …）に再分割する(S48)。例えば、図3(b)に示す例では|100-1|=7、|-10-10-1|=21、|-100-1|=9が数列Fk「1, 2, 3, 4, 5」に含まれない。そこで、当該数値yiを、分割長の上限をw-1ビットにしてVLNWを用いて再分割し、処理をステップS47に戻す。
【００３７】
ステップS47とS48を繰り返すと、最終的に、図3(c)に示す分割結果が得られる。各数値yiは、それぞれ1=|(1/-1)|、3=|(10-1/-101)|、5=|(101/-10-1)|の何れかであり、yi⊂Fkを満たす。
【００３８】
次に、倍算テーブル算出部16は、数列算出部14が算出した数列Fkに基づき、数列FkのF2からFmまでの各項をスカラに含む倍算テーブルFkPを算出する(S49)。なお、算出された各FkPはメモリに格納される。
【００３９】
図5により本実施例のスカラ倍演算の過程を説明する。図5(a)は数列Fk「1, 2, 3, 4, 5」（Fk：k = 1, 2, 3, 4, 5：F1=1, F2=2, F3=3, F4=4, F5=5）から倍算テーブルFkPを算出する過程（事前演算処理）を示す。
【００４０】
加算減算鎖の性質、つまりai=aj±ak（j, k ＜ i）により、倍算テーブルの数値FiPは、それ以前に算出した数値の加減算FjP±FkPにより演算可能である。なお、数列の種類によらず、必ずF1=1とF2=2は存在するが、1P=Pであるため、Pの計算とメモリは必要としない。
【００４１】
スカラ倍演算部17は、再分割部15から入力した分割結果yiと再分割結果yj、および、メモリに格納された倍算テーブルFkPを用いてスカラ倍演算を行う(S50)。分割結果Wn（yi, yj⊂Wn）は、図3(c)のように表現されるものとする。入力をP、Wn、FkPとし、出力QがxPになるアルゴリズムは以下のとおりである。
Q = ∞；（無限遠点）
for (i = n-1; i--; 0) {
if (Wi = 0) Q = 2L(Wi)×Q； #処理3-1
if (Wi ≠ 0) {
Q = 2L(Wi)×Q； #処理3-1
Q = Q ± FkP; #処理3-2
}
}
ここで、L(Wi)はWiのビット長。
【００４２】
図5(b)はスカラx=11957708941720303968251の場合に、実施例の処理により11957708941720303968251P（Wn：n = 0, …, 26）を演算する過程（実演算処理）を示す。
【００４３】
NAF Sウィンドウ法は、{2w-(-1)w}/3＋1個（数列1、2を含む）の倍算テーブルFkPの候補をとる。一方、本実施例は、{2w-(-1)w}/3+1個よりも少ない倍算テーブルFkPの候補によりスカラ倍演算を行うために、スカラを再分割する。従って、本実施例のスカラ倍演算においては、NAF Sウィンドウ法に比べて、倍算テーブルFkPの候補を計算するための処理時間やメモリ領域を削減して、NAF Sウィンドウ法よりも高速かつ省メモリでスカラ倍演算を行うことができる。
【００４４】
また、削減した処理時間を有効活用するために、初期分割ビット長（1からwビット）の範囲を長くとることで、スカラ倍演算に必要な点の加算回数を低減することができる。これにより、全体のスカラ倍演算処理時間の削減が可能になる。
【００４５】
なお、上述した処理工程のうち、ステップS49とS50を除く各ステップは、スカラ倍演算のスカラxのみで処理可能である。上述したように、スカラxは、通常、公開鍵や秘密鍵であり、暗号処理中に鍵生成・鍵交換が必要な場合を除き、事前に取得することができる情報である。言い替えれば、スカラ倍演算の処理時間に影響を与えることなく、ステップS41からS48までの処理が実行可能である。
【実施例２】
【００４６】
以下、本発明にかかる実施例2の情報処理を説明する。なお、実施例2において、実施例1と略同様の構成については、同一符号を付して、その詳細説明を省略する。
【００４７】
［装置の構成］
図6のブロック図により実施例2の楕円曲線上のスカラ倍演算を実行する情報処理装置の構成例を示す。実施例2の情報処理装置は、実施例1の数列Fkを算出する数列算出部14の代わりに、複数の数列Fkを予め格納する数列格納部21を有する。さらに、選択部13から入力した数値を含む数列Fkを数列格納部21に格納された数列から選択する数列選択部22を有する。
【００４８】
数列格納部21は、数列Fk（Fk：k=1, 2, …, m）を複数格納する。なお、格納する数列Fkは、上述した加算減算鎖であり、項の総数mが{2w-(-1)w}/3+1個よりも少ない条件を満たす。
【００４９】
数列選択部22は、選択部13から入力した選択結果（数値yx）に基づき、数列格納部21に格納された複数の数列Fkから、|yx|を含む数列Fk（|yx|⊂Fk）を選択し、選択した数列Fkを再分割部15、倍算テーブル算出部16に出力する。
【００５０】
［スカラ倍演算処理］
図7のフローチャートにより実施例2のスカラの分割、数列の選択、数列に基づく倍算テーブルの生成、スカラ倍演算までの一連の流れを説明する。なお、ステップS41からS44、S47からS50の処理は、実施例1と同様の処理であり、その詳細説明を割愛する。
【００５１】
数列選択部22は、選択部103から入力した選択結果（数値yx）に基づき、数列格納部21に格納された複数の数列Fkから、|yx|を含む、項の総数が最小の数列Fk（|yx|⊂Fk）を選択する(S75)。
【００５２】
実施例1と同様に、図3(b)の符号付き二進法の数値yiから、数値yxとして5=|(101/-10-1)|が選択されたものとする。数列選択部22は、数列格納部21に格納された複数の数列Fkから、「5」を含む数列として「1, 2, 3, 5」を選択したとものとする。なお、上述したように、数列Fk「1, 2, 3, 5」は項の総数は4であり、{25-(-1)5}/3+1=12（最大分割長5ビット）よりも少ない条件を満す。
【００５３】
数列選択部22が選択する数列Fk「1, 2, 3, 5」は、実施例1においてオクタル法を用いて算出される数列Fk「1, 2, 3, 4, 5」よりも項数が少ない。図5に示す演算を考えると、図5(b)に示す実演算処理にかかる演算コストは実施例1と同様であり、図5(a)に示す事前演算処理における倍算テーブルFkPを求める演算コストは、「4P」の演算が不要な分、低下する。つまり、実施例2によれば、数列Fkの選択における柔軟性が向上し、選択した数列Fkによって、倍算テーブルFkPを計算する事前演算処理の時間やメモリ領域を削減することができる。
【実施例３】
【００５４】
以下、本発明にかかる実施例3の情報処理を説明する。なお、実施例3において、実施例1、2と略同様の構成については、同一符号を付して、その詳細説明を省略する。
【００５５】
［装置の構成］
図8のブロック図により実施例3の楕円曲線上のスカラ倍演算を実行する情報処理装置の構成例を示す。実施例3の情報処理装置は、演算方式が異なる二つのスカラ倍演算方式それぞれの総スカラ倍演算回数を計算する演算回数計算部31と、計算結果に応じて、スカラ倍演算回数がより少ないスカラ倍演算方式を選択的に実行する演算方式制御部32を有する。
【００５６】
演算回数計算部31は、再分割部15から分割結果yi、yjを入力し、数列算出部204から数列Fkを入力する。そして、入力した分割結果yi、yjおよび数列Fkに基づき、本実施例のスカラ倍演算による総スカラ倍演算回数と、例えばNAF Sウィンドウ法を用いるスカラ倍演算による総スカラ倍演算回数を計算する。
【００５７】
演算方式制御部32は、演算回数計算部31の計算結果に基づき、スカラ倍演算回数がより少ないスカラ倍演算方式を選択するとともに、数列算出部204に新たな数列Fk'を算出させ、スカラの分割処理をやり直す。
【００５８】
第一の演算部であるスカラ倍演算部17は本実施例のスカラ倍演算を実行し、第二の演算部であるスカラ倍演算部33はNAF Sウィンドウ法を用いるスカラ倍演算を実行する。なお、第二のスカラ倍演算部33が実行するスカラ倍演算は、NAF Sウィンドウ法に限らず、本実施例のスカラ倍演算の方法と異なるスカラ倍演算を行えばよい。
【００５９】
［スカラ倍演算処理］
図9のフローチャートにより実施例3のスカラの分割、数列の選択、数列に基づく倍算テーブルの生成、スカラ倍演算までの一連の流れを説明する。なお、ステップS41からS48の処理は、実施例1と同様の処理であり、その詳細説明を割愛する。
【００６０】
演算回数計算部208は、再分割部15から入力した分割結果yi、yj、および、数列算出部14から入力した数列Fkに基づき、第一のスカラ倍演算部17の総スカラ倍演算回数N1を計算する(S91)。そして、第二のスカラ倍演算部33の総スカラ倍演算回数N2を計算する(S92)。
【００６１】
総スカラ倍演算回数の計算は、倍算テーブル算出部16、第一のスカラ倍演算部17と同じアルゴリズムについて、実際の演算を行わずに、アルゴリズムにおけるスカラ倍演算の総数をカウントすることで実現する。例えば、11957708941720303968251P(Wn：n=0, …, 26)、数列Fk「1, 2, 3, 5」の場合、スカラ倍演算（倍算と加算または減算）の総数はN1=89になる。また、例えば、11957708941720303968251PにNAF Sウィンドウ法をウィンドウ長5ビットで適用した場合、スカラ倍演算の総数はN2=93になる。
【００６２】
次に、演算方法制御部32は、総スカラ倍演算回数N1とN2を比較する(S93)。第一のスカラ倍演算部17の総スカラ倍演算回数の方が少ない（N1＜N2）場合、実施例1と同様に、倍算テーブル算出部17による事前演算処理(S94)と、第一のスカラ倍演算部17による実演算処理(S95)が実行される。なお、ステップS94とS95の処理は、図4に示すステップS49とS50の処理と同様であり、その詳細説明を省略する。
【００６３】
一方、N1≧N2の場合、演算方法制御部32は、算出可能なすべての数列候補Fkを算出したか否かを数列算出部14に問い合わせる(S96)。未算出の数列候補Fkがある場合は、処理をステップS45に戻して、数列算出部14に別の数列算出方法を用いて新たな数列Fk'を算出させる。算出可能なすべての数列候補Fkが算出されると、第二のスカラ倍演算部33は、スカラ倍演算を実行する(S98)。
【００６４】
このように、本実施例のスカラ倍演算の演算コスト(N1)と他の方式のスカラ倍演算の演算コスト(N2)を比較してN1≧N2場合は、新たな数列を算出して処理をやり直す。ステップS95からS92の処理を繰り返し、算出可能なすべての数列候補Fkを算出しても、N1≧N2の場合は他の方式のスカラ倍演算を実行する。言い替えれば、スカラ倍演算に必要な総演算コストを、他の方式のスカラ倍演算を適用する場合にかかる総演算コスト以下に抑えることが可能である。
【００６５】
上記の説明においては、実施例1の構成に演算回数計算部31と演算方法制御部32を追加する例を説明したが、実施例2の構成に演算回数計算部31と演算方法制御部32を追加する構成も実現可能である。その場合、ステップS96の処理は、数列選択部22に、数列格納部21に格納されたすべての数列Fkを選択したか否かを問い合わせることになる。
【００６６】
［変形例］
●数列Fkの選択方法
上記では、数値|yx|を含む数列Fk（yx⊂Fk）の選択を説明したが、数値yxは複数あってもよい。例えば、図3(b)に示す例では、5=|(101/-10-1)|だけでなく7=|100-1|も含む数列Fk（例えば「1, 2, 3, 5, 7」）を選択するようにすれば、より効率的に数列Fkを選択する処理になる。
【００６７】
●スカラxの分割処理方法
上記では、スカラxをVLNWで分割または再分割する例を説明した。分割または再分割に用いる分割アルゴリズムは毎回異なってもよい。
【００６８】
例えば、ウィンドウ長4ビットで、選択した数値が「9」、選択した数列Fkが「1, 2, 4, 5, 10, 11, 9」の場合を考える。NAFアルゴリズムでウィンドウ長4ビットの場合、分割された各数値は-9から9の範囲に収まる。上述した実施例では、1からwビットの範囲で再分割を行うため、数値11='10101'は、5='101'と1='1'に再分割される。しかし、上記の数列Fkは「11」を含み、数値11のまま演算を行えばスカラ倍演算回数を一回削減することができる。つまり、ウィンドウ長を4ビットから5ビットに拡張すれば、再分割を行わなくてもよい。
【００６９】
このように、数列Fkに適応して分割アルゴリズムを変えることにより、スカラ倍演算回数の削減が可能になる。
【００７０】
［その他の実施例］
また、本発明は、以下の処理を実行することによっても実現される。即ち、上述した実施形態の機能を実現するソフトウェア（プログラム）を、ネットワーク又は各種記憶媒体を介してシステム或いは装置に供給し、そのシステムあるいは装置のコンピュータ（又はCPUやMPU等）がプログラムを読み出して実行する処理である。
【特許請求の範囲】
【請求項１】
楕円曲線上の点のスカラ倍演算を行う情報処理装置であって、
スカラ（正の整数）を入力し、前記スカラを符号付き二進法の、負数を含む数値に変換する変換手段と、
前記数値を1ビットから最大分割ビット長wの範囲の複数の数値に分割する分割手段と、
前記複数の数値から特定の数値を選択する選択手段と、
前記選択された数値の絶対値を含み、項の総数が前記最大分割ビット長wの関数である閾値よりも少ない数列を取得する取得手段と、
前記複数の数値の絶対値のうち前記数列に含まれない数値を1ビットから前記最大分割ビット長wの範囲の複数の数値に再分割する再分割手段と、
前記数列に含まれる2以上の各項をスカラに含む倍算テーブルを算出する算出手段と、
前記分割された複数の数値、前記再分割された複数の数値、および、前記倍算テーブルを用いて前記スカラ倍演算を行う第一の演算手段とを有することを特徴とする情報処理装置。
【請求項２】
前記閾値は、NAF Sウィンドウ法における倍算テーブルの候補の数であることを特徴とする請求項1に記載された情報処理装置。
【請求項３】
前記候補の数は{2w-(-1)w}/3+1から計算されることを特徴とする請求項2に記載された情報処理装置。
【請求項４】
前記第一の演算手段は、前記楕円曲線上の点を2λ倍（λは1≦λ≦wの整数）する倍算演算と、前記楕円曲線上の点と前記倍算テーブルの加算演算または減算演算を、前記数値の最上位ビットから最下位ビットまで繰り返して、前記楕円曲線上の点の前記スカラ倍を演算することを特徴とする請求項1から請求項3の何れか一項に記載された情報処理装置。
【請求項５】
前記取得手段は、所定のアルゴリズムにより前記数列を計算することを特徴とする請求項1から請求項4の何れか一項に記載された情報処理装置。
【請求項６】
さらに、前記項の総数が前記閾値よりも少ない条件を満たす複数の数列を格納する格納手段を有し、
前記取得手段は、前記格納手段に格納された複数の数列から、前記選択された数値の絶対値を含み、前記項の総数が最小の数列を選択することを特徴とする請求項1から請求項4の何れか一項に記載された情報処理装置。
【請求項７】
さらに、前記第一の演算手段とは異なる方法により、前記スカラ倍演算を行う第二の演算手段と、
前記分割された複数の数値、前記再分割された複数の数値および前記数列に基づき、前記第一の演算手段の総スカラ倍演算回数N1および前記第二の演算手段の総スカラ倍演算回数N2を計算する計算手段と、
前記総スカラ倍演算回数N1とN2を用いて、前記第一の演算手段による前記スカラ倍演算、および、前記第二の演算手段による前記スカラ倍演算を選択的に制御する制御手段とを有することを特徴とする請求項1から請求項6の何れか一項に記載された情報処理装置。
【請求項８】
変換手段、分割手段、選択手段、取得手段、再分割手段、算出手段、演算手段を有し、楕円曲線上の点のスカラ倍演算を行う情報処理装置の情報処理方法であって、
前記変換手段が、スカラ（正の整数）を入力し、前記スカラを符号付き二進法の、負数を含む数値に変換し、
前記分割手段が、前記数値を1ビットから最大分割ビット長wの範囲の複数の数値に分割し、
前記選択手段が、前記複数の数値から特定の数値を選択し、
前記取得手段が、前記選択された数値の絶対値を含み、項の総数が前記最大分割ビット長wの関数である閾値よりも少ない数列を取得し、
前記再分割手段が、前記複数の数値の絶対値のうち前記数列に含まれない数値を1ビットから前記最大分割ビット長wの範囲の複数の数値に再分割し、
前記算出手段が、前記数列に含まれる2以上の各項をスカラに含む倍算テーブルを算出し、
前記演算手段が、前記分割された複数の数値、前記再分割された複数の数値、および、前記倍算テーブルを用いて前記スカラ倍演算を行うことを特徴とする情報処理方法。
【請求項９】
コンピュータを請求項1から請求項7の何れか一項に記載された情報処理装置の各手段として機能させるためのプログラム。
【請求項１】
楕円曲線上の点のスカラ倍演算を行う情報処理装置であって、
スカラ（正の整数）を入力し、前記スカラを符号付き二進法の、負数を含む数値に変換する変換手段と、
前記数値を1ビットから最大分割ビット長wの範囲の複数の数値に分割する分割手段と、
前記複数の数値から特定の数値を選択する選択手段と、
前記選択された数値の絶対値を含み、項の総数が前記最大分割ビット長wの関数である閾値よりも少ない数列を取得する取得手段と、
前記複数の数値の絶対値のうち前記数列に含まれない数値を1ビットから前記最大分割ビット長wの範囲の複数の数値に再分割する再分割手段と、
前記数列に含まれる2以上の各項をスカラに含む倍算テーブルを算出する算出手段と、
前記分割された複数の数値、前記再分割された複数の数値、および、前記倍算テーブルを用いて前記スカラ倍演算を行う第一の演算手段とを有することを特徴とする情報処理装置。
【請求項２】
前記閾値は、NAF Sウィンドウ法における倍算テーブルの候補の数であることを特徴とする請求項1に記載された情報処理装置。
【請求項３】
前記候補の数は{2w-(-1)w}/3+1から計算されることを特徴とする請求項2に記載された情報処理装置。
【請求項４】
前記第一の演算手段は、前記楕円曲線上の点を2λ倍（λは1≦λ≦wの整数）する倍算演算と、前記楕円曲線上の点と前記倍算テーブルの加算演算または減算演算を、前記数値の最上位ビットから最下位ビットまで繰り返して、前記楕円曲線上の点の前記スカラ倍を演算することを特徴とする請求項1から請求項3の何れか一項に記載された情報処理装置。
【請求項５】
前記取得手段は、所定のアルゴリズムにより前記数列を計算することを特徴とする請求項1から請求項4の何れか一項に記載された情報処理装置。
【請求項６】
さらに、前記項の総数が前記閾値よりも少ない条件を満たす複数の数列を格納する格納手段を有し、
前記取得手段は、前記格納手段に格納された複数の数列から、前記選択された数値の絶対値を含み、前記項の総数が最小の数列を選択することを特徴とする請求項1から請求項4の何れか一項に記載された情報処理装置。
【請求項７】
さらに、前記第一の演算手段とは異なる方法により、前記スカラ倍演算を行う第二の演算手段と、
前記分割された複数の数値、前記再分割された複数の数値および前記数列に基づき、前記第一の演算手段の総スカラ倍演算回数N1および前記第二の演算手段の総スカラ倍演算回数N2を計算する計算手段と、
前記総スカラ倍演算回数N1とN2を用いて、前記第一の演算手段による前記スカラ倍演算、および、前記第二の演算手段による前記スカラ倍演算を選択的に制御する制御手段とを有することを特徴とする請求項1から請求項6の何れか一項に記載された情報処理装置。
【請求項８】
変換手段、分割手段、選択手段、取得手段、再分割手段、算出手段、演算手段を有し、楕円曲線上の点のスカラ倍演算を行う情報処理装置の情報処理方法であって、
前記変換手段が、スカラ（正の整数）を入力し、前記スカラを符号付き二進法の、負数を含む数値に変換し、
前記分割手段が、前記数値を1ビットから最大分割ビット長wの範囲の複数の数値に分割し、
前記選択手段が、前記複数の数値から特定の数値を選択し、
前記取得手段が、前記選択された数値の絶対値を含み、項の総数が前記最大分割ビット長wの関数である閾値よりも少ない数列を取得し、
前記再分割手段が、前記複数の数値の絶対値のうち前記数列に含まれない数値を1ビットから前記最大分割ビット長wの範囲の複数の数値に再分割し、
前記算出手段が、前記数列に含まれる2以上の各項をスカラに含む倍算テーブルを算出し、
前記演算手段が、前記分割された複数の数値、前記再分割された複数の数値、および、前記倍算テーブルを用いて前記スカラ倍演算を行うことを特徴とする情報処理方法。
【請求項９】
コンピュータを請求項1から請求項7の何れか一項に記載された情報処理装置の各手段として機能させるためのプログラム。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【公開番号】特開２０１３−５７８２８（Ｐ２０１３−５７８２８Ａ）
【公開日】平成２５年３月２８日（２０１３．３．２８）
【国際特許分類】
【出願番号】特願２０１１−１９６５００（Ｐ２０１１−１９６５００）
【出願日】平成２３年９月８日（２０１１．９．８）
【出願人】（０００００１００７）キヤノン株式会社 (59,756)
【Ｆターム（参考）】
【公開日】平成２５年３月２８日（２０１３．３．２８）
【国際特許分類】
【出願日】平成２３年９月８日（２０１１．９．８）
【出願人】（０００００１００７）キヤノン株式会社 (59,756)
【Ｆターム（参考）】
[ Back to top ]