(57)【特許請求の範囲】
【請求項１】
平文から積和型の暗号文を得る暗号化装置において、暗号化すべき平文を分割して平文ベクトルを得る手段と、前記平文ベクトルに所定の変換を施して変換ベクトルを生成する手段と、前記平文ベクトル及び前記変換ベクトルの成分と公開鍵ベクトルの成分とによる積和演算により暗号文を得る手段とを備えることを特徴とする暗号化装置。
【請求項２】
前記暗号文を得る手段は、前記平文ベクトルの各成分と前記変換ベクトルの各成分とを交互に用いて前記公開鍵ベクトルの成分との積和演算を行うようにした請求項１記載の暗号化装置。
【請求項３】
前記公開鍵ベクトルは基数積ベクトルを基にモジュラ変換したものである請求項１または２記載の暗号化装置。
【請求項４】
前記平文ベクトル及び前記変換ベクトルの成分は（ｍ1 ，ｍ2 ，…，ｍK ）と示され、前記公開鍵ベクトルの成分は基数積ベクトル（Ｂ1 ，Ｂ2 ，…，ＢK ）（但し、基数ｂi （１≦ｉ≦Ｋ）を用いてＢi ＝ｂ1 ｂ2 …ｂi ）の成分Ｂi をモジュラ変換したものであり、前記基数ｂi として、ｍi が前記変換ベクトルの成分である場合にはｂi ＞ｍi-1 を満たす正規基数を用い、ｍi が前記平文ベクトルの成分である場合にはｂi ≦ｍi-1 を満たす退化基数を用いるようにした請求項１または２記載の暗号化装置。
【請求項５】
請求項１〜４の何れかに記載の暗号化装置にて得られる暗号文を復号する装置であって、復号した前記平文ベクトルの成分に基づいて前記変換ベクトルを復号する手段を備えることを特徴とする復号装置。
【請求項６】
複数のエンティティ装置間で暗号文による情報通信を行う暗号通信システムにおいて、請求項１〜４の何れかに記載の暗号化装置と、得た暗号文を一方のエンティティ装置から他方のエンティティ装置へ送信する通信路と、送信された暗号文から元の平文を復号する復号装置とを備えることを特徴とする暗号通信システム。
【請求項７】
コンピュータを請求項１記載の暗号化装置として機能させるためのコンピュータプログラムを記録してあることを特徴とする記録媒体。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、平文を積和型の暗号文に変換するための暗号化装置、及び、積和型の暗号文を平文に変換するための復号装置、並びに、これらを用いた暗号通信システム及びこの暗号化装置の動作プログラムを記録した記録媒体に関する。
【０００２】
【従来の技術】
高度情報化社会と呼ばれる現代社会では、コンピュータネットワークを基盤として、ビジネス上の重要な文書・画像情報が電子的な情報という形で伝送通信されて処理される。このような電子情報は、容易に複写が可能である、複写物とオリジナルとの区別が困難であるという性質があり、情報保全の問題が重要視されている。特に、「コンピュータリソースの共有」，「マルチアクセス」，「広域化」の各要素を満たすコンピュータネットワークの実現が高度情報化社会の確立に不可欠であるが、これは当事者間の情報保全の問題とは矛盾する要素を含んでいる。このような矛盾を解消するための有効な手法として、人類の過去の歴史上主として軍事，外交面で用いられてきた暗号技術が注目されている。
【０００３】
暗号とは、情報の意味が当事者以外には理解できないように情報を交換することである。暗号において、誰でも理解できる元の文（平文）を第三者には意味がわからない文（暗号文）に変換することが暗号化であり、また、暗号文を平文に戻すことが復号であり、この暗号化と復号との全過程をまとめて暗号系と呼ぶ。暗号化の過程及び復号の過程には、それぞれ暗号化鍵及び復号鍵と呼ばれる秘密の情報が用いられる。復号時には秘密の復号鍵が必要であるので、この復号鍵を知っている者のみが暗号文を復号でき、暗号化によって情報の秘密性が維持され得る。
【０００４】
暗号化方式は、大別すると共通鍵暗号系と公開鍵暗号系との二つに分類できる。共通鍵暗号系では、暗号化鍵と復号鍵とが等しく、送信者と受信者とが同じ共通鍵を持つことによって暗号通信を行う。送信者が平文を秘密の共通鍵に基づいて暗号化して受信者に送り、受信者はこの共通鍵を用いて暗号文を元に平文に復号する。
【０００５】
これに対して公開鍵暗号系では、暗号化鍵と復号鍵とが異なっており、公開されている受信者の公開鍵で送信者が平文を暗号化し、受信者が自身の秘密鍵でその暗号文を復号することによって暗号通信を行う。公開鍵は暗号化のための鍵、秘密鍵は公開鍵によって変換された暗号文を復号するための鍵であり、公開鍵によって変換された暗号文は秘密鍵でのみ復号することができる。
【０００６】
【発明が解決しようとする課題】
公開鍵暗号系の１つである、整数環上の演算を利用した積和型暗号に関して、新規な方式及び攻撃法が次々に提案されているが、特に、多くの情報を短時間で処理できるように高速復号可能な暗号化・復号の手法の開発が望まれている。そこで、本発明者等は、多進法を用いることにより、高速な復号処理を可能とした積和型暗号における暗号化方法及び復号方法を提案している（特願平１０−２６２０３６号）。
【０００７】
この暗号化方法及び復号方法における処理は、以下のように行う。暗号化すべき平文をＫ分割して平文ベクトルｍ＝（ｍ１  ，ｍ２  ，…，ｍＫ  ）を得る。また、基数ｂｉ  （１≦ｉ≦Ｋ）による基数積と，乱数ｖｉ  とを用いてＢｉ  ＝ｖｉ  ｂ１  ｂ２  …ｂｉ  を設定する。Ｐを素数とし、乱数ｗとこのＢｉ  とを用いて公開鍵ｃｉ  はｃｉ  ≡ｗＢｉ  （ｍｏｄ  Ｐ）により計算される。ここで、ｃｉ  は公開鍵、ｂｉ  ，ｖｉ  ，Ｐ，ｗは秘密鍵である。送信者は、公開鍵ｃｉ  を用いて暗号文Ｃ＝ｍ１  ｃ１  ＋ｍ２  ｃ２  ＋・・・＋ｍＫ  ｃＫ  による暗号化を行う。受信者は、中間復号文Ｍ≡ｗ−１Ｃ（ｍｏｄ  Ｐ）を求め、逐次復号アルゴリズムにより復号を行う。このようにして、平文を多進法を用いて表現するようにしたので、高速な復号を行うことができる。
【０００８】
また、ＬＬＬ（Ｌｅｎｓｔｒａ−Ｌｅｎｓｔｒａ−Ｌｏｖａｓｚ）法を用いた低密度攻撃に対して強くすることを目的として、上記暗号化方法の改良方法を本発明者等は提案している（特願平１１−１７３３３８号，以下先行例という）。この先行例は、誤り訂正符号を用いた退化積和型暗号方式であり、上記暗号化方法及び復号方法に以下のような要素を付加したものである。
１．暗号化すべき各分割平文を誤り訂正符号化したものを上記ｍｉ  とする。
２．基数｛ｂｉ  ｝のうち、特定の位置以降には適当な個数の退化基数を用い．その他は正規基数を用いる。但し、退化基数，正規基数は夫々ｍｉ−１  ≧ｂｉ  ，ｍｉ−１  ＜ｂｉ  を満たす基数である。
３．退化基数の影響によって復号できないｍｉ  に関しては、誤り訂正符号の能力を用いて復号する。
【０００９】
先行例では、最も前に配置された退化基数の前までのｍｉ  を解読できることが判明した。そこで、最初の退化基数をできる限り前に配置することが考えられるが、このようにした場合には、大きな誤り訂正能力が必要であって実用的でないという問題点がある。
【００１０】
このような退化基数を用いる手法は、平文に冗長性を持たせて密度（入力平文長／暗号文長）を大きくでき、ＬＬＬ法に基づく攻撃に対する耐性の向上を期待できる有効な手法であり、本発明者等は、このような退化積和型暗号方式の更なる手法を研究している。
【００１１】
本発明は斯かる事情に鑑みてなされたものであり、先行例の問題点を解決できて、ＬＬＬ法に基づく攻撃に対して強く、高速に暗号化及び復号を行える暗号化装置及び復号装置、並びに、これらを用いた暗号通信システム及びこの暗号化装置の動作プログラムを記録した記録媒体を提供することを目的とする。
【００１２】
【課題を解決するための手段】
請求項１に係る暗号化装置は、平文から積和型の暗号文を得る暗号化装置において、暗号化すべき平文を分割して平文ベクトルを得る手段と、前記平文ベクトルに所定の変換を施して変換ベクトルを生成する手段と、前記平文ベクトル及び前記変換ベクトルの成分と公開鍵ベクトルの成分とによる積和演算により暗号文を得る手段とを備えることを特徴とする。
【００１３】
請求項２に係る暗号化装置は、請求項１において、前記暗号文を得る手段は、前記平文ベクトルの各成分と前記変換ベクトルの各成分とを交互に用いて前記公開鍵ベクトルの成分との積和演算を行うようにしたことを特徴とする。
【００１４】
請求項３に係る暗号化装置は、請求項１または２において、前記公開鍵ベクトルは基数積ベクトルを基にモジュラ変換したものであることを特徴とする。
【００１５】
請求項４に係る暗号化装置は、請求項１または２において、前記平文ベクトル及び前記変換ベクトルの成分は（ｍ1 ，ｍ2 ，…，ｍK ）と示され、前記公開鍵ベクトルの成分は基数積ベクトル（Ｂ1 ，Ｂ2 ，…，ＢK ）（但し、基数ｂi （１≦ｉ≦Ｋ）を用いてＢi ＝ｂ1 ｂ2 …ｂi ）の成分Ｂi をモジュラ変換したものであり、前記基数ｂi として、ｍi が前記変換ベクトルの成分である場合にはｂi ＞ｍi-1 を満たす正規基数を用い、ｍi が前記平文ベクトルの成分である場合にはｂi ≦ｍi-1 を満たす退化基数を用いるようにしたことを特徴とする。
【００１７】
請求項５に係る復号装置は、請求項１〜４の何れかに記載の暗号化装置にて得られる暗号文を復号する装置であって、復号した前記平文ベクトルの成分に基づいて前記変換ベクトルを復号する手段を備えることを特徴とする。
【００１９】
請求項６に係る暗号通信システムは、複数のエンティティ装置間で暗号文による情報通信を行う暗号通信システムにおいて、請求項１〜４の何れかに記載の暗号化装置と、得た暗号文を一方のエンティティ装置から他方のエンティティ装置へ送信する通信路と、送信された暗号文から元の平文を復号する復号装置とを備えることを特徴とする。
【００２１】
請求項７に係る記録媒体は、コンピュータを請求項１記載の暗号化装置として機能させるためのコンピュータプログラムを記録してあることを特徴とする。
【００２２】
誤り訂正符号を用いた退化積和型暗号方式である先行例では、それまでの積和型暗号方式と比べて高密度であるので、ＬＬＬ法に基づく攻撃に強いと考えられていたが、解読されることが判明した。この解読の原因は、退化基数を連続的に末尾に配置したことに由来する。従って、ＬＬＬ法に基づく攻撃に強くするためには、退化基数を比較的前方に配置することが有効であると考えられる。但し、先行例では退化基数を前方に配置した場合、誤り訂正能力を大きくしなければならなかった。
【００２３】
本発明では、平文の拡大変換を用いた退化積和型暗号方式を提案する。本発明では、誤り訂正符号とは異なる拡大変換という新たな手法を導入する。暗号化すべき平文ベクトルに所定の変換を施して密度向上のための変換ベクトルを生成して、平文の拡大変換を行う。そして、平文ベクトル及び変換ベクトルの成分と公開鍵ベクトルの成分とによる積和演算により暗号文を得る。暗号文の復号時に、通常の復号が適用できない退化部分を、上記所定の変換に応じて再生する。
【００２４】
本発明では、平文の拡大変換という手法により、より多くの退化基数を配置することが可能となる。よって、積和型暗号の特徴である暗号化・復号の高速性を維持しながら、密度を容易に大きく設定できてＬＬＬ法に基づく攻撃に強い。また、誤り訂正符号のような複雑な暗号化／復号処理が必要ではなく、簡単に暗号化／復号処理を行える。
【００２５】
【発明の実施の形態】
以下、本発明の実施の形態について具体的に説明する。
図１は、退化積和型暗号方式を採用した本発明における暗号化方法をエンティティａ，ｂ間の情報通信に利用した状態を示す模式図である。図１の例では、一方のエンティティａ側で、平文Ｘを暗号文Ｃに暗号化し、通信路１を介してその暗号文Ｃを他方のエンティティｂへ送信し、エンティティｂ側で、その暗号文Ｃを元の平文Ｘに復号する場合を示している。
【００２６】
送信側のエンティティａには、平文Ｘを複数の分割平文に分割して複数のメッセージｍ１  ，ｍ３  ，…ｍ２ｊ−１，…を得る平文分割器２と、これらの奇数番目のメッセージｍ１  ，ｍ３  ，…ｍ２ｊ−１，…から密度を向上させるためのダミーメッセージｍ２  ，ｍ４  ，…ｍ２ｊ，…を生成するダミーメッセージ生成器３と、これらのメッセージｍ１  ，ｍ２  ，ｍ３  ，ｍ４  ，…ｍ２ｊ−１，ｍ２ｊ，…，ｍＫ  と公開鍵ｃ１  ，ｃ２  ，…，ｃＫ  とを用いて暗号文Ｃを作成する暗号化器４とが備えられている。一方、受信側のエンティティｂには、後述する分岐逐次復号アルゴリズムに従って各メッセージｍｉ  （１≦ｉ≦Ｋ）を求めて、送られてきた暗号文Ｃを元の平文Ｘに復号する復号器５が備えられている。
【００２７】
次に、具体的な手法について説明する。
〔準備〕
秘密鍵と公開鍵とを以下のように準備する。
・秘密鍵：｛ｂｉ  ｝，｛ｖｉ  ｝，Ｐ，ｗ
・公開鍵：｛ｃｉ  ｝，ｆ（・）
【００２８】
各メッセージｍｉ  の大きさをｅビットとする。即ち、各メッセージｍｉ  は下記（１）を満たす。
ｍｉ  ＜２ｅ            …（１）
【００２９】
まず、平文Ｘを分割して、奇数番目のメッセージｍ１  ，ｍ３  ，…ｍ２ｊ−１，…を得る。次に、メッセージ生成関数ｆ（・）を用いて、奇数番目のメッセージｍ２ｊ−１から偶数番目のメッセージｍ２ｊを生成することにより、平文の拡大変換を行う。ここで、偶数番目のメッセージは密度を向上させるためのダミーメッセージであり、全メッセージの総数をＫとした場合、真に有効なメッセージの数は下記（２）となる。
【００３０】
【数１】
0003587763.tif 000002
【００３１】
また、基数ｂｉ  は下記（３）を満たす整数とする。
【００３２】
【数２】
0003587763.tif 000003
【００３３】
基数積ｂ１  ｂ２  …ｂｉ  に乱数ｖｉ  を乗じて、基数ベクトルＢ＝（Ｂ１  ，Ｂ２  ，…，ＢＫ  ）を下記（４）のように設定する。
Ｂｉ  ＝ｖｉ  ｂ１  ｂ２  …ｂｉ        …（４）
【００３４】
ここで、上記（４）で示される各成分Ｂｉ  がほぼ同じ大きさになるように乱数ｖｉ  を設定する。但し、ｇｃｄ（ｖｉ  ，ｂｉ＋１  ）＝１を満たすものとする。
【００３５】
乱数ｗを用いて、公開鍵ｃｉ  は下記（５）のモジュラ変換により求められる。
ｃｉ  ≡ｗＢｉ    （ｍｏｄ  Ｐ）      …（５）
【００３６】
〔暗号化〕
暗号文Ｃは、各メッセージｍｉ  と公開鍵ｃｉ  とを用いた積和演算によって与えられる。暗号文Ｃは、具体的には下記（６）のように表される。
Ｃ＝ｍ１  ｃ１  ＋ｍ２  ｃ２  ＋・・・＋ｍＫ  ｃＫ        …（６）
【００３７】
〔復号〕
以下のようにして復号処理が行われる。暗号文Ｃに対して、中間復号文Ｍを下記（７）のようにして求める。
Ｍ≡ｗ−１Ｃ  （ｍｏｄ  Ｐ）      …（７）
【００３８】
そして、下記（８）に示す分岐逐次復号アルゴリズムに従って、各メッセージｍｉ  の復号を行う。
【００３９】
【数３】
0003587763.tif 000004
【００４０】
このアルゴリズムにあっては、奇数番目のメッセージｍｉ  については従来と同様の手法にて復号し、偶数番目のメッセージｍｉ  についてはメッセージ生成関数ｆ（・）を用いてｍｉ  ＝ｆ（ｍｉ−１  ）により復号する。
【００４１】
ここで、メッセージ生成関数ｆ（・）について考察する。本発明の暗号化方式がＬＬＬ法に基づく攻撃に高い耐性を有するためには、ｆ（・）が線形であってはならない。例えば、ｆ（・）が恒等変換である場合、即ちｍ２ｊ＝ｍ２ｊ−１である場合には、暗号文Ｃを下記（９）のように変形できるので、下記（１０）に示すようにして公開鍵を下記（１１）の個数に変換し、低密度攻撃を適用すれば、平文を求めることが可能である。
【００４２】
【数４】
0003587763.tif 000005
【００４３】
また、ｆ（・）が非線形である場合でも、必ずしも安全である保証はない。例えば、ｆ（ｘ）＝ａｘ＋ｂ（具体的に、ｆ（・）がメッセージｍｉ  の各ビットを反転するものであるときにはａ＝−１，ｂ＝２ｅ  −１）とした場合、暗号文Ｃを下記（１２）のように変形できるので、下記（１３），（１４）に示すようになることにより、公開鍵を下記（１５）の個数に変換し、同様に低密度攻撃を適用すれば、平文を求めることが可能である。
【００４４】
【数５】
0003587763.tif 000006
【００４５】
安全と考えられるメッセージ生成関数ｆ（・）としては、下記（１６），（１７）等を一例として挙げることができる。但し、ｑはｅビットの素数、ｕはｅビットの整数とする。
【００４６】
【数６】
0003587763.tif 000007
【００４７】
このメッセージ生成関数ｆ（・）は、信頼できるセンタが公開しても良いし、エンティティが公開するようにしても良い。このｆ（・）におけるビット演算は整数環上での非線形な変換であるので、上記（１７）のような論理演算を導入した場合、センタが公開したｕをパラメータとするｆ（・）に対し、エンティティはｕのみを公開する方法も可能である。
【００４８】
次に、本発明の暗号化方式における暗号化レートと密度とについて考察する。退化積和型暗号における暗号化レートｒは、平文長／暗号文長で定義される。また、密度ρは退化積和型暗号への入力文長／暗号文長で定義され、本発明の方式では密度ρは拡大平文長／暗号文長である。ここで、平文長ＬＰ  ，拡大平文長ＬＥ  ，暗号文長ＬＣ  は夫々下記（１８），（１９），（２０）のようになる。よって、暗号化レートｒ，密度ρは夫々下記（２１），（２２）のようになる。
【００４９】
【数７】
0003587763.tif 000008
【００５０】
本発明の暗号化方式にあって、ｅ′／ｅの値、即ち退化基数のビットサイズｅ′を小さくした場合に、暗号化レートｒは大きくなり、密度ρも向上する。従って、退化基数サイズを小さくすることにより、ＬＬＬ法に基づく攻撃に対して高い耐性を有することができる。
【００５１】
本発明の暗号化方式では、上記（２０），（２２）より、最小ブロック数Ｋ＝３である場合でも密度ρは１を超え、ＬＬＬ法に基づく攻撃に対して高い耐性を有することを期待できる。この場合、ｅ＝６４，ｅ′／ｅ＝αとしたときに、暗号文長ＬＣ  は下記（２３）の条件を満たすことができ、従来の公開鍵暗号と比較して、ブロックサイズが非常に小さい画期的な暗号方式を設計できる。
ＬＣ  ＝１２８＋１．６＋６４α＜１９４      …（２３）
【００５２】
図２は、本発明の記録媒体の実施の形態の構成を示す図である。ここに例示するプログラムは、上述した例において、暗号化すべき平文を分割して奇数番目のメッセージを得る処理、メッセージ生成関数ｆ（・）を用いて奇数番目のメッセージから偶数番目のメッセージを生成する処理、及び、これらのメッセージと公開鍵とを用いて積和型の暗号文を作成する処理を含んでいるか、または、上述した分岐逐次復号アルゴリズムに従って暗号文を元の平文に復号する処理を含んでおり、以下に説明する記録媒体に記録されている。なお、コンピュータ２０は、送信側または受信側のエンティティに設けられている。
【００５３】
図２において、コンピュータ２０とオンライン接続する記録媒体２１は、コンピュータ２０の設置場所から隔たって設置される例えばＷＷＷ（Ｗｏｒｌｄ  Ｗｉｄｅ  Ｗｅｂ）のサーバコンピュータを用いてなり、記録媒体２１には前述の如きプログラム２１ａが記録されている。記録媒体２１から読み出されたプログラム２１ａがコンピュータ２０を制御することにより、コンピュータ２０が、平文から暗号文を作成するか、または、暗号文を平文に復号する。
【００５４】
コンピュータ２０の内部に設けられた記録媒体２２は、内蔵設置される例えばハードディスクドライブまたはＲＯＭなどを用いてなり、記録媒体２２には前述の如きプログラム２２ａが記録されている。記録媒体２２から読み出されたプログラム２２ａがコンピュータ２０を制御することにより、コンピュータ２０が、平文から暗号文を作成するか、または、暗号文を平文に復号する。
【００５５】
コンピュータ２０に設けられたディスクドライブ２０ａに装填して使用される記録媒体２３は、運搬可能な例えば光磁気ディスク，ＣＤ−ＲＯＭまたはフレキシブルディスクなどを用いてなり、記録媒体２３には前述の如きプログラム２３ａが記録されている。記録媒体２３から読み出されたプログラム２３ａがコンピュータ２０を制御することにより、コンピュータ２０が、平文から暗号文を作成するか、または、暗号文を平文に復号する。
【００５６】
なお、上述した例では、暗号通信システムの場合について説明したが、平文を暗号化して暗号文を作成し、作成した暗号文を単に記録するような場合にも、本発明の暗号化方法を適用できることは勿論である。
【００５７】
【発明の効果】
以上のように、本発明では、平文の拡大変換を用いて暗号化するようにしたので、先行例に比べて、ＬＬＬ法に基づく攻撃に対する耐性を向上できる。また、誤り訂正符号を用いた先行例のように複雑な暗号化／復号処理を必要とせず、暗号化／復号時の演算処理を少なくでき、簡単かつ高速に暗号化／復号処理を行える。また、暗号ブロック数の低減も図れるので、小規模なハードウェアにより暗号通信システムを構築できる。この結果、積和型暗号の実用化の道を開くことに、本発明は大いに寄与できる。
【図面の簡単な説明】
【図１】２人のエンティティ間における情報の通信状態を示す模式図である。
【図２】記録媒体の実施の形態の構成を示す図である。
【符号の説明】
１  通信路
２  平文分割器
３  ダミーメッセージ生成器
４  暗号化器
５  復号器
２０  コンピュータ
２１，２２，２３  記録媒体
ａ，ｂ  エンティティ
【図１】
0003587763.tif 000009
【図２】
0003587763.tif 000010