暗黙の証明書検証
【課題】暗黙の証明書検証の提供。
【解決手段】暗号システムを介して互いに通信し合う一対の通信者の間で共有されるべき暗号鍵を計算する方法が提供される。ここで一対の通信者のうちの一方の通信者は、鍵を生成するためにその一方の通信者の秘密鍵情報と組み合わされるべき他方の通信者の公開鍵情報の証明書を受け取る。その方法は、公開鍵情報と秘密鍵情報とを組み合わせることによって鍵を計算するステップと、証明書の検証に失敗した結果として一方の通信者での鍵が他方の通信者で計算された鍵とが異なるように、証明書の検証に対応する成分を計算に含めるステップとを含む。
【解決手段】暗号システムを介して互いに通信し合う一対の通信者の間で共有されるべき暗号鍵を計算する方法が提供される。ここで一対の通信者のうちの一方の通信者は、鍵を生成するためにその一方の通信者の秘密鍵情報と組み合わされるべき他方の通信者の公開鍵情報の証明書を受け取る。その方法は、公開鍵情報と秘密鍵情報とを組み合わせることによって鍵を計算するステップと、証明書の検証に失敗した結果として一方の通信者での鍵が他方の通信者で計算された鍵とが異なるように、証明書の検証に対応する成分を計算に含めるステップとを含む。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、公開鍵暗号法に関する。
（本発明の概要）
公開鍵暗号法は、一対の通信者の間の安全な通信を可能にし、一対の通信者のうちの一方の通信者が発するメッセージの認証を可能にするために用いられる。公開鍵暗号法において各通信者は、数学的関数による秘密鍵に関連した秘密鍵および公開鍵を利用する。その数学的関数は、関係者の秘密鍵が対応する公開鍵から獲得され得ないことを保証するために「困難な」数学的問題を提供する。そのような問題は、ＲＳＡ暗号システムにおいて用いられる２つの大きな素数の積を因数分解する困難さ、およびデジタル署名アルゴリズム（ＤＳＡ）において用いられる有限体上の離散対数問題の難しさ（ｉｎｔｒａｃｔａｂｉｌｉｙ）を含む。離散対数システムは、広く用いられ、そのようなシステムの特定の適用は、有限体上に定義された楕円曲線の点を使用する。楕円曲線暗号システム（ＥＣＣ）として参照されるそのようなシステムは、他のシステムよりも小さい鍵の大きさで高いレベルの安全性を提供する。
【０００２】
メッセージが安全に交換されるべきときは、通信者間でそれぞれの秘密鍵を開示しないで共有される鍵を構築するために、公開鍵および秘密鍵が、概して鍵の合意プロトコルとして参照される特定のプロトコルにおいて用いられる。次いで、共有される鍵は、通信者間のメッセージを暗号化および復号するために用いられ得る。
【０００３】
楕円曲線公開鍵の鍵の合意プロトコルは、典型的には以下のステップを含む。
・鍵のコントリビューション（ｋｅｙ ｃｏｎｔｒｉｂｕｔｉｏｎ）：各関係者は、任意の整数である秘密鍵と、かつ一時的な公開鍵を表す点を提供するためのシード点とから、任意の短期の（一時的な）公開鍵を生成し、対応する一時的な公開鍵（しかし、秘密鍵ではない）をもう一方の関係者に伝える。加えて、鍵のコントリビューションは、その長期の固定的な公開鍵を伝え得る。
・鍵の設定：各関係者は、他方の関係者から受け取った固定的および一時的な鍵に基づいて、および自身で生成した秘密鍵に基づいて、共有される鍵を計算する。楕円曲線の特性に起因して、両方の関係者は、同一の共有される鍵に到達する。
・鍵の認証：各関係者は、共通の鍵を計算する能力があり得る唯一の関係者が、本当に、その受け取られた通信する関係者である証拠を獲得するために、他方の関係者の長期の固定的な鍵の信頼性を検証する。
・鍵の確認：各関係者は、いずれかの関係者によって伝えられた鍵のコントリビューションに対応するストリング（ｓｔｒｉｎｇ）を介して通例ではメッセージの認証チェック値を伝えることによって、他方の関係者に対し共通の鍵の所有を実証する。このことは、各関係者に対して他方の関係者の真の識別を確認し、その関係者が首尾よく共通の鍵を計算したことを証明する。このステップは、鍵の合意プロトコルの一部として、またはその後に、共有される鍵の使用を介して行われ得る。
【０００４】
鍵の認証ステップは、典型的には上記で説明された他のプロトコルステップとは独立に実行され、対応する公開鍵を手段として関係者とその秘密鍵との間の結合の信頼性を請け合う証明書の有効性をチェックすることに通例では関係する。別個の鍵の認証ステップが、（例えば、証明書の使用における）より大きな柔軟性を可能にするが、かなりのコストで行われる。なぜなら、鍵の合意プロトコルのオンラインでの計算コストは、鍵の認証ステップのコストと、鍵の設定ステップ中の鍵の計算のコストとの合計によって支配されるからである。
【０００５】
証明書は、本質的に通信者の公開鍵への信頼された関係者の署名と、発行する関係者の名前および証明書の保有者の名前のような他の情報とが一緒になったものである。ＥＣＣシステムにおいて、署名は、通例ではＥＣＤＳＡプロトコルを用いて実行され、検証されるが、他の署名プロトコルもまた、用いられ得る。例として、ＥＣＤＳＡ署名生成は、ＥＣＣのドメインパラメーター、秘密鍵ｄ、およびメッセージｍに対して機能し、メッセージｍは、証明書に関しては、通信者の公開鍵を含む。出力は、署名（ｒ，ｓ）である。ここで署名の成分ｒおよびｓは、整数であり、以下のように進められる。
１．任意の整数
【０００６】
【数１】
を選ぶ。ｎは、ドメインパラメーターのうちの１つである。
２．ｋＧ＝（ｘ１，ｙ１）を計算し、ｘ１を整数
【０００７】
【数２】
に変換する。ここでＧは、楕円曲線Ｅ上の点であり、ドメインパラメーターのうちの１つである。
３．
【０００８】
【数３】
を計算する。ここでｒ＝０の場合には、ステップ１に戻る。
４．ｅ＝Ｈ（ｍ）を計算する。ここでＨは、出力がｎのビット長さを超えないビット長さを有する、暗号ハッシュ関数を示す（この条件が満たされない場合には、Ｈの出力は切り捨て（ｔｒｕｎｃａｔｅ）られ得る）。
５．ｓ＝ｋ−１（ｅ＋αｒ）ｍｏｄ ｎを計算する。ここでαは、署名者の長期の秘密鍵である。ｓ＝０の場合には、ステップ１に戻る。
６．対（ｒ，ｓ）をメッセージｍのＥＣＤＳＡ署名として出力する。
【０００９】
ＥＣＤＳＡ署名検証は、いくつかのドメインパラメーター、長期の公開鍵Ｑ（ここでＱ＝αＧ）、メッセージｍ、および上記で導かれた署名（ｒ，ｓ）に対して機能する。ＥＣＤＳＡ署名検証の出力は、署名の拒絶または承認であり、以下のように進められる。
１．ｒおよびｓが区間［１，ｎ−１］にある整数であることを検証する。すべての検証が失敗する場合には、拒絶が返される。
２．ｅ＝Ｈ（ｍ）を計算する。
３．ｗ＝ｓ−１ ｍｏｄ ｎを計算する。
４．ｕ１＝ｅｗ ｍｏｄ ｎおよびｕ２＝ｒｗ ｍｏｄ ｎを計算する。
５．Ｒ＝ｕ１Ｇ＋ｕ２Ｑ＝ｓ−１（ｅＧ＋ｒＱ）を計算する。（上記の３および４から）６．Ｒ＝∞の場合には、署名は、拒絶される。
７．Ｒのｘ座標ｘ１を整数
【００１０】
【数４】
に変換する。
【００１１】
【数５】
を計算する。
８．ν＝ｒの場合には、署名は、承認される。そうでない場合には、署名は、拒絶される。
【００１２】
ＥＣＧＤＳＡのような他の署名生成および検証のステップが用いられ得ること、および署名の完全性を確認する特定のステップが時として省略されることは、認識されるであろう。
【００１３】
したがって、通信者の公開鍵、すなわち通信者の公開鍵および他の情報を含むメッセージｍを認証するためには、証明書上の署名を検証することが必要である。
【００１４】
認証に続いて、各関係者が本当に同一であることを確認するのが通例である。２つの関係者ＡとＢとの間で鍵の合意プロトコルの実行中、関係者Ａが鍵ＫＡを構築している間に、関係者Ｂは、鍵ＫＢを構築する。鍵の確認は、Ａが何らかの量ｆ（ＫＡ）（ここでｆは、何らかの公知の関数である）をＢ（Ｂは、これを彼自身の計算された値ｆ（ＫＢ）と比較し、これらの値が一致する場合にのみ承認する（およびその逆））に伝えることによって、ＫＡについての知識をＢに対して実証することからなる。この関数ｆは、ｆ（ＫＡ）＝ｆ（ＫＢ）の場合に圧倒的な確率でＫＡ＝±ＫＢとなり、共通の鍵が設定されるような関数である。
【発明の概要】
【発明が解決しようとする課題】
【００１５】
上記で留意されたように、鍵の認証ステップは、鍵の合意プロトコルにかなりの計算負荷を追加する。したがって、本発明の目的は、上記の不利な点を除去または軽減することである。
【課題を解決するための手段】
【００１６】
一般的に言って、本出願人は、共有される鍵と証明書検証との組み合わせを結合して計算することによって、証明書の暗黙の検証が後続の鍵の確認ステップにおいて獲得されることを認識した。
【００１７】
好ましくは、署名検証は、証明書の検証の失敗の結果、共有される鍵の値の間の不一致が生じるような同次の検証方程式、すなわち０に等しい方程式を用いる。
【００１８】
１つの局面において、暗号システムを介して互いに通信する一対の通信者の間で共有されるべき暗号鍵を計算する方法が提供され、一対の通信者のうちの一方の通信者は、鍵を生成するためにその一方の通信者の秘密鍵情報と組み合わされるべき他方の通信者の公開鍵情報の証明書を受け取り、その方法は、公開鍵情報と秘密鍵情報とを組み合わせることによって鍵を計算するステップと、証明書の検証に失敗した結果として一方の通信者での鍵が他方の通信者で計算された鍵とが異なるように、証明書の検証に対応する成分を計算に含めるステップとを含む。
【００１９】
別の局面において、コンピューター読み取り可能な媒体、暗号ユニット、および上記の方法のステップを実行するために構成されるシステムが提供される。
例えば、本願発明は以下の項目を提供する。
（項目１）
暗号システムを介して互いに通信する一対の通信者の間で共有されるべき暗号鍵を計算する方法であって、該一対の通信者のうちの一方の通信者は、該鍵を生成するために該一方の通信者の秘密鍵情報と組み合わされるべき他方の通信者の公開鍵情報の証明書を受け取り、該方法は、
該公開鍵情報と該秘密鍵情報とを組み合わせることによって該鍵を計算するステップと、
該証明書の検証に失敗した結果として、該一方の通信者での鍵が該他方の通信者で計算された鍵とは異なるように、該証明書の検証に対応する成分を該計算に含めるステップと
を含む、方法。
（項目２）
前記検証は、前記証明書に含まれる署名を利用する、項目１に記載の方法。
（項目３）
前記成分は、前記証明書が検証するときにゼロに等しい、項目２に記載の方法。
（項目４）
前記証明書の検証を隠すために、任意の要素が前記成分に含まれる、項目３に記載の方法。
（項目５）
前記任意の要素は、前記署名の検証において繰り返される反復を提供することにより、側面チャネル攻撃を禁止するように選ばれる、項目４に記載の方法。
（項目６）
前記暗号システムは、楕円曲線暗号システムである、項目１に記載の方法。
（項目７）
前記計算は、重複点の倍増を用いて実行される、項目６に記載の方法。
（項目８）
前記証明書は、楕円曲線署名プロトコルによって実行される署名を含む、項目６に記載の方法。
（項目９）
前記署名プロトコルは、ＥＣＤＳＡである、項目８に記載の方法。
（項目１０）
前記公開鍵情報は、楕円曲線の点を表し、公開鍵情報と前記秘密鍵情報との組み合わせが点の倍増を含む、項目６に記載の方法。
（項目１１）
前記署名の検証は、重複点の倍増を要求する、項目１０に記載の方法。
（項目１２）
前記計算は、重複点の倍増を用いて実行される、項目１１に記載の方法。
（項目１３）
前記一方の通信者によって生成された鍵が前記他方の通信者の鍵と一致することを確認するステップを含む、項目１に記載の方法。
【図面の簡単な説明】
【００２０】
本発明の一実施形態がここで添付の図面を参照することにより説明される。
【図１】図１は、データ通信システムの概略を表示する図である。
【図２】図２は、第一の鍵の合意プロトコルを表示する図である。
【図３】図３は、さらなる鍵の合意プロトコルを表示する図である。
【発明を実施するための形態】
【００２１】
（本発明の詳細な説明）
したがって、図１を参照すると、暗号通信システムが、数字１０によって一般的に示されている。システム１０は、通信チャネル１６を介して互いに通信し得る第一の通信者１２および第二の通信者１４を有する。通信チャネル１６は、安全であり得るか、または、安全でないこともあり得る。各通信者は、選ばれた体上で定義される楕円曲線Ｅ上で機能する暗号化操作を実行するために、暗号モジュール１８および暗号モジュール２０をそれぞれ有する。暗号モジュール１８は、以下に説明されるもののような暗号化操作を実行するように構成されるハードウェア、コンピューター読み取り可能なソフトウェア命令または両者の組み合わせであり得る。
【００２２】
通信者１２は、長期の秘密鍵「ａ」と、対応する長期の公開鍵Ａ＝ａＧとを有し、ここでＧはドメインパラメーターにおける特定の曲線上の基点である。
【００２３】
通信者１２に対して公開鍵Ａを認証するために、証明書ＴＡが、信頼された機関から獲得される。証明書は、信頼された機関の公開鍵Ｑを用いて検証され得る公開鍵Ａに関する信頼された機関の署名を含む。
【００２４】
同様に、通信者１４は、長期の秘密鍵ｂと、対応する長期の公開鍵Ｂ＝ｂＧと、その公開鍵の証明書ＴＢとを有する。証明書ＴＢは、証明書ＴＡを獲得するために用いられたものとは異なる別の信頼された関係者によってか、または別の公開鍵を用いて、署名された可能性がある。
【００２５】
典型的には、通信者１２、１４はそれぞれ、対応する一時的な公開鍵ｘＧ、ｙＧを生成するセッションまたは一時的な秘密鍵として用いるための、任意の整数ｘ、ｙを生成し得る。しかしながら、明確さのために、共通の鍵が各通信者の長期の鍵を用いて設定される第一の実施形態が、説明される。
【００２６】
図２に示された第一の鍵の合意プロトコルにおいて、固定的（ｓｔａｔｉｃ）な楕円曲線ディフィ・ヘルマン（Ｄｉｆｆｉｅ Ｈｅｌｌｍａｎ）（ＥＣＤＨ）鍵生成が、証明書ＴＡ、ＴＢを用いて使用され、ＥＣＤＳＡを用いて署名される。
【００２７】
最初に、通信者１２、１４は、公開鍵Ａ、Ｂおよびそれぞれの証明書ＴＡ、ＴＢを交換する。共通の鍵は、Ｋ＝ａｂＧであり、Ｋ＝ａｂＧは、各関係者に対して、受け取られた公開情報および各関係者が有する秘密情報から計算され得る。その結果、ＫＡ＝ａＢおよびＫＢ＝ｂＡである。
【００２８】
鍵の信頼性を検証するために、証明書ＴＡおよびＴＢを検証するのが通常である。しかしながら、本実施形態において、鍵の生成および認証は、効率性を提供するために、結合して実行される。上記で留意されたように、ＥＣＤＳＡは、その検証において、
【００２９】
【数６】
を提供する。したがって、証明書が検証する場合には、ｓ−１（ｅＧ＋ｒＱ）−Ｒ＝Σ＝Ｏである。Ｒの値は、点Ｒのｘ座標の値になるようにｒを取ることによって署名成分ｒから復元され得る。ｘ座標は、２つの可能なｙの値を提供し、曖昧さを解決するために、正しい値の指示が署名に含まれるか、または、Ｒが計算されることを可能にする正しい値として値のうちの１つの値を選ぶために予め合意されたルールがある。Ｒを復元する付加的な技術は、米国特許出願第１１／３３３，２９６号において開示され、その内容は、参照により援用される。
【００３０】
各通信者はまた、証明書ＴＡ、ＴＢから署名（ｒ，ｓ）を有する。鍵Ｋを計算するために、通信者１２は、公開鍵情報と秘密鍵情報とを組み合わせ、署名の検証に対応する成分を含むことによって鍵ＫＡを計算する。したがって、
ＫＡ＝ａｂＧ＋λ１（ｓＢ−１（ｅＢＧ＋ｒＢＱＢ）−ＲＢ）
この式で、
λ１は、任意の値である。
ｒＢ、ｓＢは、証明書ＴＢの署名成分である。
ｅＢは、証明書におけるメッセージｍのハッシュである。証明書は、通信者１４の公開鍵Ｂを含む。そして、
ＲＢは、ｒＢから復元される値である。
【００３１】
証明書がＢの公開鍵を認証する場合には、署名検証成分
【００３２】
【数７】
がゼロであるべきであり、したがって、計算の結果が鍵ＫＡ＝ａＢをもたらすべきであることは、認められるであろう。
【００３３】
同様に、通信者１４は、ｒＡ、ｓＡ、およびＲＡの値が証明書ＴＡと関連するＫＢ＝ａｂＧ＋λ２（ｓＡ−１（ｅＡＧ＋ｒＡＱＡ）−ＲＡ）を計算する。さらにまた、証明書が認証する場合には、これは、鍵ＫＢ＝ｂＡをもたらすべきである。
【００３４】
通信者１２、１４がそれぞれの鍵ＫＡ、ＫＢを計算した後で、それらは、共通の鍵の機能である情報を交換するための鍵確認ステップを実行する。受け取られた情報が計算されたものと一致しない場合には、鍵は、拒絶される。
【００３５】
共通の鍵が異なる１つの理由は、証明書の検証部分から獲得された値がゼロでなく、証明書が認証していないことを示していることである。通信者１２、１４それぞれに対して通例では異なる各計算中に任意の値λを挿入することによって、認証プロセスの有効性が高められる。
【００３６】
こうして、証明書が認証する場合には、共通の鍵の値および、Ｏに対応する関係を結合して計算することによって、計算が削減される。
【００３７】
さらなる実施形態が図３に示され、ＭＱＶ鍵合意プロトコルが、ＥＣＤＳＡを用いて署名された証明書の認証と組み合わされている。
【００３８】
図３の実施形態において、通信者１２および１４はそれぞれ、長期の秘密鍵ａ、ｂ、長期の公開鍵Ａ、Ｂ、短期の秘密鍵ｘ、ｙおよび短期の公開鍵Ｘ、Ｙを有する。ＥＣＭＱＶにおいて、共通の鍵は、
Ｋ＝ｃＸ＋ｄＢ
の形式である。
ここで、
ｃ＝ｘ＋ａｇ（ｘ）（ｍｏｄ ｎ）かつ
ｄ＝ｃｇ（Ｙ）（ｍｏｄ ｎ）。
ここで、ｇは、楕円曲線の点を適切な整数に写像する公知の表現関数である。
【００３９】
各通信者がもう一方の通信者の証明書ＴＡ、ＴＢを有していると仮定すると、各通信者はそれぞれ、もう一方の通信者に短期の公開鍵Ｘ、Ｙを送る。
【００４０】
通信者１２は、ｓ１２＝（ｘ＋ａｇ（ｘ））ｍｏｄ ｎを計算する。通信者１４は、ｓ１４＝（ｙ＋ｂｇ（ｙ））ｍｏｄ ｎを計算する。次いで、共通の鍵Ｋは、Ｋ＝ｓ１２（Ｙ＋ｇ（ｙ）Ｂ）＝ｓ１４（Ｘ＋ｇ（ｘ）Ａ）として計算され得る。
【００４１】
鍵を認証するためには、通信者の長期の公開鍵の証明書が認証されなければならない。したがって、上記で説明されたように、共通の鍵Ｋは、通信者１２によって
ＫＡ＝ｓ１２（Ｙ＋ｇ（ｙ）Ｂ）＋λΣ＝（ｘ＋ａｇ（ｘ））（Ｙ＋ｇ（ｙ）Ｂ）＋（λ１ｅＢｓＢ−１）Ｇ＋（λ１ｒＢｓＢ−１）Ｑ＋λ１ＲＢ
として、かつ、通信者１４によって、
ＫＢ＝ｓ１４（Ｙ＋ｇ（ｘ）Ａ）＋λΣ＝（ｙ＋ｂｇ（ｙ））（Ｘ＋ｇ（ｘ）Ａ）＋（λ２ｅＡｓＡ−１）Ｇ＋（λ２ｒＡｓＡ−１）ＱＡ＋λ２ＲＡ
として、計算される。
【００４２】
各通信者に対して、λは、任意の整数であり、Σは、それぞれの証明書に対する署名検証の関係ｓ−１（ｅＧ＋ｒＱ）−Ｒである。
【００４３】
Σ＝Ｏと仮定すると、鍵は、一致し、証明書は、暗黙に認証される。
【００４４】
獲得された効率性は、点の倍増操作の節約および重複点の倍増戦略を用いる可能性に帰せられ得る。
【００４５】
安全性の観点から、λの任意の値は、大きさ
【００４６】
【数８】
の組から選ばれるべきである。なぜなら、この組が、ＥＣＤＬＰ問題を解決することの作業負荷に対応しているからである。λが選ばれる組は、変化され得、後続の変形は安全である。λがｔ＜（ｌｏｇ２ｎ）／２である大きさ２ｔの組から抜き出される場合には、鍵の認証強度は、ｔビットまで下がり得る。λのそのような選択とともに、ａＢ＋λＲを計算することは、ＢまたはＢ−Ｒを伴うｗｔＨ（ａ）点の追加を伴い、ｗｔＨは、値ａの二進表現のハミング重みである。これは、ａＢの計算に伴う点の追加と同一の数である。
【００４７】
量（λｅｓ−１）Ｇ＋（λｒｓ−１）Ｑは、その内容が参照により援用されるＶａｎｓｔｏｎｅ他、Ｓｐｒｉｎｇｅｒ、「Ｇｕｉｄｅ ｔｏ Ｅｌｌｉｐｔｉｃ Ｃｕｒｖｅ Ｃｒｙｐｔｏｇｒａｐｈｙ」、９８から１０１ページにおいてより十分に説明されている、隣接していない形式（ＮＡＦ；ｎｏｎ−ａｄｊａｃｅｎｔ ｆｏｒｍ）を用いて計算され得る。
【００４８】
この方法でＫＡを評価することの作業負荷は、およそｍの点の追加およびｍの倍増であり、ｍは、曲線のビットの大きさである。
【００４９】
比較によって、ＫＡ＝ａＢを評価することおよびＥＣＤＳＡ署名を検証することは、それぞれ５ｍ／６の追加および２ｍの倍増の作業負荷を有する。
【００５０】
したがって、３０％の改善は、達成可能である。上記の米国特許出願第１１／３３３，２９６号において示されている「高速検証（ｆａｓｔ ｖｅｒｉｆｙ）」技術が用いられる場合には、１０％程度の節約が可能である。
【００５１】
二進表現におけるよりむしろＮＡＦ表現において整数とともにλを考慮することによって、さらなる改善を行い得る。
【００５２】
【数９】
であるから、
【００５３】
【数１０】
が得られる（Ｌにおけるすべての整数は、ＮＡＦ形式であり、そのため一意的であることに留意されたい）。上記と類似の分析を実行して、ここで与えられたアプローチは、およそ５ｍ／６の追加およびｍの倍増をもたらす。この場合、ここで与えられたアプローチは、上記で説明された二進法のアプローチによる１．７０ｍの追加でなく、１．５２ｍの追加をもたらし、その結果、個別の計算（Ｆａｓｔ Ｖｅｒｉｆｙ、Ｏｒｄｉｎａｒｙ ＥＣＤＳＡ Ｖｅｒｉｆｙのそれぞれ）と比較してそれぞれ２２％、４７％の効率性の改善をもたらす。この場合、ａＢ−λＲ＝（ａ−λ＋＋λ−）Ｂ−λ＋（Ｒ−Ｂ）−λ−（Ｒ＋Ｂ）と書き得る。ここでλ＝λ＋＋λ−であり、λ＋およびλ−は、それぞれ、ａの対応する成分と同じまたは異なる符合を有するλの成分を示していることに留意されたい。
【００５４】
Ｖａｎｓｔｏｎｅ他、Ｓｐｒｉｎｇｅｒ、「Ｇｕｉｄｅ ｔｏ Ｅｌｌｉｐｔｉｃ Ｃｕｒｖｅ Ｃｒｙｐｔｏｇｒａｐｈｙ」、９９ページにおいて説明されたｗ−ＮＡＦ表現（ｗ≧２）に対して、これをさらに一般化し得る。そのとき、
【００５５】
【数１１】
であり、ここでｑ：＝２ｗ−１＋１およびｔ：＝ｗｔＨ（ａ）である（すべての整数は、ｗ−ＮＡＦ形式であり、それ故一意的である）。
【００５６】
【数１２】
と仮定する場合には、
【００５７】
【数１３】
を得る。より詳細な分析は、ａＢ＋λＲにおける追加が、ａＢが２ｗ−２ではなくおよそ２（ｗ＋１）（ｗ−２）／２のより大きな予め計算するコストを有することを除いて、（同一の方法を用いることによって）ａＢにおける追加と同一のコストで計算され得る。格納コストは、１対３（ｗ＝２）、２対８（ｗ＝３）、４対２４（ｗ＝４）、８対６４（ｗ＝５）である。したがって、格納コストが選択の尺度である場合には、比較は、いくぶん誤解を招きやすい。８つの点を格納し、ｗ−ＮＡＦ技術のみを用いる場合には、本技術を用いて０．１６６ｍの追加対０．２５ｍの追加というコストで、ａＢ＋λＲを計算するための５−ＮＡＦまたは３−ＮＡＦ計算を用いてａＢを計算し得る。したがって、本技術は、ａＢ＋λＲの評価における０．０８３ｍの付加的な追加という代償でＥＣＤＳＡ署名の評価におけるｍの倍増を節約することが考えられ得る。
【００５８】
このアプローチは、基本的にＥＣＤＳＡ検証手順から倍増操作を除去する。すなわち、ＥＣＤＳＡ検証の徐々に増加するコストは、それぞれ（スケーリングの後で）０．８５ｍの追加（Ｆａｓｔ Ｖｅｒｉｆｙ）、１．０２ｍの追加（普通のＥＣＤＳＡ検証）ではなく、ｍ／２の追加のみとなる。すなわち、ＥＣＤＳＡ検証手順の７０〜１０４％の効率性改善を表している。重複点倍増の方法でできることをより十分に利用することによって、およびウィンドウイング（ｗｉｎｄｏｗｉｎｇ）とｗ−ＮＡＦの方法とを用いることによって、さらなる改善が行われ得る。
【００５９】
ＭＱＶおよびＥＣＤＳＡを含む図３の実施形態について、ＫＡ’＝ｃＹ＋ｄＢ＋λΣ＝ｃＹ＋ｄＢ−λＲ＋（（λｅｓ−１）Ｇ＋（λｒｓ−１）Ｑ）である。
【００６０】
【数１４】
とし、ここで整数ｘは、二進表現で表されるとする。ｃおよびｄがＪＳＦ表現である場合には、
【００６１】
【数１５】
が得られ、この式は、重み
【００６２】
【数１６】
（ここでｍ：＝ｌｏｇ２ｎ）を有する。その結果、
【００６３】
【数１７】
である。このλの選択によって、ＫＡ＋λＲを計算することは、まさにｗｔＨ（ｃ，ｄ）点の追加を含む。λは、このゼロでない成分が予め計算された点Ｙ、Ｂ、Ｙ−Ｂ、Ｙ＋Ｂに対してｃＹ＋ｄＢにおける対応する係数と同じ符号を有するように選ばれる（このことは、すべてのλが、実際に、一意的であることを保証する）。その結果、すべての計算は、（１２の点を要求するのでなく）８つの点Ｙ、Ｂ、Ｙ＋Ｂ、Ｙ−Ｂ、Ｒ＋Ｙ、Ｒ＋Ｂ、Ｒ＋Ｙ＋Ｂ、Ｒ＋Ｙ−Ｂに関係して行われ得る。いったんλが上記で示されたように決定されれば、量（λｅｓ−１）Ｇ＋（λｒｓ−１）Ｑは、ジョイント（ｊｏｉｎｔ）ＮＡＦ形式を用いて計算され得る。ＫＡ’をこのように評価することに伴う負荷の全体は、ほぼｍの点の追加およびｍの点の倍増である。明らかに、改善は、重複点倍増の方法でできることを利用することによって、およびウィンドウイングとｗ−ＮＡＦの方法とを用いることによって可能である。しかしながら、主たる改善は、組み合わされた計算が、倍増操作に対する相当な節約の見通しを提供することである。
【００６４】
上記のアプローチは、単純な側面チャネル攻撃（ｓｉｄｅ ｃｈａｎｎｅｌ ａｔｔａｃｋ）への抵抗を実施するために用いられ得る。詳細は、以下の通りである。
【００６５】
【数１８】
とし、ここですべての整数を二進表現であるとみなす。
【００６６】
【数１９】
であるから、
【００６７】
【数２０】
が得られる。ここで、λ＝λ＋＋λ−であるとする。ここでλ＋は、Ｌの任意の要素であり、λ−は、ｓｕｐｐ（ｃ）の外にあるすべての点に対して１に、そうでないときは０に設定されている。ｃＹ＋ｄＢ＋λ＋Ｒの計算は、５つの予め計算された点Ｙ、Ｂ、Ｙ＋Ｂ、Ｂ＋Ｒ、およびＹ＋Ｂ＋Ｒを用いて実行され得る。いったんλがＲ、Ｑ、およびＧを含む７つのゼロでない部分の合計を用いて上記で示されたように決定されれば、量λ−Ｒ＋（（λｅｓ−１）Ｇ＋（λｒｓ−１）Ｑ）が計算され得る。２２＝５×３＋３＋４の点を予め計算することによって、重複点の倍増を用い、正確にｍ＋２２の点の追加およびｍの点の倍増を用いて、ＫＡ’を計算し得る。λ−の選択は、点の倍増のための二進法の方法における各ステップが追加を伴うことを保証する。λ−：＝０を選ぶことによって、わずか１９の点のみを予め計算することが可能であり得るが、そのときは反復につき１つの追加を実行し、側面チャネル攻撃が可能であった可能性がある。このことは、そのような条件が獲得されるまで別のλ＋を選ぶことによって保証された可能性があるが、これは、側面チャネルの情報をそれ自身で漏洩し得る。上記のアプローチは、ＫＡの計算中にダミー点の追加操作を付加することに基づく単純な側面チャネル攻撃の防止の方法とほぼ同じコストを有するが、ＥＣＤＳＡ署名検証も遂行する。このように、ＥＣＤＳＡ署名検証は、このアプローチを用いて実質的に自由にできる。
【００６８】
ΣがＧによって生成される素数位数部分群にあることが仮定される。Σは、十分に大きな位数を有するべきである。ΣがＥＣＤＳＡ検証の方程式に対応する場合には、この条件は、ｈＲ≠Ｏであることをチェックすることによって、容易にチェックされ得る。ここで、ｈは曲線の余因子である。
【００６９】
上記で説明されたアプローチは、倍増操作の節約および重複点の倍増戦略を利用する見込みに起因して、性能の改善につながる。さらには、このアプローチは、鍵の合意プロトコルの実行中に鍵の認証ステップと鍵の設定ステップとを組み合わせることに限定されず、それは、いくつかの鍵を計算し、いくつかの楕円曲線の方程式を検証しなければならない任意の環境に適用され得る（事実、鍵は、秘密である必要さえない）。このこと、本アプローチが、計算された鍵が正しいか否か検証し得る環境において最も有用であるゆえんである（なぜなら、このことは、同次の楕円曲線の方程式Σ＝０が成り立つか否かに関する判定をもたらし得るからである）。このように、本アプローチは、計算された鍵の知識を本当に実証するすべての環境において効果的に機能する。
【００７０】
検証を鍵の計算と組み合わせる方法は、上記で説明されたよりもより一般的な環境において機能する。多数のＥＣＤＳＡ署名（証明書の連鎖）の検証は、計算および検証の方程式と各検証に対して異なるλとの組み合わせを用いることによって獲得され得る。同様に、任意の楕円曲線の検証および多数の楕円曲線の方程式のバッチ検証が可能である。
【００７１】
ＡＮＳＩ Ｘ９．６３ＮＩＳＴ ＳＰ８００−５６ａにおけるＥＣＤＨスキーム（ＥＣＩＥＳ、Ｕｎｉｆｉｅｄ Ｍｏｄｅｌ、ＳＴＳ、ＥＣＭＱＶ、ＥｌＧａｍａｌ暗号化を含む）を用いた鍵の計算もまた、可能である。正確さを提供された秘密でないＥＣＣ点の計算は、例えばＥＣＤＳＡ証明書を用いたＰＶ署名においてチェックされ得る。同様に、正確さを提供された多数のＥＣＣ点の計算がチェックされ得る。
【００７２】
また、そのような技術を（超楕円曲線、識別に基づく暗号システム等を含む）他の代数的構造における操作に適用することも可能である。
【００７３】
単純な側面チャネルの抵抗を提供するλの使用は、実質的に自由である。
【００７４】
上記は特定の例示的な実施形態に関して説明されてきたが、その変形は以下に続く特許請求の範囲内で可能であることが認識されるであろう。
【技術分野】
【０００１】
本発明は、公開鍵暗号法に関する。
（本発明の概要）
公開鍵暗号法は、一対の通信者の間の安全な通信を可能にし、一対の通信者のうちの一方の通信者が発するメッセージの認証を可能にするために用いられる。公開鍵暗号法において各通信者は、数学的関数による秘密鍵に関連した秘密鍵および公開鍵を利用する。その数学的関数は、関係者の秘密鍵が対応する公開鍵から獲得され得ないことを保証するために「困難な」数学的問題を提供する。そのような問題は、ＲＳＡ暗号システムにおいて用いられる２つの大きな素数の積を因数分解する困難さ、およびデジタル署名アルゴリズム（ＤＳＡ）において用いられる有限体上の離散対数問題の難しさ（ｉｎｔｒａｃｔａｂｉｌｉｙ）を含む。離散対数システムは、広く用いられ、そのようなシステムの特定の適用は、有限体上に定義された楕円曲線の点を使用する。楕円曲線暗号システム（ＥＣＣ）として参照されるそのようなシステムは、他のシステムよりも小さい鍵の大きさで高いレベルの安全性を提供する。
【０００２】
メッセージが安全に交換されるべきときは、通信者間でそれぞれの秘密鍵を開示しないで共有される鍵を構築するために、公開鍵および秘密鍵が、概して鍵の合意プロトコルとして参照される特定のプロトコルにおいて用いられる。次いで、共有される鍵は、通信者間のメッセージを暗号化および復号するために用いられ得る。
【０００３】
楕円曲線公開鍵の鍵の合意プロトコルは、典型的には以下のステップを含む。
・鍵のコントリビューション（ｋｅｙ ｃｏｎｔｒｉｂｕｔｉｏｎ）：各関係者は、任意の整数である秘密鍵と、かつ一時的な公開鍵を表す点を提供するためのシード点とから、任意の短期の（一時的な）公開鍵を生成し、対応する一時的な公開鍵（しかし、秘密鍵ではない）をもう一方の関係者に伝える。加えて、鍵のコントリビューションは、その長期の固定的な公開鍵を伝え得る。
・鍵の設定：各関係者は、他方の関係者から受け取った固定的および一時的な鍵に基づいて、および自身で生成した秘密鍵に基づいて、共有される鍵を計算する。楕円曲線の特性に起因して、両方の関係者は、同一の共有される鍵に到達する。
・鍵の認証：各関係者は、共通の鍵を計算する能力があり得る唯一の関係者が、本当に、その受け取られた通信する関係者である証拠を獲得するために、他方の関係者の長期の固定的な鍵の信頼性を検証する。
・鍵の確認：各関係者は、いずれかの関係者によって伝えられた鍵のコントリビューションに対応するストリング（ｓｔｒｉｎｇ）を介して通例ではメッセージの認証チェック値を伝えることによって、他方の関係者に対し共通の鍵の所有を実証する。このことは、各関係者に対して他方の関係者の真の識別を確認し、その関係者が首尾よく共通の鍵を計算したことを証明する。このステップは、鍵の合意プロトコルの一部として、またはその後に、共有される鍵の使用を介して行われ得る。
【０００４】
鍵の認証ステップは、典型的には上記で説明された他のプロトコルステップとは独立に実行され、対応する公開鍵を手段として関係者とその秘密鍵との間の結合の信頼性を請け合う証明書の有効性をチェックすることに通例では関係する。別個の鍵の認証ステップが、（例えば、証明書の使用における）より大きな柔軟性を可能にするが、かなりのコストで行われる。なぜなら、鍵の合意プロトコルのオンラインでの計算コストは、鍵の認証ステップのコストと、鍵の設定ステップ中の鍵の計算のコストとの合計によって支配されるからである。
【０００５】
証明書は、本質的に通信者の公開鍵への信頼された関係者の署名と、発行する関係者の名前および証明書の保有者の名前のような他の情報とが一緒になったものである。ＥＣＣシステムにおいて、署名は、通例ではＥＣＤＳＡプロトコルを用いて実行され、検証されるが、他の署名プロトコルもまた、用いられ得る。例として、ＥＣＤＳＡ署名生成は、ＥＣＣのドメインパラメーター、秘密鍵ｄ、およびメッセージｍに対して機能し、メッセージｍは、証明書に関しては、通信者の公開鍵を含む。出力は、署名（ｒ，ｓ）である。ここで署名の成分ｒおよびｓは、整数であり、以下のように進められる。
１．任意の整数
【０００６】
【数１】
を選ぶ。ｎは、ドメインパラメーターのうちの１つである。
２．ｋＧ＝（ｘ１，ｙ１）を計算し、ｘ１を整数
【０００７】
【数２】
に変換する。ここでＧは、楕円曲線Ｅ上の点であり、ドメインパラメーターのうちの１つである。
３．
【０００８】
【数３】
を計算する。ここでｒ＝０の場合には、ステップ１に戻る。
４．ｅ＝Ｈ（ｍ）を計算する。ここでＨは、出力がｎのビット長さを超えないビット長さを有する、暗号ハッシュ関数を示す（この条件が満たされない場合には、Ｈの出力は切り捨て（ｔｒｕｎｃａｔｅ）られ得る）。
５．ｓ＝ｋ−１（ｅ＋αｒ）ｍｏｄ ｎを計算する。ここでαは、署名者の長期の秘密鍵である。ｓ＝０の場合には、ステップ１に戻る。
６．対（ｒ，ｓ）をメッセージｍのＥＣＤＳＡ署名として出力する。
【０００９】
ＥＣＤＳＡ署名検証は、いくつかのドメインパラメーター、長期の公開鍵Ｑ（ここでＱ＝αＧ）、メッセージｍ、および上記で導かれた署名（ｒ，ｓ）に対して機能する。ＥＣＤＳＡ署名検証の出力は、署名の拒絶または承認であり、以下のように進められる。
１．ｒおよびｓが区間［１，ｎ−１］にある整数であることを検証する。すべての検証が失敗する場合には、拒絶が返される。
２．ｅ＝Ｈ（ｍ）を計算する。
３．ｗ＝ｓ−１ ｍｏｄ ｎを計算する。
４．ｕ１＝ｅｗ ｍｏｄ ｎおよびｕ２＝ｒｗ ｍｏｄ ｎを計算する。
５．Ｒ＝ｕ１Ｇ＋ｕ２Ｑ＝ｓ−１（ｅＧ＋ｒＱ）を計算する。（上記の３および４から）６．Ｒ＝∞の場合には、署名は、拒絶される。
７．Ｒのｘ座標ｘ１を整数
【００１０】
【数４】
に変換する。
【００１１】
【数５】
を計算する。
８．ν＝ｒの場合には、署名は、承認される。そうでない場合には、署名は、拒絶される。
【００１２】
ＥＣＧＤＳＡのような他の署名生成および検証のステップが用いられ得ること、および署名の完全性を確認する特定のステップが時として省略されることは、認識されるであろう。
【００１３】
したがって、通信者の公開鍵、すなわち通信者の公開鍵および他の情報を含むメッセージｍを認証するためには、証明書上の署名を検証することが必要である。
【００１４】
認証に続いて、各関係者が本当に同一であることを確認するのが通例である。２つの関係者ＡとＢとの間で鍵の合意プロトコルの実行中、関係者Ａが鍵ＫＡを構築している間に、関係者Ｂは、鍵ＫＢを構築する。鍵の確認は、Ａが何らかの量ｆ（ＫＡ）（ここでｆは、何らかの公知の関数である）をＢ（Ｂは、これを彼自身の計算された値ｆ（ＫＢ）と比較し、これらの値が一致する場合にのみ承認する（およびその逆））に伝えることによって、ＫＡについての知識をＢに対して実証することからなる。この関数ｆは、ｆ（ＫＡ）＝ｆ（ＫＢ）の場合に圧倒的な確率でＫＡ＝±ＫＢとなり、共通の鍵が設定されるような関数である。
【発明の概要】
【発明が解決しようとする課題】
【００１５】
上記で留意されたように、鍵の認証ステップは、鍵の合意プロトコルにかなりの計算負荷を追加する。したがって、本発明の目的は、上記の不利な点を除去または軽減することである。
【課題を解決するための手段】
【００１６】
一般的に言って、本出願人は、共有される鍵と証明書検証との組み合わせを結合して計算することによって、証明書の暗黙の検証が後続の鍵の確認ステップにおいて獲得されることを認識した。
【００１７】
好ましくは、署名検証は、証明書の検証の失敗の結果、共有される鍵の値の間の不一致が生じるような同次の検証方程式、すなわち０に等しい方程式を用いる。
【００１８】
１つの局面において、暗号システムを介して互いに通信する一対の通信者の間で共有されるべき暗号鍵を計算する方法が提供され、一対の通信者のうちの一方の通信者は、鍵を生成するためにその一方の通信者の秘密鍵情報と組み合わされるべき他方の通信者の公開鍵情報の証明書を受け取り、その方法は、公開鍵情報と秘密鍵情報とを組み合わせることによって鍵を計算するステップと、証明書の検証に失敗した結果として一方の通信者での鍵が他方の通信者で計算された鍵とが異なるように、証明書の検証に対応する成分を計算に含めるステップとを含む。
【００１９】
別の局面において、コンピューター読み取り可能な媒体、暗号ユニット、および上記の方法のステップを実行するために構成されるシステムが提供される。
例えば、本願発明は以下の項目を提供する。
（項目１）
暗号システムを介して互いに通信する一対の通信者の間で共有されるべき暗号鍵を計算する方法であって、該一対の通信者のうちの一方の通信者は、該鍵を生成するために該一方の通信者の秘密鍵情報と組み合わされるべき他方の通信者の公開鍵情報の証明書を受け取り、該方法は、
該公開鍵情報と該秘密鍵情報とを組み合わせることによって該鍵を計算するステップと、
該証明書の検証に失敗した結果として、該一方の通信者での鍵が該他方の通信者で計算された鍵とは異なるように、該証明書の検証に対応する成分を該計算に含めるステップと
を含む、方法。
（項目２）
前記検証は、前記証明書に含まれる署名を利用する、項目１に記載の方法。
（項目３）
前記成分は、前記証明書が検証するときにゼロに等しい、項目２に記載の方法。
（項目４）
前記証明書の検証を隠すために、任意の要素が前記成分に含まれる、項目３に記載の方法。
（項目５）
前記任意の要素は、前記署名の検証において繰り返される反復を提供することにより、側面チャネル攻撃を禁止するように選ばれる、項目４に記載の方法。
（項目６）
前記暗号システムは、楕円曲線暗号システムである、項目１に記載の方法。
（項目７）
前記計算は、重複点の倍増を用いて実行される、項目６に記載の方法。
（項目８）
前記証明書は、楕円曲線署名プロトコルによって実行される署名を含む、項目６に記載の方法。
（項目９）
前記署名プロトコルは、ＥＣＤＳＡである、項目８に記載の方法。
（項目１０）
前記公開鍵情報は、楕円曲線の点を表し、公開鍵情報と前記秘密鍵情報との組み合わせが点の倍増を含む、項目６に記載の方法。
（項目１１）
前記署名の検証は、重複点の倍増を要求する、項目１０に記載の方法。
（項目１２）
前記計算は、重複点の倍増を用いて実行される、項目１１に記載の方法。
（項目１３）
前記一方の通信者によって生成された鍵が前記他方の通信者の鍵と一致することを確認するステップを含む、項目１に記載の方法。
【図面の簡単な説明】
【００２０】
本発明の一実施形態がここで添付の図面を参照することにより説明される。
【図１】図１は、データ通信システムの概略を表示する図である。
【図２】図２は、第一の鍵の合意プロトコルを表示する図である。
【図３】図３は、さらなる鍵の合意プロトコルを表示する図である。
【発明を実施するための形態】
【００２１】
（本発明の詳細な説明）
したがって、図１を参照すると、暗号通信システムが、数字１０によって一般的に示されている。システム１０は、通信チャネル１６を介して互いに通信し得る第一の通信者１２および第二の通信者１４を有する。通信チャネル１６は、安全であり得るか、または、安全でないこともあり得る。各通信者は、選ばれた体上で定義される楕円曲線Ｅ上で機能する暗号化操作を実行するために、暗号モジュール１８および暗号モジュール２０をそれぞれ有する。暗号モジュール１８は、以下に説明されるもののような暗号化操作を実行するように構成されるハードウェア、コンピューター読み取り可能なソフトウェア命令または両者の組み合わせであり得る。
【００２２】
通信者１２は、長期の秘密鍵「ａ」と、対応する長期の公開鍵Ａ＝ａＧとを有し、ここでＧはドメインパラメーターにおける特定の曲線上の基点である。
【００２３】
通信者１２に対して公開鍵Ａを認証するために、証明書ＴＡが、信頼された機関から獲得される。証明書は、信頼された機関の公開鍵Ｑを用いて検証され得る公開鍵Ａに関する信頼された機関の署名を含む。
【００２４】
同様に、通信者１４は、長期の秘密鍵ｂと、対応する長期の公開鍵Ｂ＝ｂＧと、その公開鍵の証明書ＴＢとを有する。証明書ＴＢは、証明書ＴＡを獲得するために用いられたものとは異なる別の信頼された関係者によってか、または別の公開鍵を用いて、署名された可能性がある。
【００２５】
典型的には、通信者１２、１４はそれぞれ、対応する一時的な公開鍵ｘＧ、ｙＧを生成するセッションまたは一時的な秘密鍵として用いるための、任意の整数ｘ、ｙを生成し得る。しかしながら、明確さのために、共通の鍵が各通信者の長期の鍵を用いて設定される第一の実施形態が、説明される。
【００２６】
図２に示された第一の鍵の合意プロトコルにおいて、固定的（ｓｔａｔｉｃ）な楕円曲線ディフィ・ヘルマン（Ｄｉｆｆｉｅ Ｈｅｌｌｍａｎ）（ＥＣＤＨ）鍵生成が、証明書ＴＡ、ＴＢを用いて使用され、ＥＣＤＳＡを用いて署名される。
【００２７】
最初に、通信者１２、１４は、公開鍵Ａ、Ｂおよびそれぞれの証明書ＴＡ、ＴＢを交換する。共通の鍵は、Ｋ＝ａｂＧであり、Ｋ＝ａｂＧは、各関係者に対して、受け取られた公開情報および各関係者が有する秘密情報から計算され得る。その結果、ＫＡ＝ａＢおよびＫＢ＝ｂＡである。
【００２８】
鍵の信頼性を検証するために、証明書ＴＡおよびＴＢを検証するのが通常である。しかしながら、本実施形態において、鍵の生成および認証は、効率性を提供するために、結合して実行される。上記で留意されたように、ＥＣＤＳＡは、その検証において、
【００２９】
【数６】
を提供する。したがって、証明書が検証する場合には、ｓ−１（ｅＧ＋ｒＱ）−Ｒ＝Σ＝Ｏである。Ｒの値は、点Ｒのｘ座標の値になるようにｒを取ることによって署名成分ｒから復元され得る。ｘ座標は、２つの可能なｙの値を提供し、曖昧さを解決するために、正しい値の指示が署名に含まれるか、または、Ｒが計算されることを可能にする正しい値として値のうちの１つの値を選ぶために予め合意されたルールがある。Ｒを復元する付加的な技術は、米国特許出願第１１／３３３，２９６号において開示され、その内容は、参照により援用される。
【００３０】
各通信者はまた、証明書ＴＡ、ＴＢから署名（ｒ，ｓ）を有する。鍵Ｋを計算するために、通信者１２は、公開鍵情報と秘密鍵情報とを組み合わせ、署名の検証に対応する成分を含むことによって鍵ＫＡを計算する。したがって、
ＫＡ＝ａｂＧ＋λ１（ｓＢ−１（ｅＢＧ＋ｒＢＱＢ）−ＲＢ）
この式で、
λ１は、任意の値である。
ｒＢ、ｓＢは、証明書ＴＢの署名成分である。
ｅＢは、証明書におけるメッセージｍのハッシュである。証明書は、通信者１４の公開鍵Ｂを含む。そして、
ＲＢは、ｒＢから復元される値である。
【００３１】
証明書がＢの公開鍵を認証する場合には、署名検証成分
【００３２】
【数７】
がゼロであるべきであり、したがって、計算の結果が鍵ＫＡ＝ａＢをもたらすべきであることは、認められるであろう。
【００３３】
同様に、通信者１４は、ｒＡ、ｓＡ、およびＲＡの値が証明書ＴＡと関連するＫＢ＝ａｂＧ＋λ２（ｓＡ−１（ｅＡＧ＋ｒＡＱＡ）−ＲＡ）を計算する。さらにまた、証明書が認証する場合には、これは、鍵ＫＢ＝ｂＡをもたらすべきである。
【００３４】
通信者１２、１４がそれぞれの鍵ＫＡ、ＫＢを計算した後で、それらは、共通の鍵の機能である情報を交換するための鍵確認ステップを実行する。受け取られた情報が計算されたものと一致しない場合には、鍵は、拒絶される。
【００３５】
共通の鍵が異なる１つの理由は、証明書の検証部分から獲得された値がゼロでなく、証明書が認証していないことを示していることである。通信者１２、１４それぞれに対して通例では異なる各計算中に任意の値λを挿入することによって、認証プロセスの有効性が高められる。
【００３６】
こうして、証明書が認証する場合には、共通の鍵の値および、Ｏに対応する関係を結合して計算することによって、計算が削減される。
【００３７】
さらなる実施形態が図３に示され、ＭＱＶ鍵合意プロトコルが、ＥＣＤＳＡを用いて署名された証明書の認証と組み合わされている。
【００３８】
図３の実施形態において、通信者１２および１４はそれぞれ、長期の秘密鍵ａ、ｂ、長期の公開鍵Ａ、Ｂ、短期の秘密鍵ｘ、ｙおよび短期の公開鍵Ｘ、Ｙを有する。ＥＣＭＱＶにおいて、共通の鍵は、
Ｋ＝ｃＸ＋ｄＢ
の形式である。
ここで、
ｃ＝ｘ＋ａｇ（ｘ）（ｍｏｄ ｎ）かつ
ｄ＝ｃｇ（Ｙ）（ｍｏｄ ｎ）。
ここで、ｇは、楕円曲線の点を適切な整数に写像する公知の表現関数である。
【００３９】
各通信者がもう一方の通信者の証明書ＴＡ、ＴＢを有していると仮定すると、各通信者はそれぞれ、もう一方の通信者に短期の公開鍵Ｘ、Ｙを送る。
【００４０】
通信者１２は、ｓ１２＝（ｘ＋ａｇ（ｘ））ｍｏｄ ｎを計算する。通信者１４は、ｓ１４＝（ｙ＋ｂｇ（ｙ））ｍｏｄ ｎを計算する。次いで、共通の鍵Ｋは、Ｋ＝ｓ１２（Ｙ＋ｇ（ｙ）Ｂ）＝ｓ１４（Ｘ＋ｇ（ｘ）Ａ）として計算され得る。
【００４１】
鍵を認証するためには、通信者の長期の公開鍵の証明書が認証されなければならない。したがって、上記で説明されたように、共通の鍵Ｋは、通信者１２によって
ＫＡ＝ｓ１２（Ｙ＋ｇ（ｙ）Ｂ）＋λΣ＝（ｘ＋ａｇ（ｘ））（Ｙ＋ｇ（ｙ）Ｂ）＋（λ１ｅＢｓＢ−１）Ｇ＋（λ１ｒＢｓＢ−１）Ｑ＋λ１ＲＢ
として、かつ、通信者１４によって、
ＫＢ＝ｓ１４（Ｙ＋ｇ（ｘ）Ａ）＋λΣ＝（ｙ＋ｂｇ（ｙ））（Ｘ＋ｇ（ｘ）Ａ）＋（λ２ｅＡｓＡ−１）Ｇ＋（λ２ｒＡｓＡ−１）ＱＡ＋λ２ＲＡ
として、計算される。
【００４２】
各通信者に対して、λは、任意の整数であり、Σは、それぞれの証明書に対する署名検証の関係ｓ−１（ｅＧ＋ｒＱ）−Ｒである。
【００４３】
Σ＝Ｏと仮定すると、鍵は、一致し、証明書は、暗黙に認証される。
【００４４】
獲得された効率性は、点の倍増操作の節約および重複点の倍増戦略を用いる可能性に帰せられ得る。
【００４５】
安全性の観点から、λの任意の値は、大きさ
【００４６】
【数８】
の組から選ばれるべきである。なぜなら、この組が、ＥＣＤＬＰ問題を解決することの作業負荷に対応しているからである。λが選ばれる組は、変化され得、後続の変形は安全である。λがｔ＜（ｌｏｇ２ｎ）／２である大きさ２ｔの組から抜き出される場合には、鍵の認証強度は、ｔビットまで下がり得る。λのそのような選択とともに、ａＢ＋λＲを計算することは、ＢまたはＢ−Ｒを伴うｗｔＨ（ａ）点の追加を伴い、ｗｔＨは、値ａの二進表現のハミング重みである。これは、ａＢの計算に伴う点の追加と同一の数である。
【００４７】
量（λｅｓ−１）Ｇ＋（λｒｓ−１）Ｑは、その内容が参照により援用されるＶａｎｓｔｏｎｅ他、Ｓｐｒｉｎｇｅｒ、「Ｇｕｉｄｅ ｔｏ Ｅｌｌｉｐｔｉｃ Ｃｕｒｖｅ Ｃｒｙｐｔｏｇｒａｐｈｙ」、９８から１０１ページにおいてより十分に説明されている、隣接していない形式（ＮＡＦ；ｎｏｎ−ａｄｊａｃｅｎｔ ｆｏｒｍ）を用いて計算され得る。
【００４８】
この方法でＫＡを評価することの作業負荷は、およそｍの点の追加およびｍの倍増であり、ｍは、曲線のビットの大きさである。
【００４９】
比較によって、ＫＡ＝ａＢを評価することおよびＥＣＤＳＡ署名を検証することは、それぞれ５ｍ／６の追加および２ｍの倍増の作業負荷を有する。
【００５０】
したがって、３０％の改善は、達成可能である。上記の米国特許出願第１１／３３３，２９６号において示されている「高速検証（ｆａｓｔ ｖｅｒｉｆｙ）」技術が用いられる場合には、１０％程度の節約が可能である。
【００５１】
二進表現におけるよりむしろＮＡＦ表現において整数とともにλを考慮することによって、さらなる改善を行い得る。
【００５２】
【数９】
であるから、
【００５３】
【数１０】
が得られる（Ｌにおけるすべての整数は、ＮＡＦ形式であり、そのため一意的であることに留意されたい）。上記と類似の分析を実行して、ここで与えられたアプローチは、およそ５ｍ／６の追加およびｍの倍増をもたらす。この場合、ここで与えられたアプローチは、上記で説明された二進法のアプローチによる１．７０ｍの追加でなく、１．５２ｍの追加をもたらし、その結果、個別の計算（Ｆａｓｔ Ｖｅｒｉｆｙ、Ｏｒｄｉｎａｒｙ ＥＣＤＳＡ Ｖｅｒｉｆｙのそれぞれ）と比較してそれぞれ２２％、４７％の効率性の改善をもたらす。この場合、ａＢ−λＲ＝（ａ−λ＋＋λ−）Ｂ−λ＋（Ｒ−Ｂ）−λ−（Ｒ＋Ｂ）と書き得る。ここでλ＝λ＋＋λ−であり、λ＋およびλ−は、それぞれ、ａの対応する成分と同じまたは異なる符合を有するλの成分を示していることに留意されたい。
【００５４】
Ｖａｎｓｔｏｎｅ他、Ｓｐｒｉｎｇｅｒ、「Ｇｕｉｄｅ ｔｏ Ｅｌｌｉｐｔｉｃ Ｃｕｒｖｅ Ｃｒｙｐｔｏｇｒａｐｈｙ」、９９ページにおいて説明されたｗ−ＮＡＦ表現（ｗ≧２）に対して、これをさらに一般化し得る。そのとき、
【００５５】
【数１１】
であり、ここでｑ：＝２ｗ−１＋１およびｔ：＝ｗｔＨ（ａ）である（すべての整数は、ｗ−ＮＡＦ形式であり、それ故一意的である）。
【００５６】
【数１２】
と仮定する場合には、
【００５７】
【数１３】
を得る。より詳細な分析は、ａＢ＋λＲにおける追加が、ａＢが２ｗ−２ではなくおよそ２（ｗ＋１）（ｗ−２）／２のより大きな予め計算するコストを有することを除いて、（同一の方法を用いることによって）ａＢにおける追加と同一のコストで計算され得る。格納コストは、１対３（ｗ＝２）、２対８（ｗ＝３）、４対２４（ｗ＝４）、８対６４（ｗ＝５）である。したがって、格納コストが選択の尺度である場合には、比較は、いくぶん誤解を招きやすい。８つの点を格納し、ｗ−ＮＡＦ技術のみを用いる場合には、本技術を用いて０．１６６ｍの追加対０．２５ｍの追加というコストで、ａＢ＋λＲを計算するための５−ＮＡＦまたは３−ＮＡＦ計算を用いてａＢを計算し得る。したがって、本技術は、ａＢ＋λＲの評価における０．０８３ｍの付加的な追加という代償でＥＣＤＳＡ署名の評価におけるｍの倍増を節約することが考えられ得る。
【００５８】
このアプローチは、基本的にＥＣＤＳＡ検証手順から倍増操作を除去する。すなわち、ＥＣＤＳＡ検証の徐々に増加するコストは、それぞれ（スケーリングの後で）０．８５ｍの追加（Ｆａｓｔ Ｖｅｒｉｆｙ）、１．０２ｍの追加（普通のＥＣＤＳＡ検証）ではなく、ｍ／２の追加のみとなる。すなわち、ＥＣＤＳＡ検証手順の７０〜１０４％の効率性改善を表している。重複点倍増の方法でできることをより十分に利用することによって、およびウィンドウイング（ｗｉｎｄｏｗｉｎｇ）とｗ−ＮＡＦの方法とを用いることによって、さらなる改善が行われ得る。
【００５９】
ＭＱＶおよびＥＣＤＳＡを含む図３の実施形態について、ＫＡ’＝ｃＹ＋ｄＢ＋λΣ＝ｃＹ＋ｄＢ−λＲ＋（（λｅｓ−１）Ｇ＋（λｒｓ−１）Ｑ）である。
【００６０】
【数１４】
とし、ここで整数ｘは、二進表現で表されるとする。ｃおよびｄがＪＳＦ表現である場合には、
【００６１】
【数１５】
が得られ、この式は、重み
【００６２】
【数１６】
（ここでｍ：＝ｌｏｇ２ｎ）を有する。その結果、
【００６３】
【数１７】
である。このλの選択によって、ＫＡ＋λＲを計算することは、まさにｗｔＨ（ｃ，ｄ）点の追加を含む。λは、このゼロでない成分が予め計算された点Ｙ、Ｂ、Ｙ−Ｂ、Ｙ＋Ｂに対してｃＹ＋ｄＢにおける対応する係数と同じ符号を有するように選ばれる（このことは、すべてのλが、実際に、一意的であることを保証する）。その結果、すべての計算は、（１２の点を要求するのでなく）８つの点Ｙ、Ｂ、Ｙ＋Ｂ、Ｙ−Ｂ、Ｒ＋Ｙ、Ｒ＋Ｂ、Ｒ＋Ｙ＋Ｂ、Ｒ＋Ｙ−Ｂに関係して行われ得る。いったんλが上記で示されたように決定されれば、量（λｅｓ−１）Ｇ＋（λｒｓ−１）Ｑは、ジョイント（ｊｏｉｎｔ）ＮＡＦ形式を用いて計算され得る。ＫＡ’をこのように評価することに伴う負荷の全体は、ほぼｍの点の追加およびｍの点の倍増である。明らかに、改善は、重複点倍増の方法でできることを利用することによって、およびウィンドウイングとｗ−ＮＡＦの方法とを用いることによって可能である。しかしながら、主たる改善は、組み合わされた計算が、倍増操作に対する相当な節約の見通しを提供することである。
【００６４】
上記のアプローチは、単純な側面チャネル攻撃（ｓｉｄｅ ｃｈａｎｎｅｌ ａｔｔａｃｋ）への抵抗を実施するために用いられ得る。詳細は、以下の通りである。
【００６５】
【数１８】
とし、ここですべての整数を二進表現であるとみなす。
【００６６】
【数１９】
であるから、
【００６７】
【数２０】
が得られる。ここで、λ＝λ＋＋λ−であるとする。ここでλ＋は、Ｌの任意の要素であり、λ−は、ｓｕｐｐ（ｃ）の外にあるすべての点に対して１に、そうでないときは０に設定されている。ｃＹ＋ｄＢ＋λ＋Ｒの計算は、５つの予め計算された点Ｙ、Ｂ、Ｙ＋Ｂ、Ｂ＋Ｒ、およびＹ＋Ｂ＋Ｒを用いて実行され得る。いったんλがＲ、Ｑ、およびＧを含む７つのゼロでない部分の合計を用いて上記で示されたように決定されれば、量λ−Ｒ＋（（λｅｓ−１）Ｇ＋（λｒｓ−１）Ｑ）が計算され得る。２２＝５×３＋３＋４の点を予め計算することによって、重複点の倍増を用い、正確にｍ＋２２の点の追加およびｍの点の倍増を用いて、ＫＡ’を計算し得る。λ−の選択は、点の倍増のための二進法の方法における各ステップが追加を伴うことを保証する。λ−：＝０を選ぶことによって、わずか１９の点のみを予め計算することが可能であり得るが、そのときは反復につき１つの追加を実行し、側面チャネル攻撃が可能であった可能性がある。このことは、そのような条件が獲得されるまで別のλ＋を選ぶことによって保証された可能性があるが、これは、側面チャネルの情報をそれ自身で漏洩し得る。上記のアプローチは、ＫＡの計算中にダミー点の追加操作を付加することに基づく単純な側面チャネル攻撃の防止の方法とほぼ同じコストを有するが、ＥＣＤＳＡ署名検証も遂行する。このように、ＥＣＤＳＡ署名検証は、このアプローチを用いて実質的に自由にできる。
【００６８】
ΣがＧによって生成される素数位数部分群にあることが仮定される。Σは、十分に大きな位数を有するべきである。ΣがＥＣＤＳＡ検証の方程式に対応する場合には、この条件は、ｈＲ≠Ｏであることをチェックすることによって、容易にチェックされ得る。ここで、ｈは曲線の余因子である。
【００６９】
上記で説明されたアプローチは、倍増操作の節約および重複点の倍増戦略を利用する見込みに起因して、性能の改善につながる。さらには、このアプローチは、鍵の合意プロトコルの実行中に鍵の認証ステップと鍵の設定ステップとを組み合わせることに限定されず、それは、いくつかの鍵を計算し、いくつかの楕円曲線の方程式を検証しなければならない任意の環境に適用され得る（事実、鍵は、秘密である必要さえない）。このこと、本アプローチが、計算された鍵が正しいか否か検証し得る環境において最も有用であるゆえんである（なぜなら、このことは、同次の楕円曲線の方程式Σ＝０が成り立つか否かに関する判定をもたらし得るからである）。このように、本アプローチは、計算された鍵の知識を本当に実証するすべての環境において効果的に機能する。
【００７０】
検証を鍵の計算と組み合わせる方法は、上記で説明されたよりもより一般的な環境において機能する。多数のＥＣＤＳＡ署名（証明書の連鎖）の検証は、計算および検証の方程式と各検証に対して異なるλとの組み合わせを用いることによって獲得され得る。同様に、任意の楕円曲線の検証および多数の楕円曲線の方程式のバッチ検証が可能である。
【００７１】
ＡＮＳＩ Ｘ９．６３ＮＩＳＴ ＳＰ８００−５６ａにおけるＥＣＤＨスキーム（ＥＣＩＥＳ、Ｕｎｉｆｉｅｄ Ｍｏｄｅｌ、ＳＴＳ、ＥＣＭＱＶ、ＥｌＧａｍａｌ暗号化を含む）を用いた鍵の計算もまた、可能である。正確さを提供された秘密でないＥＣＣ点の計算は、例えばＥＣＤＳＡ証明書を用いたＰＶ署名においてチェックされ得る。同様に、正確さを提供された多数のＥＣＣ点の計算がチェックされ得る。
【００７２】
また、そのような技術を（超楕円曲線、識別に基づく暗号システム等を含む）他の代数的構造における操作に適用することも可能である。
【００７３】
単純な側面チャネルの抵抗を提供するλの使用は、実質的に自由である。
【００７４】
上記は特定の例示的な実施形態に関して説明されてきたが、その変形は以下に続く特許請求の範囲内で可能であることが認識されるであろう。
【特許請求の範囲】
【請求項１】
本願明細書に記載された発明。
【請求項１】
本願明細書に記載された発明。
【図１】
【図２】
【図３】
【図２】
【図３】
【公開番号】特開２０１３−３４２５１（Ｐ２０１３−３４２５１Ａ）
【公開日】平成２５年２月１４日（２０１３．２．１４）
【国際特許分類】
【外国語出願】
【出願番号】特願２０１２−２４７１３７（Ｐ２０１２−２４７１３７）
【出願日】平成２４年１１月９日（２０１２．１１．９）
【分割の表示】特願２００９−５３６５６９（Ｐ２００９−５３６５６９）の分割
【原出願日】平成１９年１１月１５日（２００７．１１．１５）
【出願人】（３９７０７１７９１）サーティコム コーポレーション (38)
【Ｆターム（参考）】
【公開日】平成２５年２月１４日（２０１３．２．１４）
【国際特許分類】
【出願番号】特願２０１２−２４７１３７（Ｐ２０１２−２４７１３７）
【出願日】平成２４年１１月９日（２０１２．１１．９）
【分割の表示】特願２００９−５３６５６９（Ｐ２００９−５３６５６９）の分割
【原出願日】平成１９年１１月１５日（２００７．１１．１５）
【出願人】（３９７０７１７９１）サーティコム コーポレーション (38)
【Ｆターム（参考）】
[ Back to top ]