(57)【要約】【課題】  超楕円暗号処理において並列演算処理の適用による高速演算を実現する装置および方法を実現する。【解決手段】  超楕円暗号処理演算におけるスカラー倍算において、加算、２倍算の演算シーケンス中に含まれる演算ステップから相互に影響を及ぼさない演算ステップを抽出し、並列演算処理として実行する構成とした。種数ｇ＝２，３の超楕円曲線で用いられる因子の加算、２倍算アル演算ステップの並列処理を実行し高速化した。ハードウェアにおいては、複数の乗算器、加算器の並列処理を実行するまた、ソフトウェアにおいては、例えばＳＩＭＤ命令に従った１２８ｂｉｔデータの並列シフト処理、並列排他論理和（ＸＯＲ）処理、および並列ＡＮＤ処理演算を適用した処理によって、並列演算を含む超楕円曲線暗号処理演算を実行する。【選択図】  図３
2005043637.tif 000002
【特許請求の範囲】
【請求項１】
超楕円曲線暗号に基づく暗号処理演算を実行する暗号処理装置であり、
並列処理可能な複数の乗算器、または並列処理可能な複数の加算器の少なくともいずれかを備え、
超楕円曲線暗号に基づく暗号処理演算シーケンス中の複数の演算ステップを前記複数の乗算器、または複数の加算器の少なくともいずれかにおいて並列処理として実行する構成としたことを特徴とする暗号処理装置。
【請求項２】
前記複数の乗算器、または前記複数の加算器の少なくともいずれかにおいて並列実行する演算ステップは、
超楕円曲線暗号に基づくスカラー倍算における加算または２倍算の演算シーケンス中における複数の演算ステップであることを特徴とする請求項１に記載の暗号処理装置。
【請求項３】
前記複数の乗算器、または並列処理可能な複数の加算器の少なくともいずれかにおいて並列実行する演算ステップは、種数ｇ＝２または３とした超楕円曲線上の２つの因子Ｄ１，Ｄ２についての加算処理としてのＤ３＝Ｄ１＋Ｄ２の演算シーケンス、または、因子Ｄ１についての２倍算処理としてのＤ３＝２Ｄ１の演算シーケンス中における複数の演算ステップであることを特徴とする請求項１に記載の暗号処理装置。
【請求項４】
超楕円曲線暗号に基づく暗号処理演算を実行する暗号処理装置であり、
暗号処理演算シーケンスを記述したプログラムに従って超楕円曲線暗号に基づく暗号処理演算を実行するデータ処理部と、
前記暗号処理演算における演算データのデータ記憶部としてのレジスタとを有し、
前記データ処理部は、超楕円曲線暗号に基づく暗号処理演算シーケンスに含まれる複数の演算ステップを、前記レジスタを適用した並列演算処理として実行する構成としたことを特徴とする暗号処理装置。
【請求項５】
前記データ処理部の実行する並列演算処理は、演算データの並列シフト処理、または並列排他論理和（ＸＯＲ）処理、または並列ＡＮＤ処理の少なくともいずれかを含むことを特徴とする請求項４に記載の演算処理装置。
【請求項６】
前記データ処理部の実行する並列演算処理は、
ＳＩＭＤ(Single Instruction, Multiple Data)命令の適用処理として実行する構成であることを特徴とする請求項４に記載の演算処理装置。
【請求項７】
前記データ処理部は、
有限体ＧＦ（２ｎ）の元である６４ビット以下の２つのデータを各々１２８ビットレジスタに格納し、該レジスタ格納データに対する並列シフト処理、または並列排他論理和（ＸＯＲ）処理、または並列ＡＮＤ処理の少なくともいずれかを含む処理として前記並列演算処理を実行する構成であることを特徴とする請求項４に記載の演算処理装置。
【請求項８】
前記並列演算処理は、
超楕円曲線暗号に基づくスカラー倍算における加算または２倍算の演算シーケンス中における複数の演算ステップであることを特徴とする請求項４に記載の暗号処理装置。
【請求項９】
前記並列演算処理は、
種数ｇ＝３における有限体ＧＦ（２ｎ）のＡ×Ｂ，Ａ×Ｃの並列乗算処理であることを特徴とする請求項４に記載の暗号処理装置。
【請求項１０】
超楕円曲線暗号に基づく暗号処理演算を実行する暗号処理演算方法であり、
超楕円曲線暗号に基づくスカラー倍算における加算または２倍算の演算シーケンスに含まれる複数の演算ステップ中、並列処理によって演算結果に影響を及ぼさない演算ステップを並列演算処理ステップとして設定した演算シーケンスに従って演算処理を実行することを特徴とする暗号処理演算方法。
【請求項１１】
前記並列演算処理ステップにおいて並列に実行する演算処理は、
超楕円曲線暗号に基づくスカラー倍算における加算または２倍算の演算シーケンス中における複数の演算であることを特徴とする請求項１０に記載の暗号処理演算方法。
【請求項１２】
前記並列演算処理ステップにおいて並列に実行する演算処理は、
種数ｇ＝２または３とした超楕円曲線上の２つの因子Ｄ１，Ｄ２についての加算処理としてのＤ３＝Ｄ１＋Ｄ２の演算シーケンス、または、因子Ｄ１についての２倍算処理としてのＤ３＝２Ｄ１の演算シーケンス中における複数の演算ステップであることを特徴とする請求項１０に記載の暗号処理演算方法。
【請求項１３】
前記並列演算処理ステップにおいて並列に実行する演算処理は、
暗号処理演算シーケンスを記述したプログラムに従って実行するものであり、演算データの並列シフト処理、または並列排他論理和（ＸＯＲ）処理、または並列ＡＮＤ処理の少なくともいずれかを含むことを特徴とする請求項１０に記載の暗号処理演算方法。
【請求項１４】
前記並列演算処理ステップにおいて並列に実行する演算処理は、
ＳＩＭＤ(Single Instruction, Multiple Data)命令の適用処理として実行することを特徴とする請求項１０に記載の暗号処理演算方法。
【請求項１５】
前記並列演算処理ステップにおいて並列に実行する演算処理は、
有限体ＧＦ（２ｎ）の元である６４ビット以下の２つのデータを各々１２８ビットレジスタに格納し、該レジスタ格納データに対する並列シフト処理、または並列排他論理和（ＸＯＲ）処理、または並列ＡＮＤ処理の少なくともいずれかを含む処理として実行することを特徴とする請求項１０に記載の暗号処理演算方法。
【請求項１６】
前記並列演算処理ステップにおいて並列に実行する演算処理は、
種数ｇ＝３における有限体ＧＦ（２ｎ）のＡ×Ｂ，Ａ×Ｃの並列乗算処理であることを特徴とする請求項１０に記載の暗号処理演算方法。
【請求項１７】
暗号処理演算をコンピュータ・システム上で実行せしめるコンピュータ・プログラムであって、
超楕円曲線暗号に基づくスカラー倍算における加算または２倍算の演算シーケンスに含まれる複数の演算ステップ中、並列処理によって演算結果に影響を及ぼさない演算ステップを並列演算処理ステップとして設定した演算シーケンスに従って演算処理を実行するステップ、
を有することを特徴とするコンピュータ・プログラム。
【請求項１８】
前記コンピュータ・プログラムは、
有限体ＧＦ（２ｎ）の元である６４ビット以下の２つのデータを各々１２８ビットレジスタに格納するステップと、
前記レジスタに格納されたデータに対する並列シフト処理、または並列排他論理和（ＸＯＲ）処理、または並列ＡＮＤ処理の少なくともいずれかを実行するステップと、
を有することを特徴とする請求項１７に記載のコンピュータ・プログラム。
【請求項１９】
前記コンピュータ・プログラムは、
種数ｇ＝３における有限体ＧＦ（２ｎ）のＡ×Ｂ，Ａ×Ｃの並列乗算処理を実行するステップを有することを特徴とする請求項１７に記載のコンピュータ・プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、暗号処理装置および暗号処理演算方法、並びにコンピュータ・プログラムに関する。さらに詳細には、超楕円曲線暗号処理演算の高速化を実現する暗号処理装置および暗号処理演算方法、並びにコンピュータ・プログラムに関する。
【背景技術】
【０００２】
昨今、ネットワーク通信、電子商取引の発展に伴い、通信におけるセキュリティ確保が重要な問題となっている。セキュリティ確保の１つの方法が暗号技術であり、現在、様々な暗号化手法を用いた通信が実際に行なわれている。
【０００３】
例えばＩＣカード等の小型の装置中に暗号処理モジュールを埋め込み、ＩＣカードと、データ読み取り書き込み装置としてのリーダライタとの間でデータ送受信を行ない、認証処理、あるいは送受信データの暗号化、復号化を行なうシステムが実用化されている。
【０００４】
暗号処理を実行する例えばＩＣカードは、例えば駅の改札などの様々なゲート、あるいはショッピングセンターなどで盛んに利用されるようになっており、小型化および処理の迅速化の要求が厳しくなってきている。
【０００５】
暗号化方式には、大別して共通鍵方式、公開鍵方式がある。共通鍵方式は、対称暗号方式ともよばれ、発信者、受信者の双方で共通の鍵を保有する。共通鍵方式の代表的な方法として、ＤＥＳ（Data Encryption Standard）がある。ＤＥＳアルゴリズムの特徴は、暗号化と復号化とをほぼ同じアルゴリズムで実行可能なことである。
【０００６】
この共通鍵暗号に対して、発信者と受信者の鍵を異なるものとした構成が公開鍵方式または非対称暗号方式である。公開鍵暗号方式では、暗号化、復号化に共通の鍵を用いる共通鍵暗号方式と異なり、秘密に保つ必要のある秘密鍵は、特定の１人が持てばよいため鍵の管理において有利である。ただし、公開鍵暗号方式は共通鍵暗号方式に比較してデータ処理速度が遅く、一般には、秘密鍵の配送、デジタル署名等のデータ量の少ない対象に多く用いられている。公開鍵暗号方式の代表的なものにはＲＳＡ（Rivest-Shamir-Adleman）暗号や、楕円曲線暗号（ＥＣＣ：Ellipitic Curve Cryptography）が知られている。
【０００７】
楕円曲線暗号（Elliptic Curve Cryptography）は、素体上の楕円曲線ｙ２＝ｘ３＋ａｘ＋ｂ（４ａ３＋２７ｂ２≠０）や、２の拡大体上の楕円曲線ｙ２＋ｘｙ＝ｘ３＋ａｘ２＋ｂ（ｂ≠０）などを用いる。これらの曲線上の点に無限遠点（Ｏ）を加えた集合は、加法に関して有限群をなし、無限遠点（Ｏ）はその単位元となる。以下、この有限群上の点の加法を＋で表す。この有限群上の異なる２点Ｐ，Ｑの加算Ｐ＋Ｑを「点の加算」、点Ｐと点Ｐの加算Ｐ＋Ｐ＝２Ｐを「点の２倍算」と呼ぶ。また、点Ｐをｋ回加算した点Ｐ＋Ｐ＋…＋Ｐ＝ｋＰを求める演算を「点のスカラー倍算」と呼ぶ。
【０００８】
点のスカラー倍算は、点の加算、および点の２倍算を用いて構成できることが知られている。素体上の楕円曲線や２の拡大体上の楕円曲線上のアフィン座標系（ｘ，ｙ）や射影座標（Ｘ，Ｙ，Ｚ）における点の加算法、点の２倍算法、および点のスカラー倍算法は、ＩＥＥＥ  P1363/D13 Standard Specifications for Public Key Cryptographyに記されている。
【０００９】
楕円曲線暗号を一般化した方式として、Koblitz、Cantorによって提案された超楕円曲線暗号方式がある。超楕円曲線暗号方式については、例えば非特許文献１、非特許文献２に記載されている。超楕円曲線暗号方式においては、超楕円加算及び２倍算の演算は楕円曲線と同様に曲線が定義されている有限体（素体及び素数の拡大体，定義体と呼ぶ）の元についての演算として実行される。
【００１０】
楕円曲線暗号については、演算処理の高速化の研究が進められており、並列演算による高速化の提案がなされている。具体的には、楕円曲線暗号の加算、２倍算を高速に実行するための研究として、プロセッサのＳＩＭＤ(Single Instruction, Multiple Data)命令を用いて並列処理を行うアルゴリズムについて幾つか研究が行われている。
【００１１】
ＳＩＭＤ命令とはプロセッサの持つ一つの命令で同じ種類の複数の演算（乗算や加算など）を同時に行う命令であり、近年のＩｎｔｅｌやＳｕｎなどの代表的なプロセッサに実装されている命令セットである。この命令を初めて楕円曲線暗号に利用したのはSmartである。一般的な楕円曲線とHessian形式という特殊な楕円曲線について並列処理のアルゴリズムが提案された。これは、例えば非特許文献３に記載されている。一般的な楕円曲線についての並列演算処理による高速化に関してさらに、計算量の削減を実現する構成については、例えば非特許文献４、非特許文献５に説明が記載されている。
【００１２】
また、特許文献１は、複数の乗算器を備えた演算装置によって、楕円曲線加算処理および２倍算処理を実行することにより演算処理を高速化した装置を開示している。
【００１３】
しかし、いずれの従来技術においても、超楕円曲線暗号に関して、楕円曲線暗号で提案されているような並列処理を使ったアルゴリズムについての提案は示されていない。Harleyのアルゴリズムは超楕円曲線暗号の加算、２倍算を計算するアルゴリズムとしては最も高速なものである。しかしこのアルゴリズムは処理手順が非常に長いため手順の効率化は一つの課題であった。楕円曲線の場合、ＳＩＭＤ(Single Instruction, Multiple Data)命令を使って並列処理を行う場合、プロセッサのワードサイズに比べて定義体のビット長が長いために、複数個に分けて処理を行うことが必要になる。従って楕円曲線での方法はソフトウェアにおける効率のよい計算方法であるとはいえず、高速化の効果は低いという問題がある。
【特許文献１】特開２００１−２０２０１９号公報
【非特許文献１】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
【非特許文献３】N. Smart. The Hessian form of an elliptic curve. CHES2001, LNCS2162, pp. 118-125, Springer-Verlag, 2001.
【非特許文献４】K.Aoki, F.Hoshino, T.Kobayashi and H.Oguro. Elliptic curve arithmetic using SIMD. ISC2001, LNCS2200, pp.235-247, Springer-Verlag, 2001.
【非特許文献５】T.Izu and T.Takagi. Fast elliptic curve multiplications with SIMD operations. ICICS 2002, LNCS 2513, pp.217-230, Springer-Verlag, 2002.
【発明の開示】
【発明が解決しようとする課題】
【００１４】
本発明は、上記問題点に鑑みてなされたものであり、超楕円曲線暗号処理における加算処理、２倍算処理を高速化することを可能とした手法を提供するものであり、超楕円曲線暗号処理アルゴリズムにおける加算、２倍算の演算中、他に影響を及ぼさない演算処理を抽出して、並列演算を実行することで全体の処理サイクルの短縮化を図り、演算処理の高速化を実現する暗号処理装置および暗号処理演算方法、並びにコンピュータ・プログラムを提供することを目的とする。
【００１５】
本発明は、例えば１２８ｂｉｔ(64bitx2)ＳＩＭＤ命令を使って有限体ＧＦ（２ｎ）での乗算、加算を並列に演算することで、処理の高速化を実現する暗号処理装置および暗号処理演算方法、並びにコンピュータ・プログラムを提供することを目的とする。
【００１６】
また、本発明は、超楕円加算、２倍算のアルゴリズムにおいて並列実行可能な乗算、加算処理に、１２８ｂｉｔ(64bitx2)ＳＩＭＤ命令を使った演算を適用し、超楕円曲線暗号をソフトウェアで高速に演算することを可能とする暗号処理装置および暗号処理演算方法、並びにコンピュータ・プログラムを提供することを目的とする。
【課題を解決するための手段】
【００１７】
本発明の第１の側面は、
超楕円曲線暗号に基づく暗号処理演算を実行する暗号処理装置であり、
並列処理可能な複数の乗算器、または並列処理可能な複数の加算器の少なくともいずれかを備え、
超楕円曲線暗号に基づく暗号処理演算シーケンス中の複数の演算ステップを前記複数の乗算器、または複数の加算器の少なくともいずれかにおいて並列処理として実行する構成としたことを特徴とする暗号処理装置にある。
【００１８】
さらに、本発明の暗号処理装置の一実施態様において、前記複数の乗算器、または前記複数の加算器の少なくともいずれかにおいて並列実行する演算ステップは、超楕円曲線暗号に基づくスカラー倍算における加算または２倍算の演算シーケンス中における複数の演算ステップであることを特徴とする。
【００１９】
さらに、本発明の暗号処理装置の一実施態様において、前記複数の乗算器、または並列処理可能な複数の加算器の少なくともいずれかにおいて並列実行する演算ステップは、種数ｇ＝２または３とした超楕円曲線上の２つの因子Ｄ１，Ｄ２についての加算処理としてのＤ３＝Ｄ１＋Ｄ２の演算シーケンス、または、因子Ｄ１についての２倍算処理としてのＤ３＝２Ｄ１の演算シーケンス中における複数の演算ステップであることを特徴とする。
【００２０】
さらに、本発明の第２の側面は、
超楕円曲線暗号に基づく暗号処理演算を実行する暗号処理装置であり、
暗号処理演算シーケンスを記述したプログラムに従って超楕円曲線暗号に基づく暗号処理演算を実行するデータ処理部と、
前記暗号処理演算における演算データのデータ記憶部としてのレジスタとを有し、
前記データ処理部は、超楕円曲線暗号に基づく暗号処理演算シーケンスに含まれる複数の演算ステップを、前記レジスタを適用した並列演算処理として実行する構成としたことを特徴とする暗号処理装置にある。
【００２１】
さらに、本発明の暗号処理装置の一実施態様において、前記データ処理部の実行する並列演算処理は、演算データの並列シフト処理、または並列排他論理和（ＸＯＲ）処理、または並列ＡＮＤ処理の少なくともいずれかを含むことを特徴とする。
【００２２】
さらに、本発明の暗号処理装置の一実施態様において、前記データ処理部の実行する並列演算処理は、ＳＩＭＤ(Single Instruction, Multiple Data)命令の適用処理として実行する構成であることを特徴とする。
【００２３】
さらに、本発明の暗号処理装置の一実施態様において、前記データ処理部は、有限体ＧＦ（２ｎ）の元である６４ビット以下の２つのデータを各々１２８ビットレジスタに格納し、該レジスタ格納データに対する並列シフト処理、または並列排他論理和（ＸＯＲ）処理、または並列ＡＮＤ処理の少なくともいずれかを含む処理として前記並列演算処理を実行する構成であることを特徴とする。
【００２４】
さらに、本発明の暗号処理装置の一実施態様において、前記並列演算処理は、超楕円曲線暗号に基づくスカラー倍算における加算または２倍算の演算シーケンス中における複数の演算ステップであることを特徴とする。
【００２５】
さらに、本発明の暗号処理装置の一実施態様において、前記並列演算処理は、種数ｇ＝３における有限体ＧＦ（２ｎ）のＡ×Ｂ，Ａ×Ｃの並列乗算処理であることを特徴とする。
【００２６】
さらに、本発明の第３の側面は、
超楕円曲線暗号に基づく暗号処理演算を実行する暗号処理演算方法であり、
超楕円曲線暗号に基づくスカラー倍算における加算または２倍算の演算シーケンスに含まれる複数の演算ステップ中、並列処理によって演算結果に影響を及ぼさない演算ステップを並列演算処理ステップとして設定した演算シーケンスに従って演算処理を実行することを特徴とする暗号処理演算方法にある。
【００２７】
さらに、本発明の暗号処理演算方法の一実施態様において、前記並列演算処理ステップにおいて並列に実行する演算処理は、超楕円曲線暗号に基づくスカラー倍算における加算または２倍算の演算シーケンス中における複数の演算であることを特徴とする。
【００２８】
さらに、本発明の暗号処理演算方法の一実施態様において、前記並列演算処理ステップにおいて並列に実行する演算処理は、種数ｇ＝２または３とした超楕円曲線上の２つの因子Ｄ１，Ｄ２についての加算処理としてのＤ３＝Ｄ１＋Ｄ２の演算シーケンス、または、因子Ｄ１についての２倍算処理としてのＤ３＝２Ｄ１の演算シーケンス中における複数の演算ステップであることを特徴とする。
【００２９】
さらに、本発明の暗号処理演算方法の一実施態様において、前記並列演算処理ステップにおいて並列に実行する演算処理は、暗号処理演算シーケンスを記述したプログラムに従って実行するものであり、演算データの並列シフト処理、または並列排他論理和（ＸＯＲ）処理、または並列ＡＮＤ処理の少なくともいずれかを含むことを特徴とする。
【００３０】
さらに、本発明の暗号処理演算方法の一実施態様において、前記並列演算処理ステップにおいて並列に実行する演算処理は、ＳＩＭＤ(Single Instruction, Multiple Data)命令の適用処理として実行することを特徴とする。
【００３１】
さらに、本発明の暗号処理演算方法の一実施態様において、前記並列演算処理ステップにおいて並列に実行する演算処理は、有限体ＧＦ（２ｎ）の元である６４ビット以下の２つのデータを各々１２８ビットレジスタに格納し、該レジスタ格納データに対する並列シフト処理、または並列排他論理和（ＸＯＲ）処理、または並列ＡＮＤ処理の少なくともいずれかを含む処理として実行することを特徴とする。
【００３２】
さらに、本発明の暗号処理演算方法の一実施態様において、前記並列演算処理ステップにおいて並列に実行する演算処理は、種数ｇ＝３における有限体ＧＦ（２ｎ）のＡ×Ｂ，Ａ×Ｃの並列乗算処理であることを特徴とする。
【００３３】
さらに、本発明の第４の側面は、
暗号処理演算をコンピュータ・システム上で実行せしめるコンピュータ・プログラムであって、
超楕円曲線暗号に基づくスカラー倍算における加算または２倍算の演算シーケンスに含まれる複数の演算ステップ中、並列処理によって演算結果に影響を及ぼさない演算ステップを並列演算処理ステップとして設定した演算シーケンスに従って演算処理を実行するステップ、
を有することを特徴とするコンピュータ・プログラムにある。
【００３４】
さらに、本発明のコンピュータ・プログラムの一実施態様において、前記コンピュータ・プログラムは、有限体ＧＦ（２ｎ）の元である６４ビット以下の２つのデータを各々１２８ビットレジスタに格納するステップと、前記レジスタに格納されたデータに対する並列シフト処理、または並列排他論理和（ＸＯＲ）処理、または並列ＡＮＤ処理の少なくともいずれかを実行するステップと、を有することを特徴とする。
【００３５】
さらに、本発明のコンピュータ・プログラムの一実施態様において、前記コンピュータ・プログラムは、種数ｇ＝３における有限体ＧＦ（２ｎ）のＡ×Ｂ，Ａ×Ｃの並列乗算処理を実行するステップを有することを特徴とする。
【００３６】
なお、本発明のコンピュータ・プログラムは、例えば、様々なプログラム・コードを実行可能なコンピュータ・システムに対して、コンピュータ可読な形式で提供する記憶媒体、通信媒体、例えば、ＣＤやＦＤ、ＭＯなどの記録媒体、あるいは、ネットワークなどの通信媒体によって提供可能なコンピュータ・プログラムである。このようなプログラムをコンピュータ可読な形式で提供することにより、コンピュータ・システム上でプログラムに応じた処理が実現される。
【００３７】
本発明のさらに他の目的、特徴や利点は、後述する本発明の実施例や添付する図面に基づくより詳細な説明によって明らかになるであろう。なお、本明細書においてシステムとは、複数の装置の論理的集合構成であり、各構成の装置が同一筐体内にあるものには限らない。
【発明の効果】
【００３８】
本発明の構成によれば、並列演算を含む演算シーケンスに従った超楕円曲線暗号処理における演算を実行する構成であるので、超楕円曲線暗号処理における高速演算が可能となる。
【００３９】
本発明の構成では、超楕円曲線暗号処理におけるカラー倍算における加算または２倍算の演算シーケンスに含まれる複数の演算ステップ中、並列処理によって演算結果に影響を及ぼさない演算ステップを並列演算処理ステップとして設定した演算シーケンスに従った演算処理を実行する構成であり、暗号処理の結果に全く影響を及ぼすことなく、高速暗号処理を実現することが可能となる。
【００４０】
また本発明の構成に従ったハードウェアでの実装構成例においては、並列処理可能な乗算器、加算器を複数併設し、並列実行可能な演算処理を同時に実行させる構成としたので、超楕円曲線暗号処理の高速化が実現されることになる。
【００４１】
また、本発明の構成をソフトウェアプログラムによって実行する構成においては、並列シフト処理、並列排他論理和（ＸＯＲ）処理、および並列ＡＮＤ処理演算を適用した処理によって、並列演算を含む超楕円曲線暗号処理演算が可能となり、ソフトウェアに従った暗号処理においても高速化が実現される。
【００４２】
また、例えばＳＩＭＤ命令を使ったソフトウェアの実装における並列乗算を含む処理により、既存のプロセッサにおいて実行可能な１２８ｂｉｔデータに基づく演算を実行した場合でも、高速な処理の実現が可能となる。
【発明を実施するための最良の形態】
【００４３】
以下、本発明の暗号処理装置および暗号処理演算方法、並びにコンピュータ・プログラムの詳細について説明する。
【００４４】
以下、下記項目に従って説明を行う。
（１）Ｈａｒｌｅｙアルゴリズムの並列演算処理を用いた高速演算方法
（２）並列演算処理を実行するハードウェア構成
（３）ソフトウェアによる並列演算処理
（４）１２８ビット演算処理によるＧＦ（２ｎ）演算処理構成
（５）プログラム実行型ＩＣモジュール
【００４５】
（１）Ｈａｒｌｅｙアルゴリズムの並列演算処理を用いた高速演算方法
まず、超楕円曲線暗号処理において実行可能なＨａｒｌｅｙアルゴリズムの並列演算処理を用いた高速演算方法について説明する。
【００４６】
超楕円曲線暗号処理では、曲線を特徴づける値として種数(genus)ｇが定義されている。ｐを素数、nを正の整数、ｑ＝ｐｎとする。このとき有限体Ｆｑ上で定義される種数ｇの超楕円曲線Ｃは以下の方程式、
ｙ２＋ｈ（ｘ）ｙ＝ｆ（ｘ）
で定義される。ここで、ｈ（ｘ），ｆ（ｘ）∈Ｆｑ［ｘ］，ｆ（ｘ）は、は次数２ｇ＋１のｍｏｎｉｃ多項式である。
【００４７】
超楕円曲線暗号の定義体の演算サイズ（ビット長）は楕円曲線暗号と同等の安全性を仮定した場合、楕円曲線の定義体の演算サイズに比べて１／ｇに小さくなることが知られている。演算サイズが小さいことは実装上メリットがあり、超楕円曲線暗号の利点の一つして挙げられる。
【００４８】
実用上安全な楕円曲線暗号として使われている鍵長は１６０ｂｉｔである。この場合、楕円曲線の定義体のサイズは１６０ｂｉｔとなる。超楕円曲線の定義体のサイズは種数ｇ＝２の曲線で８０ｂｉｔ程度、種数ｇ＝３の曲線で５３ｂｉｔ程度となる。
【００４９】
次に、超楕円曲線暗号における加算処理、および２倍算の定義とスカラー倍算について説明する。点の形式的和である因子をＤ１とするとスカラー倍算Ｄ２＝ｋＤ１が定義される。Ｄ２からｋを求める問題は超楕円曲線におけるヤコビ多様体上の離散対数問題として公開鍵暗号として用いることができる。因子のスカラー倍算は超楕円加算と超楕円２倍算の組み合わせで計算することができる。スカラー倍算のアルゴリズムとしてバイナリ法を用いた場合を例に挙げる。ここでｋの２進数表現を、（ｋ１−１，・・・・・，ｋ０），ｋ１−２，・・・，０とする。
【００５０】
Ｉｎｐｕｔ  Ｄ０
Ｄ←Ｄ０
ｆｏｒ  ｉ  ｆｒｏｍ  ｌ−２ｔｏ０
｛
Ｄ←２Ｄ    ／／２倍算
ｉｆ  ｋｉ＝１  ｔｈｅｎ  Ｄ←Ｄ＋Ｄ０  ／／加算
｝
Ｏｕｔｐｕｔ  Ｄ＝ｋＤ０
【００５１】
上記のアルゴリズムが、超楕円曲線暗号処理におけるバイナリ法を用いたスカラー倍算のアルゴリズムである。
【００５２】
次に因子の表現について、説明する。
因子は以下の形式で表現することができる。
【数１】
2005043637.tif 000003
【００５３】
上記式において、Ｐｉ＝（ｘｉ，ｙｉ）かつｉ≠ｊに対してＰｉ≠Ｐｊである。この形式の因子の表現を半被約因子とよぶ。また、
【数２】
2005043637.tif 000004
をＤのウェイト（weight）と呼ぶ。さらにウェイト（weight）が種数ｇ以下である半被約因子を被約因子と呼ぶ。
【００５４】
超楕円曲線のヤコビ（Jacobi）多様体上の任意の半被約因子Ｄは下記の多項式：Ｕ，Ｖ∈Ｆｑ［ｘ］を用いて、Ｄ＝（Ｕ，Ｖ）として表現できる。これをマンホード（Mumford）表現と呼ぶ。なお、マンホード（Mumford）表現については、例えば「D. Mumford, Tata lectures on theta II, Progress in Mathematics, no. 43, Birkhauser, 1984.」に記載されている。
【数３】
2005043637.tif 000005
【００５５】
種数ｇ＝２の任意の被約因子Ｄは、マンホード（Mumford）表現を用いると有限体Ｆｑ上の元を係数に持つ２次以下の多項式の組（Ｕ，Ｖ）として表現することができる。
【００５６】
種数ｇ＝３の任意の被約因子Ｄは、マンホード（Mumford）表現を用いると有限体Ｆｑ上の元を係数に持つ３次以下の多項式の組（Ｕ，Ｖ）として表現できる。
【００５７】
他の因子の表現として変形マンホード（Mumford）表現、あるいは「Weighted Coordinate」がある。変形マンホード（Mumford）表現はマンホード（Mumford）表現（Ｕ，Ｖ）に定数Ｚ倍し、（Ｕ，Ｖ，Ｚ）で表現するものである。「Weighted Coordinate」も同様にマンホード（Mumford）表現に複数の定数（（Ｚ１，Ｚ２）を乗算することで（Ｕ，Ｖ，Ｚ１，Ｚ２）で表現する方法である。いずれもＨａｒｌｅｙのアルゴリズムの計算量を削減するための手法として用いられている。なお、これらについては、例えば、「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 ePring Archive, 2002/153, IACR, 2002.」に説明が記載されている。
【００５８】
次に、超楕円曲線暗号処理における加算と２倍算のアルゴリズムについて説明する。最初に提案された実用的なアルゴリズムはＣａｎｔｏｒのアルゴリズムである。このアルゴリズムについては、例えば、「D.G.Cantor. Computing in the Jacobian of hyperelliptic curve. Math. Comp., Vol.48, No. 177, pp.95-101, 1987」に記載されている。このアルゴリズムは全ての種数の超楕円曲線上の因子に対して適用可能なアルゴリズムであったが、楕円曲線に比べてアルゴリズムが複雑で計算量が多いことが欠点である。
【００５９】
Ｈａｒｌｅｙは種数ｇ＝２の超楕円曲線に限定することでより計算量の少ないアルゴリズムを提案した。Ｈａｒｌｅｙのアルゴリズムは定義体を素体、種数ｇ＝２の曲線、因子の表現はMumford表現を用いている。Ｈａｒｌｅｙアルゴリズムでは最初に因子の次数によって場合分けを行い、各場合分けに応じて因子の異なる計算を行う必要がある。
【００６０】
図１がＨａｒｌｅｙのアルゴリズムに従った加算アルゴリズムのフロー、図２が２倍算のフローである。
【００６１】
図１に示すＨａｒｌｅｙのアルゴリズムに従った加算アルゴリズムは、因子Ｄ１とＤ２からＤ３＝Ｄ１＋Ｄ２を出力する処理を示している。まず、因子Ｄ１とＤ２のウェイト（weight）による場合分けとして、５つの場合分けに基づく処理を決定する。すなわち、
（１）Ｄ１のweight０の場合は、リターンＤ２、すなわちＤ２＝Ｄ３
（２）Ｄ２のweight０の場合は、リターンＤ１、すなわちＤ１＝Ｄ３となる。
その他、Ｄ１およびＤ２のweightに応じて、
（３）weight１＋weight１
（４）weight２＋weight１
（５）weight２＋weigh２
の各処理パターンがある。
【００６２】
さらに、上記（５）weight２＋weigh２の処理においては、因子Ｄ１とＤ２の値に応じて場合わけが実行されて処理がなされる。
すなわち、
（５ａ）Ｄ１≠Ｄ２
（５ｂ）Ｄ１＝Ｐ１＋Ｐ２−２Ｐ∞，Ｄ２＝Ｐ１＋Ｐ３−２Ｐ∞
（５ｃ）Ｄ１＝Ｐ１＋Ｐ２−２Ｐ∞，Ｄ２＝−Ｐ１＋Ｐ３−２Ｐ∞
（５Ｄ）Ｄ１＝Ｄ２
（５Ｅ）Ｄ１＝−Ｄ２
（５Ｆ）Ｕ１＝Ｕ２，Ｄ１≠±Ｄ２
【００６３】
これらの場合分けに基づいて、それぞれ異なった処理が実行される。上記各場合分けにおいて、最も発生頻度の高い処理が（５ａ）の処理である。すなわち、（５）weight２＋weigh２の処理において、（５ａ）Ｄ１≠Ｄ２の場合である。すなわち、これは最も頻繁に起こるケース（Ｍｏｓｔ ｆｒｅｑｕｅｎｔｃａｓｅ）である。このケースの計算アルゴリズムの効率化が超楕円暗号曲線の暗号処理演算の効率化に最も貢献することになる。
【００６４】
図２に示すＨａｒｌｅｙのアルゴリズムに従った２倍算アルゴリズムは、因子Ｄ１からＤ３＝２Ｄ１を出力する処理を示している。まず、因子Ｄ１のウェイト（weight）による場合分けとして、３つの場合分けに基づく処理を決定する。すなわち、
（１）Ｄ１のweight０の場合は、リターン０、すなわちＤ３＝０
さらに、
（２）Ｄ１のweight１の場合、
（３）Ｄ１のweight２の場合、
の各処理パターンがある。
【００６５】
さらに、上記（３）Ｄ１のweight２の処理においては、因子Ｄ１が分岐点を持つか否かによって、場合わけが実行されて処理がなされる。
すなわち、
（３ａ）分岐点なし
（３ｂ）分岐点あり
【００６６】
これらの場合分けに基づいて、それぞれ異なった処理が実行される。上記各場合分けにおいて、最も発生頻度の高い処理が（３ａ）の処理である。すなわち、（３）Ｄ１のweight２の場合において、（３ａ）分岐点なしの場合である。すなわち、これは最も頻繁に起こるケース（Ｍｏｓｔ ｆｒｅｑｕｅｎｔｃａｓｅ）である。このケースの計算アルゴリズムの効率化が超楕円暗号曲線の暗号処理演算の効率化に最も貢献することになる。
【００６７】
本発明の構成においては、超楕円暗号処理におけるスカラー倍算において実行する加算および２倍算における因子に基づく場合分け後の計算処理において、有限体の演算を互いに影響を及ぼさない演算ステップを取り出して、並列に演算することで高速化を実現した。上述したように、因子に基づく場合分けは起こる確率が均等でなく、１つの最も頻繁におこる場合（Ｍｏｓｔ  ｆｒｅｑｕｅｎｔ  ｃａｓｅ）以外はほとんど起こらないことがわかっている。このことは、例えば、「N. Nagao. Improving group law algorithms for Jacobians of hyperelliptic curves. ANTS-IV, LNCS 1838, pp.439-448, Springer-Verlag, 2000.」に記載されている。
【００６８】
従って、頻繁におこる場合（Ｍｏｓｔ  ｆｒｅｑｕｅｎｔ  ｃａｓｅ）を高速化することで、超楕円曲線暗号処理の高速化が実現される。最も頻繁に起こるケース（Ｍｏｓｔ  ｆｒｅｑｕｅｎｔ  ｃａｓｅ）は、すなわち、加算では、図１を参照して説明した（５）weight２＋weigh２の処理において、（５ａ）Ｄ１≠Ｄ２の場合である。２倍算では、図２を参照して説明した（５）weight２＋weigh２の処理において、（５ａ）Ｄ１≠Ｄ２の場合である。
【００６９】
これら、最も頻繁に起こるケースにおける種数ｇ＝２、及びｇ＝３のＧＦ（２ｎ）上で定義される超楕円曲線の２並列演算のアルゴリズムについて説明する。なお、超楕円曲線暗号処理における加算は因子Ｄ１とＤ２からＤ３＝Ｄ１＋Ｄ２を出力する処理である。２倍算は因子Ｄ１からＤ３＝２Ｄ１を出力する処理として実行される。
【００７０】
まず、種数ｇ＝２のＧＦ（２ｎ）上で定義される超楕円曲線の加算処理は、以下の演算処理として定義される。加算は因子Ｄ１とＤ２からＤ３＝Ｄ１＋Ｄ２を出力する処理である。
【００７１】
加算（ａｄｄｉｔｉｏｎ）
１５Ｍ＋２１Ａ＋Ｉ ｗｉｔｈ １１ ｖａｒ．
入力（Ｉｎｐｕｔ）：
Ｄ１＝（ｕ１，ｖ１）ａｎｄ Ｄ２＝（ｕ２，ｖ２）ｗｉｔｈ
ｕ１＝ｘ２＋ｕ１１ｘ＋ｕ１０；
ｕ２＝ｘ２＋ｕ２１ｘ＋ｕ２０；
ｖ１＝ｖ１１ｘ＋ｖ１０；
ｖ２＝ｖ２１ｘ＋ｖ２０；
ｈ（ｘ）＝ｘ２＋ｈ１ｘ＋ｈ０；
ｆ（ｘ）＝ｘ５＋ｆ３ｘ３＋ｆ１ｘ＋ｆ０；
出力（Ｏｕｔｐｕｔ）：
Ｄ３＝（ｕ３，ｖ３）＝Ｄ１＋Ｄ２ ｗｉｔｈ
ｕ３＝ｘ２＋ｕ３１ｘ＋ｕ３０；
ｖ３＝ｖ３１ｘ＋ｖ３０；
【００７２】
上記記述において、
１５Ｍ＋２１Ａ＋Ｉ ｗｉｔｈ １１ ｖａｒ．
は、１５回の乗算処理（Ｍｕｌｔｉｐｌｉｃａｔｉｏｎ）、２１回の加算処理（Ａｄｄｉｔｉｏｎ）、１回の逆元算出（Ｉｎｖｅｒｓｉｏｎ）を１１個の変数（Ｖａｒｉａｂｌｅ）を用いて実行することを意味する。すなわち、１５Ｍ＋２１Ａ＋Ｉは加算処理を実行する際に必要となる計算量を示す。
【００７３】
上記加算処理の具体的な演算処理として、本発明においては下記に示す演算処理を順次実行する。下記演算処理において、Ｒｉｊは中間変数であり、必要に応じてレジスタに格納される。すなわち、中間変数を示す。Ｒｉｊ←Ａは、値Ａ、または演算Ａの結果を中間変数として必要に応じてレジスタＲｉｊに格納する。ｕｘｘ←Ｒｙｙあるいは、ｖｘｘ←Ｒｙｙは、中間変数Ｒｙｙの値をｕｘｘまたはｖｘｘに代入することを意味する。
【００７４】
Ｒ００←ｕ１０
Ｒ０１←ｕ２０
Ｒ０２←ｕ１１
Ｒ０３←ｕ２１
Ｒ０４←Ｒ０２＋Ｒ０３／／Ｒ０５←Ｒ００＋Ｒ０１
Ｒ００←Ｒ０３×Ｒ０４／／Ｒ０２←Ｒ０４×Ｒ０４
Ｒ０６←Ｒ０５＋Ｒ００
Ｒ０７←Ｒ０６×Ｒ０５／／Ｒ００←Ｒ０２×Ｒ０１
Ｒ０８←Ｒ００＋Ｒ０７
Ｒ００←ｖ１０
Ｒ０２←ｖ２０
Ｒ０５←ｖ１１
Ｒ０７←ｖ２１
Ｒ０５←Ｒ０５＋Ｒ０７／／Ｒ００←Ｒ００＋Ｒ０２
Ｒ０７←Ｒ０５×Ｒ０４／／Ｒ０９←Ｒ００×Ｒ０６
Ｒ０２←Ｒ０５＋Ｒ００／／Ｒ１０←Ｒ０４＋Ｒ０６
Ｒ０５←Ｒ０２×Ｒ１０
Ｒ００←Ｒ０９＋Ｒ０７
Ｒ００←Ｒ０５＋Ｒ００
Ｒ１０←Ｒ０７×Ｒ０３／／Ｒ０２←Ｒ０７×Ｒ０１
Ｒ００←Ｒ００＋Ｒ１０／／Ｒ０９←Ｒ０９＋Ｒ０２
Ｒ０２←Ｒ００×Ｒ０８
Ｒ０２←１／Ｒ０２
Ｒ０５←Ｒ０２×Ｒ０８／／Ｒ０７←Ｒ０２×Ｒ００
Ｒ０２←Ｒ０７×Ｒ００／／Ｒ１０←Ｒ０７×Ｒ０９
Ｒ０６←Ｒ０５×Ｒ０８
Ｒ０９←ｕ１０
Ｒ００←Ｒ０６＋１
Ｒ０５←Ｒ１０×Ｒ１０／／Ｒ００←Ｒ０６×Ｒ００
Ｒ０７←Ｒ０５＋Ｒ１０／／Ｒ０８←Ｒ００＋Ｒ０４
Ｒ０５←Ｒ０７＋Ｒ０４／／Ｒ００←ｈ１＋Ｒ０３
Ｒ０７←Ｒ０５×Ｒ０６／／Ｒ０３←Ｒ０４×Ｒ０３
Ｒ００←Ｒ０７＋Ｒ００
Ｒ０５←Ｒ００×Ｒ０６
Ｒ００←Ｒ０３＋Ｒ０５／／Ｒ０７←Ｒ０１＋Ｒ０９
Ｒ０６←Ｒ００＋Ｒ０７
Ｒ０１←ｕ１１
Ｒ００←Ｒ０１＋Ｒ０８／／Ｒ０３←Ｒ０９＋Ｒ０６
Ｒ０５←Ｒ０２×Ｒ００／／Ｒ０７←Ｒ１０×Ｒ０３
Ｒ０１←Ｒ０５＋Ｒ０７
Ｒ０４←Ｒ００＋Ｒ０３／／Ｒ０２←Ｒ０２＋Ｒ１０
Ｒ０２←Ｒ０４×Ｒ０２
Ｒ０２←Ｒ０１＋Ｒ０２／／Ｒ０５←Ｒ０５＋１
Ｒ０１←Ｒ０６×Ｒ０５／／Ｒ０４←Ｒ０８×Ｒ０５
Ｒ００←Ｒ０４＋Ｒ０２／／Ｒ０３←Ｒ０１＋Ｒ０７
Ｒ０５←ｖ１１
Ｒ０７←ｖ１０
Ｒ０４←Ｒ０５＋ｈ１／／Ｒ０１←Ｒ０７＋ｈ０
Ｒ０２←Ｒ００＋Ｒ０４／／Ｒ０１←Ｒ０１＋Ｒ０３
ｕ３１←Ｒ０８
ｕ３０←Ｒ０６
ｖ３１←Ｒ０２
ｖ３０←Ｒ０１
【００７５】
上記演算シーケンスにおいて、
［Ｒ０４←Ｒ０２＋Ｒ０３／／Ｒ０５←Ｒ００＋Ｒ０１］
［Ｒ００←Ｒ０３×Ｒ０４／／Ｒ０２←Ｒ０４×Ｒ０４］など、
［＊＊＊／／＊＊＊］で示す２つの演算を併記した処理が並列処理可能な演算ステップであり、これらの処理を並列実行することで、全体の演算処理サイクルを減少させ、高速演算処理を実現することができる。
【００７６】
具体的には、加算処理の並列処理、すなわち、上記演算シーケンスにおいて、［Ｒｉｊ←ａ＋ｂ／／Ｒｉｊ←ｃ＋ｄ］の並列実行ステップを１３ステップ設定し、乗算処理の並列処理、すなわち、上記演算シーケンスにおいて、［Ｒｉｊ←ａ×ｂ／／Ｒｉｊ←ｃ×ｄ］の並列実行ステップを１０ステップ設定しているので、乗算ステップ（Ｍ）、加算ステップ（Ａ）の各演算ステップ数の削減が実現される。
【００７７】
具体的には、全ての演算をシーケンシャルに実行すると、
演算量＝２５Ｍ＋３４Ａ＋Ｉとなるが、
上述の並列演算処理を実行する本発明の演算シーケンスに従った処理の場合は、
演算量＝１５Ｍ＋２１Ａ＋Ｉとなり、
大幅な計算サイクル数の削減が達成される。
【００７８】
なお、上記演算シーケンスは、プロセッサのＳＩＭＤ(Single Instruction, Multiple Data)命令を用いて並列処理を行うことが可能なシーケンスに設定されている。ＳＩＭＤ命令とはプロセッサの持つ一つの命令で同じ種類の複数の演算（乗算や加算など）を同時に行う命令であり、近年のＩｎｔｅｌやＳｕｎなどの代表的なプロセッサに実装されている命令セットである。
【００７９】
同様に、種数ｇ＝２のＧＦ（２ｎ）上で定義される超楕円曲線の２倍算処理は、以下の演算処理として定義される。２倍算は因子Ｄ１からＤ３＝２Ｄ１を出力する処理として実行される。
【００８０】
２倍算（ｄｏｕｂｌｉｎｇ）
１６Ｍ＋１６Ａ＋Ｉ ｗｉｔｈ １１ｖａｒ．
入力（Ｉｎｐｕｔ）：
Ｄ１＝（ｕ１，ｖ１）ｗｉｔｈ
ｕ１＝ｘ２＋ｕ１１ｘ＋ｕ１０；
ｖ１＝ｖ１１ｘ＋ｖ１０；
ｈ（ｘ）＝ｘ２＋ｈ１ｘ＋ｈ０；
ｆ（ｘ）＝ｘ５＋ｆ３ｘ３＋ｆ１ｘ＋ｆ０；
出力（Ｏｕｔｐｕｔ）：
Ｄ３＝（ｕ３，ｖ３）＝２Ｄ１ｗｉｔｈ
ｕ３＝ｘ２＋ｕ３１ｘ＋ｕ３０；
ｖ３＝ｖ３１ｘ＋ｖ３０；
【００８１】
上記２倍算処理の具体的な演算処理として、本発明においては下記に示す演算処理を順次実行する。下記演算処理において、Ｒｉｊは中間変数であり、必要に応じてレジスタに格納される。すなわち、中間変数を示す。Ｒｉｊ←Ａは、値Ａ、または演算Ａの結果を中間変数として必要に応じてレジスタＲｉｊに格納する。ｕｘｘ←Ｒｙｙあるいは、ｖｘｘ←Ｒｙｙは、中間変数Ｒｙｙの値をｕｘｘまたはｖｘｘに代入することを意味する。
【００８２】
Ｒ００←ｕ１０
Ｒ０１←ｕ１１
Ｒ０２←ｈ１＋Ｒ０１／／Ｒ０３←ｈ０＋Ｒ００
Ｒ０４←ｈ１×Ｒ０２／／Ｒ０５←Ｒ０１×Ｒ０２
Ｒ０５←Ｒ０５＋Ｒ０３／／Ｒ０４←Ｒ０３＋Ｒ０４
Ｒ０３←ｈ０×Ｒ０５／／Ｒ０４←Ｒ０４×Ｒ００
Ｒ０３←Ｒ０３＋Ｒ０４
Ｒ０４←ｖ１０
Ｒ０６←ｖ１１
Ｒ０７←ｆ３＋Ｒ０６／／Ｒ０８←Ｒ０６＋ｈ１
Ｒ０９←Ｒ０１×Ｒ０１／／Ｒ０８←Ｒ０８×Ｒ０６
Ｒ１０←Ｒ０７＋Ｒ０９／／Ｒ０４←Ｒ０８＋Ｒ０４
Ｒ０８←Ｒ０２×Ｒ０４／／Ｒ０７←Ｒ０５×Ｒ１０
Ｒ０９←Ｒ０５×Ｒ０１／／Ｒ０６←Ｒ０２×Ｒ００
Ｒ０８←Ｒ０８＋Ｒ０７／／Ｒ０９←Ｒ０９＋Ｒ０６
Ｒ０９←Ｒ０９×Ｒ１０／／Ｒ０７←Ｒ０５×Ｒ０４
Ｒ０６←Ｒ０７＋Ｒ０９
Ｒ０４←Ｒ０３×Ｒ０８
Ｒ０５←１／Ｒ０４
Ｒ０７←Ｒ０３×Ｒ０５／／Ｒ０９←Ｒ０５×Ｒ０８
Ｒ０４←Ｒ０３×Ｒ０７／／Ｒ１０←Ｒ０９×Ｒ０８
Ｒ０９←Ｒ０９×Ｒ０６
Ｒ０５←Ｒ０４＋１／／Ｒ０７←Ｒ０９＋１
Ｒ０５←Ｒ０４×Ｒ０５／／Ｒ０７←Ｒ０９×Ｒ０７
Ｒ０７←Ｒ０７×Ｒ０４
Ｒ０７←Ｒ０７＋Ｒ０２
Ｒ０７←Ｒ０７×Ｒ０４
Ｒ０４←Ｒ０１＋Ｒ０５／／Ｒ０６←Ｒ００＋Ｒ０７
Ｒ０２←Ｒ０９＋Ｒ１０／／Ｒ０３←Ｒ０４＋Ｒ０６
Ｒ０８←Ｒ１０×Ｒ０４／／Ｒ０６←Ｒ０９×Ｒ０６
Ｒ０９←Ｒ０２×Ｒ０３
Ｒ１０←Ｒ０８＋Ｒ０６／／Ｒ０８←Ｒ０８＋１
Ｒ０３←Ｒ０８×Ｒ０５／／Ｒ０８←Ｒ０８×Ｒ０７
Ｒ０２←Ｒ０９＋Ｒ１０
Ｒ０９←Ｒ０２＋Ｒ０３／／Ｒ１０←Ｒ０８＋Ｒ０６
Ｒ００←ｖ１０
Ｒ０１←ｖ１１
Ｒ０３←ｈ１＋Ｒ０１／／Ｒ０８←ｈ０＋Ｒ００
Ｒ０１←Ｒ０９＋Ｒ０３／／Ｒ００←Ｒ１０＋Ｒ０８
ｕ２１←Ｒ０５
ｕ２０←Ｒ０７
ｖ２１←Ｒ０１
ｖ２０←Ｒ００
【００８３】
上記演算シーケンスにおいて、
［Ｒ０２←ｈ１＋Ｒ０１／／Ｒ０３←ｈ０＋Ｒ００］
［Ｒ０４←ｈ１×Ｒ０２／／Ｒ０５←Ｒ０１×Ｒ０２］
など、［＊＊＊／／＊＊＊］で示す２つの演算を併記した処理が並列処理可能な演算ステップであり、これらの処理を並列実行することで、全体の演算処理サイクルを減少させ、高速演算処理を実現することができる。
【００８４】
具体的には、加算処理の並列処理、すなわち、上記演算シーケンスにおいて、［Ｒｉｊ←ａ＋ｂ／／Ｒｉｊ←ｃ＋ｄ］の並列実行ステップを１２ステップ設定し、乗算処理の並列処理、すなわち、上記演算シーケンスにおいて、［Ｒｉｊ←ａ×ｂ／／Ｒｉｊ←ｃ×ｄ］の並列実行ステップを１１ステップ設定しているので、すべての演算をシーケンシャルに実行した場合、加算処理数は１２ステップ増加し、乗算処理数は１１ステップ増加することになる。従って、乗算ステップ（Ｍ）、加算ステップ（Ａ）、逆元算出ステップ（Ｉ）の各演算ステップ数の削減が実現される。
【００８５】
具体的には、全ての演算をシーケンシャルに実行すると、
演算量＝２８Ｍ＋２７Ａ＋Ｉとなるが、
上述の並列演算処理を実行する本発明の演算シーケンスに従った処理の場合は、
演算量＝１６Ｍ＋１６Ａ＋Ｉとなり、
大幅な計算サイクル数の削減が達成される。
【００８６】
なお、上記演算シーケンスは、プロセッサのＳＩＭＤ(Single Instruction, Multiple Data)命令を用いて並列処理を行うことが可能なシーケンスに設定されている。ＳＩＭＤ命令とはプロセッサの持つ一つの命令で同じ種類の複数の演算（乗算や加算など）を同時に行う命令であり、近年のＩｎｔｅｌやＳｕｎなどの代表的なプロセッサに実装されている命令セットである。
【００８７】
次に、種数ｇ＝３のＧＦ（２ｎ）上で定義される超楕円曲線の２並列演算のアルゴリズム、すなわち、超楕円、および、因子Ｄ１からＤ３＝２Ｄ１を出力する処理としての２倍算処理の具体的シーケンスについて説明する。
【００８８】
種数ｇ＝３のＧＦ（２ｎ）上で定義される超楕円曲線の加算処理は、以下の演算処理として定義される。加算は因子Ｄ１とＤ２からＤ３＝Ｄ１＋Ｄ２を出力する処理である。
【００８９】
加算（ａｄｄｉｔｉｏｎ）
４４Ｍ＋５８Ａ＋Ｉｗｉｔｈ １６ｖａｒ．
Ｉｎｐｕｔ：
Ｄ１＝（ｕ１，ｖ１）ａｎｄＤ２＝（ｕ２，ｖ２）ｗｉｔｈ
ｕ１＝ｘ３＋ｕ１２ｘ２＋ｕ１１ｘ＋ｕ１０；
ｕ２＝ｘ３＋ｕ２２ｘ２＋ｕ２１ｘ＋ｕ２０；
ｖ１＝ｖ１２ｘ２＋ｖ１１ｘ＋ｖ１０；
ｖ２＝ｖ２２ｘ２＋ｖ２１ｘ＋ｖ２０；
ｈ（ｘ）＝ｘ３＋ｈ２ｘ２＋ｈ１ｘ＋ｈ０；
ｆ（ｘ）＝ｘ７＋ｆ６ｘ６＋ｆ５ｘ５＋ｆ４ｘ４
＋ｆ３ｘ３＋ｆ２ｘ２＋ｆ１ｘ＋ｆ０；
Ｏｕｔｐｕｔ：
Ｄ３＝（ｕ３，ｖ３）＝Ｄ１＋Ｄ２ｗｉｔｈ
ｕ３＝ｘ３＋ｕ３２ｘ２＋ｕ３１ｘ＋ｕ３０；
ｖ３＝ｖ３２ｘ２＋ｖ３１ｘ＋ｖ３０；
【００９０】
上記加算処理の具体的な演算処理として、本発明においては下記に示す演算処理を順次実行する。下記演算処理において、Ｒｉｊは中間変数であり、必要に応じてレジスタに格納される。すなわち、中間変数を示す。Ｒｉｊ←Ａは、値Ａ、または演算Ａの結果を中間変数として必要に応じてレジスタＲｉｊに格納する。ｕｘｘ←Ｒｙｙあるいは、ｖｘｘ←Ｒｙｙは、中間変数Ｒｙｙの値をｕｘｘまたはｖｘｘに代入することを意味する。
【００９１】
Ｒ００←ｕ１２
Ｒ０１←ｕ１１
Ｒ０２←ｕ１０
Ｒ０３←ｕ２２
Ｒ０４←ｕ２１
Ｒ０５←ｕ２０
＊Ｒ０６←Ｒ０４×Ｒ００／／Ｒ０７←Ｒ０４×Ｒ０２
＊Ｒ０８←Ｒ０３×Ｒ０１／／Ｒ０９←Ｒ０３×Ｒ０２
＊Ｒ１０←Ｒ０５×Ｒ０１／／Ｒ１１←Ｒ０５×Ｒ００
Ｒ０５←Ｒ０５＋Ｒ０２／／Ｒ０４←Ｒ０４＋Ｒ０１
＊Ｒ０２←Ｒ０５×Ｒ０５／／Ｒ１２←Ｒ０５×Ｒ０４
Ｒ０４←Ｒ０４×Ｒ０４
Ｒ０３←Ｒ０３＋Ｒ００／／Ｒ１０←Ｒ１０＋Ｒ０７
＊Ｒ１３←Ｒ１０×Ｒ０４／／Ｒ１０←Ｒ１０×Ｒ０３
Ｒ０５←Ｒ０５＋Ｒ０６／／Ｒ１１←Ｒ１１＋Ｒ０９
Ｒ０５←Ｒ０５＋Ｒ０８／／Ｒ０２←Ｒ０２＋Ｒ１０  Ｒ０８←Ｒ０３×Ｒ１１
Ｒ１１←Ｒ０８×Ｒ１１
＊Ｒ０３←Ｒ０５×Ｒ０３／／Ｒ０５←Ｒ０５×Ｒ０２
Ｒ０５←Ｒ０５＋Ｒ１１／／Ｒ０４←Ｒ０４＋Ｒ０３
Ｒ０５←Ｒ０５＋Ｒ１３／／Ｒ０８←Ｒ０８＋Ｒ１２
Ｒ００←ｕ２２
Ｒ０１←ｕ２１
＊Ｒ０３←Ｒ０４×Ｒ０１／／Ｒ０１←Ｒ０４×Ｒ００
Ｒ０１←Ｒ０１＋Ｒ０８／／Ｒ０３←Ｒ０３＋Ｒ０２
Ｒ０８←Ｒ０８×Ｒ００
Ｒ０３←Ｒ０３＋Ｒ０８
Ｒ００←ｖ１２
Ｒ０２←ｖ１１
Ｒ０６←ｖ１０
Ｒ０７←ｖ２２
Ｒ０８←ｖ２１
Ｒ０９←ｖ２０
Ｒ００←Ｒ００＋Ｒ０７／／Ｒ０２←Ｒ０２＋Ｒ０８
Ｒ０６←Ｒ０６＋Ｒ０９／／Ｒ０７←Ｒ０１＋Ｒ０４
Ｒ０８←Ｒ０３＋Ｒ０４／／Ｒ０９←Ｒ０３＋Ｒ０１
Ｒ０１←Ｒ０１×Ｒ０２／／Ｒ０３←Ｒ０３×Ｒ０６
Ｒ０２←Ｒ０２＋Ｒ００／／Ｒ０６←Ｒ０６＋Ｒ００
Ｒ０７←Ｒ０７×Ｒ０２／／Ｒ０８←Ｒ０８×Ｒ０６
Ｒ０２←Ｒ０２＋Ｒ０６／／Ｒ０７←Ｒ０７＋Ｒ０１
Ｒ０２←Ｒ０２×Ｒ０９／／Ｒ００←Ｒ００×Ｒ０４
Ｒ０２←Ｒ０２＋Ｒ０１／／Ｒ０９←Ｒ０１＋Ｒ０８
Ｒ０２←Ｒ０２＋Ｒ０３／／Ｒ０９←Ｒ０９＋Ｒ０３
Ｒ０７←Ｒ０７＋Ｒ００／／Ｒ０９←Ｒ０９＋Ｒ００
Ｒ０４←ｕ２２
Ｒ１０←ｕ２１
Ｒ１１←ｕ２０
＊Ｒ１２←Ｒ００×Ｒ０４／／Ｒ１３←Ｒ００×Ｒ１０
Ｒ１２←Ｒ１２＋Ｒ０７／／Ｒ０９←Ｒ０９＋Ｒ１３
Ｒ１０←Ｒ１０＋Ｒ１１／／Ｒ０２←Ｒ０２＋Ｒ１３
＊Ｒ１３←Ｒ１２×Ｒ１１／／Ｒ０４←Ｒ１２×Ｒ０４
Ｒ０３←Ｒ０３＋Ｒ１３／／Ｒ００←Ｒ００＋Ｒ１２
Ｒ０２←Ｒ０２＋Ｒ１３／／Ｒ０９←Ｒ０９＋Ｒ０４
Ｒ１０←Ｒ１０×Ｒ００
Ｒ０２←Ｒ０２＋Ｒ１０
Ｒ０１←Ｒ０９×Ｒ０５／／Ｒ０６←Ｒ０９×Ｒ０９
Ｒ０１←１／Ｒ０１＊Ｒ０４←Ｒ０１×Ｒ０５／／Ｒ０６←Ｒ０１×Ｒ０６
Ｒ０５←Ｒ０５×Ｒ０４
Ｒ１２←Ｒ０５×Ｒ０５
＊Ｒ００←Ｒ０４×Ｒ０３／／Ｒ０１←Ｒ０４×Ｒ０２
Ｒ０２←ｕ１２
Ｒ０４←ｕ１１
Ｒ１０←ｕ１０
＊Ｒ０８←Ｒ０２×Ｒ００／／Ｒ０９←Ｒ０２×Ｒ０１
Ｒ０２←Ｒ０２＋Ｒ０１／／Ｒ０９←Ｒ０９＋Ｒ０４
＊Ｒ０７←Ｒ０４×Ｒ００／／Ｒ０４←Ｒ０４×Ｒ０１
Ｒ０８←Ｒ０８＋Ｒ０４／／Ｒ０９←Ｒ０９＋Ｒ００
＊Ｒ１１←Ｒ１０×Ｒ００／／Ｒ１３←Ｒ１０×Ｒ０１
Ｒ０７←Ｒ０７＋Ｒ１３／／Ｒ０８←Ｒ０８＋Ｒ１０
Ｒ０４←ｕ２２
Ｒ１４←ｕ２１
Ｒ１０←Ｒ０２＋Ｒ０１／／Ｒ０３←Ｒ１４＋Ｒ０９
Ｒ１０←Ｒ１０＋Ｒ０４／／Ｒ０３←Ｒ０３＋Ｒ００
＊Ｒ１３←Ｒ１０×Ｒ０４／／Ｒ１５←Ｒ１０×Ｒ１４
Ｒ１３←Ｒ１３＋Ｒ０３／／Ｒ１５←Ｒ１５＋Ｒ１２
＊Ｒ０４←Ｒ０１×Ｒ０２／／Ｒ１４←Ｒ０１×Ｒ０９
Ｒ１３←Ｒ１３＋Ｒ０４／／Ｒ１５←Ｒ１５＋Ｒ１４
＊Ｒ０３←Ｒ０１×ｈ２／／Ｒ０４←Ｒ０１×Ｒ０８
Ｒ１３←Ｒ１３＋Ｒ０５／／Ｒ０３←Ｒ０３＋ｈ１
Ｒ０１←Ｒ０１＋ｈ２／／Ｒ０３←Ｒ０３＋Ｒ００
＊Ｒ０１←Ｒ０５×Ｒ０１／／Ｒ０３←Ｒ０５×Ｒ０３
Ｒ１５←Ｒ１５＋Ｒ０１／／Ｒ０４←Ｒ０４＋Ｒ０３
＊Ｒ０１←Ｒ００×Ｒ０２／／Ｒ０３←Ｒ００×Ｒ０９
Ｒ１５←Ｒ１５＋Ｒ０１／／Ｒ０４←Ｒ０４＋Ｒ０３
Ｒ０５←ｕ２２
Ｒ１４←ｕ２１
＊Ｒ０１←Ｒ１３×Ｒ０５／／Ｒ０３←Ｒ１３×Ｒ１４
Ｒ１５←Ｒ１５＋Ｒ０１／／Ｒ０４←Ｒ０４＋Ｒ０３
Ｒ１５←Ｒ１５＋Ｒ０８／／Ｒ０４←Ｒ０４＋Ｒ０７
Ｒ００←ｕ２０
Ｒ０３←Ｒ００×Ｒ１０
Ｒ１５←Ｒ１５＋Ｒ００／／Ｒ０４←Ｒ０４＋Ｒ０３
Ｒ０３←Ｒ０５×Ｒ１５
Ｒ０４←Ｒ０４＋Ｒ０３
Ｒ００←ｕ１２
Ｒ０３←Ｒ００＋ｆ６
Ｒ０３←Ｒ０３×Ｒ１２
Ｒ０４←Ｒ０４＋Ｒ０３
Ｒ００←ｖ１２
Ｒ０１←ｖ１１
Ｒ０３←ｖ１０
Ｒ０２←Ｒ０２＋Ｒ１０
＊Ｒ０５←Ｒ０２×Ｒ０４／／Ｒ１２←Ｒ０２×Ｒ１５
Ｒ０５←Ｒ０５＋Ｒ１１／／Ｒ１２←Ｒ１２＋Ｒ０７
Ｒ１２←Ｒ１２＋Ｒ０４
＊Ｒ０５←Ｒ０６×Ｒ０５／／Ｒ１２←Ｒ０６×Ｒ１２
Ｒ０５←Ｒ０５＋ｈ０／／Ｒ１２←Ｒ１２＋ｈ１
Ｒ０５←Ｒ０５＋Ｒ０３／／Ｒ１２←Ｒ１２＋Ｒ０１
＊Ｒ０１←Ｒ０２×Ｒ１３／／Ｒ０３←Ｒ０２×Ｒ１０
Ｒ０１←Ｒ０１＋Ｒ１５／／Ｒ０３←Ｒ０３＋Ｒ１３
Ｒ０１←Ｒ０１＋Ｒ０８／／Ｒ０３←Ｒ０３＋Ｒ０９
＊Ｒ０１←Ｒ０６×Ｒ０１／／Ｒ０３←Ｒ０６×Ｒ０３
Ｒ０１←Ｒ０１＋ｈ２／／Ｒ０３←Ｒ０３＋１
Ｒ０１←Ｒ０１＋Ｒ００
＊Ｒ００←Ｒ０３×Ｒ００／／Ｒ０２←Ｒ０３×ｈ１
Ｒ０６←Ｒ００＋ｆ６／／Ｒ０７←Ｒ１５＋Ｒ０２
＊Ｒ００←ｈ２×Ｒ０３／／Ｒ０２←ｈ２×Ｒ０１
Ｒ０８←Ｒ１３＋Ｒ００／／Ｒ０７←Ｒ０７＋Ｒ０２
Ｒ０６←Ｒ０６＋Ｒ１０／／Ｒ０８←Ｒ０８＋ｆ５
Ｒ０６←Ｒ０６＋Ｒ０３／／Ｒ０８←Ｒ０８＋Ｒ０１
＊Ｒ００←Ｒ０６×Ｒ１０／／Ｒ０２←Ｒ０６×Ｒ１３
Ｒ０８←Ｒ０８＋Ｒ００／／Ｒ０７←Ｒ０７＋Ｒ０２
Ｒ００←Ｒ０１×Ｒ０１
Ｒ００←Ｒ００＋ｆ４／／Ｒ０７←Ｒ０７＋Ｒ１２
Ｒ０７←Ｒ０７＋Ｒ００／／Ｒ０３←Ｒ０３＋１
＊Ｒ００←Ｒ０８×Ｒ１０／／Ｒ０２←Ｒ０８×Ｒ０３
Ｒ０７←Ｒ０７＋Ｒ００／／Ｒ１２←Ｒ１２＋Ｒ０２
＊Ｒ００←Ｒ０３×Ｒ０６／／Ｒ０２←Ｒ０３×Ｒ０７
Ｒ０１←Ｒ０１＋Ｒ００／／Ｒ０５←Ｒ０５＋Ｒ０２
Ｒ０１←Ｒ０１＋ｈ２／／Ｒ１２←Ｒ１２＋ｈ１
Ｒ０５←Ｒ０５＋ｈ０
ｕ３２←Ｒ０６
ｕ３１←Ｒ０８
ｕ３０←Ｒ０７
ｖ３２←Ｒ０１
ｖ３１←Ｒ１２
ｖ３０←Ｒ０５
【００９２】
上記演算シーケンスにおいて、
［Ｒ０５←Ｒ０５＋Ｒ０２／／Ｒ０４←Ｒ０４＋Ｒ０１］など、［＊＊＊／／＊＊＊］で示す２つの演算を併記した処理が並列処理可能な演算ステップであり、これらの処理を並列実行することで、全体の演算処理サイクルを減少させ、高速演算処理を実現することができる。
【００９３】
すなわち、上記演算シーケンスにおいて、［Ｒｉｊ←ａ＋ｂ／／Ｒｉｊ←ｃ＋ｄ］の並列加算処理実行ステップ、および［Ｒｉｊ←ａ×ｂ／Ｒｉｊ←ｃ×ｄ］の並列乗算処理実行ステップを設定しているので、すべての演算をシーケンシャルに実行した場合に比較して大幅な演算サイクル数の低減が可能となる。
【００９４】
具体的には、乗算ステップ（Ｍ）、加算ステップ（Ａ）、逆元算出ステップ（Ｉ）の各演算ステップをシーケンシャルに実行する場合は、
演算量＝７７Ｍ＋１０２Ａ＋Ｉとなるが、
上述の並列演算処理を実行する本発明の演算シーケンスに従った処理の場合は、
演算量＝４４Ｍ＋５８Ａ＋Ｉとなり、
大幅な計算サイクル数の削減が達成される。
【００９５】
なお、上記演算シーケンスは、プロセッサのＳＩＭＤ(Single Instruction, Multiple Data)命令を用いて並列処理を行うことが可能なシーケンスに設定されている。ＳＩＭＤ命令とはプロセッサの持つ一つの命令で同じ種類の複数の演算（乗算や加算など）を同時に行う命令であり、近年のＩｎｔｅｌやＳｕｎなどの代表的なプロセッサに実装されている命令セットである。
【００９６】
本アルゴリズムをソフトウェアプログラムによって実行する場合、特に定義体がＧＦ（２ｎ）かつ種数ｇ＝３の場合、１２８ｂｉｔ（６４ｂｉｔ×２）のＳＩＭＤ(Single Instruction, Multiple Data)命令を使うことにより、有限体の２つの乗算を同時に一度の処理サイクルにおいて行うことができ、ソフトウェアの高速化技術として利用することができる。並列乗算は一つの有限体の元を共通としてＡ＊Ｂ、Ａ＊Ｃを同時に行う方法である。この乗算は、前述した演算処理シーケンス中、（＊）を付した部分で利用できる。
【００９７】
同様に、種数ｇ＝３のＧＦ（２ｎ）上で定義される超楕円曲線の２倍算処理は、以下の演算処理として定義される。２倍算は因子Ｄ１からＤ３＝２Ｄ１を出力する処理として実行される。
【００９８】
２倍算（ｄｏｕｂｌｉｎｇ）
４３Ｍ＋５５Ａ＋Ｉｗｉｔｈ １６ｖａｒ．
Ｉｎｐｕｔ：
Ｄ１＝（ｕ１，ｖ１）ｗｉｔｈ
ｕ１＝ｘ３＋ｕ１２ｘ２＋ｕ１１ｘ＋ｕ１０；
ｖ１＝ｖ１２ｘ２＋ｖ１１ｘ＋ｖ１０；
ｈ（ｘ）＝ｘ３＋ｈ２ｘ２＋ｈ１ｘ＋ｈ０；
ｆ（ｘ）＝ｘ７＋ｆ６ｘ６＋ｆ５ｘ５＋ｆ４ｘ４
＋ｆ３ｘ３＋ｆ２ｘ２＋ｆ１ｘ＋ｆ０；
Ｏｕｔｐｕｔ：
Ｄ３＝（ｕ３，ｖ３）＝２Ｄ１ｗｉｔｈ
ｕ３＝ｘ３＋ｕ３２ｘ２＋ｕ３１ｘ＋ｕ３０；
ｖ３＝ｖ３２ｘ２＋ｖ３１ｘ＋ｖ３０；
【００９９】
上記２倍算処理の具体的な演算処理として、本発明においては下記に示す演算処理を順次実行する。下記演算処理において、Ｒｉｊは中間変数であり、必要に応じてレジスタに格納される。すなわち、中間変数を示す。Ｒｉｊ←Ａは、値Ａ、または演算Ａの結果を中間変数として必要に応じてレジスタＲｉｊに格納する。ｕｘｘ←Ｒｙｙあるいは、ｖｘｘ←Ｒｙｙは、中間変数Ｒｙｙの値をｕｘｘまたはｖｘｘに代入することを意味する。
【０１００】
Ｒ００←ｕ１２
Ｒ０１←ｕ１１
Ｒ０２←ｕ１０
＊Ｒ０６←ｈ１×Ｒ００／／Ｒ０７←ｈ１×Ｒ０２
＊Ｒ０８←ｈ２×Ｒ０１／／Ｒ０９←ｈ２×Ｒ０２
＊Ｒ１０←ｈ０×Ｒ０１／／Ｒ１１←ｈ０×Ｒ００
Ｒ０５←Ｒ０２＋ｈ０／／Ｒ０４←Ｒ０１＋ｈ１
＊Ｒ０２←Ｒ０５×Ｒ０５／／Ｒ１２←Ｒ０５×Ｒ０４
Ｒ０４←Ｒ０４×Ｒ０４
Ｒ０３←Ｒ００＋ｈ２／／Ｒ１０←Ｒ１０＋Ｒ０７
＊Ｒ１３←Ｒ１０×Ｒ０４／／Ｒ１０←Ｒ１０×Ｒ０３
Ｒ０５←Ｒ０５＋Ｒ０６／／Ｒ１１←Ｒ１１＋Ｒ０９
Ｒ０５←Ｒ０５＋Ｒ０８／／Ｒ０２←Ｒ０２＋Ｒ１０
Ｒ０８←Ｒ０３×Ｒ１１
Ｒ１１←Ｒ０８×Ｒ１１
＊Ｒ０３←Ｒ０５×Ｒ０３／／Ｒ０５←Ｒ０５×Ｒ０２
Ｒ０５←Ｒ０５＋Ｒ１１／／Ｒ０４←Ｒ０４＋Ｒ０３
Ｒ０５←Ｒ０５＋Ｒ１３／／Ｒ０８←Ｒ０８＋Ｒ１２
＊Ｒ０３←Ｒ０４×Ｒ０１／／Ｒ０１←Ｒ０４×Ｒ００
Ｒ０１←Ｒ０１＋Ｒ０８／／Ｒ０３←Ｒ０３＋Ｒ０２
Ｒ０８←Ｒ０８×Ｒ００
Ｒ０３←Ｒ０３＋Ｒ０８
Ｒ００←ｕ１２
Ｒ０２←ｕ１１
Ｒ０６←ｕ１０
Ｒ０７←ｖ１２
Ｒ０８←ｖ１１
Ｒ０９←ｖ１０
＊Ｒ１０←Ｒ０７×Ｒ０７／／Ｒ１１←Ｒ０７×ｈ１
Ｒ１２←Ｒ００＋ｆ６／／Ｒ１３←Ｒ０７＋ｆ５
＊Ｒ１４←Ｒ１２×Ｒ０２／／Ｒ１５←Ｒ１２×Ｒ００
Ｒ１３←Ｒ１３＋Ｒ１５／／Ｒ１５←Ｒ１０＋ｆ４
Ｒ１３←Ｒ１３＋Ｒ０２／／Ｒ１５←Ｒ１５＋Ｒ０８
＊Ｒ０８←ｈ２×Ｒ０８／／Ｒ１０←ｈ２×Ｒ０７
Ｒ１４←Ｒ１４＋Ｒ０６／／Ｒ０８←Ｒ０８＋Ｒ０９
Ｒ１５←Ｒ１５＋Ｒ１４／／Ｒ０７←Ｒ０７＋ｆ５
Ｒ０９←Ｒ１３×Ｒ００／／Ｒ１３←Ｒ１３×Ｒ０２
Ｒ１５←Ｒ１５＋Ｒ１０
Ｒ１５←Ｒ１５＋Ｒ０９／／Ｒ０８←Ｒ０８＋Ｒ１３
Ｒ１４←Ｒ１４＋Ｒ１５／／Ｒ０８←Ｒ０８＋ｆ３
Ｒ１２←Ｒ１２×Ｒ０６／／Ｒ１５←Ｒ１５×Ｒ００
＊Ｒ０２←Ｒ００×Ｒ０２／／Ｒ００←Ｒ００×Ｒ００
Ｒ０８←Ｒ０８＋Ｒ１２／／Ｒ１１←Ｒ１１＋Ｒ１５
Ｒ０７←Ｒ０７＋Ｒ００／／Ｒ１４←Ｒ１４＋Ｒ０２
Ｒ０８←Ｒ０８＋Ｒ１１
Ｒ００←ｕ１２
Ｒ０２←ｕ１１
Ｒ０６←ｕ１０
Ｒ０９←Ｒ０１＋Ｒ０４／／Ｒ１０←Ｒ１４＋Ｒ０７
Ｒ０９←Ｒ０９×Ｒ１０／／Ｒ１４←Ｒ１４×Ｒ０１
Ｒ１１←Ｒ０３＋Ｒ０４／／Ｒ１２←Ｒ０８＋Ｒ０７
Ｒ１１←Ｒ１１×Ｒ１２／／Ｒ０８←Ｒ０８×Ｒ０３
Ｒ１３←Ｒ０３＋Ｒ０１／／Ｒ１０←Ｒ１０＋Ｒ１２
Ｒ１３←Ｒ１３×Ｒ１０／／Ｒ０７←Ｒ０７×Ｒ０４
Ｒ１３←Ｒ１３＋Ｒ１４／／Ｒ０９←Ｒ０９＋Ｒ１４
Ｒ１１←Ｒ１１＋Ｒ１４／／Ｒ１２←Ｒ０８＋Ｒ０７
Ｒ１３←Ｒ１３＋Ｒ０８／／Ｒ０９←Ｒ０９＋Ｒ０７
＊Ｒ０１←Ｒ０７×Ｒ００／／Ｒ０３←Ｒ０７×Ｒ０２
Ｒ０１←Ｒ０１＋Ｒ０９／／Ｒ１３←Ｒ１３＋Ｒ０３
Ｒ０７←Ｒ０７＋Ｒ０１／／Ｒ０２←Ｒ０２＋Ｒ０６
＊Ｒ０６←Ｒ０１×Ｒ０６／／Ｒ００←Ｒ０１×Ｒ００
Ｒ０８←Ｒ０８＋Ｒ０６／／Ｒ００←Ｒ００＋Ｒ０３
Ｒ０２←Ｒ０２×Ｒ０７
Ｒ１１←Ｒ１１＋Ｒ１２／／Ｒ１３←Ｒ１３＋Ｒ０２
Ｒ１３←Ｒ１３＋Ｒ０６／／Ｒ１１←Ｒ１１＋Ｒ００
＊Ｒ０１←Ｒ１１×Ｒ０５／／Ｒ０６←Ｒ１１×Ｒ１１
Ｒ０１←１／Ｒ０１
＊Ｒ０３←Ｒ０１×Ｒ０５／／Ｒ０６←Ｒ０１×Ｒ０６
Ｒ０５←Ｒ０５×Ｒ０３
＊Ｒ００←Ｒ０３×Ｒ０８／／Ｒ０１←Ｒ０３×Ｒ１３
Ｒ０２←ｕ１２
Ｒ０４←ｕ１１
Ｒ１０←ｕ１０
＊Ｒ０８←Ｒ０２×Ｒ００／／Ｒ０９←Ｒ０２×Ｒ０１
Ｒ０２←Ｒ０２＋Ｒ０１／／Ｒ０９←Ｒ０９＋Ｒ０４
＊Ｒ０７←Ｒ０４×Ｒ００／／Ｒ０４←Ｒ０４×Ｒ０１
Ｒ０８←Ｒ０８＋Ｒ０４／／Ｒ０９←Ｒ０９＋Ｒ００
＊Ｒ１１←Ｒ１０×Ｒ００／／Ｒ１２←Ｒ１０×Ｒ０１
Ｒ０７←Ｒ０７＋Ｒ１２／／Ｒ０８←Ｒ０８＋Ｒ１０
Ｒ０４←ｕ１２
Ｒ１４←ｕ１１
Ｒ１０←Ｒ０４＋ｈ２／／Ｒ１２←Ｒ００＋ｈ１
Ｒ１０←Ｒ１０＋Ｒ０１／／Ｒ１２←Ｒ１２＋Ｒ１４
＊Ｒ０４←Ｒ１０×Ｒ０４／／Ｒ１０←Ｒ１０×Ｒ０５
＊Ｒ１３←Ｒ０１×ｈ２／／Ｒ０１←Ｒ０１×Ｒ０１
Ｒ１２←Ｒ１２＋Ｒ０４／／Ｒ０１←Ｒ０１＋Ｒ０５
Ｒ１２←Ｒ１２＋Ｒ１３
＊Ｒ１２←Ｒ０５×Ｒ１２／／Ｒ０５←Ｒ０５×Ｒ０５
Ｒ０３←Ｒ０５×ｆ６／／Ｒ００←Ｒ００×Ｒ００
Ｒ１０←Ｒ１０＋Ｒ０５／／Ｒ０３←Ｒ０３＋Ｒ００
Ｒ１２←Ｒ１２＋Ｒ０３
Ｒ０３←ｖ１２
Ｒ０４←ｖ１１
Ｒ０５←ｖ１０
Ｒ０９←Ｒ０９＋Ｒ０１／／Ｒ０８←Ｒ０８＋Ｒ１０
＊Ｒ００←Ｒ０２×Ｒ０１／／Ｒ１３←Ｒ０２×Ｒ１０
Ｒ１４←Ｒ０２×Ｒ１２
Ｒ１２←Ｒ１２＋Ｒ０７／／Ｒ１４←Ｒ１４＋Ｒ１１
Ｒ００←Ｒ００＋Ｒ０８／／Ｒ１３←Ｒ１３＋Ｒ１２
＊Ｒ００←Ｒ０６×Ｒ００／／Ｒ１３←Ｒ０６×Ｒ１３
＊Ｒ１４←Ｒ０６×Ｒ１４／／Ｒ１５←Ｒ０６×Ｒ０９
Ｒ１５←Ｒ１５＋１／／Ｒ００←Ｒ００＋ｈ２
Ｒ１３←Ｒ１３＋ｈ１／／Ｒ１４←Ｒ１４＋ｈ０
Ｒ００←Ｒ００＋Ｒ０３／／Ｒ１３←Ｒ１３＋Ｒ０４
Ｒ１４←Ｒ１４＋Ｒ０５／／Ｒ０４←Ｒ１５＋ｆ６
＊Ｒ０２←Ｒ１５×Ｒ１５／／Ｒ０３←Ｒ１５×ｈ１
Ｒ０３←Ｒ０３＋Ｒ１０／／Ｒ０２←Ｒ０２＋Ｒ０４
＊Ｒ０４←Ｒ００×Ｒ００／／Ｒ０５←Ｒ００×ｈ２
Ｒ０３←Ｒ０３＋Ｒ０４／／Ｒ０６←Ｒ０１＋ｆ５
Ｒ０３←Ｒ０３＋ｆ４／／Ｒ０５←Ｒ０５＋Ｒ１３
Ｒ０７←Ｒ１５×ｈ２
Ｒ０６←Ｒ０６＋Ｒ０７／／Ｒ０３←Ｒ０３＋Ｒ０５
Ｒ１５←Ｒ１５＋１／／Ｒ０６←Ｒ０６＋Ｒ００
＊Ｒ０１←Ｒ０２×Ｒ０１／／Ｒ０４←Ｒ０２×Ｒ１５
Ｒ０３←Ｒ０３＋Ｒ０１／／Ｒ０４←Ｒ０４＋Ｒ００
＊Ｒ０５←Ｒ１５×Ｒ０６／／Ｒ０７←Ｒ１５×Ｒ０３
Ｒ０５←Ｒ０５＋Ｒ１３／／Ｒ０７←Ｒ０７＋Ｒ１４
Ｒ０４←Ｒ０４＋ｈ２／／Ｒ０５←Ｒ０５＋ｈ１
Ｒ０７←Ｒ０７＋ｈ０
ｕ３２←Ｒ０２
ｕ３１←Ｒ０６
ｕ３０←Ｒ０３
ｖ３２←Ｒ０４
ｖ３１←Ｒ０５
ｖ３０←Ｒ０７
【０１０１】
上記演算シーケンスにおいて、［＊＊＊／／＊＊＊］で示す２つの演算を併記した処理が並列処理可能な演算ステップであり、これらの処理を並列実行することで、全体の演算処理サイクルを減少させ、高速演算処理を実現することができる。
【０１０２】
すなわち、上記演算シーケンスにおいて、［Ｒｉｊ←ａ＋ｂ／／Ｒｉｊ←ｃ＋ｄ］の並列加算処理実行ステップ、および［Ｒｉｊ←ａ×ｂ／Ｒｉｊ←ｃ×ｄ］の並列乗算処理実行ステップを設定しているので、すべての演算をシーケンシャルに実行した場合に比較して大幅な演算サイクル数の低減が可能となる。
【０１０３】
具体的には、乗算ステップ（Ｍ）、加算ステップ（Ａ）、逆元算出ステップ（Ｉ）の各演算ステップをシーケンシャルに実行する場合は、
演算量＝７８Ｍ＋１０４Ａ＋Ｉとなるが、
上述の並列演算処理を実行する本発明の演算シーケンスに従った処理の場合は、
演算量＝４３Ｍ＋５５Ａ＋Ｉとなり、
大幅な計算サイクル数の削減が達成される。
【０１０４】
なお、上記演算シーケンスは、プロセッサのＳＩＭＤ(Single Instruction, Multiple Data)命令を用いて並列処理を行うことが可能なシーケンスに設定されている。ＳＩＭＤ命令とはプロセッサの持つ一つの命令で同じ種類の複数の演算（乗算や加算など）を同時に行う命令であり、近年のＩｎｔｅｌやＳｕｎなどの代表的なプロセッサに実装されている命令セットである。
【０１０５】
本アルゴリズムをソフトウェアプログラムによって実行する場合、特に定義体がＧＦ（２ｎ）かつ種数ｇ＝３の場合、１２８ｂｉｔ（６４ｂｉｔ×２）のＳＩＭＤ(Single Instruction, Multiple Data)命令を使うことにより、有限体の２つの乗算を同時に一度の処理サイクルにおいて行うことができ、ソフトウェアの高速化技術として利用することができる。並列乗算は一つの有限体の元を共通としてＡ＊Ｂ、Ａ＊Ｃを同時に行う方法である。この乗算は、前述した演算処理シーケンス中、（＊）を付した部分で利用できる。
【０１０６】
このように、本発明では、超楕円曲線暗号処理の演算において実行される加算、２倍算の演算において、並列演算処理を含むシーケンスを設定して演算処理を実行する構成としたので効率的な演算の実行が可能となり、高速処理が実現される。
【０１０７】
上述した例では、超楕円曲線暗号処理の演算において実行される加算、２倍算の演算において、２つの演算ステップを並列に実行する例を示したが、相互に影響を及ぼさない３つ以上の演算ステップを並列に実行することにより、さらに全体の演算サイクル数を削減することが可能である。
【０１０８】
３つの演算ステップを並列化処理する例として、種数ｇ＝２のＧＦ（２ｎ）上で定義される超楕円曲線の並列演算アルゴリズムについて説明する。以下、種数ｇ＝２のＧＦ（２ｎ）上で定義される超楕円曲線の加算処理において、３並列演算を設定した演算処理シーケンスを示す。加算処理は、以下の演算処理として定義される。加算は因子Ｄ１とＤ２からＤ３＝Ｄ１＋Ｄ２を出力する処理である。
【０１０９】
加算（ａｄｄｉｔｉｏｎ）
１３Ｍ＋２０Ａ＋Ｉ ｗｉｔｈ １１ ｖａｒ．
入力（Ｉｎｐｕｔ）：
Ｄ１＝（ｕ１，ｖ１）ａｎｄ Ｄ２＝（ｕ２，ｖ２）ｗｉｔｈ
ｕ１＝ｘ２＋ｕ１１ｘ＋ｕ１０；
ｕ２＝ｘ２＋ｕ２１ｘ＋ｕ２０；
ｖ１＝ｖ１１ｘ＋ｖ１０；
ｖ２＝ｖ２１ｘ＋ｖ２０；
ｈ（ｘ）＝ｘ２＋ｈ１ｘ＋ｈ０；
ｆ（ｘ）＝ｘ５＋ｆ３ｘ３＋ｆ１ｘ＋ｆ０；
出力（Ｏｕｔｐｕｔ）：
Ｄ３＝（ｕ３，ｖ３）＝Ｄ１＋Ｄ２ ｗｉｔｈ
ｕ３＝ｘ２＋ｕ３１ｘ＋ｕ３０；
ｖ３＝ｖ３１ｘ＋ｖ３０；
【０１１０】
上記記述において、
１３Ｍ＋２０Ａ＋Ｉ ｗｉｔｈ １１ ｖａｒ．
は、１３回の乗算処理（Ｍｕｌｔｉｐｌｅ）、２０回の加算処理（Ａｄｄｉｔｉｏｎ）、１回の逆元算出（Ｉｎｖｅｒｓｉｏｎ）を１１個の変数（Ｖａｒｉａｂｌｅ）を用いて実行することを意味する。すなわち、１３Ｍ＋２０Ａ＋Ｉは加算処理を実行する際に必要となる計算量であり、３並列演算を実行することにより、前術の２並列演算における加算処理における計算量＝１５Ｍ＋２１Ａ＋Ｉより、さらに計算量が削減される。
【０１１１】
３並列演算を含む演算処理シーケンスを以下に示す。
【０１１２】
Ｒ００←ｕ１０
Ｒ０１←ｕ２０
Ｒ０２←ｕ１１
Ｒ０３←ｕ２１
Ｒ０４←Ｒ０２＋Ｒ０３／／Ｒ０５←Ｒ００＋Ｒ０１
Ｒ００←Ｒ０３×Ｒ０４／／Ｒ０２←Ｒ０４×Ｒ０４
Ｒ０６←Ｒ０５＋Ｒ００
Ｒ０７←Ｒ０６×Ｒ０５／／Ｒ００←Ｒ０２×Ｒ０１
Ｒ０８←Ｒ００＋Ｒ０７
Ｒ００←ｖ１０
Ｒ０２←ｖ２０
Ｒ０５←ｖ１１
Ｒ０７←ｖ２１
Ｒ０５←Ｒ０５＋Ｒ０７／／Ｒ００←Ｒ００＋Ｒ０２
Ｒ０２←Ｒ０５＋Ｒ００／／Ｒ１０←Ｒ０４＋Ｒ０６
Ｒ０７←Ｒ０５×Ｒ０４／／Ｒ０９←Ｒ００×Ｒ０６／／Ｒ０５←Ｒ０２×Ｒ１０
Ｒ００←Ｒ０９＋Ｒ０７
Ｒ００←Ｒ０５＋Ｒ００
Ｒ１０←Ｒ０７×Ｒ０３／／Ｒ０２←Ｒ０７×Ｒ０１
Ｒ００←Ｒ００＋Ｒ１０／／Ｒ０９←Ｒ０９＋Ｒ０２
Ｒ０２←Ｒ００×Ｒ０８
Ｒ０２←１／Ｒ０２
Ｒ０５←Ｒ０２×Ｒ０８／／Ｒ０７←Ｒ０２×Ｒ００
Ｒ０２←Ｒ０７×Ｒ００／／Ｒ１０←Ｒ０７×Ｒ０９／／Ｒ０６←Ｒ０５×Ｒ０８
Ｒ０９←ｕ１０
Ｒ００←Ｒ０６＋１
Ｒ０５←Ｒ１０×Ｒ１０／／Ｒ００←Ｒ０６×Ｒ００
Ｒ０７←Ｒ０５＋Ｒ１０／／Ｒ０８←Ｒ００＋Ｒ０４
Ｒ０５←Ｒ０７＋Ｒ０４／／Ｒ００←ｈ１＋Ｒ０３
Ｒ０７←Ｒ０５×Ｒ０６／／Ｒ０３←Ｒ０４×Ｒ０３
Ｒ００←Ｒ０７＋Ｒ００
Ｒ０５←Ｒ００×Ｒ０６
Ｒ００←Ｒ０３＋Ｒ０５／／Ｒ０７←Ｒ０１＋Ｒ０９
Ｒ０６←Ｒ００＋Ｒ０７
Ｒ０１←ｕ１１
Ｒ００←Ｒ０１＋Ｒ０８／／Ｒ０３←Ｒ０９＋Ｒ０６
Ｒ０５←Ｒ０２×Ｒ００／／Ｒ０７←Ｒ１０×Ｒ０３
Ｒ０１←Ｒ０５＋Ｒ０７／／Ｒ０４←Ｒ００＋Ｒ０３／／Ｒ０２←Ｒ０２＋Ｒ１０
Ｒ０２←Ｒ０４×Ｒ０２
Ｒ０２←Ｒ０１＋Ｒ０２／／Ｒ０５←Ｒ０５＋１
Ｒ０１←Ｒ０６×Ｒ０５／／Ｒ０４←Ｒ０８×Ｒ０５
Ｒ００←Ｒ０４＋Ｒ０２／／Ｒ０３←Ｒ０１＋Ｒ０７
Ｒ０５←ｖ１１
Ｒ０７←ｖ１０
Ｒ０４←Ｒ０５＋ｈ１／／Ｒ０１←Ｒ０７＋ｈ０
Ｒ０２←Ｒ００＋Ｒ０４／／Ｒ０１←Ｒ０１＋Ｒ０３
ｕ３１←Ｒ０８
ｕ３０←Ｒ０６
ｖ３１←Ｒ０２
ｖ３０←Ｒ０１
【０１１３】
上記演算シーケンスにおいて、［＊＊＊／／＊＊＊／／＊＊＊］で示す３つの演算を併記した処理が３並列演算処理ステップであり、これらの処理を並列実行することで、全体の演算処理サイクルを減少させ、高速演算処理を実現することができる。
【０１１４】
具体的には、乗算ステップ（Ｍ）、加算ステップ（Ａ）、逆元算出ステップ（Ｉ）の各演算ステップをシーケンシャルに実行する場合は、
演算量＝２５Ｍ＋３４Ａ＋Ｉとなるが、
上述の並列演算処理を実行する本発明の演算シーケンスに従った処理の場合は、
演算量＝１３Ｍ＋２０Ａ＋Ｉとなり、
大幅な計算サイクル数の削減が達成される。
【０１１５】
なお、上記演算シーケンスは、プロセッサのＳＩＭＤ(Single Instruction, Multiple Data)命令を用いて並列処理を行うことが可能なシーケンスに設定されている。ＳＩＭＤ命令とはプロセッサの持つ一つの命令で同じ種類の複数の演算（乗算や加算など）を同時に行う命令であり、近年のＩｎｔｅｌやＳｕｎなどの代表的なプロセッサに実装されている命令セットである。
【０１１６】
このように、超楕円暗号処理におけるスカラー倍算において実行される超楕円加算演算処理、超楕円２倍算演算処理において、並列演算ステップを設定して演算処理を実行することにより、従来のシーケンシャルな演算を実行した場合に比較して、大幅な演算サイクル数の削減、例えば種数２、３ともに計算コストのかかる乗算に対して４０％程度計算量の削減が実現できる。
【０１１７】
（２）並列処理を行うためのハードウェアによる実装
次に、上述した演算処理を実行するハードウェア構成例について、図３を参照して説明する。
【０１１８】
乗算器，加算器１０１−１〜１０１−ｎは、並列処理可能な乗算器および加算器である。例えば前述した２並列演算を実行する場合は、ｎ＝２として、並列処理可能な２つの乗算器と２つの加算器を備えればよい。また、前述した３並列演算を実行する場合は、ｎ＝３として、並列処理可能な３つの乗算器と３つの加算器を備えればよい。すなわち、設定した演算シーケンスに含まれる並列演算数に従ってｎを設定する。
【０１１９】
各乗算器，加算器１０１−１〜１０１−ｎによる演算結果は、セレクタ１０２を介してデータ記憶部（レジスタ）１０３に格納される。データ記憶部（レジスタ）１０３には、前述の演算シーケンス中において発生する中間値Ｒｉｊ等が格納され、さらに、必要な値がレジスタから取り出されセレクタ１０４を介して、各乗算器，加算器１０１−１〜１０１−ｎに供給される。
【０１２０】
制御部１０５は、各乗算器，加算器１０１−１〜１０１−ｎ、セレクタ１０２、セレクタ１０４の処理制御を実行する。
【０１２１】
図３に示す演算装置によって、前述した２並列演算あるいは３並列演算、あるいはｎ並列演算を含む超楕円暗号処理におけるスカラー倍算において実行される加算処理、２倍算処理が実行されることになる。
【０１２２】
このように、既存の超楕円曲線の演算装置のうち、１個であった乗算器と加算器をそれぞれ複数配置し、これらを並列に動作させることで、高速な超楕円曲線暗号処理演算が実現される。
【０１２３】
（３）ソフトウェアによる並列演算処理
本アルゴリズムをソフトウェアプログラムによって実行する場合、暗号処理演算シーケンスを記述したプログラムを設定し、該プログラムに従ったデータ処理を実行するデータ処理部としてのＣＰＵ等の制御による演算として実行することができる。
【０１２４】
超楕円曲線暗号に基づく暗号処理演算を実行するデータ処理部は、暗号処理演算における演算データのデータ記憶部としてのレジスタに演算データ、中間値を記憶し、レジスタ格納値を適用した並列演算処理を実行する。特に定義体がＧＦ（２ｎ）かつ種数ｇ＝３の場合には、既存の１２８ｂｉｔ（６４ｂｉｔ×２）のＳＩＭＤ(Single Instruction, Multiple Data)命令を使うことにより、有限体の２つの乗算を同時に一度の処理サイクルにおいて行うことができ、上述した演算シーケンスにおける並列演算を既存の１２８ｂｉｔ（６４ｂｉｔ×２）のＳＩＭＤ命令によって実行することが可能である。
【０１２５】
並列乗算は一つの有限体の元を共通としてＡ×Ｂ、Ａ×Ｃを同時に行う方法である。この乗算は、前述した演算処理シーケンス中、（＊）を付した部分で利用できる。
【０１２６】
前述したように、ＳＩＭＤ(Single Instruction, Multiple Data)命令はプロセッサの持つ一つの命令で同じ種類の複数の演算（乗算や加算など）を同時に行う命令であり、近年のＩｎｔｅｌやＳｕｎなどの代表的なプロセッサに実装されている命令セットである。
【０１２７】
この並列乗算を使って、Ｉｎｔｅｌ社のＰｅｎｔｉｕｍ４，ＭｉｃｒｏｓｏｆｔＶｉｓｕａｌＣ＋＋６．０を使って実装を行った結果、オリジナルのアルゴリズムを実装した場合に比べて約９％高速化させて因子のスカラー倍算を計算することができた。Ｐｅｎｉｔｕｍ４のＳＳＥ２命令では１２８ｂｉｔ（６４ｂｉｔｘ２）ＳＩＭＤ命令をサポートしている。
【０１２８】
なお、Ｐｅｎｉｔｕｍ４のＳＳＥ２命令における１２８ｂｉｔ（６４ｂｉｔｘ２）ＳＩＭＤ命令のサポート情報についての説明は、例えば、［Intel Corp., IA-32 Intel Architecture Software Developer's Manual, volume 1: Basic Architecture］、あるいは、［Intel Corp., IA-32 Intel Architecture Software Developer's Manual, volume 2: Instruction Set Reference］に記載されている。
【０１２９】
なお、現存するＳＩＭＤ命令は、６４ｂｉｔ単位の演算を許容するものであり、現存するＳＩＭＤ命令に基づいて演算を実行する場合は、６４ｂｉｔ以下のデータに基づく処理が必要となる。以下、６４ｂｉｔデータを２つ格納したレジスタによる並列演算処理の具体的実行例について説明する。
【０１３０】
（４）１２８ビット演算処理によるＧＦ（２ｎ）演算処理構成
次に、１２８ｂｉｔ演算処理による有限体ＧＦ（２ｎ）演算の並列演算の実施例について説明する。
【０１３１】
まず、１２８ｂｉｔ（６４ｂｉｔ×２）のＳＩＭＤ(Single Instruction, Multiple Data)命令を適用した並列演算処理例について、図４を参照して説明する。１２８ｂｉｔデータの並列シフト処理、並列排他論理和（ＸＯＲ）処理、および並列ＡＮＤ処理演算について説明する。
【０１３２】
まず、演算処理対象データの格納例を図４（ａ）に示す。図４（ａ）に示すように、２つの６４ｂｉｔ以下のＧＦ（２ｎ）の元Ｂ、Ｃを１２８ｂｉｔの上位６４ｂｉｔ、下位６４ｂｉｔに分けて格納する。
【０１３３】
並列シフト演算処理は、図４（ｂ）に示すように、６４ｂｉｔ単位で独立かつ同時に右もしくは左にビットシフトを行う。これらのシフト処理は、１つの処理サイクルにおいて並列に実行可能である。
【０１３４】
並列排他論理和（ＸＯＲ）演算処理は、図４（ｃ）に示すように、１２８ｂｉｔを一括して、ビット単位の排他論理和（ＸＯＲ）演算を行う。
【０１３５】
並列ＡＮＤ演算処理は、図４（ｄ）に示すように、１２８ｂｉｔを一括して、ビット単位のＡＮＤ演算を行う。
【０１３６】
これら、１２８ｂｉｔデータの並列シフト処理、並列排他論理和（ＸＯＲ）処理、および並列ＡＮＤ処理演算はＩｎｔｅｌのＰｅｎｔｉｕｍ４プロセッサのＳＩＭＤ命令であるＳＳＥ２を用いた場合、実現可能である。
【０１３７】
上記の並列排他論理和（ＸＯＲ）処理を用いることでＧＦ（２ｎ）の元のＡ＋Ｂ，Ｃ＋Ｄの並列加算、すなわち、Ｂ１＋Ｂ２ Ｏｖｅｒ ＧＦ（２ｎ）およびＣ１＋Ｃ２ Ｏｖｅｒ ＧＦ（２ｎ）の並列加算処理を行うことができる。
【０１３８】
これらの、１２８ｂｉｔデータの並列シフト処理、並列排他論理和（ＸＯＲ）処理、および並列ＡＮＤ処理演算処理を組み合わせてＧＦ（２ｎ）のＡ×Ｂ，Ａ×Ｃの並列乗算アルゴリズムを構成することができる。
【０１３９】
すなわち、前述の各演算シーケンス中（＊）で示したＡ×Ｂ，Ａ×Ｃの並列乗算アルゴリズムを１２８ｂｉｔデータの並列シフト処理、並列排他論理和（ＸＯＲ）処理、および並列ＡＮＤ処理演算処理を組み合わせて実行、すなわち、ＩｎｔｅｌのＰｅｎｔｉｕｍ４プロセッサのＳＩＭＤ命令であるＳＳＥ２を用いて実行することができる。
【０１４０】
以下、既約多項式がｘ５９＋ｘ６＋ｘ５＋ｘ４＋ｘ３＋ｘ＋１の並列乗算アルゴリズムの実行例について説明する。このアルゴリズムはこれまで知られている並列ではない乗算の高速アルゴリズムと見た目上の処理は変わらないが、レジスタを１２８ｂｉｔに拡張し、ＸＯＲ，ＡＮＤ処理を、図４を参照して説明した並列処理のシフト、ＸＯＲ，ＡＮＤ演算に置き換えることが可能である。
【０１４１】
Ａ×Ｂ，Ａ×Ｃの並列乗算アルゴリズムは、下記のアルゴリズムとなる。
【数４】
2005043637.tif 000006
【０１４２】
上記の並列乗算アルゴリズムを、１２８ｂｉｔデータの並列シフト処理、並列排他論理和（ＸＯＲ）処理、および並列ＡＮＤ処理演算処理を組み合わせて実行する処理例について、図５〜図７を参照して説明する。上記アルゴリズムのステップ１〜８は、図５〜図７の各ステップ１〜８に対応する。
【０１４３】
ステップ１．
１２８ｂｉｔレジスタＨ，Ｌをゼロで初期化する。
【０１４４】
ステップ２．
Ｂ，Ｃに関するテーブルＴＢＣを作成する。これには、下記の各値が格納される。
（ａ）ＴＢＣ［０］←｜０×Ｂ｜０×Ｃ｜
（ｂ）ＴＢＣ［１］←｜１×Ｂ｜１×Ｃ｜
（ｃ）ＴＢＣ［２］←｜ｘ×Ｂ｜ｘ×Ｃ｜
（ｄ）ＴＢＣ［３］←｜（ｘ＋１）×Ｂ｜（ｘ＋１）×Ｃ｜
（ｅ）ＴＢＣ［４］←｜ｘ２×Ｂ｜ｘ２×Ｃ｜
（ｆ）ＴＢＣ［５］←｜（ｘ２＋１）×Ｂ｜（ｘ２＋１）×Ｃ｜
（ｇ）ＴＢＣ［６］←｜（ｘ２＋ｘ）×Ｂ｜（ｘ２＋ｘ）×Ｃ｜
（ｈ）ＴＢＣ［７］←｜（ｘ２＋ｘ＋１）×Ｂ｜（ｘ２＋ｘ＋１）×Ｃ｜
（ｉ）ＴＢＣ［８］←｜ｘ３×Ｂ｜ｘ３×Ｃ｜
（ｊ）ＴＢＣ［９］←｜（ｘ３＋１）×Ｂ｜（ｘ３＋１）×Ｃ｜
（ｋ）ＴＢＣ［１０］←｜（ｘ３＋ｘ）×Ｂ｜（ｘ３＋ｘ）×Ｃ｜
（ｌ）ＴＢＣ［１１］←｜（ｘ３＋ｘ＋１）×Ｂ｜（ｘ３＋ｘ＋１）×Ｃ｜
（ｍ）ＴＢＣ［１２］←｜（ｘ３＋ｘ２）×Ｂ｜（ｘ３＋ｘ２）×Ｃ｜
（ｎ）ＴＢＣ［１３］←｜（ｘ３＋ｘ２＋１）×Ｂ｜（ｘ３＋ｘ２＋１）×Ｃ｜
（ｏ）ＴＢＣ［１４］←｜（ｘ３＋ｘ２＋ｘ）×Ｂ｜（ｘ３＋ｘ２＋ｘ）×Ｃ｜
（ｐ）ＴＢＣ［１５］←｜（ｘ３＋ｘ２＋ｘ＋１）×Ｂ｜（ｘ３＋ｘ２＋ｘ＋１）×Ｃ｜
が代入される。
【０１４５】
ステップ３．
Ａ×Ｂ，Ａ×Ｃを計算する。Ａ，Ｂ，Ｃをそれぞれ、０，１係数の次数５８次の多項式とみなし、Ａ×Ｂ，Ａ×Ｃを多項式の掛け算を用いて求める。すると、Ａ×Ｂ，Ａ×Ｃは１１６次の多項式となる。Ｈには、Ａ×Ｂ，Ａ×Ｃの６４次〜１１６次が保存され、ＬにはＡ×Ｂ，Ａ×Ｃの０次〜６３次が保存される。このアルゴリズムでは、Ｈの上位６４ｂｉｔにはＡ×Ｂの６４次〜１１６次、下位６４ｂｉｔにはＡ×Ｃの６４次〜１１６次が保存される。
【０１４６】
Ｌの上位６４ｂｉｔにはＡ×Ｂの０次〜６３次、下位６４ｂｉｔにはＡ×Ｃの０次〜６３次が保存される。このアルゴリズムでは、実際には、掛け算を用いず、ステップ２で作成したテーブルＴＢＣを参照することにより、Ａ×Ｂ，Ａ×Ｃを求める。具体的には、Ａを下位から４ｂｉｔ毎にピックアップし、その４ｂｉｔの値ｉをインデックスに持つテーブル成分ＴＢＣ［ｉ］を参照し、このＴＢＣ［ｉ］に対して、適切な並列シフト演算を施し、Ｈ，Ｌと並列排他論理和（ＸＯＲ）演算を実行する。
【０１４７】
ステップ４
Ａ×Ｂ，Ａ×Ｃの６４次〜１１６次に対して、既約多項式ｘ５９＋ｘ６＋ｘ５＋ｘ４＋ｘ３＋ｘ＋１でリダクションする。ｘ５９＋ｘ６＋ｘ５＋ｘ４＋ｘ３＋ｘ＋１＝０であることから、
ｘ５９＝ｘ６＋ｘ５＋ｘ４＋ｘ３＋ｘ＋１
が成立する。
両辺にｘ５を乗じると
ｘ６４＝ｘ１１＋ｘ１０＋ｘ９＋ｘ８＋ｘ６＋ｘ５
が成り立つ。
【０１４８】
Ａ×Ｂ，Ａ×Ｃの６４次〜１１６次、０次〜６３次までをそれぞれ、ＡＢ［６４：１１６］，ＡＢ［０：６３］，ＡＣ［６４：１１６］，ＡＣ［０：６３］とあらわすと、既約多項式により、次のようにリダクションできる。
【０１４９】
Ａ×Ｂ＝ＡＢ［６４：１１６］×ｘ６４＋ＡＢ［０：６３］
≡ＡＢ［６４：１１６］×（ｘ１１＋ｘ１０＋ｘ９＋ｘ８＋ｘ６＋ｘ５）＋ＡＢ［０：６３］ｍｏｄ（ｘ５９＋ｘ６＋ｘ５＋ｘ４＋ｘ３＋ｘ＋１）
＝ＡＢ'［０：６３］
【０１５０】
Ａ×Ｃ＝ＡＣ［６４：１１６］×ｘ６４＋ＡＣ［０：６３］
≡ＡＣ［６４：１１６］×（ｘ１１＋ｘ１０＋ｘ９＋ｘ８＋ｘ６＋ｘ５）＋ＡＣ［０：６３］ｍｏｄ（ｘ５９＋ｘ６＋ｘ５＋ｘ４＋ｘ３＋ｘ＋１）
＝ＡＣ'［０：６３］
【０１５１】
この演算は、Ｈ（Ａ×Ｂ，Ａ×Ｃの６４次〜１１６次が保存されている）に適切な並列シフト演算を施し、Ｌと並列ＸＯＲ演算を行うことにより計算できる。結果はＬに保存される。
【０１５２】
ステップ５
ステップ４で求めたＡＢ'［０：６３］，ＡＣ'［０：６３］の５９次〜６３次に対して、既約多項式ｘ５９＋ｘ６＋ｘ５＋ｘ４＋ｘ３＋ｘ＋１でリダクションする。Ｌ（ＡＢ'［０：６３］，ＡＣ'［０：６３］が保存されている）に適切な並列シフト演算を施し、Ｌと並列ＸＯＲ演算を行うことにより計算できる。結果はＬに保存される。
【０１５３】
ステップ６．
ステップ５でＡ×ＢｍｏｄＦ，Ａ×ＣｍｏｄＦの計算は終了するが、Ｌの１２３ｂｉｔ〜１２７ｂｉｔ（ＡＢ'［０：６３］の５９次〜６３次）および５９ｂｉｔ〜６３ｂｉｔ（ＡＣ'［０：６３］の５９次〜６３次）に、不要なデータが残っているため、この不要なデータをゼロクリアする。以上で、Ｌの上位半分にＡ×ＢｍｏｄＦが、下位半分にＡ×ＣｍｏｄＦが保存される。
【０１５４】
ステップ７，ステップ８．
ＤにＡ×ＢｍｏｄＦ，ＥにＡ×ＣｍｏｄＦを代入して返す。
【０１５５】
上述の並列乗算処理例では、既約多項式をｘ５９＋ｘ６＋ｘ５＋ｘ４＋ｘ３＋ｘ＋１としたが、上述の１２８ｂｉｔデータの並列シフト処理、並列排他論理和（ＸＯＲ）処理、および並列ＡＮＤ処理演算を適用した処理は、６４次以下の既約多項式について一般的に適用可能である。
【０１５６】
なお、上述の処理例において、ステップ２，３ではテーブルを使った高速な多項式の乗算のアルゴリズムを使っているが、既約多項式の次数が大きさとテーブルのサイズの関係でレジスタをあふれてしまう場合も考えられる。しかしテーブルサイズを小さくしたり、もしくはテーブルを使わずに１ｂｉｔごとの掛け算を行い、Ｈ，Ｌに結果を格納することも可能である。従って既約多項式の次数が６４ｂｉｔ以下であれば汎用的に並列化を行うことができる。
【０１５７】
また、ステップ４におけるリダクションの操作におけるシフトするビット数は既約多項式の次数以外のｘの次数と項の数によって異なってくる。一般に既約多項式をｘｎ＋ｘａ１＋ｘａ２＋...．＋１（ｎ＞ａ１＞ａ２＞...．．）とした場合、例に示した１１，１０，９，８，６，５の値は６４−ｎ＋ａ１，６４−ｎ＋ａ２，...．，６４−ｎに変更される。
【０１５８】
また、ステップ４におけるリダクションの操作において、６４−ｎ＋ａ１ビットシフトした場合にレジスタサイズを越えてしまうケースがある。あふれない既約多項式の条件はｎ≦６５−ａ１である。この条件を満たさない場合はあふれた桁に対する簡単な例外処理を施すことで一般の既約多項式での並列演算が可能になる。
既約多項式が上記の条件を満たさない場合の処理の例として既約多項式がｘ５９＋ｘ7+ｘ４＋ｘ2＋１の場合の例を挙げる。
この場合の数式３におけるステップ４の式は、下式、
【数５】
2005043637.tif 000007
となる。例外処理が第１式である。既約多項式が条件を満たす場合，第２式だけで正しい結果が計算できる。しかしこの例では第１式によりあふれてしまう１ビットを取り出し、正しい結果が処理できるように補正を行っている。２ｂｉｔ以上あふれる場合も同様の処理で該当ビットを取り出し補正することで対応可能である。
【０１５９】
上述したように、種数ｇ＝３での超楕円曲線の暗号演算における並列乗算処理アルゴリズムに、１２８ｂｉｔデータの並列シフト処理、並列排他論理和（ＸＯＲ）処理、および並列ＡＮＤ処理演算を適用した処理が実行可能であり、ソフトウェアプログラムに従った高速演算が実行可能となる。上述の１２８ｂｉｔデータの並列シフト処理、並列排他論理和（ＸＯＲ）処理、および並列ＡＮＤ処理演算を適用した並列乗算は、前述の種数ｇ＝３における有限体ＧＦ（２ｎ）のＡ×Ｂ，Ａ×Ｃの並列乗算、すなわち、上述した演算シーケンスにおける（＊）の印をつけた部分の並列乗算に適用可能である。
【０１６０】
なお、上述したように、現存するＳＩＭＤ命令は、６４ｂｉｔ単位の演算を許容するものであり、現存するＳＩＭＤ命令に基づいて演算を実行する場合は、６４ｂｉｔ以下のデータに基づく処理が必要となるが、６４ｂｉｔ以上のデータを対象とした演算命令を設定し、その演算命令を適用した処理によれば、さらに高速化された演算が可能である。また、上述した種数ｇ＝３の並列乗算に限らず、超楕円曲線暗号処理における各種の並列演算を並列処理することにより、ソフトウェアによる超楕円曲線暗号の演算処理のさらなる高速化が実現される。
【０１６１】
（５）プログラム実行型ＩＣモジュール
最後に、上述の暗号処理をソフトウェアプログラムに従って実行するデバイスとしてのＩＣモジュール２００の構成例を図８に示す。上述の処理は、例えばＰＣ、ＩＣカード、リーダライタ、その他、様々な情報処理装置において実行可能であり、図８に示すＩＣモジュール２００は、これら様々な機器に構成することが可能である。
【０１６２】
図８に示すＣＰＵ(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)、インターネットといったネットワークを介して、コンピュータに有線で転送し、コンピュータでは、そのようにして転送されてくるプログラムを受信し、内蔵するハードディスク等の記録媒体にインストールすることができる。
【０１７４】
なお、明細書に記載された各種の処理は、記載に従って時系列に実行されるのみならず、処理を実行する装置の処理能力あるいは必要に応じて並列的にあるいは個別に実行されてもよい。また、本明細書においてシステムとは、複数の装置の論理的集合構成であり、各構成の装置が同一筐体内にあるものには限らない。
【産業上の利用可能性】
【０１７５】
本発明は、暗号処理を実行するデバイス、例えば暗号処理モジュールを持つＩＣカードあるいはその他の暗号処理装置に適用可能である。本発明の構成を適用することにより、高速な暗号処理が可能となるので高速処理機能が要請されるデバイスあるいは装置において利用可能である。
【図面の簡単な説明】
【０１７６】
【図１】超楕円曲線暗号のスカラー倍算における加算処理の場合分けについて説明する図である。
【図２】超楕円曲線暗号のスカラー倍算における２倍算処理の場合分けについて説明する図である。
【図３】本発明の超楕円曲線暗号演算処理を実行するハードウェア構成例を示す図である。
【図４】１２８ｂｉｔ（６４ｂｉｔ×２）のＳＩＭＤ(Single Instruction, Multiple Data)命令を適用した並列演算処理例としての並列シフト処理、並列排他論理和（ＸＯＲ）処理、および並列ＡＮＤ処理演算について説明する図である。
【図５】並列乗算アルゴリズムを、１２８ｂｉｔデータの並列シフト処理、並列排他論理和（ＸＯＲ）処理、および並列ＡＮＤ処理演算処理を組み合わせにより実行する処理例（ステップ１〜ステップ３）を説明する図である。
【図６】並列乗算アルゴリズムを、１２８ｂｉｔデータの並列シフト処理、並列排他論理和（ＸＯＲ）処理、および並列ＡＮＤ処理演算処理を組み合わせにより実行する処理例（ステップ４）を説明する図である。
【図７】並列乗算アルゴリズムを、１２８ｂｉｔデータの並列シフト処理、並列排他論理和（ＸＯＲ）処理、および並列ＡＮＤ処理演算処理を組み合わせにより実行する処理例（ステップ５〜ステップ８）を説明する図である。
【図８】本発明の暗号処理演算を実行する暗号処理実行デバイス例としてのＩＣモジュールの構成例を示す図である。
【符号の説明】
【０１７７】
１０１  乗算器，加算器
１０２  セレクタ
１０３  データ記憶部
１０４  セレクタ
１０５  制御部
２００  ＩＣモジュール
２０１  ＣＰＵ(Central processing Unit)
２０２  メモリ
２０３  暗号処理部
２０４  乱数発生器
２０５  送受信部
【図１】
2005043637.tif 000008
【図２】
2005043637.tif 000009
【図３】
2005043637.tif 000010
【図４】
2005043637.tif 000011
【図５】
2005043637.tif 000012
【図６】
2005043637.tif 000013
【図７】
2005043637.tif 000014
【図８】
2005043637.tif 000015