(57)【要約】【課題】  超楕円暗号処理において安全でかつ高速な演算を実現する装置および方法を実現する。【解決手段】  超楕円曲線暗号の因子Ｄに対するスカラー倍算において、演算処理として、１／２倍算を含む演算を実行することでスカラー倍算を高速化した。例えば、種数２、標数２のｈ（ｘ）＝ｘ２＋ｘ＋ｈ０，ｆ４＝０をパラメータに持つ超楕円曲線、あるいは、ｈ（ｘ）＝ｘ２＋ｈ１ｘ＋ｈ０，ｆ４＝０をパラメータに持つ超楕円曲線、あるいは、ｈ（ｘ）＝ｘをパラメータに持つ超楕円曲線の因子Ｄに対するスカラー倍算において１／２倍算を含む演算を実行する。また、固定因子Ｄについての［１／２ｉＤ］計算値に基づいて、ｋ１，ｋ１'，（ｋ０，ｋ０'）のいずれが正しいかを記録したテーブルの適用、さらに逆元演算を減少させることで計算量の削減、高速化を実現した。【選択図】  図２
2006227562.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）方式がある。超楕円曲線暗号方式については、例えば非特許文献１、非特許文献２に記載されている。
【００１０】
楕円曲線暗号では有限体Ｆｑ上で定義される楕円曲線上の点をＰとし、スカラー倍算した点ｋＰ（ｋ∈Ｚ）をＱとすると、Ｑからｋを求める問題は離散対数問題に帰着できる。一方、超楕円曲線暗号では点の形式的和である因子（ｄｉｖｉｓｏｒ）をＤ１とし、スカラー倍算ｋＤ１で定義される因子をＤ２とすると、Ｄ２からｋを求める問題は超楕円曲線におけるヤコビ多様体上の離散対数問題として公開鍵暗号として用いることができる。
【００１１】
超楕円曲線では曲線を特徴づける値は種数（ｇｅｎｕｓ）ｇである。ｐを素数、ｎを正の整数、ｑ＝ｐｎとする。このとき有限体Ｆｑ上で定義される種数ｇの超楕円曲線Ｃは以下の方程式、
ｙ２＋ｈ（ｘ）ｙ＝ｆ（ｘ）
で定義される。ここで、ｈ（ｘ），ｆ（ｘ）∈Ｆｑ［ｘ］，ｆ（ｘ）は、次数２ｇ＋１のｍｏｎｉｃ多項式である。
【００１２】
超楕円曲線Ｃ上の点Ｐ＝（ｘ、ｙ）に対して共役点（ｏｐｐｏｓｉｔｅ  ｐｏｉｎｔ）は、−Ｐ＝（ｘ、ｙ＋ｈ（ｘ））として定義される。また、Ｐ＝−Ｐである点を分岐点（ｒａｍｉｆｉｃａｔｉｏｎ  ｐｏｉｎｔ）と呼ぶ。
【００１３】
超楕円曲線暗号の定義体の演算サイズ（ビット長）は楕円曲線暗号と同等の安全性を仮定した場合、楕円曲線の定義体の演算サイズに比べて１／ｇに小さくなることが知られている。演算サイズが小さいことは実装上メリットがあり、超楕円曲線暗号の利点の一つして挙げられる。
【００１４】
次に、超楕円曲線暗号の基本事項について説明する。前述したように、超楕円曲線暗号では点の形式的和である因子（ｄｉｖｉｓｏｒ）をＤ１とし、スカラー倍算ｋＤ１で定義される因子をＤ２とすると、Ｄ２からｋを求める問題は超楕円曲線におけるヤコビ多様体上の離散対数問題として公開鍵暗号として用いることができる。
【００１５】
ここで、因子（ｄｉｖｉｓｏｒ）は有理点の形式和であり、以下の形式で表現することができる。
【数１】
2006227562.tif 000003
【００１６】
また、半被約因子（ｓｅｍｉ  ｒｅｄｕｃｅｄ  ｄｉｖｉｓｏｒ）は、以下の形式で表現することができる。
【数２】
2006227562.tif 000004
ただし、Ｐｉ＝（ｘｉ、ｙｉ）かつｉ≠ｊに対してＰｉ≠Ｐｊである。
【００１７】
また、ΣｍｉをＤのウェイト（ｗｅｉｇｈｔ）と呼ぶ。さらにウェイト（ｗｅｉｇｈｔ）が種数ｇ以下である半被約因子を被約因子（ｒｅｄｕｃｅｄ  ｄｉｖｉｓｏｒ）と呼ぶ。
【００１８】
超楕円曲線のヤコビ（Ｊａｃｏｂｉ）多様体上の任意の半被約因子Ｄは下記の多項式Ｕ、Ｖ∈Ｆｑ［ｘ］を用いてＤ＝（Ｕ、Ｖ）として表現できる。これをマンホード（Ｍｕｍｆｏｒｄ）表現と呼ぶ。なお、マンホード（Ｍｕｍｆｏｒｄ）表現については、例えば非特許文献３に記載されている。
【数３】
2006227562.tif 000005
【００１９】
種数（ｇｅｎｕｓ）２の任意の被約因子Ｄはマンホード（Ｍｕｍｆｏｒｄ）表現を用いると、有限体Ｆｑ上の元を係数に持つ２次以下の多項式の組、すなわち、
（Ｕ、Ｖ）＝（ｘ２＋ｕ１ｘ＋ｕ０、ｖ１ｘ＋ｖ０）、または、
（Ｕ、Ｖ）＝（ｘ＋ｘ０、ｙ０）
として表現することができる。
また、零元は、
（Ｕ，Ｖ）＝（１，０）＝Ｏ
として表現される。
【００２０】
次に、超楕円曲線暗号で用いられる因子のスカラー倍算について説明する．因子のスカラー倍算は加算アルゴリズムと呼ばれる因子の加算と２倍算組み合わせで計算することができる。以下では主要な加算アルゴリズムについて説明する。
【００２１】
最初に提案された実用的なアルゴリズムはＣａｎｔｏｒのアルゴリズムである。このアルゴリズムについては、例えば非特許文献１、非特許文献２に記載されている。このアルゴリズムはあらゆる種数の超楕円曲線上の因子に対して適用可能なアルゴリズムであるが、楕円曲線に比べてアルゴリズムが複雑で計算量が多いことが欠点である。
【００２２】
Ｈａｒｌｅｙは種数２の超楕円曲線に限定し、因子のｗｅｉｇｈｔの場合分けをおこない、それぞれの場合で最適化を行うことでより計算量の少ないアルゴリズムを提案した。この研究を受けて超楕円曲線暗号（ＨＥＣＣ）における演算アルゴリズムの改良、拡張の研究が近年盛んになっている。
【００２３】
（ア）Ｈａｒｌｅｙのアルゴリズムは定義体を素体、種数２の曲線、因子の表現はＭｕｍｆｏｒｄ表現を用いている。このアルゴリズムの計算量の改善の研究例として、例えば、非特許文献４、非特許文献５、非特許文献６などが挙げられる。
（イ）さらに、定義体を２の拡大体の場合について拡張した処理例について、非特許文献７、非特許文献８に報告されている。
（ウ）また、因子の表現に拡張Ｍｕｍｆｏｒｄ表現、Ｗｅｉｇｈｔｅｄ  Ｃｏｏｒｄｉｎａｔｅを用いることで計算量を削減した研究として非特許文献１１、非特許文献１２、非特許文献６、非特許文献１３がある。
【００２４】
Ｈａｒｌｅｙアルゴリズムの処理について、図１を参照して説明する。なお、本発明は、標数２の有限体上定義された種数２の超楕円曲線に関するものであり、以下の説明では、曲線の種数を２、定義体の標数を２とする。
【００２５】
図１（Ａ）は、種数２の場合の因子の加算Ｄ１＋Ｄ２の処理例を示した図である。なお、因子Ｄ１、Ｄ２は、それぞれＤ１＝（Ｕ１、Ｖ１）、Ｄ２＝（Ｕ２、Ｖ２）とする。まず、因子のウェイト（ｗｅｉｇｈｔ）の値によって場合分けが行われる。すなわち、［Ｄ１＋Ｄ２］の各ウェイト（ｗｅｉｇｈｔ）の値によって、
（１）ｗｅｉｇｈｔ２＋ｗｅｉｇｈｔ２
（２）ｗｅｉｇｈｔ２＋ｗｅｉｇｈｔ１
（３）例外処理１
の場合分けが行なわれる。
【００２６】
次にｗｅｉｇｈｔ２同士の加算、すなわち（１）ｗｅｉｇｈｔ２＋ｗｅｉｇｈｔ２の場合、因子Ｄ１＝（Ｕ１、Ｖ１）、Ｄ２＝（Ｕ２、Ｖ２）について、最大公約数ｇｃｄ（Ｕ１、Ｕ２）＝１であれば、２つの因子Ｄ１＝（Ｕ１、Ｖ１）、Ｄ２＝（Ｕ２、Ｖ２）は、互いに同一または共役点（ｏｐｐｏｓｉｔｅ  ｐｏｉｎｔ）を含まない。この場合、
（１ａ）ＨａｒｌｅｙＡＤＤ、
すなわちハーレーアルゴリズムに従った加算処理を行う。（１ａ）ＨａｒｌｅｙＡＤＤの処理は例えば非特許文献７に示されているＭｏｓｔ  Ｆｒｅｑｕｅｎｔ  Ｃａｓｅと呼ばれる処理である。このＭｏｓｔ  Ｆｒｅｑｕｅｎｔ  Ｃａｓｅは、種数２の場合の因子の加算Ｄ１＋Ｄ２処理において、高確率で発生するケースである。
【００２７】
この（１ａ）ＨａｒｌｅｙＡＤＤの処理は、非常に高い確率でおこる。その他の例外処理の起こる確率は非常に低い。Ｍｏｓｔ  Ｆｒｅｑｕｅｎｔ  Ｃａｓｅの条件を満たさない場合、すなわち、因子Ｄ１＝（Ｕ１、Ｖ１）、Ｄ２＝（Ｕ２、Ｖ２）について、最大公約数ｇｃｄ（Ｕ１、Ｕ２）＝１を満足しない場合は、
（１ｂ）例外処理２を行う。
【００２８】
（２）ｗｅｉｇｈｔ２＋ｗｅｉｇｈｔ１の場合についても同様に、ｇｃｄ（Ｕ１、Ｕ２）＝１かどうかをチェックし、ｇｃｄ（Ｕ１、Ｕ２）＝１を満足する場合には、
（２ａ）ＥｘＨａｒＡＤＤ２＋１→２を実行し、
ｇｃｄ（Ｕ１、Ｕ２）＝１を満足しない場合には、
（２ｂ）例外処理３を行う。
（３）例外処理１は、ｗｅｉｇｈｔの場合分けが上記（１），（２）以外の場合である。
【００２９】
なお、上述した種数２の加算処理のアルゴリズムの詳細については、非特許文献８に記載（Ｔａｂｌｅ１，２）されている。
【００３０】
次に、種数２の場合の２倍算の流れを図１（Ｂ）を参照して説明する。２倍算は、Ｄ＋Ｄ＝２Ｄの処理である。入力をＤ１＝（Ｕ１，Ｖ１）とし、出力をＤ２＝［２］Ｄ１とする。
加算の場合と同様に因子Ｄのｗｅｉｇｈｔが
（４）ｗｅｉｇｈｔ２、
（５）ｗｅｉｇｈｔ１、
（６）ｗｅｉｇｈｔ０、
によってそれぞれ異なる処理を行う。
【００３１】
（４）ｗｅｉｇｈｔ２の場合、因子が分岐点を含むかどうかをチェックし、含まなければ、（４ａ）ＨａｒｌｅｙＤＢＬの処理を行う。因子が分岐点を含む場合は（４ｂ）例外処理６を行う。ｇｃｄ（ｈ，Ｕ１）＝１であれば、Ｄ１は分岐点を含まない。この場合、（４ａ）ＨａｒｌｅｙＤＢＬの処理を行う。ＨａｒｌｅｙＤＢＬの処理アルゴリズムは例えば非特許文献７にＭｏｓｔ  Ｆｒｅｑｕｅｎｔ  Ｃａｓｅとして示されている。ＨａｒｌｅｙＤＢＬの処理アルゴリズム（Ａｌｇｏｒｉｔｈｍ１）を、以下に示す。
【数４】
2006227562.tif 000006
【００３２】
後述するように、この処理が非常に高い確率でおこる。その他の例外処理の起こる確率は非常に低い。上述したように、Ｍｏｓｔ  Ｆｒｅｑｕｅｎｔ  Ｃａｓｅの条件を満たさない場合は例外処理６を行う。
【００３３】
ｗｅｉｇｈｔ１の場合も同様にｇｃｄ（ｈ，Ｕ１）＝１かどうかをチェックし，（５ａ）の処理、ＥｘＨａｒＤＢＬ１＋１→２もしくは、（５ｂ）の処理である例外処理７を行う。ＥｘＨａｒＤＢＬ１＋１→２のアルゴリズムについては、非特許文献８［４．１２．（ａ）］に示されている。
【００３４】
ＨａｒｌｅｙＡＤＤ，ＨａｒｌｅｙＤＢＬは、上述のようにｍｏｓｔ  ｆｒｅｑｕｅｎｔ  ｃａｓｅと呼ばれ、ランダムに因子を発生させて加算または２倍算を行うと、非常に高い確率でＨａｒｌｅｙＡＤＤ、ＨａｒｌｅｙＤＢＬの処理になる。なお、このＨａｒｌｅｙＡＤＤ、ＨａｒｌｅｙＤＢＬが、ｍｏｓｔ  ｆｒｅｑｕｅｎｔ  ｃａｓｅとなることの説明は、例えば非特許文献１４に説明されている。
【００３５】
非特許文献１４によると、このｍｏｓｔ  ｆｒｅｑｕｅｎｔ  ｃａｅｓ以外の処理になる確率はＯ（１／ｑ）である。ここでｑは定義体の要素数であり、安全な暗号用途ではqgが１６０ｂｉｔ程度必要になる大きな数であるので現実的にはＨａｒｌｅｙＡＤＤ、ＨａｒｌｅｙＤＢＬしか発生しない状況とみなすことができる。
【００３６】
従って超楕円曲線暗号（ＨＥＣＣ）の加算アルゴリズムをＨａｒｌｅｙアルゴリズムまたはその改良アルゴリズムを使って、例えばＩＣカードなどの暗号処理演算手段として実装する場合、
ＨａｒｌｅｙＡＤＤ、
ＨａｒｌｅｙＤＢＬ
だけを実装し、その他の確率的にほとんど起こらない複雑な例外処理についての演算を実行しない実装とする場合も多い。この場合、例外処理については、ｗｅｉｇｈｔの場合分けが必要のないＣａｎｔｏｒのアルゴリズムを実行する構成とするなどの方法が適用される。種数が高くなるほど複雑な例外処理の負担は増すため、非特許文献９，１０ではこの実装方法について説明している。
【００３７】
次に超楕円曲線暗号（ＨＥＣＣ）アルゴリズムにおける因子のスカラー倍算について説明する。超楕円曲線暗号（ＨＥＣＣ）アルゴリズムにおいて、因子のスカラー倍算は、超楕円加算と超楕円２倍算の組み合わせで計算することができる。スカラー倍算のアルゴリズムとして基本的なｂｉｎａｒｙ法とｄｏｕｂｌｅ−ａｎｄ−ａｄｄ−ａｌｗａｙｓ法を例に挙げて説明する。
【００３８】
前述したように、楕円曲線暗号では有限体Ｆｑ上で定義される楕円曲線上の点をＰとし、スカラー倍算した点ｋＰ（ｋ∈Ｚ）をＱとすると、Ｑからｋを求める問題は離散対数問題に帰着できる。一方、超楕円曲線暗号では点の形式的和である因子（ｄｉｖｉｓｏｒ）をＤ１とし、スカラー倍算ｋＤ１で定義される因子をＤ２とすると、Ｄ２からｋを求める問題は超楕円曲線におけるヤコビ多様体上の離散対数問題として公開鍵暗号として用いることができる。
【００３９】
因子Ｄに対して、スカラー倍算（Ｄ＝ｄＤ）に適用する乗数としてのスカラー値:ｄの２進数表現を、
ｄ＝（ｄｌ−１、・・・・・、ｄ０）、
ただし、ｄｌ−１＝１、ｄｌ−２，・・・，０＝１ｏｒ０とする。
【００４０】
スカラー倍算のアルゴリズムとして基本的なｂｉｎａｒｙ法の演算アルゴリズムには、
ｂｉｎａｒｙ（ｒｉｇｈｔ−ｔｏ−ｌｅｆｔ）法
ｂｉｎａｒｙ（ｌｅｆｔ−ｔｏ−ｒｉｇｈｔ）法
がある。
【００４１】
ｂｉｎａｒｙ（ｒｉｇｈｔ−ｔｏ−ｌｅｆｔ）法は、ｄを下位ビットから見ていき、ｄｉ＝１の場合に、［２ｉ］Ｄを加算することが特徴である。ｂｉｎａｒｙ（ｒｉｇｈｔ−ｔｏ−ｌｅｆｔ）法のアルゴリズム（Ａｌｇｏｒｉｔｈｍ２）を以下に示す。
【数５】
2006227562.tif 000007
【００４２】
一方、ｂｉｎａｒｙ（ｌｅｆｔ−ｔｏ−ｒｉｇｈｔ）法は、ｄを上位ビットから見ていき、毎ビットＤを２倍し、ｄｉ＝１の場合に、ベースポイントを加算することが特徴である。ｂｉｎａｒｙ（ｌｅｆｔ−ｔｏ−ｒｉｇｈｔ）法のアルゴリズム（Ａｌｇｏｒｉｔｈｍ３）を以下に示す。
【数６】
2006227562.tif 000008
【００４３】
次に、ベースポイントの生成処理について説明する。スカラー倍算の計算を暗号技術で用いる場合、入力に必要な因子Ｄ０は、
（１）事前に決めた因子の場合、
（２）事前に決められないランダムに発生する因子の場合、
の２つのタイプに分けることができる。
【００４４】
ここで（１）事前に決めた因子の場合、の入力因子をベースポイントと呼ぶことにする。
一般的なベースポイントの生成アルゴリズムを以下に示す。
（ａ）
定義体Ｆｑ上の元をランダムにｇ個選び、ｇ個の超楕円曲線上の点Ｐｉ（ｉ＝１、…、ｇ）を生成する。
（ａ１）  ランダムに選んだ各元をｘ座標ｘｉ（ｉ＝１…ｇ）とし、次に超楕円曲線上に乗るようにｘｉに対応するｙ座標を求める。
（ｂ）
ベースポイントの因子をＤ０＝（Ｕ（ｘ）、Ｖ（ｘ））とする。
（ｂ１）Ｕ（ｘ）＝（ｘ−ｘ１）（ｘ−ｘ２）…（ｘ−ｘｇ）
（ｂ２）Ｖ（ｘ）＝ｖｇ−１ｘｇ−１＋ｖｇ−２ｘｇ−２＋…＋ｖ０の係数ｖｉを決定する。例えば生成した点が全て異なる場合、Ｖ（ｘｉ）＝ｙｉよりｖｉを求めることができる。
（ｃ）  上記アルゴリズムにより生成される因子はｗｅｉｇｈｔ  ｇの因子となる。
【００４５】
スカラー倍算の計算を暗号技術で用いる場合、入力に必要な因子Ｄ０の生成、すなわちベースポイントの生成において、事前に決めた因子を適用する場合、上述の処理（ａ）〜（ｃ）によってｗｅｉｇｈｔ  ｇのベースポイントに適用する因子を求めることができる。
【００４６】
さらに、楕円曲線暗号では、有理点の１／２倍算が提案されている。例えば、非特許文献１５、特許文献１、特許文献２に楕円曲線暗号における有理点の１／２倍算が示されている。有理点のスカラー倍算を計算する際に、加算と２倍算を用いるのではなくて、加算と１／２倍算を用いた処理を開示している。
【００４７】
楕円曲線暗号の１／２倍算は，一般に２倍算よりも高速であり、結果として１／２倍算を用いたスカラー倍算は高速となる。非特許文献１６によると、プロセッサとして、インテル社製［Ｉｎｔｅｌ  ＰｅｎｔｉｕｍＩＩＩ  ８００ＭＨｚ］でソフトウェア実装を行った結果、１／２倍算は、２倍算に比べて、Ｆｑ，ｑ＝２１６３の定義体では、約２．１倍高速であり、ｑ＝２２３３の定義体では、約２．６倍高速であると報告されている。超楕円曲線暗号は、楕円曲線暗号の一般化であり、楕円曲線暗号で用いられている演算を超楕円曲線に拡張できる場合がある。例えば、楕円曲線暗号でｙ座標を演算で用いないため、高速な計算を行なうことの出来る  Ｍｏｎｔｇｏｍｅｒｙ法が、非特許文献１７、１８において、超楕円曲線暗号に拡張された例が示されている。超楕円曲線暗号でも、２倍算よりも高速な１／２倍算が実現できれば、因子のスカラー倍算も、従来よりも高速に計算することが期待できる。しかしながら、従来は、この１／２倍算が知られていなかった。なお、２倍算を用いた高速演算手法として発表された文献として、非特許文献１９がある。
【特許文献１】E.Knudsen. COMPUTING METHOD FOR ELLIPTIC CURVE CRYPTOGRAPHY, WO 01/04742 A1, 18 Jan 2001
【特許文献２】R.Schroeppel. Elliptic curve point ambiguity resolution apparatus and method, WO 01/35573 A1, 17 May 2000
【非特許文献１】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.
【非特許文献１５】E.Knudsen. Elliptic Scalar Multiplication Using Point Halving. ASIACRYPTO '99, LNCS 1716, pp.135-149, Springer-Verlag, 1999.
【非特許文献１６】K.Fong, D.Hankerson, J.Lopez, and A.Menezes. Field inversion and point halving revised. Technical Report CORR2003-18, http://www.cacr.math.uwaterloo.ca/techreports/2003/corr2003-18.pdf
【非特許文献１７】S. Dquesne. Montgomery Scalar Multiplication for Genus 2 Curves. ANTS-VI, LNCS 3076, pp.153-168, 2004.
【非特許文献１８】T. Lange. Montgomery Addition for Genus Two Curves. ANTS-VI, LNCS 3076, pp.309-317, 2004.
【非特許文献１９】T. Lange. Efficient Doubling on Genus Two Curves over Binary Fields, SAC 2004, pre-proceedings, pp.189-202, 2004.
【発明の開示】
【発明が解決しようとする課題】
【００４８】
現在、実用フェーズに入りつつある楕円曲線暗号（ＥＣＣ）アルゴリズムに対して、その拡張概念である超楕円曲線暗号（ＨＥＣＣ）アルゴリズムは、現在、学会レベルで高速アルゴリズムや、その実装方法についての研究が進められている。超楕円曲線暗号（ＨＥＣＣ）のスカラー倍算の演算時間は、楕円曲線暗号（ＥＣＣ）に近づきつつある程度に過ぎず、さらなる高速化が望まれている。
【００４９】
本発明は、このような現状に鑑みてなされたものであり、超楕円曲線暗号（ＨＥＣＣ）のスカラー倍算の演算時間を短縮し、高速処理可能な超楕円曲線暗号（ＨＥＣＣ）演算処理を実現する暗号処理演算方法、および暗号処理装置、並びにコンピュータ・プログラムを提供することを目的とする。
【００５０】
本発明は、楕円曲線暗号の１／２倍算を、超楕円曲線暗号に拡張し高速に計算できるアルゴリズム、曲線パラメータ、定義体を見つけ、超楕円曲線暗号において１／２倍算を適用した演算処理により、高速演算処理を実現する暗号処理演算方法、および暗号処理装置、並びにコンピュータ・プログラムを提供することを目的とする。
【課題を解決するための手段】
【００５１】
本発明の第１の側面は、
超楕円曲線暗号に基づく暗号処理演算を実行する暗号処理演算方法であり、
超楕円曲線の因子Ｄに対するスカラー倍算の演算において、演算処理として、１／２倍算を含む演算を実行する演算ステップ、
を有することを特徴とする暗号処理演算方法にある。
【００５２】
さらに、本発明の暗号処理演算方法の一実施態様において、前記演算ステップは、種数２、標数２のランダムパラメータを持つ超楕円曲線の因子Ｄに対するスカラー倍算において１／２倍算を含む演算を実行するステップであることを特徴とする。
【００５３】
さらに、本発明の暗号処理演算方法の一実施態様において、前記演算ステップは、種数２、標数２のｈ（ｘ）＝ｘ２＋ｘ＋ｈ０，ｆ４＝０をパラメータに持つ超楕円曲線の因子Ｄに対するスカラー倍算において１／２倍算を含む演算を実行するステップであることを特徴とする。
【００５４】
さらに、本発明の暗号処理演算方法の一実施態様において、前記演算ステップは、種数２、標数２のｈ（ｘ）＝ｘ２＋ｈ１ｘ＋ｈ０，ｆ４＝０をパラメータに持つ超楕円曲線の因子Ｄに対するスカラー倍算において１／２倍算を含む演算を実行するステップであることを特徴とする。
【００５５】
さらに、本発明の暗号処理演算方法の一実施態様において、前記演算ステップは、種数２、標数２のｈ（ｘ）＝ｘをパラメータに持つ超楕円曲線の因子Ｄに対するスカラー倍算において１／２倍算を含む演算を実行するステップであることを特徴とする。
【００５６】
さらに、本発明の暗号処理演算方法の一実施態様において、前記暗号処理演算方法は、予め固定された因子Ｄについての［１／２ｉＤ］計算値に基づいて、ｋ１，ｋ１'，（ｋ０，ｋ０'）のいずれが正しいかを記録したテーブルを参照するテーブル参照ステップを有し、前記演算ステップは、前記テーブルの参照に基づく判定処理によって、１／２倍算の計算量を削減した演算処理として実行することを特徴とする。
【００５７】
さらに、本発明の暗号処理演算方法の一実施態様において、前記演算ステップは、
入力：Ｄ２＝（Ｕ２，Ｖ２）、
出力：Ｄ１＝（Ｕ１，Ｖ１）＝［１／２］Ｄ２、
ただし、Ｕｉ（ｘ）＝ｘ２＋ｕｉ１ｘ＋ｕｉ０，Ｖｉ（ｘ）＝ｖｉ１ｘ＋ｖｉ０，ｇｃｄ（ｈ，Ｕｉ）＝１，ｉ＝１，２、
とした１／２倍算の演算アルゴリズムに基づいて導出される以下の関係式、
１／ｋ１＝ｈ２＋ｋ１ｕ２１
を適用し、逆元演算を行なうことなく乗算および加算処理によって逆元１／ｋ１の値を算出するステップを含むことを特徴とする。
【００５８】
さらに、本発明の暗号処理演算方法の一実施態様において、前記暗号処理演算方法は、
入力：Ｄ２＝（Ｕ２，Ｖ２）、
出力：Ｄ１＝（Ｕ１，Ｖ１）＝［１／２］Ｄ２、
ただし、Ｕｉ（ｘ）＝ｘ２＋ｕｉ１ｘ＋ｕｉ０，Ｖｉ（ｘ）＝ｖｉ１ｘ＋ｖｉ０，ｇｃｄ（ｈ，Ｕｉ）＝１，ｉ＝１，２、
とした１／２倍算演算アルゴリズムにおいて、１／ｕ２１を入力値として適用しない設定を持つアルゴリズムに従った演算を実行することを特徴とする。
【００５９】
さらに、本発明の暗号処理演算方法の一実施態様において、前記暗号処理演算方法は、種数２、標数２のｈ（ｘ）＝ｘ２＋ｈ１ｘ＋ｈ０，ｆ４＝０をパラメータに持つ超楕円曲線の因子Ｄに対するスカラー倍算を実行する演算方法であり、前記演算ステップは、算出済みの値として１／ｈ１２を入力値として設定し、逆元１／ｈ１２を算出する処理を実行することなく、算出済みの入力値１／ｈ１２を適用するステップを含むことを特徴とする。
【００６０】
さらに、本発明の第２の側面は、
超楕円曲線暗号に基づく暗号処理演算を実行する暗号処理装置であり、
超楕円曲線の因子Ｄに対するスカラー倍算の演算において、演算処理として、１／２倍算を含む演算を実行する演算実行部を有することを特徴とする暗号処理装置にある。
【００６１】
さらに、本発明の暗号処理装置の一実施態様において、前記演算実行部は、種数２、標数２のランダムパラメータを持つ超楕円曲線の因子Ｄに対するスカラー倍算において１／２倍算を含む演算を実行する構成であることを特徴とする。
【００６２】
さらに、本発明の暗号処理装置の一実施態様において、前記演算実行部は、種数２、標数２のｈ（ｘ）＝ｘ２＋ｘ＋ｈ０，ｆ４＝０をパラメータに持つ超楕円曲線の因子Ｄに対するスカラー倍算において１／２倍算を含む演算を実行する構成であることを特徴とする。
【００６３】
さらに、本発明の暗号処理装置の一実施態様において、前記演算実行部は、種数２、標数２のｈ（ｘ）＝ｘ２＋ｈ１ｘ＋ｈ０，ｆ４＝０をパラメータに持つ超楕円曲線の因子Ｄに対するスカラー倍算において１／２倍算を含む演算を実行する構成であることを特徴とする。
【００６４】
さらに、本発明の暗号処理装置の一実施態様において、前記演算実行部は、種数２、標数２のｈ（ｘ）＝ｘをパラメータに持つ超楕円曲線の因子Ｄに対するスカラー倍算において１／２倍算を含む演算を実行する構成であることを特徴とする。
【００６５】
さらに、本発明の暗号処理装置の一実施態様において、前記暗号処理装置は、予め固定された因子Ｄについての［１／２ｉＤ］計算値に基づいて、ｋ１，ｋ１'，（ｋ０，ｋ０'）のいずれが正しいかを記録したテーブルを格納した記憶部を有し、前記演算実行部は、前記テーブルの参照に基づく判定処理によって、１／２倍算の計算量を削減した演算処理を実行する構成であることを特徴とする。
【００６６】
さらに、本発明の暗号処理装置の一実施態様において、前記演算実行部は、
入力：Ｄ２＝（Ｕ２，Ｖ２）、
出力：Ｄ１＝（Ｕ１，Ｖ１）＝［１／２］Ｄ２、
ただし、Ｕｉ（ｘ）＝ｘ２＋ｕｉ１ｘ＋ｕｉ０，Ｖｉ（ｘ）＝ｖｉ１ｘ＋ｖｉ０，ｇｃｄ（ｈ，Ｕｉ）＝１，ｉ＝１，２、
とした１／２倍算の演算アルゴリズムに基づいて導出される以下の関係式、
１／ｋ１＝ｈ２＋ｋ１ｕ２１
を適用し、逆元演算を行なうことなく乗算および加算処理によって逆元１／ｋ１の値を算出する構成であることを特徴とする。
【００６７】
さらに、本発明の暗号処理装置の一実施態様において、前記演算実行部は、
入力：Ｄ２＝（Ｕ２，Ｖ２）、
出力：Ｄ１＝（Ｕ１，Ｖ１）＝［１／２］Ｄ２、
ただし、Ｕｉ（ｘ）＝ｘ２＋ｕｉ１ｘ＋ｕｉ０，Ｖｉ（ｘ）＝ｖｉ１ｘ＋ｖｉ０，ｇｃｄ（ｈ，Ｕｉ）＝１，ｉ＝１，２、
とした１／２倍算演算アルゴリズムを実行する構成であり、１／ｕ２１を入力値として適用しない設定を持つアルゴリズムに従った演算を実行する構成であることを特徴とする。
【００６８】
さらに、本発明の暗号処理装置の一実施態様において、前記演算実行部は、種数２、標数２のｈ（ｘ）＝ｘ２＋ｈ１ｘ＋ｈ０，ｆ４＝０をパラメータに持つ超楕円曲線の因子Ｄに対するスカラー倍算を実行する構成を有し、算出済みの値として１／ｈ１２を入力値とし、逆元１／ｈ１２を算出する処理を実行することなく、算出済みの入力値１／ｈ１２を適用した演算を実行する構成であることを特徴とする。
【００６９】
さらに、本発明の第３の側面は、
超楕円曲線暗号に基づく暗号処理演算をコンピュータ上で実行させるコンピュータ・プログラムであり、
超楕円曲線の因子Ｄに対するスカラー倍算の演算において、演算処理として、１／２倍算を含む演算を実行する演算ステップ、
を有することを特徴とするコンピュータ・プログラムにある。
【００７０】
なお、本発明のコンピュータ・プログラムは、例えば、様々なプログラム・コードを実行可能なコンピュータ・システムに対して、コンピュータ可読な形式で提供する記憶媒体、通信媒体、例えば、ＣＤやＦＤ、ＭＯなどの記録媒体、あるいは、ネットワークなどの通信媒体によって提供可能なコンピュータ・プログラムである。このようなプログラムをコンピュータ可読な形式で提供することにより、コンピュータ・システム上でプログラムに応じた処理が実現される。
【００７１】
本発明のさらに他の目的、特徴や利点は、後述する本発明の実施例や添付する図面に基づくより詳細な説明によって明らかになるであろう。なお、本明細書においてシステムとは、複数の装置の論理的集合構成であり、各構成の装置が同一筐体内にあるものには限らない。
【発明の効果】
【００７２】
本発明の構成によれば、楕円曲線暗号の１／２倍算を、超楕円曲線暗号に拡張し、高速演算が実現される。超楕円曲線上の因子の演算を使う暗号処理演算において、処理の重い演算は因子のスカラー倍算であり、本発明の処理によりスカラー倍算を高速化することで超楕円曲線暗号の処理を大幅に改善することができる。
【００７３】
本発明の構成によれば、超楕円曲線暗号の因子Ｄに対するスカラー倍算において、演算処理として、１／２倍算を含む演算を実行することでスカラー倍算を高速化することができる。例えば、種数２、標数２のｈ（ｘ）＝ｘ２＋ｘ＋ｈ０，ｆ４＝０をパラメータに持つ超楕円曲線の因子Ｄに対するスカラー倍算、あるいは、種数２、標数２のｈ（ｘ）＝ｘ２＋ｈ１ｘ＋ｈ０，ｆ４＝０をパラメータに持つ超楕円曲線の因子Ｄに対するスカラー倍算、あるいは、種数２、標数２のｈ（ｘ）＝ｘをパラメータに持つ超楕円曲線の因子Ｄに対するスカラー倍算において１／２倍算を含む演算を実行することで、高速演算が実現される。
【００７４】
さらに、本発明の構成によれば、予め固定された因子Ｄについての［１／２ｉＤ］計算値に基づいて、ｋ１，ｋ１'，（ｋ０，ｋ０'）のいずれが正しいかを記録したテーブルを適用することで、因子のスカラー倍算における計算量をさらに削減することが可能となり、さらなる高速化が実現される。
【００７５】
さらに、本発明の構成によれば、超楕円曲線暗号の因子Ｄに対するスカラー倍算において、演算処理として、１／２倍算を含む演算を実行する構成とするともに、１／２倍算の演算処理において逆元演算の実行回数を減少させるアルゴリズムを適用したので、因子のスカラー倍算における計算量をさらに削減することが可能となり、さらなる高速化が実現される。
【発明を実施するための最良の形態】
【００７６】
以下、本発明の暗号処理装置および暗号処理演算方法、並びにコンピュータ・プログラムの詳細について説明する。
【００７７】
本発明は、楕円曲線暗号を一般化した超楕円曲線暗号（ＨＥＣＣ：Hyper Elliptic Curve Cryptography）についての高速化演算手法である。前述したように、超楕円曲線では曲線を特徴づける値は種数（ｇｅｎｕｓ）ｇである。ｐを素数、ｎを正の整数、ｑ＝ｐｎとする。このとき有限体Ｆｑ上で定義される種数ｇの超楕円曲線Ｃは以下の方程式、
ｙ２＋ｈ（ｘ）ｙ＝ｆ（ｘ）
で定義される。ここで、ｈ（ｘ），ｆ（ｘ）∈Ｆｑ［ｘ］，ｆ（ｘ）は、次数２ｇ＋１のｍｏｎｉｃ多項式である。
【００７８】
超楕円曲線Ｃ上の点Ｐ＝（ｘ、ｙ）に対する共役点（ｏｐｐｏｓｉｔｅ  ｐｏｉｎｔ）は、−Ｐ＝（ｘ、ｙ＋ｈ（ｘ））として定義される。また、Ｐ＝−Ｐである点を分岐点（ｒａｍｉｆｉｃａｔｉｏｎ  ｐｏｉｎｔ）と呼ぶ。
【００７９】
超楕円曲線暗号の定義体の演算サイズ（ビット長）は楕円曲線暗号と同等の安全性を仮定した場合、楕円曲線の定義体の演算サイズに比べて１／ｇに小さくなることが知られている。演算サイズが小さいことは実装上メリットがあり、超楕円曲線暗号の利点の一つして挙げられる。
【００８０】
前述したように、超楕円曲線暗号では点の形式的和である因子（ｄｉｖｉｓｏｒ）をＤ１とし、スカラー倍算ｋＤ１で定義される因子をＤ２とすると、Ｄ２からｋを求める問題は超楕円曲線におけるヤコビ多様体上の離散対数問題として公開鍵暗号として用いることができる。
【００８１】
ここで、因子（ｄｉｖｉｓｏｒ）は有理点の形式和であり、以下の形式で表現することができる。
【数７】
2006227562.tif 000009
【００８２】
また、半被約因子（ｓｅｍｉ  ｒｅｄｕｃｅｄ  ｄｉｖｉｓｏｒ）は、以下の形式で表現することができる。
【数８】
2006227562.tif 000010
ただし、Ｐｉ＝（ｘｉ、ｙｉ）かつｉ≠ｊに対してＰｉ≠Ｐｊである。
【００８３】
また、ΣｍｉをＤのウェイト（ｗｅｉｇｈｔ）と呼ぶ。さらにウェイト（ｗｅｉｇｈｔ）が種数ｇ以下である半被約因子を被約因子（ｒｅｄｕｃｅｄ  ｄｉｖｉｓｏｒ）と呼ぶ。
【００８４】
超楕円曲線のヤコビ（Ｊａｃｏｂｉ）多様体上の任意の半被約因子Ｄは下記の多項式Ｕ、Ｖ∈Ｆｑ［ｘ］を用いてＤ＝（Ｕ、Ｖ）として表現できる。これをマンホード（Ｍｕｍｆｏｒｄ）表現と呼ぶ。
【数９】
2006227562.tif 000011
【００８５】
種数（ｇｅｎｕｓ）２の任意の被約因子Ｄはマンホード（Ｍｕｍｆｏｒｄ）表現を用いると、有限体Ｆｑ上の元を係数に持つ２次以下の多項式の組、すなわち、
（Ｕ、Ｖ）＝（ｘ２＋ｕ１ｘ＋ｕ０、ｖ１ｘ＋ｖ０）、または、
（Ｕ、Ｖ）＝（ｘ＋ｘ０、ｙ０）
として表現することができる。
また、零元は、
（Ｕ，Ｖ）＝（１，０）＝Ｏ
として表現される。
【００８６】
本発明は、楕円曲線暗号の１／２倍算を、超楕円曲線暗号に拡張し、２倍算よりも高速に計算できるアルゴリズム、曲線パラメータ、定義体を見つけ、超楕円曲線暗号において、２倍算よりも高速な１／２倍算を適用した演算処理を実現するものである。以下、本発明の実施例として、まず、前半において、以下に示す処理例１〜６の手法について説明する。
【００８７】
（処理例１：提案法Ａ１）種数２、標数２のランダムパラメータを持つような超楕円曲線において、因子Ｄの１／２倍算を計算する方法。
（処理例２：提案法Ｆ１）種数２，標数２のｈ（ｘ）＝ｘ２＋ｈ１ｘ＋ｈ０、ｆ４＝０をパラメータに持つような超楕円曲線において因子Ｄの１／２倍算を計算する方法。
（処理例３：提案法Ｂ１）種数２、標数２のｈ（ｘ）＝ｘ２＋ｘ＋ｈ０、ｆ４＝０をパラメータに持つような超楕円曲線において、因子Ｄの１／２倍算を計算する方法。
（処理例４：提案法Ｅ１）種数２、標数２のｈ（ｘ）＝ｘをパラメータに持つような超楕円曲線において、因子Ｄの１／２倍算を計算する方法。
（処理例５：提案法Ｃ１）種数２、標数２のランダムパラメータを持つような超楕円曲線、ｈ（ｘ）＝ｘ２＋ｈ１ｘ＋ｈ０，ｆ４＝０をパラメータに持つ超楕円曲線、およびｈ（ｘ）＝ｘ２＋ｘ＋ｈ０、ｆ４＝０、またはｈ（ｘ）＝ｘをパラメータに持つような超楕円曲線において、因子Ｄの１／２倍算を計算する際に、１／２倍したものの候補が２つ出てくる。２つの候補のうち、正しい値を選ぶ必要があるが、選ぶ際に、有限体のトレース、乗算、平方根を計算する必要がある。どちらが正しいかは、因子Ｄに依存する。そのため、因子Ｄが固定されている場合、事前に２つの候補のうち、どちらが正しいかをテーブルに保持し、正しい値を選ぶ際に、このテーブルを参照することにより、上記の余計な計算を省略する方法。
（処理例６：提案法Ｄ１）上記処理例１〜５に示す因子の１／２倍算の計算方法を用いて、因子のスカラー倍算を計算する方法。
【００８８】
さらに、後半において、上記処理例１〜３処理例５〜６をさらに改善した手法として、
（処理例７：提案法Ａ２）種数２、標数２のランダムパラメータを持つような超楕円曲線において、因子Ｄの１／２倍算を計算する方法。
（処理例８：提案法Ｆ２）種数２，標数２のｈ（ｘ）＝ｘ２＋ｈ１ｘ＋ｈ０、ｆ４＝０をパラメータに持つような超楕円曲線において因子Ｄの１／２倍算を計算する方法。
（処理例９：提案法Ｂ２）種数２、標数２のｈ（ｘ）＝ｘ２＋ｘ＋ｈ０、ｆ４＝０をパラメータに持つような超楕円曲線において、因子Ｄの１／２倍算を計算する方法。
（処理例１０：提案法Ｃ２）種数２、標数２のランダムパラメータを持つような超楕円曲線、ｈ（ｘ）＝ｘ２＋ｈ１ｘ＋ｈ０，ｆ４＝０をパラメータに持つ超楕円曲線、およびｈ（ｘ）＝ｘ２＋ｘ＋ｈ０、ｆ４＝０をパラメータに持つような超楕円曲線において、因子Ｄの１／２倍算を計算する際に、１／２倍したものの候補が２つ出てくる。２つの候補のうち、正しい値を選ぶ必要があるが、選ぶ際に、有限体のトレース、乗算、平方根を計算する必要がある。どちらが正しいかは、因子Ｄに依存する。そのため、因子Ｄが固定されている場合、事前に２つの候補のうち、どちらが正しいかをテーブルに保持し、正しい値を選ぶ際に、このテーブルを参照することにより、上記の余計な計算を省略する方法。
（処理例１１：提案法Ｄ２）上記処理例７〜１０に示す因子の１／２倍算の計算方法を用いて、因子のスカラー倍算を計算する方法。
【００８９】
以下、各処理例について、順次、その詳細を説明する。
【００９０】
［処理例１：提案法Ａ１］
処理例１（提案法Ａ１）は、種数２、標数２のランダムパラメータを持つような超楕円曲線において、因子Ｄの１／２倍算を計算する方法である。
【００９１】
また、これから扱う因子は位数がｒのものとする。つまり、扱う因子は分岐点を持たない。入力因子を、
Ｄ２＝（Ｕ２，Ｖ２）、
Ｕ２＝ｕ２２ｘ２＋ｕ２１ｘ＋ｕ２０、
Ｖ２＝ｖ２１ｘ＋ｖ２０、
ここで、Ｄ２のｗｅｉｇｈｔが２の場合はｕ２２＝１、
Ｄ２のｗｅｉｇｈｔが１の場合はｕ２２＝０、ｕ２１＝１、ｖ２１＝０とする。
分岐点を持たないため、１／２倍算として、
ＥｘＨａｒＤＢＬ１＋１→２、ＥｘＨａｒＤＢＬ２＋２→１、ＥｘＨａｒＤＢＬ２＋２→２、および、ＨａｒｌｅｙＤＢＬの４つの逆演算を考えればよい。ＨａｒｌｅｙＤＢＬ以外は例外ケースである。
【００９２】
ここでＥｘＨａｒＤＢＬ２＋２→１は入力因子のｗｅｉｇｈｔが２で、出力因子のｗｅｉｇｈｔが１の場合を計算する方法である。また、ＥｘＨａｒＤＢＬ２＋２→２  は入力因子のｗｅｉｇｈｔが２で、かつＵ２の１次の項の係数がｕ２１＝０を満たし、出力因子のｗｅｉｇｈｔが２の場合を計算する方法である。ただし、ＥｘＨａｒＤＢＬ２＋２→２はＨａｒｌｅｙＤＢＬで計算できるが、これの逆演算である１／２倍算は、例外ケースとなるため、ここでは、ＥｘＨａｒＤＢＬ２＋２→２を例外ケースとして扱う。
【００９３】
これら、ＥｘＨａｒＤＢＬ１＋１→２、ＥｘＨａｒＤＢＬ２＋２→１、ＥｘＨａｒＤＢＬ２＋２→２、および、ＨａｒｌｅｙＤＢＬに対応する１／２倍算をそれぞれ、ＥｘＨＥＣ＿ＨＬＶ２→１＋１、ＥｘＨＥＣ＿ＨＬＶ１→２＋２、ＥｘＨＥＣ＿ＨＬＶ２→２＋２、およびＨＥＣ＿ＨＬＶとする。
【００９４】
因子の１／２倍算を行なう場合、まず、入力因子により、図２に示す通りに場合分けを行なう。入力因子のｗｅｉｇｈｔが２で、かつＵ２の１次の項の係数がｕ２１≠０を満たす場合は、ＨＥＣ＿ＨＬＶで計算を行なう。また、入力因子のｗｅｉｇｈｔが２で、かつＵ２の項の係数がｕ２１＝０を満たす場合は、ＥｘＨＥＣ＿ＨＬＶ２→２＋２、もしくは、ＥｘＨＥＣ＿ＨＬＶ２→１＋１で計算を行なう。また、入力因子のｗｅｉｇｈｔが１の場合はＥｘＨＥＣ＿ＨＬＶ１→２＋２で計算を行う。ＨＥＣ＿ＨＬＶのアルゴリズムについて、図３を参照して説明する。
【００９５】
図３は、ＨＥＣ＿ＨＬＶのアルゴリズムを示すフローチャートである。
ステップＳ１０１において、入力を、
Ｄ２＝（Ｕ２，Ｖ２）、
Ｕ２＝ｘ２＋ｕ２１ｘ＋ｕ２０、
Ｖ２＝ｖ２１ｘ＋ｖ２０、
とする。
【００９６】
ステップＳ１０２において、ｋ１ｈ２＋ｋ１２ｕ２１＋１＝０の根、ｋ１，ｋ１'を求め、ステップＳ１０３において、ｃ１←ｆ３＋ｈ２ｖ２１＋ｕ２０＋（ｆ４＋ｕ２１）ｕ２１とおき、ステップＳ１０４において、ｋ１ｈ０＋ｋ０ｈ１＋ｋ０２ｕ２１＋ｃ１＝０が根を持つか否かを判定し、根を持たない場合は、ステップＳ１０５において、ｋ１←ｋ１'とし、根を持つ場合は、ステップＳ１０６に進み、ｋ１ｈ０＋ｋ０ｈ１＋ｋ０２ｕ２１＋ｃ１＝０の根、ｋ０，ｋ０'を求める。
【００９７】
次にステップＳ１０７に進み、ｕ１１を計算し、ステップＳ１０８において、ｘｈ２＋ｘ２ｕ１１＋１＝０が根を持つか否かを判定し、根を持たない場合は、ステップＳ１０９において、ｋ０←ｋ０'とし、根を持つ場合は、ステップＳ１１０に進み、ｕ１０を計算する。さらに、ステップＳ１１１において、ｖ１１，ｖ１０を計算し、ステップＳ１１２において、
Ｕ１←ｘ２＋ｕ１１ｘ＋ｕ１０
Ｖ１←ｖ１１ｘ＋ｖ１０
として、
ステップＳ１１３において、出力、
Ｄ１←（Ｕ１，Ｖ１）
を得る。
【００９８】
因子の１／２倍算は、因子の２倍算を行うアルゴリズム、すなわち、以下に示す［Ａｌｇｏｒｉｔｈｍ  １  ＨａｒｌｅｙＤＢＬ］
【数１０】
2006227562.tif 000012
【００９９】
上記アルゴリズム１［Ａｌｇｏｒｉｔｈｍ  １  ＨａｒｌｅｙＤＢＬ］を逆から計算することにより実現する。Ａｌｇｏｒｉｔｈｍ  １のステップ６では、
Ｖ１'＋ｈ＝（ｋ１ｘ＋ｋ０）Ｕ２＋Ｖ２
を満たすような多項式、
ｋ（ｘ）＝ｋ１ｘ＋ｋ０
が唯一存在する。
【０１００】
これを、
Ｖ１'＝ｈ＋（ｋ１ｘ＋ｋ０）Ｕ２＋Ｖ２
と式変形し、ステップ４に現れる式、
（ｆ＋ｈＶ１'＋Ｖ１'２）
に代入すると、ステップ４は、次のようになる。
Ｕ２'Ｕ１'＝ｆ＋ｈ（ｋＵ２＋Ｖ２）＋ｋ２Ｕ２２＋Ｖ２２・・・式（１）
上記式において、
（Ｕ２，Ｖ２）は分かっているので、式（１）から、ｋとＵ１'との関係式が得られる。
ここで、
Ｕ２'＝ｋ１２Ｕ２
であることに注意する。
【０１０１】
上記式（１）を展開して整理すると、次のようになる。
Ｕ１'＝ｘ４＋（（ｋ１ｈ２＋ｋ１２ｕ２１＋１）／ｋ１２）ｘ３＋（（ｋ１ｈ１＋ｋ０ｈ２＋ｋ１２ｕ２０＋ｋ０２＋ｃ２）／ｋ１２）ｘ２＋（（ｋ１ｈ０＋ｋ０ｈ１＋ｋ０２ｕ２１＋ｃ１）／ｋ１２）ｘ＋（ｋ０ｈ０＋ｋ０２ｕ２０＋ｃ０）／ｋ１２ 
・・・式（２）
ここで，
ｃ２＝ｆ４＋ｕ２１
ｃ１＝ｆ３＋ｈ２ｖ２１＋ｕ２０＋ｃ２ｕ２１
ｃ０＝ｆ２＋ｈ２ｖ２０＋ｈ１ｖ２１＋ｖ２１２＋ｃ２ｕ２０＋ｃ１ｕ２１
を満たす。
【０１０２】
また、ステップ１より、
Ｕ１'＝Ｕ１２、
つまり、
Ｕ１'＝ｘ４＋ｕ１１２ｘ２＋ｕ１０２
・・・式（３）
が成り立つ。
【０１０３】
上記式（２）、（３）の各係数を比較することにより、関係式を導き、この関係式を解くことにより、１／２倍算が計算できる。上記の処理手順を示すアルゴリズムを以下に、アルゴリズム４［Ａｌｇｏｒｉｔｈｍ  ４  Ｓｋｅｔｃｈ  ＨＥＣ＿ＨＬＶ］として示す。
【数１１】
2006227562.tif 000013
【０１０４】
具体的には，次の関係式が得られる。
【数１２】
2006227562.tif 000014
【０１０５】
これらの関係式から，正しいｋ０，ｋ１を計算する必要があるが、これは、次の補題によって計算できる。
［補題１］
ｈ（ｘ）を既約多項式であると仮定する。このとき、式（４），（５）を満たすｋ１は唯一である。また、式（５）は、正しいｋ１に対してのみ、根を持つ。また、Ａｌｇｏｒｉｔｈｍ４での１／２倍された因子Ｄ１を計算できるｋ０は唯一存在する。また、以下に示す式、
ｘｈ２＋ｘ２ｕ１１＋１＝０
は、正しいｋ０に対してのみ根を持つ。
【０１０６】
Ａｌｇｏｒｉｔｈｍ４に対して上記補題１を適用した。詳細な１／２倍算の計算方法を以下のアルゴリズム５［Ａｌｇｏｒｉｔｈｍ  ５  ＨＥＣ＿ＨＬＶ］として示す。
【数１３】
2006227562.tif 000015
【０１０７】
上記アルゴリズム５［Ａｌｇｏｒｉｔｈｍ５］では、ｋ１'，ｋ０'が正しい値（言い換えるとｋ１，ｋ０が正しくない値）である場合、計算量は、
３２Ｍ＋５Ｓ＋６Ｉ＋３ＳＲ＋２Ｈ＋２Ｔ
となる。ここでＭ，Ｓ，Ｉ，ＳＲ，Ｈ，Ｔはそれぞれ有限体上の乗算、２乗算、逆元演算、平方根演算、ハーフトレース（二次方程式の根を求める演算）、トレース（二次方程式の根があるか否かの判定）を意味する。このｋ１'，ｋ０'が正しい値である場合、計算量は最も多くなる。
【０１０８】
次にｋ１，ｋ０が正しい値（言い換えるとｋ１'，ｋ０'が正しくない値）である場合、計算量は最も少なくなり、ステップ２では２Ｍの計算量が削減でき、ステップ３では、２Ｍ＋１ＳＲの計算量が削減できる。つまり、この場合の計算量は、
２８Ｍ＋５Ｓ＋６Ｉ＋２ＳＲ＋２Ｈ＋２Ｔとなり、計算量は最も少なくなる。
【０１０９】
次にｋ１，ｋ０'が正しい値（言い換えるとｋ１'，ｋ０が正しくない値）である場合，ステップ３では、２Ｍ＋１ＳＲの計算量が削減できる。つまり、この場合の計算量は、
３０Ｍ＋５Ｓ＋６Ｉ＋２ＳＲ＋２Ｈ＋２Ｔとなる。
【０１１０】
最後にｋ１'，ｋ０が正しい値（言い換えるとｋ１，ｋ０'が正しくない値）である場合、ステップ２では，２Ｍの計算量が削減できる。つまり、この場合の計算量は、
３０Ｍ＋５Ｓ＋６Ｉ＋３ＳＲ＋２Ｈ＋２Ｔとなる。
【０１１１】
上記の４つの場合が発生する確率を、計算機実験によって確認した結果、ほぼ同じ割合で発生していることが確認された。これ以降は、上記４つの場合が生じる確率は等しいとする。上記４つの場合の計算量の平均をとると、
３０Ｍ＋５Ｓ＋６Ｉ＋２．５ＳＲ＋２Ｈ＋２Ｔ
となる。
【０１１２】
次に、例外ケースの、
ＥｘＨＥＣ＿ＨＬＶ２→１＋１、
ＥｘＨＥＣ＿ＨＬＶ１→２＋２、
ＥｘＨＥＣ＿ＨＬＶ２→２＋２、
について考える。これらが発生する確率は無視できる程度であるので、計算量の評価は行なわない。
【０１１３】
まず、ＥｘＨＥＣ＿ＨＬＶ２→１＋１、のアルゴリズムを、図４のフローを参照して説明する。
ＥｘＨＥＣ＿ＨＬＶ２→１＋１は、ＥｘＨａｒＤＢＬ１＋１→２を逆から計算することにより実現する。ＥｘＨａｒＤＢＬ１＋１→２の入力因子を、
Ｄ１＝（Ｕ１、Ｖ１）、Ｕ１＝ｘ＋ｕ１０、Ｖ１＝ｖ１０、
とすると、出力因子、
Ｄ２＝（Ｕ２、Ｖ２）＝２Ｄ１、Ｕ２＝ｘ２＋ｕ２０ｘ、Ｖ２＝ｖ２１ｘ＋ｖ２０、
は、次のように計算できる。
Ｕ２＝ｘ２＋ｕ２０＝（ｘ＋ｕ１０）２、
ｖ１２＝（ｕ１０４＋ｆ３ｕ１０２＋ｆ１＋ｈ１ｖ１０）／ｈ（ｕ１０），
ｖ２０＝ｖ１０＋ｖ２１ｕ１０
【０１１４】
この関係式を用いて、ＥｘＨＥＣ＿ＨＬＶ２→１＋１を計算する。
入力因子を、
Ｄ２＝（Ｕ２、Ｖ２）、Ｕ２＝ｘ２＋ｕ２０ｘ、Ｖ２＝ｖ２１ｘ＋ｖ２０、
とする（図４のフロー：ステップＳ２０１）と、
出力因子、
Ｄ１＝（Ｕ１、Ｖ１）＝［１／２］Ｄ２、Ｕ１＝ｘ＋ｕ１０、Ｖ１＝ｖ１０、
を求めるため、
ステップＳ２０２において、ｕ１０＝√ｕ２０、
ステップＳ２０３において、ｖ１０＝（ｖ２１ｈ（ｕ１０）＋ｕ１０４＋ｆ３ｕ１０２＋ｆ１）／ｈ１、
とし、ステップＳ２０４において、
Ｕ１＝ｘ＋ｕ１０、Ｖ１＝ｖ１０、
として、ステップＳ２０５において、
出力因子、
Ｄ１＝（Ｕ１、Ｖ１）
を得る。
【０１１５】
次に、ＥｘＨＥＣ＿ＨＬＶ２→２＋２、の処理手順について、図５のフローを参照して説明する。ステップＳ３０１において、入力因子を、
Ｄ２＝（Ｕ２、Ｖ２）、Ｕ２＝ｘ２＋ｕ２０、Ｖ２＝ｖ２１ｘ＋ｖ２０、
とする。
【０１１６】
ステップＳ３０２において、ｋ１ｈ２＋１＝０をｋ１に関して解き、ｋ１←１／ｈ２とする。
ステップＳ３０３において、
ｃ２←ｆ４
ｃ１←ｆ３＋ｈ２ｖ２１＋ｕ２０＋ｕ２１ｃ２
として、ステップＳ３０４において、
ｋ１ｈ０＋ｋ０ｈ１＋ｃ１＝０をｋ０に関して解き、ｋ０←（ｋ１ｈ０＋ｃ１）／ｈ１とする。
【０１１７】
次に、ステップＳ３０５において、ｕ１１を計算し、ステップＳ３０６において、
ｘｈ２＋ｘ２ｕ１１＋１＝０
が根を持つか否かを判定し、根を持たない場合は、ステップＳ３０７において、
Ｄ１←ＨＥＣ＿ＨＬＶ２→１（Ｄ２）
によって出力Ｄ１を決定（ステップＳ３０８）する。
【０１１８】
一方、
ｘｈ２＋ｘ２ｕ１１＋１＝０
が根を持つ場合は、ステップＳ３０９に進み、ｕ１０を計算し、さらに、ステップＳ３１０においてｖ１１，ｖ１０を計算し、ステップＳ３１１において、
Ｕ１←ｘ２＋ｕ１１ｘ＋ｕ１０
Ｖ１←ｖ１１ｘ＋ｖ１０
として、ステップＳ３１２において出力、
Ｄ１←（Ｕ１，Ｖ１）
を得る。
【０１１９】
この、ＥｘＨＥＣ＿ＨＬＶ２→２＋２、の処理は、具体的には、以下の手順で行なわれる。
入力因子を、
Ｄ２＝（Ｕ２、Ｖ２）、Ｕ２＝ｘ２＋ｕ２０、Ｖ２＝ｖ２１ｘ＋ｖ２０、
として、
Ｕ２＝ｘ２＋ｕ２０、
の場合、つまりＵ２の１次の項が０の場合、出力因子の候補は２つあり、それらを、
Ｄ１＝（ｘ＋√ｕ２０，Ｖ２（√ｕ２０））
Ｄ１'＝（ｘ２＋ｕ１１ｘ＋ｕ１０，ｖ１１ｘ＋ｖ１０）
と表す。
【０１２０】
Ｄ１が正しければ、ＥｘＨＥＣ＿ＨＬＶ２→１＋１で計算する。
Ｄ１'が正しければ、ＥｘＨＥＣ＿ＨＬＶ２→２＋２を用いて計算する。
どちらのアルゴリズムを用いるかは、次の手順で判定する。
１．Ｄ１'が正しいと仮定する。
２．ｕ１１を計算する。
３．ｘｈ２＋ｘ２ｕ１１＋１＝０のトレースＴｒ（ｈ２／ｕ１１２）を計算する。もしＴｒ（ｈ２／ｕ１１２）＝０ならばＤ１'が正しいので、ＥｘＨＥＣ＿ＨＬＶ２→２＋２を用いて計算する。そうではなくてＴｒ（ｈ２／ｕ１１２）＝１ならば、Ｄ１が正しく、ＥｘＨＥＣ＿ＨＬＶ２→１＋１を用いて計算する。
【０１２１】
ＥｘＨＥＣ＿ＨＬＶ２→２＋２の計算アルゴリズムを、アルゴリズム６［Ａｌｇｏｒｉｔｈｍ６］として以下に示す。
【数１４】
2006227562.tif 000016
次に、ＥｘＨＥＣ＿ＨＬＶ１→２＋２、の処理手順について、図６のフローを参照して説明する。ステップＳ４０１において、入力を、
Ｄ２＝（Ｕ２，Ｖ２）、
Ｕ２＝ｘ＋ｕ２０、
Ｖ２＝ｖ２０、
とする。
【０１２２】
ステップＳ４０２において、ｃ３←ｆ４＋ｕ２０として、ステップＳ４０３において、ｋ１ｈ２＋ｋ１２ｕ２１＋ｃ３＝０の根、ｋ１，ｋ１'を求め、ステップＳ４０４において、
ｃ２←ｆ３＋ｃ３ｕ２０、
ｃ１←ｆ２＋ｈ２ｖ２０＋ｃ２ｕ２０、
とおき、ステップＳ４０５において、ｋ１ｈ０＋ｋ０ｈ１＋ｋ０２＋ｃ１＝０が根を持つか否かを判定し、根を持たない場合は、ステップＳ４０６において、ｋ１←ｋ１'とした後、ステップＳ４０７に進み、根を持つ場合はそのままステップＳ４０７に進む。
【０１２３】
ステップＳ４０７では、ｋ１ｈ０＋ｋ０ｈ１＋ｋ０２＋ｃ１＝０の根、ｋ０，ｋ０'を求め、次にステップＳ４０８に進み、ｕ１１を計算し、ステップＳ４０９において、ｘｈ２＋ｘ２ｕ１１＋１＝０が根を持つか否かを判定し、根を持たない場合は、ステップＳ４１０においてｋ０←ｋ０'とした後ステップＳ４１１に進む。根を持つ場合は、そのままステップＳ４１１に進み、ｕ１０を計算する。さらに、ステップＳ４１２において、ｖ１１，ｖ１０を計算し、ステップＳ４１３において、
Ｕ１←ｘ２＋ｕ１１ｘ＋ｕ１０
Ｖ１←ｖ１１ｘ＋ｖ１０
として、
ステップＳ４１４において、出力、
Ｄ１←（Ｕ１，Ｖ１）
を得る。
【０１２４】
ＥｘＨＥＣ＿ＨＬＶ１→２＋２の計算手順は、ＨＥＣ＿ＨＬＶと似ているが、大きな違いは入力因子のｗｅｉｇｈｔである。そのため、ＥｘＨＥＣ＿ＨＬＶ１→２＋２のｆ＋ｈＶ１'＋Ｖ１'２は、５次のモニック多項式となり、
Ｕ１'←（ｆ＋ｈＶ１'＋Ｖ１'２）／Ｕ２、
はＨＥＣ＿ＨＬＶのようにｋ１２で割ることはない。ＥｘＨＥＣ＿ＨＬＶ１→２＋２の計算アルゴリズムを、アルゴリズム７［Ａｌｇｏｒｉｔｈｍ７］として以下に示す。
【数１５】
2006227562.tif 000017
【０１２５】
［処理例２：提案法Ｆ１］
処理例２（提案法Ｆ１）は、種数２，標数２のｈ（ｘ）＝ｘ２＋ｈ１ｘ＋ｈ０、ｆ４＝０をパラメータに持つような超楕円曲線において因子Ｄの１／２倍算を計算する方法である。
【０１２６】
Ａｌｇｏｒｉｔｈｍ５を良く見ると、ｈ（ｘ）の係数との乗算、ｈ（ｘ）の係数の逆元演算が多くある。つまり、ｈ（ｘ）の係数を工夫することにより、乗算および逆元演算の計算量を削減することができる。なお、文献（非特許文献１９：T. Lange. Efficient Doubling on Genus Two Curves over Binary Fields, SAC 2004, pre-proceedings, pp.189-202, 2004.）では、高速化のため、ｈ２＝１、ｆ４＝０を用いている。このパラメータを用いた場合のＨａｒｌｅｙＤＢＬの計算量は、２１Ｍ＋５Ｓ＋１Ｉである。
【０１２７】
ここで説明する処理例２（提案法Ｆ１）もこれに条件を合わせることにするが、補題１より、ｈ（ｘ）は既約多項式を仮定しているため、
ｈ（ｘ）＝ｘ２＋ｈ１ｘ＋ｈ０、
Ｔｒ（ｈ０／ｈ１２）＝１[0]
とする（二次方程式ａｘ２＋ｂｘ＋ｃ＝０が既約多項式であるための必要十分条件はＴｒ（ａｃ／ｂ２）＝１である）。この場合の計算法をアルゴリズム８［Ａｌｇｏｒｉｔｈｍ  ８］ＨＥＣ＿ＨＬＶ（ｈ２＝１、ｆ４＝０）に示す。
【０１２８】
【数１６】
2006227562.tif 000018
【０１２９】
また、逆元演算の回数を削除するため、モンゴメリトリックと呼ばれる手法を用いている。これは、例えば３個の有限体の元ａ、ｂ、ｃの逆元を求めたい場合、まず、３つの元の積を求め、これの逆元をｗ＝１／（ａ＊ｂ＊ｃ）などと求める。次に、ａの逆元を求める場合は、ｗ＊ｂ＊ｃを計算する。ｂ、ｃの逆元も同様にして、ｗ＊ａ＊ｃ、ｗ＊ａ＊ｂとそれぞれ計算する。
【０１３０】
通常、逆元演算は、乗算の数倍程度（後で示すが、ソフトウェア実装を行った結果、逆元演算は乗算の８倍程度）の計算量である。そのため、例えば３つの元の逆元を求める場合、素直に３回逆元演算を行えば、Ｉ＝８Ｍと仮定すると、２４Ｍの計算量となる。逆に、前述のモンゴメリトリックを用いた場合は、Ｉ＋８Ｍ＝１６Ｍとなり、３回逆元演算を行うよりも高速である。
【０１３１】
ここで説明している処理例２（提案法Ｆ１）では、このモンゴメリトリックを用いて、ｕ１１の逆元を求めている。ｕ１１の逆元は、次回の１／２倍算の入力として与える。そのため、Ａｌｇｏｒｉｔｈｍ８は、［１／２ｉ］Ｄを計算することができ、因子Ｄのスカラー倍算を行う場合、ｒｉｇｈｔ−ｔｏ−ｌｅｆｔ法、つまり、［１／２ｉ］Ｄを加算する方法に適用できる。１／２倍算を用いたスカラー倍算については、後ほど述べる。また、この計算量は次の通りである。
（ａ）ｋ１，ｋ０が正しい値である場合：２４Ｍ＋２Ｓ＋１Ｉ＋３ＳＲ＋２Ｈ＋２Ｔ
（ｂ）ｋ１，ｋ０'が正しい値である場合：２６Ｍ＋２Ｓ＋１Ｉ＋３ＳＲ＋２Ｈ＋２Ｔ
（ｃ）ｋ１'，ｋ０が正しい値である場合：２５Ｍ＋２Ｓ＋１Ｉ＋３ＳＲ＋２Ｈ＋２Ｔ
（ｄ）ｋ１'，ｋ０'が正しい値である場合：２７Ｍ＋２Ｓ＋１Ｉ＋３ＳＲ＋２Ｈ＋２Ｔ
上記（ａ）〜（ｄ）のすべてについて平均すると、２５．５Ｍ＋２Ｓ＋１Ｉ＋３ＳＲ＋２Ｈ＋２Ｔとなる。
【０１３２】
ＨａｒｌｅｙＤＢＬの計算量は、２１Ｍ＋５Ｓ＋１Ｉであった。ここで、文献［（非特許文献１５）  E.Knudsen. Elliptic Scalar Multiplication Using Point Halving. ASIACRYPTO '99, LNCS 1716, pp.135-149, Springer-Verlag, 1999.］によると、有限体が正規基底で定義されている場合、Ｓ（２乗算），ＳＲ（平方根演算），Ｈ（ハーフトレース（二次方程式の根を求める演算）），Ｔ（トレース（二次方程式の根があるか否かの判定））の計算量は無視することができ、Ｍ（乗算），Ｉ（逆元演算）の計算量のみ考慮すればよいことが知られている。そのため、正規基底を用いた場合、Ａｌｇｏｒｉｔｈｍ８はＨａｒｌｅｙＤＢＬよりも４．５Ｍ低速となる。
【０１３３】
また、有限体が多項式基底で定義されている場合、文献［（非特許文献１６）  K.Fong, D.Hankerson, J.Lopez, and A.Menezes. Field inversion and point halving revised. Technical Report CORR2003-18, http://www.cacr.math.uwaterloo.ca/techreports/2003/ corr2003-18.pdf１８］によると、通常ＳＲ（平方根演算），Ｈ（ハーフトレース（二次方程式の根を求める演算））の計算量は、Ｍ（乗算）との対比において、ＳＲ＝Ｈ＝０．５Ｍ程度であることが知られている。また、Ｔ（トレース（二次方程式の根があるか否かの判定））の計算量は無視できる。さらにＳ（２乗算）の計算量は、Ｍ（乗算）の数分の１程度であることが知られている。しかしながら、ＳＲの計算量は、多項式基底の選び方によっては、０．５Ｍよりも少なくなることも、同時に知られている。なお、例外ケースは、前述の処理例１（提案法Ａ１）の例外ケースに基いて計算できる。
【０１３４】
［処理例３（提案法Ｂ１）］
処理例３（提案法Ｂ１）は、種数２、標数２のｈ（ｘ）＝ｘ２＋ｘ＋ｈ０、ｆ４＝０をパラメータに持つような超楕円曲線において、因子Ｄの１／２倍算を計算する方法である。
【０１３５】
前述の処理例２（提案法Ｆ１）において説明したように、処理例１（提案法Ａ１）において説明した１／２倍算の計算アルゴリズム、すなわち、アルゴリズム５［Ａｌｇｏｒｉｔｈｍ  ５  ＨＥＣ＿ＨＬＶ］を良く見ると、ｈ（ｘ）の係数との乗算、ｈ（ｘ）の係数の逆元演算が多くある。つまり、ｈ（ｘ）の係数を工夫することにより、乗算および逆元演算の計算量を削減することができる。文献［J.Pelzl, T.Wollinger, and C.Paar. High Performance Arithmetic for Hyperelliptic Curve Cryptosystems of Genus Two. Cryptology ePrint Archive, 2003/212, IACR, 2003］では、高速化のために、ｈ２，ｈ１∈｛０，１｝，ｆ４＝０を用いた例を示している。
【０１３６】
このパラメータを用いた場合の［ＨａｒｌｅｙＤＢＬ］の計算量は、
１８Ｍ＋７Ｓ＋１Ｉ
である。
【０１３７】
処理例３（提案法Ｂ１）もこれに条件を合わせることにするが、前述した［補題１］より、ｈ（ｘ）は既約多項式を仮定しているため、
ｈ（ｘ）＝ｘ２＋ｘ＋ｈ０，
Ｔｒ（ｈ０）＝１
とする（二次方程式ａｘ２＋ｂｘ＋ｃ＝０が既約多項式であるための必要十分条件はＴｒ（ａｃ／ｂ２）＝１である）。
【０１３８】
この場合の計算法示すアルゴリズムをアルゴリズム１０［Ａｌｇｏｒｉｔｈｍ１０  ＨＥＣ＿ＨＬＶ（ｈ２＝ｈ１＝１，ｆ４＝０）］として以下に示す。
【数１７】
2006227562.tif 000019
【０１３９】
また、逆元演算の回数を削除するため、前述の処理例２（提案法Ｆ１）と同様、モンゴメリトリック手法を用いている。本処理例においてもモンゴメリトリックを用いて、ｕ１１の逆元を求めている。ｕ１１の逆元は、次回の１／２倍算の入力として与える。この処理例における計算量は次の通りである。
（ａ）ｋ１，ｋ０が正しい値である場合：１９Ｍ＋３Ｓ＋１Ｉ＋３ＳＲ＋２Ｈ＋２Ｔ
（ｂ）ｋ１，ｋ０'が正しい値である場合：２０Ｍ＋３Ｓ＋１Ｉ＋３ＳＲ＋２Ｈ＋２Ｔ
（ｃ）ｋ１'，ｋ０が正しい値である場合：１９Ｍ＋３Ｓ＋１Ｉ＋３ＳＲ＋２Ｈ＋２Ｔ
（ｄ）ｋ１'，ｋ０'が正しい値である場合：２０Ｍ＋３Ｓ＋１Ｉ＋３ＳＲ＋２Ｈ＋２Ｔ
【０１４０】
上記（ａ）〜（ｄ）のすべての場合について平均すると、
１９．５Ｍ＋３Ｓ＋１Ｉ＋３ＳＲ＋２Ｈ＋２Ｔ
となる。ＨａｒｌｅｙＤＢＬの計算量は、１８Ｍ＋７Ｓ＋１Ｉであった。ここで、前述したように、文献［E.Knudsen. Elliptic Scalar Multiplication Using Point Halving. ASIACRYPTO '99, LNCS 1716, pp.135-149, Springer-Verlag, 1999.］によると、有限体が正規基底で定義されている場合、Ｓ（２乗算），ＳＲ（平方根演算），Ｈ（ハーフトレース（二次方程式の根を求める演算）），Ｔ（トレース（二次方程式の根があるか否かの判定））の計算量は無視することができ、Ｍ（乗算），Ｉ（逆元演算）の計算量のみ考慮すればよいことが知られている。
【０１４１】
そのため、正規基底を用いた場合、上述したアルゴリズム１０［Ａｌｇｏｒｉｔｈｍ１０］は、従来のアルゴリズム［ＨａｒｌｅｙＤＢＬ］よりも、１．５Ｍ低速となる。また、有限体が多項式基底で定義されている場合、文献［K.Fong, D.Hankerson, J.Lopez, and A.Menezes. Field inversion and point halving revised. Technical Report CORR2003-18, http://www.cacr.math.uwaterloo.ca/techreports/2003/corr2003-18.pdf］によると、通常ＳＲ，Ｈの計算量は、ＳＲ＝Ｈ＝０．５Ｍ程度であることが知られている。また、Ｔの計算量は無視できる。さらにＳの計算量は、Ｍの数分の１程度であることが知られている。しかしながら、ＳＲの計算量は、多項式基底の選び方によっては、０．５Ｍよりも少なくなることも同時に知られている。
【０１４２】
さて、前述のアルゴリズム１０［Ａｌｇｏｒｉｔｈｍ１０］の曲線にさらに、ｈ０＝１の制約を設ける。前述のアルゴリズム１０［Ａｌｇｏｒｉｔｈｍ１０］は、ｈ０の乗算が１回あるので、ｈ０＝１とすることにより、１Ｍの削減ができ、上記（ａ）〜（ｄ）のすべての場合についての平均の計算量は、
１８．５Ｍ＋３Ｓ＋１Ｉ＋３ＳＲ＋２Ｈ＋２Ｔ
となる。一方、ＨａｒｌｅｙＤＢＬは、計算量は、
１５Ｍ＋７Ｓ＋１Ｉ
である。なお、例外ケースは、前述の処理例１（提案法Ａ１）の例外ケースに基いて計算できる。
【０１４３】
［処理例４（提案法Ｅ１）］
処理例４（提案法Ｅ１）は、種数２、標数２のｈ（ｘ）＝ｘをパラメータに持つような超楕円曲線において、因子Ｄの１／２倍算を計算する方法である。
【０１４４】
処理例３（提案法Ｂ１）と同様、アルゴリズム５（Ａｌｇｏｒｉｔｈｍ５）において、ｈ（ｘ）をｈ（ｘ）＝ｘとすることで，因子の１／２倍算に必要な有限体上の元の乗算および逆元演算の計算量を削減することができる。具体例としてｆ（ｘ）＝ｘ５＋ｆ１ｘ＋ｆ０の場合のアルゴリズムを、アルゴリズム１２（Ａｌｇｏｒｉｔｈｍ１２）として、以下に示す。
【数１８】
2006227562.tif 000020
【０１４５】
前述の処理例３（提案法Ｂ１）と同様に、上記のアルゴリズム１２（Ａｌｇｏｒｉｔｈｍ１２）について計算量を評価する。処理例３（提案法Ｂ１）と異なり、ｈ（ｘ）＝ｘのタイプの超楕円曲線の場合、ｋ１はｓｔｅｐ．１において一意に決まるので、ｋ０のみ選択するステップが存在する（Ｓｔｅｐ．３）。計算量の少ないＢｅｓｔ  ｃａｓｅはｓｔｅｐ．３のｉｆ文のＴｒａｃｅが０の場合であり、Ｗｏｒｓｔ  ｃａｓｅはＴｒａｃｅが１の場合である。どちらも等確率で起こるため、平均の計算量は、
１１．５Ｍ＋２Ｓ＋１Ｉ＋４．５ＳＲ＋１Ｈ＋１Ｔ
である。この計算量は前述の処理例３よりも少なく高速に演算できる。なお、例外ケースは、前述の処理例１（提案法Ａ１）の例外ケースに基いて計算できる。
【０１４６】
［処理例５（提案法Ｃ１）］
処理例５（提案法Ｃ１）は、種数２、標数２のランダムパラメータを持つような超楕円曲線、ｈ（ｘ）＝ｘ２＋ｈ１ｘ＋ｈ０，ｆ４＝０をパラメータに持つ超楕円曲線、およびｈ（ｘ）＝ｘ２＋ｘ＋ｈ０、ｆ４＝０をパラメータに持つような超楕円曲線において、因子Ｄの１／２倍算を計算する際に、１／２倍したものの候補が２つ出てくる。２つの候補のうち、正しい値を選ぶ必要があるが、選ぶ際に、有限体のトレース、乗算、平方根を計算する必要がある。どちらが正しいかは、因子Ｄに依存する。そのため、因子Ｄが固定されている場合、事前に２つの候補のうち、どちらが正しいかをテーブルに保持し、正しい値を選ぶ際に、このテーブルを参照することにより、上記の余計な計算を省略する方法である。
【０１４７】
ｋ１，ｋ１'（ｋ０，ｋ０'）のどちらが正しいかは、入力因子Ｄに依存している。したがって、Ｄが固定されている場合、例えばＥＣＤＨ型鍵交換のフェーズ１や、ＥＣＤＳＡ型署名生成、検証など、ベースポイントがあらかじめ決まっている場合、事前に、［１／２ｉ］Ｄを計算し、ｋ１，ｋ１'（ｋ０，ｋ０'）のどちらが正しい値であるかを、テーブルに記録しておく。
【０１４８】
例えば、ベースポイントの位数と同じビットサイズのテーブルをＴ１，Ｔ０と二つ用意し、これらを２進数表現したものを、
Ｔ１＝（ｔ１，ｒ−１，...，ｔ１，０）
Ｔ０＝（ｔ０，ｒ−１，...，ｔ０，０）
とする。
【０１４９】
［１／２ｉ］Ｄを求める際に、
ｋ１が正しければ、ｔ１，ｉ＝０、そうではなくて、ｋ１'が正しければｔ１，ｉ＝１
ｋ０が正しければｔ０，ｉ＝０、そうではなくて、ｋ０'が正しければｔ０，ｉ＝１などとテーブルに記録すれば、テーブルサイズは、わずかベースポイントの位数のサイズの２倍程度のビット列で済む。このテーブルを参照することにより、１／２倍算の計算量を削減することができる。
【０１５０】
この方法をアルゴリズム８［Ａｌｇｏｒｉｔｈｍ  ８］  ＨＥＣ＿ＨＬＶ（ｈ２＝１，ｆ４＝０）に適用したものを、アルゴリズム９［Ａｌｇｏｒｉｔｈｍ  ９］  ＨＥＣ＿ＨＬＶ（ｈ２＝１，ｆ４＝０，ｗｉｔｈ  ｔａｂｌｅ−ｌｏｏｋｕｐ）として示す。計算量は、２２Ｍ＋２Ｓ＋１Ｉ＋２ＳＲ＋２Ｈとなる。
【０１５１】
【数１９】
2006227562.tif 000021
【０１５２】
具体的に，この方法を上述のアルゴリズム１０［Ａｌｇｏｒｉｔｈｍ１０  ＨＥＣ＿ＨＬＶ  （ｈ２＝ｈ１＝１，ｆ４＝０）］に適用したアルゴリズムをアルゴリズム１１［Ａｌｇｏｒｉｔｈｍ１１  ＨＥＣ＿ＨＬＶ（ｈ２＝ｈ１＝１，ｆ４＝０，ｗｉｔｈ  ｔａｂｌｅ−ｌｏｏｋｕｐ）］として、以下に示す。
【０１５３】
【数２０】
2006227562.tif 000022
【０１５４】
上記アルゴリズム１１［Ａｌｇｏｒｉｔｈｍ１１  ＨＥＣ＿ＨＬＶ（ｈ２＝ｈ１＝１，ｆ４＝０，ｗｉｔｈ  ｔａｂｌｅ−ｌｏｏｋｕｐ）］における計算量は、
１８Ｍ＋３Ｓ＋１Ｉ＋２ＳＲ＋２Ｈとなり、さらにｈ０＝１とすることにより、１Ｍの削減ができ、この場合の計算量は、
１７Ｍ＋３Ｓ＋１Ｉ＋２ＳＲ＋２Ｈとなる。
【０１５５】
さらにこの方法を、前述のアルゴリズム１２［Ａｌｇｏｒｉｔｈｍ１２  ＨＥＣ＿ＨＬＶ（ｈ（ｘ）＝ｘ，ｆ（ｘ）＝ｘ５＋ｆ１ｘ＋ｆ０］に適用したアルゴリズムを、アルゴリズム１３［Ａｌｇｏｒｉｔｈｍ１３  ＨＥＣ＿ＨＬＶ（ｈ（ｘ）＝ｘ，ｆ（ｘ）＝ｘ５＋ｆ１ｘ＋ｆ０，  ｗｉｔｈ  ｔａｂｌｅ−ｌｏｏｋｕｐ）として、以下に示す。
【０１５６】
【数２１】
2006227562.tif 000023
【０１５７】
上記アルゴリズムにおける計算量は、
９．５Ｍ＋２Ｓ＋１Ｉ＋３．５ＳＲ＋１Ｈ
であり、さらに高速化が実現される。
【０１５８】
［処理例６（提案法Ｄ１）］
処理例６（提案法Ｄ１）は、上記処理例１〜５に示す因子の１／２倍算の計算方法を用いて、因子のスカラー倍算を計算する方法である。
【０１５９】
楕円曲線での有理点の１／２倍算を用いたスカラー倍算の計算方法は、文献［E.Knudsen. Elliptic Scalar Multiplication Using Point Halving. ASIACRYPTO '99, LNCS 1716, pp.135-149, Springer-Verlag, 1999.］にある。超楕円曲線の因子の１／２倍算を用いたスカラー倍算の計算方法は，この文献にあるスカラー倍算に基づいて実行される。ただし、［１／２ｉ］Ｄを計算し、加算していくｒｉｇｈｔ−ｔｏ−ｌｅｆｔ法を用いる。このアルゴリズムを、アルゴリズム１４［Ａｌｇｏｒｉｔｈｍ１４  Ｓｃａｌａｒ  Ｍｕｌｔｉｐｌｉｃａｔｉｏｎ］として以下に示す。
【数２２】
2006227562.tif 000024
【０１６０】
上記アルゴリズム１４［Ａｌｇｏｒｉｔｈｍ１４  Ｓｃａｌａｒ  Ｍｕｌｔｉｐｌｉｃａｔｉｏｎ］のステップ４に出てくるＨＥＣ＿ＨＬＶは、ランダムカーブを用いた前述のアルゴリズム５［Ａｌｇｏｒｉｔｈｍ５］のＨＥＣ＿ＨＬＶでも良いし、アルゴリズム８［Ａｌｇｏｒｉｔｈｍ  ８］の曲線パラメータにｈ２＝１，ｆ４＝０の制約を設けたＨＥＣ＿ＨＬＶでも良いし、アルゴリズム８［Ａｌｇｏｒｉｔｈｍ  ８］の曲線パラメータにテーブル参照法を適用したＨＥＣ＿ＨＬＶでも良いし、アルゴリズム１０［Ａｌｇｏｒｉｔｈｍ  １０］の曲線パラメータにｈ２＝ｈ１＝１，ｆ４＝０の制約を設けたＨＥＣ＿ＨＬＶでも良いし、アルゴリズム１０［Ａｌｇｏｒｉｔｈｍ  １０］の曲線パラメータにｈ２＝ｈ１＝ｈ０＝１，ｆ４＝０の制約を設けたＨＥＣ＿ＨＬＶでも良いし、アルゴリズム１０［Ａｌｇｏｒｉｔｈｍ  １０］に対してテーブル参照法を適用したＨＥＣ＿ＨＬＶでもよい。またアルゴリズム１２［Ａｌｇｏｒｉｔｈｍ  １２］の曲線パラメータのＨＥＣ＿ＨＬＶでも良いし、アルゴリズム１２［Ａｌｇｏｒｉｔｈｍ  １２］に対してテーブル参照法を適用したＨＥＣ＿ＨＬＶでもよい。
【０１６１】
［演算高速化の検証］
次に、上述した処理例１〜６を適用した演算における計算量を求め、演算の高速化について検証する。
【０１６２】
ＨＥＣ＿ＨＬＶ（ｈ２＝１，ｆ４＝０）では、計算量は、平均で、
２５．５Ｍ＋２Ｓ＋１Ｉ＋３ＳＲ＋２Ｈ＋２Ｔ
である。
【０１６３】
まず、有限体が正規基底で定義されている場合について考える。前述のとおり、正規基底を用いた場合、Ｍ，Ｉのみの計算量を考慮すればよい。文献［A.Menezes. Elliptic Curve Public Key Cryptosystems. Kluwer Academic Publishers, 1993.］によると、有限体をＦｑ，ｑ＝２ｎとした場合、逆元計算一回は、下式によって算出される回数、すなわち、
【数２３】
2006227562.tif 000025
【０１６４】
上記式によって算出される回数の乗算に匹敵する。ここで、ｗ（ｎ−１）はｎ−１を２進数で表示した際の１の個数を表す。例えば、ｎ＝８３，８９，１１３の場合、Ｉ＝８Ｍとなり、ｎ＝１０３の場合、Ｉ＝９Ｍとなる。
【０１６５】
ここで、Ｉ＝８Ｍを仮定すると、
ＨＥＣ＿ＨＬＶ（ｈ２＝１，ｆ４＝０）
の計算量は、
２５．５Ｍ＋１Ｉ＝３３．５Ｍとなる。
【０１６６】
一方、ＨａｒｌｅｙＤＢＬでは、
２１Ｍ＋１Ｉ＝２９Ｍとなり、ＨａｒｌｅｙＤＢＬの方がＨＥＣ＿ＨＬＶよりも１３％ほど高速となる。また、テーブル参照法を用いた場合では、
２２Ｍ＋１Ｉ＝３０Ｍ
となり、ＨａｒｌｅｙＤＢＬは、ＨＥＣ＿ＨＬＶよりも３％ほど高速となる。
【０１６７】
また、ＨＥＣ＿ＨＬＶ（ｈ２＝ｈ１＝１，ｆ４＝０）
の計算量は、平均で、
１９．５Ｍ＋３Ｓ＋１Ｉ＋３ＳＲ＋２Ｈ＋２Ｔ
となる。この場合は、
１９．５Ｍ＋１Ｉ＝２７．５Ｍ
となる。
【０１６８】
一方、ＨａｒｌｅｙＤＢＬでは、
１８Ｍ＋１Ｉ＝２６Ｍとなり、ＨａｒｌｅｙＤＢＬの方がＨＥＣ＿ＨＬＶよりも５％ほど高速となる。また、テーブル参照法を用いた場合では、
１８Ｍ＋１Ｉ＝２６Ｍ
となり、ＨａｒｌｅｙＤＢＬとＨＥＣ＿ＨＬＶは同等の計算量となる。
【０１６９】
また、ＨＥＣ＿ＨＬＶ（ｈ２＝ｈ１＝ｈ０＝１，ｆ４＝０）
の計算量は、平均で、
１８．５Ｍ＋３Ｓ＋１Ｉ＋３ＳＲ＋２Ｈ＋２Ｔ
となる。この場合は、
１８．５Ｍ＋１Ｉ＝２６．５Ｍ
となる。
【０１７０】
一方、ＨａｒｌｅｙＤＢＬでは、
１５Ｍ＋１Ｉ＝２３Ｍとなり、ＨａｒｌｅｙＤＢＬの方がＨＥＣ＿ＨＬＶよりも１３％ほど高速となる。また、テーブル参照法を用いた場合では、
１７Ｍ＋１Ｉ＝２５Ｍ
となり、ＨａｒｌｅｙＤＢＬの方がＨＥＣ＿ＨＬＶよりも８％ほど高速となる。
【０１７１】
また、多項式基底の場合をソフトウェア実装を行い、速度の比較を行った。
ＣＰＵは  ＰｅｎｔｉｕｍＩＩ  ３００ＭＨｚ、
ＯＳはＲｅｄＨａｔ７．３、
コンパイラはｇｃｃ２．９６
の環境でソフトウェア実装を行った。
【０１７２】
Ｍ（乗算）、Ｓ（２乗算）は、文献［D.Hankerson, J.Hernandez, and A.Menezes. Software Implementation of Elliptic Curve Cryptography over Binary Fields. CHES 2000, LNCS 1965, pp.1-24, 2000.，Ａｌｇｏｒｉｔｈｍ４．６，４．７］、Ｉ（逆元演算）は、文献［S.Shantz. From Euclid's GCD to Montgomery Multiplication to the Great Divide. TR-2001-95, Sun Microsystems, Inc., 2001.］、ＳＲ（平方根演算）、Ｔ（トレース（二次方程式の根があるか否かの判定））は、文献［K.Fong, D.Hankerson, J.Lopez, and A.Menezes. Field inversion and point halving revised. Technical Report CORR2003-18, http://www.cacr.math.uwaterloo.ca/techreports/2003/corr2003-18.pdf］、Ｈ（ハーフトレース（二次方程式の根を求める演算））は、文献［K.Fong, D.Hankerson, J.Lopez, and A.Menezes. Field inversion and point halving revised. Technical Report CORR2003-18, http://www.cacr.math.uwaterloo.ca/techreports/2003/corr2003-18.pdf  Ａｌｇｏｒｉｔｈｍ  ４．７］  に従った。
【０１７３】
ｎ＝８３，８９，１１３の３つの有限体に対して，Ｍ，Ｓ，Ｉ，ＳＲ，Ｈ，Ｔを実装し、Ｍとの比を求めた。ここで、
ｎ＝８３の既約多項式は、
ｚ８３＋ｚ７＋ｚ４＋ｚ２＋１＝０
ｎ＝８９の既約多項式は、
ｚ８９＋ｚ３８＋１＝０
ｎ＝１１３の既約多項式は、
ｚ１１３＋ｚ９＋１＝０
を用いた。
計算量は次の通りとなった。
ｎ＝８３：Ｓ／Ｍ＝０．１２，Ｉ／Ｍ＝７．９６，ＳＲ／Ｍ＝０．５７，Ｈ／Ｍ＝０．５８
ｎ＝８９：Ｓ／Ｍ＝０．０５，Ｉ／Ｍ＝８．７４，ＳＲ／Ｍ＝０．１４，Ｈ／Ｍ＝０．６１
ｎ＝１１３：Ｓ／Ｍ＝０．０６，Ｉ／Ｍ＝８．５６，ＳＲ／Ｍ＝０．１０，Ｈ／Ｍ＝０．５０
【０１７４】
これらを、ＨａｒｌｅｙＤＢＬの計算量２１Ｍ＋５Ｓ＋１Ｉに適用すると次のようになる。
ｎ＝８３：ＨａｒｌｅｙＤＢＬ２９．５６Ｍ
ｎ＝８９：ＨａｒｌｅｙＤＢＬ２９．９９Ｍ
ｎ＝１１３：ＨａｒｌｅｙＤＢＬ２９．８６Ｍ
【０１７５】
これらを、ＨＥＣ＿ＨＬＶ（ｈ２＝１，ｆ４＝０）の計算量、２５．５Ｍ＋２Ｓ＋１Ｉ＋３ＳＲ＋２Ｈ＋２Ｔに適用すると次のようになる。
ｎ＝８３：ＨＥＣ＿ＨＬＶ（ｈ２＝１，ｆ４＝０）３６．５７Ｍ
ｎ＝８９：ＨＥＣ＿ＨＬＶ（ｈ２＝１，ｆ４＝０）３５．９８Ｍ
ｎ＝１１３：ＨＥＣ＿ＨＬＶ（ｈ２＝１，ｆ４＝０）３５．４８Ｍ
【０１７６】
この場合、ｎ＝８３，８９，１１３で、それぞれＨａｒｌｅｙＤＢＬの方がＨＥＣ＿ＨＬＶよりも２０％、１７％、１６％程度、高速である。
【０１７７】
さらに、ＨＥＣ＿ＨＬＶ（ｈ２＝１，ｆ４＝０）にテーブル参照法を適用した場合の計算量、２２Ｍ＋２Ｓ＋１Ｉ＋２ＳＲ＋２Ｈに適用すると次のようになる。
ｎ＝８３：ＨＥＣ＿ＨＬＶ（ｈ２＝１，ｆ４＝０  ｗｉｔｈ  ｔａｂｌｅ−ｌｏｏｋｕｐ）３２．５Ｍ
ｎ＝８９：ＨＥＣ＿ＨＬＶ（ｈ２＝１，ｆ４＝０  ｗｉｔｈ  ｔａｂｌｅ−ｌｏｏｋｕｐ）３２．３４Ｍ
ｎ＝１１３：ＨＥＣ＿ＨＬＶ（ｈ２＝１，ｆ４＝０  ｗｉｔｈ  ｔａｂｌｅ−ｌｏｏｋｕｐ）３１．８８Ｍ
【０１７８】
この場合、ｎ＝８３，８９，１１３で、それぞれＨａｒｌｅｙＤＢＬの方がＨＥＣ＿ＨＬＶよりも９％、７％、６％程度、高速である。
【０１７９】
また、ｈ２＝ｈ１＝１，ｆ４＝０の場合は、次の通りとなる。
ＨａｒｌｅｙＤＢＬの計算量１８Ｍ＋７Ｓ＋１Ｉに適用すると次のようになる。
ｎ＝８３：ＨａｒｌｅｙＤＢＬ２７．４Ｍ
ｎ＝８９：ＨａｒｌｅｙＤＢＬ２７．０９Ｍ
ｎ＝１１３：ＨａｒｌｅｙＤＢＬ２６．９８Ｍ
【０１８０】
次に、ＨＥＣ＿ＨＬＶ（ｈ２＝ｈ１＝１，ｆ４＝０）の計算量、１９．５Ｍ＋３Ｓ＋１Ｉ＋３ＳＲ＋２Ｈ＋２Ｔに適用すると次のようになる。
ｎ＝８３：ＨＥＣ＿ＨＬＶ（ｈ２＝ｈ１＝１，ｆ４＝０）３０．６９Ｍ
ｎ＝８９：ＨＥＣ＿ＨＬＶ（ｈ２＝ｈ１＝１，ｆ４＝０）３０．０３Ｍ
ｎ＝１１３：ＨＥＣ＿ＨＬＶ（ｈ２＝ｈ１＝１，ｆ４＝０）２９．５４Ｍ
【０１８１】
この場合、ｎ＝８３，８９，１１３で、それぞれＨａｒｌｅｙＤＢＬの方がＨＥＣ＿ＨＬＶよりも１３％、１２％、９％程度、高速である。
【０１８２】
さらに、ＨＥＣ＿ＨＬＶ（ｈ２＝ｈ１＝１，ｆ４＝０）にテーブル参照法を適用した場合の計算量、１８Ｍ＋３Ｓ＋１Ｉ＋２ＳＲ＋２Ｈに適用すると次のようになる。
ｎ＝８３：ＨＥＣ＿ＨＬＶ（ｈ２＝ｈ１＝１，ｆ４＝０  ｗｉｔｈ  ｔａｂｌｅ−ｌｏｏｋｕｐ）２８．６２Ｍ
ｎ＝８９：ＨＥＣ＿ＨＬＶ（ｈ２＝ｈ１＝１，ｆ４＝０  ｗｉｔｈ  ｔａｂｌｅ−ｌｏｏｋｕｐ）２８．３９Ｍ
ｎ＝１１３：ＨＥＣ＿ＨＬＶ（ｈ２＝ｈ１＝１，ｆ４＝０  ｗｉｔｈ  ｔａｂｌｅ−ｌｏｏｋｕｐ）２７．９４Ｍ
【０１８３】
この場合、ｎ＝８３，８９，１１３で、それぞれＨａｒｌｅｙＤＢＬの方がＨＥＣ＿ＨＬＶよりも４％、５％、３％程度、高速である。
【０１８４】
また、ｈ２＝ｈ１＝ｈ０＝１，ｆ４＝０の場合は、次の通りとなる。
ＨａｒｌｅｙＤＢＬの計算量１５Ｍ＋７Ｓ＋１Ｉに適用すると次のようになる。
ｎ＝８３：ＨａｒｌｅｙＤＢＬ２３．８Ｍ
ｎ＝８９：ＨａｒｌｅｙＤＢＬ２４．０９Ｍ
ｎ＝１１３：ＨａｒｌｅｙＤＢＬ２３．９８Ｍ
【０１８５】
次に、ＨＥＣ＿ＨＬＶ（ｈ２＝ｈ１＝ｈ０＝１，ｆ４＝０）の計算量、１８．５Ｍ＋３Ｓ＋１Ｉ＋３ＳＲ＋２Ｈ＋２Ｔに適用すると次のようになる。
ｎ＝８３：ＨＥＣ＿ＨＬＶ（ｈ２＝ｈ１＝ｈ０＝１，ｆ４＝０）２９．６９Ｍ
ｎ＝８９：ＨＥＣ＿ＨＬＶ（ｈ２＝ｈ１＝ｈ０＝１，ｆ４＝０）２９．０３Ｍ
ｎ＝１１３：ＨＥＣ＿ＨＬＶ（ｈ２＝ｈ１＝ｈ０＝１，ｆ４＝０）２８．５４Ｍ
【０１８６】
この場合、ｎ＝８３，８９，１１３で、それぞれＨａｒｌｅｙＤＢＬの方がＨＥＣ＿ＨＬＶよりも２０％、１７％、１６％程度、高速である。
【０１８７】
さらに、ＨＥＣ＿ＨＬＶ（ｈ２＝ｈ１＝ｈ０＝１，ｆ４＝０）にテーブル参照法を適用した場合の計算量、１７Ｍ＋３Ｓ＋１Ｉ＋２ＳＲ＋２Ｈに適用すると次のようになる。
ｎ＝８３：ＨＥＣ＿ＨＬＶ（ｈ２＝ｈ１＝ｈ０＝１，ｆ４＝０  ｗｉｔｈ  ｔａｂｌｅ−ｌｏｏｋｕｐ）２７．６２Ｍ
ｎ＝８９：ＨＥＣ＿ＨＬＶ（ｈ２＝ｈ１＝ｈ０＝１，ｆ４＝０  ｗｉｔｈ  ｔａｂｌｅ−ｌｏｏｋｕｐ）２７．３９Ｍ
ｎ＝１１３：ＨＥＣ＿ＨＬＶ（ｈ２＝ｈ１＝ｈ０＝１，ｆ４＝０  ｗｉｔｈ  ｔａｂｌｅ−ｌｏｏｋｕｐ）２６．９４Ｍ
【０１８８】
この場合、ｎ＝８３，８９，１１３で、それぞれＨａｒｌｅｙＤＢＬの方がＨＥＣ＿ＨＬＶよりも１４％、１２％、１１％程度、高速である。
【０１８９】
次に、上述のアルゴリズム１２［Ａｌｇｏｒｉｔｈｍ１２］、すなわち、［Ａｌｇｏｒｉｔｈｍ１２  ＨＥＣ＿ＨＬＶ（ｈ（ｘ）＝ｘ，ｆ（ｘ）＝ｘ５＋ｆ１ｘ＋ｆ０）］と、テーブル参照法を用いたアルゴリズム１３［Ａｌｇｏｒｉｔｈｍ１３］、すなわち、［Ａｌｇｏｒｉｔｈｍ１３  ＨＥＣ＿ＨＬＶ（ｈ（ｘ）＝ｘ，ｆ（ｘ）＝ｘ５＋ｆ１ｘ＋ｆ０，ｗｉｔｈ  ｔａｂｌｅ−ｌｏｏｋｕｐ）］について、ＨａｒｌｅｙＤＢＬとの比較を行う。
【０１９０】
［Ａｌｇｏｒｉｔｈｍ１２  ＨＥＣ＿ＨＬＶ（ｈ（ｘ）＝ｘ，ｆ（ｘ）＝ｘ５＋ｆ１ｘ＋ｆ０）］の計算量は、１１．５Ｍ＋２Ｓ＋１Ｉ＋４．５ＳＲ＋１Ｈ＋１Ｔ、
［Ａｌｇｏｒｉｔｈｍ１３  ＨＥＣ＿ＨＬＶ（ｈ（ｘ）＝ｘ，ｆ（ｘ）＝ｘ５＋ｆ１ｘ＋ｆ０，ｗｉｔｈ  ｔａｂｌｅ−ｌｏｏｋｕｐ）］の計算量は、９．５Ｍ＋２Ｓ＋１Ｉ＋３．５ＳＲ＋１Ｈである。ＨａｒｌｅｙＤＢＬの計算量は、文献［（非特許文献１９：T. Lange. Efficient Doubling on Genus Two Curves over Binary Fields, SAC 2004, pre-proceedings, pp.189-202, 2004.）］によると、６Ｍ＋５Ｓ＋１Ｉである。前述のように、有限体が正規基底で定義されている場合、Ｓ（２乗算），ＳＲ（平方根演算），Ｈ（ハーフトレース（二次方程式の根を求める演算）），Ｔ（トレース（二次方程式の根があるか否かの判定））の計算量は無視することができ、Ｍ（乗算），Ｉ（逆元演算）の計算量のみ考慮すればよい。
【０１９１】
従って、アルゴリズム１２［Ａｌｇｏｒｉｔｈｍ１２  ＨＥＣ＿ＨＬＶ（ｈ（ｘ）＝ｘ，ｆ（ｘ）＝ｘ５＋ｆ１ｘ＋ｆ０）］の計算量は、
１１．５Ｍ＋２Ｓ＋１Ｉ＋４．５ＳＲ＋１Ｈ＋１Ｔ、
＝１１．５Ｍ＋１Ｉ
となり、
アルゴリズム１３［Ａｌｇｏｒｉｔｈｍ１３  ＨＥＣ＿ＨＬＶ（ｈ（ｘ）＝ｘ，ｆ（ｘ）＝ｘ５＋ｆ１ｘ＋ｆ０，ｗｉｔｈ  ｔａｂｌｅ−ｌｏｏｋｕｐ）］の計算量は、
９．５Ｍ＋２Ｓ＋１Ｉ＋３．５ＳＲ＋１Ｈ
＝９．５Ｍ＋１Ｉ
となる。
【０１９２】
ＨａｒｌｅｙＤＢＬの計算量は、
６Ｍ＋１Ｉ
となる。従って、ＨａｒｌｅｙＤＢＬの方がＨＥＣ＿ＨＬＶよりも高速となる。
【０１９３】
以上、説明したように、曲線パラメータｈ２＝ｈ１＝１、ｆ４＝０の場合のＨＥＣ＿ＨＬＶにテーブル参照法を適用した場合の計算量１８Ｍ＋３Ｓ＋１Ｉ＋２ＳＲ＋２Ｈが、ＨａｒｌｅｙＤＢＬの計算量１８Ｍ＋７Ｓ＋１Ｉにほぼ等しく、同等の条件でＨＥＣ＿ＨＬＶとＨａｒｌｅｙＤＢＬとで比較した場合、最も高速なアルゴリズムである。
【０１９４】
次に、アルゴリズム１４［Ａｌｇｏｒｉｔｈｍ  １４  ｓｃａｌａｒ  ｍｕｌｔｉｐｌｉｃａｔｉｏｎ］を用いたスカラー倍算の計算量を考える。曲線パラメータは、同等な条件でＨａｒｌｅｙＤＢＬと比較して、最も高速なｈ２＝ｈ１＝１、ｆ４＝０を用い、さらに、ＨＥＣ＿ＨＶＬにはテーブル参照法を用いた方法でスカラー倍算の計算量を考える。
【０１９５】
アルゴリズム１４におけるステップ１、２がスカラー倍算全体に占める割合は非常に小さいため、これらの計算量は無視する。ここで、正規基底および多項式基底ともにｎ＝８３、８９、１１３の場合で計算量を考えてみる。また、ベースポイントの位数は、ｎ＝８３、８９、１１３に対してそれぞれ１６５ビット、１７７ビット、２２５ビットと仮定する。また、ステップ４の繰り返し部分では、ベースポイントの位数のビット数だけ繰り返す。因子の加算は文献［T.Lange, Efficient arithmetic on genus 2 hyperelliptic curves over finite fields via explicit formulae. Cryptology ePrint Archive, 2002/121, IACR, 2002］を用いる。ただし、曲線パラメータはｈ２＝ｈ１＝１、ｆ４＝０とする。この場合の因子の加算に必要な計算量は２１Ｍ＋３Ｓ＋１Ｉである。スカラー値は２進数で表現した場合、０、１が同程度の割合で現れると仮定する。計算量は、（（加算の計算量）／２＋（１／２倍算ｏｒ２倍残の計算量））ｘ（ベースポイントの位数のビット数）で計算する。まずは、正規基底の場合から見てみる。Ｉ＝８Ｍと仮定する。
【０１９６】
ｈ２＝ｈ１＝１，ｆ４＝０の場合、
ｎ＝８３：加算・２倍算：６６８２．５Ｍ
ｎ＝８９：加算・２倍算：７１６８．５Ｍ
ｎ＝１１３：加算・２倍算：９１１２．５Ｍ
【０１９７】
ｈ２＝ｈ１＝１，ｆ４＝０の場合、
ｎ＝８３：加算・１／２倍算：６９３０Ｍ
ｎ＝８９：加算・１／２倍算：７４３４Ｍ
ｎ＝１１３：加算・１／２倍算：９４５０Ｍ
【０１９８】
ｈ２＝ｈ１＝１，ｆ４＝０＋テーブル参照法の場合（加算・２倍算の場合と等しい計算量）
ｎ＝８３：加算・２倍算：６６８２．５Ｍ
ｎ＝８９：加算・２倍算：７１６８．５Ｍ
ｎ＝１１３：加算・２倍算：９１１２．５Ｍ
【０１９９】
次に、多項式の場合を考える。
ｈ２＝ｈ１＝１，ｆ４＝０の場合、
ｎ＝８３：加算・２倍算：６９１３．５Ｍ
ｎ＝８９：加算・２倍算：７３６１．３Ｍ
ｎ＝１１３：加算・２倍算：９３３３Ｍ
【０２００】
ｈ２＝ｈ１＝１，ｆ４＝０の場合、
ｎ＝８３：加算・１／２倍算：７４５６．３５Ｍ
ｎ＝８９：加算・１／２倍算：７８８１．８Ｍ
ｎ＝１１３：加算・１／２倍算：９９０９Ｍ
【０２０１】
ｈ２＝ｈ１＝１，ｆ４＝０＋テーブル参照法の場合（加算・２倍算の場合と等しい計算量）
ｎ＝８３：加算・２倍算：７１１４．８Ｍ
ｎ＝８９：加算・２倍算：７５９１．５３Ｍ
ｎ＝１１３：加算・２倍算：９５４０Ｍ
【０２０２】
以上、説明したように、上述した本発明の処理例によれば、楕円曲線暗号の１／２倍算を、超楕円曲線暗号に拡張し、高速演算が実現される。超楕円曲線上の因子の演算を使う暗号処理演算において、処理の重い演算は因子のスカラー倍算である。上述した本発明の処理によりスカラー倍算を従来と同程度の速度で演算することができ、その結果、１／２倍算を用いても超楕円曲線暗号の処理を従来と同程度の速度で処理することがきる。
【０２０３】
次に、上述した各種処理例、すなわち、
（処理例１：提案法Ａ１）
（処理例２：提案法Ｆ１）
（処理例３：提案法Ｂ１）
（処理例５：提案法Ｃ１）
（処理例６：提案法Ｄ１）
をさらに高速化した処理例７〜１１、すなわち、以下の処理例について説明する。
（処理例７：提案法Ａ２）：上記処理例（処理例１：提案法Ａ１）のさらなる高速化手法であり、種数２、標数２のランダムパラメータを持つような超楕円曲線において、因子Ｄの１／２倍算を計算する方法。
（処理例８：提案法Ｆ２）：上記処理例（処理例２：提案法Ｆ１）のさらなる高速化手法であり、種数２，標数２のｈ（ｘ）＝ｘ２＋ｈ１ｘ＋ｈ０、ｆ４＝０をパラメータに持つような超楕円曲線において因子Ｄの１／２倍算を計算する方法。
（処理例９：提案法Ｂ２）：上記処理例（処理例３：提案法Ｂ１）のさらなる高速化手法であり、種数２、標数２のｈ（ｘ）＝ｘ２＋ｘ＋ｈ０、ｆ４＝０をパラメータに持つような超楕円曲線において、因子Ｄの１／２倍算を計算する方法。
（処理例１０：提案法Ｃ２）：上記処理例（処理例５：提案法Ｃ１）のさらなる高速化手法であり、種数２、標数２のランダムパラメータを持つような超楕円曲線、ｈ（ｘ）＝ｘ２＋ｈ１ｘ＋ｈ０，ｆ４＝０をパラメータに持つ超楕円曲線、およびｈ（ｘ）＝ｘ２＋ｘ＋ｈ０、ｆ４＝０をパラメータに持つような超楕円曲線において、因子Ｄの１／２倍算を計算する際に、１／２倍したものの候補が２つ出てくる。２つの候補のうち、正しい値を選ぶ必要があるが、選ぶ際に、有限体のトレース、乗算、平方根を計算する必要がある。どちらが正しいかは、因子Ｄに依存する。そのため、因子Ｄが固定されている場合、事前に２つの候補のうち、どちらが正しいかをテーブルに保持し、正しい値を選ぶ際に、このテーブルを参照することにより、上記の余計な計算を省略する方法。
（処理例１１：提案法Ｄ２）：上記処理例（処理例６：提案法Ｄ１）のさらなる高速化手法であり、上記処理例７〜１０に示す因子の１／２倍算の計算方法を用いて、因子のスカラー倍算を計算する方法。
【０２０４】
以下、各処理例について、順次、その詳細を説明する。
【０２０５】
［処理例７：提案法Ａ２］
処理例７（提案法Ａ２）は、前述した処理例（処理例１：提案法Ａ１）のさらなる高速化手法であり、種数２、標数２のランダムパラメータを持つような超楕円曲線において、因子Ｄの１／２倍算を計算する方法である。
【０２０６】
以下の各処理例においても、扱う因子は位数がｒのものとする。つまり、扱う因子は分岐点を持たない。入力因子を、
Ｄ２＝（Ｕ２，Ｖ２）、
Ｕ２＝ｕ２２ｘ２＋ｕ２１ｘ＋ｕ２０、
Ｖ２＝ｖ２１ｘ＋ｖ２０、
ここで、Ｄ２のｗｅｉｇｈｔが２の場合はｕ２２＝１、
Ｄ２のｗｅｉｇｈｔが１の場合はｕ２２＝０、ｕ２１＝１、ｖ２１＝０とする。
分岐点を持たないため、１／２倍算として、
ＥｘＨａｒＤＢＬ１＋１→２、ＥｘＨａｒＤＢＬ２＋２→１、ＥｘＨａｒＤＢＬ２＋２→２、および、ＨａｒｌｅｙＤＢＬの４つの逆演算を考えればよい。ＨａｒｌｅｙＤＢＬ以外は例外ケースである。
【０２０７】
ここでＥｘＨａｒＤＢＬ２＋２→１は入力因子のｗｅｉｇｈｔが２で、出力因子のｗｅｉｇｈｔが１の場合を計算する方法である。また、ＥｘＨａｒＤＢＬ２＋２→２  は入力因子のｗｅｉｇｈｔが２で、かつＵ２の１次の項の係数がｕ２１＝０を満たし、出力因子のｗｅｉｇｈｔが２の場合を計算する方法である。ただし、ＥｘＨａｒＤＢＬ２＋２→２はＨａｒｌｅｙＤＢＬで計算できるが、これの逆演算である１／２倍算は、例外ケースとなるため、ここでは、ＥｘＨａｒＤＢＬ２＋２→２を例外ケースとして扱う。
【０２０８】
これら、ＥｘＨａｒＤＢＬ１＋１→２、ＥｘＨａｒＤＢＬ２＋２→１、ＥｘＨａｒＤＢＬ２＋２→２、および、ＨａｒｌｅｙＤＢＬに対応する１／２倍算をそれぞれ、ＥｘＨＥＣ＿ＨＬＶ２→１＋１、ＥｘＨＥＣ＿ＨＬＶ１→２＋２、ＥｘＨＥＣ＿ＨＬＶ２→２＋２、およびＨＥＣ＿ＨＬＶとする。
【０２０９】
因子の１／２倍算を行なう場合、先に（処理例１：提案法Ａ１）において説明したように、まず、入力因子により、図２に示す通りに場合分けを行なう。入力因子のｗｅｉｇｈｔが２で、かつＵ２の１次の項の係数がｕ２１≠０を満たす場合は、ＨＥＣ＿ＨＬＶで計算を行なう。また、入力因子のｗｅｉｇｈｔが２で、かつＵ２の項の係数がｕ２１＝０を満たす場合は、ＥｘＨＥＣ＿ＨＬＶ２→２＋２、もしくは、ＥｘＨＥＣ＿ＨＬＶ２→１＋１で計算を行なう。また、入力因子のｗｅｉｇｈｔが１の場合はＥｘＨＥＣ＿ＨＬＶ１→２＋２で計算を行う。ＨＥＣ＿ＨＬＶのアルゴリズムについては、先に図３を参照して説明した通りである。
【０２１０】
因子の１／２倍算は、因子の２倍算を行うアルゴリズム、すなわち、以下に示す［Ａｌｇｏｒｉｔｈｍ  １  ＨａｒｌｅｙＤＢＬ］
【数２４】
2006227562.tif 000026
【０２１１】
上記アルゴリズム１［Ａｌｇｏｒｉｔｈｍ  １  ＨａｒｌｅｙＤＢＬ］を逆から計算することにより実現する。Ａｌｇｏｒｉｔｈｍ  １のステップ６では、
Ｖ１'＋ｈ＝（ｋ１ｘ＋ｋ０）Ｕ２＋Ｖ２
を満たすような多項式、
ｋ（ｘ）＝ｋ１ｘ＋ｋ０
が唯一存在する。
【０２１２】
これを、
Ｖ１'＝ｈ＋（ｋ１ｘ＋ｋ０）Ｕ２＋Ｖ２
と式変形し、ステップ４に現れる式、
（ｆ＋ｈＶ１'＋Ｖ１'２）
に代入すると、ステップ４は、次のようになる。
Ｕ２'Ｕ１'＝ｆ＋ｈ（ｋＵ２＋Ｖ２）＋ｋ２Ｕ２２＋Ｖ２２・・・式（１）
上記式において、
（Ｕ２，Ｖ２）は分かっているので、式（１）から、ｋとＵ１'との関係式が得られる。
ここで、
Ｕ２'＝ｋ１２Ｕ２
であることに注意する。
【０２１３】
上記式（１）を展開して整理すると、次のようになる。
Ｕ１'＝ｘ４＋（（ｋ１ｈ２＋ｋ１２ｕ２１＋１）／ｋ１２）ｘ３＋（（ｋ１ｈ１＋ｋ０ｈ２＋ｋ１２ｕ２０＋ｋ０２＋ｃ２）／ｋ１２）ｘ２＋（（ｋ１ｈ０＋ｋ０ｈ１＋ｋ０２ｕ２１＋ｃ１）／ｋ１２）ｘ＋（ｋ０ｈ０＋ｋ０２ｕ２０＋ｃ０）／ｋ１２ 
・・・式（２）
ここで，
ｃ２＝ｆ４＋ｕ２１
ｃ１＝ｆ３＋ｈ２ｖ２１＋ｕ２０＋ｃ２ｕ２１
ｃ０＝ｆ２＋ｈ２ｖ２０＋ｈ１ｖ２１＋ｖ２１２＋ｃ２ｕ２０＋ｃ１ｕ２１
を満たす。
【０２１４】
また、ステップ１より、
Ｕ１'＝Ｕ１２、
つまり、
Ｕ１'＝ｘ４＋ｕ１１２ｘ２＋ｕ１０２
・・・式（３）
が成り立つ。
【０２１５】
上記式（２）、（３）の各係数を比較することにより、関係式を導き、この関係式を解くことにより、１／２倍算が計算できる。上記の処理手順を示すアルゴリズムを以下に、アルゴリズム４［Ａｌｇｏｒｉｔｈｍ  ４  Ｓｋｅｔｃｈ  ＨＥＣ＿ＨＬＶ］として示す。
【数２５】
2006227562.tif 000027
【０２１６】
具体的には，次の関係式が得られる。
【数２６】
2006227562.tif 000028
【０２１７】
これらの関係式から，正しいｋ０，ｋ１を計算する必要があるが、これは、次の補題によって計算できる。
［補題１］
ｈ（ｘ）を既約多項式であると仮定する。このとき、式（４），（５）を満たすｋ１は唯一である。また、式（５）は、正しいｋ１に対してのみ、根を持つ。また、Ａｌｇｏｒｉｔｈｍ４での１／２倍された因子Ｄ１を計算できるｋ０は唯一存在する。また、以下に示す式、
ｘｈ２＋ｘ２ｕ１１＋１＝０
は、正しいｋ０に対してのみ根を持つ。
【０２１８】
Ａｌｇｏｒｉｔｈｍ４に対して上記補題１を適用した。詳細な１／２倍算の計算方法を以下のアルゴリズム５ａ［Ａｌｇｏｒｉｔｈｍ  ５ａ  ＨＥＣ＿ＨＬＶ］として示す。
【数２７】
2006227562.tif 000029
【０２１９】
上記アルゴリズム５ａ［Ａｌｇｏｒｉｔｈｍ５ａ］では、ｋ１'，ｋ０'が正しい値（言い換えるとｋ１，ｋ０が正しくない値）である場合、計算量は、
２９Ｍ＋１Ｓ＋４Ｉ＋３ＳＲ＋２Ｈ＋２Ｔ
となる。ここでＭ，Ｓ，Ｉ，ＳＲ，Ｈ，Ｔはそれぞれ有限体上の乗算、２乗算、逆元演算、平方根演算、ハーフトレース（二次方程式の根を求める演算）、トレース（二次方程式の根があるか否かの判定）を意味する。このｋ１'，ｋ０'が正しい値である場合、計算量は最も多くなる。
【０２２０】
次にｋ１，ｋ０が正しい値（言い換えるとｋ１'，ｋ０'が正しくない値）である場合、計算量は最も少なくなり、ステップ２では２Ｍの計算量が削減でき、ステップ３では、２Ｍ＋１ＳＲの計算量が削減できる。つまり、この場合の計算量は、
２５Ｍ＋１Ｓ＋４Ｉ＋２ＳＲ＋２Ｈ＋２Ｔとなり、計算量は最も少なくなる。
【０２２１】
次にｋ１，ｋ０'が正しい値（言い換えるとｋ１'，ｋ０が正しくない値）である場合，ステップ３では、２Ｍ＋１ＳＲの計算量が削減できる。つまり、この場合の計算量は、
２７Ｍ＋１Ｓ＋４Ｉ＋２ＳＲ＋２Ｈ＋２Ｔとなる。
【０２２２】
最後にｋ１'，ｋ０が正しい値（言い換えるとｋ１，ｋ０'が正しくない値）である場合、ステップ２では，２Ｍの計算量が削減できる。つまり、この場合の計算量は、
２７Ｍ＋１Ｓ＋４Ｉ＋３ＳＲ＋２Ｈ＋２Ｔとなる。
【０２２３】
上記の４つの場合が発生する確率を、計算機実験によって確認した結果、ほぼ同じ割合で発生していることが確認された。これ以降は、上記４つの場合が生じる確率は等しいとする。上記４つの場合の計算量の平均をとると、
２７Ｍ＋１Ｓ＋４Ｉ＋２．５ＳＲ＋２Ｈ＋２Ｔ
となる。
【０２２４】
次に、例外ケースの、
ＥｘＨＥＣ＿ＨＬＶ２→１＋１、
ＥｘＨＥＣ＿ＨＬＶ１→２＋２、
ＥｘＨＥＣ＿ＨＬＶ２→２＋２、
について考える。これらが発生する確率は無視できる程度であるので、計算量の評価は行なわない。
【０２２５】
なお、これらの例外ケースの計算アルゴリズムについては、先の（処理例１：提案法Ａ１）の項目において説明した図４〜図６に示すフローチャート、すなわち、
ＥｘＨＥＣ＿ＨＬＶ２→１＋１のアルゴリズムについては図４に示すフローチャート、
ＥｘＨＥＣ＿ＨＬＶ１→２＋２のアルゴリズムについては図５に示すフローチャート、
ＥｘＨＥＣ＿ＨＬＶ２→２＋２のアルゴリズムについては図６に示すフローチャート、
それぞれにおいて説明した処理と同様の処理となる。
【０２２６】
また、ＥｘＨＥＣ＿ＨＬＶ２→２＋２、の計算手順についても、先に説明した（処理例１：提案法Ａ１）の項目において説明したアルゴリズム６［Ａｌｇｏｒｉｔｈｍ６］と同様の処理であり、ＥｘＨＥＣ＿ＨＬＶ１→２＋２の計算手順についても、先に説明した（処理例１：提案法Ａ１）の項目において説明したアルゴリズム７［Ａｌｇｏｒｉｔｈｍ７］と同様の処理となる。
【０２２７】
［処理例８：提案法Ｆ２］
処理例８（提案法Ｆ２）は、前述した処理例（処理例２：提案法Ｆ１）のさらなる高速化手法であり、種数２，標数２のｈ（ｘ）＝ｘ２＋ｈ１ｘ＋ｈ０、ｆ４＝０をパラメータに持つような超楕円曲線において因子Ｄの１／２倍算を計算する方法である。
【０２２８】
前述の処理例（処理例７：提案法Ａ２）において適用したＡｌｇｏｒｉｔｈｍ５ａを良く見ると、ｈ（ｘ）の係数との乗算、ｈ（ｘ）の係数の逆元演算が多くある。つまり、ｈ（ｘ）の係数を工夫することにより、乗算および逆元演算の計算量を削減することができる。なお、文献（非特許文献１９：T. Lange. Efficient Doubling on Genus Two Curves over Binary Fields, SAC 2004, pre-proceedings, pp.189-202, 2004.）では、高速化のため、ｈ２＝１、ｆ４＝０を用いている。このパラメータを用いた場合のＨａｒｌｅｙＤＢＬの計算量は、２１Ｍ＋５Ｓ＋１Ｉである。
【０２２９】
ここで説明する処理例８（提案法Ｆ２）もこれに条件を合わせることにするが、補題１より、ｈ（ｘ）は既約多項式を仮定しているため、
ｈ（ｘ）＝ｘ２＋ｈ１ｘ＋ｈ０、
Ｔｒ（ｈ０／ｈ１２）＝１[0]
とする（二次方程式ａｘ２＋ｂｘ＋ｃ＝０が既約多項式であるための必要十分条件はＴｒ（ａｃ／ｂ２）＝１である）。この場合の計算法をアルゴリズム８ａ［Ａｌｇｏｒｉｔｈｍ  ８ａ］ＨＥＣ＿ＨＬＶ（ｈ２＝１、ｆ４＝０）に示す。
【０２３０】
【数２８】
2006227562.tif 000030
【０２３１】
ここで、逆元演算の回数を削減する方法を考える。前述したアルゴリズム５ａ［Ａｌｇｏｒｉｔｈｍ  ５ａ］では、１／ｕ２１，１／ｈ２２，１／ｈ１２，１／ｋ１の４回の逆元演算が必要であるが、ここで、
ｈ２＝１
と設定することにより、逆元演算は３回とすることができる。さらに、ｈ１は曲線パラメータであるため、事前に１／ｈ１２を計算しておき、入力として与えることにより、逆元演算は１／ｕ２１と１／ｋ１の２回に削減することができる。また、１／ｋ１に関しては，前述の［処理例７：提案法Ａ２］において説明した式（４），すなわち、
１／ｋ１＝ｈ２＋ｋ１ｕ２１
より，乗算１回と加算１回で求めることができる。これらの演算により、上記のアルゴリズム８ａ［Ａｌｇｏｒｉｔｈｍ  ８ａ］ＨＥＣ＿ＨＬＶ（ｈ２＝１、ｆ４＝０）で必要となる逆元演算は１／ｕ２１の１回のみとなる。
【０２３２】
結果として、上記のアルゴリズム８ａ［Ａｌｇｏｒｉｔｈｍ  ８ａ］ＨＥＣ＿ＨＬＶ（ｈ２＝１、ｆ４＝０）における計算量は次の通りとなる。
（ａ）ｋ１，ｋ０が正しい値である場合：１８Ｍ＋２Ｓ＋１Ｉ＋２ＳＲ＋２Ｈ＋２Ｔ
（ｂ）ｋ１，ｋ０'が正しい値である場合：１９Ｍ＋２Ｓ＋１Ｉ＋３ＳＲ＋２Ｈ＋２Ｔ
（ｃ）ｋ１'，ｋ０が正しい値である場合：２０Ｍ＋２Ｓ＋１Ｉ＋２ＳＲ＋２Ｈ＋２Ｔ
（ｄ）ｋ１'，ｋ０'が正しい値である場合：２１Ｍ＋２Ｓ＋１Ｉ＋３ＳＲ＋２Ｈ＋２Ｔ
上記（ａ）〜（ｄ）のすべてについて平均すると、１９．５Ｍ＋２Ｓ＋１Ｉ＋２．５ＳＲ＋２Ｈ＋２Ｔとなる。
【０２３３】
ＨａｒｌｅｙＤＢＬの計算量は、２１Ｍ＋５Ｓ＋１Ｉであった。ここで、文献［（非特許文献１５）  E.Knudsen. Elliptic Scalar Multiplication Using Point Halving. ASIACRYPTO '99, LNCS 1716, pp.135-149, Springer-Verlag, 1999.］によると、有限体が正規基底で定義されている場合、Ｓ（２乗算），ＳＲ（平方根演算），Ｈ（ハーフトレース（二次方程式の根を求める演算）），Ｔ（トレース（二次方程式の根があるか否かの判定））の計算量は無視することができ、Ｍ（乗算），Ｉ（逆元演算）の計算量のみ考慮すればよいことが知られている。そのため、正規基底を用いた場合、Ａｌｇｏｒｉｔｈｍ８ａはＨａｒｌｅｙＤＢＬよりも１．５Ｍ高速となる。
【０２３４】
また、有限体が多項式基底で定義されている場合、
文献［（非特許文献１６）  K.Fong, D.Hankerson, J.Lopez, and A.Menezes. Field inversion and point halving revised. Technical Report CORR2003-18, http://www.cacr.math.uwaterloo.ca/techreports/2003/ corr2003-18.pdf１８］によると、通常ＳＲ（平方根演算），Ｈ（ハーフトレース（二次方程式の根を求める演算））の計算量は、Ｍ（乗算）との対比において、ＳＲ＝Ｈ＝０．５Ｍ程度であることが知られている。また、Ｔ（トレース（二次方程式の根があるか否かの判定））の計算量は無視できる。さらにＳ（２乗算）の計算量は、Ｍ（乗算）の数分の１程度であることが知られている。しかしながら、ＳＲの計算量は、多項式基底の選び方によっては、０．５Ｍよりも少なくなることも、同時に知られている。なお、例外ケースは、前述の処理例７（提案法Ａ２）の例外ケースに基いて計算できる。
【０２３５】
［処理例９（提案法Ｂ２）］
処理例９（提案法Ｂ２）は、前述した処理例（処理例３：提案法Ｂ１）のさらなる高速化手法であり、種数２、標数２のｈ（ｘ）＝ｘ２＋ｘ＋ｈ０、ｆ４＝０をパラメータに持つような超楕円曲線において、因子Ｄの１／２倍算を計算する方法である。
【０２３６】
前述の処理例８（提案法Ｆ２）において説明したように、処理例７（提案法Ａ２）において説明した１／２倍算の計算アルゴリズム、すなわち、アルゴリズム５ａ［Ａｌｇｏｒｉｔｈｍ  ５ａ  ＨＥＣ＿ＨＬＶ］を良く見ると、ｈ（ｘ）の係数との乗算、ｈ（ｘ）の係数の逆元演算が多くある。つまり、ｈ（ｘ）の係数を工夫することにより、乗算および逆元演算の計算量を削減することができる。文献［J.Pelzl, T.Wollinger, and C.Paar. High Performance Arithmetic for Hyperelliptic Curve Cryptosystems of Genus Two. Cryptology ePrint Archive, 2003/212, IACR, 2003］では、高速化のために、ｈ２，ｈ１∈｛０，１｝，ｆ４＝０を用いた例を示している。
【０２３７】
このパラメータを用いた場合の［ＨａｒｌｅｙＤＢＬ］の計算量は、
１８Ｍ＋７Ｓ＋１Ｉ
である。
【０２３８】
処理例９（提案法Ｂ２）もこれに条件を合わせることにするが、前述した［補題１］より、ｈ（ｘ）は既約多項式を仮定しているため、
ｈ（ｘ）＝ｘ２＋ｘ＋ｈ０，
Ｔｒ（ｈ０）＝１
とする（二次方程式ａｘ２＋ｂｘ＋ｃ＝０が既約多項式であるための必要十分条件はＴｒ（ａｃ／ｂ２）＝１である）。
【０２３９】
この場合の計算法示すアルゴリズムをアルゴリズム１０ａ［Ａｌｇｏｒｉｔｈｍ１０ａ  ＨＥＣ＿ＨＬＶ（ｈ２＝ｈ１＝１，ｆ４＝０）］として以下に示す。
【数２９】
2006227562.tif 000031
【０２４０】
上記のアルゴリズム１０ａ［Ａｌｇｏｒｉｔｈｍ１０ａ  ＨＥＣ＿ＨＬＶ（ｈ２＝ｈ１＝１，ｆ４＝０）］における計算量は次の通りである。
（ａ）ｋ１，ｋ０が正しい値である場合：１４Ｍ＋３Ｓ＋１Ｉ＋２ＳＲ＋２Ｈ＋２Ｔ
（ｂ）ｋ１，ｋ０'が正しい値である場合：１５Ｍ＋３Ｓ＋１Ｉ＋３ＳＲ＋２Ｈ＋２Ｔ
（ｃ）ｋ１'，ｋ０が正しい値である場合：１４Ｍ＋３Ｓ＋１Ｉ＋２ＳＲ＋２Ｈ＋２Ｔ
（ｄ）ｋ１'，ｋ０'が正しい値である場合：１５Ｍ＋３Ｓ＋１Ｉ＋３ＳＲ＋２Ｈ＋２Ｔ
【０２４１】
上記（ａ）〜（ｄ）のすべての場合について平均すると、
１４．５Ｍ＋３Ｓ＋１Ｉ＋２．５ＳＲ＋２Ｈ＋２Ｔ
となる。ＨａｒｌｅｙＤＢＬの計算量は、１８Ｍ＋７Ｓ＋１Ｉであった。ここで、前述したように、文献［E.Knudsen. Elliptic Scalar Multiplication Using Point Halving. ASIACRYPTO '99, LNCS 1716, pp.135-149, Springer-Verlag, 1999.］によると、有限体が正規基底で定義されている場合、Ｓ（２乗算），ＳＲ（平方根演算），Ｈ（ハーフトレース（二次方程式の根を求める演算）），Ｔ（トレース（二次方程式の根があるか否かの判定））の計算量は無視することができ、Ｍ（乗算），Ｉ（逆元演算）の計算量のみ考慮すればよいことが知られている。
【０２４２】
そのため、正規基底を用いた場合、上述したアルゴリズム１０ａ［Ａｌｇｏｒｉｔｈｍ１０ａ］は、従来のアルゴリズム［ＨａｒｌｅｙＤＢＬ］よりも、３．５Ｍ高速となる。また、有限体が多項式基底で定義されている場合、
文献［K.Fong, D.Hankerson, J.Lopez, and A.Menezes. Field inversion and point halving revised. Technical Report CORR2003-18, http://www.cacr.math.uwaterloo.ca/techreports/2003/corr2003-18.pdf］によると、通常ＳＲ，Ｈの計算量は、ＳＲ＝Ｈ＝０．５Ｍ程度であることが知られている。また、Ｔの計算量は無視できる。さらにＳの計算量は、Ｍの数分の１程度であることが知られている。しかしながら、ＳＲの計算量は、多項式基底の選び方によっては、０．５Ｍよりも少なくなることも同時に知られている。
【０２４３】
さて、前述のアルゴリズム１０ａ［Ａｌｇｏｒｉｔｈｍ１０ａ］の曲線にさらに、ｈ０＝１の制約を設ける。前述のアルゴリズム１０ａ［Ａｌｇｏｒｉｔｈｍ１０ａ］は、ｈ０の乗算が１回あるので、ｈ０＝１とすることにより、１Ｍの削減ができ、上記（ａ）〜（ｄ）のすべての場合についての平均の計算量は、
１３．５Ｍ＋３Ｓ＋１Ｉ＋２．５ＳＲ＋２Ｈ＋２Ｔ
となる。一方、ＨａｒｌｅｙＤＢＬは、計算量は、
１５Ｍ＋７Ｓ＋１Ｉ
である。有限体が正規規定で定義されている場合、Ｓ，ＳＲ，Ｈ，Ｔの計算量は無視することができ、正規規定を用いた場合、アルゴリズム１０ａ［Ａｌｇｏｒｉｔｈｍ１０ａ］は、従来のアルゴリズム［ＨａｒｌｅｙＤＢＬ］よりも、１．５Ｍ高速となる。なお、例外ケースは、前述の処理例７（提案法Ａ２）の例外ケースに基いて計算できる。
【０２４４】
［処理例１０（提案法Ｃ２）］
処理例１０（提案法Ｃ２）は、前述した処理例（処理例５：提案法Ｃ１）のさらなる高速化手法であり、種数２、標数２のランダムパラメータを持つような超楕円曲線、ｈ（ｘ）＝ｘ２＋ｈ１ｘ＋ｈ０，ｆ４＝０をパラメータに持つ超楕円曲線、およびｈ（ｘ）＝ｘ２＋ｘ＋ｈ０、ｆ４＝０をパラメータに持つような超楕円曲線において、因子Ｄの１／２倍算を計算する際に、１／２倍したものの候補が２つ出てくる。２つの候補のうち、正しい値を選ぶ必要があるが、選ぶ際に、有限体のトレース、乗算、平方根を計算する必要がある。どちらが正しいかは、因子Ｄに依存する。そのため、因子Ｄが固定されている場合、事前に２つの候補のうち、どちらが正しいかをテーブルに保持し、正しい値を選ぶ際に、このテーブルを参照することにより、上記の余計な計算を省略する方法である。
【０２４５】
ｋ１，ｋ１'（ｋ０，ｋ０'）のどちらが正しいかは、入力因子Ｄに依存している。したがって、Ｄが固定されている場合、例えばＥＣＤＨ型鍵交換のフェーズ１や、ＥＣＤＳＡ型署名生成、検証など、ベースポイントがあらかじめ決まっている場合、事前に、［１／２ｉ］Ｄを計算し、ｋ１，ｋ１'（ｋ０，ｋ０'）のどちらが正しい値であるかを、テーブルに記録しておく。
【０２４６】
例えば、ベースポイントの位数と同じビットサイズのテーブルをＴ１，Ｔ０と二つ用意し、これらを２進数表現したものを、
Ｔ１＝（ｔ１，ｒ−１，...，ｔ１，０）
Ｔ０＝（ｔ０，ｒ−１，...，ｔ０，０）
とする。
【０２４７】
［１／２ｉ］Ｄを求める際に、
ｋ１が正しければ、ｔ１，ｉ＝０、そうではなくて、ｋ１'が正しければｔ１，ｉ＝１
ｋ１が正しければｔ０，ｉ＝０、そうではなくて、ｋ０'が正しければｔ０，ｉ＝１などとテーブルに記録すれば、テーブルサイズは、わずかベースポイントの位数のサイズの２倍程度のビット列で済む。このテーブルを参照することにより、１／２倍算の計算量を削減することができる。
【０２４８】
この方法を前述のアルゴリズム８ａ［Ａｌｇｏｒｉｔｈｍ  ８ａ］  ＨＥＣ＿ＨＬＶ（ｈ２＝１，ｆ４＝０）に適用したものを、アルゴリズム９ａ［Ａｌｇｏｒｉｔｈｍ  ９ａ］  ＨＥＣ＿ＨＬＶ（ｈ２＝１，ｆ４＝０，ｗｉｔｈ  ｔａｂｌｅ−ｌｏｏｋｕｐ）として示す。計算量は、１８Ｍ＋２Ｓ＋１Ｉ＋２ＳＲ＋２Ｈとなる。
【０２４９】
【数３０】
2006227562.tif 000032
【０２５０】
具体的に，この方法を上述のアルゴリズム１０ａ［Ａｌｇｏｒｉｔｈｍ１０ａ  ＨＥＣ＿ＨＬＶ  （ｈ２＝ｈ１＝１，ｆ４＝０）］に適用したアルゴリズムをアルゴリズム１１ａ［Ａｌｇｏｒｉｔｈｍ１１ａ  ＨＥＣ＿ＨＬＶ（ｈ２＝ｈ１＝１，ｆ４＝０，ｗｉｔｈ  ｔａｂｌｅ−ｌｏｏｋｕｐ）］として、以下に示す。
【０２５１】
【数３１】
2006227562.tif 000033
【０２５２】
上記アルゴリズム１１ａ［Ａｌｇｏｒｉｔｈｍ１１ａ  ＨＥＣ＿ＨＬＶ（ｈ２＝ｈ１＝１，ｆ４＝０，ｗｉｔｈ  ｔａｂｌｅ−ｌｏｏｋｕｐ）］における計算量は、
１４Ｍ＋３Ｓ＋１Ｉ＋２ＳＲ＋２Ｈとなり、さらにｈ０＝１とすることにより、１Ｍの削減ができ、この場合の計算量は、
１３Ｍ＋３Ｓ＋１Ｉ＋２ＳＲ＋２Ｈとなる。
【０２５３】
［処理例１１（提案法Ｄ２）］
処理例１１（提案法Ｄ２）は、上記処理例７〜１０に示す因子の１／２倍算の計算方法を用いて、因子のスカラー倍算を計算する方法である。
【０２５４】
楕円曲線での有理点の１／２倍算を用いたスカラー倍算の計算方法は、文献［E.Knudsen. Elliptic Scalar Multiplication Using Point Halving. ASIACRYPTO '99, LNCS 1716, pp.135-149, Springer-Verlag, 1999.］、［K.Fong, D.Hankerson, J.Lopez, and A.Menezes. Field inversion and point halving revised. Technical Report CORR2003-18,http://www.cacr.math.uwaterloo.ca/techreports/2003/corr2003-18 .pdf］にある。超楕円曲線の因子の１／２倍算を用いたスカラー倍算の計算方法は、この文献にあるスカラー倍算に基づいて実行される。ここで、スカラー倍の対象となる因子Ｄは、位数が大きな素数ｒであるとする。また，スカラー値を整数０＜ｄ＜ｒとする。１／２倍算を用いたスカラー倍算を行なうには、まず、２進数で表現されているスカラー値ｄを１／２進数で表現しなおす必要がある。
【０２５５】
ここで、
【数３２】
2006227562.tif 000034
とする。また、ｄを２ｍ倍しｒで割った余り、すなわち、
【数３３】
2006227562.tif 000035
を求める。次にこれを２ｍで割ると、
【数３４】
2006227562.tif 000036
となる。上記式の、
【数３５】
2006227562.tif 000037
で表現されたスカラー値を、１／２倍算を用いたスカラー倍算［ｈａｌｖｅ−ａｎｄ−ａｄｄ  ｂｉｎａｒｙ］法で用いる。ここで、
【数３６】
2006227562.tif 000038
である。
【０２５６】
以下に、アルゴリズム１２ａ［Ａｌｇｏｒｉｔｈｍ  １２ａ］として、ｈａｌｖｅ−ａｎｄ−ａｄｄ  ｂｉｎａｒｙ法（ｒｉｇｈｔ−ｔｏ−ｌｅｆｔ）、アルゴリズム１３ａ［Ａｌｇｏｒｉｔｈｍ  １３ａ］として、ｈａｌｖｅ−ａｎｄ−ａｄｄ  ｂｉｎａｒｙ法（ｌｅｆｔ−ｔｏ−ｒｉｇｈｔ）をそれぞれ示す。
【数３７】
2006227562.tif 000039
【０２５７】
【数３８】
2006227562.tif 000040
【０２５８】
上記アルゴリズム１２ａ［Ａｌｇｏｒｉｔｈｍ  １２ａ］と、アルゴリズム１３ａ［Ａｌｇｏｒｉｔｈｍ  １３ａ］のステップ４に出てくるＨＥＣ＿ＨＬＶは、ランダムカーブを用いた前述のアルゴリズム５ａ［Ａｌｇｏｒｉｔｈｍ  ５ａ］のＨＥＣ＿ＨＬＶでも良いし、アルゴリズム８ａ［Ａｌｇｏｒｉｔｈｍ  ８ａ］の曲線パラメータに、ｈ２＝１，ｆ４＝０の制約を設けたＨＥＣ＿ＨＬＶでも良いし、アルゴリズム１０ａ［Ａｌｇｏｒｉｔｈｍ  １０ａ］の曲線パラメータにｈ２＝ｈ１＝１，ｆ４＝０の制約を設けたＨＥＣ＿ＨＬＶでも良いし、アルゴリズム１０ａ［Ａｌｇｏｒｉｔｈｍ  １０ａ］の曲線パラメータにｈ２＝ｈ１＝ｈ０＝１，ｆ４＝０の制約を設けたＨＥＣ＿ＨＬＶでも良い。
【０２５９】
前段の処理例１〜６において説明した１／２倍算において、例えば前述の［処理例３（提案法Ｂ１）］に示すアルゴリズム１０や、［処理例５（提案法Ｃ１）］に示すアルゴリズム１１では、入力に１／ｕ２１が、出力に１／ｕ１１が必要であった。これにより、ベースポイントＤの１／２ｉ倍算、すなわち、
（１／２）Ｄ、（１／２２）Ｄ、（１／２３）Ｄ、（１／２ｉ）Ｄ・・・
を、前の１／２倍算の出力の１／ｕ１１を次の１／２倍算の入力として与えることができるので、効率よく計算することができる。そのため、スカラー倍を  ｈａｌｖｅ−ａｎｄ−ａｄｄ  ｂｉｎａｒｙ法（ｒｉｇｈｔ−ｔｏ−ｌｅｆｔ）で行なう場合には、ベースポイントＤの１／２ｉ倍を適宜加えていけばよいので、ｒｉｇｈｔ−ｔｏ−ｌｅｆｔの場合には、効率よくスカラー倍算を行なうことができた。
【０２６０】
一方、ｌｅｆｔ−ｔｏ−ｒｉｇｈｔの場合には、前の１／２倍算の出力を次の１／２倍算の入力とすることができない場合がある。前述のアルゴリズム１３ａ［Ａｌｇｏｒｉｔｈｍ１３ａ］のＳｔｅｐ４では、まず途中の結果Ｑを１／２倍し（Ｑ←ＨＥＣ＿ＨＬＶ（Ｑ））、スカラー値のあるビットが１の場合は、ベースポイントを途中結果に加える（ｉｆ  ｄｉ＝１ｔｈｅｎＱ←Ｑ＋Ｄ）。このため、ビットが１の場合の、次のビットでは、前の１／２倍算の出力の１／ｕ１１を次の１／２倍算の入力として与えることができないので、新たに入力値１／ｕ２１を計算する必要がある。有限体の逆元演算は乗算に比べて非常に計算量がかかる。そのため、先の処理例１〜６において説明した１／２倍算法では、ｌｅｆｔ−ｔｏ−ｒｉｇｈｔを適用した場合、１／２倍算の入力値を生成するための余計な逆元演算を必要とするため、計算の効率が悪くなる。しかしながら、処理例７以降において説明した提案法では、入力に１／ｕ２１を必要としない設定としているため、ｌｅｆｔ−ｔｏ−ｒｉｇｈｔでもｒｉｇｈｔ−ｔｏ−ｌｅｆｔと同等の計算量で計算することができる。
【０２６１】
また、前述のアルゴリズム１２ａ［Ａｌｇｏｒｉｔｈｍ  １２ａ］のｈａｌｖｅ−ａｎｄ−ａｄｄ  ｂｉｎａｒｙ法（ｒｉｇｈｔ−ｔｏ−ｌｅｆｔ）のステップ４のＨＥＣ＿ＨＬＶは、ランダムカーブを用いたアルゴリズム５ａ［Ａｌｇｏｒｉｔｈｍ  ５ａ］にテーブル参照法を適用したＨＥＣ＿ＨＬＶでも良いし、アルゴリズム８ａ［Ａｌｇｏｒｉｔｈｍ  ８ａ］の曲線パラメータにｈ２＝１，ｆ４＝０の制約を設け、テーブル参照法を適用したＨＥＣ＿ＨＬＶでも良いし、アルゴリズム１０ａ［Ａｌｇｏｒｉｔｈｍ  １０ａ］の曲線パラメータにｈ２＝ｈ１＝１，ｆ４＝０の制約を設け、テーブル参照法を適用したＨＥＣ＿ＨＬＶでも良いし、アルゴリズム１０ａ［Ａｌｇｏｒｉｔｈｍ  １０ａ］の曲線パラメータにｈ２＝ｈ１＝ｈ０＝１，ｆ４＝０の制約を設け，テーブル参照法を適用したＨＥＣ＿ＨＬＶでも良い。
【０２６２】
また，ｂｉｎａｒｙ法のほかに、ｗｉｎｄｏｗ法も適用することができる。入力因子をＤとしｗｉｎｄｏｗ幅をｗとする。途中結果を代入する因子をＱ←Ｏとする。
整数ｉ＝（ｉｗ−１，ｉｗ−２・・・ｉ０）２∈｛０，１，・・・，２ｗ−１｝
に対して事前計算、すなわち、
【数３９】
2006227562.tif 000041
を行い２ｗ個の因子からなるテーブルを計算しておく。
【０２６３】
また、スカラー値ｄを、１／２ｗ進数展開する。
【数４０】
2006227562.tif 000042
はじめにＱに１／２倍算をｗ回適用し、
Ｑ←（１／２ｗ）Ｑ
とする。次にｄの上位ビットからｗｉｎｄｏｗ幅ｗで、スカラー値ｃ１を走査し、対応するテーブルの因子の値を参照し、結果に足し込む。
Ｑ←Ｑ＋Ｄｃｌ
これをｃ０まで繰り返す。
【０２６４】
この計算手法［ｈａｌｖｅ−ａｎｄ−ａｄｄ  ｗｉｎｄｏｗ  ｍｅｔｈｏｄ］を、アルゴリズム１４ａ［Ａｌｇｏｒｉｔｈｍ  １４ａ］として以下に示す。
【数４１】
2006227562.tif 000043
【０２６５】
また、
因子Ｄ＝（Ｕ，Ｖ），
Ｕ＝ｘ２＋ｕ１ｘ＋ｕ０，
Ｖ＝ｖ１ｘ＋ｖ０，
の逆元は、
−Ｄ＝（Ｕ，Ｖ＋ｈｍｏｄＵ）＝（Ｕ，（ｖ１＋ｈ２ｕ１＋ｈ１）ｘ＋（ｖ０＋ｈ２ｕ０＋ｈ０））
で表すことが出来る。特にｈ２＝１の場合は、有限体の乗算は必要なく、４回の有限体の加算でＤから−Ｄを求めることが出来る。因子Ｄの減算は因子−Ｄの加算により計算できる。つまり、因子の加算と減算は同等の計算量で求めることができる。
【０２６６】
そこで、スカラー値を負の値も使って表現し、それを用いてスカラー倍算を行なうことが出来る。まず、非隣接形式ＮＡＦ（Ｎｏｎ−Ａｄｊａｃｅｎｔ  Ｆｏｒｍ）を使い、ある整数ｓを｛−１，０，１｝で表現する。ＮＡＦでは２進数表現されたスカラー値ｓを下位のビットから見ていく。１が隣接するところがあれば、例えば、
（１１）であれば、（１０−１）、つまり３＝２２−１，
（１１１）であれば、（１００−１）、つまり７＝２３−１
などと表現する。
【０２６７】
ＮＡＦの計算手法を、アルゴリズム１５ａ［Ａｌｇｏｒｉｔｈｍ  １５ａ］として以下に示す。
【数４２】
2006227562.tif 000044
【０２６８】
ＮＡＦは，非零のビットの数が最も少ない表現法である。非零のビットの箇所では、因子の加算もしくは減算を行なうため、非零のビットの数が少ない方が、スカラー倍算を高速に計算することが出来る。ＮＡＦを用いたスカラー値表現を、ｈａｌｖｅ−ａｎｄ−ａｄｄ  ｂｉｎａｒｙ法，ｈａｌｖｅ−ａｎｄ−ａｄｄ  ｗｉｎｄｏｗ法に適用することが出来る。ｈａｌｖｅ−ａｎｄ−ａｄｄ  ｂｉｎａｒｙ法，ｈａｌｖｅ−ａｎｄ−ａｄｄ  ｗｉｎｄｏｗ法で用いる  ＨＥＣ＿ＨＬＶ  はランダムカーブを用いたアルゴリズム５ａ［Ａｌｇｏｒｉｔｈｍ  ５ａ］のＨＥＣ＿ＨＬＶでも良いし、アルゴリズム８ａ［Ａｌｇｏｒｉｔｈｍ  ８ａ］の曲線パラメータにｈ２＝１，ｆ４＝０の制約を設けたＨＥＣ＿ＨＬＶでも良いし、アルゴリズム１０ａ［Ａｌｇｏｒｉｔｈｍ  １０ａ］の曲線パラメータにｈ２＝ｈ１＝１，ｆ４＝０の制約を設けたＨＥＣ＿ＨＬＶでも良いし、アルゴリズム１０ａ［Ａｌｇｏｒｉｔｈｍ  １０ａ］の曲線パラメータにｈ２＝ｈ１＝ｈ０＝１，ｆ４＝０の制約を設けたＨＥＣ＿ＨＬＶでも良い。ＮＡＦを用いたｈａｌｖｅ−ａｎｄ−ａｄｄ  ｂｉｎａｒｙ方を  アルゴリズム１６ａ［Ａｌｇｏｒｉｔｈｍ  １６ａ］として以下に示す。
【数４３】
2006227562.tif 000045
【０２６９】
［演算高速化の検証］
次に、上述した処理例７〜１１を適用した演算における計算量を求め、演算の高速化について検証する。
【０２７０】
ＨＥＣ＿ＨＬＶ（ｈ２＝１，ｆ４＝０）では、計算量は、平均で、
１９．５Ｍ＋２Ｓ＋１Ｉ＋２．５ＳＲ＋２Ｈ＋２Ｔ
である。
【０２７１】
まず、有限体が正規基底で定義されている場合について考える。前述のとおり、正規基底を用いた場合、Ｍ，Ｉのみの計算量を考慮すればよい。文献［A.Menezes. Elliptic Curve Public Key Cryptosystems. Kluwer Academic Publishers, 1993.］によると、有限体をＦｑ，ｑ＝２ｎとした場合、逆元計算一回は、下式によって算出される回数、すなわち、
【数４４】
2006227562.tif 000046
【０２７２】
上記式によって算出される回数の乗算に匹敵する。ここで、ｗ（ｎ−１）はｎ−１を２進数で表示した際の１の個数を表す。例えば、ｎ＝８３，８９，１１３の場合、Ｉ＝８Ｍとなり、ｎ＝１０３の場合、Ｉ＝９Ｍとなる。
【０２７３】
ここで、Ｉ＝８Ｍを仮定すると、
ＨＥＣ＿ＨＬＶ（ｈ２＝１，ｆ４＝０）
の計算量は、
１９．５Ｍ＋１Ｉ＝２７．５Ｍとなる。
【０２７４】
一方、ＨａｒｌｅｙＤＢＬでは、
２１Ｍ＋１Ｉ＝２９Ｍとなり、ＨＥＣ＿ＨＬＶの方がＨａｒｌｅｙＤＢＬよりも５％ほど高速となる。また、テーブル参照法を用いた場合では、
１８Ｍ＋１Ｉ＝２６Ｍ
となり、ＨＥＣ＿ＨＬＶは、ＨａｒｌｅｙＤＢＬよりも１０％ほど高速となる。
【０２７５】
また、ＨＥＣ＿ＨＬＶ（ｈ２＝ｈ１＝１，ｆ４＝０）
の計算量は、平均で、
１４．５Ｍ＋３Ｓ＋１Ｉ＋２．５ＳＲ＋２Ｈ＋２Ｔ
となる。この場合は、
１４．５Ｍ＋１Ｉ＝２２．５Ｍ
となる。
【０２７６】
一方、ＨａｒｌｅｙＤＢＬでは、
１８Ｍ＋１Ｉ＝２６Ｍとなり、ＨＥＣ＿ＨＬＶの方がＨａｒｌｅｙＤＢＬよりも１３％ほど高速となる。また、テーブル参照法を用いた場合では、
１４Ｍ＋１Ｉ＝２２Ｍ
となり、ＨＥＣ＿ＨＬＶの方がＨａｒｌｅｙＤＢＬよりも１５％ほど高速となる。
【０２７７】
また、ＨＥＣ＿ＨＬＶ（ｈ２＝ｈ１＝ｈ０＝１，ｆ４＝０）
の計算量は、平均で、
１３．５Ｍ＋３Ｓ＋１Ｉ＋２．５ＳＲ＋２Ｈ＋２Ｔ
となる。この場合は、
１３．５Ｍ＋１Ｉ＝２１．５Ｍ
となる。
【０２７８】
一方、ＨａｒｌｅｙＤＢＬでは、
１５Ｍ＋１Ｉ＝２３Ｍとなり、ＨＥＣ＿ＨＬＶの方がＨａｒｌｅｙＤＢＬよりも６％ほど高速となる。また、テーブル参照法を用いた場合では、
１７Ｍ＋１Ｉ＝２５Ｍ
となり、ＨＥＣ＿ＨＬＶの方がＨａｒｌｅｙＤＢＬよりも１４％ほど高速となる。
【０２７９】
次に、多項式基底の場合の計算量を評価する。Ｓ，Ｉ，ＳＲ，Ｈ，Ｔの計算量をそれぞれＳ＝０．１Ｍ，Ｉ＝８Ｍ，ＳＲ＝０．５Ｍ，Ｈ＝０．５Ｍ，Ｔ＝０Ｍと仮定する。ＨＥＣ＿ＨＬＶ（ｈ２＝１，ｆ４＝０）では、計算量は平均で、
１９．５Ｍ＋２Ｓ＋１Ｉ＋２．５ＳＲ＋２Ｈ＋２Ｔ＝２９．９５Ｍ
となる。
一方、ＨａｒｌｅｙＤＢＬでは、
２１Ｍ＋５Ｓ＋１Ｉ＝２９．５Ｍ
となり、ＨａｒｌｅｙＤＢＬの方がＨＥＣ＿ＨＬＶよりも１％程度高速となる。
【０２８０】
また、テーブル参照法を用いた場合は、
１８Ｍ＋２Ｓ＋１Ｉ＋２ＳＲ＋２Ｈ＝２８．２Ｍ
となり、ＨＥＣ＿ＨＬＶはＨａｒｌｅｙＤＢＬよりも４％程度高速となる。
また、ＨＥＣ＿ＨＬＶ（ｈ２＝ｈ１＝１，ｆ４＝０）では、計算量は平均で、
１４．５Ｍ＋３Ｓ＋１Ｉ＋２．５ＳＲ＋２Ｈ＋２Ｔ＝２５．０５Ｍ
となる。一方、ＨａｒｌｅｙＤＢＬでは、
１８Ｍ＋７Ｓ＋１Ｉ＝２６．７Ｍ
となり、ＨＥＣ＿ＨＬＶの方がＨａｒｌｅｙＤＢＬよりも６％程度高速となる。
【０２８１】
また、テーブル参照法を用いた場合は、
１４Ｍ＋３Ｓ＋１Ｉ＋２ＳＲ＋２Ｈ＝２４．３Ｍ
となり、ＨＥＣ＿ＨＬＶの方がＨａｒｌｅｙＤＢＬよりも９％程度高速となる。
【０２８２】
また、ＨＥＣ＿ＨＬＶ（ｈ２＝ｈ１＝ｈ０＝１，ｆ４＝０）の計算量は、
１３．５Ｍ＋３Ｓ＋１Ｉ＋２．５ＳＲ＋２Ｈ＋２Ｔ＝２４．０５Ｍ
となる。一方、ＨａｒｌｅｙＤＢＬでは、
１５Ｍ＋７Ｓ＋１Ｉ＝２３．７Ｍ
となり、ＨａｒｌｅｙＤＢＬの方がＨＥＣ＿ＨＬＶよりも１％程度高速となる。また、テーブル参照法を用いた場合は、
１３Ｍ＋３Ｓ＋１Ｉ＋２ＳＲ＋２Ｈ＝２３．３Ｍ
となり、ＨＥＣ＿ＨＬＶの方がＨａｒｌｅｙＤＢＬよりも２％程度高速となる。
【０２８３】
また、多項式基底の場合をソフトウェア実装を行い、速度の比較を行った。
ＣＰＵは  ＰｅｎｔｉｕｍＩＩ  ３００ＭＨｚ、
ＯＳはＲｅｄＨａｔ７．３、
コンパイラはｇｃｃ２．９６
の環境でソフトウェア実装を行った。
【０２８４】
Ｍ（乗算）、Ｓ（２乗算）は、文献［D.Hankerson, J.Hernandez, and A.Menezes. Software Implementation of Elliptic Curve Cryptography over Binary Fields. CHES 2000, LNCS 1965, pp.1-24, 2000.，Ａｌｇｏｒｉｔｈｍ４．６，４．７］、Ｉ（逆元演算）は、文献［S.Shantz. From Euclid's GCD to Montgomery Multiplication to the Great Divide. TR-2001-95, Sun Microsystems, Inc., 2001.］、ＳＲ（平方根演算）、Ｔ（トレース（二次方程式の根があるか否かの判定））は、文献［K.Fong, D.Hankerson, J.Lopez, and A.Menezes. Field inversion and point halving revised. Technical Report CORR2003-18, http://www.cacr.math.uwaterloo.ca/techreports/2003/corr2003-18.pdf］、Ｈ（ハーフトレース（二次方程式の根を求める演算））は、文献［K.Fong, D.Hankerson, J.Lopez, and A.Menezes. Field inversion and point halving revised. Technical Report CORR2003-18, http://www.cacr.math.uwaterloo.ca/techreports/2003/corr2003-18.pdf  Ａｌｇｏｒｉｔｈｍ  ４．７］に従った。
【０２８５】
ｎ＝８３，８９，１１３の３つの有限体に対して，Ｍ，Ｓ，Ｉ，ＳＲ，Ｈ，Ｔを実装し、Ｍとの比を求めた。ここで、
ｎ＝８３の既約多項式は、
ｚ８３＋ｚ７＋ｚ４＋ｚ２＋１＝０
ｎ＝８９の既約多項式は、
ｚ８９＋ｚ３８＋１＝０
ｎ＝１１３の既約多項式は、
ｚ１１３＋ｚ９＋１＝０
を用いた。
計算量は次の通りとなった。
ｎ＝８３：Ｓ／Ｍ＝０．１２，Ｉ／Ｍ＝７．９６，ＳＲ／Ｍ＝０．５７，Ｈ／Ｍ＝０．５８
ｎ＝８９：Ｓ／Ｍ＝０．０５，Ｉ／Ｍ＝８．７４，ＳＲ／Ｍ＝０．１４，Ｈ／Ｍ＝０．６１
ｎ＝１１３：Ｓ／Ｍ＝０．０６，Ｉ／Ｍ＝８．５６，ＳＲ／Ｍ＝０．１０，Ｈ／Ｍ＝０．５０
【０２８６】
これらを、ＨａｒｌｅｙＤＢＬの計算量２１Ｍ＋５Ｓ＋１Ｉに適用すると次のようになる。
ｎ＝８３：ＨａｒｌｅｙＤＢＬ２９．５６Ｍ
ｎ＝８９：ＨａｒｌｅｙＤＢＬ２９．９９Ｍ
ｎ＝１１３：ＨａｒｌｅｙＤＢＬ２９．８６Ｍ
【０２８７】
これらを、ＨＥＣ＿ＨＬＶ（ｈ２＝１，ｆ４＝０）の計算量、１９．５Ｍ＋２Ｓ＋１Ｉ＋２．５ＳＲ＋２Ｈ＋２Ｔに適用すると次のようになる。
ｎ＝８３：ＨＥＣ＿ＨＬＶ（ｈ２＝１，ｆ４＝０）３０．２８５Ｍ
ｎ＝８９：ＨＥＣ＿ＨＬＶ（ｈ２＝１，ｆ４＝０）２９．９１Ｍ
ｎ＝１１３：ＨＥＣ＿ＨＬＶ（ｈ２＝１，ｆ４＝０）２９．４３Ｍ
【０２８８】
この場合、ｎ＝８３でＨａｒｌｅｙＤＢＬの方がＨＥＣ＿ＨＬＶよりも２％程度高速である。また、ｎ＝８９，１１３で，それぞれＨＥＣ＿ＨＬＶの方がＨａｒｌｅｙＤＢＬよりもそれぞれ、０．３％，１．５％程度高速である。
【０２８９】
さらに、ＨＥＣ＿ＨＬＶ（ｈ２＝１，ｆ４＝０）にテーブル参照法を適用した場合の計算量、１８Ｍ＋２Ｓ＋１Ｉ＋２ＳＲ＋２Ｈに適用すると次のようになる。
ｎ＝８３：ＨＥＣ＿ＨＬＶ（ｈ２＝１，ｆ４＝０，ｗｉｔｈｔａｂｌｅ−ｌｏｏｋｕｐ）２８．５Ｍ
ｎ＝８９：ＨＥＣ＿ＨＬＶ（ｈ２＝１，ｆ４＝０，ｗｉｔｈｔａｂｌｅ−ｌｏｏｋｕｐ）２８．３４Ｍ
ｎ＝１１３：ＨＥＣ＿ＨＬＶ（ｈ２＝１，ｆ４＝０，ｗｉｔｈｔａｂｌｅ−ｌｏｏｋｕｐ）２７．８８Ｍ
【０２９０】
この場合、ｎ＝８３，８９，１１３で，それぞれＨＥＣ＿ＨＬＶの方がＨａｒｌｅｙＤＢＬよりも，４％，５％，６％程度高速である。
【０２９１】
また、ｈ２＝ｈ１＝１，ｆ４＝０の場合は次の通りとなる。
ＨａｒｌｅｙＤＢＬの計算量１８Ｍ＋７Ｓ＋１Ｉに適用すると次のようになる。
ｎ＝８３：ＨａｒｌｅｙＤＢＬ２７．４Ｍ
ｎ＝８９：ＨａｒｌｅｙＤＢＬ２７．０９Ｍ
ｎ＝１１３：ＨａｒｌｅｙＤＢＬ２６．９８Ｍ
【０２９２】
次に、ＨＥＣ＿ＨＬＶ（ｈ２＝ｈ１＝１，ｆ４＝０）の計算量、１４．５Ｍ＋３Ｓ＋１Ｉ＋２．５ＳＲ＋２Ｈ＋２Ｔに適用すると次のようになる。
ｎ＝８３：ＨＥＣ＿ＨＬＶ（ｈ２＝１，ｆ４＝０）２５．４０５Ｍ
ｎ＝８９：ＨＥＣ＿ＨＬＶ（ｈ２＝１，ｆ４＝０）２４．９６Ｍ
ｎ＝１１３：ＨＥＣ＿ＨＬＶ（ｈ２＝１，ｆ４＝０）２４．４９Ｍ
この場合、ｎ＝８３，８９，１１３で、それぞれＨＥＣ＿ＨＬＶの方がＨａｒｌｅｙＤＢＬよりも、７％，８％，１０％程度高速である。
【０２９３】
さらに、ＨＥＣ＿ＨＬＶ（ｈ２＝ｈ１＝１，ｆ４＝０）にテーブル参照法を適用した場合の計算量、１４Ｍ＋３Ｓ＋１Ｉ＋２ＳＲ＋２Ｈに適用すると次のようになる。
ｎ＝８３：ＨＥＣ＿ＨＬＶ（ｈ２＝ｈ１＝１，ｆ４＝０，ｗｉｔｈｔａｂｌｅ−ｌｏｏｋｕｐ）２４．６２Ｍ
ｎ＝８９：ＨＥＣ＿ＨＬＶ（ｈ２＝ｈ１＝１，ｆ４＝０，ｗｉｔｈｔａｂｌｅ−ｌｏｏｋｕｐ）２４．３９Ｍ
ｎ＝１１３：ＨＥＣ＿ＨＬＶ（ｈ２＝ｈ１＝１，ｆ４＝０，ｗｉｔｈｔａｂｌｅ−ｌｏｏｋｕｐ）２３．９４Ｍ
この場合、ｎ＝８３，８９，１１３で、それぞれＨＥＣ＿ＨＶＬの方がＨａｒｌｅｙＤＢＬよりも，１０％，８％，１１％程度高速である。
【０２９４】
また、ｈ２＝ｈ１＝ｈ０＝１，ｆ４＝０の場合は次の通りとなる。
ＨａｒｌｅｙＤＢＬの計算量１５Ｍ＋７Ｓ＋１Ｉに適用すると次のようになる。
ｎ＝８３：ＨａｒｌｅｙＤＢＬ２３．８Ｍ
ｎ＝８９：ＨａｒｌｅｙＤＢＬ２４．０９Ｍ
ｎ＝１１３：ＨａｒｌｅｙＤＢＬ２３．９８Ｍ
【０２９５】
次に、ＨＥＣ＿ＨＬＶ（ｈ２＝ｈ１＝ｈ０＝１，ｆ４＝０）の計算量１３．５Ｍ＋３Ｓ＋１Ｉ＋２．５ＳＲ＋２Ｈ＋２Ｔに適用すると次のようになる。
ｎ＝８３：ＨＥＣ＿ＨＬＶ（ｈ２＝ｈ１＝ｈ０＝１，ｆ４＝０）２４．４０５Ｍ
ｎ＝８９：ＨＥＣ＿ＨＬＶ（ｈ２＝ｈ１＝ｈ０＝１，ｆ４＝０）２３．９６Ｍ
ｎ＝１１３：ＨＥＣ＿ＨＬＶ（ｈ２＝ｈ１＝ｈ０＝１，ｆ４＝０）２３．４９Ｍ
この場合、ｎ＝８３でＨａｒｌｅｙＤＢＬの方がＨＥＣ＿ＨＬＶよりも、２％程度高速である。また、ｎ＝８９，１１３では、それぞれＨＥＣ＿ＨＬＶの方がＨａｒｌｅｙＤＢＬよりも０．５％，２％程度高速である。
【０２９６】
さらに、ＨＥＣ＿ＨＬＶ（ｈ２＝ｈ１＝ｈ０＝１，ｆ４＝０）にテーブル参照法を適用した場合の計算量１３Ｍ＋３Ｓ＋１Ｉ＋２ＳＲ＋２Ｈに適用すると次のようになる。
ｎ＝８３：ＨＥＣ＿ＨＬＶ（ｈ２＝ｈ１＝ｈ０＝１，ｆ４＝０，ｗｉｔｈｔａｂｌｅ−ｌｏｏｋｕｐ）２３．６２Ｍ
ｎ＝８９：ＨＥＣ＿ＨＬＶ（ｈ２＝ｈ１＝ｈ０＝１，ｆ４＝０，ｗｉｔｈｔａｂｌｅ−ｌｏｏｋｕｐ）２３．３９Ｍ
ｎ＝１１３：ＨＥＣ＿ＨＬＶ（ｈ２＝ｈ１＝ｈ０＝１，ｆ４＝０，ｗｉｔｈｔａｂｌｅ−ｌｏｏｋｕｐ）２２．９４Ｍ
この場合、ｎ＝８３，８９，１１３で，それぞれＨＥＣ＿ＨＬＶの方がＨａｒｌｅｙＤＢＬよりも、１％，３％，４％程度高速である。
【０２９７】
以上より、ほとんどの場合で、ＨＥＣ＿ＨＬＶの方がＨａｒｌｅｙＤＢＬよりも高速であることが言える。特に、曲線パラメータが、ｈ２＝ｈ１＝１，ｆ４＝０の場合は、全ての場合においてＨＥＣ＿ＨＬＶの方がＨａｒｌｅｙＤＢＬよりも高速である。
【０２９８】
次に、スカラー倍算における計算量を考える。上記の例で、ＨＥＣ＿ＨＬＶの方がＨａｒｌｅｙＤＢＬよりも高速な場合は、加算と１／２倍算の組み合わせによるスカラー倍算の方が、加算と２倍算の組み合わせによるスカラー倍算よりも高速である。次に具体的にスカラー倍算の計算量を比較してみる。曲線は，ｈ２＝ｈ１＝１，ｆ４＝０を用いる。また、スカラー倍算アルゴリズムは、前述のＮＡＦ＋ｂｉｎａｒｙ法（アルゴリズム１６ａ［Ａｌｇｏｒｉｔｈｍ１６ａ］）を用いる。このアルゴリズムにおいて、ステップ１，２がスカラー倍算全体に占める割合は非常に小さいため、これらの計算量は無視する。ここで、正規基底および多項式基底ともにｎ＝８３，８９，１１３の場合で計算量を考えてみる。また、ベースポイントの位数は、ｎ＝８３，８９，１１３に対してそれぞれ１６５ビット、１７７ビット、２２５ビットと仮定する。また、ステップ４の繰り返し部分では、ベースポイントの位数のビット数だけ繰り返す。因子の加算は文献［T.Lange, Efficient arithmetic on genus 2 hyperelliptic curves over finite fields via explicit formulae. Cryptology ePrint Archive, 2002/121, IACR, 2002.］を用いる。ただし、曲線パラメータはｈ２＝ｈ１＝１，ｆ４＝０とする。
【０２９９】
この場合の因子の加算に必要な計算量は２１Ｍ＋３Ｓ＋１Ｉである。スカラー値はＮＡＦを使い｛−１，０，１｝で表現する。スカラー値をｍとした場合、非零のビットは、おおよそｍ／３個ある。よってＮＡＦ＋ｂｉｎａｒｙ法の計算量は、（（加算・減算の計算量）／３＋（１／２倍算ｏｒ２倍算の計算量））ｘ（ベースポイントの位数のビット数）で計算する。
【０３００】
まずは、正規基底の場合から見てみる。Ｉ＝８Ｍと仮定する。
ｈ２＝ｈ１＝１，ｆ４＝０の場合、
ｎ＝８３：加算・２倍算  ５８８５Ｍ
ｎ＝８９：加算・２倍算  ６３１３Ｍ
ｎ＝１１３：加算・２倍算  ８０２５Ｍ
【０３０１】
ｈ２＝ｈ１＝１，ｆ４＝０の場合、
ｎ＝８３：加算・１／２倍算  ５３０７．５Ｍ
ｎ＝８９：  加算・１／２倍算  ５６９３．５Ｍ
ｎ＝１１３：  加算・１／２倍算  ７２３７．５Ｍ
【０３０２】
ｈ２＝ｈ１＝１，ｆ４＝０＋テーブル参照法の場合、
ｎ＝８３：加算・１／２倍算  ５２２５Ｍ
ｎ＝８９：加算・１／２倍算  ５６０５Ｍ
ｎ＝１１３：加算・１／２倍算  ７１２５Ｍ
【０３０３】
次に、多項式基底の場合を考える。
ｈ２＝ｈ１＝１，ｆ４＝０の場合、
ｎ＝８３：加算・２倍算  ６１１６Ｍ
ｎ＝８９：加算・２倍算  ６５０５．９３Ｍ
ｎ＝１１３：加算・２倍算  ８２４５．５Ｍ
【０３０４】
ｈ２＝ｈ１＝１，ｆ４＝０の場合、
ｎ＝８３：加算・１／２倍算  ５７８６．８２Ｍ
ｎ＝８９：加算・１／２倍算  ６１２８．９２Ｍ
ｎ＝１１３：加算・１／２倍算  ７６８５．２５Ｍ
【０３０５】
ｈ２＝ｈ１＝１，ｆ４＝０＋テーブル参照法の場合、
ｎ＝８３：加算・１／２倍算  ５６５７．３Ｍ
ｎ＝８９：加算・１／２倍算  ６０２８．０３Ｍ
ｎ＝１１３：加算・１／２倍算  ７５６１．５Ｍ
【０３０６】
正規基底の場合は１０〜１１％程度、多項式基底の場合は５〜８％程度（加算・１／２倍算のスカラー倍）の方が（加算・２倍算のスカラー倍）よりも高速であることが言える。
【０３０７】
以上、説明したように、本発明の処理によれば、楕円曲線暗号の１／２倍算を、超楕円曲線暗号に拡張し、高速演算が実現される。
【０３０８】
超楕円曲線上の因子の演算を使う暗号処理演算において、処理の重い演算は因子のスカラー倍算である。上述した本発明の処理によりスカラー倍算を高速化することで超楕円曲線暗号の処理を大幅に改善することができる。
【０３０９】
前述したように、超楕円曲線暗号（ＨＥＣＣ）は楕円曲線暗号（ＥＣＣ）を一般化した概念であり、現在、様々な分野で適用されている楕円曲線暗号（ＥＣＣ）を使った暗号処理、具体的には署名処理、暗号データの生成、復号処理、暗号鍵共有処理、認証処理などに、本発明を適用することが可能である。楕円曲線暗号（ＥＣＣ）における演算処理中のスカラー倍算の部分を、上述したスカラー倍算に置き換えることで、演算の高速化が可能となる。
【０３１０】
［暗号処理装置の機能構成について］
図７に、本発明の暗号処理装置の機能構成を示すブロック図を示す。暗号処理装置１００は、超楕円曲線暗号に基づく暗号処理演算を実行する暗号処理装置１００であり、因子Ｄをベースポイントとして生成するベースポイント生成部１０１、前述の処理例５において説明したテーブル、すなわち、予め固定された因子Ｄについての［１／２ｉＤ］計算値に基づいて、ｋ１，ｋ１'，（ｋ０，ｋ０'）のいずれが正しいかを記録したテーブルを格納した記憶部１０２と、演算実行部１０３を有する。
【０３１１】
演算実行部１０３は、超楕円曲線の因子Ｄに対するスカラー倍算の演算において、演算処理として、１／２倍算を含む演算を実行する。具体的には、種数２、標数２のランダムパラメータを持つ超楕円曲線の因子Ｄに対するスカラー倍算において１／２倍算を含む演算を実行する。例えば、種数２、標数２のｈ（ｘ）＝ｘ２＋ｘ＋ｈ０，ｆ４＝０をパラメータに持つ超楕円曲線の因子Ｄに対するスカラー倍算、あるいは、種数２、標数２のｈ（ｘ）＝ｘをパラメータに持つ超楕円曲線の因子Ｄに対するスカラー倍算において１／２倍算を含む演算を実行する。
【０３１２】
［電子署名生成および検証アルゴリズムにおける本発明の適用例］
以下に本発明の処理を適用可能な具体的な暗号処理アルゴリズムの例として、楕円曲線暗号を適用した電子署名生成および検証アルゴリズムであるＥＣＤＳＡ（ＥＣ−Ｄｉｇｉｔａｌ Ｓｉｇｎａｔｕｒｅ Ａｌｇｏｒｉｔｈｍ）のスカラー倍算に本発明の演算手法を適用した場合について説明する。ＩＥＥＥ１３６３によるとＥＣＤＳＡによる署名生成、検証は以下のシーケンスによって実行される。
【０３１３】
（１）入力
（１−１）楕円曲線のドメインパラメータ及びベースポイントＧ（位数ｒ）
（１−２）署名者の秘密鍵ｓ
（１−３）平文Ｍ
（２）鍵生成
（２−１）秘密鍵ｓに対してＷ＝ｓＧを公開鍵とする
（３）署名生成
（３−１）ランダムな整数０＜ｕ＜ｒを生成
（３−２）Ｖ＝ｕＧ＝（ｘｖ、ｙｖ）を計算
（３−３）ｘｖを整数に変換し、ｉとする
（３−４）ｃ＝ｉ  ｍｏｄ  ｒを計算。ｃ＝０ならｓｔｅｐ３−１へ
（３−５）ｆ＝ｈ（Ｍ）、ｈはｈａｓｈ関数
（３−６）ｄ＝ｕ−１（ｆ＋ｓｃ）ｍｏｄ  ｒを計算。ｄ＝０ならｓｔｅｐ３−１へ
（３−７）（ｃ、ｄ）を平文Ｍに対する署名にする。
（４）署名検証
（４−１）０＜ｃ＜ｒ、０＜ｄ＜ｒをチェック。該当しない場合ｉｎｖａｌｉｄを出力
（４−２）ｈ＝ｄ−１ｍｏｄ  ｒ、ｈ１＝ｆｈ  ｍｏｄ  ｒ、ｈ２＝ｃｈ  ｍｏｄ  ｒを計算。
（４−３）Ｐ＝（ｘｐ、ｙｐ）＝ｈ１Ｇ＋ｈ２Ｗを計算。Ｐ＝Ｏならばｉｎｖａｌｉｄを出力
（４−４）ｘｐを整数に変換し、ｉとする。
（４−５）ｃ'＝ｉ  ｍｏｄ  ｒを計算する。
（４−６）ｃ'＝ｃならばｖａｌｉｄを出力。そうでないならばｉｎｖａｌｉｄを出力。
【０３１４】
上記アルゴリズムにおいて下記の処理が超楕円曲線を用いた本提案法が適用できる箇所である。
（２−１）秘密鍵ｓに対してＷ＝ｓＧを公開鍵とする
（３−２）Ｖ＝ｕＧ＝（ｘｖ、ｙｖ）を計算
（４−３）Ｐ＝（ｘｐ、ｙｐ）＝ｈ１Ｇ＋ｈ２Ｗを計算。Ｐ＝Ｏならばｉｎｖａｌｉｄを出力
【０３１５】
これらの各ステップ（２−１），（３−２），（４−３）における演算処理、Ｗ＝ｓＧ、Ｖ＝ｕＧ、Ｐ＝（ｘｐ、ｙｐ）＝ｈ１Ｇ＋ｈ２Ｗで、ｓＧ、ｕＧ、ｈ１Ｇ、ｈ２Ｗの演算処理は、因子のスカラー倍算処理であり、本発明の適用による高速化が可能となる。さらにｓＧ、ｕＧ、ｈ１Ｇの演算処理は、固定因子のスカラー倍算処理であり、本発明のテーブル参照法の適用による高速化が可能となる。
【０３１６】
［暗号処理装置のハードウェア構成例］
最後に、上述の暗号処理を実行するデバイスとしてのＩＣモジュール２００の構成例を図８に示す。上述の処理は、例えばＰＣ、ＩＣカード、リーダライタ、その他、様々な情報処理装置において実行可能であり、図８に示すＩＣモジュール２００は、これら様々な機器に構成することが可能である。
【０３１７】
図８に示すＣＰＵ(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)
２０２  メモリ
２０３  暗号処理部
２０４  乱数発生器
２０５  送受信部
【図１】
2006227562.tif 000047
【図２】
2006227562.tif 000048
【図３】
2006227562.tif 000049
【図４】
2006227562.tif 000050
【図５】
2006227562.tif 000051
【図６】
2006227562.tif 000052
【図７】
2006227562.tif 000053
【図８】
2006227562.tif 000054