JP3587746B2 - Secret key generator, encryption device, encryption communication method, encryption communication system, and recording medium - Google Patents

Description

【００１５】
但し、ｇ：Ｎを法とする最大生成元
ｔ：２以上の整数
【００１６】
請求項２に係る秘密鍵生成器は、エンティティの特定情報と秘密の対称行列とを用いて、前記エンティティ固有の秘密鍵を生成する秘密鍵生成器において、エンティティＸの特定情報に基づいてエンティティＸの公開鍵ベクトルｖ_X （ｘ₁ ，ｘ₂ ）を取得する手段と、取得した公開鍵ベクトルｖ_X と下記（Ｃ）で示される秘密の対称行列Ｈとを用いて、Ｎ＝ＰＱ（Ｐ，Ｑは素数）を法とする下記（Ｄ）に示すような秘密鍵Ｇ₁ ，Ｇ₂ ，Ｇ₃ を求める手段とを備えることを特徴とする。
【００１７】
【数１７】

【００１８】
但し、ｇ：Ｎを法とする最大生成元
ｍ：２以上の整数
【００１９】
請求項３に係る秘密鍵生成器は、エンティティの特定情報と秘密の対称行列とを用いて、前記エンティティ固有の秘密鍵を生成する秘密鍵生成器において、エンティティＸの特定情報に基づいてエンティティＸの公開鍵ベクトルｖ_X （ｘ₁ ，ｘ₂ ，…，ｘ_N ）を取得する手段と、取得した公開鍵ベクトルｖ_X と下記（Ｅ）で示される秘密の対称行列Ｈとを用いて、Ｎ′＝ＰＱｒ₁ ｒ₂ …ｒ_S （Ｐ，Ｑ，ｒ₁ 〜ｒ_S は素数）を法とする下記（Ｆ）及び（Ｇ）に示すような秘密鍵Ｇ₁ ，Ｇ₂ ，…，Ｇ_t+1 及びＨ₂ ，…，Ｈ_i ，…，Ｈ_N を求める手段とを備えることを特徴とする。
【００２０】
【数１８】

【００２１】
但し、ｇ：Ｎ′を法とする最大生成元
Ｓ，ｔ：２以上の整数
【００２２】
請求項４に係る暗号化装置は、各エンティティの特定情報と秘密の対称行列とを用いて生成した各エンティティ固有の秘密鍵と、暗号文の送信先である相手のエンティティの特定情報に基づいて生成した公開鍵とにより生成した共通鍵を用いて平文を暗号文に暗号化する暗号化装置において、請求項１記載の秘密鍵生成器により生成されたエンティティＸの秘密鍵を取得する手段と、取得した秘密鍵と相手のエンティティＹの特定情報に基づくエンティティＹの公開鍵ベクトルｖ_y （ｙ₁ ，ｙ₂ ）とを用いて、下記（Ｈ）に示すような共通鍵Ｋ_XYを求める手段とを備えることを特徴とする。
【００２３】
【数１９】

【００２４】
請求項５に係る暗号化装置は、各エンティティの特定情報と秘密の対称行列とを用いて生成した各エンティティ固有の秘密鍵と、暗号文の送信先である相手のエンティティの特定情報に基づいて生成した公開鍵とにより生成した共通鍵を用いて平文を暗号文に暗号化する暗号化装置において、請求項２記載の秘密鍵生成器により生成されたエンティティＸの秘密鍵を取得する手段と、取得した秘密鍵と相手のエンティティＹの特定情報に基づくエンティティＹの公開鍵ベクトルｖ_y （ｙ₁ ，ｙ₂ ）とを用いて、下記（Ｉ）に示すような共通鍵Ｋ_XYを求める手段とを備えることを特徴とする。
【００２５】
【数２０】

【００２６】
請求項６に係る暗号化装置は、各エンティティの特定情報と秘密の対称行列とを用いて生成した各エンティティ固有の秘密鍵と、暗号文の送信先である相手のエンティティの特定情報に基づいて生成した公開鍵とにより生成した共通鍵を用いて平文を暗号文に暗号化する暗号化装置において、請求項３記載の秘密鍵生成器により生成されたエンティティＸの秘密鍵を取得する手段と、取得した秘密鍵と相手のエンティティＹの特定情報に基づく公開鍵ベクトル（ｙ₂ ，ｙ₃ ，…，ｙ_N ）とを用いて、下記（Ｊ）に示すような中間値Ｊを求める手段と、取得した秘密鍵と求めた中間値ＪとエンティティＹの特定情報に基づく公開鍵ベクトル（ｙ₁ ）とを用いて、下記（Ｋ）に示すような共通鍵Ｋ_XYを求める手段とを備えることを特徴とする。
【００２７】
【数２１】

【００２８】
請求項７に係る暗号化装置は、請求項４〜６の何れかにおいて、各エンティティ固有の前記秘密鍵と相手のエンティティの前記公開鍵とを用いて、前記共通鍵を生成するための中間鍵を生成する手段と、生成した中間鍵を各エンティティ側で記憶しておく手段とを備えることを特徴とする。
【００２９】
請求項８に係る暗号化装置は、請求項７において、生成した中間鍵をＩＣカードに記憶しておき、記憶した中間鍵を用いて前記ＩＣカードにて前記共通鍵を生成するようにしたことを特徴とする。
【００３０】
請求項９に係る暗号通信方法は、センタ装置から各エンティティ装置へ各エンティティ固有の秘密鍵を送付し、一方のエンティティ装置が前記センタ装置から送付された該エンティティ固有の秘密鍵から求めた共通鍵を用いて平文を暗号文に暗号化して他方のエンティティ装置へ伝送し、該他方のエンティティ装置が伝送された暗号文を、前記センタ装置から送付された該エンティティ固有の秘密鍵から求めた、前記共通鍵と同一の共通鍵を用いて元の平文に復号することにより、エンティティ装置間で情報の通信を行う暗号通信方法において、エンティティＸの特定情報に基づいてエンティティＸの公開鍵ベクトルｖ_X （ｘ₁ ，ｘ₂ ）を取得するステップと、取得した公開鍵ベクトルｖ_X と下記（Ｌ）で示される秘密の対称行列Ｈとを用いて、Ｎ＝ＰＱ（Ｐ，Ｑは素数）を法とする下記（Ｍ）に示すような秘密鍵を求めるステップと、求めた秘密鍵をエンティティ装置へ送付するステップとを有することを特徴とする。
【００３１】
【数２２】

【００３２】
但し、ｇ：Ｎを法とする最大生成元
ｔ：２以上の整数
【００３３】
請求項１０に係る暗号通信方法は、センタ装置から各エンティティ装置へ各エンティティ固有の秘密鍵を送付し、一方のエンティティ装置が前記センタ装置から送付された該エンティティ固有の秘密鍵から求めた共通鍵を用いて平文を暗号文に暗号化して他方のエンティティ装置へ伝送し、該他方のエンティティ装置が伝送された暗号文を、前記センタ装置から送付された該エンティティ固有の秘密鍵から求めた、前記共通鍵と同一の共通鍵を用いて元の平文に復号することにより、エンティティ装置間で情報の通信を行う暗号通信方法において、エンティティＸの特定情報に基づいてエンティティＸの公開鍵ベクトルｖ_X （ｘ₁ ，ｘ₂ ）を取得するステップと、取得した公開鍵ベクトルｖ_X と下記（Ｎ）で示される秘密の対称行列Ｈとを用いて、Ｎ＝ＰＱ（Ｐ，Ｑは素数）を法とする下記（Ｏ）に示すような秘密鍵Ｇ₁ ，Ｇ₂ ，Ｇ₃ を求めるステップと、求めた秘密鍵をエンティティ装置へ送付するステップとを有することを特徴とする。
【００３４】
【数２３】

【００３５】
但し、ｇ：Ｎを法とする最大生成元
ｍ：２以上の整数
【００３６】
請求項１１に係る暗号通信方法は、センタ装置から各エンティティ装置へ各エンティティ固有の秘密鍵を送付し、一方のエンティティ装置が前記センタ装置から送付された該エンティティ固有の秘密鍵から求めた共通鍵を用いて平文を暗号文に暗号化して他方のエンティティ装置へ伝送し、該他方のエンティティ装置が伝送された暗号文を、前記センタ装置から送付された該エンティティ固有の秘密鍵から求めた、前記共通鍵と同一の共通鍵を用いて元の平文に復号することにより、エンティティ装置間で情報の通信を行う暗号通信方法において、エンティティＸの特定情報に基づいてエンティティＸのＮ次元の公開鍵ベクトルｖ_X （ｘ₁ ，ｘ₂ ，…，ｘ_N ）を取得するステップと、取得した公開鍵ベクトルｖ_X と下記（Ｐ）で示される秘密の対称行列Ｈとを用いて、Ｎ′＝ＰＱｒ₁ ｒ₂ …ｒ_S （Ｐ，Ｑ，ｒ₁ 〜ｒ_S は素数）を法とする下記（Ｑ）及び（Ｒ）に示すような秘密鍵Ｇ₁ ，Ｇ₂ ，…，Ｇ_t+1 及びＨ₂ ，…，Ｈ_i ，…，Ｈ_N を求めるステップと、求めた秘密鍵をエンティティ装置へ送付するステップとを有することを特徴とする。
【００３７】
【数２４】

