"明細書に記載の方法。一般的には、本発明は楕円曲線上の点の対のスカラー倍の合計と、曲線上の第3の点の間の関係の相等性を検証するための方法と装置を提供する。本方法は、iビット長がスカラーより短く、その比がスカラーに対応する整数の対を取得するステップと、ii整数を、その関係のスカラーに代入して、項の少なくとも1つが、縮小ビット長の点の1つのスカラー倍である等価な関係を取得するステップと、iii相等性を検証する等価関係を計算するステップを備える。本方法は、楕円曲線上の点Rを表わす値が、他の2つの点uGとvQの合計に対応することを検証するために使用できる。整数wとzは、wとzを表わすビット列がそれぞれ、整数uのビット列よりも短くて、v=w/zmodnとなるように決定される。そのようなwとzにより、方程式R=uGvQが、-zRzumodnGwQ=Oとして検証できる。好ましくは、wとzのビット長は、それぞれnのビット長の約半分であり、それはwとzの両者が、約n1/2より大きくはないことを意味する。点-zRzumodnGwQは、zとwが相対的に小さい整数なので効率よく計算でき、合計をその部分よりも高速に計算する種々の方法が使用できる。倍数zumodnは全サイズであるが、ECDSAのようなアルゴリズムの状況において、点Gは固定または繰り返えして起きてよい。この場合、計算は、Gに対して格納された表を使用することにより促進できる。Gに対する表による従来の検証に比較して、このアプローチによる時間の節約は、約40である。wとzの値は、部分完成拡張ユークリッドアルゴリズム計算を使用して取得できる。または、連分数アプローチを利用してwとzを効率よく取得することができる。本発明の更なる形態においては、定義された最大ビット長のビット列により表現される元を有する有限体の群における暗号演算により行われるメッセージのデジタル署名を検証する方法が提供される。署名は、成分の対を備え、その1つは、署名者の一時的公開鍵から導出され、他の1つは、メッセージと、第1成分と、一時的公開鍵と、署名者の長期公開鍵を結合する。本方法は、一時的公開鍵を第1成分から取り出して、検証の相等性を、一時的公開鍵と、長期公開鍵と、定義された最大ビット長よりも短い縮小ビット長を有するビット列により表わされるオペランドを含む群演算の少なくとも1つを有する群の生成子に対する群演算の結合として確立するステップと、その結合を計算して、相等性が成立すればその署名を容認し、相等性が成立しない場合はその署名を拒絶するステップを備える。好ましくは、群は楕円曲線群である。更なる形態として、メッセージの署名を、有限体の楕円曲線群において暗号演算により生成する方法があり、一時的公開鍵を表わす点から導出された成分の1つを有する署名成分の対を生成し、1つの成分から取り出すことができる公開鍵の複数の可能な値の1つを特定する指標を署名中に含むステップを備える。例えば、本発明は以下の項目を提供する。項目1楕円曲線上の点対のスカラー倍の合計と、上記曲線上の第3点の間の関係の相等性を検証する方法であって、i上記スカラーの1つよりも短く、その比は上記スカラーに相当するビット長の整数対を取得するステップと、ii上記整数を、上記関係における上記スカラーに代入して、上記項の少なくとも1つが、縮小ビット長の上記点の1つのスカラー倍である等価関係を取得するステップと、iii上記等価関係を計算して、上記相等性を検証するステップと、を含む方法。項目2一対の上記項は、縮小ビット長を有する項目1に記載の方法。項目3上記整数の他の1つは、上記第3点を修正して、縮小ビット長のスカラー倍を与える項目2に記載の方法。項目4上記等価関係の更なる項は、それぞれが縮小長のビット列により表現され、その1つは、固定値を有し、他の1つは可変である点の対に分離される項目3に記載の方法。項目5固定値の上記点の上記1つは、繰返しの使用のために前計算されて格納される項目4に記載の方法。項目6上記整数は、等しいビット長を有する項目3に記載の方法。項目7上記整数は、異なるビット長を有する項目3に記載の方法。項目8上記相等性は、上記点の合計を群の単位元に等しいと置き、少なくとも一対の上記点に対して、同時加算を行うことで検証される項目3に記載の方法。項目9少なくとも上記一対の点の加算計算は、同時倍加算アルゴリズムを使用して行われる項目8に記載の方法。項目10上記点は、上記点の1つが固定で上記点の他が可変で、上記可変の点は縮小ビット長の上記整数に関連付けられているシステムにおいて使用される項目3に記載の方法。項目11上記固定点のスカラー倍の少なくとも一部分は前計算される項目10に記載の方法。項目12上記固定点の上記スカラー倍は一対の点に分割され、上記点の1つは前計算される項目11に記載の方法。項目13上記点のそれぞれのスカラー倍は合計され、結果は相等性の検証のために群の単位元と比較される項目12に記載の方法。項目14上記整数は、必要なビット長の整数が得られたとき中断される反復アルゴリズムを使用して取得される項目1に記載の方法。項目15上記アルゴリズムは拡張ユークリッドアルゴリズムである項目14に記載の方法。項目16定義された最大ビット長のビット列により表現される元を有する有限体の群における暗号演算により行われる、メッセージのデジタル署名を検証する方法であって、上記署名は、一対の成分を備え、対の1つは署名者の一時的公開鍵から導出され、対の他方は、上記メッセージと、上記第1成分と上記署名者の上記一時的公開鍵および長期公開鍵とを結合し、上記方法は、上記第1成分から上記一時的公開鍵を取り出すステップと、検証の相等性を、上記一時的公開鍵と、上記長期公開鍵と、上記群の生成子に対する群演算の結合として確立するステップであって、上記群演算の少なくとも1つは、上記定義された最大ビット長より短い縮小ビット長を有するビット列により表現されるオペランドを含むステップと、上記結合を計算して、上記相等性が成立すれば上記署名を承認し、上記相等性が成立しないときは上記署名を拒絶するステップを備える方法。項目17縮小ビット長の上記群演算は、上記一時的公開鍵に対して行われる項目16に記載の方法。項目18上記一時的公開鍵と上記長期公開鍵に対する群演算はそれぞれ、縮小ビット長のオペランドを含む項目17に記載の方法。項目19上記群は楕円曲線群であり、群演算の上記結合は、上記曲線上の点のスカラー倍の合計である項目16に記載の方法。項目20上記検証の相等性は、-zR=zumodnGwQの形式であり、ここにおいて、Rは一時的公開鍵であり、Gは群の生成子でありQは長期公開鍵であり、nはそれぞれ群の位数であり、z、wはt<nのビット長を有する整数であり、uは上記署名成分から導出された整数であり、Oは群の単位元である、項目19に記載の方法。項目21上記第1署名成分r=x’は、kが一時的私的鍵であるときの、一時的公開鍵kGから導出された整数であり、上記第2署名成分はs=k-1HM=dr/であり、ここにおいて、HMは上記メッセージのセキュアハッシュ関数であり、dは上記署名者の長期私的鍵であり、上記整数uはHM/smodnに対応する項目20に記載の方法。項目22上記署名成分は、v-r/smodnおよびv=w/zmodnであるときの関係uGvQ=Rを満たす項目21に記載の方法。項目23上記整数w、zは、wとzのビット長が所定の値のときに中断される反復アルゴリズムの適用により得られる項目22に記載の方法。項目24上記所定ビット長は等しい項目23に記載の方法。項目25Gの前計算された値は、上記線形結合の計算中に利用される項目20に記載の方法。項目26同時倍加算演算は、上記線形結合の計算中に行われる項目25に記載の方法。項目27上記生成子から導出された上記点は、一対の点に分割され、上記点は前計算される項目27に記載の方法。項目282iGの値の表は計算され、上記表からの値は上記計算で使用される項目25に記載の方法。項目29上記点の共線性は、上記相等性の正当性を判定するためにテストされる項目19に記載の方法。項目30上記署名は、上記一時的公開鍵の複数の可能な値の1つを特定するための指標を含む項目19に記載の方法。項目31有限体の楕円曲線群における暗号演算によりメッセージの署名を生成する方法であって、署名成分の対であって、上記成分の1つは一時的公開鍵を表現する点から導出される上記署名成分対を生成するステップと、上記1つの成分から取り出すことができる上記公開鍵の複数の可能な値の1つを特定するための指標を上記署名中に含めるステップを備える方法。項目32上記指標は、上記一時的公開鍵を表現する上記点の座標の1ビットである項目31に記載の方法。項目33楕円曲線暗号システムにおいて暗号演算を使用して得られるメッセージのデジタル署名であって、署名者の一時的公開鍵を表現する点から導出された第1成分と、上記第1成分から取り出すことができる上記公開鍵の複数の値の1つを特定するための指標を含む署名。項目34上記指標は、上記点の座標の1ビットである項目33に記載の署名。項目35楕円曲線暗号システムにおいて暗号演算を使用して得られるメッセージのデジタル署名を生成する方法であって、一時的公開鍵を表現する点を生成するステップと、上記点の座標が前もって調整された基準を満たしているかどうかを判定するステップと、上記基準が満たされないときは上記点の使用を禁止するステップを備える方法。項目36上記点は、上記前もって調整された基準が満たされないときは修正される項目35に記載の方法。項目37上記基準は、上記点の上記座標の第1ビットの値である項目36に記載の方法。項目38上記点は、上記基準が満たされないときは拒絶され、更なる点が生成される項目35に記載の方法。本発明は、デジタル署名、特にECDSAを使用して生成されるそれらの署名の検証を参照して例示される。しかし、説明される技術は、楕円曲線上の点を表わす値の対の検証が楕円曲線群以外の群に要求される他のアルゴリズムにも適用可能であることは明白である。従って、好適な実施の形態に付随する説明は例としてであり、それですべてということではない。ここで、図1を参照すると、データ通信システム10は、送信線16により相互接続されている通信設備12、14の対を含む。通信設備12、14はそれぞれ、暗号モジュール20、22を含み、それぞれのモジュールは、多数の暗号機能の1つを実践することができる。モジュール20、22はそれぞれ、通信設備12、14に組み込まれたCPUにより制御され、キーボード24のような入力装置、スクリーンのような表示装置26、およびメモリ28の間のインタフェースを取る。各暗号モジュールは、乱数発生器30と、点の加算のような楕円曲線計算を行うための演算プロセッサ32を含む、内部処理機能を有する。通信設備12、14は、ネットワーク内で接続された汎用コンピュータまたは、携帯電話や、ページャー、PDAなどのような特殊化された装置であることは理解されよう。通信リンク16は、地上線またはワイヤレス、またはそれらの組合せであってよい。同様に、暗号モジュール20、22は、別個のモジュールとして設けられてもよく、またはCPU内のアプリケーションとして組み込まれてもよい。本例においては、通信設備12は、モジュール20、22内で具現化される楕円曲線暗号システムを使用して、署名して通信設備14に送りたいと所望しているメッセージMを準備する。システムのパラメータは、曲線が定義された体本例においては、pが素数の場合のFpと、基盤となる曲線Eと、暗号演算が行われる群を形成する元を生成し、従って群の位数nと、一般的には、米国連邦情報処理標準規格FederalInformationProcessingStandardFIPS180-2で定義されたセキュアハッシュアルゴリズムSecureHashAlgorithmSHA-1やSHA-256のようなの1つであるハッシュ関数Hを含み、当事者それぞれに知られている。各元は、群における各元を表現するために十分な長さの最大ビット長を有するビット列として表現される。メッセージに署名するために取るステップは、図2に示されている。従って、最初は、通信設備は、乱数発生器30により整数kを生成し、演算装置32を利用して、座標x,yを有する点R=kGを計算する。通信設備12は、座標xを整数x’に変換して、署名の第1成分であるr=x’modnを計算する。通信設備12はまた、整数e=HMmodnを計算し、ここでHはセキュアハッシュ関数である。最終的に、第2成分sは、s=edr/kmodnとして計算される。成分rとsに加えて、署名は、点Rを表現する座標を成分rから取り出すための情報iを含む。この情報は、メッセージMに埋め込まれており、またはrとsと共に、別の成分として転送され、検証者が値Rを計算するために使用される。楕円曲線が素数の位数pの体F上で定義されていて、楕円曲線Eは巡回的、または素数の位数nであるときは、iは一般的には、ymod2、つまり、ゼロまたは1の値を取る。iの表示は、Rの取り出し中に必要であり、ここで検証者は、x=rと設定する。nとpは典型的な実践においては非常に接近しているので、x=rは大いに可能性がある。xが与えられると、x,yが曲線上にあるように正確に2つの値yがあり、これらの2つの値yとy’は、2を法とする、異なる値を有する。このようにiは、その値がどちらのyが使用されるかを示す単一ビットであり、署名には相対的にほとんど負担をかけない。メッセージがいったん署名されると、そのメッセージは成分r、s、およびiと共にリンク16上を、受け入れ側の通信設備14に転送される。署名を検証するために、図3で説明したステップが行われる。最初に、通信設備14は、整数e=HMmodnを計算する。そして通信設備は、演算装置32を利用して、整数uとvの対を、u=e/smodnおよびv=r/smodnとなるように計算する。通信設備14はまた、wとzの最大ビット長が、それぞれ群の元の最大ビット長よりも短く、v=w/xmodnとなるように、反復アルゴリズムを使用して整数wとzの対を計算する。wとzのビット長は、好ましくは、元のビット長の約半分である。そのようなwとzは、拡張ユークリッドアルゴリズムにより都合よく見出すことができ、適切な点、典型的には、wとvが元のビット長の半分である中間で停止する。そのようなアルゴリズムは、例えば、ISBNコードが0-387-95273の、スプリンゲルSpringerにより発行された、ヘンカーソンHenkerson、メネチェスMenezes、およびバンストーンVanstoneによる楕円曲線暗号へのガイドGuidetoEllipticCurveCryptographyにおける、量kをk=k1k2λmodnと表現し、ここにおいてk1とk2のビット長はnの長さの約半分であるようなアルゴリズムAlgorithm3.74として例示される。この方程式は、λ=k-k1/k2modnとして書き直せる。k=1およびλ=vと設定することで、上記に言及したアルゴリズムAlgorithm3.74は、システムのために確立されたnを取得するために使用でき、kは1に設定され、vの値は可変入力として使用される。取得された出力k1k2は、w=1-k1を計算するために使用でき、k2はw=1-k1およびz=k2として使用される。このように、演算装置32は、下記の擬似コードを実践してwとzの値を取得するために使用される。r0=nおよびt0=0とする。r1=vおよびt1=1とする。i>1に対して、ri、tiを下記のように決定する。除法アルゴリズムを使用して、riを定義するr_i-1=qir_i-2riと書く。ti=t_i-1qit_i-2とする。ri<sqrtn=n^1/2、または他の所望サイズのとき即座に停止する。w=riおよびz=tiと設定する。ri=tivmodnであるので、w=zvmodn、かつ、v=w/zmodn、およびwとzの両者は、所望のように、nのビット長の約半分を有することに留意されたい。通信設備14はまた、情報iを利用して点Rに対応する値を取り出す。その最も簡単な形式においては、これは曲線内で受け取ったrの値を代入し、yの2つの可能な値のうちどちらがビットiにより示された符号と対応するかを判定することにより取得される。取り出されたRの値により、ECDSAの検証、つまり、R=uGvQが、改訂された検証により、検証相等性-zRzumodnGwQ=Oであることを確認することにより行われる。検証相等性-zRzumodnGwQは、一時的公開鍵R、生成子G、および長期公開鍵Qのそれぞれに対する群演算の結合を含み、zとwが相対的に小さな整数なので効率よく計算できる。下記に説明されるように、その部分よりも合計をより迅速に計算する種々の方法が使用できる。倍数zumodnは全サイズであるが、点が変化する寿命を有するECDSAのようなシステムの状況にあり、点Gは固定または繰り返すものと見なしてよい。この場合、計算は、Gに対して前計算された表により促進され、メモリ28に格納され、必要なときに演算装置32によりアクセスされる。効率よく前計算することができない点-zRとwQの表現は、より小さなビット長を有し、そのため、計算に消費される時間はより少ない。計算が値Qを返すとすれば、署名は検証されたとされる。必要な関係を計算するために多数の異なる既知の技術が利用でき、それぞれの技術は、演算プロセッサ32を使用して実践できる。それぞれの技術は、速度または計算リソースにおいて異なる利点を有し、そのため技術または技術の組合せは、ある程度は、通信システムが作動する環境に依存することになる。比較のため、uとvはビット長tの整数であると仮定する。uGとvQを別々に計算することは、約3t/2点の演算を必要とし、前計算を仮定しない場合は、合計約3t点の演算を必要とすることになる。uGvQを計算することは、ECDSAに対して通常使用される検証であるが、t回の倍算を必要とし、そのうちのいくつかは、同時に行える。uとvのそれぞれは、その二進法表現において1に設定される、約t/2ビットを有すると予想される。基本二進法スカラー乗法においては、1の各ビットは、別の加算を必要とする。より高度なスカラー乗法においては、符号付き二進数展開が使用され、加算の平均数はt/3となる。従って点演算の合計数は、同時倍算がt回の倍算を節約するので、平均してt2t/2=2tとなる。改訂された検証は、別の形式aGwQzRの結合の計算を使用し、ここにおいてaは、zumodnの値を示すビット長tの整数であり、wとzは、ビット長が約t/2の整数である。このようにして検証計算をまとめると、点演算の数を削減するための多数の効率的な技術の使用が可能になる。これを計算する効率的な方法は、同時倍算と加算を使用することである。例えば、関係15G20Q13Rが計算される場合は、合計12回の点演算に対して、2Q、G2Q、G2QR、2G4Q2R、3G4Q2R、3G5Q2R、3G5Q3R、6G10Q6R、7G10G6R、14G20Q12R、15G20Q13Rとしての段階で行うことができ、各項に対して別々に一般スカラー乗法を行う方法よりも少ない。この方法がより少ない演算を使用する主な場合は、G2QRから2G4G2Rへ移行するときのようなステップにおいて同時倍算を行うときである。各項を別々に計算する場合は、この1回の演算に対応して、3回の演算が使用される。実際、3回同時倍算が使用されると、それぞれが2回の演算を節約し、このようにして同時倍算がすべての節約を正確に反映することになる。結合を計算する倍算の数は、最大倍数の長さにより支配されるので、それはtである。aに対する加算数は、平均してt/2であり、QとRに対しては、平均してそれぞれt/4である。合計は、平均して、tt/2t/4t/4=2tである。このアルゴリズムは、上記に詳述した楕円曲線暗号へのガイドGuidetoEllipticCurveCryptographyのアルゴリズムAlgorithm3.48として更に例示する。以前の方法においては、これもまた2t回の点演算を行うが、節約量はまったく現れず、実際には、ECDSAに対して、生成子Gが定数であるという事実の利点を生かせる。これにより、点J=2^mGを予め計算し、将来の使用のためにメモリ28に格納しておくことが可能になる。mが約t/2として選択されると、a≡a’a’’2^mであり、ここにおいてa’とa’’はビット長約t/2の整数である。従って、aGwQzRはa’Ga’’JwQzRとして書ける。この形式では、すべてのスカラー倍は、ビット長t/2を有する。倍算の合計数は、このようにt/2となる。4項のそれぞれは、平均してt/4の加算に貢献する。点演算の合計数は、平均して、t/24t/4=3t/2である。従って、図4に図示されているように、署名r、sを検証するためには、受け手は、上述のようにwとzを計算して、a’とa’’の値を決定して、倍加算アルゴリズムを行って、検証表現の値を取得する。これが群の単位元に対応するときは、検証は確認されたことになる。従来のuGvQを計算する検証方程式アプローチでは、倍数vは、一般的に全長tであり、前計算されたGの倍数Jは、同時倍算の数を減少することには貢献しない。従って、単一点Jを前計算して格納し、関係-zRzumodnGwQ=Oを使用して検証することにより、ECDSA署名を25少ない時間で検証することが可能になる。つまり、上述した実施形態を使用して、所与の時間内に33多くの署名を検証できる。または、多くの実践においては、基本的にGの2つの倍数のすべての冪乗を前計算して格納するのに十分なメモリ32を有しており、Gに対して倍算演算を行う必要が基本的にない。そのような状況においては、uGvQはQのt回の倍算と、GとQのそれぞれに対してt/2回の加算で計算できる。合計は依然として2t回の演算である。しかし、図5に示されるように、aGの値は、メモリ32に格納されている前計算表から検索でき、それによりaGwQzRの計算は、wQとzRに対してt/2回の倍算、Gに対しては倍算なし、Gに対してはt/2回の加算、そしてQとRのそれぞれに対しては、t/4回の加算で達成できる。合計では3t/2回の演算である。節約量は、Gの1つの倍数のみが前計算されて格納されたときの、図4で説明したものと同じである。符号付き二進数展開が使用されるときは、uGvQの計算いかなる前計算もなしは、約t回の倍算と、GとQのそれぞれに対してt/3回の加算、つまり、平均して合計10/6回の演算を必要とする。符号付き二進数展開が、a’Ga’’JwQzRを求めるために使用されると、約t/2回の倍算が必要となり、G、J、Q、およびRのそれぞれに対してt/6回の加算が必要になり、平均して、合計7/6t回の演算が必要となる。上述の検証表現を使用しての検証に要する時間は、使用しないときに比べて70、つまり30少ない。これにより、所与の時間内においては、約42多い署名を検証できる。改訂された検証表現を使用しての検証の利点は、符号付き二進数展開と称されるスカラー乗法のより高度な技術と組み合わせられると増大する。この技術は、今日では、楕円曲線暗号に非常に一般的に使用されており、従って、今日存在する実践は、検証表現の採用により恩恵を受ける可能性が高い。従って、検証方程式を再編成して署名変数が縮小ビット長を有するようにすることにより、検証の速度は相当に増大する。上記の実施形態においては、受け手は、成分r、sについての計算を行う。図6に示されるように、署名検証を更に促進するために、署名者は、公開鍵Qの前計算倍数を検証者に提供するようにしてもよい。検証者は前計算された倍数を使用して、Qの検証を更に促進することができる。この実施形態においては、検証者は、aRbGcQ=Oの形式であって、ここでaは約n1/3で-zを表現し、bは約nで-zumodnを表現し、cは約n2/3でwを表現しているECDSA検証方程式と等価な方程式を判定する。これは、上述したように、拡張ユークリッドアルゴリズムを使用して行うことができ、wのビット長がzの2倍になったときに停止する。従って、ここで再び、署名者はメッセージMに署名し、署名成分r、sを生成する。署名はまた、検証者に転送されるメッセージ中に識別子iを含む。署名者は、倍数βQを前計算し、ここにおいてスカラー倍βは、n1/3に最も近い2の冪乗であり、それを署名付きで転送する。検証者が受け取ると、wとzを計算する。検証者は、c=c’c’’βおよびb=b’b’’βb’’’β^2であると判定する。更に、Gが固定パラメータなので、検証者は、βGとβ^2Gの形式のGの倍数を前計算している。nがほぼ2^tのときは、検証者は、aRbGcQを計算するためにわずかt/3回の同時倍算しか必要としない。検証は、aRb’b’’βb’’’β^2Gc’c’’βQ=0に基づいて進行できる。GとQに対する前計算された値を使用することができ、検証を行うことができる。検証者は、符号付きNAFがa、b、およびcを表現するために使用されたと仮定すると、2t/3回の点加算を必要とする。点演算の合計数はこのようにtであり、それは本発明を使用し、図4で説明されたようなQの前計算された倍数なしの3t/2と、従来の表現を使用して、Qのいかなる前計算された倍数なしの2tと比較して更に相当な節約量を示している。QとGの両者の前計算された倍数があると、uGvQは、従来の表現を使用して、t/24t/4=3t/2回の点演算で計算できる。Qの前計算された倍数が実現可能なときは、上記の形式の署名方程式は、再び相当な利点を与えてくれる。上記の解析は、符号付き二進数展開が使用されるときは少し修正される。点の線形結合を計算する、更に他の既知の高度な技術そのいくつかを下記で検討するがを使用すれば、関係を使用することにより、最大40少ない時間で署名の検証が行える。スカラー乗法および結合を実践するときは、ある倍数の起動中に表を作成することが一般的である。これらの表により、スカラー倍の表現における符号付きビットは、ふつうはウィンドウと称される群において処理が可能になる。表は作成するためには時間とメモリというコストが必要だが、計算の残りの部分を促進する。通常は、表のサイズと、関連するウィンドウは、全体の性能に対して最適化され、それは普通は、メモリがより重要であるハードウェアの実践を除いては、必要な時間を最小化することを意味する。そのような技術に対する完全な説明と実践アルゴリズムは、上記に言及した楕円曲線暗号へのガイドGuidetoEllipticCurveCryptograpyの98頁とそれ以降で見出すことができる。スカラー乗法のためのそのような起動時の表は、または、ウィンドウ化技術は、上述した実施形態における改訂検証方程式と組み合わせることができる。そのような表を使用するときは、節約量は上記に概観を示したものとほぼ同じである。節約量が類似している理由は下記の単純な事実による。表は、繰返し起こる可能性のある加算のあるパターンを前計算することにより加算の数を削減するが、改訂検証関係を使用すると、より多くの同時倍算を提供することにより倍算数を削減する。実際、表を使用すると、加算数は減少し、改訂検証関係を使用することによる倍算の更なる削減は更に大きな影響を与える。例として、表への一般的なアプローチは、サイズ5の符号付きNAFウィンドウを使用することである。そのようなNAFの表を構築するには11回の加算が必要である。署名者がQの前計算された倍数uQを送る上記の例では、検証者は、33回の加算で、R、QおよびuQの表を構築できる。検証者は、G用に構築された必要な表を既に所有していることが仮定されている。前計算された倍算を使用すると、検証者は、検証のためにわずかt/6回の同時加算が必要となるだけである。これらの節約量は、鍵のサイズが大きくなるにつれて向上する。今日使用されている最大の鍵サイズに対しては、節約量はほぼ40である。そのような表は当然ながら必要なメモリ32を必要とするので、適切な技術の選択は利用できるハードウェアに依存することになる。同様に、結合疎形式jointsparseformsとして知られている計算技術を計算効率のために使用することができる。上述したように、整数w、zは、拡張ユークリッドアルゴリズムを使用して求めた。または、連分数アプローチを含む反復アルゴリズムを使用することもできる。基本的に、拡張ユークリッドアルゴリズムと等価である連分数アプローチにおいては、分数v/nへ部分収束するγ/δを、δがほぼn1/2になるように求める。部分収束の特性は|γ/δ-v/n|<1/δ^2である。この不等式にδnを乗算すると、|γn-vδ|<n/δとなり、ほぼn1/2となる。ここでz=δおよびw=γn-vδを設定する。v=w/zmodnであることを調べるのは容易であり、wとzが所望のサイズを有していることに留意されたい。上記に示したように、従来のECDSA署名は、点Rを含まず、その代わりにr=xmodnから得られた整数x’を含み、ここにおいてR=x,yである。従って、検証者はRを取り出す必要がある。上述したRを取り出す方法は、署名r、sを追加情報iで補足することである。この情報は、例えば、メッセージに埋め込むことができる。検証者は、rとiを使用してRを計算できる。p>nのときは、x’>nとなる可能性は無視できる程度であり、従って、r=x-nである。しかし、そのようなことが起きると、検証の試みは失敗する。有効な署名に対するそのような無視できる程度の失敗率は容認でき、または下記の方法で対処できる。図7に示すように、検証が失敗すると、検証者の負担で検証者はx=rnを試み、Rの別の値に対して検証を繰り返すことができ、それはこの特別な場合には成功する。検証に連続して失敗すると、署名の拒絶という結果になる。または、図8に示すように、署名者は、無視できる程度にしか起こらないが、いつx>nとなるかを検出することができ、これが起きたときには、異なるkとRを生成することができる。アプローチのいずれにおいても、問題はめったにしか起きないので、性能に対する影響は無視できる。Rを判定する他の技術も利用できる。非巡回的曲線において、余因子hがあり、それは、実際には、普通2または4である。これはxの複数の可能な値となる。r=xの確率は、ほぼ1/hである。他の状況においては、一般的にはr=x-nh=2ならば、またはより一般的には、r=x-mnでありここでmは0とh-1の間である。pはほぼhnなので、無視できる部分を除いて、rに関連しているxの可能な値がh個あることになる。xを取り出すために、従ってRをより容易に取り出すために、署名者は、mを計算して、それを、メッセージ内、あるいは更なる署名成分として検証者に送ることができる。または検証者は、mを経験に基づいて推測できる。これはh=2の場合に例示することができる。rに対応するのは、正しいxと偽の値xfである。偽の値xfは、E上でx座標の値に対応しないという可能性はほぼ1/2であり、更に、Gの倍数に対応しないという可能性は1/hである。xに対する2つの値のうちの1つが有効でない場合は、Eにないということにより、またはそれが位数nを有していなければ、その両者は効率よく調べられ、その値は削除できる。このように、少なくとも3/4の時間で検証者は正しいxを容易に求めることができる。残りの最大1/4の時間で、検証者は、2つのxの値のいずれを試みるべきかを知ることができない。半分の時間で検証者が検証すべきxの値の1つを推測できるならばこの推測は正しくて、署名は検証されるが、残りの半分の時間で、第1署名の試みは失敗し、検証者は他のxの値を試みなければならない。従って、検証者が2つの署名を検証しなければならない確率は1/8である。2つの検証のこの確率にもかかわらず、平均検証は依然として改善される。これは、依然として平均して、検証者に時間のより多くの節約量を提供できる。促進された検証が、通常の検証の70で済むが、検証の12.5が促進された検証の2倍の時間がかかれば、平均時間は通常の検証の79ということになる。更に、下記に概要を示すが、署名者はmを検証者に提供することにより、またはたった1つのmしか有効でないことを確実にするために両者の値を試みる余分な作業を行うことにより支援することができる。類似の方法を、余因子h=4で利用できる。実際、hの値が大きいと、可能性のあるxの値のそれぞれが有効である確率が低くなる。より多くの可能性のあるxの値があるが、解析によると、検証者に対して同様な利点があることが示される。3個のxの偽の値があり、それぞれは高速チェックでは有効に見える確率は1/8である。このため、偽の値が、高速チェックで有効なxと見えない可能性は7/83であり、約77である。残りの23の時間のほとんどは、xの偽の値が1つだけ有効に見え、全署名検証を必要とする可能性がある。i必要であればmもを含むことは、rを、x座標とy座標の第1ビットから構成されるRの圧縮バージョンと置き換えることに非常に類似している。このように、rの代わりにRの圧縮値を送ることは、ある程度はより簡単で、偽の値を取り出す可能性は無視できるという利点がある。従って、図9に示されるように、署名は計算されて成分r’、sの対を提供し、メッセージMと共に受け手14に転送される。成分r’はRのx座標とy座標の第1ビットから構成される。成分sは以前と同様に計算される。署名を検証するために、受け手14は、点Rを成分r’から直接取り出し、検証相等性方程式-zRzumodnGwQ=Oを使用して、それが群の単位元に対応することを確認する。修正された座標r’の送信は、検証を簡単にするが、必要な帯域幅も増やすことになる。ある状況においては、署名者が余分なビットを送るために利用できるチャネルがない場合がある。例えば、既存の標準規格では、署名フォーマットとメッセージフォーマットの両者を厳格に制限して、送り手が追加情報を提供する余地がまったくないこともある。署名者と検証者は、それにも拘わらず、両者の実践を調整し、それにより、Rはrから取り出せる。これは、署名者が、図10に示すように、xの値が、予め準備された基準に準拠することを確実にすることにより調整できる。上記の表記によれば、署名者は、R=kG=x,yを通常のように計算し、上記の表記において、i=ymod2を計算する。i=1であれば、署名者は、kを-kmodnに変更し、それにより、Rは-R=x,-yに変わり、iは0に変わる。検証者が署名を受け取ると、検証者はi=0と仮定して、それにより署名を取り出す。iの値は、このように値0として無条件に伝えられ、署名者は、これを調整するためにほとんど無視できる程度の対価しか必要としない。同様に、非巡回的楕円曲線においては、署名者は、mを無条件に送信しようとし、これはある程度は既に上述してある。h=2の場合は、時間の1/4であることを思い出せば、検証者は、2つの署名を検証する必要がある。検証者がこの余分な作業を行う代わりに、署名者は、この1/4の場合を検出でき、その代わりにkとRに対する別の値を試み、基準に準拠するものが1つ見つかるまでこのプロセスを繰り返す。検証者は、2つの署名を検証する必要なくいずれのxを使用するかを決定することができる。上述したようなRを修正することの代替として、およびECDSA標準規格に厳格に準拠することを維持するために、sの値は、Rではなく、計算の後に修正してもよい。この場合、署名者はRの値は前もって調整された基準に準拠しないことに気付き、通常のように、rとsを生成するように進行できる。sが計算された後、その値は-sに変更され、検証が、yの前もって調整された値を仮定して達成できることを確実にする。署名者が署名r,sを、Rが無条件に取り出されるように選択すると、通常の検証者は、署名を通常のように容認する。そのような署名は完全に有効である。つまり、改訂検証は、ECDSA検証の既存の実践と完全に互換性がある。無条件の効率的な署名を期待しているが、通常に生成された署名を受け取る促進された検証者は、iの2つの異なる値を試みる必要がある。促進された検証が、通常の検証の60の時間がかかるとすれば、巡回的曲線余因子h=1においては、通常の署名を検証するために必要な平均時間は、通常の検証の506050120=90である。これは通常の署名の時間の50はi=0を有し、たった1回だけの無条件の促進された検証を必要とし、他の50の時間は2回の促進された検証を必要とするからである。無条件に促進された検証は、署名が無条件に促進されなくても、通常の検証者よりも依然として速い。従来の署名もまた、署名者または第3者により修正できて、高速検証が可能になる。この場合は、署名は、要求者から第3者に転送され、この第3者が検証相等性を使用して署名を検証する。そうすることによりRの値が取り出される。署名は修正されて、指標Iを含み、要求者に戻される。修正された署名は、高速検証署名を期待している受け手との以降の交換に使用される。上記の技術はRを取り出して、関係-zRzumodnGwQ=Oを使用して改訂検証が可能になる。しかし、ECDSAが検証されるときは、整数wとzは、図11に示されるように、Rを取り出すことなしに使用できる。zRのx座標と、点wQzumodnGのx’座標を計算し、これら2つのx座標の相等性を調べることは可能である。Rのy座標を知らずに、zRのy座標を直接計算することは不可能なので、点zRのx座標のみが計算可能である。しかし、Rのy座標を必要とせずにRのx座標からzRのx座標を計算するいくつかの既知の方法がある。そのような技術には、上記に示した楕円曲線暗号へのガイドGuidetoEllipticCurveCryptographyの102頁に説明されているモントゴメリーMontgomeryの方法がある。そして、x座標の相等性は、wQzumodnGがzRまたは-zRに等しいことを意味し、それはw/zQuGがRまたは-Rに等しいことを意味し、それはuGvQがRと同じx座標を有することを意味するので、zRとwQzumodnGのx座標を調べれば十分である。これはECDSAを首尾よく検証するための条件である。Rのx座標は、上記に検討した方法を使用して署名成分rから取り出せる。このアプローチの利点は、y座標を取り出すために余分な作業を必要としないことである。上述した以前の方法に比べて不利な点は、zRをwQzumodnGとは別に計算しなくてはならないことであり、これは、結合和の節約量のある部分は達成されないことを意味する。上記の例では、通信設備12、14の対の間の署名を検証した。この技術は、図12に示されるように、楕円曲線鍵対d,Qの検証にも使用できる。鍵対を検証することは、Q=dGを調べることである。これは、改竄が行われていないことを保証するための安全条件のもとで第3者により鍵対が提供されるときに重要である。tがdのビット長であるときに、二進法の方法でのdGの計算は、平均して3t/2回の演算が必要となる。本実施形態では、通信設備12、14の1つは乱整数dを生成して、d=w/zmodnとなるように整数w、zの対を取得する。典型的には、整数w、zはそれぞれ長さdの半分である。そして通信設備はzQ-wGを計算し、結果が群の単位元0であることを調べる。zQ-wGの計算は、平均してt回の演算を必要とし、従って、50の節約量が得られる。これは、Gの前計算された倍数を格納するためのコストが高価である環境においては最も有利な方法である。メモリに制限がある別の環境では、前計算された倍数H=uGがあれば、dGがd’Gd’’Hとして計算され、ここにおいてd=d’d’’umodnであり、上記とほぼ同じコストがかかる。別の適用は、無条件の証明書の検証である。無条件の証明書は対P,Iであり、ここでPは楕円曲線点であり、Iはある単位元列である。エンティティであるボブBobは、楕円曲線点である要求値RをCAに送ることにより、無条件の証明書をCAから取得する。CAは、無条件の証明書P,Iを返し、更に、私的鍵再構築データ値sを返す。ボブBobは、sを使用して自分の私的鍵を計算する。より一般的には、いかなるエンティティもsを使用して無条件の証明書がボブBobの要求値RとCA公開鍵Cに正確に対応していることを検証できる。これは、検証相等性HP,IRsG=HP,IPCを調べることで行われ、ここにおいてHはハッシュ関数である。この方程式は、eQsG=Cと等価であり、ここにおいてe=HP,IおよびQ=R-Pである。この方程式の形式は標準規格ECDSA検証方程式の形式に非常に類似している。従って、上記で検討した技術は、この方程式の検証を促進する手段を提供するために使用できる。これは、e=w/zmodnとなるように、相対的に小さな値wとzを決定することにより最適に行われ、この方程式にzを乗算することにより、wQszmodnG-zC=Oが得られる。再び、この方程式のGの倍数は全サイズであるが、一般的にはGの倍数は前計算でき、従って、これは問題を引き起こさない。この技術の利点を利用する別の変形例では、ECDSA署名方程式の3つすべての倍数を短くする。理論的には、各倍数は、nの長さの2/3の長さまで短くできるnはGの位数。この短小化を達成するための1つの方法は、3次元における短ベクトル束問題を解くことである。そのような問題を解くためのアルゴリズムが存在する。3つすべての倍数を短くすることは、Gの前計算された倍数をいずれも格納することができない場合には非常に有益であり、Gの倍数の長さを可能な限り短くすることをより効率的にする。そのような技術は、アンリコーヘンHenriCohenの計算法代数的数論講座ACourseinComputationalAlgebraicNumberTheory,スプリンゲルSpringer、ISBN0-387-55640-0に更に完全に記載されている。第2.6節と2.6節はLLLアルゴリズムを記載しており、その適用は、束における短ベクトルを見出すことであり、また、3次元束のためのベーユValleeの特別アルゴリズムに言及している。この技術の別の適用は、部分メッセージ取り出しのピンチョフ-バンストーン署名Pintsov-VanstoneSignaturePVS方式の修正バージョンへの適用である。PVS署名はr,s,tの3つの組から構成される。署名の検証と、公開鍵Qのもとで署名からのメッセージの取り出しは、ベース生成子Gにより、下記のように行われる。検証者はe=Hr∥tを計算し、ここにおいてHはハッシュ関数である。そして検証者は、R=sGeQを計算する。次に、検証者はRから対称暗号鍵Kを導出する。これにより、検証者は、Kを使用してrを解読し、取り出されたメッセージ部分uを得る。取り出されたメッセージは、tとuのある結合である。署名はuがある冗長性を有していれば有効であり、この冗長性は、uがある所定のフォーマットに準じていることを検証することにより調べられる。PVS方式は、草案標準規格IEEEP1363aおよびANSIX9.92の一部である。PVSの修正変形例においては、検証時間は整数wとzを利用することにより削減できる。PVSの修正変形例は図13に示されており、下記のようにして進める。通常のようにeを計算した後、検証者は、wとzが、e=w/zmodnであり、点Gの位数であるnの長さの半分であることを見出す。そして検証者は、R=wsmodnGzQを計算して、以前のように手順を進めて、Rから鍵を導出し、その鍵でrを解読し、解読が正しい形式であることを検証する。検証のこの形式は、Qの倍数がより小さいのでより効率的である。楕円曲線群および類似の群におけるデジタル署名の署名検証を更に促進するための方法が下記のように例示される。ECDSA署名の検証は、基本的には、aRbQcGのような3個の楕円曲線点の線形結合が、無限大の点と等しいことを確認することと等価である。この条件を検証する1つの方法は、点aRbQcGを計算し、その結果が無限大における点O、つまり、上述したように、群の単位元であるかを調べる。この検証は、ときどき、全体の合計を直接計算するよりもより迅速に行えることがある。例えば、a=b=cならば、点R、Q、およびGが共線でありその場合に限ってaRbQcG=Oである。点が共線であるかを調べることは、楕円曲線点への加算よりも格段に速い。共線性は、方程式xR-xGyQ-yG-xQ-xGyR-yG=0により、わずか2回の体の乗算により調べることができる。点の加算は、少なくも2回の体の乗算、つまり体の平方および体の反転が必要であり、それは一般的には、約8回の体の乗算と等価である。a=b=cのときは、検証はこのように、点の加算にかかる時間の約18で可能である。このように、この技術は、これらの条件が存在する可能性があるときは、検証プロセスの準備ステップとして使用できる。同様に、b=c=0で、aR=Oの検証を所望するときは、原理的に、aR全体を計算する必要はない。その代わりに、点Rにおけるa番目の除算多項式を評価することができる。除算多項式は基本的には、点Rの座標の有理関数として表現されるときは、点aRの座標の分母に対する帰納的公式に対応する。分母が0でありその場合に限りaR=0であることが知られている。更に、b=c=0であり、楕円曲線群が素数の位数nで巡回的であれば、a=0modnまたはR=Oでありその場合に限りaR=Oであることが知られている。この検証は、零楕円曲線点演算が必要であるという点において比較的に即座に終了する。余因子が、h=2またはh=4のように小さいときは、点演算は、数回の非常に高速な体の演算により置き換えることができる。このように、合計の点がゼロであるような検証の特別な場合は、非常に速く行うことができる。除算多項式に対する帰納的公式に類似して、aRbQcGのような合計の分母に対する帰納的公式が存在し、これらは、点aRbQcGの全値を計算するよりもより高速に計算できる。群の位数nを知っていれば、検証時間を更に短縮できる。この技術の更なる適用は、図14に示されるように、ECDSAデジタル署名のみから、公開鍵Qを効率的に回復することである。1つの通信設備12が署名r,sでメッセージMに署名して、署名したメッセージを通信設備14に送りたいとする。通常は、通信設備14は、Mとr,sを通信設備に送り、しばしば公開鍵Qも送る。通信設備12がそれ自身の公開鍵を送らなかったとすると、通常は、通信設備14は、あるネットワークを介して、局所的にまたは遠隔的に格納できる、あるデータベースにおいて相手の通信設備の公開鍵を探そうとする。これを避けるために、署名から公開鍵Qを取り出せるということは有利である。通常のECDSA署名r,sが与えられれば、公開鍵である可能性があるいくつかの候補点Qを取り出すことができる。第1ステップは点Rを取り出すことである。署名に追加情報を含むことにより、署名されたメッセージに追加情報を含むことにより、1つの有効なRがrに対応できることを保証する署名者側の追加作業により、およびrに対応する多数の異なるR値を試みる検証者側の追加作業によるなど、促進された検証の状況においてRを見出すためのいくつかの方法が既に記載されてきた。これらの方法の1つによりいったんRが取り出されると、公開鍵Qは下記のようにして取り出すことができる。標準規格ECDSA検証方程式はR=e/sGr/sQであり、ここでe=HMはメッセージのハッシュ値である。Rとこの方程式が与えられれば、Qを求めることはQ=s/rR-e/rGにより行われる。しかし、かなりの確率で、対r,sはある有効公開鍵を生成し、通信設備14は、Qが通信設備12の公開鍵であるかを調べる方法が必要となる。通信設備12は、通信設備14の公開鍵についてのCAから、別のECDSA署名r’,s’のような署名を通信設備14が利用できるようにする。通信設備12は、CA署名r’,s’を通信設備14に送ることができ、または通信設備14はそれをあるデータベースで探すことができる。CAの署名は、通信設備12の名前と公開鍵Q上にある。通信設備14は、CAの証明書を使用して、公開鍵Qに対応するメッセージを検証する。署名が検証されれば、通信設備14は、公開鍵Qに対する正しい値を取り出したことになる。証明書から公開鍵を省略することは、帯域幅と格納領域を節約することになり、上述した検証プロセスは検証時間を短縮する。通信設備14はまた、Qのビットの半分のような、Qから導出されたよりコンパクトな値に対してQを調べることにより、Qが通信設備12の公開鍵であることを検証できる。Qのコンパクトバージョンは、この後格納され、またはQの代わりに通信され、ここで再び格納領域と帯域幅を節約することができる。検証相等性で使用される値のそれぞれが公開値であることも理解されるであろう。従って、検証者が利用できる計算能力に制限がある場合は、署名者はwとzの値を計算して、それをRと共にメッセージの一部として転送することができる。受け手は、Rを取り出す必要がなく、またwとzを計算する必要もなく、利用できる情報で検証を行うことができる。検証は促進されるが帯域幅は増大する。上記の記載は、楕円曲線群に対するものであったが、本発明で記載された多数の方法は、より一般的に暗号で使用される任意の群に適用でき、更に、群の元の冪乗を使用する他の適用も可能である。例えば、本発明は、最近、楕円曲線群の代替として提案されている、群がg種=2の超楕円曲線の場合に使用できる。上記の技術は、ECDSAに類似している、デジタル署名アルゴリズムDSA:DigitalSignatureAlgorithmの検証を促進するためにも使用できる。ECDSAと同様に、DSA署名は、整数r,sの対から構成され、rはDSA群の元Rから得られる。DSA群は、有限体の乗算群の部分群であると定義されている。しかし、ECDSAとは異なり、rからRを取り出すことは、数個の追加ビットの支援があっても達成するのが容易ではない。従って、本技術は、値がRで、署名されたメッセージの一部分として、または署名の追加部分として、または値rに対する置き換えとして送られるならば、最も容易にDSAに適用できる。典型的に、整数rは20バイトで表現されるが、値Rは128バイトで表現される。結果として、結合された署名とメッセージ長は、約108バイト長くなる。しかしこれは、検証を33促進するためには小さなコストである。DSA設定においては、pは大きな素数であり、qはより小さな素数であり、qはp-1の約数である。整数gは、g^q=1modp、および1<g<pとなるように選択される。qとgは、ECDSAからのnとGにそれぞれ対応することに注意。署名者の私的鍵は、ある整数xであり、公開鍵はY=g^xmodpである。署名者は署名を、通常のr,sの代わりにR,sの形式で生成する。ここで、R=g^kmodpであるが、r=Rmodqである。両者の場合において、s=k^-1hMxrmodqであり、ここでxは署名者の私的鍵であり、Mは署名されるメッセージであり、hはメッセージを要約するために使用されるハッシュ関数であるECDSAと同様。通常のDSAにおいて、検証者は、u=hM/smodqとv=r/smodqを計算することにより署名r,sを検証し、これはECDSA実施形態におけるuとvに非常に類似しており、そしてr=g^uY^vmodpmodqを調べる。本実施形態においては、検証者は、qの約半分の長さのビット長のwとzを見出し、それによりwとzのそれぞれは、v=w/zmodqとなるように、ほぼsqrtqとなる。これは、nをqと置き換えて、上記のECDSA実施形態と同じ方法で行われる。そして検証者は、R^zg^zumodqY^wmodpを計算する。この値が1に等しければ、検証者はその署名を容認し、そうでなければその署名は拒絶される。検証者は、平方乗算アルゴリズム、またはその変形例を使用してこの値を計算し、ECDSAにおける同時倍算に類似した同時平方を利用する。ECDSA高速検証の多数の方法がDSA高速検証に使用できる。gの前計算された倍数、例えばjを使用することができ、計算はR^zg^sj^tY^wmodpのようになり、ここで、z、s、t、およびwのそれぞれは、qの約半分のビット長を有する。公開鍵Yの前計算された冪乗が利用できるならば、冪の指数の長さは、更に短縮することができ、それにより倍算の数を少なくして検証をより高速にする。発明の実施形態は、添付された図面を参照して、例としての目的のみのためにここで説明される。"