(57)【特許請求の範囲】
【請求項１】
サーバと、Ｎ台のクライアント端末とが通信可能に接続された共通鍵生成システムであって、
前記サーバは、
１個の基数、１個の除数及びＮ個の秘密鍵を生成するサーバ側鍵情報生成手段と、
前記Ｎ個の秘密鍵それぞれについて、基数を底とし、当該秘密鍵を指数とした冪乗に対して前記除数で除算した場合に生成されるＮ個の剰余をＮ個の中間鍵とするサーバ側中間鍵生成手段と、
前記Ｎ台のクライアント端末と前記Ｎ個の中間鍵の送受信を行うサーバ側通信制御手段と、
前記クライアント端末からＮ個の中間鍵を前記サーバ側通信制御手段によって受信したことに応じて、Ｎ個の秘密鍵それぞれについて他の秘密鍵の値に置換し、受信したＮ個の中間鍵それぞれについて、当該中間鍵を底とし、置換されたＮ個の秘密鍵のうち当該中間鍵に対応する秘密鍵を指数とした場合の剰余を前記除数で除算した場合に生成されるＮ個の剰余をＮ個の中間鍵とすることにより、Ｎ個の中間鍵を更新するサーバ側中間鍵更新手段と、を備え、
前記Ｎ台のクライアント端末それぞれは、
前記サーバから前記除数を受信すると共に前記Ｎ個の中間鍵の送受信を行う端末側通信制御手段と、
前記端末側通信制御手段により前記除数及び前記Ｎ個の中間鍵を受信したことに応じて、私有鍵を生成する私有鍵生成手段と、
前記私有鍵生成手段により前記私有鍵を生成したことに応じて、前記クライアント端末に対応する中間鍵の値を変更せずに更新したとみなすと共に、当該中間鍵以外のＮ−１個の中間鍵それぞれについて、当該中間鍵を底とし、当該私有鍵を指数とした冪乗に対して前記除数で除算した場合に生成されるＮ個の剰余を前記Ｎ個の中間鍵とすることにより、Ｎ個の中間鍵を更新する端末側中間鍵更新手段と、
前記端末側通信制御手段により前記Ｎ個の中間鍵のみを受信したことに応じて、前記クライアント端末に対応する中間鍵を底とし、前記私有鍵を指数とした冪乗に対して前記除数で除算した場合に生成される剰余を共通鍵とする共通鍵生成手段と、を備え、
前記サーバ側中間鍵更新手段は、Ｎ個の秘密鍵それぞれについて、ｉ番目の秘密鍵（ｉは１からＮ−１のいずれか）をｉ＋１番目の秘密鍵に置換すると共にＮ番目の秘密鍵を１番目の秘密鍵に置換することで、前記他の秘密鍵の値に置換し、
前記サーバ側通信制御手段は、前記サーバ側中間鍵更新手段により前記Ｎ個の中間鍵を更新したことに応じて前記クライアント端末に当該Ｎ個の中間鍵を送信し、前記クライアント端末から前記Ｎ個の中間鍵を受信した場合に前記Ｎ個の中間鍵が置換された回数がＮ−１回であるとき、Ｎ台のクライアント端末全てに対して前記Ｎ個の中間鍵を送信する、
共通鍵生成システム。
【請求項２】
サーバと、Ｎ台のクライアント端末とが通信可能に接続された共通鍵生成システムにおいて共通鍵を生成する方法であって、
前記サーバが、
１個の基数、１個の除数及びＮ個の秘密鍵を生成するサーバ側鍵生成ステップと、
前記Ｎ個の秘密鍵それぞれについて、前記基数を底とし、当該秘密鍵を指数とした冪乗に対して前記除数で除算した場合に生成されるＮ個の剰余をＮ個の中間鍵としてＮ個の中間鍵を生成するサーバ側中間鍵生成ステップと、
前記Ｎ台のクライアント端末のうち、前記除数を送信していない、いずれか１のクライアント端末に前記Ｎ個の中間鍵を送信する第１サーバ側送信ステップと、
前記クライアント端末それぞれが、
前記サーバから前記除数及び前記Ｎ個の中間鍵を受信する第１端末側受信ステップと、
前記第１端末側受信ステップにおいて前記除数及び前記Ｎ個の中間鍵を受信したことに応じて私有鍵を生成する私有鍵生成ステップと、
前記私有鍵生成ステップにおいて前記私有鍵が生成されたことに応じて、前記クライアント端末に対応する中間鍵の値を変更せずに更新したとみなすと共に、当該中間鍵以外のＮ−１個の中間鍵それぞれについて、当該中間鍵を底とし、当該私有鍵を指数とした冪乗に対して前記除数で除算した場合に生成されるＮ個の剰余を前記Ｎ個の中間鍵とすることにより、Ｎ個の中間鍵を更新する端末側中間鍵更新ステップと、
前記端末側中間鍵更新ステップにおいて前記Ｎ個の中間鍵が更新されたことに応じて当該Ｎ個の中間鍵を前記サーバに送信する端末側送信ステップと、を含み、
前記サーバは、
前記クライアント端末から、Ｎ個の中間鍵を受信するサーバ側受信ステップと、
前記サーバ側受信ステップにおいて前記Ｎ個の中間鍵を受信したことに応じて、Ｎ個の秘密鍵それぞれについて、ｉ番目の秘密鍵（ｉは１からＮ−１のいずれか）をｉ＋１番目の秘密鍵に置換すると共にＮ番目の秘密鍵を１番目の秘密鍵に置換することで、他の秘密鍵の値に置換する置換ステップと、
前記置換ステップにおいて前記Ｎ個の秘密鍵が置換されたことに応じて、前記サーバ側受信ステップにおいて受信したＮ個の中間鍵それぞれについて、当該中間鍵を底とし、置換されたＮ個の秘密鍵のうち当該中間鍵に対応する秘密鍵を指数とした場合の剰余を前記除数で除算した場合に生成されるＮ個の剰余をＮ個の中間鍵とすることにより、Ｎ個の中間鍵を更新するサーバ側中間鍵更新ステップと、
前記サーバ側中間鍵更新ステップにより更新されたＮ個の中間鍵を、前記除数を送信していない、いずれか１のクライアント端末に前記Ｎ個の中間鍵を送信する第２サーバ側送信ステップと、
前記サーバ側受信ステップにおいて、前記クライアント端末から前記Ｎ個の中間鍵を受信した場合に前記Ｎ個の中間鍵が置換された回数がＮ−１回であるとき、Ｎ台のクライアント端末全てに対して前記Ｎ個の中間鍵を送信する第３サーバ側送信ステップを更に含み、
前記クライアント端末は、
前記サーバから前記Ｎ個の中間鍵のみ受信する第２端末側受信ステップと、
前記第２端末側受信ステップにおいて前記Ｎ個の中間鍵のみ受信したことに応じて、記クライアント端末に対応する中間鍵を底とし、前記私有鍵を指数とした冪乗に対して前記除数で除算した場合に生成される剰余を共通鍵とする共通鍵生成ステップと、を更に含む、
共通鍵生成方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、共通鍵生成システム及び共通鍵生成方法に関する。
【背景技術】
【０００２】
近年、インターネット等のネットワークをデータの交換手段として利用することが急速に広まっている。しかしながら、インターネット等のネットワークでは、データを交換する際に複数のサーバ及び通信回線を経由してデータが転送される。このため、データを転送するサーバ及び通信回線等では、データの盗聴や、データの改ざんや、なりすましをすることが可能となり、セキュリティ問題に発展している。このようなセキュリティ問題に対応するため、暗号化技術が提案されており、例えば、簡易的な暗号化方式として、共通鍵暗号方式が知られている。
【０００３】
共通鍵暗号方式では、例えば、特許文献１に示されるように、生成した共通鍵を、２者間で所有する。続いて、送信者は、共通鍵を用いてデータの暗号化を行い、暗号化されたデータを閲覧者に送信する。閲覧者は、データを受信すると、共通鍵を用いて暗号化されたデータを復号する。
【先行技術文献】
【特許文献】
【０００４】
【特許文献１】特開２０００−２７８２５８号公報
【発明の概要】
【発明が解決しようとする課題】
【０００５】
しかしながら、特許文献１に示される共通鍵交換方式は、２者間において共通鍵を生成する方式であり、三者以上の間において、共通鍵を生成する方法については示されていない。このため、三者以上の間において、安全に共通鍵を生成することができる共通鍵生成システム及び共通鍵生成方法の提供が望まれている。
【０００６】
本発明は、共通鍵の受け渡しを行わずに、三者以上の間で安全に共通鍵を共有することができる共通鍵生成システム及び共通鍵生成方法を提供することを目的とする。
【課題を解決するための手段】
【０００７】
本発明に係る共通鍵生成システムは、サーバと、Ｎ台のクライアント端末とが通信可能に接続された共通鍵生成システムであって、前記サーバは、１個の基数、１個の除数及びＮ個の秘密鍵を生成するサーバ側鍵情報生成手段と、前記Ｎ個の秘密鍵それぞれについて、基数を底とし、当該秘密鍵を指数とした冪乗に対して前記除数で除算した場合に生成されるＮ個の剰余をＮ個の中間鍵とするサーバ側中間鍵生成手段と、前記Ｎ台のクライアント端末と前記Ｎ個の中間鍵の送受信を行うサーバ側通信制御手段と、前記クライアント端末からＮ個の中間鍵を前記サーバ側通信制御手段によって受信したことに応じて、Ｎ個の秘密鍵それぞれについて他の秘密鍵の値に置換し、受信したＮ個の中間鍵それぞれについて、当該中間鍵を底とし、置換されたＮ個の秘密鍵のうち当該中間鍵に対応する秘密鍵を指数とした場合の剰余を前記除数で除算した場合に生成されるＮ個の剰余をＮ個の中間鍵とすることにより、Ｎ個の中間鍵を更新するサーバ側中間鍵更新手段と、を備え、前記Ｎ台のクライアント端末それぞれは、前記サーバから前記除数を受信すると共に前記Ｎ個の中間鍵の送受信を行う端末側通信制御手段と、前記端末側通信制御手段により前記除数及び前記Ｎ個の中間鍵を受信したことに応じて、私有鍵を生成する私有鍵生成手段と、前記私有鍵生成手段により前記私有鍵を生成したことに応じて、前記クライアント端末に対応する中間鍵の値を変更せずに更新したとみなすと共に、当該中間鍵以外のＮ−１個の中間鍵それぞれについて、当該中間鍵を底とし、当該私有鍵を指数とした冪乗に対して前記除数で除算した場合に生成されるＮ個の剰余を前記Ｎ個の中間鍵とすることにより、Ｎ個の中間鍵を更新する端末側中間鍵更新手段と、前記端末側通信制御手段により前記Ｎ個の中間鍵のみを受信したことに応じて、前記クライアント端末に対応する中間鍵を底とし、前記私有鍵を指数とした冪乗に対して前記除数で除算した場合に生成される剰余を共通鍵とする共通鍵生成手段と、を備え、前記サーバ側中間鍵更新手段は、Ｎ個の秘密鍵それぞれについて、ｉ番目の秘密鍵（ｉは１からＮ−１のいずれか）をｉ＋１番目の秘密鍵に置換すると共にＮ番目の秘密鍵を１番目の秘密鍵に置換することで、前記他の秘密鍵の値に置換し、前記サーバ側通信制御手段は、前記サーバ側中間鍵更新手段により前記Ｎ個の中間鍵を更新したことに応じて前記クライアント端末に当該Ｎ個の中間鍵を送信し、前記クライアント端末から前記Ｎ個の中間鍵を受信した場合に前記Ｎ個の中間鍵が置換された回数がＮ−１回であるとき、Ｎ台のクライアント端末全てに対して前記Ｎ個の中間鍵を送信する。
【０００８】
本発明に係る共通鍵生成方法は、サーバと、Ｎ台のクライアント端末とが通信可能に接続された共通鍵生成システムにおいて共通鍵を生成する方法であって、前記サーバが、１個の基数、１個の除数及びＮ個の秘密鍵を生成するサーバ側鍵生成ステップと、前記Ｎ個の秘密鍵それぞれについて、前記基数を底とし、当該秘密鍵を指数とした冪乗に対して前記除数で除算した場合に生成されるＮ個の剰余をＮ個の中間鍵としてＮ個の中間鍵を生成するサーバ側中間鍵生成ステップと、前記Ｎ台のクライアント端末のうち、前記除数を送信していない、いずれか１のクライアント端末に前記Ｎ個の中間鍵を送信する第１サーバ側送信ステップと、前記クライアント端末それぞれが、前記サーバから前記除数及び前記Ｎ個の中間鍵を受信する第１端末側受信ステップと、前記第１端末側受信ステップにおいて前記除数及び前記Ｎ個の中間鍵を受信したことに応じて私有鍵を生成する私有鍵生成ステップと、前記私有鍵生成ステップにおいて前記私有鍵が生成されたことに応じて、前記クライアント端末に対応する中間鍵の値を変更せずに更新したとみなすと共に、当該中間鍵以外のＮ−１個の中間鍵それぞれについて、当該中間鍵を底とし、当該私有鍵を指数とした冪乗に対して前記除数で除算した場合に生成されるＮ個の剰余を前記Ｎ個の中間鍵とすることにより、Ｎ個の中間鍵を更新する端末側中間鍵更新ステップと、前記端末側中間鍵更新ステップにおいて前記Ｎ個の中間鍵が更新されたことに応じて当該Ｎ個の中間鍵を前記サーバに送信する端末側送信ステップと、を含み、前記サーバは、前記クライアント端末から、Ｎ個の中間鍵を受信するサーバ側受信ステップと、前記サーバ側受信ステップにおいて前記Ｎ個の中間鍵を受信したことに応じて、Ｎ個の秘密鍵それぞれについて、ｉ番目の秘密鍵（ｉは１からＮ−１のいずれか）をｉ＋１番目の秘密鍵に置換すると共にＮ番目の秘密鍵を１番目の秘密鍵に置換することで、他の秘密鍵の値に置換する置換ステップと、前記置換ステップにおいて前記Ｎ個の秘密鍵が置換されたことに応じて、前記サーバ側受信ステップにおいて受信したＮ個の中間鍵それぞれについて、当該中間鍵を底とし、置換されたＮ個の秘密鍵のうち当該中間鍵に対応する秘密鍵を指数とした場合の剰余を前記除数で除算した場合に生成されるＮ個の剰余をＮ個の中間鍵とすることにより、Ｎ個の中間鍵を更新するサーバ側中間鍵更新ステップと、前記サーバ側中間鍵更新ステップにより更新されたＮ個の中間鍵を、前記除数を送信していない、いずれか１のクライアント端末に前記Ｎ個の中間鍵を送信する第２サーバ側送信ステップと、前記サーバ側受信ステップにおいて、前記クライアント端末から前記Ｎ個の中間鍵を受信した場合に前記Ｎ個の中間鍵が置換された回数がＮ−１回であるとき、Ｎ台のクライアント端末全てに対して前記Ｎ個の中間鍵を送信する第３サーバ側送信ステップを更に含み、前記クライアント端末は、前記サーバから前記Ｎ個の中間鍵のみ受信する第２端末側受信ステップと、前記第２端末側受信ステップにおいて前記Ｎ個の中間鍵のみ受信したことに応じて、記クライアント端末に対応する中間鍵を底とし、前記私有鍵を指数とした冪乗に対して前記除数で除算した場合に生成される剰余を共通鍵とする共通鍵生成ステップと、を更に含む。
【発明の効果】
【０００９】
本発明によれば、共通鍵の受け渡しを行わずに、三者以上の間で安全に共通鍵を共有することができる。
【図面の簡単な説明】
【００１０】
【図１】本実施形態に係る共通鍵生成システムの全体概要を示す図である。
【図２】本実施形態に係る第１共通鍵生成装置の機能構成を示す図である。
【図３】本実施形態に係る第２共通鍵生成装置の機能構成を示す図である。
【図４】本実施形態に係るサーバに係る処理の流れを示すフローチャートである。
【図５】本実施形態に係るクライアント端末に係る処理の流れを示すフローチャートである。
【図６】本実施形態に係る冪剰余算出部における処理の流れを示すフローチャートである。
【発明を実施するための形態】
【００１１】
以下、本発明の実施形態について図を参照しながら説明する。
【００１２】
［機能構成］
図１は、本実施形態に係る共通鍵生成システム１の全体概要を示す図である。共通鍵生成システム１は、複数のクライアント端末それぞれで共通鍵を生成するシステムである。共通鍵生成システム１は、サーバＳＶと、Ｎ台のクライアント端末（ＣＬ１、ＣＬ２、・・・ＣＬＮ）とを備える。ここで、Ｎ台のクライアント端末（ＣＬ１、ＣＬ２、・・・ＣＬＮ）をまとめて、クライアント端末ＣＬとする。サーバＳＶと、Ｎ台のクライアント端末ＣＬとは、ＬＡＮ（Ｌｏｃａｌ  Ａｒｅａ  Ｎｅｔｗｏｒｋ）やインターネット等のコンピュータネットワークにより構成される通信ネットワークＮにより、通信可能に接続されている。
【００１３】
このサーバＳＶでは、基数Ｂ、除数Ｄ、及びＮ個の秘密鍵Ｓ１、Ｓ２、・・・ＳＮ（以下、Ｎ個の秘密鍵をまとめて秘密鍵Ｓともいう）を生成し、基数Ｂ、除数Ｄ、及び秘密鍵Ｓに基づいてＮ個の中間鍵Ｒを生成し、クライアント端末ＣＬに、除数Ｄ、及び中間鍵Ｒを送信する。また、クライアント端末ＣＬでは、除数Ｄ及び中間鍵Ｒを受信すると共に私有鍵Ｐを生成し、中間鍵Ｒを更新して、中間鍵ＲをサーバＳＶに送信する。サーバＳＶでは、その後、秘密鍵Ｓをシフトすると共に、中間鍵Ｒを更新し、全てのクライアント端末ＣＬと中間鍵の送受信を繰り返す。その後、サーバＳＶは、全てのクライアント端末ＣＬに対して中間鍵Ｒを送信する。その後、Ｎ台のクライアント端末ＣＬは、除数Ｄ、私有鍵Ｐ及び中間鍵Ｒから共通鍵Ｃを生成する。
本実施形態における各部は、コンピュータ及びその周辺装置が備えるハードウェア並びにこのハードウェアを制御するソフトウェアによって構成される。
【００１４】
図２は、本実施形態に係るサーバＳＶの機能構成を示す図である。
サーバＳＶは、コンピュータであり、サーバ側制御部１０と、サーバ側記憶部１１と、サーバ側通信部１２と、サーバ側表示部１３と、サーバ側入力部１４とを備える。
【００１５】
サーバ側制御部１０は、ＣＰＵ等により構成されており、サーバＳＶの全体を制御する。サーバ側制御部１０の詳細な機能については、後述する。サーバ側記憶部１１は、メモリ（ＲＡＭ、ＲＯＭ等）、ハードディスクドライブ（ＨＤＤ）及び光ディスク（ＣＤ、ＤＶＤ等）ドライブ等により構成されており、サーバＳＶをコンピュータとして動作させるための各種プログラムやデータを記憶する。サーバ側通信部１２は、各種有線及び無線インターフェース装置等により構成され、クライアント端末ＣＬと通信を行う。サーバ側表示部１３は、液晶ディスプレイ、プラズマディスプレイ等の各種ディスプレイにより構成され、各種機能に係る情報を表示する。サーバ側入力部１４は、キーボード及びマウス等により構成され、操作者からの操作を受け付ける。
【００１６】
サーバ側制御部１０は、サーバ側鍵情報生成手段としてのサーバ側鍵情報生成部１１０と、第１冪剰余算出手段としての冪剰余算出部１２０と、サーバ中間鍵生成手段としてのサーバ側中間鍵生成部１３０と、サーバ側通信制御手段としてのサーバ側通信制御部１４０と、サーバ側中間鍵更新手段としてのサーバ側中間鍵更新部１５０と、を備える。
【００１７】
サーバ側鍵情報生成部１１０は、共通鍵を生成する情報となる１個の基数Ｂ、１個の除数Ｄを生成する。具体的には、サーバ側鍵情報生成部１１０は、基数Ｂとして任意の自然数を生成し、除数Ｄとして、桁数が大きい自然数（例えば、２０桁以上の自然数）を生成する。また、サーバ側鍵情報生成部１１０は、Ｎ個の秘密鍵Ｓ１、Ｓ２、・・・ＳＮとして、「１」以上であり、それぞれが異なる（同一でもよい）自然数を生成する。Ｎ個の秘密鍵それぞれには、番号が付されている。具体的には、秘密鍵Ｓ１には１、Ｓ２には２、Ｓｉにはｉというように番号が付されている。ここで、Ｓｉをｉ番目の秘密鍵という。サーバ側鍵情報生成部１１０は、生成された基数Ｂ、除数Ｄ、及びＮ個の秘密鍵Ｓをサーバ側記憶部１１に記憶させる。
【００１８】
冪剰余算出部１２０は、底、除数、及び指数の入力を受け付け、この底の指数乗を、除数で除算した場合の剰余を算出し、この算出した剰余を出力する。冪剰余算出部１２０は、入力受付手段としての入力受付部１２１と、初期設定手段としての初期設定部１２２と、変換手段としての変換部１２３と、計数手段としての計数部１２４と、基数算出手段としての基数算出部１２５と、剰余算出手段としての剰余算出部１２６と、シフト手段としてのシフト部１２７と、反復実行手段としての反復実行部１２８と、出力手段としての出力部１２９と、を備える。また、冪剰余算出部１２０は、第１中間値ＡＴと、第２中間値ＭＴとを有する。
【００１９】
入力受付部１２１は、底、除数、及び指数の入力を受け付ける。ここで、入力受付部１２１により受け付けられた底、除数、及び指数を、それぞれ底Ａｉ、除数Ｂｉ、指数ｅとする。
【００２０】
初期設定部１２２は、第１中間値ＡＴの初期値を底Ａｉとし、第２中間値ＭＴの初期値を１に設定する。
変換部１２３は、指数ｅを、１０進数から２進数に変換する。
【００２１】
計数部１２４は、変換部１２３により２進数に変換された指数ｅのビット数を計数する。
【００２２】
基数算出部１２５は、２進数で表現された指数ｅの右端の値（ビット）が１である場合、第１中間値ＡＴを第２中間値ＭＴで乗算して得られた値を除数Ｂｉで除算した場合の剰余を第１中間値ＡＴとすることにより、第１中間値ＡＴを更新する。
【００２３】
なお、第１中間値ＡＴと第２中間値ＭＴとの乗算は、以下のように行われる。すなわち、基数算出部１２５は、第１中間値ＡＴ及び第２中間値ＭＴを、以下の（１）式に示すように、複数桁（例えば、１桁目〜５桁目、６桁目〜１０桁目等、５桁ずつ）に区切り、１０の冪乗により構成される多項式、すなわち、初項を１０の冪乗（例えば１０の５乗）の０乗、公比を当該１０の冪乗（例えば１０の５乗）とした数列の和で表される多項式に変換する。
【数１】
0005340347.tif 000002
【００２４】
ここで、ａ１…ａｍは、第１中間値ＡＴを満たすためにそれぞれの項に付される係数であり、ｂ１…ｂｎは、第２中間値ＭＴを満たすためにそれぞれの項に付される係数である。
【００２５】
続いて、基数算出部１２５は、１０の冪乗の和に変換された第１中間値ＡＴ及び第２中間値ＭＴの多項式を乗算して、（２）式に示すように展開する。その後、展開された値に含まれるそれぞれの項を合計することにより、第１中間値ＡＴと第２中間値ＭＴとを乗算した値を算出する。
【数２】
0005340347.tif 000003
【００２６】
剰余算出部１２６は、２進数に変換された指数ｅの右端の値（ビット）にかかわらず、第１中間値ＡＴを２乗した値を除数Ｂｉで除算した場合の剰余を第２中間値ＭＴとすることにより、第２中間値ＭＴを更新する。なお、第１中間値ＡＴの２乗の計算は、第１中間値ＡＴと第２中間値ＭＴとの乗算と同様に、第１中間値ＡＴを、初項を１０の冪乗（例えば１０の５乗）の０乗、公比を当該１０の冪乗（例えば１０の５乗）とした数列の和で表される多項式に変換し、この多項式の第１中間値ＡＴを２乗することにより計算される。
【００２７】
シフト部１２７は、２進数に変換された指数ｅを右シフトする。具体的には、シフト部１２７は、２進数に変換された指数ｅを１ビット右に論理シフトする演算（論理シフト演算）を行う。
【００２８】
反復実行部１２８は、計数部１２４により計数されたビット数の値を反復回数とし、基数算出部１２５、剰余算出部１２６、及びシフト部１２７に係る処理が、基数算出部１２５、剰余算出部１２６、シフト部１２７の順に、反復回数実行されるように制御する。具体的には、記憶部に初期値を０とするカウンタを設けておき、反復実行部１２８は、基数算出部１２５、剰余算出部１２６、及びシフト部１２７に係る処理が終了したことに応じて、カウンタに１加算（インクリメント）する。その後、反復実行部１２８は、カウンタの値が反復回数に達するまで、基数算出部１２５、剰余算出部１２６、シフト部１２７、インクリメントに係る処理を実行する制御を行い、カウンタの値が反復回数に達した場合に、反復実行を終了する。
【００２９】
出力部１２９は、反復実行部１２８により、基数算出部１２５、剰余算出部１２６、及びシフト部１２７に係る処理が反復回数実行された後、第２中間値ＭＴを剰余として出力する。
【００３０】
サーバ側中間鍵生成部１３０は、サーバ側鍵情報生成部１１０によって基数Ｂ、除数Ｄ、及びＮ個の秘密鍵Ｓが生成されたことに応じて、Ｎ個の秘密鍵それぞれについて、基数Ｂを底とし、当該秘密鍵を指数とした冪乗を、除数Ｄで除算した場合のＮ個の剰余をＮ個の中間鍵とすることにより、Ｎ個の中間鍵を生成する。
【００３１】
まず、サーバ側中間鍵生成部１３０は、基数Ｂを底、除数Ｄを除数、１番目の秘密鍵Ｓ１を指数とし、これら底、除数、及び指数を冪剰余算出部１２０に入力することにより、冪剰余算出部１２０から、基数Ｂを底とし、秘密鍵Ｓ１を指数とした冪乗を除数Ｄで除算した場合の剰余を得る。続いて、サーバ側中間鍵生成部１３０は、得られた剰余を中間鍵Ｒ１とする。
【００３２】
続いて、サーバ側中間鍵生成部１３０は、秘密鍵Ｓ２、Ｓ３、・・・ＳＮについても秘密鍵Ｓ１において中間鍵Ｒ１を算出した手順と同様の手順で、中間鍵Ｒ２、Ｒ３、・・・ＲＮを算出する。ここで、生成されたＮ個の中間鍵Ｒ１、Ｒ２、・・・ＲＮをまとめて中間鍵Ｒという。続いて、サーバ側中間鍵生成部１３０は、生成されたＮ個の中間鍵Ｒをサーバ側記憶部１１に記憶させる。
【００３３】
サーバ側通信制御部１４０は、サーバ側通信部１２を介して各種情報を送受信する。
具体的には、サーバ側通信制御部１４０は、サーバ側鍵情報生成部１１０により生成された除数Ｄと、サーバ側中間鍵生成部１３０により生成されたＮ個の中間鍵Ｒとを、Ｎ台のクライアント端末ＣＬのうち、いずれか一の端末に送信する。また、サーバ側通信制御部１４０は、送信するクライアント端末に対して、１からＮのうちいずれか１の番号を端末番号として送信する。
【００３４】
また、サーバ側通信制御部１４０は、サーバ側鍵情報生成部１１０により生成された除数Ｄとサーバ側中間鍵更新部１５０により更新された中間鍵Ｒとを、Ｎ台のクライアント端末ＣＬのうち、除数Ｄを送信していない、いずれか一の端末に送信する。
【００３５】
また、サーバ側通信制御部１４０は、後述の置換回数がＮ−１回になった場合、サーバ側中間鍵更新部１５０により更新されたＮ個の中間鍵ＲをＮ台のクライアント端末ＣＬのすべてに送信する。
【００３６】
また、サーバ側通信制御部１４０は、Ｎ台のクライアント端末ＣＬから、Ｎ台のクライアント端末それぞれで更新された中間鍵Ｒを受信する。
【００３７】
サーバ側中間鍵更新部１５０は、サーバ側通信制御部１４０によって、Ｎ台のクライアント端末ＣＬのいずれかから中間鍵Ｒを受信した場合において、サーバ側記憶部１１に記憶されている秘密鍵の置換回数がＮ−１回より小さいとき、秘密鍵Ｓの内容を置換する。
【００３８】
具体的には、サーバ側中間鍵更新部１５０は、秘密鍵Ｓｉの値を他の秘密鍵の値に置換する。すなわち、サーバ側中間鍵更新部１５０は、ｉ（Ｎを除く）番目の秘密鍵Ｓｉを、ｉ＋１番目の秘密鍵Ｓｉ＋１に置換する。また、サーバ側中間鍵更新部１５０は、Ｎ番目の秘密鍵ＳＮの値を１番目の秘密鍵Ｓ１の値に置換する。サーバ側中間鍵更新部１５０は、Ｎ個の秘密鍵Ｓの内容を置換した回数を置換回数としてサーバ側記憶部１１に記憶させる。
【００３９】
また、サーバ側中間鍵更新部１５０は、秘密鍵Ｓを置換した後、Ｎ個の中間鍵Ｒそれぞれについて、当該中間鍵Ｒを底とし、当該中間鍵Ｒに対応する秘密鍵を指数とした冪乗を、除数Ｄで除算した場合の剰余を当該中間鍵Ｒに置き換えることで、中間鍵Ｒを更新する。
【００４０】
具体的には、サーバ側中間鍵更新部１５０は、中間鍵Ｒ１を底、除数Ｄを除数、中間鍵Ｒ１に対応する秘密鍵Ｓ１を指数とし、これら底、除数、及び指数を冪剰余算出部１２０に入力することにより、冪剰余算出部１２０から、中間鍵Ｒ１を底とし、秘密鍵Ｓ１を指数とした冪乗を除数Ｄで除算した場合の剰余を得る。続いて、サーバ側中間鍵更新部１７は、中間鍵Ｒ１の値を得られた剰余の値に置換することで中間鍵Ｒ１を更新する。
【００４１】
続いて、サーバ側中間鍵更新部１５０は、中間鍵Ｒ２、Ｒ３、・・・ＲＮについても、それぞれ対応する秘密鍵Ｓ２、Ｓ３、・・・ＳＮを指数とし、除数Ｄとした場合の冪剰余を算出することで、中間鍵Ｒ１を算出した手順と同様の手順で、中間鍵Ｒ２、Ｒ３、・・・ＲＮを更新する。
【００４２】
図３は、本実施形態に係るクライアント端末ＣＬｉの機能構成を示す図である。ここで、クライアント端末ＣＬ１、ＣＬ２、・・・ＣＬＮの有する機能は同一であるので、クライアント端末ＣＬｉ（ｉは、１からＮの間の任意の数である）の機能構成に図示するものとする。ここで、クライアント端末ＣＬは、私有鍵Ｐを保有することが可能であり、クライアント端末ＣＬｉに対応する私有鍵を、私有鍵Ｐｉとする。
【００４３】
クライアント端末ＣＬｉは、サーバＳＶと同様にコンピュータであり、端末側制御部２０と、端末側記憶部２１と、端末側通信部２２と、端末側表示部２３と、端末側入力部２４と、を備える。
【００４４】
端末側制御部２０は、ＣＰＵ等により構成されており、クライアント端末ＣＬｉの全体を制御する。端末側制御部２０の詳細な機能については、後述する。端末側記憶部２１は、メモリ、ハードディスクドライブ及び光ディスクドライブ等により構成されており、クライアント端末ＣＬｉをコンピュータとして動作させるための各種プログラムやデータを記憶する。端末側通信部２２は、各種有線及び無線インターフェース装置等により構成され、サーバＳＶと通信を行う。端末側表示部２３は、液晶ディスプレイ、プラズマディスプレイ等の各種ディスプレイにより構成され、各種機能に係る情報を表示する。端末側入力部２４は、キーボード及びマウス等により構成され、操作者からの操作を受け付ける。
【００４５】
端末側制御部２０は、端末側通信制御手段としての端末側通信制御部２１０と、私有鍵生成手段としての私有鍵生成部２２０と、第２冪剰余算出手段としての冪剰余算出部２３０と、端末側中間鍵更新手段としての端末側中間鍵更新部２４０と、共通鍵生成手段としての共通鍵生成部２５０と、を備える。
【００４６】
端末側通信制御部２１０は、端末側通信部２２を介して各種情報を送受信する。
具体的には、端末側通信制御部２１０は、サーバＳＶからＮ個の中間鍵Ｒと、除数Ｄと、端末番号を受信する。
また、端末側通信制御部２１０は、端末側中間鍵更新部２４０により中間鍵Ｒが更新されたことに応じて、更新された中間鍵ＲをサーバＳＶに送信する。
【００４７】
私有鍵生成部２２０は、端末側通信制御部２１０によりサーバＳＶから中間鍵Ｒを初めて受信した場合に私有鍵Ｐｉを生成する。私有鍵Ｐｉは、「１」以上の任意の自然数である。
【００４８】
冪剰余算出部２３０は、サーバＳＶの冪剰余算出部１２０と同等の機能を有する。すなわち、冪剰余算出部２３０は、冪剰余算出部１２０が備える入力受付部１２１、初期設定部１２２、変換部１２３、計数部１２４、基数算出部１２５、剰余算出部１２６、シフト部１２７、反復実行部１２８及び出力部１２９と同等の機能を有する、入力受付部２３１、初期設定部２３２、変換部２３３、計数部２３４、基数算出部２３５、剰余算出部２３６、シフト部２３７、反復実行部２３８及び出力部２３９を備える。
【００４９】
端末側中間鍵更新部２４０は、端末側通信制御部２１０によりサーバＳＶから中間鍵Ｒを初めて受信し、私有鍵生成部２２０により私有鍵Ｐｉが生成されたことに応じて、当該クライアント端末ＣＬｉに対応している中間鍵Ｒｉを除いたＮ−１個の中間鍵Ｒについて、当該中間鍵Ｒを底とし、私有鍵Ｐｉを指数とした冪乗を、端末側通信制御部２１０によって受信した除数Ｄで除算した場合の剰余を当該中間鍵Ｒに置き換えることで、中間鍵Ｒを更新する。ここで、クライアント端末ＣＬｉに対応している中間鍵Ｒｉは、端末番号に対応している中間鍵である。例えば、端末番号が２である場合、中間鍵Ｒ２がクライアント端末ＣＬｉに対応する。
【００５０】
まず、端末側中間鍵更新部２４０は、中間鍵Ｒ１を底、除数Ｄを除数、私有鍵Ｐｉを指数とし、これら底、除数、及び指数を冪剰余算出部２３０に入力することにより、冪剰余算出部２３０から、中間鍵Ｒ１を底とし、私有鍵Ｐｉを指数とした冪乗を除数Ｄで除算した場合の剰余を得る。続いて、端末側中間鍵更新部２４０は、中間鍵Ｒ１の値を得られた剰余の値に置換することで、中間鍵Ｒ１を更新する。
【００５１】
続いて、端末側中間鍵更新部２４０は、中間鍵Ｒ２、Ｒ３、・・・ＲＮについても、私有鍵Ｐｉを指数とし、除数Ｄとした場合の冪剰余を算出することで、中間鍵Ｒ１を算出した手順と同様の手順で、中間鍵Ｒ２、Ｒ３、・・・ＲＮを更新する。
なお、端末側中間鍵更新部２４０は、中間鍵Ｒｉの値を更新しないが、中間鍵Ｒｉについても更新されたものとみなす。
【００５２】
共通鍵生成部２５０は、端末側通信制御部２１０によりサーバＳＶから中間鍵Ｒのみを受信したことに応じて、クライアント端末ＣＬｉに対応している中間鍵Ｒｉを底とし、私有鍵Ｐｉを指数とした冪乗を、除数Ｄで除算した場合の剰余を算出する。そして、共通鍵生成部２６は、当該剰余を共通鍵Ｃとすることで、Ｎ台のクライアント端末ＣＬの共通鍵Ｃを生成する。ここで、クライアント端末ＣＬｉに対応している中間鍵Ｒｉは、端末番号に対応している中間鍵である。
【００５３】
続いて、図４及び図５を参照して、共通鍵生成システム１における処理の流れを説明する。
図４は、本実施形態に係るサーバＳＶに係る処理の流れを示すフローチャートである。
【００５４】
ステップＳ１において、サーバ側制御部１０（サーバ側鍵情報生成部１１０）は、基数Ｂ、除数Ｄ、及びＮ個の秘密鍵Ｓを生成する。
【００５５】
ステップＳ２において、サーバ側制御部１０（サーバ側中間鍵生成部１３０）は、ステップＳ１において生成された基数Ｂ、Ｎ個の秘密鍵Ｓ及び除数Ｄに基づいて、中間鍵Ｒを生成する。具体的には、サーバ側制御部１０（サーバ側中間鍵生成部１３０）は、Ｎ個の秘密鍵Ｓそれぞれについて、基数Ｂを底とし、当該秘密鍵を指数とした冪乗を、除数Ｄで除算した場合に得られるＮ個の剰余を中間鍵Ｒとする。詳細な処理は、図６に示すフローチャートで説明する。
【００５６】
ステップＳ３において、サーバ側制御部１０（サーバ側通信制御部１４０）は、除数Ｄを送信済みではないクライアント端末ＣＬのうち、いずれか一のクライアント端末ＣＬに、除数Ｄ及び中間鍵Ｒを送信する。
【００５７】
ステップＳ４において、サーバ側制御部１０（サーバ側中間鍵更新部１５０）は、サーバ側受信部１５によって中間鍵Ｒを受信したか否かを判定する。サーバ側制御部１０（サーバ側中間鍵更新部１５０）は、この判定がＹＥＳの場合、ステップＳ５に処理を移し、この判定がＮＯの場合、ステップＳ４の処理を再実行する。
【００５８】
ステップＳ５において、サーバ側制御部１０（サーバ側中間鍵更新部１５０）は、置換回数がＮ−１回であるか否かを判定する。サーバ側制御部１０（サーバ側中間鍵更新部１５０）は、この判定がＹＥＳの場合、ステップＳ９に処理を移し、この判定がＮＯの場合、ステップＳ６に処理を移す。
【００５９】
ステップＳ６において、サーバ側制御部１０（サーバ側中間鍵更新部１５０）は、秘密鍵Ｓの内容を置換する。具体的には、秘密鍵シフト部１６は、秘密鍵Ｓｉの値（ｉ＝１、２、・・・Ｎ−１）を秘密鍵Ｓｉ＋１の値に置換する。また、サーバ側制御部１０（サーバ側中間鍵更新部１５０）は、秘密鍵ＳＮの値を秘密鍵Ｓ１の値に置換する。
【００６０】
ステップＳ７において、サーバ側制御部１０（サーバ側中間鍵更新部１５０）は、秘密鍵Ｓの内容を置換した回数を置換回数としてサーバ側記憶部１１に記憶させる。
【００６１】
ステップＳ８において、サーバ側制御部１０（サーバ側中間鍵更新部１５０）は、中間鍵Ｒを更新する。具体的には、サーバ側制御部１０（サーバ側中間鍵更新部１５０）は、ステップＳ７において秘密鍵Ｓがシフトされたことに応じて、Ｎ個の中間鍵Ｒそれぞれについて、当該中間鍵Ｒを底とし、当該中間鍵Ｒに対応する秘密鍵を指数とした冪乗を、除数Ｄで除算した場合の剰余を当該中間鍵Ｒに置き換えることで、中間鍵Ｒを更新する。詳細な処理は、図６に示すフローチャートで説明する。サーバ側制御部１０（サーバ側中間鍵更新部１５０）は、この処理が終了すると、ステップＳ３に処理を移す。
【００６２】
ステップＳ９において、サーバ側制御部１０（サーバ側通信制御部１４０）は、全てのクライアント端末ＣＬに中間鍵Ｒを送信する。
【００６３】
図５は、本実施形態に係るクライアント端末ＣＬｉに係る処理の流れを示すフローチャートである。
【００６４】
ステップＳ１１において、端末側制御部２０（端末側通信制御部２１０）は、サーバＳＶから中間鍵Ｒを受信したか否かを判定する。端末側制御部２０（端末側通信制御部２１０）は、この判定がＹＥＳの場合、ステップＳ１２に処理を移し、この判定がＮＯの場合、ステップＳ１１を再実行する。
【００６５】
ステップＳ１２において、端末側制御部２０（端末側通信制御部２１０）は、中間鍵Ｒと共に除数Ｄを受信したか否かを判定する。端末側制御部２０（端末側通信制御部２１０）は、この判定がＹＥＳの場合、ステップＳ１３に処理を移し、この判定がＮＯの場合、ステップＳ１６に処理を移す。
【００６６】
ステップＳ１３において、端末側制御部２０（私有鍵生成部２２０）は、私有鍵Ｐｉを生成する。
【００６７】
ステップＳ１４において、端末側制御部２０（端末側中間鍵更新部２４０）は、クライアント端末ＣＬｉに対応している中間鍵Ｒｉを除いたＮ−１個の中間鍵Ｒについて、当該中間鍵Ｒを底とし、私有鍵Ｐｉを指数とした冪乗を、除数Ｄで除算した場合の剰余を当該中間鍵Ｒに置き換えることで、中間鍵Ｒを更新する。詳細な処理は、図６に示すフローチャートで説明する。
【００６８】
ステップＳ１５において、端末側制御部２０（端末側通信制御部２１０）は、更新した中間鍵ＲをサーバＳＶに送信する。この処理が終了すると、端末側制御部２０（端末側通信制御部２１０）は、ステップＳ１１に処理を移す。
【００６９】
ステップＳ１６において、端末側制御部２０（共通鍵生成部２５０）は、クライアント端末ＣＬｉに対応している中間鍵Ｒｉを抽出する。
【００７０】
ステップＳ１７において、端末側制御部２０（共通鍵生成部２５０）は、クライアント端末ＣＬｉに対応している中間鍵Ｒｉを底とし、私有鍵Ｐｉを指数とした冪乗を、除数Ｄで除算した場合の剰余を共通鍵Ｃとすることによって、共通鍵Ｃを生成する。詳細な処理は、図６に示すフローチャートで説明する。
【００７１】
図６は、本実施形態に係る冪剰余算出部１２０及び冪剰余算出部２３０における処理の流れを示すフローチャートである。このフローチャートに示す処理は、図４のステップＳ２、ステップＳ８、図５のステップＳ１４、ステップＳ１７に利用される。
【００７２】
ステップＳ２１において、入力受付部１２１（入力受付部２３１）は、底、除数、指数の入力を受け付ける。ここで受け付けた底を底Ａｉとし、除数を除数Ｂとし、指数を指数ｅとする。
【００７３】
ステップＳ２２において、初期設定部１２２（初期設定部２３２）は、第１中間値ＡＴの初期値をステップＳ２１において受け付けた底Ａｉとし、第２中間値ＭＴの初期値を１に設定する。
【００７４】
ステップＳ２３において、変換部１２３（変換部２３３）は、ステップＳ２１において受け付けた指数ｅを、２進数に変換する。
【００７５】
ステップＳ２４において、計数部１２４（計数部２３４）は、ステップＳ２３において変換された、２進数で表現された指数ｅのビット数を計数する。
【００７６】
ステップＳ２５において、基数算出部１２５（基数算出部２３５）は、第１中間値ＡＴを更新する。具体的には、基数算出部１２５（基数算出部２３５）は、２進数で表現された指数ｅの右端の値（ビット）が１である場合、第１中間値ＡＴを第２中間値ＭＴで乗算して得られた値を除数Ｂｉで除算して剰余を算出する。続いて、基数算出部１２５（基数算出部２３５）は、この算出された剰余を第１中間値ＡＴとすることにより、第１中間値ＡＴを更新する。ここで、基数算出部１２５（基数算出部２３５）により行われる第１中間値ＡＴと第２中間値ＭＴとの乗算は、第１中間値ＡＴ及び第２中間値ＭＴそれぞれを１０のべき乗の和に変換し、この変換した第１中間値ＡＴ及び第２中間値ＭＴを乗算することで行われる。
【００７７】
ステップＳ２６において、剰余算出部１２６（剰余算出部２３６）は、第２中間値ＭＴを更新する。具体的には、剰余算出部１２６（剰余算出部２３６）は、２進数に変換された指数ｅの右端の値（ビット）にかかわらず、第１中間値ＡＴを２乗した値を除数Ｂｉで除算した場合の剰余を第２中間値ＭＴとすることにより、第２中間値ＭＴを更新する。なお、第１中間値ＡＴの２乗の計算は、第１中間値ＡＴと第２中間値ＭＴとの乗算と同様に、第１中間値ＡＴを１０のべき乗の和に変換し、この変換した第１中間値ＡＴを２乗することにより計算される。
【００７８】
ステップＳ２７において、シフト部１２７（シフト部２３７）は、２進数に変換された指数ｅを１ビット右に論理シフトする演算（論理シフト演算）を行う。
【００７９】
ステップＳ２８において、反復実行部１２８（反復実行部２３８）は、ステップＳ２５〜ステップＳ２７の処理が、反復回数行われたか判定する。ここで、反復回数は、ステップＳ２４において計数された値である。反復実行部１２８（反復実行部２３８）は、この判定がＹＥＳの場合、処理をステップＳ２９に移し、この判定がＮＯの場合、処理をステップＳ２５に移す。
【００８０】
ステップＳ２９において、出力部１２９（出力部２３９）は、第２中間値ＭＴを剰余として出力する。
【００８１】
以上、本実施形態によれば、サーバＳＶは、サーバ側鍵情報生成部１１０により、１個の基数Ｂ、１個の除数Ｄ及びＮ個の秘密鍵Ｓを生成し、サーバ側中間鍵生成部１３０により、Ｎ個の秘密鍵Ｓそれぞれについて、基数Ｂを底とし、当該秘密鍵を指数とした冪乗に対して除数Ｄで除算した場合に生成されるＮ個の剰余をＮ個の中間鍵Ｒとし、サーバ側通信制御部１４０により、生成されたＮ個の中間鍵Ｒの送受信を行う。
【００８２】
また、サーバＳＶは、サーバ側中間鍵更新部１５０により、クライアント端末ＣＬｉからＮ個の中間鍵Ｒをサーバ側通信制御部１４０によって受信したことに応じて、Ｎ個の秘密鍵Ｓそれぞれについて、ｉ番目の秘密鍵Ｓｉ（ｉは１からＮ−１のいずれか）をｉ＋１番目の秘密鍵Ｓｉ＋１に置換すると共にＮ番目の秘密鍵ＳＮを１番目の秘密鍵Ｓ１に置換することで、他の秘密鍵の値に置換し、受信したＮ個の中間鍵Ｒそれぞれについて、当該中間鍵を底とし、置換されたＮ個の秘密鍵のうち当該中間鍵に対応する秘密鍵を指数とした場合の剰余を除数Ｄで除算した場合に生成されるＮ個の剰余をＮ個の中間鍵Ｒとすることにより、Ｎ個の中間鍵Ｒを更新する。また、サーバは、サーバ側通信制御部１４０により、クライアント端末からＮ個の中間鍵Ｒを受信した場合にＮ個の中間鍵Ｒが置換された回数がＮ−１回であるとき、Ｎ台のクライアント端末ＣＬ全てに対してＮ個の中間鍵Ｒを送信する。
【００８３】
また、Ｎ台のクライアント端末ＣＬそれぞれ（クライアント端末ＣＬｉ）は、端末側通信制御部２１０によりサーバＳＶから除数Ｄを受信すると共にＮ個の中間鍵Ｒの送受信を行い、私有鍵生成部２２０により、除数Ｄ及びＮ個の中間鍵Ｒを受信したことに応じて、私有鍵Ｐｉを生成する。また、クライアント端末ＣＬｉは、端末側中間鍵更新部２４０により、私有鍵生成部２２０により私有鍵Ｐｉを生成したことに応じて、当該クライアント端末ＣＬｉに対応する中間鍵の値を変更せずに更新したとみなすと共に、当該中間鍵以外のＮ−１個の中間鍵それぞれについて、当該中間鍵を底とし、当該私有鍵Ｐｉを指数とした冪乗に対して除数Ｄで除算した場合に生成されるＮ個の剰余をＮ個の中間鍵Ｒとすることにより、中間鍵Ｒを更新する。また、クライアント端末ＣＬｉは、共通鍵生成部２５０により、端末側通信制御部２１０によりＮ個の中間鍵Ｒのみを受信したことに応じて、当該クライアント端末ＣＬｉに対応する中間鍵を底とし、私有鍵Ｐｉを指数とした冪乗に対して除数Ｄで除算した場合に生成される剰余を共通鍵Ｃとする。
【００８４】
例えば、Ｎ＝２であり、秘密鍵Ｓ１の値がａ、秘密鍵Ｓ２の値がｂである場合、１番目の中間鍵Ｒ１は、サーバＳＶにより、（３）式のようにして生成される。ここで、Ｘ１は、基数Ｂを底とし秘密鍵Ｓ１に対応するａを指数とした冪乗を除数Ｄで除算した場合の商とする。
【数３】
0005340347.tif 000004
【００８５】
続いて、中間鍵Ｒ１は、クライアント端末ＣＬ１に送信された場合、中間鍵Ｒ１の値は変化せずに、サーバＳＶに送信される。続いて、中間鍵Ｒ１は、サーバＳＶにより、（４）式のようにして更新される。なお、ここでは更新された中間鍵をＲ１’とする。また、Ｘ２は、中間鍵Ｒ１’を底とし置換された秘密鍵Ｓ１の値であるｂを指数とした冪乗を除数Ｄで除算した場合の商とする。
【数４】
0005340347.tif 000005
【００８６】
続いて、中間鍵Ｒ１’は、クライアント端末ＣＬ２に送信された場合、（５）式に示すようにして更新される。なお、ここでは更新された中間鍵をＲ１’’とする。また、Ｘ３は、中間鍵Ｒ１’を底とし私有鍵Ｐ２を指数とした冪乗を除数Ｄで除算した場合の商とする。
【数５】
0005340347.tif 000006
【００８７】
続いて、中間鍵Ｒ１’’は、サーバＳＶに送信された後、更新されずにクライアント端末ＣＬ１に送信され、共通鍵Ｃの生成に使用される。すなわち、クライアント端末ＣＬ１において共通鍵Ｃは、（６）式に示すようにして更新される。
【数６】
0005340347.tif 000007
ただし、Ｘ４は、更新された中間鍵Ｒ１’を底とし私有鍵Ｐ１を指数とした冪乗を除数Ｄで除算した場合の商とする。
【００８８】
一方、２番目の中間鍵Ｒ２は、サーバＳＶにより、（７）式のようにして生成される。ここで、Ｘ５は、基数Ｂを底とし秘密鍵Ｓ２に対応するｂを指数とした冪乗を除数Ｄで除算した場合の商とする。
【数７】
0005340347.tif 000008
【００８９】
続いて、中間鍵Ｒ２は、クライアント端末ＣＬ１に送信された場合、（８）式に示すようにして更新される。なお、ここでは更新された中間鍵をＲ２’とする。また、Ｘ６は、中間鍵Ｒ２を底とし私有鍵Ｐ１を指数とした冪乗を除数Ｄで除算した場合の商とする。
【数８】
0005340347.tif 000009
【００９０】
続いて、中間鍵Ｒ２’は、サーバＳＶに送信される。続いて、中間鍵Ｒ２’は、サーバＳＶにより、（９）式のようにして更新される。ここでは更新された中間鍵をＲ２’’とする。また、Ｘ７は、中間鍵Ｒ１’を底とし置換された秘密鍵Ｓ２の値であるａを指数とした冪乗を除数Ｄで除算した場合の商とする。
【数９】
0005340347.tif 000010
【００９１】
続いて、中間鍵Ｒ２’’は、クライアント端末ＣＬ２に送信された場合、変化せずに、サーバＳＶに送信される。続いて、中間鍵Ｒ２’’は、サーバＳＶに送信された後、更新されずにクライアント端末ＣＬ２に送信され、共通鍵Ｃの生成に使用される。すなわち、クライアント端末ＣＬ２において共通鍵Ｃは、（１０）式に示すようにして更新される。ただし、Ｘ８は、更新された中間鍵Ｒ２’’を底とし私有鍵Ｐ２を指数とした冪乗を除数Ｄで除算した場合の商とする。
【数１０】
0005340347.tif 000011
【００９２】
以上のように、サーバＳＶ、クライアント端末ＣＬ１、ＣＬ２の間では、基数Ｂに対してａ、ｂ、Ｐ１、Ｐ２を指数とした冪乗が行われることによって、共通鍵Ｃが生成される。この場合に、同一の基数Ｂについてａ、ｂ、Ｐ１、Ｐ２それぞれを指数として除数Ｄで除算した場合の剰余は、ａ、ｂ、Ｐ１、Ｐ２をどの順番で指数とした場合でも同一の結果となることが知られている。よって、この法則を利用すれば、クライアント端末の台数をＮ台とした場合であっても、本実施形態で説明した処理を行うことによって、クライアント端末ＣＬにおいて、共通鍵Ｃを生成することができる。
【００９３】
以上によれば、共通鍵生成システム１では、Ｎ台のクライアント端末ＣＬが、共通鍵の受け渡しを行うことなく共通鍵を生成することができる。ここで、除数Ｄを桁数が大きい自然数である場合、中間鍵Ｒ、除数Ｄが知られたとしても、これらの値のみから、共通鍵Ｃを求めるには、膨大な計算量が必要となる。したがって、共通鍵生成システムは、三者以上の間で安全に共通鍵を共有することができる。
【００９４】
以上、本発明の実施形態について説明したが、本発明は本実施形態に限定されるものではなく、本発明の目的を達成できる範囲での変形、改良等は本発明に含まれるものである。
【符号の説明】
【００９５】
１  共通鍵生成システム
ＳＶ  サーバ
ＣＬ  クライアント端末
１０  サーバ側制御部
２０  端末側制御部
１１０  サーバ側鍵情報生成部
１２０  冪剰余算出部
１３０  サーバ側中間鍵生成部
１４０  サーバ側通信制御部
１５０  サーバ側中間鍵更新部
２１０  端末側通信制御部
２２０  私有鍵生成部
２３０  冪剰余算出部
２４０  端末側中間鍵更新部
２５０  共通鍵生成部
【図１】
0005340347.tif 000012
【図２】
0005340347.tif 000013
【図３】
0005340347.tif 000014
【図４】
0005340347.tif 000015
【図５】
0005340347.tif 000016
【図６】
0005340347.tif 000017