(57)【要約】個人鍵を用いて楕円曲線暗号処理を行う暗号装置（１０）は、乱数に基づいて生成された楕円曲線上の点Ｒを初期点Ｖ０にセットするランダム化手段（１６）と、その楕円曲線暗号のための或るスカラー値ｄのビット・シーケンスに従って、その初期点Ｖ０と楕円曲線上の或る入力点Ａのスカラー倍との和Ｖ１＝Ｖ０＋ｄＡの演算を実行する演算手段（２０）と、その演算によって得られた和Ｖ１からその初期点Ｖ０を減算する演算Ｖ＝Ｖ１−Ｖ０を実行するランダム化解除手段（２２）と、そのランダム化解除手段によって得られた点Ｖを出力として供給する手段（２４）と、を具えている。
2005008955.tif 000002
【特許請求の範囲】
【請求項１】
個人鍵を用いて楕円曲線暗号処理を行う暗号装置であって、
乱数に基づいて生成された楕円曲線上の点Ｒを初期点Ｖ０にセットするランダム化手段と、
前記楕円曲線暗号のための或るスカラー値ｄのビット・シーケンスに従って、前記初期点Ｖ０と楕円曲線上の或る入力点Ａのスカラー倍との和Ｖ１＝Ｖ０＋ｄＡの演算を実行する演算手段と、
前記演算によって得られた和Ｖ１から前記初期点Ｖ０を減算する演算Ｖ＝Ｖ１−Ｖ０を実行するランダム化解除手段と、
前記ランダム化解除手段によって得られた点Ｖを出力として供給する手段と、
を具える、暗号装置。
【請求項２】
前記演算手段は次の演算を繰り返し実行し、
−  点の加算Ｖ［１］：＝Ｖ［０］＋Ｖ［２］、
−  点の２倍算Ｖ［２］：＝２Ｖ［２］、および
−  代入Ｖ［０］：＝Ｖ［ｄ［ｉ］］
ここで、Ｖ［２］は別の変数を表し、前記入力点Ａが変数Ｖ［２］の初期値としてセットされ、前記スカラー値ｄはｍビット・シーケンスであり、ｄ［ｉ］は、ｉ＝０，１，．．．ｍ−１について前記スカラー値ｄのｉ番目のＬＳＢの値を表すものである、請求項１に記載の暗号装置。
【請求項３】
前記ランダム化手段は、前記楕円曲線上の点Ｒの座標Ｘを生成し、前記座標Ｘに従って前記点Ｒの座標Ｙを生成して、前記生成された座標（Ｘ，Ｙ）を前記点Ｒとして前記初期点Ｖ０にセットするものである、請求項１に記載の暗号装置。
【請求項４】
前記ランダム化手段は、乱数ｓを生成し、ベースポイントＧのｓ倍を求め、前記求められたｓＧを前記点Ｒとして前記初期点Ｖ０にセットするものである、請求項１に記載の暗号装置。
【請求項５】
前記ランダム化手段は、前記ｓＧを求めるために、無限遠点Ｏをワーク変数Ｖ［０］に初期値としてセットし、前記Ｇをワーク変数Ｖ［２］に初期値としてセットし、
次の演算を繰り返し実行し、
−  点の加算Ｖ［１］：＝Ｖ［０］＋Ｖ［２］、
−  点の２倍算Ｖ［２］：＝２Ｖ［２］、および
−  代入Ｖ［０］：＝Ｖ［ｄ［ｉ］］
ここで、前記スカラー値ｄはｍビット・シーケンスであり、ｄ［ｉ］は、ｉ＝０，１，．．．ｍ−１について前記スカラー値ｄのｉ番目のＬＳＢの値を表すものである、請求項４に記載の暗号装置。
【請求項６】
前記ランダム化手段は、前記ｓＧを求めるために、乱数ｓを前記スカラー値ｄにセットし、前記入力点Ａを前記ベースポイントＧにセットし、無限遠点Ｏを前記点Ｒにセットすることによって、前記演算Ｖ１＝Ｖ０＋ｄＡを用いてｓＧ＝Ｏ＋ｓＧを求めるものである、請求項４に記載の暗号装置。
【請求項７】
最初にランダムに発生された前記楕円曲線上の点Ｒ０が前記点Ｒにセットされ、その後前記点Ｒとして関数Ｒｎ＝ｆ（Ｒｎ−１，ｃ）で表される前記楕円曲線上の点Ｒｎが用いられ、ここでＲｎはｎ回目の楕円曲線暗号処理を表すものであり、ｃは定数を表すものである、請求項１に記載の暗号装置。
【請求項８】
前記楕円曲線上の前回の点Ｒｎ−１が投影座標の点（ＲＸ，ＲＹ，ＲＺ）で表されるとき、前記楕円曲線上の今回の点Ｒｎが投影座標の点（ｃ×ＲＸ，ｃ×ＲＹ，ｃ×ＲＺ）で表されるものである、請求項７に記載の暗号装置。
【請求項９】
前記楕円曲線上の前回の点Ｒｎ−１がヤコビアン座標の点（ＲＸ，ＲＹ，ＲＺ）で表されるとき、前記楕円曲線上の今回の点Ｒｎがヤコビアン座標の点（ｃ２×ＲＸ，ｃ３×ＲＹ，ｃ×ＲＺ）で表されるものである、請求項７に記載の暗号装置。
【請求項１０】
前記楕円曲線暗号処理は素体の楕円曲線パラメータに対するヤコビヤン座標を用いた演算であり、Ｐ＝Ｖ［２］＝（Ｘｉ，Ｙｉ，Ｚｉ）＝２ｉＡであり、
ｉ＝０について、演算Ｒｉ：＝Ｚ０２、Ｒｉ：＝Ｒｉ２、およびＲｉ：＝ａＲｉを順に実行することによってＲｉを求め、
ｉ＞１について、演算Ｒｉ：＝ＲｉＴｉ−１を実行することによってＲｉを求め、ここでＴｉ−１はｉ−１についての中間データを表し、
前記求められたＲｉに従って、演算Ｍｉ：＝３Ｘｉ＋Ｒｉ、Ｑｉ：＝Ｙｉ２、Ｓｉ：＝４ＸｉＱｉ、Ｔｉ：＝８Ｑｉ２、Ｚｉ＋１：＝２ＹｉＺｉ、Ｘｉ＋１：＝Ｍｉ２−２Ｓｉ、およびＹｉ＋１：＝Ｍｉ（Ｓｉ−Ｘｉ）−Ｔｉを、この順にまたは別の順に実行してＰ＝（Ｘｉ＋１，Ｙｉ＋１，Ｚｉ＋１）＝２ｉ＋１Ａを求め、Ｖ［２］として出力するものである、
請求項２に記載の暗号装置。
【請求項１１】
個人鍵を用いてべき乗剰余暗号処理を行う暗号装置であって、
乱数に基づいて生成された整数ｒを初期値Ｖ０にセットするランダム化手段と、
前記べき乗剰余暗号のための或る値ｄのビット・シーケンスに従って、前記初期値Ｖ０と或る入力値ａに対するべき乗剰余演算Ｖ１＝Ｖ０ａｄ（ｍｏｄ  ｎ）＝ｒ×ａｄ（ｍｏｄ  ｎ）の演算を実行する演算手段と、
前記演算によって得られた値Ｖ１とｒ（ｍｏｄ  ｎ）の逆元ｒ−１（ｍｏｄ  ｎ）との乗算剰余演算Ｖ＝Ｖ１×ｒ−１（ｍｏｄ  ｎ）を実行するランダム化解除手段と、
前記ランダム化解除手段によって得られた値Ｖを出力として供給する手段と、
を具える、暗号装置。
【請求項１２】
前記演算手段は、次の演算を繰り返し実行するものである、
−  乗算Ｖ［１］：＝Ｖ［０］×Ｖ［２］（ｍｏｄ  ｎ）、
−  ２乗算Ｖ［２］：＝Ｖ［２］２（ｍｏｄ  ｎ）、および
−  代入Ｖ［０］：＝Ｖ［ｄ［ｉ］］
ここで、Ｖ［２］は別の変数を表し、前記値ｄはｍビット・シーケンスであり、ｄ［ｉ］は、ｉ＝０，１，．．．ｍ−１について前記値ｄのｉ番目のＬＳＢの値を表すものである、
請求項１１に記載の暗号装置。
【請求項１３】
情報処理装置において使用するための、個人鍵を用いて楕円曲線暗号処理を行う記憶媒体に格納されたプログラムであって、
乱数に基づいて生成された楕円曲線上の点Ｒをランダムに発生するステップと、
前記点Ｒを初期点Ｖ０にセットするステップと、
前記楕円曲線暗号のための或るスカラー値ｄのビット・シーケンスに従って、前記初期点Ｖ０と楕円曲線上の或る入力点Ａのスカラー倍との和Ｖ１＝Ｖ０＋ｄＡの演算を実行するステップと、
前記演算によって得られた和Ｖ１から前記初期点Ｖ０を減算する演算Ｖ＝Ｖ１−Ｖ０を実行するステップと、
前記減算によって得られた点Ｖを出力として供給するステップと、
を実行させるよう動作可能なプログラム。
【請求項１４】
情報処理装置において使用するための、個人鍵を用いてべき乗剰余暗号処理を行う記憶媒体に格納されたプログラムであって、
乱数に基づいて生成された整数ｒを初期値Ｖ０にセットするステップと、
前記べき乗剰余暗号のための或る値ｄのビット・シーケンスに従って、前記初期値Ｖ０と或る入力値ａに対するべき乗剰余演算Ｖ１＝Ｖ０ａｄ（ｍｏｄ  ｎ）＝ｒ×ａｄ（ｍｏｄ  ｎ）の演算を実行するステップと、
前記演算によって得られた値Ｖ１とｒ（ｍｏｄ  ｎ）の逆元ｒ−１（ｍｏｄ  ｎ）との乗算剰余演算Ｖ＝Ｖ１×ｒ−１（ｍｏｄ  ｎ）を実行するステップと、
前記逆元との乗算剰余演算によって得られた値Ｖを出力として供給するステップと、
を実行させるよう動作可能なプログラム。
【請求項１５】
情報処理装置において使用するための、個人鍵を用いて楕円曲線暗号処理を行う方法であって、
乱数に基づいて生成された楕円曲線上の点Ｒをランダムに発生するステップと、
前記点Ｒを初期点Ｖ０にセットするステップと、
前記楕円曲線暗号のための或るスカラー値ｄのビット・シーケンスに従って、前記初期点Ｖ０と楕円曲線上の或る入力点Ａのスカラー倍との和Ｖ１＝Ｖ０＋ｄＡの演算を実行するステップと、
前記演算によって得られた和Ｖ１から前記初期点Ｖ０を減算する演算Ｖ＝Ｖ１−Ｖ０を実行するステップと、
前記減算によって得られた点Ｖを出力として供給するステップと、
を含む方法。
【請求項１６】
情報処理装置において使用するための、個人鍵を用いてべき乗剰余暗号処理を行う方法であって、
乱数に基づいて生成された整数ｒを初期値Ｖ０にセットするステップと、
前記べき乗剰余暗号のための或る値ｄのビット・シーケンスに従って、前記初期値Ｖ０と或る入力値ａに対するべき乗剰余演算Ｖ１＝Ｖ０ａｄ（ｍｏｄ  ｎ）＝ｒ×ａｄ（ｍｏｄ  ｎ）の演算を実行するステップと、
前記演算によって得られた値Ｖ１とｒ（ｍｏｄ  ｎ）の逆元ｒ−１（ｍｏｄ  ｎ）との乗算剰余演算Ｖ＝Ｖ１×ｒ−１（ｍｏｄ  ｎ）を実行するステップと、
前記逆元との乗算剰余演算によって得られた値Ｖを出力として供給するステップと、
を含む方法。
【発明の詳細な説明】
発明の分野
本発明は、暗号処理の分野に関し、特に、ＲＳＡおよび楕円曲線暗号のような公開鍵暗号のためのプロセッサにおけるＳＰＡ、ＤＰＡおよびＲＰＡのような電力解祈攻撃を防止する耐タンパ（ｔａｍｐｅｒ−ｐｒｏｏｆ）暗号化／復号に開する。
発明の背景
例えば電子決済および日本の住民基本台帳ネットワークのようなネットワークを利用したサービスが普及しつつある。これらのサービスには情報セキュリティのために暗号が用いられる。
上述のサービスにおけるユーザ側のデバイスとして、ユーザの秘密情報を格納したＩＣチップを含むスマートカードが広く普及すると予想される。スマートカードは、暗号、ディジタル署名および認証の機能を有し、その秘密情報を鍵として用いる。スマートカードでは、秘密情報はＩＣチップ・メモリに格納されるので、第三者による不正なアクセスに対する安全性または耐タンパ性が磁気カードに比べて非常に高い。
図１は、スマートカードのような暗号デバイスにおける秘密鍵を用いた暗号化／復号の構成の例を示している。図１において、暗号デバイスは、その内部の暗号化／復号ユニットにおいて周知の形態で個人鍵を用いて入力平文／暗号文メッセージを処理して出力暗号文／平文メッセージを供給する。暗号方式には一般的に公開鍵暗号方式と共通鍵暗号方式が含まれる。
公開鍵暗号方式は、暗号化と復号に異なる鍵（キー）を用いる。典型的には、公開鍵を用いて平文（ｐｌａｉｎｔｅｘｔ）が暗号化され、個人または秘密鍵を用いて暗号文（ｃｉｐｈｅｒｔｅｘｔ）が復号され、それによって暗号文が安全に送信できる。または、個人鍵を用いて平文が暗号化され、公開鍵を用いて暗号文が復号され、それによって平文を暗号化したユーザが識別される。公開鍵暗号は、送受信者間で秘密鍵を共有する必要がないが、計算量が共通鍵暗号と比べて非常に大きい。公開鍵暗号にはＲＳＡおよび楕円曲線暗号が含まれる。
ＲＳＡ暗号は、ｚ＝ａｘ（ｍｏｄ  ｎ）で表される冪（べき）乗剰余演算（ｍｏｄｕｌａｒ  ｅｘｐｏｎｅｎｔｉａｔｉｏｎ）に基づくものである。ＲＳＡ暗号に基づく暗号機能は、暗号化、復号、署名生成および署名確認に関係する。復号および署名生成ではユーザの秘密情報を個人鍵として用いる。べき乗剰余演算は、ｖ＝ａｄ（ｍｏｄ  ｎ）を満たすは出力データｖを生成する。ここで、ａは入力データを表し、ｎは剰余の法を表し、ｄは個人鍵を表す。
楕円曲線暗号は、点のスカラー倍算に基づくものである。点のスカラー倍算は、スカラー値ｄ、および楕円曲線上の点Ａに対して、Ｖ＝ｄＡを満たす点Ｖを求める。楕円曲線暗号に基づく暗号機能は、ＥＣＥＳ暗号化／復号、ＥＣＤＳＡ署名生成／署名確認およびＥＣＤＨ秘密鍵共有に関係する。ＥＣＥＳ復号、ＥＣＤＳＡ署名生成およびＥＣＤＨ秘密鍵共有のための処理は、ユーザの秘密情報を個人鍵として用いる。例えば、ＥＣＤＨ秘密鍵共有処理は、秘密共有値を表す点Ｖを計算するためにＶ＝ｄＡで表される点のスカラー倍算を行う。ここで、Ａは秘密鍵を共有する公開鍵の点を表し、ｄは個人鍵のスカラー値を表す。
ＲＳＡ暗号における乗算剰余ｃ＝ａ×ｂ（ｍｏｄ  ｎ）、２乗剰余ｃ＝ａ２およびべき乗剰余ｃ＝ａｘ（ｍｏｄ  ｎ）は、楕円曲線暗号における点の加算Ｃ＝Ａ＋Ｂ、点の２倍算Ｃ＝２Ａおよび点のスカラー倍算Ｃ＝ｘＡにそれぞれ対応する。
暗号解読（分析）またはタンパ（ｔａｍｐｅｒ）は、暗号文のような入手可能な情報から個人鍵を含めた秘密情報を推定する。暗号解読の１つである電力解析攻撃が、１９９８年にＰａｕｌ  Ｋｏｃｈｅｒ（ポール  コーチャ）によって考案された。
電力解析攻撃は、文献、Ｐ．Ｋｏｃｈｅｒ，Ｊ．Ｊａｆｆｅ  ａｎｄ  Ｂ．Ｊｕｎ”Ｄｉｆｆｅｒｅｎｔｉａｌ  Ｐｏｗｅｒ  Ａｎａｙｓｉｓ”，Ｃｒｙｐｔｏ’９９，ＬＮＣＳ  １６６６，ｐｐ．３８８−３９７，Ｓｐｒｉｎｇｅｒ−Ｖｅｒｌａｇ，１９９９に記載されている。
この電力解析攻撃は、スマートカードのような暗号デバイスに含まれる暗号プロセッサに相異なる入力データを与え、例えば図１に示されているようにオシロスコープ等を用いてその処理中における時間に対する消費電力の変化を測定し、統計的に充分な数の消費電力変化の曲線を収集しそれを解析し、それによって暗号プロセッサ内部の鍵情報を推定する。これは、共通鍵暗号と公開健暗号の双方に適用できる。
電力解析攻撃には、単純電力解析（Ｓｉｍｐｌｅ  Ｐｏｗｅｒ  Ａｎａｌｙｓｉｓ）（以下、ＳＰＡという）および電力差分攻撃（Ｄｉｆｆｅｒｅｎｔｉａｌ  Ｐｏｗｅｒ  Ａｎａｌｙｓｉｓ）（以下、ＤＰＡという）が含まれる。ＳＰＡは暗号プロセッサにおける１つの消費電力変化曲線の特徴から秘密鍵または個人鍵の推定を行う。ＤＰＡは相異なる多数の消費電力変化曲線の差分（以下、電力差分曲線という）を用いて解析することによって秘密鍵の推定を行う。一般的にはＤＰＡの方が強力である。
電力解析攻撃を防止する必要性が各種国際標準に記載されている。例えば、セキュリティの国際標準ＩＳＯ１５４０８によるスマートカード用プロテクション・プロファイル（ＰＰ）では電力解析攻撃への対策が必須である。また、暗号モジュールに関する米国標準ＦＩＰＳ１４０−２には、現在は電力解析攻撃対策の必要性に関するコメントがあるだけであるが、将来的に電力解析攻撃対策が必須になるであろう。
ＲＳＡと楕円曲線暗号に対する電力解析攻撃ＳＰＡおよびＤＰＡを防止するための様々な対策が開発された。しかし、２００３年に、改善された電力解析攻撃（Ｒｅｆｉｎｅｄ  Ｐｏｗｅｒ  Ａｎａｌｙｓｉｓ）（ＲＰＡ）が、Ｌ．Ｇｏｕｂｉｎ，”Ａ  Ｒｅｆｉｎｅｄ  Ｐｏｗｅｒ−Ａｎａｌｙｓｉｓ  Ａｔｔａｃｋ  ｏｎ  Ｅｌｌｉｐｔｉｃ  Ｃｕｒｖｅ  Ｃｒｙｐｔｏ−ｓｙｓｔｅｍｓ”，ＰＫＣ  ２００３，ＬＮＣＳ  ２５６７，Ｓｐｒｉｎｇｅｒ−Ｖｅｒｌａｇ，２００３によって発表された。この攻撃は、楕円曲線暗号に対する電力解析攻撃を防止する公開鍵暗号の中の一部の暗号を攻撃するのに有効である。
次に、楕円曲線暗号に用いられる用語を説明する。詳細は文献ＩＥＥＥ  Ｐ１３６３／Ｄ１３（Ｄｒａｆｔ  Ｖｅｒｓｉｏｎ  １３，Ｎｏｖｅｍｂｅｒ  １２，１９９９）ｍａｉｎ  ｄｏｃｕｍｅｎｔ，Ｓｔａｎｄａｒｄ  Ｓｐｅｃｉｆｉｃａｔｉｏｎｓ  ｆｏｒ  Ｐｕｂｌｉｃ  Ｋｅｙ  Ｃｒｙｐｔｏｇｒａｐｈｙ，ｈｔｔｐ：／／ｇｒｏｕｐｅｒ．ｉｅｅｅ．ｏｒｇ／ｇｒｏｕｐｓ／１３６３／Ｐ１３６３／ｄｒａｆｔ．ｈｔｍｌの標準を参照されたい。
次の式で表される変数ｘおよびｙの関数で表される曲線が楕円曲線と呼ばれる。
楕円曲線（素体）：  ｙ２＝ｘ３＋ａｘ＋ｂ  （ｍｏｄ  ｐ）
2005008955.tif 000003
を表す。
楕円曲線（２べき）：  ｙ２＋ｘｙ＝ｘ３＋ａｘ２＋ｂ  （ｍｏｄ  ｆ（ｘ））
ここで、ｆはＧＦ（２ｍ）の多項式を表し、ａおよびｂは楕円曲線パラメータ（ａ，ｂ，⊆ＧＦ（２ｍ））を表す。
楕円曲線は、主に素体（ｐｒｉｍｅ  ｆｉｅｌｄ）と２べき（ｂｉｎａｒｙ  ｆｉｅｌｄ）からなる。楕円曲線は楕円曲線パラメータａおよびｂによって一意的に決定される。
楕円曲線上の点（ｅｌｌｉｐｔｉｃ  ｐｏｉｎｔ）は、楕円曲線で表される式を満たす座標（ｘ
2005008955.tif 000004
、２べきの場合は（ｘ，ｙ）⊆ＧＦ（２ｍ）を満たす要素（ｘ，ｙ）の集合である。
無限遠点（ｉｎｆｉｎｉｔｅ  ｐｏｉｎｔ）は、Ｏと表記され、任意の点Ａに対しＡ＋Ｏ＝Ｏ＋Ａ＝Ａを満たす楕円曲線上の特殊な点である。ここで、＋は点の加算を表す。
ベースポイント（ｂａｓｅ  ｐｏｉｎｔ）は、楕円曲線上の１点であり、Ｇと表記される。ベースポイントは楕円曲線暗号のユーザ間で共有され、公開鍵／個人鍵のペアの生成、および楕円曲線暗号を用いたその他の処理に用いられる。
２次元ベクトル（ｘ，ｙ）を用いた点の表現は、アファイン座標（Ａｆｆｉｎｅ  ｃｏｏｒｄｉｎａｔｅｓ）と呼ばれる。（ｘ，ｙ）＝（Ｘ／Ｚ，Ｙ／Ｚ）を満たす３次元ベクトル（Ｘ，Ｙ，Ｚ）を用いた点の表現は、投影座標（ｐｒｏｊｅｃｔｉｖｅ  ｃｏｏｒｄｉｎａｔｅｓ）と呼ばれる。（ｘ，ｙ）＝（Ｘ／Ｚ２，Ｙ／Ｚ３）を満たす３次元ベクトル（Ｘ，Ｙ，Ｚ）を用いた点の表現は、ヤコビアン座標（Ｊａｃｏｂｉａｎ  ｃｏｏｒｄｉｎａｔｅｓ）と呼ばれる。３次元ベクトル表現の使用によって、点のスカラー倍算における除算の回数を大幅に減らし、全体の演算を高速化できる。
点ＡおよびＢに対する演算Ａ＋Ｂは、点の加算（ｅｌｌｉｐｔｉｃ  ｐｏｉｎｔ  ａｄｄｉｔｉｏｎ）と呼ばれる。Ａ＋Ｂ＝Ｂ＋Ａが成立する。点ＡおよびＢに対する演算Ａ−Ｂは、点の減算（ｅｌｌｉｐｔｉｃ  ｐｏｉｎｔ  ｓｕｂｔｒａｃｔｉｏｎ）と呼ばれる。
点の２倍算（ｅｌｌｉｐｔｉｃ  ｐｏｉｎｔ  ｄｏｕｂｌｉｎｇ）は、楕円曲線上の点ＡからＣ＝２Ａで表される楕円曲線上の点Ｃが定義される。この演算２Ａを点の２倍算と呼ぶ。
点のスカラー倍算（ｅｌｌｉｐｔｉｃ  ｓｃａｌａｒ  ｍｕｌｔｉｐｌｉｃａｔｉｏｎ）は、楕円曲線上の点Ａおよびスカラー値ｄから、Ｖ＝ｄＡによって定義される楕円曲線上のＶを導出する演算であり、点の加算、点の減算および２倍算の組み合わせからなる。
ベースポイントＧと、個人鍵を表すスカラー値ｄとに対し、公開鍵はＶ＝ｄＧを満たすＶにより与えられる。公開鍵は楕円曲線上の点である。個人鍵はスカラー値である。
次に、電力解析攻撃について説明する。
べき乗剰余または点のスカラー倍算を実現するためのアルゴリズムには、例えばバイナリ法、符号付きバイナリ法およびウィンドウ法等が含まれる。攻撃者はスマートカードにおけるべき乗剰余または点のスカラー倍算のアルゴリズムを知っているものと仮定する。
図２は通常のバイナリ法によるべき乗剰余のアルゴリズムを示している。与えられた基数ａ、指数ｄおよび法ｎに対して、べき乗剰余値ｖ＝ａｄ（ｍｏｄ  ｎ）が求められる。図３は、通常のバイナリ法による点のスカラー倍算のアルゴリズムを示している。与えられた点Ａおよびスカラー値ｄに対して、点のスカラー倍を表す点Ｖ＝ｄＡが求められる。ここで、ｄはｍビットの２進値を表す。２進値ｄ中のｉ番目のビット値はｄ［ｉ］で表される（ｉ＝０，１，．．．ｍ−１
2005008955.tif 000005
はｄ［ｉ，ｊ］で表される。例えば、ｄ＝１９＝（１００１１）２のとき、ｄ［４］＝１、ｄ［３］＝０、ｄ［２］＝０、ｄ［１］＝１、ｄ［０］＝１であり、ｄ［０，０］＝（１）２＝１、ｄ［１，０］＝（１１）２＝３、ｄ［２，０］＝（０１１）２＝３、ｄ［３，０］＝（００１１）２＝３、ｄ［４，０］＝（１００１１）２＝１９、ｄ［４，１］＝（１００１）２＝９である。ＥＣＡＤＤは点の加算を表し、ＥＣＤＢＬは点の２倍算を表す。
図２を参照すると、ステップ１０２においてワーク変数ｔおよびｖがそれぞれｔ＝ａおよびｖ＝１と初期化される。ステップ１０３〜１０６は、ｉに対するループ処理であり、ｉ＝０，１，．．．ｍ−１について順次、ｄ［ｉ］＝０に対してステップ１０５における２乗算が実行され、ｄ［ｉ］＝１に対してステップ１０４における乗算とステップ１０５における２乗算が実行される。ステップ１０６の後、ワーク変数ｖの値はｖ＝ａｄ［ｉ，０］（ｍｏｄ  ｎ）で表される。
図３を参照すると、ステップ２０２においてワーク変数ＴおよびＶがＴ＝ＡおよびＶ＝Ｏと初期化される。ステップ２０３〜２０６は、ｉに対するループ処理であり、ｉ＝０，１，．．．ｍ−１について順次、ｄ［ｉ］＝０に対してステップ２０５における２倍算が実行され、ｄ［ｉ］＝１に対してステップ２０４における点の加算（ＥＣＡＤＤ）とステップ２０５における２倍算（ＥＣＤＢＬ）とが実行される。ステップ２０６の後、ワーク変数Ｖの値はＶ＝ｄ［ｉ，０］で表される。
図２および３のアルゴリズムと個人鍵ｄの間には、次の（ＣＯＲ．１）および（ＣＯＲ．２）の相関関係がある。
（ＣＯＲ．１）  値ｄのビット値と実行される演算の間に相関関係がある。図３のアルゴリズムにおいて、ｄの各ビット値に従って、ＥＣＤＢＬ、またはＥＣＤＢＬおよびＥＣＡＤＤが行われる。
（ＣＯＲ．２）  値ｄのビット値とワーク変数の値の間に相関関係がある。図３のアルゴリズムにおいて、ステップ１０６の後のＶの値はＶ＝（ｄ［ｉ，０］）Ａ＝（２ｉｄ［ｉ］）Ａ＋（ｄ［ｉ−１，０］）Ａで表される。
ＳＰＡは相関関係（ＣＯＲ．１）に基づいて個人鍵を求める。ＤＰＡは相関関係（ＣＯＲ．２）に基づいて個人鍵を推定する。ＲＰＡは相関関係（ＣＯＲ．１）および（ＣＯＲ．２）の任意のいずれかに基づいて個人鍵を推定する。
ＳＰＡは、単一の電力波形を測定し、スマートカード内部で行われている処理を推定することによって個人鍵を推定する。
例えば、図３のアルゴリズムを処理するスマートカードの消費電力を測定し、図４に例示された電力波形が得られたと仮定する。図４のように、得られた消費電力波形ＡおよびＤがＥＣＡＤＤとＥＣＤＢＬを識別できるような形状を有するとき、相関関係（ＣＯＲ．１）に従って、電力波形Ｄとその後続の波形Ａの組はビット値１に対応し、単独の波形Ｄはビット値０に対応する。このようにして、個人鍵のビット列“００１１０”が求まる。
ＳＰＡに対する対策として、個人鍵ｄのビット値に関係なく一定の演算手順を繰り返すアド・アンド・ダブル・オールウェイズ（ａｄｄ−ａｎｄ−ｄｏｕｂｌｅ−ａｌｗａｙｓ、常に加算と２倍算を行う）およびモンゴメリ・ラダー（Ｍｏｎｔｇｏｍｅｒｙ−Ｌａｄｄｅｒ）等が知られている。
アド・アンド・ダブル・オールウェイズ法は、文献、Ｊ．Ｃｏｒｏｎ，”Ｒｅｓｉｓｔａｎｃｅ  ａｇａｉｎｓｔ  ｄｉｆｆｅｒｅｎｔｉａｌ  ｐｏｗｅｒ  ａｎａｌｙｓｉｓ  ｆｏｒ  ｅｌｌｉｐｔｉｃ  ｃｕｒｖｅ  ｃｒｙｐｔｏｇｒａｐｈｉｃ  ｃｒｙｐｔｏｓｙｓｔｍｅ”，ＣＨＥＳ’９９，ＬＮＣＳ  １７１７，ｐｐ．２９２−３０２，Ｓｐｒｉｎｇｅｒ−Ｖｅｒｌａｇ，１９９９に記載されている。
モンゴメリ・ラダー法は、文献、Ｐ．Ｍｏｎｔｇｏｍｅｒｙ，”Ｓｐｅｅｄｉｎｇ  ｔｈｅ  Ｐｏｌｌａｒｄ  ａｎｄ  ｅｌｌｉｐｔｉｃ  ｃｕｒｖｅ  ｍｅｔｈｏｄｓ  ｆｏｒ  ｆａｃｔｏｒｉｚａｔｉｏｎｓ”，Ｍａｔｈ  ｏｆ  Ｃｏｍｐ，ｖｏｌ．４８，ｐｐ．２４３−２６４，１９８７に記載されている。
図５は、通常のアド・アンド・ダブル・オールウェイズのアルゴリズムを示している。この場合、演算の手順は、個人鍵ｄの各ビット値に関係なく、ＥＣＡＤＤ，ＥＣＤＢＬ，ＥＣＡＤＤ，ＥＣＤＢＬ，．．．，ＥＣＡＤＤ，ＥＣＤＢＬとなる。
ＤＰＡは、複数の電力波形を測定して解析することによって個人鍵を推定する。次の手順（ＤＰＡ．０１）〜（ＤＰＡ．０３）は、図３のアルゴリズムに対するＤＰＡの例を示している。
（ＤＰＡ．０１）  ｋ個のランダムな与えられた点Ａ０，Ａ１，Ａ０，．．．Ａｋ−１に対して、各Ａｊのｄ倍算を行っている期間の消費電力が測定される。Ａｊに対するスカラー倍算において測定されたｋ個の消費電カデータの集合がＣ（Ａｊ，ｔ）で表される（ｊ＝０，１，．．．ｋ−１）。
（ＤＰＡ．０２）  以下の手順に従って、ｄ［０］の値が推定され、その推定が正しいどうかが判定される。
−  推定値ｄ［０］が正しいと仮定する。この仮定に基づいて、ｉ＝０についてステップ２０３〜２０６が終了した時点における、スマートカード内部の変数Ｖの座標ｘのデータ値をそれぞれのＡｊについて予想する。例えばｄ［０］＝１と仮定した場合、図３のアルゴリズムに従ってＶ＝Ａｊと予想できる。予想の結果、Ｖのデータ値の最下位ビットが１であるとき、Ｃ（Ａｊ，ｔ）をＧ１に分類し、Ｖのデータ値の最下位ビットが０であるとき、Ｃ（Ａｊ，ｔ）をＧ０に分類する。分類に用いられるＶのデータ値は、ｘの代わりにｙまたはｚのデータ値であってもよい。
−  上述の分類に基づいて、次の式で表される電力差分曲線を作成する。
Δ（ｔ）＝｛Ｇ１に属するＣ（Ａｉ，ｔ）の平均｝
−｛Ｇ０に属するＣ（Ａｊ，ｔ）の平均｝
−  その電力差分曲線が図６Ａに示すようなスパイクを有するときは、ｄ［０］の推定値が正しいと判定する。その電力差分曲線が図６Ｂに示すように平坦なときは、ｄ［０］の推定値が誤りであると判定する。
（ＤＰＡ．０３）  手順（ＤＰＡ．０２）を、ｄ［１］，ｄ［２］，．．．ｄ［ｍ−１］に対して順に繰り返し実行することによって個人鍵ｄの値を求める。ｄ［ｈ］に対して手順（ＤＰＡ．０２）を実行するとき、手順（ＤＰＡ．０２）における分類の基準となるＶのデータとして、ｉ＝ｈについて終了した時点のデータが用いられる。Ｖのデータ値の予想にあたっては、既に求められたｄ［０］〜ｄ［ｈ−１］の値と今回推定したｄ［ｈ］の値が用いられる。その理由は、Ｖの値が、Ｖ＝２ｈｄ［ｈ］Ａ＋ｄ［ｈ−１，０］Ａ、即ち既に求められたｄ［０］〜ｄ［ｈ−１］と今回推定したｄ［ｈ］によって決定される値だからである。
ＤＰＡは、スマートカードの消費電力がデータ値の“１”の数に比例するという性質に基づいている。
ＤＰＡに対する一般的な対策として乱数を用いた方法が知られている。その方法は、スマートカード内部で生成された乱数を用いて変数データを隠蔽またはランダム化することによって、ＤＰＡによるデータ値の推定を防止する。
例えば、ランダム化座標と呼ばれる方法は、投影座標またはヤコビアン座標の点のデータ表現をランダム化する。この場合、通常の暗号処理において、アファイン座標を表すワーク変数（ｘ，ｙ）に対して、ワーク変数が、投影座標（ｒ×ｘ，ｒ×ｙ，ｒ×ｚ）に変換され、またはヤコビアン座標（ｒ２×ｘ，ｒ３×ｙ，ｒ×ｚ）に変換される。ここで、ｒは乱数を表す。乱数ｒによって全ての座標データがランダム化され、ワーク変数の値は予測不可能となり、ＤＰＡが防止できる。それによってワーク変数の値はランダム化されるが、乱数ｒの値に関係なくワーク変数の値はいずれも同一の点を表すので、ｄ［０］〜ｄ［ｍ−１］の計算後に、求めた座標をアファイン座標に逆変換することによって、通常の処理と同じ演算結果ｄＡｊが一意的に求められる。
次に、ＲＰＡを説明する。ＲＰＡは、個人鍵ｄのビット値を推定し、その値に基づいて特定の入力点を選択してそれを暗号装置のスカラー倍算の入力として供給することによって、個人鍵ｄを推定する。スカラー倍算の特定のタイミングにおけるワーク変数値が０であれば、ＲＰＡはビット値の推定が正しいと判定し、そうでない場合は推定が誤りであると判定する。ワーク変数値が０であるか否かは、ＳＰＡにおける単一の電力波形を用いても、またＤＰＡにおける複数の電力波形の差分を用いても判定できる。
次の手順（ＲＰＡ．０１）〜（ＲＰＡ．０４）は、図３のアルゴリズムに対するＲＰＡの例を示している。ＲＰＡにおいて、攻撃者は、既に求められたｄ［０］，ｄ［１］，．．．ｄ［ｈ−１］に基づいて、次のビット値ｄ［ｈ］を求める。
（ＲＰＡ．０１）  既知の値ｄ［０］，ｄ［１］，．．．ｄ［ｈ−１］と、推定値ｄ［ｈ］とから、Ａ＝（ｄ［ｈ，０］−１（ｍｏｄ  φ））Ｑを求める。ここで、φは位数（ｏｒｄｅｒ）の値であり、ＱはＱ＝（ｘ，０）または（０，ｙ）を満たす楕円曲線上の点、即ち座標ｘまたはｙが０となる座標である。
（ＲＰＡ．０２）  スマートカードにｄＡを演算させて、消費電力波形Ｃ（Ａ，ｄ）を測定する。
（ＲＰＡ．０３）  消費電力波形Ｃ（Ａ，ｄ）の曲線のうち、ステップ２０３〜２０６のｉ＝ｈ，ｈ＋１に対応する部分波形を観察して、ワーク変数Ｖの座標ｘが０であるかどうかを判定する。Ｖの座標ｘが０かどうかの判定法については、前述のＧｏｕｂｉｎの文献を参照されたい。
ＲＰＡが可能な理由は、ｄ［ｈ］の推定が正しいとき、ステップ２０３〜２０６のループがｉ＝ｈについて完了した後、ワーク変数Ｖの座標ｘまたはｙが０となるからである。Ｖの座標ｘまたはｙが０となると、この値がｉ＝ｈ＋１に対する演算に用いられるときに、例外的処理が発生し、この例外処理は電力波形によって観察できる。
図７Ａおよび７Ｂは、ＲＰＡにおける電力波形を例示している。
ｄ［ｈ］の推定が正しいときにｉ＝ｈに対するループ処理の後にＶの座標値を表す波形が出現する理由は、手順（ＲＰＡ．０１）に従ってＡが与えられるからである。このようなＡを与えることによって、ｄ［ｈ］の推定が正しいときにｉ＝ｈに対するステップ２０３〜２０６のループ処理の後のＶの値がＱに一致し、座標ｘまたはｙの値が０となる。
従って、ワーク変数の座標値が攻撃者の意図したタイミングにおいて０となることを回避するようアルゴリズムを作成することによってＲＰＡを防止することができる。
基本的にデータをランダム化するＤＰＡ対策によってＲＰＡを防止できるが、例外がある。例えば、ＤＰＡ対策の１つであるランダム化座標は、ＲＰＡに対して脆弱である。これは、ＤＰＡ対策なしの処理におけるワークデータを（Ｘ，Ｙ，Ｚ）としたとき、ランダム化座標を用いた場合のワークデータは（ｒ×Ｘ，ｒ×Ｙ，ｒ×Ｚ）となるからである。即ち、ＤＰＡ対策なしの処理における座標値が０である場合、ランダム化座標における座標値もｒの値に関係なく０となる。
本発明者によって公表された、伊豆、他の文献、“楕円曲線暗号向けサイドチャネル対策方式の比較評価”、２００３年、暗号と情報セキュリティシンポジウム（ＳＣＩＳ２００３）、８Ｄ−３には、楕円曲線暗号に対応する公開鍵暗号の電力解析攻撃の対策として、ＳＰＡおよびＤＰＡに対して最も安全な対策は、ランダム化座標（Ｒａｎｄｏｍｉｚｅｄ  Ｐｒｏｊｅｃｔｉｖｅ  Ｃｏｏｒｄｉｎａｔｅｓ）（ＲＰＣ）、ランダム化曲線（Ｒａｎｄｏｍｉｚｅｄ  Ｃｕｒｖｅ）（ＲＣ）、指数分割法（Ｅｘｐｏｎｅｎｔ  Ｓｐｌｉｔｔｉｎｇ）（ＥＳ）、点の隠蔽（Ｐｏｉｎｔ  Ｂｌｉｎｄｉｎｇ）（ＰＢ）の４つの対策であることが記載されている。これらは、ＤＰＡ対策であるが、ＳＰＡ対策とともに用いることによってＤＰＡとＳＰＡの双方を防止できる。
表１は、アド・アンド・ダブル・オールウェイズ法を併用した場合の、ＳＰＡ、ＤＰＡおよびＲＰＡに対する安全性と、点のスカラー倍算に必要な処理量の比較を示している。
2005008955.tif 000006
ここで、Ｓは電力解析攻撃に対して安全であること、Ｖは電力解析攻撃に対して脆弱であることを表す。Ｅは、図５のアド・アンド・ダブル・オールウェイズ法による点のスカラー倍算の処理時間を表し、Ａは、点の加算、減算および２倍算の処理量を表し、Ｉは逆元計算の処理量を表している。
ＲＰＣおよびＲＣはその処理が高速であるが、ＲＰＡに対して弱い。ＥＳおよびＰＢはＲＰＡに対し安全であるがその処理が遅い。
図８Ａは、投影座標に基づくＲＰＣのアルゴリズムを示している。図８Ｂは、ヤコビアン座標に基づくＲＰＣのアルゴリズムを示している。図８Ｃは、アファイン座標に基づくＲＣのアルゴリズムを示している。
これらのアルゴリズムは、（ｉ）入力点Ａの座標データのランダム化（図８Ａのステップ４０１〜４０２；図８Ｂのステップ５０１〜５０２；図８Ｃのステップ６０１〜６０２）、（ｉｉ）アド・アンド・ダブル・オールウェイズを用いたスカラー倍算（図８Ａのステップ４０３〜４０８；図８Ｂのステップ５０３〜５０８；図８Ｃのステップ６０３〜６０８）、および（ｉｉｉ）データのランダム化を解除して元に戻して（ｄｅ−ｒａｎｄｏｍｉｚｅ）（逆ランダム化）、演算結果を出力する（図８Ａのステップ４０９〜４１０；図８Ｂのステップ５０９〜５１０；図８Ｃの６０９〜６１０）の３段階で構成される。
段階（ｉ）はＤＰＡ対策のための処理である。乱数ｒを生成し、図８ＡにおいてはＡ’＝（ｒ×ＡＸ，ｒ×ＡＹ，ｒ×ＡＺ）、図８ＢにおいてはＡ’＝（ｒ２×ＡＸ，ｒ３×ＡＹ，ｒ×ＡＺ）、図８ＣにおいてはＡ’＝（ｒ２×ＡＸ，ｒ３×ＡＹ）に従って座標データをランダム化し、それによって、これらのデータが攻撃者によって推定されるのを防ぐ。ここで、ＡＸ，ＡＹ，ＡＺはそれぞれ点Ａの座標（Ｚ，Ｙ，Ｚ）を表す。
段階（ｉｉｉ）は、データのランダム化を解除して、通常の暗号処理と同じ処理値を出力するための処理である。図８ＡにおいてはＶ＝（Ｖ［０］Ｘ／Ｖ［０］Ｚ，Ｖ［０］Ｙ／Ｖ［０］Ｚ）、図８ＢにおいてはＶ＝（Ｖ［０］Ｘ／（Ｖ［０］Ｚ））２，Ｖ［０］Ｙ／（Ｖ［０］Ｚ）３）、図８ＣにおいてはＶ＝（Ｖ［０］Ｘ／ｒ２，Ｖ［０］Ｙ／ｒ３）が処理される。
しかし、これらの対策はＲＰＡには無効である。その理由は、段階（ｉ）のランダム化において座標値と乱数ｒの積を導入するからである。例えば、図８Ｃにおいて、ランダム化を行わない場合のワーク変数データをＶ＝（ＶＸ，ＶＹ）とすると、段階（ｉ）ステップ６０３〜６０８のワーク変数データはＶ’＝（ｒ２×ＶＸ，ｒ３×ＶＹ）で表される。即ち、ランダム化を行わない時のＶの座標Ｘ，Ｙの値いずれかが０のとき、Ｖ’の座標Ｘ，Ｙの値いずれかも乱数ｒに関係なく０となり、ＲＰＡが適用できる条件を満たす。図８Ａおよび８Ｂに示したＲＰＣおよびＲＰＡについても同様である。
処理時間は、ＲＰＣおよびＲＣにおいてアド・アンド・ダブル・オールウェイズ演算が１回、ランダム化の解除のための逆元演算が１回必要であり、合計Ｅ＋Ｉである。
図９ＡはＥＳのアルゴリズムを示している。図９ＢはＰＢのアルゴリズムを示している。
これらのアルゴリズムは、図８Ａ〜８Ｃのアルゴリズムと同様に、（ｉ）入力点Ａの座標データのランダム化（図９Ａのステップ７０１〜７０２；図９Ｂのステップ８０１〜８０２）、（ｉｉ）アド・アンド・ダブル・オールウェイズを用いたスカラー倍算（図９Ａのステップ７０３〜７０４；図９Ｂのステップ８０３〜８０４）、および（ｉｉｉ）データのランダム化を解除して元に戻し、演算結果を出力する（図９Ａのステップ７０５〜７０６；図９Ｂの８０５〜８０６）の３段階で構成される。
図９Ａにおいて、段階（ｉ）ではスカラー値ｄに対して、ｄ＝ｄ１＋ｄ２を満たすランダムなスカラー値ｄ１およびｄ２が生成される。段階（ｉｉ）では、前述のｄ１およびｄ２に対してＶ１＝ｄ１ＡおよびＶ２＝ｄ２Ａで表されるスカラー倍算を、図５のアド・アンド・ダブル・オールウェイズ演算に従って行う。ランダムなｄ１およびｄ２に対するスカラー倍算によってワーク変数をランダム化し、それによってＤＰＡ対策が実現される。段階（ｉ）および（ｉｉ）によって攻撃者の意図したタイミングでワーク変数の座標値が０となることが防止されて、ＲＰＡ対策が実現される。段階（ｉｉｉ）では、Ｖ＝Ｖ１＋Ｖ２＝ｄＡ＋（ｄ−ｒ）Ａ＝ｄＡの演算によって、データのランダム化を解除して元に戻し、ｄＡを出力する。
図９Ｂにおいて、段階（ｉ）では入力点Ａに対し、Ａ＝Ａ１＋Ａ２を満たすランダムな点Ａ１およびＡ２を生成している。段階（ｉｉ）では前述の点Ａ１およびＡ２に対してＶ１＝ｄＡ１およびＶ２＝ｄＡ２で表されるスカラー倍算を、図５のアド・アンド・ダブル・オールウェイズ演算に従って行う。ランダムな点Ａ１およびＡ２に対するスカラー倍算によってワーク変数をランダム化し、それによってＤＰＡ対策が実現される。段階（ｉ）および（ｉｉ）によって攻撃者の意図したタイミングでワーク変数の座標値が０となることが防止されて、ＲＰＡ対策が実現される。段階（ｉｉｉ）では、Ｖ＝Ｖ１＋Ｖ２＝ｄ（Ａ１＋Ａ２）＝ｄＡの演算によって、データのランダム化を解除して元に戻し、ｄＡを出力する。
ＥＳの場合、アド・アンド・ダブル・オールウェイズ演算を２回と、ランダム化の解除の際に点の加算を１回を必要とするので、処理時間は合計で２Ｅ＋Ａである。ＰＢの場合、アド・アンド・ダブル・オールウェイズ演算を２回と、データのランダム化とその解除の際に点の加算または減算を３回を必要とするので、処理時間は合計で２Ｅ＋３Ａである。
従って、点のスカラー倍算の処理量が少ない公知の公開鍵暗号処理法ではＲＰＣに対して弱く、ＲＰＣに対して安全な公知の公開鍵暗号処理法ではスカラー倍算の処理量が多くなる。
発明者たちは、スカラー倍算の処理量が少なく、かつＳＰＡ、ＤＰＡおよびＲＰＣに対して安全な公開鍵暗号の処理法を実現することの必要性を認識した。
本発明の目的は、スカラー倍算の処理量が少なく、かつＳＰＡ、ＤＰＡおよびＲＰＣに対して安全な公開鍵暗号の処理法を実現することである。
発明の概要
本発明の特徴によれば、個人鍵を用いて楕円曲線暗号処理を行う暗号装置は、乱数に基づいて生成された楕円曲線上の点Ｒを初期点Ｖ０にセットするランダム化手段と、その楕円曲線暗号のための或るスカラー値ｄのビット・シーケンスに従って、その初期点Ｖ０と楕円曲線上の或る入力点Ａのスカラー倍との和Ｖ１＝Ｖ０＋ｄＡの演算を実行する演算手段と、その演算によって得られた和Ｖ１からその初期点Ｖ０を減算する演算Ｖ＝Ｖ１−Ｖ０を実行するランダム化解除手段と、そのランダム化解除手段によって得られた点Ｖを出力として供給する手段と、を具えている。
本発明の別の特徴によれば、暗号装置は、個人鍵を用いてべき乗剰余暗号処理を行う暗号装置であって、乱数に基づいて生成された整数ｒを初期値Ｖ０にセットするランダム化手段と、そのべき乗剰余暗号のための或る値ｄを表すｍビット・シーケンスに従って、その初期値Ｖ０と或る入力値ａに対するべき乗剰余演算Ｖ１＝Ｖ０×Πａ＾（２ｉｄ［ｉ］）（ｍｏｄ  ｎ）＝ｒ×ａｄ（ｍｏｄ  ｎ）の演算（ｉ＝０，１，．．．ｍ−１）を実行する演算手段と、その演算によって得られた値Ｖ１とｒ（ｍｏｄ  ｎ）の逆元ｒ−１（ｍｏｄ  ｎ）との乗算剰余演算Ｖ＝Ｖ１×ｒ−１（ｍｏｄ  ｎ）を実行するランダム化解除手段と、そのランダム化解除手段によって得られた値Ｖを出力として供給する手段と、を具える。ここで、Πａｉは積ａ０×ａ１×．．．×ａｍ−１を表し、ａ＾ｄはａｄを表す。
本発明は、上述の暗号装置を実現するプログラムに関する。
本発明は、上述の暗号装置を実現する方法に関する。
本発明によれば、スカラー倍算の処理量が少なく、かつＳＰＡ、ＤＰＡおよびＲＰＣに対して安全な公開鍵暗号の処理法を実現できる。
図面において同じ要素には同じ参照番号が付されている。
【図面の簡単な説明】  図１は、スマートカードのような暗号デバイスにおける秘密鍵を用いた暗号化／復号の構成の例を示している。
図２は、通常のバイナリ法によるべき乗剰余のアルゴリズムを示している。
図３は、通常のバイナリ法による点のスカラー倍算のアルゴリズムを示している。
図４は、スマートカードの消費電力を測定して得られた電力波形を示している。
図５は、通常アド・アンド・ダブル・オールウェイズのアルゴリズムを示している。
図６Ａは、スパイクを有する、時間に対する消費電力の曲線を示している。
図６Ｂは、平坦な、時間に対する電力差分曲線を示している。
図７Ａおよび７Ｂは、ＲＰＡにおける電力波形を例示している。
図８Ａは、投影座標に基づくＲＰＣのアルゴリズムを示している。
図８Ｂは、ヤコビアン座標に基づくＲＰＣのアルゴリズムを示している。
図８Ｃは、アファイン座標に基づくＲＣのアルゴリズムを示している。
図９Ａは、ＥＳ暗号のアルゴリズムを示している。
図９Ｂは、ＰＢ暗号のアルゴリズムを示している。
図１０は、本発明による暗号処理装置の概略的構成を示している。
図１１は、図１０の暗号化装置によって実行される、本発明の電力解析攻撃対策が施された公開鍵暗号処理のためのアルゴリズムを示している。
図１２は、図１０の暗号化装置によって実行される、本発明による電力解析攻撃対策を楕円曲線暗号に適用した基本的アルゴリズムを示す。
図１３は、図１０の暗号化装置によって実行される、本発明による電力解析攻撃対策をＲＳＡ暗号に適用した基本的アルゴリズムを示す。
図１４〜１６は、図１２におけるランダムな点Ｒの生成のアルゴリズムを示している。
図１７は、図１２における投影座標における点Ｒの生成のアルゴリズムを示している。
図１８は、図１２におけるヤコビアン座標における点Ｒの生成のアルゴリズムを示している。
図１９は、図１２におけるワーク変数Ｖ［２］に対する点の２倍算の実施形態を示している。
図２０は、図１６、２０および１９のアルゴリズムを組み合わせた、図１２に示された本発明による基本的アルゴリズムの実施形態を示している。
好ましい実施形態の説明
図１０は、本発明による暗号処理装置１０の概略的構成を示している。暗号処理装置１０は、値ａ、ｄおよびｎまたは値Ａおよびｄを入力して供給する入力部１２と、乱数Ｒまたはｒを発生する乱数生成部１４と、乱数生成部１４からの乱数Ｒまたはｒに従ってワーク変数をＶ’［０］：＝Ｒ（またはｒ）、Ｖ［２］＝Ａ（またはａ）として初期化するワーク変数初期化部１６と、ワーク変数Ｖ’［０］、Ｖ’［１］およびＶ［２］を格納するメモリ１８と、を具えている。暗号処理装置１０は、さらに、値ｄの各ビット値を検出しながら初期化部１６のワーク変数に対して公開鍵加算（ＰＵＢＡＤＤ）および公開鍵２倍算（ＰＵＢＤＢＬ）を繰り返し実行して、Ｖ’［０］＝ｄＡ＋Ｒまたはａｄ×ｒ（ｍｏｄ  ｎ）を計算するスカラー倍算処理部２０を具えている。ここで、ＰＵＢＡＤＤは点の加算または法ｎの乗算剰余を表し、ＰＵＢＤＢＬは点の２倍算または法ｎの２乗剰余を表す。ＰＵＢＡＤＤとＰＵＢＤＢＬの演算手順はｄビット値に依存しない。暗号処理装置１０は、さらに、Ｖ’［０］からＶ＝ＰＵＢＳＵＢ（Ｖ’［０］，Ｒまたはｒ）を計算してＲまたはｒの影響を取り除いたＶ＝ｄＡを計算するランダム・データ除去部を具えている。ここで、公開鍵減算ＰＵＢＳＵＢは点の減算またはｒの逆元を用いた法ｎにおける乗算剰余を表す。暗号処理装置１０は、さらに、演算結果の値Ｖ＝ｄＡまたはｖ＝ａｄ（ｍｏｄ  ｎ）を出力する出力部２４を含んでいる。Ｒまたはｒは、暗号装置１０内部で生成され、外部からはアクセスできない値である。
暗号化装置１０は、さらに、プロセッサ３２と、ＲＯＭのようなプログラム・メモリ３４とを含んでいる。プロセッサ３２は、メモリ３４に格納されているプログラムに従ってこれらの要素１２〜２４を制御する。代替構成として、プロセッサ３２は、要素１２〜２４に対応する機能を実現するメモリ３４中のプログラムを実行することによって要素１２〜２６を実現してもよい。この場合、図１０はフロー図として見ることができる。
図１１は、図１０の暗号化装置１０によって実行される、本発明による電力解析攻撃への対策が施された公開鍵暗号処理のための基本的アルゴリズムを示している。このアルゴリズムは楕円曲線暗号とＲＳＡ暗号の双方に適用できる。
図１１のアルゴリズムは、図８Ａ〜８Ｃのアルゴリズムと同様に、（ｉ）データのランダム化（ステップ１００４〜１００６）、（ｉｉ）アド・アンド・ダブル・オールウェイズを用いたスカラー倍算（ステップ１００８）、および（ｉｉｉ）データのランダム化を解除して元に戻し、演算結果Ｖを出力する（ステップ１０１０）の３段階で構成される。
図１１を参照すると、ステップ１００２において、入力部１２は、値ａ、ｄおよびｎまたは値Ａおよびｄを入力する。ステップ１００４において、生成部１４は、ランダムなデータＲまたはｒを生成する。Ｒは、楕円曲線暗号において楕円曲線上のランダムな点のデータであり、ＲＳＡにおいてランダムな整数値である。
ステップ１００６において、初期化部１６は、アド・アンド・ダブル・オールウェイズ法で用いられるワーク変数を、Ｖ’［０］＝Ｒまたはｒ、Ｖ［２］＝Ａまたはａと、初期化する。
ステップ１００８において、点のスカラー倍算実行部２０は、ワーク変数Ｖ’［０］、Ｖ’［０］、Ｖ［２］を用いてアド・アンド・ダブル・オールウェイズを実行する。即ち、ｉ＝０，１，．．．，ｍ−１に対して、楕円曲線暗号においてＶ’［１］＝ＥＣＡＤＤ（Ｖ’［０］，Ｖ［２］），Ｖ［２］＝ＥＣＤＢＬ（Ｖ［２］）、およびＶ’［０］＝Ｖ’［ｄ［ｉ］］の演算を繰り返し実行し、またはＲＳＡ暗号においてＶ’［１］＝Ｖ’［０］×Ｖ［２］（ｍｏｄ  ｎ）、Ｖ［２］＝Ｖ［２］２（ｍｏｄ  ｎ）、およびＶ’［０］＝Ｖ’［ｄ［ｉ］］の演算を繰り返し実行する。個人鍵ｄのビット値に関係なく、アド・アンド・ダブル・オールウェイズの所定の演算パターンを繰り返すことによってＳＰＡ対策を実現する。ステップ１００４においてＶ’［０］＝Ｒまたはｒとセットすることによって、ワーク変数Ｖ’［０］およびＶ’［１］の値がランダム化されて、ＤＰＡを防止できる。Ｖ［２］の値はランダム化されない。その理由は、アド・アンド・ダブル・オールウェイズ法においてはＶ［２］の値を利用したＤＰＡおよびＳＰＡが不可能なので、Ｖ［２］をランダム化する必要がないからである。Ｖ［２］の値は、個人鍵ｄのビット値と関係なく、Ａの２倍算または２乗算を繰り返し実行することによって求められる値なので、この値を利用してＤＰＡを実行することはできない。
ステップ１０１０において、ランダム・データ除去部２２はランダム化されたデータを元に戻す。そのために、ステップ１００４で生成されＲに対して、楕円曲線暗号においてはＶ＝Ｖ’［０］−Ｒが計算され、ＲＳＡにおいてはＶ＝Ｖ’［０］×Ｒ−１またはｒ−１が求められる。ステップ１０１２において、出力部２４は演算結果Ｖを出力する。
このようにして、図１１に示されたアルゴリズムによってＳＰＡおよびＤＰＡが防止される。次に、図１１のアルゴリズムを楕円曲線暗号に適用したとき、ＲＰＡが防止されることを説明する。
図１２は、図１０の暗号化装置１０によって実行される、本発明による電力解析攻撃対策を楕円曲線暗号に適用した基本的アルゴリズムを示す。
図１２を参照すると、ステップ１１０１において、乱数点生成部１４は楕円曲線上のランダムな点Ｒを生成または選択する。初期化部１６は、ステップ１１０２において初期値としてＲをワーク変数Ｖ’［０］にセットし、ステップ１１０３において初期値としてＡをワーク変数Ｖ［２］にセットする。
ステップ１１０４〜１１０８を含むループは、ワーク変数Ｖ’［０］、Ｖ’［１］およびＶ［２］に対してアド・アンド・ダブル・オールウェイズ法による点のスカラー倍算を実行する。このループは、図５のステップ３０３〜３０７のＲＰＡ対策無しのアド・アンド・ダブル・オールウェイズ法と同じ処理を行っているが、Ｖ’［０］の初期値としてランダム点Ｒがセットされることによって、ＲＰＡ対策が実現される。
そのような初期値によって、図１２のワーク変数Ｖ’［０］およびＶ’［１］と図５のＶ［０］およびＶ［１］の間の関係は、Ｖ’［０］＝Ｖ［０］＋ＲおよびＶ’［１］＝Ｖ［１］＋Ｒで表される。即ち、図５で計算されるワーク変数のＶ［０］およびＶ［１］の値に対して、図１２のアルゴリズムは、Ｖ’［０］＝Ｖ［０］＋ＲおよびＶ’［１］＝Ｖ［１］＋Ｒを求め、これらの値はＲに応じてランダムに変化する。即ち、ＲＰＣおよびＲＣのように、ランダム値Ｒに関係なくＶ’［０］およびＶ’［１］の座標データが０となることはない。従って、攻撃者は意図的にワーク変数の座標データ値を０とすることが不可能となり、ＲＰＡが防止される。
ステップ１１０４〜１１０８のループが終了した後、ステップ１１０９において出力部２４はＶ＝Ｖ’［０］−Ｒを計算することによって、Ｒによってランダム化されたデータを元に戻して、その値Ｖを出力する。
このようにして、本発明によるアルゴリズムはＲＰＡに対して安全な暗号処理を実現する。ＲＰＡ対策なしの図５のアルゴリズムと本発明による図１２のアルゴリズムを比較すると、ＲＰＡ対策のための追加的処理はステップ１１０１に示す点Ｒの生成と、ステップ１１０９における点Ｒの減算だけである。即ち、ＲＰＡ対策に関係する速度低下は、これら２つの処理分だけに限定されるので、図５の２倍の処理時間を必要とするＥＳおよびＰＢと比較すると高速な処理が実現される。
図１３は、図１０の暗号化装置１０によって実行される、本発明による電力解析攻撃対策をＲＳＡ暗号に適用した基本的アルゴリズムを示す。
図１３を参照すると、ステップ１２０１において、乱数生成部１４は乱数ｒを生成する。初期化部１６は、ステップ１２０２において初期値としてｒをワーク変数Ｖ’［０］にセットし、ステップ１２０３において初期値としてａをワーク変数Ｖ［２］にセットする。
ステップ１２０４〜１２０８を含むループは、ワーク変数Ｖ’［０］、Ｖ’［１］およびＶ［２］に対してアド・アンド・ダブル・オールウェイズ法によりべき剰余演算を実行してワーク変数を更新する。
ステップ１２０４〜１２０８のループが終了した後、ステップ１２０９において出力部２４はｒの逆元ｒ−１（ｍｏｄ  ｎ）とＶ’［０］の乗算剰余を計算することによって、ｒによってランダム化されたデータを元に戻して、その値Ｖを出力する。
ステップ１２０４〜１２０９におけるアド・アンド・ダブル・オールウェイズ法によるループによってＳＰＡを防ぎ、ワーク変数Ｖ’［０］の初期値に乱数ｒがセットされることによって、そのループにおけるワーク変数をランダムに変化させＤＰＡを防ぐ。
処理のオーバーヘッドについて、図５をＲＳＡに適用する場合と比較すると、ＲＰＡ対策のための追加的処理はステップ１２０１に示す追加処理はｒの生成と、ステップ１２０９に示すｒの逆元の乗算剰余だけである。
次に、図１２の楕円曲線暗号用の基本的アルゴリズムの実施形態について説明する。
図１２におけるステップ１１０１における点Ｒの生成、ステップ１１０７におけるＶ［２］の２倍算として、必要な計算量が異なる複数の実施形態が存在する。
図１４〜１８は、図１２におけるステップ１１０１を実現する相異なるランダムな点Ｒの生成のアルゴリズムを示している。
図１４を参照すると、ステップ１３０１において、乱数点生成部１４は、取り得る任意の座標Ｘの値をランダムに生成し、値ＸをＲＸにセットする。即ち、素
2005008955.tif 000007
数を、２べきの楕円曲線パラメータの場合ＧＦ（２ｍ）のランダムな値を与えることによって生成する。ステップ１３０２において所与の座標Ｘに対応する座標Ｙを求めＲＹを生成する。ステップ１３０３および１３０４において、Ｒ＝（ＲＸ，ＲＹ）とセットする。座標Ｘから座標Ｙを求めるためのアルゴリズムは、前記文献ＩＥＥＥ  Ｐ１３６３／Ｄ１３に記載されている。
図１５を参照すると、生成部１４は、ステップ１４０１において乱数ｓを生成し、ステップ１４０２において図５のアド・アンド・ダブル・オールウェイズによってベースポイントＧをｓ倍したｓＧをＲにセットする。あるいは、図５のアルゴリズムの代わりに、図１２のアルゴリズムをＲ＝Ｏ、ｄ＝ｓおよびＡ＝Ｇについて実行してもよい。このように同一アルゴリズムを共用することによって、リソースの利用を効率化できる。乱数ｓは任意の値であるが、それがスカラー値ｄのビット長を超える場合、ステップ１４０２のスカラー倍算による計算オーバーヘッドが大きい。例えば１６０ビットの楕円曲線暗号においてｓが１６０ビットの乱数であるとき、ステップ１４０２の計算量が大きくなる。その結果、本発明によるアルゴリズム全体の計算量が図５のアルゴリズムの概ね２倍となって処理速度が低下する。従って、ｓは２０〜３０ビットの値であることが好ましい。
図１６は、スマートカードの初期化等において点Ｒの初期値をランダムに与えた後、本発明による電力解析攻撃から保護された暗号処理が呼び出される度にその点Ｒの値を更新するアルゴリズムを示している。その更新を簡単な演算で実現することによって、図１４および１５に示されたアルゴリズムと比べて、その処理時間を短くできる。
ステップ１５０１において、生成部１４は、通常の電力解析攻撃対策において使用されるＲの値をメモリ上の特定の領域から読み込む。代替構成として、例えば図１４および１５に示した方法を用いて点Ｒの初期値を与えてもよい。ステップ１５０２において、生成部１４は、点Ｒに対して２倍算を行うことによってその値を更新する。ステップ１５０３において、生成部１４はその更新した点Ｒの値を次回の処理のために格納する。
図１７は、図１２における投影座標における点Ｒの生成のアルゴリズムを示している。図１８は、図１２におけるヤコビアン座標における点Ｒの生成のアルゴリズムを示している。
これらのアルゴリズムにおいては、生成部１４は、図１６のアルゴリズムと同様にスマートカードが初期化されるとき等において点Ｒの初期値をランダムに生成し、その後、本発明による暗号プログラムが呼び出される度に、生成部１４は点Ｒ初期値を更新する。
図１６のアルゴリズムと同様に、生成部１４は、ステップ１６０１においてメモリ１８に格納されている前回のＲ読み込み、ステップ１６０３において更新されたＲを格納する。図１７において、生成部１４は、ステップ１６０２において定数ｔを座標値Ｒ＝（ＲＸ，ＲＹ，ＲＺ）に乗算することによって初期値Ｒを更新する。図１８において、生成部１４は、ステップ１６０２において定数ｔ、ｔ２およびｔ３を座標値Ｒ（ＲＸ，ＲＹ，ＲＺ）の各成分に乗算することによって初期値Ｒを更新する。ｔの値として、例えばｔ＝３のような小さな値を選択することによって、Ｒの更新に必要な計算量を小さくできる。
図１９は、図１２におけるステップ１１０７におけるワーク変数Ｖ［２］に対する点の２倍算の実施形態を示している。
ステップ１１０７における点の２倍算は、同一ワーク変数Ｖ［２］に対して繰り返し実行され、Ｖ［２］の値はループ変数ｉを用いてＶ［２］＝２ｉ＋１Ａと表される。ヤコビアン座標および素体の場合について、同一の点に対して繰り返し実行される２倍算（点の２ｋ倍算）によって計算を高速化する手法が、本発明者の中の２人、武仲および伊藤によって２０００年５月１６日付けで公開された特開２０００−１３７４３６号公報（Ａ）に開示されており、ここでこの文献を引用して組み込む。図１９では、その公報における図２に示されている点の２ｋ倍算の手法が用いられる。
図１９におけるｉは、図１７におけるループ変数ｉの値と同じである。このアルゴリズムは、変数ＰとしてのＡ［２］＝（Ｘｉ，Ｙｉ，Ｚｉ）＝２ｉＡの入力からＡ［２］＝（Ｘｉ＋１，Ｙｉ＋１，Ｚｉ＋１）＝２ｉ＋１Ａの出力までの演算を表している。ｉ＝０のときは、ｉｆ文によってｉ＝０に対する処理に分岐することによっ
2005008955.tif 000008
めのワーク変数Ｒｉを計算するために、ｉ−１におけるワーク変数Ｔｉ−１の値を再利用することによって計算量が削減される。前記文献ＩＥＥＥ  Ｐ１３６３に記載されている標準的な点の２倍算を用いたとき、１回当たり１０回の乗算が必要であるが、図１９のアルゴリズムを用いたとき１回当たり８回の乗算のみを必要とする。即ち、図１９に示されたアルゴリズムを用いることによって、標準的な方法を用いるのと比較して点の２倍算に必要な計算量を２割だけ削減できる。
図２０は、図１５（Ｒ初期化）、１６（ステップ１１０１、Ｒの生成）および１９（ステップ１１０６、点の２ｋ倍算）のアルゴリズムを組み合わせた、図１２に示された本発明による基本的アルゴリズムの実施形態を示している。
代替構成として、図７のステップ１１０１として図１４〜１８のいずれかと、ステップ１１０６として図１９および前記文献ＩＥＥＥ  Ｐ１３６３のいずれか、の組み合わせであってもよい。
次に、図１３のＲＳＡ暗号用の基本的アルゴリズムの実施形態について説明する。ＲＳＡ暗号用の電力解析攻撃対策の場合、図１８がそのまま実施例となる。その理由は、ステップ１２０１における乱数ｒの生成、ステップ１２０６における２乗算の実現例には変形形態がないからである。
以上説明したように、本発明の実施形態によれば、ＳＰＡ、ＤＰＡおよびＲＰＡの全ての解析に対する対策が実現でき、かつ通常安全なものとして知られていたＥＳおよびＰＢと比較して計算量が小さくなる。
表２は、電力解析攻撃対策の通常の公開鍵暗号と本発明による楕円曲線暗号の比較を示している。表３は、電力解析攻撃対策の通常の公開鍵暗号と本発明によるＲＳＡ暗号の比較を示している。表３においてＲＰＣ、ＲＣおよびＰＢ暗号は楕円曲線暗号に適用できないので除外されている。
2005008955.tif 000009
2005008955.tif 000010
ここで、Ｓは解析に対して安全であること、Ｖは解析に対して脆弱であることを表す。電力解析攻撃対策なしのアド・アンド・ダブル・オールウェイズにおいて、スカラー算の処理時間がＥで表され、逆元計算の処理時間がＩで表され、点の加算、減算および２倍算がＡで表されるものとする。ＡはＥに比べて無視できるほど小さい。
通常の暗号化による処理量は表１のものである。本発明による図２０のアルゴリズムの処理量は、ステップ１７０２における点の２倍算とステップ１７１１における点の減算以外は、図５におけるアド・アンド・ダブル・オールウェイズと同じ演算を行うので、合計Ｅ＋２Ａと表される。
表２から分かるように、ＳＰＡ、ＤＰＡおよびＲＰＡの全てに対して安全な暗号は、ＥＳ暗号、ＰＢ暗号および本発明の暗号である。処理時間を比較すると、ＡはＥに比べて無視できるほど小さいので、本発明の暗号の処理時間は、安全なＥＳ暗号およびＰＢ暗号の処理時間のほぼ半分である。
ＡがＥと比べて無視できるほど小さいのは、アド・アンド・ダブル・オールウェイズにおいて点の加算と２倍算がそれぞれｍ回実行され、合計２ｍ回実行されることから明らかである。例えば、１６０ビット楕円曲線暗号においてｍ＝１６０としたとき、Ｅ＝３２０Ａとなる。
ＥＳに必要な計算は、ＲＳＡにおけるＥＳの演算手順が次の通りなので、２Ｅとなる。
2005008955.tif 000011
ここで、ｖ１およびｖ２の乗算剰余はべき乗剰余演算と比べて非常に小さく無視できると仮定している。本発明による図１３の処理は、ステップ１２０１〜１２０８に示すアド・アンド・ダブル・オールウェイズと、ステップ１２１０における逆元ｒ−１（ｍｏｄ  ｎ）の演算で構成されるので、処理量は合計Ｅ＋Ｉと表される。即ち、Ｅ＞Ｉに対して、本発明の方がＥＳよりも高速な処理を実現できる。ＥとＩの大小関係は、処理環境によって異なるが、一般的にＥは演算ビット長の３乗、Ｉは演算ビット長の２乗に比例するので、Ｅ＞Ｉという仮定は妥当である。このように、本発明は電力解析攻撃に対する安全性を損なうことなく、処理時間が小さい。
以上説明した実施形態は典型例として挙げたに過ぎず、その変形およびバリエーションは当業者にとって明らかであり、当業者であれば本発明の原理および請求の範囲に記載した発明の範囲を逸脱することなく上述の実施形態の種々の変形を行えることは明らかである。
【図１】
2005008955.tif 000012
【図２】
2005008955.tif 000013
【図３】
2005008955.tif 000014
【図４】
2005008955.tif 000015
【図５】
2005008955.tif 000016
2005008955.tif 000017
2005008955.tif 000018
2005008955.tif 000019
2005008955.tif 000020
2005008955.tif 000021
【図１０】
2005008955.tif 000022
【図１１】
2005008955.tif 000023
【図１２】
2005008955.tif 000024
【図１３】
2005008955.tif 000025
【図１４】
2005008955.tif 000026
【図１５】
2005008955.tif 000027
【図１６】
2005008955.tif 000028
【図１７】
2005008955.tif 000029
【図１８】
2005008955.tif 000030
【図１９】
2005008955.tif 000031
【図２０】
2005008955.tif 000032
【国際調査報告】
2005008955.tif 000033
2005008955.tif 000034
2005008955.tif 000035
2005008955.tif 000036