【００３８】
但し、ｇ：Ｎ′を法とする最大生成元
Ｓ，ｔ：２以上の整数
【００３９】
請求項１２に係る暗号通信方法は、請求項９〜１１の何れかにおいて、前記共通鍵を生成するための中間鍵を生成し、生成した中間鍵を各エンティティ装置側で記憶しておくことを特徴とする。
【００４０】
請求項１３に係る暗号通信方法は、請求項１２において、生成した中間鍵をＩＣカードに記憶しておき、記憶した中間鍵を用いて前記ＩＣカードにて前記共通鍵を生成することを特徴とする。
【００４１】
請求項１４に係る暗号通信システムは、送信すべき情報である平文を暗号文に暗号化する暗号化処理、及び、送信された暗号文を元の平文に復号する復号処理を、複数のエンティティ装置間で相互に行う暗号通信システムにおいて、請求項１記載の秘密鍵生成器と、生成した秘密鍵を各エンティティへ送付する手段とを有するセンタ装置、及び、エンティティＸの秘密鍵を前記センタ装置から取得する手段と、取得した秘密鍵と相手のエンティティＹの特定情報に基づくエンティティＹのＮ次元の公開鍵ベクトルｖ_y （ｙ₁ ，ｙ₂ ）とを用いて、下記（Ｓ）に示すような前記暗号化処理及び復号処理に用いる共通鍵Ｋ_XYを求める手段とを有する複数のエンティティ装置を備えることを特徴とする。
【００４２】
【数２５】

【００４３】
請求項１５に係る暗号通信システムは、送信すべき情報である平文を暗号文に暗号化する暗号化処理、及び、送信された暗号文を元の平文に復号する復号処理を、複数のエンティティ装置間で相互に行う暗号通信システムにおいて、請求項２記載の秘密鍵生成器と、生成した秘密鍵を各エンティティへ送付する手段とを有するセンタ装置、及び、エンティティＸの秘密鍵を前記センタ装置から取得する手段と、取得した秘密鍵と相手のエンティティＹの特定情報に基づくエンティティＹのＮ次元の公開鍵ベクトルｖ_y （ｙ₁ ，ｙ₂ ）とを用いて、下記（Ｔ）に示すような前記暗号化処理及び復号処理に用いる共通鍵Ｋ_XYを求める手段とを有する複数のエンティティ装置を備えることを特徴とする。
【００４４】
【数２６】

【００４５】
請求項１６に係る暗号通信システムは、送信すべき情報である平文を暗号文に暗号化する暗号化処理、及び、送信された暗号文を元の平文に復号する復号処理を、複数のエンティティ装置間で相互に行う暗号通信システムにおいて、請求項３記載の秘密鍵生成器と、生成した秘密鍵を各エンティティへ送付する手段とを有するセンタ装置、及び、エンティティＸの秘密鍵を前記センタ装置から取得する手段と、取得した秘密鍵と相手のエンティティＹの特定情報に基づくＮ−１次元の公開鍵ベクトル（ｙ₂ ，ｙ₃ ，…，ｙ_N ）とを用いて、下記（Ｕ）に示すような中間値Ｊを求める手段と、取得した秘密鍵と求めた中間値ＪとエンティティＹの特定情報に基づく１次元の公開鍵ベクトル（ｙ₁ ）とを用いて、下記（Ｖ）に示すような共通鍵Ｋ_XYを求める手段とを有する複数のエンティティ装置を備えることを特徴とする。
【００４６】
【数２７】

【００４７】
請求項１７に係る記録媒体は、コンピュータを請求項１記載の秘密鍵生成器として機能させるためのコンピュータプログラムを記録してあることを特徴とする。
【００５０】
請求項１８に係る記録媒体は、コンピュータを請求項２記載の秘密鍵生成器として機能させるためのコンピュータプログラムを記録してあることを特徴とする。
【００５３】
請求項１９に係る記録媒体は、コンピュータを請求項３記載の秘密鍵生成器として機能させるためのコンピュータプログラムを記録してあることを特徴とする。
【００６０】
【発明の実施の形態】
以下、本発明の実施の形態について具体的に説明する。
図１は、本発明の暗号通信システムの構成を示す模式図である。情報の隠匿を信頼できるセンタ１が設定されており、このセンタ１としては、例えば社会の公的機関を該当できる。このセンタ１と、この暗号系システムを利用するユーザとしての複数の各エンティティａ，ｂ，…，ｚとは、秘密通信路２ａ，２ｂ，…，２ｚにより接続されており、これらの秘密通信路２ａ，２ｂ，…，２ｚを介してセンタ１から秘密の鍵情報が各エンティティａ，ｂ，…，ｚへ伝送されるようになっている。また、２人のエンティティの間には通信路３ab，３az，３bz，…が設けられており、この通信路３ab，３az，３bz，…を介して通信情報を暗号化した暗号文が互いのエンティティ間で伝送されるようになっている。
【００６１】
まず、本発明の基本方式について説明する。
（センタ１での準備処理）
センタ１は以下の公開鍵及び秘密鍵を準備し、公開鍵を公開する。
公開鍵 Ｎ：Ｎ＝ＰＱ（Ｐ，Ｑ：５１２ビット程度の素数）
ｈ：公開鍵ベクトルを生成するための一方向性ハッシュ関数
秘密鍵 Ｈ：下記（１）に示すような２×２の対称行列
ｇ：Ｎを法とする最大生成元
【００６２】
【数３１】

【００６３】
エンティティＸ，Ｙの特定情報（ＩＤ情報）を夫々ＩＤ_X ，ＩＤ_Y とし、それらのハッシュ値を用いて、各エンティティＸ，Ｙの公開鍵（ベクトルｖ_X ，ｖ_Y ）は、下記（２），（３）で定義される。但し、ハッシュ値サイズは１０２４ビットとする。
【００６４】
【数３２】

【００６５】
（エンティティの登録処理）
エンティティＸに登録を依頼されたセンタ１は、上記（１）に示す秘密の対称行列Ｈと上記（２）に示すエンティティＸの公開鍵（ベクトルｖ_X ）とを用いて、Ｎ＝ＰＱを法とする下記（４）に示すような秘密鍵を求め、求めた秘密鍵を秘密裏にエンティティＸへ配布する。このように本発明では、対称行列Ｈよりサイズが大きい秘密鍵（２×２行列Ｈに基づく３次元の秘密鍵）を生成する。言い換えると、本発明では、センタ秘密のサイズを拡大してエンティティＸへ送付する。
【００６６】
【数３３】

【００６７】
（エンティティ間の共通鍵の生成処理）
エンティティＸは、下記（５）のような二項定理を利用した計算を行うことにより、通信相手のエンティティＹとの共通鍵Ｋ_XYを求める。この共通鍵Ｋ_XYはエンティティＹ側から求めた共通鍵Ｋ_YXと一致する。
【００６８】
【数３４】

