(57)【要約】【課題】  安全で特に低密度攻撃への耐性に優れ、暗号化も復号も容易な暗号通信を可能にする。【解決手段】  暗号文Ｃを平文ｍから公開鍵ａ1〜ａ3を用いて、  Ｃ＝ａ1ｍ1ｅ＋ａ2ｍ2ｅ＋ａ3ｍ3ｅ   により暗号化する。暗号文Ｃを中間平文Ｍへ秘密鍵ｕ−１で復号し、  Ｍ＝ｕ−１Ｃ  modＮ＝ｂ1'ｍ1ｅ＋ｂ2'ｍ2ｅ＋ｂ3'ｍ3ｅ  とする。  ｂ1'−１Ｍ＝ｍ1ｅ＋ｂ2−１ｂ1ｍ2ｅ＋ｂ1ｂ3−１ｍ3ｅ  等の関係が成立するので、λ(ｂi)を法とするｅの逆元をｄi乗し、ｂiを法とする剰余  ｍi＝(ｂ1'−１Ｍ)ｄｉ  modｂiを求めると、ｍiが得られる．このようにして、平文ｍ＝(ｍ1,ｍ2,ｍ3)を求める。                  【選択図】    図１
2007219381.tif 000002
【特許請求の範囲】
【請求項１】
ｎ個のブロックｍi(ｉ＝１〜ｎ)からなる平文ｍ(ｍ＝ｍ1,…，ｍi,…，ｍn))に対して、
各ブロックｍiをｅi乗(ｅiは正整数で、少なくとも1個のｅiが2以上)しｍiｅiを求めるためのべき乗手段と、求めたｍiｅiに公開鍵ａi(ｉ＝１〜ｎ)を乗算しａi・ｍiｅi(ｉ＝１〜ｎ)を求めるための乗算手段と、求めたａi・ｍiｅi(ｉ＝１〜ｎ)を加算し暗号文Ｃ
(Ｃ＝Σｉ＝１〜ｎ ａi・ｍiｅi)を求めるための加算手段とを備える暗号化装置。
【請求項２】
各ｅiが少なくとも３であることを特徴とする、請求項１の暗号化装置。
【請求項３】
ｎが３であることを特徴とする、請求項２の暗号化装置。
【請求項４】
ｎ個のブロックｍi(ｉ＝１〜ｎ)からなる平文ｍ(ｍ＝(ｍ1,…，ｍn))に対して、
情報処理装置に設けたべき乗手段により、各ブロックｍiをｅi乗(ｅiは正整数で、少なくとも1個のｅiが2以上)してｍiｅi(ｉ＝１〜ｎ)を求め、
前記情報処理装置に設けた乗算手段により、求めたｍiｅiに公開鍵ａi(ｉ＝１〜ｎ)を乗算してａi・ｍiｅi(ｉ＝１〜ｎ)を求め、
前記情報処理装置に設けた加算手段により求めたａi・ｍiｅi(ｉ＝１〜ｎ)を加算して、暗号文Ｃ(Ｃ＝Σｉ＝１〜ｎ ａi・ｍiｅi)を求める、暗号化方法。
【請求項５】
ｎ個のブロックｍi(ｉ＝１〜ｎ)からなる平文ｍ(ｍ＝(ｍ1,…，ｍi,…，ｍn))を、べき乗手段と乗算手段と加算手段とを備えた情報処理装置により、暗号文Ｃ
(Ｃ＝Σｉ＝１〜ｎ ａi・ｍiｅi：ここにｅiは正整数で、少なくとも1個のｅiが2以上)へ暗号化するために、
前記べき乗手段により、各ブロックｍiをｅi乗して、ｍiｅi(ｉ＝１〜ｎ)を求めるためのべき乗命令と、
前記乗算手段により、求めたｍiｅiに公開鍵ａi(ｉ＝１〜ｎ)を乗算してａi・ｍiｅi(ｉ＝１〜ｎ)を求めるための乗算命令と、
前記加算手段により、求めたａi・ｍiｅi(ｉ＝１〜ｎ)を加算して暗号文Ｃ
(Ｃ＝Σｉ＝１〜ｎ ａi・ｍiｅi)を求めるための加算命令とを備えた暗号化プログラム。
【請求項６】
暗号文Ｃをｎ個の平文ブロックｍi(ｉ＝１〜ｎ)を経由して平文ｍへ復号するために、
秘密鍵として、正整数ｕ−１と、ｉ＝１〜ｎの各ｉに対して、正整数ｂiと、正整数
ｂi'−１と、正整数ｄi、とを記憶するための記憶部と、
暗号文Ｃに秘密鍵ｕ−１を乗算して中間平文Ｍへ復号するための中間復号手段と、
中間平文Ｍを、ｉ＝１〜ｎの各iに対して、平文のブロックｍi
(ｍi＝(ｂ1'−１Ｍ)ｄｉ  modｂi  もしくはｍi＝(ｂ1'−１Ｍ)１／２ modｂi )へ変換するためのブロック復号手段、とを備えた復号装置。
【請求項７】
前記記憶部は秘密鍵としてさらに相異なる正整数Ｐ，Ｑを記憶すると共に、前記秘密鍵、正整数ｂi、正整数ｂi'−１、ｄiとして、
Ｐに対する秘密鍵ｂi(Ｐ)、ｂi'(Ｐ)−１、ｄi(Ｐ)、及び
Ｑに対する秘密鍵ｂi(Ｑ)、ｂi'(Ｑ)−１、ｄi(Ｑ)を記憶し、
前記中間復号手段は、Ｍ(Ｐ)＝ｕ−１Ｃ modＰ  と  Ｍ(Ｑ)＝ｕ−１Ｃ modＱ  の２つの中間平文を求め、
前記ブロック復号手段は、ｍi(Ｐ)＝(ｂi'(Ｐ)−１Ｍ)ｄi(Ｐ) modｂi(Ｐ) と
ｍi(Ｑ)＝(ｂi'(Ｑ)−１Ｍ)ｄi(Ｑ) modｂi(Ｑ) とを求めて、中国人の剰余定理により、平文のブロックｍi(ｍi≡ｍi(Ｐ)  modｂi(Ｐ) ，ｍi≡ｍi(Ｑ)  modｂi(Ｑ))を求めることを特徴とする、請求項６の復号装置。
【請求項８】
暗号文Ｃをｎ個の平文ブロックｍi(ｉ＝１〜ｎ)からなる平文ｍへ復号するために、
情報処理装置の記憶部に秘密鍵として、正整数ｕ−１と、ｉ＝１〜ｎの各ｉに対して、正整数ｂiと、正整数ｂi'−１と、正整数ｄi、とを記憶し、
前記情報処理装置の中間復号手段で、暗号文Ｃに秘密鍵ｕ−１を乗算して中間平文Ｍへ復号し、
前記情報処理装置のブロック復号手段で、中間平文Ｍを、ｉ＝１〜ｎの各iに対して、平文のブロックｍi(ｍi＝(ｂ1'−１Ｍ)ｄｉ  modｂi  もしくはｍi＝(ｂ1'−１Ｍ)１／２ modｂi )へ変換して、平文ｍへ復号する復号方法。
【請求項９】
前記記憶部で秘密鍵としてさらに相異なる正整数Ｐ，Ｑを記憶すると共に、前記秘密鍵、正整数ｂi、正整数ｂi'−１、ｄiとして、
Ｐに対する秘密鍵ｂi(Ｐ)、ｂi'(Ｐ)−１、ｄi(Ｐ)、及び
Ｑに対する秘密鍵ｂi(Ｑ)、ｂi'(Ｑ)−１、ｄi(Ｑ)を記憶し、
前記中間復号手段で、Ｍ(Ｐ)＝ｕ−１Ｃ modＰ  と  Ｍ(Ｑ)＝ｕ−１Ｃ modＱ  の２つの中間平文Ｍ(Ｐ)，Ｍ(Ｑ)を求め、
前記ブロック復号手段で、ｍi(Ｐ)＝(ｂi'(Ｐ)−１Ｍ)ｄi(Ｐ) modｂi(Ｐ) と
ｍi(Ｑ)＝(ｂi'(Ｑ)−１Ｍ)ｄi(Ｑ) modｂi(Ｑ)とを求めて、中国人の剰余定理により、平文のブロックｍi(ｍi≡ｍi(Ｐ)  modｂi(Ｐ) ，ｍi≡ｍi(Ｑ)  modｂi(Ｑ))を求めることを特徴とする、請求項８の復号方法。
【請求項１０】
暗号文Ｃをｎ個の平文ブロックｍiからなる平文ｍへ復号するために、
情報処理装置の記憶部に秘密鍵として、正整数ｕ−１と、ｉ＝１〜ｎの各ｉに対して、正整数ｂiと、正整数ｂi'−１と、正整数ｄi、とを記憶させる記憶命令と、
前記情報処理装置に、暗号文Ｃに秘密鍵ｕ−１を乗算して中間平文Ｍへ復号させるための中間復号命令と、
前記情報処理装置に、中間平文Ｍをｉ＝１〜ｎの各iに対して平文のブロックｍi
(ｍi＝(ｂ1'−１Ｍ)ｄｉ  modｂi  もしくはｍi＝(ｂ1'−１Ｍ)１／２ modｂi )へ変換させるためのブロック復号命令、とを備えた復号プログラム。
【請求項１１】
前記記憶命令では記憶部に秘密鍵としてさらに相異なる正整数Ｐ，Ｑを記憶させると共に、前記秘密鍵、正整数ｂi、正整数ｂi'−１、ｄiとして、
Ｐに対する秘密鍵ｂi(Ｐ)、ｂi'(Ｐ)−１、ｄi(Ｐ)、及び
Ｑに対する秘密鍵ｂi(Ｑ)、ｂi'(Ｑ)−１、ｄi(Ｑ)を記憶させ、
前記中間復号命令で、Ｍ(Ｐ)＝ｕ−１Ｃ modＰ  と  Ｍ(Ｑ)＝ｕ−１Ｃ modＱ  の２つの中間平文Ｍ(Ｐ)，Ｍ(Ｑ)を求め、
前記ブロック復号命令で、ｍi(Ｐ)＝(ｂi'(Ｐ)−１Ｍ)ｄi(Ｐ) modｂi(Ｐ) と,
ｍi(Ｑ)＝(ｂi'(Ｑ)−１Ｍ)ｄi(Ｑ) modｂi(Ｑ) とを求めて、中国人の剰余定理により、平文のブロックｍi(ｍi≡ｍi(Ｐ)  modｂi(Ｐ) ，ｍi≡ｍi(Ｑ)  modｂi(Ｑ))を求めることを特徴とする、請求項１０の復号プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
この発明は暗号通信などに用いる公開鍵暗号とその復号とに関し、特に暗号化装置と暗号化方法、暗号化プログラム、及び復号装置、復号方法、復号プログラムに関する。
【背景技術】
【０００２】
発明者らは種々の積和型の公開鍵暗号システムについて提案してきた(非特許文献１〜３)。積和型の公開鍵暗号では一般に暗号文Ｃはｎブロックの平文ｍｉ(ｉ＝１〜ｎ)に対し、Ｃ＝Σｉ＝１−ｎａi・ｍi  で与えられる。そして積和型の公開鍵暗号には低密度攻撃(非特許文献４)が有効であることが知られている。そこで平文を拡大してそのビット数を増し、低密度攻撃への耐性を増すことが考えられる(非特許文献１〜３)。なお本発明のように平文を拡大してビット数を増す場合、密度Ｄは拡大平文のサイズと暗号文のサイズとの比で与えられ、密度Ｄが１以上であることが安全であるための必要条件と考えられている。
【非特許文献１】M.Kasahara and Y.Murakami: "New product-sum type public-keycryptosystems" Proc. of SCIS'90, p.p.15-20,1999.
【非特許文献２】R. Sakai,M.Kasahara and Y.Murakami: "Notes on product-sum type public-key cryptosystems" Technical Report of IEICE,ISEC90-46, p.p.61-66,1999.
【非特許文献３】K.Katayanagi,Y.Murakami and M.Kasahara: "New product-sum type public-key cryptosystems with selectable encryption key based on chineseremainder theorem" IEICE Trans. on Fundamentals,vol.E85-A,No.2,p.p.472-480,2002.
【非特許文献４】M.J.Coster, B.A.LaMacchia, A.M.Odlyzko and C.P.Schnorr: "AnImproved Low-Density Subset Sum Algorithm" Advances in Cryptology Proc. EUROCRYPT'91, LNCS, pp.54-67. Springer-Verlag, Berlin,1991
【発明の開示】
【発明が解決しようとする課題】
【０００３】
この発明の課題は、暗号化と復号とが容易で、低密度攻撃等の攻撃に安全な新たな公開鍵暗号を提供することにある。
この発明の課題は、具体的には新規な公開鍵暗号システムで用いる、暗号化装置、暗号化方法、暗号化プログラム、及び復号装置、復号方法、復号プログラムを提供することにある。
【課題を解決するための手段】
【０００４】
この発明の暗号化装置は、ｎ個のブロックｍi(ｉ＝１〜ｎ)からなる平文ｍ(ｍ＝ｍ1,…，ｍi,…，ｍn))に対して、
各ブロックｍiをｅi乗(ｅiは正整数で、少なくとも1個のｅiが2以上)しｍiｅiを求めるためのべき乗手段と、求めたｍiｅiに公開鍵ａi(ｉ＝１〜ｎ)を乗算しａi・ｍiｅi(ｉ＝１〜ｎ)を求めるための乗算手段と、求めたａi・ｍiｅi(ｉ＝１〜ｎ)を加算し暗号文Ｃ
(Ｃ＝Σｉ＝１〜ｎ ａi・ｍiｅi)を求めるための加算手段とを備えたものである。
【０００５】
好ましくは２個以上、特に３個以上のｅiを２以上とし、特に好ましくは各ｅiを２以上とする。また好ましくは、２個以上、特に３個以上のｅiを３以上とし、さらに好ましくは各ｅiを３以上とし、特に好ましくは各ｅiを３，５，７等の奇素数とし、最も好ましくは全ｅiを３とする。また好ましくは、ｎは３以上で、好ましくはｎを３とする。なおこの点は、暗号化方法や暗号化プログラム、復号装置や復号方法、復号プログラムに関しても同様である。
例えば暗号文Ｃ；    Ｃ＝ｍ1３・ａ1＋ｍ2３・ａ2＋ｍ3３・ａ3＋ｍ4・ａ4  は、
Ｃ＝Ｃ1＋Ｃ２：  Ｃ1＝ｍ1３・ａ1＋ｍ2３・ａ2＋ｍ3３・ａ3；  Ｃ２＝ｍ4・ａ4
のように、本発明の暗号方式を利用して暗号文Ｃ1を作成して、その安全性に依存して従来の暗号  Ｃ２＝ｍ4・ａ4  を暗号文に含めたものである。この場合の復号は、本発明に従って暗号文Ｃ1を復号することと、暗号  Ｃ２＝ｍ4・ａ4  を復号することの組み合わせになる。そこでこのような場合、ｅiが２以上となる部分について本発明の暗号化や復号が行われたものと考えることができる。
Ｃ＝Ｃ1＋Ｃ２：  Ｃ1＝ｍ1３・ａ1＋ｍ2３・ａ2＋ｍ3３・ａ3；  Ｃ２＝ｍ4・ａ4  
の復号例を説明すると、実施例の表１〜表４において、ｄ4やｄ4（Ｐ）、ｄ4（Ｑ）を1とすると良い。
さらに平文ｍは暗号化前に置換やコーディングなどを施しても良く、その場合復号した平文に置換やデコーディングを施す。
【０００６】
この発明の暗号化方法は、ｎ個のブロックｍi(ｉ＝１〜ｎ)からなる平文ｍ(ｍ＝(ｍ1,…，ｍn))に対して、
情報処理装置に設けたべき乗手段により、各ブロックｍiをｅi乗(ｅiは正整数で、少なくとも1個のｅiが2以上)してｍiｅi(ｉ＝１〜ｎ)を求め、
前記情報処理装置に設けた乗算手段により、求めたｍiｅiに公開鍵ａi(ｉ＝１〜ｎ)を乗算してａi・ｍiｅi(ｉ＝１〜ｎ)を求め、
前記情報処理装置に設けた加算手段により求めたａi・ｍiｅi(ｉ＝１〜ｎ)を加算して、暗号文Ｃ(Ｃ＝Σｉ＝１〜ｎ ａi・ｍiｅi)を求める。
【０００７】
この発明の暗号化プログラムは、ｎ個のブロックｍi(ｉ＝１〜ｎ)からなる平文ｍ(ｍ＝(ｍ1,…，ｍi,…，ｍn))を、べき乗手段と乗算手段と加算手段とを備えた情報処理装置により、暗号文Ｃ  (Ｃ＝Σｉ＝１〜ｎ ａi・ｍiｅi：ここにｅiは正整数で、少なくとも1個のｅiが2以上)へ暗号化するために、
前記べき乗手段により、各ブロックｍiをｅi乗して、ｍiｅi(ｉ＝１〜ｎ)を求めるためのべき乗命令と、
前記乗算手段により、求めたｍiｅiに公開鍵ａi(ｉ＝１〜ｎ)を乗算してａi・ｍiｅi(ｉ＝１〜ｎ)を求めるための乗算命令と、
前記加算手段により、求めたａi・ｍiｅi(ｉ＝１〜ｎ)を加算して暗号文Ｃ
(Ｃ＝Σｉ＝１〜ｎ ａi・ｍiｅi)を求めるための加算命令とを備える。
【０００８】
この発明の復号装置は、暗号文Ｃをｎ個の平文ブロックｍi(ｉ＝１〜ｎ)を経由して平文ｍへ復号するために、
秘密鍵として、正整数ｕ−１と、ｉ＝１〜ｎの各ｉに対して、正整数ｂiと、正整数
ｂi'−１と、正整数ｄi、とを記憶するための記憶部と、
暗号文Ｃに秘密鍵ｕ−１を乗算して中間平文Ｍへ復号するための中間復号手段と、
中間平文Ｍを、ｉ＝１〜ｎの各iに対して、平文のブロックｍi
(ｍi＝(ｂ1'−１Ｍ)ｄｉ  modｂi  もしくはｍi＝(ｂ1'−１Ｍ)１／２ modｂi )へ変換するためのブロック復号手段、とを備える。
【０００９】
好ましくは、前記記憶部は秘密鍵としてさらに相異なる正整数Ｐ，Ｑを記憶すると共に、前記秘密鍵、正整数ｂi、正整数ｂi'−１、ｄiとして、
Ｐに対する秘密鍵ｂi(Ｐ)、ｂi'(Ｐ)−１、ｄi(Ｐ)、及び
Ｑに対する秘密鍵ｂi(Ｑ)、ｂi'(Ｑ)−１、ｄi(Ｑ)を記憶し、
前記中間復号手段は、Ｍ(Ｐ)＝ｕ−１Ｃ modＰ  と  Ｍ(Ｑ)＝ｕ−１Ｃ modＱ  の２つの中間平文を求め、
前記ブロック復号手段は、ｍi(Ｐ)＝(ｂi'(Ｐ)−１Ｍ)ｄi(Ｐ) modｂi(Ｐ) と
ｍi(Ｑ)＝(ｂi'(Ｑ)−１Ｍ)ｄi(Ｑ) modｂi(Ｑ) とを求めて、中国人の剰余定理により、平文のブロックｍi(ｍi≡ｍi(Ｐ)  modｂi(Ｐ) ，ｍi≡ｍi(Ｑ)  modｂi(Ｑ))を求める。
ことを特徴とする、請求項６の復号装置。
【００１０】
この発明の復号方法は、暗号文Ｃをｎ個の平文ブロックｍi(ｉ＝１〜ｎ)からなる平文ｍへ復号するために、
情報処理装置の記憶部に秘密鍵として、正整数ｕ−１と、ｉ＝１〜ｎの各ｉに対して、正整数ｂiと、正整数ｂi'−１と、正整数ｄi、とを記憶し、
前記情報処理装置の中間復号手段で、暗号文Ｃに秘密鍵ｕ−１を乗算して中間平文Ｍへ復号し、
前記情報処理装置のブロック復号手段で、中間平文Ｍを、ｉ＝１〜ｎの各iに対して、平文のブロックｍi(ｍi＝(ｂ1'−１Ｍ)ｄｉ  modｂi  もしくはｍi＝(ｂ1'−１Ｍ)１／２ modｂi )へ変換して、平文ｍへ復号する。
【００１１】
好ましくは、前記記憶部で秘密鍵としてさらに相異なる正整数Ｐ，Ｑを記憶すると共に、前記秘密鍵、正整数ｂi、正整数ｂi'−１、ｄiとして、
Ｐに対する秘密鍵ｂi(Ｐ)、ｂi'(Ｐ)−１、ｄi(Ｐ)、及び
Ｑに対する秘密鍵ｂi(Ｑ)、ｂi'(Ｑ)−１、ｄi(Ｑ)を記憶し、
前記中間復号手段で、Ｍ(Ｐ)＝ｕ−１Ｃ modＰ  と  Ｍ(Ｑ)＝ｕ−１Ｃ modＱ  の２つの中間平文Ｍ(Ｐ)，Ｍ(Ｑ)を求め、
前記ブロック復号手段で、ｍi(Ｐ)＝(ｂi'(Ｐ)−１Ｍ)ｄi(Ｐ) modｂi(Ｐ) と
ｍi(Ｑ)＝(ｂi'(Ｑ)−１Ｍ)ｄi(Ｑ) modｂi(Ｑ)とを求めて、中国人の剰余定理により、平文のブロックｍi(ｍi≡ｍi(Ｐ)  modｂi(Ｐ) ，ｍi≡ｍi(Ｑ)  modｂi(Ｑ))を求める。
【００１２】
この発明の復号プログラムは、暗号文Ｃをｎ個の平文ブロックｍiからなる平文ｍへ復号するために、
情報処理装置の記憶部に秘密鍵として、正整数ｕ−１と、ｉ＝１〜ｎの各ｉに対して、正整数ｂiと、正整数ｂi'−１と、正整数ｄi、とを記憶させる記憶命令と、
前記情報処理装置に、暗号文Ｃに秘密鍵ｕ−１を乗算して中間平文Ｍへ復号させるための中間復号命令と、
前記情報処理装置に、中間平文Ｍをｉ＝１〜ｎの各iに対して平文のブロックｍi
(ｍi＝(ｂ1'−１Ｍ)ｄｉ  modｂi  もしくはｍi＝(ｂ1'−１Ｍ)１／２ modｂi )へ変換させるためのブロック復号命令、とを備える。
【００１３】
好ましくは、前記記憶命令では記憶部に秘密鍵としてさらに相異なる正整数Ｐ，Ｑを記憶させると共に、前記秘密鍵、正整数ｂi、正整数ｂi'−１、ｄiとして、
Ｐに対する秘密鍵ｂi(Ｐ)、ｂi'(Ｐ)−１、ｄi(Ｐ)、及び
Ｑに対する秘密鍵ｂi(Ｑ)、ｂi'(Ｑ)−１、ｄi(Ｑ)を記憶させ、
前記中間復号命令で、Ｍ(Ｐ)＝ｕ−１Ｃ modＰ  と  Ｍ(Ｑ)＝ｕ−１Ｃ modＱ  の２つの中間平文Ｍ(Ｐ)，Ｍ(Ｑ)を求め、
前記ブロック復号命令で、ｍi(Ｐ)＝(ｂi'(Ｐ)−１Ｍ)ｄi(Ｐ) modｂi(Ｐ) と,
ｍi(Ｑ)＝(ｂi'(Ｑ)−１Ｍ)ｄi(Ｑ) modｂi(Ｑ) とを求めて、中国人の剰余定理により、平文のブロックｍi(ｍi≡ｍi(Ｐ)  modｂi(Ｐ) ，ｍi≡ｍi(Ｑ)  modｂi(Ｑ))を求める。
【００１４】
なおこの明細書で暗号化に関する記載は特に断らない限り、暗号化装置や暗号化方法、暗号化プログラムに当てはまり、復号に関する記載は特に断らない限り、復号装置や復号方法、復号プログラムに当てはまる。用いるパラメータは全て整数で、原則として正整数である。また法が自明な場合、法を特に断らない。
【発明の効果】
【００１５】
この発明では  Ｃ＝Σｉ＝１〜ｎ ａi・ｍiｅi   により暗号化するので、簡単に暗号化できる。また拡大平文長と暗号文とのビットサイズの比は、ｅiの値と共に増し、３以上で容易に１以上にできるので、低密度攻撃に対して安全である。さらに、公開鍵ａ＝(ａ1〜ａn)より秘密鍵を推定することは困難と考えられ、特に
・  Ｐに対する秘密鍵ｂi(Ｐ)、ｂi'(Ｐ)−１、ｄi(Ｐ)、及び
・  Ｑに対する秘密鍵ｂi(Ｑ)、ｂi'(Ｑ)−１、ｄi(Ｑ)の２系列の秘密鍵を用い、
・  中国人の剰余定理を用いて最終的な復号を行うと、秘密鍵がより露呈し難くなると考えられる。
【発明を実施するための最良の形態】
【００１６】
以下に本発明を実施するための最適実施例を示す。
【実施例】
【００１７】
実施例１
図１〜図４に、最初の実施例を示す。各図において、２は暗号通信装置で、暗号化装置４と復号装置６とからなり、通信部８を介してインターネット１０などの安全でない通信路を介して通信する。なお金融機関のサーバとクライアントとが暗号通信するような場合、クライアントは暗号化ができれば充分であり、サーバは復号ができれば充分である。従って暗号化装置４と、復号装置６とを共に１台の情報処理装置内に設ける必要はない。
【００１８】
暗号化装置４において、１２は入力バッファで平文ｍを記憶し、それをｎ個のブロック、例えば３個のブロックに分割して、平文ブロックｍiとして出力する。以下ｉはブロック番号を指し、ｎはブロックの総数で例えば３で、ｎは２以上で、３以上が好ましく、３が最も好ましい。１６，１７は乗算器で、平文ｍiをｅi乗、例えば各ｉに対して３乗してｍi３を出力し、公開鍵バッファ１４で記憶しているｎ個の公開鍵ａiと乗算器１８で乗算し、加算器１９で積算して暗号文Ｃとする。
【００１９】
復号装置６は通信部８から受信した暗号文Ｃを復号する。なお暗号化装置４で生成した暗号文Ｃと復号装置６で復号する暗号文Ｃは具体的な値が異なるものであるが、便宜的に同じ記号を用いる。２２は秘密鍵記憶部で、秘密鍵Ｎ，秘密鍵ｕ−１，秘密鍵ｂ1〜ｂ3及びｂ1'−１〜ｂ3'−１を記憶する。剰余乗算器２３はＭ＝ｕ−１Ｃ modＮからなる中間平文Ｍを求める。
【００２０】
剰余乗算器２４は中間平文Ｍに対し、ｂ1'−１Ｍ  modｂ1を求め、べき乗剰余算器２８は(ｂ1'−１Ｍ)ｄ１  modｂ1を求め、これは平文のブロックｍ1に等しい。同様に剰余乗算器２５とべき乗剰余算器２９で平文ブロックｍ2を求め、剰余乗算器２６とべき乗剰余算器３０で平文ブロックｍ3を求める。なおここでは平文ブロックｍ1〜ｍ3のそれぞれに対して剰余乗算器２４〜２６とべき乗剰余算器２８〜３０を設けたが、剰余乗算器２４とべき乗剰余算器２８のみを設けて、乗数や法並びにべき指数を平文ブロックに合わせて変更しても良い。得られた平文ブロックｍiを平文バッファ３２に記憶し、これらを連接して平文ｍを出力する。
【００２１】
図２に、実施例の暗号通信プログラム４０を示す。暗号通信プログラム４０は適宜のサーバやパーソナルコンピュータあるいは携帯電話などの携帯情報端末に記憶され、暗号化プログラム４１は公開鍵取得命令４２と積和演算命令４３とからなる。公開鍵取得命令４２は公開鍵ａ＝(ａ1，ａ2，ａ3)を取得し、パーソナルコンピュータなどの情報処理装置に記憶させる命令である。積和演算命令４３は情報処理装置に図１の暗号化装置４を実装し、その処理を実行させるための命令である。積和演算命令４３は、平文をｎ個のブロックに分割し、各ブロックを例えば３乗し、これに公開鍵の各成分ａiを乗算し、次いでａi・ｍi３を加算するための命令である。
【００２２】
復号プログラム４４は、図１の復号装置６を情報処理装置に実装させて図１の復号処理を実行させるための命令である。秘密鍵記憶命令４５は情報処理装置の記憶部に秘密鍵記憶部２２を設けて、秘密鍵を記憶するための命令である。中間平文復号命令４６は、暗号文Ｃに秘密鍵ｕ−１を乗算し、Ｎに対する剰余を求めるための命令である。ｂi'−１乗算命令４７は、中間平文Ｍにｂi'−１ を乗算するための命令で、べき乗剰余算命令４８はｂiを法とし、ｄiをべき指数とするべき乗剰余算を行うための命令である。命令４６〜４８により平文の各ブロックｍ1〜ｍ3が得られ、これらを連接すると平文ｍが得られる。
【００２３】
図３に、実施例での暗号化を示す。ステップ１で公開鍵ａを取得し、ステップ２で平文ｍと公開鍵とのべき乗積和演算を行い、暗号文  Ｃ＝Σｉ＝１〜ｎ ａi・ｍiｅi    を求める。なおｎは例えば３以上とするが、特に３が好ましい。ｅiは少なくともその１つが２以上で、特に少なくともその１つを３以上とすることが好ましい。より好ましくはｅiは全て３以上とし、最も好ましくはｅiは全て３とする。そしてステップ３で暗号文Ｃを出力する。
【００２４】
図４に復号プロセスを示す。受信した暗号文Ｃに対して  ｕ−１Ｃ modＮ  を求めてこれを中間平文Ｍとする(ステップ４)。次いでｉ＝１〜ｎの各ｉ毎に、秘密鍵ｂi'−１Ｍを法をｂiとして求め(ステップ５)、これをべき指数ｄiでべき乗し、ｂiを法とする剰余ｍiを求める(ステップ６)。これによって１ブロック文の平文ｍiが得られ、全てのブロックを復号すると、平文ｍが得られる(ステップ７，ステップ８)。
【００２５】
実施例１で用いた記号の意味を表１に示し、実施例１での復号アルゴリズムを表２に示す。
【００２６】
表１    実施例１での記号                              
｜Ｉ｜：          データ、例えばＩの、ビット数単位でのサイズ
Ｎ：              乱数型の正整数で法として用いる  秘密鍵
ｂ1,ｂ2,ｂ3：     乱数型の正整数で秘密鍵；ｂ1,ｂ2,ｂ3は互いに素で、
ｂi＝２ｈ＋εiで、例えば１＜＜εi＜＜２ｈ
ｂ1'−１,ｂ2'−１,ｂ3'−１：  秘密鍵でｂi'＝(ｂ1・ｂ2・ｂ3)／ｂi modＮで定義し、
ｂi'とｂiは互いに素となり、ｂi'−１はＮを法とするｂiの逆元
λ(ｘ)：          ｘのカーマイケル関数の値；なおカーマイケル関数自体は当業者に
周知の関数である
ｄi：             λ(ｂi)を法とするｅの逆元で秘密鍵
u−１：             秘密鍵;ｕとＮは互いに素
ｅ：              公開のシステムパラメータ  ただしｅ1，ｅ2、ｅ3のように、
ｉの値毎にｅの値を変えても良い
ａ1,ａ2,ａ3：     公開鍵；ａi＝ｕｂi'  modＮ
ｉ：              ａ1〜ａ3，ｂ1〜ｂ3等に用いる添字で、ｉ＝１〜ｎ；ｎは例えば３で                  ２以上
ｍ1〜ｍ3：        平文のブロック
Ｃ：              暗号文      Ｃ＝ａ1ｍ1ｅ＋ａ2ｍ2ｅ＋ａ3ｍ3ｅ
Ｍ：              中間平文    Ｍ＝ｂ1'ｍ1ｅ＋ｂ2'ｍ2ｅ＋ｂ3'ｍ3ｅ
＝ｕ−１Ｃ  modＮ
Ｒ：              レート；平文のサイズ／暗号文のサイズ
Ｄ：              密度；拡大平文のサイズ／暗号文のサイズ  Ｄ≧１が必要
*  全ての数は正または０の整数である
【００２７】
表２      実施例１での復号アルゴリズム                    
暗号文Ｃ→中間平文Ｍ      Ｍ＝ｕ−１Ｃ  modＮ＝ｂ1'ｍ1ｅ＋ｂ2'ｍ2ｅ＋ｂ3'ｍ3ｅ
平文ブロックｍiの復号     ｂ1'−１Ｍ＝ｍ1ｅ＋ｂ2−１ｂ1ｍ2ｅ＋ｂ1ｂ3−１ｍ3ｅ  等の関係が成立し、ｂ1を法とする剰余を求めると、ｍ1ｅが得られる．各ｉに付いて、
ｍi＝(ｂ1'−１Ｍ)ｄｉ    modｂi    なので、
ｍ＝(ｍ1,ｍ2,ｍ3)
【００２８】
パラメータについて説明すると、ｎの数が増すと公開鍵が増して、秘密鍵ｂi'の推定が可能になる恐れがある。この一方でｎが２では強度が不足するので、ｎは少なくとも２以上とするが、好ましくは３以上とし、最も好ましくはｎを３とする。ｂi並びにｍiをｈビット程度の正整数とすると、ｂi'ｍiｅは(ｅ＋２)ｈビット程度の数と考えられ、中間平文Ｍはこれから、(ｅ＋２)ｈ＋２ビット程度と考えられる。ＮはＭより大きいので、Ｎは(ｅ＋２)ｈ＋２ビット以上の数となる。ａiはＮよりも小さい乱数であるので、そのビット数をＮとほぼ同程度と考え、平文ブロックｍiのビット数をｈとすると、暗号文Ｃの各項のビット数は(２ｅ＋２)ｈ＋２ビット程度で与えられる。よって暗号文の合計のビット数は(２ｅ＋２)ｈ＋４ビット程度である。一方拡大平文長は３ｅｈで与えられるので、密度Ｄは  Ｄ=３ｅｈ／((２ｅ＋２)ｈ＋４)−１    となる。そこで(ｅ−２)ｈが４以上で、Ｄは１以上となる。ｅを３以上とすればＤは容易に１よりも大きくなる。ｅを４以上とすると、密度Ｄをさらに大きくできるが、ｅ＝３でも密度Ｄは１より充分大きくできる。この一方で、ｅを大きくすることは拡大平文長を長くし、伝送効率を低下させる。従ってｅは３が好ましい。なおｅが２の場合、ｅの逆元ｄiが存在しないことがあるので、ｂiを法とする
ｂi'−１Ｍの平方根を求める。
【００２９】
実施例２
図５に第２の実施例の復号装置５２を示し、暗号化装置は図１のものを用いる。また実施例２での記号の意味を表３に、復号アルゴリズムを表４に示す。実施例１に関する記載は、中国人の剰余定理を用いることと、これに伴い秘密鍵がＰに関するものとＱに関するものとの２系統となることを除き、実施例２にも当てはまる。実施例１と同じ記号や同じ用語は同じものを表し、５３は秘密鍵記憶部で、相異なる素数Ｐ，Ｑとｕ−１，ｂi(Ｐ)，ｂi(Ｑ)，ｂi'(Ｐ)−１，ｂi'(Ｑ)−１，ｄi(Ｐ)，ｄi(Ｑ)を記憶する。剰余乗算器５４はＰを法として
ｕ−１Ｃ  modＰ  を求め、剰余乗算器５５はＱを法として  ｕ−１Ｃ  modＱ  を求める。
【００３０】
剰余乗算器５６〜５８はｉ＝１〜３の各ｉ毎に、法をｂi(Ｐ)として乗数をｂi'(Ｐ)−１を乗算し、べき乗剰余算器６４〜６６は法をｂi(Ｐ)としてべき指数をｄi(Ｐ)としてべき乗剰余算を求める。同様にべき乗剰余算器６０〜６２は法をｂi(Ｑ)として乗数をｂi'(Ｑ)−１を求め、べき乗剰余算器６８〜７０で、法をｂi(Ｑ)としべき指数をｄi(Ｑ)としてべき乗剰余算を行う。中国人の剰余定理演算部７２〜７６は、平文ブロックｍiを求め、演算器７２〜７６は各ｉに付いて、べき乗剰余算器６４の出力ｍi(Ｐ)  modｂi(Ｐ)とべき乗剰余算器７０の出力ｍi(Ｑ)  modｂi(Ｑ)  と合同な数ｍiを求め、平文バッファ３２で平文ｍに変換する。
【００３１】
表３    実施例２での記号                              
Ｐ，Ｑ：        相異なる素数で秘密鍵
Ｎ：            合成法  Ｎ＝ＰＱ
ｂi(Ｐ)，ｂi(Ｑ)：  乱数型の正整数ベースで秘密鍵  ｂi(Ｐ)ｂi(Ｑ)＝２ｈ＋εi
１＜＜εi＜＜２ｈ
ｂi(Ｐ)，ｂi(Ｑ)(は同じiに対して)互いに素で、ｂi(Ｐ)とｂj(Ｐ)
及びｂi(Ｑ)とｂj(Ｑ)はiとjが異なれば互いに素
ｖi(Ｐ)，ｖi(Ｑ)：  乱数型の正整数  ｖi(Ｐ)はｂi(Ｐ)と(は同じiに対して)
互いに素で、
ｖi(Ｑ)はｂi(Ｑ)と(は同じiに対して)互いに素
ｖi(Ｐ)，ｖi(Ｑ)によりｂi'(Ｐ)とｂi(Ｐ)との関係が複雑になり、
ｂi'(Ｑ)とｂi(Ｑ)との関係も複雑になる
ｂi'(Ｐ)−１：      ｂi'(Ｐ)≡ｖi(Ｐ)Πｋ＝１−ｎｂk(Ｐ)／ｂi(Ｐ)  秘密鍵
ｂi'(Ｑ)−１：      ｂi'(Ｑ)≡ｖi(Ｑ)Πｋ＝１−ｎｂk(Ｑ)／ｂi(Ｑ)  秘密鍵
ｂi'：          ｂi'≡ｂi'(Ｐ)  modＰ，ｂi'≡ｂi'(Ｑ)  modＱ
ｄi(Ｐ)：         λ(ｂi(Ｐ))を法とするｅの逆元で秘密鍵
ｄi(Ｑ)：         λ(ｂi(Ｑ))を法とするｅの逆元で秘密鍵
ｕ−１：          ｕはＮと互いに素な数で、ｕ−１は秘密鍵
上記の各数はいずれも秘密
ａi：           公開鍵のｉ番目の成分
ａi＝uｂi' modＮ
ｂi'≡ｂi'(Ｐ)  modＰ，ｂi'≡ｂi'(Ｑ)  modＱ  なので、
ｂi'からｂi'(Ｐ)，ｂi'(Ｑ)が直接には得られない。
Ｃ：            暗号文      Ｃ＝ａ1ｍ1ｅ＋ａ2ｍ2ｅ＋ａ3ｍ3ｅ
Ｍ(Ｐ)：          中間平文    Ｍ(Ｐ)＝Σｋ＝１−ｎｂｋ'(Ｐ)ｍkｅ
＝ｕ−１Ｃ  modＰ
Ｍ(Ｑ)：          中間平文    Ｍ(Ｑ)＝Σｋ＝１−ｎｂｋ'(Ｑ)ｍkｅ
＝ｕ−１Ｃ  modＱ
*  実施例１と同じ記号は同じものを表す
【００３２】
表４      実施例２での復号アルゴリズム                    
ｍi(Ｐ)＝ｍi modｂi(Ｐ)とすると、ｍi(Ｐ)＝(ｂi'(Ｐ)−１Ｍ)ｄi(Ｐ)  moｄｂi(Ｐ)    同様にして、
ｍi(Ｑ)＝ｍi modｂi(Ｑ)とすると、ｍi(Ｑ)＝(ｂi'(Ｑ)−１Ｍ)ｄi(Ｑ)  moｄｂi(Ｑ)  
ｍi mod(ｂi(Ｐ)ｂi(Ｑ))≡ｍi(Ｐ)  modｂi(Ｐ) ，ｍi mod(ｂi(Ｐ)ｂi(Ｑ))
≡ｍi(Ｑ)  modｂi(Ｑ)
【００３３】
図２の暗号通信プログラム４０では、暗号化プログラム４１は実施例１と同じものを用いる。秘密鍵記憶命令４５は図５の秘密鍵記憶部５３に記憶する秘密鍵を記憶し、中間平文復号命令４６は図５の剰余乗算器５４，５５の処理を行って、２つの中間平文を求める。ｂi'−１乗算命令４７では、ｂi'(Ｐ)−１  とｂi'(Ｑ)−１  を剰余乗算器５６〜６２で求め、べき乗剰余算命令４８ではべき乗剰余算器６４〜７０での処理を行う。そしてこれ以外に中国人の剰余定理演算命令４９を設けて、情報処理装置に例えば３個の中国人の剰余定理演算器７２〜７６を実装させてその処理を行う。
【００３４】
暗号化の処理は図３と同じである。復号処理では図６のように、ステップ１０で２通りの中間平文Ｍ(Ｐ)，Ｍ(Ｑ)を求める。ステップ１１でｂi'(Ｐ)−１Ｍ(Ｐ)とｂi'(Ｑ)−１Ｍ(Ｑ)を求め、
ｄi(Ｐ)乗あるいはｄi(Ｑ)乗して、ｂi(Ｐ)あるいはｂi(Ｑ)  を法とする剰余を求めて、ｍi(Ｐ)とｍi(Ｑ)  を求める。そしてステップ１２で、中国人の剰余定理によりｍiを求め、ステップ１３で平文ｍを出力する。  
【００３５】
実施例２は特に指摘した点以外は実施例１と同様で、パラメータについてｎは３が好ましく、ｅも３が好ましい。また実施例２では、Ｐに関する秘密鍵とＱに関する秘密鍵の２系統の秘密鍵があるので、秘密鍵の構造がさらに複雑でより露呈しにくい。さらにｂi(Ｐ)からｂi'(Ｐ)への変換や、ｂi(Ｑ)から    ｂi'(Ｑ)への変換に、秘密鍵ではない秘密の数ｖi(Ｐ)やｖi(Ｑ)を用いている。このため秘密鍵がより露呈しにくくなっている。
【００３６】
平文ブロックｍiの長さは、実施例１の場合６０ビット以上が好ましく、実施例２では３０ビット以上が好ましい。さらに公開鍵のサイズは、実施例１でも実施例２でも比較的小さくできる。
【００３７】
公開鍵ａiを用いた攻撃を検討する。公開鍵ａiの定義から、ａiｂj'≡ａjｂi'  modＮ  が成立することが分かる。これからＣ1，ｃ2をｈビット程度の数として、ａ1ｂ2'−ａ2ｂ1'＝Ｃ1Ｎ，ａ1ｂ3'−ａ3ｂ1'＝ｃ2Ｎが成立する。Ｎを消去すると、
ａ1(ｃ2ｂ2'−Ｃ1ｂ3')−ａ2ｃ2ｂ1'＋ａ3Ｃ1ｂ1'＝０  が成立する。そこで公開鍵ａ1〜ａ3からこの不定方程式を解くことができれば、秘密鍵が露呈する。実施例１と実施例２をこの点から比較すると、実施例２ではｃ2ｂ2'などの各項を実施例１よりも大きくできる。このため実施例２は実施例１よりも、不定方程式を用いた攻撃に対してもより安全と考えられる。
【図面の簡単な説明】
【００３８】
【図１】実施例の暗号通信装置のブロック図
【図２】実施例の暗号通信プログラムのブロック図
【図３】実施例での暗号化アルゴリズムを示すフローチャート
【図４】実施例での復号アルゴリズムを示すフローチャート
【図５】第２の実施例での復号装置のブロック図
【図６】第２の実施例での復号アルゴリズムを示すフローチャート
【符号の説明】
【００３９】
２          暗号通信装置
４          暗号化装置
６，５２    復号装置
８          通信部
１０        インターネット
１２        入力バッファ
１４        公開鍵バッファ
１６〜１８  乗算器
１９        加算器
２２，５３  秘密鍵記憶部
２３〜２６  剰余乗算器
２８〜３０  べき乗剰余算器
３２        平文バッファ
４０        暗号通信プログラム
４１        暗号化プログラム
４２        公開鍵取得命令
４３        積和演算命令
４４        復号プログラム
４５        秘密鍵記憶命令
４６        中間平文復号命令
４７        ｂi'−１乗算命令
４８        べき乗剰余算命令
４９        中国人の剰余定理演算命令
５４〜６２  剰余乗算器
６４〜７０  べき乗剰余算器
７２〜７６  中国人の剰余定理演算部  
【図１】
2007219381.tif 000003
【図２】
2007219381.tif 000004
【図３】
2007219381.tif 000005
【図４】
2007219381.tif 000006
【図５】
2007219381.tif 000007
【図６】
2007219381.tif 000008