デジタル署名と公開鍵の促進された検証
【課題】楕円曲線上の点の対のスカラー倍の合計と、曲線上の第３の点の間の関係の相等性を検証するための方法と装置を提供する。
【解決手段】有限体における群演算結合の促進された計算法が、オペランドの少なくとも１つが、相対的に小さなビット長を有するように調整することにより提供される。楕円曲線群においては、点Ｒを表現する値が、２つの別の点ｕＧとｖＱの合計に対応するかという検証は、縮小ビット長の整数ｗ、ｚを、ｖ＝ｗ／ｚとなるように導出することにより行われる。検証の相等性Ｒ＝ｕＧ＋ｖＱは、縮小ビット長のｚとｗを使用して、−ｚＲ＋（
ｕｚ ｍｏｄ ｎ）Ｇ＋ｗＱ＝Ｏとして計算される。これはデジタル署名検証において有利であり、検証数の拡大が達成される。
【解決手段】有限体における群演算結合の促進された計算法が、オペランドの少なくとも１つが、相対的に小さなビット長を有するように調整することにより提供される。楕円曲線群においては、点Ｒを表現する値が、２つの別の点ｕＧとｖＱの合計に対応するかという検証は、縮小ビット長の整数ｗ、ｚを、ｖ＝ｗ／ｚとなるように導出することにより行われる。検証の相等性Ｒ＝ｕＧ＋ｖＱは、縮小ビット長のｚとｗを使用して、−ｚＲ＋（
ｕｚ ｍｏｄ ｎ）Ｇ＋ｗＱ＝Ｏとして計算される。これはデジタル署名検証において有利であり、検証数の拡大が達成される。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、暗号アルゴリズムにおいて使用される計算法技術に関する。
【背景技術】
【０００２】
データ通信システムを通して伝達される情報の安全性とその情報が本物であることは、
最も重要なことである。情報の多くは、機密性があるため、適切な制御に欠けると、経済
的および個人的損失につながる可能性がある。暗号システムは、このような懸念に対処す
るために開発されてきた。
【０００３】
公開鍵暗号により、クーリエ（メッセンジャ）などのような独立した機構を通して情報
を交換する際に、他の通信相手に同一の鍵を送る必要がないデータ通信システム上での安
全な通信が可能になる。公開鍵暗号は、鍵対の生成に基づいており、その対の１つは私的
であり、他の１つは公開され、それらは一方向数学関数により関連付けられている。一方
向関数は、基盤となる数学的構造において、公開鍵は私的鍵から容易に計算できるが、私
的鍵は、公開鍵からは、現実的には突き止められないようになっている。
【０００４】
より強固な一方向関数の１つに、有限体における冪乗法があり、ここにおいて整数ｋは
私的鍵として使用され、体αの生成子は、公開鍵Ｋ＝αｋをもたらすために冪乗される。
αとＫが知られても、有限体の基盤となる数学的構造は、私的鍵ｋを取得することを現実
的に不可能にする。公開鍵暗号は、通信者間で使用され、両者の通信者がお互いの公開鍵
を交換して、相手の公開鍵を、自分の私的鍵で冪乗することにより共通鍵が確立される。
公開鍵暗号は、メッセージの発信元が本物であることを証明するためにデジタル的にメッ
セージに署名するためにも使用できる。メッセージを書いた人間は、自分の私的鍵を使用
してメッセージに署名し、メッセージが本物であることは対応する公開鍵を使用して検証
できる。
【０００５】
そのようなシステムの安全性は、基盤となる数学的構造に大きく依存している。離散対
数システムを実践するための、最も共通して使用される構造は、有限体の乗法群の巡回的
部分群であり、そこにおいては群演算は乗法であり、または楕円曲線群の巡回的部分群で
あり、そこにおいては群演算は加法である。
【０００６】
楕円曲線Ｅは、（ｘ，ｙ）の形式の点の集合であり、ｘとｙは、素数ｐを法とする整数
のような、一般的にはＦｐと称される数であり、体Ｆに属しており、ｘとｙは、Ｆにおけ
るあるａとｂに対して、ｙ２＝ｘ３＋ａｘ＋ｂの形式を取ることができる非特異３次方程
式を満たす。楕円曲線Ｅもまた、Ｏとして示される無限大における点を含む。Ｅの点は、
群を形成するように定義できる。点Ｏは、群の単位元であり、Ｅにおける任意の点Ｐに対
してＯ＋Ｐ＝Ｐ＋Ｏ＝Ｐが成り立つ。各点Ｐに対して、別の点があり、それを我々は−Ｐ
と書き、Ｐ＋（−Ｐ）＝Ｐ＋（−Ｐ）＝Ｏが成り立つ。Ｅにおける任意の３つの点Ｐ、Ｑ
、Ｒに対して、結合法則が成り立つ、つまり、Ｐ＋（Ｑ＋Ｒ）＝（Ｐ＋Ｑ）＋Ｒが成り立
つ。単位元、否定、および結合法則は、群を定義する３つの公理的性質である。楕円曲線
群は、それが可換、つまりＰ＋Ｑ＝Ｑ＋Ｐが成り立つという更なる性質も有する。
【０００７】
スカラー乗法は、下記のように加法から定義できる。任意の点Ｐと任意の正の整数ｄに
対して、ｄＰはＰ＋Ｐ＋．．．＋Ｐと定義され、ここにおいてＰはｄ回出現する。このよ
うにして、１Ｐ＝Ｐ、２Ｐ＝Ｐ＋Ｐ、そして３Ｐ＝Ｐ＋Ｐ＋Ｐなどとなる。我々はまた、
０Ｐ＝Ｏ、そして（−ｄ）Ｐ＝ｄ（−Ｐ）と定義する。
【０００８】
簡単のために、実際には、楕円曲線の巡回的部分群が代わりに使用されることがたまに
あるが、巡回的である楕円曲線（下記に定義される）を扱うことが好ましい。巡回的であ
るということは、生成元Ｇがあり、Ｇは、群におけるすべての他の点Ｐが、Ｇの倍数であ
る、つまり、ある正の整数ｄに対して、Ｐ＝ｄＧであるということである。ｎＧ＝Ｏとな
るような最小の正の整数ｎは、Ｇの（そして、Ｅが巡回的であるときの曲線Ｅの）位数で
ある。暗号への適用においては、楕円曲線はｎが素数になるように選択される。
【０００９】
楕円曲線暗号システムにおいては、冪乗に類似するものは点の乗算である。このように
、私的鍵は整数ｋであり、対応する公開鍵は点ｋＰであり、ここにおいてＰは、システム
パラメータの一部であり、曲線上の予め定義された点である。シード（種子）点Ｐは典型
的には生成子Ｇである。鍵対は、種々の暗号アルゴリズムで使用され、暗号化に対する共
通鍵を確立し、デジタル署名を実行する。そのようなアルゴリズムは、値のセット間の定
義された関係（検証相等性とも称せられる）を確認するために、値の対を比較することに
よる、ある演算による検証をしばしば必要とする。
【００１０】
そのようなアルゴリズムの１つは、エンティティ間で交換されるメッセージ上にデジタ
ル署名を生成するために使用される楕円曲線デジタル署名アルゴリズム（ＥＣＤＳＡ：Ｅ
ｌｌｉｐｔｉｃ Ｃｕｒｖｅ Ｄｉｇｉｔａｌ Ｓｉｇｎａｔｕｒｅ Ａｌｇｏｒｉｔｈ
ｍ）である。ＥＣＤＳＡを使用するエンティティは２つの役割、つまり、署名者と検証者
の役割を有する。署名者は、１とｎ−１間の両端を含める範囲の整数である長期私的鍵ｄ
を選択する。整数ｄは秘密でなければならず、そのため、一般的にはｄをランダムに選択
することが好ましい。署名者は、Ｑ＝ｄＧを計算する。点Ｑは、署名者の長期公開鍵であ
り、検証者が入手できるようになっている。一般的に、検証者は、Ｑが署名者であるエン
ティティに対応することを、ＣＡからの証明書により一般的には確証を得る。公開鍵Ｑか
ら私的鍵ｄを見出すことは、今日使用されている楕円曲線の選択に対して手に負えない問
題であると信じられている。
【００１１】
任意のメッセージＭに対して、署名者は、署名を作成でき、その署名は、ＥＣＤＳＡの
場合は、整数（ｒ，ｓ）の対である。検証者はいずれもメッセージＭと、公開鍵Ｑと、署
名（ｒ，ｓ）を受け取ることができ、それが対応する署名者により作成されたものかどう
かを検証できる。これは、有効な署名（ｒ，ｓ）の作成は、公開鍵Ｑに対応する私的鍵ｄ
を知っているエンティティによってのみ可能であると信じられているからである。
【００１２】
署名プロセスは下記の通りである。まず、署名者は、範囲［１，ｎ−１］におけるある
整数ｋを選択し、それは、セッション、または一時的な私的鍵として使用される。値ｋは
秘密でなくてはならず、そのため、好ましくはｋをランダムに選択する。そして、署名者
は、座標（ｘ，ｙ）を有する点Ｒ＝ｋＧを計算する。次に、署名者は、ｘを整数ｘ’に変
換して、ｒ＝ｘ’ｍｏｄ ｎ、つまり署名者の第１座標を計算する。署名者はまた、整数
ｅ＝ｈ（Ｍ）ｍｏｄ ｎも計算しなければならず、ここでｈはあるハッシュ関数であり、
一般的には、米国連邦情報処理標準規格（Ｆｅｄｅｒａｌ Ｉｎｆｏｒｍａｔｉｏｎ Ｐ
ｒｏｃｅｓｓｉｎｇ Ｓｔａｎｄａｒｄ（ＦＩＰＳ））１８０−２で定義されたＳｅｃｕ
ｒｅ Ｈａｓｈ Ａｌｇｏｒｉｔｈｍｓ（ＳＨＡ−１またはＳＨＡ−２５６のような）の
１つである。最後に、第２座標ｓはｓ＝（ｅ＋ｄｒ）／ｓ ｍｏｄ ｎとして計算される
。成分（ｒ，ｓ）は、署名者によりメッセージＭの署名として使用され、メッセージと共
に意図された受信者に送られる。
【００１３】
検証プロセスは下記の通りである。まず、検証者は、整数ｅ＝ｈ（Ｍ） ｍｏｄ ｎを
受信したメッセージから計算する。そして検証者は、ｕ＝ｅ／ｓ ｍｏｄ ｎおよびｖ＝
ｒ／ｓ ｍｏｄ ｎとなるような整数ｕとｖを計算する。次に、検証者は、ｕＧ＋ｖＱを
加算することにより得られた点Ｒに対応する値を計算する。これは座標（ｘ，ｙ）を有す
る。最後に、検証者は、体の元ｘを整数ｘ’に変換して、ｒ＝ｘ’ｍｏｄ ｎであるかを
調べる。そうであれば、署名は検証されたことになる。
【００１４】
上記から、ＥＣＤＳＡ署名の検証は、ＥＣＤＳＡ署名の作成の２倍の時間がかかるよう
に見える。これは、検証プロセスは２回のスカラー乗法、つまり、ｕＧとｖＱを含むが、
署名は１回のみのスカラー乗法、つまりｋＧを含むからである。楕円曲線スカラー乗法は
、これらのプロセスのほとんどの時間を消費しており、その２倍が本質的には計算時間を
２倍にする。ｕＧとｖＱを別々に計算するよりも時間をかけずにｕＧ＋ｖＱを計算する方
法が知られている。これらの方法のいくつかは、シャミール（Ｓｈａｍｉｒ）によるもの
であり、あるものはソリナス（Ｓｏｌｉｎａｓ）によるものであり、あるものは多様な人
々によるものである。一般的に、これらの方法は、ｕＧ＋ｖＱが、ｋＧを計算する時間の
１．５倍で済むことを意味している。
【００１５】
楕円曲線計算を促進するための、別の共通して使用される方法は、Ｇの倍数の前計算表
である。そのような前計算表は、点Ｇは一般的には、繰返し使用される固定システムパラ
メータであるので時間を節約できる。最も簡単な前計算表は、ｊが０からｔのときのすべ
ての倍数２＾ｊ Ｇから構成されており、ここでｔはｎのビット長である。そのような前
計算表があれば、任意の倍数ｋＧの計算は、ｔ／２の点の加算、またはそれより少ない点
の加算の平均で行われる。概略的に述べれば、これはｋＧの計算の基本的な方法に対して
３倍改善されたことを示しており、前計算の利点を明確に示している。一般的に述べれば
、前計算表が大きいほど、より良く時間的に改善される。前計算表を格納するために必要
なメモリは、非常に高価である。従って、改善は、より迅速な計算の利点と、より大きな
表にかかる余分なコストのバランスを取らなければならない。正確なバランスは、一般的
には、メモリ使用に対する速度の相対的な重要性に依存しており、それは実践方法により
異なる。
【００１６】
前計算はまた、公開鍵Ｑにも適用できる。一般的には、公開鍵Ｑは、Ｇよりもより頻繁
に変化する傾向にある。それは公開鍵Ｑが通信者それぞれに対して異なるが、Ｇは、所与
のシステムに対しては、固定だからである。従って、Ｑに対する１回の前計算のコストは
、より少ない回数のＱを含む繰返し起動時計算で償却される。それにも拘わらず、Ｑが２
回以上使用されると、時間のある程度の正味の節約が達成される。頻繁に使用される公開
鍵は、認証機関（ＣＡ）の公開鍵、特に、ルート、トラスト、およびアンカＣＡ公開鍵（
これらはシステムに予めインストールされる）を含む。従って、前計算は、例えば、プロ
トコルがＣＡの証明書の検証を要求するＣＡ楕円曲線公開鍵のような場合に対しては意味
がある。Ｇに対してのＱの前計算の間の別の差は、前計算表の格納または通信のコストで
ある。各公開鍵Ｑは、それ自身の前計算表を必要とする。多数の個別公開鍵のシステムに
おいて、これらのコストは、より迅速な計算のいかなる利点も、鍵を格納または通信する
コストにより相殺されてしまう程度に嵩むこともある。正味の利点は、実践およびシステ
ム間で非常に異なる時間と、メモリと、帯域幅の相対的コストに依存する。ここで再び、
ＣＡ公開鍵、特に、ルート、トラスト、およびアンカＣＡ鍵の場合は、これらの鍵の数は
、端末−エンティティの公開鍵よりも少ない傾向にあり、それにより、前計算のコストは
、一般的に少なく、より多くの演算により償却される。
【００１７】
点の倍数の表は、前計算の間でのみ有利であるだけでない。実際、そのような表は、各
計算の初期段階中の、起動時に共通して生成される。これらの表による節約は本質的には
、単一の計算内において発生するある繰返し演算を回避することによる節約である。単一
の計算は、２つの別個の計算が共通して有するよりもより少ない内部の繰返しを有し、そ
れにより節約された繰返し量は、前計算より少なくなる。それにも拘わらず、表の選択を
賢明に行えば、単一の計算に必要な時間を削減できることが分かってきている。表は計算
するのに時間がかかり、表の計算は複数の計算では償却できず、すべての計算に対しても
負担を被る。経験によると、特別な表の計算は、それがなければ必要となる繰返し計算よ
りも時間がかからないので、特別な表は、必要な時間を削減する。通常は、最適なサイズ
と最適な表の選択がある。そのような表の別のコストは、表を一時的に格納するために必
要なメモリである。そのようなメモリのコストは、最適な表の選択に影響を与える可能性
がある。ウィンドウ化法は、作動中に計算されるそのような表の例である。
【００１８】
効率的な実践に対する、上記の既知の技術のすべてにも拘わらず、更なる効率の改善が
望ましい。特に、ＥＣＤＳＡ署名の検証の効率は、特に望ましい。幅広い前計算は、ＥＣ
ＤＳＡ署名を迅速に生成することを可能にする。実際、ＥＣＤＳＡ署名生成は、既知の最
速デジタル署名生成アルゴリズムの１つである。一方、ＥＣＤＳＡ署名検証は、相対的に
より緩慢で、ＥＣＤＳＡと類似する検証時間を有する他の署名アルゴリズムがある。従っ
て、ＥＣＤＳＡ検証時間の改善は、特に検証時間が障害となっている環境においては重要
である。
【００１９】
一般的には、値が２つの値の合計に対応することを検証するために計算を行うときの効
率を高める必要性がある。従って、本発明の目的は、上記の不都合な点を除去あるいは緩
和することである。
【発明の概要】
【課題を解決するための手段】
【００２０】
一般的には、本発明は楕円曲線上の点の対のスカラー倍の合計と、曲線上の第３の点の
間の関係の相等性を検証するための方法と装置を提供する。本方法は、ｉ）ビット長がス
カラーより短く、その比がスカラーに対応する整数の対を取得するステップと、ｉｉ）整
数を、その関係のスカラーに代入して、項の少なくとも１つが、縮小ビット長の点の１つ
のスカラー倍である等価な関係を取得するステップと、ｉｉｉ）相等性を検証する等価関
係を計算するステップを備える。
【００２１】
本方法は、楕円曲線上の点Ｒを表わす値が、他の２つの点ｕＧとｖＱの合計に対応する
ことを検証するために使用できる。整数ｗとｚは、ｗとｚを表わすビット列がそれぞれ、
整数ｕのビット列よりも短くて、ｖ＝ｗ／ｚ ｍｏｄ ｎとなるように決定される。その
ようなｗとｚにより、方程式Ｒ＝ｕＧ＋ｖＱが、−ｚＲ＋（ｚｕ ｍｏｄ ｎ）Ｇ＋ｗＱ
＝Ｏとして検証できる。
【００２２】
好ましくは、ｗとｚのビット長は、それぞれｎのビット長の約半分であり、それはｗと
ｚの両者が、約ｎ１／２より大きくはないことを意味する。
【００２３】
点−ｚＲ＋（ｚｕ ｍｏｄ ｎ）Ｇ＋ｗＱは、ｚとｗが相対的に小さい整数なので効率
よく計算でき、合計をその部分よりも高速に計算する種々の方法が使用できる。倍数（ｚ
ｕ ｍｏｄ ｎ）は全サイズであるが、ＥＣＤＳＡのようなアルゴリズムの状況において
、点Ｇは固定または繰り返えして起きてよい。この場合、計算は、Ｇに対して格納された
表を使用することにより促進できる。Ｇに対する表による従来の検証に比較して、このア
プローチによる時間の節約は、約４０％である。
【００２４】
ｗとｚの値は、部分完成拡張ユークリッドアルゴリズム計算を使用して取得できる。ま
たは、連分数アプローチを利用してｗとｚを効率よく取得することができる。
【００２５】
本発明の更なる形態においては、定義された最大ビット長のビット列により表現される
元を有する有限体の群における暗号演算により行われるメッセージのデジタル署名を検証
する方法が提供される。署名は、成分の対を備え、その１つは、署名者の一時的公開鍵か
ら導出され、他の１つは、メッセージと、第１成分と、一時的公開鍵と、署名者の長期公
開鍵を結合する。本方法は、一時的公開鍵を第１成分から取り出して、検証の相等性を、
一時的公開鍵と、長期公開鍵と、定義された最大ビット長よりも短い縮小ビット長を有す
るビット列により表わされるオペランドを含む群演算の少なくとも１つを有する群の生成
子に対する群演算の結合として確立するステップと、その結合を計算して、相等性が成立
すればその署名を容認し、相等性が成立しない場合はその署名を拒絶するステップを備え
る。
好ましくは、群は楕円曲線群である。更なる形態として、メッセージの署名を、有限体
の楕円曲線群において暗号演算により生成する方法があり、一時的公開鍵を表わす点から
導出された成分の１つを有する署名成分の対を生成し、１つの成分から取り出すことがで
きる公開鍵の複数の可能な値の１つを特定する指標を署名中に含むステップを備える。
例えば、本発明は以下の項目を提供する。
（項目１）
楕円曲線上の点対のスカラー倍の合計と、前記曲線上の第３点の間の関係の相等性を検
証する方法であって、ｉ）前記スカラーの１つよりも短く、その比は前記スカラーに相当
するビット長の整数対を取得するステップと、ｉｉ）前記整数を、前記関係における前記
スカラーに代入して、前記項の少なくとも１つが、縮小ビット長の前記点の１つのスカラ
ー倍である等価関係を取得するステップと、ｉｉｉ）前記等価関係を計算して、前記相等
性を検証するステップと、を含む方法。
（項目２）
一対の前記項は、縮小ビット長を有する項目１に記載の方法。
（項目３）
前記整数の他の１つは、前記第３点を修正して、縮小ビット長のスカラー倍を与える請
求項２に記載の方法。
（項目４）
前記等価関係の更なる項は、それぞれが縮小長のビット列により表現され、その１つは
、固定値を有し、他の１つは可変である点の対に分離される項目３に記載の方法。
（項目５）
固定値の前記点の前記１つは、繰返しの使用のために前計算されて格納される項目４
に記載の方法。
（項目６）
前記整数は、等しいビット長を有する項目３に記載の方法。
（項目７）
前記整数は、異なるビット長を有する項目３に記載の方法。
（項目８）
前記相等性は、前記点の合計を群の単位元に等しいと置き、少なくとも一対の前記点に
対して、同時加算を行うことで検証される項目３に記載の方法。
（項目９）
少なくとも前記一対の点の加算計算は、同時倍加算アルゴリズムを使用して行われる請
求項８に記載の方法。
（項目１０）
前記点は、前記点の１つが固定で前記点の他が可変で、前記可変の点は縮小ビット長の
前記整数に関連付けられているシステムにおいて使用される項目３に記載の方法。
（項目１１）
前記固定点のスカラー倍の少なくとも一部分は前計算される項目１０に記載の方法。
（項目１２）
前記固定点の前記スカラー倍は一対の点に分割され、前記点の１つは前計算される請求
項１１に記載の方法。
（項目１３）
前記点のそれぞれのスカラー倍は合計され、結果は相等性の検証のために群の単位元と
比較される項目１２に記載の方法。
（項目１４）
前記整数は、必要なビット長の整数が得られたとき中断される反復アルゴリズムを使用
して取得される項目１に記載の方法。
（項目１５）
前記アルゴリズムは拡張ユークリッドアルゴリズムである項目１４に記載の方法。
（項目１６）
定義された最大ビット長のビット列により表現される元を有する有限体の群における暗
号演算により行われる、メッセージのデジタル署名を検証する方法であって、前記署名は
、一対の成分を備え、対の１つは署名者の一時的公開鍵から導出され、対の他方は、前記
メッセージと、前記第１成分と前記署名者の前記一時的公開鍵および長期公開鍵とを結合
し、前記方法は、前記第１成分から前記一時的公開鍵を取り出すステップと、検証の相等
性を、前記一時的公開鍵と、前記長期公開鍵と、前記群の生成子に対する群演算の結合と
して確立するステップであって、前記群演算の少なくとも１つは、前記定義された最大ビ
ット長より短い縮小ビット長を有するビット列により表現されるオペランドを含むステッ
プと、前記結合を計算して、前記相等性が成立すれば前記署名を承認し、前記相等性が成
立しないときは前記署名を拒絶するステップを備える方法。
（項目１７）
縮小ビット長の前記群演算は、前記一時的公開鍵に対して行われる項目１６に記載の
方法。
（項目１８）
前記一時的公開鍵と前記長期公開鍵に対する群演算はそれぞれ、縮小ビット長のオペラ
ンドを含む項目１７に記載の方法。
（項目１９）
前記群は楕円曲線群であり、群演算の前記結合は、前記曲線上の点のスカラー倍の合計
である項目１６に記載の方法。
（項目２０）
前記検証の相等性は、−ｚＲ＝（ｚｕ ｍｏｄ ｎ）Ｇ＋ｗＱの形式であり、ここにお
いて、
Ｒは一時的公開鍵であり、
Ｇは群の生成子であり
Ｑは長期公開鍵であり、
ｎはそれぞれ群の位数であり、
ｚ、ｗはｔ＜ｎのビット長を有する整数であり、
ｕは前記署名成分から導出された整数であり、
Ｏは群の単位元である、項目１９に記載の方法。
（項目２１）
前記第１署名成分ｒ＝ｘ’は、ｋが一時的私的鍵であるときの、一時的公開鍵ｋＧから
導出された整数であり、前記第２署名成分はｓ＝ｋ−１（Ｈ（Ｍ）＝ｄｒ）／であり、こ
こにおいて、Ｈ（Ｍ）は前記メッセージのセキュアハッシュ関数であり、ｄは前記署名者
の長期私的鍵であり、前記整数ｕはＨ（Ｍ）／ｓ ｍｏｄ ｎに対応する項目２０に記
載の方法。
（項目２２）
前記署名成分は、ｖ−ｒ／ｓ ｍｏｄ ｎおよびｖ＝ｗ／ｚ ｍｏｄ ｎであるときの
関係ｕＧ＋ｖＱ＝Ｒを満たす項目２１に記載の方法。
（項目２３）
前記整数ｗ、ｚは、ｗとｚのビット長が所定の値のときに中断される反復アルゴリズム
の適用により得られる項目２２に記載の方法。
（項目２４）
前記所定ビット長は等しい項目２３に記載の方法。
（項目２５）
Ｇの前計算された値は、前記線形結合の計算中に利用される項目２０に記載の方法。
（項目２６）
同時倍加算演算は、前記線形結合の計算中に行われる項目２５に記載の方法。
（項目２７）
前記生成子から導出された前記点は、一対の点に分割され、前記点は前計算される請求
項２７に記載の方法。
（項目２８）
２ｉＧの値の表は計算され、前記表からの値は前記計算で使用される項目２５に記載
の方法。
（項目２９）
前記点の共線性は、前記相等性の正当性を判定するためにテストされる項目１９に記
載の方法。
（項目３０）
前記署名は、前記一時的公開鍵の複数の可能な値の１つを特定するための指標を含む請
求項１９に記載の方法。
（項目３１）
有限体の楕円曲線群における暗号演算によりメッセージの署名を生成する方法であって
、署名成分の対であって、前記成分の１つは一時的公開鍵を表現する点から導出される前
記署名成分対を生成するステップと、前記１つの成分から取り出すことができる前記公開
鍵の複数の可能な値の１つを特定するための指標を前記署名中に含めるステップを備える
方法。
（項目３２）
前記指標は、前記一時的公開鍵を表現する前記点の座標の１ビットである項目３１に
記載の方法。
（項目３３）
楕円曲線暗号システムにおいて暗号演算を使用して得られるメッセージのデジタル署名
であって、署名者の一時的公開鍵を表現する点から導出された第１成分と、前記第１成分
から取り出すことができる前記公開鍵の複数の値の１つを特定するための指標を含む署名
。
（項目３４）
前記指標は、前記点の座標の１ビットである項目３３に記載の署名。
（項目３５）
楕円曲線暗号システムにおいて暗号演算を使用して得られるメッセージのデジタル署名
を生成する方法であって、一時的公開鍵を表現する点を生成するステップと、前記点の座
標が前もって調整された基準を満たしているかどうかを判定するステップと、前記基準が
満たされないときは前記点の使用を禁止するステップを備える方法。
（項目３６）
前記点は、前記前もって調整された基準が満たされないときは修正される項目３５に
記載の方法。
（項目３７）
前記基準は、前記点の前記座標の第１ビットの値である項目３６に記載の方法。
（項目３８）
前記点は、前記基準が満たされないときは拒絶され、更なる点が生成される項目３５
に記載の方法。
発明の実施形態は、添付された図面を参照して、例としての目的のみのためにここで説
明される。
【図面の簡単な説明】
【００２６】
【図１】データ通信システムの模式的表現である。
【図２】ＥＣＤＳＡ署名方式に対して署名を行う際のステップを示しているフローチャートである。
【図３】ＥＣＤＳＡ署名の検証を示すフローチャートである。
【図４】前計算された値を使用するＥＣＤＳＡ署名の検証を示すフローチャートである。
【図５】前計算された値の表を使用するＥＣＤＳＡ署名の検証を示すフローチャートである。
【図６】署名者により提供された前計算された値を使用するＥＣＤＳＡ署名の検証を示すフローチャートである。
【図７】検証に失敗した検証者が取るステップを示すフローチャートである。
【図８】検証を簡単にするために署名者が取るステップを示すフローチャートである。
【図９】検証を簡単にするための代替署名プロトコルを示すフローチャートである。
【図１０】検証を簡単にするために、署名者により行われる代替技術を示すフローチャートである。
【図１１】代替検証ＥＣＤＳＡを示すフローチャートである。
【図１２】点の検証を示すフローチャートである。
【図１３】修正されたＰＶＳ検証プロトコルを示すフローチャートである。
【図１４】ＥＣＤＳＡ署名から公開鍵を取り出す方法を示している。
【発明を実施するための形態】
【００２７】
本発明は、デジタル署名、特にＥＣＤＳＡを使用して生成されるそれらの署名の検証を
参照して例示される。しかし、説明される技術は、楕円曲線上の点を表わす値の対の検証
が楕円曲線群以外の群に要求される他のアルゴリズムにも適用可能であることは明白であ
る。従って、好適な実施の形態に付随する説明は例としてであり、それですべてというこ
とではない。
【００２８】
ここで、図１を参照すると、データ通信システム１０は、送信線１６により相互接続さ
れている通信設備１２、１４の対を含む。通信設備１２、１４はそれぞれ、暗号モジュー
ル２０、２２を含み、それぞれのモジュールは、多数の暗号機能の１つを実践することが
できる。モジュール２０、２２はそれぞれ、通信設備１２、１４に組み込まれたＣＰＵに
より制御され、キーボード２４のような入力装置、スクリーンのような表示装置２６、お
よびメモリ２８の間のインタフェースを取る。各暗号モジュールは、乱数発生器３０と、
点の加算のような楕円曲線計算を行うための演算プロセッサ３２を含む、内部処理機能を
有する。通信設備１２、１４は、ネットワーク内で接続された汎用コンピュータまたは、
携帯電話や、ページャー、ＰＤＡなどのような特殊化された装置であることは理解されよ
う。通信リンク１６は、地上線またはワイヤレス、またはそれらの組合せであってよい。
同様に、暗号モジュール２０、２２は、別個のモジュールとして設けられてもよく、また
はＣＰＵ内のアプリケーションとして組み込まれてもよい。
【００２９】
本例においては、通信設備１２は、モジュール２０、２２内で具現化される楕円曲線暗
号システムを使用して、署名して通信設備１４に送りたいと所望しているメッセージＭを
準備する。システムのパラメータは、曲線が定義された体（本例においては、ｐが素数の
場合のＦｐ）と、基盤となる曲線Ｅと、暗号演算が行われる群を形成する元を生成し、従
って群の位数ｎと、一般的には、米国連邦情報処理標準規格（Ｆｅｄｅｒａｌ Ｉｎｆｏ
ｒｍａｔｉｏｎ Ｐｒｏｃｅｓｓｉｎｇ Ｓｔａｎｄａｒｄ（ＦＩＰＳ））１８０−２で
定義されたセキュアハッシュアルゴリズム（Ｓｅｃｕｒｅ Ｈａｓｈ Ａｌｇｏｒｉｔｈ
ｍ）（ＳＨＡ−１やＳＨＡ−２５６のような）の１つであるハッシュ関数Ｈを含み、当事
者それぞれに知られている。各元は、群における各元を表現するために十分な長さの最大
ビット長を有するビット列として表現される。
【００３０】
メッセージに署名するために取るステップは、図２に示されている。従って、最初は、
通信設備は、乱数発生器３０により整数ｋを生成し、演算装置３２を利用して、座標（ｘ
，ｙ）を有する点Ｒ＝ｋＧを計算する。通信設備１２は、座標ｘを整数ｘ’に変換して、
署名の第１成分であるｒ＝ｘ’ ｍｏｄ ｎを計算する。通信設備１２はまた、整数ｅ＝
Ｈ（Ｍ）ｍｏｄ ｎを計算し、ここでＨはセキュアハッシュ関数である。最終的に、第２
成分ｓは、ｓ＝（ｅ＋ｄｒ）／ｋ ｍｏｄ ｎとして計算される。
【００３１】
成分ｒとｓに加えて、署名は、点Ｒを表現する座標を成分ｒから取り出すための情報ｉ
を含む。この情報は、メッセージＭに埋め込まれており、またはｒとｓと共に、別の成分
として転送され、検証者が値Ｒを計算するために使用される。楕円曲線が素数の位数ｐの
体Ｆ上で定義されていて、楕円曲線Ｅは巡回的、または素数の位数ｎであるときは、ｉは
一般的には、ｙ ｍｏｄ ２、つまり、ゼロまたは１の値を取る。ｉの表示は、Ｒの取り
出し中に必要であり、ここで検証者は、ｘ＝ｒと設定する。ｎとｐは典型的な実践におい
ては非常に接近しているので、ｘ＝ｒは大いに可能性がある。ｘが与えられると、（ｘ，
ｙ）が曲線上にあるように正確に２つの値ｙがあり、これらの２つの値ｙとｙ’は、２を
法とする、異なる値を有する。このようにｉは、その値がどちらのｙが使用されるかを示
す単一ビットであり、署名には相対的にほとんど負担をかけない。
【００３２】
メッセージがいったん署名されると、そのメッセージは成分ｒ、ｓ、およびｉと共にリ
ンク１６上を、受け入れ側の通信設備１４に転送される。署名を検証するために、図３で
説明したステップが行われる。最初に、通信設備１４は、整数ｅ＝Ｈ（Ｍ） ｍｏｄ ｎ
を計算する。そして通信設備は、演算装置３２を利用して、整数ｕとｖの対を、ｕ＝ｅ／
ｓ ｍｏｄ ｎおよびｖ＝ｒ／ｓ ｍｏｄ ｎとなるように計算する。
【００３３】
通信設備１４はまた、ｗとｚの最大ビット長が、それぞれ群の元の最大ビット長よりも
短く、ｖ＝ｗ／ｘ ｍｏｄ ｎとなるように、反復アルゴリズムを使用して整数ｗとｚの
対を計算する。ｗとｚのビット長は、好ましくは、元のビット長の約半分である。そのよ
うなｗとｚは、拡張ユークリッドアルゴリズムにより都合よく見出すことができ、適切な
点、典型的には、ｗとｖが元のビット長の半分である中間で停止する。そのようなアルゴ
リズムは、例えば、ＩＳＢＮコードが０−３８７−９５２７３の、スプリンゲル（Ｓｐｒ
ｉｎｇｅｒ）により発行された、ヘンカーソン（Ｈｅｎｋｅｒｓｏｎ）、メネチェス（Ｍ
ｅｎｅｚｅｓ）、およびバンストーン（Ｖａｎｓｔｏｎｅ）による「楕円曲線暗号へのガ
イド」（Ｇｕｉｄｅ ｔｏ Ｅｌｌｉｐｔｉｃ Ｃｕｒｖｅ Ｃｒｙｐｔｏｇｒａｐｈｙ
）における、量ｋをｋ＝ｋ１＋ｋ２λ ｍｏｄ ｎと表現し、ここにおいてｋ１とｋ２の
ビット長はｎの長さの約半分であるようなアルゴリズム（Ａｌｇｏｒｉｔｈｍ）３．７４
として例示される。この方程式は、λ＝（ｋ−ｋ１）／ｋ２ ｍｏｄ ｎとして書き直せ
る。ｋ＝１およびλ＝ｖと設定することで、上記に言及したアルゴリズム（Ａｌｇｏｒｉ
ｔｈｍ）３．７４は、システムのために確立されたｎを取得するために使用でき、ｋは１
に設定され、ｖの値は可変入力として使用される。取得された出力ｋ１ｋ２は、ｗ＝１−
ｋ１を計算するために使用でき、ｋ２はｗ＝１−ｋ１およびｚ＝ｋ２として使用される。
【００３４】
このように、演算装置３２は、下記の擬似コードを実践してｗとｚの値を取得するため
に使用される。
【００３５】
ｒ０＝ｎおよびｔ０＝０とする。
ｒ１＝ｖおよびｔ１＝１とする。
【００３６】
ｉ＞１に対して、ｒｉ、ｔｉを下記のように決定する。
【００３７】
除法アルゴリズムを使用して、ｒｉを定義するｒ＿（ｉ−１）＝ｑｉｒ＿（ｉ−２）＋
ｒｉと書く。
【００３８】
ｔｉ＝ｔ＿（ｉ−１）＋ｑｉｔ＿（ｉ−２）とする。
【００３９】
ｒｉ＜ｓｑｒｔ（ｎ）＝ｎ＾（１／２）、または他の所望サイズのとき即座に停止する
。
【００４０】
ｗ＝ｒｉおよびｚ＝ｔｉと設定する。ｒｉ＝ｔｉｖ ｍｏｄ ｎであるので、ｗ＝ｚｖ
ｍｏｄ ｎ、かつ、ｖ＝ｗ／ｚ ｍｏｄ ｎ、およびｗとｚの両者は、所望のように、
ｎのビット長の約半分を有することに留意されたい。
【００４１】
通信設備１４はまた、情報ｉを利用して点Ｒに対応する値を取り出す。その最も簡単な
形式においては、これは曲線内で受け取ったｒの値を代入し、ｙの２つの可能な値のうち
どちらがビットｉにより示された符号と対応するかを判定することにより取得される。
【００４２】
取り出されたＲの値により、ＥＣＤＳＡの検証、つまり、Ｒ＝ｕＧ＋ｖＱが、改訂され
た検証により、検証相等性−ｚＲ＋（ｚｕ ｍｏｄ ｎ）Ｇ＋ｗＱ＝Ｏであることを確認
することにより行われる。検証相等性−ｚＲ＋（ｚｕ ｍｏｄ ｎ）Ｇ＋ｗＱは、一時的
公開鍵Ｒ、生成子Ｇ、および長期公開鍵Ｑのそれぞれに対する群演算の結合を含み、ｚと
ｗが相対的に小さな整数なので効率よく計算できる。下記に説明されるように、その部分
よりも合計をより迅速に計算する種々の方法が使用できる。倍数（ｚｕ ｍｏｄ ｎ）は
全サイズであるが、点が変化する寿命を有するＥＣＤＳＡのようなシステムの状況にあり
、点Ｇは固定または繰り返すものと見なしてよい。この場合、計算は、Ｇに対して前計算
された表により促進され、メモリ２８に格納され、必要なときに演算装置３２によりアク
セスされる。効率よく前計算することができない点−ｚＲとｗＱの表現は、より小さなビ
ット長を有し、そのため、計算に消費される時間はより少ない。計算が値Ｑを返すとすれ
ば、署名は検証されたとされる。
【００４３】
必要な関係を計算するために多数の異なる既知の技術が利用でき、それぞれの技術は、
演算プロセッサ３２を使用して実践できる。それぞれの技術は、速度または計算リソース
において異なる利点を有し、そのため技術または技術の組合せは、ある程度は、通信シス
テムが作動する環境に依存することになる。比較のため、ｕとｖはビット長ｔの整数であ
ると仮定する。ｕＧとｖＱを別々に計算することは、約３ｔ／２点の演算を必要とし、前
計算を仮定しない場合は、合計約３ｔ点の演算を必要とすることになる。ｕＧ＋ｖＱを計
算することは、ＥＣＤＳＡに対して通常使用される検証であるが、ｔ回の倍算を必要とし
、そのうちのいくつかは、同時に行える。ｕとｖのそれぞれは、その二進法表現において
１に設定される、約ｔ／２ビットを有すると予想される。基本二進法スカラー乗法におい
ては、１の各ビットは、別の加算を必要とする。（より高度なスカラー乗法においては、
符号付き二進数展開が使用され、加算の平均数はｔ／３となる。従って点演算の合計数は
、同時倍算がｔ回の倍算を節約するので、平均してｔ＋（２（ｔ／２））＝２ｔとなる。
）
【００４４】
改訂された検証は、別の形式ａＧ＋ｗＱ＋ｚＲの結合の計算を使用し、ここにおいてａ
は、ｚｕ ｍｏｄ ｎの値を示すビット長ｔの整数であり、ｗとｚは、ビット長が約（ｔ
／２）の整数である。このようにして検証計算をまとめると、点演算の数を削減するため
の多数の効率的な技術の使用が可能になる。これを計算する効率的な方法は、同時倍算と
加算を使用することである。例えば、関係１５Ｇ＋２０Ｑ＋１３Ｒが計算される場合は、
合計１２回の点演算に対して、２Ｑ、Ｇ＋２Ｑ、Ｇ＋２Ｑ＋Ｒ、２Ｇ＋４Ｑ＋２Ｒ、３Ｇ
＋４Ｑ＋２Ｒ、３Ｇ＋５Ｑ＋２Ｒ、３Ｇ＋５Ｑ＋３Ｒ、６Ｇ＋１０Ｑ＋６Ｒ、７Ｇ＋１０
Ｇ＋６Ｒ、１４Ｇ＋２０Ｑ＋１２Ｒ、１５Ｇ＋２０Ｑ＋１３Ｒとしての段階で行うことが
でき、各項に対して別々に一般スカラー乗法を行う方法よりも少ない。この方法がより少
ない演算を使用する主な場合は、Ｇ＋２Ｑ＋Ｒから２Ｇ＋４Ｇ＋２Ｒへ移行するときのよ
うなステップにおいて同時倍算を行うときである。各項を別々に計算する場合は、この１
回の演算に対応して、３回の演算が使用される。実際、３回同時倍算が使用されると、そ
れぞれが２回の演算を節約し、このようにして同時倍算がすべての節約を正確に反映する
ことになる。結合を計算する倍算の数は、最大倍数の長さにより支配されるので、それは
ｔである。ａに対する加算数は、平均して（ｔ／２）であり、ＱとＲに対しては、平均し
てそれぞれ（ｔ／４）である。合計は、平均して、ｔ＋（ｔ／２）＋（ｔ／４）＋（ｔ／
４）＝２ｔである。このアルゴリズムは、上記に詳述した「楕円曲線暗号へのガイド」（
Ｇｕｉｄｅ ｔｏ Ｅｌｌｉｐｔｉｃ Ｃｕｒｖｅ Ｃｒｙｐｔｏｇｒａｐｈｙ）のアル
ゴリズム（Ａｌｇｏｒｉｔｈｍ）３．４８として更に例示する。
【００４５】
以前の方法においては、これもまた２ｔ回の点演算を行うが、節約量はまったく現れず
、実際には、ＥＣＤＳＡに対して、生成子Ｇが定数であるという事実の利点を生かせる。
これにより、点Ｊ＝２＾ｍＧを予め計算し、将来の使用のためにメモリ２８に格納してお
くことが可能になる。ｍが約ｔ／２として選択されると、ａ≡ａ’＋ａ’’２＾ｍであり
、ここにおいてａ’とａ’’はビット長約（ｔ／２）の整数である。従って、ａＧ＋ｗＱ
＋ｚＲはａ’Ｇ＋ａ’’Ｊ＋ｗＱ＋ｚＲとして書ける。この形式では、すべてのスカラー
倍は、ビット長（ｔ／２）を有する。倍算の合計数は、このように（ｔ／２）となる。４
項のそれぞれは、平均して（ｔ／４）の加算に貢献する。点演算の合計数は、平均して、
ｔ／２＋４（ｔ／４）＝３ｔ／２である。
【００４６】
従って、図４に図示されているように、署名ｒ、ｓを検証するためには、受け手は、上
述のようにｗとｚを計算して、ａ’とａ’’の値を決定して、倍加算アルゴリズムを行っ
て、検証表現の値を取得する。これが群の単位元に対応するときは、検証は確認されたこ
とになる。
【００４７】
従来のｕＧ＋ｖＱを計算する検証方程式アプローチでは、倍数ｖは、一般的に全長ｔで
あり、前計算されたＧの倍数Ｊは、同時倍算の数を減少することには貢献しない。
【００４８】
従って、単一点Ｊを前計算して格納し、関係−ｚＲ＋（ｚｕ ｍｏｄ ｎ）Ｇ＋ｗＱ＝
Ｏを使用して検証することにより、ＥＣＤＳＡ署名を２５％少ない時間で検証することが
可能になる。つまり、上述した実施形態を使用して、所与の時間内に３３％多くの署名を
検証できる。
【００４９】
または、多くの実践においては、基本的にＧの２つの倍数のすべての冪乗を前計算して
格納するのに十分なメモリ３２を有しており、Ｇに対して倍算演算を行う必要が基本的に
ない。そのような状況においては、ｕＧ＋ｖＱはＱのｔ回の倍算と、ＧとＱのそれぞれに
対して（ｔ／２）回の加算で計算できる。合計は依然として２ｔ回の演算である。しかし
、図５に示されるように、ａＧの値は、メモリ３２に格納されている前計算表から検索で
き、それによりａＧ＋ｗＱ＋ｚＲの計算は、ｗＱとｚＲに対して（ｔ／２）回の倍算、Ｇ
に対しては倍算なし、Ｇに対してはｔ／２回の加算、そしてＱとＲのそれぞれに対しては
、ｔ／４回の加算で達成できる。合計では３ｔ／２回の演算である。節約量は、Ｇの１つ
の倍数のみが前計算されて格納されたときの、図４で説明したものと同じである。
【００５０】
符号付き二進数展開が使用されるときは、ｕＧ＋ｖＱの計算（いかなる前計算もなし）
は、約ｔ回の倍算と、ＧとＱのそれぞれに対して（ｔ／３）回の加算、つまり、平均して
合計（１０／６）回の演算を必要とする。符号付き二進数展開が、ａ’Ｇ＋ａ’’Ｊ＋ｗ
Ｑ＋ｚＲを求めるために使用されると、約ｔ／２回の倍算が必要となり、Ｇ、Ｊ、Ｑ、お
よびＲのそれぞれに対して（ｔ／６）回の加算が必要になり、平均して、合計（７／６）
ｔ回の演算が必要となる。上述の検証表現を使用しての検証に要する時間は、使用しない
ときに比べて７０％、つまり３０％少ない。これにより、所与の時間内においては、約４
２％多い署名を検証できる。改訂された検証表現を使用しての検証の利点は、符号付き二
進数展開と称されるスカラー乗法のより高度な技術と組み合わせられると増大する。この
技術は、今日では、楕円曲線暗号に非常に一般的に使用されており、従って、今日存在す
る実践は、検証表現の採用により恩恵を受ける可能性が高い。
【００５１】
従って、検証方程式を再編成して署名変数が縮小ビット長を有するようにすることによ
り、検証の速度は相当に増大する。
【００５２】
上記の実施形態においては、受け手は、成分ｒ、ｓについての計算を行う。図６に示さ
れるように、署名検証を更に促進するために、署名者は、公開鍵Ｑの前計算倍数を検証者
に提供するようにしてもよい。検証者は前計算された倍数を使用して、Ｑの検証を更に促
進することができる。この実施形態においては、検証者は、ａＲ＋ｂＧ＋ｃＱ＝Ｏの形式
であって、ここでａは約ｎ１／３で−ｚを表現し、ｂは約ｎで−ｚｕ ｍｏｄ ｎを表現
し、ｃは約ｎ２／３でｗを表現しているＥＣＤＳＡ検証方程式と等価な方程式を判定する
。これは、上述したように、拡張ユークリッドアルゴリズムを使用して行うことができ、
ｗのビット長がｚの２倍になったときに停止する。従って、ここで再び、署名者はメッセ
ージＭに署名し、署名成分ｒ、ｓを生成する。署名はまた、検証者に転送されるメッセー
ジ中に識別子ｉを含む。署名者は、倍数βＱを前計算し、ここにおいてスカラー倍βは、
ｎ１／３に最も近い２の冪乗であり、それを署名付きで転送する。
【００５３】
検証者が受け取ると、ｗとｚを計算する。検証者は、ｃ＝ｃ’＋ｃ’’βおよびｂ＝ｂ
’＋ｂ’’β＋ｂ’’’β＾２であると判定する。更に、Ｇが固定パラメータなので、検
証者は、βＧとβ＾２Ｇの形式のＧの倍数を前計算している。ｎがほぼ２＾ｔのときは、
検証者は、ａＲ＋ｂＧ＋ｃＱを計算するためにわずかｔ／３回の同時倍算しか必要としな
い。検証は、ａＲ＋（ｂ’＋ｂ’’β＋ｂ’’’β＾２）Ｇ＋（ｃ’＋ｃ’’β）Ｑ＝０
に基づいて進行できる。ＧとＱに対する前計算された値を使用することができ、検証を行
うことができる。検証者は、符号付きＮＡＦがａ、ｂ、およびｃを表現するために使用さ
れたと仮定すると、２ｔ／３回の点加算を必要とする。点演算の合計数はこのようにｔで
あり、それは本発明を使用し、図４で説明されたようなＱの前計算された倍数なしの３ｔ
／２と、従来の表現を使用して、Ｑのいかなる前計算された倍数なしの２ｔと比較して更
に相当な節約量を示している。
【００５４】
ＱとＧの両者の前計算された倍数があると、ｕＧ＋ｖＱは、従来の表現を使用して、（
ｔ／２）＋４（ｔ／４）＝３ｔ／２回の点演算で計算できる。Ｑの前計算された倍数が実
現可能なときは、上記の形式の署名方程式は、再び相当な利点を与えてくれる。上記の解
析は、符号付き二進数展開が使用されるときは少し修正される。
【００５５】
点の線形結合を計算する、更に他の既知の高度な技術（そのいくつかを下記で検討する
が）を使用すれば、関係を使用することにより、最大４０％少ない時間で署名の検証が行
える。
【００５６】
スカラー乗法および結合を実践するときは、ある倍数の起動中に表を作成することが一
般的である。これらの表により、スカラー倍の表現における符号付きビットは、ふつうは
ウィンドウと称される群において処理が可能になる。表は作成するためには時間とメモリ
というコストが必要だが、計算の残りの部分を促進する。通常は、表のサイズと、関連す
るウィンドウは、全体の性能に対して最適化され、それは普通は、メモリがより重要であ
るハードウェアの実践を除いては、必要な時間を最小化することを意味する。そのような
技術に対する完全な説明と実践アルゴリズムは、上記に言及した「楕円曲線暗号へのガイ
ド」（Ｇｕｉｄｅ ｔｏ Ｅｌｌｉｐｔｉｃ Ｃｕｒｖｅ Ｃｒｙｐｔｏｇｒａｐｙ）の
９８頁とそれ以降で見出すことができる。
【００５７】
スカラー乗法のためのそのような起動時の表は、または、ウィンドウ化技術は、上述し
た実施形態における改訂検証方程式と組み合わせることができる。そのような表を使用す
るときは、節約量は上記に概観を示したものとほぼ同じである。節約量が類似している理
由は下記の単純な事実による。表は、繰返し起こる可能性のある加算のあるパターンを前
計算することにより加算の数を削減するが、改訂検証関係を使用すると、より多くの同時
倍算を提供することにより倍算数を削減する。実際、表を使用すると、加算数は減少し、
改訂検証関係を使用することによる倍算の更なる削減は更に大きな影響を与える。
【００５８】
例として、表への一般的なアプローチは、サイズ５の符号付きＮＡＦウィンドウを使用
することである。そのようなＮＡＦの表を構築するには１１回の加算が必要である。署名
者がＱの前計算された倍数ｕＱを送る上記の例では、検証者は、３３回の加算で、Ｒ、Ｑ
およびｕＱの表を構築できる。検証者は、Ｇ用に構築された必要な表を既に所有している
ことが仮定されている。前計算された倍算を使用すると、検証者は、検証のためにわずか
ｔ／６回の同時加算が必要となるだけである。これらの節約量は、鍵のサイズが大きくな
るにつれて向上する。今日使用されている最大の鍵サイズに対しては、節約量はほぼ４０
％である。そのような表は当然ながら必要なメモリ３２を必要とするので、適切な技術の
選択は利用できるハードウェアに依存することになる。
【００５９】
同様に、結合疎形式（ｊｏｉｎｔ ｓｐａｒｓｅ ｆｏｒｍｓ）として知られている計
算技術を計算効率のために使用することができる。
【００６０】
上述したように、整数ｗ、ｚは、拡張ユークリッドアルゴリズムを使用して求めた。ま
たは、連分数アプローチを含む反復アルゴリズムを使用することもできる。基本的に、拡
張ユークリッドアルゴリズムと等価である連分数アプローチにおいては、分数ｖ／ｎへ部
分収束するγ／δを、δがほぼｎ１／２になるように求める。部分収束の特性は｜γ／δ
−ｖ／ｎ｜＜１／δ＾２である。この不等式にδｎを乗算すると、｜γｎ−ｖδ｜＜ｎ／
δとなり、ほぼｎ１／２となる。ここでｚ＝δおよびｗ＝γｎ−ｖδを設定する。ｖ＝ｗ
／ｚ ｍｏｄ ｎであることを調べるのは容易であり、ｗとｚが所望のサイズを有してい
ることに留意されたい。
【００６１】
上記に示したように、従来のＥＣＤＳＡ署名は、点Ｒを含まず、その代わりにｒ＝ｘ
ｍｏｄ ｎから得られた整数ｘ’を含み、ここにおいてＲ＝（ｘ，ｙ）である。従って、
検証者はＲを取り出す必要がある。
【００６２】
上述したＲを取り出す方法は、署名（ｒ、ｓ）を追加情報ｉで補足することである。こ
の情報は、例えば、メッセージに埋め込むことができる。検証者は、ｒとｉを使用してＲ
を計算できる。ｐ＞ｎのときは、ｘ’＞ｎとなる可能性は無視できる程度であり、従って
、ｒ＝ｘ−ｎである。しかし、そのようなことが起きると、検証の試みは失敗する。有効
な署名に対するそのような無視できる程度の失敗率は容認でき、または下記の方法で対処
できる。
【００６３】
図７に示すように、検証が失敗すると、検証者の負担で検証者はｘ＝ｒ＋ｎを試み、Ｒ
の別の値に対して検証を繰り返すことができ、それはこの特別な場合には成功する。検証
に連続して失敗すると、署名の拒絶という結果になる。または、図８に示すように、署名
者は、無視できる程度にしか起こらないが、いつｘ＞ｎとなるかを検出することができ、
これが起きたときには、異なるｋとＲを生成することができる。アプローチのいずれにお
いても、問題はめったにしか起きないので、性能に対する影響は無視できる。
【００６４】
Ｒを判定する他の技術も利用できる。非巡回的曲線において、余因子ｈがあり、それは
、実際には、普通２または４である。これはｘの複数の可能な値となる。ｒ＝ｘの確率は
、ほぼ１／ｈである。他の状況においては、一般的にはｒ＝ｘ−ｎ（ｈ＝２ならば）、ま
たはより一般的には、ｒ＝ｘ−ｍｎでありここで（ｍは０とｈ−１の間）である。ｐはほ
ぼｈｎなので、無視できる部分を除いて、ｒに関連しているｘの可能な値がｈ個あること
になる。ｘを取り出すために、従ってＲをより容易に取り出すために、署名者は、ｍを計
算して、それを、メッセージ内、あるいは更なる署名成分として検証者に送ることができ
る。または検証者は、ｍを経験に基づいて推測できる。これはｈ＝２の場合に例示するこ
とができる。
【００６５】
ｒに対応するのは、正しいｘと偽の値ｘｆである。偽の値ｘｆは、Ｅ上でｘ座標の値に
対応しないという可能性はほぼ１／２であり、更に、Ｇの倍数に対応しないという可能性
は１／ｈである。ｘに対する２つの値のうちの１つが有効でない場合は、Ｅにないという
ことにより、またはそれが位数ｎを有していなければ、その両者は効率よく調べられ、そ
の値は削除できる。このように、少なくとも３／４の時間で検証者は正しいｘを容易に求
めることができる。残りの最大１／４の時間で、検証者は、２つのｘの値のいずれを試み
るべきかを知ることができない。半分の時間で検証者が検証すべきｘの値の１つを推測で
きるならばこの推測は正しくて、署名は検証されるが、残りの半分の時間で、第１署名の
試みは失敗し、検証者は他のｘの値を試みなければならない。従って、検証者が２つの署
名を検証しなければならない確率は１／８である。２つの検証のこの確率にもかかわらず
、平均検証は依然として改善される。これは、依然として平均して、検証者に時間のより
多くの節約量を提供できる。促進された検証が、通常の検証の７０％で済むが、検証の１
２．５％が促進された検証の２倍の時間がかかれば、平均時間は通常の検証の７９％とい
うことになる。更に、下記に概要を示すが、署名者はｍを検証者に提供することにより、
またはたった１つのｍしか有効でないことを確実にするために両者の値を試みる余分な作
業を行うことにより支援することができる。
【００６６】
類似の方法を、余因子ｈ＝４で利用できる。実際、ｈの値が大きいと、可能性のあるｘ
の値のそれぞれが有効である確率が低くなる。より多くの可能性のあるｘの値があるが、
解析によると、検証者に対して同様な利点があることが示される。３個のｘの偽の値があ
り、それぞれは高速チェックでは有効に見える確率は１／８である。このため、偽の値が
、高速チェックで有効なｘと見えない可能性は（７／８）３であり、約７７％である。残
りの２３％の時間のほとんどは、ｘの偽の値が１つだけ有効に見え、全署名検証を必要と
する可能性がある。
【００６７】
ｉ（必要であればｍも）を含むことは、ｒを、ｘ座標とｙ座標の第１ビットから構成さ
れるＲの圧縮バージョンと置き換えることに非常に類似している。このように、ｒの代わ
りにＲの圧縮値を送ることは、ある程度はより簡単で、偽の値を取り出す可能性は無視で
きるという利点がある。従って、図９に示されるように、署名は計算されて成分ｒ’、ｓ
の対を提供し、メッセージＭと共に受け手１４に転送される。成分ｒ’はＲのｘ座標とｙ
座標の第１ビットから構成される。成分ｓは以前と同様に計算される。
【００６８】
署名を検証するために、受け手１４は、点Ｒを成分ｒ’から直接取り出し、検証相等性
方程式−ｚＲ＋（ｚｕ ｍｏｄ ｎ）Ｇ＋ｗＱ＝Ｏを使用して、それが群の単位元に対応
することを確認する。修正された座標ｒ’の送信は、検証を簡単にするが、必要な帯域幅
も増やすことになる。
【００６９】
ある状況においては、署名者が余分なビットを送るために利用できるチャネルがない場
合がある。例えば、既存の標準規格では、署名フォーマットとメッセージフォーマットの
両者を厳格に制限して、送り手が追加情報を提供する余地がまったくないこともある。署
名者と検証者は、それにも拘わらず、両者の実践を調整し、それにより、Ｒはｒから取り
出せる。これは、署名者が、図１０に示すように、ｘの値が、予め準備された基準に準拠
することを確実にすることにより調整できる。上記の表記によれば、署名者は、Ｒ＝ｋＧ
＝（ｘ，ｙ）を通常のように計算し、上記の表記において、ｉ＝ｙ ｍｏｄ ２を計算す
る。ｉ＝１であれば、署名者は、ｋを−ｋ ｍｏｄ ｎに変更し、それにより、Ｒは−Ｒ
＝（ｘ，−ｙ）に変わり、ｉは０に変わる。検証者が署名を受け取ると、検証者はｉ＝０
と仮定して、それにより署名を取り出す。ｉの値は、このように値０として無条件に伝え
られ、署名者は、これを調整するためにほとんど無視できる程度の対価しか必要としない
。同様に、非巡回的楕円曲線においては、署名者は、ｍを無条件に送信しようとし、これ
はある程度は既に上述してある。ｈ＝２の場合は、時間の１／４であることを思い出せば
、検証者は、２つの署名を検証する必要がある。検証者がこの余分な作業を行う代わりに
、署名者は、この１／４の場合を検出でき、その代わりにｋとＲに対する別の値を試み、
基準に準拠するものが１つ見つかるまでこのプロセスを繰り返す。検証者は、２つの署名
を検証する必要なくいずれのｘを使用するかを決定することができる。
【００７０】
上述したようなＲを修正することの代替として、およびＥＣＤＳＡ標準規格に厳格に準
拠することを維持するために、ｓの値は、Ｒではなく、計算の後に修正してもよい。この
場合、署名者はＲの値は前もって調整された基準に準拠しないことに気付き、通常のよう
に、ｒとｓを生成するように進行できる。ｓが計算された後、その値は（−ｓ）に変更さ
れ、検証が、ｙの前もって調整された値を仮定して達成できることを確実にする。
【００７１】
署名者が署名（ｒ，ｓ）を、Ｒが無条件に取り出されるように選択すると、通常の検証
者は、署名を通常のように容認する。そのような署名は完全に有効である。つまり、改訂
検証は、ＥＣＤＳＡ検証の既存の実践と完全に互換性がある。無条件の効率的な署名を期
待しているが、通常に生成された署名を受け取る促進された検証者は、ｉの２つの異なる
値を試みる必要がある。促進された検証が、通常の検証の６０％の時間がかかるとすれば
、巡回的曲線（余因子ｈ＝１）においては、通常の署名を検証するために必要な平均時間
は、通常の検証の５０％（６０％）＋５０％（１２０％）＝９０％である。これは通常の
署名の時間の５０％はｉ＝０を有し、たった１回だけの無条件の促進された検証を必要と
し、他の５０％の時間は２回の促進された検証を必要とするからである。無条件に促進さ
れた検証は、署名が無条件に促進されなくても、通常の検証者よりも依然として速い。
【００７２】
従来の署名もまた、署名者または第３者により修正できて、高速検証が可能になる。こ
の場合は、署名は、要求者から第３者に転送され、この第３者が検証相等性を使用して署
名を検証する。そうすることによりＲの値が取り出される。署名は修正されて、指標Ｉを
含み、要求者に戻される。修正された署名は、高速検証署名を期待している受け手との以
降の交換に使用される。
【００７３】
上記の技術はＲを取り出して、関係−ｚＲ＋（ｚｕ ｍｏｄ ｎ）Ｇ＋ｗＱ＝Ｏを使用
して改訂検証が可能になる。しかし、ＥＣＤＳＡが検証されるときは、整数ｗとｚは、図
１１に示されるように、Ｒを取り出すことなしに使用できる。ｚＲのｘ座標と、点ｗＱ＋
（ｚｕ ｍｏｄ ｎ）Ｇのｘ’座標を計算し、これら２つのｘ座標の相等性を調べること
は可能である。Ｒのｙ座標を知らずに、ｚＲのｙ座標を直接計算することは不可能なので
、点ｚＲのｘ座標のみが計算可能である。しかし、Ｒのｙ座標を必要とせずにＲのｘ座標
からｚＲのｘ座標を計算するいくつかの既知の方法がある。そのような技術には、上記に
示した「楕円曲線暗号へのガイド」（Ｇｕｉｄｅ ｔｏ Ｅｌｌｉｐｔｉｃ Ｃｕｒｖｅ
Ｃｒｙｐｔｏｇｒａｐｈｙ）の１０２頁に説明されているモントゴメリー（Ｍｏｎｔｇ
ｏｍｅｒｙ）の方法がある。そして、ｘ座標の相等性は、ｗＱ＋（ｚｕ ｍｏｄ ｎ）Ｇ
がｚＲまたは−ｚＲに等しいことを意味し、それはｗ／ｚＱ＋ｕＧがＲまたは−Ｒに等し
いことを意味し、それはｕＧ＋ｖＱがＲと同じｘ座標を有することを意味するので、ｚＲ
とｗＱ＋（ｚｕ ｍｏｄ ｎ）Ｇのｘ座標を調べれば十分である。これはＥＣＤＳＡを首
尾よく検証するための条件である。Ｒのｘ座標は、上記に検討した方法を使用して署名成
分ｒから取り出せる。このアプローチの利点は、ｙ座標を取り出すために余分な作業を必
要としないことである。上述した以前の方法に比べて不利な点は、ｚＲをｗＱ＋（ｚｕ
ｍｏｄ ｎ）Ｇとは別に計算しなくてはならないことであり、これは、結合和の節約量の
ある部分は達成されないことを意味する。
【００７４】
上記の例では、通信設備１２、１４の対の間の署名を検証した。この技術は、図１２に
示されるように、楕円曲線鍵対（ｄ，Ｑ）の検証にも使用できる。鍵対を検証することは
、Ｑ＝ｄＧを調べることである。これは、改竄が行われていないことを保証するための安
全条件のもとで第３者により鍵対が提供されるときに重要である。ｔがｄのビット長であ
るときに、二進法の方法でのｄＧの計算は、平均して（３ｔ／２）回の演算が必要となる
。本実施形態では、通信設備１２、１４の１つは乱整数ｄを生成して、ｄ＝ｗ／ｚ ｍｏ
ｄ ｎとなるように整数ｗ、ｚの対を取得する。典型的には、整数ｗ、ｚはそれぞれ長さ
ｄの半分である。そして通信設備はｚＱ−ｗＧを計算し、結果が群の単位元０であること
を調べる。ｚＱ−ｗＧの計算は、平均してｔ回の演算を必要とし、従って、５０％の節約
量が得られる。これは、Ｇの前計算された倍数を格納するためのコストが高価である環境
においては最も有利な方法である。メモリに制限がある別の環境では、前計算された倍数
Ｈ＝ｕＧがあれば、ｄＧがｄ’Ｇ＋ｄ’’Ｈとして計算され、ここにおいてｄ＝ｄ’＋ｄ
’’ｕ ｍｏｄ ｎであり、上記とほぼ同じコストがかかる。
【００７５】
別の適用は、無条件の証明書の検証である。無条件の証明書は対（Ｐ，Ｉ）であり、こ
こでＰは楕円曲線点であり、Ｉはある単位元列である。エンティティであるボブ（Ｂｏｂ
）は、楕円曲線点である要求値ＲをＣＡに送ることにより、無条件の証明書をＣＡから取
得する。ＣＡは、無条件の証明書（Ｐ，Ｉ）を返し、更に、私的鍵再構築データ値ｓを返
す。ボブ（Ｂｏｂ）は、ｓを使用して自分の私的鍵を計算する。より一般的には、いかな
るエンティティもｓを使用して無条件の証明書がボブ（Ｂｏｂ）の要求値ＲとＣＡ公開鍵
Ｃに正確に対応していることを検証できる。これは、検証相等性Ｈ（Ｐ，Ｉ）Ｒ＋ｓＧ＝
Ｈ（Ｐ，Ｉ）Ｐ＋Ｃを調べることで行われ、ここにおいてＨはハッシュ関数である。この
方程式は、ｅＱ＋ｓＧ＝Ｃと等価であり、ここにおいてｅ＝Ｈ（Ｐ，Ｉ）およびＱ＝Ｒ−
Ｐである。この方程式の形式は標準規格ＥＣＤＳＡ検証方程式の形式に非常に類似してい
る。従って、上記で検討した技術は、この方程式の検証を促進する手段を提供するために
使用できる。これは、ｅ＝ｗ／ｚ ｍｏｄ ｎとなるように、相対的に小さな値ｗとｚを
決定することにより最適に行われ、この方程式にｚを乗算することにより、ｗＱ＋（ｓｚ
ｍｏｄ ｎ）Ｇ−ｚＣ＝Ｏが得られる。再び、この方程式のＧの倍数は全サイズである
が、一般的にはＧの倍数は前計算でき、従って、これは問題を引き起こさない。
【００７６】
この技術の利点を利用する別の変形例では、ＥＣＤＳＡ署名方程式の３つすべての倍数
を短くする。理論的には、各倍数は、ｎの長さの２／３の長さまで短くできる（ｎはＧの
位数）。この短小化を達成するための１つの方法は、３次元における短ベクトル束問題を
解くことである。そのような問題を解くためのアルゴリズムが存在する。３つすべての倍
数を短くすることは、Ｇの前計算された倍数をいずれも格納することができない場合には
非常に有益であり、Ｇの倍数の長さを可能な限り短くすることをより効率的にする。その
ような技術は、アンリコーヘン（Ｈｅｎｒｉ Ｃｏｈｅｎ）の計算法代数的数論講座（Ａ
Ｃｏｕｒｓｅ ｉｎ Ｃｏｍｐｕｔａｔｉｏｎａｌ Ａｌｇｅｂｒａｉｃ Ｎｕｍｂｅ
ｒ Ｔｈｅｏｒｙ），スプリンゲル（Ｓｐｒｉｎｇｅｒ）、ＩＳＢＮ０−３８７−５５６
４０−０に更に完全に記載されている。第２．６節と２．６節はＬＬＬアルゴリズムを記
載しており、その適用は、束における短ベクトルを見出すことであり、また、３次元束の
ためのベーユ（Ｖａｌｌｅｅ）の特別アルゴリズムに言及している。
【００７７】
この技術の別の適用は、部分メッセージ取り出しのピンチョフ−バンストーン署名（Ｐ
ｉｎｔｓｏｖ−Ｖａｎｓｔｏｎｅ Ｓｉｇｎａｔｕｒｅ（ＰＶＳ））方式の修正バージョ
ンへの適用である。ＰＶＳ署名は（ｒ，ｓ，ｔ）の３つの組から構成される。署名の検証
と、公開鍵Ｑのもとで署名からのメッセージの取り出しは、ベース生成子Ｇにより、下記
のように行われる。検証者はｅ＝Ｈ（ｒ‖ｔ）を計算し、ここにおいてＨはハッシュ関数
である。そして検証者は、Ｒ＝ｓＧ＋ｅＱを計算する。次に、検証者はＲから対称暗号鍵
Ｋを導出する。これにより、検証者は、Ｋを使用してｒを解読し、取り出されたメッセー
ジ部分ｕを得る。取り出されたメッセージは、ｔとｕのある結合である。署名はｕがある
冗長性を有していれば有効であり、この冗長性は、ｕがある所定のフォーマットに準じて
いることを検証することにより調べられる。ＰＶＳ方式は、草案標準規格ＩＥＥＥ Ｐ
１３６３ａおよびＡＮＳＩ Ｘ９．９２の一部である。
【００７８】
ＰＶＳの修正変形例においては、検証時間は整数ｗとｚを利用することにより削減でき
る。ＰＶＳの修正変形例は図１３に示されており、下記のようにして進める。通常のよう
にｅを計算した後、検証者は、ｗとｚが、ｅ＝ｗ／ｚ ｍｏｄ ｎであり、点Ｇの位数で
あるｎの長さの半分であることを見出す。そして検証者は、Ｒ＝（ｗｓ ｍｏｄ ｎ）Ｇ
＋ｚＱを計算して、以前のように手順を進めて、Ｒから鍵を導出し、その鍵でｒを解読し
、解読が正しい形式であることを検証する。検証のこの形式は、Ｑの倍数がより小さいの
でより効率的である。
【００７９】
楕円曲線群および類似の群におけるデジタル署名の署名検証を更に促進するための方法
が下記のように例示される。ＥＣＤＳＡ署名の検証は、基本的には、ａＲ＋ｂＱ＋ｃＧの
ような３個の楕円曲線点の線形結合が、無限大の点と等しいことを確認することと等価で
ある。この条件を検証する１つの方法は、点ａＲ＋ｂＱ＋ｃＧを計算し、その結果が無限
大における点Ｏ、つまり、上述したように、群の単位元であるかを調べる。この検証は、
ときどき、全体の合計を直接計算するよりもより迅速に行えることがある。例えば、ａ＝
ｂ＝ｃならば、点Ｒ、Ｑ、およびＧが共線でありその場合に限ってａＲ＋ｂＱ＋ｃＧ＝Ｏ
である。点が共線であるかを調べることは、楕円曲線点への加算よりも格段に速い。共線
性は、方程式（ｘＲ−ｘＧ）（ｙＱ−ｙＧ）−（ｘＱ−ｘＧ）（ｙＲ−ｙＧ）＝０により
、わずか２回の体の乗算により調べることができる。点の加算は、少なくも２回の体の乗
算、つまり体の平方および体の反転が必要であり、それは一般的には、約８回の体の乗算
と等価である。ａ＝ｂ＝ｃのときは、検証はこのように、点の加算にかかる時間の約１８
％で可能である。このように、この技術は、これらの条件が存在する可能性があるときは
、検証プロセスの準備ステップとして使用できる。同様に、ｂ＝ｃ＝０で、ａＲ＝Ｏの検
証を所望するときは、原理的に、ａＲ全体を計算する必要はない。その代わりに、点Ｒに
おけるａ番目の除算多項式を評価することができる。除算多項式は基本的には、点Ｒの座
標の有理関数として表現されるときは、点ａＲの座標の分母に対する帰納的公式に対応す
る。分母が０でありその場合に限りａＲ＝０であることが知られている。更に、ｂ＝ｃ＝
０であり、楕円曲線群が素数の位数ｎで巡回的であれば、ａ＝０ ｍｏｄ ｎまたはＲ＝
Ｏでありその場合に限りａＲ＝Ｏであることが知られている。この検証は、零楕円曲線点
演算が必要であるという点において比較的に即座に終了する。余因子が、ｈ＝２またはｈ
＝４のように小さいときは、点演算は、数回の非常に高速な体の演算により置き換えるこ
とができる。このように、合計の点がゼロであるような検証の特別な場合は、非常に速く
行うことができる。
【００８０】
除算多項式に対する帰納的公式に類似して、ａＲ＋ｂＱ＋ｃＧのような合計の分母に対
する帰納的公式が存在し、これらは、点ａＲ＋ｂＱ＋ｃＧの全値を計算するよりもより高
速に計算できる。群の位数ｎを知っていれば、検証時間を更に短縮できる。
【００８１】
この技術の更なる適用は、図１４に示されるように、ＥＣＤＳＡデジタル署名のみから
、公開鍵Ｑを効率的に回復することである。１つの通信設備１２が署名（ｒ，ｓ）でメッ
セージＭに署名して、署名したメッセージを通信設備１４に送りたいとする。通常は、通
信設備１４は、Ｍと（ｒ，ｓ）を通信設備に送り、しばしば公開鍵Ｑも送る。通信設備１
２がそれ自身の公開鍵を送らなかったとすると、通常は、通信設備１４は、あるネットワ
ークを介して、局所的にまたは遠隔的に格納できる、あるデータベースにおいて相手の通
信設備の公開鍵を探そうとする。これを避けるために、署名から公開鍵Ｑを取り出せると
いうことは有利である。
【００８２】
通常のＥＣＤＳＡ署名（ｒ，ｓ）が与えられれば、公開鍵である可能性があるいくつか
の候補点Ｑを取り出すことができる。第１ステップは点Ｒを取り出すことである。署名に
追加情報を含むことにより、署名されたメッセージに追加情報を含むことにより、１つの
有効なＲがｒに対応できることを保証する署名者側の追加作業により、およびｒに対応す
る多数の異なるＲ値を試みる検証者側の追加作業によるなど、促進された検証の状況にお
いてＲを見出すためのいくつかの方法が既に記載されてきた。これらの方法の１つにより
いったんＲが取り出されると、公開鍵Ｑは下記のようにして取り出すことができる。標準
規格ＥＣＤＳＡ検証方程式はＲ＝（ｅ／ｓ）Ｇ＋（ｒ／ｓ）Ｑであり、ここでｅ＝Ｈ（Ｍ
）はメッセージのハッシュ値である。Ｒとこの方程式が与えられれば、Ｑを求めることは
Ｑ＝（ｓ／ｒ）Ｒ−（ｅ／ｒ）Ｇにより行われる。
【００８３】
しかし、かなりの確率で、対（ｒ，ｓ）はある有効公開鍵を生成し、通信設備１４は、
Ｑが通信設備１２の公開鍵であるかを調べる方法が必要となる。通信設備１２は、通信設
備１４の公開鍵についてのＣＡから、別のＥＣＤＳＡ署名（ｒ’，ｓ’）のような署名を
通信設備１４が利用できるようにする。通信設備１２は、ＣＡ署名（ｒ’，ｓ’）を通信
設備１４に送ることができ、または通信設備１４はそれをあるデータベースで探すことが
できる。ＣＡの署名は、通信設備１２の名前と公開鍵Ｑ上にある。通信設備１４は、ＣＡ
の証明書を使用して、公開鍵Ｑに対応するメッセージを検証する。署名が検証されれば、
通信設備１４は、公開鍵Ｑに対する正しい値を取り出したことになる。証明書から公開鍵
を省略することは、帯域幅と格納領域を節約することになり、上述した検証プロセスは検
証時間を短縮する。
【００８４】
通信設備１４はまた、Ｑのビットの半分のような、Ｑから導出されたよりコンパクトな
値に対してＱを調べることにより、Ｑが通信設備１２の公開鍵であることを検証できる。
Ｑのコンパクトバージョンは、この後格納され、またはＱの代わりに通信され、ここで再
び格納領域と帯域幅を節約することができる。
【００８５】
検証相等性で使用される値のそれぞれが公開値であることも理解されるであろう。従っ
て、検証者が利用できる計算能力に制限がある場合は、署名者はｗとｚの値を計算して、
それをＲと共にメッセージの一部として転送することができる。受け手は、Ｒを取り出す
必要がなく、またｗとｚを計算する必要もなく、利用できる情報で検証を行うことができ
る。検証は促進されるが帯域幅は増大する。
【００８６】
上記の記載は、楕円曲線群に対するものであったが、本発明で記載された多数の方法は
、より一般的に暗号で使用される任意の群に適用でき、更に、群の元の冪乗を使用する他
の適用も可能である。例えば、本発明は、最近、楕円曲線群の代替として提案されている
、群がｇ（種）＝２の超楕円曲線の場合に使用できる。上記の技術は、ＥＣＤＳＡに類似
している、デジタル署名アルゴリズム（ＤＳＡ：Ｄｉｇｉｔａｌ Ｓｉｇｎａｔｕｒｅ
Ａｌｇｏｒｉｔｈｍ）の検証を促進するためにも使用できる。ＥＣＤＳＡと同様に、ＤＳ
Ａ署名は、整数（ｒ，ｓ）の対から構成され、ｒはＤＳＡ群の元Ｒから得られる。ＤＳＡ
群は、有限体の乗算群の部分群であると定義されている。しかし、ＥＣＤＳＡとは異なり
、ｒからＲを取り出すことは、数個の追加ビットの支援があっても達成するのが容易では
ない。従って、本技術は、値がＲで、署名されたメッセージの一部分として、または署名
の追加部分として、または値ｒに対する置き換えとして送られるならば、最も容易にＤＳ
Ａに適用できる。典型的に、整数ｒは２０バイトで表現されるが、値Ｒは１２８バイトで
表現される。結果として、結合された署名とメッセージ長は、約１０８バイト長くなる。
しかしこれは、検証を３３％促進するためには小さなコストである。
【００８７】
ＤＳＡ設定においては、ｐは大きな素数であり、ｑはより小さな素数であり、ｑは（ｐ
−１）の約数である。整数ｇは、ｇ＾ｑ＝１ ｍｏｄ ｐ、および１＜ｇ＜ｐとなるよう
に選択される。（ｑとｇは、ＥＣＤＳＡからのｎとＧにそれぞれ対応することに注意。）
【００８８】
署名者の私的鍵は、ある整数ｘであり、公開鍵はＹ＝ｇ＾ｘ ｍｏｄ ｐである。
【００８９】
署名者は署名を、通常の（ｒ，ｓ）の代わりに（Ｒ，ｓ）の形式で生成する。ここで、
Ｒ＝ｇ＾ｋ ｍｏｄ ｐであるが、ｒ＝Ｒ ｍｏｄ ｑである。両者の場合において、ｓ
＝ｋ＾（−１）（ｈ（Ｍ）＋ｘｒ） ｍｏｄ ｑであり、ここでｘは署名者の私的鍵であ
り、Ｍは署名されるメッセージであり、ｈはメッセージを要約するために使用されるハッ
シュ関数である（ＥＣＤＳＡと同様）。
【００９０】
通常のＤＳＡにおいて、検証者は、ｕ＝ｈ（Ｍ）／ｓ ｍｏｄ ｑとｖ＝ｒ／ｓ ｍｏ
ｄ ｑを計算することにより署名（ｒ，ｓ）を検証し、これはＥＣＤＳＡ実施形態におけ
るｕとｖに非常に類似しており、そしてｒ＝（ｇ＾ｕＹ＾ｖ ｍｏｄ ｐ） ｍｏｄ ｑ
を調べる。本実施形態においては、検証者は、ｑの約半分の長さのビット長のｗとｚを見
出し、それによりｗとｚのそれぞれは、ｖ＝ｗ／ｚ ｍｏｄ ｑとなるように、ほぼｓｑ
ｒｔ（ｑ）となる。これは、ｎをｑと置き換えて、上記のＥＣＤＳＡ実施形態と同じ方法
で行われる。そして検証者は、Ｒ＾ｚｇ＾（ｚｕ ｍｏｄ ｑ）Ｙ＾ｗ ｍｏｄ ｐを計
算する。
【００９１】
この値が１に等しければ、検証者はその署名を容認し、そうでなければその署名は拒絶
される。
【００９２】
検証者は、平方乗算アルゴリズム、またはその変形例を使用してこの値を計算し、ＥＣ
ＤＳＡにおける同時倍算に類似した同時平方を利用する。ＥＣＤＳＡ高速検証の多数の方
法がＤＳＡ高速検証に使用できる。ｇの前計算された倍数、例えばｊを使用することがで
き、計算はＲ＾ｚｇ＾ｓｊ＾ｔＹ＾ｗ ｍｏｄ ｐのようになり、ここで、ｚ、ｓ、ｔ、
およびｗのそれぞれは、ｑの約半分のビット長を有する。公開鍵Ｙの前計算された冪乗が
利用できるならば、冪の指数の長さは、更に短縮することができ、それにより倍算の数を
少なくして検証をより高速にする。
【技術分野】
【０００１】
本発明は、暗号アルゴリズムにおいて使用される計算法技術に関する。
【背景技術】
【０００２】
データ通信システムを通して伝達される情報の安全性とその情報が本物であることは、
最も重要なことである。情報の多くは、機密性があるため、適切な制御に欠けると、経済
的および個人的損失につながる可能性がある。暗号システムは、このような懸念に対処す
るために開発されてきた。
【０００３】
公開鍵暗号により、クーリエ（メッセンジャ）などのような独立した機構を通して情報
を交換する際に、他の通信相手に同一の鍵を送る必要がないデータ通信システム上での安
全な通信が可能になる。公開鍵暗号は、鍵対の生成に基づいており、その対の１つは私的
であり、他の１つは公開され、それらは一方向数学関数により関連付けられている。一方
向関数は、基盤となる数学的構造において、公開鍵は私的鍵から容易に計算できるが、私
的鍵は、公開鍵からは、現実的には突き止められないようになっている。
【０００４】
より強固な一方向関数の１つに、有限体における冪乗法があり、ここにおいて整数ｋは
私的鍵として使用され、体αの生成子は、公開鍵Ｋ＝αｋをもたらすために冪乗される。
αとＫが知られても、有限体の基盤となる数学的構造は、私的鍵ｋを取得することを現実
的に不可能にする。公開鍵暗号は、通信者間で使用され、両者の通信者がお互いの公開鍵
を交換して、相手の公開鍵を、自分の私的鍵で冪乗することにより共通鍵が確立される。
公開鍵暗号は、メッセージの発信元が本物であることを証明するためにデジタル的にメッ
セージに署名するためにも使用できる。メッセージを書いた人間は、自分の私的鍵を使用
してメッセージに署名し、メッセージが本物であることは対応する公開鍵を使用して検証
できる。
【０００５】
そのようなシステムの安全性は、基盤となる数学的構造に大きく依存している。離散対
数システムを実践するための、最も共通して使用される構造は、有限体の乗法群の巡回的
部分群であり、そこにおいては群演算は乗法であり、または楕円曲線群の巡回的部分群で
あり、そこにおいては群演算は加法である。
【０００６】
楕円曲線Ｅは、（ｘ，ｙ）の形式の点の集合であり、ｘとｙは、素数ｐを法とする整数
のような、一般的にはＦｐと称される数であり、体Ｆに属しており、ｘとｙは、Ｆにおけ
るあるａとｂに対して、ｙ２＝ｘ３＋ａｘ＋ｂの形式を取ることができる非特異３次方程
式を満たす。楕円曲線Ｅもまた、Ｏとして示される無限大における点を含む。Ｅの点は、
群を形成するように定義できる。点Ｏは、群の単位元であり、Ｅにおける任意の点Ｐに対
してＯ＋Ｐ＝Ｐ＋Ｏ＝Ｐが成り立つ。各点Ｐに対して、別の点があり、それを我々は−Ｐ
と書き、Ｐ＋（−Ｐ）＝Ｐ＋（−Ｐ）＝Ｏが成り立つ。Ｅにおける任意の３つの点Ｐ、Ｑ
、Ｒに対して、結合法則が成り立つ、つまり、Ｐ＋（Ｑ＋Ｒ）＝（Ｐ＋Ｑ）＋Ｒが成り立
つ。単位元、否定、および結合法則は、群を定義する３つの公理的性質である。楕円曲線
群は、それが可換、つまりＰ＋Ｑ＝Ｑ＋Ｐが成り立つという更なる性質も有する。
【０００７】
スカラー乗法は、下記のように加法から定義できる。任意の点Ｐと任意の正の整数ｄに
対して、ｄＰはＰ＋Ｐ＋．．．＋Ｐと定義され、ここにおいてＰはｄ回出現する。このよ
うにして、１Ｐ＝Ｐ、２Ｐ＝Ｐ＋Ｐ、そして３Ｐ＝Ｐ＋Ｐ＋Ｐなどとなる。我々はまた、
０Ｐ＝Ｏ、そして（−ｄ）Ｐ＝ｄ（−Ｐ）と定義する。
【０００８】
簡単のために、実際には、楕円曲線の巡回的部分群が代わりに使用されることがたまに
あるが、巡回的である楕円曲線（下記に定義される）を扱うことが好ましい。巡回的であ
るということは、生成元Ｇがあり、Ｇは、群におけるすべての他の点Ｐが、Ｇの倍数であ
る、つまり、ある正の整数ｄに対して、Ｐ＝ｄＧであるということである。ｎＧ＝Ｏとな
るような最小の正の整数ｎは、Ｇの（そして、Ｅが巡回的であるときの曲線Ｅの）位数で
ある。暗号への適用においては、楕円曲線はｎが素数になるように選択される。
【０００９】
楕円曲線暗号システムにおいては、冪乗に類似するものは点の乗算である。このように
、私的鍵は整数ｋであり、対応する公開鍵は点ｋＰであり、ここにおいてＰは、システム
パラメータの一部であり、曲線上の予め定義された点である。シード（種子）点Ｐは典型
的には生成子Ｇである。鍵対は、種々の暗号アルゴリズムで使用され、暗号化に対する共
通鍵を確立し、デジタル署名を実行する。そのようなアルゴリズムは、値のセット間の定
義された関係（検証相等性とも称せられる）を確認するために、値の対を比較することに
よる、ある演算による検証をしばしば必要とする。
【００１０】
そのようなアルゴリズムの１つは、エンティティ間で交換されるメッセージ上にデジタ
ル署名を生成するために使用される楕円曲線デジタル署名アルゴリズム（ＥＣＤＳＡ：Ｅ
ｌｌｉｐｔｉｃ Ｃｕｒｖｅ Ｄｉｇｉｔａｌ Ｓｉｇｎａｔｕｒｅ Ａｌｇｏｒｉｔｈ
ｍ）である。ＥＣＤＳＡを使用するエンティティは２つの役割、つまり、署名者と検証者
の役割を有する。署名者は、１とｎ−１間の両端を含める範囲の整数である長期私的鍵ｄ
を選択する。整数ｄは秘密でなければならず、そのため、一般的にはｄをランダムに選択
することが好ましい。署名者は、Ｑ＝ｄＧを計算する。点Ｑは、署名者の長期公開鍵であ
り、検証者が入手できるようになっている。一般的に、検証者は、Ｑが署名者であるエン
ティティに対応することを、ＣＡからの証明書により一般的には確証を得る。公開鍵Ｑか
ら私的鍵ｄを見出すことは、今日使用されている楕円曲線の選択に対して手に負えない問
題であると信じられている。
【００１１】
任意のメッセージＭに対して、署名者は、署名を作成でき、その署名は、ＥＣＤＳＡの
場合は、整数（ｒ，ｓ）の対である。検証者はいずれもメッセージＭと、公開鍵Ｑと、署
名（ｒ，ｓ）を受け取ることができ、それが対応する署名者により作成されたものかどう
かを検証できる。これは、有効な署名（ｒ，ｓ）の作成は、公開鍵Ｑに対応する私的鍵ｄ
を知っているエンティティによってのみ可能であると信じられているからである。
【００１２】
署名プロセスは下記の通りである。まず、署名者は、範囲［１，ｎ−１］におけるある
整数ｋを選択し、それは、セッション、または一時的な私的鍵として使用される。値ｋは
秘密でなくてはならず、そのため、好ましくはｋをランダムに選択する。そして、署名者
は、座標（ｘ，ｙ）を有する点Ｒ＝ｋＧを計算する。次に、署名者は、ｘを整数ｘ’に変
換して、ｒ＝ｘ’ｍｏｄ ｎ、つまり署名者の第１座標を計算する。署名者はまた、整数
ｅ＝ｈ（Ｍ）ｍｏｄ ｎも計算しなければならず、ここでｈはあるハッシュ関数であり、
一般的には、米国連邦情報処理標準規格（Ｆｅｄｅｒａｌ Ｉｎｆｏｒｍａｔｉｏｎ Ｐ
ｒｏｃｅｓｓｉｎｇ Ｓｔａｎｄａｒｄ（ＦＩＰＳ））１８０−２で定義されたＳｅｃｕ
ｒｅ Ｈａｓｈ Ａｌｇｏｒｉｔｈｍｓ（ＳＨＡ−１またはＳＨＡ−２５６のような）の
１つである。最後に、第２座標ｓはｓ＝（ｅ＋ｄｒ）／ｓ ｍｏｄ ｎとして計算される
。成分（ｒ，ｓ）は、署名者によりメッセージＭの署名として使用され、メッセージと共
に意図された受信者に送られる。
【００１３】
検証プロセスは下記の通りである。まず、検証者は、整数ｅ＝ｈ（Ｍ） ｍｏｄ ｎを
受信したメッセージから計算する。そして検証者は、ｕ＝ｅ／ｓ ｍｏｄ ｎおよびｖ＝
ｒ／ｓ ｍｏｄ ｎとなるような整数ｕとｖを計算する。次に、検証者は、ｕＧ＋ｖＱを
加算することにより得られた点Ｒに対応する値を計算する。これは座標（ｘ，ｙ）を有す
る。最後に、検証者は、体の元ｘを整数ｘ’に変換して、ｒ＝ｘ’ｍｏｄ ｎであるかを
調べる。そうであれば、署名は検証されたことになる。
【００１４】
上記から、ＥＣＤＳＡ署名の検証は、ＥＣＤＳＡ署名の作成の２倍の時間がかかるよう
に見える。これは、検証プロセスは２回のスカラー乗法、つまり、ｕＧとｖＱを含むが、
署名は１回のみのスカラー乗法、つまりｋＧを含むからである。楕円曲線スカラー乗法は
、これらのプロセスのほとんどの時間を消費しており、その２倍が本質的には計算時間を
２倍にする。ｕＧとｖＱを別々に計算するよりも時間をかけずにｕＧ＋ｖＱを計算する方
法が知られている。これらの方法のいくつかは、シャミール（Ｓｈａｍｉｒ）によるもの
であり、あるものはソリナス（Ｓｏｌｉｎａｓ）によるものであり、あるものは多様な人
々によるものである。一般的に、これらの方法は、ｕＧ＋ｖＱが、ｋＧを計算する時間の
１．５倍で済むことを意味している。
【００１５】
楕円曲線計算を促進するための、別の共通して使用される方法は、Ｇの倍数の前計算表
である。そのような前計算表は、点Ｇは一般的には、繰返し使用される固定システムパラ
メータであるので時間を節約できる。最も簡単な前計算表は、ｊが０からｔのときのすべ
ての倍数２＾ｊ Ｇから構成されており、ここでｔはｎのビット長である。そのような前
計算表があれば、任意の倍数ｋＧの計算は、ｔ／２の点の加算、またはそれより少ない点
の加算の平均で行われる。概略的に述べれば、これはｋＧの計算の基本的な方法に対して
３倍改善されたことを示しており、前計算の利点を明確に示している。一般的に述べれば
、前計算表が大きいほど、より良く時間的に改善される。前計算表を格納するために必要
なメモリは、非常に高価である。従って、改善は、より迅速な計算の利点と、より大きな
表にかかる余分なコストのバランスを取らなければならない。正確なバランスは、一般的
には、メモリ使用に対する速度の相対的な重要性に依存しており、それは実践方法により
異なる。
【００１６】
前計算はまた、公開鍵Ｑにも適用できる。一般的には、公開鍵Ｑは、Ｇよりもより頻繁
に変化する傾向にある。それは公開鍵Ｑが通信者それぞれに対して異なるが、Ｇは、所与
のシステムに対しては、固定だからである。従って、Ｑに対する１回の前計算のコストは
、より少ない回数のＱを含む繰返し起動時計算で償却される。それにも拘わらず、Ｑが２
回以上使用されると、時間のある程度の正味の節約が達成される。頻繁に使用される公開
鍵は、認証機関（ＣＡ）の公開鍵、特に、ルート、トラスト、およびアンカＣＡ公開鍵（
これらはシステムに予めインストールされる）を含む。従って、前計算は、例えば、プロ
トコルがＣＡの証明書の検証を要求するＣＡ楕円曲線公開鍵のような場合に対しては意味
がある。Ｇに対してのＱの前計算の間の別の差は、前計算表の格納または通信のコストで
ある。各公開鍵Ｑは、それ自身の前計算表を必要とする。多数の個別公開鍵のシステムに
おいて、これらのコストは、より迅速な計算のいかなる利点も、鍵を格納または通信する
コストにより相殺されてしまう程度に嵩むこともある。正味の利点は、実践およびシステ
ム間で非常に異なる時間と、メモリと、帯域幅の相対的コストに依存する。ここで再び、
ＣＡ公開鍵、特に、ルート、トラスト、およびアンカＣＡ鍵の場合は、これらの鍵の数は
、端末−エンティティの公開鍵よりも少ない傾向にあり、それにより、前計算のコストは
、一般的に少なく、より多くの演算により償却される。
【００１７】
点の倍数の表は、前計算の間でのみ有利であるだけでない。実際、そのような表は、各
計算の初期段階中の、起動時に共通して生成される。これらの表による節約は本質的には
、単一の計算内において発生するある繰返し演算を回避することによる節約である。単一
の計算は、２つの別個の計算が共通して有するよりもより少ない内部の繰返しを有し、そ
れにより節約された繰返し量は、前計算より少なくなる。それにも拘わらず、表の選択を
賢明に行えば、単一の計算に必要な時間を削減できることが分かってきている。表は計算
するのに時間がかかり、表の計算は複数の計算では償却できず、すべての計算に対しても
負担を被る。経験によると、特別な表の計算は、それがなければ必要となる繰返し計算よ
りも時間がかからないので、特別な表は、必要な時間を削減する。通常は、最適なサイズ
と最適な表の選択がある。そのような表の別のコストは、表を一時的に格納するために必
要なメモリである。そのようなメモリのコストは、最適な表の選択に影響を与える可能性
がある。ウィンドウ化法は、作動中に計算されるそのような表の例である。
【００１８】
効率的な実践に対する、上記の既知の技術のすべてにも拘わらず、更なる効率の改善が
望ましい。特に、ＥＣＤＳＡ署名の検証の効率は、特に望ましい。幅広い前計算は、ＥＣ
ＤＳＡ署名を迅速に生成することを可能にする。実際、ＥＣＤＳＡ署名生成は、既知の最
速デジタル署名生成アルゴリズムの１つである。一方、ＥＣＤＳＡ署名検証は、相対的に
より緩慢で、ＥＣＤＳＡと類似する検証時間を有する他の署名アルゴリズムがある。従っ
て、ＥＣＤＳＡ検証時間の改善は、特に検証時間が障害となっている環境においては重要
である。
【００１９】
一般的には、値が２つの値の合計に対応することを検証するために計算を行うときの効
率を高める必要性がある。従って、本発明の目的は、上記の不都合な点を除去あるいは緩
和することである。
【発明の概要】
【課題を解決するための手段】
【００２０】
一般的には、本発明は楕円曲線上の点の対のスカラー倍の合計と、曲線上の第３の点の
間の関係の相等性を検証するための方法と装置を提供する。本方法は、ｉ）ビット長がス
カラーより短く、その比がスカラーに対応する整数の対を取得するステップと、ｉｉ）整
数を、その関係のスカラーに代入して、項の少なくとも１つが、縮小ビット長の点の１つ
のスカラー倍である等価な関係を取得するステップと、ｉｉｉ）相等性を検証する等価関
係を計算するステップを備える。
【００２１】
本方法は、楕円曲線上の点Ｒを表わす値が、他の２つの点ｕＧとｖＱの合計に対応する
ことを検証するために使用できる。整数ｗとｚは、ｗとｚを表わすビット列がそれぞれ、
整数ｕのビット列よりも短くて、ｖ＝ｗ／ｚ ｍｏｄ ｎとなるように決定される。その
ようなｗとｚにより、方程式Ｒ＝ｕＧ＋ｖＱが、−ｚＲ＋（ｚｕ ｍｏｄ ｎ）Ｇ＋ｗＱ
＝Ｏとして検証できる。
【００２２】
好ましくは、ｗとｚのビット長は、それぞれｎのビット長の約半分であり、それはｗと
ｚの両者が、約ｎ１／２より大きくはないことを意味する。
【００２３】
点−ｚＲ＋（ｚｕ ｍｏｄ ｎ）Ｇ＋ｗＱは、ｚとｗが相対的に小さい整数なので効率
よく計算でき、合計をその部分よりも高速に計算する種々の方法が使用できる。倍数（ｚ
ｕ ｍｏｄ ｎ）は全サイズであるが、ＥＣＤＳＡのようなアルゴリズムの状況において
、点Ｇは固定または繰り返えして起きてよい。この場合、計算は、Ｇに対して格納された
表を使用することにより促進できる。Ｇに対する表による従来の検証に比較して、このア
プローチによる時間の節約は、約４０％である。
【００２４】
ｗとｚの値は、部分完成拡張ユークリッドアルゴリズム計算を使用して取得できる。ま
たは、連分数アプローチを利用してｗとｚを効率よく取得することができる。
【００２５】
本発明の更なる形態においては、定義された最大ビット長のビット列により表現される
元を有する有限体の群における暗号演算により行われるメッセージのデジタル署名を検証
する方法が提供される。署名は、成分の対を備え、その１つは、署名者の一時的公開鍵か
ら導出され、他の１つは、メッセージと、第１成分と、一時的公開鍵と、署名者の長期公
開鍵を結合する。本方法は、一時的公開鍵を第１成分から取り出して、検証の相等性を、
一時的公開鍵と、長期公開鍵と、定義された最大ビット長よりも短い縮小ビット長を有す
るビット列により表わされるオペランドを含む群演算の少なくとも１つを有する群の生成
子に対する群演算の結合として確立するステップと、その結合を計算して、相等性が成立
すればその署名を容認し、相等性が成立しない場合はその署名を拒絶するステップを備え
る。
好ましくは、群は楕円曲線群である。更なる形態として、メッセージの署名を、有限体
の楕円曲線群において暗号演算により生成する方法があり、一時的公開鍵を表わす点から
導出された成分の１つを有する署名成分の対を生成し、１つの成分から取り出すことがで
きる公開鍵の複数の可能な値の１つを特定する指標を署名中に含むステップを備える。
例えば、本発明は以下の項目を提供する。
（項目１）
楕円曲線上の点対のスカラー倍の合計と、前記曲線上の第３点の間の関係の相等性を検
証する方法であって、ｉ）前記スカラーの１つよりも短く、その比は前記スカラーに相当
するビット長の整数対を取得するステップと、ｉｉ）前記整数を、前記関係における前記
スカラーに代入して、前記項の少なくとも１つが、縮小ビット長の前記点の１つのスカラ
ー倍である等価関係を取得するステップと、ｉｉｉ）前記等価関係を計算して、前記相等
性を検証するステップと、を含む方法。
（項目２）
一対の前記項は、縮小ビット長を有する項目１に記載の方法。
（項目３）
前記整数の他の１つは、前記第３点を修正して、縮小ビット長のスカラー倍を与える請
求項２に記載の方法。
（項目４）
前記等価関係の更なる項は、それぞれが縮小長のビット列により表現され、その１つは
、固定値を有し、他の１つは可変である点の対に分離される項目３に記載の方法。
（項目５）
固定値の前記点の前記１つは、繰返しの使用のために前計算されて格納される項目４
に記載の方法。
（項目６）
前記整数は、等しいビット長を有する項目３に記載の方法。
（項目７）
前記整数は、異なるビット長を有する項目３に記載の方法。
（項目８）
前記相等性は、前記点の合計を群の単位元に等しいと置き、少なくとも一対の前記点に
対して、同時加算を行うことで検証される項目３に記載の方法。
（項目９）
少なくとも前記一対の点の加算計算は、同時倍加算アルゴリズムを使用して行われる請
求項８に記載の方法。
（項目１０）
前記点は、前記点の１つが固定で前記点の他が可変で、前記可変の点は縮小ビット長の
前記整数に関連付けられているシステムにおいて使用される項目３に記載の方法。
（項目１１）
前記固定点のスカラー倍の少なくとも一部分は前計算される項目１０に記載の方法。
（項目１２）
前記固定点の前記スカラー倍は一対の点に分割され、前記点の１つは前計算される請求
項１１に記載の方法。
（項目１３）
前記点のそれぞれのスカラー倍は合計され、結果は相等性の検証のために群の単位元と
比較される項目１２に記載の方法。
（項目１４）
前記整数は、必要なビット長の整数が得られたとき中断される反復アルゴリズムを使用
して取得される項目１に記載の方法。
（項目１５）
前記アルゴリズムは拡張ユークリッドアルゴリズムである項目１４に記載の方法。
（項目１６）
定義された最大ビット長のビット列により表現される元を有する有限体の群における暗
号演算により行われる、メッセージのデジタル署名を検証する方法であって、前記署名は
、一対の成分を備え、対の１つは署名者の一時的公開鍵から導出され、対の他方は、前記
メッセージと、前記第１成分と前記署名者の前記一時的公開鍵および長期公開鍵とを結合
し、前記方法は、前記第１成分から前記一時的公開鍵を取り出すステップと、検証の相等
性を、前記一時的公開鍵と、前記長期公開鍵と、前記群の生成子に対する群演算の結合と
して確立するステップであって、前記群演算の少なくとも１つは、前記定義された最大ビ
ット長より短い縮小ビット長を有するビット列により表現されるオペランドを含むステッ
プと、前記結合を計算して、前記相等性が成立すれば前記署名を承認し、前記相等性が成
立しないときは前記署名を拒絶するステップを備える方法。
（項目１７）
縮小ビット長の前記群演算は、前記一時的公開鍵に対して行われる項目１６に記載の
方法。
（項目１８）
前記一時的公開鍵と前記長期公開鍵に対する群演算はそれぞれ、縮小ビット長のオペラ
ンドを含む項目１７に記載の方法。
（項目１９）
前記群は楕円曲線群であり、群演算の前記結合は、前記曲線上の点のスカラー倍の合計
である項目１６に記載の方法。
（項目２０）
前記検証の相等性は、−ｚＲ＝（ｚｕ ｍｏｄ ｎ）Ｇ＋ｗＱの形式であり、ここにお
いて、
Ｒは一時的公開鍵であり、
Ｇは群の生成子であり
Ｑは長期公開鍵であり、
ｎはそれぞれ群の位数であり、
ｚ、ｗはｔ＜ｎのビット長を有する整数であり、
ｕは前記署名成分から導出された整数であり、
Ｏは群の単位元である、項目１９に記載の方法。
（項目２１）
前記第１署名成分ｒ＝ｘ’は、ｋが一時的私的鍵であるときの、一時的公開鍵ｋＧから
導出された整数であり、前記第２署名成分はｓ＝ｋ−１（Ｈ（Ｍ）＝ｄｒ）／であり、こ
こにおいて、Ｈ（Ｍ）は前記メッセージのセキュアハッシュ関数であり、ｄは前記署名者
の長期私的鍵であり、前記整数ｕはＨ（Ｍ）／ｓ ｍｏｄ ｎに対応する項目２０に記
載の方法。
（項目２２）
前記署名成分は、ｖ−ｒ／ｓ ｍｏｄ ｎおよびｖ＝ｗ／ｚ ｍｏｄ ｎであるときの
関係ｕＧ＋ｖＱ＝Ｒを満たす項目２１に記載の方法。
（項目２３）
前記整数ｗ、ｚは、ｗとｚのビット長が所定の値のときに中断される反復アルゴリズム
の適用により得られる項目２２に記載の方法。
（項目２４）
前記所定ビット長は等しい項目２３に記載の方法。
（項目２５）
Ｇの前計算された値は、前記線形結合の計算中に利用される項目２０に記載の方法。
（項目２６）
同時倍加算演算は、前記線形結合の計算中に行われる項目２５に記載の方法。
（項目２７）
前記生成子から導出された前記点は、一対の点に分割され、前記点は前計算される請求
項２７に記載の方法。
（項目２８）
２ｉＧの値の表は計算され、前記表からの値は前記計算で使用される項目２５に記載
の方法。
（項目２９）
前記点の共線性は、前記相等性の正当性を判定するためにテストされる項目１９に記
載の方法。
（項目３０）
前記署名は、前記一時的公開鍵の複数の可能な値の１つを特定するための指標を含む請
求項１９に記載の方法。
（項目３１）
有限体の楕円曲線群における暗号演算によりメッセージの署名を生成する方法であって
、署名成分の対であって、前記成分の１つは一時的公開鍵を表現する点から導出される前
記署名成分対を生成するステップと、前記１つの成分から取り出すことができる前記公開
鍵の複数の可能な値の１つを特定するための指標を前記署名中に含めるステップを備える
方法。
（項目３２）
前記指標は、前記一時的公開鍵を表現する前記点の座標の１ビットである項目３１に
記載の方法。
（項目３３）
楕円曲線暗号システムにおいて暗号演算を使用して得られるメッセージのデジタル署名
であって、署名者の一時的公開鍵を表現する点から導出された第１成分と、前記第１成分
から取り出すことができる前記公開鍵の複数の値の１つを特定するための指標を含む署名
。
（項目３４）
前記指標は、前記点の座標の１ビットである項目３３に記載の署名。
（項目３５）
楕円曲線暗号システムにおいて暗号演算を使用して得られるメッセージのデジタル署名
を生成する方法であって、一時的公開鍵を表現する点を生成するステップと、前記点の座
標が前もって調整された基準を満たしているかどうかを判定するステップと、前記基準が
満たされないときは前記点の使用を禁止するステップを備える方法。
（項目３６）
前記点は、前記前もって調整された基準が満たされないときは修正される項目３５に
記載の方法。
（項目３７）
前記基準は、前記点の前記座標の第１ビットの値である項目３６に記載の方法。
（項目３８）
前記点は、前記基準が満たされないときは拒絶され、更なる点が生成される項目３５
に記載の方法。
発明の実施形態は、添付された図面を参照して、例としての目的のみのためにここで説
明される。
【図面の簡単な説明】
【００２６】
【図１】データ通信システムの模式的表現である。
【図２】ＥＣＤＳＡ署名方式に対して署名を行う際のステップを示しているフローチャートである。
【図３】ＥＣＤＳＡ署名の検証を示すフローチャートである。
【図４】前計算された値を使用するＥＣＤＳＡ署名の検証を示すフローチャートである。
【図５】前計算された値の表を使用するＥＣＤＳＡ署名の検証を示すフローチャートである。
【図６】署名者により提供された前計算された値を使用するＥＣＤＳＡ署名の検証を示すフローチャートである。
【図７】検証に失敗した検証者が取るステップを示すフローチャートである。
【図８】検証を簡単にするために署名者が取るステップを示すフローチャートである。
【図９】検証を簡単にするための代替署名プロトコルを示すフローチャートである。
【図１０】検証を簡単にするために、署名者により行われる代替技術を示すフローチャートである。
【図１１】代替検証ＥＣＤＳＡを示すフローチャートである。
【図１２】点の検証を示すフローチャートである。
【図１３】修正されたＰＶＳ検証プロトコルを示すフローチャートである。
【図１４】ＥＣＤＳＡ署名から公開鍵を取り出す方法を示している。
【発明を実施するための形態】
【００２７】
本発明は、デジタル署名、特にＥＣＤＳＡを使用して生成されるそれらの署名の検証を
参照して例示される。しかし、説明される技術は、楕円曲線上の点を表わす値の対の検証
が楕円曲線群以外の群に要求される他のアルゴリズムにも適用可能であることは明白であ
る。従って、好適な実施の形態に付随する説明は例としてであり、それですべてというこ
とではない。
【００２８】
ここで、図１を参照すると、データ通信システム１０は、送信線１６により相互接続さ
れている通信設備１２、１４の対を含む。通信設備１２、１４はそれぞれ、暗号モジュー
ル２０、２２を含み、それぞれのモジュールは、多数の暗号機能の１つを実践することが
できる。モジュール２０、２２はそれぞれ、通信設備１２、１４に組み込まれたＣＰＵに
より制御され、キーボード２４のような入力装置、スクリーンのような表示装置２６、お
よびメモリ２８の間のインタフェースを取る。各暗号モジュールは、乱数発生器３０と、
点の加算のような楕円曲線計算を行うための演算プロセッサ３２を含む、内部処理機能を
有する。通信設備１２、１４は、ネットワーク内で接続された汎用コンピュータまたは、
携帯電話や、ページャー、ＰＤＡなどのような特殊化された装置であることは理解されよ
う。通信リンク１６は、地上線またはワイヤレス、またはそれらの組合せであってよい。
同様に、暗号モジュール２０、２２は、別個のモジュールとして設けられてもよく、また
はＣＰＵ内のアプリケーションとして組み込まれてもよい。
【００２９】
本例においては、通信設備１２は、モジュール２０、２２内で具現化される楕円曲線暗
号システムを使用して、署名して通信設備１４に送りたいと所望しているメッセージＭを
準備する。システムのパラメータは、曲線が定義された体（本例においては、ｐが素数の
場合のＦｐ）と、基盤となる曲線Ｅと、暗号演算が行われる群を形成する元を生成し、従
って群の位数ｎと、一般的には、米国連邦情報処理標準規格（Ｆｅｄｅｒａｌ Ｉｎｆｏ
ｒｍａｔｉｏｎ Ｐｒｏｃｅｓｓｉｎｇ Ｓｔａｎｄａｒｄ（ＦＩＰＳ））１８０−２で
定義されたセキュアハッシュアルゴリズム（Ｓｅｃｕｒｅ Ｈａｓｈ Ａｌｇｏｒｉｔｈ
ｍ）（ＳＨＡ−１やＳＨＡ−２５６のような）の１つであるハッシュ関数Ｈを含み、当事
者それぞれに知られている。各元は、群における各元を表現するために十分な長さの最大
ビット長を有するビット列として表現される。
【００３０】
メッセージに署名するために取るステップは、図２に示されている。従って、最初は、
通信設備は、乱数発生器３０により整数ｋを生成し、演算装置３２を利用して、座標（ｘ
，ｙ）を有する点Ｒ＝ｋＧを計算する。通信設備１２は、座標ｘを整数ｘ’に変換して、
署名の第１成分であるｒ＝ｘ’ ｍｏｄ ｎを計算する。通信設備１２はまた、整数ｅ＝
Ｈ（Ｍ）ｍｏｄ ｎを計算し、ここでＨはセキュアハッシュ関数である。最終的に、第２
成分ｓは、ｓ＝（ｅ＋ｄｒ）／ｋ ｍｏｄ ｎとして計算される。
【００３１】
成分ｒとｓに加えて、署名は、点Ｒを表現する座標を成分ｒから取り出すための情報ｉ
を含む。この情報は、メッセージＭに埋め込まれており、またはｒとｓと共に、別の成分
として転送され、検証者が値Ｒを計算するために使用される。楕円曲線が素数の位数ｐの
体Ｆ上で定義されていて、楕円曲線Ｅは巡回的、または素数の位数ｎであるときは、ｉは
一般的には、ｙ ｍｏｄ ２、つまり、ゼロまたは１の値を取る。ｉの表示は、Ｒの取り
出し中に必要であり、ここで検証者は、ｘ＝ｒと設定する。ｎとｐは典型的な実践におい
ては非常に接近しているので、ｘ＝ｒは大いに可能性がある。ｘが与えられると、（ｘ，
ｙ）が曲線上にあるように正確に２つの値ｙがあり、これらの２つの値ｙとｙ’は、２を
法とする、異なる値を有する。このようにｉは、その値がどちらのｙが使用されるかを示
す単一ビットであり、署名には相対的にほとんど負担をかけない。
【００３２】
メッセージがいったん署名されると、そのメッセージは成分ｒ、ｓ、およびｉと共にリ
ンク１６上を、受け入れ側の通信設備１４に転送される。署名を検証するために、図３で
説明したステップが行われる。最初に、通信設備１４は、整数ｅ＝Ｈ（Ｍ） ｍｏｄ ｎ
を計算する。そして通信設備は、演算装置３２を利用して、整数ｕとｖの対を、ｕ＝ｅ／
ｓ ｍｏｄ ｎおよびｖ＝ｒ／ｓ ｍｏｄ ｎとなるように計算する。
【００３３】
通信設備１４はまた、ｗとｚの最大ビット長が、それぞれ群の元の最大ビット長よりも
短く、ｖ＝ｗ／ｘ ｍｏｄ ｎとなるように、反復アルゴリズムを使用して整数ｗとｚの
対を計算する。ｗとｚのビット長は、好ましくは、元のビット長の約半分である。そのよ
うなｗとｚは、拡張ユークリッドアルゴリズムにより都合よく見出すことができ、適切な
点、典型的には、ｗとｖが元のビット長の半分である中間で停止する。そのようなアルゴ
リズムは、例えば、ＩＳＢＮコードが０−３８７−９５２７３の、スプリンゲル（Ｓｐｒ
ｉｎｇｅｒ）により発行された、ヘンカーソン（Ｈｅｎｋｅｒｓｏｎ）、メネチェス（Ｍ
ｅｎｅｚｅｓ）、およびバンストーン（Ｖａｎｓｔｏｎｅ）による「楕円曲線暗号へのガ
イド」（Ｇｕｉｄｅ ｔｏ Ｅｌｌｉｐｔｉｃ Ｃｕｒｖｅ Ｃｒｙｐｔｏｇｒａｐｈｙ
）における、量ｋをｋ＝ｋ１＋ｋ２λ ｍｏｄ ｎと表現し、ここにおいてｋ１とｋ２の
ビット長はｎの長さの約半分であるようなアルゴリズム（Ａｌｇｏｒｉｔｈｍ）３．７４
として例示される。この方程式は、λ＝（ｋ−ｋ１）／ｋ２ ｍｏｄ ｎとして書き直せ
る。ｋ＝１およびλ＝ｖと設定することで、上記に言及したアルゴリズム（Ａｌｇｏｒｉ
ｔｈｍ）３．７４は、システムのために確立されたｎを取得するために使用でき、ｋは１
に設定され、ｖの値は可変入力として使用される。取得された出力ｋ１ｋ２は、ｗ＝１−
ｋ１を計算するために使用でき、ｋ２はｗ＝１−ｋ１およびｚ＝ｋ２として使用される。
【００３４】
このように、演算装置３２は、下記の擬似コードを実践してｗとｚの値を取得するため
に使用される。
【００３５】
ｒ０＝ｎおよびｔ０＝０とする。
ｒ１＝ｖおよびｔ１＝１とする。
【００３６】
ｉ＞１に対して、ｒｉ、ｔｉを下記のように決定する。
【００３７】
除法アルゴリズムを使用して、ｒｉを定義するｒ＿（ｉ−１）＝ｑｉｒ＿（ｉ−２）＋
ｒｉと書く。
【００３８】
ｔｉ＝ｔ＿（ｉ−１）＋ｑｉｔ＿（ｉ−２）とする。
【００３９】
ｒｉ＜ｓｑｒｔ（ｎ）＝ｎ＾（１／２）、または他の所望サイズのとき即座に停止する
。
【００４０】
ｗ＝ｒｉおよびｚ＝ｔｉと設定する。ｒｉ＝ｔｉｖ ｍｏｄ ｎであるので、ｗ＝ｚｖ
ｍｏｄ ｎ、かつ、ｖ＝ｗ／ｚ ｍｏｄ ｎ、およびｗとｚの両者は、所望のように、
ｎのビット長の約半分を有することに留意されたい。
【００４１】
通信設備１４はまた、情報ｉを利用して点Ｒに対応する値を取り出す。その最も簡単な
形式においては、これは曲線内で受け取ったｒの値を代入し、ｙの２つの可能な値のうち
どちらがビットｉにより示された符号と対応するかを判定することにより取得される。
【００４２】
取り出されたＲの値により、ＥＣＤＳＡの検証、つまり、Ｒ＝ｕＧ＋ｖＱが、改訂され
た検証により、検証相等性−ｚＲ＋（ｚｕ ｍｏｄ ｎ）Ｇ＋ｗＱ＝Ｏであることを確認
することにより行われる。検証相等性−ｚＲ＋（ｚｕ ｍｏｄ ｎ）Ｇ＋ｗＱは、一時的
公開鍵Ｒ、生成子Ｇ、および長期公開鍵Ｑのそれぞれに対する群演算の結合を含み、ｚと
ｗが相対的に小さな整数なので効率よく計算できる。下記に説明されるように、その部分
よりも合計をより迅速に計算する種々の方法が使用できる。倍数（ｚｕ ｍｏｄ ｎ）は
全サイズであるが、点が変化する寿命を有するＥＣＤＳＡのようなシステムの状況にあり
、点Ｇは固定または繰り返すものと見なしてよい。この場合、計算は、Ｇに対して前計算
された表により促進され、メモリ２８に格納され、必要なときに演算装置３２によりアク
セスされる。効率よく前計算することができない点−ｚＲとｗＱの表現は、より小さなビ
ット長を有し、そのため、計算に消費される時間はより少ない。計算が値Ｑを返すとすれ
ば、署名は検証されたとされる。
【００４３】
必要な関係を計算するために多数の異なる既知の技術が利用でき、それぞれの技術は、
演算プロセッサ３２を使用して実践できる。それぞれの技術は、速度または計算リソース
において異なる利点を有し、そのため技術または技術の組合せは、ある程度は、通信シス
テムが作動する環境に依存することになる。比較のため、ｕとｖはビット長ｔの整数であ
ると仮定する。ｕＧとｖＱを別々に計算することは、約３ｔ／２点の演算を必要とし、前
計算を仮定しない場合は、合計約３ｔ点の演算を必要とすることになる。ｕＧ＋ｖＱを計
算することは、ＥＣＤＳＡに対して通常使用される検証であるが、ｔ回の倍算を必要とし
、そのうちのいくつかは、同時に行える。ｕとｖのそれぞれは、その二進法表現において
１に設定される、約ｔ／２ビットを有すると予想される。基本二進法スカラー乗法におい
ては、１の各ビットは、別の加算を必要とする。（より高度なスカラー乗法においては、
符号付き二進数展開が使用され、加算の平均数はｔ／３となる。従って点演算の合計数は
、同時倍算がｔ回の倍算を節約するので、平均してｔ＋（２（ｔ／２））＝２ｔとなる。
）
【００４４】
改訂された検証は、別の形式ａＧ＋ｗＱ＋ｚＲの結合の計算を使用し、ここにおいてａ
は、ｚｕ ｍｏｄ ｎの値を示すビット長ｔの整数であり、ｗとｚは、ビット長が約（ｔ
／２）の整数である。このようにして検証計算をまとめると、点演算の数を削減するため
の多数の効率的な技術の使用が可能になる。これを計算する効率的な方法は、同時倍算と
加算を使用することである。例えば、関係１５Ｇ＋２０Ｑ＋１３Ｒが計算される場合は、
合計１２回の点演算に対して、２Ｑ、Ｇ＋２Ｑ、Ｇ＋２Ｑ＋Ｒ、２Ｇ＋４Ｑ＋２Ｒ、３Ｇ
＋４Ｑ＋２Ｒ、３Ｇ＋５Ｑ＋２Ｒ、３Ｇ＋５Ｑ＋３Ｒ、６Ｇ＋１０Ｑ＋６Ｒ、７Ｇ＋１０
Ｇ＋６Ｒ、１４Ｇ＋２０Ｑ＋１２Ｒ、１５Ｇ＋２０Ｑ＋１３Ｒとしての段階で行うことが
でき、各項に対して別々に一般スカラー乗法を行う方法よりも少ない。この方法がより少
ない演算を使用する主な場合は、Ｇ＋２Ｑ＋Ｒから２Ｇ＋４Ｇ＋２Ｒへ移行するときのよ
うなステップにおいて同時倍算を行うときである。各項を別々に計算する場合は、この１
回の演算に対応して、３回の演算が使用される。実際、３回同時倍算が使用されると、そ
れぞれが２回の演算を節約し、このようにして同時倍算がすべての節約を正確に反映する
ことになる。結合を計算する倍算の数は、最大倍数の長さにより支配されるので、それは
ｔである。ａに対する加算数は、平均して（ｔ／２）であり、ＱとＲに対しては、平均し
てそれぞれ（ｔ／４）である。合計は、平均して、ｔ＋（ｔ／２）＋（ｔ／４）＋（ｔ／
４）＝２ｔである。このアルゴリズムは、上記に詳述した「楕円曲線暗号へのガイド」（
Ｇｕｉｄｅ ｔｏ Ｅｌｌｉｐｔｉｃ Ｃｕｒｖｅ Ｃｒｙｐｔｏｇｒａｐｈｙ）のアル
ゴリズム（Ａｌｇｏｒｉｔｈｍ）３．４８として更に例示する。
【００４５】
以前の方法においては、これもまた２ｔ回の点演算を行うが、節約量はまったく現れず
、実際には、ＥＣＤＳＡに対して、生成子Ｇが定数であるという事実の利点を生かせる。
これにより、点Ｊ＝２＾ｍＧを予め計算し、将来の使用のためにメモリ２８に格納してお
くことが可能になる。ｍが約ｔ／２として選択されると、ａ≡ａ’＋ａ’’２＾ｍであり
、ここにおいてａ’とａ’’はビット長約（ｔ／２）の整数である。従って、ａＧ＋ｗＱ
＋ｚＲはａ’Ｇ＋ａ’’Ｊ＋ｗＱ＋ｚＲとして書ける。この形式では、すべてのスカラー
倍は、ビット長（ｔ／２）を有する。倍算の合計数は、このように（ｔ／２）となる。４
項のそれぞれは、平均して（ｔ／４）の加算に貢献する。点演算の合計数は、平均して、
ｔ／２＋４（ｔ／４）＝３ｔ／２である。
【００４６】
従って、図４に図示されているように、署名ｒ、ｓを検証するためには、受け手は、上
述のようにｗとｚを計算して、ａ’とａ’’の値を決定して、倍加算アルゴリズムを行っ
て、検証表現の値を取得する。これが群の単位元に対応するときは、検証は確認されたこ
とになる。
【００４７】
従来のｕＧ＋ｖＱを計算する検証方程式アプローチでは、倍数ｖは、一般的に全長ｔで
あり、前計算されたＧの倍数Ｊは、同時倍算の数を減少することには貢献しない。
【００４８】
従って、単一点Ｊを前計算して格納し、関係−ｚＲ＋（ｚｕ ｍｏｄ ｎ）Ｇ＋ｗＱ＝
Ｏを使用して検証することにより、ＥＣＤＳＡ署名を２５％少ない時間で検証することが
可能になる。つまり、上述した実施形態を使用して、所与の時間内に３３％多くの署名を
検証できる。
【００４９】
または、多くの実践においては、基本的にＧの２つの倍数のすべての冪乗を前計算して
格納するのに十分なメモリ３２を有しており、Ｇに対して倍算演算を行う必要が基本的に
ない。そのような状況においては、ｕＧ＋ｖＱはＱのｔ回の倍算と、ＧとＱのそれぞれに
対して（ｔ／２）回の加算で計算できる。合計は依然として２ｔ回の演算である。しかし
、図５に示されるように、ａＧの値は、メモリ３２に格納されている前計算表から検索で
き、それによりａＧ＋ｗＱ＋ｚＲの計算は、ｗＱとｚＲに対して（ｔ／２）回の倍算、Ｇ
に対しては倍算なし、Ｇに対してはｔ／２回の加算、そしてＱとＲのそれぞれに対しては
、ｔ／４回の加算で達成できる。合計では３ｔ／２回の演算である。節約量は、Ｇの１つ
の倍数のみが前計算されて格納されたときの、図４で説明したものと同じである。
【００５０】
符号付き二進数展開が使用されるときは、ｕＧ＋ｖＱの計算（いかなる前計算もなし）
は、約ｔ回の倍算と、ＧとＱのそれぞれに対して（ｔ／３）回の加算、つまり、平均して
合計（１０／６）回の演算を必要とする。符号付き二進数展開が、ａ’Ｇ＋ａ’’Ｊ＋ｗ
Ｑ＋ｚＲを求めるために使用されると、約ｔ／２回の倍算が必要となり、Ｇ、Ｊ、Ｑ、お
よびＲのそれぞれに対して（ｔ／６）回の加算が必要になり、平均して、合計（７／６）
ｔ回の演算が必要となる。上述の検証表現を使用しての検証に要する時間は、使用しない
ときに比べて７０％、つまり３０％少ない。これにより、所与の時間内においては、約４
２％多い署名を検証できる。改訂された検証表現を使用しての検証の利点は、符号付き二
進数展開と称されるスカラー乗法のより高度な技術と組み合わせられると増大する。この
技術は、今日では、楕円曲線暗号に非常に一般的に使用されており、従って、今日存在す
る実践は、検証表現の採用により恩恵を受ける可能性が高い。
【００５１】
従って、検証方程式を再編成して署名変数が縮小ビット長を有するようにすることによ
り、検証の速度は相当に増大する。
【００５２】
上記の実施形態においては、受け手は、成分ｒ、ｓについての計算を行う。図６に示さ
れるように、署名検証を更に促進するために、署名者は、公開鍵Ｑの前計算倍数を検証者
に提供するようにしてもよい。検証者は前計算された倍数を使用して、Ｑの検証を更に促
進することができる。この実施形態においては、検証者は、ａＲ＋ｂＧ＋ｃＱ＝Ｏの形式
であって、ここでａは約ｎ１／３で−ｚを表現し、ｂは約ｎで−ｚｕ ｍｏｄ ｎを表現
し、ｃは約ｎ２／３でｗを表現しているＥＣＤＳＡ検証方程式と等価な方程式を判定する
。これは、上述したように、拡張ユークリッドアルゴリズムを使用して行うことができ、
ｗのビット長がｚの２倍になったときに停止する。従って、ここで再び、署名者はメッセ
ージＭに署名し、署名成分ｒ、ｓを生成する。署名はまた、検証者に転送されるメッセー
ジ中に識別子ｉを含む。署名者は、倍数βＱを前計算し、ここにおいてスカラー倍βは、
ｎ１／３に最も近い２の冪乗であり、それを署名付きで転送する。
【００５３】
検証者が受け取ると、ｗとｚを計算する。検証者は、ｃ＝ｃ’＋ｃ’’βおよびｂ＝ｂ
’＋ｂ’’β＋ｂ’’’β＾２であると判定する。更に、Ｇが固定パラメータなので、検
証者は、βＧとβ＾２Ｇの形式のＧの倍数を前計算している。ｎがほぼ２＾ｔのときは、
検証者は、ａＲ＋ｂＧ＋ｃＱを計算するためにわずかｔ／３回の同時倍算しか必要としな
い。検証は、ａＲ＋（ｂ’＋ｂ’’β＋ｂ’’’β＾２）Ｇ＋（ｃ’＋ｃ’’β）Ｑ＝０
に基づいて進行できる。ＧとＱに対する前計算された値を使用することができ、検証を行
うことができる。検証者は、符号付きＮＡＦがａ、ｂ、およびｃを表現するために使用さ
れたと仮定すると、２ｔ／３回の点加算を必要とする。点演算の合計数はこのようにｔで
あり、それは本発明を使用し、図４で説明されたようなＱの前計算された倍数なしの３ｔ
／２と、従来の表現を使用して、Ｑのいかなる前計算された倍数なしの２ｔと比較して更
に相当な節約量を示している。
【００５４】
ＱとＧの両者の前計算された倍数があると、ｕＧ＋ｖＱは、従来の表現を使用して、（
ｔ／２）＋４（ｔ／４）＝３ｔ／２回の点演算で計算できる。Ｑの前計算された倍数が実
現可能なときは、上記の形式の署名方程式は、再び相当な利点を与えてくれる。上記の解
析は、符号付き二進数展開が使用されるときは少し修正される。
【００５５】
点の線形結合を計算する、更に他の既知の高度な技術（そのいくつかを下記で検討する
が）を使用すれば、関係を使用することにより、最大４０％少ない時間で署名の検証が行
える。
【００５６】
スカラー乗法および結合を実践するときは、ある倍数の起動中に表を作成することが一
般的である。これらの表により、スカラー倍の表現における符号付きビットは、ふつうは
ウィンドウと称される群において処理が可能になる。表は作成するためには時間とメモリ
というコストが必要だが、計算の残りの部分を促進する。通常は、表のサイズと、関連す
るウィンドウは、全体の性能に対して最適化され、それは普通は、メモリがより重要であ
るハードウェアの実践を除いては、必要な時間を最小化することを意味する。そのような
技術に対する完全な説明と実践アルゴリズムは、上記に言及した「楕円曲線暗号へのガイ
ド」（Ｇｕｉｄｅ ｔｏ Ｅｌｌｉｐｔｉｃ Ｃｕｒｖｅ Ｃｒｙｐｔｏｇｒａｐｙ）の
９８頁とそれ以降で見出すことができる。
【００５７】
スカラー乗法のためのそのような起動時の表は、または、ウィンドウ化技術は、上述し
た実施形態における改訂検証方程式と組み合わせることができる。そのような表を使用す
るときは、節約量は上記に概観を示したものとほぼ同じである。節約量が類似している理
由は下記の単純な事実による。表は、繰返し起こる可能性のある加算のあるパターンを前
計算することにより加算の数を削減するが、改訂検証関係を使用すると、より多くの同時
倍算を提供することにより倍算数を削減する。実際、表を使用すると、加算数は減少し、
改訂検証関係を使用することによる倍算の更なる削減は更に大きな影響を与える。
【００５８】
例として、表への一般的なアプローチは、サイズ５の符号付きＮＡＦウィンドウを使用
することである。そのようなＮＡＦの表を構築するには１１回の加算が必要である。署名
者がＱの前計算された倍数ｕＱを送る上記の例では、検証者は、３３回の加算で、Ｒ、Ｑ
およびｕＱの表を構築できる。検証者は、Ｇ用に構築された必要な表を既に所有している
ことが仮定されている。前計算された倍算を使用すると、検証者は、検証のためにわずか
ｔ／６回の同時加算が必要となるだけである。これらの節約量は、鍵のサイズが大きくな
るにつれて向上する。今日使用されている最大の鍵サイズに対しては、節約量はほぼ４０
％である。そのような表は当然ながら必要なメモリ３２を必要とするので、適切な技術の
選択は利用できるハードウェアに依存することになる。
【００５９】
同様に、結合疎形式（ｊｏｉｎｔ ｓｐａｒｓｅ ｆｏｒｍｓ）として知られている計
算技術を計算効率のために使用することができる。
【００６０】
上述したように、整数ｗ、ｚは、拡張ユークリッドアルゴリズムを使用して求めた。ま
たは、連分数アプローチを含む反復アルゴリズムを使用することもできる。基本的に、拡
張ユークリッドアルゴリズムと等価である連分数アプローチにおいては、分数ｖ／ｎへ部
分収束するγ／δを、δがほぼｎ１／２になるように求める。部分収束の特性は｜γ／δ
−ｖ／ｎ｜＜１／δ＾２である。この不等式にδｎを乗算すると、｜γｎ−ｖδ｜＜ｎ／
δとなり、ほぼｎ１／２となる。ここでｚ＝δおよびｗ＝γｎ−ｖδを設定する。ｖ＝ｗ
／ｚ ｍｏｄ ｎであることを調べるのは容易であり、ｗとｚが所望のサイズを有してい
ることに留意されたい。
【００６１】
上記に示したように、従来のＥＣＤＳＡ署名は、点Ｒを含まず、その代わりにｒ＝ｘ
ｍｏｄ ｎから得られた整数ｘ’を含み、ここにおいてＲ＝（ｘ，ｙ）である。従って、
検証者はＲを取り出す必要がある。
【００６２】
上述したＲを取り出す方法は、署名（ｒ、ｓ）を追加情報ｉで補足することである。こ
の情報は、例えば、メッセージに埋め込むことができる。検証者は、ｒとｉを使用してＲ
を計算できる。ｐ＞ｎのときは、ｘ’＞ｎとなる可能性は無視できる程度であり、従って
、ｒ＝ｘ−ｎである。しかし、そのようなことが起きると、検証の試みは失敗する。有効
な署名に対するそのような無視できる程度の失敗率は容認でき、または下記の方法で対処
できる。
【００６３】
図７に示すように、検証が失敗すると、検証者の負担で検証者はｘ＝ｒ＋ｎを試み、Ｒ
の別の値に対して検証を繰り返すことができ、それはこの特別な場合には成功する。検証
に連続して失敗すると、署名の拒絶という結果になる。または、図８に示すように、署名
者は、無視できる程度にしか起こらないが、いつｘ＞ｎとなるかを検出することができ、
これが起きたときには、異なるｋとＲを生成することができる。アプローチのいずれにお
いても、問題はめったにしか起きないので、性能に対する影響は無視できる。
【００６４】
Ｒを判定する他の技術も利用できる。非巡回的曲線において、余因子ｈがあり、それは
、実際には、普通２または４である。これはｘの複数の可能な値となる。ｒ＝ｘの確率は
、ほぼ１／ｈである。他の状況においては、一般的にはｒ＝ｘ−ｎ（ｈ＝２ならば）、ま
たはより一般的には、ｒ＝ｘ−ｍｎでありここで（ｍは０とｈ−１の間）である。ｐはほ
ぼｈｎなので、無視できる部分を除いて、ｒに関連しているｘの可能な値がｈ個あること
になる。ｘを取り出すために、従ってＲをより容易に取り出すために、署名者は、ｍを計
算して、それを、メッセージ内、あるいは更なる署名成分として検証者に送ることができ
る。または検証者は、ｍを経験に基づいて推測できる。これはｈ＝２の場合に例示するこ
とができる。
【００６５】
ｒに対応するのは、正しいｘと偽の値ｘｆである。偽の値ｘｆは、Ｅ上でｘ座標の値に
対応しないという可能性はほぼ１／２であり、更に、Ｇの倍数に対応しないという可能性
は１／ｈである。ｘに対する２つの値のうちの１つが有効でない場合は、Ｅにないという
ことにより、またはそれが位数ｎを有していなければ、その両者は効率よく調べられ、そ
の値は削除できる。このように、少なくとも３／４の時間で検証者は正しいｘを容易に求
めることができる。残りの最大１／４の時間で、検証者は、２つのｘの値のいずれを試み
るべきかを知ることができない。半分の時間で検証者が検証すべきｘの値の１つを推測で
きるならばこの推測は正しくて、署名は検証されるが、残りの半分の時間で、第１署名の
試みは失敗し、検証者は他のｘの値を試みなければならない。従って、検証者が２つの署
名を検証しなければならない確率は１／８である。２つの検証のこの確率にもかかわらず
、平均検証は依然として改善される。これは、依然として平均して、検証者に時間のより
多くの節約量を提供できる。促進された検証が、通常の検証の７０％で済むが、検証の１
２．５％が促進された検証の２倍の時間がかかれば、平均時間は通常の検証の７９％とい
うことになる。更に、下記に概要を示すが、署名者はｍを検証者に提供することにより、
またはたった１つのｍしか有効でないことを確実にするために両者の値を試みる余分な作
業を行うことにより支援することができる。
【００６６】
類似の方法を、余因子ｈ＝４で利用できる。実際、ｈの値が大きいと、可能性のあるｘ
の値のそれぞれが有効である確率が低くなる。より多くの可能性のあるｘの値があるが、
解析によると、検証者に対して同様な利点があることが示される。３個のｘの偽の値があ
り、それぞれは高速チェックでは有効に見える確率は１／８である。このため、偽の値が
、高速チェックで有効なｘと見えない可能性は（７／８）３であり、約７７％である。残
りの２３％の時間のほとんどは、ｘの偽の値が１つだけ有効に見え、全署名検証を必要と
する可能性がある。
【００６７】
ｉ（必要であればｍも）を含むことは、ｒを、ｘ座標とｙ座標の第１ビットから構成さ
れるＲの圧縮バージョンと置き換えることに非常に類似している。このように、ｒの代わ
りにＲの圧縮値を送ることは、ある程度はより簡単で、偽の値を取り出す可能性は無視で
きるという利点がある。従って、図９に示されるように、署名は計算されて成分ｒ’、ｓ
の対を提供し、メッセージＭと共に受け手１４に転送される。成分ｒ’はＲのｘ座標とｙ
座標の第１ビットから構成される。成分ｓは以前と同様に計算される。
【００６８】
署名を検証するために、受け手１４は、点Ｒを成分ｒ’から直接取り出し、検証相等性
方程式−ｚＲ＋（ｚｕ ｍｏｄ ｎ）Ｇ＋ｗＱ＝Ｏを使用して、それが群の単位元に対応
することを確認する。修正された座標ｒ’の送信は、検証を簡単にするが、必要な帯域幅
も増やすことになる。
【００６９】
ある状況においては、署名者が余分なビットを送るために利用できるチャネルがない場
合がある。例えば、既存の標準規格では、署名フォーマットとメッセージフォーマットの
両者を厳格に制限して、送り手が追加情報を提供する余地がまったくないこともある。署
名者と検証者は、それにも拘わらず、両者の実践を調整し、それにより、Ｒはｒから取り
出せる。これは、署名者が、図１０に示すように、ｘの値が、予め準備された基準に準拠
することを確実にすることにより調整できる。上記の表記によれば、署名者は、Ｒ＝ｋＧ
＝（ｘ，ｙ）を通常のように計算し、上記の表記において、ｉ＝ｙ ｍｏｄ ２を計算す
る。ｉ＝１であれば、署名者は、ｋを−ｋ ｍｏｄ ｎに変更し、それにより、Ｒは−Ｒ
＝（ｘ，−ｙ）に変わり、ｉは０に変わる。検証者が署名を受け取ると、検証者はｉ＝０
と仮定して、それにより署名を取り出す。ｉの値は、このように値０として無条件に伝え
られ、署名者は、これを調整するためにほとんど無視できる程度の対価しか必要としない
。同様に、非巡回的楕円曲線においては、署名者は、ｍを無条件に送信しようとし、これ
はある程度は既に上述してある。ｈ＝２の場合は、時間の１／４であることを思い出せば
、検証者は、２つの署名を検証する必要がある。検証者がこの余分な作業を行う代わりに
、署名者は、この１／４の場合を検出でき、その代わりにｋとＲに対する別の値を試み、
基準に準拠するものが１つ見つかるまでこのプロセスを繰り返す。検証者は、２つの署名
を検証する必要なくいずれのｘを使用するかを決定することができる。
【００７０】
上述したようなＲを修正することの代替として、およびＥＣＤＳＡ標準規格に厳格に準
拠することを維持するために、ｓの値は、Ｒではなく、計算の後に修正してもよい。この
場合、署名者はＲの値は前もって調整された基準に準拠しないことに気付き、通常のよう
に、ｒとｓを生成するように進行できる。ｓが計算された後、その値は（−ｓ）に変更さ
れ、検証が、ｙの前もって調整された値を仮定して達成できることを確実にする。
【００７１】
署名者が署名（ｒ，ｓ）を、Ｒが無条件に取り出されるように選択すると、通常の検証
者は、署名を通常のように容認する。そのような署名は完全に有効である。つまり、改訂
検証は、ＥＣＤＳＡ検証の既存の実践と完全に互換性がある。無条件の効率的な署名を期
待しているが、通常に生成された署名を受け取る促進された検証者は、ｉの２つの異なる
値を試みる必要がある。促進された検証が、通常の検証の６０％の時間がかかるとすれば
、巡回的曲線（余因子ｈ＝１）においては、通常の署名を検証するために必要な平均時間
は、通常の検証の５０％（６０％）＋５０％（１２０％）＝９０％である。これは通常の
署名の時間の５０％はｉ＝０を有し、たった１回だけの無条件の促進された検証を必要と
し、他の５０％の時間は２回の促進された検証を必要とするからである。無条件に促進さ
れた検証は、署名が無条件に促進されなくても、通常の検証者よりも依然として速い。
【００７２】
従来の署名もまた、署名者または第３者により修正できて、高速検証が可能になる。こ
の場合は、署名は、要求者から第３者に転送され、この第３者が検証相等性を使用して署
名を検証する。そうすることによりＲの値が取り出される。署名は修正されて、指標Ｉを
含み、要求者に戻される。修正された署名は、高速検証署名を期待している受け手との以
降の交換に使用される。
【００７３】
上記の技術はＲを取り出して、関係−ｚＲ＋（ｚｕ ｍｏｄ ｎ）Ｇ＋ｗＱ＝Ｏを使用
して改訂検証が可能になる。しかし、ＥＣＤＳＡが検証されるときは、整数ｗとｚは、図
１１に示されるように、Ｒを取り出すことなしに使用できる。ｚＲのｘ座標と、点ｗＱ＋
（ｚｕ ｍｏｄ ｎ）Ｇのｘ’座標を計算し、これら２つのｘ座標の相等性を調べること
は可能である。Ｒのｙ座標を知らずに、ｚＲのｙ座標を直接計算することは不可能なので
、点ｚＲのｘ座標のみが計算可能である。しかし、Ｒのｙ座標を必要とせずにＲのｘ座標
からｚＲのｘ座標を計算するいくつかの既知の方法がある。そのような技術には、上記に
示した「楕円曲線暗号へのガイド」（Ｇｕｉｄｅ ｔｏ Ｅｌｌｉｐｔｉｃ Ｃｕｒｖｅ
Ｃｒｙｐｔｏｇｒａｐｈｙ）の１０２頁に説明されているモントゴメリー（Ｍｏｎｔｇ
ｏｍｅｒｙ）の方法がある。そして、ｘ座標の相等性は、ｗＱ＋（ｚｕ ｍｏｄ ｎ）Ｇ
がｚＲまたは−ｚＲに等しいことを意味し、それはｗ／ｚＱ＋ｕＧがＲまたは−Ｒに等し
いことを意味し、それはｕＧ＋ｖＱがＲと同じｘ座標を有することを意味するので、ｚＲ
とｗＱ＋（ｚｕ ｍｏｄ ｎ）Ｇのｘ座標を調べれば十分である。これはＥＣＤＳＡを首
尾よく検証するための条件である。Ｒのｘ座標は、上記に検討した方法を使用して署名成
分ｒから取り出せる。このアプローチの利点は、ｙ座標を取り出すために余分な作業を必
要としないことである。上述した以前の方法に比べて不利な点は、ｚＲをｗＱ＋（ｚｕ
ｍｏｄ ｎ）Ｇとは別に計算しなくてはならないことであり、これは、結合和の節約量の
ある部分は達成されないことを意味する。
【００７４】
上記の例では、通信設備１２、１４の対の間の署名を検証した。この技術は、図１２に
示されるように、楕円曲線鍵対（ｄ，Ｑ）の検証にも使用できる。鍵対を検証することは
、Ｑ＝ｄＧを調べることである。これは、改竄が行われていないことを保証するための安
全条件のもとで第３者により鍵対が提供されるときに重要である。ｔがｄのビット長であ
るときに、二進法の方法でのｄＧの計算は、平均して（３ｔ／２）回の演算が必要となる
。本実施形態では、通信設備１２、１４の１つは乱整数ｄを生成して、ｄ＝ｗ／ｚ ｍｏ
ｄ ｎとなるように整数ｗ、ｚの対を取得する。典型的には、整数ｗ、ｚはそれぞれ長さ
ｄの半分である。そして通信設備はｚＱ−ｗＧを計算し、結果が群の単位元０であること
を調べる。ｚＱ−ｗＧの計算は、平均してｔ回の演算を必要とし、従って、５０％の節約
量が得られる。これは、Ｇの前計算された倍数を格納するためのコストが高価である環境
においては最も有利な方法である。メモリに制限がある別の環境では、前計算された倍数
Ｈ＝ｕＧがあれば、ｄＧがｄ’Ｇ＋ｄ’’Ｈとして計算され、ここにおいてｄ＝ｄ’＋ｄ
’’ｕ ｍｏｄ ｎであり、上記とほぼ同じコストがかかる。
【００７５】
別の適用は、無条件の証明書の検証である。無条件の証明書は対（Ｐ，Ｉ）であり、こ
こでＰは楕円曲線点であり、Ｉはある単位元列である。エンティティであるボブ（Ｂｏｂ
）は、楕円曲線点である要求値ＲをＣＡに送ることにより、無条件の証明書をＣＡから取
得する。ＣＡは、無条件の証明書（Ｐ，Ｉ）を返し、更に、私的鍵再構築データ値ｓを返
す。ボブ（Ｂｏｂ）は、ｓを使用して自分の私的鍵を計算する。より一般的には、いかな
るエンティティもｓを使用して無条件の証明書がボブ（Ｂｏｂ）の要求値ＲとＣＡ公開鍵
Ｃに正確に対応していることを検証できる。これは、検証相等性Ｈ（Ｐ，Ｉ）Ｒ＋ｓＧ＝
Ｈ（Ｐ，Ｉ）Ｐ＋Ｃを調べることで行われ、ここにおいてＨはハッシュ関数である。この
方程式は、ｅＱ＋ｓＧ＝Ｃと等価であり、ここにおいてｅ＝Ｈ（Ｐ，Ｉ）およびＱ＝Ｒ−
Ｐである。この方程式の形式は標準規格ＥＣＤＳＡ検証方程式の形式に非常に類似してい
る。従って、上記で検討した技術は、この方程式の検証を促進する手段を提供するために
使用できる。これは、ｅ＝ｗ／ｚ ｍｏｄ ｎとなるように、相対的に小さな値ｗとｚを
決定することにより最適に行われ、この方程式にｚを乗算することにより、ｗＱ＋（ｓｚ
ｍｏｄ ｎ）Ｇ−ｚＣ＝Ｏが得られる。再び、この方程式のＧの倍数は全サイズである
が、一般的にはＧの倍数は前計算でき、従って、これは問題を引き起こさない。
【００７６】
この技術の利点を利用する別の変形例では、ＥＣＤＳＡ署名方程式の３つすべての倍数
を短くする。理論的には、各倍数は、ｎの長さの２／３の長さまで短くできる（ｎはＧの
位数）。この短小化を達成するための１つの方法は、３次元における短ベクトル束問題を
解くことである。そのような問題を解くためのアルゴリズムが存在する。３つすべての倍
数を短くすることは、Ｇの前計算された倍数をいずれも格納することができない場合には
非常に有益であり、Ｇの倍数の長さを可能な限り短くすることをより効率的にする。その
ような技術は、アンリコーヘン（Ｈｅｎｒｉ Ｃｏｈｅｎ）の計算法代数的数論講座（Ａ
Ｃｏｕｒｓｅ ｉｎ Ｃｏｍｐｕｔａｔｉｏｎａｌ Ａｌｇｅｂｒａｉｃ Ｎｕｍｂｅ
ｒ Ｔｈｅｏｒｙ），スプリンゲル（Ｓｐｒｉｎｇｅｒ）、ＩＳＢＮ０−３８７−５５６
４０−０に更に完全に記載されている。第２．６節と２．６節はＬＬＬアルゴリズムを記
載しており、その適用は、束における短ベクトルを見出すことであり、また、３次元束の
ためのベーユ（Ｖａｌｌｅｅ）の特別アルゴリズムに言及している。
【００７７】
この技術の別の適用は、部分メッセージ取り出しのピンチョフ−バンストーン署名（Ｐ
ｉｎｔｓｏｖ−Ｖａｎｓｔｏｎｅ Ｓｉｇｎａｔｕｒｅ（ＰＶＳ））方式の修正バージョ
ンへの適用である。ＰＶＳ署名は（ｒ，ｓ，ｔ）の３つの組から構成される。署名の検証
と、公開鍵Ｑのもとで署名からのメッセージの取り出しは、ベース生成子Ｇにより、下記
のように行われる。検証者はｅ＝Ｈ（ｒ‖ｔ）を計算し、ここにおいてＨはハッシュ関数
である。そして検証者は、Ｒ＝ｓＧ＋ｅＱを計算する。次に、検証者はＲから対称暗号鍵
Ｋを導出する。これにより、検証者は、Ｋを使用してｒを解読し、取り出されたメッセー
ジ部分ｕを得る。取り出されたメッセージは、ｔとｕのある結合である。署名はｕがある
冗長性を有していれば有効であり、この冗長性は、ｕがある所定のフォーマットに準じて
いることを検証することにより調べられる。ＰＶＳ方式は、草案標準規格ＩＥＥＥ Ｐ
１３６３ａおよびＡＮＳＩ Ｘ９．９２の一部である。
【００７８】
ＰＶＳの修正変形例においては、検証時間は整数ｗとｚを利用することにより削減でき
る。ＰＶＳの修正変形例は図１３に示されており、下記のようにして進める。通常のよう
にｅを計算した後、検証者は、ｗとｚが、ｅ＝ｗ／ｚ ｍｏｄ ｎであり、点Ｇの位数で
あるｎの長さの半分であることを見出す。そして検証者は、Ｒ＝（ｗｓ ｍｏｄ ｎ）Ｇ
＋ｚＱを計算して、以前のように手順を進めて、Ｒから鍵を導出し、その鍵でｒを解読し
、解読が正しい形式であることを検証する。検証のこの形式は、Ｑの倍数がより小さいの
でより効率的である。
【００７９】
楕円曲線群および類似の群におけるデジタル署名の署名検証を更に促進するための方法
が下記のように例示される。ＥＣＤＳＡ署名の検証は、基本的には、ａＲ＋ｂＱ＋ｃＧの
ような３個の楕円曲線点の線形結合が、無限大の点と等しいことを確認することと等価で
ある。この条件を検証する１つの方法は、点ａＲ＋ｂＱ＋ｃＧを計算し、その結果が無限
大における点Ｏ、つまり、上述したように、群の単位元であるかを調べる。この検証は、
ときどき、全体の合計を直接計算するよりもより迅速に行えることがある。例えば、ａ＝
ｂ＝ｃならば、点Ｒ、Ｑ、およびＧが共線でありその場合に限ってａＲ＋ｂＱ＋ｃＧ＝Ｏ
である。点が共線であるかを調べることは、楕円曲線点への加算よりも格段に速い。共線
性は、方程式（ｘＲ−ｘＧ）（ｙＱ−ｙＧ）−（ｘＱ−ｘＧ）（ｙＲ−ｙＧ）＝０により
、わずか２回の体の乗算により調べることができる。点の加算は、少なくも２回の体の乗
算、つまり体の平方および体の反転が必要であり、それは一般的には、約８回の体の乗算
と等価である。ａ＝ｂ＝ｃのときは、検証はこのように、点の加算にかかる時間の約１８
％で可能である。このように、この技術は、これらの条件が存在する可能性があるときは
、検証プロセスの準備ステップとして使用できる。同様に、ｂ＝ｃ＝０で、ａＲ＝Ｏの検
証を所望するときは、原理的に、ａＲ全体を計算する必要はない。その代わりに、点Ｒに
おけるａ番目の除算多項式を評価することができる。除算多項式は基本的には、点Ｒの座
標の有理関数として表現されるときは、点ａＲの座標の分母に対する帰納的公式に対応す
る。分母が０でありその場合に限りａＲ＝０であることが知られている。更に、ｂ＝ｃ＝
０であり、楕円曲線群が素数の位数ｎで巡回的であれば、ａ＝０ ｍｏｄ ｎまたはＲ＝
Ｏでありその場合に限りａＲ＝Ｏであることが知られている。この検証は、零楕円曲線点
演算が必要であるという点において比較的に即座に終了する。余因子が、ｈ＝２またはｈ
＝４のように小さいときは、点演算は、数回の非常に高速な体の演算により置き換えるこ
とができる。このように、合計の点がゼロであるような検証の特別な場合は、非常に速く
行うことができる。
【００８０】
除算多項式に対する帰納的公式に類似して、ａＲ＋ｂＱ＋ｃＧのような合計の分母に対
する帰納的公式が存在し、これらは、点ａＲ＋ｂＱ＋ｃＧの全値を計算するよりもより高
速に計算できる。群の位数ｎを知っていれば、検証時間を更に短縮できる。
【００８１】
この技術の更なる適用は、図１４に示されるように、ＥＣＤＳＡデジタル署名のみから
、公開鍵Ｑを効率的に回復することである。１つの通信設備１２が署名（ｒ，ｓ）でメッ
セージＭに署名して、署名したメッセージを通信設備１４に送りたいとする。通常は、通
信設備１４は、Ｍと（ｒ，ｓ）を通信設備に送り、しばしば公開鍵Ｑも送る。通信設備１
２がそれ自身の公開鍵を送らなかったとすると、通常は、通信設備１４は、あるネットワ
ークを介して、局所的にまたは遠隔的に格納できる、あるデータベースにおいて相手の通
信設備の公開鍵を探そうとする。これを避けるために、署名から公開鍵Ｑを取り出せると
いうことは有利である。
【００８２】
通常のＥＣＤＳＡ署名（ｒ，ｓ）が与えられれば、公開鍵である可能性があるいくつか
の候補点Ｑを取り出すことができる。第１ステップは点Ｒを取り出すことである。署名に
追加情報を含むことにより、署名されたメッセージに追加情報を含むことにより、１つの
有効なＲがｒに対応できることを保証する署名者側の追加作業により、およびｒに対応す
る多数の異なるＲ値を試みる検証者側の追加作業によるなど、促進された検証の状況にお
いてＲを見出すためのいくつかの方法が既に記載されてきた。これらの方法の１つにより
いったんＲが取り出されると、公開鍵Ｑは下記のようにして取り出すことができる。標準
規格ＥＣＤＳＡ検証方程式はＲ＝（ｅ／ｓ）Ｇ＋（ｒ／ｓ）Ｑであり、ここでｅ＝Ｈ（Ｍ
）はメッセージのハッシュ値である。Ｒとこの方程式が与えられれば、Ｑを求めることは
Ｑ＝（ｓ／ｒ）Ｒ−（ｅ／ｒ）Ｇにより行われる。
【００８３】
しかし、かなりの確率で、対（ｒ，ｓ）はある有効公開鍵を生成し、通信設備１４は、
Ｑが通信設備１２の公開鍵であるかを調べる方法が必要となる。通信設備１２は、通信設
備１４の公開鍵についてのＣＡから、別のＥＣＤＳＡ署名（ｒ’，ｓ’）のような署名を
通信設備１４が利用できるようにする。通信設備１２は、ＣＡ署名（ｒ’，ｓ’）を通信
設備１４に送ることができ、または通信設備１４はそれをあるデータベースで探すことが
できる。ＣＡの署名は、通信設備１２の名前と公開鍵Ｑ上にある。通信設備１４は、ＣＡ
の証明書を使用して、公開鍵Ｑに対応するメッセージを検証する。署名が検証されれば、
通信設備１４は、公開鍵Ｑに対する正しい値を取り出したことになる。証明書から公開鍵
を省略することは、帯域幅と格納領域を節約することになり、上述した検証プロセスは検
証時間を短縮する。
【００８４】
通信設備１４はまた、Ｑのビットの半分のような、Ｑから導出されたよりコンパクトな
値に対してＱを調べることにより、Ｑが通信設備１２の公開鍵であることを検証できる。
Ｑのコンパクトバージョンは、この後格納され、またはＱの代わりに通信され、ここで再
び格納領域と帯域幅を節約することができる。
【００８５】
検証相等性で使用される値のそれぞれが公開値であることも理解されるであろう。従っ
て、検証者が利用できる計算能力に制限がある場合は、署名者はｗとｚの値を計算して、
それをＲと共にメッセージの一部として転送することができる。受け手は、Ｒを取り出す
必要がなく、またｗとｚを計算する必要もなく、利用できる情報で検証を行うことができ
る。検証は促進されるが帯域幅は増大する。
【００８６】
上記の記載は、楕円曲線群に対するものであったが、本発明で記載された多数の方法は
、より一般的に暗号で使用される任意の群に適用でき、更に、群の元の冪乗を使用する他
の適用も可能である。例えば、本発明は、最近、楕円曲線群の代替として提案されている
、群がｇ（種）＝２の超楕円曲線の場合に使用できる。上記の技術は、ＥＣＤＳＡに類似
している、デジタル署名アルゴリズム（ＤＳＡ：Ｄｉｇｉｔａｌ Ｓｉｇｎａｔｕｒｅ
Ａｌｇｏｒｉｔｈｍ）の検証を促進するためにも使用できる。ＥＣＤＳＡと同様に、ＤＳ
Ａ署名は、整数（ｒ，ｓ）の対から構成され、ｒはＤＳＡ群の元Ｒから得られる。ＤＳＡ
群は、有限体の乗算群の部分群であると定義されている。しかし、ＥＣＤＳＡとは異なり
、ｒからＲを取り出すことは、数個の追加ビットの支援があっても達成するのが容易では
ない。従って、本技術は、値がＲで、署名されたメッセージの一部分として、または署名
の追加部分として、または値ｒに対する置き換えとして送られるならば、最も容易にＤＳ
Ａに適用できる。典型的に、整数ｒは２０バイトで表現されるが、値Ｒは１２８バイトで
表現される。結果として、結合された署名とメッセージ長は、約１０８バイト長くなる。
しかしこれは、検証を３３％促進するためには小さなコストである。
【００８７】
ＤＳＡ設定においては、ｐは大きな素数であり、ｑはより小さな素数であり、ｑは（ｐ
−１）の約数である。整数ｇは、ｇ＾ｑ＝１ ｍｏｄ ｐ、および１＜ｇ＜ｐとなるよう
に選択される。（ｑとｇは、ＥＣＤＳＡからのｎとＧにそれぞれ対応することに注意。）
【００８８】
署名者の私的鍵は、ある整数ｘであり、公開鍵はＹ＝ｇ＾ｘ ｍｏｄ ｐである。
【００８９】
署名者は署名を、通常の（ｒ，ｓ）の代わりに（Ｒ，ｓ）の形式で生成する。ここで、
Ｒ＝ｇ＾ｋ ｍｏｄ ｐであるが、ｒ＝Ｒ ｍｏｄ ｑである。両者の場合において、ｓ
＝ｋ＾（−１）（ｈ（Ｍ）＋ｘｒ） ｍｏｄ ｑであり、ここでｘは署名者の私的鍵であ
り、Ｍは署名されるメッセージであり、ｈはメッセージを要約するために使用されるハッ
シュ関数である（ＥＣＤＳＡと同様）。
【００９０】
通常のＤＳＡにおいて、検証者は、ｕ＝ｈ（Ｍ）／ｓ ｍｏｄ ｑとｖ＝ｒ／ｓ ｍｏ
ｄ ｑを計算することにより署名（ｒ，ｓ）を検証し、これはＥＣＤＳＡ実施形態におけ
るｕとｖに非常に類似しており、そしてｒ＝（ｇ＾ｕＹ＾ｖ ｍｏｄ ｐ） ｍｏｄ ｑ
を調べる。本実施形態においては、検証者は、ｑの約半分の長さのビット長のｗとｚを見
出し、それによりｗとｚのそれぞれは、ｖ＝ｗ／ｚ ｍｏｄ ｑとなるように、ほぼｓｑ
ｒｔ（ｑ）となる。これは、ｎをｑと置き換えて、上記のＥＣＤＳＡ実施形態と同じ方法
で行われる。そして検証者は、Ｒ＾ｚｇ＾（ｚｕ ｍｏｄ ｑ）Ｙ＾ｗ ｍｏｄ ｐを計
算する。
【００９１】
この値が１に等しければ、検証者はその署名を容認し、そうでなければその署名は拒絶
される。
【００９２】
検証者は、平方乗算アルゴリズム、またはその変形例を使用してこの値を計算し、ＥＣ
ＤＳＡにおける同時倍算に類似した同時平方を利用する。ＥＣＤＳＡ高速検証の多数の方
法がＤＳＡ高速検証に使用できる。ｇの前計算された倍数、例えばｊを使用することがで
き、計算はＲ＾ｚｇ＾ｓｊ＾ｔＹ＾ｗ ｍｏｄ ｐのようになり、ここで、ｚ、ｓ、ｔ、
およびｗのそれぞれは、ｑの約半分のビット長を有する。公開鍵Ｙの前計算された冪乗が
利用できるならば、冪の指数の長さは、更に短縮することができ、それにより倍算の数を
少なくして検証をより高速にする。
【特許請求の範囲】
【請求項１】
明細書に記載の発明。
【請求項１】
明細書に記載の発明。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【公開番号】特開２０１２−２１２１６４（Ｐ２０１２−２１２１６４Ａ）
【公開日】平成２４年１１月１日（２０１２．１１．１）
【国際特許分類】
【外国語出願】
【出願番号】特願２０１２−１４３２７２（Ｐ２０１２−１４３２７２）
【出願日】平成２４年６月２６日（２０１２．６．２６）
【分割の表示】特願２００７−５５０６４７（Ｐ２００７−５５０６４７）の分割
【原出願日】平成１８年１月１８日（２００６．１．１８）
【出願人】（３９７０７１７９１）サーティコム コーポレーション (38)
【Ｆターム（参考）】
【公開日】平成２４年１１月１日（２０１２．１１．１）
【国際特許分類】
【出願番号】特願２０１２−１４３２７２（Ｐ２０１２−１４３２７２）
【出願日】平成２４年６月２６日（２０１２．６．２６）
【分割の表示】特願２００７−５５０６４７（Ｐ２００７−５５０６４７）の分割
【原出願日】平成１８年１月１８日（２００６．１．１８）
【出願人】（３９７０７１７９１）サーティコム コーポレーション (38)
【Ｆターム（参考）】
[ Back to top ]