(57)【要約】【課題】楕円曲線暗号の電力解析攻撃に対する耐性を向上させる。【解決手段】ｉ＝１のときには、ｒ１×Ｐのスカラー倍算が計算され、ｉ＝２のときにはｒ２×Ｐのスカラー倍算が計算される。ｉ＝ｓのときには、ｒｓ×Ｐのスカラー倍算が計算される。また、ｉ＝ｓ＋１のときには、（ｄ−ｒ１−ｒ２−・・・−ｒｓ）×Ｐのスカラー倍算が計算される。そして、ｓ＋１個のスカラー倍算により得られる点の楕円加算ＥＣＡＤＤを計算することで、ｄ×Ｐのスカラー倍算を求めることができる。乱数を用いてスカラー倍算を個々に計算することで電力解析攻撃に対する楕円曲線暗号の耐性を向上させることができる。【選択図】      図３
2004163687.tif 000002
【特許請求の範囲】
【請求項１】
有限体上の楕円曲線Ｅと、楕円曲線上のベースポイントＰと、整数ｄを記憶する記憶手段と、
ｓ（ｓ≧２）個の乱数ｒ１〜ｒｓを発生する乱数発生手段と、
前記乱数発生手段により発生されるｓ個の乱数を用いて、ｒ１×Ｐ、ｒ２×Ｐ、・・・、ｒｓ×Ｐ、（ｄ−ｒ１−・・・−ｒｓ）×Ｐのｓ＋１個のスカラー倍算の演算をそれぞれ実行し、それらの演算により得られる点の楕円加算を実行してスカラー倍算ｄ×Ｐを計算する演算手段とを備える楕円曲線暗号装置。
【請求項２】
有限体上の楕円曲線Ｅと、楕円曲線上のベースポイントＰと、整数ｄとを記憶する記憶手段と、
乱数ｒ１とｒ２を発生する乱数発生手段と、
前記乱数発生手段により発生される乱数を用いて、ｒ１×Ｐのスカラー倍算と、ｒ２×Ｐのスカラー倍算と、（ｄ−ｒ１−ｒ２）×Ｐのスカラー倍算の演算をそれぞれ実行し、それらのスカラー倍算により得られる点の楕円加算を実行してスカラー倍算ｄ×Ｐを計算する演算手段とを備える楕円曲線暗号装置。
【請求項３】
有限体上の楕円曲線Ｅと、楕円曲線上のベースポイントＰと、整数ｄとを記憶する記憶手段と、
乱数ｒ１とｒ２を発生する乱数発生手段と、
前記乱数発生手段により発生される乱数を用いて、ｒ１×Ｐのスカラー倍算と、ｒ２×（ｒ１×Ｐ）のスカラー倍算と、（ｄ−ｒ１×ｒ２）×Ｐのスカラー倍算をそれぞれ実行し、ｒ２×（ｒ１×Ｐ）のスカラー倍算により得られる点Ｐ１と、（ｄ−ｒ１×ｒ２）×Ｐのスカラー倍算とにより得られる点Ｐ２との楕円加算によりスカラー倍算ｄ×Ｐを計算する演算手段とを備える楕円曲線暗号装置。
【請求項４】
有限体上の楕円曲線Ｅと、楕円曲線上のベースポイントＰと、整数ｄとを記憶する記憶手段と、
乱数ｒ１とｒ２を発生する乱数発生手段と、
前記乱数発生手段により発生される乱数を用いて、（ｄ−ｒ１）×Ｐのスカラー倍算と、（ｄ＋ｒ２）×Ｐのスカラー倍算と、ｒ２×（（ｄ−ｒ１）×Ｐ）のスカラー倍算と、ｒ１×（（ｄ＋ｒ２）×Ｐ）のスカラー倍算とをそれぞれ実行し、ｒ２×（（ｄ−ｒ１）×Ｐ）のスカラー倍算により得られる点Ｐ１と、ｒ１×（（ｄ＋ｒ２）×Ｐ）のスカラー倍算により得られる点Ｐ２との楕円加算と、楕円加算の演算結果と１／（ｒ１＋ｒ２）とのスカラー倍算を実行して、スカラー倍算ｄ×Ｐを計算する演算手段とを備える楕円曲線暗号装置。
【請求項５】
有限体上の楕円曲線Ｅと、楕円曲線上のベースポイントＰと整数ｄを記憶部に記憶させ、
ｓ個の乱数ｒ１〜ｒｓを発生させ、発生させたｓ個の乱数を用いて、演算部に、ｒ１×Ｐ、ｒ２×Ｐ、・・・、ｒｓ×Ｐ、（ｄ−ｒ１−・・・・−ｒｓ）×Ｐのｓ＋１個のスカラー倍算の演算をそれぞれ実行させ、それらの演算により得られる点の楕円加算を計算させてスカラー倍算ｄ×Ｐを計算させる楕円曲線暗号プログラム。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、楕円曲線暗号装置、楕円曲線暗号プログラム及び楕円曲線暗号演算方法に関する。
【０００２】
【従来の技術】
暗号方式は、共通鍵暗号方式と公開鍵暗号方式に大別される。共通鍵暗号方式と呼ばれるものは、暗号化と復号で同一の鍵（秘密鍵）を用いる方式であり、この秘密鍵を送信者と受信者以外の第三者にわからない情報とすることで安全性を保つ方式である。
【０００３】
公開鍵暗号方式とは、暗号化と復号で異なる鍵を用いる方式であり、暗号化を行うための鍵（公開鍵）を一般に公開する代わりに、暗号文を復号するための鍵（秘密鍵）を受信者のみの秘密情報とすることで安全性を保つ方式である。公開鍵暗号としてＲＳＡ暗号、楕円曲線暗号などが知られている。
【０００４】
楕円曲線暗号の例として、ＥＣＥＳ暗号プリミティブを説明する。送信者Ａは秘密鍵ｓ（ｓは整数）を持ち、受信者Ｂが秘密鍵ｔ（ｔは整数）を持つ場合に、楕円曲線Ｅと、楕円曲線Ｅ上に設定されるベースポイントＰ（ｘ，ｙ）と、公開鍵ｓ×Ｐ（送信者Ａの秘密鍵ｓとベースポイントＰとのスカラー倍算）と、公開鍵ｔ×Ｐ（受信者Ｂの秘密鍵ｔとベースポイントＰとのスカラー倍算）があらかじめ公開されている。このとき送信者Ａは、自分の秘密鍵ｓと、受信者Ｂの公開鍵ｔ×Ｐとのスカラー倍算ｓ×（ｔ×Ｐ）を計算し、そのｘ座標のビット表現を求め、このビット表現とメッセージのビット表現との間でビット対応のＥＯＲ演算を施すことで、メッセージｍに対する暗号文Ｃを生成し、それを受信者Ｂに送信する。受信者Ｂは、自分の秘密鍵ｔと、送信者Ａの公開鍵ｓ×Ｐとのスカラー倍算ｔ×（ｓ×Ｐ）を計算し、そのｘ座標のビット表現を求める。そして、”ｓ×（ｔ×Ｐ）＝ｔ×（ｓ×Ｐ）”という関係式が成立することを考慮して、そのビット表現と暗号文Ｃのビット表現との間でビット対応のＥＯＲ演算を施すことで、暗号文Ｃを復号しメッセージｍを得る。このようにして、ＥＣＥＳ暗号と呼ばれる楕円曲線暗号のプリミティブでは、スカラー倍演算を用いて暗号・復号処理を行う。
【０００５】
暗号の分野における技術の一つに、解読技術とよばれるものがある。解読技術とは秘密鍵等の秘密情報を暗号文等の入手可能な情報から推定する技術のことであり、様々な手法が存在する。その中で最近注目されている技術に、電力解析攻撃と呼ばれる手法がある。電力解析攻撃とは、１９９８年にＰｏｕｌ  Ｋｏｃｈｅｒによって考案された手法で、スマートカード等に搭載された暗号プロセッサに様々な入力データを与えた時の電力消費データを収集・解析することにより、暗号プロセッサ内部の鍵情報を推定する手法である。電力解析攻撃を用いれば、共通鍵暗号、公開鍵暗号共に暗号プロセッサから秘密鍵を推定できることが知られている。
【０００６】
電力解析攻撃には、単純電力解析（Ｓｉｎｇｌｅ  Ｐｏｗｅｒ  Ａｎａｌｙｓｉｓ；以下ＳＰＡという）、差分電力解析（Ｄｉｆｆｅｒｅｎｔｉａｌ  Ｐｏｗｅｒ  Ａｎａｌｙｓｉｓ；以下ＤＰＡという）の２種類が存在する。ＳＰＡは暗号プロセッサにおける単一の電力消費データの特徴から秘密鍵の推定を行う方法であり、ＤＰＡは多数の電力消費データの差分を解析することで秘密鍵の推定を行う方法である。
【０００７】
ＲＳＡ暗号に対してＳＰＡとＤＰＡを用いた推定法については、Ｔｈｏｍａｓ  Ｓ．Ｍｅｓｓｅｒｇｅｓ，  Ｅｚｚｙ  Ａ．Ｄａｂｂｉｓｈ  ａｎｄ  Ｒｏｂｅｒｔ  Ｈ．Ｓｌｏａｎ  ”Ｐｏｗｅｒ  Ａｎａｌｙｓｉｓ  Ａｔｔａｃｋｓ  ｏｆ  Ｍｏｄｕｌａｒ  Ｅｘｐｏｎｅｎｔｉｔｉａｔｉｏｎ  ｉｎ  Ｓｍａｒｔｃａｒｄｓ”，  Ｃｒｙｐｔｏｇｒａｐｈｉｃ  Ｈａｒｄｗａｒｅ  ａｎｄ  Ｅｍｂｅｄｄｅｄ  Ｓｙｓｔｅｍｓ（以下、ＣＨＥＳ’９９という），  Ｌｅｃｔｕｒｅ  Ｎｏｔｅｓ  ｉｎ  Ｃｏｍｐｕｔｅｒ  Ｓｃｉｅｎｃｅ  ｖｏｌ．  １７１７，  Ｓｐｒｉｎｇｅｒ−Ｖｅｒｌａｇ，  ｐｐ．１４４−１５７や、Ｊｅａｎ−Ｓｅｂａｓｔｅｉｎ  Ｃｏｒｏｎ  “Ｒｅｓｉｓｔａｎｃｅ  ａｇａｉｎｓｔ  Ｄｉｆｆｅｒｅｎｔｉａｌ  Ｐｏｗｅｒ  Ａｎａｌｙｓｉｓ  ｆｏｒ  Ｅｌｌｉｐｔｉｃ  Ｃｕｒｖｅ  Ｃｒｙｔｏｓｙｓｔｅｍｓ”，  Ｃｒｙｐｔｏｇｒａｐｈｉｃ  Ｈａｒｄｗａｒｅ  ａｎｄ  Ｅｍｂｅｄｄｅｄ  Ｓｙｓｔｅｍｓ  （ＣＨＥＳ’９９），  Ｌｅｃｔｕｒｅ  Ｎｏｔｅｓｉｎ  Ｃｏｍｐｕｔｅｒ  Ｓｃｉｅｎｃｅ  ｖｏｌ．  １７１７，  Ｓｐｒｉｎｇｅｒ−Ｖｅｒｌａｇ，  ｐｐ．２９２−３０２，  １９９９（以下、文献１という）などの文献にて述べられている。
【０００８】
一方、公開鍵暗号系の中で、ＲＳＡ暗号と並んで代表的なものに、楕円曲線暗号（Ｅｌｌｉｐｔｉｃ  Ｃｕｒｖｅ  Ｃｒｙｐｔｏｇｒａｐｈｙ）がある。これは、楕円曲線の離散対数問題に基づくもので、Ｎ．  Ｋｏｂｌｉｔｚ（”Ｅｌｌｉｐｔｉｃ  Ｃｕｒｖｅ  Ｃｒｙｐｔｏｓｙｓｔｅｍｓ”，  Ｍａｔｈｅｍａｔｉｃｓ  ｏｆＣｏｍｐｕｔｅｒｓ，  Ｖｏｌ．  ４８，  ｐｐ．  ２０３−２０９，  １９８７．）とＶ．  Ｍｉｌｌｅｒ（”Ｕｓｅ  ｏｆ  ｅｌｌｉｐｔｉｃ  ｃｕｒｖｅｓ  ｉｎ  ｃｒｙｐｔｏｇｒａｐｈｙ”，  Ａｄｖａｎｃｅｓ  ｉｎ  Ｃｒｙｐｔｏｌｏｇｙ−Ｐｒｏｃｅｅｄｉｎｇｓ  ｏｆ  Ｃｒｙｐｔｏ  ’８５，  Ｌｅｃｔｕｒｅ  Ｎｏｔｅｓ  ｉｎ  Ｃｏｍｐｕｔｅｒ  Ｓｃｉｅｎｃｅ，  ２１８（１９８６），  Ｓｐｒｉｎｇｅｒ−Ｖｅｒｌａｇ，  ｐｐ  ４１７−４２６）により提案された。
【０００９】
楕円曲線暗号においては、公開鍵点Ｑは、例えば、公開されたベースポイントと呼ばれる楕円曲線上の点Ｐに対して、スカラー値である秘密鍵ｄを用いた楕円曲線上の点のスカラー倍算Ｑ＝ｄ×Ｐで計算された楕円曲線上の点となる。以下にスカラー倍算Ｑ＝ｄ×Ｐの演算アルゴリズムについて説明する。
【００１０】
図１１は、Ｂｉｎａｒｙ  Ｍｅｔｈｏｄにより整数ｄのＭＳＢ（Ｍｏｓｔ  Ｓｉｇｎｉｆｉｃａｎｔ  Ｂｉｔ）からスカラー倍算ｄ×Ｐの計算を行うアルゴリズム１の演算プログラムを示す図である。
【００１１】
以下に述べるアルゴリズム１及び他のアルゴリズムの説明では、ｄはｎビットのスカラー値、Ｐ，Ｑは楕円曲線上の点、ＥＣＡＤＤは楕円加算、ＥＣＤＢＬは楕円２倍算をそれぞれ表す。
【００１２】
変数Ｔの初期値として点Ｐの座標を設定し、変数ｉをｎ−２から０まで変化させて楕円２倍算ＥＣＤＢＬ（Ｔ）を計算する。
２進展開の係数ｄ［ｉ］が”１”のときには、楕円２倍算ＥＣＤＢＬ（Ｔ）により得られる点Ｔと、点Ｐの楕円加算ＥＣＡＤＤ（Ｔ，Ｐ）を計算し、計算結果を変数Ｔに格納する。
【００１３】
上記の処理を変数ｉ＝ｎ−２からｉ＝０まで実行した後、変数Ｔの値をスカラー倍算ｄ×Ｐにより得られる点Ｑの座標として出力する。
上記のアルゴリズム１は、ｄ［ｉ］の値が”１”か否かにより楕円加算ＥＣＡＤＤが実行されたり、されなかったりする。ＳＰＡ攻撃では、この性質を利用して秘密鍵ｄを解析する。多くの実験から楕円加算ＥＣＡＤＤと楕円２倍算ＥＣＤＢＬの電力波形は特徴的で容易に区別可能であることが知られている。このことから、演算アルゴリズム１の処理の電力波形を測定すれば、その波形から楕円加算ＥＣＡＤＤと楕円２倍算ＥＣＤＢＬの処理の順序と回数がわかるので秘密鍵ｄを解析できる。
【００１４】
このＳＰＡ攻撃への対策について、ａｄｄ−ａｎｄ−ｄｏｕｂｌｅ−ａｌｗａｙｓと呼ばれる方法が上述した文献１で提案されている。この方法は、常に楕円２倍算と楕円加算が交互に計算されるためＳＰＡ攻撃に対して安全である。
【００１５】
図１２は、アルゴリズム１に対してａｄｄ−ａｎｄ−ｄｏｕｂｌｅ−ａｌｗａｙｓを施したアルゴリズム２の演算プログラムを示す図である。
変数Ｔ［０］の初期値として点Ｐの座標を設定し、変数ｉをｎ−２から０まで変化させて楕円２倍算ＥＣＤＢＬ（Ｔ［０］）を計算し、計算結果を変数Ｔ［０］に設定する。
【００１６】
さらに、点Ｔ［０］と点Ｐとの楕円加算ＥＣＡＤＤ（Ｔ［０］、Ｐ）を計算し、計算結果を変数Ｔ［１］に設定する。
そして、係数ｄ［ｉ］の値により定まるＴ［ｄ［ｉ］］の値を変数Ｔ［０］に設定する。
【００１７】
上記の処理をｉ＝ｎ−２からｉ＝０まで実行した後、変数Ｔ［０］の値をスカラー倍算ｄ×Ｐにより得られる点Ｑの座標として出力する。
上述したアルゴリム２によればＳＰＡ攻撃を防ぐことが可能となる。しかしながら、文献１には、これらのアルゴリズムに対するＤＰＡ攻撃についても述べられており、アルゴリズム２に対するＤＰＡ攻撃により秘密鍵情報が解析可能であることを示している。
【００１８】
文献１は、ＲＰＣ（Ｒａｎｄｏｍｉｚｅｄ  Ｐｒｏｊｅｃｔｉｖｅ  Ｃｏｏｒｄｉｎａｔｅｓ）という乱数を使用した楕円曲線上の点の表現を導入することで、アルゴリズム２に対するＤＰＡ攻撃に対する対策について提案している。
【００１９】
図１３は、アルゴリズム２に対してＲＰＣを施したアルゴリズム３の演算プログラムを示す図である。
変数Ｔ’［２］の初期値として、乱数を使用した楕円曲線上の点ＲＰＣ（Ｐ）の座標を設定し、変数Ｔ’［０］の初期値としてＴ’［２］を設定する。
【００２０】
変数ｉをｎ−２から０まで変化させて、楕円２倍算ＥＣＤＢＬ（Ｔ’［０］）を計算し、計算結果を変数Ｔ’［０］に設定する。点Ｔ’［０］と点Ｔ’［２］の楕円加算ＥＣＡＤＤ（Ｔ’［０］、Ｔ’［２］）を計算し、計算結果を変数Ｔ’［１］に設定する。ｄ［ｉ］の値に応じてＴ’［０］またはＴ’［１］の値をＴ’［０］に格納する。
【００２１】
上述した処理をｉ＝ｎ−２からｉ＝０まで実行した後、変数Ｔ’［０］をＲＰＣ表現から楕円曲線上の点の座標に変換し、その座標をスカラー倍算ｄ×Ｐにより得られる点Ｑの座標として出力する。
【００２２】
図１４は、Ｂｉｎａｒｙ  Ｍｅｔｈｏｄにより整数ｄのＬＳＢ（Ｌｅａｓｔ  Ｓｉｇｎｉｆｉｃａｎｔ  Ｂｉｔ）からスカラー倍算ｄ×Ｐの計算を行うアルゴリズム４の演算プログラムを示す図である。このアルゴリズム４は、楕円加算ＥＣＡＤＤと楕円２倍算ＥＣＤＢＬを常に計算するアルゴリズムで、かつＲＰＣを適用したものである。
【００２３】
最初に、変数Ｔ’［０］の初期値として０を設定し、変数Ｔ’［２］の初期値として、楕円楕円曲線上の点ＲＰＣ（Ｐ）の座標を設定する。
変数ｉを０からｎ−１まで変化させて点Ｔ’［０］と点Ｔ’［２］の楕円加算ＥＣＡＤＤ（Ｔ’［０］，Ｔ’［２］）を計算し、計算結果を変数Ｔ’［１］に設定する。点Ｔ’［２］の楕円２倍算ＥＣＤＢＬ（Ｔ’［２］）を計算し、計算結果を変数Ｔ’［２］に設定する。ｄ［ｉ］の値に応じてＴ’［０］またはＴ’［１］の値をＴ’［０］に格納する。
【００２４】
上述した処理をｉ＝０からｉ＝ｎ−１まで実行した後、変数Ｔ’［０］をＲＰＣ表現から楕円曲線上の点の座標に変換し、変換した座標をスカラー倍算ｄ×Ｐにより得られる点Ｑの座標として出力する。
【００２５】
上記の乱数を用いる方法と同様の効果を持つ方法として、ＳＰＡ対策を行ったＭｏｎｔｇｏｍｅｒｙ−ＬａｄｄｅｒとＲＰＣを併用した方法が、Ｔ．  Ｉｚｕ，  ａｎｄ  Ｔ．  Ｔａｋａｇｉ，  ”Ａ  Ｆａｓｔ  Ｐａｒａｌｌｅｌ  Ｅｌｌｉｐｔｉｃ  Ｃｕｒｖｅ  Ｍｕｌｔｉｐｌｉｃａｔｉｏｎ  Ｒｅｓｉｓｔａｎｔ  ａｇａｉｎｓｔ  Ｓｉｄｅ  Ｃｈａｎｎｅｌ  Ａｔｔａｃｋｓ’’，  ＰＫＣ  ２００２，  ＬＮＣＳ  ２２７４，  ｐｐ．２８０−２９６，  Ｓｐｒｉｎｇｅｒ−Ｖｅｒｌａｇ，  ２００２．  （Ｉｚｕ−Ｔａｋａｇｉ）で提案されている。これは、ＳＰＡ対策を行ったＭｏｎｔｇｏｍｅｒｙ−Ｌａｄｄｅｒと呼ばれるスカラー倍算方式を用いるのが特徴である。Ｍｏｎｔｇｏｍｅｒｙ−Ｌａｄｄｅｒでは、スカラー倍算Ｑ＝ｄ×Ｐにおいて、常に楕円２倍算と楕円加算を計算することにより、差が１Ｐとなるような２点の計算を行う。
【００２６】
図１５は、ＳＰＡ対策を行ったＭｏｎｔｇｏｍｅｒｙ−ＬａｄｄｅｒとＲＰＣを使用したスカラー倍算のアルゴリズム５の演算プログラムを示す図である。
最初に、変数Ｔ’［０］の初期値として乱数を使用した楕円曲線上の点ＲＰＣ（Ｐ）を設定し、変数Ｔ’［１］の初期値として点Ｔ’［０］の楕円２倍算ＥＣＤＢＬ（Ｔ’［０］）により得られる点の座標を設定する。
【００２７】
次に、変数ｉをｎ−２から０まで変化させ、楕円２倍算ＥＣＤＢＬ（Ｔ’〔ｄ〔ｉ〕〕）を計算し、計算結果を変数Ｔ’〔２〕に格納する。
次に、Ｔ’〔０〕とＴ’〔１〕の楕円加算ＥＣＡＤＤ（Ｔ’〔０〕，Ｔ’〔１〕）を計算し、計算結果を変数Ｔ’〔１〕に格納する。
【００２８】
次に、係数ｄ〔ｉ〕の値により定まるＴ［２−ｄ［ｉ］］の値を変数Ｔ’［０］に設定する。
同様に係数ｄ［ｉ］の値により定まるＴ’［１＋ｄ［ｉ］］の値を変数Ｔ’［１］に設定する。
【００２９】
上記の処理をｉ＝ｎ−２からｉ＝０まで繰り返した後、乱数を用いて表現した変数Ｔ’［０］の座標を元の楕円曲線上の座標に逆変換してスカラー倍算ｄ×Ｐの点Ｒの座標として出力する。
【００３０】
ＲＰＣと同様の効果を持つスカラー倍算の演算方法として、Ｍ．  Ｊｏｙｅ，  ａｎｄ  Ｃ．  Ｔｙｍｅｎ，  “Ｐｒｏｔｅｃｔｉｏｎｓ  ａｇａｉｎｓｔ  ｄｉｆｆｅｒｅｎｔｉａｌ  ａｎａｌｙｓｉｓ  ｆｏｒ  ｅｌｌｉｐｔｉｃ  ｃｕｒｖｅ  ｃｒｙｐｔｏｇｒａｐｈｙ”，  ＣＨＥＳ  ２００１，ＬＮＣＳ  ２１６２，  ｐｐ．  ３７７−３９０，  Ｓｐｒｉｎｇｅｒ−Ｖｅｒｌａｇ，  ２００１．  （ＪＴ０１）において、ＲＣ（Ｒａｎｄｏｍｉｚｅｄ  Ｃｕｒｖｅ）法がある。ＲＣは、素体上のワイヤストラス型の楕円曲線にのみ適用できる方法であり、ＲＰＣと同様に乱数を用いた点の表現を用いるＤＰＡ対策である。
【００３１】
上述したアルゴリズム３のＲＰＣの代わりにＲＣを適用したアルゴリズム３’を図１６に示す。またアルゴリズム５にＲＣを適用したアルゴリズム５’を図１７に示す。なお、図１６及び図１７において、ＲＣで表現された楕円曲線上の点はダブルダッシュ（”）付の変数で示す。
【００３２】
図１６及び図１７のアルゴリズム３’及び５’の演算プログラムは、基本的には、図１３及び図１５の演算プログラムと同じである。異なる点は、楕円曲線上の点Ｐの座標をＲＣにより変換した座標を用いてスカラー倍算の計算を行うことである。
【００３３】
スカラー倍算ｄ×Ｐの実現法には上述したアルゴリズム以外にＷｉｎｄｏｗ  Ｍｅｔｈｏｄと呼ばれる方法がある。例えば、４−ｂｉｔのＷｉｎｄｏｗ  Ｍｅｔｈｏｄの場合、初期処理としてＰの０〜１５倍を計算し、その結果をテーブルとして持っておき、秘密鍵を４ビット単位（これをＷｉｎｄｏｗと呼ぶ）で処理する。
【００３４】
図１８に４ビットＷｉｎｄｏｗ  Ｍｅｔｈｏｄの基本的なアルゴリズムであるアルゴリズム６を示す。なお、ｄはｎビットのスカラー値で４の倍数と仮定する。また、ｄ［ｎ−１，ｎ−４］は、整数ｄの下位ｎ−１ビット目からｎ−４ビット目までの４ビットの値であり、Ｗ［ｉ］は、Ｗｉｎｄｏｗ  Ｍｅｔｈｏｄで使用するテーブルである。
【００３５】
最初に、変数Ｗ［０］に初期値として楕円曲線上の点０の座標を設定し、変数Ｗ［１］の初期値として楕円曲線上の点Ｐの座標を設定し、変数Ｗ［２］の初期値として点Ｐの楕円２倍算ＥＣＤＢＬ（Ｐ）の点の座標を設定する。
【００３６】
次に、変数ｉを３から１５まで変化させ、点Ｗ［ｉ−１］と点Ｐとの楕円加算ＥＣＡＤＤ（Ｗ［ｉ−１］，Ｐ）を計算し、計算結果をテーブルＷ［ｉ］に格納する。
【００３７】
上記の処理により、例えば、変数ｉが３の場合には、Ｗ［３］＝ＥＣＡＤＤ（Ｗ［２］，Ｐ）となり、楕円２倍算２×Ｐの計算により得られる点と、点Ｐとの楕円加算により得られる点の座標が算出され、テーブルＷ［ｉ］に格納される。
【００３８】
次に、変数ＱとしてＷ［ｄ［ｎ−１，ｎ−４］］を設定する。
次に、変数ｉをｎ−５から０まで４ビット単位で変化させ、楕円２倍算ＥＣＤＢＬ（Ｑ）の計算を４回行う。４回の楕円２倍算ＥＣＤＢＬの演算により、変数ｉにより指定されるビット位置から４ビット分のデータをシフトさせる。さらに、楕円加算ＥＣＡＤＤ（Ｑ，Ｗ［ｄ［ｉ，ｉ−３］］）の計算を行い、４回の楕円２倍算ＥＣＤＢＬの演算結果と、テーブルＷから取得するＷ［ｄ［ｉ，ｉ−３］］との楕円加算ＥＣＡＤＤの計算を行う。
【００３９】
上記の処理をｉ＝ｎ−５からｉ＝０まで実行することにより、スカラー倍算ｄ×Ｐの点の座標を求める。
上記のアルゴリズム６を使用した場合、整数ｄのビット値によって行われたり行われなかったりする処理は存在しない。そのためＷｉｎｄｏｗ  ＭｅｔｈｏｄはＢｉｎａｒｙ  Ｍｅｔｈｏｄと異なり一般にＳＰＡ攻撃に対して安全であるといわれている。しかし、Ｗｉｎｄｏｗ  ＭｅｔｈｏｄはＢｉｎａｒｙ  Ｍｅｔｈｏｄ  と同様にＤＰＡ攻撃に対しては安全と言えず、文献１の電力解析の手法でｄを推定することが可能である。
【００４０】
Ｗｉｎｄｏｗ  ＭｅｔｈｏｄのＤＰＡ対策としてＢｉｎａｒｙ  Ｍｅｔｈｏｄと同様にＲＰＣやＲＣが有効であることが知られている。
図１９は、アルゴリズム６に対してＲＰＣを適用したアルゴリズム７の演算プログラムを示し、図２０は、アルゴリズム６に対してＲＣを適用したアルゴリズム８の演算プログラムを示す。
【００４１】
図１９のアルゴリズム７及び図２０のアルゴリズム８によりＤＰＡ耐性を向上させることができる。
【００４２】
【非特許文献１】
Ｊｅａｎ−Ｓｅｂａｓｔｅｉｎ  Ｃｏｒｏｎ  “Ｒｅｓｉｓｔａｎｃｅ  ａｇａｉｎｓｔ  Ｄｉｆｆｅｒｅｎｔｉａｌ  Ｐｏｗｅｒ  Ａｎａｌｙｓｉｓ  ｆｏｒ  Ｅｌｌｉｐｔｉｃ  Ｃｕｒｖｅ  Ｃｒｙｔｏｓｙｓｔｅｍｓ”，  Ｃｒｙｐｔｏｇｒａｐｈｉｃ  Ｈａｒｄｗａｒｅ  ａｎｄ  Ｅｍｂｅｄｄｅｄ  Ｓｙｓｔｅｍｓ  （ＣＨＥＳ’９９），  Ｌｅｃｔｕｒｅ  Ｎｏｔｅｓ  ｉｎ  Ｃｏｍｐｕｔｅｒ  Ｓｃｉｅｎｃｅ  ｖｏｌ．  １７１７，  Ｓｐｒｉｎｇｅｒ−Ｖｅｒｌａｇ，  ｐｐ．２９２−３０２，  １９９９
【００４３】
【非特許文献２】
Ｋ．  Ｉｔｏｈ，  Ｔ．  Ｉｚｕ，  ａｎｄ  Ｍ．  Ｔａｋｅｎａｋａ  ”Ａｄｄｒｅｓｓ−ｂｉｔ  Ｄｉｆｆｅｒｅｎｔｉａｌ  Ｐｏｗｅｒ  Ａｎａｌｙｓｉｓ  ｏｆ  Ｃｒｙｐｔｏｇｒａｐｈｉｃ  Ｓｃｈｅｍｅｓ  ＯＫ−ＥＣＤＨ  ａｎｄ  ＯＫ−ＥＣＤＳＡ”，  Ｃｒｙｐｔｏｇｒａｐｈｉｃ  Ｈａｒｄｗａｒｅ  ａｎｄ  Ｅｍｂｅｄｄｅｄ  Ｓｙｓｔｅｍｓ  （ＣＨＥＳ２００２），  Ｐｒｅ−ｐｒｏｃｅｅｄｉｎｇ，  ｐｐ．１２９−１４３
【００４４】
【発明が解決しようとする課題】
従来、上述したアルゴリズム３，５，３’，５’、７，８を用いれば、ＳＰＡ及びＤＰＡ攻撃に対して安全であると言われていた。
【００４５】
しかしながら、Ｋ．  Ｉｔｏｈ，  Ｔ．  Ｉｚｕ，  ａｎｄ  Ｍ．  Ｔａｋｅｎａｋａ  ”Ａｄｄｒｅｓｓ−ｂｉｔ  Ｄｉｆｆｅｒｅｎｔｉａｌ  Ｐｏｗｅｒ  Ａｎａｌｙｓｉｓ  ｏｆ  Ｃｒｙｐｔｏｇｒａｐｈｉｃ  Ｓｃｈｅｍｅｓ  ＯＫ−ＥＣＤＨ  ａｎｄ  ＯＫ−ＥＣＤＳＡ”，  Ｃｒｙｐｔｏｇｒａｐｈｉｃ  Ｈａｒｄｗａｒｅ  ａｎｄ  Ｅｍｂｅｄｄｅｄ  Ｓｙｓｔｅｍｓ  （ＣＨＥＳ２００２），  Ｐｒｅ−ｐｒｏｃｅｅｄｉｎｇ，  ｐｐ．１２９−１４３  （以下、文献２という）において、アルゴリズム５に対して電力解析を行う手法が発表された。従来のＤＰＡはデータの変化がもたらす消費電力に注目していたのに対し、この手法（ａｄｄｒｅｓｓ−ｂｉｔ  ＤＰＡ）はアドレスの変化がもたらす消費電力に注目した解析手法である。
【００４６】
例えば、図１５のアルゴリズム５において、Ｔ’［２］＝ＥＣＤＢＬ（Ｔ’［ｄ［ｉ］］）の処理（図１５に＊で示す処理）は、ｄ［ｉ］の値によって、Ｔ’［０］が使用されるか、Ｔ’［１］が使用されるかが決定される。そのため楕円加算ＥＣＡＤＤで使用するデータが格納されているアドレスはｄ［ｉ］と強い相関を持つ。同様のことは、Ｔ’［０］＝Ｔ’［２−ｄ［ｄ［ｉ］］の処理及びＴ’〔１〕＝Ｔ’〔１＋ｄ〔ｉ〕〕の処理（図１５に＃で示す処理）にも言える。これにより、ａｄｄｒｅｓｓ−ｂｉｔＤＰＡではアドレスとの相関を利用することで秘密鍵ｄを解析することができる。
【００４７】
文献２のａｄｄｒｅｓｓ−ｂｉｔ  ＤＰＡは、アルゴリズム３’、５’にも適用可能である。また、アルゴリズム７，８のＷｉｎｄｏｗ  Ｍｅｔｈｏｄも、秘密鍵ｄの値と使用するテーブルとが強い関係を持つため同様の攻撃が可能であると考えられる。
【００４８】
従って、アルゴリズム３、５、３’、５’、７，８がａｄｄｒｅｓｓ−ｂｉｔ  ＤＰＡ攻撃に対して安全であるとは言えない。
文献２のａｄｄｒｅｓｓ−ｂｉｔ  ＤＰＡへの対策としてスカラー値をランダムに変化させる手法、例えば、ｅｘｐｏｎｅｎｔ−ｓｐｌｉｔｔｉｎｇが提案されている。
【００４９】
Ｅｘｐｏｎｅｎｔ−ｓｐｌｉｔｔｉｎｇでは、乱数ｒを発生させ、ｒ×Ｐと（ｄ−ｒ）×Ｐを別々に計算し、ｒ×Ｐ＋（ｄ−ｒ）×Ｐ＝ｄ×Ｐという性質から、スカラー倍算ｄ×Ｐを計算する。ここでスカラー倍算ｒ×Ｐ、（ｄ―ｒ）×Ｐには、従来のＳＰＡ、ＤＰＡ攻撃に耐性を持つアルゴリズムを用いる。Ａｄｄｒｅｓｓ−ｂｉｔ  ＤＰＡについては、スカラー値がランダムに変化するためｄに関する情報が集めらないので防御が可能となる。
【００５０】
図２１は、Ｅｘｐｏｎｅｎｔ−ｓｐｌｉｔｔｉｎｇ  のアルゴリズム９の演算プログラムを示す図である。
図２１において、ｒａｎｄｏｍ（）は、ｎビットの乱数を発生させる関数である。また、ｓｃａｌａｒ（ｄ，Ｐ）は、スカラー倍算ｄ×Ｐを計算する関数であり、上述したアルゴリズム３，３’、５，７等により実現される。
【００５１】
Ｅｘｐｏｎｅｎｔ−ｓｐｌｉｔｔｉｎｇに対する攻撃報告は知られていないが、提案者らの主張通り一方のスカラー倍算をＳＰＡ／ＤＰＡ耐性を持たないアルゴリズムで計算した場合、スカラー倍算全体にＤＰＡ攻撃が可能である。
【００５２】
本発明の課題は、電力解析攻撃に対する耐性を向上させることである。
【００５３】
【課題を解決するための手段】
本発明の楕円曲線暗号装置は、有限体上の楕円曲線Ｅと、楕円曲線上のベースポイントＰと、整数ｄを記憶する記憶手段と、ｓ（ｓ≧２）個の乱数ｒ１〜ｒｓを発生する乱数発生手段と、前記乱数発生手段により発生されるｓ個の乱数を用いて、ｒ１×Ｐ、ｒ２×Ｐ、・・・、ｒｓ×Ｐ、（ｄ−ｒ１−・・・−ｒｓ）×Ｐのｓ＋１個のスカラー倍算の演算をそれぞれ実行し、それらの演算により得られる点の楕円加算を実行してスカラー倍算ｄ×Ｐを計算する演算手段とを備える。
【００５４】
この発明によれば、ｓ個の乱数を用いてｓ＋１回のスカラー倍算の計算を行うことにより、電力解析攻撃に対する楕円曲線暗号の耐性を向上させることができる。
【００５５】
本発明の他の楕円曲線暗号装置は、有限体上の楕円曲線Ｅと、楕円曲線上のベースポイントＰと、整数ｄとを記憶する記憶手段と、乱数ｒ１とｒ２を発生する乱数発生手段と、前記乱数発生手段により発生される乱数を用いて、ｒ１×Ｐのスカラー倍算と、ｒ２×Ｐのスカラー倍算と、（ｄ−ｒ１−ｒ２）×Ｐのスカラー倍算の演算をそれぞれ実行し、それらのスカラー倍算により得られる点の楕円加算を実行してスカラー倍算ｄ×Ｐを計算する演算手段とを備える。
【００５６】
この発明によれば、２個の乱数を用いて３回のスカラー倍算の計算を行うことで、電力解析攻撃に対する楕円曲線暗号の耐性を向上させることができる。
本発明の他の楕円曲線暗号装置は、有限体上の楕円曲線Ｅと、楕円曲線上のベースポイントＰと、整数ｄとを記憶する記憶手段と、乱数ｒ１とｒ２を発生する乱数発生手段と、前記乱数発生手段により発生される乱数を用いて、ｒ１×Ｐのスカラー倍算と、ｒ２×（ｒ１×Ｐ）のスカラー倍算と、（ｄ−ｒ１×ｒ２）×Ｐのスカラー倍算をそれぞれ実行し、ｒ２×（ｒ１×Ｐ）のスカラー倍算により得られる点Ｐ１と、（ｄ−ｒ１×ｒ２）×Ｐのスカラー倍算とにより得られる点Ｐ２との楕円加算によりスカラー倍算ｄ×Ｐを計算する演算手段とを備える。
【００５７】
この発明によれば、乱数ｒ１とｒ２を乗算した値を用いてスカラー倍算の計算を行うことで電力解析による個々の乱数の推定が困難になり、整数ｄの推定がより困難になる。これにより楕円曲線暗号の電力解析攻撃に対する耐性を向上させることができる。また、点Ｐ１と点Ｐ２の１回の楕円加算の計算を行うだけでよいので楕円加算の計算時間を短縮できる。さらに、乱数ｒ１と乱数ｒ２の乗算値が整数ｄと同じビット長を持てばよいので、乱数ｒ１，ｒ２のビット長を整数ｄのビット長より短くできる。これにより、乱数と点Ｐとのスカラー倍算の計算時間を短くでき、スカラー倍算の全体の計算時間を短縮できる。
【００５８】
本発明の他の楕円曲線暗号装置は、有限体上の楕円曲線Ｅと、楕円曲線上のベースポイントＰと、整数ｄとを記憶する記憶手段と、乱数ｒ１とｒ２を発生する乱数発生手段と、前記乱数発生手段により発生される乱数を用いて、（ｄ−ｒ１）×Ｐのスカラー倍算と、（ｄ＋ｒ２）×Ｐのスカラー倍算と、ｒ２×（（ｄ−ｒ１）×Ｐ）のスカラー倍算と、ｒ１×（（ｄ＋ｒ２）×Ｐ）のスカラー倍算とをそれぞれ実行し、ｒ２×（（ｄ−ｒ１）×Ｐ）のスカラー倍算により得られる点Ｐ１と、ｒ１×（（ｄ＋ｒ２）×Ｐ）のスカラー倍算により得られる点Ｐ２との楕円加算と、楕円加算の演算結果と１／（ｒ１＋ｒ２）とのスカラー倍算を実行して、スカラー倍算ｄ×Ｐを計算する演算手段とを備える。
【００５９】
この発明によれば、乱数ｒ１，ｒ２を用いて、５回のスカラー倍算を実行することで電力解析による整数ｄの推定を困難にできる。
なお、記憶手段は、例えば、図１の記憶部１６及びレジスタ１４に対応し、演算手段は、演算部１２または演算器１３に対応する。
【００６０】
【発明の実施の形態】
以下、本発明の実施の形態を、図面を参照しながら説明する。実施の形態の楕円曲線暗号装置は、例えば、専用の情報処理装置、パーソナルコンピュータ、ＩＣカード（スマートカード）等に内蔵されたＩＣチップ、携帯電話、携帯情報端末装置、ＤＶＤプレーヤ等からなり、楕円曲線の演算を行うプロセッサを有している。
【００６１】
図１は、本発明に係る楕円曲線暗号装置１１の要部の構成を示す図である。実施の形態の楕円曲線暗号装置１１の演算部１２は、演算器（ＣＰＵ）１３と、複数のレジスタからなるレジスタ１４とからなり、演算結果は再びレジスタ１４に入力される。記憶部１６は、ハードディスク、メモリ等からなり、後述する楕円曲線暗号のスカラー倍算の演算プログラムが記憶される。演算部１２は、記憶部１６に記憶されている演算プログラムを実行し、乱数ｒ１，ｒ２等を発生し、それらの乱数を用いてスカラー倍算ｄ×Ｐの計算を行う。
【００６２】
以下の説明では、本発明に係る楕円曲線暗号の演算方法を、素体ＧＦ（ｐ）（ｐは５以上の素数）上の楕円曲線に適用した場合について説明する。
ＧＦ（ｐ）上の円曲線Ｅは、以下の式で表せる。
【００６３】
Ｅ：ｙ＾２＝ｘ＾３＋ａ×ｘ＋ｂ
ここでａ，ｂ，ｘ，ｙはＧＦ（ｐ）の要素で、４×ａ＾３＋２７×ｂ＾２≠０を満たす。
【００６４】
図２は、本発明の第１の実施の形態のスカラー倍算の演算プログラムを示す図である。
第１の実施の形態は、ｎビットの整数ｄと、楕円曲線上のベースポイントＰと、パラメータｓを入力として受け取り、ｓ個の乱数ｒ１，ｒ２，…、ｒｓを発生させ、スカラーｄをｒ１、ｒ２、…、ｒｓ、ｄ−ｒ１−ｒ２−…−ｒｓに分割し、ｓ＋１個のスカラー倍算ｒ１×Ｐ、ｒ２×Ｐ、…、ｒｓ×Ｐ、（ｄ−ｒ１−ｒ２−…−ｒｓ）×Ｐを個々に計算するものである。
【００６５】
以下に述べる第１の実施の形態（他の実施の形態も同様）の演算プログラムは、演算部１２により実行され、演算途中の値、あるいは演算結果はレジスタ１４に格納される。
【００６６】
演算部１２は、変数ｒ［ｓ＋１］として整数ｄを設定する（図２，Ｓ２１）。変数ｉをｉ＝１からｉ＝ｓまで順に変化させ（図２，Ｓ２３）、ステップＳ２４及びＳ２５の処理を実行する。
【００６７】
ステップＳ２４において、関数ｒａｎｄｏｍ（）により乱数を発生させ、発生した乱数を変数ｒ〔ｉ〕に設定する。次のステップＳ２５において、変数ｒ［ｓ＋１］から乱数ｒ〔ｉ〕を減算し、減算結果を変数ｒ［ｓ＋１］に設定する。
【００６８】
ステップＳ２３〜Ｓ２６の次に、スカラー倍算の演算を行う。変数ｉをｉ＝１からｉ≦ｓ＋１まで変化させ（図２，Ｓ２８）、関数ｓｃａｌａｒ（ｒ〔ｉ〕，Ｐ）を用いてｒ〔ｉ〕×Ｐのスカラー倍算を計算し、計算結果を変数ｄ［ｉ］に格納する（図２，Ｓ２９）。
【００６９】
ここで、ｒ〔ｉ〕は関数ｒａｎｄｏｍ（）により発生されるｓ個の乱数ｒ〔１〕、ｒ〔２〕・・・ｒ〔ｓ〕である。上記のステップＳ２３〜Ｓ２５の処理をｓ回繰り返すことにより、最終的なｒ〔ｓ＋１〕の値としてｒ［ｓ＋１］＝ｄ−ｒ１−ｒ２−・・・・−ｒｓ”が得られている。そして、ステップＳ２８〜Ｓ２９の処理をｓ＋１回繰り返すことにより、スカラー倍算ｒ１×Ｐ、ｒ２×Ｐ、ｒ３×Ｐ、・・・ｒｓ×Ｐ、（ｄ−ｒ１−ｒ２−・・・−ｒｓ）×Ｐが順に計算される。
【００７０】
次に、スカラーの統合を行う。変数ｉをｉ＝１からｉ≦ｓ＋１まで変化させ（図２，Ｓ３２）、それぞれの点の楕円加算ＥＣＡＤＤ（Ｑ，ｄ〔ｉ〕）を計算し、計算結果を変数Ｑに格納する（図２，Ｓ３３）。上記の処理をｉ＝１〜ｓ＋１まで実行した後、変数Ｑをスカラー倍算ｄ×Ｐの計算結果として出力する（図２，Ｓ３５）。
【００７１】
上記のステップＳ３２及びＳ３３の処理は、ｓ＋１個の点の楕円加算ＥＣＡＤＤを計算する処理である。ステップＳ３２〜Ｓ３３のループの処理をｓ＋１回繰り返した後の変数Ｑは以下の式で表せる。
【００７２】
2004163687.tif 000003
上記の式（１）は、ｄ×Ｐと等しいので変数Ｑを求めることでスカラー倍算ｄ×Ｐを計算することができる。
【００７３】
図３は、第１の実施の形態のスカラー倍算ｄ×Ｐの説明図である。
ｉ＝１のときには、ｒ１×Ｐのスカラー倍算が計算され、ｉ＝２のときにはｒ２×Ｐのスカラー倍算が計算される。ｉ＝ｓのときには、ｒｓ×Ｐのスカラー倍算が計算される。また、ｉ＝ｓ＋１のときには、（ｄ−ｒ１−ｒ２−・・・−ｒｓ）×Ｐのスカラー倍算が計算される。そして、ｓ＋１個のスカラー倍算により得られる点の楕円加算ＥＣＡＤＤを計算することで、ｄ×Ｐのスカラー倍算を求めることができる。
【００７４】
この第１の実施の形態によれば、パラメータｓにより指定される個数の乱数を発生させ、発生させたｓ個の乱数を用いてスカラー倍算の計算をｓ＋１回行うことで、ＳＰＡ及びＤＰＡ等の電力解析による整数ｄの推定を困難にできる。また、パラメータｓを個々のデータに対するスカラー倍算を実行する毎に変化させることで、整数ｄの推定をさらに困難にできる。
【００７５】
次に、図４は、本発明の第２の実施の形態のスカラー倍算の演算プログラムを示す図である。
第２の実施の形態は、上述した第１の実施の形態において、ｓ＋１個のスカラー倍算の計算の中で少なくとも２個のスカラー倍算の計算をＤＰＡに対する耐性を有するアルゴリズムを用いて行うものである。他のスカラー倍算の計算はＤＰＡ耐性を持たないアルゴリズムを用いても、あるいはＤＰＡ耐性を有するアルゴリズを用いても良い。
【００７６】
図４のＳ４１〜Ｓ４６までの処理は、図２のＳ２１〜２６の処理と同じである。  次に、図４のステップＳ４８において、関数ｓｅｌｅｃｔ２（ｓ＋１）を用いて、ｓ＋１個のスカラー倍算の計算の中でＤＰＡ攻撃に対して安全なアルゴリズムを用いるものを決める。ここで、関数ｓｅｌｅｃｔ２（ｓ＋１）は、ｓ＋１個の配列の中の２個の配列ｔ〔〕の値を１にし、他の配列ｔ〔〕の値を０にする関数である。
【００７７】
次に、変数ｉをｉ＝１からｉ＝ｓ＋１まで順に変化させる（図４，Ｓ５０）。ｔ〔ｉ〕＝１か否かを判断する（図４，Ｓ５１）。
ｔ〔ｉ〕＝１のときには、次のステップＳ５２において、関数ｓｃａｌａｒ（ｒ〔ｉ〕，Ｐ）を用いて乱数ｒ〔ｉ〕と点Ｐのスカラー倍算を計算し、計算結果を変数ｄ〔ｉ〕に格納する。
【００７８】
こで、関数ｓｃａｌａｒ（ｒ〔ｉ〕，Ｐ）は、ＤＰＡ攻撃に対して耐性を有するアルゴリズム、例えば、図１３のアルゴリズム３，あるいは図１５のアルゴリズム５等を用いてスカラー倍算の計算を行う関数である。
【００７９】
ｔ〔ｉ〕＝０のときには、ステップ５３に進む。そして、次のステップＳ５４において、関数ｓｃａｌａｒ２（ｒ〔ｉ〕，Ｐ）を用いて乱数ｒ〔ｉ〕と点Ｐとのスカラー倍算を計算し、計算結果を変数ｄ〔ｉ〕に格納する。
【００８０】
関数ｓｃａｌａｒ２（ｒ〔ｉ〕，Ｐ）は、ＤＰＡ攻撃に対する耐性を要求しないアルゴリズムによりスカラー倍算の計算を行う関数である。もちろん、ＤＰＡ攻撃に対する耐性を有するアルゴリズムを用いて計算しても良い。
【００８１】
次に、スカラーの統合を行う。変数ｉをｉ＝１からｉ≦ｓ＋１まで変化させ（図４，Ｓ５７）、楕円加算ＥＣＡＤＤ（Ｑ，ｄ〔ｉ〕）の計算を行う（図４，Ｓ５８）。ステップＳ５７，Ｓ５８の処理をｉ＝１〜ｓ＋１まで実行した後、変数Ｑをスカラー倍算ｄ×Ｐの計算結果として出力する（図４，Ｓ６０）。
【００８２】
この第２の実施の形態は、上述した第１の実施の形態の効果に加え、ｓ＋１個のスカラー倍算の計算の内少なくとも２個のスカラー倍算の計算にＤＰＡ攻撃に対する耐性を有するアルゴリズムを用い、他のスカラー倍算にはＤＰＡ耐性を有しないアルゴリズムを用いることにより、全ての計算をＤＰＡ耐性を有するアルゴリズムを用いる場合に比べてスカラー倍算の全体の計算時間を短縮できるという効果が得られる。
【００８３】
次に、上述した第１と第２の実施の形態においてｒ＝２とした場合について説明する。
第１’の実施の形態は、第１の実施の形態のｓ＝２の場合に相当し、２個の乱数ｒ１，ｒ２を発生させ、スカラーｄをｒ１，ｒ２，ｄ−ｒ１−ｒ２に分割し、３個のスカラー倍算ｒ１×Ｐ，ｒ２×Ｐ，（ｄ−ｒ１−ｒ２）×Ｐを個々に計算するものである。
【００８４】
ｒ１×Ｐのスカラー倍算，ｒ２×Ｐのスカラー倍算，（ｄ−ｒ１−ｒ２）×Ｐのスカラー倍算が終了したなら、それらの演算により得られる３個の点の楕円加算ＥＣＡＤＤを計算する。３個の点の楕円加算は、以下の式で表せる。
【００８５】
ｒ１×Ｐ＋ｒ２×Ｐ＋（ｄ−ｒ１−ｒ２）×Ｐ＝（ｒ１＋ｒ２＋（ｄ−ｒ１−ｒ２））×Ｐ＝ｄ×Ｐ
従って、３個の点の楕円加算ＥＣＡＤＤを計算することによりスカラー倍算ｄ×Ｐを計算することができる。
【００８６】
また、この第１’の実施の形態において、ｒ１×Ｐ，ｒ２×Ｐ，（ｄ−ｒ１−ｒ２）×Ｐのスカラー倍算の計算において、ＤＰＡ攻撃に対する耐性を有するアルゴリズムを用いることで、スカラー倍算ｄ×Ｐの計算をＤＰＡ攻撃に対する耐性を保持して実行できる。
【００８７】
この第１’の実施の形態によれば、２個の乱数を用い、３個のスカラー倍算を個々に計算することで、電力解析により整数ｄが推定されるのを困難にできる。また、この場合、３個のスカラー倍算を計算するだけでよいので計算時間を短縮できる。
【００８８】
次に、第２’の実施の形態は、第２の実施の形態のｓ＝２の場合に相当し、３個のスカラー倍算ｒ１×Ｐ，ｒ２×Ｐ，（ｄ−ｒ１−ｒ２）×Ｐの内の２個のスカラー倍算をランダムに指定し、その２個のスカラー倍算の計算をＤＰＡ攻撃に対する耐性を有するアルゴリズムを用いて行い、残りの１個のスカラー倍算の計算をＤＰＡ攻撃に対する耐性を有しないアルゴリズムを用いて行うものである。
【００８９】
この第２’の実施の形態によれば、３個のスカラー倍算の計算の内の２個の計算をＤＰＡ攻撃に対する耐性を有するアルゴリズムを用い、他の１個の計算を耐性を有しないアルゴリズムを用いることで、スカラー倍算ｄ×Ｐの計算をＤＰＡ攻撃に対する耐性を保持したままで計算時間を短縮することができる。
【００９０】
次に、図５は、本発明の第３の実施の形態のスカラー倍算の演算プログラムを示す図である。
第３の実施の形態は、整数ｄとベースポイントＰの座標と、２個の乱数ｒ１，ｒ２を発生させ、スカラーｄをｒ１、ｒ２、ｄ−ｒ１−ｒ２に分割し、３個のスカラー倍算ｒ１×Ｐ，ｒ２×（ｒ１×Ｐ），（ｄ−ｒ１×ｒ２）×Ｐを個々に計算するものである。
【００９１】
関数ｒａｎｄｏｍ（）を用いて乱数を発生させ、発生させた乱数を変数ｒ〔１〕に格納する（図５，ステップ６２）。同様に、関数ｒａｎｄｏｍ（）を用いて乱数を発生させ、発生させた乱数を変数ｒ２に格納する（図５，Ｓ６３）。
【００９２】
次に、スカラー倍算の計算を行う。関数ｓｃａｌａｒ（ｒ〔１〕，Ｐ）を用いて乱数ｒ〔１〕と点Ｐとのスカラー倍算を計算し、計算結果を変数Ｐ〔１〕に格納する（図５，Ｓ６５）。
【００９３】
次に、上記の処理により求めた変数Ｐ〔１〕と、関数ｓｃａｌａｒ（ｒ〔２〕，Ｐ［１］）を用いて乱数ｒ〔２〕と点Ｐ〔１〕とのスカラー倍算ｒ［２］×（ｒ１×Ｐ）を計算し、計算結果を変数Ｐ〔２〕に格納する（図５，Ｓ６６）。
【００９４】
次に、乱数ｒ〔１〕とｒ〔２〕と関数ｓｃａｌａｒ（ｄ−ｒ［１］×ｒ〔２〕，Ｐ）を用いてスカラー（ｄ−ｒ〔１〕×ｒ〔２〕）と点Ｐとのスカラー倍算を計算し、計算結果を変数Ｐ〔３〕に格納する（図５，Ｓ６７）。
【００９５】
上記のステップＳ６５〜Ｓ６７の処理を実行することにより、ｒ〔１〕×Ｐのスカラー倍算と、ｒ〔２〕×ｒ［１］×Ｐのスカラー倍算と、（ｄ−ｒ〔１〕×ｒ〔２〕）×Ｐのスカラー倍算の計算が行われる。
【００９６】
次に、スカラーの統合を行う。変数Ｐ〔２〕により定まる点と変数Ｐ［３］により定まる点の楕円加算ＥＣＡＤＤ（Ｐ［２］，Ｐ〔３〕）を計算し、計算結果を変数Ｑに格納する（図５，Ｓ６９）。最後に、変数Ｑの座標をスカラー倍算ｄ×Ｐの計算結果として出力する（図５，Ｓ７０）。
【００９７】
上記のステップＳ６９の処理は、２個の点Ｐ［２］、Ｐ［３］の楕円加算ＥＣＡＤＤを計算する処理であり、ステップＳ６９の処理を終了した後の変数Ｑは、以下の式で表せる。
【００９８】
Ｑ＝ｒ〔１〕×ｒ〔２〕×Ｐ＋（ｄ−ｒ〔１〕×ｒ〔２〕）×Ｐ    （２）
上記の（２）式は、ｄ×Ｐと等しいので、上述した処理によりスカラー倍算ｄ×Ｐを計算することができる。
【００９９】
図６は、第３の実施の形態のスカラー倍算ｄ×Ｐの説明図である。
乱数をｒ１、ｒ２とすると、最初にｒ１×Ｐのスカラー倍算が計算され、次に、ｒ１×Ｐのスカラー倍算により得られた点とｒ２とのスカラー倍算、すなわち、ｒ１×ｒ２×Ｐのスカラー倍算が計算される。また、（ｄ−ｒ〔１〕×ｒ〔２〕）とＰとのスカラー倍算が計算される。
【０１００】
そして、上記のスカラー倍算により得られる点”ｒ１×ｒ２×Ｐ”と、点”（ｄ−ｒ１×ｒ２）×Ｐ”の楕円加算ＥＣＡＤＤを計算することで、ｄ×Ｐのスカラー倍算を計算することができる。
【０１０１】
この第３の実施の形態によれば、２個の乱数を用いて３個のスカラー倍算を計算することで、電力解析による整数ｄの推定を困難にし、楕円曲線暗号のＤＰＡ攻撃に対する耐性を向上させることができる。また、この第３の実施の形態は、スカラー倍算が２個の乱数ｒ［１］とｒ［２］の乗算になっているので、乱数の推定がより困難になる。また、乱数ｒ［１］とｒ［２］のビット長を整数ｄのビット長より短くすることができる。これにより、乱数と点Ｐとのスカラー倍算の計算時間を短くなるので、ｄ×Ｐのスカラー倍算の全体の計算時間を短縮できる。
【０１０２】
次に、図７は、本発明の第４の実施の形態のスカラー倍算の演算プログラムを示す図である。
第４の実施の形態は、第３の実施の形態の３個のスカラー倍算の計算の中で２個のスカラー倍算の計算にＤＰＡ攻撃に対する耐性を有するアルゴリズムを用いるものである。
【０１０３】
図７のステップＳ７１〜７３の処理は、図５の演算プログラムのステップＳ６１〜６３の処理と同じである。
ステップＳ７５において、関数ｓｅｌｅｃｔ２（ｓ＋１）を用いてｔ［ｉ］＝１となる配列を決める。この場合ｓ＝２であるので、３個の配列ｔ［ｉ］の中の任意の２個の配列の値が１、他が０となるように設定する。
【０１０４】
次に、スカラー倍算の計算を行う。ｒ［１］に対応する配列ｔ［１］が１のときには、関数ｓｃａｌａｒ（ｒ［１］，Ｐ）を用いて乱数ｒ［１］と点Ｐとのスカラー倍算ｒ１×Ｐを計算し、計算結果を変数Ｐ［１］に格納する。ｔ［１］が１でなければ（Ｓ７７，Ｓｅｌｓｅ）、関数ｓｃａｌａｒ２（ｒ［１］，Ｐ）を用いてスカラー倍算ｒ［１］×Ｐを計算し、計算結果を変数Ｐ［１］に格納する（図７，Ｓ７７）。
【０１０５】
次に、ｒ［２］に対応する配列ｔ［２］が１のときには、関数ｓｃａｌａｒ（ｒ［２］，Ｐ［１］）を用いて乱数ｒ［２］と点Ｐ［１］とのスカラー倍算ｒ［２］×Ｐ［１］＝ｒ［２］×（ｒ［１］×Ｐ）を計算し、計算結果を変数Ｐ［２］に格納する。ｔ［２］が１でなければ（Ｓ７８，Ｓｅｌｓｅ）、関数ｓｃａｌａｒ２（ｒ［２］，Ｐ）を用いてスカラー倍算ｒ［２］×（ｒ［１］×Ｐ）を計算し、計算結果を変数Ｐ［２］に格納する（図７，Ｓ７８）。
【０１０６】
次に、配列ｔ［３］が１のときには、関数ｓｃａｌａｒ（ｄ−ｒ［１］×ｒ［２］，Ｐ［２］）を用いてスカラー（ｄ−ｒ［１］×ｒ［２］）と点Ｐとのスカラー倍算を計算し、計算結果を変数Ｐ［３］に格納する。ｔ［３］が１でなければ（Ｓ７９，ｅｌｓｅ）、関数ｓｃａｌａｒ２（ｄ−ｒ［１］×ｒ［２］，Ｐ）を用いてスカラー倍算（ｄ−ｒ［１］×ｒ［２］）×Ｐを計算し、計算結果を変数Ｐ［３］に格納する（図７，Ｓ７９）。
【０１０７】
次に、点Ｐ［２］と点Ｐ［３］の楕円加算ＥＣＡＤＤ（Ｐ［２］，Ｐ［３］）を計算する（図７，Ｓ８１）。最後に、変数Ｑの座標をスカラー倍算ｄ×Ｐの計算結果として出力する（図７，Ｓ８２）。
【０１０８】
この第４の実施の形態によれば、上述した第３の実施の形態の効果に加え、３個のスカラー倍算の中の２個のスカラー倍算をＤＰＡ攻撃に対する耐性を有するアルゴリズムを用い、他の１個のスカラー倍算を耐性を有しないアルゴリズムを用いることで、ｄ×Ｐのスカラー倍算の全体の計算時間を短縮できる。さらに、１つのデータに対してスカラー倍算の計算が行われる毎に、どのスカラー倍算に対してＤＰＡ攻撃に対して耐性を有するアルゴリズムを用いるかを任意に決めているので電力解析がより困難になる。
【０１０９】
次に、図８は、本発明の第５の実施の形態のスカラー倍算の演算プログラムを示す図である。
第５の実施の形態は、２個の乱数ｒ１，ｒ２を発生させ、スカラーｄをｄ＝（（ｄ−ｒ１）×ｒ２＋（ｄ＋ｒ２）×ｒ１）／（ｒ１＋ｒ２）と分割し、４個のスカラー倍算（ｄ−ｒ１）×Ｐ、（ｄ＋ｒ２）×Ｐ、ｒ２×（（ｄ−ｒ１）×Ｐ）、ｒ１×（（ｄ＋ｒ２）×Ｐ）を個々に計算し、楕円加算の結果と１／（ｒ１＋ｒ２）とのスカラー倍算とを実行するものである。
【０１１０】
関数ｒａｎｄｏｍ（）を用いて乱数を発生させ、発生させた乱数を変数ｒ〔１〕に格納する（図８，ステップ９２）。同様に、関数ｒａｎｄｏｍ（）を用いて乱数を発生させ、発生させた乱数を変数ｒ［２］に格納する（図８，Ｓ９３）。
【０１１１】
次に、スカラー倍算の計算を行う。関数ｓｃａｌａｒ（ｒ〔１〕，Ｐ）を用いて乱数ｒ〔１〕と点Ｐとのスカラー倍算ｒ［１］×Ｐを計算し、計算結果を変数Ｐ〔１〕に格納する（図８，Ｓ９５）。
【０１１２】
次に、ステップＳ９５の処理により求めた点Ｐ〔１〕と、関数ｓｃａｌａｒ（ｄ＋ｒ〔２〕，Ｐ［１］）を用いて、スカラー倍算（ｄ＋ｒ〔２〕）×Ｐ［１］を計算し、計算結果を変数Ｐ〔２〕に格納する（図８，Ｓ９６）。
【０１１３】
次に、関数ｓｃａｌａｒ（ｒ〔２〕，Ｐ）を用いて乱数ｒ［２］と点Ｐとのスカラー倍算ｒ［２］×Ｐを計算し、計算結果を変数Ｐ〔３〕に格納する（図５，Ｓ９７）。
【０１１４】
次に、ステップＳ９７の処理により求めた点Ｐ［３］と、関数ｓｃａｌａｒ（ｄ−ｒ〔１〕，Ｐ［３］）を用いて、スカラー倍算（ｄ−ｒ［１］）×Ｐ［３］＝（ｄ−ｒ［１］）×ｒ［２］×Ｐを計算し、計算結果を変数Ｐ［４］に格納する（図８，Ｓ９８）。
【０１１５】
上記のステップＳ９５〜Ｓ９８の処理を実行することにより、ｒ〔１〕×Ｐのスカラー倍算と、（ｄ＋ｒ〔２〕）×ｒ［１］×Ｐのスカラー倍算と、ｒ［２］×Ｐのスカラー倍算と、（ｄ−ｒ〔１〕）×ｒ［２］×Ｐのスカラー倍算の計算が行われる。
【０１１６】
次に、スカラーの統合を行う。変数Ｐ［３］により定まる点と変数Ｐ［４］により定まる点の楕円加算ＥＣＡＤＤ（Ｐ［３］，Ｐ［４］）を計算し、計算結果を変数Ｑに格納する（図８，Ｓ１００）。すなわち、スカラー倍算（ｄ＋ｒ〔２〕）×ｒ［１］×Ｐにより得られる点Ｐ［２］と、スカラー倍算（ｄ−ｒ〔１〕）×ｒ［２］×Ｐにより得られる点Ｐ［４］の楕円加算ＥＣＡＤＤを計算する。
【０１１７】
次に、関数ｓｃａｌａｒ（１／（ｒ［１］＋ｒ［２］），Ｑ）を用い、スカラー（１／（ｒ［１］＋ｒ［２］）と変数Ｑのスカラー倍算を計算する（図８，Ｓ１０１）。最後に、変数Ｑの座標をスカラー倍算ｄ×Ｐの計算結果として出力する（図８，Ｓ１０２）。
【０１１８】
上記のステップＳ１０１の処理を終了した後の変数Ｑは、以下の式で表せる。
2004163687.tif 000004
上記の式（３）は、ｄ×Ｐと等しいので、上述した処理により変数Ｑとしてスカラー倍算ｄ×Ｐを計算することができる。
【０１１９】
図９は、第５の実施の形態のスカラー倍算ｄ×Ｐの説明図である。
乱数をｒ１、ｒ２とすると、最初にｒ１×Ｐのスカラー倍算が計算され、次に、ｄ＋ｒ２とｒ１×Ｐとのスカラー倍算、すなわち、ｒ１×（ｄ＋ｒ２）×Ｐのスカラー倍算が計算される。
【０１２０】
また、ｒ２×Ｐのスカラー倍算が計算され、計算により得られる点ｒ２×Ｐとスカラー（ｄ−ｒ１）とのスカラー倍算、すなわち、ｒ１×（ｄ−ｒ１）×Ｐのスカラー倍算が計算される。
【０１２１】
そして、上記のスカラー倍算により得られる点ｒ１×（ｄ＋ｒ２）×Ｐと、点ｒ１×（ｄ−ｒ１）×Ｐの楕円加算ＥＣＡＤＤ（ｒ１×（ｄ＋ｒ２）×Ｐ，ｒ１×（ｄ−ｒ１）×Ｐ）を計算することで、ｄ×Ｐのスカラー倍算を求めることができる。
【０１２２】
この第５の実施の形態によれば、２個の乱数を用いて、５個のスカラー倍算を個々に計算することで整数ｄの推定を困難にし、電力解析攻撃に対する耐性を向上させることができる。
【０１２３】
ここで、上述した実施の形態のスカラー倍算の演算プログラムを実行する楕円曲線暗号装置のハードウェア構成の一例を図１０を参照して説明する。楕円暗号装置は、例えば、パーソナルコンピュータ等の情報処理装置により実現できる。
【０１２４】
ＣＰＵ２３は、上述したスカラー倍算の演算プログラム等を実行する。ＲＯＭ２４にはＢＩＯＳ等の制御プログラムが格納される。ＲＡＭ（メモリ）２６は、演算に使用される各種のレジスタとして使用される。記憶装置２５には、楕円曲線暗号の演算プログラム等が格納される。
【０１２５】
記録媒体読み取り装置２７は、ＣＤＲＯＭ、ＤＶＤ、フレキシブルディスク、ＩＣカード等の可搬記録媒体２８の読み取り、あるいは書き込みを行う装置である。
【０１２６】
入力装置２９は、キーボード等のデータを入力する装置である。通信インタフェース３０は、インターネット等のネットワーク３１に接続するための装置であり、この装置を介してネットワーク上の情報提供者３２のサーバからプログラムをダウンロードすることができる。なお、ＣＰＵ２２，ＲＡＭ２４，外部記憶装置２５等はバス２２により接続されている。
【０１２７】
本発明は、楕円曲線暗号の暗号化及び解読を行う専用の装置に限らず、ＩＣカード、ＤＶＤ装置、携帯電話機、パーソナルコンピュータ等の種々の製品に適用できる。
【０１２８】
また、本発明は、実施の形態及で説明したスカラー倍算を計算するアルゴリズムに限らず他の楕円曲線暗号のアルゴリズムにも適用できる。
（付記１）  有限体上の楕円曲線Ｅと、楕円曲線上のベースポイントＰと、整数ｄを記憶する記憶手段と、
ｓ（ｓ≧２）個の乱数ｒ１〜ｒｓを発生する乱数発生手段と、
前記乱数発生手段により発生される乱数を用いて、ｒ１×Ｐ、ｒ２×Ｐ、・・・、ｒｓ×Ｐ、（ｄ−ｒ１−・・・−ｒｓ）×Ｐのスカラー倍算の演算をそれぞれ実行し、それらの演算により得られる点の楕円加算を実行してスカラー倍算ｄ×Ｐを計算する演算手段とを備える楕円曲線暗号装置。
（付記２）  有限体上の楕円曲線Ｅと、楕円曲線上のベースポイントＰと、整数ｄとを記憶する記憶手段と、
乱数ｒ１とｒ２を発生する乱数発生手段と、
前記乱数発生手段により発生される乱数を用いて、ｒ１×Ｐのスカラー倍算と、ｒ２×Ｐのスカラー倍算と、（ｄ−ｒ１−ｒ２）×Ｐのスカラー倍算の演算をそれぞれ実行し、それらのスカラー倍算により得られる点の楕円加算を実行してスカラー倍算ｄ×Ｐを計算する演算手段とを備える楕円曲線暗号装置。
（付記３）  有限体上の楕円曲線Ｅと、楕円曲線上のベースポイントＰと、整数ｄとを記憶する記憶手段と、
乱数ｒ１とｒ２を発生する乱数発生手段と、
前記乱数発生手段により発生される乱数を用いて、ｒ１×Ｐのスカラー倍算と、ｒ２×（ｒ１×Ｐ）のスカラー倍算と、（ｄ−ｒ１×ｒ２）×Ｐのスカラー倍算をそれぞれ実行し、ｒ２×（ｒ１×Ｐ）のスカラー倍算により得られる点Ｐ１と、（ｄ−ｒ１×ｒ２）×Ｐのスカラー倍算とにより得られる点Ｐ２との楕円加算によりスカラー倍算ｄ×Ｐを計算する演算手段とを備える楕円曲線暗号装置。
【０１２９】
（付記４）  有限体上の楕円曲線Ｅと、楕円曲線上のベースポイントＰと、整数ｄとを記憶する記憶手段と、
乱数ｒ１とｒ２を発生する乱数発生手段と、
前記乱数発生手段により発生される乱数を用いて、（ｄ−ｒ１）×Ｐのスカラー倍算と、（ｄ＋ｒ２）×Ｐのスカラー倍算と、ｒ２×（（ｄ−ｒ１）×Ｐ）のスカラー倍算と、ｒ１×（（ｄ＋ｒ２）×Ｐ）のスカラー倍算とをそれぞれ実行し、ｒ２×（（ｄ−ｒ１）×Ｐ）のスカラー倍算により得られる点Ｐ１と、ｒ１×（（ｄ＋ｒ２）×Ｐ）のスカラー倍算により得られる点Ｐ２との楕円加算と、楕円加算の演算結果と１／（ｒ１＋ｒ２）とのスカラー倍算を実行して、スカラー倍算ｄ×Ｐを計算する演算手段とを備える楕円曲線暗号装置。
（付記５）  有限体上の楕円曲線Ｅと、楕円曲線上のベースポイントＰと整数ｄを取得し、
ｓ個の乱数ｒ１〜ｒｓを発生させ、
ｓ個の乱数を用いて、ｒ１×Ｐ、ｒ２×Ｐ、・・・、ｒｓ×Ｐ、（ｄ−ｒ１−・・・−ｒｓ）×Ｐのスカラー倍算の演算をそれぞれ実行し、それらの演算により得られる点の楕円加算を実行してスカラー倍算ｄ×Ｐを計算する楕円曲線暗号プログラム。
（付記６）  付記２記載の楕円曲線暗号装置において、
前記演算手段は、３個のスカラー倍算を電力解析攻撃に対する耐性を有するアルゴリズムに基づいて個々に計算する。
【０１３０】
（付記７）  付記２記載の楕円曲線暗号装置において、
前記演算手段は、３個スカラー倍算の内の２個のスカラー倍算を、電力解析攻撃に対する耐性を有するアルゴリズムに基づいて個々に計算し、他のスカラー倍算を電力解析攻撃に対する耐性を有しないアルゴリズムに基づいて計算する。
【０１３１】
（付記８）  付記３記載の楕円曲線暗号装置において、
前記演算手段は、ｒ１×Ｐ，ｒ２×Ｐ及び（ｄ−ｒ１−ｒ２）×Ｐの３つのスカラー倍算の演算において、少なくとも２つのスカラー倍算の演算に電力解析攻撃に対する耐性を有するアルゴリズムを用いる。
【０１３２】
（付記９）  有限体上の楕円曲線Ｅと、楕円曲線上のベースポイントＰと、整数ｄとを記憶部に記憶させ、
乱数ｒ１とｒ２を発生させ、発生された乱数を用いて、演算部に、ｒ１×Ｐのスカラー倍算と、ｒ２×Ｐのスカラー倍算と、（ｄ−ｒ１−ｒ２）×Ｐのスカラー倍算の演算をそれぞれ実行させ、それらのスカラー倍算により得られる点の楕円加算を実行させてスカラー倍算ｄ×Ｐを計算する楕円曲線暗号プログラム。
【０１３３】
（付記１０）  有限体上の楕円曲線Ｅと、楕円曲線上のベースポイントＰと、整数ｄとを記憶部に記憶させ、
乱数ｒ１とｒ２を発生させ、発生された乱数を用いて、演算部に、ｒ１×Ｐのスカラー倍算と、ｒ２×（ｒ１×Ｐ）のスカラー倍算と、（ｄ−ｒ１×ｒ２）×Ｐのスカラー倍算をそれぞれ実行させ、ｒ２×（ｒ１×Ｐ）のスカラー倍算により得られる点Ｐ１と、（ｄ−ｒ１×ｒ２）×Ｐのスカラー倍算とにより得られる点Ｐ２との楕円加算によりスカラー倍算ｄ×Ｐを計算させる楕円曲線暗号プログラム。
【０１３４】
（付記１１）  有限体上の楕円曲線Ｅと、楕円曲線上のベースポイントＰと、整数ｄとを記憶部に記憶させ、
乱数ｒ１とｒ２を発生させ、発生された乱数を用いて、演算部に、（ｄ−ｒ１）×Ｐのスカラー倍算と、（ｄ＋ｒ２）×Ｐのスカラー倍算と、ｒ２×（（ｄ−ｒ１）×Ｐ）のスカラー倍算と、ｒ１×（（ｄ＋ｒ２）×Ｐ）のスカラー倍算とをそれぞれ実行させ、ｒ２×（（ｄ−ｒ１）×Ｐ）のスカラー倍算により得られる点Ｐ１と、ｒ１×（（ｄ＋ｒ２）×Ｐ）のスカラー倍算により得られる点Ｐ２との楕円加算と、楕円加算の演算結果と１／（ｒ１＋ｒ２）とのスカラー倍算を実行させて、スカラー倍算ｄ×Ｐを計算させる楕円曲線暗号プログラム。
【０１３５】
（付記１２）  有限体上の楕円曲線Ｅと、楕円曲線上のベースポイントＰと、整数ｄとを記憶部に記憶させ、
乱数ｒ１とｒ２を発生させ、発生された乱数を用いて、演算部に、ｒ１×Ｐのスカラー倍算と、ｒ２×（ｒ１×Ｐ）のスカラー倍算と、（ｄ−ｒ１×ｒ２）×Ｐのスカラー倍算をそれぞれ実行させ、ｒ２×（ｒ１×Ｐ）のスカラー倍算により得られる点Ｐ１と、（ｄ−ｒ１×ｒ２）×Ｐのスカラー倍算とにより得られる点Ｐ２との楕円加算によりスカラー倍算ｄ×Ｐを計算させる楕円曲線暗号演算方法。
【０１３６】
（付記１３）  有限体上の楕円曲線Ｅと、楕円曲線上のベースポイントＰと、整数ｄとを記憶部に記憶させ、
乱数ｒ１とｒ２を発生させ、発生された乱数を用いて、演算部に、（ｄ−ｒ１）×Ｐのスカラー倍算と、（ｄ＋ｒ２）×Ｐのスカラー倍算と、ｒ２×（（ｄ−ｒ１）×Ｐ）のスカラー倍算と、ｒ１×（（ｄ＋ｒ２）×Ｐ）のスカラー倍算とをそれぞれ実行させ、ｒ２×（（ｄ−ｒ１）×Ｐ）のスカラー倍算により得られる点Ｐ１と、ｒ１×（（ｄ＋ｒ２）×Ｐ）のスカラー倍算により得られる点Ｐ２との楕円加算と、楕円加算の演算結果と１／（ｒ１＋ｒ２）とのスカラー倍算を実行させてスカラー倍算ｄ×Ｐを計算させる楕円曲線暗号演算方法。
【０１３７】
【発明の効果】
本発明によれば、楕円曲線暗号におけるスカラー倍算の計算の電力解析攻撃に対する耐性を向上させることができる。
【図面の簡単な説明】
【図１】楕円曲線暗号装置の要部の構成を示す図である。
【図２】第１の実施の形態のスカラー倍算の演算プログラムを示す図である。
【図３】第１の実施の形態のスカラー倍算の説明図である。
【図４】第２の実施の形態のスカラー倍算の演算プログラムを示す図である。
【図５】第３の実施の形態のスカラー倍算の演算プログラムを示す図である。
【図６】第３の実施の形態のスカラー倍算の説明図である。
【図７】第４の実施の形態のスカラー倍算の演算プログラムを示す図である。
【図８】第５の実施の形態のスカラー倍算の演算プログラムを示す図である。
【図９】第５の実施の形態のスカラー倍算の説明図である。
【図１０】実施の形態の演算プログラムを実行するハードウェア環境を示す図である。
【図１１】アルゴリズム１の演算プログラムを示す図である。
【図１２】アルゴリズム２の演算プログラムを示す図である。
【図１３】アルゴリズム３の演算プログラムを示す図である。
【図１４】アルゴリズム４の演算プログラムを示す図である。
【図１５】アルゴリズム５の演算プログラムを示す図である。
【図１６】アルゴリズム３’の演算プログラムを示す図である。
【図１７】アルゴリズム５’の演算プログラムを示す図である。
【図１８】アルゴリズム６の演算プログラムを示す図である。
【図１９】アルゴリズム７の演算プログラムを示す図である。
【図２０】アルゴリズム８の演算プログラムを示す図である。
【図２１】アルゴリズム９の演算プログラムを示す図である。
【符号の説明】
１１    楕円曲線暗号装置
１２    演算部
１３    演算器
１４    レジスタ
１６    記憶部
【図１】
2004163687.tif 000005
【図２】
2004163687.tif 000006
【図３】
2004163687.tif 000007
【図４】
2004163687.tif 000008
【図５】
2004163687.tif 000009
【図６】
2004163687.tif 000010
【図７】
2004163687.tif 000011
【図８】
2004163687.tif 000012
【図９】
2004163687.tif 000013
【図１０】
2004163687.tif 000014
【図１１】
2004163687.tif 000015
【図１２】
2004163687.tif 000016
【図１３】
2004163687.tif 000017
【図１４】
2004163687.tif 000018
【図１５】
2004163687.tif 000019
【図１６】
2004163687.tif 000020
【図１７】
2004163687.tif 000021
【図１８】
2004163687.tif 000022
【図１９】
2004163687.tif 000023
【図２０】
2004163687.tif 000024
【図２１】
2004163687.tif 000025