デジタル署名と公開鍵の促進された検証
【課題】有限体における群演算結合の促進された計算法を提供すること。
【解決手段】有限体における群演算結合の促進された計算法が、オペランドの少なくとも1つが、相対的に小さなビット長を有するように調整することにより提供される。楕円曲線群においては、点Rを表現する値が、2つの別の点uGとvQの合計に対応するかという検証は、縮小ビット長の整数w、zを、v=w/zとなるように導出することにより行われる。検証の相等性R=uG+vQは、縮小ビット長のzとwを使用して、−zR+(uz mod n)G+wQ=Oとして計算される。これはデジタル署名検証において有利であり、検証数の拡大が達成される。
【解決手段】有限体における群演算結合の促進された計算法が、オペランドの少なくとも1つが、相対的に小さなビット長を有するように調整することにより提供される。楕円曲線群においては、点Rを表現する値が、2つの別の点uGとvQの合計に対応するかという検証は、縮小ビット長の整数w、zを、v=w/zとなるように導出することにより行われる。検証の相等性R=uG+vQは、縮小ビット長のzとwを使用して、−zR+(uz mod n)G+wQ=Oとして計算される。これはデジタル署名検証において有利であり、検証数の拡大が達成される。
【発明の詳細な説明】
【技術分野】
【0001】
本発明は、暗号アルゴリズムにおいて使用される計算法技術に関する。
【背景技術】
【0002】
データ通信システムを通して伝達される情報の安全性とその情報が本物であることは、最も重要なことである。情報の多くは、機密性があるため、適切な制御に欠けると、経済的および個人的損失につながる可能性がある。暗号システムは、このような懸念に対処するために開発されてきた。
【0003】
公開鍵暗号により、クーリエ(メッセンジャ)などのような独立した機構を通して情報を交換する際に、他の通信相手に同一の鍵を送る必要がないデータ通信システム上での安全な通信が可能になる。公開鍵暗号は、鍵対の生成に基づいており、その対の1つは私的であり、他の1つは公開され、それらは一方向数学関数により関連付けられている。一方向関数は、基盤となる数学的構造において、公開鍵は私的鍵から容易に計算できるが、私的鍵は、公開鍵からは、現実的には突き止められないようになっている。
【0004】
より強固な一方向関数の1つに、有限体における冪乗法があり、ここにおいて整数kは私的鍵として使用され、体αの生成子は、公開鍵K=αkをもたらすために冪乗される。αとKが知られても、有限体の基盤となる数学的構造は、私的鍵kを取得することを現実的に不可能にする。公開鍵暗号は、通信者間で使用され、両者の通信者がお互いの公開鍵を交換して、相手の公開鍵を、自分の私的鍵で冪乗することにより共通鍵が確立される。公開鍵暗号は、メッセージの発信元が本物であることを証明するためにデジタル的にメッセージに署名するためにも使用できる。メッセージを書いた人間は、自分の私的鍵を使用してメッセージに署名し、メッセージが本物であることは対応する公開鍵を使用して検証できる。
【0005】
そのようなシステムの安全性は、基盤となる数学的構造に大きく依存している。離散対数システムを実践するための、最も共通して使用される構造は、有限体の乗法群の巡回的部分群であり、そこにおいては群演算は乗法であり、または楕円曲線群の巡回的部分群であり、そこにおいては群演算は加法である。
【0006】
楕円曲線Eは、(x,y)の形式の点の集合であり、xとyは、素数pを法とする整数のような、一般的にはFpと称される数であり、体Fに属しており、xとyは、Fにおけるあるaとbに対して、y2=x3+ax+bの形式を取ることができる非特異3次方程式を満たす。楕円曲線Eもまた、Oとして示される無限大における点を含む。Eの点は、群を形成するように定義できる。点Oは、群の単位元であり、Eにおける任意の点Pに対してO+P=P+O=Pが成り立つ。各点Pに対して、別の点があり、それを我々は−Pと書き、P+(−P)=P+(−P)=Oが成り立つ。Eにおける任意の3つの点P、Q、Rに対して、結合法則が成り立つ、つまり、P+(Q+R)=(P+Q)+Rが成り立つ。単位元、否定、および結合法則は、群を定義する3つの公理的性質である。楕円曲線群は、それが可換、つまりP+Q=Q+Pが成り立つという更なる性質も有する。
【0007】
スカラー乗法は、下記のように加法から定義できる。任意の点Pと任意の正の整数dに対して、dPはP+P+...+Pと定義され、ここにおいてPはd回出現する。このようにして、1P=P、2P=P+P、そして3P=P+P+Pなどとなる。我々はまた、0P=O、そして(−d)P=d(−P)と定義する。
【0008】
簡単のために、実際には、楕円曲線の巡回的部分群が代わりに使用されることがたまにあるが、巡回的である楕円曲線(下記に定義される)を扱うことが好ましい。巡回的であるということは、生成元Gがあり、Gは、群におけるすべての他の点Pが、Gの倍数である、つまり、ある正の整数dに対して、P=dGであるということである。nG=Oとなるような最小の正の整数nは、Gの(そして、Eが巡回的であるときの曲線Eの)位数である。暗号への適用においては、楕円曲線はnが素数になるように選択される。
【0009】
楕円曲線暗号システムにおいては、冪乗に類似するものは点の乗算である。このように、私的鍵は整数kであり、対応する公開鍵は点kPであり、ここにおいてPは、システムパラメータの一部であり、曲線上の予め定義された点である。シード(種子)点Pは典型的には生成子Gである。鍵対は、種々の暗号アルゴリズムで使用され、暗号化に対する共通鍵を確立し、デジタル署名を実行する。そのようなアルゴリズムは、値のセット間の定義された関係(検証相等性とも称せられる)を確認するために、値の対を比較することによる、ある演算による検証をしばしば必要とする。
【0010】
そのようなアルゴリズムの1つは、エンティティ間で交換されるメッセージ上にデジタル署名を生成するために使用される楕円曲線デジタル署名アルゴリズム(ECDSA:Elliptic Curve Digital Signature Algorithm)である。ECDSAを使用するエンティティは2つの役割、つまり、署名者と検証者の役割を有する。署名者は、1とn−1間の両端を含める範囲の整数である長期私的鍵dを選択する。整数dは秘密でなければならず、そのため、一般的にはdをランダムに選択することが好ましい。署名者は、Q=dGを計算する。点Qは、署名者の長期公開鍵であり、検証者が入手できるようになっている。一般的に、検証者は、Qが署名者であるエンティティに対応することを、CAからの証明書により一般的には確証を得る。公開鍵Qから私的鍵dを見出すことは、今日使用されている楕円曲線の選択に対して手に負えない問題であると信じられている。
【0011】
任意のメッセージMに対して、署名者は、署名を作成でき、その署名は、ECDSAの場合は、整数(r,s)の対である。検証者はいずれもメッセージMと、公開鍵Qと、署名(r,s)を受け取ることができ、それが対応する署名者により作成されたものかどうかを検証できる。これは、有効な署名(r,s)の作成は、公開鍵Qに対応する私的鍵dを知っているエンティティによってのみ可能であると信じられているからである。
【0012】
署名プロセスは下記の通りである。まず、署名者は、範囲[1,n−1]におけるある整数kを選択し、それは、セッション、または一時的な私的鍵として使用される。値kは秘密でなくてはならず、そのため、好ましくはkをランダムに選択する。そして、署名者は、座標(x,y)を有する点R=kGを計算する。次に、署名者は、xを整数x’に変換して、r=x’mod n、つまり署名者の第1座標を計算する。署名者はまた、整数e=h(M)mod nも計算しなければならず、ここでhはあるハッシュ関数であり、一般的には、米国連邦情報処理標準規格(Federal Information Processing Standard(FIPS))180−2で定義されたSecure Hash Algorithms(SHA−1またはSHA−256のような)の1つである。最後に、第2座標sはs=(e+dr)/s mod nとして計算される。成分(r,s)は、署名者によりメッセージMの署名として使用され、メッセージと共に意図された受信者に送られる。
【0013】
検証プロセスは下記の通りである。まず、検証者は、整数e=h(M) mod nを受信したメッセージから計算する。そして検証者は、u=e/s mod nおよびv=r/s mod nとなるような整数uとvを計算する。次に、検証者は、uG+vQを加算することにより得られた点Rに対応する値を計算する。これは座標(x,y)を有する。最後に、検証者は、体の元xを整数x’に変換して、r=x’mod nであるかを調べる。そうであれば、署名は検証されたことになる。
【0014】
上記から、ECDSA署名の検証は、ECDSA署名の作成の2倍の時間がかかるように見える。これは、検証プロセスは2回のスカラー乗法、つまり、uGとvQを含むが、署名は1回のみのスカラー乗法、つまりkGを含むからである。楕円曲線スカラー乗法は、これらのプロセスのほとんどの時間を消費しており、その2倍が本質的には計算時間を2倍にする。uGとvQを別々に計算するよりも時間をかけずにuG+vQを計算する方法が知られている。これらの方法のいくつかは、シャミール(Shamir)によるものであり、あるものはソリナス(Solinas)によるものであり、あるものは多様な人々によるものである。一般的に、これらの方法は、uG+vQが、kGを計算する時間の1.5倍で済むことを意味している。
【0015】
楕円曲線計算を促進するための、別の共通して使用される方法は、Gの倍数の前計算表である。そのような前計算表は、点Gは一般的には、繰返し使用される固定システムパラメータであるので時間を節約できる。最も簡単な前計算表は、jが0からtのときのすべての倍数2^j Gから構成されており、ここでtはnのビット長である。そのような前計算表があれば、任意の倍数kGの計算は、t/2の点の加算、またはそれより少ない点の加算の平均で行われる。概略的に述べれば、これはkGの計算の基本的な方法に対して3倍改善されたことを示しており、前計算の利点を明確に示している。一般的に述べれば、前計算表が大きいほど、より良く時間的に改善される。前計算表を格納するために必要なメモリは、非常に高価である。従って、改善は、より迅速な計算の利点と、より大きな表にかかる余分なコストのバランスを取らなければならない。正確なバランスは、一般的には、メモリ使用に対する速度の相対的な重要性に依存しており、それは実践方法により異なる。
【0016】
前計算はまた、公開鍵Qにも適用できる。一般的には、公開鍵Qは、Gよりもより頻繁に変化する傾向にある。それは公開鍵Qが通信者それぞれに対して異なるが、Gは、所与のシステムに対しては、固定だからである。従って、Qに対する1回の前計算のコストは、より少ない回数のQを含む繰返し起動時計算で償却される。それにも拘わらず、Qが2回以上使用されると、時間のある程度の正味の節約が達成される。頻繁に使用される公開鍵は、認証機関(CA)の公開鍵、特に、ルート、トラスト、およびアンカCA公開鍵(これらはシステムに予めインストールされる)を含む。従って、前計算は、例えば、プロトコルがCAの証明書の検証を要求するCA楕円曲線公開鍵のような場合に対しては意味がある。Gに対してのQの前計算の間の別の差は、前計算表の格納または通信のコストである。各公開鍵Qは、それ自身の前計算表を必要とする。多数の個別公開鍵のシステムにおいて、これらのコストは、より迅速な計算のいかなる利点も、鍵を格納または通信するコストにより相殺されてしまう程度に嵩むこともある。正味の利点は、実践およびシステム間で非常に異なる時間と、メモリと、帯域幅の相対的コストに依存する。ここで再び、CA公開鍵、特に、ルート、トラスト、およびアンカCA鍵の場合は、これらの鍵の数は、端末−エンティティの公開鍵よりも少ない傾向にあり、それにより、前計算のコストは、一般的に少なく、より多くの演算により償却される。
【0017】
点の倍数の表は、前計算の間でのみ有利であるだけでない。実際、そのような表は、各計算の初期段階中の、起動時に共通して生成される。これらの表による節約は本質的には、単一の計算内において発生するある繰返し演算を回避することによる節約である。単一の計算は、2つの別個の計算が共通して有するよりもより少ない内部の繰返しを有し、それにより節約された繰返し量は、前計算より少なくなる。それにも拘わらず、表の選択を賢明に行えば、単一の計算に必要な時間を削減できることが分かってきている。表は計算するのに時間がかかり、表の計算は複数の計算では償却できず、すべての計算に対しても負担を被る。経験によると、特別な表の計算は、それがなければ必要となる繰返し計算よりも時間がかからないので、特別な表は、必要な時間を削減する。通常は、最適なサイズと最適な表の選択がある。そのような表の別のコストは、表を一時的に格納するために必要なメモリである。そのようなメモリのコストは、最適な表の選択に影響を与える可能性がある。ウィンドウ化法は、作動中に計算されるそのような表の例である。
【0018】
効率的な実践に対する、上記の既知の技術のすべてにも拘わらず、更なる効率の改善が望ましい。特に、ECDSA署名の検証の効率は、特に望ましい。幅広い前計算は、ECDSA署名を迅速に生成することを可能にする。実際、ECDSA署名生成は、既知の最速デジタル署名生成アルゴリズムの1つである。一方、ECDSA署名検証は、相対的により緩慢で、ECDSAと類似する検証時間を有する他の署名アルゴリズムがある。従って、ECDSA検証時間の改善は、特に検証時間が障害となっている環境においては重要である。
【0019】
一般的には、値が2つの値の合計に対応することを検証するために計算を行うときの効率を高める必要性がある。従って、本発明の目的は、上記の不都合な点を除去あるいは緩和することである。
【発明の概要】
【課題を解決するための手段】
【0020】
一般的には、本発明は楕円曲線上の点の対のスカラー倍の合計と、曲線上の第3の点の間の関係の相等性を検証するための方法と装置を提供する。本方法は、i)ビット長がスカラーより短く、その比がスカラーに対応する整数の対を取得するステップと、ii)整数を、その関係のスカラーに代入して、項の少なくとも1つが、縮小ビット長の点の1つのスカラー倍である等価な関係を取得するステップと、iii)相等性を検証する等価関係を計算するステップを備える。
【0021】
本方法は、楕円曲線上の点Rを表わす値が、他の2つの点uGとvQの合計に対応することを検証するために使用できる。整数wとzは、wとzを表わすビット列がそれぞれ、整数uのビット列よりも短くて、v=w/z mod nとなるように決定される。そのようなwとzにより、方程式R=uG+vQが、−zR+(zu mod n)G+wQ=Oとして検証できる。
【0022】
好ましくは、wとzのビット長は、それぞれnのビット長の約半分であり、それはwとzの両者が、約n1/2より大きくはないことを意味する。
【0023】
点−zR+(zu mod n)G+wQは、zとwが相対的に小さい整数なので効率よく計算でき、合計をその部分よりも高速に計算する種々の方法が使用できる。倍数(zu mod n)は全サイズであるが、ECDSAのようなアルゴリズムの状況において、点Gは固定または繰り返えして起きてよい。この場合、計算は、Gに対して格納された表を使用することにより促進できる。Gに対する表による従来の検証に比較して、このアプローチによる時間の節約は、約40%である。
【0024】
wとzの値は、部分完成拡張ユークリッドアルゴリズム計算を使用して取得できる。または、連分数アプローチを利用してwとzを効率よく取得することができる。
【0025】
本発明の更なる形態においては、定義された最大ビット長のビット列により表現される元を有する有限体の群における暗号演算により行われるメッセージのデジタル署名を検証する方法が提供される。署名は、成分の対を備え、その1つは、署名者の一時的公開鍵から導出され、他の1つは、メッセージと、第1成分と、一時的公開鍵と、署名者の長期公開鍵を結合する。本方法は、一時的公開鍵を第1成分から取り出して、検証の相等性を、一時的公開鍵と、長期公開鍵と、定義された最大ビット長よりも短い縮小ビット長を有するビット列により表わされるオペランドを含む群演算の少なくとも1つを有する群の生成子に対する群演算の結合として確立するステップと、その結合を計算して、相等性が成立すればその署名を容認し、相等性が成立しない場合はその署名を拒絶するステップを備える。
【0026】
好ましくは、群は楕円曲線群である。更なる形態として、メッセージの署名を、有限体の楕円曲線群において暗号演算により生成する方法があり、一時的公開鍵を表わす点から導出された成分の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=(zu mod n)G+wQの形式であり、ここにおいて、
Rは一時的公開鍵であり、
Gは群の生成子であり
Qは長期公開鍵であり、
nはそれぞれ群の位数であり、
z、wはt<nのビット長を有する整数であり、
uは上記署名成分から導出された整数であり、
Oは群の単位元である、項目19に記載の方法。
(項目21)
上記第1署名成分r=x’は、kが一時的私的鍵であるときの、一時的公開鍵kGから導出された整数であり、上記第2署名成分はs=k−1(H(M)=dr)/であり、ここにおいて、H(M)は上記メッセージのセキュアハッシュ関数であり、dは上記署名者の長期私的鍵であり、上記整数uはH(M)/s mod nに対応する項目20に記載の方法。
(項目22)
上記署名成分は、v−r/s mod nおよびv=w/z mod nであるときの関係uG+vQ=Rを満たす項目21に記載の方法。
(項目23)
上記整数w、zは、wとzのビット長が所定の値のときに中断される反復アルゴリズムの適用により得られる項目22に記載の方法。
(項目24)
上記所定ビット長は等しい項目23に記載の方法。
(項目25)
Gの前計算された値は、上記線形結合の計算中に利用される項目20に記載の方法。
(項目26)
同時倍加算演算は、上記線形結合の計算中に行われる項目25に記載の方法。
(項目27)
上記生成子から導出された上記点は、一対の点に分割され、上記点は前計算される項目27に記載の方法。
(項目28)
2iGの値の表は計算され、上記表からの値は上記計算で使用される項目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に記載の方法。
【図面の簡単な説明】
【0027】
【図1】データ通信システムの模式的表現である。
【図2】ECDSA署名方式に対して署名を行う際のステップを示しているフローチャートである。
【図3】ECDSA署名の検証を示すフローチャートである。
【図4】前計算された値を使用するECDSA署名の検証を示すフローチャートである。
【図5】前計算された値の表を使用するECDSA署名の検証を示すフローチャートである。
【図6】署名者により提供された前計算された値を使用するECDSA署名の検証を示すフローチャートである。
【図7】検証に失敗した検証者が取るステップを示すフローチャートである。
【図8】検証を簡単にするために署名者が取るステップを示すフローチャートである。
【図9】検証を簡単にするための代替署名プロトコルを示すフローチャートである。
【図10】検証を簡単にするために、署名者により行われる代替技術を示すフローチャートである。
【図11】代替検証ECDSAを示すフローチャートである。
【図12】点の検証を示すフローチャートである。
【図13】修正されたPVS検証プロトコルを示すフローチャートである。
【図14】ECDSA署名から公開鍵を取り出す方法を示している。
【発明を実施するための形態】
【0028】
本発明は、デジタル署名、特にECDSAを使用して生成されるそれらの署名の検証を参照して例示される。しかし、説明される技術は、楕円曲線上の点を表わす値の対の検証が楕円曲線群以外の群に要求される他のアルゴリズムにも適用可能であることは明白である。従って、好適な実施の形態に付随する説明は例としてであり、それですべてということではない。
【0029】
ここで、図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内のアプリケーションとして組み込まれてもよい。
【0030】
本例においては、通信設備12は、モジュール20、22内で具現化される楕円曲線暗号システムを使用して、署名して通信設備14に送りたいと所望しているメッセージMを準備する。システムのパラメータは、曲線が定義された体(本例においては、pが素数の場合のFp)と、基盤となる曲線Eと、暗号演算が行われる群を形成する元を生成し、従って群の位数nと、一般的には、米国連邦情報処理標準規格(Federal Information Processing Standard(FIPS))180−2で定義されたセキュアハッシュアルゴリズム(Secure Hash Algorithm)(SHA−1やSHA−256のような)の1つであるハッシュ関数Hを含み、当事者それぞれに知られている。各元は、群における各元を表現するために十分な長さの最大ビット長を有するビット列として表現される。
【0031】
メッセージに署名するために取るステップは、図2に示されている。従って、最初は、通信設備は、乱数発生器30により整数kを生成し、演算装置32を利用して、座標(x,y)を有する点R=kGを計算する。通信設備12は、座標xを整数x’に変換して、署名の第1成分であるr=x’ mod nを計算する。通信設備12はまた、整数e=H(M)mod nを計算し、ここでHはセキュアハッシュ関数である。最終的に、第2成分sは、s=(e+dr)/k mod nとして計算される。
【0032】
成分rとsに加えて、署名は、点Rを表現する座標を成分rから取り出すための情報iを含む。この情報は、メッセージMに埋め込まれており、またはrとsと共に、別の成分として転送され、検証者が値Rを計算するために使用される。楕円曲線が素数の位数pの体F上で定義されていて、楕円曲線Eは巡回的、または素数の位数nであるときは、iは一般的には、y mod 2、つまり、ゼロまたは1の値を取る。iの表示は、Rの取り出し中に必要であり、ここで検証者は、x=rと設定する。nとpは典型的な実践においては非常に接近しているので、x=rは大いに可能性がある。xが与えられると、(x,y)が曲線上にあるように正確に2つの値yがあり、これらの2つの値yとy’は、2を法とする、異なる値を有する。このようにiは、その値がどちらのyが使用されるかを示す単一ビットであり、署名には相対的にほとんど負担をかけない。
【0033】
メッセージがいったん署名されると、そのメッセージは成分r、s、およびiと共にリンク16上を、受け入れ側の通信設備14に転送される。署名を検証するために、図3で説明したステップが行われる。最初に、通信設備14は、整数e=H(M) mod nを計算する。そして通信設備は、演算装置32を利用して、整数uとvの対を、u=e/s mod nおよびv=r/s mod nとなるように計算する。
【0034】
通信設備14はまた、wとzの最大ビット長が、それぞれ群の元の最大ビット長よりも短く、v=w/x mod nとなるように、反復アルゴリズムを使用して整数wとzの対を計算する。wとzのビット長は、好ましくは、元のビット長の約半分である。そのようなwとzは、拡張ユークリッドアルゴリズムにより都合よく見出すことができ、適切な点、典型的には、wとvが元のビット長の半分である中間で停止する。そのようなアルゴリズムは、例えば、ISBNコードが0−387−95273の、スプリンゲル(Springer)により発行された、ヘンカーソン(Henkerson)、メネチェス(Menezes)、およびバンストーン(Vanstone)による「楕円曲線暗号へのガイド」(Guide to Elliptic Curve Cryptography)における、量kをk=k1+k2λ mod nと表現し、ここにおいてk1とk2のビット長はnの長さの約半分であるようなアルゴリズム(Algorithm)3.74として例示される。この方程式は、λ=(k−k1)/k2 mod nとして書き直せる。k=1およびλ=vと設定することで、上記に言及したアルゴリズム(Algorithm)3.74は、システムのために確立されたnを取得するために使用でき、kは1に設定され、vの値は可変入力として使用される。取得された出力k1k2は、w=1−k1を計算するために使用でき、k2はw=1−k1およびz=k2として使用される。
【0035】
このように、演算装置32は、下記の擬似コードを実践してwとzの値を取得するために使用される。
【0036】
r0=nおよびt0=0とする。
r1=vおよびt1=1とする。
【0037】
i>1に対して、ri、tiを下記のように決定する。
【0038】
除法アルゴリズムを使用して、riを定義するr_(i−1)=qir_(i−2)+riと書く。
【0039】
ti=t_(i−1)+qit_(i−2)とする。
【0040】
ri<sqrt(n)=n^(1/2)、または他の所望サイズのとき即座に停止する。
【0041】
w=riおよびz=tiと設定する。ri=tiv mod nであるので、w=zv mod n、かつ、v=w/z mod n、およびwとzの両者は、所望のように、nのビット長の約半分を有することに留意されたい。
【0042】
通信設備14はまた、情報iを利用して点Rに対応する値を取り出す。その最も簡単な形式においては、これは曲線内で受け取ったrの値を代入し、yの2つの可能な値のうちどちらがビットiにより示された符号と対応するかを判定することにより取得される。
【0043】
取り出されたRの値により、ECDSAの検証、つまり、R=uG+vQが、改訂された検証により、検証相等性−zR+(zu mod n)G+wQ=Oであることを確認することにより行われる。検証相等性−zR+(zu mod n)G+wQは、一時的公開鍵R、生成子G、および長期公開鍵Qのそれぞれに対する群演算の結合を含み、zとwが相対的に小さな整数なので効率よく計算できる。下記に説明されるように、その部分よりも合計をより迅速に計算する種々の方法が使用できる。倍数(zu mod n)は全サイズであるが、点が変化する寿命を有するECDSAのようなシステムの状況にあり、点Gは固定または繰り返すものと見なしてよい。この場合、計算は、Gに対して前計算された表により促進され、メモリ28に格納され、必要なときに演算装置32によりアクセスされる。効率よく前計算することができない点−zRとwQの表現は、より小さなビット長を有し、そのため、計算に消費される時間はより少ない。計算が値Qを返すとすれば、署名は検証されたとされる。
【0044】
必要な関係を計算するために多数の異なる既知の技術が利用でき、それぞれの技術は、演算プロセッサ32を使用して実践できる。それぞれの技術は、速度または計算リソースにおいて異なる利点を有し、そのため技術または技術の組合せは、ある程度は、通信システムが作動する環境に依存することになる。比較のため、uとvはビット長tの整数であると仮定する。uGとvQを別々に計算することは、約3t/2点の演算を必要とし、前計算を仮定しない場合は、合計約3t点の演算を必要とすることになる。uG+vQを計算することは、ECDSAに対して通常使用される検証であるが、t回の倍算を必要とし、そのうちのいくつかは、同時に行える。uとvのそれぞれは、その二進法表現において1に設定される、約t/2ビットを有すると予想される。基本二進法スカラー乗法においては、1の各ビットは、別の加算を必要とする。(より高度なスカラー乗法においては、符号付き二進数展開が使用され、加算の平均数はt/3となる。従って点演算の合計数は、同時倍算がt回の倍算を節約するので、平均してt+(2(t/2))=2tとなる。)
【0045】
改訂された検証は、別の形式aG+wQ+zRの結合の計算を使用し、ここにおいてaは、zu mod nの値を示すビット長tの整数であり、wとzは、ビット長が約(t/2)の整数である。このようにして検証計算をまとめると、点演算の数を削減するための多数の効率的な技術の使用が可能になる。これを計算する効率的な方法は、同時倍算と加算を使用することである。例えば、関係15G+20Q+13Rが計算される場合は、合計12回の点演算に対して、2Q、G+2Q、G+2Q+R、2G+4Q+2R、3G+4Q+2R、3G+5Q+2R、3G+5Q+3R、6G+10Q+6R、7G+10G+6R、14G+20Q+12R、15G+20Q+13Rとしての段階で行うことができ、各項に対して別々に一般スカラー乗法を行う方法よりも少ない。この方法がより少ない演算を使用する主な場合は、G+2Q+Rから2G+4G+2Rへ移行するときのようなステップにおいて同時倍算を行うときである。各項を別々に計算する場合は、この1回の演算に対応して、3回の演算が使用される。実際、3回同時倍算が使用されると、それぞれが2回の演算を節約し、このようにして同時倍算がすべての節約を正確に反映することになる。結合を計算する倍算の数は、最大倍数の長さにより支配されるので、それはtである。aに対する加算数は、平均して(t/2)であり、QとRに対しては、平均してそれぞれ(t/4)である。合計は、平均して、t+(t/2)+(t/4)+(t/4)=2tである。このアルゴリズムは、上記に詳述した「楕円曲線暗号へのガイド」(Guide to Elliptic Curve Cryptography)のアルゴリズム(Algorithm)3.48として更に例示する。
【0046】
以前の方法においては、これもまた2t回の点演算を行うが、節約量はまったく現れず、実際には、ECDSAに対して、生成子Gが定数であるという事実の利点を生かせる。これにより、点J=2^mGを予め計算し、将来の使用のためにメモリ28に格納しておくことが可能になる。mが約t/2として選択されると、a≡a’+a’’2^mであり、ここにおいてa’とa’’はビット長約(t/2)の整数である。従って、aG+wQ+zRはa’G+a’’J+wQ+zRとして書ける。この形式では、すべてのスカラー倍は、ビット長(t/2)を有する。倍算の合計数は、このように(t/2)となる。4項のそれぞれは、平均して(t/4)の加算に貢献する。点演算の合計数は、平均して、t/2+4(t/4)=3t/2である。
【0047】
従って、図4に図示されているように、署名r、sを検証するためには、受け手は、上述のようにwとzを計算して、a’とa’’の値を決定して、倍加算アルゴリズムを行って、検証表現の値を取得する。これが群の単位元に対応するときは、検証は確認されたことになる。
【0048】
従来のuG+vQを計算する検証方程式アプローチでは、倍数vは、一般的に全長tであり、前計算されたGの倍数Jは、同時倍算の数を減少することには貢献しない。
【0049】
従って、単一点Jを前計算して格納し、関係−zR+(zu mod n)G+wQ=Oを使用して検証することにより、ECDSA署名を25%少ない時間で検証することが可能になる。つまり、上述した実施形態を使用して、所与の時間内に33%多くの署名を検証できる。
【0050】
または、多くの実践においては、基本的にGの2つの倍数のすべての冪乗を前計算して格納するのに十分なメモリ32を有しており、Gに対して倍算演算を行う必要が基本的にない。そのような状況においては、uG+vQはQのt回の倍算と、GとQのそれぞれに対して(t/2)回の加算で計算できる。合計は依然として2t回の演算である。しかし、図5に示されるように、aGの値は、メモリ32に格納されている前計算表から検索でき、それによりaG+wQ+zRの計算は、wQとzRに対して(t/2)回の倍算、Gに対しては倍算なし、Gに対してはt/2回の加算、そしてQとRのそれぞれに対しては、t/4回の加算で達成できる。合計では3t/2回の演算である。節約量は、Gの1つの倍数のみが前計算されて格納されたときの、図4で説明したものと同じである。
【0051】
符号付き二進数展開が使用されるときは、uG+vQの計算(いかなる前計算もなし)は、約t回の倍算と、GとQのそれぞれに対して(t/3)回の加算、つまり、平均して合計(10/6)回の演算を必要とする。符号付き二進数展開が、a’G+a’’J+wQ+zRを求めるために使用されると、約t/2回の倍算が必要となり、G、J、Q、およびRのそれぞれに対して(t/6)回の加算が必要になり、平均して、合計(7/6)t回の演算が必要となる。上述の検証表現を使用しての検証に要する時間は、使用しないときに比べて70%、つまり30%少ない。これにより、所与の時間内においては、約42%多い署名を検証できる。改訂された検証表現を使用しての検証の利点は、符号付き二進数展開と称されるスカラー乗法のより高度な技術と組み合わせられると増大する。この技術は、今日では、楕円曲線暗号に非常に一般的に使用されており、従って、今日存在する実践は、検証表現の採用により恩恵を受ける可能性が高い。
【0052】
従って、検証方程式を再編成して署名変数が縮小ビット長を有するようにすることにより、検証の速度は相当に増大する。
【0053】
上記の実施形態においては、受け手は、成分r、sについての計算を行う。図6に示されるように、署名検証を更に促進するために、署名者は、公開鍵Qの前計算倍数を検証者に提供するようにしてもよい。検証者は前計算された倍数を使用して、Qの検証を更に促進することができる。この実施形態においては、検証者は、aR+bG+cQ=Oの形式であって、ここでaは約n1/3で−zを表現し、bは約nで−zu mod nを表現し、cは約n2/3でwを表現しているECDSA検証方程式と等価な方程式を判定する。これは、上述したように、拡張ユークリッドアルゴリズムを使用して行うことができ、wのビット長がzの2倍になったときに停止する。従って、ここで再び、署名者はメッセージMに署名し、署名成分r、sを生成する。署名はまた、検証者に転送されるメッセージ中に識別子iを含む。署名者は、倍数βQを前計算し、ここにおいてスカラー倍βは、n1/3に最も近い2の冪乗であり、それを署名付きで転送する。
【0054】
検証者が受け取ると、wとzを計算する。検証者は、c=c’+c’’βおよびb=b’+b’’β+b’’’β^2であると判定する。更に、Gが固定パラメータなので、検証者は、βGとβ^2Gの形式のGの倍数を前計算している。nがほぼ2^tのときは、検証者は、aR+bG+cQを計算するためにわずかt/3回の同時倍算しか必要としない。検証は、aR+(b’+b’’β+b’’’β^2)G+(c’+c’’β)Q=0に基づいて進行できる。GとQに対する前計算された値を使用することができ、検証を行うことができる。検証者は、符号付きNAFがa、b、およびcを表現するために使用されたと仮定すると、2t/3回の点加算を必要とする。点演算の合計数はこのようにtであり、それは本発明を使用し、図4で説明されたようなQの前計算された倍数なしの3t/2と、従来の表現を使用して、Qのいかなる前計算された倍数なしの2tと比較して更に相当な節約量を示している。
【0055】
QとGの両者の前計算された倍数があると、uG+vQは、従来の表現を使用して、(t/2)+4(t/4)=3t/2回の点演算で計算できる。Qの前計算された倍数が実現可能なときは、上記の形式の署名方程式は、再び相当な利点を与えてくれる。上記の解析は、符号付き二進数展開が使用されるときは少し修正される。
【0056】
点の線形結合を計算する、更に他の既知の高度な技術(そのいくつかを下記で検討するが)を使用すれば、関係を使用することにより、最大40%少ない時間で署名の検証が行える。
【0057】
スカラー乗法および結合を実践するときは、ある倍数の起動中に表を作成することが一般的である。これらの表により、スカラー倍の表現における符号付きビットは、ふつうはウィンドウと称される群において処理が可能になる。表は作成するためには時間とメモリというコストが必要だが、計算の残りの部分を促進する。通常は、表のサイズと、関連するウィンドウは、全体の性能に対して最適化され、それは普通は、メモリがより重要であるハードウェアの実践を除いては、必要な時間を最小化することを意味する。そのような技術に対する完全な説明と実践アルゴリズムは、上記に言及した「楕円曲線暗号へのガイド」(Guide to Elliptic Curve Cryptograpy)の98頁とそれ以降で見出すことができる。
【0058】
スカラー乗法のためのそのような起動時の表は、または、ウィンドウ化技術は、上述した実施形態における改訂検証方程式と組み合わせることができる。そのような表を使用するときは、節約量は上記に概観を示したものとほぼ同じである。節約量が類似している理由は下記の単純な事実による。表は、繰返し起こる可能性のある加算のあるパターンを前計算することにより加算の数を削減するが、改訂検証関係を使用すると、より多くの同時倍算を提供することにより倍算数を削減する。実際、表を使用すると、加算数は減少し、改訂検証関係を使用することによる倍算の更なる削減は更に大きな影響を与える。
【0059】
例として、表への一般的なアプローチは、サイズ5の符号付きNAFウィンドウを使用することである。そのようなNAFの表を構築するには11回の加算が必要である。署名者がQの前計算された倍数uQを送る上記の例では、検証者は、33回の加算で、R、QおよびuQの表を構築できる。検証者は、G用に構築された必要な表を既に所有していることが仮定されている。前計算された倍算を使用すると、検証者は、検証のためにわずかt/6回の同時加算が必要となるだけである。これらの節約量は、鍵のサイズが大きくなるにつれて向上する。今日使用されている最大の鍵サイズに対しては、節約量はほぼ40%である。そのような表は当然ながら必要なメモリ32を必要とするので、適切な技術の選択は利用できるハードウェアに依存することになる。
【0060】
同様に、結合疎形式(joint sparse forms)として知られている計算技術を計算効率のために使用することができる。
【0061】
上述したように、整数w、zは、拡張ユークリッドアルゴリズムを使用して求めた。または、連分数アプローチを含む反復アルゴリズムを使用することもできる。基本的に、拡張ユークリッドアルゴリズムと等価である連分数アプローチにおいては、分数v/nへ部分収束するγ/δを、δがほぼn1/2になるように求める。部分収束の特性は|γ/δ−v/n|<1/δ^2である。この不等式にδnを乗算すると、|γn−vδ|<n/δとなり、ほぼn1/2となる。ここでz=δおよびw=γn−vδを設定する。v=w/z mod nであることを調べるのは容易であり、wとzが所望のサイズを有していることに留意されたい。
【0062】
上記に示したように、従来のECDSA署名は、点Rを含まず、その代わりにr=x mod nから得られた整数x’を含み、ここにおいてR=(x,y)である。従って、検証者はRを取り出す必要がある。
【0063】
上述したRを取り出す方法は、署名(r、s)を追加情報iで補足することである。この情報は、例えば、メッセージに埋め込むことができる。検証者は、rとiを使用してRを計算できる。p>nのときは、x’>nとなる可能性は無視できる程度であり、従って、r=x−nである。しかし、そのようなことが起きると、検証の試みは失敗する。有効な署名に対するそのような無視できる程度の失敗率は容認でき、または下記の方法で対処できる。
【0064】
図7に示すように、検証が失敗すると、検証者の負担で検証者はx=r+nを試み、Rの別の値に対して検証を繰り返すことができ、それはこの特別な場合には成功する。検証に連続して失敗すると、署名の拒絶という結果になる。または、図8に示すように、署名者は、無視できる程度にしか起こらないが、いつx>nとなるかを検出することができ、これが起きたときには、異なるkとRを生成することができる。アプローチのいずれにおいても、問題はめったにしか起きないので、性能に対する影響は無視できる。
【0065】
Rを判定する他の技術も利用できる。非巡回的曲線において、余因子hがあり、それは、実際には、普通2または4である。これはxの複数の可能な値となる。r=xの確率は、ほぼ1/hである。他の状況においては、一般的にはr=x−n(h=2ならば)、またはより一般的には、r=x−mnでありここで(mは0とh−1の間)である。pはほぼhnなので、無視できる部分を除いて、rに関連しているxの可能な値がh個あることになる。xを取り出すために、従ってRをより容易に取り出すために、署名者は、mを計算して、それを、メッセージ内、あるいは更なる署名成分として検証者に送ることができる。または検証者は、mを経験に基づいて推測できる。これはh=2の場合に例示することができる。
【0066】
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しか有効でないことを確実にするために両者の値を試みる余分な作業を行うことにより支援することができる。
【0067】
類似の方法を、余因子h=4で利用できる。実際、hの値が大きいと、可能性のあるxの値のそれぞれが有効である確率が低くなる。より多くの可能性のあるxの値があるが、解析によると、検証者に対して同様な利点があることが示される。3個のxの偽の値があり、それぞれは高速チェックでは有効に見える確率は1/8である。このため、偽の値が、高速チェックで有効なxと見えない可能性は(7/8)3であり、約77%である。残りの23%の時間のほとんどは、xの偽の値が1つだけ有効に見え、全署名検証を必要とする可能性がある。
【0068】
i(必要であればmも)を含むことは、rを、x座標とy座標の第1ビットから構成されるRの圧縮バージョンと置き換えることに非常に類似している。このように、rの代わりにRの圧縮値を送ることは、ある程度はより簡単で、偽の値を取り出す可能性は無視できるという利点がある。従って、図9に示されるように、署名は計算されて成分r’、sの対を提供し、メッセージMと共に受け手14に転送される。成分r’はRのx座標とy座標の第1ビットから構成される。成分sは以前と同様に計算される。
【0069】
署名を検証するために、受け手14は、点Rを成分r’から直接取り出し、検証相等性方程式−zR+(zu mod n)G+wQ=Oを使用して、それが群の単位元に対応することを確認する。修正された座標r’の送信は、検証を簡単にするが、必要な帯域幅も増やすことになる。
【0070】
ある状況においては、署名者が余分なビットを送るために利用できるチャネルがない場合がある。例えば、既存の標準規格では、署名フォーマットとメッセージフォーマットの両者を厳格に制限して、送り手が追加情報を提供する余地がまったくないこともある。署名者と検証者は、それにも拘わらず、両者の実践を調整し、それにより、Rはrから取り出せる。これは、署名者が、図10に示すように、xの値が、予め準備された基準に準拠することを確実にすることにより調整できる。上記の表記によれば、署名者は、R=kG=(x,y)を通常のように計算し、上記の表記において、i=y mod 2を計算する。i=1であれば、署名者は、kを−k mod nに変更し、それにより、Rは−R=(x,−y)に変わり、iは0に変わる。検証者が署名を受け取ると、検証者はi=0と仮定して、それにより署名を取り出す。iの値は、このように値0として無条件に伝えられ、署名者は、これを調整するためにほとんど無視できる程度の対価しか必要としない。同様に、非巡回的楕円曲線においては、署名者は、mを無条件に送信しようとし、これはある程度は既に上述してある。h=2の場合は、時間の1/4であることを思い出せば、検証者は、2つの署名を検証する必要がある。検証者がこの余分な作業を行う代わりに、署名者は、この1/4の場合を検出でき、その代わりにkとRに対する別の値を試み、基準に準拠するものが1つ見つかるまでこのプロセスを繰り返す。検証者は、2つの署名を検証する必要なくいずれのxを使用するかを決定することができる。
【0071】
上述したようなRを修正することの代替として、およびECDSA標準規格に厳格に準拠することを維持するために、sの値は、Rではなく、計算の後に修正してもよい。この場合、署名者はRの値は前もって調整された基準に準拠しないことに気付き、通常のように、rとsを生成するように進行できる。sが計算された後、その値は(−s)に変更され、検証が、yの前もって調整された値を仮定して達成できることを確実にする。
【0072】
署名者が署名(r,s)を、Rが無条件に取り出されるように選択すると、通常の検証者は、署名を通常のように容認する。そのような署名は完全に有効である。つまり、改訂検証は、ECDSA検証の既存の実践と完全に互換性がある。無条件の効率的な署名を期待しているが、通常に生成された署名を受け取る促進された検証者は、iの2つの異なる値を試みる必要がある。促進された検証が、通常の検証の60%の時間がかかるとすれば、巡回的曲線(余因子h=1)においては、通常の署名を検証するために必要な平均時間は、通常の検証の50%(60%)+50%(120%)=90%である。これは通常の署名の時間の50%はi=0を有し、たった1回だけの無条件の促進された検証を必要とし、他の50%の時間は2回の促進された検証を必要とするからである。無条件に促進された検証は、署名が無条件に促進されなくても、通常の検証者よりも依然として速い。
【0073】
従来の署名もまた、署名者または第3者により修正できて、高速検証が可能になる。この場合は、署名は、要求者から第3者に転送され、この第3者が検証相等性を使用して署名を検証する。そうすることによりRの値が取り出される。署名は修正されて、指標Iを含み、要求者に戻される。修正された署名は、高速検証署名を期待している受け手との以降の交換に使用される。
【0074】
上記の技術はRを取り出して、関係−zR+(zu mod n)G+wQ=Oを使用して改訂検証が可能になる。しかし、ECDSAが検証されるときは、整数wとzは、図11に示されるように、Rを取り出すことなしに使用できる。zRのx座標と、点wQ+(zu mod n)Gのx’座標を計算し、これら2つのx座標の相等性を調べることは可能である。Rのy座標を知らずに、zRのy座標を直接計算することは不可能なので、点zRのx座標のみが計算可能である。しかし、Rのy座標を必要とせずにRのx座標からzRのx座標を計算するいくつかの既知の方法がある。そのような技術には、上記に示した「楕円曲線暗号へのガイド」(Guide to Elliptic Curve Cryptography)の102頁に説明されているモントゴメリー(Montgomery)の方法がある。そして、x座標の相等性は、wQ+(zu mod n)GがzRまたは−zRに等しいことを意味し、それはw/zQ+uGがRまたは−Rに等しいことを意味し、それはuG+vQがRと同じx座標を有することを意味するので、zRとwQ+(zu mod n)Gのx座標を調べれば十分である。これはECDSAを首尾よく検証するための条件である。Rのx座標は、上記に検討した方法を使用して署名成分rから取り出せる。このアプローチの利点は、y座標を取り出すために余分な作業を必要としないことである。上述した以前の方法に比べて不利な点は、zRをwQ+(zu mod n)Gとは別に計算しなくてはならないことであり、これは、結合和の節約量のある部分は達成されないことを意味する。
【0075】
上記の例では、通信設備12、14の対の間の署名を検証した。この技術は、図12に示されるように、楕円曲線鍵対(d,Q)の検証にも使用できる。鍵対を検証することは、Q=dGを調べることである。これは、改竄が行われていないことを保証するための安全条件のもとで第3者により鍵対が提供されるときに重要である。tがdのビット長であるときに、二進法の方法でのdGの計算は、平均して(3t/2)回の演算が必要となる。本実施形態では、通信設備12、14の1つは乱整数dを生成して、d=w/z mod nとなるように整数w、zの対を取得する。典型的には、整数w、zはそれぞれ長さdの半分である。そして通信設備はzQ−wGを計算し、結果が群の単位元0であることを調べる。zQ−wGの計算は、平均してt回の演算を必要とし、従って、50%の節約量が得られる。これは、Gの前計算された倍数を格納するためのコストが高価である環境においては最も有利な方法である。メモリに制限がある別の環境では、前計算された倍数H=uGがあれば、dGがd’G+d’’Hとして計算され、ここにおいてd=d’+d’’u mod nであり、上記とほぼ同じコストがかかる。
【0076】
別の適用は、無条件の証明書の検証である。無条件の証明書は対(P,I)であり、ここでPは楕円曲線点であり、Iはある単位元列である。エンティティであるボブ(Bob)は、楕円曲線点である要求値RをCAに送ることにより、無条件の証明書をCAから取得する。CAは、無条件の証明書(P,I)を返し、更に、私的鍵再構築データ値sを返す。ボブ(Bob)は、sを使用して自分の私的鍵を計算する。より一般的には、いかなるエンティティもsを使用して無条件の証明書がボブ(Bob)の要求値RとCA公開鍵Cに正確に対応していることを検証できる。これは、検証相等性H(P,I)R+sG=H(P,I)P+Cを調べることで行われ、ここにおいてHはハッシュ関数である。この方程式は、eQ+sG=Cと等価であり、ここにおいてe=H(P,I)およびQ=R−Pである。この方程式の形式は標準規格ECDSA検証方程式の形式に非常に類似している。従って、上記で検討した技術は、この方程式の検証を促進する手段を提供するために使用できる。これは、e=w/z mod nとなるように、相対的に小さな値wとzを決定することにより最適に行われ、この方程式にzを乗算することにより、wQ+(sz mod n)G−zC=Oが得られる。再び、この方程式のGの倍数は全サイズであるが、一般的にはGの倍数は前計算でき、従って、これは問題を引き起こさない。
【0077】
この技術の利点を利用する別の変形例では、ECDSA署名方程式の3つすべての倍数を短くする。理論的には、各倍数は、nの長さの2/3の長さまで短くできる(nはGの位数)。この短小化を達成するための1つの方法は、3次元における短ベクトル束問題を解くことである。そのような問題を解くためのアルゴリズムが存在する。3つすべての倍数を短くすることは、Gの前計算された倍数をいずれも格納することができない場合には非常に有益であり、Gの倍数の長さを可能な限り短くすることをより効率的にする。そのような技術は、アンリコーヘン(Henri Cohen)の計算法代数的数論講座(A Course in Computational Algebraic Number Theory),スプリンゲル(Springer)、ISBN0−387−55640−0に更に完全に記載されている。第2.6節と2.6節はLLLアルゴリズムを記載しており、その適用は、束における短ベクトルを見出すことであり、また、3次元束のためのベーユ(Vallee)の特別アルゴリズムに言及している。
【0078】
この技術の別の適用は、部分メッセージ取り出しのピンチョフ−バンストーン署名(Pintsov−Vanstone Signature(PVS))方式の修正バージョンへの適用である。PVS署名は(r,s,t)の3つの組から構成される。署名の検証と、公開鍵Qのもとで署名からのメッセージの取り出しは、ベース生成子Gにより、下記のように行われる。検証者はe=H(r‖t)を計算し、ここにおいてHはハッシュ関数である。そして検証者は、R=sG+eQを計算する。次に、検証者はRから対称暗号鍵Kを導出する。これにより、検証者は、Kを使用してrを解読し、取り出されたメッセージ部分uを得る。取り出されたメッセージは、tとuのある結合である。署名はuがある冗長性を有していれば有効であり、この冗長性は、uがある所定のフォーマットに準じていることを検証することにより調べられる。PVS方式は、草案標準規格IEEE P 1363aおよびANSI X9.92の一部である。
【0079】
PVSの修正変形例においては、検証時間は整数wとzを利用することにより削減できる。PVSの修正変形例は図13に示されており、下記のようにして進める。通常のようにeを計算した後、検証者は、wとzが、e=w/z mod nであり、点Gの位数であるnの長さの半分であることを見出す。そして検証者は、R=(ws mod n)G+zQを計算して、以前のように手順を進めて、Rから鍵を導出し、その鍵でrを解読し、解読が正しい形式であることを検証する。検証のこの形式は、Qの倍数がより小さいのでより効率的である。
【0080】
楕円曲線群および類似の群におけるデジタル署名の署名検証を更に促進するための方法が下記のように例示される。ECDSA署名の検証は、基本的には、aR+bQ+cGのような3個の楕円曲線点の線形結合が、無限大の点と等しいことを確認することと等価である。この条件を検証する1つの方法は、点aR+bQ+cGを計算し、その結果が無限大における点O、つまり、上述したように、群の単位元であるかを調べる。この検証は、ときどき、全体の合計を直接計算するよりもより迅速に行えることがある。例えば、a=b=cならば、点R、Q、およびGが共線でありその場合に限ってaR+bQ+cG=Oである。点が共線であるかを調べることは、楕円曲線点への加算よりも格段に速い。共線性は、方程式(xR−xG)(yQ−yG)−(xQ−xG)(yR−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=0 mod nまたはR=Oでありその場合に限りaR=Oであることが知られている。この検証は、零楕円曲線点演算が必要であるという点において比較的に即座に終了する。余因子が、h=2またはh=4のように小さいときは、点演算は、数回の非常に高速な体の演算により置き換えることができる。このように、合計の点がゼロであるような検証の特別な場合は、非常に速く行うことができる。
【0081】
除算多項式に対する帰納的公式に類似して、aR+bQ+cGのような合計の分母に対する帰納的公式が存在し、これらは、点aR+bQ+cGの全値を計算するよりもより高速に計算できる。群の位数nを知っていれば、検証時間を更に短縮できる。
【0082】
この技術の更なる適用は、図14に示されるように、ECDSAデジタル署名のみから、公開鍵Qを効率的に回復することである。1つの通信設備12が署名(r,s)でメッセージMに署名して、署名したメッセージを通信設備14に送りたいとする。通常は、通信設備14は、Mと(r,s)を通信設備に送り、しばしば公開鍵Qも送る。通信設備12がそれ自身の公開鍵を送らなかったとすると、通常は、通信設備14は、あるネットワークを介して、局所的にまたは遠隔的に格納できる、あるデータベースにおいて相手の通信設備の公開鍵を探そうとする。これを避けるために、署名から公開鍵Qを取り出せるということは有利である。
【0083】
通常のECDSA署名(r,s)が与えられれば、公開鍵である可能性があるいくつかの候補点Qを取り出すことができる。第1ステップは点Rを取り出すことである。署名に追加情報を含むことにより、署名されたメッセージに追加情報を含むことにより、1つの有効なRがrに対応できることを保証する署名者側の追加作業により、およびrに対応する多数の異なるR値を試みる検証者側の追加作業によるなど、促進された検証の状況においてRを見出すためのいくつかの方法が既に記載されてきた。これらの方法の1つによりいったんRが取り出されると、公開鍵Qは下記のようにして取り出すことができる。標準規格ECDSA検証方程式はR=(e/s)G+(r/s)Qであり、ここでe=H(M)はメッセージのハッシュ値である。Rとこの方程式が与えられれば、Qを求めることはQ=(s/r)R−(e/r)Gにより行われる。
【0084】
しかし、かなりの確率で、対(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に対する正しい値を取り出したことになる。証明書から公開鍵を省略することは、帯域幅と格納領域を節約することになり、上述した検証プロセスは検証時間を短縮する。
【0085】
通信設備14はまた、Qのビットの半分のような、Qから導出されたよりコンパクトな値に対してQを調べることにより、Qが通信設備12の公開鍵であることを検証できる。Qのコンパクトバージョンは、この後格納され、またはQの代わりに通信され、ここで再び格納領域と帯域幅を節約することができる。
【0086】
検証相等性で使用される値のそれぞれが公開値であることも理解されるであろう。従って、検証者が利用できる計算能力に制限がある場合は、署名者はwとzの値を計算して、それをRと共にメッセージの一部として転送することができる。受け手は、Rを取り出す必要がなく、またwとzを計算する必要もなく、利用できる情報で検証を行うことができる。検証は促進されるが帯域幅は増大する。
【0087】
上記の記載は、楕円曲線群に対するものであったが、本発明で記載された多数の方法は、より一般的に暗号で使用される任意の群に適用でき、更に、群の元の冪乗を使用する他の適用も可能である。例えば、本発明は、最近、楕円曲線群の代替として提案されている、群がg(種)=2の超楕円曲線の場合に使用できる。上記の技術は、ECDSAに類似している、デジタル署名アルゴリズム(DSA:Digital Signature Algorithm)の検証を促進するためにも使用できる。ECDSAと同様に、DSA署名は、整数(r,s)の対から構成され、rはDSA群の元Rから得られる。DSA群は、有限体の乗算群の部分群であると定義されている。しかし、ECDSAとは異なり、rからRを取り出すことは、数個の追加ビットの支援があっても達成するのが容易ではない。従って、本技術は、値がRで、署名されたメッセージの一部分として、または署名の追加部分として、または値rに対する置き換えとして送られるならば、最も容易にDSAに適用できる。典型的に、整数rは20バイトで表現されるが、値Rは128バイトで表現される。結果として、結合された署名とメッセージ長は、約108バイト長くなる。しかしこれは、検証を33%促進するためには小さなコストである。
【0088】
DSA設定においては、pは大きな素数であり、qはより小さな素数であり、qは(p−1)の約数である。整数gは、g^q=1 mod p、および1<g<pとなるように選択される。(qとgは、ECDSAからのnとGにそれぞれ対応することに注意。)
【0089】
署名者の私的鍵は、ある整数xであり、公開鍵はY=g^x mod pである。
【0090】
署名者は署名を、通常の(r,s)の代わりに(R,s)の形式で生成する。ここで、R=g^k mod pであるが、r=R mod qである。両者の場合において、s=k^(−1)(h(M)+xr) mod qであり、ここでxは署名者の私的鍵であり、Mは署名されるメッセージであり、hはメッセージを要約するために使用されるハッシュ関数である(ECDSAと同様)。
【0091】
通常のDSAにおいて、検証者は、u=h(M)/s mod qとv=r/s mod qを計算することにより署名(r,s)を検証し、これはECDSA実施形態におけるuとvに非常に類似しており、そしてr=(g^uY^v mod p) mod qを調べる。本実施形態においては、検証者は、qの約半分の長さのビット長のwとzを見出し、それによりwとzのそれぞれは、v=w/z mod qとなるように、ほぼsqrt(q)となる。これは、nをqと置き換えて、上記のECDSA実施形態と同じ方法で行われる。そして検証者は、R^zg^(zu mod q)Y^w mod pを計算する。
【0092】
この値が1に等しければ、検証者はその署名を容認し、そうでなければその署名は拒絶される。
【0093】
検証者は、平方乗算アルゴリズム、またはその変形例を使用してこの値を計算し、ECDSAにおける同時倍算に類似した同時平方を利用する。ECDSA高速検証の多数の方法がDSA高速検証に使用できる。gの前計算された倍数、例えばjを使用することができ、計算はR^zg^sj^tY^w mod pのようになり、ここで、z、s、t、およびwのそれぞれは、qの約半分のビット長を有する。公開鍵Yの前計算された冪乗が利用できるならば、冪の指数の長さは、更に短縮することができ、それにより倍算の数を少なくして検証をより高速にする。
【0094】
発明の実施形態は、添付された図面を参照して、例としての目的のみのためにここで説明される。
【技術分野】
【0001】
本発明は、暗号アルゴリズムにおいて使用される計算法技術に関する。
【背景技術】
【0002】
データ通信システムを通して伝達される情報の安全性とその情報が本物であることは、最も重要なことである。情報の多くは、機密性があるため、適切な制御に欠けると、経済的および個人的損失につながる可能性がある。暗号システムは、このような懸念に対処するために開発されてきた。
【0003】
公開鍵暗号により、クーリエ(メッセンジャ)などのような独立した機構を通して情報を交換する際に、他の通信相手に同一の鍵を送る必要がないデータ通信システム上での安全な通信が可能になる。公開鍵暗号は、鍵対の生成に基づいており、その対の1つは私的であり、他の1つは公開され、それらは一方向数学関数により関連付けられている。一方向関数は、基盤となる数学的構造において、公開鍵は私的鍵から容易に計算できるが、私的鍵は、公開鍵からは、現実的には突き止められないようになっている。
【0004】
より強固な一方向関数の1つに、有限体における冪乗法があり、ここにおいて整数kは私的鍵として使用され、体αの生成子は、公開鍵K=αkをもたらすために冪乗される。αとKが知られても、有限体の基盤となる数学的構造は、私的鍵kを取得することを現実的に不可能にする。公開鍵暗号は、通信者間で使用され、両者の通信者がお互いの公開鍵を交換して、相手の公開鍵を、自分の私的鍵で冪乗することにより共通鍵が確立される。公開鍵暗号は、メッセージの発信元が本物であることを証明するためにデジタル的にメッセージに署名するためにも使用できる。メッセージを書いた人間は、自分の私的鍵を使用してメッセージに署名し、メッセージが本物であることは対応する公開鍵を使用して検証できる。
【0005】
そのようなシステムの安全性は、基盤となる数学的構造に大きく依存している。離散対数システムを実践するための、最も共通して使用される構造は、有限体の乗法群の巡回的部分群であり、そこにおいては群演算は乗法であり、または楕円曲線群の巡回的部分群であり、そこにおいては群演算は加法である。
【0006】
楕円曲線Eは、(x,y)の形式の点の集合であり、xとyは、素数pを法とする整数のような、一般的にはFpと称される数であり、体Fに属しており、xとyは、Fにおけるあるaとbに対して、y2=x3+ax+bの形式を取ることができる非特異3次方程式を満たす。楕円曲線Eもまた、Oとして示される無限大における点を含む。Eの点は、群を形成するように定義できる。点Oは、群の単位元であり、Eにおける任意の点Pに対してO+P=P+O=Pが成り立つ。各点Pに対して、別の点があり、それを我々は−Pと書き、P+(−P)=P+(−P)=Oが成り立つ。Eにおける任意の3つの点P、Q、Rに対して、結合法則が成り立つ、つまり、P+(Q+R)=(P+Q)+Rが成り立つ。単位元、否定、および結合法則は、群を定義する3つの公理的性質である。楕円曲線群は、それが可換、つまりP+Q=Q+Pが成り立つという更なる性質も有する。
【0007】
スカラー乗法は、下記のように加法から定義できる。任意の点Pと任意の正の整数dに対して、dPはP+P+...+Pと定義され、ここにおいてPはd回出現する。このようにして、1P=P、2P=P+P、そして3P=P+P+Pなどとなる。我々はまた、0P=O、そして(−d)P=d(−P)と定義する。
【0008】
簡単のために、実際には、楕円曲線の巡回的部分群が代わりに使用されることがたまにあるが、巡回的である楕円曲線(下記に定義される)を扱うことが好ましい。巡回的であるということは、生成元Gがあり、Gは、群におけるすべての他の点Pが、Gの倍数である、つまり、ある正の整数dに対して、P=dGであるということである。nG=Oとなるような最小の正の整数nは、Gの(そして、Eが巡回的であるときの曲線Eの)位数である。暗号への適用においては、楕円曲線はnが素数になるように選択される。
【0009】
楕円曲線暗号システムにおいては、冪乗に類似するものは点の乗算である。このように、私的鍵は整数kであり、対応する公開鍵は点kPであり、ここにおいてPは、システムパラメータの一部であり、曲線上の予め定義された点である。シード(種子)点Pは典型的には生成子Gである。鍵対は、種々の暗号アルゴリズムで使用され、暗号化に対する共通鍵を確立し、デジタル署名を実行する。そのようなアルゴリズムは、値のセット間の定義された関係(検証相等性とも称せられる)を確認するために、値の対を比較することによる、ある演算による検証をしばしば必要とする。
【0010】
そのようなアルゴリズムの1つは、エンティティ間で交換されるメッセージ上にデジタル署名を生成するために使用される楕円曲線デジタル署名アルゴリズム(ECDSA:Elliptic Curve Digital Signature Algorithm)である。ECDSAを使用するエンティティは2つの役割、つまり、署名者と検証者の役割を有する。署名者は、1とn−1間の両端を含める範囲の整数である長期私的鍵dを選択する。整数dは秘密でなければならず、そのため、一般的にはdをランダムに選択することが好ましい。署名者は、Q=dGを計算する。点Qは、署名者の長期公開鍵であり、検証者が入手できるようになっている。一般的に、検証者は、Qが署名者であるエンティティに対応することを、CAからの証明書により一般的には確証を得る。公開鍵Qから私的鍵dを見出すことは、今日使用されている楕円曲線の選択に対して手に負えない問題であると信じられている。
【0011】
任意のメッセージMに対して、署名者は、署名を作成でき、その署名は、ECDSAの場合は、整数(r,s)の対である。検証者はいずれもメッセージMと、公開鍵Qと、署名(r,s)を受け取ることができ、それが対応する署名者により作成されたものかどうかを検証できる。これは、有効な署名(r,s)の作成は、公開鍵Qに対応する私的鍵dを知っているエンティティによってのみ可能であると信じられているからである。
【0012】
署名プロセスは下記の通りである。まず、署名者は、範囲[1,n−1]におけるある整数kを選択し、それは、セッション、または一時的な私的鍵として使用される。値kは秘密でなくてはならず、そのため、好ましくはkをランダムに選択する。そして、署名者は、座標(x,y)を有する点R=kGを計算する。次に、署名者は、xを整数x’に変換して、r=x’mod n、つまり署名者の第1座標を計算する。署名者はまた、整数e=h(M)mod nも計算しなければならず、ここでhはあるハッシュ関数であり、一般的には、米国連邦情報処理標準規格(Federal Information Processing Standard(FIPS))180−2で定義されたSecure Hash Algorithms(SHA−1またはSHA−256のような)の1つである。最後に、第2座標sはs=(e+dr)/s mod nとして計算される。成分(r,s)は、署名者によりメッセージMの署名として使用され、メッセージと共に意図された受信者に送られる。
【0013】
検証プロセスは下記の通りである。まず、検証者は、整数e=h(M) mod nを受信したメッセージから計算する。そして検証者は、u=e/s mod nおよびv=r/s mod nとなるような整数uとvを計算する。次に、検証者は、uG+vQを加算することにより得られた点Rに対応する値を計算する。これは座標(x,y)を有する。最後に、検証者は、体の元xを整数x’に変換して、r=x’mod nであるかを調べる。そうであれば、署名は検証されたことになる。
【0014】
上記から、ECDSA署名の検証は、ECDSA署名の作成の2倍の時間がかかるように見える。これは、検証プロセスは2回のスカラー乗法、つまり、uGとvQを含むが、署名は1回のみのスカラー乗法、つまりkGを含むからである。楕円曲線スカラー乗法は、これらのプロセスのほとんどの時間を消費しており、その2倍が本質的には計算時間を2倍にする。uGとvQを別々に計算するよりも時間をかけずにuG+vQを計算する方法が知られている。これらの方法のいくつかは、シャミール(Shamir)によるものであり、あるものはソリナス(Solinas)によるものであり、あるものは多様な人々によるものである。一般的に、これらの方法は、uG+vQが、kGを計算する時間の1.5倍で済むことを意味している。
【0015】
楕円曲線計算を促進するための、別の共通して使用される方法は、Gの倍数の前計算表である。そのような前計算表は、点Gは一般的には、繰返し使用される固定システムパラメータであるので時間を節約できる。最も簡単な前計算表は、jが0からtのときのすべての倍数2^j Gから構成されており、ここでtはnのビット長である。そのような前計算表があれば、任意の倍数kGの計算は、t/2の点の加算、またはそれより少ない点の加算の平均で行われる。概略的に述べれば、これはkGの計算の基本的な方法に対して3倍改善されたことを示しており、前計算の利点を明確に示している。一般的に述べれば、前計算表が大きいほど、より良く時間的に改善される。前計算表を格納するために必要なメモリは、非常に高価である。従って、改善は、より迅速な計算の利点と、より大きな表にかかる余分なコストのバランスを取らなければならない。正確なバランスは、一般的には、メモリ使用に対する速度の相対的な重要性に依存しており、それは実践方法により異なる。
【0016】
前計算はまた、公開鍵Qにも適用できる。一般的には、公開鍵Qは、Gよりもより頻繁に変化する傾向にある。それは公開鍵Qが通信者それぞれに対して異なるが、Gは、所与のシステムに対しては、固定だからである。従って、Qに対する1回の前計算のコストは、より少ない回数のQを含む繰返し起動時計算で償却される。それにも拘わらず、Qが2回以上使用されると、時間のある程度の正味の節約が達成される。頻繁に使用される公開鍵は、認証機関(CA)の公開鍵、特に、ルート、トラスト、およびアンカCA公開鍵(これらはシステムに予めインストールされる)を含む。従って、前計算は、例えば、プロトコルがCAの証明書の検証を要求するCA楕円曲線公開鍵のような場合に対しては意味がある。Gに対してのQの前計算の間の別の差は、前計算表の格納または通信のコストである。各公開鍵Qは、それ自身の前計算表を必要とする。多数の個別公開鍵のシステムにおいて、これらのコストは、より迅速な計算のいかなる利点も、鍵を格納または通信するコストにより相殺されてしまう程度に嵩むこともある。正味の利点は、実践およびシステム間で非常に異なる時間と、メモリと、帯域幅の相対的コストに依存する。ここで再び、CA公開鍵、特に、ルート、トラスト、およびアンカCA鍵の場合は、これらの鍵の数は、端末−エンティティの公開鍵よりも少ない傾向にあり、それにより、前計算のコストは、一般的に少なく、より多くの演算により償却される。
【0017】
点の倍数の表は、前計算の間でのみ有利であるだけでない。実際、そのような表は、各計算の初期段階中の、起動時に共通して生成される。これらの表による節約は本質的には、単一の計算内において発生するある繰返し演算を回避することによる節約である。単一の計算は、2つの別個の計算が共通して有するよりもより少ない内部の繰返しを有し、それにより節約された繰返し量は、前計算より少なくなる。それにも拘わらず、表の選択を賢明に行えば、単一の計算に必要な時間を削減できることが分かってきている。表は計算するのに時間がかかり、表の計算は複数の計算では償却できず、すべての計算に対しても負担を被る。経験によると、特別な表の計算は、それがなければ必要となる繰返し計算よりも時間がかからないので、特別な表は、必要な時間を削減する。通常は、最適なサイズと最適な表の選択がある。そのような表の別のコストは、表を一時的に格納するために必要なメモリである。そのようなメモリのコストは、最適な表の選択に影響を与える可能性がある。ウィンドウ化法は、作動中に計算されるそのような表の例である。
【0018】
効率的な実践に対する、上記の既知の技術のすべてにも拘わらず、更なる効率の改善が望ましい。特に、ECDSA署名の検証の効率は、特に望ましい。幅広い前計算は、ECDSA署名を迅速に生成することを可能にする。実際、ECDSA署名生成は、既知の最速デジタル署名生成アルゴリズムの1つである。一方、ECDSA署名検証は、相対的により緩慢で、ECDSAと類似する検証時間を有する他の署名アルゴリズムがある。従って、ECDSA検証時間の改善は、特に検証時間が障害となっている環境においては重要である。
【0019】
一般的には、値が2つの値の合計に対応することを検証するために計算を行うときの効率を高める必要性がある。従って、本発明の目的は、上記の不都合な点を除去あるいは緩和することである。
【発明の概要】
【課題を解決するための手段】
【0020】
一般的には、本発明は楕円曲線上の点の対のスカラー倍の合計と、曲線上の第3の点の間の関係の相等性を検証するための方法と装置を提供する。本方法は、i)ビット長がスカラーより短く、その比がスカラーに対応する整数の対を取得するステップと、ii)整数を、その関係のスカラーに代入して、項の少なくとも1つが、縮小ビット長の点の1つのスカラー倍である等価な関係を取得するステップと、iii)相等性を検証する等価関係を計算するステップを備える。
【0021】
本方法は、楕円曲線上の点Rを表わす値が、他の2つの点uGとvQの合計に対応することを検証するために使用できる。整数wとzは、wとzを表わすビット列がそれぞれ、整数uのビット列よりも短くて、v=w/z mod nとなるように決定される。そのようなwとzにより、方程式R=uG+vQが、−zR+(zu mod n)G+wQ=Oとして検証できる。
【0022】
好ましくは、wとzのビット長は、それぞれnのビット長の約半分であり、それはwとzの両者が、約n1/2より大きくはないことを意味する。
【0023】
点−zR+(zu mod n)G+wQは、zとwが相対的に小さい整数なので効率よく計算でき、合計をその部分よりも高速に計算する種々の方法が使用できる。倍数(zu mod n)は全サイズであるが、ECDSAのようなアルゴリズムの状況において、点Gは固定または繰り返えして起きてよい。この場合、計算は、Gに対して格納された表を使用することにより促進できる。Gに対する表による従来の検証に比較して、このアプローチによる時間の節約は、約40%である。
【0024】
wとzの値は、部分完成拡張ユークリッドアルゴリズム計算を使用して取得できる。または、連分数アプローチを利用してwとzを効率よく取得することができる。
【0025】
本発明の更なる形態においては、定義された最大ビット長のビット列により表現される元を有する有限体の群における暗号演算により行われるメッセージのデジタル署名を検証する方法が提供される。署名は、成分の対を備え、その1つは、署名者の一時的公開鍵から導出され、他の1つは、メッセージと、第1成分と、一時的公開鍵と、署名者の長期公開鍵を結合する。本方法は、一時的公開鍵を第1成分から取り出して、検証の相等性を、一時的公開鍵と、長期公開鍵と、定義された最大ビット長よりも短い縮小ビット長を有するビット列により表わされるオペランドを含む群演算の少なくとも1つを有する群の生成子に対する群演算の結合として確立するステップと、その結合を計算して、相等性が成立すればその署名を容認し、相等性が成立しない場合はその署名を拒絶するステップを備える。
【0026】
好ましくは、群は楕円曲線群である。更なる形態として、メッセージの署名を、有限体の楕円曲線群において暗号演算により生成する方法があり、一時的公開鍵を表わす点から導出された成分の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=(zu mod n)G+wQの形式であり、ここにおいて、
Rは一時的公開鍵であり、
Gは群の生成子であり
Qは長期公開鍵であり、
nはそれぞれ群の位数であり、
z、wはt<nのビット長を有する整数であり、
uは上記署名成分から導出された整数であり、
Oは群の単位元である、項目19に記載の方法。
(項目21)
上記第1署名成分r=x’は、kが一時的私的鍵であるときの、一時的公開鍵kGから導出された整数であり、上記第2署名成分はs=k−1(H(M)=dr)/であり、ここにおいて、H(M)は上記メッセージのセキュアハッシュ関数であり、dは上記署名者の長期私的鍵であり、上記整数uはH(M)/s mod nに対応する項目20に記載の方法。
(項目22)
上記署名成分は、v−r/s mod nおよびv=w/z mod nであるときの関係uG+vQ=Rを満たす項目21に記載の方法。
(項目23)
上記整数w、zは、wとzのビット長が所定の値のときに中断される反復アルゴリズムの適用により得られる項目22に記載の方法。
(項目24)
上記所定ビット長は等しい項目23に記載の方法。
(項目25)
Gの前計算された値は、上記線形結合の計算中に利用される項目20に記載の方法。
(項目26)
同時倍加算演算は、上記線形結合の計算中に行われる項目25に記載の方法。
(項目27)
上記生成子から導出された上記点は、一対の点に分割され、上記点は前計算される項目27に記載の方法。
(項目28)
2iGの値の表は計算され、上記表からの値は上記計算で使用される項目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に記載の方法。
【図面の簡単な説明】
【0027】
【図1】データ通信システムの模式的表現である。
【図2】ECDSA署名方式に対して署名を行う際のステップを示しているフローチャートである。
【図3】ECDSA署名の検証を示すフローチャートである。
【図4】前計算された値を使用するECDSA署名の検証を示すフローチャートである。
【図5】前計算された値の表を使用するECDSA署名の検証を示すフローチャートである。
【図6】署名者により提供された前計算された値を使用するECDSA署名の検証を示すフローチャートである。
【図7】検証に失敗した検証者が取るステップを示すフローチャートである。
【図8】検証を簡単にするために署名者が取るステップを示すフローチャートである。
【図9】検証を簡単にするための代替署名プロトコルを示すフローチャートである。
【図10】検証を簡単にするために、署名者により行われる代替技術を示すフローチャートである。
【図11】代替検証ECDSAを示すフローチャートである。
【図12】点の検証を示すフローチャートである。
【図13】修正されたPVS検証プロトコルを示すフローチャートである。
【図14】ECDSA署名から公開鍵を取り出す方法を示している。
【発明を実施するための形態】
【0028】
本発明は、デジタル署名、特にECDSAを使用して生成されるそれらの署名の検証を参照して例示される。しかし、説明される技術は、楕円曲線上の点を表わす値の対の検証が楕円曲線群以外の群に要求される他のアルゴリズムにも適用可能であることは明白である。従って、好適な実施の形態に付随する説明は例としてであり、それですべてということではない。
【0029】
ここで、図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内のアプリケーションとして組み込まれてもよい。
【0030】
本例においては、通信設備12は、モジュール20、22内で具現化される楕円曲線暗号システムを使用して、署名して通信設備14に送りたいと所望しているメッセージMを準備する。システムのパラメータは、曲線が定義された体(本例においては、pが素数の場合のFp)と、基盤となる曲線Eと、暗号演算が行われる群を形成する元を生成し、従って群の位数nと、一般的には、米国連邦情報処理標準規格(Federal Information Processing Standard(FIPS))180−2で定義されたセキュアハッシュアルゴリズム(Secure Hash Algorithm)(SHA−1やSHA−256のような)の1つであるハッシュ関数Hを含み、当事者それぞれに知られている。各元は、群における各元を表現するために十分な長さの最大ビット長を有するビット列として表現される。
【0031】
メッセージに署名するために取るステップは、図2に示されている。従って、最初は、通信設備は、乱数発生器30により整数kを生成し、演算装置32を利用して、座標(x,y)を有する点R=kGを計算する。通信設備12は、座標xを整数x’に変換して、署名の第1成分であるr=x’ mod nを計算する。通信設備12はまた、整数e=H(M)mod nを計算し、ここでHはセキュアハッシュ関数である。最終的に、第2成分sは、s=(e+dr)/k mod nとして計算される。
【0032】
成分rとsに加えて、署名は、点Rを表現する座標を成分rから取り出すための情報iを含む。この情報は、メッセージMに埋め込まれており、またはrとsと共に、別の成分として転送され、検証者が値Rを計算するために使用される。楕円曲線が素数の位数pの体F上で定義されていて、楕円曲線Eは巡回的、または素数の位数nであるときは、iは一般的には、y mod 2、つまり、ゼロまたは1の値を取る。iの表示は、Rの取り出し中に必要であり、ここで検証者は、x=rと設定する。nとpは典型的な実践においては非常に接近しているので、x=rは大いに可能性がある。xが与えられると、(x,y)が曲線上にあるように正確に2つの値yがあり、これらの2つの値yとy’は、2を法とする、異なる値を有する。このようにiは、その値がどちらのyが使用されるかを示す単一ビットであり、署名には相対的にほとんど負担をかけない。
【0033】
メッセージがいったん署名されると、そのメッセージは成分r、s、およびiと共にリンク16上を、受け入れ側の通信設備14に転送される。署名を検証するために、図3で説明したステップが行われる。最初に、通信設備14は、整数e=H(M) mod nを計算する。そして通信設備は、演算装置32を利用して、整数uとvの対を、u=e/s mod nおよびv=r/s mod nとなるように計算する。
【0034】
通信設備14はまた、wとzの最大ビット長が、それぞれ群の元の最大ビット長よりも短く、v=w/x mod nとなるように、反復アルゴリズムを使用して整数wとzの対を計算する。wとzのビット長は、好ましくは、元のビット長の約半分である。そのようなwとzは、拡張ユークリッドアルゴリズムにより都合よく見出すことができ、適切な点、典型的には、wとvが元のビット長の半分である中間で停止する。そのようなアルゴリズムは、例えば、ISBNコードが0−387−95273の、スプリンゲル(Springer)により発行された、ヘンカーソン(Henkerson)、メネチェス(Menezes)、およびバンストーン(Vanstone)による「楕円曲線暗号へのガイド」(Guide to Elliptic Curve Cryptography)における、量kをk=k1+k2λ mod nと表現し、ここにおいてk1とk2のビット長はnの長さの約半分であるようなアルゴリズム(Algorithm)3.74として例示される。この方程式は、λ=(k−k1)/k2 mod nとして書き直せる。k=1およびλ=vと設定することで、上記に言及したアルゴリズム(Algorithm)3.74は、システムのために確立されたnを取得するために使用でき、kは1に設定され、vの値は可変入力として使用される。取得された出力k1k2は、w=1−k1を計算するために使用でき、k2はw=1−k1およびz=k2として使用される。
【0035】
このように、演算装置32は、下記の擬似コードを実践してwとzの値を取得するために使用される。
【0036】
r0=nおよびt0=0とする。
r1=vおよびt1=1とする。
【0037】
i>1に対して、ri、tiを下記のように決定する。
【0038】
除法アルゴリズムを使用して、riを定義するr_(i−1)=qir_(i−2)+riと書く。
【0039】
ti=t_(i−1)+qit_(i−2)とする。
【0040】
ri<sqrt(n)=n^(1/2)、または他の所望サイズのとき即座に停止する。
【0041】
w=riおよびz=tiと設定する。ri=tiv mod nであるので、w=zv mod n、かつ、v=w/z mod n、およびwとzの両者は、所望のように、nのビット長の約半分を有することに留意されたい。
【0042】
通信設備14はまた、情報iを利用して点Rに対応する値を取り出す。その最も簡単な形式においては、これは曲線内で受け取ったrの値を代入し、yの2つの可能な値のうちどちらがビットiにより示された符号と対応するかを判定することにより取得される。
【0043】
取り出されたRの値により、ECDSAの検証、つまり、R=uG+vQが、改訂された検証により、検証相等性−zR+(zu mod n)G+wQ=Oであることを確認することにより行われる。検証相等性−zR+(zu mod n)G+wQは、一時的公開鍵R、生成子G、および長期公開鍵Qのそれぞれに対する群演算の結合を含み、zとwが相対的に小さな整数なので効率よく計算できる。下記に説明されるように、その部分よりも合計をより迅速に計算する種々の方法が使用できる。倍数(zu mod n)は全サイズであるが、点が変化する寿命を有するECDSAのようなシステムの状況にあり、点Gは固定または繰り返すものと見なしてよい。この場合、計算は、Gに対して前計算された表により促進され、メモリ28に格納され、必要なときに演算装置32によりアクセスされる。効率よく前計算することができない点−zRとwQの表現は、より小さなビット長を有し、そのため、計算に消費される時間はより少ない。計算が値Qを返すとすれば、署名は検証されたとされる。
【0044】
必要な関係を計算するために多数の異なる既知の技術が利用でき、それぞれの技術は、演算プロセッサ32を使用して実践できる。それぞれの技術は、速度または計算リソースにおいて異なる利点を有し、そのため技術または技術の組合せは、ある程度は、通信システムが作動する環境に依存することになる。比較のため、uとvはビット長tの整数であると仮定する。uGとvQを別々に計算することは、約3t/2点の演算を必要とし、前計算を仮定しない場合は、合計約3t点の演算を必要とすることになる。uG+vQを計算することは、ECDSAに対して通常使用される検証であるが、t回の倍算を必要とし、そのうちのいくつかは、同時に行える。uとvのそれぞれは、その二進法表現において1に設定される、約t/2ビットを有すると予想される。基本二進法スカラー乗法においては、1の各ビットは、別の加算を必要とする。(より高度なスカラー乗法においては、符号付き二進数展開が使用され、加算の平均数はt/3となる。従って点演算の合計数は、同時倍算がt回の倍算を節約するので、平均してt+(2(t/2))=2tとなる。)
【0045】
改訂された検証は、別の形式aG+wQ+zRの結合の計算を使用し、ここにおいてaは、zu mod nの値を示すビット長tの整数であり、wとzは、ビット長が約(t/2)の整数である。このようにして検証計算をまとめると、点演算の数を削減するための多数の効率的な技術の使用が可能になる。これを計算する効率的な方法は、同時倍算と加算を使用することである。例えば、関係15G+20Q+13Rが計算される場合は、合計12回の点演算に対して、2Q、G+2Q、G+2Q+R、2G+4Q+2R、3G+4Q+2R、3G+5Q+2R、3G+5Q+3R、6G+10Q+6R、7G+10G+6R、14G+20Q+12R、15G+20Q+13Rとしての段階で行うことができ、各項に対して別々に一般スカラー乗法を行う方法よりも少ない。この方法がより少ない演算を使用する主な場合は、G+2Q+Rから2G+4G+2Rへ移行するときのようなステップにおいて同時倍算を行うときである。各項を別々に計算する場合は、この1回の演算に対応して、3回の演算が使用される。実際、3回同時倍算が使用されると、それぞれが2回の演算を節約し、このようにして同時倍算がすべての節約を正確に反映することになる。結合を計算する倍算の数は、最大倍数の長さにより支配されるので、それはtである。aに対する加算数は、平均して(t/2)であり、QとRに対しては、平均してそれぞれ(t/4)である。合計は、平均して、t+(t/2)+(t/4)+(t/4)=2tである。このアルゴリズムは、上記に詳述した「楕円曲線暗号へのガイド」(Guide to Elliptic Curve Cryptography)のアルゴリズム(Algorithm)3.48として更に例示する。
【0046】
以前の方法においては、これもまた2t回の点演算を行うが、節約量はまったく現れず、実際には、ECDSAに対して、生成子Gが定数であるという事実の利点を生かせる。これにより、点J=2^mGを予め計算し、将来の使用のためにメモリ28に格納しておくことが可能になる。mが約t/2として選択されると、a≡a’+a’’2^mであり、ここにおいてa’とa’’はビット長約(t/2)の整数である。従って、aG+wQ+zRはa’G+a’’J+wQ+zRとして書ける。この形式では、すべてのスカラー倍は、ビット長(t/2)を有する。倍算の合計数は、このように(t/2)となる。4項のそれぞれは、平均して(t/4)の加算に貢献する。点演算の合計数は、平均して、t/2+4(t/4)=3t/2である。
【0047】
従って、図4に図示されているように、署名r、sを検証するためには、受け手は、上述のようにwとzを計算して、a’とa’’の値を決定して、倍加算アルゴリズムを行って、検証表現の値を取得する。これが群の単位元に対応するときは、検証は確認されたことになる。
【0048】
従来のuG+vQを計算する検証方程式アプローチでは、倍数vは、一般的に全長tであり、前計算されたGの倍数Jは、同時倍算の数を減少することには貢献しない。
【0049】
従って、単一点Jを前計算して格納し、関係−zR+(zu mod n)G+wQ=Oを使用して検証することにより、ECDSA署名を25%少ない時間で検証することが可能になる。つまり、上述した実施形態を使用して、所与の時間内に33%多くの署名を検証できる。
【0050】
または、多くの実践においては、基本的にGの2つの倍数のすべての冪乗を前計算して格納するのに十分なメモリ32を有しており、Gに対して倍算演算を行う必要が基本的にない。そのような状況においては、uG+vQはQのt回の倍算と、GとQのそれぞれに対して(t/2)回の加算で計算できる。合計は依然として2t回の演算である。しかし、図5に示されるように、aGの値は、メモリ32に格納されている前計算表から検索でき、それによりaG+wQ+zRの計算は、wQとzRに対して(t/2)回の倍算、Gに対しては倍算なし、Gに対してはt/2回の加算、そしてQとRのそれぞれに対しては、t/4回の加算で達成できる。合計では3t/2回の演算である。節約量は、Gの1つの倍数のみが前計算されて格納されたときの、図4で説明したものと同じである。
【0051】
符号付き二進数展開が使用されるときは、uG+vQの計算(いかなる前計算もなし)は、約t回の倍算と、GとQのそれぞれに対して(t/3)回の加算、つまり、平均して合計(10/6)回の演算を必要とする。符号付き二進数展開が、a’G+a’’J+wQ+zRを求めるために使用されると、約t/2回の倍算が必要となり、G、J、Q、およびRのそれぞれに対して(t/6)回の加算が必要になり、平均して、合計(7/6)t回の演算が必要となる。上述の検証表現を使用しての検証に要する時間は、使用しないときに比べて70%、つまり30%少ない。これにより、所与の時間内においては、約42%多い署名を検証できる。改訂された検証表現を使用しての検証の利点は、符号付き二進数展開と称されるスカラー乗法のより高度な技術と組み合わせられると増大する。この技術は、今日では、楕円曲線暗号に非常に一般的に使用されており、従って、今日存在する実践は、検証表現の採用により恩恵を受ける可能性が高い。
【0052】
従って、検証方程式を再編成して署名変数が縮小ビット長を有するようにすることにより、検証の速度は相当に増大する。
【0053】
上記の実施形態においては、受け手は、成分r、sについての計算を行う。図6に示されるように、署名検証を更に促進するために、署名者は、公開鍵Qの前計算倍数を検証者に提供するようにしてもよい。検証者は前計算された倍数を使用して、Qの検証を更に促進することができる。この実施形態においては、検証者は、aR+bG+cQ=Oの形式であって、ここでaは約n1/3で−zを表現し、bは約nで−zu mod nを表現し、cは約n2/3でwを表現しているECDSA検証方程式と等価な方程式を判定する。これは、上述したように、拡張ユークリッドアルゴリズムを使用して行うことができ、wのビット長がzの2倍になったときに停止する。従って、ここで再び、署名者はメッセージMに署名し、署名成分r、sを生成する。署名はまた、検証者に転送されるメッセージ中に識別子iを含む。署名者は、倍数βQを前計算し、ここにおいてスカラー倍βは、n1/3に最も近い2の冪乗であり、それを署名付きで転送する。
【0054】
検証者が受け取ると、wとzを計算する。検証者は、c=c’+c’’βおよびb=b’+b’’β+b’’’β^2であると判定する。更に、Gが固定パラメータなので、検証者は、βGとβ^2Gの形式のGの倍数を前計算している。nがほぼ2^tのときは、検証者は、aR+bG+cQを計算するためにわずかt/3回の同時倍算しか必要としない。検証は、aR+(b’+b’’β+b’’’β^2)G+(c’+c’’β)Q=0に基づいて進行できる。GとQに対する前計算された値を使用することができ、検証を行うことができる。検証者は、符号付きNAFがa、b、およびcを表現するために使用されたと仮定すると、2t/3回の点加算を必要とする。点演算の合計数はこのようにtであり、それは本発明を使用し、図4で説明されたようなQの前計算された倍数なしの3t/2と、従来の表現を使用して、Qのいかなる前計算された倍数なしの2tと比較して更に相当な節約量を示している。
【0055】
QとGの両者の前計算された倍数があると、uG+vQは、従来の表現を使用して、(t/2)+4(t/4)=3t/2回の点演算で計算できる。Qの前計算された倍数が実現可能なときは、上記の形式の署名方程式は、再び相当な利点を与えてくれる。上記の解析は、符号付き二進数展開が使用されるときは少し修正される。
【0056】
点の線形結合を計算する、更に他の既知の高度な技術(そのいくつかを下記で検討するが)を使用すれば、関係を使用することにより、最大40%少ない時間で署名の検証が行える。
【0057】
スカラー乗法および結合を実践するときは、ある倍数の起動中に表を作成することが一般的である。これらの表により、スカラー倍の表現における符号付きビットは、ふつうはウィンドウと称される群において処理が可能になる。表は作成するためには時間とメモリというコストが必要だが、計算の残りの部分を促進する。通常は、表のサイズと、関連するウィンドウは、全体の性能に対して最適化され、それは普通は、メモリがより重要であるハードウェアの実践を除いては、必要な時間を最小化することを意味する。そのような技術に対する完全な説明と実践アルゴリズムは、上記に言及した「楕円曲線暗号へのガイド」(Guide to Elliptic Curve Cryptograpy)の98頁とそれ以降で見出すことができる。
【0058】
スカラー乗法のためのそのような起動時の表は、または、ウィンドウ化技術は、上述した実施形態における改訂検証方程式と組み合わせることができる。そのような表を使用するときは、節約量は上記に概観を示したものとほぼ同じである。節約量が類似している理由は下記の単純な事実による。表は、繰返し起こる可能性のある加算のあるパターンを前計算することにより加算の数を削減するが、改訂検証関係を使用すると、より多くの同時倍算を提供することにより倍算数を削減する。実際、表を使用すると、加算数は減少し、改訂検証関係を使用することによる倍算の更なる削減は更に大きな影響を与える。
【0059】
例として、表への一般的なアプローチは、サイズ5の符号付きNAFウィンドウを使用することである。そのようなNAFの表を構築するには11回の加算が必要である。署名者がQの前計算された倍数uQを送る上記の例では、検証者は、33回の加算で、R、QおよびuQの表を構築できる。検証者は、G用に構築された必要な表を既に所有していることが仮定されている。前計算された倍算を使用すると、検証者は、検証のためにわずかt/6回の同時加算が必要となるだけである。これらの節約量は、鍵のサイズが大きくなるにつれて向上する。今日使用されている最大の鍵サイズに対しては、節約量はほぼ40%である。そのような表は当然ながら必要なメモリ32を必要とするので、適切な技術の選択は利用できるハードウェアに依存することになる。
【0060】
同様に、結合疎形式(joint sparse forms)として知られている計算技術を計算効率のために使用することができる。
【0061】
上述したように、整数w、zは、拡張ユークリッドアルゴリズムを使用して求めた。または、連分数アプローチを含む反復アルゴリズムを使用することもできる。基本的に、拡張ユークリッドアルゴリズムと等価である連分数アプローチにおいては、分数v/nへ部分収束するγ/δを、δがほぼn1/2になるように求める。部分収束の特性は|γ/δ−v/n|<1/δ^2である。この不等式にδnを乗算すると、|γn−vδ|<n/δとなり、ほぼn1/2となる。ここでz=δおよびw=γn−vδを設定する。v=w/z mod nであることを調べるのは容易であり、wとzが所望のサイズを有していることに留意されたい。
【0062】
上記に示したように、従来のECDSA署名は、点Rを含まず、その代わりにr=x mod nから得られた整数x’を含み、ここにおいてR=(x,y)である。従って、検証者はRを取り出す必要がある。
【0063】
上述したRを取り出す方法は、署名(r、s)を追加情報iで補足することである。この情報は、例えば、メッセージに埋め込むことができる。検証者は、rとiを使用してRを計算できる。p>nのときは、x’>nとなる可能性は無視できる程度であり、従って、r=x−nである。しかし、そのようなことが起きると、検証の試みは失敗する。有効な署名に対するそのような無視できる程度の失敗率は容認でき、または下記の方法で対処できる。
【0064】
図7に示すように、検証が失敗すると、検証者の負担で検証者はx=r+nを試み、Rの別の値に対して検証を繰り返すことができ、それはこの特別な場合には成功する。検証に連続して失敗すると、署名の拒絶という結果になる。または、図8に示すように、署名者は、無視できる程度にしか起こらないが、いつx>nとなるかを検出することができ、これが起きたときには、異なるkとRを生成することができる。アプローチのいずれにおいても、問題はめったにしか起きないので、性能に対する影響は無視できる。
【0065】
Rを判定する他の技術も利用できる。非巡回的曲線において、余因子hがあり、それは、実際には、普通2または4である。これはxの複数の可能な値となる。r=xの確率は、ほぼ1/hである。他の状況においては、一般的にはr=x−n(h=2ならば)、またはより一般的には、r=x−mnでありここで(mは0とh−1の間)である。pはほぼhnなので、無視できる部分を除いて、rに関連しているxの可能な値がh個あることになる。xを取り出すために、従ってRをより容易に取り出すために、署名者は、mを計算して、それを、メッセージ内、あるいは更なる署名成分として検証者に送ることができる。または検証者は、mを経験に基づいて推測できる。これはh=2の場合に例示することができる。
【0066】
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しか有効でないことを確実にするために両者の値を試みる余分な作業を行うことにより支援することができる。
【0067】
類似の方法を、余因子h=4で利用できる。実際、hの値が大きいと、可能性のあるxの値のそれぞれが有効である確率が低くなる。より多くの可能性のあるxの値があるが、解析によると、検証者に対して同様な利点があることが示される。3個のxの偽の値があり、それぞれは高速チェックでは有効に見える確率は1/8である。このため、偽の値が、高速チェックで有効なxと見えない可能性は(7/8)3であり、約77%である。残りの23%の時間のほとんどは、xの偽の値が1つだけ有効に見え、全署名検証を必要とする可能性がある。
【0068】
i(必要であればmも)を含むことは、rを、x座標とy座標の第1ビットから構成されるRの圧縮バージョンと置き換えることに非常に類似している。このように、rの代わりにRの圧縮値を送ることは、ある程度はより簡単で、偽の値を取り出す可能性は無視できるという利点がある。従って、図9に示されるように、署名は計算されて成分r’、sの対を提供し、メッセージMと共に受け手14に転送される。成分r’はRのx座標とy座標の第1ビットから構成される。成分sは以前と同様に計算される。
【0069】
署名を検証するために、受け手14は、点Rを成分r’から直接取り出し、検証相等性方程式−zR+(zu mod n)G+wQ=Oを使用して、それが群の単位元に対応することを確認する。修正された座標r’の送信は、検証を簡単にするが、必要な帯域幅も増やすことになる。
【0070】
ある状況においては、署名者が余分なビットを送るために利用できるチャネルがない場合がある。例えば、既存の標準規格では、署名フォーマットとメッセージフォーマットの両者を厳格に制限して、送り手が追加情報を提供する余地がまったくないこともある。署名者と検証者は、それにも拘わらず、両者の実践を調整し、それにより、Rはrから取り出せる。これは、署名者が、図10に示すように、xの値が、予め準備された基準に準拠することを確実にすることにより調整できる。上記の表記によれば、署名者は、R=kG=(x,y)を通常のように計算し、上記の表記において、i=y mod 2を計算する。i=1であれば、署名者は、kを−k mod nに変更し、それにより、Rは−R=(x,−y)に変わり、iは0に変わる。検証者が署名を受け取ると、検証者はi=0と仮定して、それにより署名を取り出す。iの値は、このように値0として無条件に伝えられ、署名者は、これを調整するためにほとんど無視できる程度の対価しか必要としない。同様に、非巡回的楕円曲線においては、署名者は、mを無条件に送信しようとし、これはある程度は既に上述してある。h=2の場合は、時間の1/4であることを思い出せば、検証者は、2つの署名を検証する必要がある。検証者がこの余分な作業を行う代わりに、署名者は、この1/4の場合を検出でき、その代わりにkとRに対する別の値を試み、基準に準拠するものが1つ見つかるまでこのプロセスを繰り返す。検証者は、2つの署名を検証する必要なくいずれのxを使用するかを決定することができる。
【0071】
上述したようなRを修正することの代替として、およびECDSA標準規格に厳格に準拠することを維持するために、sの値は、Rではなく、計算の後に修正してもよい。この場合、署名者はRの値は前もって調整された基準に準拠しないことに気付き、通常のように、rとsを生成するように進行できる。sが計算された後、その値は(−s)に変更され、検証が、yの前もって調整された値を仮定して達成できることを確実にする。
【0072】
署名者が署名(r,s)を、Rが無条件に取り出されるように選択すると、通常の検証者は、署名を通常のように容認する。そのような署名は完全に有効である。つまり、改訂検証は、ECDSA検証の既存の実践と完全に互換性がある。無条件の効率的な署名を期待しているが、通常に生成された署名を受け取る促進された検証者は、iの2つの異なる値を試みる必要がある。促進された検証が、通常の検証の60%の時間がかかるとすれば、巡回的曲線(余因子h=1)においては、通常の署名を検証するために必要な平均時間は、通常の検証の50%(60%)+50%(120%)=90%である。これは通常の署名の時間の50%はi=0を有し、たった1回だけの無条件の促進された検証を必要とし、他の50%の時間は2回の促進された検証を必要とするからである。無条件に促進された検証は、署名が無条件に促進されなくても、通常の検証者よりも依然として速い。
【0073】
従来の署名もまた、署名者または第3者により修正できて、高速検証が可能になる。この場合は、署名は、要求者から第3者に転送され、この第3者が検証相等性を使用して署名を検証する。そうすることによりRの値が取り出される。署名は修正されて、指標Iを含み、要求者に戻される。修正された署名は、高速検証署名を期待している受け手との以降の交換に使用される。
【0074】
上記の技術はRを取り出して、関係−zR+(zu mod n)G+wQ=Oを使用して改訂検証が可能になる。しかし、ECDSAが検証されるときは、整数wとzは、図11に示されるように、Rを取り出すことなしに使用できる。zRのx座標と、点wQ+(zu mod n)Gのx’座標を計算し、これら2つのx座標の相等性を調べることは可能である。Rのy座標を知らずに、zRのy座標を直接計算することは不可能なので、点zRのx座標のみが計算可能である。しかし、Rのy座標を必要とせずにRのx座標からzRのx座標を計算するいくつかの既知の方法がある。そのような技術には、上記に示した「楕円曲線暗号へのガイド」(Guide to Elliptic Curve Cryptography)の102頁に説明されているモントゴメリー(Montgomery)の方法がある。そして、x座標の相等性は、wQ+(zu mod n)GがzRまたは−zRに等しいことを意味し、それはw/zQ+uGがRまたは−Rに等しいことを意味し、それはuG+vQがRと同じx座標を有することを意味するので、zRとwQ+(zu mod n)Gのx座標を調べれば十分である。これはECDSAを首尾よく検証するための条件である。Rのx座標は、上記に検討した方法を使用して署名成分rから取り出せる。このアプローチの利点は、y座標を取り出すために余分な作業を必要としないことである。上述した以前の方法に比べて不利な点は、zRをwQ+(zu mod n)Gとは別に計算しなくてはならないことであり、これは、結合和の節約量のある部分は達成されないことを意味する。
【0075】
上記の例では、通信設備12、14の対の間の署名を検証した。この技術は、図12に示されるように、楕円曲線鍵対(d,Q)の検証にも使用できる。鍵対を検証することは、Q=dGを調べることである。これは、改竄が行われていないことを保証するための安全条件のもとで第3者により鍵対が提供されるときに重要である。tがdのビット長であるときに、二進法の方法でのdGの計算は、平均して(3t/2)回の演算が必要となる。本実施形態では、通信設備12、14の1つは乱整数dを生成して、d=w/z mod nとなるように整数w、zの対を取得する。典型的には、整数w、zはそれぞれ長さdの半分である。そして通信設備はzQ−wGを計算し、結果が群の単位元0であることを調べる。zQ−wGの計算は、平均してt回の演算を必要とし、従って、50%の節約量が得られる。これは、Gの前計算された倍数を格納するためのコストが高価である環境においては最も有利な方法である。メモリに制限がある別の環境では、前計算された倍数H=uGがあれば、dGがd’G+d’’Hとして計算され、ここにおいてd=d’+d’’u mod nであり、上記とほぼ同じコストがかかる。
【0076】
別の適用は、無条件の証明書の検証である。無条件の証明書は対(P,I)であり、ここでPは楕円曲線点であり、Iはある単位元列である。エンティティであるボブ(Bob)は、楕円曲線点である要求値RをCAに送ることにより、無条件の証明書をCAから取得する。CAは、無条件の証明書(P,I)を返し、更に、私的鍵再構築データ値sを返す。ボブ(Bob)は、sを使用して自分の私的鍵を計算する。より一般的には、いかなるエンティティもsを使用して無条件の証明書がボブ(Bob)の要求値RとCA公開鍵Cに正確に対応していることを検証できる。これは、検証相等性H(P,I)R+sG=H(P,I)P+Cを調べることで行われ、ここにおいてHはハッシュ関数である。この方程式は、eQ+sG=Cと等価であり、ここにおいてe=H(P,I)およびQ=R−Pである。この方程式の形式は標準規格ECDSA検証方程式の形式に非常に類似している。従って、上記で検討した技術は、この方程式の検証を促進する手段を提供するために使用できる。これは、e=w/z mod nとなるように、相対的に小さな値wとzを決定することにより最適に行われ、この方程式にzを乗算することにより、wQ+(sz mod n)G−zC=Oが得られる。再び、この方程式のGの倍数は全サイズであるが、一般的にはGの倍数は前計算でき、従って、これは問題を引き起こさない。
【0077】
この技術の利点を利用する別の変形例では、ECDSA署名方程式の3つすべての倍数を短くする。理論的には、各倍数は、nの長さの2/3の長さまで短くできる(nはGの位数)。この短小化を達成するための1つの方法は、3次元における短ベクトル束問題を解くことである。そのような問題を解くためのアルゴリズムが存在する。3つすべての倍数を短くすることは、Gの前計算された倍数をいずれも格納することができない場合には非常に有益であり、Gの倍数の長さを可能な限り短くすることをより効率的にする。そのような技術は、アンリコーヘン(Henri Cohen)の計算法代数的数論講座(A Course in Computational Algebraic Number Theory),スプリンゲル(Springer)、ISBN0−387−55640−0に更に完全に記載されている。第2.6節と2.6節はLLLアルゴリズムを記載しており、その適用は、束における短ベクトルを見出すことであり、また、3次元束のためのベーユ(Vallee)の特別アルゴリズムに言及している。
【0078】
この技術の別の適用は、部分メッセージ取り出しのピンチョフ−バンストーン署名(Pintsov−Vanstone Signature(PVS))方式の修正バージョンへの適用である。PVS署名は(r,s,t)の3つの組から構成される。署名の検証と、公開鍵Qのもとで署名からのメッセージの取り出しは、ベース生成子Gにより、下記のように行われる。検証者はe=H(r‖t)を計算し、ここにおいてHはハッシュ関数である。そして検証者は、R=sG+eQを計算する。次に、検証者はRから対称暗号鍵Kを導出する。これにより、検証者は、Kを使用してrを解読し、取り出されたメッセージ部分uを得る。取り出されたメッセージは、tとuのある結合である。署名はuがある冗長性を有していれば有効であり、この冗長性は、uがある所定のフォーマットに準じていることを検証することにより調べられる。PVS方式は、草案標準規格IEEE P 1363aおよびANSI X9.92の一部である。
【0079】
PVSの修正変形例においては、検証時間は整数wとzを利用することにより削減できる。PVSの修正変形例は図13に示されており、下記のようにして進める。通常のようにeを計算した後、検証者は、wとzが、e=w/z mod nであり、点Gの位数であるnの長さの半分であることを見出す。そして検証者は、R=(ws mod n)G+zQを計算して、以前のように手順を進めて、Rから鍵を導出し、その鍵でrを解読し、解読が正しい形式であることを検証する。検証のこの形式は、Qの倍数がより小さいのでより効率的である。
【0080】
楕円曲線群および類似の群におけるデジタル署名の署名検証を更に促進するための方法が下記のように例示される。ECDSA署名の検証は、基本的には、aR+bQ+cGのような3個の楕円曲線点の線形結合が、無限大の点と等しいことを確認することと等価である。この条件を検証する1つの方法は、点aR+bQ+cGを計算し、その結果が無限大における点O、つまり、上述したように、群の単位元であるかを調べる。この検証は、ときどき、全体の合計を直接計算するよりもより迅速に行えることがある。例えば、a=b=cならば、点R、Q、およびGが共線でありその場合に限ってaR+bQ+cG=Oである。点が共線であるかを調べることは、楕円曲線点への加算よりも格段に速い。共線性は、方程式(xR−xG)(yQ−yG)−(xQ−xG)(yR−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=0 mod nまたはR=Oでありその場合に限りaR=Oであることが知られている。この検証は、零楕円曲線点演算が必要であるという点において比較的に即座に終了する。余因子が、h=2またはh=4のように小さいときは、点演算は、数回の非常に高速な体の演算により置き換えることができる。このように、合計の点がゼロであるような検証の特別な場合は、非常に速く行うことができる。
【0081】
除算多項式に対する帰納的公式に類似して、aR+bQ+cGのような合計の分母に対する帰納的公式が存在し、これらは、点aR+bQ+cGの全値を計算するよりもより高速に計算できる。群の位数nを知っていれば、検証時間を更に短縮できる。
【0082】
この技術の更なる適用は、図14に示されるように、ECDSAデジタル署名のみから、公開鍵Qを効率的に回復することである。1つの通信設備12が署名(r,s)でメッセージMに署名して、署名したメッセージを通信設備14に送りたいとする。通常は、通信設備14は、Mと(r,s)を通信設備に送り、しばしば公開鍵Qも送る。通信設備12がそれ自身の公開鍵を送らなかったとすると、通常は、通信設備14は、あるネットワークを介して、局所的にまたは遠隔的に格納できる、あるデータベースにおいて相手の通信設備の公開鍵を探そうとする。これを避けるために、署名から公開鍵Qを取り出せるということは有利である。
【0083】
通常のECDSA署名(r,s)が与えられれば、公開鍵である可能性があるいくつかの候補点Qを取り出すことができる。第1ステップは点Rを取り出すことである。署名に追加情報を含むことにより、署名されたメッセージに追加情報を含むことにより、1つの有効なRがrに対応できることを保証する署名者側の追加作業により、およびrに対応する多数の異なるR値を試みる検証者側の追加作業によるなど、促進された検証の状況においてRを見出すためのいくつかの方法が既に記載されてきた。これらの方法の1つによりいったんRが取り出されると、公開鍵Qは下記のようにして取り出すことができる。標準規格ECDSA検証方程式はR=(e/s)G+(r/s)Qであり、ここでe=H(M)はメッセージのハッシュ値である。Rとこの方程式が与えられれば、Qを求めることはQ=(s/r)R−(e/r)Gにより行われる。
【0084】
しかし、かなりの確率で、対(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に対する正しい値を取り出したことになる。証明書から公開鍵を省略することは、帯域幅と格納領域を節約することになり、上述した検証プロセスは検証時間を短縮する。
【0085】
通信設備14はまた、Qのビットの半分のような、Qから導出されたよりコンパクトな値に対してQを調べることにより、Qが通信設備12の公開鍵であることを検証できる。Qのコンパクトバージョンは、この後格納され、またはQの代わりに通信され、ここで再び格納領域と帯域幅を節約することができる。
【0086】
検証相等性で使用される値のそれぞれが公開値であることも理解されるであろう。従って、検証者が利用できる計算能力に制限がある場合は、署名者はwとzの値を計算して、それをRと共にメッセージの一部として転送することができる。受け手は、Rを取り出す必要がなく、またwとzを計算する必要もなく、利用できる情報で検証を行うことができる。検証は促進されるが帯域幅は増大する。
【0087】
上記の記載は、楕円曲線群に対するものであったが、本発明で記載された多数の方法は、より一般的に暗号で使用される任意の群に適用でき、更に、群の元の冪乗を使用する他の適用も可能である。例えば、本発明は、最近、楕円曲線群の代替として提案されている、群がg(種)=2の超楕円曲線の場合に使用できる。上記の技術は、ECDSAに類似している、デジタル署名アルゴリズム(DSA:Digital Signature Algorithm)の検証を促進するためにも使用できる。ECDSAと同様に、DSA署名は、整数(r,s)の対から構成され、rはDSA群の元Rから得られる。DSA群は、有限体の乗算群の部分群であると定義されている。しかし、ECDSAとは異なり、rからRを取り出すことは、数個の追加ビットの支援があっても達成するのが容易ではない。従って、本技術は、値がRで、署名されたメッセージの一部分として、または署名の追加部分として、または値rに対する置き換えとして送られるならば、最も容易にDSAに適用できる。典型的に、整数rは20バイトで表現されるが、値Rは128バイトで表現される。結果として、結合された署名とメッセージ長は、約108バイト長くなる。しかしこれは、検証を33%促進するためには小さなコストである。
【0088】
DSA設定においては、pは大きな素数であり、qはより小さな素数であり、qは(p−1)の約数である。整数gは、g^q=1 mod p、および1<g<pとなるように選択される。(qとgは、ECDSAからのnとGにそれぞれ対応することに注意。)
【0089】
署名者の私的鍵は、ある整数xであり、公開鍵はY=g^x mod pである。
【0090】
署名者は署名を、通常の(r,s)の代わりに(R,s)の形式で生成する。ここで、R=g^k mod pであるが、r=R mod qである。両者の場合において、s=k^(−1)(h(M)+xr) mod qであり、ここでxは署名者の私的鍵であり、Mは署名されるメッセージであり、hはメッセージを要約するために使用されるハッシュ関数である(ECDSAと同様)。
【0091】
通常のDSAにおいて、検証者は、u=h(M)/s mod qとv=r/s mod qを計算することにより署名(r,s)を検証し、これはECDSA実施形態におけるuとvに非常に類似しており、そしてr=(g^uY^v mod p) mod qを調べる。本実施形態においては、検証者は、qの約半分の長さのビット長のwとzを見出し、それによりwとzのそれぞれは、v=w/z mod qとなるように、ほぼsqrt(q)となる。これは、nをqと置き換えて、上記のECDSA実施形態と同じ方法で行われる。そして検証者は、R^zg^(zu mod q)Y^w mod pを計算する。
【0092】
この値が1に等しければ、検証者はその署名を容認し、そうでなければその署名は拒絶される。
【0093】
検証者は、平方乗算アルゴリズム、またはその変形例を使用してこの値を計算し、ECDSAにおける同時倍算に類似した同時平方を利用する。ECDSA高速検証の多数の方法がDSA高速検証に使用できる。gの前計算された倍数、例えばjを使用することができ、計算はR^zg^sj^tY^w mod pのようになり、ここで、z、s、t、およびwのそれぞれは、qの約半分のビット長を有する。公開鍵Yの前計算された冪乗が利用できるならば、冪の指数の長さは、更に短縮することができ、それにより倍算の数を少なくして検証をより高速にする。
【0094】
発明の実施形態は、添付された図面を参照して、例としての目的のみのためにここで説明される。
【特許請求の範囲】
【請求項1】
明細書に記載の方法。
【請求項1】
明細書に記載の方法。
【図1】
【図2】
【図3】
【図4】
【図5】
【図6】
【図7】
【図8】
【図9】
【図10】
【図11】
【図12】
【図13】
【図14】
【図2】
【図3】
【図4】
【図5】
【図6】
【図7】
【図8】
【図9】
【図10】
【図11】
【図12】
【図13】
【図14】
【公開番号】特開2012−14203(P2012−14203A)
【公開日】平成24年1月19日(2012.1.19)
【国際特許分類】
【外国語出願】
【出願番号】特願2011−230106(P2011−230106)
【出願日】平成23年10月19日(2011.10.19)
【分割の表示】特願2007−550647(P2007−550647)の分割
【原出願日】平成18年1月18日(2006.1.18)
【出願人】(397071791)サーティコム コーポレーション (38)
【Fターム(参考)】
【公開日】平成24年1月19日(2012.1.19)
【国際特許分類】
【出願番号】特願2011−230106(P2011−230106)
【出願日】平成23年10月19日(2011.10.19)
【分割の表示】特願2007−550647(P2007−550647)の分割
【原出願日】平成18年1月18日(2006.1.18)
【出願人】(397071791)サーティコム コーポレーション (38)
【Fターム(参考)】
[ Back to top ]