共通鍵生成システム及び共通鍵生成方法
【課題】共通鍵の受け渡しを行わずに、３者間で安全に共通鍵を共有することができる共通鍵生成システム及び共通鍵生成方法を提供すること。
【解決手段】第１共通鍵生成装置１０及び第２共通鍵生成装置２０は、２次中間鍵ＭＳ１を生成し、第３共通鍵生成装置３０に送信する。第２共通鍵生成装置２０及び第３共通鍵生成装置３０は、２次中間鍵ＭＳ３を生成し、第１共通鍵生成装置１０に送信する。第３共通鍵生成装置３０及び第１共通鍵生成装置１０は、２次中間鍵ＭＳ２を生成し、第２共通鍵生成装置２０に送信する。第１共通鍵生成装置１０は、第１秘密鍵Ｓ１、２次中間鍵ＭＳ３、除数Ｂに基づいて、共通鍵Ｃを生成する。第２共通鍵生成装置２０は、第２秘密鍵Ｓ２、２次中間鍵ＭＳ２、除数Ｂに基づいて、共通鍵Ｃを生成する。第３共通鍵生成装置３０は、第３秘密鍵Ｓ３、２次中間鍵ＭＳ１、除数Ｂに基づいて、共通鍵Ｃを生成する。
【解決手段】第１共通鍵生成装置１０及び第２共通鍵生成装置２０は、２次中間鍵ＭＳ１を生成し、第３共通鍵生成装置３０に送信する。第２共通鍵生成装置２０及び第３共通鍵生成装置３０は、２次中間鍵ＭＳ３を生成し、第１共通鍵生成装置１０に送信する。第３共通鍵生成装置３０及び第１共通鍵生成装置１０は、２次中間鍵ＭＳ２を生成し、第２共通鍵生成装置２０に送信する。第１共通鍵生成装置１０は、第１秘密鍵Ｓ１、２次中間鍵ＭＳ３、除数Ｂに基づいて、共通鍵Ｃを生成する。第２共通鍵生成装置２０は、第２秘密鍵Ｓ２、２次中間鍵ＭＳ２、除数Ｂに基づいて、共通鍵Ｃを生成する。第３共通鍵生成装置３０は、第３秘密鍵Ｓ３、２次中間鍵ＭＳ１、除数Ｂに基づいて、共通鍵Ｃを生成する。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、共通鍵生成システム及び共通鍵生成方法に関する。
【背景技術】
【０００２】
近年、インターネット等のネットワークをデータの交換手段として利用することが急速に広まっている。しかしながら、インターネット等のネットワークでは、データを交換する際に複数のサーバ及び通信回線を経由してデータが転送される。このため、データを転送するサーバ及び通信回線等では、データの盗聴や、データの改ざんや、なりすましをすることが可能となり、セキュリティ問題に発展している。このようなセキュリティ問題に対応するため、暗号化技術が提案されており、例えば、簡易的な暗号化方式として、共通鍵暗号方式が知られている。
【０００３】
共通鍵暗号方式では、例えば、特許文献１に示されるように、生成した共通鍵を、２者間で所有する。続いて、送信者は、共通鍵を用いてデータの暗号化を行い、暗号化されたデータを閲覧者に送信する。閲覧者は、データを受信すると、共通鍵を用いて暗号化されたデータを復号する。
【先行技術文献】
【特許文献】
【０００４】
【特許文献１】特開２０００−２７８２５８号公報
【発明の概要】
【発明が解決しようとする課題】
【０００５】
しかしながら、特許文献１に示される共通鍵交換方式は、２者間において共通鍵を生成する方式であり、３者間において、共通鍵を生成する方法については示されていない。このため、３者間において、安全に共通鍵を生成することができる共通鍵生成システム及び共通鍵生成方法の提供が望まれている。
【０００６】
本発明は、共通鍵の受け渡しを行わずに、３者間で安全に共通鍵を共有することができる共通鍵生成システム及び共通鍵生成方法を提供することを目的とする。
【課題を解決するための手段】
【０００７】
本発明に係る共通鍵生成システムは、第１共通鍵生成装置、第２共通鍵生成装置、及び第３共通鍵生成装置を備え、前記第１共通鍵生成装置、前記第２共通鍵生成装置、及び第３共通鍵生成装置において共通鍵を生成する共通鍵生成システムであって、前記第１共通鍵生成装置は、基数、除数、及び第１秘密鍵を生成する第１鍵情報生成手段と、前記基数を底とし、前記第１秘密鍵を指数としたべき乗を、前記除数で除算した場合の剰余を算出し、当該剰余を第１の１次中間鍵とする第１中間鍵生成手段と、前記基数、前記除数、及び前記第１の１次中間鍵を前記第２共通鍵生成装置及び前記第３共通鍵生成装置に送信する第１送信手段と、を備え、前記第２共通鍵生成装置は、前記第１共通鍵生成装置から、前記基数、前記除数、及び前記第１の１次中間鍵を受信する第２受信手段と、第２秘密鍵を生成する第２鍵情報生成手段と、前記基数を底とし、前記第２秘密鍵を指数としたべき乗を、前記除数で除算した場合の剰余を算出し、当該剰余を第２の１次中間鍵とする第２中間鍵生成手段と、前記第２の１次中間鍵を前記第１共通鍵生成装置及び前記第３共通鍵生成装置に送信する第２送信手段と、を備え、前記第３共通鍵生成装置は、前記第１共通鍵生成装置から、前記基数、前記除数、及び前記第１の１次中間鍵を受信する第３受信手段と、第３秘密鍵を生成する第３鍵情報生成手段と、前記基数を底とし、前記第３秘密鍵を指数としたべき乗を、前記除数で除算した場合の剰余を算出し、当該剰余を第３の１次中間鍵とする第３中間鍵生成手段と、前記第３の１次中間鍵を前記第１共通鍵生成装置及び前記第２共通鍵生成装置に送信する第３送信手段と、を備え、前記第１共通鍵生成装置は、前記第２共通鍵生成装置から前記第２の１次中間鍵を受信するとともに、前記第３共通鍵生成装置から前記第３の１次中間鍵を受信する第１受信手段を更に備え、前記第１中間鍵生成手段は、前記第１受信手段により受信した前記第２の１次中間鍵を底とし、前記第１秘密鍵を指数としたべき乗を、前記除数で除算した場合の剰余を算出し、当該剰余を第１の２次中間鍵とするとともに、前記第１受信手段により受信した前記第３の１次中間鍵を底とし、前記第１秘密鍵を指数としたべき乗を、前記除数で除算した場合の剰余を算出し、当該剰余を第２の２次中間鍵とし、前記第１送信手段は、前記第２の２次中間鍵を前記第２共通鍵生成装置に送信するとともに、前記第１の２次中間鍵を前記第３共通鍵生成装置に送信し、前記第２受信手段は、第３共通鍵生成装置から前記第３の１次中間鍵を更に受信し、前記第２中間鍵生成手段は、前記第２受信手段により受信した前記第３の１次中間鍵を底とし、前記第２秘密鍵を指数としたべき乗を、前記除数で除算した場合の剰余を算出し、当該剰余を第３の２次中間鍵とするとともに、前記第２受信手段により受信した前記第１の１次中間鍵を底とし、前記第２秘密鍵を指数としたべき乗を、前記除数で除算した場合の剰余を算出し、当該剰余を前記第１の２次中間鍵とし、前記第２送信手段は、前記第３の２次中間鍵を前記第１共通鍵生成装置に送信するとともに、前記第１の２次中間鍵を前記第３共通鍵生成装置に送信し、前記第３受信手段は、第２共通鍵生成装置から前記第２の１次中間鍵を更に受信し、前記第３中間鍵生成手段は、前記第３受信手段により受信した前記第１の１次中間鍵を底とし、前記第３秘密鍵を指数としたべき乗を、前記除数で除算した場合の剰余を算出し、当該剰余を前記第２の２次中間鍵とするとともに、前記第３受信手段により受信した前記第２の１次中間鍵を底とし、前記第３秘密鍵を指数としたべき乗を、前記除数で除算した場合の剰余を算出し、当該剰余を前記第３の２次中間鍵とし、前記第３送信手段は、前記第３の２次中間鍵を前記第１共通鍵生成装置に送信するとともに、前記第２の２次中間鍵を前記第２共通鍵生成装置に送信し、前記第１受信手段は、前記第２共通鍵生成装置から前記第３の２次中間鍵を受信するとともに、前記第３共通鍵生成装置から前記第３の２次中間鍵を受信し、前記第１共通鍵生成装置は、前記第１受信手段により受信した前記第３の２次中間鍵を底とし、前記第１秘密鍵を指数としたべき乗を、前記除数で除算した場合の剰余を算出し、当該剰余を共通鍵とする第１共通鍵生成手段を更に備え、前記第２受信手段は、前記第３共通鍵生成装置から前記第２の２次中間鍵を受信するとともに、前記第１共通鍵生成装置から前記第２の２次中間鍵を受信し、前記第２共通鍵生成装置は、前記第２受信手段により受信した前記第２の２次中間鍵を底とし、前記第２秘密鍵を指数としたべき乗を、前記除数で除算した場合の剰余を算出し、当該剰余を前記共通鍵とする第２共通鍵生成手段を更に備え、前記第３受信手段は、前記第１共通鍵生成装置から前記第１の２次中間鍵を受信するとともに、前記第２共通鍵生成装置から前記第１の２次中間鍵を受信し、前記第３共通鍵生成装置は、前記第３受信手段により受信した前記第１の２次中間鍵を底とし、前記第３秘密鍵を指数としたべき乗を、前記除数で除算した場合の剰余を算出し、当該剰余を前記共通鍵とする第３共通鍵生成手段を更に備える。
【０００８】
本発明に係る共通鍵生成方法は、第１共通鍵生成装置、第２共通鍵生成装置、及び第３共通鍵生成装置が共通鍵を生成する共通鍵生成方法であって、前記第１共通鍵生成装置が、基数、除数、及び第１秘密鍵を生成するステップと、前記第１共通鍵生成装置が、前記基数を底とし、前記第１秘密鍵を指数としたべき乗を、前記除数で除算した場合の剰余を算出し、当該剰余を第１の１次中間鍵とするステップと、前記第１共通鍵生成装置が、前記基数、前記除数、及び前記第１の１次中間鍵を前記第２共通鍵生成装置及び前記第３共通鍵生成装置に送信するステップと、前記第２共通鍵生成装置が、前記第１共通鍵生成装置から、前記基数、前記除数、及び前記第１の１次中間鍵を受信するステップと、前記第２共通鍵生成装置が、第２秘密鍵を生成するステップと、前記第２共通鍵生成装置が、前記基数を底とし、前記第２秘密鍵を指数としたべき乗を、前記除数で除算した場合の剰余を算出し、当該剰余を第２の１次中間鍵とするステップと、前記第２共通鍵生成装置が、前記第２の１次中間鍵を前記第１共通鍵生成装置及び前記第３共通鍵生成装置に送信するステップと、前記第３共通鍵生成装置が、前記第１共通鍵生成装置から、前記基数、前記除数、及び前記第１の１次中間鍵を受信するステップと、前記第３共通鍵生成装置が、第３秘密鍵を生成するステップと、前記第３共通鍵生成装置が、前記基数を底とし、前記第３秘密鍵を指数としたべき乗を、前記除数で除算した場合の剰余を算出し、当該剰余を第３の１次中間鍵とするステップと、前記第３共通鍵生成装置が、前記第３の１次中間鍵を前記第１共通鍵生成装置及び前記第２共通鍵生成装置に送信するステップと、前記第１共通鍵生成装置が、前記第２共通鍵生成装置から前記第２の１次中間鍵を受信するステップと、前記第１共通鍵生成装置が、前記第２の１次中間鍵を底とし、前記第１秘密鍵を指数としたべき乗を、前記除数で除算した場合の剰余を算出し、当該剰余を第１の２次中間鍵とするステップと、前記第１共通鍵生成装置が、前記第１の２次中間鍵を前記第３共通鍵生成装置に送信するステップと、前記第１共通鍵生成装置が、前記第３共通鍵生成装置から前記第３の１次中間鍵を受信するステップと、前記第１共通鍵生成装置が、前記第３の１次中間鍵を底とし、前記第１秘密鍵を指数としたべき乗を、前記除数で除算した場合の剰余を算出し、当該剰余を第２の２次中間鍵とするステップと、前記第１共通鍵生成装置が、前記第２の２次中間鍵を前記第２共通鍵生成装置に送信するステップと、前記第２共通鍵生成装置が、前記第１の１次中間鍵を底とし、前記第２秘密鍵を指数としたべき乗を、前記除数で除算した場合の剰余を算出し、当該剰余を第１の２次中間鍵とするステップと、前記第２共通鍵生成装置が、前記第１の２次中間鍵を前記第３共通鍵生成装置に送信するステップと、前記第２共通鍵生成装置が、前記第３共通鍵生成装置から前記第３の１次中間鍵を受信するステップと、前記第２共通鍵生成装置が、前記第３の１次中間鍵を底とし、前記第２秘密鍵を指数としたべき乗を、前記除数で除算した場合の剰余を算出し、当該剰余を第３の２次中間鍵とするステップと、前記第２共通鍵生成装置が、前記第３の２次中間鍵を前記第１共通鍵生成装置に送信するステップと、前記第３共通鍵生成装置が、前記第１の１次中間鍵を底とし、前記第３秘密鍵を指数としたべき乗を、前記除数で除算した場合の剰余を算出し、当該剰余を第２の２次中間鍵とするステップと、前記第３共通鍵生成装置が、前記第２の２次中間鍵を前記第２共通鍵生成装置に送信するステップと、前記第３共通鍵生成装置が、前記第２共通鍵生成装置から前記第２の１次中間鍵を受信するステップと、前記第３共通鍵生成装置が、前記第２の１次中間鍵を底とし、前記第３秘密鍵を指数としたべき乗を、前記除数で除算した場合の剰余を算出し、当該剰余を第３の２次中間鍵とするステップと、前記第３共通鍵生成装置が、前記第３の２次中間鍵を前記第１共通鍵生成装置に送信するステップと、前記第１共通鍵生成装置が、前記第２共通鍵生成装置又は前記第３共通鍵生成装置から前記第３の２次中間鍵を受信するステップと、前記第１共通鍵生成装置が、前記第３の２次中間鍵を底とし、前記第１秘密鍵を指数としたべき乗を、前記除数で除算した場合の剰余を算出し、当該剰余を共通鍵とするステップと、前記第２共通鍵生成装置が、前記第３共通鍵生成装置又は前記第１共通鍵生成装置から前記第２の２次中間鍵を受信するステップと、前記第２共通鍵生成装置が、前記第２の２次中間鍵を底とし、前記第２秘密鍵を指数としたべき乗を、前記除数で除算した場合の剰余を算出し、当該剰余を前記共通鍵とするステップと、前記第３共通鍵生成装置が、前記第１共通鍵生成装置又は前記第２共通鍵生成装置から前記第１の２次中間鍵を受信するステップと、前記第３共通鍵生成装置が、前記第１の２次中間鍵を底とし、前記第３秘密鍵を指数としたべき乗を、前記除数で除算した場合の剰余を算出し、当該剰余を前記共通鍵とするステップと、を含む。
【発明の効果】
【０００９】
本発明によれば、共通鍵の受け渡しを行わずに、３者間で安全に共通鍵を共有することができる。
【図面の簡単な説明】
【００１０】
【図１】本実施形態に係る共通鍵生成システムの全体概要を示す図である。
【図２】本実施形態に係る共通鍵生成装置の機能構成を示す図である。
【図３】本実施形態に係るべき剰余算出部の機能構成を示す図である。
【図４】本実施形態に係る第１共通鍵生成装置における共通鍵生成に係る処理の流れを示すフローチャートである。
【図５】本実施形態に係るべき剰余算出部における処理の流れを示すフローチャートである。
【図６】本実施形態に係る第２共通鍵生成装置における共通鍵生成に係る処理の流れを示すフローチャートである。
【図７】本実施形態に係る第３共通鍵生成装置における共通鍵生成に係る処理の流れを示すフローチャートである。
【発明を実施するための形態】
【００１１】
以下、本発明の実施形態について図を参照しながら説明する。
【００１２】
図１は、本実施形態に係る共通鍵生成システム１の全体概要を示す図である。共通鍵生成システム１は、３台の共通鍵生成装置間で共通鍵を生成するシステムである。共通鍵生成システム１は、第１共通鍵生成装置１０と、第２共通鍵生成装置２０と、第３共通鍵生成装置３０と、を備える。第１共通鍵生成装置１０と、第２共通鍵生成装置２０と、第３共通鍵生成装置３０とは、ＬＡＮ（Ｌｏｃａｌ Ａｒｅａ Ｎｅｔｗｏｒｋ）やインターネット等のコンピュータネットワークにより構成される通信ネットワークＮにより、通信可能に接続されている。
【００１３】
この第１共通鍵生成装置１０では、基数Ａ、除数Ｂ、及び第１秘密鍵Ｓ１を生成し、基数Ａ、除数Ｂ、及び第１秘密鍵Ｓ１に基づいて第１の１次中間鍵として１次中間鍵ＭＦ１を生成し、第２共通鍵生成装置２０及び第３共通鍵生成装置３０に、基数Ａ、除数Ｂ、及び１次中間鍵ＭＦ１を送信する。また、第２共通鍵生成装置２０では、第２秘密鍵Ｓ２を生成し、基数Ａ、除数Ｂ、及び第２秘密鍵Ｓ２に基づいて第２の１次中間鍵として１次中間鍵ＭＦ２を生成し、第３共通鍵生成装置３０及び第１共通鍵生成装置１０に、１次中間鍵ＭＦ２を送信する。また、第３共通鍵生成装置３０では、第３秘密鍵Ｓ３を生成し、基数Ａ、除数Ｂ、及び第３秘密鍵Ｓ３に基づいて第３の１次中間鍵として１次中間鍵ＭＦ３を生成し、第１共通鍵生成装置１０及び第２共通鍵生成装置２０に、１次中間鍵ＭＦ３を送信する。
【００１４】
また、第１共通鍵生成装置１０は、第２共通鍵生成装置２０から、１次中間鍵ＭＦ２を受信するとともに、第３共通鍵生成装置３０から、１次中間鍵ＭＦ３を受信し、１次中間鍵ＭＦ２、除数Ｂ、及び第１秘密鍵Ｓ１に基づいて第１の２次中間鍵として２次中間鍵ＭＳ１を生成し、１次中間鍵ＭＦ３、除数Ｂ、及び第１秘密鍵Ｓ１に基づいて第２の２次中間鍵として２次中間鍵ＭＳ２を生成する。続いて、第１共通鍵生成装置１０は、２次中間鍵ＭＳ２を第２共通鍵生成装置２０に送信し、２次中間鍵ＭＳ１を第３共通鍵生成装置３０に送信する。
【００１５】
また、第２共通鍵生成装置２０は、第３共通鍵生成装置３０から、１次中間鍵ＭＦ３を受信するとともに、第１共通鍵生成装置１０から、１次中間鍵ＭＦ１を受信し、１次中間鍵ＭＦ３、除数Ｂ、及び第２秘密鍵Ｓ２に基づいて第３の２次中間鍵として２次中間鍵ＭＳ３を生成し、１次中間鍵ＭＦ１、除数Ｂ、及び第２秘密鍵Ｓ２に基づいて第１の２次中間鍵として２次中間鍵ＭＳ１を生成する。続いて、第２共通鍵生成装置２０は、２次中間鍵ＭＳ１を第３共通鍵生成装置３０に送信し、２次中間鍵ＭＳ３を第１共通鍵生成装置１０に送信する。
【００１６】
また、第３共通鍵生成装置３０は、第１共通鍵生成装置１０から、１次中間鍵ＭＦ１を受信するとともに、第２共通鍵生成装置２０から、１次中間鍵ＭＦ２を受信し、１次中間鍵ＭＦ１、除数Ｂ、及び第３秘密鍵Ｓ３に基づいて第２の２次中間鍵として２次中間鍵ＭＳ２を生成し、１次中間鍵ＭＦ２、除数Ｂ、及び第３秘密鍵Ｓ３に基づいて第３の２次中間鍵として２次中間鍵ＭＳ３を生成する。続いて、第３共通鍵生成装置３０は、２次中間鍵ＭＳ３を第１共通鍵生成装置１０に送信し、２次中間鍵ＭＳ２を第２共通鍵生成装置２０に送信する。
【００１７】
また、第１共通鍵生成装置１０は、第２共通鍵生成装置２０及び第３共通鍵生成装置３０から２次中間鍵ＭＳ３を受信し、２次中間鍵ＭＳ３、除数Ｂ、及び第１秘密鍵Ｓ１に基づいて共通鍵Ｃを生成する。
【００１８】
また、第２共通鍵生成装置２０は、第３共通鍵生成装置３０及び第１共通鍵生成装置１０から２次中間鍵ＭＳ２を受信し、２次中間鍵ＭＳ２、除数Ｂ、及び第２秘密鍵Ｓ２に基づいて共通鍵Ｃを生成する。
【００１９】
また、第３共通鍵生成装置３０は、第１共通鍵生成装置１０及び第２共通鍵生成装置２０から２次中間鍵ＭＳ１を受信し、２次中間鍵ＭＳ１、除数Ｂ、及び第３秘密鍵Ｓ３に基づいて共通鍵Ｃを生成する。
【００２０】
本実施形態は、コンピュータ（第１共通鍵生成装置１０、第２共通鍵生成装置２０及び第３共通鍵生成装置３０）及びその周辺装置に適用される。本実施形態における各部は、コンピュータ及びその周辺装置が備えるハードウェア並びにこのハードウェアを制御するソフトウェアによって構成される。
【００２１】
上記ハードウェアには、制御部としてのＣＰＵの他、記憶部、通信部、表示部及び入力部が含まれる。記憶部としては、例えば、メモリ（ＲＡＭ、ＲＯＭ等）、ハードディスクドライブ（ＨＤＤ）及び光ディスク（ＣＤ、ＤＶＤ等）ドライブが挙げられる。通信部としては、例えば、各種有線及び無線インターフェース装置が挙げられる。表示部としては、例えば、液晶ディスプレイ、プラズマディスプレイ等の各種ディスプレイが挙げられる。入力部としては、例えば、キーボード及びマウス等が挙げられる。
【００２２】
上記ソフトウェアには、上記ハードウェアを制御するコンピュータ・プログラムやデータが含まれる。コンピュータ・プログラムやデータは、記憶部により記憶され、制御部により適宜実行、参照される。また、コンピュータ・プログラムやデータは、通信回線を介して配布することも可能であり、ＣＤ−ＲＯＭ等のコンピュータ可読媒体に記録して配布することも可能である。
【００２３】
図２は、本実施形態に係る共通鍵生成装置の機能構成を示す図である。
第１共通鍵生成装置１０の制御部は、第１送信手段及び第１受信手段としての第１通信部１１と、第１鍵情報生成手段としての第１鍵情報生成部１２と、第１中間鍵生成手段としての第１中間鍵生成部１３と、第１共通鍵生成手段としての第１共通鍵生成部１４と、べき剰余算出部５０と、を備える。
【００２４】
第１通信部１１は、第２共通鍵生成装置２０及び第３共通鍵生成装置３０と、通信ネットワークＮを介して、鍵情報の送受信を行う。具体的には、第１通信部１１は、後述の第１鍵情報生成部１２により生成される基数Ａ及び除数Ｂ、並びに後述の第１中間鍵生成部１３により生成される１次中間鍵ＭＦ１を、第２共通鍵生成装置２０及び第３共通鍵生成装置３０に送信する。また、第１通信部１１は、第２共通鍵生成装置２０に、２次中間鍵ＭＳ２を送信し、第２共通鍵生成装置２０から、１次中間鍵ＭＦ２及び２次中間鍵ＭＳ３を受信する。また、第１通信部１１は、第３共通鍵生成装置３０に、２次中間鍵ＭＳ１を送信し、第３共通鍵生成装置３０から、１次中間鍵ＭＦ３及び２次中間鍵ＭＳ３を受信する。
【００２５】
第１鍵情報生成部１２は、共通鍵Ｃを生成する情報となる基数Ａ、除数Ｂ、及び第１秘密鍵Ｓ１を生成する。具体的には、第１鍵情報生成部１２は、基数Ａとして任意の自然数を生成し、除数Ｂとして、桁数が大きい素数（例えば、２０桁以上の素数）を生成するものとする。また、第１鍵情報生成部１２は、第１秘密鍵Ｓ１として、「０」以上かつ「除数Ｂ−２」以下である任意の自然数を生成する。
【００２６】
第１中間鍵生成部１３は、基数Ａを底とし、第１秘密鍵Ｓ１を指数としたべき乗を、除数Ｂで除算した場合の剰余を１次中間鍵ＭＦ１として生成する。具体的には、第１中間鍵生成部１３は、基数Ａを底、除数Ｂを除数、第１秘密鍵Ｓ１を指数とし、これら底、除数、及び指数をべき剰余算出部５０に入力することにより、べき剰余算出部５０から、基数Ａを底とし、第１秘密鍵Ｓ１を指数としたべき乗を除数Ｂで除算した場合の剰余を得る。続いて、第１中間鍵生成部１３は、得られた剰余を１次中間鍵ＭＦ１とすることにより、１次中間鍵ＭＦ１を生成する。
【００２７】
また、第１中間鍵生成部１３は、第１通信部１１により、１次中間鍵ＭＦ２を受信したことに応じて、１次中間鍵ＭＦ２を底とし、第１秘密鍵Ｓ１を指数としたべき乗を、除数Ｂで除算した場合の剰余を２次中間鍵ＭＳ１として生成する。具体的には、第１中間鍵生成部１３は、１次中間鍵ＭＦ２を底、除数Ｂを除数、第１秘密鍵Ｓ１を指数とし、これら底、除数、及び指数をべき剰余算出部５０に入力することにより、べき剰余算出部５０から得られる剰余を２次中間鍵ＭＳ１とすることにより、２次中間鍵ＭＳ１を生成する。
【００２８】
また、第１中間鍵生成部１３は、第１通信部１１により、１次中間鍵ＭＦ３を受信したことに応じて、１次中間鍵ＭＦ３を底とし、第１秘密鍵Ｓ１を指数としたべき乗を、除数Ｂで除算した場合の剰余を２次中間鍵ＭＳ２として生成する。具体的には、第１中間鍵生成部１３は、１次中間鍵ＭＦ３を底、除数Ｂを除数、第１秘密鍵Ｓ１を指数とし、これら底、除数、及び指数をべき剰余算出部５０に入力することにより、べき剰余算出部５０から得られる剰余を２次中間鍵ＭＳ２とすることにより、２次中間鍵ＭＳ２を生成する。
【００２９】
第１共通鍵生成部１４は、第１通信部１１により、２次中間鍵ＭＳ３を受信したことに応じて、２次中間鍵ＭＳ３を底とし、第１秘密鍵Ｓ１を指数としたべき乗を、除数Ｂで除算した場合の剰余を共通鍵Ｃとして生成する。具体的には、第１共通鍵生成部１４は、２次中間鍵ＭＳ３を底、除数Ｂを除数、第１秘密鍵Ｓ１を指数とし、これら底、除数、及び指数をべき剰余算出部５０に入力することにより、べき剰余算出部５０から得られる剰余を共通鍵Ｃとすることにより、共通鍵Ｃを生成する。
【００３０】
べき剰余算出部５０は、第１共通鍵生成装置１０、第２共通鍵生成装置２０、及び第３共通鍵生成装置３０の共通機能である。
図３を参照してべき剰余算出部５０について説明する。図３は、本実施形態に係るべき剰余算出部５０の機能構成を示す図である。
【００３１】
べき剰余算出部５０は、底、除数、及び指数の入力を受け付け、この底の指数乗を、除数で除算した場合の剰余を算出し、この算出した剰余を出力する。べき剰余算出部５０は、入力受付手段としての入力受付部５１と、初期設定手段としての初期設定部５２と、変換手段としての変換部５３と、計数手段としての計数部５４と、基数算出手段としての基数算出部５５と、剰余算出手段としての剰余算出部５６と、シフト手段としてのシフト部５７と、反復実行手段としての反復実行部５８と、出力手段としての出力部５９と、を備える。また、べき剰余算出部５０は、第１中間値ＡＴと、第２中間値ＭＴとを備える。
【００３２】
入力受付部５１は、底、除数、及び指数の入力を受け付ける。ここで、入力受付部５１により受け付けられた底、除数、及び指数を、それぞれ底Ａｉ、除数Ｂｉ、指数ｅとする。
【００３３】
初期設定部５２は、第１中間値ＡＴの初期値を底Ａｉとし、第２中間値ＭＴの初期値を１に設定する。
変換部５３は、指数ｅを、１０進数から２進数に変換する。
【００３４】
計数部５４は、変換部５３により２進数に変換された指数ｅのビット数を計数する。
【００３５】
基数算出部５５は、２進数で表現された指数ｅの右端の値（ビット）が１である場合、第１中間値ＡＴを第２中間値ＭＴで乗算して得られた値を除数Ｂｉで除算した場合の剰余を第１中間値ＡＴとすることにより、第１中間値ＡＴを更新する。
【００３６】
なお、第１中間値ＡＴと第２中間値ＭＴとの乗算は、以下のように行われる。すなわち、基数算出部５５は、第１中間値ＡＴ及び第２中間値ＭＴを、以下の（１）式に示すように、複数桁（例えば、１桁目〜５桁目、６桁目〜１０桁目等、５桁ずつ）に区切り、１０のべき乗により構成される多項式、すなわち、初項を１０のべき乗（例えば１０の５乗）の０乗、公比を当該１０のべき乗（例えば１０の５乗）とした数列の和で表される多項式に変換する。
【数１】
【００３７】
ここで、ａ１…ａｍは、第１中間値ＡＴを満たすためにそれぞれの項に付される係数であり、ｂ１…ｂｎは、第２中間値ＭＴを満たすためにそれぞれの項に付される係数である。
【００３８】
続いて、基数算出部５５は、１０のべき乗の和に変換された第１中間値ＡＴ及び第２中間値ＭＴの多項式を乗算して、（２）式に示すように展開する。その後、展開された値に含まれるそれぞれの項を合計することにより、第１中間値ＡＴと第２中間値ＭＴとを乗算した値を算出する。
【数２】
【００３９】
剰余算出部５６は、２進数に変換された指数ｅの右端の値（ビット）にかかわらず、第１中間値ＡＴを２乗した値を除数Ｂｉで除算した場合の剰余を第２中間値ＭＴとすることにより、第２中間値ＭＴを更新する。なお、第１中間値ＡＴの２乗の計算は、第１中間値ＡＴと第２中間値ＭＴとの乗算と同様に、第１中間値ＡＴを、初項を１０のべき乗（例えば１０の５乗）の０乗、公比を当該１０のべき乗（例えば１０の５乗）とした数列の和で表される多項式に変換し、この多項式の第１中間値ＡＴを２乗することにより計算される。
【００４０】
シフト部５７は、２進数に変換された指数ｅを右シフトする。具体的には、シフト部５７は、２進数に変換された指数ｅを１ビット右に論理シフトする演算（論理シフト演算）を行う。
【００４１】
反復実行部５８は、計数部５４により計数されたビット数の値を反復回数とし、基数算出部５５、剰余算出部５６、及びシフト部５７に係る処理が、基数算出部５５、剰余算出部５６、シフト部５７の順に、反復回数実行されるように制御する。具体的には、記憶部に初期値を０とするカウンタを設けておき、反復実行部５８は、基数算出部５５、剰余算出部５６、及びシフト部５７に係る処理が終了したことに応じて、カウンタに１加算（インクリメント）する。その後、反復実行部５８は、カウンタの値が反復回数に達するまで、基数算出部５５、剰余算出部５６、シフト部５７、インクリメントに係る処理を実行する制御を行い、カウンタの値が反復回数に達した場合に、反復実行を終了する。
【００４２】
出力部５９は、反復実行部５８により、基数算出部５５、剰余算出部５６、及びシフト部５７に係る処理が反復回数実行された後、第２中間値ＭＴを剰余として出力する。
【００４３】
第２共通鍵生成装置２０の制御部は、第２送信手段及び第２受信手段としての第２通信部２１と、第２鍵情報生成手段としての第２鍵情報生成部２２と、第２中間鍵生成手段としての第２中間鍵生成部２３と、第２共通鍵生成手段としての第２共通鍵生成部２４と、べき剰余算出部５０と、を備える。
【００４４】
第２通信部２１は、第３共通鍵生成装置３０及び第１共通鍵生成装置１０と、通信ネットワークＮを介して、鍵情報の送受信を行う。具体的には、第２通信部２１は、後述の第２中間鍵生成部２３により生成される１次中間鍵ＭＦ２を、第３共通鍵生成装置３０及び第１共通鍵生成装置１０に送信する。また、第２通信部２１は、第３共通鍵生成装置３０に、２次中間鍵ＭＳ１を送信し、第３共通鍵生成装置３０から、１次中間鍵ＭＦ３及び２次中間鍵ＭＳ２を受信する。また、第２通信部２１は、第１共通鍵生成装置１０に、２次中間鍵ＭＳ３を送信し、第１共通鍵生成装置１０から、１次中間鍵ＭＦ１及び２次中間鍵ＭＳ２を受信する。
【００４５】
第２鍵情報生成部２２は、共通鍵を生成する情報となる第２秘密鍵Ｓ２を生成する。具体的には、第２鍵情報生成部２２は、第２秘密鍵Ｓ２として、「０」以上かつ「除数Ｂ−２」以下である任意の自然数を生成する。
【００４６】
第２中間鍵生成部２３は、基数Ａを底とし、第２秘密鍵Ｓ２を指数としたべき乗を、除数Ｂで除算した場合の剰余を１次中間鍵ＭＦ２として生成する。具体的には、第２中間鍵生成部２３は、基数Ａを底、除数Ｂを除数、第２秘密鍵Ｓ２を指数とし、これら底、除数、及び指数をべき剰余算出部５０に入力することにより、べき剰余算出部５０から、基数Ａを底とし、第２秘密鍵Ｓ２を指数としたべき乗を除数Ｂで除算した場合の剰余を得る。続いて、第２中間鍵生成部２３は、得られた剰余を１次中間鍵ＭＦ２とすることにより、１次中間鍵ＭＦ２を生成する。
【００４７】
また、第２中間鍵生成部２３は、第２通信部２１により、１次中間鍵ＭＦ３を受信したことに応じて、１次中間鍵ＭＦ３を底とし、第２秘密鍵Ｓ２を指数としたべき乗を、除数Ｂで除算した場合の剰余を２次中間鍵ＭＳ３として生成する。具体的には、第２中間鍵生成部２３は、１次中間鍵ＭＦ３を底、除数Ｂを除数、第２秘密鍵Ｓ２を指数とし、これら底、除数、及び指数をべき剰余算出部５０に入力することにより、べき剰余算出部５０から得られる剰余を２次中間鍵ＭＳ３とすることにより、２次中間鍵ＭＳ３を生成する。
【００４８】
また、第２中間鍵生成部２３は、第２通信部２１により、１次中間鍵ＭＦ１を受信したことに応じて、１次中間鍵ＭＦ１を底とし、第２秘密鍵Ｓ２を指数としたべき乗を、除数Ｂで除算した場合の剰余を２次中間鍵ＭＳ１として生成する。具体的には、第２中間鍵生成部２３は、１次中間鍵ＭＦ１を底、除数Ｂを除数、第２秘密鍵Ｓ２を指数とし、これら底、除数、及び指数をべき剰余算出部５０に入力することにより、べき剰余算出部５０から得られる剰余を２次中間鍵ＭＳ１とすることにより、２次中間鍵ＭＳ１を生成する。
【００４９】
第２共通鍵生成部２４は、第２通信部２１により、２次中間鍵ＭＳ２を受信したことに応じて、２次中間鍵ＭＳ２を底とし、第２秘密鍵Ｓ２を指数としたべき乗を、除数Ｂで除算した場合の剰余を共通鍵Ｃとして生成する。具体的には、第２共通鍵生成部２４は、２次中間鍵ＭＳ２を底、除数Ｂを除数、第２秘密鍵Ｓ２を指数とし、これら底、除数、及び指数をべき剰余算出部５０に入力することにより、べき剰余算出部５０から得られる剰余を共通鍵Ｃとすることにより、共通鍵Ｃを生成する。
【００５０】
べき剰余算出部５０は、第１共通鍵生成装置１０に備えているべき剰余算出部５０と同一であるので、説明を省略する。
【００５１】
第３共通鍵生成装置３０の制御部は、第３送信手段及び第３受信手段としての第３通信部３１と、第３鍵情報生成手段としての第３鍵情報生成部３２と、第３中間鍵生成手段としての第３中間鍵生成部３３と、第３共通鍵生成手段としての第３共通鍵生成部３４と、べき剰余算出部５０と、を備える。
【００５２】
第３通信部３１は、第１共通鍵生成装置１０及び第２共通鍵生成装置２０と、通信ネットワークＮを介して、鍵情報の送受信を行う。具体的には、第３通信部３１は、後述の第３中間鍵生成部３３により生成される１次中間鍵ＭＦ３を、第１共通鍵生成装置１０及び第２共通鍵生成装置２０に送信する。また、第３通信部３１は、第１共通鍵生成装置１０に、２次中間鍵ＭＳ３を送信し、第１共通鍵生成装置１０から、１次中間鍵ＭＦ１及び２次中間鍵ＭＳ１を受信する。また、第３通信部３１は、第２共通鍵生成装置２０に、２次中間鍵ＭＳ２を送信し、第２共通鍵生成装置２０から、１次中間鍵ＭＦ２及び２次中間鍵ＭＳ１を受信する。
【００５３】
第３鍵情報生成部３２は、共通鍵を生成する情報となる第３秘密鍵Ｓ３を生成する。具体的には、第３鍵情報生成部３２は、第３秘密鍵Ｓ３として、「０」以上かつ「除数Ｂ−２」以下である任意の自然数を生成する。
【００５４】
第３中間鍵生成部３３は、基数Ａを底とし、第３秘密鍵Ｓ３を指数としたべき乗を、除数Ｂで除算した場合の剰余を１次中間鍵ＭＦ３として生成する。具体的には、第３中間鍵生成部３３は、基数Ａを底、除数Ｂを除数、第３秘密鍵Ｓ３を指数とし、これら底、除数、及び指数をべき剰余算出部５０に入力することにより、べき剰余算出部５０から、基数Ａを底とし、第３秘密鍵Ｓ３を指数としたべき乗を除数Ｂで除算した場合の剰余を得る。続いて、第３中間鍵生成部３３は、得られた剰余を１次中間鍵ＭＦ３とすることにより、１次中間鍵ＭＦ３を生成する。
【００５５】
また、第３中間鍵生成部３３は、第３通信部３１により、１次中間鍵ＭＦ１を受信したことに応じて、１次中間鍵ＭＦ１を底とし、第３秘密鍵Ｓ３を指数としたべき乗を、除数Ｂで除算した場合の剰余を２次中間鍵ＭＳ２として生成する。具体的には、第３中間鍵生成部３３は、１次中間鍵ＭＦ１を底、除数Ｂを除数、第３秘密鍵Ｓ３を指数とし、これら底、除数、及び指数をべき剰余算出部５０に入力することにより、べき剰余算出部５０から得られる剰余を２次中間鍵ＭＳ２とすることにより、２次中間鍵ＭＳ２を生成する。
【００５６】
また、第３中間鍵生成部３３は、第３通信部３１により、１次中間鍵ＭＦ２を受信したことに応じて、１次中間鍵ＭＦ２を底とし、第３秘密鍵Ｓ３を指数としたべき乗を、除数Ｂで除算した場合の剰余を２次中間鍵ＭＳ３として生成する。具体的には、第３中間鍵生成部３３は、１次中間鍵ＭＦ２を底、除数Ｂを除数、第３秘密鍵Ｓ３を指数とし、これら底、除数、及び指数をべき剰余算出部５０に入力することにより、べき剰余算出部５０から得られる剰余を２次中間鍵ＭＳ３とすることにより、２次中間鍵ＭＳ３を生成する。
【００５７】
第３共通鍵生成部３４は、第３通信部３１により、２次中間鍵ＭＳ１を受信したことに応じて、２次中間鍵ＭＳ１を底とし、第３秘密鍵Ｓ３を指数としたべき乗を、除数Ｂで除算した場合の剰余を共通鍵Ｃとして生成する。具体的には、第３共通鍵生成部３４は、２次中間鍵ＭＳ１を底、除数Ｂを除数、第３秘密鍵Ｓ３を指数とし、これら底、除数、及び指数をべき剰余算出部５０に入力することにより、べき剰余算出部５０から得られる剰余を共通鍵Ｃとすることにより、共通鍵Ｃを生成する。
【００５８】
べき剰余算出部５０は、第１共通鍵生成装置１０に備えているべき剰余算出部５０と同一であるので、説明を省略する。
【００５９】
続いて、図４から図７を参照して、共通鍵生成システム１における処理の流れを説明する。
図４は、本実施形態に係る第１共通鍵生成装置１０における共通鍵生成に係る処理の流れを示すフローチャートである。
【００６０】
ステップＳ１において、第１鍵情報生成部１２は、基数Ａ、除数Ｂ、及び第１秘密鍵Ｓ１を生成する。
【００６１】
ステップＳ２において、第１中間鍵生成部１３は、ステップＳ１において生成された基数Ａ、除数Ｂ、及び第１秘密鍵Ｓ１に基づいて、１次中間鍵ＭＦ１を生成する。すなわち、第１中間鍵生成部１３は、基数Ａを底とし、第１秘密鍵Ｓ１を指数としたべき乗を、除数Ｂで除算した場合の剰余を１次中間鍵ＭＦ１とする。１次中間鍵ＭＦ１を生成する詳細な処理は、第１共通鍵生成装置１０のべき剰余算出部５０において行われる。べき剰余算出部５０における処理は、後述で説明する。
【００６２】
ステップＳ３において、第１通信部１１は、ステップＳ１において生成された基数Ａ、除数Ｂ、及びステップＳ２において生成された１次中間鍵ＭＦ１を第２共通鍵生成装置２０及び第３共通鍵生成装置３０に送信する。
【００６３】
ステップＳ４において、第１共通鍵生成装置１０の制御部は、第１通信部１１により、第２共通鍵生成装置２０又は第３共通鍵生成装置３０から、鍵を受信したか否かを判定する。第１共通鍵生成装置１０の制御部は、この判定がＹＥＳの場合、処理をステップＳ５に移し、この処理がＮＯの場合、ステップＳ４の処理を再実行する。
【００６４】
ステップＳ５において、第１中間鍵生成部１３は、ステップＳ４において受信した鍵が、１次中間鍵ＭＦ２であるか否かを判定する。第１中間鍵生成部１３は、この判定がＹＥＳの場合、処理をステップＳ６に移し、この判定がＮＯの場合、処理をステップＳ９に移す。
【００６５】
ステップＳ６において、第１中間鍵生成部１３は、１次中間鍵ＭＦ２、除数Ｂ、及び第１秘密鍵Ｓ１に基づいて、２次中間鍵ＭＳ１を生成する。すなわち、第１中間鍵生成部１３は、１次中間鍵ＭＦ２を底とし、第１秘密鍵Ｓ１を指数としたべき乗を、除数Ｂで除算した場合の剰余を２次中間鍵ＭＳ１とする。２次中間鍵ＭＳ１を生成する詳細な処理は、第１共通鍵生成装置１０のべき剰余算出部５０において行われる。
【００６６】
ステップＳ７において、第１通信部１１は、ステップＳ６において生成された２次中間鍵ＭＳ１を第３共通鍵生成装置３０に送信する。
【００６７】
ステップＳ８において、第１共通鍵生成装置１０の制御部は、第１通信部１１により、全ての鍵、すなわち、１次中間鍵ＭＦ２、１次中間鍵ＭＦ３及び２次中間鍵ＭＳ３を受信したか否かを判定する。第１共通鍵生成装置１０の制御部は、この判定がＹＥＳの場合、処理を終了し、この判定がＮＯの場合、処理をステップＳ４に移す。
【００６８】
ステップＳ９において、第１中間鍵生成部１３は、ステップＳ４において受信した鍵が、１次中間鍵ＭＦ３であるか否かを判定する。第１中間鍵生成部１３は、この判定がＹＥＳの場合、処理をステップＳ１０に移し、この判定がＮＯの場合、処理をステップＳ１２に移す。
【００６９】
ステップＳ１０において、第１中間鍵生成部１３は、１次中間鍵ＭＦ３、除数Ｂ、及び第１秘密鍵Ｓ１に基づいて、２次中間鍵ＭＳ２を生成する。すなわち、第１中間鍵生成部１３は、１次中間鍵ＭＦ３を底とし、第１秘密鍵Ｓ１を指数としたべき乗を、除数Ｂで除算した場合の剰余を２次中間鍵ＭＳ２とする。２次中間鍵ＭＳ２を生成する詳細な処理は、第１共通鍵生成装置１０のべき剰余算出部５０において行われる。
【００７０】
ステップＳ１１において、第１通信部１１は、ステップＳ６において生成された２次中間鍵ＭＳ２を第２共通鍵生成装置２０に送信する。この処理が終了すると、ステップＳ８に移る。
【００７１】
ステップＳ１２において、第１共通鍵生成部１４は、２次中間鍵ＭＳ３、除数Ｂ、及び第１秘密鍵Ｓ１に基づいて、共通鍵Ｃを生成する。すなわち、ステップＳ１２の処理が実行される場合、第１通信部１１は、ステップＳ４において、２次中間鍵ＭＳ３を受信していることとなる。この場合、第１共通鍵生成部１４は、２次中間鍵ＭＳ３を底とし、第１秘密鍵Ｓ１を指数としたべき乗を、除数Ｂで除算した場合の剰余を共通鍵Ｃとする。共通鍵Ｃを生成する詳細な処理は、第１共通鍵生成装置１０のべき剰余算出部５０において行われる。この処理が終了すると、ステップＳ８に移る。
【００７２】
図５は、本実施形態に係るべき剰余算出部５０における処理の流れを示すフローチャートである。
【００７３】
ステップＳ２１（入力受付ステップ）において、入力受付部５１は、底、除数、指数の入力を受け付ける。ここで受け付けた底を底Ａｉとし、除数を除数Ｂとし、指数を指数ｅとする。
【００７４】
ステップＳ２２（初期設定ステップ）において、初期設定部５２は、第１中間値ＡＴの初期値をステップＳ２１において受け付けた底Ａｉとし、第２中間値ＭＴの初期値を１に設定する。
【００７５】
ステップＳ２３（変換ステップ）において、変換部５３は、ステップＳ２１において受け付けた指数ｅを、２進数に変換する。
【００７６】
ステップＳ２４（計数ステップ）において、計数部５４は、ステップＳ２３において変換された、２進数で表現された指数ｅのビット数を計数する。
【００７７】
ステップＳ２５（基数算出ステップ）において、基数算出部５５は、第１中間値ＡＴを更新する。具体的には、基数算出部５５は、２進数で表現された指数ｅの右端の値（ビット）が１である場合、第１中間値ＡＴを第２中間値ＭＴで乗算して得られた値を除数Ｂｉで除算して剰余を算出する。続いて、基数算出部５５は、この算出された剰余を第１中間値ＡＴとすることにより、第１中間値ＡＴを更新する。ここで、基数算出部５５により行われる第１中間値ＡＴと第２中間値ＭＴとの乗算は、第１中間値ＡＴ及び第２中間値ＭＴそれぞれを１０のべき乗の和に変換し、この変換した第１中間値ＡＴ及び第２中間値ＭＴを乗算することで行われる。
【００７８】
ステップＳ２６（剰余算出ステップ）において、剰余算出部５６は、第２中間値ＭＴを更新する。具体的には、剰余算出部５６は、２進数に変換された指数ｅの右端の値（ビット）にかかわらず、第１中間値ＡＴを２乗した値を除数Ｂｉで除算した場合の剰余を第２中間値ＭＴとすることにより、第２中間値ＭＴを更新する。なお、第１中間値ＡＴの２乗の計算は、第１中間値ＡＴと第２中間値ＭＴとの乗算と同様に、第１中間値ＡＴを１０のべき乗の和に変換し、この変換した第１中間値ＡＴを２乗することにより計算される。
【００７９】
ステップＳ２７（シフトステップ）において、シフト部５７は、２進数に変換された指数ｅを１ビット右に論理シフトする演算（論理シフト演算）を行う。
【００８０】
ステップＳ２８（反復実行ステップ）において、反復実行部５８は、ステップＳ２５〜ステップＳ２７の処理が、反復回数行われたか判定する。ここで、反復回数は、ステップＳ２４において計数された値である。反復実行部５８は、この判定がＹＥＳの場合、処理をステップＳ２９に移し、この判定がＮＯの場合、処理をステップＳ２５に移す。
【００８１】
ステップＳ２９（出力ステップ）において、出力部５９は、第２中間値ＭＴを剰余として出力する。
【００８２】
図６は、本実施形態に係る第２共通鍵生成装置２０における共通鍵生成に係る処理の流れを示すフローチャートである。
【００８３】
ステップＳ３１において、第２通信部２１は、第１共通鍵生成装置１０から、基数Ａ、除数Ｂ、及び１次中間鍵ＭＦ１を受信する。
【００８４】
ステップＳ３２において、第２鍵情報生成部２２は、第２秘密鍵Ｓ２を生成する。
【００８５】
ステップＳ３３において、第２中間鍵生成部２３は、ステップＳ３１において受信した基数Ａ、除数Ｂ、及びステップＳ３２において生成した第２秘密鍵Ｓ２に基づいて、１次中間鍵ＭＦ２を生成する。すなわち、第２中間鍵生成部２３は、基数Ａを底とし、第２秘密鍵Ｓ２を指数としたべき乗を、除数Ｂで除算した場合の剰余を１次中間鍵ＭＦ２とする。１次中間鍵ＭＦ２を生成する詳細な処理は、第２共通鍵生成装置２０のべき剰余算出部５０において行われる。
【００８６】
ステップＳ３４において、第２通信部２１は、ステップＳ３３において生成された１次中間鍵ＭＦ２を第３共通鍵生成装置３０及び第１共通鍵生成装置１０に送信する。
【００８７】
ステップＳ３５において、第２中間鍵生成部２３は、１次中間鍵ＭＦ１、除数Ｂ、及び第２秘密鍵Ｓ２に基づいて、２次中間鍵ＭＳ１を生成する。すなわち、第２中間鍵生成部２３は、１次中間鍵ＭＦ１を底とし、第２秘密鍵Ｓ２を指数としたべき乗を、除数Ｂで除算した場合の剰余を２次中間鍵ＭＳ１とする。２次中間鍵ＭＳ１を生成する詳細な処理は、第２共通鍵生成装置２０のべき剰余算出部５０において行われる。
【００８８】
ステップＳ３６において、第２通信部２１は、ステップＳ３５において生成された２次中間鍵ＭＳ１を第３共通鍵生成装置３０に送信する。
【００８９】
ステップＳ３７において、第２共通鍵生成装置２０の制御部は、第２通信部２１により、第３共通鍵生成装置３０から、１次中間鍵ＭＦ３を受信したか否かを判定する。第２共通鍵生成装置２０の制御部は、この判定がＹＥＳの場合、処理をステップＳ３８に移し、この処理がＮＯの場合、処理をステップＳ４１に移す。
【００９０】
ステップＳ３８において、第２中間鍵生成部２３は、１次中間鍵ＭＦ３、除数Ｂ、及び第２秘密鍵Ｓ２に基づいて、２次中間鍵ＭＳ３を生成する。すなわち、第２中間鍵生成部２３は、１次中間鍵ＭＦ３を底とし、第２秘密鍵Ｓ２を指数としたべき乗を、除数Ｂで除算した場合の剰余を２次中間鍵ＭＳ３とする。２次中間鍵ＭＳ３を生成する詳細な処理は、第２共通鍵生成装置２０のべき剰余算出部５０において行われる。
【００９１】
ステップＳ３９において、第２通信部２１は、ステップＳ３８において生成された２次中間鍵ＭＳ３を第１共通鍵生成装置１０に送信する。
【００９２】
ステップＳ４０において、第２共通鍵生成装置２０の制御部は、第２通信部２１により、全ての鍵、すなわち、１次中間鍵ＭＦ１、１次中間鍵ＭＦ３及び２次中間鍵ＭＳ２を受信したか否かを判定する。第２共通鍵生成装置２０の制御部は、この判定がＹＥＳの場合、処理を終了し、この判定がＮＯの場合、処理をステップＳ３７に移す。
【００９３】
ステップＳ４１において、第２共通鍵生成装置２０の制御部は、第２通信部２１により、２次中間鍵ＭＳ２を受信したか否かを判定する。第２共通鍵生成装置２０の制御部は、この判定がＹＥＳの場合、処理をステップＳ４２に移し、この処理がＮＯの場合、処理をステップＳ４０に移す。
【００９４】
ステップＳ４２において、第２共通鍵生成部２４は、２次中間鍵ＭＳ２、除数Ｂ、及び第２秘密鍵Ｓ２に基づいて、共通鍵Ｃを生成する。すなわち、第２共通鍵生成部２４は、２次中間鍵ＭＳ２を底とし、第２秘密鍵Ｓ２を指数としたべき乗を、除数Ｂで除算した場合の剰余を共通鍵Ｃとする。共通鍵Ｃを生成する詳細な処理は、第２共通鍵生成装置２０のべき剰余算出部５０において行われる。この処理が終了すると、ステップＳ４０に移る。
【００９５】
図７は、本実施形態に係る第３共通鍵生成装置３０における共通鍵生成に係る処理の流れを示すフローチャートである。
【００９６】
ステップＳ５１において、第３通信部３１は、第１共通鍵生成装置１０から、基数Ａ、除数Ｂ、及び１次中間鍵ＭＦ１を受信する。
【００９７】
ステップＳ５２において、第３鍵情報生成部３２は、第３秘密鍵Ｓ３を生成する。
【００９８】
ステップＳ５３において、第３中間鍵生成部３３は、ステップＳ５１において受信した基数Ａ、除数Ｂ、及びステップＳ５２において生成した第３秘密鍵Ｓ３に基づいて、１次中間鍵ＭＦ３を生成する。すなわち、第３中間鍵生成部３３は、基数Ａを底とし、第３秘密鍵Ｓ３を指数としたべき乗を、除数Ｂで除算した場合の剰余を１次中間鍵ＭＦ３とする。１次中間鍵ＭＦ３を生成する詳細な処理は、第３共通鍵生成装置３０のべき剰余算出部５０において行われる。
【００９９】
ステップＳ５４において、第３通信部３１は、ステップＳ５３において生成された１次中間鍵ＭＦ３を第１共通鍵生成装置１０及び第２共通鍵生成装置２０に送信する。
【０１００】
ステップＳ５５において、第３中間鍵生成部３３は、１次中間鍵ＭＦ１、除数Ｂ、及び第３秘密鍵Ｓ３に基づいて、２次中間鍵ＭＳ２を生成する。すなわち、第３中間鍵生成部３３は、１次中間鍵ＭＦ１を底とし、第３秘密鍵Ｓ３を指数としたべき乗を、除数Ｂで除算した場合の剰余を２次中間鍵ＭＳ２とする。２次中間鍵ＭＳ２を生成する詳細な処理は、第３共通鍵生成装置３０のべき剰余算出部５０において行われる。
【０１０１】
ステップＳ５６において、第３通信部３１は、ステップＳ５５において生成された２次中間鍵ＭＳ２を第２共通鍵生成装置２０に送信する。
【０１０２】
ステップＳ５７において、第３共通鍵生成装置３０の制御部は、第３通信部３１により、第２共通鍵生成装置２０から、１次中間鍵ＭＦ２を受信したか否かを判定する。第３共通鍵生成装置３０の制御部は、この判定がＹＥＳの場合、処理をステップＳ５８に移し、この処理がＮＯの場合、処理をステップＳ６１に移す。
【０１０３】
ステップＳ５８において、第３中間鍵生成部３３は、１次中間鍵ＭＦ２、除数Ｂ、及び第３秘密鍵Ｓ３に基づいて、２次中間鍵ＭＳ３を生成する。すなわち、第３中間鍵生成部３３は、１次中間鍵ＭＦ２を底とし、第３秘密鍵Ｓ３を指数としたべき乗を、除数Ｂで除算した場合の剰余を２次中間鍵ＭＳ３とする。２次中間鍵ＭＳ３を生成する詳細な処理は、第３共通鍵生成装置３０のべき剰余算出部５０において行われる。
【０１０４】
ステップＳ５９において、第３通信部３１は、ステップＳ５８において生成された２次中間鍵ＭＳ３を第１共通鍵生成装置１０に送信する。
【０１０５】
ステップＳ６０において、第３共通鍵生成装置３０の制御部は、第３通信部３１により、全ての鍵、すなわち、１次中間鍵ＭＦ１、１次中間鍵ＭＦ２及び２次中間鍵ＭＳ１を受信したか否かを判定する。第３共通鍵生成装置３０の制御部は、この判定がＹＥＳの場合、処理を終了し、この判定がＮＯの場合、処理をステップＳ５７に移す。
【０１０６】
ステップＳ６１において、第３共通鍵生成装置３０の制御部は、第３通信部３１により、２次中間鍵ＭＳ１を受信したか否かを判定する。第３共通鍵生成装置３０の制御部は、この判定がＹＥＳの場合、処理をステップＳ６２に移し、この処理がＮＯの場合、処理をステップＳ６０に移す。
【０１０７】
ステップＳ６２において、第３共通鍵生成部３４は、２次中間鍵ＭＳ１、除数Ｂ、及び第３秘密鍵Ｓ３に基づいて、共通鍵Ｃを生成する。すなわち、第３共通鍵生成部３４は、２次中間鍵ＭＳ１を底とし、第３秘密鍵Ｓ３を指数としたべき乗を、除数Ｂで除算した場合の剰余を共通鍵Ｃとする。共通鍵Ｃを生成する詳細な処理は、第３共通鍵生成装置３０のべき剰余算出部５０において行われる。この処理が終了すると、ステップＳ６０に移る。
【０１０８】
以上のように、本実施形態によれば、第１共通鍵生成装置１０は、１次中間鍵ＭＦ２を底とし、第１秘密鍵Ｓ１を指数としたべき乗を、除数Ｂで除算した場合の剰余を２次中間鍵ＭＳ１として第３共通鍵生成装置３０に送信し、１次中間鍵ＭＦ３を底とし、第１秘密鍵Ｓ１を指数としたべき乗を、除数Ｂで除算した場合の剰余を２次中間鍵ＭＳ２とし、第２共通鍵生成装置２０に送信する。また、第２共通鍵生成装置２０は、１次中間鍵ＭＦ３を底とし、第２秘密鍵Ｓ２を指数としたべき乗を、除数Ｂで除算した場合の剰余を２次中間鍵ＭＳ３として第１共通鍵生成装置１０に送信し、１次中間鍵ＭＦ１を底とし、第２秘密鍵Ｓ２を指数としたべき乗を、除数Ｂで除算した場合の剰余を２次中間鍵ＭＳ１とし、第３共通鍵生成装置３０に送信する。また、第３共通鍵生成装置３０は、１次中間鍵ＭＦ１を底とし、第３秘密鍵Ｓ３を指数としたべき乗を、除数Ｂで除算した場合の剰余を２次中間鍵ＭＳ２として第２共通鍵生成装置２０に送信し、１次中間鍵ＭＦ２を底とし、第３秘密鍵Ｓ３を指数としたべき乗を、除数Ｂで除算した場合の剰余を２次中間鍵ＭＳ３とし、第１共通鍵生成装置１０に送信する。続いて、第１共通鍵生成装置１０は、２次中間鍵ＭＳ３を底とし、第１秘密鍵Ｓ１を指数としたべき乗を、除数Ｂで除算した場合の剰余を共通鍵Ｃとする。また、第２共通鍵生成装置２０は、２次中間鍵ＭＳ２を底とし、第２秘密鍵Ｓ２を指数としたべき乗を、除数Ｂで除算した場合の剰余を共通鍵Ｃとする。また、第３共通鍵生成装置３０は、２次中間鍵ＭＳ１を底とし、第３秘密鍵Ｓ３を指数としたべき乗を、除数Ｂで除算した場合の剰余を共通鍵Ｃとする。
【０１０９】
ここで、基数Ａを底とし秘密鍵を指数としたべき乗は、以下の（３）式で表される。
【数３】
ただし、Ｘ１は、基数Ａを底とし第１秘密鍵Ｓ１を指数としたべき乗を除数Ｂで除算した場合の商とし、Ｘ２は、基数Ａを底とし第２秘密鍵Ｓ２を指数としたべき乗を除数Ｂで除算した場合の商とし、Ｘ３は、基数Ａを底とし第３秘密鍵Ｓ３を指数としたべき乗を除数Ｂで除算した場合の商とする。
【０１１０】
また、１次中間鍵を底とし秘密鍵を指数としたべき乗は、以下の（４）式で表される。
【数４】
ただし、Ｘ４は、１次中間鍵ＭＦ１を底とし第１秘密鍵Ｓ１を指数としたべき乗を除数Ｂで除算した場合の商とし、Ｘ５は、１次中間鍵ＭＦ２を底とし第２秘密鍵Ｓ２を指数としたべき乗を除数Ｂで除算した場合の商とし、Ｘ６は、１次中間鍵ＭＦ３を底とし第３秘密鍵Ｓ３を指数としたべき乗を除数Ｂで除算した場合の商とする。
【０１１１】
また、指数法則により、以下の（５）、（６）式が成り立つ。
【数５】
【０１１２】
【数６】
【０１１３】
ここで、（６）式に（３）式を代入すると、（７）式が成り立つ。
【数７】
【０１１４】
ここで、（７）式を部分的に展開すると、（８）式が成り立つ。
【数８】
【０１１５】
ここで、（８）式に対して、（４）式を代入すると、（９）式が成り立つ。
【数９】
【０１１６】
そして、（９）式のそれぞれの辺について、除数Ｂで除算した場合の剰余は、共通鍵Ｃとなる。
【０１１７】
よって、第１共通鍵生成装置１０、第２共通鍵生成装置２０、及び第３共通鍵生成装置３０それぞれにおいて、秘密鍵を交換することなく共通鍵を生成することができる。ここで、除数Ｂが桁数の大きい素数である場合、基数Ａ、除数Ｂ、並びに１次中間鍵、２次中間鍵を知っていたとしても、これらの値から、共通鍵Ｃを求めるには、膨大な計算量が必要となる。よって、共通鍵生成システム１は、３者間で安全に共通鍵を共有することができる。
【０１１８】
また、共通鍵生成システム１は、べき剰余算出部５０において第１中間値ＡＴ及び第２中間値ＭＴを、１０のべき乗により構成される多項式に変換し、これら多項式を乗算して、展開することにより、第１中間値ＡＴと第２中間値ＭＴとの乗算、及び第１中間値ＡＴの２乗の計算を行う。
【０１１９】
このようにすることで、共通鍵生成システム１は、第１中間値ＡＴと第２中間値ＭＴが長大桁数である場合、この長大桁数よりも桁数が小さい項を複数含む多項式の乗算により、第１中間値ＡＴと第２中間値ＭＴの乗算や第１中間値ＡＴの２乗の計算を行うことができる。このため、共通鍵生成システム１は、第１共通鍵生成装置１０、第２共通鍵生成装置２０、及び第３共通鍵生成装置３０において、市販の表計算ソフト等を利用して共通鍵を生成する場合に、この表計算ソフト等で有効桁数が限られていても、桁あふれ等による情報落ちを防ぐことができ、問題なく共通鍵を生成することができる。
【０１２０】
以上、本発明の実施形態について説明したが、本発明は本実施形態に限定されるものではなく、本発明の目的を達成できる範囲での変形、改良等は本発明に含まれるものである。
【０１２１】
本実施形態では、第３共通鍵生成装置３０において、１次中間鍵ＭＦ３を生成し、第１共通鍵生成装置１０において、１次中間鍵ＭＦ３を用いて２次中間鍵ＭＳ２を生成するとともに、第２共通鍵生成装置２０において、１次中間鍵ＭＦ３を用いて２次中間鍵ＭＳ３を生成することとしたが、このように１次中間鍵ＭＦ３、２次中間鍵ＭＳ２、及び２次中間鍵ＭＳ３を生成しなくてもよい。すなわち、２次中間鍵ＭＳ２は、第２共通鍵生成装置２０において、１次中間鍵ＭＦ１を用いて生成することができ、２次中間鍵ＭＳ３は、第３共通鍵生成装置３０において、１次中間鍵ＭＦ２を用いて生成することができる。このため、２次中間鍵ＭＳ２、２次中間鍵ＭＳ３を冗長に生成しないようにしてもよい。
【０１２２】
すなわち、共通鍵生成システム１は、第１共通鍵生成装置１０、第２共通鍵生成装置２０、及び第３共通鍵生成装置３０のいずれかにおいて、２次中間鍵ＭＳ１、２次中間鍵ＭＳ２、及び２次中間鍵ＭＳ３をそれぞれ１個のみ生成できるように構成するようにしてもよい。このようにすることで、第１共通鍵生成装置１０、第２共通鍵生成装置２０、及び第３共通鍵生成装置３０間におけるやりとりを減らして通信量を削減することができる。
【符号の説明】
【０１２３】
１ 共通鍵生成システム
１０ 第１共通鍵生成装置
１１ 第１通信部
１２ 第１鍵情報生成部
１３ 第１中間鍵生成部
１４ 第１共通鍵生成部
２０ 第２共通鍵生成装置
２１ 第２通信部
２２ 第２鍵情報生成部
２３ 第２中間鍵生成部
２４ 第２共通鍵生成部
３０ 第３共通鍵生成装置
３１ 第３通信部
３２ 第３鍵情報生成部
３３ 第３中間鍵生成部
３４ 第３共通鍵生成部
５０ べき剰余算出部
５１ 入力受付部
５２ 初期設定部
５３ 変換部
５４ 計数部
５５ 基数算出部
５６ 剰余算出部
５７ シフト部
５８ 反復実行部
５９ 出力部
【技術分野】
【０００１】
本発明は、共通鍵生成システム及び共通鍵生成方法に関する。
【背景技術】
【０００２】
近年、インターネット等のネットワークをデータの交換手段として利用することが急速に広まっている。しかしながら、インターネット等のネットワークでは、データを交換する際に複数のサーバ及び通信回線を経由してデータが転送される。このため、データを転送するサーバ及び通信回線等では、データの盗聴や、データの改ざんや、なりすましをすることが可能となり、セキュリティ問題に発展している。このようなセキュリティ問題に対応するため、暗号化技術が提案されており、例えば、簡易的な暗号化方式として、共通鍵暗号方式が知られている。
【０００３】
共通鍵暗号方式では、例えば、特許文献１に示されるように、生成した共通鍵を、２者間で所有する。続いて、送信者は、共通鍵を用いてデータの暗号化を行い、暗号化されたデータを閲覧者に送信する。閲覧者は、データを受信すると、共通鍵を用いて暗号化されたデータを復号する。
【先行技術文献】
【特許文献】
【０００４】
【特許文献１】特開２０００−２７８２５８号公報
【発明の概要】
【発明が解決しようとする課題】
【０００５】
しかしながら、特許文献１に示される共通鍵交換方式は、２者間において共通鍵を生成する方式であり、３者間において、共通鍵を生成する方法については示されていない。このため、３者間において、安全に共通鍵を生成することができる共通鍵生成システム及び共通鍵生成方法の提供が望まれている。
【０００６】
本発明は、共通鍵の受け渡しを行わずに、３者間で安全に共通鍵を共有することができる共通鍵生成システム及び共通鍵生成方法を提供することを目的とする。
【課題を解決するための手段】
【０００７】
本発明に係る共通鍵生成システムは、第１共通鍵生成装置、第２共通鍵生成装置、及び第３共通鍵生成装置を備え、前記第１共通鍵生成装置、前記第２共通鍵生成装置、及び第３共通鍵生成装置において共通鍵を生成する共通鍵生成システムであって、前記第１共通鍵生成装置は、基数、除数、及び第１秘密鍵を生成する第１鍵情報生成手段と、前記基数を底とし、前記第１秘密鍵を指数としたべき乗を、前記除数で除算した場合の剰余を算出し、当該剰余を第１の１次中間鍵とする第１中間鍵生成手段と、前記基数、前記除数、及び前記第１の１次中間鍵を前記第２共通鍵生成装置及び前記第３共通鍵生成装置に送信する第１送信手段と、を備え、前記第２共通鍵生成装置は、前記第１共通鍵生成装置から、前記基数、前記除数、及び前記第１の１次中間鍵を受信する第２受信手段と、第２秘密鍵を生成する第２鍵情報生成手段と、前記基数を底とし、前記第２秘密鍵を指数としたべき乗を、前記除数で除算した場合の剰余を算出し、当該剰余を第２の１次中間鍵とする第２中間鍵生成手段と、前記第２の１次中間鍵を前記第１共通鍵生成装置及び前記第３共通鍵生成装置に送信する第２送信手段と、を備え、前記第３共通鍵生成装置は、前記第１共通鍵生成装置から、前記基数、前記除数、及び前記第１の１次中間鍵を受信する第３受信手段と、第３秘密鍵を生成する第３鍵情報生成手段と、前記基数を底とし、前記第３秘密鍵を指数としたべき乗を、前記除数で除算した場合の剰余を算出し、当該剰余を第３の１次中間鍵とする第３中間鍵生成手段と、前記第３の１次中間鍵を前記第１共通鍵生成装置及び前記第２共通鍵生成装置に送信する第３送信手段と、を備え、前記第１共通鍵生成装置は、前記第２共通鍵生成装置から前記第２の１次中間鍵を受信するとともに、前記第３共通鍵生成装置から前記第３の１次中間鍵を受信する第１受信手段を更に備え、前記第１中間鍵生成手段は、前記第１受信手段により受信した前記第２の１次中間鍵を底とし、前記第１秘密鍵を指数としたべき乗を、前記除数で除算した場合の剰余を算出し、当該剰余を第１の２次中間鍵とするとともに、前記第１受信手段により受信した前記第３の１次中間鍵を底とし、前記第１秘密鍵を指数としたべき乗を、前記除数で除算した場合の剰余を算出し、当該剰余を第２の２次中間鍵とし、前記第１送信手段は、前記第２の２次中間鍵を前記第２共通鍵生成装置に送信するとともに、前記第１の２次中間鍵を前記第３共通鍵生成装置に送信し、前記第２受信手段は、第３共通鍵生成装置から前記第３の１次中間鍵を更に受信し、前記第２中間鍵生成手段は、前記第２受信手段により受信した前記第３の１次中間鍵を底とし、前記第２秘密鍵を指数としたべき乗を、前記除数で除算した場合の剰余を算出し、当該剰余を第３の２次中間鍵とするとともに、前記第２受信手段により受信した前記第１の１次中間鍵を底とし、前記第２秘密鍵を指数としたべき乗を、前記除数で除算した場合の剰余を算出し、当該剰余を前記第１の２次中間鍵とし、前記第２送信手段は、前記第３の２次中間鍵を前記第１共通鍵生成装置に送信するとともに、前記第１の２次中間鍵を前記第３共通鍵生成装置に送信し、前記第３受信手段は、第２共通鍵生成装置から前記第２の１次中間鍵を更に受信し、前記第３中間鍵生成手段は、前記第３受信手段により受信した前記第１の１次中間鍵を底とし、前記第３秘密鍵を指数としたべき乗を、前記除数で除算した場合の剰余を算出し、当該剰余を前記第２の２次中間鍵とするとともに、前記第３受信手段により受信した前記第２の１次中間鍵を底とし、前記第３秘密鍵を指数としたべき乗を、前記除数で除算した場合の剰余を算出し、当該剰余を前記第３の２次中間鍵とし、前記第３送信手段は、前記第３の２次中間鍵を前記第１共通鍵生成装置に送信するとともに、前記第２の２次中間鍵を前記第２共通鍵生成装置に送信し、前記第１受信手段は、前記第２共通鍵生成装置から前記第３の２次中間鍵を受信するとともに、前記第３共通鍵生成装置から前記第３の２次中間鍵を受信し、前記第１共通鍵生成装置は、前記第１受信手段により受信した前記第３の２次中間鍵を底とし、前記第１秘密鍵を指数としたべき乗を、前記除数で除算した場合の剰余を算出し、当該剰余を共通鍵とする第１共通鍵生成手段を更に備え、前記第２受信手段は、前記第３共通鍵生成装置から前記第２の２次中間鍵を受信するとともに、前記第１共通鍵生成装置から前記第２の２次中間鍵を受信し、前記第２共通鍵生成装置は、前記第２受信手段により受信した前記第２の２次中間鍵を底とし、前記第２秘密鍵を指数としたべき乗を、前記除数で除算した場合の剰余を算出し、当該剰余を前記共通鍵とする第２共通鍵生成手段を更に備え、前記第３受信手段は、前記第１共通鍵生成装置から前記第１の２次中間鍵を受信するとともに、前記第２共通鍵生成装置から前記第１の２次中間鍵を受信し、前記第３共通鍵生成装置は、前記第３受信手段により受信した前記第１の２次中間鍵を底とし、前記第３秘密鍵を指数としたべき乗を、前記除数で除算した場合の剰余を算出し、当該剰余を前記共通鍵とする第３共通鍵生成手段を更に備える。
【０００８】
本発明に係る共通鍵生成方法は、第１共通鍵生成装置、第２共通鍵生成装置、及び第３共通鍵生成装置が共通鍵を生成する共通鍵生成方法であって、前記第１共通鍵生成装置が、基数、除数、及び第１秘密鍵を生成するステップと、前記第１共通鍵生成装置が、前記基数を底とし、前記第１秘密鍵を指数としたべき乗を、前記除数で除算した場合の剰余を算出し、当該剰余を第１の１次中間鍵とするステップと、前記第１共通鍵生成装置が、前記基数、前記除数、及び前記第１の１次中間鍵を前記第２共通鍵生成装置及び前記第３共通鍵生成装置に送信するステップと、前記第２共通鍵生成装置が、前記第１共通鍵生成装置から、前記基数、前記除数、及び前記第１の１次中間鍵を受信するステップと、前記第２共通鍵生成装置が、第２秘密鍵を生成するステップと、前記第２共通鍵生成装置が、前記基数を底とし、前記第２秘密鍵を指数としたべき乗を、前記除数で除算した場合の剰余を算出し、当該剰余を第２の１次中間鍵とするステップと、前記第２共通鍵生成装置が、前記第２の１次中間鍵を前記第１共通鍵生成装置及び前記第３共通鍵生成装置に送信するステップと、前記第３共通鍵生成装置が、前記第１共通鍵生成装置から、前記基数、前記除数、及び前記第１の１次中間鍵を受信するステップと、前記第３共通鍵生成装置が、第３秘密鍵を生成するステップと、前記第３共通鍵生成装置が、前記基数を底とし、前記第３秘密鍵を指数としたべき乗を、前記除数で除算した場合の剰余を算出し、当該剰余を第３の１次中間鍵とするステップと、前記第３共通鍵生成装置が、前記第３の１次中間鍵を前記第１共通鍵生成装置及び前記第２共通鍵生成装置に送信するステップと、前記第１共通鍵生成装置が、前記第２共通鍵生成装置から前記第２の１次中間鍵を受信するステップと、前記第１共通鍵生成装置が、前記第２の１次中間鍵を底とし、前記第１秘密鍵を指数としたべき乗を、前記除数で除算した場合の剰余を算出し、当該剰余を第１の２次中間鍵とするステップと、前記第１共通鍵生成装置が、前記第１の２次中間鍵を前記第３共通鍵生成装置に送信するステップと、前記第１共通鍵生成装置が、前記第３共通鍵生成装置から前記第３の１次中間鍵を受信するステップと、前記第１共通鍵生成装置が、前記第３の１次中間鍵を底とし、前記第１秘密鍵を指数としたべき乗を、前記除数で除算した場合の剰余を算出し、当該剰余を第２の２次中間鍵とするステップと、前記第１共通鍵生成装置が、前記第２の２次中間鍵を前記第２共通鍵生成装置に送信するステップと、前記第２共通鍵生成装置が、前記第１の１次中間鍵を底とし、前記第２秘密鍵を指数としたべき乗を、前記除数で除算した場合の剰余を算出し、当該剰余を第１の２次中間鍵とするステップと、前記第２共通鍵生成装置が、前記第１の２次中間鍵を前記第３共通鍵生成装置に送信するステップと、前記第２共通鍵生成装置が、前記第３共通鍵生成装置から前記第３の１次中間鍵を受信するステップと、前記第２共通鍵生成装置が、前記第３の１次中間鍵を底とし、前記第２秘密鍵を指数としたべき乗を、前記除数で除算した場合の剰余を算出し、当該剰余を第３の２次中間鍵とするステップと、前記第２共通鍵生成装置が、前記第３の２次中間鍵を前記第１共通鍵生成装置に送信するステップと、前記第３共通鍵生成装置が、前記第１の１次中間鍵を底とし、前記第３秘密鍵を指数としたべき乗を、前記除数で除算した場合の剰余を算出し、当該剰余を第２の２次中間鍵とするステップと、前記第３共通鍵生成装置が、前記第２の２次中間鍵を前記第２共通鍵生成装置に送信するステップと、前記第３共通鍵生成装置が、前記第２共通鍵生成装置から前記第２の１次中間鍵を受信するステップと、前記第３共通鍵生成装置が、前記第２の１次中間鍵を底とし、前記第３秘密鍵を指数としたべき乗を、前記除数で除算した場合の剰余を算出し、当該剰余を第３の２次中間鍵とするステップと、前記第３共通鍵生成装置が、前記第３の２次中間鍵を前記第１共通鍵生成装置に送信するステップと、前記第１共通鍵生成装置が、前記第２共通鍵生成装置又は前記第３共通鍵生成装置から前記第３の２次中間鍵を受信するステップと、前記第１共通鍵生成装置が、前記第３の２次中間鍵を底とし、前記第１秘密鍵を指数としたべき乗を、前記除数で除算した場合の剰余を算出し、当該剰余を共通鍵とするステップと、前記第２共通鍵生成装置が、前記第３共通鍵生成装置又は前記第１共通鍵生成装置から前記第２の２次中間鍵を受信するステップと、前記第２共通鍵生成装置が、前記第２の２次中間鍵を底とし、前記第２秘密鍵を指数としたべき乗を、前記除数で除算した場合の剰余を算出し、当該剰余を前記共通鍵とするステップと、前記第３共通鍵生成装置が、前記第１共通鍵生成装置又は前記第２共通鍵生成装置から前記第１の２次中間鍵を受信するステップと、前記第３共通鍵生成装置が、前記第１の２次中間鍵を底とし、前記第３秘密鍵を指数としたべき乗を、前記除数で除算した場合の剰余を算出し、当該剰余を前記共通鍵とするステップと、を含む。
【発明の効果】
【０００９】
本発明によれば、共通鍵の受け渡しを行わずに、３者間で安全に共通鍵を共有することができる。
【図面の簡単な説明】
【００１０】
【図１】本実施形態に係る共通鍵生成システムの全体概要を示す図である。
【図２】本実施形態に係る共通鍵生成装置の機能構成を示す図である。
【図３】本実施形態に係るべき剰余算出部の機能構成を示す図である。
【図４】本実施形態に係る第１共通鍵生成装置における共通鍵生成に係る処理の流れを示すフローチャートである。
【図５】本実施形態に係るべき剰余算出部における処理の流れを示すフローチャートである。
【図６】本実施形態に係る第２共通鍵生成装置における共通鍵生成に係る処理の流れを示すフローチャートである。
【図７】本実施形態に係る第３共通鍵生成装置における共通鍵生成に係る処理の流れを示すフローチャートである。
【発明を実施するための形態】
【００１１】
以下、本発明の実施形態について図を参照しながら説明する。
【００１２】
図１は、本実施形態に係る共通鍵生成システム１の全体概要を示す図である。共通鍵生成システム１は、３台の共通鍵生成装置間で共通鍵を生成するシステムである。共通鍵生成システム１は、第１共通鍵生成装置１０と、第２共通鍵生成装置２０と、第３共通鍵生成装置３０と、を備える。第１共通鍵生成装置１０と、第２共通鍵生成装置２０と、第３共通鍵生成装置３０とは、ＬＡＮ（Ｌｏｃａｌ Ａｒｅａ Ｎｅｔｗｏｒｋ）やインターネット等のコンピュータネットワークにより構成される通信ネットワークＮにより、通信可能に接続されている。
【００１３】
この第１共通鍵生成装置１０では、基数Ａ、除数Ｂ、及び第１秘密鍵Ｓ１を生成し、基数Ａ、除数Ｂ、及び第１秘密鍵Ｓ１に基づいて第１の１次中間鍵として１次中間鍵ＭＦ１を生成し、第２共通鍵生成装置２０及び第３共通鍵生成装置３０に、基数Ａ、除数Ｂ、及び１次中間鍵ＭＦ１を送信する。また、第２共通鍵生成装置２０では、第２秘密鍵Ｓ２を生成し、基数Ａ、除数Ｂ、及び第２秘密鍵Ｓ２に基づいて第２の１次中間鍵として１次中間鍵ＭＦ２を生成し、第３共通鍵生成装置３０及び第１共通鍵生成装置１０に、１次中間鍵ＭＦ２を送信する。また、第３共通鍵生成装置３０では、第３秘密鍵Ｓ３を生成し、基数Ａ、除数Ｂ、及び第３秘密鍵Ｓ３に基づいて第３の１次中間鍵として１次中間鍵ＭＦ３を生成し、第１共通鍵生成装置１０及び第２共通鍵生成装置２０に、１次中間鍵ＭＦ３を送信する。
【００１４】
また、第１共通鍵生成装置１０は、第２共通鍵生成装置２０から、１次中間鍵ＭＦ２を受信するとともに、第３共通鍵生成装置３０から、１次中間鍵ＭＦ３を受信し、１次中間鍵ＭＦ２、除数Ｂ、及び第１秘密鍵Ｓ１に基づいて第１の２次中間鍵として２次中間鍵ＭＳ１を生成し、１次中間鍵ＭＦ３、除数Ｂ、及び第１秘密鍵Ｓ１に基づいて第２の２次中間鍵として２次中間鍵ＭＳ２を生成する。続いて、第１共通鍵生成装置１０は、２次中間鍵ＭＳ２を第２共通鍵生成装置２０に送信し、２次中間鍵ＭＳ１を第３共通鍵生成装置３０に送信する。
【００１５】
また、第２共通鍵生成装置２０は、第３共通鍵生成装置３０から、１次中間鍵ＭＦ３を受信するとともに、第１共通鍵生成装置１０から、１次中間鍵ＭＦ１を受信し、１次中間鍵ＭＦ３、除数Ｂ、及び第２秘密鍵Ｓ２に基づいて第３の２次中間鍵として２次中間鍵ＭＳ３を生成し、１次中間鍵ＭＦ１、除数Ｂ、及び第２秘密鍵Ｓ２に基づいて第１の２次中間鍵として２次中間鍵ＭＳ１を生成する。続いて、第２共通鍵生成装置２０は、２次中間鍵ＭＳ１を第３共通鍵生成装置３０に送信し、２次中間鍵ＭＳ３を第１共通鍵生成装置１０に送信する。
【００１６】
また、第３共通鍵生成装置３０は、第１共通鍵生成装置１０から、１次中間鍵ＭＦ１を受信するとともに、第２共通鍵生成装置２０から、１次中間鍵ＭＦ２を受信し、１次中間鍵ＭＦ１、除数Ｂ、及び第３秘密鍵Ｓ３に基づいて第２の２次中間鍵として２次中間鍵ＭＳ２を生成し、１次中間鍵ＭＦ２、除数Ｂ、及び第３秘密鍵Ｓ３に基づいて第３の２次中間鍵として２次中間鍵ＭＳ３を生成する。続いて、第３共通鍵生成装置３０は、２次中間鍵ＭＳ３を第１共通鍵生成装置１０に送信し、２次中間鍵ＭＳ２を第２共通鍵生成装置２０に送信する。
【００１７】
また、第１共通鍵生成装置１０は、第２共通鍵生成装置２０及び第３共通鍵生成装置３０から２次中間鍵ＭＳ３を受信し、２次中間鍵ＭＳ３、除数Ｂ、及び第１秘密鍵Ｓ１に基づいて共通鍵Ｃを生成する。
【００１８】
また、第２共通鍵生成装置２０は、第３共通鍵生成装置３０及び第１共通鍵生成装置１０から２次中間鍵ＭＳ２を受信し、２次中間鍵ＭＳ２、除数Ｂ、及び第２秘密鍵Ｓ２に基づいて共通鍵Ｃを生成する。
【００１９】
また、第３共通鍵生成装置３０は、第１共通鍵生成装置１０及び第２共通鍵生成装置２０から２次中間鍵ＭＳ１を受信し、２次中間鍵ＭＳ１、除数Ｂ、及び第３秘密鍵Ｓ３に基づいて共通鍵Ｃを生成する。
【００２０】
本実施形態は、コンピュータ（第１共通鍵生成装置１０、第２共通鍵生成装置２０及び第３共通鍵生成装置３０）及びその周辺装置に適用される。本実施形態における各部は、コンピュータ及びその周辺装置が備えるハードウェア並びにこのハードウェアを制御するソフトウェアによって構成される。
【００２１】
上記ハードウェアには、制御部としてのＣＰＵの他、記憶部、通信部、表示部及び入力部が含まれる。記憶部としては、例えば、メモリ（ＲＡＭ、ＲＯＭ等）、ハードディスクドライブ（ＨＤＤ）及び光ディスク（ＣＤ、ＤＶＤ等）ドライブが挙げられる。通信部としては、例えば、各種有線及び無線インターフェース装置が挙げられる。表示部としては、例えば、液晶ディスプレイ、プラズマディスプレイ等の各種ディスプレイが挙げられる。入力部としては、例えば、キーボード及びマウス等が挙げられる。
【００２２】
上記ソフトウェアには、上記ハードウェアを制御するコンピュータ・プログラムやデータが含まれる。コンピュータ・プログラムやデータは、記憶部により記憶され、制御部により適宜実行、参照される。また、コンピュータ・プログラムやデータは、通信回線を介して配布することも可能であり、ＣＤ−ＲＯＭ等のコンピュータ可読媒体に記録して配布することも可能である。
【００２３】
図２は、本実施形態に係る共通鍵生成装置の機能構成を示す図である。
第１共通鍵生成装置１０の制御部は、第１送信手段及び第１受信手段としての第１通信部１１と、第１鍵情報生成手段としての第１鍵情報生成部１２と、第１中間鍵生成手段としての第１中間鍵生成部１３と、第１共通鍵生成手段としての第１共通鍵生成部１４と、べき剰余算出部５０と、を備える。
【００２４】
第１通信部１１は、第２共通鍵生成装置２０及び第３共通鍵生成装置３０と、通信ネットワークＮを介して、鍵情報の送受信を行う。具体的には、第１通信部１１は、後述の第１鍵情報生成部１２により生成される基数Ａ及び除数Ｂ、並びに後述の第１中間鍵生成部１３により生成される１次中間鍵ＭＦ１を、第２共通鍵生成装置２０及び第３共通鍵生成装置３０に送信する。また、第１通信部１１は、第２共通鍵生成装置２０に、２次中間鍵ＭＳ２を送信し、第２共通鍵生成装置２０から、１次中間鍵ＭＦ２及び２次中間鍵ＭＳ３を受信する。また、第１通信部１１は、第３共通鍵生成装置３０に、２次中間鍵ＭＳ１を送信し、第３共通鍵生成装置３０から、１次中間鍵ＭＦ３及び２次中間鍵ＭＳ３を受信する。
【００２５】
第１鍵情報生成部１２は、共通鍵Ｃを生成する情報となる基数Ａ、除数Ｂ、及び第１秘密鍵Ｓ１を生成する。具体的には、第１鍵情報生成部１２は、基数Ａとして任意の自然数を生成し、除数Ｂとして、桁数が大きい素数（例えば、２０桁以上の素数）を生成するものとする。また、第１鍵情報生成部１２は、第１秘密鍵Ｓ１として、「０」以上かつ「除数Ｂ−２」以下である任意の自然数を生成する。
【００２６】
第１中間鍵生成部１３は、基数Ａを底とし、第１秘密鍵Ｓ１を指数としたべき乗を、除数Ｂで除算した場合の剰余を１次中間鍵ＭＦ１として生成する。具体的には、第１中間鍵生成部１３は、基数Ａを底、除数Ｂを除数、第１秘密鍵Ｓ１を指数とし、これら底、除数、及び指数をべき剰余算出部５０に入力することにより、べき剰余算出部５０から、基数Ａを底とし、第１秘密鍵Ｓ１を指数としたべき乗を除数Ｂで除算した場合の剰余を得る。続いて、第１中間鍵生成部１３は、得られた剰余を１次中間鍵ＭＦ１とすることにより、１次中間鍵ＭＦ１を生成する。
【００２７】
また、第１中間鍵生成部１３は、第１通信部１１により、１次中間鍵ＭＦ２を受信したことに応じて、１次中間鍵ＭＦ２を底とし、第１秘密鍵Ｓ１を指数としたべき乗を、除数Ｂで除算した場合の剰余を２次中間鍵ＭＳ１として生成する。具体的には、第１中間鍵生成部１３は、１次中間鍵ＭＦ２を底、除数Ｂを除数、第１秘密鍵Ｓ１を指数とし、これら底、除数、及び指数をべき剰余算出部５０に入力することにより、べき剰余算出部５０から得られる剰余を２次中間鍵ＭＳ１とすることにより、２次中間鍵ＭＳ１を生成する。
【００２８】
また、第１中間鍵生成部１３は、第１通信部１１により、１次中間鍵ＭＦ３を受信したことに応じて、１次中間鍵ＭＦ３を底とし、第１秘密鍵Ｓ１を指数としたべき乗を、除数Ｂで除算した場合の剰余を２次中間鍵ＭＳ２として生成する。具体的には、第１中間鍵生成部１３は、１次中間鍵ＭＦ３を底、除数Ｂを除数、第１秘密鍵Ｓ１を指数とし、これら底、除数、及び指数をべき剰余算出部５０に入力することにより、べき剰余算出部５０から得られる剰余を２次中間鍵ＭＳ２とすることにより、２次中間鍵ＭＳ２を生成する。
【００２９】
第１共通鍵生成部１４は、第１通信部１１により、２次中間鍵ＭＳ３を受信したことに応じて、２次中間鍵ＭＳ３を底とし、第１秘密鍵Ｓ１を指数としたべき乗を、除数Ｂで除算した場合の剰余を共通鍵Ｃとして生成する。具体的には、第１共通鍵生成部１４は、２次中間鍵ＭＳ３を底、除数Ｂを除数、第１秘密鍵Ｓ１を指数とし、これら底、除数、及び指数をべき剰余算出部５０に入力することにより、べき剰余算出部５０から得られる剰余を共通鍵Ｃとすることにより、共通鍵Ｃを生成する。
【００３０】
べき剰余算出部５０は、第１共通鍵生成装置１０、第２共通鍵生成装置２０、及び第３共通鍵生成装置３０の共通機能である。
図３を参照してべき剰余算出部５０について説明する。図３は、本実施形態に係るべき剰余算出部５０の機能構成を示す図である。
【００３１】
べき剰余算出部５０は、底、除数、及び指数の入力を受け付け、この底の指数乗を、除数で除算した場合の剰余を算出し、この算出した剰余を出力する。べき剰余算出部５０は、入力受付手段としての入力受付部５１と、初期設定手段としての初期設定部５２と、変換手段としての変換部５３と、計数手段としての計数部５４と、基数算出手段としての基数算出部５５と、剰余算出手段としての剰余算出部５６と、シフト手段としてのシフト部５７と、反復実行手段としての反復実行部５８と、出力手段としての出力部５９と、を備える。また、べき剰余算出部５０は、第１中間値ＡＴと、第２中間値ＭＴとを備える。
【００３２】
入力受付部５１は、底、除数、及び指数の入力を受け付ける。ここで、入力受付部５１により受け付けられた底、除数、及び指数を、それぞれ底Ａｉ、除数Ｂｉ、指数ｅとする。
【００３３】
初期設定部５２は、第１中間値ＡＴの初期値を底Ａｉとし、第２中間値ＭＴの初期値を１に設定する。
変換部５３は、指数ｅを、１０進数から２進数に変換する。
【００３４】
計数部５４は、変換部５３により２進数に変換された指数ｅのビット数を計数する。
【００３５】
基数算出部５５は、２進数で表現された指数ｅの右端の値（ビット）が１である場合、第１中間値ＡＴを第２中間値ＭＴで乗算して得られた値を除数Ｂｉで除算した場合の剰余を第１中間値ＡＴとすることにより、第１中間値ＡＴを更新する。
【００３６】
なお、第１中間値ＡＴと第２中間値ＭＴとの乗算は、以下のように行われる。すなわち、基数算出部５５は、第１中間値ＡＴ及び第２中間値ＭＴを、以下の（１）式に示すように、複数桁（例えば、１桁目〜５桁目、６桁目〜１０桁目等、５桁ずつ）に区切り、１０のべき乗により構成される多項式、すなわち、初項を１０のべき乗（例えば１０の５乗）の０乗、公比を当該１０のべき乗（例えば１０の５乗）とした数列の和で表される多項式に変換する。
【数１】
【００３７】
ここで、ａ１…ａｍは、第１中間値ＡＴを満たすためにそれぞれの項に付される係数であり、ｂ１…ｂｎは、第２中間値ＭＴを満たすためにそれぞれの項に付される係数である。
【００３８】
続いて、基数算出部５５は、１０のべき乗の和に変換された第１中間値ＡＴ及び第２中間値ＭＴの多項式を乗算して、（２）式に示すように展開する。その後、展開された値に含まれるそれぞれの項を合計することにより、第１中間値ＡＴと第２中間値ＭＴとを乗算した値を算出する。
【数２】
【００３９】
剰余算出部５６は、２進数に変換された指数ｅの右端の値（ビット）にかかわらず、第１中間値ＡＴを２乗した値を除数Ｂｉで除算した場合の剰余を第２中間値ＭＴとすることにより、第２中間値ＭＴを更新する。なお、第１中間値ＡＴの２乗の計算は、第１中間値ＡＴと第２中間値ＭＴとの乗算と同様に、第１中間値ＡＴを、初項を１０のべき乗（例えば１０の５乗）の０乗、公比を当該１０のべき乗（例えば１０の５乗）とした数列の和で表される多項式に変換し、この多項式の第１中間値ＡＴを２乗することにより計算される。
【００４０】
シフト部５７は、２進数に変換された指数ｅを右シフトする。具体的には、シフト部５７は、２進数に変換された指数ｅを１ビット右に論理シフトする演算（論理シフト演算）を行う。
【００４１】
反復実行部５８は、計数部５４により計数されたビット数の値を反復回数とし、基数算出部５５、剰余算出部５６、及びシフト部５７に係る処理が、基数算出部５５、剰余算出部５６、シフト部５７の順に、反復回数実行されるように制御する。具体的には、記憶部に初期値を０とするカウンタを設けておき、反復実行部５８は、基数算出部５５、剰余算出部５６、及びシフト部５７に係る処理が終了したことに応じて、カウンタに１加算（インクリメント）する。その後、反復実行部５８は、カウンタの値が反復回数に達するまで、基数算出部５５、剰余算出部５６、シフト部５７、インクリメントに係る処理を実行する制御を行い、カウンタの値が反復回数に達した場合に、反復実行を終了する。
【００４２】
出力部５９は、反復実行部５８により、基数算出部５５、剰余算出部５６、及びシフト部５７に係る処理が反復回数実行された後、第２中間値ＭＴを剰余として出力する。
【００４３】
第２共通鍵生成装置２０の制御部は、第２送信手段及び第２受信手段としての第２通信部２１と、第２鍵情報生成手段としての第２鍵情報生成部２２と、第２中間鍵生成手段としての第２中間鍵生成部２３と、第２共通鍵生成手段としての第２共通鍵生成部２４と、べき剰余算出部５０と、を備える。
【００４４】
第２通信部２１は、第３共通鍵生成装置３０及び第１共通鍵生成装置１０と、通信ネットワークＮを介して、鍵情報の送受信を行う。具体的には、第２通信部２１は、後述の第２中間鍵生成部２３により生成される１次中間鍵ＭＦ２を、第３共通鍵生成装置３０及び第１共通鍵生成装置１０に送信する。また、第２通信部２１は、第３共通鍵生成装置３０に、２次中間鍵ＭＳ１を送信し、第３共通鍵生成装置３０から、１次中間鍵ＭＦ３及び２次中間鍵ＭＳ２を受信する。また、第２通信部２１は、第１共通鍵生成装置１０に、２次中間鍵ＭＳ３を送信し、第１共通鍵生成装置１０から、１次中間鍵ＭＦ１及び２次中間鍵ＭＳ２を受信する。
【００４５】
第２鍵情報生成部２２は、共通鍵を生成する情報となる第２秘密鍵Ｓ２を生成する。具体的には、第２鍵情報生成部２２は、第２秘密鍵Ｓ２として、「０」以上かつ「除数Ｂ−２」以下である任意の自然数を生成する。
【００４６】
第２中間鍵生成部２３は、基数Ａを底とし、第２秘密鍵Ｓ２を指数としたべき乗を、除数Ｂで除算した場合の剰余を１次中間鍵ＭＦ２として生成する。具体的には、第２中間鍵生成部２３は、基数Ａを底、除数Ｂを除数、第２秘密鍵Ｓ２を指数とし、これら底、除数、及び指数をべき剰余算出部５０に入力することにより、べき剰余算出部５０から、基数Ａを底とし、第２秘密鍵Ｓ２を指数としたべき乗を除数Ｂで除算した場合の剰余を得る。続いて、第２中間鍵生成部２３は、得られた剰余を１次中間鍵ＭＦ２とすることにより、１次中間鍵ＭＦ２を生成する。
【００４７】
また、第２中間鍵生成部２３は、第２通信部２１により、１次中間鍵ＭＦ３を受信したことに応じて、１次中間鍵ＭＦ３を底とし、第２秘密鍵Ｓ２を指数としたべき乗を、除数Ｂで除算した場合の剰余を２次中間鍵ＭＳ３として生成する。具体的には、第２中間鍵生成部２３は、１次中間鍵ＭＦ３を底、除数Ｂを除数、第２秘密鍵Ｓ２を指数とし、これら底、除数、及び指数をべき剰余算出部５０に入力することにより、べき剰余算出部５０から得られる剰余を２次中間鍵ＭＳ３とすることにより、２次中間鍵ＭＳ３を生成する。
【００４８】
また、第２中間鍵生成部２３は、第２通信部２１により、１次中間鍵ＭＦ１を受信したことに応じて、１次中間鍵ＭＦ１を底とし、第２秘密鍵Ｓ２を指数としたべき乗を、除数Ｂで除算した場合の剰余を２次中間鍵ＭＳ１として生成する。具体的には、第２中間鍵生成部２３は、１次中間鍵ＭＦ１を底、除数Ｂを除数、第２秘密鍵Ｓ２を指数とし、これら底、除数、及び指数をべき剰余算出部５０に入力することにより、べき剰余算出部５０から得られる剰余を２次中間鍵ＭＳ１とすることにより、２次中間鍵ＭＳ１を生成する。
【００４９】
第２共通鍵生成部２４は、第２通信部２１により、２次中間鍵ＭＳ２を受信したことに応じて、２次中間鍵ＭＳ２を底とし、第２秘密鍵Ｓ２を指数としたべき乗を、除数Ｂで除算した場合の剰余を共通鍵Ｃとして生成する。具体的には、第２共通鍵生成部２４は、２次中間鍵ＭＳ２を底、除数Ｂを除数、第２秘密鍵Ｓ２を指数とし、これら底、除数、及び指数をべき剰余算出部５０に入力することにより、べき剰余算出部５０から得られる剰余を共通鍵Ｃとすることにより、共通鍵Ｃを生成する。
【００５０】
べき剰余算出部５０は、第１共通鍵生成装置１０に備えているべき剰余算出部５０と同一であるので、説明を省略する。
【００５１】
第３共通鍵生成装置３０の制御部は、第３送信手段及び第３受信手段としての第３通信部３１と、第３鍵情報生成手段としての第３鍵情報生成部３２と、第３中間鍵生成手段としての第３中間鍵生成部３３と、第３共通鍵生成手段としての第３共通鍵生成部３４と、べき剰余算出部５０と、を備える。
【００５２】
第３通信部３１は、第１共通鍵生成装置１０及び第２共通鍵生成装置２０と、通信ネットワークＮを介して、鍵情報の送受信を行う。具体的には、第３通信部３１は、後述の第３中間鍵生成部３３により生成される１次中間鍵ＭＦ３を、第１共通鍵生成装置１０及び第２共通鍵生成装置２０に送信する。また、第３通信部３１は、第１共通鍵生成装置１０に、２次中間鍵ＭＳ３を送信し、第１共通鍵生成装置１０から、１次中間鍵ＭＦ１及び２次中間鍵ＭＳ１を受信する。また、第３通信部３１は、第２共通鍵生成装置２０に、２次中間鍵ＭＳ２を送信し、第２共通鍵生成装置２０から、１次中間鍵ＭＦ２及び２次中間鍵ＭＳ１を受信する。
【００５３】
第３鍵情報生成部３２は、共通鍵を生成する情報となる第３秘密鍵Ｓ３を生成する。具体的には、第３鍵情報生成部３２は、第３秘密鍵Ｓ３として、「０」以上かつ「除数Ｂ−２」以下である任意の自然数を生成する。
【００５４】
第３中間鍵生成部３３は、基数Ａを底とし、第３秘密鍵Ｓ３を指数としたべき乗を、除数Ｂで除算した場合の剰余を１次中間鍵ＭＦ３として生成する。具体的には、第３中間鍵生成部３３は、基数Ａを底、除数Ｂを除数、第３秘密鍵Ｓ３を指数とし、これら底、除数、及び指数をべき剰余算出部５０に入力することにより、べき剰余算出部５０から、基数Ａを底とし、第３秘密鍵Ｓ３を指数としたべき乗を除数Ｂで除算した場合の剰余を得る。続いて、第３中間鍵生成部３３は、得られた剰余を１次中間鍵ＭＦ３とすることにより、１次中間鍵ＭＦ３を生成する。
【００５５】
また、第３中間鍵生成部３３は、第３通信部３１により、１次中間鍵ＭＦ１を受信したことに応じて、１次中間鍵ＭＦ１を底とし、第３秘密鍵Ｓ３を指数としたべき乗を、除数Ｂで除算した場合の剰余を２次中間鍵ＭＳ２として生成する。具体的には、第３中間鍵生成部３３は、１次中間鍵ＭＦ１を底、除数Ｂを除数、第３秘密鍵Ｓ３を指数とし、これら底、除数、及び指数をべき剰余算出部５０に入力することにより、べき剰余算出部５０から得られる剰余を２次中間鍵ＭＳ２とすることにより、２次中間鍵ＭＳ２を生成する。
【００５６】
また、第３中間鍵生成部３３は、第３通信部３１により、１次中間鍵ＭＦ２を受信したことに応じて、１次中間鍵ＭＦ２を底とし、第３秘密鍵Ｓ３を指数としたべき乗を、除数Ｂで除算した場合の剰余を２次中間鍵ＭＳ３として生成する。具体的には、第３中間鍵生成部３３は、１次中間鍵ＭＦ２を底、除数Ｂを除数、第３秘密鍵Ｓ３を指数とし、これら底、除数、及び指数をべき剰余算出部５０に入力することにより、べき剰余算出部５０から得られる剰余を２次中間鍵ＭＳ３とすることにより、２次中間鍵ＭＳ３を生成する。
【００５７】
第３共通鍵生成部３４は、第３通信部３１により、２次中間鍵ＭＳ１を受信したことに応じて、２次中間鍵ＭＳ１を底とし、第３秘密鍵Ｓ３を指数としたべき乗を、除数Ｂで除算した場合の剰余を共通鍵Ｃとして生成する。具体的には、第３共通鍵生成部３４は、２次中間鍵ＭＳ１を底、除数Ｂを除数、第３秘密鍵Ｓ３を指数とし、これら底、除数、及び指数をべき剰余算出部５０に入力することにより、べき剰余算出部５０から得られる剰余を共通鍵Ｃとすることにより、共通鍵Ｃを生成する。
【００５８】
べき剰余算出部５０は、第１共通鍵生成装置１０に備えているべき剰余算出部５０と同一であるので、説明を省略する。
【００５９】
続いて、図４から図７を参照して、共通鍵生成システム１における処理の流れを説明する。
図４は、本実施形態に係る第１共通鍵生成装置１０における共通鍵生成に係る処理の流れを示すフローチャートである。
【００６０】
ステップＳ１において、第１鍵情報生成部１２は、基数Ａ、除数Ｂ、及び第１秘密鍵Ｓ１を生成する。
【００６１】
ステップＳ２において、第１中間鍵生成部１３は、ステップＳ１において生成された基数Ａ、除数Ｂ、及び第１秘密鍵Ｓ１に基づいて、１次中間鍵ＭＦ１を生成する。すなわち、第１中間鍵生成部１３は、基数Ａを底とし、第１秘密鍵Ｓ１を指数としたべき乗を、除数Ｂで除算した場合の剰余を１次中間鍵ＭＦ１とする。１次中間鍵ＭＦ１を生成する詳細な処理は、第１共通鍵生成装置１０のべき剰余算出部５０において行われる。べき剰余算出部５０における処理は、後述で説明する。
【００６２】
ステップＳ３において、第１通信部１１は、ステップＳ１において生成された基数Ａ、除数Ｂ、及びステップＳ２において生成された１次中間鍵ＭＦ１を第２共通鍵生成装置２０及び第３共通鍵生成装置３０に送信する。
【００６３】
ステップＳ４において、第１共通鍵生成装置１０の制御部は、第１通信部１１により、第２共通鍵生成装置２０又は第３共通鍵生成装置３０から、鍵を受信したか否かを判定する。第１共通鍵生成装置１０の制御部は、この判定がＹＥＳの場合、処理をステップＳ５に移し、この処理がＮＯの場合、ステップＳ４の処理を再実行する。
【００６４】
ステップＳ５において、第１中間鍵生成部１３は、ステップＳ４において受信した鍵が、１次中間鍵ＭＦ２であるか否かを判定する。第１中間鍵生成部１３は、この判定がＹＥＳの場合、処理をステップＳ６に移し、この判定がＮＯの場合、処理をステップＳ９に移す。
【００６５】
ステップＳ６において、第１中間鍵生成部１３は、１次中間鍵ＭＦ２、除数Ｂ、及び第１秘密鍵Ｓ１に基づいて、２次中間鍵ＭＳ１を生成する。すなわち、第１中間鍵生成部１３は、１次中間鍵ＭＦ２を底とし、第１秘密鍵Ｓ１を指数としたべき乗を、除数Ｂで除算した場合の剰余を２次中間鍵ＭＳ１とする。２次中間鍵ＭＳ１を生成する詳細な処理は、第１共通鍵生成装置１０のべき剰余算出部５０において行われる。
【００６６】
ステップＳ７において、第１通信部１１は、ステップＳ６において生成された２次中間鍵ＭＳ１を第３共通鍵生成装置３０に送信する。
【００６７】
ステップＳ８において、第１共通鍵生成装置１０の制御部は、第１通信部１１により、全ての鍵、すなわち、１次中間鍵ＭＦ２、１次中間鍵ＭＦ３及び２次中間鍵ＭＳ３を受信したか否かを判定する。第１共通鍵生成装置１０の制御部は、この判定がＹＥＳの場合、処理を終了し、この判定がＮＯの場合、処理をステップＳ４に移す。
【００６８】
ステップＳ９において、第１中間鍵生成部１３は、ステップＳ４において受信した鍵が、１次中間鍵ＭＦ３であるか否かを判定する。第１中間鍵生成部１３は、この判定がＹＥＳの場合、処理をステップＳ１０に移し、この判定がＮＯの場合、処理をステップＳ１２に移す。
【００６９】
ステップＳ１０において、第１中間鍵生成部１３は、１次中間鍵ＭＦ３、除数Ｂ、及び第１秘密鍵Ｓ１に基づいて、２次中間鍵ＭＳ２を生成する。すなわち、第１中間鍵生成部１３は、１次中間鍵ＭＦ３を底とし、第１秘密鍵Ｓ１を指数としたべき乗を、除数Ｂで除算した場合の剰余を２次中間鍵ＭＳ２とする。２次中間鍵ＭＳ２を生成する詳細な処理は、第１共通鍵生成装置１０のべき剰余算出部５０において行われる。
【００７０】
ステップＳ１１において、第１通信部１１は、ステップＳ６において生成された２次中間鍵ＭＳ２を第２共通鍵生成装置２０に送信する。この処理が終了すると、ステップＳ８に移る。
【００７１】
ステップＳ１２において、第１共通鍵生成部１４は、２次中間鍵ＭＳ３、除数Ｂ、及び第１秘密鍵Ｓ１に基づいて、共通鍵Ｃを生成する。すなわち、ステップＳ１２の処理が実行される場合、第１通信部１１は、ステップＳ４において、２次中間鍵ＭＳ３を受信していることとなる。この場合、第１共通鍵生成部１４は、２次中間鍵ＭＳ３を底とし、第１秘密鍵Ｓ１を指数としたべき乗を、除数Ｂで除算した場合の剰余を共通鍵Ｃとする。共通鍵Ｃを生成する詳細な処理は、第１共通鍵生成装置１０のべき剰余算出部５０において行われる。この処理が終了すると、ステップＳ８に移る。
【００７２】
図５は、本実施形態に係るべき剰余算出部５０における処理の流れを示すフローチャートである。
【００７３】
ステップＳ２１（入力受付ステップ）において、入力受付部５１は、底、除数、指数の入力を受け付ける。ここで受け付けた底を底Ａｉとし、除数を除数Ｂとし、指数を指数ｅとする。
【００７４】
ステップＳ２２（初期設定ステップ）において、初期設定部５２は、第１中間値ＡＴの初期値をステップＳ２１において受け付けた底Ａｉとし、第２中間値ＭＴの初期値を１に設定する。
【００７５】
ステップＳ２３（変換ステップ）において、変換部５３は、ステップＳ２１において受け付けた指数ｅを、２進数に変換する。
【００７６】
ステップＳ２４（計数ステップ）において、計数部５４は、ステップＳ２３において変換された、２進数で表現された指数ｅのビット数を計数する。
【００７７】
ステップＳ２５（基数算出ステップ）において、基数算出部５５は、第１中間値ＡＴを更新する。具体的には、基数算出部５５は、２進数で表現された指数ｅの右端の値（ビット）が１である場合、第１中間値ＡＴを第２中間値ＭＴで乗算して得られた値を除数Ｂｉで除算して剰余を算出する。続いて、基数算出部５５は、この算出された剰余を第１中間値ＡＴとすることにより、第１中間値ＡＴを更新する。ここで、基数算出部５５により行われる第１中間値ＡＴと第２中間値ＭＴとの乗算は、第１中間値ＡＴ及び第２中間値ＭＴそれぞれを１０のべき乗の和に変換し、この変換した第１中間値ＡＴ及び第２中間値ＭＴを乗算することで行われる。
【００７８】
ステップＳ２６（剰余算出ステップ）において、剰余算出部５６は、第２中間値ＭＴを更新する。具体的には、剰余算出部５６は、２進数に変換された指数ｅの右端の値（ビット）にかかわらず、第１中間値ＡＴを２乗した値を除数Ｂｉで除算した場合の剰余を第２中間値ＭＴとすることにより、第２中間値ＭＴを更新する。なお、第１中間値ＡＴの２乗の計算は、第１中間値ＡＴと第２中間値ＭＴとの乗算と同様に、第１中間値ＡＴを１０のべき乗の和に変換し、この変換した第１中間値ＡＴを２乗することにより計算される。
【００７９】
ステップＳ２７（シフトステップ）において、シフト部５７は、２進数に変換された指数ｅを１ビット右に論理シフトする演算（論理シフト演算）を行う。
【００８０】
ステップＳ２８（反復実行ステップ）において、反復実行部５８は、ステップＳ２５〜ステップＳ２７の処理が、反復回数行われたか判定する。ここで、反復回数は、ステップＳ２４において計数された値である。反復実行部５８は、この判定がＹＥＳの場合、処理をステップＳ２９に移し、この判定がＮＯの場合、処理をステップＳ２５に移す。
【００８１】
ステップＳ２９（出力ステップ）において、出力部５９は、第２中間値ＭＴを剰余として出力する。
【００８２】
図６は、本実施形態に係る第２共通鍵生成装置２０における共通鍵生成に係る処理の流れを示すフローチャートである。
【００８３】
ステップＳ３１において、第２通信部２１は、第１共通鍵生成装置１０から、基数Ａ、除数Ｂ、及び１次中間鍵ＭＦ１を受信する。
【００８４】
ステップＳ３２において、第２鍵情報生成部２２は、第２秘密鍵Ｓ２を生成する。
【００８５】
ステップＳ３３において、第２中間鍵生成部２３は、ステップＳ３１において受信した基数Ａ、除数Ｂ、及びステップＳ３２において生成した第２秘密鍵Ｓ２に基づいて、１次中間鍵ＭＦ２を生成する。すなわち、第２中間鍵生成部２３は、基数Ａを底とし、第２秘密鍵Ｓ２を指数としたべき乗を、除数Ｂで除算した場合の剰余を１次中間鍵ＭＦ２とする。１次中間鍵ＭＦ２を生成する詳細な処理は、第２共通鍵生成装置２０のべき剰余算出部５０において行われる。
【００８６】
ステップＳ３４において、第２通信部２１は、ステップＳ３３において生成された１次中間鍵ＭＦ２を第３共通鍵生成装置３０及び第１共通鍵生成装置１０に送信する。
【００８７】
ステップＳ３５において、第２中間鍵生成部２３は、１次中間鍵ＭＦ１、除数Ｂ、及び第２秘密鍵Ｓ２に基づいて、２次中間鍵ＭＳ１を生成する。すなわち、第２中間鍵生成部２３は、１次中間鍵ＭＦ１を底とし、第２秘密鍵Ｓ２を指数としたべき乗を、除数Ｂで除算した場合の剰余を２次中間鍵ＭＳ１とする。２次中間鍵ＭＳ１を生成する詳細な処理は、第２共通鍵生成装置２０のべき剰余算出部５０において行われる。
【００８８】
ステップＳ３６において、第２通信部２１は、ステップＳ３５において生成された２次中間鍵ＭＳ１を第３共通鍵生成装置３０に送信する。
【００８９】
ステップＳ３７において、第２共通鍵生成装置２０の制御部は、第２通信部２１により、第３共通鍵生成装置３０から、１次中間鍵ＭＦ３を受信したか否かを判定する。第２共通鍵生成装置２０の制御部は、この判定がＹＥＳの場合、処理をステップＳ３８に移し、この処理がＮＯの場合、処理をステップＳ４１に移す。
【００９０】
ステップＳ３８において、第２中間鍵生成部２３は、１次中間鍵ＭＦ３、除数Ｂ、及び第２秘密鍵Ｓ２に基づいて、２次中間鍵ＭＳ３を生成する。すなわち、第２中間鍵生成部２３は、１次中間鍵ＭＦ３を底とし、第２秘密鍵Ｓ２を指数としたべき乗を、除数Ｂで除算した場合の剰余を２次中間鍵ＭＳ３とする。２次中間鍵ＭＳ３を生成する詳細な処理は、第２共通鍵生成装置２０のべき剰余算出部５０において行われる。
【００９１】
ステップＳ３９において、第２通信部２１は、ステップＳ３８において生成された２次中間鍵ＭＳ３を第１共通鍵生成装置１０に送信する。
【００９２】
ステップＳ４０において、第２共通鍵生成装置２０の制御部は、第２通信部２１により、全ての鍵、すなわち、１次中間鍵ＭＦ１、１次中間鍵ＭＦ３及び２次中間鍵ＭＳ２を受信したか否かを判定する。第２共通鍵生成装置２０の制御部は、この判定がＹＥＳの場合、処理を終了し、この判定がＮＯの場合、処理をステップＳ３７に移す。
【００９３】
ステップＳ４１において、第２共通鍵生成装置２０の制御部は、第２通信部２１により、２次中間鍵ＭＳ２を受信したか否かを判定する。第２共通鍵生成装置２０の制御部は、この判定がＹＥＳの場合、処理をステップＳ４２に移し、この処理がＮＯの場合、処理をステップＳ４０に移す。
【００９４】
ステップＳ４２において、第２共通鍵生成部２４は、２次中間鍵ＭＳ２、除数Ｂ、及び第２秘密鍵Ｓ２に基づいて、共通鍵Ｃを生成する。すなわち、第２共通鍵生成部２４は、２次中間鍵ＭＳ２を底とし、第２秘密鍵Ｓ２を指数としたべき乗を、除数Ｂで除算した場合の剰余を共通鍵Ｃとする。共通鍵Ｃを生成する詳細な処理は、第２共通鍵生成装置２０のべき剰余算出部５０において行われる。この処理が終了すると、ステップＳ４０に移る。
【００９５】
図７は、本実施形態に係る第３共通鍵生成装置３０における共通鍵生成に係る処理の流れを示すフローチャートである。
【００９６】
ステップＳ５１において、第３通信部３１は、第１共通鍵生成装置１０から、基数Ａ、除数Ｂ、及び１次中間鍵ＭＦ１を受信する。
【００９７】
ステップＳ５２において、第３鍵情報生成部３２は、第３秘密鍵Ｓ３を生成する。
【００９８】
ステップＳ５３において、第３中間鍵生成部３３は、ステップＳ５１において受信した基数Ａ、除数Ｂ、及びステップＳ５２において生成した第３秘密鍵Ｓ３に基づいて、１次中間鍵ＭＦ３を生成する。すなわち、第３中間鍵生成部３３は、基数Ａを底とし、第３秘密鍵Ｓ３を指数としたべき乗を、除数Ｂで除算した場合の剰余を１次中間鍵ＭＦ３とする。１次中間鍵ＭＦ３を生成する詳細な処理は、第３共通鍵生成装置３０のべき剰余算出部５０において行われる。
【００９９】
ステップＳ５４において、第３通信部３１は、ステップＳ５３において生成された１次中間鍵ＭＦ３を第１共通鍵生成装置１０及び第２共通鍵生成装置２０に送信する。
【０１００】
ステップＳ５５において、第３中間鍵生成部３３は、１次中間鍵ＭＦ１、除数Ｂ、及び第３秘密鍵Ｓ３に基づいて、２次中間鍵ＭＳ２を生成する。すなわち、第３中間鍵生成部３３は、１次中間鍵ＭＦ１を底とし、第３秘密鍵Ｓ３を指数としたべき乗を、除数Ｂで除算した場合の剰余を２次中間鍵ＭＳ２とする。２次中間鍵ＭＳ２を生成する詳細な処理は、第３共通鍵生成装置３０のべき剰余算出部５０において行われる。
【０１０１】
ステップＳ５６において、第３通信部３１は、ステップＳ５５において生成された２次中間鍵ＭＳ２を第２共通鍵生成装置２０に送信する。
【０１０２】
ステップＳ５７において、第３共通鍵生成装置３０の制御部は、第３通信部３１により、第２共通鍵生成装置２０から、１次中間鍵ＭＦ２を受信したか否かを判定する。第３共通鍵生成装置３０の制御部は、この判定がＹＥＳの場合、処理をステップＳ５８に移し、この処理がＮＯの場合、処理をステップＳ６１に移す。
【０１０３】
ステップＳ５８において、第３中間鍵生成部３３は、１次中間鍵ＭＦ２、除数Ｂ、及び第３秘密鍵Ｓ３に基づいて、２次中間鍵ＭＳ３を生成する。すなわち、第３中間鍵生成部３３は、１次中間鍵ＭＦ２を底とし、第３秘密鍵Ｓ３を指数としたべき乗を、除数Ｂで除算した場合の剰余を２次中間鍵ＭＳ３とする。２次中間鍵ＭＳ３を生成する詳細な処理は、第３共通鍵生成装置３０のべき剰余算出部５０において行われる。
【０１０４】
ステップＳ５９において、第３通信部３１は、ステップＳ５８において生成された２次中間鍵ＭＳ３を第１共通鍵生成装置１０に送信する。
【０１０５】
ステップＳ６０において、第３共通鍵生成装置３０の制御部は、第３通信部３１により、全ての鍵、すなわち、１次中間鍵ＭＦ１、１次中間鍵ＭＦ２及び２次中間鍵ＭＳ１を受信したか否かを判定する。第３共通鍵生成装置３０の制御部は、この判定がＹＥＳの場合、処理を終了し、この判定がＮＯの場合、処理をステップＳ５７に移す。
【０１０６】
ステップＳ６１において、第３共通鍵生成装置３０の制御部は、第３通信部３１により、２次中間鍵ＭＳ１を受信したか否かを判定する。第３共通鍵生成装置３０の制御部は、この判定がＹＥＳの場合、処理をステップＳ６２に移し、この処理がＮＯの場合、処理をステップＳ６０に移す。
【０１０７】
ステップＳ６２において、第３共通鍵生成部３４は、２次中間鍵ＭＳ１、除数Ｂ、及び第３秘密鍵Ｓ３に基づいて、共通鍵Ｃを生成する。すなわち、第３共通鍵生成部３４は、２次中間鍵ＭＳ１を底とし、第３秘密鍵Ｓ３を指数としたべき乗を、除数Ｂで除算した場合の剰余を共通鍵Ｃとする。共通鍵Ｃを生成する詳細な処理は、第３共通鍵生成装置３０のべき剰余算出部５０において行われる。この処理が終了すると、ステップＳ６０に移る。
【０１０８】
以上のように、本実施形態によれば、第１共通鍵生成装置１０は、１次中間鍵ＭＦ２を底とし、第１秘密鍵Ｓ１を指数としたべき乗を、除数Ｂで除算した場合の剰余を２次中間鍵ＭＳ１として第３共通鍵生成装置３０に送信し、１次中間鍵ＭＦ３を底とし、第１秘密鍵Ｓ１を指数としたべき乗を、除数Ｂで除算した場合の剰余を２次中間鍵ＭＳ２とし、第２共通鍵生成装置２０に送信する。また、第２共通鍵生成装置２０は、１次中間鍵ＭＦ３を底とし、第２秘密鍵Ｓ２を指数としたべき乗を、除数Ｂで除算した場合の剰余を２次中間鍵ＭＳ３として第１共通鍵生成装置１０に送信し、１次中間鍵ＭＦ１を底とし、第２秘密鍵Ｓ２を指数としたべき乗を、除数Ｂで除算した場合の剰余を２次中間鍵ＭＳ１とし、第３共通鍵生成装置３０に送信する。また、第３共通鍵生成装置３０は、１次中間鍵ＭＦ１を底とし、第３秘密鍵Ｓ３を指数としたべき乗を、除数Ｂで除算した場合の剰余を２次中間鍵ＭＳ２として第２共通鍵生成装置２０に送信し、１次中間鍵ＭＦ２を底とし、第３秘密鍵Ｓ３を指数としたべき乗を、除数Ｂで除算した場合の剰余を２次中間鍵ＭＳ３とし、第１共通鍵生成装置１０に送信する。続いて、第１共通鍵生成装置１０は、２次中間鍵ＭＳ３を底とし、第１秘密鍵Ｓ１を指数としたべき乗を、除数Ｂで除算した場合の剰余を共通鍵Ｃとする。また、第２共通鍵生成装置２０は、２次中間鍵ＭＳ２を底とし、第２秘密鍵Ｓ２を指数としたべき乗を、除数Ｂで除算した場合の剰余を共通鍵Ｃとする。また、第３共通鍵生成装置３０は、２次中間鍵ＭＳ１を底とし、第３秘密鍵Ｓ３を指数としたべき乗を、除数Ｂで除算した場合の剰余を共通鍵Ｃとする。
【０１０９】
ここで、基数Ａを底とし秘密鍵を指数としたべき乗は、以下の（３）式で表される。
【数３】
ただし、Ｘ１は、基数Ａを底とし第１秘密鍵Ｓ１を指数としたべき乗を除数Ｂで除算した場合の商とし、Ｘ２は、基数Ａを底とし第２秘密鍵Ｓ２を指数としたべき乗を除数Ｂで除算した場合の商とし、Ｘ３は、基数Ａを底とし第３秘密鍵Ｓ３を指数としたべき乗を除数Ｂで除算した場合の商とする。
【０１１０】
また、１次中間鍵を底とし秘密鍵を指数としたべき乗は、以下の（４）式で表される。
【数４】
ただし、Ｘ４は、１次中間鍵ＭＦ１を底とし第１秘密鍵Ｓ１を指数としたべき乗を除数Ｂで除算した場合の商とし、Ｘ５は、１次中間鍵ＭＦ２を底とし第２秘密鍵Ｓ２を指数としたべき乗を除数Ｂで除算した場合の商とし、Ｘ６は、１次中間鍵ＭＦ３を底とし第３秘密鍵Ｓ３を指数としたべき乗を除数Ｂで除算した場合の商とする。
【０１１１】
また、指数法則により、以下の（５）、（６）式が成り立つ。
【数５】
【０１１２】
【数６】
【０１１３】
ここで、（６）式に（３）式を代入すると、（７）式が成り立つ。
【数７】
【０１１４】
ここで、（７）式を部分的に展開すると、（８）式が成り立つ。
【数８】
【０１１５】
ここで、（８）式に対して、（４）式を代入すると、（９）式が成り立つ。
【数９】
【０１１６】
そして、（９）式のそれぞれの辺について、除数Ｂで除算した場合の剰余は、共通鍵Ｃとなる。
【０１１７】
よって、第１共通鍵生成装置１０、第２共通鍵生成装置２０、及び第３共通鍵生成装置３０それぞれにおいて、秘密鍵を交換することなく共通鍵を生成することができる。ここで、除数Ｂが桁数の大きい素数である場合、基数Ａ、除数Ｂ、並びに１次中間鍵、２次中間鍵を知っていたとしても、これらの値から、共通鍵Ｃを求めるには、膨大な計算量が必要となる。よって、共通鍵生成システム１は、３者間で安全に共通鍵を共有することができる。
【０１１８】
また、共通鍵生成システム１は、べき剰余算出部５０において第１中間値ＡＴ及び第２中間値ＭＴを、１０のべき乗により構成される多項式に変換し、これら多項式を乗算して、展開することにより、第１中間値ＡＴと第２中間値ＭＴとの乗算、及び第１中間値ＡＴの２乗の計算を行う。
【０１１９】
このようにすることで、共通鍵生成システム１は、第１中間値ＡＴと第２中間値ＭＴが長大桁数である場合、この長大桁数よりも桁数が小さい項を複数含む多項式の乗算により、第１中間値ＡＴと第２中間値ＭＴの乗算や第１中間値ＡＴの２乗の計算を行うことができる。このため、共通鍵生成システム１は、第１共通鍵生成装置１０、第２共通鍵生成装置２０、及び第３共通鍵生成装置３０において、市販の表計算ソフト等を利用して共通鍵を生成する場合に、この表計算ソフト等で有効桁数が限られていても、桁あふれ等による情報落ちを防ぐことができ、問題なく共通鍵を生成することができる。
【０１２０】
以上、本発明の実施形態について説明したが、本発明は本実施形態に限定されるものではなく、本発明の目的を達成できる範囲での変形、改良等は本発明に含まれるものである。
【０１２１】
本実施形態では、第３共通鍵生成装置３０において、１次中間鍵ＭＦ３を生成し、第１共通鍵生成装置１０において、１次中間鍵ＭＦ３を用いて２次中間鍵ＭＳ２を生成するとともに、第２共通鍵生成装置２０において、１次中間鍵ＭＦ３を用いて２次中間鍵ＭＳ３を生成することとしたが、このように１次中間鍵ＭＦ３、２次中間鍵ＭＳ２、及び２次中間鍵ＭＳ３を生成しなくてもよい。すなわち、２次中間鍵ＭＳ２は、第２共通鍵生成装置２０において、１次中間鍵ＭＦ１を用いて生成することができ、２次中間鍵ＭＳ３は、第３共通鍵生成装置３０において、１次中間鍵ＭＦ２を用いて生成することができる。このため、２次中間鍵ＭＳ２、２次中間鍵ＭＳ３を冗長に生成しないようにしてもよい。
【０１２２】
すなわち、共通鍵生成システム１は、第１共通鍵生成装置１０、第２共通鍵生成装置２０、及び第３共通鍵生成装置３０のいずれかにおいて、２次中間鍵ＭＳ１、２次中間鍵ＭＳ２、及び２次中間鍵ＭＳ３をそれぞれ１個のみ生成できるように構成するようにしてもよい。このようにすることで、第１共通鍵生成装置１０、第２共通鍵生成装置２０、及び第３共通鍵生成装置３０間におけるやりとりを減らして通信量を削減することができる。
【符号の説明】
【０１２３】
１ 共通鍵生成システム
１０ 第１共通鍵生成装置
１１ 第１通信部
１２ 第１鍵情報生成部
１３ 第１中間鍵生成部
１４ 第１共通鍵生成部
２０ 第２共通鍵生成装置
２１ 第２通信部
２２ 第２鍵情報生成部
２３ 第２中間鍵生成部
２４ 第２共通鍵生成部
３０ 第３共通鍵生成装置
３１ 第３通信部
３２ 第３鍵情報生成部
３３ 第３中間鍵生成部
３４ 第３共通鍵生成部
５０ べき剰余算出部
５１ 入力受付部
５２ 初期設定部
５３ 変換部
５４ 計数部
５５ 基数算出部
５６ 剰余算出部
５７ シフト部
５８ 反復実行部
５９ 出力部
【特許請求の範囲】
【請求項１】
第１共通鍵生成装置、第２共通鍵生成装置、及び第３共通鍵生成装置を備え、前記第１共通鍵生成装置、前記第２共通鍵生成装置、及び第３共通鍵生成装置において共通鍵を生成する共通鍵生成システムであって、
前記第１共通鍵生成装置は、
基数、除数、及び第１秘密鍵を生成する第１鍵情報生成手段と、
前記基数を底とし、前記第１秘密鍵を指数としたべき乗を、前記除数で除算した場合の剰余を算出し、当該剰余を第１の１次中間鍵とする第１中間鍵生成手段と、
前記基数、前記除数、及び前記第１の１次中間鍵を前記第２共通鍵生成装置及び前記第３共通鍵生成装置に送信する第１送信手段と、を備え、
前記第２共通鍵生成装置は、
前記第１共通鍵生成装置から、前記基数、前記除数、及び前記第１の１次中間鍵を受信する第２受信手段と、
第２秘密鍵を生成する第２鍵情報生成手段と、
前記基数を底とし、前記第２秘密鍵を指数としたべき乗を、前記除数で除算した場合の剰余を算出し、当該剰余を第２の１次中間鍵とする第２中間鍵生成手段と、
前記第２の１次中間鍵を前記第１共通鍵生成装置及び前記第３共通鍵生成装置に送信する第２送信手段と、を備え、
前記第３共通鍵生成装置は、
前記第１共通鍵生成装置から、前記基数、前記除数、及び前記第１の１次中間鍵を受信する第３受信手段と、
第３秘密鍵を生成する第３鍵情報生成手段と、
前記基数を底とし、前記第３秘密鍵を指数としたべき乗を、前記除数で除算した場合の剰余を算出し、当該剰余を第３の１次中間鍵とする第３中間鍵生成手段と、
前記第３の１次中間鍵を前記第１共通鍵生成装置及び前記第２共通鍵生成装置に送信する第３送信手段と、を備え、
前記第１共通鍵生成装置は、前記第２共通鍵生成装置から前記第２の１次中間鍵を受信するとともに、前記第３共通鍵生成装置から前記第３の１次中間鍵を受信する第１受信手段を更に備え、
前記第１中間鍵生成手段は、前記第１受信手段により受信した前記第２の１次中間鍵を底とし、前記第１秘密鍵を指数としたべき乗を、前記除数で除算した場合の剰余を算出し、当該剰余を第１の２次中間鍵とするとともに、前記第１受信手段により受信した前記第３の１次中間鍵を底とし、前記第１秘密鍵を指数としたべき乗を、前記除数で除算した場合の剰余を算出し、当該剰余を第２の２次中間鍵とし、
前記第１送信手段は、前記第２の２次中間鍵を前記第２共通鍵生成装置に送信するとともに、前記第１の２次中間鍵を前記第３共通鍵生成装置に送信し、
前記第２受信手段は、第３共通鍵生成装置から前記第３の１次中間鍵を更に受信し、
前記第２中間鍵生成手段は、前記第２受信手段により受信した前記第３の１次中間鍵を底とし、前記第２秘密鍵を指数としたべき乗を、前記除数で除算した場合の剰余を算出し、当該剰余を第３の２次中間鍵とするとともに、前記第２受信手段により受信した前記第１の１次中間鍵を底とし、前記第２秘密鍵を指数としたべき乗を、前記除数で除算した場合の剰余を算出し、当該剰余を前記第１の２次中間鍵とし、
前記第２送信手段は、前記第３の２次中間鍵を前記第１共通鍵生成装置に送信するとともに、前記第１の２次中間鍵を前記第３共通鍵生成装置に送信し、
前記第３受信手段は、第２共通鍵生成装置から前記第２の１次中間鍵を更に受信し、
前記第３中間鍵生成手段は、前記第３受信手段により受信した前記第１の１次中間鍵を底とし、前記第３秘密鍵を指数としたべき乗を、前記除数で除算した場合の剰余を算出し、当該剰余を前記第２の２次中間鍵とするとともに、前記第３受信手段により受信した前記第２の１次中間鍵を底とし、前記第３秘密鍵を指数としたべき乗を、前記除数で除算した場合の剰余を算出し、当該剰余を前記第３の２次中間鍵とし、
前記第３送信手段は、前記第３の２次中間鍵を前記第１共通鍵生成装置に送信するとともに、前記第２の２次中間鍵を前記第２共通鍵生成装置に送信し、
前記第１受信手段は、前記第２共通鍵生成装置から前記第３の２次中間鍵を受信するとともに、前記第３共通鍵生成装置から前記第３の２次中間鍵を受信し、
前記第１共通鍵生成装置は、前記第１受信手段により受信した前記第３の２次中間鍵を底とし、前記第１秘密鍵を指数としたべき乗を、前記除数で除算した場合の剰余を算出し、当該剰余を共通鍵とする第１共通鍵生成手段を更に備え、
前記第２受信手段は、前記第３共通鍵生成装置から前記第２の２次中間鍵を受信するとともに、前記第１共通鍵生成装置から前記第２の２次中間鍵を受信し、
前記第２共通鍵生成装置は、前記第２受信手段により受信した前記第２の２次中間鍵を底とし、前記第２秘密鍵を指数としたべき乗を、前記除数で除算した場合の剰余を算出し、当該剰余を前記共通鍵とする第２共通鍵生成手段を更に備え、
前記第３受信手段は、前記第１共通鍵生成装置から前記第１の２次中間鍵を受信するとともに、前記第２共通鍵生成装置から前記第１の２次中間鍵を受信し、
前記第３共通鍵生成装置は、前記第３受信手段により受信した前記第１の２次中間鍵を底とし、前記第３秘密鍵を指数としたべき乗を、前記除数で除算した場合の剰余を算出し、当該剰余を前記共通鍵とする第３共通鍵生成手段を更に備える共通鍵生成システム。
【請求項２】
第１共通鍵生成装置、第２共通鍵生成装置、及び第３共通鍵生成装置が共通鍵を生成する共通鍵生成方法であって、
前記第１共通鍵生成装置が、基数、除数、及び第１秘密鍵を生成するステップと、
前記第１共通鍵生成装置が、前記基数を底とし、前記第１秘密鍵を指数としたべき乗を、前記除数で除算した場合の剰余を算出し、当該剰余を第１の１次中間鍵とするステップと、
前記第１共通鍵生成装置が、前記基数、前記除数、及び前記第１の１次中間鍵を前記第２共通鍵生成装置及び前記第３共通鍵生成装置に送信するステップと、
前記第２共通鍵生成装置が、前記第１共通鍵生成装置から、前記基数、前記除数、及び前記第１の１次中間鍵を受信するステップと、
前記第２共通鍵生成装置が、第２秘密鍵を生成するステップと、
前記第２共通鍵生成装置が、前記基数を底とし、前記第２秘密鍵を指数としたべき乗を、前記除数で除算した場合の剰余を算出し、当該剰余を第２の１次中間鍵とするステップと、
前記第２共通鍵生成装置が、前記第２の１次中間鍵を前記第１共通鍵生成装置及び前記第３共通鍵生成装置に送信するステップと、
前記第３共通鍵生成装置が、前記第１共通鍵生成装置から、前記基数、前記除数、及び前記第１の１次中間鍵を受信するステップと、
前記第３共通鍵生成装置が、第３秘密鍵を生成するステップと、
前記第３共通鍵生成装置が、前記基数を底とし、前記第３秘密鍵を指数としたべき乗を、前記除数で除算した場合の剰余を算出し、当該剰余を第３の１次中間鍵とするステップと、
前記第３共通鍵生成装置が、前記第３の１次中間鍵を前記第１共通鍵生成装置及び前記第２共通鍵生成装置に送信するステップと、
前記第１共通鍵生成装置が、前記第２共通鍵生成装置から前記第２の１次中間鍵を受信するステップと、
前記第１共通鍵生成装置が、前記第２の１次中間鍵を底とし、前記第１秘密鍵を指数としたべき乗を、前記除数で除算した場合の剰余を算出し、当該剰余を第１の２次中間鍵とするステップと、
前記第１共通鍵生成装置が、前記第１の２次中間鍵を前記第３共通鍵生成装置に送信するステップと、
前記第１共通鍵生成装置が、前記第３共通鍵生成装置から前記第３の１次中間鍵を受信するステップと、
前記第１共通鍵生成装置が、前記第３の１次中間鍵を底とし、前記第１秘密鍵を指数としたべき乗を、前記除数で除算した場合の剰余を算出し、当該剰余を第２の２次中間鍵とするステップと、
前記第１共通鍵生成装置が、前記第２の２次中間鍵を前記第２共通鍵生成装置に送信するステップと、
前記第２共通鍵生成装置が、前記第１の１次中間鍵を底とし、前記第２秘密鍵を指数としたべき乗を、前記除数で除算した場合の剰余を算出し、当該剰余を第１の２次中間鍵とするステップと、
前記第２共通鍵生成装置が、前記第１の２次中間鍵を前記第３共通鍵生成装置に送信するステップと、
前記第２共通鍵生成装置が、前記第３共通鍵生成装置から前記第３の１次中間鍵を受信するステップと、
前記第２共通鍵生成装置が、前記第３の１次中間鍵を底とし、前記第２秘密鍵を指数としたべき乗を、前記除数で除算した場合の剰余を算出し、当該剰余を第３の２次中間鍵とするステップと、
前記第２共通鍵生成装置が、前記第３の２次中間鍵を前記第１共通鍵生成装置に送信するステップと、
前記第３共通鍵生成装置が、前記第１の１次中間鍵を底とし、前記第３秘密鍵を指数としたべき乗を、前記除数で除算した場合の剰余を算出し、当該剰余を第２の２次中間鍵とするステップと、
前記第３共通鍵生成装置が、前記第２の２次中間鍵を前記第２共通鍵生成装置に送信するステップと、
前記第３共通鍵生成装置が、前記第２共通鍵生成装置から前記第２の１次中間鍵を受信するステップと、
前記第３共通鍵生成装置が、前記第２の１次中間鍵を底とし、前記第３秘密鍵を指数としたべき乗を、前記除数で除算した場合の剰余を算出し、当該剰余を第３の２次中間鍵とするステップと、
前記第３共通鍵生成装置が、前記第３の２次中間鍵を前記第１共通鍵生成装置に送信するステップと、
前記第１共通鍵生成装置が、前記第２共通鍵生成装置又は前記第３共通鍵生成装置から前記第３の２次中間鍵を受信するステップと、
前記第１共通鍵生成装置が、前記第３の２次中間鍵を底とし、前記第１秘密鍵を指数としたべき乗を、前記除数で除算した場合の剰余を算出し、当該剰余を共通鍵とするステップと、
前記第２共通鍵生成装置が、前記第３共通鍵生成装置又は前記第１共通鍵生成装置から前記第２の２次中間鍵を受信するステップと、
前記第２共通鍵生成装置が、前記第２の２次中間鍵を底とし、前記第２秘密鍵を指数としたべき乗を、前記除数で除算した場合の剰余を算出し、当該剰余を前記共通鍵とするステップと、
前記第３共通鍵生成装置が、前記第１共通鍵生成装置又は前記第２共通鍵生成装置から前記第１の２次中間鍵を受信するステップと、
前記第３共通鍵生成装置が、前記第１の２次中間鍵を底とし、前記第３秘密鍵を指数としたべき乗を、前記除数で除算した場合の剰余を算出し、当該剰余を前記共通鍵とするステップと、を含む共通鍵生成方法。
【請求項１】
第１共通鍵生成装置、第２共通鍵生成装置、及び第３共通鍵生成装置を備え、前記第１共通鍵生成装置、前記第２共通鍵生成装置、及び第３共通鍵生成装置において共通鍵を生成する共通鍵生成システムであって、
前記第１共通鍵生成装置は、
基数、除数、及び第１秘密鍵を生成する第１鍵情報生成手段と、
前記基数を底とし、前記第１秘密鍵を指数としたべき乗を、前記除数で除算した場合の剰余を算出し、当該剰余を第１の１次中間鍵とする第１中間鍵生成手段と、
前記基数、前記除数、及び前記第１の１次中間鍵を前記第２共通鍵生成装置及び前記第３共通鍵生成装置に送信する第１送信手段と、を備え、
前記第２共通鍵生成装置は、
前記第１共通鍵生成装置から、前記基数、前記除数、及び前記第１の１次中間鍵を受信する第２受信手段と、
第２秘密鍵を生成する第２鍵情報生成手段と、
前記基数を底とし、前記第２秘密鍵を指数としたべき乗を、前記除数で除算した場合の剰余を算出し、当該剰余を第２の１次中間鍵とする第２中間鍵生成手段と、
前記第２の１次中間鍵を前記第１共通鍵生成装置及び前記第３共通鍵生成装置に送信する第２送信手段と、を備え、
前記第３共通鍵生成装置は、
前記第１共通鍵生成装置から、前記基数、前記除数、及び前記第１の１次中間鍵を受信する第３受信手段と、
第３秘密鍵を生成する第３鍵情報生成手段と、
前記基数を底とし、前記第３秘密鍵を指数としたべき乗を、前記除数で除算した場合の剰余を算出し、当該剰余を第３の１次中間鍵とする第３中間鍵生成手段と、
前記第３の１次中間鍵を前記第１共通鍵生成装置及び前記第２共通鍵生成装置に送信する第３送信手段と、を備え、
前記第１共通鍵生成装置は、前記第２共通鍵生成装置から前記第２の１次中間鍵を受信するとともに、前記第３共通鍵生成装置から前記第３の１次中間鍵を受信する第１受信手段を更に備え、
前記第１中間鍵生成手段は、前記第１受信手段により受信した前記第２の１次中間鍵を底とし、前記第１秘密鍵を指数としたべき乗を、前記除数で除算した場合の剰余を算出し、当該剰余を第１の２次中間鍵とするとともに、前記第１受信手段により受信した前記第３の１次中間鍵を底とし、前記第１秘密鍵を指数としたべき乗を、前記除数で除算した場合の剰余を算出し、当該剰余を第２の２次中間鍵とし、
前記第１送信手段は、前記第２の２次中間鍵を前記第２共通鍵生成装置に送信するとともに、前記第１の２次中間鍵を前記第３共通鍵生成装置に送信し、
前記第２受信手段は、第３共通鍵生成装置から前記第３の１次中間鍵を更に受信し、
前記第２中間鍵生成手段は、前記第２受信手段により受信した前記第３の１次中間鍵を底とし、前記第２秘密鍵を指数としたべき乗を、前記除数で除算した場合の剰余を算出し、当該剰余を第３の２次中間鍵とするとともに、前記第２受信手段により受信した前記第１の１次中間鍵を底とし、前記第２秘密鍵を指数としたべき乗を、前記除数で除算した場合の剰余を算出し、当該剰余を前記第１の２次中間鍵とし、
前記第２送信手段は、前記第３の２次中間鍵を前記第１共通鍵生成装置に送信するとともに、前記第１の２次中間鍵を前記第３共通鍵生成装置に送信し、
前記第３受信手段は、第２共通鍵生成装置から前記第２の１次中間鍵を更に受信し、
前記第３中間鍵生成手段は、前記第３受信手段により受信した前記第１の１次中間鍵を底とし、前記第３秘密鍵を指数としたべき乗を、前記除数で除算した場合の剰余を算出し、当該剰余を前記第２の２次中間鍵とするとともに、前記第３受信手段により受信した前記第２の１次中間鍵を底とし、前記第３秘密鍵を指数としたべき乗を、前記除数で除算した場合の剰余を算出し、当該剰余を前記第３の２次中間鍵とし、
前記第３送信手段は、前記第３の２次中間鍵を前記第１共通鍵生成装置に送信するとともに、前記第２の２次中間鍵を前記第２共通鍵生成装置に送信し、
前記第１受信手段は、前記第２共通鍵生成装置から前記第３の２次中間鍵を受信するとともに、前記第３共通鍵生成装置から前記第３の２次中間鍵を受信し、
前記第１共通鍵生成装置は、前記第１受信手段により受信した前記第３の２次中間鍵を底とし、前記第１秘密鍵を指数としたべき乗を、前記除数で除算した場合の剰余を算出し、当該剰余を共通鍵とする第１共通鍵生成手段を更に備え、
前記第２受信手段は、前記第３共通鍵生成装置から前記第２の２次中間鍵を受信するとともに、前記第１共通鍵生成装置から前記第２の２次中間鍵を受信し、
前記第２共通鍵生成装置は、前記第２受信手段により受信した前記第２の２次中間鍵を底とし、前記第２秘密鍵を指数としたべき乗を、前記除数で除算した場合の剰余を算出し、当該剰余を前記共通鍵とする第２共通鍵生成手段を更に備え、
前記第３受信手段は、前記第１共通鍵生成装置から前記第１の２次中間鍵を受信するとともに、前記第２共通鍵生成装置から前記第１の２次中間鍵を受信し、
前記第３共通鍵生成装置は、前記第３受信手段により受信した前記第１の２次中間鍵を底とし、前記第３秘密鍵を指数としたべき乗を、前記除数で除算した場合の剰余を算出し、当該剰余を前記共通鍵とする第３共通鍵生成手段を更に備える共通鍵生成システム。
【請求項２】
第１共通鍵生成装置、第２共通鍵生成装置、及び第３共通鍵生成装置が共通鍵を生成する共通鍵生成方法であって、
前記第１共通鍵生成装置が、基数、除数、及び第１秘密鍵を生成するステップと、
前記第１共通鍵生成装置が、前記基数を底とし、前記第１秘密鍵を指数としたべき乗を、前記除数で除算した場合の剰余を算出し、当該剰余を第１の１次中間鍵とするステップと、
前記第１共通鍵生成装置が、前記基数、前記除数、及び前記第１の１次中間鍵を前記第２共通鍵生成装置及び前記第３共通鍵生成装置に送信するステップと、
前記第２共通鍵生成装置が、前記第１共通鍵生成装置から、前記基数、前記除数、及び前記第１の１次中間鍵を受信するステップと、
前記第２共通鍵生成装置が、第２秘密鍵を生成するステップと、
前記第２共通鍵生成装置が、前記基数を底とし、前記第２秘密鍵を指数としたべき乗を、前記除数で除算した場合の剰余を算出し、当該剰余を第２の１次中間鍵とするステップと、
前記第２共通鍵生成装置が、前記第２の１次中間鍵を前記第１共通鍵生成装置及び前記第３共通鍵生成装置に送信するステップと、
前記第３共通鍵生成装置が、前記第１共通鍵生成装置から、前記基数、前記除数、及び前記第１の１次中間鍵を受信するステップと、
前記第３共通鍵生成装置が、第３秘密鍵を生成するステップと、
前記第３共通鍵生成装置が、前記基数を底とし、前記第３秘密鍵を指数としたべき乗を、前記除数で除算した場合の剰余を算出し、当該剰余を第３の１次中間鍵とするステップと、
前記第３共通鍵生成装置が、前記第３の１次中間鍵を前記第１共通鍵生成装置及び前記第２共通鍵生成装置に送信するステップと、
前記第１共通鍵生成装置が、前記第２共通鍵生成装置から前記第２の１次中間鍵を受信するステップと、
前記第１共通鍵生成装置が、前記第２の１次中間鍵を底とし、前記第１秘密鍵を指数としたべき乗を、前記除数で除算した場合の剰余を算出し、当該剰余を第１の２次中間鍵とするステップと、
前記第１共通鍵生成装置が、前記第１の２次中間鍵を前記第３共通鍵生成装置に送信するステップと、
前記第１共通鍵生成装置が、前記第３共通鍵生成装置から前記第３の１次中間鍵を受信するステップと、
前記第１共通鍵生成装置が、前記第３の１次中間鍵を底とし、前記第１秘密鍵を指数としたべき乗を、前記除数で除算した場合の剰余を算出し、当該剰余を第２の２次中間鍵とするステップと、
前記第１共通鍵生成装置が、前記第２の２次中間鍵を前記第２共通鍵生成装置に送信するステップと、
前記第２共通鍵生成装置が、前記第１の１次中間鍵を底とし、前記第２秘密鍵を指数としたべき乗を、前記除数で除算した場合の剰余を算出し、当該剰余を第１の２次中間鍵とするステップと、
前記第２共通鍵生成装置が、前記第１の２次中間鍵を前記第３共通鍵生成装置に送信するステップと、
前記第２共通鍵生成装置が、前記第３共通鍵生成装置から前記第３の１次中間鍵を受信するステップと、
前記第２共通鍵生成装置が、前記第３の１次中間鍵を底とし、前記第２秘密鍵を指数としたべき乗を、前記除数で除算した場合の剰余を算出し、当該剰余を第３の２次中間鍵とするステップと、
前記第２共通鍵生成装置が、前記第３の２次中間鍵を前記第１共通鍵生成装置に送信するステップと、
前記第３共通鍵生成装置が、前記第１の１次中間鍵を底とし、前記第３秘密鍵を指数としたべき乗を、前記除数で除算した場合の剰余を算出し、当該剰余を第２の２次中間鍵とするステップと、
前記第３共通鍵生成装置が、前記第２の２次中間鍵を前記第２共通鍵生成装置に送信するステップと、
前記第３共通鍵生成装置が、前記第２共通鍵生成装置から前記第２の１次中間鍵を受信するステップと、
前記第３共通鍵生成装置が、前記第２の１次中間鍵を底とし、前記第３秘密鍵を指数としたべき乗を、前記除数で除算した場合の剰余を算出し、当該剰余を第３の２次中間鍵とするステップと、
前記第３共通鍵生成装置が、前記第３の２次中間鍵を前記第１共通鍵生成装置に送信するステップと、
前記第１共通鍵生成装置が、前記第２共通鍵生成装置又は前記第３共通鍵生成装置から前記第３の２次中間鍵を受信するステップと、
前記第１共通鍵生成装置が、前記第３の２次中間鍵を底とし、前記第１秘密鍵を指数としたべき乗を、前記除数で除算した場合の剰余を算出し、当該剰余を共通鍵とするステップと、
前記第２共通鍵生成装置が、前記第３共通鍵生成装置又は前記第１共通鍵生成装置から前記第２の２次中間鍵を受信するステップと、
前記第２共通鍵生成装置が、前記第２の２次中間鍵を底とし、前記第２秘密鍵を指数としたべき乗を、前記除数で除算した場合の剰余を算出し、当該剰余を前記共通鍵とするステップと、
前記第３共通鍵生成装置が、前記第１共通鍵生成装置又は前記第２共通鍵生成装置から前記第１の２次中間鍵を受信するステップと、
前記第３共通鍵生成装置が、前記第１の２次中間鍵を底とし、前記第３秘密鍵を指数としたべき乗を、前記除数で除算した場合の剰余を算出し、当該剰余を前記共通鍵とするステップと、を含む共通鍵生成方法。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【公開番号】特開２０１２−１２４５６８（Ｐ２０１２−１２４５６８Ａ）
【公開日】平成２４年６月２８日（２０１２．６．２８）
【国際特許分類】
【出願番号】特願２０１０−２７１４９３（Ｐ２０１０−２７１４９３）
【出願日】平成２２年１２月６日（２０１０．１２．６）
【出願人】（０００２１１３０７）中国電力株式会社 (6,505)
【Ｆターム（参考）】
【公開日】平成２４年６月２８日（２０１２．６．２８）
【国際特許分類】
【出願日】平成２２年１２月６日（２０１０．１２．６）
【出願人】（０００２１１３０７）中国電力株式会社 (6,505)
【Ｆターム（参考）】
[ Back to top ]