(57)【要約】【課題】ＳＩＭＤ処理を用いた楕円曲線８倍化のためのシステムおよび方法を提供する。【解決手段】一態様では、座標が（ｘ，ｙ，ｚ）である、楕円曲線上の重み付け射影点Ｐが特定される。８Ｐという値は、Ｐから、１２組の体の乗算により、ＳＩＭＤ処理を用いて計算される。体の乗算の各組は、１つから４つの体の乗算をそれぞれ含む。体の乗算の各組は、並列に、割り当てられた時間ステップに従って実行される。【選択図】図１
2006259735.tif 000002
【特許請求の範囲】
【請求項１】
楕円曲線上の重み付け射影点Ｐを識別することであって、Ｐの座標は（ｘ，ｙ，ｚ）であること、および
１２組の体の乗算でＰから８Ｐを計算することであって、体の乗算の各組は１つから４つの体の乗算を含み、体の乗算の各組は並列に、割り当てられた時間ステップに従って行われ、８Ｐの座標は（ｒ，ｓ，ｔ）であること
を含むことを特徴とする方法。
【請求項２】
前記８Ｐを計算することは、繰り返し２倍化操作とは独立であることを特徴とする請求項１に記載の方法。
【請求項３】
前記８Ｐを計算することは、ストレートライン型アルゴリズムによって決定され、前記方法は、
８Ｐを決定することであって、前記楕円曲線上のそれぞれの点に対して、前記ストレートライン型楕円曲線点８倍化アルゴリズムを用いて行うこと、および
元のデータを暗号化することまたは署名することを、前記８Ｐを決定することの結果に基づいて行うこと
をさらに含むことを特徴とする請求項１に記載の方法。
【請求項４】
前記８Ｐを計算することは、ストレートライン型アルゴリズムによって決定され、前記方法は、
８Ｐを決定することであって、前記楕円曲線上のそれぞれの点に対して、前記ストレートライン型楕円曲線点８倍化アルゴリズムを用いて行うこと、および
暗号処理されたデータを復号することまたは検証することを、前記８Ｐを決定することの結果に基づいて行うこと
をさらに含むことを特徴とする請求項１に記載の方法。
【請求項５】
前記１２組の体の乗算は、ストレートライン型楕円曲線点８倍化アルゴリズムで提供され、これがＳＩＭＤ処理で実装されない場合には、８Ｐを計算するための２６回の体の乗算になることを特徴とする請求項１に記載の方法。
【請求項６】
記号：＝は「定義する」操作を表し、前記ストレートライン型楕円曲線点８倍化アルゴリズムは、次のもの、すなわち
ｘ２：＝ｘ＾２；
ｙ２：＝ｙ＾２；
ｙ４：＝ｙ２＾２；
ｘｙ２：＝ｘ＊ｙ２；
ｙｚ：＝ｙ＊ｚ；
ｚ２：＝ｚ＾２；
ｚ４：＝ｚ２＾２；
ａｚ４：＝ａ＊ｚ４；
ａｙ４ｚ４：＝ａｚ４＊ｙ４；
Ｔ１：＝３＊ｘ２＋ａｚ４；
Ｔ１２：＝Ｔ１＾２；
Ｔ２：＝１２＊ｘｙ２−Ｔ１２；
Ｔ３：＝Ｔ１２−８＊ｘｙ２；
Ｔ３２：＝Ｔ３＾２；
Ｔ４：＝Ｔ１＊Ｔ２−８＊ｙ４；
Ｔ４２：＝Ｔ４＾２；
Ｔ４４：＝Ｔ４２＾２；
Ｔ５：＝３＊Ｔ３２＋１６＊ａｙ４ｚ４；
Ｔ５２：＝Ｔ５＾２；
Ｔ６：＝Ｔ４４＊２５６＊ａｙ４ｚ４；
Ｔ７：＝Ｔ３＊Ｔ４２；
Ｔ８：＝Ｔ５２−８＊Ｔ７；
Ｔ８２：＝３＊Ｔ８＾２；
Ｔ９：＝Ｔ８２＋Ｔ６；
Ｔ９２：＝（Ｔ９）＾２；
Ｓ１０：＝Ｔ５２−８＊Ｔ７；
Ｓ１１：＝１２＊Ｔ７−Ｔ５２；
Ｓ１２：＝Ｔ５＊Ｓ１１；
Ｓ１３：＝Ｓ１２−８＊Ｔ４４；
Ｓ１３２：＝Ｓ１３＾２；
Ｓ１４：＝Ｓ１０＊Ｓ１３２；
ｒ：＝Ｔ９２−８＊Ｓ１４；
Ｓ１５：＝１２＊Ｓ１４−Ｔ９２；
Ｓ１３４：＝Ｓ１３２＾２；
ｓ：＝Ｔ９＊Ｓ１５−８＊Ｓ１３４；および
ｔ：＝８＊Ｓ１３＊Ｔ４＊ｙｚ
を含むことを特徴とする請求項５に記載の方法。
【請求項７】
前記１２組の体の乗算のうちの各組のそれぞれのステップにおける実行は、
８Ｐ、ｘ２、ｙ２、ｙｚ、およびｚ２を、時間ステップ１において、
ｙ４、ｘｙ２、およびｚ４を、時間ステップ２において、
ａｚ４を、時間ステップ３において、
ａｙ４ｚ４およびＴ１を、時間ステップ４において、
Ｔ１２、Ｔ２、およびＴ３を、時間ステップ５において、
Ｔ３２、Ｔ４、およびＴ５を、時間ステップ６において、
Ｔ４２およびＴ５２を、時間ステップ７において、
Ｔ４４、Ｔ７、Ｔ８、Ｓ１０、およびＳ１１を、時間ステップ８において、
Ｔ８２、Ｔ９、Ｓ１２、およびＳ１３を、時間ステップ９において、
Ｔ９２、Ｓ１３２、およびｔの第１の部分を、時間ステップ１０において、
Ｓ１４、ｒ、Ｓ１５、Ｓ１３４、およびｔの残りの部分を、時間ステップ１１において、
ｓを、時間ステップ１２において
実施することによって行われることを特徴とする請求項６に記載の方法。
【請求項８】
楕円曲線上の重み付け射影点Ｐを識別することであって、Ｐの座標は（ｘ，ｙ，ｚ）であること、および
１２組の体の乗算でＰから８Ｐを計算することであって、体の乗算の各組は１つから４つの体の乗算を含み、体の乗算の各組は並列に、割り当てられた時間ステップに従って行われ、８Ｐの座標は（ｒ，ｓ，ｔ）であること
のための、プロセッサによって実行可能なコンピュータプログラム命令を含むことを特徴とするコンピュータ読取り可能記憶媒体。
【請求項９】
前記８Ｐを計算することのためのコンピュータプログラム命令は、繰り返し２倍化操作とは独立であることを特徴とする請求項８に記載のコンピュータ読取り可能記憶媒体。
【請求項１０】
前記８Ｐを計算することのためのコンピュータプログラム命令は、ストレートライン型アルゴリズムによって決定され、前記コンピュータプログラム命令は、
８Ｐを決定することであって、前記楕円曲線上のそれぞれの点に対して、前記ストレートライン型楕円曲線点８倍化アルゴリズムを用いて行うこと、および
元のデータの暗号化することまたは署名することを、前記８Ｐを決定することの結果に基づいて行うこと
のための命令をさらに含むことを特徴とする請求項８に記載のコンピュータ読取り可能記憶媒体。
【請求項１１】
前記８Ｐを計算することのためのコンピュータプログラム命令は、ストレートライン型アルゴリズムによって決定され、前記コンピュータプログラム命令は、
８Ｐを決定することであって、前記楕円曲線上のそれぞれの点に対して、前記ストレートライン型楕円曲線点８倍化アルゴリズムを用いて行うこと、および
暗号処理されたデータを復号することまたは検証することを、前記８Ｐを決定することの結果に基づいて行うこと
のための命令をさらに含むことを特徴とする請求項８に記載のコンピュータ読取り可能記憶媒体。
【請求項１２】
前記１２組の体の乗算は、ストレートライン型楕円曲線点８倍化アルゴリズムで提供され、これがＳＩＭＤ処理で実装されない場合には、８Ｐを計算するための２６回の体の乗算になることを特徴とする請求項８に記載のコンピュータ読取り可能記憶媒体。
【請求項１３】
記号：＝は「定義する」操作を表し、前記ストレートライン型楕円曲線点８倍化アルゴリズムは、次のもの、すなわち
ｘ２：＝ｘ＾２；
ｙ２：＝ｙ＾２；
ｙ４：＝ｙ２＾２；
ｘｙ２：＝ｘ＊ｙ２；
ｙｚ：＝ｙ＊ｚ；
ｚ２：＝ｚ＾２；
ｚ４：＝ｚ２＾２；
ａｚ４：＝ａ＊ｚ４；
ａｙ４ｚ４：＝ａｚ４＊ｙ４；
Ｔ１：＝３＊ｘ２＋ａｚ４；
Ｔ１２：＝Ｔ１＾２；
Ｔ２：＝１２＊ｘｙ２−Ｔ１２；
Ｔ３：＝Ｔ１２−８＊ｘｙ２；
Ｔ３２：＝Ｔ３＾２；
Ｔ４：＝Ｔ１＊Ｔ２−８＊ｙ４；
Ｔ４２：＝Ｔ４＾２；
Ｔ４４：＝Ｔ４２＾２；
Ｔ５：＝３＊Ｔ３２＋１６＊ａｙ４ｚ４；
Ｔ５２：＝Ｔ５＾２；
Ｔ６：＝Ｔ４４＊２５６＊ａｙ４ｚ４；
Ｔ７：＝Ｔ３＊Ｔ４２；
Ｔ８：＝Ｔ５２−８＊Ｔ７；
Ｔ８２：＝３＊Ｔ８＾２；
Ｔ９：＝Ｔ８２＋Ｔ６；
Ｔ９２：＝（Ｔ９）＾２；
Ｓ１０：＝Ｔ５２−８＊Ｔ７；
Ｓ１１：＝１２＊Ｔ７−Ｔ５２；
Ｓ１２：＝Ｔ５＊Ｓ１１；
Ｓ１３：＝Ｓ１２−８＊Ｔ４４；
Ｓ１３２：＝Ｓ１３＾２；
Ｓ１４：＝Ｓ１０＊Ｓ１３２；
ｒ：＝Ｔ９２−８＊Ｓ１４；
Ｓ１５：＝１２＊Ｓ１４−Ｔ９２；
Ｓ１３４：＝Ｓ１３２＾２；
ｓ：＝Ｔ９＊Ｓ１５−８＊Ｓ１３４；および
ｔ：＝８＊Ｓ１３＊Ｔ４＊ｙｚ
を含むことを特徴とする請求項１２に記載のコンピュータ読取り可能記憶媒体。
【請求項１４】
８Ｐを計算することのためのコンピュータプログラム命令である、前記１２組の体の乗算のうちの各組のそれぞれのステップにおける実行は、
８Ｐ、ｘ２、ｙ２、ｙｚ、およびｚ２を、時間ステップ１において、
ｙ４、ｘｙ２、およびｚ４を、時間ステップ２において、
ａｚ４を、時間ステップ３において、
ａｙ４ｚ４およびＴ１を、時間ステップ４において、
Ｔ１２、Ｔ２、およびＴ３を、時間ステップ５において、
Ｔ３２、Ｔ４、およびＴ５を、時間ステップ６において、
Ｔ４２およびＴ５２を、時間ステップ７において、
Ｔ４４、Ｔ７、Ｔ８、Ｓ１０、およびＳ１１を、時間ステップ８において、
Ｔ８２、Ｔ９、Ｓ１２、およびＳ１３を、時間ステップ９において、
Ｔ９２、Ｓ１３２、およびｔの第１の部分を、時間ステップ１０において、
Ｓ１４、ｒ、Ｓ１５、Ｓ１３４、およびｔの残りの部分を、時間ステップ１１において、
ｓを、時間ステップ１２において
実施することによって行われることを特徴とする請求項１３に記載のコンピュータ読取り可能記憶媒体。
【請求項１５】
プロセッサと、
前記プロセッサに結合されたメモリとを含み、前記メモリは、
楕円曲線上の重み付け射影点Ｐを識別することであって、Ｐの座標は（ｘ，ｙ，ｚ）であること、および
１２組の体の乗算でＰから８Ｐを計算することであって、体の乗算の各組は１つから４つの体の乗算を含み、体の乗算の各組は並列に、割り当てられた時間ステップに従って行われ、８Ｐの座標は（ｒ，ｓ，ｔ）であること
のための、前記プロセッサで実行可能なコンピュータプログラム命令を含むことを特徴とするコンピューティング装置。
【請求項１６】
前記８Ｐを計算することのためのコンピュータプログラム命令は、ストレートライン型アルゴリズムによって決定され、前記コンピュータプログラム命令は、
８Ｐを決定することであって、前記楕円曲線上のそれぞれの点に対して、前記ストレートライン型楕円曲線点８倍化アルゴリズムを用いて行うこと、および
元のデータを暗号化することまたは署名することを、前記８Ｐを決定することの結果に基づいて行うこと
のための命令をさらに含むことを特徴とする請求項１５に記載のコンピューティング装置。
【請求項１７】
前記８Ｐを計算することのためのコンピュータプログラム命令は、ストレートライン型アルゴリズムによって決定され、前記コンピュータプログラム命令は、
８Ｐを決定することであって、前記楕円曲線上のそれぞれの点に対して、前記ストレートライン型楕円曲線点８倍化アルゴリズムを用いて行うこと、および
暗号処理されたデータを復号することまたは検証することを、前記８Ｐを決定することの結果に基づいて行うこと
のための命令をさらに含むことを特徴とする請求項１５に記載のコンピューティング装置。
【請求項１８】
前記１２組の体の乗算は、ストレートライン型楕円曲線点８倍化アルゴリズムで提供され、これがＳＩＭＤ処理で実装されない場合には、８Ｐを計算するための２６回の体の乗算になることを特徴とする請求項１５に記載のコンピューティング装置。
【請求項１９】
記号：＝は「定義する」操作を表し、前記ストレートライン型楕円曲線点８倍化アルゴリズムは、次のもの、すなわち
ｘ２：＝ｘ＾２；
ｙ２：＝ｙ＾２；
ｙ４：＝ｙ２＾２；
ｘｙ２：＝ｘ＊ｙ２；
ｙｚ：＝ｙ＊ｚ；
ｚ２：＝ｚ＾２；
ｚ４：＝ｚ２＾２；
ａｚ４：＝ａ＊ｚ４；
ａｙ４ｚ４：＝ａｚ４＊ｙ４；
Ｔ１：＝３＊ｘ２＋ａｚ４；
Ｔ１２：＝Ｔ１＾２；
Ｔ２：＝１２＊ｘｙ２−Ｔ１２；
Ｔ３：＝Ｔ１２−８＊ｘｙ２；
Ｔ３２：＝Ｔ３＾２；
Ｔ４：＝Ｔ１＊Ｔ２−８＊ｙ４；
Ｔ４２：＝Ｔ４＾２；
Ｔ４４：＝Ｔ４２＾２；
Ｔ５：＝３＊Ｔ３２＋１６＊ａｙ４ｚ４；
Ｔ５２：＝Ｔ５＾２；
Ｔ６：＝Ｔ４４＊２５６＊ａｙ４ｚ４；
Ｔ７：＝Ｔ３＊Ｔ４２；
Ｔ８：＝Ｔ５２−８＊Ｔ７；
Ｔ８２：＝３＊Ｔ８＾２；
Ｔ９：＝Ｔ８２＋Ｔ６；
Ｔ９２：＝（Ｔ９）＾２；
Ｓ１０：＝Ｔ５２−８＊Ｔ７；
Ｓ１１：＝１２＊Ｔ７−Ｔ５２；
Ｓ１２：＝Ｔ５＊Ｓ１１；
Ｓ１３：＝Ｓ１２−８＊Ｔ４４；
Ｓ１３２：＝Ｓ１３＾２；
Ｓ１４：＝Ｓ１０＊Ｓ１３２；
ｒ：＝Ｔ９２−８＊Ｓ１４；
Ｓ１５：＝１２＊Ｓ１４−Ｔ９２；
Ｓ１３４：＝Ｓ１３２＾２；
ｓ：＝Ｔ９＊Ｓ１５−８＊Ｓ１３４；および
ｔ：＝８＊Ｓ１３＊Ｔ４＊ｙｚ
を含むことを特徴とする請求項１８に記載のコンピューティング装置。
【請求項２０】
８Ｐを計算することのためのコンピュータプログラム命令である、前記１２組の体の乗算のうちの各組のそれぞれのステップにおける実行は、
８Ｐ、ｘ２、ｙ２、ｙｚ、およびｚ２を、時間ステップ１において、
ｙ４、ｘｙ２、およびｚ４を、時間ステップ２において、
ａｚ４を、時間ステップ３において、
ａｙ４ｚ４およびＴ１を、時間ステップ４において、
Ｔ１２、Ｔ２、およびＴ３を、時間ステップ５において、
Ｔ３２、Ｔ４、およびＴ５を、時間ステップ６において、
Ｔ４２およびＴ５２を、時間ステップ７において、
Ｔ４４、Ｔ７、Ｔ８、Ｓ１０、およびＳ１１を、時間ステップ８において、
Ｔ８２、Ｔ９、Ｓ１２、およびＳ１３を、時間ステップ９において、
Ｔ９２、Ｓ１３２、およびｔの第１の部分を、時間ステップ１０において、
Ｓ１４、ｒ、Ｓ１５、Ｓ１３４、およびｔの残りの部分を、時間ステップ１１において、
ｓを、時間ステップ１２において
実施することによって行われることを特徴とする請求項１９に記載のコンピューティング装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は一般に、データ処理に関し、より詳細には、楕円曲線暗号システムに関する。
【背景技術】
【０００２】
暗号システムは、甲から乙へと送られたデータの秘密性（confidentiality）、信頼性（authenticity）、完全性（integrity）、および否認防止（non-repudiation）に関係している。有限アーベル群における離散対数問題に基づく最新の暗号方式は、こうした問題に取り組むように設計されている。そのような有限アーベル群の１つは、単純な算術式の提供する群演算による有限体上の楕円曲線（elliptic curve）上の点からなる群である。そのような群は、暗号システムでますます利用されるようになっているが、その理由は、対応する群演算が、ハードウェアまたはソフトウェアで実現するのが比較的容易であるためである。
【０００３】
楕円曲線群を用いた実装効率を完全に理解するためには、関連する体の四則演算（arithmetic）を注意深く考慮すべきである。例えば、体の逆元演算（inversion）は、乗算演算に比べて、実装に著しく多くの処理が必要となる可能性がある。そのような場合、通常、重み付け射影座標を利用して、点の加算が体の乗算を用いて行えるようにし（例えば、非特許文献１参照）、それにより、体の逆元演算は、例えば、長く続く一連の乗算の最後まで保留される。しかし、逆元演算を実質的に取り除くということの計算上のコストは、増加した回数の乗算が計算されるということである。有限群Ｇ内の２つの元の乗算を行う効率のよい技法は、効率のよい指数計算を行うのに不可欠である。
【０００４】
指数計算は、公開鍵暗号方式では、楕円曲線上の点Ｐのスカラー倍ｎを計算するために一般によく使用される。ここでｎは非常に大きな整数（例えば、乱数または秘密鍵）であり、Ｐは重み付け射影座標である。ｎＰを計算する単純な手法は、群Ｇにおける演算をｎ−１回行うことである。暗号の適用例では、群Ｇの位数（order）は、通常、元が２160個を越えており、元が２2024個を越えることもある。そのような演算では、計算の量が多く、選ばれるｎはたいてい大きくて、応答のよいアプリケーションの提供ということから見ると、ｎＰの計算をＰによるｎ−１回の連続する乗算を用いて行うことが、実質的に実現不可能なほどになる。しかし、指数計算の計算上のコストを低減するために使用できるいくつもの技法がある。
【０００５】
例えば、繰り返し平方乗算（repeated square-and-multiply）アルゴリズム（すなわち、バイナリ法（binary exponentiation））、および窓方式（windowing methods）（例えば、非特許文献２参照）により、指数計算の計算上のコストを低減することができる。より具体的には、繰り返し平方乗算アルゴリズムでは、指数ｎを分割して２の冪乗のより小さい総和にし、このそれぞれでは、計算にかかる処理資源がより少なくなる。例えば、有限体上の楕円曲線上に座標（ｘ，ｙ，ｚ）の射影点Ｐがあるとき、ｎを大きさ２3の部分に分割して（すなわち、大きさ３の窓を用いて）、Ｐのスカラー倍（２3Ｐ、すなわち８Ｐ）の計算を複数の点の２倍化の反復によって行う。これを達成するために、既存のシステムでは、通常、Ｐ＝（ｘ，ｙ，ｚ）を平方乗算アルゴリズムへと入力して２Ｐを生成する。次に、２Ｐ（第１の２倍化演算からの出力）に対する座標を（ｘ，ｙ，ｚ）として同じ平方乗算アルゴリズムへと入力して、４Ｐを得る。最後に、この反復プロセスがもう１度繰り返されて、４Ｐ（第２の２倍化演算からの出力）に対する座標を（ｘ，ｙ，ｚ）として同じ平方乗算アルゴリズムへと入力して、８Ｐを得る。８Ｐを得るための繰り返し２倍化方法（repeated doubling method）は、計３０回の体の乗算を含んでいる。
【０００６】
【非特許文献１】Blake et al, "Elliptic Curves in Cryptography", Cambridge University Press, 1999, pages 59-60
【非特許文献２】Blake et al, "Elliptic Curves in Cryptography", Cambridge University Press, 1999, pages 63-72
【発明の開示】
【発明が解決しようとする課題】
【０００７】
コンピュータプロセッサでは、普通、コンピュータ命令ごとに１つのデータ要素の処理を行う。この処理スタイルは、ＳＩＳＤ（Single Instruction Single Data）と呼ばれる。有限体上の楕円曲線上の点Ｐから８Ｐを計算するためにＳＩＳＤ処理を用いる従来の指数計算の技法では、８Ｐの計算のための３０回の体の乗算（すなわち、３０個の体の乗算ステップ）を含む繰り返し／反復２倍化（repeated/iterative doublings）が必要である。８Ｐの計算のための体の乗算の回数（例えば、３０回の体の乗算）および／または処理時間を低減する技法により、効率の改善されたシステムが提供されるだろう。このために、有限体上の楕円曲線上の点Ｐから８Ｐを計算するためにＳＩＭＤ処理を使用する、この楕円曲線点８倍化（elliptic curve point octpuling）のためのシステムおよび方法では、８Ｐを計算するための体の乗算の回数は、従来の８Ｐのバイナリ法による実装に比べて、かなり低減される。
【課題を解決するための手段】
【０００８】
ＳＩＭＤ（Single Instruction Multiple Data）処理を用いた楕円曲線８倍化（elliptic curve octupling）のためのシステムおよび方法を説明する。一態様では、座標が（ｘ，ｙ，ｚ）である、楕円曲線上の重み付け射影点（weighted projective point）Ｐが特定される。値８Ｐは、ＳＩＭＤ処理を用いて、Ｐから、１２組の体の乗算により計算される。体の乗算の各組は、１から４回の体の乗算をそれぞれ含む。体の乗算の各組は、並列に、割り当てられた時間ステップ（time-step）に従って行われる。
【０００９】
図面では、構成要素の符号の最も左の数字により、その構成要素の最初に現れる特定の図を識別している。
【発明を実施するための最良の形態】
【００１０】
（概要）
本システムおよび方法では、有限体上の楕円曲線上の点Ｐの重み付け射影点８倍化のための、実質的に最適化されたストレートライン型（straight-line）アルゴリズムを実装する。このストレートライン型８倍化アルゴリズムの実装を、もっぱらＳＩＳＤ処理を用いて行った場合には、Ｐからの８Ｐの計算は、２６回の体の乗算で行われる。しかし、このストレートライン型８倍化アルゴリズムの実装は、ＳＩＭＤ処理を用いて行われて、Ｐからの８Ｐの計算は、最大幅が４の、１２ステップ以内の並列の体の乗算で行われる。すなわち、ＳＩＭＤ処理を利用すると、ストレートライン型アルゴリズムにおける乗算は、４つまでの並列の体の乗算からなる１２個のインスタンスに並列化される。議論の都合上、４つ以下の並列の体の乗算からなるインスタンスそれぞれを、ステップと呼ぶ。８Ｐの計算のためのどのような中間的な体の加算にも、無視できる長さの処理時間しかかからないと仮定する。したがって、既存のバイナリ法による実装に比べて、このＳＩＭＤ処理を用いた楕円曲線点８倍化のためのシステムおよび方法では、有限体上の楕円曲線上の点Ｐから８Ｐを計算するための体の乗算の回数および乗算ステップの数がかなり低減される。
【００１１】
ＳＩＭＤ処理を用いた楕円曲線点８倍化のためのシステムおよび方法の、これらおよびその他の態様を、次に、より詳細に説明する。
【００１２】
（例示的なシステム）
必須ではないが、ＳＩＭＤ処理を用いた楕円曲線点８倍化のためのシステムおよび方法の説明を、パーソナルコンピュータなどのコンピューティング装置の実行するコンピュータ実行可能命令（プログラムモジュール）の一般的な文脈において行う。プログラムモジュールは、一般に、特定のタスクを行い、または特定の抽象データ型を実装するルーチン、プログラム、オブジェクト、コンポーネント、データ構造などを含む。このシステムおよび方法の説明は以上の文脈において行うが、以下で説明する動作（acts）および操作は、ハードウェアで実装することもできる。
【００１３】
図１に、ＳＩＭＤ処理を用いた楕円曲線点８倍化のための例示的なシステム１００を示している。システム１００は、第１のコンピューティング装置１０２を含み、これは通信ネットワーク１０３を介して第２のコンピューティング装置１０４へと結合されている。通信ネットワーク１０３は、オフィス、企業規模のコンピュータネットワーク、イントラネット、インターネットなどでは一般的である、ＬＡＮおよび一般的なＷＡＮ通信環境のどのような組合せを含むものでもよい。第１のコンピューティング装置１０２、および第２のコンピューティング装置１０４は、それぞれ、パーソナルコンピュータ、ラップトップ、サーバ、ハンドヘルドまたはモバイルのコンピューティング装置（例えば、セルラ電話、ＰＤＡ（personal digital assistant））など、どのようなタイプのコンピューティング装置にも相当する。
【００１４】
コンピューティング装置１０２は、プログラムモジュール１０６およびプログラムデータ１０８を含む。プログラムモジュール１０６は、例えば、元のデータ１１２の署名または暗号化を、楕円曲線（ＥＣ）点８倍化の指数計算を用いてそれぞれ行う、署名／暗号化モジュール１１０を含む。後述する楕円曲線点８倍化のためのアルゴリズムとは独立に、署名／暗号化モジュール１１０の実装する特定の暗号プロトコルは、任意であり、また、実装のために選択された特定の暗号アルゴリズムの一機能である。署名／暗号化モジュール１１０は、楕円曲線点８倍化を行うために、楕円曲線１１４上の１組の点に対して操作を行う。楕円曲線１１４は、体の標数（characteristic）が２または３に等しくない場合、次の方程式、ｙ2＝ｘ3＋ａｘｚ4＋ｂｚ6に従う。基底の体の標数は、ｐとその体の任意の元（element）による積がゼロであるような、ゼロでない最小の自然数ｐであると定義される。
【００１５】
楕円曲線１１４上の点Ｐは、重み付け射影形式で、Ｐ＝（ｘ，ｙ，ｚ）と表される。一実装形態では、実装される暗号プロトコルが署名方式である場合には、点Ｐは、その暗号（cryptosystem）用の公開情報の一部とすることができる。別の実装形態では、実装される暗号プロトコルが鍵共有方式（例えば、Ｄｉｆｆｉｅ−Ｈｅｌｌｍａｎｎ鍵共有法）または暗号方式（例えば、ＥｌＧａｍａｌ暗号）である場合には、点Ｐを、暗号の公開情報または秘密情報の一部とすることができる。
【００１６】
表１に、楕円曲線１１４上の点Ｐから８Ｐ（図１のデータコンポーネント１１６を参照）を決定する例示的な直接型（direct）楕円曲線点８倍化アルゴリズムを示している。
【００１７】
【表１−１】
2006259735.tif 000003
【００１８】
【表１−２】
2006259735.tif 000004
【００１９】
表１では、８Ｐ＝（ｒ，ｓ，ｔ）という数量に対する数式を与えている。ここでＰは楕円曲線ｙ2＝ｘ3＋ａｘｚ4＋ｂｚ6上の重み付け射影座標（ｘ，ｙ，ｚ）において与えられた点である。従来のバイナリ法による指数計算の技法では、有限体上の楕円曲線上の点Ｐから８Ｐを生成するために平方乗算アルゴリズムを反復して呼び出すが、これとは対照的に、表１の８倍化アルゴリズムでは、８Ｐの座標（ｒ，ｓ，ｔ）の計算を、平方乗算アルゴリズムの反復呼び出しとは独立に行っている。
【００２０】
そのような直接型点８倍化アルゴリズムは、窓の大きさ３を用いた指数計算ルーチンのための基本操作として使用することができる（ここで、窓の大きさ（window size）は、どの２の冪乗を使用して指数を分解するかを示す）。例えば、５８７＊Ｐは、２＊（２＊（２＊（２＊（２＊（２＊（２＊２＊２＊Ｐ＋Ｐ）））＋Ｐ））＋Ｐ）＋Ｐではなく、８＊（８＊（８＊Ｐ＋Ｐ）＋Ｐ）＋３＊Ｐとして計算することができる。
【００２１】
署名／暗号化モジュール１１０では、有限体上の楕円曲線１１４上の点Ｐの８Ｐ（１１６）の計算を、ストレートライン型アルゴリズムを用いて行い、これは表１の直接型アルゴリズムから導かれる。議論の都合上、ストレートライン型の数式とは、所望の結果を得るために、数式中の各ステートメントの実行を、連続して、ちょうど操作がコンピュータにより、コードのループまたは分岐がないように実装されるように行うためのプロセスである。表２に、例示的な、そのようなストレートライン型アルゴリズムを示している。
【００２２】
【表２−１】
2006259735.tif 000005
【００２３】
【表２−２】
2006259735.tif 000006
【００２４】
【表２−３】
2006259735.tif 000007
【００２５】
【表２−４】
2006259735.tif 000008
【００２６】
【表２−５】
2006259735.tif 000009
【００２７】
【表２−６】
2006259735.tif 000010
【００２８】
【表２−７】
2006259735.tif 000011
【００２９】
表２を参照すると、例示的なストレートライン型アルゴリズムの式を、その前に前向きの山括弧（forward angle bracket）を置き、ボールド体で示している。記号「：＝」は「定義」または「．．．として定義する」（is defined as）を意味する。表１のアルゴリズムとの比較の目的で、ストレートライン型アルゴリズムの式それぞれを、表１のアルゴリズムからの式に対応するプログラム命令の実行トレースのわきに（非ボールド体で）示している。表２に示すように、ストレートライン型アルゴリズムでは、表１に示した式のビルディングブロック（building block）または部分を、体系的に生成する。例示の目的で、そのようなビルディングブロックを「その他のデータ」１１８のそれぞれの部分で表している。例えば、定義「ｘｙ２：＝ｘ＊ｙ２」により、ｘｙ２は、ｘ＊ｙ２に等しく設定される。また、Ｔ２という項により、ｘｙ２の定義をＴ２：＝１２＊ｘｙ２−Ｔ１２に利用し、ｘ＊ｙ２などを計算し直さなくても済んでいることに注意されたい。このようにして、楕円曲線１１４上の点の８Ｐの（ｒ，ｓ，ｔ）の計算に必要な体の計算の数が、２６まで低減される。
【００３０】
表２の式の中の「＊」という記号は、それぞれ、体の乗算を示す。すなわち、署名／暗号化モジュール１１０では、計２６個の体の乗算に対して、１２個の平方（squares）を生成し、かつ、１４個の乗算の実装し、楕円曲線１１４上の点Ｐに対する８Ｐ（１１６）の座標（ｒ，ｓ，ｔ）を決定する。これは、既存の技法によって代表される体の乗算の回数の大幅な低減である。
【００３１】
表３に、表２のストレートライン型アルゴリズムのＳＩＭＤ処理に関する、時間ステップの例示的な組を示している。
【００３２】
【表３−１】
2006259735.tif 000012
【００３３】
【表３−２】
2006259735.tif 000013
【００３４】
表３を参照すると、１２個の時間ステップが示してあり、各時間ステップにより、並列に処理すべき１つまたは複数の式が識別されている。各時間ステップにより、さらに、１組の式の処理時間が、異なる時間ステップに関連する式の処理時間と比較して識別される。例えば、時間ステップ１でマークされる式に対するプログラム命令の実行は、並列に、かつ時間ステップ２でマークされる式それぞれに関連するプログラム命令の前に実行される。例えば、行６、７、１０、および１１のプログラム命令は、並列で第１のステップ（すなわち、ステップ１）の間に、かつ時間ステップ２〜１２に関連する命令の前に実行される。同様に、時間ステップ２でマークされる式それぞれに対するプログラム命令は、並列に、かつ時間ステップ３〜１２でマークされる式に関連するプログラム命令の前に実行される。例えば、行８、９、および１２のプログラム命令は、並列で第２のステップ（すなわち、ステップ２）の間に、時間ステップ１に対応する命令の後で、かつ時間ステップ３〜１２に対応する命令の前に実行される。このようにして、表３のストレートライン型アルゴリズムが、署名／暗号化モジュール１１０によって実施される。（ＳＩＭＤ処理を実装する例示的なプロセッサは、図３のプロセッサ３２０に関して示し、後述する）。星印（star）でマークしたステップは、体の加算または減算を表しており、体の並列の乗算と考えるべきではない。
【００３５】
表３に示すように、ストレートライン型アルゴリズムのＳＩＭＤ処理による実装から、有限体上の楕円曲線上の点Ｐの８Ｐの座標を計算する、深さが１２で幅が４の乗算計算の計算木（computation tree）ができる。具体的には、
・  ８Ｐ、ｘ２、ｙ２、ｙｚ、およびｚ２が、時間ステップ１において決定される。
・  ｙ４、ｘｙ２、およびｚ４が、時間ステップ２において決定される。
・  ａｚ４が、時間ステップ３において決定される。
・  ａｙ４ｚ４およびＴ１が、時間ステップ４において決定される。
・  Ｔ１２、Ｔ２、およびＴ３が、時間ステップ５において決定される。
・  Ｔ３２、Ｔ４、およびＴ５が、時間ステップ６において決定される。
・  Ｔ４２およびＴ５２が、時間ステップ７において決定される。
・  Ｔ４４、Ｔ７、Ｔ８、Ｓ１０、およびＳ１１が、時間ステップ８において決定される。
・  Ｔ８２、Ｔ９、Ｓ１２、およびＳ１３が、時間ステップ９において決定される。
・  Ｔ９２、Ｓ１３２、およびｔの第１の部分が、時間ステップ１０において決定され、ｔ1＝８＊Ｓ１３＊ｔ４である。
・  Ｓ１４、ｒ、Ｓ１５、Ｓ１３４、およびｔの残りの部分が、時間ステップ１１において決定され、ｔ＝ｔ1＊ｙｚである。
・  ｓが、時間ステップ１２において決定される。
【００３６】
体の加算および減算には、体の乗算に比べて、無視できる時間しかかからない。表２および表３のアルゴリズムの中の体の加算または減算を必要とするステップは、表３では、ステップの標示の次にアスタリスク（「＊」）でマークしてある。
【００３７】
署名／暗号化モジュール１１０では、楕円曲線８倍化指数計算を実装するように変更された任意の公開鍵ベースの暗号アルゴリズムを用いて、元のデータ１１２の暗号処理し、暗号処理されたデータを生成する。暗号処理されたデータを、「その他のデータ」１１８のそれぞれの部分として示している。暗号処理の説明を、Ｄｉｆｆｉｅ−Ｈｅｌｌｍａｎ鍵交換（key exchange）およびＥｌＧａｍａｌ暗号に関して行ってきているが、署名／暗号化モジュール１１０では、楕円曲線８倍化指数計算を利用するように変更されたその他のアルゴリズムを使用して、元のデータを暗号処理することができる。言い換えると、署名／暗号化モジュール１１０によって実装された特定の公開鍵ベースの暗号アルゴリズムは、表１および２に示した楕円曲線１１４上の点の８Ｐを計算するアルゴリズムとは独立であり、実装のために選択された特定の暗号アルゴリズムの一機能であるため、任意である。
【００３８】
例えば、署名／暗号化モジュール１１０のそれぞれの実装では、次の暗号プロトコルのうちの１つまたは複数を実装している。すなわち、アイデンティティによる暗号化（identity-based cryptography）（例えば、平文（plain）、ブラインド（blind）、代理（proxy）、リング、否認不可（undeniable）など）、暗号化プロトコル（例えば、認証済み、ブロードキャスト、キーワード検索による暗号化など）、バッチ署名、鍵共有（key agreement）（平文、認証済み、グループなど）、認証機関および公開鍵認証、階層型暗号システム（hierarchical cryptosystems）、閾値暗号システム（threshold cryptosystem）および署名、カメレオンハッシュ（chameleon hash）ならびに署名、認証、アプリケーションおよびシステム、アクセス制御、鍵共有、非対話的な鍵配布、クレデンシャル（例えば、匿名、隠し（hidden）、セルフブラインダブル（self-blindable）など）、シークレットハンドシェイク、証明可能にセキュリティ保護された署名（provably secure signatures）、ショートシグネチャ（short signatures）、アグリゲート、リング、および検証可能暗号化署名、ブラインドおよび部分ブラインド署名、代理署名、否認不可署名、サインクリプション、多重署名および閾値署名、ベリファイア限定（limited-verifier）およびベリファイア指定（designated-verifier）署名、閾値暗号システム、階層型および役割ベースの暗号システム、カメレオンハッシュおよび署名、検証可能な乱数関数（verifiable random functions）、強く絶縁された暗号（strongly insulated encryption）、イントリュージョンレジリエント暗号（intrusion-resilient encryption）、証明書を用いない公開鍵証明書（certificate-less PKC）、ａｌ、不正者追跡（traitor-tracing）、および／またはその他などである。
【００３９】
一実施形態では、コンピューティング装置１０２は、暗号処理されたデータをコンピューティング装置１０４へ、検証／復号のために通信で送る。例示の目的で、コンピューティング装置１０４が受け取る暗号処理されたデータを、署名／暗号化されたデータ１２０として示している。コンピューティング装置１０４は、受け取った暗号処理されたデータを検証または復号するための検証／復号モジュール１２２を含む。ある状況では、検証／復号モジュール１２２は、暗号処理されたデータが暗号署名されている場合に、暗号処理されたデータとして検証する。この場合、検証／復号モジュール１２２は、上述した楕円曲線点８倍化指数計算の１つまたは複数の実装を利用して、暗号処理されたデータを検証する。別の状況では、検証／復号モジュール１２２は、暗号化されている暗号処理されたデータを復号化する。この場合、検証／復号モジュール１２２は、上述した楕円曲線点８倍化指数計算の１つまたは複数の実装を利用して、暗号処理されたデータを復号化する。
【００４０】
（ＳＩＭＤ処理を用いた例示的な楕円曲線点８倍化）
図２に、ＳＩＭＤ処理を用いた楕円曲線点８倍化のための例示的な手順２００を示している。議論および例示の都合上、手順２００の操作の説明を、図１の構成要素に関して行う。このために、構成要素の符号の左端の数字は、その構成要素が最初に現れる特定の図を示している。ブロック２０２において、署名／暗号化モジュール１１０（図１）は、有限体Ｆq上の楕円曲線１１４上の点Ｐを識別する。点Ｐは、（ｘ，ｙ，ｚ）という重み付け射影座標をもつ。ブロック２０４において、署名／暗号化モジュール１１０は、繰り返し２倍化操作とは独立に、Ｐの８Ｐを計算する。８Ｐの座標は（ｒ，ｓ，ｔ）である。一実施形態では、８Ｐは、表３のストレートライン型楕円曲線点８倍化アルゴリズムを用いて計算される。これは、ＳＩＭＤ処理を用いて達成される。結果として、８Ｐは、最大幅が４である並列の体の乗算１２回で計算される（すなわち、対応する時間ステップの関数として並列に実行される１つから４つの乗算演算である）。ブロック２０６において、楕円曲線点８倍化アルゴリズムの結果を利用して、元のデータの暗号化または暗号署名、または暗号処理されたデータの復号または検証が行われる。
【００４１】
（例示的な動作環境）
図３に、ＳＩＭＤ処理を用いた楕円曲線点８倍化を完全にまたは部分的に実装できる適切なコンピューティング環境の例を示している。例示的なコンピューティング環境３００は、図１の例示的なシステムおよび図２の例示的な操作に適したコンピューティング環境の１つの例に過ぎず、本明細書で説明するシステムおよび方法の使用または機能の範囲に関してなんら制限を示唆するものではない。また、コンピューティング環境３００になんらかの依存関係または要件があるとの解釈を、コンピューティング環境３００に示す構成要素のいずれかまたは組合せに関して行うべきでもない。
【００４２】
本明細書で説明する方法およびシステムは、他の数多くの汎用または専用のコンピューティングシステム、環境、または構成とともに動作可能である。使用に適する可能性のあるよく知られているコンピューティングシステム、環境、および／または構成の例としては、パーソナルコンピュータ、サーバコンピュータ、マルチプロセッサシステム、マイクロプロセッサベースのシステム、ネットワークＰＣ、ミニコンピュータ、メインフレームコンピュータ、以上のシステムまたは装置のいずれかを含む分散コンピューティング環境などがあるが、これに限定されるものではない。このフレームワークのコンパクト版またはサブセット版を、ハンドヘルドコンピュータなどのリソースの限られたクライアント、またはその他のコンピューティング装置において実装することもできる。本発明は、タスクが、通信ネットワークを介してリンクされるリモート処理装置によって実行される、分散コンピューティング環境において実施することもできる。分散コンピューティング環境では、プログラムモジュールは、ローカルとリモートのどちらの記憶装置内にあってもよい。
【００４３】
図３を参照すると、ＳＩＭＤ処理を用いた楕円曲線点８倍化の例示的なシステムは、例えば、図１のシステム１００を実装するコンピュータ３１０の形の汎用コンピューティング装置を含む。コンピュータ３１０の以下で説明する諸態様は、図１のコンピューティング装置１０２および／または１０４の例示的な実装形態である。コンピュータ３１０の構成要素は、処理ユニット３２０、システムメモリ３３０、および、システムメモリを含む様々なシステム構成要素を処理ユニット３２０へと結合するシステムバス３２１を含むことができるが、これに限定されるものではない。システムバス３２１は、様々なバスアーキテクチャのうちのいずれかを用いた、メモリバスまたはメモリコントローラ、周辺バス、およびローカルバスを含むいくつかのタイプのバス構造のうちの任意のものとすることができる。限定ではなく例として、そのようなアーキテクチャは、ＩＳＡ（Industry Standard Architecture）バス、ＭＣＡ（Micro-Channel Architecture）バス、ＥＩＳＡ（Enhanced ISA）バス、ＶＥＳＡ（Video Electronics Standards Association）ローカルバス、および、Ｍｅｚｚａｎｉｎｅバスとしても知られるＰＣＩ（Peripheral Component Interconnect）バスを含むことができる。
【００４４】
コンピュータ３１０は、通常、様々なコンピュータ読取り可能記憶媒体を含む。コンピュータ読取り可能記憶媒体は、コンピュータ３１０がアクセスできる任意の利用可能な媒体とすることもでき、揮発性および不揮発性の媒体、取外し可能および取外し不可能な媒体をいずれも含む。限定ではなく例として、コンピュータ読取り可能記憶媒体は、コンピュータストレージ媒体および通信媒体を含むことができる。コンピュータストレージ媒体は、コンピュータ読取り可能命令、データ構造、プログラムモジュール、またはその他のデータなど、情報を格納するための任意の方法または技術で実装される揮発性および不揮発性、取外し可能および取外不可能な媒体を含む。コンピュータストレージ媒体は、ＲＡＭ、ＲＯＭ、ＥＥＰＲＯＭ、フラッシュメモリ、または他のメモリ技術、ＣＤ−ＲＯＭ、ＤＶＤ、またはその他の光ディスクストレージ、磁気カセット、磁気テープ、磁気ディスクストレージ、またはその他の磁気ストレージ装置、あるいは所望の情報を格納するために使用でき、コンピュータ３１０がアクセスできるその他の任意の媒体も含むが、これに限定されるものではない。
【００４５】
通信媒体は、通常、コンピュータ読取り可能命令、データ構造、プログラムモジュール、またはその他のデータを、搬送波などの被変調データ信号またはその他の通信機構においおて実施し、任意の情報配信媒体も含む。「被変調データ信号」という用語は、その特徴の１つまたは複数が、情報をその信号の中にエンコードする形で設定または変更される信号を意味する。限定ではなく例として、通信媒体は、有線ネットワークや直接配線接続などの有線媒体、ならびに音響、ＲＦ、赤外線などの無線媒体およびその他の無線媒体を含む。また、上記の任意の組合せも、コンピュータ読取り可能記憶媒体の範囲内に含められる。
【００４６】
システムメモリ３３０は、ＲＯＭ（read only memory）３３１やＲＡＭ（random access memory）３３２などの揮発性および／または不揮発性の形のコンピュータストレージ媒体を含む。ＢＩＯＳ（基本入出力システム）３３３は、起動時などにコンピュータ３１０内部の要素間で情報を転送するのに役立つ基本ルーチンを含み、通常、ＲＯＭ３３１に格納されている。ＲＡＭ３３２は、通常、ＳＩＭＤ処理を実装する処理ユニット３２０が、直ちにアクセス可能なかつ／または現在動作の対象としている、データおよび／またはプログラムモジュールを含む。一実装形態では、プロセッサ３２０は、６４ビット浮動小数点数値をサポートする１組のＳＩＭＤ命令を備えている（例えば、ＳＩＭＤ  Ｅｘｔｅｎｓｉｏｎ（ＳＳＥ）Ｅｘｔｅｎｓｉｏｎｓ（ＳＳＥ２）アーキテクチャ）。限定ではなく例として、図３に、オペレーティングシステム３３４、アプリケーションプログラム３３５、その他のプログラムモジュール３３６、およびプログラムデータ３３７を示している。
【００４７】
また、コンピュータ３１０は、その他の取外し可能／取外し不可能な、揮発性／不揮発性のコンピュータストレージ媒体を含むことができる。単なる一例として、図３に、取外し不可能な不揮発性の磁気媒体からの読み取りまたはそれへの書き込みを行うハードディスクドライブ３４１、取外し可能な不揮発性の磁気ディスク３５２からの読み取りまたはそれへの書き込みを行う磁気ディスクドライブ３５１、および、ＣＤ  ＲＯＭまたはその他の光学メディアなどの取外し可能な不揮発性の光ディスク３５６からの読み取りまたはそれへの書き込みを行う光ディスクドライブ３５５を示している。例示的な動作環境において使用できるその他の取外し可能／取外し不可能な、揮発性／不揮発性のコンピュータストレージ媒体としては、磁気テープカセット、フラッシュメモリカード、ＤＶＤ（digital versatile disk）、デジタルビデオテープ、ソリッドステートＲＡＭ、ソリッドステートＲＯＭなどがあるが、これに限定されるものではない。ハードディスクドライブ３４１のシステムバス３２１への接続は、通常、インターフェース３４０などの取外し不可能なメモリインターフェースを介して行われ、磁気ディスクドライブ３５１および光ディスクドライブ３５５のシステムバス３２１への接続は、通常、インターフェース３５０などの取外し可能なメモリインターフェースによって行われる。
【００４８】
上述し図３に示したドライブおよびそれに関連するコンピュータストレージ媒体により、コンピュータ３１０用のコンピュータ読取り可能命令、データ構造、プログラムモジュール、およびその他のデータの記憶領域が提供される。図３では、例えば、ハードディスクドライブ３４１を、オペレーティングシステム３４４、アプリケーションプログラム３４５、その他のプログラムモジュール３４６、およびプログラムデータ３４７を格納するものとして示している。こうしたコンポーネントは、オペレーティングシステム３３４、アプリケーションプログラム３３５、その他のプログラムモジュール３３６、およびプログラムデータ３３７とは、同じものまたは異なるものとすることができることに注意されたい。アプリケーションプログラム３３５は、例えば、図１のコンピューティング装置１０２または１０４のプログラムモジュールを含む。プログラムデータ３３７は、例えば、図１のコンピューティング装置１０２または１０４のプログラムデータを含む。オペレーティングシステム３３４、アプリケーションプログラム３４５、その他のプログラムモジュール３４６、およびプログラムデータ３４７には、ここでは異なる符号を付して、これらが少なくとも異なるコピーであることを示している。
【００４９】
ユーザは、キーボード３６２、および、一般的に、マウス、トラックボール、またはタッチパッドと呼ばれるポインティングデバイス３６１などの入力装置を介して、コマンドまたは情報をコンピュータ３１０へ入力する。その他の入力装置（図示せず）には、マイクロフォン、ジョイスティック、ゲームパッド、衛星放送受信用アンテナ、スキャナなどがあげられる。こうしたおよびその他の入力装置は、しばしば、システムバス３２１へ結合されているユーザ入力インターフェース３６０を介して、処理ユニット３２０へ接続されるが、パラレルポート、ゲームポート、ＵＳＢ（universal serial bus）など、その他のインターフェースおよびバス構造によって接続することもできる。
【００５０】
モニタ３９１またはその他のタイプのディスプレイ装置も、システムバス３２１に、ビデオインターフェース３９０などのインターフェースを介して接続される。コンピュータは、このモニタのほかに、プリンタ３９６やオーディオ装置３９７など、その他の出力周辺装置を含むこともでき、それらは出力周辺インターフェース３９５を介して接続することができる。
【００５１】
コンピュータ３１０は、リモートコンピュータ３８０などの１つまたは複数のリモートコンピュータへの論理接続を用いてネットワーク化された環境において動作する。一実装形態では、リモートコンピュータ３８０は、図１のコンピューティング装置１０２またはネットワーク化されたコンピュータ１０４に相当する。リモートコンピュータ３８０は、パーソナルコンピュータ、サーバ、ルータ、ネットワークＰＣ、ピア装置、または他の一般的なネットワークノードとすることができ、その特定の実装形態の一機能として、コンピュータ３１０に関して上述した要素の多くまたはすべてを含むことができるが、図３にはメモリストレージ装置３８１だけを示している。図３に示す論理接続は、ＬＡＮ（local area network）３７１、ＷＡＮ（wide area network）３７３を含むが、その他のネットワークも含むことができる。そのようなネットワーキング環境は、オフィス、企業規模のコンピュータネットワーク、イントラネット、およびインターネットでは一般的なものである。
【００５２】
コンピュータ３１０は、ＬＡＮネットワーキング環境において使用する場合には、ＬＡＮ３７１に、ネットワークインターフェースまたはアダプタ３７０を介して接続される。コンピュータ３１０は、ＷＡＮネットワーキング環境において使用する場合には、通常、モデム３７２、または、インターネットなどのＷＡＮ３７３を介して通信を確立するためのその他の手段を含む。モデム３７２は、内蔵でも外付けでもよく、ユーザ入力インターフェース３６０またはその他の適切な機構を介してシステムバス３２１へ接続される。ネットワーク化された環境では、コンピュータ３１０に関して示したプログラムモジュールまたはその部分は、リモートのメモリストレージ装置に格納することができる。限定ではなく例として、図３に、リモートアプリケーションプログラム３８５を、メモリ装置３８１上に常駐するものとして示している。ここに示すネットワーク接続は例示的なものであり、コンピュータ間に通信リンクを確立するその他の手段を使用してもよい。
【００５３】
（まとめ）
ＳＩＭＤ処理を用いた楕円曲線点８倍化のためのシステムおよび方法を、構造的な特徴および／または方法の（methodological）操作またはアクションに特有の言葉で説明してきたが、添付の特許請求の範囲で定義される実装形態は、説明した特定の特徴またはアクションに必ずしも限定されるわけではないことが理解されよう。例えば、署名／暗号化モジュール１１０（図１）および検証／復号モジュール１２２（図１）を、それぞれ異なるコンピューティング装置（すなわち、装置１０２および１０４）上に示しているが、別の実装形態では、これらのプログラムモジュールに関連する論理を単一のコンピューティング装置１０２上に実装することができる。このため、システム１００の特定の特徴および操作を、特許請求の範囲に記載されている主題（subject matter）を実施する例示的な形式として開示している。
【図面の簡単な説明】
【００５４】
【図１】ＳＩＭＤ処理を用いた楕円曲線点８倍化のための例示的なシステムを示す図である。
【図２】ＳＩＭＤ処理を用いた楕円曲線点８倍化のための例示的な手順を示す図である。
【図３】ＳＩＭＤ処理を用いた楕円曲線点８倍化のためのシステムおよび方法を完全にまたは部分的に実施するための、適切なコンピューティング環境の例を示す図である。
【図１】
2006259735.tif 000014
【図２】
2006259735.tif 000015
【図３】
2006259735.tif 000016