(57)【特許請求の範囲】
【請求項１】
エンティティの特定情報と秘密の対称行列とを用いて、前記エンティティ固有の秘密鍵を生成する秘密鍵生成器において、エンティティＸの特定情報に基づいてエンティティＸの公開鍵ベクトルｖX （ｘ1 ，ｘ2 ）を取得する手段と、取得した公開鍵ベクトルｖX と下記（Ａ）で示される秘密の対称行列Ｈとを用いて、Ｎ＝ＰＱ（Ｐ，Ｑは素数）を法とする下記（Ｂ）に示すような秘密鍵を求める手段とを備えることを特徴とする秘密鍵生成器。
【数１】
0003587746.tif 000026
但し、ｇ：Ｎを法とする最大生成元
ｔ：２以上の整数
【請求項２】
エンティティの特定情報と秘密の対称行列とを用いて、前記エンティティ固有の秘密鍵を生成する秘密鍵生成器において、エンティティＸの特定情報に基づいてエンティティＸの公開鍵ベクトルｖX （ｘ1 ，ｘ2 ）を取得する手段と、取得した公開鍵ベクトルｖX と下記（Ｃ）で示される秘密の対称行列Ｈとを用いて、Ｎ＝ＰＱ（Ｐ，Ｑは素数）を法とする下記（Ｄ）に示すような秘密鍵Ｇ1 ，Ｇ2 ，Ｇ3 を求める手段とを備えることを特徴とする秘密鍵生成器。
【数２】
0003587746.tif 000027
但し、ｇ：Ｎを法とする最大生成元
ｍ：２以上の整数
【請求項３】
エンティティの特定情報と秘密の対称行列とを用いて、前記エンティティ固有の秘密鍵を生成する秘密鍵生成器において、エンティティＸの特定情報に基づいてエンティティＸの公開鍵ベクトルｖX （ｘ1 ，ｘ2 ，…，ｘN ）を取得する手段と、取得した公開鍵ベクトルｖX と下記（Ｅ）で示される秘密の対称行列Ｈとを用いて、Ｎ′＝ＰＱｒ1 ｒ2 …ｒS （Ｐ，Ｑ，ｒ1 〜ｒS は素数）を法とする下記（Ｆ）及び（Ｇ）に示すような秘密鍵Ｇ1 ，Ｇ2 ，…，Ｇt+1 及びＨ2 ，…，Ｈi ，…，ＨN を求める手段とを備えることを特徴とする秘密鍵生成器。
【数３】
0003587746.tif 000028
但し、ｇ：Ｎ′を法とする最大生成元
Ｓ，ｔ：２以上の整数
【請求項４】
各エンティティの特定情報と秘密の対称行列とを用いて生成した各エンティティ固有の秘密鍵と、暗号文の送信先である相手のエンティティの特定情報に基づいて生成した公開鍵とにより生成した共通鍵を用いて平文を暗号文に暗号化する暗号化装置において、請求項１記載の秘密鍵生成器により生成されたエンティティＸの秘密鍵を取得する手段と、取得した秘密鍵と相手のエンティティＹの特定情報に基づくエンティティＹの公開鍵ベクトルｖy （ｙ1 ，ｙ2 ）とを用いて、下記（Ｈ）に示すような共通鍵ＫXYを求める手段とを備えることを特徴とする暗号化装置。
【数４】
0003587746.tif 000029
【請求項５】
各エンティティの特定情報と秘密の対称行列とを用いて生成した各エンティティ固有の秘密鍵と、暗号文の送信先である相手のエンティティの特定情報に基づいて生成した公開鍵とにより生成した共通鍵を用いて平文を暗号文に暗号化する暗号化装置において、請求項２記載の秘密鍵生成器により生成されたエンティティＸの秘密鍵を取得する手段と、取得した秘密鍵と相手のエンティティＹの特定情報に基づくエンティティＹの公開鍵ベクトルｖy （ｙ1 ，ｙ2 ）とを用いて、下記（Ｉ）に示すような共通鍵ＫXYを求める手段とを備えることを特徴とする暗号化装置。
【数５】
0003587746.tif 000030
【請求項６】
各エンティティの特定情報と秘密の対称行列とを用いて生成した各エンティティ固有の秘密鍵と、暗号文の送信先である相手のエンティティの特定情報に基づいて生成した公開鍵とにより生成した共通鍵を用いて平文を暗号文に暗号化する暗号化装置において、請求項３記載の秘密鍵生成器により生成されたエンティティＸの秘密鍵を取得する手段と、取得した秘密鍵と相手のエンティティＹの特定情報に基づく公開鍵ベクトル（ｙ2 ，ｙ3 ，…，ｙN ）とを用いて、下記（Ｊ）に示すような中間値Ｊを求める手段と、取得した秘密鍵と求めた中間値ＪとエンティティＹの特定情報に基づく公開鍵ベクトル（ｙ1 ）とを用いて、下記（Ｋ）に示すような共通鍵ＫXYを求める手段とを備えることを特徴とする暗号化装置。
【数６】
0003587746.tif 000031
【請求項７】
各エンティティ固有の前記秘密鍵と相手のエンティティの前記公開鍵とを用いて、前記共通鍵を生成するための中間鍵を生成する手段と、生成した中間鍵を各エンティティ側で記憶しておく手段とを備える請求項４〜６の何れかに記載の暗号化装置。
【請求項８】
生成した中間鍵をＩＣカードに記憶しておき、記憶した中間鍵を用いて前記ＩＣカードにて前記共通鍵を生成するようにした請求項７記載の暗号化装置。
【請求項９】
センタ装置から各エンティティ装置へ各エンティティ固有の秘密鍵を送付し、一方のエンティティ装置が前記センタ装置から送付された該エンティティ固有の秘密鍵から求めた共通鍵を用いて平文を暗号文に暗号化して他方のエンティティ装置へ伝送し、該他方のエンティティ装置が伝送された暗号文を、前記センタ装置から送付された該エンティティ固有の秘密鍵から求めた、前記共通鍵と同一の共通鍵を用いて元の平文に復号することにより、エンティティ装置間で情報の通信を行う暗号通信方法において、エンティティＸの特定情報に基づいてエンティティＸの公開鍵ベクトルｖX （ｘ1 ，ｘ2 ）を取得するステップと、取得した公開鍵ベクトルｖX と下記（Ｌ）で示される秘密の対称行列Ｈとを用いて、Ｎ＝ＰＱ（Ｐ，Ｑは素数）を法とする下記（Ｍ）に示すような秘密鍵を求めるステップと、求めた秘密鍵をエンティティ装置へ送付するステップとを有することを特徴とする暗号通信方法。
【数７】
0003587746.tif 000032
但し、ｇ：Ｎを法とする最大生成元
ｔ：２以上の整数
【請求項１０】
センタ装置から各エンティティ装置へ各エンティティ固有の秘密鍵を送付し、一方のエンティティ装置が前記センタ装置から送付された該エンティティ固有の秘密鍵から求めた共通鍵を用いて平文を暗号文に暗号化して他方のエンティティ装置へ伝送し、該他方のエンティティ装置が伝送された暗号文を、前記センタ装置から送付された該エンティティ固有の秘密鍵から求めた、前記共通鍵と同一の共通鍵を用いて元の平文に復号することにより、エンティティ装置間で情報の通信を行う暗号通信方法において、エンティティＸの特定情報に基づいてエンティティＸの公開鍵ベクトルｖX （ｘ1 ，ｘ2 ）を取得するステップと、取得した公開鍵ベクトルｖX と下記（Ｎ）で示される秘密の対称行列Ｈとを用いて、Ｎ＝ＰＱ（Ｐ，Ｑは素数）を法とする下記（Ｏ）に示すような秘密鍵Ｇ1 ，Ｇ2 ，Ｇ3 を求めるステップと、求めた秘密鍵をエンティティ装置へ送付するステップとを有することを特徴とする暗号通信方法。
【数８】
0003587746.tif 000033
但し、ｇ：Ｎを法とする最大生成元
ｍ：２以上の整数
【請求項１１】
センタ装置から各エンティティ装置へ各エンティティ固有の秘密鍵を送付し、一方のエンティティ装置が前記センタ装置から送付された該エンティティ固有の秘密鍵から求めた共通鍵を用いて平文を暗号文に暗号化して他方のエンティティ装置へ伝送し、該他方のエンティティ装置が伝送された暗号文を、前記センタ装置から送付された該エンティティ固有の秘密鍵から求めた、前記共通鍵と同一の共通鍵を用いて元の平文に復号することにより、エンティティ装置間で情報の通信を行う暗号通信方法において、エンティティＸの特定情報に基づいてエンティティＸのＮ次元の公開鍵ベクトルｖX （ｘ1 ，ｘ2 ，…，ｘN ）を取得するステップと、取得した公開鍵ベクトルｖX と下記（Ｐ）で示される秘密の対称行列Ｈとを用いて、Ｎ′＝ＰＱｒ1 ｒ2 …ｒS （Ｐ，Ｑ，ｒ1 〜ｒS は素数）を法とする下記（Ｑ）及び（Ｒ）に示すような秘密鍵Ｇ1 ，Ｇ2 ，…，Ｇt+1 及びＨ2 ，…，Ｈi ，…，ＨN を求めるステップと、求めた秘密鍵をエンティティ装置へ送付するステップとを有することを特徴とする暗号通信方法。
【数９】
0003587746.tif 000034
但し、ｇ：Ｎ′を法とする最大生成元
Ｓ，ｔ：２以上の整数
【請求項１２】
前記共通鍵を生成するための中間鍵を生成し、生成した中間鍵を各エンティティ装置側で記憶しておく請求項９〜１１の何れかに記載の暗号通信方法。
【請求項１３】
生成した中間鍵をＩＣカードに記憶しておき、記憶した中間鍵を用いて前記ＩＣカードにて前記共通鍵を生成する請求項１２記載の暗号通信方法。
【請求項１４】
送信すべき情報である平文を暗号文に暗号化する暗号化処理、及び、送信された暗号文を元の平文に復号する復号処理を、複数のエンティティ装置間で相互に行う暗号通信システムにおいて、請求項１記載の秘密鍵生成器と、生成した秘密鍵を各エンティティへ送付する手段とを有するセンタ装置、及び、エンティティＸの秘密鍵を前記センタ装置から取得する手段と、取得した秘密鍵と相手のエンティティＹの特定情報に基づくエンティティＹのＮ次元の公開鍵ベクトルｖy （ｙ1 ，ｙ2 ）とを用いて、下記（Ｓ）に示すような前記暗号化処理及び復号処理に用いる共通鍵ＫXYを求める手段とを有する複数のエンティティ装置を備えることを特徴とする暗号通信システム。
【数１０】
0003587746.tif 000035
【請求項１５】
送信すべき情報である平文を暗号文に暗号化する暗号化処理、及び、送信された暗号文を元の平文に復号する復号処理を、複数のエンティティ装置間で相互に行う暗号通信システムにおいて、請求項２記載の秘密鍵生成器と、生成した秘密鍵を各エンティティへ送付する手段とを有するセンタ装置、及び、エンティティＸの秘密鍵を前記センタ装置から取得する手段と、取得した秘密鍵と相手のエンティティＹの特定情報に基づくエンティティＹのＮ次元の公開鍵ベクトルｖy （ｙ1 ，ｙ2 ）とを用いて、下記（Ｔ）に示すような前記暗号化処理及び復号処理に用いる共通鍵ＫXYを求める手段とを有する複数のエンティティ装置を備えることを特徴とする暗号通信システム。
【数１１】
0003587746.tif 000036
【請求項１６】
送信すべき情報である平文を暗号文に暗号化する暗号化処理、及び、送信された暗号文を元の平文に復号する復号処理を、複数のエンティティ装置間で相互に行う暗号通信システムにおいて、請求項３記載の秘密鍵生成器と、生成した秘密鍵を各エンティティへ送付する手段とを有するセンタ装置、及び、エンティティＸの秘密鍵を前記センタ装置から取得する手段と、取得した秘密鍵と相手のエンティティＹの特定情報に基づくＮ−１次元の公開鍵ベクトル（ｙ2 ，ｙ3 ，…，ｙN ）とを用いて、下記（Ｕ）に示すような中間値Ｊを求める手段と、取得した秘密鍵と求めた中間値ＪとエンティティＹの特定情報に基づく１次元の公開鍵ベクトル（ｙ1 ）とを用いて、下記（Ｖ）に示すような共通鍵ＫXYを求める手段とを有する複数のエンティティ装置を備えることを特徴とする暗号通信システム。
【数１２】
0003587746.tif 000037
【請求項１７】
コンピュータを請求項１記載の秘密鍵生成器として機能させるためのコンピュータプログラムを記録してあることを特徴とする記録媒体。
【請求項１８】
コンピュータを請求項２記載の秘密鍵生成器として機能させるためのコンピュータプログラムを記録してあることを特徴とする記録媒体。
【請求項１９】
コンピュータを請求項３記載の秘密鍵生成器として機能させるためのコンピュータプログラムを記録してあることを特徴とする記録媒体。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、エンティティ固有の秘密鍵を生成する秘密鍵生成器、情報の内容が当事者以外にはわからないように情報を暗号化する暗号化装置、暗号文にて通信を行う暗号通信方法及び暗号通信システム、並びに、秘密鍵生成のためのコンピュータプログラムを記録した記録媒体に関する。
【０００２】
【従来の技術】
高度情報化社会と呼ばれる現代社会では、コンピュータネットワークを基盤として、ビジネス上の重要な文書・画像情報が電子的な情報という形で伝送通信されて処理される。このような電子情報は、容易に複写が可能である、複写物とオリジナルとの区別が困難であるという性質があり、情報保全の問題が重要視されている。特に、「コンピュータリソースの共有」，「マルチアクセス」，「広域化」の各要素を満たすコンピュータネットワークの実現が高度情報化社会の確立に不可欠であるが、これは当事者間の情報保全の問題とは矛盾する要素を含んでいる。このような矛盾を解消するための有効な手法として、人類の過去の歴史上主として軍事，外交面で用いられてきた暗号技術が注目されている。
【０００３】
暗号とは、情報の意味が当事者以外には理解できないように情報を交換することである。暗号において、誰でも理解できる元の文（平文）を第三者には意味がわからない文（暗号文）に変換することが暗号化であり、また、暗号文を平文に戻すことが復号であり、この暗号化と復号との全過程をまとめて暗号系と呼ぶ。暗号化の過程及び復号の過程には、それぞれ暗号化鍵及び復号鍵と呼ばれる秘密の情報が用いられる。復号時には秘密の復号鍵が必要であるので、この復号鍵を知っている者のみが暗号文を復号でき、暗号化によって情報の秘密性が維持され得る。
【０００４】
暗号化鍵と復号鍵とは、等しくても良いし、異なっていても良い。両者の鍵が等しい暗号系は、共通鍵暗号系と呼ばれ、米国商務省標準局が採用したＤＥＳ（Data Encryption Standards)はその典型例である。また、両者の鍵が異なる暗号系の一例として、公開鍵暗号系と呼ばれる暗号系が提案された。この公開鍵暗号系は、暗号系を利用する各ユーザ（エンティティ）が暗号化鍵と復号鍵とを一対ずつ作成し、暗号化鍵を公開鍵リストにて公開し、復号鍵のみを秘密に保持するという暗号系である。公開鍵暗号系では、この一対となる暗号化鍵と復号鍵とが異なり、一方向性関数を利用することによって暗号化鍵から復号鍵を割り出せないという特徴を持たせている。
【０００５】
公開鍵暗号系は、暗号化鍵を公開するという画期的な暗号系であって、高度情報化社会の確立に必要な上述した３つの要素に適合するものであり、情報通信技術の分野等での利用を図るべく、その研究が活発に行われ、典型的な公開鍵暗号系としてＲＳＡ暗号系が提案された。このＲＳＡ暗号系は、一方向性関数として素因数分解の困難さを利用して実現されている。また、離散対数問題を解くことの困難さ（離散対数問題）を利用した公開鍵暗号系も種々の手法が提案されてきた。
【０００６】
また、各エンティティの住所，氏名等の個人を特定するＩＤ（Identity）情報を利用する暗号系が提案された。この暗号系では、ＩＤ情報に基づいて送受信者間で共通の暗号化鍵を生成する。また、このＩＤ情報に基づく暗号技法には、（１）暗号文通信に先立って送受信者間での予備通信を必要とする方式と、（２）暗号文通信に先立って送受信者間での予備通信を必要としない方式とがある。特に、（２）の手法は予備通信が不要であるので、エンティティの利便性が高く、将来の暗号系の中枢をなすものと考えられている。
【０００７】
この（２）の手法による暗号系は、ＩＤ−ＮＩＫＳ（ID-based non-interactive key sharing scheme)と呼ばれており、通信相手のＩＤ情報を用いて予備通信を行うことなく暗号化鍵を共有する方式を採用している。ＩＤ−ＮＩＫＳは、送受信者間で公開鍵，秘密鍵を交換する必要がなく、また鍵のリスト及び第三者によるサービスも必要としない方式であり、任意のエンティティ間で安全に通信を行える。
【０００８】
図５は、このＩＤ−ＮＩＫＳのシステムの原理を示す図である。信頼できるセンタの存在を仮定し、このセンタを中心にして共通鍵生成システムを構成している。図５において、エンティティＸの特定情報であるエンティティＡの名前，住所，電話番号等のＩＤ情報は、ハッシュ関数ｈ（・）を用いてｈ（ＩＤA ）で表す。センタは任意のエンティティＡに対して、センタ公開情報｛ＰＣi ｝，センタ秘密情報｛ＳＣi ｝及びエンティティＡのＩＤ情報ｈ（ＩＤA ）に基づいて、以下のように秘密情報ＳXiを計算し、秘密裏にエンティティＡへ配布する。
ＳXi＝Ｆi （｛ＳＣi ｝，｛ＰＣi ｝，ｈ（ＩＤA ））
【０００９】
エンティティＡは他の任意のエンティティＢとの間で、暗号化，復号のための共通鍵ＫABを、エンティティＡ自身の秘密情報｛ＳAi｝，センタ公開情報｛ＰＣi ｝及び相手先のエンティティＢのＩＤ情報ｈ（ＩＤB ）を用いて以下のように生成する。
ＫAB＝ｆ（｛ＳAi｝，｛ＰＣi ｝，ｈ（ＩＤB ））
また、エンティティＢも同様にエンティティＡへの鍵を共通鍵ＫBAを生成する。もし常にＫAB＝ＫBAの関係が成立すれば、この鍵ＫAB，ＫBAをエンティティＡ，Ｂ間で暗号化鍵，復号鍵として使用できる。
【００１０】
上述した公開鍵暗号系では、例えばＲＳＡ暗号系の場合にその公開鍵の長さは現在の電話番号の十数倍となり、極めて煩雑である。これに対して、ＩＤ−ＮＩＫＳでは、各ＩＤ情報を名簿という形式で登録しておけば、この名簿を参照して任意のエンティティとの間で共通鍵を生成することができる。従って、図５に示すようなＩＤ−ＮＩＫＳのシステムが安全に実現されれば、多数のエンティティが加入するコンピュータネットワーク上で便利な暗号系を構築できる。このような理由により、ＩＤ−ＮＩＫＳが将来の暗号系の中心になると期待されている。
【００１１】
【発明が解決しようとする課題】
通信相手のＩＤ情報を用いて予備通信を行うことなく暗号化鍵及び復号鍵となる共通鍵を互いに共有するようなＩＤ−ＮＩＫＳにあっては、複数のエンティティの結託等の攻撃に対して十分に安全であることが望まれる。一方、暗号通信を広範囲に行えるためには、ＩＤ−ＮＩＫＳにおける暗号化の構成原理が出来る限り単純であることが望ましい。このような安全性と単純化とは互いに相反する課題であって、構成的に単純であって暗号学的に安全であるＩＤ−ＮＩＫＳを構築できるか否かは、高度情報化社会にとって重要な問題であり、両課題を解決できるより理想的な暗号方式の探究が進められている。
【００１２】
本発明は斯かる事情に鑑みてなされたものであり、単純な構成であって安全性が高いＩＤ−ＮＩＫＳにおける秘密鍵生成器，暗号化装置，暗号通信方法，暗号通信システム及び記録媒体を提供することを目的とする。
【００１３】
【課題を解決するための手段】
請求項１に係る秘密鍵生成器は、エンティティの特定情報と秘密の対称行列とを用いて、前記エンティティ固有の秘密鍵を生成する秘密鍵生成器において、エンティティＸの特定情報に基づいてエンティティＸの公開鍵ベクトルｖX （ｘ1 ，ｘ2 ）を取得する手段と、取得した公開鍵ベクトルｖX と下記（Ａ）で示される秘密の対称行列Ｈとを用いて、Ｎ＝ＰＱ（Ｐ，Ｑは素数）を法とする下記（Ｂ）に示すような秘密鍵を求める手段とを備えることを特徴とする。
【００１４】
【数１６】
0003587746.tif 000002
【００１５】
但し、ｇ：Ｎを法とする最大生成元
ｔ：２以上の整数
【００１６】
請求項２に係る秘密鍵生成器は、エンティティの特定情報と秘密の対称行列とを用いて、前記エンティティ固有の秘密鍵を生成する秘密鍵生成器において、エンティティＸの特定情報に基づいてエンティティＸの公開鍵ベクトルｖX （ｘ1 ，ｘ2 ）を取得する手段と、取得した公開鍵ベクトルｖX と下記（Ｃ）で示される秘密の対称行列Ｈとを用いて、Ｎ＝ＰＱ（Ｐ，Ｑは素数）を法とする下記（Ｄ）に示すような秘密鍵Ｇ1 ，Ｇ2 ，Ｇ3 を求める手段とを備えることを特徴とする。
【００１７】
【数１７】
0003587746.tif 000003
【００１８】
但し、ｇ：Ｎを法とする最大生成元
ｍ：２以上の整数
【００１９】
請求項３に係る秘密鍵生成器は、エンティティの特定情報と秘密の対称行列とを用いて、前記エンティティ固有の秘密鍵を生成する秘密鍵生成器において、エンティティＸの特定情報に基づいてエンティティＸの公開鍵ベクトルｖX （ｘ1 ，ｘ2 ，…，ｘN ）を取得する手段と、取得した公開鍵ベクトルｖX と下記（Ｅ）で示される秘密の対称行列Ｈとを用いて、Ｎ′＝ＰＱｒ1 ｒ2 …ｒS （Ｐ，Ｑ，ｒ1 〜ｒS は素数）を法とする下記（Ｆ）及び（Ｇ）に示すような秘密鍵Ｇ1 ，Ｇ2 ，…，Ｇt+1 及びＨ2 ，…，Ｈi ，…，ＨN を求める手段とを備えることを特徴とする。
【００２０】
【数１８】
0003587746.tif 000004
【００２１】
但し、ｇ：Ｎ′を法とする最大生成元
Ｓ，ｔ：２以上の整数
【００２２】
請求項４に係る暗号化装置は、各エンティティの特定情報と秘密の対称行列とを用いて生成した各エンティティ固有の秘密鍵と、暗号文の送信先である相手のエンティティの特定情報に基づいて生成した公開鍵とにより生成した共通鍵を用いて平文を暗号文に暗号化する暗号化装置において、請求項１記載の秘密鍵生成器により生成されたエンティティＸの秘密鍵を取得する手段と、取得した秘密鍵と相手のエンティティＹの特定情報に基づくエンティティＹの公開鍵ベクトルｖy （ｙ1 ，ｙ2 ）とを用いて、下記（Ｈ）に示すような共通鍵ＫXYを求める手段とを備えることを特徴とする。
【００２３】
【数１９】
0003587746.tif 000005
【００２４】
請求項５に係る暗号化装置は、各エンティティの特定情報と秘密の対称行列とを用いて生成した各エンティティ固有の秘密鍵と、暗号文の送信先である相手のエンティティの特定情報に基づいて生成した公開鍵とにより生成した共通鍵を用いて平文を暗号文に暗号化する暗号化装置において、請求項２記載の秘密鍵生成器により生成されたエンティティＸの秘密鍵を取得する手段と、取得した秘密鍵と相手のエンティティＹの特定情報に基づくエンティティＹの公開鍵ベクトルｖy （ｙ1 ，ｙ2 ）とを用いて、下記（Ｉ）に示すような共通鍵ＫXYを求める手段とを備えることを特徴とする。
【００２５】
【数２０】
0003587746.tif 000006
【００２６】
請求項６に係る暗号化装置は、各エンティティの特定情報と秘密の対称行列とを用いて生成した各エンティティ固有の秘密鍵と、暗号文の送信先である相手のエンティティの特定情報に基づいて生成した公開鍵とにより生成した共通鍵を用いて平文を暗号文に暗号化する暗号化装置において、請求項３記載の秘密鍵生成器により生成されたエンティティＸの秘密鍵を取得する手段と、取得した秘密鍵と相手のエンティティＹの特定情報に基づく公開鍵ベクトル（ｙ2 ，ｙ3 ，…，ｙN ）とを用いて、下記（Ｊ）に示すような中間値Ｊを求める手段と、取得した秘密鍵と求めた中間値ＪとエンティティＹの特定情報に基づく公開鍵ベクトル（ｙ1 ）とを用いて、下記（Ｋ）に示すような共通鍵ＫXYを求める手段とを備えることを特徴とする。
【００２７】
【数２１】
0003587746.tif 000007
【００２８】
請求項７に係る暗号化装置は、請求項４〜６の何れかにおいて、各エンティティ固有の前記秘密鍵と相手のエンティティの前記公開鍵とを用いて、前記共通鍵を生成するための中間鍵を生成する手段と、生成した中間鍵を各エンティティ側で記憶しておく手段とを備えることを特徴とする。
【００２９】
請求項８に係る暗号化装置は、請求項７において、生成した中間鍵をＩＣカードに記憶しておき、記憶した中間鍵を用いて前記ＩＣカードにて前記共通鍵を生成するようにしたことを特徴とする。
【００３０】
請求項９に係る暗号通信方法は、センタ装置から各エンティティ装置へ各エンティティ固有の秘密鍵を送付し、一方のエンティティ装置が前記センタ装置から送付された該エンティティ固有の秘密鍵から求めた共通鍵を用いて平文を暗号文に暗号化して他方のエンティティ装置へ伝送し、該他方のエンティティ装置が伝送された暗号文を、前記センタ装置から送付された該エンティティ固有の秘密鍵から求めた、前記共通鍵と同一の共通鍵を用いて元の平文に復号することにより、エンティティ装置間で情報の通信を行う暗号通信方法において、エンティティＸの特定情報に基づいてエンティティＸの公開鍵ベクトルｖX （ｘ1 ，ｘ2 ）を取得するステップと、取得した公開鍵ベクトルｖX と下記（Ｌ）で示される秘密の対称行列Ｈとを用いて、Ｎ＝ＰＱ（Ｐ，Ｑは素数）を法とする下記（Ｍ）に示すような秘密鍵を求めるステップと、求めた秘密鍵をエンティティ装置へ送付するステップとを有することを特徴とする。
【００３１】
【数２２】
0003587746.tif 000008
【００３２】
但し、ｇ：Ｎを法とする最大生成元
ｔ：２以上の整数
【００３３】
請求項１０に係る暗号通信方法は、センタ装置から各エンティティ装置へ各エンティティ固有の秘密鍵を送付し、一方のエンティティ装置が前記センタ装置から送付された該エンティティ固有の秘密鍵から求めた共通鍵を用いて平文を暗号文に暗号化して他方のエンティティ装置へ伝送し、該他方のエンティティ装置が伝送された暗号文を、前記センタ装置から送付された該エンティティ固有の秘密鍵から求めた、前記共通鍵と同一の共通鍵を用いて元の平文に復号することにより、エンティティ装置間で情報の通信を行う暗号通信方法において、エンティティＸの特定情報に基づいてエンティティＸの公開鍵ベクトルｖX （ｘ1 ，ｘ2 ）を取得するステップと、取得した公開鍵ベクトルｖX と下記（Ｎ）で示される秘密の対称行列Ｈとを用いて、Ｎ＝ＰＱ（Ｐ，Ｑは素数）を法とする下記（Ｏ）に示すような秘密鍵Ｇ1 ，Ｇ2 ，Ｇ3 を求めるステップと、求めた秘密鍵をエンティティ装置へ送付するステップとを有することを特徴とする。
【００３４】
【数２３】
0003587746.tif 000009
【００３５】
但し、ｇ：Ｎを法とする最大生成元
ｍ：２以上の整数
【００３６】
請求項１１に係る暗号通信方法は、センタ装置から各エンティティ装置へ各エンティティ固有の秘密鍵を送付し、一方のエンティティ装置が前記センタ装置から送付された該エンティティ固有の秘密鍵から求めた共通鍵を用いて平文を暗号文に暗号化して他方のエンティティ装置へ伝送し、該他方のエンティティ装置が伝送された暗号文を、前記センタ装置から送付された該エンティティ固有の秘密鍵から求めた、前記共通鍵と同一の共通鍵を用いて元の平文に復号することにより、エンティティ装置間で情報の通信を行う暗号通信方法において、エンティティＸの特定情報に基づいてエンティティＸのＮ次元の公開鍵ベクトルｖX （ｘ1 ，ｘ2 ，…，ｘN ）を取得するステップと、取得した公開鍵ベクトルｖX と下記（Ｐ）で示される秘密の対称行列Ｈとを用いて、Ｎ′＝ＰＱｒ1 ｒ2 …ｒS （Ｐ，Ｑ，ｒ1 〜ｒS は素数）を法とする下記（Ｑ）及び（Ｒ）に示すような秘密鍵Ｇ1 ，Ｇ2 ，…，Ｇt+1 及びＨ2 ，…，Ｈi ，…，ＨN を求めるステップと、求めた秘密鍵をエンティティ装置へ送付するステップとを有することを特徴とする。
【００３７】
【数２４】
0003587746.tif 000010
【００３８】
但し、ｇ：Ｎ′を法とする最大生成元
Ｓ，ｔ：２以上の整数
【００３９】
請求項１２に係る暗号通信方法は、請求項９〜１１の何れかにおいて、前記共通鍵を生成するための中間鍵を生成し、生成した中間鍵を各エンティティ装置側で記憶しておくことを特徴とする。
【００４０】
請求項１３に係る暗号通信方法は、請求項１２において、生成した中間鍵をＩＣカードに記憶しておき、記憶した中間鍵を用いて前記ＩＣカードにて前記共通鍵を生成することを特徴とする。
【００４１】
請求項１４に係る暗号通信システムは、送信すべき情報である平文を暗号文に暗号化する暗号化処理、及び、送信された暗号文を元の平文に復号する復号処理を、複数のエンティティ装置間で相互に行う暗号通信システムにおいて、請求項１記載の秘密鍵生成器と、生成した秘密鍵を各エンティティへ送付する手段とを有するセンタ装置、及び、エンティティＸの秘密鍵を前記センタ装置から取得する手段と、取得した秘密鍵と相手のエンティティＹの特定情報に基づくエンティティＹのＮ次元の公開鍵ベクトルｖy （ｙ1 ，ｙ2 ）とを用いて、下記（Ｓ）に示すような前記暗号化処理及び復号処理に用いる共通鍵ＫXYを求める手段とを有する複数のエンティティ装置を備えることを特徴とする。
【００４２】
【数２５】
0003587746.tif 000011
【００４３】
請求項１５に係る暗号通信システムは、送信すべき情報である平文を暗号文に暗号化する暗号化処理、及び、送信された暗号文を元の平文に復号する復号処理を、複数のエンティティ装置間で相互に行う暗号通信システムにおいて、請求項２記載の秘密鍵生成器と、生成した秘密鍵を各エンティティへ送付する手段とを有するセンタ装置、及び、エンティティＸの秘密鍵を前記センタ装置から取得する手段と、取得した秘密鍵と相手のエンティティＹの特定情報に基づくエンティティＹのＮ次元の公開鍵ベクトルｖy （ｙ1 ，ｙ2 ）とを用いて、下記（Ｔ）に示すような前記暗号化処理及び復号処理に用いる共通鍵ＫXYを求める手段とを有する複数のエンティティ装置を備えることを特徴とする。
【００４４】
【数２６】
0003587746.tif 000012
【００４５】
請求項１６に係る暗号通信システムは、送信すべき情報である平文を暗号文に暗号化する暗号化処理、及び、送信された暗号文を元の平文に復号する復号処理を、複数のエンティティ装置間で相互に行う暗号通信システムにおいて、請求項３記載の秘密鍵生成器と、生成した秘密鍵を各エンティティへ送付する手段とを有するセンタ装置、及び、エンティティＸの秘密鍵を前記センタ装置から取得する手段と、取得した秘密鍵と相手のエンティティＹの特定情報に基づくＮ−１次元の公開鍵ベクトル（ｙ2 ，ｙ3 ，…，ｙN ）とを用いて、下記（Ｕ）に示すような中間値Ｊを求める手段と、取得した秘密鍵と求めた中間値ＪとエンティティＹの特定情報に基づく１次元の公開鍵ベクトル（ｙ1 ）とを用いて、下記（Ｖ）に示すような共通鍵ＫXYを求める手段とを有する複数のエンティティ装置を備えることを特徴とする。
【００４６】
【数２７】
0003587746.tif 000013
【００４７】
請求項１７に係る記録媒体は、コンピュータを請求項１記載の秘密鍵生成器として機能させるためのコンピュータプログラムを記録してあることを特徴とする。
【００５０】
請求項１８に係る記録媒体は、コンピュータを請求項２記載の秘密鍵生成器として機能させるためのコンピュータプログラムを記録してあることを特徴とする。
【００５３】
請求項１９に係る記録媒体は、コンピュータを請求項３記載の秘密鍵生成器として機能させるためのコンピュータプログラムを記録してあることを特徴とする。
【００６０】
【発明の実施の形態】
以下、本発明の実施の形態について具体的に説明する。
図１は、本発明の暗号通信システムの構成を示す模式図である。情報の隠匿を信頼できるセンタ１が設定されており、このセンタ１としては、例えば社会の公的機関を該当できる。このセンタ１と、この暗号系システムを利用するユーザとしての複数の各エンティティａ，ｂ，…，ｚとは、秘密通信路２ａ，２ｂ，…，２ｚにより接続されており、これらの秘密通信路２ａ，２ｂ，…，２ｚを介してセンタ１から秘密の鍵情報が各エンティティａ，ｂ，…，ｚへ伝送されるようになっている。また、２人のエンティティの間には通信路３ab，３az，３bz，…が設けられており、この通信路３ab，３az，３bz，…を介して通信情報を暗号化した暗号文が互いのエンティティ間で伝送されるようになっている。
【００６１】
まず、本発明の基本方式について説明する。
（センタ１での準備処理）
センタ１は以下の公開鍵及び秘密鍵を準備し、公開鍵を公開する。
公開鍵  Ｎ：Ｎ＝ＰＱ（Ｐ，Ｑ：５１２ビット程度の素数）
ｈ：公開鍵ベクトルを生成するための一方向性ハッシュ関数
秘密鍵  Ｈ：下記（１）に示すような２×２の対称行列
ｇ：Ｎを法とする最大生成元
【００６２】
【数３１】
0003587746.tif 000014
【００６３】
エンティティＸ，Ｙの特定情報（ＩＤ情報）を夫々ＩＤX ，ＩＤY とし、それらのハッシュ値を用いて、各エンティティＸ，Ｙの公開鍵（ベクトルｖX ，ｖY ）は、下記（２），（３）で定義される。但し、ハッシュ値サイズは１０２４ビットとする。
【００６４】
【数３２】
0003587746.tif 000015
【００６５】
（エンティティの登録処理）
エンティティＸに登録を依頼されたセンタ１は、上記（１）に示す秘密の対称行列Ｈと上記（２）に示すエンティティＸの公開鍵（ベクトルｖX ）とを用いて、Ｎ＝ＰＱを法とする下記（４）に示すような秘密鍵を求め、求めた秘密鍵を秘密裏にエンティティＸへ配布する。このように本発明では、対称行列Ｈよりサイズが大きい秘密鍵（２×２行列Ｈに基づく３次元の秘密鍵）を生成する。言い換えると、本発明では、センタ秘密のサイズを拡大してエンティティＸへ送付する。
【００６６】
【数３３】
0003587746.tif 000016
【００６７】
（エンティティ間の共通鍵の生成処理）
エンティティＸは、下記（５）のような二項定理を利用した計算を行うことにより、通信相手のエンティティＹとの共通鍵ＫXYを求める。この共通鍵ＫXYはエンティティＹ側から求めた共通鍵ＫYXと一致する。
【００６８】
【数３４】
0003587746.tif 000017
【００６９】
なお、上記（１）に示す対称行列ＨをＭ×Ｍ（Ｍ≧３）の行列に一般化することも可能であり、この場合にはＭ項定理を利用することによって共通鍵の鍵共有を実現できる。しかしながら、センタ１から配布される秘密鍵のデータ量が一定であるという条件では、Ｍを大きくすることは安全性を弱める方向に働くので、Ｍ＝２の場合が最適である。
【００７０】
次に、上述した暗号システムにおけるエンティティ間の情報の通信について説明する。図２は、２人のエンティティＸ，Ｙ間における情報の通信状態を示す模式図である。図２の例は、エンティティＸが平文（メッセージ）Ｍを暗号文Ｃに暗号化してそれをエンティティＹへ伝送し、エンティティＹがその暗号文Ｃを元の平文（メッセージ）Ｍに復号する場合を示している。
【００７１】
エンティティＸ側には、エンティティＹの特定情報ＩＤY を入力し、ハッシュ関数を利用して公開鍵（ベクトルｖY ）を得る公開鍵生成器１１と、センタ１から送られる秘密鍵（上記（４）で示すもの）と公開鍵生成器１１からの公開鍵（ベクトルｖY ）とに基づいてエンティティＸが求めるエンティティＹとの共通鍵ＫXYを生成する共通鍵生成器１２と、共通鍵ＫXYを用いて平文（メッセージ）Ｍを暗号文Ｃに暗号化して通信路３０へ出力する暗号化器１３とが備えられている。
【００７２】
また、エンティティＹ側には、エンティティＸの特定情報ＩＤX を入力し、ハッシュ関数を利用して公開鍵（ベクトルｖX ）を得る公開鍵生成器２１と、センタ１から送られる秘密鍵（上記（４）と同様なもの）と公開鍵生成器２１からの公開鍵（ベクトルｖX ）とに基づいてエンティティＹが求めるエンティティＸとの共通鍵ＫYXを生成する共通鍵生成器２２と、共通鍵ＫYXを用いて通信路３０から入力した暗号文Ｃを平文（メッセージ）Ｍに復号して出力する復号器２３とが備えられている。
【００７３】
次に、動作について説明する。エンティティＸからエンティティＹへ情報を伝送しようとする場合、まず、エンティティＹの特定情報ＩＤY が公開鍵生成器１１に入力されて公開鍵（ベクトルｖY ）が得られ、得られたエンティティＹの公開鍵が共通鍵生成器１２へ送られる。また、センタ１から上記（４）で示される秘密鍵が共通鍵生成器１２へ入力される。そして、上記（５）に従って共通鍵ＫXYが求められて、暗号化器１３へ送られる。暗号化器１３において、この共通鍵ＫXYを用いて平文（メッセージ）Ｍが暗号文Ｃに暗号化され、暗号文Ｃが通信路３０を介して伝送される。
【００７４】
通信路３０を伝送された暗号文ＣはエンティティＹの復号器２３へ入力される。エンティティＸの特定情報ＩＤX が公開鍵生成器２１に入力されて公開鍵（ベクトルｖX ）が得られ、得られたエンティティＸの公開鍵が共通鍵生成器２２へ送られる。また、センタ１から上記（４）と同様な秘密鍵が共通鍵生成器２２へ入力される。そして、上記（５）と同様に共通鍵ＫYXが求められて、復号器２３へ送られる。復号器２３において、この共通鍵ＫYXを用いて暗号文Ｃが平文（メッセージ）Ｍに復号される。
【００７５】
図３は、本発明の記録媒体の実施の形態の構成を示す図である。ここに例示するプログラムは、秘密の対称行列と各エンティティの公開鍵とを用いて、上記（４）に示すような秘密鍵を生成する処理を含むか、または、上記（４）に示すような自身の秘密鍵と相手エンティティの公開鍵とを用いて上記（５）に従って両エンティティ間の共通鍵を生成する処理を含んでおり、以下に説明する記録媒体に記録されている。なお、コンピュータ４０は、センタ１側か、または、各エンティティ側に設けられている。
【００７６】
図３において、コンピュータ４０とオンライン接続する記録媒体４１は、コンピュータ４０の設置場所から隔たって設置される例えばＷＷＷ(World Wide Web)のサーバコンピュータを用いてなり、記録媒体４１には前述の如きプログラム４１ａが記録されている。記録媒体４１から読み出されたプログラム４１ａがコンピュータ４０を制御することにより、各エンティティ固有の秘密鍵を生成するか、または、両エンティティ間の共通鍵を生成する。
【００７７】
コンピュータ４０の内部に設けられた記録媒体４２は、内蔵設置される例えばハードディスクドライブまたはＲＯＭ等を用いてなり、記録媒体４２には前述の如きプログラム４２ａが記録されている。記録媒体４２から読み出されたプログラム４２ａがコンピュータ４０を制御することにより、各エンティティ固有の秘密鍵を生成するか、または、両エンティティ間の共通鍵を生成する。
【００７８】
コンピュータ４０に設けられたディスクドライブ４０ａに装填して使用される記録媒体４３は、運搬可能な例えば光磁気ディスク，ＣＤ−ＲＯＭまたはフレキシブルディスク等を用いてなり、記録媒体４３には前述の如きプログラム４３ａが記録されている。記録媒体４３から読み出されたプログラム４３ａがコンピュータ４０を制御することにより、各エンティティ固有の秘密鍵を生成するか、または、両エンティティ間の共通鍵を生成する。
【００７９】
以下、本発明の安全性について考察する。攻撃目標の任意のエンティティＺの秘密鍵を導くために必要な結託者数に関して、以下の（定理）が成立する。
（定理）（ｔ＋１）人の結託により、任意のエンティティＺの秘密鍵を導ける。
【００８０】
（本発明の安全性を計算量格差に依存する方式：第１方式）
（１）基本方式をそのまま使用する方法
上記（定理）で述べたように、（ｔ＋１）人の結託によって基本方式は秘密鍵が露呈する。しかし、カーマイケル関数が不明であるので、ｙ1 t-i ｙ2 i の値は非常に大きくなる。例えばｙ1 の大きさを１０２４ビット、ｔ＝１０００とした場合に、ｙ1 t-i ｙ2 i の大きさは１０進数で約３１万桁に達する。任意のエンティティＺの秘密鍵を導出する際には、その要素の大きさが１０進数３１万桁であるような１０００×１０００の行列に関わる演算を必要とし、更に１０００人の結託者が必要であることを考慮した場合、研究所内，事業所内，学校内等のような比較的狭い範囲での運用に限定すれば、この基本方式は十分に実用に耐えると言える。
【００８１】
（２）専用ＩＣカードを利用する方法
ここでは高機能の専用ＩＣカードを用いて共通鍵を生成することを前提にした方法、言い換えると、攻撃に要する計算量を過大にすることを目的とした方法について説明する。図４は、このＩＣカード５０の構成図である。ＩＣカード５０は，ハッシュ関数を利用して公開鍵を生成する公開鍵生成部５１と、べき乗剰余演算，積和演算を行って後述するプレ鍵（中間鍵）を生成するプレ鍵生成部５２と、生成したプレ鍵を記憶するメモリ部５３と，共通鍵を生成する共通鍵生成部５４とを有する。
【００８２】
この専用ＩＣカードを利用する方法では、以下のような条件を設定する。
（ａ）  鍵の更新期間を１カ月程度とする。
（ｂ）  共通鍵の前段階としてのプレ鍵を、１カ月程度の更新期間中に、１０分〜１時間程度の時間を費やして生成する。
（ｃ）  １枚のＩＣカードに、頻繁に通信する相手エンティティに対する共通鍵のプレ鍵を数百名程度分記憶する。
【００８３】
この方法では、更新期間中の比較的長い時間を利用してＩＣカードにプレ鍵を生成させ、これにより攻撃者との計算量に格差を作ることを目的としているので、ｔの値は最小値の２に設定することができる。従って、センタ１はエンティティＸに対して、下記（６）に示す３種の秘密鍵を配布する。但し、ｍは大きな正の整数である。カーマイケル関数を知るセンタ１にとって、これらの秘密鍵を計算することは容易である。
【００８４】
【数３５】
0003587746.tif 000018
【００８５】
エンティティＹとの共通鍵ＫXYは、エンティティＸにおいて、エンティティＹのハッシュ値（ｙ1 ，ｙ2 ）を用いて下記（７）のように生成される。
【００８６】
【数３６】
0003587746.tif 000019
【００８７】
ここにおいて、ｙ1 m ，ｙ2 m 等はカーマイケル関数によって法をとれず、整数環上で計算しなければならないので、攻撃者にとっては非常に大きな数になり、このことが計算量の上で大きな格差を生むことになる。
【００８８】
上記（７）に対応するプレ鍵ＫXY′は、下記（８）のように定義される。
【００８９】
【数３７】
0003587746.tif 000020
【００９０】
例えば、ｍ≒１０6 である場合、Ｊ，Ｋ，Ｌ，Ｍ≒１０4 に設定し、Ｊ，Ｋ，Ｌ，Ｍを秘密に保持する。一般のｔの値に対するプレ鍵は全く同様に定義される。頻繁に通信する相手エンティティとの共通鍵を生成するための時間の短縮化を図るため、即ち、共通鍵共有時の処理の負担の軽減を図るためにプレ鍵は求められているが、プレ鍵を記憶するメモリ部５３の容量は、Ｎのサイズ｜Ｎ｜を１０２４ビットとした場合、通信相手毎に約３ｋビットとなる。上述した例のように、一般にＪ，Ｋ，Ｌ，Ｍ≪ｍのように設定するので、プレ鍵ＫXY′から共通鍵ＫXYを生成するのに要する時間が短くなるように工夫できる。一方、攻撃者にとっては、Ｊ，Ｋ，Ｌ，Ｍの組み合わせ数がこの例においても１０16程度となり、その組み合わせを同定することは不可能である。一般に、この組み合わせ数を非常に大きな数に設定することは、ｔが大きくなるほど容易となる。
【００９１】
プレ鍵を記憶しており、しかもＪ，Ｋ，Ｌ，Ｍの組み合わせを知っている正当なエンティティでは、上記（８）に示すプレ鍵ＫXY′から始めて（Ｊ＋Ｋ＋Ｌ＋Ｍ）回の累乗演算を行うだけで上記（７）に示す共通鍵ＫXYを算出することができる。これに対して攻撃者では、共通鍵ＫXYを算出するために４ｍ回もの累乗演算が必要である。
【００９２】
各エンティティがプレ鍵を生成するための時間と攻撃者がハッシュ値のｍ乗値ｘ1 m ，ｙ1 m 等を求める際に必要な計算量とを比較する。以下の条件を仮定する。
（ａ）  ２個のｎ桁の数を乗算する際に必要な計算量をｎ2 とする。
（ｂ）  エンティティはプレ鍵を１個生成するために、例えば１カ月の鍵更新期間中に１０分間の時間が与えられる。
【００９３】
（ｇA ）B mod Ｎという形の法演算に必要な計算量は、ｇA 及びＢのサイズを｜ｇA ｜，｜Ｂ｜と表記した場合、｜ｇA ｜×｜ｇA ｜×｜Ｂ｜で与えられる。｜ｇA ｜，｜Ｂ｜を１０２４ビットとし、更にこの法演算（ｇA ）B mod Ｎが１ミリ秒で１０回実行されると仮定した場合、プレ鍵生成のための計算量は１０２４×１０２４×１００００×６００となる。この場合、ｍ＝６×１０6 である。一方、攻撃者にとって必要な計算量は、ｎ＝１０２４×１００００×６００であるので、（１０２４×１００００×６００）2 となる。ｍ＝６×１０5 である場合、攻撃者にとっては正当なエンティティの約５．８６×１０5 倍の計算時間、即ち４０．７日を必要とし、正当なエンティティと攻撃者との間で計算量に大きな格差が生じる。もし、プレ鍵生成のために１００分が許された場合には、この格差は１０倍に拡大され、攻撃者には４０７日の計算時間が要求されることになる。
【００９４】
ここで計算条件を変更して、以下のように仮定する。
（ａ）  ２つのｎ桁の数の乗算に必要な計算量を、ｎ2 でなく下記（９）に示すものとする。
【００９５】
【数３８】
0003587746.tif 000021
【００９６】
（ｂ）  プレ鍵生成のために１００分間が与えられ、しかも法演算ＡB mod Ｎが１０3 倍高速化されたとする。
【００９７】
攻撃者が上述の乗算に要する計算量は、正当なエンティティの１００分に対して１３７日である。この場合、ｙ1 m 等の値は１０進数約１８．５兆桁となっている。必要なメモリの容量を考えると、この攻撃は現実的でない。ここで、プレ鍵生成時間を１〜２桁増大し、また法演算を１〜２桁高速化することは容易であり、高速演算法が将来実現された場合でも、大きな計算量の格差は残存するので、この第１方式は安全性を確保できる。
【００９８】
（本発明の安全性を確率的構造に依存する方式：第２方式）
上記（１）で与えられた２×２のセンタ秘密の対称行列Ｈを、下記（10）のようにＮ×Ｎの対称行列Ｈで与える。但し、法Ｎ′は下記（11）とする。
【００９９】
【数３９】
0003587746.tif 000022
【０１００】
ｒ1 〜ｒS は１６ビットの素数とし、これらの素数の集合をＳr ＝｛ｒi ｝と表記する。対称行列Ｈの要素ｈijはランダムな個数の素数ｒi ∈Ｓr で整除されるものとする。
【０１０１】
一方、任意のエンティティＸに対するハッシュ値を下記（12）のように与える。下記（12）における成分ｘi は素数ｒi ∈Ｓr のランダムな積とする。
【０１０２】
【数４０】
0003587746.tif 000023
【０１０３】
センタ１は、エンティティＸに対して、Ｎ′＝ＰＱｒ1 ｒ2 …ｒS を法として下記（13）に示す秘密鍵を秘密裏に送付する。また、同時に、下記（14）に示す秘密鍵も秘密裏に送付する。
【０１０４】
【数４１】
0003587746.tif 000024
【０１０５】
エンティティＹに対する共通鍵は、エンティティＸにおいて次のように生成される。まず、上記（14）の秘密鍵とエンティティＹのハッシュ値（ｙ1 以外）とを用いて、下記（15）のように中間値Ｊを求め、求めた中間値Ｊと上記（13）の秘密鍵とエンティティＹのハッシュ値（ｙ1 ）とを用いて、エンティティＹとの共通鍵ＫXYを下記（16）に従って算出する。
【０１０６】
【数４２】
0003587746.tif 000025
【０１０７】
具体例として各パラメータをＮ＝１６，ｔ＝１６，Ｓ＝６４に設定した場合、共通鍵ＫXYの指数部を展開したときの項数は16Ｈ16＝31Ｃ16＝３００５４０１９５となる。エンティティの総数を１００万人程度としても、センタ１から配布される方程式の総数（約３２００万個）がその人数を１桁程度上回り、共通鍵ＫXYの形からセンタ秘密の対称行列を導くことは困難である。また、各エンティティに配布されている方程式を連立させて解く場合、各方程式の法が一定ではなくランダムな値となってしまうこと、更にはセンタ秘密の対称行列の一部が指数部にあることにより、センタ秘密の露呈は困難である。
【０１０８】
この例において、センタ１から各エンティティへのデータ配布量は、下記（17）に示すように３２ビットである。
ｔ＋１＋Ｎ−１＝ｔ＋Ｎ＝３２      …（17）
一方、｜ＰＱ｜＝１０２４ビットとした場合、Ｎ′＝１０２４＋ｔ×Ｓ＝２０４８ビットである。従って、各エンティティに配布される総データ量は６５．５ｋビット（８．１９ｋバイト）である。なおこの場合、共通鍵生成時間は、２０４８ビットＲＳＡ暗号の復号時間の約１６倍の時間で与えられる。
【０１０９】
このように，この第２方式では、センタ１から配布される秘密鍵のうちの一部を指数部に置き、残り部分（整数環上の方程式）に確率的構造を持たせている。これらの方程式と法Ｎ′との共通因数はランダムに与えられるため、また一部の秘密鍵が指数部にあるので、縮小された共通鍵同士で比をとるといった攻撃は除かれており、結託攻撃は困難である。
【０１１０】
【発明の効果】
以上詳述したように、本発明は、構成原理が単純であり、しかも、安全性を確保したＩＤ−ＮＩＫＳにおける秘密鍵生成器，暗号化装置，暗号通信方法，暗号通信システム及び記録媒体を提供することができ、理想的なＩＤ−ＮＩＫＳの構築に寄与できる。また、プレ鍵（中間鍵）を予め求めておくようにしたので、鍵共有時の処理の負担を軽減できる。
【図面の簡単な説明】
【図１】本発明の暗号通信システムの構成を示す模式図である。
【図２】２人のエンティティ間における情報の通信状態を示す模式図である。
【図３】記録媒体の実施の形態の構成を示す図である。
【図４】ＩＣカードの構成図である。
【図５】ＩＤ−ＮＩＫＳのシステムの原理構成図である。
【符号の説明】
１  センタ
１１，２１  公開鍵生成器
１２，２２  共通鍵生成器
１３  暗号化器
２３  復号器
３０  通信路
４０  コンピュータ
４１，４２，４３  記録媒体
５０  ＩＣカード
【図１】
0003587746.tif 000038
【図２】
0003587746.tif 000039
【図３】
0003587746.tif 000040
【図４】
0003587746.tif 000041
【図５】
0003587746.tif 000042