【００６９】
なお、上記（１）に示す対称行列ＨをＭ×Ｍ（Ｍ≧３）の行列に一般化することも可能であり、この場合にはＭ項定理を利用することによって共通鍵の鍵共有を実現できる。しかしながら、センタ１から配布される秘密鍵のデータ量が一定であるという条件では、Ｍを大きくすることは安全性を弱める方向に働くので、Ｍ＝２の場合が最適である。
【００７０】
次に、上述した暗号システムにおけるエンティティ間の情報の通信について説明する。図２は、２人のエンティティＸ，Ｙ間における情報の通信状態を示す模式図である。図２の例は、エンティティＸが平文（メッセージ）Ｍを暗号文Ｃに暗号化してそれをエンティティＹへ伝送し、エンティティＹがその暗号文Ｃを元の平文（メッセージ）Ｍに復号する場合を示している。
【００７１】
エンティティＸ側には、エンティティＹの特定情報ＩＤ_Y を入力し、ハッシュ関数を利用して公開鍵（ベクトルｖ_Y ）を得る公開鍵生成器１１と、センタ１から送られる秘密鍵（上記（４）で示すもの）と公開鍵生成器１１からの公開鍵（ベクトルｖ_Y ）とに基づいてエンティティＸが求めるエンティティＹとの共通鍵Ｋ_XYを生成する共通鍵生成器１２と、共通鍵Ｋ_XYを用いて平文（メッセージ）Ｍを暗号文Ｃに暗号化して通信路３０へ出力する暗号化器１３とが備えられている。
【００７２】
また、エンティティＹ側には、エンティティＸの特定情報ＩＤ_X を入力し、ハッシュ関数を利用して公開鍵（ベクトルｖ_X ）を得る公開鍵生成器２１と、センタ１から送られる秘密鍵（上記（４）と同様なもの）と公開鍵生成器２１からの公開鍵（ベクトルｖ_X ）とに基づいてエンティティＹが求めるエンティティＸとの共通鍵Ｋ_YXを生成する共通鍵生成器２２と、共通鍵Ｋ_YXを用いて通信路３０から入力した暗号文Ｃを平文（メッセージ）Ｍに復号して出力する復号器２３とが備えられている。
【００７３】
次に、動作について説明する。エンティティＸからエンティティＹへ情報を伝送しようとする場合、まず、エンティティＹの特定情報ＩＤ_Y が公開鍵生成器１１に入力されて公開鍵（ベクトルｖ_Y ）が得られ、得られたエンティティＹの公開鍵が共通鍵生成器１２へ送られる。また、センタ１から上記（４）で示される秘密鍵が共通鍵生成器１２へ入力される。そして、上記（５）に従って共通鍵Ｋ_XYが求められて、暗号化器１３へ送られる。暗号化器１３において、この共通鍵Ｋ_XYを用いて平文（メッセージ）Ｍが暗号文Ｃに暗号化され、暗号文Ｃが通信路３０を介して伝送される。
【００７４】
通信路３０を伝送された暗号文ＣはエンティティＹの復号器２３へ入力される。エンティティＸの特定情報ＩＤ_X が公開鍵生成器２１に入力されて公開鍵（ベクトルｖ_X ）が得られ、得られたエンティティＸの公開鍵が共通鍵生成器２２へ送られる。また、センタ１から上記（４）と同様な秘密鍵が共通鍵生成器２２へ入力される。そして、上記（５）と同様に共通鍵Ｋ_YXが求められて、復号器２３へ送られる。復号器２３において、この共通鍵Ｋ_YXを用いて暗号文Ｃが平文（メッセージ）Ｍに復号される。
【００７５】
図３は、本発明の記録媒体の実施の形態の構成を示す図である。ここに例示するプログラムは、秘密の対称行列と各エンティティの公開鍵とを用いて、上記（４）に示すような秘密鍵を生成する処理を含むか、または、上記（４）に示すような自身の秘密鍵と相手エンティティの公開鍵とを用いて上記（５）に従って両エンティティ間の共通鍵を生成する処理を含んでおり、以下に説明する記録媒体に記録されている。なお、コンピュータ４０は、センタ１側か、または、各エンティティ側に設けられている。
【００７６】
図３において、コンピュータ４０とオンライン接続する記録媒体４１は、コンピュータ４０の設置場所から隔たって設置される例えばＷＷＷ(World Wide Web)のサーバコンピュータを用いてなり、記録媒体４１には前述の如きプログラム４１ａが記録されている。記録媒体４１から読み出されたプログラム４１ａがコンピュータ４０を制御することにより、各エンティティ固有の秘密鍵を生成するか、または、両エンティティ間の共通鍵を生成する。
【００７７】
コンピュータ４０の内部に設けられた記録媒体４２は、内蔵設置される例えばハードディスクドライブまたはＲＯＭ等を用いてなり、記録媒体４２には前述の如きプログラム４２ａが記録されている。記録媒体４２から読み出されたプログラム４２ａがコンピュータ４０を制御することにより、各エンティティ固有の秘密鍵を生成するか、または、両エンティティ間の共通鍵を生成する。
【００７８】
コンピュータ４０に設けられたディスクドライブ４０ａに装填して使用される記録媒体４３は、運搬可能な例えば光磁気ディスク，ＣＤ−ＲＯＭまたはフレキシブルディスク等を用いてなり、記録媒体４３には前述の如きプログラム４３ａが記録されている。記録媒体４３から読み出されたプログラム４３ａがコンピュータ４０を制御することにより、各エンティティ固有の秘密鍵を生成するか、または、両エンティティ間の共通鍵を生成する。
【００７９】
以下、本発明の安全性について考察する。攻撃目標の任意のエンティティＺの秘密鍵を導くために必要な結託者数に関して、以下の（定理）が成立する。
（定理）（ｔ＋１）人の結託により、任意のエンティティＺの秘密鍵を導ける。
【００８０】
（本発明の安全性を計算量格差に依存する方式：第１方式）
（１）基本方式をそのまま使用する方法
上記（定理）で述べたように、（ｔ＋１）人の結託によって基本方式は秘密鍵が露呈する。しかし、カーマイケル関数が不明であるので、ｙ₁ ^t-i ｙ₂ ⁱ の値は非常に大きくなる。例えばｙ₁ の大きさを１０２４ビット、ｔ＝１０００とした場合に、ｙ₁ ^t-i ｙ₂ ⁱ の大きさは１０進数で約３１万桁に達する。任意のエンティティＺの秘密鍵を導出する際には、その要素の大きさが１０進数３１万桁であるような１０００×１０００の行列に関わる演算を必要とし、更に１０００人の結託者が必要であることを考慮した場合、研究所内，事業所内，学校内等のような比較的狭い範囲での運用に限定すれば、この基本方式は十分に実用に耐えると言える。
【００８１】
（２）専用ＩＣカードを利用する方法
ここでは高機能の専用ＩＣカードを用いて共通鍵を生成することを前提にした方法、言い換えると、攻撃に要する計算量を過大にすることを目的とした方法について説明する。図４は、このＩＣカード５０の構成図である。ＩＣカード５０は，ハッシュ関数を利用して公開鍵を生成する公開鍵生成部５１と、べき乗剰余演算，積和演算を行って後述するプレ鍵（中間鍵）を生成するプレ鍵生成部５２と、生成したプレ鍵を記憶するメモリ部５３と，共通鍵を生成する共通鍵生成部５４とを有する。
【００８２】
この専用ＩＣカードを利用する方法では、以下のような条件を設定する。
（ａ） 鍵の更新期間を１カ月程度とする。
（ｂ） 共通鍵の前段階としてのプレ鍵を、１カ月程度の更新期間中に、１０分〜１時間程度の時間を費やして生成する。
（ｃ） １枚のＩＣカードに、頻繁に通信する相手エンティティに対する共通鍵のプレ鍵を数百名程度分記憶する。
【００８３】
この方法では、更新期間中の比較的長い時間を利用してＩＣカードにプレ鍵を生成させ、これにより攻撃者との計算量に格差を作ることを目的としているので、ｔの値は最小値の２に設定することができる。従って、センタ１はエンティティＸに対して、下記（６）に示す３種の秘密鍵を配布する。但し、ｍは大きな正の整数である。カーマイケル関数を知るセンタ１にとって、これらの秘密鍵を計算することは容易である。
【００８４】
【数３５】

【００８５】
エンティティＹとの共通鍵Ｋ_XYは、エンティティＸにおいて、エンティティＹのハッシュ値（ｙ₁ ，ｙ₂ ）を用いて下記（７）のように生成される。
【００８６】
【数３６】

【００８７】
ここにおいて、ｙ₁ ^m ，ｙ₂ ^m 等はカーマイケル関数によって法をとれず、整数環上で計算しなければならないので、攻撃者にとっては非常に大きな数になり、このことが計算量の上で大きな格差を生むことになる。
【００８８】
上記（７）に対応するプレ鍵Ｋ_XY′は、下記（８）のように定義される。
【００８９】
【数３７】

【００９０】
例えば、ｍ≒１０⁶ である場合、Ｊ，Ｋ，Ｌ，Ｍ≒１０⁴ に設定し、Ｊ，Ｋ，Ｌ，Ｍを秘密に保持する。一般のｔの値に対するプレ鍵は全く同様に定義される。頻繁に通信する相手エンティティとの共通鍵を生成するための時間の短縮化を図るため、即ち、共通鍵共有時の処理の負担の軽減を図るためにプレ鍵は求められているが、プレ鍵を記憶するメモリ部５３の容量は、Ｎのサイズ｜Ｎ｜を１０２４ビットとした場合、通信相手毎に約３ｋビットとなる。上述した例のように、一般にＪ，Ｋ，Ｌ，Ｍ≪ｍのように設定するので、プレ鍵Ｋ_XY′から共通鍵Ｋ_XYを生成するのに要する時間が短くなるように工夫できる。一方、攻撃者にとっては、Ｊ，Ｋ，Ｌ，Ｍの組み合わせ数がこの例においても１０¹⁶程度となり、その組み合わせを同定することは不可能である。一般に、この組み合わせ数を非常に大きな数に設定することは、ｔが大きくなるほど容易となる。
【００９１】
プレ鍵を記憶しており、しかもＪ，Ｋ，Ｌ，Ｍの組み合わせを知っている正当なエンティティでは、上記（８）に示すプレ鍵Ｋ_XY′から始めて（Ｊ＋Ｋ＋Ｌ＋Ｍ）回の累乗演算を行うだけで上記（７）に示す共通鍵Ｋ_XYを算出することができる。これに対して攻撃者では、共通鍵Ｋ_XYを算出するために４ｍ回もの累乗演算が必要である。
【００９２】
各エンティティがプレ鍵を生成するための時間と攻撃者がハッシュ値のｍ乗値ｘ₁ ^m ，ｙ₁ ^m 等を求める際に必要な計算量とを比較する。以下の条件を仮定する。
（ａ） ２個のｎ桁の数を乗算する際に必要な計算量をｎ² とする。
（ｂ） エンティティはプレ鍵を１個生成するために、例えば１カ月の鍵更新期間中に１０分間の時間が与えられる。
【００９３】
（ｇ^A ）^B mod Ｎという形の法演算に必要な計算量は、ｇ^A 及びＢのサイズを｜ｇ^A ｜，｜Ｂ｜と表記した場合、｜ｇ^A ｜×｜ｇ^A ｜×｜Ｂ｜で与えられる。｜ｇ^A ｜，｜Ｂ｜を１０２４ビットとし、更にこの法演算（ｇ^A ）^B mod Ｎが１ミリ秒で１０回実行されると仮定した場合、プレ鍵生成のための計算量は１０２４×１０２４×１００００×６００となる。この場合、ｍ＝６×１０⁶ である。一方、攻撃者にとって必要な計算量は、ｎ＝１０２４×１００００×６００であるので、（１０２４×１００００×６００）² となる。ｍ＝６×１０⁵ である場合、攻撃者にとっては正当なエンティティの約５．８６×１０⁵ 倍の計算時間、即ち４０．７日を必要とし、正当なエンティティと攻撃者との間で計算量に大きな格差が生じる。もし、プレ鍵生成のために１００分が許された場合には、この格差は１０倍に拡大され、攻撃者には４０７日の計算時間が要求されることになる。
【００９４】
ここで計算条件を変更して、以下のように仮定する。
（ａ） ２つのｎ桁の数の乗算に必要な計算量を、ｎ² でなく下記（９）に示すものとする。
【００９５】
【数３８】

