(57)【要約】【課題】  超楕円暗号処理において高速演算を実現する装置および方法を実現する。【解決手段】  超楕円曲線の種数ｇ（ｇｅｎｕｓ）より小さいウェイト（ｗｅｉｇｈｔ）ｇ０（ただし、１≦ｇ０＜ｇ）の因子をベースポイントとして生成し、スカラー倍算処理を実行する。本構成により、スカラー倍算処理において実行する演算処理を、種数ｇ＝２の超楕円曲線暗号においては、Ｈａｒｌｅｙ  ＡＤＤから、演算ステップ数の少ないＥｘＨａｒＡＤＤ２＋１→２の実行ステップに変更し、また、種数ｇ＝３の超楕円曲線暗号においては、Ｈａｒｌｅｙ  ＡＤＤから演算ステップ数の少ないＥｘＨａｒＡＤＤ３＋２→３、またはＥｘＨａｒＡＤＤ３＋１→３の実行に変更することが可能となり、高速な演算処理が実現される。【選択図】  図４
2005258228.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）方式がある。超楕円曲線暗号方式については、例えば非特許文献１、非特許文献２に記載されている。
【００１０】
楕円曲線暗号では有限体Ｆｑ上で定義される楕円曲線上の点をＰとし、スカラー倍算した点ｋＰ（ｋ∈Ｚ）をＱとすると、Ｑからｋを求める問題は離散対数問題に帰着できる。一方、超楕円曲線暗号では点の形式的和である因子（ｄｉｖｉｓｏｒ）をＤ１とし、スカラー倍算ｋＤ１で定義される因子をＤ２とすると、Ｄ２からｋを求める問題は超楕円曲線におけるヤコビ多様体上の離散対数問題として公開鍵暗号として用いることができる。
【００１１】
超楕円曲線では曲線を特徴づける値は種数（ｇｅｎｕｓ）ｇである。ｐを素数、ｎを正の整数、ｑ＝ｐｎとする。このとき有限体Ｆｑ上で定義される種数ｇの超楕円曲線Ｃは以下の方程式、
ｙ２＋ｈ（ｘ）ｙ＝ｆ（ｘ）
で定義される。ここで、ｈ（ｘ），ｆ（ｘ）∈Ｆｑ［ｘ］，ｆ（ｘ）は、は次数２ｇ＋１のｍｏｎｉｃ多項式である。
【００１２】
超楕円曲線Ｃ上の点Ｐ＝（ｘ、ｙ）に対してｏｐｐｏｓｉｔｅな点−Ｐは（ｘ、ｙ＋ｈ（ｘ））として定義される。Ｐ＝−Ｐである点を分岐点（ｒａｍｉｆｉｃａｔｉｏｎ  ｐｏｉｎｔ）と呼ぶ。
【００１３】
超楕円曲線暗号の定義体の演算サイズ（ビット長）は楕円曲線暗号と同等の安全性を仮定した場合、楕円曲線の定義体の演算サイズに比べて１／ｇに小さくなることが知られている。演算サイズが小さいことは実装上メリットがあり、超楕円曲線暗号の利点の一つして挙げられる。
【００１４】
次に、超楕円曲線暗号の基本事項について説明する。前述したように、超楕円曲線暗号では点の形式的和である因子（ｄｉｖｉｓｏｒ）をＤ１とし、スカラー倍算ｋＤ１で定義される因子をＤ２とすると、Ｄ２からｋを求める問題は超楕円曲線におけるヤコビ多様体上の離散対数問題として公開鍵暗号として用いることができる。
【００１５】
ここで、因子（ｄｉｖｉｓｏｒ）は以下の形式で表現することができる。
【数１】
2005258228.tif 000003
【００１６】
但しＰｉ＝（ｘｉ、ｙｉ）かつｉ≠ｊに対してＰｉ≠Ｐｊである。この形式の因子の表現を半被約因子（ｓｅｍｉ  ｒｅｄｕｃｅｄ  ｄｉｖｉｓｏｒ）とよぶ。
【００１７】
また、ΣｍｉをＤのウェイト（ｗｅｉｇｈｔ）と呼ぶ。さらにウェイト（ｗｅｉｇｈｔ）が種数ｇ以下である半被約因子を被約因子（ｒｅｄｕｃｅｄ  ｄｉｖｉｓｏｒ）と呼ぶ。
【００１８】
超楕円曲線のヤコビ（Ｊａｃｏｂｉ）多様体上の任意の半被約因子Ｄは下記の多項式Ｕ、Ｖ∈Ｆｑ［ｘ］を用いてＤ＝（Ｕ、Ｖ）として表現できる。これをマンホード（Ｍｕｍｆｏｒｄ）表現と呼ぶ。なお、マンホード（Ｍｕｍｆｏｒｄ）表現については、例えば非特許文献３に記載されている。
【数２】
2005258228.tif 000004
【００１９】
種数（ｇｅｎｕｓ）２の任意の被約因子Ｄはマンホード（Ｍｕｍｆｏｒｄ）表現を用いると、有限体Ｆｑ上の元を係数に持つ２次以下の多項式の組、すなわち、
（Ｕ、Ｖ）＝（ｘ２＋ｕ１ｘ＋ｕ０、ｖ１ｘ＋ｖ０）
として表現することができる。
また、種数（ｇｅｎｕｓ）３の任意の被約因子Ｄはマンホード（Ｍｕｍｆｏｒｄ）表現を用いると有限体Ｆｑ上の元を係数に持つ３次以下の多項式の組、すなわち、
（Ｕ、Ｖ）＝（ｘ３＋ｕ２ｘ２＋ｕ１ｘ＋ｕ０、ｖ２ｘ２＋ｖ１ｘ＋ｖ０）
として表現できる。
【００２０】
他の因子の表現として変形Ｍｕｍｆｏｒｄ表現、Ｗｅｉｇｈｔｅｄ  Ｃｏｏｒｄｉｎａｔｅがある。変形Ｍｕｍｆｏｒｄ表現はＥＣＣ（楕円曲線暗号）でいうプロジェクティブ（ｐｒｏｊｅｃｔｉｖｅ）座標に相当し、Ｍｕｍｆｏｒｄ表現（Ｕ、Ｖ）に定数Ｚ倍し、（Ｕ、Ｖ、Ｚ）で表現するものである。
【００２１】
Ｗｅｉｇｈｔｅｄ  Ｃｏｏｒｄｉｎａｔｅも同様にＭｕｍｆｏｒｄ表現に複数の定数（Ｚ１、Ｚ２）をかけることで（Ｕ、Ｖ、Ｚ１、Ｚ２）で表現する方法である。いずれも下記に述べるＨａｒｌｅｙのアルゴリズムの計算量を削減するための手法として用いられている。
【００２２】
以下、超楕円曲線における
［１］加算処理（２倍算を含む）
［２］スカラー倍算処理
［３］ベースポイント生成処理
の各処理について説明する。
なお、以下、本明細書において、因子Ｄは、特に断りがない限り被約因子（ｒｅｄｕｃｅｄ  ｄｉｖｉｓｏｒ）であるものとする。すなわち、ウェイト（ｗｅｉｇｈｔ）が種数ｇ以下である半被約因子としての被約因子（ｒｅｄｕｃｅｄ  ｄｉｖｉｓｏｒ）であるものとする。
【００２３】
［１］加算処理（２倍算を含む）
まず、超楕円曲線における加算アルゴリズムについて説明する。
因子のスカラー倍算は加算アルゴリズムと呼ばれる因子の加算と２倍算の組み合わせで計算することができる。以下ではこれまでに知られている加算アルゴリズムについて説明する。
【００２４】
最初に提案された実用的なアルゴリズムはＣａｎｔｏｒのアルゴリズムである。このアルゴリズムについては、例えば非特許文献１、非特許文献２に記載されている。このアルゴリズムはあらゆる種数の超楕円曲線上の因子に対して適用可能なアルゴリズムであるが、楕円曲線に比べてアルゴリズムが複雑で計算量が多いことが欠点である。
【００２５】
Ｈａｒｌｅｙは種数２の超楕円曲線に限定し、因子のｗｅｉｇｈｔの場合分けをおこない、それぞれの場合で最適化を行うことでより計算量の少ないアルゴリズムを提案した。この研究を受けて超楕円曲線暗号（ＨＥＣＣ）における演算アルゴリズムの改良、拡張の研究が近年盛んになっている。
【００２６】
Ｈａｒｌｅｙのアルゴリズムは定義体を素体、種数２の曲線、因子の表現はＭｕｍｆｏｒｄ表現を用いている。このアルゴリズムの計算量の改善の研究例として、例えば、非特許文献４、非特許文献５、非特許文献６などが挙げられる。さらに、定義体を２の拡大体の場合について拡張した処理例について、非特許文献７、非特許文献８に報告されている。また、種数が３の場合のＨａｒｌｅｙのアルゴリズムへの拡張処理については、非特許文献９、非特許文献１０に報告されている。また、因子の表現に拡張Ｍｕｍｆｏｒｄ表現、Ｗｅｉｇｈｔｅｄ  Ｃｏｏｒｄｉｎａｔｅを用いることで計算量を削減した研究として非特許文献１１、非特許文献１２、非特許文献６、非特許文献１３がある。
【００２７】
Ｈａｒｌｅｙアルゴリズムの処理について、図１および図２を参照して説明する。図１（Ａ）は、種数２の場合の因子の加算Ｄ１＋Ｄ２の処理例を示した図である。なお、因子Ｄ１、Ｄ２は、それぞれＤ１＝（Ｕ１、Ｖ１）、Ｄ２＝（Ｕ２、Ｖ２）とする。まず、因子のウェイト（ｗｅｉｇｈｔ）の値によって場合分けが行われる。すなわち、［Ｄ１＋Ｄ２］の各ウェイト（ｗｅｉｇｈｔ）の値によって、
（１）ｗｅｉｇｈｔ２＋ｗｅｉｇｈｔ２
（２）ｗｅｉｇｈｔ２＋ｗｅｉｇｈｔ１
（３）例外処理１
の場合分けが行なわれる。
【００２８】
次にｗｅｉｇｈｔ２同士の加算、すなわち（１）ｗｅｉｇｈｔ２＋ｗｅｉｇｈｔ２の場合、因子Ｄ１＝（Ｕ１、Ｖ１）、Ｄ２＝（Ｕ２、Ｖ２）について、最大公約数ｇｃｄ（Ｕ１、Ｕ２）＝１であれば、２つの因子Ｄ１＝（Ｕ１、Ｖ１）、Ｄ２＝（Ｕ２、Ｖ２）は、互いに同一またはオポジット（ｏｐｐｏｓｉｔｅ）な点を含まない。この場合、
（１ａ）ＨａｒｌｅｙＡＤＤ、
すなわちハーレーアルゴリズムに従った加算処理を行う。（１ａ）ＨａｒｌｅｙＡＤＤの処理は例えば非特許文献７に示されているＭｏｓｔ  Ｆｒｅｑｕｅｎｔ  Ｃａｓｅと呼ばれる処理である。このＭｏｓｔ  Ｆｒｅｑｕｅｎｔ  Ｃａｓｅは、種数２の場合の因子の加算Ｄ１＋Ｄ２処理において、高確率で発生するケースである。
【００２９】
種数２の加算処理におけるＭｏｓｔ  Ｆｒｅｑｕｅｎｔ  Ｃａｓｅで実行するＨａｒｌｅｙＡＤＤの処理を、以下のテーブル１［Ｔａｂｌｅ１］に示す。
【数３】
2005258228.tif 000005
【００３０】
この（１ａ）ＨａｒｌｅｙＡＤＤの処理は、後述するように非常に高い確率でおこる。その他の例外処理の起こる確率は非常に低い。Ｍｏｓｔ  Ｆｒｅｑｕｅｎｔ  Ｃａｓｅの条件を満たさない場合、すなわち、因子Ｄ１＝（Ｕ１、Ｖ１）、Ｄ２＝（Ｕ２、Ｖ２）について、最大公約数ｇｃｄ（Ｕ１、Ｕ２）＝１を満足しない場合は、
（１ｂ）例外処理２を行う。
【００３１】
（２）ｗｅｉｇｈｔ２＋ｗｅｉｇｈｔ１の場合についても同様に、ｇｃｄ（Ｕ１、Ｕ２）＝１かどうかをチェックし、ｇｃｄ（Ｕ１、Ｕ２）＝１を満足する場合には、
（２ａ）ＥｘＨａｒＡＤＤ２＋１→２を実行し、
ｇｃｄ（Ｕ１、Ｕ２）＝１を満足しない場合には、
（２ｂ）例外処理３を行う。
【００３２】
（２ａ）ＥｘＨａｒＡＤＤ２＋１→２のアルゴリズムは非特許文献８に示されている。ＥｘＨａｒＡＤＤ２＋１→２の処理を、以下のテーブル３［Ｔａｂｌｅ３］に示す。
【数４】
2005258228.tif 000006
【００３３】
（３）例外処理１は、ｗｅｉｇｈｔの場合分けが上記（１），（２）以外の場合である。
【００３４】
種数２の場合の２倍算の流れを図１（Ｂ）に示す。２倍算は、Ｄ＋Ｄ＝２Ｄの処理である。加算の場合と同様に因子Ｄのｗｅｉｇｈｔが
（４）ｗｅｉｇｈｔ２、
（５）ｗｅｉｇｈｔ１、
（６）ｗｅｉｇｈｔ０、
によってそれぞれ異なる処理を行う。
【００３５】
（４）ｗｅｉｇｈｔ２の場合、因子が分岐点を含むかどうかをチェックし、含まなければ、（４ａ）ＨａｒｌｅｙＤＢＬの処理を行う。因子が分岐点を含む場合は（４ｂ）例外処理６を行う。
【００３６】
（４ａ）ＨａｒｌｅｙＤＢＬの処理アルゴリズムは例えば非特許文献７にＭｏｓｔ  Ｆｒｅｑｕｅｎｔ  Ｃａｓｅとして示されている。ＨａｒｌｅｙＤＢＬの処理アルゴリズムを、以下のテーブル２［Ｔａｂｌｅ２］に示す。
【数５】
2005258228.tif 000007
【００３７】
次に、種数３の場合における加算、２倍算について、図２を参照して説明する。種数３においても、種数２の場合と基本的な考え方は同じであるが、種数３の場合、因子の最大のｗｅｉｇｈｔが３になるため、場合分けの数は種数２に比べて非常に多くなることが特徴である。
【００３８】
図２（Ａ）加算において、因子Ｄ１、Ｄ２は、それぞれＤ１＝（Ｕ１、Ｖ１）、Ｄ２＝（Ｕ２、Ｖ２）とする。まず、因子のウェイト（ｗｅｉｇｈｔ）の値によって場合分けが行われる。すなわち、［Ｄ１＋Ｄ２］の各ウェイト（ｗｅｉｇｈｔ）の値によって、
（１）ｗｅｉｇｈｔ３＋ｗｅｉｇｈｔ３
（２）ｗｅｉｇｈｔ３＋ｗｅｉｇｈｔ２
（３）ｗｅｉｇｈｔ３＋ｗｅｉｇｈｔ１
（４）例外処理７
の場合分けが行なわれる。
【００３９】
さらに、（１）ｗｅｉｇｈｔ３＋ｗｅｉｇｈｔ３の場合において、因子Ｄ１＝（Ｕ１、Ｖ１）、Ｄ２＝（Ｕ２、Ｖ２）について、最大公約数ｇｃｄ（Ｕ１、Ｕ２）＝１を満足する場合は、
（１ａ）ＨａｒｌｅｙＡＤＤ
を実行する。これが種数３の加算処理における最も高確率で発生するケース、すなわち、Ｍｏｓｔ  Ｆｒｅｑｕｅｎｔ  Ｃａｓｅである。
【００４０】
種数３の加算処理におけるＭｏｓｔ  Ｆｒｅｑｕｅｎｔ  ＣａｓｅとしてのＨａｒｌｅｙＡＤＤは例えば非特許文献９，１０に示されている。種数３の加算処理におけるＭｏｓｔ  Ｆｒｅｑｕｅｎｔ  ＣａｓｅとしてのＨａｒｌｅｙＡＤＤのアルゴリズムを以下のテーブル［Ｔａｂｌｅ４］に示す。
【数６】
2005258228.tif 000008
【００４１】
同様に、（２）ｗｅｉｇｈｔ３＋ｗｅｉｇｈｔ２の場合において、因子Ｄ１＝（Ｕ１、Ｖ１）、Ｄ２＝（Ｕ２、Ｖ２）について、最大公約数ｇｃｄ（Ｕ１、Ｕ２）＝１を満足する場合は、
（２ａ）ＥｘＨａｒＡＤＤ３＋２→３、
を実行する。
最大公約数ｇｃｄ（Ｕ１、Ｕ２）＝１を満足しない場合は、
（２ｂ）例外処理９
を実行する。
【００４２】
同様に、（３）ｗｅｉｇｈｔ３＋ｗｅｉｇｈｔ１の場合において、因子Ｄ１＝（Ｕ１、Ｖ１）、Ｄ２＝（Ｕ２、Ｖ２）について、最大公約数ｇｃｄ（Ｕ１、Ｕ２）＝１を満足する場合は、
（３ａ）ＥｘＨａｒＡＤＤ３＋１→３、
を実行する。
最大公約数ｇｃｄ（Ｕ１、Ｕ２）＝１を満足しない場合は、
（３ｂ）例外処理１０
を実行する。
【００４３】
それぞれのアルゴリズムは文献等に明示的に示されていないので、定義体がＦ２ｎの場合の公式を導出した。その結果としてのＥｘＨａｒＡＤＤ３＋１→３、およびＥｘＨａｒＡＤＤ３＋２→３のアルゴリズムを、以下のテーブル［Ｔａｂｌｅ６］、［Ｔａｂｌｅ７］に示す。
【数７】
2005258228.tif 000009
【００４４】
【数８】
2005258228.tif 000010
【００４５】
種数３の場合の２倍算の流れを図２（Ｂ）に示す。２倍算は、Ｄ＋Ｄ＝２Ｄの処理である。加算の場合と同様に因子Ｄのｗｅｉｇｈｔが
（４）ｗｅｉｇｈｔ３、
（５）ｗｅｉｇｈｔ２、
（６）ｗｅｉｇｈｔ１、
（７）ｗｅｉｇｈｔ０、
によってそれぞれ異なる処理を行う。
【００４６】
（４）ｗｅｉｇｈｔ３の場合、因子が分岐点を含むかどうかをチェックし、含まなければ、（４ａ）ＨａｒｌｅｙＤＢＬの処理を行う。因子が分岐点を含む場合は（４ｂ）例外処理１１を行う。
【００４７】
（４ａ）ＨａｒｌｅｙＤＢＬの処理アルゴリズムは例えば非特許文献９，１０にＭｏｓｔ  Ｆｒｅｑｕｅｎｔ  Ｃａｓｅとして示されている。ＨａｒｌｅｙＤＢＬの処理アルゴリズムを、以下のテーブル５［Ｔａｂｌｅ５］に示す。
【数９】
2005258228.tif 000011
【００４８】
種数２、３共にＨａｒｌｅｙＡＤＤ、ＨａｒｌｅｙＤＢＬはｍｏｓｔ  ｆｒｅｑｕｅｎｔ  ｃａｓｅと呼ばれ、ランダムに因子を発生させて加算または２倍算を行うと、非常に高い確率でＨａｒｌｅｙＡＤＤ、ＨａｒｌｅｙＤＢＬの処理になる。なお、このＨａｒｌｅｙＡＤＤ、ＨａｒｌｅｙＤＢＬが、ｍｏｓｔ  ｆｒｅｑｕｅｎｔ  ｃａｓｅとなることの説明は、例えば非特許文献１４に説明されている。
【００４９】
非特許文献１４によると、このｍｏｓｔ  ｆｒｅｑｕｅｎｔ  ｃａｅｓ以外の処理になる確率はＯ（１／ｑ）である。ここでｑは定義体の要素数であり、安全な暗号用途ではqgが１６０ｂｉｔ程度必要になる大きな数であるので現実的にはＨａｒｌｅｙＡＤＤ、ＨａｒｌｅｙＤＢＬしか発生しない状況とみなすことができる。
【００５０】
従って超楕円曲線暗号（ＨＥＣＣ）の加算アルゴリズムをＨａｒｌｅｙアルゴリズムまたはその改良アルゴリズムを使って、例えばＩＣカードなどの暗号処理演算手段として実装する場合、
ＨａｒｌｅｙＡＤＤ、
ＨａｒｌｅｙＤＢＬ
だけを実装し、その他の確率的にほとんど起こらない複雑な例外処理についての演算を実行しない実装とする場合も多い。この場合、例外処理については、ｗｅｉｇｈｔの場合分けが必要のないＣａｎｔｏｒのアルゴリズムを実行する構成とするなどの方法が適用される。種数が高くなるほど複雑な例外処理の負担は増すため、非特許文献９，１０ではこの実装方法について説明している。
【００５１】
［２］スカラー倍算について
次に超楕円曲線暗号（ＨＥＣＣ）アルゴリズムにおける因子のスカラー倍算について説明する。
【００５２】
超楕円曲線暗号（ＨＥＣＣ）アルゴリズムにおいて、因子のスカラー倍算は、超楕円加算と超楕円２倍算の組み合わせで計算することができる。スカラー倍算のアルゴリズムとして基本的なｂｉｎａｒｙ法とｄｏｕｂｌｅ−ａｎｄ−ａｄｄ−ａｌｗａｙｓ法を例に挙げて説明する。
【００５３】
ここでｄの２進数表現を、
（ｄｌ−１、・・・・・、ｄ０）、ｄｌ−１＝１、ｄｌ−２，・・・，０＝１ｏｒ０とする。
【００５４】
スカラー倍算のアルゴリズムとして基本的なｂｉｎａｒｙ法の演算アルゴリズムを以下に示す。
【数１０】
2005258228.tif 000012
【００５５】
次に、ｄｏｕｂｌｅ−ａｎｄ−ａｄｄ−ａｌｗａｙｓ法の演算アルゴリズムについて説明する。
【００５６】
暗号技術の実装方法の不具合を利用して秘密情報を知る方法をサイドチャネルアタック（Ｓｉｄｅ  Ｃｈａｎｎｅｌ  Ａｔｔｔａｃｋ、  ＳＣＡ）と呼ぶ。ＳＣＡにはタイミングアタック（ＴＡ：Ｔｉｍｉｎｇ  Ａｔｔａｃｋ）や、単純電力解析（ＳＰＡ：Ｓｉｍｐｌｅ  Ｐｏｗｅｒ  Ａｎａｌｙｓｉｓ）や、差分電力解析（ＤＰＡ：Ｄｉｆｆｅｒｅｎｔｉａｌ  Ｐｏｗｅｒ  Ａｎａｌｙｓｉｓ）といった電力攻撃などがある。タイミングアタック（ＴＡ）については非特許文献１５、電力攻撃については、非特許文献１６に説明がある。
【００５７】
楕円曲線暗号（ＥＣＣ）、および超楕円曲線暗号（ＨＥＣＣ）に対するタイミングアタック（ＴＡ）、および電力攻撃（ＳＰＡ）に対する対策としてｄｏｕｂｌｅ−ａｎｄ−ａｄｄ−ａｌｗａｙｓ法が用いられる。このｄｏｕｂｌｅ−ａｎｄ−ａｄｄ−ａｌｗａｙｓ法についての詳細は、非特許文献１７に説明されている。
【００５８】
スカラー倍算のアルゴリズムとして基本的なｄｏｕｂｌｅ−ａｎｄ−ａｄｄ−ａｌｗａｙｓ法の演算アルゴリズムを以下に示す。
【数１１】
2005258228.tif 000013
【００５９】
［３］ベースポイントの生成
スカラー倍算の計算を暗号技術で用いる場合、入力に必要な因子Ｄ０は、
（１）事前に決めた因子の場合、
（２）事前に決められないランダムに発生する因子の場合、
の２つのタイプに分けることができる。
【００６０】
ここで（１）事前に決めた因子の場合、の入力因子をベースポイントと呼ぶことにする。
一般的なベースポイントの生成アルゴリズムを以下に示す。
（ａ）
定義体Ｆｑ上の元をランダムにｇ個選び、ｇ個の超楕円曲線上の点Ｐｉ（ｉ＝１、…、ｇ）を生成する。
（ａ１）  ランダムに選んだ各元をｘ座標ｘｉ（ｉ＝１…ｇ）とし、次に超楕円曲線上に乗るようにｘｉに対応するｙ座標を求める。
（ｂ）
ベースポイントの因子をＤ０＝（Ｕ（ｘ）、Ｖ（ｘ））とする。
（ｂ１）Ｕ（ｘ）＝（ｘ−ｘ１）（ｘ−ｘ２）…（ｘ−ｘｇ）
（ｂ２）Ｖ（ｘ）＝ｖｇ−１ｘｇ−１＋ｖｇ−２ｘｇ−２＋…＋ｖ０の係数ｖｉを決定する。例えば生成した点が全て異なる場合、Ｖ（ｘｉ）＝ｙｉよりｖｉを求めることができる。
（ｃ）  上記アルゴリズムにより生成される因子はｗｅｉｇｈｔ  ｇの因子となる。
【００６１】
スカラー倍算の計算を暗号技術で用いる場合、入力に必要な因子Ｄ０の生成、すなわちベースポイントの生成において、事前に決めた因子を適用する場合、上述の処理（ａ）〜（ｃ）によってｗｅｉｇｈｔ  ｇのベースポイントに適用する因子を求めることができる。
【非特許文献１】N.Koblitz. Hyperelliptic curve cryptosystems. J.Cryptology, vol.1,No.3, pp.139-150, 1989.
【非特許文献２】D.G.Cantor. Computing in the Jacobian of hyperelliptic curve. Math. Comp., Vol.48, No. 177, pp.95-101, 1987
【非特許文献３】「D. Mumford, Tata lectures on theta II, Progress in Mathematics, no. 43, Birkhauser, 1984.」
【非特許文献４】K.Matsuo, J.Chao, and S.Tsujii. Fast Genus two hyperelliptic curve cryptosystems. Technical Report ISEC2001-31, IEICE Japan, 2001.
【非特許文献５】M.Takahashi. Improving Harley algorithms for Jacobians of genus 2 hyperelliptic curves. SCIS2002. (Japanese).
【非特許文献６】T.Lange. Inversion-free arithmetic on genus 2 hyperelliptic curves. Cryptology ePrint Archive, 2002/147, IACR, 2002.
【非特許文献７】T.Sugizaki, K.Matsuo, J.Chao, and S.Tsujii. An extension of Harley addition algtorithm for hyperelliptic curves over finite fields of characteristic two. ISEC2002-9, IEICE, 2001
【非特許文献８】T.Lange, Efficient arithmetic on genus 2 hyperelliptic curves over finite fields via explicit formulae. Cryptology ePrint Archive, 2002/121, IACR, 2002.
【非特許文献９】J.Kuroki, M.Gonda, K.Masuo, J.Chao and S.Tsujii. Fast genus three hyperellipitc curve cryptosystems. SCIS2002
【非特許文献１０】J.Pelzl, T.Wollinger, J. Guajardo, and C. Paar. Hyperelliptic curve Cryptosystems: Closing the Performance Gap to Elliptic Curves. Cryptology ePrint Archive, 2003/026, IACR, 2003.
【非特許文献１１】Y.Miyamoto, H.Doi, K.Matsuo, J.Chao and S.Tsujii. A fast addition algorithm of genus two hyperelliptic curves. SCIS2002. (Japanese).
【非特許文献１２】N.Takahashi, H.Morimoto and A.Miyaji. Efficient exponentiation on genus two hyperelliptic curves (II). ISEC2002-145, IEICE, 2003. (Japanese)
【非特許文献１３】T.Lange. Weighed coordinate on genus 2 hyperellipitc curve. Cryptology ePrint Archive, 2002/153, IACR, 2002.
【非特許文献１４】N. Nagao. Improving group law algorithms for Jacobians of hyperelliptic curves. ANTS-IV, LNCS 1838, pp.439-448, Springer-Verlag, 2000.
【非特許文献１５】C. Kocher, Timing Attacks on Implementations of Diffie-Hellman, RSA, DSS, and Other Systems, CRYPTO'96, LNCS 1109, pp.104-113, 1996
【非特許文献１６】C. Kocher, J. Jaffe, and B. Jun, Differential Power Analysis, CRYPTO '99, LNCS 1666, pp.388-397, Springer-Verlag, 1999
【非特許文献１７】J.-S. Coron, Resistance against Differential Power Analysis for Elliptic Curve Cryptosystems, CHES'99, LNCS 1717, pp.292-302, Springer-Verlag, 1999
【発明の開示】
【発明が解決しようとする課題】
【００６２】
現在、実用フェーズに入りつつある楕円曲線暗号（ＥＣＣ）アルゴリズムに対して、その拡張概念である超楕円曲線暗号（ＨＥＣＣ）アルゴリズムは、現在、学会レベルで高速アルゴリズムや、その実装方法についての研究が進められている。超楕円曲線暗号（ＨＥＣＣ）のスカラー倍算の演算時間は、楕円曲線暗号（ＥＣＣ）に近づきつつある程度に過ぎず、さらなる高速化が望まれている。
【００６３】
本発明は、このような現状に鑑みてなされたものであり、超楕円曲線暗号（ＨＥＣＣ）のスカラー倍算の演算時間を短縮し、高速処理可能な超楕円曲線暗号（ＨＥＣＣ）演算処理を実現する暗号処理演算方法、および暗号処理装置、並びにコンピュータ・プログラムを提供することを目的とする。
【００６４】
本発明は、通常用いられることのない、ｍｏｓｔ  ｆｒｅｑｕｅｎｔ  ｃａｓｅ以外の演算処理のうち、計算量の少ない演算処理をスカラー倍算の計算に積極的に利用することで、スカラー倍算を高速化し、高速処理可能な超楕円曲線暗号（ＨＥＣＣ）演算処理を実現する暗号処理演算方法、および暗号処理装置、並びにコンピュータ・プログラムを提供する。
【課題を解決するための手段】
【００６５】
本発明の第１の側面は、
超楕円曲線暗号に基づく暗号処理演算を実行する暗号処理演算方法であり、
超楕円曲線の種数ｇ（ｇｅｎｕｓ）より小さいウェイト（ｗｅｉｇｈｔ）ｇ０（ただし、１≦ｇ０＜ｇ）の因子をベースポイントとして生成するベースポイント生成ステップと、
前記ベースポイントとしての因子を含む因子のスカラー倍算処理を実行する演算処理ステップと、
を有することを特徴とする暗号処理演算方法にある。
【００６６】
さらに、本発明の暗号処理演算方法の一実施例において、前記ベースポイント生成ステップは、定義体としての有限体Ｆｑ上の元をランダムにｇ０個選び、ｇ０個の超楕円曲線上の点Ｐｉ（ｉ＝１、…、ｇ０）を生成するステップと、
Ｕ（ｘ）＝（ｘ−ｘ１）（ｘ−ｘ２）…（ｘ−ｘｇ０）
Ｖ（ｘ）＝ｖｇ０−１ｘｇ０−１＋ｖｇ０−２ｘｇ０−２＋…＋ｖ０の係数ｖｉを決定し、ベースポイントの因子：Ｄ０＝（Ｕ（ｘ）、Ｖ（ｘ））を決定するステップと、
を含むステップであることを特徴とする。
【００６７】
さらに、本発明の暗号処理演算方法の一実施例において、前記ベースポイント生成ステップは、超楕円曲線の種数ｇ（ｇｅｎｕｓ）＝２である場合、ウェイト（ｗｅｉｇｈｔ）１となる因子をベースポイントとして生成するステップであり、前記演算処理ステップは、因子の加算処理として、ウェイト（ｗｅｉｇｈｔ）１の因子＋ウェイト（ｗｅｉｇｈｔ）２の因子の加算処理を実行するステップであることを特徴とする。
【００６８】
さらに、本発明の暗号処理演算方法の一実施例において、前記演算処理ステップは、加算演算処理アルゴリズム：ＥｘＨａｒＡＤＤ２＋１→２を実行するステップを含むことを特徴とする。
【００６９】
さらに、本発明の暗号処理演算方法の一実施例において、前記ベースポイント生成ステップは、超楕円曲線の種数ｇ（ｇｅｎｕｓ）＝３である場合、ウェイト（ｗｅｉｇｈｔ）１もしくは２となる因子をベースポイントとして生成するステップであり、前記演算処理ステップは、因子の加算処理として、ウェイト（ｗｅｉｇｈｔ）１の因子＋ウェイト（ｗｅｉｇｈｔ）３の因子の加算処理、またはウェイト（ｗｅｉｇｈｔ）２の因子＋ウェイト（ｗｅｉｇｈｔ）３の因子の加算処理を実行するステップであることを特徴とする。
【００７０】
さらに、本発明の暗号処理演算方法の一実施例において、前記演算処理ステップは、加算演算処理アルゴリズム：ＥｘＨａｒＡＤＤ３＋２→３、または、加算演算処理アルゴリズム：ＥｘＨａｒＡＤＤ３＋１→３、の少なくともいずれかの加算演算処理アルゴリズムを実行するステップを含むことを特徴とする。
【００７１】
さらに、本発明の暗号処理演算方法の一実施例において、前記ベースポイント生成ステップは、超楕円曲線の種数ｇ（ｇｅｎｕｓ）より小さいウェイト（ｗｅｉｇｈｔ）ｇ０（ただし、１≦ｇ０＜ｇ）の因子のうち、因子のＭｕｍｆｏｒｄ表現の多項式の係数が少なくとも一つ以上０または１である因子をベースポイントとして生成するステップであることを特徴とする。
【００７２】
さらに、本発明の暗号処理演算方法の一実施例において、前記演算処理ステップは、Ｈａｒｌｅｙのアルゴリズムに従った加算アルゴリズムを含む演算処理を実行するステップであることを特徴とする。
【００７３】
さらに、本発明の暗号処理演算方法の一実施例において、前記演算処理ステップは、ｂｉｎａｒｙ法またはｄｏｕｂｌｅ−ａｎｄ−ａｄｄ−ａｌｗａｙｓ法の少なくともいずれかのスカラー倍算アルゴリズムに従った演算を実行するステップであることを特徴とする。
【００７４】
さらに、本発明の暗号処理演算方法の一実施例において、前記演算処理ステップは、Ｃａｎｔｏｒのアルゴリズムに従った加算アルゴリズムを含む演算を実行するステップであることを特徴とする。
【００７５】
さらに、本発明の第２の側面は、
超楕円曲線暗号に基づく暗号処理演算を実行する暗号処理装置であり、
超楕円曲線の種数ｇ（ｇｅｎｕｓ）より小さいウェイト（ｗｅｉｇｈｔ）ｇ０（ただし、１≦ｇ０＜ｇ）の因子をベースポイントとして生成するベースポイント生成手段と、
前記ベースポイントとしての因子を含む因子のスカラー倍算処理を実行する演算処理手段と、
を有することを特徴とする暗号処理装置にある。
【００７６】
さらに、本発明の暗号処理装置の一実施例において、前記ベースポイント生成手段は、定義体としての有限体Ｆｑ上の元をランダムにｇ０個選び、ｇ０個の超楕円曲線上の点Ｐｉ（ｉ＝１、…、ｇ０）を生成し、
Ｕ（ｘ）＝（ｘ−ｘ１）（ｘ−ｘ２）…（ｘ−ｘｇ０）
Ｖ（ｘ）＝ｖｇ０−１ｘｇ０−１＋ｖｇ０−２ｘｇ０−２＋…＋ｖ０の係数ｖｉを決定し、ベースポイントの因子：Ｄ０＝（Ｕ（ｘ）、Ｖ（ｘ））を決定する処理を実行する構成であることを特徴とする。
【００７７】
さらに、本発明の暗号処理装置の一実施例において、前記ベースポイント生成手段は、超楕円曲線の種数ｇ（ｇｅｎｕｓ）＝２である場合、ウェイト（ｗｅｉｇｈｔ）１となる因子をベースポイントとして生成する構成であり、前記演算処理手段は、因子の加算処理として、ウェイト（ｗｅｉｇｈｔ）１の因子＋ウェイト（ｗｅｉｇｈｔ）２の因子の加算処理を実行する構成を有することを特徴とする。
【００７８】
さらに、本発明の暗号処理装置の一実施例において、前記演算処理手段は、加算演算処理アルゴリズム：ＥｘＨａｒＡＤＤ２＋１→２を実行する構成であることを特徴とする。
【００７９】
さらに、本発明の暗号処理装置の一実施例において、前記ベースポイント生成手段は、超楕円曲線の種数ｇ（ｇｅｎｕｓ）＝３である場合、ウェイト（ｗｅｉｇｈｔ）１もしくは２となる因子をベースポイントとして生成し、前記演算処理手段は、因子の加算処理として、ウェイト（ｗｅｉｇｈｔ）１の因子＋ウェイト（ｗｅｉｇｈｔ）３の因子の加算処理、またはウェイト（ｗｅｉｇｈｔ）２の因子＋ウェイト（ｗｅｉｇｈｔ）３の因子の加算処理を実行する構成であることを特徴とする。
【００８０】
さらに、本発明の暗号処理装置の一実施例において、前記演算処理手段は、加算演算処理アルゴリズム：ＥｘＨａｒＡＤＤ３＋２→３、または、加算演算処理アルゴリズム：ＥｘＨａｒＡＤＤ３＋１→３、の少なくともいずれかの加算演算処理アルゴリズムを実行する構成であることを特徴とする。
【００８１】
さらに、本発明の暗号処理装置の一実施例において、前記ベースポイント生成手段は、超楕円曲線の種数ｇ（ｇｅｎｕｓ）より小さいウェイト（ｗｅｉｇｈｔ）ｇ０（ただし、１≦ｇ０＜ｇ）の因子のうち、因子のＭｕｍｆｏｒｄ表現の多項式の係数が少なくとも一つ以上０または１である因子をベースポイントとして生成する処理を実行する構成であることを特徴とする。
【００８２】
さらに、本発明の暗号処理装置の一実施例において、前記演算処理手段は、Ｈａｒｌｅｙのアルゴリズムに従った加算アルゴリズムを含む演算処理を実行する構成であることを特徴とする。
【００８３】
さらに、本発明の暗号処理装置の一実施例において、前記演算処理手段は、ｂｉｎａｒｙ法またはｄｏｕｂｌｅ−ａｎｄ−ａｄｄ−ａｌｗａｙｓ法の少なくともいずれかのスカラー倍算アルゴリズムに従った演算を実行する構成であることを特徴とする。
【００８４】
さらに、本発明の暗号処理装置の一実施例において、前記演算処理手段は、Ｃａｎｔｏｒのアルゴリズムに従った加算アルゴリズムを含む演算を実行する構成であることを特徴とする。
【００８５】
さらに、本発明の第３の側面は、
超楕円曲線暗号に基づく暗号処理演算を実行するコンピュータ・プログラムであり、
超楕円曲線の種数ｇ（ｇｅｎｕｓ）より小さいウェイト（ｗｅｉｇｈｔ）ｇ０（ただし、１≦ｇ０＜ｇ）となる因子をベースポイントとして生成するベースポイント生成ステップと、
前記ベースポイントとしての因子を含む因子のスカラー倍算処理を実行する演算処理ステップと、
を有することを特徴とするコンピュータ・プログラムにある。
【００８６】
なお、本発明のコンピュータ・プログラムは、例えば、様々なプログラム・コードを実行可能なコンピュータ・システムに対して、コンピュータ可読な形式で提供する記憶媒体、通信媒体、例えば、ＣＤやＦＤ、ＭＯなどの記録媒体、あるいは、ネットワークなどの通信媒体によって提供可能なコンピュータ・プログラムである。このようなプログラムをコンピュータ可読な形式で提供することにより、コンピュータ・システム上でプログラムに応じた処理が実現される。
【００８７】
本発明のさらに他の目的、特徴や利点は、後述する本発明の実施例や添付する図面に基づくより詳細な説明によって明らかになるであろう。なお、本明細書においてシステムとは、複数の装置の論理的集合構成であり、各構成の装置が同一筐体内にあるものには限らない。
【発明の効果】
【００８８】
本発明の構成によれば、超楕円曲線暗号に基づく暗号処理において、超楕円曲線の種数ｇ（ｇｅｎｕｓ）より小さいウェイト（ｗｅｉｇｈｔ）ｇ０（ただし、１≦ｇ０＜ｇ）の因子をベースポイントとして生成し、スカラー倍算処理を実行する構成としたので、スカラー倍算処理において実行する演算処理を、例えば種数ｇ＝２の超楕円曲線暗号においては、Ｈａｒｌｅｙ  ＡＤＤから、演算ステップ数の少ないＥｘＨａｒＡＤＤ２＋１→２の実行ステップに変更し、また、種数ｇ＝３の超楕円曲線暗号においては、Ｈａｒｌｅｙ  ＡＤＤから演算ステップ数の少ないＥｘＨａｒＡＤＤ３＋２→３、またはＥｘＨａｒＡＤＤ３＋１→３の実行に変更することが可能となり、超楕円曲線暗号処理における高速な演算処理が実現される。
【００８９】
さらに、本発明の構成によれば、ベースポイント生成において、超楕円曲線の種数ｇ（ｇｅｎｕｓ）より小さいウェイト（ｗｅｉｇｈｔ）ｇ０（ただし、１≦ｇ０＜ｇ）の因子のうち、因子のＭｕｍｆｏｒｄ表現の多項式の係数が少なくとも一つ以上０または１である因子をベースポイントとして生成することで、さらなる演算ステップの削減が可能となり、超楕円曲線暗号処理における高速な演算処理が実現される。
【発明を実施するための最良の形態】
【００９０】
以下、本発明の暗号処理装置および暗号処理演算方法、並びにコンピュータ・プログラムの詳細について説明する。なお、説明は、以下の項目に従って行なう。
１．本発明の概要について
２．ベースポイント生成アルゴリズムについて
３．演算処理の詳細
４．暗号処理装置の機能構成について
５．電子署名生成および検証アルゴリズムにおける本発明の適用例
６．暗号処理装置のハードウェア構成例
【００９１】
［１．本発明の概要について］
前述したように、楕円曲線暗号を一般化した超楕円曲線暗号（ＨＥＣＣ：Hyper Elliptic Curve Cryptography）についての高速化演算手法についての研究が盛んに行なわれている。超楕円曲線では曲線を特徴づける値は種数（ｇｅｎｕｓ）ｇである。ｐを素数、ｎを正の整数、ｑ＝ｐｎとする。このとき有限体Ｆｑ上で定義される種数ｇの超楕円曲線Ｃは以下の方程式、
ｙ２＋ｈ（ｘ）ｙ＝ｆ（ｘ）
で定義される。ここで、ｈ（ｘ），ｆ（ｘ）∈Ｆｑ［ｘ］，ｆ（ｘ）は、は次数２ｇ＋１のｍｏｎｉｃ多項式である。
【００９２】
超楕円曲線Ｃ上の点Ｐ＝（ｘ、ｙ）に対してｏｐｐｏｓｉｔｅな点−Ｐは（ｘ、ｙ＋ｈ（ｘ））として定義される。Ｐ＝−Ｐである点を分岐点（ｒａｍｉｆｉｃａｔｉｏｎ  ｐｏｉｎｔ）と呼ぶ。
【００９３】
超楕円曲線暗号の定義体の演算サイズ（ビット長）は楕円曲線暗号と同等の安全性を仮定した場合、楕円曲線の定義体の演算サイズに比べて１／ｇに小さくなることが知られている。演算サイズが小さいことは実装上メリットがあり、超楕円曲線暗号の利点の一つして挙げられる。
【００９４】
前述したように、超楕円曲線暗号では点の形式的和である因子（ｄｉｖｉｓｏｒ）をＤ１とし、スカラー倍算ｋＤ１で定義される因子をＤ２とすると、Ｄ２からｋを求める問題は超楕円曲線におけるヤコビ多様体上の離散対数問題として公開鍵暗号として用いることができる。
【００９５】
因子（ｄｉｖｉｓｏｒ）は、前述したように、以下の形式で表現することができる。
【数１２】
2005258228.tif 000014
【００９６】
但しＰｉ＝（ｘｉ、ｙｉ）かつｉ≠ｊに対してＰｉ≠Ｐｊである。この形式の因子を半被約因子（ｓｅｍｉ  ｒｅｄｕｃｅｄ  ｄｉｖｉｓｏｒ）とよぶ。また、ΣｍｉをＤのウェイト（ｗｅｉｇｈｔ）と呼ぶ。さらにウェイト（ｗｅｉｇｈｔ）が種数ｇ以下である半被約因子を被約因子（ｒｅｄｕｃｅｄ  ｄｉｖｉｓｏｒ）と呼ぶ。
【００９７】
超楕円曲線のヤコビ（Ｊａｃｏｂｉ）多様体上の任意の半被約因子Ｄは下記の多項式Ｕ、Ｖ∈Ｆｑ［ｘ］を用いてＤ＝（Ｕ、Ｖ）として表現できる。これをマンホード（Ｍｕｍｆｏｒｄ）表現と呼ぶ。
【数１３】
2005258228.tif 000015
【００９８】
種数（ｇｅｎｕｓ）２の任意の被約因子Ｄはマンホード（Ｍｕｍｆｏｒｄ）表現を用いると、有限体Ｆｑ上の元を係数に持つ２次以下の多項式の組、すなわち、
（Ｕ、Ｖ）＝（ｘ２＋ｕ１ｘ＋ｕ０、ｖ１ｘ＋ｖ０）
として表現することができる。
また、種数（ｇｅｎｕｓ）３の任意の被約因子Ｄはマンホード（Ｍｕｍｆｏｒｄ）表現を用いると有限体Ｆｑ上の元を係数に持つ３次以下の多項式の組、すなわち、
（Ｕ、Ｖ）＝（ｘ３＋ｕ２ｘ２＋ｕ１ｘ＋ｕ０、ｖ２ｘ２＋ｖ１ｘ＋ｖ０）
として表現できる。
【００９９】
なお、他の因子の表現として変形Ｍｕｍｆｏｒｄ表現、Ｗｅｉｇｈｔｅｄ  Ｃｏｏｒｄｉｎａｔｅがある。変形Ｍｕｍｆｏｒｄ表現はＥＣＣ（楕円曲線暗号）でいうプロジェクティブ（ｐｒｏｊｅｃｔｉｖｅ）座標に相当し、Ｍｕｍｆｏｒｄ表現（Ｕ、Ｖ）に定数Ｚ倍し、（Ｕ、Ｖ、Ｚ）で表現するものである。
【０１００】
Ｗｅｉｇｈｔｅｄ  Ｃｏｏｒｄｉｎａｔｅも同様にＭｕｍｆｏｒｄ表現に複数の定数（Ｚ１、Ｚ２）をかけることで（Ｕ、Ｖ、Ｚ１、Ｚ２）で表現する方法である。いずれも下記に述べるＨａｒｌｅｙのアルゴリズムの計算量を削減するための手法として用いられている。
【０１０１】
前述したように、スカラー倍算の計算を暗号技術で用いる場合、入力に必要な因子Ｄ０は、
（１）事前に決めた因子の場合、
（２）事前に決められないランダムに発生する因子の場合、
の２つのタイプに分けることができる。
ここで（１）事前に決めた因子を適用する場合、この入力因子がベースポイントとなる。
【０１０２】
なお、以下、本発明の説明において、因子Ｄは、特に断りがない限り被約因子（ｒｅｄｕｃｅｄ  ｄｉｖｉｓｏｒ）であるものとする。すなわち、ウェイト（ｗｅｉｇｈｔ）が種数ｇ以下である半被約因子としての被約因子（ｒｅｄｕｃｅｄ  ｄｉｖｉｓｏｒ）であるものとする。
【０１０３】
前述したように、一般的なベースポイントの生成アルゴリズムは、以下の処理によって実行される。
（ａ）  定義体Ｆｑ上の元をランダムにｇ個選び、ｇ個の超楕円曲線上の点Ｐｉ（ｉ＝１、…、ｇ）を生成する。
（ａ１）  ランダムに選んだ各元をｘ座標ｘｉ（ｉ＝１…ｇ）とし、次に超楕円曲線上に乗るようにｘｉに対応するｙ座標を求める。
（ｂ）  ベースポイントの因子をＤ０＝（Ｕ（ｘ）、Ｖ（ｘ））とする。
（ｂ１）Ｕ（ｘ）＝（ｘ−ｘ１）（ｘ−ｘ２）…（ｘ−ｘｇ）
（ｂ２）Ｖ（ｘ）＝ｖｇ−１ｘｇ−１＋ｖｇ−２ｘｇ−２＋…＋ｖ０の係数ｖｉを決定する。例えば生成した点が全て異なる場合、Ｖ（ｘｉ）＝ｙｉよりｖｉを求めることができる。
（ｃ）  上記アルゴリズムにより生成される因子はｗｅｉｇｈｔ  ｇの因子となる。
【０１０４】
このように、種数ｇの超楕円曲線においてベースポイントを生成する従来のアルゴリズム及び装置は通常、ウェイト（ｗｅｉｇｈｔ）＝ｇの因子を生成する。
【０１０５】
本発明においては、種数ｇの超楕円曲線において、ｇより小さいウェイト（ｗｅｉｇｈｔ）＝ｇ０の因子を生成して、これをベースポイントとする。
すなわち、種数ｇの超楕円曲線におけるベースポイントを、
ｇ０＜ｇ
が成立するウェイト（ｗｅｉｇｈｔ）＝ｇ０の因子に設定する。このベースポイント設定により、超楕円曲線暗号におけるスカラー倍算を高速化させる。
【０１０６】
［２．ベースポイント生成アルゴリズムについて］
以下、種数ｇの超楕円曲線において、ウェイト（ｗｅｉｇｈｔ）がｇより小さいウェイト（ｗｅｉｇｈｔ）＝ｇ０である因子をベースポイントとして生成するアルゴリズムについて説明する。
【０１０７】
種数ｇの超楕円曲線においてウェイト（ｗｅｉｇｈｔ）＝ｇの因子をベースポイントとして生成する従来のアルゴリズムでは、超楕円曲線上の点をｇ個選ぶ処理を実行するのに対して、本発明のベースポイント生成アルゴリズムでは、超楕円曲線上の点をｇ０個、選択する処理を実行する。但しｇ０は１≦ｇ０＜ｇを満たす値である。
【０１０８】
本発明に従ったベースポイント生成アルゴリズムを、図３を参照して説明する。本発明に従ったベースポイント生成は、以下の処理手順で実行する。
【０１０９】
（ステップＳ１０１）
定義体としての有限体Ｆｑ上の元をランダムにｇ０個選び、ｇ０個の超楕円曲線上の点Ｐｉ（ｉ＝１、…、ｇ０）を生成する。
（１）ランダムに選んだ各元をｘ座標ｘｉ（ｉ＝１…ｇ０）とし、次に超楕円曲線上に乗るようにｘｉに対応するｙ座標を求める。
【０１１０】
（ステップＳ１０２）
ベースポイントの因子をＤ０＝（Ｕ（ｘ）、Ｖ（ｘ））とする。
（１）Ｕ（ｘ）＝（ｘ−ｘ１）（ｘ−ｘ２）…（ｘ−ｘｇ０）
（２）Ｖ（ｘ）＝ｖｇ０−１ｘｇ０−１＋ｖｇ０−２ｘｇ０−２＋…＋ｖ０の係数ｖｉを決定する。例えば生成した点が全て異なる場合、Ｖ（ｘｉ）＝ｙｉ（ｉ＝１…ｇ０）よりｖｉを求めることができる。
【０１１１】
上述のステップの実行により、種数ｇの超楕円曲線において、ウェイト（ｗｅｉｇｈｔ）がｇより小さいウェイト（ｗｅｉｇｈｔ）＝ｇ０である因子をベースポイントとして生成する。
【０１１２】
例えば種数ｇ＝３の超楕円曲線の場合、ベースポイントは、従来の手法によれば、通常ｗｅｉｇｈｔ  ３の因子を用いるのに対して、本発明に従ったベースポイント設定アルゴリズムを適用した場合、種数ｇ＝３より小さいウェイト、すなわちウェイト（ｗｅｉｇｈｔ）＝１もしくはウェイト（ｗｅｉｇｈｔ）＝２の因子をベースポイントとする。
【０１１３】
また、例えば種数ｇ＝２の超楕円曲線の場合、ベースポイントは、従来の手法によれば、通常ｗｅｉｇｈｔ  ２の因子を用いるのに対して、本発明に従ったベースポイント設定アルゴリズムを適用した場合、種数ｇ＝２より小さいウェイト、すなわちウェイト（ｗｅｉｇｈｔ）＝１の因子をベースポイントとする。
【０１１４】
［３．演算処理の詳細］
図３を参照して説明したアルゴリズムを適用して、種数ｇの超楕円曲線において、ｇより小さいウェイト（ｗｅｉｇｈｔ）＝ｇ０である因子をベースポイントとして生成した場合、この因子を適用して実行するスカラー倍算では、スカラー倍算実行アルゴリズム中で用いる加算公式が、従来の種数ｇに等しいウェイトを持つベースポイントを適用した場合とは異なってくる。
【０１１５】
すなわち、種数ｇより小さいウェイト（ｗｅｉｇｈｔ）の因子をベースポイントに選んだ場合、スカラー倍算中の加算は、ＨａｒｌｅｙＡＤＤではなくなり、「ｗｅｉｇｈｔ  ｇの因子＋ｇより小さいｗｅｉｇｈｔの因子の加算」になる。この「ｗｅｉｇｈｔ  ｇの因子＋ｇより小さいｗｅｉｇｈｔの因子の加算」にかかる計算コストは因子を表現する多項式の次数が下がるため、ＨａｒｌｅｙＡＤＤよりも計算量が少なくなり、スカラー倍算の処理時間を短くすることができる。
【０１１６】
図４を参照して種数ｇより小さいウェイト（ｗｅｉｇｈｔ）の因子をベースポイントに選んだ場合のスカラー倍算中の加算処理について説明する。図４（Ａ）は、種数ｇ＝２の場合の加算処理を説明する図であり、図４（Ｂ）は、種数ｇ＝３の場合の加算処理を説明する図である。
【０１１７】
図４（Ａ）の、種数ｇ＝２の場合の加算処理において、従来の処理では、ベースポイントは、通常ｗｅｉｇｈｔ  ２の因子を用いることになり、図４（Ａ）の加算アルゴリズムにおいて、（１）「ｗｅｉｇｈｔ２の因子＋ｗｅｉｇｈｔ２の因子の加算」、すなわち、ｗｅｉｇｈｔ２同士の加算となる。このとき、因子Ｄ１＝（Ｕ１、Ｖ１）、Ｄ２＝（Ｕ２、Ｖ２）について、最大公約数ｇｃｄ（Ｕ１、Ｕ２）＝１であれば
（１ａ）ＨａｒｌｅｙＡＤＤ、
に従った加算処理を行う。これが、Ｍｏｓｔ  Ｆｒｅｑｕｅｎｔ  Ｃａｓｅと呼ばれる処理であり、多くの場合、このアルゴリズムに従った加算処理、すなわち、（１ａ）ＨａｒｌｅｙＡＤＤが実行されることになる。
【０１１８】
しかし、図３を参照して説明したベースポイント選択アルゴリズムに従って、種数ｇより小さいウェイト（ｗｅｉｇｈｔ）の因子をベースポイントに選んだ場合、「ｗｅｉｇｈｔ  ｇの因子＋ｇより小さいｗｅｉｇｈｔの因子の加算」、すなわち、図４（Ａ）において、（２）ｗｅｉｇｈｔ２＋ｗｅｉｇｈｔ１の処理が実行される。この処理では、ｇｃｄ（Ｕ１、Ｕ２）＝１かどうかをチェックし、ｇｃｄ（Ｕ１、Ｕ２）＝１を満足する場合には、
（２ａ）ＥｘＨａｒＡＤＤ２＋１→２を実行し、
ｇｃｄ（Ｕ１、Ｕ２）＝１を満足しない場合には、
（２ｂ）例外処理３を行う。
【０１１９】
多くの場合、ｇｃｄ（Ｕ１、Ｕ２）＝１が成立することになり、（２ａ）ＥｘＨａｒＡＤＤ２＋１→２の処理が行なわれることになる。この「ｗｅｉｇｈｔ  ｇの因子＋ｇより小さいｗｅｉｇｈｔの因子の加算」にかかる計算コストは因子を表現する多項式の次数が下がるため、ＨａｒｌｅｙＡＤＤよりも計算量が少なくなり、スカラー倍算の処理時間を短くすることができる。
【０１２０】
図４（Ｂ）の、種数ｇ＝３の場合の加算処理においては、従来の処理では、ベースポイントは、通常ｗｅｉｇｈｔ  ３の因子を用いることになり、図４（Ｂ）の加算アルゴリズムにおいて、（１）「ｗｅｉｇｈｔ３の因子＋ｗｅｉｇｈｔ３の因子の加算」、すなわち、ｗｅｉｇｈｔ３同士の加算となる。このとき、因子Ｄ１＝（Ｕ１、Ｖ１）、Ｄ２＝（Ｕ２、Ｖ２）について、最大公約数ｇｃｄ（Ｕ１、Ｕ２）＝１であれば
（１ａ）ＨａｒｌｅｙＡＤＤ、
すなわちハーレーアルゴリズムに従った加算処理を行う。これが、Ｍｏｓｔ  Ｆｒｅｑｕｅｎｔ  Ｃａｓｅと呼ばれる処理であり、多くの場合、ハーレーアルゴリズムに従った加算処理、すなわち、（１ａ）ＨａｒｌｅｙＡＤＤが実行されることになる。
【０１２１】
しかし、図３を参照して説明したベースポイント選択アルゴリズムに従って、種数ｇより小さいウェイト（ｗｅｉｇｈｔ）の因子をベースポイントに選んだ場合、「ｗｅｉｇｈｔ  ｇの因子＋ｇより小さいｗｅｉｇｈｔの因子の加算」、すなわち、図４（Ｂ）において、（２）ｗｅｉｇｈｔ３＋ｗｅｉｇｈｔ２の処理、または、（３）ｗｅｉｇｈｔ３＋ｗｅｉｇｈｔ１の処理が実行される。これらの処理においても、ｇｃｄ（Ｕ１、Ｕ２）＝１かどうかをチェックし、ｇｃｄ（Ｕ１、Ｕ２）＝１を満足する場合には、
（２ａ）ＥｘＨａｒＡＤＤ３＋２→３、または、
（３ａ）ＥｘＨａｒＡＤＤ３＋１→３を実行し、
ｇｃｄ（Ｕ１、Ｕ２）＝１を満足しない場合には、
例外処理９，１０を行う。
【０１２２】
多くの場合、ｇｃｄ（Ｕ１、Ｕ２）＝１が成立することになり、（２ａ）ＥｘＨａｒＡＤＤ３＋２→３、または（３ａ）ＥｘＨａｒＡＤＤ３＋１→３の処理が行なわれることになる。この「ｗｅｉｇｈｔ  ｇの因子＋ｇより小さいｗｅｉｇｈｔの因子の加算」にかかる計算コストは因子を表現する多項式の次数が下がるため、ＨａｒｌｅｙＡＤＤよりも計算量が少なくなり、スカラー倍算の処理時間を短くすることができる。
【０１２３】
研究論文等でよくとりあげられている、種数２、３の超楕円曲線暗号の場合を例にとり、本発明に従ったスカラー倍算の処理について説明する。
【０１２４】
種数２の場合の超楕円曲線の場合、ｇ以下のウェイト（ｗｅｉｇｈｔ）の因子として、ｗｅｉｇｈｔ  １の因子をベースポイントに選んでスカラー倍算を行う。スカラー倍算としてｂｉｎａｒｙ法及びｄｏｕｂｌｅ−ａｎｄ−ａｄｄ−ａｌｗａｙｓ法を使った場合のアルゴリズムを以下に示す。
【０１２５】
（１）種数２、ｂｉｎａｒｙ法、ｗｅｉｇｈｔ１のベースポイント
【数１４】
2005258228.tif 000016
【０１２６】
（２）種数２、ｄｏｕｂｌｅ−ａｎｄ−ａｄｄ−ａｌｗａｙｓ法、ｗｅｉｇｈｔ１のベースポイント
【数１５】
2005258228.tif 000017
【０１２７】
いずれの場合も従来法では、加算をＨａｒｌｅｙＡＤＤで行っていたのに対し、ベースポイントをｗｅｉｇｈｔ１にすることで加算処理を図４Ａの（２）ｗｅｉｇｈｔ１＋ｗｅｉｇｈｔ２の処理に置き換えることができる。このｗｅｉｇｈｔ１＋ｗｅｉｇｈｔ２の処理ではｗｅｉｇｈｔ１の因子とｗｅｉｇｈｔ２の因子が共通の点を持つ場合と持たない場合において異なる処理を行なうことになる。
【０１２８】
すなわち、因子Ｄ１＝（Ｕ１、Ｖ１）、Ｄ２＝（Ｕ２、Ｖ２）について、最大公約数ｇｃｄ（Ｕ１、Ｕ２）＝１であれば、２つの因子Ｄ１＝（Ｕ１、Ｖ１）、Ｄ２＝（Ｕ２、Ｖ２）は、互いに同一またはオポジット（ｏｐｐｏｓｉｔｅ）な点を含まない。この場合、
（２ａ）ＥｘＨａｒＡＤＤ２＋１→２を実行し、
ｇｃｄ（Ｕ１、Ｕ２）＝１を満足しない場合には、
（２ｂ）例外処理３を行う。
【０１２９】
Ｍｏｓｔ  Ｆｒｅｑｕｅｎｔ  Ｃａｓｅと呼ばれるＨａｒｌｅｙＡＤＤと同様、因子Ｄ１＝（Ｕ１、Ｖ１）、Ｄ２＝（Ｕ２、Ｖ２）について、多くの場合、最大公約数ｇｃｄ（Ｕ１、Ｕ２）＝１が成立し、高確率で、
（２ａ）ＥｘＨａｒＡＤＤ２＋１→２を実行することになる。
【０１３０】
ＥｘＨａｒＡＤＤ２＋１→２の計算プロセス［Ｔａｂｌｅ３］を以下に示す。
【数１６】
2005258228.tif 000018
【０１３１】
標数２の場合、ＥｘＨａｒＡＤＤ２＋１→２の計算量は、１回の逆元算出演算（Ｉ：Ｉｎｖｅｒｓｉｏｎ）と、１１回の乗算（Ｍ：Ｍｕｌｔｉｐｌｉｃａｔｉｏｎ）、すなわち、Ｉ＋１１Ｍとなる。
【０１３２】
一方、ＨａｒｌｅｙＡＤＤの計算プロセス［Ｔａｂｌｅ１］を以下に示す。
【数１７】
2005258228.tif 000019
【０１３３】
ＨａｒｌｅｙＡＤＤの計算量は、１回の逆元算出演算（Ｉ：Ｉｎｖｅｒｓｉｏｎ）と、２５回の乗算（Ｍ：Ｍｕｌｔｉｐｌｉｃａｔｉｏｎ）、すなわち、Ｉ＋２５Ｍとなる。
【０１３４】
このように、ＥｘＨａｒＡＤＤ２＋１→２の計算量は、ＨａｒｌｅｙＡＤＤの計算量より少なく、高速にスカラー倍演算を行うことができる。すなわち、種数ｇ以下のウェイト（ｗｅｉｇｈｔ）の因子をベースポイントに選んでスカラー倍算を行うことで、ＨａｒｌｅｙＡＤＤの計算ではなく、計算量の少ないＥｘＨａｒＡＤＤ２＋１→２の計算を実行させることが可能となり、高速にスカラー倍演算を行うことができる。定義体が２の拡大体ではない場合も同様に計算量が削減できる。
【０１３５】
具体的な例について説明する。種数２、定義体がＦ２８３の場合、ｂｉｎａｒｙ法、ｄｏｕｂｌｅ−ａｎｄ−ａｄｄ−ａｌｗａｙｓ法でのスカラー倍算が１ｂｉｔあたり、従来法に比べてどの程度高速化されるかを見積もった。
【０１３６】
ｂｉｎａｒｙ法における１ビットあたりの演算削減率は、
｛１／２（ＨａｒｌｅｙＡＤＤの計算量−ＥｘＨａｒＡＤＤ２＋１→２の計算量）｝／（１／２ＨａｒｌｅｙＡＤＤの計算量＋ＨａｒｌｅｙＤＢＬの計算量）
で与えられる。
【０１３７】
また、ｄｏｕｂｌｅ−ａｎｄ−ａｄｄ−ａｌｗａｙｓ法における１ビットあたりの演算削減率は、
（ＨａｒｌｅｙＡＤＤの計算量−ＥｘＨａｒＡＤＤ２＋１→２計算量）／（ＨａｒｌｅｙＡＤＤの計算量＋ＨａｒｌｅｙＤＢＬの計算量）
で与えられる。
【０１３８】
これらの計算式に基づいて、
ＥｘＨａｒＡＤＤ２＋１→２の計算量＝Ｉ＋１１Ｍ
ＨａｒｌｅｙＡＤＤの計算量＝Ｉ＋２５Ｍ
ＨａｒｌｅｙＤＢＬの計算量＝Ｉ＋２７Ｍ
の各計算量を代入し演算削減率を求める。
【０１３９】
この結果、本発明のベースポイント設定処理、すなわち種数ｇより小さいウェイトｇ０である因子をベースポイントとして設定した場合、種数ｇに等しいウェイトｇである因子をベースポイントとして設定した従来手法に比較して、ｂｉｎａｒｙ法で１５．３％、ｄｏｕｂｌｅ−ａｎｄ−ａｄｄ−ａｌｗａｙｓ法で２３．３％の高速化ができることがわかった。ただし、有限体の乗算Ｍと、逆元算出としての除算ＩをＩ＝４．１Ｍとして見積もっている。
【０１４０】
種数３の場合、種数３未満の因子として、ｗｅｉｇｈｔ１の因子をベースポイントに用いる方法とｗｅｉｇｈ２の因子を用いる方法がある。種数２の場合と同様、ｂｉｎａｒｙ法、ｄｏｕｂｌｅ−ａｎｄ−ａｄｄ−ａｌｗａｙｓ法の演算処理において、種数３に等しいウェイト同士の因子の加算の際に実行していたＨａｒｌｅｙＡＤＤが、加算ｗｅｉｇｈｔ１＋ｗｅｉｇｈｔ３もしくは加算ｗｅｉｇｈｔ２＋ｗｅｉｇｈｔ３に置き換わる。
【０１４１】
種数３の場合、スカラー倍算としてｂｉｎａｒｙ法及びｄｏｕｂｌｅ−ａｎｄ−ａｄｄ−ａｌｗａｙｓ法を使った場合のアルゴリズムを以下に示す。
【０１４２】
（１）種数３、ｂｉｎａｒｙ法、ｗｅｉｇｈｔ１のベースポイント
【数１８】
2005258228.tif 000020
【０１４３】
（２）種数３、ｄｏｕｂｌｅ−ａｎｄ−ａｄｄ−ａｌｗａｙｓ法、ｗｅｉｇｈｔ１のベースポイント
【数１９】
2005258228.tif 000021
【０１４４】
（３）種数３、ｂｉｎａｒｙ法、ｗｅｉｇｈｔ２のベースポイント
【数２０】
2005258228.tif 000022
【０１４５】
（４）種数３、ｄｏｕｂｌｅ−ａｎｄ−ａｄｄ−ａｌｗａｙｓ法、ｗｅｉｇｈｔ２のベースポイント
【数２１】
2005258228.tif 000023
【０１４６】
このように、種数２の場合と同様、ｂｉｎａｒｙ法、ｄｏｕｂｌｅ−ａｎｄ−ａｄｄ−ａｌｗａｙｓ法の演算処理において、種数３に等しいウェイト同士の因子の加算の際に実行していたＨａｒｌｅｙＡＤＤが、加算ｗｅｉｇｈｔ１＋ｗｅｉｇｈｔ３もしくは加算ｗｅｉｇｈｔ２＋ｗｅｉｇｈｔ３に置き換わる。Ｗｅｉｇｈｔ１＋ｗｅｉｇｈ３、若しくはｗｅｉｇｈｔ２＋ｗｅｉｇｈｔ３の加算は図４（Ｂ）に示すように、因子が共通の点を持つ場合と持たない場合において異なる処理を行なうことになる。
【０１４７】
すなわち、因子Ｄ１＝（Ｕ１、Ｖ１）、Ｄ２＝（Ｕ２、Ｖ２）について、最大公約数ｇｃｄ（Ｕ１、Ｕ２）＝１であれば、２つの因子Ｄ１＝（Ｕ１、Ｖ１）、Ｄ２＝（Ｕ２、Ｖ２）は、互いに同一またはオポジット（ｏｐｐｏｓｉｔｅ）な点を含まない。この場合、
（２ａ）ＥｘＨａｒＡＤＤ３＋２→３、または、
（３ａ）ＥｘＨａｒＡＤＤ３＋１→３を実行し、
ｇｃｄ（Ｕ１、Ｕ２）＝１を満足しない場合には、
（２ｂ）または（３ｂ）例外処理を行う。
【０１４８】
Ｍｏｓｔ  Ｆｒｅｑｕｅｎｔ  Ｃａｓｅと呼ばれるＨａｒｌｅｙＡＤＤと同様、因子Ｄ１＝（Ｕ１、Ｖ１）、Ｄ２＝（Ｕ２、Ｖ２）について、多くの場合、最大公約数ｇｃｄ（Ｕ１、Ｕ２）＝１が成立し、高確率で、
（２ａ）ＥｘＨａｒＡＤＤ３＋２→３、または、
（３ａ）ＥｘＨａｒＡＤＤ３＋１→３を実行することになる。
【０１４９】
ＥｘＨａｒＡＤＤ３＋１→３、ＥｘＨａｒＡＤＤ３＋２→３はそれぞれＨａｒＡＤＤに比べて計算量が少ないため、全体のスカラー倍演算を高速化することができる。ＥｘＨａｒＡＤＤ３＋１→３、ＥｘＨａｒＡＤＤ３＋２→３の計算量は論文等に明示的にしめされていないため、独自に各演算における計算量を見積もった。
【０１５０】
ＥｘＨａｒＡＤＤ３＋１→３の計算プロセス［Ｔａｂｌｅ６］を以下に示す。
【数２２】
2005258228.tif 000024
【０１５１】
ＥｘＨａｒＡＤＤ３＋１→３の計算量は、１回の逆元算出演算（Ｉ：Ｉｎｖｅｒｓｉｏｎ）と、２１回の乗算（Ｍ：Ｍｕｌｔｉｐｌｉｃａｔｉｏｎ）、すなわち、Ｉ＋２１Ｍとなる。
【０１５２】
ＥｘＨａｒＡＤＤ３＋２→３の計算プロセス［Ｔａｂｌｅ７］を以下に示す。
【数２３】
2005258228.tif 000025
【０１５３】
ＥｘＨａｒＡＤＤ３＋２→３の計算量は、１回の逆元算出演算（Ｉ：Ｉｎｖｅｒｓｉｏｎ）と、５２回の乗算（Ｍ：Ｍｕｌｔｉｐｌｉｃａｔｉｏｎ）、すなわち、Ｉ＋５２Ｍとなる。
【０１５４】
一方、種数ｇ＝３でのＨａｒｌｅｙＡＤＤ、ＨａｒｌｅｙＤＢＬの計算量は、文献［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.］による見積もりを参照している。但し、見積もりが正しいかどうか検証するため、実際に実装を行って計算量を確認した結果、ＨａｒｌｅｙＡＤＤでＩ＋７８Ｍ、ＨａｒｌｅｙＤＢＬでＩ＋８１Ｍであった。
【０１５５】
従って、以下に述べるように種数ｇ＝２の場合と同様に計算量の削減、高速化が期待できる。なお、上述したＥｘＨａｒＡＤＤ３＋２→３、ＥｘＨａｒＡＤＤ３＋１→３、ＨａｒｌｅｙＡＤＤ、ＨａｒｌｅｙＤＢＬの計算量は、すべて標数２の場合である。標数が２でない場合も同様に計算量の削減ができる。
【０１５６】
具体的な例について説明する。種数３、定義体がＦ２６３の場合、ｂｉｎａｒｙ法、ｄｏｕｂｌｅ−ａｎｄ−ａｄｄ−ａｌｗａｙｓ法でのスカラー倍算が１ｂｉｔあたり、従来法に比べてどの程度高速化されるかを見積もった。
【０１５７】
種数２の場合と同様に、ｂｉｎａｒｙ法における１ビットあたりの演算削減率は、
｛１／２（ＨａｒｌｅｙＡＤＤの計算量−ＥｘＨａｒＡＤＤ３＋１→３  もしくはＥｘＨａｒＡＤＤ３＋２→３の計算量）｝／（１／２ＨａｒｌｅｙＡＤＤの計算量＋ＨａｒｌｅｙＤＢＬの計算量）
で与えられる。
【０１５８】
また、ｄｏｕｂｌｅ−ａｎｄ−ａｄｄ−ａｌｗａｙｓ法における１ビットあたりの演算削減率は、
（ＨａｒｌｅｙＡＤＤの計算量−ＥｘＨａｒＡＤＤ３＋１→３もしくはＥｘＨａｒＡＤＤ３＋２→３計算量）／（ＨａｒｌｅｙＡＤＤの計算量＋ＨａｒｌｅｙＤＢＬの計算量）
で与えられる。
【０１５９】
これらの計算式に基づいて、
ＥｘＨａｒＡＤＤ３＋１→３の計算量＝Ｉ＋２１Ｍ
ＥｘＨａｒＡＤＤ３＋２→３の計算量＝Ｉ＋５２Ｍ
ＨａｒｌｅｙＡＤＤの計算量＝Ｉ＋７８Ｍ
ＨａｒｌｅｙＤＢＬの計算量＝Ｉ＋８１Ｍ
の各計算量を代入し演算削減率を求める。
【０１６０】
この結果、ｗｅｉｇｈｔ１の因子をベースポイントとして使った場合、ｂｉｎａｒｙ法で２２．０％、ｄｏｕｂｌｅ−ａｎｄ−ａｄｄ−ａｌｗａｙｓ法で３３．２％、Ｗｅｉｇｈｔ２の因子をベースポイントとして使った方法では、ｂｉｎａｒｙ法で１０．０％、ｄｏｕｂｌｅ−ａｎｄ−ａｄｄ−ａｌｗａｙｓ法で１５．１％の高速化が期待できる。ただしＦ２６３の乗算Ｍと除算Ｉの比率をＩ＝６．４Ｍとして見積もった。
【０１６１】
このように、本発明のベースポイント設定処理、すなわち種数ｇより小さいウェイトｇ０である因子をベースポイントとして設定した場合、種数ｇに等しいウェイトｇである因子をベースポイントとして設定した従来手法に比較して、ｂｉｎａｒｙ法、ｄｏｕｂｌｅ−ａｎｄ−ａｄｄ−ａｌｗａｙｓ法とも、演算量が削減され、高速演算が可能となる。
【０１６２】
これまでｗｅｉｇｈｔがｇより小さい任意の因子をベースポイントして使った場合の高速化の方法について述べてきた。そのｗｅｉｇｈｔがｇより小さい因子のうち、因子のＭｕｍｆｏｒｄ表現の多項式の係数が少なくとも一つ以上０または１である因子を選んだ場合、種数２の場合の加算アルゴリズムにおける図４（Ａ）の
（２ａ）ＥｘＨａｒＡＤＤ３＋１→３の計算
および、種数３の場合の加算アルゴリズムにおける図４（Ｂ）の
（２ａ）ＥｘＨａｒＡＤＤ３＋２→３の計算
（３ａ）ＥｘＨａｒＡＤＤ３＋１→３の計算
を適用したベースポイントの加算処理における乗算回数を削減することができるため、さらに高速化することができる。説明を簡単にするために以下ｇ＝２の場合を例に挙げて説明する。
【０１６３】
ｇ＝２の場合、ベースポイントは任意に選んだｗｅｉｇｈｔ１の因子であり、Ｍｕｍｆｏｒｄ表現を使うと以下のように書くことができる。
１．Ｄ０＝（Ｕ（ｘ）、Ｖ（ｘ））
２．Ｕ（ｘ）＝ｘ＋ｕ０、Ｖ（ｘ）＝ｖ０
３．（ｕ０、ｖ０）は超楕円曲線Ｃ上の任意に選んだ点の座標
【０１６４】
例えば超楕円曲線Ｃ上の点に（０、ｙ）が存在する場合（ｘ座標、ｙ座標は定義体Ｆｑの元である）、この点を使ってベースポイントを生成した場合、ｕ０＝０、ｖ０＝ｙとなる。この時、ＨａｒＡＤＤ２＋１→２の計算プロセス、これは、先に示した［数１６］のＥｘＨａｒＡＤＤ２＋１→２の計算プロセス［Ｔａｂｌｅ３］であるが、この計算プロセス中、以下の有限体の乗算を実装する必要がなくなる。
【０１６５】
Ｔａｂｌｅ３  Ｓｔｅｐ１  （ｕ２１＋ｕ１０）ｕ１０  （１Ｍ削減）
Ｔａｂｌｅ３  Ｓｔｅｐ３  ｖ２１ｕ１０      （１Ｍ削減）
Ｔａｂｌｅ３  Ｓｔｅｐ６  ｕ１０ｕ３１    （１Ｍ削減）
【０１６６】
従って通常のＨａｒＡＤＤ２＋１→２の計算量Ｉ＋１１Ｍに対して３つの乗算（３Ｍ）少ないＩ＋８Ｍで計算を行うことができるため、さらなる高速化をすることができる。
【０１６７】
今までＨａｒｌｅｙアルゴリズムとその改良アルゴリズムに対する高速化手法として、種数ｇの超楕円曲線において、ｇより小さいウェイト（ｗｅｉｇｈｔ）の因子をベースポイントとして使うことで、加算処理における計算量を削減し、スカラー倍算の高速化を実現する構成について説明してきたが、もう１の加算アルゴリズムであるＣａｎｔｏｒアルゴリズムでも、種数ｇの超楕円曲線において、ｇより小さいウェイト（ｗｅｉｇｈｔ）の因子をベースポイントとして使うことで、同様に加算処理における計算量が削減されスカラー倍算の高速化が実現される。
【０１６８】
種数ｇの超楕円曲線暗号（ＨＥＣＣ）においてＣａｎｔｏｒのアルゴリズムを使って加算アルゴリズムを実装した場合、ｗｅｉｇｈｔ  ｇより小さい因子とｗｅｉｇｈｔ  ｇの因子を使った加算はｗｅｉｇｈｔ  ｇ同士の因子の加算よりも計算量が小さくなる。従って種数  ｇの加算アルゴリズムにおいて、ベースポイントをｇより小さい因子を使うことで、Ｈａｒｌｅｙアルゴリズムと全く同様の高速化ができる。
【０１６９】
一般に、超楕円曲線暗号（ＨＥＣＣ）の安全性（ＨＥＣＣ１とする）はベース因子Ｄと任意の因子Ｗ（＝ｋＤ）からｋを求める離散対数問題（離散対数問題１とする）の困難性に基づいている。同様に、今回提案したｗｅｉｇｈｔがｇより小さい因子Ｄ１をベース因子とするＨＥＣＣの安全性（ＨＥＣＣ２とする）も任意の因子Ｗ１（＝ｋＤ１）からｋを求める離散対数問題（離散対数問題２とする）の困難性に基づいている。離散対数問題１は離散対数問題２を２回解くことによって解けることが容易に示される。つまり、今回提案したｗｅｉｇｈｔがｇより小さい因子Ｄ１をベース因子とするＨＥＣＣの安全性（ＨＥＣＣ２）は、一般的な超楕円曲線暗号（ＨＥＣＣ）の安全性（ＨＥＣＣ１）と同等並の安全性を有することになる。
【０１７０】
以上、説明したように、本発明によれば、種数ｇの超楕円曲線において、ｇより小さいウェイト（ｗｅｉｇｈｔ）の因子をベースポイントとして使うことで、一般的な超楕円曲線暗号（ＨＥＣＣ）の安全性を損なうことなく、加算処理における計算量を削減し、スカラー倍算の高速化が実現され、暗号処理演算を高速に実行することが可能となる。
【０１７１】
超楕円曲線上の因子の演算を使う暗号処理演算において、処理の重い演算は因子のスカラー倍算である。提案法によりスカラー倍算を高速化することで超楕円曲線暗号の処理を大幅に改善することができる。
【０１７２】
前述したように、超楕円曲線暗号（ＨＥＣＣ）は楕円曲線暗号（ＥＣＣ）を一般化した概念であり、現在、様々な分野で適用されている楕円曲線暗号（ＥＣＣ）を使った暗号処理、具体的には署名処理、暗号データの生成、復号処理、暗号鍵共有処理、認証処理などに、本発明を適用することが可能である。楕円曲線暗号（ＥＣＣ）における演算処理中のスカラー倍算の部分を、上述したスカラー倍算に置き換えることで、演算の高速化が可能となる。
【０１７３】
楕円曲線暗号（ＥＣＣ）を使ったアルゴリズムでは、スカラー倍算は大きく分けると事前に決められた点、ベースポイントをスカラー倍算する処理と、ランダムに発生した点をスカラー倍算する処理に分類される。これは、超楕円曲線暗号（ＨＥＣＣ）でも同様である。本発明は種数ｇの曲線において全ての因子のうち、ｗｅｉｇｈｔ  ｇより小さい因子を選びこれをベースポイントとして、因子の加算処理を高速化しているものであり、固定のベースポイントをスカラー倍算する処理において、ｗｅｉｇｈｔ  ｇより小さい因子を選びこれをベースポイントとして演算を行なうことで、高速化が実現される。
【０１７４】
［４．暗号処理装置の機能構成について］
図５に、本発明の暗号処理装置の機能構成を示すブロック図を示す。暗号処理装置１００は、超楕円曲線暗号に基づく暗号処理演算を実行する暗号処理装置であり、超楕円曲線の種数ｇ（ｇｅｎｕｓ）より小さいウェイト（ｗｅｉｇｈｔ）ｇ０（ただし、１≦ｇ０＜ｇ）の因子をベースポイントとして生成するベースポイント生成部１０１と、ベースポイントとしての因子を含む因子のスカラー倍算処理を実行する演算処理部１０２とによって構成される。
【０１７５】
ベースポイント生成部１０１は、定義体としての有限体Ｆｑ上の元をランダムにｇ０個選び、ｇ０個の超楕円曲線上の点Ｐｉ（ｉ＝１、…、ｇ０）を生成し、
Ｕ（ｘ）＝（ｘ−ｘ１）（ｘ−ｘ２）…（ｘ−ｘｇ０）
Ｖ（ｘ）＝ｖｇ０−１ｘｇ０−１＋ｖｇ０−２ｘｇ０−２＋…＋ｖ０の係数ｖｉを決定し、ベースポイントの因子：Ｄ０＝（Ｕ（ｘ）、Ｖ（ｘ））を決定する処理を実行する構成である。
【０１７６】
ベースポイント生成部１０１は、例えば、超楕円曲線の種数ｇ（ｇｅｎｕｓ）＝２である場合には、ウェイト（ｗｅｉｇｈｔ）１となる因子をベースポイントとして生成する。演算処理部１０２は、種数ｇ（ｇｅｎｕｓ）＝２である場合、因子の加算処理として、ウェイト（ｗｅｉｇｈｔ）１の因子＋ウェイト（ｗｅｉｇｈｔ）２の因子の加算処理を実行する。このとき、演算処理部１０２は、加算演算処理アルゴリズム：ＥｘＨａｒＡＤＤ２＋１→２を実行する。
【０１７７】
また、ベースポイント生成部１０１は、超楕円曲線の種数ｇ（ｇｅｎｕｓ）＝３である場合には、ウェイト（ｗｅｉｇｈｔ）１もしくは２となる因子をベースポイントとして生成する。演算処理部１０２は、因子の加算処理として、ウェイト（ｗｅｉｇｈｔ）１の因子＋ウェイト（ｗｅｉｇｈｔ）３の因子の加算処理、またはウェイト（ｗｅｉｇｈｔ）２の因子＋ウェイト（ｗｅｉｇｈｔ）３の因子の加算処理を実行する。このとき、演算処理部１０２は、加算演算処理アルゴリズム：ＥｘＨａｒＡＤＤ３＋２→３、または、加算演算処理アルゴリズム：ＥｘＨａｒＡＤＤ３＋１→３、の少なくともいずれかの加算演算処理アルゴリズムを実行する。
【０１７８】
なお、演算処理部１０２は、Ｈａｒｌｅｙのアルゴリズムに従った加算アルゴリズムを含む演算処理を実行し、ｂｉｎａｒｙ法またはｄｏｕｂｌｅ−ａｎｄ−ａｄｄ−ａｌｗａｙｓ法の少なくともいずれかのスカラー倍算アルゴリズムに従った演算を実行する。あるいは、演算処理部１０２は、Ｃａｎｔｏｒのアルゴリズムに従った加算アルゴリズムを含む演算を実行する構成としてもよい。
【０１７９】
また、前述したように、ベースポイント生成部１０１は、超楕円曲線の種数ｇ（ｇｅｎｕｓ）より小さいウェイト（ｗｅｉｇｈｔ）ｇ０（ただし、１≦ｇ０＜ｇ）の因子のうち、因子のＭｕｍｆｏｒｄ表現の多項式の係数が少なくとも一つ以上０または１である因子をベースポイントとして生成する処理を実行する構成してもよく、このベースポイント生成処理により更なる演算の高速化が実現される。
【０１８０】
［５．電子署名生成および検証アルゴリズムにおける本発明の適用例］
以下に本発明の処理を適用可能な具体的な暗号処理アルゴリズムの例として、楕円曲線暗号を適用した電子署名生成および検証アルゴリズムであるＥＣＤＳＡ（ＥＣ−Ｄｉｇｉｔａｌ Ｓｉｇｎａｔｕｒｅ Ａｌｇｏｒｉｔｈｍ）のスカラー倍算に本発明の演算手法を適用した場合について説明する。ＩＥＥＥ１３６３によるとＥＣＤＳＡによる署名生成、検証は以下のシーケンスによって実行される。
【０１８１】
（１）入力
（１−１）楕円曲線のドメインパラメータ及びベースポイントＧ（位数ｒ）
（１−２）署名者の秘密鍵ｓ
（１−３）平文Ｍ
（２）鍵生成
（２−１）秘密鍵ｓに対してＷ＝ｓＧを公開鍵とする
（３）署名生成
（３−１）ランダムな整数０＜ｕ＜ｒを生成
（３−２）Ｖ＝ｕＧ＝（ｘｖ、ｙｖ）を計算
（３−３）ｘｖを整数に変換し、ｉとする
（３−４）ｃ＝ｉ  ｍｏｄ  ｒを計算。ｃ＝０ならｓｔｅｐ３−１へ
（３−５）ｆ＝ｈ（Ｍ）、ｈはｈａｓｈ関数
（３−６）ｄ＝ｕ−１（ｆ＋ｓｃ）ｍｏｄ  ｒを計算。ｄ＝０ならｓｔｅｐ３−１へ
（３−７）（ｃ、ｄ）を平文Ｍに対する署名にする。
（４）署名検証
（４−１）０＜ｃ＜ｒ、０＜ｄ＜ｒをチェック。該当しない場合ｉｎｖａｌｉｄを出力
（４−２）ｈ＝ｄ−１ｍｏｄ  ｒ、ｈ１＝ｆｈ  ｍｏｄ  ｒ、ｈ２＝ｃｈ  ｍｏｄ  ｒを計算。
（４−３）Ｐ＝（ｘｐ、ｙｐ）＝ｈ１Ｇ＋ｈ２Ｗを計算。Ｐ＝Ｏならばｉｎｖａｌｉｄを出力
（４−４）ｘｐを整数に変換し、ｉとする。
（４−５）ｃ'＝ｉ  ｍｏｄ  ｒを計算する。
（４−６）ｃ'＝ｃならばｖａｌｉｄを出力。そうでないならばｉｎｖａｌｉｄを出力。
【０１８２】
上記アルゴリズムにおいて下記の処理が超楕円曲線を用いた本提案法が適用できる箇所である。
（２−１）秘密鍵ｓに対してＷ＝ｓＧを公開鍵とする
（３−２）Ｖ＝ｕＧ＝（ｘｖ、ｙｖ）を計算
（４−３）Ｐ＝（ｘｐ、ｙｐ）＝ｈ１Ｇ＋ｈ２Ｗを計算。Ｐ＝Ｏならばｉｎｖａｌｉｄを出力
【０１８３】
これらの各ステップ（２−１），（３−２），（４−３）における演算処理、Ｗ＝ｓＧ、Ｖ＝ｕＧ、Ｐ＝（ｘｐ、ｙｐ）＝ｈ１Ｇ＋ｈ２Ｗにおけるｈ１Ｇの演算処理は、因子のスカラー倍算処理であり、本発明の適用による高速化が可能となる。
【０１８４】
［６．暗号処理装置のハードウェア構成例］
最後に、上述の暗号処理を実行するデバイスとしてのＩＣモジュール２００の構成例を図６に示す。上述の処理は、例えばＰＣ、ＩＣカード、リーダライタ、その他、様々な情報処理装置において実行可能であり、図６に示すＩＣモジュール２００は、これら様々な機器に構成することが可能である。
【０１８５】
図６に示すＣＰＵ(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)
２０２  メモリ
２０３  暗号処理部
２０４  乱数発生器
２０５  送受信部
【図１】
2005258228.tif 000026
【図２】
2005258228.tif 000027
【図３】
2005258228.tif 000028
【図４】
2005258228.tif 000029
【図５】
2005258228.tif 000030
【図６】
2005258228.tif 000031