鍵交換システム、鍵交換方法及び鍵交換プログラム
【課題】４者間で容易に鍵交換が行える鍵交換システム、鍵交換方法及び鍵交換プログラムを提供すること。
【解決手段】鍵交換システム１において、各端末１０は、自然数からなる秘密情報を選択する秘密情報選択部１１１と、ＧＤＨグループに属する公開要素に対して秘密情報により演算を行い、１次公開情報を生成する１次公開情報生成部１１２と、生成された１次公開情報を他の端末へ送信する１次公開情報送信部１１３と、１次公開情報を受信する１次公開情報受信部１１４と、受信された１次公開情報に対して秘密情報により演算を行い、２次公開情報を生成する２次公開情報生成部１１５と、生成された２次公開情報を他の端末へ送信する２次公開情報送信部１１６と、２次公開情報を受信する２次公開情報受信部１１７と、生成された又は受信された２次公開情報及び秘密情報に基づいて、共通鍵を生成する共通鍵生成部１１８と、を備える。
【解決手段】鍵交換システム１において、各端末１０は、自然数からなる秘密情報を選択する秘密情報選択部１１１と、ＧＤＨグループに属する公開要素に対して秘密情報により演算を行い、１次公開情報を生成する１次公開情報生成部１１２と、生成された１次公開情報を他の端末へ送信する１次公開情報送信部１１３と、１次公開情報を受信する１次公開情報受信部１１４と、受信された１次公開情報に対して秘密情報により演算を行い、２次公開情報を生成する２次公開情報生成部１１５と、生成された２次公開情報を他の端末へ送信する２次公開情報送信部１１６と、２次公開情報を受信する２次公開情報受信部１１７と、生成された又は受信された２次公開情報及び秘密情報に基づいて、共通鍵を生成する共通鍵生成部１１８と、を備える。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、共通鍵暗号における鍵を共有するための鍵交換システム、鍵交換方法及び鍵交換プログラムに関する。
【背景技術】
【０００２】
従来、通信装置（端末）の間で秘密情報の通信を安全に行うために、暗号通信が用いられている。暗号の方式には、共通鍵暗号方式と公開鍵暗号方式とがある。共通鍵暗号方式は、暗号通信を行う端末の間で共通の鍵を用いる方式であり、例えばＡＥＳ（Ａｄｖａｎｃｅｄ Ｅｎｃｒｙｐｔｉｏｎ Ｓｔａｎｄａｒｄ）が知られている。また、公開鍵暗号方式は、秘密鍵と公開鍵との２つの鍵を用いる方式で、例えばＲＳＡ（Ｒｉｖｅｓｔ Ｓｈａｍｉｒ Ａｄｌｅｍａｎ）暗号が知られている。
【０００３】
ところで、公開鍵暗号方式は、暗号化のために端末間で鍵交換をする必要がないという利点がある。しかし、公開鍵暗号方式は、共通鍵暗号方式と比較して処理速度が遅い、あるいは負荷が重いという性能面での難点があるため、公開鍵暗号方式だけで全ての通信の暗号化を行うのは効率的ではない。
【０００４】
一方、共通鍵暗号化方式では、暗号通信を行う端末間で共通鍵を共有することが必要である。原始的には、第三者による傍受の困難な方法として、共通鍵は、それぞれの端末の管理者が対面して交換されたり、通信回線とは別の郵送等のルートを用いて交換されたりしていた。しかし、こうした原始的な共通鍵の交換方法は、非効率であり、ネットワーク通信を実現する上では実用的ではなかった。
【０００５】
そこで、通信回線を介して共通鍵を配送する様々な手法が提案されている。例えば、Ｄｉｆｆｉｅ−Ｈｅｌｌｍａｎの鍵共有方式（非特許文献１参照）や、その応用例（特許文献１参照）が提案されている。
【先行技術文献】
【特許文献】
【０００６】
【特許文献１】特開２０００−２７８２５８号公報
【非特許文献】
【０００７】
【非特許文献１】Ｗ．Ｄｉｆｆｉｅ ａｎｄ Ｍ．Ｅ．Ｈｅｌｌｍａｎ， “Ｎｅｗ Ｄｉｒｅｃｔｉｏｎｓ ｉｎ Ｃｒｙｐｔｏｇｒａｐｈｙ，” ＩＥＥＥ Ｔｒａｎｓ． ｏｎ Ｉｎｆｏｒｍａｔｉｏｎ Ｔｈｅｏｒｙ， Ｖｏｌ．２２， Ｎｏ．６， ｐｐ．６４４−６５４， １９７６
【非特許文献２】Ａ．Ｊｏｕｘ， “Ａ Ｏｎｅ Ｒｏｕｎｄ Ｐｒｏｔｏｃｏｌ ｆｏｒ Ｔｒｉｐａｒｔｉｔｅ Ｄｉｆｆｉｅ−Ｈｅｌｌｍａｎ，” Ｐｒｏｃ． ｏｆ Ａｌｇｏｒｉｔｈｍｉｃ Ｎｕｍｂｅｒ Ｔｈｅｏｒｙ Ｓｙｍｐｏｓｉｕｍ ＩＶ， Ｓｐｒｉｎｇｅｒ−Ｖｅｒｌａｇ， ＬＮＣＳ １８３８， ｐｐ．３８５−３９３， ２０００
【発明の概要】
【発明が解決しようとする課題】
【０００８】
前述のＤｉｆｆｉｅ−Ｈｅｌｌｍａｎ鍵共有方式は、通信回線を使用して安全に鍵交換できる方式であるが、２者間のみで鍵を共有することしかできない。したがって、多人数で同一の共通鍵を共有する必要がある場合には、この鍵共有方式を複数の組み合わせに対して行い、さらに実際の鍵情報を共有する複雑な手順が必要となるため、通信の負荷が増大していた。さらに、この場合、複数の組み合わせにおける共有情報を管理する装置（サーバ）が必要となることもあり、システム構築の金銭的コストが増大していた。
【０００９】
そこで、ペアリングと呼ばれる関数を用いることで、３者間で鍵共有を行う方式が提案されている（例えば、非特許文献２参照）。しかしながら、４者間以上での鍵交換は、複数の方式を組み合わせずには実現できなかった。
【００１０】
本発明は、４者間で容易に鍵交換が行える鍵交換システム、鍵交換方法及び鍵交換プログラムを提供することを目的とする。
【課題を解決するための手段】
【００１１】
本発明では、以下のような解決手段を提供する。
【００１２】
（１）４つの端末が共通鍵を共有する鍵交換システムであって、各端末は、自然数からなる秘密情報を選択する選択部と、ＧＤＨ（ＧＡＰ−Ｄｉｆｆｉｅ−Ｈｅｌｌｍａｎ）グループに属する公開要素に対して、前記秘密情報により演算を行い、第１の公開情報を生成する第１の公開情報生成部と、前記第１の公開情報生成部により生成された前記第１の公開情報を、他の端末へ送信する第１の送信部と、前記他の端末から送信された前記第１の公開情報を受信する第１の受信部と、前記第１の受信部により受信された前記第１の公開情報に対して、前記秘密情報により演算を行い、第２の公開情報を生成する第２の公開情報生成部と、前記第２の公開情報生成部により生成された前記第２の公開情報を、他の端末へ送信する第２の送信部と、前記他の端末から送信された前記第２の公開情報を受信する第２の受信部と、前記第２の公開情報生成部により生成された又は前記第２の受信部により受信された前記第２の公開情報、及び前記秘密情報に基づいて、前記共通鍵を生成する鍵生成部と、を備える鍵交換システム。
【００１３】
このような構成によれば、当該鍵交換システムにおいて、各端末は、ＧＤＨグループに属する公開要素、及び自然数からなる秘密情報により、第１の公開情報及び第２の公開情報を生成して送信することにより公開する。したがって、当該鍵交換システムは、秘密情報を求めることが困難な情報のみを公開するので、各端末が選択した秘密情報の秘匿性が保たれる。
【００１４】
そして、各端末は、第２の公開情報及び秘密情報により共通鍵を生成する。したがって、当該鍵交換システムは、複数の鍵交換方式を組み合わせることなく、同一の共通鍵を４者間で容易に共有することができる。
【００１５】
（２）前記第１の公開情報生成部は、前記公開要素に対して、前記秘密情報からなる１次の値を乗じて、前記第１の公開情報を生成し、前記第２の公開情報生成部は、前記第１の公開情報に対して、前記秘密情報からなる１次の値を乗じて、前記第２の公開情報を生成し、前記鍵生成部は、双線形のペアリング関数に対して、前記４つの端末の秘密情報からなる５次の値をべき乗した値を前記共通鍵として生成する（１）に記載の鍵交換システム。
【００１６】
このような構成によれば、当該鍵交換システムは、公開情報として、秘密情報が１次の値、及び２次の値を公開する。そして、これらの公開情報をどのような組み合わせでペアリング関数に入力しても、秘密情報の高々４次までの値しか求められないのに対して、当該鍵交換システムは、秘密情報が５次の値を用いた共通鍵を生成する。したがって、いずれの秘密情報も知らない第三者が、公開情報のみから共通鍵を算出することはできないため、鍵交換の安全性が向上する。
【００１７】
（３）前記各端末において生成又は受信される前記第２の公開情報が重複しないように、前記第１の送信部の送信先、及び前記第２の送信部の送信先が予め設定されている（１）又は（２）に記載の鍵交換システム。
【００１８】
このような構成によれば、当該鍵交換システムは、公開情報の重複を回避するので、公開情報の演算回数及び通信回数が減少し、処理負荷を低減できる。
【００１９】
（４）前記各端末において生成又は受信される前記第２の公開情報は、自端末の秘密情報を用いずに演算された３種類、及び自端末の秘密情報を用いて演算された１種類である（３）に記載の鍵交換システム。
【００２０】
このような構成によれば、当該鍵交換システムは、冗長な公開情報の演算及び通信を抑制するので、さらに演算回数及び通信回数が減少し、処理負荷を低減できる。
【００２１】
（５）４つの端末が共通鍵を共有する鍵交換方法であって、各端末は、自然数からなる秘密情報を選択する選択ステップと、ＧＤＨ（ＧＡＰ−Ｄｉｆｆｉｅ−Ｈｅｌｌｍａｎ）グループに属する公開要素に対して、前記秘密情報により演算を行い、第１の公開情報を生成する第１の公開情報生成ステップと、前記第１の公開情報生成ステップにおいて生成された前記第１の公開情報を、他の端末へ送信する第１の送信ステップと、前記他の端末から送信された前記第１の公開情報を受信する第１の受信ステップと、前記第１の受信ステップにおいて受信された前記第１の公開情報に対して、前記秘密情報により演算を行い、第２の公開情報を生成する第２の公開情報生成ステップと、前記第２の公開情報生成ステップにおいて生成された前記第２の公開情報を、他の端末へ送信する第２の送信ステップと、前記他の端末から送信された前記第２の公開情報を受信する第２の受信ステップと、前記第２の公開情報生成ステップにおいて生成された又は前記第２の受信ステップにおいて受信された前記第２の公開情報、及び前記秘密情報に基づいて、前記共通鍵を生成する鍵生成ステップと、を実行する鍵交換方法。
【００２２】
このような構成によれば、当該鍵交換方法を各端末が実行することにより、（１）と同様の効果が期待できる。
【００２３】
（６）４つの端末に共通鍵を共有させる鍵交換プログラムであって、各端末に、自然数からなる秘密情報を選択する選択ステップと、ＧＤＨ（ＧＡＰ−Ｄｉｆｆｉｅ−Ｈｅｌｌｍａｎ）グループに属する公開要素に対して、前記秘密情報により演算を行い、第１の公開情報を生成する第１の公開情報生成ステップと、前記第１の公開情報生成ステップにおいて生成された前記第１の公開情報を、他の端末へ送信する第１の送信ステップと、前記他の端末から送信された前記第１の公開情報を受信する第１の受信ステップと、前記第１の受信ステップにおいて受信された前記第１の公開情報に対して、前記秘密情報により演算を行い、第２の公開情報を生成する第２の公開情報生成ステップと、前記第２の公開情報生成ステップにおいて生成された前記第２の公開情報を、他の端末へ送信する第２の送信ステップと、前記他の端末から送信された前記第２の公開情報を受信する第２の受信ステップと、前記第２の公開情報生成ステップにおいて生成された又は前記第２の受信ステップにおいて受信された前記第２の公開情報、及び前記秘密情報に基づいて、前記共通鍵を生成する鍵生成ステップと、を実行させる鍵交換プログラム。
【００２４】
このような構成によれば、当該鍵交換プログラムを各端末に実行させることにより、（１）と同様の効果が期待できる。
【発明の効果】
【００２５】
本発明によれば、４者間で容易に鍵交換が行える。
【図面の簡単な説明】
【００２６】
【図１】本発明の実施形態に係る鍵交換システムの機能構成を示すブロック図である。
【図２】本発明の実施形態に係る鍵交換方法を示す概要図である。
【図３】本発明の実施形態に係る公開情報の送受信パターンの一例を示す図である。
【図４】本発明の実施形態に係る端末の処理手順を示すフローチャートである。
【発明を実施するための形態】
【００２７】
以下、本発明の実施形態の一例について説明する。本実施形態に係る鍵交換システム１は、所定の通信及び演算により、４つの端末１０（１０Ａ、１０Ｂ、１０Ｃ及び１０Ｄ）間で共通鍵を共有する。
【００２８】
まず、本実施形態の鍵交換システムで用いるペアリング関数について説明する。
Ｇをある楕円曲線上の点の集合とする。ｇを集合Ｇの要素としたとき、集合Ｇにおける楕円曲線上のＤｅｃｉｓｉｏｎａｌ Ｄｉｆｆｉｅ−Ｈｅｌｌｍａｎ（ＤＤＨ）問題とＣｏｍｐｕｔａｔｉｏｎａｌ Ｄｉｆｆｉｅ−Ｈｅｌｌｍａｎ（ＣＤＨ）問題が以下のように定義される。
【００２９】
ＤＤＨ問題：あるａ、ｂ、ｃ∈Ｚｐ＊（ｐ未満の自然数）があり、ｇ、ａｇ、ｂｇ、ｃｇが与えられた時、ｃ＝ａｂかどうかを判定する問題。
ＣＤＨ問題：あるａ、ｂ、ｃ∈Ｚｐ＊があり、ｇ、ａｇ、ｂｇが与えられた時、ａｂｇを計算する問題。
【００３０】
このとき、ＤＤＨ問題は、計算量的に簡単であるが、ＣＤＨ問題は、計算量的に難問である場合、この集合ＧをＧＤＨ（ＧＡＰ−Ｄｉｆｆｉｅ−Ｈｅｌｌｍａｎ）グループと定義する。
【００３１】
これに対し、ある楕円曲線上の点をＰ，Ｑとし、そのＰ，Ｑによっては、次にあげる双線形と呼ばれる性質を持つことができる、ペアリング関数と呼ばれるブラックボックス関数ｅ（Ｐ，Ｑ）を定義できるものが存在する。
ｅ（Ｐ，Ｑ１＋Ｑ２）＝ｅ（Ｐ，Ｑ１）ｅ（Ｐ，Ｑ２） ・・・（１）
ｅ（Ｐ１＋Ｐ２，Ｑ）＝ｅ（Ｐ１，Ｑ）ｅ（Ｐ２，Ｑ） ・・・（２）
ｅ（ａＰ，ｂＱ）＝ｅ（ｂＰ，ａＱ）＝ｅ（ａｂＰ，Ｑ）＝ｅ（Ｐ，ａｂＱ）＝ｅ（Ｐ，Ｑ）ａｂ ・・・（３）
【００３２】
図１は、本実施形態に係る鍵交換システム１の機能構成を示すブロック図である。
４つの端末１０（１０Ａ、１０Ｂ、１０Ｃ及び１０Ｄ）は、ネットワークを介して接続されている。そして、端末１０は、それぞれ、制御部１１と、記憶部１２と、入力部１３と、表示部１４と、通信部１５とを備える。
【００３３】
制御部１１は、端末１０の全体を制御する部分であり、記憶部１２に記憶された各種プログラムを適宜読み出して実行することにより、前述のハードウェアと協働し、本実施形態における各種機能を実現している。制御部１１は、ＣＰＵ（Ｃｅｎｔｒａｌ Ｐｒｏｃｅｓｓｉｎｇ Ｕｎｉｔ）であってよい。なお、制御部１１が備える各部の機能は後述する。
【００３４】
記憶部１２は、ハードウェア群を端末１０として機能させるための各種プログラム、及び各種データ等の記憶領域であり、ハードディスク（ＨＤＤ）であってよい。具体的には、記憶部１２には、本実施形態の各種機能を制御部１１に実行させるプログラムと、端末固有の秘密情報及び各種公開情報とが記憶される。
【００３５】
入力部１３は、端末１０に対するユーザからの指示入力を受け付けるインタフェース装置である。入力部１３は、例えば、キーボード、マウス及びタッチパネル等により構成される。
【００３６】
表示部１４は、ユーザにデータの入力を受け付ける画面を表示したり、端末１０による処理結果の画面を表示したりするものである。表示部１４は、ブラウン管表示装置（ＣＲＴ）や液晶表示装置（ＬＣＤ）等のディスプレイ装置であってよい。
【００３７】
通信部１５は、ネットワークを介して外部装置と通信を行うネットワーク・アダプタである。通信部１５は、４つの端末間での相互の通信を確立し、互いに各種データの送受信を行う。具体的には、本実施形態では、共通鍵の生成に用いられる各種公開情報が送受信される。
【００３８】
次に、端末１０の制御部１１の機能を詳述する。
各端末１０には、共通して、予め公開要素として、ペアリングの演算が可能な楕円曲線上の点Ｇが与えられている。以下、４つの端末１０のうち、代表して端末１０Ａを説明する。
【００３９】
制御部１１は、秘密情報選択部１１１（選択部）と、１次公開情報生成部１１２（第１の公開情報生成部）と、１次公開情報送信部１１３（第１の送信部）と、１次公開情報受信部１１４（第１の受信部）と、２次公開情報生成部１１５（第２の公開情報生成部）と、２次公開情報送信部１１６（第２の送信部）と、２次公開情報受信部１１７（第２の受信部）と、共通鍵生成部１１８（鍵生成部）とを備える。
【００４０】
秘密情報選択部１１１は、自然数からなる端末１０Ａに固有の秘密情報（ａ∈Ｚｐ＊）をランダムに選択する。なお、端末１０Ｂは秘密情報ｂを、端末１０Ｃは秘密情報ｃを、端末１０Ｄは秘密情報ｄを選択する。
【００４１】
１次公開情報生成部１１２は、ＧＤＨグループに属する公開要素（Ｇ）に対して、自身の秘密情報（ａ）により演算（ａ倍）を行い、１次公開情報（ａＧ；第１の公開情報）を生成する。
【００４２】
１次公開情報送信部１１３は、１次公開情報生成部１１２により生成された１次公開情報（ａＧ）を公開する。具体的には、１次公開情報送信部１１３は、１次公開情報（ａＧ）を、通信部１５を介して、他の端末１０Ｂ、１０Ｃ又は１０Ｄへ送信する。
【００４３】
なお、公開された１次公開情報（ａＧ）から秘密情報（ａ）を求めることは、楕円曲線上の離散対数問題により困難なため、秘密情報の秘匿性が保たれる。
【００４４】
１次公開情報受信部１１４は、他の端末１０Ｂ、１０Ｃ又は１０Ｄの１次公開情報送信部１１３から送信された１次公開情報（ｂＧ、ｃＧ又はｄＧ）を、通信部１５を介して受信する。
【００４５】
２次公開情報生成部１１５は、１次公開情報受信部１１４により受信された１次公開情報（ｂＧ、ｃＧ又はｄＧ）に対して、自身の秘密情報（ａ）により演算（ａ倍）を行い、２次公開情報（ａｂＧ、ａｃＧ又はａｄＧ；第２の公開情報）を生成する。
【００４６】
２次公開情報送信部１１６は、２次公開情報生成部１１５により生成された２次公開情報（ｂＧ、ｃＧ又はｄＧ）を公開する。具体的には、２次公開情報送信部１１６は、２次公開情報（ｂＧ、ｃＧ又はｄＧ）を、通信部１５を介して、他の端末１０Ｂ、１０Ｃ又は１０Ｄへ送信する。
【００４７】
なお、公開された１次公開情報（ａＧ）及び２次公開情報（ａｂＧ、ａｃＧ又はａｄＧ）から秘密情報（ａ）を求めることは、楕円曲線上の離散対数問題及びＣＤＨ問題により困難なため、秘密情報の秘匿性が保たれる。
【００４８】
２次公開情報受信部１１７は、他の端末１０Ｂ、１０Ｃ又は１０Ｄの２次公開情報送信部１１６から送信された２次公開情報（ａｂＧ、ａｃＧ、ａｄＧ、ｂｃＧ、ｂｄＧ又はｃｄＧ）を、通信部１５を介して受信する。
【００４９】
共通鍵生成部１１８は、２次公開情報生成部１１５により生成された又は２次公開情報受信部１１７により受信された２次公開情報、及び自身の秘密情報（ａ）に基づいて、ペアリング関数を用いて共通鍵を生成する。
【００５０】
具体的には、共通鍵生成部１１８は、共通鍵Ｋｅｙを、例えば、
【数１】
により算出する。なお、算出の式は一例であって、式（８）が成立するように、例えば、式（４）の第１項は、ｅ（ａｃＧ，ｂｄＧ）やｅ（ａｄＧ，ｂｃＧ）に置き換えることもできる。
【００５１】
端末１０Ｂ、１０Ｃ及び１０Ｄにおいても、それぞれ同様に、公開情報と自身の秘密情報とを用いることで、式（８）と同一の共通鍵を算出できる。
【００５２】
このようにして算出された共通鍵は、ペアリング関数ｅ（Ｇ，Ｇ）に対して、４つの端末１０の秘密情報（ａ、ｂ、ｃ及びｄ）からなる５次の値をべき乗した値となっている。一方、公開されている情報は、公開要素Ｇに対して秘密情報からなる１次の値を乗じた１次公開情報と、１次公開情報に対して秘密情報からなる１次の値を乗じた、すなわち秘密情報からなる２次の値を乗じた２次公開情報である。このため、公開情報をどのような組み合わせでペアリング関数に入力しても、秘密情報の高々４次までの値しか求められない。したがって、いずれの秘密情報（ａ、ｂ、ｃ又はｄ）も知らない第三者が、公開情報のみから上記の共通鍵を算出することはできないため、鍵交換システム１により安全に鍵交換が行われている。
【００５３】
図２は、実施形態に係る鍵交換システム１における鍵交換方法を示す概要図である。
端末１０Ａは、秘密情報ａ及び公開要素Ｇを、端末１０Ｂは、秘密情報ｂ及び公開要素Ｇを、端末１０Ｃは、秘密情報ｃ及び公開要素Ｇを、端末１０Ｄは、秘密情報ｄ及び公開要素Ｇを有している。
【００５４】
４つの端末１０のいずれかにより１次公開情報（ａＧ、ｂＧ、ｃＧ及びｄＧ）が生成され、端末間で送受信されることにより公開される。
また、これらの１次公開情報を用いて、４つの端末１０のいずれかにより２次公開情報（ａｂＧ、ａｃＧ、ａｄＧ、ｂｃＧ、ｂｄＧ及びｃｄＧ）が生成され、同様に端末間で送受信されることにより公開される。
【００５５】
そして、各端末１０は、公開された２次公開情報と、自身の秘密情報とに基づいて、共通鍵を生成する。
【００５６】
ここで、２次公開情報は、用いられる２つの秘密情報の一方を有するいずれかの端末１０で生成可能であるため、各端末１０において生成又は受信される２次公開情報が重複する可能性がある。そこで、生成又は受信される２次公開情報が重複しないように、１次公開情報送信部１１３の送信先、及び２次公開情報送信部１１６の送信先が予め設定されていてよい。
【００５７】
また、共通鍵生成部１１８は、６種類の２次公開情報（ａｂＧ、ａｃＧ、ａｄＧ、ｂｃＧ、ｂｄＧ及びｃｄＧ）のうち、自身の秘密情報を用いずに演算された３種類、及び自身の秘密情報を用いて演算された１種類を用いて共通鍵を生成する。そこで、少なくともこれら最小限の公開情報を生成又は受信できるように、１次公開情報送信部１１３の送信先、及び２次公開情報送信部１１６の送信先が予め設定されていてよい。
【００５８】
図３は、本実施形態に係る鍵交換システム１における公開情報の送受信パターンの一例を示す図である。
【００５９】
まず、図３（ａ）のように、１次公開情報は、各端末１０の１次公開情報送信部１１３により、６通りの組み合わせで送信される。そして、各端末１０の２次公開情報生成部１１５は、受信した１次公開情報のそれぞれに応じて、２次公開情報を生成する。
【００６０】
次に、端末１０Ａは、図３（ｂ１）のように、自身の秘密情報を用いずに演算された３種類の２次公開情報を受信する。同様に、端末１０Ｂは、図３（ｂ２）のように、端末１０Ｃは、図３（ｂ３）のように、端末１０Ｄは、図３（ｂ４）のように、自身の秘密情報を用いずに演算された３種類の２次公開情報を受信する。
【００６１】
そして、各端末１０の共通鍵生成部１１８は、生成及び受信した２次公開情報に基づいて、共通鍵を生成する。これにより、鍵交換システム１は、最小限の通信及び演算回数により、鍵交換を行える。
【００６２】
図４は、本実施形態に係る鍵交換システム１における端末の処理手順を示すフローチャートである。なお、端末１０Ａにおける具体例を、図３の送受信パターンに沿って例示する。
【００６３】
ステップＳ１では、秘密情報選択部１１１は、秘密情報（ａ）を選択する。
ステップＳ２では、１次公開情報生成部１１２は、公開要素（Ｇ）と、ステップＳ１で選択された秘密情報（ａ）とから、１次公開情報（ａＧ）を生成する。
ステップＳ３では、１次公開情報送信部１１３は、ステップＳ２で生成された１次公開情報（ａＧ）を、他の端末（端末１０Ｄ）へ送信する。
【００６４】
ステップＳ４では、１次公開情報受信部１１４は、他の端末１０（端末１０Ｂ及び１０Ｃ）から送信された１次公開情報（ｂＧ及びｃＧ）を受信する。
ステップＳ５では、２次公開情報生成部１１５は、ステップＳ４で受信された１次公開情報（ｂＧ及びｃＧ）と、ステップＳ１で選択された秘密情報（ａ）とから、２次公開情報（ａｂＧ及びａｃＧ）を生成する。
ステップＳ６では、２次公開情報送信部１１６は、ステップＳ５で生成された２次公開情報を、他の端末１０へ（ａｂＧを端末１０Ｃ及び１０Ｄへ、ａｃＧを端末１０Ｂ及び１０Ｄへ）送信する。
【００６５】
ステップＳ７では、２次公開情報受信部１１７は、他の端末１０から２次公開情報を（端末１０ＢからｂｃＧ及びｂｄＧを、端末１０ＣからｃｄＧを）受信する。
ステップＳ８では、共通鍵生成部１１８は、生成した２次公開情報（例えば、ａｂＧ）と、受信した２次公開情報（ｂｃＧ、ｂｄＧ及びｃｄＧ）とを用いて、共通鍵を生成する。
【００６６】
このように、本実施形態によれば、鍵交換システム１において、各端末は、秘密情報を用いた楕円曲線上の演算により、１次公開情報及び２次公開情報を公開する。したがって、鍵交換システム１は、楕円曲線上の離散対数問題及びＣＤＨ問題により秘密情報を求めることが困難な情報のみを公開するので、各端末が選択した秘密情報の秘匿性が保たれる。
【００６７】
そして、各端末は、ペアリング関数を用いて、２次公開情報及び秘密情報により共通鍵を生成する。したがって、鍵交換システム１は、複数の鍵交換方式を組み合わせることなく、同一の共通鍵を４者間で容易に共有することができる。その結果、メモリコスト、通信コスト、処理負荷の軽減が期待できる。
【００６８】
また、鍵交換システム１は、公開情報として、秘密情報が１次の値、及び２次の値を公開する。そして、これらの公開情報をどのような組み合わせでペアリング関数に入力しても、秘密情報の高々４次までの値しか求められないのに対して、鍵交換システム１は、秘密情報が５次の値を用いた共通鍵を生成する。したがって、いずれの秘密情報も知らない第三者が、公開情報のみから共通鍵を算出することはできないため、鍵交換の安全性が向上する。
【００６９】
また、鍵交換システム１は、公開情報の重複や、冗長な演算及び通信を抑制するので、さらに公開情報の演算回数及び通信回数が減少し、処理負荷を低減できる。
【００７０】
以上、本発明の実施形態について説明したが、本発明は前述した実施形態に限るものではない。また、本実施形態に記載された効果は、本発明から生じる最も好適な効果を列挙したに過ぎず、本発明による効果は、本実施形態に記載されたものに限定されるものではない。
【００７１】
前述の実施形態において、ペアリング関数への入力である２つの引数は、ペアリングの演算が可能な楕円曲線上の点Ｇのスカラー倍として表されるが、この楕円曲線は、第１引数と第２引数とで共通でなくてもよい。すなわち、ペアリング関数の第１引数用と第２引数用とに、それぞれ異なる楕円曲線上の２点（Ｇ１又はＧ２）が与えられていてもよい。
この場合、前述の実施形態の説明におけるペアリング関数の第１引数に表れるＧはＧ１に、第２引数に表れるＧはＧ２に読み替えられる。また、楕円曲線上の点を用いて生成される前述の各種公開情報は、ペアリング関数の第１引数又は第２引数のいずれに入力されるかに応じて、Ｇ１若しくはＧ２のいずれかを用いて１種類、又は双方を用いて２種類生成される。
このことにより、公開情報の数、すなわち演算回数が増加する場合があるが、ペアリング関数の演算において並列して処理できるため、計算時間の短縮が期待できる。
【符号の説明】
【００７２】
１ 鍵交換システム
１０（１０Ａ、１０Ｂ、１０Ｃ、１０Ｄ） 端末
１１ 制御部
１２ 記憶部
１３ 入力部
１４ 表示部
１５ 通信部
１１１ 秘密情報選択部（選択部）
１１２ １次公開情報生成部（第１の公開情報生成部）
１１３ １次公開情報送信部（第１の送信部）
１１４ １次公開情報受信部（第１の受信部）
１１５ ２次公開情報生成部（第２の公開情報生成部）
１１６ ２次公開情報送信部（第２の送信部）
１１７ ２次公開情報受信部（第２の受信部）
１１８ 共通鍵生成部（鍵生成部）
【技術分野】
【０００１】
本発明は、共通鍵暗号における鍵を共有するための鍵交換システム、鍵交換方法及び鍵交換プログラムに関する。
【背景技術】
【０００２】
従来、通信装置（端末）の間で秘密情報の通信を安全に行うために、暗号通信が用いられている。暗号の方式には、共通鍵暗号方式と公開鍵暗号方式とがある。共通鍵暗号方式は、暗号通信を行う端末の間で共通の鍵を用いる方式であり、例えばＡＥＳ（Ａｄｖａｎｃｅｄ Ｅｎｃｒｙｐｔｉｏｎ Ｓｔａｎｄａｒｄ）が知られている。また、公開鍵暗号方式は、秘密鍵と公開鍵との２つの鍵を用いる方式で、例えばＲＳＡ（Ｒｉｖｅｓｔ Ｓｈａｍｉｒ Ａｄｌｅｍａｎ）暗号が知られている。
【０００３】
ところで、公開鍵暗号方式は、暗号化のために端末間で鍵交換をする必要がないという利点がある。しかし、公開鍵暗号方式は、共通鍵暗号方式と比較して処理速度が遅い、あるいは負荷が重いという性能面での難点があるため、公開鍵暗号方式だけで全ての通信の暗号化を行うのは効率的ではない。
【０００４】
一方、共通鍵暗号化方式では、暗号通信を行う端末間で共通鍵を共有することが必要である。原始的には、第三者による傍受の困難な方法として、共通鍵は、それぞれの端末の管理者が対面して交換されたり、通信回線とは別の郵送等のルートを用いて交換されたりしていた。しかし、こうした原始的な共通鍵の交換方法は、非効率であり、ネットワーク通信を実現する上では実用的ではなかった。
【０００５】
そこで、通信回線を介して共通鍵を配送する様々な手法が提案されている。例えば、Ｄｉｆｆｉｅ−Ｈｅｌｌｍａｎの鍵共有方式（非特許文献１参照）や、その応用例（特許文献１参照）が提案されている。
【先行技術文献】
【特許文献】
【０００６】
【特許文献１】特開２０００−２７８２５８号公報
【非特許文献】
【０００７】
【非特許文献１】Ｗ．Ｄｉｆｆｉｅ ａｎｄ Ｍ．Ｅ．Ｈｅｌｌｍａｎ， “Ｎｅｗ Ｄｉｒｅｃｔｉｏｎｓ ｉｎ Ｃｒｙｐｔｏｇｒａｐｈｙ，” ＩＥＥＥ Ｔｒａｎｓ． ｏｎ Ｉｎｆｏｒｍａｔｉｏｎ Ｔｈｅｏｒｙ， Ｖｏｌ．２２， Ｎｏ．６， ｐｐ．６４４−６５４， １９７６
【非特許文献２】Ａ．Ｊｏｕｘ， “Ａ Ｏｎｅ Ｒｏｕｎｄ Ｐｒｏｔｏｃｏｌ ｆｏｒ Ｔｒｉｐａｒｔｉｔｅ Ｄｉｆｆｉｅ−Ｈｅｌｌｍａｎ，” Ｐｒｏｃ． ｏｆ Ａｌｇｏｒｉｔｈｍｉｃ Ｎｕｍｂｅｒ Ｔｈｅｏｒｙ Ｓｙｍｐｏｓｉｕｍ ＩＶ， Ｓｐｒｉｎｇｅｒ−Ｖｅｒｌａｇ， ＬＮＣＳ １８３８， ｐｐ．３８５−３９３， ２０００
【発明の概要】
【発明が解決しようとする課題】
【０００８】
前述のＤｉｆｆｉｅ−Ｈｅｌｌｍａｎ鍵共有方式は、通信回線を使用して安全に鍵交換できる方式であるが、２者間のみで鍵を共有することしかできない。したがって、多人数で同一の共通鍵を共有する必要がある場合には、この鍵共有方式を複数の組み合わせに対して行い、さらに実際の鍵情報を共有する複雑な手順が必要となるため、通信の負荷が増大していた。さらに、この場合、複数の組み合わせにおける共有情報を管理する装置（サーバ）が必要となることもあり、システム構築の金銭的コストが増大していた。
【０００９】
そこで、ペアリングと呼ばれる関数を用いることで、３者間で鍵共有を行う方式が提案されている（例えば、非特許文献２参照）。しかしながら、４者間以上での鍵交換は、複数の方式を組み合わせずには実現できなかった。
【００１０】
本発明は、４者間で容易に鍵交換が行える鍵交換システム、鍵交換方法及び鍵交換プログラムを提供することを目的とする。
【課題を解決するための手段】
【００１１】
本発明では、以下のような解決手段を提供する。
【００１２】
（１）４つの端末が共通鍵を共有する鍵交換システムであって、各端末は、自然数からなる秘密情報を選択する選択部と、ＧＤＨ（ＧＡＰ−Ｄｉｆｆｉｅ−Ｈｅｌｌｍａｎ）グループに属する公開要素に対して、前記秘密情報により演算を行い、第１の公開情報を生成する第１の公開情報生成部と、前記第１の公開情報生成部により生成された前記第１の公開情報を、他の端末へ送信する第１の送信部と、前記他の端末から送信された前記第１の公開情報を受信する第１の受信部と、前記第１の受信部により受信された前記第１の公開情報に対して、前記秘密情報により演算を行い、第２の公開情報を生成する第２の公開情報生成部と、前記第２の公開情報生成部により生成された前記第２の公開情報を、他の端末へ送信する第２の送信部と、前記他の端末から送信された前記第２の公開情報を受信する第２の受信部と、前記第２の公開情報生成部により生成された又は前記第２の受信部により受信された前記第２の公開情報、及び前記秘密情報に基づいて、前記共通鍵を生成する鍵生成部と、を備える鍵交換システム。
【００１３】
このような構成によれば、当該鍵交換システムにおいて、各端末は、ＧＤＨグループに属する公開要素、及び自然数からなる秘密情報により、第１の公開情報及び第２の公開情報を生成して送信することにより公開する。したがって、当該鍵交換システムは、秘密情報を求めることが困難な情報のみを公開するので、各端末が選択した秘密情報の秘匿性が保たれる。
【００１４】
そして、各端末は、第２の公開情報及び秘密情報により共通鍵を生成する。したがって、当該鍵交換システムは、複数の鍵交換方式を組み合わせることなく、同一の共通鍵を４者間で容易に共有することができる。
【００１５】
（２）前記第１の公開情報生成部は、前記公開要素に対して、前記秘密情報からなる１次の値を乗じて、前記第１の公開情報を生成し、前記第２の公開情報生成部は、前記第１の公開情報に対して、前記秘密情報からなる１次の値を乗じて、前記第２の公開情報を生成し、前記鍵生成部は、双線形のペアリング関数に対して、前記４つの端末の秘密情報からなる５次の値をべき乗した値を前記共通鍵として生成する（１）に記載の鍵交換システム。
【００１６】
このような構成によれば、当該鍵交換システムは、公開情報として、秘密情報が１次の値、及び２次の値を公開する。そして、これらの公開情報をどのような組み合わせでペアリング関数に入力しても、秘密情報の高々４次までの値しか求められないのに対して、当該鍵交換システムは、秘密情報が５次の値を用いた共通鍵を生成する。したがって、いずれの秘密情報も知らない第三者が、公開情報のみから共通鍵を算出することはできないため、鍵交換の安全性が向上する。
【００１７】
（３）前記各端末において生成又は受信される前記第２の公開情報が重複しないように、前記第１の送信部の送信先、及び前記第２の送信部の送信先が予め設定されている（１）又は（２）に記載の鍵交換システム。
【００１８】
このような構成によれば、当該鍵交換システムは、公開情報の重複を回避するので、公開情報の演算回数及び通信回数が減少し、処理負荷を低減できる。
【００１９】
（４）前記各端末において生成又は受信される前記第２の公開情報は、自端末の秘密情報を用いずに演算された３種類、及び自端末の秘密情報を用いて演算された１種類である（３）に記載の鍵交換システム。
【００２０】
このような構成によれば、当該鍵交換システムは、冗長な公開情報の演算及び通信を抑制するので、さらに演算回数及び通信回数が減少し、処理負荷を低減できる。
【００２１】
（５）４つの端末が共通鍵を共有する鍵交換方法であって、各端末は、自然数からなる秘密情報を選択する選択ステップと、ＧＤＨ（ＧＡＰ−Ｄｉｆｆｉｅ−Ｈｅｌｌｍａｎ）グループに属する公開要素に対して、前記秘密情報により演算を行い、第１の公開情報を生成する第１の公開情報生成ステップと、前記第１の公開情報生成ステップにおいて生成された前記第１の公開情報を、他の端末へ送信する第１の送信ステップと、前記他の端末から送信された前記第１の公開情報を受信する第１の受信ステップと、前記第１の受信ステップにおいて受信された前記第１の公開情報に対して、前記秘密情報により演算を行い、第２の公開情報を生成する第２の公開情報生成ステップと、前記第２の公開情報生成ステップにおいて生成された前記第２の公開情報を、他の端末へ送信する第２の送信ステップと、前記他の端末から送信された前記第２の公開情報を受信する第２の受信ステップと、前記第２の公開情報生成ステップにおいて生成された又は前記第２の受信ステップにおいて受信された前記第２の公開情報、及び前記秘密情報に基づいて、前記共通鍵を生成する鍵生成ステップと、を実行する鍵交換方法。
【００２２】
このような構成によれば、当該鍵交換方法を各端末が実行することにより、（１）と同様の効果が期待できる。
【００２３】
（６）４つの端末に共通鍵を共有させる鍵交換プログラムであって、各端末に、自然数からなる秘密情報を選択する選択ステップと、ＧＤＨ（ＧＡＰ−Ｄｉｆｆｉｅ−Ｈｅｌｌｍａｎ）グループに属する公開要素に対して、前記秘密情報により演算を行い、第１の公開情報を生成する第１の公開情報生成ステップと、前記第１の公開情報生成ステップにおいて生成された前記第１の公開情報を、他の端末へ送信する第１の送信ステップと、前記他の端末から送信された前記第１の公開情報を受信する第１の受信ステップと、前記第１の受信ステップにおいて受信された前記第１の公開情報に対して、前記秘密情報により演算を行い、第２の公開情報を生成する第２の公開情報生成ステップと、前記第２の公開情報生成ステップにおいて生成された前記第２の公開情報を、他の端末へ送信する第２の送信ステップと、前記他の端末から送信された前記第２の公開情報を受信する第２の受信ステップと、前記第２の公開情報生成ステップにおいて生成された又は前記第２の受信ステップにおいて受信された前記第２の公開情報、及び前記秘密情報に基づいて、前記共通鍵を生成する鍵生成ステップと、を実行させる鍵交換プログラム。
【００２４】
このような構成によれば、当該鍵交換プログラムを各端末に実行させることにより、（１）と同様の効果が期待できる。
【発明の効果】
【００２５】
本発明によれば、４者間で容易に鍵交換が行える。
【図面の簡単な説明】
【００２６】
【図１】本発明の実施形態に係る鍵交換システムの機能構成を示すブロック図である。
【図２】本発明の実施形態に係る鍵交換方法を示す概要図である。
【図３】本発明の実施形態に係る公開情報の送受信パターンの一例を示す図である。
【図４】本発明の実施形態に係る端末の処理手順を示すフローチャートである。
【発明を実施するための形態】
【００２７】
以下、本発明の実施形態の一例について説明する。本実施形態に係る鍵交換システム１は、所定の通信及び演算により、４つの端末１０（１０Ａ、１０Ｂ、１０Ｃ及び１０Ｄ）間で共通鍵を共有する。
【００２８】
まず、本実施形態の鍵交換システムで用いるペアリング関数について説明する。
Ｇをある楕円曲線上の点の集合とする。ｇを集合Ｇの要素としたとき、集合Ｇにおける楕円曲線上のＤｅｃｉｓｉｏｎａｌ Ｄｉｆｆｉｅ−Ｈｅｌｌｍａｎ（ＤＤＨ）問題とＣｏｍｐｕｔａｔｉｏｎａｌ Ｄｉｆｆｉｅ−Ｈｅｌｌｍａｎ（ＣＤＨ）問題が以下のように定義される。
【００２９】
ＤＤＨ問題：あるａ、ｂ、ｃ∈Ｚｐ＊（ｐ未満の自然数）があり、ｇ、ａｇ、ｂｇ、ｃｇが与えられた時、ｃ＝ａｂかどうかを判定する問題。
ＣＤＨ問題：あるａ、ｂ、ｃ∈Ｚｐ＊があり、ｇ、ａｇ、ｂｇが与えられた時、ａｂｇを計算する問題。
【００３０】
このとき、ＤＤＨ問題は、計算量的に簡単であるが、ＣＤＨ問題は、計算量的に難問である場合、この集合ＧをＧＤＨ（ＧＡＰ−Ｄｉｆｆｉｅ−Ｈｅｌｌｍａｎ）グループと定義する。
【００３１】
これに対し、ある楕円曲線上の点をＰ，Ｑとし、そのＰ，Ｑによっては、次にあげる双線形と呼ばれる性質を持つことができる、ペアリング関数と呼ばれるブラックボックス関数ｅ（Ｐ，Ｑ）を定義できるものが存在する。
ｅ（Ｐ，Ｑ１＋Ｑ２）＝ｅ（Ｐ，Ｑ１）ｅ（Ｐ，Ｑ２） ・・・（１）
ｅ（Ｐ１＋Ｐ２，Ｑ）＝ｅ（Ｐ１，Ｑ）ｅ（Ｐ２，Ｑ） ・・・（２）
ｅ（ａＰ，ｂＱ）＝ｅ（ｂＰ，ａＱ）＝ｅ（ａｂＰ，Ｑ）＝ｅ（Ｐ，ａｂＱ）＝ｅ（Ｐ，Ｑ）ａｂ ・・・（３）
【００３２】
図１は、本実施形態に係る鍵交換システム１の機能構成を示すブロック図である。
４つの端末１０（１０Ａ、１０Ｂ、１０Ｃ及び１０Ｄ）は、ネットワークを介して接続されている。そして、端末１０は、それぞれ、制御部１１と、記憶部１２と、入力部１３と、表示部１４と、通信部１５とを備える。
【００３３】
制御部１１は、端末１０の全体を制御する部分であり、記憶部１２に記憶された各種プログラムを適宜読み出して実行することにより、前述のハードウェアと協働し、本実施形態における各種機能を実現している。制御部１１は、ＣＰＵ（Ｃｅｎｔｒａｌ Ｐｒｏｃｅｓｓｉｎｇ Ｕｎｉｔ）であってよい。なお、制御部１１が備える各部の機能は後述する。
【００３４】
記憶部１２は、ハードウェア群を端末１０として機能させるための各種プログラム、及び各種データ等の記憶領域であり、ハードディスク（ＨＤＤ）であってよい。具体的には、記憶部１２には、本実施形態の各種機能を制御部１１に実行させるプログラムと、端末固有の秘密情報及び各種公開情報とが記憶される。
【００３５】
入力部１３は、端末１０に対するユーザからの指示入力を受け付けるインタフェース装置である。入力部１３は、例えば、キーボード、マウス及びタッチパネル等により構成される。
【００３６】
表示部１４は、ユーザにデータの入力を受け付ける画面を表示したり、端末１０による処理結果の画面を表示したりするものである。表示部１４は、ブラウン管表示装置（ＣＲＴ）や液晶表示装置（ＬＣＤ）等のディスプレイ装置であってよい。
【００３７】
通信部１５は、ネットワークを介して外部装置と通信を行うネットワーク・アダプタである。通信部１５は、４つの端末間での相互の通信を確立し、互いに各種データの送受信を行う。具体的には、本実施形態では、共通鍵の生成に用いられる各種公開情報が送受信される。
【００３８】
次に、端末１０の制御部１１の機能を詳述する。
各端末１０には、共通して、予め公開要素として、ペアリングの演算が可能な楕円曲線上の点Ｇが与えられている。以下、４つの端末１０のうち、代表して端末１０Ａを説明する。
【００３９】
制御部１１は、秘密情報選択部１１１（選択部）と、１次公開情報生成部１１２（第１の公開情報生成部）と、１次公開情報送信部１１３（第１の送信部）と、１次公開情報受信部１１４（第１の受信部）と、２次公開情報生成部１１５（第２の公開情報生成部）と、２次公開情報送信部１１６（第２の送信部）と、２次公開情報受信部１１７（第２の受信部）と、共通鍵生成部１１８（鍵生成部）とを備える。
【００４０】
秘密情報選択部１１１は、自然数からなる端末１０Ａに固有の秘密情報（ａ∈Ｚｐ＊）をランダムに選択する。なお、端末１０Ｂは秘密情報ｂを、端末１０Ｃは秘密情報ｃを、端末１０Ｄは秘密情報ｄを選択する。
【００４１】
１次公開情報生成部１１２は、ＧＤＨグループに属する公開要素（Ｇ）に対して、自身の秘密情報（ａ）により演算（ａ倍）を行い、１次公開情報（ａＧ；第１の公開情報）を生成する。
【００４２】
１次公開情報送信部１１３は、１次公開情報生成部１１２により生成された１次公開情報（ａＧ）を公開する。具体的には、１次公開情報送信部１１３は、１次公開情報（ａＧ）を、通信部１５を介して、他の端末１０Ｂ、１０Ｃ又は１０Ｄへ送信する。
【００４３】
なお、公開された１次公開情報（ａＧ）から秘密情報（ａ）を求めることは、楕円曲線上の離散対数問題により困難なため、秘密情報の秘匿性が保たれる。
【００４４】
１次公開情報受信部１１４は、他の端末１０Ｂ、１０Ｃ又は１０Ｄの１次公開情報送信部１１３から送信された１次公開情報（ｂＧ、ｃＧ又はｄＧ）を、通信部１５を介して受信する。
【００４５】
２次公開情報生成部１１５は、１次公開情報受信部１１４により受信された１次公開情報（ｂＧ、ｃＧ又はｄＧ）に対して、自身の秘密情報（ａ）により演算（ａ倍）を行い、２次公開情報（ａｂＧ、ａｃＧ又はａｄＧ；第２の公開情報）を生成する。
【００４６】
２次公開情報送信部１１６は、２次公開情報生成部１１５により生成された２次公開情報（ｂＧ、ｃＧ又はｄＧ）を公開する。具体的には、２次公開情報送信部１１６は、２次公開情報（ｂＧ、ｃＧ又はｄＧ）を、通信部１５を介して、他の端末１０Ｂ、１０Ｃ又は１０Ｄへ送信する。
【００４７】
なお、公開された１次公開情報（ａＧ）及び２次公開情報（ａｂＧ、ａｃＧ又はａｄＧ）から秘密情報（ａ）を求めることは、楕円曲線上の離散対数問題及びＣＤＨ問題により困難なため、秘密情報の秘匿性が保たれる。
【００４８】
２次公開情報受信部１１７は、他の端末１０Ｂ、１０Ｃ又は１０Ｄの２次公開情報送信部１１６から送信された２次公開情報（ａｂＧ、ａｃＧ、ａｄＧ、ｂｃＧ、ｂｄＧ又はｃｄＧ）を、通信部１５を介して受信する。
【００４９】
共通鍵生成部１１８は、２次公開情報生成部１１５により生成された又は２次公開情報受信部１１７により受信された２次公開情報、及び自身の秘密情報（ａ）に基づいて、ペアリング関数を用いて共通鍵を生成する。
【００５０】
具体的には、共通鍵生成部１１８は、共通鍵Ｋｅｙを、例えば、
【数１】
により算出する。なお、算出の式は一例であって、式（８）が成立するように、例えば、式（４）の第１項は、ｅ（ａｃＧ，ｂｄＧ）やｅ（ａｄＧ，ｂｃＧ）に置き換えることもできる。
【００５１】
端末１０Ｂ、１０Ｃ及び１０Ｄにおいても、それぞれ同様に、公開情報と自身の秘密情報とを用いることで、式（８）と同一の共通鍵を算出できる。
【００５２】
このようにして算出された共通鍵は、ペアリング関数ｅ（Ｇ，Ｇ）に対して、４つの端末１０の秘密情報（ａ、ｂ、ｃ及びｄ）からなる５次の値をべき乗した値となっている。一方、公開されている情報は、公開要素Ｇに対して秘密情報からなる１次の値を乗じた１次公開情報と、１次公開情報に対して秘密情報からなる１次の値を乗じた、すなわち秘密情報からなる２次の値を乗じた２次公開情報である。このため、公開情報をどのような組み合わせでペアリング関数に入力しても、秘密情報の高々４次までの値しか求められない。したがって、いずれの秘密情報（ａ、ｂ、ｃ又はｄ）も知らない第三者が、公開情報のみから上記の共通鍵を算出することはできないため、鍵交換システム１により安全に鍵交換が行われている。
【００５３】
図２は、実施形態に係る鍵交換システム１における鍵交換方法を示す概要図である。
端末１０Ａは、秘密情報ａ及び公開要素Ｇを、端末１０Ｂは、秘密情報ｂ及び公開要素Ｇを、端末１０Ｃは、秘密情報ｃ及び公開要素Ｇを、端末１０Ｄは、秘密情報ｄ及び公開要素Ｇを有している。
【００５４】
４つの端末１０のいずれかにより１次公開情報（ａＧ、ｂＧ、ｃＧ及びｄＧ）が生成され、端末間で送受信されることにより公開される。
また、これらの１次公開情報を用いて、４つの端末１０のいずれかにより２次公開情報（ａｂＧ、ａｃＧ、ａｄＧ、ｂｃＧ、ｂｄＧ及びｃｄＧ）が生成され、同様に端末間で送受信されることにより公開される。
【００５５】
そして、各端末１０は、公開された２次公開情報と、自身の秘密情報とに基づいて、共通鍵を生成する。
【００５６】
ここで、２次公開情報は、用いられる２つの秘密情報の一方を有するいずれかの端末１０で生成可能であるため、各端末１０において生成又は受信される２次公開情報が重複する可能性がある。そこで、生成又は受信される２次公開情報が重複しないように、１次公開情報送信部１１３の送信先、及び２次公開情報送信部１１６の送信先が予め設定されていてよい。
【００５７】
また、共通鍵生成部１１８は、６種類の２次公開情報（ａｂＧ、ａｃＧ、ａｄＧ、ｂｃＧ、ｂｄＧ及びｃｄＧ）のうち、自身の秘密情報を用いずに演算された３種類、及び自身の秘密情報を用いて演算された１種類を用いて共通鍵を生成する。そこで、少なくともこれら最小限の公開情報を生成又は受信できるように、１次公開情報送信部１１３の送信先、及び２次公開情報送信部１１６の送信先が予め設定されていてよい。
【００５８】
図３は、本実施形態に係る鍵交換システム１における公開情報の送受信パターンの一例を示す図である。
【００５９】
まず、図３（ａ）のように、１次公開情報は、各端末１０の１次公開情報送信部１１３により、６通りの組み合わせで送信される。そして、各端末１０の２次公開情報生成部１１５は、受信した１次公開情報のそれぞれに応じて、２次公開情報を生成する。
【００６０】
次に、端末１０Ａは、図３（ｂ１）のように、自身の秘密情報を用いずに演算された３種類の２次公開情報を受信する。同様に、端末１０Ｂは、図３（ｂ２）のように、端末１０Ｃは、図３（ｂ３）のように、端末１０Ｄは、図３（ｂ４）のように、自身の秘密情報を用いずに演算された３種類の２次公開情報を受信する。
【００６１】
そして、各端末１０の共通鍵生成部１１８は、生成及び受信した２次公開情報に基づいて、共通鍵を生成する。これにより、鍵交換システム１は、最小限の通信及び演算回数により、鍵交換を行える。
【００６２】
図４は、本実施形態に係る鍵交換システム１における端末の処理手順を示すフローチャートである。なお、端末１０Ａにおける具体例を、図３の送受信パターンに沿って例示する。
【００６３】
ステップＳ１では、秘密情報選択部１１１は、秘密情報（ａ）を選択する。
ステップＳ２では、１次公開情報生成部１１２は、公開要素（Ｇ）と、ステップＳ１で選択された秘密情報（ａ）とから、１次公開情報（ａＧ）を生成する。
ステップＳ３では、１次公開情報送信部１１３は、ステップＳ２で生成された１次公開情報（ａＧ）を、他の端末（端末１０Ｄ）へ送信する。
【００６４】
ステップＳ４では、１次公開情報受信部１１４は、他の端末１０（端末１０Ｂ及び１０Ｃ）から送信された１次公開情報（ｂＧ及びｃＧ）を受信する。
ステップＳ５では、２次公開情報生成部１１５は、ステップＳ４で受信された１次公開情報（ｂＧ及びｃＧ）と、ステップＳ１で選択された秘密情報（ａ）とから、２次公開情報（ａｂＧ及びａｃＧ）を生成する。
ステップＳ６では、２次公開情報送信部１１６は、ステップＳ５で生成された２次公開情報を、他の端末１０へ（ａｂＧを端末１０Ｃ及び１０Ｄへ、ａｃＧを端末１０Ｂ及び１０Ｄへ）送信する。
【００６５】
ステップＳ７では、２次公開情報受信部１１７は、他の端末１０から２次公開情報を（端末１０ＢからｂｃＧ及びｂｄＧを、端末１０ＣからｃｄＧを）受信する。
ステップＳ８では、共通鍵生成部１１８は、生成した２次公開情報（例えば、ａｂＧ）と、受信した２次公開情報（ｂｃＧ、ｂｄＧ及びｃｄＧ）とを用いて、共通鍵を生成する。
【００６６】
このように、本実施形態によれば、鍵交換システム１において、各端末は、秘密情報を用いた楕円曲線上の演算により、１次公開情報及び２次公開情報を公開する。したがって、鍵交換システム１は、楕円曲線上の離散対数問題及びＣＤＨ問題により秘密情報を求めることが困難な情報のみを公開するので、各端末が選択した秘密情報の秘匿性が保たれる。
【００６７】
そして、各端末は、ペアリング関数を用いて、２次公開情報及び秘密情報により共通鍵を生成する。したがって、鍵交換システム１は、複数の鍵交換方式を組み合わせることなく、同一の共通鍵を４者間で容易に共有することができる。その結果、メモリコスト、通信コスト、処理負荷の軽減が期待できる。
【００６８】
また、鍵交換システム１は、公開情報として、秘密情報が１次の値、及び２次の値を公開する。そして、これらの公開情報をどのような組み合わせでペアリング関数に入力しても、秘密情報の高々４次までの値しか求められないのに対して、鍵交換システム１は、秘密情報が５次の値を用いた共通鍵を生成する。したがって、いずれの秘密情報も知らない第三者が、公開情報のみから共通鍵を算出することはできないため、鍵交換の安全性が向上する。
【００６９】
また、鍵交換システム１は、公開情報の重複や、冗長な演算及び通信を抑制するので、さらに公開情報の演算回数及び通信回数が減少し、処理負荷を低減できる。
【００７０】
以上、本発明の実施形態について説明したが、本発明は前述した実施形態に限るものではない。また、本実施形態に記載された効果は、本発明から生じる最も好適な効果を列挙したに過ぎず、本発明による効果は、本実施形態に記載されたものに限定されるものではない。
【００７１】
前述の実施形態において、ペアリング関数への入力である２つの引数は、ペアリングの演算が可能な楕円曲線上の点Ｇのスカラー倍として表されるが、この楕円曲線は、第１引数と第２引数とで共通でなくてもよい。すなわち、ペアリング関数の第１引数用と第２引数用とに、それぞれ異なる楕円曲線上の２点（Ｇ１又はＧ２）が与えられていてもよい。
この場合、前述の実施形態の説明におけるペアリング関数の第１引数に表れるＧはＧ１に、第２引数に表れるＧはＧ２に読み替えられる。また、楕円曲線上の点を用いて生成される前述の各種公開情報は、ペアリング関数の第１引数又は第２引数のいずれに入力されるかに応じて、Ｇ１若しくはＧ２のいずれかを用いて１種類、又は双方を用いて２種類生成される。
このことにより、公開情報の数、すなわち演算回数が増加する場合があるが、ペアリング関数の演算において並列して処理できるため、計算時間の短縮が期待できる。
【符号の説明】
【００７２】
１ 鍵交換システム
１０（１０Ａ、１０Ｂ、１０Ｃ、１０Ｄ） 端末
１１ 制御部
１２ 記憶部
１３ 入力部
１４ 表示部
１５ 通信部
１１１ 秘密情報選択部（選択部）
１１２ １次公開情報生成部（第１の公開情報生成部）
１１３ １次公開情報送信部（第１の送信部）
１１４ １次公開情報受信部（第１の受信部）
１１５ ２次公開情報生成部（第２の公開情報生成部）
１１６ ２次公開情報送信部（第２の送信部）
１１７ ２次公開情報受信部（第２の受信部）
１１８ 共通鍵生成部（鍵生成部）
【特許請求の範囲】
【請求項１】
４つの端末が共通鍵を共有する鍵交換システムであって、
各端末は、
自然数からなる秘密情報を選択する選択部と、
ＧＤＨ（ＧＡＰ−Ｄｉｆｆｉｅ−Ｈｅｌｌｍａｎ）グループに属する公開要素に対して、前記秘密情報により演算を行い、第１の公開情報を生成する第１の公開情報生成部と、
前記第１の公開情報生成部により生成された前記第１の公開情報を、他の端末へ送信する第１の送信部と、
前記他の端末から送信された前記第１の公開情報を受信する第１の受信部と、
前記第１の受信部により受信された前記第１の公開情報に対して、前記秘密情報により演算を行い、第２の公開情報を生成する第２の公開情報生成部と、
前記第２の公開情報生成部により生成された前記第２の公開情報を、他の端末へ送信する第２の送信部と、
前記他の端末から送信された前記第２の公開情報を受信する第２の受信部と、
前記第２の公開情報生成部により生成された又は前記第２の受信部により受信された前記第２の公開情報、及び前記秘密情報に基づいて、前記共通鍵を生成する鍵生成部と、を備える鍵交換システム。
【請求項２】
前記第１の公開情報生成部は、前記公開要素に対して、前記秘密情報からなる１次の値を乗じて、前記第１の公開情報を生成し、
前記第２の公開情報生成部は、前記第１の公開情報に対して、前記秘密情報からなる１次の値を乗じて、前記第２の公開情報を生成し、
前記鍵生成部は、双線形のペアリング関数に対して、前記４つの端末の秘密情報からなる５次の値をべき乗した値を前記共通鍵として生成する請求項１に記載の鍵交換システム。
【請求項３】
前記各端末において生成又は受信される前記第２の公開情報が重複しないように、前記第１の送信部の送信先、及び前記第２の送信部の送信先が予め設定されている請求項１又は請求項２に記載の鍵交換システム。
【請求項４】
前記各端末において生成又は受信される前記第２の公開情報は、自端末の秘密情報を用いずに演算された３種類、及び自端末の秘密情報を用いて演算された１種類である請求項３に記載の鍵交換システム。
【請求項５】
４つの端末が共通鍵を共有する鍵交換方法であって、
各端末は、
自然数からなる秘密情報を選択する選択ステップと、
ＧＤＨ（ＧＡＰ−Ｄｉｆｆｉｅ−Ｈｅｌｌｍａｎ）グループに属する公開要素に対して、前記秘密情報により演算を行い、第１の公開情報を生成する第１の公開情報生成ステップと、
前記第１の公開情報生成ステップにおいて生成された前記第１の公開情報を、他の端末へ送信する第１の送信ステップと、
前記他の端末から送信された前記第１の公開情報を受信する第１の受信ステップと、
前記第１の受信ステップにおいて受信された前記第１の公開情報に対して、前記秘密情報により演算を行い、第２の公開情報を生成する第２の公開情報生成ステップと、
前記第２の公開情報生成ステップにおいて生成された前記第２の公開情報を、他の端末へ送信する第２の送信ステップと、
前記他の端末から送信された前記第２の公開情報を受信する第２の受信ステップと、
前記第２の公開情報生成ステップにおいて生成された又は前記第２の受信ステップにおいて受信された前記第２の公開情報、及び前記秘密情報に基づいて、前記共通鍵を生成する鍵生成ステップと、を実行する鍵交換方法。
【請求項６】
４つの端末に共通鍵を共有させる鍵交換プログラムであって、
各端末に、
自然数からなる秘密情報を選択する選択ステップと、
ＧＤＨ（ＧＡＰ−Ｄｉｆｆｉｅ−Ｈｅｌｌｍａｎ）グループに属する公開要素に対して、前記秘密情報により演算を行い、第１の公開情報を生成する第１の公開情報生成ステップと、
前記第１の公開情報生成ステップにおいて生成された前記第１の公開情報を、他の端末へ送信する第１の送信ステップと、
前記他の端末から送信された前記第１の公開情報を受信する第１の受信ステップと、
前記第１の受信ステップにおいて受信された前記第１の公開情報に対して、前記秘密情報により演算を行い、第２の公開情報を生成する第２の公開情報生成ステップと、
前記第２の公開情報生成ステップにおいて生成された前記第２の公開情報を、他の端末へ送信する第２の送信ステップと、
前記他の端末から送信された前記第２の公開情報を受信する第２の受信ステップと、
前記第２の公開情報生成ステップにおいて生成された又は前記第２の受信ステップにおいて受信された前記第２の公開情報、及び前記秘密情報に基づいて、前記共通鍵を生成する鍵生成ステップと、を実行させる鍵交換プログラム。
【請求項１】
４つの端末が共通鍵を共有する鍵交換システムであって、
各端末は、
自然数からなる秘密情報を選択する選択部と、
ＧＤＨ（ＧＡＰ−Ｄｉｆｆｉｅ−Ｈｅｌｌｍａｎ）グループに属する公開要素に対して、前記秘密情報により演算を行い、第１の公開情報を生成する第１の公開情報生成部と、
前記第１の公開情報生成部により生成された前記第１の公開情報を、他の端末へ送信する第１の送信部と、
前記他の端末から送信された前記第１の公開情報を受信する第１の受信部と、
前記第１の受信部により受信された前記第１の公開情報に対して、前記秘密情報により演算を行い、第２の公開情報を生成する第２の公開情報生成部と、
前記第２の公開情報生成部により生成された前記第２の公開情報を、他の端末へ送信する第２の送信部と、
前記他の端末から送信された前記第２の公開情報を受信する第２の受信部と、
前記第２の公開情報生成部により生成された又は前記第２の受信部により受信された前記第２の公開情報、及び前記秘密情報に基づいて、前記共通鍵を生成する鍵生成部と、を備える鍵交換システム。
【請求項２】
前記第１の公開情報生成部は、前記公開要素に対して、前記秘密情報からなる１次の値を乗じて、前記第１の公開情報を生成し、
前記第２の公開情報生成部は、前記第１の公開情報に対して、前記秘密情報からなる１次の値を乗じて、前記第２の公開情報を生成し、
前記鍵生成部は、双線形のペアリング関数に対して、前記４つの端末の秘密情報からなる５次の値をべき乗した値を前記共通鍵として生成する請求項１に記載の鍵交換システム。
【請求項３】
前記各端末において生成又は受信される前記第２の公開情報が重複しないように、前記第１の送信部の送信先、及び前記第２の送信部の送信先が予め設定されている請求項１又は請求項２に記載の鍵交換システム。
【請求項４】
前記各端末において生成又は受信される前記第２の公開情報は、自端末の秘密情報を用いずに演算された３種類、及び自端末の秘密情報を用いて演算された１種類である請求項３に記載の鍵交換システム。
【請求項５】
４つの端末が共通鍵を共有する鍵交換方法であって、
各端末は、
自然数からなる秘密情報を選択する選択ステップと、
ＧＤＨ（ＧＡＰ−Ｄｉｆｆｉｅ−Ｈｅｌｌｍａｎ）グループに属する公開要素に対して、前記秘密情報により演算を行い、第１の公開情報を生成する第１の公開情報生成ステップと、
前記第１の公開情報生成ステップにおいて生成された前記第１の公開情報を、他の端末へ送信する第１の送信ステップと、
前記他の端末から送信された前記第１の公開情報を受信する第１の受信ステップと、
前記第１の受信ステップにおいて受信された前記第１の公開情報に対して、前記秘密情報により演算を行い、第２の公開情報を生成する第２の公開情報生成ステップと、
前記第２の公開情報生成ステップにおいて生成された前記第２の公開情報を、他の端末へ送信する第２の送信ステップと、
前記他の端末から送信された前記第２の公開情報を受信する第２の受信ステップと、
前記第２の公開情報生成ステップにおいて生成された又は前記第２の受信ステップにおいて受信された前記第２の公開情報、及び前記秘密情報に基づいて、前記共通鍵を生成する鍵生成ステップと、を実行する鍵交換方法。
【請求項６】
４つの端末に共通鍵を共有させる鍵交換プログラムであって、
各端末に、
自然数からなる秘密情報を選択する選択ステップと、
ＧＤＨ（ＧＡＰ−Ｄｉｆｆｉｅ−Ｈｅｌｌｍａｎ）グループに属する公開要素に対して、前記秘密情報により演算を行い、第１の公開情報を生成する第１の公開情報生成ステップと、
前記第１の公開情報生成ステップにおいて生成された前記第１の公開情報を、他の端末へ送信する第１の送信ステップと、
前記他の端末から送信された前記第１の公開情報を受信する第１の受信ステップと、
前記第１の受信ステップにおいて受信された前記第１の公開情報に対して、前記秘密情報により演算を行い、第２の公開情報を生成する第２の公開情報生成ステップと、
前記第２の公開情報生成ステップにおいて生成された前記第２の公開情報を、他の端末へ送信する第２の送信ステップと、
前記他の端末から送信された前記第２の公開情報を受信する第２の受信ステップと、
前記第２の公開情報生成ステップにおいて生成された又は前記第２の受信ステップにおいて受信された前記第２の公開情報、及び前記秘密情報に基づいて、前記共通鍵を生成する鍵生成ステップと、を実行させる鍵交換プログラム。
【図１】
【図２】
【図３】
【図４】
【図２】
【図３】
【図４】
【公開番号】特開２０１２−６０６１９（Ｐ２０１２−６０６１９Ａ）
【公開日】平成２４年３月２２日（２０１２．３．２２）
【国際特許分類】
【出願番号】特願２０１０−２０４９３２（Ｐ２０１０−２０４９３２）
【出願日】平成２２年９月１３日（２０１０．９．１３）
【出願人】（０００２０８８９１）ＫＤＤＩ株式会社 (2,700)
【Ｆターム（参考）】
【公開日】平成２４年３月２２日（２０１２．３．２２）
【国際特許分類】
【出願日】平成２２年９月１３日（２０１０．９．１３）
【出願人】（０００２０８８９１）ＫＤＤＩ株式会社 (2,700)
【Ｆターム（参考）】
[ Back to top ]