【００９６】
（ｂ） プレ鍵生成のために１００分間が与えられ、しかも法演算Ａ^B mod Ｎが１０³ 倍高速化されたとする。
【００９７】
攻撃者が上述の乗算に要する計算量は、正当なエンティティの１００分に対して１３７日である。この場合、ｙ₁ ^m 等の値は１０進数約１８．５兆桁となっている。必要なメモリの容量を考えると、この攻撃は現実的でない。ここで、プレ鍵生成時間を１〜２桁増大し、また法演算を１〜２桁高速化することは容易であり、高速演算法が将来実現された場合でも、大きな計算量の格差は残存するので、この第１方式は安全性を確保できる。
【００９８】
（本発明の安全性を確率的構造に依存する方式：第２方式）
上記（１）で与えられた２×２のセンタ秘密の対称行列Ｈを、下記（10）のようにＮ×Ｎの対称行列Ｈで与える。但し、法Ｎ′は下記（11）とする。
【００９９】
【数３９】

【０１００】
ｒ₁ 〜ｒ_S は１６ビットの素数とし、これらの素数の集合をＳ_r ＝｛ｒ_i ｝と表記する。対称行列Ｈの要素ｈ_ijはランダムな個数の素数ｒ_i ∈Ｓ_r で整除されるものとする。
【０１０１】
一方、任意のエンティティＸに対するハッシュ値を下記（12）のように与える。下記（12）における成分ｘ_i は素数ｒ_i ∈Ｓ_r のランダムな積とする。
【０１０２】
【数４０】

【０１０３】
センタ１は、エンティティＸに対して、Ｎ′＝ＰＱｒ₁ ｒ₂ …ｒ_S を法として下記（13）に示す秘密鍵を秘密裏に送付する。また、同時に、下記（14）に示す秘密鍵も秘密裏に送付する。
【０１０４】
【数４１】

【０１０５】
エンティティＹに対する共通鍵は、エンティティＸにおいて次のように生成される。まず、上記（14）の秘密鍵とエンティティＹのハッシュ値（ｙ₁ 以外）とを用いて、下記（15）のように中間値Ｊを求め、求めた中間値Ｊと上記（13）の秘密鍵とエンティティＹのハッシュ値（ｙ₁ ）とを用いて、エンティティＹとの共通鍵Ｋ_XYを下記（16）に従って算出する。
【０１０６】
【数４２】

【０１０７】
具体例として各パラメータをＮ＝１６，ｔ＝１６，Ｓ＝６４に設定した場合、共通鍵Ｋ_XYの指数部を展開したときの項数は₁₆Ｈ₁₆＝₃₁Ｃ₁₆＝３００５４０１９５となる。エンティティの総数を１００万人程度としても、センタ１から配布される方程式の総数（約３２００万個）がその人数を１桁程度上回り、共通鍵Ｋ_XYの形からセンタ秘密の対称行列を導くことは困難である。また、各エンティティに配布されている方程式を連立させて解く場合、各方程式の法が一定ではなくランダムな値となってしまうこと、更にはセンタ秘密の対称行列の一部が指数部にあることにより、センタ秘密の露呈は困難である。
【０１０８】
この例において、センタ１から各エンティティへのデータ配布量は、下記（17）に示すように３２ビットである。
ｔ＋１＋Ｎ−１＝ｔ＋Ｎ＝３２ …（17）
一方、｜ＰＱ｜＝１０２４ビットとした場合、Ｎ′＝１０２４＋ｔ×Ｓ＝２０４８ビットである。従って、各エンティティに配布される総データ量は６５．５ｋビット（８．１９ｋバイト）である。なおこの場合、共通鍵生成時間は、２０４８ビットＲＳＡ暗号の復号時間の約１６倍の時間で与えられる。
【０１０９】
このように，この第２方式では、センタ１から配布される秘密鍵のうちの一部を指数部に置き、残り部分（整数環上の方程式）に確率的構造を持たせている。これらの方程式と法Ｎ′との共通因数はランダムに与えられるため、また一部の秘密鍵が指数部にあるので、縮小された共通鍵同士で比をとるといった攻撃は除かれており、結託攻撃は困難である。
【０１１０】
【発明の効果】
以上詳述したように、本発明は、構成原理が単純であり、しかも、安全性を確保したＩＤ−ＮＩＫＳにおける秘密鍵生成器，暗号化装置，暗号通信方法，暗号通信システム及び記録媒体を提供することができ、理想的なＩＤ−ＮＩＫＳの構築に寄与できる。また、プレ鍵（中間鍵）を予め求めておくようにしたので、鍵共有時の処理の負担を軽減できる。
【図面の簡単な説明】
【図１】本発明の暗号通信システムの構成を示す模式図である。
【図２】２人のエンティティ間における情報の通信状態を示す模式図である。
【図３】記録媒体の実施の形態の構成を示す図である。
【図４】ＩＣカードの構成図である。
【図５】ＩＤ−ＮＩＫＳのシステムの原理構成図である。
【符号の説明】
１ センタ
１１，２１ 公開鍵生成器
１２，２２ 共通鍵生成器
１３ 暗号化器
２３ 復号器
３０ 通信路
４０ コンピュータ
４１，４２，４３ 記録媒体
５０ ＩＣカード[0001]
TECHNICAL FIELD OF THE INVENTION
The present invention relates to a secret key generation for generating an entity-specific secret key.vessel,Encrypting device that encrypts information so that the contents of the information cannot be understood by anyone other than the parties, an encryption communication method and an encryption communication system that perform communication using ciphertext, and a recording medium that records a computer program for generating a secret key About.
[0002]
[Prior art]
In a modern society called an advanced information society, important document and image information in business is transmitted, communicated, and processed in the form of electronic information based on a computer network. Such electronic information has a property that it can be easily copied, and it is difficult to distinguish a copy from an original, and thus the importance of information security is emphasized. In particular, the realization of a computer network that satisfies the elements of “computer resource sharing”, “multi-access”, and “wide-area” is indispensable for the establishment of an advanced information society. Contains inconsistent elements. As an effective method for resolving such contradictions, cryptographic techniques that have been used mainly in military and diplomatic aspects in the past history of humankind have been attracting attention.
[0003]
Cryptography is the exchange of information so that the meaning of the information cannot be understood by anyone other than the parties. In encryption, it is encryption to convert an original sentence (plaintext) that anyone can understand into a sentence (ciphertext) whose meaning is unknown to a third party, and decryption is to return the ciphertext to plaintext. The entire process of encryption and decryption is collectively called an encryption system. In the encryption process and the decryption process, secret information called an encryption key and a decryption key are used, respectively. Since a secret decryption key is required at the time of decryption, only a person who knows the decryption key can decrypt the ciphertext, and the encryption can maintain the confidentiality of the information.
[0004]
The encryption key and the decryption key may be equal or different. An encryption system in which both keys are equal is called a common key encryption system, and DES (Data Encryption Standards) adopted by the US Bureau of Standards is a typical example. Also, as an example of an encryption system in which both keys are different, an encryption system called a public key encryption system has been proposed. In this public key cryptosystem, each user (entity) using the cryptosystem creates a pair of an encryption key and a decryption key, publishes the encryption key in a public key list, and keeps only the decryption key secret. It is a cryptographic system that does. In the public key cryptosystem, the pair of the encryption key and the decryption key are different from each other, and have a feature that the decryption key cannot be determined from the encryption key by using the one-way function.
[0005]
The public key cryptosystem is an epoch-making cryptosystem that publishes an encryption key, and conforms to the above three elements necessary for establishing an advanced information society. The research has been actively conducted in order to use the RSA cryptosystem, and the RSA cryptosystem has been proposed as a typical public key cryptosystem. This RSA encryption system is realized by utilizing the difficulty of factorization as a one-way function. In addition, various methods have been proposed for a public key cryptosystem utilizing the difficulty of solving the discrete logarithm problem (discrete logarithm problem).
[0006]
In addition, an encryption system using ID (Identity) information for specifying an individual such as an address and a name of each entity has been proposed. In this encryption system, a common encryption key is generated between the transmitting and receiving parties based on the ID information. The encryption technique based on the ID information includes (1) a method that requires preliminary communication between the transmitter and the receiver before ciphertext communication, and (2) a method that requires a preliminary communication between the transmitter and receiver before the ciphertext communication. Some systems do not require communication. In particular, since the method (2) does not require preliminary communication, the convenience of the entity is high, and it is considered that the method will be the center of the future cryptosystem.
[0007]
The encryption system according to the method (2) is called an ID-NIKS (ID-based non-interactive key sharing scheme), and shares an encryption key without performing preliminary communication using ID information of a communication partner. It adopts the method of doing. The ID-NIKS is a method that does not require the exchange of a public key and a secret key between a sender and a receiver, and does not require a key list and a service by a third party, and can perform secure communication between arbitrary entities.
[0008]
FIG. 5 is a diagram showing the principle of the ID-NIKS system. Assuming the existence of a reliable center, the common key generation system is configured around this center. In FIG. 5, ID information such as the name, address, and telephone number of entity A, which is the specific information of entity X, is represented by h (ID) using a hash function h (·)._A). The center sends the center public information @ PC to any entity A._i｝ 、 Center secret information ｛SC_iＩＤ and the ID information h of the entity A (ID_A) Based on the secret information S_XiAnd secretly distribute it to entity A.
S_Xi= F_i(｛SC_i｛, ｛PC_i｝, H (ID_A))
[0009]
The entity A exchanges a common key K for encryption and decryption with any other entity B._ABIs the secret information of the entity A itself ｛S_Aiセ ン タ Center public information ｛PC_i｝ And the ID information h (ID_B) Is generated as follows.
K_AB= F (｛S_Ai｛, ｛PC_i｝, H (ID_B))
Similarly, the entity B also exchanges the key to the entity A with the common key K_BAGenerate If always K_AB= K_BAHolds, this key K_AB, K_BACan be used as an encryption key and a decryption key between the entities A and B.
[0010]
In the public key cryptosystem described above, for example, in the case of the RSA cryptosystem, the length of the public key is ten and several times the current telephone number, which is extremely complicated. On the other hand, in the ID-NIKS, if each ID information is registered in the form of a list, a common key can be generated with an arbitrary entity by referring to the list. Therefore, if the ID-NIKS system as shown in FIG. 5 is safely realized, a convenient encryption system can be constructed on a computer network to which many entities subscribe. For these reasons, ID-NIKS is expected to become the center of future cryptosystems.
[0011]
[Problems to be solved by the invention]
An ID-NIKS that shares a common key serving as an encryption key and a decryption key without performing preliminary communication using the ID information of a communication partner is sufficiently resistant to attacks such as collusion of multiple entities. It is desired to be safe. On the other hand, in order to be able to perform cryptographic communication over a wide range, it is desirable that the principle of encryption in ID-NIKS is as simple as possible. Such security and simplification are conflicting issues, and it is important for an advanced information society to be able to construct an ID-NIKS that is structurally simple and cryptographically secure. This is a problem, and the search for a more ideal encryption method that can solve both problems is being pursued.
[0012]
The present invention has been made in view of the above circumstances, and has a simple configuration and a highly secure ID-NIKS for generating a secret key.vessel,An object is to provide an encryption device, an encryption communication method, an encryption communication system, and a recording medium.
[0013]
[Means for Solving the Problems]
2. The secret key generator according to claim 1, wherein the secret key generator generates the secret key unique to the entity using the specific information of the entity and a secret symmetric matrix. Public key vector v_X(X₁, X_Two) And the obtained public key vector v_XAnd means for obtaining a secret key as shown in the following (B) modulo N = PQ (P and Q are prime numbers) using the secret symmetric matrix H shown in the following (A). Features.
[0014]
(Equation 16)

