(57)【要約】  デバイス間の隣接性を検査する方法及び装置を提供する。少なくとも一つ以上の乱数を連鎖的にハッシュすることで複数のハッシュ値を生成し、このハッシュ値のうちいずれか一つを所定デバイスに伝送し、所定デバイスに対するＲＴＴ測定を始め、次いで、伝送されたハッシュ値に対する応答を受信し、ＲＴＴ測定を終了するＲＴＴ測定方法。これにより、数十回〜数千回の暗号化及び復号化が要求される従来の隣接性検査より非常に効率的に隣接性検査を行える。
2008539648.tif 000002
【特許請求の範囲】
【請求項１】
（ａ）少なくとも一つ以上の乱数を連鎖的にハッシュすることで複数のハッシュ値を生成するステップと、
（ｂ）前記生成されたハッシュ値のうちいずれか一つを所定デバイスに伝送し、前記所定デバイスに対するＲＴＴ測定を始めるステップと、
（ｃ）前記伝送されたハッシュ値に対する応答を受信し、前記ＲＴＴ測定を終了するステップと、を含むことを特徴とするＲＴＴ測定方法。
【請求項２】
前記（ｂ）ステップは、前記生成されたハッシュ値のうち最後のハッシュ値を最初に伝送することを特徴とする請求項１に記載のＲＴＴ測定方法。
【請求項３】
前記（ａ）ステップは、前記少なくとも一つ以上の乱数を所定回数ほど連鎖的にハッシュし、
前記（ｂ）ステップ及び前記（ｃ）ステップはね前記所定回数内で反復されることを特徴とする請求項１に記載のＲＴＴ測定方法。
【請求項４】
前記少なくとも一つ以上の乱数を暗号化するステップをさらに含み、
前記（ｂ）ステップは、前記暗号化された乱数を前記所定デバイスに伝送することを特徴とする請求項１に記載のＲＴＴ測定方法。
【請求項５】
前記（ａ）ステップは、第１乱数及び第２乱数それぞれを連鎖的にハッシュすることで、前記第１乱数に対するハッシュ値及び前記第２乱数に対するハッシュ値を生成し、
前記（ｂ）ステップは、前記第１乱数に対するハッシュ値のうちいずれか一つを伝送し、
前記（ｃ）ステップは、前記伝送されたハッシュ値に対する応答として前記第２乱数に対するハッシュ値のうちいずれか一つを受信することを特徴とする請求項１に記載のＲＴＴ測定方法。
【請求項６】
前記（ａ）ステップは、一つの乱数を連鎖的にハッシュすることで複数のハッシュ値を生成し、
前記（ｂ）ステップは、前記ハッシュ値の一部のうちいずれか一つを伝送し、
前記（ｃ）ステップは、前記伝送されたハッシュ値に対する応答として前記一部に対する残りのうちいずれか一つを受信することを特徴とする請求項１に記載のＲＴＴ測定方法。
【請求項７】
少なくとも一つ以上の乱数を連鎖的にハッシュすることで複数のハッシュ値を生成するハッシュ部と、
前記ハッシュ部により生成されたハッシュ値のうちいずれか一つを所定デバイスに伝送し、前記伝送されたハッシュ値に対する応答を前記所定デバイスから受信する送受信部と、
前記送受信部での伝送時刻及び受信時刻に基づいて前記所定デバイスに対するＲＴＴを測定するＲＴＴ測定部と、を備えることを特徴とするＲＴＴ測定装置。
【請求項８】
少なくとも一つ以上の乱数を連鎖的にハッシュすることで複数のハッシュ値を生成するステップと、
前記生成されたハッシュ値のうちいずれか一つを所定デバイスに伝送し、前記所定デバイスに対するＲＴＴ測定を始めるステップと、
前記伝送されたハッシュ値に対する応答を受信し、前記ＲＴＴ測定を終了するステップと、を含むことを特徴とするＲＴＴ測定方法をコンピュータで実行させるためのプログラムを記録したコンピュータで読み取り可能な記録媒体。
【請求項９】
（ａ）少なくとも一つ以上の乱数を連鎖的にハッシュすることで複数のハッシュ値を生成するステップと、
（ｂ）前記生成されたハッシュ値のうちいずれか一つを所定デバイスに伝送し、前記所定デバイスに対するＲＴＴ測定を始めるステップと、
（ｃ）前記伝送されたハッシュ値に対する応答を受信し、前記ＲＴＴ測定を終了するステップと、
（ｄ）前記ＲＴＴ測定に基づいて前記所定デバイスとの隣接性如何を決定するステップと、を含むことを特徴とする隣接性検査方法。
【請求項１０】
前記応答に含まれたハッシュ値を認証するステップをさらに含み、
前記（ｄ）ステップは、前記認証の結果によって前記隣接性如何を選択的に決定することを特徴とする請求項９に記載の隣接性検査方法。
【請求項１１】
少なくとも一つ以上の乱数を連鎖的にハッシュすることで複数のハッシュ値を生成するハッシュ部と、
前記ハッシュ部により生成されたハッシュ値のうちいずれか一つを所定デバイスに伝送し、前記伝送されたハッシュ値に対する応答を前記所定デバイスから受信する送受信部と、
前記送受信部からの伝送時刻及び受信時刻に基づいて、前記所定デバイスに対するＲＴＴを測定するＲＴＴ測定部と、
前記ＲＴＴ測定部でのＲＴＴ測定に基づいて前記所定デバイスとの隣接性如何を決定する隣接性決定部と、を備えることを特徴とする隣接性検査装置。
【請求項１２】
少なくとも一つ以上の乱数を連鎖的にハッシュすることで複数のハッシュ値を生成するステップと、
前記生成されたハッシュ値のうちいずれか一つを所定デバイスに伝送し、前記所定デバイスに対するＲＴＴ測定を始めるステップと、
前記伝送されたハッシュ値に対する応答を受信して前記ＲＴＴ測定を終了するステップと、
前記ＲＴＴ測定に基づいて前記所定デバイスとの隣接性如何を決定するステップと、を含むことを特徴とする隣接性検査方法をコンピュータで実行させるためのプログラムを記録したコンピュータで読み取り可能な記録媒体。
【請求項１３】
（ａ）少なくとも一つ以上の乱数を連鎖的にハッシュすることで複数のハッシュ値を生成するステップと、
（ｂ）所定デバイスから前記所定デバイスに対するＲＴＴ測定の開始に該当するハッシュ値を受信するステップと、
（ｃ）前記受信されたハッシュ値に対する応答として、前記生成されたハッシュ値のうち、前記ＲＴＴ測定の終了に該当するいずれか一つを伝送するステップと、を含むことを特徴とするＲＴＴ測定支援方法。
【請求項１４】
前記（ｃ）ステップは、前記生成されたハッシュ値のうち、最後のハッシュ値を最初に伝送することを特徴とする請求項１３に記載のＲＴＴ測定支援方法。
【請求項１５】
暗号化された乱数を復号化するステップをさらに含み、
前記（ａ）ステップは、前記復号化された乱数を連鎖的にハッシュすることを特徴とする請求項１３に記載のＲＴＴ測定支援方法。
【請求項１６】
前記受信されたハッシュ値を認証するステップをさらに含み、
前記（ａ）ステップは、前記認証の結果によって選択的に伝送することを特徴とする請求項１３に記載のＲＴＴ測定支援方法。
【請求項１７】
前記（ａ）ステップは、前記乱数を所定回数ほど連鎖的にハッシュし、
前記（ｂ）ステップ及び前記（ｃ）ステップは、前記所定回数内で反復されることを特徴とする請求項１３に記載のＲＴＴ測定支援方法。
【請求項１８】
少なくとも一つ以上の乱数を連鎖的にハッシュすることで複数のハッシュ値を生成するハッシュ部と、
所定デバイスから前記所定デバイスに対するＲＴＴ測定の開始に該当するハッシュ値を受信し、前記受信されたハッシュ値に対する応答として、前記ハッシュ値のうち、前記ＲＴＴ測定の終了に該当するいずれか一つを伝送する送受信部と、を備えることを特徴とするＲＴＴ測定支援装置。
【請求項１９】
少なくとも一つ以上の乱数を連鎖的にハッシュすることで複数のハッシュ値を生成するステップと、
所定デバイスから前記所定デバイスに対するＲＴＴ測定の開始に該当するハッシュ値を受信するステップと、
前記受信されたハッシュ値に対する応答として、前記生成されたハッシュ値のうち、前記ＲＴＴ測定の終了に該当するいずれか一つを伝送するステップと、を含むことを特徴とするＲＴＴ測定支援方法をコンピュータで実行させるためのプログラムを記録したコンピュータで読み取り可能な記録媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、デバイス間のＲＴＴ（Ｒｏｕｎｄ  Ｔｒｉｐ  Ｔｉｍｅ）を測定する方法及び装置に係り、特に、ＲＴＴ測定を利用してデバイス間の隣接性を検査する方法及び装置に関する。
【背景技術】
【０００２】
図１は、一般的な隣接性検査が適用される通信環境を示す図である。図１を参照するに、コンテンツ提供者（ＣＰ）１１は、あるコンテンツに対する正当な権限を持っているデバイスＡ  １２に該当コンテンツを提供する。デバイスＡ  １２の所有者は、このコンテンツに対する正当な権限である者であるために、この者が所有しているデバイスＢ  １３及びデバイスＣ  １４に対しては、このコンテンツに対する配布を許容せねばならない。しかし、デバイスＡ  １２の所有者のホームネットワークではない外部のネットワークに位置したデバイスＤ  １５に対しては、このコンテンツに対する正当な権限を持っている者であるとしても、このコンテンツに対する無制限的配布を防止するために、このコンテンツの配布を許容することはない。したがって、デバイスＡ  １２から他のデバイスへのコンテンツ伝送の許容如何を決定するためには、デバイスＡ  １２と他のデバイスとの隣接性検査が先行されねばならない。
【０００３】
図２は、従来の隣接性検査プロトコルを示す図である。図２を参照するに、従来の隣接性検査プロトコルは、次のようなステップで構成される。
【０００４】
２１ステップでデバイスＡ  １は、デバイスＢ  ２にデバイスＡ  ３及びデバイスＢ  ４との隣接性検査の準備を要請するために、Ｎ個の乱数対｛Ｒａ，Ｒｂ｝１、｛Ｒａ，Ｒｂ｝２，…，｛Ｒａ，Ｒｂ｝Ｎ及び乱数対の数ＮをデバイスＢ  ４の公開キーＰｕｂＢで暗号化し、Ｅ（ＰｕｂＢ，［Ｎ，｛Ｒａ，Ｒｂ｝１，｛Ｒａ，Ｒｂ｝２，…，｛Ｒａ，Ｒｂ｝Ｎ］）を含む準備要請メッセージを伝送する。
【０００５】
２２ステップでデバイスＢ  ４は、準備要請メッセージに含まれたＥ（ＰｕｂＢ，［Ｎ，｛Ｒａ，Ｒｂ｝１，｛Ｒａ，Ｒｂ｝２，…，｛Ｒａ，Ｒｂ｝Ｎ］）をデバイスＢ  ４の個人キーＰｒｉｖＢで復号化し、デバイスＡ  ３とデバイスＢ  ４との隣接性検査の準備が完了したことを表す準備応答メッセージを生成し、この準備応答メッセージをデバイスＡ  ３に伝送する。
【０００６】
２３ステップでデバイスＡ  ３は、デバイスＡ  ３とデバイスＢ  ４との隣接性検査の通過に挑戦するために、Ｎ個の乱数｛Ｒａ｝１，｛Ｒａ｝２，…，｛Ｒａ｝Ｎのうち、｛Ｒａ｝１及びＩ＝１を含む挑戦要請メッセージ、すなわち｛１，Ｒａ｝１を含む挑戦要請メッセージを生成し、この挑戦要請メッセージをデバイスＢ  ４に伝送する。また、２３ステップでデバイスＡ  ３は、これと同時に挑戦要請メッセージ伝送時刻を測定することによって、デバイスＢ  ４に対するＲＴＴ測定を始める。
【０００７】
２４ステップでデバイスＢ  ４は、挑戦要請メッセージに含まれた乱数｛Ｒａ｝１と、Ｎ個の乱数｛Ｒａ｝１，｛Ｒａ｝２，…，｛Ｒａ｝Ｎのうち、挑戦要請メッセージに含まれたＩ＝１に該当する｛Ｒａ｝１とを比較し、両者が一致すれば、挑戦要請メッセージに含まれた乱数が真であると決定し、両者が一致しなければ、挑戦要請メッセージに含まれた乱数が真でないと決定する。また、２４ステップでデバイスＢ  ４は、挑戦要請メッセージに含まれた乱数が真であると決定された場合に、Ｎ個の乱数｛Ｒｂ｝１，｛Ｒｂ｝２，…，｛Ｒｂ｝Ｎのうち、挑戦要請メッセージに含まれたＩ＝１に該当する乱数｛Ｒｂ｝１及びＩ＝１を含む挑戦応答メッセージ、すなわち［１，｛Ｒｂ｝１］を含む挑戦応答メッセージを生成し、この挑戦応答メッセージをデバイスＡ  ３に伝送する。
【０００８】
２４ステップでデバイスＡ  ３は、［１，｛Ｒｂ｝１］を含む挑戦応答メッセージを受信し、これと同時に挑戦応答メッセージの受信時刻を測定することによって、デバイスＢ  ４に対するＲＴＴ測定を終了する。すなわち、挑戦応答メッセージ受信時刻から挑戦要請メッセージ伝送時刻を引いた値がＲＴＴとなる。また、デバイスＡ  ３は、挑戦応答メッセージに含まれた乱数｛Ｒｂ｝１と、Ｎ個の乱数｛Ｒｂ｝１，｛Ｒｂ｝２，…，｛Ｒｂ｝Ｎのうち、挑戦応答メッセージに含まれたＩ＝１に該当する乱数｛Ｒｂ｝１とを比較し、両者が一致すれば、挑戦応答メッセージに含まれた乱数が真であると決定し、両者が一致しなければ、挑戦応答メッセージに含まれた乱数が真でないと決定する。
【０００９】
また、２４ステップでデバイスＡ  ３は、挑戦応答メッセージに含まれた乱数が真であると決定された場合にＲＴＴと隣接性臨界値とを比較し、その結果、ＲＴＴが隣接性臨界値より小さければ、デバイスＡ  ３とデバイスＢ  ４とが互いに隣接していると決定し、デバイスＡ  ３とデバイスＢ  ４との隣接性検査が成功したことと処理する。また、デバイスＡ  ３は、ＲＴＴが隣接性臨界値より小さくなければ、デバイスＡ  ３とデバイスＢ  ４とが互いに隣接していないと決定し、Ｉを１ずつ増加させ、ＩとＮとを比較してＩがＮより小さな場合、２３ステップに戻り、ＩがＮより小さくない場合、デバイスＡ  ３とデバイスＢ  ４との隣接性検査が失敗したと処理する。
【００１０】
前記のように、デバイスＡ３とデバイスＢ  ４との隣接性を検査するためにＲＴＴは１回のみ測定されるものではなく、数十回〜数千回反復的に測定される。これは、ネットワークなどの伝送経路のトラフィックの可変性を考慮して、ただ１回でもデバイスＡ  ３とデバイスＢ  ４とが隣接していると見られるＲＴＴが測定されれば、デバイスＡ  ３とデバイスＢ  ４とは隣接していると見なされるためである。しかし、このようにＲＴＴが数十回〜数千回反復的に測定される場合、数十回〜数千回の暗号化及び復号化が行われねばならないために非常に非効率的であり、これは、デバイスＡ  ３及びデバイスＢ  ４それぞれのシステムに莫大な負荷として作用するという問題点があった。
【発明の開示】
【発明が解決しようとする課題】
【００１１】
本発明が解決しようとする技術的課題は、数十回〜数千回の暗号化及び復号化が要求される従来の隣接性検査よりはるかに効率的に隣接性検査を行える方法及び装置を提供するところにある。また、前記方法をコンピュータで実行させるためのプロラムを記録したコンピュータで読み取り可能な記録媒体を提供するところにある。
【課題を解決するための手段】
【００１２】
前記技術的課題を解決するための本発明によるＲＴＴ測定方法は、少なくとも一つ以上の乱数を連鎖的にハッシュすることで複数のハッシュ値を生成するステップと、前記生成されたハッシュ値のうちいずれか一つを所定デバイスに伝送し、前記所定デバイスに対するＲＴＴ測定を始めるステップと、前記伝送されたハッシュ値に対する応答を受信し、前記ＲＴＴ測定を終了するステップとを含む。
【００１３】
前記他の技術的課題を解決するための本発明によるＲＴＴ測定装置は、少なくとも一つ以上の乱数を連鎖的にハッシュすることで複数のハッシュ値を生成するハッシュ部と、前記ハッシュ部により生成されたハッシュ値のうちいずれか一つを所定デバイスに伝送し、前記伝送されたハッシュ値に対する応答を前記所定デバイスから受信する送受信部と、前記送受信部からの伝送時刻及び受信時刻に基づいて前記所定デバイスに対するＲＴＴを測定するＲＴＴ測定部とを備える。
【００１４】
前記さらに他の技術的課題を解決するために、本発明は、前記ＲＴＴ測定方法をコンピュータで実行させるためのプログラムを記録したコンピュータで読み取り可能な記録媒体を提供する。
【００１５】
前記さらに他の技術的課題を解決するための本発明による隣接性検査方法は、少なくとも一つ以上の乱数を連鎖的にハッシュすることで複数のハッシュ値を生成するステップと、前記生成されたハッシュ値のうちいずれか一つを所定デバイスに伝送し、前記所定デバイスに対するＲＴＴ測定を始めるステップと、前記伝送されたハッシュ値に対する応答を受信し、前記ＲＴＴ測定を終了するステップと、前記ＲＴＴ測定に基づいて前記所定デバイスとの隣接性如何を決定するステップとを含む。
【００１６】
前記さらに他の技術的課題を解決するための本発明による隣接性検査装置は、少なくとも一つ以上の乱数を連鎖的にハッシュすることで複数のハッシュ値を生成するハッシュ部と、前記ハッシュ部により生成されたハッシュ値のうちいずれか一つを所定デバイスに伝送し、前記伝送されたハッシュ値に対する応答を前記所定デバイスから受信する送受信部と、前記送受信部からの伝送時刻及び受信時刻に基づいて、前記所定デバイスに対するＲＴＴを測定するＲＴＴ測定部と、前記ＲＴＴ測定部でのＲＴＴ測定に基づいて前記所定デバイスとの隣接性如何を決定する隣接性決定部とを備える。
【００１７】
前記さらに他の技術的課題を解決するために、本発明は、前記隣接性検査方法をコンピュータで実行させるためのプログラムを記録したコンピュータで読み取り可能な記録媒体を提供する。
【００１８】
前記さらに他の技術的課題を解決するための本発明によるＲＴＴ測定支援方法は、少なくとも一つ以上の乱数を連鎖的にハッシュすることで複数のハッシュ値を生成するステップと、所定デバイスから前記所定デバイスに対するＲＴＴ測定の開始に該当するハッシュ値を受信するステップと、前記受信されたハッシュ値に対する応答として、前記生成されたハッシュ値のうち、前記ＲＴＴ測定の終了に該当するいずれか一つを伝送するステップとを含む。
【００１９】
前記さらに他の技術的課題を解決するための本発明によるＲＴＴ測定支援装置は、少なくとも一つ以上の乱数を連鎖的にハッシュすることで複数のハッシュ値を生成するハッシュ部と、所定デバイスから前記所定デバイスに対するＲＴＴ測定の開始に該当するハッシュ値を受信し、前記受信されたハッシュ値に対する応答として、前記ハッシュ値のうち、前記ＲＴＴ測定の終了に該当するいずれか一つを伝送する送受信部とを備える。
【００２０】
前記さらに他の技術的課題を解決するために、本発明は、前記ＲＴＴ測定支援方法をコンピュータで実行させるためのプログラムを記録したコンピュータで読み取り可能な記録媒体を提供する。
【発明の効果】
【００２１】
本発明によれば、ハッシュチェーンを利用して数十回〜数千回ＲＴＴを測定することによって、数十回〜数千回の暗号化及び復号化が要求される従来の隣接性検査よりはるかに効率的に隣接性検査を行える。また、本発明によれば、最初の挑戦要請メッセージに外部の攻撃に最も強い最後のハッシュ値を含めることによって、さらに強い隣接性検査を行える。
【発明を実施するための最良の形態】
【００２２】
以下では、図面を参照して本発明の望ましい実施形態を詳細に説明する。
【００２３】
図３は、本発明の望ましい一実施形態による隣接性検査プロトコルを示す図である。図３を参照するに、本実施形態による隣接性検査プロトコルは次のようなステップで構成される。特に、本実施形態による隣接性検査プロトコルは、従来の隣接性検査プロトコルとは異なって、暗号化及び復号化の代わりにハッシュチェーンを利用した。ハッシングは、一つの文字列を元来のものを象徴するさらに短い長さの値に変換することをいい、指数演算など複雑な演算が要求される現在の暗号化及び復号化より非常に簡単である。
【００２４】
３１ステップでデバイスＡ  ３は、デバイスＢ  ４にデバイスＡ  ３とデバイスＢ４との隣接性検査の準備を要請するために、乱数Ｒａ、Ｒｂ及びハッシュ回数ＮをデバイスＢ  ４の公開キーＰｕｂＢで暗号化し、Ｅ（ＰｕｂＢ，［Ｎ，｛Ｒａ，Ｒｂ｝］）を含む準備要請メッセージを伝送する。また、３１ステップでデバイスＡ  ３は、乱数Ｒａ、ＲｂをＮ回数ほど連鎖的にハッシュすることで、乱数Ｒａに対するハッシュ値を生成し、乱数Ｒｂに対するハッシュ値を生成する。図２に図示された従来隣接性検査プロトコルは２Ｎ回数ほどの暗号化及び復号化が要求されるが、本実施形態による隣接性検査プロトコルは２回の暗号化及び復号化しか要求されない。
【００２５】
３２ステップでデバイスＢ  ４は、準備要請メッセージに含まれたＥ（ＰｕｂＢ，［Ｎ，｛Ｒａ，Ｒｂ｝］）をデバイスＢ  ４の個人キーＰｒｉｖＢで復号化し、乱数Ｒａ、Ｒｂをハッシュ回数Ｎほど連鎖的にハッシュすることで乱数Ｒａに対するハッシュ値を生成し、乱数Ｒｂに対するハッシュ値を生成する。また、３２ステップでデバイスＢ  ４は、このようなハッシングが完了した場合、デバイスＡ  ３とデバイスＢ  ４との隣接性検査の準備が完了したことを表す準備応答メッセージを生成し、この準備応答メッセージをデバイスＡ  ３に伝送する。
【００２６】
３３ステップでデバイスＡ  ３は、デバイスＡ  ３とデバイスＢ  ４との隣接性検査の通過に挑戦するために、乱数Ｒａに対するハッシュ値Ｈ（Ｒａ），Ｈ２（Ｒａ），Ｈ３（Ｒａ），…，ＨＮ（Ｒａ）のうち、ＨＮ（Ｒａ）及びハッシュ順序Ｉ＝０を含む挑戦要請メッセージ、すなわち｛０，ＨＮ（Ｒａ）｝を含む挑戦要請メッセージを生成し、この挑戦要請メッセージをデバイスＢ  ４に伝送する。また、３３ステップでデバイスＡ  ３は、これと同時に挑戦要請メッセージ伝送時刻を測定することによってデバイスＢ  ４に対するＲＴＴ測定を始める。
【００２７】
このように、最後のハッシュ値ＨＮ（Ｒａ）を最初の挑戦要請メッセージに含めることは、最後のハッシュ値ＨＮ（Ｒａ）が最も多くハッシュされていて、外部の攻撃に他のハッシュ値より強いためである。すなわち、最初の挑戦要請メッセージに外部の攻撃に最も強いハッシュ値を含めることによって、さらに強い（ｒｏｂｕｓｔ）隣接性検査を行うことができる。
【００２８】
３４ステップでデバイスＢ  ４は、挑戦要請メッセージに含まれたハッシュ値ＨＮ（Ｒａ）と、乱数Ｒａに対するハッシュ値Ｈ（Ｒａ），Ｈ２（Ｒａ），Ｈ３（Ｒａ），…，ＨＮ（Ｒａ）のうち、挑戦要請メッセージに含まれたハッシュ順序Ｉ＝０に該当するハッシュ値ＨＮ（Ｒａ）とを比較して、両者が一致すれば、挑戦要請メッセージに含まれたハッシュ値が真であると決定し、両者が一致しなければ、挑戦要請メッセージに含まれたハッシュ値が真でないと決定する。また、３４ステップでデバイスＢ  ４は、挑戦要請メッセージに含まれたハッシュ値が真であると決定された場合に、乱数Ｒｂに対するハッシュ値Ｈ（Ｒｂ），Ｈ２（Ｒｂ），Ｈ３（Ｒｂ），…，ＨＮ（Ｒｂ）のうち、挑戦要請メッセージに含まれたハッシュ順序Ｉ＝０に該当するハッシュ値及び前記Ｉ＝０を含む挑戦応答メッセージ、すなわち｛０，ＨＮ（Ｒｂ）｝を含む挑戦応答メッセージを生成して、この挑戦応答メッセージをデバイスＡ  ３に伝送する。
【００２９】
ある攻撃者デバイスが色々な方式で隣接性検査を妨害することも可能である。例えば、攻撃者デバイスが挑戦要請メッセージを横取りした後、デバイスＢ  ４に攻撃者デバイスにより偽造された挑戦要請メッセージを伝送することによって、攻撃者デバイスは自身の存在を隠しつつ、デバイスＢ  ４にＲＴＴ測定が正常に行われているように示すことができる。前記の挑戦要請メッセージのハッシュ値認証はこれを防止するためのものである。
【００３０】
３４ステップでデバイスＡ  ３は、｛０，ＨＮ（Ｒｂ）｝を含む挑戦応答メッセージを受信し、これと同時に挑戦応答メッセージの受信時刻を測定することによってデバイスＢ  ４に対するＲＴＴ測定を終了する。すなわち、挑戦応答メッセージ受信時刻から挑戦要請メッセージ伝送時刻を引いた値がＲＴＴとなる。また、３４ステップでデバイスＡ  ３は、挑戦応答メッセージに含まれたハッシュ値ＨＮ（Ｒｂ）と、乱数Ｒｂに対するハッシュ値Ｈ（Ｒｂ），Ｈ２（Ｒｂ），Ｈ３（Ｒｂ），…，ＨＮ（Ｒｂ）のうち、挑戦応答メッセージに含まれたハッシュ順序Ｉ＝０に該当するハッシュ値ＨＮ（Ｒｂ）とを比較して、両者が一致すれば、挑戦応答メッセージに含まれたハッシュ値が真であると決定し、両者が一致しなければ、挑戦応答メッセージに含まれたハッシュ値が真でないと決定する。
【００３１】
攻撃者デバイスが挑戦応答メッセージを横取りした後、デバイスＡ  ３に攻撃者デバイスにより操作された挑戦応答メッセージを伝送することによってＲＴＴをでっち上げる操作できる。前記の挑戦応答メッセージのハッシュ値認証はこれを防止するためのことである。
【００３２】
また、３４ステップでデバイスＡ  ３は、挑戦応答メッセージに含まれたハッシュ値が真であると決定された場合にＲＴＴと隣接性臨界値とを比較し、その結果、ＲＴＴが隣接性臨界値より小さければ、デバイスＡ  ３とデバイスＢ  ４とが互いに隣接していると決定し、デバイスＡ  ３とデバイスＢ  ４との隣接性検査が成功したと処理する。また、３４ステップでデバイスＡ  ３は、ＲＴＴが隣接性臨界値より小さくなければ、デバイスＡ  ３とデバイスＢ  ４とが互いに隣接していないと決定し、Ｉを１ずつ増加させ、ＩとＮとを比較してＩがＮより小さな場合、３３ステップに戻り、ＩがＮより小さくない場合、デバイスＡ  ３とデバイスＢ  ４との隣接性検査が失敗したと処理する。
【００３３】
図４は、本発明の望ましい他の実施形態による隣接性検査プロトコルを示す図である。図４を参照するに、本実施形態による隣接性検査プロトコルは、次のようなステップで構成される。
【００３４】
４１ステップでデバイスＡ  ３は、デバイスＢ  ４にデバイスＡ  ３とデバイスＢ４との隣接性検査の準備を要請するために、乱数Ｒ及びハッシュ回数２ＮをデバイスＢ  ４の公開キーＰｕｂＢで暗号化し、Ｅ（ＰｕｂＢ，｛２Ｎ，Ｒ｝）を含む準備要請メッセージを生成し、この準備要請メッセージをデバイスＢ  ４に伝送する。また、４１ステップでデバイスＡ３は、乱数Ｒを２Ｎ回数ほど連鎖的にハッシュすることで、乱数Ｒに対するハッシュ値を生成する。図２に図示された従来の隣接性検査プロトコルは、２Ｎ回数ほどの暗号化及び復号化が要求されるが、本実施形態による隣接性検査プロトコルは、一回の暗号化及び復号化しか要求されない。
【００３５】
４２ステップでデバイスＢ  ４は、準備要請メッセージに含まれた暗号化されたＥ（ＰｕｂＢ，｛２Ｎ，Ｒ｝）を、デバイスＢ  ４の個人キーＰｒｉｖＢで復号化し、乱数Ｒをハッシュ回数２Ｎほど連鎖的にハッシュすることで、乱数Ｒに対するハッシュ値を生成する。また、４２ステップでデバイスＢ  ４は、このようなハッシングが完了した場合、デバイスＡ  ３とデバイスＢ  ４との隣接性検査の準備が完了したことを表す準備応答メッセージを生成し、この準備応答メッセージをデバイスＡ  ３に伝送する。
【００３６】
４３ステップでデバイスＡ  ３は、デバイスＡ  ３とデバイスＢ  ４との隣接性検査の通過に挑戦するために、乱数Ｒに対するハッシュ値Ｈ（Ｒ），Ｈ２（Ｒ），Ｈ３（Ｒ），…，Ｈ２Ｎ（Ｒ）の偶数番目のハッシュ値Ｈ２（Ｒ），Ｈ４（Ｒ），…，Ｈ２Ｎ（Ｒ）のうち、Ｈ２Ｎ（Ｒ）及びハッシュ順序Ｉ＝０を含む挑戦要請メッセージ、すなわち｛０，Ｈ２Ｎ（Ｒ）｝を含む挑戦要請メッセージを生成し、この挑戦要請メッセージをデバイスＢ  ４に伝送する。また、４３ステップでデバイスＡ  ３は、これと同時に挑戦要請メッセージ伝送時刻を測定することによってデバイスＢ  ４に対するＲＴＴ測定を始める。
【００３７】
４４ステップでデバイスＢ  ４は、挑戦要請メッセージに含まれたハッシュ値Ｈ２Ｎ（Ｒ）と、乱数Ｒに対するハッシュ値Ｈ（Ｒ），Ｈ２（Ｒ），Ｈ３（Ｒ），…，Ｈ２Ｎ（Ｒ）の偶数番目のハッシュ値Ｈ２（Ｒ），Ｈ４（Ｒ），…，Ｈ２Ｎ（Ｒ）のうち、挑戦要請メッセージに含まれたハッシュ順序Ｉ＝０に該当するハッシュ値Ｈ２Ｎ（Ｒ）とを比較して、両者が一致すれば、挑戦要請メッセージに含まれたハッシュ値が真であると決定し、両者が一致しなければ、挑戦要請メッセージに含まれたハッシュ値が真でないと決定する。また、４４ステップでデバイスＢ  ４は、挑戦要請メッセージに含まれたハッシュ値が真であると決定された場合に、乱数Ｒに対するハッシュ値Ｈ（Ｒ），Ｈ２（Ｒ），Ｈ３（Ｒ），…，Ｈ２Ｎ（Ｒ）の奇数番目のハッシュ値Ｈ（Ｒ），Ｈ３（Ｒ），…，Ｈ２Ｎ−１（Ｒ）のうち、挑戦要請メッセージに含まれたハッシュ順序Ｉ＝０に該当するハッシュ値Ｈ２Ｎ−１（Ｒ）及びＩ＝０を含む挑戦応答メッセージ、すなわち｛０，Ｈ２Ｎ−１（Ｒ）｝を含む挑戦応答メッセージを生成し、この挑戦応答メッセージをデバイスＡ  ３に伝送する。
【００３８】
４４ステップでデバイスＡ  ３は、｛０，Ｈ２Ｎ−１（Ｒ）｝を含む挑戦応答メッセージを受信し、これと同時に挑戦応答メッセージの受信時刻を測定することによってデバイスＢ  ４に対するＲＴＴ測定を終了する。すなわち、挑戦応答メッセージ受信時刻から挑戦要請メッセージ伝送時刻を引いた値がＲＴＴになる。また、４４ステップでデバイスＡ  ３は、挑戦応答メッセージに含まれたハッシュ値Ｈ２Ｎ−１（Ｒ）と、乱数Ｒに対するハッシュ値Ｈ（Ｒ），Ｈ２（Ｒ），Ｈ３（Ｒ），…，Ｈ２Ｎ（Ｒ）の奇数番目のハッシュ値Ｈ（Ｒ），Ｈ３（Ｒ），…，Ｈ２Ｎ−１（Ｒ）のうち、挑戦応答メッセージに含まれたハッシュ順序Ｉ＝０に該当するハッシュ値Ｈ２Ｎ−１（Ｒ）とを比較して、両者が一致すれば、挑戦応答メッセージに含まれたハッシュ値が真であると決定し、両者が一致しなければ、挑戦応答メッセージに含まれたハッシュ値が真でないと決定する。
【００３９】
また、４４ステップでデバイスＡ  ３は、挑戦応答メッセージに含まれたハッシュ値が真であると決定された場合に、ＲＴＴと隣接性臨界値とを比較して、その結果、ＲＴＴが隣接性臨界値より小さければ、デバイスＡ  ３とデバイスＢ  ４とが互いに隣接していると決定し、デバイスＡ  ３とデバイスＢ  ４との隣接性検査が成功したと処理する。また、４４ステップでデバイスＡ  ３は、ＲＴＴが隣接性臨界値より小さくなければ、デバイスＡ  ３とデバイスＢ  ４とが互いに隣接していないと決定し、Ｉを１ずつ増加させ、ＩとＮとを比較してＩがＮより小さな場合、４３ステップに戻り、ＩがＮより小さくない場合、デバイスＡ  ３とデバイスＢ  ４との隣接性検査が失敗したと処理する。
【００４０】
当業者ならば、図３及び図４に図示された隣接性検査プロトコルに基づいて、少なくとも一つの以上の乱数を連鎖的にハッシュする隣接性検査プロトコルを容易に設計できるということを理解できるであろう。
【００４１】
図５は、本発明の望ましい一実施形態による隣接性検査システムの構成図である。図５を参照するに、隣接性検査装置は、図３及び図４に図示されたデバイスＡ  ３に搭載され、乱数生成部３０１、暗号化部３０２、準備要請メッセージ生成部３０３、ハッシュ部３０４、挑戦要請メッセージ生成部３０５、ＲＴＴ測定部３０６、ハッシュ値認証部３０７、隣接性決定部３０８、送受信部３０９、及びメッセージ判別部３１０で構成される。また、隣接性検査支援装置は、図３及び図４に図示されたデバイスＢ  ４に搭載され、復号化部４０１、ハッシュ部４０２、準備応答メッセージ生成部４０３、ハッシュ値認証部４０４、挑戦応答メッセージ生成部４０５、送受信部４０６、及びメッセージ判別部４０７で構成される。
【００４２】
前記のように、図３及び図４に図示されたデバイスＡ  ３及びデバイスＢ  ４は同じ構成要素で構成されているが、図３及び図４に図示された隣接性検査プロトコルの差によってその機能は多少差がある。以下では、図３に図示されたデバイスの観点で前記の構成要素を説明し、次いで、図４に図示されたデバイスの観点で前記の構成要素を説明する。
【００４３】
まず、図３に図示されたデバイスＡ  ３の隣接性検査装置について説明する。
【００４４】
乱数生成部３０１は、２つの乱数Ｒａ、Ｒｂを生成する。
【００４５】
暗号化部３０２は、乱数生成部３０１で生成された乱数Ｒａ、Ｒｂ及びハッシュ回数ＮをデバイスＢ  ４の公開キーＰｕｂＢで暗号化することによって、Ｅ（ＰｕｂＢ，［Ｎ，｛Ｒａ，Ｒｂ｝］）を生成する。一般的に、暗号化部３０２は、ＲＳＡ（Ｒｉｖｅｓｔ  Ｓｈａｍｉｒ  Ａｄｌｅｍａｎ）のような公開キーアルゴリズムを使用して暗号化する。ハッシュ回数Ｎはユーザにより決定されてもよく、デバイス設計者によりデバイスＡ  ３にデフォルト値として保存されてもよい。
【００４６】
準備要請メッセージ生成部３０３は、デバイスＡ３とデバイスＢ  ４との隣接性検査の準備を要請するために、暗号化部３０２により暗号化された乱数Ｒａ、Ｒｂ及びハッシュ回数Ｎを含む準備要請メッセージ、すなわちＥ（ＰｕｂＢ，［Ｎ，｛Ｒａ，Ｒｂ｝］）を含む準備要請メッセージを生成する。
【００４７】
ハッシュ部３０４は、乱数生成部３０１で生成された乱数Ｒａ、ＲｂをＮ回数ほど連鎖的にハッシュすることで乱数Ｒａに対するハッシュ値を生成し、乱数Ｒｂに対するハッシュ値を生成する。一般的に、ハッシュ部３０４は、ＳＨＡ（Ｓｅｃｕｒｅ  Ｈａｓｈ  Ａｌｇｏｒｉｔｈｍ）−１のようなハッシュ関数を使用してハッシュする。さらに詳細に説明すれば、ハッシュ部３０４は、乱数ＲａをハッシュすることでＨ（Ｒａ）を生成し、次いで、Ｈ（Ｒａ）をハッシュすることでＨ２（Ｒａ）を生成する。ハッシュ部３０４は、このような過程をＮ回数ほど反復することによって、Ｈ（Ｒａ），Ｈ２（Ｒａ），Ｈ３（Ｒａ），…，ＨＮ（Ｒａ）を生成する。同様に、ハッシュ部３０４は、乱数ＲｂをハッシュすることでＨ（Ｒｂ）を生成し、次いで、Ｈ（Ｒｂ）をハッシュすることでＨ２（Ｒｂ）を生成する。ハッシュ部３０４は、このような過程をＮ回数ほど反復することによってＨ（Ｒｂ），Ｈ２（Ｒｂ），Ｈ３（Ｒｂ），…，ＨＮ（Ｒｂ）を生成する。
【００４８】
挑戦要請メッセージ生成部３０５は、デバイスＡ  ３とデバイスＢ  ４との隣接性検査の通過に挑戦するために、Ｎ回数内で順次にハッシュ部３０４で生成された乱数Ｒａに対するハッシュ値Ｈ（Ｒａ），Ｈ２（Ｒａ），Ｈ３（Ｒａ），…，ＨＮ（Ｒａ）のうちいずれか一つ、及びハッシュ順序Ｉを含む挑戦要請メッセージ、すなわち｛Ｉ，ＨＮ−Ｉ（Ｒａ）｝を含む挑戦要請メッセージを生成する。さらに詳細に説明すれば、挑戦要請メッセージ生成部３０５は、メッセージ判別部３１０での判別結果、送受信部３０９に受信されたメッセージが、デバイスＡ  ３とデバイスＢ  ４との隣接性検査の準備が完了したことを表す準備応答メッセージである場合、ハッシュ部３０４で生成された乱数Ｒａに対するハッシュ値Ｈ（Ｒａ），Ｈ２（Ｒａ），Ｈ３（Ｒａ），…，ＨＮ（Ｒａ）のうち、最後のハッシュ値ＨＮ（Ｒａ）及びハッシュ順序Ｉ＝０を含む最初の挑戦要請メッセージ、すなわち｛Ｉ、ＨＮ（Ｒａ）｝を含む最初の挑戦要請メッセージを生成する。
【００４９】
次いで、挑戦要請メッセージ生成部３０５は、隣接性決定部３０８から挑戦要請メッセージ生成を指示された場合、ハッシュ部３０４で生成された乱数Ｒａに対するハッシュ値Ｈ（Ｒａ），Ｈ２（Ｒａ），Ｈ３（Ｒａ），…，ＨＮ（Ｒａ）のうち、最後のハッシュ値ＨＮ（Ｒａ）の次のハッシュ値ＨＮ−１（Ｒａ）及びハッシュ順序Ｉ＝１を含む最初の挑戦要請メッセージ、すなわち｛Ｉ、ＨＮ−１（Ｒａ）｝を含む最初の挑戦要請メッセージを生成する。このような方式で、挑戦要請メッセージ生成部３０５は、順次に｛Ｉ，ＨＮ−２（Ｒａ）｝，｛Ｉ，ＨＮ−３（Ｒａ）｝，…，｛Ｉ，Ｈ（Ｒａ）｝を含む挑戦要請メッセージを生成する。
【００５０】
ＲＴＴ測定部３０６は、送受信部３０９での挑戦要請メッセージ伝送時刻及び挑戦応答メッセージ受信時刻に基づいて、デバイスＡ  ３とデバイスＢ  ４との間のＲＴＴを選択的に測定する。さらに詳細に説明すれば、ＲＴＴ測定部３０６は、送受信部３０９での挑戦要請メッセージ伝送時刻を測定し、送受信部３０９での挑戦応答メッセージ受信時刻を測定する。また、ＲＴＴ測定部３０６は、このように測定された挑戦要請メッセージ伝送時刻と挑戦応答メッセージ受信時刻との差からＲＴＴを測定する。すなわち、挑戦応答メッセージ受信時刻から挑戦要請メッセージ伝送時刻を引いた値がＲＴＴになる。
【００５１】
ハッシュ値認証部３０７は、メッセージ判別部３１０での判別結果、送受信部３０９に受信されたメッセージが、送受信部３０９から伝送された挑戦要請メッセージに対する応答であり、｛Ｉ，ＨＮ−Ｉ（Ｒｂ）｝を含む挑戦応答メッセージである場合、挑戦応答メッセージに含まれたハッシュ値を認証する。さらに詳細に説明すれば、ハッシュ値認証部３０７は、挑戦応答メッセージに含まれたハッシュ値ＨＮ−Ｉ（Ｒｂ）と、乱数Ｒｂに対するハッシュ値Ｈ（Ｒｂ），Ｈ２（Ｒｂ），Ｈ３（Ｒｂ），…，ＨＮ（Ｒｂ）のうち、挑戦応答メッセージに含まれたハッシュ順序Ｉに該当するハッシュ値ＨＮ−Ｉ（Ｒｂ）とを比較して、両者が一致すれば、挑戦応答メッセージに含まれたハッシュ値が真であると決定し、両者が一致しなければ、挑戦応答メッセージに含まれたハッシュ値が真でないと決定する。
【００５２】
隣接性決定部３０８は、ＲＴＴ測定部３０６でのＲＴＴ測定に基づいて、ハッシュ値認証部３０７での認証結果によってデバイスＡ  ３とデバイスＢ  ４との隣接性如何を選択的に決定する。さらに詳細に説明すれば、隣接性決定部３０８は、ハッシュ値認証部３０７での認証結果、挑戦応答メッセージに含まれたハッシュ値が真であると決定された場合にＲＴＴ測定部３０６で測定されたＲＴＴと隣接性臨界値とを比較し、その結果、ＲＴＴ測定部３０６で測定されたＲＴＴが隣接性臨界値より小さければ、デバイスＡ  ３とデバイスＢ  ４とが互いに隣接していると決定する。また、隣接性決定部３０８は、ＲＴＴ測定部３０６で測定されたＲＴＴが隣接性臨界値より小さくなければ、デバイスＡ  ３とデバイスＢ  ４とが互いに隣接していないと決定し、Ｎ回数内で隣接性検査を通過するまで挑戦要請メッセージ生成部３０３に挑戦要請メッセージ生成を指示する。
【００５３】
送受信部３０９は、準備要請メッセージ生成部３０３で生成された準備要請メッセージを伝送するか、挑戦要請メッセージ生成部３０５で生成された挑戦要請メッセージを伝送する。また、送受信部３０９は、ネットワークを経由してデバイスＢ  ４から準備応答メッセージまたは挑戦応答メッセージを受信する。
【００５４】
メッセージ判別部３１０は、送受信部３０９に受信されたメッセージが準備応答メッセージであるか、または挑戦応答メッセージであるかを判別する。さらに詳細に説明すれば、メッセージ判別部３１０は、送受信部３０９に受信されたメッセージに含まれたメッセージタイプを参照して準備応答メッセージであるか、または挑戦応答メッセージであるかを判別する。
【００５５】
次いで、図３に図示されたデバイスＢ  ４の隣接性検査支援装置について説明する。
【００５６】
復号化部４０１は、メッセージ判別部４０７での判別結果、送受信部４０６に受信されたメッセージが準備要請メッセージである場合、準備要請メッセージに含まれた暗号化された乱数Ｒａ、Ｒｂ及びハッシュ回数Ｎ、すなわちＥ（ＰｕｂＢ，［Ｎ，｛Ｒａ，Ｒｂ｝］）をデバイスＢ  ４の個人キーＰｒｉｖＢで復号化する。
【００５７】
ハッシュ部４０２は、復号化部４０１により復号化された乱数Ｒａ、Ｒｂを、復号化部４０１により復号化されたハッシュ回数Ｎほど連鎖的にハッシュすることで、乱数Ｒａに対するハッシュ値を生成し、乱数Ｒｂに対するハッシュ値を生成する。
【００５８】
準備応答メッセージ生成部４０３は、ハッシュ部４０２でのハッシングが完了した場合、デバイスＡ  ３とデバイスＢ  ４との隣接性検査の準備が完了したことを表す準備応答メッセージを生成する。
【００５９】
ハッシュ値認証部４０４は、メッセージ判別部４０７での判別結果、送受信部４０６に受信されたメッセージが｛Ｉ，ＨＮ−Ｉ（Ｒａ）｝を含む挑戦要請メッセージである場合、挑戦要請メッセージに含まれたハッシュ値を認証する。さらに詳細に説明すれば、ハッシュ値認証部４０４は、挑戦要請メッセージに含まれたハッシュ値｛Ｉ，ＨＮ−Ｉ（Ｒａ）｝と、乱数Ｒａに対するハッシュ値Ｈ（Ｒａ），Ｈ２（Ｒａ），Ｈ３（Ｒａ），…，ＨＮ（Ｒａ）のうち、挑戦要請メッセージに含まれたハッシュ順序Ｉに該当するハッシュ値｛Ｉ，ＨＮ−Ｉ（Ｒａ）｝とを比較して、両者が一致すれば、挑戦要請メッセージに含まれたハッシュ値が真であると決定し、両者が一致しなければ、挑戦要請メッセージに含まれたハッシュ値が真でないと決定する。
【００６０】
挑戦応答メッセージ生成部４０５は、ハッシュ値認証部４０４での認証結果、挑戦要請メッセージに含まれたハッシュ値が真であると決定された場合に、乱数Ｒｂに対するハッシュ値Ｈ（Ｒｂ），Ｈ２（Ｒｂ），Ｈ３（Ｒｂ），…，ＨＮ（Ｒｂ）のうち、挑戦要請メッセージに含まれたハッシュ順序Ｉに該当するハッシュ値及び前記Ｉを含む挑戦応答メッセージ、すなわち｛Ｉ，ＨＮ−Ｉ（Ｒｂ）｝を含む挑戦応答メッセージを生成する。例えば、挑戦要請メッセージがＨＮ（Ｒａ）及びＩ＝０を含んでいる場合、挑戦応答メッセージ生成部４０５は、ＨＮ（Ｒｂ）及びＩ＝０を含む挑戦応答メッセージを生成する。
【００６１】
送受信部４０６は、準備応答メッセージ生成部４０３で生成された準備応答メッセージを伝送するか、挑戦応答メッセージ生成部４０５で生成された挑戦応答メッセージを伝送する。また、送受信部４０６は、ネットワークを経由してデバイスＡ  ３から準備要請メッセージまたは挑戦要請メッセージを受信する。
【００６２】
メッセージ判別部４０７は、送受信部４０６に受信されたメッセージが準備要請メッセージであるか、または挑戦要請メッセージであるかを判別する。
【００６３】
次いで、図４に図示されたデバイスＡ  ３の隣接性検査装置について説明する。
【００６４】
乱数生成部３０１は、一つの乱数Ｒを生成する。
【００６５】
暗号化部３０２は、乱数生成部３０１で生成された乱数Ｒ及びハッシュ回数２ＮをデバイスＢ  ４の公開キーＰｕｂＢで暗号化することによって、Ｅ（ＰｕｂＢ，｛２Ｎ，Ｒ｝）を生成する。一般的に、暗号化部３０２は、ＲＳＡのような公開キーアルゴリズムを使用して暗号化する。ハッシュ回数２Ｎは、ユーザにより決定されてもよく、デバイス設計者によりデバイスＡ  ３にデフォルト値として保存されてもよい。
【００６６】
準備要請メッセージ生成部３０３は、デバイスＡ  ３とデバイスＢ  ４との隣接性検査の準備を要請するために、暗号化部３０２により暗号化された乱数Ｒ及びハッシュ回数２Ｎを含む準備要請メッセージ、すなわちＥ（ＰｕｂＢ，｛２Ｎ，Ｒ｝）を含む準備要請メッセージを生成する。
【００６７】
ハッシュ部３０４は、乱数生成部３０１で生成された乱数Ｒを２Ｎ回数ほど連鎖的にハッシュすることで、乱数Ｒに対するハッシュ値を生成する。一般的に、ハッシュ部３０４は、ＳＨＡ−１のようなハッシュ関数を使用してハッシュする。さらに詳細に説明すれば、ハッシュ部３０４は、乱数ＲをハッシュすることでＨ（Ｒ）を生成し、次いで、Ｈ（Ｒ）をハッシュすることでＨ２（Ｒ）を生成する。ハッシュ部３０４は、このような過程を２Ｎ回数ほど反復することによってＨ（Ｒ），Ｈ２（Ｒ），Ｈ３（Ｒ），…，Ｈ２Ｎ（Ｒ）を生成する。
【００６８】
挑戦要請メッセージ生成部３０５は、デバイスＡ  ３とデバイスＢ  ４との隣接性検査の通過に挑戦するために、Ｎ回数内で順次にハッシュ部３０４で生成された乱数Ｒに対するハッシュ値Ｈ（Ｒ），Ｈ２（Ｒ），Ｈ３（Ｒ），…，Ｈ２Ｎ（Ｒ）の偶数番目のハッシュ値Ｈ２（Ｒ），Ｈ４（Ｒ），…，Ｈ２Ｎ（Ｒ）のうち、いずれか一つ及びハッシュ順序Ｉを含む挑戦要請メッセージ、すなわち｛Ｉ，Ｈ２Ｎ−２Ｉ（Ｒ）｝を含む挑戦要請メッセージを生成する。さらに詳細に説明すれば、挑戦要請メッセージ生成部３０５は、メッセージ判別部３１０での判別結果、送受信部３０９に受信されたメッセージが、デバイスＡ  ３とデバイスＢ  ４との隣接性検査の準備が完了したことを表す準備応答メッセージである場合、ハッシュ部３０４で生成された乱数Ｒに対するハッシュ値Ｈ（Ｒ），Ｈ２（Ｒ），Ｈ３（Ｒ），…，Ｈ２Ｎ（Ｒ）のうち、最後のハッシュ値Ｈ２Ｎ（Ｒ）及びハッシュ順序Ｉ＝０を含む最初の挑戦要請メッセージ、すなわち｛Ｉ，Ｈ２Ｎ（Ｒ）｝を含む最初の挑戦要請メッセージを生成する。
【００６９】
次いで、挑戦要請メッセージ生成部３０５は、隣接性決定部３０８から挑戦要請メッセージ生成を指示された場合、ハッシュ部３０４で生成された乱数Ｒに対するハッシュ値Ｈ（Ｒ），Ｈ２（Ｒ），Ｈ３（Ｒ），…，Ｈ２Ｎ（Ｒ）の偶数番目のハッシュ値Ｈ２（Ｒ），Ｈ４（Ｒ），…，Ｈ２Ｎ（Ｒ）のうち、最後のハッシュ値Ｈ２Ｎ（Ｒ）の次のハッシュ値Ｈ２Ｎ−２（Ｒ）及びハッシュ順序Ｉ＝１を含む最初の挑戦要請メッセージ、すなわち｛Ｉ、Ｈ２Ｎ−２（Ｒ）｝を含む最初の挑戦要請メッセージを生成する。このような方式で、挑戦要請メッセージ生成部３０５は、順次に｛Ｉ，Ｈ２Ｎ−２（Ｒ）｝，｛Ｉ，Ｈ２Ｎ−４（Ｒ）｝，…，｛Ｉ，Ｈ２（Ｒ）｝を含む挑戦要請メッセージを生成する。
【００７０】
ＲＴＴ測定部３０６は、送受信部３０９での挑戦要請メッセージ伝送時刻及び挑戦応答メッセージ受信時刻に基づいて、デバイスＡ  ３とデバイスＢ  ４との間のＲＴＴを選択的に測定する。さらに詳細に説明すれば、ＲＴＴ測定部３０６は、送受信部３０９での挑戦要請メッセージ伝送時刻を測定し、送受信部３０９での挑戦応答メッセージ受信時刻を測定する。また、ＲＴＴ測定部３０６は、このように測定された挑戦要請メッセージ伝送時刻と挑戦応答メッセージ受信時刻との差からＲＴＴを測定する。すなわち、挑戦応答メッセージ受信時刻から挑戦要請メッセージ伝送時刻を引いた値がＲＴＴになる。
【００７１】
ハッシュ値認証部３０７は、メッセージ判別部３１０での判別結果、送受信部３０９に受信されたメッセージが、送受信部３０９から伝送された挑戦要請メッセージに対する応答であって、｛Ｉ，Ｈ２Ｎ−１−２Ｉ（Ｒ）｝を含む挑戦応答メッセージである場合、挑戦応答メッセージに含まれたハッシュ値を認証する。さらに詳細に説明すれば、ハッシュ値認証部３０７は、挑戦応答メッセージに含まれたハッシュ値Ｈ２Ｎ−１−２Ｉ（Ｒ）と、ハッシュ部３０４で生成された乱数Ｒに対するハッシュ値Ｈ（Ｒ），Ｈ２（Ｒ），Ｈ３（Ｒ），…，Ｈ２Ｎ（Ｒ）の奇数番目のハッシュ値Ｈ（Ｒ），Ｈ３（Ｒ），…，Ｈ２Ｎ−１（Ｒ）のうち、挑戦応答メッセージに含まれたハッシュ順序Ｉに該当するハッシュ値Ｈ２Ｎ−１−２Ｉ（Ｒ）とを比較して、両者が一致すれば、挑戦応答メッセージに含まれたハッシュ値が真であると決定し、両者が一致しなければ、挑戦応答メッセージに含まれたハッシュ値が真でないと決定する。
【００７２】
隣接性決定部３０８は、ＲＴＴ測定部３０６でのＲＴＴ測定に基づいてハッシュ値認証部３０７での認証結果によって、デバイスＡ  ３とデバイスＢ  ４との隣接性如何を選択的に決定する。さらに詳細に説明すれば、隣接性決定部３０８は、ハッシュ値認証部３０７での認証結果、挑戦応答メッセージに含まれたハッシュ値が真であると決定された場合に、ＲＴＴ測定部３０６で測定されたＲＴＴと隣接性臨界値とを比較し、その結果、ＲＴＴ測定部３０６で測定されたＲＴＴが隣接性臨界値より小さければ、デバイスＡ  ３とデバイスＢ  ４とが互いに隣接したと決定する。また、隣接性決定部３０８は、ＲＴＴ測定部３０６で測定されたＲＴＴが隣接性臨界値より小さくなければ、デバイスＡ  ３とデバイスＢ  ４とが互いに隣接していないと決定し、Ｎ回数内で隣接性検査を通過するまで挑戦要請メッセージ生成部３０３に挑戦要請メッセージの生成を指示する。
【００７３】
送受信部３０９は、準備要請メッセージ生成部３０３で生成された準備要請メッセージを伝送するか、挑戦要請メッセージ生成部３０５で生成された挑戦要請メッセージを伝送する。また、送受信部３０９は、ネットワークを経由してデバイスＢ  ４から準備応答メッセージまたは挑戦応答メッセージを受信する。
【００７４】
メッセージ判別部３１０は、送受信部３０９に受信されたメッセージが準備応答メッセージであるか、または挑戦応答メッセージであるかを判別する。さらに詳細に説明すれば、メッセージ判別部３１０は、送受信部３０９に受信されたメッセージに含まれたメッセージタイプを参照して、準備応答メッセージであるか、または挑戦応答メッセージであるかを判別する。
【００７５】
最後に、図４に図示されたデバイスＢ  ４の隣接性検査支援装置について説明する。
【００７６】
復号化部４０１は、メッセージ判別部４０７での判別結果、送受信部４０６に受信されたメッセージが準備要請メッセージである場合、準備要請メッセージに含まれた暗号化された乱数Ｒ及びハッシュ回数２Ｎ、すなわちＥ（ＰｕｂＢ，｛２Ｎ，Ｒ｝）をデバイスＢ  ４の個人キーＰｒｉｖＢで復号化する。
【００７７】
ハッシュ部４０２は、復号化部４０１により復号化された乱数Ｒを復号化部４０１により復号化されたハッシュ回数２Ｎほど連鎖的にハッシュすることで、乱数Ｒに対するハッシュ値を生成する。
【００７８】
準備応答メッセージ生成部４０３は、ハッシュ部４０２でのハッシングが完了した場合、デバイスＡ  ３とデバイスＢ  ４との隣接性検査の準備が完了したことを表す準備応答メッセージを生成する。
【００７９】
ハッシュ値認証部４０４は、メッセージ判別部４０７での判別結果、送受信部４０６に受信されたメッセージが｛Ｉ，Ｈ２Ｎ−２Ｉ（Ｒ）｝を含む挑戦要請メッセージである場合、挑戦要請メッセージに含まれたハッシュ値を認証する。さらに詳細に説明すれば、ハッシュ値認証部４０４は、挑戦要請メッセージに含まれたハッシュ値Ｈ２Ｎ−２Ｉ（Ｒ）と、乱数Ｒに対するハッシュ値Ｈ（Ｒ），Ｈ２（Ｒ），Ｈ３（Ｒ），…，Ｈ２Ｎ（Ｒ）の偶数番目のハッシュ値Ｈ２（Ｒ），Ｈ４（Ｒ），…，Ｈ２Ｎ（Ｒ）のうち、挑戦要請メッセージに含まれたハッシュ順序Ｉに該当するハッシュ値Ｈ２Ｎ−２Ｉ（Ｒ）とを比較して、両者が一致すれば、挑戦要請メッセージに含まれたハッシュ値が真であると決定し、両者が一致しなければ、挑戦要請メッセージに含まれたハッシュ値が真でないと決定する。
【００８０】
挑戦応答メッセージ生成部４０５は、ハッシュ値認証部４０４での認証結果、挑戦要請メッセージに含まれたハッシュ値が真であると決定された場合に、乱数Ｒに対するハッシュ値Ｈ（Ｒ），Ｈ２（Ｒ），Ｈ３（Ｒ），…，Ｈ２Ｎ（Ｒ）の奇数番目のハッシュ値Ｈ（Ｒ），Ｈ３（Ｒ），…，Ｈ２Ｎ−１（Ｒ）のうち、挑戦要請メッセージに含まれたハッシュ順序Ｉに該当するハッシュ値及び前記Ｉを含む挑戦応答メッセージ、すなわち｛Ｉ，Ｈ２Ｎ−１−Ｉ（Ｒ）｝を含む挑戦応答メッセージを生成する。例えば、挑戦要請メッセージがＨ２Ｎ（Ｒ）及びＩ＝０を含んでいる場合、挑戦応答メッセージ生成部４０５は、Ｈ２Ｎ−１（Ｒｂ）及びＩ＝０を含む挑戦応答メッセージを生成する。
【００８１】
送受信部４０６は、準備応答メッセージ生成部４０３で生成された準備応答メッセージを伝送するか、挑戦応答メッセージ生成部４０５で生成された挑戦応答メッセージを伝送する。また、送受信部４０６は、ネットワークを経由してデバイスＡ  ３から準備要請メッセージまたは挑戦要請メッセージを受信する。
【００８２】
メッセージ判別部４０７は、送受信部４０６に受信されたメッセージが準備要請メッセージであるか、または挑戦要請メッセージであるかを判別する。
【００８３】
図６は、本発明の望ましい一実施形態による隣接性検査方法のフローチャートである。図６を参照するに、本実施形態による隣接性検査方法は、次のようなステップで構成される。本実施形態による隣接性検査方法は、図３及び図５に図示されたデバイスＡ  ３の隣接性検査装置で時系列的に処理されるステップで構成される。したがって、以下で省略された内容であっても、図３及び図５に図示されたデバイスＡ  ３の隣接性検査装置に関して以上で記述された内容は、本実施形態による隣接性検査方法にも適用される。
【００８４】
６１ステップでデバイスＡ  ３は、２つの乱数Ｒａ、Ｒｂを生成する。
【００８５】
６２ステップでデバイスＡ  ３は、６１ステップで生成された乱数Ｒａ、Ｒｂ及びハッシュ回数ＮをデバイスＢ  ４の公開キーＰｕｂＢで暗号化することによって、Ｅ（ＰｕｂＢ，［Ｎ，｛Ｒａ，Ｒｂ｝］）を生成する。
【００８６】
６３ステップでデバイスＡ  ３は、デバイスＡ  ３とデバイスＢ  ４との隣接性検査の準備を要請するために、６２ステップで暗号化された乱数Ｒａ、Ｒｂ及びハッシュ回数Ｎを含む準備要請メッセージ、すなわちＥ（ＰｕｂＢ，［Ｎ，｛Ｒａ，Ｒｂ｝］）を含む準備要請メッセージを生成し、この準備要請メッセージをデバイスＢ  ４に伝送する。
【００８７】
６４ステップでデバイスＡ  ３は、６２ステップで生成された乱数Ｒａ、ＲｂをＮ回数ほど連鎖的にハッシュすることで、乱数Ｒａに対するハッシュ値を生成し、乱数Ｒｂに対するハッシュ値を生成する。
【００８８】
６５ステップでデバイスＡ  ３は、６３ステップから伝送された準備要請メッセージに応答として、デバイスＡ  ３とデバイスＢ  ４との隣接性検査の準備が完了したことを表す準備応答メッセージを受信する。
【００８９】
６５ステップでデバイスＡ  ３が準備応答メッセージを受信した場合、６６ステップでデバイスＡ  ３は、デバイスＡ  ３とデバイスＢ  ４との隣接性検査の通過に挑戦するために、６４ステップで生成された乱数Ｒａに対するハッシュ値Ｈ（Ｒａ），Ｈ２（Ｒａ），Ｈ３（Ｒａ），…，ＨＮ（Ｒａ）のうち、ＨＮ（Ｒａ）及びハッシュ順序Ｉ＝０を含む挑戦要請メッセージ、すなわち｛０，ＨＮ（Ｒａ）｝を含む挑戦要請メッセージを生成し、この挑戦要請メッセージをデバイスＢ  ４に伝送する。また、６５ステップでデバイスＡ  ３は、これと同時に挑戦要請メッセージ伝送時刻を測定することによってデバイスＢ  ４に対するＲＴＴ測定を始める。
【００９０】
６７ステップでデバイスＡ  ３は、６６ステップから伝送された挑戦要請メッセージに対する応答として、｛０，ＨＮ（Ｒｂ）｝を含む挑戦応答メッセージを受信し、これと同時に挑戦応答メッセージの受信時刻を測定することによって、デバイスＢ  ４に対するＲＴＴ測定を終了する。すなわち、挑戦応答メッセージ受信時刻から挑戦要請メッセージ伝送時刻を引いた値がＲＴＴになる。
【００９１】
６８ステップでデバイスＡ  ３は、６７ステップで受信された挑戦応答メッセージに含まれたハッシュ値を認証する。さらに詳細に説明すれば、６７ステップでデバイスＡ  ３は、挑戦応答メッセージに含まれたハッシュ値ＨＮ（Ｒｂ）と、乱数Ｒｂに対するハッシュ値Ｈ（Ｒｂ），Ｈ２（Ｒｂ），Ｈ３（Ｒｂ），…，ＨＮ（Ｒｂ）のうち、挑戦応答メッセージに含まれたハッシュ順序Ｉ＝０に該当するハッシュ値ＨＮ（Ｒｂ）とを比較して、両者が一致すれば、挑戦応答メッセージに含まれたハッシュ値が真であると決定し、両者が一致しなければ、挑戦応答メッセージに含まれたハッシュ値が真でないと決定する。
【００９２】
６８ステップでデバイスＡ  ３は、６７ステップでの認証結果、挑戦応答メッセージに含まれたハッシュ値が真であると決定された場合に、６５ステップ及び６６ステップでのＲＴＴ測定に基づいてデバイスＡ  ３とデバイスＢ  ４との隣接性如何を決定する。さらに詳細に説明すれば、６８ステップでデバイスＡ  ３は、６５ステップ及び６６ステップで測定されたＲＴＴと隣接性臨界値とを比較し、その結果、６５ステップ及び６６ステップで測定されたＲＴＴが隣接性臨界値より小さければ、デバイスＡ  ３とデバイスＢ  ４とが互いに隣接していると決定し、デバイスＡ  ３とデバイスＢ  ４との隣接性検査が成功したと処理する。また、６８ステップでデバイスＡ  ３は、６５ステップ及び６６ステップで測定されたＲＴＴが隣接性臨界値より小さくなければ、デバイスＡ  ３とデバイスＢ  ４とが互いに隣接していないと決定する。
【００９３】
６７ステップでの認証結果、挑戦応答メッセージに含まれたハッシュ値が真でないと決定された場合、または６９ステップでデバイスＡ  ３とデバイスＢ  ４とが互いに隣接していないと決定された場合、６１０ステップでデバイスＡ  ３は、Ｉを１ずつ増加させる。
【００９４】
６１１ステップでデバイスＡ  ３は、６１０ステップで増加したＩとＮとを比較して、ＩがＮより小さな場合、６６ステップに戻り、ＩがＮより小さくない場合、デバイスＡ  ３とデバイスＢ  ４との隣接性検査が失敗したと処理する。
【００９５】
図７は、本発明の望ましい一実施形態による隣接性検査支援方法のフローチャートである。図７を参照するに、本実施形態による隣接性検査支援方法は、次のようなステップで構成される。本実施形態による隣接性検査支援方法は、図３及び図５に図示されたデバイスＢ  ４の隣接性検査支援装置で時系列的に処理されるステップで構成される。したがって、以下で省略された内容であっても、図３及び図５に図示されたデバイスＢ  ４の隣接性検査支援装置に関して以上で記述された内容は、本実施形態による隣接性検査支援方法にも適用される。
【００９６】
７１ステップでデバイスＢ  ４は、デバイスＡ  ３から暗号化された乱数Ｒａ、Ｒｂ及びハッシュ回数Ｎを含む準備要請メッセージ、すなわちＥ（ＰｕｂＢ，［Ｎ，｛Ｒａ，Ｒｂ｝］）を含む準備要請メッセージを受信する。
【００９７】
７２ステップでデバイスＢ  ４は、７１ステップで受信された準備要請メッセージに含まれた暗号化された乱数Ｒａ、Ｒｂ及びハッシュ回数Ｎ、すなわちＥ（ＰｕｂＢ，［Ｎ，｛Ｒａ，Ｒｂ｝］）を、デバイスＢ  ４の個人キーＰｒｉｖＢで復号化する。
【００９８】
７３ステップでデバイスＢ  ４は、７２ステップで復号化された乱数Ｒａ、Ｒｂを７２ステップで復号化されたハッシュ回数Ｎほど連鎖的にハッシュすることで、乱数Ｒａに対するハッシュ値を生成し、乱数Ｒｂに対するハッシュ値を生成する。
【００９９】
７４ステップでデバイスＢ  ４は、７３ステップでのハッシングが完了した場合、デバイスＡ  ３とデバイスＢ  ４との隣接性検査の準備が完了したことを表す準備応答メッセージを生成し、この準備応答メッセージをデバイスＡ  ３に伝送する。
【０１００】
７５ステップでデバイスＢ  ４は、７４ステップから伝送された準備応答メッセージを受信したデバイスＡ  ３から、｛０，ＨＮ（Ｒａ）｝を含む挑戦要請メッセージを受信する。
【０１０１】
７６ステップでデバイスＢ  ４は、７５ステップで受信された挑戦要請メッセージに含まれたハッシュ値を認証する。さらに詳細に説明すれば、７６ステップでデバイスＢ  ４は、挑戦要請メッセージに含まれたハッシュ値ＨＮ（Ｒａ）と、乱数Ｒａに対するハッシュ値Ｈ（Ｒａ），Ｈ２（Ｒａ），Ｈ３（Ｒａ），…，ＨＮ（Ｒａ）のうち、挑戦要請メッセージに含まれたハッシュ順序Ｉ＝０に該当するハッシュ値ＨＮ（Ｒａ）とを比較して、両者が一致すれば、挑戦要請メッセージに含まれたハッシュ値が真であると決定して、両者が一致しなければ、挑戦要請メッセージに含まれたハッシュ値が真でないと決定して、７５ステップに戻る。
【０１０２】
７７ステップでデバイスＢ  ４は、７６ステップでの認証結果、挑戦要請メッセージに含まれたハッシュ値が真であると決定された場合に、乱数Ｒｂに対するハッシュ値Ｈ（Ｒｂ），Ｈ２（Ｒｂ），Ｈ３（Ｒｂ），…，ＨＮ（Ｒｂ）のうち、挑戦要請メッセージに含まれたハッシュ順序Ｉ＝０に該当するハッシュ値及び前記Ｉ＝０を含む挑戦応答メッセージ、すなわち｛０，ＨＮ（Ｒｂ）｝を含む挑戦応答メッセージを生成し、この挑戦応答メッセージをデバイスＡ  ３に伝送し、７５ステップに戻る。
【０１０３】
図８は、本発明の望ましい一実施形態による隣接性検査方法のフローチャートである。図８を参照するに、本実施形態による隣接性検査方法は次のようなステップで構成される。本実施形態による隣接性検査方法は、図４及び図５に図示されたデバイスＡ  ３の隣接性検査装置で時系列的に処理されるステップで構成される。したがって、以下で省略された内容であっても、図４及び図５に図示されたデバイスＡ  ３の隣接性検査装置に関して以上で記述された内容は、本実施形態による隣接性検査方法にも適用される。
【０１０４】
８１ステップでデバイスＡ  ３は、一つの乱数Ｒを生成する。
【０１０５】
８２ステップでデバイスＡ  ３は、６１ステップで生成された乱数Ｒ及びハッシュ回数２ＮをデバイスＢ  ４の公開キーＰｕｂＢで暗号化することによって、Ｅ（ＰｕｂＢ，｛２Ｎ，Ｒ｝）を生成する。
【０１０６】
８３ステップでデバイスＡ  ３は、デバイスＡ  ３とデバイスＢ  ４との隣接性検査の準備を要請するために、８２ステップで暗号化された乱数Ｒ及びハッシュ回数２Ｎを含む準備要請メッセージ、すなわちＥ（ＰｕｂＢ，｛２Ｎ，Ｒ｝）を含む準備要請メッセージを生成し、この準備要請メッセージをデバイスＢ  ４に伝送する。
【０１０７】
８４ステップでデバイスＡ  ３は、８２ステップで生成された乱数Ｒを２Ｎ回数ほど連鎖的にハッシュすることで、乱数Ｒに対するハッシュ値を生成する。
【０１０８】
８５ステップでデバイスＡ  ３は、８３ステップから伝送された準備要請メッセージに応答として、デバイスＡ  ３とデバイスＢ  ４との隣接性検査の準備が完了したことを表す準備応答メッセージを受信する。
【０１０９】
８５ステップでデバイスＡ  ３が準備応答メッセージを受信した場合、８６ステップでデバイスＡ  ３は、デバイスＡ  ３とデバイスＢ  ４との隣接性検査の通過に挑戦するために、８４ステップで生成された乱数Ｒに対するハッシュ値Ｈ（Ｒ），Ｈ２（Ｒ），Ｈ３（Ｒ），…，Ｈ２Ｎ（Ｒ）の偶数番目のハッシュ値Ｈ２（Ｒ），Ｈ４（Ｒ），…，Ｈ２Ｎ（Ｒ）のうち、Ｈ２Ｎ（Ｒ）及びハッシュ順序Ｉ＝０を含む挑戦要請メッセージ、すなわち｛０，Ｈ２Ｎ（Ｒ）｝を含む挑戦要請メッセージを生成し、この挑戦要請メッセージをデバイスＢ  ４に伝送する。また、８５ステップでデバイスＡ  ３は、これと同時に挑戦要請メッセージ伝送時刻を測定することによってデバイスＢ  ４に対するＲＴＴ測定を始める。
【０１１０】
８７ステップでデバイスＡ  ３は、６６ステップで伝送された挑戦要請メッセージに対する応答として、｛０，Ｈ２Ｎ−１（Ｒ）｝を含む挑戦応答メッセージを受信し、これと同時に挑戦応答メッセージの受信時刻を測定することによってデバイスＢ  ４に対するＲＴＴ測定を終了する。すなわち、挑戦応答メッセージ受信時刻から挑戦要請メッセージ伝送時刻を引いた値がＲＴＴになる。
【０１１１】
８８ステップでデバイスＡ  ３は、８７ステップで受信された挑戦応答メッセージに含まれたハッシュ値を認証する。さらに詳細に説明すれば、８７ステップでデバイスＡ  ３は、挑戦応答メッセージに含まれたハッシュ値Ｈ２Ｎ−１（Ｒ）と、乱数Ｒに対するハッシュ値Ｈ（Ｒ），Ｈ２（Ｒ），Ｈ３（Ｒ），…，Ｈ２Ｎ（Ｒ）の奇数番目のハッシュ値Ｈ（Ｒ），Ｈ３（Ｒ），…，Ｈ２Ｎ−１（Ｒ）のうち、挑戦応答メッセージに含まれたハッシュ順序Ｉ＝０に該当するハッシュ値Ｈ２Ｎ−１（Ｒ）とを比較して、両者が一致すれば、挑戦応答メッセージに含まれたハッシュ値が真であると決定し、両者が一致しなければ、挑戦応答メッセージに含まれたハッシュ値が真でないと決定する。
【０１１２】
８８ステップでデバイスＡ  ３は、８７ステップでの認証結果、挑戦応答メッセージに含まれたハッシュ値が真であると決定された場合に、８５ステップ及び８６ステップでのＲＴＴ測定に基づいて、デバイスＡ  ３とデバイスＢ  ４との隣接性如何を決定する。さらに詳細に説明すれば、８８ステップでデバイスＡ  ３は、８５ステップ及び８６ステップで測定されたＲＴＴと隣接性臨界値とを比較し、その結果、８５ステップ及び８６ステップで測定されたＲＴＴが隣接性臨界値より小さければ、デバイスＡ  ３とデバイスＢ  ４とが互いに隣接していると決定し、デバイスＡ  ３とデバイスＢ  ４との隣接性検査が成功したと処理する。また、８８ステップでデバイスＡ  ３は、８５ステップ及び８６ステップで測定されたＲＴＴが隣接性臨界値より小さくなければ、デバイスＡ  ３とデバイスＢ  ４とが互いに隣接していないと決定する。
【０１１３】
８７ステップでの認証結果、挑戦応答メッセージに含まれたハッシュ値が真でないと決定された場合、または８９ステップでデバイスＡ  ３とデバイスＢ  ４とが互いに隣接していないと決定された場合、８１０ステップでデバイスＡ  ３は、Ｉを１ずつ増加させる。
【０１１４】
８１１ステップでデバイスＡ  ３は、８１０ステップで増加したＩとＮとを比較して、ＩがＮより小さな場合、８６ステップに戻り、ＩがＮより小さくない場合、デバイスＡ  ３とデバイスＢ  ４との隣接性検査が失敗したと処理する。次いで、図４に図示されたデバイスＡ  ３の隣接性検査装置について説明する。
【０１１５】
図９は、本発明の望ましい一実施形態による隣接性検査支援方法のフローチャートである。図９を参照するに、本実施形態による隣接性検査支援方法は、次のようなステップで構成される。本実施形態による隣接性検査支援方法は、図４及び図５に図示されたデバイスＢ  ４の隣接性検査支援装置で時系列的に処理されるステップで構成される。したがって、以下で省略された内容であっても、図４及び図５に図示されたデバイスＢ  ４の隣接性検査支援装置に関して以上で記述された内容は、本実施形態による隣接性検査支援方法にも適用される。
【０１１６】
９１ステップでデバイスＢ  ４は、デバイスＡ  ３から、暗号化された乱数Ｒ及びハッシュ回数２Ｎを含む準備要請メッセージ、すなわちＥ（ＰｕｂＢ，｛２Ｎ，Ｒ｝）を含む準備要請メッセージを受信する。
【０１１７】
９２ステップでデバイスＢ  ４は、９１ステップで受信された準備要請メッセージに含まれた暗号化された乱数Ｒ及びハッシュ回数２Ｎ、すなわちＥ（ＰｕｂＢ，｛２Ｎ，Ｒ｝）をデバイスＢ  ４の個人キーＰｒｉｖＢで復号化する。
【０１１８】
９３ステップでデバイスＢ  ４は、９２ステップで復号化された乱数Ｒを９２ステップで復号化されたハッシュ回数２Ｎほど連鎖的にハッシュすることで、乱数Ｒに対するハッシュ値を生成する。
【０１１９】
９４ステップでデバイスＢ  ４は、９３ステップでのハッシングが完了した場合、デバイスＡ  ３とデバイスＢ  ４との隣接性検査の準備が完了したことを表す準備応答メッセージを生成して、この準備応答メッセージをデバイスＡ  ３に伝送する。
【０１２０】
９５ステップでデバイスＢ  ４は、９４ステップで伝送された準備応答メッセージを受信したデバイスＡ  ３から、｛０，Ｈ２Ｎ（Ｒ）｝を含む挑戦要請メッセージを受信する。
【０１２１】
９６ステップでデバイスＢ  ４は、９５ステップで受信された挑戦要請メッセージに含まれたハッシュ値を認証する。さらに詳細に説明すれば、デバイスＢ  ４は、挑戦要請メッセージに含まれたハッシュ値Ｈ２Ｎ（Ｒ）と、乱数Ｒに対するハッシュ値Ｈ（Ｒ），Ｈ２（Ｒ），Ｈ３（Ｒ），…，Ｈ２Ｎ（Ｒ）の偶数番目のハッシュ値Ｈ２（Ｒ），Ｈ４（Ｒ），…，Ｈ２Ｎ（Ｒ）のうち、挑戦要請メッセージに含まれたハッシュ順序Ｉ＝０に該当するハッシュ値Ｈ２Ｎ（Ｒ）とを比較して、両者が一致すれば、挑戦要請メッセージに含まれたハッシュ値が真であると決定し、両者が一致しなければ、挑戦要請メッセージに含まれたハッシュ値が真でないと決定して、９５ステップに戻る。
【０１２２】
９７ステップでデバイスＢ  ４は、９６ステップでの認証結果、挑戦要請メッセージに含まれたハッシュ値が真であると決定された場合に、乱数Ｒに対するハッシュ値Ｈ（Ｒ），Ｈ２（Ｒ），Ｈ３（Ｒ），…，Ｈ２Ｎ（Ｒ）の奇数番目のハッシュ値Ｈ（Ｒ），Ｈ３（Ｒ），…，Ｈ２Ｎ−１（Ｒ）のうち、挑戦要請メッセージに含まれたハッシュ順序Ｉ＝０に該当するハッシュ値Ｈ２Ｎ−１（Ｒ）及びＩ＝０を含む挑戦応答メッセージ、すなわち｛０，Ｈ２Ｎ−１（Ｒ）｝を含む挑戦応答メッセージを生成し、この挑戦応答メッセージをデバイスＡ  ３に伝送して、９５ステップに戻る。
【０１２３】
一方、前述した本発明の実施形態はコンピュータで実行できるプログラムで作成可能であり、コンピュータで読み取り可能な記録媒体を利用して前記プログラムを動作させる汎用デジタルコンピュータで具現できる。また、前述した本発明の実施形態で使われたデータの構造は、コンピュータで読み取り可能な記録媒体にいろいろな手段を通じて記録できる。
【０１２４】
前記コンピュータで読み取り可能な記録媒体は、ＲＯＭ（Ｒｅａｄ−Ｏｎｌｙ  Ｍｅｍｏｒｙ）、ＲＡＭ（Ｒａｎｄｏｍ−Ａｃｃｅｓｓ  Ｍｅｍｏｒｙ）、ＣＤ−ＲＯＭ、磁気テープ、フロッピー（登録商標）ディスク及びキャリアウェーブのような記録媒体を含む。
【０１２５】
これまで本発明についてその望ましい実施形態を中心に説明した。当業者ならば本発明が本発明の本質的な特性から逸脱しない範囲で変形された形態で具現できるということが理解できるであろう。したがって、開示された実施形態は限定的な観点ではなく説明的な観点で考慮されねばならない。本発明の範囲は、前述した説明ではなく特許請求の範囲に現れており、それと同等な範囲内にあるあらゆる差異点は本発明に含まれていると解釈されねばならない。
【図面の簡単な説明】
【０１２６】
【図１】一般的な隣接性検査が適用される通信環境を示す図である。
【図２】従来の隣接性検査プロトコルを示す図である。
【図３】本発明の望ましい一実施形態による隣接性検査プロトコルを示す図である。
【図４】本発明の望ましい他の実施形態による隣接性検査プロトコルを示す図である。
【図５】本発明の望ましい一実施形態による隣接性検査システムの構成図である。
【図６】本発明の望ましい一実施形態による隣接性検査方法のフローチャートである。
【図７】本発明の望ましい一実施形態による隣接性検査支援方法のフローチャートである。
【図８】本発明の望ましい一実施形態による隣接性検査方法のフローチャートである。
【図９】本発明の望ましい一実施形態による隣接性検査支援方法のフローチャートである。
【図１】
2008539648.tif 000003
【図２】
2008539648.tif 000004
【図３】
2008539648.tif 000005
【図４】
2008539648.tif 000006
【図５】
2008539648.tif 000007
【図６】
2008539648.tif 000008
【図７】
2008539648.tif 000009
【図８】
2008539648.tif 000010
【図９】
2008539648.tif 000011
【国際調査報告】
2008539648.tif 000012
2008539648.tif 000013