(57)【特許請求の範囲】
【請求項１】
第１の端末と第２の端末とが共通鍵を共有する鍵交換システムであって、
前記第１の端末及び前記第２の端末には、予め重複しない自然数からなる固有署名鍵と、当該固有署名鍵及びＧＤＨ（ＧＡＰ−Ｄｉｆｆｉｅ−Ｈｅｌｌｍａｎ）グループに属する公開された要素に基づいて生成される固有検証鍵と、がそれぞれ割り当てられており、
前記第１の端末は、
前記ＧＤＨグループから一の要素を選択する選択部と、
前記一の要素に対して前記第１の端末の固有署名鍵により演算を行い、署名情報を生成する署名生成部と、
前記第１の端末の固有検証鍵及び前記署名情報を、前記第２の端末へ送信する第１の送信部と、
前記第２の端末から、前記第２の端末の固有検証鍵を受信する第１の受信部と、
前記一の要素、前記第２の端末の固有検証鍵及び前記第１の端末の固有署名鍵に基づいて、前記共通鍵を生成する第１の鍵生成部と、を備え、
前記第２の端末は、
前記第１の端末から、前記第１の端末の固有検証鍵及び前記署名情報を受信する第２の受信部と、
前記第２の端末の固有検証鍵を、前記第１の端末へ送信する第２の送信部と、
前記署名情報、前記第１の端末の固有検証鍵及び前記第２の端末の固有署名鍵に基づいて、前記共通鍵を生成する第２の鍵生成部と、を備える鍵交換システム。
【請求項２】
前記第１の端末は、
前記第１の送信部により、さらに前記一の要素を、前記第２の端末へ送信し、
前記第２の端末は、
前記第２の受信部により、前記第１の端末から、さらに前記一の要素を受信し、
前記公開された要素及び前記署名情報に基づく所定の演算結果と、前記第１の端末の固有検証鍵及び前記一の要素に基づく前記所定の演算結果と、が等しいことを確かめ、前記署名情報の正当性を検証する検証部をさらに備え、
前記第２の送信部は、前記検証部により前記署名情報の正当性が検証された場合に、前記第２の端末の固有検証鍵を、前記第１の端末へ送信する請求項１に記載の鍵交換システム。
【請求項３】
前記選択部は、前記一の要素を、前記ＧＤＨグループからランダムに選択する請求項１又は請求項２に記載の鍵交換システム。
【請求項４】
前記選択部は、数値データを前記ＧＤＨグループの要素に写像変換する一方向性ハッシュ関数演算により、乱数データから前記一の要素を求める請求項３に記載の鍵交換システム。
【請求項５】
前記選択部は、数値データを固定長の数値データに写像変換する一方向性ハッシュ関数演算により乱数データから算出された数値、及び前記ＧＤＨグループの要素に基づいて、前記一の要素を求める請求項３に記載の鍵交換システム。
【請求項６】
第１の端末と第２の端末とが共通鍵を共有する鍵交換方法であって、
前記第１の端末及び前記第２の端末には、予め重複しない自然数からなる固有署名鍵と、当該固有署名鍵及びＧＤＨ（ＧＡＰ−Ｄｉｆｆｉｅ−Ｈｅｌｌｍａｎ）グループに属する公開された要素に基づいて生成される固有検証鍵と、がそれぞれ割り当てられており、
前記第１の端末は、
前記ＧＤＨグループから一の要素を選択する選択ステップと、
前記一の要素に対して前記第１の端末の固有署名鍵により演算を行い、署名情報を生成する署名生成ステップと、
前記第１の端末の固有検証鍵及び前記署名情報を、前記第２の端末へ送信する第１の送信ステップと、
前記第２の端末から、前記第２の端末の固有検証鍵を受信する第１の受信ステップと、
前記一の要素、前記第２の端末の固有検証鍵及び前記第１の端末の固有署名鍵に基づいて、前記共通鍵を生成する第１の鍵生成ステップと、を実行し、
前記第２の端末は、
前記第１の端末から、前記第１の端末の固有検証鍵及び前記署名情報を受信する第２の受信ステップと、
前記第２の端末の固有検証鍵を、前記第１の端末へ送信する第２の送信ステップと、
前記署名情報、前記第１の端末の固有検証鍵及び前記第２の端末の固有署名鍵に基づいて、前記共通鍵を生成する第２の鍵生成ステップと、を実行する鍵交換方法。
【請求項７】
第１の端末と第２の端末とに共通鍵を共有させる鍵交換プログラムであって、
前記第１の端末及び前記第２の端末には、予め重複しない自然数からなる固有署名鍵と、当該固有署名鍵及びＧＤＨ（ＧＡＰ−Ｄｉｆｆｉｅ−Ｈｅｌｌｍａｎ）グループに属する公開された要素に基づいて生成される固有検証鍵と、がそれぞれ割り当てられており、
前記第１の端末に、
前記ＧＤＨグループから一の要素を選択する選択ステップと、
前記一の要素に対して前記第１の端末の固有署名鍵により演算を行い、署名情報を生成する署名生成ステップと、
前記第１の端末の固有検証鍵及び前記署名情報を、前記第２の端末へ送信する第１の送信ステップと、
前記第２の端末から、前記第２の端末の固有検証鍵を受信する第１の受信ステップと、
前記一の要素、前記第２の端末の固有検証鍵及び前記第１の端末の固有署名鍵に基づいて、前記共通鍵を生成する第１の鍵生成ステップと、を実行させ、
前記第２の端末に、
前記第１の端末から、前記第１の端末の固有検証鍵及び前記署名情報を受信する第２の受信ステップと、
前記第２の端末の固有検証鍵を、前記第１の端末へ送信する第２の送信ステップと、
前記署名情報、前記第１の端末の固有検証鍵及び前記第２の端末の固有署名鍵に基づいて、前記共通鍵を生成する第２の鍵生成ステップと、を実行させる鍵交換プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、共通鍵暗号における鍵を共有するための鍵交換システム、鍵交換方法及び鍵交換プログラムに関する。
【背景技術】
【０００２】
従来、通信装置（端末）の間で秘密情報の通信を安全に行うために、暗号通信が用いられている。暗号の方式には、共通鍵暗号方式と公開鍵暗号方式とがある。共通鍵暗号方式は、暗号通信を行う端末の間で共通の鍵を用いる方式であり、例えばＡＥＳ（Ａｄｖａｎｃｅｄ  Ｅｎｃｒｙｐｔｉｏｎ  Ｓｔａｎｄａｒｄ）が知られている。また、公開鍵暗号方式は、秘密鍵と公開鍵との２つの鍵を用いる方式で、例えばＲＳＡ（Ｒｉｖｅｓｔ  Ｓｈａｍｉｒ  Ａｄｌｅｍａｎ）暗号が知られている。
【０００３】
ところで、公開鍵暗号方式は、暗号化のために端末間で鍵交換をする必要がないという利点がある。しかし、公開鍵暗号方式は、共通鍵暗号方式と比較して処理速度が遅い、あるいは負荷が重いという性能面での難点があるため、公開鍵暗号方式だけで全ての通信の暗号化を行うのは効率的ではない。
【０００４】
一方、共通鍵暗号化方式では、暗号通信を行う端末間で共通鍵を共有することが必要である。原始的には、第三者による傍受の困難な方法として、共通鍵は、それぞれの端末の管理者が対面して交換されたり、通信回線とは別の郵送等のルートを用いて交換されたりしていた。しかし、こうした原始的な共通鍵の交換方法は、非効率であり、ネットワーク通信を実現する上では実用的ではなかった。
【０００５】
そこで、通信回線を介して共通鍵を配送する様々な手法が提案されている。例えば、Ｄｉｆｆｉｅ−Ｈｅｌｌｍａｎの鍵共有方式（非特許文献１参照）や、その応用例（特許文献１参照）が提案されている。
【先行技術文献】
【特許文献】
【０００６】
【特許文献１】特開２０００−２７８２５８号公報
【特許文献２】特開２００６−１４０７４３号公報
【非特許文献】
【０００７】
【非特許文献１】Ｗ．Ｄｉｆｆｉｅ  ａｎｄ  Ｍ．Ｅ．Ｈｅｌｌｍａｎ，  “Ｎｅｗ  Ｄｉｒｅｃｔｉｏｎｓ  ｉｎ  Ｃｒｙｐｔｏｇｒａｐｈｙ，”  ＩＥＥＥ  Ｔｒａｎｓ．  ｏｎ  Ｉｎｆｏｒｍａｔｉｏｎ  Ｔｈｅｏｒｙ，  Ｖｏｌ．２２，  Ｎｏ．６，  ｐｐ．６４４−６５４，  １９７６
【非特許文献２】Ｈ．Ｋｒａｗｃｚｙｋ，  “ＨＭＱＶ：  Ａ  Ｈｉｇｈ−Ｐｅｒｆｏｒｍａｎｃｅ  Ｓｅｃｕｒｅ  Ｄｉｆｆｉｅ−Ｈｅｌｌｍａｎ  Ｐｒｏｔｏｃｏｌ，”  Ａｄｖａｎｃｅｓ  ｉｎ  Ｃｒｙｐｔｏｌｏｇｙ−ＣＲＹＰＴＯ  ２００５，  Ｓｐｒｉｎｇｅｒ−Ｖｅｒｌａｇ，  ＬＮＣＳ  ３６２１，  ｐｐ．５４６−５６６，  ２００５
【発明の概要】
【発明が解決しようとする課題】
【０００８】
前述のＤｉｆｆｉｅ−Ｈｅｌｌｍａｎ鍵共有は、通信回線を使用して安全に鍵交換できる方式であるが、鍵交換を行うために共有する乱数値に対して保証がないため、通信に介在して中間者攻撃を受ける可能性がある。つまり、共通鍵の交換のために、ある端末から別の端末へ公開鍵等の情報を送信する際、伝送路上の第三者がこの情報を取得し、偽造情報にすり替えて送信することで鍵交換に割り込み、共通鍵を不正に取得することができる。したがって、第三者により暗号通信の内容が盗聴又は改竄される問題があった。
【０００９】
そこで、この中間者攻撃を防止するために、電子署名や認証機能を用いて相互認証を行い、共有する乱数値が真正であることを確認する認証鍵交換（ＡＫＥ：Ａｕｔｈｅｔｉｃａｔｅｄ  Ｋｅｙ  Ｅｘｃｈａｎｇｅ）という方法もある（例えば、非特許文献２及び特許文献２参照）。
【００１０】
しかしながら、ＡＫＥは、相互認証を行うために、通信量や通信回数が増大し、さらに、鍵を生成するまでの演算負荷が重くなるという課題があった。
【００１１】
本発明は、通信回数及び演算回数を低減した認証鍵交換が行える鍵交換システム、鍵交換方法及び鍵交換プログラムを提供することを目的とする。
【課題を解決するための手段】
【００１２】
本発明では、以下のような解決手段を提供する。
【００１３】
（１）第１の端末と第２の端末とが共通鍵を共有する鍵交換システムであって、前記第１の端末及び前記第２の端末には、予め重複しない自然数からなる固有署名鍵と、当該固有署名鍵及びＧＤＨ（ＧＡＰ−Ｄｉｆｆｉｅ−Ｈｅｌｌｍａｎ）グループに属する公開された要素に基づいて生成される固有検証鍵と、がそれぞれ割り当てられており、前記第１の端末は、前記ＧＤＨグループから一の要素を選択する選択部と、前記一の要素に対して前記第１の端末の固有署名鍵により演算を行い、署名情報を生成する署名生成部と、前記第１の端末の固有検証鍵及び前記署名情報を、前記第２の端末へ送信する第１の送信部と、前記第２の端末から、前記第２の端末の固有検証鍵を受信する第１の受信部と、前記一の要素、前記第２の端末の固有検証鍵及び前記第１の端末の固有署名鍵に基づいて、前記共通鍵を生成する第１の鍵生成部と、を備え、前記第２の端末は、前記第１の端末から、前記第１の端末の固有検証鍵及び前記署名情報を受信する第２の受信部と、前記第２の端末の固有検証鍵を、前記第１の端末へ送信する第２の送信部と、前記署名情報、前記第１の端末の固有検証鍵及び前記第２の端末の固有署名鍵に基づいて、前記共通鍵を生成する第２の鍵生成部と、を備える鍵交換システム。
【００１４】
このような構成によれば、当該鍵交換システムは、各端末において、発行証明書付きの相手端末の正規の固有検証鍵と、各端末以外が取得することは困難な固有署名鍵とを用いて共通鍵を生成する。第１の端末から第２の端末へ、及び第２の端末から第１の端末への２回の通信回数により、共通鍵の生成に必要な情報は取得され、各端末それぞれで１回の演算により共通鍵が生成される。したがって、当該鍵交換システムは、固有検証鍵による認証を可能としつつ、通信回数及び演算回数を低減した認証鍵交換を行える。
【００１５】
（２）前記第１の端末は、前記第１の送信部により、さらに前記一の要素を、前記第２の端末へ送信し、前記第２の端末は、前記第２の受信部により、前記第１の端末から、さらに前記一の要素を受信し、前記公開された要素及び前記署名情報に基づく所定の演算結果と、前記第１の端末の固有検証鍵及び前記一の要素に基づく前記所定の演算結果と、が等しいことを確かめ、前記署名情報の正当性を検証する検証部をさらに備え、前記第２の送信部は、前記検証部により前記署名情報の正当性が検証された場合に、前記第２の端末の固有検証鍵を、前記第１の端末へ送信する（１）に記載の鍵交換システム。
【００１６】
このような構成によれば、当該鍵交換システムは、ＧＤＨグループから選択された一の要素をさらに第２の端末へ送信することにより、第２の端末において、共通鍵の生成に用いられる署名情報の正当性を検証することができる。このとき、正当性の検証のためには、所定の演算が２回実行されるのみである。したがって、当該鍵交換システムは、相互認証を可能としつつも、演算回数を低減することができる。
【００１７】
（３）前記選択部は、前記一の要素を、前記ＧＤＨグループからランダムに選択する（１）又は（２）に記載の鍵交換システム。
【００１８】
このような構成によれば、当該鍵交換システムは、一の要素をＧＤＨグループからランダムに選択するので、共通鍵の生成に利用されるデータが第三者により取得される可能性を低減することができる。
【００１９】
（４）前記選択部は、数値データを前記ＧＤＨグループの要素に写像変換する一方向性ハッシュ関数演算により、乱数データから前記一の要素を求める（３）に記載の鍵交換システム。
【００２０】
このような構成によれば、当該鍵交換システムは、数値データをＧＤＨグループの要素に写像変換する一方向性ハッシュ関数演算により一の要素を求める。したがって、当該鍵交換システムは、ＧＤＨグループに属するランダムな要素を、乱数データから容易に算出することができる。
【００２１】
（５）前記選択部は、数値データを固定長の数値データに写像変換する一方向性ハッシュ関数演算により乱数データから算出された数値、及び前記ＧＤＨグループの要素に基づいて、前記一の要素を求める（３）に記載の鍵交換システム。
【００２２】
このような構成によれば、当該鍵交換システムは、数値データを対象とする簡易な一方向性ハッシュ関数演算を用いて、ＧＤＨグループに属するランダムな要素を、乱数データから容易に算出することができる。
【００２３】
（６）第１の端末と第２の端末とが共通鍵を共有する鍵交換方法であって、前記第１の端末及び前記第２の端末には、予め重複しない自然数からなる固有署名鍵と、当該固有署名鍵及びＧＤＨ（ＧＡＰ−Ｄｉｆｆｉｅ−Ｈｅｌｌｍａｎ）グループに属する公開された要素に基づいて生成される固有検証鍵と、がそれぞれ割り当てられており、前記第１の端末は、前記ＧＤＨグループから一の要素を選択する選択ステップと、前記一の要素に対して前記第１の端末の固有署名鍵により演算を行い、署名情報を生成する署名生成ステップと、前記第１の端末の固有検証鍵及び前記署名情報を、前記第２の端末へ送信する第１の送信ステップと、前記第２の端末から、前記第２の端末の固有検証鍵を受信する第１の受信ステップと、前記一の要素、前記第２の端末の固有検証鍵及び前記第１の端末の固有署名鍵に基づいて、前記共通鍵を生成する第１の鍵生成ステップと、を実行し、前記第２の端末は、前記第１の端末から、前記第１の端末の固有検証鍵及び前記署名情報を受信する第２の受信ステップと、前記第２の端末の固有検証鍵を、前記第１の端末へ送信する第２の送信ステップと、前記署名情報、前記第１の端末の固有検証鍵及び前記第２の端末の固有署名鍵に基づいて、前記共通鍵を生成する第２の鍵生成ステップと、を実行する鍵交換方法。
【００２４】
このような構成によれば、当該鍵交換方法を第１の端末と第２の端末とが実行することにより、（１）と同様の効果が期待できる。
【００２５】
（７）第１の端末と第２の端末とに共通鍵を共有させる鍵交換プログラムであって、前記第１の端末及び前記第２の端末には、予め重複しない自然数からなる固有署名鍵と、当該固有署名鍵及びＧＤＨ（ＧＡＰ−Ｄｉｆｆｉｅ−Ｈｅｌｌｍａｎ）グループに属する公開された要素に基づいて生成される固有検証鍵と、がそれぞれ割り当てられており、前記第１の端末に、前記ＧＤＨグループから一の要素を選択する選択ステップと、前記一の要素に対して前記第１の端末の固有署名鍵により演算を行い、署名情報を生成する署名生成ステップと、前記第１の端末の固有検証鍵及び前記署名情報を、前記第２の端末へ送信する第１の送信ステップと、前記第２の端末から、前記第２の端末の固有検証鍵を受信する第１の受信ステップと、前記一の要素、前記第２の端末の固有検証鍵及び前記第１の端末の固有署名鍵に基づいて、前記共通鍵を生成する第１の鍵生成ステップと、を実行させ、前記第２の端末に、前記第１の端末から、前記第１の端末の固有検証鍵及び前記署名情報を受信する第２の受信ステップと、前記第２の端末の固有検証鍵を、前記第１の端末へ送信する第２の送信ステップと、前記署名情報、前記第１の端末の固有検証鍵及び前記第２の端末の固有署名鍵に基づいて、前記共通鍵を生成する第２の鍵生成ステップと、を実行させる鍵交換プログラム。
【００２６】
このような構成によれば、当該鍵交換プログラムを第１の端末と第２の端末とに実行させることにより、（１）と同様の効果が期待できる。
【発明の効果】
【００２７】
本発明によれば、通信回数及び演算回数を低減した認証鍵交換を行うことができる。
【図面の簡単な説明】
【００２８】
【図１】本発明の実施形態に係る鍵交換システムの機能構成を示すブロック図である。
【図２】本発明の実施形態に係る鍵交換システムにおける鍵交換方法を示す概要図である。
【図３】本発明の実施形態に係る鍵交換システムにおける鍵交換方法の処理手順を示すフローチャートである。
【発明を実施するための形態】
【００２９】
以下、本発明の実施形態の一例について説明する。本実施形態に係る鍵交換システムは、所定の通信及び演算により、２つの端末間で相互認証をしつつ、共通鍵を共有する。
【００３０】
ところで、各端末には、予め重複しない固有署名鍵と固有検証鍵が認証局（ＣＡ）によってそれぞれ割り当てられている。固有署名鍵は、所定の自然数（ｘ）からなり、固有検証鍵は、ＧＤＨ（ＧＡＰ−Ｄｉｆｆｉｅ−Ｈｅｌｌｍａｎ）グループ（Ｇ）の要素である楕円曲線上の点（ｇ）と固有署名鍵（ｘ）とに基づいて生成される楕円曲線上の点（ｖ＝ｘｇ）からなることが好ましい。このように構成されることにより、固有署名鍵（ｘ）を知らない第三者が「ｖ」や「ｇ」の値から固有署名鍵（ｘ）を求めることは計算量的に困難となる。
【００３１】
ここで、本実施形態で採用される具体的な署名方式について説明する。鍵交換システムでは、基本となる署名方式としてＧＡＰ−Ｄｉｆｆｉｅ−Ｈｅｌｌｍａｎ（ＧＤＨ）署名を採用する。ＧＤＨ署名とは、Ｄｅｃｉｓｉｏｎ−Ｄｉｆｆｉｅ−Ｈｅｌｌｍａｎ（ＤＤＨ）問題をペアリングと呼ばれるある種のブラックボックス関数ｅ（Ｐ，Ｑ）を用いることで、解くことが可能であることを利用した署名である。
【００３２】
次に、ペアリング演算を用いたＧＤＨ署名について説明する。楕円曲線上のＤｉｆｆｉｅ−Ｈｅｌｌｍａｎ問題に関連して、ＧＤＨグループが定義されている。ＧＤＨグループについて簡単に説明する。Ｇをある楕円曲線上の点の集合とする。「ｇ」を集合Ｇの要素としたとき、集合Ｇにおける楕円曲線上のＤｅｃｉｓｉｏｎａｌ  Ｄｉｆｆｉｅ−Ｈｅｌｌｍａｎ（ＤＤＨ）問題とＣｏｍｐｕｔａｔｉｏｎａｌ  Ｄｉｆｆｉｅ−Ｈｅｌｌｍａｎ（ＣＤＨ）問題が以下のように定義される。
【００３３】
ＤＤＨ問題：あるａ、ｂ、ｃ∈Ｚｐ＊（ｐ未満の自然数）があり、ｇ、ａｇ、ｂｇ、ｃｇが与えられた時、ｃ＝ａｂかどうかを判定する問題。
ＣＤＨ問題：あるａ、ｂ、ｃ∈Ｚｐ＊があり、ｇ、ａｇ、ｂｇが与えられた時、ａｂｇを計算する問題。
【００３４】
このとき、ＤＤＨ問題は、計算量的に簡単であるが、ＣＤＨ問題は、計算量的に難問である場合、この集合ＧをＧＤＨグループと定義する。
【００３５】
これに対し、ある楕円曲線上の点をＰ，Ｑとし、そのＰ，Ｑによっては、次にあげる性質を持つことができるペアリングと呼ばれるブラックボックス関数ｅ（Ｐ，Ｑ）を定義できるものが存在する。
ｅ（Ｐ，Ｑ１＋Ｑ２）＝ｅ（Ｐ，Ｑ１）ｅ（Ｐ，Ｑ２）  ・・・（１）
ｅ（Ｐ１＋Ｐ２，Ｑ）＝ｅ（Ｐ１，Ｑ）ｅ（Ｐ２，Ｑ）  ・・・（２）
ｅ（ａＰ，ｂＱ）＝ｅ（ｂＰ，ａＱ）＝ｅ（ａｂＰ，Ｑ）＝ｅ（Ｐ，ａｂＱ）＝ｅ（Ｐ，Ｑ）ａｂ  ・・・（３）
【００３６】
よって、ｇがペアリング演算の可能な楕円曲線上の点である場合には、上記の性質から、（３）式にｇ、ａｇ、ｂｇ、ｃｇを入力すると、
ｅ（ａｇ，ｂｇ）＝ｅ（ｇ，ｇ）ａｂ  ・・・（４）
ｅ（ｇ，ｃｇ）＝ｅ（ｇ，ｇ）ｃ  ・・・（５）
となり、両者の値が一致するかどうかにより、「ａｂ＝ｃ」であるかどうかを判定でき、ｇはＧＤＨグループＧの要素となりうる。
【００３７】
この性質を利用してＧＤＨ署名が構成される。集合Ｇは、ＧＤＨグループであり、ｇは集合Ｇの要素となる点とする。また、一方向性ハッシュ関数Ｈを、通常使用される任意のビット長のサイズの数値データが固定のビット長のサイズの数値データに写像変換される方式とは異なり、
Ｈ：｛０，１｝＊→Ｇ
のように、任意のビット長のサイズの数値データを、楕円曲線上の点として表現されるＧＤＨグループＧの要素に写像変換する方式であると定義する。
【００３８】
このとき、ＧＤＨ署名は以下のように定義される。
鍵生成：自然数ｘ∈Ｚｐ＊を選び、ｇからｖ＝ｘｇを計算する。ｘを署名鍵、楕円曲線上の点ｖを検証鍵とする。
署名：署名者は、メッセージ「ｍ∈｛０，１｝＊」に対しｈ＝Ｈ（ｍ）を計算し、さらに自分の署名鍵を用いてσ＝ｘｈを計算する。σをｍに対する署名として公開する。
検証：検証者は、メッセージｍからｈ＝Ｈ（ｍ）を計算し、ｇ、ｖ、ｈ、σを準備する。ｅ（ｇ，σ）とｅ（ｖ，ｈ）を計算し、両者の値が一致したら、署名σは、正しい署名と判定する。
【００３９】
このとき、ｈの値は集合Ｇの要素となるので、あるｙ∈Ｚｐ＊を用いてｈ＝ｙｇと表現できる。その結果、正しく署名が行われていれば（ｇ，ｖ，ｈ，σ）＝（ｇ，ｘｇ，ｙｇ，ｘｙｇ）となる。したがって、正当な署名であれば、上記の検証でのペアリング演算は、ｅ（ｇ，σ）＝ｅ（ｇ，ｘｙｇ）＝ｅ（ｇ，ｇ）ｘｙ＝ｅ（ｘｇ，ｙｇ）＝ｅ（ｖ，ｈ）となり、値が一致することから、検証可能となる。なお、ＧＤＨグループの条件であるＣＤＨ問題の困難性から、署名鍵ｘを知らない第三者がｇ、ｖ、ｈの値から署名σを導出することは不可能である。
【００４０】
図１は、本実施形態に係る鍵交換システム１の機能構成を示すブロック図である。端末１０（第１の端末）と端末２０（第２の端末）とは、ネットワークを介して接続されている。なお、本実施形態では、端末１０から通信を開始することとして説明するが、端末２０から開始してもよい。この場合、端末１０と端末２０とが備える構成（各部）が逆となる。
【００４１】
端末１０は、制御部１１と、記憶部１２と、入力部１３と、表示部１４と、通信部１５とを備える。また、端末２０も同様に、制御部２１と、記憶部２２と、入力部２３と、表示部２４と、通信部２５とを備える。
【００４２】
制御部１１は、端末１０の全体を、制御部２１は、端末２０の全体を制御する部分であり、それぞれ、記憶部１２又は記憶部２２に記憶された各種プログラムを適宜読み出して実行することにより、前述のハードウェアと協働し、本実施形態における各種機能を実現している。制御部１１及び制御部２１は、ＣＰＵ（Ｃｅｎｔｒａｌ  Ｐｒｏｃｅｓｓｉｎｇ  Ｕｎｉｔ）であってよい。なお、制御部１１及び制御部２１が備える各部の機能は後述する。
【００４３】
記憶部１２及び記憶部２２は、ハードウェア群を端末１０又は端末２０として機能させるための各種プログラム、及び各種データ等の記憶領域であり、ハードディスク（ＨＤＤ）であってよい。具体的には、記憶部１２及び記憶部２２には、本実施形態の各種機能を制御部１１及び制御部２１に実行させるプログラムと、公的認証局により発行された固有署名鍵及び固有検証鍵とが記憶される。
【００４４】
なお、固有署名鍵及び固有検証鍵の生成元である、ＧＤＨグループ（楕円曲線）Ｇの要素ｇが与えられており、端末１０については、ｘ１∈Ｚｐ＊を固有署名鍵、ｘ１ｇを固有検証鍵とする。また、端末２０については、ｘ２∈Ｚｐ＊を固有署名鍵、ｘ２ｇを固有検証鍵とする。それぞれの固有検証鍵には、公的認証局による発行証明書が付いており、ｇと固有検証鍵（ｖ１＝ｘ１ｇ及びｖ２＝ｘ２ｇ）とは公開されている。
【００４５】
入力部１３及び入力部２３は、端末１０又は端末２０に対するユーザからの指示入力を受け付けるインタフェース装置である。入力部１３及び入力部２３は、例えば、キーボード、マウス及びタッチパネル等により構成される。
【００４６】
表示部１４及び表示部２４は、ユーザにデータの入力を受け付ける画面を表示したり、端末１０又は端末２０による処理結果の画面を表示したりするものである。表示部１４及び表示部２４は、ブラウン管表示装置（ＣＲＴ）や液晶表示装置（ＬＣＤ）等のディスプレイ装置であってよい。
【００４７】
通信部１５及び通信部２５は、ネットワークを介して外部装置と通信を行うネットワーク・アダプタである。通信部１５と通信部２５とは、端末１０と端末２０との間の通信を確立し、互いに各種データの送受信を行う。具体的には、本実施形態では、共通鍵の生成及び相互認証に用いられるデータが送受信される。
【００４８】
端末１０の制御部１１は、選択部１１１と、署名生成部１１２と、送信部１１３（第１の送信部）と、受信部１１４（第１の受信部）と、鍵生成部１１５（第１の鍵生成部）とを備える。また、端末２０の制御部２１は、受信部２１１（第２の受信部）と、検証部２１２と、送信部２１３（第２の送信部）と、鍵生成部２１４（第２の鍵生成部）とを備える。
【００４９】
選択部１１１は、ＧＤＨグループ（楕円曲線）Ｇから、一の要素（点）ｈをランダムに選択する。
【００５０】
署名生成部１１２は、選択部１１１により選択されたｈに対して端末１０の固有署名鍵（ｘ１）により演算を行い、署名情報（ｘ１ｈ）を生成する。
【００５１】
送信部１１３は、端末１０の発行証明書付き固有検証鍵（ｖ１）、一の要素（ｈ）及び署名情報（ｘ１ｈ）を、通信部１５を介して端末２０へ送信する。
【００５２】
受信部１１４は、端末２０から、通信部１５を介して端末２０の発行証明書付き固有検証鍵（ｖ２）を受信する。
【００５３】
鍵生成部１１５は、一の要素（ｈ）、端末２０の固有検証鍵（ｖ２）及び端末１０の固有署名鍵に基づいて、（６）式又は（７）式により、共通鍵（Ｋｅｙ）を生成する。
【数１】
0005414558.tif 000002
【００５４】
受信部２１１は、端末１０から、端末１０の発行証明書付き固有検証鍵（ｖ１）、一の要素（ｈ）及び署名情報（ｘ１ｈ）を、通信部２５を介して受信する。
【００５５】
検証部２１２は、公開されている要素（ｇ）及び署名情報（ｘ１ｈ）に基づくペアリング演算「ｅ（ｇ，ｘ１ｈ）」の結果と、端末１０の固有検証鍵（ｖ１）及び一の要素（ｈ）に基づくペアリング演算「ｅ（ｖ１，ｈ）」の結果とが等しいことを確かめ、署名情報（ｘ１ｈ）の正当性を検証する。
【００５６】
送信部２１３は、検証部２１２により署名情報（ｘ１ｈ）の正当性が検証された場合に、鍵交換の手続きを継続するため、端末２０の発行証明書付き固有検証鍵（ｖ２）を、通信部２５を介して端末１０へ送信する。
【００５７】
鍵生成部２１４は、署名情報（ｘ１ｈ）、端末１０の固有検証鍵（ｖ１）及び端末２０の固有署名鍵に基づいて、（８）式により、共通鍵（Ｋｅｙ）を生成する。
【数２】
0005414558.tif 000003
【００５８】
ここで、「ｖ１＝ｘ１ｇ」、「ｖ２＝ｘ２ｇ」であることを用いると、式（６）〜（８）は、いずれも、
【数３】
0005414558.tif 000004
と変形できるので、端末１０の鍵生成部１１５により生成された共通鍵と、端末２０の鍵生成部２１４により生成された共通鍵とは同一の値となる。
【００５９】
図２は、本実施形態に係る鍵交換システム１における鍵交換方法を示す概要図である。
端末１０は、固有署名鍵（ｘ１）と固有検証鍵（ｖ１＝ｘ１ｇ）とを記憶している。また、端末２０は、固有署名鍵（ｘ２）と固有検証鍵（ｖ２＝ｘ２ｇ）とを記憶している。
【００６０】
端末１０においてランダムに選択された一の要素（ｈ）により、署名情報（ｘ１ｈ）が生成されると、端末１０から端末２０へ、固有検証鍵（ｖ１）、一の要素（ｈ）及び署名情報（ｘ１ｈ）が送信される。
【００６１】
端末２０は、ペアリング演算により「ｅ（ｇ，ｘ１ｈ）」と「ｅ（ｖ１，ｈ）」とが等しいことを確認する。そして、両者が一致した場合に、端末２０から端末１０へ、固有検証鍵（ｖ２）が送信される。
【００６２】
端末１０及び端末２０では、それぞれが前述のように、ペアリング演算により共通鍵を生成し、端末間で共有する。
【００６３】
図３は、本実施形態に係る鍵交換システム１における鍵交換方法の処理手順を示すフローチャートである。本処理は、記憶部１２及び記憶部２２に記憶されているプログラムが、それぞれ制御部１１及び制御部２１により実行されることにより行われる。
【００６４】
ステップＳ１（選択ステップ）では、制御部１１（選択部１１１）は、ＧＤＨグループから一の要素（ｈ）を選択する。
【００６５】
ステップＳ２（署名生成ステップ）では、制御部１１（署名生成部１１２）は、自身の固有署名鍵（ｘ１）とステップＳ１で選択された一の要素（ｈ）とに基づいて、署名情報（ｘ１ｈ）を生成する。
【００６６】
ステップＳ３（第１の送信ステップ）では、制御部１１（送信部１１３）は、固有検証鍵（ｖ１）、一の要素（ｈ）、及びステップＳ２で生成された署名情報（ｘ１ｈ）を、端末２０へ送信する。
【００６７】
ステップＳ４（第２の受信ステップ）では、制御部２１（受信部２１１）は、ステップＳ３で送信された固有検証鍵（ｖ１）、一の要素（ｈ）及び署名情報（ｘ１ｈ）を受信する。
【００６８】
ステップＳ５では、制御部２１（検証部２１２）は、ペアリング演算を用いて、ステップＳ４で受信した署名情報（ｘ１ｈ）の正当性を検証する。
【００６９】
ステップＳ６では、制御部２１は、ステップＳ５で検証された署名情報（ｘ１ｈ）が正当なものであるか否かを判定する。制御部２１は、この判定がＹＥＳの場合は、処理をステップＳ７に移し、判定がＮＯの場合は、処理を終了して鍵交換を中止する。
【００７０】
ステップＳ７（第２の送信ステップ）では、制御部２１（送信部２１３）は、署名情報（ｘ１ｈ）が正当であることが確認されたので、自身の固有検証鍵（ｖ２）を端末１０へ送信する。
【００７１】
ステップＳ８（第１の受信ステップ）では、制御部１１（受信部１１４）は、ステップＳ７で送信された固有検証鍵（ｖ２）を受信する。
【００７２】
ステップＳ９（第１の鍵生成ステップ）では、制御部１１（鍵生成部１１５）は、一の要素（ｈ）又は署名情報（ｘ１ｈ）、端末２０の固有検証鍵（ｖ２）、及び端末１０の固有署名鍵（ｘ１）を用いた前述のペアリング演算により、共通鍵を生成する。
【００７３】
ステップＳ１０（第２の鍵生成ステップ）では、制御部２１（鍵生成部２１４）は、署名情報（ｘ１ｈ）、端末１０の固有検証鍵（ｖ１）、及び端末２０の固有署名鍵（ｘ２）を用いた前述のペアリング演算により、共通鍵を生成する。
【００７４】
以上のように、本実施形態によれば、鍵生成部１１５及び鍵生成部２１４は、それぞれの発行証明書付きの公開された固有検証鍵を用いて共通鍵の生成を行っているため、端末１０と端末２０との相互認証が可能となる。したがって、鍵交換システム１は、中間者攻撃を排除することができる。
【００７５】
さらに、鍵交換システム１では、端末間の１往復（２回）の通信のみで共通鍵が共有され、また、公開情報の他に必要な情報は、ランダムな要素ｈと、このｈに対する署名情報ｘ１ｈのみであり、情報量が少ない。また、演算回数は、端末２０では署名検証時及び鍵生成時の３回のペアリング演算、端末１０では鍵生成時の１回のペアリング演算であるため、従来の認証鍵交換に比べて演算回数が少ない。したがって、本実施形態によれば、相互認証を可能としつつ、通信、メモリ及び演算の負荷を低減した認証鍵交換を行える。
【００７６】
以上、本発明の実施形態について説明したが、本発明は前述した実施形態に限るものではない。また、本実施形態に記載された効果は、本発明から生じる最も好適な効果を列挙したに過ぎず、本発明による効果は、本実施形態に記載されたものに限定されるものではない。
【００７７】
前述の実施形態では、選択部１１１は、一の要素（ｈ）をＧＤＨグループから直接求めたが、これには限られない。例えば、選択部１１１は、数値データをＧＤＨグループの要素に写像変換する一方向性ハッシュ関数（Ｈ：｛０，１｝＊→Ｇ）の演算により、乱数データ（ｒ∈Ｚｐ＊）から一の要素（ｈ＝Ｈ（ｒ））を求めてもよい。
【００７８】
また、例えば、選択部１１１は、数値データを固定長の数値データに写像変換する一方向性ハッシュ関数（Ｈ´：｛０，１｝＊→｛０，１｝ｌ）の演算により乱数データ（ｒ）から算出された数値、及びＧＤＨグループの要素（ｇ´）に基づいて、一の要素（ｈ＝Ｈ´（ｒ）ｇ´）を求めてもよい。ここで、ｌは、ハッシュ値のサイズを示し、例えばＳＨＡ−１なら１６０である。なお、乱数データ（ｒ）が第三者に取得されると、要素（ｇ´）が求められ、一の要素（ｈ）が書き換えられるおそれがあるため、乱数データ（ｒ）は公開されない。
【００７９】
このように一方向性ハッシュ関数を用いることにより、選択部１１１は、ＧＤＨグループに属するランダムな要素（ｈ）を、乱数データから容易に算出することができる。
【符号の説明】
【００８０】
１  鍵交換システム
１０  端末（第１の端末）
２０  端末（第２の端末）
１１１  選択部
１１２  署名生成部
１１３  送信部（第１の送信部）
１１４  受信部（第１の受信部）
１１５  鍵生成部（第１の鍵生成部）
２１１  受信部（第２の受信部）
２１２  検証部
２１３  送信部（第２の送信部）
２１４  鍵生成部（第２の鍵生成部）
【図１】
0005414558.tif 000005
【図２】
0005414558.tif 000006
【図３】
0005414558.tif 000007