[0015]
Where g is the largest generator modulo N
t: integer of 2 or more
[0016]
3. A secret key generator according to claim 2, wherein the secret key generator generates the secret key unique to the entity using the specific information of the entity and a secret symmetric matrix. Public key vector v_X(X₁, X_Two) And the obtained public key vector v_XAnd a secret symmetric matrix H shown in the following (C), a secret key G as shown in the following (D) modulo N = PQ (P and Q are prime numbers)₁, G_Two, G_ThreeAnd means for determining
[0017]
[Equation 17]

[0018]
Where g is the largest generator modulo N
m: Integer of 2 or more
[0019]
4. A secret key generator according to claim 3, wherein the secret key generator generates the secret key unique to the entity using the specific information of the entity and a secret symmetric matrix. Public key vector v_X(X₁, X_Two, ..., x_N) And the obtained public key vector v_XAnd a secret symmetric matrix H shown in the following (E), N ′ = PQr₁r_Two... r_S(P, Q, r₁~ R_SIs a prime number modulo a secret key G as shown in (F) and (G) below.₁, G_Two, ..., G_{t + 1}And H_Two, ..., H_i, ..., H_NAnd means for determining
[0020]
(Equation 18)

[0021]
Where g: the maximum generator modulo N '
S, t: integer of 2 or more
[0022]
The encryption device according to claim 4 is based on the specific information of each entity and the secret key unique to each entity generated using the secret symmetric matrix and the specific information of the other entity to which the ciphertext is transmitted. A means for obtaining a secret key of an entity X generated by a secret key generator according to claim 1, wherein the encryption device encrypts a plaintext into a ciphertext using a common key generated by the generated public key. The public key vector v of the entity Y based on the acquired secret key and the specific information of the partner entity Y_y(Y₁, Y_Two) To obtain a common key K as shown in (H) below._XYAnd means for determining
[0023]
[Equation 19]

[0024]
The encryption device according to claim 5, based on the specific information of each entity and the secret key unique to each entity generated using the secret symmetric matrix and the specific information of the other entity to which the ciphertext is to be transmitted. A means for acquiring a secret key of an entity X generated by a secret key generator according to claim 2, wherein the encryption device encrypts a plaintext into a ciphertext using a common key generated by the generated public key. The public key vector v of the entity Y based on the acquired secret key and the specific information of the partner entity Y_y(Y₁, Y_Two) To obtain a common key K as shown in the following (I)._XYAnd means for determining
[0025]
(Equation 20)

[0026]
The encryption device according to claim 6, based on the specific information of each entity and the secret key unique to each entity generated using the secret symmetric matrix and the specific information of the other entity to which the ciphertext is to be transmitted. A means for acquiring a secret key of an entity X generated by a secret key generator according to claim 3, wherein the encryption device encrypts plaintext into ciphertext using a common key generated by the generated public key. A public key vector (y) based on the acquired secret key and the specific information of the other party entity Y_Two, Y_Three, ..., y_N), A means for obtaining an intermediate value J as shown in the following (J), and a public key vector (y₁) To obtain a common key K as shown in the following (K)._XYAnd means for determining
[0027]
(Equation 21)

[0028]
An encryption device according to claim 7, wherein the intermediate key for generating the common key using the secret key unique to each entity and the public key of the partner entity according to any one of claims 4 to 6. And means for storing the generated intermediate key on each entity side.
[0029]
According to an eighth aspect of the present invention, in the encryption device according to the seventh aspect, the generated intermediate key is stored in an IC card, and the common key is generated by the IC card using the stored intermediate key. It is characterized by.
[0030]
10. The cryptographic communication method according to claim 9, wherein the center device sends a private key unique to each entity to each entity device, and one entity device obtains a common key obtained from the private key unique to the entity sent from the center device. The plaintext is encrypted into ciphertext and transmitted to the other entity device by using the other entity device, and the transmitted ciphertext is obtained from the secret key unique to the entity sent from the center device. In a cryptographic communication method in which information is communicated between entity devices by decrypting the original plaintext using the same common key as the common key, the public key vector v of the entity X based on the specific information of the entity X_X(X₁, X_Two) And the obtained public key vector v_XAnd a secret symmetric matrix H shown in the following (L) to obtain a secret key as shown in the following (M) modulo N = PQ (P and Q are prime numbers); Sending the key to the entity device.
[0031]
(Equation 22)

[0032]
Where g is the largest generator modulo N
t: integer of 2 or more
[0033]
11. The cryptographic communication method according to claim 10, wherein a secret key unique to each entity is sent from the center device to each entity device, and one of the entity devices is obtained from the secret key unique to the entity sent from the center device. The plaintext is encrypted into ciphertext and transmitted to the other entity device by using the other entity device, and the transmitted ciphertext is obtained from the secret key unique to the entity sent from the center device. In a cryptographic communication method in which information is communicated between entity devices by decrypting the original plaintext using the same common key as the common key, the public key vector v of the entity X based on the specific information of the entity X_X(X₁, X_Two) And the obtained public key vector v_XAnd a secret symmetric matrix H shown in the following (N), a secret key G shown in the following (O) modulo N = PQ (P and Q are prime numbers)₁, G_Two, G_ThreeAnd sending the obtained secret key to the entity device.
[0034]
(Equation 23)

