(57)【特許請求の範囲】
【請求項１】
ｐを２以上の素数とする有限体ＧＦ（ｐ）のｍ次拡大体であるＧＦ（ｐｍ）上で定義された楕円曲線Ｅ／ＧＦ（ｐｍ）上のベースポイントＰのスカラーｋ倍算を行う楕円曲線暗号演算装置であって、
上記ベースポイントＰを基にしてフロベニウス写像φを用いた式として定義される、楕円曲線Ｅ／ＧＦ（ｐｍ）上の、無限遠点Ｏを含む２ｍ個の参照点Ｐｕ（ｕ＝０，１，…，２ｍ−２，２ｍ−１）
【数１】
0004861272.tif 000015
をそれぞれ求めて、式Σｉ＝０ｍ−１ｕｉφｉ（Ｐ）と参照点Ｐｕとを各ｕごとに対応させた事前計算テーブルを生成する事前計算テーブル生成手段と、
ｒをｌｏｇ２（ｐ−１）の整数部分以上の整数として、上記ベースポイントＰのスカラーｋ倍算ｋ×Ｐを、非負整数の展開係数を用いてφ進展開して、該非負整数の展開係数をバイナリ展開することにより得られる展開式
【数２】
0004861272.tif 000016
を満たすｃｉｊ（ｉ＝０，…ｍ−１，ｊ＝０，…，ｒ）を求めるφ進展開手段と、
上記求まったｃｉｊから定まる各式Ｐ♯ｃ（ｊ）に対応する参照点Ｐｃ（ｊ）を上記生成された事前演算テーブルを参照してそれぞれ求める参照点列生成手段と、
上記参照して求まった参照点Ｐｃ（ｊ）の列｛Ｐｃ（ｒ），Ｐｃ（ｒ−１），…，Ｐｃ（１），Ｐｃ（０）｝（以下、参照点列とする。）の中の１つまたは連続する複数の参照点Ｐｃ（ｊ）（ｊはＪ２≧ｊ≧Ｊ１を満たす整数、Ｊ２，Ｊ１はｒ≧Ｊ２≧Ｊ１≧１を満たす整数、Ｐｃ（Ｊ１−１）≠Ｏとする。）が無限遠点Ｏである場合には、ｊ＝Ｊ２の参照点Ｐｃ（ｊ）を点Ｐｃ（Ｊ１−１）に変換すると共に、Ｊ２−１≧ｊ≧Ｊ１−１の各参照点Ｐｃ（ｊ）を点−Ｐｃ（Ｊ１−１）に変換する第一参照点列変換手段と、
上記展開式の各式Ｐ♯ｃ（ｊ）（ｊ＝０，…，ｒ）に、上記参照して求まった参照点Ｐｃ（ｊ）、又は、上記参照して求まった参照点Ｐｃ（ｊ）が上記第一参照点列変換手段により変換された場合には上記変換された点、をそれぞれ代入した式を、楕円２倍算と楕円加算とを交互に行うことにより計算するメイン計算手段と、
を備え、
上記参照点列の中の１つまたは連続する複数の参照点Ｐｃ（ｊ）（ｊはＪ３≧ｊ≧０を満たす整数、Ｊ３はｒ≧Ｊ３≧０を満たす整数とする。）が無限遠点Ｏである場合には、ｊ＝Ｊ３の参照点Ｐｃ（ｊ）を上記楕円曲線Ｅ／ＧＦ（ｐｍ）上の無限遠点Ｏではない任意の点Ｐ’に変換すると共に、Ｊ３≧１である場合にはＪ３−１≧ｊ≧０の各参照点Ｐｃ（ｊ）を点−Ｐ’に変換する第二参照点列変換手段、をさらに備え、
上記メイン計算手段は、上記展開式の各式Ｐ♯ｃ（ｊ）（ｊ＝０，…，ｒ）に、上記参照して求まった参照点Ｐｃ（ｊ）、又は、上記参照して求まった参照点Ｐｃ（ｊ）が上記第一参照点列変換手段又は上記第二参照点列変換手段により変換された場合には上記変換された点、をそれぞれ代入した式を、楕円２倍算と楕円加算とを交互に行うことにより計算し、その計算結果に点−Ｐ’を加算する手段である、
ことを特徴とする楕円曲線暗号演算装置。
【請求項２】
ｐを２以上の素数とする有限体ＧＦ（ｐ）のｍ次拡大体であるＧＦ（ｐｍ）上で定義された楕円曲線Ｅ／ＧＦ（ｐｍ）上のベースポイントＰのスカラーｋ倍算を行う楕円曲線暗号演算方法であって、
事前計算テーブル生成手段が、上記ベースポイントＰを基にしてフロベニウス写像φを用いた式として定義される、楕円曲線Ｅ／ＧＦ（ｐｍ）上の、無限遠点Ｏを含む２ｍ個の参照点Ｐｕ（ｕ＝０，１，…，２ｍ−２，２ｍ−１）
【数３】
0004861272.tif 000017
をそれぞれ求めて、式Σｉ＝０ｍ−１ｕｉφｉ（Ｐ）と参照点Ｐｕとを各ｕごとに対応させた事前計算テーブルを生成する事前計算テーブル生成ステップと、
φ進展開手段が、ｒをｌｏｇ２（ｐ−１）の整数部分以上の整数として、上記ベースポイントＰのスカラーｋ倍算ｋ×Ｐを、非負整数の展開係数を用いてφ進展開して、該非負整数の展開係数をバイナリ展開することにより得られる展開式
【数４】
0004861272.tif 000018
を満たすｃｉｊ（ｉ＝０，…ｍ−１，ｊ＝０，…，ｒ）を求めるφ進展開ステップと、
参照点列生成手段が、上記求まったｃｉｊから定まる各式Ｐ♯ｃ（ｊ）に対応する参照点Ｐｃ（ｊ）を上記生成された事前演算テーブルを参照してそれぞれ求める参照点列生成ステップと、
第一参照点列変換手段が、上記参照して求まった参照点Ｐｃ（ｊ）の列｛Ｐｃ（ｒ），Ｐｃ（ｒ−１），…，Ｐｃ（１），Ｐｃ（０）｝（以下、参照点列とする。）の中の１つまたは連続する複数の参照点Ｐｃ（ｊ）（ｊはＪ２≧ｊ≧Ｊ１を満たす整数、Ｊ２，Ｊ１はｒ≧Ｊ２≧Ｊ１≧１を満たす整数、Ｐｃ（Ｊ１−１）≠Ｏとする。）が無限遠点Ｏである場合には、ｊ＝Ｊ２の参照点Ｐｃ（ｊ）を点Ｐｃ（Ｊ１−１）に変換すると共に、Ｊ２−１≧ｊ≧Ｊ１−１の各参照点Ｐｃ（ｊ）を点−Ｐｃ（Ｊ１−１）に変換する第一参照点列変換ステップと、
メイン計算手段が、上記展開式の各式Ｐ♯ｃ（ｊ）（ｊ＝０，…，ｒ）に、上記参照して求まった参照点Ｐｃ（ｊ）、又は、上記参照して求まった参照点Ｐｃ（ｊ）が上記第一参照点列変換ステップにより変換された場合には上記変換された点、をそれぞれ代入した式を、楕円２倍算と楕円加算とを交互に行うことにより計算するメイン計算ステップと、
を有し、
第二参照点列変換手段が、上記参照点列の中の１つまたは連続する複数の参照点Ｐｃ（ｊ）（ｊはＪ３≧ｊ≧０を満たす整数、Ｊ３はｒ≧Ｊ３≧０を満たす整数とする。）が無限遠点Ｏである場合には、ｊ＝Ｊ３の参照点Ｐｃ（ｊ）を上記楕円曲線Ｅ／ＧＦ（ｐｍ）上の無限遠点Ｏではない任意の点Ｐ’に変換すると共に、Ｊ３≧１である場合にはＪ３−１≧ｊ≧０の各参照点Ｐｃ（ｊ）を点−Ｐ’に変換する第二参照点列変換ステップ、をさらに有し、
上記メイン計算ステップは、上記展開式の各式Ｐ♯ｃ（ｊ）（ｊ＝０，…，ｒ）に、上記参照して求まった参照点Ｐｃ（ｊ）、又は、上記参照して求まった参照点Ｐｃ（ｊ）が上記第一参照点列変換ステップ又は上記第二参照点列変換ステップにより変換された場合には上記変換された点、をそれぞれ代入した式を、楕円２倍算と楕円加算とを交互に行うことにより計算し、その計算結果に点−Ｐ’を加算するステップである、
ことを特徴とする楕円曲線暗号演算方法。
【請求項３】
請求項１に記載の楕円曲線暗号演算装置の各手段としてコンピュータを機能させるための楕円曲線暗号演算装置プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
この発明は、情報セキュリティ技術に関する。特に、有限体上定義された楕円曲線上の点についてスカラーｋ倍算を行う際の、電力解析法等による実装攻撃を防止する楕円曲線暗号演算装置、方法、プログラムに関する。
【背景技術】
【０００２】
ｐを３以上の素数とする有限体ＧＦ（ｐ）のｍ次拡大体であるＧＦ（ｐｍ）上で定義された楕円曲線Ｅ／ＧＦ（ｐｍ）上のベースポイントＰのスカラーｋ倍算ｋ×Ｐを行う楕円曲線演算方法として、次のような方法が知られている。
【０００３】
ｋ×Ｐをフロベニウス写像を用いてφ進展開した式の各項に、予め生成した事前計算テーブルを参照して楕円曲線Ｅ／ＧＦ（ｐｍ）上の参照点を代入する。そして、楕円２倍算と楕円加算とを交互に繰り返すことにより、ｋ×Ｐを計算する方法である（例えば、特許文献１及び特許文献２参照。）。
【特許文献１】特許第３１４５３６８号公報
【特許文献２】特許第３６０４１２６号公報
【発明の開示】
【発明が解決しようとする課題】
【０００４】
一般に楕円２倍算の処理と楕円加算の処理とでは、楕円加算の処理の方が重く、消費電力が大きいことが知られている。このため、参照点に無限遠点Ｏが含まれていない場合には、楕円２倍算と楕円加算とが交互に繰り返されることにより、図５Ａに例示するように消費電力が小さい波形と消費電力が大きい波形とが交互に続く。一方、参照点に無限遠点Ｏが含まれている場合には、参照点が無限遠点Ｏである箇所で楕円加算が行われないため、その箇所で楕円２倍算が続く。このため、図５Ｂに例示するように消費電力が小さい波形が続く。図５Ａ，Ｂの縦軸は消費電力、横軸は時間を表す。
【０００５】
したがって、消費電力が小さい波形が続く箇所を調べることにより、無限遠点Ｏである参照点を知ることができる。無限遠点Ｏである参照点についての情報は、秘密鍵であるスカラー倍指数ｋの解読を容易にする。すなわち、無限遠点Ｏである参照点が判明するほど、秘密鍵であるスカラー倍指数ｋの探索空間が狭まり、安全性が低下するという問題がある。この攻撃方法は、単純電力解析法（SPA:Simple Power Analysis）として知られている。
【０００６】
この発明は、単純電力解析法に対して耐性を有する楕円曲線暗号演算装置、方法、プログラムを提供することを目的とする。
【課題を解決するための手段】
【０００７】
本発明によれば、ｐを２以上の素数とする有限体ＧＦ（ｐ）のｍ次拡大体であるＧＦ（ｐｍ）上で定義された楕円曲線Ｅ／ＧＦ（ｐｍ）上のベースポイントＰのスカラーｋ倍算を行うために、事前計算テーブル生成手段が、ベースポイントＰを基にしてフロベニウス写像φを用いた式として定義される、楕円曲線Ｅ／ＧＦ（ｐｍ）上の、無限遠点Ｏを含む２ｍ個の参照点Ｐｕ（ｕ＝０，１，…，２ｍ−２，２ｍ−１）
【０００８】
【数５】
0004861272.tif 000002
をそれぞれ求めて、式Σｉ＝０ｍ−１ｕｉφｉ（Ｐ）と参照点Ｐｕとを各ｕごとに対応させた事前計算テーブルを生成する。φ進展開手段が、ｒをｌｏｇ２（ｐ−１）の整数部分以上の整数として、ベースポイントＰのスカラーｋ倍算ｋ×Ｐを、非負整数の展開係数を用いてφ進展開して、該非負整数の展開係数をバイナリ展開することにより得られる展開式
【０００９】
【数６】
0004861272.tif 000003
を満たすｃｉｊ（ｉ＝０，…ｍ−１，ｊ＝０，…，ｒ）を求める。参照点列生成手段が、求まったｃｉｊから定まる各式Ｐ♯ｃ（ｊ）に対応する参照点Ｐｃ（ｊ）を生成された事前演算テーブルを参照してそれぞれ求める。第一参照点列変換手段が、上記参照して求まった参照点Ｐｃ（ｊ）の列｛Ｐｃ（ｒ），Ｐｃ（ｒ−１），…，Ｐｃ（１），Ｐｃ（０）｝（以下、参照点列とする。）の中の１つまたは連続する複数の参照点Ｐｃ（ｊ）（ｊはＪ２≧ｊ≧Ｊ１を満たす整数、Ｊ２，Ｊ１はｒ≧Ｊ２≧Ｊ１≧１を満たす整数、Ｐｃ（Ｊ１−１）≠Ｏとする。）が無限遠点Ｏである場合には、ｊ＝Ｊ２の参照点Ｐｃ（ｊ）を点Ｐｃ（Ｊ１−１）に変換すると共に、Ｊ２−１≧ｊ≧Ｊ１−１の各参照点Ｐｃ（ｊ）を点−Ｐｃ（Ｊ１−１）に変換する。メイン計算手段が、展開式の各式Ｐ♯ｃ（ｊ）（ｊ＝０，…，ｒ）に、参照して求まった参照点Ｐｃ（ｊ）、又は、参照して求まった参照点Ｐｃ（ｊ）が第一参照点列変換手段により変換された場合には変換された点、をそれぞれ代入した式を、楕円２倍算と楕円加算とを交互に行うことにより計算する。
また、第二参照点列変換手段が、参照点列の中の１つまたは連続する複数の参照点Ｐｃ（ｊ）（ｊはＪ３≧ｊ≧０を満たす整数、Ｊ３はｒ≧Ｊ３≧０を満たす整数とする。）が無限遠点Ｏである場合には、ｊ＝Ｊ３の参照点Ｐｃ（ｊ）を楕円曲線Ｅ／ＧＦ（ｐｍ）上の無限遠点Ｏではない任意の点Ｐ’に変換すると共に、Ｊ３≧１である場合にはＪ３−１≧ｊ≧０の各参照点Ｐｃ（ｊ）を点−Ｐ’に変換し、メイン計算手段は、展開式の各式Ｐ♯ｃ（ｊ）（ｊ＝０，…，ｒ）に、参照して求まった参照点Ｐｃ（ｊ）、又は、参照して求まった参照点Ｐｃ（ｊ）が第一参照点列変換手段又は第二参照点列変換手段により変換された場合には変換された点、をそれぞれ代入した式を、楕円２倍算と楕円加算とを交互に行うことにより計算し、その計算結果に点−Ｐ’を加算する。
【発明の効果】
【００１０】
参照点列中の一部又は全部の無限遠点Ｏを、無限遠点Ｏ以外の楕円曲線Ｅ／Ｇ（ｐｍ）上の点に置き換えることにより、楕円２倍算が続く箇所の数を少なくすること又はなくすことができる。これにより、消費電力の波形の変化の態様がより一定となり、秘密鍵であるスカラー倍指数ｋの解読を困難にする。
【発明を実施するための最良の形態】
【００１１】
［第一実施例］
図１，２を参照して、この発明の一実施例である楕円曲線暗号演算装置１０について説明をする。図１は、楕円曲線暗号演算装置１０の機能構成を例示する図である。図１に例示するように、楕円曲線暗号演算装置１０は、記憶部１、事前計算テーブル生成部２、事前計算テーブル記憶部３、φ進展開部４、参照点列生成部５、第一参照点列変換部６、メイン計算部８からなる。図２は、楕円曲線暗号演算装置１０の処理の流れを例示するフローチャートである。
【００１２】
楕円曲線暗号演算装置１０は、ｐを２以上の素数とする有限体ＧＦ（ｐ）のｍ次拡大体であるＧＦ（ｐｍ）上で定義された楕円曲線Ｅ／ＧＦ（ｐｍ）上の点Ｐ（以下、点ＰをベースポイントＰとも呼ぶ。）についてスカラーｋ倍算を行い、すなわち、ｋ×Ｐの計算を行う装置である。
【００１３】
記憶部１には、有限体パラメータである標数ｐ及び拡大次数ｍ、楕円パラメータＥが記憶されている。楕円パラメータＥとは、例えば、無限遠点をＯとして、楕円曲線Ｅ／ＧＦ（ｐｍ）を
Ｅ／ＧＦ（ｐｍ）＝｛（ｘ，ｙ）∈ＧＦ（ｐｍ）２｜ｙ２＝ｘ３＋ａｘ＋ｂ｝∪Ｏ
と表した場合のａ，ｂ∈ＧＦ（ｐｍ）のことである。ただし、ａ，ｂは４ａ３＋２７ｂ２≠０の関係を満たす。
【００１４】
標数ｐが大きければ大きいほど、セキュリティの強度を確保するために必要とされる拡大次数ｍを小さくすることができ、これにより後述する事前計算テーブルのサイズを小さくすることができる。例えば、標数ｐをＣＰＵのレジスタサイズに合わせて最適化したある程度大きな値とする。例えば、６４ビットＣＰＵであれば、標数ｐ＝２６１−１とする。この場合、拡大次数ｍ＝５とすれば十分なセキュリティの強度を確保することができる。拡大次数ｍ＝５の場合、後述する事前計算テーブルに登録される参照点の数は高々２５＝３２個となる。
【００１５】
＜ステップＳ１＞
事前計算テーブル生成部２は、入力されたベースポイントＰを基にしてフロベニウス（Frobenius）写像φを用いて下記の展開式により定義される、楕円曲線Ｅ／ＧＦ（ｐｍ）上の無限遠点Ｏを含む２ｍ個の参照点Ｐｕ（ｕ＝０，１，…，２ｍ−２，２ｍ−１）を求める。すなわち、式Σｉ＝０ｍ−１ｕｉφｉ（Ｐ）に対応する参照点Ｐｕを各ｕごとにそれぞれ求める。その際必要に応じて、記憶部１から有限体パラメータである標数ｐ及び拡大次数ｍ、楕円パラメータＥが読み込まれる。
【００１６】
【数７】
0004861272.tif 000004
フロベニウス写像φは、ｘ，ｙ∈ＧＦ（ｐｍ）として、φ：（ｘ，ｙ）→（ｘｐ，ｙｐ）により定義される写像である。一般に、楕円曲線上の点Ｐ，Ｑに対して、φ（Ｐ＋Ｑ）＝φ（Ｐ）＋φ（Ｑ）という性質と、Σｉ＝０ｍ−１φｉ（Ｐ）＝Ｏという性質とを持つ。これらの性質を用いると、参照点Ｐｕの計算が容易となる。
【００１７】
例えば、ｍ＝５のとき、以下のように各Ｐｕ（ｕ＝０，１，…，３０，３１）をそれぞれ求めることができる。
【００１８】
Ｐ０＝Ｏ
Ｐ１＝φ０（Ｐ）＝Ｐ
Ｐ２＝φ１（Ｐ）＝φ（Ｐ）
Ｐ３＝φ１（Ｐ）＋φ０（Ｐ）＝φ（Ｐ）＋Ｐ
Ｐ４＝φ２（Ｐ）＝φ（φ（Ｐ））＝φ（Ｐ２）
Ｐ５＝φ２（Ｐ）＋φ０（Ｐ）＝φ（Ｐ２）＋Ｐ
Ｐ６＝φ２（Ｐ）＋φ１（Ｐ）＝φ（φ１（Ｐ）＋φ０（Ｐ））＝φ（Ｐ３）
Ｐ７＝φ２（Ｐ）＋φ１（Ｐ）＋φ０（Ｐ）＝−φ４（Ｐ）−φ３（Ｐ）＋φ４（Ｐ）＋φ３（Ｐ）＋φ２（Ｐ）＋φ１（Ｐ）＋φ０（Ｐ）＝−φ４（Ｐ）−φ３（Ｐ）＝−φ３（φ（Ｐ）＋Ｐ）＝−φ３（Ｐ３）
…
Ｐ３０＝φ４（Ｐ）＋φ３（Ｐ）＋φ２（Ｐ）＋φ１（Ｐ）＝φ４（Ｐ）＋φ３（Ｐ）＋φ２（Ｐ）＋φ１（Ｐ）＋φ０（Ｐ）−φ０（Ｐ）＝−φ０（Ｐ）＝−Ｐ
Ｐ３１＝φ４（Ｐ）＋φ３（Ｐ）＋φ２（Ｐ）＋φ１（Ｐ）＋φ０（Ｐ）＝Ｏ
Ｐ６の式変形において、φ（Ｐ＋Ｑ）＝φ（Ｐ）＋φ（Ｑ）という上記したフロベニウス写像φの性質を利用している。また、Ｐ７，Ｐ３０，Ｐ３１の式変形において、Σｉ＝０５−１φｉ（Ｐ）＝φ４（Ｐ）＋φ３（Ｐ）＋φ２（Ｐ）＋φ１（Ｐ）＋φ０（Ｐ）＝Ｏという上記したフロベニウス写像φの性質を利用している。
【００１９】
これらのフロベニウス写像φの性質を適宜利用して式Σｉ＝０ｍ−１ｕｉφｉ（Ｐ）を変形することにより、参照点Ｐｕを求めるための楕円加算の回数を減らすことができる。
【００２０】
このように、事前計算テーブル生成部２は、各式Σｉ＝０ｍ−１ｕｉφｉ（Ｐ）に対応する参照点Ｐｕをそれぞれ求め、これにより、式Σｉ＝０ｍ−１ｕｉφｉ（Ｐ）と参照点Ｐｕとを各ｕごとに対応付けた事前計算テーブルを生成する。生成された事前計算テーブルは、事前計算テーブル記憶部３に記憶される。
【００２１】
＜ステップＳ２＞
φ進展開部４は、ベースポイントＰのスカラーｋ倍算ｋ×Ｐを、非負整数の展開係数を用いてφ進展開して、該非負整数の展開係数をバイナリ展開することにより得られる展開式
【００２２】
【数８】
0004861272.tif 000005
を満たすｃｉｊ（ｉ＝０，…ｍ−１，ｊ＝０，…，ｒ）を求める。求まったｃｉｊは、参照点列生成部５とメイン計算部８に送られる。また、ｒについてもメイン計算部８に送られる。
ｃｉｊを求めるまでの過程を以下に述べる。
【００２３】
まずφ進展開部４はｋ×Ｐを、以下のようにφ進展開する。
【数９】
0004861272.tif 000006
展開係数ｃｉを求めるためにまず、ｋ＝ｘ０＋ｙ０φ（ただし、初期値：ｘ０＝ｋ，ｙ０＝０）を、
ｘ０＋ｙ０φ＝ｃ０＋（ｘ１＋ｙ１φ）φ
ｃ０≡ｋ（ｍｏｄ  ｐ），  −（ｐ−１）／２≦ｃ０≦（ｐ−１）／２
と変換する。φが特性方程式φ２−ｔφ＋ｐ＝０を満たすことを用いると、ｘ１，ｙ１は、
ｘ１＝ｙ０＋ｔ（（ｘ０−ｃ０）／ｐ）
ｙ１＝−（ｘ０−ｃ０）／ｐ
と表される。特性方程式に現れるｔは楕円曲線に固有の値（トレース）であり、♯Ｅ（ＧＦ（ｐｍ））＝ｐ＋１−ｔを満たす。
【００２４】
ｉ＝１，…，Ｍ（Ｍ≦２ｍ＋３）についても、
ｘｉ＋ｙｉφ＝ｃｉ＋（ｘｉ＋１＋ｙｉ＋１φ）φ
ｃｉ≡ｋ（ｍｏｄ  ｐ），  −（ｐ−１）／２≦ｃｉ≦（ｐ−１）／２
ｘｉ＝ｙｉ＋ｔ（（ｘｉ−ｃｉ）／ｐ）
ｙｉ＝−（ｘｉ−ｃｉ）／ｐ
上記の関係が成立する。これらの関係をｘｉ＝０，ｙｉ＝０となるまで繰り返し用いることにより、各展開係数ｃｉを求めることができる（例えば、特許文献１参照。）。
【００２５】
次にφ進展開部４は、展開係数ｃｉの最小値ｃｍｉｎを用いて、各展開係数ｃｉをｃｉ＝ｃｉ−ｃｍｉｎにより非負整数化する。φｍ（Ｐ＄）＝Ｐ＄（ここで、Ｐ＄は楕円曲線上の任意の点）というフロベニウス写像の性質を用いると、
ｉ＝ｍ＋ｊ（０≦ｊ≦ｍ−１）なるｉに対して、φｉ＝φｊ（φｍＰ）＝φｊＰ
ｉ＝２ｍ＋ｊ（０≦ｊ≦３）なるｉに対して、φｉ＝φｊ（φｍ（φｍＰ））＝φｊＰ
が成り立つ。したがって、ｃｉ＝ｃｉ＋ｃｉ＋ｍ＋ｃｉ＋２ｍと書き直せば、Σｉ＝０２ｍ＋３ｃｉφｉＰ＝Σｉ＝０ｍ−１ｃｉφｉＰと変形できる。
【００２６】
【数１０】
0004861272.tif 000007
であるため、各展開係数ｃｉをｃｉ＝ｃｉ−ｃｍｉｎと非負整数化してもｋ×Ｐの計算結果は変わらない。
【００２７】
最後にφ進展開部４は、展開係数ｃｉをｃｉ＝Σｊ＝０ｒ２ｊｃｉｊ，ｃｉｊ＝｛０，１｝とバイナリ展開して、ｋ×Ｐを以下のように表す。
【００２８】
【数１１】
0004861272.tif 000008
ただし、式Ｐ♯ｃ（ｊ）は、
【００２９】
【数１２】
0004861272.tif 000009
である。また、ｒは、ｌｏｇ２（ｐ−１）の整数部分以上の整数である。すなわち、ｒは、
【００３０】
【数１３】
0004861272.tif 000010
を満たす整数である。
【００３１】
例えばこのようにして、φ進展開部４は上記（１）式を満たすｃｉｊ（ｉ＝０，…ｍ−１，ｊ＝０，…，ｒ）を求める。
【００３２】
＜ステップＳ３＞
参照点列生成部５は、各式Ｐ♯ｃ（ｊ）（ｊ＝ｒ，ｒ−１，…，１，０）に対応する参照点Ｐｃ（ｊ）を、事前計算テーブル記憶部３に格納された事前計算テーブルを参照してそれぞれ求める。求まった参照点Ｐｃ（ｊ）の列｛Ｐｃ（ｒ），Ｐｃ（ｒ−１），…，Ｐｃ（１），Ｐｃ（０）｝（以下、参照点列とする。）は、第一参照点列変換部６に送られる。
【００３３】
＜ステップＳ４＞
第一参照点列変換部６は、参照点列の中１つ又は連続する参照点Ｐｃ（ｊ）が無限遠点Ｏである場合には、それらの参照点と、それらの参照点の下位側に隣接する参照点とを次のように無限遠点Ｏ以外の点に置き換える。
【００３４】
参照点列中の１つ又は連続する複数の参照点Ｐｃ（Ｊ２）〜参照点Ｐｃ（Ｊ１）が、無限遠点Ｏであるとする。ここで、Ｊ２，Ｊ１は、ｒ≧Ｊ２≧Ｊ１≧１を満たす整数であり、参照点Ｐｃ（Ｊ１−１）≠Ｏとする。この場合、第一参照点列変換部６は、参照点Ｐｃ（Ｊ２）を点Ｐｃ（Ｊ１−１）に変換する。また、第一参照点列変換部６は、参照点Ｐｃ（Ｊ２−１）〜参照点Ｐｃ（Ｊ１−１）を点−Ｐｃ（Ｊ１−１）に変換する。変換された参照点列は、メイン計算部８に送られる。
【００３５】
ｊ＝Ｊ２  →  Ｐｃ（ｊ）＝Ｐｃ（Ｊ１−１）
Ｊ２−１≧ｊ≧Ｊ１−１  →  Ｐｃ（ｊ）＝−Ｐｃ（Ｊ１−１）
以下、図３に例示するように、ｒ＝８であり、事前計算テーブルを参照した結果、（Ｐ♯ｃ（８），Ｐ♯ｃ（７），Ｐ♯ｃ（６），Ｐ♯ｃ（５），Ｐ♯ｃ（４），Ｐ♯ｃ（３），Ｐ♯ｃ（２），Ｐ♯ｃ（１），Ｐ♯ｃ（０））に（Ｐ３，Ｐ０（＝Ｏ），Ｐ０（＝Ｏ），Ｐ０（＝Ｏ），Ｐ７，Ｐ０（＝Ｏ），Ｐ０（＝Ｏ），Ｐ１２，Ｐ６）がそれぞれ対応させられている場合を例に挙げて説明をする。
【００３６】
この参照点列は、（Ｏ，Ｏ，Ｏ，Ｐ７）という参照点のパターンを含む。これらの参照点は、第一参照点列変換部６により、（Ｐ７，−Ｐ７，−Ｐ７，−Ｐ７）と変換される。また、この参照点列は、（Ｏ，Ｏ，Ｐ１２）という参照点のパターンを含む。これらの参照点は、第一参照点列変換部６により、（Ｐ１２，−Ｐ１２，−Ｐ１２）と変換される。
【００３７】
この結果、（Ｐ♯ｃ（８），Ｐ♯ｃ（７），Ｐ♯ｃ（６），Ｐ♯ｃ（５），Ｐ♯ｃ（４），Ｐ♯ｃ（３），Ｐ♯ｃ（２），Ｐ♯ｃ（１），Ｐ♯ｃ（０））に（Ｐ３，Ｐ７，−Ｐ７，−Ｐ７，−Ｐ７，Ｐ１２，−Ｐ１２，−Ｐ１２，Ｐ６）がそれぞれ対応することになる。
【００３８】
このように第一参照点列変換部６により参照点を変換しても、ｋ×Ｐの計算結果が変わらない理由については後述する。
【００３９】
＜ステップＳ５＞
メイン計算部８は、上記（１）式の各式Ｐ♯ｃ（ｊ）（ｊ＝０，…，ｒ）に、事前計算テーブルを参照することにより求まった参照点Ｐｃ（ｊ）、又は、参照点Ｐｃ（ｊ）が第一参照点列変換部６により変換された場合にはその変換された点を代入した式を計算することにより、ｋ×Ｐを計算する。すなわち、上記（１）式の各式Ｐ♯ｃ（ｊ）（ｊ＝０，…，ｒ）に最終的に対応する点を代入した式を計算することにより、ｋ×Ｐを計算する。
【００４０】
参照点列が図３に例示する参照列である場合には、第一参照点列変換部６により参照点が変換された結果、メイン計算部８は、
【００４１】
【数１４】
0004861272.tif 000011
を計算することになる。
【００４２】
メイン計算部８は、例えば、楕円２倍算と楕円加算を繰り返し行う次の処理を行うことにより、上記（１）式の各式Ｐ♯ｃ（ｊ）に参照点Ｐｃ（ｊ）又は変換された点を代入した式を計算する。点Ｐ＊ｃ（ｊ）は、式Ｐ♯ｃ（ｊ）（ｊ＝０，…，ｒ）に最終的に対応する点のことである。下記の処理が終了したときのＱが、ｋ×Ｐの演算結果となる。
【００４３】
Ｑ＝Ｐ＊ｃ（ｒ）
ｆｏｒ  ｊ＝ｒ−１  ｔｏ  ０  ｛
Ｑ＝２Ｑ
Ｑ＝Ｑ＋Ｐ＊ｃ（ｊ）
｝
この実施例によれば、Ｐｃ（０）が無限遠点Ｏでない場合には、各Ｐ＊ｃ（ｊ）は無限遠点Ｏではないため、メイン計算部８は、各Ｐ＊ｃ（ｊ）（ｊ＝ｒ−１，…，０）について、楕円２倍算（Ｑ＝２Ｑ）と楕円加算（Ｑ＝Ｑ＋Ｐ＊ｃ（ｊ））の両方の処理を行う。このため、消費電力の変化の態様が一定となり、攻撃者が単純電力解析をしても秘密鍵であるスカラー倍指数ｋを解読するための情報を得ることはできなくなる。
【００４４】
また、Ｐｃ（０）が無限遠点Ｏである場合には、単純電力解析により無限遠点である参照列Ｐｃ（ｊ）が判明する可能性がある。しかし、無限遠点Ｏであることが判明する可能性があるのは、後述するように、Ｐｃ（０）を含む１つ又は複数の連続する無限遠点である参照点だけであり、依然として秘密鍵であるスカラー倍指数ｋを解読するのは困難である。
【００４５】
これらの点において、この実施例による楕円曲線暗号演算装置は、単純電力解析攻撃に対して耐性を有するということができる。また、フォルト混入させればｋ×Ｐの最終的な結果が変わるため、セーフエラー攻撃も通用しない。
【００４６】
《第一参照点列変換部６により参照点を変換してもｋ×Ｐの計算結果が変わらない理由について》
Σｉ＝０ａ−１２ｉ＝２ａ−１
という等比数列の和の公式がある。これを式変形すると、
２ａ−（２ａ−１＋２ａ−２＋…＋２＋１）＝１
という関係が得られる。したがって、楕円曲線Ｅ／Ｇ（ｐｍ）上の点Ｐ”についても、
２ａＰ”−（２ａ−１＋２ａ−２＋…＋２＋１）Ｐ”＝Ｐ”
という関係が成立する。このため、第一参照点列変換部６により参照点を変換してもｋ×Ｐの計算結果が変わらないのである。
【００４７】
例えば、これを上記式（２）にあてはめると、
【数１５】
0004861272.tif 000012
となり、上記（１）式の各式Ｐ♯ｃ（ｊ）（ｊ＝０，…，ｒ）に、第一参照点列変換部６により変換される前の参照点を代入した式
【００４８】
【数１６】
0004861272.tif 000013
と同値であることがわかる。
【００４９】
［第二実施例］
第二実施例による楕円曲線暗号演算装置は、第一参照点列変換部６により変換された参照点列をさらに変換する第二参照点列変換部７を備え、メイン計算部８が第二参照点列変換部７による参照点列の変換によりｋ×Ｐの計算結果が変化しないように補正をする点で、第一実施例による楕円曲線暗号演算装置１０とは異なる。他の点については、第一実施例による楕円曲線暗号演算装置１０と同様であるため重複説明を省略する。以下、第一実施例と異なる部分について説明をする。
【００５０】
第一参照点列変換部６により変換された参照点列は、第二参照点列変換部７に送られる。例えば、参照点列生成部５により生成された参照点列が図４の上段に例示する参照点列（変換前の参照点列）であるとする。この変換前の参照点列は、第一参照点列変換部６により図４の中段に示す参照点列（変換後１の参照点列）に変換される。
【００５１】
第二参照点列変換部７は、受け取った参照点列の中の１つまたは連続する複数の参照点Ｐｃ（ｊ）（ｊはＪ３≧ｊ≧０を満たす整数、Ｊ３はｒ≧Ｊ３≧０を満たす整数とする。）が無限遠点Ｏである場合には、ｊ＝Ｊ３の参照点Ｐｃ（ｊ）を上記楕円曲線Ｅ／ＧＦ（ｐｍ）上の無限遠点Ｏではない任意の点Ｐ’に変換すると共に、Ｊ３≧１である場合にはＪ３−１≧ｊ≧０の各参照点Ｐｃ（ｊ）を点−Ｐ’に変換する。変換された参照点列は、メイン計算部８に送られる。
【００５２】
例えば、図４の中段に示した（変換後１の参照点列）は、（Ｏ，Ｏ，Ｏ，Ｏ）という参照点のパターンを含む。これらの参照点は、（Ｐ’，−Ｐ’，−Ｐ’，−Ｐ’）とそれぞれ変換される。
【００５３】
この結果、（Ｐ♯ｃ（８），Ｐ♯ｃ（７），Ｐ♯ｃ（６），Ｐ♯ｃ（５），Ｐ♯ｃ（４），Ｐ♯ｃ（３），Ｐ♯ｃ（２），Ｐ♯ｃ（１），Ｐ♯ｃ（０））に（Ｐ３，Ｐ１１，−Ｐ１１，Ｐ６，−Ｐ６，Ｐ’，−Ｐ’，−Ｐ’，−Ｐ’）がそれぞれ対応することになる。
【００５４】
メイン計算部８は、上記式（１）の各式Ｐ♯ｃ（ｊ）（ｊ＝０，…，ｒ）に、参照点列生成部５が参照して求まった参照点Ｐｃ（ｊ）、又は、上記参照して求まった参照点Ｐｃ（ｊ）が第一参照点列変換部６又は第二参照点列変換部７により変換された場合には上記変換された点、をそれぞれ代入した式を楕円２倍算と楕円加算を交互に行うことにより計算して、その計算結果に点−Ｐ’を加算する。
【００５５】
第二参照点列変換部７により参照点を変換した場合に、−Ｐ’を加算する必要がある理由については後述する。
【００５６】
例えば、参照点列が図４に例示する参照点列である場合には、第一参照点列変換部６及び第二参照点列変換部７により参照点が変換された結果、メイン計算部８は、
【００５７】
【数１７】
0004861272.tif 000014
を計算することになる。
【００５８】
この実施例によれば、Ｐｃ（０）が無限遠点Ｏであるかどうかを問わず、各Ｐ＊ｃ（ｊ）は無限遠点Ｏではないため、メイン計算部８は、各Ｐ＊ｃ（ｊ）（ｊ＝ｒ−１，…，０）について、楕円２倍算（Ｑ＝２Ｑ）と楕円加算（Ｑ＝Ｑ＋Ｐ＊ｃ（ｊ））の両方の処理を行う。このため、消費電力の変化の態様が一定となり、攻撃者が単純電力解析をしても秘密鍵であるスカラー倍指数ｋを解読するための情報を得ることはできなくなる。
【００５９】
《第二参照点列変換部７により参照点を変換するとｋ×Ｐの計算結果に−Ｐ’を加算する必要がある理由について》
上記説明したように、楕円曲線Ｅ／Ｇ（ｐｍ）上の点Ｐ”について、
２ａＰ”−（２ａ−１＋２ａ−２＋…＋２＋１）Ｐ”＝Ｐ”
という関係が成立する。このため、第二参照点列変換部７により参照点を変換した場合のｋ×Ｐの計算結果は、第二参照点列変換部７により参照点を変換しなかった場合のｋ×Ｐの計算結果と比較して＋Ｐ’だけずれる。このため、第二参照点列変換部７により参照点を変換するとｋ×Ｐの計算結果に−Ｐ’を加算する必要があるのである。
【００６０】
［変形例等］
有限体パラメータｐ，ｍ、楕円パラメータＥに関わらず、常に、Ｐ０＝Ｏ，Ｐ１＝Ｐ，Ｐ２＾ｍ−２＝−Ｐ，Ｐ２＾ｍ−１＝Ｏである。このため、事前計算テーブル生成部２は、これらの参照点の全部又は一部については事前計算をしなくてもよい。この場合の事前計算テーブルは、これらの参照点の全部又は一部以外の各参照点と、式Σｉ＝０ｍ−１ｕｉφｉ（Ｐ）とをそれぞれ対応付けたものとなる。この場合、参照点列生成部５は、これらの参照点の全部又は一部を求めるために事前計算テーブルを参照しないで、Ｐ０＝Ｏ，Ｐ１＝Ｐ，Ｐ２＾ｍ−２＝−Ｐ，Ｐ２＾ｍ−１＝Ｏであるとして参照点列を生成する。  
【００６１】
上述の構成をコンピュータによって実現する場合、各装置が有すべき機能の処理内容はプログラムによって記述される。そして、このプログラムをコンピュータで実行することにより、上記処理機能がコンピュータ上で実現される。
【００６２】
この処理内容を記述したプログラムは、コンピュータで読み取り可能な記録媒体に記録しておくことができる。コンピュータで読み取り可能な記録媒体としては、例えば、磁気記録装置、光ディスク、光磁気記録媒体、半導体メモリ等どのようなものでもよいが、具体的には、例えば、磁気記録装置として、ハードディスク装置、フレキシブルディスク、磁気テープ等を、光ディスクとして、ＤＶＤ（Digital Versatile Disc）、ＤＶＤ−ＲＡＭ（Random Access Memory）、ＣＤ−ＲＯＭ（Compact Disc Read Only Memory）、ＣＤ
−Ｒ（Recordable）／ＲＷ（ReWritable）等を、光磁気記録媒体として、ＭＯ（Magneto-Optical disc）等を、半導体メモリとしてＥＥＰ−ＲＯＭ（Electronically Erasable and Programmable-Read Only Memory）等を用いることができる。
【００６３】
また、このプログラムの流通は、例えば、そのプログラムを記録したＤＶＤ、ＣＤ−ＲＯＭ等の可搬型記録媒体を販売、譲渡、貸与等することによって行う。さらに、このプログラムをサーバコンピュータの記憶装置に格納しておき、ネットワークを介して、サーバコンピュータから他のコンピュータにそのプログラムを転送することにより、このプログラムを流通させる構成としてもよい。
【００６４】
また、上述した実施形態とは別の実行形態として、コンピュータが可搬型記録媒体から直接このプログラムを読み取り、そのプログラムに従った処理を実行することとしてもよく、さらに、このコンピュータにサーバコンピュータからプログラムが転送されるたびに、逐次、受け取ったプログラムに従った処理を実行することとしてもよい。また、サーバコンピュータから、このコンピュータへのプログラムの転送は行わず、その実行指示と結果取得のみによって処理機能を実現する、いわゆるＡＳＰ（Application Service Provider）型のサービスによって、上述の処理を実行する構成としてもよい。なお、本形態におけるプログラムには、電子計算機による処理の用に供する情報であってプログラムに準ずるもの（コンピュータに対する直接の指令ではないがコンピュータの処理を規定する性質を有するデータ等）を含むものとする。
【００６５】
また、この形態では、コンピュータ上で所定のプログラムを実行させることにより、本装置を構成することとしたが、これらの処理内容の少なくとも一部をハードウェア的に実現することとしてもよい。
【００６６】
また、上述の各種の処理は、記載に従って時系列に実行されるのみならず、処理を実行する装置の処理能力あるいは必要に応じて並列的にあるいは個別に実行されてもよい。その他、本発明の趣旨を逸脱しない範囲で適宜変更が可能であることはいうまでもない。
【図面の簡単な説明】
【００６７】
【図１】楕円曲線暗号装置の一実施例の機能構成を例示する図。
【図２】楕円曲線暗号装置の一実施例の処理の流れを例示する図。
【図３】ｒ＝８の場合の、変換前の参照点列、及び、第一参照点列変換部６による変換後の参照点列を例示する図。
【図４】ｒ＝８の場合の、変換前の参照点列、第一参照点列変換部６による変換後の参照点列、及び、第二参照点列変換部７による変換後の参照点列を例示する図。
【図５】Ａは、参照点列に無限遠点を含まない場合の消費電力の波形を例示する図。Ｂは、参照点列に無限遠点を含む場合の消費電力の波形を例示する図。
【図１】
0004861272.tif 000019
【図２】
0004861272.tif 000020
【図３】
0004861272.tif 000021
【図４】
0004861272.tif 000022
【図５】
0004861272.tif 000023