(57)【要約】【課題】正整数ｋとｌを２進展開した行列における非ゼロ列の数よりも少ない点加算回数で、高速な楕円同時スカラー倍演算を実行することを目的とする。【解決手段】曲線上の複数の点の値とそれぞれ２進数の複数の正整数とを入力する入力部４０１と、上記正整数の非ゼロ列の数の合計値を初期合計値として記憶する記憶部４０２と、上記各正整数に対し、順に、シフトするシフト部４１０と、非ゼロ列の数の合計値と、上記初期合計値と、各シフト値とを用いて、上記シフトされた場合の楕円曲線上の複数の点のスカラー倍点の和を計算するための計算回数の合計値とシフトされない場合の楕円曲線上の複数の点のスカラー倍点の和を計算するための計算回数の合計値との差が最大となる計算回数合計差分値を選択する最大値計算部４０５と、楕円曲線上の複数の点の値のスカラー倍の和を計算する計算部５２０とを備えたことを特徴とする。【選択図】　　　　図３
2004117627.tif 000002
【特許請求の範囲】
【請求項１】
楕円曲線上の複数の点の値とそれぞれ所定の桁数を有する２進数の複数の正整数とを入力する入力部と、
上記入力部により入力された複数の正整数の同位置の桁に１つでも１が割り当てられた桁の数の合計値を初期合計値として記憶する記憶部と、
上記複数の正整数の各正整数に対し、順に、上記複数の正整数の内１つを残して他の少なくとも１つの正整数の各桁に割り当てられた値を１桁ずつ所定の上限値までシフトするシフト部と、
上記シフト部によりシフトされた結果として上記複数の正整数の同位置の桁に１つでも１が割り当てられた桁の数の合計値と、上記記憶部に記憶された初期合計値と、上記シフト部によりシフトされた上記各正整数のシフト値とを用いて、上記シフト部によりシフトされた場合の楕円曲線上の複数の点のスカラー倍点の和を計算するための計算回数の合計値と上記シフト部によりシフトされない場合の楕円曲線上の複数の点のスカラー倍点の和を計算するための計算回数の合計値との差を上記各正整数の計算回数合計差分値としてそれぞれ計算し、上記各正整数の計算回数合計差分値を上記記憶部に記憶させる第１の計算部と、
上記第１の計算部により計算され上記記憶部に記憶された上記各正整数の計算回数合計差分値の内、最大となる計算回数合計差分値を選択し、選択された計算回数合計差分値を上記記憶部に記憶させる選択部と、
上記選択部により選択され上記記憶部に記憶された計算回数合計差分値が正の場合、上記選択部により選択され上記記憶部に記憶された計算回数合計差分値を計算させた複数の正整数の内上記シフト部によりシフトされた少なくとも１つの正整数と、複数の正整数の内上記シフト部によりシフトされていない他の正整数とを用いて、楕円曲線上の複数の点の値のスカラー倍の和を計算し、上記選択部により選択され上記記憶部に記憶された計算回数合計差分値が正でない場合、上記シフト部によりシフトされていない上記入力部により入力された複数の正整数を用いて、楕円曲線上の複数の点の値のスカラー倍の和を計算し、計算された楕円曲線上の複数の点の値のスカラー倍の和を上記記憶部に記憶させる第２の計算部と、
上記第２の計算部により計算され上記記憶部に記憶された楕円曲線上の複数の点の値のスカラー倍の和を出力する出力部と
を備えたことを特徴とする楕円曲線演算装置。
【請求項２】
上記第２の計算部は、楕円曲線上の複数の点の値のスカラー倍の和を計算するにあたり、上記シフト部によりシフトされた１つの正整数と数値２に上記１つの正整数のシフト値をべき乗した第１の補正値とを乗じ、さらに、上記１つの正整数が上記シフト部によりシフトされなかった場合に加算されていたであろう値の代わりに、上記乗じた値と上記シフト部によりシフトされた１つの正整数を計算に用いたことにより生じる第２の補正値とを楕円曲線上の複数の点の値のスカラー倍の和に加算することにより楕円曲線上の複数の点の値のスカラー倍の和を補正することを特徴とする請求項１記載の楕円曲線演算装置。
【請求項３】
上記楕円曲線演算装置は、さらに、上記入力部により入力された複数の正整数に対し、所定のブロック数により複数の正整数の桁を複数のブロックに分割する分割部を備え、
上記記憶部は、上記分割部により分割された所定のブロック数毎に、複数の正整数の同位置の桁に１つでも１が割り当てられた桁の数の合計値を初期合計値として記憶し、
上記シフト部は、上記分割部により分割された所定のブロック数毎に、上記複数の正整数の各正整数に対し、順に、上記複数の正整数の内１つを残して他の少なくとも１つの正整数の各桁に割り当てられた値を１桁ずつ所定の上限値までシフトし、
上記第１の計算部は、上記分割部により分割された所定のブロック数毎に、上記シフト部によりシフトされた結果として上記複数の正整数の同位置の桁に１つでも１が割り当てられた桁の数の合計値と、上記記憶部に記憶された初期合計値と、上記シフト部によりシフトされた上記各正整数のシフト値とを用いて、上記シフト部によりシフトされた場合の楕円曲線上の複数の点のスカラー倍点の和を計算するための計算回数の合計値と上記シフト部によりシフトされない場合の楕円曲線上の複数の点のスカラー倍点の和を計算するための計算回数の合計値との差を上記各正整数の計算回数合計差分値としてそれぞれ計算し、上記各正整数の計算回数合計差分値を上記記憶部に記憶させ、
上記選択部は、上記分割部により分割された所定のブロック数毎に、上記第１の計算部により計算され上記記憶部に記憶された上記各正整数の計算回数合計差分値の内、最大となる計算回数合計差分値を選択し、選択された計算回数合計差分値を上記記憶部に記憶させ、
上記第２の計算部は、上記分割部により分割された所定のブロック数毎に、上記選択部により選択され上記記憶部に記憶された計算回数合計差分値が正の場合、上記選択部により選択され上記記憶部に記憶された計算回数合計差分値を計算させた複数の正整数の内、上記シフト部によりシフトされた少なくとも１つの正整数と複数の正整数の内、上記シフト部によりシフトされていない他の正整数とを用いて、楕円曲線上の複数の点の値のスカラー倍の和を計算し、上記選択部により選択され上記記憶部に記憶された計算回数合計差分値が正でない場合、上記シフト部によりシフトされていない上記入力部により入力された複数の正整数を用いて、楕円曲線上の複数の点の値のスカラー倍の和を計算し、所定のブロック数毎に計算された楕円曲線上の複数の点の値のスカラー倍の和の合計値を上記記憶部に記憶させ、
上記出力部は、上記第２の計算部により計算され上記記憶部に記憶された楕円曲線上の複数の点の値のスカラー倍の和の合計値を出力することを特徴とする請求項１記載の楕円曲線演算装置。
【請求項４】
楕円曲線上の２点ＰとＱの値と、ｔビットの２つの正整数ｋとｌと、シフト長の上限値ｓ（０以上の整数）と、楕円曲線上の点加算の計算量Ａと、楕円曲線上の点２倍算の計算量Ｄとを入力する入力部と、
上記入力部により入力されたｋとｌとの連結ハミング重みＪＨＷ００＝ＪＨＷ（ｋ，ｌ）を計算し、記憶装置に記憶する第１の計算部と、
変数ｉを上記記憶装置に記憶するｉ記憶部と、
上記ｉ記憶部により記憶された変数ｉに初期値１を設定し、上記記憶装置に記憶するｉ初期値設定部と、
上記入力部により入力されたシフト長の上限値ｓと、上記記憶装置から読み出した上記ｉ初期値設定部により設定された変数ｉとを用いて、変数ｉがシフト長の上限値ｓに達するまで変数ｉに順次１を加えて、上記記憶装置に記憶するｉインクリメント部と、
上記ｉインクリメント部により上記記憶装置に変数ｉに順次１が加えられ記憶される度に、上記記憶装置から読み出した変数ｉと、上記入力部により入力された整数ｋと整数ｌとを用いて、整数ｋをｉビット右シフトした値（ｋ＞＞ｉ）と整数ｌとの連結ハミング重みＪＨＷｉ０＝ＪＨＷ（ｋ＞＞ｉ，ｌ）を計算し、上記記憶装置に記憶する第２の計算部と、
上記ｉインクリメント部により上記記憶装置に変数ｉに順次１が加えられ記憶される度に、上記記憶装置から読み出した変数ｉと、上記入力部により入力された整数ｋと整数ｌとを用いて、整数ｋと整数ｌをｉビット右シフトした値（ｌ＞＞ｉ）との連結ハミング重みＪＨＷ０ｉ＝ＪＨＷ（ｋ，ｌ＞＞ｉ）を計算し、上記記憶装置に記憶する第３の計算部と、
上記ｉインクリメント部により上記記憶装置に変数ｉに順次１が加えられ記憶される度に、上記記憶装置から読み出した変数ｉと上記第１の計算部により計算された連結ハミング重みＪＨＷ００と上記第２の計算部により計算された連結ハミング重みＪＨＷｉ０と、上記入力部により入力された楕円曲線上の点加算の計算量Ａと楕円曲線上の点２倍算の計算量Ｄとを用いて、計算量減少量Ｒｅｄｕｃｔｉｏｎｉ０＝（ＪＨＷ００−ＪＨＷｉ０）Ａ−ｉＤを計算し、上記記憶装置に記憶する第４の計算部と、
上記ｉインクリメント部により上記記憶装置に変数ｉに順次１が加えられ記憶される度に、上記記憶装置から読み出した変数ｉと上記第１の計算部により計算された連結ハミング重みＪＨＷ００と、上記第３の計算部により計算された連結ハミング重みＪＨＷ０ｉと、楕円曲線上の点加算の計算量Ａと、楕円曲線上の点２倍算の計算量Ｄとを読み出し、計算量減少量Ｒｅｄｕｃｔｉｏｎ０ｉ＝（ＪＨＷ００−ＪＨＷ０ｉ）Ａ−ｉＤを計算し、上記記憶装置に記憶する第５の計算部と、
上記第４の計算部により計算された計算量減少量Ｒｅｄｕｃｔｉｏｎｉ０と上記上記第５の計算部により計算された計算量減少量Ｒｅｄｕｃｔｉｏｎ０ｉとの内、計算量減少量の最大値を計算し、上記記憶装置に記憶する第６の計算部と、
上記第６の計算部により計算された計算量減少量の最大値が正の値である場合には上記最大値に対応する計算量減少量に用いられた整数ｋと整数ｌとの組合わせである（ｋ＞＞ｉ，ｌ）と（ｋ，ｌ＞＞ｉ）とのいずれか、上記第６の計算部により計算された計算量減少量の最大値が負の値である場合には上記入力部により入力された整数ｋと整数ｌとの組合わせである（ｋ，ｌ）を用いて、上記入力部により入力された楕円曲線上の２点ＰとＱの値のスカラー倍の和を計算し、上記記憶装置に記憶する第７の計算部と、
上記第７の計算部により計算された楕円曲線上の２点ＰとＱの値のスカラー倍の和を出力する出力部と
を備えたことを特徴とする楕円曲線演算装置。
【請求項５】
上記第７の計算部は、
計算に用いられた整数ｋと整数ｌとの組合わせが（ｋ，ｌ）の場合、ＰをＰｓに、ＱをＱｓに、ｋをｋ’に、ｌをｌ’に変換し、数値０の値を有する第１の補正値ｃと無限遠点値を有する第２の補正値Ｒとを設定し、上記記憶装置に記憶し、
計算に用いられた整数ｋと整数ｌとの組合わせであるが（ｋ＞＞ｉ，ｌ）の場合、２ｓ’ＰをＰｓに、ＱをＱｓに、ｋ＞＞ｉをｋ’に、ｌをｌ’に変換し、ｋと（２ｉ−１）とのビット毎の論理積の値ｋ∧（２ｉ−１）を有する第１の補正値ｃと楕円曲線上の点Ｐの値を有する第２の補正値Ｒとを設定し、上記記憶装置に記憶し、
計算に用いられた整数ｋと整数ｌとの組合わせが（ｋ，ｌ＞＞ｉ）の場合、ＰをＰｓに、２ｓ’ＱをＱｓに、ｋをｋ’に、ｌ＞＞ｉをｌ’に変換し、ｌと（２ｉ−１）とのビット毎の論理積の値ｌ∧（２ｉ−１）を有する第１の補正値ｃと楕円曲線上の点Ｑの値を有する第２の補正値Ｒとを設定し、上記記憶装置に記憶する変換設定部と、
変換設定部により変換されたＰｓとＱｓとｋ’とｌ’と、上記変換設定部により設定された第１の補正値ｃと第２の補正値Ｒとを用いて補正された楕円曲線上の２点ＰとＱの値のスカラー倍の和ｋ’Ｐｓ＋ｌ’Ｑｓ＋ｃＲを計算し、上記記憶装置に記憶するスカラー倍計算部と
を有することを特徴とする請求項４記載の楕円曲線演算装置。
【請求項６】
上記入力部は、さらに、上記ｔビットを分割するためのブロック長ｂ（正整数）を入力し、
上記第１の計算部は、整数ｋと整数ｌの上位ｉ番目のｂビットブロック毎に、上記入力部により入力されたｋとｌとの連結ハミング重みＪＨＷ００＝ＪＨＷ（ｋ，ｌ）を計算し、記憶装置に記憶し、
上記ｉインクリメント部は、ｔをｂで除し、除した値の内の整数ｔ／ｂと、変数ｉとを用いて、変数ｉが整数ｔ／ｂに達するまで変数ｉに順次１を加えて、上記記憶装置に記憶し、
上記第２の計算部は、上記ｉインクリメント部により変数ｉに順次１を加えられる度に、整数ｋと整数ｌの上位ｉ番目のｂビットブロック毎に、上記記憶装置から読み出した変数ｉと、上記入力部により入力された整数ｋと整数ｌとを用いて、整数ｋをｉビット右シフトした値（ｋ＞＞ｉ）と整数ｌとの連結ハミング重みＪＨＷｉ０＝ＪＨＷ（ｋ＞＞ｉ，ｌ）を計算し、上記記憶装置に記憶し、
上記第３の計算部は、上記ｉインクリメント部により変数ｉに順次１を加えられる度に、整数ｋと整数ｌの上位ｉ番目のｂビットブロック毎に、上記記憶装置から読み出した変数ｉと、上記入力部により入力された整数ｋと整数ｌとを用いて、整数ｋと整数ｌをｉビット右シフトした値（ｌ＞＞ｉ）との連結ハミング重みＪＨＷ０ｉ＝ＪＨＷ（ｋ，ｌ＞＞ｉ）を計算し、上記記憶装置に記憶し、
上記第４の計算部は、上記ｉインクリメント部により変数ｉに順次１を加えられる度に、整数ｋと整数ｌの上位ｉ番目のｂビットブロック毎に、上記記憶装置から読み出した変数ｉと上記第１の計算部により計算された連結ハミング重みＪＨＷ００と上記第２の計算部により計算された連結ハミング重みＪＨＷｉ０と、上記入力部により入力された楕円曲線上の点加算の計算量Ａと楕円曲線上の点２倍算の計算量Ｄとを用いて、計算量減少量Ｒｅｄｕｃｔｉｏｎｉ０＝（ＪＨＷ００−ＪＨＷｉ０）Ａ−ｉＤを計算し、上記記憶装置に記憶し、
上記第５の計算部は、上記ｉインクリメント部により変数ｉに順次１を加えられる度に、整数ｋと整数ｌの上位ｉ番目のｂビットブロック毎に、上記記憶装置から読み出した変数ｉと上記第１の計算部により計算された連結ハミング重みＪＨＷ００と、上記第３の計算部により計算された連結ハミング重みＪＨＷ０ｉと、楕円曲線上の点加算の計算量Ａと、楕円曲線上の点２倍算の計算量Ｄとを読み出し、計算量減少量Ｒｅｄｕｃｔｉｏｎ０ｉ＝（ＪＨＷ００−ＪＨＷ０ｉ）Ａ−ｉＤを計算し、上記記憶装置に記憶し、
上記第６の計算部は、上記ｉインクリメント部により変数ｉに順次１を加えられる度に、整数ｋと整数ｌの上位ｉ番目のｂビットブロック毎に、上記第４の計算部により計算された計算量減少量Ｒｅｄｕｃｔｉｏｎｉ０と上記上記第５の計算部により計算された計算量減少量Ｒｅｄｕｃｔｉｏｎ０ｉとの内、計算量減少量の最大値を計算し、上記記憶装置に記憶し、
上記第７の計算部は、上記ｉインクリメント部により変数ｉに順次１を加えられる度に、整数ｋと整数ｌの上位ｉ番目のｂビットブロック毎に、上記第６の計算部により計算された計算量減少量の最大値が正の値である場合には上記最大値に対応する計算量減少量に用いられた整数ｋと整数ｌとの組合わせである（ｋ＞＞ｉ，ｌ）と（ｋ，ｌ＞＞ｉ）とのいずれかを、上記第６の計算部により計算された計算量減少量の最大値が負の値である場合には上記入力部により入力された整数ｋと整数ｌとの組合わせである（ｋ，ｌ）を用いて、上記入力部により入力された楕円曲線上の２点ＰとＱの値のスカラー倍の和を計算し、ｂビットブロック毎に計算された楕円曲線上の２点ＰとＱの値のスカラー倍の和の合計を上記記憶装置に記憶することを特徴とする請求項４記載の楕円曲線演算装置。
【請求項７】
楕円曲線上の複数の点Ｐ１、Ｐ２、…、Ｐｎの値と、ｔビットの複数の正整数ｋ１、ｋ２、…、ｋｎと、シフト長の上限値ｓ（０以上の整数）と、楕円曲線上の点加算の計算量Ａと、楕円曲線上の点２倍算の計算量Ｄとを入力する入力部と、
上記入力部により入力されたｋ１、ｋ２、…、ｋｎの連結ハミング重みＪＨＷ０…０（ｎ個）＝ＪＨＷ（ｋ１，ｋ２，…，ｋｎ）を計算し、記憶装置に記憶する初期計算部と、
変数ｉを上記記憶装置に記憶するｉ記憶部と、
上記ｉ記憶部により記憶された変数ｉに初期値１を設定し、上記記憶装置に記憶するｉ初期値設定部と、
上記入力部により入力されたシフト長の上限値ｓと、上記記憶装置から読み出した上記ｉ初期値設定部により設定された変数ｉとを用いて、変数ｉがシフト長の上限値ｓに達するまで変数ｉに順次１を加えて、上記記憶装置に記憶するｉインクリメント部と、
上記ｉインクリメント部により上記記憶装置に変数ｉに順次１が加えられ記憶される度に、上記記憶装置から読み出した変数ｉと、上記入力部により入力された整数ｋ１、ｋ２、…、ｋｎを用いて、整数ｋ１、ｋ２、…、ｋｎ各値の内少なくとも１つを最大ｉビット右シフトした値と右シフトしない他の整数ｋ１、ｋ２、…、ｋｎとの連結ハミング重みＪＨＷｉを順に計算し、それぞれ上記記憶装置に記憶する連結ハミング重み計算部と、
上記ｉインクリメント部により上記記憶装置に変数ｉに順次１が加えられ記憶される度に、上記記憶装置から読み出した変数ｉと上記初期計算部により計算された連結ハミング重みＪＨＷ０…０（ｎ個）と、上記連結ハミング重み計算部により計算された連結ハミング重みＪＨＷｉと、楕円曲線上の点加算の計算量Ａと、楕円曲線上の点２倍算の計算量Ｄとを読み出し、さらに、上記整数ｋ１、ｋ２、…、ｋｎ各値の内、最大ｉビット右シフトした少なくとも１つの整数のシフト値の合計値Ｚを用いて、計算量減少量Ｒｅｄｕｃｔｉｏｎｉ＝（ＪＨＷ０…０（ｎ個）−ＪＨＷｉ）Ａ−ＺＤを順に計算し、上記記憶装置に記憶する計算量減少量計算部と、上記計算量減少量計算部により順に計算された計算量減少量Ｒｅｄｕｃｔｉｏｎｉの内、計算量減少量の最大値を計算し、上記記憶装置に記憶する最大値計算部と、
上記最大値計算部により計算された計算量減少量の最大値が正の値である場合には上記最大値に対応する計算量減少量に用いられた最大ｉビット右シフトした少なくとも１つの整数と右シフトしない他の整数ｋ１、ｋ２、…、ｋｎとを、上記最大値計算部により計算された計算量減少量の最大値が正の値でない場合には上記入力部により入力された整数ｋ１、ｋ２、…、ｋｎを用いて、上記入力部により入力された楕円曲線上の複数の点Ｐ１、Ｐ２、…、Ｐｎの値のスカラー倍の和ｋ１Ｐ１＋ｋ２Ｐ２＋，…，＋ｋｎＰｎを計算し、上記記憶装置に記憶するスカラー倍計算部と、
上記スカラー倍計算部により計算された楕円曲線上の複数の点の値のスカラー倍の和を出力する出力部と
を備えたことを特徴とする楕円曲線演算装置。
【請求項８】
ｔビットの２つの正整数ｋとｌと、シフト長の上限値ｓ（０以上の整数）と、楕円曲線上の点加算の計算量Ａと、楕円曲線上の点２倍算の計算量Ｄとを入力する入力部と、
上記入力部により入力されたｋとｌとの連結ハミング重みＪＨＷ００＝ＪＨＷ（ｋ，ｌ）を計算し、記憶装置に記憶する第１の計算部と、
変数ｉを上記記憶装置に記憶するｉ記憶部と、
上記ｉ記憶部により記憶された変数ｉに初期値１を設定し、上記記憶装置に記憶するｉ初期値設定部と、
上記入力部により入力されたシフト長の上限値ｓと、上記記憶装置から読み出した上記ｉ初期値設定部により設定された変数ｉとを用いて、変数ｉがシフト長の上限値ｓに達するまで変数ｉに順次１を加えて、上記記憶装置に記憶するｉインクリメント部と、
上記ｉインクリメント部により上記記憶装置に変数ｉに順次１が加えられ記憶される度に、上記記憶装置から読み出した変数ｉと、上記入力部により入力された整数ｋと整数ｌとを用いて、整数ｋをｉビット右シフトした値（ｋ＞＞ｉ）と整数ｌとの連結ハミング重みＪＨＷｉ０＝ＪＨＷ（ｋ＞＞ｉ，ｌ）を計算し、上記記憶装置に記憶する第２の計算部と、
上記ｉインクリメント部により上記記憶装置に変数ｉに順次１が加えられ記憶される度に、上記記憶装置から読み出した変数ｉと、上記入力部により入力された整数ｋと整数ｌとを用いて、整数ｋと整数ｌをｉビット右シフトした値（ｌ＞＞ｉ）との連結ハミング重みＪＨＷ０ｉ＝ＪＨＷ（ｋ，ｌ＞＞ｉ）を計算し、上記記憶装置に記憶する第３の計算部と、
上記ｉインクリメント部により上記記憶装置に変数ｉに順次１が加えられ記憶される度に、上記記憶装置から読み出した変数ｉと上記第１の計算部により計算された連結ハミング重みＪＨＷ００と上記第２の計算部により計算された連結ハミング重みＪＨＷｉ０と、上記入力部により入力された楕円曲線上の点加算の計算量Ａと楕円曲線上の点２倍算の計算量Ｄとを用いて、計算量減少量Ｒｅｄｕｃｔｉｏｎｉ０＝（ＪＨＷ００−ＪＨＷｉ０）Ａ−ｉＤを計算し、上記記憶装置に記憶する第４の計算部と、
上記ｉインクリメント部により上記記憶装置に変数ｉに順次１が加えられ記憶される度に、上記記憶装置から読み出した変数ｉと上記第１の計算部により計算された連結ハミング重みＪＨＷ００と、上記第３の計算部により計算された連結ハミング重みＪＨＷ０ｉと、楕円曲線上の点加算の計算量Ａと、楕円曲線上の点２倍算の計算量Ｄとを読み出し、計算量減少量Ｒｅｄｕｃｔｉｏｎ０ｉ＝（ＪＨＷ００−ＪＨＷ０ｉ）Ａ−ｉＤを計算し、上記記憶装置に記憶する第５の計算部と、
上記第４の計算部により計算された計算量減少量Ｒｅｄｕｃｔｉｏｎｉ０と上記上記第５の計算部により計算された計算量減少量Ｒｅｄｕｃｔｉｏｎ０ｉとの内、計算量減少量の最大値を計算し、上記記憶装置に記憶する第６の計算部と、
上記第６の計算部により計算された計算量減少量の最大値が正の値である場合には上記最大値に対応する計算量減少量に用いられた整数ｋと整数ｌとの組合わせである（ｋ＞＞ｉ，ｌ）と（ｋ，ｌ＞＞ｉ）とのいずれかを、上記第６の計算部により計算された計算量減少量の最大値が負の値である場合には上記入力部により入力された整数ｋと整数ｌとの組合わせである（ｋ，ｌ）を最適な整数ｋと整数ｌとの組合わせとして出力する出力部と
を備えたことを特徴とする変換装置。
【請求項９】
楕円曲線上の複数の点の値とそれぞれ所定の桁数を有する２進数の複数の正整数とを入力する入力工程と、
上記入力工程により入力された複数の正整数の同位置の桁に１つでも１が割り当てられた桁の数の合計値を初期合計値として記憶装置に記憶する記憶工程と、
上記複数の正整数の各正整数に対し、順に、上記複数の正整数の内１つを残して他の少なくとも１つの正整数の各桁に割り当てられた値を１桁ずつ所定の上限値までシフトするシフト工程と、
上記シフト工程によりシフトされた結果として上記複数の正整数の同位置の桁に１つでも１が割り当てられた桁の数の合計値と、上記記憶工程に記憶された初期合計値と、上記シフト工程によりシフトされた上記各正整数のシフト値とを用いて、上記シフト工程によりシフトされた場合の楕円曲線上の複数の点のスカラー倍点の和を計算するための計算回数の合計値と上記シフト工程によりシフトされない場合の楕円曲線上の複数の点のスカラー倍点の和を計算するための計算回数の合計値との差を上記各正整数の計算回数合計差分値としてそれぞれ計算し、上記各正整数の計算回数合計差分値を上記記憶装置に記憶させる第１の計算工程と、
上記第１の計算工程により計算され上記記憶装置に記憶された上記各正整数の計算回数合計差分値の内、最大となる計算回数合計差分値を選択し、選択された計算回数合計差分値を上記記憶装置に記憶させる選択工程と、
上記選択工程により選択され上記記憶装置に記憶された計算回数合計差分値が正の場合、上記選択工程により選択され上記記憶装置に記憶された計算回数合計差分値を計算させた複数の正整数の内上記シフト工程よりシフトされた少なくとも１つの正整数と、複数の正整数の内上記シフト工程によりシフトされていない他の正整数とを用いて、楕円曲線上の複数の点の値のスカラー倍の和を計算し、上記選択工程により選択され上記記憶装置に記憶された計算回数合計差分値が正でない場合、上記シフト工程によりシフトされていない上記入力工程により入力された複数の正整数を用いて、楕円曲線上の複数の点の値のスカラー倍の和を計算し、計算された楕円曲線上の複数の点の値のスカラー倍の和を上記記憶装置に記憶させる第２の計算工程と、
上記第２の計算工程により計算され上記記憶装置に記憶された楕円曲線上の複数の点の値のスカラー倍の和を出力する出力工程と
を備えたことを特徴とする楕円曲線演算方法。
【請求項１０】
楕円曲線上の２点ＰとＱの値と、ｔビットの２つの正整数ｋとｌと、シフト長の上限値ｓ（０以上の整数）と、楕円曲線上の点加算の計算量Ａと、楕円曲線上の点２倍算の計算量Ｄとを入力する入力工程と、
上記入力工程により入力されたｋとｌとの連結ハミング重みＪＨＷ００＝ＪＨＷ（ｋ，ｌ）を計算し、記憶装置に記憶する第１の計算工程と、
変数ｉを上記記憶装置に記憶するｉ記憶工程と、
上記ｉ記憶工程により記憶された変数ｉに初期値１を設定し、上記記憶装置に記憶するｉ初期値設定工程と、
上記入力工程により入力されたシフト長の上限値ｓと、上記記憶装置から読み出した上記ｉ初期値設定工程により設定された変数ｉとを用いて、変数ｉがシフト長の上限値ｓに達するまで変数ｉに順次１を加えて、上記記憶装置に記憶するｉインクリメント工程と、
上記ｉインクリメント工程により上記記憶装置に変数ｉに順次１が加えられ記憶される度に、上記記憶装置から読み出した変数ｉと、上記入力工程により入力された整数ｋと整数ｌとを用いて、整数ｋをｉビット右シフトした値（ｋ＞＞ｉ）と整数ｌとの連結ハミング重みＪＨＷｉ０＝ＪＨＷ（ｋ＞＞ｉ，ｌ）を計算し、上記記憶装置に記憶する第２の計算工程と、
上記ｉインクリメント工程により上記記憶装置に変数ｉに順次１が加えられ記憶される度に、上記記憶装置から読み出した変数ｉと、上記入力工程により入力された整数ｋと整数ｌとを用いて、整数ｋと整数ｌをｉビット右シフトした値（ｌ＞＞ｉ）との連結ハミング重みＪＨＷ０ｉ＝ＪＨＷ（ｋ，ｌ＞＞ｉ）を計算し、上記記憶装置に記憶する第３の計算工程と、
上記ｉインクリメント工程により上記記憶装置に変数ｉに順次１が加えられ記憶される度に、上記記憶装置から読み出した変数ｉと上記第１の計算工程により計算された連結ハミング重みＪＨＷ００と上記第２の計算工程により計算された連結ハミング重みＪＨＷｉ０と、上記入力工程により入力された楕円曲線上の点加算の計算量Ａと楕円曲線上の点２倍算の計算量Ｄとを用いて、計算量減少量Ｒｅｄｕｃｔｉｏｎｉ０＝（ＪＨＷ００−ＪＨＷｉ０）Ａ−ｉＤを計算し、上記記憶装置に記憶する第４の計算工程と、
上記ｉインクリメント工程により上記記憶装置に変数ｉに順次１が加えられ記憶される度に、上記記憶装置から読み出した変数ｉと上記第１の計算工程により計算された連結ハミング重みＪＨＷ００と、上記第３の計算工程により計算された連結ハミング重みＪＨＷ０ｉと、楕円曲線上の点加算の計算量Ａと、楕円曲線上の点２倍算の計算量Ｄとを読み出し、計算量減少量Ｒｅｄｕｃｔｉｏｎ０ｉ＝（ＪＨＷ００−ＪＨＷ０ｉ）Ａ−ｉＤを計算し、上記記憶装置に記憶する第５の計算工程と、
上記第４の計算工程により計算された計算量減少量Ｒｅｄｕｃｔｉｏｎｉ０と上記上記第５の計算工程により計算された計算量減少量Ｒｅｄｕｃｔｉｏｎ０ｉとの内、計算量減少量の最大値を計算し、上記記憶装置に記憶する第６の計算工程と、
上記第６の計算工程により計算された計算量減少量の最大値が正の値である場合には上記最大値に対応する計算量減少量に用いられた整数ｋと整数ｌとの組合わせである（ｋ＞＞ｉ，ｌ）と（ｋ，ｌ＞＞ｉ）とのいずれかを、上記第６の計算工程により計算された計算量減少量の最大値が負の値である場合には上記入力工程により入力された整数ｋと整数ｌとの組合わせである（ｋ，ｌ）を用いて、上記入力工程により入力された楕円曲線上の２点ＰとＱの値のスカラー倍の和を計算し、上記記憶装置に記憶する第７の計算工程と、
上記第７の計算工程により計算された楕円曲線上の２点ＰとＱの値のスカラー倍の和を出力する出力工程と
を備えたことを特徴とする楕円曲線演算方法。
【請求項１１】
楕円曲線上の複数の点の値とそれぞれ所定の桁数を有する２進数の複数の正整数とを入力する入力処理と、
上記入力処理により入力された複数の正整数の同位置の桁に１つでも１が割り当てられた桁の数の合計値を初期合計値として記憶装置に記憶する記憶処理と、
上記複数の正整数の各正整数に対し、順に、上記複数の正整数の内１つを残して他の少なくとも１つの正整数の各桁に割り当てられた値を１桁ずつ所定の上限値までシフトするシフト処理と、
上記シフト処理によりシフトされた結果として上記複数の正整数の同位置の桁に１つでも１が割り当てられた桁の数の合計値と、上記記憶処理に記憶された初期合計値と、上記シフト処理によりシフトされた上記各正整数のシフト値とを用いて、上記シフト処理によりシフトされた場合の楕円曲線上の複数の点のスカラー倍点の和を計算するための計算回数の合計値と上記シフト処理によりシフトされない場合の楕円曲線上の複数の点のスカラー倍点の和を計算するための計算回数の合計値との差を上記各正整数の計算回数合計差分値としてそれぞれ計算し、上記各正整数の計算回数合計差分値を上記記憶装置に記憶させる第１の計算処理と、
上記第１の計算処理により計算され上記記憶装置に記憶された上記各正整数の計算回数合計差分値の内、最大となる計算回数合計差分値を選択し、選択された計算回数合計差分値を上記記憶装置に記憶させる選択処理と、
上記選択処理により選択され上記記憶装置に記憶された計算回数合計差分値が正の場合、上記選択処理により選択され上記記憶装置に記憶された計算回数合計差分値を計算させた複数の正整数の内上記シフト処理よりシフトされた少なくとも１つの正整数と、複数の正整数の内上記シフト処理によりシフトされていない他の正整数とを用いて、楕円曲線上の複数の点の値のスカラー倍の和を計算し、上記選択処理により選択され上記記憶装置に記憶された計算回数合計差分値が正でない場合、上記シフト処理によりシフトされていない上記入力処理により入力された複数の正整数を用いて、楕円曲線上の複数の点の値のスカラー倍の和を計算し、計算された楕円曲線上の複数の点の値のスカラー倍の和を上記記憶装置に記憶させる第２の計算処理と、
上記第２の計算処理により計算され上記記憶装置に記憶された楕円曲線上の複数の点の値のスカラー倍の和を出力する出力処理と
をコンピュータに実行させるためのプログラム。
【請求項１２】
楕円曲線上の２点ＰとＱの値と、ｔビットの２つの正整数ｋとｌと、シフト長の上限値ｓ（０以上の整数）と、楕円曲線上の点加算の計算量Ａと、楕円曲線上の点２倍算の計算量Ｄとを入力する入力処理と、
上記入力処理により入力されたｋとｌとの連結ハミング重みＪＨＷ００＝ＪＨＷ（ｋ，ｌ）を計算し、記憶装置に記憶する第１の計算処理と、
変数ｉを上記記憶装置に記憶するｉ記憶処理と、
上記ｉ記憶処理により記憶された変数ｉに初期値１を設定し、上記記憶装置に記憶するｉ初期値設定処理と、
上記入力処理により入力されたシフト長の上限値ｓと、上記記憶装置から読み出した上記ｉ初期値設定処理により設定された変数ｉとを用いて、変数ｉがシフト長の上限値ｓに達するまで変数ｉに順次１を加えて、上記記憶装置に記憶するｉインクリメント処理と、
上記ｉインクリメント処理により上記記憶装置に変数ｉに順次１が加えられ記憶される度に、上記記憶装置から読み出した変数ｉと、上記入力処理により入力された整数ｋと整数ｌとを用いて、整数ｋをｉビット右シフトした値（ｋ＞＞ｉ）と整数ｌとの連結ハミング重みＪＨＷｉ０＝ＪＨＷ（ｋ＞＞ｉ，ｌ）を計算し、上記記憶装置に記憶する第２の計算処理と、
上記ｉインクリメント処理により上記記憶装置に変数ｉに順次１が加えられ記憶される度に、上記記憶装置から読み出した変数ｉと、上記入力処理により入力された整数ｋと整数ｌとを用いて、整数ｋと整数ｌをｉビット右シフトした値（ｌ＞＞ｉ）との連結ハミング重みＪＨＷ０ｉ＝ＪＨＷ（ｋ，ｌ＞＞ｉ）を計算し、上記記憶装置に記憶する第３の計算処理と、
上記ｉインクリメント処理により上記記憶装置に変数ｉに順次１が加えられ記憶される度に、上記記憶装置から読み出した変数ｉと上記第１の計算処理により計算された連結ハミング重みＪＨＷ００と上記第２の計算処理により計算された連結ハミング重みＪＨＷｉ０と、上記入力処理により入力された楕円曲線上の点加算の計算量Ａと楕円曲線上の点２倍算の計算量Ｄとを用いて、計算量減少量Ｒｅｄｕｃｔｉｏｎｉ０＝（ＪＨＷ００−ＪＨＷｉ０）Ａ−ｉＤを計算し、上記記憶装置に記憶する第４の計算処理と、
上記ｉインクリメント処理により上記記憶装置に変数ｉに順次１が加えられ記憶される度に、上記記憶装置から読み出した変数ｉと上記第１の計算処理により計算された連結ハミング重みＪＨＷ００と、上記第３の計算処理により計算された連結ハミング重みＪＨＷ０ｉと、楕円曲線上の点加算の計算量Ａと、楕円曲線上の点２倍算の計算量Ｄとを読み出し、計算量減少量Ｒｅｄｕｃｔｉｏｎ０ｉ＝（ＪＨＷ００−ＪＨＷ０ｉ）Ａ−ｉＤを計算し、上記記憶装置に記憶する第５の計算処理と、
上記第４の計算処理により計算された計算量減少量Ｒｅｄｕｃｔｉｏｎｉ０と上記上記第５の計算処理により計算された計算量減少量Ｒｅｄｕｃｔｉｏｎ０ｉとの内、計算量減少量の最大値を計算し、上記記憶装置に記憶する第６の計算処理と、
上記第６の計算処理により計算された計算量減少量の最大値が正の値である場合には上記最大値に対応する計算量減少量に用いられた整数ｋと整数ｌとの組合わせである（ｋ＞＞ｉ，ｌ）と（ｋ，ｌ＞＞ｉ）とのいずれかを、上記第６の計算処理により計算された計算量減少量の最大値が負の値である場合には上記入力処理により入力された整数ｋと整数ｌとの組合わせである（ｋ，ｌ）を用いて、上記入力処理により入力された楕円曲線上の２点ＰとＱの値のスカラー倍の和を計算し、上記記憶装置に記憶する第７の計算処理と、
上記第７の計算処理により計算された楕円曲線上の２点ＰとＱの値のスカラー倍の和を出力する出力処理と
をコンピュータに実行させるためのプログラム。
【請求項１３】
楕円曲線上の複数の点の値とそれぞれ所定の桁数を有する２進数の複数の正整数とを入力する入力処理と、
上記入力処理により入力された複数の正整数の同位置の桁に１つでも１が割り当てられた桁の数の合計値を初期合計値として記憶装置に記憶する記憶処理と、
上記複数の正整数の各正整数に対し、順に、上記複数の正整数の内１つを残して他の少なくとも１つの正整数の各桁に割り当てられた値を１桁ずつ所定の上限値までシフトするシフト処理と、
上記シフト処理によりシフトされた結果として上記複数の正整数の同位置の桁に１つでも１が割り当てられた桁の数の合計値と、上記記憶処理に記憶された初期合計値と、上記シフト処理によりシフトされた上記各正整数のシフト値とを用いて、上記シフト処理によりシフトされた場合の楕円曲線上の複数の点のスカラー倍点の和を計算するための計算回数の合計値と上記シフト処理によりシフトされない場合の楕円曲線上の複数の点のスカラー倍点の和を計算するための計算回数の合計値との差を上記各正整数の計算回数合計差分値としてそれぞれ計算し、上記各正整数の計算回数合計差分値を上記記憶装置に記憶させる第１の計算処理と、
上記第１の計算処理により計算され上記記憶装置に記憶された上記各正整数の計算回数合計差分値の内、最大となる計算回数合計差分値を選択し、選択された計算回数合計差分値を上記記憶装置に記憶させる選択処理と、
上記選択処理により選択され上記記憶装置に記憶された計算回数合計差分値が正の場合、上記選択処理により選択され上記記憶装置に記憶された計算回数合計差分値を計算させた複数の正整数の内上記シフト処理よりシフトされた少なくとも１つの正整数と、複数の正整数の内上記シフト処理によりシフトされていない他の正整数とを用いて、楕円曲線上の複数の点の値のスカラー倍の和を計算し、上記選択処理により選択され上記記憶装置に記憶された計算回数合計差分値が正でない場合、上記シフト処理によりシフトされていない上記入力処理により入力された複数の正整数を用いて、楕円曲線上の複数の点の値のスカラー倍の和を計算し、計算された楕円曲線上の複数の点の値のスカラー倍の和を上記記憶装置に記憶させる第２の計算処理と、
上記第２の計算処理により計算され上記記憶装置に記憶された楕円曲線上の複数の点の値のスカラー倍の和を出力する出力処理と
をコンピュータに実行させるためのプログラムを記録したコンピュータ読み取り可能な記録媒体。
【請求項１４】
楕円曲線上の２点ＰとＱの値と、ｔビットの２つの正整数ｋとｌと、シフト長の上限値ｓ（０以上の整数）と、楕円曲線上の点加算の計算量Ａと、楕円曲線上の点２倍算の計算量Ｄとを入力する入力処理と、
上記入力処理により入力されたｋとｌとの連結ハミング重みＪＨＷ００＝ＪＨＷ（ｋ，ｌ）を計算し、記憶装置に記憶する第１の計算処理と、
変数ｉを上記記憶装置に記憶するｉ記憶処理と、
上記ｉ記憶処理により記憶された変数ｉに初期値１を設定し、上記記憶装置に記憶するｉ初期値設定処理と、
上記入力処理により入力されたシフト長の上限値ｓと、上記記憶装置から読み出した上記ｉ初期値設定処理により設定された変数ｉとを用いて、変数ｉがシフト長の上限値ｓに達するまで変数ｉに順次１を加えて、上記記憶装置に記憶するｉインクリメント処理と、
上記ｉインクリメント処理により上記記憶装置に変数ｉに順次１が加えられ記憶される度に、上記記憶装置から読み出した変数ｉと、上記入力処理により入力された整数ｋと整数ｌとを用いて、整数ｋをｉビット右シフトした値（ｋ＞＞ｉ）と整数ｌとの連結ハミング重みＪＨＷｉ０＝ＪＨＷ（ｋ＞＞ｉ，ｌ）を計算し、上記記憶装置に記憶する第２の計算処理と、
上記ｉインクリメント処理により上記記憶装置に変数ｉに順次１が加えられ記憶される度に、上記記憶装置から読み出した変数ｉと、上記入力処理により入力された整数ｋと整数ｌとを用いて、整数ｋと整数ｌをｉビット右シフトした値（ｌ＞＞ｉ）との連結ハミング重みＪＨＷ０ｉ＝ＪＨＷ（ｋ，ｌ＞＞ｉ）を計算し、上記記憶装置に記憶する第３の計算処理と、
上記ｉインクリメント処理により上記記憶装置に変数ｉに順次１が加えられ記憶される度に、上記記憶装置から読み出した変数ｉと上記第１の計算処理により計算された連結ハミング重みＪＨＷ００と上記第２の計算処理により計算された連結ハミング重みＪＨＷｉ０と、上記入力処理により入力された楕円曲線上の点加算の計算量Ａと楕円曲線上の点２倍算の計算量Ｄとを用いて、計算量減少量Ｒｅｄｕｃｔｉｏｎｉ０＝（ＪＨＷ００−ＪＨＷｉ０）Ａ−ｉＤを計算し、上記記憶装置に記憶する第４の計算処理と、
上記ｉインクリメント処理により上記記憶装置に変数ｉに順次１が加えられ記憶される度に、上記記憶装置から読み出した変数ｉと上記第１の計算処理により計算された連結ハミング重みＪＨＷ００と、上記第３の計算処理により計算された連結ハミング重みＪＨＷ０ｉと、楕円曲線上の点加算の計算量Ａと、楕円曲線上の点２倍算の計算量Ｄとを読み出し、計算量減少量Ｒｅｄｕｃｔｉｏｎ０ｉ＝（ＪＨＷ００−ＪＨＷ０ｉ）Ａ−ｉＤを計算し、上記記憶装置に記憶する第５の計算処理と、
上記第４の計算処理により計算された計算量減少量Ｒｅｄｕｃｔｉｏｎｉ０と上記上記第５の計算処理により計算された計算量減少量Ｒｅｄｕｃｔｉｏｎ０ｉとの内、計算量減少量の最大値を計算し、上記記憶装置に記憶する第６の計算処理と、
上記第６の計算処理により計算された計算量減少量の最大値が正の値である場合には上記最大値に対応する計算量減少量に用いられた整数ｋと整数ｌとの組合わせである（ｋ＞＞ｉ，ｌ）と（ｋ，ｌ＞＞ｉ）とのいずれかを、上記第６の計算処理により計算された計算量減少量の最大値が負の値である場合には上記入力処理により入力された整数ｋと整数ｌとの組合わせである（ｋ，ｌ）を用いて、上記入力処理により入力された楕円曲線上の２点ＰとＱの値のスカラー倍の和を計算し、上記記憶装置に記憶する第７の計算処理と、
上記第７の計算処理により計算された楕円曲線上の２点ＰとＱの値のスカラー倍の和を出力する出力処理と
をコンピュータに実行させるためのプログラムを記録したコンピュータ読み取り可能な記録媒体。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、楕円曲線演算装置又は楕円曲線上の点の演算方法、又はそれを用いるスカラーを変換する変換装置又はそれらを用いた暗号化方法に関する。
【０００２】
【従来の技術】
従来の楕円曲線上の点の同時スカラー倍演算方法について説明する。従来演算方法は、例えば、非特許文献１に記載されている。
【０００３】
図９は、楕円曲線上の点の同時スカラー倍演算、ｋＰ＋ｌＱを演算する従来の方法を示すフローチャートである。
図９において、Ｓ７０１はＧ←Ｐ＋Ｑを計算するステップ、Ｓ７０２はＡを無限遠点に初期化するステップ、Ｓ７０３は楕円曲線上の点の同時スカラー倍算を計算するメインループである。
【０００４】
次に動作を説明する。まず楕円曲線上の２つの点ＰとＱ、ｔビットの２つの正整数ｋとｌが入力される。ｋとｌはそれぞれ、
【０００５】
【数１】
2004117627.tif 000003
【０００６】
であるとする。すなわち、ｋを２進数表示すると（ｋｔ−１，…，ｋ１，ｋ０）となり、ｌを２進数表示すると（ｌｔ−１，…，ｌ１，ｌ０）となる。
次に、Ｓ７０１において、Ｐ＋Ｑを計算し、結果をＧとして保存する。この点Ｇは、楕円同時スカラー倍算のメインループＳ７０３において適宜参照される。Ｓ７０１の計算は、事前計算とも呼ばれる。
次に、Ｓ７０２において、点Ａを無限遠点Оに初期化する。
次に、Ｓ７０３において、楕円同時スカラー倍演算のメインループを実行する。Ｓ７０３は、入力された正整数ｋとｌのビット数回、すなわちｔ回ループする。ループは、ｋとｌのビットを上位側から参照しながら実行される。各ループ内では、まず点の２倍算が演算される。点Ａを２倍した点を再びＡとおく。２倍算はループの初回以外は必ず実行される。次に点の加算が演算される。加算はビットｋｉとｌｉに依存して実行される。（ｋｉ，ｌｉ）＝（１，０）の時は点Ａに点Ｐを加算し、結果をＡとおく。（ｋｉ，ｌｉ）＝（０，１）の時は点Ａに点Ｑを加算し、結果をＡとおく。（ｋｉ，ｌｉ）＝（１，１）の時は点Ａに点Ｇを加算し、結果をＡとおく。（ｋｉ，ｌｉ）＝（０，０）の時は加算は演算されない。ループをｔ回実行した後、Ａを出力する。
【０００７】
例えば、簡単な例として、整数３と整数１３と所定の点ＰとＱによるスカラー倍算として、３Ｐ＋１３Ｑを考える。
整数３は、２進数で表示すると２ビット値１１となる。整数１３は、２進数で表示すると４ビット値１１０１となる。整数１３と桁数（ビット数）を合わせると整数３は、００１１となる。
まず、所定の点の和Ｇ＝Ｐ＋Ｑを計算する。
次に、第１の加算値Ａ０は、整数１３について左の最初のビット値が１であるから、Ａ０＝左の最初のビット値１・Ｑ＝Ｑである。
次に、第１の２倍算値Ａ１は、Ａ１＝２Ａ０＝２Ｑである。
次に、第２の加算値Ａ２は、整数１３について２番目のビット値が１であるから、Ａ２＝２番目のビット値１・Ｑ＋Ａ１＝３Ｑである。
次に、第２の２倍算値Ａ３は、Ａ３＝２Ａ２＝６Ｑである。
次に、第３の加算値Ａ４は、整数３について３番目のビット値が１であるから、Ａ４＝３番目のビット値１・Ｐ＋Ａ３＝Ｐ＋６Ｑである。
次に、第３の２倍算値Ａ５は、Ａ５＝２Ａ４＝２Ｐ＋１２Ｑである。
次に、第４の加算値Ａ６は、整数３と整数１３とについて４番目のビット値が１であるから、Ａ６＝４番目のビット値１・Ｇ＋Ａ５＝３Ｐ＋１３Ｑである。
以上のように、３Ｐ＋１３Ｑを計算するには、１回の所定の点の和Ｇの加算と４回の加算と３回の２倍算との合計８回の演算が必要となる。
【０００８】
この従来の楕円同時スカラー倍演算方法では、点の２倍算はｋとｌのビット長−１回実行される。点の加算は、Ｓ７０１で１回実行され、その他にＳ７０３のループ内では正整数ｋとｌのビットパターンに依存して決まる。ｋとｌを２進展開した２行ｔ列の行列における非ゼロ列（ｋｉとｌｉのどちらかが１の列）の数が、必要な加算回数となる。たとえば、ｋとｌが、
【０００９】
【数２】
2004117627.tif 000004
【００１０】
と２進数表示される時、非ゼロ列の数は８列であるから、加算は８回必要となる。また、非ゼロ列の数は連結ハミング重みと呼ばれ、ＪＨＷと書く。ｋとｌの連結ハミング重みはＪＨＷ（ｋ，ｌ）と書く。上記ｋとｌの例では、ＪＨＷ（ｋ，ｌ）＝８となる。
一般に、ランダムに生成された正整数のビットは半分が１であるから、ｋとｌがランダムに生成されたｔビットの正整数である時、列が非ゼロ列である確率は
１−（１／２）２＝３／４
となる。したがって、従来の楕円同時スカラー倍演算の演算量の平均は、楕円曲線上の点加算の演算量をＡ、点２倍算の演算量をＤとすると、
【００１１】
【数３】
2004117627.tif 000005
【００１２】
となる。点加算の演算量Ａについては、Ｓ７０３における３／４ｔ回の点加算とＳ７０１における初回加算の合計、点２倍算の演算量については、Ｓ７０３におけるｔ−１回となる。
【００１３】
【非特許文献１】
Ａ．Ｊ．Ｍｅｎｅｚｅｓ，Ｐ．Ｃ．Ｏｏｒｓｃｈｏｔ，Ｓ．Ａ．Ｖａｎｓｔｏｎｅ著、「Ｈａｎｄｂｏｏｋ　ｏｆ　Ａｐｐｌｉｅｄ　Ｃｒｙｐｔｏｇｒａｐｈｙ」、ＣＲＣ　Ｐｒｅｓｓ、ｐｐ　６１７−６１８
【非特許文献２】
「ＩＥＥＥ　Ｓｔａｎｄａｒｄ　Ｓｐｅｃｉｆｉｃａｔｉｏｎ　ｆｏｒ　Ｐｕｂｌｉｃ−Ｋｅｙ　Ｃｒｙｐｔｏｇｒａｐｈｙ」、ＩＥＥＥ　Ｓｔｄ　１３６３−２０００
【００１４】
【発明が解決しようとする課題】
従来の楕円同時スカラー倍演算方法は、以上のように構成されており、正整数ｋとｌを２進展開した２行ｔ列の行列における非ゼロ列（ｋｉとｌｉのどちらかが１の列）の数の分、点の加算を演算しなければならなかった。したがって、演算量が多いという課題があった。
【００１５】
本発明の目的は、正整数ｋとｌを２進展開した２行ｔ列の行列における非ゼロ列（ｋｉとｌｉのどちらかが１の列）の数よりも少ない点加算回数で、楕円同時スカラー倍演算を実行し、高速な演算方法を得ることを目的とする。
【００１６】
【課題を解決するための手段】
この発明に係る楕円曲線演算装置は、楕円曲線上の複数の点の値とそれぞれ所定の桁数を有する２進数の複数の正整数とを入力する入力部と、
上記入力部により入力された複数の正整数の同位置の桁に１つでも１が割り当てられた桁の数の合計値を初期合計値として記憶する記憶部と、
上記複数の正整数の各正整数に対し、順に、上記複数の正整数の内１つを残して他の少なくとも１つの正整数の各桁に割り当てられた値を１桁ずつ所定の上限値までシフトするシフト部と、
上記シフト部によりシフトされた結果として上記複数の正整数の同位置の桁に１つでも１が割り当てられた桁の数の合計値と、上記記憶部に記憶された初期合計値と、上記シフト部によりシフトされた上記各正整数のシフト値とを用いて、上記シフト部によりシフトされた場合の楕円曲線上の複数の点のスカラー倍点の和を計算するための計算回数の合計値と上記シフト部によりシフトされない場合の楕円曲線上の複数の点のスカラー倍点の和を計算するための計算回数の合計値との差を上記各正整数の計算回数合計差分値としてそれぞれ計算し、上記各正整数の計算回数合計差分値を上記記憶部に記憶させる第１の計算部と、
上記第１の計算部により計算され上記記憶部に記憶された上記各正整数の計算回数合計差分値の内、最大となる計算回数合計差分値を選択し、選択された計算回数合計差分値を上記記憶部に記憶させる選択部と、
上記選択部により選択され上記記憶部に記憶された計算回数合計差分値が正の場合、上記選択部により選択され上記記憶部に記憶された計算回数合計差分値を計算させた複数の正整数の内上記シフト部によりシフトされた少なくとも１つの正整数と、複数の正整数の内上記シフト部によりシフトされていない他の正整数とを用いて、楕円曲線上の複数の点の値のスカラー倍の和を計算し、上記選択部により選択され上記記憶部に記憶された計算回数合計差分値が正でない場合、上記シフト部によりシフトされていない上記入力部により入力された複数の正整数を用いて、楕円曲線上の複数の点の値のスカラー倍の和を計算し、計算された楕円曲線上の複数の点の値のスカラー倍の和を上記記憶部に記憶させる第２の計算部と、
上記第２の計算部により計算され上記記憶部に記憶された楕円曲線上の複数の点の値のスカラー倍の和を出力する出力部と
を備えたことを特徴とする。
【００１７】
【発明の実施の形態】
実施の形態１．
図１は、実施の形態１におけるコンピュータ装置の外観を示す図である。
図１において、パーソナルコンピュータ（ＰＣ）１００（変換装置、楕円曲線演算装置の一例である）は、システムユニット３３、ＣＲＴ（Ｃａｔｈｏｄｅ　Ｒａｙ　Ｔｕｂｅ）表示装置４１、キーボード（Ｋ／Ｂ）４２、マウス４３、コンパクトディスク装置（ＣＤＤ）８６、プリンタ装置８７、スキャナ装置８８を備えている。ＣＲＴ表示装置４１、Ｋ／Ｂ４２、マウス４３、ＣＤＤ８６、プリンタ装置８７、スキャナ装置８８は、システムユニット３３にケーブルで接続されている。
【００１８】
図２は、実施の形態１におけるコンピュータ装置のハードウェア構成図である。
図２において、プログラムを実行するＣＰＵ（Ｃｅｎｔｒａｌ　Ｐｒｏｃｅｓｓｉｎｇ　Ｕｎｉｔ）３７は、バス３８を介してＲＯＭ（Ｒｅａｄ　Ｏｎｌｙ　Ｍｅｍｏｒｙ）３９（記憶装置の一例である）、ＲＡＭ（Ｒａｎｄｏｍ　Ａｃｃｅｓｓ　Ｍｅｍｏｒｙ）４０（記憶装置の一例である）、ＣＲＴ表示装置４１、Ｋ／Ｂ４２、マウス４３、通信ボード４４、ＦＤＤ（Ｆｌｅｘｉｂｌｅ　Ｄｉｓｋ　Ｄｒｉｖｅ）４５、磁気ディスク装置４６（記憶装置の一例である）、ＣＤＤ８６、プリンタ装置８７、スキャナ装置８８と接続されている。通信ボード４４は、インターネット３０に接続されている。
ここで、通信ボード４４は、インターネット３０に限らず、ＬＡＮ（ローカルエリアネットワーク）、或いはＩＳＤＮ等のＷＡＮ（ワイドエリアネットワーク）に接続されていても構わない。
磁気ディスク装置４６には、オペレーティングシステム（ＯＳ）４７、ウィンドウシステム４８、プログラム群４９、ファイル群５０が記憶されている。プログラム群４９は、ＣＰＵ３７、ＯＳ４７、ウィンドウシステム４８により実行される。
【００１９】
図３は、実施の形態１における変換装置の構成を示すブロック図である。
図３において、変換装置４００は、入力部４０１、記憶部４０２（ｉ記憶部、記憶装置の一例である。）、計算部４０３（第１の計算部、初期計算部の一例である。）、計算部４０４、最大値計算部４０５（選択部、第６の計算部の一例である。）、出力部４０６を備えている。変換装置４００は、制御部４０７に接続されている。ＰＣ１００は、変換装置４００、制御部４０７を備えている。
計算部４０４は、シフト部４１０、計算部４２０（第１の計算部の一例である。）を有している。
シフト部４１０は、ｉ初期値設定部４１１、ｉインクリメント部４１２を有している。
計算部４２０は、細分化された、計算部４２１、計算部４２２、計算部４２３、計算部４２４を有している。計算部４２１と計算部４２２とにより連結ハミング重み計算部の一例を構成する。計算部４２３と計算部４２４とにより計算量減少量計算部の一例を構成する。
【００２０】
変換装置４００は、最適なスカラーの組合わせを計算し、変換する。
入力部４０１は、それぞれ所定の桁数を有する２進数の複数の正整数とを入力する。言いかえれば、入力部４０１は、ｔビットの２つの正整数ｋとｌと、シフト長の上限値ｓ（０以上の整数）と、楕円曲線上の点加算の計算量Ａと、楕円曲線上の点２倍算の計算量Ｄとを入力する。
計算部４０３は、上記入力部４０１により入力されたｋとｌとの連結ハミング重みＪＨＷ００＝ＪＨＷ（ｋ，ｌ）を計算し、記憶装置の一例である記憶部４０２に記憶する。
記憶部４０２は、上記入力部４０１により入力された複数の正整数の同位置の桁に１つでも１が割り当てられた桁の数の合計値を初期合計値として記憶する。記憶部４０２は、変数ｉをＲＡＭ４０等の記憶装置に記憶する。
シフト部４１０は、上記複数の正整数の各正整数に対し、順に、上記複数の正整数の内１つを残して他の少なくとも１つの正整数の各桁に割り当てられた値を１桁ずつ所定の上限値までシフトする。ｉ初期値設定部４１１は、上記ｉ記憶部により記憶された変数ｉに初期値１を設定し、上記記憶部４０２に記憶する。ｉインクリメント部４１２は、上記入力部４０１により入力されたシフト長の上限値ｓと、上記記憶部４０２から読み出した上記ｉ初期値設定部４１１により設定された変数ｉとを用いて、変数ｉがシフト長の上限値ｓに達するまで変数ｉに順次１を加えて、上記記憶部４０２に記憶する。
計算部４２０は、上記シフト部４１０によりシフトされた結果として上記複数の正整数の同位置の桁に１つでも１が割り当てられた桁の数の合計値と、上記記憶部４０２に記憶された初期合計値と、上記シフト部４１０によりシフトされた上記各正整数のシフト値とを用いて、上記シフト部４１０によりシフトされた場合の楕円曲線上の複数の点のスカラー倍点の和を計算するための計算回数の合計値と上記シフト部４１０によりシフトされない場合の楕円曲線上の複数の点のスカラー倍点の和を計算するための計算回数の合計値との差を上記各正整数の計算回数合計差分値としてそれぞれ計算し、上記各正整数の計算回数合計差分値を上記記憶部４０２に記憶させる。計算部４２１は、上記ｉインクリメント部４１２により上記記憶部４０２に変数ｉに順次１が加えられ記憶される度に、上記記憶部４０２から読み出した変数ｉと、上記入力部４０１により入力された整数ｋと整数ｌとを用いて、整数ｋをｉビット右シフトした値（ｋ＞＞ｉ）と整数ｌとの連結ハミング重みＪＨＷｉ０＝ＪＨＷ（ｋ＞＞ｉ，ｌ）を計算し、上記記憶部４０２に記憶する。計算部４２２は、上記ｉインクリメント部４１２により上記記憶部４０２に変数ｉに順次１が加えられ記憶される度に、上記記憶部４０２から読み出した変数ｉと、上記入力部４０１により入力された整数ｋと整数ｌとを用いて、整数ｋと整数ｌをｉビット右シフトした値（ｌ＞＞ｉ）との連結ハミング重みＪＨＷ０ｉ＝ＪＨＷ（ｋ，ｌ＞＞ｉ）を計算し、上記記憶部４０２に記憶する。計算部４２３は、上記ｉインクリメント部４１２により上記記憶部４０２に変数ｉに順次１が加えられ記憶される度に、上記記憶部４０２から読み出した変数ｉと上記計算部４０３により計算された連結ハミング重みＪＨＷ００と上記計算部４２１により計算された連結ハミング重みＪＨＷｉ０と、上記入力部４０１により入力された楕円曲線上の点加算の計算量Ａと楕円曲線上の点２倍算の計算量Ｄとを用いて、計算量減少量Ｒｅｄｕｃｔｉｏｎｉ０＝（ＪＨＷ００−ＪＨＷｉ０）Ａ−ｉＤを計算し、上記記憶部４０２に記憶する。計算部４２４は、上記ｉインクリメント部４１２により上記記憶部４０２に変数ｉに順次１が加えられ記憶される度に、上記記憶部４０２から読み出した変数ｉと上記計算部４０３により計算された連結ハミング重みＪＨＷ００と、上記計算部４２２により計算された連結ハミング重みＪＨＷ０ｉと、楕円曲線上の点加算の計算量Ａと、楕円曲線上の点２倍算の計算量Ｄとを読み出し、計算量減少量Ｒｅｄｕｃｔｉｏｎ０ｉ＝（ＪＨＷ００−ＪＨＷ０ｉ）Ａ−ｉＤを計算し、上記記憶部４０２に記憶する。
最大値計算部４０５は、上記計算部４２０により計算され上記記憶部４０２に記憶された上記各正整数の計算回数合計差分値の内、最大となる計算回数合計差分値を選択し、選択された計算回数合計差分値を上記記憶部４０２に記憶させる。言いかえれば、最大値計算部４０５は、上記計算部４２３により計算された計算量減少量Ｒｅｄｕｃｔｉｏｎｉ０と上記上記計算部４２４により計算された計算量減少量Ｒｅｄｕｃｔｉｏｎ０ｉとの内、計算量減少量の最大値を計算し、上記記憶部４０２に記憶する。
出力部４０６は、最適なスカラーの組合わせとして、上記最大値計算部４０５により選択され上記記憶部４０２に記憶された計算回数合計差分値が正の場合、上記計算回数合計差分値を計算させた複数の正整数の内上記シフト部４１０によりシフトされた少なくとも１つの正整数と、複数の正整数の内上記シフト部４１０によりシフトされていない他の正整数とを出力する。計算回数合計差分値が正でない場合、上記シフト部４１０によりシフトされていない上記入力部４０１により入力された複数の正整数を出力する。言いかえれば、出力部４０６は、上記最大値計算部４０５により計算された計算量減少量の最大値が正の値である場合には上記最大値に対応する計算量減少量に用いられた整数ｋと整数ｌとの組合わせである（ｋ＞＞ｉ，ｌ）と（ｋ，ｌ＞＞ｉ）とのいずれかを、上記最大値計算部４０５により計算された計算量減少量の最大値が負の値、或いは０値である場合には上記入力部４０１により入力された整数ｋと整数ｌとの組合わせである（ｋ，ｌ）を出力する。
【００２１】
図４は、実施の形態１における整数の変換方法を示したフローチャートである。
図４におけるＳ（ステップ）１００において、入力部４０１は、まずｔビットの２つの正整数ｋとｌと、シフト長の上限ｓと、楕円曲線上の点加算の計算量Ａと、楕円曲線上の点２倍算の計算量Ｄとを入力する。
Ｓ１０１において、計算部４０３は、ｋとｌの連結ハミング重みＪＨＷ００＝ＪＨＷ（ｋ，ｌ）を計算する。
Ｓ１０２において、計算部４０４は、１≦ｉ≦ｓに対してＪＨＷｉ０＝ＪＨＷ（ｋ＞＞ｉ，ｌ）とＪＨＷ０ｉ＝ＪＨＷ（ｋ，ｌ＞＞ｉ）と、（ＪＨＷ００−ＪＨＷｉ０）Ａ−ｉＤと、（ＪＨＷ００−ＪＨＷ０ｉ）Ａ−ｉＤとを計算する。
Ｓ１０３において、最大値計算部４０５は、ＪＨＷ００と（ＪＨＷ００−ＪＨＷｉ０）Ａ−ｉＤと（ＪＨＷ００−ＪＨＷ０ｉ）Ａ−ｉＤとの中で最大の値を計算する。
Ｓ１０４において、出力部４０６は、最大となる（ｋ，ｌ）または（ｋ＞＞ｓ’，ｌ）または（ｋ，ｌ＞＞ｓ’）、ここで０＜ｓ’≦ｓ、を出力する。ここで、記号ｋ＞＞ｉは、ｋをｉビット右シフトし、ｋの上位ｉビットをビット０でパディングする操作である。
【００２２】
次に図４における各ステップの詳細な動作を説明する。
まず、Ｓ１００において、入力部４０１は、ｔビットの２つの正整数ｋとｌと、シフト長の上限ｓと、楕円曲線上の点加算の計算量Ａと、楕円曲線上の点２倍算の計算量Ｄとを入力する。
次に、Ｓ１０１において、計算部４０３は、ｋとｌとの連結ハミング重みＪＨＷ００＝ＪＨＷ（ｋ，ｌ）を計算する。次に計算量減少量Ｒｅｄｕｃｔｉｏｎ００を０に初期化する。
ｋとｌをそのまま使い、楕円同時スカラー倍演算ｋＰ＋ｌＱを計算するのが従来の方法であり、本実施の形態１では、ｋとｌをそのまま使うのではなく、ｋまたはｌをあるビット数右シフトした値を使って、楕円同時スカラー倍演算を行う。計算量減少量Ｒｅｄｕｃｔｉｏｎは、ｋまたはｌを右シフトした時に、楕円同時スカラー倍演算の計算量がどの程度減少するかを評価するためのもので、ｋもｌもシフトしないそのままの値の場合を０とし、これを基準に比較を行う。
次に、Ｓ１０２において、計算部４２１は、ｋをｉビット右シフトした値とｌとの連結ハミング重みＪＨＷｉ０＝ＪＨＷ（ｋ＞＞ｉ，ｌ）を計算する。また、計算部４２２は、ｌをｉビット右シフトした値とｋとの連結ハミング重みＪＨＷ０ｉ＝ＪＨＷ（ｋ，ｌ＞＞ｉ）も計算する。次に、計算部４２３と計算部４２４とは、楕円同時スカラー倍計算量減少量Ｒｅｄｕｃｔｉｏｎを計算する。整数を右シフトした際に、楕円同時スカラー倍演算の計算量がどの程度減少するかは、次のように評価できる。
前述のように、スカラー倍演算は、点の加算と２倍算とで構成される。整数のビット長がｔの場合、点の２倍算は（ｔ−１）回必要である。また、前述のように、２つの整数ｋとｌを２進展開した２行ｔ列の行列における非ゼロ列（ｋｉとｌｉのどちらかが１の列）の数が、必要な点加算回数となる。例えば、ｋ＝１３２１＝（１０１００１０１００１）２、ｌ＝１１７３＝（１００１００１０１０１）２の時、２行×１１列の行列表示すると、
【００２３】
【数４】
2004117627.tif 000006
【００２４】
となるから、必要な点加算回数は８回となる。また、ｋとｌは１１ビットであるから、事前計算において点加算が１回必要なことを考慮すると、楕円同時スカラー倍演算の計算量は、
９Ａ＋１０Ｄ
となる。
次に、ｋを１ビット右シフトした値とｌとの連結ハミング重みを考える。ｋを１ビット右シフトすると、行列表示は、
【００２５】
【数５】
2004117627.tif 000007
【００２６】
となり、連結ハミング重みは７となる。したがって、（ｋ＞＞１，ｌ）を用いた楕円同時スカラー倍演算に必要な点加算回数は、事前計算に必要な１回を含めると８回となる。一方、２つの整数を合わせたビット長は１ビット伸びて１２ビットとなる。したがって、楕円同時スカラー倍演算の計算量は、
８Ａ＋１１Ｄ
となる。
ｋとｌをそのまま使う場合の計算量９Ａ＋１０Ｄと、ｋを１ビット右シフトした時の計算量８Ａ＋１１Ｄとのどちらが計算量が少ないかは、点加算の計算量Ａと点２倍算の計算量Ｄの大きさで決まる。素体Ｆｐ上の楕円曲線で、Ｊａｃｏｂｉａｎ座標系を用いた場合、点演算の計算量は、Ａ＝１２Ｍ＋４Ｓ＝１５．２Ｍ、Ｄ＝４Ｍ＋６Ｓ＝８．８Ｍとなる。楕円曲線上の点演算は、定義体上の乗算Ｍと２乗算Ｓとで構成され、ＭとＳとの計算量比は、一般にＳ＝０．８Ｍとなる。したがって、点演算の計算量は定義体上の乗算の回数で評価できる。点演算の公式は、先に紹介した非特許文献２に詳しく記載されている。
したがって、この例の場合、ｋとｌをそのまま使う場合、計算量は、
９Ａ＋１０Ｄ　＝　１３６．８Ｍ＋８８Ｍ　＝　２２４．８Ｍ
となり、ｋを１ビット右シフトした場合は、
８Ａ＋１１Ｄ　＝　１２１．６Ｍ＋９６．８Ｍ　＝　２１８．４Ｍとなり、ｋを１ビット右シフトした場合の方が、楕円同時スカラー倍演算の計算量は少ないことがわかる。
一般に、整数の１つをｉビット右シフトした場合の計算量減少量Ｒｅｄｕｃｔｉｏｎｉ０は、シフトしない場合の連結ハミング重みをＪＨＷ００とし、ｉビット右シフトした場合の連結ハミング重みをＪＨＷｉ０とすると、
Ｒｅｄｕｃｔｉｏｎｉ０＝（ＪＨＷ００−ＪＨＷｉ０）Ａ−ｉＤ
と評価できる。連結ハミング重みの減少量分、加算回数が減り、シフト長分、２倍算回数が増えるので、連結ハミング重みがある程度減少すれば、楕円同時スカラー倍演算全体の計算量は減少することになる。
計算部４２３は、あらかじめシフト長の上限ｓを設定し、ｋを１ビットからｓビットまで右シフトした値とｌとの連結ハミング重みＪＨＷｉ０を計算し、計算量減少量Ｒｅｄｕｃｔｉｏｎｉ０を計算する。
同様に、計算部４２４は、ｌを１ビットからｓビットまで右シフトした値とｋとの連結ハミング重みＪＨＷ０ｉを計算し、計算量減少量Ｒｅｄｕｃｔｉｏｎ０ｉを計算する。
最大値計算部４０５は、計算量減少量が最大となるものを選択する。（ｋ＞＞ｉ，ｌ）と（ｋ，ｌ＞＞ｉ）の中で計算量減少量が最大となるものが、最適なスカラーの組み合わせとなる。全てのＲｅｄｕｃｔｉｏｎｉ０もＲｅｄｕｃｔｉｏｎ０ｉが負の値の場合は、元々の（ｋ，ｌ）が最適なスカラーの組み合わせということになる。
【００２７】
以上のように演算すれば、楕円同時スカラー倍演算の計算量を減少させることができる。
【００２８】
上記説明では、Ｊａｃｏｂｉａｎ座標系を用いた場合の説明をしたが、楕円曲線上の点演算を行う座標系に応じて、点加算演算量Ａと点２倍算演算量Ｄの値を変えればよい。
【００２９】
さらに、一般化すると、以下のように示すことができる。
入力部４０１は、楕円曲線上の複数の点Ｐ１、Ｐ２、…、Ｐｎの値と、ｔビットの複数の正整数ｋ１、ｋ２、…、ｋｎと、シフト長の上限値ｓ（０以上の整数）と、楕円曲線上の点加算の計算量Ａと、楕円曲線上の点２倍算の計算量Ｄとを入力する。
計算部４０３は、上記入力部４０１により入力されたｋ１、ｋ２、…、ｋｎの連結ハミング重みＪＨＷ０…０（ｎ個）＝ＪＨＷ（ｋ１，ｋ２，…，ｋｎ）を計算し、記憶部４０２に記憶する。
記憶部４０２は、変数ｉをＲＡＭ４０等の記憶装置に記憶する。
ｉ初期値設定部４１１は、上記記憶部４０２により記憶された変数ｉに初期値１を設定し、上記記憶装置に記憶する。
ｉインクリメント部４１２は、上記入力部４０１により入力されたシフト長の上限値ｓと、上記記憶装置から読み出した上記ｉ初期値設定部４１１により設定された変数ｉとを用いて、変数ｉがシフト長の上限値ｓに達するまで変数ｉに順次１を加えて、上記記憶装置に記憶する。
連結ハミング重み計算部は、上記ｉインクリメント部４１２により上記記憶装置に変数ｉに順次１が加えられ記憶される度に、上記記憶装置から読み出した変数ｉと、上記入力部４０１により入力された整数ｋ１、ｋ２、…、ｋｎを用いて、整数ｋ１、ｋ２、…、ｋｎ各値の内少なくとも１つを最大ｉビット右シフトした値と右シフトしない他の整数ｋ１、ｋ２、…、ｋｎとの連結ハミング重みＪＨＷｉを順に計算し、それぞれ上記記憶装置に記憶する。
計算量減少量計算部は、上記ｉインクリメント部４１２により上記記憶装置に変数ｉに順次１が加えられ記憶される度に、上記記憶装置から読み出した変数ｉと上記計算部４０３により計算された連結ハミング重みＪＨＷ０…０（ｎ個）と、上記連結ハミング重み計算部により計算された連結ハミング重みＪＨＷｉと、楕円曲線上の点加算の計算量Ａと、楕円曲線上の点２倍算の計算量Ｄとを読み出し、さらに、上記整数ｋ１、ｋ２、…、ｋｎ各値の内、最大ｉビット右シフトした少なくとも１つの整数のシフト値の合計値Ｚを用いて、計算量減少量Ｒｅｄｕｃｔｉｏｎｉ＝（ＪＨＷ０…０（ｎ個）−ＪＨＷｉ）Ａ−ＺＤを順に計算し、上記記憶装置に記憶する。
最大値計算部４０５は、上記計算量減少量計算部により順に計算された計算量減少量Ｒｅｄｕｃｔｉｏｎｉの内、計算量減少量の最大値を計算し、上記記憶装置に記憶する。
出力部４０６は、上記最大値計算部４０５により計算された計算量減少量の最大値が正の値である場合には上記最大値に対応する計算量減少量に用いられた最大ｉビット右シフトした少なくとも１つの整数の値と右シフトしない他の整数ｋ１、ｋ２、…、ｋｎとを、上記最大値計算部により計算された計算量減少量の最大値が正の値でない場合には上記入力部により入力された整数ｋ１、ｋ２、…、ｋｎを出力する。
【００３０】
本演算方法を、楕円曲線を用いた暗号化やディジタル署名に使用することもできる。
【００３１】
本演算方法は、楕円曲線上のスカラー倍演算だけでなく、法ｎでのべき乗剰余演算の場合にも適用できる。また、法ｎでのべき乗剰余演算を用いた暗号系にも適用できる。
【００３２】
以上のように、実施の形態１における変換装置４００が行なう２つの正整数ｋとｌを変換する方法は、以下の要素を有する変換方法である。
（１）ｔビットの２つの正整数ｋとｌと、シフト長の上限ｓ（０以上の整数）と、楕円曲線上の点加算の計算量Ａと、楕円曲線上の点２倍算の計算量Ｄとを入力する工程、
（２）ｋとｌとの連結ハミング重みＪＨＷ００＝ＪＨＷ（ｋ，ｌ）を計算し、記憶する工程、
（３）変数ｉを記憶するｉ記憶工程、
（４）ｉ記憶手段に、変数ｉの初期値１を設定するｉ初期値設定工程、
（５）整数ｓと、変数ｉとを読み出し、変数ｉが整数ｓに達するまで変数ｉに順次１を加えて、ｉ記憶手段に設定するｉインクリメント工程、
（６）ｉ記憶手段に変数ｉが設定される度に、変数ｉと、整数ｋと、整数ｌとを読み出し、整数ｋをｉビット右シフトした値と整数ｌとの連結ハミング重みＪＨＷｉ０＝ＪＨＷ（ｋ＞＞ｉ，ｌ）を計算し、記憶する工程、
（７）ｉ記憶手段に変数ｉが設定される度に、変数ｉと、整数ｋと、整数ｌとを読み出し、整数ｋと整数ｌをｉビット右シフトした値との連結ハミング重みＪＨＷ０ｉ＝ＪＨＷ（ｋ，ｌ＞＞ｉ）を計算し、記憶する工程、
（８）ｉ記憶手段に変数ｉが設定される度に、変数ｉと、連結ハミング重みＪＨＷ００と、連結ハミング重みＪＨＷｉ０と、楕円曲線上の点加算の計算量Ａと、楕円曲線上の点２倍算の計算量Ｄとを読み出し、計算量減少量Ｒｅｄｕｃｔｉｏｎｉ０＝（ＪＨＷ００−ＪＨＷｉ０）Ａ−ｉＤを計算し、記憶する工程、
（９）ｉ記憶手段に変数ｉが設定される度に、変数ｉと、連結ハミング重みＪＨＷ００と、連結ハミング重みＪＨＷ０ｉと、楕円曲線上の点加算の計算量Ａと、楕円曲線上の点２倍算の計算量Ｄとを読み出し、計算量減少量Ｒｅｄｕｃｔｉｏｎ０ｉ＝（ＪＨＷ００−ＪＨＷ０ｉ）Ａ−ｉＤを計算し、記憶する工程、
（１０）計算量減少量の最大値を計算し、記憶する工程、
（１１）計算量減少量が最大となる（ｋ，ｌ）または（ｋ＞＞ｓ’，ｌ）または（ｋ，ｌ＞＞ｓ’）を出力する出力工程。
【００３３】
また、変換装置４００は、複数の正整数ｋ１、ｋ２、…、ｋｎに対して変換する変換装置として用いることができる。
【００３４】
以上のように、本実施の形態１によれば、楕円曲線演算を高速に行うためのスカラー変換を行なうことができる。
【００３５】
本実施の形態１では、正整数について符号なし２進数展開した値を用いた例が記載されているが、これに限るものではなく正整数について符号付２進数展開した値を用いても構わない。
ここで、例えば、楕円曲線上の点Ｐと正整数１５とを用いて、スカラー倍演算１５Ｐを行なう場合について説明する。
正整数１５について符号なし２進数展開すると４ビット値１１１１となる。よって、点加算演算が必要な非ゼロ列となる桁の数は、４になる。点２倍算演算が必要なビット数ｔ−１の値は３となる。また、Ａ＝１５．２Ｍ、Ｄ＝８．８Ｍである。したがって、スカラー倍演算１５Ｐを行なう場合の計算量は、４Ａ＋３Ｄ＝８７．２Ｍとなる。
次に、正整数１５を１６−１と捉え、１６−１について、符号付２進数展開すると
【００３６】
【数６】
2004117627.tif 000008
【００３７】
のように５ビット値となる。よって、点加算演算が必要な非ゼロ列となる桁の数は、２になる。点２倍算演算が必要なビット数ｔ−１の値は４となる。また、Ａ＝１５．２Ｍ、Ｄ＝８．８Ｍである。したがって、スカラー倍演算１５Ｐ＝（１６−１）Ｐを行なう場合の計算量は、２Ａ＋４Ｄ＝６５．６Ｍとなる。
よって、正整数について符号なし２進数展開した値を用いた場合より符号付２進数展開した値を用いた方がスカラー倍演算の計算量を少なくすることができる場合もある。
以上のように、本実施の形態１では、正整数について符号なし２進数展開した値ではなく正整数について符号付２進数展開した値を用いることにより、さらに、スカラー倍演算の計算量を少なくするスカラーを計算することができ、楕円曲線演算を高速に行うためのスカラー変換を行なうことができる。
【００３８】
実施の形態２．
図５は、実施の形態２における楕円曲線演算装置の構成を示すブロック図である。
図５において、楕円同時スカラー倍演算装置５００（楕円曲線演算装置の一例である。）は、入力部５０１、記憶部５０７（記憶装置の一例である。）、変換部５０２、計算部５２０（第２の計算部、第７の計算部の一例である。）、出力部５０６を備えている。変換部５０２は、図３における変換装置４００を有している。計算部５２０は、計算部５０３（変換設定部の一例である。）、スカラー倍計算部５３０を有している。スカラー倍計算部５３０は、計算部５０４、計算部５０５、点加算部５０８、点２倍算部５０９を有している。その他の構成は、図１、図２、図３と同様である。楕円同時スカラー倍演算装置５００は、制御部５１０に接続されている。ＰＣ１００は、楕円同時スカラー倍演算装置５００、制御部５１０を備えている。
【００３９】
入力部５０１は、楕円曲線上の複数の点の値とそれぞれ所定の桁数を有する２進数の複数の正整数とを入力する。言いかえれば、入力部５０１は、楕円曲線上の２点ＰとＱの値と、ｔビットの２つの正整数ｋとｌと、シフト長の上限値ｓ（０以上の整数）と、楕円曲線上の点加算の計算量Ａと、楕円曲線上の点２倍算の計算量Ｄとを入力する。
変換部５０２は、図３における変換装置４００の出力部４０６より出力された、上記最大値計算部４０５により選択され上記記憶部４０２に記憶された計算回数合計値を計算させた複数の正整数の内上記シフト部４１０によりシフトされた１つの正整数と、複数の正整数の内上記シフト部４１０によりシフトされていない他の正整数とを計算部５２０に出力する。言いかえれば、変換部５０２は、図３における変換装置４００の出力部４０６より出力された、上記最大値計算部４０５により計算された計算量減少量の最大値が正の値である場合には上記最大値に対応する計算量減少量に用いられた整数ｋと整数ｌとの組合わせである（ｋ＞＞ｉ，ｌ）と（ｋ，ｌ＞＞ｉ）とのいずれかを、上記最大値計算部４０５により計算された計算量減少量の最大値が負の値である場合には上記入力部４０１により入力された整数ｋと整数ｌとの組合わせである（ｋ，ｌ）を計算部５２０に出力する。
計算部５２０は、変換部５０２により入力された、上記最大値計算部４０５により選択され上記記憶部４０２に記憶された計算回数合計値を計算させた複数の正整数の内上記シフト部４１０によりシフトされた１つの正整数と、複数の正整数の内上記シフト部４１０によりシフトされていない他の正整数と用いて、楕円曲線上の複数の点の値のスカラー倍の和を計算し、計算された楕円曲線上の複数の点の値のスカラー倍の和を上記記憶部５０７に記憶させる。ここで、計算部５２０は、楕円曲線上の複数の点の値のスカラー倍の和を計算するにあたり、上記シフト部４１０によりシフトされた１つの正整数と数値２に上記１つの正整数のシフト値をべき乗した２ｓ’（第１の補正値の一例である。）とを乗じ、さらに、上記１つの正整数が上記シフト部４１０によりシフトされなかった場合に加算されていたであろう値の代わりに、上記乗じた値と上記シフト部４１０によりシフトされた１つの正整数を計算に用いたことにより生じる第２の補正値の一例である値ｃＲとを楕円曲線上の複数の点の値のスカラー倍の和に加算することにより楕円曲線上の複数の点の値のスカラー倍の和を補正する。言いかえれば、計算部５２０は、変換部５０２により入力された、上記最大値計算部４０５により計算された計算量減少量の最大値が正の値である場合には上記最大値に対応する計算量減少量に用いられた整数ｋと整数ｌとの組合わせである（ｋ＞＞ｉ，ｌ）と（ｋ，ｌ＞＞ｉ）とのいずれかを、上記最大値計算部４０５により計算された計算量減少量の最大値が負の値である場合には上記入力部４０１により入力された整数ｋと整数ｌとの組合わせである（ｋ，ｌ）を用いて、上記入力部５０１により入力された楕円曲線上の２点ＰとＱの値のスカラー倍の和を計算し、上記記憶装置の一例である記憶部５０７に記憶する。ここで、計算部５２０は、計算に用いられた整数ｋと整数ｌとの組合わせが（ｋ，ｌ）の場合、ＰをＰｓに、ＱをＱｓに、ｋをｋ’に、ｌをｌ’に変換し、数値０の値を有する第１の補正値ｃと無限遠点値を有する第２の補正値Ｒとを設定し、上記記憶部５０７に記憶し、
計算に用いられた整数ｋと整数ｌとの組合わせであるが（ｋ＞＞ｉ，ｌ）の場合、２ｓ’ＰをＰｓに、ＱをＱｓに、ｋ＞＞ｉをｋ’に、ｌをｌ’に変換し、ｋと（２ｉ−１）とのビット毎の論理積の値ｋ∧（２ｉ−１）を有する第１の補正値ｃと楕円曲線上の点Ｐの値を有する第２の補正値Ｒとを設定し、上記記憶部５０７に記憶する。
計算部５０３は、計算に用いられた整数ｋと整数ｌとの組合わせが（ｋ，ｌ＞＞ｉ）の場合、ＰをＰｓに、２ｓ’ＱをＱｓに、ｋをｋ’に、ｌ＞＞ｉをｌ’に変換し、ｌと（２ｉ−１）とのビット毎の論理積の値ｌ∧（２ｉ−１）を有する第１の補正値ｃと楕円曲線上の点Ｑの値を有する第２の補正値Ｒとを設定し、上記記憶部５０７に記憶する。
スカラー倍計算部５３０は、計算部５０３により変換されたＰｓとＱｓとｋ’とｌ’と、上記計算部５０３により設定された第１の補正値ｃと第２の補正値Ｒとを用いて補正された楕円曲線上の２点ＰとＱの値のスカラー倍の和ｋ’Ｐｓ＋ｌ’Ｑｓ＋ｃＲを計算し、上記記憶部５０７に記憶する。
出力部５０６は、上記計算部５２０により計算され上記記憶部５０７に記憶された楕円曲線上の複数の点の値のスカラー倍の和を出力する。言いかえれば、出力部５０６は、上記計算部５２０により計算された楕円曲線上の２点ＰとＱの値のスカラー倍の和を出力する。
【００４０】
図６は、実施の形態２による楕円同時スカラー倍演算方法を示したフローチャートである。
図６におけるＳ２００において、入力部５０１は、まず、楕円曲線上の２点ＰとＱがと、ｔビットの２つの正整数ｋとｌと、シフト長の上限ｓとを入力する。
Ｓ２０１において、変換部５０２は、実施の形態１における変換装置４００を用いて、最適な整数の組を選択する。
Ｓ２０２において、計算部５０３は、Ｓ２０３における楕円同時スカラー倍演算の前に行う事前計算を行なう。
Ｓ２０３において、計算部５０４は、楕円同時スカラー倍演算を行う。
Ｓ２０４において、計算部５０５は、楕円同時スカラー倍演算の後に行う事後計算を行なう。
Ｓ２０５において、出力部５０６は、最後に、楕円同時スカラー倍演算の結果を出力する。
【００４１】
次に図６における各ステップの説明を追加する。
まず、Ｓ２００において、入力部５０１により楕円曲線上の２点ＰとＱと、ｔビットの２つの正整数ｋとｌと、シフト長の上限ｓとが入力される。
次に、Ｓ２０１において、変換部５０２は、ｋとｌ、およびシフトされたｋとｌの中から、楕円同時スカラー倍演算に最適な組み合わせを選択する。この選択は、前述の実施の形態１の方法を用いる。
ここで、Ｓ２０３は、従来の楕円同時スカラー倍演算方法であるが、楕円同時スカラー倍演算を行う際に入力される整数および曲線上の点は、シフトに応じて補正されたものでなければならない。その補正を行うステップがＳ２０２である。例えば、ｋがｓ’ビット右シフトされた場合、点Ｐを入力する変わりに、２ｓ’Ｐを入力しなければならない。また、ｌがｓ’ビット右シフトされた場合、点Ｑを入力する変わりに、２ｓ’Ｑを入力しなければならない。ｃは、右シフトによって生じた切捨てビットで、ｋをｓ’ビット右シフトした場合は、切捨てられるビットはｋ∧（２ｓ’−１）となる。ここで、記号∧はビットごとの論理積である。ｌをｓ’ビット右シフトした場合は、切捨てられるビットはｌ∧（２ｓ’−１）となる。ｃは、Ｓ２０３の楕円同時スカラー倍演算の終了後、参照される。ｃに応じて点の加算を行う必要がある。
最後に、楕円同時スカラー倍演算結果を出力する。
【００４２】
以上のように演算すれば、楕円同時スカラー倍演算の計算量を減少させることができる。
【００４３】
本演算方法を、楕円曲線を用いた暗号化やディジタル署名に使用することもできる。
【００４４】
本演算方法は、楕円曲線上のスカラー倍演算だけでなく、法ｎでのべき乗剰余演算の場合にも適用できる。また、法ｎでのべき乗剰余演算を用いた暗号系にも適用できる。
【００４５】
以上のように、本実施の形態２における楕円同時スカラー倍演算装置５００は、楕円曲線上の複数の点Ｐ１、Ｐ２、…、Ｐｎと、複数の正整数ｋ１、ｋ２、…、ｋｎから、複数のスカラー倍点の和ｋ１Ｐ１＋ｋ２Ｐ２＋…＋ｋｎＰｎを計算する方法であって、正整数ｋ１、ｋ２、…、ｋｎを連結ハミング重みが最適になるように変換し、複数のスカラー倍点を計算する。
【００４６】
以上のように、本実施の形態２における楕円同時スカラー倍演算装置５００がおこなう楕円曲線上の同時スカラー倍演算を行う楕円曲線演算方法は、以下の要素を有する。
（１）楕円曲線上の２点ＰとＱと、ｔビットの２つの正整数ｋとｌと、シフト長の上限ｓ（０以上の整数）とを入力する工程、
（２）実施の形態１の変換方法を用いて（ｋ，ｌ）または（ｋ＞＞ｓ’，ｌ）または（ｋ，ｌ＞＞ｓ’）の中から最適な組を選択し、記憶する工程、
（３）前記選択された組が（ｋ，ｌ）の場合、次を計算し、記憶する工程、
Ｐｓ←Ｐ，Ｑｓ←Ｑ，ｋ’←ｋ，ｌ’←ｌ，ｃ←０，Ｒ←О
（４）前記選択された組が（ｋ＞＞ｓ’，ｌ）の場合、次を計算し、記憶する工程、
Ｐｓ←２ｓ’Ｐ，Ｑｓ←Ｑ，ｋ’←ｋ＞＞ｓ’，ｌ’←ｌ，ｃ←ｋ∧（２ｓ’−１），Ｒ←Ｐ
（５）前記選択された組が（ｋ，ｌ＞＞ｓ’）の場合、次を計算し、記憶する工程、
Ｐｓ←Ｐ，Ｑｓ←２ｓ’Ｑ，ｋ’←ｋ，ｌ’←ｌ＞＞ｓ’，ｃ←ｌ∧（２ｓ’−１），Ｒ←Ｑ
（６）次を計算し、記憶する工程、
Ａ＝ｋ’Ｐｓ＋ｌ’Ｑｓ
（７）Ａを出力する工程。
【００４７】
以上のように、本実施の形態２における楕円同時スカラー倍演算装置５００は、複数の正整数ｋ１、ｋ２、…、ｋｎと、複数の楕円曲線上の点Ｐ１、Ｐ２、…、Ｐｎに対してｋ１Ｐ１＋ｋ２Ｐ２＋，…，ｋｎＰｎを演算する。
【００４８】
以上のように、本実施の形態２によれば、楕円曲線演算を高速に行うことができる。
また、上記演算方法を利用することにより、楕円曲線を用いた暗号化やディジタル署名を高速に行うことができる。
【００４９】
実施の形態３．
図７は、実施の形態３における楕円曲線演算装置の構成を示すブロック図である。
図７において、楕円同時スカラー倍演算装置６００（楕円曲線演算装置の一例である。）は、入力部６０１、記憶部６０５（ｉ記憶部、記憶装置の一例である。）、計算部６０２、計算部６０３、出力部６０４、スカラー倍演算部６０６（第２の計算部、第７の計算部の一例である。）を備えている。計算部６０３は、シフト部６１１、分割部６１２、選択部６１４（第６の計算部の一例である。）、計算部６２０、計算部６３０（第１の計算部の一例である。）を有している。計算部６２０（第１の計算部の一例である。）は、計算部６２１（第２の計算部の一例である。）、計算部６２２（第３の計算部の一例である。）、計算部６２３（第４の計算部の一例である。）、計算部６２４（第５の計算部の一例である。）を有している。シフト部６１１は、ｉ初期値設定部６３１、ｉインクリメント部６３２を有している。その他の構成は、図１、図２、図３と同様である。楕円同時スカラー倍演算装置６００は、制御部６０７に接続されている。ＰＣ１００は、楕円同時スカラー倍演算装置６００、制御部６０７を備えている。
【００５０】
入力部６０１は、楕円曲線上の複数の点の値とそれぞれ所定の桁数を有する２進数の複数の正整数と所定のブロック数とを入力する。言いかえれば、上記入力部６０１は、楕円曲線上の２点ＰとＱの値と、ｔビットの２つの正整数ｋとｌと、シフト長の上限値ｓ（０以上の整数）と、楕円曲線上の点加算の計算量Ａと、楕円曲線上の点２倍算の計算量Ｄと、さらに、上記ｔビットを分割するためのブロック長ｂ（正整数）を入力する。
計算部６０２は、楕円同時スカラー倍演算結果である点Ａ値を無限遠点に初期化する。
計算部６３０は、上記入力部６０１により入力されたｋとｌとの連結ハミング重みＪＨＷ００＝ＪＨＷ（ｋ，ｌ）を計算し、記憶部６０５に記憶する。
分割部６１２は、上記入力部６０１により入力された複数の正整数に対し、所定のブロック数により複数の正整数の桁を複数のブロックに分割する。
上記記憶部６０５は、上記分割部６１２により分割された所定のブロック数毎に、複数の正整数の同位置の桁に１つでも１が割り当てられた桁の数の合計値を初期合計値として記憶する。また、上記記憶部６０５は、変数ｉをＲＡＭ４０等の記憶装置に記憶する。
ｉ初期値設定部６３１は、上記記憶部６０５により記憶された変数ｉに初期値１を設定し、上記記憶部６０５に記憶する。
上記シフト部６１１は、上記分割部６１２により分割された所定のブロック数毎に、上記複数の正整数の各正整数に対し、順に、複数の正整数の内１つを残して他の少なくとも１つの正整数の各桁に割り当てられた値を１桁ずつ所定の上限値までシフトする。
上記計算部６２０は、上記分割部６１２により分割された所定のブロック数毎に、上記シフト部６１１によりシフトされた結果として上記複数の正整数の同位置の桁に１つでも１が割り当てられた桁の数の合計値と、上記記憶部６０５に記憶された初期合計値と、上記シフト部６１１によりシフトされた上記各正整数のシフト値とを用いて、上記シフト部６１１によりシフトされた場合の楕円曲線上の複数の点のスカラー倍点の和を計算するための計算回数の合計値と、上記シフト部６１１によりシフトされない場合の楕円曲線上の複数の点のスカラー倍点の和を計算するための計算回数の合計値との差を上記各正整数の計算回数合計差分値としてそれぞれ計算し、上記各正整数の計算回数合計差分値を上記記憶部６０５に記憶させる。
言いかえれば、上記計算部６３０は、整数ｋと整数ｌの上位ｉ番目のｂビットブロック毎に、上記入力部６０１により入力されたｋとｌとの連結ハミング重みＪＨＷ００＝ＪＨＷ（ｋ，ｌ）を計算し、記憶部６０５に記憶する。上記ｉインクリメント部６３２は、ｔをｂで除し、除した値の内の整数ｔ／ｂと、変数ｉとを用いて、変数ｉが整数ｔ／ｂに達するまで変数ｉに順次１を加えて、上記記憶部６０５に記憶する。計算部６２１は、上記ｉインクリメント部６３２により変数ｉに順次１を加えられる度に、整数ｋと整数ｌの上位ｉ番目のｂビットブロック毎に、上記記憶部６０５から読み出した変数ｉと、上記入力部６０１により入力された整数ｋと整数ｌとを用いて、整数ｋをｉビット右シフトした値（ｋ＞＞ｉ）と整数ｌとの連結ハミング重みＪＨＷｉ０＝ＪＨＷ（ｋ＞＞ｉ，ｌ）を計算し、上記記憶部６０５に記憶する。計算部６２２は、上記ｉインクリメント部６３２により変数ｉに順次１を加えられる度に、整数ｋと整数ｌの上位ｉ番目のｂビットブロック毎に、上記記憶部６０５から読み出した変数ｉと、上記入力部６０１により入力された整数ｋと整数ｌとを用いて、整数ｋと整数ｌをｉビット右シフトした値（ｌ＞＞ｉ）との連結ハミング重みＪＨＷ０ｉ＝ＪＨＷ（ｋ，ｌ＞＞ｉ）を計算し、上記記憶部６０５に記憶する。計算部６２３は、上記ｉインクリメント部６３２により変数ｉに順次１を加えられる度に、整数ｋと整数ｌの上位ｉ番目のｂビットブロック毎に、上記記憶部６０５から読み出した変数ｉと上記計算部６３０により計算された連結ハミング重みＪＨＷ００と上記計算部６２１により計算された連結ハミング重みＪＨＷｉ０と、上記入力部６０１により入力された楕円曲線上の点加算の計算量Ａと楕円曲線上の点２倍算の計算量Ｄとを用いて、計算量減少量Ｒｅｄｕｃｔｉｏｎｉ０＝（ＪＨＷ００−ＪＨＷｉ０）Ａ−ｉＤを計算し、上記記憶部６０５に記憶する。計算部６２４は、上記ｉインクリメント部６３２により変数ｉに順次１を加えられる度に、整数ｋと整数ｌの上位ｉ番目のｂビットブロック毎に、上記記憶部６０５から読み出した変数ｉと上記計算部６３０により計算された連結ハミング重みＪＨＷ００と、上記計算部６２３により計算された連結ハミング重みＪＨＷ０ｉと、楕円曲線上の点加算の計算量Ａと、楕円曲線上の点２倍算の計算量Ｄとを読み出し、計算量減少量Ｒｅｄｕｃｔｉｏｎ０ｉ＝（ＪＨＷ００−ＪＨＷ０ｉ）Ａ−ｉＤを計算し、上記記憶部６０５に記憶する。
上記選択部６１４は、上記分割部６１２により分割された所定のブロック数毎に、上記計算部６２０により計算され上記記憶部６０５に記憶された上記各正整数の計算回数合計差分値の内、最大となる計算回数合計差分値を選択し、選択された計算回数合計差分値を上記記憶部６０５に記憶させる。言いかえれば、選択部６１４は、上記ｉインクリメント部６３２により変数ｉに順次１を加えられる度に、整数ｋと整数ｌの上位ｉ番目のｂビットブロック毎に、上記計算部６２３により計算された計算量減少量Ｒｅｄｕｃｔｉｏｎｉ０と上記上記計算部６２４により計算された計算量減少量Ｒｅｄｕｃｔｉｏｎ０ｉとの内、計算量減少量の最大値を計算し、上記記憶部６０５に記憶する。
上記スカラー倍演算部６０６は、上記分割部６１２により分割された所定のブロック数毎に、上記選択部６１４により選択され上記記憶部６０５に記憶された計算回数合計差分値が正の場合、上記選択部６１４により選択され上記記憶部６０５に記憶された計算回数合計差分値を計算させた複数の正整数の内、上記シフト部６１１によりシフトされた少なくとも１つの正整数と、複数の正整数の内、上記シフト部６１１によりシフトされていない他の正整数とを用いて、楕円曲線上の複数の点の値のスカラー倍の和を計算する。上記選択部６１４により選択され上記記憶部６０５に記憶された計算回数合計差分値が正でない場合、上記シフト部６１１によりシフトされていない上記入力部６０１により入力された正整数を用いて、楕円曲線上の複数の点の値のスカラー倍の和を計算する。そして、スカラー倍演算部６０６は、所定のブロック数毎に計算された楕円曲線上の複数の点の値のスカラー倍の和の合計値を上記記憶部６０５に記憶させる。言いかえれば、上記スカラー倍演算部６０６は、上記ｉインクリメント部６３２により変数ｉに順次１を加えられる度に、整数ｋと整数ｌの上位ｉ番目のｂビットブロック毎に、上記選択部６１４により計算された計算量減少量の最大値が正の値である場合には上記最大値に対応する計算量減少量に用いられた整数ｋと整数ｌとの組合わせである（ｋ＞＞ｉ，ｌ）と（ｋ，ｌ＞＞ｉ）とのいずれかを、上記選択部６１４により計算された計算量減少量の最大値が負の値、或いは０値である場合には上記入力部６０１により入力された整数ｋと整数ｌとの組合わせである（ｋ，ｌ）を用いて、上記入力部６０１により入力された楕円曲線上の２点ＰとＱの値のスカラー倍の和を計算する。そして、スカラー倍演算部６０６は、ｂビットブロック毎に計算された楕円曲線上の２点ＰとＱの値のスカラー倍の和の合計を上記記憶部６０５に記憶する。
上記出力部６０４は、上記スカラー倍演算部６０６により計算され上記記憶部６０５に記憶された楕円曲線上の複数の点の値のスカラー倍の和の合計値を出力する。
【００５１】
図８は、実施の形態３による楕円同時スカラー倍演算方法を示したフローチャートである。
図８におけるＳ３００において、入力部６０１は、まず、楕円曲線上の２点ＰとＱがと、ｔビットの２つの正整数ｋとｌと、シフト長の上限ｓと、ブロック長ｂとを入力する。
Ｓ３０１において、計算部６０２は、楕円同時スカラー倍演算結果である点Ａを無限遠点に初期化する。
Ｓ３０２において、計算部６０３は、ｋとｌをブロック分割して楕円同時スカラー倍演算を実行する。
Ｓ３０３において、出力部６０４は、楕円同時スカラー倍演算の結果を出力する。
【００５２】
次に図８における各ステップの説明を追加する。
まず、Ｓ３００において、入力部６０１により、楕円曲線上の２点ＰとＱと、ｔビットの２つの正整数ｋとｌと、シフト長の上限ｓと、ブロック長ｂとが入力される。
Ｓ３０２において、計算部６０３による楕円同時スカラー倍演算は、整数ｋとｌをｂビットのブロックに分割し、ブロックごとに行う。まず、ｋとｌとを上位側からｂビット取り出し、実施の形態２で説明した楕円同時スカラー倍演算を行う。次に、ｋとｌから次のｂビットブロックを取り出し、実施の形態２で説明した楕円同時スカラー倍演算を行う。ブロックの分割数は、ｔ／ｂとなる。例えば、ｋとｌを
【００５３】
【数７】
2004117627.tif 000009
【００５４】
とし、ｂ＝４とすると、ｋとｌは１１ビットであるから３つのブロックに分割される。最初のブロックは
【００５５】
【数８】
2004117627.tif 000010
【００５６】
となり、２番目のブロックは、
【００５７】
【数９】
2004117627.tif 000011
【００５８】
となり、最後のブロックは、
【００５９】
【数１０】
2004117627.tif 000012
【００６０】
となる。各ブロックごとに計算された楕円同時スカラー倍演算結果は、次のブロックを計算結果に加算することによって、楕円同時スカラー倍演算全体が計算される。
Ｓ３０３において、出力部６０４は、楕円同時スカラー倍演算結果を出力する。
【００６１】
以上のように、実施の形態３における楕円同時スカラー倍演算装置６００が行なう楕円曲線上の同時スカラー倍演算を行う楕円曲線演算方法は、以下の要素を有する。
（１）楕円曲線上の２点ＰとＱと、ｔビットの２つの正整数ｋとｌと、シフト長の上限ｓ（０以上の整数）と、ブロック長ｂ（正整数）とを入力する工程、
（２）Ａを無限遠点に初期化する工程、
（３）変数ｉを記憶するｉ記憶工程、
（４）ｉ記憶手段に、変数ｉの初期値１を設定するｉ初期値設定工程、
（５）整数ｔ／ｂと、変数ｉとを読み出し、変数ｉが整数ｔ／ｂに達するまで変数ｉに順次１を加えて、ｉ記憶手段に設定するｉインクリメント工程、
（６）ｉ記憶手段に変数ｉが設定される度に、ｋとｌの上位ｉ番目のｂビットブロックを取り出し、それぞれｋ’、ｌ’とし、実施の形態１に記載の楕円曲線演算方法を用いて、次を計算し、記憶する工程、
Ａ←ｋ’Ｐ＋ｌ’Ｑ＋Ａ
（７）Ａを出力する工程。
【００６２】
以上のように、実施の形態３における楕円同時スカラー倍演算装置６００は、複数の正整数ｋ１、ｋ２、…、ｋｎと、複数の楕円曲線上の点Ｐ１、Ｐ２、…、Ｐｎに対してｋ１Ｐ１＋ｋ２Ｐ２＋，…，ｋｎＰｎを演算する。
【００６３】
実施の形態１、２、３とも整数ｋとｌを符号なし２進展開した場合で説明したが、符号付２進展開や、他の展開方法に対しても適用できる。
【００６４】
以上のように、上記実施の形態に係る演算方法は、楕円曲線上の複数の点Ｐ１、Ｐ２、…、Ｐｎと、複数の正整数ｋ１、ｋ２、…、ｋｎから、複数のスカラー倍点の和ｋ１Ｐ１＋ｋ２Ｐ２＋…＋ｋｎＰｎを計算する方法であって、正整数ｋ１、ｋ２、…、ｋｎを連結ハミング重みが最適になるように変換し、複数のスカラー倍点を計算することを特徴とする。
【００６５】
また、上記実施の形態に係る変換方法は、２つの正整数ｋとｌを変換する方法であって、以下の要素を有することを特徴とする。
（１）ｔビットの２つの正整数ｋとｌと、シフト長の上限ｓ（０以上の整数）と、楕円曲線上の点加算の計算量Ａと、楕円曲線上の点２倍算の計算量Ｄとを入力する工程、
（２）ｋとｌとの連結ハミング重みＪＨＷ００＝ＪＨＷ（ｋ，ｌ）を計算し、記憶する工程、
（３）変数ｉを記憶するｉ記憶工程、
（４）ｉ記憶手段に、変数ｉの初期値１を設定するｉ初期値設定工程、
（５）整数ｓと、変数ｉとを読み出し、変数ｉが整数ｓに達するまで変数ｉに順次１を加えて、ｉ記憶手段に設定するｉインクリメント工程、
（６）ｉ記憶手段に変数ｉが設定される度に、変数ｉと、整数ｋと、整数ｌとを読み出し、整数ｋをｉビット右シフトした値と整数ｌとの連結ハミング重みＪＨＷｉ０＝ＪＨＷ（ｋ＞＞ｉ，ｌ）を計算し、記憶する工程、
（７）ｉ記憶手段に変数ｉが設定される度に、変数ｉと、整数ｋと、整数ｌとを読み出し、整数ｋと整数ｌをｉビット右シフトした値との連結ハミング重みＪＨＷ０ｉ＝ＪＨＷ（ｋ，ｌ＞＞ｉ）を計算し、記憶する工程、
（８）ｉ記憶手段に変数ｉが設定される度に、変数ｉと、連結ハミング重みＪＨＷ００と、連結ハミング重みＪＨＷｉ０と、楕円曲線上の点加算の計算量Ａと、楕円曲線上の点２倍算の計算量Ｄとを読み出し、計算量減少量Ｒｅｄｕｃｔｉｏｎｉ０＝（ＪＨＷ００−ＪＨＷｉ０）Ａ−ｉＤを計算し、記憶する工程、
（９）ｉ記憶手段に変数ｉが設定される度に、変数ｉと、連結ハミング重みＪＨＷ００と、連結ハミング重みＪＨＷ０ｉと、楕円曲線上の点加算の計算量Ａと、楕円曲線上の点２倍算の計算量Ｄとを読み出し、計算量減少量Ｒｅｄｕｃｔｉｏｎ０ｉ＝（ＪＨＷ００−ＪＨＷ０ｉ）Ａ−ｉＤを計算し、記憶する工程、
（１０）計算量減少量の最大値を計算し、記憶する工程
（１１）計算量減少量が最大となる（ｋ，ｌ）または（ｋ＞＞ｓ’，ｌ）または（ｋ，ｌ＞＞ｓ’）を出力する出力工程。
【００６６】
また、上記実施の形態に係る演算方法は、楕円曲線上の同時スカラー倍演算を行う方法であって、以下の要素を有することを特徴とする。
（１）楕円曲線上の２点ＰとＱと、ｔビットの２つの正整数ｋとｌと、シフト長の上限ｓ（０以上の整数）とを入力する工程、
（２）実施の形態１に記載の変換方法を用いて（ｋ，ｌ）または（ｋ＞＞ｓ’，ｌ）または（ｋ，ｌ＞＞ｓ’）の中から最適な組を選択し、記憶する工程、
（３）前記選択された組が（ｋ，ｌ）の場合、次を計算し、記憶する工程、
Ｐｓ←Ｐ，　Ｑｓ←Ｑ，　ｋ’←ｋ，　ｌ’←ｌ，　ｃ←０，　Ｒ←О
（４）前記選択された組が（ｋ＞＞ｓ’，ｌ）の場合、次を計算し、記憶する工程、
Ｐｓ←２ｓ’Ｐ，　Ｑｓ←Ｑ，　ｋ’←ｋ＞＞ｓ’，　ｌ’←ｌ，　ｃ←ｋ∧（２ｓ’−１），　Ｒ←Ｐ
（５）前記選択された組が（ｋ，ｌ＞＞ｓ’）の場合、次を計算し、記憶する工程、
Ｐｓ←Ｐ，　Ｑｓ←２ｓ’Ｑ，　ｋ’←ｋ，　ｌ’←ｌ＞＞ｓ’，　ｃ←ｌ∧（２ｓ’−１），　Ｒ←Ｑ
（６）次を計算し、記憶する工程、
Ａ　＝　ｋ’Ｐｓ　＋　ｌ’Ｑｓ
（７）Ａを出力する工程。
【００６７】
また、上記実施の形態に係る演算方法は、楕円曲線上の同時スカラー倍演算を行う方法であって、以下の要素を有することを特徴とする。
（１）楕円曲線上の２点ＰとＱと、ｔビットの２つの正整数ｋとｌと、シフト長の上限ｓ（０以上の整数）と、ブロック長ｂ（正整数）とを入力する工程、
（２）Ａを無限遠点に初期化する工程、
（３）変数ｉを記憶するｉ記憶工程、
（４）ｉ記憶手段に、変数ｉの初期値１を設定するｉ初期値設定工程、
（５）整数ｔ／ｂと、変数ｉとを読み出し、変数ｉが整数ｔ／ｂに達するまで変数ｉに順次１を加えて、ｉ記憶手段に設定するｉインクリメント工程、
（６）ｉ記憶手段に変数ｉが設定される度に、ｋとｌの上位ｉ番目のｂビットブロックを取り出し、それぞれｋ’、ｌ’とし、実施の形態２に記載の楕円曲線演算方法を用いて、次を計算し、記憶する工程、
Ａ　←　ｋ’Ｐ　＋　ｌ’Ｑ　＋　Ａ
（７）Ａを出力する工程。
【００６８】
以上のように、本実施の形態３によれば、桁数の多いスカラーであっても楕円曲線演算を高速に行うことができる。
【００６９】
以上の説明において、各実施の形態の説明において「〜部」として説明したものは、一部或いはすべてコンピュータで動作可能なプログラムにより構成することができる。これらのプログラムは、例えば、Ｃ言語により作成することができる。或いは、ＨＴＭＬやＳＧＭＬやＸＭＬを用いても構わない。或いは、ＪＡＶＡ（登録商標）を用いて画面表示を行っても構わない。
また、各実施の形態の説明において「〜部」として説明したものは、ＲＯＭ３９に記憶されたファームウェアで実現されていても構わない。或いは、ソフトウェア或いは、ハードウェア或いは、ソフトウェアとハードウェアとファームウェアとの組み合わせで実施されても構わない。
また、上記各実施の形態を実施させるプログラムは、また、磁気ディスク装置４６、ＦＤ（Ｆｌｅｘｉｂｌｅ　Ｄｉｓｋ）、光ディスク、ＣＤ（コンパクトディスク）、ＭＤ（ミニディスク）、ＤＶＤ（Ｄｉｇｉｔａｌ　Ｖｅｒｓａｔｉｌｅ　Ｄｉｓｋ）等のその他の記録媒体による記録装置を用いても構わない。
また、出力部は、ＣＲＴ表示装置４１、その他の表示装置、プリンタ装置８７等の出力装置を用いても構わない。
【００７０】
以上のように、上記実施の形態における楕円曲線演算装置は、楕円曲線上の複数の点の値とそれぞれ所定の桁数を有する２進数の複数の正整数とを入力する入力部と、
上記入力部により入力された複数の正整数の同位置の桁に１つでも１が割り当てられた桁の数の合計値を初期合計値として記憶する記憶部と、
上記複数の正整数の各正整数に対し、順に、上記複数の正整数の内１つを残して他の少なくとも１つの正整数の各桁に割り当てられた値を１桁ずつ所定の上限値までシフトするシフト部と、
上記シフト部によりシフトされた結果として上記複数の正整数の同位置の桁に１つでも１が割り当てられた桁の数の合計値と、上記記憶部に記憶された初期合計値と、上記シフト部によりシフトされた上記各正整数のシフト値とを用いて、上記シフト部によりシフトされた場合の楕円曲線上の複数の点のスカラー倍点の和を計算するための計算回数の合計値と上記シフト部によりシフトされない場合の楕円曲線上の複数の点のスカラー倍点の和を計算するための計算回数の合計値との差を上記各正整数の計算回数合計差分値としてそれぞれ計算し、上記各正整数の計算回数合計差分値を上記記憶部に記憶させる第１の計算部と、
上記第１の計算部により計算され上記記憶部に記憶された上記各正整数の計算回数合計差分値の内、最大となる計算回数合計差分値を選択し、選択された計算回数合計差分値を上記記憶部に記憶させる選択部と、
上記選択部により選択され上記記憶部に記憶された計算回数合計差分値が正の場合、上記選択部により選択され上記記憶部に記憶された計算回数合計差分値を計算させた複数の正整数の内上記シフト部によりシフトされた少なくとも１つの正整数と、複数の正整数の内上記シフト部によりシフトされていない他の正整数とを用いて、楕円曲線上の複数の点の値のスカラー倍の和を計算し、上記選択部により選択され上記記憶部に記憶された計算回数合計差分値が正でない場合、上記シフト部によりシフトされていない上記入力部により入力された複数の正整数を用いて、楕円曲線上の複数の点の値のスカラー倍の和を計算し、計算された楕円曲線上の複数の点の値のスカラー倍の和を上記記憶部に記憶させる第２の計算部と、
上記第２の計算部により計算され上記記憶部に記憶された楕円曲線上の複数の点の値のスカラー倍の和を出力する出力部と
を備えたことを特徴とする。
【００７１】
また、以上のように、上記第２の計算部は、楕円曲線上の複数の点の値のスカラー倍の和を計算するにあたり、上記シフト部によりシフトされた１つの正整数と数値２に上記１つの正整数のシフト値をべき乗した第１の補正値とを乗じ、さらに、上記１つの正整数が上記シフト部によりシフトされなかった場合に加算されていたであろう値の代わりに、上記乗じた値と上記シフト部によりシフトされた１つの正整数を計算に用いたことにより生じる第２の補正値とを楕円曲線上の複数の点の値のスカラー倍の和に加算することにより楕円曲線上の複数の点の値のスカラー倍の和を補正することを特徴とする。
【００７２】
また、以上のように、上記楕円曲線演算装置は、さらに、上記入力部により入力された複数の正整数に対し、所定のブロック数により複数の正整数の桁を複数のブロックに分割する分割部を備え、
上記記憶部は、上記分割部により分割された所定のブロック数毎に、複数の正整数の同位置の桁に１つでも１が割り当てられた桁の数の合計値を初期合計値として記憶し、
上記シフト部は、上記分割部により分割された所定のブロック数毎に、上記複数の正整数の各正整数に対し、順に、上記複数の正整数の内１つを残して他の少なくとも１つの正整数の各桁に割り当てられた値を１桁ずつ所定の上限値までシフトし、
上記第１の計算部は、上記分割部により分割された所定のブロック数毎に、上記シフト部によりシフトされた結果として上記複数の正整数の同位置の桁に１つでも１が割り当てられた桁の数の合計値と、上記記憶部に記憶された初期合計値と、上記シフト部によりシフトされた上記各正整数のシフト値とを用いて、上記シフト部によりシフトされた場合の楕円曲線上の複数の点のスカラー倍点の和を計算するための計算回数の合計値と上記シフト部によりシフトされない場合の楕円曲線上の複数の点のスカラー倍点の和を計算するための計算回数の合計値との差を上記各正整数の計算回数合計差分値としてそれぞれ計算し、上記各正整数の計算回数合計差分値を上記記憶部に記憶させ、
上記選択部は、上記分割部により分割された所定のブロック数毎に、上記第１の計算部により計算され上記記憶部に記憶された上記各正整数の計算回数合計差分値の内、最大となる計算回数合計差分値を選択し、選択された計算回数合計差分値を上記記憶部に記憶させ、
上記第２の計算部は、上記分割部により分割された所定のブロック数毎に、上記選択部により選択され上記記憶部に記憶された計算回数合計差分値が正の場合、上記選択部により選択され上記記憶部に記憶された計算回数合計差分値を計算させた複数の正整数の内、上記シフト部によりシフトされた少なくとも１つの正整数と複数の正整数の内、上記シフト部によりシフトされていない他の正整数とを用いて、楕円曲線上の複数の点の値のスカラー倍の和を計算し、上記選択部により選択され上記記憶部に記憶された計算回数合計差分値が正でない場合、上記シフト部によりシフトされていない上記入力部により入力された複数の正整数を用いて、楕円曲線上の複数の点の値のスカラー倍の和を計算し、所定のブロック数毎に計算された楕円曲線上の複数の点の値のスカラー倍の和の合計値を上記記憶部に記憶させ、
上記出力部は、上記第２の計算部により計算され上記記憶部に記憶された楕円曲線上の複数の点の値のスカラー倍の和の合計値を出力することを特徴とする。
【００７３】
また、以上のように、上記実施の形態における楕円曲線演算装置は、楕円曲線上の２点ＰとＱの値と、ｔビットの２つの正整数ｋとｌと、シフト長の上限値ｓ（０以上の整数）と、楕円曲線上の点加算の計算量Ａと、楕円曲線上の点２倍算の計算量Ｄとを入力する入力部と、
上記入力部により入力されたｋとｌとの連結ハミング重みＪＨＷ００＝ＪＨＷ（ｋ，ｌ）を計算し、記憶装置に記憶する第１の計算部と、
変数ｉを上記記憶装置に記憶するｉ記憶部と、
上記ｉ記憶部により記憶された変数ｉに初期値１を設定し、上記記憶装置に記憶するｉ初期値設定部と、
上記入力部により入力されたシフト長の上限値ｓと、上記記憶装置から読み出した上記ｉ初期値設定部により設定された変数ｉとを用いて、変数ｉがシフト長の上限値ｓに達するまで変数ｉに順次１を加えて、上記記憶装置に記憶するｉインクリメント部と、
上記ｉインクリメント部により上記記憶装置に変数ｉに順次１が加えられ記憶される度に、上記記憶装置から読み出した変数ｉと、上記入力部により入力された整数ｋと整数ｌとを用いて、整数ｋをｉビット右シフトした値（ｋ＞＞ｉ）と整数ｌとの連結ハミング重みＪＨＷｉ０＝ＪＨＷ（ｋ＞＞ｉ，ｌ）を計算し、上記記憶装置に記憶する第２の計算部と、
上記ｉインクリメント部により上記記憶装置に変数ｉに順次１が加えられ記憶される度に、上記記憶装置から読み出した変数ｉと、上記入力部により入力された整数ｋと整数ｌとを用いて、整数ｋと整数ｌをｉビット右シフトした値（ｌ＞＞ｉ）との連結ハミング重みＪＨＷ０ｉ＝ＪＨＷ（ｋ，ｌ＞＞ｉ）を計算し、上記記憶装置に記憶する第３の計算部と、
上記ｉインクリメント部により上記記憶装置に変数ｉに順次１が加えられ記憶される度に、上記記憶装置から読み出した変数ｉと上記第１の計算部により計算された連結ハミング重みＪＨＷ００と上記第２の計算部により計算された連結ハミング重みＪＨＷｉ０と、上記入力部により入力された楕円曲線上の点加算の計算量Ａと楕円曲線上の点２倍算の計算量Ｄとを用いて、計算量減少量Ｒｅｄｕｃｔｉｏｎｉ０＝（ＪＨＷ００−ＪＨＷｉ０）Ａ−ｉＤを計算し、上記記憶装置に記憶する第４の計算部と、
上記ｉインクリメント部により上記記憶装置に変数ｉに順次１が加えられ記憶される度に、上記記憶装置から読み出した変数ｉと上記第１の計算部により計算された連結ハミング重みＪＨＷ００と、上記第３の計算部により計算された連結ハミング重みＪＨＷ０ｉと、楕円曲線上の点加算の計算量Ａと、楕円曲線上の点２倍算の計算量Ｄとを読み出し、計算量減少量Ｒｅｄｕｃｔｉｏｎ０ｉ＝（ＪＨＷ００−ＪＨＷ０ｉ）Ａ−ｉＤを計算し、上記記憶装置に記憶する第５の計算部と、
上記第４の計算部により計算された計算量減少量Ｒｅｄｕｃｔｉｏｎｉ０と上記上記第５の計算部により計算された計算量減少量Ｒｅｄｕｃｔｉｏｎ０ｉとの内、計算量減少量の最大値を計算し、上記記憶装置に記憶する第６の計算部と、
上記第６の計算部により計算された計算量減少量の最大値が正の値である場合には上記最大値に対応する計算量減少量に用いられた整数ｋと整数ｌとの組合わせである（ｋ＞＞ｉ，ｌ）と（ｋ，ｌ＞＞ｉ）とのいずれか、上記第６の計算部により計算された計算量減少量の最大値が負の値である場合には上記入力部により入力された整数ｋと整数ｌとの組合わせである（ｋ，ｌ）を用いて、上記入力部により入力された楕円曲線上の２点ＰとＱの値のスカラー倍の和を計算し、上記記憶装置に記憶する第７の計算部と、
上記第７の計算部により計算された楕円曲線上の２点ＰとＱの値のスカラー倍の和を出力する出力部と
を備えたことを特徴とする。
【００７４】
また、以上のように、上記第７の計算部は、
計算に用いられた整数ｋと整数ｌとの組合わせが（ｋ，ｌ）の場合、ＰをＰｓに、ＱをＱｓに、ｋをｋ’に、ｌをｌ’に変換し、数値０の値を有する第１の補正値ｃと無限遠点値を有する第２の補正値Ｒとを設定し、上記記憶装置に記憶し、
計算に用いられた整数ｋと整数ｌとの組合わせであるが（ｋ＞＞ｉ，ｌ）の場合、２ｓ’ＰをＰｓに、ＱをＱｓに、ｋ＞＞ｉをｋ’に、ｌをｌ’に変換し、ｋと（２ｉ−１）とのビット毎の論理積の値ｋ∧（２ｉ−１）を有する第１の補正値ｃと楕円曲線上の点Ｐの値を有する第２の補正値Ｒとを設定し、上記記憶装置に記憶し、
計算に用いられた整数ｋと整数ｌとの組合わせが（ｋ，ｌ＞＞ｉ）の場合、ＰをＰｓに、２ｓ’ＱをＱｓに、ｋをｋ’に、ｌ＞＞ｉをｌ’に変換し、ｌと（２ｉ−１）とのビット毎の論理積の値ｌ∧（２ｉ−１）を有する第１の補正値ｃと楕円曲線上の点Ｑの値を有する第２の補正値Ｒとを設定し、上記記憶装置に記憶する変換設定部と、
変換設定部により変換されたＰｓとＱｓとｋ’とｌ’と、上記変換設定部により設定された第１の補正値ｃと第２の補正値Ｒとを用いて補正された楕円曲線上の２点ＰとＱの値のスカラー倍の和ｋ’Ｐｓ＋ｌ’Ｑｓ＋ｃＲを計算し、上記記憶装置に記憶するスカラー倍計算部と
を有することを特徴とする。
【００７５】
また、以上のように、上記入力部は、さらに、上記ｔビットを分割するためのブロック長ｂ（正整数）を入力し、
上記第１の計算部は、整数ｋと整数ｌの上位ｉ番目のｂビットブロック毎に、上記入力部により入力されたｋとｌとの連結ハミング重みＪＨＷ００＝ＪＨＷ（ｋ，ｌ）を計算し、記憶装置に記憶し、
上記ｉインクリメント部は、ｔをｂで除し、除した値の内の整数ｔ／ｂと、変数ｉとを用いて、変数ｉが整数ｔ／ｂに達するまで変数ｉに順次１を加えて、上記記憶装置に記憶し、
上記第２の計算部は、上記ｉインクリメント部により変数ｉに順次１を加えられる度に、整数ｋと整数ｌの上位ｉ番目のｂビットブロック毎に、上記記憶装置から読み出した変数ｉと、上記入力部により入力された整数ｋと整数ｌとを用いて、整数ｋをｉビット右シフトした値（ｋ＞＞ｉ）と整数ｌとの連結ハミング重みＪＨＷｉ０＝ＪＨＷ（ｋ＞＞ｉ，ｌ）を計算し、上記記憶装置に記憶し、
上記第３の計算部は、上記ｉインクリメント部により変数ｉに順次１を加えられる度に、整数ｋと整数ｌの上位ｉ番目のｂビットブロック毎に、上記記憶装置から読み出した変数ｉと、上記入力部により入力された整数ｋと整数ｌとを用いて、整数ｋと整数ｌをｉビット右シフトした値（ｌ＞＞ｉ）との連結ハミング重みＪＨＷ０ｉ＝ＪＨＷ（ｋ，ｌ＞＞ｉ）を計算し、上記記憶装置に記憶し、
上記第４の計算部は、上記ｉインクリメント部により変数ｉに順次１を加えられる度に、整数ｋと整数ｌの上位ｉ番目のｂビットブロック毎に、上記記憶装置から読み出した変数ｉと上記第１の計算部により計算された連結ハミング重みＪＨＷ００と上記第２の計算部により計算された連結ハミング重みＪＨＷｉ０と、上記入力部により入力された楕円曲線上の点加算の計算量Ａと楕円曲線上の点２倍算の計算量Ｄとを用いて、計算量減少量Ｒｅｄｕｃｔｉｏｎｉ０＝（ＪＨＷ００−ＪＨＷｉ０）Ａ−ｉＤを計算し、上記記憶装置に記憶し、
上記第５の計算部は、上記ｉインクリメント部により変数ｉに順次１を加えられる度に、整数ｋと整数ｌの上位ｉ番目のｂビットブロック毎に、上記記憶装置から読み出した変数ｉと上記第１の計算部により計算された連結ハミング重みＪＨＷ００と、上記第３の計算部により計算された連結ハミング重みＪＨＷ０ｉと、楕円曲線上の点加算の計算量Ａと、楕円曲線上の点２倍算の計算量Ｄとを読み出し、計算量減少量Ｒｅｄｕｃｔｉｏｎ０ｉ＝（ＪＨＷ００−ＪＨＷ０ｉ）Ａ−ｉＤを計算し、上記記憶装置に記憶し、
上記第６の計算部は、上記ｉインクリメント部により変数ｉに順次１を加えられる度に、整数ｋと整数ｌの上位ｉ番目のｂビットブロック毎に、上記第４の計算部により計算された計算量減少量Ｒｅｄｕｃｔｉｏｎｉ０と上記上記第５の計算部により計算された計算量減少量Ｒｅｄｕｃｔｉｏｎ０ｉとの内、計算量減少量の最大値を計算し、上記記憶装置に記憶し、
上記第７の計算部は、上記ｉインクリメント部により変数ｉに順次１を加えられる度に、整数ｋと整数ｌの上位ｉ番目のｂビットブロック毎に、上記第６の計算部により計算された計算量減少量の最大値が正の値である場合には上記最大値に対応する計算量減少量に用いられた整数ｋと整数ｌとの組合わせである（ｋ＞＞ｉ，ｌ）と（ｋ，ｌ＞＞ｉ）とのいずれかを、上記第６の計算部により計算された計算量減少量の最大値が負の値である場合には上記入力部により入力された整数ｋと整数ｌとの組合わせである（ｋ，ｌ）を用いて、上記入力部により入力された楕円曲線上の２点ＰとＱの値のスカラー倍の和を計算し、ｂビットブロック毎に計算された楕円曲線上の２点ＰとＱの値のスカラー倍の和の合計を上記記憶装置に記憶することを特徴とする。
【００７６】
また、以上のように、上記実施の形態における楕円曲線演算装置は、楕円曲線上の複数の点Ｐ１、Ｐ２、…、Ｐｎの値と、ｔビットの複数の正整数ｋ１、ｋ２、…、ｋｎと、シフト長の上限値ｓ（０以上の整数）と、楕円曲線上の点加算の計算量Ａと、楕円曲線上の点２倍算の計算量Ｄとを入力する入力部と、
上記入力部により入力されたｋ１、ｋ２、…、ｋｎの連結ハミング重みＪＨＷ０…０（ｎ個）＝ＪＨＷ（ｋ１，ｋ２，…，ｋｎ）を計算し、記憶装置に記憶する初期計算部と、
変数ｉを上記記憶装置に記憶するｉ記憶部と、
上記ｉ記憶部により記憶された変数ｉに初期値１を設定し、上記記憶装置に記憶するｉ初期値設定部と、
上記入力部により入力されたシフト長の上限値ｓと、上記記憶装置から読み出した上記ｉ初期値設定部により設定された変数ｉとを用いて、変数ｉがシフト長の上限値ｓに達するまで変数ｉに順次１を加えて、上記記憶装置に記憶するｉインクリメント部と、
上記ｉインクリメント部により上記記憶装置に変数ｉに順次１が加えられ記憶される度に、上記記憶装置から読み出した変数ｉと、上記入力部により入力された整数ｋ１、ｋ２、…、ｋｎを用いて、整数ｋ１、ｋ２、…、ｋｎ各値の内少なくとも１つを最大ｉビット右シフトした値と右シフトしない他の整数ｋ１、ｋ２、…、ｋｎとの連結ハミング重みＪＨＷｉを順に計算し、それぞれ上記記憶装置に記憶する連結ハミング重み計算部と、
上記ｉインクリメント部により上記記憶装置に変数ｉに順次１が加えられ記憶される度に、上記記憶装置から読み出した変数ｉと上記初期計算部により計算された連結ハミング重みＪＨＷ０…０（ｎ個）と、上記連結ハミング重み計算部により計算された連結ハミング重みＪＨＷｉと、楕円曲線上の点加算の計算量Ａと、楕円曲線上の点２倍算の計算量Ｄとを読み出し、さらに、上記整数ｋ１、ｋ２、…、ｋｎ各値の内、最大ｉビット右シフトした少なくとも１つの整数のシフト値の合計値Ｚを用いて、計算量減少量Ｒｅｄｕｃｔｉｏｎｉ＝（ＪＨＷ０…０（ｎ個）−ＪＨＷｉ）Ａ−ＺＤを順に計算し、上記記憶装置に記憶する計算量減少量計算部と、
上記計算量減少量計算部により順に計算された計算量減少量Ｒｅｄｕｃｔｉｏｎｉの内、計算量減少量の最大値を計算し、上記記憶装置に記憶する最大値計算部と、
上記最大値計算部により計算された計算量減少量の最大値が正の値である場合には上記最大値に対応する計算量減少量に用いられた最大ｉビット右シフトした少なくとも１つの整数と右シフトしない他の整数ｋ１、ｋ２、…、ｋｎとを、上記最大値計算部により計算された計算量減少量の最大値が正の値でない場合には上記入力部により入力された整数ｋ１、ｋ２、…、ｋｎを用いて、上記入力部により入力された楕円曲線上の複数の点Ｐ１、Ｐ２、…、Ｐｎの値のスカラー倍の和ｋ１Ｐ１＋ｋ２Ｐ２＋，…，＋ｋｎＰｎを計算し、上記記憶装置に記憶するスカラー倍計算部と、
上記スカラー倍計算部により計算された楕円曲線上の複数の点の値のスカラー倍の和を出力する出力部と
を備えたことを特徴とする。
【００７７】
また、以上のように、上記実施の形態における変換装置は、ｔビットの２つの正整数ｋとｌと、シフト長の上限値ｓ（０以上の整数）と、楕円曲線上の点加算の計算量Ａと、楕円曲線上の点２倍算の計算量Ｄとを入力する入力部と、
上記入力部により入力されたｋとｌとの連結ハミング重みＪＨＷ００＝ＪＨＷ（ｋ，ｌ）を計算し、記憶装置に記憶する第１の計算部と、
変数ｉを上記記憶装置に記憶するｉ記憶部と、
上記ｉ記憶部により記憶された変数ｉに初期値１を設定し、上記記憶装置に記憶するｉ初期値設定部と、
上記入力部により入力されたシフト長の上限値ｓと、上記記憶装置から読み出した上記ｉ初期値設定部により設定された変数ｉとを用いて、変数ｉがシフト長の上限値ｓに達するまで変数ｉに順次１を加えて、上記記憶装置に記憶するｉインクリメント部と、
上記ｉインクリメント部により上記記憶装置に変数ｉに順次１が加えられ記憶される度に、上記記憶装置から読み出した変数ｉと、上記入力部により入力された整数ｋと整数ｌとを用いて、整数ｋをｉビット右シフトした値（ｋ＞＞ｉ）と整数ｌとの連結ハミング重みＪＨＷｉ０＝ＪＨＷ（ｋ＞＞ｉ，ｌ）を計算し、上記記憶装置に記憶する第２の計算部と、
上記ｉインクリメント部により上記記憶装置に変数ｉに順次１が加えられ記憶される度に、上記記憶装置から読み出した変数ｉと、上記入力部により入力された整数ｋと整数ｌとを用いて、整数ｋと整数ｌをｉビット右シフトした値（ｌ＞＞ｉ）との連結ハミング重みＪＨＷ０ｉ＝ＪＨＷ（ｋ，ｌ＞＞ｉ）を計算し、上記記憶装置に記憶する第３の計算部と、
上記ｉインクリメント部により上記記憶装置に変数ｉに順次１が加えられ記憶される度に、上記記憶装置から読み出した変数ｉと上記第１の計算部により計算された連結ハミング重みＪＨＷ００と上記第２の計算部により計算された連結ハミング重みＪＨＷｉ０と、上記入力部により入力された楕円曲線上の点加算の計算量Ａと楕円曲線上の点２倍算の計算量Ｄとを用いて、計算量減少量Ｒｅｄｕｃｔｉｏｎｉ０＝（ＪＨＷ００−ＪＨＷｉ０）Ａ−ｉＤを計算し、上記記憶装置に記憶する第４の計算部と、
上記ｉインクリメント部により上記記憶装置に変数ｉに順次１が加えられ記憶される度に、上記記憶装置から読み出した変数ｉと上記第１の計算部により計算された連結ハミング重みＪＨＷ００と、上記第３の計算部により計算された連結ハミング重みＪＨＷ０ｉと、楕円曲線上の点加算の計算量Ａと、楕円曲線上の点２倍算の計算量Ｄとを読み出し、計算量減少量Ｒｅｄｕｃｔｉｏｎ０ｉ＝（ＪＨＷ００−ＪＨＷ０ｉ）Ａ−ｉＤを計算し、上記記憶装置に記憶する第５の計算部と、
上記第４の計算部により計算された計算量減少量Ｒｅｄｕｃｔｉｏｎｉ０と上記上記第５の計算部により計算された計算量減少量Ｒｅｄｕｃｔｉｏｎ０ｉとの内、計算量減少量の最大値を計算し、上記記憶装置に記憶する第６の計算部と、
上記第６の計算部により計算された計算量減少量の最大値が正の値である場合には上記最大値に対応する計算量減少量に用いられた整数ｋと整数ｌとの組合わせである（ｋ＞＞ｉ，ｌ）と（ｋ，ｌ＞＞ｉ）とのいずれかを、上記第６の計算部により計算された計算量減少量の最大値が負の値である場合には上記入力部により入力された整数ｋと整数ｌとの組合わせである（ｋ，ｌ）を最適な整数ｋと整数ｌとの組合わせとして出力する出力部と
を備えたことを特徴とする。
【００７８】
また、以上のように、上記実施の形態における楕円曲線演算方法は、楕円曲線上の複数の点の値とそれぞれ所定の桁数を有する２進数の複数の正整数とを入力する入力工程と、
上記入力工程により入力された複数の正整数の同位置の桁に１つでも１が割り当てられた桁の数の合計値を初期合計値として記憶装置に記憶する記憶工程と、
上記複数の正整数の各正整数に対し、順に、上記複数の正整数の内１つを残して他の少なくとも１つの正整数の各桁に割り当てられた値を１桁ずつ所定の上限値までシフトするシフト工程と、
上記シフト工程によりシフトされた結果として上記複数の正整数の同位置の桁に１つでも１が割り当てられた桁の数の合計値と、上記記憶工程に記憶された初期合計値と、上記シフト工程によりシフトされた上記各正整数のシフト値とを用いて、上記シフト工程によりシフトされた場合の楕円曲線上の複数の点のスカラー倍点の和を計算するための計算回数の合計値と上記シフト工程によりシフトされない場合の楕円曲線上の複数の点のスカラー倍点の和を計算するための計算回数の合計値との差を上記各正整数の計算回数合計差分値としてそれぞれ計算し、上記各正整数の計算回数合計差分値を上記記憶装置に記憶させる第１の計算工程と、
上記第１の計算工程により計算され上記記憶装置に記憶された上記各正整数の計算回数合計差分値の内、最大となる計算回数合計差分値を選択し、選択された計算回数合計差分値を上記記憶装置に記憶させる選択工程と、
上記選択工程により選択され上記記憶装置に記憶された計算回数合計差分値が正の場合、上記選択工程により選択され上記記憶装置に記憶された計算回数合計差分値を計算させた複数の正整数の内上記シフト工程よりシフトされた少なくとも１つの正整数と、複数の正整数の内上記シフト工程によりシフトされていない他の正整数とを用いて、楕円曲線上の複数の点の値のスカラー倍の和を計算し、上記選択工程により選択され上記記憶装置に記憶された計算回数合計差分値が正でない場合、上記シフト工程によりシフトされていない上記入力工程により入力された複数の正整数を用いて、楕円曲線上の複数の点の値のスカラー倍の和を計算し、計算された楕円曲線上の複数の点の値のスカラー倍の和を上記記憶装置に記憶させる第２の計算工程と、
上記第２の計算工程により計算され上記記憶装置に記憶された楕円曲線上の複数の点の値のスカラー倍の和を出力する出力工程と
を備えたことを特徴とする。
【００７９】
また、以上のように、上記実施の形態における楕円曲線演算方法は、楕円曲線上の２点ＰとＱの値と、ｔビットの２つの正整数ｋとｌと、シフト長の上限値ｓ（０以上の整数）と、楕円曲線上の点加算の計算量Ａと、楕円曲線上の点２倍算の計算量Ｄとを入力する入力工程と、
上記入力工程により入力されたｋとｌとの連結ハミング重みＪＨＷ００＝ＪＨＷ（ｋ，ｌ）を計算し、記憶装置に記憶する第１の計算工程と、
変数ｉを上記記憶装置に記憶するｉ記憶工程と、
上記ｉ記憶工程により記憶された変数ｉに初期値１を設定し、上記記憶装置に記憶するｉ初期値設定工程と、
上記入力工程により入力されたシフト長の上限値ｓと、上記記憶装置から読み出した上記ｉ初期値設定工程により設定された変数ｉとを用いて、変数ｉがシフト長の上限値ｓに達するまで変数ｉに順次１を加えて、上記記憶装置に記憶するｉインクリメント工程と、
上記ｉインクリメント工程により上記記憶装置に変数ｉに順次１が加えられ記憶される度に、上記記憶装置から読み出した変数ｉと、上記入力工程により入力された整数ｋと整数ｌとを用いて、整数ｋをｉビット右シフトした値（ｋ＞＞ｉ）と整数ｌとの連結ハミング重みＪＨＷｉ０＝ＪＨＷ（ｋ＞＞ｉ，ｌ）を計算し、上記記憶装置に記憶する第２の計算工程と、
上記ｉインクリメント工程により上記記憶装置に変数ｉに順次１が加えられ記憶される度に、上記記憶装置から読み出した変数ｉと、上記入力工程により入力された整数ｋと整数ｌとを用いて、整数ｋと整数ｌをｉビット右シフトした値（ｌ＞＞ｉ）との連結ハミング重みＪＨＷ０ｉ＝ＪＨＷ（ｋ，ｌ＞＞ｉ）を計算し、上記記憶装置に記憶する第３の計算工程と、
上記ｉインクリメント工程により上記記憶装置に変数ｉに順次１が加えられ記憶される度に、上記記憶装置から読み出した変数ｉと上記第１の計算工程により計算された連結ハミング重みＪＨＷ００と上記第２の計算工程により計算された連結ハミング重みＪＨＷｉ０と、上記入力工程により入力された楕円曲線上の点加算の計算量Ａと楕円曲線上の点２倍算の計算量Ｄとを用いて、計算量減少量Ｒｅｄｕｃｔｉｏｎｉ０＝（ＪＨＷ００−ＪＨＷｉ０）Ａ−ｉＤを計算し、上記記憶装置に記憶する第４の計算工程と、
上記ｉインクリメント工程により上記記憶装置に変数ｉに順次１が加えられ記憶される度に、上記記憶装置から読み出した変数ｉと上記第１の計算工程により計算された連結ハミング重みＪＨＷ００と、上記第３の計算工程により計算された連結ハミング重みＪＨＷ０ｉと、楕円曲線上の点加算の計算量Ａと、楕円曲線上の点２倍算の計算量Ｄとを読み出し、計算量減少量Ｒｅｄｕｃｔｉｏｎ０ｉ＝（ＪＨＷ００−ＪＨＷ０ｉ）Ａ−ｉＤを計算し、上記記憶装置に記憶する第５の計算工程と、
上記第４の計算工程により計算された計算量減少量Ｒｅｄｕｃｔｉｏｎｉ０と上記上記第５の計算工程により計算された計算量減少量Ｒｅｄｕｃｔｉｏｎ０ｉとの内、計算量減少量の最大値を計算し、上記記憶装置に記憶する第６の計算工程と、
上記第６の計算工程により計算された計算量減少量の最大値が正の値である場合には上記最大値に対応する計算量減少量に用いられた整数ｋと整数ｌとの組合わせである（ｋ＞＞ｉ，ｌ）と（ｋ，ｌ＞＞ｉ）とのいずれかを、上記第６の計算工程により計算された計算量減少量の最大値が負の値である場合には上記入力工程により入力された整数ｋと整数ｌとの組合わせである（ｋ，ｌ）を用いて、上記入力工程により入力された楕円曲線上の２点ＰとＱの値のスカラー倍の和を計算し、上記記憶装置に記憶する第７の計算工程と、
上記第７の計算工程により計算された楕円曲線上の２点ＰとＱの値のスカラー倍の和を出力する出力工程と
を備えたことを特徴とする。
【００８０】
また、以上のように、上記実施の形態におけるプログラムは、楕円曲線上の複数の点の値とそれぞれ所定の桁数を有する２進数の複数の正整数とを入力する入力処理と、
上記入力処理により入力された複数の正整数の同位置の桁に１つでも１が割り当てられた桁の数の合計値を初期合計値として記憶装置に記憶する記憶処理と、
上記複数の正整数の各正整数に対し、順に、上記複数の正整数の内１つを残して他の少なくとも１つの正整数の各桁に割り当てられた値を１桁ずつ所定の上限値までシフトするシフト処理と、
上記シフト処理によりシフトされた結果として上記複数の正整数の同位置の桁に１つでも１が割り当てられた桁の数の合計値と、上記記憶処理に記憶された初期合計値と、上記シフト処理によりシフトされた上記各正整数のシフト値とを用いて、上記シフト処理によりシフトされた場合の楕円曲線上の複数の点のスカラー倍点の和を計算するための計算回数の合計値と上記シフト処理によりシフトされない場合の楕円曲線上の複数の点のスカラー倍点の和を計算するための計算回数の合計値との差を上記各正整数の計算回数合計差分値としてそれぞれ計算し、上記各正整数の計算回数合計差分値を上記記憶装置に記憶させる第１の計算処理と、
上記第１の計算処理により計算され上記記憶装置に記憶された上記各正整数の計算回数合計差分値の内、最大となる計算回数合計差分値を選択し、選択された計算回数合計差分値を上記記憶装置に記憶させる選択処理と、
上記選択処理により選択され上記記憶装置に記憶された計算回数合計差分値が正の場合、上記選択処理により選択され上記記憶装置に記憶された計算回数合計差分値を計算させた複数の正整数の内上記シフト処理よりシフトされた少なくとも１つの正整数と、複数の正整数の内上記シフト処理によりシフトされていない他の正整数とを用いて、楕円曲線上の複数の点の値のスカラー倍の和を計算し、上記選択処理により選択され上記記憶装置に記憶された計算回数合計差分値が正でない場合、上記シフト処理によりシフトされていない上記入力処理により入力された複数の正整数を用いて、楕円曲線上の複数の点の値のスカラー倍の和を計算し、計算された楕円曲線上の複数の点の値のスカラー倍の和を上記記憶装置に記憶させる第２の計算処理と、
上記第２の計算処理により計算され上記記憶装置に記憶された楕円曲線上の複数の点の値のスカラー倍の和を出力する出力処理と
をコンピュータに実行させるためのプログラムであることを特徴とする。
【００８１】
また、以上のように、上記実施の形態におけるプログラムは、楕円曲線上の２点ＰとＱの値と、ｔビットの２つの正整数ｋとｌと、シフト長の上限値ｓ（０以上の整数）と、楕円曲線上の点加算の計算量Ａと、楕円曲線上の点２倍算の計算量Ｄとを入力する入力処理と、
上記入力処理により入力されたｋとｌとの連結ハミング重みＪＨＷ００＝ＪＨＷ（ｋ，ｌ）を計算し、記憶装置に記憶する第１の計算処理と、
変数ｉを上記記憶装置に記憶するｉ記憶処理と、
上記ｉ記憶処理により記憶された変数ｉに初期値１を設定し、上記記憶装置に記憶するｉ初期値設定処理と、
上記入力処理により入力されたシフト長の上限値ｓと、上記記憶装置から読み出した上記ｉ初期値設定処理により設定された変数ｉとを用いて、変数ｉがシフト長の上限値ｓに達するまで変数ｉに順次１を加えて、上記記憶装置に記憶するｉインクリメント処理と、
上記ｉインクリメント処理により上記記憶装置に変数ｉに順次１が加えられ記憶される度に、上記記憶装置から読み出した変数ｉと、上記入力処理により入力された整数ｋと整数ｌとを用いて、整数ｋをｉビット右シフトした値（ｋ＞＞ｉ）と整数ｌとの連結ハミング重みＪＨＷｉ０＝ＪＨＷ（ｋ＞＞ｉ，ｌ）を計算し、上記記憶装置に記憶する第２の計算処理と、
上記ｉインクリメント処理により上記記憶装置に変数ｉに順次１が加えられ記憶される度に、上記記憶装置から読み出した変数ｉと、上記入力処理により入力された整数ｋと整数ｌとを用いて、整数ｋと整数ｌをｉビット右シフトした値（ｌ＞＞ｉ）との連結ハミング重みＪＨＷ０ｉ＝ＪＨＷ（ｋ，ｌ＞＞ｉ）を計算し、上記記憶装置に記憶する第３の計算処理と、
上記ｉインクリメント処理により上記記憶装置に変数ｉに順次１が加えられ記憶される度に、上記記憶装置から読み出した変数ｉと上記第１の計算処理により計算された連結ハミング重みＪＨＷ００と上記第２の計算処理により計算された連結ハミング重みＪＨＷｉ０と、上記入力処理により入力された楕円曲線上の点加算の計算量Ａと楕円曲線上の点２倍算の計算量Ｄとを用いて、計算量減少量Ｒｅｄｕｃｔｉｏｎｉ０＝（ＪＨＷ００−ＪＨＷｉ０）Ａ−ｉＤを計算し、上記記憶装置に記憶する第４の計算処理と、
上記ｉインクリメント処理により上記記憶装置に変数ｉに順次１が加えられ記憶される度に、上記記憶装置から読み出した変数ｉと上記第１の計算処理により計算された連結ハミング重みＪＨＷ００と、上記第３の計算処理により計算された連結ハミング重みＪＨＷ０ｉと、楕円曲線上の点加算の計算量Ａと、楕円曲線上の点２倍算の計算量Ｄとを読み出し、計算量減少量Ｒｅｄｕｃｔｉｏｎ０ｉ＝（ＪＨＷ００−ＪＨＷ０ｉ）Ａ−ｉＤを計算し、上記記憶装置に記憶する第５の計算処理と、
上記第４の計算処理により計算された計算量減少量Ｒｅｄｕｃｔｉｏｎｉ０と上記上記第５の計算処理により計算された計算量減少量Ｒｅｄｕｃｔｉｏｎ０ｉとの内、計算量減少量の最大値を計算し、上記記憶装置に記憶する第６の計算処理と、
上記第６の計算処理により計算された計算量減少量の最大値が正の値である場合には上記最大値に対応する計算量減少量に用いられた整数ｋと整数ｌとの組合わせである（ｋ＞＞ｉ，ｌ）と（ｋ，ｌ＞＞ｉ）とのいずれかを、上記第６の計算処理により計算された計算量減少量の最大値が負の値である場合には上記入力処理により入力された整数ｋと整数ｌとの組合わせである（ｋ，ｌ）を用いて、上記入力処理により入力された楕円曲線上の２点ＰとＱの値のスカラー倍の和を計算し、上記記憶装置に記憶する第７の計算処理と、
上記第７の計算処理により計算された楕円曲線上の２点ＰとＱの値のスカラー倍の和を出力する出力処理と
をコンピュータに実行させるためのプログラムであることを特徴とする。
【００８２】
また、以上のように、上記実施の形態におけるコンピュータ読み取り可能な記録媒体は、楕円曲線上の複数の点の値とそれぞれ所定の桁数を有する２進数の複数の正整数とを入力する入力処理と、
上記入力処理により入力された複数の正整数の同位置の桁に１つでも１が割り当てられた桁の数の合計値を初期合計値として記憶装置に記憶する記憶処理と、
上記複数の正整数の各正整数に対し、順に、上記複数の正整数の内１つを残して他の少なくとも１つの正整数の各桁に割り当てられた値を１桁ずつ所定の上限値までシフトするシフト処理と、
上記シフト処理によりシフトされた結果として上記複数の正整数の同位置の桁に１つでも１が割り当てられた桁の数の合計値と、上記記憶処理に記憶された初期合計値と、上記シフト処理によりシフトされた上記各正整数のシフト値とを用いて、上記シフト処理によりシフトされた場合の楕円曲線上の複数の点のスカラー倍点の和を計算するための計算回数の合計値と上記シフト処理によりシフトされない場合の楕円曲線上の複数の点のスカラー倍点の和を計算するための計算回数の合計値との差を上記各正整数の計算回数合計差分値としてそれぞれ計算し、上記各正整数の計算回数合計差分値を上記記憶装置に記憶させる第１の計算処理と、
上記第１の計算処理により計算され上記記憶装置に記憶された上記各正整数の計算回数合計差分値の内、最大となる計算回数合計差分値を選択し、選択された計算回数合計差分値を上記記憶装置に記憶させる選択処理と、
上記選択処理により選択され上記記憶装置に記憶された計算回数合計差分値が正の場合、上記選択処理により選択され上記記憶装置に記憶された計算回数合計差分値を計算させた複数の正整数の内上記シフト処理よりシフトされた少なくとも１つの正整数と、複数の正整数の内上記シフト処理によりシフトされていない他の正整数とを用いて、楕円曲線上の複数の点の値のスカラー倍の和を計算し、上記選択処理により選択され上記記憶装置に記憶された計算回数合計差分値が正でない場合、上記シフト処理によりシフトされていない上記入力処理により入力された複数の正整数を用いて、楕円曲線上の複数の点の値のスカラー倍の和を計算し、計算された楕円曲線上の複数の点の値のスカラー倍の和を上記記憶装置に記憶させる第２の計算処理と、
上記第２の計算処理により計算され上記記憶装置に記憶された楕円曲線上の複数の点の値のスカラー倍の和を出力する出力処理と
をコンピュータに実行させるためのプログラムを記録したことを特徴とする。
【００８３】
また、以上のように、上記実施の形態におけるコンピュータ読み取り可能な記録媒体は、楕円曲線上の２点ＰとＱの値と、ｔビットの２つの正整数ｋとｌと、シフト長の上限値ｓ（０以上の整数）と、楕円曲線上の点加算の計算量Ａと、楕円曲線上の点２倍算の計算量Ｄとを入力する入力処理と、
上記入力処理により入力されたｋとｌとの連結ハミング重みＪＨＷ００＝ＪＨＷ（ｋ，ｌ）を計算し、記憶装置に記憶する第１の計算処理と、
変数ｉを上記記憶装置に記憶するｉ記憶処理と、
上記ｉ記憶処理により記憶された変数ｉに初期値１を設定し、上記記憶装置に記憶するｉ初期値設定処理と、
上記入力処理により入力されたシフト長の上限値ｓと、上記記憶装置から読み出した上記ｉ初期値設定処理により設定された変数ｉとを用いて、変数ｉがシフト長の上限値ｓに達するまで変数ｉに順次１を加えて、上記記憶装置に記憶するｉインクリメント処理と、
上記ｉインクリメント処理により上記記憶装置に変数ｉに順次１が加えられ記憶される度に、上記記憶装置から読み出した変数ｉと、上記入力処理により入力された整数ｋと整数ｌとを用いて、整数ｋをｉビット右シフトした値（ｋ＞＞ｉ）と整数ｌとの連結ハミング重みＪＨＷｉ０＝ＪＨＷ（ｋ＞＞ｉ，ｌ）を計算し、上記記憶装置に記憶する第２の計算処理と、
上記ｉインクリメント処理により上記記憶装置に変数ｉに順次１が加えられ記憶される度に、上記記憶装置から読み出した変数ｉと、上記入力処理により入力された整数ｋと整数ｌとを用いて、整数ｋと整数ｌをｉビット右シフトした値（ｌ＞＞ｉ）との連結ハミング重みＪＨＷ０ｉ＝ＪＨＷ（ｋ，ｌ＞＞ｉ）を計算し、上記記憶装置に記憶する第３の計算処理と、
上記ｉインクリメント処理により上記記憶装置に変数ｉに順次１が加えられ記憶される度に、上記記憶装置から読み出した変数ｉと上記第１の計算処理により計算された連結ハミング重みＪＨＷ００と上記第２の計算処理により計算された連結ハミング重みＪＨＷｉ０と、上記入力処理により入力された楕円曲線上の点加算の計算量Ａと楕円曲線上の点２倍算の計算量Ｄとを用いて、計算量減少量Ｒｅｄｕｃｔｉｏｎｉ０＝（ＪＨＷ００−ＪＨＷｉ０）Ａ−ｉＤを計算し、上記記憶装置に記憶する第４の計算処理と、
上記ｉインクリメント処理により上記記憶装置に変数ｉに順次１が加えられ記憶される度に、上記記憶装置から読み出した変数ｉと上記第１の計算処理により計算された連結ハミング重みＪＨＷ００と、上記第３の計算処理により計算された連結ハミング重みＪＨＷ０ｉと、楕円曲線上の点加算の計算量Ａと、楕円曲線上の点２倍算の計算量Ｄとを読み出し、計算量減少量Ｒｅｄｕｃｔｉｏｎ０ｉ＝（ＪＨＷ００−ＪＨＷ０ｉ）Ａ−ｉＤを計算し、上記記憶装置に記憶する第５の計算処理と、
上記第４の計算処理により計算された計算量減少量Ｒｅｄｕｃｔｉｏｎｉ０と上記上記第５の計算処理により計算された計算量減少量Ｒｅｄｕｃｔｉｏｎ０ｉとの内、計算量減少量の最大値を計算し、上記記憶装置に記憶する第６の計算処理と、
上記第６の計算処理により計算された計算量減少量の最大値が正の値である場合には上記最大値に対応する計算量減少量に用いられた整数ｋと整数ｌとの組合わせである（ｋ＞＞ｉ，ｌ）と（ｋ，ｌ＞＞ｉ）とのいずれかを、上記第６の計算処理により計算された計算量減少量の最大値が負の値である場合には上記入力処理により入力された整数ｋと整数ｌとの組合わせである（ｋ，ｌ）を用いて、上記入力処理により入力された楕円曲線上の２点ＰとＱの値のスカラー倍の和を計算し、上記記憶装置に記憶する第７の計算処理と、
上記第７の計算処理により計算された楕円曲線上の２点ＰとＱの値のスカラー倍の和を出力する出力処理と
をコンピュータに実行させるためのプログラムを記録したことを特徴とする。
【００８４】
【発明の効果】
本発明によれば、楕円曲線演算を高速に行うためのスカラー変換を行なうことができる。
【００８５】
本発明によれば、楕円曲線演算を高速に行うことができる。
また、上記演算方法を利用することにより、楕円曲線を用いた暗号化やディジタル署名を高速に行うことができる。
【００８６】
本発明によれば、桁数の多いスカラーであっても楕円曲線演算を高速に行うことができる。
【図面の簡単な説明】
【図１】実施の形態１におけるコンピュータ装置の外観を示す図である。
【図２】実施の形態１におけるコンピュータ装置のハードウェア構成図である。
【図３】実施の形態１における変換装置の構成を示すブロック図である。
【図４】実施の形態１における整数の変換方法を示したフローチャートである。
【図５】実施の形態２における楕円曲線演算装置の構成を示すブロック図である。
【図６】実施の形態２による楕円同時スカラー倍演算方法を示したフローチャートである。
【図７】実施の形態３における楕円曲線演算装置の構成を示すブロック図である。
【図８】
【図９】楕円曲線上の点の同時スカラー倍演算、ｋＰ＋ｌＱを演算する従来の方法を示すフローチャートである。
【符号の説明】
３０　インターネット、３３　システムユニット、３７　ＣＰＵ、３８　バス、３９　ＲＯＭ、４０　ＲＡＭ、４１　ＣＲＴ表示装置、４２　Ｋ／Ｂ、４３　マウス、４４　通信ボード、４５　ＦＤＤ、４６　磁気ディスク装置、８６　ＣＤＤ、８７　プリンタ装置、８８　スキャナ装置、１００　ＰＣ、４００　変換装置、４０１　入力部、４０２　記憶部、４０３　計算部、４０４　計算部、４０５　最大値計算部、４０６　出力部、４０７　制御部４０７、５００　楕円同時スカラー倍演算装置、５０１　入力部、５０２　変換部、５０３　計算部、５０４　計算部、５０５　計算部、５０６　出力部、５０７　記憶部、５０８　点加算部、５０９　点２倍算部、５１０　制御部、５２０　計算部、５３０　スカラー倍計算部、６００　楕円同時スカラー倍演算装置、６０１　入力部、６０２計算部、６０３　計算部、６０４　出力部、６０５　記憶部、６０６　スカラー倍演算部、６０７　制御部、６１１　シフト部、６１２　分割部、６１４　選択部、６２０　計算部、６２１　計算部、６２２　計算部、６２３　計算部、６２４　計算部、６３０　計算部、６３１　ｉ初期値設定部、６３２　ｉインクリメント部。
【図１】
2004117627.tif 000013
【図２】
2004117627.tif 000014
【図３】
2004117627.tif 000015
【図４】
2004117627.tif 000016
【図５】
2004117627.tif 000017
【図６】
2004117627.tif 000018
【図７】
2004117627.tif 000019
【図８】
2004117627.tif 000020
【図９】
2004117627.tif 000021