(57)【特許請求の範囲】
【請求項１】
楕円曲線上の点をスカラーＫでスカラー倍するために用いる上記スカラーＫを、自己準同形写像である特殊準同型写像φと分割値ｋ１とｋ２とを用いてスカラーＫ＝ｋ１＋ｋ２φとし、２次元の整数係数の線形空間から１次元の線形空間への写像ｆをｆ：（ｉ，ｊ）→ｉ＋λｊ（ｍｏｄ  ｎ）（但し、ｍｏｄ  ｎは、ｉ＋λｊをｎで割った余りを意味する）とし、上記写像ｆが０になる２次元の部分空間をＫｅｒ  ｆとし、Ｋｅｒ  ｆの基底ベクトルであって基底ベクトルの成分の絶対値が最も小さくなるもの（ただし、絶対値がゼロになるものを除く）をベクトルＶ１とベクトルＶ２とし、ベクトルＶ１及びベクトルＶ２を使用して、ｆ（ｕ）＝Ｋとなる小ベクトルｕ＝（ｋ１，ｋ２）を計算すると、小ベクトルｕが上記スカラーＫのＫ＝ｋ１＋ｋ２φのｋ１，ｋ２を与えるベクトルＶ１とベクトルＶ２とを演算するベクトル演算装置において、
拡張ユークリッド互除法を用いて上記ベクトルＶ１を演算するベクトルＶ１演算部と、
上記拡張ユークリッド互除法を用いて、複数の整数値を有する複数の集合Ａｈを演算し、演算された複数の整数値を有する複数の集合Ａｈに含まれる複数の整数値αを用いて上記ベクトルＶ２を演算するベクトルＶ２演算部と、
上記ベクトルＶ１演算部により演算されたベクトルＶ１と上記ベクトルＶ２演算部により演算されたベクトルＶ２とを出力するベクトル出力部と
を備えたことを特徴とするベクトル演算装置。
【請求項２】
上記ベクトルＶ２演算部は、
上記特殊準同型写像φがφ２＋ｒ・φ＋ｓ＝０を満たす時、φが満たす最小多項式（Ｘ２＋ｒ・Ｘ＋ｓ）の式の係数として定まる値ｒ、ｓを用いて定まる定数ｋ＊を用いた整数値ｈ（ｈは、−（２ｋ＊−１）≦ｈ≦２ｋ＊−１、ｈ≠０を満たす）を用いて、整数値ｈが取り得る複数の整数値の数だけ所定の閉区間Ｉ１の両端値を演算する閉区間Ｉ１演算部と、
上記閉区間Ｉ１演算部により用いられた整数値ｈを用いて、上記整数値ｈが取り得る複数の整数値の数だけ所定の閉区間Ｉ２の両端値を演算する閉区間Ｉ２演算部と、
上記整数値ｈを用いた上記閉区間Ｉ１演算部により演算された所定の閉区間Ｉ１の両端値によって定まる所定の閉区間Ｉ１と上記閉区間Ｉ２演算部とにより演算された所定の閉区間Ｉ２の両端値によって定まる所定の閉区間Ｉ２とに共に含まれる複数の整数値を有する集合Ａｈを上記整数値ｈが取り得る複数の整数値の数だけ演算し、上記複数の整数値を有する複数の集合Ａｈを演算する集合Ａｈ演算部と、
上記集合Ａｈ演算部により演算された複数の整数値を有する複数の集合Ａｈに含まれる上記複数の整数値αを用いて複数のベクトル（ｕ，ｖ）を演算するベクトル（ｕ，ｖ）演算部と、
上記ベクトル（ｕ，ｖ）演算部により演算された複数のベクトル（ｕ，ｖ）のｍａｘノルムを演算し、演算された複数のベクトル（ｕ，ｖ）のｍａｘノルムのうち、ｍａｘノルムが最小となるベクトル（ｕ，ｖ）をベクトルＶ２として上記出力部に出力するｍａｘノルム演算部と
を有することを特徴とする請求項１記載のベクトル演算装置。
【請求項３】
上記ベクトル演算装置は、さらに、上記楕円曲線の有理点群の位数ｎと、上記特殊準同型写像φが有理点群上で与えるスカラー倍数であるスカラーλとを入力する入力部を備え、
上記ベクトルＶ１演算部は、上記入力部により入力された位数ｎとスカラーλとを用いて、拡張ユークリッド互除法が定める式：ｓｉ・ｎ＋ｔｉ・λ＝ｒｉについて絶対値｜ｒｉ｜、｜ｔｉ｜＜√ｎとなる最小のインデックスｉをｍ＋１として、｜ｒｍ＋１｜、｜ｔｍ＋１｜＜√ｎ、ｓｍ＋１・ｎ＋ｔｍ＋１・λ＝ｒｍ＋１、最大公約数ｇｃｄ（ｓｍ＋１、ｔｍ＋１）＝１となる変数ｓｍ＋１、ｔｍ＋１を演算し、
上記ベクトルＶ２演算部は、さらに、
上記ベクトルＶ１演算部により演算された変数ｓｍ＋１、ｔｍ＋１を用いてｓｍ＋１・ｖ’−ｔｍ＋１・ｗ‘＝１となる変数ｖ’、ｗ‘を演算する変数ｖ’、ｗ‘演算部と、
上記変数ｖ’、ｗ‘演算部により演算された変数ｖ’、ｗ‘に上記整数値ｈを乗じて変数ｖ“、ｗ“を演算する変数ｖ“、ｗ“演算部と
を有し、
上記閉区間Ｉ１演算部は、上記変数ｖ“、ｗ“演算部により演算された変数ｖ“、ｗ“を用いて所定の閉区間Ｉ１の両端値を演算し、
上記閉区間Ｉ２演算部は、上記変数ｖ“、ｗ“演算部により演算された変数ｖ“、ｗ“を用いて所定の閉区間Ｉ２の両端値を演算することを特徴とする請求項２記載のベクトル演算装置。
【請求項４】
請求項１記載のベクトル演算装置により演算されたベクトルＶ１とベクトルＶ２とを入力するベクトル入力部と、
上記ベクトル入力部により入力されたベクトルＶ１とベクトルＶ２とを用いて上記スカラーＫの分割値ｋ１とｋ２とを演算する分割値演算部と、
上記分割値演算部により演算されたスカラーＫの分割値ｋ１とｋ２とを出力する分割値出力部と
を備えたことを特徴とする分割値演算装置。
【請求項５】
楕円曲線上の点をパラメータとして入力するパラメータ入力部と、
請求項４記載の分割値演算装置により演算されたスカラーＫの分割値ｋ１とｋ２とを入力する分割値入力部と、
上記分割値入力部により入力された分割値ｋ１とｋ２とを用いて、上記パラメータ入力部により入力されたパラメータをスカラーＫ倍演算するスカラー倍演算部と、
上記スカラー倍演算部により演算された結果を出力するスカラー倍出力部と
を備えたことを特徴とする楕円曲線スカラー倍演算装置。
【請求項６】
楕円曲線上の点を楕円暗号パラメータとして入力するパラメータ入力部と、
請求項４記載の分割値演算装置により演算された秘密鍵となるスカラーＫの分割値ｋ１とｋ２とを入力する分割値入力部と、
上記分割値入力部により入力された分割値ｋ１とｋ２とを用いて、上記パラメータ入力部により入力されたパラメータをスカラーＫ倍演算するスカラー倍演算部と、
上記スカラー倍演算部により演算された結果を公開鍵として出力するスカラー倍出力部と
を備えたことを特徴とする楕円暗号演算装置。
【請求項７】
楕円曲線上の点をスカラーＫでスカラーＫ倍するために用いる上記スカラーＫを、自己準同形写像である特殊準同型写像φと分割値ｋ１とｋ２とを用いてスカラーＫ＝ｋ１＋ｋ２φとし、２次元の整数係数の線形空間から１次元の線形空間への写像ｆをｆ：（ｉ，ｊ）→ｉ＋λｊ（ｍｏｄ  ｎ）（但し、ｍｏｄ  ｎは、ｉ＋λｊをｎで割った余りを意味する）とし、上記写像ｆが０になる２次元の部分空間をＫｅｒ  ｆとし、Ｋｅｒ  ｆの基底ベクトルであって基底ベクトルの成分の絶対値が最も小さくなるもの（ただし、絶対値がゼロになるものを除く）をベクトルＶ１とベクトルＶ２とし、ベクトルＶ１及びベクトルＶ２を使用して、ｆ（ｕ）＝Ｋとなる小ベクトルｕ＝（ｋ１，ｋ２）を計算すると、小ベクトルｕが上記スカラーＫのＫ＝ｋ１＋ｋ２φのｋ１，ｋ２を与えるベクトルＶ１とベクトルＶ２とを演算するベクトル演算方法において、
拡張ユークリッド互除法を用いて上記ベクトルＶ１をＣＰＵ（Ｃｅｎｔｒａｌ  Ｐｒｏｃｅｓｓｉｎｇ  Ｕｎｉｔ）に演算させるベクトルＶ１演算工程と、
上記ベクトルＶ１演算工程によりＣＰＵが演算させられたベクトルＶ１を記憶装置に記憶するベクトルＶ１記憶工程と、
上記拡張ユークリッド互除法を用いて、ＣＰＵに複数の整数値を有する複数の集合Ａｈを演算させ、演算させられた複数の整数値を有する複数の集合Ａｈに含まれる複数の整数値αを用いてベクトルＶ２をＣＰＵに演算させるベクトルＶ２演算工程と、
上記ベクトルＶ２演算工程によりＣＰＵが演算させられたベクトルＶ２を記憶装置に記憶するベクトルＶ２記憶工程と、
上記ベクトルＶ１演算工程により演算され、上記記憶装置に記憶されたベクトルＶ１と上記ベクトルＶ２演算工程により演算され、上記記憶装置に記憶されたベクトルＶ２とを出力装置に出力する出力工程と
を備えたことを特徴とするベクトル演算方法。
【請求項８】
楕円曲線上の点をスカラーＫでスカラー倍するために用いる上記スカラーＫを、自己準同形写像である特殊準同型写像φと分割値ｋ１とｋ２とを用いてスカラーＫ＝ｋ１＋ｋ２φとし、２次元の整数係数の線形空間から１次元の線形空間への写像ｆをｆ：（ｉ，ｊ）→ｉ＋λｊ（ｍｏｄ  ｎ）（但し、ｍｏｄ  ｎは、ｉ＋λｊをｎで割った余りを意味する）とし、上記写像ｆが０になる２次元の部分空間をＫｅｒ  ｆとし、Ｋｅｒ  ｆの基底ベクトルであって基底ベクトルの成分の絶対値が最も小さくなるもの（ただし、絶対値がゼロになるものを除く）をベクトルＶ１とベクトルＶ２とし、ベクトルＶ１及びベクトルＶ２を使用して、ｆ（ｕ）＝Ｋとなる小ベクトルｕ＝（ｋ１，ｋ２）を計算すると、小ベクトルｕが上記スカラーＫのＫ＝ｋ１＋ｋ２φのｋ１，ｋ２を与えるベクトルＶ１とベクトルＶ２とを演算することをコンピュータに実行させるプログラムにおいて、
拡張ユークリッド互除法を用いて上記ベクトルＶ１を演算するベクトルＶ１演算処理と、
上記ベクトルＶ１演算処理により演算されたベクトルＶ１を記憶装置に記憶するベクトルＶ１記憶処理と、
上記拡張ユークリッド互除法を用いて、複数の整数値を有する複数の集合Ａｈを演算し、演算された複数の整数値を有する複数の集合Ａｈに含まれる複数の整数値αを用いて上記ベクトルＶ２を演算するベクトルＶ２演算処理と、
上記ベクトルＶ２演算処理により演算されたベクトルＶ２を記憶装置に記憶するベクトルＶ２記憶処理と、
上記ベクトルＶ１演算処理により演算され、上記記憶装置に記憶されたベクトルＶ１と上記ベクトルＶ２演算処理により演算され、上記記憶装置に記憶されたベクトルＶ２とを出力装置に出力する出力処理と
をコンピュータに実行させることを特徴とするプログラム。
【請求項９】
楕円曲線上の点をスカラーＫでスカラー倍するために用いる上記スカラーＫを、自己準同形写像である特殊準同型写像φと分割値ｋ１とｋ２とを用いてスカラーＫ＝ｋ１＋ｋ２φとし、２次元の整数係数の線形空間から１次元の線形空間への写像ｆをｆ：（ｉ，ｊ）→ｉ＋λｊ（ｍｏｄ  ｎ）（但し、ｍｏｄ  ｎは、ｉ＋λｊをｎで割った余りを意味する）とし、上記写像ｆが０になる２次元の部分空間をＫｅｒ  ｆとし、Ｋｅｒ  ｆの基底ベクトルであって基底ベクトルの成分の絶対値が最も小さくなるもの（ただし、絶対値がゼロになるものを除く）をベクトルＶ１とベクトルＶ２とし、ベクトルＶ１及びベクトルＶ２を使用して、ｆ（ｕ）＝Ｋとなる小ベクトルｕ＝（ｋ１，ｋ２）を計算すると、小ベクトルｕが上記スカラーＫのＫ＝ｋ１＋ｋ２φのｋ１，ｋ２を与えるベクトルＶ１とベクトルＶ２とを演算することをコンピュータに実行させるプログラムを記録したコンピュータ読み取り可能な記録媒体において、
拡張ユークリッド互除法を用いて上記ベクトルＶ１を演算するベクトルＶ１演算処理と、
上記ベクトルＶ１演算処理により演算されたベクトルＶ１を記憶装置に記憶するベクトルＶ１記憶処理と、
上記拡張ユークリッド互除法を用いて、複数の整数値を有する複数の集合Ａｈを演算し、演算された複数の整数値を有するの複数の集合Ａｈに含まれる複数の整数値αを用いてベクトルＶ２を演算するベクトルＶ２演算処理と、
上記ベクトルＶ２演算処理により演算されたベクトルＶ２を記憶装置に記憶するベクトルＶ２記憶処理と、
上記ベクトルＶ１演算処理により演算され、上記記憶装置に記憶されたベクトルＶ１と上記ベクトルＶ２演算処理により演算され、上記記憶装置に記憶されたベクトルＶ２とを出力装置に出力する出力処理と
をコンピュータに実行させることを特徴とするプログラムを記録したコンピュータ読み取り可能な記録媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ベクトル演算装置或いは分割値演算装置或いは楕円曲線スカラー倍演算装置或いは楕円暗号演算装置、または、各方法に関する。特に、本発明は、楕円暗号演算を高速に行う方法、及びその方法を用いた演算装置に関する。
【背景技術】
【０００２】
楕円暗号演算を高速に行うためには、スカラー倍演算の高速化が必須である。これまで、様々なスカラー倍演算高速化手法が提案されてきた。近年の研究で、効率的に計算可能な自己準同形写像である特殊準同型写像φを用いて定数ＫをＫ＝ｋ１＋ｋ２φ（又はｋ１＋ｋ２λ、λは点群上でφが与えるスカラー倍数）と表現（分割）することで演算効率を高めた技術が存在する（非特許文献１参照）。
【０００３】
また、非特許文献１にある分割方法がどれだけ演算効率を高めるかを評価した結果が知られている（非特許文献２参照）。
【０００４】
また、非特許文献１にある分割方法を、更に演算効率を高めるように改良した結果が知られている（非特許文献３参照）。以下、非特許文献３にあるＫの分割法を説明していく。
【０００５】
Ｋの分割は、まず、スカラーＫによらない互いに一次独立なベクトル（基底）Ｖ１、Ｖ２を以下の手順で求めることから始まる。２次元の整数係数の線形空間から１次元の線形空間への写像ｆをｆ：（ｉ，ｊ）→ｉ＋λｊ（ｍｏｄ  ｎ）（但し、ｍｏｄ  ｎは、ｉ＋λｊをｎで割った余りを意味する）と定める。ｆで０になる２次元の部分空間をＫｅｒ  ｆと書くことにすると、Ｋｅｒ  ｆの基底Ｖ１、Ｖ２で、その成分の絶対値が小さくなるもの（ビット数が少なくなるもの）をとることが必要となる。そのＶ１、Ｖ２を使って、ｆ（ｕ）＝Ｋとなる小ベクトルｕ＝（ｋ１，ｋ２）を計算すると、ｕが、Ｋ＝ｋ１＋ｋ２φ（又はｋ１＋ｋ２λ）であるｋ１，ｋ２を与えることがわかる。
【０００６】
Ｖ１とＶ２は一次独立だから、（Ｋ，０）＝β１・Ｖ１＋β２・Ｖ２となる有理数β１、β２が存在することがわかり、それらは容易に計算可能である。ｂ１：＝“β１に一番近い整数”、ｂ２：＝“β２に一番近い整数”として、ｕ：＝（Ｋ，０）−（ｂ１・Ｖ１＋ｂ２・Ｖ２）とすることで、“Ｋの分割”が得られる。
【０００７】
従来知られていた小基底Ｖ１、Ｖ２の探索アルゴリズムを説明する。
【０００８】
楕円曲線有理点群の位数ｎと、楕円曲線特殊準同型が定めるスカラーλを入力として、ステップＳ１０１で拡張ユークリッド互除法を用いて、｜ｒｍ＋１｜、｜ｔｍ＋１｜＜√ｎ、ｓｍ＋１・ｎ＋ｔｍ＋１・λ＝ｒｍ＋１、ｇｃｄ（ｓｍ＋１、ｔｍ＋１）＝１となるＶ１：＝（ｒｍ＋１、−ｔｍ＋１）を計算する。但し、ここで、ｒｍ＋１等の記法は、ｍ＋１とインデックス付けされた変数ｒを表すものとする。また、記号「：＝」は、左を右で定義することを意味する。
【０００９】
次にステップＳ１０２で、拡張ユークリッド互除法の中間変数を用いて構成したベクトル（ｒｍ、−ｔｍ）か（ｒｍ＋２、−ｔｍ＋２）のｍａｘノルムが√ｎより小さいかどうかをチェックして、もしそうなら、そのベクトルをＶ２とする。そうでないなら、次のス
テップに進む。ここで、例えば、値ｉ，ｊについてのｍａｘノルムとは、値ｉの絶対値｜ｉ｜と値ｊの絶対値｜ｊ｜とのうちの大きい方の値を示す。
【００１０】
次にステップＳ１０３で、拡張ユークリッド互除法を用いて、ｓｍ＋１・ｖ’−ｔｍ＋１・ｗ‘＝１となるｖ’、ｗ‘を計算する。
【００１１】
次にステップＳ１０４で、Ｉ１１：＝−ｖ’／ｔｍ＋１−√ｎ／ｔｍ＋１、Ｉ１２：＝−ｖ’／ｔｍ＋１＋√ｎ／ｔｍ＋１とし、もしｔｍ＋１＞０ならＩ１：＝［Ｉ１１，Ｉ１２］（閉区間）とし、そうでないなら、Ｉ１：＝［Ｉ１２，Ｉ１１］とする。
【００１２】
次にステップＳ１０５で、Ｉ２１：＝（ｖ’・λ−ｗ‘・ｎ）／ｒｍ＋１−√ｎ／ｒｍ＋１、Ｉ２２：＝（ｖ’・λ−ｗ‘・ｎ）／ｒｍ＋１＋√ｎ／ｒｍ＋１、Ｉ２：＝［Ｉ２１，Ｉ２２］とする。
【００１３】
次にステップＳ１０６で、全ての整数α∈Ｉ１∩Ｉ２に対して、ｕ：＝ｗ‘・ｎ−ｖ’・λ＋αｒｍ＋１、ｖ：＝ｖ’−α・ｔｍ＋１としたベクトル（ｕ，ｖ）を考え、その中でｍａｘノルムが最小のものをＶ２として、Ｖ１、Ｖ２を出力する。
【非特許文献１】Ｒ．Ｐ．Ｇａｌｌａｎｔ，Ｊ．Ｌ．Ｌａｍｂｅｒｔ  ａｎｄ  Ｓ．Ａ．Ｖａｎｓｔｏｎｅ，“Ｆａｓｔｅｒ  ｐｏｉｎｔ  ｍｕｌｔｉｐｌｉｃａｔｉｏｎ  ｏｎ  ｅｌｌｉｐｔｉｃ  ｃｕｒｖｅｓ  ｗｉｔｈ  ｅｆｆｉｃｉｅｎｔ  ｅｎｄｏｍｏｒｐｈｉｓｍｓ”，Ｃｒｙｐｔｏ  ２００１，  Ｓｐｒｉｎｇｅｒ  Ｖｅｒｌａｇ，（２００１），１９０−２００．
【非特許文献２】Ｆ．Ｓｉｃａ，Ｍ．Ｃｉｅｔ，Ｊ．−Ｊ．Ｑｕｉｓｑｕａｔｅｒ，“Ａｎａｌｙｓｉｓ  ｏｆ  ｔｈｅ  Ｇａｌｌａｎｔ−Ｌａｍｂｅｒｔ−Ｖａｎｓｔｏｎｅ  ｍｅｔｈｏｄ  ｂａｓｅｄ  ｏｎ  ｅｆｆｉｃｉｅｎｔ  ｅｎｄｏｍｏｒｐｈｉｓｍｓ  ：ｅｌｌｉｐｔｉｃ  ａｎｄ  ｈｙｐｅｒｅｌｌｉｐｔｉｃ  ｃｕｒｖｅｓ”，ＳＡＣ  ２００２，Ｓｐｒｉｎｇｅｒ  Ｖｅｒｌａｇ，（２００２），２１−３６．
【非特許文献３】Ｄ．Ｋｉｍ，Ｓ．Ｌｉｍ，“Ｉｎｔｅｇｅｒ  ｄｅｃｏｍｐｏｓｉｔｉｏｎ  ｆｏｒ  ｆａｓｔ  ｓｃａｌａｒ  ｍｕｌｔｉｐｌｉｃａｔｉｏｎ  ｏｎ  ｅｌｌｉｐｔｉｃ  ｃｕｒｖｅｓ”，ＳＡＣ  ２００２，Ｓｐｒｉｎｇｅｒ  Ｖｅｒｌａｇ，（２００２），１３−２０．
【発明の開示】
【発明が解決しようとする課題】
【００１４】
近年の高度情報通信技術の実用化に伴い、楕円暗号を含む公開鍵暗号も既に実用化段階に入っているが、クロックの小さいＣＰＵ（Ｃｅｎｔｒａｌ  Ｐｒｏｃｅｓｓｉｎｇ  Ｕｎｉｔ）しか搭載していない、或いはできないＩＣカード上での暗号演算実行や、ユビキタス環境での情報セキュリティ確保のため、計算リソースが制限された環境での使用も必要不可欠のものとなっている。つまり、暗号演算計算速度の向上が切に望まれている。
【００１５】
しかしながら、上記従来技術のＶ１、Ｖ２探索法では、必ずしも最短の基底を探索できていなかった。よって、最良のＫの分割を与えられなかった。すなわち、十分小さいｋ１、ｋ２の値を得ることができなかった。すなわち、暗号演算計算速度が遅く、特に、上記ＩＣカード上での暗号演算実行や、ユビキタス環境において、十分な対応ができなかった。
【００１６】
本発明は、上記Ｖ１、Ｖ２探索法より短いＶ１、Ｖ２を探索することを目的とする。
【００１７】
また、本発明は、分割Ｋ＝ｋ１＋ｋ２φ（又はｋ１＋ｋ２λ）で、ｋ１、ｋ２の値をより小さくすることを目的とする。
【００１８】
また、本発明は、スカラー倍演算を高速に行うこと、つまり、楕円暗号演算を高速に行うことを目的とする。
【課題を解決するための手段】
【００１９】
この発明に係るベクトル演算装置は、楕円曲線上の点をスカラーＫでスカラー倍するために用いる上記スカラーＫを、自己準同形写像である特殊準同型写像φと分割値ｋ１とｋ２とを用いてスカラーＫ＝ｋ１＋ｋ２φとし、２次元の整数係数の線形空間から１次元の線形空間への写像ｆをｆ：（ｉ，ｊ）→ｉ＋λｊ（ｍｏｄ  ｎ）（但し、ｍｏｄ  ｎは、ｉ＋λｊをｎで割った余りを意味する）とし、上記写像ｆが０になる２次元の部分空間をＫｅｒ  ｆとし、Ｋｅｒ  ｆの基底ベクトルであって基底ベクトルの成分の絶対値が最も小さくなるもの（ただし、絶対値がゼロになるものを除く）をベクトルＶ１とベクトルＶ２とし、ベクトルＶ１及びベクトルＶ２を使用して、ｆ（ｕ）＝Ｋとなる小ベクトルｕ＝（ｋ１，ｋ２）を計算すると、小ベクトルｕが上記スカラーＫのＫ＝ｋ１＋ｋ２φのｋ１，ｋ２を与えるベクトルＶ１とベクトルＶ２とを演算するベクトル演算装置において、
拡張ユークリッド互除法を用いて上記ベクトルＶ１を演算するベクトルＶ１演算部と、
上記拡張ユークリッド互除法を用いて、複数の整数値を有する複数の集合Ａｈを演算し、演算された複数の整数値を有する複数の集合Ａｈに含まれる複数の整数値αを用いて上記ベクトルＶ２を演算するベクトルＶ２演算部と、
上記ベクトルＶ１演算部により演算されたベクトルＶ１と上記ベクトルＶ２演算部により演算されたベクトルＶ２とを出力するベクトル出力部と
を備えたことを特徴とする。
【発明の効果】
【００２０】
本発明によれば、従来法では、まだ改善の余地が残されていた楕円曲線暗号演算法に対して、更なる高速化を得ることを可能にし、計算資源が限られた環境においても、実用性を発揮する暗号機能を実現可能にすることができるＶ１、Ｖ２を探索することができる。
【発明を実施するための最良の形態】
【００２１】
以下に説明する楕円暗号演算装置は、所定の楕円暗号上の点とスカラーを入力する入力部と、所定のスカラー分割値演算装置と分割値演算装置の元となるベクトルを演算するベクトル演算装置と、所定のスカラー分割値を用いて楕円曲線スカラー倍計算をおこなうスカラー倍演算部とを備えている。そして、上記入力部により入力された所定の楕円パラメータとスカラーに対する演算をおこない、所定のスカラー分割値を用いて楕円曲線スカラー倍計算をおこなう。
【００２２】
実施の形態１．
まず、公開鍵暗号、離散対数問題および楕円暗号について簡単に説明する。公開鍵暗号通信においては、利用者ごとに秘密鍵ｘと公開鍵ｙの組が用意され、秘密鍵ｘは、各利用者が秘密に保持しておく。公開鍵ｙは利用者自身以外の一般に公開する。利用者Ｂが利用者Ａに秘密にデータを送りたい時は、利用者Ｂは利用者Ａに対応する公開鍵ｙを用いてデータを暗号化する。この暗号文は、秘密鍵ｘを知る利用者Ａにしか復号できない。
【００２３】
離散対数問題とは代数群Ｇ（加法が定義されているものとする）の２つの要素ｇ１，ｇ２に対して、ｇ１＝ｍｇ２を満たすようなｍを求める問題である。代数群Ｇの要素の数が大きい場合、多くの離散対数問題を解くことは、計算量的に非常に困難になることが知られている。この事実を利用して公開鍵暗号を設計することができる。
【００２４】
離散対数型公開鍵暗号は多く、代数群Ｇを定める式とｇ２を公開鍵暗号パラメータとし、ｇ１をその公開鍵、ｍをその秘密鍵とする。
【００２５】
有限体ＧＦ（ｑ）（ｑは素数ｐのべき乗）上の楕円曲線Ｃとは、ｙ２＋ｈ（ｘ）ｙ＝ｆ（ｘ）（ｈ（ｘ），ｆ（ｘ）はそれぞれＧＦ（ｑ）係数の高々１次及び、３次多項式。かつ、ｆ（ｘ）は最高次の係数が１）と表される方程式である。また、Ｃの有理点集合には加法が定義され、群となる。これらの群を利用した公開鍵暗号を楕円暗号という。
【００２６】
つまり、楕円暗号の場合には、方程式ｙ２＋ｈ（ｘ）ｙ＝ｆ（ｘ）の係数とその上の点（ｘ０，ｙ０）が楕円暗号パラメータとなり、楕円曲線上の加算に従って計算される（ｘ１，ｙ１）（（ｘ１，ｙ１）は、（ｘ１，ｙ１）＝Ｋ・（ｘ０，ｙ０）を満たす）がその公開鍵、スカラーＫがその秘密鍵となる。
【００２７】
ここで、スカラーＫの値が大きいと、計算に時間がかかってしまう。例えば、楕円暗号の場合、Ｋは、２進数で１６０ビットの値を用いる。ここで、１６０ビットの各位のビット値を順に楕円暗号パラメータに加算していった場合に、相当な時間を要することになる。したがって、スカラーＫをＫ＝ｋ１＋ｋ２φ（又はｋ１＋ｋ２λ、λは点群上でφが与えるスカラー倍数）と表現（分割）することで、ｋ１或いはｋ２φのビット数の計算量で済むことになる。例えば、楕円暗号パラメータである楕円曲線上の点をＰとすれば、スカラー倍計算は、ＫＰ＝ｋ１・Ｐ＋ｋ２・λＰとなる。予め、Ｐ＋λＰ＝Ｓとすると、所定の位のビット値がｋ１＝１、ｋ２＝０であれば、Ｐを用いた計算となり、ｋ１＝０、ｋ２＝１であれば、λＰを用いた計算となり、ｋ１＝１、ｋ２＝１であれば、Ｓを用いた計算となり、ｋ１＝０、ｋ２＝０であれば、計算が不要となる。したがって、各位について、Ｐまたは、λＰまたは、Ｓを用いた計算となり、しかも、ｋ１或いはｋ２φのビット数の計算量で済むことになる。例えば、スカラーＫが楕円曲線有理点群の位数ｎと同等なビット数を有するとして、ｋ１とｋ２φとのビット数が概ね√ｎ近くに小さくなる。すなわち、それだけ、演算回数が減り、演算速度を高速化させることができる。
【００２８】
まず、楕円曲線上の点をスカラーＫでスカラー倍するために用いる上記スカラーＫを、特殊準同型写像φを用いて分割するための分割値ｋ１とｋ２とを求めるために用いる、ベクトルＶ１とベクトルＶ２とを演算するベクトル演算装置について説明する。
【００２９】
図１は、実施の形態１におけるベクトル演算装置の構成を示す図である。
【００３０】
図１において、ベクトル演算装置４００は、入力部４０１、ベクトルＶ１演算部４０２、ベクトルＶ２演算部４２０、出力部４１１、記憶部４１２、制御部４１３を備えている。ベクトルＶ２演算部４２０は、計算部４０３，４０４，４０５，４０６，４０７，４０８，４０９，４１０を有する。
【００３１】
ベクトルＶ１演算部４０２は、拡張ユークリッド互除法を用いてベクトルＶ１を演算する。
【００３２】
ベクトルＶ２演算部４２０は、拡張ユークリッド互除法を用いて、整数の複数の集合Ａｈを演算し、演算された整数の複数の集合Ａｈに含まれる複数の整数値αを用いてベクトルＶ２を演算する。
【００３３】
記憶部４１２は、上記各部により入力された値、計算或いは演算された値、出力された値を記憶する。
【００３４】
制御部４１３は、各部を制御する。ここで、図１では、全体を制御する制御部４１３を備えているが、各部ごとに自己を制御する機構を備えても構わない。
【００３５】
ベクトル出力部としての出力部４１１は、上記ベクトルＶ１演算部４０２により演算されたベクトルＶ１と上記ベクトルＶ２演算部４２０により演算されたベクトルＶ２とを出力する。出力部４１１は、各演算部、或いは計算部から入力したベクトルを出力してもよいし、記憶部４１２に記憶されたベクトルを出力しても構わない。
【００３６】
図２は、実施の形態１におけるベクトル演算方法のフローチャートを示す図である。
【００３７】
まず、入力部４０１は、整数である楕円曲線有理点群の位数ｎと、楕円曲線特殊準同型写像φが定めるスカラーλを入力する。
【００３８】
ステップＳ２０１において、ベクトルＶ１演算工程として、ベクトルＶ１演算部４０２は、上記入力部４０１により入力された位数ｎとスカラーλとを用いて、拡張ユークリッド互除法が定める式：ｓｉ・ｎ＋ｔｉ・λ＝ｒｉについて、ｉ＝０、１，２，３・・・ｍ，ｍ＋１，ｍ＋２と順に演算し、変数ｒｉについての絶対値｜ｒｉ｜＜√ｎ、変数ｔｉについての絶対値｜ｔｉ｜＜√ｎとなる最小のインデックスｉをｍ＋１として、絶対値｜ｒｍ＋１｜＜√ｎ、絶対値｜ｔｍ＋１｜＜√ｎ、ｓｍ＋１・ｎ＋ｔｍ＋１・λ＝ｒｍ＋１、ｓｍ＋１とｔｍ＋１との最大公約数ｇｃｄ（ｓｍ＋１、ｔｍ＋１）＝１となる変数ｓｍ＋１、ｔｍ＋１、ｒｍ＋１を演算する。そして、演算された変数ｒｍ＋１、ｔｍ＋１を用いて、ベクトルＶ１：＝（ｒｍ＋１、−ｔｍ＋１）を計算する。ここで、拡張ユークリッド互除法を初期値として、変数ｓ０＝１，ｔ０＝０，ｒ０＝ｎ，ｓ１＝０，ｔ１＝１，ｒ１＝λで行うと、ｓｉ・ｎ＋ｔｉ・λ＝ｒｉ（ｉ＝０，１，２，…）となる列（ｓｉ，ｔｉ，ｒｉ）（ｉ＝０，１，２，…）を漸化的に得るが、それら列の中で｜ｒｉ｜、｜ｔｉ｜＜√ｎとなる最小のインデックスｉをｍ＋１と定義する。また、記号「：＝」は、記号の左の記載は記号の右の記載で定義することを示す。以下、同様である。
【００３９】
次にステップＳ２０２で、ベクトルＶ２演算工程の一部として、計算部４０３は、ベクトルＶ１演算部４０２により拡張ユークリッド互除法に従い順次計算された中間変数（ｒｍ、−ｔｍ）か（ｒｍ＋２、−ｔｍ＋２）のｍａｘノルムが√ｎより小さいかどうかをチェックして、もしそうなら、そのベクトルをベクトルＶ２とする。そうでないなら、次のステップに進む。ここで、例えば、値ｉ，ｊについてのｍａｘノルムとは、値ｉの絶対値｜ｉ｜と値ｊの絶対値｜ｊ｜とのうちの大きい方の値を示す。
【００４０】
次にステップＳ２０３で、ベクトルＶ２演算工程の一部として、変数ｖ’、ｗ‘演算部の一例としての計算部４０４は、拡張ユークリッド互除法を用いて上記ベクトルＶ１演算部により演算された変数ｓｍ＋１、ｔｍ＋１を用いてｓｍ＋１・ｖ’−ｔｍ＋１・ｗ‘＝１となる変数ｖ’、ｗ‘を演算（計算）する。
【００４１】
次にステップＳ２０４で、ベクトルＶ２演算工程の一部として、計算部４０５は、上記特殊準同型写像φが満たす最小多項式（Ｘ２＋ｒ・Ｘ＋ｓ）の係数として定まる値ｒ、ｓを用いて定まる定数ｋ＊を用いて、整数値ｈに、−（２ｋ＊−１）≦ｈ≦２ｋ＊−１、ｈ≠０を満たす値を順に入力する。ここで、ｋ＊：＝”√（１＋｜ｒ｜＋ｓ）値以上の最小の整数値”とする。以下、ｈ＝−（２ｋ＊−１）から２ｋ＊−１まで、次のステップＳ２０５からＳ２０８までを繰り返すことになる。
【００４２】
ステップＳ２０５で、ベクトルＶ２演算工程の一部として、変数ｖ“、ｗ“演算部の一例としての計算部４０６は、以下に説明する区間を定めるためのパラメータとして、上記計算部４０４により演算された変数ｖ’、ｗ‘に上記整数値ｈを乗じた変数ｖ“、ｗ“を演算する。すなわち、計算部４０６は、ｖ“：＝ｈｖ’、ｗ“：＝ｈｗ’を計算する。
【００４３】
次にステップＳ２０６で、ベクトルＶ２演算工程の一部である閉区間Ｉ１演算工程として、閉区間Ｉ１演算部の一例としての計算部４０７は、上記特殊準同型写像φが満たす最小多項式（Ｘ２＋ｒ・Ｘ＋ｓ）の係数として定まる値ｒ、ｓを用いて定まる定数ｋ＊を用いた整数値ｈ（ｈは、−（２ｋ＊−１）≦ｈ≦２ｋ＊−１、ｈ≠０を満たす）を用いて、整数値ｈが取り得る複数の整数値の数だけ、後述する整数αの探索範囲の確定その１の所定の閉区間Ｉ１の両端値を演算する。ここでは、計算部４０７は、計算部４０６により演算された変数ｖ“、ｗ“を用いて所定の閉区間Ｉ１の両端値を演算する。まず、後述する
整数αの探索範囲の確定その１の一方の端であるＩ１１：＝−ｖ“／ｔｍ＋１−ｋ＊・√ｎ／ｔｍ＋１を演算する。そして、後述する整数αの探索範囲の確定その１の他方の端であるＩ１２：＝−ｖ“／ｔｍ＋１＋ｋ＊・√ｎ／ｔｍ＋１を演算する。そして、もし、ｔｍ＋１＞０なら閉区間Ｉ１：＝［Ｉ１１，Ｉ１２］とし、そうでないなら、閉区間Ｉ１：＝［Ｉ１２，Ｉ１１］とする。ここで、閉区間とは、例えば、閉区間Ｉ１：＝［Ｉ１２，Ｉ１１］であれば、端値Ｉ１２，Ｉ１１を含む、端値Ｉ１２から端値Ｉ１１までの間の範囲を示す。
【００４４】
次にステップＳ２０７で、ベクトルＶ２演算工程の一部である閉区間Ｉ２演算工程として、閉区間Ｉ２演算部の一例としての計算部４０８は、上記計算部４０７により用いられた整数値ｈを用いて、上記整数値ｈが取り得る複数の整数値の数だけ、後述する整数αの探索範囲の確定その２の所定の閉区間Ｉ２の両端値を演算する。ここでは、計算部４０８は、上記変数ｖ“、ｗ“演算部により演算された変数ｖ“、ｗ“を用いて所定の閉区間Ｉ２の両端値を演算する。まず、後述する整数αの探索範囲の確定その２の一方の端であるＩ２１：＝（ｖ“・λ−ｗ“・ｎ）／ｒｍ＋１−√ｎ／ｒｍ＋１を演算する。そして、後述する整数αの探索範囲の確定その２の他方の端であるＩ２２：＝（ｖ“・λ−ｗ“・ｎ）／ｒｍ＋１＋√ｎ／ｒｍ＋１を演算する。そして、閉区間Ｉ２：＝［Ｉ２１，Ｉ２２］とする。
【００４５】
次にステップＳ２０８で、ベクトルＶ２演算工程の一部である集合Ａｈ演算工程として、集合Ａｈ演算部の一例としての計算部４０９は、上記整数値ｈを用いた上記計算部４０７により演算された所定の閉区間Ｉ１の両端値によって定まる所定の閉区間Ｉ１と上記計算部４０８とにより演算された所定の閉区間Ｉ２の両端値によって定まる所定の閉区間Ｉ２とに共に含まれる整数の集合Ａｈを演算する。すなわち、集合Ａｈ：＝“Ｉ１∩Ｉ２に含まれる整数の集合”とする。そして、上記Ｓ２０４に戻る。上記Ｓ２０４において、上記整数値ｈに順に値が入力され、Ｓ２０４からＳ２０８までループ計算させることにより、結果的に上記整数値ｈが取り得る複数の整数値の数だけ演算し、上記整数の複数の集合Ａｈを演算する。
【００４６】
上記ループを終えた後に、ステップＳ２０９で、ベクトルＶ２演算工程の一部であるベクトル（ｕ，ｖ）演算工程として、ベクトル（ｕ，ｖ）演算部の一例としての計算部４１０は、上記計算部４０９により演算された整数の複数の集合Ａｈ（ｈは、−（２ｋ＊−１）≦ｈ≦２ｋ＊−１、ｈ≠０を満たす）に含まれる上記複数の整数値αを用いて複数のベクトル（ｕ，ｖ）を演算する。ここでは、全てのｈ（−（２ｋ＊−１）≦ｈ≦２ｋ＊−１、ｈ≠０）、整数α∈Ａｈに対して、ｕ：＝ｈ・ｗ‘ｎ−ｈ・ｖ’λ＋αｒｍ＋１、ｖ：＝ｈｖ’−α・ｔｍ＋１としたベクトル（ｕ，ｖ）を演算する。
【００４７】
そして、ベクトルＶ２演算工程の一部であるｍａｘノルム演算工程として、ｍａｘノルム演算部の一例でもある計算部４１０は、上記ベクトル（ｕ，ｖ）演算部により演算された複数のベクトル（ｕ，ｖ）のｍａｘノルムを演算し、演算された複数のベクトル（ｕ，ｖ）のｍａｘノルムのうち、ｍａｘノルムが最小となるベクトル（ｕ，ｖ）をベクトルＶ２として上記出力部４１１に出力する。すなわち、計算部４０３は、Ｖ１を、計算部４１０は、Ｖ２を上記出力部４１１に出力する。
【００４８】
ベクトル出力部としての出力部４１１は、上記ベクトルＶ１演算部により演算されたベクトルＶ１と上記ベクトルＶ２演算部により演算されたベクトルＶ２とを出力する。
【００４９】
以上のように、上記整数値ｈが取り得る複数の整数値の数だけ演算され、その結果得た整数の複数の集合Ａｈを用いることにより、従来技術では、拾うことができなかった整数αの探索範囲を適性に妥当な範囲で拡大させることができ、探索範囲が広がったことで、
従来技術では、得ることができなかった最短の基底を探索することができる。
【００５０】
次に、Ｖ１、Ｖ２を用いて“Ｋの分割”を行う所定のスカラー分割値演算装置となる分割値演算装置を説明する。
【００５１】
図３は、実施の形態１における分割値演算装置の構成を示す図である。
【００５２】
図３において、分割値演算装置５００は、入力部５０１、分割値演算部５２０、分割値出力部５０５、記憶部５０６、制御部５０７を備えている。分割値演算部５２０は、計算部５０２，５０３，５０４を有している。
【００５３】
ベクトル入力部としての入力部５０１は、上記ベクトル演算装置４００により演算されたベクトルＶ１とベクトルＶ２とを入力する。
【００５４】
分割値演算部５２０は、入力部５０１により入力されたベクトルＶ１とベクトルＶ２とを用いて上記スカラーＫの分割値ｋ１とｋ２とを演算する。
【００５５】
記憶部５０６は、上記各部により入力された値、計算或いは演算された値、出力された値を記憶する。
【００５６】
制御部５０７は、各部を制御する。ここで、図３では、全体を制御する制御部５０７を備えているが、各部ごとに自己を制御する機構を備えても構わない。
【００５７】
分割値出力部としての出力部５０５は、上記分割値演算部５２０により演算されたスカラーＫの分割値ｋ１とｋ２とを出力する。出力部５０５は、各演算部、或いは計算部から入力した分割値を出力してもよいし、記憶部５０６に記憶された分割値を出力しても構わない。
【００５８】
図４は、実施の形態１における分割値演算方法のフローチャートを示す図である。
【００５９】
Ｋの分割は、まず、スカラーＫによらない互いに一次独立なベクトルＶ１、Ｖ２を以下の手順で求めることから始まる。整数である楕円曲線有理点群の位数ｎと、楕円曲線特殊準同型写像φが定めるスカラーλとを用いて、２次元の整数係数の線形空間から１次元の線形空間への写像φをφ：（ｉ，ｊ）→ｉ＋λｊ（ｍｏｄ  ｎ）（但し、ｍｏｄ  ｎは、ｉ＋λｊを整数である楕円曲線有理点群の位数ｎで割った余りを意味する）と定める。φで０になる２次元の部分空間をＫｅｒ  φと書くことにすると、十分小さな“Ｋの分割”を得るためには、Ｋｅｒ  φの基底Ｖ１、Ｖ２で、その成分がなるべく小さくなるものをとることが必要となる。そのＶ１、Ｖ２を使って、ｕ＝（ｉ，ｊ）として、φ（ｕ）＝Ｋとなる小ベクトルｕ＝（ｋ１，ｋ２）を計算すると、ｕが、Ｋ＝ｋ１＋ｋ２φ（又はｋ１＋ｋ２λ）であるｋ１，ｋ２を与えることがわかる。
【００６０】
まず、入力部５０１は、整数であるスカラーＫと基底となるベクトルＶ１とベクトルＶ２とを入力する。
【００６１】
ステップＳ３０１において、Ｖ１とＶ２は一次独立だから、（Ｋ，０）＝β１・Ｖ１＋β２・Ｖ２となる有理数β１、β２が存在することがわかり、計算部５０２は、有理数β１、β２を計算する。
【００６２】
ステップＳ３０２において、計算部５０３は、ｂ１：＝“β１に一番近い整数”、ｂ２：＝“β２に一番近い整数”を計算する。
【００６３】
ステップＳ３０３において、計算部５０４は、ｕ：＝（Ｋ，０）−（ｂ１・Ｖ１＋ｂ２・Ｖ２）を計算する。すなわち、ベクトルＶ１＝（ｒｍ＋１、−ｔｍ＋１）、ベクトルＶ２＝（ｕ，ｖ）とすると、ｕ＝（ｋ１，ｋ２）＝（Ｋ，０）−（ｂ１・Ｖ１＋ｂ２・Ｖ２）＝（（β１−ｂ１）ｒｍ＋１＋（β２−ｂ２）ｕ，−（β１−ｂ１）ｔｍ＋１＋（β２−ｂ２）ｖ）を計算することにより、“Ｋの分割”として、ｋ１＝（β１−ｂ１）ｒｍ＋１＋（β２−ｂ２）ｕ、ｋ２＝−（β１−ｂ１）ｔｍ＋１＋（β２−ｂ２）ｖを得る。
【００６４】
そして、出力部５０５を通して、“Ｋの分割”ｕ＝（ｋ１，ｋ２）を出力する。
【００６５】
以上のように、整数の複数の集合Ａｈを用いることにより適性に広がった探索範囲中の整数αにより得た最短の基底を用いることにより、最良のＫの分割を得ることができる。すなわち、十分小さいｋ１、ｋ２の値を得ることができる。
【００６６】
次に、楕円暗号演算装置について説明する。
【００６７】
図５は、実施の形態１における楕円暗号演算装置の構成を示す図である。
【００６８】
図５において、楕円暗号演算装置６００（楕円曲線スカラー倍演算装置の一例である）は、パラメータ入力部６１０、分割値入力部６２０、スカラー倍演算部６３０、スカラー倍出力部６４０、記憶部６５０、制御部６６０、ベクトル演算装置４００、分割値演算装置５００を備えている。ベクトル演算装置４００と分割値演算装置５００とは、別の装置として構成しても構わない。
【００６９】
パラメータ入力部６１０は、スカラーＫと楕円曲線上の点をパラメータとして入力する。
【００７０】
分割値入力部６２０は、上記分割値演算装置５００により演算された秘密鍵となるスカラーＫの分割値ｋ１とｋ２とを入力する。
【００７１】
スカラー倍演算部６３０は、上記分割値入力部６２０により入力された分割値ｋ１とｋ２とを用いて、上記パラメータ入力部６１０により入力されたパラメータをスカラーＫ倍演算する。
【００７２】
記憶部６５０は、上記各部により入力された値、計算或いは演算された値、出力された値を記憶する。記憶部６５０は、ベクトル演算装置４００の記憶部４１２と分割値演算装置５００の記憶部５０６とを兼ねていても構わない。
【００７３】
制御部６６０は、各部を制御する。ここで、図５では、全体を制御する制御部６６０を備えているが、各部ごとに自己を制御する機構を備えても構わない。また、制御部６６０は、ベクトル演算装置４００の制御部４１３と分割値演算装置５００の制御部５０７とを兼ねていても構わない。
【００７４】
スカラー倍出力部６４０は、上記スカラー倍演算部６３０により演算された結果を公開鍵として出力する。スカラー倍出力部６４０は、各演算部、或いは計算部から入力した結果を出力してもよいし、記憶部６５０に記憶された結果を出力しても構わない。
【００７５】
以上のように、最良のＫの分割、すなわち、十分小さいｋ１、ｋ２の値を用いることにより、スカラー倍演算を高速に行うこと、つまり、楕円暗号演算を高速に行うことができる。
【００７６】
以上のように、実施の形態１では、楕円暗号演算を行う方法であって、特殊な準同型写像を用いて定数倍点を計算する方法を説明した。
【００７７】
実施の形態２．
実施の形態１の説明において「〜部」として説明したものは、一部或いはすべてコンピュータで動作可能なプログラムにより構成することができる。これらのプログラムは、例えば、Ｃ言語により作成することができる。或いは、ＨＴＭＬやＳＧＭＬやＸＭＬを用いても構わない。或いは、ＪＡＶＡ（登録商標）を用いて画面表示を行っても構わない。
【００７８】
また、実施の形態１の説明において「〜部」として説明したものは、以下に説明するＲＯＭ３９に記憶されたファームウェアで実現されていても構わない。或いは、ソフトウェア或いは、ハードウェア或いは、ソフトウェアとハードウェアとファームウェアとの組み合わせで実施されても構わない。
【００７９】
また、上記実施の形態１を実施させるプログラムは、また、磁気ディスク装置、ＦＤ（Ｆｌｅｘｉｂｌｅ  Ｄｉｓｋ）、光ディスク、ＣＤ（コンパクトディスク）、ＭＤ（ミニディスク）、ＤＶＤ（Ｄｉｇｉｔａｌ  Ｖｅｒｓａｔｉｌｅ  Ｄｉｓｋ）等のその他の記録媒体による記録装置を用いても構わない。
【００８０】
実施の形態２では、以下に、実施の形態１の説明において「〜部」として説明したものは、一部或いはすべてコンピュータで動作可能なプログラムにより、ベクトル演算装置、分割値演算装置或いは楕円暗号演算装置を構成する場合について説明する。
【００８１】
図６は、実施の形態２における楕円暗号演算装置の外観を示す図である。
【００８２】
図６において、ＣＲＴ（Ｃａｔｈｏｄｅ  Ｒａｙ  Ｔｕｂｅ）表示装置４１、キーボード（Ｋ／Ｂ）４２、マウス４３、コンパクトディスク装置（ＣＤＤ）８６、プリンタ装置８７、スキャナ装置８８は、パーソナルコンピュータ（ＰＣ）３３にケーブルで接続されている。
【００８３】
図７は、実施の形態２における楕円暗号演算装置のハードウェア構成図である。
【００８４】
図７において、プログラムを実行するＣＰＵ（Ｃｅｎｔｒａｌ  Ｐｒｏｃｅｓｓｉｎｇ
Ｕｎｉｔ）３７は、バス３８を介してＲＯＭ（Ｒｅａｄ  Ｏｎｌｙ  Ｍｅｍｏｒｙ）３９、ＲＡＭ（Ｒａｎｄｏｍ  Ａｃｃｅｓｓ  Ｍｅｍｏｒｙ）４０、ＣＲＴ表示装置４１、Ｋ／Ｂ４２、マウス４３、通信ボード４４、ＦＤＤ（Ｆｌｅｘｉｂｌｅ  Ｄｉｓｋ  Ｄｒｉｖｅ）４５、磁気ディスク装置４６、ＣＤＤ８６、プリンタ装置８７、スキャナ装置８８と接続されている。通信ボード４４は、インターネット３０に接続されている。
【００８５】
この実施の形態に係るベクトル演算方法は、楕円曲線上の点をスカラーＫ倍するために用いるスカラーＫの分割値ｋ１とｋ２とを求めるために用いる、ベクトルＶ１とベクトルＶ２とを演算するベクトル演算方法において、
拡張ユークリッド互除法を用いてベクトルＶ１をＣＰＵ（Ｃｅｎｔｒａｌ  Ｐｒｏｃｅｓｓｉｎｇ  Ｕｎｉｔ）に演算させるベクトルＶ１演算工程と、
上記ベクトルＶ１演算工程によりＣＰＵが演算させられたベクトルＶ１を記憶装置に記憶するベクトルＶ１記憶工程と、
拡張ユークリッド互除法を用いて、ＣＰＵに整数の複数の集合Ａｈを演算させ、演算させられた整数の複数の集合Ａｈに含まれる複数の整数値αを用いてベクトルＶ２をＣＰＵに演算させるベクトルＶ２演算工程と、
上記ベクトルＶ２演算工程によりＣＰＵが演算させられたベクトルＶ２を記憶装置に記憶するベクトルＶ２記憶工程と、
上記ベクトルＶ１演算工程により演算され、上記記憶装置に記憶されたベクトルＶ１と上記ベクトルＶ２演算工程により演算され、上記記憶装置に記憶されたベクトルＶ２とを出力装置に出力する出力工程と
を備えたことを特徴とする。
【００８６】
ここで、通信ボード４４は、インターネット３０に限らず、ＬＡＮ（ローカルエリアネットワーク）、或いはＩＳＤＮ等のＷＡＮ（ワイドエリアネットワーク）に接続されていても構わない。
【００８７】
磁気ディスク装置４６には、オペレーティングシステム（ＯＳ）４７、ウィンドウシステム４８、プログラム群４９、ファイル群５０が記憶されている。プログラム群４９は、ＣＰＵ３７、ＯＳ４７、ウィンドウシステム４８により実行される。
【００８８】
実施の形態１の説明において「〜部」として説明したものをすべてプログラムにより構成する場合、上記プログラム群４９には、実施の形態１の説明において「〜部」として説明したものにより実行されるプログラムがソフトウェアとして記憶されている。ファイル群には、上記実施の形態１の説明において、入力部において入力された値、各演算部、各計算部において演算或いは計算された値が記憶されている。或いは、ファームウェアとして、ＲＯＭ３９に記憶される。
【００８９】
また、実施の形態１の説明において「〜部」として説明したものをハードウェアで実現する場合、例えば、Ｋ／Ｂ４２、マウス４３、通信ボード４４、ＦＤＤ４５、ＣＤＤ８６、スキャナ装置８８は、各装置の入力部の一例となる。また、ＣＲＴ表示装置４１、Ｋ／Ｂ４２、マウス４３、通信ボード４４、ＦＤＤ４５、ＣＤＤ８６、プリンタ装置８７は、各装置の出力部の一例となる。また、ＣＰＵ３７は、各装置の各演算部、各計算部の一例となる。出力部は、ＣＲＴ表示装置４１以外の出力装置を用いても構わない。
【００９０】
また、上述したように、実施の形態１の説明において「〜部」として説明したものをソフトウェアとハードウェアとファームウェアとの組み合わせで実施されても構わない。
【００９１】
以上のように、上記実施の形態では、楕円暗号演算装置であって、楕円曲線有理点群位数ｎとスカラー倍数λとを入力する入力手段と、基底Ｖ１を計算する計算手段と、候補となるαの集合Ａｈを計算する計算手段と、基底Ｖ２を計算する計算手段と、計算結果を出力する出力手段とを備えたことにより、上記従来技術で用いられた分割Ｋ＝ｋ１＋ｋ２φ（又はｋ１＋ｋ２λ）で、ｋ１、ｋ２の値をより小さくすることができる。このことにより、スカラー倍演算を高速に行うこと、つまり、楕円暗号演算を高速に行うことが可能になる。
【００９２】
以上のように、上記実施の形態では、従来法では、まだ改善の余地が残されていた楕円曲線暗号演算法に対して、更なる高速化を得ることを可能にし、計算資源が限られた環境においても、十分な実用性を発揮する暗号機能を実現可能にすることができるＶ１、Ｖ２を探索することができる。
【産業上の利用可能性】
【００９３】
最良のＫの分割、すなわち、十分小さいｋ１、ｋ２の値を用いることにより、スカラー倍演算を高速に行うこと、計算時間を短くすること、つまり、楕円暗号演算を高速に行うことができることにより、クロックの小さいＣＰＵしか搭載していない、或いはできないＩＣカード上での暗号演算実行や、ユビキタス環境での情報セキュリティ確保のため、メ
モリ或いは計算時間といった計算リソースが制限された環境での使用が可能となる。
【図面の簡単な説明】
【００９４】
【図１】実施の形態１におけるベクトル演算装置の構成を示す図である。
【図２】実施の形態１におけるベクトル演算方法のフローチャートを示す図である。
【図３】実施の形態１における分割値演算装置の構成を示す図である。
【図４】実施の形態１における分割値演算方法のフローチャートを示す図である。
【図５】実施の形態１における楕円暗号演算装置の構成を示す図である。
【図６】実施の形態２における楕円暗号演算装置の外観を示す図である。
【図７】実施の形態２における楕円暗号演算装置のハードウェア構成図である。
【符号の説明】
【００９５】
３０  インターネット、３３  ＰＣ、３７  ＣＰＵ、３８  バス、３９  ＲＯＭ、４０
ＲＡＭ、４１  ＣＲＴ表示装置、４２  Ｋ／Ｂ、４３  マウス、４４  通信ボード、４５  ＦＤＤ、４６  磁気ディスク装置、４７  ＯＳ、４８  ウィンドウシステム、４９  プログラム群、５０  ファイル群、８６  ＣＤＤ、８７  プリンタ装置、８８  スキャナ装置、４００  ベクトル演算装置、４０１  入力部、４０２  ベクトルＶ１演算部、４０３，４０４，４０５，４０６，４０７，４０８，４０９，４１０  計算部、４１１  出力部、４１２  記憶部、４１３  制御部、４２０  ベクトルＶ２演算部、５００  分割値演算装置、５０１  入力部、５０２，５０３，５０４  計算部、５０５  出力部、５０６  記憶部、５０７  制御部、５２０  分割値演算部、６００  楕円暗号演算装置、６１０  パラメータ入力部、６２０  分割値入力部、６３０  スカラー倍演算部、６４０  スカラー倍出力部、６５０  記憶部、６６０  制御部。
【図１】
0004629972.tif 000002
【図２】
0004629972.tif 000003
【図３】
0004629972.tif 000004
【図４】
0004629972.tif 000005
【図５】
0004629972.tif 000006
【図６】
0004629972.tif 000007
【図７】
0004629972.tif 000008