サーバと、N台のクライアント端末とが通信可能に接続された共通鍵生成システムであって、前記サーバは、1個の基数、1個の除数及びN個の秘密鍵を生成するサーバ側鍵情報生成手段と、前記N個の秘密鍵それぞれについて、基数を底とし、当該秘密鍵を指数とした冪乗に対して前記除数で除算した場合に生成されるN個の剰余をN個の中間鍵とするサーバ側中間鍵生成手段と、前記N台のクライアント端末と前記N個の中間鍵の送受信を行うサーバ側通信制御手段と、前記クライアント端末からN個の中間鍵を前記サーバ側通信制御手段によって受信したことに応じて、N個の秘密鍵それぞれについて他の秘密鍵の値に置換し、受信したN個の中間鍵それぞれについて、当該中間鍵を底とし、置換されたN個の秘密鍵のうち当該中間鍵に対応する秘密鍵を指数とした場合の剰余を前記除数で除算した場合に生成されるN個の剰余をN個の中間鍵とすることにより、N個の中間鍵を更新するサーバ側中間鍵更新手段と、を備え、前記N台のクライアント端末それぞれは、前記サーバから前記除数を受信すると共に前記N個の中間鍵の送受信を行う端末側通信制御手段と、前記端末側通信制御手段により前記除数及び前記N個の中間鍵を受信したことに応じて、私有鍵を生成する私有鍵生成手段と、前記私有鍵生成手段により前記私有鍵を生成したことに応じて、前記クライアント端末に対応する中間鍵の値を変更せずに更新したとみなすと共に、当該中間鍵以外のN-1個の中間鍵それぞれについて、当該中間鍵を底とし、当該私有鍵を指数とした冪乗に対して前記除数で除算した場合に生成されるN個の剰余を前記N個の中間鍵とすることにより、N個の中間鍵を更新する端末側中間鍵更新手段と、前記端末側通信制御手段により前記N個の中間鍵のみを受信したことに応じて、前記クライアント端末に対応する中間鍵を底とし、前記私有鍵を指数とした冪乗に対して前記除数で除算した場合に生成される剰余を共通鍵とする共通鍵生成手段と、を備え、前記サーバ側中間鍵更新手段は、N個の秘密鍵それぞれについて、i番目の秘密鍵iは1からN-1のいずれかをi1番目の秘密鍵に置換すると共にN番目の秘密鍵を1番目の秘密鍵に置換することで、前記他の秘密鍵の値に置換し、前記サーバ側通信制御手段は、前記サーバ側中間鍵更新手段により前記N個の中間鍵を更新したことに応じて前記クライアント端末に当該N個の中間鍵を送信し、前記クライアント端末から前記N個の中間鍵を受信した場合に前記N個の中間鍵が置換された回数がN-1回であるとき、N台のクライアント端末全てに対して前記N個の中間鍵を送信する、共通鍵生成システム。サーバと、N台のクライアント端末とが通信可能に接続された共通鍵生成システムにおいて共通鍵を生成する方法であって、前記サーバが、1個の基数、1個の除数及びN個の秘密鍵を生成するサーバ側鍵生成ステップと、前記N個の秘密鍵それぞれについて、前記基数を底とし、当該秘密鍵を指数とした冪乗に対して前記除数で除算した場合に生成されるN個の剰余をN個の中間鍵としてN個の中間鍵を生成するサーバ側中間鍵生成ステップと、前記N台のクライアント端末のうち、前記除数を送信していない、いずれか1のクライアント端末に前記N個の中間鍵を送信する第1サーバ側送信ステップと、前記クライアント端末それぞれが、前記サーバから前記除数及び前記N個の中間鍵を受信する第1端末側受信ステップと、前記第1端末側受信ステップにおいて前記除数及び前記N個の中間鍵を受信したことに応じて私有鍵を生成する私有鍵生成ステップと、前記私有鍵生成ステップにおいて前記私有鍵が生成されたことに応じて、前記クライアント端末に対応する中間鍵の値を変更せずに更新したとみなすと共に、当該中間鍵以外のN-1個の中間鍵それぞれについて、当該中間鍵を底とし、当該私有鍵を指数とした冪乗に対して前記除数で除算した場合に生成されるN個の剰余を前記N個の中間鍵とすることにより、N個の中間鍵を更新する端末側中間鍵更新ステップと、前記端末側中間鍵更新ステップにおいて前記N個の中間鍵が更新されたことに応じて当該N個の中間鍵を前記サーバに送信する端末側送信ステップと、を含み、前記サーバは、前記クライアント端末から、N個の中間鍵を受信するサーバ側受信ステップと、前記サーバ側受信ステップにおいて前記N個の中間鍵を受信したことに応じて、N個の秘密鍵それぞれについて、i番目の秘密鍵iは1からN-1のいずれかをi1番目の秘密鍵に置換すると共にN番目の秘密鍵を1番目の秘密鍵に置換することで、他の秘密鍵の値に置換する置換ステップと、前記置換ステップにおいて前記N個の秘密鍵が置換されたことに応じて、前記サーバ側受信ステップにおいて受信したN個の中間鍵それぞれについて、当該中間鍵を底とし、置換されたN個の秘密鍵のうち当該中間鍵に対応する秘密鍵を指数とした場合の剰余を前記除数で除算した場合に生成されるN個の剰余をN個の中間鍵とすることにより、N個の中間鍵を更新するサーバ側中間鍵更新ステップと、前記サーバ側中間鍵更新ステップにより更新されたN個の中間鍵を、前記除数を送信していない、いずれか1のクライアント端末に前記N個の中間鍵を送信する第2サーバ側送信ステップと、前記サーバ側受信ステップにおいて、前記クライアント端末から前記N個の中間鍵を受信した場合に前記N個の中間鍵が置換された回数がN-1回であるとき、N台のクライアント端末全てに対して前記N個の中間鍵を送信する第3サーバ側送信ステップを更に含み、前記クライアント端末は、前記サーバから前記N個の中間鍵のみ受信する第2端末側受信ステップと、前記第2端末側受信ステップにおいて前記N個の中間鍵のみ受信したことに応じて、記クライアント端末に対応する中間鍵を底とし、前記私有鍵を指数とした冪乗に対して前記除数で除算した場合に生成される剰余を共通鍵とする共通鍵生成ステップと、を更に含む、共通鍵生成方法。しかしながら、特許文献1に示される共通鍵交換方式は、2者間において共通鍵を生成する方式であり、三者以上の間において、共通鍵を生成する方法については示されていない。このため、三者以上の間において、安全に共通鍵を生成することができる共通鍵生成システム及び共通鍵生成方法の提供が望まれている。本発明は、共通鍵の受け渡しを行わずに、三者以上の間で安全に共通鍵を共有することができる共通鍵生成システム及び共通鍵生成方法を提供することを目的とする。本発明に係る共通鍵生成システムは、サーバと、N台のクライアント端末とが通信可能に接続された共通鍵生成システムであって、前記サーバは、1個の基数、1個の除数及びN個の秘密鍵を生成するサーバ側鍵情報生成手段と、前記N個の秘密鍵それぞれについて、基数を底とし、当該秘密鍵を指数とした冪乗に対して前記除数で除算した場合に生成されるN個の剰余をN個の中間鍵とするサーバ側中間鍵生成手段と、前記N台のクライアント端末と前記N個の中間鍵の送受信を行うサーバ側通信制御手段と、前記クライアント端末からN個の中間鍵を前記サーバ側通信制御手段によって受信したことに応じて、N個の秘密鍵それぞれについて他の秘密鍵の値に置換し、受信したN個の中間鍵それぞれについて、当該中間鍵を底とし、置換されたN個の秘密鍵のうち当該中間鍵に対応する秘密鍵を指数とした場合の剰余を前記除数で除算した場合に生成されるN個の剰余をN個の中間鍵とすることにより、N個の中間鍵を更新するサーバ側中間鍵更新手段と、を備え、前記N台のクライアント端末それぞれは、前記サーバから前記除数を受信すると共に前記N個の中間鍵の送受信を行う端末側通信制御手段と、前記端末側通信制御手段により前記除数及び前記N個の中間鍵を受信したことに応じて、私有鍵を生成する私有鍵生成手段と、前記私有鍵生成手段により前記私有鍵を生成したことに応じて、前記クライアント端末に対応する中間鍵の値を変更せずに更新したとみなすと共に、当該中間鍵以外のN-1個の中間鍵それぞれについて、当該中間鍵を底とし、当該私有鍵を指数とした冪乗に対して前記除数で除算した場合に生成されるN個の剰余を前記N個の中間鍵とすることにより、N個の中間鍵を更新する端末側中間鍵更新手段と、前記端末側通信制御手段により前記N個の中間鍵のみを受信したことに応じて、前記クライアント端末に対応する中間鍵を底とし、前記私有鍵を指数とした冪乗に対して前記除数で除算した場合に生成される剰余を共通鍵とする共通鍵生成手段と、を備え、前記サーバ側中間鍵更新手段は、N個の秘密鍵それぞれについて、i番目の秘密鍵iは1からN-1のいずれかをi1番目の秘密鍵に置換すると共にN番目の秘密鍵を1番目の秘密鍵に置換することで、前記他の秘密鍵の値に置換し、前記サーバ側通信制御手段は、前記サーバ側中間鍵更新手段により前記N個の中間鍵を更新したことに応じて前記クライアント端末に当該N個の中間鍵を送信し、前記クライアント端末から前記N個の中間鍵を受信した場合に前記N個の中間鍵が置換された回数がN-1回であるとき、N台のクライアント端末全てに対して前記N個の中間鍵を送信する。本発明に係る共通鍵生成方法は、サーバと、N台のクライアント端末とが通信可能に接続された共通鍵生成システムにおいて共通鍵を生成する方法であって、前記サーバが、1個の基数、1個の除数及びN個の秘密鍵を生成するサーバ側鍵生成ステップと、前記N個の秘密鍵それぞれについて、前記基数を底とし、当該秘密鍵を指数とした冪乗に対して前記除数で除算した場合に生成されるN個の剰余をN個の中間鍵としてN個の中間鍵を生成するサーバ側中間鍵生成ステップと、前記N台のクライアント端末のうち、前記除数を送信していない、いずれか1のクライアント端末に前記N個の中間鍵を送信する第1サーバ側送信ステップと、前記クライアント端末それぞれが、前記サーバから前記除数及び前記N個の中間鍵を受信する第1端末側受信ステップと、前記第1端末側受信ステップにおいて前記除数及び前記N個の中間鍵を受信したことに応じて私有鍵を生成する私有鍵生成ステップと、前記私有鍵生成ステップにおいて前記私有鍵が生成されたことに応じて、前記クライアント端末に対応する中間鍵の値を変更せずに更新したとみなすと共に、当該中間鍵以外のN-1個の中間鍵それぞれについて、当該中間鍵を底とし、当該私有鍵を指数とした冪乗に対して前記除数で除算した場合に生成されるN個の剰余を前記N個の中間鍵とすることにより、N個の中間鍵を更新する端末側中間鍵更新ステップと、前記端末側中間鍵更新ステップにおいて前記N個の中間鍵が更新されたことに応じて当該N個の中間鍵を前記サーバに送信する端末側送信ステップと、を含み、前記サーバは、前記クライアント端末から、N個の中間鍵を受信するサーバ側受信ステップと、前記サーバ側受信ステップにおいて前記N個の中間鍵を受信したことに応じて、N個の秘密鍵それぞれについて、i番目の秘密鍵iは1からN-1のいずれかをi1番目の秘密鍵に置換すると共にN番目の秘密鍵を1番目の秘密鍵に置換することで、他の秘密鍵の値に置換する置換ステップと、前記置換ステップにおいて前記N個の秘密鍵が置換されたことに応じて、前記サーバ側受信ステップにおいて受信したN個の中間鍵それぞれについて、当該中間鍵を底とし、置換されたN個の秘密鍵のうち当該中間鍵に対応する秘密鍵を指数とした場合の剰余を前記除数で除算した場合に生成されるN個の剰余をN個の中間鍵とすることにより、N個の中間鍵を更新するサーバ側中間鍵更新ステップと、前記サーバ側中間鍵更新ステップにより更新されたN個の中間鍵を、前記除数を送信していない、いずれか1のクライアント端末に前記N個の中間鍵を送信する第2サーバ側送信ステップと、前記サーバ側受信ステップにおいて、前記クライアント端末から前記N個の中間鍵を受信した場合に前記N個の中間鍵が置換された回数がN-1回であるとき、N台のクライアント端末全てに対して前記N個の中間鍵を送信する第3サーバ側送信ステップを更に含み、前記クライアント端末は、前記サーバから前記N個の中間鍵のみ受信する第2端末側受信ステップと、前記第2端末側受信ステップにおいて前記N個の中間鍵のみ受信したことに応じて、記クライアント端末に対応する中間鍵を底とし、前記私有鍵を指数とした冪乗に対して前記除数で除算した場合に生成される剰余を共通鍵とする共通鍵生成ステップと、を更に含む。本発明によれば、共通鍵の受け渡しを行わずに、三者以上の間で安全に共通鍵を共有することができる。以下、本発明の実施形態について図を参照しながら説明する。[機能構成]図1は、本実施形態に係る共通鍵生成システム1の全体概要を示す図である。共通鍵生成システム1は、複数のクライアント端末それぞれで共通鍵を生成するシステムである。共通鍵生成システム1は、サーバSVと、N台のクライアント端末CL1、CL2、CLNとを備える。ここで、N台のクライアント端末CL1、CL2、CLNをまとめて、クライアント端末CLとする。サーバSVと、N台のクライアント端末CLとは、LANLocalAreaNetworkやインターネット等のコンピュータネットワークにより構成される通信ネットワークNにより、通信可能に接続されている。このサーバSVでは、基数B、除数D、及びN個の秘密鍵S1、S2、SN以下、N個の秘密鍵をまとめて秘密鍵Sともいうを生成し、基数B、除数D、及び秘密鍵Sに基づいてN個の中間鍵Rを生成し、クライアント端末CLに、除数D、及び中間鍵Rを送信する。また、クライアント端末CLでは、除数D及び中間鍵Rを受信すると共に私有鍵Pを生成し、中間鍵Rを更新して、中間鍵RをサーバSVに送信する。サーバSVでは、その後、秘密鍵Sをシフトすると共に、中間鍵Rを更新し、全てのクライアント端末CLと中間鍵の送受信を繰り返す。その後、サーバSVは、全てのクライアント端末CLに対して中間鍵Rを送信する。その後、N台のクライアント端末CLは、除数D、私有鍵P及び中間鍵Rから共通鍵Cを生成する。本実施形態における各部は、コンピュータ及びその周辺装置が備えるハードウェア並びにこのハードウェアを制御するソフトウェアによって構成される。図2は、本実施形態に係るサーバSVの機能構成を示す図である。サーバSVは、コンピュータであり、サーバ側制御部10と、サーバ側記憶部11と、サーバ側通信部12と、サーバ側表示部13と、サーバ側入力部14とを備える。サーバ側制御部10は、CPU等により構成されており、サーバSVの全体を制御する。サーバ側制御部10の詳細な機能については、後述する。サーバ側記憶部11は、メモリRAM、ROM等、ハードディスクドライブHDD及び光ディスクCD、DVD等ドライブ等により構成されており、サーバSVをコンピュータとして動作させるための各種プログラムやデータを記憶する。サーバ側通信部12は、各種有線及び無線インターフェース装置等により構成され、クライアント端末CLと通信を行う。サーバ側表示部13は、液晶ディスプレイ、プラズマディスプレイ等の各種ディスプレイにより構成され、各種機能に係る情報を表示する。サーバ側入力部14は、キーボード及びマウス等により構成され、操作者からの操作を受け付ける。サーバ側制御部10は、サーバ側鍵情報生成手段としてのサーバ側鍵情報生成部110と、第1冪剰余算出手段としての冪剰余算出部120と、サーバ中間鍵生成手段としてのサーバ側中間鍵生成部130と、サーバ側通信制御手段としてのサーバ側通信制御部140と、サーバ側中間鍵更新手段としてのサーバ側中間鍵更新部150と、を備える。サーバ側鍵情報生成部110は、共通鍵を生成する情報となる1個の基数B、1個の除数Dを生成する。具体的には、サーバ側鍵情報生成部110は、基数Bとして任意の自然数を生成し、除数Dとして、桁数が大きい自然数例えば、20桁以上の自然数を生成する。また、サーバ側鍵情報生成部110は、N個の秘密鍵S1、S2、SNとして、1以上であり、それぞれが異なる同一でもよい自然数を生成する。N個の秘密鍵それぞれには、番号が付されている。具体的には、秘密鍵S1には1、S2には2、Siにはiというように番号が付されている。ここで、Siをi番目の秘密鍵という。サーバ側鍵情報生成部110は、生成された基数B、除数D、及びN個の秘密鍵Sをサーバ側記憶部11に記憶させる。冪剰余算出部120は、底、除数、及び指数の入力を受け付け、この底の指数乗を、除数で除算した場合の剰余を算出し、この算出した剰余を出力する。冪剰余算出部120は、入力受付手段としての入力受付部121と、初期設定手段としての初期設定部122と、変換手段としての変換部123と、計数手段としての計数部124と、基数算出手段としての基数算出部125と、剰余算出手段としての剰余算出部126と、シフト手段としてのシフト部127と、反復実行手段としての反復実行部128と、出力手段としての出力部129と、を備える。また、冪剰余算出部120は、第1中間値ATと、第2中間値MTとを有する。入力受付部121は、底、除数、及び指数の入力を受け付ける。ここで、入力受付部121により受け付けられた底、除数、及び指数を、それぞれ底Ai、除数Bi、指数eとする。初期設定部122は、第1中間値ATの初期値を底Aiとし、第2中間値MTの初期値を1に設定する。変換部123は、指数eを、10進数から2進数に変換する。計数部124は、変換部123により2進数に変換された指数eのビット数を計数する。基数算出部125は、2進数で表現された指数eの右端の値ビットが1である場合、第1中間値ATを第2中間値MTで乗算して得られた値を除数Biで除算した場合の剰余を第1中間値ATとすることにより、第1中間値ATを更新する。なお、第1中間値ATと第2中間値MTとの乗算は、以下のように行われる。すなわち、基数算出部125は、第1中間値AT及び第2中間値MTを、以下の1式に示すように、複数桁例えば、1桁目~5桁目、6桁目~10桁目等、5桁ずつに区切り、10の冪乗により構成される多項式、すなわち、初項を10の冪乗例えば10の5乗の0乗、公比を当該10の冪乗例えば10の5乗とした数列の和で表される多項式に変換する。ここで、a1...amは、第1中間値ATを満たすためにそれぞれの項に付される係数であり、b1...bnは、第2中間値MTを満たすためにそれぞれの項に付される係数である。続いて、基数算出部125は、10の冪乗の和に変換された第1中間値AT及び第2中間値MTの多項式を乗算して、2式に示すように展開する。その後、展開された値に含まれるそれぞれの項を合計することにより、第1中間値ATと第2中間値MTとを乗算した値を算出する。剰余算出部126は、2進数に変換された指数eの右端の値ビットにかかわらず、第1中間値ATを2乗した値を除数Biで除算した場合の剰余を第2中間値MTとすることにより、第2中間値MTを更新する。なお、第1中間値ATの2乗の計算は、第1中間値ATと第2中間値MTとの乗算と同様に、第1中間値ATを、初項を10の冪乗例えば10の5乗の0乗、公比を当該10の冪乗例えば10の5乗とした数列の和で表される多項式に変換し、この多項式の第1中間値ATを2乗することにより計算される。シフト部127は、2進数に変換された指数eを右シフトする。具体的には、シフト部127は、2進数に変換された指数eを1ビット右に論理シフトする演算論理シフト演算を行う。反復実行部128は、計数部124により計数されたビット数の値を反復回数とし、基数算出部125、剰余算出部126、及びシフト部127に係る処理が、基数算出部125、剰余算出部126、シフト部127の順に、反復回数実行されるように制御する。具体的には、記憶部に初期値を0とするカウンタを設けておき、反復実行部128は、基数算出部125、剰余算出部126、及びシフト部127に係る処理が終了したことに応じて、カウンタに1加算インクリメントする。その後、反復実行部128は、カウンタの値が反復回数に達するまで、基数算出部125、剰余算出部126、シフト部127、インクリメントに係る処理を実行する制御を行い、カウンタの値が反復回数に達した場合に、反復実行を終了する。出力部129は、反復実行部128により、基数算出部125、剰余算出部126、及びシフト部127に係る処理が反復回数実行された後、第2中間値MTを剰余として出力する。サーバ側中間鍵生成部130は、サーバ側鍵情報生成部110によって基数B、除数D、及びN個の秘密鍵Sが生成されたことに応じて、N個の秘密鍵それぞれについて、基数Bを底とし、当該秘密鍵を指数とした冪乗を、除数Dで除算した場合のN個の剰余をN個の中間鍵とすることにより、N個の中間鍵を生成する。まず、サーバ側中間鍵生成部130は、基数Bを底、除数Dを除数、1番目の秘密鍵S1を指数とし、これら底、除数、及び指数を冪剰余算出部120に入力することにより、冪剰余算出部120から、基数Bを底とし、秘密鍵S1を指数とした冪乗を除数Dで除算した場合の剰余を得る。続いて、サーバ側中間鍵生成部130は、得られた剰余を中間鍵R1とする。続いて、サーバ側中間鍵生成部130は、秘密鍵S2、S3、SNについても秘密鍵S1において中間鍵R1を算出した手順と同様の手順で、中間鍵R2、R3、RNを算出する。ここで、生成されたN個の中間鍵R1、R2、RNをまとめて中間鍵Rという。続いて、サーバ側中間鍵生成部130は、生成されたN個の中間鍵Rをサーバ側記憶部11に記憶させる。サーバ側通信制御部140は、サーバ側通信部12を介して各種情報を送受信する。具体的には、サーバ側通信制御部140は、サーバ側鍵情報生成部110により生成された除数Dと、サーバ側中間鍵生成部130により生成されたN個の中間鍵Rとを、N台のクライアント端末CLのうち、いずれか一の端末に送信する。また、サーバ側通信制御部140は、送信するクライアント端末に対して、1からNのうちいずれか1の番号を端末番号として送信する。また、サーバ側通信制御部140は、サーバ側鍵情報生成部110により生成された除数Dとサーバ側中間鍵更新部150により更新された中間鍵Rとを、N台のクライアント端末CLのうち、除数Dを送信していない、いずれか一の端末に送信する。また、サーバ側通信制御部140は、後述の置換回数がN-1回になった場合、サーバ側中間鍵更新部150により更新されたN個の中間鍵RをN台のクライアント端末CLのすべてに送信する。また、サーバ側通信制御部140は、N台のクライアント端末CLから、N台のクライアント端末それぞれで更新された中間鍵Rを受信する。サーバ側中間鍵更新部150は、サーバ側通信制御部140によって、N台のクライアント端末CLのいずれかから中間鍵Rを受信した場合において、サーバ側記憶部11に記憶されている秘密鍵の置換回数がN-1回より小さいとき、秘密鍵Sの内容を置換する。具体的には、サーバ側中間鍵更新部150は、秘密鍵Siの値を他の秘密鍵の値に置換する。すなわち、サーバ側中間鍵更新部150は、iNを除く番目の秘密鍵Siを、i1番目の秘密鍵Si1に置換する。また、サーバ側中間鍵更新部150は、N番目の秘密鍵SNの値を1番目の秘密鍵S1の値に置換する。サーバ側中間鍵更新部150は、N個の秘密鍵Sの内容を置換した回数を置換回数としてサーバ側記憶部11に記憶させる。また、サーバ側中間鍵更新部150は、秘密鍵Sを置換した後、N個の中間鍵Rそれぞれについて、当該中間鍵Rを底とし、当該中間鍵Rに対応する秘密鍵を指数とした冪乗を、除数Dで除算した場合の剰余を当該中間鍵Rに置き換えることで、中間鍵Rを更新する。具体的には、サーバ側中間鍵更新部150は、中間鍵R1を底、除数Dを除数、中間鍵R1に対応する秘密鍵S1を指数とし、これら底、除数、及び指数を冪剰余算出部120に入力することにより、冪剰余算出部120から、中間鍵R1を底とし、秘密鍵S1を指数とした冪乗を除数Dで除算した場合の剰余を得る。続いて、サーバ側中間鍵更新部17は、中間鍵R1の値を得られた剰余の値に置換することで中間鍵R1を更新する。続いて、サーバ側中間鍵更新部150は、中間鍵R2、R3、RNについても、それぞれ対応する秘密鍵S2、S3、SNを指数とし、除数Dとした場合の冪剰余を算出することで、中間鍵R1を算出した手順と同様の手順で、中間鍵R2、R3、RNを更新する。図3は、本実施形態に係るクライアント端末CLiの機能構成を示す図である。ここで、クライアント端末CL1、CL2、CLNの有する機能は同一であるので、クライアント端末CLiiは、1からNの間の任意の数であるの機能構成に図示するものとする。ここで、クライアント端末CLは、私有鍵Pを保有することが可能であり、クライアント端末CLiに対応する私有鍵を、私有鍵Piとする。クライアント端末CLiは、サーバSVと同様にコンピュータであり、端末側制御部20と、端末側記憶部21と、端末側通信部22と、端末側表示部23と、端末側入力部24と、を備える。端末側制御部20は、CPU等により構成されており、クライアント端末CLiの全体を制御する。端末側制御部20の詳細な機能については、後述する。端末側記憶部21は、メモリ、ハードディスクドライブ及び光ディスクドライブ等により構成されており、クライアント端末CLiをコンピュータとして動作させるための各種プログラムやデータを記憶する。端末側通信部22は、各種有線及び無線インターフェース装置等により構成され、サーバSVと通信を行う。端末側表示部23は、液晶ディスプレイ、プラズマディスプレイ等の各種ディスプレイにより構成され、各種機能に係る情報を表示する。端末側入力部24は、キーボード及びマウス等により構成され、操作者からの操作を受け付ける。端末側制御部20は、端末側通信制御手段としての端末側通信制御部210と、私有鍵生成手段としての私有鍵生成部220と、第2冪剰余算出手段としての冪剰余算出部230と、端末側中間鍵更新手段としての端末側中間鍵更新部240と、共通鍵生成手段としての共通鍵生成部250と、を備える。端末側通信制御部210は、端末側通信部22を介して各種情報を送受信する。具体的には、端末側通信制御部210は、サーバSVからN個の中間鍵Rと、除数Dと、端末番号を受信する。また、端末側通信制御部210は、端末側中間鍵更新部240により中間鍵Rが更新されたことに応じて、更新された中間鍵RをサーバSVに送信する。私有鍵生成部220は、端末側通信制御部210によりサーバSVから中間鍵Rを初めて受信した場合に私有鍵Piを生成する。私有鍵Piは、1以上の任意の自然数である。冪剰余算出部230は、サーバSVの冪剰余算出部120と同等の機能を有する。すなわち、冪剰余算出部230は、冪剰余算出部120が備える入力受付部121、初期設定部122、変換部123、計数部124、基数算出部125、剰余算出部126、シフト部127、反復実行部128及び出力部129と同等の機能を有する、入力受付部231、初期設定部232、変換部233、計数部234、基数算出部235、剰余算出部236、シフト部237、反復実行部238及び出力部239を備える。端末側中間鍵更新部240は、端末側通信制御部210によりサーバSVから中間鍵Rを初めて受信し、私有鍵生成部220により私有鍵Piが生成されたことに応じて、当該クライアント端末CLiに対応している中間鍵Riを除いたN-1個の中間鍵Rについて、当該中間鍵Rを底とし、私有鍵Piを指数とした冪乗を、端末側通信制御部210によって受信した除数Dで除算した場合の剰余を当該中間鍵Rに置き換えることで、中間鍵Rを更新する。ここで、クライアント端末CLiに対応している中間鍵Riは、端末番号に対応している中間鍵である。例えば、端末番号が2である場合、中間鍵R2がクライアント端末CLiに対応する。まず、端末側中間鍵更新部240は、中間鍵R1を底、除数Dを除数、私有鍵Piを指数とし、これら底、除数、及び指数を冪剰余算出部230に入力することにより、冪剰余算出部230から、中間鍵R1を底とし、私有鍵Piを指数とした冪乗を除数Dで除算した場合の剰余を得る。続いて、端末側中間鍵更新部240は、中間鍵R1の値を得られた剰余の値に置換することで、中間鍵R1を更新する。続いて、端末側中間鍵更新部240は、中間鍵R2、R3、RNについても、私有鍵Piを指数とし、除数Dとした場合の冪剰余を算出することで、中間鍵R1を算出した手順と同様の手順で、中間鍵R2、R3、RNを更新する。なお、端末側中間鍵更新部240は、中間鍵Riの値を更新しないが、中間鍵Riについても更新されたものとみなす。共通鍵生成部250は、端末側通信制御部210によりサーバSVから中間鍵Rのみを受信したことに応じて、クライアント端末CLiに対応している中間鍵Riを底とし、私有鍵Piを指数とした冪乗を、除数Dで除算した場合の剰余を算出する。そして、共通鍵生成部26は、当該剰余を共通鍵Cとすることで、N台のクライアント端末CLの共通鍵Cを生成する。ここで、クライアント端末CLiに対応している中間鍵Riは、端末番号に対応している中間鍵である。続いて、図4及び図5を参照して、共通鍵生成システム1における処理の流れを説明する。図4は、本実施形態に係るサーバSVに係る処理の流れを示すフローチャートである。ステップS1において、サーバ側制御部10サーバ側鍵情報生成部110は、基数B、除数D、及びN個の秘密鍵Sを生成する。ステップS2において、サーバ側制御部10サーバ側中間鍵生成部130は、ステップS1において生成された基数B、N個の秘密鍵S及び除数Dに基づいて、中間鍵Rを生成する。具体的には、サーバ側制御部10サーバ側中間鍵生成部130は、N個の秘密鍵Sそれぞれについて、基数Bを底とし、当該秘密鍵を指数とした冪乗を、除数Dで除算した場合に得られるN個の剰余を中間鍵Rとする。詳細な処理は、図6に示すフローチャートで説明する。ステップS3において、サーバ側制御部10サーバ側通信制御部140は、除数Dを送信済みではないクライアント端末CLのうち、いずれか一のクライアント端末CLに、除数D及び中間鍵Rを送信する。ステップS4において、サーバ側制御部10サーバ側中間鍵更新部150は、サーバ側受信部15によって中間鍵Rを受信したか否かを判定する。サーバ側制御部10サーバ側中間鍵更新部150は、この判定がYESの場合、ステップS5に処理を移し、この判定がNOの場合、ステップS4の処理を再実行する。ステップS5において、サーバ側制御部10サーバ側中間鍵更新部150は、置換回数がN-1回であるか否かを判定する。サーバ側制御部10サーバ側中間鍵更新部150は、この判定がYESの場合、ステップS9に処理を移し、この判定がNOの場合、ステップS6に処理を移す。ステップS6において、サーバ側制御部10サーバ側中間鍵更新部150は、秘密鍵Sの内容を置換する。具体的には、秘密鍵シフト部16は、秘密鍵Siの値i=1、2、N-1を秘密鍵Si1の値に置換する。また、サーバ側制御部10サーバ側中間鍵更新部150は、秘密鍵SNの値を秘密鍵S1の値に置換する。ステップS7において、サーバ側制御部10サーバ側中間鍵更新部150は、秘密鍵Sの内容を置換した回数を置換回数としてサーバ側記憶部11に記憶させる。ステップS8において、サーバ側制御部10サーバ側中間鍵更新部150は、中間鍵Rを更新する。具体的には、サーバ側制御部10サーバ側中間鍵更新部150は、ステップS7において秘密鍵Sがシフトされたことに応じて、N個の中間鍵Rそれぞれについて、当該中間鍵Rを底とし、当該中間鍵Rに対応する秘密鍵を指数とした冪乗を、除数Dで除算した場合の剰余を当該中間鍵Rに置き換えることで、中間鍵Rを更新する。詳細な処理は、図6に示すフローチャートで説明する。サーバ側制御部10サーバ側中間鍵更新部150は、この処理が終了すると、ステップS3に処理を移す。ステップS9において、サーバ側制御部10サーバ側通信制御部140は、全てのクライアント端末CLに中間鍵Rを送信する。図5は、本実施形態に係るクライアント端末CLiに係る処理の流れを示すフローチャートである。ステップS11において、端末側制御部20端末側通信制御部210は、サーバSVから中間鍵Rを受信したか否かを判定する。端末側制御部20端末側通信制御部210は、この判定がYESの場合、ステップS12に処理を移し、この判定がNOの場合、ステップS11を再実行する。ステップS12において、端末側制御部20端末側通信制御部210は、中間鍵Rと共に除数Dを受信したか否かを判定する。端末側制御部20端末側通信制御部210は、この判定がYESの場合、ステップS13に処理を移し、この判定がNOの場合、ステップS16に処理を移す。ステップS13において、端末側制御部20私有鍵生成部220は、私有鍵Piを生成する。ステップS14において、端末側制御部20端末側中間鍵更新部240は、クライアント端末CLiに対応している中間鍵Riを除いたN-1個の中間鍵Rについて、当該中間鍵Rを底とし、私有鍵Piを指数とした冪乗を、除数Dで除算した場合の剰余を当該中間鍵Rに置き換えることで、中間鍵Rを更新する。詳細な処理は、図6に示すフローチャートで説明する。ステップS15において、端末側制御部20端末側通信制御部210は、更新した中間鍵RをサーバSVに送信する。この処理が終了すると、端末側制御部20端末側通信制御部210は、ステップS11に処理を移す。ステップS16において、端末側制御部20共通鍵生成部250は、クライアント端末CLiに対応している中間鍵Riを抽出する。ステップS17において、端末側制御部20共通鍵生成部250は、クライアント端末CLiに対応している中間鍵Riを底とし、私有鍵Piを指数とした冪乗を、除数Dで除算した場合の剰余を共通鍵Cとすることによって、共通鍵Cを生成する。詳細な処理は、図6に示すフローチャートで説明する。図6は、本実施形態に係る冪剰余算出部120及び冪剰余算出部230における処理の流れを示すフローチャートである。このフローチャートに示す処理は、図4のステップS2、ステップS8、図5のステップS14、ステップS17に利用される。ステップS21において、入力受付部121入力受付部231は、底、除数、指数の入力を受け付ける。ここで受け付けた底を底Aiとし、除数を除数Bとし、指数を指数eとする。ステップS22において、初期設定部122初期設定部232は、第1中間値ATの初期値をステップS21において受け付けた底Aiとし、第2中間値MTの初期値を1に設定する。ステップS23において、変換部123変換部233は、ステップS21において受け付けた指数eを、2進数に変換する。ステップS24において、計数部124計数部234は、ステップS23において変換された、2進数で表現された指数eのビット数を計数する。ステップS25において、基数算出部125基数算出部235は、第1中間値ATを更新する。具体的には、基数算出部125基数算出部235は、2進数で表現された指数eの右端の値ビットが1である場合、第1中間値ATを第2中間値MTで乗算して得られた値を除数Biで除算して剰余を算出する。続いて、基数算出部125基数算出部235は、この算出された剰余を第1中間値ATとすることにより、第1中間値ATを更新する。ここで、基数算出部125基数算出部235により行われる第1中間値ATと第2中間値MTとの乗算は、第1中間値AT及び第2中間値MTそれぞれを10のべき乗の和に変換し、この変換した第1中間値AT及び第2中間値MTを乗算することで行われる。ステップS26において、剰余算出部126剰余算出部236は、第2中間値MTを更新する。具体的には、剰余算出部126剰余算出部236は、2進数に変換された指数eの右端の値ビットにかかわらず、第1中間値ATを2乗した値を除数Biで除算した場合の剰余を第2中間値MTとすることにより、第2中間値MTを更新する。なお、第1中間値ATの2乗の計算は、第1中間値ATと第2中間値MTとの乗算と同様に、第1中間値ATを10のべき乗の和に変換し、この変換した第1中間値ATを2乗することにより計算される。ステップS27において、シフト部127シフト部237は、2進数に変換された指数eを1ビット右に論理シフトする演算論理シフト演算を行う。ステップS28において、反復実行部128反復実行部238は、ステップS25~ステップS27の処理が、反復回数行われたか判定する。ここで、反復回数は、ステップS24において計数された値である。反復実行部128反復実行部238は、この判定がYESの場合、処理をステップS29に移し、この判定がNOの場合、処理をステップS25に移す。ステップS29において、出力部129出力部239は、第2中間値MTを剰余として出力する。以上、本実施形態によれば、サーバSVは、サーバ側鍵情報生成部110により、1個の基数B、1個の除数D及びN個の秘密鍵Sを生成し、サーバ側中間鍵生成部130により、N個の秘密鍵Sそれぞれについて、基数Bを底とし、当該秘密鍵を指数とした冪乗に対して除数Dで除算した場合に生成されるN個の剰余をN個の中間鍵Rとし、サーバ側通信制御部140により、生成されたN個の中間鍵Rの送受信を行う。また、サーバSVは、サーバ側中間鍵更新部150により、クライアント端末CLiからN個の中間鍵Rをサーバ側通信制御部140によって受信したことに応じて、N個の秘密鍵Sそれぞれについて、i番目の秘密鍵Siiは1からN-1のいずれかをi1番目の秘密鍵Si1に置換すると共にN番目の秘密鍵SNを1番目の秘密鍵S1に置換することで、他の秘密鍵の値に置換し、受信したN個の中間鍵Rそれぞれについて、当該中間鍵を底とし、置換されたN個の秘密鍵のうち当該中間鍵に対応する秘密鍵を指数とした場合の剰余を除数Dで除算した場合に生成されるN個の剰余をN個の中間鍵Rとすることにより、N個の中間鍵Rを更新する。また、サーバは、サーバ側通信制御部140により、クライアント端末からN個の中間鍵Rを受信した場合にN個の中間鍵Rが置換された回数がN-1回であるとき、N台のクライアント端末CL全てに対してN個の中間鍵Rを送信する。また、N台のクライアント端末CLそれぞれクライアント端末CLiは、端末側通信制御部210によりサーバSVから除数Dを受信すると共にN個の中間鍵Rの送受信を行い、私有鍵生成部220により、除数D及びN個の中間鍵Rを受信したことに応じて、私有鍵Piを生成する。また、クライアント端末CLiは、端末側中間鍵更新部240により、私有鍵生成部220により私有鍵Piを生成したことに応じて、当該クライアント端末CLiに対応する中間鍵の値を変更せずに更新したとみなすと共に、当該中間鍵以外のN-1個の中間鍵それぞれについて、当該中間鍵を底とし、当該私有鍵Piを指数とした冪乗に対して除数Dで除算した場合に生成されるN個の剰余をN個の中間鍵Rとすることにより、中間鍵Rを更新する。また、クライアント端末CLiは、共通鍵生成部250により、端末側通信制御部210によりN個の中間鍵Rのみを受信したことに応じて、当該クライアント端末CLiに対応する中間鍵を底とし、私有鍵Piを指数とした冪乗に対して除数Dで除算した場合に生成される剰余を共通鍵Cとする。例えば、N=2であり、秘密鍵S1の値がa、秘密鍵S2の値がbである場合、1番目の中間鍵R1は、サーバSVにより、3式のようにして生成される。ここで、X1は、基数Bを底とし秘密鍵S1に対応するaを指数とした冪乗を除数Dで除算した場合の商とする。続いて、中間鍵R1は、クライアント端末CL1に送信された場合、中間鍵R1の値は変化せずに、サーバSVに送信される。続いて、中間鍵R1は、サーバSVにより、4式のようにして更新される。なお、ここでは更新された中間鍵をR1’とする。また、X2は、中間鍵R1’を底とし置換された秘密鍵S1の値であるbを指数とした冪乗を除数Dで除算した場合の商とする。続いて、中間鍵R1’は、クライアント端末CL2に送信された場合、5式に示すようにして更新される。なお、ここでは更新された中間鍵をR1’’とする。また、X3は、中間鍵R1’を底とし私有鍵P2を指数とした冪乗を除数Dで除算した場合の商とする。続いて、中間鍵R1’’は、サーバSVに送信された後、更新されずにクライアント端末CL1に送信され、共通鍵Cの生成に使用される。すなわち、クライアント端末CL1において共通鍵Cは、6式に示すようにして更新される。ただし、X4は、更新された中間鍵R1’を底とし私有鍵P1を指数とした冪乗を除数Dで除算した場合の商とする。一方、2番目の中間鍵R2は、サーバSVにより、7式のようにして生成される。ここで、X5は、基数Bを底とし秘密鍵S2に対応するbを指数とした冪乗を除数Dで除算した場合の商とする。続いて、中間鍵R2は、クライアント端末CL1に送信された場合、8式に示すようにして更新される。なお、ここでは更新された中間鍵をR2’とする。また、X6は、中間鍵R2を底とし私有鍵P1を指数とした冪乗を除数Dで除算した場合の商とする。続いて、中間鍵R2’は、サーバSVに送信される。続いて、中間鍵R2’は、サーバSVにより、9式のようにして更新される。ここでは更新された中間鍵をR2’’とする。また、X7は、中間鍵R1’を底とし置換された秘密鍵S2の値であるaを指数とした冪乗を除数Dで除算した場合の商とする。続いて、中間鍵R2’’は、クライアント端末CL2に送信された場合、変化せずに、サーバSVに送信される。続いて、中間鍵R2’’は、サーバSVに送信された後、更新されずにクライアント端末CL2に送信され、共通鍵Cの生成に使用される。すなわち、クライアント端末CL2において共通鍵Cは、10式に示すようにして更新される。ただし、X8は、更新された中間鍵R2’’を底とし私有鍵P2を指数とした冪乗を除数Dで除算した場合の商とする。以上のように、サーバSV、クライアント端末CL1、CL2の間では、基数Bに対してa、b、P1、P2を指数とした冪乗が行われることによって、共通鍵Cが生成される。この場合に、同一の基数Bについてa、b、P1、P2それぞれを指数として除数Dで除算した場合の剰余は、a、b、P1、P2をどの順番で指数とした場合でも同一の結果となることが知られている。よって、この法則を利用すれば、クライアント端末の台数をN台とした場合であっても、本実施形態で説明した処理を行うことによって、クライアント端末CLにおいて、共通鍵Cを生成することができる。以上によれば、共通鍵生成システム1では、N台のクライアント端末CLが、共通鍵の受け渡しを行うことなく共通鍵を生成することができる。ここで、除数Dを桁数が大きい自然数である場合、中間鍵R、除数Dが知られたとしても、これらの値のみから、共通鍵Cを求めるには、膨大な計算量が必要となる。したがって、共通鍵生成システムは、三者以上の間で安全に共通鍵を共有することができる。以上、本発明の実施形態について説明したが、本発明は本実施形態に限定されるものではなく、本発明の目的を達成できる範囲での変形、改良等は本発明に含まれるものである。