(57)【特許請求の範囲】
【請求項１】
協働する複数のキー回復エージェントを使用するコンピュータまたはワークステーションを含んで構成されるシステムにおいて暗号キーを回復する方法であって、
前記暗号キーおよび公開情報を反転関数に入力して暗号キーを反転させ、反転された前記暗号キーから前記暗号キーを再生可能な、複数の共用キー回復値を生成するステップと、
ソルト値を使用して前記キー回復エージェントの公開回復キーにより前記共用キー回復値をそれぞれ暗号化することで、前記複数の暗号化された共用キー回復値を生成し、かつ前記暗号化された前記共用キー回復値から前記共用キー回復値を生成させるため、前記キー回復エージェントの情報を含む回復情報を生成し、前記暗号キーにより暗号化された第１のメッセージに伴うセッション・ヘッダに書き込んでメッセージ・パケットを生成するステップと、
通信チャネルを介して前記メッセージ・パケットを送信するステップとを含み、
前記メッセージ・パケットを受信した他のキー回復エージェントが前記セッション・ヘッダと共に前記第１のメッセージを読み取り、前記暗号化された共用キー回復値と公開情報とから共用キー回復値を回復させて前記暗号キーを回復する
方法。
【請求項２】
一対の通信当事者の設置するそれぞれのシステムが前記暗号キーを使用して相互通信する請求項１に記載の方法。
【請求項３】
前記暗号キーが前記当事者の一方のシステムによって確立され、前記当事者の他方のシステムに伝達される請求項２に記載の方法。
【請求項４】
前記暗号キーが協働する前記当事者の両方のシステムによって確立される請求項２に記載の方法。
【請求項５】
前記暗号キーが前記共用キー回復値によって完全に決定される請求項１に記載の方法。
【請求項６】
前記複数の共用キー回復値を生成するステップが、
前記暗号キーから反転関数を使用してどのキー回復エージェントとも共用されない非共用キー回復値を生成するステップをさらに含み、前記キーが前記共用キー回復値および前記非共用キー回復値によって完全に決定される請求項１に記載の方法。
【請求項７】
各前記キー回復エージェントが、公開回復キーおよび対応する秘密回復キーを有する請求項１に記載の方法。
【請求項８】
前記複数の共用キー回復値を生成するステップが、
前記暗号キーの第１の反転可能関数の第１の入力値を生成するステップと、
前記第１の入力値の少なくとも一部を第２の入力値に連結して、延長入力値を生成するステップと、
前記延長入力値の第２の反転可能関数の出力値を生成するステップと、
前記出力値を副部分に分割して、前記共用キー回復値を生成するステップとを含む請求項１に記載の方法。
【請求項９】
前記第２の入力値が前記暗号キーの関数として生成される請求項８に記載の方法。
【請求項１０】
前記第１の入力値の一部のみが前記第２の入力値に連結されて、前記延長入力値を生成し、前記第１の入力値の残りの部分が、どのキー回復エージェントにも使用可能にされない非共用キー回復値を生成するために使用される請求項８に記載の方法。
【請求項１１】
前記第２の入力値が前記入力値の前記残りの部分の関数として生成される請求項１０に記載の方法。
【請求項１２】
前記第１の反転可能関数が疑似ランダム関数である請求項８に記載の方法。
【請求項１３】
前記第１の反転可能関数が、前記第１の入力値の各ビットが前記暗号キーの各ビットに依存するような関数である請求項８に記載の方法。
【請求項１４】
前記第２の反転可能関数が疑似ランダム関数である請求項８に記載の方法。
【請求項１５】
前記第２の反転可能関数が、前記出力値の各ビットが前記延長入力値の各ビットに依存するような関数である請求項８に記載の方法。
【請求項１６】
すべての前記第１の入力値が前記第２の入力値に連結されて、前記延長入力値を生成する請求項８に記載の方法。
【請求項１７】
前記第１の反転可能関数が非疑似ランダム関数である請求項８に記載の方法。
【請求項１８】
前記出力値の前記副部分の１つが、どのキー回復エージェントにも使用可能にされない非共用キー回復値である請求項８に記載の方法。
【請求項１９】
協働する複数のキー回復エージェントを使用するコンピュータまたはワークステーションを含んで構成され、暗号キーを回復する装置であって、
前記暗号キーおよび公開情報を反転関数に入力して暗号キーを反転させ、反転された前記暗号キーから前記暗号キーを再生可能な、複数の共用キー回復値を生成する手段と、
ソルト値を使用して前記キー回復エージェントの公開回復キーにより前記共用キー回復値をそれぞれ暗号化することで、前記複数の暗号化された共用キー回復値を生成し、かつ前記暗号化された前記共用キー回復値から前記共用キー回復値を生成させるため、前記キー回復エージェントの情報を含む回復情報を生成して前記暗号キーにより暗号化された第１のメッセージに伴うセッション・ヘッダに書き込んでメッセージ・パケットを生成する手段と、
通信チャネルを介して前記メッセージ・パケットを送信する手段とを含み、
前記メッセージ・パケットを受信した他のキー回復エージェントをして、前記セッション・ヘッダと共に前記第１のメッセージを読み取らせ、前記暗号化された共用キー回復値と前記公開情報とから共用キー回復値を回復させて前記暗号キーを回復させる
装置。
【請求項２０】
前記複数の共用キー回復値を生成する手段が、
前記暗号キーから反転関数を使用して、どのキー回復エージェントとも共用されない非共用キー回復値を生成する手段をさらに含み、前記キーが前記共用キー回復値および前記非共用キー回復値によって完全に決定される請求項１９に記載の装置。
【請求項２１】
各前記キー回復エージェントが、公開回復キーおよび対応する秘密回復キーを有する請求項１９に記載の装置。
【請求項２２】
前記複数の共用キー回復値を生成する手段が、
前記暗号キーの第１の反転可能関数の第１の入力値を生成する手段と、
前記第１の入力値の少なくとも一部を第２の入力値に連結して、延長入力値を生成する手段と、
前記延長入力値の第２の反転可能関数の出力値を生成する手段と、
前記出力値を副部分に分割して、前記共用キー回復値を生成する手段とを含む請求項１９に記載の装置。
【発明の詳細な説明】
本発明は、暗号キー回復システムに関し、より詳細には、通信当事者間でキーを確定するために既存のシステムと協働するキー回復システムに関する。
データ暗号化システムはデータ処理技術分野で周知である。一般に、そのようなシステムは、暗号化キーを使用して、平文入力ブロックに対して暗号化操作を実施して、暗号文出力ブロックをつくり出すことによって動作する。暗号化されたメッセージの受信者は、暗号解読キーを使用して、対応する暗号解読操作を実施して、平文ブロックを回復する。
暗号化システムは２つの種類に分けられる。データ暗号化標準（ＤＥＳ）システムなど対称（または秘密キー）暗号化システムは、メッセージの暗号化と暗号解読の両方に同じ機密キーを使用する。ＤＥＳシステムでは、独立して指定可能な５６個のビットを有するキーを使用して、６４ビット平文ブロックを暗号文ブロックに変換し、逆もまた同様である。
他方、非対称（または公開キー）暗号化システムは、互いに容易に推論できない異なるキーを暗号化と暗号解読に使用する。メッセージを受信したい人は、一対の対応する暗号化キーおよび暗号解読キーを生成する。暗号化キーは公開にされるが、対応する暗号解読キーは非公開にされる。受信者と通信したい人は、受信者の公開キーを使用してメッセージを暗号化することができる。ただし、受信者だけが秘密キーを持っているので、受信者だけがメッセージを暗号解読することができる。おそらく最も良く知られている非対称暗号化システムは、その創始者であるRivest、Shamir、Adlemanに因んで名付けられたＲＳＡ暗号化システムであろう。
非対称暗号化システムは、一般に対称暗号化システムよりも多くの計算を必要とするが、暗号化キーを伝送するための安全保護チャネルを必要としないという利点を有する。この理由で、非対称暗号化システムは、しばしば対称暗号化キーなどの秘密データを移送するために使用される。
すべてのタイプのデータ暗号化システムは、政府情報機関および法律施行機関の注目を引いている。これは、権限のない第三者による暗号解読を防ぐ同じ暗号強度が、平文データにアクセスしたい正当な理由を持っている情報局員または法律施行局員による暗号解読をも防ぐからである。そのような関心のために、政府は、強力な暗号化システムの使用または輸出を禁止するか、またはキー消耗攻撃（すなわち、正しいキーが見つかるまで考えられるすべてのキーを組織的にテストすること）を受けやすい弱いキーの使用に関して政府の承認を条件としている。そのような弱い暗号化システムは、権限を与えられた政府公務員に対して弱いだけでなく、権限のない第三者に対しても弱いという明らかな欠点を有する。
最近、電子通信でのプライバシーに対する通信当事者の要求と、犯罪または国家安全保護に対する脅威を摘発する必要がある場合のそのような通信へのアクセスに対する法律施行機関の要求との折衷案として様々な暗号キー回復システムが提案されている。一般に、そのようなキー回復システムでは、通信当事者が使用したキーの全部または一部が、実際にそのキー部分をキー回復エージェントに与える（この場合、キー部分が「エスクロー」されるという）か、またはキー回復エージェントがキーの一部を再生することができるように（キー部分の暗号化などによって）通信自体に十分な情報を提供することによって、１つまたは複数のキー回復エージェントに入手可能である。キー回復エージェントは、傍受の権限を与える裁判所命令など、権限の正確な証拠が提示されたときのみ、エスクローまたは再生されたキー部分を要求側法律施行エージェントに明かすだろう。複数のキー回復エージェントを使用した場合、すべてのエージェントは協働してキーを回復しなければならず、法律施行エージェントが不正なキー回復エージェントを使用してキーを不正に回復する可能性は最小限に抑えられる。
キー回復システムは、プライバシーに関する通信者の関心を満たす。これは、それらの暗号化システムが第三者に対してその十分な強度を保持しており、また暗号化に関する国内制限に従うか、または輸出要件を満たすように弱められる必要がないからである。同時に、キー回復システムは、暗号化されていない通信が予め傍受されている状況（裁判所命令が得られている状況など）で暗号化された通信を傍受することができるので法律施行の正当な必要を満たす。
法律施行の必要を満たすこと以外に、キー回復システムは純粋に私的な状況に応用できる。したがって、組織は、キーが回復できない重要なファイルの強力な暗号化を使用する被雇用者を心配している。キーをなくすことは重要な記憶されたデータをなくすことになる。
キー回復システムのいくつかの望ましい特徴は確定している。したがって、まず優先度の高い特徴について考えてみると、キー回復システムは、ソフトウェアまたはハードウェアの形で実施できなければならない。キー回復システムは、メッセージ生成または接続確立の際に第三者との通信を必要としてはならない。キー回復システムは、異なる国のユーザ間の共通操作性を提供しなければならない。使用されるアルゴリズムは公に知られていなければならず、その機構はアルゴリズム独立でなければならない。その設計は公開され、出版された仕様に基づいて複数のベンダが実施できるものでなければならない。キー回復システムは、各国ごとにキー回復能力を独立して提供しなければならない。キー回復システムは、単一のシステムで、異なる環境で異なるレベルの安全保護に対するフレキシビリティを提供しなければならず、また法律によって許される最高レベルの暗号安全保護を提供しなければならない。キー回復システムは、既存の暗号システムのモジュール拡張（アドオン）でなければならない。キー回復システムは、どんなキー交換機構でも使用でき、同時にキー回復のための制御点を保持しなければならない。回復を許すことを除いて、交換されたキーの機密性が維持されなければならない。
他の特徴は、優先度が低いとは言えかなり望ましい。キー回復システムは蓄積交換環境と対話式環境の両方をサポートすべきである。キー回復システムは、設置について第三者との通信を必要とすべきでない（すなわち、キー回復システムは「アウト・オブ・ザ・ボックス」で動作する）。キー回復システムは、（不正なキー回復エージェントに対して保護を実施するために）キーを回復するために複数のキー回復エージェントの協働を必要とする方針選択をサポートすべきである。キー回復システムは、当事者がこのシステムのアンパッチ・インプリメンテーションを使用することに対するある程度の信用を外部検証者が（キー回復キーへのアクセスなしに）持てるようにすべきである。（対話式環境では、両方の当事者が同じ公開キーとキー回復情報を使用して暗号化する場合、第三者は暗号文の同一性について検査することができることに留意されたい。）キー回復システムは、パッチ（不正）インプリメンテーションがアンパッチ（準拠）インプリメンテーションと協働するのを防ぐべきである。バルク・データ機密性チャネルでの使用のために方式を変えるのは難しい。
様々なタイプのキー回復システムが参照により本発明の一部となるD.E. DenningおよびD.K. Branstadの「A Taxonomy for Key Escrow Encryption Systems」、Communications of the ACM、vol. 39、no. 3、1996年3月、pp,34-40に記載されている。２つの特定のキー回復システムを以下に示す。
１９９６年４月１０日出願のD.B. Johnson他の特許出願第０８／６２９８１５号「Cryptographic Key Recovery System」には、複数のキー回復エージェントを使用した部分キー回復システムが記載されている。その出願に記載されているシステムの１つのバージョンでは、送信者は、一組のキー回復値（またはキー・パート）Ｐ、Ｑおよび（任意選択で）Ｒを生成する。セッション・キーは、Ｐ値とＱ値をＸＯＲ加算によって結合し、結果をＲと連結し、連結結果をハッシュして、キーを生成することによって生成される。次いで、各キー回復エージェントの公開キーを使用してＰ値とＱ値を暗号化し、暗号化されたＰ値とＱ値を（他の回復情報とともに）暗号化されたメッセージに付随するセクション・ヘッダ内に入れる。Ｒ値が生成された場合、Ｒ値は、どのキー回復エージェントにも使用可能にされず、キーを回復しようとする法律施行エージェントに対して重要なワーク・ファクタを提供するために非公開にされる。
上記の説明から明らかなように、上記特許出願に記載されているキー回復手順では、キー回復手順自体の機構を使用して、メッセージを暗号化するために使用される機密セッション・キーを確立する必要がある。ユーザがセッション・キーを独立して指定することができないので、開示されたキー回復手順は既存のキー一致手順に適合しない。
ＰＣＴ公開特許明細書ＷＯ９６／０５６７３（Trusted Information Systems社）に記載されている他のキー回復システムでは、送信者は、第１のセッション・キー部分を乱数に等しくなるように設定し、かつ第２のセッション・キー部分をその乱数とそのセッション・キーとのＸＯＲに等しくなるように設定することによって、セッション・キーを第１のセッション・キー部分と第２のセッション・キー部分とに分割する。送信者は、第１および第２のキー回復エージェントの公開暗号化キーを使用してそれぞれのセッション・キー部分を暗号化し、かつ２つの暗号化生成物を連結することによって、法律施行アクセス・フィールド（ＬＥＡＦ）を生成する。送信者はまた、元のセッション・キー部分を連結することによってＬＥＡＦ検証ストリング（ＬＶＳ）を生成し、セッション・キーを使用してこれを暗号化して、暗号化ＬＥＡＦ検証ストリング（ＥＬＶＳ）を形成する。最後に、送信者は、暗号化されたメッセージをＬＥＡＦおよびＥＬＶＳと一緒に受信者に送信する。
暗号化されたメッセージを暗号解読する前に、受信者は、実際にキー回復エージェントを介してセッション・キーの回復を可能にする適切なＬＥＡＦを送信者が生成したことを検証するためにＬＥＡＦを再生する。これは、ＥＬＶＳを暗号解読して、セッション・キー部分を得、次いで第１および第２のキー回復エージェントの公開暗号化キーを使用して各セッション・キー部分を暗号化することによって行われる。受信者は、送信されたＬＥＡＦをこのような形で再生するのに成功した場合、ＬＥＡＦが真正であると結論し、メッセージの暗号解読に取りかかる。それ以外の場合、受信者は、ＬＥＡＦが不正であると結論し、暗号解読ステップには取りかからない。
このキー回復システムは、受信者が有していない追加の機密量（乱数）をキー分割手順に導入することによって、任意に生成されたセッション・キーの使用を可能にする。この追加の機密量のために、受信者は（ＬＥＡＦを確認するために）キー部分を独立して再生することができず、それらを（ＬＥＶＳによって）送信者から追加の情報として得なければならない。
本発明の第１の態様によれば、協働する複数のキー回復エージェントを使用して、暗号キーを回復する方法であって、前記キーの関数として、追加の非公開情報を必要とせずに前記キーを共用キー回復値から再生できるような形で複数の共用キー回復値を生成するステップと、
前記キー回復エージェントを使用して、前記キーの回復を容易にするために前記共用キー回復値を前記キー回復エージェントに使用可能にするステップとを含む方法が提供される。
本発明の第２の態様によれば、機械によって読取り可能であり、機械が下記の方法クレームに定義する方法ステップを実施するために実行可能な命令のプログラムを実体化するプログラム記憶装置が提供される。
本発明は、キー回復を処理するシステムを意図している。本発明は、ユーザが所望のキー配布手順またはキー一致手順（たとえば、完全転送機密の属性を有する手順）を使用してセッション・キーを確立できるようにすることによって、D.B. Johnson他の特許出願に記載されているシステムを強化する。セッション・キーを確立するために使用される機構は、暗号キー回復手順から独立しており、それに対して完全に透過的である。同時に、本発明はキー配布手順がない場合にそれを提供する。
本発明の１つの特徴は、キー回復手順に必要なＰ値、Ｑ値、Ｒ値を機密セッション・キーから（すなわち、キーから逆に動作することによって）生成できるようにする新しいキー反転関数にある。すなわち、セッション・キーは独立変数であり、Ｐ値、Ｑ値、Ｒ値は従属変数である。これに対して、D.B. Johnson他の特許出願では、Ｐ値、Ｑ値、Ｒ値は独立変数であり、キーは従属変数である（すなわち、キーはＰ値、Ｑ値、Ｒ値から導出される）。
（既存のキー確立手順に適合できないという）問題の考えられる１つの解決策は、上述のＰＣＴ出願に記載されているように、「キー共用」または「キー分割」と呼ばれる方法を使用することであった。しかしながら、上述のように、キー共用は、キー回復手順のもとで送信者から受信者に機密に送信されなければならない追加の機密変数を導入する。本発明は、そのような要件を回避すること、および受信者がキー回復手順の自分の分を実施できるように送信者が機密情報を受信者に伝達する必要をなくすことを目的とする。この問題は、機密セッション・キーとキー回復手順によって使用される公開情報とからＰ値、Ｑ値、Ｒ値を計算できるようにする特別なエントロピー保存キー反転関数を構成することによって回避される。
以下で説明する実施形態のキー反転関数とキー共用との違いについてさらに説明する。キー反転関数は、キーを「等価表示」に変換するために使用される。キー反転は、もっぱら入力としてのキーと公開パラメータとに基づいている。したがって、キー反転は、キーにアクセスできるだれでもが容易に検証することができる。また、出力（すなわちキー回復）値が与えられれば、（検証には出力値と公開変数のみが必要であるので）キーを容易に検証することができる。キー反転は、キーと公開パラメータのみを使用し、機密共用に使用される追加のランダム・ビットを必要としないので、「機密共用」技法とは異なる。したがって、（上記のＰＣＴ出願の場合と同様に）キーを２つの値に分割するとき、分割の「エントロピー」（すなわち、ランダムネス・コンテント）は最初のキーと比較して二倍になる。反対に、本発明のキー反転は、反転機構に追加のランダムネスが不要であるのでキーの「エントロピー」を増大させない。
このエントロピー保存のために、説明した実施形態のキー反転関数は、実際に反転可能であり、キーから始めて出力値を導出するか、または出力値から始めてキーを導出することができる。これは、出力の検証およびその使用法にとって重要である。機密共用技法はそのような検証を考慮していない。
以下で説明するように、本発明は、（１）当事者がキーに同意できるように、または独立して確立されたキーを使用できるようにするため、（２）受信者が関連するキー回復情報を検証できるようにするため、（３）権限を与えられたエンティティにキーの構成要素を回復する能力を与えるため、（４）権限を与えられたエンティティに、キー回復エージェントによって与えられたキー回復情報の正しいことを検証する能力を与えるために、十分な情報を含むセッション・コンテキストを送信する。
機密値は様々な形で使用可能にされる。機密値は暗号化され、第三者に使用可能にされることもある。あるいは、機密値は暗号化され、暗号化されたデータとともに送信されることもある。その場合、機密値は電子手段を介してアクセスしなければならない。本明細書の例では後者の手法について説明している。
本発明は、既存のキー配布方式に対して置換ではなく「アドオン」として実施される。「アドオン」手法によれば、既存の暗号化システムが本発明の利点（より長いキー）を得ることができ、同時にシステムの既存のキー配布構成要素の変更を要求しない。したがって、本発明の主要な目的の１つは、できるだけ自己完結型で独立のものとし、かつキー回復を実施するために既存の暗号化システムまたはアプリケーションの必要な変更を最小限に抑えることである。
以下で説明するシステムおよび方法の利点を手短に要約する。このシステムおよび方法は、キー配布手順と協働できるアドオン解決策であり、またキー配布がない場合にそれを提供する。このシステムおよび方法によれば、回復エージェントによる失われた暗号キーの回復が可能になる。キー回復エージェントによって保持されるユーザ・キーはない。キー回復エージェントはユーザ・キーを生成する役目を有しない。このシステムおよび方法はマルチウェイ・キー回復方式である。システムおよび方法によれば、強力な暗号を世界中で使用可能にする。このシステムおよび方法は、正当で権限を与えられた法律施行の必要に対処し、同時に他のキー回復提案に固有の弱さ（たとえば、ユーザ・キーを確立するためのインフラストラクチャの要件または特別なハードウェア・デバイスの要件）に対処する。このシステムおよび方法には、キー長さに関する制限はなく、またアルゴリズムの制約もない。このシステムおよび方法はすべてのキー交換機構と協働できる。セッション暗号キーのみが回復可能である。キー回復情報の一部が方針に従って使用可能にされる。一様な（暗号アルゴリズム独立の）ワーク・ファクタが完全なキー回復のために提供される。本発明は暗号化のみを使用するので、バルク・データ機密性チャネルでの使用のために方式を変えるのは難しい。
以下で説明するように、本発明の実施形態は多くのフレキシビリティを提供する。たとえば、本発明は各国の法律および規則に適合でき、それらを遵守できる。本発明は、非エスクロー・キー長およびキー・エスクロー・キー長に対するビルトイン・フレキシビリティを有する。２国間の通信の場合、エスクロー規則はデフォルトでＰおよびＲの値を小さくし、その結果ワーク・ファクタが小さくなる。キー管理は、現代の標準業界慣行に一致する様々な形で行われる。
本発明は、２人の協働不正ユーザの検出を実施しようと試みない。２人のユーザは常にこのシステムの外で「彼ら自身のことを行う」ことができる。
本発明は、異なる国のユーザおよび権限を与えられたキー回復エージェントの通信の必要に対処する。本発明は、非常に様々な暗号アルゴリズムおよびキー長に適用できる。本明細書では、１６８ビットの全キー長を有するトリプルＤＥＳの例を使用する。
本発明では、キー回復エージェントと動作する際の公開キー暗号の使用を仮定する。本発明は、ユーザ間のキー配布のための公開キー暗号の使用を仮定しない。本明細書のキー配布の例は公開キー暗号（たとえば、ＲＳＡまたはDiffie-Hellmanキー交換）のみを使用するが、対称キー暗号（たとえばKerberos）も使用できる。本発明は、キー配布機構によって提供される機密を維持する。本発明はキー回復能力を高める。たとえば、キー配布が完全転送機密を有する場合、この特性は維持される。
本発明は、ユーザならびにキー回復エージェントの公開キーが証明されると仮定する。そのような証明を行う手順および機構は当技術分野で周知であり、このシステムの範囲外である。
各国は複数のキー回復エージェントを使用することができる。各キー回復エージェントは一意のＩＤを有する。
キー回復エージェントおよび／またはそれらの証明者の公開キー、またはこれらの公開キーを得る安全保護手段は、いくつかの機構の１つを使用してクライアントのハードウェアまたはソフトウェアで与えられる。したがって、各キー回復エージェントは、それ自体の公開キーと秘密キーの対（たとえば１０２４ビットのＲＳＡキー）を生成し、公開キーは公開するが、秘密キーは機密に保つ。（暗号装置は可変のキー・サイズを処理することができる）。これにより「アウト・オブ・ザ・ボックス」でターン・キー解決策として動作する能力を有する暗号化製品が出荷できるようになる。開示したキー回復システムを組み込んだシステムは、そのシステムが位置し、動作できる国を示す国ＩＤで事前に構成できる。ユーザはまた、キー回復手順に必要な他の情報でシステムを構成することができる。
キー回復能力のみを有する暗号製品では、その実施形態は、暗号化アルゴリズムを直接呼び出すことによってアプリケーション・プログラムがキー回復システムを回避することを許さない。キー回復システムは、呼び出された後、キー回復手順ステップがとられることを保証する。すなわち、データ・プライバシー暗号化に使用されるキーは、手順ステップがうまく完了するまでアプリケーション・プログラムまたはユーザに使用可能にされない。
次に、本発明の実施形態について、例としてのみ添付の図面を参照しながら説明する。
第１図は、本発明が使用される通信システムの概略ブロック図である。
第２図は、特定の国に対して実施される本発明の一般キー反転方式の概略ブロック図である。
第３Ａ図は、セッション・キーからキー回復値を生成するための例示的なキー反転関数の概略ブロック図である。
第３Ｂ図は、セッション・キーからキー回復値を生成するための代替キー反転関数の概略ブロック図である。
第４図は、独立して確立されたセッション・キーを使用して暗号化されたメッセージを受信者に送信したい送信者が使用する手順の流れ図である。
第５図は、送信者からメッセージ・パケットを受信したときに受信者がとる手順の流れ図である。
第６図は、メッセージ・ヘッダのセッション・コンテキストの概略ブロック図である。
第７図は、メッセージ・パケットのセッション・ヘッダの概略ブロック図である。
第８図は、メッセージ・パケットの概略ブロック図である。
第９図は、セッション・コンテキストの回復情報の概略ブロック図である。
第１０図は、第９図のセッション・コンテキストのキー回復エージェント・キー・ヘッダの概略ブロック図である
第１１図は、共用キー回復値を暗号化するための手順の概略ブロック図である。
第１２図は、本発明で使用するグローバル通信方針テーブルを示す図である。
第１３図は、本発明の可能なシステム実施形態の概略ブロック図である。
第１４図は、第３Ａ図のキー反転関数で使用されるシャフラ関数の概略ブロック図である。
第１５図は、第１４図に示されるシャフラ関数の反転の概略ブロック図である。
第１６図は、第１４図に示されるシャフラ関数で使用されるブロックの１つを細分する方法の概略ブロック図である。
一般環境
第１図に、本発明のキー回復システムが使用される通信システム１００を示す。
システム１００で、国Ｘの送信者１０２（「アリス」）は、通信チャネル１０６を介して（通信セッションを構成する）１つまたは複数の暗号化されたメッセージを送信することによって国Ｙの受信者１０４（「ボブ」）と通信する。送信者１０２と受信者１０４はそれぞれ、以下で説明する暗号化関数およびキー回復関数を提供するように適切にプログラムされたコンピュータ・ワークステーションを含む。第１図の例は、送信者１０２と受信者１０４が異なる国（ＸとＹ）に位置すると仮定しているが、本発明はまた完全に単一の国内で使用することもできる。
送信メッセージは、送信者１０２がセッション暗号化キーを使用して暗号化し、受信者１０４が対応するセッション暗号解読キーを使用して暗号解読する。対称暗号化方式（たとえばＤＥＳ）を使用する場合、セッション暗号化キー（これはセッション暗号解読キーでもある）がキー回復のための「機密」セッション・キーである。他方、非対称暗号化方式（たとえばＲＳＡ）を使用する場合、以下でさらに説明するように、プライベート・セッション暗号解読キーがキー回復のための「機密」セッション・キーである。
キー回復エージェント１０８および１１０の対（この特定の例では）は国Ｘで選択され、キー回復エージェント１１２および１１４の対は国Ｙで選択される。キー回復エージェントの確立は一般公開キー・インフラストラクチャの確立の一部として行うことができる。
通信チャネル１０６による通信は、国ＸおよびＹの各法律施行エージェント１１６および１１８を含む第三者による傍受を受けやすいと仮定する。暗号化された通信を傍受する民間の第三者は、１つまたは複数の暗号解読技法をうまく使用しなければ通信を解読することはできない。他方、正当な権限を有する法律施行エージェント１１６または１１８は、以下で説明するように自身の国のキー回復エージェント１０８、１１０または１１２、１１４を使用してセッション・キーを回復することができる。
キー反転関数：一般形態
第２図に、（たとえば）国Ｘに対して実施される本発明の一般キー反転方式２００を示す。送信者１０２は、キー反転関数２０４を呼び出して、機密セッション・キーＫ（２０２）および公開情報に応じて一対の共用キー回復値ＰおよびＱ（２０６および２０８）ならびに任意選択で非共用キー回復値Ｒ（２１０）を生成する。
以下でより完全に説明するように、送信者１０２は、キー回復エージェントの各公開回復キーを使用して共用キー回復値ＰおよびＱを暗号化して、暗号化されたキー回復値Ｐ’およびＱ’を生成することによって、共用キー回復値ＰおよびＱを国Ｘの第１および第２のキー回復エージェント１０８、１１０に使用可能にする。送信者１０２は、少なくとも通信チャネル１０６を介して受信者１０４まで第１のメッセージに伴うヘッダ中に暗号化されたキー回復値Ｐ’およびＱ’を含む。他方、非共用キー回復値Ｒ（生成された場合）はどんな第三者にも明かされない。
キー反転関数２０４は、（１）キーＫと生成されたキー回復値との間で１対１の対応を与える、（２）関数を反転させることによってキーＫをキー回復値から容易に再生することができる、という意味で反転可能である。生成されたキー回復値がＰおよびＱのみを含む（すなわちＲが生成されない）場合、キーＫは、完全にＰおよびＱによって決定され、これらの値が分かっていれば容易に再生できる。生成されたキー回復値がＲを含む場合、キーは、Ｐ、Ｑ、Ｒによってのみ完全に決定され、ＰおよびＱのみからは容易に決定できない。しかしながら、キー反転関数２０４によって生成された可能なＲ値の数は、以下で説明するように、ＰおよびＱを知っている法律施行エージェントが可能なＲ値のスペースを使い尽くすことによってキーＫをうまく再生することができるよう十分小さくされる。Ｒを確認するために必要なワーク・ファクタは、法律施行エージェントがＰ値およびＱ値を得た場合でも、法律施行エージェントによるメッセージの通常の暗号解読を思いとどまらせるようになされている。
法律施行エージェント１１６は、それが傍受したメッセージを解読するために、セッション・ヘッダから暗号化されたキー回復値Ｐ’およびＱ’を取り出し、それらを（裁判所命令など）権限の正確な証拠と一緒にキー回復エージェント１０８、１１０に提示する。キー・エスクロー・エージェント１０８、１１０は、法律施行エージェントの権限があると確信したとき、それらのプライベート暗号解読キーを使用して暗号化されたキー回復値を解読し、回復された値ＰおよびＱを法律施行エージェント１１６に与える。次いで、法律施行エージェントは、Ｒの連続する試験値を生成し、それらを元のセッション・キーＫが回復されるまで回復されたＰ値およびＱ値と一緒にキー反転関数２０４に入力として供給する。
キー反転関数：特定の実施形態
第３Ａ図に、セッション・キーＫからキー回復値Ｐ、Ｑ、Ｒを生成するか、またはキー回復値Ｐ、Ｑ、Ｒからセッション・キーＫを生成する例示的なキー反転関数３００を示す。例示的なキー反転関数３００はユーザごとに２つのキー回復エージェントに対してＰ値およびＱ値を生成するが、送信者と受信者がそれぞれ２つ以上のキー回復エージェントまたはただ１つのキー回復エージェントを有する場合に対処するためにキー反転関数は任意の数の出力を生成することができる。
キー反転関数３００は以下の入力を必要とする。すなわち、（１）キーＫ、（２）ビットで表したキーＫの長さ、（３）ｒで示されるビットで表したＲの長さ、（４）通信当事者１０２、１０４の第１および第２のキー回復エージェントＩＤ９１２、９１６、９２２、９２６を含めて、記述すべき回復情報６１０（第９図）。
元のキーＫは、最大１５個の０ビットを最上位ビット位置に埋め込むことによって事前処理され、ｎビットの処理されたキー３０２を形成する。ただし、ｎは１６の倍数である。第３Ａ図の例は、送信者が国ＸでｒビットのＲ値を使用し、受信者が国Ｙで０ビットのＲを使用する場合を示す。
ｎビットの埋め込み済みキー３０２は、（以下でさらに説明する）第１の反転可能な「シャフラ」関数３０４で処理され、Ｆ（Ｐ、Ｑ、Ｒ）で示されるｎビット出力値３０６を生成する。Ｆ（Ｐ、Ｑ、Ｒ）のどのビットもすべてのキー・ビットに疑似ランダムに依存する。Ｆ（Ｐ、Ｑ、Ｒ）はキーＫの代表または変更形態である。
送信者のエージェントのＰｘ値およびＱｘ値は、Ｆ（Ｐ、Ｑ、Ｒ）から次のようにして生成される。Ｆ（Ｐ、Ｑ、Ｒ）の任意のｒビット（たとえば最下位ｒビット）を値Ｒ（３０８）として定義する。Ｆ（Ｐ、Ｑ、Ｒ）の残りのｎ−ｒビット（たとえば最上位ｎ−ｒビット）を（記述すべきシャフラ関数への）第１の入力値Ｆ（Ｐｘ、Ｑｘ）（３１０）として定義する。（ｎ＋ｒ）ビットの第２の入力値Ｈｘ（３１６）を（ｎ−ｒ）ビットの第１の入力値Ｆ（Ｐｘ、Ｑｘ）（３１０）の前に付けて、２ｎビットの延長入力値３１７を生成する。次いで、延長入力値３１７を第２の反転可能シャフラ関数３１８を使用して処理して、２ｎビット出力値３１９を生成する。最後に、出力値３１９をｎビット値Ｐｘ（３２０）とｎビット値Ｑｘ（３２２）とから構成される部分に分割する。シャフラ関数３１８は、入力値３１７および出力値３１９の長さを除いてシャフラ関数３０４と同じである。Ｈｘのビットの数は、シャフラ関数３１８への最後の入力が常に（キー回復エージェントの数にかかわらず）偶数のバイトになることを保証する。
Ｈｘの（ｎ＋ｒ）ビット値（３１６）は次のようにして計算する。送信者の第１および第２のキー回復エージェントＩＤ９１２および９１６（第９図）、回復情報（Ｔ１）に基づいて計算したハッシュ値Ｈ（Ｔ１）６１０（第９図）、Ｆ（Ｐ、Ｑ、Ｒ）、ならびに公開ヘッダを所定の順序で（たとえば上記の順序で）連結して、Ｄ１で示されるデータ・ブロックを形成する。
Ｄ１＝（送信者の第１のキー回復エージェントＩＤ｜｜送信者の第２のキー回復エージェントＩＤ｜｜Ｈ（Ｔ１）｜｜Ｆ（Ｐ、Ｑ、Ｒ）｜｜公開ヘッダ）
回復情報６１０（Ｔ１で示される）は第９図で定義し、説明する。送信者の第１および第２のキー回復エージェントＩＤ９１２および９１６はこのキー回復情報の一部である。公開ヘッダは次のように定義される８バイト構造である。
１バイト  識別子：ハッシュすべきデータ＝「ＰＱキー回復エージェントＩＤ」
１バイト  カウンタ：０、１、２、など
６バイト  予約済み：０にセット
データ・ブロックＤ１（公開ヘッダ中のカウンタは最初０）をハッシュして、ハッシュ値Ｈ（Ｄ１）を生成する。Ｈ（Ｄ１）の長さがｎ＋ｒよりも小さい場合、合計長さがｎ＋ｒに等しいかまたはそれよりも大きくなるまで連続するハッシュＨ（Ｄ１）を連結する（カウンタは後続のハッシュごとに増分する）。Ｈｘは最下位ｎ＋ｒビットとして定義される。この技法は大きいＲ長に対してワークロード・ファクタが小さくなるのを防ぐ。
値Ｐｘ（３２０）および値Ｑｘ（３２２）はそれぞれシャフラ関数３１８から生成された２ｎビット出力３１９の最上位ｎビットおよび最下位ｎビットである。Ｐｘ（３２０）は送信者の第１のキー回復エージェント１０８の公開キーで暗号化された値である。Ｑｘ（３２２）は送信者の第２のキー回復エージェント１１０の公開キーで暗号化された値である。
受信者のエージェントのＰｙ値およびＱｙ値は、次のようにして元のキーから同様にして生成される。受信者１０４は（この例では）Ｒ値を有しないので、全Ｆ（Ｐ、Ｑ、Ｒ）値３０６をｎビットの第１の入力値Ｆ（Ｐｙ、Ｑｙ）（３２４）と定義する。ｎビットの第２の入力値Ｈｙ（３２６）をｎビットの第１の入力値Ｆ（Ｐｙ、Ｑｙ）（３２４）の前に付けて、延長入力値３２７を生成する。次いで、延長入力３２７を（前に説明したシャフラ関数と同様の）シャフラ関数３２８を使用して処理して、２ｎビット出力値３２９を生成し、これをｎビットＰｙ（３３０）とｎビットＱｙ（３３２）に分割する。ＨｙをＨｘと同様にして計算する。ただし、データ・ブロック（ここではＤ２で示される）を形成する際、送信者の第１および第２のキー回復エージェントＩＤ９１２、９１６の代わりに受信者の第１および第２のキー回復エージェントＩＤ９２２、９２６を使用する（第９図）。
所与の当事者の第１または第２のキー回復エージェントとして指定される特定のキー回復エージェントは、それらのＩＤが回復情報６１０中に現れる順序によって決定される（第９図）。送信者の第１および第２のキー回復エージェントＩＤ９１２、９１６ならびに受信者の第１および第２のキー回復エージェントＩＤ９２２、９２６はそれぞれ回復情報６１０内で分類された順序で配置される。したがって、Ｐ、Ｑ、Ｒの値およびソルト値（以下で説明する）を生成し、データ構造を構築するプロセスは完全に決定論的プロセスである。
キー反転関数３００は、それによって生成されたＰ、Ｑ、Ｒの値が機密キーＫおよび他の公開情報から導出されるのでエントロピー保存関数である。すなわち、キーの組み合わせの数はＰ−Ｑ−Ｒの組み合わせの数と同じである。機密共用方式では、エントロピーは、元のキーを回復するために必要な分割の数とともに増大する。
キー反転関数３００は、Ｐ、Ｑ、Ｒの値を計算するプロセスでキーＫ全体を必要とする。したがって、（たとえば）Ｐの値がわかったとしても、順方向または逆方向にキー反転関数を実行して、キーＫを徹底的に決定するためのワークファクタよりも小さいワークファクタでＱを徹底的に決定することはできないであろう。
送信者１０２が機密プロトコル情報を受信者１０４に伝達する必要はない。受信者１０４が暗号化されたＰおよびＱの値を検証するために必要な唯一の機密値は機密セッション・キーＫである。任意選択で、送信者１０２は機密署名生成キーを有し、受信者１０４は送信者の公開検証キーの有効コピーを有する。その他、送信者１０２と受信者１０４は、本発明の暗号化手順を実行するためにそれらの間で確立される特別のキーを必要としない。
本発明は、すべての暗号キー・タイプについて（法律施行エージェントから見える）ワーク・ファクタに一様性をもたらす。さらに、ワーク・ファクタはすべてのタイプの暗号化アルゴリズムに対して一貫性がある。すなわち、４０ビットのワーク・ファクタはＤＥＳ、公開キー、ＲＣ２／４／５、または他のアルゴリズムに対して常に４０ビットである。
キー反転関数３００は、機密キーＫが独立ランダム変数（たとえばＲＳＡ機密キー）でない状況に適応する追加の利点を有する。たとえば、公開キーが固定の定数（たとえば２１６−１）である場合、機密キーは従属変数である。そのような機密キーは独立したＰ、Ｑ、Ｒの値から生成することができない。キー反転関数を使用して、機密キーからＰ、Ｑ、Ｒの値を生成する必要がある。
第３Ａ図の手順３００は、任意の数のキー回復エージェントを処理するために拡張することができる。たとえば、送信者１０２が３つのキー回復エージェントを有する場合、２ｎ＋ｒビットのＨｘをＦ（Ｐｘ、Ｑｘ）の前に付ける。そのような場合、データ・ブロックＤ１は２つではなく連結された３つのキー回復エージェントＩＤを有する。一般に、ｋ個のキー回復エージェントがある場合、（ｋ−１）ｎ＋ｒビットをＦ（Ｐｘ、Ｑｘ）の前に付ける。そのような場合、データ・ブロックＤ１は２つではなく連結されたｋ個のキー回復エージェントＩＤを有する。同様に、受信者１０４が３つのキー回復エージェントを有する場合、２ｎビットのＨｙをＦ（Ｐｙ、Ｑｙ）の前に付ける。受信者がＲ値を有しないのでｒは受信者の式中には現れない。受信者１０４がｋ個のキー回復エージェントを有する場合、（ｋ−１）ｎビットのＨｙをＦ（Ｐｙ、Ｑｙ）の前に付ける。受信者のデータ・ブロックＤ２はまた必要な追加のキー回復エージェントＩＤを含めることによって変更される。
ただ１つのキー回復エージェントがある場合（たとえば、国Ｘの送信者１０２がただ１つのキー回復エージェントを使用する場合）、手順はわずかに変更される。ＰおよびＱの値は、２つのキー回復エージェントが必要な場合と同様にして計算する。ただし、Ｈｘの値（第３Ａ図）の計算はわずかに異なる）。この場合、データ・ブロックＤ１＝（第１のキー回復エージェントＩＤ｜｜第１のキー回復エージェントＩＤ｜｜Ｈ（Ｔ１）｜｜Ｆ（Ｐ、Ｑ、Ｒ）｜｜公開ヘッダ）をハッシュして、１６０ビットのハッシュ値Ｈ（Ｄ１）を生成する。Ｈ（Ｄ１）がｎよりも小さい場合、前述のように、合計長さがｎに等しいかまたはそれよりも大きくなるまでカウンタを後続のハッシュ値Ｈ（Ｄ１）とともに使用する。この技法は大きいＲ長に対してワークロード・ファクタが小さくなるのを防ぐ。同じプロセスは、受信者１０４がただ１つのキー回復エージェントを有する場合でも使用される。その場合、ＨｙはＨｘと同様にして計算するが、送信者のエージェントＩＤの代わりに受信者のエージェントＩＤを使用する。
キー回復エージェントの数は国ごとにまたはアプリケーションごとに異なる。たとえば、送信者が２つのキー回復エージェントを使用し、受信者が１つまたは３つのキー回復エージェントを使用することもある。
セッション・キーＫを回復するために、法律施行エージェント１１６または１１８（第１図）は、ＰおよびＱの値からキーを生成するためにキー反転関数３００を逆に実行する。このためには、以下で説明するようにシャフラ関数３０４、３１８、３２８を逆方向に実行する必要がある。さらに回復されたＨｘまたはＨｙの値に対して処理を実行する。キーＫが回復された後、ＰおよびＱを暗号化するために使用されるソルト値（以下で説明する）を再計算し、暗号化されたＰおよびＱの値を再生し、傍受された暗号化されたＰおよびＱの値との同一性について検査する。
キー回復操作について、一例として国Ｘを使用してさらに説明する。第３Ａ図を参照すると、実施すべき第１の操作は、Ｐｘ（３２０）およびＱｘ（３２２）を「アンシャフル」して（すなわち、シャフラ関数３１８を逆に実行して）Ｈｘ（３１６）およびＦ（Ｐｘ、Ｑｘ）（３１０）を得ることである。次のステップはＲ（３０８）の徹底的なサーチを必要とする。正確なＲは、候補Ｒに基づいてＨｘを計算し、結果をアンシャフルしたＨｘと突き合わせることによってきわめて高い確度で検出できる。Ｆ（Ｐｘ、Ｑｘ）（３１０）およびＲ（３０８）が与えられれば、（シャフラ関数３０４を逆に実行することによって）量Ｆ（Ｐ、Ｑ、Ｒ）（３０６）をアンシャフルして、埋め込み済みキー３０２を得る。
第３Ｂ図に、各国ごとにただ１つのシャフリング操作があり、かつ３つのすべてのキー回復値Ｐ、Ｑ、Ｒが手順の同じ段階で生成されるキー反転関数の代替実施形態３５０を示す。
この代替実施形態では、送信者のエージェントのＰｘおよびＱｘの値は、次のようにして元のｎビット・キーＫ（３５２）から生成される。（ｎ＋ｒ＋ｓ）ビット値Ｈｘ（３５４）（上述のＨｘ値３１６と同様に計算される）をｎビット・キー３５２の前に付け、得られた（２ｎ＋ｒ＋ｓ）ビット入力値３５６をシャフラ関数３５８で処理して、（２ｎ＋ｒ＋ｓ）ビット出力値３６０を生成する。ｓは、２ｎ＋ｒ＋ｓが１６の倍数となるような０から１５までの整数である。次いで、出力値３６０をｒビットＲ値３６２、（ｎ＋ｓ／２）ビットＱ値３６４、（ｎ＋ｓ−ｓ／２）ビットＰ値３６６に分割する。ｓ／２は分数値の整数成分と定義する。すべての実際的な目的で、Ｐは、ＱおよびＲが抽出された後に残る出力ビットを示す。抽出方法は、出力中のすべてのビットが値Ｐ、Ｑ、Ｒ中に割り振られ、かつＰおよびＱの長さが高々１ビット異なることを保証する。
送信者のエージェントのＰｙおよびＱｙの値は、次のようにして元のキー（Ｋ）３５２から生成される。（ｎ＋ｓ）ビット値Ｈｙ（３６８）（上述のＨｙ値３２６と同様に計算される）をｎビット・キー３５２の前に付け、得られた（２ｎ＋ｓ）ビット入力値３７０をシャフラ関数３７２で処理して、（２ｎ＋ｓ）ビット出力値３７４を生成する。変数ｒは、ｒ＝０であるので式から落とされている。また、ｒは、２ｎ＋ｓが１６の倍数となるような０から１５までの整数である。次いで、出力値３７４を（ｎ＋ｓ／２）ビットＱ値３７６および（ｎ＋ｓ−ｓ／２）ビットＰ値３７８に分割する。ｓ／２は上記のように定義する。すべての実際的な目的で、Ｐは、Ｑが抽出された後に残る出力ビットを示す。抽出方法は、出力３７４中のすべてのビットがＰおよびＱ中に割り振られ、かつＰおよびＱの長さが高々１ビット異なることを保証する。
通信手順
第４図に、独立して指定されたセッション・キーを使用して暗号化されたメッセージを国Ｙの受信者１０４に送信したい国Ｘの送信者１０２（第１図）が使用する手順４００を示す。手順４００への入力は、（１）機密キー、（２）回復情報のアプリケーション固有部分、（３）任意選択の機密ランダム・ソルトである。ソルトは、平文のランダムネスを高めるために使用されるランダム値である。ソルトはただ１回使用される。機密ランダム・ソルトは、手順に与えられた場合、ＳＡＬＴ０と呼ばれる。それ以外の場合、ＳＡＬＴ０は、以下で説明するように指定された機密キーから疑似ランダムに導出される。
第４図を参照すると、送信者１０２および受信者１０４はまず、機密セッション・キーＫを確立する（ステップ４０２）。送信者１０２および受信者１０４は、キーＫを確立するために彼らが望むどんなキー配布手順またはキー一致手順でも使用できる。一般に、セッション・キーＫは、送信者１０２が受信者１０４に対するメッセージを暗号化するため、ならびに受信者が送信者からのメッセージを暗号解読するために使用される対称暗号化キーである。公開キーをセッション・キーとして使用する場合、手順は、Ｋ＝（ＰＫａ、ＳＫａ）と定義することによって使用される。ＰＫａは送信者１０２が使用する公開暗号化キーであり、ＳＫａは受信者１０４が使用する対応する機密暗号解読キーである。
次いで、送信者１０２は、機密セッション・キーＫおよびキー反転関数３００（第３Ａ図）を使用して、国Ｘの第１および第２のキー回復エージェント１０８、１１０（送信者のキー回復エージェント）のＰおよびＱの値、ならびに国Ｙの第１および第２のキー回復エージェント１１２、１１４（受信者のキー回復エージェント）のＰおよびＱの値を生成する（ステップ４０４）。この例では国ごとに２つのキー回復エージェントしか示していないが、キー反転関数３００の説明で述べたように任意の数のキー回復エージェントが使用できる。次いで、送信者１０２は、機密セッション・キーＫを使用して、以下で説明するようにして複数のソルト値を生成する（ステップ４０６）。
第６図を参照すると、送信者１０２は、生成されたソルト値をキー回復エージェント１０８〜１１４の公開キーおよびその他の情報と一緒に使用して、国Ｘの暗号化されたＰおよびＱの値６０２、６０４ならびに国Ｙの暗号化されたＰおよびＱの値６０６、６０８を生成する（ステップ４０８）。この情報を使用して、送信者１０２は、暗号化されたＰおよびＱの値６０２〜６０８と回復情報６１０の連結から構成されるセッション・コンテキスト６１２（第６図）を生成する（ステップ４１０）。
第７図を参照すると、送信者１０２は、次いで秘密署名キーを使用してセッション・コンテキスト６１２に対するデジタル署名６１４を生成する（ステップ４１２）。これは、セッション・コンテキスト６１２のハッシュを生成し、送信者の秘密署名キーを使ってこのハッシュを暗号化することによって通常の形で行われる。次いで、セッション・コンテキスト６１２とこのコンテキストに対する署名６１４が連結されて、セッション・ヘッダ６１６を形成する（ステップ４１４）。デジタル署名６１４により、受信者１０４は、送信者の公開検証キーの有効コピーを用いてセッション・コンテキスト６１２を妥当性検査することができる。ただし、デジタル署名６１４はオプションにすぎず、望むならセッション・ヘッダ６１６から省略してもよい。
次に第８図を参照すると、送信者１０２は次いでセッション・キーＫを用いて第１のメッセージ（メッセージ１）を暗号化して、暗号化された第１メッセージ６１８を生成する（ステップ４１６）。最後に、送信者１０２は受信者１０４に、セッション・ヘッダ６１６と暗号化された第１メッセージ６１８から構成されるパケット６２０を送ることができる（ステップ４１８）。
第５図は、送信者１０２からメッセージ・パケット６２０を受け取ったときに受信者１０４が従う手順５００を示すものである。
セッション・ヘッダ６１６がセッション・コンテキスト６１２に対する署名６１４を含んでいる場合、受信者１０４はまず送信者の公開検証キーを用いて署名を妥当性検査する（ステップ５０２）。これは、送信者と同じハッシュ関数を用いてセッション・コンテキスト６１２のハッシュを生成し、送信者の公開検証キーを用いて署名６１６を暗号解読し、その結果が等しいかどうか比較することによって通常の形で行われる。２つの結果が一致しない場合（ステップ５０４）、セッション・コンテキスト６１２と署名６１４のどちらかが伝送中に壊れたことを示し、受信者１０４はそれ以上メッセージを処理せずに終了する（ステップ５１８）。そうでない場合、あるいは署名が使用されない場合は、受信者１０４は次のステップに進む。
署名検査に続いて、受信者１０４は、送信者１０２が実行した諸ステップを繰り返して受信した暗号化されたＰおよびＱ値６０２〜６０８を妥当性検査する。すなわち、受信者１０４は機密セッション・キーＫからＰ、ＱおよびＲ値を生成し（ステップ５０６）、キーＫからソルト値を生成する（ステップ５１０）。ステップ５０６〜５１０は送信者１０２が実行したステップ４０４〜４０８と同じである。次いで受信者１０４はこうして生成した暗号化されたＰおよびＱ値を、送信者１０２から受け取った１組の暗号化されたＰおよびＱ値６０２〜６０８と等しいかどうか比較する。受信者はまた送信者から受け取った回復情報６１０を、受信者が維持する同様の情報と一致するかどうか検査する（ステップ１１０８）。
暗号化されたＰおよびＱ値６０２〜６０８と送信者１０２から受け取った回復情報６０６の妥当性検査がうまくいった場合（ステップ５１４）、受信者１０４は、第１のメッセージを暗号解読するために使用する機密セッション・キーＫをイネーブルする最終ステップに進む（ステップ５１６）。そうでない場合、受信者１０４は、キー回復のために必要な値６０２〜６１０が送信されたことを検証できないので、メッセージをそれ以上処理することなく手順を終了する（５１８）。
上述の手順（第４図〜第５図）では、送信者１０２および受信者１０４が任意のキー移送手順またはキー一致手順を使用して予め機密セッション・キーＫを確立していたと仮定した。別法として、キーＫは、受信者１０４と関係なく送信者１０２が生成し、送信パケット６２０の一部として含めることもできる。次に、この手順でキー確立に伴う変更について説明する。
ここで、機密値が送信者と受信者の間で共用されると仮定する。システムへの入力は、（１）送信者から受信者へのキーの送信に使用すべき受信者の公開キー、および（２）回復情報のアプリケーション固有部分である。この場合、キー回復システムは機密セッション・キーＫおよびランダム機密ＳＡＬＴ０を生成する。
送信者１０２は、受信者１０４の公開キーを使用してセッション・キーＫを暗号化し、セッション・コンテキスト６１２の追加の一部（図示せず）として暗号化されたセッション・キーを含む。セッション・キーＫは次の値として暗号化される。
Ｋ’＝ｅＰＵｂ（Ｈ（Ｔ１）；Ｋ；ＳＡＬＴ０；ＳＡＬＴ）上式で、Ｋ’は暗号化されたセッション・キーである。ＰＵｂは受信者１０４の公開キーである。Ｈ（Ｔ１）、ＫおよびＳＡＬＴ０は前に定義したものである。ＳＡＬＴはＳＡＬＴ０またはＫに相関しない追加の１６０ビット機密ランダム値である。ＳＡＬＴは当事者間で交換されたＫとＳＡＬＴ０の安全保護を保証する。Ｋは、ＰおよびＱキー回復値を暗号化するために使用される暗号化手順（以下で説明する）を使用して暗号化されることが好ましい。
受信者１０４は、署名妥当性検査ステップ（５０４〜５０６）に従ってその秘密暗号解読キーを使用して暗号解読することによってセッション・コンテキスト６１２からセッション・キーを回復する。それ以外の場合、第４図および第５図に示すように同じ手順を使用する。
回復情報
第９図を参照すると、回復情報６１０は、（１）受信者１０４が各キー回復エージェント１０８〜１１４ごとに暗号化されたＰおよびＱの値６０２〜６０８を確認できるように、また（２）キー回復エージェントが暗号解読されたＰおよびＱの値に対して整合性検査を実施できるように提供される。
送信者ＩＤ９０２は、セッション・コンテキスト６１２に対して送信者１０２によって生成された任意選択の署名６１４を確認するために必要な公開キー証明を受信者１０４が得ることを可能にする。受信者ＩＤ９０６は、メッセージ６２０が実際に自身に向けられたものであることを受信者１０４が決定することを可能にする。発信元の国のＩＤ９０４および宛先の国のＩＤ９０８は、等価な暗号化されたＰおよびＱの値を再生し、受信した暗号化されたＰおよびＱの値６０２〜６０８との同一性について比較することによって受信者１０４がセッション・コンテキスト６１２の内容を確認することを可能にする。
送信者のキー回復エージェント・グループ９１０は、送信者の第１のキー回復エージェントＩＤ９１２、送信者の第１のキー回復エージェント・ヘッダ９１４、送信者の第２のキー回復エージェントＩＤ９１６、および送信者の第２のキー回復エージェント・ヘッダ９１８から構成される。受信者のキー回復エージェント・グループ９２０は、受信者の第１のキー回復エージェントＩＤ９２２、受信者の第１のキー回復エージェント・ヘッダ９２４、受信者の第２のキー回復エージェントＩＤ９２６、および受信者の第２のキー回復エージェント・ヘッダ９２８から構成される。
送信者および受信者の第１および第２のキー回復エージェントＩＤ９１２、９１６、９２２、９２６は、真正キー回復エージェントがキー回復手順に従って使用されていることを受信者１０４が確認することを可能にする。キー回復エージェントＩＤはまた、各キー回復エージェントの公開キー証明を得ることができるようにする。キー回復エージェントＩＤはまた、どのキー回復エージェントがユーザのＰおよびＱの値を暗号解読することができるかを法律施行エージェントが知ることを可能にする。各ユーザのデフォルト・キー回復エージェントＩＤをＸ．５０９バージョン３証明の拡張部に含めることもできる。
送信者および受信者の第１および第２のキー回復エージェント・キー・ヘッダ９１４、９１８、９２４、９２８は、キー回復エージェントに属する公開キーに関する情報を含む。第１０図を参照すると、各キー・ヘッダは、暗号化アルゴリズムＩＤ９４６（使用すべき公開キー・アルゴリズムを指定する）、公開キーのビットで表したキー長９４８、およびキーＩＤ９５０を含む。キーＩＤ９５０は、ＰおよびＱの値を暗号化する公開キーを受信者が決定することを可能にする。受信者は、暗号化されたＰおよびＱの値６０２および６０４を確認するためにこれらの公開キーを必要とする。キーＩＤ９５０は、ＰおよびＱの値を暗号化する公開キー、したがってＰおよびＱの値を解読するために必要な秘密キーをキー回復エージェントが決定することを可能にする。
一意のセッションＩＤ９３０は送信者および受信者がセッションを確定することを可能にする。
キーの暗号期間９３２は、キー使用の開始および終了の日時によって指定される。ＰまたはＱの値は、裁判所命令の期間がキーの暗号期間の一部に重ならなければ解放されることはない。キー回復システムは、国の方針決定である比較的短い暗号期間（たとえば１日未満）を守らせる。これは、セッション・コンテキストが動的に確立され、送信者と受信者の間で送信されることを保証するのを助ける。これはまた頻繁なキー交換のためによりよい安全保護を保証する。
生成日時９３４は、セッション・コンテキストが生成された日付および時間（ＵＴＣ符号化）を示す。受信者は、整合性検査の一部として日時９３４を検査する。日時は、ＰまたはＱの値にアクセスするために裁判所命令の期間内に入らなければならない。
セッション・キー・ヘッダ９３６は、セッション暗号化アルゴリズムＩＤ９３８、ビットで表したセッション・キー長９４０、およびセッション・キーＩＤ９４２を含む。セッション・キー長９４０は、ＰまたはＱの値からキーを再計算する必要がある場合に政府によって必要とされる。セッション暗号化アルゴリズムＩＤ９３８は、Ｒを徹底的に計算する必要がある場合に政府によって必要とされる。
暗号アルゴリズムＩＤは、キー回復手順をパラメータ化することを可能にする。すなわち、Ｐ、Ｑ、Ｒのサイズをデータ暗号化に使用される暗号アルゴリズムに依存させることができる。
回復情報６１０は様々な発信源から発生する。したがって、キー・ヘッダ９１４、９１８，９２４、９２８および暗号期間９３２は、以下で説明する方針テーブル１２００（第１２図）に記載され得る。生成日時９３４は暗号システム自体から発生する。キー回復エージェントＩＤ９１２，９１６、９２２、９２６およびハッシュＩＤはアプリケーションから発生するか、または事前に構成することができ、残りのエントリはアプリケーションから発生され得る。
Ｐ値およびＱ値の暗号化
次に、暗号化されたＰおよびＱの値６０２〜６０８を生成する手順（ステップ４０８および５１０）について説明する。
以下では、キーＫによる入力Ｘの暗号化をｅＫ（Ｘ）で示す。「ｅ」は暗号化を示し、ｅＫ（Ｘ）＝Ｙは出力である。キーＫによるＹの暗号解読をｄＫ（Ｙ）で示す。「ｄ」は暗号解読を示す。公開キー暗号法では、公開キーおよび秘密キーの対（ＰＵ、ＰＲ）を使用して暗号化／暗号解読を行う。公開キーＰＵによる入力Ｘの暗号化をｅＰＵ（Ｘ）で示す。秘密キーＰＲによるＹの暗号解読をｄＲＰ（Ｙ）で示す。
暗号化されたＰおよびＱの値６０２〜６０８を次のように定義する。
Px'=ePUx1(H(T1);Px;SALT<for Px>)
Qx'=ePUx2(H(T1);Qx;SALT<for Qx>)
Py'=ePUy1(H(T1);Py;SALT<for Py>)
Qy'=ePUy2(H(T1);Qy;SALT<for Qy>)
上式で、
ＰＵｘ１は国Ｘのキー回復エージェント１の公開キーである。
ＰＵｘ２は国Ｘのキー回復エージェント２の公開キーである。
ＰＵｙ１は国Ｙのキー回復エージェント１の公開キーである。
ＰＵｙ２は国Ｙのキー回復エージェント２の公開キーである。
Ｈ（Ｔ１）は１６０ビットの非機密ハッシュ値である。
Ｔ１は非機密回復情報６１０（第９図）である。
Ｐｘ、Ｑｘは国Ｘの権限を与えられたキー回復エージェントが使用可能なＰ値およびＱ値である。
Ｐｙ、Ｑｙは国Ｙの権限を与えられたキー回復エージェントが使用可能なＰ値およびＱ値である。
Ｐｘ’、Ｑｘ’、Ｐｙ’、Ｑｙ’はＰｘ、Ｑｘ、Ｐｙ、Ｑｙの暗号化バージョンである。
ＳＡＬＴ＜ｆｏｒ  Ｐｘ＞、ＳＡＬＴ＜ｆｏｒ  Ｑｘ＞、ＳＡＬＴ＜ｆｏｒ  Ｐｙ＞、ＳＡＬＴ＜ｆｏｒ  Ｑｙ＞は１６０ビットの機密導出値である。
使用する暗号化手順は、ANSI X9.44RSA Key Transport draft standard、および参照により本明細書の一部となる１９９６年米国カリフォルニア州サンフランシスコのD.B. JohnsonおよびS.M.Matyasの「Enhanced Optical Asymmetric Encryption:Reverse Signatures and ANSI X9.44」、Proceedings of the 1996 RSA Data Security Conferenceに詳述されている拡張最適非対称暗号化（ＥＯＡＥ）手順が好ましい。ただし、他の手順も代わりに使用できる。
Ｈ（Ｔ１）は、公開一方向性ハッシュ関数を使用して回復情報６１０（Ｔ１）から計算したハッシュ値である。Ｈ（Ｔ１）は、Ｔ１の情報に対する「逆署名」の形を与える。逆署名は情報を機密に強く結合する。誰でも逆署名を計算することができるが、暗号化されたブロック内のすべての機密を知っている（したがってそれを公開キーを使用して再生成できる）か、または秘密キーを知っている（したがって機密を直接回復できる）ユーザのみが逆署名を検証できる。逆署名に関するさらなる情報は、上記のD.B. JohnsonおよびS.M.Matyasの論文に見られる。
ＳＡＬＴ０は、暗号化手順への追加の入力として指定されるか、または機密セッション・キーＫから疑似ランダムに生成される１６０ビットの機密ランダム値である。本発明は、送信者および受信者がセッション・キーＫと無関係にＳＡＬＴ０の機密値を確立することを可能にする。たとえば、当事者は、キーＫを生成するために使用されないDiffie-Hellman手順からのビットを使用してＳＡＬＴ０を生成することができる。このような形でＳＡＬＴ０をセッション・キーＫと無関係に生成することは、一種の暗号解読攻撃に対する追加の保護を与えることができる。
ＳＡＬＴ０は機密セッション・キーＫから生成される場合、（Ｋ｜｜Ｈ（Ｔ１）｜｜公開ヘッダ）をＳＨＡ−１でハッシュすることによって生成される。ただし、Ｈ（Ｔ１）は上記のように定義され、公開ヘッダは次のように定義される８バイト構造である。
１バイト識別子：「ソルト０」ＩＤ
７バイト予約済み：０にセットされる
本明細書において、ＳＨＡ−１は暗号的に強いハッシュ・アルゴリズムである安全保護（セキュア）ハッシュ・アルゴリズム（ＳＨＡ−１）をさす。ただし、、ＳＨＡ−１の代わりに任意の適切な強い暗号ハッシュ関数も使用できる。
ＳＡＬＴ０は、追加のソルト値、すなわちＳＡＬＴ＜ｆｏｒ  Ｐｘ＞、ＳＡＬＴ＜ｆｏｒ  Ｑｘ＞、ＳＡＬＴ＜ｆｏｒ  Ｐｙ＞、ＳＡＬＴ＜ｆｏｒ  Ｑｙ＞を生成するための公開一方向性関数への入力として使用される。一方向性関数は、ＳＡＬＴ０からＳＡＬＴ＜ｆｏｒ  Ｐｘ＞、ＳＡＬＴ＜ｆｏｒ  Ｑｘ＞、ＳＡＬＴ＜ｆｏｒ  Ｐｙ＞、ＳＡＬＴ＜ｆｏｒ  Ｑｙ＞を計算することを容易にするが、これらの導出されたソルト値のいずれかからＳＡＬＴ０を生成することは計算上不可能である。
ソルト（ＳＡＬＴ＜ｆｏｒ  Ｐｘ＞、ＳＡＬＴ＜ｆｏｒ  Ｑｘ＞、ＳＡＬＴ＜ｆｏｒ  Ｐｙ＞、ＳＡＬＴ＜ｆｏｒ  Ｑｙ＞）は暗号化されたＰおよびＱの値６０２〜６０８を保護する。ソルト（ＳＡＬＴ＜ｆｏｒ  Ｐｘ＞、ＳＡＬＴ＜ｆｏｒ  Ｑｘ＞、ＳＡＬＴ＜ｆｏｒ  Ｐｙ＞、ＳＡＬＴ＜ｆｏｒ  Ｑｙ＞）は異なった値になるよう特別に構成される。ＳＡＬＴ０が暗号化手順への入力として指定された機密ランダム値である場合、これは、キー回復エージェントに対して暗号化すべきすべてのブロックがＳＡＬＴ０（キーと無関係の機密ランダム１６０ビット値）への依存性を有することを保証する。ＳＡＬＴ０がキーから疑似ランダムに生成される場合、これは、キー回復エージェントに対して暗号化すべきすべてのブロックが疑似ランダムな形でキー全体への依存性を有することを保証する。
Ｈ（Ｔ１）は暗号化されたＰおよびＱの値６０２〜６０８に含まれ、暗号化されたＰまたはＱの値への回復情報６１０の強い結合を与え、それにより暗号化されたＰまたはＱの値が提示された裁判所命令の記述された条件を満足するかどうかを決定する手段をキー回復エージェントに与える。
暗号化されたＰおよびＱの値６０２〜６０８はまた、暗号化された値がＰまたはＱの値であるかどうかを指定するインジケータを含む。
第１１図を参照すると、Ｈ（Ｔ１）、ＰまたはＱの値、インジケータ、およびソルトは、ブロック（１１０２）でフォーマットされ、必要に応じて左側に０ビットを埋め込まれ、好ましくは上記のD.B. Johnson他の論文に記載されている拡張最適非対称暗号化（ＥＯＡＥ）手順を使用して、キー回復エージェントの公開キーで暗号化される。その文献に記載されているように、ＥＯＡＥ手順は、まずフォーマットされたブロック１１０２を複数のマスキング・ラウンド１１０４にかけ（一方の半入力が他方の半入力をマスクするために交互に使用される）、その後マスキング・ラウンドの結果を暗号化する（１１０６）。
暗号化されたＰｘ、Ｑｘ、Ｐｙ、Ｑｙの値中で使用されるランダムに現れるソルトは、それらが正確であることを受信者が検証できるような形で生成される。受信者はキー回復エージェントに属する秘密キーを知らないので、これは、キー回復エージェントの公開キーで平文値を暗号化し、それらを受け取った値と同一性について比較することによって行われる。これは、ＳＡＬＴ０から暗号化されたＰｘ、Ｑｘ、Ｐｙ、Ｑｙの値中のソルトを導出することによって可能になる。
Ｕｖが集合（Ｐｘ、Ｑｘ、Ｐｙ、Ｑｙ）中のＰおよびＱの値のいずれか１つを表すとする。Ｓａｌｔ＜ｆｏｒ  Ｕｖ＞で示されるＵｖの暗号化に使用されるソルト値は、データ（ＳＡＬＴ０｜｜Ｕｖ｜｜キー回復エージェントＩＤ｜｜送信者または受信者のＩＤ｜｜公開ヘッダ）のＳＨＡ−１ハッシュと定義される。送信者のＩＤは、ソルトを送信者のキー回復エージェントのための暗号化に使用すべき場合に使用される。それ以外の場合、受信者のＩＤが使用される。公開ヘッダは次のように定義される８バイト構造である。
１バイト  識別子：「ＳＡＬＴ」ＩＤ（ＳＡＬＴ０を除くすべてのソルトについて）
１バイト  連鎖値：多数のブロックがある場合の暗号化されたブロックの順序を示す０、１など。
１バイト  最後の連鎖：最後の連鎖値の数
５バイト  予約済み：０にセットされる
この手法によれば、暗号化されたＰｘ、Ｑｘ、Ｐｙ、Ｑｙの値の導出された各ソルト値は独立して現れる。不正なキー回復エージェントは他の暗号化されたＰまたはＱの値の安全保護を減じるために導出されたソルト値を使用することができない。権限を与えられた要求者にＰまたはＱの値を供給するために、キー回復エージェントはまた、使用された導出されたソルトを供給することができ、したがって権限を与えられた要求者はキー回復公開キーを使用して、正確な暗号解読がキー回復エージェントによって行われたことを検証することができる。
ＰまたはＱの長さがｍよりも大きい場合（ｍは、意図されたキー回復エージェントの公開キーで暗号化できるＰまたはＱの最大長）、値（ＰまたはＱ）はｍビットのブロックに分割される。最後のブロックは短いブロックである。そのようなブロックが「ｉ」個ある場合、「ｉ」個の異なるソルト値を計算し、それにより異なる（ただし予測できる）ソルト値が暗号化すべき各ｍビット・ブロックごとに計算されることを保証する。たとえば、ｍ＝２５６、Ｐの長さが５１２ビットであると仮定する。その場合、Ｐはサイズ２５６ビットの２つのブロックに分割され、上述のアルゴリズムを使用して２つのソルト値が計算される。第１のソルト値は、連鎖値がゼロ（０）であるヘッダを使用して計算される。第２のソルト値は連鎖値が１であるヘッダを使用して計算される。この場合、２つのヘッダは連鎖値を除いて等しい。「最後の連鎖」は最後の連鎖値の数である。たとえば、連鎖すべきブロックが「ｉ」個ある場合、「最後の連鎖」値はｉ−１である。「最後の連鎖」フィールドは、所与の連鎖のすべての暗号化されたブロックが考慮されることを保証する。
拡張最適非対称暗号化（ＥＯＡＥ）手順
本発明の拡張最適非対称暗号化（ＥＯＡＥ）手順は、（D.B. Johnson他の文献に記載されている）M. BellareおよびP. Rogawayの従来の最適非対称暗号化（ＯＡＥ）手順とは、ＯＡＥの非順応性ビットに代わって制御情報のハッシュが使用される点で異なる。本発明の場合、非順応性ビットはＨ（Ｔ１）、すなわち回復情報（Ｔ１）６１２（第９図）のハッシュと置き換えられる。
ＥＯＡＥの特定の実施態様はまた他の点でＯＡＥと異なる。ＯＡＥでは、まず機密乱数（ＲＮ）を入力Ｘに付加してＸ｜｜ＲＮを形成することによって入力Ｘを処理する。ただし、ＲＮの長さは使用しているハッシュ・アルゴリズムの長さに等しい（たとえばＭＤ５の場合は１２８、ＳＨＡ−１の場合は１６０）。しかしながら、キー回復システムによって暗号化すべきＸの値はすでに、各Ｘ値の右端（最下位）部分として機密ランダム・ソルト値を有している。入力Ｘに追加の機密ランダム値を付ける必要はない。したがって、ＸがＥＯＡＥで処理すべき入力である場合、まずＸをＸ＝Ｘ’｜｜Ｓａｌｔとして書き直す。ただし、Ｘ’はＯＡＥ入力であり、ＳａｌｔはＯＡＥによって生成され、Ｘ’に付加された乱数である。次いで、Ｘ’｜｜ＳａｌｔをＯＡＥで通常の形で処理する（すなわち、Ｘ’をマスクするためのマスキング値を生成するシードとしてＳａｌｔを使用し、マスクされたＸ’をＳＨＡ−１でハッシュして、Ｓａｌｔをマスクするために使用されるハッシュ値を生成する）。ＥＯＡＥおよびＯＡＥ処理のマスキング部分の具体的な詳細は以下のシャフラ関数の説明で示す。
通信シナリオ
以下で説明するように、様々な通信シナリオが考えられる。
多くの場合、モバイル・ユーザは、回復情報をエンドユーザのエージェントだけでなく、ベース（すなわちエアリンクおよびワイヤード・ネットワークを接続するインフラストラクチャ機能）のエージェントにも使用可能にしなければならない。
対称キー暗号法、たとえばKerberosを使用してキー配布を実施するシステムでは、同じ情報がキー配布センター（ＫＤＣ）によって記憶され、与えられる。ＫＤＣはまた暗号化されたＰおよびＱの値を準備する。暗号化されたＰおよびＱの値に対して整合性検査を実施するためにKerberosの特別のキー回復バージョンが必要になる。
マルチキャスティング・シナリオは１つの送信者および多数の受信者を有する。これは、単一のセッションの複製として処理されるか、または受信者の集合として処理される。前者の場合、各受信者は、送信者のキー回復エージェントへの暗号化のコピーおよび自身のエージェントへの暗号化を得る。後者の場合、各受信者は、すべてのＰ、Ｑ暗号化を得、自分自身および送信者の暗号化を検証する。スケーラビリティを援助するために、多数の国にわたるマルチキャスティング用に特別のエージェントを持つオプションもある。
グローバル通信方針テーブル
第１２図を参照すると、本発明のキー回復システムに必要な情報は、グローバル通信方針テーブルと呼ばれるテーブル１２００に記憶される。テーブル１２００は説明のためのものにすぎない。実際の実施態様では、データはおそらく、あるものはキー回復エージェントの公開キーを指定し、あるものは規則を指定する別々のテーブルに適切に記憶される。テーブル１２００は、特定のアルゴリズムおよび異なる国にいるユーザに対してキーのサイズおよびＰ、Ｑ、Ｒをシステムが計算できるようにする情報を含んでいる。テーブル１２００はまた各国ごとに権限を与えられたキー回復エージェントの公開キーを含む。テーブル１２００中の数は、本発明が可能にするフレキシビリティを例示するための例にすぎない。その種類には事実上制限はない。特に、各国は多数のキー回復エージェントを有することができる。
国間通信では、キー回復システムは、受信者の公開キー証明または相当するシステム構成情報から受信者の国のＩＤ９０８（第９図）を決定することができる。送信者の発信元国ＩＤおよび受信者の宛先国ＩＤ、ならびに送信者および受信者が使用すべき意図された暗号化アルゴリズムのアルゴリズムＩＤを使用して、キー回復システムは、（１）送信者および受信者が使用できる最大キー長、（２）送信者と受信者で異なっていてもよい許されるＲの値、（３）キー反転関数に必要な所要のキー回復エージェントＩＤを決定する。次いで、キー回復システムは、この情報をキー反転関数に送る。キー長は、２つのキー長の値の小さい方である。たとえば、国Ｘおよび国Ｙで、ＤＥＳのキー値が６４ビットおよび１２８ビの場合、６４が使用する値である。
他のシステムとの協働性
本発明の「ＰＱＲ」キー回復システムは、それと他の「非ＰＱＲ」システムとの間の制限された協働性を提供する。したがって、送信者１０２は、（１）送信者と受信者がそれぞれＰＱＲシステムを使用する場合、（２）送信者と受信者がそれぞれ非ＰＱＲシステムを使用する場合、または（３）送信者がＰＱＲシステムを使用し、受信者が非ＰＱＲシステムを使用する場合、暗号化されたメッセージを受信者１０４に送信することができる。送信者が非ＰＱＲシステムを使用し、受信者がＰＱＲシステムを使用する場合、送信者は暗号化されたメッセージを受信者に送信することはできない。基本的に、受信者のＰＱＲシステムは、送信者のシステムが有効なＰＱＲ「キー・ブロブ」を生成したことを確認しようと試みる。それができないと、受信者のＰＱＲシステムは、送信者から受け取ったデータを暗号解読するために使用できる形でキーを受信者のアプリケーションに使用可能にしない。
キー回復手順
権限を与えられた法律施行エージェントは、特定の時間期間の間、特定の容疑者の暗号化されたデータにアクセスするための保証または裁判所命令を得る。法律施行エージェントは、セッション・コンテキストを含めて、容疑者に対する暗号化された情報にアクセスする。法律施行エージェントは、ユーザＩＤおよび日時値が有効であること、すなわち令状または裁判所命令で指定されていることを検証することができる。他の公開情報も適宜確認できる。法律施行エージェントは、セッション・コンテキストを令状または裁判所命令とともに適切なキー回復エージェントに与える。
キー回復エージェントは、令状または裁判所命令のすべての要件が満足されたことを保証するために、ユーザＩＤおよび日時を含めて、回復情報を検証する。これは、暗号解読されたＨ（Ｔ１）および受け取った回復情報（Ｔ１）のハッシュの同一性を検査することによって行われる。次いで、キー回復エージェントは、ＰおよびＱの値を回復し、その値および関連するソルトを法律施行エージェントに戻す。キー回復エージェントはまた、暗号解読された情報に署名し、その後それを解放し、それによりキー回復が実施された時間および日付を証明することもある。
法律施行エージェントは、平文値から暗号化されたＰまたはＱを再生成することによってキー回復エージェントが正確なＰまたはＱの値を戻したことを検証することができる。法律施行エージェントは、すべての必要なＰおよびＱの値をアセンブルした後、Ｆ（Ｐ、Ｑ）を再生成するためにキー反転関数を実行し、キーを導出し、情報を暗号解読するためにＲの徹底的なサーチを実施することができる。Ｒの徹底的なサーチが必要になるので、キー回復エージェントが共謀する場合でもキー回復のコストは大きくなる。
暗号システムの実施態様
第１３図に、暗号システム内でのキー回復システムの可能な実施態様１３００を示す。キー回復システム１３００はアプリケーション・プログラミング・インタフェース（ＡＰＩ）を介して呼び出される暗号化／暗号解読機能と対話する。すなわち、キー回復システム１３００によって処理されるセッションまたはファイル・キーは、暗号化／暗号解読機能でのみ使用するために使用可能にされるデータ・キーである。使用可能化プロセスは、キー回復システム１３００を介してのみ許される。
第１３図に、ＰＱＲ生成サービス（１３１０）、ＰＱＲ検証サービス（１３２０）、ＰＱＲ暗号化サービス（１３３０）、ＰＱＲ暗号解読サービス（１３４０）の４つの新しい暗号サービスを示す。ＰＱＲ生成サービス１３１０は入力キーＫから一組のＰ、Ｑ、Ｒの値を生成する。ＰＱＲ生成サービス（１３１０）はまたキーＫをＰＱＲ暗号化サービス１３３０中で動作する形Ｋ’に変換する。ＰＱＲ検証サービス１３２０は一組のＰ、Ｑ、Ｒの値を検証し、検証が成功したとき、キーＫをＰＱＲ暗号解読サービス１３４０中で動作する形Ｋ’に変換する。ＰＱＲ暗号化サービス１３３０およびＰＱＲ暗号解読サービス１３４０は通常の暗号化サービスおよび暗号解読サービスと同じであるが、入力キーがＰＱＲ暗号化サービスおよびＰＱＲ暗号解読サービスによって認識される特別の変換された形になっている必要がある。キーＫは、まず形Ｋ’に変換されなければ、ＰＱＲ暗号化サービス１３３０およびＰＱＲ暗号解読サービス１３４０中で適切に動作しない。
シャフラ関数
第１４図は、キー反転関数３００（第３Ａ図）で使用されるシャフラ関数３０４のハイレベル・ブロック図である。上述のように、シャフラ関数３０４はｎビット入力Ｘを「シャフルされた」ｎビット出力Ｙに変換する。
（偶数個のオクテットを含む）ｎビット入力Ｘは、左半部ＸＬ（１４０２）と右半部ＸＲ（１４０４）に分割される。ＸＬおよびＸＲはそれぞれｎ／２ビットを含む。第１４図に示される特定の例では、ＸＬ（１４０２）とＸＲ（１４０４）のビット長は、使用されるハッシュ関数によって生成されるハッシュ値の長さ（１６０ビット）と同じである。他のビット長を有するＸＬおよびＸＲの手順について以下でさらに説明する。
ハッシュ反復１において、ＸＲ（１４０４）はハッシュされて（１４０６）、１６０ビットのハッシュ値Ｈ（ＸＲ）（１４０８）を生成し、これがＸＬ（１４０２）と排他的論理和（１４１０）をとられて、一回マスクされた出力ｍＸＬ（１４１２）を生成する。ハッシュ反復２において、ｍＸＬ（１４１２）はハッシュされて（１４１４）、１６０ビットのハッシュ値Ｈ（ｍＸＬ）（１４１６）を生成し、これがＸＲ（１４０４）と排他的論理和（１４１８）をとられて、一回マスクされた出力ｍＸＲ（１４２０）を生成する。ハッシュ反復３において、ｍＸＲ（１４２０）はハッシュされて（１４２２）、１６０ビットのハッシュ値Ｈ（ｍＸＲ）（１４２４）を生成し、これが一回マスクされた出力ｍＸＬ（１４１２）と排他的論理和（１４２６）をとられて、二回マスクされた出力ｍｍＸＬ（１４２８）を生成する。出力Ｙは、一回マスクされた出力ｍＸＲ（１４２０）と連結された二回マスクされた出力ｍｍＸＬ（１４２８）から構成され、次式が成り立つ。
Ｙ＝ｍｍＸＬ｜｜ｍＸＲ
第１５図に、元の入力ＸＬ｜｜ＸＲを回復するためにｍｍＸＬ｜｜ｍＸＲを「アンシャフル」する逆シャフラ関数１５００を示す。逆シャフラ関数１５００では、シャフラ関数３０４のハッシュ反復１〜３（１４０６、１４１４、１４２２）はハッシュ反復３、２、１のように逆順に実施される。ハッシュ反復３において、ｍＸＲ（１４２０）はハッシュされて（１５０２）、１６０ビットのハッシュ値Ｈ（ｍＸＲ）（１５０４）を回復し、これがｍｍＸＬ（１４２８）と排他的論理和（１５０６）をとられて、ｍＸＬ（１５０８）を回復する。ハッシュ反復２において、ｍＸＬ（１５０８）はハッシュされて（１５１０）、１６０ビットのハッシュ値Ｈ（ｍＸＬ）（１５１２）を回復し、これがｍＸＲ（１４２０）と排他的論理和（１５１４）をとられて、元の入力ＸＲ（１５１６）を回復する。ハッシュ反復１において、ＸＲ（１５１６）はハッシュされて（１５１８）、１６０ビットのハッシュ値Ｈ（ＸＲ）（１５２０）を回復し、これがｍＸＬ（１５０８）と排他的論理和（１５２２）をとられて、元の入力ＸＬ（１５２４）を回復する。
次に、ＸＬおよびＸＲがそれぞれ１６０ビットから構成されない場合の処理について説明する。
その手順は全体として上述の通りである。（偶数個のオクテットを含む）ｎビット入力Ｘは左半部ＸＬと右半部ＸＲに分割され、ＸＬとＸＲはそれぞれｎ／２ビットを含んでいる。ＸＲを使ってＸＬをマスクして１度マスクされたＸＬが生成され、次いで１度マスクされたＸＬを使ってＸＲがマスクされる。次いでマスクされたＸＲを使って１度マスクされたＸＬをさらにマスクして２度マスクされたＸＬが生成される。しかし、ハッシング・アルゴリズムのブロック・サイズに対処するため、ＸＬとＸＲはそれぞれ連続したチャンクで処理される。
第１６図を参照すると、ＸＲを使ってＸＬをマスクするため、ＸＬはまずｋ個以下のビットからなるｉ個のブロックに分別される。ここでｋはハッシュ・アルゴリズムのブロック・サイズと定義される。たとえば、ＳＨＡ−１がハッシュ・アルゴリズムである場合、ｋ＝１６０となる。ＭＤ５がハッシュ・アルゴリズムである場合、ｋ＝１２８となる。本明細書で別段の記載がない限り、ＳＨＡ−１がシャフラ関数によって使用されるハッシュ・アルゴリズムとなる。ｎがｋの倍数である場合、各ブロックはｋビットを含む。ｎがｋの倍数でない場合、ＸＬは短いブロックｉ（＜ｋビット）１個と任意選択でｋビットのブロック１個以上からなる。短いブロックが存在する場合、それはＸＬの最上位ビットから構築される。
ハッシュされる入力は次のように定義される。
入力＝ＸＲ｜｜公開ヘッダ
上式で、公開ヘッダは次のような１０バイト符号化構造である。
１バイト  識別子      ：「シャフラ」ＩＤ
４ビット  反復        ：１＝最初の反復
４ビット  アルゴリズム：ハッシング・アルゴリズムのＩＤ
４バイト  カウンタ    ：１，２など。カウンタはマスクされるＸＬ中のブロック数と一致する。
４バイト  長さ        ：ビット数で表したキー長（ｋ＝奇数の場合の０の埋め込みが実行されたかどうかも示す）。ヘッダ当たりの最大キー長は２３２ビット。
マスキング動作は次のように実行される。最初カウンタは１に設定され、入力（ＸＲ｜｜公開ヘッダ）がＳＨＡ−１でハッシュされて１６０ビットのハッシュＨ１を生成する。Ｈ１がＸＬからのブロック１とＸＯＲされてマスクされたブロック１（ｍｂｌｏｃｋ１で表す）を生成する。次いで、カウンタが２に増分され、入力（ＸＲ｜｜公開ヘッダ）がＳＨＡ−１でハッシュされて１６０ビットのハッシュＨ２を生成する。Ｈ２がＸＬからのブロック２とＸＯＲされてマスクされたブロック２（ｍｂｌｏｃｋ２で表す）を生成する。
最後のブロック（ブロックｉ）がマスクされるまで、動作はこのように続行する。最後のブロックがｊビット（ｊ＜ｋ）を含む短いブロックである場合は、Ｈｉの最下位ｊビットをブロックｉと排他的ＯＲしてマスクされたブロックｉ（ｍｂｌｏｃｋ  ｉで表す）を生成することによりブロックｉがマスクされる。マスクされたＸＬ（マスクされたブロック１〜ｉの連結からなる）をｍＸＬで表す。
マスクされたＸＬ（ｍＸＬで表す）を使ったＸＲのマスク動作も同様に実行される。ＸＬが分割されたのと同じ方式でＸＲがブロックに分割される。実際のマスク動作も、公開ヘッダ中の反復数が２に設定される（「２回目の反復」を表す）点以外は同じ方式で実施される。この場合、公開ヘッダはｍＸＬに後置される。
ハッシュされる入力は次の通りである。
入力＝ｍＸＬ｜｜公開ヘッダ
上式で、公開ヘッダ中の反復数は「２回目の反復」を表す２に設定される。カウンタがリセットされ、前と同様に１，２などと増分される。マスク動作は、入力をハッシュし、こうして生成されたハッシュ値をＸＲ中のブロックと排他的ＯＲすることからなる。マスクされたＸＲ（マスクされたブロック１からｉの連結からなる）はｍＸＲで表す。
値ｍＸＬは、公開ヘッダ中の反復数が（「３回目の反復」を表す）３に設定される点以外は、ＸＬがＸＲでマスクされたのと同じ方式でｍＸＲでマスクされる。マスクされたｍＸＬをｍｍＸＬで表す。
シャフラの出力はｍｍＸＬ｜｜ｍＸＲである。
公開ヘッダ
本明細書で述べる各公開ヘッダは１バイトの識別子フィールドを有する。識別子フィールドは次のように定義される。
Ｘ’０１’  「ソルト０」
Ｘ’０２’  ソルト０以外の「ソルト」
Ｘ’０３’  「ＰＱキー回復エージェントＩＤ」
Ｘ’０４’  「シャフラ」
雑
各ユーザの公開キー証明はＸ．５０９バージョン３証明規格に準拠し、ｖ３拡張版は、ユーザＩＤ、国ＩＤ、第１キー回復エージェントＩＤ、第２キー回復エージェントＩＤなどキー回復手順に関するある種の必要な情報を保持できるようになることが企図されている。また、送信者および受信者の公開キー証明がキー回復システムに使用可能となることも企図されている。したがって、キー配布を実施する目的でユーザの公開キーが使用可能になるとき、キー回復を実行するために必要な情報も使用可能となり、妥当性検査できる。証明はこの情報を担持する自然な場所と思われる。ユーザのキー回復情報をその公開キー証明に組み入れることにより、ユーザが、たとえばより有利なキー回復オプションのある異なる国ＩＤを請求して、回復システムを悪用する機会が少なくなる。
攻撃
開示されたキー回復システムに対していくつかのタイプの攻撃が考えられる。そのあるものは、不正なキー回復エージェントに基づくものである。
単一のキー回復エージェントが不正者であって、あるユーザに対するＰ値を明らかにした場合、Ｑ値は依然として攻撃者には未知なので問題とはならないはずでである。ＱまたはＲがわからないと攻撃者にとってキー全体を決定するのと同様の問題がある。したがってこの部分的回復の解決策はキー回復エージェントによってキー全体が回復される方式よりも好ましい。
不正なキー回復エージェントは、暗号化されたＰまたはＱに関連するソルト値を使って別の暗号化されたＰまたはＱを分析することができない。各ソルトはＳＡＬＴ０を一方向性関数中を通過させることによって導出されるからである。したがって、各ソルトは独立しているように見える。
（ｎ−ｒ）が小さい値の場合、不正なエージェントがその暗号解読されたＰを見つけるために、Ｆ（Ｐｘ，Ｑｘ）すべてにわたって全順方向シャフリングを試みようとすることがあるかもしれない。この攻撃は、Ｈｘの導出にＦ（Ｐ，Ｑ，Ｒ）を含めることによって阻止される。
他の攻撃は不正ユーザに基づくものである。送信者１０２と受信者１０４が共に不正者である場合、彼らは自分の暗号化方法を使用し、任意のソフトウェア・システム・チェックを迂回することができる。本発明は、両方のユーザが不正である場合の攻撃を防止しようとするものではない。これは事を簡単にするための基本的前提である。
送信者１０２が不正で、キー回復情報６１０（第６図、第９図）を送らない場合、受信者１０４はその妥当性検査を行うことができない。不正な伝送を検出すると、暗号解読プロセスはイネーブルされなくなる。
受信者１０４が不正で、キー回復値を検証しない場合、送信者１０２は依然それらの値を送信しており、必要に応じてそれらにアクセスできるようにしている。
動的で頻繁なセッションは暗号期間を制限し、セッション・コンテキストがアクセスできるようにする助けとなる。
その他の攻撃も考えられる。その一つはいわゆる「スクイズ攻撃」である。Ｙ．フランケル（Frankel）とＭ．ユング（Yung）は「Escrow Encryption Systems Visited:Attacks, Analysis and Designs」、Crypto '95 Conference Proceedings, 1995年8月において、セッション・ヘッダが他のユーザによって識別できるようにキーをセッション間で移送する方法を示している。こうした攻撃を避けるには、キーが悪用されている心配のあるときは、ユーザが活動キー配布方法（たとえばDiffie-Hellmanキー交換に基づくもの）を使用することが推奨される。ユーザは、その交換、セッション情報、当事者のＩＤ、およびセッション中のメッセージに署名してそれらのソースを識別することにより、ユーザ自身が盗聴されているのでない限り、それらが回復エージェントによって開かれないようにすることができる。これにより、メッセージがそのソースと結合され、盗聴されていないソースからのメッセージが接続における最小化の原則（すなわち疑わしい者のみを聴取）によって必要とされるように有効とはみなされないという事実を補償する。アプリケーションによっては、２つの端点の真正さを保証するために、他方当事者がセッション−ヘッダなどに署名することも必要とすべきである。これらの通信アプリケーションは、署名が２人の当事者によって一意に生成されるため保護される。
「偽のエージェント」がエージェントのキーを複製することによってある種の攻撃が可能になる。したがって、エージェントのキーのテーブルは、現実にある国のエージェントに属することが検証されたキーを含むものと仮定する。
また、「非フレッシュ」キーがキー管理手順に挿入される可能性もある。したがって、対話式アプリケーションにおけるセッションＩＤは「フレッシュ情報」または日時から導出することが推奨される。適切な「キー配布」機構を使用すると、それ自体でフレッシュさが確保される。非対話式バージョンでは、セッションＩＤを日時から導出し日時に関係付けることができ、受信者のアプリケーションによって（そのアプリケーションが予想する予想遅延に基づいて）チェックすることができる。
キー回復のための暗号化が、予め確立されたキー・シナリオにおいて攻撃者をどれだけ助けるかに関しては、エージェントのキーの下での公開キー暗号化はすべて異なったものにされ、さらに１６０ビットの乱数値であるＳＡＬＴ０とキーの一部に依存するか、またはキーがプロセスへの唯一の入力である場合はソルトの疑似ランダム導出により「キー全体」に依存するようにされる。これにより、理解の及ぶ限り、エージェントに対する暗号化がキー自体よりも小さな攻撃者「探索スペース」を導出しないことが保証される。この可変性と最適非対称暗号化の使用により、エージェントに対する様々な平文が疑似ランダムに互いに独立となることが保証される。
結論
このキー回復システムの利点についてもう一度述べる。このシステムは多数のアルゴリズムをサポートする。どんなキー配布手順もサポートし、それがない場合は提供する。多数のキー回復エージェントをサポートする。多数の国をサポートし、ある国の特殊な要件を扱うことができる。またこのシステムは自己実施型であり、キー回復エージェントに「使用可能になる」値を受信者が妥当性検査する。輸出可能な暗号化仕様（たとえば４０ビット・キー）を使用する場合とは対照的に、ユーザは、ユーザのシステムが行う仕事が多くなるという犠牲を払って、許可を受けたエンティティ以外のすべてに対してより強い暗号化キーの強度を得る。ユーザは法律に従った最大の強さを得る。法律施行エージェントは、キー回復エージェントが彼等に正確な情報を与えていることを検証することができる。キー回復エージェントが完全には信頼できないという心配を軽減する助けとなる。暗号化されたキーをエスクロー・エージェントに送ることに基づくキー・エスクロー・システムでは、コストはセッション数に比例するが、本システムではコストはアクセス数に比例する。
「使用可能にされる」キーはセッション・レベルのキーである。これにより、区画化および適切なアクセスが可能となる。区画化とは、キーの自然な時間的制限があり、それが許可されたキー回復の時間枠と密接に対応するという意味である。適切なアクセスとは、より永続的なキーや別のユーザ用のキーではなく、暗号化されたデータを明らかにするのに必要なキーが回復されるという意味である。一方、公開キー・アルゴリズムの秘密キーを回復するというのは、他者に送ったメッセージではなく他者から受け取った暗号化メッセージへのアクセスを可能にするので、よい考えではない。また適切な区画化を実施するために、こうした通常は長い寿命のキーを頻繁にロールオーバーすることになる。このテーマに関するさらに詳しい情報は、参照により本明細書に合体する前掲のフランケルとユングの刊行物に出ている。
本発明の様々な修正例は当業者には明らかであろう。本発明は、ハードウェアとしても、ソフトウェアとしても、あるいは両者の組合せとしても実施できる。使用するシャフル手順、ハッシュ手順および暗号化手順は上記のものと異なるものでもよい。追加のストリングや定数を含む修正例も可能である。当業者にはさらに他の修正例も思い浮かぶことであろう。
【図１】
0003872107.tif 000002
【図２】
0003872107.tif 000003
【図３Ａ】
0003872107.tif 000004
【図３Ｂ】
0003872107.tif 000005
【図６】
0003872107.tif 000006
【図７】
0003872107.tif 000007
【図８】
0003872107.tif 000008
【図４】
0003872107.tif 000009
【図５】
0003872107.tif 000010
【図９】
0003872107.tif 000011
【図１０】
0003872107.tif 000012
【図１１】
0003872107.tif 000013
【図１２】
0003872107.tif 000014
【図１３】
0003872107.tif 000015
【図１４】
0003872107.tif 000016
【図１５】
0003872107.tif 000017
【図１６】
0003872107.tif 000018