(57)【特許請求の範囲】
【請求項１】
楕円曲線上の点Ｐを楕円スカラｋ倍した点ｋ×Ｐを求める楕円曲線暗号演算装置であって、
上記点Ｐの位数をｎとして、１＜ｒ＜ｎの予め定められた整数ｒと、上記点Ｐを楕円スカラｒ倍した点Ｓ＝ｒ×Ｐとを、正当権限を有しない外部機器が読み出すことができないように記憶する記憶部と、
１＜α＜ｎの整数の乱数であるαと、上記記憶部から読み込んだ上記整数ｒとを用いて、ｒ’＝αｒ  ｍｏｄ  ｎにより定義される除数ｒ’を生成する除数生成部と、
上記点Ｐを楕円スカラ（ｋ  ｍｏｄ  ｒ’）倍した点（ｋ  ｍｏｄ  ｒ’）×Ｐを求める第一スカラ倍演算部と、
［・］を・の整数部分を出力する床関数として、上記記憶部から読み込んだ上記点Ｓを楕円スカラ［ｋ／ｒ’］α倍した点［ｋ／ｒ’］α×Ｓを求める第二スカラ倍演算部と、
上記点（ｋ  ｍｏｄ  ｒ’）×Ｐと、上記点［ｋ／ｒ’］α×Ｓを加算する加算部と、
を有する楕円曲線暗号演算装置。
【請求項２】
請求項１に記載の楕円曲線暗号演算装置であって、
１＜βの整数である乱数βを用いて、ｋを拡張した拡張スカラ倍指数ｋ’＝ｋ＋βｎを求める拡張スカラ倍指数生成部を更に有し、
上記第一スカラ倍演算部は、上記点Ｐを楕円スカラ（ｋ’  ｍｏｄ  ｒ’）倍した点（ｋ’  ｍｏｄ  ｒ’）×Ｐを求める部であり、
上記第二スカラ倍演算部は、上記点Ｓを楕円スカラ［ｋ’／ｒ’］α倍した点［ｋ’／ｒ’］α×Ｓを求める部であり、
上記加算部は、上記点（ｋ’  ｍｏｄ  ｒ’）×Ｐと、上記点［ｋ’／ｒ’］α×Ｓを加算する部である、
ことを特徴とする楕円曲線暗号演算装置。
【請求項３】
請求項１又は２に記載の楕円曲線暗号演算装置であって、
上記αは、１＜α＜ｎ−１の整数の乱数であり、
Ｌを２以上の整数として、上記ｒはｎ／２Ｌ＜ｒ＜ｎ−ｎ／２Ｌの整数であり、
上記除数ｒ’の値が、ｎ／２Ｌ以上又はより大であるかどうかを判断する判断部と、
上記ｒ’の値がｎ／２Ｌ以上又はより大でないと判断された場合には、上記ｒ’の値を上記ｒ’の値に上記ｒを加算した値に変換すると共に、上記αの値を上記αの値に１を加算した値に変換する変換部と、
を更に有することを特徴とする楕円曲線暗号演算装置。
【請求項４】
請求項１から３の何れかに記載の楕円曲線暗号演算装置であって、
正当権限を有する外部機器から、更新された整数ｒ及び更新された点Ｓを受信する受信部と、
上記更新された整数ｒ及び上記更新された点Ｓで、上記記憶部に記憶された上記整数ｒ及び上記点Ｓを更新する更新部と、
を更に有することを特徴とする楕円曲線暗号演算装置。
【請求項５】
請求項１から３の何れかに記載の楕円曲線暗号演算装置であって、
正当権限を有する外部機器から更新コマンドを受信すると、１＜ｒ＜ｎの整数又はｎ／２Ｌ＜ｒ＜ｎ−ｎ／２Ｌの整数ｒを更新された整数ｒとして選択する整数生成部と、
上記更新された整数ｒを用いて、上記点Ｐの楕円スカラｒ倍点Ｓ＝ｒ×Ｐを更新された点Ｓとして求める第四スカラ倍演算部と、
上記更新された整数ｒ及び上記更新された点Ｓで、上記記憶部に記憶された上記整数ｒ及び上記点Ｓを更新する更新部と、
を更に有することを特徴とする楕円曲線暗号演算装置。
【請求項６】
請求項４に記載の楕円曲線暗号演算装置と、
上記正当権限を有する外部機器と、
を有し、
上記正当権限を有する外部機器は、
１＜ｒ＜ｎの整数又はｎ／２Ｌ＜ｒ＜ｎ−ｎ／２Ｌの整数ｒを更新された整数ｒとして選択する整数生成部と、更新された整数ｒを用いて上記点Ｐの楕円スカラｒ倍点Ｓ＝ｒ×Ｐを更新された点Ｓとして求める第三スカラ倍演算部と、上記更新された整数ｒ及び上記更新された点Ｓを上記楕円曲線暗号演算装置に送る送信部とを有する、
ことを特徴とする楕円曲線暗号演算システム。
【請求項７】
請求項５に記載の楕円曲線暗号演算装置と、
上記正当権限を有する外部機器と、
を有し、
上記正当権限を有する外部機器は、更新コマンドを上記楕円曲線暗号演算装置に送る送信部を有する、
ことを特徴とする楕円曲線暗号演算システム。
【請求項８】
楕円曲線上の点Ｐを楕円スカラｋ倍した点ｋ×Ｐを求める楕円曲線暗号演算方法であって、
記憶部には、上記点Ｐの位数をｎとして、１＜ｒ＜ｎの予め定められた整数ｒと、上記点Ｐを楕円スカラｒ倍した点Ｓ＝ｒ×Ｐとを、正当権限を有しない外部機器が読み出すことができないように記憶されており、
除数生成部が、１＜α＜ｎの整数の乱数であるαと、上記記憶部から読み込んだ上記整数ｒとを用いて、ｒ’＝αｒ  ｍｏｄ  ｎにより定義される除数ｒ’を生成する除数生成ステップと、
第一スカラ倍演算部が、上記点Ｐを楕円スカラ（ｋ  ｍｏｄ  ｒ’）倍した点（ｋ  ｍｏｄ  ｒ’）×Ｐを求める第一スカラ倍演算ステップと、
第二スカラ倍演算部が、［・］を・の整数部分を出力する床関数として、上記記憶部から読み込んだ上記点Ｓを楕円スカラ［ｋ／ｒ’］α倍した点［ｋ／ｒ’］α×Ｓを求める第二スカラ倍演算ステップと、
加算部が、上記点（ｋ  ｍｏｄ  ｒ’）×Ｐと、上記点［ｋ／ｒ’］α×Ｓを加算する加算ステップと、
を有する楕円曲線暗号演算方法。
【請求項９】
請求項８に記載の楕円曲線暗号演算方法であって、
拡張スカラ倍指数生成部が、１＜βの整数である乱数βを用いて、ｋを拡張した拡張スカラ倍指数ｋ’＝ｋ＋βｎを求める拡張スカラ倍指数生成ステップを更に有し、
上記第一スカラ倍演算ステップは、上記点Ｐを楕円スカラ（ｋ’  ｍｏｄ  ｒ’）倍した点（ｋ’  ｍｏｄ  ｒ’）×Ｐを求めるステップであり、
上記第二スカラ倍演算ステップは、上記点Ｓを楕円スカラ［ｋ’／ｒ’］α倍した点［ｋ’／ｒ’］α×Ｓを求めるステップであり、
上記加算ステップは、上記点（ｋ’  ｍｏｄ  ｒ’）×Ｐと、上記点［ｋ’／ｒ’］α×Ｓを加算するステップである、
ことを特徴とする楕円曲線暗号演算方法。
【請求項１０】
請求項８又は９に記載の楕円曲線暗号演算方法であって、
上記αは、１＜α＜ｎ−１の整数の乱数であり、
Ｌを２以上の整数として、上記ｒはｎ／２Ｌ＜ｒ＜ｎ−ｎ／２Ｌの整数であり、
判断部が、上記除数ｒ’の値が、ｎ／２Ｌ以上又はより大であるかどうかを判断する判断ステップと、
変換部が、上記ｒ’の値がｎ／２Ｌ以上又はより大でないと判断された場合には、上記ｒ’の値を上記ｒ’の値に上記ｒを加算した値に変換すると共に、上記αの値を上記αの値に１を加算した値に変換する変換ステップと、
を更に有することを特徴とする楕円曲線暗号演算方法。
【請求項１１】
請求項８から１０の何れかに記載の楕円曲線暗号演算方法であって、
受信部が、正当権限を有する外部機器から、更新された整数ｒ及び更新された点Ｓを受信する受信ステップと、
更新部が、上記更新された整数ｒ及び上記更新された点Ｓで、上記記憶部に記憶された上記整数ｒ及び上記点Ｓを更新する更新ステップと、
を更に有することを特徴とする楕円曲線暗号演算方法。
【請求項１２】
請求項８から１０の何れかに記載の楕円曲線暗号演算方法であって、
整数生成部が、正当権限を有する外部機器から更新コマンドを受信すると、１＜ｒ＜ｎの整数又はｎ／２Ｌ＜ｒ＜ｎ−ｎ／２Ｌの整数ｒを更新された整数ｒとして選択する整数生成ステップと、
第四スカラ倍演算部が、上記更新された整数ｒを用いて、上記点Ｐの楕円スカラｒ倍点Ｓ＝ｒ×Ｐを更新された点Ｓとして求める第四スカラ倍演算ステップと、
更新部が、上記更新された整数ｒ及び上記更新された点Ｓで、上記記憶部に記憶された上記整数ｒ及び上記点Ｓを更新する更新ステップと、
を更に有することを特徴とする楕円曲線暗号演算方法。
【請求項１３】
請求項１１に記載の楕円曲線暗号演算方法と、
上記正当権限を有する外部機器が、１＜ｒ＜ｎの整数又はｎ／２Ｌ＜ｒ＜ｎ−ｎ／２Ｌの整数ｒを更新された整数ｒとして選択する整数生成ステップと、
上記正当権限を有する外部機器が、更新された整数ｒを用いて上記点Ｐの楕円スカラｒ倍点Ｓ＝ｒ×Ｐを更新された点Ｓとして求める第三スカラ倍演算ステップと、
上記正当権限を有する外部機器が、上記更新された整数ｒ及び上記更新された点Ｓを上記受信部に送る送信ステップと、
を有することを特徴とする楕円曲線暗号演算システムの方法。
【請求項１４】
請求項１２に記載の楕円曲線暗号演算方法と、
上記正当権限を有する外部機器が、更新コマンドを上記楕円曲線暗号演算方法に送る送信ステップ、
を有することを特徴とする楕円曲線暗号演算システムの方法。
【請求項１５】
請求項１から５のいずれかに記載の楕円曲線暗号演算装置の各部としてコンピュータを機能させるための楕円曲線暗号演算プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
この発明は、楕円曲線暗号に関する。特に、楕円曲線暗号演算への電力解析攻撃に対する防御技術に関する。
【背景技術】
【０００２】
楕円曲線暗号演算への電力解析攻撃に対する防御技術として、乱数を用いてスカラ倍指数を分離する方法が提案されている（例えば、非特許文献１参照。）。この方法では、楕円スカラ倍算ｋ×Ｐを実行する度に毎回異なる乱数ｒを生成して、この乱数ｒを用いて、スカラ倍指数ｋをｋ→（ｋ−ｒ）＋（ｒ）のように２つの整数に分離する。そして、点Ｐの楕円スカラｋ倍算ｋ×Ｐを、下記の式を計算することにより行う。すなわち、点Ｐの楕円スカラ（ｋ−ｒ）倍点（ｋ−ｒ）×Ｐと、点Ｐの楕円スカラｒ倍点ｒ×Ｐとをそれぞれ計算した後に、これらの計算された点を加算する。
（ｋ−ｒ）×Ｐ＋ｒ×Ｐ
【０００３】
上記の方法の変形として、下記の式により楕円スカラ倍算ｋ×Ｐを行う方法が提案されている（例えば、非特許文献２参照。）。ここで、［・］は、［・］を・の整数部分を出力する床関数である。このように、スカラ倍指数ｋを、スカラ倍指数ｋを乱数ｒで割ったときの余り（ｋ  ｍｏｄ  ｒ）と、商［ｋ／ｒ］をｒ倍した値［ｋ／ｒ］ｒとに分離して、下記の式により楕円スカラ倍算ｋ×Ｐを行う。すなわち、点Ｐの楕円スカラ（ｋ  ｍｏｄ  ｒ）倍点と、点Ｐの楕円スカラ［ｋ／ｒ］ｒ倍点とをそれぞれ計算した後に、これらの計算された点を加算する。
（ｋ  ｍｏｄ  ｒ）×Ｐ＋［ｋ／ｒ］ｒ×Ｐ
【０００４】
これらの２つの方法のように、乱数ｒを用いてスカラ倍指数ｋを２つの整数に分離して楕円スカラ倍算を行うことにより、演算の中間値が楕円スカラ倍算の度に毎回異なる値を取るようにできるため、いわゆる差分電力解析攻撃（ＤＰＡ：Ｄｉｆｆｅｒｅｎｔｉａｌ  Ｐｏｗｅｒ  Ａｎａｌｙｓｉｓ）を防ぐことができる。
【非特許文献１】Christopher Clavier and Marc Joye, 「Universal Exponentiation Algorithm」, CHES 2001, volume 2162 of LNCS, Springer-Verlag, 2001, P.300-308
【非特許文献２】Christopher Clavier and Marc Joye, 「(Virtually) Free Randomization Techniques for Elliptic Curve Cryptography」, ICIS 2003, volume 2836 of LNCS, Springer-Verlag, 2003, P.348-359,
【発明の開示】
【発明が解決しようとする課題】
【０００５】
しかし、上記の２つの方法は、楕円スカラ倍算を行うモジュールがいわゆる単純電力解析攻撃（ＳＰＡ：Ｓｉｍｐｌｅ  Ｐｏｗｅｒ  Ａｎａｌｙｓｉｓ）に対する防御機能を備えていることを前提としている。楕円スカラ倍算を行うモジュールが単純電力解析攻撃に対する防御機能を備えていない場合、攻撃者は、スカラ倍指数ｋをｋ→ｘ１＋ｘ２と分離した結果生じる２つのスカラ倍指数ｘ１，ｘ２を、点Ｐの楕円スカラｘ１倍算ｘ１×Ｐ及び点Ｐの楕円スカラｘ２倍算ｘ２×Ｐのそれぞれ単純電力解析攻撃することにより取得することが可能である。したがって、取得した２つのスカラ倍指数ｘ１，ｘ２から、元の秘密情報であるスカラ倍指数ｋを、ｋ＝ｘ１＋ｘ２により復元することができるという問題があった。
【０００６】
この発明は、上記問題に鑑み、元のスカラ倍指数ｋを復元することができない楕円曲線暗号演算装置、方法及びプログラム並びに楕円曲線暗号演算システム及び方法を提供することを目的とする。
【課題を解決するための手段】
【０００７】
この発明の１つの観点によれば、楕円曲線上の点Ｐを楕円スカラｋ倍した点ｋ×Ｐを求めるために、記憶部には、点Ｐの位数をｎとして、１＜ｒ＜ｎの予め定められた整数ｒと、点Ｐを楕円スカラｒ倍した点Ｓ＝ｒ×Ｐとを、正当権限を有しない外部機器が読み出すことができないように記憶されている。除数生成部が、１＜α＜ｎの整数の乱数であるαと、記憶部から読み込んだ整数ｒとを用いて、ｒ’＝αｒ  ｍｏｄ  ｎにより定義される除数ｒ’を生成する。第一スカラ倍演算部が、点Ｐを楕円スカラ（ｋ  ｍｏｄ  ｒ’）倍した点（ｋ  ｍｏｄ  ｒ’）×Ｐを求める。第二スカラ倍演算部が、［・］を・の整数部分を出力する床関数として、記憶部から読み込んだ点Ｓを楕円スカラ［ｋ／ｒ’］α倍した点［ｋ／ｒ’］α×Ｓを求める。加算部が、点（ｋ  ｍｏｄ  ｒ’）×Ｐと、点［ｋ／ｒ’］α×Ｓを加算する。
【発明の効果】
【０００８】
攻撃者が、点Ｐの楕円スカラ倍算と、点Ｓの楕円スカラ倍算とをそれぞれ単純電力解析攻撃をすることにより得た２つのスカラ倍指数を加算しても、元のスカラ倍指数ｋを復元することはできない。
【発明を実施するための最良の形態】
【０００９】
図面を参照して、この発明の各実施例について説明する。同一の部分には、同じ符号を付けて重複説明を略する。
【実施例１】
【００１０】
図１に示すように、実施例１の楕円曲線暗号演算装置は、記憶部１１、乱数生成部１２、除数生成部１３及びメイン計算部１５を例えば含む。メイン計算部１５は、第一スカラ倍演算部１５１、第二スカラ倍演算部１５２及び加算部１５３を例えば含む。実施例１の楕円曲線暗号演算方法は、図２に示すステップＳ１からステップＳ３の処理を例えば行う。
【００１１】
楕円曲線暗号演算装置は、単純電力解析攻撃に対する防御機能を備えていない、ＩＣカード、携帯端末機器等の楕円曲線暗号の演算を行う装置である。
楕円曲線暗号演算装置の記憶部１１には、楕円曲線パラメータＥ、ベースポイントである点Ｐのｘ，ｙ座標ｘＰ，ｙＰ、点Ｐの位数ｎ、１＜ｒ＜ｎの予め定められた整数ｒ、点Ｐの楕円スカラｒ倍点Ｓ＝ｒ×Ｐのｘ，ｙ座標ｘＳ，ｙＳが事前パラメータとして格納される。これらの事前パラメータは、正当権限を有しない外部インターフェースから読み出すことができないように記憶部１１に記憶される。
【００１２】
なお、事前パラメータの内、整数ｒ、及び、点Ｐの楕円スカラｒ倍点Ｓ＝ｒ×Ｐのｘ，ｙ座標ｘＳ，ｙＳは、秘密情報として正当権限を有する機器のみで秘密にされる。一方、事前パラメータの内、楕円曲線パラメータＥ、ベースポイントである点Ｐのｘ，ｙ座標ｘＰ，ｙＰ、点Ｐの位数ｎは、公開情報として公開されるものであるため、正当権限を有しない外部インターフェースが読み出すことができるように楕円曲線暗号演算装置に記憶されていてもよい。
【００１３】
＜ステップＳ１＞
暗号演算処理の過程で、楕円スカラｋ倍算を行う必要が生じたとき、乱数生成部１２が、１＜α＜ｎの整数の乱数αを生成する。生成された乱数αは、除数生成部１３と、メイン計算部１５とに送られる。
【００１４】
＜ステップＳ２＞
除数生成部１３は、乱数αと、記憶部から読み込んだ整数ｒとを用いて、
ｒ’＝αｒ  ｍｏｄ  ｎ
により定義される除数ｒ’を生成する。生成された除数ｒ’は、メイン計算部１５に送られる。
【００１５】
＜ステップＳ３＞
メイン計算部１５は、下記の式（１）を計算することにより、点Ｐの楕円スカラｋ倍点ｋ×Ｐを求める。具体的には、第一スカラ倍演算部１５１，第二スカラ倍演算部１５２及び加算部１５３が、ステップＳ３１からステップＳ３３の処理を行うことにより、点ｋ×Ｐの計算を行う。下記の式（１）を計算することにより求まる点が、点ｋ×Ｐと等しくなる理由、すなわちｋ×Ｐ＝（ｋ  ｍｏｄ  ｒ’）×Ｐ＋［ｋ／ｒ’］α×Ｓとなる理由については後述する。
（ｋ  ｍｏｄ  ｒ’）×Ｐ＋［ｋ／ｒ’］α×Ｓ  …（１）
【００１６】
＜ステップＳ３１＞
第一スカラ倍演算部１５１は、点Ｐを楕円スカラ（ｋ  ｍｏｄ  ｒ’）倍した点
（ｋ  ｍｏｄ  ｒ’）×Ｐ
を求める。点（ｋ  ｍｏｄ  ｒ’）×Ｐは、加算部１５３に送られる。
【００１７】
＜ステップＳ３２＞
第二スカラ倍演算部１５２は、［・］を・の整数部分を出力する床関数として、記憶部１１から読み込んだ点Ｓを楕円スカラ［ｋ／ｒ’］α倍した点
［ｋ／ｒ’］α×Ｓ
を求める。点［ｋ／ｒ’］α×Ｓは、加算部１５３に送られる。
【００１８】
＜ステップＳ３３＞
加算部１５３は、点（ｋ  ｍｏｄ  ｒ’）×Ｐと、点［ｋ／ｒ’］α×Ｓとを加算する。
以上が、実施例１の楕円曲線暗号演算装置、方法の処理である。
【００１９】
楕円曲線暗号演算装置が単純電力解析攻撃に対する防御機能を備えていない場合には、攻撃者は、点Ｐの楕円スカラ（ｋ  ｍｏｄ  ｒ’）倍算と、点Ｓの楕円スカラ［ｋ／ｒ’］α倍算とをそれぞれ単純電力解析攻撃をすることにより、（ｋ  ｍｏｄ  ｒ’）の値と、［ｋ／ｒ’］αの値とを取得することができる。しかし、（ｋ  ｍｏｄ  ｒ’）の値と、［ｋ／ｒ’］αの値とを加算しても、スカラ倍指数ｋにはならない。記憶部１１に格納された予め定められた整数ｒの値を取得できない限り、これらの値から元のスカラ倍指数ｋを復元することはできない。このように、この実施例１の楕円曲線暗号演算装置、方法により、単純電力解析攻撃からスカラ倍指数ｋを防御することができる。
【００２０】
ｋ×Ｐ＝（ｋ  ｍｏｄ  ｒ’）×Ｐ＋［ｋ／ｒ’］α×Ｓとなる理由について説明する。ｎは点Ｐの位数であるから、位数の定義よりｎ×Ｐ＝Ｏ（無限遠点）である。このため、
α×Ｓ＝αｒ×Ｐ＝（αｒ  ｍｏｄ  ｎ）×Ｐ＝ｒ’×Ｐ
となる。したがって、
（ｋ  ｍｏｄ  ｒ’）×Ｐ＋［ｋ／ｒ’］α×Ｓ
＝（ｋ  ｍｏｄ  ｒ’）×Ｐ＋［ｋ／ｒ’］ｒ’×Ｐ
＝ｋ×Ｐ
となるのである。
【実施例２】
【００２１】
図３に例示するように、実施例２の楕円曲線暗号演算装置は、実施例１のメイン計算部１５を除く各部に加えて、スカラ倍指数ｋを拡張スカラ倍指数ｋ’に変換する拡張スカラ倍指数生成部１４と、乱数生成部１４１とを更に有する。また、メイン計算部１５に代えて、第一スカラ倍演算部１５１’、第二スカラ倍演算部１５２’及び加算部１５３’を例えば有するメイン計算部１５’を有する。実施例２の楕円曲線暗号演算方法は、図４に例示するように、実施例１のステップ１，ステップＳ２に加えて、ステップＳ４，ステップＳ５の処理を行う。また、ステップＳ３の処理に代えて、ステップＳ３’の処理を行う。実施例２はこれらの部分で実施例１とは異なる。他の部分は実施例１と同様である。
【００２２】
＜ステップＳ４（図４）＞
乱数生成部１４１（図３）は、１＜βの整数である乱数βを生成して、拡張スカラ倍指数生成部１４に送る。
【００２３】
＜ステップＳ５＞
拡張スカラ倍指数生成部１４は、乱数βを用いて、入力されたスカラ倍指数ｋを拡張した拡張スカラ倍指数ｋ’＝ｋ＋βｎを求める。
【００２４】
＜ステップＳ３’＞
メイン計算部１５’は、下記の式を計算することにより、点Ｐの楕円スカラｋ倍点ｋ×Ｐを求める。具体的には、第一スカラ倍演算部１５１’，第二スカラ倍演算部１５２’及び加算部１５３’が、ステップＳ３１’からステップＳ３３’の処理を行うことにより、点ｋ×Ｐの計算を行う。下記の式（２）を計算することにより求まる点が、点ｋ×Ｐと等しくなる理由、すなわちｋ×Ｐ＝（ｋ’  ｍｏｄ  ｒ’）×Ｐ＋［ｋ’／ｒ’］α×Ｓとなる理由については後述する。
（ｋ’  ｍｏｄ  ｒ’）×Ｐ＋［ｋ’／ｒ’］α×Ｓ  …（２）
【００２５】
＜ステップＳ３１’＞
第一スカラ倍演算部１５１’は、点Ｐを楕円スカラ（ｋ’  ｍｏｄ  ｒ’）倍した点
（ｋ’  ｍｏｄ  ｒ’）×Ｐ
を求める。点（ｋ’  ｍｏｄ  ｒ’）×Ｐは、加算部１５３’に送られる。
【００２６】
＜ステップＳ３２’＞
第二スカラ倍演算部１５２’は、［・］を・の整数部分を出力する床関数として、記憶部１１から読み込んだ点Ｓを楕円スカラ［ｋ’／ｒ’］α倍した点
［ｋ’／ｒ’］α×Ｓ
を求める。点［ｋ’／ｒ’］α×Ｓは、加算部１５３’に送られる。
【００２７】
＜ステップＳ３３’＞
加算部１５３’は、点（ｋ’  ｍｏｄ  ｒ’）×Ｐと、点［ｋ’／ｒ’］α×Ｓとを加算する。
以上が、実施例２の楕円曲線暗号演算装置、方法の処理である。
【００２８】
楕円曲線暗号演算装置が単純電力解析攻撃に対する防御機能を備えていない場合には、攻撃者は、点Ｐの楕円スカラ（ｋ’  ｍｏｄ  ｒ’）倍算と、点Ｓの楕円スカラ［ｋ’／ｒ’］α倍算とをそれぞれ単純電力解析攻撃をすることにより、（ｋ’  ｍｏｄ  ｒ’）の値と、［ｋ’／ｒ’］αとを取得することができる。しかし、（ｋ’  ｍｏｄ  ｒ’）の値と、［ｋ’／ｒ’］αの値とを加算しても、スカラ倍指数ｋにはならない。記憶部１１に格納された予め定められた整数ｒの値を取得できない限り、これらの値から元のスカラ倍指数ｋを復元することはできない。このように、この実施例２の楕円曲線暗号演算装置、方法により、単純電力解析攻撃からスカラ倍指数ｋを防御することができる。
【００２９】
ｋ’×Ｐ＝（ｋ’  ｍｏｄ  ｒ’）×Ｐ＋［ｋ’／ｒ’］α×Ｓとなる理由について説明する。ｎは点Ｐの位数であるから、位数の定義よりｎ×Ｐ＝Ｏ（無限遠点）である。このため、
α×Ｓ＝αｒ×Ｐ＝（αｒ  ｍｏｄ  ｎ）×Ｐ＝ｒ’×Ｐ
となり、また、
ｋ’＝ｋ＋βｎ＝ｋ
となる。したがって、
（ｋ’  ｍｏｄ  ｒ’）×Ｐ＋［ｋ’／ｒ’］α×Ｓ
＝（ｋ’  ｍｏｄ  ｒ’）×Ｐ＋［ｋ’／ｒ’］ｒ’×Ｐ
＝ｋ’×Ｐ
＝ｋ×Ｐ
となるのである。
【００３０】
実施例１においては、スカラ倍指数ｋの値が小さく、除数ｒ’の値が大きい場合、［ｋ／ｒ’］＝０となる可能性がある。［ｋ／ｒ’］＝０の場合、ｋ＝ｋ  ｍｏｄ  ｒ’であるため、攻撃者は、点Ｐの楕円スカラ（ｋ  ｍｏｄ  ｒ’）倍算を単純電力解析攻撃をすることにより、スカラ倍指数ｋを知ることができる。しかし、実施例２においては、拡張スカラ倍指数ｋ’＞ｎであり、除数ｒ’＜ｎであり、［ｋ’／ｒ’］＝０となることはないため、実施例１に比べて安全性が更に高い。
【実施例３】
【００３１】
実施例３は、除数ｒ’の値を所定の大きさ以上にすることにより、ｋ／ｒ’又はｋ／ｒ’の計算コストを削減することを特徴とする。
【００３２】
具体的には、実施例３の楕円曲線暗号演算装置は、実施例１又は２の各部に加えて、除数ｒ’が所定の値よりも大きいかどうかを判断する判断部１６、除数ｒ’が所定の値よりも小さい場合に除数ｒ’とαを大きくする変換部１７を更に有する。また、実施例３の楕円曲線暗号演算方法は、実施例１又は２の各ステップに加えて、図２又は図４において破線で示した、ステップＳ６，ステップＳ７の処理を例えば行う。
【００３３】
なお、実施例３においては、αは、１＜α＜ｎではなく、１＜α＜ｎ−１からランダムに選択される整数の乱数であるとする。後述する処理においてα←α＋１と変換された場合に、変換されたαが１＜α＜ｎとなるようにするためである。
【００３４】
以下では、図５を参照して、実施例２に、判断部１６、変換部１７を設けた場合を例に挙げて説明をする。実施例２と異なる部分についてのみ説明をして、同様な部分については重複説明を略する。
Ｌを２以上の整数として、整数ｒは、ｎ／２Ｌ＜ｒ＜ｎ−ｎ／２Ｌの範囲からランダムに選択されて、記憶部１１に記憶されている。
除数生成部１３が生成した除数ｒ’は、判断部１６に送られる。
【００３５】
＜ステップＳ６＞
判断部１６は、除数ｒ’が、ｒ’≧ｎ／２Ｌを満たすかどうかを判断する。判断結果は、変換部１７に送られる。
【００３６】
＜ステップＳ７＞
変換部１７は、ステップＳ６においてｒ’≧ｎ／２Ｌを満たさないと判断された場合には、ｒ’←ｒ’＋ｒ、α←α＋１と変換する。すなわち、ｒ’の値をｒ’の値にｒを加算した値に変換すると共に、αの値をαの値に１を加算した値に変換する。変換された、除数ｒ’及び乱数αは、メイン計算部１５に送られる。
【００３７】
その後、メイン計算部１５’は、変換された、除数ｒ’及び乱数αに基づいて、実施例２と同じ計算を行う（ステップＳ３’）。
変換部１７は、ステップＳ６においてｒ’≧ｎ／２Ｌを満たす判断された場合には、除数ｒ’及び乱数αを変更しない。
以上が、実施例３の楕円曲線暗号演算装置、方法の処理である。
【００３８】
以下、上記の処理により、ｋ’／ｒ’の値が所定の値（この例では、２Ｌ＋１）よりも小さくなることを、（１）ｎ／２Ｌ≦ｒ’＜ｎの場合と、（２）０＜ｒ’＜ｎ／２Ｌの場合とに分けて説明する。
【００３９】
（１）ｎ／２Ｌ≦ｒ’＜ｎの場合
ｋ’＝ｋ＋ｎ＜２ｎであるから、ｋ’／ｒ’＜２ｎ／（ｎ／２Ｌ）＝２Ｌ＋１
（２）０＜ｒ’＜ｎ／２Ｌの場合
この場合、変換部１７により、ｒ’←ｒ’＋ｒ、α←α＋１と変換される。今、ｒ’’＝ｒ’＋ｒと置くと、０＜ｒ’、ｎ／２Ｌ＜ｒより、ｎ／２Ｌ＜ｒ’’、また、ｒ’＜ｎ／２Ｌ、ｒ＜ｎ−ｎ／２Ｌより、ｒ’’＜ｒ／２Ｌ＋（ｎ−ｎ／２Ｌ）＝ｎとなる。したがって、ｎ／２Ｌ＜ｒ’’＜ｎとなる。
ｋ’＝ｋ＋ｎ＜２ｎであるから、ｋ’／ｒ’’＜２ｎ／（ｎ／２Ｌ）＝２Ｌ＋１となる。
このように、何れの場合も、ｋ’／ｒ’＜２Ｌ＋１となり、パラメータＬ（≧２）により、ｋ’／ｒ’の上限値を制限することができる。すなわち、ｋ’／ｒ’の計算コストを小さくすることができる。
【００４０】
実施例２に、判断部１６、変換部１７を設けた場合を例に挙げて説明したが、実施例１についても、同様の処理を行う判断部１６、変換部１７を設けてもよい。
実施例３の楕円曲線暗号演算装置、方法も、実施例１及び２と同じ理由により、単純電力解析攻撃からスカラ倍指数ｋを防御することができる。また、実施例１及び２と同じ理由により、メイン計算部１５の計算結果が、ｋ×Ｐと等しくなる。
【実施例４】
【００４１】
実施例４は、実施例１から３の何れかの楕円曲線暗号演算装置と、整数ｒ及び点Ｓ＝ｒ×Ｐを更新する発行装置３０とを有する楕円曲線暗号演算システム及びその方法であり、整数ｒ及び点Ｓを更新することを特徴とする。
以下では、図６、図７及び図８を参照して、楕円曲線暗号演算装置が実施例２の楕円曲線暗号演算装置である場合を例に挙げて説明する。実施例２と異なる部分についてのみ説明をして、同様な部分については重複説明を略する。
【００４２】
実施例４の楕円曲線暗号演算装置は、実施例２の楕円曲線暗号演算装置の各部に加えて、図６に例示するように、受信部１８及び更新部１９を例えば有する。また、実施例４の楕円曲線暗号演算方法は、実施例２の楕円曲線暗号演算方法の各ステップ（図４参照）に加えて、ステップＳ８からステップＳ１２の処理（図８参照）を例えば行う。発行装置３０（図７参照）は、整数生成部３２、第三スカラ倍演算部３３及び送信部３４を例えば備える。
【００４３】
＜ステップＳ８（図８参照）＞
正当権限を有する外部機器である発行装置３０の整数生成部３２（図７参照）は、１＜ｒ＜ｎの整数ｒを更新された整数ｒとして選択する。更新された整数ｒは、第三スカラ倍演算部３３と、送信部３４とに送られる。なお、楕円曲線暗号演算装置が実施例３の楕円曲線暗号演算装置である場合には、ｎ／２Ｌ＜ｒ＜ｎ−ｎ／２Ｌの整数ｒが更新された整数ｒとして選択される。
【００４４】
＜ステップＳ９＞
第三スカラ倍演算部３３は、更新された整数ｒを用いて、点Ｐの楕円スカラｒ倍点Ｓ＝ｒ×Ｐを更新された点Ｓとして求める。更新された点Ｓは、送信部３４に送られる。
【００４５】
＜ステップＳ１０＞
送信部３４は、更新された整数ｒ及び更新された点Ｓを、公衆網等を介しないセキュアな通信手段を用いて、この発明による楕円曲線暗号演算装置に送る。
【００４６】
＜ステップＳ１１＞
楕円曲線暗号演算装置の受信部１８（図６参照）は、正当権限を有する発行装置３０から受信した、更新された整数ｒ及び更新された点Ｓを更新部１９に送る。
【００４７】
＜ステップＳ１２＞
更新部１９は、更新された整数ｒ及び更新された点Ｓで、記憶部１１に記憶された整数ｒ及び点Ｓを更新する。
その後、更新された整数ｒ及び更新された点Ｓとに基づいて、実施例２と同様の計算が行われる。
【００４８】
ここで、図７に破線で例示するように、安全性を保障するために、ユーザ認証を行うユーザ認証部３１を発行装置３０に設けて、メンテナンス許可者のみが、ユーザ認証を経て整数ｒ及び点Ｓの更新処理シーケンスを行うことが可能であることが望ましい。また、整数ｒ、点Ｓの更新が完了した後は、生成した、整数ｒ、点Ｓの値を直ちに消去する機能を有していることが望ましい。さらに、整数ｒ、点Ｓの更新以外の目的で使用されることができない仕様になっていることが望ましい。
以上が、実施例４の楕円曲線暗号演算装置及び方法、並びに、楕円曲線暗号演算システム及び方法の処理である。
【００４９】
このようにして、整数ｒ及び点Ｓを更新することにより、安全性を増すことができる。何らかのデータ管理上の不手際等が原因で整数ｒの値が外部に放出され第三者に知れ渡ってしまったような場合、同一の整数ｒの値を暗号処理に継続して使用することは安全性の点で問題がある。例えばこのような場合に備えて、整数ｒや点Ｓを一定の頻度で更新することが望ましい。
【実施例５】
【００５０】
実施例５は、実施例１から３の何れかの楕円曲線暗号演算装置と、整数ｒ及び点Ｓ＝ｒ×Ｐを更新するための更新コマンドを生成する発行装置３０’を有する楕円曲線暗号演算システム及びその方法である。実施例５は、発行装置ではなく、更新コマンドを受けた楕円曲線暗号演算装置が整数ｒ及び点Ｓを生成する点で、実施例４とは異なる。
【００５１】
以下では、図９、図１０及び図１１を参照して、楕円曲線暗号演算装置が実施例２の楕円曲線暗号演算装置である場合を例に挙げて説明する。実施例２と異なる部分についてのみ説明をして、同様な部分については重複説明を略する。
【００５２】
実施例５の楕円曲線暗号演算装置は、実施例２の楕円曲線暗号演算装置の各部（図３参照）に加えて、図９に例示する受信部１８、更新部１９、整数生成部２０及び第四スカラ倍演算部２１を例えば有する。また、実施例４の楕円曲線暗号演算方法は、図１１に例示するように、実施例２の楕円曲線暗号演算方法の各ステップ（図４参照）に加えて、ステップＳ１３からステップＳ１６の処理を例えば行う。発行装置３０’は、図１０に例示するように、整数生成部３２、第三スカラ倍演算部３３及び送信部３４を例えば備える。
【００５３】
＜ステップＳ１３（図１１参照）＞
正当権限を有する外部機器である発行装置３０’の更新コマンド生成部３５（図１０参照）は、楕円曲線暗号演算装置に整数ｒ及び点Ｓの更新を指示する更新コマンドを生成して、楕円曲線暗号演算装置に送る。
【００５４】
＜ステップＳ１４＞
楕円曲線暗号演算装置の整数生成部２０は、受信部１８を介して更新コマンドを受け取ると、整数ｒを生成する。生成された整数ｒは、更新部１９及び第四スカラ倍演算部２１に送られる。なお、楕円曲線暗号演算装置が実施例３の楕円曲線暗号演算装置である場合には、ｎ／２Ｌ＜ｒ＜ｎ−ｎ／２Ｌの整数ｒが更新された整数ｒとして選択される。
【００５５】
＜ステップＳ１５＞
第四スカラ倍演算部２１は、更新された整数ｒを用いて、点Ｐの楕円スカラｒ倍点Ｓ＝ｒ×Ｐを更新された点Ｓとして求める。更新された点Ｓは、更新部１９に送られる。
【００５６】
＜ステップＳ１６＞
更新部１９は、更新された整数ｒ及び更新された点Ｓで、記憶部１１に記憶された整数ｒ及び点Ｓを更新する。
その後、更新された整数ｒ及び更新された点Ｓに基づいて、実施例２と同様の計算が行われる。
【００５７】
実施例５においては、更新の際に第四スカラ倍演算部２１において点Ｐの楕円スカラｒ倍算ｒ×Ｐが行われる。したがって、更新の際に単純電力解析攻撃を受けると、整数ｒの値が取得されてしまうので、整数ｒ及び点Ｓの更新は限定的な条件でのみ許可され得る仕様になっていることが望ましい。したがって、図１０に破線で例示するように、ユーザ認証を行うユーザ認証部３１を発行装置３０’に設けて、メンテナンス許可者のみが、ユーザ認証を経て整数ｒ及び点Ｓの更新処理シーケンスを行うことが可能であることが望ましい。このようにして、整数ｒ及び点Ｓを更新することにより、実施例４と同様に安全性を増すことができる。
【００５８】
［変形例等］
乱数生成部１２を設けないで、予め生成された乱数αに基づいて上記の計算が行われるようにしてもよい。同様に、乱数生成部１４１を設けないで、予め生成された乱数βに基づいて上記の計算が行われるようにしてもよい。
なお、単純電力解析攻撃に対する防御機能を備えている楕円曲線暗号演算装置が、更なる安全性を確保するために、この発明による楕円曲線暗号の演算を行ってもよい。すなわち、この発明の楕円曲線暗号演算装置は、単純電力解析攻撃に対する防御機能を備えていてもよい。
【００５９】
上述の構成をコンピュータによって実現する場合、楕円曲線暗号演算装置の各部が有する機能の処理内容はプログラムによって記述される。そして、このプログラムを図１２に例示するコンピュータで実行することにより、上記各部の機能がコンピュータ上で実現される。
【００６０】
すなわち、ＣＰＵ１がプログラムを逐次読み込んで実行することにより、乱数生成部１２、除数生成部１３、拡張スカラ倍指数生成部１４、乱数生成部１４１、メイン計算部１５、第一スカラ倍演算部１５１、第二スカラ倍演算部１５２、加算部１５３、メイン計算部１５’、第一スカラ倍演算部１５１’、第二スカラ倍演算部１５２’、加算部１５３’、判断部１６、変換部１７、受信部１８、更新部１９、整数生成部２０及び第四スカラ倍演算部２１の機能がそれぞれ実現される。また、補助記憶装置３又はメモリ２が、記憶部１１として機能する。
【００６１】
楕円曲線暗号演算装置の各部として機能するＣＰＵ１は、例えばメモリ２又は補助記憶装置３から読み込み込んだデータに対して処理を行い、処理を行った後のデータをメモリ２又は補助記憶装置３に格納する。すなわち、メモリ２又は補助記憶装置３を介して、楕円曲線暗号演算装置の各部間でデータがやり取りされる。
【００６２】
この処理内容を記述したプログラムは、コンピュータで読み取り可能な記録媒体に記録しておくことができる。コンピュータで読み取り可能な記録媒体としては、例えば、磁気記録装置、光ディスク、光磁気記録媒体、半導体メモリ等どのようなものでもよいが、具体的には、例えば、磁気記録装置として、ハードディスク装置、フレキシブルディスク、磁気テープ等を、光ディスクとして、ＤＶＤ（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）型のサービスによって、上述の処理を実行する構成としてもよい。なお、本形態におけるプログラムには、電子計算機による処理の用に供する情報であってプログラムに準ずるもの（コンピュータに対する直接の指令ではないがコンピュータの処理を基底する性質を有するデータ等）を含むものとする。
【００６５】
また、この形態では、コンピュータ上で所定のプログラムを実行させることにより、本装置を構成することとしたが、これらの処理内容の少なくとも一部をハードウェア的に実現することとしてもよい。
また、上述の各種の処理は、記載に従って時系列に実行されるのみならず、処理を実行する装置の処理能力あるいは必要に応じて並列的にあるいは個別に実行されてもよい。例えば、図２において、ステップＳ３１の処理及びステップＳ３２の処理を並列に行ってもよい。
その他、本発明の趣旨を逸脱しない範囲で適宜変更が可能であることはいうまでもない。
【図面の簡単な説明】
【００６６】
【図１】実施例１の楕円曲線暗号演算装置の機能ブロック図。
【図２】実施例１の楕円曲線暗号演算方法のフローチャート。
【図３】実施例２の楕円曲線暗号演算装置の機能ブロック図。
【図４】実施例２の楕円曲線暗号演算方法のフローチャート。
【図５】実施例３の楕円曲線暗号演算装置の機能ブロック図。
【図６】実施例４の楕円曲線暗号演算装置の機能ブロック図。
【図７】実施例４の発行装置の機能ブロック図。
【図８】実施例４の楕円曲線暗号演算システムの方法のフローチャート。
【図９】実施例５の楕円曲線暗号演算装置の機能ブロック図。
【図１０】実施例５の発行装置の機能ブロック図。
【図１１】実施例５の楕円曲線暗号演算システムの方法のフローチャート。
【図１２】この発明の楕円曲線暗号演算装置をコンピュータで実現させる場合の機能ブロック図の例。
【符号の説明】
【００６７】
１１   記憶部
１２   乱数生成部
１３   除数生成部
１４   拡張スカラ倍指数生成部
１５，１５’  メイン計算部
１５１，１５１’     第一スカラ倍演算部
１５２，１５２’     第二スカラ倍演算部
１６   判断部
１７   変換部
１８   受信部
１９   更新部
２０   整数生成部
２１   第四スカラ倍演算部
３０   発行装置
３１   ユーザ認証部
３２   整数生成部
３３   第三スカラ倍演算部
３４   送信部
３５   更新コマンド生成部
１４１ 乱数生成部
【図１】
0005010508.tif 000002
【図２】
0005010508.tif 000003
【図３】
0005010508.tif 000004
【図４】
0005010508.tif 000005
【図５】
0005010508.tif 000006
【図６】
0005010508.tif 000007
【図７】
0005010508.tif 000008
【図８】
0005010508.tif 000009
【図９】
0005010508.tif 000010
【図１０】
0005010508.tif 000011
【図１１】
0005010508.tif 000012
【図１２】
0005010508.tif 000013