鍵交換装置、鍵交換システム、および鍵交換プログラム
【課題】 最小限の通信回数で、鍵の秘密の保持と秘密情報の更新の確実性を確保すること。
【解決手段】 鍵識別子生成装置は、乱数生成装置を用いて生成した乱数と、 相手装置から受信したデータとを用いて自己の鍵識別子を生成する。同期確認装置は、第１の秘密情報を用いて生成された自己の第１の同期確認値と第２の秘密情報を用いて生成された自己の第２の同期確認値とを相手装置へ送出し、受信した相手の第１の同期確認値および相手の第２の同期確認値と、第１の秘密情報を用いて生成した自己の第１の同期検証値および第２の秘密情報を用いて生成した自己の第２の同期検証値とを用いて、同期判定値を生成する。秘密更新装置は、第２の秘密情報と鍵識別子とから第３の秘密情報を生成し、第１の秘密情報の値を第２の秘密情報の値に変更し、第２の秘密情報の値を第３の秘密情報の値に変更する。鍵生成装置は、第１の秘密情報から鍵を生成する。
【解決手段】 鍵識別子生成装置は、乱数生成装置を用いて生成した乱数と、 相手装置から受信したデータとを用いて自己の鍵識別子を生成する。同期確認装置は、第１の秘密情報を用いて生成された自己の第１の同期確認値と第２の秘密情報を用いて生成された自己の第２の同期確認値とを相手装置へ送出し、受信した相手の第１の同期確認値および相手の第２の同期確認値と、第１の秘密情報を用いて生成した自己の第１の同期検証値および第２の秘密情報を用いて生成した自己の第２の同期検証値とを用いて、同期判定値を生成する。秘密更新装置は、第２の秘密情報と鍵識別子とから第３の秘密情報を生成し、第１の秘密情報の値を第２の秘密情報の値に変更し、第２の秘密情報の値を第３の秘密情報の値に変更する。鍵生成装置は、第１の秘密情報から鍵を生成する。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、鍵交換装置及び鍵交換システムに関し、特に、共有した秘密情報に基づく認証付鍵交換装置及びシステムに関する。
【背景技術】
【０００２】
鍵交換方式には二つの装置が参加し、これら二つの装置が互いに通信することにより、同一の鍵を共有する。特に、各装置が自分である事の認証を受ける方法を備えていて、鍵を交換した相手の装置を認証する方式を、「認証付き鍵交換方式」と呼ぶ。
【０００３】
従来の認証付き鍵交換方式として、非特許文献１に記されている方式があげられる。
【０００４】
図１に、従来の認証付き鍵交換方式の概略を示す。
【０００５】
認証付き鍵交換方式は、第１の鍵交換装置１００と、第２の鍵交換装置２００とを備え、これらの間で鍵を交換するものである。ここでは、第１の鍵交換装置１００は自己の識別子としてΠを有し、第２の鍵交換装置２００は自己の識別子としてΠ'を有する。図１に示されるように、第１の鍵交換装置１００と第２の鍵交換装置２００とは、実質的に同様の構成を有する。
【０００６】
詳述すると、第１の鍵交換装置１００は、入力装置１０１、乱数入力装置１０２、認証装置１０４、通信装置１０５、記憶装置１０３、および出力装置１０６を備える。同様に、第２の交換装置２００は、入力装置２０１、乱数入力装置２０２、認証装置２０４、通信装置２０５、記憶装置２０３、および出力装置２０６を備える。したがって、説明を簡略化するために、以下では、第１の鍵交換装置１００を代表として、単に鍵交換装置と記して、説明する。
【０００７】
鍵交換装置１００は、入力装置１０１から、Gを巡回群、qをGの位数、gをGの生成子、Hashをハッシュ関数として、システムパラメター１０７(q,G,g,Hash)と、識別子Πである自己識別子１０８とが入力されて、起動され命令待ち状態となる。
【０００８】
この状態において、識別子Πを持つ命令待ち状態の鍵交換装置１００に、入力装置１０１から、鍵交換開始命令１０９、sidのセッション番号１１２、および識別子Π'である相手識別子１１０が入力されたとする。この場合、次のように鍵交換装置１００の第一ラウンド装置１２０が動作する。ここで、sidは、識別子ΠとΠ'が鍵交換に使う数としては、唯一無二の数であることが期待される。
【０００９】
先ず、第一ラウンド装置１２０は、乱数入力装置１０２より乱数１１１を取り込む。
次に、第一ラウンド装置１２０は、暫定数 r ∈ Z/qZを乱数１１１からランダムに生成する。
【００１０】
第一ラウンド装置１２０は、y = grを生成する。yを冪乗数と呼ぶ。
第一ラウンド装置１２０は、状態 (sid, Π',r) を生成して、これを記憶装置１０３する。
第一ラウンド装置１２０は、("生成",(sid,y))を認証装置１０４に入力し、識別子sigを得る。
第一ラウンド装置１０２は、メッセージ(sid,y,sig) を通信装置１０５を用いて、送信者が識別子Πで、宛先が識別子Π'であるとして送信する。
そして、鍵交換装置１００は命令待ち状態となる。
【００１１】
この状態において、識別子Πを持つ命令待ち状態の鍵交換装置１００が、通信装置１０５を通じて、送信者が識別子Π' で、宛先が識別子Πであるメッセージ (sid,y',sig')を受信したとする。この場合、鍵交換装置１００の鍵生成装置１２１は、次のように動作する。
【００１２】
先ず、鍵生成装置１２１は、記憶装置１０３に保存されている状態を調べる。ここで、記憶装置１０３が、いかなる y,r に対しても、状態 (sid,y,r)を記憶していないとする。その場合には、鍵生成装置１２１は、鍵交換装置１００を直ちに命令待ち状態とする。
【００１３】
一方、記憶装置１０３がある y,r に対して、状態(sid,y,r) を記憶していたとする。この場合、鍵生成装置１２１は、 ("検証",Π',(sid,y'),sig' )を認証装置１０４に入力する。認証装置１０４が"不当"を出力した場合、鍵生成装置１２は、鍵交換装置１００を直ちに命令待ち状態とする。
【００１４】
そうでない場合、鍵生成装置１２１は、記憶装置１０３にある状態(sid,Π',y,r)を完全に消去し、冪乗数 y を用いて (sid,z=y'r) を生成し、それを出力装置１０６に出力する。
この出力装置１０６に出力された(sid,z=y'r)が、交換結果（鍵）１２２である。
【００１５】
また、本発明に関連する先行技術文献として、特許第４１０９１６４号公報（特許文献１）が知られている。この特許文献１は、容易に生成でき、かつ、他人から極めて類推され難く、さらに使用者本人が鍵を紛失した場合でも同じ鍵を安全に生成できる「暗号鍵の生成システム」を開示している。この特許文献１に開示された暗号鍵の生成システムでは、第１情報及び第２情報と、会社を識別するための識別子と、暗号鍵の識別子とに基づいて、ハッシュ関数を用いて暗号鍵を生成している。この特許文献１において、第１情報は「キーワード」であり、第２情報は「パスワード」である。
【先行技術文献】
【特許文献】
【００１６】
【特許文献１】特許第４１０９１６４号公報
【非特許文献】
【００１７】
【非特許文献１】Ran Canetti, Hugo Krawczyk."Universally Composable Notions of Key Exchange and Secure Channels",Advances in Cryptology - EUROCRYPT 2002, International Conference on the Theory and Applications of Cryptographic Techniques, Amsterdam, The Netherlands, April 28 - May 2, 2002, Proceedings, pages 337-351, Springer, Lecture Notes in Computer Science, volume 2332, year 2002.
【発明の概要】
【発明が解決しようとする課題】
【００１８】
図１に示した従来技術の認証付き鍵交換方式には、次に述べるような問題点がある。
【００１９】
第一の問題点は、従来技術の鍵交換方式の安全性が Diffie-Hellman 鍵交換の安全性に依存していることである。何故なら、 Diffie-Hellman 鍵交換は量子計算機の実現や新しいアルゴリズムの発見により、安全でなくなる可能性があるからである。
【００２０】
第二の問題点は、従来技術はDiffie-Hellman 鍵交換等、公開鍵暗号の技術に依存しており、計算量が大きいことである。
【００２１】
これらの問題点を解決するために、あらかじめ秘密情報を両者で共有しておき、これからハッシュ関数等で、新たな鍵を生成する事も可能である。但し、セッション毎に異なる鍵を生成し、ある時点で共有する秘密情報が漏れてもそれまでに使った鍵が分からないようにする為に、共有する秘密情報をハッシュ関数などを用いて更新していく必要がある。この時、以下の問題が発生あるいは問題の発生に注意しなければならない。
【００２２】
(1) 秘密情報の更新が決定的に行われると、初期の秘密情報から未来の鍵が全て分かってしまう。このため、気が付かない秘密情報の盗難が起きると被害が大きくなる。
(2) 秘密情報の更新を確率的に行うと、両者の秘密情報の同期を妨害する攻撃が可能となる可能性がある。また、この妨害を防ぐために通信回数が多くなっしまう。
(3) ある時点で秘密情報が盗まれたとき、秘密情報の更新が十分でないと、直前の鍵が漏洩してしまう。
【００２３】
尚、特許文献１は、暗号鍵の識別子等に基づいて、ハッシュ関数を用いて暗号鍵を生成する技術的思想を開示している。しかしながら、特許文献１は、暗号鍵を生成するシステムを開示しているだけであって、二つの装置が互いに通信することにより、同一の鍵を共有する鍵交換システムとは異なる。
【００２４】
本発明の目的は、最小限の通信回数で、鍵の秘密の保持と秘密情報の更新の確実性とを確保できる、鍵交換装置及び鍵交換システムを提供することにある。
【課題を解決するための手段】
【００２５】
本発明による鍵交換装置は、乱数を生成する乱数生成装置と；本人識別子と相手識別子とを保持する識別子記憶装置と；第１の秘密情報と第２の秘密情報とを保持する秘密情報記憶装置と；乱数生成装置を用いて生成した乱数と、相手装置から受信したデータとを用いて鍵識別子を生成する鍵識別子生成装置と；第１の秘密情報を用いて自己の第１の同期確認値を生成し、第２の秘密情報を用いて自己の第２の同期確認値を生成し、この生成した自己の第１の同期確認値と生成した自己の第２の同期確認値とを相手装置へ送出し、第１の秘密情報を用いて第１の同期検証値を生成し、第２の秘密情報を用いて第２の同期検証値を生成し、相手の第１の同期確認値と相手の第２の同期確認値とを相手装置から受信し、受信した相手の第１の同期確認値および受信した相手の第２の同期確認値と、生成した第１の同期検証値および生成した第２の同期検証値とを用いて、同期判定値を生成する同期確認装置と；第１の秘密情報と第２の秘密情報と鍵識別子とを受け取り、第２の秘密情報と鍵識別子とから第３の秘密情報を生成し、第１の秘密情報の値を第２の秘密情報の値に変更し、第２の秘密情報の値を第３の秘密情報の値に変更する秘密更新装置と；第１の秘密情報から鍵を生成する鍵生成装置と；を備える。
【発明の効果】
【００２６】
本発明によれば、最小限の通信回数で、鍵の秘密の保持と秘密情報の更新の確実性とを確保できる。
【図面の簡単な説明】
【００２７】
【図１】従来の鍵交換方式の構成を示すブロック図である。
【図２】本発明の第１の実施例に係る鍵交換装置を示すブロック図である。
【図３】図２に示した鍵交換装置において、“開始命令”が入力された場合の処理を示したブロック図である。
【図４】図２に示した鍵交換装置において、“開始要求”を含んだメッセージを受信した場合の処理を示したブロック図である。
【図５】図２に示した鍵交換装置において、“応答命令”が入力された場合の処理を示したブロック図である。
【図６】図２に示した鍵交換装置において、“応答”を含んだメッセージを受信した場合の処理を示したブロック図である。
【図７】図２に示した鍵交換装置において、“非同期”を含んだメッセージを受信した場合の処理を示したブロック図である。
【図８】図２に示した鍵交換装置において、“了解”を含んだメッセージを受信した場合の処理を示したブロック図である。
【図９】図２に示した鍵交換装置において、“非同期確認”を含んだメッセージを受信した場合の処理を示したブロック図である。
【図１０】図２に示した鍵交換装置において、“失効命令”が入力された場合の処理を示したブロック図である。
【発明を実施するための形態】
【００２８】
本発明の実施形態に係る鍵交換装置は、乱数を生成する乱数生成装置と、本人識別子と相手識別子とを保持する識別子記憶装置と、第１の秘密情報と第２の秘密情報とを保持する秘密情報記憶装置と、鍵識別子生成装置と、同期確認装置と、秘密更新装置と、第１の秘密情報から鍵を生成する鍵生成装置と、を備える。
【００２９】
鍵識別子生成装置は、乱数生成装置を用いて生成した乱数と、相手装置から受信したデータとを用いて鍵識別子を生成する機能を有する。
【００３０】
同期確認装置は、第１の秘密情報を用いて自己の第１の同期確認値を生成し、第２の秘密情報を用いて自己の第２の同期確認値を生成する機能と、この生成した自己の第１の同期確認値と生成した自己の第２の同期確認値とを相手装置へ送出する機能と、第１の秘密情報を用いて第１の同期検証値を生成し、第２の秘密情報を用いて第２の同期検証値を生成する機能と、相手の第１の同期確認値と相手の第２の同期確認値とを相手装置から受信する機能と、受信した相手の第１の同期確認値および受信した相手の第２の同期確認値と、生成した第１の同期検証値および生成した第２の同期検証値とを用いて、同期判定値を生成する機能とを有する。
【００３１】
秘密更新装置は、第１の秘密情報と第２の秘密情報と鍵識別子とを受け取り、第２の秘密情報と鍵識別子とから第３の秘密情報を生成し、第１の秘密情報の値を第２の秘密情報の値に変更し、第２の秘密情報の値を第３の秘密情報の値に変更する機能を有する。
【００３２】
秘密情報の更新を、ハッシュ関数にその秘密情報を入力して得られた結果を新たな秘密情報とする様に行うとする。この時、ハッシュ関数に更新する前の秘密情報のみを入力するとすると、最初の秘密情報が漏れるとこれから未来の秘密情報が全て分かってしまう。そこで、本発明の実施形態では、ハッシュ関数への入力に鍵識別子 kid を加わえて、未来の秘密情報を確率的に決定している。このことにより、攻撃者が、全ての通信を盗聴することなく秘密情報を同期し続ける事は出来なくなる。また、鍵識別子は両方の参加者が生成する乱数からなるため、少なくとも一人が正直であれば、秘密情報は確率的に遷移する。
【００３３】
また、秘密情報が確率的に遷移する場合、両方の参加者の秘密情報の同期が崩れてしまう可能性がある。そこで、本発明の実施形態では、秘密情報として、第１の秘密情報と第２の秘密情報との二つの秘密情報を準備する。そして、第１の秘密情報と第２の秘密情報とを更新したときに、更新する前の第２の秘密情報へと第１の秘密情報を更新する。この様にすることで、二人の参加者が第２の秘密情報を互いに異なるものへと更新してしまっても、第１の秘密情報から再度同じものを構築し直すことができる。
【００３４】
更に、片方の参加者が共有する秘密情報から鍵を生成して出力した時点で、この鍵生成に使った秘密情報が残存していると、この秘密情報を得た攻撃者が生成された秘密情報を知る可能性がある。それゆえ、鍵生成に用いた秘密情報は速やかに更新して消去する必要がある。特に、片方が鍵を生成して秘密情報を更新しても、他方がこの更新前の秘密情報を保持している様な事がないように注意する必要がある。一方、あまりに早急に秘密情報を更新すると、相手の秘密情報がどのように更新されるか十分に把握する前に自身の秘密情報を更新してしまい、両方の参加者の秘密情報の同期が壊れてしまう。
【００３５】
この様な鍵の秘密保持と秘密情報の更新の確実性の両方を求めるには、両方の参加者で通信を何度も行って、両方の状況を確認しながら処理を進めれば良い。しかしながら、この様なことをすると、通信回数が多くなり効率的でない。
【００３６】
そこで、本発明の実施形態では、三回という最低限の通信回数で、先の問題を解決している。特に、鍵の安全性を確保するために、両方の参加者が同期している場合には、次のようなタイミングで秘密情報の更新を行う。すなわち、二回目のメッセージ送信を行う者はこの時に秘密情報の更新を行い、一回目と三回目のメッセージ送信を行う者は三回目のそのときに秘密情報の更新を行う。一方、秘密情報の同期がとれていない場合は、次のようなタイミングで秘密情報の更新を行う。すなわち、二回目のメッセージ送信を行う者は三回目のメッセージを受信してから、一回目と三回目のメッセージ送信を行うものは三回目のそのときに、秘密情報の更新を行い、鍵の生成は行わずに秘密情報の同期のみを行う。この様に、鍵の生成を行うときと、秘密情報の同期を行うときとで、秘密情報の更新時期を違える事で、鍵の秘密の保持と秘密情報の更新の確実性の両方とを、最小限の通信回数で成功している。
【実施例１】
【００３７】
以下、図面を参照して、本発明の第１の実施例による、共有した秘密情報に基づく認証付鍵交換装置について説明する。
【００３８】
図２は、本発明の第１の実施例による鍵交換装置を示すブロック図である。
【００３９】
鍵交換装置は、入力装置３００と、出力装置３０１と、通信装置３０２とを備える。以下の説明では、次のことを定義する。「鍵交換装置にあるデータが入力される」とは、鍵交換装置の入力装置３００にこのデータが書き込まれる事を意味する。「鍵交換装置があるデータを出力する」とは、鍵交換装置の出力装置３０１がこのデータを鍵交換装置の外の媒体に書き出すことを意味する。「鍵交換装置があるデータを受け取る」とは、鍵交換装置の通信装置３０２にこのデータが書き込まれる事を意味する。「鍵交換装置があるデータを送付する」とは、鍵交換装置の通信装置３０２がこのデータを通信路に書き込む事を意味する。
【００４０】
鍵交換装置は乱数生成装置３０３を備える。この乱数生成装置３０３は、外から何らかの情報を受け入れて乱数を生成し、ランダムに値を選ぶ場合に、このランダム性の源として利用する。
【００４１】
鍵交換装置は、セッション番号生成装置３０９、鍵識別子生成装置３１０、同期確認装置３１１、秘密更新装置３１２、鍵生成装置３１３、および鍵検証装置３１４も備える。
【００４２】
(初期設定)
鍵交換装置は、安全変数κに関する、独立なハッシュ関数 HashS:{0,1}* → {0,1}κ, HashC:{0,1}* → {0,1}κ, HashK:{0,1}* → K, を実現する機能を備えているとする。ここで、Kは認証付鍵交換で生成される鍵の空間である。また、ハッシュ関数HashS は第１のハッシュ関数と呼ばれ、ハッシュ関数HashKは第２のハッシュ関数と呼ばれ、ハッシュ関数HashCは第３のハッシュ関数と呼ばれる。第１のハッシュ関数HashS は、同期確認／検証に用いられるので、同期確認／検証用ハッシュ関数とも呼ばれる。第２のハッシュ関数HashKは、鍵生成に用いられるので、鍵生成用ハッシュ関数とも呼ばれる。第３のハッシュ関数HashCは、鍵検証に用いられるので、鍵検証用ハッシュ関数とも呼ばれる。
【００４３】
また、以下の説明では、自己の情報と相手の情報とを区別するために、相手の情報には右肩にダッシュ「’」を付しているが、自己の情報には、このようなダッシュ「’」を付していない。
【００４４】
鍵交換装置には、自己の識別子Pである自己識別子３０６と、相手の識別子P'である相手識別子３０７とが設定される。換言すれば、鍵交換装置は、自己識別子３０５と相手識別子３０７とを保持する識別子記憶装置３２０を備えている。
【００４５】
鍵交換装置には、自己カウンタOCTR=0 と、相手カウンタPCTR=0とが設定される。
【００４６】
鍵交換装置には、第１の秘密情報３０４としてのsecret1 ∈{0,1}κと、第２の秘密情報３０５としてのsecret2 ∈{0,1}κ とが、秘密情報として格納される。換言すれば、鍵交換装置は、第１の秘密情報３０４と第２の秘密情報３０５とを保持する秘密情報記憶装置３２２を備えている。尚、図２では、第１の秘密情報３０４（secret1）を“秘密１”と記してあり、第２の秘密情報３０５（secret2）を“秘密２”と記してある。
【００４７】
鍵交換装置にはセッション状態３０８を保存する記憶装置３２４が確保される。セッション状態３０８の初期状態は“空”である。
【００４８】
このようにして、初期設定が終わった鍵交換装置は、待ち状態におかれる。待ち状態の鍵交換装置は、メッセージが入力されるあるいはメッセージを受け取った場合、その内容により処理を選択３１５して行い、再び待ち状態に戻る。
【００４９】
図３乃至図１０は、それぞれ、入力されるあるいは受け取るメッセージが、"開始命令"、"開始要求"、"応答命令"、"応答"、"非同期"、"了解"、"非同期確認"、および"失効命令"である場合の鍵交換装置の処理を示したブロック図である。図３乃至図１０では、それぞれの処理を、順番に処理１、処理２、処理３、処理４、処理５、処理６、処理７、および処理８と記して示している。
【００５０】
図３を参照して、鍵交換装置に(開始命令)が入力装置３００から入力された場合の動作について説明する。この場合、鍵交換装置は、次の何れかの動作をする(処理１)。
【００５１】
Ａ１） もしセッション状態を保持していないならば、セッション番号生成装置３０９は自己開始者カウンタ ictr= OCTR とし、OCTRをOCTR+1に変更し、自己セッション番号 sid ∈ {0,1}κ をランダムに選ぶ。すなわち、セッション番号生成装置３０９は、乱数生成装置３０３で生成された乱数を、自己セッション番号 sidとしてランダムに選ぶ。そして、同期確認装置３１１は、自己の第1の同期確認値x1と自己の第2の同期確認値x2とを、第１の秘密情報３０４と第２の秘密情報３０５とを用いて、次のように生成する。
x1 = HashS(secret1,P,ictr,sid,"開始要求")
x2 = HashS(secret2,P,ictr,sid,"開始要求").
【００５２】
すなわち、同期確認装置３１１は、第１の秘密情報３０４（secret1）、自己識別子３０６（P）、自己開始者カウンタ（ictr）、および自己セッション番号（sid）に基づいて、第１のハッシュ関数HashSを用いて、自己の第１の同期確認値x1を生成する。また、同期確認装置３１１は、第２の秘密情報３０５（secret2）、自己識別子３０６（P）、自己開始者カウンタ（ictr）、および自己セッション番号（sid）に基づいて、第１のハッシュ関数HashSを用いて、自己の第2の同期確認値x2を生成する。
【００５３】
そして、同期確認装置３３１は、自己識別子３０６（P）、自己開始者カウンタ（ictr）、自己セッション番号（sid）、自己の第１の同期確認値x1、および自己の第2の同期確認値x2を含む、開始要求メッセージ (P,"開始要求",ictr,sid,x1,x2) を、通信装置３０２から、相手の識別子P'を持つ相手側の鍵交換装置に送付し、自己開始者カウンタ（ictr）、自己セッション番号（sid）、自己の第１の同期確認値x1、および自己の第2の同期確認値x2を含む、開始要求情報("開始要求",ictr,sid,x1,x2) をセッション状態３０８として記憶装置３２４に保存する。その後、鍵交換装置は、待ち状態に戻る。
【００５４】
Ａ２） その他の場合、鍵交換装置は入力を無視する。
【００５５】
次に図４を参照して、鍵交換装置が、相手側の鍵交換装置から、相手識別子３０７（P'）、相手開始者カウンタ（ictr'）、相手セッション番号（sid'）、相手の第１の同期確認値（x'1）、および相手の第２の同期確認値（x'2）を含む、開始要求メッセージ (P',"開始要求",ictr',sid',x'1,x'2) を通信装置３０２で受け取った場合の動作について説明する。この場合、鍵交換装置は、次の何れかの動作をする(処理2)。
【００５６】
Ｂ１） もし、ある同期判定値 sync に関して、セッション状態３０８として応答待情報("応答待",ictr',sid',x'1,x'2,sync) を記憶装置３２４に保持しているならば、鍵交換装置は、待ち状態に戻る。
【００５７】
Ｂ２） ｉctr'>PCTR でなければ、鍵交換装置は、待ち状態に戻る。
【００５８】
Ｂ３） その他の場合、同期確認装置３１１は、自己の第1の同期検証値 y1 と自己の第2の同期検証値 y2とを、第１の秘密情報３０４と第２の秘密情報３０５とを用いて、次のように生成する。
y1 = HashS(secret1,P',ictr',sid',"開始要求")
y2 = HashS(secret2,P',ictr',sid',"開始要求").
【００５９】
すなわち、同期確認装置３１１は、第１の秘密情報３０４（secret1）、相手識別子３０７（P'）、相手開始者カウンタ（ictr'）、および相手セッション番号（sid'）に基づいて、第１のハッシュ関数HashSを用いて、自己の第1の同期検証値 y1 を生成する。また、同期確認装置３１１は、第２の秘密情報３０５（secret2）、相手識別子３０７（P'）、相手開始者カウンタ（ictr'）、および相手セッション番号（sid'）に基づいて、第１のハッシュ関数HashSを用いて、自己の第2の同期検証値 y2を生成する。
【００６０】
さらに、同期確認装置３１１は、同期判定値 sync を次の様に決定する。
Ｂ３−１) もし (x'1=y2) なら、sync=-1 とする。
Ｂ３−２） もし (x'1,x'2)=(y1,y2) なら、sync=0 とする。
Ｂ３−３) もし (x'2=y1) なら、sync=1 とする。
Ｂ３−４） もし (x'1=y1) かつ (x'2 ≠ y2) ならば、sync=2 とする。
Ｂ３−５) その他の場合は sync = NA.とする。
【００６１】
次に、sync= NA なら、鍵交換装置は待ち状態に戻る。待ち状態に戻らない場合、同期確認装置３１１は、PCTR=ictr' として、次の何れかの動作をする。
【００６２】
Ｂ３−５−１) もしセッション状態３０８を保持していないならば、同期確認装置３１１は、(開始要求受付) を出力装置３０１から出力し、応答待情報("応答待",ictr',sid',x'1,x'2,sync) をセッション状態３０８として記憶装置３２４に保存する。その後、鍵交換装置は、待ち状態に戻る。
【００６３】
Ｂ３−５−２) その他の場合、同期確認装置は、そのセッション状態３０８を消去し、(中止)を出力装置３０１から出力する。その後、鍵交換装置は、待ち状態に戻る。
【００６４】
次に図５を参照して、鍵交換装置が(応答命令)を入力装置３００から入力された場合の動作について説明する。この場合、鍵交換装置は、次の何れかの動作をする(処理3)。
【００６５】
Ｃ１） セッション状態３０８が、ある(ictr',sid',x'1,x'2,sync) に関して応答待情報 ("応答待",ictr',sid',x'1,x'2,sync) であるとする。この場合、セッション番号生成装置３０９は、自己応答者カウンタ rctr=OCTR とし、OCTR を OCTR+1 に変更し、自己セッション番号 sid ∈ {0,1}κ をランダムに選ぶ。すなわち、セッション番号生成装置３０９は、乱数生成装置３０３で生成された乱数を、自己セッション番号sidとしてランダムに選ぶ。鍵識別子生成装置３１０は、自己の鍵識別子 kid を (ictr',sid',rctr,sid) とする。すなわち、鍵識別子生成装置３１０は、相手開始者カウンタ（ictr'）、相手セッション番号（sid'）、自己応答者カウンタ（rctr）、および自己セッション番号（sid）を用いて、自己の鍵識別子 kid を生成する。次に、鍵交換装置は、次の何れかの動作をする。
【００６６】
Ｃ１−１） もし sync=0 なら（すなわち、同期判定値syncが“同期”を示しているなら）、同期確認装置３１１は、自己の第1の同期確認値 x1と自己の第2の同期確認値 x2とを、第１の秘密情報３０４と第２の秘密情報３０５とを用いて、次のように生成する。
x1 = HashS(secret1,P,kid,"応答"),
x2 = HashS(secret2,P,kid,"応答").
【００６７】
すなわち、同期確認装置３１１は、第１の秘密情報３０４（secret1）、自己識別子３０６（P）、および自己の鍵識別子 kidに基づいて、第１のハッシュ関数HashSを用いて、自己の第1の同期確認値 x1を生成する。また、同期確認装置３１１は、第２の秘密情報３０５（secret2）、自己識別子３０６（P）、および自己の鍵識別子 kidに基づいて、第１のハッシュ関数HashSを用いて、自己の第２の同期確認値 x2を生成する。
【００６８】
次に、鍵生成装置３１３は、次の式に従って、鍵keyを生成し、
key = Hashk(secret1,kid)
鍵検証装置314は、次の式に従って、鍵検証値verを生成する。
ver = HashC(secret1,kid)
【００６９】
すなわち、鍵生成装置３１３は、第１の秘密情報３０４（secret1）および自己の鍵識別子 kidに基づいて、第２のハッシュ関数HashKを用いて、鍵keyを生成する。また、鍵検証装置３１４は、第１の秘密情報３０４（secret1）および自己の鍵識別子 kidに基づいて、第３のハッシュ関数HashCを用いて、自己鍵検証値verを生成する。
【００７０】
そして、秘密更新装置３１２は、秘密情報 (secret1,secret2) を (secret2,HashS(secret2,kid)) に更新する。詳述すると、秘密更新装置３１２は、第１の秘密情報３０４（secret1）、第２の秘密情報３０５（secret2）、および自己の鍵識別子 kid を受け取り、第２の秘密情報３０５（secret2）と自己の鍵識別子 kidとに基づいて、第１のハッシュ関数HashS を用いて、第３の秘密情報（secret３）を生成し、第１の秘密情報３０４（secret1）の値を第２の秘密情報３０５（secret2）の値に変更し、第２の秘密情報３０５（secret2）の値を第３の秘密情報（secret３）の値に変更する。
【００７１】
同期確認装置３１１は、セッション状態３０８を応答情報 ("応答",kid,ver,key) へ更新し、自己の鍵識別子 kid を出力装置３０１から出力し、応答メッセージ (P,"応答",ictr',sid',rctr,sid,x1,x2) を通信装置３０２から、相手識別子 P'を持つ相手側の鍵交換装置に送る。そして、鍵交換装置は、待ち状態に戻る。
【００７２】
Ｃ１−２) もし sync ≠ 0 なら、鍵交換装置は、次の何れかの動作をする。
【００７３】
Ｃ１−２−１） もし sync=-1 なら、同期確認装置３１１は、一時秘密情報（第３の秘密情報） secret3 と自己の第1の同期確認値 x1 と自己の第2の同期確認値 x2 とを、次のように生成する。
secret3 = HashS(secret2, kid) 、
x1 = HashS(secret2,P,kid,"非同期",sync)、
x2 = HashS(secret3,P,kid,"非同期",sync).
【００７４】
すなわち、同期確認装置３１１は、第２の秘密情報３０５（secret2）および自己の鍵識別子 kidに基づいて、第１のハッシュ関数HashS を用いて、一時秘密情報（第３の秘密情報）（secret３）を生成する。また、同期確認装置３１１は、第２の秘密情報３０５（secret2）、自己識別子３０６（P）、自己の鍵識別子 kid および同期判定値sync に基づいて、第１のハッシュ関数HashS を用いて、自己の第1の同期確認値 x1 を生成する。そして、同期確認装置３１１は、一次秘密情報（第３の秘密情報）（secret３）、自己識別子３０６（P）、自己の鍵識別子 kid および同期判定値sync に基づいて、第１のハッシュ関数HashS を用いて、自己の第2の同期確認値 x2 を生成する。
【００７５】
Ｃ１−２−２) もし、sync=1 あるいは sync=2 なら、同期確認装置３１１は、一時秘密情報（第３の秘密情報） secret3 と自己の第1の同期確認値 x1 と自己の第2の同期確認値 x2 とを、第１の秘密情報３０４と第２の秘密情報３０５とを用いて、次のように生成する。
secret3 =HashS(secret1,kid)、
x1 = HashS(secret1,P,kid,"非同期",sync)、
x2 = HashS(secret3,P,kid,"非同期",sync).
【００７６】
すなわち、同期確認装置３１１は、第１の秘密情報３０４（secret1）および自己の鍵識別子 kidに基づいて、第１のハッシュ関数HashS を用いて、一時秘密情報（第３の秘密情報）（secret３）を生成する。また、同期確認装置３１１は、第１の秘密情報３０４（secret1）、自己識別子３０６（P）、自己の鍵識別子 kid および同期判定値sync に基づいて、第１のハッシュ関数HashS を用いて、自己の第1の同期確認値 x1 を生成する。そして、同期確認装置３１１は、一次秘密情報（第３の秘密情報）（secret３）、自己識別子３０６（P）、自己の鍵識別子 kid および同期判定値sync に基づいて、第１のハッシュ関数HashS を用いて、自己の第２の同期確認値 x2 を生成する。
【００７７】
次に、同期確認装置３１１は、非同期メッセージ (P,"非同期",sync,ictr',sid',rctr,sid,x1,x2) を、相手識別子 P'を持つ相手側の鍵交換装置へ送り、セッション状態３０８を情報("応答","非同期",sync,kid,x1,x2,secret3) へ更新し、そして、鍵交換装置は、待ち状態に戻る。
【００７８】
Ｃ２） その他の場合、鍵交換装置は、セッション状態３０８を消去し、入力を無視する。
【００７９】
次に図６を参照して、鍵交換装置が、相手側の鍵交換装置から、相手識別子３０７（P'）、自己開始者カウンタ（ictr）、自己セッション番号（sid）、相手応答者カウンタ（rctr'）、相手セッション番号（sid'）、相手の第１の同期確認値（x'1）、および相手の第２の同期確認値（x'2）を含む、応答メッセージ(P',"応答",ictr,sid,rctr',sid',x'1,x'2) を通信装置３０２で受け取った場合の動作について説明する。この場合、鍵交換装置は、次の何れかの動作をする(処理4)。
【００８０】
Ｄ１） セッション状態３０８が、ある (x1,x2) に関して開始要求情報 ("開始要求",ictr,sid,x1,x2) であるとする。この場合、鍵識別子生成装置３１０は自己の鍵識別子 kid を (ictr,sid,rctr',sid') とする。すなわち、鍵識別子静止装置３１０は、自己開始者カウンタ（ictr）、自己セッション番号（sid）、相手応答者カウンタ（rctr'）、および相手セッション番号（sid'）を用いて自己の鍵識別子 kid を生成する。そして、同期確認装置３１１は、自己の第1の同期検証値 y1 と自己の第2の同期検証値 y2 とを、第１の秘密情報３０４と第２の秘密情報３０５とを用いて、次のように生成する。
y1 = HashS(secret1,P',kid,"応答"),
y2 = HashS(secret2,P',kid,"応答").
【００８１】
すなわち、同期確認装置３１１は、第１の秘密情報３０４（secret1）、相手識別子３０７（P'）、および自己の鍵識別子 kid に基づいて、第１のハッシュ関数HashS を用いて、自己の第1の同期検証値 y1を生成する。また、同期確認装置３１１は、第２の秘密情報３０５（secret2）、相手識別子３０７（P'）、および自己の鍵識別子 kid に基づいて、第１のハッシュ関数HashS を用いて、自己の第2の同期検証値 y2とを生成する。
【００８２】
そして、鍵交換装置は、次の何れかの動作をする。
【００８３】
Ｄ１−１） もし rctr' > PCTR かつ (x'1,x'2)=(y1,y2) ならば、鍵生成装置３１３は、次の式に従って、鍵keyを生成し、
key = Hashk(secret1,kid)
鍵検証装置３１４は、次の式に従って、自己の鍵検証値verを生成する。
ver = HashC(secret1,kid)
【００８４】
すなわち、鍵生成装置３１３は、第１の秘密情報３０４（secret1）および自己の鍵識別子 kid をに基づいて、第２のハッシュ関数HashKを用いて、鍵keyを生成する。また、鍵検証装置３１４は、第１の秘密情報３０４（secret1）および自己の鍵識別子 kidに基づいて、第３のハッシュ関数HashCを用いて、自己の鍵検証値verを生成する。
【００８５】
そして、秘密更新装置３１２は、秘密情報 (secret1,secret2) を (secret2,HashS(secret2,kid)) へ更新し、PCTR = rctr' と変更する。詳述すると、秘密更新装置３１２は、第１の秘密情報３０４（secret1）、第２の秘密情報３０５（secret2）、および自己の鍵識別子 kid を受け取り、第２の秘密情報３０５（secret2）と自己の鍵識別子 kidとに基づいて、第１のハッシュ関数HashS を用いて、第３の秘密情報（secret３）を生成し、第１の秘密情報３０４（secret1）の値を第２の秘密情報３０５（secret2）の値に変更し、第２の秘密情報３０５（secret2）の値を第３の秘密情報（secret３）の値に変更する。
【００８６】
同期確認装置３１１は、自己の鍵識別子 (kid) を出力装置３１０から出力し、 (kid,key) を出力装置３０１から出力し、了解メッセージ(P,"了解",ictr,sid,rctr',sid',ver) を通信装置３０２から相手識別子 P' を持つ相手側の鍵交換装置へ送り、セッション状態３０８を消去する。その後、鍵交換装置は、待ち状態に戻る。
【００８７】
Ｄ１−２) もし、その他の場合、鍵交換装置は、待ち状態に戻る。
Ｄ２） その他の場合、鍵交換装置は、待ち状態に戻る。
【００８８】
次に図７を参照して、鍵交換装置が相手側の鍵交換装置から、相手識別子３０７（P'）、同期判定値（sync）、自己開始者カウンタ（ictr）、自己セッション番号（sid）、相手応答者カウンタ（rctr'）、相手セッション番号（sid'）、相手の第１の同期確認値（x'1）、および相手の第２の同期確認値（x'2）を含む、非同期メッセージ(P',"非同期",sync,ictr,sid,rctr',sid',x'1,x'2) を通信装置３０２で受け取った場合の動作について説明する。この場合、鍵交換装置は、次の何れかの動作をする(処理５)。
【００８９】
Ｅ１） セッション状態３０８が、ある (x1,x2) に関して開始要求情報("開始要求",ictr,sid,x1,x2) であるとする。この場合、鍵識別子生成装置３１０は、自己の鍵識別子 kid を (ictr,sid,rctr',sid') とする。すなわち、鍵識別子生成装置３１０は、自己開始者カウンタ（ictr）、自己セッション番号（sid）、相手応答者カウンタ（rctr'）、および相手セッション番号（sid'）を用いて自己の鍵識別子 kid を生成する。そして、鍵交換装置は、次の何れかの動作をする。
【００９０】
Ｅ１−１） sync=-1 あるいは sync=2 とする。この場合、同期確認装置３１１は、一時秘密情報（第３の秘密情報）secret3 と自己の第1の同期検証値 y1 と自己の第2の同期検証値 y2 とを、第１の秘密情報３０４と第２の秘密情報３０５とを用いて、次のように生成する。
secret3 = HashS(secret1,kid)
y1 = HashS(secret1,P',kid,"非同期",sync)
y2 = HashS(secret3,P',kid,"非同期",sync).
【００９１】
すなわち、同期確認装置３１１は、第１の秘密情報３０４（secret1）および自己の鍵識別子kidに基いて、第１のハッシュ関数HashS を用いて、一時秘密情報（第３の秘密情報）（secret３）を生成する。また、同期確認装置３１１は、第１の秘密情報３０４（secret1）、相手識別子３０７（P'）、自己の鍵識別子kid、および同期判定値syncに基いて、第１のハッシュ関数HashS を用いて、自己の第1の同期検証値 y1を生成する。さらに、同期確認装置３１１は、一時秘密情報（第３の秘密情報）（secret３）、相手識別子３０７（P'）、自己の鍵識別子kid、および同期判定値syncに基いて、第１のハッシュ関数HashS を用いて、自己の第2の同期検証値 y2 を生成する。
【００９２】
そして、鍵交換装置は、次の何れかの動作をする。
【００９３】
Ｅ１−１−１） rctr' >PCTR かつ (x'1,x'2) =(y1,y2)なら、秘密更新装置３１２は、秘密情報 (secret1,secret2) を(secret1,secret3) へ更新し、 PCTR=rctr' に変更する。すなわち、秘密更新装置３１２は、第１の秘密情報３０４（secret1）の値をそのまま第１の秘密情報３０４（secret1）の値とし、第２の秘密情報３０５（secret2）の値を一時秘密情報（第３の秘密情報）（secret３）の値に更新する。
【００９４】
Ｅ１−１−２) その他の場合、鍵交換装置は、待ち受け状態に戻る。
【００９５】
Ｅ１−２） sync = 1 とする。この場合、同期確認装置３１１は、一時秘密情報（第３の秘密情報）secret3と自己の第1の同期検証値y1と自己の第2の同期検証値y2とを、第１の秘密情報３０４と第２の秘密情報３０５とを用いて、次のように生成する。
secret3 = HashS(secret2,kid)
y1 = HashS(secret2,P',kid,"非同期",sync)
y2 = HashS(secret3,P',kid,"非同期",sync).
【００９６】
すなわち、同期確認装置３１１は、第２の秘密情報３０５（secret2）および自己の鍵識別子kidに基いて、第１のハッシュ関数HashS を用いて、一時秘密情報（第３の秘密情報）（secret３）を生成する。また、同期確認装置３１１は、第２の秘密情報３０５（secret2）、相手識別子３０７（P'）、自己の鍵識別子kid、および同期判定値syncに基いて、第１のハッシュ関数HashS を用いて、自己の第1の同期検証値y1を生成する。さらに、同期確認装置３１１は、一時秘密情報（第３の秘密情報）（secret３）、相手識別子３０７（P'）、自己の鍵識別子kid、および同期判定値syncに基いて、第１のハッシュ関数HashS を用いて、自己の第2の同期検証値y2を生成する。
【００９７】
そして、鍵交換装置は、次の何れかの動作をする。
【００９８】
Ｅ１−２−１） rctr' >PCTR かつ (x'1,x'2) =(y1,y2)なら、秘密更新装置３１２は、秘密情報 (secret1,secret2) を(secret2,secret3) へ更新し、PCTR=rctr' に変更する。すなわち、秘密更新装置３１２は、第１の秘密情報３０４（secret1）の値を第２の秘密情報３０５（secret2）の値に更新し、第２の秘密情報３０５（secret2）の値を一時秘密情報（第３の秘密情報）（secret３）に更新する。
【００９９】
Ｅ１−２−２) その他の場合、鍵交換装置は、待ち受け状態に戻る。
【０１００】
次に、同期確認装置３１１は、自己の第1の同期確認値x1 と自己の第2の同期確認値x2とを、第１の秘密情報３０４と第２の秘密情報３０５とを用いて、次のように生成する。
x1 = HashS(secret1,P,kid,"非同期確認",sync),
x2 = HashS(secret2,P,kid,"非同期確認",sync).
【０１０１】
すなわち、同期確認装置３１１は、第１の秘密情報３０４（secret1）、自己識別子３０６（P）、自己の鍵識別子kid、および同期判定値syncに基づいて、第１のハッシュ関数HashS を用いて、自己の第1の同期確認値 x1 を生成する。また、同期確認装置３１１は、第２の秘密情報３０５（）、自己識別子３０６（P）、自己の鍵識別子kid、および同期判定値syncに基づいて、第１のハッシュ関数HashS を用いて、自己の第2の同期確認値 x2を生成する。
【０１０２】
そして、同期確認装置３１１は、非同期確認メッセージ(P,"非同期確認",kid,x1,x2) を通信装置３０２から、相手識別子P' を持つ相手側の鍵交換装置へ送り、セッション状態３０８を消去し、(中止)を出力装置３０１から出力する。その後、鍵交換装置は、待ち受け状態に戻る。
【０１０３】
Ｅ２） その他の場合、鍵交換装置は、受け取ったメッセージを無視する。
【０１０４】
次に図８を参照して、鍵交換装置が、相手側の鍵交換装置から、相手識別子３０７（P'）、相手開始者カウンタ（ictr'）、相手セッション番号（sid'）、自己応答者カウンタ（rctr）、自己セッション番号（sid）、および相手鍵検証値（ver'）を含む了解メッセージ(P',"了解",ictr',sid',rctr,sid,ver') を、通信装置３０２で受け取った場合の動作について説明する。この場合、鍵交換装置は、次の何れかの動作をする(処理6)。
【０１０５】
Ｆ１） セション状態３０８が、kid=(ictr',sid',rctr,sid) かつ ver=ver' であるような応答情報 ("応答",kid,ver,key) であるとする。この場合、同期確認装置３１１は、(kid,key) を出力装置３０１から出力し、セッション状態３０８を消去する。そして、鍵交換装置は、待ち受け状態に戻る。
【０１０６】
Ｆ２） その他の場合、鍵交換装置は、受け取ったメッセージを無視する。
【０１０７】
次に図９を参照して、鍵交換装置が、相手側の鍵交換装置から、相手識別子３０７（P'）、相手鍵識別子（kid'）、相手の第１の同期確認値（x'1）、および相手の第２の同期確認値（x'2）を含む、非同期確認メッセージ(P',"非同期確認",kid',x'1,x'2) を通信装置３０２で受け取った場合の動作について説明する。この場合、鍵交換装置は、次の何れかの動作をする(処理7)。
【０１０８】
Ｇ１） セション状態３０８が、kid=kid' であるような情報("応答","非同期",sync,kid,x1,x2,secret3) であるとする。この場合、鍵交換装置は、次の何れかの動作をする。
【０１０９】
Ｇ１−１) sync=-1 とする。この場合、同期確認装置３１１は、自己の第１の同期検証値 y1 と自己の第２の同期検証値y2 とを、第２の秘密情報３０５とセッション状態３０８とを用いて、次のように生成する。
y1 = HashS(secret2,P,kid,"非同期確認",sync)
y2 = HashS(secret3,P,kid,"非同期確認",sync).
【０１１０】
すなわち、同期確認装置３１１は、第２の秘密情報３０５（secret2）、自己識別子３０６（P）、自己の鍵識別子kid、および同期判定値syncに基いて、第１のハッシュ関数HashS を用いて、自己の第１の同期検証値 y1を生成する。また、同期確認装置３１１は、セッション状態３０８中の一時秘密情報（secret3）、自己識別子３０６（P）、自己の鍵識別子kid、および同期判定値syncに基いて、第１のハッシュ関数HashS を用いて、自己の第２の同期検証値y2を生成する。
【０１１１】
そして、鍵交換装置は、次の何れかの動作をする。
【０１１２】
Ｇ１−１−１) (x'1,x'2)=(y1,y2)なら、秘密更新装置３１２は、秘密情報 (secret1,secret2) を(secret2,secret3) へ更新する。すなわち、秘密更新装置３１２は、第１の秘密情報３０４（secret1）の値を第２の秘密情報３０５（secret2）の値に更新し、第２の秘密情報３０５（secret2）の値を一時秘密情報（第３の秘密情報）（secret3）の値に更新する。
【０１１３】
Ｇ１−１−２) その他の場合、鍵交換装置は、待ち受け状態に戻る。
【０１１４】
Ｇ１−２) sync=1 あるいは sync=2とする。この場合、同期確認装置３１１は、自己の第１の同期検証値 y1 と自己の第２の同期検証値 y2 とを、第１の秘密情報３０４とセッション状態３０８とを用いて、次のように生成する。
y1 = HashS(secret1,P,kid,"非同期確認",sync)
y2 = HashS(secret3,P,kid,"非同期確認",sync).
【０１１５】
すなわち、同期確認装置３１１は、第１の秘密情報３０４（secret1）、自己識別子３０６（P）、自己の鍵識別子kid、および同期判定値syncに基いて、第１のハッシュ関数HashS を用いて、自己の第１の同期検証値 y1を生成する。また、同期確認装置３１１は、セッション状態３０８中の一時秘密情報（secret3）、自己識別子３０６（P）、自己の鍵識別子kid、および同期判定値syncに基いて、第１のハッシュ関数HashS を用いて、自己の第２の同期検証値y2を生成する。
【０１１６】
そして、鍵交換装置は、次の何れかの動作をする。
Ｇ１−２−１) (x'1,x'2)=(y1,y2)なら、秘密更新装置３１２は、秘密情報 (secret1,secret2) を(secret1,secret3) へ更新する。すなわち、秘密更新装置３１２は、第１の秘密情報３０４（secret1）の値をそのまま第１の秘密情報３０４（secret1）に維持し、第２の秘密情報３０５（secret2）の値を一時秘密情報（第３の秘密情報）（secret3）の値に更新する。
【０１１７】
Ｇ１−２−２) その他の場合、鍵交換装置は、待ち受け状態に戻る。
【０１１８】
次に、同期確認装置３１１は、セッション状態３０８を消去し、 (中止)を出装置３０１から出力する。その後、鍵交換装置は、待ち状態に戻る。
【０１１９】
Ｇ２） その他の場合、鍵交換装置は、受け取ったメッセージを無視する。
【０１２０】
次に図１０を参照して、鍵交換装置 が入力装置３００から(失効命令)が入力された場合の動作について説明する。この場合、鍵交換装置は、次の何れかの動作をする(処理8)。
【０１２１】
Ｈ１） もし何らかのセション状態３０８を保持している場合、鍵交換装置は、このセション状態を消去し、出力装置３０１から(失効)を出力し、待ち受け状態に戻る。
Ｈ２） その他の場合、鍵交換装置は、受け取ったメッセージを無視する。
【実施例２】
【０１２２】
次に、本発明の第２の実施例による、共有した秘密情報に基づく認証付鍵交換システムについて説明する。
【０１２３】
鍵交換システムは、上記第１の実施例に記載した二つの鍵交換装置からなる。それらの一方を第１の鍵交換装置と呼び、他方を第２の鍵交換装置と呼ぶことにする。第１および第２の鍵交換装置とも、通信路に接続されている。
【０１２４】
第１の鍵交換装置には、その初期設定において自己の識別子としてあるP が入力され、相手の識別子としてあるP' が入力される。また、 {0,1}κ からランダムに選ばれた、第１の秘密情報と第２の秘密情報が、それぞれ、 secret1, secret2 として格納される。以降、 この第１の鍵交換装置をP と呼ぶ。
【０１２５】
第２の鍵交換装置には、その初期設定において自己の識別子として先の P' が入力され、相手の識別子として先の P が入力される。 {0,1}κ からランダムに選ばれて、第１の鍵交換装置P に格納された二つの値と同じ値が、 secret1, secret2 として格納される。以降、この第２の鍵交換装置を P' と呼ぶ。
【０１２６】
第１の鍵交換装置P がメッセージを第２の鍵交換装置P' に送付する動作を行うと、このメッセージは前記通信路を伝って第２の鍵交換装置P' の通信装置に入力される。逆に、第２の鍵交換装置 P' がメッセージを第１の鍵交換装置P に送付する動作を行うと、このメッセージは前記通信路を伝って第１の鍵交換装置P の通信装置に入力される。
【０１２７】
以下、第１および第２の鍵交換装置が鍵識別子kid と鍵key とを出力する典型的な動作について説明する。但し、P とP' とは入れ替えても良い。
【０１２８】
第１の鍵交換装置P に(開始命令)が入力される。第１の鍵交換装置P は上記第１の実施例に記載される通りに動作し、開始要求メッセージ (P,"開始要求",sid,x1,x2) を第２の鍵交換装置 P' に送付し、開始要求情報("開始要求",sid,x1,x2) をセッション状態として保存し、待ち状態に戻る。
【０１２９】
第２の鍵交換装置P' は開始要求メッセージ (P,"開始要求",sid,x1,x2) を受け取る。第２の鍵交換装置P' は、上記第１の実施例に記載される通りに動作し、鍵交換装置P' は (開始要求受付) を出力し、応答待情報("応答待",sid,x1,x2,sync) をセッション状態と して保存し、待ち状態に戻る。
【０１３０】
第２の鍵交換装置P'に(応答命令)が入力される。第２の鍵交換装置P' は上記第１の実施例に記載される通りに動作し、秘密情報 (secret1,secret2) を (secret2,HashS(secret2,kid)) に更新し、セッション状態を応答情報("応答",kid,ver,key) へ更新し、kid を出力し、応答メッセージ (P',"応答",sid,sid',x'1,x'2) を第１の鍵交換装置P に送り、待ち状態に戻る。
【０１３１】
第１の鍵交換装置P は応答メッセージ (P',"応答",sid,sid',x'1,x'2) を受け取る。第１の鍵交換装置 P は、上記第１の実施例に記載される通りに動作し、秘密情報 (secret1,secret2) を (secret2,HashS(secret2,kid)) へ更新し、(kid) を出力し、(kid,key) を出力し、了解メッ セージ (P,"了解",sid,sid',ver) を第２の鍵交換装置P' へ送り、セッション状態を消去し、待ち状態に戻る。
【０１３２】
第２の鍵交換装置P' は了解メッセージ (P',"了解",sid,sid',ver') を受けとる。第２の鍵交換装置P' は上記第１の実施例に記載される通りに動作し、(kid,key) を出力し、セッション状態を消去し、待ち受け状態に戻る。
【０１３３】
次に、本発明の実施例の効果について説明する。
【０１３４】
秘密情報の更新は、ハッシュ関数にその秘密情報を入力して得られた結果を新たな秘密情報とする様に行う。この時、 ハッシュ関数に更新する前の秘密情報のみを入力するとすると、最初の秘密情報が漏れるとこれから未来の秘密情報が全て分かってしまう。そこで、本発明の実施例では、ハッシュ関数への入力に鍵識別子 kid が加わっているため、未来の秘密情報は確率的に決定される。このことにより、攻撃者が、全ての通信を盗聴することなく秘密情報を同期し続ける事は出来なくなる。また、鍵識別子は両方の参加者が生成する乱数からなるため、少なくとも一人が正直であれば、秘密情報は確率的に遷移する。
【０１３５】
秘密情報が確率的に遷移する場合、両方の参加者の秘密情報の同期が崩れてしまう可能性がある。そこで、本発明の実施例では第１の秘密情報と第２の秘密情報の二つを準備する。そして、第１の秘密情報と第２の秘密情報を更新したときに、更新する前の第２の秘密情報へと第１の秘密情報を更新する。この様にすることで、二人の参加者が第２の秘密情報を互いに異なるものへと更新してしまっても、第１の秘密情報から再度同じものを構築し直すことができる。
【０１３６】
片方の参加者が共有する秘密情報から鍵を生成して出力した時点で、この鍵生成に使った秘密情報が残存していると、この秘密情報を得た攻撃者が生成された秘密情報を知る可能性がある。それゆえ、鍵生成に用いた秘密情報は速やかに更新して消去する必要がある。特に、片方が鍵を生成して秘密情報を更新しても、他方がこの更新前の秘密情報を保持している様な事がないように注意する必要がある。一方、あまりに早急に秘密情報を更新すると、相手の秘密情報がどのように更新されるか十分に把握する前に自身の秘密情報を更新してしまい、両方の参加者の秘密情報の同期が壊れてしまう。
【０１３７】
この様な鍵の秘密保持と秘密情報の更新の確実性の両方を求めるには、両方の参加者で通信を何度も行って、両方の状況を確認しながら処理を進めれば良い。しかしながら、この様なことをすると、通信回数が多くなり効率的でない。
【０１３８】
そこで、本発明の実施例では、三回という最低限の通信回数で、先の問題を解決している。特に、鍵の安全性を確保するために、両方の参加者が同期している場合には、二回目のメッセージ送信を行う者はこの時に一回目と三回目のメッセージ送信を行う者は三回目のそのときに秘密情報の更新を行う。一方、秘密情報の同期がとれていない場合は、二回目のメッセージ送信を行う者は三回目のメッセージを受信してから、一回目と三回目のメッセージ送信を行うものは三回目のそのときに秘密情報の更新を行い、鍵の生成は行わずに秘密情報の同期のみを行う。この様に、鍵の生成を行うときと、秘密情報の同期を行うときで秘密情報の更新時期を違える事で、鍵の秘密の保持と秘密情報の更新の確実性の両方を、最小限の通信回数で成功している。
【０１３９】
以上、実施形態（実施例）を参照して本発明を説明したが、本発明は上記実施形態（実施例）に限定されるものではない。本発明の構成や詳細には、本発明のスコープ内で当業者が理解し得る様々な変更をすることができる。
【０１４０】
上記の実施形態の一部又は全部は、以下の付記のようにも記載されうるが、以下には限られない。
【０１４１】
（付記１）乱数を生成する乱数生成装置と、
第１の秘密情報と第２の秘密情報とを保持する秘密情報記憶装置と、
前記乱数生成装置を用いて生成した乱数と、相手装置から受信したデータとを用いて自己の鍵識別子を生成する鍵識別子生成装置と、
前記第１の秘密情報を用いて自己の第１の同期確認値を生成し、前記第２の秘密情報を用いて自己の第２の同期確認値を生成し、該自己の第１の同期確認値と前記自己の第２の同期確認値とを前記相手装置へ送出し、前記第１の秘密情報を用いて自己の第１の同期検証値を生成し、前記第２の秘密情報を用いて自己の第２の同期検証値を生成し、相手の第１の同期確認値と相手の第２の同期確認値とを前記相手装置から受信し、前記相手の第１の同期確認値および前記相手の第２の同期確認値と、前記自己の第１の同期検証値および前記自己の第２の同期検証値とを用いて、同期判定値を生成する同期確認装置と、
前記第１の秘密情報と前記第２の秘密情報と前記鍵識別子とを受け取り、前記第２の秘密情報と前記鍵識別子とから第３の秘密情報を生成し、前記第１の秘密情報の値を前記第２の秘密情報の値に変更し、前記第２の秘密情報の値を前記第３の秘密情報の値に変更する秘密更新装置と、
前記第１の秘密情報から鍵を生成する鍵生成装置と、
を備える鍵交換装置。
【０１４２】
（付記２）前記同期判定値は、前記相手の第１の同期確認値および前記相手の第２の同期確認値が、それぞれ、前記自己の第１の同期検証値および前記自己の第２の同期検証値と等しいなら、“同期”を示す０の値を持ち、前記相手の第１の同期確認値と前記自己の第２の同期検証値とが等しいなら、−１の値を持ち、前記相手の第２の同期確認値と前記自己の第１の同期検証値とが等しいなら、１の値を持ち、前記相手の第１の同期確認値と前記自己の第１の同期検証値とが等しく、かつ、前記相手の第２の同期確認値と前記自己の第２の同期検証値とが等しくないとき、２の値を持ち、
前記同期確認装置は、
前記同期判定値の値が−１に等しいとき、前記第２の秘密情報と前記鍵識別子とから前記第３の秘密情報を生成し、前記第２の秘密情報を用いて前記自己の第１の同期確認値を生成し、前記第３の秘密情報を用いて前記自己の第２の同期確認値を生成する機能と、
前記同期判定値の値が１又は２に等しいとき、前記第１の秘密情報と前記鍵識別子とから前記第３の秘密情報を生成し、前記第１の秘密情報を用いて前記自己の第１の同期確認値を生成し、前記第３の秘密情報を用いて前記自己の第２の同期確認値を生成する機能と、
前記同期判定値の値が１に等しいとき、前記第２の秘密情報と前記鍵識別子とから前記第３の秘密情報を生成し、前記第２の秘密情報を用いて前記自己の第１の同期検証値を生成し、前記第３の秘密情報を用いて前記自己の第２の同期検証値を生成する機能と、
前記同期判定値の値が−１又は２に等しいとき、前記第１の秘密情報と前記鍵識別子とから前記第３の秘密情報を生成し、前記第１の秘密情報を用いて前記自己の第１の同期検証値を生成し、前記第３の秘密情報を用いて前記自己の第２の同期検証値を生成する機能と、
をさらに備える、ことを特徴とする付記１に記載の鍵交換装置。
【０１４３】
（付記３）付記１に記載の鍵交換装置二つからなる鍵交換システムであって、
第１の鍵交換装置が保持する自己識別子と第２の鍵交換装置が保持する相手識別子とが同一で、
前記第１の鍵交換装置が保持する相手識別子と前記第２の鍵交換装置が保持する自己識別子とが同一であり、
前記第１の鍵交換装置と前記第２の鍵交換装置とは通信路で繋がっており、
前記第１の鍵交換装置が送出するメッセージを前記第２の鍵交換装置が受信可能であり、
前記第２の鍵交換装置が送出するメッセージを前記第１の鍵交換装置が受信可能であり、
何れかの鍵交換装置には、開始命令、応答命令を入力する事が出来る
ことを特徴とする鍵交換システム。
【０１４４】
（付記４）前記第１の鍵交換装置は、前記開始命令が入力されると、その前記同期確認装置が、前記第１の秘密情報および前記第２の秘密情報を用いて、前記自己の第１の同期確認値および前記自己の第２の同期確認値を生成し、前記自己の第１の同期確認値および前記自己の第２の同期確認値を含む開始要求メッセージを、前記第２の鍵交換装置へ送出する、付記３に記載の鍵交換システム。
【０１４５】
（付記５）前記第２の鍵交換装置は、前記開始要求メッセージを受け取ると、その前記同期確認装置が、前記第１の秘密情報および前記第２の秘密情報を用いて、自己の第１の同期検証値および自己の第１の同期検証値を生成し、前記開始要求メッセージに含まれる相手の第１の同期確認値および相手の第２の同期確認値と前記自己の第１の同期検証値および前記自己の第１の同期検証値とを用いて同期判定値を生成する、付記４に記載の鍵交換システム。
【０１４６】
（付記６）前記第２の鍵交換装置は、前記応答命令が入力されると、その前記鍵識別子生成装置が、その前記乱数生成装置で生成された乱数と前記開始要求メッセージに含まれるデータとを用いて自己の鍵識別子を生成し、
前記第２の鍵交換装置は、前記同期判定値が“同期”を示しているなら、その前記鍵生成装置が、前記第１の秘密情報から鍵を生成し、その秘密更新装置が、前記第１の秘密情報の値および前記第２の秘密情報の値を、それぞれ、前記第２の秘密情報の値および前記前記第３の秘密情報の値に変更する、付記５に記載の鍵交換システム。
【０１４７】
（付記７）前記第２の鍵交換装置は、前記同期判定値が“同期”を示しているなら、その前記同期確認装置は、前記自己の鍵識別子、前記第１の秘密情報、および前記第２の秘密情報を用いて、自己の第１の同期確認値および自己の第２の同期確認値を生成し、前記自己の第１の同期確認値および前記自己の第２の同期確認値を含む応答メッセージを、前記第１の鍵交換装置へ送出する、付記６に記載の鍵交換システム。
【０１４８】
（付記８）前記第１の鍵交換装置は、前記応答メッセージを受け取ると、その前記鍵識別子生成装置が、該応答メッセージに含まれるデータから自己の鍵識別子を生成し、その前記同期確認装置が、前記自己の鍵識別子、前記第１の秘密情報、および前記第２の秘密情報を用いて、自己の第１の同期検証値および自己の第２の同期検証値を生成する、付記７に記載の鍵交換システム。
【０１４９】
（付記９）前記第１の鍵交換装置は、前記応答メッセージに含まれる相手の第１の同期確認値および相手の第２の同期確認値が、それぞれ、前記自己の第１の同期検証値および前記自己の第２の同期検証値に等しいとき、その前記鍵生成装置が、前記第１の秘密情報から鍵を生成し、その秘密更新装置が、前記第１の秘密情報の値および前記第２の秘密情報の値を、それぞれ、前記第２の秘密情報の値および前記前記第３の秘密情報の値に変更する、付記８に記載の鍵交換システム。
【０１５０】
（付記１０）第１の鍵交換装置と第２の鍵交換装置との間で鍵の交換を行う鍵交換方法であって、
開始命令を入力したとき、前記第１の鍵交換装置が、第１の秘密情報および第２の秘密情報を用いて、それぞれ、自己の第１の同期確認値および自己の第２の同期確認値を生成し、前記自己の第１の同期確認値および前記自己の第２の同期確認値を含む開始要求メッセージを前記第２の鍵交換装置へ送信する工程と、
前記第１の鍵交換装置から相手の第１の同期確認値および相手の第２の同期確認値を含む前記開始要求メッセージを受け取ったとき、前記第２の鍵交換装置が、前記第１の秘密情報および前記第２の秘密情報を用いて、それぞれ、自己の第１の同期検証値および自己の第２の同期検証値を生成し、前記相手の第１の同期確認値、前記相手の第２の同期確認値、前記自己の第１の同期検証値、および前記自己の第２の同期検証値を用いて同期判定値を生成する工程と、
を含む、鍵交換方法。
【０１５１】
（付記１１）応答命令を入力したとき、前記第２の鍵交換装置が、乱数生成装置を用いて生成した乱数と前記開始要求メッセージに含まれるデータとを用いて、自己の鍵識別子を生成する工程を含む、付記１０に記載の鍵交換方法。
【０１５２】
（付記１２）前記同期判定値が“同期”を示しているなら、前記第２の鍵交換装置が、前記第１の秘密情報から鍵を生成し、前記第２の秘密情報と前記自己の鍵識別子とから第３の秘密情報を生成し、前記第１の秘密情報の値を前記第２の秘密情報の値に更新し、前記第２の秘密情報の値を前記第３の秘密情報の値に更新する工程を含む、請求項１１に記載の鍵交換方法。
【０１５３】
（付記１３）前記同期判定値が“同期”を示しているなら、前記第２の鍵交換装置が、前記自己の鍵識別子、前記第１の秘密情報、および前記第２の秘密情報を用いて、自己の第１の同期確認値および自己の第２の同期確認値を生成し、前記自己の第１の同期確認値および前記自己の第２の同期確認値を含む応答メッセージを前記第１の鍵交換装置へ送信する工程を含む、付記１１又は１２に記載の鍵交換方法。
【０１５４】
（付記１４）前記第２の鍵交換装置から相手の第１の同期確認値および相手の第２の同期確認値を含む前記応答メッセージを受け取ったとき、前記第１の鍵交換装置が、該応答メッセージに含まれるデータから鍵識別子を生成し、該生成した鍵識別子、前記第１の秘密情報、および前記第２の秘密情報を用いて、自己の第１の同期検証値および自己の第２の同期検証値を生成する工程を含む、付記１３に記載の鍵交換方法。
【０１５５】
（付記１５）前記相手の第１の同期確認値および前記相手の第２の同期確認値が、それぞれ、前記自己の第１の同期検証値および前記自己の第２の同期検証値と等しいとき、前記第１の鍵交換装置が、前記第１の秘密情報から鍵を生成し、前記第２の秘密情報と前記鍵識別子とから第３の秘密情報を生成し、前記第１の秘密情報の値を前記第２の秘密情報の値に更新し、前記第２の秘密情報の値を前記第３の秘密情報の値に更新する工程を含む、請求項１４に記載の鍵交換方法。
【０１５６】
（付記１６）前記同期判定値が“非同期”を示しているなら、前記第２の鍵交換装置が、前記第１の秘密情報および前記第２の秘密情報を用いて、一時秘密情報、自己の第１の同期確認値、自己の第２の同期確認値を生成し、前記自己の第１の同期確認値、前記自己の第２の同期確認値、および前記同期判定値を含む非同期メッセージを前記第１の鍵交換装置へ送出する工程を含む、付記１０に記載の鍵交換方法。
【０１５７】
（付記１７）前記第２の鍵交換装置から前記同期判定値、相手の第１の同期確認値、および相手の第２の同期確認値を含む前記非同期メッセージを受け取ったとき、前記第１の鍵交換装置が、該非同期メッセージに含まれるデータから自己の鍵識別子を生成し、該生成した自己の鍵識別子、前記第１の秘密情報、および前記第２の秘密情報を用いて、自己の第１の同期検証値および自己の第２の同期検証値を生成する工程を含む、付記１６に記載の鍵交換方法。
【０１５８】
（付記１８）前記相手の第１の同期確認値および前記相手の第２の同期確認値が、それぞれ、前記自己の第１の同期検証値および前記自己の第２の同期検証値に等しいなら、前記第１の鍵交換装置が、前記同期判定値の値に応じて、前記第１の秘密情報の値と前記第２の秘密情報の値とを更新する工程を含む、付記１７に記載の鍵交換方法。
【０１５９】
（付記１９）前記第１の鍵交換装置が、前記自己の鍵識別子、前記第１の秘密情報、および前記第２の秘密情報を用いて、自己の第１の同期確認値および自己の第２の同期確認値を生成し、前記同期判定値、前記自己の第１の同期確認値および前記自己の第２の同期確認値を含む非同期確認メッセージを、前記第２の鍵交換装置へ送出する工程を含む、付記１７又は１８に記載の鍵交換方法。
【０１６０】
（付記２０）前記第１の鍵交換装置から、相手の第１の同期確認値および相手の第２の同期確認値を含む前記非同期確認メッセージを受け取ったとき、前記第２の鍵交換装置が、前記自己の鍵識別子、前記一時秘密情報、および前記第１の秘密情報又は前記第２の秘密情報を用いて、自己の第１の同期検証値および自己の第２の同期検証値を生成し、前記相手の第１の同期確認値および前記相手の第２の同期確認値が、それぞれ、前記自己の第１の同期検証値および前記自己の第２の同期検証値に等しいとき、前記同期判定値の値に応じて、前記第１の秘密情報の値と前記第２の秘密情報の値とを更新する工程を含む、付記１９に記載の鍵交換方法。
【０１６１】
（付記２１）乱数を生成する手順と、
第１の秘密情報と第２の秘密情報とを保持する手順と、
前記生成された乱数と、相手装置から受信したデータとを用いて自己の鍵識別子を生成する手順と、
前記第１の秘密情報を用いて自己の第１の同期確認値を生成し、前記第２の秘密情報を用いて自己の第２の同期確認値を生成し、該自己の第１の同期確認値と前記自己の第２の同期確認値とを前記相手装置へ送出し、前記第１の秘密情報を用いて自己の第１の同期検証値を生成し、前記第２の秘密情報を用いて自己の第２の同期検証値を生成し、相手の第１の同期確認値と相手の第２の同期確認値とを前記相手装置から受信し、前記相手の第１の同期確認値および前記相手の第２の同期確認値と、前記自己の第１の同期検証値および前記自己の第２の同期検証値とを用いて、同期判定値を生成する手順と、
前記第１の秘密情報と前記第２の秘密情報と前記鍵識別子とを受け取り、前記第２の秘密情報と前記鍵識別子とから第３の秘密情報を生成し、前記第１の秘密情報の値を前記第２の秘密情報の値に変更し、前記第２の秘密情報の値を前記第３の秘密情報の値に変更する手順と、
前記第１の秘密情報から鍵を生成する手順と、
をコンピュータに実行させる鍵交換プログラム。
【０１６２】
（付記２２）前記同期判定値は、前記相手の第１の同期確認値および前記相手の第２の同期確認値が、それぞれ、前記自己の第１の同期検証値および前記自己の第２の同期検証値と等しいなら、“同期”を示す０の値を持ち、前記相手の第１の同期確認値と前記自己の第２の同期検証値とが等しいなら、−１の値を持ち、前記相手の第２の同期確認値と前記自己の第１の同期検証値とが等しいなら、１の値を持ち、前記相手の第１の同期確認値と前記自己の第１の同期検証値とが等しく、かつ、前記相手の第２の同期確認値と前記自己の第２の同期検証値とが等しくないとき、２の値を持ち、
前記同期判定値を生成する手順は、
前記同期判定値の値が−１に等しいとき、前記第２の秘密情報と前記鍵識別子とから前記第３の秘密情報を生成し、前記第２の秘密情報を用いて前記自己の第１の同期確認値を生成し、前記第３の秘密情報を用いて前記自己の第２の同期確認値を生成する手順と、
前記同期判定値の値が１又は２に等しいとき、前記第１の秘密情報と前記鍵識別子とから前記第３の秘密情報を生成し、前記第１の秘密情報を用いて前記自己の第１の同期確認値を生成し、前記第３の秘密情報を用いて前記自己の第２の同期確認値を生成する手順と、
前記同期判定値の値が１に等しいとき、前記第２の秘密情報と前記鍵識別子とから前記第３の秘密情報を生成し、前記第２の秘密情報を用いて前記自己の第１の同期検証値を生成し、前記第３の秘密情報を用いて前記自己の第２の同期検証値を生成する手順と、
前記同期判定値の値が−１又は２に等しいとき、前記第１の秘密情報と前記鍵識別子とから前記第３の秘密情報を生成し、前記第１の秘密情報を用いて前記自己の第１の同期検証値を生成し、前記第３の秘密情報を用いて前記自己の第２の同期検証値を生成する手順と、
をさらに前記コンピュータに実行させる、付記２１に記載の鍵交換プログラム。
【符号の説明】
【０１６３】
３００ ・・・ 入力装置
３０１ ・・・ 出力装置
３０２ ・・・ 通信装置
３０３ ・・・ 乱数生成装置
３０４ ・・・ 第１の秘密情報
３０５ ・・・ 第２に秘密情報
３０６ ・・・ 自己識別子
３０７ ・・・ 相手識別子
３０８ ・・・ セッション状態
３０９ ・・・ セッション番号生成装置
３１０ ・・・ 鍵識別子生成装置
３１１ ・・・ 同期確認装置
３１２ ・・・ 秘密更新装置
３１３ ・・・ 鍵生成装置
３１４ ・・・ 鍵検証装置
３２０ ・・・ 識別子記憶装置
３２２ ・・・ 秘密情報記憶装置
３２４ ・・・ 記憶装置
【技術分野】
【０００１】
本発明は、鍵交換装置及び鍵交換システムに関し、特に、共有した秘密情報に基づく認証付鍵交換装置及びシステムに関する。
【背景技術】
【０００２】
鍵交換方式には二つの装置が参加し、これら二つの装置が互いに通信することにより、同一の鍵を共有する。特に、各装置が自分である事の認証を受ける方法を備えていて、鍵を交換した相手の装置を認証する方式を、「認証付き鍵交換方式」と呼ぶ。
【０００３】
従来の認証付き鍵交換方式として、非特許文献１に記されている方式があげられる。
【０００４】
図１に、従来の認証付き鍵交換方式の概略を示す。
【０００５】
認証付き鍵交換方式は、第１の鍵交換装置１００と、第２の鍵交換装置２００とを備え、これらの間で鍵を交換するものである。ここでは、第１の鍵交換装置１００は自己の識別子としてΠを有し、第２の鍵交換装置２００は自己の識別子としてΠ'を有する。図１に示されるように、第１の鍵交換装置１００と第２の鍵交換装置２００とは、実質的に同様の構成を有する。
【０００６】
詳述すると、第１の鍵交換装置１００は、入力装置１０１、乱数入力装置１０２、認証装置１０４、通信装置１０５、記憶装置１０３、および出力装置１０６を備える。同様に、第２の交換装置２００は、入力装置２０１、乱数入力装置２０２、認証装置２０４、通信装置２０５、記憶装置２０３、および出力装置２０６を備える。したがって、説明を簡略化するために、以下では、第１の鍵交換装置１００を代表として、単に鍵交換装置と記して、説明する。
【０００７】
鍵交換装置１００は、入力装置１０１から、Gを巡回群、qをGの位数、gをGの生成子、Hashをハッシュ関数として、システムパラメター１０７(q,G,g,Hash)と、識別子Πである自己識別子１０８とが入力されて、起動され命令待ち状態となる。
【０００８】
この状態において、識別子Πを持つ命令待ち状態の鍵交換装置１００に、入力装置１０１から、鍵交換開始命令１０９、sidのセッション番号１１２、および識別子Π'である相手識別子１１０が入力されたとする。この場合、次のように鍵交換装置１００の第一ラウンド装置１２０が動作する。ここで、sidは、識別子ΠとΠ'が鍵交換に使う数としては、唯一無二の数であることが期待される。
【０００９】
先ず、第一ラウンド装置１２０は、乱数入力装置１０２より乱数１１１を取り込む。
次に、第一ラウンド装置１２０は、暫定数 r ∈ Z/qZを乱数１１１からランダムに生成する。
【００１０】
第一ラウンド装置１２０は、y = grを生成する。yを冪乗数と呼ぶ。
第一ラウンド装置１２０は、状態 (sid, Π',r) を生成して、これを記憶装置１０３する。
第一ラウンド装置１２０は、("生成",(sid,y))を認証装置１０４に入力し、識別子sigを得る。
第一ラウンド装置１０２は、メッセージ(sid,y,sig) を通信装置１０５を用いて、送信者が識別子Πで、宛先が識別子Π'であるとして送信する。
そして、鍵交換装置１００は命令待ち状態となる。
【００１１】
この状態において、識別子Πを持つ命令待ち状態の鍵交換装置１００が、通信装置１０５を通じて、送信者が識別子Π' で、宛先が識別子Πであるメッセージ (sid,y',sig')を受信したとする。この場合、鍵交換装置１００の鍵生成装置１２１は、次のように動作する。
【００１２】
先ず、鍵生成装置１２１は、記憶装置１０３に保存されている状態を調べる。ここで、記憶装置１０３が、いかなる y,r に対しても、状態 (sid,y,r)を記憶していないとする。その場合には、鍵生成装置１２１は、鍵交換装置１００を直ちに命令待ち状態とする。
【００１３】
一方、記憶装置１０３がある y,r に対して、状態(sid,y,r) を記憶していたとする。この場合、鍵生成装置１２１は、 ("検証",Π',(sid,y'),sig' )を認証装置１０４に入力する。認証装置１０４が"不当"を出力した場合、鍵生成装置１２は、鍵交換装置１００を直ちに命令待ち状態とする。
【００１４】
そうでない場合、鍵生成装置１２１は、記憶装置１０３にある状態(sid,Π',y,r)を完全に消去し、冪乗数 y を用いて (sid,z=y'r) を生成し、それを出力装置１０６に出力する。
この出力装置１０６に出力された(sid,z=y'r)が、交換結果（鍵）１２２である。
【００１５】
また、本発明に関連する先行技術文献として、特許第４１０９１６４号公報（特許文献１）が知られている。この特許文献１は、容易に生成でき、かつ、他人から極めて類推され難く、さらに使用者本人が鍵を紛失した場合でも同じ鍵を安全に生成できる「暗号鍵の生成システム」を開示している。この特許文献１に開示された暗号鍵の生成システムでは、第１情報及び第２情報と、会社を識別するための識別子と、暗号鍵の識別子とに基づいて、ハッシュ関数を用いて暗号鍵を生成している。この特許文献１において、第１情報は「キーワード」であり、第２情報は「パスワード」である。
【先行技術文献】
【特許文献】
【００１６】
【特許文献１】特許第４１０９１６４号公報
【非特許文献】
【００１７】
【非特許文献１】Ran Canetti, Hugo Krawczyk."Universally Composable Notions of Key Exchange and Secure Channels",Advances in Cryptology - EUROCRYPT 2002, International Conference on the Theory and Applications of Cryptographic Techniques, Amsterdam, The Netherlands, April 28 - May 2, 2002, Proceedings, pages 337-351, Springer, Lecture Notes in Computer Science, volume 2332, year 2002.
【発明の概要】
【発明が解決しようとする課題】
【００１８】
図１に示した従来技術の認証付き鍵交換方式には、次に述べるような問題点がある。
【００１９】
第一の問題点は、従来技術の鍵交換方式の安全性が Diffie-Hellman 鍵交換の安全性に依存していることである。何故なら、 Diffie-Hellman 鍵交換は量子計算機の実現や新しいアルゴリズムの発見により、安全でなくなる可能性があるからである。
【００２０】
第二の問題点は、従来技術はDiffie-Hellman 鍵交換等、公開鍵暗号の技術に依存しており、計算量が大きいことである。
【００２１】
これらの問題点を解決するために、あらかじめ秘密情報を両者で共有しておき、これからハッシュ関数等で、新たな鍵を生成する事も可能である。但し、セッション毎に異なる鍵を生成し、ある時点で共有する秘密情報が漏れてもそれまでに使った鍵が分からないようにする為に、共有する秘密情報をハッシュ関数などを用いて更新していく必要がある。この時、以下の問題が発生あるいは問題の発生に注意しなければならない。
【００２２】
(1) 秘密情報の更新が決定的に行われると、初期の秘密情報から未来の鍵が全て分かってしまう。このため、気が付かない秘密情報の盗難が起きると被害が大きくなる。
(2) 秘密情報の更新を確率的に行うと、両者の秘密情報の同期を妨害する攻撃が可能となる可能性がある。また、この妨害を防ぐために通信回数が多くなっしまう。
(3) ある時点で秘密情報が盗まれたとき、秘密情報の更新が十分でないと、直前の鍵が漏洩してしまう。
【００２３】
尚、特許文献１は、暗号鍵の識別子等に基づいて、ハッシュ関数を用いて暗号鍵を生成する技術的思想を開示している。しかしながら、特許文献１は、暗号鍵を生成するシステムを開示しているだけであって、二つの装置が互いに通信することにより、同一の鍵を共有する鍵交換システムとは異なる。
【００２４】
本発明の目的は、最小限の通信回数で、鍵の秘密の保持と秘密情報の更新の確実性とを確保できる、鍵交換装置及び鍵交換システムを提供することにある。
【課題を解決するための手段】
【００２５】
本発明による鍵交換装置は、乱数を生成する乱数生成装置と；本人識別子と相手識別子とを保持する識別子記憶装置と；第１の秘密情報と第２の秘密情報とを保持する秘密情報記憶装置と；乱数生成装置を用いて生成した乱数と、相手装置から受信したデータとを用いて鍵識別子を生成する鍵識別子生成装置と；第１の秘密情報を用いて自己の第１の同期確認値を生成し、第２の秘密情報を用いて自己の第２の同期確認値を生成し、この生成した自己の第１の同期確認値と生成した自己の第２の同期確認値とを相手装置へ送出し、第１の秘密情報を用いて第１の同期検証値を生成し、第２の秘密情報を用いて第２の同期検証値を生成し、相手の第１の同期確認値と相手の第２の同期確認値とを相手装置から受信し、受信した相手の第１の同期確認値および受信した相手の第２の同期確認値と、生成した第１の同期検証値および生成した第２の同期検証値とを用いて、同期判定値を生成する同期確認装置と；第１の秘密情報と第２の秘密情報と鍵識別子とを受け取り、第２の秘密情報と鍵識別子とから第３の秘密情報を生成し、第１の秘密情報の値を第２の秘密情報の値に変更し、第２の秘密情報の値を第３の秘密情報の値に変更する秘密更新装置と；第１の秘密情報から鍵を生成する鍵生成装置と；を備える。
【発明の効果】
【００２６】
本発明によれば、最小限の通信回数で、鍵の秘密の保持と秘密情報の更新の確実性とを確保できる。
【図面の簡単な説明】
【００２７】
【図１】従来の鍵交換方式の構成を示すブロック図である。
【図２】本発明の第１の実施例に係る鍵交換装置を示すブロック図である。
【図３】図２に示した鍵交換装置において、“開始命令”が入力された場合の処理を示したブロック図である。
【図４】図２に示した鍵交換装置において、“開始要求”を含んだメッセージを受信した場合の処理を示したブロック図である。
【図５】図２に示した鍵交換装置において、“応答命令”が入力された場合の処理を示したブロック図である。
【図６】図２に示した鍵交換装置において、“応答”を含んだメッセージを受信した場合の処理を示したブロック図である。
【図７】図２に示した鍵交換装置において、“非同期”を含んだメッセージを受信した場合の処理を示したブロック図である。
【図８】図２に示した鍵交換装置において、“了解”を含んだメッセージを受信した場合の処理を示したブロック図である。
【図９】図２に示した鍵交換装置において、“非同期確認”を含んだメッセージを受信した場合の処理を示したブロック図である。
【図１０】図２に示した鍵交換装置において、“失効命令”が入力された場合の処理を示したブロック図である。
【発明を実施するための形態】
【００２８】
本発明の実施形態に係る鍵交換装置は、乱数を生成する乱数生成装置と、本人識別子と相手識別子とを保持する識別子記憶装置と、第１の秘密情報と第２の秘密情報とを保持する秘密情報記憶装置と、鍵識別子生成装置と、同期確認装置と、秘密更新装置と、第１の秘密情報から鍵を生成する鍵生成装置と、を備える。
【００２９】
鍵識別子生成装置は、乱数生成装置を用いて生成した乱数と、相手装置から受信したデータとを用いて鍵識別子を生成する機能を有する。
【００３０】
同期確認装置は、第１の秘密情報を用いて自己の第１の同期確認値を生成し、第２の秘密情報を用いて自己の第２の同期確認値を生成する機能と、この生成した自己の第１の同期確認値と生成した自己の第２の同期確認値とを相手装置へ送出する機能と、第１の秘密情報を用いて第１の同期検証値を生成し、第２の秘密情報を用いて第２の同期検証値を生成する機能と、相手の第１の同期確認値と相手の第２の同期確認値とを相手装置から受信する機能と、受信した相手の第１の同期確認値および受信した相手の第２の同期確認値と、生成した第１の同期検証値および生成した第２の同期検証値とを用いて、同期判定値を生成する機能とを有する。
【００３１】
秘密更新装置は、第１の秘密情報と第２の秘密情報と鍵識別子とを受け取り、第２の秘密情報と鍵識別子とから第３の秘密情報を生成し、第１の秘密情報の値を第２の秘密情報の値に変更し、第２の秘密情報の値を第３の秘密情報の値に変更する機能を有する。
【００３２】
秘密情報の更新を、ハッシュ関数にその秘密情報を入力して得られた結果を新たな秘密情報とする様に行うとする。この時、ハッシュ関数に更新する前の秘密情報のみを入力するとすると、最初の秘密情報が漏れるとこれから未来の秘密情報が全て分かってしまう。そこで、本発明の実施形態では、ハッシュ関数への入力に鍵識別子 kid を加わえて、未来の秘密情報を確率的に決定している。このことにより、攻撃者が、全ての通信を盗聴することなく秘密情報を同期し続ける事は出来なくなる。また、鍵識別子は両方の参加者が生成する乱数からなるため、少なくとも一人が正直であれば、秘密情報は確率的に遷移する。
【００３３】
また、秘密情報が確率的に遷移する場合、両方の参加者の秘密情報の同期が崩れてしまう可能性がある。そこで、本発明の実施形態では、秘密情報として、第１の秘密情報と第２の秘密情報との二つの秘密情報を準備する。そして、第１の秘密情報と第２の秘密情報とを更新したときに、更新する前の第２の秘密情報へと第１の秘密情報を更新する。この様にすることで、二人の参加者が第２の秘密情報を互いに異なるものへと更新してしまっても、第１の秘密情報から再度同じものを構築し直すことができる。
【００３４】
更に、片方の参加者が共有する秘密情報から鍵を生成して出力した時点で、この鍵生成に使った秘密情報が残存していると、この秘密情報を得た攻撃者が生成された秘密情報を知る可能性がある。それゆえ、鍵生成に用いた秘密情報は速やかに更新して消去する必要がある。特に、片方が鍵を生成して秘密情報を更新しても、他方がこの更新前の秘密情報を保持している様な事がないように注意する必要がある。一方、あまりに早急に秘密情報を更新すると、相手の秘密情報がどのように更新されるか十分に把握する前に自身の秘密情報を更新してしまい、両方の参加者の秘密情報の同期が壊れてしまう。
【００３５】
この様な鍵の秘密保持と秘密情報の更新の確実性の両方を求めるには、両方の参加者で通信を何度も行って、両方の状況を確認しながら処理を進めれば良い。しかしながら、この様なことをすると、通信回数が多くなり効率的でない。
【００３６】
そこで、本発明の実施形態では、三回という最低限の通信回数で、先の問題を解決している。特に、鍵の安全性を確保するために、両方の参加者が同期している場合には、次のようなタイミングで秘密情報の更新を行う。すなわち、二回目のメッセージ送信を行う者はこの時に秘密情報の更新を行い、一回目と三回目のメッセージ送信を行う者は三回目のそのときに秘密情報の更新を行う。一方、秘密情報の同期がとれていない場合は、次のようなタイミングで秘密情報の更新を行う。すなわち、二回目のメッセージ送信を行う者は三回目のメッセージを受信してから、一回目と三回目のメッセージ送信を行うものは三回目のそのときに、秘密情報の更新を行い、鍵の生成は行わずに秘密情報の同期のみを行う。この様に、鍵の生成を行うときと、秘密情報の同期を行うときとで、秘密情報の更新時期を違える事で、鍵の秘密の保持と秘密情報の更新の確実性の両方とを、最小限の通信回数で成功している。
【実施例１】
【００３７】
以下、図面を参照して、本発明の第１の実施例による、共有した秘密情報に基づく認証付鍵交換装置について説明する。
【００３８】
図２は、本発明の第１の実施例による鍵交換装置を示すブロック図である。
【００３９】
鍵交換装置は、入力装置３００と、出力装置３０１と、通信装置３０２とを備える。以下の説明では、次のことを定義する。「鍵交換装置にあるデータが入力される」とは、鍵交換装置の入力装置３００にこのデータが書き込まれる事を意味する。「鍵交換装置があるデータを出力する」とは、鍵交換装置の出力装置３０１がこのデータを鍵交換装置の外の媒体に書き出すことを意味する。「鍵交換装置があるデータを受け取る」とは、鍵交換装置の通信装置３０２にこのデータが書き込まれる事を意味する。「鍵交換装置があるデータを送付する」とは、鍵交換装置の通信装置３０２がこのデータを通信路に書き込む事を意味する。
【００４０】
鍵交換装置は乱数生成装置３０３を備える。この乱数生成装置３０３は、外から何らかの情報を受け入れて乱数を生成し、ランダムに値を選ぶ場合に、このランダム性の源として利用する。
【００４１】
鍵交換装置は、セッション番号生成装置３０９、鍵識別子生成装置３１０、同期確認装置３１１、秘密更新装置３１２、鍵生成装置３１３、および鍵検証装置３１４も備える。
【００４２】
(初期設定)
鍵交換装置は、安全変数κに関する、独立なハッシュ関数 HashS:{0,1}* → {0,1}κ, HashC:{0,1}* → {0,1}κ, HashK:{0,1}* → K, を実現する機能を備えているとする。ここで、Kは認証付鍵交換で生成される鍵の空間である。また、ハッシュ関数HashS は第１のハッシュ関数と呼ばれ、ハッシュ関数HashKは第２のハッシュ関数と呼ばれ、ハッシュ関数HashCは第３のハッシュ関数と呼ばれる。第１のハッシュ関数HashS は、同期確認／検証に用いられるので、同期確認／検証用ハッシュ関数とも呼ばれる。第２のハッシュ関数HashKは、鍵生成に用いられるので、鍵生成用ハッシュ関数とも呼ばれる。第３のハッシュ関数HashCは、鍵検証に用いられるので、鍵検証用ハッシュ関数とも呼ばれる。
【００４３】
また、以下の説明では、自己の情報と相手の情報とを区別するために、相手の情報には右肩にダッシュ「’」を付しているが、自己の情報には、このようなダッシュ「’」を付していない。
【００４４】
鍵交換装置には、自己の識別子Pである自己識別子３０６と、相手の識別子P'である相手識別子３０７とが設定される。換言すれば、鍵交換装置は、自己識別子３０５と相手識別子３０７とを保持する識別子記憶装置３２０を備えている。
【００４５】
鍵交換装置には、自己カウンタOCTR=0 と、相手カウンタPCTR=0とが設定される。
【００４６】
鍵交換装置には、第１の秘密情報３０４としてのsecret1 ∈{0,1}κと、第２の秘密情報３０５としてのsecret2 ∈{0,1}κ とが、秘密情報として格納される。換言すれば、鍵交換装置は、第１の秘密情報３０４と第２の秘密情報３０５とを保持する秘密情報記憶装置３２２を備えている。尚、図２では、第１の秘密情報３０４（secret1）を“秘密１”と記してあり、第２の秘密情報３０５（secret2）を“秘密２”と記してある。
【００４７】
鍵交換装置にはセッション状態３０８を保存する記憶装置３２４が確保される。セッション状態３０８の初期状態は“空”である。
【００４８】
このようにして、初期設定が終わった鍵交換装置は、待ち状態におかれる。待ち状態の鍵交換装置は、メッセージが入力されるあるいはメッセージを受け取った場合、その内容により処理を選択３１５して行い、再び待ち状態に戻る。
【００４９】
図３乃至図１０は、それぞれ、入力されるあるいは受け取るメッセージが、"開始命令"、"開始要求"、"応答命令"、"応答"、"非同期"、"了解"、"非同期確認"、および"失効命令"である場合の鍵交換装置の処理を示したブロック図である。図３乃至図１０では、それぞれの処理を、順番に処理１、処理２、処理３、処理４、処理５、処理６、処理７、および処理８と記して示している。
【００５０】
図３を参照して、鍵交換装置に(開始命令)が入力装置３００から入力された場合の動作について説明する。この場合、鍵交換装置は、次の何れかの動作をする(処理１)。
【００５１】
Ａ１） もしセッション状態を保持していないならば、セッション番号生成装置３０９は自己開始者カウンタ ictr= OCTR とし、OCTRをOCTR+1に変更し、自己セッション番号 sid ∈ {0,1}κ をランダムに選ぶ。すなわち、セッション番号生成装置３０９は、乱数生成装置３０３で生成された乱数を、自己セッション番号 sidとしてランダムに選ぶ。そして、同期確認装置３１１は、自己の第1の同期確認値x1と自己の第2の同期確認値x2とを、第１の秘密情報３０４と第２の秘密情報３０５とを用いて、次のように生成する。
x1 = HashS(secret1,P,ictr,sid,"開始要求")
x2 = HashS(secret2,P,ictr,sid,"開始要求").
【００５２】
すなわち、同期確認装置３１１は、第１の秘密情報３０４（secret1）、自己識別子３０６（P）、自己開始者カウンタ（ictr）、および自己セッション番号（sid）に基づいて、第１のハッシュ関数HashSを用いて、自己の第１の同期確認値x1を生成する。また、同期確認装置３１１は、第２の秘密情報３０５（secret2）、自己識別子３０６（P）、自己開始者カウンタ（ictr）、および自己セッション番号（sid）に基づいて、第１のハッシュ関数HashSを用いて、自己の第2の同期確認値x2を生成する。
【００５３】
そして、同期確認装置３３１は、自己識別子３０６（P）、自己開始者カウンタ（ictr）、自己セッション番号（sid）、自己の第１の同期確認値x1、および自己の第2の同期確認値x2を含む、開始要求メッセージ (P,"開始要求",ictr,sid,x1,x2) を、通信装置３０２から、相手の識別子P'を持つ相手側の鍵交換装置に送付し、自己開始者カウンタ（ictr）、自己セッション番号（sid）、自己の第１の同期確認値x1、および自己の第2の同期確認値x2を含む、開始要求情報("開始要求",ictr,sid,x1,x2) をセッション状態３０８として記憶装置３２４に保存する。その後、鍵交換装置は、待ち状態に戻る。
【００５４】
Ａ２） その他の場合、鍵交換装置は入力を無視する。
【００５５】
次に図４を参照して、鍵交換装置が、相手側の鍵交換装置から、相手識別子３０７（P'）、相手開始者カウンタ（ictr'）、相手セッション番号（sid'）、相手の第１の同期確認値（x'1）、および相手の第２の同期確認値（x'2）を含む、開始要求メッセージ (P',"開始要求",ictr',sid',x'1,x'2) を通信装置３０２で受け取った場合の動作について説明する。この場合、鍵交換装置は、次の何れかの動作をする(処理2)。
【００５６】
Ｂ１） もし、ある同期判定値 sync に関して、セッション状態３０８として応答待情報("応答待",ictr',sid',x'1,x'2,sync) を記憶装置３２４に保持しているならば、鍵交換装置は、待ち状態に戻る。
【００５７】
Ｂ２） ｉctr'>PCTR でなければ、鍵交換装置は、待ち状態に戻る。
【００５８】
Ｂ３） その他の場合、同期確認装置３１１は、自己の第1の同期検証値 y1 と自己の第2の同期検証値 y2とを、第１の秘密情報３０４と第２の秘密情報３０５とを用いて、次のように生成する。
y1 = HashS(secret1,P',ictr',sid',"開始要求")
y2 = HashS(secret2,P',ictr',sid',"開始要求").
【００５９】
すなわち、同期確認装置３１１は、第１の秘密情報３０４（secret1）、相手識別子３０７（P'）、相手開始者カウンタ（ictr'）、および相手セッション番号（sid'）に基づいて、第１のハッシュ関数HashSを用いて、自己の第1の同期検証値 y1 を生成する。また、同期確認装置３１１は、第２の秘密情報３０５（secret2）、相手識別子３０７（P'）、相手開始者カウンタ（ictr'）、および相手セッション番号（sid'）に基づいて、第１のハッシュ関数HashSを用いて、自己の第2の同期検証値 y2を生成する。
【００６０】
さらに、同期確認装置３１１は、同期判定値 sync を次の様に決定する。
Ｂ３−１) もし (x'1=y2) なら、sync=-1 とする。
Ｂ３−２） もし (x'1,x'2)=(y1,y2) なら、sync=0 とする。
Ｂ３−３) もし (x'2=y1) なら、sync=1 とする。
Ｂ３−４） もし (x'1=y1) かつ (x'2 ≠ y2) ならば、sync=2 とする。
Ｂ３−５) その他の場合は sync = NA.とする。
【００６１】
次に、sync= NA なら、鍵交換装置は待ち状態に戻る。待ち状態に戻らない場合、同期確認装置３１１は、PCTR=ictr' として、次の何れかの動作をする。
【００６２】
Ｂ３−５−１) もしセッション状態３０８を保持していないならば、同期確認装置３１１は、(開始要求受付) を出力装置３０１から出力し、応答待情報("応答待",ictr',sid',x'1,x'2,sync) をセッション状態３０８として記憶装置３２４に保存する。その後、鍵交換装置は、待ち状態に戻る。
【００６３】
Ｂ３−５−２) その他の場合、同期確認装置は、そのセッション状態３０８を消去し、(中止)を出力装置３０１から出力する。その後、鍵交換装置は、待ち状態に戻る。
【００６４】
次に図５を参照して、鍵交換装置が(応答命令)を入力装置３００から入力された場合の動作について説明する。この場合、鍵交換装置は、次の何れかの動作をする(処理3)。
【００６５】
Ｃ１） セッション状態３０８が、ある(ictr',sid',x'1,x'2,sync) に関して応答待情報 ("応答待",ictr',sid',x'1,x'2,sync) であるとする。この場合、セッション番号生成装置３０９は、自己応答者カウンタ rctr=OCTR とし、OCTR を OCTR+1 に変更し、自己セッション番号 sid ∈ {0,1}κ をランダムに選ぶ。すなわち、セッション番号生成装置３０９は、乱数生成装置３０３で生成された乱数を、自己セッション番号sidとしてランダムに選ぶ。鍵識別子生成装置３１０は、自己の鍵識別子 kid を (ictr',sid',rctr,sid) とする。すなわち、鍵識別子生成装置３１０は、相手開始者カウンタ（ictr'）、相手セッション番号（sid'）、自己応答者カウンタ（rctr）、および自己セッション番号（sid）を用いて、自己の鍵識別子 kid を生成する。次に、鍵交換装置は、次の何れかの動作をする。
【００６６】
Ｃ１−１） もし sync=0 なら（すなわち、同期判定値syncが“同期”を示しているなら）、同期確認装置３１１は、自己の第1の同期確認値 x1と自己の第2の同期確認値 x2とを、第１の秘密情報３０４と第２の秘密情報３０５とを用いて、次のように生成する。
x1 = HashS(secret1,P,kid,"応答"),
x2 = HashS(secret2,P,kid,"応答").
【００６７】
すなわち、同期確認装置３１１は、第１の秘密情報３０４（secret1）、自己識別子３０６（P）、および自己の鍵識別子 kidに基づいて、第１のハッシュ関数HashSを用いて、自己の第1の同期確認値 x1を生成する。また、同期確認装置３１１は、第２の秘密情報３０５（secret2）、自己識別子３０６（P）、および自己の鍵識別子 kidに基づいて、第１のハッシュ関数HashSを用いて、自己の第２の同期確認値 x2を生成する。
【００６８】
次に、鍵生成装置３１３は、次の式に従って、鍵keyを生成し、
key = Hashk(secret1,kid)
鍵検証装置314は、次の式に従って、鍵検証値verを生成する。
ver = HashC(secret1,kid)
【００６９】
すなわち、鍵生成装置３１３は、第１の秘密情報３０４（secret1）および自己の鍵識別子 kidに基づいて、第２のハッシュ関数HashKを用いて、鍵keyを生成する。また、鍵検証装置３１４は、第１の秘密情報３０４（secret1）および自己の鍵識別子 kidに基づいて、第３のハッシュ関数HashCを用いて、自己鍵検証値verを生成する。
【００７０】
そして、秘密更新装置３１２は、秘密情報 (secret1,secret2) を (secret2,HashS(secret2,kid)) に更新する。詳述すると、秘密更新装置３１２は、第１の秘密情報３０４（secret1）、第２の秘密情報３０５（secret2）、および自己の鍵識別子 kid を受け取り、第２の秘密情報３０５（secret2）と自己の鍵識別子 kidとに基づいて、第１のハッシュ関数HashS を用いて、第３の秘密情報（secret３）を生成し、第１の秘密情報３０４（secret1）の値を第２の秘密情報３０５（secret2）の値に変更し、第２の秘密情報３０５（secret2）の値を第３の秘密情報（secret３）の値に変更する。
【００７１】
同期確認装置３１１は、セッション状態３０８を応答情報 ("応答",kid,ver,key) へ更新し、自己の鍵識別子 kid を出力装置３０１から出力し、応答メッセージ (P,"応答",ictr',sid',rctr,sid,x1,x2) を通信装置３０２から、相手識別子 P'を持つ相手側の鍵交換装置に送る。そして、鍵交換装置は、待ち状態に戻る。
【００７２】
Ｃ１−２) もし sync ≠ 0 なら、鍵交換装置は、次の何れかの動作をする。
【００７３】
Ｃ１−２−１） もし sync=-1 なら、同期確認装置３１１は、一時秘密情報（第３の秘密情報） secret3 と自己の第1の同期確認値 x1 と自己の第2の同期確認値 x2 とを、次のように生成する。
secret3 = HashS(secret2, kid) 、
x1 = HashS(secret2,P,kid,"非同期",sync)、
x2 = HashS(secret3,P,kid,"非同期",sync).
【００７４】
すなわち、同期確認装置３１１は、第２の秘密情報３０５（secret2）および自己の鍵識別子 kidに基づいて、第１のハッシュ関数HashS を用いて、一時秘密情報（第３の秘密情報）（secret３）を生成する。また、同期確認装置３１１は、第２の秘密情報３０５（secret2）、自己識別子３０６（P）、自己の鍵識別子 kid および同期判定値sync に基づいて、第１のハッシュ関数HashS を用いて、自己の第1の同期確認値 x1 を生成する。そして、同期確認装置３１１は、一次秘密情報（第３の秘密情報）（secret３）、自己識別子３０６（P）、自己の鍵識別子 kid および同期判定値sync に基づいて、第１のハッシュ関数HashS を用いて、自己の第2の同期確認値 x2 を生成する。
【００７５】
Ｃ１−２−２) もし、sync=1 あるいは sync=2 なら、同期確認装置３１１は、一時秘密情報（第３の秘密情報） secret3 と自己の第1の同期確認値 x1 と自己の第2の同期確認値 x2 とを、第１の秘密情報３０４と第２の秘密情報３０５とを用いて、次のように生成する。
secret3 =HashS(secret1,kid)、
x1 = HashS(secret1,P,kid,"非同期",sync)、
x2 = HashS(secret3,P,kid,"非同期",sync).
【００７６】
すなわち、同期確認装置３１１は、第１の秘密情報３０４（secret1）および自己の鍵識別子 kidに基づいて、第１のハッシュ関数HashS を用いて、一時秘密情報（第３の秘密情報）（secret３）を生成する。また、同期確認装置３１１は、第１の秘密情報３０４（secret1）、自己識別子３０６（P）、自己の鍵識別子 kid および同期判定値sync に基づいて、第１のハッシュ関数HashS を用いて、自己の第1の同期確認値 x1 を生成する。そして、同期確認装置３１１は、一次秘密情報（第３の秘密情報）（secret３）、自己識別子３０６（P）、自己の鍵識別子 kid および同期判定値sync に基づいて、第１のハッシュ関数HashS を用いて、自己の第２の同期確認値 x2 を生成する。
【００７７】
次に、同期確認装置３１１は、非同期メッセージ (P,"非同期",sync,ictr',sid',rctr,sid,x1,x2) を、相手識別子 P'を持つ相手側の鍵交換装置へ送り、セッション状態３０８を情報("応答","非同期",sync,kid,x1,x2,secret3) へ更新し、そして、鍵交換装置は、待ち状態に戻る。
【００７８】
Ｃ２） その他の場合、鍵交換装置は、セッション状態３０８を消去し、入力を無視する。
【００７９】
次に図６を参照して、鍵交換装置が、相手側の鍵交換装置から、相手識別子３０７（P'）、自己開始者カウンタ（ictr）、自己セッション番号（sid）、相手応答者カウンタ（rctr'）、相手セッション番号（sid'）、相手の第１の同期確認値（x'1）、および相手の第２の同期確認値（x'2）を含む、応答メッセージ(P',"応答",ictr,sid,rctr',sid',x'1,x'2) を通信装置３０２で受け取った場合の動作について説明する。この場合、鍵交換装置は、次の何れかの動作をする(処理4)。
【００８０】
Ｄ１） セッション状態３０８が、ある (x1,x2) に関して開始要求情報 ("開始要求",ictr,sid,x1,x2) であるとする。この場合、鍵識別子生成装置３１０は自己の鍵識別子 kid を (ictr,sid,rctr',sid') とする。すなわち、鍵識別子静止装置３１０は、自己開始者カウンタ（ictr）、自己セッション番号（sid）、相手応答者カウンタ（rctr'）、および相手セッション番号（sid'）を用いて自己の鍵識別子 kid を生成する。そして、同期確認装置３１１は、自己の第1の同期検証値 y1 と自己の第2の同期検証値 y2 とを、第１の秘密情報３０４と第２の秘密情報３０５とを用いて、次のように生成する。
y1 = HashS(secret1,P',kid,"応答"),
y2 = HashS(secret2,P',kid,"応答").
【００８１】
すなわち、同期確認装置３１１は、第１の秘密情報３０４（secret1）、相手識別子３０７（P'）、および自己の鍵識別子 kid に基づいて、第１のハッシュ関数HashS を用いて、自己の第1の同期検証値 y1を生成する。また、同期確認装置３１１は、第２の秘密情報３０５（secret2）、相手識別子３０７（P'）、および自己の鍵識別子 kid に基づいて、第１のハッシュ関数HashS を用いて、自己の第2の同期検証値 y2とを生成する。
【００８２】
そして、鍵交換装置は、次の何れかの動作をする。
【００８３】
Ｄ１−１） もし rctr' > PCTR かつ (x'1,x'2)=(y1,y2) ならば、鍵生成装置３１３は、次の式に従って、鍵keyを生成し、
key = Hashk(secret1,kid)
鍵検証装置３１４は、次の式に従って、自己の鍵検証値verを生成する。
ver = HashC(secret1,kid)
【００８４】
すなわち、鍵生成装置３１３は、第１の秘密情報３０４（secret1）および自己の鍵識別子 kid をに基づいて、第２のハッシュ関数HashKを用いて、鍵keyを生成する。また、鍵検証装置３１４は、第１の秘密情報３０４（secret1）および自己の鍵識別子 kidに基づいて、第３のハッシュ関数HashCを用いて、自己の鍵検証値verを生成する。
【００８５】
そして、秘密更新装置３１２は、秘密情報 (secret1,secret2) を (secret2,HashS(secret2,kid)) へ更新し、PCTR = rctr' と変更する。詳述すると、秘密更新装置３１２は、第１の秘密情報３０４（secret1）、第２の秘密情報３０５（secret2）、および自己の鍵識別子 kid を受け取り、第２の秘密情報３０５（secret2）と自己の鍵識別子 kidとに基づいて、第１のハッシュ関数HashS を用いて、第３の秘密情報（secret３）を生成し、第１の秘密情報３０４（secret1）の値を第２の秘密情報３０５（secret2）の値に変更し、第２の秘密情報３０５（secret2）の値を第３の秘密情報（secret３）の値に変更する。
【００８６】
同期確認装置３１１は、自己の鍵識別子 (kid) を出力装置３１０から出力し、 (kid,key) を出力装置３０１から出力し、了解メッセージ(P,"了解",ictr,sid,rctr',sid',ver) を通信装置３０２から相手識別子 P' を持つ相手側の鍵交換装置へ送り、セッション状態３０８を消去する。その後、鍵交換装置は、待ち状態に戻る。
【００８７】
Ｄ１−２) もし、その他の場合、鍵交換装置は、待ち状態に戻る。
Ｄ２） その他の場合、鍵交換装置は、待ち状態に戻る。
【００８８】
次に図７を参照して、鍵交換装置が相手側の鍵交換装置から、相手識別子３０７（P'）、同期判定値（sync）、自己開始者カウンタ（ictr）、自己セッション番号（sid）、相手応答者カウンタ（rctr'）、相手セッション番号（sid'）、相手の第１の同期確認値（x'1）、および相手の第２の同期確認値（x'2）を含む、非同期メッセージ(P',"非同期",sync,ictr,sid,rctr',sid',x'1,x'2) を通信装置３０２で受け取った場合の動作について説明する。この場合、鍵交換装置は、次の何れかの動作をする(処理５)。
【００８９】
Ｅ１） セッション状態３０８が、ある (x1,x2) に関して開始要求情報("開始要求",ictr,sid,x1,x2) であるとする。この場合、鍵識別子生成装置３１０は、自己の鍵識別子 kid を (ictr,sid,rctr',sid') とする。すなわち、鍵識別子生成装置３１０は、自己開始者カウンタ（ictr）、自己セッション番号（sid）、相手応答者カウンタ（rctr'）、および相手セッション番号（sid'）を用いて自己の鍵識別子 kid を生成する。そして、鍵交換装置は、次の何れかの動作をする。
【００９０】
Ｅ１−１） sync=-1 あるいは sync=2 とする。この場合、同期確認装置３１１は、一時秘密情報（第３の秘密情報）secret3 と自己の第1の同期検証値 y1 と自己の第2の同期検証値 y2 とを、第１の秘密情報３０４と第２の秘密情報３０５とを用いて、次のように生成する。
secret3 = HashS(secret1,kid)
y1 = HashS(secret1,P',kid,"非同期",sync)
y2 = HashS(secret3,P',kid,"非同期",sync).
【００９１】
すなわち、同期確認装置３１１は、第１の秘密情報３０４（secret1）および自己の鍵識別子kidに基いて、第１のハッシュ関数HashS を用いて、一時秘密情報（第３の秘密情報）（secret３）を生成する。また、同期確認装置３１１は、第１の秘密情報３０４（secret1）、相手識別子３０７（P'）、自己の鍵識別子kid、および同期判定値syncに基いて、第１のハッシュ関数HashS を用いて、自己の第1の同期検証値 y1を生成する。さらに、同期確認装置３１１は、一時秘密情報（第３の秘密情報）（secret３）、相手識別子３０７（P'）、自己の鍵識別子kid、および同期判定値syncに基いて、第１のハッシュ関数HashS を用いて、自己の第2の同期検証値 y2 を生成する。
【００９２】
そして、鍵交換装置は、次の何れかの動作をする。
【００９３】
Ｅ１−１−１） rctr' >PCTR かつ (x'1,x'2) =(y1,y2)なら、秘密更新装置３１２は、秘密情報 (secret1,secret2) を(secret1,secret3) へ更新し、 PCTR=rctr' に変更する。すなわち、秘密更新装置３１２は、第１の秘密情報３０４（secret1）の値をそのまま第１の秘密情報３０４（secret1）の値とし、第２の秘密情報３０５（secret2）の値を一時秘密情報（第３の秘密情報）（secret３）の値に更新する。
【００９４】
Ｅ１−１−２) その他の場合、鍵交換装置は、待ち受け状態に戻る。
【００９５】
Ｅ１−２） sync = 1 とする。この場合、同期確認装置３１１は、一時秘密情報（第３の秘密情報）secret3と自己の第1の同期検証値y1と自己の第2の同期検証値y2とを、第１の秘密情報３０４と第２の秘密情報３０５とを用いて、次のように生成する。
secret3 = HashS(secret2,kid)
y1 = HashS(secret2,P',kid,"非同期",sync)
y2 = HashS(secret3,P',kid,"非同期",sync).
【００９６】
すなわち、同期確認装置３１１は、第２の秘密情報３０５（secret2）および自己の鍵識別子kidに基いて、第１のハッシュ関数HashS を用いて、一時秘密情報（第３の秘密情報）（secret３）を生成する。また、同期確認装置３１１は、第２の秘密情報３０５（secret2）、相手識別子３０７（P'）、自己の鍵識別子kid、および同期判定値syncに基いて、第１のハッシュ関数HashS を用いて、自己の第1の同期検証値y1を生成する。さらに、同期確認装置３１１は、一時秘密情報（第３の秘密情報）（secret３）、相手識別子３０７（P'）、自己の鍵識別子kid、および同期判定値syncに基いて、第１のハッシュ関数HashS を用いて、自己の第2の同期検証値y2を生成する。
【００９７】
そして、鍵交換装置は、次の何れかの動作をする。
【００９８】
Ｅ１−２−１） rctr' >PCTR かつ (x'1,x'2) =(y1,y2)なら、秘密更新装置３１２は、秘密情報 (secret1,secret2) を(secret2,secret3) へ更新し、PCTR=rctr' に変更する。すなわち、秘密更新装置３１２は、第１の秘密情報３０４（secret1）の値を第２の秘密情報３０５（secret2）の値に更新し、第２の秘密情報３０５（secret2）の値を一時秘密情報（第３の秘密情報）（secret３）に更新する。
【００９９】
Ｅ１−２−２) その他の場合、鍵交換装置は、待ち受け状態に戻る。
【０１００】
次に、同期確認装置３１１は、自己の第1の同期確認値x1 と自己の第2の同期確認値x2とを、第１の秘密情報３０４と第２の秘密情報３０５とを用いて、次のように生成する。
x1 = HashS(secret1,P,kid,"非同期確認",sync),
x2 = HashS(secret2,P,kid,"非同期確認",sync).
【０１０１】
すなわち、同期確認装置３１１は、第１の秘密情報３０４（secret1）、自己識別子３０６（P）、自己の鍵識別子kid、および同期判定値syncに基づいて、第１のハッシュ関数HashS を用いて、自己の第1の同期確認値 x1 を生成する。また、同期確認装置３１１は、第２の秘密情報３０５（）、自己識別子３０６（P）、自己の鍵識別子kid、および同期判定値syncに基づいて、第１のハッシュ関数HashS を用いて、自己の第2の同期確認値 x2を生成する。
【０１０２】
そして、同期確認装置３１１は、非同期確認メッセージ(P,"非同期確認",kid,x1,x2) を通信装置３０２から、相手識別子P' を持つ相手側の鍵交換装置へ送り、セッション状態３０８を消去し、(中止)を出力装置３０１から出力する。その後、鍵交換装置は、待ち受け状態に戻る。
【０１０３】
Ｅ２） その他の場合、鍵交換装置は、受け取ったメッセージを無視する。
【０１０４】
次に図８を参照して、鍵交換装置が、相手側の鍵交換装置から、相手識別子３０７（P'）、相手開始者カウンタ（ictr'）、相手セッション番号（sid'）、自己応答者カウンタ（rctr）、自己セッション番号（sid）、および相手鍵検証値（ver'）を含む了解メッセージ(P',"了解",ictr',sid',rctr,sid,ver') を、通信装置３０２で受け取った場合の動作について説明する。この場合、鍵交換装置は、次の何れかの動作をする(処理6)。
【０１０５】
Ｆ１） セション状態３０８が、kid=(ictr',sid',rctr,sid) かつ ver=ver' であるような応答情報 ("応答",kid,ver,key) であるとする。この場合、同期確認装置３１１は、(kid,key) を出力装置３０１から出力し、セッション状態３０８を消去する。そして、鍵交換装置は、待ち受け状態に戻る。
【０１０６】
Ｆ２） その他の場合、鍵交換装置は、受け取ったメッセージを無視する。
【０１０７】
次に図９を参照して、鍵交換装置が、相手側の鍵交換装置から、相手識別子３０７（P'）、相手鍵識別子（kid'）、相手の第１の同期確認値（x'1）、および相手の第２の同期確認値（x'2）を含む、非同期確認メッセージ(P',"非同期確認",kid',x'1,x'2) を通信装置３０２で受け取った場合の動作について説明する。この場合、鍵交換装置は、次の何れかの動作をする(処理7)。
【０１０８】
Ｇ１） セション状態３０８が、kid=kid' であるような情報("応答","非同期",sync,kid,x1,x2,secret3) であるとする。この場合、鍵交換装置は、次の何れかの動作をする。
【０１０９】
Ｇ１−１) sync=-1 とする。この場合、同期確認装置３１１は、自己の第１の同期検証値 y1 と自己の第２の同期検証値y2 とを、第２の秘密情報３０５とセッション状態３０８とを用いて、次のように生成する。
y1 = HashS(secret2,P,kid,"非同期確認",sync)
y2 = HashS(secret3,P,kid,"非同期確認",sync).
【０１１０】
すなわち、同期確認装置３１１は、第２の秘密情報３０５（secret2）、自己識別子３０６（P）、自己の鍵識別子kid、および同期判定値syncに基いて、第１のハッシュ関数HashS を用いて、自己の第１の同期検証値 y1を生成する。また、同期確認装置３１１は、セッション状態３０８中の一時秘密情報（secret3）、自己識別子３０６（P）、自己の鍵識別子kid、および同期判定値syncに基いて、第１のハッシュ関数HashS を用いて、自己の第２の同期検証値y2を生成する。
【０１１１】
そして、鍵交換装置は、次の何れかの動作をする。
【０１１２】
Ｇ１−１−１) (x'1,x'2)=(y1,y2)なら、秘密更新装置３１２は、秘密情報 (secret1,secret2) を(secret2,secret3) へ更新する。すなわち、秘密更新装置３１２は、第１の秘密情報３０４（secret1）の値を第２の秘密情報３０５（secret2）の値に更新し、第２の秘密情報３０５（secret2）の値を一時秘密情報（第３の秘密情報）（secret3）の値に更新する。
【０１１３】
Ｇ１−１−２) その他の場合、鍵交換装置は、待ち受け状態に戻る。
【０１１４】
Ｇ１−２) sync=1 あるいは sync=2とする。この場合、同期確認装置３１１は、自己の第１の同期検証値 y1 と自己の第２の同期検証値 y2 とを、第１の秘密情報３０４とセッション状態３０８とを用いて、次のように生成する。
y1 = HashS(secret1,P,kid,"非同期確認",sync)
y2 = HashS(secret3,P,kid,"非同期確認",sync).
【０１１５】
すなわち、同期確認装置３１１は、第１の秘密情報３０４（secret1）、自己識別子３０６（P）、自己の鍵識別子kid、および同期判定値syncに基いて、第１のハッシュ関数HashS を用いて、自己の第１の同期検証値 y1を生成する。また、同期確認装置３１１は、セッション状態３０８中の一時秘密情報（secret3）、自己識別子３０６（P）、自己の鍵識別子kid、および同期判定値syncに基いて、第１のハッシュ関数HashS を用いて、自己の第２の同期検証値y2を生成する。
【０１１６】
そして、鍵交換装置は、次の何れかの動作をする。
Ｇ１−２−１) (x'1,x'2)=(y1,y2)なら、秘密更新装置３１２は、秘密情報 (secret1,secret2) を(secret1,secret3) へ更新する。すなわち、秘密更新装置３１２は、第１の秘密情報３０４（secret1）の値をそのまま第１の秘密情報３０４（secret1）に維持し、第２の秘密情報３０５（secret2）の値を一時秘密情報（第３の秘密情報）（secret3）の値に更新する。
【０１１７】
Ｇ１−２−２) その他の場合、鍵交換装置は、待ち受け状態に戻る。
【０１１８】
次に、同期確認装置３１１は、セッション状態３０８を消去し、 (中止)を出装置３０１から出力する。その後、鍵交換装置は、待ち状態に戻る。
【０１１９】
Ｇ２） その他の場合、鍵交換装置は、受け取ったメッセージを無視する。
【０１２０】
次に図１０を参照して、鍵交換装置 が入力装置３００から(失効命令)が入力された場合の動作について説明する。この場合、鍵交換装置は、次の何れかの動作をする(処理8)。
【０１２１】
Ｈ１） もし何らかのセション状態３０８を保持している場合、鍵交換装置は、このセション状態を消去し、出力装置３０１から(失効)を出力し、待ち受け状態に戻る。
Ｈ２） その他の場合、鍵交換装置は、受け取ったメッセージを無視する。
【実施例２】
【０１２２】
次に、本発明の第２の実施例による、共有した秘密情報に基づく認証付鍵交換システムについて説明する。
【０１２３】
鍵交換システムは、上記第１の実施例に記載した二つの鍵交換装置からなる。それらの一方を第１の鍵交換装置と呼び、他方を第２の鍵交換装置と呼ぶことにする。第１および第２の鍵交換装置とも、通信路に接続されている。
【０１２４】
第１の鍵交換装置には、その初期設定において自己の識別子としてあるP が入力され、相手の識別子としてあるP' が入力される。また、 {0,1}κ からランダムに選ばれた、第１の秘密情報と第２の秘密情報が、それぞれ、 secret1, secret2 として格納される。以降、 この第１の鍵交換装置をP と呼ぶ。
【０１２５】
第２の鍵交換装置には、その初期設定において自己の識別子として先の P' が入力され、相手の識別子として先の P が入力される。 {0,1}κ からランダムに選ばれて、第１の鍵交換装置P に格納された二つの値と同じ値が、 secret1, secret2 として格納される。以降、この第２の鍵交換装置を P' と呼ぶ。
【０１２６】
第１の鍵交換装置P がメッセージを第２の鍵交換装置P' に送付する動作を行うと、このメッセージは前記通信路を伝って第２の鍵交換装置P' の通信装置に入力される。逆に、第２の鍵交換装置 P' がメッセージを第１の鍵交換装置P に送付する動作を行うと、このメッセージは前記通信路を伝って第１の鍵交換装置P の通信装置に入力される。
【０１２７】
以下、第１および第２の鍵交換装置が鍵識別子kid と鍵key とを出力する典型的な動作について説明する。但し、P とP' とは入れ替えても良い。
【０１２８】
第１の鍵交換装置P に(開始命令)が入力される。第１の鍵交換装置P は上記第１の実施例に記載される通りに動作し、開始要求メッセージ (P,"開始要求",sid,x1,x2) を第２の鍵交換装置 P' に送付し、開始要求情報("開始要求",sid,x1,x2) をセッション状態として保存し、待ち状態に戻る。
【０１２９】
第２の鍵交換装置P' は開始要求メッセージ (P,"開始要求",sid,x1,x2) を受け取る。第２の鍵交換装置P' は、上記第１の実施例に記載される通りに動作し、鍵交換装置P' は (開始要求受付) を出力し、応答待情報("応答待",sid,x1,x2,sync) をセッション状態と して保存し、待ち状態に戻る。
【０１３０】
第２の鍵交換装置P'に(応答命令)が入力される。第２の鍵交換装置P' は上記第１の実施例に記載される通りに動作し、秘密情報 (secret1,secret2) を (secret2,HashS(secret2,kid)) に更新し、セッション状態を応答情報("応答",kid,ver,key) へ更新し、kid を出力し、応答メッセージ (P',"応答",sid,sid',x'1,x'2) を第１の鍵交換装置P に送り、待ち状態に戻る。
【０１３１】
第１の鍵交換装置P は応答メッセージ (P',"応答",sid,sid',x'1,x'2) を受け取る。第１の鍵交換装置 P は、上記第１の実施例に記載される通りに動作し、秘密情報 (secret1,secret2) を (secret2,HashS(secret2,kid)) へ更新し、(kid) を出力し、(kid,key) を出力し、了解メッ セージ (P,"了解",sid,sid',ver) を第２の鍵交換装置P' へ送り、セッション状態を消去し、待ち状態に戻る。
【０１３２】
第２の鍵交換装置P' は了解メッセージ (P',"了解",sid,sid',ver') を受けとる。第２の鍵交換装置P' は上記第１の実施例に記載される通りに動作し、(kid,key) を出力し、セッション状態を消去し、待ち受け状態に戻る。
【０１３３】
次に、本発明の実施例の効果について説明する。
【０１３４】
秘密情報の更新は、ハッシュ関数にその秘密情報を入力して得られた結果を新たな秘密情報とする様に行う。この時、 ハッシュ関数に更新する前の秘密情報のみを入力するとすると、最初の秘密情報が漏れるとこれから未来の秘密情報が全て分かってしまう。そこで、本発明の実施例では、ハッシュ関数への入力に鍵識別子 kid が加わっているため、未来の秘密情報は確率的に決定される。このことにより、攻撃者が、全ての通信を盗聴することなく秘密情報を同期し続ける事は出来なくなる。また、鍵識別子は両方の参加者が生成する乱数からなるため、少なくとも一人が正直であれば、秘密情報は確率的に遷移する。
【０１３５】
秘密情報が確率的に遷移する場合、両方の参加者の秘密情報の同期が崩れてしまう可能性がある。そこで、本発明の実施例では第１の秘密情報と第２の秘密情報の二つを準備する。そして、第１の秘密情報と第２の秘密情報を更新したときに、更新する前の第２の秘密情報へと第１の秘密情報を更新する。この様にすることで、二人の参加者が第２の秘密情報を互いに異なるものへと更新してしまっても、第１の秘密情報から再度同じものを構築し直すことができる。
【０１３６】
片方の参加者が共有する秘密情報から鍵を生成して出力した時点で、この鍵生成に使った秘密情報が残存していると、この秘密情報を得た攻撃者が生成された秘密情報を知る可能性がある。それゆえ、鍵生成に用いた秘密情報は速やかに更新して消去する必要がある。特に、片方が鍵を生成して秘密情報を更新しても、他方がこの更新前の秘密情報を保持している様な事がないように注意する必要がある。一方、あまりに早急に秘密情報を更新すると、相手の秘密情報がどのように更新されるか十分に把握する前に自身の秘密情報を更新してしまい、両方の参加者の秘密情報の同期が壊れてしまう。
【０１３７】
この様な鍵の秘密保持と秘密情報の更新の確実性の両方を求めるには、両方の参加者で通信を何度も行って、両方の状況を確認しながら処理を進めれば良い。しかしながら、この様なことをすると、通信回数が多くなり効率的でない。
【０１３８】
そこで、本発明の実施例では、三回という最低限の通信回数で、先の問題を解決している。特に、鍵の安全性を確保するために、両方の参加者が同期している場合には、二回目のメッセージ送信を行う者はこの時に一回目と三回目のメッセージ送信を行う者は三回目のそのときに秘密情報の更新を行う。一方、秘密情報の同期がとれていない場合は、二回目のメッセージ送信を行う者は三回目のメッセージを受信してから、一回目と三回目のメッセージ送信を行うものは三回目のそのときに秘密情報の更新を行い、鍵の生成は行わずに秘密情報の同期のみを行う。この様に、鍵の生成を行うときと、秘密情報の同期を行うときで秘密情報の更新時期を違える事で、鍵の秘密の保持と秘密情報の更新の確実性の両方を、最小限の通信回数で成功している。
【０１３９】
以上、実施形態（実施例）を参照して本発明を説明したが、本発明は上記実施形態（実施例）に限定されるものではない。本発明の構成や詳細には、本発明のスコープ内で当業者が理解し得る様々な変更をすることができる。
【０１４０】
上記の実施形態の一部又は全部は、以下の付記のようにも記載されうるが、以下には限られない。
【０１４１】
（付記１）乱数を生成する乱数生成装置と、
第１の秘密情報と第２の秘密情報とを保持する秘密情報記憶装置と、
前記乱数生成装置を用いて生成した乱数と、相手装置から受信したデータとを用いて自己の鍵識別子を生成する鍵識別子生成装置と、
前記第１の秘密情報を用いて自己の第１の同期確認値を生成し、前記第２の秘密情報を用いて自己の第２の同期確認値を生成し、該自己の第１の同期確認値と前記自己の第２の同期確認値とを前記相手装置へ送出し、前記第１の秘密情報を用いて自己の第１の同期検証値を生成し、前記第２の秘密情報を用いて自己の第２の同期検証値を生成し、相手の第１の同期確認値と相手の第２の同期確認値とを前記相手装置から受信し、前記相手の第１の同期確認値および前記相手の第２の同期確認値と、前記自己の第１の同期検証値および前記自己の第２の同期検証値とを用いて、同期判定値を生成する同期確認装置と、
前記第１の秘密情報と前記第２の秘密情報と前記鍵識別子とを受け取り、前記第２の秘密情報と前記鍵識別子とから第３の秘密情報を生成し、前記第１の秘密情報の値を前記第２の秘密情報の値に変更し、前記第２の秘密情報の値を前記第３の秘密情報の値に変更する秘密更新装置と、
前記第１の秘密情報から鍵を生成する鍵生成装置と、
を備える鍵交換装置。
【０１４２】
（付記２）前記同期判定値は、前記相手の第１の同期確認値および前記相手の第２の同期確認値が、それぞれ、前記自己の第１の同期検証値および前記自己の第２の同期検証値と等しいなら、“同期”を示す０の値を持ち、前記相手の第１の同期確認値と前記自己の第２の同期検証値とが等しいなら、−１の値を持ち、前記相手の第２の同期確認値と前記自己の第１の同期検証値とが等しいなら、１の値を持ち、前記相手の第１の同期確認値と前記自己の第１の同期検証値とが等しく、かつ、前記相手の第２の同期確認値と前記自己の第２の同期検証値とが等しくないとき、２の値を持ち、
前記同期確認装置は、
前記同期判定値の値が−１に等しいとき、前記第２の秘密情報と前記鍵識別子とから前記第３の秘密情報を生成し、前記第２の秘密情報を用いて前記自己の第１の同期確認値を生成し、前記第３の秘密情報を用いて前記自己の第２の同期確認値を生成する機能と、
前記同期判定値の値が１又は２に等しいとき、前記第１の秘密情報と前記鍵識別子とから前記第３の秘密情報を生成し、前記第１の秘密情報を用いて前記自己の第１の同期確認値を生成し、前記第３の秘密情報を用いて前記自己の第２の同期確認値を生成する機能と、
前記同期判定値の値が１に等しいとき、前記第２の秘密情報と前記鍵識別子とから前記第３の秘密情報を生成し、前記第２の秘密情報を用いて前記自己の第１の同期検証値を生成し、前記第３の秘密情報を用いて前記自己の第２の同期検証値を生成する機能と、
前記同期判定値の値が−１又は２に等しいとき、前記第１の秘密情報と前記鍵識別子とから前記第３の秘密情報を生成し、前記第１の秘密情報を用いて前記自己の第１の同期検証値を生成し、前記第３の秘密情報を用いて前記自己の第２の同期検証値を生成する機能と、
をさらに備える、ことを特徴とする付記１に記載の鍵交換装置。
【０１４３】
（付記３）付記１に記載の鍵交換装置二つからなる鍵交換システムであって、
第１の鍵交換装置が保持する自己識別子と第２の鍵交換装置が保持する相手識別子とが同一で、
前記第１の鍵交換装置が保持する相手識別子と前記第２の鍵交換装置が保持する自己識別子とが同一であり、
前記第１の鍵交換装置と前記第２の鍵交換装置とは通信路で繋がっており、
前記第１の鍵交換装置が送出するメッセージを前記第２の鍵交換装置が受信可能であり、
前記第２の鍵交換装置が送出するメッセージを前記第１の鍵交換装置が受信可能であり、
何れかの鍵交換装置には、開始命令、応答命令を入力する事が出来る
ことを特徴とする鍵交換システム。
【０１４４】
（付記４）前記第１の鍵交換装置は、前記開始命令が入力されると、その前記同期確認装置が、前記第１の秘密情報および前記第２の秘密情報を用いて、前記自己の第１の同期確認値および前記自己の第２の同期確認値を生成し、前記自己の第１の同期確認値および前記自己の第２の同期確認値を含む開始要求メッセージを、前記第２の鍵交換装置へ送出する、付記３に記載の鍵交換システム。
【０１４５】
（付記５）前記第２の鍵交換装置は、前記開始要求メッセージを受け取ると、その前記同期確認装置が、前記第１の秘密情報および前記第２の秘密情報を用いて、自己の第１の同期検証値および自己の第１の同期検証値を生成し、前記開始要求メッセージに含まれる相手の第１の同期確認値および相手の第２の同期確認値と前記自己の第１の同期検証値および前記自己の第１の同期検証値とを用いて同期判定値を生成する、付記４に記載の鍵交換システム。
【０１４６】
（付記６）前記第２の鍵交換装置は、前記応答命令が入力されると、その前記鍵識別子生成装置が、その前記乱数生成装置で生成された乱数と前記開始要求メッセージに含まれるデータとを用いて自己の鍵識別子を生成し、
前記第２の鍵交換装置は、前記同期判定値が“同期”を示しているなら、その前記鍵生成装置が、前記第１の秘密情報から鍵を生成し、その秘密更新装置が、前記第１の秘密情報の値および前記第２の秘密情報の値を、それぞれ、前記第２の秘密情報の値および前記前記第３の秘密情報の値に変更する、付記５に記載の鍵交換システム。
【０１４７】
（付記７）前記第２の鍵交換装置は、前記同期判定値が“同期”を示しているなら、その前記同期確認装置は、前記自己の鍵識別子、前記第１の秘密情報、および前記第２の秘密情報を用いて、自己の第１の同期確認値および自己の第２の同期確認値を生成し、前記自己の第１の同期確認値および前記自己の第２の同期確認値を含む応答メッセージを、前記第１の鍵交換装置へ送出する、付記６に記載の鍵交換システム。
【０１４８】
（付記８）前記第１の鍵交換装置は、前記応答メッセージを受け取ると、その前記鍵識別子生成装置が、該応答メッセージに含まれるデータから自己の鍵識別子を生成し、その前記同期確認装置が、前記自己の鍵識別子、前記第１の秘密情報、および前記第２の秘密情報を用いて、自己の第１の同期検証値および自己の第２の同期検証値を生成する、付記７に記載の鍵交換システム。
【０１４９】
（付記９）前記第１の鍵交換装置は、前記応答メッセージに含まれる相手の第１の同期確認値および相手の第２の同期確認値が、それぞれ、前記自己の第１の同期検証値および前記自己の第２の同期検証値に等しいとき、その前記鍵生成装置が、前記第１の秘密情報から鍵を生成し、その秘密更新装置が、前記第１の秘密情報の値および前記第２の秘密情報の値を、それぞれ、前記第２の秘密情報の値および前記前記第３の秘密情報の値に変更する、付記８に記載の鍵交換システム。
【０１５０】
（付記１０）第１の鍵交換装置と第２の鍵交換装置との間で鍵の交換を行う鍵交換方法であって、
開始命令を入力したとき、前記第１の鍵交換装置が、第１の秘密情報および第２の秘密情報を用いて、それぞれ、自己の第１の同期確認値および自己の第２の同期確認値を生成し、前記自己の第１の同期確認値および前記自己の第２の同期確認値を含む開始要求メッセージを前記第２の鍵交換装置へ送信する工程と、
前記第１の鍵交換装置から相手の第１の同期確認値および相手の第２の同期確認値を含む前記開始要求メッセージを受け取ったとき、前記第２の鍵交換装置が、前記第１の秘密情報および前記第２の秘密情報を用いて、それぞれ、自己の第１の同期検証値および自己の第２の同期検証値を生成し、前記相手の第１の同期確認値、前記相手の第２の同期確認値、前記自己の第１の同期検証値、および前記自己の第２の同期検証値を用いて同期判定値を生成する工程と、
を含む、鍵交換方法。
【０１５１】
（付記１１）応答命令を入力したとき、前記第２の鍵交換装置が、乱数生成装置を用いて生成した乱数と前記開始要求メッセージに含まれるデータとを用いて、自己の鍵識別子を生成する工程を含む、付記１０に記載の鍵交換方法。
【０１５２】
（付記１２）前記同期判定値が“同期”を示しているなら、前記第２の鍵交換装置が、前記第１の秘密情報から鍵を生成し、前記第２の秘密情報と前記自己の鍵識別子とから第３の秘密情報を生成し、前記第１の秘密情報の値を前記第２の秘密情報の値に更新し、前記第２の秘密情報の値を前記第３の秘密情報の値に更新する工程を含む、請求項１１に記載の鍵交換方法。
【０１５３】
（付記１３）前記同期判定値が“同期”を示しているなら、前記第２の鍵交換装置が、前記自己の鍵識別子、前記第１の秘密情報、および前記第２の秘密情報を用いて、自己の第１の同期確認値および自己の第２の同期確認値を生成し、前記自己の第１の同期確認値および前記自己の第２の同期確認値を含む応答メッセージを前記第１の鍵交換装置へ送信する工程を含む、付記１１又は１２に記載の鍵交換方法。
【０１５４】
（付記１４）前記第２の鍵交換装置から相手の第１の同期確認値および相手の第２の同期確認値を含む前記応答メッセージを受け取ったとき、前記第１の鍵交換装置が、該応答メッセージに含まれるデータから鍵識別子を生成し、該生成した鍵識別子、前記第１の秘密情報、および前記第２の秘密情報を用いて、自己の第１の同期検証値および自己の第２の同期検証値を生成する工程を含む、付記１３に記載の鍵交換方法。
【０１５５】
（付記１５）前記相手の第１の同期確認値および前記相手の第２の同期確認値が、それぞれ、前記自己の第１の同期検証値および前記自己の第２の同期検証値と等しいとき、前記第１の鍵交換装置が、前記第１の秘密情報から鍵を生成し、前記第２の秘密情報と前記鍵識別子とから第３の秘密情報を生成し、前記第１の秘密情報の値を前記第２の秘密情報の値に更新し、前記第２の秘密情報の値を前記第３の秘密情報の値に更新する工程を含む、請求項１４に記載の鍵交換方法。
【０１５６】
（付記１６）前記同期判定値が“非同期”を示しているなら、前記第２の鍵交換装置が、前記第１の秘密情報および前記第２の秘密情報を用いて、一時秘密情報、自己の第１の同期確認値、自己の第２の同期確認値を生成し、前記自己の第１の同期確認値、前記自己の第２の同期確認値、および前記同期判定値を含む非同期メッセージを前記第１の鍵交換装置へ送出する工程を含む、付記１０に記載の鍵交換方法。
【０１５７】
（付記１７）前記第２の鍵交換装置から前記同期判定値、相手の第１の同期確認値、および相手の第２の同期確認値を含む前記非同期メッセージを受け取ったとき、前記第１の鍵交換装置が、該非同期メッセージに含まれるデータから自己の鍵識別子を生成し、該生成した自己の鍵識別子、前記第１の秘密情報、および前記第２の秘密情報を用いて、自己の第１の同期検証値および自己の第２の同期検証値を生成する工程を含む、付記１６に記載の鍵交換方法。
【０１５８】
（付記１８）前記相手の第１の同期確認値および前記相手の第２の同期確認値が、それぞれ、前記自己の第１の同期検証値および前記自己の第２の同期検証値に等しいなら、前記第１の鍵交換装置が、前記同期判定値の値に応じて、前記第１の秘密情報の値と前記第２の秘密情報の値とを更新する工程を含む、付記１７に記載の鍵交換方法。
【０１５９】
（付記１９）前記第１の鍵交換装置が、前記自己の鍵識別子、前記第１の秘密情報、および前記第２の秘密情報を用いて、自己の第１の同期確認値および自己の第２の同期確認値を生成し、前記同期判定値、前記自己の第１の同期確認値および前記自己の第２の同期確認値を含む非同期確認メッセージを、前記第２の鍵交換装置へ送出する工程を含む、付記１７又は１８に記載の鍵交換方法。
【０１６０】
（付記２０）前記第１の鍵交換装置から、相手の第１の同期確認値および相手の第２の同期確認値を含む前記非同期確認メッセージを受け取ったとき、前記第２の鍵交換装置が、前記自己の鍵識別子、前記一時秘密情報、および前記第１の秘密情報又は前記第２の秘密情報を用いて、自己の第１の同期検証値および自己の第２の同期検証値を生成し、前記相手の第１の同期確認値および前記相手の第２の同期確認値が、それぞれ、前記自己の第１の同期検証値および前記自己の第２の同期検証値に等しいとき、前記同期判定値の値に応じて、前記第１の秘密情報の値と前記第２の秘密情報の値とを更新する工程を含む、付記１９に記載の鍵交換方法。
【０１６１】
（付記２１）乱数を生成する手順と、
第１の秘密情報と第２の秘密情報とを保持する手順と、
前記生成された乱数と、相手装置から受信したデータとを用いて自己の鍵識別子を生成する手順と、
前記第１の秘密情報を用いて自己の第１の同期確認値を生成し、前記第２の秘密情報を用いて自己の第２の同期確認値を生成し、該自己の第１の同期確認値と前記自己の第２の同期確認値とを前記相手装置へ送出し、前記第１の秘密情報を用いて自己の第１の同期検証値を生成し、前記第２の秘密情報を用いて自己の第２の同期検証値を生成し、相手の第１の同期確認値と相手の第２の同期確認値とを前記相手装置から受信し、前記相手の第１の同期確認値および前記相手の第２の同期確認値と、前記自己の第１の同期検証値および前記自己の第２の同期検証値とを用いて、同期判定値を生成する手順と、
前記第１の秘密情報と前記第２の秘密情報と前記鍵識別子とを受け取り、前記第２の秘密情報と前記鍵識別子とから第３の秘密情報を生成し、前記第１の秘密情報の値を前記第２の秘密情報の値に変更し、前記第２の秘密情報の値を前記第３の秘密情報の値に変更する手順と、
前記第１の秘密情報から鍵を生成する手順と、
をコンピュータに実行させる鍵交換プログラム。
【０１６２】
（付記２２）前記同期判定値は、前記相手の第１の同期確認値および前記相手の第２の同期確認値が、それぞれ、前記自己の第１の同期検証値および前記自己の第２の同期検証値と等しいなら、“同期”を示す０の値を持ち、前記相手の第１の同期確認値と前記自己の第２の同期検証値とが等しいなら、−１の値を持ち、前記相手の第２の同期確認値と前記自己の第１の同期検証値とが等しいなら、１の値を持ち、前記相手の第１の同期確認値と前記自己の第１の同期検証値とが等しく、かつ、前記相手の第２の同期確認値と前記自己の第２の同期検証値とが等しくないとき、２の値を持ち、
前記同期判定値を生成する手順は、
前記同期判定値の値が−１に等しいとき、前記第２の秘密情報と前記鍵識別子とから前記第３の秘密情報を生成し、前記第２の秘密情報を用いて前記自己の第１の同期確認値を生成し、前記第３の秘密情報を用いて前記自己の第２の同期確認値を生成する手順と、
前記同期判定値の値が１又は２に等しいとき、前記第１の秘密情報と前記鍵識別子とから前記第３の秘密情報を生成し、前記第１の秘密情報を用いて前記自己の第１の同期確認値を生成し、前記第３の秘密情報を用いて前記自己の第２の同期確認値を生成する手順と、
前記同期判定値の値が１に等しいとき、前記第２の秘密情報と前記鍵識別子とから前記第３の秘密情報を生成し、前記第２の秘密情報を用いて前記自己の第１の同期検証値を生成し、前記第３の秘密情報を用いて前記自己の第２の同期検証値を生成する手順と、
前記同期判定値の値が−１又は２に等しいとき、前記第１の秘密情報と前記鍵識別子とから前記第３の秘密情報を生成し、前記第１の秘密情報を用いて前記自己の第１の同期検証値を生成し、前記第３の秘密情報を用いて前記自己の第２の同期検証値を生成する手順と、
をさらに前記コンピュータに実行させる、付記２１に記載の鍵交換プログラム。
【符号の説明】
【０１６３】
３００ ・・・ 入力装置
３０１ ・・・ 出力装置
３０２ ・・・ 通信装置
３０３ ・・・ 乱数生成装置
３０４ ・・・ 第１の秘密情報
３０５ ・・・ 第２に秘密情報
３０６ ・・・ 自己識別子
３０７ ・・・ 相手識別子
３０８ ・・・ セッション状態
３０９ ・・・ セッション番号生成装置
３１０ ・・・ 鍵識別子生成装置
３１１ ・・・ 同期確認装置
３１２ ・・・ 秘密更新装置
３１３ ・・・ 鍵生成装置
３１４ ・・・ 鍵検証装置
３２０ ・・・ 識別子記憶装置
３２２ ・・・ 秘密情報記憶装置
３２４ ・・・ 記憶装置
【特許請求の範囲】
【請求項１】
乱数を生成する乱数生成装置と、
第１の秘密情報と第２の秘密情報とを保持する秘密情報記憶装置と、
前記乱数生成装置を用いて生成した乱数と、相手装置から受信したデータとを用いて自己の鍵識別子を生成する鍵識別子生成装置と、
前記第１の秘密情報を用いて自己の第１の同期確認値を生成し、前記第２の秘密情報を用いて自己の第２の同期確認値を生成し、該自己の第１の同期確認値と前記自己の第２の同期確認値とを前記相手装置へ送出し、前記第１の秘密情報を用いて自己の第１の同期検証値を生成し、前記第２の秘密情報を用いて自己の第２の同期検証値を生成し、相手の第１の同期確認値と相手の第２の同期確認値とを前記相手装置から受信し、前記相手の第１の同期確認値および前記相手の第２の同期確認値と、前記自己の第１の同期検証値および前記自己の第２の同期検証値とを用いて、同期判定値を生成する同期確認装置と、
前記第１の秘密情報と前記第２の秘密情報と前記鍵識別子とを受け取り、前記第２の秘密情報と前記鍵識別子とから第３の秘密情報を生成し、前記第１の秘密情報の値を前記第２の秘密情報の値に変更し、前記第２の秘密情報の値を前記第３の秘密情報の値に変更する秘密更新装置と、
前記第１の秘密情報から鍵を生成する鍵生成装置と、
を備える鍵交換装置。
【請求項２】
前記同期判定値は、前記相手の第１の同期確認値および前記相手の第２の同期確認値が、それぞれ、前記自己の第１の同期検証値および前記自己の第２の同期検証値と等しいなら、“同期”を示す０の値を持ち、前記相手の第１の同期確認値と前記自己の第２の同期検証値とが等しいなら、−１の値を持ち、前記相手の第２の同期確認値と前記自己の第１の同期検証値とが等しいなら、１の値を持ち、前記相手の第１の同期確認値と前記自己の第１の同期検証値とが等しく、かつ、前記相手の第２の同期確認値と前記自己の第２の同期検証値とが等しくないとき、２の値を持ち、
前記同期確認装置は、
前記同期判定値の値が−１に等しいとき、前記第２の秘密情報と前記鍵識別子とから前記第３の秘密情報を生成し、前記第２の秘密情報を用いて前記自己の第１の同期確認値を生成し、前記第３の秘密情報を用いて前記自己の第２の同期確認値を生成する機能と、
前記同期判定値の値が１又は２に等しいとき、前記第１の秘密情報と前記鍵識別子とから前記第３の秘密情報を生成し、前記第１の秘密情報を用いて前記自己の第１の同期確認値を生成し、前記第３の秘密情報を用いて前記自己の第２の同期確認値を生成する機能と、
前記同期判定値の値が１に等しいとき、前記第２の秘密情報と前記鍵識別子とから前記第３の秘密情報を生成し、前記第２の秘密情報を用いて前記自己の第１の同期検証値を生成し、前記第３の秘密情報を用いて前記自己の第２の同期検証値を生成する機能と、
前記同期判定値の値が−１又は２に等しいとき、前記第１の秘密情報と前記鍵識別子とから前記第３の秘密情報を生成し、前記第１の秘密情報を用いて前記自己の第１の同期検証値を生成し、前記第３の秘密情報を用いて前記自己の第２の同期検証値を生成する機能と、
をさらに備える、ことを特徴とする請求項１に記載の鍵交換装置。
【請求項３】
請求項１に記載の鍵交換装置二つからなる鍵交換システムであって、
第１の鍵交換装置が保持する自己識別子と第２の鍵交換装置が保持する相手識別子とが同一で、
前記第１の鍵交換装置が保持する相手識別子と前記第２の鍵交換装置が保持する自己識別子とが同一であり、
前記第１の鍵交換装置と前記第２の鍵交換装置とは通信路で繋がっており、
前記第１の鍵交換装置が送出するメッセージを前記第２の鍵交換装置が受信可能であり、
前記第２の鍵交換装置が送出するメッセージを前記第１の鍵交換装置が受信可能であり、
何れかの鍵交換装置には、開始命令、応答命令を入力する事が出来る
ことを特徴とする鍵交換システム。
【請求項４】
第１の鍵交換装置と第２の鍵交換装置との間で鍵の交換を行う鍵交換方法であって、
開始命令を入力したとき、前記第１の鍵交換装置が、第１の秘密情報および第２の秘密情報を用いて、それぞれ、自己の第１の同期確認値および自己の第２の同期確認値を生成し、前記自己の第１の同期確認値および前記自己の第２の同期確認値を含む開始要求メッセージを前記第２の鍵交換装置へ送信する工程と、
前記第１の鍵交換装置から相手の第１の同期確認値および相手の第２の同期確認値を含む前記開始要求メッセージを受け取ったとき、前記第２の鍵交換装置が、前記第１の秘密情報および前記第２の秘密情報を用いて、それぞれ、自己の第１の同期検証値および自己の第２の同期検証値を生成し、前記相手の第１の同期確認値、前記相手の第２の同期確認値、前記自己の第１の同期検証値、および前記自己の第２の同期検証値を用いて同期判定値を生成する工程と、
を含む、鍵交換方法。
【請求項５】
乱数を生成する手順と、
第１の秘密情報と第２の秘密情報とを保持する手順と、
前記生成された乱数と、相手装置から受信したデータとを用いて自己の鍵識別子を生成する手順と、
前記第１の秘密情報を用いて自己の第１の同期確認値を生成し、前記第２の秘密情報を用いて自己の第２の同期確認値を生成し、該自己の第１の同期確認値と前記自己の第２の同期確認値とを前記相手装置へ送出し、前記第１の秘密情報を用いて自己の第１の同期検証値を生成し、前記第２の秘密情報を用いて自己の第２の同期検証値を生成し、相手の第１の同期確認値と相手の第２の同期確認値とを前記相手装置から受信し、前記相手の第１の同期確認値および前記相手の第２の同期確認値と、前記自己の第１の同期検証値および前記自己の第２の同期検証値とを用いて、同期判定値を生成する手順と、
前記第１の秘密情報と前記第２の秘密情報と前記鍵識別子とを受け取り、前記第２の秘密情報と前記鍵識別子とから第３の秘密情報を生成し、前記第１の秘密情報の値を前記第２の秘密情報の値に変更し、前記第２の秘密情報の値を前記第３の秘密情報の値に変更する手順と、
前記第１の秘密情報から鍵を生成する手順と、
をコンピュータに実行させる鍵交換プログラム。
【請求項１】
乱数を生成する乱数生成装置と、
第１の秘密情報と第２の秘密情報とを保持する秘密情報記憶装置と、
前記乱数生成装置を用いて生成した乱数と、相手装置から受信したデータとを用いて自己の鍵識別子を生成する鍵識別子生成装置と、
前記第１の秘密情報を用いて自己の第１の同期確認値を生成し、前記第２の秘密情報を用いて自己の第２の同期確認値を生成し、該自己の第１の同期確認値と前記自己の第２の同期確認値とを前記相手装置へ送出し、前記第１の秘密情報を用いて自己の第１の同期検証値を生成し、前記第２の秘密情報を用いて自己の第２の同期検証値を生成し、相手の第１の同期確認値と相手の第２の同期確認値とを前記相手装置から受信し、前記相手の第１の同期確認値および前記相手の第２の同期確認値と、前記自己の第１の同期検証値および前記自己の第２の同期検証値とを用いて、同期判定値を生成する同期確認装置と、
前記第１の秘密情報と前記第２の秘密情報と前記鍵識別子とを受け取り、前記第２の秘密情報と前記鍵識別子とから第３の秘密情報を生成し、前記第１の秘密情報の値を前記第２の秘密情報の値に変更し、前記第２の秘密情報の値を前記第３の秘密情報の値に変更する秘密更新装置と、
前記第１の秘密情報から鍵を生成する鍵生成装置と、
を備える鍵交換装置。
【請求項２】
前記同期判定値は、前記相手の第１の同期確認値および前記相手の第２の同期確認値が、それぞれ、前記自己の第１の同期検証値および前記自己の第２の同期検証値と等しいなら、“同期”を示す０の値を持ち、前記相手の第１の同期確認値と前記自己の第２の同期検証値とが等しいなら、−１の値を持ち、前記相手の第２の同期確認値と前記自己の第１の同期検証値とが等しいなら、１の値を持ち、前記相手の第１の同期確認値と前記自己の第１の同期検証値とが等しく、かつ、前記相手の第２の同期確認値と前記自己の第２の同期検証値とが等しくないとき、２の値を持ち、
前記同期確認装置は、
前記同期判定値の値が−１に等しいとき、前記第２の秘密情報と前記鍵識別子とから前記第３の秘密情報を生成し、前記第２の秘密情報を用いて前記自己の第１の同期確認値を生成し、前記第３の秘密情報を用いて前記自己の第２の同期確認値を生成する機能と、
前記同期判定値の値が１又は２に等しいとき、前記第１の秘密情報と前記鍵識別子とから前記第３の秘密情報を生成し、前記第１の秘密情報を用いて前記自己の第１の同期確認値を生成し、前記第３の秘密情報を用いて前記自己の第２の同期確認値を生成する機能と、
前記同期判定値の値が１に等しいとき、前記第２の秘密情報と前記鍵識別子とから前記第３の秘密情報を生成し、前記第２の秘密情報を用いて前記自己の第１の同期検証値を生成し、前記第３の秘密情報を用いて前記自己の第２の同期検証値を生成する機能と、
前記同期判定値の値が−１又は２に等しいとき、前記第１の秘密情報と前記鍵識別子とから前記第３の秘密情報を生成し、前記第１の秘密情報を用いて前記自己の第１の同期検証値を生成し、前記第３の秘密情報を用いて前記自己の第２の同期検証値を生成する機能と、
をさらに備える、ことを特徴とする請求項１に記載の鍵交換装置。
【請求項３】
請求項１に記載の鍵交換装置二つからなる鍵交換システムであって、
第１の鍵交換装置が保持する自己識別子と第２の鍵交換装置が保持する相手識別子とが同一で、
前記第１の鍵交換装置が保持する相手識別子と前記第２の鍵交換装置が保持する自己識別子とが同一であり、
前記第１の鍵交換装置と前記第２の鍵交換装置とは通信路で繋がっており、
前記第１の鍵交換装置が送出するメッセージを前記第２の鍵交換装置が受信可能であり、
前記第２の鍵交換装置が送出するメッセージを前記第１の鍵交換装置が受信可能であり、
何れかの鍵交換装置には、開始命令、応答命令を入力する事が出来る
ことを特徴とする鍵交換システム。
【請求項４】
第１の鍵交換装置と第２の鍵交換装置との間で鍵の交換を行う鍵交換方法であって、
開始命令を入力したとき、前記第１の鍵交換装置が、第１の秘密情報および第２の秘密情報を用いて、それぞれ、自己の第１の同期確認値および自己の第２の同期確認値を生成し、前記自己の第１の同期確認値および前記自己の第２の同期確認値を含む開始要求メッセージを前記第２の鍵交換装置へ送信する工程と、
前記第１の鍵交換装置から相手の第１の同期確認値および相手の第２の同期確認値を含む前記開始要求メッセージを受け取ったとき、前記第２の鍵交換装置が、前記第１の秘密情報および前記第２の秘密情報を用いて、それぞれ、自己の第１の同期検証値および自己の第２の同期検証値を生成し、前記相手の第１の同期確認値、前記相手の第２の同期確認値、前記自己の第１の同期検証値、および前記自己の第２の同期検証値を用いて同期判定値を生成する工程と、
を含む、鍵交換方法。
【請求項５】
乱数を生成する手順と、
第１の秘密情報と第２の秘密情報とを保持する手順と、
前記生成された乱数と、相手装置から受信したデータとを用いて自己の鍵識別子を生成する手順と、
前記第１の秘密情報を用いて自己の第１の同期確認値を生成し、前記第２の秘密情報を用いて自己の第２の同期確認値を生成し、該自己の第１の同期確認値と前記自己の第２の同期確認値とを前記相手装置へ送出し、前記第１の秘密情報を用いて自己の第１の同期検証値を生成し、前記第２の秘密情報を用いて自己の第２の同期検証値を生成し、相手の第１の同期確認値と相手の第２の同期確認値とを前記相手装置から受信し、前記相手の第１の同期確認値および前記相手の第２の同期確認値と、前記自己の第１の同期検証値および前記自己の第２の同期検証値とを用いて、同期判定値を生成する手順と、
前記第１の秘密情報と前記第２の秘密情報と前記鍵識別子とを受け取り、前記第２の秘密情報と前記鍵識別子とから第３の秘密情報を生成し、前記第１の秘密情報の値を前記第２の秘密情報の値に変更し、前記第２の秘密情報の値を前記第３の秘密情報の値に変更する手順と、
前記第１の秘密情報から鍵を生成する手順と、
をコンピュータに実行させる鍵交換プログラム。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【公開番号】特開２０１１−２２８９７０（Ｐ２０１１−２２８９７０Ａ）
【公開日】平成２３年１１月１０日（２０１１．１１．１０）
【国際特許分類】
【出願番号】特願２０１０−９７５０６（Ｐ２０１０−９７５０６）
【出願日】平成２２年４月２１日（２０１０．４．２１）
【出願人】（０００００４２３７）日本電気株式会社 (19,353)
【Ｆターム（参考）】
【公開日】平成２３年１１月１０日（２０１１．１１．１０）
【国際特許分類】
【出願日】平成２２年４月２１日（２０１０．４．２１）
【出願人】（０００００４２３７）日本電気株式会社 (19,353)
【Ｆターム（参考）】
[ Back to top ]