(57)【特許請求の範囲】
【請求項１】
公開鍵暗号システムに関与する一対のコンピュータデバイスのうちの一方において共通鍵を生成する方法であって、前記共通鍵は、データ通信チャネル上でもう一方のコンピュータデバイスと通信している前記一方のコンピュータデバイスによって使用され、前記コンピュータデバイスの各々は、それぞれの長期非公開鍵およびそれぞれの対応する長期公開鍵を有し、前記共通鍵は、前記コンピュータデバイスのうちの一方の長期非公開鍵と前記コンピュータデバイスのうちのもう一方の長期公開鍵および一時公開鍵との組み合わせの形態を有し、前記方法は、
ａ）前記一方のコンピュータデバイスの暗号化ハードウェアモジュールが、前記もう一方のコンピュータデバイスの前記長期公開鍵を取得するステップと、
ｂ）前記暗号化ハードウェアモジュールが、前記もう一方のコンピュータデバイスの前記一時公開鍵が前記もう一方のコンピュータデバイスの前記長期公開鍵と同じか否かを決定するステップと、
ｃ）前記暗号化ハードウェアモジュールが、前記もう一方のコンピュータデバイスの前記長期公開鍵と前記一時公開鍵とが同じであることを決定すると、前記もう一方のコンピュータデバイスの前記長期公開鍵および前記一時公開鍵の両方として前記もう一方のコンピュータデバイスの前記長期公開鍵を利用することにより、前記共通鍵を生成するステップと、
ｄ）前記暗号化ハードウェアモジュールが、前記もう一方のコンピュータデバイスと情報を交換するために前記共通鍵を利用するステップと
を含む、方法。
【請求項２】
前記共通鍵を生成することは、前記組み合わせの同等表現を計算することを含む、請求項１に記載の方法。
【請求項３】
前記共通鍵を生成することは、前記一方のコンピュータデバイスの中間値を前記もう一方のコンピュータデバイスの前記長期公開鍵と組み合わせることを含み、前記中間値は、前記一方のコンピュータデバイスの前記長期非公開鍵および長期公開鍵を前記一方のコンピュータデバイスの一時非公開鍵と結合させる、請求項２に記載の方法。
【請求項４】
前記暗号システムは、加算群上で実装され、前記共通鍵は、
【数６９】
0005329676.tif 000087
に依存し、ＲＢは、前記もう一方のコンピュータデバイスの一時公開鍵であり、ＱＢは、前記もう一方のコンピュータデバイスの長期公開鍵であり、
【数７０】
0005329676.tif 000088
は、ＲＢから導出される整数であり、前記方法は、前記暗号化ハードウェアモジュールが、形態ｖＱＢを有する同等表現から前記共通鍵Ｋを計算するステップをさらに含み、ｖは、
【数７１】
0005329676.tif 000089
に依存している、請求項２または３のうちのいずれか一項に記載の方法。
【請求項５】
前記共通鍵を生成することは、ＥＣＭＱＶ鍵合意プロトコルに従うものであり、前記プロトコルは、形態
【数７２】
0005329676.tif 000090
の共通鍵を必要とし、ｈは、楕円曲線群の余因数であり、ｓＡは、前記中間値であり、前記方法は、前記暗号化ハードウェアモジュールが、νＱＢとして前記共通鍵Ｋを計算するステップをさらに含み、
【数７３】
0005329676.tif 000091
である、請求項４に記載の方法。
【請求項６】
前記共通鍵を生成することは、乗法群上で実装されるＭＱＶ鍵合意プロトコルに従うものであり、前記プロトコルは、形態
【数７４】
0005329676.tif 000092
の共通鍵を必要とし、
ＲＢは、前記もう一方のコンピュータデバイスの前記一時公開鍵であり、
ＱＢは、前記もう一方のコンピュータデバイスの前記長期公開鍵であり、
【数７５】
0005329676.tif 000093
は、前記一時公開鍵から導出される整数であり、
ｓＡは、前記中間値であり、前記方法は、前記暗号化ハードウェアモジュールが、
【数７５−１】
0005329676.tif 000094
として前記共通鍵を計算するステップをさらに含み、ｙ＝ｈｓＡＲＢ＋ｈｓＡであり、ｈは、群の余因数である、請求項３に記載の方法。
【請求項７】
前記共通鍵を生成することは、ＭＴＩ鍵合意プロトコルに従うものであり、前記プロトコルは、形態Ｋ＝（αｙ）ａＺＢｘの共通鍵を必要とし、
αｙは、前記もう一方のコンピュータデバイスの一時公開鍵であり、
ＺＢは、前記もう一方のコンピュータデバイスの長期公開鍵であり、
ｘは、前記一方のコンピュータデバイスの一時非公開鍵であり、
ａは、前記一方のコンピュータデバイスの長期非公開鍵であり、
前記方法は、前記暗号化ハードウェアモジュールが、Ｋ＝（ＺＢ）ａ＋ｘとして前記共通鍵を計算するステップをさらに含む、請求項３に記載の方法。
【請求項８】
前記暗号化ハードウェアモジュールが、前記鍵が同じか否かを決定するために、前記もう一方のコンピュータデバイスから受信された前記一時公開鍵および前記長期公開鍵を比較するステップをさらに含む、請求項２〜７のうちのいずれか一項に記載の方法。
【請求項９】
前記暗号化ハードウェアモジュールが、前記もう一方のコンピュータデバイスの前記長期公開鍵および前記一時公開鍵が同じであるという指標について、前記もう一方のコンピュータデバイスから受信されたメッセージを調査するステップと、前記指標を識別すると前記同等表現を計算するステップとをさらに含む、請求項２〜７のうちのいずれか一項に記載の方法。
【請求項１０】
前記同等表現は、前記長期公開鍵の線形結合であり、前記方法は、前記暗号化ハードウェアモジュールが、前記長期公開鍵から導出される事前計算された値から前記共通鍵を累積するステップをさらに含む、請求項２〜７のうちのいずれか一項に記載の方法。
【請求項１１】
前記暗号システムは、加算群上で実装され、前記事前計算された値は、前記長期公開鍵の倍数である、請求項１０に記載の方法。
【請求項１２】
前記暗号システムは、乗法群上で実装され、前記事前計算された値は、前記長期公開鍵のべき乗の結果である、請求項１０に記載の方法。
【請求項１３】
通信リンク上で通信し、共通鍵を共通する一対のコンピュータデバイスを有する暗号化システムであって、少なくとも、前記コンピュータデバイスのうちの一方の暗号化ハードウェアモジュールは、請求項１〜１２のうちのいずれか一項に記載の方法に従って、前記共通鍵を生成するように動作可能である、暗号化システム。
【請求項１４】
暗号化システムの中の一方のコンピュータデバイスと関連付けられる暗号モジュールであって、前記暗号化システムは、もう一方のコンピュータデバイスを含み、前記暗号化ハードウェアモジュールは、
コントローラと、
前記もう一方のコンピュータデバイスの一時公開鍵および長期公開鍵と前記一方のコンピュータデバイスの非公開鍵との組み合わせから共通鍵を生成するように動作可能である算術論理演算ユニットと、
前記もう一方のコンピュータデバイスの前記一時公開鍵と前記長期公開鍵とが同じであるか否かを決定するように動作可能であるコンパレータと
を備え、
前記コントローラは、前記もう一方のコンピュータデバイスの前記一時公開鍵と前記長期公開鍵とが同じであると前記コンパレータが決定する場合に、前記共通鍵の計算において前記一時公開鍵として前記長期公開鍵を利用することを前記算術演算ユニットに命令するように動作可能である、暗号モジュール。
【請求項１５】
前記コントローラは、前記共通鍵を計算する際に前記組み合わせの同等表現を計算することを前記算術論理演算ユニットに指図するように動作可能である、請求項１４に記載の暗号モジュール。
【請求項１６】
前記もう一方のコンピュータデバイスの前記長期公開鍵から導出される事前計算された値は、メモリに記憶され、前記算術論理演算ユニットは、前記共通鍵を計算する際に前記事前計算された値を使用するように動作可能である、請求項１５に記載の暗号モジュール。
【請求項１７】
前記コンパレータは、前記長期公開鍵および前記一時公開鍵を表す一対の値を比較するように動作可能である、請求項１４に記載の暗号モジュール。
【請求項１８】
前記もう一方のコンピュータデバイスの前記一時公開鍵と前記長期公開鍵とが同じか否かを決定することは、指標を既知の値と比較することを含む、請求項１４に記載の暗号モジュール。
【請求項１９】
請求項１〜１２のうちのいずれか一項に記載の方法を実行するためのコンピュータ実行可能な命令を格納しているコンピュータ読み取り可能な媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
（技術分野）
以下は、暗号化システムに関し、より具体的には、共通秘密鍵を計算する方法および装置に関する。
【背景技術】
【０００２】
（従来技術の説明）
公開鍵暗号化は、公衆ネットワーク上を伝送される情報に対するセキュリティを提供するために使用される。多数の暗号プロトコルが、セキュリティ、完全性、および認証を提供するために利用可能である。それらのセキュリティは、因数分解および離散対数問題等の、ある数学問題の明白な取り扱い難さに基づいている。これらは通常、計算能力の限定およびバッテリ電力の利用可能性を有する。公開鍵スキームは、利用可能である以上の計算能力を必要とすることがある。大抵の暗号化システムでは、多数のビットを有するパラメータが、より優れたセキュリティを提供するが、通常、速度の減少という不利益を負う。そのような環境においては、楕円曲線暗号化（ＥＣＣ）が、ＲＳＡ等の他の暗号化システムと比べて少ない数のビットを有するパラメータを有する必要レベルのセキュリティを提供するので、特に魅力的である。計算は、操作されなければならないデータがより少量であるほど、それに対応してより高速になる。セキュリティは、携帯電話、ポケットベル、およびスマートカードを含む、移動コンピュータデバイス等の制約環境における要件である。強化されたセキュリティに対する継続的な需要を考慮して、可能な限り迅速に暗号動作を最適化し、それにより、既存のプロトコルのより高いセキュリティ実装を実行可能にする継続的な必要がある。
【０００３】
デジタル署名は、認証を提供するために使用される暗号プロトコルの類である。全ての公開鍵システムの場合のように、送信者が、非公開鍵と、数学的に相互に関係付けられる対応する公開鍵とを有する。公開鍵は、証明書またはディレクトリを通して、他のユーザに利用可能となり、認証される。送信者は、非公開鍵を使用してメッセージに署名し、受信者は、真正の公開鍵を使用することによって署名を検証することができる。そのようなシステムは、大きい素数の積によって生じる数の因数分解、および有限フィールドで対数を得ることの困難等の、「難しい」数学問題に基づいている。根本的な問題の困難は、非公開鍵の所有者のみが、その所有者の公開鍵を使用して検証する署名を生成できるという保証を提供することである。
【発明の概要】
【課題を解決するための手段】
【０００４】
ユーザは、データ通信ネットワーク上で情報を交換するコンピュータデバイスであり、概して通信者と呼ばれる。通信者は、説明を簡単にするために、Ａｌｉｃｅ、Ｂｏｂ等の個人名によって口語的に呼ばれる。
【０００５】
しばしば、関心の対象は、公開鍵暗号システムの２人のユーザの間で秘密鍵を共通にし、次いで、それは暗号化されたデータを交換するために対称鍵暗号化スキームにおいて使用され得ることである。対称鍵プロトコルは、データを暗号化することにおいて公開鍵プロトコルよりも高速であるが、通信者間での共通秘密鍵の確立が難しい。公開鍵暗号システムは、一対の通信者が共通秘密鍵を確立し得るように、共通鍵を確立するために使用され得る。この秘密鍵は、対称鍵スキームを使用して、将来の通信を確保するために使用することができる。１つの部類の鍵確立プロトコルは、鍵輸送プロトコルであって、これにおいては、単一のイニシエータが秘密鍵を作成し、それを受信者に安全に転送する。別の部類の鍵確立プロトコルは、鍵合意プロトコルであって、これにおいては、全ての参加エンティティが、共通秘密鍵を導出するために使用される情報に寄与する。
例えば、本発明は以下の項目を提供する。
（項目１）
公開鍵暗号システムに関与する一対の通信者のうちの一方において共通鍵を生成する方法であって、該共通鍵は、データ通信チャネル上でもう一方の通信者と通信している該一方の通信者によって使用され、該通信者の各々は、長期非公開鍵および対応する長期公開鍵をそれぞれ有し、該共通鍵は、該通信者のうちの一方の長期非公開鍵と該通信者のうちのもう一方の長期公開鍵および一時公開鍵との組み合わせの形態を有し、該方法は、
ａ）該一方の通信者が、該もう一方の通信者の該長期公開鍵を取得するステップと、
ｂ）該一方の通信者が、該もう一方の通信者の該一時公開鍵が該もう一方の通信者の該長期公開鍵と同じか否かを決定するステップと、
ｃ）該もう一方の通信者の該長期公開鍵と該一時公開鍵とが同じであることを決定すると、該一方の通信者は、該共通鍵を生成する際に、該もう一方の通信者の該長期公開鍵および該一時公開鍵の両方として該もう一方の通信者の該長期公開鍵を利用するステップと、
ｄ）該通信者の間で情報を交換するために該共通鍵を利用するステップと
を含む、方法。
（項目２）
上記もう一方の通信者の上記長期公開鍵と上記一時公開鍵とが同じであることを決定すると、上記一方の通信者は、上記組み合わせの同等表現を計算することによって上記共通鍵を生成する、項目１に記載の方法。
（項目３）
上記共通鍵は、上記一方の通信者の中間値を上記もう一方の通信者の上記長期公開鍵と組み合わせ、該中間値は、該一方の通信者の上記長期非公開鍵および長期公開鍵を該一方の通信者の一時非公開鍵と結合させる、項目２に記載の方法。
（項目４）
項目３または４のうちのいずれか一項に記載の方法であって、
上記暗号システムは、加算群上で実装され、上記共通鍵は、
【数６９】
0005329676.tif 000002
に依存し、ＲＢは、上記もう一方の通信者の一時公開鍵であり、ＱＢは、該もう一方の通信者の長期公開鍵であり、
【数７０】
0005329676.tif 000003
は、ＲＢから導出される整数であり、該方法は、上記一方の通信者が、形態ｖＱＢを有する同等表現から上記共通鍵Ｋを計算するステップをさらに含み、ここに、ｖは、
【数７１】
0005329676.tif 000004
に依存している、方法。
（項目５）
項目４に記載の方法であって、
上記共通鍵は、ＥＣＭＱＶ鍵合意プロトコルに従って生成され、形態
【数７２】
0005329676.tif 000005
を有し、ここに、ｈは、楕円曲線群の余因数であり、ｓＡは、上記中間値であり、該方法は、ｖＱＢとして上記共通鍵Ｋを計算するステップをさらに含み、ここに、
【数７３】
0005329676.tif 000006
である、方法。
（項目６）
項目３に記載の方法であって、
上記共通鍵は、乗法群上で実装されるＭＱＶ鍵合意プロトコルに従って生成され、形態
【数７４】
0005329676.tif 000007
の共通鍵を必要とし、ここに、
ＲＢは、上記もう一方の通信者の上記一時公開鍵であり、
ＱＢは、該もう一方の通信者の上記長期公開鍵であり、

