(57)【要約】【課題】超楕円暗号処理において高速演算を実現する装置および方法を実現する。【解決手段】超楕円曲線暗号のスカラー倍算において、超楕円曲線の曲線パラメータに基づいて、２倍算適用演算アルゴリズムと、１／２倍算適用演算アルゴリズムのいずれの演算アルゴリズムが高速演算可能かの判定を行ない、高速演算可能と判定されたアルゴリズムを選択適用してスカラー倍算処理を実行する。本構成により、様々な曲線に対応する暗号処理に伴うスカラー倍算を、確実に高速な処理で行なうことが可能となる。すなわち、曲線パラメータに応じたアルゴリズム選択により、スカラー倍算における計算量を削減した高速演算が実現される。【選択図】図１４
2008020757.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）方式がある。超楕円曲線暗号方式については、例えば非特許文献１、非特許文献２に記載されている。
【００１０】
楕円曲線暗号では、有限体Ｆｑ、ただしｑ＝ｐｎ、ｐを素数、ｎを正整数、この有限体Ｆｑ上で定義される楕円曲線上の点をＰとし、スカラー倍算した点ｋＰ（ｋ∈Ｚ）をＱとすると、Ｑからｋを求める問題は離散対数問題に帰着できる。一方、超楕円曲線暗号では点の形式的和である因子（ｄｉｖｉｓｏｒ）をＤ１とし、スカラー倍算ｋＤ１で定義される因子をＤ２とすると、Ｄ２からｋを求める問題は超楕円曲線におけるヤコビ多様体上の離散対数問題と呼ばれる。この数学適な困難精に基づいて公開鍵暗号を構成することができる。
【００１１】
超楕円曲線では曲線を特徴づける値は種数（ｇｅｎｕｓ）ｇである。ｐを素数、ｎを正の整数、ｑ＝ｐｎとする。このとき有限体Ｆｑ上で定義される種数ｇの超楕円曲線Ｃは以下の方程式、
ｙ２＋ｈ（ｘ）ｙ＝ｆ（ｘ）
で定義される。ここで、ｈ（ｘ），ｆ（ｘ）∈Ｆｑ［ｘ］，ｆ（ｘ）は、次数２ｇ＋１のｍｏｎｉｃ多項式である。
【００１２】
超楕円曲線Ｃ上の点Ｐ＝（ｘ、ｙ）に対して共役点（ｏｐｐｏｓｉｔｅ  ｐｏｉｎｔ）は、−Ｐ＝（ｘ、−ｙ−ｈ（ｘ））として定義される。また、Ｐ＝−Ｐである点を分岐点（ｒａｍｉｆｉｃａｔｉｏｎ  ｐｏｉｎｔ）と呼ぶ。また、無限遠点をＰ∞と表す。
【００１３】
超楕円曲線暗号の定義体の演算サイズ（ビット長）は楕円曲線暗号と同等の安全性を仮定した場合、楕円曲線の定義体の演算サイズに比べて１／ｇに小さくなることが知られている。演算サイズが小さいことは実装上メリットがあり、超楕円曲線暗号の利点の一つして挙げられる。
【００１４】
次に、超楕円曲線暗号の基本事項について説明する。前述したように、超楕円曲線暗号では点の形式的和である因子（ｄｉｖｉｓｏｒ）をＤ１とし、スカラー倍算ｋＤ１で定義される因子をＤ２とすると、Ｄ２からｋを求める問題は超楕円曲線におけるヤコビ多様体上の離散対数問題として公開鍵暗号として用いることができる。
【００１５】
ここで、因子（ｄｉｖｉｓｏｒ）は有理点の形式和であり、以下の形式で表現することができる。
【数１】
2008020757.tif 000003
【００１６】
また、半被約因子（ｓｅｍｉ  ｒｅｄｕｃｅｄ  ｄｉｖｉｓｏｒ）は、以下の形式で表現することができる。
【数２】
2008020757.tif 000004
【００１７】
ただし、Ｐｉ＝（ｘｉ、ｙｉ）かつｉ≠ｊに対してＰｉ≠Ｐｊである。
【００１８】
また、ΣｍｉをＤのウェイト（ｗｅｉｇｈｔ）と呼ぶ。さらにウェイト（ｗｅｉｇｈｔ）が種数ｇ以下である半被約因子を被約因子（ｒｅｄｕｃｅｄ  ｄｉｖｉｓｏｒ）と呼ぶ。
【００１９】
超楕円曲線の安全性は被約因子の個数に依存しているここで被約因子の個数をＮとする。安全な超楕円曲線暗号を実現するためには、Ｎが１６０ビット以上の素数ｒを因数に持つことが必要である。このとき、ＮはＮ＝ｃ×ｒと表現される。ｃはコファクターと呼ばれ，小さい数であることが望ましい。例えば、
ｑ＝ｐ（ｐは奇素数）の場合は、ｃ＝１、
ｑ＝２ｎの場合は、ｃ＝２、
を満たす超楕円曲線を用いる。また、ベースポイントは位数がｒであるものを選ぶ。
【００２０】
超楕円曲線の任意の半被約因子Ｄは下記の多項式Ｕ、Ｖ∈Ｆｑ［ｘ］を用いてＤ＝（Ｕ、Ｖ）として表現できる。これをマンホード（Ｍｕｍｆｏｒｄ）表現と呼ぶ。なお、マンホード（Ｍｕｍｆｏｒｄ）表現については、例えば非特許文献３に記載されている。
【数３】
2008020757.tif 000005
【００２１】
種数（ｇｅｎｕｓ）２の任意の被約因子Ｄはマンホード（Ｍｕｍｆｏｒｄ）表現を用いると、有限体Ｆｑ上の元を係数に持つ２次以下の多項式の組、すなわち、
（Ｕ、Ｖ）＝（ｘ２＋ｕ１ｘ＋ｕ０、ｖ１ｘ＋ｖ０）、または、
（Ｕ、Ｖ）＝（ｘ＋ｘ０、ｙ０）
として表現することができる。
また、零元は、
（Ｕ，Ｖ）＝（１，０）＝Ｏ
として表現される。
【００２２】
次に、超楕円曲線暗号で用いられる因子のスカラー倍算について説明する。因子のスカラー倍算は加算アルゴリズムと呼ばれる因子の加算と２倍算の組み合わせ、もしくは加算と１／２倍算の組み合わせで計算することができる。以下では主要な加算アルゴリズムについて説明する。
【００２３】
最初に提案された実用的なアルゴリズムはＣａｎｔｏｒのアルゴリズムである。このアルゴリズムについては、例えば非特許文献１、非特許文献２に記載されている。このアルゴリズムはあらゆる種数の超楕円曲線上の因子に対して適用可能なアルゴリズムであるが、楕円曲線に比べてアルゴリズムが複雑で計算量が多いことが欠点である。
【００２４】
Ｈａｒｌｅｙは種数２の超楕円曲線に限定し、因子のｗｅｉｇｈｔの場合分けをおこない、それぞれの場合で最適化を行うことでより計算量の少ないアルゴリズムを提案した。この研究を受けて超楕円曲線暗号（ＨＥＣＣ）における演算アルゴリズムの改良、拡張の研究が近年盛んになっている。
【００２５】
（ア）Ｈａｒｌｅｙのアルゴリズムは定義体を素体、種数２の曲線、因子の表現はＭｕｍｆｏｒｄ表現を用いている。このアルゴリズムの計算量の改善の研究例として、例えば、非特許文献４、非特許文献５、非特許文献６などが挙げられる。
（イ）さらに、定義体を２の拡大体の場合について拡張した処理例について、非特許文献７、非特許文献８に報告されている。
（ウ）また、因子の表現に拡張Ｍｕｍｆｏｒｄ表現、Ｗｅｉｇｈｔｅｄ  Ｃｏｏｒｄｉｎａｔｅを用いることで計算量を削減した研究として非特許文献１１、非特許文献１２、非特許文献６、非特許文献１３がある。
【００２６】
Ｈａｒｌｅｙアルゴリズムの処理について、図１を参照して説明する。なお、本発明は、標数２の有限体上定義された種数２の超楕円曲線に関するものであり、以下の説明では、曲線の種数を２、定義体の標数を２とする。
【００２７】
図１（Ａ）は、種数２の場合の因子の加算Ｄ１＋Ｄ２の処理例を示した図である。なお、因子Ｄ１、Ｄ２は、それぞれＤ１＝（Ｕ１、Ｖ１）、Ｄ２＝（Ｕ２、Ｖ２）とする。まず、因子のウェイト（ｗｅｉｇｈｔ）の値によって場合分けが行われる。すなわち、［Ｄ１＋Ｄ２］の各ウェイト（ｗｅｉｇｈｔ）の値によって、
（１）ｗｅｉｇｈｔ２＋ｗｅｉｇｈｔ２
（２）ｗｅｉｇｈｔ２＋ｗｅｉｇｈｔ１
（３）例外処理１
の場合分けが行なわれる。
【００２８】
次にｗｅｉｇｈｔ２同士の加算、すなわち（１）ｗｅｉｇｈｔ２＋ｗｅｉｇｈｔ２の場合、因子Ｄ１＝（Ｕ１、Ｖ１）、Ｄ２＝（Ｕ２、Ｖ２）について、最大公約数ｇｃｄ（Ｕ１、Ｕ２）＝１であれば、２つの因子Ｄ１＝（Ｕ１、Ｖ１）、Ｄ２＝（Ｕ２、Ｖ２）は、互いに同一または共役点（ｏｐｐｏｓｉｔｅ  ｐｏｉｎｔ）を含まない。この場合、
（１ａ）ＨａｒｌｅｙＡＤＤ、
すなわちハーレーアルゴリズムに従った加算処理を行う。（１ａ）ＨａｒｌｅｙＡＤＤの処理は例えば非特許文献７に示されているＭｏｓｔ  Ｆｒｅｑｕｅｎｔ  Ｃａｓｅと呼ばれる処理である。このＭｏｓｔ  Ｆｒｅｑｕｅｎｔ  Ｃａｓｅは、種数２の場合の因子の加算Ｄ１＋Ｄ２処理において、高確率で発生するケースである。
【００２９】
この（１ａ）ＨａｒｌｅｙＡＤＤの処理は、非常に高い確率でおこる。その他の例外処理の起こる確率は非常に低い。Ｍｏｓｔ  Ｆｒｅｑｕｅｎｔ  Ｃａｓｅの条件を満たさない場合、すなわち、因子Ｄ１＝（Ｕ１、Ｖ１）、Ｄ２＝（Ｕ２、Ｖ２）について、最大公約数ｇｃｄ（Ｕ１、Ｕ２）＝１を満足しない場合は、
（１ｂ）例外処理２を行う。
【００３０】
（２）ｗｅｉｇｈｔ２＋ｗｅｉｇｈｔ１の場合についても同様に、ｇｃｄ（Ｕ１、Ｕ２）＝１かどうかをチェックし、ｇｃｄ（Ｕ１、Ｕ２）＝１を満足する場合には、
（２ａ）ＥｘＨａｒＡＤＤ２＋１→２を実行し、
ｇｃｄ（Ｕ１、Ｕ２）＝１を満足しない場合には、
（２ｂ）例外処理３を行う。
（３）例外処理１は、ｗｅｉｇｈｔの場合分けが上記（１），（２）以外の場合である。
【００３１】
なお、上述した種数２の加算処理のアルゴリズムの詳細については、非特許文献８に記載（Ｔａｂｌｅ１，２）されている。
【００３２】
次に、種数２の場合の２倍算の流れを図１（Ｂ）を参照して説明する。２倍算は、Ｄ＋Ｄ＝２Ｄの処理である。入力をＤ１＝（Ｕ１，Ｖ１）とし、出力をＤ２＝［２］Ｄ１とする。
加算の場合と同様に因子Ｄ１のｗｅｉｇｈｔが
（４）ｗｅｉｇｈｔ２、
（５）ｗｅｉｇｈｔ１、
（６）ｗｅｉｇｈｔ０、
によってそれぞれ異なる処理を行う。
【００３３】
（４）ｗｅｉｇｈｔ２の場合、因子が分岐点を含むかどうかをチェックし、含まなければ、（４ａ）ＨａｒｌｅｙＤＢＬの処理を行う。因子が分岐点を含む場合は（４ｂ）例外処理６を行う。ｇｃｄ（ｈ，Ｕ１）＝１であれば、Ｄ１は分岐点を含まない。この場合、（４ａ）ＨａｒｌｅｙＤＢＬの処理を行う。ＨａｒｌｅｙＤＢＬの処理アルゴリズムは例えば非特許文献５にＭｏｓｔ  Ｆｒｅｑｕｅｎｔ  Ｃａｓｅとして示されている。
【００３４】
後述するように、この処理が非常に高い確率でおこる。その他の例外処理の起こる確率は非常に低い。上述したように、Ｍｏｓｔ  Ｆｒｅｑｕｅｎｔ  Ｃａｓｅの条件を満たさない場合は例外処理６を行う。
【００３５】
ｗｅｉｇｈｔ１の場合も同様にｇｃｄ（ｈ，Ｕ１）＝１かどうかをチェックし，（５ａ）の処理、ＥｘＨａｒＤＢＬ１＋１→２もしくは、（５ｂ）の処理である例外処理７を行う。ＥｘＨａｒＤＢＬ１＋１→２のアルゴリズムについては、非特許文献８［４．１２．（ａ）］に示されている。
【００３６】
ＨａｒｌｅｙＡＤＤ，ＨａｒｌｅｙＤＢＬは、上述のようにＭｏｓｔ  Ｆｒｅｑｕｅｎｔ  Ｃａｓｅと呼ばれ、ランダムに因子を発生させて加算または２倍算を行うと、非常に高い確率でＨａｒｌｅｙＡＤＤ、ＨａｒｌｅｙＤＢＬの処理になる。なお、このＨａｒｌｅｙＡＤＤ、ＨａｒｌｅｙＤＢＬが、Ｍｏｓｔ  Ｆｒｅｑｕｅｎｔ  Ｃａｓｅとなることの説明は、例えば非特許文献１４に説明されている。
【００３７】
非特許文献１４によると、このＭｏｓｔ  Ｆｒｅｑｕｅｎｔ  Ｃａｅｓ以外の処理になる確率はＯ（１／ｑ）である。ここでｑは定義体の要素数であり、安全な暗号用途ではqgが１６０ｂｉｔ程度必要になる大きな数であるので現実的にはＨａｒｌｅｙＡＤＤ、ＨａｒｌｅｙＤＢＬしか発生しない状況とみなすことができる。
【００３８】
従って超楕円曲線暗号（ＨＥＣＣ）の加算アルゴリズムをＨａｒｌｅｙアルゴリズムまたはその改良アルゴリズムを使って、例えばＩＣカードなどの暗号処理演算手段として実装する場合、
ＨａｒｌｅｙＡＤＤ、
ＨａｒｌｅｙＤＢＬ
これらの演算アルゴリズム実行手段のみを実装し、その他の確率的にほとんど起こらない複雑な例外処理についての演算を実行しない実装とする場合も多い。この場合、例外処理については、ｗｅｉｇｈｔの場合分けが必要のないＣａｎｔｏｒのアルゴリズムを実行する構成とするなどの方法が適用される。種数が高くなるほど複雑な例外処理の負担は増すため、非特許文献９，１０ではこの実装方法について説明している。
【００３９】
次に超楕円曲線暗号（ＨＥＣＣ）アルゴリズムにおける因子のスカラー倍算について説明する。因子のスカラー倍算の実行方法としては、
（ａ）超楕円加算と超楕円２倍算の組み合わせ、
（ｂ）超楕円加算と超楕円１／２倍算の組み合わせ、
上記（ａ）または（ｂ）のいずれにおいても計算することができる。
以下、（ａ），（ｂ）の計算方法について説明する。
【００４０】
（ａ）超楕円加算と超楕円２倍算の組み合わせに基づく因子のスカラー倍算
まず、超楕円加算と超楕円２倍算の組み合わせに基づく因子のスカラー倍算について説明する。スカラー倍算のアルゴリズムとして基本的なＤｏｕｂｌｅ−ａｎｄ−ａｄｄ  ｂｉｎａｒｙ法の中で、ｒｉｇｈｔ−ｔｏ−ｌｅｆｔとｌｅｆｔ−ｔｏ−ｒｉｇｈｔの２種類を説明する。
【００４１】
前述したように、楕円曲線暗号では有限体Ｆｑ上で定義される楕円曲線上の点をＰとし、スカラー倍算した点ｋＰ（ｋ∈Ｚ）をＱとすると、Ｑからｋを求める問題は離散対数問題に帰着できる。一方、超楕円曲線暗号では点の形式的和である因子（ｄｉｖｉｓｏｒ）をＤ１とし、スカラー倍算ｋＤ１で定義される因子をＤ２とすると、Ｄ２からｋを求める問題は超楕円曲線におけるヤコビ多様体上の離散対数問題として公開鍵暗号として用いることができる。
【００４２】
因子Ｄに対して、スカラー倍算（ｄＤ）に適用する乗数としてのスカラー値:ｄの２進数表現を、
ｄ＝（ｄｌ−１、・・・・・、ｄ０）、
ただし、ｄｌ−１＝１、ｄｌ−２，・・・，ｄ０＝１ｏｒ０とする。
【００４３】
スカラー倍算のアルゴリズムとして基本的なｂｉｎａｒｙ法の演算アルゴリズムには、
ｂｉｎａｒｙ（ｒｉｇｈｔ−ｔｏ−ｌｅｆｔ）法
ｂｉｎａｒｙ（ｌｅｆｔ−ｔｏ−ｒｉｇｈｔ）法
がある。
【００４４】
ｂｉｎａｒｙ（ｒｉｇｈｔ−ｔｏ−ｌｅｆｔ）法は、ｄを下位ビットから見ていき、ｄｉ＝１の場合に、［２ｉ］Ｄを加算することが特徴である。ｂｉｎａｒｙ（ｒｉｇｈｔ−ｔｏ−ｌｅｆｔ）法のアルゴリズム１（Ａｌｇｏｒｉｔｈｍ１）を以下に示す。
【数４】
2008020757.tif 000006
【００４５】
一方、ｂｉｎａｒｙ（ｌｅｆｔ−ｔｏ−ｒｉｇｈｔ）法は、ｄを上位ビットから見ていき、毎ビットＤを２倍し、ｄｉ＝１の場合に、ベースポイントを加算することが特徴である。ｂｉｎａｒｙ（ｌｅｆｔ−ｔｏ−ｒｉｇｈｔ）法のアルゴリズム２（Ａｌｇｏｒｉｔｈｍ２）を以下に示す。
【数５】
2008020757.tif 000007
【００４６】
（ｂ）超楕円加算と超楕円１／２倍算の組み合わせに基づく因子のスカラー倍算
次に、超楕円加算と超楕円１／２倍算の組み合わせに基づく因子のスカラー倍算について説明する。
【００４７】
（ｂ１）種数２，標数２の１／２倍算
まず、種数２，標数２の１／２倍算について説明する。１／２倍算は、前述の２倍算の逆演算である。１／２倍算においては、因子のｗｅｉｇｈｔの場合分けを行い、それぞれの場合毎に対応した２倍算の逆演算を計算する。この１／２倍算は、曲線パラメータや使用する有限体によっては、２倍算よりも高速に処理できることが知られている。これらについては非特許文献１５、非特許文献１６に記載されている。
【００４８】
１／２倍算の流れを図２を参照して説明する。入力をＤ２＝（Ｕ２，Ｖ２）とし、出力をＤ１＝［１／２］Ｄ２とする。なお、因子は位数がｒのものとする。つまり、扱う因子は分岐点を持たない。入力因子Ｄ２＝（Ｕ２，Ｖ２）は以下のように示すことができる。
Ｄ２＝（Ｕ２，Ｖ２）、
Ｕ２＝ｕ２２ｘ２＋ｕ２１ｘ＋ｕ２０、
Ｖ２＝ｖ２１ｘ＋ｖ２０、
ｕ２２＝０ｏｒ１
とする。分岐点を持たないため、１／２倍算として、
ＥｘＨａｒＤＢＬ１＋１→２、ＥｘＨａｒＤＢＬ２＋２→１、ＥｘＨａｒＤＢＬ２＋２→２、および、ＨａｒｌｅｙＤＢＬの４つの逆演算を考えればよい。ＨａｒｌｅｙＤＢＬ以外は例外ケースである。
【００４９】
ここでＥｘＨａｒＤＢＬ２＋２→１は入力因子のｗｅｉｇｈｔが２で、出力因子のｗｅｉｇｈｔが１の場合を計算する方法である。また、ＥｘＨａｒＤＢＬ２＋２→２  は入力因子のｗｅｉｇｈｔが２で、かつＵ２の１次の項の係数がｕ２１＝０を満たし、出力因子のｗｅｉｇｈｔが２の場合を計算する方法である。ただし、ＥｘＨａｒＤＢＬ２＋２→２はＨａｒｌｅｙＤＢＬで計算できるが、これの逆演算である１／２倍算は、例外ケースとなるため、ここでは、ＥｘＨａｒＤＢＬ２＋２→２を例外ケースとして扱う。
【００５０】
これら、ＥｘＨａｒＤＢＬ１＋１→２、ＥｘＨａｒＤＢＬ２＋２→１、ＥｘＨａｒＤＢＬ２＋２→２、および、ＨａｒｌｅｙＤＢＬに対応する１／２倍算をそれぞれ、ＥｘＨＥＣ＿ＨＬＶ２→１＋１、ＥｘＨＥＣ＿ＨＬＶ１→２＋２、ＥｘＨＥＣ＿ＨＬＶ２→２＋２、およびＨＥＣ＿ＨＬＶとする。
【００５１】
因子の１／２倍算を行なう場合、まず、入力因子により、図２に示す通りに場合分けを行なう。入力因子のｗｅｉｇｈｔが２で、かつＵ２の１次の項の係数がｕ２１≠０を満たす場合は、ＨＥＣ＿ＨＬＶで計算を行なう。ＨＥＣ＿ＨＬＶのアルゴリズムについては、非特許文献１５（Ａｌｇｏｒｉｔｈｍ３）に記載されている。ＨＥＣ＿ＨＬＶはＨａｒｌｅｙＤＢＬの逆演算であるため、１／２倍算の中でＨＥＣ＿ＨＬＶの処理が非常に高い確率でおこる。その他の例外処理の起こる確率は非常に低い。このＨＥＣ＿ＨＬＶ以外の場合は例外処理を行う。
【００５２】
入力因子のｗｅｉｇｈｔが２で、かつＵ２の項の係数がｕ２１＝０を満たす場合は、ＨａｒｌｅｙＤＢＬ２＋２→２の逆演算であるＥｘＨＥＣ＿ＨＬＶ２→２＋２、もしくは、ＨａｒｌｅｙＤＢＬ１＋１→２の逆演算であるＥｘＨＥＣ＿ＨＬＶ２→１＋１で計算を行なう。これらのアルゴリズムは非特許文献１６（４．２，４．３）に示されている。
【００５３】
また、入力因子のｗｅｉｇｈｔが１の場合は、ＨａｒｌｅｙＤＢＬ２＋２→１の逆演算であるＥｘＨＥＣ＿ＨＬＶ１→２＋２で計算を行う。このアルゴリズムは非特許文献１６（４．１）に記載されている。
【００５４】
１／２倍算では，有限体の平方根計算と、有限体上での２次方程式を解くための計算が必要となる。このため、２倍算になかった平方根演算と、２次方程式を解くためのハーフトレース演算と、トレース演算が必要となる。トレース演算の計算量は無視できる程度であるが、平方根演算とハーフトレース演算の計算量は有限体によって異なり、無視できる場合もあるが、無視できない場合もある。
【００５５】
（ｂ２）超楕円曲線暗号における加算と１／２倍算の組み合わせに基づく因子のスカラー倍算
次に、上述の１／２倍算を適用して実現される超楕円曲線暗号における加算と１／２倍算の組み合わせに基づく因子のスカラー倍算について説明する。超楕円曲線暗号における因子のスカラー倍算は、前述の
（ａ）加算と２倍算の組み合わせ、
において実現できるととともに、加算と１／２倍算の組み合わせでも実現できる。この処理については、非特許文献１６（Ａｌｇｏｒｉｔｈｍ６）において示されている。以下、超楕円曲線暗号における加算と１／２倍算の組み合わせによるスカラー倍算の処理の概要について説明する。
【００５６】
超楕円曲線暗号における因子のスカラー倍算は超楕円加算と超楕円１／２倍算で計算する手順について説明する。
まずスカラー値ｄを因子のオーダーｒを法として１／２進数展開し、それをｄ'とする。具体的には、ｄ'を以下のように表現する。
【数６】
2008020757.tif 000008
【００５７】
上記式において、ｍはオーダーｒのビット長とする。この処理の詳細アルゴリズムを以下に、アルゴリズム３（Ａｌｇｏｒｉｔｈｍ３：Ｓｃａｌａｒ  ｖａｌｕｅ  ｃｏｎｖｅｒｓｉｏｎ）として示す。
【数７】
2008020757.tif 000009
【００５８】
加算と１／２倍算の組み合わせによるスカラー倍算のアルゴリズムとして基本的なＨａｌｖｅ−ａｎｄ−ａｄｄ  ｂｉｎａｒｙ法の中で、
（ア）ｒｉｇｈｔ−ｔｏ−ｌｅｆｔ法と、
（イ）ｌｅｆｔ−ｔｏ−ｒｉｇｈｔ法、
これらの２種類の手法について説明する。なお、ここで、
ｄ'の２進数表現を（ｄ'ｌ−１，...，ｄ'０），
ただし、
ｄ'ｌ−１＝１，
ｄ'ｌ−２，...，ｄ'０＝１ｏｒ０
とする。
【００５９】
（ア）Ｈａｌｖｅ−ａｎｄ−ａｄｄ  ｂｉｎａｒｙ（ｒｉｇｈｔ−ｔｏ−ｌｅｆｔ）法
ｒｉｇｈｔ−ｔｏ−ｌｅｆｔ法は、２進数表現されたスカラー値ｄ'を下位ビットから見ていき、
ｄ'ｉ＝１
の場合に、
［１／２ｉ］Ｄ０
を加算することが特徴である。
このｒｉｇｈｔ−ｔｏ−ｌｅｆｔ法のアルゴリズムを以下に、アルゴリズム４（Ａｌｇｏｒｉｔｈｍ４：Ｈａｌｖｅ−ａｎｄ−ａｄｄ  ｂｉｎａｒｙ  （ｒｉｇｈｔ−ｔｏ−ｌｅｆｔ）法）として示す。
【数８】
2008020757.tif 000010
【００６０】
上記のアルゴリズム４（Ａｌｇｏｒｉｔｈｍ４）では，スカラー倍ｄＤ０を計算するために、前述のアルゴリズム３（Ａｌｇｏｒｉｔｈｍ３）を用いて、スカラー値ｄを１／２進数展開したｄ'を入力として与えている。
【００６１】
（イ）Ｈａｌｖｅ−ａｎｄ−ａｄｄ  ｂｉｎａｒｙ（ｌｅｆｔ−ｔｏ−ｒｉｇｈｔ）法
ｌｅｆｔ−ｔｏ−ｒｉｇｈｔ法は、２進数表現されたスカラー値ｄ'を上位ビットから見ていき、毎ビットＤを１／２倍して、
ｄ'ｉ＝１
の場合に、ベースポイントを加算することが特徴である。
【００６２】
このｌｅｆｔ−ｔｏ−ｒｉｇｈｔ法のアルゴリズムの詳細を以下に、アルゴリズム５（Ａｌｇｏｒｉｔｈｍ５：Ｈａｌｖｅ−ａｎｄ−ａｄｄ  ｂｉｎａｒｙ  （ｌｅｆｔ−ｔｏ−ｒｉｇｈｔ）法）として示す。
【数９】
2008020757.tif 000011
【００６３】
上記アルゴリズム５（Ａｌｇｏｒｉｔｈｍ５）では、スカラー倍ｄＤ０を計算するために、前述のアルゴリズム３（Ａｌｇｏｒｉｔｈｍ３）を用いて、スカラー値ｄを１／２進数展開したｄ'を入力として与えている。
【００６４】
上述したように、超楕円曲線暗号では、因子のスカラー倍算を計算する方法として、
（ａ）加算と２倍算を用いる方法、
（ｂ）加算と１／２倍算を用いる方法、
これらの２種類の手法が知られている。
上記の２つの手法について記載した従来技術として、非特許文献１５、非特許文献１６がある。これらの文献には、１／２倍算の適用により、高速演算を実現する構成が記載されている。
【非特許文献１】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.
【非特許文献１５】I. Kitamura, M. Katagi, and T. Takagi, A Complete Divisor Class Halving Algorithm for Hyperelliptic Curve Cryptosystems of Genus Two. ACISP 2005, LNCS 3574, pp.146-157, 2005.
【非特許文献１６】Kitamura, M. Katagi, and T. Takagi, A Complete Divisor Class Halving Algorithm for Hyperelliptic Curve Cryptosystems of Genus Two. Cryptology ePrint Archive, 2004/255, IACR, 2004
【発明の開示】
【発明が解決しようとする課題】
【００６５】
現在、実用フェーズに入りつつある楕円曲線暗号（ＥＣＣ）アルゴリズムに対して、その拡張概念である超楕円曲線暗号（ＨＥＣＣ）アルゴリズムは、現在、学会レベルで高速アルゴリズムや、その実装方法についての研究が進められている。超楕円曲線暗号（ＨＥＣＣ）のスカラー倍算の演算時間は、楕円曲線暗号（ＥＣＣ）に近づきつつある程度に過ぎず、さらなる高速化が望まれている。
【００６６】
本発明は、このような現状に鑑みてなされたものであり、超楕円曲線暗号（ＨＥＣＣ）のスカラー倍算の演算時間を短縮し、高速処理可能な超楕円曲線暗号（ＨＥＣＣ）演算処理を実現する暗号処理装置、および暗号処理演算方法、並びにコンピュータ・プログラムを提供することを目的とする。
【００６７】
上述したように、超楕円曲線暗号では、因子のスカラー倍算を計算する方法として、
（ａ）加算と２倍算を用いる方法、
（ｂ）加算と１／２倍算を用いる方法、
これらの２種類の手法が知られており、１／２倍算の適用により高速演算が実現されることがあることが知られている。しかし、２倍算を適用した場合より、１／２倍算を適用した場合に演算が高速化されるのは、超楕円曲線暗号において適用する曲線パラメータや有限体が特定の条件を満たす場合であり、全ての条件で、１／２倍算の適用が２倍算の適用より高速になるものではない。条件によっては、１／２倍算より２倍算を適用した方が高速演算が可能となるケースがある。
【００６８】
本発明は、超楕円曲線暗号における因子のスカラー倍算処理において、与えられた条件、例えば超楕円暗号曲線の設定条件に基づいて、
（ａ）加算と２倍算を用いる方法、
（ｂ）加算と１／２倍算を用いる方法、
これら（ａ），（ｂ）のいずれのアルゴリズムが高速演算可能かを判断して、高速なアルゴリズムを、適宜選択して実行することで、高速な暗号処理演算を実行することを可能とした暗号処理装置、および暗号処理演算方法、並びにコンピュータ・プログラムを提供することを目的とする。
【課題を解決するための手段】
【００６９】
本発明の第１の側面は、
超楕円曲線暗号に基づく暗号処理演算を実行する暗号処理装置であり、
暗号処理演算に適用する超楕円曲線の曲線パラメータに基づいて、スカラー倍算アルゴリズムとして、２倍算適用演算アルゴリズムと、１／２倍算適用演算アルゴリズムのいずれの演算アルゴリズムが高速演算可能かを判定する制御部と、
高速演算可能と判定されたアルゴリズムを選択適用して、超楕円曲線暗号におけるスカラー倍算処理を実行する演算処理部と、
を有することを特徴とする暗号処理装置にある。
【００７０】
さらに、本発明の暗号処理装置の一実施態様において、前記制御部は、超楕円曲線の曲線パラメータと、高速演算の実行可能なアルゴリズム情報とを対応付けたテーブルを記憶部から取得し、暗号処理演算に適用する超楕円曲線の曲線パラメータと前記テーブルに記録された曲線パラメータ情報とを比較照合し、一致または類似するテーブル記録データに対応して設定されたアルゴリズム情報を高速演算可能なアルゴリズムと判定する処理を実行する構成であることを特徴とする。
【００７１】
さらに、本発明の暗号処理装置の一実施態様において、前記演算処理部は、２倍算適用演算アルゴリズムと、１／２倍算適用演算アルゴリズムの両アルゴリズムを実行可能な構成を有し、２倍算および１／２倍算において共通に利用する演算実行ハードウェアまたはプログラムを利用した演算処理を実行する構成であることを特徴とする。
【００７２】
さらに、本発明の暗号処理装置の一実施態様において、前記制御部は、暗号処理演算に適用する超楕円曲線の曲線パラメータ、および暗号処理演算に適用する有限体のタイプに基づいて、スカラー倍算アルゴリズムとして、２倍算適用演算アルゴリズムと、１／２倍算適用演算アルゴリズムのいずれの演算アルゴリズムが高速演算可能かを判定する処理を実行する構成であることを特徴とする。
【００７３】
さらに、本発明の暗号処理装置の一実施態様において、前記制御部は、暗号処理演算に適用する超楕円曲線の曲線パラメータに基づいて、スカラー倍算における１／２倍算適用演算アルゴリズムの高速実行可能性の有無を判定し、１／２倍算適用演算アルゴリズムの高速実行可能性有りと判定した場合に、２倍算適用演算アルゴリズムと、１／２倍算適用演算アルゴリズムのいずれの演算アルゴリズムが高速演算可能かを判定する処理を実行する構成であることを特徴とする。
【００７４】
さらに、本発明の暗号処理装置の一実施態様において、前記制御部は、暗号処理演算に適用する種数２、標数２の有限体上定義された超楕円曲線：ｙ２＋ｈ（ｘ）ｙ＝ｆ（ｘ）の曲線パラメータに含まれるコファクター［ｃ］が２で、ｈ（ｘ）が既約多項式の場合に、１／２倍算適用演算アルゴリズムの高速実行可能性高速に計算が可能であると判定する構成であることを特徴とする。
【００７５】
さらに、本発明の暗号処理装置の一実施態様において、前記暗号処理装置は、暗号処理演算に適用する超楕円曲線の曲線パラメータを適用した２倍算適用演算と、１／２倍算適用演算を実行して処理時間を計測する演算速度算出手段を有し、前記制御部は、前記演算速度算出手段の算出結果に基づいて、スカラー倍算アルゴリズムとして、２倍算適用演算アルゴリズムと、１／２倍算適用演算アルゴリズムのいずれの演算アルゴリズムが高速演算可能かの判定処理を実行する構成であることを特徴とする。
【００７６】
さらに、本発明の第２の側面は、
暗号処理装置において、超楕円曲線暗号に基づく暗号処理演算を実行する暗号処理演算方法であり、
制御部において、超楕円曲線の曲線パラメータに基づいて、スカラー倍算アルゴリズムとして、２倍算適用演算アルゴリズムと、１／２倍算適用演算アルゴリズムのいずれの演算アルゴリズムが高速演算可能かを判定する演算時間検証ステップと、
演算処理部において、前記演算時間検証ステップにおいて高速演算可能と判定されたアルゴリズムを選択適用して、超楕円曲線暗号におけるスカラー倍算処理を実行する演算実行ステップと、
を有することを特徴とする暗号処理演算方法にある。
【００７７】
さらに、本発明の暗号処理演算方法の一実施態様において、前記演算時間検証ステップは、超楕円曲線の曲線パラメータと、高速演算の実行可能なアルゴリズム情報とを対応付けたテーブルを参照して、２倍算適用演算アルゴリズムと、１／２倍算適用演算アルゴリズムのいずれの演算アルゴリズムが高速演算可能かを判定する処理を実行するステップであることを特徴とする。
【００７８】
さらに、本発明の暗号処理演算方法の一実施態様において、前記演算時間検証ステップは、暗号処理演算に適用する超楕円曲線の曲線パラメータ、および暗号処理演算に適用する有限体のタイプに基づいて、スカラー倍算アルゴリズムとして、２倍算適用演算アルゴリズムと、１／２倍算適用演算アルゴリズムのいずれの演算アルゴリズムが高速演算可能かを判定する処理を実行するステップであることを特徴とする。
【００７９】
さらに、本発明の暗号処理演算方法の一実施態様において、前記演算時間検証ステップは、暗号処理演算に適用する超楕円曲線の曲線パラメータに基づいて、スカラー倍算における１／２倍算適用演算アルゴリズムの高速実行可能性の有無を判定し、１／２倍算適用演算アルゴリズムの高速実行可能性有りと判定した場合に、２倍算適用演算アルゴリズムと、１／２倍算適用演算アルゴリズムのいずれの演算アルゴリズムが高速演算可能かを判定する処理を実行するステップであることを特徴とする。
【００８０】
さらに、本発明の暗号処理演算方法の一実施態様において、１／２倍算適用演算アルゴリズムの高速実行可能性の有無を判定する処理は、暗号処理演算に適用する種数２、標数２の有限体上定義された超楕円曲線：ｙ２＋ｈ（ｘ）ｙ＝ｆ（ｘ）の曲線パラメータに含まれるコファクター［ｃ］が２で、ｈ（ｘ）が既約多項式の場合に、１／２倍算適用演算アルゴリズムの高速実行可能性高速に計算が可能であると判定する処理であることを特徴とする。
【００８１】
さらに、本発明の暗号処理演算方法の一実施態様において、前記暗号処理演算方法は、さらに、演算速度算出手段において、暗号処理演算に適用する超楕円曲線の曲線パラメータを適用した２倍算適用演算と、１／２倍算適用演算を実行して処理時間を計測する演算速度算出ステップを有し、前記演算時間検証ステップは、前記演算速度算出ステップにおける算出結果に基づいて、スカラー倍算アルゴリズムとして、２倍算適用演算アルゴリズムと、１／２倍算適用演算アルゴリズムのいずれの演算アルゴリズムが高速演算可能かの判定処理を実行するステップであることを特徴とする。
【００８２】
さらに、本発明の第３の側面は、
暗号処理装置において、超楕円曲線暗号に基づく暗号処理演算を実行させるコンピュータ・プログラムであり、
制御部において、超楕円曲線の曲線パラメータに基づいて、スカラー倍算アルゴリズムとして、２倍算適用演算アルゴリズムと、１／２倍算適用演算アルゴリズムのいずれの演算アルゴリズムが高速演算可能かを判定させる演算時間検証ステップと、
演算処理部において、前記演算時間検証ステップにおいて高速演算可能と判定されたアルゴリズムを選択適用して、超楕円曲線暗号におけるスカラー倍算処理を実行させる演算実行ステップと、
を実行させることを特徴とするコンピュータ・プログラムにある。
【００８３】
なお、本発明のコンピュータ・プログラムは、例えば、様々なプログラム・コードを実行可能なコンピュータ・システムに対して、コンピュータ可読な形式で提供する記憶媒体、通信媒体、例えば、ＣＤやＦＤ、ＭＯなどの記録媒体、あるいは、ネットワークなどの通信媒体によって提供可能なコンピュータ・プログラムである。このようなプログラムをコンピュータ可読な形式で提供することにより、コンピュータ・システム上でプログラムに応じた処理が実現される。
【００８４】
本発明のさらに他の目的、特徴や利点は、後述する本発明の実施例や添付する図面に基づくより詳細な説明によって明らかになるであろう。なお、本明細書においてシステムとは、複数の装置の論理的集合構成であり、各構成の装置が同一筐体内にあるものには限らない。
【発明の効果】
【００８５】
本発明の一実施例構成によれば、超楕円曲線暗号の因子Ｄに対するスカラー倍算を実行する構成において、暗号処理演算に適用する超楕円曲線の曲線パラメータに基づいて、スカラー倍算アルゴリズムとして、２倍算適用演算アルゴリズムと、１／２倍算適用演算アルゴリズムのいずれの演算アルゴリズムが高速演算可能かの判定を行ない、高速演算可能と判定されたアルゴリズムを選択適用してスカラー倍算処理を実行する構成としたので、様々な曲線に対応する暗号処理に伴うスカラー倍算を、確実に高速な処理で行なうことが可能となる。すなわち、曲線パラメータに応じたアルゴリズム選択により、スカラー倍算における計算量を削減した高速演算が実現される。
【発明を実施するための最良の形態】
【００８６】
以下、本発明の暗号処理装置および暗号処理演算方法、並びにコンピュータ・プログラムの詳細について説明する。
【００８７】
本発明は、楕円曲線暗号を一般化した超楕円曲線暗号（ＨＥＣＣ：Hyper Elliptic Curve Cryptography）についての高速化演算手法である。前述したように、超楕円曲線では曲線を特徴づける値は種数（ｇｅｎｕｓ）ｇである。ｐを素数、ｎを正の整数、ｑ＝ｐｎとする。このとき有限体Ｆｑ上で定義される種数ｇの超楕円曲線Ｃは以下の方程式、
ｙ２＋ｈ（ｘ）ｙ＝ｆ（ｘ）
で定義される。ここで、ｈ（ｘ），ｆ（ｘ）∈Ｆｑ［ｘ］，ｆ（ｘ）は、次数２ｇ＋１のｍｏｎｉｃ多項式である。
【００８８】
超楕円曲線Ｃ上の点Ｐ＝（ｘ、ｙ）に対する共役点（ｏｐｐｏｓｉｔｅ  ｐｏｉｎｔ）は、−Ｐ＝（ｘ、−ｙ−ｈ（ｘ））として定義される。また、Ｐ＝−Ｐである点を分岐点（ｒａｍｉｆｉｃａｔｉｏｎ  ｐｏｉｎｔ）と呼ぶ。
【００８９】
超楕円曲線暗号の定義体の演算サイズ（ビット長）は楕円曲線暗号と同等の安全性を仮定した場合、楕円曲線の定義体の演算サイズに比べて１／ｇに小さくなることが知られている。演算サイズが小さいことは実装上メリットがあり、超楕円曲線暗号の利点の一つして挙げられる。
【００９０】
前述したように、超楕円曲線暗号では点の形式的和である因子（ｄｉｖｉｓｏｒ）をＤ１とし、スカラー倍算ｋＤ１で定義される因子をＤ２とすると、Ｄ２からｋを求める問題は超楕円曲線におけるヤコビ多様体上の離散対数問題として公開鍵暗号として用いることができる。
【００９１】
ここで、因子（ｄｉｖｉｓｏｒ）は有理点の形式和であり、以下の形式で表現することができる。
【数１０】
2008020757.tif 000012
【００９２】
また、半被約因子（ｓｅｍｉ  ｒｅｄｕｃｅｄ  ｄｉｖｉｓｏｒ）は、以下の形式で表現することができる。
【数１１】
2008020757.tif 000013
【００９３】
ただし、Ｐｉ＝（ｘｉ、ｙｉ）かつｉ≠ｊに対してＰｉ≠Ｐｊである。
【００９４】
また、ΣｍｉをＤのウェイト（ｗｅｉｇｈｔ）と呼ぶ。さらにウェイト（ｗｅｉｇｈｔ）が種数ｇ以下である半被約因子を被約因子（ｒｅｄｕｃｅｄ  ｄｉｖｉｓｏｒ）と呼ぶ。
【００９５】
超楕円曲線のヤコビ（Ｊａｃｏｂｉ）多様体上の任意の半被約因子Ｄは下記の多項式Ｕ、Ｖ∈Ｆｑ［ｘ］を用いてＤ＝（Ｕ、Ｖ）として表現できる。これをマンホード（Ｍｕｍｆｏｒｄ）表現と呼ぶ。
【数１２】
2008020757.tif 000014
【００９６】
種数（ｇｅｎｕｓ）２の任意の被約因子Ｄはマンホード（Ｍｕｍｆｏｒｄ）表現を用いると、有限体Ｆｑ上の元を係数に持つ２次以下の多項式の組、すなわち、
（Ｕ、Ｖ）＝（ｘ２＋ｕ１ｘ＋ｕ０、ｖ１ｘ＋ｖ０）、または、
（Ｕ、Ｖ）＝（ｘ＋ｘ０、ｙ０）
として表現することができる。
また、零元は、
（Ｕ，Ｖ）＝（１，０）＝Ｏ
として表現される。
【００９７】
上述したように、超楕円曲線暗号では、因子のスカラー倍算を計算する方法として、
（ａ）加算と２倍算を用いる方法、
（ｂ）加算と１／２倍算を用いる方法、
これらの２種類の手法が知られている。本発明は、超楕円曲線暗号における因子のスカラー倍算処理において、与えられた条件、例えば超楕円暗号曲線において適用する曲線パラメータや有限体の様々な設定条件に基づいて、
（ａ）加算と２倍算を用いる方法、
（ｂ）加算と１／２倍算を用いる方法、
これら（ａ），（ｂ）のいずれのアルゴリズムが高速演算可能かを判断して、高速なアルゴリズムを、適宜選択して実行することで、高速な暗号処理演算を実行することを可能とするものである。以下、本発明の実施例について、以下に示す項目に従って、順次説明する。
【００９８】
（１）種数２、標数２の有限体上定義された超楕円曲線の因子Ｄに対して、２倍算もしくは１／２倍算を計算する方法。
（２）種数２、標数２の有限体上定義された超楕円曲線の因子Ｄに対するスカラー倍算の演算処理において、
（ａ）加算および２倍算を適用した演算アルゴリズム、
（ｂ）加算および１／２倍算を適用した演算アルゴリズム、
これらの各演算アルゴリズムを用いて、因子のスカラー倍算を計算する方法。
（３）種数２、標数２の有限体上定義された超楕円曲線の因子Ｄに対するスカラー倍算の演算処理において、
（ａ）加算および２倍算を適用した演算アルゴリズム、
（ｂ）加算および１／２倍算を適用した演算アルゴリズム、
これらのどちらの処理が高速かを判断する方法。
（４）種数２、標数２の有限体上定義された超楕円曲線の因子Ｄに対するスカラー倍算の演算処理において、
（ａ）加算および２倍算を適用した演算アルゴリズム、
（ｂ）加算および１／２倍算を適用した演算アルゴリズム、
から高速演算可能なアルゴリズムを選択して因子のスカラー倍算を実行する構成。
【００９９】
以下、これらの各項目（１）〜（４）について順次、説明する。
【０１００】
（１）種数２、標数２の有限体上定義された超楕円曲線の因子Ｄに対して、２倍算もしくは１／２倍算を計算する方法。
まず、種数２、標数２の有限体上定義された超楕円曲線の因子Ｄに対して、２倍算もしくは１／２倍算を計算する装置構成および方法について説明する。
【０１０１】
本発明は、標数２の有限体上定義された種数２の超楕円曲線に関するものであり、以下の説明では、曲線の種数を２、定義体の標数を２とする。
【０１０２】
種数２、標数２の有限体上定義された超楕円曲線の因子Ｄに対する２倍算処理は、先に図１（Ｂ）を参照して説明した処理によって実行される。２倍算は、因子Ｄについて、Ｄ＋Ｄ＝２Ｄを算出する処理である。入力をＤ１＝（Ｕ１，Ｖ１）とし、出力をＤ２＝［２］Ｄ１とする。
図１（Ｂ）を参照して説明したように、因子Ｄ１のｗｅｉｇｈｔが
ｗｅｉｇｈｔ２、
ｗｅｉｇｈｔ１、
ｗｅｉｇｈｔ０、
によってそれぞれ異なる処理を行う。
【０１０３】
ｗｅｉｇｈｔ２の場合、因子が分岐点を含むかどうかをチェックし、含まなければ、図１（Ｂ）に示すように、（４ａ）ＨａｒｌｅｙＤＢＬの処理を行う。因子が分岐点を含む場合は（４ｂ）例外処理６を行う。ｇｃｄ（ｈ，Ｕ１）＝１であれば、Ｄ１は分岐点を含まない。この場合、（４ａ）ＨａｒｌｅｙＤＢＬの処理を行う。この処理が、Ｍｏｓｔ  Ｆｒｅｑｕｅｎｔ  Ｃａｓｅ、すなわち、非常に高い確率でおこる。その他の例外処理の起こる確率は非常に低い。Ｍｏｓｔ  Ｆｒｅｑｕｅｎｔ  Ｃａｓｅの条件を満たさない場合は例外処理６を行う。
【０１０４】
ｗｅｉｇｈｔ１の場合も同様にｇｃｄ（ｈ，Ｕ１）＝１かどうかをチェックし，（５ａ）の処理、ＥｘＨａｒＤＢＬ１＋１→２もしくは、（５ｂ）の処理である例外処理７を行う。
【０１０５】
ＨａｒｌｅｙＤＢＬは、上述のようにＭｏｓｔ  Ｆｒｅｑｕｅｎｔ  Ｃａｓｅと呼ばれ、ランダムに因子を発生させて２倍算を行うと、非常に高い確率でＨａｒｌｅｙＤＢＬの処理になる。
【０１０６】
先に背景技術の欄で説明したように、このＭｏｓｔ  Ｆｒｅｑｕｅｎｔ  Ｃａｅｓ以外の処理になる確率はＯ（１／ｑ）である。ここでｑは定義体の要素数であり、安全な暗号用途ではqgが１６０ｂｉｔ程度必要になる大きな数であるので現実的には２倍算の処理では、ＨａｒｌｅｙＤＢＬしか発生しない状況とみなすことができる。
【０１０７】
ＨａｒｌｅｙＤＢＬの演算処理アルゴリズムは公知のものであり、先に説明した非特許文献５（M.Takahashi. Improving Harley algorithms for Jacobians of genus 2 hyperelliptic curves. SCIS2002. (Japanese)）に示されている。
【０１０８】
超楕円曲線の因子Ｄに対する２倍算処理（ＨａｒｌｅｙＤＢＬの演算処理アルゴリズム）において必要となる有限体の演算は、加算、乗算、２乗算、逆元演算の４種類である。
【０１０９】
また、種数２、標数２の有限体上定義された超楕円曲線の因子Ｄに対する１／２倍算処理は、先に図２を参照して説明した処理によって実行される。入力をＤ２＝（Ｕ２，Ｖ２）とし、出力をＤ１＝［１／２］Ｄ２とする。なお、因子は位数がｒのものとする。つまり、扱う因子は分岐点を持たない。入力因子Ｄ２＝（Ｕ２，Ｖ２）は以下のように示すことができる。
Ｄ２＝（Ｕ２，Ｖ２）、
Ｕ２＝ｕ２２ｘ２＋ｕ２１ｘ＋ｕ２０、
Ｖ２＝ｖ２１ｘ＋ｖ２０、
ｕ２２＝０ｏｒ１
とする。分岐点を持たないため、１／２倍算として、
ＥｘＨａｒＤＢＬ１＋１→２、ＥｘＨａｒＤＢＬ２＋２→１、ＥｘＨａｒＤＢＬ２＋２→２、および、ＨａｒｌｅｙＤＢＬの４つの逆演算を考えればよい。ＨａｒｌｅｙＤＢＬ以外は例外ケースである。
【０１１０】
ここでＥｘＨａｒＤＢＬ２＋２→１は入力因子のｗｅｉｇｈｔが２で、出力因子のｗｅｉｇｈｔが１の場合を計算する方法である。また、ＥｘＨａｒＤＢＬ２＋２→２  は入力因子のｗｅｉｇｈｔが２で、かつＵ２の１次の項の係数がｕ２１＝０を満たし、出力因子のｗｅｉｇｈｔが２の場合を計算する方法である。ただし、ＥｘＨａｒＤＢＬ２＋２→２はＨａｒｌｅｙＤＢＬで計算できるが、これの逆演算である１／２倍算は、例外ケースとなるため、ここでは、ＥｘＨａｒＤＢＬ２＋２→２を例外ケースとして扱う。
【０１１１】
これら、ＥｘＨａｒＤＢＬ１＋１→２、ＥｘＨａｒＤＢＬ２＋２→１、ＥｘＨａｒＤＢＬ２＋２→２、および、ＨａｒｌｅｙＤＢＬに対応する１／２倍算をそれぞれ、ＥｘＨＥＣ＿ＨＬＶ２→１＋１、ＥｘＨＥＣ＿ＨＬＶ１→２＋２、ＥｘＨＥＣ＿ＨＬＶ２→２＋２、およびＨＥＣ＿ＨＬＶとする。
【０１１２】
因子の１／２倍算を行なう場合、まず、入力因子により、図２に示す通りに場合分けを行なう。入力因子のｗｅｉｇｈｔが２で、かつＵ２の１次の項の係数がｕ２１≠０を満たす場合は、ＨＥＣ＿ＨＬＶで計算を行なう。ＨＥＣ＿ＨＬＶはＨａｒｌｅｙＤＢＬの逆演算であるため、１／２倍算の中でＨＥＣ＿ＨＬＶの処理が非常に高い確率でおこる。その他の例外処理の起こる確率は非常に低い。このＨＥＣ＿ＨＬＶ以外の場合は例外処理を行う。
【０１１３】
入力因子のｗｅｉｇｈｔが２で、かつＵ２の項の係数がｕ２１＝０を満たす場合は、ＨａｒｌｅｙＤＢＬ２＋２→２の逆演算であるＥｘＨＥＣ＿ＨＬＶ２→２＋２、もしくは、ＨａｒｌｅｙＤＢＬ１＋１→２の逆演算であるＥｘＨＥＣ＿ＨＬＶ２→１＋１で計算を行なう。また、入力因子のｗｅｉｇｈｔが１の場合は、ＨａｒｌｅｙＤＢＬ２＋２→１の逆演算であるＥｘＨＥＣ＿ＨＬＶ１→２＋２で計算を行う。
【０１１４】
１／２倍算では，有限体の平方根計算と、有限体上での２次方程式を解くための計算が必要となる。このため、２倍算になかった平方根演算と、２次方程式を解き、根を求めるハーフトレース演算と、二次方程式の根があるか否かの判定演算としてのトレース演算が必要となる。
【０１１５】
図３に、超楕円曲線の因子Ｄに対する２倍算、および１／２倍算の双方を算出可能とした暗号処理装置の演算手段の構成例を示す。演算手段１００は、図３に示すように、群演算手段１１０、有限体演算手段１２０から構成される。
【０１１６】
超楕円曲線の因子Ｄに対する２倍算、または、１／２倍算処理を実行する場合、入力データ１０として、適用する超楕円曲線を定義する曲線パラメータ１１、２倍算、１／２倍算のいずれを実行するかを示す群演算種類情報１２、さらに、実際の演算対象となる入力因子１３の各情報が演算手段１００に入力される。これらの入力データに基づいて、演算手段１００において２倍算または１／２倍算が実行されて処理結果としての出力因子２１を出力データ２０として出力する。
【０１１７】
演算手段１００では、２倍算と１／２倍算のいずれの場合においても、入力値である因子を表現する有限体上定義された多項式に対して、それぞれの演算アルゴリズムに従った有限体の演算を実行する。そのため、２倍算と１／２倍算実現のためには、有限体の各種演算を実行する有限体演算手段１２０と、２倍算、および１／２倍算処理手続きと途中の演算結果を保存する手段としての群演算手段１１０が必要となる。
【０１１８】
群演算手段１１０には、２倍算処理の際、演算処理手続きと途中の演算結果を保存する手段としての２倍算処理手段１１１、１／２倍算処理の際、演算処理手続きと途中の演算結果を保存する手段としての１／２倍算処理手段１１２が含まれる。
【０１１９】
また、有限体演算手段１２０には、２倍算と１／２倍算のそれぞれの演算アルゴリズムに従った有限体の演算を実行するための各種の演算手段が含まれる。先に説明したように、超楕円曲線の因子Ｄに対する２倍算処理において必要となる有限体の演算は、加算、乗算、２乗算、逆元演算の４種類であり、１／２倍算では，これらの加算、乗算、２乗算、逆元演算の４種類に加えて、有限体の平方根計算と、有限体上での２次方程式を解くための演算、すなわち、２次方程式を解き、根を求めるハーフトレース演算と、二次方程式の根があるか否かの判定演算としてのトレース演算が必要となる。
【０１２０】
従って、有限体演算手段１２０には、加算手段１２１、乗算手段１２２、２乗算手段１２３、逆元演算手段１２４、平方根演算手段１２５、ハーフトレース演算手段１２６、トレース演算手段１２７が含まれる。加算手段１２１、乗算手段１２２、２乗算手段１２３、逆元演算手段１２４は、例えばハードウェア構成、プログラムにおいて２倍算、１／２倍算各々に専用の構成とするのではなく、いずれの処理においても共通に利用可能な１つの構成とする。このように、加算手段１２１、乗算手段１２２、２乗算手段１２３、逆元演算手段１２４を２倍算、１／２倍算個別に構成することなく、共有構成とすることにより、演算手段の構成としてのハードウェアサイズ、プログラムサイズを小型化することが可能となる。ハードウェアを用いた場合はゲート数の削減、装置の小型化を実現することができる。
【０１２１】
また、超楕円曲線の因子Ｄの加算処理は、先に、図１（Ａ）を参照して説明した処理によって実行される。種数２の場合の因子の加算Ｄ１＋Ｄ２において、因子Ｄ１、Ｄ２は、それぞれＤ１＝（Ｕ１、Ｖ１）、Ｄ２＝（Ｕ２、Ｖ２）とした場合、まず、因子のウェイト（ｗｅｉｇｈｔ）の値によって場合分けが行われる。すなわち、［Ｄ１＋Ｄ２］の各ウェイト（ｗｅｉｇｈｔ）の値によって、
（１）ｗｅｉｇｈｔ２＋ｗｅｉｇｈｔ２
（２）ｗｅｉｇｈｔ２＋ｗｅｉｇｈｔ１
（３）例外処理１
の場合分けが行なわれる。
【０１２２】
次にｗｅｉｇｈｔ２同士の加算、すなわち（１）ｗｅｉｇｈｔ２＋ｗｅｉｇｈｔ２の場合、因子Ｄ１＝（Ｕ１、Ｖ１）、Ｄ２＝（Ｕ２、Ｖ２）について、最大公約数ｇｃｄ（Ｕ１、Ｕ２）＝１であれば、２つの因子Ｄ１＝（Ｕ１、Ｖ１）、Ｄ２＝（Ｕ２、Ｖ２）は、互いに同一または共役点（ｏｐｐｏｓｉｔｅ  ｐｏｉｎｔ）を含まない。この場合、
（１ａ）ＨａｒｌｅｙＡＤＤ、
すなわちハーレーアルゴリズムに従った加算処理を行う。（１ａ）ＨａｒｌｅｙＡＤＤの処理は例えば非特許文献７に示されているＭｏｓｔ  Ｆｒｅｑｕｅｎｔ  Ｃａｓｅと呼ばれる処理である。このＭｏｓｔ  Ｆｒｅｑｕｅｎｔ  Ｃａｓｅは、種数２の場合の因子の加算Ｄ１＋Ｄ２処理において、高確率で発生するケースである。
【０１２３】
この（１ａ）ＨａｒｌｅｙＡＤＤの処理は、非常に高い確率でおこる。その他の例外処理の起こる確率は非常に低い。Ｍｏｓｔ  Ｆｒｅｑｕｅｎｔ  Ｃａｓｅの条件を満たさない場合、すなわち、因子Ｄ１＝（Ｕ１、Ｖ１）、Ｄ２＝（Ｕ２、Ｖ２）について、最大公約数ｇｃｄ（Ｕ１、Ｕ２）＝１を満足しない場合は、
（１ｂ）例外処理２を行う。
【０１２４】
（２）ｗｅｉｇｈｔ２＋ｗｅｉｇｈｔ１の場合についても同様に、ｇｃｄ（Ｕ１、Ｕ２）＝１かどうかをチェックし、ｇｃｄ（Ｕ１、Ｕ２）＝１を満足する場合には、
（２ａ）ＥｘＨａｒＡＤＤ２＋１→２を実行し、
ｇｃｄ（Ｕ１、Ｕ２）＝１を満足しない場合には、
（２ｂ）例外処理３を行う。
（３）例外処理１は、ｗｅｉｇｈｔの場合分けが上記（１），（２）以外の場合である。
【０１２５】
なお、上述した種数２の加算処理のアルゴリズムの詳細については、先に説明した非特許文献８（T.Lange, Efficient arithmetic on genus 2 hyperelliptic curves over finite fields via explicit formulae. Cryptology ePrint Archive, 2002/121, IACR, 2002.）に記載されている。
【０１２６】
超楕円曲線の因子Ｄの加算処理に必要となる有限体の演算は２倍算と同様であり、加算、乗算、２乗算、逆元演算の４種類である。従って、２倍算、１／２倍算に加えて加算処理も実行可能とする演算手段は、図４に演算手段１５０として示すように、図３に示す演算手段１００の持つ有限体演算手段１２０と同様の構成、すなわち、加算手段１２１、乗算手段１２２、２乗算手段１２３、逆元演算手段１２４、平方根演算手段１２５、ハーフトレース演算手段１２６、トレース演算手段１２７を持つ有限体演算手段１２０と、２倍算処理手段１６１、１／２倍算処理手段１６２に加え、加算処理の際、演算処理手続きと途中の演算結果を保存する手段としての加算処理手段１６３を持つ群演算手段１６１によって構成することができる。
【０１２７】
超楕円曲線の因子Ｄに対する２倍算、または、１／２倍算処理、または加算処理を実行する場合、入力データ１０として、適用する超楕円曲線を定義するパラメータ１１、２倍算、１／２倍算、加算のいずれを実行するかを示す群演算種類情報１２、さらに、実際の演算対象となる入力因子１３の各情報が演算手段１００に入力される。これらの入力データに基づいて、演算手段１００において２倍算または１／２倍算、または加算が実行されて処理結果としての出力因子２１を出力データ２０として出力する。
【０１２８】
この構成においても、加算手段１２１、乗算手段１２２、２乗算手段１２３、逆元演算手段１２４は、例えばハードウェア構成、プログラムにおいて２倍算、１／２倍算、加算演算各々に専用の構成とするのではなく、いずれの処理においても共通に利用可能な１つの構成とする。このように、加算手段１２１、乗算手段１２２、２乗算手段１２３、逆元演算手段１２４を２倍算、１／２倍算個別に構成することなく、共有構成とすることにより、演算手段の構成としてのハードウェアサイズ、プログラムサイズを小型化することが可能となる。ハードウェアを用いた場合はゲート数の削減、装置の小型化を実現することができる。
【０１２９】
（２）種数２、標数２の有限体上定義された超楕円曲線の因子Ｄに対するスカラー倍算の演算処理において、
（ａ）加算および２倍算を適用した演算アルゴリズム、
（ｂ）加算および１／２倍算を適用した演算アルゴリズム、
これらの各演算アルゴリズムを用いて、因子のスカラー倍算を計算する方法。
【０１３０】
先に、説明したように、超楕円曲線の因子Ｄに対するスカラー倍算の演算処理は、
（ａ）加算および２倍算を適用した演算アルゴリズム、
（ｂ）加算および１／２倍算を適用した演算アルゴリズム、
この（ａ），（ｂ）のいずれを適用することも可能である。
【０１３１】
（ａ）加算および２倍算を適用した演算アルゴリズムは、先に説明したように、
ｂｉｎａｒｙ（ｒｉｇｈｔ−ｔｏ−ｌｅｆｔ）法
ｂｉｎａｒｙ（ｌｅｆｔ−ｔｏ−ｒｉｇｈｔ）法
が適用可能である。
【０１３２】
ｂｉｎａｒｙ（ｒｉｇｈｔ−ｔｏ−ｌｅｆｔ）法は、ｄを下位ビットから見ていき、ｄｉ＝１の場合に、［２ｉ］Ｄを加算することが特徴である。ｂｉｎａｒｙ（ｒｉｇｈｔ−ｔｏ−ｌｅｆｔ）法のアルゴリズム１（Ａｌｇｏｒｉｔｈｍ１）を以下に示す。
【数１３】
2008020757.tif 000015
【０１３３】
一方、ｂｉｎａｒｙ（ｌｅｆｔ−ｔｏ−ｒｉｇｈｔ）法は、ｄを上位ビットから見ていき、毎ビットＤを２倍し、ｄｉ＝１の場合に、ベースポイントを加算することが特徴である。ｂｉｎａｒｙ（ｌｅｆｔ−ｔｏ−ｒｉｇｈｔ）法のアルゴリズム２（Ａｌｇｏｒｉｔｈｍ２）を以下に示す。
【数１４】
2008020757.tif 000016
【０１３４】
また、（ｂ）加算および１／２倍算を適用した演算アルゴリズムは、先に説明したように、Ｈａｌｖｅ−ａｎｄ−ａｄｄ  ｂｉｎａｒｙ法として、
（ア）ｒｉｇｈｔ−ｔｏ−ｌｅｆｔ法と、
（イ）ｌｅｆｔ−ｔｏ−ｒｉｇｈｔ法、
これらの２種類の手法が域用可能である。スカラー値ｄを因子のオーダーｒを法として１／２進数展開し、それをｄ'とする。
【０１３５】
（ア）Ｈａｌｖｅ−ａｎｄ−ａｄｄ  ｂｉｎａｒｙ（ｒｉｇｈｔ−ｔｏ−ｌｅｆｔ）法は、２進数表現されたスカラー値ｄ'を下位ビットから見ていき、
ｄ'ｉ＝１
の場合に、
［１／２ｉ］Ｄ０
を加算することが特徴である。このｒｉｇｈｔ−ｔｏ−ｌｅｆｔ法のアルゴリズムを以下に、アルゴリズム４（Ａｌｇｏｒｉｔｈｍ４：Ｈａｌｖｅ−ａｎｄ−ａｄｄ  ｂｉｎａｒｙ  （ｒｉｇｈｔ−ｔｏ−ｌｅｆｔ）法）として示す。
【数１５】
2008020757.tif 000017
【０１３６】
上記のアルゴリズム４（Ａｌｇｏｒｉｔｈｍ４）では，スカラー倍ｄＤ０を計算するために、前述のアルゴリズム３（Ａｌｇｏｒｉｔｈｍ３）を用いて、スカラー値ｄを１／２進数展開したｄ'を入力として与えている。
【０１３７】
（イ）Ｈａｌｖｅ−ａｎｄ−ａｄｄ  ｂｉｎａｒｙ（ｌｅｆｔ−ｔｏ−ｒｉｇｈｔ）法は、２進数表現されたスカラー値ｄ'を上位ビットから見ていき、毎ビットＤを１／２倍して、
ｄ'ｉ＝１
の場合に、ベースポイントを加算することが特徴である。このｌｅｆｔ−ｔｏ−ｒｉｇｈｔ法のアルゴリズムの詳細を以下に、アルゴリズム５（Ａｌｇｏｒｉｔｈｍ５：Ｈａｌｖｅ−ａｎｄ−ａｄｄ  ｂｉｎａｒｙ  （ｌｅｆｔ−ｔｏ−ｒｉｇｈｔ）法）として示す。
【数１６】
2008020757.tif 000018
【０１３８】
上記アルゴリズム５（Ａｌｇｏｒｉｔｈｍ５）では、スカラー倍ｄＤ０を計算するために、前述のアルゴリズム３（Ａｌｇｏｒｉｔｈｍ３）を用いて、スカラー値ｄを１／２進数展開したｄ'を入力として与えている。
【０１３９】
ここで、上記したアルゴリズム中、
２倍算を適用した場合のスカラー倍算アルゴリズム：アルゴリズム１（Ａｌｇｏｒｉｔｈｍ１）と、
１／２倍算を適用した場合のスカラー倍算アルゴリズム：アルゴリズム４（Ａｌｇｏｒｉｔｈｍ４）
を比較する。
【０１４０】
アルゴリズム１（Ａｌｇｏｒｉｔｈｍ１）における２倍算の適用部分が、アルゴリズム４（Ａｌｇｏｒｉｔｈｍ４）においては、１／２倍算に置き換わっているのみであり、他の部分に関してはまったく共通している。
【０１４１】
さらに、同様に、上記したアルゴリズム中、
２倍算を適用した場合のスカラー倍算アルゴリズム：アルゴリズム２（Ａｌｇｏｒｉｔｈｍ２）と、
１／２倍算を適用した場合のスカラー倍算アルゴリズム：アルゴリズム５（Ａｌｇｏｒｉｔｈｍ５）
を比較する。
【０１４２】
この２つのアルゴリズムを比較した場合も、上記の比較と同様であり、アルゴリズム２（Ａｌｇｏｒｉｔｈｍ２）における２倍算の適用部分が、アルゴリズム５（Ａｌｇｏｒｉｔｈｍ５）において、１／２倍算に置き換わっているのみであり、他の部分に関してはまったく共通している。
【０１４３】
このことから、アルゴリズム１（Ａｌｇｏｒｉｔｈｍ１）と、アルゴリズム４（Ａｌｇｏｒｉｔｈｍ４）を１つの共通アルゴリズムとして設定し、実行する処理が、
（ａ）加算および２倍算を適用した演算アルゴリズム、
（ｂ）加算および１／２倍算を適用した演算アルゴリズム、
上記（ａ），（ｂ）のいずれかによって、一部の処理のみを変更する設定とすることで、
（ａ）加算および２倍算を適用した演算アルゴリズム、
（ｂ）加算および１／２倍算を適用した演算アルゴリズム、
の双方を実行する構成が実現される。
【０１４４】
同様に、アルゴリズム２（Ａｌｇｏｒｉｔｈｍ２）と、アルゴリズム５（Ａｌｇｏｒｉｔｈｍ５）を１つの共通アルゴリズムとして設定し、実行する処理が、
（ａ）加算および２倍算を適用した演算アルゴリズム、
（ｂ）加算および１／２倍算を適用した演算アルゴリズム、
上記（ａ），（ｂ）のいずれかによって、一部の処理のみを変更する設定とすることで、
（ａ）加算および２倍算を適用した演算アルゴリズム、
（ｂ）加算および１／２倍算を適用した演算アルゴリズム、
の双方を実行する構成が実現される。
【０１４５】
これらのことから、超楕円曲線の因子Ｄに対するスカラー倍算の演算処理として、
（ａ）加算および２倍算を適用した演算アルゴリズム、
（ｂ）加算および１／２倍算を適用した演算アルゴリズム、
これらのいずれのアルゴリズムでも実行可能としたスカラー倍算手段は、例えば図５に示す２倍算・１／２倍算切換スカラー倍算手段２５０として構成することができる。
【０１４６】
図５に示す２倍算・１／２倍算切換スカラー倍算手段２５０は、図４を参照して説明した演算手段１５０、すなわち、超楕円曲線の因子Ｄに対する２倍算、１／２倍算、加算処理を実行する演算手段１５０に加え、１／２倍算を適用した場合のスカラー倍算アルゴリズムの実行において必要となるスカラー値変換処理を実行するスカラー値変換手段２５１と、スカラー倍算アルゴリズムを実行するスカラー倍算処理手段２５２とを有する。
【０１４７】
スカラー倍算処理手段２５２は、例えば、
（Ｐ）アルゴリズム１（Ａｌｇｏｒｉｔｈｍ１）と、アルゴリズム４（Ａｌｇｏｒｉｔｈｍ４）を１つの共通アルゴリズムとして設定し、実行する処理が、
（ａ）加算および２倍算を適用した演算アルゴリズム、
（ｂ）加算および１／２倍算を適用した演算アルゴリズム、
上記（ａ），（ｂ）のいずれかによって、一部の処理のみを変更する設定としたアルゴリズムの実行構成、または、
（Ｑ）アルゴリズム２（Ａｌｇｏｒｉｔｈｍ２）と、アルゴリズム５（Ａｌｇｏｒｉｔｈｍ５）を１つの共通アルゴリズムとして設定し、実行する処理が、
（ａ）加算および２倍算を適用した演算アルゴリズム、
（ｂ）加算および１／２倍算を適用した演算アルゴリズム、
上記（ａ），（ｂ）のいずれかによって、一部の処理のみを変更する設定としたアルゴリズムの実行構成、
上記（Ｐ），（Ｑ）の少なくともいずれかの処理を実行可能な構成とする。
【０１４８】
スカラー値変換手段２５１は、１／２倍算を適用した場合のスカラー倍算アルゴリズムの実行において必要となるスカラー値変換処理を実行する構成であり、先に説明したように、スカラー値ｄを因子のオーダーｒを法として１／２進数展開し、それをｄ'とする。具体的には、ｄ'を以下のように表現する処理を行なう。
【数１７】
2008020757.tif 000019
【０１４９】
上記式において、ｍはオーダーｒのビット長である。このスカラー値変換処理は、先に説明したアルゴリズム３（Ａｌｇｏｌｉｔｈｍ３）であり、以下のアルゴリズムである。
【数１８】
2008020757.tif 000020
【０１５０】
図５に示す２倍算・１／２倍算切換スカラー倍算手段２５０を適用して、超楕円曲線の因子Ｄに対するスカラー倍算を実行する場合、入力データ２１０として、適用する超楕円曲線を定義する曲線パラメータ２１１、２倍算、１／２倍算のいずれを実行するかを示す群演算種類情報２１２、さらに、実際の演算対象となる入力因子２１３とスカラー値２１４の各情報が２倍算・１／２倍算切換スカラー倍算手段２５０に入力される。これらの入力データに基づいて、２倍算・１／２倍算切換スカラー倍算手段２５０において、
（ａ）加算および２倍算を適用した演算アルゴリズム、
（ｂ）加算および１／２倍算を適用した演算アルゴリズム、
これらのいずれかのスカラー倍算が実行されて処理結果としてのスカラー倍算結果２２１を出力データ２２０として出力する。
【０１５１】
この構成において、演算手段１５０は、図４を参照して説明した構成を有し、有限体演算手段１２０には、加算手段１２１、乗算手段１２２、２乗算手段１２３、逆元演算手段１２４、平方根演算手段１２５、ハーフトレース演算手段１２６、トレース演算手段１２７を有するが、加算手段１２１、乗算手段１２２、２乗算手段１２３、逆元演算手段１２４は、ハードウェア構成、プログラムにおいて２倍算、１／２倍算、加算演算各々に専用の構成とするのではなく、いずれの処理においても共通に利用可能な１つの構成とする。共通構成とすることで、演算手段の構成としてのハードウェアサイズ、プログラムサイズを小型化することが可能となる。ハードウェアを用いた場合はゲート数の削減、装置の小型化を実現することができる。
【０１５２】
なお、上述のスカラー倍算では、ｂｉｎａｒｙ法を適用した処理構成について説明したが、ｂｉｎａｒｙ法と異なる手法に基づくスカラー倍算処理、例えばｗｉｎｄｏｗ法を適用したスカラー倍算処理においても、図５に示す構成において、スカラー値変換手段２５１およびスカラー倍算処理手段２５２をｗｉｎｄｏｗ法のアルゴリズムに対応した構成とすることで、演算手段１５０を適用した処理が可能である。
【０１５３】
（３）種数２、標数２の有限体上定義された超楕円曲線の因子Ｄに対するスカラー倍算の演算処理において、
（ａ）加算および２倍算を適用した演算アルゴリズム、
（ｂ）加算および１／２倍算を適用した演算アルゴリズム、
これらのどちらの処理が高速かを判断する方法。
【０１５４】
超楕円曲線の因子Ｄに対するスカラー倍算の演算処理において、
（ａ）加算および２倍算を適用した演算アルゴリズム、
（ｂ）加算および１／２倍算を適用した演算アルゴリズム、
このいずれの処理も適用可能であるが、
上記（ａ），（ｂ）のいずれが高速演算可能であるかは、超楕円曲線暗号において適用する曲線パラメータや有限体に依存する。
【０１５５】
図５の構成を持つ２倍算・１／２倍算切換スカラー倍算手段２５０中の演算手段１５０内に構成される図４に示す有限体演算手段１２０は、加算手段１２１、乗算手段１２２、２乗算手段１２３、逆元演算手段１２４、平方根演算手段１２５、ハーフトレース演算手段１２６、トレース演算手段１２７を有し、
（ａ）加算および２倍算を適用した演算アルゴリズム、
（ｂ）加算および１／２倍算を適用した演算アルゴリズム、
これらのアルゴリズムにおいて、有限体演算手段１２０の各手段が有限体の演算を実行することになる。
【０１５６】
以下、
（ａ）加算および２倍算を適用した演算アルゴリズム、
（ｂ）加算および１／２倍算を適用した演算アルゴリズム、
これらのアルゴリズムにおける演算量を算出する。
【０１５７】
有限体の各演算の計算量を以下のように定義する。
乗算の計算量をＭ、
２乗算の計算量をＳ、
逆元演算の計算量をＩ、
平方根演算の計算量をＳＲ、
ハーフトレース演算の計算量をＨ、
で表す。なお、有限体の加算はビット毎の排他的論理輪を計算するだけであるため、非常に計算量が小さい。また、有限体のトレース演算は、ごく少数のビット値を調べることにより計算できる。よって、有限体の加算およびとレース演算の計算量を無視しても問題ないので、以下では、加算、トレース演算の計算量は考慮しない。
【０１５８】
前述した通り、超楕円曲線では曲線を特徴づける値は種数（ｇｅｎｕｓ）ｇである。ｐを素数、ｎを正の整数、ｑ＝ｐｎとする。このとき有限体Ｆｑ上で定義される種数ｇの超楕円曲線Ｃは以下の方程式、
ｙ２＋ｈ（ｘ）ｙ＝ｆ（ｘ）
で定義される。ここで、ｈ（ｘ），ｆ（ｘ）∈Ｆｑ［ｘ］，ｆ（ｘ）は、次数２ｇ＋１のｍｏｎｉｃ多項式である。
【０１５９】
スカラー倍算を実行する際に与えられる超楕円曲線パラメータや有限体のタイプによって、２倍算と１／２倍算の演算量は異なる。本発明の一実施例構成において考慮する超楕円曲線パラメータや有限体のタイプは、以下の情報である。
＊有限体のタイプ：正規基底もしくは多項式基底
＊既約多項式：有限体のタイプが多項式基底の場合に必要
＊有限体の拡大次数：ｎ（Ｆｑ、ｑ＝２ｎ）
＊曲線の係数：ｈ２、ｈ１、ｈ０、ｆ４、ｆ３、ｆ２、ｆ１、ｆ０、
（ｙ２＋（ｈ２ｘ２＋ｈ１ｘ＋ｈ０）ｙ＝ｘ５＋ｆ４ｘ４＋ｆ３ｘ３＋ｆ２ｘ２＋ｆ１ｘ＋ｆ０）
＊ｈ（ｘ）が既約か可約か：
＊ベースポイントＤ０：ｕ２、ｕ１、ｕ０、ｖ１、ｖ０．（Ｄ０＝（ｕ２ｘ２＋ｕ１ｘ＋ｕ０、ｖ１ｘ＋ｖ０））
＊ベースポイントの位数ｒ：１６０ビット以上の大きな素数
＊コファクターｃ：Ｎ＝ｃ＊ｒを満たす数（Ｎは被約因子の個数）
【０１６０】
上記情報に基づいて、
（ａ）加算および２倍算を適用した演算アルゴリズム、
（ｂ）加算および１／２倍算を適用した演算アルゴリズム、
のいずれが高速演算可能かを判定する。上記情報のすべてを考慮する構成としてもよいし、一部の情報のみに基づいて判定する構成としてもよい。
【０１６１】
以下では、超楕円曲線パラメータを、
（Ｐ１）ｈ２＝１、ｆ４＝０（一般的な曲線）の場合、
（Ｐ２）ｈ２＝ｈ１＝１、ｆ４＝０の場合、
（Ｐ３）ｈ２＝ｈ１＝ｈ１＝１、ｆ４＝０の場合、
これらの３種類のパラメータによって定義される超楕円曲線における２倍算と１／２倍算の有限体演算の演算量を算出して比較する。
なお、ｈ（ｘ）は既約多項式であるとする。ｈ（ｘ）が既約多項式でない場合は、１／２倍算の演算は２倍算よりも低速となるため、ｈ（ｘ）が既約多項式の場合の２倍算と１／２倍算の演算量の比較は省略する。
【０１６２】
（Ｐ１）ｈ２＝１、ｆ４＝０（一般的な曲線）の場合、
２倍算：２１Ｍ＋５Ｓ＋１Ｉ
１／２倍算：１９．５Ｍ＋２Ｓ＋１Ｉ＋２．５ＳＲ＋２Ｈ
（Ｐ２）ｈ２＝ｈ１＝１、ｆ４＝０の場合、
２倍算：１８Ｍ＋７Ｓ＋１Ｉ
１／２倍算：１４．５Ｍ＋３Ｓ＋１Ｉ＋２．５ＳＲ＋２Ｈ
（Ｐ３）ｈ２＝ｈ１＝ｈ１＝１、ｆ４＝０の場合、
２倍算：１５Ｍ＋７Ｓ＋１Ｉ
１／２倍算：１３．５Ｍ＋３Ｓ＋１Ｉ＋２．５ＳＲ＋２Ｈ
【０１６３】
上記のように、適用する超楕円曲線に応じて、２倍算と１／２倍算の演算量が算出される。
【０１６４】
さらに、スカラー倍算における
（ａ）加算および２倍算を適用した演算アルゴリズム、
（ｂ）加算および１／２倍算を適用した演算アルゴリズム、
これらのアルゴリズムにおける演算量を比較する場合、
有限体演算に適用する有限体が正規規定であるか多項式規定であるかによって演算量が異なるので、これらを区別することが必要となる。
【０１６５】
［有限体が正規規定の場合］
まず、有限体が正規基底の場合には、
２乗算の計算量：Ｓ、
平方根演算の計算量：ＳＲ、
ハーフトレース演算の計算量：Ｈ、
を無視することができる。正規基底の乗算の計算量をＭＮと表す。
また、
【数１９】
2008020757.tif 000021
【０１６６】
上記のように表現されることが知られている。例えば、［A.Menezes. Elliptic Curve Public Key Cryptosystems. Kluwer Academic Publishers, 1993］参照のこと。
なお、ｎは有限体の拡大次数である。＃（ｎ−１）は、ｎ−１を２進数表記した場合の１の個数である。例えばＩ＝８ＭＮと仮定すると、２倍算と１／２倍算の計算量は次のようになる。
【０１６７】
（Ｐ１）ｈ２＝１、ｆ４＝０（一般的な曲線）の場合、
２倍算：２９ＭＮ
１／２倍算：２７．５ＭＮ
（Ｐ２）ｈ２＝ｈ１＝１、ｆ４＝０の場合、
２倍算：２６ＭＮ
１／２倍算：２２．５ＭＮ
（Ｐ３）ｈ２＝ｈ１＝ｈ１＝１、ｆ４＝０の場合、
２倍算：２３ＭＮ
１／２倍算：２１．５ＭＮ
【０１６８】
［有限体が多項式基底の場合］
有限体が多項式基底の場合は、
２乗算の計算量：Ｓ、
平方根演算の計算量：ＳＲ、
ハーフトレース演算の計算量：Ｈ、
を無視することができない。多項式基底の乗算の計算量をＭＰと表す。有限体を定義する既約多項式にもよるが、一般的に、
１ＳＲ＝０．５ＭＰ、
１Ｈ＝０．５ＭＰ
であることが知られている。
【０１６９】
既約多項式や実装方法によっては、これらの計算量が０．５ＭＰよりも大きかったり、小さかったりする。また、２乗算の計算量：ＳはＭＰの数分の１程度であることが知られている。例えば１Ｓ＝０．１ＭＰ、１ＳＲ＝０．５ＭＰ、１Ｈ＝０．５ＭＰ、１Ｉ＝８ＭＰと仮定すると、２倍算と１／２倍算の計算量は次のようになる。
（Ｐ１）ｈ２＝１、ｆ４＝０（一般的な曲線）の場合、
２倍算：２９．５ＭＰ
１／２倍算：２９．９５ＭＰ
（Ｐ２）ｈ２＝ｈ１＝１、ｆ４＝０の場合、
２倍算：２６．７ＭＰ
１／２倍算：２５．０５ＭＰ
（Ｐ３）ｈ２＝ｈ１＝ｈ１＝１、ｆ４＝０の場合、
２倍算：２３．７ＭＰ
１／２倍算：２４．０５ＭＰ
【０１７０】
このように、曲線パラメータと有限体により、２倍算と１／２倍算の計算量が異なる。
【０１７１】
具体的な、超楕円曲線暗号処理におけるスカラー倍算を実行する処理形態としては、例えば、超楕円曲線暗号を用いた署名生成、署名検証、ＤＨ型鍵交換などの処理が想定される。また、このような暗号処理演算を実行する情報処理装置やシステムとしては、例えば、様々なサービスを提供するサーバや、ＰＣ、デジタル家電、携帯電話などの情報端末、ＩＣカードなど、様々な機器が想定される。
【０１７２】
例えば、ユーザの持つ携帯端末などの情報処理装置が、ネットバンキング、音楽配信などといった様々なサービスを受領しようとする場合、異なるサービス提供主体との間で暗号処理を伴うデータ処理や通信を実行することになる。この場合、それぞれのサービス提供主体が個別に設定したアルゴリズムに従った処理を行なうことが必要であり、ユーザの持つ携帯端末などの情報処理装置では、異なる超楕円曲線パラメータや有限体をベースとした暗号処理を実行しなければならないことになる。
【０１７３】
上述したように、スカラー倍算における
（ａ）加算および２倍算を適用した演算アルゴリズム、
（ｂ）加算および１／２倍算を適用した演算アルゴリズム、
のいずれが高速に実行可能かは、超楕円曲線パラメータや有限体に依存することになる。従って、例えば、ユーザの持つ携帯端末などの情報処理装置において、上記（ａ）（ｂ）のいずれか一方のみのアルゴリズムしか実行できない構成である場合は、ある条件設定では、遅い演算処理速度での処理を余儀なくされることになる。
【０１７４】
従って、ユーザの持つ携帯端末などの情報処理装置を、上記（ａ）（ｂ）の両アルゴリズムを実行可能な構成として、サービス提供主体が設定した異なる超楕円曲線パラメータや有限体の情報に基づいて、上記（ａ）（ｂ）のいずれが、高速演算可能なアルゴリズムであるかを判定して、高速処理が可能なアルゴリズムに従って演算を行なうとすれば、超楕円曲線パラメータや有限体の様々な条件に応じて、常に高速処理を行なうことが可能となる。
【０１７５】
以下では、異なる超楕円曲線パラメータや有限体に基づいて、高速演算が可能なアルゴリズムを選択して実行するための構成について説明する。
【０１７６】
本発明の一実施例構成としての暗号処理装置では、初期設定として、超楕円曲線暗号処理に際して使用する様々な曲線毎に２倍算と１／２倍算の処理速度を、予め測定し、各曲線に応じて２倍算と１／２倍算のうち、どちらが高速演算可能であるかを判定して、各曲線対応の高速演算可能なアルゴリズム情報を記録したテーブルを生成して、記憶手段に保持しておく。このテーブルを「２倍算・１／２倍算切換テーブル」と呼ぶことにする。また、この初期設定を、「２倍算・１／２倍算切換テーブル初期設定」と呼ぶ。
【０１７７】
本発明の一実施例構成としての暗号処理装置は、図５に示すような２倍算・１／２倍算切換スカラー倍算手段２５０、すなわち、
（ａ）加算および２倍算を適用した演算アルゴリズム、
（ｂ）加算および１／２倍算を適用した演算アルゴリズム、
これら（ａ），（ｂ）の演算アルゴリズムのいずれも実行可能な２倍算・１／２倍算切換スカラー倍算手段２５０を有するとともに、上述の「２倍算・１／２倍算切換テーブル」を記憶手段に保持し、暗号処理演算の開始前に、２倍算・１／２倍算切換テーブルを参照して、演算に適用する超楕円曲線パラメータや有限体情報に基づいて、高速演算が可能なアルゴリズムが、
（ａ）加算および２倍算を適用した演算アルゴリズム、
（ｂ）加算および１／２倍算を適用した演算アルゴリズム、
これらのいずれであるかを判断し、高速に実行可能と判断されたアルゴリズムを選択して実行する。
【０１７８】
まず、暗号処理装置において実行される２倍算・１／２倍算切換テーブル初期設定に関して説明する。
具体例として、Ｍ個の超楕円曲線に対して、２倍算・１／２倍算切換テーブルを作成する場合を考える。
すなわち、入力としてＭ個の曲線パラメータが与えられ、出力として、各曲線に対して、２倍算もしくは１／２倍算のどちらを使うかを記載したテーブルを得る。
【０１７９】
１／２倍算は、コファクター［ｃ］が２で、ｈ（ｘ）が既約多項式の場合に高速に計算が可能である。前述したように、コファクター［ｃ］は、
Ｎ＝ｃ＊ｒを満たす数
によって定義される。
ただし、
Ｎは被約因子の個数、
ｒはベースポイントの位数（１６０ビット以上の大きな素数）
である。
【０１８０】
このように、１／２倍算は、コファクター［ｃ］が２で、ｈ（ｘ）が既約多項式の場合に高速に計算が可能であるため、検証対象となるＭ個の超楕円曲線の曲線パラメータを参照し、コファクターとｈ（ｘ）が上記条件を満たさない場合は、テーブルに２倍算を使用すると記載する。
【０１８１】
一方、コファクター［ｃ］とｈ（ｘ）が上記条件を満たしている場合、すなわち、
コファクター［ｃ］が２で、ｈ（ｘ）が既約多項式である。
この条件を満たしている場合にのみ、２倍算と１／２倍算の計算速度を算出し、テーブルに、算出結果として得られる、いずれか一方の高速なアルゴリズムを記載する。
この処理を、Ｍ個の曲線に対して行い、２倍算・１／２倍算切換テーブルを出力する。
【０１８２】
２倍算・１／２倍算切換テーブル初期設定処理のシーケンスについて、図６に示すフローチャートを参照して説明する。まず、ステップＳ１０１において、演算速度の検証対象とするＭ個の超楕円曲線のパラメータを入力する。これらのパラメータは、上述したように、
＊有限体のタイプ：正規基底もしくは多項式基底
＊既約多項式：有限体のタイプが多項式基底の場合に必要
＊有限体の拡大次数：ｎ（Ｆｑ、ｑ＝２ｎ）
＊曲線の係数：ｈ２、ｈ１、ｈ０、ｆ４、ｆ３、ｆ２、ｆ１、ｆ０、
（ｙ２＋（ｈ２ｘ２＋ｈ１ｘ＋ｈ０）ｙ＝ｘ５＋ｆ４ｘ４＋ｆ３ｘ３＋ｆ２ｘ２＋ｆ１ｘ＋ｆ０）
＊ｈ（ｘ）が既約か可約か：
＊ベースポイントＤ０：ｕ２、ｕ１、ｕ０、ｖ１、ｖ０．（Ｄ０＝（ｕ２ｘ２＋ｕ１ｘ＋ｕ０、ｖ１ｘ＋ｖ０））
＊ベースポイントの位数ｒ：１６０ビット以上の大きな素数
＊コファクターｃ：Ｎ＝ｃ＊ｒを満たす数（Ｎは被約因子の個数）
これらのデータである。
【０１８３】
次に、ステップＳ１０２において、Ｍ個の超楕円曲線各々の識別子に対応する変数（ｉ）の初期設定としてｉ＝１とし、ステップＳ１０３において、ｉ≦Ｍを判定し、ステップＳ１０４において、ｉ番目の超楕円曲線のパラメータを選択する。
【０１８４】
次に、ステップＳ１０５において、検証対象として選択したｉ番目の超楕円曲線のパラメータを検証し、コファクター［ｃ］が２で、かつ、ｈ（ｘ）が既約多項式であるか否かを検証する。前述したように、１／２倍算が高速に計算可能となる可能性があるのは、コファクター［ｃ］が２で、かつ、ｈ（ｘ）が既約多項式である場合に限られる。
【０１８５】
ステップＳ１０５において、検証対象として選択したｉ番目の超楕円曲線のパラメータが、
コファクター［ｃ］が２で、かつ、ｈ（ｘ）が既約多項式である
という条件を満足していない場合は、１／２倍算の計算が高速になる可能性がないと判断し、２倍算を適用することになる。この場合は、ステップＳ１０９に進み、検証対象としたｉ番目の超楕円曲線に適用すべき高速演算アルゴリズムとして［２倍算］をテーブルに記録する。
【０１８６】
一方、ステップＳ１０５において、検証対象として選択したｉ番目の超楕円曲線のパラメータが、
コファクター［ｃ］が２で、かつ、ｈ（ｘ）が既約多項式である
という条件を満足している場合は、１／２倍算の計算が高速になる可能性があり、ステップＳ１０６に進み、検証対象としているｉ番目の超楕円曲線パラメータの条件設定に基づいて２倍算および１／２倍算の演算速度の検証処理を実行する。
【０１８７】
２倍算および１／２倍算の演算速度の検証処理は、実際に計算を実行してその処理時間を計測してもよいし、あるいは、必要となる計算回数を算出して、実際に計算を実行した場合の処理時間を算出する構成としてもよい。このステップＳ１０６における２倍算および１／２倍算の演算速度の検証処理を実行するための構成例について、図７、図８を参照して説明する。
【０１８８】
図７は、２倍算および１／２倍算の演算速度の検証処理を実行する１つの構成例として２倍算・１／２倍算速度算出手段３２０を示している。２倍算・１／２倍算速度算出手段３２０は、検証対象とする超楕円曲線に対応する曲線パラメータ３１０を入力して、曲線パラメータ３１０に基づいて、２倍算および１／２倍算の演算速度の検証を実行し、２倍算および１／２倍算演算時間情報３１５を出力する。
【０１８９】
２倍算・１／２倍算速度算出手段３２０は、有限体演算部３２１、有限体演算時間測定部３２２、２倍算・１／２倍算演算時間算出部３２３、２倍算・１／２倍算有限体演算計算回数算出部３２４を有する。
【０１９０】
有限体演算部３２１では、２倍算・１／２倍算各々について、曲線パラメータ３１０に応じた有限体演算を実行し、有限体演算時間測定部３２２は、２倍算・１／２倍算各々についての有限体演算部３２１での有限体演算時間を測定する。
【０１９１】
次に２倍算・１／２倍算有限体演算計算回数算出部３２４は、２倍算および１／２倍算で必要な各有限体演算の計算回数を算出し、２倍算・１／２倍算演算時間算出部３２３は、
有限体演算時間測定部３２２の測定した２倍算・１／２倍算各々についての有限体演算部３２１での有限体演算時間情報と、
２倍算・１／２倍算有限体演算計算回数算出部３２４から受領する２倍算および１／２倍算で必要な各有限体演算の計算回数との情報、
これらの情報に基づいて、２倍算と１／２倍算の計算時間を算出して、この算出した２倍算および１／２倍算の計算速度を２倍算および１／２倍算の演算速度情報３１５として出力する。
【０１９２】
図８には、図７に示す構成とは異なる構成を持つ２倍算・１／２倍算速度算出手段３４０を示している。２倍算・１／２倍算速度算出手段３４０は、検証対象とする超楕円曲線に対応する曲線パラメータ３３０を入力して、曲線パラメータ３３０に基づいて、２倍算および１／２倍算の演算速度の検証を実行し、２倍算および１／２倍算の演算速度情報３５０を出力する。
【０１９３】
図８に示す２倍算・１／２倍算速度算出手段３４０は、２倍算・１／２倍算演算手段３４１と、２倍算・１／２倍算演算時間算出部３４２を有する。この図８に示す構成は、検証対象とする超楕円曲線に対応する曲線パラメータ３３０を入力して、曲線パラメータ３３０に記載のベースポイントを適用して、２倍算・１／２倍算演算３４１において、２倍算・１／２倍算を実行して、その実行時間を２倍算・１／２倍算演算時間算出部３４２において算出し、２倍算および１／２倍算の演算速度情報３５０を出力する。
【０１９４】
２倍算・１／２倍算演算手段３４１としては、例えば、先に図３、図４を参照して説明した構成が適用可能である。すなわち、２倍算、１／２倍算の計算を実行可能な暗号処理装置に時間計測機能を付加するのみで２倍算・１／２倍算速度算出手段は構成することが可能である。
【０１９５】
図６に示すフローに戻り、２倍算・１／２倍算切換テーブル初期設定処理のシーケンスについての説明を続ける。ステップＳ１０６において、検証対象としているｉ番目の超楕円曲線パラメータの条件設定に基づいて２倍算および１／２倍算の演算速度の検証処理が、上述したように、例えば、図７、図８に示す構成を持つ２倍算・１／２倍算速度算出手段を適用して実行される。
【０１９６】
ステップＳ１０７では、この検証結果を判定する。１／２倍算が２倍算より高速であると判定された場合は、ステップＳ１０８に進み、ｉ番目の曲線に対応する高速演算アルゴリズムとして１／２倍算をテーブルに記録する。一方、ステップＳ１０７において、２倍算が１／２倍算より高速であると判定された場合は、ステップＳ１０９に進み、ｉ番目の曲線に対応する高速演算アルゴリズムとして２倍算をテーブルに記録する。
【０１９７】
次に、ステップＳ１１０に進み、Ｍ個の超楕円曲線各々の識別子に対応する変数（ｉ）の更新処理としてｉ＝ｉ＋１とし、ステップＳ１０３以下の処理を繰り返し実行する。入力したＭ個の超楕円曲線に対応する曲線パラメータに対するすべての検証が終了すると、ステップＳ１０３のｉ≦Ｍ判定処理においてＮｏと判定され、ステップＳ１２１に進み、Ｍ個の超楕円曲線各々について、２倍算と１／２倍算のいずれが、高速演算可能であるかを記録した２倍算・１／２倍算切換テーブルを記憶部に格納して処理を終了する。
【０１９８】
次に、上述した処理によって生成される２倍算・１／２倍算切換テーブルの具体例について、図９以下を参照して説明する。図９は２倍算・１／２倍算切換テーブルに記録されるデータについて説明する図である。２倍算・１／２倍算切換テーブルには、検証の実行されたＭ個の超楕円曲線のパラメータと、２倍算と１／２倍算のどちらが高速に実行可能かについての高速演算アルゴリズム情報が記録される。
【０１９９】
超楕円曲線パラメータは、先に説明したように、有限体のタイプを含み、以下のデータによって構成される。
＊有限体のタイプ：正規基底もしくは多項式基底
＊既約多項式：有限体のタイプが多項式基底の場合に必要
＊有限体の拡大次数：ｎ（Ｆｑ、ｑ＝２ｎ）
＊曲線の係数：ｈ２、ｈ１、ｈ０、ｆ４、ｆ３、ｆ２、ｆ１、ｆ０、
（ｙ２＋（ｈ２ｘ２＋ｈ１ｘ＋ｈ０）ｙ＝ｘ５＋ｆ４ｘ４＋ｆ３ｘ３＋ｆ２ｘ２＋ｆ１ｘ＋ｆ０）
＊ｈ（ｘ）が既約か可約か：
＊ベースポイントＤ０：ｕ２、ｕ１、ｕ０、ｖ１、ｖ０．（Ｄ０＝（ｕ２ｘ２＋ｕ１ｘ＋ｕ０、ｖ１ｘ＋ｖ０））
＊ベースポイントの位数ｒ：１６０ビット以上の大きな素数
＊コファクターｃ：Ｎ＝ｃ＊ｒを満たす数（Ｎは被約因子の個数）
これらのデータである。
【０２００】
これらのパラメータ情報と、２倍算と１／２倍算のどちらが高速に実行可能かについての高速演算アルゴリズム情報が記録される。高速演算アルゴリズム情報は、例えば２倍算が高速である場合は［０］、１／２倍算が高速である場合は［１］が記録される。
【０２０１】
具体的な、２倍算・１／２倍算切換テーブルの記録データ例を、図１０〜図１３に示す。図１０〜図１３には、４つの異なる超楕円曲線（Ｃ１，Ｃ２，Ｃ３，Ｃ４）の記録データ例を示している。
【０２０２】
図１０に示すデータは、示す２倍算・１／２倍算切換テーブルにおける超楕円曲線（Ｃ１）の記録データを示している。この記録データは、以下の構成を持つ。
長楕円曲線識別子：Ｃ１
有限体のタイプ：多項式基底
既約多項式：z83 + z7 + z4 + z2 + 1
有限体の拡大次数：83
曲線の係数：1, 1, 26c76058679188f41f7bc, 0, 3510a16ab31776237482d, 
2905946b804eae26b529d, 12e53b7f0fb5f060de6f0, 15000c12e0c816fa3c90d,
h(x)が既約か可約か：既約
ベースポイント：1, c436c8f77259e78f912c2, d655910a524f04ae82ef3,
7c8cb3c0127db4a1e3d26, 82251eb5ca6a6bee606f7
ベースポイントの位数：
46768052394603572927593652383474201578491908925599
コファクター：2
高速演算アルゴリズム情報：［１］＝１／２倍算が高速
【０２０３】
図１１に示すデータは、示す２倍算・１／２倍算切換テーブルにおける超楕円曲線（Ｃ２）の記録データを示している。この記録データは、以下の構成を持つ。
長楕円曲線識別子：Ｃ２
有限体のタイプ：多項式基底
既約多項式：z83 + z7 + z4 + z2 + 1
有限体の拡大次数：83
曲線の係数：1, 1, 1, 0, 6aeccc919ba7b17905576, 674ad22c4ae3a624f2662, 
64ed5727767c5bd20a4d2, 12d5d21396915b5770a14,
h(x)が既約か可約か：既約
ベースポイント：1, 3c6d393b089ae5d7f4d12 ,8189d7211e26eeb0a9c7 
1, 75d9b6e682bf78baa3247, 1b11732b994c91069e295，
ベースポイントの位数：
46768052394606306447078621357434240674807384948657
コファクター：2
高速演算アルゴリズム情報：［０］＝２倍算が高速
【０２０４】
図１２に示すデータは、示す２倍算・１／２倍算切換テーブルにおける超楕円曲線（Ｃ３）の記録データを示している。この記録データは、以下の構成を持つ。
長楕円曲線識別子：Ｃ３
有限体のタイプ：多項式基底
既約多項式：z89 + z38 + 1
有限体の拡大次数：89
曲線の係数：1, 1, 10b4e25d9f772a17f079633, 0, 1cdcfccf952029e11a6d591,
57a45459240e1b_1e9c51, 1233884427d30a923afef30, 5232b0a2cc9c4205f0a77e,
h(x)が既約か可約か：既約
ベースポイント：1, 09b36fa3848e7e249fe8ed1, cc1478b173c15367a40ea81,
22c828ba94cd197b36de68, 2d8490ae18ed1ee4f3b5531
ベースポイントの位数：
191561942608247727889817815217170268849704825025870087
コファクター：2
高速演算アルゴリズム情報：［１］＝１／２倍算が高速
【０２０５】
図１３に示すデータは、示す２倍算・１／２倍算切換テーブルにおける超楕円曲線（Ｃ４）の記録データを示している。この記録データは、以下の構成を持つ。
長楕円曲線識別子：Ｃ４
有限体のタイプ：多項式基底
既約多項式：z89 + z38 + 1
有限体の拡大次数：89
曲線の係数：1, 1, 1, 0, 12c8551e2a5509652647b44, 10eed3aaec17720e2588277,
1e27989afc4eb5c4288db79, 16cc764d307ce3295795cbd,
h(x)が既約か可約か：既約
ベースポイント：0ec349e8d803268974d6e3, 92c7e15707841b0ea57e891,
46216855c55fd3186727e7, 5fd2e671dcad8609c3ad6b
ベースポイントの位数：
191561942608238453928841542765255795300282270809283583
コファクター：2
高速演算アルゴリズム情報：［０］＝２倍算が高速
【０２０６】
暗号処理を実行する暗号処理装置は、このようなデータが記録された２倍算・１／２倍算切換テーブルを記憶部に格納し、実際に暗号処理演算を実行する際に適用する超楕円曲線のパラメータと、テーブルに登録されたパラメータとを照合して、一致するパラメータが登録されたエントリに対応付けられた高速演算アルゴリズム情報を参照して、２倍算が高速に演算可能か１／２倍算が高速に演算可能であるかを判別し、テーブルに登録された一方のアルゴリズムを選択して、
（ａ）加算および２倍算を適用した演算アルゴリズム、
（ｂ）加算および１／２倍算を適用した演算アルゴリズム、
上記（ａ），（ｂ）のいずれかを実行する。この処理によって、超楕円曲線のパラメータに応じた最適な、すなわち最速の処理による演算が可能となる。
【０２０７】
このような処理は、サーバやＰＣの他、様々なデジタル家電やＩＣカードにおいて実行可能である。異なる曲線を適用した暗号処理演算が要請される機器において、上述したテーブルを保持することで、実際に暗号処理演算を実行する際に適用する超楕円曲線のパラメータと、テーブルに登録されたパラメータとを照合して、一致するパラメータが登録されたエントリに対応付けられた高速演算アルゴリズム情報を参照して、２倍算が高速に演算可能か１／２倍算が高速に演算可能であるかを判別し、テーブルに登録された一方のアルゴリズムを選択して処理をすることで高速な暗号処理演算が実行可能となる。
【０２０８】
（４）種数２、標数２の有限体上定義された超楕円曲線の因子Ｄに対するスカラー倍算の演算処理において、
（ａ）加算および２倍算を適用した演算アルゴリズム、
（ｂ）加算および１／２倍算を適用した演算アルゴリズム、
から高速演算可能なアルゴリズムを選択して因子のスカラー倍算を実行する方法。
【０２０９】
次に、上述した処理、すなわち、超楕円曲線の因子Ｄに対するスカラー倍算の演算処理において、
（ａ）加算および２倍算を適用した演算アルゴリズム、
（ｂ）加算および１／２倍算を適用した演算アルゴリズム、
から高速演算可能なアルゴリズムを選択して因子のスカラー倍算を実行する処理構成を持つ暗号処理装置の構成例について説明する。
【０２１０】
図１４に、本発明の暗号処理装置の一実施例に構成されるスカラー倍演算手段４３０の構成例を示す。図１４に示すスカラー倍演算手段４３０は、図９〜図１３を参照して説明したデータ構成を持つ２倍算・１／２倍算切換テーブル４３１と、２倍算・１／２倍算切換テーブル４３１を参照して、入力する超楕円曲線パラメータに基づいて、高速に実行可能な演算が２倍算であるか１／２倍算であるかを判断する群演算種類判定手段４３２と、先に図５を参照して説明した２倍算・１／２倍算切換スカラー倍算手段２５０と同様の構成を有し、
（ａ）加算および２倍算を適用した演算アルゴリズム、
（ｂ）加算および１／２倍算を適用した演算アルゴリズム、
（ａ）（ｂ）のいずれのアルゴリズムについても実行可能な２倍算・１／２倍算切換スカラー倍算手段４３３を有する。
【０２１１】
図１４に示すスカラー倍演算手段４３０を適用して、超楕円曲線の因子Ｄに対するスカラー倍算を実行する場合、入力データ４１０として、適用する超楕円曲線を定義する曲線パラメータ４１１、実際の演算対象となる入力因子４１２とスカラー値４１３の各情報がスカラー倍演算手段４３０に入力される。
【０２１２】
群演算種類判定手段４３２は、２倍算・１／２倍算切換テーブル４３１を参照して、入力する超楕円曲線の曲線パラメータ４１１に基づいて、高速に実行可能な演算が２倍算であるか１／２倍算であるかを判断する。その判断に基づいて、２倍算・１／２倍算切換スカラー倍算手段４３３を制御して、高速に実行される一方のアルゴリズム、すなわち、
（ａ）加算および２倍算を適用した演算アルゴリズム、
（ｂ）加算および１／２倍算を適用した演算アルゴリズム、
（ａ）（ｂ）のいずれのアルゴリズムに基づくスカラー倍算を、２倍算・１／２倍算切換スカラー倍算手段４３３において実行し、処理結果としてのスカラー倍算結果４５１を出力データ４５０として出力する。
【０２１３】
この構成において、２倍算・１／２倍算切換スカラー倍算手段４３３は、図５を参照して説明したと同様の構成を有し、図５に示す演算手段１５０は、図４を参照して説明した構成を持つものである。すなわち、図４に示すように、有限体演算手段１２０には、加算手段１２１、乗算手段１２２、２乗算手段１２３、逆元演算手段１２４、平方根演算手段１２５、ハーフトレース演算手段１２６、トレース演算手段１２７を有しており、これらの手段において、２倍算・１／２倍算切換スカラー倍算処理に必要な演算が実行される。
【０２１４】
先に、図４、図５を参照して説明したように、加算手段１２１、乗算手段１２２、２乗算手段１２３、逆元演算手段１２４は、ハードウェア構成、プログラムにおいて２倍算、１／２倍算、加算演算各々に専用の構成とするのではなく、いずれの処理においても共通に利用可能な１つの構成とする。共通構成とすることで、演算手段の構成としてのハードウェアサイズ、プログラムサイズを小型化することが可能となる。ハードウェアを用いた場合はゲート数の削減、装置の小型化を実現することができる。
【０２１５】
群演算種類判定手段４３２においては、２倍算・１／２倍算切換テーブル４３１を参照して、入力する超楕円曲線の曲線パラメータ４１１に基づいて、高速に実行可能な演算が２倍算であるか１／２倍算であるかを判断する処理が行なわれる。具体的には、例えば図９〜図１３を参照して説明した２倍算・１／２倍算切換テーブルを参照して判断が実行される。例えば、入力する曲線パラメータが、図１０に示す曲線識別子（Ｃ１）に登録されたパラメータと一致する場合、テーブルには、高速演算アルゴリズム情報として１／２倍算が高速であることが記録されているので、その判断に基づいて、２倍算・１／２倍算切換スカラー倍算手段４３３を、加算および１／２倍算を適用した演算アルゴリズムに基づくスカラー倍算を実行するように制御して、２倍算・１／２倍算切換スカラー倍算手段４３３に、入力因子４１２、スカラー値４１３を入力してスカラー倍算を実行させて、処理結果としてのスカラー倍算結果４５１を出力データ４５０として出力する。
【０２１６】
このように、本発明の構成では、超楕円曲線暗号処理を実行する構成において、曲線パラメータ各々について２倍算・１／２倍算のいずれが高速演算可能かを登録した２倍算・１／２倍算切換テーブルを参照して、２倍算と１／２倍算のうち、高速な演算を選択して実行する構成としたので、適用する曲線に対して、常に高速なスカラー倍算を実行することができる。
【０２１７】
図１４を参照して本発明の暗号処理装置の構成例について説明したが、図１４に示す構成は、１つの構成例であり、本発明の暗号処理装置の構成はこの構成に限られるものではない。図１５を参照して本発明の暗号処理装置の構成例について説明する。
【０２１８】
図１５には、制御部４８１、演算処理部４８２、記憶部４８３、演算速度算出部４８４を持つ暗号処理装置を示している。制御部４８１は、暗号処理演算に適用する超楕円曲線の曲線パラメータや有限体のタイプに基づいて、スカラー倍算アルゴリズムとして、２倍算適用演算アルゴリズムと、１／２倍算適用演算アルゴリズムのいずれの演算アルゴリズムが高速演算可能かを判定する。演算処理部４８２は、制御部４８１において、高速演算可能と判定されたアルゴリズムを選択適用して、超楕円曲線の因子Ｄに対するスカラー倍算の演算処理を実行する。図１４の構成では、群演算種類判定手段４３２が制御部に相当し、２倍算・１／２倍算切換スカラー倍算手段４３３が演算処理部に相当する。
【０２１９】
制御部４８１は、例えば、超楕円曲線の曲線パラメータと、高速演算の実行可能なアルゴリズム情報とを対応付けたテーブルを記憶部４８３から取得し、暗号処理演算に適用する超楕円曲線の曲線パラメータと前記テーブルに記録された曲線パラメータ情報とを比較照合し、一致または類似するテーブル記録データに対応して設定されたアルゴリズム情報を高速演算可能なアルゴリズムと判定する処理を実行する。
【０２２０】
演算処理部４８２は、２倍算適用演算アルゴリズムと、１／２倍算適用演算アルゴリズムの両アルゴリズムを実行可能な構成を有し、２倍算および１／２倍算において共通に利用する演算実行ハードウェアまたはプログラムを利用した演算処理を実行する。
【０２２１】
制御部４８１のアルゴリズム判定処理は、先に、図６に示すフローチャートを参照して説明した処理に従って実行される。すなわち、まず、暗号処理演算に適用する超楕円曲線の曲線パラメータ、具体的には、暗号処理演算に適用する種数２、標数２の有限体上定義された超楕円曲線：ｙ２＋ｈ（ｘ）ｙ＝ｆ（ｘ）の曲線パラメータに含まれるコファクター［ｃ］が２で、ｈ（ｘ）が既約多項式の場合に、１／２倍算適用演算アルゴリズムの高速実行可能性高速に計算が可能であると判定し、この場合に、２倍算適用演算アルゴリズムと、１／２倍算適用演算アルゴリズムのいずれの演算アルゴリズムが高速演算可能かを判定する。判定処理には、先に、図９〜図１３を参照して説明した２倍算・１／２倍算切換テーブルを記憶部４８３から取得してテーブルの記録情報に基づいて判定する。
【０２２２】
なお、暗号処理装置内に演算速度算出手段４８４を設定し、演算速度算出手段４８４が、演算処理部４８２を適用して、暗号処理演算に適用する超楕円曲線の曲線パラメータを適用した２倍算適用演算と、１／２倍算適用演算を実行させて処理時間を計測する構成としてもよい。この場合、制御部４８１は、演算速度算出手段４８４の算出結果に基づいて、スカラー倍算アルゴリズムとして、２倍算適用演算アルゴリズムと、１／２倍算適用演算アルゴリズムのいずれの演算アルゴリズムが高速演算可能かの判定処理を実行する。
【０２２３】
具体的に、スカラー倍算を行った際に、２倍算と１／２倍算でどのような差が出るのかを考察する。
ここでは、コファクター［ｃ］は２であると仮定する。また、スカラー倍算は、Ｄｏｕｂｌｅ−ａｎｄ−ａｄｄもしくはＨａｌｖｅ−ａｎｄ−ａｄｄを用いる。スカラー値のビット長（ベースポイントの位数のビット長）をｍとする。この場合、スカラー値の非零のビット数はおおよそｍ／２個となる。よって、Ｄｏｕｂｌｅ−ａｎｄ−ａｄｄとＨａｌｖｅ−ａｎｄ−ａｄｄの計算量は、
（（加算の計算量）／２＋（２倍算ｏｒ１／２倍算の計算量））×ｍ
で計算することができる。
【０２２４】
まず、曲線パラメータ（ｈ２＝ｈ１＝１、ｆ４＝０、ｈ（ｘ）は既約多項式）を用いた場合を考える。
このとき、加算の計算量は、
２１Ｍ＋３Ｓ＋１Ｉ
である。
多項式基底を用いた場合、１Ｓ＝０．１ＭＰ、１Ｉ＝８ＭＰと仮定していたので、多項式基底での加算の計算量は２９．３ＭＰとなる。
また、２倍算は２６．７ＭＰ、１／２倍算は２５．０５ＭＰである。
よって、
２倍算を適用したＤｏｕｂｌｅ−ａｎｄ−ａｄｄを用いた場合は４１．３５７ＭＰ×ｍ、
１／２倍算を適用したＨａｌｖｅ−ａｎｄ−ａｄｄを用いた場合は３９．７ＭＰｘｍ
となり、
１／２倍算を用いた方が２倍算を用いたものよりも、４％ほど高速である。
【０２２５】
超楕円曲線暗号処理手段が２倍算のみを搭載していた場合、上記曲線パラメータを用いた場合は、より高速な１／２倍算アルゴリズムを適用することができないため、計算が遅くなるという欠点がある。しかしながら、本発明を用いれば、１／２倍算を選択し、Ｈａｌｖｅ−ａｎｄ−ａｄｄを実行し、計算を高速に行うことができる。
【０２２６】
次に、曲線パラメータ（ｈ２＝ｈ１＝ｈ１＝１、ｆ４＝０）を用いた場合を考える。
このとき、加算の計算量は２１Ｍ＋３Ｓ＋１Ｉである。
多項式基底を用いた場合、１Ｓ＝０．１ＭＰ、１Ｉ＝８ＭＰと仮定していたので、多項式基底での加算の計算量は２９．３ＭＰとなる。
また、２倍算は２３．７ＭＰ、１／２倍算は２４。０５ＭＰである。
よって、
２倍算を適用したＤｏｕｂｌｅ−ａｎｄ−ａｄｄを用いた場合は３８．３５ＭＰ×ｍ、
１／２倍算を適用したＨａｌｖｅ−ａｎｄ−ａｄｄを用いた場合は３８．７ＭＰ×ｍ
となり、２倍算を用いた方が１／２倍算を用いたものよりも、１％ほど高速である。
【０２２７】
超楕円曲線暗号処理手段が１／２倍算のみを搭載していた場合、上記曲線パラメータを用いた場合は、より高速な２倍算アルゴリズムを適用することができないため、計算が遅くなるという欠点がある。しかしながら、本発明を用いれば、２倍算を選択し、Ｄｏｕｂｌｅ−ａｎｄ−ａｄｄを実行し、計算を高速に行うことができる。
【０２２８】
さらに、ｈ（ｘ）が既約多項式で、かつ、曲線パラメータカラーが一般的（ｈ２＝１、ｆ４＝０）で、多項式基底を用いた場合や、ｈ（ｘ）が既約多項式で、かつ、任意の曲線パラメータで、正規基底を用いた場合は、１／２倍算の方が２倍算よりも高速である。そのため、この場合、本発明により、高速な１／２倍算を選択し、高速にスカラー倍算を計算することができる。
【０２２９】
また、ｈ（ｘ）が可約多項式である場合、２倍算を選択することにより、高速にスカラー倍算を行うことができる。
また、コファクターが２以外の場合は、２倍算を選択することにより、高速にスカラー倍算を行うことができる。
上記の場合は、各種有限体の演算速度を仮定して考えたものである。実際の超楕円曲線暗号処理手段の構成や実装方法により、２倍算と１／２倍算の演算速度の関係は、上記とは異なることもありうるが、上記はあくまでも一例を挙げたものである。
【０２３０】
［暗号処理装置のハードウェア構成例］
最後に、上述の暗号処理を実行するデバイスとしてのＩＣモジュール５００の構成例を図１６に示す。上述の処理は、例えばＰＣ、ＩＣカード、リーダライタ、その他、様々な情報処理装置において実行可能であり、図１６に示すＩＣモジュール５００は、これら様々な機器に構成することが可能である。
【０２３１】
図１６に示すＣＰＵ(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)
５０２  メモリ
５０３  暗号処理部
５０４  乱数発生器
５０５  送受信部
【図１】
2008020757.tif 000022
【図２】
2008020757.tif 000023
【図３】
2008020757.tif 000024
【図４】
2008020757.tif 000025
【図５】
2008020757.tif 000026
【図６】
2008020757.tif 000027
【図７】
2008020757.tif 000028
【図８】
2008020757.tif 000029
【図９】
2008020757.tif 000030
【図１０】
2008020757.tif 000031
【図１１】
2008020757.tif 000032
【図１２】
2008020757.tif 000033
【図１３】
2008020757.tif 000034
【図１４】
2008020757.tif 000035
【図１５】
2008020757.tif 000036
【図１６】
2008020757.tif 000037