(57)【要約】【課題】  超楕円暗号処理において安全でかつ高速な演算を実現する装置および方法を実現する。【解決手段】  超楕円曲線暗号に基づくスカラー倍算処理におけるベースポイントＤと、スカラー倍算の実行アルゴリズムとしてのウィンドウ法における事前算出データを、超楕円曲線の種数ｇ（ｇｅｎｕｓ）より小さいウェイトの因子である退化因子とし、ウィンドウ法を適用したスカラー倍算処理における加算処理を退化因子＋非退化因子の加算処理によって実行する。本構成により高速演算が実現され、さらに、演算における鍵解析などの一体様態であるＳＰＡ解析などに対する耐性も損なわれない安全で高速な演算が実現される。【選択図】  図９
2006145945.tif 000002
【特許請求の範囲】
【請求項１】
超楕円曲線暗号に基づく暗号処理演算を実行する暗号処理演算方法であり、
超楕円曲線暗号に基づくスカラー倍算処理における入力因子としてのベースポイントと、スカラー倍算の実行アルゴリズムとしてのウィンドウ法における事前算出データ中、ベースポイントを除く１つ以上の事前算出データとが、超楕円曲線の種数ｇ（ｇｅｎｕｓ）より小さいウェイト（ｗｅｉｇｈｔ）ｇ０（ただし、１≦ｇ０＜ｇ）の因子である退化因子となるベースポイントを生成するベースポイント生成ステップと、
前記ベースポイント生成ステップにおいて生成したベースポイントに基づいて、ウィンドウ法における事前算出データを、退化因子のみからなるデータとして算出する事前算出退化因子データ生成ステップと、
前記事前算出退化因子データ生成ステップにおいて生成した事前算出退化因子データを適用してウィンドウ法を適用したスカラー倍算処理を実行するステップであり、スカラー倍算における加算処理を前記事前算出退化因子を含む加算処理として実行する演算処理ステップと、
を有することを特徴とする暗号処理演算方法。
【請求項２】
前記演算処理ステップは、
因子Ｄに対するスカラー倍算Ｄ＝ｄＤの乗数ｄについての展開処理として、前記ウィンドウ法に基づく展開処理であるｗＮＡＦ（ｗｉｄｔｈ−ｗＮｏｎ−Ａｄｊａｃｅｎｔ  Ｆｏｒｍ）展開を実行する展開処理ステップと、
前記展開処理ステップにおいて生成されたｗＮＡＦ展開処理データに、前記事前算出退化因子データを対応付けた演算を実行するステップと、
を有することを特徴とする請求項１に記載の暗号処理演算方法。
【請求項３】
前記演算処理ステップは、
因子Ｄに対するスカラー倍算Ｄ＝ｄＤの乗数ｄについての展開処理として、前記ウィンドウ法に基づく展開処理であるｗＮＡＦ（ｗｉｄｔｈ−ｗＮｏｎ−Ａｄｊａｃｅｎｔ  Ｆｏｒｍ）展開を実行する展開処理ステップと、
前記展開処理ステップにおいて生成されたｗＮＡＦ展開処理データに基づいて決定される事前算出データに前記事前算出退化因子データ以外のデータを含む場合、前記ｗＮＡＦ展開データを変換し、前記事前算出退化因子データのみによって構成される変換ｗＮＡＦ展開データを生成する展開処理データ変換ステップと、
前記展開処理データ変換ステップにおいて生成された変換ｗＮＡＦ展開データに、前記事前算出退化因子データを対応付けた演算を実行するステップと、
を有することを特徴とする請求項１に記載の暗号処理演算方法。
【請求項４】
前記ベースポイント生成ステップは、
ベースポイントＤと、スカラー倍算の実行アルゴリズムとしてのウィンドウ法における事前算出データ中、ベースポイントを除く１つ以上の事前算出データｎＤ（ただしｎは１以外の整数）とを、超楕円曲線の種数ｇ（ｇｅｎｕｓ）より小さいウェイト（ｗｅｉｇｈｔ）ｇ０（ただし、１≦ｇ０＜ｇ）の因子である退化因子となる設定としてベースポイントを生成するステップであることを特徴とする請求項１に記載の暗号処理演算方法。
【請求項５】
前記暗号処理演算方法は、種数ｇ（ｇｅｎｕｓ）＝２の超楕円曲線におけるスカラー倍算処理を実行する方法であり、
前記ベースポイント生成ステップは、
ベースポイントＤと、５Ｄとを、ウェイト（ｗｅｉｇｈｔ）１の退化因子となるようにベースポイントを生成するステップであり、
前記演算処理ステップは、
因子Ｄに対するスカラー倍算Ｄ＝ｄＤの乗数ｄについての展開処理として、前記ウィンドウ法に基づく展開処理であるｗＮＡＦ（ｗｉｄｔｈ−ｗＮｏｎ−Ａｄｊａｃｅｎｔ  Ｆｏｒｍ）展開を、ウィンドウサイズ＝３として実行する展開処理ステップと、
前記展開処理ステップにおいて生成されたｗＮＡＦ展開処理データに基づいて決定される事前算出データに前記退化因子Ｄ，５Ｄ以外のデータを含む場合、前記ｗＮＡＦ展開データを変換し、前記退化因子Ｄ，５Ｄのみによって構成される変換ｗＮＡＦ展開データを生成する展開処理データ変換ステップと、
前記展開処理データ変換ステップにおいて生成された変換ｗＮＡＦ展開データに、前記退化因子Ｄ，５Ｄを対応付け、スカラー倍算処理中の加算処理を退化因子Ｄ，５Ｄを含む加算処理とした演算を実行するステップと、
を有することを特徴とする請求項１に記載の暗号処理演算方法。
【請求項６】
前記暗号処理演算方法は、種数ｇ（ｇｅｎｕｓ）＝３の超楕円曲線におけるスカラー倍算処理を実行する方法であり、
前記ベースポイント生成ステップは、
ベースポイントＤと、３Ｄとをウェイト（ｗｅｉｇｈｔ）２の退化因子となるようにベースポイントを生成するステップであり、
前記演算処理ステップは、
因子Ｄに対するスカラー倍算Ｄ＝ｄＤの乗数ｄについての展開処理として、前記ウィンドウ法に基づく展開処理であるｗＮＡＦ（ｗｉｄｔｈ−ｗＮｏｎ−Ａｄｊａｃｅｎｔ  Ｆｏｒｍ）展開を、ウィンドウサイズ＝２として実行する展開処理ステップと、
前記展開処理ステップにおいて生成されたｗＮＡＦ展開データに、前記退化因子Ｄ，３Ｄを対応付け、スカラー倍算処理中の加算処理を退化因子Ｄ，３Ｄを含む加算処理とした演算を実行するステップと、
を有することを特徴とする請求項１に記載の暗号処理演算方法。
【請求項７】
超楕円曲線暗号に基づく暗号処理演算を実行する暗号処理装置であり、
超楕円曲線暗号に基づくスカラー倍算処理における入力因子としてのベースポイントと、スカラー倍算の実行アルゴリズムとしてのウィンドウ法における事前算出データ中、ベースポイントを除く１つ以上の事前算出データとが、超楕円曲線の種数ｇ（ｇｅｎｕｓ）より小さいウェイト（ｗｅｉｇｈｔ）ｇ０（ただし、１≦ｇ０＜ｇ）の因子である退化因子となるベースポイントを生成するベースポイント生成手段と、
前記ベースポイント生成手段において生成したベースポイントに基づいて、ウィンドウ法における事前算出データを、退化因子のみからなるデータとして算出する事前算出退化因子データ生成手段と、
前記事前算出退化因子データ生成手段において生成した事前算出退化因子データを適用してウィンドウ法を適用したスカラー倍算処理を実行するステップであり、スカラー倍算における加算処理を前記事前算出退化因子を含む加算処理として実行する演算処理手段と、
を有することを特徴とする暗号処理装置。
【請求項８】
前記暗号処理装置は、さらに、
因子Ｄに対するスカラー倍算Ｄ＝ｄＤの乗数ｄについての展開処理として、前記ウィンドウ法に基づく展開処理であるｗＮＡＦ（ｗｉｄｔｈ−ｗＮｏｎ−Ａｄｊａｃｅｎｔ  Ｆｏｒｍ）展開を実行する展開処理手段を含み、
前記演算処理手段は、
前記展開処理手段において生成されたｗＮＡＦ展開処理データに、前記事前算出退化因子データを対応付けた演算を実行する構成であることを特徴とする請求項７に記載の暗号処理装置。
【請求項９】
前記暗号処理装置は、さらに、
因子Ｄに対するスカラー倍算Ｄ＝ｄＤの乗数ｄについての展開処理として、前記ウィンドウ法に基づく展開処理であるｗＮＡＦ（ｗｉｄｔｈ−ｗＮｏｎ−Ａｄｊａｃｅｎｔ  Ｆｏｒｍ）展開を実行する展開処理手段と、
前記展開処理手段において生成されたｗＮＡＦ展開処理データに基づいて決定される事前算出データに前記事前算出退化因子データ以外のデータを含む場合、前記ｗＮＡＦ展開データを変換し、前記事前算出退化因子データのみによって構成される変換ｗＮＡＦ展開データを生成する展開処理データ変換手段とを含み、
前記演算処理手段は、
前記展開処理データ変換手段において生成された変換ｗＮＡＦ展開データに、前記事前算出退化因子データを対応付けた演算を実行する構成であることを特徴とする請求項７に記載の暗号処理装置。
【請求項１０】
前記ベースポイント生成手段は、
ベースポイントＤと、スカラー倍算の実行アルゴリズムとしてのウィンドウ法における事前算出データ中、ベースポイントを除く１つ以上の事前算出データｎＤ（ただしｎは１以外の整数）とを、超楕円曲線の種数ｇ（ｇｅｎｕｓ）より小さいウェイト（ｗｅｉｇｈｔ）ｇ０（ただし、１≦ｇ０＜ｇ）の因子である退化因子となる設定としてベースポイントを生成する構成であることを特徴とする請求項７に記載の暗号処理装置。
【請求項１１】
前記暗号処理装置は、種数ｇ（ｇｅｎｕｓ）＝２の超楕円曲線におけるスカラー倍算処理を実行する構成であり、
前記ベースポイント生成手段は、
ベースポイントＤと、５Ｄとを、ウェイト（ｗｅｉｇｈｔ）１の退化因子となるようにベースポイントを生成する構成であり、
因子Ｄに対するスカラー倍算Ｄ＝ｄＤの乗数ｄについての展開処理として、前記ウィンドウ法に基づく展開処理であるｗＮＡＦ（ｗｉｄｔｈ−ｗＮｏｎ−Ａｄｊａｃｅｎｔ  Ｆｏｒｍ）展開を、ウィンドウサイズ＝３として実行する展開処理手段と、
前記展開処理手段において生成されたｗＮＡＦ展開処理データに基づいて決定される事前算出データに前記退化因子Ｄ，５Ｄ以外のデータを含む場合、前記ｗＮＡＦ展開データを変換し、前記退化因子Ｄ，５Ｄのみによって構成される変換ｗＮＡＦ展開データを生成する展開処理データ変換手段と、
前記展開処理データ変換手段において生成された変換ｗＮＡＦ展開データに、前記退化因子Ｄ，５Ｄを対応付け、スカラー倍算処理中の加算処理を退化因子Ｄ，５Ｄを含む加算処理とした演算を実行する演算処理手段と、
を有することを特徴とする請求項７に記載の暗号処理装置。
【請求項１２】
前記暗号処理装置は、種数ｇ（ｇｅｎｕｓ）＝３の超楕円曲線におけるスカラー倍算処理を実行する構成であり、
前記ベースポイント生成手段は、
ベースポイントＤと、３Ｄとをウェイト（ｗｅｉｇｈｔ）２の退化因子となるようにベースポイントを生成する構成であり、
因子Ｄに対するスカラー倍算Ｄ＝ｄＤの乗数ｄについての展開処理として、前記ウィンドウ法に基づく展開処理であるｗＮＡＦ（ｗｉｄｔｈ−ｗＮｏｎ−Ａｄｊａｃｅｎｔ  Ｆｏｒｍ）展開を、ウィンドウサイズ＝２として実行する展開処理手段と、
前記展開処理手段において生成されたｗＮＡＦ展開データに、前記退化因子Ｄ，３Ｄを対応付け、スカラー倍算処理中の加算処理を退化因子Ｄ，３Ｄを含む加算処理とした演算を実行する演算処理手段と、
を有することを特徴とする請求項７に記載の暗号処理装置。
【請求項１３】
超楕円曲線暗号に基づく暗号処理演算をコンピュータにおいて実行させるコンピュータ・プログラムであり、
超楕円曲線暗号に基づくスカラー倍算処理における入力因子としてのベースポイントと、スカラー倍算の実行アルゴリズムとしてのウィンドウ法における事前算出データ中、ベースポイントを除く１つ以上の事前算出データとが、超楕円曲線の種数ｇ（ｇｅｎｕｓ）より小さいウェイト（ｗｅｉｇｈｔ）ｇ０（ただし、１≦ｇ０＜ｇ）の因子である退化因子となるベースポイントを生成するベースポイント生成ステップと、
前記ベースポイント生成ステップにおいて生成したベースポイントに基づいて、ウィンドウ法における事前算出データを、退化因子のみからなるデータとして算出する事前算出退化因子データ生成ステップと、
前記事前算出退化因子データ生成ステップにおいて生成した事前算出退化因子データを適用してウィンドウ法を適用したスカラー倍算処理を実行するステップであり、スカラー倍算における加算処理を前記事前算出退化因子を含む加算処理として実行する演算処理ステップと、
を有することを特徴とするコンピュータ・プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、暗号処理演算方法、および暗号処理装置、並びにコンピュータ・プログラムに関する。さらに詳細には、超楕円曲線暗号におけるスカラー倍算の高速化を実現する暗号処理演算方法、および暗号処理装置、並びにコンピュータ・プログラムに関する。
【背景技術】
【０００２】
昨今、ネットワーク通信、電子商取引の発展に伴い、通信におけるセキュリティ確保が重要な問題となっている。セキュリティ確保の１つの方法が暗号技術であり、現在、様々な暗号化手法を用いた通信が行なわれている。
【０００３】
例えばＩＣカード等の小型の装置中に暗号処理モジュールを埋め込み、ＩＣカードと、データ読み取り書き込み装置としてのリーダライタとの間でデータ送受信を行ない、認証処理、あるいは送受信データの暗号化、復号化を行なうシステムが実用化されている。
【０００４】
暗号処理を実行する例えばＩＣカードは、例えば駅の改札などの様々なゲート、あるいはショッピングセンターなどで盛んに利用されるようになっており、小型化および処理の迅速化の要求が厳しくなってきている。
【０００５】
暗号化方式には、大別して共通鍵方式、公開鍵方式がある。共通鍵方式は、対称暗号方式ともよばれ、発信者、受信者の双方で共通の鍵を保有する。共通鍵方式の代表的な方法として、ＤＥＳ（Data Encryption Standard）がある。ＤＥＳアルゴリズムの特徴は、暗号化と復号化とをほぼ同じアルゴリズムで実行可能なことである。
【０００６】
この共通鍵暗号に対して、発信者と受信者の鍵を異なるものとした構成が公開鍵方式または非対称暗号方式である。公開鍵暗号方式では、暗号化、復号化に共通の鍵を用いる共通鍵暗号方式と異なり、秘密に保つ必要のある秘密鍵は、特定の１人が持てばよいため鍵の管理において有利である。ただし、公開鍵暗号方式は共通鍵暗号方式に比較してデータ処理速度が遅く、一般には、秘密鍵の配送、デジタル署名等のデータ量の少ない対象に多く用いられている。公開鍵暗号方式の代表的なものにはＲＳＡ（Rivest-Shamir-Adleman）暗号や、楕円曲線暗号（ＥＣＣ：Elliptic Curve Cryptography）が知られている。
【０００７】
楕円曲線暗号（Elliptic Curve Cryptography）は、素体上の楕円曲線ｙ２＝ｘ３＋ａｘ＋ｂ（４ａ３＋２７ｂ２≠０）や、２の拡大体上の楕円曲線ｙ２＋ｘｙ＝ｘ３＋ａｘ２＋ｂ（ｂ≠０）などを用いる。これらの曲線上の点に無限遠点（Ｏ）を加えた集合は、加法に関して有限群をなし、無限遠点（Ｏ）はその単位元となる。以下、この有限群上の点の加法を＋で表す。この有限群上の異なる２点Ｐ，Ｑの加算Ｐ＋Ｑを「点の加算」、点Ｐと点Ｐの加算Ｐ＋Ｐ＝２Ｐを「点の２倍算」と呼ぶ。また、点Ｐをｋ回加算した点Ｐ＋Ｐ＋…＋Ｐ＝ｋＰを求める演算を「点のスカラー倍算」と呼ぶ。
【０００８】
点のスカラー倍算は、点の加算、および点の２倍算を用いて構成できることが知られている。素体上の楕円曲線や２の拡大体上の楕円曲線上のアフィン座標系（ｘ，ｙ）や射影座標（Ｘ，Ｙ，Ｚ）における点の加算法、点の２倍算法、および点のスカラー倍算法は、ＩＥＥＥ  P1363/D13 Standard Specifications for Public Key Cryptographyに記されている。
【０００９】
楕円曲線暗号を一般化した方式として、Koblitz、Cantorによって提案された超楕円曲線暗号（ＨＥＣＣ：Hyper Elliptic Curve Cryptography）方式がある。超楕円曲線暗号方式については、例えば非特許文献１、非特許文献２に記載されている。
【００１０】
楕円曲線暗号では有限体Ｆｑ上で定義される楕円曲線上の点をＰとし、スカラー倍算した点ｋＰ（ｋ∈Ｚ）をＱとすると、Ｑからｋを求める問題は離散対数問題に帰着できる。一方、超楕円曲線暗号では点の形式的和である因子（ｄｉｖｉｓｏｒ）をＤ１とし、スカラー倍算ｋＤ１で定義される因子をＤ２とすると、Ｄ２からｋを求める問題は超楕円曲線におけるヤコビ多様体上の離散対数問題として公開鍵暗号として用いることができる。
【００１１】
超楕円曲線では曲線を特徴づける値は種数（ｇｅｎｕｓ）ｇである。ｐを素数、ｎを正の整数、ｑ＝ｐｎとする。このとき有限体Ｆｑ上で定義される種数ｇの超楕円曲線Ｃは以下の方程式、
ｙ２＋ｈ（ｘ）ｙ＝ｆ（ｘ）
で定義される。ここで、ｈ（ｘ），ｆ（ｘ）∈Ｆｑ［ｘ］，ｆ（ｘ）は、次数２ｇ＋１のｍｏｎｉｃ多項式である。
【００１２】
超楕円曲線Ｃ上の点Ｐ＝（ｘ、ｙ）に対してｏｐｐｏｓｉｔｅな点−Ｐは（ｘ、ｙ＋ｈ（ｘ））として定義される。Ｐ＝−Ｐである点を分岐点（ｒａｍｉｆｉｃａｔｉｏｎ  ｐｏｉｎｔ）と呼ぶ。
【００１３】
超楕円曲線暗号の定義体の演算サイズ（ビット長）は楕円曲線暗号と同等の安全性を仮定した場合、楕円曲線の定義体の演算サイズに比べて１／ｇに小さくなることが知られている。演算サイズが小さいことは実装上メリットがあり、超楕円曲線暗号の利点の一つして挙げられる。
【００１４】
次に、超楕円曲線暗号の基本事項について説明する。前述したように、超楕円曲線暗号では点の形式的和である因子（ｄｉｖｉｓｏｒ）をＤ１とし、スカラー倍算ｋＤ１で定義される因子をＤ２とすると、Ｄ２からｋを求める問題は超楕円曲線におけるヤコビ多様体上の離散対数問題として公開鍵暗号として用いることができる。
【００１５】
ここで、因子（ｄｉｖｉｓｏｒ）は以下の形式で表現することができる。
【数１】
2006145945.tif 000003
【００１６】
但しＰｉ＝（ｘｉ、ｙｉ）かつｉ≠ｊに対してＰｉ≠Ｐｊである。この形式の因子の表現を半被約因子（ｓｅｍｉ  ｒｅｄｕｃｅｄ  ｄｉｖｉｓｏｒ）とよぶ。
【００１７】
また、ΣｍｉをＤのウェイト（ｗｅｉｇｈｔ）と呼ぶ。さらにウェイト（ｗｅｉｇｈｔ）が種数ｇ以下である半被約因子を被約因子（ｒｅｄｕｃｅｄ  ｄｉｖｉｓｏｒ）と呼ぶ。
【００１８】
超楕円曲線のヤコビ（Ｊａｃｏｂｉ）多様体上の任意の半被約因子Ｄは下記の多項式Ｕ、Ｖ∈Ｆｑ［ｘ］を用いてＤ＝（Ｕ、Ｖ）として表現できる。これをマンホード（Ｍｕｍｆｏｒｄ）表現と呼ぶ。なお、マンホード（Ｍｕｍｆｏｒｄ）表現については、例えば非特許文献３に記載されている。
【数２】
2006145945.tif 000004
【００１９】
種数（ｇｅｎｕｓ）２の任意の被約因子Ｄはマンホード（Ｍｕｍｆｏｒｄ）表現を用いると、有限体Ｆｑ上の元を係数に持つ２次以下の多項式の組、すなわち、
（Ｕ、Ｖ）＝（ｘ２＋ｕ１ｘ＋ｕ０、ｖ１ｘ＋ｖ０）
として表現することができる。
また、種数（ｇｅｎｕｓ）３の任意の被約因子Ｄはマンホード（Ｍｕｍｆｏｒｄ）表現を用いると有限体Ｆｑ上の元を係数に持つ３次以下の多項式の組、すなわち、
（Ｕ、Ｖ）＝（ｘ３＋ｕ２ｘ２＋ｕ１ｘ＋ｕ０、ｖ２ｘ２＋ｖ１ｘ＋ｖ０）
として表現できる。
【００２０】
なお、以下、本明細書において、因子Ｄは、特に断りがない限り被約因子（ｒｅｄｕｃｅｄ  ｄｉｖｉｓｏｒ）であるものとする。すなわち、ウェイト（ｗｅｉｇｈｔ）が種数ｇ以下である半被約因子としての被約因子（ｒｅｄｕｃｅｄ  ｄｉｖｉｓｏｒ）であるものとする。
【００２１】
さらに、被約因子（ｒｅｄｕｃｅｄ  ｄｉｖｉｓｏｒ）のうち、ウェイト（ｗｅｉｇｈｔ）が種数ｇに等しいものを除いた因子、すなわち、被約因子（ｒｅｄｕｃｅｄ  ｄｉｖｉｓｏｒ）のうち、ウェイト（ｗｅｉｇｈｔ）が種数ｇより小さい因子を退化因子（ｄｅｇｅｎｅｒａｔｅ  ｄｉｖｉｓｏｒ）と呼ぶことにする。
例えば、
種数ｇ＝２の場合、退化因子はウェイト（ｗｅｉｇｈｔ）＝１の因子、
種数ｇ＝３の場合、退化因子はウェイト（ｗｅｉｇｈｔ）＝１，２の因子、
となる。
【００２２】
種数ｇ＝２の場合と、種数ｇ＝３の場合において、退化因子（ｄｅｇｅｎｅｒａｔｅ  ｄｉｖｉｓｏｒ）をマンホード（Ｍｕｍｆｏｒｄ）表現を用いて示すと、以下のように表される。
（ア）種数２の退化因子（Ｗｅｉｇｈｔ１）：（Ｕ，Ｖ）＝（ｘ＋ｕ，ｖ）
（イ）種数３の退化因子（Ｗｅｉｇｈｔ１）：（Ｕ，Ｖ）＝（ｘ＋ｕ０，ｖ０）
（ウ）種数３の退化因子（Ｗｅｉｇｈｔ２）：（Ｕ，Ｖ）＝（ｘ２＋ｕ１ｘ＋ｕ０，ｖ１ｘ＋ｖ０）
【００２３】
次に、超楕円曲線暗号で用いられる因子のスカラー倍算について説明する．因子のスカラー倍算は加算アルゴリズムと呼ばれる因子の加算と２倍算組み合わせで計算することができる。以下では主要な加算アルゴリズムについて説明する。
【００２４】
最初に提案された実用的なアルゴリズムはＣａｎｔｏｒのアルゴリズムである。このアルゴリズムについては、例えば非特許文献１、非特許文献２に記載されている。このアルゴリズムはあらゆる種数の超楕円曲線上の因子に対して適用可能なアルゴリズムであるが、楕円曲線に比べてアルゴリズムが複雑で計算量が多いことが欠点である。
【００２５】
Ｈａｒｌｅｙは種数２の超楕円曲線に限定し、因子のｗｅｉｇｈｔの場合分けをおこない、それぞれの場合で最適化を行うことでより計算量の少ないアルゴリズムを提案した。この研究を受けて超楕円曲線暗号（ＨＥＣＣ）における演算アルゴリズムの改良、拡張の研究が近年盛んになっている。
【００２６】
Ｈａｒｌｅｙのアルゴリズムは定義体を素体、種数２の曲線、因子の表現はＭｕｍｆｏｒｄ表現を用いている。このアルゴリズムの計算量の改善の研究例として、例えば、非特許文献４、非特許文献５、非特許文献６などが挙げられる。さらに、定義体を２の拡大体の場合について拡張した処理例について、非特許文献７、非特許文献８に報告されている。また、種数が３の場合のＨａｒｌｅｙのアルゴリズムへの拡張処理については、非特許文献９、非特許文献１０に報告されている。また、因子の表現に拡張Ｍｕｍｆｏｒｄ表現、Ｗｅｉｇｈｔｅｄ  Ｃｏｏｒｄｉｎａｔｅを用いることで計算量を削減した研究として非特許文献１１、非特許文献１２、非特許文献６、非特許文献１３がある。
【００２７】
Ｈａｒｌｅｙアルゴリズムの処理について、図１および図２を参照して説明する。図１（Ａ）は、種数２の場合の因子の加算Ｄ１＋Ｄ２の処理例を示した図である。なお、因子Ｄ１、Ｄ２は、それぞれＤ１＝（Ｕ１、Ｖ１）、Ｄ２＝（Ｕ２、Ｖ２）とする。まず、因子のウェイト（ｗｅｉｇｈｔ）の値によって場合分けが行われる。すなわち、［Ｄ１＋Ｄ２］の各ウェイト（ｗｅｉｇｈｔ）の値によって、
（１）ｗｅｉｇｈｔ２＋ｗｅｉｇｈｔ２
（２）ｗｅｉｇｈｔ２＋ｗｅｉｇｈｔ１
（３）例外処理１
の場合分けが行なわれる。
【００２８】
次にｗｅｉｇｈｔ２同士の加算、すなわち（１）ｗｅｉｇｈｔ２＋ｗｅｉｇｈｔ２の場合、因子Ｄ１＝（Ｕ１、Ｖ１）、Ｄ２＝（Ｕ２、Ｖ２）について、最大公約数ｇｃｄ（Ｕ１、Ｕ２）＝１であれば、２つの因子Ｄ１＝（Ｕ１、Ｖ１）、Ｄ２＝（Ｕ２、Ｖ２）は、互いに同一またはオポジット（ｏｐｐｏｓｉｔｅ）な点を含まない。この場合、
（１ａ）ＨａｒｌｅｙＡＤＤ、
すなわちハーレーアルゴリズムに従った加算処理を行う。（１ａ）ＨａｒｌｅｙＡＤＤの処理は例えば非特許文献７に示されているＭｏｓｔ  Ｆｒｅｑｕｅｎｔ  Ｃａｓｅと呼ばれる処理である。このＭｏｓｔ  Ｆｒｅｑｕｅｎｔ  Ｃａｓｅは、種数２の場合の因子の加算Ｄ１＋Ｄ２処理において、高確率で発生するケースである。
【００２９】
種数２の加算処理におけるＭｏｓｔ  Ｆｒｅｑｕｅｎｔ  Ｃａｓｅで実行するＨａｒｌｅｙＡＤＤの処理を、以下のテーブル１［Ｔａｂｌｅ１］に示す。
【数３】
2006145945.tif 000005
【００３０】
この（１ａ）ＨａｒｌｅｙＡＤＤの処理は、非常に高い確率でおこる。その他の例外処理の起こる確率は非常に低い。Ｍｏｓｔ  Ｆｒｅｑｕｅｎｔ  Ｃａｓｅの条件を満たさない場合、すなわち、因子Ｄ１＝（Ｕ１、Ｖ１）、Ｄ２＝（Ｕ２、Ｖ２）について、最大公約数ｇｃｄ（Ｕ１、Ｕ２）＝１を満足しない場合は、
（１ｂ）例外処理２を行う。
【００３１】
（２）ｗｅｉｇｈｔ２＋ｗｅｉｇｈｔ１の場合についても同様に、ｇｃｄ（Ｕ１、Ｕ２）＝１かどうかをチェックし、ｇｃｄ（Ｕ１、Ｕ２）＝１を満足する場合には、
（２ａ）ＥｘＨａｒＡＤＤ２＋１→２を実行し、
ｇｃｄ（Ｕ１、Ｕ２）＝１を満足しない場合には、
（２ｂ）例外処理３を行う。
【００３２】
（２ａ）ＥｘＨａｒＡＤＤ２＋１→２のアルゴリズムは非特許文献８に示されている。ＥｘＨａｒＡＤＤ２＋１→２の処理を、以下のテーブル３［Ｔａｂｌｅ３］に示す。
【数４】
2006145945.tif 000006
【００３３】
（３）例外処理１は、ｗｅｉｇｈｔの場合分けが上記（１），（２）以外の場合である。
【００３４】
種数２の場合の２倍算の流れを図１（Ｂ）に示す。２倍算は、Ｄ＋Ｄ＝２Ｄの処理である。加算の場合と同様に因子Ｄのｗｅｉｇｈｔが
（４）ｗｅｉｇｈｔ２、
（５）ｗｅｉｇｈｔ１、
（６）ｗｅｉｇｈｔ０、
によってそれぞれ異なる処理を行う。
【００３５】
（４）ｗｅｉｇｈｔ２の場合、因子が分岐点を含むかどうかをチェックし、含まなければ、（４ａ）ＨａｒｌｅｙＤＢＬの処理を行う。因子が分岐点を含む場合は（４ｂ）例外処理６を行う。
【００３６】
（４ａ）ＨａｒｌｅｙＤＢＬの処理アルゴリズムは例えば非特許文献７にＭｏｓｔ  Ｆｒｅｑｕｅｎｔ  Ｃａｓｅとして示されている。ＨａｒｌｅｙＤＢＬの処理アルゴリズムを、以下のテーブル２［Ｔａｂｌｅ２］に示す。
【数５】
2006145945.tif 000007
【００３７】
次に、種数３の場合における加算、２倍算について、図２を参照して説明する。種数３においても、種数２の場合と基本的な考え方は同じであるが、種数３の場合、因子の最大のｗｅｉｇｈｔが３になるため、場合分けの数は種数２に比べて非常に多くなることが特徴である。
【００３８】
図２（Ａ）加算において、因子Ｄ１、Ｄ２は、それぞれＤ１＝（Ｕ１、Ｖ１）、Ｄ２＝（Ｕ２、Ｖ２）とする。まず、因子のウェイト（ｗｅｉｇｈｔ）の値によって場合分けが行われる。すなわち、［Ｄ１＋Ｄ２］の各ウェイト（ｗｅｉｇｈｔ）の値によって、
（１）ｗｅｉｇｈｔ３＋ｗｅｉｇｈｔ３
（２）ｗｅｉｇｈｔ３＋ｗｅｉｇｈｔ２
（３）ｗｅｉｇｈｔ３＋ｗｅｉｇｈｔ１
（４）例外処理７
の場合分けが行なわれる。
【００３９】
さらに、（１）ｗｅｉｇｈｔ３＋ｗｅｉｇｈｔ３の場合において、因子Ｄ１＝（Ｕ１、Ｖ１）、Ｄ２＝（Ｕ２、Ｖ２）について、最大公約数ｇｃｄ（Ｕ１、Ｕ２）＝１を満足する場合は、
（１ａ）ＨａｒｌｅｙＡＤＤ
を実行する。これが種数３の加算処理における最も高確率で発生するケース、すなわち、Ｍｏｓｔ  Ｆｒｅｑｕｅｎｔ  Ｃａｓｅである。
【００４０】
種数３の加算処理におけるＭｏｓｔ  Ｆｒｅｑｕｅｎｔ  ＣａｓｅとしてのＨａｒｌｅｙＡＤＤは例えば非特許文献９，１０に示されている。種数３の加算処理におけるＭｏｓｔ  Ｆｒｅｑｕｅｎｔ  ＣａｓｅとしてのＨａｒｌｅｙＡＤＤのアルゴリズムを以下のテーブル［Ｔａｂｌｅ４］に示す。
【数６】
2006145945.tif 000008
【００４１】
同様に、（２）ｗｅｉｇｈｔ３＋ｗｅｉｇｈｔ２の場合において、因子Ｄ１＝（Ｕ１、Ｖ１）、Ｄ２＝（Ｕ２、Ｖ２）について、最大公約数ｇｃｄ（Ｕ１、Ｕ２）＝１を満足する場合は、
（２ａ）ＥｘＨａｒＡＤＤ３＋２→３、
を実行する。
最大公約数ｇｃｄ（Ｕ１、Ｕ２）＝１を満足しない場合は、
（２ｂ）例外処理９
を実行する。
【００４２】
同様に、（３）ｗｅｉｇｈｔ３＋ｗｅｉｇｈｔ１の場合において、因子Ｄ１＝（Ｕ１、Ｖ１）、Ｄ２＝（Ｕ２、Ｖ２）について、最大公約数ｇｃｄ（Ｕ１、Ｕ２）＝１を満足する場合は、
（３ａ）ＥｘＨａｒＡＤＤ３＋１→３、
を実行する。
最大公約数ｇｃｄ（Ｕ１、Ｕ２）＝１を満足しない場合は、
（３ｂ）例外処理１０
を実行する。
【００４３】
それぞれのアルゴリズムは文献等に明示的に示されていないので、定義体がＦ２ｎの場合の公式を導出した。その結果としてのＥｘＨａｒＡＤＤ３＋１→３、およびＥｘＨａｒＡＤＤ３＋２→３のアルゴリズムを、以下のテーブル［Ｔａｂｌｅ６］、［Ｔａｂｌｅ７］に示す。
【数７】
2006145945.tif 000009
【００４４】
【数８】
2006145945.tif 000010
【００４５】
種数３の場合の２倍算の流れを図２（Ｂ）に示す。２倍算は、Ｄ＋Ｄ＝２Ｄの処理である。加算の場合と同様に因子Ｄのｗｅｉｇｈｔが
（４）ｗｅｉｇｈｔ３、
（５）ｗｅｉｇｈｔ２、
（６）ｗｅｉｇｈｔ１、
（７）ｗｅｉｇｈｔ０、
によってそれぞれ異なる処理を行う。
【００４６】
（４）ｗｅｉｇｈｔ３の場合、因子が分岐点を含むかどうかをチェックし、含まなければ、（４ａ）ＨａｒｌｅｙＤＢＬの処理を行う。因子が分岐点を含む場合は（４ｂ）例外処理１１を行う。
【００４７】
（４ａ）ＨａｒｌｅｙＤＢＬの処理アルゴリズムは例えば非特許文献９，１０にＭｏｓｔ  Ｆｒｅｑｕｅｎｔ  Ｃａｓｅとして示されている。ＨａｒｌｅｙＤＢＬの処理アルゴリズムを、以下のテーブル５［Ｔａｂｌｅ５］に示す。
【数９】
2006145945.tif 000011
【００４８】
種数２、３共にＨａｒｌｅｙＡＤＤ、ＨａｒｌｅｙＤＢＬはｍｏｓｔ  ｆｒｅｑｕｅｎｔ  ｃａｓｅと呼ばれ、ランダムに因子を発生させて加算または２倍算を行うと、非常に高い確率でＨａｒｌｅｙＡＤＤ、ＨａｒｌｅｙＤＢＬの処理になる。なお、このＨａｒｌｅｙＡＤＤ、ＨａｒｌｅｙＤＢＬが、ｍｏｓｔ  ｆｒｅｑｕｅｎｔ  ｃａｓｅとなることの説明は、例えば非特許文献１４に説明されている。
【００４９】
非特許文献１４によると、このｍｏｓｔ  ｆｒｅｑｕｅｎｔ  ｃａｅｓ以外の処理になる確率はＯ（１／ｑ）である。ここでｑは定義体の要素数であり、安全な暗号用途ではqgが１６０ｂｉｔ程度必要になる大きな数であるので現実的にはＨａｒｌｅｙＡＤＤ、ＨａｒｌｅｙＤＢＬしか発生しない状況とみなすことができる。
【００５０】
従って超楕円曲線暗号（ＨＥＣＣ）の加算アルゴリズムをＨａｒｌｅｙアルゴリズムまたはその改良アルゴリズムを使って、例えばＩＣカードなどの暗号処理演算手段として実装する場合、
ＨａｒｌｅｙＡＤＤ、
ＨａｒｌｅｙＤＢＬ
だけを実装し、その他の確率的にほとんど起こらない複雑な例外処理についての演算を実行しない実装とする場合も多い。この場合、例外処理については、ｗｅｉｇｈｔの場合分けが必要のないＣａｎｔｏｒのアルゴリズムを実行する構成とするなどの方法が適用される。種数が高くなるほど複雑な例外処理の負担は増すため、非特許文献９，１０ではこの実装方法について説明している。
【００５１】
次に超楕円曲線暗号（ＨＥＣＣ）アルゴリズムにおける因子のスカラー倍算について説明する。超楕円曲線暗号（ＨＥＣＣ）アルゴリズムにおいて、因子のスカラー倍算は、超楕円加算と超楕円２倍算の組み合わせで計算することができる。スカラー倍算のアルゴリズムとして基本的なｂｉｎａｒｙ法とｄｏｕｂｌｅ−ａｎｄ−ａｄｄ−ａｌｗａｙｓ法を例に挙げて説明する。
【００５２】
前述したように、楕円曲線暗号では有限体Ｆｑ上で定義される楕円曲線上の点をＰとし、スカラー倍算した点ｋＰ（ｋ∈Ｚ）をＱとすると、Ｑからｋを求める問題は離散対数問題に帰着できる。一方、超楕円曲線暗号では点の形式的和である因子（ｄｉｖｉｓｏｒ）をＤ１とし、スカラー倍算ｋＤ１で定義される因子をＤ２とすると、Ｄ２からｋを求める問題は超楕円曲線におけるヤコビ多様体上の離散対数問題として公開鍵暗号として用いることができる。
【００５３】
因子Ｄに対して、スカラー倍算（Ｄ＝ｄＤ）に適用する乗数としてのスカラー値:ｄの２進数表現を、
ｄ＝（ｄｌ−１、・・・・・、ｄ０）、
ただし、ｄｌ−１＝１、ｄｌ−２，・・・，０＝１ｏｒ０とする。
【００５４】
スカラー倍算のアルゴリズムとして基本的なｂｉｎａｒｙ法の演算アルゴリズム［アルゴリズム１］を以下に示す。
【数１０】
2006145945.tif 000012
【００５５】
次に、ｄｏｕｂｌｅ−ａｎｄ−ａｄｄ−ａｌｗａｙｓ法の演算アルゴリズムについて説明する。
【００５６】
暗号技術の実装方法の不具合を利用して秘密情報を知る方法をサイドチャネルアタック（Ｓｉｄｅ  Ｃｈａｎｎｅｌ  Ａｔｔｔａｃｋ、  ＳＣＡ）と呼ぶ。ＳＣＡには秘密情報と相関のある演算の処理時間を利用して攻撃を行なうタイミングアタック（ＴＡ：Ｔｉｍｉｎｇ  Ａｔｔａｃｋ）や、秘密情報と電力消費量の相関を利用して攻撃を行なう単純電力解析（ＳＰＡ：Ｓｉｍｐｌｅ  Ｐｏｗｅｒ  Ａｎａｌｙｓｉｓ）や、差分電力解析（ＤＰＡ：Ｄｉｆｆｅｒｅｎｔｉａｌ  Ｐｏｗｅｒ  Ａｎａｌｙｓｉｓ）といった電力攻撃などがある。タイミングアタック（ＴＡ）については非特許文献１５、電力攻撃については、非特許文献１６に説明がある。
【００５７】
単純電力解析（ＳＰＡ）は秘密鍵のビット情報に依存した演算の消費電力の波形を直接観測することにより、秘密情報を明らかにする実装攻撃である。暗号処理アルゴリズムのＳＰＡに対する耐性を高めるためには、例えば秘密鍵のビット情報と電力波形の相関を発生させないアルゴリズムに設定することが必要となる。また、タイミングアタック（ＴＡ）に対する耐性を高めるためには、例えば秘密鍵のビット情報と演算時間の相関を発生させないアルゴリズムに設定することが有効である。
【００５８】
楕円曲線暗号（ＥＣＣ）、および超楕円曲線暗号（ＨＥＣＣ）に対するタイミングアタック（ＴＡ）、および電力攻撃（ＳＰＡ）に対する対策構成としてｄｏｕｂｌｅ−ａｎｄ−ａｄｄ−ａｌｗａｙｓ法が有効であることが知られている。このｄｏｕｂｌｅ−ａｎｄ−ａｄｄ−ａｌｗａｙｓ法についての詳細は、非特許文献１７に説明されている。このアルゴリズムでは上記のｂｉｎａｒｙ法の演算アルゴリズムと異なり、乗数としてのスカラー量ｄの構成ｂｉｔの値によって演算時間や電力波形が異ならないようにダミー（Dummy）の加算を常に行なう構成としてある。
【００５９】
スカラー倍算のアルゴリズムとして基本的なｄｏｕｂｌｅ−ａｎｄ−ａｄｄ−ａｌｗａｙｓ法の演算アルゴリズム［アルゴリズム２］を以下に示す。
【数１１】
2006145945.tif 000013
【００６０】
次に、ベースポイントの生成処理について説明する。スカラー倍算の計算を暗号技術で用いる場合、入力に必要な因子Ｄ０は、
（１）事前に決めた因子の場合、
（２）事前に決められないランダムに発生する因子の場合、
の２つのタイプに分けることができる。
【００６１】
ここで（１）事前に決めた因子の場合、の入力因子をベースポイントと呼ぶことにする。
一般的なベースポイントの生成アルゴリズムを以下に示す。
（ａ）
定義体Ｆｑ上の元をランダムにｇ個選び、ｇ個の超楕円曲線上の点Ｐｉ（ｉ＝１、…、ｇ）を生成する。
（ａ１）  ランダムに選んだ各元をｘ座標ｘｉ（ｉ＝１…ｇ）とし、次に超楕円曲線上に乗るようにｘｉに対応するｙ座標を求める。
（ｂ）
ベースポイントの因子をＤ０＝（Ｕ（ｘ）、Ｖ（ｘ））とする。
（ｂ１）Ｕ（ｘ）＝（ｘ−ｘ１）（ｘ−ｘ２）…（ｘ−ｘｇ）
（ｂ２）Ｖ（ｘ）＝ｖｇ−１ｘｇ−１＋ｖｇ−２ｘｇ−２＋…＋ｖ０の係数ｖｉを決定する。例えば生成した点が全て異なる場合、Ｖ（ｘｉ）＝ｙｉよりｖｉを求めることができる。
（ｃ）  上記アルゴリズムにより生成される因子はｗｅｉｇｈｔ  ｇの因子となる。
【００６２】
スカラー倍算の計算を暗号技術で用いる場合、入力に必要な因子Ｄ０の生成、すなわちベースポイントの生成において、事前に決めた因子を適用する場合、上述の処理（ａ）〜（ｃ）によってｗｅｉｇｈｔ  ｇのベースポイントに適用する因子を求めることができる。
【非特許文献１】N.Koblitz. Hyperelliptic curve cryptosystems. J.Cryptology, vol.1,No.3, pp.139-150, 1989.
【非特許文献２】D.G.Cantor. Computing in the Jacobian of hyperelliptic curve. Math. Comp., Vol.48, No. 177, pp.95-101, 1987
【非特許文献３】「D. Mumford, Tata lectures on theta II, Progress in Mathematics, no. 43, Birkhauser, 1984.」
【非特許文献４】K.Matsuo, J.Chao, and S.Tsujii. Fast Genus two hyperelliptic curve cryptosystems. Technical Report ISEC2001-31, IEICE Japan, 2001.
【非特許文献５】M.Takahashi. Improving Harley algorithms for Jacobians of genus 2 hyperelliptic curves. SCIS2002. (Japanese).
【非特許文献６】T.Lange. Inversion-free arithmetic on genus 2 hyperelliptic curves. Cryptology ePrint Archive, 2002/147, IACR, 2002.
【非特許文献７】T.Sugizaki, K.Matsuo, J.Chao, and S.Tsujii. An extension of Harley addition algtorithm for hyperelliptic curves over finite fields of characteristic two. ISEC2002-9, IEICE, 2001
【非特許文献８】T.Lange, Efficient arithmetic on genus 2 hyperelliptic curves over finite fields via explicit formulae. Cryptology ePrint Archive, 2002/121, IACR, 2002.
【非特許文献９】J.Kuroki, M.Gonda, K.Masuo, J.Chao and S.Tsujii. Fast genus three hyperellipitc curve cryptosystems. SCIS2002
【非特許文献１０】J.Pelzl, T.Wollinger, J. Guajardo, and C. Paar. Hyperelliptic curve Cryptosystems: Closing the Performance Gap to Elliptic Curves. Cryptology ePrint Archive, 2003/026, IACR, 2003.
【非特許文献１１】Y.Miyamoto, H.Doi, K.Matsuo, J.Chao and S.Tsujii. A fast addition algorithm of genus two hyperelliptic curves. SCIS2002. (Japanese).
【非特許文献１２】N.Takahashi, H.Morimoto and A.Miyaji. Efficient exponentiation on genus two hyperelliptic curves (II). ISEC2002-145, IEICE, 2003. (Japanese)
【非特許文献１３】T.Lange. Weighed coordinate on genus 2 hyperellipitc curve. Cryptology ePrint Archive, 2002/153, IACR, 2002.
【非特許文献１４】N. Nagao. Improving group law algorithms for Jacobians of hyperelliptic curves. ANTS-IV, LNCS 1838, pp.439-448, Springer-Verlag, 2000.
【非特許文献１５】C. Kocher, Timing Attacks on Implementations of Diffie-Hellman, RSA, DSS, and Other Systems, CRYPTO'96, LNCS 1109, pp.104-113, 1996
【非特許文献１６】C. Kocher, J. Jaffe, and B. Jun, Differential Power Analysis, CRYPTO '99, LNCS 1666, pp.388-397, Springer-Verlag, 1999
【非特許文献１７】J.-S. Coron, Resistance against Differential Power Analysis for Elliptic Curve Cryptosystems, CHES'99, LNCS 1717, pp.292-302, Springer-Verlag, 1999
【発明の開示】
【発明が解決しようとする課題】
【００６３】
現在、実用フェーズに入りつつある楕円曲線暗号（ＥＣＣ）アルゴリズムに対して、その拡張概念である超楕円曲線暗号（ＨＥＣＣ）アルゴリズムは、現在、学会レベルで高速アルゴリズムや、その実装方法についての研究が進められている。超楕円曲線暗号（ＨＥＣＣ）のスカラー倍算の演算時間は、楕円曲線暗号（ＥＣＣ）に近づきつつある程度に過ぎず、さらなる高速化が望まれている。
【００６４】
本発明は、このような現状に鑑みてなされたものであり、超楕円曲線暗号（ＨＥＣＣ）のスカラー倍算の演算時間を短縮し、高速処理可能な超楕円曲線暗号（ＨＥＣＣ）演算処理を実現する暗号処理演算方法、および暗号処理装置、並びにコンピュータ・プログラムを提供することを目的とする。
【００６５】
本発明は、種数ｇの超楕円曲線において、種数ｇより小さいウェイト（ｗｅｉｇｈｔ）の因子（退化因子）をベースポイントとして選択し、ウィンドウ法を適用したスカラー倍算を実行する構成としたものであり、ウィンドウ法において適用する事前算出データを退化因子によって表現し、スカラー倍算における加算演算処理をすべて退化因子＋非退化因子の加算処理として実行可能としたことで、安全性の高い高速演算処理を実現する暗号処理演算方法、および暗号処理装置、並びにコンピュータ・プログラムを提供することを目的とする。
【００６６】
さらに具体的には、本発明は、種数ｇ＝２の曲線において，ベースポイントＤと５Ｄが、ウェイト（ｗｅｉｇｈｔ）＝１である退化因子を効率的に探索し、これらを事前計算退化因子Ｄ，５Ｄとしたウィンドウ法によるスカラー倍算処理を行なうことで演算の高速化を実現する。また、種数３の曲線において，ベースポイントＤと３Ｄがウェイト（ｗｅｉｇｈｔ）＝２である退化因子を効率的に検出し、これらを事前計算退化因子Ｄ，３Ｄとしたウィンドウ法によるスカラー倍算処理を行なうことで演算の高速化を実現する暗号処理演算方法、および暗号処理装置、並びにコンピュータ・プログラムを提供することを目的とする。
【課題を解決するための手段】
【００６７】
本発明の第１の側面は、
超楕円曲線暗号に基づく暗号処理演算を実行する暗号処理演算方法であり、
超楕円曲線暗号に基づくスカラー倍算処理における入力因子としてのベースポイントと、スカラー倍算の実行アルゴリズムとしてのウィンドウ法における事前算出データ中、ベースポイントを除く１つ以上の事前算出データとが、超楕円曲線の種数ｇ（ｇｅｎｕｓ）より小さいウェイト（ｗｅｉｇｈｔ）ｇ０（ただし、１≦ｇ０＜ｇ）の因子である退化因子となるベースポイントを生成するベースポイント生成ステップと、
前記ベースポイント生成ステップにおいて生成したベースポイントに基づいて、ウィンドウ法における事前算出データを、退化因子のみからなるデータとして算出する事前算出退化因子データ生成ステップと、
前記事前算出退化因子データ生成ステップにおいて生成した事前算出退化因子データを適用してウィンドウ法を適用したスカラー倍算処理を実行するステップであり、スカラー倍算における加算処理を前記事前算出退化因子を含む加算処理として実行する演算処理ステップと、
を有することを特徴とする暗号処理演算方法にある。
【００６８】
さらに、本発明の暗号処理演算方法の一実施態様において、前記演算処理ステップは、因子Ｄに対するスカラー倍算Ｄ＝ｄＤの乗数ｄについての展開処理として、前記ウィンドウ法に基づく展開処理であるｗＮＡＦ（ｗｉｄｔｈ−ｗＮｏｎ−Ａｄｊａｃｅｎｔ  Ｆｏｒｍ）展開を実行する展開処理ステップと、前記展開処理ステップにおいて生成されたｗＮＡＦ展開処理データに、前記事前算出退化因子データを対応付けた演算を実行するステップと、を有することを特徴とする。
【００６９】
さらに、本発明の暗号処理演算方法の一実施態様において、前記演算処理ステップは、因子Ｄに対するスカラー倍算Ｄ＝ｄＤの乗数ｄについての展開処理として、前記ウィンドウ法に基づく展開処理であるｗＮＡＦ（ｗｉｄｔｈ−ｗＮｏｎ−Ａｄｊａｃｅｎｔ  Ｆｏｒｍ）展開を実行する展開処理ステップと、前記展開処理ステップにおいて生成されたｗＮＡＦ展開処理データに基づいて決定される事前算出データに前記事前算出退化因子データ以外のデータを含む場合、前記ｗＮＡＦ展開データを変換し、前記事前算出退化因子データのみによって構成される変換ｗＮＡＦ展開データを生成する展開処理データ変換ステップと、前記展開処理データ変換ステップにおいて生成された変換ｗＮＡＦ展開データに、前記事前算出退化因子データを対応付けた演算を実行するステップとを有することを特徴とする。
【００７０】
さらに、本発明の暗号処理演算方法の一実施態様において、前記ベースポイント生成ステップは、ベースポイントＤと、スカラー倍算の実行アルゴリズムとしてのウィンドウ法における事前算出データ中、ベースポイントを除く１つ以上の事前算出データｎＤ（ただしｎは１以外の整数）とを、超楕円曲線の種数ｇ（ｇｅｎｕｓ）より小さいウェイト（ｗｅｉｇｈｔ）ｇ０（ただし、１≦ｇ０＜ｇ）の因子である退化因子となる設定としてベースポイントを生成するステップであることを特徴とする。
【００７１】
さらに、本発明の暗号処理演算方法の一実施態様において、前記暗号処理演算方法は、種数ｇ（ｇｅｎｕｓ）＝２の超楕円曲線におけるスカラー倍算処理を実行する方法であり、前記ベースポイント生成ステップは、ベースポイントＤと、５Ｄとを、ウェイト（ｗｅｉｇｈｔ）１の退化因子となるようにベースポイントを生成するステップであり、前記演算処理ステップは、因子Ｄに対するスカラー倍算Ｄ＝ｄＤの乗数ｄについての展開処理として、前記ウィンドウ法に基づく展開処理であるｗＮＡＦ（ｗｉｄｔｈ−ｗＮｏｎ−Ａｄｊａｃｅｎｔ  Ｆｏｒｍ）展開を、ウィンドウサイズ＝３として実行する展開処理ステップと、前記展開処理ステップにおいて生成されたｗＮＡＦ展開処理データに基づいて決定される事前算出データに前記退化因子Ｄ，５Ｄ以外のデータを含む場合、前記ｗＮＡＦ展開データを変換し、前記退化因子Ｄ，５Ｄのみによって構成される変換ｗＮＡＦ展開データを生成する展開処理データ変換ステップと、前記展開処理データ変換ステップにおいて生成された変換ｗＮＡＦ展開データに、前記退化因子Ｄ，５Ｄを対応付け、スカラー倍算処理中の加算処理を退化因子Ｄ，５Ｄを含む加算処理とした演算を実行するステップとを有することを特徴とする。
【００７２】
さらに、本発明の暗号処理演算方法の一実施態様において、前記暗号処理演算方法は、種数ｇ（ｇｅｎｕｓ）＝３の超楕円曲線におけるスカラー倍算処理を実行する方法であり、前記ベースポイント生成ステップは、ベースポイントＤと、３Ｄとをウェイト（ｗｅｉｇｈｔ）２の退化因子となるようにベースポイントを生成するステップであり、前記演算処理ステップは、因子Ｄに対するスカラー倍算Ｄ＝ｄＤの乗数ｄについての展開処理として、前記ウィンドウ法に基づく展開処理であるｗＮＡＦ（ｗｉｄｔｈ−ｗＮｏｎ−Ａｄｊａｃｅｎｔ  Ｆｏｒｍ）展開を、ウィンドウサイズ＝２として実行する展開処理ステップと、前記展開処理ステップにおいて生成されたｗＮＡＦ展開データに、前記退化因子Ｄ，３Ｄを対応付け、スカラー倍算処理中の加算処理を退化因子Ｄ，３Ｄを含む加算処理とした演算を実行するステップとを有することを特徴とする。
【００７３】
さらに、本発明の第２の側面は、
超楕円曲線暗号に基づく暗号処理演算を実行する暗号処理装置であり、
超楕円曲線暗号に基づくスカラー倍算処理における入力因子としてのベースポイントと、スカラー倍算の実行アルゴリズムとしてのウィンドウ法における事前算出データ中、ベースポイントを除く１つ以上の事前算出データとが、超楕円曲線の種数ｇ（ｇｅｎｕｓ）より小さいウェイト（ｗｅｉｇｈｔ）ｇ０（ただし、１≦ｇ０＜ｇ）の因子である退化因子となるベースポイントを生成するベースポイント生成手段と、
前記ベースポイント生成手段において生成したベースポイントに基づいて、ウィンドウ法における事前算出データを、退化因子のみからなるデータとして算出する事前算出退化因子データ生成手段と、
前記事前算出退化因子データ生成手段において生成した事前算出退化因子データを適用してウィンドウ法を適用したスカラー倍算処理を実行するステップであり、スカラー倍算における加算処理を前記事前算出退化因子を含む加算処理として実行する演算処理手段と、
を有することを特徴とする暗号処理装置にある。
【００７４】
さらに、本発明の暗号処理装置の一実施態様において、前記暗号処理装置は、さらに、因子Ｄに対するスカラー倍算Ｄ＝ｄＤの乗数ｄについての展開処理として、前記ウィンドウ法に基づく展開処理であるｗＮＡＦ（ｗｉｄｔｈ−ｗＮｏｎ−Ａｄｊａｃｅｎｔ  Ｆｏｒｍ）展開を実行する展開処理手段を含み、前記演算処理手段は、前記展開処理手段において生成されたｗＮＡＦ展開処理データに、前記事前算出退化因子データを対応付けた演算を実行する構成であることを特徴とする。
【００７５】
さらに、本発明の暗号処理装置の一実施態様において、前記暗号処理装置は、さらに、因子Ｄに対するスカラー倍算Ｄ＝ｄＤの乗数ｄについての展開処理として、前記ウィンドウ法に基づく展開処理であるｗＮＡＦ（ｗｉｄｔｈ−ｗＮｏｎ−Ａｄｊａｃｅｎｔ  Ｆｏｒｍ）展開を実行する展開処理手段と、前記展開処理手段において生成されたｗＮＡＦ展開処理データに基づいて決定される事前算出データに前記事前算出退化因子データ以外のデータを含む場合、前記ｗＮＡＦ展開データを変換し、前記事前算出退化因子データのみによって構成される変換ｗＮＡＦ展開データを生成する展開処理データ変換手段とを含み、前記演算処理手段は、前記展開処理データ変換手段において生成された変換ｗＮＡＦ展開データに、前記事前算出退化因子データを対応付けた演算を実行する構成であることを特徴とする。
【００７６】
さらに、本発明の暗号処理装置の一実施態様において、前記ベースポイント生成手段は、ベースポイントＤと、スカラー倍算の実行アルゴリズムとしてのウィンドウ法における事前算出データ中、ベースポイントを除く１つ以上の事前算出データｎＤ（ただしｎは１以外の整数）とを、超楕円曲線の種数ｇ（ｇｅｎｕｓ）より小さいウェイト（ｗｅｉｇｈｔ）ｇ０（ただし、１≦ｇ０＜ｇ）の因子である退化因子となる設定としてベースポイントを生成する構成であることを特徴とする。
【００７７】
さらに、本発明の暗号処理装置の一実施態様において、前記暗号処理装置は、種数ｇ（ｇｅｎｕｓ）＝２の超楕円曲線におけるスカラー倍算処理を実行する構成であり、前記ベースポイント生成手段は、ベースポイントＤと、５Ｄとを、ウェイト（ｗｅｉｇｈｔ）１の退化因子となるようにベースポイントを生成する構成であり、因子Ｄに対するスカラー倍算Ｄ＝ｄＤの乗数ｄについての展開処理として、前記ウィンドウ法に基づく展開処理であるｗＮＡＦ（ｗｉｄｔｈ−ｗＮｏｎ−Ａｄｊａｃｅｎｔ  Ｆｏｒｍ）展開を、ウィンドウサイズ＝３として実行する展開処理手段と、前記展開処理手段において生成されたｗＮＡＦ展開処理データに基づいて決定される事前算出データに前記退化因子Ｄ，５Ｄ以外のデータを含む場合、前記ｗＮＡＦ展開データを変換し、前記退化因子Ｄ，５Ｄのみによって構成される変換ｗＮＡＦ展開データを生成する展開処理データ変換手段と、前記展開処理データ変換手段において生成された変換ｗＮＡＦ展開データに、前記退化因子Ｄ，５Ｄを対応付け、スカラー倍算処理中の加算処理を退化因子Ｄ，５Ｄを含む加算処理とした演算を実行する演算処理手段とを有することを特徴とする。
【００７８】
さらに、本発明の暗号処理装置の一実施態様において、前記暗号処理装置は、種数ｇ（ｇｅｎｕｓ）＝３の超楕円曲線におけるスカラー倍算処理を実行する構成であり、前記ベースポイント生成手段は、ベースポイントＤと、３Ｄとをウェイト（ｗｅｉｇｈｔ）２の退化因子となるようにベースポイントを生成する構成であり、因子Ｄに対するスカラー倍算Ｄ＝ｄＤの乗数ｄについての展開処理として、前記ウィンドウ法に基づく展開処理であるｗＮＡＦ（ｗｉｄｔｈ−ｗＮｏｎ−Ａｄｊａｃｅｎｔ  Ｆｏｒｍ）展開を、ウィンドウサイズ＝２として実行する展開処理手段と、前記展開処理手段において生成されたｗＮＡＦ展開データに、前記退化因子Ｄ，３Ｄを対応付け、スカラー倍算処理中の加算処理を退化因子Ｄ，３Ｄを含む加算処理とした演算を実行する演算処理手段とを有することを特徴とする。
【００７９】
さらに、本発明の第３の側面は、
超楕円曲線暗号に基づく暗号処理演算をコンピュータにおいて実行させるコンピュータ・プログラムであり、
超楕円曲線暗号に基づくスカラー倍算処理における入力因子としてのベースポイントと、スカラー倍算の実行アルゴリズムとしてのウィンドウ法における事前算出データ中、ベースポイントを除く１つ以上の事前算出データとが、超楕円曲線の種数ｇ（ｇｅｎｕｓ）より小さいウェイト（ｗｅｉｇｈｔ）ｇ０（ただし、１≦ｇ０＜ｇ）の因子である退化因子となるベースポイントを生成するベースポイント生成ステップと、
前記ベースポイント生成ステップにおいて生成したベースポイントに基づいて、ウィンドウ法における事前算出データを、退化因子のみからなるデータとして算出する事前算出退化因子データ生成ステップと、
前記事前算出退化因子データ生成ステップにおいて生成した事前算出退化因子データを適用してウィンドウ法を適用したスカラー倍算処理を実行するステップであり、スカラー倍算における加算処理を前記事前算出退化因子を含む加算処理として実行する演算処理ステップと、
を有することを特徴とするコンピュータ・プログラムにある。
【００８０】
なお、本発明のコンピュータ・プログラムは、例えば、様々なプログラム・コードを実行可能なコンピュータ・システムに対して、コンピュータ可読な形式で提供する記憶媒体、通信媒体、例えば、ＣＤやＦＤ、ＭＯなどの記録媒体、あるいは、ネットワークなどの通信媒体によって提供可能なコンピュータ・プログラムである。このようなプログラムをコンピュータ可読な形式で提供することにより、コンピュータ・システム上でプログラムに応じた処理が実現される。
【００８１】
本発明のさらに他の目的、特徴や利点は、後述する本発明の実施例や添付する図面に基づくより詳細な説明によって明らかになるであろう。なお、本明細書においてシステムとは、複数の装置の論理的集合構成であり、各構成の装置が同一筐体内にあるものには限らない。
【発明の効果】
【００８２】
本発明の構成によれば、超楕円曲線暗号に基づくスカラー倍算処理におけるベースポイントＤと、スカラー倍算の実行アルゴリズムとしてのウィンドウ法における事前算出データ中、ベースポイントを除く１つ以上の事前算出データとを、超楕円曲線の種数ｇ（ｇｅｎｕｓ）より小さいウェイト（ｗｅｉｇｈｔ）ｇ０（ただし、１≦ｇ０＜ｇ）の因子である退化因子となる設定とし、ウィンドウ法を適用したスカラー倍算処理における加算処理を事前算出した退化因子を含む加算処理によって実行する構成としたので、高速演算が実現されるとともに、退化因子を含まない加算処理が混在しないので加算処理の演算処理時間や、演算処理に伴う消費電力の差異が発生せず、演算シーケンスの解析としてのＳＰＡ、ＴＡ解析に対する耐性も損なわれることのない安全で高速な演算が実現される。
【００８３】
さらに、本発明の構成によれば、因子Ｄに対するスカラー倍算Ｄ＝ｄＤの乗数ｄについての展開処理として、ウィンドウ法に基づく展開処理であるｗＮＡＦ（ｗｉｄｔｈ−ｗＮｏｎ−Ａｄｊａｃｅｎｔ  Ｆｏｒｍ）展開を実行し、展開処理において生成されたｗＮＡＦ展開処理データに基づいて決定される事前算出データに、退化因子データ以外のデータを含む場合、ｗＮＡＦ展開データを変換し、退化因子データのみによって構成される変換ｗＮＡＦ展開データを生成して、変換ｗＮＡＦ展開データに退化因子データを対応付け、スカラー倍算における加算処理を非退化因子＋退化因子の加算処理として実行する構成としたので、演算シーケンスの解析としてのＳＰＡ、ＴＡ解析に対する耐性の損なわれない安全で高速な演算が実現する。
【発明を実施するための最良の形態】
【００８４】
以下、本発明の暗号処理装置および暗号処理演算方法、並びにコンピュータ・プログラムの詳細について説明する。なお、説明は、以下の項目に従って行なう。
１．本発明の基礎技術としての超楕円曲線暗号アルゴリズムの高速化手法
（１Ａ）退化因子をベースポイントとして適用した処理例
（１Ｂ）ウィンドウ（Ｗｉｎｄｏｗ）法を適用した処理例
２．本発明の処理例としての退化因子をベースポイントとして設定し、かつウィンドウ（Ｗｉｎｄｏｗ）法を適用した処理例
３．暗号処理装置の機能構成について
４．電子署名生成および検証アルゴリズムにおける本発明の適用例
５．暗号処理装置のハードウェア構成例
【００８５】
［１．本発明の基礎技術としての超楕円曲線暗号アルゴリズムの高速化手法］
まず、本発明の基礎技術としての超楕円曲線暗号アルゴリズムの高速化手法として、以下の２つの手法について説明する。
（１Ａ）退化因子をベースポイントに適用した処理例
（１Ｂ）ウィンドウ（Ｗｉｎｄｏｗ）法を適用した処理例
【００８６】
（１Ａ）退化因子をベースポイントとして適用した処理例
まず、退化因子をベースポイントとして適用した処理例について説明する。なお、本手法は、本願特許出願人が先に出願した特許出願である特願２００４−７１７５７において開示した手法である。
【００８７】
本手法は、楕円曲線暗号を一般化した超楕円曲線暗号（ＨＥＣＣ：Hyper Elliptic Curve Cryptography）についての高速化演算手法である。前述したように、超楕円曲線では曲線を特徴づける値は種数（ｇｅｎｕｓ）ｇである。ｐを素数、ｎを正の整数、ｑ＝ｐｎとする。このとき有限体Ｆｑ上で定義される種数ｇの超楕円曲線Ｃは以下の方程式、
ｙ２＋ｈ（ｘ）ｙ＝ｆ（ｘ）
で定義される。ここで、ｈ（ｘ），ｆ（ｘ）∈Ｆｑ［ｘ］，ｆ（ｘ）は、次数２ｇ＋１のｍｏｎｉｃ多項式である。
【００８８】
超楕円曲線Ｃ上の点Ｐ＝（ｘ、ｙ）に対してｏｐｐｏｓｉｔｅな点−Ｐは（ｘ、ｙ＋ｈ（ｘ））として定義される。Ｐ＝−Ｐである点を分岐点（ｒａｍｉｆｉｃａｔｉｏｎ  ｐｏｉｎｔ）と呼ぶ。
【００８９】
超楕円曲線暗号の定義体の演算サイズ（ビット長）は楕円曲線暗号と同等の安全性を仮定した場合、楕円曲線の定義体の演算サイズに比べて１／ｇに小さくなることが知られている。演算サイズが小さいことは実装上メリットがあり、超楕円曲線暗号の利点の一つして挙げられる。
【００９０】
前述したように、超楕円曲線暗号では点の形式的和である因子（ｄｉｖｉｓｏｒ）をＤ１とし、スカラー倍算ｋＤ１で定義される因子をＤ２とすると、Ｄ２からｋを求める問題は超楕円曲線におけるヤコビ多様体上の離散対数問題として公開鍵暗号として用いることができる。
【００９１】
因子（ｄｉｖｉｓｏｒ）は、前述したように、以下の形式で表現することができる。
【数１２】
2006145945.tif 000014
【００９２】
但しＰｉ＝（ｘｉ、ｙｉ）かつｉ≠ｊに対してＰｉ≠Ｐｊである。この形式の因子を半被約因子（ｓｅｍｉ  ｒｅｄｕｃｅｄ  ｄｉｖｉｓｏｒ）とよぶ。また、ΣｍｉをＤのウェイト（ｗｅｉｇｈｔ）と呼ぶ。さらにウェイト（ｗｅｉｇｈｔ）が種数ｇ以下である半被約因子を被約因子（ｒｅｄｕｃｅｄ  ｄｉｖｉｓｏｒ）と呼ぶ。
【００９３】
超楕円曲線のヤコビ（Ｊａｃｏｂｉ）多様体上の任意の半被約因子Ｄは下記の多項式Ｕ、Ｖ∈Ｆｑ［ｘ］を用いてＤ＝（Ｕ、Ｖ）として表現できる。これをマンホード（Ｍｕｍｆｏｒｄ）表現と呼ぶ。
【数１３】
2006145945.tif 000015
【００９４】
種数（ｇｅｎｕｓ）２の任意の被約因子Ｄはマンホード（Ｍｕｍｆｏｒｄ）表現を用いると、有限体Ｆｑ上の元を係数に持つ２次以下の多項式の組、すなわち、
（Ｕ、Ｖ）＝（ｘ２＋ｕ１ｘ＋ｕ０、ｖ１ｘ＋ｖ０）
として表現することができる。
また、種数（ｇｅｎｕｓ）３の任意の被約因子Ｄはマンホード（Ｍｕｍｆｏｒｄ）表現を用いると有限体Ｆｑ上の元を係数に持つ３次以下の多項式の組、すなわち、
（Ｕ、Ｖ）＝（ｘ３＋ｕ２ｘ２＋ｕ１ｘ＋ｕ０、ｖ２ｘ２＋ｖ１ｘ＋ｖ０）
として表現できる。
【００９５】
なお、他の因子の表現として変形Ｍｕｍｆｏｒｄ表現、Ｗｅｉｇｈｔｅｄ  Ｃｏｏｒｄｉｎａｔｅがある。変形Ｍｕｍｆｏｒｄ表現はＥＣＣ（楕円曲線暗号）でいうプロジェクティブ（ｐｒｏｊｅｃｔｉｖｅ）座標に相当し、Ｍｕｍｆｏｒｄ表現（Ｕ、Ｖ）に定数Ｚ倍し、（Ｕ、Ｖ、Ｚ）で表現するものである。
【００９６】
Ｗｅｉｇｈｔｅｄ  Ｃｏｏｒｄｉｎａｔｅも同様にＭｕｍｆｏｒｄ表現に複数の定数（Ｚ１、Ｚ２）をかけることで（Ｕ、Ｖ、Ｚ１、Ｚ２）で表現する方法である。いずれも下記に述べるＨａｒｌｅｙのアルゴリズムの計算量を削減するための手法として用いられている。
【００９７】
前述したように、スカラー倍算の計算を暗号技術で用いる場合、入力に必要な因子Ｄ０は、
（１）事前に決めた因子の場合、
（２）事前に決められないランダムに発生する因子の場合、
の２つのタイプに分けることができる。
ここで（１）事前に決めた因子を適用する場合、この入力因子がベースポイントとなる。
【００９８】
なお、前述のように、本発明の説明において、因子Ｄは、ウェイト（ｗｅｉｇｈｔ）が種数ｇ以下である半被約因子としての被約因子（ｒｅｄｕｃｅｄ  ｄｉｖｉｓｏｒ）である。また、ウェイト（ｗｅｉｇｈｔ）が種数ｇに等しいものを除いた因子、すなわち、被約因子（ｒｅｄｕｃｅｄ  ｄｉｖｉｓｏｒ）のうち、ウェイト（ｗｅｉｇｈｔ）が種数ｇより小さい因子を退化因子（ｄｅｇｅｎｅｒａｔｅ  ｄｉｖｉｓｏｒ）と呼ぶ。
例えば、
種数ｇ＝２の場合、退化因子はウェイト（ｗｅｉｇｈｔ）＝１の因子、
種数ｇ＝３の場合、退化因子はウェイト（ｗｅｉｇｈｔ）＝１，２の因子、
となる。
【００９９】
種数ｇ＝２の場合と、種数ｇ＝３の場合において、退化因子（ｄｅｇｅｎｅｒａｔｅ  ｄｉｖｉｓｏｒ）をマンホード（Ｍｕｍｆｏｒｄ）表現を用いて示すと、以下のように表される。
（ア）種数２の退化因子：（Ｕ，Ｖ）＝（ｘ＋ｕ，ｖ）
（イ）種数３の退化因子（Ｗｅｉｇｈｔ１）：（Ｕ，Ｖ）＝（ｘ＋ｕ０，ｖ０）
（ウ）種数３の退化因子（Ｗｅｉｇｈｔ２）：（Ｕ，Ｖ）＝（ｘ２＋ｕ１ｘ＋ｕ０，ｖ１ｘ＋ｖ０）
【０１００】
前述したように、一般的なベースポイントの生成アルゴリズムは、以下の処理によって実行される。
（ａ）  定義体Ｆｑ上の元をランダムにｇ個選び、ｇ個の超楕円曲線上の点Ｐｉ（ｉ＝１、…、ｇ）を生成する。
（ａ１）  ランダムに選んだ各元をｘ座標ｘｉ（ｉ＝１…ｇ）とし、次に超楕円曲線上に乗るようにｘｉに対応するｙ座標を求める。
（ｂ）  ベースポイントの因子をＤ０＝（Ｕ（ｘ）、Ｖ（ｘ））とする。
（ｂ１）Ｕ（ｘ）＝（ｘ−ｘ１）（ｘ−ｘ２）…（ｘ−ｘｇ）
（ｂ２）Ｖ（ｘ）＝ｖｇ−１ｘｇ−１＋ｖｇ−２ｘｇ−２＋…＋ｖ０の係数ｖｉを決定する。例えば生成した点が全て異なる場合、Ｖ（ｘｉ）＝ｙｉよりｖｉを求めることができる。
（ｃ）  上記アルゴリズムにより生成される因子はｗｅｉｇｈｔ  ｇの因子となる。
【０１０１】
このように、種数ｇの超楕円曲線においてベースポイントを生成する従来のアルゴリズム及び装置は通常、ウェイト（ｗｅｉｇｈｔ）＝ｇの因子を生成する。
【０１０２】
本願特許出願人の先願特許として出願済みの特願２００４−７１７５７において説明している退化因子をベースポイントに適用した処理例は、種数ｇの超楕円曲線において、ｇより小さいウェイト（ｗｅｉｇｈｔ）＝ｇ０の因子、すなわち退化因子（ｄｅｇｅｎａｒａｔｅ  ｄｉｖｉｓｏｒ）を生成して、これをベースポイントとして設定して処理を行なう。
【０１０３】
本処理例を適用して、スカラー倍算処理を実行する場合の全体シーケンスについて、図３を参照して説明する。退化因子（ｄｅｇｅｎａｒａｔｅ  ｄｉｖｉｓｏｒ）をベースポイントに適用したスカラー倍算処理例においては、まず、ステップＳ１０１において、種数ｇの超楕円曲線において、ｇより小さいウェイト（ｗｅｉｇｈｔ）＝ｇ０の因子、すなわち退化因子（Ｄ０）を生成する。すなわち、
種数ｇ＝２の場合、ウェイト（ｗｅｉｇｈｔ）＝１の因子、
種数ｇ＝３の場合、ウェイト（ｗｅｉｇｈｔ）＝１，２の因子、
を生成する。
【０１０４】
次に、ステップＳ１０２において、スカラー倍算（Ｄ＝ｄＤ０）に適用する乗数としてのスカラー値:ｄを２進展開する。ステップＳ１０３において、２進展開したスカラー値：ｄと、ステップＳ１０１において生成した退化因子（Ｄ０）を適用したスカラー倍算演算処理（Ｄ＝ｄＤ０）を実行する。スカラー倍算演算処理（Ｄ＝ｄＤ０）は、例えば前述したｂｉｎａｒｙ法や、ｄｏｕｂｌｅ−ａｎｄ−ａｌｗａｙｓ法を適用して実行する。
【０１０５】
ステップＳ１０１において実行する処理、すなわち、種数ｇの超楕円曲線において、ｇより小さいウェイト（ｗｅｉｇｈｔ）＝ｇ０の退化因子（Ｄ０）を生成する処理の詳細について説明する。
本処理例では、種数ｇの超楕円曲線におけるベースポイントを、
ｇ０＜ｇ
が成立するウェイト（ｗｅｉｇｈｔ）＝ｇ０の退化因子に設定する。この退化因子を適用したベースポイント設定により、超楕円曲線暗号におけるスカラー倍算を高速化させる。
【０１０６】
種数ｇの超楕円曲線を適用した超楕円曲線暗号で適用する因子は、多くの場合、種数ｇと同じｗｅｉｇｈｔを持った因子である。つまり、退化因子ではない因子である。ランダムに因子を生成した場合，退化因子になる確率は、有限体の元の数をｑとするとＯ（１／ｑ）の確率である。例えば種数２の場合、ｑは暗号用途で使うことを考えると、２８０程度の大きな値になるため、ランダムに因子を選んだ場合、退化因子になる確率は非常に少ない。しかし固定点のベースポイントのスカラー倍算の場合、意図的に退化因子を作ることができる。退化因子を生成する方法について図４を参照して説明する。
【０１０７】
種数ｇの超楕円曲線においてウェイト（ｗｅｉｇｈｔ）＝ｇの因子をベースポイントとして生成する従来のアルゴリズムでは、超楕円曲線上の点をｇ個選ぶ処理を実行するのに対して、本処理例のベースポイント生成アルゴリズムでは、超楕円曲線上の点をｇ０個、選択する処理を実行する。但しｇ０は１≦ｇ０＜ｇを満たす値である。本処理例に従ったベースポイント生成は、以下の処理手順で実行する。
【０１０８】
（ステップＳ１２１）
定義体としての有限体Ｆｑ上の元をランダムにｇ０個選び、ｇ０個の超楕円曲線上の点Ｐｉ（ｉ＝１、…、ｇ０）を生成する。
（１）ランダムに選んだ各元をｘ座標ｘｉ（ｉ＝１…ｇ０）とし、次に超楕円曲線上に乗るようにｘｉに対応するｙ座標を求める。
【０１０９】
（ステップＳ１２２）
ベースポイントの因子をＤ０＝（Ｕ（ｘ）、Ｖ（ｘ））とする。
（１）Ｕ（ｘ）＝（ｘ−ｘ１）（ｘ−ｘ２）…（ｘ−ｘｇ０）
（２）Ｖ（ｘ）＝ｖｇ０−１ｘｇ０−１＋ｖｇ０−２ｘｇ０−２＋…＋ｖ０の係数ｖｉを決定する。例えば生成した点が全て異なる場合、Ｖ（ｘｉ）＝ｙｉ（ｉ＝１…ｇ０）よりｖｉを求めることができる。
【０１１０】
上述のステップの実行により、種数ｇの超楕円曲線において、ウェイト（ｗｅｉｇｈｔ）がｇより小さいウェイト（ｗｅｉｇｈｔ）＝ｇ０である因子をベースポイントとして生成する。
【０１１１】
例えば種数ｇ＝３の超楕円曲線の場合、ベースポイントは、従来の手法によれば、通常ｗｅｉｇｈｔ  ３の因子を用いるのに対して、本処理例に従ったベースポイント設定アルゴリズムを適用した場合、種数ｇ＝３より小さいウェイト、すなわちウェイト（ｗｅｉｇｈｔ）＝１もしくはウェイト（ｗｅｉｇｈｔ）＝２の因子をベースポイントとする。
【０１１２】
また、例えば種数ｇ＝２の超楕円曲線の場合、ベースポイントは、従来の手法によれば、通常ｗｅｉｇｈｔ  ２の因子を用いるのに対して、本処理例に従ったベースポイント設定アルゴリズムを適用した場合、種数ｇ＝２より小さいウェイト、すなわちウェイト（ｗｅｉｇｈｔ）＝１の因子をベースポイントとする。
【０１１３】
図４を参照して説明したアルゴリズムを適用して、種数ｇの超楕円曲線において、ｇより小さいウェイト（ｗｅｉｇｈｔ）＝ｇ０である因子をベースポイントとして生成した場合、この因子を適用して実行するスカラー倍算では、スカラー倍算実行アルゴリズム中で用いる加算公式が、従来の種数ｇに等しいウェイトを持つベースポイントを適用した場合とは異なってくる。
【０１１４】
すなわち、種数ｇより小さいウェイト（ｗｅｉｇｈｔ）の因子をベースポイントに選んだ場合、スカラー倍算中の加算は、ＨａｒｌｅｙＡＤＤではなくなり、「ｗｅｉｇｈｔ  ｇの因子＋ｇより小さいｗｅｉｇｈｔの因子の加算」になる。この「ｗｅｉｇｈｔ  ｇの因子＋ｇより小さいｗｅｉｇｈｔの因子の加算」にかかる計算コストは因子を表現する多項式の次数が下がるため、ＨａｒｌｅｙＡＤＤよりも計算量が少なくなり、スカラー倍算の処理時間を短くすることができる。
【０１１５】
退化因子をベースポイントにセットした場合、単純電力解析（ＳＰＡ）に対する耐性のあるスカラー倍算のアルゴリズムとして基本的なｄｏｕｂｌｅ−ａｎｄ−ａｄｄ−ａｌｗａｙｓ法の演算アルゴリズム［アルゴリズム３］を以下に示す。
【数１４】
2006145945.tif 000016
【０１１６】
本処理例では、上記アルゴリズムに従った演算が実行されることになる。通常、退化因子との加算は退化因子でないものどうしの加算よりも計算量が少なくなるため、意図的に退化因子を作らない場合に比べてスカラー倍算を高速に演算することができる。
【０１１７】
（１Ｂ）ウィンドウ（Ｗｉｎｄｏｗ）法を適用した処理例
次に、本発明の基礎技術としての超楕円曲線暗号アルゴリズムの高速化手法処理のもう１つの処理例であるウィンドウ（Ｗｉｎｄｏｗ）法を適用した処理例について説明する。
【０１１８】
ウィンドウ（Ｗｉｎｄｏｗ）法を使った単純電力解析に耐性のある方法として、例えば、［K. Okeya and T. Takagi, The Width-w NAF Method Provides Small Memory and Fast Elliptic Scalar Multiplications Secure against Side Channel Attacks, CT-RSA 2003, LNCS 2612, pp328-343, Springer-Verlag, 2003］に記載されている。なお、超楕円曲線暗号は、楕円曲線暗号を一般化した方式であり、このウィンドウ法を適用した高速化手法がギャップなしに適用できる。
【０１１９】
図５を参照して、ウィンドウ法を適用して、スカラー倍算処理を実行する場合の全体シーケンスについて説明する。
【０１２０】
ウィンドウ法には、いくつかの種類がある。最も基本的なものは、因子Ｄに対するスカラー倍算［Ｄ＝ｄＤ］において適用する乗数として設定されるスカラー値：ｄを２進表現に展開し、２進表現データの最上位ビット〜最下位ビットを所定の桁数で分割して分割ブロックを生成し、各分割ブロックに設定される乗数ｄの構成ビットと被乗数Ｄとの乗算データｄＤを事前に算出してテーブル化して保持し、実際のスカラー倍算処理に際しては、テーブルを参照して事前算出データを取得することで演算を省略して高速化を図るものである。
【０１２１】
例えば、スカラー倍算［Ｄ＝ｄＤ］において適用する乗数として設定されるスカラー値：ｄ＝２６７４・・・２２３（１０進表現）であるとき、この２進展開は、例えば、
ｄ＝１１１０１０１００１・・・００１０１１１００１１
のように表現されたとする。
この場合、上位から、例えば３ビットずつのウィンドウ（ウィンドウサイズ：ｗ＝３）を設定する。
［１１１］，［０１０］，［１００］・・・
これらの各構成ビットと因子Ｄとの乗算結果を、予め算出してテーブルに記憶しておけば、演算を実行することなくテーブルに記録された事前算出データを抽出するのみでよく、演算が簡略化され高速化処理が可能となる。なお、事前に算出しテーブル化するデータは、様々な組み合わせが提案されている。
【０１２２】
テーブルに記録する事前算出データを削減した方式として、ＮＡＦ展開方式がある。これは、乗数（ｄ）をＮＡＦ（Ｎｏｎ−Ａｄｊａｃｅｎｔ  ｆｏｒｍ）展開（＝非隣接型符号付き２進数展開）する。ＮＡＦ展開は、乗数（ｄ）を０でないビット（１または−１）が連続しないような符号付き２進数表現とする展開処理であり、０でないビットの数が最小となる。
【０１２３】
ＮＡＦ展開では、乗数ｄの２進展開データについて、連続する［１］のデータ部を変換するため［−１］を適用して、０，１，−１のビットデータ、すなわち、非隣接型符号付き２進数展開を行なう。
【０１２４】
さらに、事前に算出しテーブル化するデータを削減した方式として、ｗＮＡＦ（ｗｉｄｔｈ−ｗＮｏｎ−Ａｄｊａｃｅｎｔ  Ｆｏｒｍ）法が提案された。この詳細は、前述の［K. Okeya and T. Takagi, The Width-w NAF Method Provides Small Memory and Fast Elliptic Scalar Multiplications Secure against Side Channel Attacks, CT-RSA 2003, LNCS 2612, pp328-343, Springer-Verlag, 2003］に記載されている。
【０１２５】
ｗＮＡＦ展開方式では、所定の桁数でなる数値ブロックのうち、被乗数（Ｄ）に乗算した値、例えば±Ｄ，±３Ｄ，±５Ｄ，・・・±（２ｗ−１）Ｄを事前計算してこれをテーブルに保持する形式とする。乗数ｄの２進展開データについてデータ変換を実行して、所定桁数（ウィンドウサイズ）からなる数値ブロックの各々を、
｜００・・０ｘ｜００・・０ｘ｜００・・０ｘ｜・・
ただし、ｘは奇数（±１，±３・・）
となるように設定する。
このような設定とすることで、テーブルに保持する事前計算データを
±Ｄ，±３，±５Ｄ，・・・±（２ｗ−１）Ｄ
のような限定されたデータとすることができ、事前計算データを削減することができる。
【０１２６】
図５に示すフローに従って、ウィンドウ法（ｗＮＡＦ法）を適用したスカラー倍算処理の全体シーケンスについて説明する。ステップＳ１５１において、種数ｇの超楕円曲線において、ランダムに因子を生成する。このときの生成因子は、退化因子を選択した因子生成処理としては実行されない。従って、多くの場合ｇに等しいウェイト（ｗｅｉｇｈｔ）の因子が生成される。この生成因子をベースポイントとする。
【０１２７】
次に、ステップＳ１５２において、上述した事前算出データを算出する。ここでは、ウィンドウサイズ：ｗとして、符号付きの奇数１，３，・・・２ｗ−１を適用し、事前算出データとして、これらの符号付き奇数とベースポイント因子Ｄとの乗算値、すなわち、
±Ｄ，±３，±５Ｄ，・・・±（２ｗ−１）Ｄ
の各乗算値を事前算出データとして算出し、メモリに保持する。
【０１２８】
次に、ステップＳ１５３において、スカラー倍算［Ｄ＝ｄＤ］において適用する乗数として設定されるスカラー値：ｄをｗＮＡＦ展開する。ｗＮＡＦ展開とは、上述したように、乗数として設定されるスカラー値：ｄを、
｜００・・０ｘ｜００・・０ｘ｜００・・０ｘ｜・・
ただし、ｘは奇数（±１，±３・・）
となる分割ブロックに分割する処理であり、ここでは、スカラー値：ｄを±の符号付きの奇数によって構成される固定幅ウィンドウサイズ（所定桁数）からなるブロックに展開する。
【０１２９】
スカラー値：ｄのｗＮＡＦ展開のアルゴリズム［アルゴリズム４］を以下に示す。
【数１５】
2006145945.tif 000017
次に、ステップＳ１５４において、スカラー倍算［Ｄ＝ｄＤ］の演算処理を実行する。この演算処理では、ｗＮＡＦ展開したスカラー値：ｄと、ステップＳ１５２において、事前算出済みの乗算値算出データ：±Ｄ，±３，±５Ｄ，・・・±（２ｗ−１）Ｄ、を適用した演算処理が実行される。
【０１３０】
スカラー倍算［Ｄ＝ｄＤ］の演算アルゴリズム［アルゴリズム５］を以下に示す。
【数１６】
2006145945.tif 000018
本処理例では、ステップＳ１５３のｗＮＡＦ展開により、スカラー値：ｄが、符号付奇数１，３、・・・２ｗ−１と０によって示されるブロックデータとして展開される。スカラー値を２進展開した場合と同様にスカラー値に現れる非零の数が少ないほど，スカラー倍算の計算量を削減することができる．本処理例は、非零の頻度を最も少なくすることができる方法である．また，展開したパターンは常にＤＤ・・ＤＡＤ・・・ＤＡのパターン（Ｄが因子の２倍算、Ａが因子の加算）になるため、単純電力解析（ＳＰＡ）に対して耐性のある方式となる。また、ステップＳ１５４で実行するスカラー倍算はパターン自体にＳＰＡ耐性があるので，２進展開した場合のDouble-and-Add-Always法のようにダミー演算を伴わないことが特徴である。
【０１３１】
［２．本発明の処理例としての退化因子をベースポイントとして設定し、かつウィンドウ（Ｗｉｎｄｏｗ）法を適用した処理例］
次に、本発明の処理例として、退化因子をベースポイントとして設定し、かつウィンドウ法（ｗＮＡＦ）を適用した処理例について説明する。上述した２つの超楕円曲線暗号アルゴリズムの高速化手法、すなわち、
（１Ａ）退化因子をベースポイントに適用した処理例
（１Ｂ）ウィンドウ（Ｗｉｎｄｏｗ）法を適用した処理例
は、それぞれ、異なる手法によって超楕円曲線暗号アルゴリズムの高速化を実現している。
【０１３２】
上述のウィンドウ（Ｗｉｎｄｏｗ）法は、固定因子として退化因子ではないベースポイントを適用して高速化を図っている。このウィンドウ（Ｗｉｎｄｏｗ）法に、上述した処理例［（１Ａ）退化因子をベースポイントに適用した処理例］で説明した退化因子をベースポイントとして使うことができれば、前述の［（１Ｂ）ウィンドウ（Ｗｉｎｄｏｗ）法を適用した処理例］において説明した図５のステップＳ１５４の処理において実行する加算処理、具体的には、前述のスカラー倍算［Ｄ＝ｄＤ］の演算アルゴリズム［アルゴリズム５］における加算演算処理（２．２）のステップにおいて実行する加算処理を退化因子を適用した加算演算として実行することができる。退化因子を含む加算は、退化因子を含まない加算に比べて高速に演算することができるため、ウィンドウ（Ｗｉｎｄｏｗ）法を適用した処理のさらなる高速化が実現される。
【０１３３】
しかし、［（１Ｂ）ウィンドウ（Ｗｉｎｄｏｗ）法を適用した処理例］において、退化因子をベースポイントとして適用し、暗号解析に対して安全な処理構成とするためには、前述のウィンドウ法の適用例で説明した図５のステップＳ１５２の処理において算出する事前計算点：Ｄ〜（２ｗ−１）Ｄ（ただし、ｗはｗｉｎｄｏｗ  ｓｉｚｅ）の因子が全て退化因子である設定とすることが必要である。
【０１３４】
ベースポイントＤ以外の因子、すなわち事前算出データを退化因子ではない因子に設定し、ウィンドウ（Ｗｉｎｄｏｗ）法を適用することも可能ではあるが、このような処理構成は様々な攻撃に対する脆弱化を招き、好ましくない。すなわち、このようにベースポイントとしての退化因子を適用した加算処理と、退化因子以外の因子による加算処理を混在させた演算処理を実行する構成とした場合、スカラー倍算［ｄＤ］の計算中に行う因子の加算処理がベースポイントＤを含む場合とそうでない場合とにおいて消費電力や計算時間が明らかに異なってしまい、単純電力解析（ＳＰＡ）やタイミングアタック（ＴＡ）に対しての安全性が損なわれる可能性があるからである。
【０１３５】
従って、攻撃に対する耐性を維持した構成とするためには、事前計算点は全て退化因子とする必要があるが、ベースポイントを退化因子Ｄとして設定したとき、事前計算点、例えば±Ｄ，±３，±５Ｄ，・・・±（２ｗ−１）Ｄのすべてが退化因子となるベースポイントを全数探索して見つけることは技術的に非常に困難である。なぜなら退化因子は全体の因子の中での存在確率が非常に低いため、複数の因子が同時に退化因子である確率はさらに低くなるからである。
【０１３６】
例えば種数（ｇｅｎｕｓ）＝２の曲線を考えるとヤコビ多様体の位数はＨａｓｓｅの定理から＃Ｊ〜ｑ２程度存在する。種数ｇ＝２の曲線において、ｇ＝２未満のウェイト（ｗｅｉｇｈｔ）＝１を持つ退化因子は高々ｑ個しか存在しないから、ヤコビ多様体中からランダムに２つの因子を選んで両方とも退化因子である確率は１／ｑ２になる。ｑは暗号で使う場合、２８０程度の大きな数であるから、ランダムに因子を発生させて全数探索しても見つけることはきわめて困難である。種数（Ｇｅｎｕｓ）＝３の場合も同様である。
【０１３７】
従って、上述した［（１Ｂ）ウィンドウ（Ｗｉｎｄｏｗ）法を適用した処理例］において、退化因子のベースポイントが使えるように拡張するためには事前点として持っておくべき、ベースポイントとベースポイントの奇数倍がすべて退化因子になるようなベースポイントを効率的に見つける方法を構築することが必要となる。
【０１３８】
本発明では、上記課題を具体的に解決する以下の２つの処理例Ａ，Ｂを提案する。
（処理例Ａ）種数（ｇ）２の曲線において、ベースポイントＤと５Ｄとの双方がウェイト（ｗｅｉｇｈｔ）＝１となる退化因子を効率よく探索し、探索した退化因子Ｄ，５Ｄのみを適用して、ｗＮＡＦ展開データを変換し、変換したｗＮＡＦ展開データを適用してスカラー倍算を実行する処理。
（処理例Ｂ）種数（ｇ）３の曲線において、ベースポイントＤと３Ｄとの双方がウェイト（ｗｅｉｇｈｔ）＝２となる退化因子を効率よく探索し、探索した退化因子Ｄ，３Ｄのみを適用して、ｗＮＡＦ展開データを変換し、変換したｗＮＡＦ展開データを適用してスカラー倍算を実行する処理。
【０１３９】
以下、これらの２つの処理例（処理例Ａ），（処理例Ｂ）について、順次、説明する。
【０１４０】
［（処理例Ａ）種数（ｇ）２の曲線において、ベースポイントＤと５Ｄとの双方がウェイト（ｗｅｉｇｈｔ）＝１となる退化因子を効率よく探索し、探索した退化因子Ｄ，５Ｄのみを適用して、ｗＮＡＦ展開データを変換し、変換したｗＮＡＦ展開データを適用してスカラー倍算を実行する処理］
【０１４１】
まず、種数（ｇ）２の超楕円曲線において、ウィンドウ（Ｗｉｎｄｏｗ）法を適用するとともに、退化因子Ｄをベースポイントとして設定し、ウィンドウ法における事前計算データを全て退化因子に基づいて算出可能に設定し、スカラー倍算における加算処理をすべて非退化因子＋退化因子の加算処理として実行することを可能とした構成例について説明する。
【０１４２】
本処理例では、種数（ｇ）２の超楕円曲線において、ベースポイント［Ｄ］と、［５Ｄ］とが共に退化因子、すなわちウェイト＝１の退化因子となるような因子を効率的に検出し、これらのＤ，５Ｄを適用して、ｗＮＡＦ展開データを変換し、退化因子のみからなる変換ｗＮＡＦ展開データを適用してスカラー倍算を実行する。
【０１４３】
前述したように、種数ｇ＝２の曲線において、ｇ＝２未満のウェイト（ｗｅｉｇｈｔ）＝１を持つ退化因子は高々ｑ個しか存在しないから、ヤコビ多様体中からランダムに２つの因子を選んで両方とも退化因子である確率は１／ｑ２になり、ランダムな探索処理によって、ベースポイントＤ、５Ｄが同時に退化因子になるベースポイントＤを探索することは確率的に不可能である。
【０１４４】
本処理例では、Ｄ、５Ｄが共に退化因子となるベースポイントＤの効率的探索を実現する。さらにスカラー倍算の処理においては、事前計算因子として、Ｄ、５Ｄしか用意できないため、これらのＤ，５Ｄを適用してウィンドウ法において必要とする事前計算因子のすべてを算出する。本処理例Ａは以下の３つの処理から構成される。
（処理Ａ１）ベースポイントＤと５Ｄがｗｅｉｇｈｔ１の退化因子であるＤを効率よく見つける処理
（処理Ａ２）退化因子Ｄ，５Ｄを適用して、ｗＮＡＦ展開データを変換し、退化因子のみからなる変換ｗＮＡＦ展開データを生成する処理
（処理Ａ３）退化因子Ｄ、５Ｄのみによって表現された事前算出データを適用したスカラー倍算演算処理
以下、（処理Ａ１）〜（処理Ａ３）の順に、各処理の詳細について説明する。
【０１４５】
（処理Ａ１）ベースポイントＤと５Ｄをｗｅｉｇｈｔ  １である因子を効率よく見つける処理
ベースポイントＤと５Ｄの双方が退化因子、すなわち共にウェイト（ｗ）＝１である因子の探索処理は、Ｄをベースポイントとして５Ｄを計算するまでのＨａｒｌｅｙの公式を使ってｗ（Ｄ）＝ｗ（５Ｄ）＝１となるＤの条件を導く方法を適用した処理として実行される。なお、ｗ（Ｄ）＝ｗ（５Ｄ）＝１は、因子Ｄ，５Ｄが共にウェイト（ｗ）＝１であることを意味する。
【０１４６】
前述したようにＨａｒｌｅｙのアルゴリズムは定義体を素体、種数２の曲線、因子の表現はＭｕｍｆｏｒｄ表現を用いている。種数（ｇｅｎｕｓ）２の任意の被約因子Ｄはマンホード（Ｍｕｍｆｏｒｄ）表現を用いると、有限体Ｆｑ上の元を係数に持つ２次以下の多項式の組、すなわち、
（Ｕ、Ｖ）＝（ｘ２＋ｕ１ｘ＋ｕ０、ｖ１ｘ＋ｖ０）
として表現することができる。
【０１４７】
Ｈａｒｌｅｙの公式を使ってｗ（Ｄ）＝ｗ（５Ｄ）＝１となるＤの条件を導くためにＤから５Ｄを計算する加算連鎖（ａｄｄｉｔｉｏｎ  ｃｈａｉｎ）を考える。ここでＤ、２Ｄ、４Ｄの因子のＭｕｍｆｏｒｄ表現を、
Ｄ＝（ｘ＋ｕ，ｖ）
２Ｄ＝（ｘ２＋ｕ１ｘ＋ｕ０，ｖ１ｘ＋ｖ０）
４Ｄ＝（ｘ２＋ｗ１ｘ＋ｗ０，ｚ１ｘ＋ｚ０）
とする。
【０１４８】
このとき、Ｄ→２Ｄ、２Ｄ→４Ｄ、４Ｄ→５Ｄの算出処理に対応するＨａｒｌｅｙ公式は、
Ｄ→２Ｄ：ＥｘＨａｒＤＢＬ１→２  （Ｔａｂｌｅ  ８）
２Ｄ→４Ｄ：ＨａｒｌｅｙＤＢＬ  （Ｔａｂｌｅ  ２）
４Ｄ→５Ｄ：ＥｘＨａｒＡＤＤ２＋１→１
である。
【０１４９】
上記の各Ｈａｒｌｅｙ公式中、４Ｄ→５Ｄ：ＥｘＨａｒＡＤＤ２＋１→１は、因子Ｄ、４Ｄの加算処理として実行され、先に図１を参照して説明した種数ｇ＝２のＨａｒｌｅｙアルゴリズムの処理における処理としては、ｗｅｉｇｈｔ１＋ｗｅｉｇｈｔ２の加算処理に相当するので対応する公式は、図１に示されるＥｘＨａｒＡＤＤ２＋１→２もしくは例外処理３である。
【０１５０】
上記の各Ｈａｒｌｅｙ公式中、
Ｄ→２Ｄ：ＥｘＨａｒＤＢＬ１→２、および
２Ｄ→４Ｄ：ＨａｒｌｅｙＤＢＬ
の各アルゴリズムを、以下のテーブル［Ｔａｂｌｅ８］、［Ｔａｂｌｅ２］に示す。
【数１７】
2006145945.tif 000019
【０１５１】
【数１８】
2006145945.tif 000020
【０１５２】
ベースポイントＤから、そのスカラー倍によって算出される５Ｄは、上記処理、すなわち、Ｄ→２Ｄ→４Ｄ→５Ｄによって算出可能であり、この算出処理過程において求められる関係式を適用して、Ｄ，５Ｄが退化因子、すなわちウェイト＝１となるベースポイントＤを検出する。ベースポイントＤの探索処理の詳細について、図６を参照して説明する。
【０１５３】
（ステップ１）
因子２ＤのＭｕｍｆｏｒｄ表現、すなわち、
２Ｄ＝（ｘ２＋ｕ１ｘ＋ｕ０，ｖ１ｘ＋ｖ０）
のＭｕｍｆｏｒｄ表現中のパラメータ：ｕ１、ｕ０、ｖ１、ｖ０をＤのＭｕｍｆｏｒｄ表現［Ｄ＝（ｘ＋ｕ，ｖ）］に適用されるｕ、ｖで表現する。
図６に示すステップ１（ｓｔｅｐ１）に示すように、
ｕ１＝ｕ１（ｕ，ｖ）
ｕ０＝ｕ０（ｕ，ｖ）
ｖ１＝ｕ１（ｕ，ｖ）
ｖ０＝ｕ０（ｕ，ｖ）
とする。Ｄ→２Ｄの処理で適用する公式、すなわち、前に示したテーブル８に示す［ＥｘＨａｒＤＢＬ１→２］の公式から導かれた関係式を以下の（式１）に示す。
【数１９】
2006145945.tif 000021
・・・（式１）
【０１５４】
（ステップ２）
因子４ＤのＭｕｍｆｏｒｄ表現、
４Ｄ＝（ｘ２＋ｗ１ｘ＋ｗ０，ｚ１ｘ＋ｚ０）
のｗ１、ｗ０、ｚ１、ｚ０をＤのＭｕｍｆｏｒｄ表現［Ｄ＝（ｘ＋ｕ，ｖ）］に適用されるｕ、ｖで表現する。
図６に示すステップ２（ｓｔｅｐ２）に示すように、
ｗ１＝ｗ１（ｕ，ｖ）
ｗ０＝ｗ０（ｕ，ｖ）
ｚ１＝ｚ１（ｕ，ｖ）
ｚ０＝ｚ０（ｕ，ｖ）
とする。２Ｄ→４Ｄの処理で適用する公式、すなわち、テーブル２に示す［ＨａｒｌｅｙＤＢＬ］の公式中、Ｔａｂｌｅ２に示すｓｔｅｐ１のｒ、ｓｔｅｐ３のｔ１、ｔ０とｕ１、ｕ０、ｖ１、ｖ０の関係式を導き、ｗ１、ｗ０、ｚ１、ｚ０をｕ１、ｕ０、ｖ１、ｖ０、ｔ１、ｔ０、ｒで表現する。導かれた関係式を以下の（式２）に示す。
【数２０】
2006145945.tif 000022
・・・（式２）
【０１５５】
さらに、上記（ステップ１）の結果を代入することでｗ１、ｗ０、ｚ１、ｚ０をＤのＭｕｍｆｏｒｄ表現に適用されるｕ、ｖだけで表現する。
【０１５６】
（ステップ３）
５Ｄ＝Ｄ＋４Ｄがｗｅｉｇｈｔ１になる条件を用いてｕだけの１変数方程式を導く。
Ｄ＋４Ｄを計算する方程式はＥｘＨａｒＡＤＤ１＋２→１である。これは、上述したように、先に説明した図１のＨａｒｌｅｙの加算公式の分岐処理において、因子Ｄ、４Ｄの加算処理は、ｗｅｉｇｈｔ１＋ｗｅｉｇｈｔ２の加算処理に相当するので対応する公式は、図１に示されるＥｘＨａｒＡＤＤ２＋１→２もしくは例外処理３である。
【０１５７】
ＥｘＨａｒＡＤＤ２＋１→２のアルゴリズムを、以下のテーブル［Ｔａｂｌｅ３］に示す。
【数２１】
2006145945.tif 000023
【０１５８】
上記テーブル３（Ｔａｂｌｅ３）から理解されるようにＥｘＨａｒＡＤＤ２＋１→２の出力が退化因子（ウェイト＝１）になる分岐はないので、出力が退化因子になる条件を求めるには例外処理３を考える必要がある。例外処理３において、５Ｄが退化因子、すなわち、ウェイト＝１である因子になる条件は、Ｄおよび４Ｄが以下の［条件］を満足する場合である。すなわち、
［条件］
Ｄ＝Ｐ−Ｐ∞
４Ｄ＝−Ｐ＋Ｑ−２Ｐ∞
を満足する場合である。
【０１５９】
この場合、以下の２つの条件が導かれる。この２つの条件に対応してベースポイントＤのｕ、ｖに関する２つの方程式を成立する。
（条件１）
ｗ１（ｕ、ｖ）×ｕ＋ｗ０（ｕ、ｖ）＝０
・・・（式３ａ）
（条件２）
ｚ１（ｕ、ｖ）×ｕ＋ｚ０（ｕ、ｖ）＝ｖ＋ｈ（ｕ）
・・・（式４ａ）
条件１、２に対応する方程式をそれぞれ（式３ａ）、（式４ａ）とする。この条件１，２が図６のステップ３（ｓｔｅｐ３）に示す条件である。
【０１６０】
上記式３ａ、式４ａはそれぞれＤのＭｕｍｆｏｒｄ表現としてのＤ＝（ｘ＋ｕ，ｖ）に適用されるｕ、ｖに関する方程式である。しかし、以下に述べる方法によって上記式３、式４ａは、ともにｕに関する１変数方程式に変形することができる。
【０１６１】
すなわち、超楕円曲線の定義式からｖ２は、
ｖ２＝ｈ（ｕ）ｖ＋ｆ（ｕ）
である。
この式を使うと、ｖの２次以降の式は全てｖの１次式に変形することができる。これを繰り返すことによってｖの次数を下げていくことができる。これを用いて、式３ａを形式的に表現すると、
Ｇ１（ｕ、ｖ）＝ａ１（ｕ）＋ｂ１（ｕ）ｖ＝０
の形式に変形することができる。さらにＧの共役な多項式を
Ｇ１（ｕ、ｖ）＝ａ１（ｕ）＋ｂ１（ｕ）（ｖ＋ｈ（ｕ））
と定義すると、
Ｎ１＝Ｇ１×Ｇ１'＝ａ１２＋ａ１ｂ１ｈ＋ｂ１２ｆとなり、最終的にｕだけの１変数方程式として下記の（式３ｂ）、すなわち、  Ｎ１（ｕ）＝０
・・・（式３ｂ）
を導くことができる。
【０１６２】
式４ａについても同様の処理を行う。同様に導かれたｕの１変数方程式を、
Ｎ２（ｕ）＝０
・・・（式４ｂ）
とする。
【０１６３】
上記式（式３ｂ）、（式４ｂ）中のＮ１、Ｎ２は具体的に上述したステップに沿って計算していくと、それぞれ５３次、７２次のｕの多項式となる。１変数の有限次数の多項式方程式は一般に多項式時間で解けることが知られている。これらの多項式それぞれについて、ｕの解を求める。
【０１６４】
（ステップ４）
ステップ３で求めた２つの方程式の解が共通解を持つ場合、その共通解を因子のｕとする。
算出したｕに基づいて、超楕円曲線の式ｖ２＋ｈ（ｕ）＝ｆ（ｕ）に、ｕを代入して、ｖを求める。
算出したｕ、ｖに基づいて、ベースポイントＤとしての退化因子：Ｄ＝（ｘ−ｕ、ｖ）を決定する。
【０１６５】
このようにして算出されたベースポイント：Ｄは、ウェイトが１の退化因子であり、また、５Ｄについてもウェイト＝１の退化因子であることが保証される。
【０１６６】
図７に示すフローチャートを参照して、退化因子Ｄ、５Ｄを生成する処理手順について説明する。まず、ステップＳ２０１において、超楕円曲線のパラメータを入力する。前述したように、超楕円曲線では曲線を特徴づける値は種数（ｇｅｎｕｓ）ｇである。ｐを素数、ｎを正の整数、ｑ＝ｐｎとする。このとき有限体Ｆｑ上で定義される種数ｇの超楕円曲線Ｃは以下の方程式、
ｙ２＋ｈ（ｘ）ｙ＝ｆ（ｘ）
で定義される。ここで、ｈ（ｘ），ｆ（ｘ）∈Ｆｑ［ｘ］，ｆ（ｘ）は、次数２ｇ＋１のｍｏｎｉｃ多項式である。
【０１６７】
ここでは超楕円曲線の方程式をｙ２＋ｈ（ｘ）＝ｆ（ｘ）、
ｈ（ｘ）＝ｘ２＋ｈ１ｘ＋ｈ０、
ｆ（ｘ）＝ｘ５＋ｆ３ｘ３＋ｆ１ｘ＋ｆ０
としている。
このように、種数ｇ＝２の超楕円曲線は、パラメータとしてｈ１，ｈ０，ｆ３，ｆ１，ｆ０を設定することで定義される。
【０１６８】
ステップＳ２０２において、５Ｄ＝Ｄ＋４Ｄがｗｅｉｇｈｔ１になる条件を用いてｕだけの１変数方程式、すなわち、上述した式、
Ｎ１（ｕ）＝０    ・・・（式３ｂ）
Ｎ２（ｕ）＝０    ・・・（式４ｂ）
から共通解（ｕ）を求める。
【０１６９】
これは、前述したように、因子Ｄ、４Ｄの加算処理として実行される５Ｄ＝Ｄ＋４Ｄの処理において、図１に示す例外処理３において、５Ｄが退化因子、すなわち、ウェイト＝１である因子になる条件として設定される［条件］から導かれる式である。すなわち、
［条件］
Ｄ＝Ｐ−Ｐ∞
４Ｄ＝−Ｐ＋Ｑ−２Ｐ∞
から下記の条件式、すなわち、
（条件１）
ｗ１（ｕ、ｖ）×ｕ＋ｗ０（ｕ、ｖ）＝０
・・・（式３ａ）
（条件２）
ｚ１（ｕ、ｖ）×ｕ＋ｚ０（ｕ、ｖ）＝ｖ＋ｈ（ｕ）
・・・（式４ａ）
を導き、さらに、超楕円曲線の定義式
ｖ２＝ｈ（ｕ）ｖ＋ｆ（ｕ）
を適用して、式３ａ，式４ａにおけるｖの２次以降の式を全てｖの１次式に変形する処理を行なうことによってｖの次数を下げ、式３ａを、
Ｇ１（ｕ、ｖ）＝ａ１（ｕ）＋ｂ１（ｕ）ｖ＝０
の形式に変形し、さらにＧの共役な多項式を
Ｇ１（ｕ、ｖ）＝ａ１（ｕ）＋ｂ１（ｕ）（ｖ＋ｈ（ｕ））
と定義することで、
Ｎ１＝Ｇ１×Ｇ１'＝ａ１２＋ａ１ｂ１ｈ＋ｂ１２ｆとして、最終的にｕだけの１変数方程式として、
Ｎ１（ｕ）＝０    ・・・（式３ｂ）
を導き、同様の処理によって、
Ｎ２（ｕ）＝０    ・・・（式４ｂ）
を導いたものである。
【０１７０】
ステップＳ２０２では、これらの式、
Ｎ１（ｕ）＝０    ・・・（式３ｂ）
Ｎ２（ｕ）＝０    ・・・（式４ｂ）
から共通解（ｕ）を求める。
【０１７１】
これらの式に共通解が存在しない場合（ステップＳ２０３：Ｎｏ）は、ステップＳ２０１に戻り、パラメータ：ｈ１，ｈ０，ｆ３，ｆ１，ｆ０を再設定して、共通解（ｕ）の算出を実行する。
【０１７２】
共通解（ｕ）が算出される（ステップＳ２０３：Ｙｅｓ）と、ステップＳ２０４に進み、超楕円曲線の式：ｖ２＋ｈ（ｕ）＝ｆ（ｕ）に代入してｖを求める。さらに、ステップＳ２０５において、算出したｕ，ｖに基づいて、ベースポイントとしての退化因子Ｄ＝（ｘ−ｕ、ｖ）を決定する。
【０１７３】
（処理Ａ２）退化因子Ｄ，５Ｄを適用して、ｗＮＡＦ展開データを変換し、退化因子のみからなる変換ｗＮＡＦ展開データを生成する処理
上述した処理によって、種数（ｇ）＝２の超楕円曲線において、ウェイト（ｗｅｉｇｈｔ）＝１となる退化因子としてのベースポイントＤ、５Ｄを検出することができる。次に、これらの因子Ｄ，５Ｄを適用して単純電力解析（ＳＰＡ）などの解析攻撃に対する耐性を保持したｗＮＡＦ（width−wNon-Adjacent form）展開データの生成を行なう処理について説明する。
【０１７４】
ｗＮＡＦ展開とは、前述したウィンドウ法の処理において説明したように、スカラー倍演算処理［Ｄ＝ｄＤ］において適用するスカラー値［ｄ］を所定桁数からなる分割ブロックに分割する処理であり、乗数として設定されるスカラー値：ｄを、
｜００・・０ｘ｜００・・０ｘ｜００・・０ｘ｜・・
ただし、ｘは奇数（±１，±３・・）
となる分割ブロックに分割する処理である。
【０１７５】
上述した処理によって検出した退化因子Ｄ、５Ｄのみでは、ＳＰＡ耐性のあるスカラー倍算を行うことができない。例えば前述したウィンドウ法（ｗＮＡＦ）において、スカラー値［ｄ］の分割ブロックサイズ（桁数）を２とした場合、
｜０１｜、｜０３｜、｜０（−１）｜、｜０（−３）｜
に対応するブロック値に基づく算出データとして、±Ｄ，±３Ｄの各値を事前算出データとしてテーブルに保存することが必要となる。
また、スカラー値［ｄ］の分割ブロックサイズ（桁数）を３とした場合、
｜００１｜、｜００３｜、｜００５｜、｜００７｜、
｜００（−１）｜、｜００（−３）｜、｜００（−５）｜、｜００（−７）｜、
に対応するブロック値に基づく算出データとして、±Ｄ、±３Ｄ、±５Ｄ、±７Ｄの各値を事前算出データとしてテーブルに保存することが必要となる。
【０１７６】
しかし、本処理例においては、上述した処理によって生成される退化因子は、Ｄ、５Ｄのみであるので、例えば、スカラー値［ｄ］の分割ブロックサイズ（桁数）を３とした場合、事前計算データとして必要となる±Ｄ、±３Ｄ、±５Ｄ、±７Ｄの一部が算出されておらず、このままでは、前述のウィンドウ法を実行することができない。例えばＤ、５Ｄ以外に必要となる３Ｄ、７Ｄ等を、別に算出して事前算出データとして適用することも可能ではあるが、この場合には、前述したようにこれらの値が退化因子以外の因子に設定される可能性が非常に高く、スカラー倍算において実行する加算演算において退化因子を含んだ加算処理と、非退化因子のみの加算処理が混在してしまうことになる。この場合、これらの演算による消費電力、時間などが明らかに異なることに起因して単純電力解析（ＳＰＡ）などの各種攻撃に対する脆弱性が発生するという問題がある。
【０１７７】
本処理例では、上述した処理によって検出した退化因子Ｄ，５Ｄを適用して単純電力解析（ＳＰＡ）などの解析攻撃に対する耐性を有するウィンドウ法（ｗｉｄｏｗ法）によるスカラー倍算を実現する。
【０１７８】
退化因子Ｄ，５Ｄを適用して単純電力解析（ＳＰＡ）に対する耐性を有するウィンドウ法（ｗｉｄｏｗ法）によるスカラー倍算を実現するための改良されたｗＮＡＦ展開をここではｗＮＡＦ（１、５）と呼ぶことにする。ｗＮＡＦ（１、５）は、従来のｗＮＡＦ展開データの変換処理を伴う処理として実行され、従来のｗＮＡＦ展開データに対して変換テーブルを適用した変換処理を行う。ｗＮＡＦ展開データの変換処理は、図８に示す処理ステップによって実現される。
【０１７９】
まず、ステップＳ２３１において、先の［（１Ｂ）ウィンドウ（Ｗｉｎｄｏｗ）法を適用した処理例］において、図５を参照して説明したステップＳ１５３の処理と同様の処理によって通常のｗＮＡＦ展開を行う。
【０１８０】
すなわち、乗数として設定されるスカラー値：ｄをｗＮＡＦ展開する。ｗＮＡＦ展開は、上述したように、乗数として設定されるスカラー値：ｄを、
｜００・・０ｘ｜００・・０ｘ｜００・・０ｘ｜・・
ただし、ｘは奇数（±１，±３・・）
となる分割ブロックに分割する処理である。
【０１８１】
ここでは、ウィンドウサイズ＝３とした処理例について説明する。ウィンドウサイズ＝３として乗数ｄをｗＮＡＦ展開する。テーブルに保持すべき事前算出データ［ｄＤ］としては、±Ｄ，±３，±５Ｄ，±７Ｄが選択される。
【０１８２】
次に、ステップＳ２３２において、テーブルに保持すべき事前算出データである、±Ｄ，±３，±５Ｄ，±７Ｄを、図８（ｂ）に示す変換テーブルを使って算出されている退化因子Ｄ，５Ｄによって表現可能な±１、±５のみを適用した表現形式に変換する。
【０１８３】
図８（ｂ）に示す変換テーブルは以下の構成を持つ。
＋Ｄ算出に適用する分割ブロック    ［００１］→［００１］に変換（変更なし）、
＋３Ｄ算出に対応する分割ブロック  ［００３］→［０１１］に変換、
＋５Ｄ算出に対応する分割ブロック  ［００５］→［００５］に変換（変更なし）、
＋７Ｄ算出に対応する分割ブロック  ［００７］→［０１５］に変換、
−Ｄ算出に適用する分割ブロック    ［００（−１）］→［００（−１）］に変換（変更なし）、
−３Ｄ算出に対応する分割ブロック  ［００（−３）］→［０（−１）（−１）］に変換、
−５Ｄ算出に対応する分割ブロック  ［００（−５）］→［００（−５）］に変換（変更なし）、
−７Ｄ算出に対応する分割ブロック  ［００（−７）］→［０（−１）（−５）］に変換、
【０１８４】
この変換テーブルによる変換により、テーブルに保持すべき事前算出データである［±Ｄ，±３，±５Ｄ，±７Ｄ］を、退化因子Ｄ，５Ｄによって表現可能な±１、±５のみを適用した表現形式に変換する。
【０１８５】
上述の処理によって、テーブルに保持すべき事前算出データである［±Ｄ，±３，±５Ｄ，±７Ｄ］は、退化因子Ｄ，５Ｄによって表現可能な±１、±５のみを適用した表現形式に変換される。スカラー倍算Ｄ＝ｄＤは、この表現形式を適用して、退化因子Ｄ，５Ｄを適用した加算処理、すなわち、退化因子のみによる加算処理を含む演算処理によって実現される。
【０１８６】
（処理Ａ３）退化因子Ｄ、５Ｄのみによって表現された事前算出データを適用したスカラー倍算演算処理
次に、上述の処理によって、テーブルに保持すべき事前算出データである［±Ｄ，±３，±５Ｄ，±７Ｄ］を、退化因子Ｄ，５Ｄのみを適用した変換データとし、これらのデータを適用して実行するスカラー倍算処理［Ｄ＝ｄＤ］のアルゴリズムについて説明する。
【０１８７】
本処理例におけるスカラー倍算アルゴリズム［アルゴリズム７］を以下に示す。
【数２２】
2006145945.tif 000024
【０１８８】
上記アルゴリズムにおいて、δはｄ［ｉ］＝０の時、０、それ以外のｄ［ｉ］に対しては１になる関数である。［〜］はδのビット反転を表しており、δが１のとき０、δが０のとき１をとる。
【０１８９】
上記アルゴリズムでは、±Ｄ，±３，±５Ｄ，±７Ｄを、予め検出済みの退化因子Ｄ，５Ｄのみによって表現し、スカラー倍算アルゴリズムにおいて発生する加算処理は、すべて退化因子＋非退化因子の加算処理として実現されている。さらに変換後のテーブルにおいて２ｎｄビットが０の場合、ダミーの演算を行なっている。従って、高速化演算が可能であり、また非退化因子による加算処理が混在しないので、退化因子と非退化因子の演算処理時間や、演算処理に伴う消費電力の差異が発生せず、演算シーケンスの解析としてのＳＰＡ、ＴＡ解析に対する耐性も損なわれることのない安全で高速な演算が実現される。
【０１９０】
上述した種数（ｇ）２の曲線において、ベースポイントＤと５Ｄとの双方がウェイト（ｗｅｉｇｈｔ）＝１となる退化因子を探索し、探索した退化因子Ｄ，５Ｄのみを適用して、ｗＮＡＦ展開データを変換し、変換したｗＮＡＦ展開データを適用してスカラー倍算を実行する処理の全体シーケンスについて、図９に示すフローチャートを参照して説明する。
【０１９１】
まず、図９のステップＳ２５１において、ベースポイント［Ｄ］と、［５Ｄ］とが共に退化因子、すなわちウェイト＝１の退化因子となるような因子を検出する。この退化因子検出処理は、先に、図６、図７を参照して説明した処理によって求められる。すなわち、図１に示す例外処理３において、５Ｄが退化因子、すなわち、ウェイト＝１である因子になる条件として設定される［条件］と、超楕円曲線の定義式：ｖ２＝ｈ（ｕ）ｖ＋ｆ（ｕ）とに基づいて、前述した
Ｎ１（ｕ）＝０    ・・・（式３ｂ）
Ｎ２（ｕ）＝０    ・・・（式４ｂ）
から共通解（ｕ）を求め、求めたｕから、超楕円曲線の式：ｖ２＋ｈ（ｕ）＝ｆ（ｕ）に代入してｖを求め、さらに、算出したｕ，ｖに基づいて、ベースポイントとしての退化因子Ｄ＝（ｘ−ｕ、ｖ）を決定する処理として実行する。
【０１９２】
ステップＳ２５２では、ステップＳ２５１において算出したベースポイントＤに基づいて、もう１つの退化因子５Ｄを事前算出する。算出処理は、
Ｄ→２Ｄ：ＥｘＨａｒＤＢＬ１→２  （Ｔａｂｌｅ  ８）
２Ｄ→４Ｄ：ＨａｒｌｅｙＤＢＬ  （Ｔａｂｌｅ  ２）
４Ｄ→５Ｄ：ＥｘＨａｒＡＤＤ２＋１→１
上記算出処理工程によって実行できる。
【０１９３】
ステップＳ２５３では、スカラー倍算ｄ＝ｄＤにおける乗算データとしてのスカラー値ｄをｗＮＡＦ展開し、さらに、ｗＮＡＦ展開データをステップＳ２５１，Ｓ２５２において算出した退化因子Ｄ，５Ｄを適用して変換した変換ｗＮＡＦ展開データを生成する。すなわち、ウィンドウサイズ＝３の場合、通常のｗＮＡＦ展開処理によって事前算出データとして必要とされる［±Ｄ，±３，±５Ｄ，±７Ｄ］を退化因子Ｄ，５Ｄのみによって表現した変換ｗＮＡＦ展開データを生成する。変換処理には、先に図８を参照して説明した変換テーブルを適用し、変換テーブルに従った変換処理が実行される。
【０１９４】
最後に、ステップＳ２５４において、スカラー倍算Ｄ＝ｄＤを実行する。このスカラー倍算では、退化因子Ｄ、５Ｄのみによって表現された事前算出データを適用したスカラー倍算演算処理として実行され、先に説明したアルゴリズム［アルゴリズム７］に従った処理として実行される。このスカラー倍算では、通常のｗＮＡＦ適用処理において、必要となる事前算出データである［±Ｄ，±３，±５Ｄ，±７Ｄ］を、退化因子Ｄ，５Ｄのみを適用した処理に変更しており、スカラー倍算アルゴリズムにおいて発生する加算処理は、すべて退化因子による加算処理として実現される。従って、高速化演算が可能であり、また非退化因子による加算処理が混在しないので、退化因子と非退化因子の演算処理時間や、演算処理に伴う消費電力の差異が発生せず、演算シーケンスの解析としてのＳＰＡ、ＴＡ解析に対する耐性も損なわれることのない安全で高速な演算が実現される。
【０１９５】
［（処理例Ｂ）種数（ｇ）３の曲線において、ベースポイントＤと３Ｄとの双方がウェイト（ｗｅｉｇｈｔ）＝２となる退化因子を効率よく検出し、検出した退化因子Ｄ，３Ｄのみを適用して、ｗＮＡＦ展開データを変換し、変換したｗＮＡＦ展開データを適用してスカラー倍算を実行する処理］
【０１９６】
次に、種数（ｇ）３の曲線において、ベースポイントＤと３Ｄとの双方がウェイト（ｗｅｉｇｈｔ）＝２となる退化因子を効率よく検出し、検出した退化因子Ｄ，３Ｄのみを適用して、ｗＮＡＦ展開データを変換し、変換したｗＮＡＦ展開データを適用してスカラー倍算を実行する処理について説明する。
【０１９７】
本処理例では、種数（ｇ）３の超楕円曲線において、ベースポイント［Ｄ］と、［３Ｄ］とが共に退化因子、すなわちウェイト＝２の退化因子となるような因子を効率的に検出し、これらのＤ，３Ｄを適用して、ｗＮＡＦ展開データを変換し、退化因子のみからなる変換ｗＮＡＦ展開データを適用してスカラー倍算を実行する。
【０１９８】
前述したように、ランダムな探索処理によって、ベースポイントＤ、３Ｄが同時に退化因子になるベースポイントＤを全数探索することは確率的に不可能である。本処理例では、Ｄ、３Ｄが共に退化因子となるベースポイントＤの効率的探索を実現する。さらにスカラー倍算の処理においては、事前計算因子として、Ｄ、３Ｄを用意し、これらのＤ，３Ｄを適用してウィンドウ法において必要とする事前計算因子のすべてを算出する。種数（ｇ）３の場合、種数（ｇ）２の場合のように変換が必要とならないのでＤ，３Ｄのみで十分である。本処理例Ａは以下の３つの処理から構成される。
（処理Ｂ１）ベースポイントＤと３Ｄがｗｅｉｇｈｔ２の退化因子であるＤを効率よく見つける処理
（処理Ｂ２）退化因子Ｄ、３Ｄのみによって表現された事前算出データを適用したスカラー倍算演算処理
以下、（処理Ｂ１）〜（処理Ｂ２）の順に、各処理の詳細について説明する。
【０１９９】
（処理Ｂ１）ベースポイントＤと３Ｄをｗｅｉｇｈｔ  ２である因子を効率よく見つける処理
ベースポイントＤと３Ｄの双方が退化因子、すなわち共にウェイト（ｗ）＝２である因子の探索処理は、Ｄをベースポイントとして３Ｄを計算するまでのＨａｒｌｅｙの公式を使ってｗ（Ｄ）＝ｗ（３Ｄ）＝２となるＤの条件を導く方法を適用した処理として実行される。なお、ｗ（Ｄ）＝ｗ（３Ｄ）＝３は、因子Ｄ，３Ｄが共にウェイト（ｗ）＝２であることを意味する。
【０２００】
ｗ（Ｄ）＝ｗ（３Ｄ）＝２となるＤの条件を導くためにＤから３Ｄを計算する加算連鎖（ａｄｄｉｔｉｏｎ  ｃｈａｉｎ）を考える。ここでＤ、２Ｄの因子のＭｕｍｆｏｒｄ表現を、
Ｄ＝（ｘ２＋ｕ２１ｘ＋ｕ２０，ｖ２１ｘ＋ｖ２０）
２Ｄ＝（ｘ３＋ｕ１２ｘ２＋ｕ１１ｘ＋ｕ１０，ｖ１２ｘ２＋ｖ１１ｘ＋ｖ１０）
とする。
【０２０１】
このとき、Ｄ→２Ｄ、２Ｄ→３Ｄの算出処理に対応するＨａｒｌｅｙ公式は、
Ｄ→２Ｄ：ＥｘＨａｒＤＢＬ２→３  （Ｔａｂｌｅ  ９）
２Ｄ→３Ｄ：ＥｘＨａｒＡＤＤ２＋３→２  （Ｔａｂｌｅ  ７）
である。
【０２０２】
上記の各Ｈａｒｌｅｙ公式、
Ｄ→２Ｄ：ＥｘＨａｒＤＢＬ２→３  （Ｔａｂｌｅ  ９）
２Ｄ→３Ｄ：ＥｘＨａｒＡＤＤ２＋３→２  （Ｔａｂｌｅ  ７）
の各アルゴリズムを、以下のテーブル［Ｔａｂｌｅ９］、［Ｔａｂｌｅ７］に示す。
【数２３】
2006145945.tif 000025
【０２０３】
【数２４】
2006145945.tif 000026
【０２０４】
ベースポイントＤから、そのスカラー倍によって算出される３Ｄは、上記処理、すなわち、Ｄ→２Ｄ→３によって算出可能であり、この算出処理過程において求められる関係式を適用して、Ｄ，３Ｄが退化因子、すなわちウェイト＝２となるベースポイントＤを検出する。ベースポイントＤの検出処理の詳細について、図１０を参照して説明する。
【０２０５】
（ステップ１）
因子２ＤのＭｕｍｆｏｒｄ表現、
２Ｄ＝（ｘ３＋ｕ１２ｘ２＋ｕ１１ｘ＋ｕ１０，ｖ１２ｘ２＋ｖ１１ｘ＋ｖ１０）
のｕ１２、ｕ１１、ｕ１０、ｖ１２、ｖ１１、ｖ１０をＤのＭｕｍｆｏｒｄ表現［Ｄ＝（ｘ２＋ｕ２１ｘ＋ｕ２０，ｖ２１ｘ＋ｖ２０）］に適用されるｕ２１、ｕ２０、ｖ２１、ｖ２０で表現する。
図１０に示すステップ１（ｓｔｅｐ１）に示すように、
ｕ１２＝ｕ１２（ｕ２１、ｕ２０、ｖ２１、ｖ２０）
ｕ１１＝ｕ１１（ｕ２１、ｕ２０、ｖ２１、ｖ２０）
ｕ１０＝ｕ１０（ｕ２１、ｕ２０、ｖ２１、ｖ２０）
ｖ１２＝ｖ１２（ｕ２１、ｕ２０、ｖ２１、ｖ２０）
ｖ１１＝ｖ１１（ｕ２１、ｕ２０、ｖ２１、ｖ２０）
ｖ１０＝ｖ１０（ｕ２１、ｕ２０、ｖ２１、ｖ２０）
とする。Ｄ→２Ｄの処理で適用する公式、すなわち、前に示したテーブル９に示す［ＥｘＨａｒＤＢＬ２→３］の公式から導かれた関係式を以下の（式５）に示す。
【数２５】
2006145945.tif 000027
・・・（式５）
【０２０６】
上記式（式５）中のｓ１，ｓ０，ｒは、以下の式（式６）によって与えられる（ｕ２１、ｕ２０、ｖ２１、ｖ２０）の関数である。
【数２６】
2006145945.tif 000028
・・・（式６）
【０２０７】
（ステップ２）
３Ｄ＝Ｄ＋２Ｄがｗｅｉｇｈｔ２になる条件を用いて、探索する方程式［ｔ１＝０］を求める。
３Ｄ＝Ｄ＋２Ｄがｗｅｉｇｈｔ２になる条件を導くために、
２Ｄ→３Ｄ：ＥｘＨａｒＡＤＤ３＋２→３  （Ｔａｂｌｅ  ７）のアルゴリズムについて考察する。上記したテーブル７（Ｔａｂｌｅ  ７）のステップ３において、
ｔ１＝０
になった場合、ステップ６で求められる３ＤのＭｕｍｆｏｒｄ表現としてのｕ３の多項式次数が２次、すなわちｗｅｉｇｈｔ２となる。従って、
ｔ１＝０
が、３Ｄ＝Ｄ＋２Ｄがｗｅｉｇｈｔ２になる条件である。
図１０、ステップ２に示すように、
ｔ１＝ｔ１（ｕ１２、ｕ１１、ｕ１０、ｖ１２、ｖ１１、ｖ１０、ｕ２１、ｕ２０、ｖ２１、ｖ２０）として、Ｄ，２ＤのＭｕｍｆｏｒｄ表現、
Ｄ＝（ｘ２＋ｕ２１ｘ＋ｕ２０，ｖ２１ｘ＋ｖ２０）
２Ｄ＝（ｘ３＋ｕ１２ｘ２＋ｕ１１ｘ＋ｕ１０，ｖ１２ｘ２＋ｖ１１ｘ＋ｖ１０）
の係数による関数とする。
ｔ１＝ｔ１（ｕ１２、ｕ１１、ｕ１０、ｖ１２、ｖ１１、ｖ１０、ｕ２１、ｕ２０、ｖ２１、ｖ２０）は、以下の式（式７）として示される。
【数２７】
2006145945.tif 000029
・・・（式７）
【０２０８】
さらに、上記式（式７）を整理して、ＤのＭｕｍｆｏｒｄ表現、
Ｄ＝（ｘ２＋ｕ２１ｘ＋ｕ２０，ｖ２１ｘ＋ｖ２０）
の係数（ｕ２１、ｕ２０、ｖ２１、ｖ２０）のみの式に変換する。この式変換は、ステップ１で求めた関係式、すなわち、
ｕ１２＝ｕ１２（ｕ２１、ｕ２０、ｖ２１、ｖ２０）
ｕ１１＝ｕ１１（ｕ２１、ｕ２０、ｖ２１、ｖ２０）
ｕ１０＝ｕ１０（ｕ２１、ｕ２０、ｖ２１、ｖ２０）
ｖ１２＝ｖ１２（ｕ２１、ｕ２０、ｖ２１、ｖ２０）
ｖ１１＝ｖ１１（ｕ２１、ｕ２０、ｖ２１、ｖ２０）
ｖ１０＝ｖ１０（ｕ２１、ｕ２０、ｖ２１、ｖ２０）
を適用する。
このようにして求められた条件式
ｔ１＝ｔ１（ｕ２１、ｕ２０、ｖ２１、ｖ２０）＝０
を求める。
【０２０９】
（ステップ３）
次に、図１０のステップ３に示すように、ステップ２で求めた条件式、
ｔ１＝ｔ１（ｕ２１、ｕ２０、ｖ２１、ｖ２０）＝０
に含まれるパラメータ（ｕ２１、ｕ２０、ｖ２１、ｖ２０）を、超楕円曲線上の点：Ｐ（ｘ１，ｙ１）、Ｑ（ｘ２，ｙ２）で表現する。
【０２１０】
前述したように、種数（ｇｅｎｕｓ）３の任意の被約因子Ｄはマンホード（Ｍｕｍｆｏｒｄ）表現を用いると有限体Ｆｑ上の元を係数に持つ３次以下の多項式の組、すなわち、
（Ｕ、Ｖ）＝（ｘ３＋ｕ２ｘ２＋ｕ１ｘ＋ｕ０、ｖ２ｘ２＋ｖ１ｘ＋ｖ０）
として表現でき、種数ｇの超楕円曲線Ｃは以下の方程式、
ｙ２＋ｈ（ｘ）ｙ＝ｆ（ｘ）
で定義される。ここで、ｈ（ｘ），ｆ（ｘ）∈Ｆｑ［ｘ］，ｆ（ｘ）は、次数２ｇ＋１のｍｏｎｉｃ多項式である。これらマンホード（Ｍｕｍｆｏｒｄ）表現の定義に基づいて、
ｔ１＝ｔ１（ｕ２１、ｕ２０、ｖ２１、ｖ２０）＝０
に含まれるパラメータ（ｕ２１、ｕ２０、ｖ２１、ｖ２０）を、超楕円曲線上の点：Ｐ（ｘ１，ｙ１）、Ｑ（ｘ２，ｙ２）で表現すると、図１０のステップ３に示す関係式、すなわち、以下の式（式８）に示す関係式が設定される。
ｕ２１＝ｘ１＋ｘ２
ｕ２０＝ｘ１ｘ２
ｖ２１＝（ｙ１＋ｙ２）／（ｘ１＋ｘ２）
ｖ２０＝ｖ２１ｘ１＋ｙ１
・・・（式８）
【０２１１】
上記式（式８）に基づいて、条件式
ｔ１＝ｔ１（ｕ２１、ｕ２０、ｖ２１、ｖ２０）＝０
から、下記式（式９）
ｔ１＝ｔ１（ｘ１、ｘ２、ｙ１、ｙ２）＝０
・・・（式９）
を得る。
【０２１２】
（ステップ４）
次に、図１０のステップ４に示すように、ステップ２で求めた条件式、
ｔ１＝ｔ１（ｘ１、ｘ２、ｙ１、ｙ２）＝０
において、ｘ１、ｙ１を定数とみなし、ｘ２、ｙ２に関する方程式として、さらに、ｙ２の次数を下げていく処理を行なう。これは、先に種数２の場合に説明した（式３ｂ）の生成処理と同様の処理であり、超楕円曲線の定義式、
ｙ２＋ｈ（ｘ）ｙ＝ｆ（ｘ）
を使うことで、ｙ２の次数を下げていくことができる。これを用いて、式９を形式的に表現すると、
Ｇ３（ｘ２，ｙ２）＝ａ３（ｘ２）＋ｂ３（ｘ２）ｙ２＝０
の形式に変形することができる。さらにＧ３の共役な多項式を
Ｇ３'＝ａ３（ｘ２）＋ｂ３（ｘ２）（ｙ２＋ｈ（ｘ２））
と定義すると、
Ｎ３＝Ｇ×Ｇ'＝ａ２＋ａｂｈ＋ｂ２ｆとなり、最終的にｘ２だけの方程式として下記の（式１０）、すなわち、  Ｎ３（ｘ２）＝０
・・・（式１０）
を導くことができる。
【０２１３】
（ステップ５）
上記式
Ｎ３（ｘ２）＝０（式１０）
が解ｘ２を持つことができれば、前述の式（式８）、すなわち、
ｕ２１＝ｘ１＋ｘ２
ｕ２０＝ｘ１ｘ２
ｖ２１＝（ｙ１＋ｙ２）／（ｘ１＋ｘ２）
ｖ２０＝ｖ２１ｘ１＋ｙ１
に基づいて、因子Ｄ＝（ｘ２＋ｕ２１ｘ＋ｕ２０，ｖ２１ｘ＋ｖ２０）
を求めることができる。
【０２１４】
具体的に、上記ステップに従ってｘ２に関する１変数多項式を導くと、２９次の多項式を得ることができる。先に説明した種数（ｇ）＝２の場合と同様、１変数の有限次数の多項式方程式は一般に多項式時間で解けることが知られている。これらの多項式に基づいてｘ２の解を求める。
【０２１５】
（ステップ６）
Ｎ３（ｘ２）＝０
の解ｘ２が算出されたら、超楕円曲線の定義式、
ｙ２＋ｈ（ｘ）ｙ＝ｆ（ｘ）
にｘ２を代入してｙ２求める。
さらに、超楕円曲線上の点：Ｐ（ｘ１，ｙ１）、Ｑ（ｘ２，ｙ２）からベースポイントＤ、すなわち、
Ｄ＝（ｘ２＋ｕ２１ｘ＋ｕ２０，ｖ２１ｘ＋ｖ２０）
を求める。
【０２１６】
このようにして算出されたベースポイント：Ｄは、ウェイトが２の退化因子であり、また、３Ｄについてもウェイト＝２の退化因子であることが保証される。
【０２１７】
図１１に示すフローチャートを参照して、退化因子Ｄ、３Ｄを生成する処理手順について説明する。まず、ステップＳ３０１において、超楕円曲線のパラメータを入力する。前述したように、超楕円曲線では曲線を特徴づける値は種数（ｇｅｎｕｓ）ｇである。ｐを素数、ｎを正の整数、ｑ＝ｐｎとする。このとき有限体Ｆｑ上で定義される種数ｇの超楕円曲線Ｃは以下の方程式、
ｙ２＋ｈ（ｘ）ｙ＝ｆ（ｘ）
で定義される。ここで、ｈ（ｘ），ｆ（ｘ）∈Ｆｑ［ｘ］，ｆ（ｘ）は、次数２ｇ＋１のｍｏｎｉｃ多項式である。
【０２１８】
ここでは超楕円曲線の方程式をｙ２＋ｈ（ｘ）＝ｆ（ｘ）、
ｈ（ｘ）＝ｘ３＋ｈ２ｘ２＋ｈ１ｘ＋ｈ０、
ｆ（ｘ）＝ｘ７＋ｆ５ｘ５＋ｆ４ｘ４＋ｆ３ｘ３＋ｆ２ｘ２＋ｆ１ｘ＋ｆ０
としている。
このように、種数ｇ＝３の超楕円曲線は、パラメータとしてｈ２，ｈ１，ｈ０，ｆ５，ｆ４，ｆ３，ｆ２，ｆ１，ｆ０を設定することで定義される。
【０２１９】
ステップＳ３０２において、ランダムに超楕円曲線上の点Ｐ（ｘ１，ｙ１）を生成し、方程式：Ｎ３（ｘ２，ｘ１，ｙ１）＝０に代入する。
Ｎ３（ｘ２，ｘ１，ｙ１）＝０
は、前述したように、２Ｄ→３Ｄ：ＥｘＨａｒＡＤＤ３＋２→３  （Ｔａｂｌｅ  ７）のアルゴリズム、すなわち上記したテーブル７（Ｔａｂｌｅ  ７）のステップ３において、
ｔ１＝０
が、３Ｄ＝Ｄ＋２Ｄをｗｅｉｇｈｔ２とする条件であることから、導かれる式であり、
マンホード（Ｍｕｍｆｏｒｄ）表現の定義に基づいて、
ｔ１＝ｔ１（ｕ２１、ｕ２０、ｖ２１、ｖ２０）＝０
に含まれるパラメータ（ｕ２１、ｕ２０、ｖ２１、ｖ２０）を、超楕円曲線上の点：Ｐ（ｘ１，ｙ１）、Ｑ（ｘ２，ｙ２）で表現し、
ｕ２１＝ｘ１＋ｘ２
ｕ２０＝ｘ１ｘ２
ｖ２１＝（ｙ１＋ｙ２）／（ｘ１＋ｘ２）
ｖ２０＝ｖ２１ｘ１＋ｙ１
条件式を、
ｔ１＝ｔ１（ｘ１、ｘ２、ｙ１、ｙ２）＝０
として設定し、さらに、ｘ１、ｙ１を定数とみなし、ｘ２、ｙ２に関する方程式として、超楕円曲線の定義式、ｙ２＋ｈ（ｘ）ｙ＝ｆ（ｘ）
を使い、ｙ２の次数を下げ、
ｔ１＝ｔ１（ｘ１、ｘ２、ｙ１、ｙ２）＝０
を、
Ｇ３（ｘ２，ｙ２）＝ａ３（ｘ２）＋ｂ３（ｘ２）ｙ２＝０
の形式に変形し、さらにＧ３の共役な多項式を
Ｇ３'＝ａ３（ｘ２）＋ｂ３（ｘ２）（ｙ２＋ｈ（ｘ２））
と定義して、
Ｎ３＝Ｇ×Ｇ'＝ａ２＋ａｂｈ＋ｂ２ｆとして生成された式である。
【０２２０】
さらに、ステップＳ３０３において、Ｎ３＝Ｇ×Ｇ'＝ａ２＋ａｂｈ＋ｂ２ｆから、
最終的にｘ２だけの方程式、すなわち、前述の式（式１０）  Ｎ３（ｘ２）＝０
に従って、解ｘ２を求める。
【０２２１】
式：  Ｎ３（ｘ２）＝０
に解が存在しない場合（ステップＳ３０４：Ｎｏ）は、ステップＳ３０２に戻り、パラメータ：ｈ２，ｈ１，ｈ０，ｆ５，ｆ４，ｆ３，ｆ２，ｆ１，ｆ０を再設定して、解（ｘ２）の算出を実行する。
【０２２２】
解（ｘ２）が算出される（ステップＳ３０４：Ｙｅｓ）と、ステップＳ３０５に進み、超楕円曲線の式：ｙ２＋ｈ（ｘ）＝ｆ（ｘ）にｘ２を代入してｙ２を求める。さらに、ステップＳ３０６、ステップＳ３０７において、超楕円曲線上の点：Ｐ（ｘ１，ｙ１）、Ｑ（ｘ２，ｙ２）からベースポイントＤ、すなわち、
Ｄ＝（ｘ２＋ｕ２１ｘ＋ｕ２０，ｖ２１ｘ＋ｖ２０）
を求める。
【０２２３】
このようにして算出されたベースポイント：Ｄは、ウェイトが２の退化因子であり、また、３Ｄについてもウェイト＝２の退化因子であることが保証される。
【０２２４】
（処理Ｂ２）退化因子Ｄ、３Ｄのみによって表現された事前算出データを適用したスカラー倍算演算処理
【０２２５】
次に、退化因子Ｄ，３Ｄのみを適用し、事前算出データ［±Ｄ，±３］を用いたスカラー倍算処理［Ｄ＝ｄＤ］のアルゴリズムについて説明する。なお、この処理例では、ウィンドウ法（ｗＮＡＦ）においてウィンドウサイズ＝２とした処理例であり、ｗＮＡＦ法において必要となる事前算出データは、［±Ｄ，±３］であって、前述の処理において求めた退化因子Ｄ，３Ｄから直接算出可能な値となる。従って、前述の処理例、すなわち、種数２としてウィンドウサイズ＝３とした場合のように、変換テーブルを適用した変換処理は不要となる。
【０２２６】
本処理例におけるスカラー倍算アルゴリズム［アルゴリズム８］を以下に示す。
【数２８】
2006145945.tif 000030
【０２２７】
上記アルゴリズムにおいて、前述の従来のウィンドウ法（ｗＮＡＦ）において説明したアルゴリズム（アルゴリズム６）との差異は、２つの退化因子Ｄ，３Ｄを入力（ｉｎｐｕｔ）とすることと、ステップ２．２における加算処理が退化因子＋非退化因子の加算処理として実行される点である。このように、スカラー倍算アルゴリズムにおいて発生する加算処理は、すべて退化因子を含む加算処理として実現される。従って、高速化演算が可能であり、また非退化因子のみの加算処理が混在しないので、退化因子と非退化因子の演算処理時間や、演算処理に伴う消費電力の差異が発生せず、演算シーケンスの解析としてのＳＰＡ、ＴＡ解析に対する耐性も損なわれることのない安全で高速な演算が実現される。
【０２２８】
上述した種数（ｇ）３の曲線において、ベースポイントＤと３Ｄとの双方がウェイト（ｗｅｉｇｈｔ）＝２となる退化因子を検出し、検出した退化因子Ｄ，３Ｄを入力値として、スカラー倍算を実行する処理の全体シーケンスについて、図１２に示すフローチャートを参照して説明する。
【０２２９】
まず、図１２のステップＳ３５１において、ベースポイント［Ｄ］と、［３Ｄ］とが共に退化因子、すなわちウェイト＝２の退化因子となるような因子を検出する。この退化因子検出処理は、先に、図１０、図１１を参照して説明した処理によって求められる。すなわち、２Ｄ→３Ｄ：ＥｘＨａｒＡＤＤ３＋２→３  （Ｔａｂｌｅ  ７）のアルゴリズムのステップ３において、
ｔ１＝０
が、３Ｄ＝Ｄ＋２Ｄをｗｅｉｇｈｔ２とする条件であることから、導かれる式、
Ｎ３（ｘ２）＝０
を成立させる解（ｘ２）を求め、求めたｘ２から、超楕円曲線の式：ｙ２＋ｈ（ｘ）＝ｆ（ｘ）に代入してｙ２を求め、超楕円曲線上の点：Ｐ（ｘ１，ｙ１）、Ｑ（ｘ２，ｙ２）からベースポイントＤ、すなわち、
Ｄ＝（ｘ２＋ｕ２１ｘ＋ｕ２０，ｖ２１ｘ＋ｖ２０）
を求める処理として実行する。
【０２３０】
ステップＳ３５２では、ステップＳ３５１において算出したベースポイントＤに基づいて、もう１つの退化因子３Ｄを事前算出する。算出処理は、
Ｄ→２Ｄ：ＥｘＨａｒＤＢＬ１→２  （Ｔａｂｌｅ  ８）
２Ｄ→３Ｄ：ＥｘＨａｒＡＤＤ３＋２→３  （Ｔａｂｌｅ  ７）
上記算出処理工程によって実行できる。
【０２３１】
ステップＳ３５３では、スカラー倍算ｄ＝ｄＤにおける乗算データとしてのスカラー値ｄをｗＮＡＦ展開する。
【０２３２】
最後に、ステップＳ３５４において、スカラー倍算Ｄ＝ｄＤを実行する。このスカラー倍算では、退化因子Ｄ、３Ｄのみによって表現された事前算出データを適用したスカラー倍算演算処理として実行され、先に説明したアルゴリズム［アルゴリズム８］に従った処理として実行される。
【０２３３】
従来のｗＮＡＦ適用処理演算では、退化因子以外の因子、すなわちウェイト＝３の因子を適用した加算が実行されるが、本処理例のスカラー倍算における加算処理は、退化因子Ｄ，３Ｄのみを適用した加算処理、すなわち、すべて退化因子＋非退化因子の加算処理として実現される。従って、高速化演算が可能であり、また非退化因子による加算処理が混在しないので、退化因子と非退化因子の演算処理時間や、演算処理に伴う消費電力の差異が発生せず、演算シーケンスの解析としてのＳＰＡ、ＴＡ解析に対する耐性も損なわれることのない安全で高速な演算が実現される。
【０２３４】
以上、本発明の処理例としての退化因子をベースポイントとして設定し、かつウィンドウ（Ｗｉｎｄｏｗ）法を適用した処理例として、２つの処理例、
（処理例Ａ）種数（ｇ）２の曲線において、ベースポイントＤと５Ｄとの双方がウェイト（ｗｅｉｇｈｔ）＝１となる退化因子を効率よく検出し、検出した退化因子Ｄ，５Ｄのみを適用して、ｗＮＡＦ展開データを変換し、変換したｗＮＡＦ展開データを適用してスカラー倍算を実行する処理。
（処理例Ｂ）種数（ｇ）３の曲線において、ベースポイントＤと３Ｄとの双方がウェイト（ｗｅｉｇｈｔ）＝２となる退化因子を効率よく検出し、検出した退化因子Ｄ，３Ｄのみを適用して、ｗＮＡＦ展開データを適用してスカラー倍算を実行する処理。
の各処理について説明した
【０２３５】
上述したように、本発明の処理により、超楕円曲線暗号におけるスカラー倍算において退化因子を使ったＳＰＡ耐性のあるｗｉｎｄｏｗ法を用いることができるようになった。この処理により既存の方法に比べてスカラー倍算の高速処理が可能となる。以下に、従来の処理と、本発明による処理との計算量の比較データを示す。
【０２３６】
まず、種数２の場合の１６０ｂｉｔのｄのスカラー倍算を行う場合の計算量について、上述した
（本発明処理例Ａ）
種数（ｇ）２の曲線において、ベースポイントＤと５Ｄとの双方がウェイト（ｗｅｉｇｈｔ）＝１となる退化因子を効率よく検出し、検出した退化因子Ｄ，５Ｄのみを適用して、ｗＮＡＦ展開データを変換し、変換したｗＮＡＦ展開データを適用してスカラー倍算を実行する処理と、
従来法Ａ＝（１Ａ）退化因子をベースポイントに適用した処理例
従来法Ｂ＝（１Ｂ）ウィンドウ法（ｗＮＡＦ）を適用した処理例（ウィンドウサイズ＝２）
との計算コストの比較データを示す。
【０２３７】
従来法Ａ：３１８Ｉ＋６０２８Ｍ
従来法Ｂ：２３９Ｉ＋６２９３Ｍ
本発明処理例Ａ：２６７Ｉ＋５４７７Ｍ
上記中、Ｉは有限体の元の除算にかかるコストを表し、Ｍは有限体の元の乗算にかかるコストを示している。この数字が小さいほど計算量の少ない効率のよい方法であるといえる。これらの計算量の見積もりは、上述した説明で適用した計算アルゴリズム１〜９の因子の加算公式の計算量を基に算出した。各方式のスカラー倍算の公式は従来法Ａがアルゴリズム３（Ａｌｇｏｒｉｔｈｍ３）、従来法Ｂがアルゴリズム５（Ａｌｇｏｒｉｔｈｍ５）、本発明処理例Ａがアルゴリズム７（Ａｌｇｏｒｉｔｈｍ７）に対応している。
【０２３８】
例えば従来法Ａの計算コストは、
（Ｉ＋７Ｍ）＋（Ｉ＋２７Ｍ）＋１５８×｛（Ｉ＋２７Ｍ）＋（Ｉ＋１１Ｍ）｝
＝３１８Ｉ＋６０２８Ｍ
と計算することができる。
ＩとＭは実装した計算機によって異なってくるものであるが、ここではＩ＝４Ｍとしてすると、本発明処理例Ａ（計算コスト＝２６７Ｉ＋５４７７Ｍ）は、従来法Ａ（計算コスト＝３１８Ｉ＋６０２８Ｍ）に比較して、１０％程度の高速化が期待される。同様に従来法Ｂ（計算コスト＝２３９Ｉ＋６２９３Ｍ）と、本発明処理例Ａ（計算コスト＝２６７Ｉ＋５４７７Ｍ）とを比較した場合も、約１０％高速になる。なお、従来法Ｂと本発明処理例Ａの比較では、保持すべき事前算出データ数を同じ設定とした処理同士の比較を行った。すなわち、従来法Ｂは、ｗｉｎｄｏｗ  ｓｉｚｅ＝２のアルゴリズム（事前算出データ＝Ｄ，３Ｄ）、本発明処理例Ａは、ｗｉｎｄｏｗ  ｓｉｚｅ＝３のアルゴリズム（事前算出データ＝Ｄ，５Ｄ、ただし退化因子）とした比較データである。
【０２３９】
次に種数３の場合の１６０ｂｉｔのｄのスカラー倍算を行う場合の計算量について、上述した
（本発明処理例Ｂ）
種数（ｇ）３の曲線において、ベースポイントＤと３Ｄとの双方がウェイト（ｗｅｉｇｈｔ）＝２となる退化因子を効率よく検出し、検出した退化因子Ｄ，３Ｄのみを適用して、ｗＮＡＦ展開データを変換し、変換したｗＮＡＦ展開データを適用してスカラー倍算を実行する処理と、
従来法Ａ＝（１Ａ）退化因子（Ｗｅｉｇｈｔ２）をベースポイントに適用した処理例
従来法Ｂ＝（１Ｂ）ウィンドウ法（ｗＮＡＦ）を適用した処理例（ウィンドウサイズ＝２）
との計算コストの比較データを示す。
【０２４０】
従来法Ａ：３１８Ｉ＋２１１１１Ｍ
従来法Ｂ：２３９Ｉ＋１９１１９Ｍ
本発明処理例Ｂ：２３９Ｉ＋１７００３Ｍ
これらの計算量の見積もりは上述した説明で適用した計算アルゴリズム１〜９の因子の加算公式の計算量をもとに算出した。各方式のスカラー倍算の公式は従来法Ａがアルゴリズム３（Ａｌｇｏｒｉｔｈｍ３）、従来法Ｂがアルゴリズム５（Ａｌｇｏｒｉｔｈｍ５）、本発明処理例Ｂがアルゴリズム８（Ａｌｇｏｒｉｔｈｍ８）に対応している。
【０２４１】
種数２の場合と同様にＩ＝４Ｍと換算すると、本発明処理例Ｂ（計算コスト＝２３９Ｉ＋１７００３Ｍ）は、従来法Ａ（計算コスト＝３１８Ｉ＋２１１１１Ｍ）に比較して、２０％程度の高速化が期待される。同様に従来法Ｂ（計算コスト＝２３９Ｉ＋１９１１９Ｍ）と、本発明処理例Ａ（計算コスト＝２３９Ｉ＋１７００３Ｍ）とを比較した場合、約１１％高速になる。なお、この両者の比較では、両者ともｗｉｎｄｏｗ  ｓｉｚｅ＝２のアルゴリズム（事前算出データ＝Ｄ，３Ｄ）とした比較データである。
【０２４２】
以上、説明したように、本発明によれば、種数ｇの超楕円曲線において、ｇより小さいウェイト（ｗｅｉｇｈｔ）の因子をベースポイントとして使い、さらにウィンドウ法において適用する事前算出データを退化因子によって表現し、スカラー倍算における加算演算処理をすべて退化因子＋非退化因子の加算処理によって実行する構成としたので、加算処理の高速化が実現され、また、加算処理を退化因子＋非退化因子の演算のみとすることで、非退化因子の加算処理を混在させることがなくなり、演算処理における消費電力や処理時間のばらつきの検出による攻撃（ＳＰＡ，ＴＡ）に対する耐性も損なうことなく、安全性の高い高速処理可能な構成が実現される。
【０２４３】
超楕円曲線上の因子の演算を使う暗号処理演算において、処理の重い演算は因子のスカラー倍算である。上述した本発明の処理によりスカラー倍算を高速化することで超楕円曲線暗号の処理を大幅に改善することができる。
【０２４４】
前述したように、超楕円曲線暗号（ＨＥＣＣ）は楕円曲線暗号（ＥＣＣ）を一般化した概念であり、現在、様々な分野で適用されている楕円曲線暗号（ＥＣＣ）を使った暗号処理、具体的には署名処理、暗号データの生成、復号処理、暗号鍵共有処理、認証処理などに、本発明を適用することが可能である。楕円曲線暗号（ＥＣＣ）における演算処理中のスカラー倍算の部分を、上述したスカラー倍算に置き換えることで、演算の高速化が可能となる。
【０２４５】
［３．暗号処理装置の機能構成について］
図１３に、本発明の暗号処理装置の機能構成を示すブロック図を示す。暗号処理装置１００は、超楕円曲線暗号に基づく暗号処理演算を実行する暗号処理装置１００であり、超楕円曲線の種数ｇ（ｇｅｎｕｓ）より小さいウェイト（ｗｅｉｇｈｔ）ｇ０（ただし、１≦ｇ０＜ｇ）の因子、すなわち退化因子をベースポイントとして生成し、さらに、ウィンドウ法において適用する事前算出データを算出するために必要となるベースポイント以外の１つ以上の因子、例えば上述した処理例Ａでは５Ｄ、処理例Ｂでは３Ｄも退化因子となるような設定とした因子Ｄをベースポイントとして生成するベースポイント生成部１０１を有する。
【０２４６】
事前算出データ生成部１０２は、ベースポイント生成部１０１において生成したベースポイントＤに基づいて、事前算出退化因子データ、例えば３Ｄ、５Ｄ等の退化因子を算出する事前算出退化因子データ生成手段として機能する。
【０２４７】
暗号処理装置１００は、さらに、因子Ｄに対するスカラー倍算［Ｄ＝ｄＤ］において適用する乗数として設定されるスカラー値：ｄのｗＮＡＦ展開処理を実行する展開処理部１０３と、展開処理部１０３の展開データに対して、さらに変換テーブルに基づく変換処理を実行し、退化因子のみの表現としたｗＮＡＦ展開データを生成する展開処理データ変換部１０４と、ベースポイントとしての因子を含む因子のスカラー倍算処理を実行する演算処理部１０５とを有する。
【０２４８】
ベースポイント生成部１０１は、定義体としての有限体Ｆｑ上の元をランダムにｇ０個選び、ｇ０個の超楕円曲線上の点Ｐｉ（ｉ＝１、…、ｇ０）を生成し、
Ｕ（ｘ）＝（ｘ−ｘ１）（ｘ−ｘ２）…（ｘ−ｘｇ０）
Ｖ（ｘ）＝ｖｇ０−１ｘｇ０−１＋ｖｇ０−２ｘｇ０−２＋…＋ｖ０の係数ｖｉを決定し、ベースポイントの因子：Ｄ０＝（Ｕ（ｘ）、Ｖ（ｘ））を決定する処理を実行する構成である。
【０２４９】
ベースポイント生成部１０１は、例えば、超楕円曲線の種数ｇ（ｇｅｎｕｓ）＝２である場合には、ウェイト（ｗｅｉｇｈｔ）１となる退化因子をベースポイントとして生成する。超楕円曲線の種数ｇ（ｇｅｎｕｓ）＝３である場合には、ウェイト（ｗｅｉｇｈｔ）１または２となる退化因子をベースポイントとして生成する。ベースポイント生成部１０１は、ウィンドウ法において適用する事前算出データを算出するために必要となるベースポイント以外の１つ以上の因子、例えば上述した処理例Ａでは５Ｄ、処理例Ｂでは３Ｄも退化因子となる因子Ｄをベースポイントとして生成する処理を実行する。
【０２５０】
事前算出データ生成部１０２は、ベースポイント生成部１０１において生成したベースポイントＤに基づいて、事前算出データ３Ｄ、５Ｄ等の、ウィンドウ法において適用する事前算出データを算出する。上述の処理例Ａ（種数（ｇ）＝２）では、ウィンドウサイズ＝３として、５Ｄを事前に算出した。５Ｄは退化因子である。また、処理例Ｂ（種数（ｇ）＝３）では、ウィンドウサイズ＝２として、３Ｄを事前に算出した。３Ｄは退化因子である。
【０２５１】
展開処理部１０３は、因子Ｄに対するスカラー倍算［Ｄ＝ｄＤ］において適用する乗数として設定されるスカラー値：ｄのｗＮＡＦ展開処理を実行する。すなわち、乗数ｄの２進展開データについてデータ変換を実行して、所定桁数（ウィンドウサイズ）からなる数値ブロックの各々を、
｜００・・０ｘ｜００・・０ｘ｜００・・０ｘ｜・・
ただし、ｘは奇数（±１，±３・・）
となるように設定する。
【０２５２】
展開処理データ変換部１０４は、展開処理部１０３の展開データに対して、さらに変換テーブルに基づく変換処理を実行し、退化因子のみの表現としたｗＮＡＦ展開データを生成する。なお、この処理は、上述の処理例Ａにおいては適用されるが、処理例Ｂにおいては不要となる。処理例Ａでは、ウィンドウサイズ＝３であり、従来のｗＮＡＦ法では、±Ｄ、±３Ｄ、±５Ｄ、±７Ｄの各値を事前算出データとしてテーブルに保存することが必要となり、この場合、処理例Ａでは、Ｄ，５Ｄのみを退化因子として事前算出しているのみであるので、その他の必要となる事前算出データをＤ，５Ｄで表現した形式に変換することを必要とするためである。一方、上述した処理例Ｂでは、ウィンドウサイズ＝２であり、±Ｄ、±３Ｄを事前算出データとしてテーブルに保存することが必要となり、この場合、処理例Ｂでは、Ｄ，３Ｄを退化因子として事前算出しているので、その他の必要となる事前算出データがなく、ｗＮＡＦ展開データの変換が不要となる。
【０２５３】
演算処理部１０５は、スカラー倍算処理を実行する。この処理は、たとえば先に説明したアルゴリズム７（処理例Ａ）、またはアルゴリズム８（処理例Ｂ）に従った演算処理となる。従来のｗＮＡＦ適用処理演算では、退化因子以外の因子、すなわち種数（ｇ）に等しいウェイトの因子を適用した加算が実行されるが、本処理例のスカラー倍算における加算処理は、種数（ｇ）より小さいウェイトを持つ因子、すなわち退化因子＋非退化因子の加算処理が実行される。従って、高速化演算が可能であり、また非退化因子のみの加算処理が混在しないので、退化因子と非退化因子の演算処理時間や、演算処理に伴う消費電力の差異が発生せず、演算シーケンスの解析としてのＳＰＡ、ＴＡ解析に対する耐性も損なわれることのない安全で高速な演算が実現される。
【０２５４】
［４．電子署名生成および検証アルゴリズムにおける本発明の適用例］
以下に本発明の処理を適用可能な具体的な暗号処理アルゴリズムの例として、楕円曲線暗号を適用した電子署名生成および検証アルゴリズムであるＥＣＤＳＡ（ＥＣ−Ｄｉｇｉｔａｌ Ｓｉｇｎａｔｕｒｅ Ａｌｇｏｒｉｔｈｍ）のスカラー倍算に本発明の演算手法を適用した場合について説明する。ＩＥＥＥ１３６３によるとＥＣＤＳＡによる署名生成、検証は以下のシーケンスによって実行される。
【０２５５】
（１）入力
（１−１）楕円曲線のドメインパラメータ及びベースポイントＧ（位数ｒ）
（１−２）署名者の秘密鍵ｓ
（１−３）平文Ｍ
（２）鍵生成
（２−１）秘密鍵ｓに対してＷ＝ｓＧを公開鍵とする
（３）署名生成
（３−１）ランダムな整数０＜ｕ＜ｒを生成
（３−２）Ｖ＝ｕＧ＝（ｘｖ、ｙｖ）を計算
（３−３）ｘｖを整数に変換し、ｉとする
（３−４）ｃ＝ｉ  ｍｏｄ  ｒを計算。ｃ＝０ならｓｔｅｐ３−１へ
（３−５）ｆ＝ｈ（Ｍ）、ｈはｈａｓｈ関数
（３−６）ｄ＝ｕ−１（ｆ＋ｓｃ）ｍｏｄ  ｒを計算。ｄ＝０ならｓｔｅｐ３−１へ
（３−７）（ｃ、ｄ）を平文Ｍに対する署名にする。
（４）署名検証
（４−１）０＜ｃ＜ｒ、０＜ｄ＜ｒをチェック。該当しない場合ｉｎｖａｌｉｄを出力
（４−２）ｈ＝ｄ−１ｍｏｄ  ｒ、ｈ１＝ｆｈ  ｍｏｄ  ｒ、ｈ２＝ｃｈ  ｍｏｄ  ｒを計算。
（４−３）Ｐ＝（ｘｐ、ｙｐ）＝ｈ１Ｇ＋ｈ２Ｗを計算。Ｐ＝Ｏならばｉｎｖａｌｉｄを出力
（４−４）ｘｐを整数に変換し、ｉとする。
（４−５）ｃ'＝ｉ  ｍｏｄ  ｒを計算する。
（４−６）ｃ'＝ｃならばｖａｌｉｄを出力。そうでないならばｉｎｖａｌｉｄを出力。
【０２５６】
上記アルゴリズムにおいて下記の処理が超楕円曲線を用いた本提案法が適用できる箇所である。
（２−１）秘密鍵ｓに対してＷ＝ｓＧを公開鍵とする
（３−２）Ｖ＝ｕＧ＝（ｘｖ、ｙｖ）を計算
（４−３）Ｐ＝（ｘｐ、ｙｐ）＝ｈ１Ｇ＋ｈ２Ｗを計算。Ｐ＝Ｏならばｉｎｖａｌｉｄを出力
【０２５７】
これらの各ステップ（２−１），（３−２），（４−３）における演算処理、Ｗ＝ｓＧ、Ｖ＝ｕＧ、Ｐ＝（ｘｐ、ｙｐ）＝ｈ１Ｇ＋ｈ２Ｗにおけるｈ１Ｇの演算処理は、因子のスカラー倍算処理であり、本発明の適用による高速化が可能となる。
【０２５８】
［５．暗号処理装置のハードウェア構成例］
最後に、上述の暗号処理を実行するデバイスとしてのＩＣモジュール２００の構成例を図１４に示す。上述の処理は、例えばＰＣ、ＩＣカード、リーダライタ、その他、様々な情報処理装置において実行可能であり、図１４に示すＩＣモジュール２００は、これら様々な機器に構成することが可能である。
【０２５９】
図１４に示すＣＰＵ(Central processing Unit)２０１は、暗号処理の開始や、終了、データの送受信の制御、各構成部間のデータ転送制御、その他の各種プログラムを実行するプロセッサである。メモリ２０２は、ＣＰＵ２０１が実行するプログラム、あるいは演算パラメータとしての固定データを格納するＲＯＭ（Read-Only-Memory）、ＣＰＵ２０１の処理において実行されるプログラム、およびプログラム処理において適宜変化するパラメータの格納エリア、ワーク領域として使用されるＲＡＭ（Random Access Memory）等からなる。
【０２６０】
なお、メモリ２０２に格納する演算実行プログラムは、上述したベースポイントの設定処理、スカラー倍算としての加算、２倍算の実行シーケンスを含むプログラムとして設定される。また、メモリ２０２は暗号処理に必要な鍵データ等の格納領域として使用可能である。データ等の格納領域は、耐タンパ構造を持つメモリとして構成されることが好ましい。
【０２６１】
暗号処理手部２０３は、上述したスカラー倍算処理を含む暗号処理、復号処理等を実行する。なお、ここでは、暗号処理手段を個別モジュールとした例を示したが、このような独立した暗号処理モジュールを設けず、例えば暗号処理プログラムをＲＯＭに格納し、ＣＰＵ２０１がＲＯＭ格納プログラムを読み出して実行するように構成してもよい。
【０２６２】
乱数発生器２０４は、暗号処理に必要となる鍵の生成などにおいて必要となる乱数の発生処理を実行する。
【０２６３】
送受信部２０５は、外部とのデータ通信を実行するデータ通信処理部であり、例えばリーダライタ等、ＩＣモジュールとのデータ通信を実行し、ＩＣモジュール内で生成した暗号文の出力、あるいは外部のリーダライタ等の機器からのデータ入力などを実行する。
【０２６４】
以上、特定の実施例を参照しながら、本発明について詳解してきた。しかしながら、本発明の要旨を逸脱しない範囲で当業者が該実施例の修正や代用を成し得ることは自明である。すなわち、例示という形態で本発明を開示してきたのであり、限定的に解釈されるべきではない。本発明の要旨を判断するためには、特許請求の範囲の欄を参酌すべきである。
【０２６５】
なお、明細書中において説明した一連の処理はハードウェア、またはソフトウェア、あるいは両者の複合構成によって実行することが可能である。ソフトウェアによる処理を実行する場合は、処理シーケンスを記録したプログラムを、専用のハードウェアに組み込まれたコンピュータ内のメモリにインストールして実行させるか、あるいは、各種処理が実行可能な汎用コンピュータにプログラムをインストールして実行させることが可能である。
【０２６６】
例えば、プログラムは記録媒体としてのハードディスクやＲＯＭ（Read Only Memory)に予め記録しておくことができる。あるいは、プログラムはフレキシブルディスク、ＣＤ−ＲＯＭ(Compact Disc Read Only Memory)，ＭＯ(Magneto optical)ディスク，ＤＶＤ(Digital Versatile Disc)、磁気ディスク、半導体メモリなどのリムーバブル記録媒体に、一時的あるいは永続的に格納（記録）しておくことができる。このようなリムーバブル記録媒体は、いわゆるパッケージソフトウエアとして提供することができる。
【０２６７】
なお、プログラムは、上述したようなリムーバブル記録媒体からコンピュータにインストールする他、ダウンロードサイトから、コンピュータに無線転送したり、ＬＡＮ(Local Area Network)、インターネットといったネットワークを介して、コンピュータに有線で転送し、コンピュータでは、そのようにして転送されてくるプログラムを受信し、内蔵するハードディスク等の記録媒体にインストールすることができる。
【０２６８】
なお、明細書に記載された各種の処理は、記載に従って時系列に実行されるのみならず、処理を実行する装置の処理能力あるいは必要に応じて並列的にあるいは個別に実行されてもよい。また、本明細書においてシステムとは、複数の装置の論理的集合構成であり、各構成の装置が同一筐体内にあるものには限らない。
【産業上の利用可能性】
【０２６９】
本発明の構成によれば、超楕円曲線暗号に基づくスカラー倍算処理におけるベースポイントＤと、スカラー倍算の実行アルゴリズムとしてのウィンドウ法における事前算出データ中、ベースポイントを除く１つ以上の事前算出データとを、超楕円曲線の種数ｇ（ｇｅｎｕｓ）より小さいウェイト（ｗｅｉｇｈｔ）ｇ０（ただし、１≦ｇ０＜ｇ）の因子である退化因子となる設定とし、ウィンドウ法を適用したスカラー倍算処理における加算処理を事前算出した退化因子＋非退化因子の加算処理によって実行する構成としたので、高速演算が実現されるとともに、また非退化因子のみの加算処理が混在しないので、退化因子と非退化因子の演算処理時間や、演算処理に伴う消費電力の差異が発生せず、演算シーケンスの解析としてのＳＰＡ、ＴＡ解析に対する耐性も損なわれることのない安全で高速な演算が実現され、ＩＣカードなど高速性、安全性の要求される暗号処理演算を行う機器、デバイスなどにおいて本発明の適用が可能である。
【０２７０】
さらに、本発明の構成によれば、因子Ｄに対するスカラー倍算Ｄ＝ｄＤの乗数ｄについての展開処理として、ウィンドウ法に基づく展開処理であるｗＮＡＦ（ｗｉｄｔｈ−ｗＮｏｎ−Ａｄｊａｃｅｎｔ  Ｆｏｒｍ）展開を実行し、展開処理において生成されたｗＮＡＦ展開処理データに基づいて決定される事前算出データに、退化因子データ以外のデータを含む場合、ｗＮＡＦ展開データを変換し、退化因子データのみによって構成される変換ｗＮＡＦ展開データを生成して、変換ｗＮＡＦ展開データに退化因子データを対応付け、スカラー倍算における加算処理を退化因子＋非退化因子の加算処理として実行する構成としたので、演算シーケンスの解析としてのＳＰＡ、ＴＡ解析に対する耐性の損なわれない安全で高速な演算が実現され、ＩＣカードなど高速性、安全性の要求される暗号処理演算を行う機器、デバイスなどにおいて本発明の適用が可能である。
【図面の簡単な説明】
【０２７１】
【図１】種数２の超楕円曲線暗号のスカラー倍算における加算処理、２倍算処理のアルゴリズムについて説明する図である。
【図２】種数３の超楕円曲線暗号のスカラー倍算における加算処理、２倍算処理のアルゴリズムについて説明する図である。
【図３】退化因子の生成およびスカラー倍算処理を実行する場合の全体シーケンスについて説明するフローチャートを示す図である。
【図４】超楕円曲線暗号演算処理における退化因子としてのベースポイント設定処理の手順を説明するフローチャートである。
【図５】ウィンドウ法を適用して、スカラー倍算処理を実行する場合の全体シーケンスについて説明する図である。
【図６】種数（ｇ）２の超楕円曲線においてＤ，５Ｄが退化因子、すなわちウェイト＝１となるベースポイントＤを検出する処理の詳細について説明する図である。
【図７】種数（ｇ）２の超楕円曲線においてＤ，５Ｄが退化因子、すなわちウェイト＝１となるベースポイントＤを検出する処理手順を説明するフローチャートを示す図である。
【図８】退化因子Ｄ，５Ｄを適用して単純電力解析（ＳＰＡ）に対する耐性を有するウィンドウ法（ｗｉｄｏｗ法）によるスカラー倍算を実現するための改良されたｗＮＡＦ展開、ｗＮＡＦ（１、５）の処理を説明する図である。
【図９】種数（ｇ）２の曲線において、ベースポイントＤと５Ｄとの双方がウェイト（ｗｅｉｇｈｔ）＝１となる退化因子を検出し、検出した退化因子Ｄ，５Ｄのみを適用して、ｗＮＡＦ展開データを変換し、変換したｗＮＡＦ展開データを適用してスカラー倍算を実行する処理の全体シーケンスについて説明する図である。
【図１０】種数（ｇ）３の超楕円曲線においてＤ，３Ｄが退化因子、すなわちウェイト＝２となるベースポイントＤを検出する処理の詳細について説明する図である。
【図１１】種数（ｇ）３の超楕円曲線においてＤ，３Ｄが退化因子、すなわちウェイト＝２となるベースポイントＤを検出する処理手順を説明するフローチャートを示す図である。
【図１２】種数（ｇ）３の曲線において、ベースポイントＤと３Ｄとの双方がウェイト（ｗｅｉｇｈｔ）＝２となる退化因子を検出し、検出した退化因子Ｄ，３Ｄのみを適用して、ｗＮＡＦ展開データを生成し、スカラー倍算を実行する処理の全体シーケンスについて説明する図である。
【図１３】本発明の暗号処理装置の機能構成を示すブロック図である。
【図１４】本発明の暗号処理演算を実行する暗号処理実行デバイス例としてのＩＣモジュールの構成例を示す図である。
【符号の説明】
【０２７２】
１００  暗号処理装置
１０１  ベースポイント生成部
１０２  事前算出データ生成部
１０３  展開処理部
１０４  展開処理データ変換部
１０５  演算処理部
２００  ＩＣモジュール
２０１  ＣＰＵ(Central Processing Unit)
２０２  メモリ
２０３  暗号処理部
２０４  乱数発生器
２０５  送受信部
【図１】
2006145945.tif 000031
【図２】
2006145945.tif 000032
【図３】
2006145945.tif 000033
【図４】
2006145945.tif 000034
【図５】
2006145945.tif 000035
【図６】
2006145945.tif 000036
【図７】
2006145945.tif 000037
【図８】
2006145945.tif 000038
【図９】
2006145945.tif 000039
【図１０】
2006145945.tif 000040
【図１１】
2006145945.tif 000041
【図１２】
2006145945.tif 000042
【図１３】
2006145945.tif 000043
【図１４】
2006145945.tif 000044