[0035]
Where g is the largest generator modulo N
m: Integer of 2 or more
[0036]
The cryptographic communication method according to claim 11, wherein a secret key unique to each entity is sent from the center device to each entity device, and a common key obtained from one entity device from the secret key unique to the entity sent from the center device. The plaintext is encrypted into ciphertext and transmitted to the other entity device by using the other entity device, and the transmitted ciphertext is obtained from the secret key unique to the entity sent from the center device. In a cryptographic communication method for communicating information between entity devices by decrypting the original plaintext using the same common key as the common key, an N-dimensional public key vector of the entity X based on the specific information of the entity X v_X(X₁, X_Two, ..., x_N) And the obtained public key vector v_XAnd N ′ = PQr using the secret symmetric matrix H shown in the following (P).₁r_Two... r_S(P, Q, r₁~ R_SIs a prime number) and a secret key G as shown in (Q) and (R) below.₁, G_Two, ..., G_{t + 1}And H_Two, ..., H_i, ..., H_NAnd sending the obtained secret key to the entity device.
[0037]
[Equation 24]

[0038]
Where g: the maximum generator modulo N '
S, t: integer of 2 or more
[0039]
According to a twelfth aspect of the present invention, in the cryptographic communication method according to any one of the ninth to eleventh aspects, an intermediate key for generating the common key is generated, and the generated intermediate key is stored in each entity device. Features.
[0040]
The cryptographic communication method according to claim 13 is characterized in that, in claim 12, the generated intermediate key is stored in an IC card, and the common key is generated by the IC card using the stored intermediate key. I do.
[0041]
15. The encryption communication system according to claim 14, wherein a plurality of entity devices perform an encryption process of encrypting a plaintext, which is information to be transmitted, into a ciphertext, and a decryption process of decoding the transmitted ciphertext into the original plaintext. A center device having a secret key generator according to claim 1 and means for sending the generated secret key to each entity, and a secret key of the entity X from the center device. Acquiring means, and an N-dimensional public key vector v of the entity Y based on the acquired secret key and the specific information of the partner entity Y_y(Y₁, Y_Two) To obtain a common key K used for the encryption and decryption as shown in (S) below._XYAnd a plurality of entity devices having means for determining
[0042]
(Equation 25)

[0043]
The encryption communication system according to claim 15, wherein a plurality of entity devices perform an encryption process of encrypting a plaintext, which is information to be transmitted, into a ciphertext, and a decryption process of decoding the transmitted ciphertext into the original plaintext. A center device having a secret key generator according to claim 2 and means for sending the generated secret key to each entity, and a secret key of the entity X from the center device. Acquiring means, and an N-dimensional public key vector v of the entity Y based on the acquired secret key and the specific information of the partner entity Y_y(Y₁, Y_Two) To obtain a common key K used for the encryption and decryption as shown in (T) below._XYAnd a plurality of entity devices having means for determining
[0044]
(Equation 26)

[0045]
17. The encryption communication system according to claim 16, wherein a plurality of entity devices perform an encryption process of encrypting a plaintext, which is information to be transmitted, into a ciphertext and a decryption process of decoding the transmitted ciphertext into the original plaintext. And a center device having a secret key generator according to claim 3 and means for sending the generated secret key to each entity, and a secret key of the entity X from the center device. Means for obtaining, and an N-1 dimensional public key vector (y_Two, Y_Three, ..., y_N), A means for obtaining an intermediate value J as shown in the following (U), and a one-dimensional public key vector (y₁) To obtain a common key K as shown in the following (V)._XYAnd a plurality of entity devices having means for determining
[0046]
[Equation 27]

[0047]
The recording medium according to claim 17 isA computer for causing the computer to function as the secret key generator according to claim 1.A computer program is recorded.
[0050]
The recording medium according to claim 18 isA computer for causing the computer to function as the secret key generator according to claim 2.A computer program is recorded.
[0053]
The recording medium according to claim 19 isA computer for functioning as a secret key generator according to claim 3.A computer program is recorded.
[0060]
BEST MODE FOR CARRYING OUT THE INVENTION
Hereinafter, embodiments of the present invention will be specifically described.
FIG. 1 is a schematic diagram showing the configuration of the cryptographic communication system of the present invention. A center 1 that can trust information concealment is set, and this center 1 can be, for example, a public organization of society. The center 1 is connected to a plurality of entities a, b,..., Z as users who use the cryptosystem by secret communication paths 2a, 2b,. The secret key information is transmitted from the center 1 to the entities a, b,..., Z via 2a, 2b,. Further, communication paths 3ab, 3az, 3bz,... Are provided between the two entities, and ciphertexts obtained by encrypting communication information via the communication paths 3ab, 3az, 3bz,. It is transmitted between them.
[0061]
First, the basic method of the present invention will be described.
(Preparation processing at center 1)
The center 1 prepares the following public key and secret key, and publishes the public key.
Public key N: N = PQ (P, Q: prime number of about 512 bits)
h: One-way hash function for generating public key vector
Secret key H: 2 × 2 symmetric matrix as shown in (1) below
g: maximum generator modulo N
[0062]
[Equation 31]

[0063]
Each of the specific information (ID information) of the entities X and Y is ID_X, ID_YAnd using the hash values thereof, the public key of each entity X, Y (vector v_X, V_Y) Is defined by the following (2) and (3). However, the hash value size is 1024 bits.
[0064]
(Equation 32)

[0065]
(Entity registration process)
The center 1 requested to register the entity X registers the secret symmetric matrix H shown in the above (1) and the public key (vector v) of the entity X shown in the above (2)._X), A secret key as shown in the following (4) modulo N = PQ is obtained, and the obtained secret key is secretly distributed to the entity X. Thus, in the present invention, a secret key having a size larger than the symmetric matrix H (a three-dimensional secret key based on the 2 × 2 matrix H) is generated. In other words, in the present invention, the size of the center secret is enlarged and sent to the entity X.
[0066]
[Equation 33]

[0067]
(Generation process of common key between entities)
The entity X performs a calculation using a binary theorem as shown in the following (5), thereby forming a common key K with the communication partner entity Y._XYAsk for. This common key K_XYIs the common key K obtained from the entity Y side_YXMatches.
[0068]
(Equation 34)

[0069]
It should be noted that the symmetric matrix H shown in the above (1) can be generalized to a matrix of M × M (M ≧ 3). In this case, the key sharing of the common key can be performed by using the M-term theorem. realizable. However, under the condition that the data amount of the secret key distributed from the center 1 is constant, increasing M works in the direction of weakening the security, so the case of M = 2 is optimal.
[0070]
Next, communication of information between entities in the above-described cryptographic system will be described. FIG. 2 is a schematic diagram showing a communication state of information between two entities X and Y. The example of FIG. 2 shows a case where the entity X encrypts a plaintext (message) M into a ciphertext C and transmits it to the entity Y, and the entity Y decrypts the ciphertext C into the original plaintext (message) M. Is shown.
[0071]
On the entity X side, the specific information ID of the entity Y_YAnd a public key (vector v_Y), The secret key (shown in (4) above) sent from the center 1 and the public key (vector v) from the public key generator 11._Y), The common key K with the entity Y required by the entity X based on_XYAnd a common key generator 12 for generating_XYAnd an encryptor 13 for encrypting a plaintext (message) M into a ciphertext C by using the ciphertext C and outputting the ciphertext C to the communication path 30.
[0072]
Also, on the entity Y side, the specific information ID of the entity X_XAnd a public key (vector v_X), A secret key (similar to the above (4)) sent from the center 1, and a public key (vector v) from the public key generator 21._X), The common key K with the entity X obtained by the entity Y based on_YXAnd a common key generator 22 for generating the_YXAnd a decryptor 23 for decrypting the ciphertext C input from the communication path 30 into a plaintext (message) M and outputting the same.
[0073]
Next, the operation will be described. When transmitting information from the entity X to the entity Y, first, the specific information ID of the entity Y_YIs input to the public key generator 11 and the public key (vector v_Y) Is obtained, and the obtained public key of the entity Y is sent to the common key generator 12. Also, the secret key shown in the above (4) is input from the center 1 to the common key generator 12. Then, according to the above (5), the common key K_XYIs sent to the encryptor 13. In the encryptor 13, this common key K_XYIs used to encrypt a plaintext (message) M into a ciphertext C, and the ciphertext C is transmitted via the communication path 30.
[0074]
The ciphertext C transmitted through the communication path 30 is input to the decryptor 23 of the entity Y. Specific information ID of entity X_XIs input to the public key generator 21 and the public key (vector v_X) Is obtained, and the obtained public key of the entity X is sent to the common key generator 22. Also, a secret key similar to the above (4) is input to the common key generator 22 from the center 1. Then, similarly to the above (5), the common key K_YXIs sent to the decoder 23. In the decryptor 23, this common key K_YXIs used to decrypt the ciphertext C into a plaintext (message) M.
[0075]
FIG. 3 is a diagram showing a configuration of an embodiment of the recording medium of the present invention. The program exemplified here includes a process of generating a secret key as shown in the above (4) using a secret symmetric matrix and a public key of each entity, or a process as shown in the above (4). It includes a process of generating a common key between the two entities according to the above (5) using its own private key and the public key of the partner entity, and is recorded on a recording medium described below. The computer 40 is provided on the center 1 side or on each entity side.
[0076]
In FIG. 3, a recording medium 41 that is connected online to the computer 40 is, for example, a WWW (World Wide Web) server computer that is installed separately from a place where the computer 40 is installed. 41a is recorded. The program 41a read from the recording medium 41 controls the computer 40 to generate a secret key unique to each entity or a common key between both entities.
[0077]
The recording medium 42 provided inside the computer 40 uses, for example, a hard disk drive or a ROM installed therein, and the recording medium 42 stores the program 42a as described above. By controlling the computer 40 by the program 42a read from the recording medium 42, a secret key unique to each entity is generated, or a common key between both entities is generated.
[0078]
The recording medium 43 used by being loaded into a disk drive 40a provided in the computer 40 is a transportable medium such as a magneto-optical disk, a CD-ROM, or a flexible disk. 43a is recorded. The program 43a read from the recording medium 43 controls the computer 40 to generate a secret key unique to each entity or a common key between both entities.
[0079]
Hereinafter, the safety of the present invention will be considered. The following (theorem) holds for the number of colluders required to derive the secret key of any entity Z of the attack target.
(Theorem) The secret key of an arbitrary entity Z can be derived by collusion of (t + 1) persons.
[0080]
(Method of Depending Security on Computation Disparity of the Present Invention: First Method)
(1) Method using the basic method as it is
As described in the above (theorem), the secret key is exposed in the basic scheme by the collusion of (t + 1) persons. However, since the Carmichael function is unknown, y₁ ^tiy_Two ⁱBecomes very large. For example, y₁Is 1024 bits and t = 1000, y₁ ^tiy_Two ⁱReaches approximately 310,000 decimal digits. Deriving the secret key of an arbitrary entity Z requires an operation related to a 1000 × 1000 matrix whose element size is 310,000 decimal digits, and further requires 1000 colluders. In consideration of this fact, it can be said that this basic method can sufficiently be put to practical use if the operation is limited to a relatively narrow range, such as in a research laboratory, a business establishment, or a school.
[0081]
(2) Method using a dedicated IC card
Here, a method on the assumption that a common key is generated using a high-performance dedicated IC card, in other words, a method for increasing the amount of calculation required for an attack will be described. FIG. 4 is a configuration diagram of the IC card 50. The IC card 50 includes a public key generation unit 51 that generates a public key using a hash function, a pre-key generation unit 52 that performs a modular exponentiation operation and a product-sum operation to generate a pre-key (intermediate key) described later. , A memory unit 53 for storing the generated pre-key, and a common key generation unit 54 for generating the common key.
[0082]
In the method using the dedicated IC card, the following conditions are set.
(A) The key renewal period is about one month.
(B) A pre-key as a pre-stage of the common key is generated during a period of about one month, spending about 10 minutes to 1 hour.
(C) A single IC card stores several hundred pre-keys of a common key for a partner entity that frequently communicates.
[0083]
In this method, the purpose of making the IC card generate a pre-key using a relatively long time during the update period is to create a difference in the amount of calculation with the attacker, so that the value of t is the minimum value. 2 can be set. Therefore, the center 1 distributes the following three types of secret keys to the entity X as shown in (6) below. Here, m is a large positive integer. It is easy for the center 1 that knows the Carmichael function to calculate these secret keys.
[0084]
(Equation 35)

