(57)【要約】【課題】  暗号化と復号とを高速で行え、低密度攻撃に強い公開鍵暗号を提供する。【解決手段】  暗号文Ｃに対して乗算器２１で秘密のパラメータｕ−１を乗算し、剰余算器２２で法Ｎに対する剰余を求め、中間メッセージＭとする。中間メッセージＭに乗算器２４で秘密のパラメータσ−１を乗算し、べき乗剰余算器２５で(γ＋１)／４乗し、ｍ''3を求め、ここにγは秘密の素数である。ｍ''3の最下位ビットが１であればそのままｍ'3とし、０であれば  ｍ'3＝γ−ｍ''3  として、中間メッセージＭから  Ｍ−σｍ'3２を求めて、メッセージの各成分ｍ1，ｍ2，ｍ3を復号する。【選択図】    図２
2007133221.tif 000002
【特許請求の範囲】
【請求項１】
少なくとも３つの部分ｍ1，ｍ2，ｍ3からなるメッセージの各部分もしくはそのべき乗と、いずれも正整数からなる少なくとも３つの公開鍵ａ1，ａ2，ａ3との積和演算を施した暗号文Ｃを復号するための装置であって、
暗号文Ｃに対し秘密のパラメータｕ−１を乗算し秘密の法Ｎとの剰余演算をすることにより、中間平文Ｍを得るための中間平文復号手段と、
中間平文Ｍに秘密のパラメータσ−１を乗算し、秘密の素数γを法とする平方根ｍ3''を１個求めるための平方根演算手段と、
求めた平方根ｍ3''の最下位ビットもしくは最上位ビットの値により、平方根ｍ3''をそのまま正しい平方根ｍ3'とするか、(γ−ｍ3'')を正しい平方根とするかを選択すると共に、平方根ｍ3'からメッセージの一部分ｍ3を求めるための平方根選択手段と、
(Ｍ−σｍ3'２)を求めてγで除算し、第２中間平文  Ｍ'＝(Ｍ−σｍ3'２)／γ  を求めるための手段と、
第２中間平文Ｍ'に対し  ｍ1≡β−１Ｍ'  modα，ｍ2≡α−１Ｍ'  modβ  となるように、秘密のパラメータα−１、β−１を乗算するための手段と、α、βとの法を剰余算するための手段とを備えて、メッセージの残りの部分ｍ1，ｍ2を復号するための積和部分の復号手段とを設けたことを特徴とする、復号装置。
【請求項２】
前記γは  γ mod４≡３  を充たし、前記平方根演算手段はσ−１Ｍの(γ＋１)／４乗のべき乗演算手段とγを法とする剰余算手段とを備えて、平方根ｍ3''を求めることを特徴とする、請求項１の復号装置。
【請求項３】
前記平方根選択手段は、平方根ｍ3''の最下位ビットをチェックするための手段と、最下位ビットが１で平方根ｍ3''をそのまま正しい平方根ｍ3'とし、最下位ビットが０で(γ−ｍ3'')を正しい平方根とするための手段と、平方根ｍ3'を所定ビット分右シフトして、メッセージの一部分ｍ3を求めるための手段とを備えていることを特徴とする、請求項１の復号装置。
【請求項４】
前記平方根選択手段は、平方根ｍ3''の最上位ビットをチェックするための手段と、最上位ビットが０で平方根ｍ3''をそのまま正しい平方根ｍ3'とし、最上位ビットが１で(γ−ｍ3'')を正しい平方根とするための手段とを備え、求めた平方根ｍ3'をメッセージの一部分ｍ3とすることを特徴とする、請求項１の復号装置。
【請求項５】
前記ｕ，ａ3，σは  ｕ≡ａ3σ−１  modＮ  との関係にあり、ｕのビット長をａ3のビット長及びσのビット長よりも５０％以上長くしたことを特徴とする、請求項１〜４のいずれかの復号装置。
【請求項６】
少なくとも３つの部分ｍ1，ｍ2，ｍ3からなるメッセージの各部分もしくはそのべき乗と、いずれも正整数からなる少なくとも３つの公開鍵ａ1，ａ2，ａ3との積和演算を施した暗号文Ｃを復号するための方法であって、
暗号文Ｃに対し秘密のパラメータｕ−１を乗算し、秘密の法Ｎとの剰余演算をして、中間平文Ｍを得、
得られた中間平文Ｍに秘密のパラメータσ−１を乗算し、秘密の素数γを法とする平方根ｍ3''を１個求め、
求めた平方根ｍ3''の最下位ビットもしくは最上位ビットの値により、ｍ3''をそのまま正しい平方根ｍ3'とするか、(γ−ｍ3'')を正しい平方根とするかを選択すると共に、
ｍ3''からメッセージの一部分ｍ3を求め、
(Ｍ−σｍ3'２)を求めてγで除算し、第２中間平文  Ｍ'＝(Ｍ−σｍ3'２)／γ  を求め、
第２中間平文Ｍ'に対し  ｍ1≡β−１Ｍ'  modα，ｍ2≡α−１Ｍ'  modβ  となるように、秘密のパラメータα−１、β−１を乗算し、α、βとの法を剰余算することにより、メッセージの残りの部分ｍ1，ｍ2を復号することを特徴とする、復号方法。
【請求項７】
少なくとも３つの部分ｍ1，ｍ2，ｍ3からなるメッセージの各部分もしくはそのべき乗と、いずれも正整数からなる少なくとも３つの公開鍵ａ1，ａ2，ａ3との積和演算を施した暗号文Ｃを復号するために、情報処理装置で実行される復号プログラムであって、
暗号文Ｃに対し秘密のパラメータｕ−１を乗算し、秘密の法Ｎとの剰余演算をすることにより、中間平文Ｍを得るための中間平文復号命令と、
中間平文Ｍに秘密のパラメータσ−１を乗算し、秘密の素数γを法とする平方根ｍ3''を１個求めるための平方根演算命令と、
求めた平方根ｍ3''の最下位ビットもしくは最上位ビットの値により、ｍ3''をそのまま正しい平方根ｍ3'とするか、(γ−ｍ3'')を正しい平方根とするかを選択すると共に、
ｍ3'からメッセージの一部分ｍ3を求めるための平方根選択命令と、
(Ｍ−σｍ3'２)を求めてγで除算し、第２中間平文  Ｍ'＝(Ｍ−σｍ3'２)／γ  を求めるための手段と、
第２中間平文Ｍ'に対し  ｍ1≡β−１Ｍ'  modα，ｍ2≡α−１Ｍ'  modβ  となるように、秘密のパラメータα−１、β−１を乗算し、かつα、βとの法を剰余算することにより、メッセージの残りの部分ｍ1，ｍ2を復号するための積和部分の復号命令とを設けたことを特徴とする、復号プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
この発明は積和型の公開鍵暗号システムに関し、特にその復号に関する。
【背景技術】
【０００２】
発明者らは積和型の公開鍵暗号システムを提案してきた(非特許文献１〜３)。積和型の暗号システムは、メッセージと暗号文とのビット長の比を密度Ｄとして、密度Ｄが低いことを利用した攻撃に弱いとの問題がある。そこで発明者は、暗号化や復号が容易でかつ密度が高い、新規な積和側の公開鍵暗号システムを検討してこの発明に到った。
【非特許文献１】M.Kasahara and Y.Murakami: "New product-sum type public-key cryptosystems" 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.
【発明の開示】
【発明が解決しようとする課題】
【０００３】
この発明の課題は、安全性が高く、暗号化や復号を高速で行える新規な積和型の公開鍵暗号システムに用いる、復号装置や復号方法、復号プログラムを提供することにある。
この発明での副次的な課題は、平方根演算を容易にすることにある。
この発明での他の副次的な課題は、２つの平方根の一方を得ることにより、求める平方根であるか否かを判別して、適切な平方根を得ることにある。
この発明での他の副次的な課題は、２乗演算を施した部分のビット長が長いことから暗号を解読されることへの対策を施すことにある。
【課題を解決するための手段】
【０００４】
この発明は、少なくとも３つの部分ｍ1，ｍ2，ｍ3からなるメッセージの各部分もしくはそのべき乗と、いずれも正整数からなる少なくとも３つの公開鍵ａ1，ａ2，ａ3との積和演算を施した暗号文Ｃを復号するための装置であって、
暗号文Ｃに対し秘密のパラメータｕ−１を乗算し秘密の法Ｎとの剰余演算をすることにより、中間平文Ｍを得るための中間平文復号手段と、
中間平文Ｍに秘密のパラメータσ−１を乗算し、秘密の素数γを法とする平方根ｍ3''を１個求めるための平方根演算手段と、
求めた平方根ｍ3''の最下位ビットもしくは最上位ビットの値により、平方根ｍ3''をそのまま正しい平方根ｍ3'とするか、(γ−ｍ3'')を正しい平方根とするかを選択すると共に、平方根ｍ3'からメッセージの一部分ｍ3を求めるための平方根選択手段と、
(Ｍ−σｍ3'２)を求めてγで除算し、第２中間平文  Ｍ'＝(Ｍ−σｍ3'２)／γ  を求めるための手段と、
第２中間平文Ｍ'に対し  ｍ1≡β−１Ｍ'  modα，ｍ2≡α−１Ｍ'  modβ  となるように、秘密のパラメータα−１、β−１を乗算するための手段と、α、βとの法を剰余算するための手段とを備えて、メッセージの残りの部分ｍ1，ｍ2を復号するための積和部分の復号手段とを設けたことを特徴とする。
【０００５】
好ましくは、前記γは  γ mod４≡３  を充たし、前記平方根演算手段はσ−１Ｍの(γ＋１)／４乗のべき乗演算手段とγを法とする剰余算手段とを備えて、平方根ｍ3''を求める。
【０００６】
好ましくは、前記平方根選択手段は、平方根ｍ3''の最下位ビットをチェックするための手段と、最下位ビットが１で平方根ｍ3''をそのまま正しい平方根ｍ3'とし、最下位ビットが０で(γ−ｍ3'')を正しい平方根とするための手段と、平方根ｍ3'を所定ビット分右シフトして、メッセージの一部分ｍ3を求める。
あるいは好ましくは、前記平方根選択手段は、平方根ｍ3''の最上位ビットをチェックするための手段と、最上位ビットが０で平方根ｍ3''をそのまま正しい平方根ｍ3'とし、最上位ビットが１で(γ−ｍ3'')を正しい平方根とするための手段とを備え、求めた平方根ｍ3'をメッセージの一部分ｍ3とする。
【０００７】
好ましくは、前記ｕ，ａ3，σは  ｕ≡ａ3σ−１  modＮ  との関係にあり、ｕのビット長をａ3のビット長及びσのビット長よりも５０％以上長くする。
【０００８】
この発明は、少なくとも３つの部分ｍ1，ｍ2，ｍ3からなるメッセージの各部分もしくはそのべき乗と、いずれも正整数からなる少なくとも３つの公開鍵ａ1，ａ2，ａ3との積和演算を施した暗号文Ｃを復号するための方法であって、
暗号文Ｃに対し秘密のパラメータｕ−１を乗算し、秘密の法Ｎとの剰余演算をして、中間平文Ｍを得、
得られた中間平文Ｍに秘密のパラメータσ−１を乗算し、秘密の素数γを法とする平方根ｍ3''を１個求め、
求めた平方根ｍ3''の最下位ビットもしくは最上位ビットの値により、ｍ3''をそのまま正しい平方根ｍ3'とするか、(γ−ｍ3'')を正しい平方根とするかを選択すると共に、
ｍ3''からメッセージの一部分ｍ3を求め、
(Ｍ−σｍ3'２)を求めてγで除算し、第２中間平文  Ｍ'＝(Ｍ−σｍ3'２)／γ  を求め、
第２中間平文Ｍ'に対し  ｍ1≡β−１Ｍ'  modα，ｍ2≡α−１Ｍ'  modβ  となるように、秘密のパラメータα−１、β−１を乗算し、α、βとの法を剰余算することにより、メッセージの残りの部分ｍ1，ｍ2を復号することを特徴とする。
【０００９】
またこの発明は、少なくとも３つの部分ｍ1，ｍ2，ｍ3からなるメッセージの各部分もしくはそのべき乗と、いずれも正整数からなる少なくとも３つの公開鍵ａ1，ａ2，ａ3との積和演算を施した暗号文Ｃを復号するために、情報処理装置で実行される復号プログラムであって、
暗号文Ｃに対し秘密のパラメータｕ−１を乗算し、秘密の法Ｎとの剰余演算をすることにより、中間平文Ｍを得るための中間平文復号命令と、
中間平文Ｍに秘密のパラメータσ−１を乗算し、秘密の素数γを法とする平方根ｍ3''を１個求めるための平方根演算命令と、
求めた平方根ｍ3''の最下位ビットもしくは最上位ビットの値により、ｍ3''をそのまま正しい平方根ｍ3'とするか、(γ−ｍ3'')を正しい平方根とするかを選択すると共に、
ｍ3'からメッセージの一部分ｍ3を求めるための平方根選択命令と、
(Ｍ−σｍ3'２)を求めてγで除算し、第２中間平文  Ｍ'＝(Ｍ−σｍ3'２)／γ  を求めるための手段と、
第２中間平文Ｍ'に対し  ｍ1≡β−１Ｍ'  modα，ｍ2≡α−１Ｍ'  modβ  となるように、秘密のパラメータα−１、β−１を乗算し、かつα、βとの法を剰余算することにより、メッセージの残りの部分ｍ1，ｍ2を復号するための積和部分の復号命令とを設けたことを特徴とする。
【発明の効果】
【００１０】
この発明では、暗号文Ｃに対し、秘密のパラメータｕ-1を乗算し、秘密の法Ｎに対する剰余を求めて、中間平文Ｍとする。すると中間平文Ｍは秘密のパラメータα，β，γ，σに対し、Ｍ≡βγｍ1＋αγｍ2＋σｍ3２  との関係があるように、少なくとも３つの公開鍵ａ1，ａ2，ａ3が選ばれている。そこで中間平文Ｍに秘密のパラメータσ−１  を乗算し、γを法とする平方根を求める。このような平方根には一般に２根があり、その一方がメッセージの一部分ｍ3に対応し、他方はｍ3に対応しない。ここで平方根を１個求めて、その値をｍ3''とすると、その下位ビットもしくは最上位ビットにより、ｍ3''が正しい平方根ｍ3'に対応するか、そうでないかが判明する。正しい平方根に対応しない場合、(γ−ｍ3'')が正しい平方根ｍ3'に対応する。また正しい平方根ｍ3'が得られると、その値を例えば所定ビットだけ右シフトして最下位ビット等を切り捨てる、あるいは正しい平方根ｍ3'をそのままｍ3とする等により、メッセージの一部分ｍ3が得られる。
【００１１】
中間平文Ｍからσｍ3'2を引くと、  βγｍ1＋αγｍ2  が得られる。これはγの倍数なので、γで除算し、β−１を乗算して、αを法として剰余算を行うと、メッセージの一部分ｍ1が得られる。同様にα−１を乗算し、βを法として剰余算すると、メッセージの残りの部分ｍ2が得られる。このようにしてメッセージの各部分ｍ1，ｍ2，ｍ3を復号できる。なおメッセージは少なくとも３つの部分ｍ1，ｍ2，ｍ3からなり、より多数個の部分を設けても良い。例えばメッセージをｍ1〜ｍnとし、公開鍵をａ1〜ａnとして、
Σｍiａi＋ｍ3２ａ3  （iは１，２または４〜ｎで３を除く）等としても良い。さらにこの明細書でのメッセージは平文の他に、これを符号化したものや、公知の他の暗号システムにより平文を暗号化したものなどを含んでいる。
【００１２】
この発明では、平方根演算以外の部分は単純な演算で構成されているので、高速で復号できる。またｍ3'を求める過程で、２つの平方根を共に求める必要はなく、その一方の平方根を求めると、最下位ビットもしくは最上位ビットを検査して、ｍ3'に対応する正しい平方根かどうかをチェックし、正しい平方根でない場合、(γ−ｍ3'')から正しい平方根ｍ3'を求める。ｍ3'は簡単にメッセージの一部分ｍ3に変換でき、またｍ3'とσとからメッセージの残りの部分ｍ1，ｍ2のみに由来する第２の中間平文Ｍ'を求めることができる。そして第２の中間平文Ｍ'が得られれば、メッセージの残りの部分ｍ1，ｍ2も得ることができる。
【００１３】
積和型の公開鍵暗号では、拡大平文の長さと暗号文との長さの比、即ち密度Ｄが問題となり、密度が低い場合には低密度攻撃が成立しやすい。この発明では、メッセージの一部分ｍ3を２乗しているので、拡大平文のビット長において、ｍ3に由来する部分が２倍に引き伸ばし、密度を１以上にできる。
【００１４】
γを法とする平方根演算は一般に複雑な計算を要する。ここでγmod４≡３としておくと、(γ＋１)／４乗し、γとの剰余を求めると、平方根ｍ3''を求めることができる。このため平方根演算を簡単にできる。
【００１５】
メッセージの暗号化において、メッセージｍ3を例えば１ビット左シフトして、最下位ビットに１ビット加算している場合、平方根ｍ3''の最下位ビットが１であれば正しい平方根ｍ3'であり、最下位ビットが０であればｍ3'以外の平方根である。この場合正しい平方根ｍ3'は(γ−ｍ3'')なので、ｍ3''の符号を反転し、γから引くと正しい平方根ｍ3'を得ることができる。そして正しい平方根ｍ3'を例えば１ビット右シフトして、最下位ビットの１を切り捨てたものがメッセージの一部分ｍ3である。
【００１６】
暗号化の過程で、メッセージの一部分ｍ3を左シフトしていない場合、求めた平方根    ｍ3''の最上位ビットが０で正しい平方根ｍ3'が得られており、最上位ビットが１の場合、(γ−ｍ3'')が正しい平方根ｍ3'となる。この場合は、正しい平方根ｍ3'がそのままメッセージの一部分ｍ3となる。
【００１７】
暗号文Ｃにおいて、ａ3ｍ32の項がａ1ｍ1やａ2ｍ2の項よりもビット長が長くなると、
ｍ32に由来する項から攻撃される可能性がある。同様に中間平文Ｍにおいて、σｍ32の項がβγｍ1やαγｍ2の項よりも大きいと、σｍ32の項が解読の手掛かりとなることがある。このためにはａ3ｍ32の項のビット長がａ1ｍ1の項やａ2ｍ2の項のビット長とほぼ等しくなり、同様にσｍ32の項のビット長がβγｍ1のビット長やαγｍ2のビット長とほぼ等しくなるようにすることが好ましい。そこで公開鍵中のａ3をａ1やａ2よりも短くし、同様にσをβγやαγよりも短くし、ｕ≡ａ3σ−１modＮ  とすると、暗号文Ｃや中間平文Ｍにおいて、  ｍ32に由来する項と他の項とを分離することが困難となる。ｕのビット長はａ3のビット長及びσのビット長よりも好ましくは５０％以上長くし、特に好ましくは１００％以上長くする。
【発明を実施するための最良の形態】
【００１８】
以下に本発明を実施するための最適実施例を示す。
【実施例】
【００１９】
図１〜図６に、実施例とその変形とを示す。図１〜図４において、２は暗号化装置で、４は復号装置である。暗号化装置２と復号装置４とをパーソナルコンピュータなどの適宜の情報処理装置に設けて、図示しない通信部を介してインターネットなどを介して暗号通信する。例えばメッセージは３つの部分ｍ1，ｍ2，ｍ3からなり、ｍ1及びｍ2のビット長は６０ビット程度、ｍ3のビット長は９０ビット程度とする。またａ1，ａ2，ａ3は公開鍵で、それぞれ正整数からなり、ａ1とａ2のビット長は例えば２１０ビット程度、ａ3のビット長は９０ビット程度とする。そしてｍ3に対して左シフト演算器１２で１ビット左シフトし、加算器１３で最下位ビットに１加算し、乗算器１４で２乗してｍ3'2とする。次に乗算器１５〜１７によりｍ1，ｍ2，ｍ3'2に公開鍵ａ1，ａ2，ａ3を乗算し、加算器１８，１９で加算して、暗号文Ｃとする。このため高速で暗号文Ｃを作成することができる。
【００２０】
実施例での主な記号と式を以下に示す。
記号リストと主な式
Ｎ：                秘密の正整数で例えば２１２ビットの素数
α、β、γ、σ：    秘密の正整数；  
α、β、γは互いに素で、σはγ及びＮと互いに素でγは素数
α、βを例えば約６０ビット（ｋ＋１ビット）、
γは例えば９０ビット（Ｌ＋１ビット）  σは例えば３０ビット
ａ1，ａ2，ａ3：     正整数からなる公開鍵で、ａ3はＮと互いに素、ａ3のビット長
｜ａ3｜はａ1，ａ2のビット長｜ａ1｜，｜ａ2｜よりも短く、
｜ａ1ｍ1｜≒｜ａ2ｍ2｜≒｜ａ3ｍ3２｜
また同様に  ｜βγｍ1｜≒｜αγｍ2｜≒｜σｍ3２｜
例えば  ｜ａ1｜≒｜ａ2｜≒２１２ビット、｜ａ3｜≒９２ビット
ｍ1，ｍ2，ｍ3：     メッセージの各部分  なおｍ3には１ビットの左シフトを施す
ことがあるが、シフト前のものもシフト後のものも、共にｍ3
ということがある
ｍ1やｍ2はｋビットデータで、ｍ3はＬ−１ビットデータ
Ｃ：                暗号文      Ｃ＝ａ1ｍ1＋ａ2ｍ2＋ａ3ｍ3'２          (1)
ｕ：                秘密のパラメータで  ｕ≡ａ3σ−１  modＮ            (2)
ａ3及びσに対して、ｕのビット長が充分長くなるように定め、
例えば２１２ビット
ａ1≡ｕβγ  modＮ；ａ2≡ｕαγ  modＮ             (3)
Ｍ：                中間平文   
Ｍ≡ｕ−１Ｃ  modＮ＝βγｍ1＋αγｍ2＋σｍ3２        (4)
ｍ3≡(σ−１Ｍ)１／２  modγ                            (5)
ｍ3''：            σ−１Ｍに対するべき乗剰余演算の結果で、(σ−１Ｍ)のγを法
とする２つの平方根の一方  正しい平方根はｍ3''の最下位ビット                      または最上位ビットにより判明
ｍ3'：              ｍ3''から求めた正しい平方根
Ｍ'：               ｍ1，ｍ2に由来する中間平文
Ｍ’＝(Ｍ−σｍ3２)／γ                              (6)
ｍ1≡β−１Ｍ’  modα，ｍ2≡α−１Ｍ’  modβ          (7)
Ｄ：                密度；  拡大平文(ビット長≒｜ｍ1｜＋｜ｍ2｜＋２｜ｍ3｜)
と暗号文長との比，  Ｄ≒(２ｋ＋２Ｌ)／(３ｋ＋Ｌ)    (8)
｜ｕ｜が｜ａ3｜や｜σ｜よりも充分に長いとの条件で、
Ｄを１以上にできる。
【００２１】
復号装置４について説明する。中間メッセージ復号部２０で、乗算器２１と剰余算器２２とにより、暗号文Ｃを中間平文Ｍに変換する。暗号文Ｃは式(1)で与えられるので、これにｕ-1を乗算し、Ｎとの法を求めると、式(4)のように、中間平文Ｍが定まる。
【００２２】
中間平文Ｍにおいてβγｍ1やαγｍ2はγの倍数で、他にσｍ32の項がある。そこで平方根演算部２３では、乗算器２４によりσ-1を乗算し、べき乗剰余算器２５でγを法として  (γ＋１)／４乗を求める。これによってｍ3'2の平方根の一方、ｍ3''が求まる。なおべき乗剰余算器２５に代えて、文字通りの平方根演算器を用いても良いが、演算アルゴリズムが複雑になる。
【００２３】
得られた平方根ｍ3''はｍ3'2の平方根の一方で、ｍ3'に対応する正しい平方根であるかどうかは不明である。そこで平方根選択部２６にスイッチ２７を設けて、平方根ｍ3''の最下位ビットが１であればそのまま平方根ｍ3'とし、最下位ビットが０であれば乗算器２８で符号を逆転し、加算器２９でγを加えて、(γ−ｍ3'')を平方根ｍ3'とする。暗号化装置２では、ｍ3'の最下位ビットを１にセットしている。なおｍ3'２の平方根は一方が最下位ビットが１で、他方が０であり、これらの和はγである。
【００２４】
平方根ｍ3'が得られると、中間平文Ｍからσｍ3'2を引き算すると、メッセージｍ1，ｍ2に由来する項のみが残る。そこで２乗成分除去部３０では乗算器３２でｍ3'を２乗し、乗算器３３で−σを乗算し、加算器３４で中間平文Ｍと加算することにより、ｍ−σｍ3'2を求める。この値は  γ(βｍ1＋αｍ2)  なので、乗算器３６でγ-1を乗算して第２中間平文Ｍ'を求め、乗算器３７でβ-1を乗算し、剰余算器３８でαを法とする剰余を求めると、メッセージの一部分ｍ1が求まる。同様に乗算器３６の出力Ｍ'に対し、乗算器３９でα-1を乗算し、剰余算器４０でβを法とする剰余を求めると、メッセージの一部分ｍ2が求まる。また前記の平方根ｍ3'に対し、右シフト演算器４２で例えば１ビット右シフトすると、メッセージの残りの部分ｍ3が求まる。
【００２５】
ここで数値例を示すと、αやβは例えば６０ビット程度の正整数とし、γは９０ビット程度の正整数とし、γのビット長はαやβよりも長くする。さらに法Ｎは２１０ビット程度とし、σは３０ビット程度とし、ｕやａ1，ａ2は２１０ビット程度のビット長、ａ3は９０ビット程度のビット長とし、ｕの５０％以下とする。すると暗号文Ｃにおいて、ａ1ｍ1やａ2ｍ2，ａ3ｍ32の項はそれぞれ２７０ビット程度となり、各項を分離することは困難となる。また中間平文Ｍでも各項はそれぞれ２１０ビット程度となり、σｍ32の項を分離できなくなる。このため２乗の項を求めたことに基づく攻撃が困難になる。次にγを法とする平方根演算は一般に複雑な演算であるが、これを(γ＋１)／４乗のべき乗に変換し、スイッチ２７により最下位ビットの値を利用して、正しい平方根かそれ以外の平方根かを判別すると、簡単に平方根ｍ3'を求めることができる。
【００２６】
実施例での暗号文の密度について検討すると、αやβをｋビット程度、例えば６０ビット程度、γをＬビット程度、例えば９０ビット程度とすると、密度Ｄは(２ｋ＋２Ｌ)／(３ｋ＋Ｌ)程度となり、前記の数値例では約１．１１となる。この結果低密度攻撃は困難になる。
【００２７】
図４に、実施例の復号プログラムを示す。中間平文復号命令４４は暗号文Ｃを中間平文Ｍに変換し、その手続は暗号文Ｃにｕ-1を乗算して法Ｎに対する剰余を求めることである。平方根演算命令４５では、中間平文Ｍにσ-1を乗算し(γ＋１)／４乗し、γを法とする剰余を求めることにより、１つの平方根ｍ3''を求める。平方根選択命令４６では、得られた平方根ｍ3''の最下位ビットを検査し、この値が１でそのまま平方根ｍ3'とし、０で    (γ−ｍ3'')を平方根ｍ3'とする。２乗成分除去命令４７では、σｍ3'2を中間平文Ｍから引き算して、Ｍ−σｍ3'2を求める。積和部分の復号命令４８では、２乗成分を除去した後のデータにγ-1を乗算して第２中間平文Ｍ'とする。そして第２中間平文Ｍ'にβ-1を乗算して、αを法とする剰余を求めることによりメッセージの一部分ｍ1を求める。また第２中間平文Ｍ'に  α-1を乗算して、βを法とする剰余を求めることにより、メッセージの一部分ｍ2を求める。メッセージの残りの部分ｍ3は、平方根ｍ3'を１ビット右シフトすることにより得られる。
【００２８】
図５に変形例の暗号化装置５２を示し、図６にこれに対応する復号装置６４を示す。図１，図２との違いは、メッセージの一部分ｍ3に対し、１ビットの左シフトと最下位ビットへの１加算を行っていない点である。図１，図２ではｍ3'はＬビットデータであるが、図５，図６ではｍ3'はＬ−１ビットデータで、図１，図２の場合よりも１ビット短い。そこでべき乗剰余算器２５で平方根ｍ3''を求めると、最上位ビットが０で正しい平方根ｍ3'となる。これに対応して、スイッチ６７では所定のビット長データ（Ｌ−１ビット）の平方根ｍ3''の最上位ビットを検査し、この値が０でそのままｍ3''＝ｍ3'とし、最上位ビットが１で(γ−ｍ3'')をｍ3'とする。ｍ3をｍ3'に変換する際に１ビットの左シフトを行っていないので、ｍ3'はそのままｍ3となる。他の点は図１，図２の例と同様である。
【００２９】
実施例は特定の例を示したがこれに限るものではない。特にメッセージｍ1，ｍ2，ｍ3は直接に平文でのメッセージである必要はなく、これにモジュラー変換やプリコーディングなどを施した中間的な平文でも良い。
【図面の簡単な説明】
【００３０】
【図１】実施例の復号装置に対応する暗号化装置でのデータの流れを示す図
【図２】実施例の復号装置でのデータの流れを示す図
【図３】図２の復号装置のブロック図
【図４】実施例の復号プログラムのブロック図
【図５】変形例の復号装置に対応する暗号化装置でのデータの流れを示す図
【図６】変形例の復号装置でのデータの流れを示す図
【符号の説明】
【００３１】
２，５２      暗号化装置
４，６４      復号装置
１２          左シフト演算器
１３          加算器
１４          乗算器
１５〜１７    乗算器
１８，１９    加算器
２０          中間メッセージ復号部
２１          乗算器
２２          剰余算器
２３          平方根演算部
２４          乗算器
２５          べき乗剰余算器
２６          平方根選択部
２７，６７    スイッチ
２８          乗算器
２９          加算器
３０          ２乗成分除去部
３２，３３    乗算器
３４          加算器
３６          乗算器
３７，３９    乗算器
３８，４０    剰余算器
４２          右シフト演算器
４４          中間メッセージ復号命令
４５          平方根演算命令
４６          平方根選択命令
４７          ２乗成分除去命令
４８          積和部分の復号命令
【図１】
2007133221.tif 000003
【図２】
2007133221.tif 000004
【図３】
2007133221.tif 000005
【図４】
2007133221.tif 000006
【図５】
2007133221.tif 000007
【図６】
2007133221.tif 000008