楕円曲線暗号装置，楕円曲線暗号方法および楕円曲線暗号プログラム
楕円曲線暗号処理を行なう楕円曲線暗号装置である。 有限体ＧＦ（ｐ＾ｍ）上における楕円曲線上の点Ｐの座標（Ｘ：Ｙ：Ｚ）を座標（ｒ１×（Ｘ−ｓ１）：ｒ２×（Ｙ−ｓ２）：ｒ３×（Ｚ−ｓ３））に変換する座標変換部（２３）（ただし、ｐは素数、ｍは１以上の整数、ｒ１，ｒ２，ｒ３はそれぞれ１以上且つ（ｐ−１）以下の整数、ｓ１，ｓ２，ｓ３はそれぞれ０以上且つ（ｐ−１）以下の整数、又、符号＾はべき乗を表わす）と、この座標変換部（２３）によって変換された楕円曲線上の点のスカラー倍算を行なうスカラー倍算演算部（２２）とをそなえ、パラメーターｓ１，ｓ２，ｓ３のうち少なくとも１つが０以外の値を有するように構成することにより、楕円曲線暗号におけるスカラー倍算を、サイドチャネル攻撃に対する耐性をもって計算することができる。
【発明の詳細な説明】
【技術分野】
本発明は、楕円曲線暗号処理に関し、特に、楕円曲線暗号処理を行なうプロセッサにおける電力解析攻撃の防止に用いて好適な、楕円曲線暗号装置，楕円曲線暗号方法，楕円曲線暗号プログラムおよび同プログラムを記録したコンピュータ読取可能な記録媒体に関する。
【背景技術】
暗号方式には公開鍵暗号方式と共通鍵暗号方式とが含まれる。公開鍵暗号方式は、暗号化と復号化とで異なる鍵（キー）を用いる方式である。典型的な公開鍵暗号方式では、暗号化を行なうための鍵（公開鍵）を公開しておき、この公開鍵を用いて平文を暗号化して受信者に送信する。暗号文を復号化するための鍵（秘密鍵）は受信者のみが知る秘密情報として保持されており、受信者がこの秘密鍵を用いて暗号文を復号化することにより平文を得ることができる。
また、近年では、公開鍵暗号として楕円曲線暗号（Ｅｌｌｉｐｔｉｃ Ｃｕｒｖｅ Ｃｒｙｐｔｏｇｒａｐｈｙ）が注目を集めている。この楕円曲線暗号にはさまざまな種類の暗号化・復号化アルゴリズムが知られているが、ほとんどの暗号化・復号化処理でスカラー倍算という演算が用いられる。ここでスカラー倍算とは、楕円曲線上のベースポイントと呼ばれる点Ｐとスカラーと呼ばれる整数ｄとから、ｄ×Ｐ＝Ｐ＋Ｐ＋．．＋Ｐ（ｄ個の和）を計算することである。なお、楕円曲線暗号においては、ベースポイントＰとスカラー倍点ｄ×Ｐとから、スカラーｄ（秘密鍵）を求めることは困難であることが知られている。
ここで、楕円曲線暗号の例として、ＥＣＥＳ暗号方式を説明する。送信者Ａが秘密鍵ｓ（ｓは整数）を持ち、受信者Ｂが秘密鍵ｔ（ｔは整数）を持つ場合に、楕円曲線Ｅと、楕円曲線Ｅ上に設定されるベースポイントＰ（＝（ｘ，ｙ））と、公開鍵ｓ×Ｐ（送信者Ａの秘密鍵ｓとベースポイントＰとのスカラー倍点）と、公開鍵ｔ×Ｐ（受信者Ｂの秘密鍵ｔとベースポイントＰとのスカラー倍点）とがあらかじめ公開されている。
このとき送信者Ａは、自分の秘密鍵ｓと、受信者Ｂの公開鍵ｔ×Ｐとのスカラー倍算ｓ×（ｔ×Ｐ）を計算し、そのｘ座標のビット表現を求め、このビット表現とメッセージのビット表現との間でビット対応のＥＯＲ（Ｅｘｃｌｕｓｉｖｅ ＯＲ：排他的論理和）演算を施すことで、メッセージｍに対する暗号文Ｃを生成し、それを受信者Ｂに送信する。受信者Ｂは、自分の秘密鍵ｔと、送信者Ａの公開鍵ｓ×Ｐとのスカラー倍算ｔ×（ｓ×Ｐ）を計算し、そのｘ座標のビット表現を求める。そして、
ｓ×（ｔ×Ｐ）＝ｔ×（ｓ×Ｐ）
という関係式が成立することを考慮して、そのビット表現と暗号文Ｃのビット表現との間でビット対応のＥＯＲ演算を施すことで、暗号文Ｃを復号してメッセージｍを得る。このようにしてＥＣＥＳ暗号と呼ばれる暗号方式では、スカラー倍を用いて暗号化・復号化処理を行なう。
また、暗号の分野における技術の一つに、解読技術と呼ばれるものがある。解読技術とは秘密鍵等の秘密情報を暗号文等入手可能な情報から推定する技術のことであり、様々な手法が存在する。その中で最近注目されている技術に、サイドチャネル攻撃と呼ばれる手法がある。
サイドチャネル攻撃は、１９９８年にＰａｕｌ Ｋｏｃｈｅｒによって考案された手法であって、スマートカード等に搭載された暗号プロセッサに様々な入力データを与えた時のサイドチャネル情報（消費電力データ・消費時間データ・電磁波データ等）を収集・解析することにより、暗号プロセッサ内部の鍵情報を推定する手法である。サイドチャネル攻撃を用いると、公開鍵暗号、共通鍵暗号共に暗号プロセッサから秘密鍵を推定できる可能性があることが指摘されている。
このサイドチャネル攻撃の中で、電力解析攻撃は強力な攻撃法である。この電力解析攻撃として、単純電力解析（ＳＰＡ；Ｓｉｎｇｌｅ Ｐｏｗｅｒ Ａｎａｌｙｓｉｓ）と、差分電力解析（ＤＰＡ；Ｄｉｆｆｅｒｅｎｔｉａｌ Ｐｏｗｅｒ Ａｎａｌｙｓｉｓ）との２種類の手法が知られている。ＳＰＡは暗号プロセッサにおける単一の電力消費データの特徴から秘密鍵の推定を行なう方式であり、ＤＰＡは多数の電力消費データの差分を解析することで秘密鍵の推定を行なう方式である。
そして、楕円曲線暗号に対しても、上述したＳＰＡやＤＰＡを適用することが可能である。この場合、スカラー倍算が攻撃対象となることが多い。詳細な推定法については、Ｊｅａｎ−Ｓｅｂａｓｔｅｉｎ Ｃｏｒｏｎ“Ｒｅｓｉｓｔａｎｃｅ ａｇａｉｎｓｔ Ｄｉｆｆｅｒｅｎｔｉａｌ Ｐｏｗｅｒ Ａｎａｌｙｓｉｓ ｆｏｒ Ｅｌｌｉｐｔｉｃ Ｃｕｒｖｅ Ｃｒｙｔｏｓｙｓｔｅｍｓ”，Ｃｒｙｐｔｏｇｒａｐｈｉｃ Ｈａｒｄｗａｒｅ ａｎｄ Ｅｍｂｅｄｄｅｄ Ｓｙｓｔｅｍｓ １９９９（ＣＨＥＳ１９９９），Ｌｅｃｔｕｒｅ Ｎｏｔｅｓ ｉｎ Ｃｏｍｐｕｔｅｒ Ｓｃｉｅｎｃｅ ｖｏｌ．１７１７，Ｓｐｒｉｎｇｅｒ−Ｖｅｒｌａｇ，ｐｐ．２９２−３０２，１９９９（以下、文献Ｃｏｒｏｎ９９という）等の文献にて述べられている。
さて、楕円曲線暗号の暗号化・復号化処理では、楕円曲線上の点のスカラー倍算が中心となる。スカラー倍算ｄ×Ｐの最も単純な実現手法としてバイナリ法（Ｂｉｎａｒｙ ｍｅｔｈｏｄ）があり、最上位ビット（Ｍｏｓｔ Ｓｉｇｎｉｆｉｃａｎｔ Ｂｉｔ；ＭＳＢ）から計算する方法（バイナリ法（ＭＳＢ））と、最下位ビット（Ｌｅａｓｔ Ｓｉｇｎｉｆｉｃａｎｔ Ｂｉｔ；ＬＳＢ）から計算する方法（バイナリ法（ＬＳＢ））とが知られている。
ここで、バイナリ法（ＭＳＢ）のアルゴリズム例を（１）Ａｌｇｏｒｉｔｈｍ １に、又、バイナリ法（ＬＳＢ）のアルゴリズム例を（２）Ａｌｇｏｒｉｔｈｍ ２に示す。なお、以下、特に断りの無い限り、小文字（ｄ等）はスカラー値を表わし、大文字（Ｐ，Ｔ等）は楕円曲線上の点を表わすものとする。又、楕円加算をＥＣＡＤＤ、楕円２倍算をＥＣＤＢＬと表わす。更に、符号“＾”はべき乗算を表わすものとし、“（”と“）２”とによって囲まれた数列は２進数で表現された数字を表わす。又、“Ｓ１：”等のように、Ｓを付した数字はアルゴリズムを表わすプログラム例におけるステップ数を示すものとする。
ここで、Ｔは一時変数、ｄはｎビットのスカラー値で、ｄ［ｉ］はｄの下位ｉ番目のビットの値である。
例えばｄ＝２１＝２＾４＋２＾２＋２＾０＝（１０１０１）２についてスカラー倍算ｄ×Ｐを計算する場合を考える。ステップＳ１においては変数Ｔに点Ｐが設定され、その次のステップＳ２〜Ｓ７において、ｉ＝３，２，１，０に対応する各処理が行なわれる。
ｉ＝３のとき、ステップＳ３では変数ＴにＥＣＤＢＬ（Ｔ）が設定され、処理後の変数Ｔの値は２×Ｐとなる。また、ｉ＝３のときには、ｄ［ｉ］＝ｄ［３］＝０なので、ステップＳ４〜Ｓ６はスキップされる。
ｉ＝２のとき、ステップＳ３では変数ＴにＥＣＤＢＬ（Ｔ）が設定され、処理後の変数Ｔの値は４×Ｐとなる。又、ｉ＝２のときには、ｄ［ｉ］＝ｄ［２］＝１なので、ステップＳ５では変数ＴにＥＣＤＢＬ（Ｔ，Ｐ）が設定され、処理後の変数Ｔの値は５×Ｐとなる。
ｉ＝１のとき、ステップＳ３では変数ＴにＥＣＤＢＬ（Ｔ）が設定され、処理後の変数Ｔの値は１０×Ｐとなる。又、ｉ＝１のときには、ｄ［ｉ］＝ｄ［１］＝０なので、ステップＳ４〜Ｓ６はスキップされる。
ｉ＝０とき、ステップＳ３では変数ＴにＥＣＤＢＬ（Ｔ）が設定され、処理後の変数Ｔの値は２０×Ｐとなる。又、ｉ＝０のときには、ｄ［ｉ］＝ｄ［０］＝１なので、ステップＳ５では変数ＴにＥＣＤＢＬ（Ｔ，Ｐ）が設定され、処理後の変数Ｔの値は２１×Ｐとなる。
以上でステップＳ２〜Ｓ７の処理が終了し、最後のステップＳ８で変数Ｔの値２１×Ｐが出力される。このようにバイナリ法（ＭＳＢ）では、スカラ値の最上位ビットから処理が行なわれるのである。
ここでＴ［０］，Ｔ［１］はいずれも一時変数、ｄはｎビットのスカラー値で、ｄ［ｉ］はｄの下位ｉ番目のビットの値である。
例えばｄ＝２１＝２＾４＋２＾２＋２＾０＝（１０１０１）２についてスカラー倍算ｄ×Ｐを計算する場合を考える。ステップＳ１においては変数Ｔ［１］に点Ｐが、又、変数Ｔ［０］に点Ｏが設定される。次のステップＳ３〜Ｓ８においてｉ＝０，１，２，３，４に対応する各処理が行なわれる。
ｉ＝０のときには、ｄ［ｉ］＝ｄ［０］＝１なので、ステップＳ５では変数Ｔ［０］にＥＣＡＤＤ（Ｔ［０］，Ｔ［１］）が設定され、処理後の変数Ｔ［０］の値はＰとなる。ステップＳ７では変数Ｔ［１］にＥＣＤＢＬ（Ｔ［１］）が設定され、処理後の変数Ｔ［１］の値は２×Ｐとなる。
ｉ＝１のときには、ｄ［ｉ］＝ｄ［１］＝０なので、ステップＳ４〜Ｓ６はスキップされる。ステップＳ７では変数Ｔ［１］にＥＣＤＢＬ（Ｔ［１］）が設定され、処理後の変数Ｔ［１］の値は４×Ｐとなる。
ｉ＝２のときには、ｄ［ｉ］＝ｄ［２］＝１なので、ステップＳ５では変数Ｔ［０］にＥＣＡＤＤ（Ｔ［０］，Ｔ［１］）が設定され、処理後の変数Ｔ［０］の値は５×Ｐとなる。ステップＳ７では変数Ｔ［１］にＥＣＤＢＬ（Ｔ［１］）が設定され、処理後の変数Ｔ［１］の値は８×Ｐとなる。
ｉ＝３のときには、ｄ［ｉ］＝ｄ［３］＝０なので、ステップＳ４〜Ｓ６はスキップされる。ステップＳ７では変数Ｔ［１］にＥＣＤＢＬ（Ｔ［１］）が設定され、処理後の変数Ｔ［１］の値は１６×Ｐとなる。
ｉ＝４のときには、ｄ［ｉ］＝ｄ［０］＝１なので、ステップＳ５では変数Ｔ［０］にＥＣＡＤＤ（Ｔ［０］，Ｔ［１］）が設定され、処理後の変数Ｔ［０］の値は２１×Ｐとなる。ステップＳ７では変数Ｔ［１］にＥＣＤＢＬ（Ｔ［１］）が設定され、処理後の変数Ｔ［１］の値は３２×Ｐとなる。
以上でステップＳ３〜Ｓ８の処理が終了し、最後のステップＳ９で変数Ｔ［０］の値２１×Ｐが出力される。このようにバイナリ法（ＬＳＢ）では、スカラ値の最下位ビットから処理が行なわれるのである。
さて、上述したＡｌｇｏｒｉｔｈｍ １およびＡｌｇｏｒｉｔｈｍ ２を点のスカラー倍算に使用した場合には、いずれも※印を付したステップＳ５の処理は、ｄのビット値ｄ［ｉ］に応じて実行されたりされなかったりする。ＳＰＡではこの性質を利用して秘密鍵ｄを解析する。多くの実験から、ＥＣＤＢＬとＥＣＡＤＤの電力波形は特徴的で容易に区別可能であることが知られている。従って、プロセッサにおけるＡｌｇｏｒｉｔｈｍ １およびＡｌｇｏｒｉｔｈｍ ２の演算において発生する電力波形を測定することによって、その波形からＥＣＤＢＬとＥＣＡＤＤの演算の順序と回数がわかり、秘密鍵ｄを解析して求めることができる。
このＳＰＡへの対策として、アド・アンド・ダブル・オールウェイズ（ａｄｄ−ａｎｄ−ｄｏｕｂｌｅ−ａｌｗａｙｓ）と呼ばれる、加算と２倍算とを常に行なう方法が文献Ｃｏｒｏｎ９９で提案されている。この方法では、常にＥＣＤＢＬ演算とＥＣＡＤＤ演算とが交互に行なわれるのでＳＰＡに対して安全である。以下に、先述したＡｌｇｏｒｉｔｈｍ １およびＡｌｇｏｒｉｔｈｍ ２に対してアド・アンド・ダブル・オールウェイズを施したアルゴリズム例をＡｌｇｏｒｉｔｈｍ ３およびＡｌｇｏｒｉｔｈｍ ４として示す。
ここで、Ｔ［０］，Ｔ［１］はいずれも一時変数、ｄはｎビットのスカラー値で、ｄ［ｉ］はｄの下位ｉビット目の値である。
ここで、Ｔ［０］，Ｔ［１］，Ｔ［２］はいずれも一時変数、ｄはｎビットのスカラー値で、ｄ［ｉ］はｄの下位ｉビット目の値である。
上述したＡｌｇｏｒｉｔｈｍ ３およびＡｌｇｏｒｉｔｈｍ ４を用いることによりＳＰＡを防止することができる。又、同様の効果をもつ方式として、モンゴメリ・ラダー（Ｍｏｎｔｇｏｍｅｒｙ−Ｌａｄｄｅｒ）を用いた方法が、Ｔ．Ｉｚｕ，ａｎｄ Ｔ．Ｔａｋａｇｉ，”Ａ Ｆａｓｔ Ｐａｒａｌｌｅｌ Ｅｌｌｉｐｔｉｃ Ｃｕｒｖｅ Ｍｕｌｔｉｐｌｉｃａｔｉｏｎ Ｒｅｓｉｓｔａｎｔ ａｇａｉｎｓｔ Ｓｉｄｅ Ｃｈａｎｎｅｌ Ａｔｔａｃｋｓ”，Ｐｕｂｌｉｃ−Ｋｅｙ Ｃｒｙｐｔｏｇｒａｐｈｙ ２００２（ＰＫＣ２００２），Ｌｅｃｔｕｒｅ Ｎｏｔｅｓ ｉｎ Ｃｏｍｐｕｔｅｒ Ｓｃｉｅｎｃｅ ｖｏｌ．２２７４，ｐｐ．２８０−２９６，Ｓｐｒｉｎｇｅｒ−Ｖｅｒｌａｇ，２００２．（以下、文献Ｉｚｕ−Ｔａｋａｇｉ０２という）にて提案されている。
スカラー倍算ｄ×Ｐにおいて、モンゴメリ・ラダーでは常にＥＣＤＢＬとＥＣＡＤＤを交互に計算するので、ＳＰＡに対して安全である。モンゴメリ・ラダーのアルゴリズム例をＡｌｇｏｒｉｔｈｍ ５に示す。
ここでＴ［０］，Ｔ［１］，Ｔ［２］はいずれも一時変数、ｄはｎビットのスカラー値で、ｄ［ｉ］はｄの下位ｉビット目の値である。
上述したＡｌｇｏｒｉｔｈｍ ３〜Ａｌｇｏｒｉｔｈｍ ５を用いることによりＳＰＡを防止することができるが、文献Ｃｏｒｏｎ９９にはこれらのアルゴリズムに対するＤＰＡについても述べられており、Ａｌｇｏｒｉｔｈｍ ３〜Ａｌｇｏｒｉｔｈｍ ５ではＤＰＡで秘密鍵を解析して求めることができることが示されている。そして、文献Ｃｏｒｏｎ９９には、ランダム化射影座標（Ｒａｎｄｏｍｉｚｅｄ Ｐｒｏｊｅｃｔｉｖｅ Ｃｏｏｒｄｉｎａｔｅｓ；ＲＰＣ）と呼ばれる、乱数を使用した楕円曲線上の点の表現を導入することによって、Ａｌｇｏｒｉｔｈｍ ３〜Ａｌｇｏｒｉｔｈｍ ５に対するＤＰＡへの各対策が提案されている。
以下に、Ａｌｇｏｒｉｔｈｍ ３に対してＲＰＣを施したアルゴリズム例をＡｌｇｏｒｉｔｈｍ ３′として示す他、Ａｌｇｏｒｉｔｈｍ ４に対してＲＰＣを施したアルゴリズム例をＡｌｇｏｒｉｔｈｍ ４′として、又、Ａｌｇｏｒｉｔｈｍ ５に対してＲＰＣを施したものをＡｌｇｏｒｉｔｈｍ ５′としてそれぞれ示す。なお、以下、ＲＰＣで表現された楕円曲線上の点をダッシュ（′もしくは’）付の変数で示す。
ここで、Ｔ’［０］，Ｔ’［１］，Ｔ’［２］はいずれも一時変数、ｄはｎビットのスカラー値で、ｄ［ｉ］はｄの下位ｉビット目の値である。又、ｉｎｖＲＰＣはＲＰＣ表現からの逆変換を示す。
ここで、Ｔ’［０］，Ｔ’［１］，Ｔ’［２］はいずれも一時変数、ｄはｎビットのスカラー値で、ｄ［ｉ］はｄの下位ｉビット目の値である。又、ｉｎｖＲＰＣはＲＰＣ表現からの逆変換を示す。
ここで、Ｔ’［０］，Ｔ’［１］，Ｔ’［２］はいずれも一時変数、ｄはｎビットのスカラー値で、ｄ［ｉ］はｄの下位ｉビット目の値である。又、ｉｎｖＲＰＣはＲＰＣ表現からの逆変換を示す。
また、ＤＰＡに対する対策として、ＲＰＣと同様の効果を持つ方式として、Ｍ．Ｊｏｙｅ，ａｎｄ Ｃ．Ｔｙｍｅｎ，“Ｐｒｏｔｅｃｔｉｏｎｓ ａｇａｉｎｓｔ ｄｉｆｆｅｒｅｎｔｉａｌ ａｎａｌｙｓｉｓ ｆｏｒ ｅｌｌｉｐｔｉｃ ｃｕｒｖｅ ｃｒｙｐｔｏｇｒａｐｈｙ”，Ｃｒｙｐｔｏｇｒａｐｈｉｃ Ｈａｒｄｗａｒｅ ａｎｄ Ｅｍｂｅｄｄｅｄ Ｓｙｓｔｅｍｓ ２００１（ＣＨＥＳ ２００１），Ｌｅｃｔｕｒｅ Ｎｏｔｅｓ ｉｎ Ｃｏｍｐｕｔｅｒ Ｓｃｉｅｎｃｅ ｖｏｌ．２１６２，ｐｐ．３７７−３９０，Ｓｐｒｉｎｇｅｒ−Ｖｅｒｌａｇ，２００１．（文献Ｊｏｙｅ−Ｔｙｍｅｎ０１という）で提案されたランダム化曲線（Ｒａｎｄｏｍｉｚｅｄ Ｃｕｒｖｅ；ＲＣ）法がある。
ＲＣは、ＲＰＣと同様に乱数を用いた点の表現を用いた点の表現を用いた点の表現を用いることによるＤＰＡ対策法である。ＲＣの適用方法はＲＰＣと同様である。Ａｌｇｏｒｉｔｈｍ ３に対してＲＣを施したアルゴリズム例をＡｌｇｏｒｉｔｈｍ ３″として示し、同様に、Ａｌｇｏｒｉｔｈｍ ４に対してＲＣを施したアルゴリズム例をＡｌｇｏｒｉｔｈｍ ４″，Ａｌｇｏｒｉｔｈｍ ５に対してＲＣを施したアルゴリズム例をＡｌｇｏｒｉｔｈｍ ５″としてそれぞれ示す。なお、以下、ＲＣで表現された楕円曲線上の点はダブルダッシュ（″もしくは”）付の変数で示す。
ここで、Ｔ”［０］，Ｔ”［１］，Ｔ”［２］はいずれも一時変数、ｄはｎビットのスカラー値で、ｄ［ｉ］はｄの下位ｉビット目の値である。又、ｉｎｖＲＣはＲＣ表現からの逆変換を示す。
ここで、Ｔ”［０］，Ｔ”［１］，Ｔ”［２］はいずれも一時変数、ｄはｎビットのスカラー値で、ｄ［ｉ］はｄの下位ｉビット目の値である。又、ｉｎｖＲＣはＲＣ表現からの逆変換を示す。
ここで、Ｔ”［０］，Ｔ”［１］，Ｔ”［２］はいずれも一時変数、ｄはｎビットのスカラー値で、ｄ［ｉ］はｄの下位ｉビット目の値である。又、ｉｎｖＲＣはＲＣ表現からの逆変換を示す。
また、スカラー倍算ｄ×Ｐの実現手法としては、前述したバイナリ法（Ａｌｇｏｒｉｔｈｍ １，２）やモンゴメリ・ラダー（Ａｌｇｏｒｉｔｈｍ ５）の他に、ウィンドウ法（ｗｉｎｄｏｗ ｍｅｔｈｏｄ）と呼ばれる方法もある。例えば、幅４ビットのウィンドウ法は、初期処理としてＰの０〜１５倍を計算し、その結果をテーブルとして持っておき、次にスカラー値を４ビット単位（ウィンドウ）に分割することにより、スカラー倍算を処理する。以下に、Ａｌｇｏｒｉｔｈｍ ６としてウィンドウ法（幅４ビット）のアルゴリズム例を示す。
ここで、ｄはｎビットのスカラー値で、ｎは４の倍数と仮定する。又、ｄ［ｉ，ｉ−３］はｄの下位ｉビット目から（ｉ−３）ビットまでの４ビット値とする。Ｗ［ｉ］はウィンドウ法で使用するテーブルである。
例えば、ｄ＝２１＝２＾４＋２＾２＋２＾０＝（１０１０１）２＝（０００１ ０１０１）２に対するスカラー倍算を考える。このときｄは５ビットで４の倍数ではないので、便宜上、その上位３ビットに０を挿入して８ビットとみなす。このときｎ＝８である。先ず、初期値としてステップＳ０１でＷ［０］＝０が、ステップＳ０２でＷ［１］＝Ｐが設定される。次にｉ＝２，３，．．．，１５に対し、ステップＳ０３〜Ｓ０５が実行される。各ｉに対し、ステップＳ０４でＷ［ｉ］＝ＥＣＡＤＤ（Ｗ［ｉ−１］，Ｐ）が設定される。このとき、Ｗ［ｉ］に設定されている値はｉ×Ｐとなっている。ステップＳ０３〜Ｓ０５の処理の終了後、ステップＳ０６で変数ＴにＷ［ｄ［ｎ−１，ｎ−４］］＝Ｗ［ｄ［７，４］］＝Ｗ［ｄ［０００１］］＝１×Ｐが設定される。
次に、ｉ＝３に対してステップＳ０７〜Ｓ１３が処理される。ステップＳ０８ではＴ：＝ＥＣＤＢＬ（Ｔ）が処理され、変数Ｔには２×Ｐが登録される。ステップＳ０９ではＴ：＝ＥＣＤＢＬ（Ｔ）が処理され、変数Ｔには４×Ｐが登録される。ステップＳ１０ではＴ：＝ＥＣＤＢＬ（Ｔ）が処理され、変数Ｔには８×Ｐが登録される。ステップＳ１１ではＴ：＝ＥＣＤＢＬ（Ｔ）が処理され、変数Ｔには１６×Ｐが登録される。ステップＳ１２ではＴ：＝ＥＣＡＤＤ（Ｔ，Ｗ［ｄ［ｉ，ｉ−３］］）＝ＥＣＡＤＤ（Ｔ，Ｗ［０１０１］）＝ＥＣＡＤＤ（１６×Ｐ，５×Ｐ）＝２１×Ｐが処理され、変数Ｔに２１×Ｐが登録される。
以上でステップＳ０７〜Ｓ１３の処理が終了する。最後にステップＳ１４において変数Ｔの値２１×Ｐが出力される。このようにウィンドウ法では、あらかじめ作成したテーブルを用いてスカラー倍算ｄ×Ｐを計算するのである。
さて、点のスカラー倍算にＡｌｇｏｒｉｔｈｍ ６（ウィンドウ法）を使用する場合には、ｄのビット値に応じて行なわれたり行なわれなかったりするような処理が無いので、バイナリ法と比較して一般にＳＰＡに対して安全であるといわれている。しかし、ウィンドウ法は、バイナリ法と同様に、ＤＰＡに対しては安全ではなく、文献Ｃｏｒｏｎ９９に開示された手法で解析可能であるが、かかるＤＰＡに対しては、バイナリ法やモンゴメリ・ラダーと同様に、ＲＰＣやＲＣが有効であることが知られている。以下に、Ａｌｇｏｒｉｔｈｍ ６に対してＲＰＣを施したアルゴリズム例をＡｌｇｏｒｉｔｈｍ ６′に、又、Ａｌｇｏｒｉｔｈｍ ６にＲＣを施したアルゴリズム例をＡｌｇｏｒｉｔｈｍ ６″に示す。
ここで、ｄはｎビットのスカラー値で、ｎは４の倍数と仮定する。またｄ［ｉ，ｉ−３］はｄの下位ｉビット目から（ｉ−３）ビットまでの４ビット値とする。Ｔ′は一時変数、Ｗ’［ｉ］はウィンドウ法で使用するテーブル、ｉｎｖＲＰＣはＲＰＣ表現からの逆変換を示す。
ここで、ｄはｎビットのスカラー値で、ｎは４の倍数と仮定する。またｄ［ｉ，ｉ−３］はｄの下位ｉビット目から（ｉ−３）ビットまでの４ビット値とする。Ｔ″は一時変数、Ｗ”［ｉ］はウィンドウ法で使用するテーブル、ｉｎｖＲＣはＲＣ表現からの逆変換を示す。
さて、ＳＰＡとＤＰＡとの双方に対しては、従来、前述したＡｌｇｏｒｉｔｈｍ ３′〜６′やＡｌｇｏｒｉｔｈｍ ３″〜６″を用いれば安全であるとされていた。しかしながら、最近、Ｌ．Ｇｏｕｂｉｎ，“Ａ Ｒｅｆｉｎｅｄ Ｐｏｗｅｒ−Ａｎａｌｙｓｉｓ Ａｔｔａｃｋ ｏｎ Ｅｌｌｉｐｔｉｃ Ｃｕｒｖｅ Ｃｒｙｐｔｏｓｙｓｔｅｍ”，Ｐｕｂｌｉｃ−Ｋｅｙ Ｃｒｙｐｔｏｇｒａｐｈｙ ２００３（ＰＫＣ２００３），Ｌｅｃｔｕｒｅ Ｎｏｔｅｓ ｉｎ Ｃｏｍｐｕｔｅｒ Ｓｃｉｅｎｃｅ ｖｏｌ．２５６７，Ｓｐｒｉｎｇｅｒ−Ｖｅｒｌａｇ，ｐｐ．１９９−２１０，２００３．（文献Ｇｏｕｂｉｎ０３という）において、これらを解析する手法が開示された。
楕円曲線上の点のうち、ｘ座標またはｙ座標が０であるような点を特殊点という。スカラー倍算の途中に特殊点が出現した場合には、ＳＰＡやＤＰＡによって、このような点が中間値として現れたことを容易に検出することができる。文献Ｇｏｕｂｉｎ０３に開示された解析手法においては、あるビットｄ［ｉ］に対応する計算の終了時に特殊点が現れるようなベースポイントを人工的に生成し、実際に特殊点が検出されるかどうかによってｄ［ｉ］の値を推定するようになっている。以下、便宜上、この文献Ｇｏｕｂｉｎ０３の解析手法を用いた攻撃を特殊点攻撃と呼ぶ。
この特殊点攻撃に対し、バイナリ法やモンゴメリ・ラダーは安全でない。又、ＲＰＣやＲＣを用いたとしても、座標値が０になるという性質は保持されてしまうので、Ａｌｇｏｒｉｔｈｍ ３′〜６′やＡｌｇｏｒｉｔｈｍ ３″〜６″も特殊点攻撃に対して安全であるとはいえない。
なお、Ａｌｇｏｒｉｔｈｍ ３〜６についてのＤＰＡに対する他の対策として、Ｃ．Ｃｌａｖｉｅｒ，ａｎｄ Ｍ．Ｊｏｙｅ，”Ｕｎｉｖｅｒｓａｌ ｅｘｐｏｎｅｎｔｉａｔｉｏｎ ａｌｇｏｒｉｔｈｍ −−Ａ ｆｉｒｓｔ ｓｔｅｐ ｔｏｗａｒｄｓ ｐｒｏｖａｂｌｅ ＳＰＡ−ｒｅｓｉｓｔａｎｃｅ−−”，Ｃｒｙｐｔｏｇｒａｐｈｉｃ Ｈａｒｄｗａｒｅ ａｎｄ Ｅｍｂｅｄｄｅｄ Ｓｙｓｔｅｍｓ ２００１（ＣＨＥＳ２００１），Ｌｅｃｔｕｒｅ Ｎｏｔｅｓ ｉｎ Ｃｏｍｐｕｔｅｒ Ｓｃｉｅｎｃｅ ｖｏｌ．２１６２，Ｓｐｒｉｎｇｅｒ−Ｖｅｒｌａｇ，ｐｐ．３００−３０８，２００１．（文献Ｃｌａｖｉｅｒ−Ｊｏｙｅ０１という）にて提案されているエクスポーネント・スプリッティング（ｅｘｐｏｎｅｎｔ−ｓｐｌｉｔｔｉｎｇ；ＥＳ）がある。このＥＳはスカラー値をランダムに変化させる手法であって、乱数ｒによって、スカラーｄをｄ＝ｒ＋（ｄ−ｒ）に分割して、２つのスカラー倍算ｒ×Ｐと（ｄ−ｒ）×Ｐとを別々に計算し、
ｒ×Ｐ＋（ｄ−ｒ）×Ｐ＝ｄ×Ｐ
が成り立つという性質を利用して、２つのスカラー倍算の結果を足しあわせることでｄ×Ｐを計算するものである。
ここで、２つのスカラー倍算ｒ×Ｐおよび（ｄ−ｒ）×Ｐには、他のＳＰＡ／ＤＰＡに耐性を有するアルゴリズムを用いる。特殊点攻撃に対しては、スカラー値がランダムに変化するために防御が可能となる。ＥＳのアルゴリズム例をＡｌｇｏｒｉｔｈｍ ７に示す。
ここでｒａｎｄｏｍ（）はｎビットの乱数を生成する関数である。又、ｓｃａｌａｒ（ｄ，Ｐ）はスカラー倍算ｄ×Ｐを計算する関数であって、具体的には、前述したＡｌｇｏｒｉｔｈｍ ３′〜６′やＡｌｇｏｒｉｔｈｍ ３″〜６″等を用いて計算される。また変数ｒ，Ｔ，Ｔ１，Ｔ２はいずれも一時変数である。
ＥＳは、ＳＰＡ，ＤＰＡおよび特殊点攻撃に対して安全といえるが、ＥＳで使用するスカラー倍算はその手法単独でＳＰＡ対策，ＤＰＡ対策であるので、既にＳＰＡ対策とＤＰＡ対策済のＡｌｇｏｒｉｔｈｍ ３′〜６′やＡｌｇｏｒｉｔｈｍ ３″〜６″に適用するには無駄が多い。特に、これらの手法を適用すると、楕円曲線上の点の加算および２倍算を、適用前と比較して余分に処理しなければならず、処理オーバーヘッドが大きくなる欠点がある。
本発明は、このような課題に鑑み創案されたもので、特定点攻撃に対して秘密情報の推定を困難にし、暗号処理の安全性を高めることが可能な楕円曲線暗号装置，楕円曲線暗号方法，楕円曲線暗号プログラムおよび同プログラムを記録したコンピュータ読取可能な記録媒体を提供することを目的とする。
【非特許文献１】（文献Ｃｏｒｏｎ９９） Ｊｅａｎ−Ｓｅｂａｓｔｅｉｎ Ｃｏｒｏｎ“Ｒｅｓｉｓｔａｎｃｅ ａｇａｉｎｓｔ Ｄｉｆｆｅｒｅｎｔｉａｌ Ｐｏｗｅｒ Ａｎａｌｙｓｉｓ ｆｏｒ Ｅｌｌｉｐｔｉｃ Ｃｕｒｖｅ Ｃｒｙｔｏｓｙｓｔｅｍｓ”，Ｃｒｙｐｔｏｇｒａｐｈｉｃ Ｈａｒｄｗａｒｅ ａｎｄ Ｅｍｂｅｄｄｅｄ Ｓｙｓｔｅｍｓ １９９９（ＣＨＥＳ１９９９），Ｌｅｃｔｕｒｅ Ｎｏｔｅｓ ｉｎ Ｃｏｍｐｕｔｅｒ Ｓｃｉｅｎｃｅ ｖｏｌ．１７１７，Ｓｐｒｉｎｇｅｒ−Ｖｅｒｌａｇ，ｐｐ．２９２−３０２，１９９９
【非特許文献２】（文献Ｉｚｕ−Ｔａｋａｇｉ０２） Ｔ．Ｉｚｕ，ａｎｄ Ｔ．Ｔａｋａｇｉ，”Ａ Ｆａｓｔ Ｐａｒａｌｌｅｌ Ｅｌｌｉｐｔｉｃ Ｃｕｒｖｅ Ｍｕｌｔｉｐｌｉｃａｔｉｏｎ Ｒｅｓｉｓｔａｎｔ ａｇａｉｎｓｔ Ｓｉｄｅ Ｃｈａｎｎｅｌ Ａｔｔａｃｋｓ”，Ｐｕｂｌｉｃ−Ｋｅｙ Ｃｒｙｐｔｏｇｒａｐｈｙ ２００２（ＰＫＣ２００２），Ｌｅｃｔｕｒｅ Ｎｏｔｅｓ ｉｎ Ｃｏｍｐｕｔｅｒ Ｓｃｉｅｎｃｅ ｖｏｌ．２２７４，ｐｐ．２８０−２９６，Ｓｐｒｉｎｇｅｒ−Ｖｅｒｌａｇ，２００２．
【非特許文献３】（文献Ｊｏｙｅ−Ｔｙｍｅｎ０１） Ｍ．Ｊｏｙｅ，ａｎｄ Ｃ．Ｔｙｍｅｎ，“Ｐｒｏｔｅｃｔｉｏｎｓ ａｇａｉｎｓｔ ｄｉｆｆｅｒｅｎｔｉａｌ ａｎａｌｙｓｉｓ ｆｏｒ ｅｌｌｉｐｔｉｃ ｃｕｒｖｅ ｃｒｙｐｔｏｇｒａｐｈｙ”，Ｃｒｙｐｔｏｇｒａｐｈｉｃ Ｈａｒｄｗａｒｅ ａｎｄ Ｅｍｂｅｄｄｅｄ Ｓｙｓｔｅｍｓ ２００１（ＣＨＥＳ２００１），Ｌｅｃｔｕｒｅ Ｎｏｔｅｓ ｉｎ Ｃｏｍｐｕｔｅｒ Ｓｃｉｅｎｃｅ ｖｏｌ．２１６２，ｐｐ．３７７−３９０，Ｓｐｒｉｎｇｅｒ−Ｖｅｒｌａｇ，２００１．
【非特許文献４】（文献Ｇｏｕｂｉｎ０３） Ｌ．Ｇｏｕｂｉｎ，“Ａ Ｒｅｆｉｎｅｄ Ｐｏｗｅｒ−Ａｎａｌｙｓｉｓ Ａｔｔａｃｋ ｏｎ Ｅｌｌｉｐｔｉｃ Ｃｕｒｖｅ Ｃｒｙｐｔｏｓｙｓｔｅｍ”，Ｐｕｂｌｉｃ−Ｋｅｙ Ｃｒｙｐｔｏｇｒａｐｈｙ ２００３（ＰＫＣ２００３），Ｌｅｃｔｕｒｅ Ｎｏｔｅｓ ｉｎ Ｃｏｍｐｕｔｅｒ Ｓｃｉｅｎｃｅ ｖｏｌ．２５６７，Ｓｐｒｉｎｇｅｒ−Ｖｅｒｌａｇ，ｐｐ．１９９−２１０，２００３．
【非特許文献５】（文献Ｃｌａｖｉｅｒ−Ｊｏｙｅ０１） Ｃ．Ｃｌａｖｉｅｒ，ａｎｄ Ｍ．Ｊｏｙｅ，”Ｕｎｉｖｅｒｓａｌ ｅｘｐｏｎｅｎｔｉａｔｉｏｎ ａｌｇｏｒｉｔｈｍ −−Ａ ｆｉｒｓｔ ｓｔｅｐ ｔｏｗａｒｄｓ ｐｒｏｖａｂｌｅ ＳＰＡ−ｒｅｓｉｓｔａｎｃｅ−−”，Ｃｒｙｐｔｏｇｒａｐｈｉｃ Ｈａｒｄｗａｒｅ ａｎｄ Ｅｍｂｅｄｄｅｄ Ｓｙｓｔｅｍｓ ２００１（ＣＨＥＳ２００１），Ｌｅｃｔｕｒｅ Ｎｏｔｅｓ ｉｎ Ｃｏｍｐｕｔｅｒ Ｓｃｉｅｎｃｅ ｖｏｌ．２１６２，Ｓｐｒｉｎｇｅｒ−Ｖｅｒｌａｇ，ｐｐ．３００−３０８，２００１．
【発明の開示】
上記の目的を達成するために、本発明の楕円曲線暗号装置は、楕円曲線暗号処理を行なう楕円曲線暗号装置であって、有限体ＧＦ（ｐ＾ｍ）上における楕円曲線上の点Ｐの座標（Ｘ：Ｙ：Ｚ）を座標（ｒ１×（Ｘ−ｓ１）：ｒ２×（Ｙ−ｓ２）：ｒ３×（Ｚ−ｓ３））に変換する座標変換部（ただし、ｐは素数、ｍは１以上の整数、ｒ１，ｒ２，ｒ３はいずれも１以上且つ（ｐ−１）以下の整数、ｓ１，ｓ２，ｓ３はいずれも０以上且つ（ｐ−１）以下の整数、又、符号＾はべき乗を表わす）と、この座標変換部によって変換された楕円曲線上の点のスカラー倍算を行なうスカラー倍算演算部とをそなえ、パラメーターｓ１，ｓ２，ｓ３のうち少なくとも１つが０以外の値を有することを特徴としている。
なお、スカラー倍算演算部が、アド・アンド・ダブル・オールウェイズを用いたバイナリメソッドで、スカラー倍算を行なってもよく、又、モンゴメリ・ラダー法でスカラー倍算を行なってもよく、更に、ウィンドウ・メソッドでスカラー倍算を行なってもよい。
また、スカラー倍算演算部が、ｘ座標法でスカラー倍算を行なってもよく、連続楕円２倍算を用いてスカラー倍算を行なってもよい。
さらに、本発明の楕円曲線暗号方法は、楕円曲線暗号処理を行なう楕円曲線暗号方法であって、有限体ＧＦ（ｐ＾ｍ）上における楕円曲線上の点Ｐの座標（Ｘ：Ｙ：Ｚ）を座標（ｒ１×（Ｘ−ｓ１）：ｒ２×（Ｙ−ｓ２）：ｒ３×（Ｚ−ｓ３））に変換する座標変換ステップ（ただし、ｐは素数、ｍは１以上の整数、ｒ１，ｒ２，ｒ３はいずれも１以上且つ（ｐ−１）以下の整数、ｓ１，ｓ２，ｓ３はいずれも０以上且つ（ｐ−１）以下の整数、又、符号＾はべき乗を表わす）と、この座標変換ステップにおいて変換された楕円曲線上の点のスカラー倍算を行なうスカラー倍算演算ステップとをそなえ、パラメーターｓ１，ｓ２，ｓ３のうち少なくとも１つが０以外の値を有することを特徴としている。
なお、スカラー倍算演算ステップにおいて、アド・アンド・ダブル・オールウェイズを用いたバイナリメソッドでスカラー倍算を行なってもよく、又、スカラー倍算演算ステップにおいてモンゴメリ・ラダー法でスカラー倍算を行なってもよく、更に、スカラー倍算演算ステップにおいて、ウィンドウ・メソッドでスカラー倍算を行なってもよい。
また、スカラー倍算演算ステップにおいて、ｘ座標法でスカラー倍算を行なってもよく、又、スカラー倍算演算ステップにおいて、連続楕円２倍算を用いてスカラー倍算を行なってもよい。
さらに、本発明の楕円曲線暗号プログラムは、楕円曲線暗号処理を行なう楕円曲線暗号プログラムであって、有限体ＧＦ（ｐ＾ｍ）上における楕円曲線上の点Ｐの座標（Ｘ：Ｙ：Ｚ）を座標（ｒ１×（Ｘ−ｓ１）：ｒ２×（Ｙ−ｓ２）：ｒ３×（Ｚ−ｓ３））に変換する座標変換部（ただし、ｐは素数、ｍは１以上の整数、ｒ１，ｒ２，ｒ３はいずれも１以上且つ（ｐ−１）以下の整数、ｓ１，ｓ２，ｓ３はいずれも０以上且つ（ｐ−１）以下の整数であり、且つ、これらのｓ１，ｓ２，ｓ３のうち少なくとも１つが０以外の値を有する。又、符号＾はべき乗を表わす）と、座標変換部によって変換された楕円曲線上の点のスカラー倍算を行なうスカラー倍算演算部としてコンピュータを機能させることを特徴としている。
なお、スカラー倍算演算部としてコンピュータを機能させる際に、アド・アンド・ダブル・オールウェイズを用いたバイナリメソッドでスカラー倍算を行なってもよく、又、スカラー倍算演算部としてコンピュータを機能させる際に、モンゴメリ・ラダー法でスカラー倍算を行なってもよく、更に、スカラー倍算演算部としてコンピュータを機能させる際に、ウィンドウ・メソッドでスカラー倍算を行なってもよい。
また、スカラー倍算演算部としてコンピュータを機能させる際に、ｘ座標法でスカラー倍算を行なってもよく、又、スカラー倍算演算部としてコンピュータを機能させる際に、連続楕円２倍算を用いてスカラー倍算を行なってもよい。
そして、本発明のコンピュータ読取可能な記録媒体は、上述した楕円曲線暗号プログラムを記録したものである。
このように、本発明の楕円曲線暗号装置，楕円曲線暗号方法，楕円曲線暗号プログラムおよび同プログラムを記録したコンピュータ読取可能な記録媒体によれば、以下の効果ないし利点がある。
（１）有限体ＧＦ（ｐ＾ｍ）上における楕円曲線上の点Ｐの座標（Ｘ：Ｙ：Ｚ）を座標（ｒ１×（Ｘ−ｓ１）：ｒ２×（Ｙ−ｓ２）：ｒ３×（Ｚ−ｓ３））に変換（ただし、ｐは素数、ｍは１以上の整数、ｒ１，ｒ２，ｒ３はいずれも１以上且つ（ｐ−１）以下のランダムな整数、ｓ１，ｓ２，ｓ３はいずれも０以上且つ（ｐ−１）以下のランダムな整数であり、且つ、これらのｓ１，ｓ２，ｓ３のうち少なくとも１つが０以外の値を有する。又、符号＾はべき乗を表わす）し、この変換された楕円曲線上の点のスカラー倍算を行なうので、楕円曲線暗号におけるスカラー倍算を、サイドチャネル攻撃に対する耐性をもって計算することが可能となる。
（２）特に、ｓ１，ｓ２，ｓ３のうち少なくとも１つが０以外の値を有するので、特殊点の線型変換座標での座標が０以外の値となり、スカラー倍算の途中で出現することがなく、これにより特殊点攻撃に対して安全である。
（３）アド・アンド・ダブル・オールウェイズを用いたバイナリメソッドで、スカラー倍算を行なうことにより、ＳＰＡおよびＤＰＡに対して安全である。
（４）ヤコビアン座標におけるＲＰＣと同様のランダム効果が期待でき、ＤＰＡに対しても安全である。
（５）モンゴメリ・ラダー法で前記スカラー倍算を行なうことにより、ＳＰＡおよびＤＰＡに対して安全である。
（６）ｘ座標法で前記スカラー倍算を行なうことにより、ＳＰＡおよびＤＰＡに対して安全であり、さらに計算時間を短縮することができる。
（７）ウィンドウ・メソッドで前記スカラー倍算を行なうことにより、ＳＰＡおよびＤＰＡに対して安全である。
（８）連続楕円２倍算を用いて前記スカラー倍算を行なうことにより、高速に演算を行なうことができる。
【図面の簡単な説明】
図１は楕円加算を説明するための図である。
図２は楕円２倍算を説明するための図である。
図３は本発明に係る楕円曲線暗号装置の要部の構成を示す図である。
図４は本発明の一実施形態としての楕円曲線暗号装置の機能構成を示すブロック図である。
図５は本発明の楕円曲線暗号プログラムを実行する楕円曲線暗号装置のハードウェア構成の一例を示す図である。
【発明を実施するための最良の形態】
以下、図面を参照して本発明の実施の形態を説明する。
（ａ）基本説明
本発明の一実施形態としての楕円曲線暗号装置は、例えば、楕円曲線暗号の専用の情報処理装置，パーソナルコンピュータ，ＩＣカード（スマートカード）等に内蔵されたＩＣチップ，携帯電話機，携帯情報端末装置（ＰＤＡ（Ｐｅｒｓｏｎａｌ ｄａｔａ ａｓｓｉｓｔａｎｔ）等），ＤＶＤプレーヤ等として実現されるものであり、演算を行なうプロセッサを有して構成されるものである。
以下の説明では、本発明にかかる楕円曲線暗号演算方法を、ｐを素数、ｍを１以上の整数とし、要素数ｐ＾ｍの有限体ＧＦ（ｐ＾ｍ）上の楕円曲線に適用した場合について説明する。なお、以下、特に断りの無い限り、小文字（ｄ等）はスカラー値を表わし、大文字（Ｐ，Ｔ等）は楕円曲線上の点を表わすものとする。又、楕円加算をＥＣＡＤＤ、楕円２倍算をＥＣＤＢＬと表わす。更に、符号“＾”はべき乗算を表わすものとし、“（”と“）２”とによって囲まれた数列は２進数で表現された数字を表わす。又、“Ｓ０１：”等のように、Ｓを付した数字はアルゴリズムを表わすプログラム例におけるステップ数を示すものとする。
ＧＦ（ｐ＾ｍ）上の楕円曲線Ｅは、以下の方程式を満たす点（ｘ，ｙ）の集合に、無限遠点（以下、ゼロ点という場合もある）と呼ばれる点∞を加えた集合である。なお、無限遠点∞を０と表すこともある。
Ｅ：ｙ＾２＋ａ１×ｘ×ｙ＋ａ３×ｙ＝ｘ＾３＋ａ２×ｘ＾２＋ａ４×ｘ＋ａ６ここでａ１，ａ２，ａ３，ａ４，ａ６，ｘ，ｙはそれぞれＧＦ（ｐ＾ｍ）の要素である。楕円曲線上の点は（ｘ，ｙ）のような座標形式で表現できるが、無限遠点∞は（ｘ，ｙ）のような座標形式で表現することができない唯一の点である。
ＰをＧＦ（ｐ＾ｍ）上の楕円曲線Ｅ上の点とし、以下のようにＰの逆元−Ｐを定義する。
（１）Ｐ＝∞ならば、−Ｐ＝∞
（２）Ｐ≠∞ならば、Ｐ＝（ｘ，ｙ）としたときに、
−Ｐ＝（ｘ，−ｙ−ａ１×ｘ−ａ３）
また、Ｐ１，Ｐ２をＧＦ（ｐ＾ｍ）上の楕円曲線Ｅ上の２点とし、以下に示すようにＰ１とＰ２との和Ｐ３＝Ｐ１＋Ｐ２を定義する。
（１）Ｐ１＝∞ならば、Ｐ３＝Ｐ２
（２）Ｐ２＝∞ならば、Ｐ３＝Ｐ１
（３）Ｐ１＝−Ｐ２ならば、Ｐ３＝∞
（４）Ｐ１≠−Ｐ２ならばＰ１＝（ｘ１，ｙ１），Ｐ２＝（ｘ２，ｙ２），Ｐ３＝（ｘ３，ｙ３）としたときに、
ｘ３＝λ＾２＋ａ１×λ−ａ２−ｘ１−ｘ２，
ｙ３＝−（λ＋ａ１）×ｘ３−ν−ａ３，
ただし、
Ｐ１≠Ｐ２のとき
λ＝（ｙ２−ｙ１）／（ｘ２−ｘ１）
ν＝（ｙ１×ｘ２−ｙ２×ｘ１）／（ｘ２−ｘ１）
Ｐ１＝Ｐ２のとき
λ＝（３×ｘ１＾２＋２×ａ２×ｘ＋ａ４−ａ１×ｙ１）／（２×ｙ１＋ａ１×ｘ１＋ａ３）
ν＝（−ｘ１＾３＋ａ４×ｘ１＋２×ａ６−ａ３×ｙ１）／（２×ｙ１＋ａ１×ｘ１＋ａ３）
と定める。
Ｐ１≠Ｐ２のときに、Ｐ１＋Ｐ２を計算することを楕円加算（ＥＣＡＤＤ）、Ｐ１＝Ｐ２のときにＰ１＋Ｐ２＝２×Ｐ１を計算することを楕円２倍算（ＥＣＤＢＬ）という。楕円加算・楕円２倍算は、有限体ＧＦ（ｐ＾ｍ）での加減算・乗算・平方算・逆元計算の組み合わせによって計算される。
ｐを素数とするとき、有限体ＧＦ（ｐ）を素体という。特に、ｐが５以上の素数の場合には、素体ＧＦ（ｐ）上の楕円曲線Ｅは、方程式
Ｅ：ｙ＾２＝ｘ＾３＋ａ×ｘ＋ｂ
を満たす点（ｘ，ｙ）の集合上に、無限遠点と呼ばれる点∞を加えた集合である。なお、無限遠点∞を０と表すこともある。又、ａ，ｂ，ｘ，ｙはそれぞれＧＦ（ｐ）の要素である。楕円曲線上の点は（ｘ，ｙ）のような座標形式で表現できるが、無限遠点∞は（ｘ，ｙ）のような座標形式で表現することができない唯一の点である。
ＰをＧＦ（ｐ）上の楕円曲線Ｅ上の点とし、以下に示すようにＰの逆元−Ｐを定義する。
（１）Ｐ＝∞ならば、−Ｐ＝∞
（２）Ｐ≠∞ならば、Ｐ＝（ｘ，ｙ）としたときに、−Ｐ＝（ｘ，−ｙ）
また、Ｐ１，Ｐ２をＧＦ（ｐ）上の楕円曲線Ｅ上の２点とし、以下に示すようにしてＰ１とＰ２との和Ｐ３＝Ｐ１＋Ｐ２を定義する。
（１）Ｐ１＝∞ならば、Ｐ３＝Ｐ２
（２）Ｐ２＝∞ならば、Ｐ３＝Ｐ１
（３）Ｐ１＝−Ｐ２ならば、Ｐ３＝∞
（４）Ｐ１≠−Ｐ２ならば、Ｐ１＝（ｘ１，ｙ１），Ｐ２＝（ｘ２，ｙ２），Ｐ３＝（ｘ３，ｙ３）としたときに、
ｘ３＝λ＾２−ｘ１−ｘ２
ｙ３＝−λ×ｘ３−ν，
ただし
Ｐ１≠Ｐ２のとき
λ＝（ｙ２−ｙ１）／（ｘ２−ｘ１）
ν＝（ｙ１×ｘ２−ｙ２×ｘ１）／（ｘ２−ｘ１）
Ｐ１＝Ｐ２のとき
λ＝（３×ｘ１＾２＋ａ）／（２×ｙ１）
ν＝（−ｘ１＾３＋ａ×ｘ１＋２×ｂ）／（２×ｙ１）
と定める。
Ｐ１≠Ｐ２のときに、Ｐ１＋Ｐ２を計算することを楕円加算（ＥＣＡＤＤ）、Ｐ１＝Ｐ２のときにＰ１＋Ｐ２＝２×Ｐ１を計算することを楕円２倍算（ＥＣＤＢＬ）という。楕円加算・楕円２倍算は、有限体ＧＦ（ｐ）での加減算・乗算・平方算・逆元計算の組み合わせによって計算される。
図１は楕円加算を説明するための図、図２は楕円２倍算を説明するための図である。楕円加算は、図１に示すように、楕円曲線上の点Ｐ１＝（ｘ１，ｙ１）とＰ２＝（ｘ２，ｙ２）とを結ぶ直線と楕円曲線との交点を、ｘ軸で折り返した点Ｐ３＝Ｐ１＋Ｐ２＝（ｘ３，ｙ３）として定義される。楕円２倍算は、図２に示されるように、楕円曲線上の点Ｐ１＝（ｘ１，ｙ１）の接線と楕円曲線との交点を、ｘ軸で折り返した点Ｐ４＝Ｐ１＋Ｐ１＝２×Ｐ１＝（ｘ４，ｙ４）として定義される。
有限体上の楕円曲線Ｅと、ベースポイントと呼ばれる曲線上の点Ｐと、スカラーと呼ばれる整数ｄとに対して、点ｄ×Ｐ＝Ｐ＋Ｐ＋…＋Ｐ（ｄ個の和）を計算することをスカラー倍算という。スカラー倍算は、楕円加算、楕円２倍算の組み合わせによって実現される。
楕円加算、楕円２倍算、スカラー倍算の計算時間は、有限体における乗算、平方算、逆元計算の計算時間の和によって見積もられることが多い。これは実際の楕円加算、楕円２倍算、スカラー倍算の計算が、有限体における加減算・乗算・平方算・逆元計算の組み合わせで計算され、多くの場合、加減算の計算時間はその他の計算時間に比べて無視できるほど短いからである。
一般に有限体ＧＦ（ｐ＾ｍ）での逆元計算の計算時間は、乗算・平方算の計算時間に比べて非常に大きくなる。このため、本発明の楕円曲線暗号装置においては、楕円曲線の点を表現する上で線形座標を使用するようになっている。
本発明で使用する線型変換座標においては、ＧＦ（ｐ＾ｍ）上の楕円曲線の点は（Ｘ：Ｙ：Ｚ）のような３つの要素の組み合わせで表される。ただし、ＧＦ（ｐ＾ｍ）の要素ｒ１≠０、ｒ２≠０、ｒ３≠０、ｓ１、ｓ２、ｓ３に対して、（Ｘ：Ｙ：Ｚ）と（ｒ１×（Ｘ−ｓ１）：ｒ２×（Ｙ−ｓ２）：ｒ３×（Ｚ−ｓ３））とが同じ点と考える。
そして、本楕円曲線暗号装置１１においては、線形変換座標は、有限体上における楕円曲線上の点Ｐの座標（Ｘ：Ｙ：Ｚ）を座標（ｒ１×（Ｘ−ｓ１）：ｒ２×（Ｙ−ｓ２）：ｒ３×（Ｚ−ｓ３））に変換するものであって、ｒ１，ｒ２，ｒ３はそれぞれ０以外の任意の整数であり、ｓ１，ｓ２，ｓ３の少なくともいずれか１つが０以外の整数である。なお、以下、これらのｒ１，ｒ２，ｒ３，ｓ１，ｓ２，ｓ３を線型変換座標のパラメータという場合もある。
線型変換座標を用いると、楕円曲線上の全ての点は（Ｘ：Ｙ：Ｚ）のような座標形式で表現することができる。又、無限遠点は∞＝（０：１：０）となる。
なお、線型変換座標のパラメータを（ｒ１，ｒ２，ｒ３，ｓ１，ｓ２，ｓ３）と表わす場合に、
（ｒ１，ｒ２，ｒ３，ｓ１，ｓ２，ｓ３）＝（ｒ，ｒ，ｒ，０，０，０）
とした場合に、射影座標として用いることができ、又、
（ｒ１，ｒ２，ｒ３，ｓ１，ｓ２，ｓ３）＝（ｒ＾２，ｒ＾３，ｒ，０，０，０）
とした場合に、ヤコビアン座標として用いることができる。
以下、本発明に係る楕円曲線暗号演算方法を、ｐを５以上の素数とし、要素数ｐの有限体ＧＦ（ｐ）（ｐは５以上の素数）上の楕円曲線に適用した場合について説明する。
ＧＦ（ｐ）上の楕円曲線Ｅは、以下の式で表わすことができる。
Ｅ：ｙ＾２＝ｘ＾３＋ａ×ｘ＋ｂ
ここでａ，ｂ，ｘ，ｙはＧＦ（ｐ）の要素で、４×ａ＾３＋２７×ｂ＾２≠０を満たす。
図３は本発明に係る楕円曲線暗号装置１１の要部の構成を示す図である。本楕円曲線暗号装置１１は、図３に示すように、演算部（プロセッサ）１２と記憶１６とをそなえて構成されている。記憶部１５は、後述する楕円曲線暗号の楕円加算，楕円２倍算，楕円２＾ｋ倍算等の演算プログラムを記憶するものである。
演算部１２は、演算器１３，レジスタ群１４および演算結果出力レジスタ群１５をそなえて構成されている。演算器１３は、記憶部１６に格納された楕円曲線暗号プログラムをレジスタ群１４を用いて実行するものであって、その演算結果を演算結果出力レジスタ群１５に出力するようになっている。
レジスタ群１４および演算結果出力レジスタ群１５は、いずれも複数のレジスタからなり、これらのレジスタに、演算を行なうための数値や、演算実行後の結果，現在実行しているコードのメモリアドレス、ＣＰＵの状態などを格納するものであり、演算結果出力レジスタ群１５には、特に演算器１３による演算結果が格納されるようになっている。
図４は本発明の一実施形態としての楕円曲線暗号装置１１の機能構成を示すブロック図である。本楕円曲線暗号装置１１は、図４に示すように、ゼロ点判定部２１，スカラー倍算処理部２２，線形座標変換部（座標変換部）２３および乱数生成部２４をそなえて構成されている。
乱数生成部２４は、乱数ｒ１，ｒ２，ｒ３を生成するものであり、生成した乱数ｒ１，ｒ２，ｒ３をスカラ倍算処理部２２および線形座標変換部２３に渡すようになっている。
ゼロ点判定部２１は、スカラー倍算の結果がゼロ点（無限遠点）であるか否かを判定するものである。
線形座標変換部２３は、有限体ＧＦ（ｐ）上における楕円曲線上の点Ｐの座標（Ｘ：Ｙ：Ｚ）を座標（ｒ１×（Ｘ−ｓ１）：ｒ２×（Ｙ−ｓ２）：ｒ３×（Ｚ−ｓ３））に変換（線形座標変換）するものであり、変換後の座標（以下、線形変換座標という場合もある）をスカラー倍算処理部２２に渡すようになっている。スカラー倍算処理部２２は、線形座標変換部２３によって変換された楕円曲線上の点のスカラー倍算ｄ×Ｐを演算するものであり、後述する種々のアルゴリズムを用いて楕円加算，楕円２倍算，楕円２＾ｋ倍算等の演算処理を行なうことにより、スカラー倍算を行なうようになっている。
なお、本楕円曲線暗号装置１１においては、例えば、演算部１２が、記憶部１６に記憶されたプログラムを実行することにより、ゼロ点判定部２１，スカラー倍算処理部２２，線形座標変換部２３および乱数生成部２４として機能するようになっている。
そして、スカラー倍算処理部２２が、スカラー倍算ｄ×Ｐを計算する際に、この変換後の線型変換座標における楕円加算と楕円２倍算を計算するようになっている。すなわち、スカラー倍算処理部２２は、素体ＧＦ（ｐ）上の楕円曲線Ｅに対して、パラメーター（ｒ１，ｒ２，ｒ３，ｓ１，ｓ２，ｓ３）＝（ｒ＾２，ｒ＾３，ｒ，ｓ，０，０）の線型変換座標における楕円加算（以下、ＬＣＥＣＡＤＤという）と楕円２倍算（以下、ＬＣＥＣＤＢＬという）を計算するようになっているのである。
このときの楕円加算の計算アルゴリズムをＡｌｇｏｒｉｔｈｍ ８に示すとともに、楕円２倍算の計算アルゴリズムをＡｌｇｏｒｉｔｈｍ ９に示す。
（ｂ）第１実施形態の説明
本発明の第１の実施形態としての楕円曲線暗号装置１１は、スカラー倍算処理部２２が、スカラー倍算ｄ×Ｐを計算する際に、バイナリ法（ＬＳＢ，アド・アンド・ダブル・オールウェイズ）を用いるようになっている。以下に、スカラー倍算処理部２２がスカラー倍算に用いるアルゴリズム例をＡｌｇｏｒｉｔｈｍ １０として示す。
なお、本第１実施形態の楕円曲線暗号装置１１においては、線形座標変換部２３は、パラメーター（ｒ１，ｒ２，ｒ３，ｓ１，ｓ２，ｓ３）＝（ｒ＾２，ｒ＾３，ｒ，ｓ，０，０）に基づいて、素体ＧＦ（ｐ）上の楕円曲線Ｅに対して、楕円曲線上の点Ｐの座標（Ｘ：Ｙ：Ｚ）を座標（ｒ１×（Ｘ−ｓ１）：ｒ２×（Ｙ−ｓ２）：ｒ３×（Ｚ−ｓ３））に変換するようになっている。すなわち、線形座標変換部２３は、楕円曲線上の点Ｐの座標（Ｘ：Ｙ：Ｚ）を座標（ｒ＾２×（Ｘ−ｓ）：ｒ＾３×Ｙ：ｒ×Ｚ）に変換（線形座標変換）するようになっている
ここで、ＬＣは線型写像座標への変換（線形座標変換）、ｉｎｖＬＣはその逆変換を表す。またＴ［０］，Ｔ［１］，Ｔ［２］はいずれも一時変数であり、ｄはｎビットのスカラー値で、ｄ［ｉ］はｄの下位ｉビット目の値である。
すなわち、本第１実施形態の楕円曲線暗号装置１１においては、演算部１２が上述したＡｌｇｏｒｉｔｈｍ １０のステップＳ１およびＳ２を実行することにより線形座標変換部２３として機能し、ステップＳ３〜ステップＳ７を実行することにより、スカラー処理部２２として機能するようになっているのである。
本発明の第１実施形態としての楕円曲線暗号装置１１によれば、線形座標変換部２３が、パラメーター（ｒ１，ｒ２，ｒ３，ｓ１，ｓ２，ｓ３）＝（ｒ＾２，ｒ＾３，ｒ，ｓ，０，０）に基づいて、素体ＧＦ（ｐ）上の楕円曲線Ｅに対して、楕円曲線上の点Ｐの座標（Ｘ：Ｙ：Ｚ）を座標（ｒ１×（Ｘ−ｓ１）：ｒ２×（Ｙ−ｓ２）：ｒ３×（Ｚ−ｓ３））に変換し、スカラー倍算処理部２２が、この変換後の線型変換座標における楕円加算と楕円２倍算を計算するので、ｓ≠０とすることにより、ｘ座標が０であるような特殊点は、線型変換座標でのＸ座標がｓの点として表され、スカラー倍算の途中で出現することがない。これにより特殊点攻撃に対して安全である。
また、スカラー倍算処理部２２が用いるＡｌｇｏｒｉｔｈｍ １０において、アド・アンド・ダブル・オールウェイズを用いているので、ＳＰＡおよびＤＰＡに対して安全である。
さらに、線形座標変換部２３が、パラメーター（ｒ１，ｒ２，ｒ３，ｓ１，ｓ２，ｓ３）＝（ｒ＾２，ｒ＾３，ｒ，ｓ，０，０）に基づいて、素体ＧＦ（ｐ）上の楕円曲線Ｅに対して、楕円曲線上の点Ｐの座標（Ｘ：Ｙ：Ｚ）を座標（ｒ１×（Ｘ−ｓ１）：ｒ２×（Ｙ−ｓ２）：ｒ３×（Ｚ−ｓ３））に変換し、スカラー倍算処理部２２が、この変換後の線型変換座標における楕円加算と楕円２倍算を計算するので、ヤコビアン座標におけるＲＰＣと同様のランダム効果が期待でき、ＤＰＡに対しても安全である。
（ｃ）第２実施形態の説明
前述した第１実施形態の楕円曲線暗号装置１１で用いられるＡｌｇｏｒｉｔｈｍ １０においては、変数Ｔ［２］に保管される値はｄとは無関係であり、そのステップＳ５以外では値が変更されることはない。そこでバイナリ法（ＬＳＢ，アド・アンド・ダブル・オールウェイズ）の変形として、以下のＡｌｇｏｒｉｔｈｍ １１に示すアルゴリズム例によって表わされる変形アド・アンド・ダブル・オールウェイズを適用することもできる。
本発明の第２実施形態としての楕円曲線暗号装置１１においては、スカラー倍算ｄ×Ｐを計算する際に、アド・アンド・ダブル・オールウェイズに代えてＡｌｇｏｒｉｔｈｍ １１に示すような変形アド・アンド・ダブル・オールウェイズを用いるようになっており、それ以外の部分については前述した第１実施形態の楕円曲線暗号装置１１とほぼ同様に構成されている。以下に、スカラー倍算処理部２２がスカラー倍算に用いるアルゴリズム例をＡｌｇｏｒｉｔｈｍ １１として示す。
ここで、ＬＣは線型写像座標への変換、ｉｎｖＬＣはその逆変換を表す。又、Ｔ［０］，Ｔ［１］，Ｔ［２］はいずれも一時変数、ｄはｎビットのスカラー値で、ｄ［ｉ］はｄの下位ｉビット目の値である。なお、ステップＳ０６とステップＳ１０とで使用される一時変数は共用されるものとする。
本第２実施形態の楕円曲線暗号装置１１においては、演算部１２が上述したＡｌｇｏｒｉｔｈｍ １１のステップＳ０１およびＳ０２を実行することにより線形座標変換部２３として機能し、ステップＳ０３〜ステップＳ１２を実行することにより、スカラー処理部２２として機能するようになっているのである。
本発明の第２実施形態の楕円曲線暗号装置１１によれば、スカラー倍算処理部２２が用いるＡｌｇｏｒｉｔｈｍ １１において、変形アド・アンド・ダブル・オールウェイズを用いているので、ＳＰＡに対して安全である。
また、線形座標変換部２３が、パラメーター（ｒ１，ｒ２，ｒ３，ｓ１，ｓ２，ｓ３）＝（ｒ＾２，ｒ＾３，ｒ，ｓ，０，０）に基づいて、素体ＧＦ（ｐ）上の楕円曲線Ｅに対して、楕円曲線上の点Ｐの座標（Ｘ：Ｙ：Ｚ）を座標（ｒ１×（Ｘ−ｓ１）：ｒ２×（Ｙ−ｓ２）：ｒ３×（Ｚ−ｓ３））に変換し、スカラー倍算処理部２２が、この変換後の線型変換座標における楕円加算と楕円２倍算を計算するので、ヤコビアン座標におけるＲＰＣと同様のランダム効果が期待でき、ＤＰＡに対しても安全である。
さらに、上記パラメータにおいてｓ≠０であるので、ｘ座標が０であるような特殊点は、線型変換座標でのＸ座標がｓとなり、スカラー倍算の途中で出現しない。これにより特殊点攻撃に対しても安全である。
（ｄ）第３実施形態の説明
本発明の第３実施形態としての楕円曲線暗号装置１１は、線形座標変換部２３が、パラメーター（ｒ１，ｒ２，ｒ３，ｓ１，ｓ２，ｓ３）＝（ｒ，ｒ，ｒ，ｓ，０，０）に基づいて、素体ＧＦ（ｐ）上の楕円曲線Ｅに対して、楕円曲線上の点Ｐの座標（Ｘ：Ｙ：Ｚ）を座標（ｒ１×（Ｘ−ｓ１）：ｒ２×（Ｙ−ｓ２）：ｒ３×（Ｚ−ｓ３））に変換する線形座標変換を行なうようになっており、更に、スカラー倍算処理部２２が、ｘ座標法を用いて楕円加算と楕円２倍算と楕円加算２倍算とを計算するようになっている。
本第３実施形態においては、スカラー倍算処理部２２がｘ座標法で前記スカラー倍算を行なうので、ＳＰＡおよびＤＰＡに対して安全である他、計算時間を短縮することができる。
また、本実施形態においては、上述の如くパラメーター（ｒ１，ｒ２，ｒ３，ｓ１，ｓ２，ｓ３）＝（ｒ，ｒ，ｒ，ｓ，０，０）を用いるようになっており、これにより、計算時間を短縮することができる。
ここで、ｘ座標法とは、楕円加算・楕円２倍算・楕円加算２倍算をｙ座標を用いずに計算するアルゴリズムである。参考までに、素体上の射影座標で表された楕円曲線に対する、文献Ｉｚｕ−Ｔａｋａｇｉ０２に開示されたｘ座標法のアルゴリズム例を、以下にＡｌｇｏｒｉｔｈｍ １２ｍ，１２ａ，１３，１４ｍ，１４ａとしてそれぞれ示す。なお、アルゴリズムの番号の末尾に付した符号ｍは乗法的（ｍｕｌｔｉｐｌｉｃａｔｉｖｅ）なＥＣＡＤＤを用いることを示すものであり、符号ａは加算的（ａｄｄｉｔｉｖｅ）なＥＣＡＤＤを用いることを示す。
本発明の第３実施形態の楕円曲線暗号装置１１によれば、線形座標変換部２３が、パラメーター（ｒ１，ｒ２，ｒ３，ｓ１，ｓ２，ｓ３）＝（ｒ，ｒ，ｒ，ｓ，０，０）に基づいて、素体ＧＦ（ｐ）上の楕円曲線Ｅに対して、楕円曲線上の点Ｐの座標（Ｘ：Ｙ：Ｚ）を座標（ｒ１×（Ｘ−ｓ１）：ｒ２×（Ｙ−ｓ２）：ｒ３×（Ｚ−ｓ３））に変換し、スカラー倍算処理部２２が、この変換後の線型変換座標における楕円加算と楕円２倍算を計算するので、ヤコビアン座標におけるＲＰＣと同様のランダム効果が期待でき、ＤＰＡに対しても安全である。
また、上記パラメータにおいてｓ≠０であるので、ｘ座標が０であるような特殊点は、線型変換座標でのＸ座標がｓとなり、スカラー倍算の途中で出現しない。これにより特殊点攻撃に対しても安全である。
さらに、上述したＡｌｇｏｒｉｔｈｍ １４ｍ，１４ａによれば、ｘＥＣＡＤＤＤＢＬｍやｘＥＣＡＤＤＤＢＬａを用いることにより、１つの関数で加算と２倍算とを行なうようになっている。これにより、関数の呼び出し回数を低減することができ、処理を高速化することができる。又、加算と２倍算とで演算結果を共有することができるので、計算量も低減することもできる。
（ｅ）第４実施形態の説明
本発明の第４実施形態としての楕円曲線暗号装置１１は、第３実施形態の楕円曲線暗号装置１１におけるスカラー倍算処理部２２が、スカラー倍算ｄ×Ｐを計算する際にモンゴメリ・ラダーを用いるようになっており、その他の部分については第３実施形態の楕円曲線暗号装置１１とほぼ同様に構成されている。以下に、スカラー倍算処理部２２がスカラー倍算に用いるアルゴリズム例をＡｌｇｏｒｉｔｈｍ １５として示す。
ここで、ｘＬＣは線型写像座標におけるｘ座標法で用いる座標への変換であり、ｉｎｖＬＣはその逆変換を表す。又、Ｔ［０］，Ｔ［１］およびＴ［２］はいずれも一時変数、ｄはｎビットのスカラー値で、ｄ［ｉ］はｄの下位ｉビット目の値である。
本発明の第４実施形態としての楕円曲線暗号装置１１によれば、上述した第４実施形態と同様の作用効果を得ることができる他、スカラー倍算処理部２２が用いるＡｌｇｏｒｉｔｈｍ １５において、モンゴメリ・ラダーを用いているので、ＳＰＡおよびＤＰＡに対して安全である。
（ｆ）第５実施形態の説明
本発明の第５実施形態としての楕円曲線暗号装置１１は、スカラー倍算処理部２２が、スカラー倍算ｄ×Ｐを計算する際に改良モンゴメリ・ラダーを用いるようになっており、それ以外の部分は第４実施形態の楕円曲線暗号装置１１とほぼ同様に構成されている。
改良モンゴメリ・ラダーは、上述したＡｌｇｏｒｉｔｈｍ １４ｍ，１４ａと同様に、ｘＥＣＡＤＤＤＢＬを用いることにより、１つの関数で加算と２倍算を行なうことにより、関数の呼び出し回数を低減して処理を高速化することができるものであり、又、加算と２倍算とで演算結果を共有することにより計算量を低減することもできるものである。以下に、スカラー倍算処理部２２がスカラー倍算に用いるアルゴリズム例をＡｌｇｏｒｉｔｈｍ １５′として示す。
ここで、ｘＬＣは線型写像座標におけるｘ座標法で用いる座標への変換であり、ｉｎｖＬＣはその逆変換を表す。又、Ｔ［０］，Ｔ［１］およびＴ［２］はいずれも一時変数、ｄはｎビットのスカラー値で、ｄ［ｉ］はｄの下位ｉビット目の値である。
本発明の第５実施形態としての楕円曲線暗号装置１１によれば、上述した第４実施形態と同様の作用効果を得ることができる他、スカラー倍算処理部２２が用いるＡｌｇｏｒｉｔｈｍ １５′において、ｘＥＣＡＤＤＤＢＬを用いるので、１つの関数で加算と２倍算を行なうことにより、関数の呼び出し回数を低減して処理を高速化することができる他、加算と２倍算とで演算結果を共有することにより計算量を低減することができる。
上述の如く、本発明の各実施形態にかかる楕円曲線暗号装置１１によれば、楕円曲線暗号におけるスカラー倍算を、サイドチャネル攻撃に対する耐性をもって計算することが可能となる。
（ｇ）第６実施形態
本発明の第６実施形態としての楕円曲線暗号装置１１は、スカラー倍算処理部２２が、スカラー倍算ｄ×Ｐを計算する際に、楕円２ｋ（２＾ｋ）倍算（ｉＥＣＤＢＬ）を用いるようになっている。ここで、楕円２ｋ倍算とは、与えられた点の２ｋ倍点２ｋ×Ｐを計算することである。楕円２ｋ倍算は、楕円２倍算をｋ回連続して用いることで計算可能であるが、１つの関数として処理した場合には、中間値の削減によって連続に適用するよりも効率的な計算が可能なことがある。
例えば、Ｋ．Ｉｔｏｈ，Ｍ．Ｔａｋｅｎａｋａ，Ｎ．Ｔｏｒｉｉ，Ｓ．Ｔｅｍｍａ，ａｎｄ Ｙ．Ｋｕｒｉｈａｒａ， ，，Ｆａｓｔ Ｉｍｐｌｅｍｅｎｔａｔｉｏｎ ｏｆ Ｐｕｂｌｉｃ−ｋｅｙ Ｃｒｙｐｔｏｇｒａｐｈｙ ｏｎ ＤＳＰ ＴＭＳ３２０Ｃ６２０１”，Ｃｒｙｐｔｏｇｒａｐｈｉｃ Ｈａｒｄｗａｒｅ ａｎｄ Ｅｍｂｅｄｄｅｄ Ｓｙｓｔｅｍｓ １９９９（ＣＨＥＳ１９９９），Ｌｅｃｔｕｒｅ Ｎｏｔｅｓ ｉｎ Ｃｏｍｐｕｔｅｒ Ｓｃｉｅｎｃｅ ｖｏｌ．１７１７，ｐｐ．６１−７２，Ｓｐｒｉｎｇｅｒ−Ｖｅｒｌａｇ，１９９９．（文献Ｉｔｏｈ＋９９という）には、以下のＡｌｇｏｒｉｔｈｍ １６に示すような、楕円２ｋ倍算を実現するためのアルゴリズムが開示されている。なお、この楕円２ｋ倍算は、素体上でヤコビアン座標で表現された楕円曲線に対して適用可能である。
上述したＡｌｇｏｒｉｔｈｍ １６は、ヤコビアン座標に対して楕円２ｋ倍算を適用したものであるが、このヤコビアン座標に代えて本発明の線形座標変換部２３により行なわれた線形変換座標に対して楕円２ｋ倍算を適用することもでき、これにより、演算速度を向上させることができる。
なお、線形座標変換部２３は、パラメーター（ｒ１，ｒ２，ｒ３，ｓ１，ｓ２，ｓ３）＝（ｒ＾２，ｒ＾３，ｒ，ｓ，０，０）に基づいて線形座標変換を行なってもよく、又、パラメーター（ｒ１，ｒ２，ｒ３，ｓ１，ｓ２，ｓ３）＝（ｒ，ｒ，ｒ，ｓ，０，０）に基づいて線形座標変換を行なってもよい。
（ｈ）その他
次に、上述した本発明の楕円曲線暗号プログラムを実行する楕円曲線暗号装置のハードウェア構成の一例を図５を参照して説明する。楕円暗号装置は、例えば、パーソナルコンピュータ等の情報処理装置により実現できる。
ＣＰＵ（Ｃｅｎｔｒａｌ Ｐｒｏｃｅｓｓｉｎｇ Ｕｎｉｔ）３１は、楕円曲線暗号の楕円加算、楕円２倍算等を実行する。メモリ３２は、演算に使用される各種のレジスタとして使用される。外部記憶装置３３は、ＯＳや、楕円曲線暗号プログラム等が格納される。
媒体駆動装置３４は、ＣＤＲＯＭ、ＤＶＤ、フレキシブルディスク、ＩＣカード等の可搬記録媒体３５の読み取り、あるいは書き込みを行なう装置である。
入力装置３６は、キーボード等のデータを入力する装置である。出力装置３７は、ディスプレイ、プリンタ等の装置である。ネットワーク接続装置３８は、インターネット等のネットワークに接続するための装置であり、この装置を介してネットワーク上のサーバからプログラムをダウンロードすることができる。なお、ＣＰＵ３１，メモリ３２，外部記憶装置３３，入力装置３６等はバス３９により接続されている。
そして、情報処理装置のＣＰＵ３１が、楕円曲線暗号プログラムを実行することにより、上述したゼロ点判定部２１，スカラー倍算処理部２２，線形座標変換部（座標変換部）２３および乱数生成部２４として機能するようになっている。
なお、これらのゼロ点判定部２１，スカラー倍算処理部２２，線形座標変換部（座標変換部）２３および乱数生成部２４としての機能を実現するためのプログラム（楕円曲線暗号プログラム）は、例えばフレキシブルディスク，ＣＤ−ＲＯＭ，ＣＤ−Ｒ，ＣＤ−Ｒ／Ｗ，ＤＶＤ，ＤＶＤ−Ｒ，ＤＶＤ−Ｒ／Ｗ，磁気ディスク，光ディスク，光磁気ディスク等の、コンピュータ読取可能な記録媒体に記録された形態で提供される。そして、コンピュータはその記録媒体からプログラムを読み取って内部記憶装置または外部記憶装置に転送し格納して用いる。又、そのプログラムを、例えば磁気ディスク，光ディスク，光磁気ディスク等の記憶装置（記録媒体）に記録しておき、その記憶装置から通信経路を介してコンピュータに提供するようにしてもよい。
ゼロ点判定部２１，スカラー倍算処理部２２，線形座標変換部（座標変換部）２３および乱数生成部２４としての機能を実現する際には、内部記憶装置（記憶部１６，メモリ３２）に格納されたプログラムがコンピュータのマイクロプロセッサ（演算部１２，ＣＰＵ３１）によって実行される。このとき、記録媒体に記録されたプログラムをコンピュータが読み取って実行するようにしてもよい。
なお、本実施形態において、コンピュータとは、ハードウェアとオペレーティングシステムとを含む概念であり、オペレーティングシステムの制御の下で動作するハードウェアを意味している。又、オペレーティングシステムが不要でアプリケーションプログラム単独でハードウェアを動作させるような場合には、そのハードウェア自体がコンピュータに相当する。ハードウェアは、少なくとも、ＣＰＵ等のマイクロプロセッサと、記録媒体に記録されたコンピュータプログラムを読み取るための手段とをそなえており、本実施形態においては、楕円曲線暗号装置１１がコンピュータとしての機能を有しているのである。
さらに、本実施形態における記録媒体としては、上述したフレキシブルディスク，ＣＤ−ＲＯＭ，ＣＤ−Ｒ，ＣＤ−Ｒ／Ｗ，ＤＶＤ，ＤＶＤ−Ｒ，ＤＶＤ−Ｒ／Ｗ，磁気ディスク，光ディスク，光磁気ディスクのほか、ＩＣカード，ＲＯＭカートリッジ，磁気テープ，パンチカード，コンピュータの内部記憶装置（ＲＡＭやＲＯＭなどのメモリ），外部記憶装置等や、バーコードなどの符号が印刷された印刷物等のコンピュータ読取可能な種々の媒体を利用することができる。
そして、本発明は、楕円曲線暗号の暗号化及び解読を行なう専用の装置に限らず、ＩＣカード、ＤＶＤ装置、携帯電話機、パーソナルコンピュータ等の種々の製品に適用できる。
そして、本発明は上述した各実施形態に限定されるものではなく、本発明の趣旨を逸脱しない範囲で種々変形して実施することができる。
例えば、演算部１２が、記憶部１６に記憶されたプログラムを実行することにより、ゼロ点判定部２１，スカラー倍算処理部２２，線形座標変換部２３および乱数生成部２４として機能するようになっているが、これに限定されるものではなく、例えば、ゼロ点判定部２１，スカラー倍算処理部２２，線形座標変換部２３および乱数生成部２４のうちの一部の機能を外部装置が処理してもよく、例えば、スカラー倍算処理部２２のみを実行してもよい。
また、本楕円曲線暗号装置１１は、例えば、プロセッサをそなえたスマートカードによって実現されてもよく、又、スマートカードのメモリに秘密鍵や秘密鍵のみを格納しておき、このスマートと通信可能に接続された外部装置（楕円曲線暗号装置）によって楕円曲線暗号処理を行なってもよい。
さらに、上述した第１実施形態および第２実施形態では、線形座標変換部２３が、パラメーター（ｒ１，ｒ２，ｒ３，ｓ１，ｓ２，ｓ３）＝（ｒ＾２，ｒ＾３，ｒ，ｓ，０，０）に基づいて線形座標変換を行なう例について説明しているが、これに限定されるものではなく、例えば、パラメータ（ｒ１，ｒ２，ｒ３）の部分が第３〜第５実施形態と同様に（ｒ，ｒ，ｒ）であってもよく、又、これらのｒ１，ｒ２，ｒ３のうち一部もしくは全てが互いに異なる数値であってもよい。
また、上述した第３〜第５実施形態では、線形座標変換部２３が、パラメーター（ｒ１，ｒ２，ｒ３，ｓ１，ｓ２，ｓ３）＝（ｒ，ｒ，ｒ，ｓ，０，０）に基づいて線形座標変換を行なう例について説明しているが、これに限定されるものではなく、例えば、パラメータ（ｒ１，ｒ２，ｒ３）の部分が第１実施形態や第２実施形態と同様に（ｒ＾２，ｒ＾３，ｒ）であってもよく、又、これらのｒ１，ｒ２，ｒ３のうち一部もしくは全てが互いに異なる数値であってもよい。
さらに、上述した各実施形態について、線形座標変換部２３が線形座標変換に用いるパラメーター（ｒ１，ｒ２，ｒ３，ｓ１，ｓ２，ｓ３）における、パラメータ（ｓ１，ｓ２，ｓ３）の部分は、（ｓ、０，０）に限定されるものではなく、例えば、ｓ１，ｓ２，ｓ３のいずれも０以外の値であってもよく、又、ｓ１とｓ３とだけがそれぞれ０，ｓ１とｓ２とだけがそれぞれ０，ｓ３だけが０，ｓ２だけが０，ｓ１だけが０等、種々変形して実施することができる。更に、これらのｓ１，ｓ２，ｓ３のうち一部もしくは全てが互いに異なる数値であってもよい。
ここで、パラメータｓ１に０ではない数値ｓを適用することにより、ｘ座標が０であるような特殊点は、線型変換座標でのＸ座標がｓの点として表され、スカラー倍算の途中で出現することがない。これによりｘ座標に関する特殊点攻撃に対して安全となる。
また、パラメータｓ２に０ではない数値ｓを適用することにより、ｙ座標が０であるような特殊点は、線型変換座標でのＹ座標がｓの点として表され、スカラー倍算の途中で出現することがなく、ｙ座標に関する特殊点攻撃に対して安全となる。同様に、パラメータｓ３に０ではない数値ｓを適用することにより、ｚ座標が０であるような特殊点は、線型変換座標でのＺ座標がｓの点として表され、スカラー倍算の途中で出現することがなく、ｚ座標に関する特殊点攻撃に対して安全となる。
さらに、上述した線形座標変換部２３によって線形座標変換を行なった変換後の座標を、スカラー倍算処理部２２が、ウィンドウ法（Ａｌｇｏｒｉｔｈｍ ６，６′，６″参照）を用いてスカラー倍算を行なってもよく、これにより、特殊点攻撃に対して安全であるとともにＳＰＡに対しても安全である。
また、上述した各実施形態においては、ｐを５以上の素数とし、要素数ｐの有限体ＧＦ（ｐ）（ｐは５以上の素数）上の楕円曲線に適用した場合について説明しているが、これに限定されるものではなく、本発明の趣旨を逸脱しない範囲で種々変形して実施することができる。
なお、本発明の各実施形態が開示されていれば、本発明の楕円曲線暗号装置，楕円曲線暗号方法，楕円曲線暗号プログラムおよび同プログラムを記録したコンピュータ読取可能な記録媒体を当業者によって実施・製造することが可能である。
【産業上の利用可能性】
以上のように、本発明の楕円曲線暗号装置，楕円曲線暗号方法，楕円曲線暗号プログラムおよび同プログラムを記録したコンピュータ読取可能な記録媒体は、楕円曲線暗号処理を行なうのに有用であり、特にサイドチャネル攻撃に対して有効である。
【図１】
【図２】
【図３】
【図４】
【図５】
【技術分野】
本発明は、楕円曲線暗号処理に関し、特に、楕円曲線暗号処理を行なうプロセッサにおける電力解析攻撃の防止に用いて好適な、楕円曲線暗号装置，楕円曲線暗号方法，楕円曲線暗号プログラムおよび同プログラムを記録したコンピュータ読取可能な記録媒体に関する。
【背景技術】
暗号方式には公開鍵暗号方式と共通鍵暗号方式とが含まれる。公開鍵暗号方式は、暗号化と復号化とで異なる鍵（キー）を用いる方式である。典型的な公開鍵暗号方式では、暗号化を行なうための鍵（公開鍵）を公開しておき、この公開鍵を用いて平文を暗号化して受信者に送信する。暗号文を復号化するための鍵（秘密鍵）は受信者のみが知る秘密情報として保持されており、受信者がこの秘密鍵を用いて暗号文を復号化することにより平文を得ることができる。
また、近年では、公開鍵暗号として楕円曲線暗号（Ｅｌｌｉｐｔｉｃ Ｃｕｒｖｅ Ｃｒｙｐｔｏｇｒａｐｈｙ）が注目を集めている。この楕円曲線暗号にはさまざまな種類の暗号化・復号化アルゴリズムが知られているが、ほとんどの暗号化・復号化処理でスカラー倍算という演算が用いられる。ここでスカラー倍算とは、楕円曲線上のベースポイントと呼ばれる点Ｐとスカラーと呼ばれる整数ｄとから、ｄ×Ｐ＝Ｐ＋Ｐ＋．．＋Ｐ（ｄ個の和）を計算することである。なお、楕円曲線暗号においては、ベースポイントＰとスカラー倍点ｄ×Ｐとから、スカラーｄ（秘密鍵）を求めることは困難であることが知られている。
ここで、楕円曲線暗号の例として、ＥＣＥＳ暗号方式を説明する。送信者Ａが秘密鍵ｓ（ｓは整数）を持ち、受信者Ｂが秘密鍵ｔ（ｔは整数）を持つ場合に、楕円曲線Ｅと、楕円曲線Ｅ上に設定されるベースポイントＰ（＝（ｘ，ｙ））と、公開鍵ｓ×Ｐ（送信者Ａの秘密鍵ｓとベースポイントＰとのスカラー倍点）と、公開鍵ｔ×Ｐ（受信者Ｂの秘密鍵ｔとベースポイントＰとのスカラー倍点）とがあらかじめ公開されている。
このとき送信者Ａは、自分の秘密鍵ｓと、受信者Ｂの公開鍵ｔ×Ｐとのスカラー倍算ｓ×（ｔ×Ｐ）を計算し、そのｘ座標のビット表現を求め、このビット表現とメッセージのビット表現との間でビット対応のＥＯＲ（Ｅｘｃｌｕｓｉｖｅ ＯＲ：排他的論理和）演算を施すことで、メッセージｍに対する暗号文Ｃを生成し、それを受信者Ｂに送信する。受信者Ｂは、自分の秘密鍵ｔと、送信者Ａの公開鍵ｓ×Ｐとのスカラー倍算ｔ×（ｓ×Ｐ）を計算し、そのｘ座標のビット表現を求める。そして、
ｓ×（ｔ×Ｐ）＝ｔ×（ｓ×Ｐ）
という関係式が成立することを考慮して、そのビット表現と暗号文Ｃのビット表現との間でビット対応のＥＯＲ演算を施すことで、暗号文Ｃを復号してメッセージｍを得る。このようにしてＥＣＥＳ暗号と呼ばれる暗号方式では、スカラー倍を用いて暗号化・復号化処理を行なう。
また、暗号の分野における技術の一つに、解読技術と呼ばれるものがある。解読技術とは秘密鍵等の秘密情報を暗号文等入手可能な情報から推定する技術のことであり、様々な手法が存在する。その中で最近注目されている技術に、サイドチャネル攻撃と呼ばれる手法がある。
サイドチャネル攻撃は、１９９８年にＰａｕｌ Ｋｏｃｈｅｒによって考案された手法であって、スマートカード等に搭載された暗号プロセッサに様々な入力データを与えた時のサイドチャネル情報（消費電力データ・消費時間データ・電磁波データ等）を収集・解析することにより、暗号プロセッサ内部の鍵情報を推定する手法である。サイドチャネル攻撃を用いると、公開鍵暗号、共通鍵暗号共に暗号プロセッサから秘密鍵を推定できる可能性があることが指摘されている。
このサイドチャネル攻撃の中で、電力解析攻撃は強力な攻撃法である。この電力解析攻撃として、単純電力解析（ＳＰＡ；Ｓｉｎｇｌｅ Ｐｏｗｅｒ Ａｎａｌｙｓｉｓ）と、差分電力解析（ＤＰＡ；Ｄｉｆｆｅｒｅｎｔｉａｌ Ｐｏｗｅｒ Ａｎａｌｙｓｉｓ）との２種類の手法が知られている。ＳＰＡは暗号プロセッサにおける単一の電力消費データの特徴から秘密鍵の推定を行なう方式であり、ＤＰＡは多数の電力消費データの差分を解析することで秘密鍵の推定を行なう方式である。
そして、楕円曲線暗号に対しても、上述したＳＰＡやＤＰＡを適用することが可能である。この場合、スカラー倍算が攻撃対象となることが多い。詳細な推定法については、Ｊｅａｎ−Ｓｅｂａｓｔｅｉｎ Ｃｏｒｏｎ“Ｒｅｓｉｓｔａｎｃｅ ａｇａｉｎｓｔ Ｄｉｆｆｅｒｅｎｔｉａｌ Ｐｏｗｅｒ Ａｎａｌｙｓｉｓ ｆｏｒ Ｅｌｌｉｐｔｉｃ Ｃｕｒｖｅ Ｃｒｙｔｏｓｙｓｔｅｍｓ”，Ｃｒｙｐｔｏｇｒａｐｈｉｃ Ｈａｒｄｗａｒｅ ａｎｄ Ｅｍｂｅｄｄｅｄ Ｓｙｓｔｅｍｓ １９９９（ＣＨＥＳ１９９９），Ｌｅｃｔｕｒｅ Ｎｏｔｅｓ ｉｎ Ｃｏｍｐｕｔｅｒ Ｓｃｉｅｎｃｅ ｖｏｌ．１７１７，Ｓｐｒｉｎｇｅｒ−Ｖｅｒｌａｇ，ｐｐ．２９２−３０２，１９９９（以下、文献Ｃｏｒｏｎ９９という）等の文献にて述べられている。
さて、楕円曲線暗号の暗号化・復号化処理では、楕円曲線上の点のスカラー倍算が中心となる。スカラー倍算ｄ×Ｐの最も単純な実現手法としてバイナリ法（Ｂｉｎａｒｙ ｍｅｔｈｏｄ）があり、最上位ビット（Ｍｏｓｔ Ｓｉｇｎｉｆｉｃａｎｔ Ｂｉｔ；ＭＳＢ）から計算する方法（バイナリ法（ＭＳＢ））と、最下位ビット（Ｌｅａｓｔ Ｓｉｇｎｉｆｉｃａｎｔ Ｂｉｔ；ＬＳＢ）から計算する方法（バイナリ法（ＬＳＢ））とが知られている。
ここで、バイナリ法（ＭＳＢ）のアルゴリズム例を（１）Ａｌｇｏｒｉｔｈｍ １に、又、バイナリ法（ＬＳＢ）のアルゴリズム例を（２）Ａｌｇｏｒｉｔｈｍ ２に示す。なお、以下、特に断りの無い限り、小文字（ｄ等）はスカラー値を表わし、大文字（Ｐ，Ｔ等）は楕円曲線上の点を表わすものとする。又、楕円加算をＥＣＡＤＤ、楕円２倍算をＥＣＤＢＬと表わす。更に、符号“＾”はべき乗算を表わすものとし、“（”と“）２”とによって囲まれた数列は２進数で表現された数字を表わす。又、“Ｓ１：”等のように、Ｓを付した数字はアルゴリズムを表わすプログラム例におけるステップ数を示すものとする。
ここで、Ｔは一時変数、ｄはｎビットのスカラー値で、ｄ［ｉ］はｄの下位ｉ番目のビットの値である。
例えばｄ＝２１＝２＾４＋２＾２＋２＾０＝（１０１０１）２についてスカラー倍算ｄ×Ｐを計算する場合を考える。ステップＳ１においては変数Ｔに点Ｐが設定され、その次のステップＳ２〜Ｓ７において、ｉ＝３，２，１，０に対応する各処理が行なわれる。
ｉ＝３のとき、ステップＳ３では変数ＴにＥＣＤＢＬ（Ｔ）が設定され、処理後の変数Ｔの値は２×Ｐとなる。また、ｉ＝３のときには、ｄ［ｉ］＝ｄ［３］＝０なので、ステップＳ４〜Ｓ６はスキップされる。
ｉ＝２のとき、ステップＳ３では変数ＴにＥＣＤＢＬ（Ｔ）が設定され、処理後の変数Ｔの値は４×Ｐとなる。又、ｉ＝２のときには、ｄ［ｉ］＝ｄ［２］＝１なので、ステップＳ５では変数ＴにＥＣＤＢＬ（Ｔ，Ｐ）が設定され、処理後の変数Ｔの値は５×Ｐとなる。
ｉ＝１のとき、ステップＳ３では変数ＴにＥＣＤＢＬ（Ｔ）が設定され、処理後の変数Ｔの値は１０×Ｐとなる。又、ｉ＝１のときには、ｄ［ｉ］＝ｄ［１］＝０なので、ステップＳ４〜Ｓ６はスキップされる。
ｉ＝０とき、ステップＳ３では変数ＴにＥＣＤＢＬ（Ｔ）が設定され、処理後の変数Ｔの値は２０×Ｐとなる。又、ｉ＝０のときには、ｄ［ｉ］＝ｄ［０］＝１なので、ステップＳ５では変数ＴにＥＣＤＢＬ（Ｔ，Ｐ）が設定され、処理後の変数Ｔの値は２１×Ｐとなる。
以上でステップＳ２〜Ｓ７の処理が終了し、最後のステップＳ８で変数Ｔの値２１×Ｐが出力される。このようにバイナリ法（ＭＳＢ）では、スカラ値の最上位ビットから処理が行なわれるのである。
ここでＴ［０］，Ｔ［１］はいずれも一時変数、ｄはｎビットのスカラー値で、ｄ［ｉ］はｄの下位ｉ番目のビットの値である。
例えばｄ＝２１＝２＾４＋２＾２＋２＾０＝（１０１０１）２についてスカラー倍算ｄ×Ｐを計算する場合を考える。ステップＳ１においては変数Ｔ［１］に点Ｐが、又、変数Ｔ［０］に点Ｏが設定される。次のステップＳ３〜Ｓ８においてｉ＝０，１，２，３，４に対応する各処理が行なわれる。
ｉ＝０のときには、ｄ［ｉ］＝ｄ［０］＝１なので、ステップＳ５では変数Ｔ［０］にＥＣＡＤＤ（Ｔ［０］，Ｔ［１］）が設定され、処理後の変数Ｔ［０］の値はＰとなる。ステップＳ７では変数Ｔ［１］にＥＣＤＢＬ（Ｔ［１］）が設定され、処理後の変数Ｔ［１］の値は２×Ｐとなる。
ｉ＝１のときには、ｄ［ｉ］＝ｄ［１］＝０なので、ステップＳ４〜Ｓ６はスキップされる。ステップＳ７では変数Ｔ［１］にＥＣＤＢＬ（Ｔ［１］）が設定され、処理後の変数Ｔ［１］の値は４×Ｐとなる。
ｉ＝２のときには、ｄ［ｉ］＝ｄ［２］＝１なので、ステップＳ５では変数Ｔ［０］にＥＣＡＤＤ（Ｔ［０］，Ｔ［１］）が設定され、処理後の変数Ｔ［０］の値は５×Ｐとなる。ステップＳ７では変数Ｔ［１］にＥＣＤＢＬ（Ｔ［１］）が設定され、処理後の変数Ｔ［１］の値は８×Ｐとなる。
ｉ＝３のときには、ｄ［ｉ］＝ｄ［３］＝０なので、ステップＳ４〜Ｓ６はスキップされる。ステップＳ７では変数Ｔ［１］にＥＣＤＢＬ（Ｔ［１］）が設定され、処理後の変数Ｔ［１］の値は１６×Ｐとなる。
ｉ＝４のときには、ｄ［ｉ］＝ｄ［０］＝１なので、ステップＳ５では変数Ｔ［０］にＥＣＡＤＤ（Ｔ［０］，Ｔ［１］）が設定され、処理後の変数Ｔ［０］の値は２１×Ｐとなる。ステップＳ７では変数Ｔ［１］にＥＣＤＢＬ（Ｔ［１］）が設定され、処理後の変数Ｔ［１］の値は３２×Ｐとなる。
以上でステップＳ３〜Ｓ８の処理が終了し、最後のステップＳ９で変数Ｔ［０］の値２１×Ｐが出力される。このようにバイナリ法（ＬＳＢ）では、スカラ値の最下位ビットから処理が行なわれるのである。
さて、上述したＡｌｇｏｒｉｔｈｍ １およびＡｌｇｏｒｉｔｈｍ ２を点のスカラー倍算に使用した場合には、いずれも※印を付したステップＳ５の処理は、ｄのビット値ｄ［ｉ］に応じて実行されたりされなかったりする。ＳＰＡではこの性質を利用して秘密鍵ｄを解析する。多くの実験から、ＥＣＤＢＬとＥＣＡＤＤの電力波形は特徴的で容易に区別可能であることが知られている。従って、プロセッサにおけるＡｌｇｏｒｉｔｈｍ １およびＡｌｇｏｒｉｔｈｍ ２の演算において発生する電力波形を測定することによって、その波形からＥＣＤＢＬとＥＣＡＤＤの演算の順序と回数がわかり、秘密鍵ｄを解析して求めることができる。
このＳＰＡへの対策として、アド・アンド・ダブル・オールウェイズ（ａｄｄ−ａｎｄ−ｄｏｕｂｌｅ−ａｌｗａｙｓ）と呼ばれる、加算と２倍算とを常に行なう方法が文献Ｃｏｒｏｎ９９で提案されている。この方法では、常にＥＣＤＢＬ演算とＥＣＡＤＤ演算とが交互に行なわれるのでＳＰＡに対して安全である。以下に、先述したＡｌｇｏｒｉｔｈｍ １およびＡｌｇｏｒｉｔｈｍ ２に対してアド・アンド・ダブル・オールウェイズを施したアルゴリズム例をＡｌｇｏｒｉｔｈｍ ３およびＡｌｇｏｒｉｔｈｍ ４として示す。
ここで、Ｔ［０］，Ｔ［１］はいずれも一時変数、ｄはｎビットのスカラー値で、ｄ［ｉ］はｄの下位ｉビット目の値である。
ここで、Ｔ［０］，Ｔ［１］，Ｔ［２］はいずれも一時変数、ｄはｎビットのスカラー値で、ｄ［ｉ］はｄの下位ｉビット目の値である。
上述したＡｌｇｏｒｉｔｈｍ ３およびＡｌｇｏｒｉｔｈｍ ４を用いることによりＳＰＡを防止することができる。又、同様の効果をもつ方式として、モンゴメリ・ラダー（Ｍｏｎｔｇｏｍｅｒｙ−Ｌａｄｄｅｒ）を用いた方法が、Ｔ．Ｉｚｕ，ａｎｄ Ｔ．Ｔａｋａｇｉ，”Ａ Ｆａｓｔ Ｐａｒａｌｌｅｌ Ｅｌｌｉｐｔｉｃ Ｃｕｒｖｅ Ｍｕｌｔｉｐｌｉｃａｔｉｏｎ Ｒｅｓｉｓｔａｎｔ ａｇａｉｎｓｔ Ｓｉｄｅ Ｃｈａｎｎｅｌ Ａｔｔａｃｋｓ”，Ｐｕｂｌｉｃ−Ｋｅｙ Ｃｒｙｐｔｏｇｒａｐｈｙ ２００２（ＰＫＣ２００２），Ｌｅｃｔｕｒｅ Ｎｏｔｅｓ ｉｎ Ｃｏｍｐｕｔｅｒ Ｓｃｉｅｎｃｅ ｖｏｌ．２２７４，ｐｐ．２８０−２９６，Ｓｐｒｉｎｇｅｒ−Ｖｅｒｌａｇ，２００２．（以下、文献Ｉｚｕ−Ｔａｋａｇｉ０２という）にて提案されている。
スカラー倍算ｄ×Ｐにおいて、モンゴメリ・ラダーでは常にＥＣＤＢＬとＥＣＡＤＤを交互に計算するので、ＳＰＡに対して安全である。モンゴメリ・ラダーのアルゴリズム例をＡｌｇｏｒｉｔｈｍ ５に示す。
ここでＴ［０］，Ｔ［１］，Ｔ［２］はいずれも一時変数、ｄはｎビットのスカラー値で、ｄ［ｉ］はｄの下位ｉビット目の値である。
上述したＡｌｇｏｒｉｔｈｍ ３〜Ａｌｇｏｒｉｔｈｍ ５を用いることによりＳＰＡを防止することができるが、文献Ｃｏｒｏｎ９９にはこれらのアルゴリズムに対するＤＰＡについても述べられており、Ａｌｇｏｒｉｔｈｍ ３〜Ａｌｇｏｒｉｔｈｍ ５ではＤＰＡで秘密鍵を解析して求めることができることが示されている。そして、文献Ｃｏｒｏｎ９９には、ランダム化射影座標（Ｒａｎｄｏｍｉｚｅｄ Ｐｒｏｊｅｃｔｉｖｅ Ｃｏｏｒｄｉｎａｔｅｓ；ＲＰＣ）と呼ばれる、乱数を使用した楕円曲線上の点の表現を導入することによって、Ａｌｇｏｒｉｔｈｍ ３〜Ａｌｇｏｒｉｔｈｍ ５に対するＤＰＡへの各対策が提案されている。
以下に、Ａｌｇｏｒｉｔｈｍ ３に対してＲＰＣを施したアルゴリズム例をＡｌｇｏｒｉｔｈｍ ３′として示す他、Ａｌｇｏｒｉｔｈｍ ４に対してＲＰＣを施したアルゴリズム例をＡｌｇｏｒｉｔｈｍ ４′として、又、Ａｌｇｏｒｉｔｈｍ ５に対してＲＰＣを施したものをＡｌｇｏｒｉｔｈｍ ５′としてそれぞれ示す。なお、以下、ＲＰＣで表現された楕円曲線上の点をダッシュ（′もしくは’）付の変数で示す。
ここで、Ｔ’［０］，Ｔ’［１］，Ｔ’［２］はいずれも一時変数、ｄはｎビットのスカラー値で、ｄ［ｉ］はｄの下位ｉビット目の値である。又、ｉｎｖＲＰＣはＲＰＣ表現からの逆変換を示す。
ここで、Ｔ’［０］，Ｔ’［１］，Ｔ’［２］はいずれも一時変数、ｄはｎビットのスカラー値で、ｄ［ｉ］はｄの下位ｉビット目の値である。又、ｉｎｖＲＰＣはＲＰＣ表現からの逆変換を示す。
ここで、Ｔ’［０］，Ｔ’［１］，Ｔ’［２］はいずれも一時変数、ｄはｎビットのスカラー値で、ｄ［ｉ］はｄの下位ｉビット目の値である。又、ｉｎｖＲＰＣはＲＰＣ表現からの逆変換を示す。
また、ＤＰＡに対する対策として、ＲＰＣと同様の効果を持つ方式として、Ｍ．Ｊｏｙｅ，ａｎｄ Ｃ．Ｔｙｍｅｎ，“Ｐｒｏｔｅｃｔｉｏｎｓ ａｇａｉｎｓｔ ｄｉｆｆｅｒｅｎｔｉａｌ ａｎａｌｙｓｉｓ ｆｏｒ ｅｌｌｉｐｔｉｃ ｃｕｒｖｅ ｃｒｙｐｔｏｇｒａｐｈｙ”，Ｃｒｙｐｔｏｇｒａｐｈｉｃ Ｈａｒｄｗａｒｅ ａｎｄ Ｅｍｂｅｄｄｅｄ Ｓｙｓｔｅｍｓ ２００１（ＣＨＥＳ ２００１），Ｌｅｃｔｕｒｅ Ｎｏｔｅｓ ｉｎ Ｃｏｍｐｕｔｅｒ Ｓｃｉｅｎｃｅ ｖｏｌ．２１６２，ｐｐ．３７７−３９０，Ｓｐｒｉｎｇｅｒ−Ｖｅｒｌａｇ，２００１．（文献Ｊｏｙｅ−Ｔｙｍｅｎ０１という）で提案されたランダム化曲線（Ｒａｎｄｏｍｉｚｅｄ Ｃｕｒｖｅ；ＲＣ）法がある。
ＲＣは、ＲＰＣと同様に乱数を用いた点の表現を用いた点の表現を用いた点の表現を用いることによるＤＰＡ対策法である。ＲＣの適用方法はＲＰＣと同様である。Ａｌｇｏｒｉｔｈｍ ３に対してＲＣを施したアルゴリズム例をＡｌｇｏｒｉｔｈｍ ３″として示し、同様に、Ａｌｇｏｒｉｔｈｍ ４に対してＲＣを施したアルゴリズム例をＡｌｇｏｒｉｔｈｍ ４″，Ａｌｇｏｒｉｔｈｍ ５に対してＲＣを施したアルゴリズム例をＡｌｇｏｒｉｔｈｍ ５″としてそれぞれ示す。なお、以下、ＲＣで表現された楕円曲線上の点はダブルダッシュ（″もしくは”）付の変数で示す。
ここで、Ｔ”［０］，Ｔ”［１］，Ｔ”［２］はいずれも一時変数、ｄはｎビットのスカラー値で、ｄ［ｉ］はｄの下位ｉビット目の値である。又、ｉｎｖＲＣはＲＣ表現からの逆変換を示す。
ここで、Ｔ”［０］，Ｔ”［１］，Ｔ”［２］はいずれも一時変数、ｄはｎビットのスカラー値で、ｄ［ｉ］はｄの下位ｉビット目の値である。又、ｉｎｖＲＣはＲＣ表現からの逆変換を示す。
ここで、Ｔ”［０］，Ｔ”［１］，Ｔ”［２］はいずれも一時変数、ｄはｎビットのスカラー値で、ｄ［ｉ］はｄの下位ｉビット目の値である。又、ｉｎｖＲＣはＲＣ表現からの逆変換を示す。
また、スカラー倍算ｄ×Ｐの実現手法としては、前述したバイナリ法（Ａｌｇｏｒｉｔｈｍ １，２）やモンゴメリ・ラダー（Ａｌｇｏｒｉｔｈｍ ５）の他に、ウィンドウ法（ｗｉｎｄｏｗ ｍｅｔｈｏｄ）と呼ばれる方法もある。例えば、幅４ビットのウィンドウ法は、初期処理としてＰの０〜１５倍を計算し、その結果をテーブルとして持っておき、次にスカラー値を４ビット単位（ウィンドウ）に分割することにより、スカラー倍算を処理する。以下に、Ａｌｇｏｒｉｔｈｍ ６としてウィンドウ法（幅４ビット）のアルゴリズム例を示す。
ここで、ｄはｎビットのスカラー値で、ｎは４の倍数と仮定する。又、ｄ［ｉ，ｉ−３］はｄの下位ｉビット目から（ｉ−３）ビットまでの４ビット値とする。Ｗ［ｉ］はウィンドウ法で使用するテーブルである。
例えば、ｄ＝２１＝２＾４＋２＾２＋２＾０＝（１０１０１）２＝（０００１ ０１０１）２に対するスカラー倍算を考える。このときｄは５ビットで４の倍数ではないので、便宜上、その上位３ビットに０を挿入して８ビットとみなす。このときｎ＝８である。先ず、初期値としてステップＳ０１でＷ［０］＝０が、ステップＳ０２でＷ［１］＝Ｐが設定される。次にｉ＝２，３，．．．，１５に対し、ステップＳ０３〜Ｓ０５が実行される。各ｉに対し、ステップＳ０４でＷ［ｉ］＝ＥＣＡＤＤ（Ｗ［ｉ−１］，Ｐ）が設定される。このとき、Ｗ［ｉ］に設定されている値はｉ×Ｐとなっている。ステップＳ０３〜Ｓ０５の処理の終了後、ステップＳ０６で変数ＴにＷ［ｄ［ｎ−１，ｎ−４］］＝Ｗ［ｄ［７，４］］＝Ｗ［ｄ［０００１］］＝１×Ｐが設定される。
次に、ｉ＝３に対してステップＳ０７〜Ｓ１３が処理される。ステップＳ０８ではＴ：＝ＥＣＤＢＬ（Ｔ）が処理され、変数Ｔには２×Ｐが登録される。ステップＳ０９ではＴ：＝ＥＣＤＢＬ（Ｔ）が処理され、変数Ｔには４×Ｐが登録される。ステップＳ１０ではＴ：＝ＥＣＤＢＬ（Ｔ）が処理され、変数Ｔには８×Ｐが登録される。ステップＳ１１ではＴ：＝ＥＣＤＢＬ（Ｔ）が処理され、変数Ｔには１６×Ｐが登録される。ステップＳ１２ではＴ：＝ＥＣＡＤＤ（Ｔ，Ｗ［ｄ［ｉ，ｉ−３］］）＝ＥＣＡＤＤ（Ｔ，Ｗ［０１０１］）＝ＥＣＡＤＤ（１６×Ｐ，５×Ｐ）＝２１×Ｐが処理され、変数Ｔに２１×Ｐが登録される。
以上でステップＳ０７〜Ｓ１３の処理が終了する。最後にステップＳ１４において変数Ｔの値２１×Ｐが出力される。このようにウィンドウ法では、あらかじめ作成したテーブルを用いてスカラー倍算ｄ×Ｐを計算するのである。
さて、点のスカラー倍算にＡｌｇｏｒｉｔｈｍ ６（ウィンドウ法）を使用する場合には、ｄのビット値に応じて行なわれたり行なわれなかったりするような処理が無いので、バイナリ法と比較して一般にＳＰＡに対して安全であるといわれている。しかし、ウィンドウ法は、バイナリ法と同様に、ＤＰＡに対しては安全ではなく、文献Ｃｏｒｏｎ９９に開示された手法で解析可能であるが、かかるＤＰＡに対しては、バイナリ法やモンゴメリ・ラダーと同様に、ＲＰＣやＲＣが有効であることが知られている。以下に、Ａｌｇｏｒｉｔｈｍ ６に対してＲＰＣを施したアルゴリズム例をＡｌｇｏｒｉｔｈｍ ６′に、又、Ａｌｇｏｒｉｔｈｍ ６にＲＣを施したアルゴリズム例をＡｌｇｏｒｉｔｈｍ ６″に示す。
ここで、ｄはｎビットのスカラー値で、ｎは４の倍数と仮定する。またｄ［ｉ，ｉ−３］はｄの下位ｉビット目から（ｉ−３）ビットまでの４ビット値とする。Ｔ′は一時変数、Ｗ’［ｉ］はウィンドウ法で使用するテーブル、ｉｎｖＲＰＣはＲＰＣ表現からの逆変換を示す。
ここで、ｄはｎビットのスカラー値で、ｎは４の倍数と仮定する。またｄ［ｉ，ｉ−３］はｄの下位ｉビット目から（ｉ−３）ビットまでの４ビット値とする。Ｔ″は一時変数、Ｗ”［ｉ］はウィンドウ法で使用するテーブル、ｉｎｖＲＣはＲＣ表現からの逆変換を示す。
さて、ＳＰＡとＤＰＡとの双方に対しては、従来、前述したＡｌｇｏｒｉｔｈｍ ３′〜６′やＡｌｇｏｒｉｔｈｍ ３″〜６″を用いれば安全であるとされていた。しかしながら、最近、Ｌ．Ｇｏｕｂｉｎ，“Ａ Ｒｅｆｉｎｅｄ Ｐｏｗｅｒ−Ａｎａｌｙｓｉｓ Ａｔｔａｃｋ ｏｎ Ｅｌｌｉｐｔｉｃ Ｃｕｒｖｅ Ｃｒｙｐｔｏｓｙｓｔｅｍ”，Ｐｕｂｌｉｃ−Ｋｅｙ Ｃｒｙｐｔｏｇｒａｐｈｙ ２００３（ＰＫＣ２００３），Ｌｅｃｔｕｒｅ Ｎｏｔｅｓ ｉｎ Ｃｏｍｐｕｔｅｒ Ｓｃｉｅｎｃｅ ｖｏｌ．２５６７，Ｓｐｒｉｎｇｅｒ−Ｖｅｒｌａｇ，ｐｐ．１９９−２１０，２００３．（文献Ｇｏｕｂｉｎ０３という）において、これらを解析する手法が開示された。
楕円曲線上の点のうち、ｘ座標またはｙ座標が０であるような点を特殊点という。スカラー倍算の途中に特殊点が出現した場合には、ＳＰＡやＤＰＡによって、このような点が中間値として現れたことを容易に検出することができる。文献Ｇｏｕｂｉｎ０３に開示された解析手法においては、あるビットｄ［ｉ］に対応する計算の終了時に特殊点が現れるようなベースポイントを人工的に生成し、実際に特殊点が検出されるかどうかによってｄ［ｉ］の値を推定するようになっている。以下、便宜上、この文献Ｇｏｕｂｉｎ０３の解析手法を用いた攻撃を特殊点攻撃と呼ぶ。
この特殊点攻撃に対し、バイナリ法やモンゴメリ・ラダーは安全でない。又、ＲＰＣやＲＣを用いたとしても、座標値が０になるという性質は保持されてしまうので、Ａｌｇｏｒｉｔｈｍ ３′〜６′やＡｌｇｏｒｉｔｈｍ ３″〜６″も特殊点攻撃に対して安全であるとはいえない。
なお、Ａｌｇｏｒｉｔｈｍ ３〜６についてのＤＰＡに対する他の対策として、Ｃ．Ｃｌａｖｉｅｒ，ａｎｄ Ｍ．Ｊｏｙｅ，”Ｕｎｉｖｅｒｓａｌ ｅｘｐｏｎｅｎｔｉａｔｉｏｎ ａｌｇｏｒｉｔｈｍ −−Ａ ｆｉｒｓｔ ｓｔｅｐ ｔｏｗａｒｄｓ ｐｒｏｖａｂｌｅ ＳＰＡ−ｒｅｓｉｓｔａｎｃｅ−−”，Ｃｒｙｐｔｏｇｒａｐｈｉｃ Ｈａｒｄｗａｒｅ ａｎｄ Ｅｍｂｅｄｄｅｄ Ｓｙｓｔｅｍｓ ２００１（ＣＨＥＳ２００１），Ｌｅｃｔｕｒｅ Ｎｏｔｅｓ ｉｎ Ｃｏｍｐｕｔｅｒ Ｓｃｉｅｎｃｅ ｖｏｌ．２１６２，Ｓｐｒｉｎｇｅｒ−Ｖｅｒｌａｇ，ｐｐ．３００−３０８，２００１．（文献Ｃｌａｖｉｅｒ−Ｊｏｙｅ０１という）にて提案されているエクスポーネント・スプリッティング（ｅｘｐｏｎｅｎｔ−ｓｐｌｉｔｔｉｎｇ；ＥＳ）がある。このＥＳはスカラー値をランダムに変化させる手法であって、乱数ｒによって、スカラーｄをｄ＝ｒ＋（ｄ−ｒ）に分割して、２つのスカラー倍算ｒ×Ｐと（ｄ−ｒ）×Ｐとを別々に計算し、
ｒ×Ｐ＋（ｄ−ｒ）×Ｐ＝ｄ×Ｐ
が成り立つという性質を利用して、２つのスカラー倍算の結果を足しあわせることでｄ×Ｐを計算するものである。
ここで、２つのスカラー倍算ｒ×Ｐおよび（ｄ−ｒ）×Ｐには、他のＳＰＡ／ＤＰＡに耐性を有するアルゴリズムを用いる。特殊点攻撃に対しては、スカラー値がランダムに変化するために防御が可能となる。ＥＳのアルゴリズム例をＡｌｇｏｒｉｔｈｍ ７に示す。
ここでｒａｎｄｏｍ（）はｎビットの乱数を生成する関数である。又、ｓｃａｌａｒ（ｄ，Ｐ）はスカラー倍算ｄ×Ｐを計算する関数であって、具体的には、前述したＡｌｇｏｒｉｔｈｍ ３′〜６′やＡｌｇｏｒｉｔｈｍ ３″〜６″等を用いて計算される。また変数ｒ，Ｔ，Ｔ１，Ｔ２はいずれも一時変数である。
ＥＳは、ＳＰＡ，ＤＰＡおよび特殊点攻撃に対して安全といえるが、ＥＳで使用するスカラー倍算はその手法単独でＳＰＡ対策，ＤＰＡ対策であるので、既にＳＰＡ対策とＤＰＡ対策済のＡｌｇｏｒｉｔｈｍ ３′〜６′やＡｌｇｏｒｉｔｈｍ ３″〜６″に適用するには無駄が多い。特に、これらの手法を適用すると、楕円曲線上の点の加算および２倍算を、適用前と比較して余分に処理しなければならず、処理オーバーヘッドが大きくなる欠点がある。
本発明は、このような課題に鑑み創案されたもので、特定点攻撃に対して秘密情報の推定を困難にし、暗号処理の安全性を高めることが可能な楕円曲線暗号装置，楕円曲線暗号方法，楕円曲線暗号プログラムおよび同プログラムを記録したコンピュータ読取可能な記録媒体を提供することを目的とする。
【非特許文献１】（文献Ｃｏｒｏｎ９９） Ｊｅａｎ−Ｓｅｂａｓｔｅｉｎ Ｃｏｒｏｎ“Ｒｅｓｉｓｔａｎｃｅ ａｇａｉｎｓｔ Ｄｉｆｆｅｒｅｎｔｉａｌ Ｐｏｗｅｒ Ａｎａｌｙｓｉｓ ｆｏｒ Ｅｌｌｉｐｔｉｃ Ｃｕｒｖｅ Ｃｒｙｔｏｓｙｓｔｅｍｓ”，Ｃｒｙｐｔｏｇｒａｐｈｉｃ Ｈａｒｄｗａｒｅ ａｎｄ Ｅｍｂｅｄｄｅｄ Ｓｙｓｔｅｍｓ １９９９（ＣＨＥＳ１９９９），Ｌｅｃｔｕｒｅ Ｎｏｔｅｓ ｉｎ Ｃｏｍｐｕｔｅｒ Ｓｃｉｅｎｃｅ ｖｏｌ．１７１７，Ｓｐｒｉｎｇｅｒ−Ｖｅｒｌａｇ，ｐｐ．２９２−３０２，１９９９
【非特許文献２】（文献Ｉｚｕ−Ｔａｋａｇｉ０２） Ｔ．Ｉｚｕ，ａｎｄ Ｔ．Ｔａｋａｇｉ，”Ａ Ｆａｓｔ Ｐａｒａｌｌｅｌ Ｅｌｌｉｐｔｉｃ Ｃｕｒｖｅ Ｍｕｌｔｉｐｌｉｃａｔｉｏｎ Ｒｅｓｉｓｔａｎｔ ａｇａｉｎｓｔ Ｓｉｄｅ Ｃｈａｎｎｅｌ Ａｔｔａｃｋｓ”，Ｐｕｂｌｉｃ−Ｋｅｙ Ｃｒｙｐｔｏｇｒａｐｈｙ ２００２（ＰＫＣ２００２），Ｌｅｃｔｕｒｅ Ｎｏｔｅｓ ｉｎ Ｃｏｍｐｕｔｅｒ Ｓｃｉｅｎｃｅ ｖｏｌ．２２７４，ｐｐ．２８０−２９６，Ｓｐｒｉｎｇｅｒ−Ｖｅｒｌａｇ，２００２．
【非特許文献３】（文献Ｊｏｙｅ−Ｔｙｍｅｎ０１） Ｍ．Ｊｏｙｅ，ａｎｄ Ｃ．Ｔｙｍｅｎ，“Ｐｒｏｔｅｃｔｉｏｎｓ ａｇａｉｎｓｔ ｄｉｆｆｅｒｅｎｔｉａｌ ａｎａｌｙｓｉｓ ｆｏｒ ｅｌｌｉｐｔｉｃ ｃｕｒｖｅ ｃｒｙｐｔｏｇｒａｐｈｙ”，Ｃｒｙｐｔｏｇｒａｐｈｉｃ Ｈａｒｄｗａｒｅ ａｎｄ Ｅｍｂｅｄｄｅｄ Ｓｙｓｔｅｍｓ ２００１（ＣＨＥＳ２００１），Ｌｅｃｔｕｒｅ Ｎｏｔｅｓ ｉｎ Ｃｏｍｐｕｔｅｒ Ｓｃｉｅｎｃｅ ｖｏｌ．２１６２，ｐｐ．３７７−３９０，Ｓｐｒｉｎｇｅｒ−Ｖｅｒｌａｇ，２００１．
【非特許文献４】（文献Ｇｏｕｂｉｎ０３） Ｌ．Ｇｏｕｂｉｎ，“Ａ Ｒｅｆｉｎｅｄ Ｐｏｗｅｒ−Ａｎａｌｙｓｉｓ Ａｔｔａｃｋ ｏｎ Ｅｌｌｉｐｔｉｃ Ｃｕｒｖｅ Ｃｒｙｐｔｏｓｙｓｔｅｍ”，Ｐｕｂｌｉｃ−Ｋｅｙ Ｃｒｙｐｔｏｇｒａｐｈｙ ２００３（ＰＫＣ２００３），Ｌｅｃｔｕｒｅ Ｎｏｔｅｓ ｉｎ Ｃｏｍｐｕｔｅｒ Ｓｃｉｅｎｃｅ ｖｏｌ．２５６７，Ｓｐｒｉｎｇｅｒ−Ｖｅｒｌａｇ，ｐｐ．１９９−２１０，２００３．
【非特許文献５】（文献Ｃｌａｖｉｅｒ−Ｊｏｙｅ０１） Ｃ．Ｃｌａｖｉｅｒ，ａｎｄ Ｍ．Ｊｏｙｅ，”Ｕｎｉｖｅｒｓａｌ ｅｘｐｏｎｅｎｔｉａｔｉｏｎ ａｌｇｏｒｉｔｈｍ −−Ａ ｆｉｒｓｔ ｓｔｅｐ ｔｏｗａｒｄｓ ｐｒｏｖａｂｌｅ ＳＰＡ−ｒｅｓｉｓｔａｎｃｅ−−”，Ｃｒｙｐｔｏｇｒａｐｈｉｃ Ｈａｒｄｗａｒｅ ａｎｄ Ｅｍｂｅｄｄｅｄ Ｓｙｓｔｅｍｓ ２００１（ＣＨＥＳ２００１），Ｌｅｃｔｕｒｅ Ｎｏｔｅｓ ｉｎ Ｃｏｍｐｕｔｅｒ Ｓｃｉｅｎｃｅ ｖｏｌ．２１６２，Ｓｐｒｉｎｇｅｒ−Ｖｅｒｌａｇ，ｐｐ．３００−３０８，２００１．
【発明の開示】
上記の目的を達成するために、本発明の楕円曲線暗号装置は、楕円曲線暗号処理を行なう楕円曲線暗号装置であって、有限体ＧＦ（ｐ＾ｍ）上における楕円曲線上の点Ｐの座標（Ｘ：Ｙ：Ｚ）を座標（ｒ１×（Ｘ−ｓ１）：ｒ２×（Ｙ−ｓ２）：ｒ３×（Ｚ−ｓ３））に変換する座標変換部（ただし、ｐは素数、ｍは１以上の整数、ｒ１，ｒ２，ｒ３はいずれも１以上且つ（ｐ−１）以下の整数、ｓ１，ｓ２，ｓ３はいずれも０以上且つ（ｐ−１）以下の整数、又、符号＾はべき乗を表わす）と、この座標変換部によって変換された楕円曲線上の点のスカラー倍算を行なうスカラー倍算演算部とをそなえ、パラメーターｓ１，ｓ２，ｓ３のうち少なくとも１つが０以外の値を有することを特徴としている。
なお、スカラー倍算演算部が、アド・アンド・ダブル・オールウェイズを用いたバイナリメソッドで、スカラー倍算を行なってもよく、又、モンゴメリ・ラダー法でスカラー倍算を行なってもよく、更に、ウィンドウ・メソッドでスカラー倍算を行なってもよい。
また、スカラー倍算演算部が、ｘ座標法でスカラー倍算を行なってもよく、連続楕円２倍算を用いてスカラー倍算を行なってもよい。
さらに、本発明の楕円曲線暗号方法は、楕円曲線暗号処理を行なう楕円曲線暗号方法であって、有限体ＧＦ（ｐ＾ｍ）上における楕円曲線上の点Ｐの座標（Ｘ：Ｙ：Ｚ）を座標（ｒ１×（Ｘ−ｓ１）：ｒ２×（Ｙ−ｓ２）：ｒ３×（Ｚ−ｓ３））に変換する座標変換ステップ（ただし、ｐは素数、ｍは１以上の整数、ｒ１，ｒ２，ｒ３はいずれも１以上且つ（ｐ−１）以下の整数、ｓ１，ｓ２，ｓ３はいずれも０以上且つ（ｐ−１）以下の整数、又、符号＾はべき乗を表わす）と、この座標変換ステップにおいて変換された楕円曲線上の点のスカラー倍算を行なうスカラー倍算演算ステップとをそなえ、パラメーターｓ１，ｓ２，ｓ３のうち少なくとも１つが０以外の値を有することを特徴としている。
なお、スカラー倍算演算ステップにおいて、アド・アンド・ダブル・オールウェイズを用いたバイナリメソッドでスカラー倍算を行なってもよく、又、スカラー倍算演算ステップにおいてモンゴメリ・ラダー法でスカラー倍算を行なってもよく、更に、スカラー倍算演算ステップにおいて、ウィンドウ・メソッドでスカラー倍算を行なってもよい。
また、スカラー倍算演算ステップにおいて、ｘ座標法でスカラー倍算を行なってもよく、又、スカラー倍算演算ステップにおいて、連続楕円２倍算を用いてスカラー倍算を行なってもよい。
さらに、本発明の楕円曲線暗号プログラムは、楕円曲線暗号処理を行なう楕円曲線暗号プログラムであって、有限体ＧＦ（ｐ＾ｍ）上における楕円曲線上の点Ｐの座標（Ｘ：Ｙ：Ｚ）を座標（ｒ１×（Ｘ−ｓ１）：ｒ２×（Ｙ−ｓ２）：ｒ３×（Ｚ−ｓ３））に変換する座標変換部（ただし、ｐは素数、ｍは１以上の整数、ｒ１，ｒ２，ｒ３はいずれも１以上且つ（ｐ−１）以下の整数、ｓ１，ｓ２，ｓ３はいずれも０以上且つ（ｐ−１）以下の整数であり、且つ、これらのｓ１，ｓ２，ｓ３のうち少なくとも１つが０以外の値を有する。又、符号＾はべき乗を表わす）と、座標変換部によって変換された楕円曲線上の点のスカラー倍算を行なうスカラー倍算演算部としてコンピュータを機能させることを特徴としている。
なお、スカラー倍算演算部としてコンピュータを機能させる際に、アド・アンド・ダブル・オールウェイズを用いたバイナリメソッドでスカラー倍算を行なってもよく、又、スカラー倍算演算部としてコンピュータを機能させる際に、モンゴメリ・ラダー法でスカラー倍算を行なってもよく、更に、スカラー倍算演算部としてコンピュータを機能させる際に、ウィンドウ・メソッドでスカラー倍算を行なってもよい。
また、スカラー倍算演算部としてコンピュータを機能させる際に、ｘ座標法でスカラー倍算を行なってもよく、又、スカラー倍算演算部としてコンピュータを機能させる際に、連続楕円２倍算を用いてスカラー倍算を行なってもよい。
そして、本発明のコンピュータ読取可能な記録媒体は、上述した楕円曲線暗号プログラムを記録したものである。
このように、本発明の楕円曲線暗号装置，楕円曲線暗号方法，楕円曲線暗号プログラムおよび同プログラムを記録したコンピュータ読取可能な記録媒体によれば、以下の効果ないし利点がある。
（１）有限体ＧＦ（ｐ＾ｍ）上における楕円曲線上の点Ｐの座標（Ｘ：Ｙ：Ｚ）を座標（ｒ１×（Ｘ−ｓ１）：ｒ２×（Ｙ−ｓ２）：ｒ３×（Ｚ−ｓ３））に変換（ただし、ｐは素数、ｍは１以上の整数、ｒ１，ｒ２，ｒ３はいずれも１以上且つ（ｐ−１）以下のランダムな整数、ｓ１，ｓ２，ｓ３はいずれも０以上且つ（ｐ−１）以下のランダムな整数であり、且つ、これらのｓ１，ｓ２，ｓ３のうち少なくとも１つが０以外の値を有する。又、符号＾はべき乗を表わす）し、この変換された楕円曲線上の点のスカラー倍算を行なうので、楕円曲線暗号におけるスカラー倍算を、サイドチャネル攻撃に対する耐性をもって計算することが可能となる。
（２）特に、ｓ１，ｓ２，ｓ３のうち少なくとも１つが０以外の値を有するので、特殊点の線型変換座標での座標が０以外の値となり、スカラー倍算の途中で出現することがなく、これにより特殊点攻撃に対して安全である。
（３）アド・アンド・ダブル・オールウェイズを用いたバイナリメソッドで、スカラー倍算を行なうことにより、ＳＰＡおよびＤＰＡに対して安全である。
（４）ヤコビアン座標におけるＲＰＣと同様のランダム効果が期待でき、ＤＰＡに対しても安全である。
（５）モンゴメリ・ラダー法で前記スカラー倍算を行なうことにより、ＳＰＡおよびＤＰＡに対して安全である。
（６）ｘ座標法で前記スカラー倍算を行なうことにより、ＳＰＡおよびＤＰＡに対して安全であり、さらに計算時間を短縮することができる。
（７）ウィンドウ・メソッドで前記スカラー倍算を行なうことにより、ＳＰＡおよびＤＰＡに対して安全である。
（８）連続楕円２倍算を用いて前記スカラー倍算を行なうことにより、高速に演算を行なうことができる。
【図面の簡単な説明】
図１は楕円加算を説明するための図である。
図２は楕円２倍算を説明するための図である。
図３は本発明に係る楕円曲線暗号装置の要部の構成を示す図である。
図４は本発明の一実施形態としての楕円曲線暗号装置の機能構成を示すブロック図である。
図５は本発明の楕円曲線暗号プログラムを実行する楕円曲線暗号装置のハードウェア構成の一例を示す図である。
【発明を実施するための最良の形態】
以下、図面を参照して本発明の実施の形態を説明する。
（ａ）基本説明
本発明の一実施形態としての楕円曲線暗号装置は、例えば、楕円曲線暗号の専用の情報処理装置，パーソナルコンピュータ，ＩＣカード（スマートカード）等に内蔵されたＩＣチップ，携帯電話機，携帯情報端末装置（ＰＤＡ（Ｐｅｒｓｏｎａｌ ｄａｔａ ａｓｓｉｓｔａｎｔ）等），ＤＶＤプレーヤ等として実現されるものであり、演算を行なうプロセッサを有して構成されるものである。
以下の説明では、本発明にかかる楕円曲線暗号演算方法を、ｐを素数、ｍを１以上の整数とし、要素数ｐ＾ｍの有限体ＧＦ（ｐ＾ｍ）上の楕円曲線に適用した場合について説明する。なお、以下、特に断りの無い限り、小文字（ｄ等）はスカラー値を表わし、大文字（Ｐ，Ｔ等）は楕円曲線上の点を表わすものとする。又、楕円加算をＥＣＡＤＤ、楕円２倍算をＥＣＤＢＬと表わす。更に、符号“＾”はべき乗算を表わすものとし、“（”と“）２”とによって囲まれた数列は２進数で表現された数字を表わす。又、“Ｓ０１：”等のように、Ｓを付した数字はアルゴリズムを表わすプログラム例におけるステップ数を示すものとする。
ＧＦ（ｐ＾ｍ）上の楕円曲線Ｅは、以下の方程式を満たす点（ｘ，ｙ）の集合に、無限遠点（以下、ゼロ点という場合もある）と呼ばれる点∞を加えた集合である。なお、無限遠点∞を０と表すこともある。
Ｅ：ｙ＾２＋ａ１×ｘ×ｙ＋ａ３×ｙ＝ｘ＾３＋ａ２×ｘ＾２＋ａ４×ｘ＋ａ６ここでａ１，ａ２，ａ３，ａ４，ａ６，ｘ，ｙはそれぞれＧＦ（ｐ＾ｍ）の要素である。楕円曲線上の点は（ｘ，ｙ）のような座標形式で表現できるが、無限遠点∞は（ｘ，ｙ）のような座標形式で表現することができない唯一の点である。
ＰをＧＦ（ｐ＾ｍ）上の楕円曲線Ｅ上の点とし、以下のようにＰの逆元−Ｐを定義する。
（１）Ｐ＝∞ならば、−Ｐ＝∞
（２）Ｐ≠∞ならば、Ｐ＝（ｘ，ｙ）としたときに、
−Ｐ＝（ｘ，−ｙ−ａ１×ｘ−ａ３）
また、Ｐ１，Ｐ２をＧＦ（ｐ＾ｍ）上の楕円曲線Ｅ上の２点とし、以下に示すようにＰ１とＰ２との和Ｐ３＝Ｐ１＋Ｐ２を定義する。
（１）Ｐ１＝∞ならば、Ｐ３＝Ｐ２
（２）Ｐ２＝∞ならば、Ｐ３＝Ｐ１
（３）Ｐ１＝−Ｐ２ならば、Ｐ３＝∞
（４）Ｐ１≠−Ｐ２ならばＰ１＝（ｘ１，ｙ１），Ｐ２＝（ｘ２，ｙ２），Ｐ３＝（ｘ３，ｙ３）としたときに、
ｘ３＝λ＾２＋ａ１×λ−ａ２−ｘ１−ｘ２，
ｙ３＝−（λ＋ａ１）×ｘ３−ν−ａ３，
ただし、
Ｐ１≠Ｐ２のとき
λ＝（ｙ２−ｙ１）／（ｘ２−ｘ１）
ν＝（ｙ１×ｘ２−ｙ２×ｘ１）／（ｘ２−ｘ１）
Ｐ１＝Ｐ２のとき
λ＝（３×ｘ１＾２＋２×ａ２×ｘ＋ａ４−ａ１×ｙ１）／（２×ｙ１＋ａ１×ｘ１＋ａ３）
ν＝（−ｘ１＾３＋ａ４×ｘ１＋２×ａ６−ａ３×ｙ１）／（２×ｙ１＋ａ１×ｘ１＋ａ３）
と定める。
Ｐ１≠Ｐ２のときに、Ｐ１＋Ｐ２を計算することを楕円加算（ＥＣＡＤＤ）、Ｐ１＝Ｐ２のときにＰ１＋Ｐ２＝２×Ｐ１を計算することを楕円２倍算（ＥＣＤＢＬ）という。楕円加算・楕円２倍算は、有限体ＧＦ（ｐ＾ｍ）での加減算・乗算・平方算・逆元計算の組み合わせによって計算される。
ｐを素数とするとき、有限体ＧＦ（ｐ）を素体という。特に、ｐが５以上の素数の場合には、素体ＧＦ（ｐ）上の楕円曲線Ｅは、方程式
Ｅ：ｙ＾２＝ｘ＾３＋ａ×ｘ＋ｂ
を満たす点（ｘ，ｙ）の集合上に、無限遠点と呼ばれる点∞を加えた集合である。なお、無限遠点∞を０と表すこともある。又、ａ，ｂ，ｘ，ｙはそれぞれＧＦ（ｐ）の要素である。楕円曲線上の点は（ｘ，ｙ）のような座標形式で表現できるが、無限遠点∞は（ｘ，ｙ）のような座標形式で表現することができない唯一の点である。
ＰをＧＦ（ｐ）上の楕円曲線Ｅ上の点とし、以下に示すようにＰの逆元−Ｐを定義する。
（１）Ｐ＝∞ならば、−Ｐ＝∞
（２）Ｐ≠∞ならば、Ｐ＝（ｘ，ｙ）としたときに、−Ｐ＝（ｘ，−ｙ）
また、Ｐ１，Ｐ２をＧＦ（ｐ）上の楕円曲線Ｅ上の２点とし、以下に示すようにしてＰ１とＰ２との和Ｐ３＝Ｐ１＋Ｐ２を定義する。
（１）Ｐ１＝∞ならば、Ｐ３＝Ｐ２
（２）Ｐ２＝∞ならば、Ｐ３＝Ｐ１
（３）Ｐ１＝−Ｐ２ならば、Ｐ３＝∞
（４）Ｐ１≠−Ｐ２ならば、Ｐ１＝（ｘ１，ｙ１），Ｐ２＝（ｘ２，ｙ２），Ｐ３＝（ｘ３，ｙ３）としたときに、
ｘ３＝λ＾２−ｘ１−ｘ２
ｙ３＝−λ×ｘ３−ν，
ただし
Ｐ１≠Ｐ２のとき
λ＝（ｙ２−ｙ１）／（ｘ２−ｘ１）
ν＝（ｙ１×ｘ２−ｙ２×ｘ１）／（ｘ２−ｘ１）
Ｐ１＝Ｐ２のとき
λ＝（３×ｘ１＾２＋ａ）／（２×ｙ１）
ν＝（−ｘ１＾３＋ａ×ｘ１＋２×ｂ）／（２×ｙ１）
と定める。
Ｐ１≠Ｐ２のときに、Ｐ１＋Ｐ２を計算することを楕円加算（ＥＣＡＤＤ）、Ｐ１＝Ｐ２のときにＰ１＋Ｐ２＝２×Ｐ１を計算することを楕円２倍算（ＥＣＤＢＬ）という。楕円加算・楕円２倍算は、有限体ＧＦ（ｐ）での加減算・乗算・平方算・逆元計算の組み合わせによって計算される。
図１は楕円加算を説明するための図、図２は楕円２倍算を説明するための図である。楕円加算は、図１に示すように、楕円曲線上の点Ｐ１＝（ｘ１，ｙ１）とＰ２＝（ｘ２，ｙ２）とを結ぶ直線と楕円曲線との交点を、ｘ軸で折り返した点Ｐ３＝Ｐ１＋Ｐ２＝（ｘ３，ｙ３）として定義される。楕円２倍算は、図２に示されるように、楕円曲線上の点Ｐ１＝（ｘ１，ｙ１）の接線と楕円曲線との交点を、ｘ軸で折り返した点Ｐ４＝Ｐ１＋Ｐ１＝２×Ｐ１＝（ｘ４，ｙ４）として定義される。
有限体上の楕円曲線Ｅと、ベースポイントと呼ばれる曲線上の点Ｐと、スカラーと呼ばれる整数ｄとに対して、点ｄ×Ｐ＝Ｐ＋Ｐ＋…＋Ｐ（ｄ個の和）を計算することをスカラー倍算という。スカラー倍算は、楕円加算、楕円２倍算の組み合わせによって実現される。
楕円加算、楕円２倍算、スカラー倍算の計算時間は、有限体における乗算、平方算、逆元計算の計算時間の和によって見積もられることが多い。これは実際の楕円加算、楕円２倍算、スカラー倍算の計算が、有限体における加減算・乗算・平方算・逆元計算の組み合わせで計算され、多くの場合、加減算の計算時間はその他の計算時間に比べて無視できるほど短いからである。
一般に有限体ＧＦ（ｐ＾ｍ）での逆元計算の計算時間は、乗算・平方算の計算時間に比べて非常に大きくなる。このため、本発明の楕円曲線暗号装置においては、楕円曲線の点を表現する上で線形座標を使用するようになっている。
本発明で使用する線型変換座標においては、ＧＦ（ｐ＾ｍ）上の楕円曲線の点は（Ｘ：Ｙ：Ｚ）のような３つの要素の組み合わせで表される。ただし、ＧＦ（ｐ＾ｍ）の要素ｒ１≠０、ｒ２≠０、ｒ３≠０、ｓ１、ｓ２、ｓ３に対して、（Ｘ：Ｙ：Ｚ）と（ｒ１×（Ｘ−ｓ１）：ｒ２×（Ｙ−ｓ２）：ｒ３×（Ｚ−ｓ３））とが同じ点と考える。
そして、本楕円曲線暗号装置１１においては、線形変換座標は、有限体上における楕円曲線上の点Ｐの座標（Ｘ：Ｙ：Ｚ）を座標（ｒ１×（Ｘ−ｓ１）：ｒ２×（Ｙ−ｓ２）：ｒ３×（Ｚ−ｓ３））に変換するものであって、ｒ１，ｒ２，ｒ３はそれぞれ０以外の任意の整数であり、ｓ１，ｓ２，ｓ３の少なくともいずれか１つが０以外の整数である。なお、以下、これらのｒ１，ｒ２，ｒ３，ｓ１，ｓ２，ｓ３を線型変換座標のパラメータという場合もある。
線型変換座標を用いると、楕円曲線上の全ての点は（Ｘ：Ｙ：Ｚ）のような座標形式で表現することができる。又、無限遠点は∞＝（０：１：０）となる。
なお、線型変換座標のパラメータを（ｒ１，ｒ２，ｒ３，ｓ１，ｓ２，ｓ３）と表わす場合に、
（ｒ１，ｒ２，ｒ３，ｓ１，ｓ２，ｓ３）＝（ｒ，ｒ，ｒ，０，０，０）
とした場合に、射影座標として用いることができ、又、
（ｒ１，ｒ２，ｒ３，ｓ１，ｓ２，ｓ３）＝（ｒ＾２，ｒ＾３，ｒ，０，０，０）
とした場合に、ヤコビアン座標として用いることができる。
以下、本発明に係る楕円曲線暗号演算方法を、ｐを５以上の素数とし、要素数ｐの有限体ＧＦ（ｐ）（ｐは５以上の素数）上の楕円曲線に適用した場合について説明する。
ＧＦ（ｐ）上の楕円曲線Ｅは、以下の式で表わすことができる。
Ｅ：ｙ＾２＝ｘ＾３＋ａ×ｘ＋ｂ
ここでａ，ｂ，ｘ，ｙはＧＦ（ｐ）の要素で、４×ａ＾３＋２７×ｂ＾２≠０を満たす。
図３は本発明に係る楕円曲線暗号装置１１の要部の構成を示す図である。本楕円曲線暗号装置１１は、図３に示すように、演算部（プロセッサ）１２と記憶１６とをそなえて構成されている。記憶部１５は、後述する楕円曲線暗号の楕円加算，楕円２倍算，楕円２＾ｋ倍算等の演算プログラムを記憶するものである。
演算部１２は、演算器１３，レジスタ群１４および演算結果出力レジスタ群１５をそなえて構成されている。演算器１３は、記憶部１６に格納された楕円曲線暗号プログラムをレジスタ群１４を用いて実行するものであって、その演算結果を演算結果出力レジスタ群１５に出力するようになっている。
レジスタ群１４および演算結果出力レジスタ群１５は、いずれも複数のレジスタからなり、これらのレジスタに、演算を行なうための数値や、演算実行後の結果，現在実行しているコードのメモリアドレス、ＣＰＵの状態などを格納するものであり、演算結果出力レジスタ群１５には、特に演算器１３による演算結果が格納されるようになっている。
図４は本発明の一実施形態としての楕円曲線暗号装置１１の機能構成を示すブロック図である。本楕円曲線暗号装置１１は、図４に示すように、ゼロ点判定部２１，スカラー倍算処理部２２，線形座標変換部（座標変換部）２３および乱数生成部２４をそなえて構成されている。
乱数生成部２４は、乱数ｒ１，ｒ２，ｒ３を生成するものであり、生成した乱数ｒ１，ｒ２，ｒ３をスカラ倍算処理部２２および線形座標変換部２３に渡すようになっている。
ゼロ点判定部２１は、スカラー倍算の結果がゼロ点（無限遠点）であるか否かを判定するものである。
線形座標変換部２３は、有限体ＧＦ（ｐ）上における楕円曲線上の点Ｐの座標（Ｘ：Ｙ：Ｚ）を座標（ｒ１×（Ｘ−ｓ１）：ｒ２×（Ｙ−ｓ２）：ｒ３×（Ｚ−ｓ３））に変換（線形座標変換）するものであり、変換後の座標（以下、線形変換座標という場合もある）をスカラー倍算処理部２２に渡すようになっている。スカラー倍算処理部２２は、線形座標変換部２３によって変換された楕円曲線上の点のスカラー倍算ｄ×Ｐを演算するものであり、後述する種々のアルゴリズムを用いて楕円加算，楕円２倍算，楕円２＾ｋ倍算等の演算処理を行なうことにより、スカラー倍算を行なうようになっている。
なお、本楕円曲線暗号装置１１においては、例えば、演算部１２が、記憶部１６に記憶されたプログラムを実行することにより、ゼロ点判定部２１，スカラー倍算処理部２２，線形座標変換部２３および乱数生成部２４として機能するようになっている。
そして、スカラー倍算処理部２２が、スカラー倍算ｄ×Ｐを計算する際に、この変換後の線型変換座標における楕円加算と楕円２倍算を計算するようになっている。すなわち、スカラー倍算処理部２２は、素体ＧＦ（ｐ）上の楕円曲線Ｅに対して、パラメーター（ｒ１，ｒ２，ｒ３，ｓ１，ｓ２，ｓ３）＝（ｒ＾２，ｒ＾３，ｒ，ｓ，０，０）の線型変換座標における楕円加算（以下、ＬＣＥＣＡＤＤという）と楕円２倍算（以下、ＬＣＥＣＤＢＬという）を計算するようになっているのである。
このときの楕円加算の計算アルゴリズムをＡｌｇｏｒｉｔｈｍ ８に示すとともに、楕円２倍算の計算アルゴリズムをＡｌｇｏｒｉｔｈｍ ９に示す。
（ｂ）第１実施形態の説明
本発明の第１の実施形態としての楕円曲線暗号装置１１は、スカラー倍算処理部２２が、スカラー倍算ｄ×Ｐを計算する際に、バイナリ法（ＬＳＢ，アド・アンド・ダブル・オールウェイズ）を用いるようになっている。以下に、スカラー倍算処理部２２がスカラー倍算に用いるアルゴリズム例をＡｌｇｏｒｉｔｈｍ １０として示す。
なお、本第１実施形態の楕円曲線暗号装置１１においては、線形座標変換部２３は、パラメーター（ｒ１，ｒ２，ｒ３，ｓ１，ｓ２，ｓ３）＝（ｒ＾２，ｒ＾３，ｒ，ｓ，０，０）に基づいて、素体ＧＦ（ｐ）上の楕円曲線Ｅに対して、楕円曲線上の点Ｐの座標（Ｘ：Ｙ：Ｚ）を座標（ｒ１×（Ｘ−ｓ１）：ｒ２×（Ｙ−ｓ２）：ｒ３×（Ｚ−ｓ３））に変換するようになっている。すなわち、線形座標変換部２３は、楕円曲線上の点Ｐの座標（Ｘ：Ｙ：Ｚ）を座標（ｒ＾２×（Ｘ−ｓ）：ｒ＾３×Ｙ：ｒ×Ｚ）に変換（線形座標変換）するようになっている
ここで、ＬＣは線型写像座標への変換（線形座標変換）、ｉｎｖＬＣはその逆変換を表す。またＴ［０］，Ｔ［１］，Ｔ［２］はいずれも一時変数であり、ｄはｎビットのスカラー値で、ｄ［ｉ］はｄの下位ｉビット目の値である。
すなわち、本第１実施形態の楕円曲線暗号装置１１においては、演算部１２が上述したＡｌｇｏｒｉｔｈｍ １０のステップＳ１およびＳ２を実行することにより線形座標変換部２３として機能し、ステップＳ３〜ステップＳ７を実行することにより、スカラー処理部２２として機能するようになっているのである。
本発明の第１実施形態としての楕円曲線暗号装置１１によれば、線形座標変換部２３が、パラメーター（ｒ１，ｒ２，ｒ３，ｓ１，ｓ２，ｓ３）＝（ｒ＾２，ｒ＾３，ｒ，ｓ，０，０）に基づいて、素体ＧＦ（ｐ）上の楕円曲線Ｅに対して、楕円曲線上の点Ｐの座標（Ｘ：Ｙ：Ｚ）を座標（ｒ１×（Ｘ−ｓ１）：ｒ２×（Ｙ−ｓ２）：ｒ３×（Ｚ−ｓ３））に変換し、スカラー倍算処理部２２が、この変換後の線型変換座標における楕円加算と楕円２倍算を計算するので、ｓ≠０とすることにより、ｘ座標が０であるような特殊点は、線型変換座標でのＸ座標がｓの点として表され、スカラー倍算の途中で出現することがない。これにより特殊点攻撃に対して安全である。
また、スカラー倍算処理部２２が用いるＡｌｇｏｒｉｔｈｍ １０において、アド・アンド・ダブル・オールウェイズを用いているので、ＳＰＡおよびＤＰＡに対して安全である。
さらに、線形座標変換部２３が、パラメーター（ｒ１，ｒ２，ｒ３，ｓ１，ｓ２，ｓ３）＝（ｒ＾２，ｒ＾３，ｒ，ｓ，０，０）に基づいて、素体ＧＦ（ｐ）上の楕円曲線Ｅに対して、楕円曲線上の点Ｐの座標（Ｘ：Ｙ：Ｚ）を座標（ｒ１×（Ｘ−ｓ１）：ｒ２×（Ｙ−ｓ２）：ｒ３×（Ｚ−ｓ３））に変換し、スカラー倍算処理部２２が、この変換後の線型変換座標における楕円加算と楕円２倍算を計算するので、ヤコビアン座標におけるＲＰＣと同様のランダム効果が期待でき、ＤＰＡに対しても安全である。
（ｃ）第２実施形態の説明
前述した第１実施形態の楕円曲線暗号装置１１で用いられるＡｌｇｏｒｉｔｈｍ １０においては、変数Ｔ［２］に保管される値はｄとは無関係であり、そのステップＳ５以外では値が変更されることはない。そこでバイナリ法（ＬＳＢ，アド・アンド・ダブル・オールウェイズ）の変形として、以下のＡｌｇｏｒｉｔｈｍ １１に示すアルゴリズム例によって表わされる変形アド・アンド・ダブル・オールウェイズを適用することもできる。
本発明の第２実施形態としての楕円曲線暗号装置１１においては、スカラー倍算ｄ×Ｐを計算する際に、アド・アンド・ダブル・オールウェイズに代えてＡｌｇｏｒｉｔｈｍ １１に示すような変形アド・アンド・ダブル・オールウェイズを用いるようになっており、それ以外の部分については前述した第１実施形態の楕円曲線暗号装置１１とほぼ同様に構成されている。以下に、スカラー倍算処理部２２がスカラー倍算に用いるアルゴリズム例をＡｌｇｏｒｉｔｈｍ １１として示す。
ここで、ＬＣは線型写像座標への変換、ｉｎｖＬＣはその逆変換を表す。又、Ｔ［０］，Ｔ［１］，Ｔ［２］はいずれも一時変数、ｄはｎビットのスカラー値で、ｄ［ｉ］はｄの下位ｉビット目の値である。なお、ステップＳ０６とステップＳ１０とで使用される一時変数は共用されるものとする。
本第２実施形態の楕円曲線暗号装置１１においては、演算部１２が上述したＡｌｇｏｒｉｔｈｍ １１のステップＳ０１およびＳ０２を実行することにより線形座標変換部２３として機能し、ステップＳ０３〜ステップＳ１２を実行することにより、スカラー処理部２２として機能するようになっているのである。
本発明の第２実施形態の楕円曲線暗号装置１１によれば、スカラー倍算処理部２２が用いるＡｌｇｏｒｉｔｈｍ １１において、変形アド・アンド・ダブル・オールウェイズを用いているので、ＳＰＡに対して安全である。
また、線形座標変換部２３が、パラメーター（ｒ１，ｒ２，ｒ３，ｓ１，ｓ２，ｓ３）＝（ｒ＾２，ｒ＾３，ｒ，ｓ，０，０）に基づいて、素体ＧＦ（ｐ）上の楕円曲線Ｅに対して、楕円曲線上の点Ｐの座標（Ｘ：Ｙ：Ｚ）を座標（ｒ１×（Ｘ−ｓ１）：ｒ２×（Ｙ−ｓ２）：ｒ３×（Ｚ−ｓ３））に変換し、スカラー倍算処理部２２が、この変換後の線型変換座標における楕円加算と楕円２倍算を計算するので、ヤコビアン座標におけるＲＰＣと同様のランダム効果が期待でき、ＤＰＡに対しても安全である。
さらに、上記パラメータにおいてｓ≠０であるので、ｘ座標が０であるような特殊点は、線型変換座標でのＸ座標がｓとなり、スカラー倍算の途中で出現しない。これにより特殊点攻撃に対しても安全である。
（ｄ）第３実施形態の説明
本発明の第３実施形態としての楕円曲線暗号装置１１は、線形座標変換部２３が、パラメーター（ｒ１，ｒ２，ｒ３，ｓ１，ｓ２，ｓ３）＝（ｒ，ｒ，ｒ，ｓ，０，０）に基づいて、素体ＧＦ（ｐ）上の楕円曲線Ｅに対して、楕円曲線上の点Ｐの座標（Ｘ：Ｙ：Ｚ）を座標（ｒ１×（Ｘ−ｓ１）：ｒ２×（Ｙ−ｓ２）：ｒ３×（Ｚ−ｓ３））に変換する線形座標変換を行なうようになっており、更に、スカラー倍算処理部２２が、ｘ座標法を用いて楕円加算と楕円２倍算と楕円加算２倍算とを計算するようになっている。
本第３実施形態においては、スカラー倍算処理部２２がｘ座標法で前記スカラー倍算を行なうので、ＳＰＡおよびＤＰＡに対して安全である他、計算時間を短縮することができる。
また、本実施形態においては、上述の如くパラメーター（ｒ１，ｒ２，ｒ３，ｓ１，ｓ２，ｓ３）＝（ｒ，ｒ，ｒ，ｓ，０，０）を用いるようになっており、これにより、計算時間を短縮することができる。
ここで、ｘ座標法とは、楕円加算・楕円２倍算・楕円加算２倍算をｙ座標を用いずに計算するアルゴリズムである。参考までに、素体上の射影座標で表された楕円曲線に対する、文献Ｉｚｕ−Ｔａｋａｇｉ０２に開示されたｘ座標法のアルゴリズム例を、以下にＡｌｇｏｒｉｔｈｍ １２ｍ，１２ａ，１３，１４ｍ，１４ａとしてそれぞれ示す。なお、アルゴリズムの番号の末尾に付した符号ｍは乗法的（ｍｕｌｔｉｐｌｉｃａｔｉｖｅ）なＥＣＡＤＤを用いることを示すものであり、符号ａは加算的（ａｄｄｉｔｉｖｅ）なＥＣＡＤＤを用いることを示す。
本発明の第３実施形態の楕円曲線暗号装置１１によれば、線形座標変換部２３が、パラメーター（ｒ１，ｒ２，ｒ３，ｓ１，ｓ２，ｓ３）＝（ｒ，ｒ，ｒ，ｓ，０，０）に基づいて、素体ＧＦ（ｐ）上の楕円曲線Ｅに対して、楕円曲線上の点Ｐの座標（Ｘ：Ｙ：Ｚ）を座標（ｒ１×（Ｘ−ｓ１）：ｒ２×（Ｙ−ｓ２）：ｒ３×（Ｚ−ｓ３））に変換し、スカラー倍算処理部２２が、この変換後の線型変換座標における楕円加算と楕円２倍算を計算するので、ヤコビアン座標におけるＲＰＣと同様のランダム効果が期待でき、ＤＰＡに対しても安全である。
また、上記パラメータにおいてｓ≠０であるので、ｘ座標が０であるような特殊点は、線型変換座標でのＸ座標がｓとなり、スカラー倍算の途中で出現しない。これにより特殊点攻撃に対しても安全である。
さらに、上述したＡｌｇｏｒｉｔｈｍ １４ｍ，１４ａによれば、ｘＥＣＡＤＤＤＢＬｍやｘＥＣＡＤＤＤＢＬａを用いることにより、１つの関数で加算と２倍算とを行なうようになっている。これにより、関数の呼び出し回数を低減することができ、処理を高速化することができる。又、加算と２倍算とで演算結果を共有することができるので、計算量も低減することもできる。
（ｅ）第４実施形態の説明
本発明の第４実施形態としての楕円曲線暗号装置１１は、第３実施形態の楕円曲線暗号装置１１におけるスカラー倍算処理部２２が、スカラー倍算ｄ×Ｐを計算する際にモンゴメリ・ラダーを用いるようになっており、その他の部分については第３実施形態の楕円曲線暗号装置１１とほぼ同様に構成されている。以下に、スカラー倍算処理部２２がスカラー倍算に用いるアルゴリズム例をＡｌｇｏｒｉｔｈｍ １５として示す。
ここで、ｘＬＣは線型写像座標におけるｘ座標法で用いる座標への変換であり、ｉｎｖＬＣはその逆変換を表す。又、Ｔ［０］，Ｔ［１］およびＴ［２］はいずれも一時変数、ｄはｎビットのスカラー値で、ｄ［ｉ］はｄの下位ｉビット目の値である。
本発明の第４実施形態としての楕円曲線暗号装置１１によれば、上述した第４実施形態と同様の作用効果を得ることができる他、スカラー倍算処理部２２が用いるＡｌｇｏｒｉｔｈｍ １５において、モンゴメリ・ラダーを用いているので、ＳＰＡおよびＤＰＡに対して安全である。
（ｆ）第５実施形態の説明
本発明の第５実施形態としての楕円曲線暗号装置１１は、スカラー倍算処理部２２が、スカラー倍算ｄ×Ｐを計算する際に改良モンゴメリ・ラダーを用いるようになっており、それ以外の部分は第４実施形態の楕円曲線暗号装置１１とほぼ同様に構成されている。
改良モンゴメリ・ラダーは、上述したＡｌｇｏｒｉｔｈｍ １４ｍ，１４ａと同様に、ｘＥＣＡＤＤＤＢＬを用いることにより、１つの関数で加算と２倍算を行なうことにより、関数の呼び出し回数を低減して処理を高速化することができるものであり、又、加算と２倍算とで演算結果を共有することにより計算量を低減することもできるものである。以下に、スカラー倍算処理部２２がスカラー倍算に用いるアルゴリズム例をＡｌｇｏｒｉｔｈｍ １５′として示す。
ここで、ｘＬＣは線型写像座標におけるｘ座標法で用いる座標への変換であり、ｉｎｖＬＣはその逆変換を表す。又、Ｔ［０］，Ｔ［１］およびＴ［２］はいずれも一時変数、ｄはｎビットのスカラー値で、ｄ［ｉ］はｄの下位ｉビット目の値である。
本発明の第５実施形態としての楕円曲線暗号装置１１によれば、上述した第４実施形態と同様の作用効果を得ることができる他、スカラー倍算処理部２２が用いるＡｌｇｏｒｉｔｈｍ １５′において、ｘＥＣＡＤＤＤＢＬを用いるので、１つの関数で加算と２倍算を行なうことにより、関数の呼び出し回数を低減して処理を高速化することができる他、加算と２倍算とで演算結果を共有することにより計算量を低減することができる。
上述の如く、本発明の各実施形態にかかる楕円曲線暗号装置１１によれば、楕円曲線暗号におけるスカラー倍算を、サイドチャネル攻撃に対する耐性をもって計算することが可能となる。
（ｇ）第６実施形態
本発明の第６実施形態としての楕円曲線暗号装置１１は、スカラー倍算処理部２２が、スカラー倍算ｄ×Ｐを計算する際に、楕円２ｋ（２＾ｋ）倍算（ｉＥＣＤＢＬ）を用いるようになっている。ここで、楕円２ｋ倍算とは、与えられた点の２ｋ倍点２ｋ×Ｐを計算することである。楕円２ｋ倍算は、楕円２倍算をｋ回連続して用いることで計算可能であるが、１つの関数として処理した場合には、中間値の削減によって連続に適用するよりも効率的な計算が可能なことがある。
例えば、Ｋ．Ｉｔｏｈ，Ｍ．Ｔａｋｅｎａｋａ，Ｎ．Ｔｏｒｉｉ，Ｓ．Ｔｅｍｍａ，ａｎｄ Ｙ．Ｋｕｒｉｈａｒａ， ，，Ｆａｓｔ Ｉｍｐｌｅｍｅｎｔａｔｉｏｎ ｏｆ Ｐｕｂｌｉｃ−ｋｅｙ Ｃｒｙｐｔｏｇｒａｐｈｙ ｏｎ ＤＳＰ ＴＭＳ３２０Ｃ６２０１”，Ｃｒｙｐｔｏｇｒａｐｈｉｃ Ｈａｒｄｗａｒｅ ａｎｄ Ｅｍｂｅｄｄｅｄ Ｓｙｓｔｅｍｓ １９９９（ＣＨＥＳ１９９９），Ｌｅｃｔｕｒｅ Ｎｏｔｅｓ ｉｎ Ｃｏｍｐｕｔｅｒ Ｓｃｉｅｎｃｅ ｖｏｌ．１７１７，ｐｐ．６１−７２，Ｓｐｒｉｎｇｅｒ−Ｖｅｒｌａｇ，１９９９．（文献Ｉｔｏｈ＋９９という）には、以下のＡｌｇｏｒｉｔｈｍ １６に示すような、楕円２ｋ倍算を実現するためのアルゴリズムが開示されている。なお、この楕円２ｋ倍算は、素体上でヤコビアン座標で表現された楕円曲線に対して適用可能である。
上述したＡｌｇｏｒｉｔｈｍ １６は、ヤコビアン座標に対して楕円２ｋ倍算を適用したものであるが、このヤコビアン座標に代えて本発明の線形座標変換部２３により行なわれた線形変換座標に対して楕円２ｋ倍算を適用することもでき、これにより、演算速度を向上させることができる。
なお、線形座標変換部２３は、パラメーター（ｒ１，ｒ２，ｒ３，ｓ１，ｓ２，ｓ３）＝（ｒ＾２，ｒ＾３，ｒ，ｓ，０，０）に基づいて線形座標変換を行なってもよく、又、パラメーター（ｒ１，ｒ２，ｒ３，ｓ１，ｓ２，ｓ３）＝（ｒ，ｒ，ｒ，ｓ，０，０）に基づいて線形座標変換を行なってもよい。
（ｈ）その他
次に、上述した本発明の楕円曲線暗号プログラムを実行する楕円曲線暗号装置のハードウェア構成の一例を図５を参照して説明する。楕円暗号装置は、例えば、パーソナルコンピュータ等の情報処理装置により実現できる。
ＣＰＵ（Ｃｅｎｔｒａｌ Ｐｒｏｃｅｓｓｉｎｇ Ｕｎｉｔ）３１は、楕円曲線暗号の楕円加算、楕円２倍算等を実行する。メモリ３２は、演算に使用される各種のレジスタとして使用される。外部記憶装置３３は、ＯＳや、楕円曲線暗号プログラム等が格納される。
媒体駆動装置３４は、ＣＤＲＯＭ、ＤＶＤ、フレキシブルディスク、ＩＣカード等の可搬記録媒体３５の読み取り、あるいは書き込みを行なう装置である。
入力装置３６は、キーボード等のデータを入力する装置である。出力装置３７は、ディスプレイ、プリンタ等の装置である。ネットワーク接続装置３８は、インターネット等のネットワークに接続するための装置であり、この装置を介してネットワーク上のサーバからプログラムをダウンロードすることができる。なお、ＣＰＵ３１，メモリ３２，外部記憶装置３３，入力装置３６等はバス３９により接続されている。
そして、情報処理装置のＣＰＵ３１が、楕円曲線暗号プログラムを実行することにより、上述したゼロ点判定部２１，スカラー倍算処理部２２，線形座標変換部（座標変換部）２３および乱数生成部２４として機能するようになっている。
なお、これらのゼロ点判定部２１，スカラー倍算処理部２２，線形座標変換部（座標変換部）２３および乱数生成部２４としての機能を実現するためのプログラム（楕円曲線暗号プログラム）は、例えばフレキシブルディスク，ＣＤ−ＲＯＭ，ＣＤ−Ｒ，ＣＤ−Ｒ／Ｗ，ＤＶＤ，ＤＶＤ−Ｒ，ＤＶＤ−Ｒ／Ｗ，磁気ディスク，光ディスク，光磁気ディスク等の、コンピュータ読取可能な記録媒体に記録された形態で提供される。そして、コンピュータはその記録媒体からプログラムを読み取って内部記憶装置または外部記憶装置に転送し格納して用いる。又、そのプログラムを、例えば磁気ディスク，光ディスク，光磁気ディスク等の記憶装置（記録媒体）に記録しておき、その記憶装置から通信経路を介してコンピュータに提供するようにしてもよい。
ゼロ点判定部２１，スカラー倍算処理部２２，線形座標変換部（座標変換部）２３および乱数生成部２４としての機能を実現する際には、内部記憶装置（記憶部１６，メモリ３２）に格納されたプログラムがコンピュータのマイクロプロセッサ（演算部１２，ＣＰＵ３１）によって実行される。このとき、記録媒体に記録されたプログラムをコンピュータが読み取って実行するようにしてもよい。
なお、本実施形態において、コンピュータとは、ハードウェアとオペレーティングシステムとを含む概念であり、オペレーティングシステムの制御の下で動作するハードウェアを意味している。又、オペレーティングシステムが不要でアプリケーションプログラム単独でハードウェアを動作させるような場合には、そのハードウェア自体がコンピュータに相当する。ハードウェアは、少なくとも、ＣＰＵ等のマイクロプロセッサと、記録媒体に記録されたコンピュータプログラムを読み取るための手段とをそなえており、本実施形態においては、楕円曲線暗号装置１１がコンピュータとしての機能を有しているのである。
さらに、本実施形態における記録媒体としては、上述したフレキシブルディスク，ＣＤ−ＲＯＭ，ＣＤ−Ｒ，ＣＤ−Ｒ／Ｗ，ＤＶＤ，ＤＶＤ−Ｒ，ＤＶＤ−Ｒ／Ｗ，磁気ディスク，光ディスク，光磁気ディスクのほか、ＩＣカード，ＲＯＭカートリッジ，磁気テープ，パンチカード，コンピュータの内部記憶装置（ＲＡＭやＲＯＭなどのメモリ），外部記憶装置等や、バーコードなどの符号が印刷された印刷物等のコンピュータ読取可能な種々の媒体を利用することができる。
そして、本発明は、楕円曲線暗号の暗号化及び解読を行なう専用の装置に限らず、ＩＣカード、ＤＶＤ装置、携帯電話機、パーソナルコンピュータ等の種々の製品に適用できる。
そして、本発明は上述した各実施形態に限定されるものではなく、本発明の趣旨を逸脱しない範囲で種々変形して実施することができる。
例えば、演算部１２が、記憶部１６に記憶されたプログラムを実行することにより、ゼロ点判定部２１，スカラー倍算処理部２２，線形座標変換部２３および乱数生成部２４として機能するようになっているが、これに限定されるものではなく、例えば、ゼロ点判定部２１，スカラー倍算処理部２２，線形座標変換部２３および乱数生成部２４のうちの一部の機能を外部装置が処理してもよく、例えば、スカラー倍算処理部２２のみを実行してもよい。
また、本楕円曲線暗号装置１１は、例えば、プロセッサをそなえたスマートカードによって実現されてもよく、又、スマートカードのメモリに秘密鍵や秘密鍵のみを格納しておき、このスマートと通信可能に接続された外部装置（楕円曲線暗号装置）によって楕円曲線暗号処理を行なってもよい。
さらに、上述した第１実施形態および第２実施形態では、線形座標変換部２３が、パラメーター（ｒ１，ｒ２，ｒ３，ｓ１，ｓ２，ｓ３）＝（ｒ＾２，ｒ＾３，ｒ，ｓ，０，０）に基づいて線形座標変換を行なう例について説明しているが、これに限定されるものではなく、例えば、パラメータ（ｒ１，ｒ２，ｒ３）の部分が第３〜第５実施形態と同様に（ｒ，ｒ，ｒ）であってもよく、又、これらのｒ１，ｒ２，ｒ３のうち一部もしくは全てが互いに異なる数値であってもよい。
また、上述した第３〜第５実施形態では、線形座標変換部２３が、パラメーター（ｒ１，ｒ２，ｒ３，ｓ１，ｓ２，ｓ３）＝（ｒ，ｒ，ｒ，ｓ，０，０）に基づいて線形座標変換を行なう例について説明しているが、これに限定されるものではなく、例えば、パラメータ（ｒ１，ｒ２，ｒ３）の部分が第１実施形態や第２実施形態と同様に（ｒ＾２，ｒ＾３，ｒ）であってもよく、又、これらのｒ１，ｒ２，ｒ３のうち一部もしくは全てが互いに異なる数値であってもよい。
さらに、上述した各実施形態について、線形座標変換部２３が線形座標変換に用いるパラメーター（ｒ１，ｒ２，ｒ３，ｓ１，ｓ２，ｓ３）における、パラメータ（ｓ１，ｓ２，ｓ３）の部分は、（ｓ、０，０）に限定されるものではなく、例えば、ｓ１，ｓ２，ｓ３のいずれも０以外の値であってもよく、又、ｓ１とｓ３とだけがそれぞれ０，ｓ１とｓ２とだけがそれぞれ０，ｓ３だけが０，ｓ２だけが０，ｓ１だけが０等、種々変形して実施することができる。更に、これらのｓ１，ｓ２，ｓ３のうち一部もしくは全てが互いに異なる数値であってもよい。
ここで、パラメータｓ１に０ではない数値ｓを適用することにより、ｘ座標が０であるような特殊点は、線型変換座標でのＸ座標がｓの点として表され、スカラー倍算の途中で出現することがない。これによりｘ座標に関する特殊点攻撃に対して安全となる。
また、パラメータｓ２に０ではない数値ｓを適用することにより、ｙ座標が０であるような特殊点は、線型変換座標でのＹ座標がｓの点として表され、スカラー倍算の途中で出現することがなく、ｙ座標に関する特殊点攻撃に対して安全となる。同様に、パラメータｓ３に０ではない数値ｓを適用することにより、ｚ座標が０であるような特殊点は、線型変換座標でのＺ座標がｓの点として表され、スカラー倍算の途中で出現することがなく、ｚ座標に関する特殊点攻撃に対して安全となる。
さらに、上述した線形座標変換部２３によって線形座標変換を行なった変換後の座標を、スカラー倍算処理部２２が、ウィンドウ法（Ａｌｇｏｒｉｔｈｍ ６，６′，６″参照）を用いてスカラー倍算を行なってもよく、これにより、特殊点攻撃に対して安全であるとともにＳＰＡに対しても安全である。
また、上述した各実施形態においては、ｐを５以上の素数とし、要素数ｐの有限体ＧＦ（ｐ）（ｐは５以上の素数）上の楕円曲線に適用した場合について説明しているが、これに限定されるものではなく、本発明の趣旨を逸脱しない範囲で種々変形して実施することができる。
なお、本発明の各実施形態が開示されていれば、本発明の楕円曲線暗号装置，楕円曲線暗号方法，楕円曲線暗号プログラムおよび同プログラムを記録したコンピュータ読取可能な記録媒体を当業者によって実施・製造することが可能である。
【産業上の利用可能性】
以上のように、本発明の楕円曲線暗号装置，楕円曲線暗号方法，楕円曲線暗号プログラムおよび同プログラムを記録したコンピュータ読取可能な記録媒体は、楕円曲線暗号処理を行なうのに有用であり、特にサイドチャネル攻撃に対して有効である。
【図１】
【図２】
【図３】
【図４】
【図５】
【特許請求の範囲】
【請求項１】
楕円曲線暗号処理を行なう楕円曲線暗号装置であって、
有限体ＧＦ（ｐ＾ｍ）上における楕円曲線上の点Ｐの座標（Ｘ：Ｙ：Ｚ）を座標（ｒ１×（Ｘ−ｓ１）：ｒ２×（Ｙ−ｓ２）：ｒ３×（Ｚ−ｓ３））に変換する座標変換部（２３）（ただし、ｐは素数、ｍは１以上の整数、ｒ１，ｒ２，ｒ３はそれぞれ１以上且つ（ｐ−１）以下の整数、ｓ１，ｓ２，ｓ３はそれぞれ０以上且つ（ｐ−１）以下の整数、又、符号＾はべき乗を表わす）と、
該座標変換部（２３）によって変換された楕円曲線上の点のスカラー倍算を行なうスカラー倍算演算部（２２）とをそなえ、
該パラメーターｓ１，ｓ２，ｓ３のうち少なくとも１つが０以外の値を有することを特徴とする、楕円曲線暗号装置。
【請求項２】
該スカラー倍算演算部（２２）が、アド・アンド・ダブル・オールウェイズを用いたバイナリメソッドで、該スカラー倍算を行なうことを特徴とする、請求の範囲第１項に記載の楕円曲線暗号装置。
【請求項３】
該スカラー倍算演算部（２２）が、モンゴメリ・ラダー法で前記スカラー倍算を行なうことを特徴とする、請求の範囲第１項に記載の楕円曲線暗号装置。
【請求項４】
該スカラー倍算演算部（２２）が、ウィンドウ・メソッドで前記スカラー倍算を行なうことを特徴とする、請求の範囲第１項に記載の楕円曲線暗号装置。
【請求項５】
該スカラー倍算演算部（２２）が、ｘ座標法で前記スカラー倍算を行なうことを特徴とする、請求の範囲第１項に記載の楕円曲線暗号装置。
【請求項６】
該スカラー倍算演算部（２２）が、連続楕円２倍算を用いて前記スカラー倍算を行なうことを特徴とする、請求の範囲第１項に記載の楕円曲線暗号装置。
【請求項７】
楕円曲線暗号処理を行なう楕円曲線暗号方法であって、
有限体ＧＦ（ｐ＾ｍ）上における楕円曲線上の点Ｐの座標（Ｘ：Ｙ：Ｚ）を座標（ｒ１×（Ｘ−ｓ１）：ｒ２×（Ｙ−ｓ２）：ｒ３×（Ｚ−ｓ３））に変換する座標変換ステップ（ただし、ｐは素数、ｍは１以上の整数、ｒ１，ｒ２，ｒ３はそれぞれ１以上且つ（ｐ−１）以下の整数、ｓ１，ｓ２，ｓ３はそれぞれ０以上且つ（ｐ−１）以下の整数、又、符号＾はべき乗を表わす）と、
該座標変換ステップにおいて変換された楕円曲線上の点のスカラー倍算を行なうスカラー倍算演算ステップとをそなえ、
該パラメーターｓ１，ｓ２，ｓ３のうち少なくとも１つが０以外の値を有することを特徴とする、楕円曲線暗号方法。
【請求項８】
該スカラー倍算演算ステップにおいて、アド・アンド・ダブル・オールウェイズを用いたバイナリメソッドで、該スカラー倍算を行なうことを特徴とする、請求の範囲第７項に記載の楕円曲線暗号方法。
【請求項９】
該スカラー倍算演算ステップにおいて、モンゴメリ・ラダー法で前記スカラー倍算を行なうことを特徴とする、請求の範囲第７項に記載の楕円曲線暗号方法。
【請求項１０】
該スカラー倍算演算ステップにおいて、ウィンドウ・メソッドで前記スカラー倍算を行なうことを特徴とする、請求の範囲第７項に記載の楕円曲線暗号方法。
【請求項１１】
該スカラー倍算演算ステップにおいて、ｘ座標法で前記スカラー倍算を行なうことを特徴とする、請求の範囲第７項に記載の楕円曲線暗号方法。
【請求項１２】
該スカラー倍算演算ステップにおいて、連続楕円２倍算を用いて前記スカラー倍算を行なうことを特徴とする、請求の範囲第７項に記載の楕円曲線暗号装置。
【請求項１３】
楕円曲線暗号処理を行なう楕円曲線暗号プログラムであって、
有限体ＧＦ（ｐ＾ｍ）上における楕円曲線上の点Ｐの座標（Ｘ：Ｙ：Ｚ）を座標（ｒ１×（Ｘ−ｓ１）：ｒ２×（Ｙ−ｓ２）：ｒ３×（Ｚ−ｓ３））に変換する座標変換部（２３）（ただし、ｐは素数、ｍは１以上の整数、ｒ１，ｒ２，ｒ３はそれぞれ１以上且つ（ｐ−１）以下の整数、ｓ１，ｓ２，ｓ３はそれぞれ０以上且つ（ｐ−１）以下の整数であり、且つ、これらのｓ１，ｓ２，ｓ３のうち少なくとも１つが０以外の値を有する。又、符号＾はべき乗を表わす）と、
該座標変換部（２３）によって変換された楕円曲線上の点のスカラー倍算を行なうスカラー倍算演算部（２２）としてコンピュータを機能させることを特徴とする、楕円曲線暗号プログラム。
【請求項１４】
該スカラー倍算演算部（２２）として該コンピュータを機能させる際に、アド・アンド・ダブル・オールウェイズを用いたバイナリメソッドで、該スカラー倍算を行なうことを特徴とする、請求の範囲第１３項に記載の楕円曲線暗号プログラム。
【請求項１５】
該スカラー倍算演算部（２２）として該コンピュータを機能させる際に、モンゴメリ・ラダー法で前記スカラー倍算を行なうことを特徴とする、請求の範囲第１３項に記載の楕円曲線暗号プログラム。
【請求項１６】
該スカラー倍算演算部（２２）として該コンピュータを機能させる際に、ウィンドウ・メソッドで前記スカラー倍算を行なうことを特徴とする、請求の範囲第１３項に記載の楕円曲線暗号プログラム。
【請求項１７】
該スカラー倍算演算部（２２）として該コンピュータを機能させる際に、ｘ座標法で前記スカラー倍算を行なうことを特徴とする、請求の範囲第１３項に記載の楕円曲線暗号プログラム。
【請求項１８】
該スカラー倍算演算部（２２）として該コンピュータを機能させる際に、連続楕円２倍算を用いて前記スカラー倍算を行なうことを特徴とする、請求の範囲第１３項に記載の楕円曲線暗号プログラム。
【請求項１９】
楕円曲線暗号処理を行なう楕円曲線暗号プログラムを記録したコンピュータ読取可能な記録媒体であって、
該楕円曲線暗号プログラムが、
有限体ＧＦ（ｐ＾ｍ）上における楕円曲線上の点Ｐの座標（Ｘ：Ｙ：Ｚ）を座標（ｒ１×（Ｘ−ｓ１）：ｒ２×（Ｙ−ｓ２）：ｒ３×（Ｚ−ｓ３））に変換する座標変換部（２３）（ただし、ｐは素数、ｍは１以上の整数、ｒ１，ｒ２，ｒ３はそれぞれ１以上且つ（ｐ−１）以下の整数、ｓ１，ｓ２，ｓ３はそれぞれ０以上且つ（ｐ−１）以下の整数であり、且つ、これらのｓ１，ｓ２，ｓ３のうち少なくとも１つが０以外の値を有する。又、符号＾はべき乗を表わす）と、
該座標変換部（２３）によって変換された楕円曲線上の点のスカラー倍算を行なうスカラー倍算演算部（２２）としてコンピュータを機能させることを特徴とする、楕円曲線暗号プログラムを記録したコンピュータ読取可能な記録媒体。
【請求項２０】
該スカラー倍算演算部（２２）として該コンピュータを機能させる際に、アド・アンド・ダブル・オールウェイズを用いたバイナリメソッドで、該スカラー倍算を行なうことを特徴とする、請求の範囲第１９項に記載の楕円曲線暗号プログラムを記録したコンピュータ読取可能な記録媒体。
【請求項２１】
該スカラー倍算演算部（２２）として該コンピュータを機能させる際に、モンゴメリ・ラダー法で前記スカラー倍算を行なうことを特徴とする、請求の範囲第１９項に記載の楕円曲線暗号プログラムを記録したコンピュータ読取可能な記録媒体。
【請求項２２】
該スカラー倍算演算部（２２）として該コンピュータを機能させる際に、ウィンドウ・メソッドで前記スカラー倍算を行なうことを特徴とする、請求の範囲第１９項に記載の楕円曲線暗号プログラムを記録したコンピュータ読取可能な記録媒体。
【請求項２３】
該スカラー倍算演算部（２２）として該コンピュータを機能させる際に、ｘ座標法で前記スカラー倍算を行なうことを特徴とする、請求の範囲第１９項に記載の楕円曲線暗号プログラムを記録したコンピュータ読取可能な記録媒体。
【請求項２４】
該スカラー倍算演算部（２２）として該コンピュータを機能させる際に、連続楕円２倍算を用いて前記スカラー倍算を行なうことを特徴とする、請求の範囲第１９項に記載の楕円曲線暗号プログラムを記録したコンピュータ読取可能な記録媒体。
【請求項１】
楕円曲線暗号処理を行なう楕円曲線暗号装置であって、
有限体ＧＦ（ｐ＾ｍ）上における楕円曲線上の点Ｐの座標（Ｘ：Ｙ：Ｚ）を座標（ｒ１×（Ｘ−ｓ１）：ｒ２×（Ｙ−ｓ２）：ｒ３×（Ｚ−ｓ３））に変換する座標変換部（２３）（ただし、ｐは素数、ｍは１以上の整数、ｒ１，ｒ２，ｒ３はそれぞれ１以上且つ（ｐ−１）以下の整数、ｓ１，ｓ２，ｓ３はそれぞれ０以上且つ（ｐ−１）以下の整数、又、符号＾はべき乗を表わす）と、
該座標変換部（２３）によって変換された楕円曲線上の点のスカラー倍算を行なうスカラー倍算演算部（２２）とをそなえ、
該パラメーターｓ１，ｓ２，ｓ３のうち少なくとも１つが０以外の値を有することを特徴とする、楕円曲線暗号装置。
【請求項２】
該スカラー倍算演算部（２２）が、アド・アンド・ダブル・オールウェイズを用いたバイナリメソッドで、該スカラー倍算を行なうことを特徴とする、請求の範囲第１項に記載の楕円曲線暗号装置。
【請求項３】
該スカラー倍算演算部（２２）が、モンゴメリ・ラダー法で前記スカラー倍算を行なうことを特徴とする、請求の範囲第１項に記載の楕円曲線暗号装置。
【請求項４】
該スカラー倍算演算部（２２）が、ウィンドウ・メソッドで前記スカラー倍算を行なうことを特徴とする、請求の範囲第１項に記載の楕円曲線暗号装置。
【請求項５】
該スカラー倍算演算部（２２）が、ｘ座標法で前記スカラー倍算を行なうことを特徴とする、請求の範囲第１項に記載の楕円曲線暗号装置。
【請求項６】
該スカラー倍算演算部（２２）が、連続楕円２倍算を用いて前記スカラー倍算を行なうことを特徴とする、請求の範囲第１項に記載の楕円曲線暗号装置。
【請求項７】
楕円曲線暗号処理を行なう楕円曲線暗号方法であって、
有限体ＧＦ（ｐ＾ｍ）上における楕円曲線上の点Ｐの座標（Ｘ：Ｙ：Ｚ）を座標（ｒ１×（Ｘ−ｓ１）：ｒ２×（Ｙ−ｓ２）：ｒ３×（Ｚ−ｓ３））に変換する座標変換ステップ（ただし、ｐは素数、ｍは１以上の整数、ｒ１，ｒ２，ｒ３はそれぞれ１以上且つ（ｐ−１）以下の整数、ｓ１，ｓ２，ｓ３はそれぞれ０以上且つ（ｐ−１）以下の整数、又、符号＾はべき乗を表わす）と、
該座標変換ステップにおいて変換された楕円曲線上の点のスカラー倍算を行なうスカラー倍算演算ステップとをそなえ、
該パラメーターｓ１，ｓ２，ｓ３のうち少なくとも１つが０以外の値を有することを特徴とする、楕円曲線暗号方法。
【請求項８】
該スカラー倍算演算ステップにおいて、アド・アンド・ダブル・オールウェイズを用いたバイナリメソッドで、該スカラー倍算を行なうことを特徴とする、請求の範囲第７項に記載の楕円曲線暗号方法。
【請求項９】
該スカラー倍算演算ステップにおいて、モンゴメリ・ラダー法で前記スカラー倍算を行なうことを特徴とする、請求の範囲第７項に記載の楕円曲線暗号方法。
【請求項１０】
該スカラー倍算演算ステップにおいて、ウィンドウ・メソッドで前記スカラー倍算を行なうことを特徴とする、請求の範囲第７項に記載の楕円曲線暗号方法。
【請求項１１】
該スカラー倍算演算ステップにおいて、ｘ座標法で前記スカラー倍算を行なうことを特徴とする、請求の範囲第７項に記載の楕円曲線暗号方法。
【請求項１２】
該スカラー倍算演算ステップにおいて、連続楕円２倍算を用いて前記スカラー倍算を行なうことを特徴とする、請求の範囲第７項に記載の楕円曲線暗号装置。
【請求項１３】
楕円曲線暗号処理を行なう楕円曲線暗号プログラムであって、
有限体ＧＦ（ｐ＾ｍ）上における楕円曲線上の点Ｐの座標（Ｘ：Ｙ：Ｚ）を座標（ｒ１×（Ｘ−ｓ１）：ｒ２×（Ｙ−ｓ２）：ｒ３×（Ｚ−ｓ３））に変換する座標変換部（２３）（ただし、ｐは素数、ｍは１以上の整数、ｒ１，ｒ２，ｒ３はそれぞれ１以上且つ（ｐ−１）以下の整数、ｓ１，ｓ２，ｓ３はそれぞれ０以上且つ（ｐ−１）以下の整数であり、且つ、これらのｓ１，ｓ２，ｓ３のうち少なくとも１つが０以外の値を有する。又、符号＾はべき乗を表わす）と、
該座標変換部（２３）によって変換された楕円曲線上の点のスカラー倍算を行なうスカラー倍算演算部（２２）としてコンピュータを機能させることを特徴とする、楕円曲線暗号プログラム。
【請求項１４】
該スカラー倍算演算部（２２）として該コンピュータを機能させる際に、アド・アンド・ダブル・オールウェイズを用いたバイナリメソッドで、該スカラー倍算を行なうことを特徴とする、請求の範囲第１３項に記載の楕円曲線暗号プログラム。
【請求項１５】
該スカラー倍算演算部（２２）として該コンピュータを機能させる際に、モンゴメリ・ラダー法で前記スカラー倍算を行なうことを特徴とする、請求の範囲第１３項に記載の楕円曲線暗号プログラム。
【請求項１６】
該スカラー倍算演算部（２２）として該コンピュータを機能させる際に、ウィンドウ・メソッドで前記スカラー倍算を行なうことを特徴とする、請求の範囲第１３項に記載の楕円曲線暗号プログラム。
【請求項１７】
該スカラー倍算演算部（２２）として該コンピュータを機能させる際に、ｘ座標法で前記スカラー倍算を行なうことを特徴とする、請求の範囲第１３項に記載の楕円曲線暗号プログラム。
【請求項１８】
該スカラー倍算演算部（２２）として該コンピュータを機能させる際に、連続楕円２倍算を用いて前記スカラー倍算を行なうことを特徴とする、請求の範囲第１３項に記載の楕円曲線暗号プログラム。
【請求項１９】
楕円曲線暗号処理を行なう楕円曲線暗号プログラムを記録したコンピュータ読取可能な記録媒体であって、
該楕円曲線暗号プログラムが、
有限体ＧＦ（ｐ＾ｍ）上における楕円曲線上の点Ｐの座標（Ｘ：Ｙ：Ｚ）を座標（ｒ１×（Ｘ−ｓ１）：ｒ２×（Ｙ−ｓ２）：ｒ３×（Ｚ−ｓ３））に変換する座標変換部（２３）（ただし、ｐは素数、ｍは１以上の整数、ｒ１，ｒ２，ｒ３はそれぞれ１以上且つ（ｐ−１）以下の整数、ｓ１，ｓ２，ｓ３はそれぞれ０以上且つ（ｐ−１）以下の整数であり、且つ、これらのｓ１，ｓ２，ｓ３のうち少なくとも１つが０以外の値を有する。又、符号＾はべき乗を表わす）と、
該座標変換部（２３）によって変換された楕円曲線上の点のスカラー倍算を行なうスカラー倍算演算部（２２）としてコンピュータを機能させることを特徴とする、楕円曲線暗号プログラムを記録したコンピュータ読取可能な記録媒体。
【請求項２０】
該スカラー倍算演算部（２２）として該コンピュータを機能させる際に、アド・アンド・ダブル・オールウェイズを用いたバイナリメソッドで、該スカラー倍算を行なうことを特徴とする、請求の範囲第１９項に記載の楕円曲線暗号プログラムを記録したコンピュータ読取可能な記録媒体。
【請求項２１】
該スカラー倍算演算部（２２）として該コンピュータを機能させる際に、モンゴメリ・ラダー法で前記スカラー倍算を行なうことを特徴とする、請求の範囲第１９項に記載の楕円曲線暗号プログラムを記録したコンピュータ読取可能な記録媒体。
【請求項２２】
該スカラー倍算演算部（２２）として該コンピュータを機能させる際に、ウィンドウ・メソッドで前記スカラー倍算を行なうことを特徴とする、請求の範囲第１９項に記載の楕円曲線暗号プログラムを記録したコンピュータ読取可能な記録媒体。
【請求項２３】
該スカラー倍算演算部（２２）として該コンピュータを機能させる際に、ｘ座標法で前記スカラー倍算を行なうことを特徴とする、請求の範囲第１９項に記載の楕円曲線暗号プログラムを記録したコンピュータ読取可能な記録媒体。
【請求項２４】
該スカラー倍算演算部（２２）として該コンピュータを機能させる際に、連続楕円２倍算を用いて前記スカラー倍算を行なうことを特徴とする、請求の範囲第１９項に記載の楕円曲線暗号プログラムを記録したコンピュータ読取可能な記録媒体。
【国際公開番号】ＷＯ２００５／０１５５２６
【国際公開日】平成１７年２月１７日（２００５．２．１７）
【発行日】平成１８年１０月５日（２００６．１０．５）
【国際特許分類】
【出願番号】特願２００５−５０７５７８（Ｐ２００５−５０７５７８）
【国際出願番号】ＰＣＴ／ＪＰ２００３／０１０００３
【国際出願日】平成１５年８月６日（２００３．８．６）
【出願人】（０００００５２２３）富士通株式会社 (25,993)
【Ｆターム（参考）】
【国際公開日】平成１７年２月１７日（２００５．２．１７）
【発行日】平成１８年１０月５日（２００６．１０．５）
【国際特許分類】
【国際出願番号】ＰＣＴ／ＪＰ２００３／０１０００３
【国際出願日】平成１５年８月６日（２００３．８．６）
【出願人】（０００００５２２３）富士通株式会社 (25,993)
【Ｆターム（参考）】
[ Back to top ]