(57)【要約】【課題】中心アルゴリズムの計算の複雑性が極めて低い新たなＩＤ−ＮＩＫＳ方式を構築し、鍵配送の問題と実装の問題との両方を解決することを課題とする。【解決手段】共通鍵暗号通信における共通鍵生成用の鍵生成情報を作成する鍵生成情報作成装置において、鍵生成情報の作成指示の入力を受付ける入力受付手段と、前記入力受付手段にて鍵生成情報の作成指示の入力が受け付けられた場合に、所定条件に合致するものとして選択された大きな素数ｐ及びｑを用いて、所定の所定式から取得されたｘl及びｙlを格納する格納手段と、前記格納手段からｘl及びｙlを取得し、これらｘl及びｙlを用いて所定式から各ユーザｌの鍵生成情報ｄ1を算定する鍵生成情報作成手段と、前記鍵生成情報作成手段にて算定された前記鍵生成情報ｄ1を所定の出力先に出力する出力手段とを備える。【選択図】        図５
2006210968.tif 000002
【特許請求の範囲】
【請求項１】
共通鍵暗号通信における共通鍵生成用の鍵生成情報を作成する鍵生成情報作成装置において、
鍵生成情報の作成指示の入力を受付ける入力受付手段と、
前記所定条件に合致するように選択された素数ｐ及びｑを格納する格納手段と、
前記入力受付手段にて鍵生成情報の作成指示の入力が受け付けられた場合に、
前記格納手段から前記素数ｐ及びｑを取得し、これら素数ｐ及びｑを用いて、
【数１】
2006210968.tif 000024
【数２】
2006210968.tif 000025
におけるｘl及びｙlを算定する中間情報作成手段と（ここで、ｐ及びｑは所定条件に合致するものとして選択された素数、ｇは素数ｐ及びｑの両乗法群における原始元、ＩＤlは各ユーザｌの個人情報番号、αはｐ−１の素因数、βはｑ−１の素因数）、
前記中間情報作成手段にて算定されたｘl及びｙlを用いて、
【数３】
2006210968.tif 000026
から各ユーザｌの鍵生成情報ｄ1を算定する鍵生成情報作成手段と（ここで、Ｌ1＝Ｌ／（ｐ−１）＝Ｌ／αγ、Ｌ2＝Ｌ／（ｑ−１）＝Ｌ／βδ、Ｌ＝１ｃｍ[ｐ−１，ｑ−１]、p−１＝αγ、ｑ−１＝βδ、γ及びδは大きな素数を含まない数）、
前記鍵生成情報作成手段にて算定された前記鍵生成情報ｄ1を所定の出力先に出力する出力手段と、
を備えたことを特徴とする鍵生成情報作成装置。
【請求項２】
前記所定条件に合致する素数ｐ及びｑを選択する素数選択手段、
を備えたことを特徴とする請求項１に記載の鍵生成情報作成装置。
【請求項３】
共通鍵暗号通信における共通鍵生成用の鍵生成情報を作成する鍵生成情報作成方法をコンピュータに実行させるための鍵生成情報作成プログラムであって、
鍵生成情報の作成指示の入力が所定の入力受付手段にて受け付けられたか否かを判断する作成指示受付ステップと、
前記作成指示受付ステップにおいて前記作成指示受付の入力が受け付けられたと判断された場合に、
所定の格納手段に格納された前記素数ｐ及びｑを取得し、これら素数ｐ及びｑを用いて、
【数４】
2006210968.tif 000027
【数５】
2006210968.tif 000028
におけるｘl及びｙlを算定する中間情報作成ステップと（ここで、ｐ及びｑは所定条件に合致するものとして選択された素数、ｇは素数ｐ及びｑの両乗法群における原始元、ＩＤlは各ユーザｌの個人情報番号、αはｐ−１の素因数、βはｑ−１の素因数）、
前記中間情報取得ステップにおいて算定されたｘl及びｙlを用いて、
【数６】
2006210968.tif 000029
から各ユーザｌの鍵生成情報ｄ1を算定する鍵生成情報作成ステップと（ここで、Ｌ1＝Ｌ／（ｐ−１）＝Ｌ／αγ、Ｌ2＝Ｌ／（ｑ−１）＝Ｌ／βδ、Ｌ＝１ｃｍ[ｐ−１，ｑ−１]、p−１＝αγ、ｑ−１＝βδ、γ及びδは大きな素数を含まない）、
前記鍵生成情報作成ステップにおいて算定された前記鍵生成情報ｄ1を所定の出力先に出力する出力ステップと、
を含む鍵生成情報作成方法をコンピュータに実行させることを特徴とする鍵生成情報作成プログラム。
【請求項４】
前記所定条件に合致する素数ｐ及びｑを選択する素数選択ステップ、
を備えたことを特徴とする請求項３に記載の鍵生成情報作成プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
この発明は、共通鍵を用いて暗号通信を行うための装置及びプログラムに関し、特に、この共通鍵を生成するための鍵生成情報を作成する鍵生成情報作成装置及び鍵生成情報作成プログラムに関する。
【背景技術】
【０００２】
任意のメッセージを暗号通信するための一般的な方式として、従来から共通鍵暗号方式が知られている。この共通鍵暗号方式においては、メッセージの送信者と受信者とが共通鍵（秘密鍵）を共有する。そして、送信者はこの共通鍵を用いてメッセージを暗号化して送信し、受信者は送信されたメッセージを共通鍵を用いて復号する。しかしながら、この共通鍵暗号方式では、鍵配送の問題、すなわち、送信者と受信者とが共通鍵をいかに秘密に共有できるかという鍵共有の問題と、送信者及び受信者が多数存在する場合に通信相手毎に異なる多量の共通鍵をいかに生成するかという鍵管理の問題とが生ずる。
【０００３】
このような鍵配送の問題を解決するため、さらに様々な共通鍵暗号方式が提案されている。これら共通鍵暗号方式は、その鍵発行のタイミングに基づいて、事前鍵発行方式（ＫＰＳ：Ｋｅｙ  Ｐｒｅｄｉｓｔｒｉｂｕｔｉｏｎ  Ｓｙｓｔｅｍ）と、予備通信不要鍵共有方式（ＮＩＫＳ：Ｎｏｎ−Ｉｎｔｅｒｅｃｔｉｖｅ  Ｋｅｙ  Ｓｈａｒｉｎｇ）とに大別される。
【０００４】
このうち、ＫＰＳ方式においては、センターが、センターデータを保管しており、このセンターデータと各ユーザの識別情報とを用いて各々の秘密鍵を生成し、この秘密鍵を予め各ユーザに配布する。そして、送信者になるユーザは、受信者の識別情報と自己の秘密鍵とを用いて共通鍵を生成し、この共通鍵を用いて作業鍵を生成する。そして、送信者は、この作業鍵を用いてメッセージを暗号化すると共に、作業鍵を共通鍵で暗号化し、これら暗号化されたメッセージと作業鍵とを受信者に送信する。これを受けた受信者は、送信者の識別情報と自己の秘密鍵とを用いて共通鍵を生成し、この共通鍵を用いて作業鍵を復号化し、この作業鍵を用いてメッセージを復号化する。このＫＰＳ方式によれば、共通鍵を共有するために送信者と受信者が事前に連絡を取り合う必要がないため、鍵配送問題の一部を解決することができる（例えば、非特許文献１参照）。
【０００５】
一方、ＮＩＫＳ方式では、秘密鍵を事前に配布することなく、共通鍵を共有することができる。例えば、ＮＩＫＳ方式の一形態である、個人情報に基づく予備通信不要鍵共有方式（ＩＤ−ＮＩＫＳ：ＩＤ−ｂａｓｅｄ  Ｎｏｎ−Ｉｎｔｅｒｅｃｔｉｖｅ  Ｋｅｙ  Ｓｈａｒｉｎｇ）において、センターは、各ユーザの個人情報に基づいて共通鍵を生成するための方法を公開すると共に、このように共通鍵を生成する際に用いる鍵生成情報（秘密情報）を秘密に保管する。そして、センターは、各ユーザからの要望に応じて、各ユーザに鍵生成情報を秘密に送信する。これを受信した各ユーザは、この鍵生成情報を用いて、通信の相手方との共通鍵を生成する。以降、各ユーザは、この共通鍵を用いて、ＫＰＳ方式と同様に暗号通信を行う（例えば、非特許文献２参照）。このＩＤ−ＮＩＫＳ方式によれば、共通鍵を共有するために送信者と受信者が事前に連絡を取り合う必要がなく、さらに、秘密鍵を事前に配布する必要がないことから秘密鍵管理の問題もないため、鍵配送問題を解決することができる。
【０００６】
また、ＮＩＫＳ方式の一形態として、Ｍａｕｒｅｒ−Ｙａｃｏｂｉ方式が知られている。このＭａｕｒｅｒ−Ｙａｃｏｂｉ方式においては、信頼できる鍵生成センターは、３個〜４個程度の秘密の大きな素数ｐ、ｑ、ｒ等を選び、それらの積ｎを法として公開する。各ユーザに配布する鍵生成情報の作成は、素数ｐ、ｑ、ｒ等を法とする離散対対数問題を解き、中国人剰余定理（ＣＲＴ）を用いてそれらを合成する（例えば、非特許文献３参照）。
【０００７】
【非特許文献１】Ｔ．Ｍａｔｓｕｍｏｔｏ  ａｎｄ  Ｈ．Ｉｍａｉ，“Ｏｎ  ｔｈｅ  ｋｅｙ  ｐｒｅｄｉｓｔｒｉｂｕｔｉｏｎ  ｓｙｓｔｅｍ：Ａ  ｐｒａｃｔｉｃａｌ  ｓｏｌｕｔｉｏｎ  ｔｏ  ｔｈｅ  ｋｅｙ  ｄｉｓｔｒｉｂｕｔｉｏｎ  ｐｒｏｂｌｅｍ，”  Ｐｒｏｃ．  ｏｆ  Ｃｒｙｐｔｏ’８７，ＬＮＣＳ  Ｖｏｌ．２９３，ｐｐ．１８５−１９３，１９８８
【非特許文献２】Ａ．Ｓｈａｍｉｒ，“Ｉｄｅｎｔｉｔｙ−ｂａｓｅｄ  ｃｒｙｐｔｏｓｙｓｔｅｍｓ  ａｎｄ  ｓｉｇｎａｔｕｒｅ  ｓｃｈｅｍｅｓ，”  Ｐｒｏｃ．  ｏｆ  Ｃｒｙｐｔｏ’８４，ＬＮＣＳ  Ｖｏｌ．１９６，ｐｐ．４７−５３，１９８５
【非特許文献３】Ｕ．Ｍ．Ｍａｕｒｅｒ  ａｎｄ  Ｙ．Ｙａｃｏｂｉ，“Ｎｏｎ−ｉｎｔｅｒａｃｔｉｖｅ  ｐｕｂｌｉｃ−ｋｅｙ  ｃｒｙｐｔｏｇｒａｐｈｙ，”  Ｐｒｏｃ．  ｏｆ  Ｅｕｒｏ−ｃｒｙｐｔｏ’９１，ＬＮＣＳ  Ｖｏｌ．５４７，ｐｐ．４９８−５０７，１９９１
【発明の開示】
【発明が解決しようとする課題】
【０００８】
しかしながら、ＫＰＳ方式においては、多数のユーザが秘密鍵を持ち寄ってセンターデータを解読する結託攻撃に関し、結託者の数が閾値を超えた場合には安全性が確保できないという問題がある。また、ＫＰＳ方式においては、ユーザ数が増加した場合には、多量の秘密鍵を管理するためにセンター側に大量のストレージを確保する必要が生じる。
【０００９】
他方、ＮＩＫＳ方式では、結託攻撃に対する安全性が高いという利点はあるが、センター側において鍵生成情報を作成するために、２〜３個の大きな素数を法とする離散対数問題を解く必要があることから、その実現が極めて困難であるという問題がある。
【００１０】
また、Ｍａｕｒｅｒ−Ｙａｃｏｂｉ方式においては、センター側において鍵生成情報を生成するために、素因数分解が極めて困難である大きな法ｐ、ｑ、及びγ等（これらの積ｎ＝ｐｑγは素因数分解できない）について離散対数問題を解いた後、中国剰余定理を使用してこれらの解を合成せねばならないず、センターの計算量が膨大となるので、実用化が極めて難しい。
【００１１】
本発明は、上記に鑑みてなされたものであって、中心アルゴリズムの計算の複雑性が極めて低い新たなＩＤ−ＮＩＫＳ方式を構築するための鍵生成情報作成装置及び鍵生成情報作成プログラムを提案することにより、鍵配送の問題と実装の問題との両方を解決することを目的とする。
【課題を解決するための手段】
【００１２】
上述した課題を解決し、目的を達成するために、請求項１に記載の鍵生成情報作成装置は、共通鍵暗号通信における共通鍵生成用の鍵生成情報を作成する鍵生成情報作成装置において、鍵生成情報の作成指示の入力を受付ける入力受付手段と、前記所定条件に合致するように選択された素数ｐ及びｑを格納する格納手段と、前記入力受付手段にて鍵生成情報の作成指示の入力が受け付けられた場合に、前記格納手段から前記素数ｐ及びｑを取得し、これら素数ｐ及びｑを用いて、
【数１】
2006210968.tif 000003
【数２】
2006210968.tif 000004
におけるｘl及びｙlを算定する中間情報作成手段と（ここで、ｐ及びｑは所定条件に合致するものとして選択された素数、ｇは素数ｐ及びｑの両乗法群における原始元、ＩＤlは各ユーザｌの個人情報番号、αはｐ−１の素因数、βはｑ−１の素因数）、前記中間情報作成手段にて算定されたｘl及びｙlを用いて、
【数３】
2006210968.tif 000005
から各ユーザｌの鍵生成情報ｄ1を算定する鍵生成情報作成手段と（ここで、Ｌ1＝Ｌ／（ｐ−１）＝Ｌ／αγ、Ｌ2＝Ｌ／（ｑ−１）＝Ｌ／βδ、Ｌ＝１ｃｍ[ｐ−１，ｑ−１]、p−１＝αγ、ｑ−１＝βδ、γ及びδは大きな素数を含まない数）、前記鍵生成情報作成手段にて算定された前記鍵生成情報ｄ1を所定の出力先に出力する出力手段とを備えたことを特徴とする。
【００１３】
また、請求項２に記載の鍵生成情報作成装置は、請求項１に記載の鍵生成情報作成装置において、前記所定条件に合致する素数ｐ及びｑを選択する素数選択手段を備えたことを特徴とする。
【００１４】
また、請求項３に記載の鍵生成情報作成プログラムは、共通鍵暗号通信における共通鍵生成用の鍵生成情報を作成する鍵生成情報作成方法をコンピュータに実行させるための鍵生成情報作成プログラムであって、鍵生成情報の作成指示の入力が所定の入力受付手段にて受け付けられたか否かを判断する作成指示受付ステップと、前記作成指示受付ステップにおいて前記作成指示受付の入力が受け付けられたと判断された場合に、所定の格納手段に格納された前記素数ｐ及びｑを取得し、これら素数ｐ及びｑを用いて、
【数４】
2006210968.tif 000006
【数５】
2006210968.tif 000007
におけるｘl及びｙlを算定する中間情報作成ステップと（ここで、ｐ及びｑは所定条件に合致するものとして選択された素数、ｇは素数ｐ及びｑの両乗法群における原始元、ＩＤlは各ユーザｌの個人情報番号、αはｐ−１の素因数、βはｑ−１の素因数）、前記中間情報取得ステップにおいて算定されたｘl及びｙlを用いて、
【数６】
2006210968.tif 000008
から各ユーザｌの鍵生成情報ｄ1を算定する鍵生成情報作成ステップと（ここで、Ｌ1＝Ｌ／（ｐ−１）＝Ｌ／αγ、Ｌ2＝Ｌ／（ｑ−１）＝Ｌ／βδ、Ｌ＝１ｃｍ[ｐ−１，ｑ−１]、p−１＝αγ、ｑ−１＝βδ、γ及びδは大きな素数を含まない）、前記鍵生成情報作成ステップにおいて算定された前記鍵生成情報ｄ1を所定の出力先に出力する出力ステップと、を含む鍵生成情報作成方法をコンピュータに実行させることを特徴とする。
【００１５】
また、請求項４に記載の鍵生成情報作成プログラムは、請求項３に記載の鍵生成情報作成プログラムにおいて、前記所定条件に合致する素数ｐ及びｑを選択する素数選択ステップを備えたことを特徴とする。
【発明の効果】
【００１６】
本発明によれば、安全性を損なうことなく、鍵生成情報の生成のための計算の複雑性を著しく減じることができるので、ＩＤ−ＮＩＫＳ方式の鍵配送の問題と実装の問題との両方を解決することができる。
【発明を実施するための最良の形態】
【００１７】
以下に添付図面を参照して、この発明に係る実施例を詳細に説明する。まず、〔I〕本発明の基本的概念を説明した後、〔II〕本発明の実施の形態について説明し、〔III〕最後に、本発明の実施の形態に対する変形例について説明する。
【００１８】
〔I〕本発明の基本的概念
まず、本発明の基本的概念について説明する。本発明は、概略的には、中心アルゴリズムの計算の複雑性が極めて低い新たなＩＤ−ＮＩＫＳ方式を構築するための鍵生成情報作成装置及び鍵生成情報作成プログラムを提案することにより、鍵配送の問題と実装の問題との両方を解決するものである。
【００１９】
この本発明に係る方式では、センター側において、後述する所定条件を満たすように選択された２つの大きな素数ｐとｑとの各々について、法（ｍｏｄ、ｍｏｄｕｌｕｓ）をｐ又はｑとする２つの単純な離散対数問題を解き、さらにある素因数分解を行うことにより、鍵生成情報（秘密情報、共通鍵生成情報）の生成を行う。そして、センターから各ユーザに、この鍵生成情報を提供する。次いで、各ユーザは、この鍵生成情報を用いて共通鍵の作成等を行い、暗号通信を行う。
【００２０】
このような本方式において、鍵共有に必要な計算量は、一つの法指数計算、法（ｍｏｄ）ｎ＝ｐｑのみであり、各ユーザｌの秘密の情報を記憶するために必要なストレージの量は、ｎの対数より小さい１ワードサイズである。従って、実装上の困難性も解決することができる。なお、本方式は、ＥｌＧａｍａｌ暗号類似の予備通信不要公共鍵暗号化システムにも適用できる。
【００２１】
また、この方式におけるの暗号通信の安全性は、素因数分解ｎ＝ｐｑの難しさに依存するが、上記所定条件下で選択されたｐとｑとを用いることにより、この素因数分解ｎ＝ｐｑが十分な困難性を有するため、本方式における暗号通信の安全性が確保される。この所定条件については後述する。
【００２２】
さらに、本方式によれば、仮にユーザ間での結託が可能であったとしても、結託者以外のどのユーザの秘密の情報も偽造することはできないため、結託攻撃に対する安全性も確保される。
【００２３】
〔II〕本発明の実施の形態
次に、本発明の実施の形態について説明する。ただし、この実施の形態によって本発明が限定されるものではない。以下では、鍵生成情報の作成や作成された鍵生成情報を用いて暗号通信を行うためのシステム構成を説明し、次いで、このシステム上で実行される各種の処理内容について説明する。
【００２４】
（システム構成）
最初に、実施の形態にかかる暗号通信システムの構成について説明する。図１は、暗号通信システムの全体構成を機能概念的に例示する図である。この図１に例示するように、暗号通信システムは、信頼できるセンターのサーバ１０と、各ユーザ（エンティティ）の通信端末２０とを、所定のネットワーク３０を介して通信可能に接続して構成されている。
【００２５】
このうち、サーバ１０は、共通鍵生成用の鍵生成情報の作成等を行うもので、特許請求の範囲における鍵生成情報作成装置に対応する。図２は、図１のサーバ１０の構成を機能概念的に例示するブロック図である。この図２に例示するように、サーバ１０は、データベース１１、通信制御インターフェース（通信制御ＩＦ）１２、及び、制御部１３を備えて構成されており、これら各部がバスにて相互に入出力可能に接続されている。
【００２６】
このうち、データベース１１は、鍵生成情報を作成するために必要な各種の情報を格納するためのもので、特許請求の範囲における格納手段に対応し、例えば、ハードディスクの如き不揮発的記憶媒体にて構成される。また、通信制御ＩＦ１２は、通信端末２０との間における通信の制御を行う通信制御手段で、特許請求の範囲における入力受付手段及び出力手段に対応する。
【００２７】
また、制御部１３は、データベース１１の各部を制御する制御手段であり、機能概念的に、素数選択部１３ａ、中間情報作成部１３ｂ、及び、鍵生成情報作成部１３ｃを備えて構成されている。このうち、素数選択部１３ａは、鍵生成情報を作成するために必要な中間情報を取得するため、所定条件に合致する素数ｐ及びｑを選択するもので、特許請求の範囲における素数選択手段に対応する。また、中間情報作成部１３ｂは、鍵生成情報を作成するために必要な中間情報を取得するもので、特許請求の範囲における中間情報作成手段に対応する。また、鍵生成情報作成部１３ｃは、共通鍵暗号通信における共通鍵生成用の鍵生成情報を作成するためのもので、特許請求の範囲における鍵生成情報作成手段に対応する。これら各部の具体的処理内容については後述する。
【００２８】
一方、図１の通信端末２０は、ユーザにて操作されて暗号化通信を行う暗号通信端末装置である。図３は、図１の通信端末２０の構成を機能概念的に示すブロック図である。この図３に例示するように、通信端末２０は、機能概念的に、記憶部２１、入力部２２、出力部２３、入出力制御インターフェース(入出力制御ＩＦ）２４、通信制御インターフェース（通信制御ＩＦ）２５、及び、制御部２６を備えて構成されており、これら各部がバスを解して相互にデータ通信可能に接続されている。
【００２９】
このうち、記憶部２１は、情報を記憶する記憶手段であり、例えば、ＲＡＭ（Ｒａｎｄｏｍ  Ａｃｃｅｓｓ  Ｍｅｍｏｒｙ）の如き揮発的記憶媒体やハードディスクの如き不揮発的記憶媒体を用いて構成することができる。また、入力部２２は、ユーザが任意の情報をクライアントに入力するための入力手段であり、例えば、マウスの如きポインティングデバイスとキーボードとから構成されている。また、出力部２３は、任意の情報をユーザに対して出力するための出力手段であり、例えばモニタとして構成されている。また、入出力制御ＩＦ２４は、これら入力部２２及び出力部２３によるデータの入出力を制御する入出力制御手段である。また、通信制御ＩＦ２５は、通信端末２０とサーバ１０との間における通信制御を行う通信制御手段である。
【００３０】
また、制御部２６は、通信端末２０の各部を制御する制御手段であり、機能概念的に、共通鍵作成部２６ａ、作業鍵作成部２６ｂ、作業鍵暗号化部２６ｃ、メッセージ暗号化部２６ｄ、作業鍵復号化部２６ｅ、及び、メッセージ復号化部２６ｆを備えて構成されている。このうち、共通鍵作成部２６ａは共通鍵を作成する共通鍵作成手段、作業鍵作成部２６ｂは作業鍵を作成する作業鍵作成手段、作業鍵暗号化部２６ｃは作業鍵を暗号化する作業鍵暗号化手段、メッセージ暗号化部２６ｄは送信者が受信者に送りたい任意の情報（以下、メッセージ）を暗号化するメッセージ暗号化手段、作業鍵復号化部２６ｅは作業鍵を復号化する作業鍵復号化手段、メッセージ復号化部２６ｆはメッセージを復号化するメッセージ復号化手段である。これら各部の具体的処理内容については後述する。
【００３１】
（処理内容）
次に、このようなシステム上で実行される処理の内容について説明する。なお、以下では、ユーザである送信者Ａからユーザである受信者ＢにメッセージＭ（０＜Ｍ＜ｎ）を送信する場合を例にとって説明する。以下では、必要に応じて、送信者Ａの個人情報ＩＤlと鍵生成情報ｄ1とをそれぞれ個人情報ＩＤAと鍵生成情報ｄA、受信者Ｂの個人情報ＩＤlと鍵生成情報ｄ1とをそれぞれ個人情報ＩＤBと鍵生成情報ｄBとする。
【００３２】
この処理全体の概要を図４に概念的に示す。この図４に示すように、送信者Ａの通信端末を２０Ａ、受信者Ｂの通信端末を２０Ｂとすると、送信者Ａ及び受信者Ｂは、それぞれ自己の通信端末２０Ａ、２０Ｂを介して、鍵生成情報の作成要求をサーバ１０に送信する（ステップＳＡ−１、ＳＡ−２）。また、この要求と同時に、又は、要求の前後の任意のタイミングにおいて、送信者Ａ及び受信者Ｂは、自己の個人情報ＩＤA、ＩＤBをサーバに送信する。そして、サーバでは、これら個人情報ＩＤA、ＩＤBをデータベース１１に格納する。
【００３３】
一方、サーバ１０は、鍵生成情報の作成要求を受信すると、鍵生成情報作成処理を行うことによって鍵生成情報を作成する（ステップＳＡ−３）。次いで、サーバ１０は、この鍵生成情報を各通信端末２０Ａ、２０Ｂに送信する。
【００３４】
その後、送信者Ａ及び受信者Ｂは、それぞれ、サーバ１０から送信された鍵生成情報を用いて、自己の通信端末２０Ａ、２０Ｂにおいて、送信者Ａと受信者Ｂとの相互の通信に用いる共通鍵を作成する（ステップＳＡ−４、ＳＡ−５）。
【００３５】
次いで、送信者Ａは、通信端末２０Ａを用いて、作業鍵を作成し（ステップＳＡ−６）、この作業鍵を共通鍵によって暗号化し（ステップＳＡ−７）、さらにメッセージを作業鍵を用いて暗号化して（ステップＳＡ−８）、これら暗号化された作業鍵及びメッセージを受信者Ｂの通信端末２０Ｂに送信する。
【００３６】
一方、受信者Ｂは、送信者Ａから送信された作業鍵を自己の共通鍵を用いて復号化し（ステップＳＡ−９）、この復号化した作業鍵を用いてメッセージを復号化する（ステップＳＡ−１０）。これにて、受信者Ｂはメッセージを解読することができるので、送信者Ａから受信者Ｂへのメッセージ送信が完了する。なお、２回目以降からは、以前に作成した共通鍵を用いてステップＳＡ−６及びそれ以降の処理を行えばよく、ステップＳＡ−１〜ＳＡ−５を省略することができる。
【００３７】
（鍵生成情報作成処理）
これら各処理のうち、鍵生成情報作成処理（ステップＳＡ−３）についてより詳細に説明する。この鍵生成情報作成処理は、法ｐとｑの各々について二つの単純な離散対数問題を解くことにより、鍵生成情報の作成を行う処理であり、主として、サーバ１０の素数選択部１３ａ、中間情報作成部１３ｂ、及び、鍵生成情報作成部１３ｃによって実行される。図５は、鍵生成情報作成処理のフローチャートである。
【００３８】
この図５に示すように、まず、制御部１３は、各ユーザの通信端末２０からの鍵生成情報の要求を監視する（ステップＳＢ−１）。そして、この要求を通信制御ＩＦ１２を介して受信した場合（ステップＳＢ−１、Ｙｅｓ。特許請求の範囲における作成指示受付ステップに対応する）、制御部１３の素数選択部１３ａは、所定条件に合致する素数ｐ及びｑを選択する（ステップＳＢ−２。特許請求の範囲における素数選択ステップに対応する）。
【００３９】
ここで、所定条件とは、以下の（１）及び（２）の２つである。
【００４０】
所定条件（１）：
有限群上の離散対数問題を解くためのアルゴリズムの一つである公知の「Ｐｏｈｌｉｇ−Ｈｅｌｌｍａｎアルゴリズム」を容易に適用できること、すなわち、Ｐｏｈｌｉｇ−Ｈｅｌｌｍａｎアルゴリズムを用いて、ｐとｑ各々についての離散対数問題を容易に解くことができること（なお、Ｐｏｈｌｉｇ−Ｈｅｌｌｍａｎアルゴリズムについては、Ｓ．Ｃ．Ｐｏｈｌｉｇ  ａｎｄ  Ｍ．Ｅ．Ｈｅｌｌｍａｎ，“Ａｎ  ｉｍｐｒｏｖｅｄ  ａｌｇｏｒｉｔｈｍ  ｆｏｒ  ｃｏｍｐｕｔｉｎｇ  ｌｏｇａｒｉｔｈｍｓ  ｏｖｅｒ  ＧＦ（ｐ）  ａｎｄ  ｉｔｓ  ｃｒｙｐｔｏｇｒａｐｈｉｃ  ｓｉｇｎｉｆｉｃａｎｃｅ，”  ＩＥＥＥ  Ｔｒａｎｓ．  Ｉｎｆｏｒｍ．  Ｔｈｅｏｒｙ，  ｖｏｌ．ＩＴ−２４，ｎｏ．１，ｐｐ．１０６−１１０，Ｊａｎｕａｒｙ  １９７８参照）。ここで、大きな素数ｐあるいはｑを法とする離散対数を求める場合、ｐ−１及びｑ−１に大きな素因数αあるいはβが含まれており、また後述する式（１）及び（２）のように離散対数問題が設定されているので、αおよびβの範囲は離散対数問題の範囲から除外され、解の範囲が縮小される。さらに、αおよびβを除いた部分には、大きな素因数が含まれていないので、Ｐｏｈｌｉｇ−Ｈｅｌｌｍａｎアルゴリズムを用いて離散対数問題を容易に解くことができることができる。α、βを除外した部分の最大素因数ｐ0がある程度小さくなると、計算量が指数時間オーダの計算量から多項式時間オーダの計算量Ｏ（（ｌｏｇｐ0）2）（ｐ0のビット数の２乗のオーダー）になることが知られている。
【００４１】
所定条件（２）：
Ｐｏｌｌａｒｄ素因数分解アルゴリズムまたはその変形アルゴリズムを適用しても、p±１及びｑ±１が少なくとも一つの大きな素数を含むために、解を導けないこと。例えば、法ｎの下で、その素数未満の全ての素数の積を計算する時間が、計算量的に事実上不可能であればよい。一例としては、現在のコンピュータの性能では、２００ビット程度であれば十分であると考えられる。因みに、２００ビット未満の素数は、２200／ｌｏｇ２200〜２193個になる。ここで、ＤＥＳ（Ｄａｔａ  Ｅｎｃｒｙｐｔｉｏｎ  Ｓｔａｎｄａｒｄ）暗号系の鍵を総当りで探索する攻撃を考えた場合の計算量は、２56回程度であるため、２193個は十分に大きな数値であることが判る。
【００４２】
ここでは、ｐ及びｑが二つの大きな素数、たとえば５１２ビットであると仮定する。また、p−１＝αγかつｑ−１＝βδであり、式中α及びβは二つの大きな素数であり、γ及びδは大きな素数を含まないものとする。したがって、法ｐ及びｑの離散対数問題を解くため、指数計算（ｉｎｄｅｘ  ｃａｌｃｕｌｕｓ）で補完しつつ、Ｐｏｈｌｉｇ−Ｈｅｌｌｍａｎアルゴリズムを容易に適用することができる。ここで、ｐ−1及びｑ−１はそれぞれ大きな素因数α及びβを含むため、Ｐｏｌｌａｒｄ素因数分解アルゴリズムを適用することは極めて難しい。また、同様の理由から、ｐ＋１及びｑ＋１もまた少なくとも一つの大きな素因数を含むように、ｐ及びｑを選択することが望ましい。すなわち、ｐ＋１やｑ＋１が極めて大きな素因数を含むか否かが不明でありながら、大量のリソースを投入してｐ＋１やｑ＋１に対する攻撃を行うユーザが存在する場合には、ｐ＋１及びｑ＋１も少なくとも一つの大きな素因数を含むようにしておくことが必要になる。通常、５００ビット程度の大きな素数ｐ、ｑを選択した場合、ｐ＋１及びｑ＋１は、確率的にはかなり大きな素因数を含むため、ｐ＋１及びｑ＋１が少なくとも一つの大きな素因数を含むようにｐ、ｑの選択を意図的に行わなくても、安全性が損なわれることはない。
【００４３】
なお、このような所定条件を満たす素数ｐ及びｑの選択は、最初に１回のみ行ってデータベース１１に格納しておけばよく、２回目以降の処理においては、最初に選択してデータベース１１から素数ｐ及びｑを取得して用いることができる。
【００４４】
その後、中間情報作成部１３ｂは、素数選択部１３ａにて選択された素数ｐ及びｑを用いて、以下の二つの式（１）及び（２）を、ｘl及びｙlについて解く（ステップＳＢ−３。特許請求の範囲における中間情報作成ステップに対応する）。すなわち、離散対問題を解く。ここで、ｎ＝ｐｑかつＬ＝１ｃｍ[ｐ−１，ｑ−１]と置き、ｇを、整数法であるｐ及びｑの両乗法群における原始元とする。また、ＩＤlを、各ユーザｌの個人情報番号、α及びβはそれぞれｐ−１及びｑ−１の素因数である。ここで、式（１）及び（２）がすべてのＩＤlに対して一意の解ｘl及びｙlを持つことは、離散対数問題の性質上明らかである。このように取得されたｘl及びｙlはデータベース１１に格納される。
【００４５】
【数７】
2006210968.tif 000009
【数８】
2006210968.tif 000010
【００４６】
また、Ｌ1とＬ2とを以下の式（３）又は（４）のように定義し、各ユーザｌの鍵生成情報ｄ1を以下の式（５）のように定義する。そして、鍵生成情報作成部１３ｃは、データベース１１からｘl及びｙlを取得する（特許請求の範囲における中間情報取得ステップに対応する）。次いで、鍵生成情報作成部１３ｃは、これら取得した上記のｘl及びｙlを用いて、式（５）を素因数分解することにより、各ユーザｌの鍵生成情報ｄ1を計算する（ステップＳＢ−４。特許請求の範囲における鍵生成情報作成ステップに対応する）。
【００４７】
【数９】
2006210968.tif 000011
【数１０】
2006210968.tif 000012
【数１１】
2006210968.tif 000013
【００４８】
その後、鍵生成情報作成部１３ｃは、この鍵生成情報ｄ1を通信制御ＩＦ１２を介して各ユーザｌに秘密に送信する（ステップＳＢ−５。特許請求の範囲における出力ステップに対応する）。このように送信された鍵生成情報ｄ1は、各通信端末２０の記憶部２１に記憶される。これにて鍵生成情報作成処理が終了する。なお、この鍵生成情報ｄ1の送付形態には任意の形態を用いることができ、例えば、ネットワーク３０を他の任意の暗号を用いてセキュアチャネル化した上で送信したり、ネットワーク３０に替えてＩＣカードとして送付してもよい。
【００４９】
（鍵生成情報作成処理以降の各処理）
次いで、鍵生成情報作成処理以降の各処理についてより詳細に説明する。ここでは、任意のユーザＡからユーザＢにメッセージＭ（０＜Ｍ＜ｎ）を送信する場合を例にとって説明する。以下では、ユーザＡを送信者Ａ、ユーザＢを受信者Ｂ、送信者Ａの個人情報ＩＤlと鍵生成情報ｄ1をそれぞれ個人情報ＩＤAと鍵生成情報ｄA、受信者Ｂの個人情報ＩＤlと鍵生成情報ｄ1をそれぞれ個人情報ＩＤBと鍵生成情報ｄBとする。
【００５０】
まず、図４において、送信者Ａが自己の通信端末２０Ａの入力部２２を介して所定操作を行うと、共通鍵作成部２６ａは、記憶部２１から鍵生成情報ｄAを取得すると共に、サーバから所定方法で受信者Ｂの個人情報ＩＤBを取得し、これら鍵生成情報ｄA及び個人情報ＩＤBを用いて、受信者Ｂとの共通鍵ＫABを以下の式（６）により計算する（ステップＳＡ−４）。なお、送信者Ａ及び受信者Ｂが共通鍵を生成する際に必要になる法ｎは、センターによって公知の方法で公開される。
【００５１】
また、同様に、送信者Ｂが自己の通信端末２０Ｂの入力部２２を介して所定操作を行うと、共通鍵作成部２６ａは、記憶部２１から鍵生成情報ｄBを取得すると共に、サーバから所定方法で受信者Ａの個人情報ＩＤAを取得し、これら鍵生成情報ｄB及び個人情報ＩＤAを用いて、受信者Ａとの共通鍵ＫABを以下の式（７）により計算する（ステップＳＡ−５）。したがって、ＡとＢとの共通鍵は、次の式（８）によって与えられる。
【００５２】
【数１２】
2006210968.tif 000014
【数１３】
2006210968.tif 000015
【数１４】
2006210968.tif 000016
【００５３】
このように、送信者Ａと受信者Ｂとの間で一度共通鍵が共有されれば、送信者Ａから受信者Ｂへの暗号通信は、以下のように容易に実行することができる。まず、通信端末２０Ａの作業鍵生成部２６ｂは、作業鍵を生成し（ステップＳＡ−６）、この作業鍵を作業鍵暗号化部２６ｃ及びメッセージ暗号化部２６ｄに送出する。この作業鍵の生成方法は任意であるが、例えば、乱数Ｒを生成してこれを作業鍵とする。
【００５４】
そして、通信端末２０Ａの作業鍵暗号化部２６ｃは、この作業鍵Ｒを、上記式（６）にて計算した共通鍵ＫABを使用して、以下の式（９）のように暗号化する（ステップＳＡ−７）。
【００５５】
【数１５】
2006210968.tif 000017
【００５６】
また、通信端末２０Ａのメッセージ暗号化部２６ｄは、この作業鍵Ｒを使用して、メッセージＭを以下の式（１０）のように暗号化する（ステップＳＡ−８）。
【００５７】
【数１６】
2006210968.tif 000018
【００５８】
次いで、制御部２６は、このように暗号化された作業鍵Ｒ及びメッセージＭを、暗号Ｃ＝（Ｃ1、Ｃ2）として、ネットワーク３０を介して受信者Ｂに送信する。なお、これら作業鍵ＲやメッセージＭを暗号化する際の暗号化アルゴリズムには任意のものを用いることができるが、例えば、標準的なブロック暗号である、ＤＥＳやＡＥＳ（Ａｄｖａｎｃｅｄ  Ｅｎｃｒｙｐｔｉｏｎ  Ｓｔａｎｄａｒｄ）を用いることができる。
【００５９】
次に、暗号Ｃを受信した受信者Ｂの通信端末２０Ｂの作業鍵復号化部２６ｅ及びメッセージ復号化部２６ｆは、この暗号Ｃを、上記式（７）にて計算した共通鍵ＫABを使用して、以下の式（１１）のように復号化することにより、メッセージを解読する（ステップＳＡ−９、ＳＡ−１０）。このように解読されたメッセージは出力部２３を介して所定形式で出力される。これにて、送信者Ａと受信者Ｂとの間の秘密通信が終了する。
【００６０】
【数１７】
2006210968.tif 000019
【００６１】
（安全性について）
以下、本実施の形態に係る暗号化方式の安全性について説明する。ここでは、概略的に、既に安全性が検証されている公知の公開鍵暗号方式である、ＥｌＧａｍａｌ暗号及びＲＳＡ暗号（Ｒｉｖｅｓｔ  Ｓｈａｍｉｒ  Ａｄｌｅｍａｎ  Ｃｒｙｐｔｏｇｒａｐｈｙ）との対比を行うことにより、安全性を説明する。
【００６２】
まず、ＥｌＧａｍａｌ暗号との対比による安全性について説明する。本方式は、ＥｌＧａｍａｌ暗号における公開鍵ｇと、受信者Ｂの公開情報ｈB＝ｇdB（ｍｏｄ  ｐ）を、送信者Ａの個人情報ＩＤA及び共通鍵ＫABに置き換えることで、ＥｌＧａｍａｌ暗号システムを修正したものと考えることができる。したがって、本方式の安全性は、ＥｌＧａｍａｌ暗号の安全性と等価であるということができる。
【００６３】
次に、ＲＳＡ暗号との対比による安全性について説明する。本方式の安全性は、素因数分解ｎ＝ｐｑの難しさに依存する。もし、個人情報ＩＤBを、受信者Ｂによって暗号化された暗号Ｃであるとみなし、秘密の情報ｄAを送信者Ａの解読鍵ｄであるとみなすならば、本方式における共通鍵ＫABの生成は、ＲＳＡ公共鍵暗号化システムの解読処理とみなすことができる。従って、この仮説が成り立つ場合には、本方式の安全性は、ＲＳＡ暗号システムの安全性と等価であるということができる。
【００６４】
そこで、安全性の等価性を議論する前に、安全性に関して、ｄlがｄと等価であることを示す。必要がある。すなわち、（１）ユーザの結託によって多くのｄl（ｌ＝Ａ、Ｂ、Ｃ…）が集められたとしても、本方式の安全性を損なうようないかなる秘密の情報も、公式（５）から導出できないこと、及び、（２）ｄl及び鍵共有公式の組である下記式（１２）を使用して任意の二人の標的ユーザＸ及びＹの間の共通鍵ＫXYを偽造することができないことを示す必要がある。
【００６５】
【数１８】
2006210968.tif 000020
【００６６】
まず、一組の連立方程式ｄl（ｌ＝Ａ、Ｂ、Ｃ…）を、αL1ｘl及びβＬ2ｙlで解くことを考える。しかし、ｔ人のユーザの獲得する公式セットは、Ｌも含めて（２ｔ＋１）個の未知数を含むため、情報不足で、αL1ｘl及びβL2ｙlで公式を解くことはできない。ここで、ｄl（ｌ＝Ａ、Ｂ、Ｃ…）の最大公約数を計算すれば、ｄlは下記式（１３）のように書き直せることから、αβを求めることができる。
【００６７】
【数１９】
2006210968.tif 000021
【００６８】
ここで、式（１３）において、δ'＝δ/ｇｃｄ[γ，δ]、γ'＝γ/ｇｃｄ[γ，δ]であり、αβはLの因数である。しかし、α、βはともに大きな素数であるため、αとβとをその積αβから求めるのは極めて困難である。仮に、α及びβを求め得たとしても、Ｌ1、Ｌ2、ｘl及びｙlは、ｐ及びｑが未知数であるから、求め得ない（定理１：ｐ及びｑが未知数であれば、いずれのｄl（ｌ＝Ａ、Ｂ、Ｃ…）の組からも本方式の安全性を損なうような情報は獲得できない）。
【００６９】
次に、ｄl及びｘとｌ（ｌ＝Ａ、Ｂ、Ｃ、…、Ｍ）との間の鍵共有公式を使用して、二人のユーザＸとＹとの間の共通鍵ＫXYを偽造することを考える。ＫXYを偽造する巧妙な方法の一つは以下のように考えられる。もし、ユーザＹの個人情報ＩＤyを、下記式（１４）で表すことができるとすれば（ａ、ｂ、ｃ、…、ｍは整数）、共通鍵ＫXYは、下記式（１５）によって偽造できるように思われる。
【００７０】
【数２０】
2006210968.tif 000022
【数２１】
2006210968.tif 000023
【００７１】
しかし、指数整数[ａ、ｂ、ｃ、…、Ｍ]の組を計算する問題は、法 ｎの離散対数問題を解くことと等価である。つまり、素因数分解ｎ＝ｐｑを解くのが困難であるという条件のもとでは、ｄxを式（１２）から解くことができる（定理２：「もしｎ＝ｐｑの素因数分解が不可能であれば、任意の二人のユーザＸ及びＹの間の共通鍵ＫXYを、ｄl及び鍵共有公式を使用して偽造することは不可能である」）。
【００７２】
これら定理１及び定理２から、ｎ＝ｐｑを素因数分解できる場合は、本方式もＲＳＡ方式も安全性を欠くことになる。したがって、ｄlとｄとは安全性の観点からは等価といえる。
【００７３】
最後に、本方式の安全性を保証するため、定理３として、「本方式のＩＤ−ＮＩＫＳの安全性は、ＲＳＡの安全性と等価である」ことを示す。
証明：安全性の等価性を示すため、ここでは、以下の二つの命題を検討する。
〈Ｐ１〉もしＲＳＡが安全ならば、本方式も安全である。
〈Ｐ２〉もし本方式が安全ならば、ＲＳＡも安全である。
ここで、Ｐ２の対偶は以下のようになる。
〈Ｐ２*〉もしＲＳＡが安全でないなら、本方式も安全でない。
以下においては、命題Ｐ１と命題Ｐ２のかわりに、命題Ｐ１と命題Ｐ２*を示す。
【００７４】
まず、命題Ｐ１を示す。もしＲＳＡが安全ならば、ｄは式ｍ＝ｃｄ（ｍｏｄ  ｎ）で解くことはできず、ｎ＝ｐｑを素因数分解してｐ及びｑを求めることはできない。つまり、Lによってｄを求めることはできない。同様に、ユーザの鍵生成情報ｄxは、式ＫlX＝ＩＤdXl（ｍｏｄ  ｎ）から求められず、本方式を損なうような如何なる鍵生成情報も導かれることはなく、ｐ及びｑが未知数であるため、任意の二人のユーザＸ及びＹの間の共通鍵ＫXYを偽造することはできない。
【００７５】
次に、命題Ｐ２*を示す。もしＲＳＡが安全でないなら、鍵生成情報ｄを式ｍ＝ｃｄ（ｍｏｄ  ｎ）から求めることができるか、または、ｎ＝ｐｑを素因数分解してｐ及びｑ、つまりＬ及びｄに等価な値を求めることができる。同様に、鍵生成情報ｄxは、ＫlX＝ＩＤdXl（ｍｏｄ  ｎ）から求められる。したがって、本方式は安全でない。あるいは、ｐ及びｑ、したがってＬが与えられているため、任意のユーザの鍵生成情報ｄxを再構築することができる。したがって、本方式は安全でない。
【００７６】
このように、命題Ｐ１と命題Ｐ２*を示すことができ、従って、本方式のＩＤ−ＮＩＫＳの安全性は、ＲＳＡの安全性と等価であることが判る。
【００７７】
（実装性について）
次に、本実施の形態に係る暗号化方式の実装性について説明する。ここでは、概略的に、ＮＩＫＳ方式の一形態であるＭａｕｒｅｒ−Ｙａｃｏｂｉ方式との対比を行うことにより、実装性を検討する。本実施の形態に係る暗号化方式と、Ｍａｕｒｅｒ−Ｙａｃｏｂｉ方式とは、いずれも、（１）素因数分解の不可能性に依存しており、かつ、（２）法の離散対数問題は、なんらかの大きな素数の合成数である、という点において共通している。従って、これら両方式の安全性は等価である。しかし、本実施の形態に係る暗号化方式は、Ｍａｕｒｅｒ−Ｙａｃｏｂｉ方式に比べて、各ユーザｌの鍵生成情報ｄlを生成するための計算の複雑性という点で、本質的にＭａｕｒｅｒ−Ｙａｃｏｂｉ方式と異なっている。すなわち、本方式においては、中心アルゴリズムに導入される新しい着想のため、鍵生成情報ｄlの生成のための計算の複雑性が著しく減じられ、安全性を損なうことなく容易に実現することができる。
【００７８】
Ｍａｕｒｅｒ−Ｙａｃｏｂｉ方式において、鍵生成情報ｄlを生成するには、極めて大きな法、ｐ、ｑ、及び、γ（これらの積ｎ＝ｐｑγは素因数分解できない）について、２以上、たとえば、３つの離散対数問題を解いた後、中国剰余定理を使用してこれらの解を合成せねばならない。したがって、各ユーザの鍵生成情報を生成することが極めて難しい。
【００７９】
これに対して、本方式では、式（１）及び（２）に示した、ｐ及びｑについての二つの単純な離散対数問題を解くことにより、各ユーザの鍵生成情報を生成することができる。これら式（１）及び（２）は、指数計算で補完しつつＰｏｈｌｉｇ−Ｈｅｌｌｍａｎアルゴリズムを使用することにより、ｘl及びｙlについて容易に解くことができ、さらに式（５）を適用することにより、各ユーザｌの鍵生成情報ｄlを得ることができる。従って、本方式において鍵生成情報ｄlを生成するための計算の複雑性は著しく減じられるため、本方式はＭａｕｒｅｒ−Ｙａｃｏｂｉ方式に比べはるかに容易に実現できる。また、Ｍａｕｒｅｒ−Ｙａｃｏｂｉ方式におけるｄlの空間サイズは｜Ｌ｜であるが、本方式においては、｜Ｌ/αβ｜にすぎず、｜Ｌ｜よりもはるかに小さい（ここで、Ａのサイズは｜Ａ｜のように示す）。しかし、空間サイズ｜Ｌ/αβ｜は暗号通信に参加するユーザの最大数よりもはるかに大きいと思われるため、本方式を実現するためには十分な大きさである。
【００８０】
〔III〕実施例に対する変形例
以上、本発明の各実施例について説明したが、本発明の具体的な構成及び方法は、特許請求の範囲に記載した各発明の技術的思想の範囲内において、任意に改変及び改良することができる。以下、このような変形例について説明する。
【００８１】
（解決しようとする課題や発明の効果について）
まず、発明が解決しようとする課題や発明の効果は、前記した内容に限定されるものではなく、本発明によって、前記に記載されていない課題を解決したり、前記に記載されていない効果を奏することもでき、また、記載されている課題の一部のみを解決したり、記載されている効果の一部のみを奏することがある。例えば、本方式の実装性が従来技術の実装性よりわずかにでも向上している限りにおいて、本発明の課題は達成されている。
【００８２】
（制御について）
また、前記各実施例で自動的に行われるものとして説明した制御の全部又は任意の一部を手動で行っても良く、逆に、手動で行われるものとして説明した制御の全部又は任意の一部を公知技術又は上述した思想に基づいて自動化しても良い。また、制御部１３、２６内の各機能ブロックは、実際には、ＣＰＵ及びこのＣＰＵにて読み出され実行されるコンピュータプログラムとして構成することができ、あるいは、ハードワイヤードロジックにて構成することができる。あるいは、このプログラムをコンピュータ読み取り可能な任意の記憶媒体、例えば、ＣＲ−ＲＯＭ、ＤＶＤ、ＨＤ  ＤＶＤ、あるいは、ブルーディスクに記憶しておくことができる。また、上述した各電気的構成要素は機能概念的なものであり、必ずしも物理的に図示の如く構成されていることを要しない。すなわち、各部の分散・統合の具体的形態は図示のものに限られず、その全部又は一部を、各種の負荷や使用状況などに応じて、任意の単位で機能的又は物理的に分散・統合して構成することができる。この他、前記文書中や図面中で示した処理手順、又は、制御手順については、特記する場合を除いて任意に変更することができる。
【産業上の利用可能性】
【００８３】
以上のように、本発明に係る鍵生成情報作成装置及び鍵生成情報作成プログラムは、ＩＤ−ＮＩＫＳ方式において共通鍵を生成するための鍵生成情報を作成することに有用であり、特に、ＩＤ−ＮＩＫＳ方式の実装性を向上させることに適している。
【図面の簡単な説明】
【００８４】
【図１】本発明の実施の形態に係る暗号通信シシステムの全体構成を機能概念的に例示する図である。
【図２】図１のサーバの構成を機能概念的に例示するブロック図である。
【図３】図１の通信端末の構成を機能概念的に示すブロック図である。
【図４】暗号通信処理全体の概要を概念的に示す図である。
【図５】鍵生成情報作成処理のフローチャートである。
【符号の説明】
【００８５】
１０  サーバ
１１  データベース
１２  通信制御インターフェース
１３  制御部
１３ａ  素数選択部
１３ｂ  中間情報作成部
１３ｃ  鍵生成情報作成部
２０  通信端末
２１  記憶部
２２  入力部
２３  出力部
２４  入出力制御インターフェース
２５  通信制御インターフェース
２６  制御部
２６ａ  共通鍵作成部
２６ｂ  作業鍵作成部
２６ｃ  作業鍵暗号化部
２６ｄ  メッセージ暗号化部
２６ｅ  作業鍵復号化部
２６ｆ  メッセージ復号化部
３０  ネットワーク
【図１】
2006210968.tif 000030
【図２】
2006210968.tif 000031
【図３】
2006210968.tif 000032
【図４】
2006210968.tif 000033
【図５】
2006210968.tif 000034
【手続補正書】
【提出日】平成17年5月27日(2005.5.27)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
共通鍵暗号通信における共通鍵生成用の鍵生成情報を作成する鍵生成情報作成装置において、
鍵生成情報の作成指示の入力を受付ける入力受付手段と、
所定条件に合致するように選択された素数ｐ及びｑを格納する格納手段と、
前記入力受付手段にて鍵生成情報の作成指示の入力が受け付けられた場合に、
前記格納手段から前記素数ｐ及びｑを取得し、これら素数ｐ及びｑを用いて、
【数１】
2006210968.tif 000035
【数２】
2006210968.tif 000036
におけるｘｌ及びｙｌを算定する中間情報作成手段と（ここで、ｐ及びｑは所定条件に合致するものとして選択された素数、ｇは素数ｐ及びｑの両乗法群における原始元、ＩＤｌは各ユーザｌの個人情報番号、αはｐ−１の素因数、βはｑ−１の素因数）、
前記中間情報作成手段にて算定されたｘｌ及びｙｌを用いて、
【数３】
2006210968.tif 000037
から各ユーザｌの鍵生成情報ｄ１を算定する鍵生成情報作成手段と（ここで、Ｌ１＝Ｌ／（ｐ−１）＝Ｌ／αγ、Ｌ２＝Ｌ／（ｑ−１）＝Ｌ／βδ、Ｌ＝１ｃｍ{ｐ−１，ｑ−１}、p−１＝αγ、ｑ−１＝βδ、γ及びδは大きな素数を含まない数）、
前記鍵生成情報作成手段にて算定された前記鍵生成情報ｄ１を所定の出力先に出力する出力手段と、
を備えたことを特徴とする鍵生成情報作成装置。
【請求項２】
前記所定条件に合致する素数ｐ及びｑを選択する素数選択手段、
を備えたことを特徴とする請求項１に記載の鍵生成情報作成装置。
【請求項３】
共通鍵暗号通信における共通鍵生成用の鍵生成情報を作成する鍵生成情報作成方法をコンピュータに実行させるための鍵生成情報作成プログラムであって、前記コンピュータに、
鍵生成情報の作成指示の入力が当該コンピュータの所定の入力受付手段にて受け付けられたか否かを判断させる作成指示受付ステップと、
前記作成指示受付ステップにおいて前記作成指示受付の入力が受け付けられたと判断された場合に、当該コンピュータの所定の格納手段から、所定条件に合致するように予め選択された素数ｐ及びｑを取得させるステップと、
これら素数ｐ及びｑを用いて、当該コンピュータの所定の中間情報作成手段に、
【数４】
2006210968.tif 000038
【数５】
2006210968.tif 000039
におけるｘｌ及びｙｌを算定させる中間情報作成ステップと（ここで、ｐ及びｑは所定条件に合致するものとして選択された素数、ｇは素数ｐ及びｑの両乗法群における原始元、ＩＤｌは各ユーザｌの個人情報番号、αはｐ−１の素因数、βはｑ−１の素因数）、
前記中間情報取得ステップにおいて算定されたｘｌ及びｙｌを用いて、当該コンピュータの所定の鍵生成情報作成手段に、
【数６】
2006210968.tif 000040
から各ユーザｌの鍵生成情報ｄ１を算定させる鍵生成情報作成ステップと（ここで、Ｌ１＝Ｌ／（ｐ−１）＝Ｌ／αγ、Ｌ２＝Ｌ／（ｑ−１）＝Ｌ／βδ、Ｌ＝１ｃｍ{ｐ−１，ｑ−１}、p−１＝αγ、ｑ−１＝βδ、γ及びδは大きな素数を含まない）、
前記鍵生成情報作成ステップにおいて算定された前記鍵生成情報ｄ１を、当該コンピュータの所定の出力手段を介して所定の出力先に出力させる出力ステップと、
を実行させることを特徴とする鍵生成情報作成プログラム。
【請求項４】
さらに前記コンピュータの所定の素数選択手段に、前記所定条件に合致する素数ｐ及びｑを選択させること、
を特徴とする請求項３に記載の鍵生成情報作成プログラム。
【手続補正２】
【補正対象書類名】明細書
【補正対象項目名】００１４
【補正方法】変更
【補正の内容】
【００１４】
また、請求項３に記載の鍵生成情報作成プログラムは、共通鍵暗号通信における共通鍵生成用の鍵生成情報を作成する鍵生成情報作成方法をコンピュータに実行させるための鍵生成情報作成プログラムであって、前記コンピュータに、鍵生成情報の作成指示の入力が当該コンピュータの所定の入力受付手段にて受け付けられたか否かを判断させる作成指示受付ステップと、前記作成指示受付ステップにおいて前記作成指示受付の入力が受け付けられたと判断された場合に、当該コンピュータの所定の格納手段から、所定条件に合致するように予め選択された素数ｐ及びｑを取得させるステップと、これら素数ｐ及びｑを用いて、当該コンピュータの所定の中間情報作成手段に、
【数４】
2006210968.tif 000041
【数５】
2006210968.tif 000042
におけるｘｌ及びｙｌを算定させる中間情報作成ステップと（ここで、ｐ及びｑは所定条件に合致するものとして選択された素数、ｇは素数ｐ及びｑの両乗法群における原始元、ＩＤｌは各ユーザｌの個人情報番号、αはｐ−１の素因数、βはｑ−１の素因数）、前記中間情報取得ステップにおいて算定されたｘｌ及びｙｌを用いて、当該コンピュータの所定の鍵生成情報作成手段に、
【数６】
2006210968.tif 000043
から各ユーザｌの鍵生成情報ｄ１を算定させる鍵生成情報作成ステップと（ここで、Ｌ１＝Ｌ／（ｐ−１）＝Ｌ／αγ、Ｌ２＝Ｌ／（ｑ−１）＝Ｌ／βδ、Ｌ＝１ｃｍ{ｐ−１，ｑ−１}、p−１＝αγ、ｑ−１＝βδ、γ及びδは大きな素数を含まない）、前記鍵生成情報作成ステップにおいて算定された前記鍵生成情報ｄ１を、当該コンピュータの所定の出力手段を介して所定の出力先に出力させる出力ステップと実行させることを特徴とする。
【手続補正３】
【補正対象書類名】明細書
【補正対象項目名】００１５
【補正方法】変更
【補正の内容】
【００１５】
また、請求項４に記載の鍵生成情報作成プログラムは、請求項３に記載の鍵生成情報作成プログラムにおいて、さらに前記コンピュータの所定の素数選択手段に、前記所定条件に合致する素数ｐ及びｑを選択させることを特徴とする。
【手続補正４】
【補正対象書類名】明細書
【補正対象項目名】００４４
【補正方法】変更
【補正の内容】
【００４４】
その後、中間情報作成部１３ｂは、素数選択部１３ａにて選択された素数ｐ及びｑを用いて、以下の二つの式（１）及び（２）を、ｘｌ及びｙｌについて解く（ステップＳＢ−３。特許請求の範囲における中間情報作成ステップに対応する）。すなわち、離散対数問題を解く。ここで、ｎ＝ｐｑかつＬ＝１ｃｍ{ｐ−１，ｑ−１}と置き、ｇを、整数法であるｐ及びｑの両乗法群における原始元とする。また、ＩＤｌを、各ユーザｌの個人情報番号、α及びβはそれぞれｐ−１及びｑ−１の素因数である。ここで、式（１）及び（２）がすべてのＩＤlに対して一意の解ｘｌ及びｙｌを持つことは、離散対数問題の性質上明らかである。このように取得されたｘｌ及びｙｌはデータベース１１に格納される。
【手続補正書】
【提出日】平成18年4月28日(2006.4.28)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
メッセージの送信者Ａの通信端末と当該メッセージの受信者Ｂの通信端末とにネットワークを介して接続され、共通鍵暗号通信用の同一の共通鍵を前記送信者Ａの通信端末と前記受信者Ｂの通信端末とにおいて生成するための鍵生成情報を作成する鍵生成情報作成装置であって、
前記送信者Ａの通信端末又は前記受信者Ｂの通信端末から、前記ネットワークを介して、鍵生成情報の作成要求を受付ける入力受付手段と、
所定条件に合致するように選択された素数ｐ及びｑを格納する格納手段と、
前記入力受付手段にて鍵生成情報の作成要求が受け付けられた場合に、
前記格納手段から前記素数ｐ及びｑを取得し、これら素数ｐ及びｑを用いて、
【数１】
2006210968.tif 000044
【数２】
2006210968.tif 000045
におけるｘｌ及びｙｌを算定する中間情報作成手段と（ここで、ｐ及びｑは所定条件に合致するものとして選択された素数、ｇは素数ｐ及びｑの両乗法群における原始元、ｌは前記送信者Ａ又は前記受信者Ｂ、ＩＤｌは前記送信者Ａ又は前記受信者Ｂの個人情報番号、αはｐ−１の素因数、βはｑ−１の素因数）、
前記中間情報作成手段にて算定されたｘｌ及びｙｌを用いて、
【数３】
2006210968.tif 000046
から前記送信者Ａ又は前記受信者Ｂの鍵生成情報ｄｌを算定する鍵生成情報作成手段と（ここで、Ｌ１＝Ｌ／（ｐ−１）＝Ｌ／αγ、Ｌ２＝Ｌ／（ｑ−１）＝Ｌ／βδ、Ｌ＝１ｃｍ{ｐ−１，ｑ−１}、p−１＝αγ、ｑ−１＝βδ、γ及びδは大きな素数を含まない数、ｌは前記送信者Ａ又は前記受信者Ｂ）、
前記鍵生成情報作成手段にて算定された前記鍵生成情報ｄｌを、前記ネットワークを介して、前記送信者Ａの通信端末及び前記受信者Ｂの通信端末に送信する出力手段と、
を備えたことを特徴とする鍵生成情報作成装置。
【請求項２】
前記所定条件に合致する素数ｐ及びｑを選択する素数選択手段、
を備えたことを特徴とする請求項１に記載の鍵生成情報作成装置。
【請求項３】
メッセージの送信者Ａの通信端末と当該メッセージの受信者Ｂの通信端末とにネットワークを介して接続されたコンピュータに、共通鍵暗号通信用の同一の共通鍵を前記送信者Ａの通信端末と前記受信者Ｂの通信端末とにおいて生成するための鍵生成情報を作成させる鍵生成情報作成プログラムであって、
前記送信者Ａの通信端末又は前記受信者Ｂの通信端末から、前記ネットワークを介して、鍵生成情報の作成要求を受付ける処理と、
前記鍵生成情報の作成要求が受け付けられた場合に、
所定条件に合致するように選択されて当該コンピュータの格納手段に格納された素数ｐ及びｑを、当該格納手段から取得する処理と、
これら素数ｐ及びｑを用いて、
【数４】
2006210968.tif 000047
【数５】
2006210968.tif 000048
におけるｘｌ及びｙｌを算定する処理と（ここで、ｐ及びｑは所定条件に合致するものとして選択された素数、ｇは素数ｐ及びｑの両乗法群における原始元、ｌは前記送信者Ａ又は前記受信者Ｂ、ＩＤｌは前記送信者Ａ又は前記受信者Ｂの個人情報番号、αはｐ−１の素因数、βはｑ−１の素因数）、
前記算定されたｘｌ及びｙｌを用いて、
【数６】
2006210968.tif 000049
から前記送信者Ａ又は前記受信者Ｂの鍵生成情報ｄｌを算定する処理と（ここで、Ｌ１＝Ｌ／（ｐ−１）＝Ｌ／αγ、Ｌ２＝Ｌ／（ｑ−１）＝Ｌ／βδ、Ｌ＝１ｃｍ{ｐ−１，ｑ−１}、p−１＝αγ、ｑ−１＝βδ、γ及びδは大きな素数を含まない数、ｌは前記送信者Ａ又は前記受信者Ｂ）、
前記算定された前記鍵生成情報ｄｌを、前記ネットワークを介して、前記送信者Ａの通信端末及び前記受信者Ｂの通信端末に送信する処理と、
を実行させることを特徴とする鍵生成情報作成プログラム。
【請求項４】
さらに前記コンピュータに、前記所定条件に合致する素数ｐ及びｑを選択する処理、
を実行させることを特徴とする請求項３に記載の鍵生成情報作成プログラム。
【手続補正２】
【補正対象書類名】明細書
【補正対象項目名】００１２
【補正方法】変更
【補正の内容】
【００１２】
上述した課題を解決し、目的を達成するために、請求項１に記載の鍵生成情報作成装置は、メッセージの送信者Ａの通信端末と当該メッセージの受信者Ｂの通信端末とにネットワークを介して接続され、共通鍵暗号通信用の同一の共通鍵を前記送信者Ａの通信端末と前記受信者Ｂの通信端末とにおいて生成するための鍵生成情報を作成する鍵生成情報作成装置であって、前記送信者Ａの通信端末又は前記受信者Ｂの通信端末から、前記ネットワークを介して、鍵生成情報の作成要求を受付ける入力受付手段と、所定条件に合致するように選択された素数ｐ及びｑを格納する格納手段と、前記入力受付手段にて鍵生成情報の作成要求が受け付けられた場合に、前記格納手段から前記素数ｐ及びｑを取得し、これら素数ｐ及びｑを用いて、
【数１】
2006210968.tif 000050
【数２】
2006210968.tif 000051
におけるｘｌ及びｙｌを算定する中間情報作成手段と（ここで、ｐ及びｑは所定条件に合致するものとして選択された素数、ｇは素数ｐ及びｑの両乗法群における原始元、ｌは前記送信者Ａ又は前記受信者Ｂ、ＩＤｌは前記送信者Ａ又は前記受信者Ｂの個人情報番号、αはｐ−１の素因数、βはｑ−１の素因数）、前記中間情報作成手段にて算定されたｘｌ及びｙｌを用いて、
【数３】
2006210968.tif 000052
から前記送信者Ａ又は前記受信者Ｂの鍵生成情報ｄｌを算定する鍵生成情報作成手段と（ここで、Ｌ１＝Ｌ／（ｐ−１）＝Ｌ／αγ、Ｌ２＝Ｌ／（ｑ−１）＝Ｌ／βδ、Ｌ＝１ｃｍ{ｐ−１，ｑ−１}、p−１＝αγ、ｑ−１＝βδ、γ及びδは大きな素数を含まない数、ｌは前記送信者Ａ又は前記受信者Ｂ）、前記鍵生成情報作成手段にて算定された前記鍵生成情報ｄｌを、前記ネットワークを介して、前記送信者Ａの通信端末及び前記受信者Ｂの通信端末に送信する出力手段とを備えたことを特徴とする。
【手続補正３】
【補正対象書類名】明細書
【補正対象項目名】００１３
【補正方法】変更
【補正の内容】
【００１３】
また、請求項２に記載の鍵生成情報作成装置は、請求項１に記載の鍵生成情報作成装置において、前記所定条件に合致する素数ｐ及びｑを選択する素数選択手段を備えたことを特徴とする。
【手続補正４】
【補正対象書類名】明細書
【補正対象項目名】００１４
【補正方法】変更
【補正の内容】
【００１４】
また、請求項３に記載の鍵生成情報作成プログラムは、メッセージの送信者Ａの通信端末と当該メッセージの受信者Ｂの通信端末とにネットワークを介して接続されたコンピュータに、共通鍵暗号通信用の同一の共通鍵を前記送信者Ａの通信端末と前記受信者Ｂの通信端末とにおいて生成するための鍵生成情報を作成させる鍵生成情報作成プログラムであって、前記送信者Ａの通信端末又は前記受信者Ｂの通信端末から、前記ネットワークを介して、鍵生成情報の作成要求を受付ける処理と、前記鍵生成情報の作成要求が受け付けられた場合に、所定条件に合致するように選択されて当該コンピュータの格納手段に格納された素数ｐ及びｑを、当該格納手段から取得する処理と、これら素数ｐ及びｑを用いて、
【数４】
2006210968.tif 000053
【数５】
2006210968.tif 000054
におけるｘｌ及びｙｌを算定する処理と（ここで、ｐ及びｑは所定条件に合致するものとして選択された素数、ｇは素数ｐ及びｑの両乗法群における原始元、ｌは前記送信者Ａ又は前記受信者Ｂ、ＩＤｌは前記送信者Ａ又は前記受信者Ｂの個人情報番号、αはｐ−１の素因数、βはｑ−１の素因数）、前記算定されたｘｌ及びｙｌを用いて、
【数６】
2006210968.tif 000055
から前記送信者Ａ又は前記受信者Ｂの鍵生成情報ｄｌを算定する処理と（ここで、Ｌ１＝Ｌ／（ｐ−１）＝Ｌ／αγ、Ｌ２＝Ｌ／（ｑ−１）＝Ｌ／βδ、Ｌ＝１ｃｍ{ｐ−１，ｑ−１}、p−１＝αγ、ｑ−１＝βδ、γ及びδは大きな素数を含まない数、ｌは前記送信者Ａ又は前記受信者Ｂ）、前記算定された前記鍵生成情報ｄｌを、前記ネットワークを介して、前記送信者Ａの通信端末及び前記受信者Ｂの通信端末に送信する処理とを実行させることを特徴とする。
【手続補正５】
【補正対象書類名】明細書
【補正対象項目名】００１５
【補正方法】変更
【補正の内容】
【００１５】
また、請求項４に記載の鍵生成情報作成プログラムは、請求項３に記載の鍵生成情報作成プログラムにおいて、さらに前記コンピュータに、前記所定条件に合致する素数ｐ及びｑを選択する処理を実行させることを特徴とする。