(57)【特許請求の範囲】
【請求項１】
暗号化装置と復号化装置とが同一の共通鍵を用いて通信データの暗号化および復号化を行う暗号通信システムにおいて、
各利用者が共通に使用する公開情報を保持する保持部と、前記各利用者が公開鍵を入力すると該公開鍵に対し秘密鍵を生成する秘密鍵生成部とを有する鍵生成センタと、
前記利用者の自己の秘密鍵と通信相手となる利用者の公開鍵及び前記公開情報に基づいてこれら各利用者に共通の共通鍵を生成する共通鍵生成部を有する共通鍵生成装置とを備える暗号通信システムにおいて、
前記秘密鍵生成部は前記公開情報に含まれる値をＮ，内部保持パラメータをＧ，δとすると、次式（１）の演算を行って秘密鍵を生成することを特徴とする暗号通信システム。
任意のｋ＞０に対して、
Ｇ＾（δ＋ｋ）≡Ｇ＾ｋ（ｍｏｄ．Ｎ）      …（１）
ただし、＾はべき乗演算を表し、ａ≡ｂ（ｍｏｄ．ｑ）はａとｂがｑを法として合同であることを表す。
【請求項２】
請求項１において、
前記秘密鍵生成部または前記共通鍵生成部は、前記公開情報Ｎを法とする剰余演算を含む処理を行うことを特徴とする暗号通信システム。
【請求項３】
請求項１において、
前記秘密鍵生成部は、前記パラメータＧをべき乗する演算を含む処理を行うことを特徴とする暗号通信システム。
【請求項４】
請求項３において、
前記秘密鍵生成部は、前記パラメータＧのべき乗演算として、当該Ｇのべき乗演算に用いる指数部の演算を、法δによる剰余のもとで行うことを特徴とする暗号通信システム。
【請求項５】
請求項１において、
前記秘密鍵生成部は、前記パラメータδの倍数を法とする剰余演算を含む演算を、前記秘密鍵の生成に用いることを特徴とする暗号通信システム。
【請求項６】
請求項１において、
前記秘密鍵生成部、前記パラメータδの任意の倍数を用いて、前記公開情報の生成を行うことを特徴とする暗号通信システム。
【請求項７】
請求項１において、
前記秘密鍵生成部は、前記パラメータδの任意の倍数を前記公開情報に含めることを特徴とする暗号通信システム。
【請求項８】
請求項１において、
前記秘密鍵生成部は、前記パラメータδの任意の倍数を法とする剰余演算を含む処理を、前記共通鍵の生成に用いることを特徴とする暗号通信システム。
【請求項９】
請求項１，２または３のいずれかにおいて、
前記秘密鍵生成部は、利用者Ａの公開鍵Ｘ（Ａ）に対する秘密鍵Ｙ（Ａ）として、式（６）または式（７）の演算により生成したＧｆ  （Ａ）またはＧｈ  （Ａ）の演算結果を含む情報を生成することを特徴とする暗号通信システム。
Ｇｆ （Ａ）＝Ｇ＾｛ｘ＾Ｆ（Ｘ（Ａ））＋ｙ＾Ｈ（Ｘ（Ａ））｝（ｍｏｄ．Ｎ）      …（６）
Ｇｈ （Ａ）＝Ｇ＾｛ｙ＾Ｆ（Ｘ（Ａ））＋ｚ＾Ｈ（Ｘ（Ａ））｝（ｍｏｄ．Ｎ）      …（７）
ただし、Ｆ、Ｈは公開鍵Ｘ（Ａ）に対する所定の関数である。
【請求項１０】
請求項９において、
前記秘密鍵生成部は、利用者Ａの公開鍵Ｘ（Ａ）に対して、式（６）および式（７）の演算により生成したＧｆ  （Ａ）とＧｈ  （Ａ）の組を、秘密鍵Ｙ（Ａ）＝（Ｇｆ  （Ａ），Ｇｈ  （Ａ））として生成することを特徴とする暗号通信システム。
【請求項１１】
請求項９において、
前記秘密鍵生成部は、式（６）または式（７）における関数ＦまたはＨとして、次式（８）または式（９）の関数を用いることを特徴とする暗号通信システム。
Ｆ（Ｘ）＝Σｉ ｛ｒｉ ｆｉ （Ｘ）｝      …（８）
Ｈ（Ｘ）＝Σｉ ｛ｔｉ ｈｉ （Ｘ）｝      …（９）
ただし、Σｉ はｉ＝０からｍ−１までの和を表す。
ここで、ｆｉ （Ｘ），ｈｉ （Ｘ）（０≦ｉ＜ｍ）は、公開鍵Ｘに対して出力されるそれぞれｍ個の出力である。
それぞれｍ個のｒｉ ｔｉ （０≦ｉ＜ｍ）は任意である。
【請求項１２】
暗号化装置と復号化装置とが同一の共通鍵を用いて通信データの暗号化および復号化を行う暗号通信システムにおいて、
各利用者が共通に使用する公開情報を保持する保持部と、前記各利用者が公開鍵を入力すると該公開鍵に対し秘密鍵を生成する秘密鍵生成部とを有する鍵生成センタと、
前記利用者の自己の秘密鍵と通信相手となる利用者の公開鍵及び前記公開情報に基づいてこれら各利用者に共通の共通鍵を生成する共通鍵生成部を有する共通鍵生成装置とを備える暗号通信システムにおいて、
前記秘密鍵生成部は、任意の値であるδに対して、式（２）または式（３）の関係を満たす二つの値ｘとｙまたはｙとｚを用いた演算を、前記秘密鍵の生成に用いることを特著とする暗号通信システム。
ｘｙ≡０（ｍｏｄ．δ）      …（２）
ｙｚ≡０（ｍｏｄ．δ）      …（３）
【請求項１３】
請求項１２において、
前記秘密鍵生成部は、ｘとｙまたはｙとｚに対して、（ｘ＋ｙ）の任意のべき乗または（ｙ＋ｚ）の任意のべき乗を含む演算を前記公開情報の生成に用いることを特徴とする暗号通信システム。
【請求項１４】
請求項１２において、
前記秘密鍵生成部は、（ｘ＋ｙ）の任意のべき乗、または（ｙ＋ｚ）の任意のべき乗を含む項をδの任意の倍数を含む項を加算する演算を含む処理を公開情報の生成に用いることを特徴とする暗号通信システム。
【請求項１５】
請求項１４において、
前記秘密鍵生成部は、式（４）または式（５）に示す演算で得られるｅｉ  またはｄｉ  を公開情報に含めることを特徴とする暗号通信システム。
ｅｉ ＝（ｘ＋ｙ）＾ｒｉ ＋ｓｉ δ（ｍｏｄ．Ｍ）      …（４）
ｄｉ ＝（ｙ＋ｚ）＾ｔｉ ＋ｕｉ δ（ｍｏｄ．Ｍ）      …（５）
ただし、Ｍはδの任意の倍数である。
また、ｒｉ ，ｓｉ ，ｔｉ ，ｕｉ は、任意の数である。
【請求項１６】
請求項１５において、
前記秘密鍵生成部は、次式（８）または式（９）の演算で用いるｍ個のｒｉ（０≦ｉ＜ｍ）またはｔｉ （０≦ｉ＜ｍ）を用いて、式（４）または式（５）の計算で得られるｍ個のｅｉ （０≦ｉ＜ｍ）またはｄｉ （０≦ｉ＜ｍ）を、公開情報に含めることを特徴とする暗号通信システム。
Ｆ（Ｘ）＝Σｉ ｛ｒｉ ｆｉ （Ｘ）｝      …（８）
Ｈ（Ｘ）＝Σｉ ｛ｔｉ ｈｉ （Ｘ）｝      …（９）
ただし、Σｉ はｉ＝０からｍ−１までの和を表す。
ここで、ｆｉ （Ｘ），ｈｉ （Ｘ）（０≦ｉ＜ｍ）は、公開鍵Ｘに対して出力されるそれぞれｍ個の出力である。
それぞれｍ個のｒｉ ｔｉ （０≦ｉ＜ｍ）は任意である。
【請求項１７】
請求項１２において、
前記秘密鍵生成部は、ｘとｙまたはｙとｚをべき乗する演算を含む処理を行うことを特徴とする暗号通信システム。
【請求項１８】
請求項１７において、
前記秘密鍵生成部は、ｘとｙまたはｙとｚを、それぞれべき乗して得られた結果を含む項を加算する演算を含む処理を行うことを特徴とする暗号通信システム。
【請求項１９】
請求項１２において、
前記秘密鍵生成部は、δの倍数を法とする剰余演算を含む演算を、前記秘密鍵の生成または公開情報の生成に用いることを特徴とする暗号通信システム。
【請求項２０】
請求項１２において、
前記秘密鍵生成部は、δの任意の倍数を用いて、公開情報の生成を行うことを特徴とする暗号通信システム。
【請求項２１】
請求項１２において、
前記秘密鍵生成部は、δの任意の倍数を公開情報に含めて出力することを特徴とする暗号通信システム。
【請求項２２】
請求項１２において、
前記共通鍵生成部は、δの任意の倍数を法とする剰余演算を含む処理を、共通の生成に用いることを特徴とする暗号通信システム。
【請求項２３】
請求項１２において、
前記秘密鍵生成部は、利用者Ａの公開鍵Ｘ（Ａ）に対する秘密鍵Ｙ（Ａ）として、式（６）または式（７）の演算により生成したＧｆ  （Ａ）またはＧｈ  （Ａ）の演算結果を含む情報を生成することを特徴とする暗号通信システム。
Ｇｆ （Ａ）＝Ｇ＾｛ｘ＾Ｆ（Ｘ（Ａ））＋ｙ＾Ｈ（Ｘ（Ａ））｝（ｍｏｄ．Ｎ）      …（６）
Ｇｈ （Ａ）＝Ｇ＾｛ｙ＾Ｆ（Ｘ（Ａ））＋ｚ＾Ｈ（Ｘ（Ａ））｝（ｍｏｄ．Ｎ）      …（７）
ただし、Ｆ、Ｈは公開鍵Ｘ（Ａ）に対する所定の関数である。
【請求項２４】
請求項２３において、
前記秘密鍵生成部は、利用者Ａの公開鍵Ｘ（Ａ）に対して、式（６）および式（７）の演算により生成したＧｆ  （Ａ）とＧｈ  （Ａ）の組を、秘密鍵Ｙ（Ａ）＝（Ｇｆ  （Ａ），Ｇｈ  （Ａ））として生成することを特徴とする暗号通信システム。
【請求項２５】
請求項２３において、
前記秘密鍵生成部は、式（６）または式（７）における関数ＦまたはＨとして、次式（８）または式（９）の関数を用いることを特徴とする暗号通信システム。
Ｆ（Ｘ）＝Σｉ ｛ｒｉ ｆｉ （Ｘ）｝      …（８）
Ｈ（Ｘ）＝Σｉ ｛ｔｉ ｈｉ （Ｘ）｝      …（９）
ただし、Σｉ はｉ＝０からｍ−１までの和を表す。
ここで、ｆｉ （Ｘ），ｈｉ （Ｘ）（０≦ｉ＜ｍ）は、公開鍵Ｘに対して出力されるそれぞれｍ個の出力である。
それぞれｍ個のｒｉ ｔｉ （０≦ｉ＜ｍ）は任意である。
【請求項２６】
暗号化装置と復号化装置とが同一の共通鍵を用いて通信データの暗号化および復号化を行う暗号通信システムにおいて、
各利用者が共通に使用する公開情報を保持する保持部と、前記各利用者が公開鍵を入力すると該公開鍵に対し秘密鍵を生成する秘密鍵生成部とを有する鍵生成センタと、
前記利用者の自己の秘密鍵と通信相手となる利用者の公開鍵及び前記公開情報に基づいてこれら各利用者に共通の共通鍵を生成する共通鍵生成部を有する共通鍵生成装置とを備える暗号通信システムにおいて、
前記秘密鍵生成部または共通鍵生成部は、入力される利用者Ａの公開鍵Ｘ（Ａ）または公開鍵Ｘ（Ａ）に基づいて演算した結果から、所定の値であるｍ個の出力を得る処理手段を備え、
前記秘密鍵生成部は、ある公開鍵Ｘに対して出力されるｍ個の出力を、ｆｉ  （Ｘ）（０≦ｉ＜ｍ）またはｈｉ  （Ｘ）（０≦ｉ＜ｍ）として、これらｆｉ  （Ｘ）またはｈｉ  （Ｘ）を用いた式（８）または式（９）のような関数ＦまたはＨを用いることを特徴とする暗号通信システム。
Ｆ（Ｘ）＝Σｉ ｛ｒｉ ｆｉ （Ｘ）｝      …（８）
Ｈ（Ｘ）＝Σｉ ｛ｔｉ ｈｉ （Ｘ）｝      …（９）
ただし、Σｉ はｉ＝０からｍ−１までの和を表す。
ここで、ｆｉ （Ｘ），ｈｉ （Ｘ）（０≦ｉ＜ｍ）は、公開鍵Ｘに対して出力されるそれぞれｍ個の出力である。
それぞれｍ個のｒｉ ｔｉ （０≦ｉ＜ｍ）は任意である。
【請求項２７】
暗号化装置と復号化装置とが同一の共通鍵を用いて通信データの暗号化および復号化を行う暗号通信システムにおいて、
各利用者が共通に使用する公開情報を保持する保持部と、前記各利用者が公開鍵を入力すると該公開鍵に対し秘密鍵を生成する秘密鍵生成部とを有する鍵生成センタと、
前記利用者の自己の秘密鍵と通信相手となる利用者の公開鍵及び前記公開情報に基づいてこれら各利用者に共通の共通鍵を生成する共通鍵生成部を有する共通鍵生成装置とを備える暗号通信システムにおいて、
前記秘密鍵生成部または共通鍵生成部は、入力される利用者Ａの公開鍵Ｘ（Ａ）または公開鍵Ｘ（Ａ）に基づいて演算した結果から、所定の値であるｍ個の出力を得る処理手段を備え、
前記共通鍵生成部は、前記共通鍵生成装置を持つ利用者Ａの秘密鍵Ｙ（Ａ）に含まれる二つの部分情報Ｇｆ  （Ａ）とＧｈ  （Ａ）および公開情報に含まれているそれぞれｍ個のｅｉ  ，ｄｉ  （０≦ｉ＜ｍ）と、利用者Ａの通信相手となる利用者Ｂの公開鍵Ｘ（Ｂ）に対して、それぞれｍ個の出力ｆｉ  （Ｘ（Ｂ）），ｈｉ  （Ｘ（Ｂ））（０≦ｉ＜ｍ）を得る処理とを用いて次式（１０）の演算により、共通鍵Ｋ（Ａ，Ｂ）を生成することを特徴とする暗号通信システム。
Ｋ（Ａ，Ｂ）＝Ｇｆ （Ａ）＾｛Πｉ ［ｅｉ ＾ｆｉ （Ｘ（Ｂ））］｝・Ｇｈ （Ａ）＾｛Πｉ ［ｄｉ ＾ｈｉ （Ｘ（Ｂ））］｝（ｍｏｄ．Ｎ）      …（１０）
ただし、Πｉ はｉ＝０からｍ−１までの積を表す。
ここで、Ｇｆ （Ａ），Ｇｈ （Ａ）は、秘密鍵Ｙ（Ａ）に含まれる二つの部分情報、ｆｉ （Ｘ（Ｂ）），ｈｉ （Ｘ（Ｂ））（０≦ｉ＜ｍ）は、公開鍵Ｘ（Ｂ）に対するそれぞれｍ個の出力である。
【請求項２８】
請求項２７において、
前記共通鍵生成部は、式（１０）におけるＧｆ  （Ａ）またはＧｈ  （Ａ）のべき乗演算の指数部での積を法Ｎの剰余のもとでのべき乗の繰り返しにより計算することを特徴とする暗号通信システム。
【請求項２９】
請求項２８において、
前記共通鍵生成部は、式（１０）におけるｆｉ （Ｘ（Ｂ））またはｈｉ （Ｘ（Ｂ））の出力が０であった場合に、ｅｉ  ＾ｆｉ（Ｘ（Ｂ））またはｄｉ  ＾ｈｉ （Ｘ（Ｂ））を指数とするべき乗処理を省略することを特徴とする暗号通信システム。
【請求項３０】
請求項２９において、
前記共通鍵生成部は、式（１０）におけるｆｉ （Ｘ（Ｂ））またはｈｉ （Ｘ（Ｂ））の出力を、０または１の２値出力とし、ｅｉ  ＾ｆｉ（Ｘ（Ｂ））またはｄｉ  ＾ｈｉ （Ｘ（Ｂ））を指数とするべき乗処理を、前記出力値が０のときはべき乗処理を省略し、前記出力値が１のときはｅｉ  またはｄｉ  によるべき乗処理として行うことを特徴とする暗号通信システム。
【請求項３１】
暗号化装置と復号化装置とが同一の共通鍵を用いて通信データの暗号化および復号化を行う暗号通信システムにおいて、
各利用者が共通に使用する公開情報を保持する保持部と、前記各利用者が公開鍵を入力すると該公開鍵に対し秘密鍵を生成する秘密鍵生成部とを有する鍵生成センタと、
前記利用者の自己の秘密鍵と通信相手となる利用者の公開鍵及び前記公開情報に基づいてこれら各利用者に共通の共通鍵を生成する共通鍵生成部を有する共通鍵生成装置とを備える暗号通信システムにおいて、
前記秘密鍵生成部は、次式（１）の関係を示すＮと、次式（４）、（５）の演算結果として得られるそれぞれｍ個のｅｉ  ，ｄｉ  （０≦ｉ＜ｍ）を公開情報に含めて出力し、かつ、任意の利用者Ａの公開鍵Ｘ（Ａ）に対する秘密鍵Ｙ（Ａ）＝（Ｇｆ  （Ａ），Ｇｈ  （Ａ））を、次式（６），（７）の演算より生成し、
前記共通鍵生成部は、前記利用者Ａの秘密鍵Ｙ（Ａ）と、当該利用者の通信相手となる利用者Ｂの公開鍵Ｘ（Ｂ）を用いて、次式（１０）の演算により共通鍵Ｋ（Ａ，Ｂ）を生成することを特徴とする暗号通信システム。
任意のｋ＞０に対して、
Ｇ＾（δ＋ｋ）≡Ｇ＾ｋ（ｍｏｄ．Ｎ）      …（１）
ただし、＾はべき乗演算を表し、ａ≡ｂ（ｍｏｄ．ｑ）はａとｂがｑを法として合同であることを表す。
ｅｉ ＝（ｘ＋ｙ）＾ｒｉ ＋ｓｉ δ（ｍｏｄ．Ｍ）      …（４）
ｄｉ ＝（ｙ＋ｚ）＾ｔｉ ＋ｕｉ δ（ｍｏｄ．Ｍ）      …（５）
ただし、Ｍはδの任意の倍数である。
また、ｒｉ ，ｓｉ ，ｔｉ ，ｕｉ は、任意の数である。
Ｇｆ （Ａ）＝Ｇ＾｛ｘ＾Ｆ（Ｘ（Ａ））＋ｙ＾Ｈ（Ｘ（Ａ））｝（ｍｏｄ．Ｎ）      …（６）
Ｇｈ （Ａ）＝Ｇ＾｛ｙ＾Ｆ（Ｘ（Ａ））＋ｚ＾Ｈ（Ｘ（Ａ））｝（ｍｏｄ．Ｎ）      …（７）
ただし、式（４），（５），（６），（７）におけるｘ，ｙ，ｚは次式（２），（３）の関係を満たす。
ｘｙ≡０（ｍｏｄ．δ）      …（２）
ｙｚ≡０（ｍｏｄ．δ）      …（３）
また、Ｆ，Ｈは、ある公開鍵Ｘに対して次式（８），（９）のような関数である。
Ｆ（Ｘ）＝Σｉ ｛ｒｉ ｆｉ （Ｘ）｝      …（８）
Ｈ（Ｘ）＝Σｉ ｛ｔｉ ｈｉ （Ｘ）｝      …（９）
ただし、Σｉ  はｉ＝０からｍ−１までの和を表す。
ここで、ｆｉ  （Ｘ），ｈｉ  （Ｘ）（０≦ｉ＜ｍ）は、公開鍵Ｘに対して出力されるそれぞれｍ個の出力である。
Ｋ（Ａ，Ｂ）＝Ｇｆ （Ａ）＾｛Πｉ ［ｅｉ ＾ｆｉ （Ｘ（Ｂ））］｝・Ｇｈ （Ａ）＾｛Πｉ ［ｄｉ ＾ｈｉ （Ｘ（Ｂ））］｝（ｍｏｄ．Ｎ）      …（１０）
ただし、Πｉ はｉ＝０からｍ−１までの積を表す。
ここで、Ｇｆ （Ａ），Ｇｈ （Ａ）は、秘密鍵Ｙ（Ａ）に含まれる二つの部分情報、ｆｉ （Ｘ（Ｂ）），ｈｉ （Ｘ（Ｂ））（０≦ｉ＜ｍ）は、公開鍵Ｘ（Ｂ）に対するそれぞれｍ個の出力である。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、利用者間で暗号鍵を共有して暗号通信を行う暗号通信システムに関する。
【０００２】
【従来の技術】
この種の暗号通信システムの従来の技術としては、次の文献に示されるものがある。
Ｗ．Ｄｉｆｆｉｅ，  Ｍ．Ｅ．  Ｈｅｌｌｍａｎ，  “Ｎｅｗ  Ｄｉｒｅｃｔｉｏｎｓ  ｉｎ  Ｃｒｙｐｔｏｇｒａｐｈｙ”，  ＩＥＥＥ  Ｔｒａｎｓ．  ｏｎ  Ｉｎｆｏ．  Ｔｈｅｏｒｙ，  Ｖｏｌ．  ＩＴ−２２，  Ｎｏ．６，  Ｎｏｖ．  １９７６
【０００３】
図２は、上記文献に示された暗号通信システムの説明図である。
図は利用者Ａと利用者Ｂが、暗号通信を行う際に共通に利用する共通鍵Ｋ（Ａ，Ｂ）＝Ｋ（Ｂ，Ａ）を生成する手順を説明している。
【０００４】
先ず、利用者Ａは利用者Ａの秘密鍵Ｙ（Ａ）を第１の鍵生成装置２０１−Ａに入力する。第１の鍵生成装置２０１−Ａは、利用者Ａの公開鍵Ｘ（Ａ）＝ｇ＾Ｙ（Ａ）（ｍｏｄ．ｑ）を生成し、通信路２０３を介して通信相手である利用者Ｂに送信する。
【０００５】
同様に、利用者Ｂは第１の鍵生成装置２０１−Ｂで利用者Ｂの秘密鍵Ｙ（Ｂ）から公開鍵Ｘ（Ｂ）を計算し、この公開鍵Ｘ（Ｂ）を利用者Ａに送信する。利用者Ａは、利用者Ａが秘密に保管する秘密鍵Ｙ（Ａ）と、通信路２０３を介して利用者Ｂから受け取った利用者Ｂの公開鍵Ｘ（Ｂ）とを第２の鍵生成装置２０２−Ａに入力する。第２の鍵生成装置２０２−Ａは、Ｋ（Ａ，Ｂ）＝Ｘ（Ｂ）＾Ｙ（Ａ）（ｍｏｄ．ｑ）＝ｇ＾｛Ｙ（Ｂ）Ｙ（Ａ）｝（ｍｏｄ．ｑ）を生成する。同様に、利用者Ｂ側でも、第２の鍵生成装置２０２−Ｂが、Ｋ（Ｂ，Ａ）＝Ｘ（Ａ）＾Ｙ（Ｂ）（ｍｏｄ．ｑ）＝ｇ＾｛Ｙ（Ａ）Ｙ（Ｂ）｝（ｍｏｄ．ｑ）を生成する。
【０００６】
以上の方法で、利用者Ａと利用者Ｂは第三者が盗聴可能な通信路２０３を介して秘密に共通鍵Ｋ（Ｂ，Ａ）＝Ｋ（Ａ，Ｂ）を共有でき、この秘密鍵を用いてデータの暗号化／復号化が可能となる。
【０００７】
【発明が解決しようとする課題】
しかしながら、上記従来の暗号通信システムはこのように構成されているため、第３の利用者Ｃが容易に利用者Ａや利用者Ｂになりすまし、不正に鍵を共有できてしまうという問題点があった。また、従来の暗号通信システムでは、鍵共有の際に相手局との予備通信が必要であり、電子メール等の一方向の郵便型通信には適用できないという問題点もあった。
【０００８】
このような点から、第３の利用者によるなりすましを防ぐと同時に、鍵共有時に相手局との予備通信を必要としない暗号通信システムを実現することが望まれていた。
【０００９】
【課題を解決するための手段】
本発明は以上の点を解決するため次の構成を採用する。
〈請求項１の構成〉
暗号化装置と復号化装置とが同一の共通鍵を用いて通信データの暗号化および復号化を行う暗号通信システムにおいて、各利用者が共通に使用する公開情報を保持する保持部と、前記各利用者が公開鍵を入力すると該公開鍵に対し秘密鍵を生成する秘密鍵生成部とを有する鍵生成センタと、前記利用者の自己の秘密鍵と通信相手となる利用者の公開鍵及び前記公開情報に基づいてこれら各利用者に共通の共通鍵を生成する共通鍵生成部を有する共通鍵生成装置とを備える暗号通信システムにおいて、前記秘密鍵生成部は前記公開情報に含まれる値をＮ，内部保持パラメータをＧ，δとすると、次式（１）の演算を行って秘密鍵を生成することを特徴とする暗号通信システム。任意のｋ＞０に対して、
Ｇ＾（δ＋ｋ）≡Ｇ＾ｋ（ｍｏｄ．Ｎ）      …（１）
ただし、＾はべき乗演算を表し、ａ≡ｂ（ｍｏｄ．ｑ）はａとｂがｑを法として合同であることを表す。
【００１０】
〈請求項１の説明〉
鍵生成センタの秘密鍵生成部の生成する秘密鍵Ｙ（Ａ）と公開情報は、共通鍵生成部において、利用者Ａ（または利用者Ｂ）の秘密鍵Ｙ（Ａ）（または秘密鍵Ｙ（Ｂ））と、この利用者Ａ（または利用者Ｂ）の通信相手となる利用者Ｂ（利用者Ａ）の公開鍵Ｘ（Ｂ）（またはＸ（Ａ））と、公開情報とから、これら利用者Ａと利用者Ｂの間の共通鍵Ｋ（Ａ，Ｂ）（またはＫ（Ｂ，Ａ））を生成するよう構成されていれば、どんな値であってもよい。また、鍵生成センタの構成についても、利用者Ａ、Ｂに対してこれらの秘密鍵Ｙ（Ａ）やＹ（Ｂ）を出力できるものであれば、どんなものであってもよい。
【００１１】
請求項１の発明は上記のように構成されているため、共通鍵の生成に対しては相手との通信を行う必要がなく、従って、第３の利用者によるなりすましを防止することができると共に、鍵共有時に相手との予備通信を必要としないことから、電子メール等の一方向の郵便型通信にも適用できるという効果が得られる。
【００１３】
請求項１の発明は、上記のようなＮ、Ｇ、δの関係を示している。このような関係を持っているため、暗号通信システムの種々の処理において、以下のような性質を利用した演算が使用できる。
ａ≡ｂ（ｍｏｄ．δ）を満たす任意のａ，ｂ＞０において、
Ｇ＾ａ≡Ｇ＾ｂ（ｍｏｄ．Ｎ）
【００１４】
〈請求項２の構成〉
請求項１において、前記秘密鍵生成部または前記共通鍵生成部は、前記公開情報Ｎを法とする剰余演算を含む処理を行うことを特徴とする暗号通信システム。
【００１５】
〈請求項２の説明〉
請求項３は、式（１）の関係を満たすＮによって、何らかの値を除算した余りを求める処理を含むことを示す発明である。
【００１６】
〈請求項３の構成〉
請求項１において、前記秘密鍵生成部は、前記パラメータＧをべき乗する演算を含む処理を行うことを特徴とする暗号通信システム。
【００１７】
〈請求項３の説明〉
請求項３は、式（１）の関係を満たすＧに対して、このＧをべき乗する演算を行うことを示す発明である。
【００２４】
〈請求項４の構成〉
請求項３において、前記秘密鍵生成部は、前記パラメータＧのべき乗演算として、当該Ｇのべき乗演算に用いる指数部の演算を、法δによる剰余のもとで行うことを特徴とする暗号通信システム。
【００２６】
請求項１において、秘密鍵生成部は、前記パラメータδの任意の倍数を前記公開情報Ｔに含めることを特徴とする暗号通信システム。
【００２７】
〈請求項５の説明〉
請求項５の発明は、請求項１の式（１）に示す関係を満たすδを用い、このδを法とする剰余演算を行って、鍵生成や公開情報Ｔの作成を行うことを示している。ここで、δの倍数とは１倍も含むものとする。このような剰余演算としては、例えば、ｘ＾Ｆ（Ｘ（Ａ））＋ｙ＾Ｈ（Ｘ（Ａ））の演算や、ｙ＾Ｆ（Ｘ（Ａ））＋ｚ＾Ｈ（Ｘ（Ａ））の演算をδを法として行ったり、また、δの任意の倍数を法として演算するといったことがある。
【００２９】
Ｇのべき乗演算を含む処理として、Ｇをべき乗する指数部が何らかの演算により構成されており、この指数部の演算を請求項９に示したように法δによる剰余のもとで行うようにしたものである。このような剰余演算としては、式（６）のＧの指数部（ｘ＾Ｆ（Ｘ（Ａ））＋ｙ＾Ｈ（Ｘ（Ａ））の演算を法δによる剰余のもとで演算するといったことがある。
【００３０】
〈請求項６の構成〉
請求項１において、前記秘密鍵生成部、前記パラメータδの任意の倍数を用いて、前記公開情報の生成を行うことを特徴とする暗号通信システム。
【００３１】
〈請求項６の説明〉
δの任意の倍数とは、ｓｉ δやｕｉ δまたはＭを示しているが、これ以外の値であってもよい。
【００３６】
〈請求項７の構成〉
請求項１において、前記秘密鍵生成部は、前記パラメータδの任意の倍数を前記公開情報に含めることを特徴とする暗号通信システム。
【００３７】
〈請求項７の説明〉
δの任意の倍数とは例えばＭである。ここで、Ｍ＝δεとした場合、δとεがそれぞれ大きな素因数を因数に含み、Ｍの素因数分解が困難になるようにＭを選ぶようにすれば、Ｍを公開情報Ｔとして出力することができる。
【００３８】
〈請求項８の構成〉
請求項１において、前記秘密鍵生成部は、前記パラメータδの任意の倍数を法とする剰余演算を含む処理を、前記共通鍵の生成に用いることを特徴とする暗号通信システム。
【００３９】
〈請求項８の説明〉
公開情報Ｔに含まれるδの任意の倍数を用い、利用者側の共通鍵生成装置で、例えばＭのようなδの任意の倍数を法として剰余演算を行うことを示している。
【００４０】
〈請求項９の構成〉
請求項１，２または３のいずれかにおいて、前記秘密鍵生成部は、利用者Ａの公開鍵Ｘ（Ａ）に対する秘密鍵Ｙ（Ａ）として、式（６）または式（７）の演算により生成したＧｆ  （Ａ）またはＧｈ  （Ａ）の演算結果を含む情報を生成することを特徴とする暗号通信システム。
Ｇｆ （Ａ）＝Ｇ＾｛ｘ＾Ｆ（Ｘ（Ａ））＋ｙ＾Ｈ（Ｘ（Ａ））｝（ｍｏｄ．Ｎ）      …（６）
Ｇｈ （Ａ）＝Ｇ＾｛ｙ＾Ｆ（Ｘ（Ａ））＋ｚ＾Ｈ（Ｘ（Ａ））｝（ｍｏｄ．Ｎ）      …（７）
ただし、Ｆ、Ｈは公開鍵Ｘ（Ａ）に対する所定の関数である。
【００４１】
〈請求項１０の構成〉
請求項９において、前記秘密鍵生成部は、利用者Ａの公開鍵Ｘ（Ａ）に対して、式（６）および式（７）の演算により生成したＧｆ  （Ａ）とＧｈ  （Ａ）の組を、秘密鍵Ｙ（Ａ）＝（Ｇｆ  （Ａ），Ｇｈ  （Ａ））として生成することを特徴とする暗号通信システム。
【００４２】
〈請求項１１の構成〉
請求項９において、前記秘密鍵生成部は、式（６）または式（７）における関数ＦまたはＨとして、次式（８）または式（９）の関数を用いることを特徴とする暗号通信システム。
Ｆ（Ｘ）＝Σｉ ｛ｒｉ ｆｉ （Ｘ）｝      …（８）
Ｈ（Ｘ）＝Σｉ ｛ｔｉ ｈｉ （Ｘ）｝      …（９）
ただし、Σｉ はｉ＝０からｍ−１までの和を表す。
ここで、ｆｉ （Ｘ），ｈｉ （Ｘ）（０≦ｉ＜ｍ）は、公開鍵Ｘに対して出力されるそれぞれｍ個の出力である。それぞれｍ個のｒｉｔｉ （０≦ｉ＜ｍ）は任意である。
【００５９】
〈請求項１２の構成〉
暗号化装置と復号化装置とが同一の共通鍵を用いて通信データの暗号化および復号化を行う暗号通信システムにおいて、各利用者が共通に使用する公開情報を保持する保持部と、前記各利用者が公開鍵を入力すると該公開鍵に対し秘密鍵を生成する秘密鍵生成部とを有する鍵生成センタと、前記利用者の自己の秘密鍵と通信相手となる利用者の公開鍵及び前記公開情報に基づいてこれら各利用者に共通の共通鍵を生成する共通鍵生成部を有する共通鍵生成装置とを備える暗号通信システムにおいて、前記秘密鍵生成部は、任意の値であるδに対して、式（２）または式（３）の関係を満たす二つの値ｘとｙまたはｙとｚを用いた演算を、前記秘密鍵の生成に用いることを特著とする暗号通信システム。
ｘｙ≡０（ｍｏｄ．δ）      …（２）
ｙｚ≡０（ｍｏｄ．δ）      …（３）
【００６０】
〈請求項１３の構成〉
請求項１２において、前記秘密鍵生成部は、ｘとｙまたはｙとｚに対して、（ｘ＋ｙ）の任意のべき乗または（ｙ＋ｚ）の任意のべき乗を含む演算を前記公開情報の生成に用いることを特徴とする暗号通信システム。
【００６１】
〈請求項１４の構成〉
請求項１２において、前記秘密鍵生成部は、（ｘ＋ｙ）の任意のべき乗、または（ｙ＋ｚ）の任意のべき乗を含む項をδの任意の倍数を含む項を加算する演算を含む処理を公開情報の生成に用いることを特徴とする暗号通信システム。
【００６２】
〈請求項１５の構成〉
請求項１４において、前記秘密鍵生成部は、式（４）または式（５）に示す演算で得られるｅｉ  またはｄｉ  を公開情報に含めることを特徴とする暗号通信システム。
ｅｉ ＝（ｘ＋ｙ）＾ｒｉ ＋ｓｉ δ（ｍｏｄ．Ｍ）      …（４）
ｄｉ ＝（ｙ＋ｚ）＾ｔｉ ＋ｕｉ δ（ｍｏｄ．Ｍ）      …（５）
ただし、Ｍはδの任意の倍数である。また、ｒｉ ，ｓｉ ，ｔｉ ，ｕｉ は、任意の数である。
【００６３】
〈請求項１６の構成〉
請求項１５において、前記秘密鍵生成部は、次式（８）または式（９）の演算で用いるｍ個のｒｉ （０≦ｉ＜ｍ）またはｔｉ （０≦ｉ＜ｍ）を用いて、式（４）または式（５）の計算で得られるｍ個のｅｉ（０≦ｉ＜ｍ）またはｄｉ （０≦ｉ＜ｍ）を、公開情報に含めることを特徴とする暗号通信システム。
Ｆ（Ｘ）＝Σｉ ｛ｒｉ ｆｉ （Ｘ）｝      …（８）
Ｈ（Ｘ）＝Σｉ ｛ｔｉ ｈｉ （Ｘ）｝      …（９）
ただし、Σｉ はｉ＝０からｍ−１までの和を表す。ここで、ｆｉ （Ｘ），ｈｉ （Ｘ）（０≦ｉ＜ｍ）は、公開鍵Ｘに対して出力されるそれぞれｍ個の出力である。それぞれｍ個のｒｉｔｉ （０≦ｉ＜ｍ）は任意である。
【００６４】
〈請求項１７の構成〉
請求項１２において、前記秘密鍵生成部は、ｘとｙまたはｙとｚをべき乗する演算を含む処理を行うことを特徴とする暗号通信システム。
【００６５】
〈請求項１８の構成〉
請求項１７において、前記秘密鍵生成部は、ｘとｙまたはｙとｚを、それぞれべき乗して得られた結果を含む項を加算する演算を含む処理を行うことを特徴とする暗号通信システム。
【００６６】
〈請求項１９の構成〉
請求項１２において、前記秘密鍵生成部は、δの倍数を法とする剰余演算を含む演算を、前記秘密鍵の生成または公開情報の生成に用いることを特徴とする暗号通信システム。
【００６７】
〈請求項２０の構成〉
請求項１２において、前記秘密鍵生成部は、δの任意の倍数を用いて、公開情報の生成を行うことを特徴とする暗号通信システム。
【００６８】
＜請求項２１の構成＞
請求項１２において、前記秘密鍵生成部は、δの任意の倍数を公開情報に含めて出力することを特徴とする暗号通信システム。
【００６９】
＜請求項２２の構成＞
請求項１２において、前記共通鍵生成部は、δの任意の倍数を法とする剰余演算を含む処理を、共通鍵の生成に用いることを特徴とする暗号通信システム。
【００７０】
＜請求項２３の構成＞
請求項１２において、前記秘密鍵生成部は、利用者Ａの公開鍵Ｘ（Ａ）に対する秘密鍵Ｙ（Ａ）として、式（６）または式（７）の演算により生成したＧｆ  （Ａ）またはＧｈ  （Ａ）の演算結果を含む情報を生成することを特徴とする暗号通信システム。
Ｇｆ （Ａ）＝Ｇ＾｛ｘ＾Ｆ（Ｘ（Ａ））＋ｙ＾Ｈ（Ｘ（Ａ））｝（ｍｏｄ．Ｎ）      …（６）
Ｇｈ （Ａ）＝Ｇ＾｛ｙ＾Ｆ（Ｘ（Ａ））＋ｚ＾Ｈ（Ｘ（Ａ））｝（ｍｏｄ．Ｎ）      …（７）
ただし、Ｆ、Ｈは公開鍵Ｘ（Ａ）に対する所定の関数である。
【００７１】
＜請求項２４の構成＞
請求項２３において、前記秘密鍵生成部は、利用者Ａの公開鍵Ｘ（Ａ）に対して、式（６）および式（７）の演算により生成したＧｆ  （Ａ）とＧｈ  （Ａ）の組を、秘密鍵Ｙ（Ａ）＝（Ｇｆ  （Ａ），Ｇｈ  （Ａ））として生成することを特徴とする暗号通信システム。
【００７２】
＜請求項２５の構成＞
請求項２３において、前記秘密鍵生成部は、式（６）または式（７）における関数ＦまたはＨとして、次式（８）または式（９）の関数を用いることを特徴とする暗号通信システム。
Ｆ（Ｘ）＝Σｉ ｛ｒｉｆｉ （Ｘ）｝      …（８）
Ｈ（Ｘ）＝Σｉ ｛ｔｉｈｉ （Ｘ）｝      …（９）
ただし、Σｉ はｉ＝０からｍ−１までの和を表す。
ここで、ｆｉ （Ｘ），ｈｉ（Ｘ）（０≦ｉ＜ｍ）は、公開鍵Ｘに対して出力されるそれぞれｍ個の出力である。
それぞれｍ個のｒｉ ｔｉ（０≦ｉ＜ｍ）は任意である。
【００７３】
＜請求項２６の説明＞
暗号化装置と復号化装置とが同一の共通鍵を用いて通信データの暗号化および復号化を行う暗号通信システムにおいて、各利用者が共通に使用する公開情報を保持する保持部と、前記各利用者が公開鍵を入力すると該公開鍵に対し秘密鍵を生成する秘密鍵生成部とを有する鍵生成センタと、前記利用者の自己の秘密鍵と通信相手となる利用者の公開鍵及び前記公開情報に基づいてこれら各利用者に共通の共通鍵を生成する共通鍵生成部を有する共通鍵生成装置とを備える暗号通信システムにおいて、前記秘密鍵生成部または共通鍵生成部は、入力される利用者Ａの公開鍵Ｘ（Ａ）または公開鍵Ｘ（Ａ）に基づいて演算した結果から、所定の値であるｍ個の出力を得る処理手段を備え、前記秘密鍵生成部は、ある公開鍵Ｘに対して出力されるｍ個の出力を、ｆｉ  （Ｘ）（０≦ｉ＜ｍ）またはｈｉ  （Ｘ）（０≦ｉ＜ｍ）として、これらｆｉ  （Ｘ）またはｈｉ  （Ｘ）を用いた式（８）または式（９）のような関数ＦまたはＨを用いることを特徴とする暗号通信システム。
Ｆ（Ｘ）＝Σｉ ｛ｒｉ ｆｉ （Ｘ）｝      …（８）
Ｈ（Ｘ）＝Σｉ ｛ｔｉ ｈｉ （Ｘ）｝      …（９）
ただし、Σｉ はｉ＝０からｍ−１までの和を表す。
ここで、ｆｉ （Ｘ），ｈｉ （Ｘ）（０≦ｉ＜ｍ）は、公開鍵Ｘに対して出力されるそれぞれｍ個の出力である。それぞれｍ個のｒｉｔｉ （０≦ｉ＜ｍ）は任意である。
【００７４】
＜請求項２７の構成＞
暗号化装置と復号化装置とが同一の共通鍵を用いて通信データの暗号化および復号化を行う暗号通信システムにおいて、各利用者が共通に使用する公開情報を保持する保持部と、前記各利用者が公開鍵を入力すると該公開鍵に対し秘密鍵を生成する秘密鍵生成部とを有する鍵生成センタと、前記利用者の自己の秘密鍵と通信相手となる利用者の公開鍵及び前記公開情報に基づいてこれら各利用者に共通の共通鍵を生成する共通鍵生成部を有する共通鍵生成装置とを備える暗号通信システムにおいて、前記秘密鍵生成部または共通鍵生成部は、入力される利用者Ａの公開鍵Ｘ（Ａ）または公開鍵Ｘ（Ａ）に基づいて演算した結果から、所定の値であるｍ個の出力を得る処理手段を備え、前記共通鍵生成部は、前記共通鍵生成装置を持つ利用者Ａの秘密鍵Ｙ（Ａ）に含まれる二つの部分情報Ｇｆ  （Ａ）とＧｈ  （Ａ）および公開情報に含まれているそれぞれｍ個のｅｉ  ，ｄｉ  （０≦ｉ＜ｍ）と、利用者Ａの通信相手となる利用者Ｂの公開鍵Ｘ（Ｂ）に対して、それぞれｍ個の出力ｆｉ  （Ｘ（Ｂ）），ｈｉ  （Ｘ（Ｂ））（０≦ｉ＜ｍ）を得る処理とを用いて次式（１０）の演算により、共通鍵Ｋ（Ａ，Ｂ）を生成することを特徴とする暗号通信システム。
Ｋ（Ａ，Ｂ）＝Ｇｆ （Ａ）＾｛Πｉ［ｅｉ ＾ｆｉ （Ｘ（Ｂ））］｝・Ｇｈ （Ａ）＾｛Πｉ ［ｄｉ ＾ｈｉ （Ｘ（Ｂ））］｝（ｍｏｄ．Ｎ）      …（１０）
ただし、Πｉ はｉ＝０からｍ−１までの積を表す。ここで、Ｇｆ（Ａ），Ｇｈ （Ａ）は、秘密鍵Ｙ（Ａ）に含まれる二つの部分情報、ｆｉ （Ｘ（Ｂ）），ｈｉ （Ｘ（Ｂ））（０≦ｉ＜ｍ）は、公開鍵Ｘ（Ｂ）に対するそれぞれｍ個の出力である。
【００７５】
＜請求項２８の構成＞
請求項２７において、前記共通鍵生成部は、式（１０）におけるＧｆ  （Ａ）またはＧｈ  （Ａ）のべき乗演算の指数部での積を法Ｎの剰余のもとでのべき乗の繰り返しにより計算することを特徴とする暗号通信システム。
【００７６】
＜請求項２９の構成＞
請求項２８において、前記共通鍵生成部は、式（１０）におけるｆｉ（Ｘ（Ｂ））またはｈｉ （Ｘ（Ｂ））の出力が０であった場合に、ｅｉ  ＾ｆｉ （Ｘ（Ｂ））またはｄｉ  ＾ｈｉ （Ｘ（Ｂ））を指数とするべき乗処理を省略することを特徴とする暗号通信システム。
【００７７】
＜請求項３０の構成＞
請求項２９において、前記共通鍵生成部は、式（１０）におけるｆｉ（Ｘ（Ｂ））またはｈｉ （Ｘ（Ｂ））の出力を、０または１の２値出力とし、ｅｉ  ＾ｆｉ （Ｘ（Ｂ））またはｄｉ  ＾ｈｉ （Ｘ（Ｂ））を指数とするべき乗処理を、前記出力値が０のときはべき乗処理を省略し、前記出力値が１のときはｅｉ  またはｄｉ  によるべき乗処理として行うことを特徴とする暗号通信システム。
【００７８】
＜請求項３１の構成＞
暗号化装置と復号化装置とが同一の共通鍵を用いて通信データの暗号化および復号化を行う暗号通信システムにおいて、各利用者が共通に使用する公開情報を保持する保持部と、前記各利用者が公開鍵を入力すると該公開鍵に対し秘密鍵を生成する秘密鍵生成部とを有する鍵生成センタと、前記利用者の自己の秘密鍵と通信相手となる利用者の公開鍵及び前記公開情報に基づいてこれら各利用者に共通の共通鍵を生成する共通鍵生成部を有する共通鍵生成装置とを備える暗号通信システムにおいて、前記秘密鍵生成部は、次式（１）の関係を示すＮと、次式（４）、（５）の演算結果として得られるそれぞれｍ個のｅｉ  ，ｄｉ  （０≦ｉ＜ｍ）を公開情報に含めて出力し、かつ、任意の利用者Ａの公開鍵Ｘ（Ａ）に対する秘密鍵Ｙ（Ａ）＝（Ｇｆ  （Ａ），Ｇｈ  （Ａ））を、次式（６），（７）の演算より生成し、前記共通鍵生成部は、前記利用者Ａの秘密鍵Ｙ（Ａ）と、当該利用者の通信相手となる利用者Ｂの公開鍵Ｘ（Ｂ）を用いて、次式（１０）の演算により共通鍵Ｋ（Ａ，Ｂ）を生成することを特徴とする暗号通信システム。
任意のｋ＞０に対して、
Ｇ＾（δ＋ｋ）≡Ｇ＾ｋ（ｍｏｄ．Ｎ）               …（１）
ただし、＾はべき乗演算を表し、ａ≡ｂ（ｍｏｄ．ｑ）はａとｂがｑを法として合同であることを表す。
ｅｉ ＝（ｘ＋ｙ）＾ｒｉ＋ｓｉ δ（ｍｏｄ．Ｍ）          …（４）
ｄｉ ＝（ｙ＋ｚ）＾ｔｉ＋ｕｉ δ（ｍｏｄ．Ｍ）          …（５）
ただし、Ｍはδの任意の倍数である。また、ｒｉ，ｓｉ ，ｔｉ ，ｕｉ は、任意の数である。
Ｇｆ （Ａ）＝Ｇ＾｛ｘ＾Ｆ（Ｘ（Ａ））＋ｙ＾Ｈ（Ｘ（Ａ））｝（ｍｏｄ．Ｎ）      …（６）
Ｇｈ （Ａ）＝Ｇ＾｛ｙ＾Ｆ（Ｘ（Ａ））＋ｚ＾Ｈ（Ｘ（Ａ））｝（ｍｏｄ．Ｎ）      …（７）
ただし、式（４），（５），（６），（７）におけるｘ，ｙ，ｚは次式（２），（３）の関係を満たす。
ｘｙ≡０（ｍｏｄ．δ）      …（２）
ｙｚ≡０（ｍｏｄ．δ）      …（３）
また、Ｆ，Ｈは、ある公開鍵Ｘに対して次式（８），（９）のような関数である。
Ｆ（Ｘ）＝Σｉ ｛ｒｉｆｉ （Ｘ）｝                      …（８）
Ｈ（Ｘ）＝Σｉ ｛ｔｉｈｉ （Ｘ）｝                      …（９）
ただし、Σｉ  はｉ＝０からｍ−１までの和を表す。ここで、ｆｉ  （Ｘ），ｈｉ  （Ｘ）（０≦ｉ＜ｍ）は、公開鍵Ｘに対して出力されるそれぞれｍ個の出力である。
Ｋ（Ａ，Ｂ）＝Ｇｆ （Ａ）＾｛Πｉ［ｅｉ ＾ｆｉ （Ｘ（Ｂ））］｝・Ｇｈ （Ａ）＾｛Πｉ ［ｄｉ ＾ｈｉ （Ｘ（Ｂ））］｝（ｍｏｄ．Ｎ）      …（１０）
ただし、Πｉ はｉ＝０からｍ−１までの積を表す。ここで、Ｇｆ
（Ａ），Ｇｈ （Ａ）は、秘密鍵Ｙ（Ａ）に含まれる二つの部分情報、ｆｉ （Ｘ（Ｂ）），ｈｉ （Ｘ（Ｂ））（０≦ｉ＜ｍ）は、公開鍵Ｘ（Ｂ）に対するそれぞれｍ個の出力である。
【００８２】
【発明の実施の形態】
以下、本発明の実施の形態を具体例を用いて説明する。
【００８３】
〈具体例１〉
図１は、本発明の暗号通信システムにおける具体例１を示す構成図である。
図のシステムは、鍵生成センタ１０１、共通鍵生成装置１０２−Ａ、１０２−Ｂ、暗号化装置１０３、復号化装置１０４からなる。
【００８４】
鍵生成センタ１０１は、各利用者が共通に使用する公開情報Ｔを出力すると共に、例えば、任意の利用者を利用者Ａとした場合、この利用者Ａの公開鍵（ＩＤ情報）Ｘ（Ａ）に対し、利用者Ａの秘密鍵（秘密情報）Ｙ（Ａ）を出力する機能を有している。共通鍵生成装置１０２−Ａ、１０２−Ｂは、それぞれ利用者Ａ、利用者Ｂの秘密鍵Ｙ（Ａ）、Ｙ（Ｂ）と、利用者Ａ、利用者Ｂの通信相手となる利用者Ｂ、利用者Ａの公開鍵Ｘ（Ｂ）、Ｘ（Ａ）と、公開情報Ｔとから、これら利用者Ａと利用者Ｂの間の共通鍵Ｋ（Ａ，Ｂ）、Ｋ（Ｂ，Ａ）を出力する機能を有している。
【００８５】
また、暗号化装置１０３は、通信データに対して、共通鍵生成装置１０２−Ａで生成した共通鍵Ｋ（Ａ，Ｂ）を用いて暗号化を行う装置であり、復号化装置１０４は、暗号化データに対して、共通鍵生成装置１０２−Ｂで生成した共通鍵Ｋ（Ｂ，Ａ）を用いて復号化を行う装置である。尚、以下、共通鍵生成装置１０２−Ａ、１０２−Ｂで共通の構成については共通鍵生成装置１０２として説明する。
【００８６】
このような暗号通信システムにおいて、先ず、暗号通信システムの利用者は、他の利用者がその利用者を一意に特定できるＩＤ情報を、鍵生成センタ１０１に入力する。これにより、鍵生成センタ１０１は、後述する所定の処理を行って、利用者が秘密に保管する秘密情報（秘密鍵）を出力し、利用者はこれを受け取る。ここで、ＩＤ情報とは、例えば名前、住所、電子メールアドレス等である。そして、この手続きは、暗号システム利用者がこのシステムに加入する際に１回だけ行われる。
【００８７】
次に、他の利用者と暗号通信を行う場合には、鍵生成センタ１０１から受け取った秘密情報と、通信する相手のＩＤ情報を、利用者が保持する共通鍵生成装置１０２に入力する。共通鍵生成装置１０２は、通信相手との共通鍵を生成し、出力する。利用者は、この共通鍵を暗号通信のための鍵として利用し、相手との暗号通信を行う。
【００８８】
次に、図１を用いて各構成要素の動作を詳細に説明する。
先ず、鍵生成センタ１０１は、システムの運用開始前に次のようなパラメータを用意する。
【００８９】
・Ｎ
通常Ｎは、その素因数分解が困難であるような合成数とする。
例えば、大きな素数Ｐ，Ｑの積として、Ｎ＝ＰＱとする。
・Ｇ，δ
ただし、Ｇとδは、上記Ｎに対して次式（１）の関係を満たすものとする。
任意のｋ＞０に対して、
Ｇ＾（δ＋ｋ）≡Ｇ＾ｋ（ｍｏｄ．Ｎ）    …（１）
ただし、＾はべき乗演算を表し、ａ≡ｂ（ｍｏｄ．ｑ）は、ａとｂがｑを法として合同であることを表す。尚、「ａとｂがｑを法として合同である」とは、「値ｑで除算した剰余がａとｂとで等しい」ことを意味している。
【００９０】
例えば、上記のＧとδは、次のようにして選ぶことができる。
ＮのＣａｒｍｉｃｈａｅｌ関数をＬ＝λ（Ｎ）とする。例えば、Ｎ＝ＰＱ（Ｐ，Ｑは素数）とした場合は、Ｌ＝λ（Ｎ）＝ｌｃｍ（Ｐ−１，Ｑ−１）である。ただし、ｌｃｍ（ａ，ｂ）は、ａとｂの最小公倍数を表す。
【００９１】
Ｌは、Ｎと互いに素なｇ、即ち、ｇｃｄ（ｇ，Ｎ）＝１であるｇについて、次の関係
ｇ＾Ｌ≡１（ｍｏｄ．Ｎ）
を満たす。ただし、ｇｃｄ（ａ，ｂ）はａとｂの最大公約数を表す。
【００９２】
上記Ｌに対して、Ｌ＝γδとなるようにγとδを選び、また、Ｎと互いに素なｇにより、Ｇ≡ｇ＾γ（ｍｏｄ．Ｎ）とすれば、上記式（１）の関係を満たす。ｇをＮと互いに素に選んだ場合、式（１）は、ｋ＝０についても成立する。例えば、Ｎ＝ＰＱ（Ｐ，Ｑは素数）としたときには、ｇをＧＦ（Ｐ）、ＧＦ（Ｑ）上の原始元となるように選ぶこともできる。
【００９３】
・ｘ，ｙ，ｚ
ただし、ｘ，ｙ，ｚは、上記δに対して、次式（２）、（３）の関係を満たすものとする。
ｘｙ≡０（ｍｏｄ．δ）    …（２）
ｙｚ≡０（ｍｏｄ．δ）    …（３）
【００９４】
例えば、δ＝αβであるようなαとβを用いて、ｘ＝ｘ′α，ｙ＝ｙ′β，ｚ＝ｚ′αとすれば、上記式（２），（３）の関係を満たす。このとき、ｘ′，ｙ′，ｚ′は乱数でもよい。
【００９５】
・ｆ，ｈ，ｎ、もしくは、それぞれｍ個のｆｉ  ，ｈｉ  （０≦ｉ＜ｍ）
ｆ，ｈは、一方向性ハッシュ関数である。ただし、０≦ｆ（Ｘ），ｈ（Ｘ）＜ｎ＾ｍとする。尚、一方向性ハッシュ関数は、入力から出力は容易に求められるが、出力から入力を推定するのは困難である関数である。
【００９６】
このとき、ｆ（Ｘ），ｈ（Ｘ）をｍ桁以下のｎ進数で表したときのｉ番目の桁をそれぞれｆｉ  （Ｘ），ｈｉ  （Ｘ）（０≦ｉ＜ｍ）とする。ただし、０≦ｆｉ  （Ｘ），ｈｉ  （Ｘ）＜ｎ  （０≦ｉ＜ｍ）である。即ち、ｆ（Ｘ）＝Σｉ  ｛ｆｉ  （Ｘ）ｎ＾ｉ｝、ｈ（Ｘ）＝Σｉ  ｛ｈｉ  （Ｘ）ｎ＾ｉ｝とする。ここで、Σｉ  はｉ＝０からｍ−１までの和を表すものとする。
【００９７】
ｎは、ｆ（Ｘ），ｈ（Ｘ）を、ｆｉ  （Ｘ），ｈｉ  （Ｘ）（０≦ｉ＜ｍ）に分解するときの基数である。通常ｎ＝２とする。ｆ，ｈおよびｎの代わりに、それぞれｍ個の一方向性関数群ｆｉ  ，ｈｉ  （０≦ｉ＜ｍ）のみがあるものと考えてもよい。
【００９８】
・それぞれｍ個のｒｉ  ，ｔｉ  （０≦ｉ＜ｍ）
ｒｉ  ，ｔｉ  は、それぞれ乱数でもよい。
【００９９】
・それぞれｍ個のｅｉ  ，ｄｉ  （０≦ｉ＜ｍ）
ただし、ｅｉ  ，ｄｉ  は、次式（４），（５）のように計算して得られたものである。
ｅｉ  ＝（ｘ＋ｙ）＾ｒｉ  ＋ｓｉ  δ（ｍｏｄ．Ｍ）    …（４）
ｄｉ  ＝（ｙ＋ｚ）＾ｔｉ  ＋ｕｉ  δ（ｍｏｄ．Ｍ）    …（５）
ただし、Ｍはδの任意の倍数である。
【０１００】
ここで、Ｍは、Ｍ＝δε、即ち、上記δとεの積である。ただし、εは乱数でもよい。例えば、εは、Ｌ＝γδとした場合のγと同じ（ε＝γ）であってもよく、この場合はＭ＝Ｌとなる。また、それぞれｍ個のｓｉ  ，ｕｉ  （０≦ｉ＜ｍ）は、乱数でもよい。
【０１０１】
以上、述べたパラメータの内、Ｇ，δ，ｘ，ｙ，ｚ、およびそれぞれｍ個のｒｉ  ，ｔｉ  （０≦ｉ＜ｍ）は、鍵生成センタ１０１が内部に秘密に保管する。一方、Ｎと、それぞれｍ個のｅｉ  ，ｄｉ  （０≦ｉ＜ｍ）、および関数ｆ，ｈと基数ｎ（もしくは、それぞれｍ個の関数ｆｉ  ，ｈｉ  ）は、各利用者の共通鍵生成装置１０２においても使用する公開可能な情報である公開情報Ｔである。公開情報Ｔは、各利用者の共通鍵生成装置１０２において使用可能なように提供されていればよく、共通鍵生成装置１０２に組み込まれていたり、秘密鍵と共に利用者のみに秘密に届ける等、共通鍵生成装置１０２以外には公になっていなくてもよい。
【０１０２】
その他、上記のパラメータを用意する過程で使用したパラメータ（例えば、Ｌ，Ｍ，ｇ，α，β，γ，ε，ｘ′，ｙ′，ｚ′，ｓｉ  ，ｕｉ  ，Ｐ，Ｑ等）は、鍵生成センタ１０１が内部に秘密に保管するか、もしくは破棄してもよい。尚、例えばδとεがそれぞれ大きな素因数を因数に含み、Ｍの素因数分解が困難となるようにＭを選べば、このＭを公開することも可能である。また、ｒｉ  ，ｔｉ  は、それぞれのｉにおいてｒｉ  ＝ｔｉ  としてもよく、このとき鍵生成センタ１０１は、その片方のｍ個を保管すればよい。
【０１０３】
ある利用者（ここでは利用者Ａとする）が、本具体例の暗号通信システムに加入するとき、利用者Ａは自己のＩＤ情報Ｘ（Ａ）を鍵生成センタ１０１に入力する。鍵生成センタ１０１は、内部で次式（６），（７）の演算を行い、利用者Ａが秘密に保管する秘密情報Ｙ（Ａ）を出力し、利用者Ａに秘密に届ける。秘密に届ける方法としては、ＩＣカード内にデータを納めて郵送する等の方法がある。
【０１０４】
Ｙ（Ａ）は、Ｇｆ  （Ａ）とＧｈ  （Ａ）を並べたものであり、鍵生成センタ１０１の内部での次の演算により生成される。
0003634097.tif 000002
ここで、Ｆ，Ｈは、上記ｆｉ  ，ｈｉ  、および、ｒｉ  ，ｔｉ  を用いた次式（８），（９）のような関数である。
【０１０５】
Ｆ（Ｘ）＝Σｉ  ｛ｒｉ  ｆｉ  （Ｘ）｝    …（８）
Ｈ（Ｘ）＝Σｉ  ｛ｔｉ  ｈｉ  （Ｘ）｝    …（９）
ただし、Σｉ  はｉ＝０からｍ−１までの和を表す。
【０１０６】
他の利用者（ここでは利用者Ｂとする）も同様に、システム加入時には、自己のＩＤ情報Ｘ（Ｂ）を鍵生成センタ１０１に入力し、鍵生成センタ１０１内部での演算により得られた利用者Ｂが秘密に保管する秘密情報Ｙ（Ｂ）を受け取る。
【０１０７】
尚、鍵生成センタ１０１は、式（６），（７）のＧの指数部（例えば、ｘ＾Ｆ（Ｘ（Ａ））＋ｙ＾Ｈ（Ｘ（Ａ））の演算を法δによる剰余のもとで演算することも可能である。
【０１０８】
次に、利用者Ａは秘密通信を行う相手のＩＤ情報Ｘ（Ｂ）と鍵生成センタ１０１から受け取ったＹ（Ａ）を利用者Ａが保有する共通鍵生成装置１０２−Ａに入力する。共通鍵生成装置１０２−Ａは、次の演算を行い、共通鍵Ｋ（Ａ，Ｂ）を出力する。
0003634097.tif 000003
ただし、Πｉ  はｉ＝０からｍ−１までの積を表す。
【０１０９】
利用者Ｂも同様に、共通鍵生成装置１０２−Ｂを利用し、
0003634097.tif 000004
ただし、Πｉ  はｉ＝０からｍ−１までの積を表す。
を得る。
【０１１０】
式（１０）および式（１１）の演算において、Πｉ  ［ｅｉ  ＾ｆｉ  （Ｘ（Ｂ））］のような演算の値は、非常に大きなものであるが、次のように計算することが可能である。
ａ＾｛ｂｃ｝≡｛ａ＾ｂ（ｍｏｄ．Ｎ）｝＾ｃ（ｍｏｄ．Ｎ）
即ち、指数部での積を、べき乗の繰り返しとし、各べき乗毎に法Ｎによる剰余を求めることによって、Ｎ程度の大きさの数の演算の繰り返しで計算できる。
【０１１１】
また、ｆｉ  やｈｉ  の出力が０となった場合には、ｅｉ  ＾ｆｉ  （Ｘ（Ｂ））＝１であるので、ｅｉ  ＾ｆｉ  （Ｘ（Ｂ））によるべき乗処理は不要となる。
特に、ｎ＝２の場合、即ち各ｆｉ  ，ｈｉ  の出力が０もしくは１のみである場合は、ｅｉ  ＾ｆｉ  （Ｘ（Ｂ））のような演算において、ｆｉ  （Ｘ（Ｂ））によるべき乗処理は不要となる。
【０１１２】
一方、公開情報Ｔの一部としてＭが提供されている場合は、式（１０）および式（１１）におけるΠｉ  ［ｅｉ  ＾ｆｉ  （Ｘ（Ｂ））］のような演算を法Ｍの剰余のもとで行うことも可能である。
【０１１３】
式（１０），（１１）を、それぞれ展開すると、
0003634097.tif 000005
となり、利用者Ａと利用者Ｂがそれぞれの共通鍵生成装置１０２で生成した鍵が一致する。共通鍵を生成する過程では、利用者Ａと利用者Ｂ間では情報の交換が行われておらず、しかも公開されている情報から、利用者Ａおよび利用者Ｂ以外は共有鍵Ｋ（Ａ，Ｂ）、Ｋ（Ｂ，Ａ）を導くことができない。従って、この利用者Ａと利用者Ｂは、通信することなく秘密に暗号通信のための共通鍵を共有したことになる。
【０１１４】
次に、利用者Ａは共通鍵生成装置１０２−Ａから出力されたＫ（Ａ，Ｂ）を暗号化装置１０３に入力し、通信データを暗号化して通信路を介して利用者Ｂに送信する。利用者Ｂは共通鍵生成装置１０２−Ｂから出力されたＫ（Ｂ，Ａ）を復号化装置１０４に入力し、暗号化装置１０３から受信した暗号化データを復号し、出力する。利用者Ａおよび利用者Ｂ以外は、暗号化装置１０３で使用された暗号鍵を知らないので、通信路上に流れるデータが第三者に盗聴されても安全である。
【０１１５】
〈具体例２〉
図３は、暗号通信システムの具体例２の構成図である。
ここで、図１に示した具体例１の暗号通信システムとは、乱数生成装置３０５が付加されたこと、および共通鍵生成装置の入力に乱数が付け加えられたことが異なる。乱数を入力とする共通鍵生成装置が３０２−Ａと３０２−Ｂである。
【０１１６】
利用者Ａおよび利用者Ｂが鍵生成センタ１０１からそれぞれの秘密情報Ｙ（Ａ）およびＹ（Ｂ）を入手するまでの動作は具体例１と同一であるため、ここでの説明は省略する。
次に、利用者Ａが持つ乱数発生装置３０５が乱数Ｒを発生する。乱数発生装置３０５は、毎回異なる乱数を発生する。利用者Ａは、鍵生成センタ１０１から受け取った秘密情報Ｙ（Ａ）と、利用者ＢのＩＤ情報Ｘ（Ｂ）と、乱数発生装置３０５が発生した乱数Ｒとを共通鍵生成装置３０２−Ａに入力する。共通鍵生成装置３０２−Ａは、次の演算を行い共通鍵Ｋ（Ａ，Ｂ）を生成する。
【０１１７】
0003634097.tif 000006
ただし、Πｉ  はｉ＝０からｍ−１までの積を表す。
【０１１８】
また、乱数Ｒは利用者Ｂに通信路を介して伝送される。利用者Ｂは、共通鍵生成装置３０２−Ｂにおいて次の演算を行い共通鍵Ｋ（Ｂ，Ａ）を生成する。
【０１１９】
0003634097.tif 000007
ただし、Πｉ  はｉ＝０からｍ−１までの積を表す。
明らかに、Ｋ（Ａ，Ｂ）＝Ｋ（Ｂ，Ａ）となる。
【０１２０】
具体例２における共通鍵Ｋ（Ａ，Ｂ）またはＫ（Ｂ，Ａ）の生成方法は、具体例１における式（１０）または式（１１）の右辺とＲの加算以外にも、式（１０）または式（１１）の右辺の演算結果とＲの双方に依存した演算を行う種々の生成方法に変形可能である。即ち、式（１０）または式（１１）の右辺に対してＲを加算する構成以外にも、Ｒの乗算を行う等、種々の構成によって共通鍵の生成を行うようにしてもよい。
【０１２１】
具体例１においては、利用者Ａと利用者Ｂの間の共通鍵は毎回同一であったが、具体例２では、鍵共有を行う度に異なる共通鍵が利用者Ａと利用者Ｂの間で共有される。
【図面の簡単な説明】
【図１】本発明の暗号通信システムの具体例１の構成図である。
【図２】従来の暗号通信システムの構成図である。
【図３】本発明の暗号通信システムの具体例２の構成図である。
【符号の説明】
１０１  鍵生成センタ
１０２−Ａ、１０２−Ｂ、３０２−Ａ、３０２−Ｂ  共通鍵生成装置
１０３  暗号化装置
１０４  復号化装置
３０５  乱数発生装置
【図１】
0003634097.tif 000008
【図２】
0003634097.tif 000009
【図３】
0003634097.tif 000010