【数７５】
0005329676.tif 000008
は、該一時公開鍵から導出される整数であり、
ｓＡは、上記中間値であり、該方法は、ＱＢｙとして該共通鍵を計算するステップをさらに含み、ここに、ｙ＝ｈｓＡＱＢ＋ｈｓＡであり、ｈは、群の余因数である、方法。
（項目７）
項目３に記載の方法であって、
上記共通鍵は、ＭＴＩ鍵合意プロトコルに従って生成され、形態Ｋ＝（αｙ）ａＺＢｘを有し、ここに、
αｙは、上記もう一方の通信者の一時公開鍵であり、
ＺＢは、該もう一方の通信者の長期公開鍵であり、
ｘは、上記一方の通信者の一時非公開鍵であり、
ａは、該一方の通信者の長期非公開鍵であり、
該方法は、該一方の通信者がＫ＝（ＺＢ）ａ＋ｘとして該共通鍵を計算するステップをさらに含む、方法。
（項目８）
上記鍵が同じか否かを決定するために、上記もう一方の通信者から受信された上記短期公開鍵および上記長期公開鍵を比較するステップを含む、項目２〜７のうちのいずれか一項に記載の方法。
（項目９）
上記公開鍵が同じであるという指標について、上記もう一方の通信者から受信されたメッセージを調査するステップと、該指標を識別すると上記同等表現を計算するステップとを含む、項目２〜７のうちのいずれか一項に記載の方法。
（項目１０）
上記同等表現は、上記長期公開鍵の線形結合であり、上記方法は、該長期公開鍵から導出される事前計算された値から上記共通鍵を累積するステップを含む、項目２〜７のうちのいずれか一項に記載の方法。
（項目１１）
上記暗号システムは、加算群上で実装され、上記事前計算された値は、上記長期公開鍵の倍数である、項目１０に記載の方法。
（項目１２）
上記暗号システムは、乗法群上で実装され、上記事前計算された値は、上記長期公開鍵のべき乗の結果である、項目１０に記載の方法。
（項目１３）
通信リンク上で通信し、共通鍵を共通する一対の通信者を有する暗号化システムであって、該共通鍵は、項目１〜１２のうちのいずれか一項に記載の方法に従って該通信者のうちの少なくとも一方によって生成される、暗号化システム。
（項目１４）
暗号化システムの中の一方の通信者と関連付けられる暗号モジュールであって、該モジュールは、
コントローラと、
もう一方の通信者の一時および長期公開鍵と該一方の通信者の非公開鍵との組み合わせから共通鍵を生成するように動作可能である算術論理演算ユニットと、
該もう一方の通信者の該一時公開鍵と長期公開鍵とが同じであるか否かを決定するように動作可能であるコンパレータと
を備え、該コントローラは、該鍵が同じであると該コンパレータが決定する場合に、該共通鍵の計算において該一時公開鍵として該長期公開鍵を利用することを該算術演算ユニットに命令するように動作可能である、モジュール。
（項目１５）
上記コントローラは、上記共通鍵を計算する際に上記組み合わせの同等表現を計算することを上記算術論理演算ユニットに指図するように動作可能である、項目１４に記載の暗号モジュール。
（項目１６）
上記もう一方の通信者の上記長期公開鍵から導出される事前計算された値は、メモリに記憶され、上記算術論理演算ユニットは、上記共通鍵を計算する際に該事前計算された値を使用するように動作可能である、項目１５に記載の暗号モジュール。
（項目１７）
上記コンパレータは、上記長期公開鍵および上記一時鍵を表す一対の値を比較するように動作可能である、項目１４に記載の暗号モジュール。
（項目１８）
上記コンパレータは、指標を既知の値と比較するように動作可能である、項目１４に記載の暗号モジュール。
【図面の簡単な説明】
【０００６】
ここで、添付図面を参照して、一例のみとして実施形態を説明する。
【図１】図１は、暗号化システムの概略図である。
【図２】図２は、ＥＣＭＱＶプロトコルを使用した鍵合意の既知の方法を示す、フローチャートである。
【図３】図３は、図２からの組込み鍵検証ステップの詳細を示す、フローチャートである。
【図４】図４は、ＥＣＭＱＶによる加速鍵合意の実施形態を示す、フローチャートである。
【図５】図５は、一方の通信者によって行われる、図４からの共通秘密鍵の加速計算の詳細を示す、フローチャートである。
【図６】図６は、一方の通信者によって行われる、図４からの共通秘密鍵の加速計算の詳細を示す、フローチャートである。
【図７】図７は、別の通信者によって行われる、図４からの共通秘密鍵の加速計算の詳細を示す、フローチャートである。
【図８】図８ａは、ＥＣＭＱＶプロトコルを使用した同時スカラー乗法の既知の方法を示す、フローチャートである。図８ｂは、図６および７の技法を使用した同時スカラー乗法の加速方法を示す、フローチャートである。
【図９】図９は、乗法群上でＭＱＶプロトコルを使用した鍵合意の既知の方法を示す、フローチャートである。
【図１０】図１０は、乗法群上でＭＱＶプロトコルを使用した加速鍵合意の実施形態を示す、フローチャートである。
【図１１】図１１ａは、図９からの同時べき乗の方法を示す、フローチャートである。図１１ｂは、図１０からの加速同時べき乗の方法を示す、フローチャートである。
【図１２】図１２は、並列アーキテクチャとともにＭＱＶプロトコルを使用した加速鍵合意の代替実施形態を示す、フローチャートである。
【図１３】図１３は、単一鍵転送とともにＭＱＶプロトコルを使用した加速鍵合意の代替実施形態を示す、フローチャートである。
【図１４】図１４は、並列アーキテクチャおよび単一鍵転送とともにＭＱＶプロトコルを使用した加速鍵合意の代替実施形態を示す、フローチャートである。
【図１５】図１５は、単一鍵転送とともにＭＱＶプロトコルを使用した加速鍵合意の別の代替実施形態を示す、フローチャートである。
【図１６】図１６は、並列アーキテクチャおよび単一鍵転送とともにＭＱＶプロトコルを使用した加速鍵合意の別の代替実施形態を示す、フローチャートである。
【図１７】図１７は、ＭＴＩプロトコルの代替実施形態を示すフローチャートである。
【発明を実施するための形態】
【０００７】
ＭＱＶ（Ｍｅｎｅｚｅｓ、Ｑｕ、Ｖａｎｓｔｏｎｅ）プロトコルは、公開鍵暗号システムの２人のユーザの間で鍵を共通する方法を提供し、鍵の認証を提供する鍵合意プロトコル群に属する。このプロトコルは、米国特許第５，７６１，３０５号、米国特許第５，８８９，８６５号、米国特許第５，８９６，４５５号、および米国特許第６，１２２，７３６号で説明されている。
【０００８】
それには、いくつかの変形があり、そのうちのいくつかは標準化され、したがって、以下の説明の基礎として使用される。ＭＱＶ鍵合意プロトコルは、有限フィールド上で定義される両方の乗法群で、または楕円曲線群等の加算群を使用して、実装されてもよい。一般的アルゴリズムは、両方の場合において同様のままである。ＭＱＶの表記が、以下の表に挙げられる。
【０００９】
【表１】
0005329676.tif 000009
ＭＱＶプロトコルの乗法群バージョンが、以下で説明される。具体的には、一対の通信者ＡｌｉｃｅとＢｏｂとが、Ｋとして示される鍵を共通するために、２パスＭＱＶ変形を使用する。
１．Ａｌｉｃｅが、間隔１から（ｑ−１）までにおいてランダムにｋＡを選択し、ここに、ｑは群の位数である。
２．Ａｌｉｃｅが、
【００１０】
【数１】
0005329676.tif 000010
を計算し、それをＢｏｂに送信し、ここに、ｇは群の生成器である。
３．Ｂｏｂが、間隔１から（ｑ−１）までにおいてランダムにｋＢを選択する。
４．Ｂｏｂが、
【００１１】
【数２】
0005329676.tif 000011
を計算し、それをＡｌｉｃｅに送信する。
５．Ａｌｉｃｅが、ｓＡ＝（ｋＡ＋ｄＡＲＡ）ｍｏｄｑを計算し、共通秘密鍵が
【００１２】
【数３】
0005329676.tif 000012
になる。
６．ＢｏｂがｓＢ＝（ｋＢ＋ｄＢＲＢ）ｍｏｄｑを計算し、共通秘密鍵が
【００１３】
【数４】
0005329676.tif 000013
になる。
【００１４】
鍵合意プロトコルの計算上の集中的部分は、Ｋを決定する際に行われるべき乗である。
【００１５】
ＭＱＶプロトコルがＡＮＳＩ  Ｘ９．６２およびＩＥＥＥ  Ｐ１３６３規格で標準化されたと鍵に、プロトコルをより効率的にするために切捨て演算が導入された。標準化されたようなＭＱＶプロトコルは、指数のビット長を縮小するために切捨て演算を使用し、
【００１６】
【数５】
0005329676.tif 000014
によって示される。
【００１７】
切捨て演算の使用は、指数がより短いので、計算を加速し、この切捨ては、プロトコルのセキュリティに影響を及ぼさないと考えられる。
【００１８】
ＭＱＶプロトコルの別のバージョンは、以下で説明される鍵確認とともに３パス変形を使用する楕円曲線ＭＱＶ（ＥＣＭＱＶ）プロトコルである。
１．Ａｌｉｃｅが、間隔１から（ｑ−１）までにおいてランダムにｋＡを選択し、ここに、ｑは群の位数である。
２．Ａｌｉｃｅが、ＲＡ＝ｋＡＰを計算し、ＲＡおよびＱＡをＢｏｂに送信し、ここに、Pは、楕円曲線群の要素を生成する曲線上の点である。
３．Ｂｏｂが、ＲＡの組込み鍵検証を行い、ＲＡが無限大に位置しない点であり、群の要素であり、かつ楕円曲線上に位置する点であることを確実にする。
４．Ｂｏｂが、間隔１から（ｑ−１）までにおいてランダムにｋＢを選択する。
５．Ｂｏｂが、ＲＢ＝ｋＢＰおよび
【００１９】
【数６】
0005329676.tif 000015
および
【００２０】
【数７】
0005329676.tif 000016
を計算し、ここに、ｈは群の余因数である。
６．Ｋは座標（ｘ，ｙ）を有する点であり、Ｂｏｂは、その入力としてＫのｘ座標を用いて、鍵導出作用（ＫＤＦ）を実行し、２つの付属鍵ｋ１およびｋ２を導出する。これは、（ｋ１，ｋ２）←ＫＤＦ（ｘＫ）として示される。
７．Ｂｏｂがメッセージ認証コード（ＭＡＣ）を使用してタグｔＢを計算する。これは、      
【００２１】
【化１】
0005329676.tif 000017
として示される。
８．ＢｏｂがｔＢ、ＱＢ、ＲＢをＡｌｉｃｅに送信する。
９．ＡｌｉｃｅがＲＢの組込み公開鍵検証を行い、ＲＢが無限大に位置しない点であり、群の要素であり、かつ楕円曲線上に位置する点であることを確実にする。
１０．Ａｌｉｃｅが
【００２２】
【数８】
0005329676.tif 000018
および
【００２３】
【数９】
0005329676.tif 000019
を計算し、ここに、ｈは群の余因数である。
１１．Ａｌｉｃｅが上記のステップ６で説明されるような（ｋ１，ｋ２）を計算する。
１２．Ａｌｉｃｅが
【００２４】
【化２】
0005329676.tif 000020
を計算し、ｔ＝ｔＢであることを検証する。
１３．Ａｌｉｃｅが
【００２５】
【化３】
0005329676.tif 000021
を計算し、ｔＡをＢｏｂに送信する。
１４．Ｂｏｂが
【００２６】
【化４】
0005329676.tif 000022
を計算し、ｔ＝ｔＡであることを検証する。
１５．次いで、合意したセッション鍵がｋ２になる。
【００２７】
上記で説明される乗法群の実装と同様に、加算群を使用するＥＣＭＱＶプロトコルは、Ｋを決定するために、点乗法とも呼ばれるスカラー乗法を実装すると鍵に計算において最も集中的である。
【００２８】
べき乗およびスカラー乗法の両方の場合に、Ｋを計算すると鍵の効率を増加させるために使用されるいくつかの方法がある。１つの方法は、例えば、並行してそれぞれのＫ値を計算するために、通信者ＡｌｉｃｅとＢｏｂとを組織化することによって、アルゴリズム効率を増加させる。しかしながら、このアーキテクチャ変更は、計算強度を低減しない。
【００２９】
ここで図１を参照すると、暗号化システム１０は、概して、通信チャネル１６上で「Ｂｏｂ」と呼ばれる第２の通信者１４と通信する「Ａｌｉｃｅ」と呼ばれる第１の通信者１２を備える。各通信者１２、１４は、指定された機能を果たすために必要なプロセッサ、メモリ、電力供給、入力および出力デバイスを含む、コンピュータ、サーバ、携帯電話、ＰＤＡ、ＡＴＭ、または同等物等のコンピュータデバイスである。各通信者１２、１４は、暗号動作の入力、出力、および中間部分を記憶するための独自のメモリ２０を有するか、または通信者（１２、１４）の一部である外部メモリ２０にアクセスできる暗号モジュール１８を含む。図１に示された実施例では、第１の通信者１２は、暗号モジュール１８の外部にあるメモリ２０を含み、第２の通信者１４は、データを記憶する能力を任意の好適な配設で提供できることを図示するように、暗号モジュール１８の内部にあるメモリ２０を含むことが分かる。また、必要または所望であれば、メモリ２０は、通信者１２、１４の外部にあり、（例えば、ネットワーク接続等を介して）アクセス可能となり得ることが理解されるであろう。
【００３０】
暗号モジュール１８は、暗号化／暗号解読、署名、およびモジュラー演算等の暗号動作を行うように構成される。典型的には、暗号モジュール１８は、乱数発生器２２と、非公開鍵を記憶するための安全な記憶装置３０と、暗号動作を行うための算術論理演算ユニットＡＬＵ２８とを含む。
【００３１】
メモリ３０は、メモリ２０（図１に示される）の全体または一部を備えてもよく、または示されるような暗号モジュール１８の中の別個の構成要素として提供されてもよいことが理解されるであろう。メモリ３０は、ランダムアクセスメモリ（ＲＡＭ）、読み出し専用メモリ（ＲＯＭ）、および／または任意の他の種類の好適なメモリ構造を含んでもよい。
【００３２】
ＡＬＵ２８の計算動作は、コントローラ２４の中に存在するか、またはコントローラ２４にアクセス可能であり、かつ命令バス３５を介してＡＬＵ２８に伝達される、配線またはプログラムされた命令を介して制御される。ＡＬＵ２８の操作を行い、結果を出力する時に、コントローラ２４がメモリ３０を利用することを可能にするように、メモリバス３６も提供される。ＡＬＵ２８は、コントローラ２４の指図の下で種々の動作を行うために使用されてもよい。
【００３３】
命令を実行する、本明細書において例示される任意のモジュールまたは構成要素は、記憶媒体、コンピュータ記憶媒体、または、例えば、磁気ディスク、光ディスク、あるいはテープ等のデータ記憶デバイス（取外し可能および／または取外し不可能）等の、コンピュータ可読媒体を含んでもよく、または別様にそれらにアクセスできてもよいことが理解されるであろう。コンピュータ記憶媒体は、コンピュータ可読命令、データ構造、プログラムモジュール、または他のデータ等の情報を記憶するための任意の方法または技術で実装される、揮発性および不揮発性、取外し可能および取外し不可能媒体を含んでもよい。コンピュータ記憶媒体の実施例は、ＲＡＭ、ＲＯＭ、ＥＥＰＲＯＭ、フラッシュメモリまたは他のメモリ技術、ＣＤ−ＲＯＭ、デジタル多用途ディスク（ＤＶＤ）または他の光学記憶装置、磁気カセット、磁気テープ、磁気ディスク記憶装置または他の磁気記憶デバイス、または、所望の情報を記憶するために使用することができ、アプリケーション、モジュール、または両方によってアクセスすることができる任意の他の媒体を含む。任意のそのようなコンピュータ記憶媒体は、コントローラ２４の一部であってもよく、またはそこにアクセス可能あるいは接続可能であってもよい。本明細書で説明される任意のアプリケーションまたはモジュールは、そのようなコンピュータ可読媒体によって記憶または別様に保持されてもよいコンピュータ可読／実行可能命令を使用して実装されてもよい。
【００３４】
暗号モジュールはまた、メモリ２０に記憶されたデータを比較するためのコンパレータ３９も含む。
【００３５】
通信者１２、１４はそれぞれ、有限フィールドＦｐ上で定義される楕円曲線群Ｅと、楕円曲線暗号システムのパラメータを共通する。基準点Ｐを含むパラメータは、メモリ３０に記憶され、コントローラ２４にアクセス可能である。同様の動作が、拡大体またはハイパー楕円曲線等の高次種数曲線上で、楕円曲線を実装することができる。
【００３６】
各通信者１２、１４は、それぞれ整数を表すコンピュータ可読ビット列の形態である長期非公開鍵ｄＡ、ｄＢと、それぞれ対応する長期公開鍵ＱＡ、ＱＢとを有する。公開鍵ＱＡ、ＱＢは、楕円曲線の式を満たす基礎フィールドの中の一対の要素である。公開鍵は、点の（ｘ，ｙ）座標を表す要素を有する楕円曲線上の点を表す。各通信者１２、１４は、一方の通信者からもう一方の通信者に提供され、認証機関（ＣＡ）によって署名される証明書として、またはＣＡから直接、もう一方の通信者の長期公開鍵の真正コピーにアクセスできる。
【００３７】
ＭＱＶプロトコルとして例示される鍵合意プロトコルを使用して、通信者間で秘密鍵を共通することが望ましい。特に、鍵のある条件を考慮して、効率的な計算を提供するために、ＭＱＶプロトコルによって要求される通信者間の情報の交換を組織化できることが、現在では認識されている。
【００３８】
特に、第２の通信者の短期公開鍵および長期公開鍵がＭＱＶ鍵合意交換において同一であることを第１の通信者が知っている時に、第１の通信者は、２つの演算または線形結合の代わりに、単一のスカラー乗法演算または単一のべき乗演算を使用して、ＭＱＶ共通秘密鍵の計算を加速することができる。共通秘密鍵Ｋを決定するために必要とされる、低減した数の集中的計算のが、ＭＱＶプロトコルを加速する。
【００３９】
通信者の一時公開鍵および長期公開鍵は、非意図的または意図的に同一であってもよい。意図的に一時公開鍵を長期公開鍵と同一に設定することが好適である、状況があってもよい。例えば、受信者が一時公開鍵を送信することが好ましくないか、または実行可能ではなく、したがって、受信者の一時公開鍵が長期公開鍵と同一にされる、ｅメール等の状況があってもよい。さらに別の状況では、証明書とも呼ばれる認証された公開鍵が必要とされながらも利用可能ではない場合がある。例えば、金融機関のオンラインサーバが証明書を使用して動作してもよい一方で、オンラインバンキングクライアントは、証明書なしでサーバに安全に接続するためにインターネットブラウザを使用する。クライアントは、クライアントの一時の鍵および長期鍵が意図的に同一に設定されるため、銀行のサーバと接続するために証明書を必要としなくてもよい。
【００４０】
３パスＥＣＭＱＶプロトコルを通して共通秘密鍵を計算する方法が、概して数字２００によって図２で示されている。図２に示されたステップは、その内側でＥＣＭＱＶプロトコルの加速が得られてもよい、フレームワークを表す。ＥＣＭＱＶの加速が検討されないと仮定すると、Ａｌｉｃｅがセッションを開始して一式の命令（２１０）を実装し、その場合、最初に、１から（ｑ−１）までの間で一時非公開鍵ｋＡとして整数をランダムに選択し（２１２）、ここに、ｑは群の位数である。Ａｌｉｃｅは、ＲＡ＝ｋＡＰに従って曲線上の点として一時公開鍵ＲＡを計算し（２１４）、ここに、点Ｐは群生成器である。次いで、Ａｌｉｃｅは、長期公開鍵ＱＡおよび一時公開鍵ＲＡをＢｏｂに送信する（２１６）。
【００４１】
次いで、Ｂｏｂが一式の命令（２２０）を行う。Ｂｏｂは、１から（ｑ−１）までの間で独自の一時非公開鍵ｋＢをランダムに選択する（２２４）前に、受信した公開鍵ＲＡに組込み公開鍵検証（３００）を行う。組込み鍵検証は、数字３００によって図３で詳細に示されている。第１に、公開鍵、この場合ＲＡは、ＲＡが無限大における点ではない、すなわちＲＡ≠∞という条件に従って検証される（３０２）。この条件（３０２）が真である場合には、ＲＡのデカルト座標が有限フィールドＦｑ内で適正に表されるように、次の条件（３０４）が検証される。最後に、ＲＡがパラメータａおよびｂによって定義される楕円曲線上に位置するか否かを確かめる（３０６）ように、ＲＡの座標が楕円曲線の方程式に挿入される。全ての条件が満たされた場合、アルゴリズムが「有効」を返信する（３０８）。条件のうちのいずれの満たされない場合には、アルゴリズムが「無効」を返信する（３１０）。
【００４２】
再び図２に戻ると、Ｂｏｂが鍵ＲＡの妥当性を立証し（３００）、一時非公開鍵ｋＢをランダムに選択した（２２４）後、ＲＢ＝ｋＢＰに従って、対応する一時公開鍵ＲＢを計算し続ける（２２６）。これは、中間値
【００４３】
【数１０】
0005329676.tif 000023
を計算するために使用される（２２８）。
【００４４】
【数１１】
0005329676.tif 000024
は、ビット長を縮小し、それにより、計算効率を増加させるために、ＲＢの短縮バージョンである。共通秘密鍵Ｋは、
【００４５】
【数１２】
0005329676.tif 000025
に依存する。例示されるように、鍵Ｋは、
【００４６】
【数１３】
0005329676.tif 000026
に従って計算され（２３０）、ここに、ｈは群の余因数である。Ｋのｘ座標は、好適な鍵導出関数（ＫＤＦ）を通して２つの他の秘密鍵ｋ１およびｋ２を導出するために使用される（２３２）。これらの秘密鍵ｋ１、ｋ２は、メッセージ認証コード（ＭＡＣ）を使用して認証タグを計算するために使用される。Ｂｏｂは、
【００４７】
【化５】
0005329676.tif 000027
に従って認証タグｔＢを計算するために秘密鍵ｋ１を使用する（２３４）。列「２」は、タグが応答者に由来することを示すようにＭＡＣ入力に含まれる。次いで、Ｂｏｂは、パラメータＱＢ、ＲＢ、およびｔＢをＡｌｉｃｅに渡す（２３６）。
【００４８】
Ｂｏｂからパラメータを受信すると、Ａｌｉｃｅは別の一連の命令（２４０）を進める。Ａｌｉｃｅは、ＲＢに組込み公開鍵検証（３００）を行い、次いで、中間値
【００４９】
【数１４】
0005329676.tif 000028
を計算する（２４４）。共通秘密鍵Ｋは、この実施例では
【００５０】
【数１５】
0005329676.tif 000029
に従って、
【００５１】
【数１６】
0005329676.tif 000030
に依存する（２４６）。同じＫＤＦが、ＫＤＦ（ｘＫ）が秘密鍵ｋ１、ｋ２を生じるように、Ｋのｘ座標、すなわち、ｘＫに適用される（２３２）。Ａｌｉｃｅは、認証タグ
【００５２】
【化６】
0005329676.tif 000031
を計算し（２５０）、ｔ＝ｔＢを検証する（２５２）。タグの平等性が検証された場合、Ａｌｉｃｅは、
【００５３】
【化７】
0005329676.tif 000032
である２次認証タグを計算して（２５４）、Ｂｏｂに送信する（２５６）。列「３」は、タグがイニシエータに由来することを示すようにＭＡＣ入力に含まれる。
【００５４】
次いで、次の一式の命令（２６０）で、Ｂｏｂが対応するタグ
【００５５】
【化８】
0005329676.tif 000033
を計算し（２６２）、ｔ＝ｔＡであることを検証する（２６４）。ＡｌｉｃｅおよびＢｏｂのデバイスの両方で、条件ｔ＝ｔＡが真である場合には、両方の秘密鍵ｋ１およびｋ２が共通されている。認証タグｔＡおよびｔＢの検証の成功は、（タグの計算がｋ１の知識、したがってＫの知識も必要とするため）もう一方のエンティティが確かに共通秘密鍵Ｋを計算していること、通信が改ざんされていないこと（ＭＡＣが安全であると仮定する）、および（アイデンティティがＭＡＣされるメッセージに含まれるため）もう一方のエンティティが通信しているエンティティのアイデンティティを知っていることを、各エンティティに確信させる。上記の条件を検証した後、ＥＣＭＱＶプロトコルは、ＫＤＦから導出された、合意秘密セッション鍵ｋ２（２７０）を返信する。次いで、セッション鍵ｋ２は、ｋ２の下で対称暗号化を使用して、通信チャネル１６上で情報を交換するために使用されてもよい。
【００５６】
ＥＣＭＱＶプロトコル内の任意のステップで、検証過程が「真」を返信しなければ、プロトコルは終了される。
【００５７】
上記で説明されるＥＣＭＱＶプロトコルの最も計算上集中的側面は、より一般的には点乗法と呼ばれる、スカラー乗法演算である。ＥＣＭＱＶプロトコルの効率は、共通秘密鍵を計算するために必要とされる数のスカラー乗法を使用して測定される。図２および３で説明されたプロトコルでは、Ａｌｉｃｅがスカラー乗法を行って
【００５８】
【数１７】
0005329676.tif 000034
を計算し（２４６）、Ｂｏｂがスカラー乗法を行って
【００５９】
【数１８】
0005329676.tif 000035
を計算する（２３０）。具体的には、ＡｌｉｃｅおよびＢｏｂの両方がそれぞれ、１．５スカラー乗法を行って、上記の形式でＫを計算する。Ａｌｉｃｅの場合、ＡＬＵ（２８）が
【００６０】
【数１９】
0005329676.tif 000036
を計算する（２４６）。括弧の項
【００６１】
【数２０】
0005329676.tif 000037
内で、乗法
【００６２】
【数２１】
0005329676.tif 000038
が行われ、ここに、
【００６３】
【数２２】
0005329676.tif 000039
は整数であり、ＱＢは楕円曲線上の点である。
【００６４】
【数２３】
0005329676.tif 000040
が切り捨てられ、より短いビット長を有するため、演算
【００６５】
【数２４】
0005329676.tif 000041
には、スカラー乗法の半分、または０．５のスカラー乗法を費やす。次のスカラー乗法は、整数ｈｓＡと楕円曲線点
【００６６】
【数２５】
0005329676.tif 000042
との間で積を計算する時に発生し、それには、１つの完全スカラー乗法を費やす。したがって、Ｋの計算には、合計（１＋０．５）＝１．５のスカラー乗法を費やす。
【００６７】
スカラー乗法の数を削減し、それにより、鍵合意プロトコルを加速するために、ＲＢ＝ＱＢおよび／またはＲＡ＝ＱＡであるように、通信者の一対の公開鍵が等しい時に、スカラー乗法の代償がさらに削減されてもよいという認識に基づいて、図３のフレームワークが、図４に示されるように適合される。Ｂｏｂにとって、加速計算はＲＡ＝ＱＡである時に発生し、それは、共通秘密鍵計算が簡略化してＫ＝ｕＱＡになることを可能にし、ここに、単純化因数ｕは、
【００６８】
【数２６】
0005329676.tif 000043
に依存する。特定の実施例では、
【００６９】
【数２７】
0005329676.tif 000044
である。同様に、Ａｌｉｃｅにとって、加速計算はＲＢ＝ＱＢである時に発生し、それは、共通秘密鍵計算が簡略化してＫ＝ｖＱＢになることを可能にし、ここに、単純化因数ｖは、
【００７０】
【数２８】
0005329676.tif 000045
に依存する。この実施例では、
【００７１】
【数２９】
0005329676.tif 000046
である。共通秘密鍵を計算するために、１．０のスカラー乗法代償が必要とされる。したがって、図４で説明されたプロトコルは、図３で説明されたものよりも３３％ほども速く実装することができる。
【００７２】
図４を参照すると、一対の同一公開鍵が通信者によって使用されることが識別される時に、スカラー乗法の数を削減することによってＥＣＭＱＶプロトコルを加速する実施形態が示されている。この実施形態では、ＡｌｉｃｅおよびＢｏｂは、意図的に、それぞれの一時公開鍵をそれらの長期公開鍵と同一に設定する。加速アルゴリズムは、一時非公開鍵ｋＡをランダムに選択すること（２１２）、長期鍵ＱＡと等しくなるように、一時公開鍵ＲＡを意図的に選択すること（２１５）、ならびにＱＡおよびＲＡをＢｏｂに送信すること（２１６）を含む、命令のブロック（２１１）をＡｌｉｃｅが行うことから始まる。
【００７３】
一対の公開鍵を受信すると、Ｂｏｂは鍵が同一であるか否かを決定する。図４に示されるように、Ｂｏｂは、最初にＱＡおよびＲＡを比較する（６１２）ことによって、一連の命令（６１０）を行い始める。ＱＡがＲＡに等しくない場合、Ｂｏｂは一式のステップ２２１を続ける。図５を参照すると、セット２２１がより詳細に示されている。セット２２１はセット２２０で以前に説明された一式のステップと同様であるが、セット２２１は、一時非公開鍵ｋＢを使用してＲＢを計算しない。代わりに、セット２２１では、Ｂｏｂは、ステップ２２７の通り、ＱＢと等しくなるようにＲＢを意図的に選択する。
【００７４】
しかしながら、図４の決定過程でＱＡおよびＲＡが等しいと識別される（６１２）場合には、Ｂｏｂは加速スカラー乗法形式を採用する（７０１）。図６を参照すると、第１に、Ｂｏｂは、ＲＡの組込み公開鍵検証を行い（３００）、１から（ｑ−１）までの間でｋＢをランダムに選択し（７１２）、次いで、ＱＢと等しくなるようにＲＢを意図的に選択する（７１５）。中間成分ｓＢが計算され（７１６）、その後に単純化因数
【００７５】
【数３０】
0005329676.tif 000047
が続く（７１８）。これは、単純化スカラー乗法形式を使用して共通秘密鍵Ｋ＝ｕＱＡを計算するために使用される（７２０）。次いで、ＫＤＦ（ｘＫ）を使用して、２つの鍵ｋ１およびｋ２が導出される（７２２）。次いで、Ｂｏｂは、ＭＡＣアルゴリズムを使用して認証タグｔＢを計算する（７２４）。次いで、ＱＢ、ＲＢ、およびｔＢをＡｌｉｃｅに送信する（７２６）。
【００７６】
Ｂｏｂは、Ａｌｉｃｅが意図的に一時公開鍵ＲＡを長期公開鍵ＱＡと等しく設定してもよいことを確信していない場合に、公開鍵比較（６１２）を実行してもよいことが理解される。例えば、事前に確立された何らかの合意を通して、Ａｌｉｃｅの一時および長期公開鍵が同一であるとＢｏｂが決定した場合には、Ｂｏｂは、公開鍵比較（６１２）を実装しないことを選択し、それにより、計算負荷を低減してもよい。したがって、Ａｌｉｃｅの一対の公開鍵を受信すると、Ｂｏｂは、加速スカラー乗法形式を直接採用してもよい（７０１）。つまり、ステップ２１６は、公開鍵が同一であることが事前に理解されている場合、ステップ７０１に直接進んでもよい。Ｂｏｂが意図的に一時および長期公開鍵を同一に設定していることをＡｌｉｃｅが知っていると考慮して、Ａｌｉｃｅも比較（６１６）を行わないことを選択してもよいことが理解される。同様に、ステップ２３６から７２６で、アルゴリズムは、ステップ８００に直接進んでもよい。しかしながら、図４で参照される具体的実施例では、決定はＡｌｉｃｅおよびＢｏｂの両方の比較によって行われる。
【００７７】
再び図４に戻って、Ｂｏｂから一対の公開鍵を受信すると、Ａｌｉｃｅは、最初にＱＢおよびＲＢを比較する（６１６）ことによって、一連の命令（６１４）を行い始める。ＱＢがＲＢに等しくない場合、Ａｌｉｃｅは、図２で詳細に示されるような、元の一式のステップ２４０を続ける。しかしながら、ＱＢおよびＲＢが等しくない場合には、Ａｌｉｃｅは加速スカラー乗法形式を採用する（８００）。図７を参照して、第１に、Ａｌｉｃｅは、ＲＢの組込み公開鍵検証（３００）を行う。中間成分ｓＡ（８１２）が計算され、その後に単純化因数
【００７８】
【数３１】
0005329676.tif 000048
（８１４）が続く。これは、単純化スカラー乗法形式を使用して共通秘密鍵Ｋ＝ｖＱＢを計算するために使用される（８１６）。次いで、ＫＤＦ（ｘＫ）を使用して、２つの鍵ｋ１およびｋ２が導出される（８１８）。次いで、Ａｌｉｃｅは、ＭＡＣアルゴリズムを使用して認証タグｔを計算し（８２０）、ｔ＝ｔＢであることを検証する（８２２）。Ａｌｉｃｅは、ｔＡを計算し（８２４）、それをＢｏｂに送信する（８２６）。
【００７９】
再び図４を参照すると、Ａｌｉｃｅがアルゴリズム（２４０）または（８００）を完了した後に、Ｂｏｂは一式のステップ（２６０）を行い、その場合、ステップ２６２で認証タグｔを計算し、ｔ＝ｔＡであることを検証する（２６４）。全てのタグが加速ＥＣＭＱＶ過程で検証されている場合には、ＡｌｉｃｅおよびＢｏｂの両方にとって、合意セッション鍵はｋ２である（２７０）。
【００８０】
図４で説明される実施形態に関して、一時公開鍵（すなわち、ＲＡおよび／またはＲＢ）が、対応する長期公開鍵と同一となるように意図的に選択されるか否かは随意的である。同一となるように意図的に選択されない場合には、例えば、Ａｌｉｃｅの一時公開鍵は、ＲＡ＝ｋＡＰによって決定されてもよい。同様に、Ｂｏｂは、一対の同一の公開鍵を意図的に選択しないことを選んでもよく、したがって、ＲＢ＝ｋＢＰを計算してもよい。しかしながら、通信者が、長期公開鍵と同一となるように一時公開鍵を意図的に選択すると、次いで、一時非公開鍵から一時公開鍵を取得するための計算は必要とされないことが留意される。したがって、通信者において同一の公開鍵を意図的に選択することにより、一時公開鍵を決定する際の計算負荷を低減する。
【００８１】
ＲＢ＝ＱＢおよび／またはＲＡ＝ＱＡの条件は、実行時間中に検出され、長期公開鍵ＱおよびＱの事前計算されたスカラー倍数を含有するｆａｔ証明書に事前に記憶されてもよい。この事前識別された条件は、ｕＱＡを提供するように組み合わせられる、公開鍵ＱＡの倍数の事前計算された表を作成するために使用されてもよい。これは、共通秘密鍵Ｋの計算をさらに加速する。
【００８２】
図４の考慮から理解されてもよいように、公開鍵が同じであるか否かを決定する能力は、通信者間の通信における多用途性を提供する。例えば、Ａｌｉｃｅは、２つの異なる公開鍵を使用してもよいが、Ｂｏｂは、より便利であれば同じ公開鍵を使用してもよい。例えば、Ｂｏｂが限定された計算能力を有するコンピュータデバイスである場合、一時公開鍵と関連付けられるスカラー乗法を行わないことを選択してもよい。
【００８３】
Ａｌｉｃｅは、Ｂｏｂからのデータの受信時にこれを確認し、共通鍵の計算を促進することができる。
【００８４】
同様に、Ａｌｉｃｅは、同一の公開鍵を使用することを選択して、Ｂｏｂが共通鍵の計算を促進することを可能にしてもよいが、Ｂｏｂは、Ａｌｉｃｅと通信するための異なる公開鍵を使用することを選択してもよい。
【００８５】
最後に、ＡｌｉｃｅおよびＢｏｂの両方はそれぞれ、それぞれの同一の公開鍵を使用することを選択してもよく、それぞれが共通鍵の計算を促進する。
【００８６】
中間値ｓＡ、ｓＢを計算する際に、一時非公開鍵ｋＡ、ｋＢを計算する代わりに、ＡｌｉｃｅおよびＢｏｂは、長期非公開鍵ｄＡ、ｄＢをそれぞれ使用することが可能である。しかしながら、これは、同一の鍵が連続セッションで使用されることをもたらし、これは概して望ましくないと見なされる。
【００８７】
方法の別の好ましい実施形態では、ＭＱＶ過程をさらに加速するためにテーブルが使用されてもよい。複数対の同一の公開鍵を識別することによって得られる費用節約は、同時多点乗法を実装するために説明される方法に適用されてもよい。図８ａに示されるように、計算を加速するために従来使用されている方法は、シャミルのトリックとも呼ばれる、多点乗法を採用するものである。第１に、共通秘密鍵の元の方程式（すなわち、
【００８８】
【数３２】
0005329676.tif 000049
は、一般線形結合形態ｍＰ＋ｌＱに合致するように再編成されなければならない。ｍＰ＋ｌＱの表現において、ｍ＝ｈｓＡ、Ｐ＝ＲＢ、
【００８９】
【数３３】
0005329676.tif 000050
、およびＱ＝ＱＢであるように、括弧が排除され、
【００９０】
【数３４】
0005329676.tif 000051
を生じる。ＲＢおよびＱＢが両方とも点であると、鍵Ｋの式は、２つのスカラー倍数の加算である、一般形態ｍＰ＋ｌＱである。
【００９１】
図８ａでは、所定数のビットのウィンドウ幅ｗが最初に確立される（９０２）。次いで、ＲＢのαの小さい倍数のテーブル（９２０）が確立され（９０４）、ＱＢのβの小さい倍数のテーブル（９２２）が確立される（９０６）。テーブル全体は、可能なビットの組み合わせ（例えば、α＝１００１２）の縦列、および対応するスカラー倍数（例えば、１００１２ＲＢ）の縦列から成る。次いで、ウィンドウ幅ｗのウィンドウを使用して、ｈｓＡおよび
【００９２】
【数３５】
0005329676.tif 000052
が調査される（９０８）。各ウィンドウに対応するＲＢおよびＱＢのスカラー倍数は、各テーブルから取り出される（９１０）。２つのウィンドウからのテーブル入力の和は、累算器に加えられる（９１２）。次いで、累算器は、ウィンドウの幅ｗに従ってｗ倍に倍加され（９１４）、次いで、次のウィンドウが調査される（９１６）。スカラーは繰り返し調査され、テーブル入力は累算器に加えられ、累算器は、共通秘密Ｋが計算される（９１８）まで、上記で説明されるように各反復についてｗ倍に倍加される（９２４）。この同時多点乗法の形式（すなわち、
【００９３】
【数３６】
0005329676.tif 000053
）は、図３に示された計算と比べて、０．２５のスカラー乗法の計算費用の節約を提供し、それにより、合計１．２５のスカラー乗法を必要とする。
【００９４】
上記の同時多点乗法方法は、通信者の一対の公開鍵が同一である時にさらに加速されてもよい。異なる公開鍵が使用される、図８ａに示された計算では、同時乗法を行うために、２つのテーブル（９２０、９２２）が必要とされる。図８ｂを参照して、一時公開鍵および長期公開鍵が同一である、例えば、ＲＢ＝ＱＢである時に、１つだけのテーブル（９４２）がウィンドウ方法を行うために通信者によって必要とされる。したがって、ｗビットのウィンドウ幅を確立し（９２６）、次いで、ＲＢのスカラー倍数のテーブルを確立する（９２８）ことによって、加速同時スカラー乗法（７２０、８１６）が始まる。ウィンドウ幅ｗのウィンドウを使用して、スカラーｈｓＡおよび
【００９５】
【数３７】
0005329676.tif 000054
が調査される（９３０）。各ウィンドウに対応するＲＢのスカラー倍数が取り出され（９３２）、累算器の中へ記憶される（９３４）。次いで、累算器は、ウィンドウの幅ｗに従ってｗ倍に倍加され（９３６）、次いで、次のウィンドウが調査される（９３８）。スカラーは繰り返し調査され、テーブル入力は累算器に加えられ、累算器は、共通秘密Ｋが計算される（９４０）まで、上記で説明されるように各反復についてｗ倍に倍加される（９４４）。
【００９６】
同一公開鍵の使用に起因し、同時点乗法に使用されるテーブルに適用される、費用節約方法も、共同構築されたテーブルに適用されてもよいことを理解されたい。２つの別個のテーブルを構築する必要性を排除すること、または複数対の公開鍵ＲＡ、ＱＡ、およびＲＢ、ＱＢの合同テーブルを構築することにより、結果として、実行時間を削減し、２０％を大幅に超える費用節約を達成してもよい。
【００９７】
また、複数対の同一公開鍵を使用する鍵合意プロトコルの加速も、乗法群を使用する実装に適用可能であることも理解されたい。上記で説明される実装は、群演算が加算表記で言及される、楕円曲線群を利用する。一式の非ゼロ整数のモジュールｐである、群Ｆｐ等の他の群は、乗法表記を使用する。楕円曲線設定での加算表記は、乗法群設定での乗法表記に置鍵換えられる。
【００９８】
したがって、背景として図９を参照すると、乗法群設定でＭＱＶを使用して、概して共通秘密鍵Ｋを計算するための方法が数字１０００によって示されている。Ａｌｉｃｅによる一式の動作（１０１０）では、一時非公開鍵ｋＡが間隔１から（ｑ−１）までにおいてランダムに選択され（１０１２）、ここに、ｑは群の位数である。Ａｌｉｃｅは、対応する一時公開鍵
【００９９】
【数３８】
0005329676.tif 000055
を計算し（１０１４）、ここに、ｇは群生成器であり、ＲＡおよび長期公開鍵ＱＡをＢｏｂに送信する（１０１６）。Ｂｏｂによる同様の一式の動作（１０２０）では、一時非公開鍵ｋＢが、間隔１から（ｑ−１）までにおいてランダムに選択される（１０２２）。Ｂｏｂは、対応する一時公開鍵
【０１００】
【数３９】
0005329676.tif 000056
を計算し（１０２４）次いで、ＲＢおよび長期公開鍵ＱＢをＡｌｉｃｅに送信する（１０２６）。次いで、Ａｌｉｃｅは、
【０１０１】
【数４０】
0005329676.tif 000057
を計算する（１０３２）ために、一式の動作（１０３０）でこれらの鍵を使用し、その後に、共通秘密鍵
【０１０２】
【数４１】
0005329676.tif 000058
のべき乗式が続き（１０３４）、ここに、ｈは群の余因数である。数字１０４０では、Ｂｏｂが、共通秘密鍵
【０１０３】
【数４２】
0005329676.tif 000059
のべき乗式（１０４４）を計算するために使用される、中間値
【０１０４】
【数４３】
0005329676.tif 000060
を計算する（１０４２）。
【０１０５】
図１０を参照すると、乗法群に対する図９の実装を加速するための実施形態が示されている。上記で説明される加速ＥＣＭＱＶと同様に、一対の公開鍵が同じ値を有する時に集中的計算の数が削減される。数字１０１２では、Ａｌｉｃｅが、間隔１から（ｑ−１）までにおいて一時非公開鍵ｋＡをランダムに選択する。Ａｌｉｃｅは、長期公開鍵ＱＡと等しくなるように一時公開鍵ＲＡを意図的に選択し（１０１５）、ＲＡおよびＱＡをＢｏｂに送信する（１０１６）。同様に、数字１０２２では、Ｂｏｂが、間隔１から（ｑ−１）までにおいて一時非公開鍵ｋＢをランダムに選択する。Ｂｏｂは、長期公開鍵ＱＢと等しくなるように一時公開鍵ＲＢを意図的に選択し（１０２５）、ＲＢおよびＱＢをＡｌｉｃｅに送信する（１０２６）。ステップ１１１０では、Ａｌｉｃｅが、中間値
【０１０６】
【数４４】
0005329676.tif 000061
を計算し（１１１２）、次いで、ＲＢおよびＱＢを比較する（１１１４）。Ｂｏｂの一対の公開鍵が、ＲＢ＝ＱＢであるように同一である場合には、Ａｌｉｃｅが、単純化指数
【０１０７】
【数４５】
0005329676.tif 000062
、または、
【０１０８】
【数４６】
0005329676.tif 000063
を計算（すなわちｙは
【０１０９】
【数４７】
0005329676.tif 000064
に依存している）し、次いで、指数Ｋ＝ＲＢｙ（１１２０）を計算することによって、共通秘密鍵の加速べき乗式を計算する。そうでなければ、ＲＢ≠ＱＢである場合には、Ａｌｉｃｅが、共通秘密鍵
【０１１０】
【数４８】
0005329676.tif 000065
の非加速べき乗式を計算する（１１１６）。同様に、数字１１２２では、Ｂｏｂが中間値
【０１１１】
【数４９】
0005329676.tif 000066
を計算し（１１２４）、次いで、ＲＡおよびＱＡを比較する（１１２６）。Ａｌｉｃｅの一対の公開鍵が、ＲＡ＝ＱＡであるように同一である場合には、Ｂｏｂが、単純化指数
【０１１２】
【数５０】
0005329676.tif 000067
（１１３０）または
【０１１３】
【数５１】
0005329676.tif 000068
を計算し、次いで、指数Ｋ＝ＲＡｚ（１１３２）を計算することによって、共通秘密鍵の加速べき乗式を計算する。そうでなければ、ＲＡ≠ＱＡである場合には、Ｂｏｂが共通秘密鍵
【０１１４】
【数５２】
0005329676.tif 000069
の非加速べき乗式を計算する（１１２８）。
【０１１５】
図１０に示された実施形態では、もう一方が同一の公開鍵を使用するかどうか、ＡｌｉｃｅおよびＢｏｂが確かではない場合に、比較過程（１１１４、１１２６）が必要とされてもよい。複数対の同一公開鍵が採用されてもよいことをＡｌｉｃｅおよびＢｏｂが確信している場合には、比較過程（１１１４、１１２６）が回避されてもよく、加速ＭＱＶプロトコルが直接適用されてもよい。
【０１１６】
加速ＭＱＶ方法の別の実施形態は、上記で論議される同時多点乗法に類似している同時べき乗を使用する。鍵を決定するために使用される式
【０１１７】
【数５３】
0005329676.tif 000070
を
【０１１８】
【数５４】
0005329676.tif 000071
として再編成することができる。この再編成は、１一式の二乗のみを使用する同時多重べき乗として知られている技法を使用することによって、鍵が計算されることを可能にする。
【０１１９】
図１１ａを参照すると、同時多重べき乗の方法が非同等値の２つの公開鍵について示されている。所定数のビットのウィンドウ幅ｗが、最初に確立される（１２０２）。ＲＢの小さい指数αのテーブル（１２２０）が確立され（１２０４）、ＱＢの小さい指数βのテーブル（１２２２）が確立される（１２０６）。テーブルは、可能なビットの組み合わせ（例えば、α＝１００１２）の縦列、および対応するべき乗に起因する値（例えば、
【０１２０】
【数５５】
0005329676.tif 000072
）の縦列を備える。次いで、ウィンドウ幅ｗのウィンドウを使用して、ｈｓＡおよび
【０１２１】
【数５５−１】
0005329676.tif 000073
が調査される（１２０８）。各ウィンドウに対応する指数による、ＲＢおよびＱＢのスカラーべき乗の結果は、各テーブルから取り出される（１２１０）。２つのウィンドウからのテーブル入力の積は、累算器に加えられる（１２１２）。次いで、累算器の中の値は、ウィンドウの幅ｗに従ってｗ回だけ二乗され（１２１４）、その後、次のウィンドウが調査される（１２１６）。スカラーは繰り返し調査され、テーブル入力は乗じられて累算器に記憶され、累算器は、共通秘密Ｋが計算される（１２１８）まで、上記で説明されるように各反復についてｗ回だけ二乗される（１２２４）。
【０１２２】
図１１ｂを参照すると、加速ＭＱＶ方法の好ましい実施形態は、一対の公開鍵が同一である場合にべき乗テーブル（１２２２）のうちの１つを排除する。複数対の同一公開鍵の状況では、図１０を簡潔に参照すると、ステップ１１２０および１１３２が、本明細書で説明される、対応する加速アルゴリズムを使用してもよい。図１１ｂでは、ｗビットのウィンドウ幅を確立する（１２２６）ことによって、加速同時べき乗が始まり、その後に続いて、小さい指数によるＲＢのべき乗の結果のテーブルを確立する（１２２８、１２４２）。ウィンドウ幅ｗのウィンドウを使用して、ｈｓＡおよび
【０１２３】
【数５６】
0005329676.tif 000074
が調査される（１２３０）。各ウィンドウに対応するＲＢのべき乗が取り出され（１２３２）、累算器に記憶される（１２３４）。次いで、累算器は、ウィンドウの幅ｗに従ってｗ回だけ二乗され（１２３６）、値で、次のウィンドウが調査される（１２３８）。スカラーは繰り返し調査され、テーブル入力は累算器に加えられ、累算器は、共通秘密Ｋが計算される（１２４０）まで、上記で説明されるように各反復についてｗ回だけ二乗される（１２４４）。
【０１２４】
例えば、通信者が並行してアルゴリズムの複数セクションを行うために、計算のタイミングを最適化することを含む、加速ＭＱＶアルゴリズムの異なるアーキテクチャが形成されてもよいことを理解されたい。図１２を参照すると、並列計算の１つの代替実施形態が、乗法群上の加速ＭＱＶの場合について示されている。ＡｌｉｃｅおよびＢｏｂの両方が、並行して一式の初期ステップ（１３１０、１３２０）を実行する。Ａｌｉｃｅは、数字１３１１で、一時非公開鍵ｋＡをランダムに選択し、長期公開鍵ＱＡと等しくなるように一時公開鍵ＲＡを選択し、ＲＡおよびＱＡをＢｏｂに送信する。同時に、Ａｌｉｃｅがステップ１３１１を行うにつれて、ｋＢが生成され、ＲＢがＱＢと等しくなるように意図的に選択され、次いで、ＲＢおよびＱＢがＡｌｉｃｅに送信されるように、Ｂｏｂがステップ１３２１を行う。
【０１２５】
並行して、ＢｏｂおよびＡｌｉｃｅの両方は、もう一方の一対の同一公開鍵を取り出す。次いで、Ａｌｉｃｅは、同様にＱＡ＝ＲＡであるかどうかを決定する（１３４０）Ｂｏｂと並行して、ＲＢ＝ＱＢであるかどうかを決定する（１３３０）。Ａｌｉｃｅにとって、同等性を決定した（１３３０）後、ＲＢ≠ＱＢである場合には、Ａｌｉｃｅは、最初に中間値ｓＡを計算し、次いで、共通秘密鍵
【０１２６】
【数５７】
0005329676.tif 000075
を計算することによって、非加速べき乗式を計算する（１３５０）。しかしながら、ＲＢ＝ＱＢである場合、Ａｌｉｃｅは、最初に中間値ｓＡを計算し、次いで、
【０１２７】
【数５８】
0005329676.tif 000076
を計算し、最終的にＫ＝ＲＢｙを計算することによって、加速べき乗式を計算する（１３７０）。Ａｌｉｃｅと並行して、Ｂｏｂが同等性を決定した（１３４０）後、ＲＡ≠ＱＡである場合には、Ｂｏｂは、最初に中間値ｓＢを計算し、次いで、共通秘密鍵
【０１２８】
【数５９】
0005329676.tif 000077
を計算することによって、非加速べき乗式を計算する（１３６０）。しかしながら、ＱＡ＝ＲＡである場合、Ｂｏｂは、最初に中間値ｓＢを計算し、次いで、単純化指数
【０１２９】
【数６０】
0005329676.tif 000078
を計算し、最終的にＫ＝ＲＡｚを計算することによって、加速式を計算する（１３８０）。さらに、並列計算編成はまた、楕円曲線群上の加速ＭＱＶアルゴリズムにも該当することを理解されたい。
【０１３０】
複数対の同一鍵を使用する加速アルゴリズムが使用されていることをＡｌｉｃｅおよびＢｏｂが知っている場合に、ステップ１３３０および１３４０における比較過程は必要ではなくてもよいことが留意される。言い換えれば、Ａｌｉｃｅは、事前にすでに知っていれば、Ｂｏｂの鍵が同一であるかどうかを検証する（１３３０）必要がない。したがって、上記の場合、ステップ１３２０から、アルゴリズムがステップ１３７０に直接進んでもよい。同様に、ステップ１３１０から、アルゴリズムがステップ１３８０に直接進んでもよい。
【０１３１】
加速ＭＱＶプロトコルへの代替的アプローチで、一時および長期公開鍵が同一であるため、通信者は、単一の公開鍵を送信することしか要求されない。これは、通信者間で転送されるデータの量を低減し、より大きい鍵が使用されることを可能にする。
【０１３２】
図１３を参照すると、単一の公開鍵のみを送信する乗法群上の加速ＭＱＶプロトコルの実施形態が図示されている。ＡｌｉｃｅおよびＢｏｂの両方は、同一の公開鍵を使用して加速アルゴリズムが実装されていることを知っていると理解される。Ａｌｉｃｅは、ｋＡをランダムに選択し（１４０２）、意図的にＲＡ＝ＱＡを選択する（１４０５）ことによって始める。次いで、Ａｌｉｃｅは、ＱＡをＢｏｂに送信する（１４１１）。これは、２つの公開鍵のデータサイズと比較して、ネットワーク上で送信されるデータの量を低減する。
【０１３３】
図１３を続けると、ステップ１４１１からのデータがＡｌｉｃｅによって送信された後、Ｂｏｂが続けてｋＢをランダムに選択し（１４１２）、意図的にＲＢ＝ＱＢを選択する（１４１５）。同様に、次いで、Ｂｏｂは、ＱＢをＡｌｉｃｅに送信する（１４２０）。次いで、Ａｌｉｃｅは、加速ＭＱＶアルゴリズムを使用し、中間成分ｓＡ、単純化指数
【０１３４】
【数６１】
0005329676.tif 000079
、最終的に共通秘密鍵Ｋ＝ＲＢｙを計算する（１４２６）。ＲＢ＝ＱＢであることが理解される。同様に、Ｂｏｂは、加速ＭＱＶアルゴリズムを計算するために、ステップ１４１１からの受信したデータを使用する。Ｂｏｂは、中間成分ｓＢ、単純化指数
【０１３５】
【数６２】
0005329676.tif 000080
、最終的に共通秘密鍵Ｋ＝ＲＡｚを計算する（１４３２）。ＲＡ＝ＱＡであることが留意される。本明細書で説明される、この代替的アプローチはまた、楕円曲線群上で適用されてもよいことを理解されたい。
【０１３６】
データサイズ節約はまた、加速ＭＱＶアルゴリズムの並列アーキテクチャで適用されてもよい。加速ＭＱＶアルゴリズムのさらに別の実施形態では、図１４を参照すると、並列アーキテクチャが図示されている。以前に説明された実施形態と同様に、ＡｌｉｃｅおよびＢｏｂの両方は、同一の公開鍵を使用して加速アルゴリズムが実装されていることを知っていると理解される。Ａｌｉｃｅは、ｋＡを選択し、意図的にＲＡ＝ＱＡを選択する、一式のステップ（１５０３）を行う。並行して、Ｂｏｂは、ｋＢを選択し、意図的にＲＢ＝ＱＢを選択する、一式のステップ（１５０５）を行う。次いで、ＡｌｉｃｅはＱＡをＢｏｂに送信し（１５１２）、ＢｏｂはＱＢをＡｌｉｃｅに送信する（１５１６）。データを受信すると、Ａｌｉｃｅは、加速アルゴリズムを使用して共通秘密鍵Ｋを計算する（１５２４）。並行して、Ｂｏｂは、加速アルゴリズムを使用して共通秘密鍵Ｋを計算する（１５２８）。加速ＭＱＶアルゴリズムにおける並列アーキテクチャの上記の単一公開鍵転送はまた、楕円曲線群にも該当することが理解されるであろう。
【０１３７】
加速ＭＱＶプロトコルへの代替的アプローチで、通信者の同一の一対の公開鍵の検証は、一時公開鍵を生成した同じＡＬＵで行うことができる。例えば、Ａｌｉｃｅは、ＲＡを計算した後、次いで、続いてＲＡ＝ＱＡであるかどうかを検証する。このアプローチの有益性は、一対の公開鍵が同一である場合に、２つの鍵の代わりに１つだけの公開鍵を通信者に送信するという要件を含み、それは結果として、ネットワークの必要帯域幅を縮小する。
【０１３８】
図１５を参照すると、１つだけの公開鍵を送信する、乗法群上の加速ＭＱＶプロトコルの実施形態が図示されている。この実施形態では、各通信者は、長期公開鍵と同一になるように一時公開鍵を意図的に選択するというオプションを有する。Ａｌｉｃｅは、ｋＡをランダムに選択し（１４０２）、ＲＡ＝ＱＡに従って、または
【０１３９】
【数６３】
0005329676.tif 000081
を計算することにより、ＲＡを決定する（１４０４）ことによって始める。次いで、Ａｌｉｃｅは、ＱＡ＝ＲＡであるかどうかを決定する（１４０６）。ＱＡ≠ＲＡである場合には、Ａｌｉｃｅは、ＲＡ、ＱＡ、およびＥｑｕａｌ＝偽をＢｏｂに送信する（１４０８）。そうでなければ、ＱＡ＝ＲＡである場合には、Ａｌｉｃｅは、ＱＡおよびＥｑｕａｌ＝真をＢｏｂに送信する（１４１０）。可変数Ｅｑｕａｌは、一対の公開鍵が同一であるか同一でないかを示す、例えば、１ビットといった、小さいビットサイズのブールパラメータであってもよい。一対の公開鍵が同一である（すなわち、Ｅｑｕａｌ＝真）ときの状況では、長期公開鍵等の１つだけの公開鍵、および小ビットサイズパラメータＥｑｕａｌが、通信者に送信される。これは、２つの公開鍵のデータサイズと比較して、ネットワーク上で送信されるデータの量を低減する。
【０１４０】
図１５を続けると、ステップ１４０８またはステップ１４１０からのデータがＡｌｉｃｅによって送信された後、Ｂｏｂは、ｋＢをランダムに選択し（１４１２）、ＲＢ＝ＱＢに従って、または
【０１４１】
【数６４】
0005329676.tif 000082
を計算することにより、ＲＡを決定する（１４１４）ことによって始める。同様に、次いで、Ｂｏｂは、ＱＢ＝ＲＢであるかどうかを決定する（１４１６）。ＱＢ≠ＲＢである場合には、Ｂｏｂは、ＲＢ、ＱＢ、およびＥｑｕａｌ＝偽をＡｌｉｃｅに送信する（１４１８）。そうでなければ、ＱＢ＝ＲＢである場合には、Ｂｏｂは、ＱＢおよびＥｑｕａｌ＝真をＡｌｉｃｅに送信する（１４２０）。次いで、Ａｌｉｃｅは、Ｅｑｕａｌ＝真であるかどうかを決定する（１４２２）ためにステップ１４１８またはステップ１４２０からの受信したデータを使用する。Ｅｑｕａｌ＝偽である場合、Ａｌｉｃｅは、非加速ＭＱＶ方法を使用して共通鍵Ｋを計算する（１４２４）。Ｅｑｕａｌ＝真である場合、Ａｌｉｃｅは、加速ＭＱＶアルゴリズムを使用し、中間成分ｓＡ、単純化指数
【０１４２】
【数６５】
0005329676.tif 000083
、最終的にＫ＝ＲＢｙを計算する（１４２６）。同様に、Ｂｏｂは、Ｅｑｕａｌ＝真であるかどうかを決定する（１４２８）ためにステップ１４０８またはステップ１４１０からの受信したデータを使用する。Ｅｑｕａｌ＝偽である場合、Ｂｏｂは、非加速ＭＱＶ方法を使用して共通鍵Ｋを計算する（１４３０）。Ｅｑｕａｌ＝真である場合、Ａｌｉｃｅは、加速ＭＱＶアルゴリズムを使用し、ｓＢ、中間値
【０１４３】
【数６６】
0005329676.tif 000084
、最終的に共通秘密鍵Ｋ＝ＲＡｚを計算する（１４３２）。本明細書で説明される、この代替的アプローチはまた、楕円曲線群上で適用されてもよいことを理解されたい。
【０１４４】
一時公開鍵の計算、および同じ通信者による各同一鍵ペア状態の決定に起因する、データサイズ節約はまた、加速ＭＱＶアルゴリズムの並列アーキテクチャにおいて適用されてもよい。加速ＭＱＶアルゴリズムのさらに別の実施形態では、図１６を参照すると、並列アーキテクチャが図示されている。Ａｌｉｃｅは、ｋＡを選択し、ＲＡを決定する、一式のステップ（１５０２）を行う。Ａｌｉｃｅは、意図的にＲＡ＝ＱＡを設定するか、または
【０１４５】
【数６７】
0005329676.tif 000085
を計算してもよい。並行して、Ｂｏｂは、ｋＢを選択し、ＲＢを決定する、一式のステップ（１５０４）を行う。Ｂｏｂは、意図的にＲＢ＝ＱＢを設定するか、または
【０１４６】
【数６８】
0005329676.tif 000086
を計算してもよい。次いで、ＡｌｉｃｅおよびＢｏｂは同時に、それぞれの一対の公開鍵が等しいかどうかを決定する（１５０６、１５０８）。ＱＡ≠ＲＡである場合、Ａｌｉｃｅは、ＲＡ、ＱＡ、およびＥｑｕａｌ＝偽をＢｏｂに送信する（１５１０）。そうでなければ、ＱＡ＝ＲＡである場合には、Ａｌｉｃｅは、ＱＡおよびＥｑｕａｌ＝真をＢｏｂに送信する（１５１２）。同様に、並行して、ＱＢ≠ＲＢである場合には、Ｂｏｂは、ＲＢ、ＱＢ、およびＥｑｕａｌ＝偽をＡｌｉｃｅに送信する（１４１８）。そうでなければ、ＱＢ＝ＲＢである場合には、Ｂｏｂは、ＱＢおよびＥｑｕａｌ＝真をＡｌｉｃｅに送信する（１４２０）。データを受信すると、ＡｌｉｃｅおよびＢｏｂの両方は、Ｅｑｕａｌ＝真であるかどうかを並行して決定する（１５１８、１５２０）。Ａｌｉｃｅにとって、Ｅｑｕａｌ＝偽である場合には、非加速アルゴリズムを使用して共通秘密鍵Ｋを計算する（１５２２）。そうでなければ、Ｅｑｕａｌ＝真である場合は、加速アルゴリズムを使用して共通秘密鍵Ｋを計算する（１５２４）。並行して、Ｂｏｂに対するステップ１５２０から続いて、Ｅｑｕａｌ＝偽である場合は、非加速アルゴリズムを使用して共通秘密鍵Ｋを計算する（１５２６）。そうでなければ、Ｅｑｕａｌ＝真である場合は、加速アルゴリズムを使用して共通秘密鍵Ｋを計算する（１５２８）。加速ＭＱＶアルゴリズムにおける並列アーキテクチャの上記の単一公開鍵転送はまた、楕円曲線群にも該当することが理解されるであろう。
【０１４７】
上記の実施例のそれぞれは、公開鍵が一方の通信者からもう一方の通信者に送信されることを示す。長期公開鍵は、代替として、認証機関から取得され、ディレクトリから取得され、または以前の交換からのメモリ３０内に記憶されてもよい。したがって、長期公開鍵のみが使用される場合、通信者間の情報の直接転送は、ＭＡＣ、ｔＢの交換によって生じてもよい。
【０１４８】
同一公開鍵に基づく加速は、ＭＱＶアルゴリズムに限定されないことが理解される。一時公開鍵および長期公開鍵の線形結合を備える、他のアルゴリズムも好適であってもよい。
【０１４９】
そのようなプロトコルの１つの部類は、Ｈａｎｄｂｏｏｋ  ｏｆ  Ａｐｐｌｉｅｄ  Ｃｒｙｐｔｏｌｏｇｙ，Ｍｅｎｚｅｓ  ｅｔ  ａｌ．ＩＳＢＮ  ０−８４９３−８５２３−７のページ５１８で説明されているようなＭＴＩプロトコルである。図１７に示されるように、ＭＴＩ  ＡＯプロトコルは、それぞれの長期非公開／公開鍵ａ、ＺＡおよびｂ、ＺＢを有する、ＡｌｉｃｅおよびＢｏｂとともに実装されてもよく、長期公開鍵ＺＡ、ＺＢは、もう一方の通信者と交換されるか、またはもう一方の通信者に利用可能となる。Ａｌｉｃｅは、一時非公開鍵ｘを生成し、Ｂｏｂに送信される、対応する一時公開鍵αｘを計算する。
【０１５０】
Ｂｏｂは同様に、通常、一時非公開鍵ｙを生成し、Ａｌｉｃｅに一時公開鍵αｙを送信する。
【０１５１】
共通鍵Ｋは、Ａｌｉｃｅにおいて（αｙ）ａＺＢｘから、およびＢｏｂにおいて（αｘ）ｂＺＡｙから計算される。
【０１５２】
図１７に示されるように、Ｂｏｂは、ｙ＝ｂおよびαｙ＝ＺＢであるように、短期鍵として長期鍵ｂ、αｂを使用し、値を比較することができるＡｌｉｃｅにＺＢを送信することによって、またはメッセージＥｑｕａｌ＝真の形態の指示を送信することによって、あるいは長期公開鍵の交換中等の事前合意によって、Ａｌｉｃｅに通知する。
【０１５３】
Ａｌｉｃｅは、ａおよびｘの両方を知っているため、共通鍵Ｋ＝（ＺＢ）ａ＋ｘを計算してもよく、Ｂｏｂは、ｂを知っているため、（αｘＺＡ）ｂを計算する。全体的な計算負荷を低減するように、１つのべき乗がＢｏｂおよびＡｌｉｃｅの両方で行われる。
【０１５４】
本発明は、ある具体的実施形態を参照して説明されているが、本発明の精神および範囲から逸脱することなく、その種々の修正が当業者にとって明白となるであろう。
加えて、説明される種々の方法は、ソフトウェアによって選択的に起動または再構成される、汎用コンピュータで実装されるが、当業者であれば、そのような実施形態がハードウェアで実行されてもよいことも認識するであろう。
【図１】
0005329676.tif 000095
【図２】
0005329676.tif 000096
【図３】
0005329676.tif 000097
【図４】
0005329676.tif 000098
【図５】
0005329676.tif 000099
【図６】
0005329676.tif 000100
【図７】
0005329676.tif 000101
【図８】
0005329676.tif 000102
【図９】
0005329676.tif 000103
【図１０】
0005329676.tif 000104
【図１１】
0005329676.tif 000105
【図１２】
0005329676.tif 000106
【図１３】
0005329676.tif 000107
【図１４】
0005329676.tif 000108
【図１５】
0005329676.tif 000109
【図１６】
0005329676.tif 000110
【図１７】
0005329676.tif 000111