復号装置と復号プログラム及び暗号通信システム
【課題】 安全で情報化率の高い公開鍵暗号を提供する。
【解決手段】 ゴッパ符号等の符号化行列Ｇを左右に２回繰り返し、乱数ベクトルＲを１行追加した行列Ｋを用いて、ｋ＋１次元のメッセージｍを符号化し、Ｃ１とする。２ｎ次元よりも短いベクトルｅを非線形変換して加算しＣ２を求め、Ｃ１と加算して暗号文Ｃとする。Ｃに置換行列Ｐ-1を作用させた後に、左半分と右半分とを加算し、これらの排他加算を行い、位置ｊでの成分からｍk+1を求め、(Ｃ２Ｐ-1)Ｒ(+)(Ｃ２Ｐ-1)Ｌを求める。
Ｃ２Ｐ-1 ＝(ＸＬ,ＹＬ,ＹＲ,ＸＲ) かつ ＹＬ＝αＹＲ となるようにし、Ｇの訂正能力を用いてＹＬを求め、Ｃ２Ｐ-1を決定する。またＧの訂正能力を用いてｍを復号する。
【解決手段】 ゴッパ符号等の符号化行列Ｇを左右に２回繰り返し、乱数ベクトルＲを１行追加した行列Ｋを用いて、ｋ＋１次元のメッセージｍを符号化し、Ｃ１とする。２ｎ次元よりも短いベクトルｅを非線形変換して加算しＣ２を求め、Ｃ１と加算して暗号文Ｃとする。Ｃに置換行列Ｐ-1を作用させた後に、左半分と右半分とを加算し、これらの排他加算を行い、位置ｊでの成分からｍk+1を求め、(Ｃ２Ｐ-1)Ｒ(+)(Ｃ２Ｐ-1)Ｌを求める。
Ｃ２Ｐ-1 ＝(ＸＬ,ＹＬ,ＹＲ,ＸＲ) かつ ＹＬ＝αＹＲ となるようにし、Ｇの訂正能力を用いてＹＬを求め、Ｃ２Ｐ-1を決定する。またＧの訂正能力を用いてｍを復号する。
【発明の詳細な説明】
【技術分野】
【０００１】
この発明は、公開鍵暗号に関し、特にその復号装置と復号プログラム、及び暗号通信装置に関する。
【背景技術】
【０００２】
非特許文献１でMcElieceは、ゴッパ符号などを用いた公開鍵暗号システムを提案している。このシステムでは、ｋ行ｎ列の符号化行列をＧ、ｋ×ｋの正則行列をＳ、ｎ×ｎの置換行列をＰとして、メッセージｍ、ノイズｅを用いて、 ｍＳＧＰ(＋)ｅ を暗号文とする。復号側ではＰ-1が既知なことから、 ｍＳＧ(＋)ｅＰ-1 を求め、Ｐが置換行列で、ｅとｅＰ-1とで０でない成分の数が増さないことから、ｍＳＧ(＋)ｅＰ-1がｍＳへ誤り訂正可能な範囲で有れば、ｍＳを介してｍへ復号できる。
非特許文献２のNiderreiterのシステムでは、ｎ×(ｎ−ｋ)の検査行列Ｈと、(ｎ−ｋ)×(ｎ−ｋ)の正則行列Ｓと、ｎ×ｎの置換行列Ｐを用い、ＰＨＳを公開鍵とする。メッセージｍに対してｍＰＨＳを暗号文とする。復号側では、ｍＰＨＳをｍＰＨへ変換し、検査行列Ｈに対する誤り訂正でｍＰを求めて、メッセージｍを復号する。
【非特許文献１】R.J.McEliece: "A public-key cryptosystem based on algebraic coding theory", Deep Space Network Progress Report 42-44,pp114-116, Jet Propulsion Lab., Pasadena,CA (1978)
【非特許文献２】H.Niderreiter: "Error-correcting codes and cryptography" in "Public-Key Cryptography and Computational Number Theory" edited by K.Alster, J.Urbanowicz and H.C.Williams, Walter de Gruyter,(2001)
【０００３】
これらのシステムでの暗号強度は、符号化行列Ｇや検査行列Ｈの多様さ、言い換えるとこれらの曖昧さに依存し、行列Ｇ,Ｈが推定可能であれば安全ではない。そこで行列Ｇ,Ｈの推定困難性のみに根拠を置く暗号は、必ずしも安全とは言えない。McElieceのシステムでは乱数を加えて強度を高めているが、乱数は誤り訂正可能な範囲に限られ、例えばｎ次元のベクトルに対してｎ個の乱数成分を付加することはできない。また平文長と暗号文長との比を情報化率と呼ぶと、誤り訂正のために、これらのシステムでは情報化率を高くできない。
【発明の開示】
【発明が解決しようとする課題】
【０００４】
この発明の基本的課題は、誤り訂正を用いたより安全な暗号システムのための復号装置と復号プログラム、及び暗号通信装置を提供することにある。
この発明での副次的課題は、暗号に用いるノイズの少なくとも一部をメッセージとして、情報化率を高めることにある。
【課題を解決するための手段】
【０００５】
この発明は、メッセージｍを誤り訂正可能な符号に符号化したものにノイズｅを混合した暗号文を、前記符号の誤り訂正能力を用いて平文へ復号する復号装置において、
受信した暗号文Ｃに由来するベクトルＣＰ-1から、例えばベクトルＣＰ-1を左右に分割して、少なくとも２つのサブベクトルＣＰ-1Ｒ,ＣＰ-1Ｌを生成するための手段と、
前記少なくとも２つのサブベクトルＣＰ-1Ｌ,ＣＰ-1Ｒを組み合わせてベクトルＢを求めるための手段と、
ベクトルＢの特定の成分から、少なくともデータｍ~k+1を求めるための手段と、
既知の乱数とデータｍ~k+1とから、ベクトルＢもしくはベクトルＣＰ-1の、少なくとも一部の成分に対して、前記既知乱数に由来する成分を消去したデータを求めるための手段と、
前記既知乱数に由来する成分を除去したデータから、誤り訂正によりメッセージｍを復号するための手段とを設けたことを特徴とする。
なおデータｍ~k+1をメッセージへと復号しても良く、あるいはそのまま中間変数として捨てても良い。
【０００６】
好ましくは、既知乱数に由来する成分を除去したデータから、例えばメッセージｍの復号の誤り訂正により、ノイズをメッセージとして復号するための手段を設ける。
特に好ましくは、メッセージｍを復号する際の誤り訂正によりノイズの一部を復号すると共に、ベクトルＢから既知乱数に由来する成分を除去したデータと組み合わせて、ノイズの他の部分を復号する手段を設ける。
【０００７】
この発明は、メッセージｍを誤り訂正可能な符号に符号化したものにノイズｅを混合した暗号文を、前記符号の誤り訂正能力を用いて平文へ復号するための復号プログラムにおいて、
受信した暗号文Ｃに由来するベクトルＣＰ-1から、少なくとも２つのサブベクトル
ＣＰ-1Ｒ,ＣＰ-1Ｌを生成するための命令と、
前記少なくとも２つのサブベクトルＣＰ-1Ｌ,ＣＰ-1Ｒを組み合わせてベクトルＢを求めるための命令と、
ベクトルＢの特定の成分から、少なくともデータｍ~k+1を求めるための手段と、
既知の乱数とデータｍ~k+1とから、ベクトルＢもしくはベクトルＣＰ-1の、少なくとも一部の成分に対して、前記既知乱数に由来する成分を消去したデータを求めるための命令と、
前記既知乱数に由来する成分を除去したデータから、誤り訂正によりメッセージｍを復号するための命令とを設けたことを特徴とする。
【０００８】
この発明は、通信手段と、メッセージｍを誤り訂正可能な符号に符号化したものにノイズｅを混合して暗号化するための暗号化手段と、受信した暗号文を前記符号の誤り訂正能力を用いて平文へ復号するための復号手段とを備えた暗号通信装置において、
前記復号手段は、
受信した暗号文Ｃに由来するベクトルＣＰ-1から、少なくとも２つのサブベクトル
ＣＰ-1Ｒ,ＣＰ-1Ｌを生成するための手段と、
前記少なくとも２つのサブベクトルＣＰ-1Ｌ,ＣＰ-1Ｒを組み合わせてベクトルＢを求めるための手段と、
ベクトルＢの特定の成分から、少なくともデータｍ~k+1を求めるための手段と、
既知の乱数とデータｍ~k+1とから、ベクトルＢもしくはベクトルＣＰ-1、の少なくとも一部の成分に対して、前記既知乱数に由来する成分を消去したデータを求めるための手段と、
前記既知乱数に由来する成分を除去したデータから、誤り訂正によりメッセージｍを復号するための手段とを備えていることを特徴とする。
【０００９】
好ましくは、前記暗号通信装置は、符号化行列
Ｋ＝ ｜ＧA,ＧB｜
｜ Ｒ ｜
に由来する変換を公開鍵とする。
ここにＧA,ＧBは符号化行列で、ＧAで符号化した符号とＧBで符号化した符号とは相互変換が自在である。Ｒは少なくとも１行の乱数ベクトルである。
【００１０】
用語法
この明細書において、ベクトルは行列を含むものとし、例えば２行ｎ列の行列はｎ成分のベクトルを上下に２つに重ねたベクトルと見なす。
特許請求の範囲等での記号は、実施例との対比を容易にするためだけのもので、特許請求の範囲を限定する意味を持たず、例えばベクトルＣＰ-1との記号は、暗号文Ｃを変換Ｐ-1で処理したものを意味するのではなく、このベクトルを実施例でベクトルＣＰ-1と呼んでいることを意味する。またサブベクトルＣＰ-1Ｌ,ＣＰ-1ＲはＣＰ-1Ｌが左側の成分,ＣＰ-1Ｒが右側の成分であることを意味せず、単に２つのサブベクトルの名前がＣＰ-1ＬとＣＰ-1Ｒであることを意味する。
実施例を除き、また文脈上不自然な場合を除き、あるデータとそれから簡単に求めることができるデータとは同一視する。
また復号装置に関する記載は、復号プログラムや暗号通信装置にもそのまま当てはまるものとする。
【発明の効果】
【００１１】
この発明では、符号化行列に乱数を例えば１行追加できるので安全性が高い。即ち一般に、符号化行列の自由度に比べて、乱数の自由度が高いので、安全性が向上する。
【００１２】
ここでノイズの少なくとも一部をメッセージとすると、情報化率を高めることができる。この発明での情報化率は、例えば１００％近くまで、あるいは情報化率をより小さくした場合でも７／８程度まで高めることができる。
【００１３】
この発明での基本的な着眼点は、
Ｋ＝ ｜ＧA,ＧB｜
｜ Ｒ ｜
に由来する公開鍵を用いる点にある。ＧA,ＧBは類似もしくは同一の符号化行列で、類似の符号化を２回行い、暗号文長を２倍に引き伸ばす。そして暗号文の左半部と右半部などの排他加算を行うと、メッセージｍをＧAで処理した部分とＧBで処理した部分とが打ち消し合い、メッセージを乱数Ｒで処理したベクトルに暗号化側で付加したノイズが重なったものが残る。
【００１４】
このデータが例えばｎ個の成分(排他加算によりデータ長を、例えば２ｎからｎに圧縮済み)からなるものとし、ノイズの成分の個数を暗号文の長さよりも短くして、データ中の特定の個所に、ノイズが現れないようにする。その個所のデータは、メッセージの内で例えばＧA,ＧBで処理されていない部分と、乱数データとで定まり、乱数データは受信側（復号側）に既知なので、前記の部分を決定できる。このデータが求まると、乱数データが既知なので、その影響を除くことができる。最も簡単には、乱数成分の影響を除いて、
McElieceと同様に復号すると良い。
【００１５】
乱数データの影響を除いた際に、ノイズ成分相互の排他加算の値を求めることができ、例えば暗号文の長さを例えば２ｎとして、ノイズから約ｎの情報量を得ることができる。そして残るノイズと本来のメッセージとを誤り訂正で求めると、例えば本来のメッセージ長をｎ／２として、例えば ｎ＋ｎ／２＋ｎ／４＝７ｎ／４ の情報量を復号できる。ここにｎはノイズの排他加算で求めた情報量、ｎ／２はメッセージに対応する情報量は、ｎ／４は誤り訂正でノイズとして求めた情報量である。後に示すように、この発明で求めることができる情報量は、この記法での２ｎが上限で、暗号文長に対する平文長の比はほぼ１（情報化率）を高くできる。
【発明を実施するための最良の形態】
【００１６】
以下に発明を実施するための最良の形態を示す。
【実施例】
【００１７】
暗号通信システム
図１〜図８に実施例を示す。図１に、暗号通信システムの例を示すと、２はインターネットで、セキュアでない通信路の例であり、４,６はエンティティで、パーソナルコンピュータや各種のサーバなどを用い、資源としてＣＰＵとＲＡＭ並びにＲＯＭ及び入出力を備え、インターネット２と通信するための通信部を備えているものとする。８は暗号化部、１０は復号部、１２は鍵記憶部である。鍵記憶部１２では、自己の公開鍵 Ｍ＝ＳＫＰ としてＭを記憶し、ノイズｅを非線形変換するための変換Ａを記憶する。ただしノイズが文字通りのノイズであり、情報ではない場合、非線形変換Ａは不要である。秘密鍵として、公開鍵Ｍに対する逆変換のＰ-1,Ｓ-1を記憶する。Ｐ,Ｓは例えば共に正則行列で、Ｐはここでは成分の転置を行う置換行列とし、その成分は０と１とに限られる。行列Ｋは、符号化行列Ｇを左右に繰り返し２回配置し、例えばその下部あるいはその上部などに、例えば１行あるいは２行以上の乱数ベクトルＲを配置したものである。秘密鍵として、行列Ｋを記憶し、特に乱数ベクトルＲと符号化行列Ｇの復号アルゴリズムを記憶する。ここでは符号化行列Ｇの生成行列をＧ(Ｘ)としてこれを記憶し、後述のファクタα並びに、公開鍵Ａに対する逆変換Ａ-1を記憶する。
【００１８】
エンティティ４,６は、相手方の公開鍵Ｍ,Ａを用いて、メッセージｍ、並びにノイズの形で用いるメッセージｅを暗号化し、暗号文Ｃは、 Ｃ＝ｍＭ(＋)ｅＡ で与えられる。(＋)は排他加算を示す記号である。復号部１０では、Ｐの逆変換Ｐ-1とＳの逆変換Ｓ-1、及びＡの逆変換Ａ-1並びに行列Ｋに関する知識、特に乱数ベクトルＲやＧの生成多項式Ｇ(Ｘ),αなどを用いて復号を行う。
【００１９】
暗号通信プログラム
図２に、暗号通信プログラム２０を示すと、このプログラムはエンティティ４,６が記憶し、暗号化部８や復号部１０並びに鍵記憶部１２を生成するために用いられる。２２は鍵記憶命令で、自己の公開鍵と秘密鍵の値、並びにこれらの鍵を記憶するための命令とから成る。暗号化命令２４は、暗号化部８でメッセージｍとノイズｅを暗号文Ｃに変換するための命令である。復号命令２６は受信した暗号文を復号部１０で復号するための命令である。暗号化命令２４の内容は、以下の暗号化の説明から明らかになり、復号命令２６の内容も、復号に関する説明から明らかになる。
【００２０】
記号
図３に、実施例での記号の意味などを示す。なお各データは、拡大体Ｆ2Ｐのデータであるものとし、メッセージｍは例えばｋ＋１次元のベクトルで与えられ、ノイズｅは純粋なノイズであることもあれば、長さが２ｎよりも短いメッセージであることもある。実施例ではノイズｅをそのまま使うことによる暗号強度の低下を防止するため、ｅを非線形変換Ａで処理してｅＡとして用いる。Ｃは暗号文で、例えば長さ２ｎのベクトルであり、メッセージｍを暗号化した部分をＣ１,ノイズｅを暗号化した部分をＣ２とすると、これらの排他加算により暗号文Ｃが与えられる。
【００２１】
Ｋは実施例での中心となる行列で、交代式符号やゴッパ符号などの代数符号の、符号化行列Ｇを左右に２回重ね、例えばその下部に乱数ベクトルＲを１行分あるいは複数行分追加したものである。符号化行列Ｇがｎ×ｋ次の行列とすると(ｎ＞ｋ)、行列Ｋは例えばｋ＋１行で２ｎ列の行列となる。前記の置換行列Ｐの逆変換Ｐ-1で暗号文Ｃを処理するところから復号が開始される。ＣＰ-1の例えば左半分と右半分とを排他加算すると、ｎ次元のベクトルが得られる。このベクトルをＢと呼ぶ。行列ＫでＧを左右に２回繰り返して用いているため、ベクトルＢではｍＳＧに由来する成分が消去されている。即ちベクトルＢの成分は、メッセージｍ中のｋ＋１番目の最後の成分ｍ~k+1と、乱数ベクトル、並びにｅに由来する成分で構成されている。
【００２２】
行列Ｋが２ｎ列の行列であるのに対して、ノイズｅの長さは、２ｎよりも短い長さ、例えば ２ｎ−(ｎ／４＋２) 以下の長さとするので、ＣＰ-1にはノイズの寄与が既知の成分を設けることができる。例えばＣＰ-1のｊ番目の成分とｊ＋ｎ番目の成分で、ノイズに由来する部分の値を０とすることができる。ｊの値は復号化部で既知なので、Ｂのｊ番目の成分はｍ~k+1(Ｒｊ(＋)Ｒｊ＋ｎ)で定まり、ｍ~k+1を求めることができる。そしてｍ~k+1が判明すると、ＣＰ-1やＢからＲに由来する成分を除去できる。 Ｃ２＝ｅＡ として、Ｃ２Ｐ-1を４分割し、(ＸＬ,ＹＬ,ＹＲ,ＸＲ)とする。ここでＸＬ〜ＸＲは、例えば各々長さがｎ／２のベクトルとなる。Ｃ２Ｐ-1を直接求めることは困難であるが、Ｂから乱数ベクトルＲに由来する成分を消去すると、ＸＬ＋ＹＲ及びＹＬ＋ＸＲを求めることができる。言い換えるとＣ２の持つ情報量の約半分を求めることができる。また ＹＲ＝αＹＬ とする。ここにαはＦ２Ｐの元である。
【００２３】
暗号化
図４,図５に暗号化のプロセスを示す。暗号化しようとするエンティティは公開鍵Ｍ,Ａを取得し、メッセージｍに対して公開鍵Ｍを用いて暗号文Ｃ１を作成する。なおメッセージの長さはｋ＋１次元で、このうち元ｍ１〜ｍｋは符号化行列Ｇの作用を受け、元ｍk+1は乱数ベクトルＲの作用を受ける。行列Ｋの長さを２ｎ次元として、これよりも少なくとも２次元短いベクトルｅを用意し、ベクトルｅはノイズであっても、メッセージであっても良い。ベクトルｅがメッセージである場合は、アフィン変換や８Ｃ４符号などの非線形符号を用いた変換Ａにより、ベクトルｅを暗号文Ｃ２に変換する。この結果、暗号文Ｃ２には、簡単な規則性が見出しにくくなる。そして暗号文Ｃ１と暗号文Ｃ２との排他加算を暗号文Ｃとする。暗号文Ｃは２ｎ次元のベクトルで、各元はＦＰｑ（例えばＰ＝２，ｑは素数や８などであるが、１でも良い）の元である。得られた暗号文を、インターネットなどを介して復号側のエンティティへと送信する。
【００２４】
メッセージｍやメッセージなどのベクトルｅから、暗号文Ｃへの変換過程を図５に示すと、ｋ＋１次元のメッセージｍは、(ｋ＋１)×(ｋ＋１)の正則行列Ｓにより変換され、ｍ~へと変化する。これを符号化行列Ｋで処理することにより、２ｎ次元のメッセージｍ~ｋへと変化する。行列Ｋの構造から明らかなように、ｍ~ｋには符号化行列Ｇに由来する部分と、乱数ベクトルＲに由来する部分があり、符号化行列Ｇの作用を受けるものは、ベクトルｍ~の１番目からｋ番目までの元で、乱数ベクトルＲの作用を受けるのは、ｍ~k+1である。
【００２５】
メッセージｅは、非線形変換Ａを受けることによりＣ２に変換される。この時ベクトルの長さは２ｎ次元へと伸張される。暗号文Ｃ２にはＣ２Ｐ-1において、既知の番号ｊに対し、(Ｃ２Ｐ-1)ｊ,(Ｃ２Ｐ-1)ｊ＋ｎが共に既知であるとの条件がある。この性質は後にｍ~k+1の復号に用いられる。またＣ２Ｐ-1を長さがそれぞれｎ／２のサブベクトルＸＬ,ＹＬ,ＹＲ,ＸＲに分割すると、 ＹＲ＝αＹＬ との関係があるようにする。なおＹＲとＹＬとを関係づけることに代えて、例えばＸＬとＹＬとの間に同様の関係を与えたり、ＹＲとＸＲとの間に同様の関係を与えてもよい。これらのためベクトルｅの次元は、例えば３ｎ／２程度、あるいは２ｎ−ｋ程度が上限となる。そして暗号文Ｃ１と暗号文Ｃ２の排他加算が暗号文Ｃとなる。
【００２６】
復号
図６〜図８に、復号アルゴリズムとその過程での処理を示す。復号するエンティティは暗号文Ｃを受信すると、転置行列Ｐの逆行列Ｐ-1を作用させ、 ＣＰ-1＝ｍ~ｋ＋Ｃ２Ｐ-1 を得る。ＣＰ-1の左半分と右半分とを排他加算したものをベクトルＢとすると、その次元はｎ次元である。ベクトルＢにおいて、符号化行列Ｇに由来する部分は排他加算で消去され、ｍ~k+1と乱数ベクトルＲに由来する部分、並びにＣ２Ｐ-1の左半分(Ｃ２Ｐ-1)Ｌと右半分(Ｃ２Ｐ-1)Ｒとの排他加算が残る。ここで１〜ｎの特定の値ｊに対して、(Ｃ２Ｐ-1)Ｌｊと
(Ｃ２Ｐ-1)Ｒｊの排他加算の値は既知なので、ｍ~k+1を決定できる。さらに乱数ベクトルＲは既知なので、これを用いてベクトルＢから(Ｃ２Ｐ-1)Ｌｊと(Ｃ２Ｐ-1)Ｒｊの排他加算値を決定できる。ここに ｊ＝１〜ｎ である。
【００２７】
前記のようにＣ２Ｐ-1を４つの等長のサブベクトルに分割し、ＸＬ,ＹＬ,ＹＲ,ＸＲを各サブベクトルとすると、(Ｃ２Ｐ-1)ｊと(Ｃ２Ｐ-1)ｊ＋ｎの排他加算値が ｊ＝１〜ｎ に付いて既知なことから、ＸＬとＹＲの排他加算値やＹＬとＸＲの排他加算値は既知となる。そこで
Ｃ２Ｐ-1の例えば左半分にＸＬとＹＲの排他加算値を排他加算すると、ｍ~Ｇ＋(ＹＲ,ＹＬ)が得られる。
【００２８】
ここでＹＲとＹＬには特別な関係があり、一方が定まれば他方が定まる関係にある。特に ＹＲ＝αＹＬ としておくと、符号化行列Ｇに由来する誤り訂正能力を用いて、ＹＲ及び ＹＬを決定できる。例えばＹＲの０でない元の数を、符号化行列Ｇの誤り訂正能力の範囲にすると、ＹＲ,ＹＬを決定できる。
【００２９】
ＹＲ,ＹＬを決定できると、同時にｍ~が決定でき、 ｍ＝ｍ~Ｓ-1 なので、ｍを復号できる。ＹＲとＹＬが分かると、ＸＬとＹＲとの排他加算値が既知なので、ＸＬが決定できる。同様にＹＬとＸＲの排他加算値も既知なので、ＸＲも決定できる。これらによって、ＸＬ,ＹＬ,ＹＲ,ＸＲが求まり、ｅを復号できる。そしてメッセージｍとベクトルｅを復号できると、復号が終了する。
【００３０】
図８に、復号過程でのデータの変化を示し、特にＹＲとＹＬとの関係を用いて、これらを決定する点を示す。符号化行列Ｇに対応する生成多項式をＧ(Ｘ)とし、
Ｇ(Ｘ)＝Πｉ＝１〜ｇ(Ｘ−αｉ) とすると、ＹＬ(Ｘ)及びＹＲ(Ｘ)を図８のように表すことができる。そこでＹＬ(Ｘ)とＹＲ(Ｘ)を加算したものは、 ＹＬ(Ｘ)(１＋αＸｎ／２) に等しく、ここで因数(１＋αＸｎ／２)と生成多項式Ｇ(Ｘ)が互いに素ならば、ＹＬ(Ｘ)が判明する。
【００３１】
図８の過程で、暗号文Ｃに含まれる２ｎの情報量の内、Ｃ２Ｐ-1の左半分とＣ２Ｐ-1の右半分の排他加算値を決定した時点で、ほぼｎに相当する情報量を得ることができる。次にＹＬ,ＹＲを決定する時点で、ｎ／２〜ｎ／４程度の情報量を求めることができ、復号した情報量の合計は３ｎ／２〜５ｎ／４となる。またｍ~の復号により、行列Ｋの行数程度、ここでは ｎ／２＝ｋ 程度の情報量が求まり、合計約２ｎの情報量を復元できる。
【００３２】
暗号システムの強度
暗号システムの強度は主として行列Ｋの曖昧さ、即ち行列Ｋの全体から成る集合の濃度で定まる。そこでこの濃度の対数により暗号の強度を評価できる。例えば体がＦ２８であるものとし、符号化行列Ｇが１２８×２５６の行列で、乱数ベクトルＲが１行のベクトルであるとすると、行列Ｋのサイズは１０３２行×４０９６列となる。この結果、公開鍵Ｍのサイズは約４Ｍビットとなる。符号化行列Ｇは任意の値をとることができるわけではないので、その濃度の対数は約１０００バイト程度と評価できる。これに対して乱数ベクトルＲ全体の集合の濃度の対数は、少なくとも４０００バイトで、乱数ベクトルの付加により暗号強度が飛躍的に増していることが分かる。
【００３３】
情報化率
行列Ｇのサイズがｋ×ｎで、ｋは約ｎ／２と仮定する。すると長さ２ｎの暗号文に対し、メッセージ長はｎ／２、ベクトルｅが持つことができる情報量はｎ＋ｎ/４〜ｎ＋ｎ/２である。従って情報化率の上限は約１もしくは０.８７５の程度となる。このように高い情報化率が求められる。
【００３４】
変形例
乱数ベクトルＲは１行のベクトルである必要はなく、２行以上のベクトルでも良い。例えば乱数ベクトルが３行から成るものとし、これに対応して復号可能な元がｍ~k+1,ｍ~k+2,ｍ~k+3とする。これらの値を決定するには、ノイズに由来するデータの無い個所が３個所必要で、前記のｊの他に、ｊ’,ｊ”において、ノイズに由来するデータがなければよい。
【００３５】
行列Ｋでの符号化行列Ｇは、左右同じものを用いる必要はなく、例えばベクトルＣＰ-1の左半分と右半分の排他加算を行った際に、左側の行列ＧＬと右側の行列ＧＲとに由来する部分の排他加算値が既知となればよい。
ベクトルｅを単なるノイズとすれば、情報化率が低下する。例えば最も簡単には、ベクトルｅの中で、０でない元の数ｗ(ｅ)が行列Ｇの誤り訂正能力の範囲内であるようにする。すると、ｍ~k+1を決定した後に、行列Ｇによる符号訂正を用いて、ベクトルＣＰ-1の左半分もしくは右半分により、メッセージｍ~を直ちに復号できる。また情報化率を３／４程度にする場合、メッセージｅの長さを例えば５ｎ／４程度とし、うちｎ個の元を実際のメッセージとし、ｎ／４個の元をノイズとする。Ｃ２Ｐ-1では、ｎ個の元がメッセージに由来し、これらがＸＬとＸＲの部分に分布し、ｎ／４個の元がノイズに由来して、これらがＹＲとＹＬの部分に分布するようにすれば、行列Ｇの誤り訂正能力を用いて、ノイズに由来するｎ／４個の元を決定すると共に、メッセージｍ~を決定できる。そしてＸＬとＹＲの排他加算値や、ＹＬとＸＲの排他加算値が既知なので、ＹＬ,ＹＲの値から、ＸＬやＸＲに含まれるメッセージを復号できる。
【図面の簡単な説明】
【００３６】
【図１】実施例の暗号通信装置を用いたシステムのブロック図
【図２】実施例の暗号通信プログラムのブロック図
【図３】実施例で用いる記号の意味を示す図
【図４】実施例での暗号化手続を示すフローチャート
【図５】実施例での、暗号化過程でのデータの変化を示す図
【図６】実施例での復号手続の前半を示すフローチャート
【図７】実施例での復号手続の後半を示すフローチャート
【図８】実施例での、復号過程でのデータの変化を示す図
【符号の説明】
【００３７】
２ インターネット
４,６ エンティティ
８ 暗号化部
１０ 復号部
１２ 鍵記憶部
２０ 暗号通信プログラム
２２ 鍵記憶命令
２４ 暗号化命令
２６ 復号命令
【技術分野】
【０００１】
この発明は、公開鍵暗号に関し、特にその復号装置と復号プログラム、及び暗号通信装置に関する。
【背景技術】
【０００２】
非特許文献１でMcElieceは、ゴッパ符号などを用いた公開鍵暗号システムを提案している。このシステムでは、ｋ行ｎ列の符号化行列をＧ、ｋ×ｋの正則行列をＳ、ｎ×ｎの置換行列をＰとして、メッセージｍ、ノイズｅを用いて、 ｍＳＧＰ(＋)ｅ を暗号文とする。復号側ではＰ-1が既知なことから、 ｍＳＧ(＋)ｅＰ-1 を求め、Ｐが置換行列で、ｅとｅＰ-1とで０でない成分の数が増さないことから、ｍＳＧ(＋)ｅＰ-1がｍＳへ誤り訂正可能な範囲で有れば、ｍＳを介してｍへ復号できる。
非特許文献２のNiderreiterのシステムでは、ｎ×(ｎ−ｋ)の検査行列Ｈと、(ｎ−ｋ)×(ｎ−ｋ)の正則行列Ｓと、ｎ×ｎの置換行列Ｐを用い、ＰＨＳを公開鍵とする。メッセージｍに対してｍＰＨＳを暗号文とする。復号側では、ｍＰＨＳをｍＰＨへ変換し、検査行列Ｈに対する誤り訂正でｍＰを求めて、メッセージｍを復号する。
【非特許文献１】R.J.McEliece: "A public-key cryptosystem based on algebraic coding theory", Deep Space Network Progress Report 42-44,pp114-116, Jet Propulsion Lab., Pasadena,CA (1978)
【非特許文献２】H.Niderreiter: "Error-correcting codes and cryptography" in "Public-Key Cryptography and Computational Number Theory" edited by K.Alster, J.Urbanowicz and H.C.Williams, Walter de Gruyter,(2001)
【０００３】
これらのシステムでの暗号強度は、符号化行列Ｇや検査行列Ｈの多様さ、言い換えるとこれらの曖昧さに依存し、行列Ｇ,Ｈが推定可能であれば安全ではない。そこで行列Ｇ,Ｈの推定困難性のみに根拠を置く暗号は、必ずしも安全とは言えない。McElieceのシステムでは乱数を加えて強度を高めているが、乱数は誤り訂正可能な範囲に限られ、例えばｎ次元のベクトルに対してｎ個の乱数成分を付加することはできない。また平文長と暗号文長との比を情報化率と呼ぶと、誤り訂正のために、これらのシステムでは情報化率を高くできない。
【発明の開示】
【発明が解決しようとする課題】
【０００４】
この発明の基本的課題は、誤り訂正を用いたより安全な暗号システムのための復号装置と復号プログラム、及び暗号通信装置を提供することにある。
この発明での副次的課題は、暗号に用いるノイズの少なくとも一部をメッセージとして、情報化率を高めることにある。
【課題を解決するための手段】
【０００５】
この発明は、メッセージｍを誤り訂正可能な符号に符号化したものにノイズｅを混合した暗号文を、前記符号の誤り訂正能力を用いて平文へ復号する復号装置において、
受信した暗号文Ｃに由来するベクトルＣＰ-1から、例えばベクトルＣＰ-1を左右に分割して、少なくとも２つのサブベクトルＣＰ-1Ｒ,ＣＰ-1Ｌを生成するための手段と、
前記少なくとも２つのサブベクトルＣＰ-1Ｌ,ＣＰ-1Ｒを組み合わせてベクトルＢを求めるための手段と、
ベクトルＢの特定の成分から、少なくともデータｍ~k+1を求めるための手段と、
既知の乱数とデータｍ~k+1とから、ベクトルＢもしくはベクトルＣＰ-1の、少なくとも一部の成分に対して、前記既知乱数に由来する成分を消去したデータを求めるための手段と、
前記既知乱数に由来する成分を除去したデータから、誤り訂正によりメッセージｍを復号するための手段とを設けたことを特徴とする。
なおデータｍ~k+1をメッセージへと復号しても良く、あるいはそのまま中間変数として捨てても良い。
【０００６】
好ましくは、既知乱数に由来する成分を除去したデータから、例えばメッセージｍの復号の誤り訂正により、ノイズをメッセージとして復号するための手段を設ける。
特に好ましくは、メッセージｍを復号する際の誤り訂正によりノイズの一部を復号すると共に、ベクトルＢから既知乱数に由来する成分を除去したデータと組み合わせて、ノイズの他の部分を復号する手段を設ける。
【０００７】
この発明は、メッセージｍを誤り訂正可能な符号に符号化したものにノイズｅを混合した暗号文を、前記符号の誤り訂正能力を用いて平文へ復号するための復号プログラムにおいて、
受信した暗号文Ｃに由来するベクトルＣＰ-1から、少なくとも２つのサブベクトル
ＣＰ-1Ｒ,ＣＰ-1Ｌを生成するための命令と、
前記少なくとも２つのサブベクトルＣＰ-1Ｌ,ＣＰ-1Ｒを組み合わせてベクトルＢを求めるための命令と、
ベクトルＢの特定の成分から、少なくともデータｍ~k+1を求めるための手段と、
既知の乱数とデータｍ~k+1とから、ベクトルＢもしくはベクトルＣＰ-1の、少なくとも一部の成分に対して、前記既知乱数に由来する成分を消去したデータを求めるための命令と、
前記既知乱数に由来する成分を除去したデータから、誤り訂正によりメッセージｍを復号するための命令とを設けたことを特徴とする。
【０００８】
この発明は、通信手段と、メッセージｍを誤り訂正可能な符号に符号化したものにノイズｅを混合して暗号化するための暗号化手段と、受信した暗号文を前記符号の誤り訂正能力を用いて平文へ復号するための復号手段とを備えた暗号通信装置において、
前記復号手段は、
受信した暗号文Ｃに由来するベクトルＣＰ-1から、少なくとも２つのサブベクトル
ＣＰ-1Ｒ,ＣＰ-1Ｌを生成するための手段と、
前記少なくとも２つのサブベクトルＣＰ-1Ｌ,ＣＰ-1Ｒを組み合わせてベクトルＢを求めるための手段と、
ベクトルＢの特定の成分から、少なくともデータｍ~k+1を求めるための手段と、
既知の乱数とデータｍ~k+1とから、ベクトルＢもしくはベクトルＣＰ-1、の少なくとも一部の成分に対して、前記既知乱数に由来する成分を消去したデータを求めるための手段と、
前記既知乱数に由来する成分を除去したデータから、誤り訂正によりメッセージｍを復号するための手段とを備えていることを特徴とする。
【０００９】
好ましくは、前記暗号通信装置は、符号化行列
Ｋ＝ ｜ＧA,ＧB｜
｜ Ｒ ｜
に由来する変換を公開鍵とする。
ここにＧA,ＧBは符号化行列で、ＧAで符号化した符号とＧBで符号化した符号とは相互変換が自在である。Ｒは少なくとも１行の乱数ベクトルである。
【００１０】
用語法
この明細書において、ベクトルは行列を含むものとし、例えば２行ｎ列の行列はｎ成分のベクトルを上下に２つに重ねたベクトルと見なす。
特許請求の範囲等での記号は、実施例との対比を容易にするためだけのもので、特許請求の範囲を限定する意味を持たず、例えばベクトルＣＰ-1との記号は、暗号文Ｃを変換Ｐ-1で処理したものを意味するのではなく、このベクトルを実施例でベクトルＣＰ-1と呼んでいることを意味する。またサブベクトルＣＰ-1Ｌ,ＣＰ-1ＲはＣＰ-1Ｌが左側の成分,ＣＰ-1Ｒが右側の成分であることを意味せず、単に２つのサブベクトルの名前がＣＰ-1ＬとＣＰ-1Ｒであることを意味する。
実施例を除き、また文脈上不自然な場合を除き、あるデータとそれから簡単に求めることができるデータとは同一視する。
また復号装置に関する記載は、復号プログラムや暗号通信装置にもそのまま当てはまるものとする。
【発明の効果】
【００１１】
この発明では、符号化行列に乱数を例えば１行追加できるので安全性が高い。即ち一般に、符号化行列の自由度に比べて、乱数の自由度が高いので、安全性が向上する。
【００１２】
ここでノイズの少なくとも一部をメッセージとすると、情報化率を高めることができる。この発明での情報化率は、例えば１００％近くまで、あるいは情報化率をより小さくした場合でも７／８程度まで高めることができる。
【００１３】
この発明での基本的な着眼点は、
Ｋ＝ ｜ＧA,ＧB｜
｜ Ｒ ｜
に由来する公開鍵を用いる点にある。ＧA,ＧBは類似もしくは同一の符号化行列で、類似の符号化を２回行い、暗号文長を２倍に引き伸ばす。そして暗号文の左半部と右半部などの排他加算を行うと、メッセージｍをＧAで処理した部分とＧBで処理した部分とが打ち消し合い、メッセージを乱数Ｒで処理したベクトルに暗号化側で付加したノイズが重なったものが残る。
【００１４】
このデータが例えばｎ個の成分(排他加算によりデータ長を、例えば２ｎからｎに圧縮済み)からなるものとし、ノイズの成分の個数を暗号文の長さよりも短くして、データ中の特定の個所に、ノイズが現れないようにする。その個所のデータは、メッセージの内で例えばＧA,ＧBで処理されていない部分と、乱数データとで定まり、乱数データは受信側（復号側）に既知なので、前記の部分を決定できる。このデータが求まると、乱数データが既知なので、その影響を除くことができる。最も簡単には、乱数成分の影響を除いて、
McElieceと同様に復号すると良い。
【００１５】
乱数データの影響を除いた際に、ノイズ成分相互の排他加算の値を求めることができ、例えば暗号文の長さを例えば２ｎとして、ノイズから約ｎの情報量を得ることができる。そして残るノイズと本来のメッセージとを誤り訂正で求めると、例えば本来のメッセージ長をｎ／２として、例えば ｎ＋ｎ／２＋ｎ／４＝７ｎ／４ の情報量を復号できる。ここにｎはノイズの排他加算で求めた情報量、ｎ／２はメッセージに対応する情報量は、ｎ／４は誤り訂正でノイズとして求めた情報量である。後に示すように、この発明で求めることができる情報量は、この記法での２ｎが上限で、暗号文長に対する平文長の比はほぼ１（情報化率）を高くできる。
【発明を実施するための最良の形態】
【００１６】
以下に発明を実施するための最良の形態を示す。
【実施例】
【００１７】
暗号通信システム
図１〜図８に実施例を示す。図１に、暗号通信システムの例を示すと、２はインターネットで、セキュアでない通信路の例であり、４,６はエンティティで、パーソナルコンピュータや各種のサーバなどを用い、資源としてＣＰＵとＲＡＭ並びにＲＯＭ及び入出力を備え、インターネット２と通信するための通信部を備えているものとする。８は暗号化部、１０は復号部、１２は鍵記憶部である。鍵記憶部１２では、自己の公開鍵 Ｍ＝ＳＫＰ としてＭを記憶し、ノイズｅを非線形変換するための変換Ａを記憶する。ただしノイズが文字通りのノイズであり、情報ではない場合、非線形変換Ａは不要である。秘密鍵として、公開鍵Ｍに対する逆変換のＰ-1,Ｓ-1を記憶する。Ｐ,Ｓは例えば共に正則行列で、Ｐはここでは成分の転置を行う置換行列とし、その成分は０と１とに限られる。行列Ｋは、符号化行列Ｇを左右に繰り返し２回配置し、例えばその下部あるいはその上部などに、例えば１行あるいは２行以上の乱数ベクトルＲを配置したものである。秘密鍵として、行列Ｋを記憶し、特に乱数ベクトルＲと符号化行列Ｇの復号アルゴリズムを記憶する。ここでは符号化行列Ｇの生成行列をＧ(Ｘ)としてこれを記憶し、後述のファクタα並びに、公開鍵Ａに対する逆変換Ａ-1を記憶する。
【００１８】
エンティティ４,６は、相手方の公開鍵Ｍ,Ａを用いて、メッセージｍ、並びにノイズの形で用いるメッセージｅを暗号化し、暗号文Ｃは、 Ｃ＝ｍＭ(＋)ｅＡ で与えられる。(＋)は排他加算を示す記号である。復号部１０では、Ｐの逆変換Ｐ-1とＳの逆変換Ｓ-1、及びＡの逆変換Ａ-1並びに行列Ｋに関する知識、特に乱数ベクトルＲやＧの生成多項式Ｇ(Ｘ),αなどを用いて復号を行う。
【００１９】
暗号通信プログラム
図２に、暗号通信プログラム２０を示すと、このプログラムはエンティティ４,６が記憶し、暗号化部８や復号部１０並びに鍵記憶部１２を生成するために用いられる。２２は鍵記憶命令で、自己の公開鍵と秘密鍵の値、並びにこれらの鍵を記憶するための命令とから成る。暗号化命令２４は、暗号化部８でメッセージｍとノイズｅを暗号文Ｃに変換するための命令である。復号命令２６は受信した暗号文を復号部１０で復号するための命令である。暗号化命令２４の内容は、以下の暗号化の説明から明らかになり、復号命令２６の内容も、復号に関する説明から明らかになる。
【００２０】
記号
図３に、実施例での記号の意味などを示す。なお各データは、拡大体Ｆ2Ｐのデータであるものとし、メッセージｍは例えばｋ＋１次元のベクトルで与えられ、ノイズｅは純粋なノイズであることもあれば、長さが２ｎよりも短いメッセージであることもある。実施例ではノイズｅをそのまま使うことによる暗号強度の低下を防止するため、ｅを非線形変換Ａで処理してｅＡとして用いる。Ｃは暗号文で、例えば長さ２ｎのベクトルであり、メッセージｍを暗号化した部分をＣ１,ノイズｅを暗号化した部分をＣ２とすると、これらの排他加算により暗号文Ｃが与えられる。
【００２１】
Ｋは実施例での中心となる行列で、交代式符号やゴッパ符号などの代数符号の、符号化行列Ｇを左右に２回重ね、例えばその下部に乱数ベクトルＲを１行分あるいは複数行分追加したものである。符号化行列Ｇがｎ×ｋ次の行列とすると(ｎ＞ｋ)、行列Ｋは例えばｋ＋１行で２ｎ列の行列となる。前記の置換行列Ｐの逆変換Ｐ-1で暗号文Ｃを処理するところから復号が開始される。ＣＰ-1の例えば左半分と右半分とを排他加算すると、ｎ次元のベクトルが得られる。このベクトルをＢと呼ぶ。行列ＫでＧを左右に２回繰り返して用いているため、ベクトルＢではｍＳＧに由来する成分が消去されている。即ちベクトルＢの成分は、メッセージｍ中のｋ＋１番目の最後の成分ｍ~k+1と、乱数ベクトル、並びにｅに由来する成分で構成されている。
【００２２】
行列Ｋが２ｎ列の行列であるのに対して、ノイズｅの長さは、２ｎよりも短い長さ、例えば ２ｎ−(ｎ／４＋２) 以下の長さとするので、ＣＰ-1にはノイズの寄与が既知の成分を設けることができる。例えばＣＰ-1のｊ番目の成分とｊ＋ｎ番目の成分で、ノイズに由来する部分の値を０とすることができる。ｊの値は復号化部で既知なので、Ｂのｊ番目の成分はｍ~k+1(Ｒｊ(＋)Ｒｊ＋ｎ)で定まり、ｍ~k+1を求めることができる。そしてｍ~k+1が判明すると、ＣＰ-1やＢからＲに由来する成分を除去できる。 Ｃ２＝ｅＡ として、Ｃ２Ｐ-1を４分割し、(ＸＬ,ＹＬ,ＹＲ,ＸＲ)とする。ここでＸＬ〜ＸＲは、例えば各々長さがｎ／２のベクトルとなる。Ｃ２Ｐ-1を直接求めることは困難であるが、Ｂから乱数ベクトルＲに由来する成分を消去すると、ＸＬ＋ＹＲ及びＹＬ＋ＸＲを求めることができる。言い換えるとＣ２の持つ情報量の約半分を求めることができる。また ＹＲ＝αＹＬ とする。ここにαはＦ２Ｐの元である。
【００２３】
暗号化
図４,図５に暗号化のプロセスを示す。暗号化しようとするエンティティは公開鍵Ｍ,Ａを取得し、メッセージｍに対して公開鍵Ｍを用いて暗号文Ｃ１を作成する。なおメッセージの長さはｋ＋１次元で、このうち元ｍ１〜ｍｋは符号化行列Ｇの作用を受け、元ｍk+1は乱数ベクトルＲの作用を受ける。行列Ｋの長さを２ｎ次元として、これよりも少なくとも２次元短いベクトルｅを用意し、ベクトルｅはノイズであっても、メッセージであっても良い。ベクトルｅがメッセージである場合は、アフィン変換や８Ｃ４符号などの非線形符号を用いた変換Ａにより、ベクトルｅを暗号文Ｃ２に変換する。この結果、暗号文Ｃ２には、簡単な規則性が見出しにくくなる。そして暗号文Ｃ１と暗号文Ｃ２との排他加算を暗号文Ｃとする。暗号文Ｃは２ｎ次元のベクトルで、各元はＦＰｑ（例えばＰ＝２，ｑは素数や８などであるが、１でも良い）の元である。得られた暗号文を、インターネットなどを介して復号側のエンティティへと送信する。
【００２４】
メッセージｍやメッセージなどのベクトルｅから、暗号文Ｃへの変換過程を図５に示すと、ｋ＋１次元のメッセージｍは、(ｋ＋１)×(ｋ＋１)の正則行列Ｓにより変換され、ｍ~へと変化する。これを符号化行列Ｋで処理することにより、２ｎ次元のメッセージｍ~ｋへと変化する。行列Ｋの構造から明らかなように、ｍ~ｋには符号化行列Ｇに由来する部分と、乱数ベクトルＲに由来する部分があり、符号化行列Ｇの作用を受けるものは、ベクトルｍ~の１番目からｋ番目までの元で、乱数ベクトルＲの作用を受けるのは、ｍ~k+1である。
【００２５】
メッセージｅは、非線形変換Ａを受けることによりＣ２に変換される。この時ベクトルの長さは２ｎ次元へと伸張される。暗号文Ｃ２にはＣ２Ｐ-1において、既知の番号ｊに対し、(Ｃ２Ｐ-1)ｊ,(Ｃ２Ｐ-1)ｊ＋ｎが共に既知であるとの条件がある。この性質は後にｍ~k+1の復号に用いられる。またＣ２Ｐ-1を長さがそれぞれｎ／２のサブベクトルＸＬ,ＹＬ,ＹＲ,ＸＲに分割すると、 ＹＲ＝αＹＬ との関係があるようにする。なおＹＲとＹＬとを関係づけることに代えて、例えばＸＬとＹＬとの間に同様の関係を与えたり、ＹＲとＸＲとの間に同様の関係を与えてもよい。これらのためベクトルｅの次元は、例えば３ｎ／２程度、あるいは２ｎ−ｋ程度が上限となる。そして暗号文Ｃ１と暗号文Ｃ２の排他加算が暗号文Ｃとなる。
【００２６】
復号
図６〜図８に、復号アルゴリズムとその過程での処理を示す。復号するエンティティは暗号文Ｃを受信すると、転置行列Ｐの逆行列Ｐ-1を作用させ、 ＣＰ-1＝ｍ~ｋ＋Ｃ２Ｐ-1 を得る。ＣＰ-1の左半分と右半分とを排他加算したものをベクトルＢとすると、その次元はｎ次元である。ベクトルＢにおいて、符号化行列Ｇに由来する部分は排他加算で消去され、ｍ~k+1と乱数ベクトルＲに由来する部分、並びにＣ２Ｐ-1の左半分(Ｃ２Ｐ-1)Ｌと右半分(Ｃ２Ｐ-1)Ｒとの排他加算が残る。ここで１〜ｎの特定の値ｊに対して、(Ｃ２Ｐ-1)Ｌｊと
(Ｃ２Ｐ-1)Ｒｊの排他加算の値は既知なので、ｍ~k+1を決定できる。さらに乱数ベクトルＲは既知なので、これを用いてベクトルＢから(Ｃ２Ｐ-1)Ｌｊと(Ｃ２Ｐ-1)Ｒｊの排他加算値を決定できる。ここに ｊ＝１〜ｎ である。
【００２７】
前記のようにＣ２Ｐ-1を４つの等長のサブベクトルに分割し、ＸＬ,ＹＬ,ＹＲ,ＸＲを各サブベクトルとすると、(Ｃ２Ｐ-1)ｊと(Ｃ２Ｐ-1)ｊ＋ｎの排他加算値が ｊ＝１〜ｎ に付いて既知なことから、ＸＬとＹＲの排他加算値やＹＬとＸＲの排他加算値は既知となる。そこで
Ｃ２Ｐ-1の例えば左半分にＸＬとＹＲの排他加算値を排他加算すると、ｍ~Ｇ＋(ＹＲ,ＹＬ)が得られる。
【００２８】
ここでＹＲとＹＬには特別な関係があり、一方が定まれば他方が定まる関係にある。特に ＹＲ＝αＹＬ としておくと、符号化行列Ｇに由来する誤り訂正能力を用いて、ＹＲ及び ＹＬを決定できる。例えばＹＲの０でない元の数を、符号化行列Ｇの誤り訂正能力の範囲にすると、ＹＲ,ＹＬを決定できる。
【００２９】
ＹＲ,ＹＬを決定できると、同時にｍ~が決定でき、 ｍ＝ｍ~Ｓ-1 なので、ｍを復号できる。ＹＲとＹＬが分かると、ＸＬとＹＲとの排他加算値が既知なので、ＸＬが決定できる。同様にＹＬとＸＲの排他加算値も既知なので、ＸＲも決定できる。これらによって、ＸＬ,ＹＬ,ＹＲ,ＸＲが求まり、ｅを復号できる。そしてメッセージｍとベクトルｅを復号できると、復号が終了する。
【００３０】
図８に、復号過程でのデータの変化を示し、特にＹＲとＹＬとの関係を用いて、これらを決定する点を示す。符号化行列Ｇに対応する生成多項式をＧ(Ｘ)とし、
Ｇ(Ｘ)＝Πｉ＝１〜ｇ(Ｘ−αｉ) とすると、ＹＬ(Ｘ)及びＹＲ(Ｘ)を図８のように表すことができる。そこでＹＬ(Ｘ)とＹＲ(Ｘ)を加算したものは、 ＹＬ(Ｘ)(１＋αＸｎ／２) に等しく、ここで因数(１＋αＸｎ／２)と生成多項式Ｇ(Ｘ)が互いに素ならば、ＹＬ(Ｘ)が判明する。
【００３１】
図８の過程で、暗号文Ｃに含まれる２ｎの情報量の内、Ｃ２Ｐ-1の左半分とＣ２Ｐ-1の右半分の排他加算値を決定した時点で、ほぼｎに相当する情報量を得ることができる。次にＹＬ,ＹＲを決定する時点で、ｎ／２〜ｎ／４程度の情報量を求めることができ、復号した情報量の合計は３ｎ／２〜５ｎ／４となる。またｍ~の復号により、行列Ｋの行数程度、ここでは ｎ／２＝ｋ 程度の情報量が求まり、合計約２ｎの情報量を復元できる。
【００３２】
暗号システムの強度
暗号システムの強度は主として行列Ｋの曖昧さ、即ち行列Ｋの全体から成る集合の濃度で定まる。そこでこの濃度の対数により暗号の強度を評価できる。例えば体がＦ２８であるものとし、符号化行列Ｇが１２８×２５６の行列で、乱数ベクトルＲが１行のベクトルであるとすると、行列Ｋのサイズは１０３２行×４０９６列となる。この結果、公開鍵Ｍのサイズは約４Ｍビットとなる。符号化行列Ｇは任意の値をとることができるわけではないので、その濃度の対数は約１０００バイト程度と評価できる。これに対して乱数ベクトルＲ全体の集合の濃度の対数は、少なくとも４０００バイトで、乱数ベクトルの付加により暗号強度が飛躍的に増していることが分かる。
【００３３】
情報化率
行列Ｇのサイズがｋ×ｎで、ｋは約ｎ／２と仮定する。すると長さ２ｎの暗号文に対し、メッセージ長はｎ／２、ベクトルｅが持つことができる情報量はｎ＋ｎ/４〜ｎ＋ｎ/２である。従って情報化率の上限は約１もしくは０.８７５の程度となる。このように高い情報化率が求められる。
【００３４】
変形例
乱数ベクトルＲは１行のベクトルである必要はなく、２行以上のベクトルでも良い。例えば乱数ベクトルが３行から成るものとし、これに対応して復号可能な元がｍ~k+1,ｍ~k+2,ｍ~k+3とする。これらの値を決定するには、ノイズに由来するデータの無い個所が３個所必要で、前記のｊの他に、ｊ’,ｊ”において、ノイズに由来するデータがなければよい。
【００３５】
行列Ｋでの符号化行列Ｇは、左右同じものを用いる必要はなく、例えばベクトルＣＰ-1の左半分と右半分の排他加算を行った際に、左側の行列ＧＬと右側の行列ＧＲとに由来する部分の排他加算値が既知となればよい。
ベクトルｅを単なるノイズとすれば、情報化率が低下する。例えば最も簡単には、ベクトルｅの中で、０でない元の数ｗ(ｅ)が行列Ｇの誤り訂正能力の範囲内であるようにする。すると、ｍ~k+1を決定した後に、行列Ｇによる符号訂正を用いて、ベクトルＣＰ-1の左半分もしくは右半分により、メッセージｍ~を直ちに復号できる。また情報化率を３／４程度にする場合、メッセージｅの長さを例えば５ｎ／４程度とし、うちｎ個の元を実際のメッセージとし、ｎ／４個の元をノイズとする。Ｃ２Ｐ-1では、ｎ個の元がメッセージに由来し、これらがＸＬとＸＲの部分に分布し、ｎ／４個の元がノイズに由来して、これらがＹＲとＹＬの部分に分布するようにすれば、行列Ｇの誤り訂正能力を用いて、ノイズに由来するｎ／４個の元を決定すると共に、メッセージｍ~を決定できる。そしてＸＬとＹＲの排他加算値や、ＹＬとＸＲの排他加算値が既知なので、ＹＬ,ＹＲの値から、ＸＬやＸＲに含まれるメッセージを復号できる。
【図面の簡単な説明】
【００３６】
【図１】実施例の暗号通信装置を用いたシステムのブロック図
【図２】実施例の暗号通信プログラムのブロック図
【図３】実施例で用いる記号の意味を示す図
【図４】実施例での暗号化手続を示すフローチャート
【図５】実施例での、暗号化過程でのデータの変化を示す図
【図６】実施例での復号手続の前半を示すフローチャート
【図７】実施例での復号手続の後半を示すフローチャート
【図８】実施例での、復号過程でのデータの変化を示す図
【符号の説明】
【００３７】
２ インターネット
４,６ エンティティ
８ 暗号化部
１０ 復号部
１２ 鍵記憶部
２０ 暗号通信プログラム
２２ 鍵記憶命令
２４ 暗号化命令
２６ 復号命令
【特許請求の範囲】
【請求項１】
メッセージｍを誤り訂正可能な符号に符号化したものにノイズｅを混合した暗号文を、前記符号の誤り訂正能力を用いて平文へ復号する復号装置において、
受信した暗号文Ｃに由来するベクトルＣＰ-1から、少なくとも２つのサブベクトル
ＣＰ-1Ｒ,ＣＰ-1Ｌを生成するための手段と、
前記少なくとも２つのサブベクトルＣＰ-1Ｌ,ＣＰ-1Ｒを組み合わせてベクトルＢを求めるための手段と、
ベクトルＢの特定の成分から、少なくともデータｍ~k+1を求めるための手段と、
既知の乱数とデータｍ~k+1とから、ベクトルＢもしくはベクトルＣＰ-1の、少なくとも一部の成分に対して、前記既知乱数に由来する成分を消去したデータを求めるための手段と、
前記既知乱数に由来する成分を除去したデータから、誤り訂正によりメッセージｍを復号するための手段とを設けたことを特徴とする、復号装置。
【請求項２】
既知乱数に由来する成分を除去したデータから、ノイズをメッセージとして復号するための手段を設けたことを特徴とする、請求項１の復号装置。
【請求項３】
メッセージｍを復号する際の誤り訂正によりノイズの一部を復号すると共に、ベクトルＢから既知乱数に由来する成分を除去したデータと組み合わせて、ノイズの他の部分を復号する手段を設けたことを特徴とする、請求項２の復号装置。
【請求項４】
メッセージｍを誤り訂正可能な符号に符号化したものにノイズｅを混合した暗号文を、前記符号の誤り訂正能力を用いて平文へ復号するための復号プログラムにおいて、
受信した暗号文Ｃに由来するベクトルＣＰ-1から、少なくとも２つのサブベクトル
ＣＰ-1Ｒ,ＣＰ-1Ｌを生成するための命令と、
前記少なくとも２つのサブベクトルＣＰ-1Ｌ,ＣＰ-1Ｒを組み合わせてベクトルＢを求めるための命令と、
ベクトルＢの特定の成分から、少なくともデータｍ~k+1を求めるための手段と、
既知の乱数とデータｍ~k+1とから、ベクトルＢもしくはベクトルＣＰ-1の、少なくとも一部の成分に対して、前記既知乱数に由来する成分を消去したデータを求めるための命令と、
前記既知乱数に由来する成分を除去したデータから、誤り訂正によりメッセージｍを復号するための命令とを設けたことを特徴とする、復号プログラム。
【請求項５】
通信手段と、メッセージｍを誤り訂正可能な符号に符号化したものにノイズｅを混合して暗号化するための暗号化手段と、受信した暗号文を前記符号の誤り訂正能力を用いて平文へ復号するための復号手段とを備えた暗号通信装置において、
前記復号手段は、
受信した暗号文Ｃに由来するベクトルＣＰ-1から、少なくとも２つのサブベクトル
ＣＰ-1Ｒ,ＣＰ-1Ｌを生成するための手段と、
前記少なくとも２つのサブベクトルＣＰ-1Ｌ,ＣＰ-1Ｒを組み合わせてベクトルＢを求めるための手段と、
ベクトルＢの特定の成分から、少なくともデータｍ~k+1を求めるための手段と、
既知の乱数とデータｍ~k+1とから、ベクトルＢもしくはベクトルＣＰ-1、の少なくとも一部の成分に対して、前記既知乱数に由来する成分を消去したデータを求めるための手段と、
前記既知乱数に由来する成分を除去したデータから、誤り訂正によりメッセージｍを復号するための手段とを備えていることを特徴とする、暗号通信装置。
【請求項６】
前記暗号通信装置は、符号化行列
Ｋ＝ ｜ＧA,ＧB｜
｜ Ｒ ｜
に由来する変換を公開鍵とすることを特徴とする、請求項５の暗号通信装置。
ここにＧA,ＧBは符号化行列で、ＧAで符号化した符号とＧBで符号化した符号とは相互変換が自在である。Ｒは少なくとも１行の乱数ベクトルである。
【請求項１】
メッセージｍを誤り訂正可能な符号に符号化したものにノイズｅを混合した暗号文を、前記符号の誤り訂正能力を用いて平文へ復号する復号装置において、
受信した暗号文Ｃに由来するベクトルＣＰ-1から、少なくとも２つのサブベクトル
ＣＰ-1Ｒ,ＣＰ-1Ｌを生成するための手段と、
前記少なくとも２つのサブベクトルＣＰ-1Ｌ,ＣＰ-1Ｒを組み合わせてベクトルＢを求めるための手段と、
ベクトルＢの特定の成分から、少なくともデータｍ~k+1を求めるための手段と、
既知の乱数とデータｍ~k+1とから、ベクトルＢもしくはベクトルＣＰ-1の、少なくとも一部の成分に対して、前記既知乱数に由来する成分を消去したデータを求めるための手段と、
前記既知乱数に由来する成分を除去したデータから、誤り訂正によりメッセージｍを復号するための手段とを設けたことを特徴とする、復号装置。
【請求項２】
既知乱数に由来する成分を除去したデータから、ノイズをメッセージとして復号するための手段を設けたことを特徴とする、請求項１の復号装置。
【請求項３】
メッセージｍを復号する際の誤り訂正によりノイズの一部を復号すると共に、ベクトルＢから既知乱数に由来する成分を除去したデータと組み合わせて、ノイズの他の部分を復号する手段を設けたことを特徴とする、請求項２の復号装置。
【請求項４】
メッセージｍを誤り訂正可能な符号に符号化したものにノイズｅを混合した暗号文を、前記符号の誤り訂正能力を用いて平文へ復号するための復号プログラムにおいて、
受信した暗号文Ｃに由来するベクトルＣＰ-1から、少なくとも２つのサブベクトル
ＣＰ-1Ｒ,ＣＰ-1Ｌを生成するための命令と、
前記少なくとも２つのサブベクトルＣＰ-1Ｌ,ＣＰ-1Ｒを組み合わせてベクトルＢを求めるための命令と、
ベクトルＢの特定の成分から、少なくともデータｍ~k+1を求めるための手段と、
既知の乱数とデータｍ~k+1とから、ベクトルＢもしくはベクトルＣＰ-1の、少なくとも一部の成分に対して、前記既知乱数に由来する成分を消去したデータを求めるための命令と、
前記既知乱数に由来する成分を除去したデータから、誤り訂正によりメッセージｍを復号するための命令とを設けたことを特徴とする、復号プログラム。
【請求項５】
通信手段と、メッセージｍを誤り訂正可能な符号に符号化したものにノイズｅを混合して暗号化するための暗号化手段と、受信した暗号文を前記符号の誤り訂正能力を用いて平文へ復号するための復号手段とを備えた暗号通信装置において、
前記復号手段は、
受信した暗号文Ｃに由来するベクトルＣＰ-1から、少なくとも２つのサブベクトル
ＣＰ-1Ｒ,ＣＰ-1Ｌを生成するための手段と、
前記少なくとも２つのサブベクトルＣＰ-1Ｌ,ＣＰ-1Ｒを組み合わせてベクトルＢを求めるための手段と、
ベクトルＢの特定の成分から、少なくともデータｍ~k+1を求めるための手段と、
既知の乱数とデータｍ~k+1とから、ベクトルＢもしくはベクトルＣＰ-1、の少なくとも一部の成分に対して、前記既知乱数に由来する成分を消去したデータを求めるための手段と、
前記既知乱数に由来する成分を除去したデータから、誤り訂正によりメッセージｍを復号するための手段とを備えていることを特徴とする、暗号通信装置。
【請求項６】
前記暗号通信装置は、符号化行列
Ｋ＝ ｜ＧA,ＧB｜
｜ Ｒ ｜
に由来する変換を公開鍵とすることを特徴とする、請求項５の暗号通信装置。
ここにＧA,ＧBは符号化行列で、ＧAで符号化した符号とＧBで符号化した符号とは相互変換が自在である。Ｒは少なくとも１行の乱数ベクトルである。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【公開番号】特開２００６−１３３３８０（Ｐ２００６−１３３３８０Ａ）
【公開日】平成１８年５月２５日（２００６．５．２５）
【国際特許分類】
【出願番号】特願２００４−３２０５７９（Ｐ２００４−３２０５７９）
【出願日】平成１６年１１月４日（２００４．１１．４）
【出願人】（０００００６２９７）村田機械株式会社 (4,916)
【出願人】（５９７００８６３６）
【Ｆターム（参考）】
【公開日】平成１８年５月２５日（２００６．５．２５）
【国際特許分類】
【出願日】平成１６年１１月４日（２００４．１１．４）
【出願人】（０００００６２９７）村田機械株式会社 (4,916)
【出願人】（５９７００８６３６）
【Ｆターム（参考）】
[ Back to top ]