JP2000502553A - 内在的署名を用いた鍵一致及び輸送プロトコル - Google Patents

Abstract

(57)【要約】 １対の通信者の間の鍵確立プロトコルは、それぞれの通信者によるそれぞれの署名の生成を含む。署名は、当該通信者にとって秘密である情報と公開されている情報とから導かれる。署名を交換した後で、交換メッセージの完全性（integrity）は、署名に含まれる公開情報を抽出し、その公開情報を、当該署名を生成するのに用いられた情報と比較することによって検証される。次に、共通のセッション鍵が通信者それぞれの公開及び秘密情報から生成される。

Description

【発明の詳細な説明】 内在的署名を用いた鍵一致及び輸送プロトコル 本発明は、暗号鍵の転送及び認証のための鍵一致（key agreement）プロトコ ルに関する。 情報の交換の際にプライバシを維持するために、データを鍵を用いて暗号化す ることが、広く知られている。この鍵は、通信者がメッセージを暗号化及び復号 化できるが介入者にはメッセージの内容を判断できないように、選択されなけれ ばならない。 秘密鍵暗号プロトコルでは、通信者は、彼らにとって秘密である共通鍵を共有 （share）する。このためには、この鍵が通信者の間で一致しており、この鍵の 秘密性を維持するために条項（provision）が作成され、基礎となる安全性が万 一危険にさらされた場合には、鍵の交換がなされることが要求される。 公開鍵暗号プロトコルは、１９７６年にDiffie-Hellmanによって最初に提案さ れ、すべての潜在的な通信者に利用可能とされている公開鍵と、意図された受信 者にだけ知られている秘密鍵（private key）とを用いる。公開鍵と秘密鍵とは 、受信者の公開鍵を用いて暗号化されたメッセージは、秘密鍵を用いて容易に復 号化できるが、秘密鍵は、平文（plaintext）、暗号文（ciphertext）及び公開 鍵の知識からは導くことはできないような、相互関係になっている。 鍵の確立（establishment）は、二人以上の当事者が、セッション（session） 鍵と称される、共有される秘密鍵（secret key）を確立するプロセスである。セ ッション鍵は、プライバシなどの何らかの暗号上の目的を達成するために、後で 用いられる。鍵一致プロトコルには、２つの種類が存在する。すなわち、鍵が第 １の当事者によって作成され、第２の当事者に安全に送信されるという鍵輸送（ transport）プロトコルと、両方の当事者が、共有される秘密鍵を共同して確立 する情報を出 し合う鍵一致プロトコルと、である。当事者の間で必要となるメッセージ交換の 数は、パス数（number of passes）と称される。鍵確立プロトコルは、ある当事 者が、特別に識別された第２の当事者以外のどの当事者もセッション鍵の値を知 ることを許されないことが保証されている場合に、「内在的」（implicit）鍵認 証（又は、単に、鍵認証）を提供すると称される。内在的鍵認証の性質は、第２ の当事者が実際のセッション鍵を有していることを必ずしも意味しない。次に、 鍵確立プロトコルは、ある当事者が、特別に識別された第２の当事者が特定のセ ッション鍵を実際に所持していることを保証されている場合には、鍵確認（conf irmation）を提供すると称される。プロトコルに関係する両方の当事者に認証が 提供される場合には、鍵認証は、相互的（mutual）と称され、一人の当事者にだ け提供される場合には、認証は、一方的（unilateral）と称される。 内在的な鍵認証を提供すると主張する提案は、これまでに、いくつかなされて いる。 例としては、鍵一致に関する、Nyberg-Rueppelによる１パス（one-pass）プロ トコル、 Matsumoto-Takashima-Imai(MTI)及びGoss and Yacobiによる２パス・ プロトコルがある。 従来の提案は、共通鍵を確立するための通信者の間の送信が安全であり、侵入 者がセッション鍵をリトリーブし暗号文を復号化することはできないことを保証 している。このようにして、資金の移動などの注意を要するトランザクションに 対する安全性が提供されている。 例えば、MTI/AO鍵一致プロトコルでは、二人の通信者に知られている、共有さ れる秘密鍵を、次のようにして確立している。 １．当初の、一時的な（one-time）セットアップの間に、鍵の発生と公開とが、 適切なシステム・プライム（system prime）ｐと生成元（generator）α∈Ｚ^* _p とを真正であることが補償されるように、選択され公開される。通信者Ａは、長 期の秘密鍵として１＜ａ＜ｐ−１であるランダムな整数ａを選択し、長期の公開 鍵ｚ_A＝α^aｍｏｄｐを計算する。Ｂも、同 様のｂとｚ_Bとを生成する。ＡとＢとは、相互の長期公開鍵の認証されたコピー へのアクセスを有することになる。 ２．このプロトコルは、次のメッセージの交換を要求する。すなわち、 ＡからＢ：α^x ｍｏｄｐ （１） ＢからＡ：α^y ｍｏｄｐ （２） ｘ及びｙの値は、その送信の間は安全に保たれるが、その理由は、ｐが十分に 大きくとられていれば、αの値と指数化とが知られているとしても、指数を決定 するのは実際的ではないからである。 ３．このプロトコルを実現するには、次のステップが、共有されている鍵が要求 される度に実行される。 （ａ）Ａは、１≦ｘ≦ｐ−２であるランダムな整数ｘを選び、Ｂに向けて、メッ セージ（１）、すなわち、α^xｍｏｄｐを送る。 （ｂ）Ｂは、１≦ｙ≦ｐ−２であるランダムな整数ｙを選び、Ａに向けて、メッ セージ（２）、すなわち、α^yｍｏｄｐを送る。 （ｃ）Ａは、鍵Ｋ＝（α^y）^aｚ_B ^xｍｏｄｐを計算する。 （ｄ）Ｂは、鍵Ｋ＝（α^x）^bｚ_A ^yｍｏｄｐを計算する。 （ｅ）両者は、鍵Ｋ＝α^bx+ayを共有する。 鍵Ｋを計算するためには、Ａは、自分の秘密鍵ａとランダムな整数ｘとを使わ なければならない。これらは、共に、Ａ本人だけに知られているものである。同 様にして、Ｂは、セッション鍵Ｋを計算するためには、自分の秘密鍵ｂとランダ ムな整数ｙとを使わなければならない。秘密鍵ａ及びｂが、危険にさらされてい ないと仮定すると、侵入者は、他方の通信者と同一のセッション鍵を生成するこ とはできない。従って、任意の暗文は、どちらの通信者にも復号化が不可能であ る。 従って、このプロトコル及び関連するプロトコルは、鍵確立には十分なもので あると考えられてきたし、従来型の盗聴や、中間者（man-in-the-middle）によ る攻撃に対して抵抗できると考えられてきた。 状況によっては、相手方が、一方の通信者を他方の通信者であるとミスリード するのが効果的である。 そのような攻撃では、アクティブな相手方、すなわち、侵入者Ｅは、ＡとＢと の間で交換されるメッセージを修正し、その結果として、Ｂは、Ｅと鍵Ｋを共有 していると信じ、他方で、Ａは、同じ鍵をＢと共有していると信じることになる 。ＥがＫの値を知らない場合であっても、通信者の識別（ＩＤ）に関する偽の情 報が、有用となる。 そのような攻撃が成功するであろう実際的なシナリオは、次のようなものであ る。Ｂは、銀行の支店であり、Ａは、口座保持者であると仮定する。銀行の本部 によって証明書が発行され、その証明書の中には、保持者の口座情報が書かれて いる。資金の電子的支払い（デポジット）のためのプロトコルは、相互認証され た鍵一致を介して、銀行の支店との鍵の交換であると仮定する。Ｂがいったん送 信者を認証すると、暗号化された資金がその証明書の口座番号に払い込まれる。 それ以上の認証が暗号化された支払いメッセージにおいてなされない場合（これ は、帯域幅を節約するためになされるかもしれない）には、支払いは、Ｅの口座 になされる。 本発明の目的は、上述の短所が回避される又は解消されるようなプロトコルを 提供することである。 従って、本発明によると、１対の通信者Ａ及びＢが相互に情報を交換すること を認証する方法であって、前記通信者は、それぞれが、秘密鍵ａ及びｂと、生成 元αと前記秘密鍵ａ及びｂのそれぞれとから導かれた公開鍵ｐ_A及びｐ_Bと、を有 している方法が提供される。この方法は、 ｉ）前記通信者の第１の者Ａが、第１のランダムな整数ｘを選択し、前記生成 元を含む関数ｆ（α）のｇ^(x)をベキとする指数関数を作ることにより、第１の 指数関数ｆ（α）^g(x)を提供するステップと、 ｉｉ）前記第１の通信者Ａが、前記ランダムな整数ｘと前記指数関数ｆ（α）^g(x) とから第１の署名ｓ_Aを生成するステップと、 ｉｉｉ）前記第１の通信者Ａが、第２の通信者Ｂに向けて、前記第１の指数関 数ｆ（α）^g(x)と署名ｓ_Aとを含むメッセージを送るステップと、 ｉｖ）前記通信者Ｂが、第２のランダムな整数ｙを選択し、前記生成 元を含む関数ｆ’（α）のｇ^(y)をベキとする指数関数を作ることにより、第２ の指数関数ｆ’（α）^g(y)と、前記第２の整数ｙと前記第２の指数関数ｆ（α）^g(x) とから得られるｓ_Bとを提供するステップと、 ｖ）前記第２の通信者Ｂが、第１の通信者Ａに向けて、前記第２の指数関数ｆ ’（α）^g(y)と前記署名ｓ_Bとを含むメッセージを送るステップと、 ｖｉ）前記通信者のそれぞれが、受け取ったメッセージの中の前記署名と前記 指数関数とから、前記指数関数と等しい値を計算し、前記計算された値と前記送 信された値とを比較することによって、自分たちが受け取ったメッセージの真正 を検証するステップと、 ｖｉｉ）前記通信者Ａ及びＢのそれぞれが、前記他方の通信者によって彼ら自 身にとって秘密である前記ランダムな整数を用いて、公開された情報を指数化す ることによって、セッション鍵を構成するステップと、を含む。 従って、侵入者Ｅが自らの公開鍵ｐ_E＝α^acをメッセージの一部として送信の 中に入れることはできるが、Ｂは、メッセージを認証する際には、ｐ_Aではなく ｐ_Eを用いることになる。従って、指数関数の計算され送信された値は、対応し ない。 本発明の実施例を次の添付した図面を参照することによって、これから説明す ることにする。 図１は、データ通信システムの概略図である。 従って、図１を参照すると、通信者Ａ及び通信者Ｂとして表される１対の通信 者１０、１２が、通信チャネル１４上で情報を交換する。暗号ユニット１６、１ ８が、通信者１０、１２とチャネル１４とのそれぞれの間に配置されている。鍵 ２０は、暗号ユニット１６、１８のそれぞれに関連し、それぞれのユニット１６ 、１８とそれぞれの通信者１０、１２との間で運ばれる平文を、チャネル１４上 で運ばれる暗文に変換する。 動作においては、Ａの通信者１０によって生成されるメッセージは、ユニット １６によって、鍵２０を用いて暗号化され、チャネル１４上の 暗文として、ユニット１８まで送信される。 鍵２０は、ユニット１８において暗文に作用して、Ｂの通信者１２のために平 文のメッセージを生成する。鍵２０が対応する場合には、通信者１２によって受 け取られたメッセージは、通信者１０によって送られたものである。 図１に示されたシステムが動作するためには、鍵２０が同一であり、従って、 公開的な態様での情報の移動を可能にする鍵一致（agreement）プロトコルが確 立されていることが必要である。そのような鍵の生成には多数のプロトコルが利 用可能であり、また、Diffie-Hellman鍵交換の変形も存在する。その目的は、当 事者Ａ及びＢが秘密セッション鍵Ｋを確立することである。 これらのプロトコルのためのシステム・パラメータは、素数ｐと乗法群Ｚ^* _pの 生成元αとである。通信者Ａは、秘密鍵ａと、公開鍵ｐ_A＝α^aとを有する。通信 者Ｂは、秘密鍵ｂと、公開鍵ｐ_B＝α^bとを有する。以下で例を挙げるプロトコル では、ｔｅｘｔ_Aは、当事者Ａを識別する情報のストリングを意味する。他方の 当事者Ｂが通信者Ａの公開鍵の真正のコピーを有しており、更に、ｔｅｘｔ_Aが Ａの信用のおけるセンターによって発行された公開鍵証明書を含む場合には、通 信者Ｂは、その信用のおけるセンターの公開鍵の真正のコピーを用いて、通信者 Ａの証明書を検証でき、従って、通信者Ａの公開鍵の真正のコピーを得ることが できる。 以下のそれぞれの例では、侵入者Ｅは、ＡからのメッセージがＥ自身から生じ たものとして識別されることを望んでいると仮定する。これを達成するには、Ｅ は、１≦ｅ≦ｐ−２であるランダムな整数ｅを選択し、ｐ_E＝（ｐ_A）ｅ＝α^ae ｍｏｄｐを計算し、これがＥ自身の公開鍵であることを証明させる。Ｅは、ｅを 知ってはいるが、指数ａｅは知らない。ｔｅｘｔＡをｔｅｘｔＥによって代替す ることによって、通信者Ｂは、メッセージがＡからではなくＥからのものである と考え、Ｅの公開鍵を用いてセッション鍵Ｋを生成する。Ｅはまた、Ｂからのメ ッセージ を中間奪取（インターセプト）し、その秘密のランダムな整数ｅを用いて、その 内容を修正する。Ａは、次に、その情報を用いて、ＡがＢと通信できるようにす る同じセッション鍵を生成する。 侵入者ＥがＢに、ＢはＥと通信しているということを信じさせようとしている のを妨害するには、次のプロトコルが採用される。 このプロトコルの目的は、当事者Ａ及びＢがセッション鍵Ｋを確立することで ある。ここで挙げたプロトコルは、役割対称的（role-symmetric）であり、対話 的（interactive）ではない。 このプロトコルのためのシステム・パラメータは、素数ｐと乗法群Ｚ^* _pの生成 元αとである。通信者Ａは、秘密鍵ａと、公開鍵ｐ_A＝α^aとを有する。通信者Ｂ は、秘密鍵ｂと、公開鍵ｐ_B＝α^bとを有する。 第１のプロトコル １．Ａは、１≦ｘ≦ｐ−２であるランダムな整数ｘを選び、ｒ_A＝α^xと、署名ｓ_A ＝ｘ−ｒ_Aａα^aｍｏｄ（ｐ−１）と、を計算する。Ａは、Ｂに向けて、｛ｒ_A， ｓ_A，ｔｅｘｔ_A｝を送る。 ２．Ｂは、１≦ｙ≦ｐ−２であるランダムな整数ｙを選び、ｒ_B＝α^yと、署名ｓ_B ＝ｙ−ｒ_Bｂα^bｍｏｄ（ｐ−１）と、を計算する。Ａは、Ｂに向けて、｛ｒ_B， ｓ_B，ｔｅｘｔ_B｝を送る。 ３．Ａは、α^sB（ｐ_B）^{rB αb}を計算し、これが、ｒ_Bに等しいことを検証する。 Ａは、次に、セッション鍵Ｋ＝（ｒ_B）^x＝α^xyを計算する。 ４．Ｂは、α^sA（ｐ_A）^{rA αa}を計算し、これが、ｒ_Aに等しいことを検証する。 Ｂは、次に、セッション鍵Ｋ＝（ｒ_A）^y＝α^xyを計算する。 Ｅが、ｔｅｘｔ_Aをｔｅｘｔ_Bに交換する場合には、Ｂは、ｒ_Aの送信された値 には対応しないα^sA（ｐ_E）^{rA αa}を計算する。Ｂは、従って、侵入者Ｅに関する 警告を受け、別のセッション鍵を開始することになる。 第１のプロトコルの短所は、完全な前方向の秘密性（守秘性）（perfect forw ard secrecy）が得られないことである。すなわち、相手側が当事者Ａの長期の 秘密鍵ａを知る場合には、この相手側は、Ａの過去のセッション鍵すべてを導き 出せることになる。完全な前方向の秘密性 は、プロトコル１を次のようにして修正することによって、達成される。 修正された第１のプロトコル ステップ１では、Ａはまた、α^x1をＢに送る。ここで、ｘ₁は、Ａによって生 成された第２のランダムな整数である。同様にして、上述のステップ２では、 Ｂはまた、α^y1をＡに送る。ここで、ｙ₁は、ランダムな整数である。Ａ及びＢ は、鍵Ｋ＝α^xy＋α^x1y1を計算する。 第１のプロトコルの別の短所は、相手側がＡの秘密のランダムな整数ｘを知る 場合には、この相手側は、当事者Ａの長期の秘密鍵を、方程式ｓ_A＝ｘ−ｒ_Aａα^a ｍｏｄ（ｐ−１）から求めることができる点である。このプロトコルのうまく 設計された実現例では、秘密の整数の開示は回避されるので、この短所は、基本 的に理論的性格を有するものである。 第２のプロトコル 次に述べる第２のプロトコルは、これら２つの短所を解決する。 １．Ａは、１≦ｘ≦ｐ−２であるランダムな整数ｘを選び、（ｐ_B）^xと、α^xと 署名ｓ_A＝ｘ＋ａα^a（ｐ_B）^xｍｏｄ（ｐ−１）と、を計算する。Ａは、Ｂに向け て、｛α^x，ｓ_A，ｔｅｘｔ_A｝を送る。 ２．Ｂは、１≦ｙ≦ｐ−２であるランダムな整数ｙを選び、（ｐ_A）^yと、α^yと 署名ｓ_B＝ｙ＋ｂα^b（ｐ_A）^yｍｏｄ（ｐ−１）と、を計算する。Ｂは、Ａに向け て、｛α^y，ｓ_B，ｔｅｘｔ_B｝を送る。 ３．Ａは、（α^y）^aを計算して、α^SB（ｐ_B）^{- αbαay}＝α^yであることを検証す る。Ａは、次に、セッション鍵Ｋ＝α^ay（ｐ_B）^xを計算する。 ４．Ｂは、（α^x）^bを計算して、α^SA（ｐ_A）^{- αaαbx}＝α^xであることを検証す る。Ａは、次に、セッション鍵Ｋ＝α^by（ｐ_A）^yを計算する。 第２のプロトコルが第１のプロトコルとの比較で優れているのは、それが、完 全な前方向の秘密性（forward secrecy）を提供するからである。秘密であるラ ンダムな整数ｘの開示によって、相手側が秘密鍵ａを知ることができる のではあるが、これは実際上は問題ではない。なぜならば、Ａは、自分がこのプ ロトコルのステップ１においてｘを用いた直後に、ｘを廃棄することができるか らである。 ＡがＢの公開鍵の認証されたコピーを有していない場合には、Ｂは、自らの鍵 の真正（certified）なコピーを、プロトコルの開始時に、Ａに送信しなければ ならない。この場合には、第２のプロトコルは、３パス・プロトコルである。 量Ｓ_Aは、値α^xに対して、Ａの署名として機能する。この署名は、当事者Ｂだ けに確認が可能であるという新規な性質を有している。このアイデアは、ElGama lライクな署名方式のすべてに一般化できる。 上述の第１及び第２のプロトコルは、帯域幅の要件と、鍵一致の計算上の効率 とを向上させるように修正が可能である。修正されたプロトコルは、次に、プロ トコル１’及びプロトコル２’として、示してある。それぞれの場合に、Ａ及び Ｂは、共通鍵α^SASBを共有している。 プロトコル１’ １．Ａは、１≦ｘ≦ｐ−２であるランダムな整数ｘを選び、ｒ_A＝α^aと、ｓ_A＝ ｘ＋ｒ_Aａα^aｍｏｄ（ｐ−１）と、を計算する。Ａは、Ｂに向けて、｛ｒ_A，ｔ ｅｘｔ_A｝を送る。 ２．Ｂは、１≦ｙ≦ｐ−２であるランダムな整数ｙを選び、ｒ_B＝α^yと、ｓ_B＝ ｙ＋ｒ_Bｂα^bｍｏｄ（ｐ−１）と、を計算する。Ａは、Ｂに向けて、｛ｒ_B，ｔ ｅｘｔ_B｝を送る。 ３．Ａは、α^SASBに等しいＫ＝（ｒ_B（ｐ_B）^{rB αb}）^SAを計算する。 ４．Ｂは、α^SASBに等しいＫ＝（ｒ_A（ｐ_A）^{rA αa}）^SBを計算する。 このようにして、Ａ及びＢは、共通鍵を共有するが、署名ｓＡ及びｓＢは、送 信される必要がないことに注意すべきである。 プロトコル２’ １．Ａは、１≦ｘ≦ｐ−２であるランダムな整数ｘを選び、（ｐ_B）^xと、α^xと 署名ｓ_A＝ｘ＋ａ（ｐ_B）^xｍｏｄ（ｐ−１）と、を計算する。Ａは、Ｂに向けて 、｛α^x，ｔｅｘｔ_A｝を送る。 ２．Ｂは、１≦ｙ≦ｐ−２であるランダムな整数ｙを選び、（ｐ_A）^yと、α^yと 署名ｓ_B＝ｙ＋ｂ（ｐ_A）^yｍｏｄ（ｐ−１）と、を計算する。Ｂは、Ａに向けて 、｛α^y，ｔｅｘｔ_B｝を送る。 ３．Ａは、（α^y）^aと、Ｋ＝（α^y（ｐ_B）^αbαay）^SAを、すなわち、α^SASBを 計算する。 ４．Ｂは、（α^x）^bと、Ｋ＝（α^x（ｐ_A）^αaαbx）^SBを、すなわち、α^SASBを 計算する。 従って、やはり、ｓＡ及びｓＢの送信が回避された。 Ａ及びＢがセッション鍵Ｋを確立するために、別のプロトコルが利用可能であ る。 第３のプロトコル このプロトコルに対するシステム・パラメータは、乗法群Ｚ^* _pの素数ｐと生成 元αである。ユーザＡは、秘密鍵ａと公開鍵ｐ_A＝α^aとを有している。ユーザＢ は、秘密鍵ｂと公開鍵ｐ_B＝α^bとを有している。 １．Ａは、１≦ｘ，ｘ₁≦ｐ−２である２つのランダムな整数ｘ，ｘ₁を選び、ｒ_x1 ＝α^x1と、ｒ_A＝α^xと、（ｒ^A）^rx1とを計算し、更に、署名ｓ_A＝ｘｒ_x1−（ ｒ_A）^rx1ａα^aｍｏｄ（ｐ−１）を計算する。Ａは、Ｂに向けて、｛ｒ_A，ｓ_A， α^x1，ｔｅｘｔ_A｝を送る。 ２．Ｂは、１≦ｙ，ｙ₁≦ｐ−２である２つのランダムな整数ｙ，ｙ₁を選び、ｒ_y1 ＝α^y1と、ｒ_B＝α^yと、（ｒ^B）^ry1とを計算し、更に、署名ｓ_B＝ｙｒ_y1−（ ｒ_B）^ry1ｂ ｍｏｄ（ｐ−１）を計算する。Ｂは、Ａに向けて、｛ｒ_B，ｓ_B，α^y1 ，ｔｅｘｔ_B｝を送る。 ３．Ａは、α^SB（ｐ_B）^(rB)ry1を計算し、これが、（ｒ_B）^ry1に等しいことを確 認する。Ａは、セッション鍵Ｋ＝（α^y1）^x1＝α^x1y1を計算する。 ４．Ｂは、α^SA（ｐ_A）^(rA)rx1を計算し、これが、（ｒ_A）^rx1に等しいことを確 認する。Ｂは、セッション鍵Ｋ＝（α^x1）^y1＝α^x1y1を計算する。 これらのプロトコルでは、（ｒ_A，ｓ_A）は、Ａだけがメッセージｒ_{x 1} に署名できるという性質を有するｒ_x1の署名であると考えることができる。 鍵輸送プロトコル 上述のプロトコルによれば、セッション鍵の確立と認証とが可能になる。Ａが セッション鍵を当事者Ｂに輸送（transport）することを可能にするプロトコル を確立することが望まれる。そのようなプロトコルを次に述べる。 １．Ａは、１≦ｘ≦ｐ−２であるランダムな整数ｘを選び、ｒ_A＝α^xと、署名ｓ_A ＝ｘ−ｒ_Aａα^aｍｏｄ（ｐ−１）と、を計算する。Ａは、Ｂに向けて、｛ｒ_A， ｓ_A，ｔｅｘｔ_A｝を送る。 ２．Ｂは、α^SA（ｐ_A）^{rA αa}を計算し、この量が、ｒ_Aに等しいことを検証する 。Ｂは、次に、セッション鍵Ｋ＝（ｒ_A）^bを計算する。 修正された鍵輸送プロトコル 上述のプロトコルは、署名ｓＡを送信する必要をなくすことによって、帯域幅 を減少させるように修正が可能である。 １．Ａは、１≦ｘ≦ｐ−２であるランダムな整数ｘを選び、ｒ_A＝α^xと、署名ｓ_A ＝ｘ−ｒ_Aａα^a ｍｏｄ（ｐ−１）と、を計算する。Ａは、更に、Ｋ＝（ｐ^B）^{S A} を計算して、Ｂに向けて、｛ｒ_A，ｔｅｘｔ_A｝を送る。 ２．Ｂは、α^SA（ｐ_A）^{rA αa}を計算し、この量が、ｒ_Aに等しいことを検証する 。Ｂは、次に、セッション鍵Ｋ＝（α^x（ｐ_A）^{-rA αa}）^b＝α^bSAを計算する。 すべての１パス鍵輸送プロトコルは、次に述べるリプレイの問題を有する。１ パス鍵輸送プロトコルを用いてセッション鍵ＫをＡからＢへ、このセッション鍵 を用いて暗号化された何らかのテキストと共に送信することを考える。Ｅが、Ａ からＢへの送信を記録すると仮定する。もし、Ｅが、後に、Ｂの復号化装置への アクセス（ただし、Ｂの秘密鍵など、その装置の内部的な内容へのアクセスでは ない）を、その装置への送信をリプレイすることによって得ることになる場合に は、Ｅは、元のテキ ストを回復することができる。この状況では、Ｅは、セッション鍵を知らない。 このリプレイによるアタックは、タイムスタンプの使用などの、通常の方法に よって失敗させることができる。しかし、Ｂの計算資源が限定されていて、それ ぞれのセッションの開始時に、Ｂがランダムなビット・ストリングｋをＡに送信 する方がより適切であるようなこともあり得る。テキストを暗号化するのに用い られるセッション鍵は、その場合には、ｋ＋ｋ、すなわち、ｋとｋとのＸＯＲを 計算したものとなる。 署名（signing）方程式ｓ_A＝ｘ−ｒ_Aａα^aと、プロトコル２における鍵輸送プ ロトコルｒ_A＝α^xbとは、いくつかの変形例で代替することができる。いくつか 例を挙げると、次の通りである。 ｒ_A＝ｓ_Aｘ＋ｚ ｓ_A＝ｘα^a＋ａｒ_A ｓ_A＝ｘｒ_A＋Ａα^a １＝ａｒ_A＋ｘｓ_A 既に述べたプロトコルは、すべて、乗法群Ｚ^* _pの設定において、説明された。 しかし、これらのプロトコルは、離散対数問題が困難を生じさせるように見える 任意の有限群において機能するように容易に修正することができる。適切な選択 肢としては、有限体の乗法群（特に、有限体ＧＦ（２ⁿ））、位数（order）ｑの Ｚ^* _pの部分群、有限体上で定義される楕円曲線上の点から成る群などがある。そ れぞれの場合に、適切な生成元（generator）αを用いて公開鍵を定義する。 上述したプロトコルは、また、直接的な方法で修正して、それぞれのユーザが 自分自身のシステム・パラメータｐ及びα（又は、Ｚ^* _p以外の群が用いられる場 合には、類似のパラメータ）を選択できるような状況を扱えるようにできる。 上述のプロトコルでは、一般形式ｓ_A＝ｘ＋ｒ_a・ａ・α^aの署名成分が用いら れていた。これらのプロトコルは、安全性を損ねることなく、より単純な一般形 式ｓ_A＝ｘ＋ｒ_a・ａの署名成分を用いるように修正が 可能である。 これらのプロトコルの例を、同じ記号（notation）を用いて以下に与えるが、 望むのであれば、別の記号を用いてこれらのプロトコルを表現することができる ことを理解すべきである。 プロトコル１’’ このプロトコルは、乗法群Ｚ^* _pにおける次の記号を用いて説明される。 ｐは、素数である。 αは、Ｚ^* _pの生成元である。 ａ及びｂは、当事者Ａ及びＢのそれぞれの長期的な秘密鍵である。 α^a ｍｏｄ ｐは、当事者Ａの長期的な秘密鍵である。 α^b ｍｏｄ ｐは、当事者Ｂの長期的な秘密鍵である。 ｘは、Ａによって短期の秘密鍵として選択されるランダムな整数である。 ｒ_a＝α^x ｍｏｄ ｐは、当事者Ａの短期の公開鍵である。 ｙは、Ｂによって短期の秘密鍵として選択されるランダムな整数である。 ｒ_b＝α^y ｍｏｄ ｐは、当事者Ａの短期の公開鍵である。 ｒ_aは、ｒ_aから導かれる整数である。 ｒ_bは、ｒ_bから導かれる整数である。 プロトコルを実現するには、次のようにする。 １．Ａは、ｒ_aをＢに送る。 ２．Ｂは、ｒ_bをＡに送る。 ３．Ａは、ｓ_A＝ｘ＋ｒ_a・ａｍｏｄ（ｐ−１）を計算する。 ４．Ａは、セッション鍵Ｋ＝（α^y（α^b）^rb）^sAｍｏｄｐを計算する。 ５．Ｂは、ｓ_B＝ｙ＋ｒ_b・ｂｍｏｄ（ｐ−１）を計算する。 ６．Ｂは、セッション鍵Ｋ＝（α^x（α^a）^ra）^sBｍｏｄｐを計算する。 ７．共有される秘密は、α^sAsBｍｏｄｐである。 このプロトコルでは、待機幅の要件が再び緩和されているが、署名成分は、通 信者の短期及び長期の鍵を組み合わせて、侵入者からの攻撃を禁止している。 このプロトコルは、また、Ｚ^* _pの部分群を用いても実現できる。この場合 には、ｑは、（ｐ−１）の素約数（prime divisor）であり、ｇは、Ｚ^* _pの中の 位数ｐの要素である。 Ａ及びＢの公開鍵は、それぞれが、ｇ^a及びｇ^bの形式を有し、短期の鍵ｒ_a及 びｒ_bは、ｇ^x及びｇ^yの形式を有している。 署名成分であるｓ_A及びｓ_Bは、ｍｏｄｑで計算され、セッション鍵は、従前の ように、ｍｏｄｑで計算される。この場合には、共有の秘密は、ｇ^sAsBｍｏｄｐ である。 既に述べたように、これらのプロトコルは、Ｚ^* _p以外の群においても実現が可 能であり、特に、ローバスト（robust）群は、有限体上の楕円曲線上の点から成 る群である。このような実現例は、次にプロトコル１’’’として挙げてある。 プロトコル１’’’ 次の記号を用いる。 Ｅは、Ｆｑ上で定義される楕円曲線である。 Ｐは、Ｅ（Ｆｑ）内の素数位数の点である。 ｄ_a（１＜ｄ_a＜ｎ−１）は、当事者Ａの長期の秘密鍵である。 ｄ_b（１＜ｄ_b＜ｎ−１）は、当事者Ｂの長期の秘密鍵である。 Ｑ_a＝ｄ_aＰは、当事者Ａの長期の公開鍵である。 Ｑ_b＝ｄ_bＰは、当事者Ｂの長期の公開鍵である。 ｋ（１＜ｋ＜ｎ−１）は、当事者Ａの短期の秘密鍵である。 ｍ（１＜ｍ＜ｎ−１）は、当事者Ｂの短期の秘密鍵である。 ｒ_b＝ｍＰは、当事者Ｂの短期の公開鍵である。 ｒａ及びｒｂは、ビット・ストリングであり、例えば、ｒ_a及びｒ_bのｘ座標の８ ０最下位ビットである。 このプロトコルを実現するには、次のようにする。 １．Ａは、ｒ_aをＢに送る。 ２．Ｂは、ｒ_bをＡに送る。 ３．Ａは、ｓ_A＝（ｋ＋ｒ_a・ｄ_a）ｍｏｄｎを計算する。 ４．Ａは、セッション鍵Ｋ＝ｓ_A（ｒ_b＋ｒ_bＱ_b）を計算する。 ５．Ｂは、ｓ_B＝（ｍ＋ｒ_b・ｄ_b）ｍｏｄｎを計算する。 ６．Ｂは、セッション鍵Ｋ＝ｓ_b（ｒ_a＋ｒ_aＱ_a）を計算する。 ７．共有される秘密は、ｓ_aｓ_bＰである。 再び、通信者の間では署名成分ｓＡ及びｓＢを送る必要はないことに注意すべ きである。しかし、通信者の短期及び長期の鍵が成分の形式で組み合わされる。 先の例におけるｘ及びｙに対して、記号ｍを用いているのは、曲線上の点の座 標（ｘ，ｙ）との混乱を回避するためである。