[0085]
Common key K with entity Y_XYIs the hash value (y₁, Y_Two) Is generated as shown in the following (7).
[0086]
[Equation 36]

[0087]
Where y₁ ^m, Y_Two ^mSince they cannot be modulo by the Carmichael function and must be calculated on an integer ring, the number becomes very large for an attacker, which causes a great difference in the amount of calculation.
[0088]
Pre-key K corresponding to (7) above_XY'Is defined as in the following (8).
[0089]
(37)

[0090]
For example, m ≒ 10⁶, J, K, L, M ≒ 10^Four, And J, K, L, and M are kept secret. The pre-key for the general value of t is defined exactly the same. A pre-key is required to reduce the time required to generate a common key with a partner entity that frequently communicates, that is, to reduce the processing load when sharing a common key. Is approximately 3 kbits for each communication partner when the size | N | of N is 1024 bits. As in the example described above, generally, J, K, L, M≪m are set, so that the pre-key K_XY'To the common key K_XYCan be devised so as to reduce the time required to generate the. On the other hand, for the attacker, the number of combinations of J, K, L, and M is also 10 in this example.¹⁶It is impossible to identify the combination. Generally, it is easier to set the number of combinations to a very large number as t increases.
[0091]
A legitimate entity that stores the pre-key and knows the combination of J, K, L, and M is the pre-key K shown in (8) above._XY', And only by performing (J + K + L + M) power operations, the common key K shown in the above (7) is obtained._XYCan be calculated. On the other hand, in the attacker, the common key K_XYRequires a power operation as many as 4 m times.
[0092]
The time required for each entity to generate a pre-key and the attacker calculates the hash value x₁ ^m, Y₁ ^mIs compared with the amount of calculation required when obtaining the values. Assume the following conditions:
(A) The calculation amount required for multiplying two n-digit numbers is n^TwoAnd
(B) The entity is given 10 minutes to generate one pre-key, for example during a one-month key renewal period.
[0093]
(G^A)^BThe amount of computation required for a modulo operation of the form mod N is g^AAnd B size | g^A|, | B |, then | g^A| × | g^A| × | B |. | G^A|, | B | are 1024 bits, and this modulo operation (g^A)^BAssuming that mod N is executed ten times in one millisecond, the amount of calculation for pre-key generation is 1024 × 1024 × 10000 × 600. In this case, m = 6 × 10⁶It is. On the other hand, since the amount of calculation required for the attacker is n = 1024 × 10000 × 600, (1024 × 10000 × 600)^TwoIt becomes. m = 6 × 10^Five, About 5.86 × 10 of legitimate entities for the attacker^FiveIt requires twice as much computation time, ie, 40.7 days, and there is a large disparity in computation between legitimate entities and attackers. If 100 minutes were allowed for pre-key generation, this disparity would be increased by a factor of 10 and would require an attacker 407 days of computation time.
[0094]
Here, the calculation conditions are changed, and the following assumption is made.
(A) The amount of computation required to multiply two n-digit numbers is n^TwoNot shown in (9) below.
[0095]
[Equation 38]

[0096]
(B) 100 minutes are given for pre-key generation, and legal operation A^Bmod N is 10^ThreeSuppose the speed is doubled.
[0097]
The amount of computation required by the attacker for the above multiplication is 137 days for 100 minutes of a valid entity. In this case, y₁ ^mAre about 18.5 trillion decimal digits. This attack is impractical given the amount of memory required. Here, it is easy to increase the pre-key generation time by one or two digits, and to speed up the legal operation by one or two digits. Therefore, the first method can ensure security.
[0098]
(Method of Depending Security on Stochastic Structure of the Present Invention: Second Method)
The 2 × 2 center secret symmetric matrix H given in the above (1) is given as an N × N symmetric matrix H as shown in the following (10). However, the modulus N 'is (11) below.
[0099]
[Equation 39]

[0100]
r₁~ R_SIs a 16-bit prime number, and a set of these prime numbers is S_r= ｛R_iNotated as｝. Element h of symmetric matrix H_ijIs a random number of prime numbers r_i∈S_rShall be divided by
[0101]
On the other hand, a hash value for an arbitrary entity X is given as in the following (12). Component x in the following (12)_iIs a prime number r_i∈S_rAnd a random product of
[0102]
(Equation 40)

[0103]
The center 1 receives N ′ = PQr for the entity X₁r_Two... r_SThe secret key shown in (13) below is sent secretly under the law. At the same time, the secret key shown in (14) below is also sent secretly.
[0104]
[Equation 41]

[0105]
The common key for entity Y is generated in entity X as follows. First, the secret key of the above (14) and the hash value (y₁), The intermediate value J is obtained as shown in the following (15), and the obtained intermediate value J, the secret key of the above (13), and the hash value (y₁) And the common key K with the entity Y_XYIs calculated according to the following (16).
[0106]
(Equation 42)

[0107]
As a specific example, when each parameter is set to N = 16, t = 16, and S = 64, the common key K_XYThe number of terms when expanding the exponent of is₁₆H₁₆=₃₁C₁₆= 300540195. Even if the total number of entities is about one million, the total number of equations distributed from the center 1 (about 32 million) exceeds the number by about one digit, and the common key K_XYIt is difficult to derive a center secret symmetric matrix from the form In addition, when solving equations distributed to each entity simultaneously, the modulus of each equation is not constant but a random value, and a part of the center secret symmetric matrix is in the exponent part. Therefore, it is difficult to expose the center secret.
[0108]
In this example, the data distribution amount from the center 1 to each entity is 32 bits as shown in (17) below.
t + 1 + N-1 = t + N = 32 (17)
On the other hand, when | PQ | = 1024 bits, N ′ = 1024 + t × S = 2048 bits. Therefore, the total amount of data distributed to each entity is 65.5 kbits (8.19 kbytes). In this case, the common key generation time is given by a time that is about 16 times the decryption time of the 2048-bit RSA encryption.
[0109]
As described above, in the second method, a part of the secret key distributed from the center 1 is placed in the exponent part, and the remaining part (an equation on the integer ring) has a stochastic structure. Since the common factors between these equations and the modulus N 'are given at random and some of the secret keys are in the exponent part, attacks such as taking the ratio between the reduced common keys are excluded, Attack is difficult.
[0110]
【The invention's effect】
As described above in detail, according to the present invention, the secret key generation in ID-NIKS which has a simple configuration principle and secures securityvessel,An encryption device, an encryption communication method, an encryption communication system, and a recording medium can be provided, which can contribute to the construction of an ideal ID-NIKS. Further, since the pre-key (intermediate key) is obtained in advance, the processing load at the time of key sharing can be reduced.
[Brief description of the drawings]
FIG. 1 is a schematic diagram showing a configuration of a cryptographic communication system of the present invention.
FIG. 2 is a schematic diagram showing a communication state of information between two entities.
FIG. 3 is a diagram showing a configuration of an embodiment of a recording medium.
FIG. 4 is a configuration diagram of an IC card.
FIG. 5 is a diagram illustrating the principle configuration of an ID-NIKS system.
[Explanation of symbols]
1 center
11,21 public key generator
12,22 common key generator
13 Encryptor
23 Decoder
30 communication channels
40 Computer
41, 42, 43 recording medium
50 IC card