───────────────────────────────────────────────────── フロントページの続き (81)指定国 ＥＰ(ＡＴ，ＢＥ，ＣＨ，ＤＥ， ＤＫ，ＥＳ，ＦＩ，ＦＲ，ＧＢ，ＧＲ，ＩＥ，ＩＴ，Ｌ Ｕ，ＭＣ，ＮＬ，ＰＴ，ＳＥ)，ＯＡ(ＢＦ，ＢＪ，ＣＦ ，ＣＧ，ＣＩ，ＣＭ，ＧＡ，ＧＮ，ＭＬ，ＭＲ，ＮＥ， ＳＮ，ＴＤ，ＴＧ)，ＡＰ(ＫＥ，ＬＳ，ＭＷ，ＳＤ，Ｓ Ｚ，ＵＧ)，ＵＡ(ＡＭ，ＡＺ，ＢＹ，ＫＧ，ＫＺ，ＭＤ ，ＲＵ，ＴＪ，ＴＭ)，ＡＬ，ＡＭ，ＡＴ，ＡＵ，ＡＺ ，ＢＡ，ＢＢ，ＢＧ，ＢＲ，ＢＹ，ＣＡ，ＣＨ，ＣＮ， ＣＵ，ＣＺ，ＤＥ，ＤＫ，ＥＥ，ＥＳ，ＦＩ，ＧＢ，Ｇ Ｅ，ＨＵ，ＩＬ，ＩＳ，ＪＰ，ＫＥ，ＫＧ，ＫＰ，ＫＲ ，ＫＺ，ＬＣ，ＬＫ，ＬＲ，ＬＳ，ＬＴ，ＬＵ，ＬＶ， ＭＤ，ＭＧ，ＭＫ，ＭＮ，ＭＷ，ＭＸ，ＮＯ，ＮＺ，Ｐ Ｌ，ＰＴ，ＲＯ，ＲＵ，ＳＤ，ＳＥ，ＳＧ，ＳＩ，ＳＫ ，ＴＪ，ＴＭ，ＴＲ，ＴＴ，ＵＡ，ＵＧ，ＵＳ，ＵＺ， ＶＮ (72)発明者 キュー，ミングァ カナダ国 エヌ２エル・３イー５ オンタ リオ，ウォータールー，ユニバーシティ・ アベニュー・ウエスト 157，ナンバー 112

Claims (1)

1. 【特許請求の範囲】 １．１対の通信者Ａ及びＢが相互に情報を交換することを認証する方法であって 、前記通信者は、それぞれが、秘密鍵ａ及びｂと、生成元αと前記秘密鍵ａ及び ｂのそれぞれとから導かれた公開鍵ｐ_A及びｐ_Bと、を有している方法において、 ｉ）前記通信者の第１の者Ａが、第１のランダムな整数ｘを選択し、前記生成 元を含む関数ｆ（α）のｇ^(x)をベキとする指数関数を作ることにより、第１の 指数関数ｆ（α）^g(x)を提供するステップと、 ｉｉ）前記第１の通信者Ａが、前記ランダムな整数ｘと前記指数関数ｆ（α）^g(x) とから第１の署名ｓＡを生成するステップと、 ｉｉｉ）前記第１の通信者Ａが、第２の通信者Ｂに向けて、前記第１の指数関 数ｆ（α）^g(x)を含むメッセージを送るステップと、 ｉｖ）前記通信者Ｂが、第２のランダムな整数ｙを選択し、前記生成元を含む 関数ｆ’（α）のｇ^(y)をベキとする指数関数を作ることにより、第２の指数関 数ｆ’（α）^g(y)を提供するステップと、 ｖ）前記第２の通信者Ｂが、第１の通信者Ａに向けて、前記第２の指数関数ｆ ’（α）^g(y)を含むメッセージを送るステップと、 ｖｉ）前記通信者のそれぞれが、別の通信者によって公開とされた情報を、彼 らに対して秘密である情報を用いて指数化することによって、セッション鍵Ｋを 構成するステップと、 を含むことを特徴とする方法。 ２．請求項１記載の方法において、前記第１の通信者によって送られる前記情報 は、前記第１の通信者のアイデンティフィケーション（ＩＤ）を含むことを特徴 とする方法。 ３．請求項１記載の方法において、前記第２の通信者によって送られる前記情報 は、前記第２の通信者のＩＤを含むことを特徴とする方法。 ４．請求項３記載の方法において、前記第１の通信者によって送られる前記メッ セージは、前記第１の通信者のＩＤを含むことを特徴とする方 法。 ５．請求項１記載の方法において、前記生成元ｆ（α）を含む前記第１の関数は 、前記生成元自体であることを特徴とする方法。 ６．請求項１記載の方法において、前記生成元を含む前記第２の関数は、前記生 成元自体であることを特徴とする方法。 ７．請求項６記載の方法において、前記生成元を含む前記第１の関数ｆ（α）は 、前記生成元自体であることを特徴とする方法。 ８．請求項１記載の方法において、前記生成元ｆ（α）を含む前記第１の関数は 、前記第２の通信者の秘密鍵ｐ_Bを含むことを特徴とする方法。 ９．請求項１記載の方法において、前記生成元ｆ’（α）を含む前記第２の関数 は、前記第１の通信者の秘密鍵ｐ_Aを含むことを特徴とする方法。 １０．請求項１記載の方法において、前記通信者の一方によって生成された前記 署名は、その一方の通信者の前記ランダムな整数と、指数関数と、秘密鍵とを組 み合わせることを特徴とする方法。 １１．請求項１０記載の方法において、通信者Ａの前記署名は、ｘ−ｒ_Aａα^a ｍｏｄ（ｐ−１）の形式をとることを特徴とする方法。 １２．請求項１０記載の方法において、通信者Ａの前記署名は、ｘ＋ａα^a（ｐ_B ）ｘ ｍｏｄ（ｐ−１）の形式を有することを特徴とする方法。 １３．請求項１０記載の方法において、通信者Ａの前記署名は、ｘ₁をＡによっ て選択された第２のランダムな整数とし、ｒ_x1＝α^x1として、ｘｒ_x1−（ｒ_A）^{r x1} ａの形式を有することを特徴とする方法。 １４．請求項１０記載の方法において、通信者Ｂの前記署名は、ｙ_B−ｒ_Bｂα^b ｍｏｄ（ｐ−１）の形式をとることを特徴とする方法。 １５．請求項１０記載の方法において、通信者Ｂの前記署名は、ｙ＋ｂα^b（ｐ_A ）^y ｍｏｄ（ｐ−１）の形式を有することを特徴とする方法。 １６．請求項１０記載の方法において、通信者Ｂの前記署名は、ｙ₁を通信者Ｂ によって選択された第２の整数とし、ｒ_y1＝α^y1として、ｙｒ_y1−（ｒ_B）^ry1ｂ の形式を有することを特徴とする方法。 １７．請求項１１記載の方法において、通信者Ａは、第２の整数ｘ₁を選択し、 ｒ_A1＝α^x1を通信者Ｂに送り、通信者Ｂは、第２のランダムな整数ｙ₁を選択し 、ｒ_B1＝α^y1を通信者Ｂに送り、前記通信者のそれぞれは、α^xy及びα^x1y1にそ れぞれ等しい１対の鍵ｋ₁及びｋ₂を計算し、前記セッション鍵Ｋは、ｋ₁とｋ₂と のＸＯＲを計算することによって生成されることを特徴とする方法。