Claims (19)

A secret key generator for generating a secret key unique to the entity using the specific information of the entity and a secret symmetric matrix, wherein a public key vector v _X (x ₁ , x ₂ ), using the obtained public key vector v _X and the secret symmetric matrix H shown in (A) below, modulo N = PQ (P and Q are prime numbers) ) Means for obtaining a secret key as described in (1).

Where g: the maximum generator modulo N t: an integer of 2 or more A secret key generator for generating a secret key unique to the entity using the specific information of the entity and a secret symmetric matrix, wherein a public key vector v _X (x ₁ , x ₂ ), using the obtained public key vector v _X and a secret symmetric matrix H shown in the following (C), modulo N = PQ (P and Q are prime numbers) ), Means for obtaining the secret keys G ₁ , G ₂ , G ₃ .

Here, g: the maximum generator modulo N m: an integer of 2 or more A secret key generator for generating a secret key unique to the entity using the specific information of the entity and a secret symmetric matrix, wherein a public key vector v _X (x ₁ , x _2, ..., with means for obtaining x _N), and a symmetric matrix H secret indicated by the acquired public key vector v _X and the following (E), N '= PQr 1 r 2 ... r S (P , Q, r _{1 to} r _S are prime numbers) and secret keys G ₁ , G ₂ ,..., G _{t + 1} and H _{2 ,.} ..., a means for determining H _N.

Where g: the maximum generator S modulo N ', t: an integer of 2 or more A common key generated from a secret key unique to each entity generated using specific information of each entity and a secret symmetric matrix, and a public key generated based on specific information of the other entity to which the cipher text is transmitted And a means for obtaining a secret key of the entity X generated by the secret key generator according to claim 1; A means for obtaining a common key K _XY as shown in the following (H) using the public key vector v _y (y ₁ , y ₂ ) of the entity Y based on the specific information. .

A common key generated from a secret key unique to each entity generated using specific information of each entity and a secret symmetric matrix, and a public key generated based on specific information of the other entity to which the cipher text is transmitted And a means for obtaining the secret key of the entity X generated by the secret key generator according to claim 2; Means for obtaining a common key K _XY as shown in the following (I) using a public key vector v _y (y ₁ , y ₂ ) of the entity Y based on the specific information. .

A common key generated from a secret key unique to each entity generated using specific information of each entity and a secret symmetric matrix, and a public key generated based on specific information of the other entity to which the cipher text is transmitted And a means for acquiring the secret key of the entity X generated by the secret key generator according to claim 3; Means for obtaining an intermediate value J as shown in the following (J) using the public key vector (y ₂ , y ₃ ,..., Y _N ) based on the specific information, and the obtained secret key and the obtained intermediate value J And a means for obtaining a common key K _XY as shown in the following (K) using the public key vector (y ₁ ) based on the specific information of the entity Y.

Means for generating an intermediate key for generating the common key using the secret key unique to each entity and the public key of the other entity, and means for storing the generated intermediate key on each entity side The encryption device according to any one of claims 4 to 6, further comprising: The encryption device according to claim 7, wherein the generated intermediate key is stored in an IC card, and the common key is generated in the IC card using the stored intermediate key. The center device sends a secret key unique to each entity to each entity device, and one of the entity devices encrypts plaintext into ciphertext using a common key obtained from the secret key unique to the entity sent from the center device. And transmitting the ciphertext transmitted by the other entity device from the secret key unique to the entity sent from the center device, using the same common key as the common key. A step of obtaining a public key vector v _X (x ₁ , x ₂ ) of the entity X based on the specific information of the entity X in a cryptographic communication method for communicating information between entity devices by decrypting the original plain text When, by using the symmetric matrix H secret indicated by the acquired public key vector v _X and the following (L), N = PQ and (P, Q is a prime number) Cryptographic communication method characterized by comprising the steps of obtaining a secret key as shown below (M) which, a step of sending a private key determined to an entity device.

Where g: the maximum generator modulo N t: an integer of 2 or more The center device sends a secret key unique to each entity to each entity device, and one of the entity devices encrypts the plaintext into ciphertext using the common key obtained from the secret key unique to the entity sent from the center device. And transmitting the ciphertext transmitted by the other entity device from the secret key unique to the entity sent from the center device, using the same common key as the common key. A step of obtaining a public key vector v _X (x ₁ , x ₂ ) of the entity X based on the specific information of the entity X in a cryptographic communication method for communicating information between entity devices by decrypting the original plain text When, by using the symmetric matrix H secret indicated by the acquired public key vector v _X and the following (N), N = PQ and (P, Q is a prime number) Cryptographic communication method characterized by comprising the steps of obtaining a secret key G _1, G _2, G _3, as shown in the following (O) which, with the steps of sending a private key determined to an entity device.

Here, g: the maximum generator modulo N m: an integer of 2 or more The center device sends a secret key unique to each entity to each entity device, and one of the entity devices encrypts the plaintext into ciphertext using the common key obtained from the secret key unique to the entity sent from the center device. And transmitting the ciphertext transmitted by the other entity device from the secret key unique to the entity sent from the center device, using the same common key as the common key. In a cryptographic communication method for performing information communication between entity devices by decrypting the original plaintext, an N-dimensional public key vector v _X (x ₁ , x ₂ ,... using acquiring x _N), and a symmetric matrix H secret indicated by the acquired public key vector v _X and below (P), N '= P r ₁ r ₂ ... r _S and _{(P, Q, r 1 ~r} S is a prime number) the law following (Q) and a secret key, such as shown in _{(R) G 1, G 2} , ..., G t + 1 And H ₂ ,..., H _i ,..., H _N , and sending the obtained secret key to the entity device.

Where g: the maximum generator S modulo N ', t: an integer of 2 or more The cryptographic communication method according to claim 9, wherein an intermediate key for generating the common key is generated, and the generated intermediate key is stored in each entity device. 13. The encryption communication method according to claim 12, wherein the generated intermediate key is stored in an IC card, and the common key is generated by the IC card using the stored intermediate key. In a cryptographic communication system in which a plurality of entity devices mutually perform an encryption process of encrypting a plaintext that is information to be transmitted into a ciphertext, and a decryption process of decoding the transmitted ciphertext into the original plaintext, 2. A center device comprising: the secret key generator according to claim 1; and means for sending the generated secret key to each entity; and means for obtaining the secret key of the entity X from the center device; Using the N-dimensional public key vector v _y (y ₁ , y ₂ ) of the entity Y based on the specific information of the partner entity Y, a common key used in the encryption processing and the decryption processing as shown in the following (S) A cryptographic communication system comprising a plurality of entity devices having means for determining a key _KXY .

In a cryptographic communication system in which a plurality of entity devices mutually perform an encryption process of encrypting a plaintext that is information to be transmitted into a ciphertext, and a decryption process of decoding the transmitted ciphertext into the original plaintext, 3. A center device comprising: the secret key generator according to claim 2; and means for sending the generated secret key to each entity; and means for obtaining the secret key of the entity X from the center device. Using the N-dimensional public key vector v _y (y ₁ , y ₂ ) of the entity Y based on the specific information of the partner entity Y, a common key used in the encryption processing and the decryption processing as shown in the following (T) A cryptographic communication system comprising a plurality of entity devices having means for determining a key _KXY .

In a cryptographic communication system in which a plurality of entity devices mutually perform an encryption process of encrypting a plaintext that is information to be transmitted into a ciphertext, and a decryption process of decoding the transmitted ciphertext into the original plaintext, 4. A center device comprising: the secret key generator according to claim 3; and means for sending the generated secret key to each entity; and means for obtaining the secret key of the entity X from the center device; Means for obtaining an intermediate value J as shown in the following (U) using an N-1 dimensional public key vector (y ₂ , y ₃ ,..., Y _N ) based on the specific information of the partner entity Y; A means for obtaining a common key K _XY as shown in the following (V) using the obtained secret key, the obtained intermediate value J and the one-dimensional public key vector (y ₁ ) based on the specific information of the entity Y. Multiple entertainment Cryptographic communication system, characterized in that it comprises a tee device.

A recording medium on which a computer program for causing a computer to function as the secret key generator according to claim 1 is recorded. A recording medium on which a computer program for causing a computer to function as the secret key generator according to claim 2 is recorded. A recording medium on which a computer program for causing a computer to function as the secret key generator according to claim 3 is recorded.

Images