TOP > 国内特許検索 > 複数のナップザックを用いる公開鍵暗号方式による暗号システム、鍵生成装置、暗号化装置、復号装置、データ交換方法およびプログラム > 明細書

明細書 :複数のナップザックを用いる公開鍵暗号方式による暗号システム、鍵生成装置、暗号化装置、復号装置、データ交換方法およびプログラム

発行国 日本国特許庁(JP)
公報種別 特許公報(B2)
特許番号 特許第5464341号 (P5464341)
公開番号 特開2011-128281 (P2011-128281A)
登録日 平成26年1月31日(2014.1.31)
発行日 平成26年4月9日(2014.4.9)
公開日 平成23年6月30日(2011.6.30)
発明の名称または考案の名称 複数のナップザックを用いる公開鍵暗号方式による暗号システム、鍵生成装置、暗号化装置、復号装置、データ交換方法およびプログラム
国際特許分類 G09C   1/00        (2006.01)
FI G09C 1/00 620Z
請求項の数または発明の数 14
全頁数 21
出願番号 特願2009-285093 (P2009-285093)
出願日 平成21年12月16日(2009.12.16)
審査請求日 平成24年12月11日(2012.12.11)
特許権者または実用新案権者 【識別番号】599011687
【氏名又は名称】学校法人 中央大学
発明者または考案者 【氏名】辻井 重男
【氏名】小林 邦勝
【氏名】笠原 正雄
個別代理人の代理人 【識別番号】110000420、【氏名又は名称】特許業務法人エム・アイ・ピー
審査官 【審査官】石田 信行
参考文献・文献 特開2011-33809(JP,A)
特開2010-256549(JP,A)
特開2007-140095(JP,A)
特開2006-235291(JP,A)
小林 邦勝,既知の攻撃法に耐性をもつナップザック暗号,電子情報通信学会技術研究報告 Vol.108 No.355,日本,社団法人電子情報通信学会,2008年12月10日,41~44頁
小林 邦勝,2つの演算を用いるナップザック暗号(その2),電子情報通信学会技術研究報告 Vol.107 No.500,日本,社団法人電子情報通信学会,2008年 2月21日,45~48頁
調査した分野 G09C 1/00
特許請求の範囲 【請求項1】
ナップザック問題を安全性の根拠とした公開鍵暗号方式による、鍵生成装置、暗号化装置および復号装置を含む暗号システムであって、前記鍵生成装置は、
個々は超増加性を示さない複数の秘密鍵数列を、前記複数の秘密鍵数列それぞれの要素を変数として非線形関数により組み合わせると超増加性を満たすという条件のもと、生成する秘密鍵生成手段と、
法と、前記法と互いに素な複数の乗数とをさらに秘密鍵として定めて、前記複数の秘密鍵数列それぞれの要素をモジュラ変換し、複数の公開鍵数列を生成する公開鍵生成手段とを含み、前記暗号化装置は、
前記複数の公開鍵数列それぞれと平文との内積を求めて複数のナップザックを計算し、計算した前記複数のナップザックを前記非線形関数に対応して演算し、暗号文を生成する暗号化手段を含み、前記復号装置は、
前記法による前記乗数の乗法逆元と、前記法とを用いて、受信した暗号文を逆モジュラ変換し、前記複数の秘密鍵数列を用いて前記暗号文から平文を一意に復号する復号手段を含む、
暗号システム。
【請求項2】
前記非線形関数により組み合わせると超増加性を満たすという前記条件とは、前記複数の秘密鍵数列をQ(j=1,...,N)とし、前記秘密鍵数列Qそれぞれのn個あるうちのi番目の要素をqとし、要素qから要素qi-1までの和をS(j=1,...,N)とし、前記要素qまたは前記和Sを変数とする前記非線形関数をfとして、前記秘密鍵数列Qそれぞれのi=2,...,nについての各要素q(j=1,...,N)が、下記不等式(1)
【数1】
JP0005464341B2_000015t.gif
を満たすという条件である、請求項1に記載の暗号システム。
【請求項3】
前記法pは、下記式(2)
【数2】
JP0005464341B2_000016t.gif
を満たすように選択され、前記複数の公開鍵数列を生成するための前記モジュラ変換は、前記複数の公開鍵数列をO(j=1,...,N)とし、前記公開鍵数列Oそれぞれのn個あるうちのi番目の要素をoとし、前記複数の乗数をr(j=1,...,N)として、下記式(3)
【数3】
JP0005464341B2_000017t.gif
で表される、請求項2に記載の暗号システム。
【請求項4】
前記平文Mのn個あるうちのi番目の要素をm(∈{0,1})とし、前記ナップザックをCとして、前記暗号文Cは、下記式(4)
【数4】
JP0005464341B2_000018t.gif
で演算される、請求項3に記載の暗号システム。
【請求項5】
前記復号手段は、前記法pによる前記乗数rの前記乗法逆元r-1と、前記法pとを用いて、受信した暗号文Cを逆モジュラ変換し、下記式(5)
【数5】
JP0005464341B2_000019t.gif
にて表される剰余D(C)を算出し、下記判定式(6)
【数6】
JP0005464341B2_000020t.gif
に従って、平文Mの要素mを判定する、請求項4に記載の暗号システム。
【請求項6】
N=3であり、前記乗数rはr×rと等しく、前記非線形関数fは、2変数の積と変数との和であり、前記不等式(1)、前記式(2)、前記式(4)、前記式(5)および前記判定式(6)は、下記不等式(7)、下記式(8)、下記式(9)、下記式(10)および下記判定式(11)
【数7】
JP0005464341B2_000021t.gif
で表される、請求項5に記載の暗号システム。
【請求項7】
N=2であり、前記非線形関数fは、2変数の積であり、前記不等式(1)、前記式(2)、前記式(4)、前記式(5)および前記判定式(6)は、下記不等式(12)、下記式(13)、下記式(14)、下記式(15)および下記判定式(16)
【数8】
JP0005464341B2_000022t.gif
で表される、請求項5に記載の暗号システム。
【請求項8】
ナップザック問題を安全性の根拠とした公開鍵暗号方式による鍵生成を実行する鍵生成装置であって、前記鍵生成装置は、
個々は超増加性を示さない複数の秘密鍵数列を、前記複数の秘密鍵数列それぞれの要素を変数として非線形関数により組み合わせると超増加性を満たすという条件のもと、生成する秘密鍵生成手段と、
法と、前記法と互いに素な複数の乗数とをさらに秘密鍵として定めて、前記複数の秘密鍵数列それぞれの要素をモジュラ変換し、複数の公開鍵数列を生成する公開鍵生成手段とを含む、鍵生成装置。
【請求項9】
ナップザック問題を安全性の根拠とした公開鍵暗号方式による複数の公開鍵数列を使用した暗号化処理を実行する暗号化装置であって、前記暗号化装置は、
前記複数の公開鍵数列それぞれと平文との内積を求めて複数のナップザックを計算し、秘密鍵生成に用いた非線形関数に対応して前記複数のナップザックを演算し、暗号文を生成する暗号化手段を含み、前記複数の公開鍵数列は、
個々は超増加性を示さない複数の秘密鍵数列であって、それぞれの要素を変数とした前記非線形関数により組み合わせると超増加性示すという条件のもと生成された当該複数の秘密鍵数列から、法と前記法と互いに素な複数の乗数とをさらに秘密鍵として用いて、前記複数の秘密鍵数列それぞれの要素をモジュラ変換して生成されたものである、暗号化装置。
【請求項10】
ナップザック問題を安全性の根拠とした公開鍵暗号方式による復号処理を実行する復号装置であって、前記復号装置は、
個々は超増加性を示さない複数の秘密鍵数列であって、それぞれの要素を変数として非線形関数により組み合わせると超増加性示す条件のもと生成される当該複数の秘密鍵数列と、前記秘密鍵数列から複数の公開鍵数列を生成する際に用いられた秘密鍵としての法および前記法と互いに素な複数の乗数とを用いて、前記法による前記乗数の乗法逆元を算出し、受信した暗号文を逆モジュラ変換し、前記複数の秘密鍵数列を用いて前記暗号文から平文を一意に復号する復号手段を含む、復号装置。
【請求項11】
ナップザック問題を安全性の根拠とした公開鍵暗号方式によるデータ交換方法であって、前記方法は、
個々は超増加性を示さない複数の秘密鍵数列を、前記複数の秘密鍵数列それぞれの要素を変数として非線形関数により組み合わせると超増加性を満たすという条件のもと生成するステップと、
法と、前記法と互いに素な複数の乗数とをさらに秘密鍵として定めて、前記複数の秘密鍵数列それぞれの要素をモジュラ変換し、複数の公開鍵数列を生成するステップと、
前記複数の秘密鍵数列と、前記法と、前記複数の乗数とをデータ受取側の装置で保持するとともに、前記複数の公開鍵数列をデータ受渡側の装置で保持するステップと、
前記データ受渡側の装置が、前記複数の公開鍵数列それぞれと平文との内積を求めて複数のナップザックを計算し、計算した前記複数のナップザックを前記非線形関数に対応して演算し、暗号文を生成するステップと、
前記データ受取側の装置が、前記法による前記乗数の乗法逆元と、前記法とを用いて、受信した暗号文を逆モジュラ変換し、前記複数の秘密鍵数列を用いて前記暗号文から平文を一意に復号するステップと
を含む、データ交換方法。
【請求項12】
コンピュータを、請求項8に記載の各手段として機能させるための装置実行可能なプログラム。
【請求項13】
コンピュータを、請求項9に記載の各手段として機能させるための装置実行可能なプログラム。
【請求項14】
コンピュータを、請求項10に記載の各手段として機能させるための装置実行可能なプログラム。
発明の詳細な説明 【技術分野】
【0001】
本発明は、ナップザック問題を安全性の根拠とした公開鍵暗号方式に関し、より詳細には、高い安全性および処理の高速性を実現するナップザック暗号方式による、鍵生成を実行する鍵生成装置と、暗号化処理を実行する暗号化装置と、暗号文の復号処理を実行する復号装置とを含む暗号システム、該鍵生成装置、該暗号化装置、該復号装置、データ交換方法およびプログラムに関する。
【背景技術】
【0002】
近年の情報通信技術の発達およびネットワークのブロードバンド化に伴い、暗号理論に基づく暗号化技術は、ネットワーク上を伝送するデータの機密性および完全性を保証する技術として、ますます重要な技術となっている。
【0003】
このような暗号理論による暗号化方式は、素因数分解問題、離散対数問題、ラティス問題、ナップザック問題などの数学上の問題を安全性の根拠としている。ナップザック問題は、NP完全問題のひとつであり、この一般のナップザック問題に超増加性等の落とし戸を導入して暗号理論に応用したものがナップザック暗号方式である。この超増加性を導入したナップザック暗号方式は、暗号文から平文を一意に復号することができる一方、解読が容易となってしまう。そのため、Markle-Hellmanナップザック暗号(非特許文献1)やChor-Rivestナップザック暗号といった、これまでに提案されている多くのナップザック暗号方式は、LLLアルゴリズム(格子基底縮小アルゴリズム)を用いた攻撃(非特許文献2)や、シャミア攻撃法(非特許文献3)等の解読法による攻撃に対して脆弱性を有し、安全性の問題等から実用されるに至っていない。
【先行技術文献】
【0004】

【非特許文献1】R. C. Merkle and M. E. Hellman, ”Hiding Information and Signatures in Trapdoor Knapsacks”, IEEE Trans. Inf. Theory, IT-24(5), 525-530, September, 1978.
【非特許文献2】J. C. Lagarias and A. M. Odlyzko, ”Solving Low-density Subset Sum Problem,” J. Assoc. Comp. Math., vol.32, no.1, pp.229-246, Preliminary version in Proc. 24th IEEE, 1985.
【非特許文献3】A. Shamir, ”A Polynomial Time Algorithm for Breaking The Basic Merkle-Hellman Cryptosystems”, IEEE Trans. Inform. Theory, vol. IT-30, no.5, 699-704, 1982.
【発明の概要】
【発明が解決しようとする課題】
【0005】
LLLアルゴリズムを用いる攻撃は、与えられた公開鍵と暗号文とから適切な格子を形成し、LLLアルゴリズムによって簡約された基底ベクトルを求めて、平文を求める方法であり、格子の次元が数百程度であれば解けるとされている。上記シャミアの攻撃法は、上記導入した秘密鍵の超増加性の特徴を利用するものである。高い安全性を有する暗号方式を実現するためには、上述したような従来からの攻撃法に対して耐性を持たせる必要がある。
【0006】
本発明は、上記従来からの問題点に鑑みてなされたものであり、本発明は、解読法として代表的なLLLアルゴリズムを用いる攻撃およびシャミア攻撃法による攻撃に対して耐性を有し、高速処理が可能なナップザック問題を安全性の根拠とする新奇なナップザック暗号方式による、鍵生成を実行する鍵生成装置と、暗号化処理を実行する暗号化装置と、暗号文の復号処理を実行する復号装置とを含む暗号システム、該鍵生成装置、該暗号化装置、該復号装置、データ交換方法およびプログラムを提供することを目的とする。
【課題を解決するための手段】
【0007】
本発明は、上記従来技術に鑑みてなされたものであり、本発明では、ナップザック問題を安全性の根拠とし、複数のナップザックを用いた公開鍵暗号方式による鍵生成装置、暗号化装置、復号装置およびこれらを含む暗号システム、データ交換方法およびプログラムを提供する。
【0008】
本発明の鍵生成装置は、まず、複数の秘密鍵数列それぞれの要素を変数として非線形関数により組み合わせると超増加性を満たすという条件のもと、複数の秘密鍵数列を生成する。この生成される秘密鍵数列は、個々では超増加性を示さない。鍵生成装置は、さらに、適切な法と、この法と互いに素な複数の乗数とをさらに秘密鍵として定めて、上記複数の秘密鍵数列それぞれの要素をモジュラ変換し、複数の公開鍵数列を生成する。
【0009】
本発明の暗号化装置は、複数の公開鍵数列それぞれと平文との内積を求めて複数のナップザックを計算し、計算した複数のナップザックを上記非線形関数に対応して演算して暗号文を生成する。一方、本発明の復号装置は、上記秘密鍵の法と乗数とから、法による乗数の乗法逆元を求め、この法と乗法逆元とを用いて、受信した暗号文を逆モジュラ変換し、複数の秘密鍵数列を用いて暗号文から平文を一意に復号する。
【0010】
また本発明では、上記非線形関数により組み合わせると超増加性を満たすという条件としては、複数の秘密鍵数列をQ(j=1,...,N)とし、秘密鍵数列Qそれぞれのn個あるうちのi番目の要素をqとし、要素qから要素qi-1までの和をS(j=1,...,N)とし、要素qまたは前記和Sを変数とする非線形関数をfとして、上記秘密鍵数列Qそれぞれのi=2,...,nについての各要素q(j=1,...,N)が、後述する非線形不等式(1)を満たすという条件を採用することができる。
【0011】
さらに本発明では、鍵生成装置は、後述する式(2)を満たす上記法pを選択し、複数の公開鍵数列をO(j=1,...,N)とし、公開鍵数列Oそれぞれのn個あるうちのi番目の要素をoとし、複数の乗数をr(j=1,...,N)として、後述する式(3)で表されるモジュラ変換により複数の公開鍵数列を生成することができる。
【0012】
さらに本発明では、暗号化装置は、平文Mのn個あるうちのi番目の要素をm(∈{0,1})とし、ナップザックをCとして、暗号文Cを後述する式(4)に従って演算することができる。本発明では、さらに、復号装置は、法pによる乗数rの乗法逆元r-1と、法pとを用いて、受信した暗号文Cを逆モジュラ変換して、後述する式(5)にて表される剰余D(C)を算出し、後述する判定式(6)に従って平文Mの要素mそれぞれを判定することができる。
【発明の効果】
【0013】
上記構成によれば、適切な平文サイズを定めることにより、LLLアルゴリズムにおける格子次元を解読不可能となる次元まで増大させ、LLLアルゴリズムによる攻撃に対する耐性を備えるとともに、個々の秘密鍵数列が超増加性を有さないため、線形不等式を扱うある線形計画法と見なされるシャミア・アルゴリズムによる攻撃に対しても耐性を備えることができる。また、従来のナップザック暗号方式に比べて、鍵サイズが大きくなるが、ナップザック間の演算(例えば乗算)が追加される程度の計算量の増加で済み、高速な暗号化処理および復号処理が実現される。
【図面の簡単な説明】
【0014】
【図1】本発明の実施形態のセキュア通信システムにおけるコンピュータ装置のハードウェア構成図。
【図2】本発明の実施形態によるセキュア通信システムにおいて各コンピュータ装置上に実現される機能ブロック図。
【図3】本実施形態のセキュア通信システムにおいて実行される、3つのナップザックを用いた秘密通信の処理を示すフローチャート。
【図4】本発明の実施形態による、3つのナップザックを用いた公開鍵暗号方式による暗号化処理を示す概念図。
【発明を実施するための形態】
【0015】
以下、本発明を図面に示した特定の実施形態をもって説明するが、本発明は、図面に示した実施形態に限定されるものではない。なお、以下に説明する実施形態では、本発明の暗号システムの一例として、ネットワークを介して秘密通信を実行する複数のコンピュータ装置を含むセキュア通信システムを用いて説明する。

【0016】
1.ハードウェア構成
本実施形態のセキュア通信システムは、ナップザック問題を安全性の根拠とした公開鍵暗号方式による秘密通信を確立する複数のコンピュータ装置10,50を含んで構成される。以下、まず図1を参照しながら、当該コンピュータ装置10,50のハードウェア構成について説明する。

【0017】
図1は、本発明の実施形態のセキュア通信システムにおけるコンピュータ装置10,50のハードウェア構成を示す。図1に示すコンピュータ装置10,50は、概ねパーソナル・コンピュータやワークステーションなどとして構成される。図1に示すコンピュータ装置10,50は、中央演算装置(CPU)12と、CPU12が使用するデータの高速アクセスを可能とするL1およびL2などのレベルを有するキャッシュ・メモリ14と、CPU12の処理を可能とするRAM、DRAMなどの固体メモリ素子から形成されるシステム・メモリ16とを備えている。システム・メモリ16は、本発明の実施形態おいて、鍵生成処理、暗号化処理または復号処理を実行するための作業空間を提供する。

【0018】
CPU12、キャッシュ・メモリ14、およびシステム・メモリ16は、システム・バス18を介して、他のデバイスまたはドライバ、例えば、グラフィックス・ドライバ20およびネットワーク・インタフェース・カード(NIC)22へと接続されている。グラフィックス・ドライバ20は、バスを介してディスプレイ24に接続されて、CPU12による処理結果をディスプレイ画面上に表示させている。また、NIC22は、物理層レベルおよびリンク層レベルでコンピュータ装置10,50を、TCP/IPなどの適切な通信プロトコルを使用するネットワークへと接続し、コンピュータ装置10,50間の通信のインタフェースを提供している。

【0019】
システム・バス18には、さらにI/Oバス・ブリッジ26が接続されている。I/Oバス・ブリッジ26の下流側には、PCIなどのI/Oバス28を介して、IDE、ATA、ATAPI、シリアルATA、SCSI、USBなどにより、ハードディスクなどの記憶装置30が接続されている。記録装置30は、本発明の実施形態において、暗号化処理に用いる秘密鍵または公開鍵を格納するために用いることができる。また、I/Oバス28には、USBなどのバスを介して、キーボードおよびマウスなどのポインティング・デバイスなどの入力装置32が接続されていて、オペレータによる指令をコンピュータ装置10,50に指令している。

【0020】
コンピュータ装置10,50は、Windows 7(登録商標)、Windows(登録商標)Vista、UNIX(登録商標)、LINUX(登録商標)などのオペレーティング・システム上で動作する、FORTRAN、COBOL、PL/I、C、C++、Visual C++、VisualBasic、Java(登録商標)、Perl、Rubyなどのプログラミング言語により記述されたアプリケーション・プログラムを格納し、実行し、後述する各機能部をコンピュータ装置10,50上で機能させている。

【0021】
2.複数のナップザックを用いた公開鍵暗号方式による秘密通信
以下、図2~図4を参照しながら、本発明の実施形態による秘密通信について説明する。なお以下、説明の便宜上、2つのコンピュータ装置間における一方向の通信に注目し、送信するべきメッセージの送信側の装置を、便宜上、送信側コンピュータ装置50と参照し、メッセージの受信側の装置を受信側コンピュータ装置10と参照する。

【0022】
図2は、本発明の実施形態によるセキュア通信システムにおいて各コンピュータ装置上に実現される機能ブロックを示す。図2に示すセキュア通信システムは、受信側コンピュータ装置10と、送信側コンピュータ装置50とを含み構成され、コンピュータ装置10,50間において、ナップザック問題を安全性の根拠とした公開鍵暗号方式による秘密通信を実現している。

【0023】
本実施形態において、受信側コンピュータ装置10は、秘密通信で使用する公開鍵および秘密鍵を生成する鍵生成装置と、生成された秘密鍵を用いて暗号文を復号する復号装置との両方の機能を有する。一方、送信側コンピュータ装置50は、専ら公開鍵を用いて送信すべきメッセージの平文を暗号化する暗号化装置としての機能を有する。なお、他の実施形態では、本受信側コンピュータ装置10は、鍵生成装置としての機能を専ら有するコンピュータ装置と、生成された秘密鍵を安全に取得し、保持し、その秘密鍵を用いて暗号文を復号する復号装置としての機能を専ら有するコンピュータ装置とに分離して構成されていてもよい。

【0024】
本実施形態の受信側コンピュータ装置10は、秘密鍵および公開鍵の生成処理を実行する鍵生成処理部110と、送信側からの暗号文Cを秘密鍵を用いて復号処理を実行する復号処理部120と、復号して得られた平文Mを出力する平文出力部130とを含む。一方、本実施形態の送信側コンピュータ装置50は、安全に送信すべきメッセージの平文Mが入力される平文入力部150と、公開された公開鍵を用いて平文Mに暗号化処理を施す暗号化処理部160とを含む。

【0025】
受信側コンピュータ装置10の鍵生成処理部110は、より具体的には、秘密鍵生成部112と、公開鍵生成部114とを含んで構成される。秘密鍵生成部112は、N個の秘密鍵数列Q(j=1,...,N)を、一定の条件のもと生成する。秘密鍵数列Qは、それぞれ、n個の要素q(i=1,...,n)から構成される数列である。秘密鍵生成部112は、まずq>0またはq≧0の条件下、各秘密鍵数列Qの1番目の要素qの値をランダムに選択し、続いて、それ以降のi=2,...,nについて、各要素qが下記非線形不等式(1)を満たすように当該要素qをランダムに選択する。

【0026】
【数1】
JP0005464341B2_000002t.gif

【0027】
上記式(1)中、関数fは、N個の要素qまたは、要素qから要素qi-1までの和S(j=1,...,N)を変数とした非線形関数を表している。この非線形関数は、複数の変数による和、積といった演算により表現されるものである。非線形関数は、2以上の次数を有する限り、特に限定されるものではないが、好ましくは少なくとも2変数の積を含む演算式を採用することができる。より具体的には、N=2の場合、上記非線形関数fは、第1変数および第2変数の積による2変数2次式、N=3の場合、第1変数および第2変数の積と、第3変数との和による3変数2次式、または3変数の積による3変数3次式、N=4の場合、第1変数および第2変数の積と、第3変数および第4変数の積との和による4変数2次式が好適に採用される。このように生成された秘密鍵数列Qは、個々では超増加性を示さないが、秘密鍵数列Qの各要素qを変数として非線形関数により組み合わせると超増加性を示すものとなる。

【0028】
一方、公開鍵生成部114は、秘密鍵生成部112が生成した複数の秘密鍵数列Qから、対応する複数の公開鍵数列O(j=1,...,N)を生成する。公開鍵数列Oも、n個の要素o(i=1,...,n)から構成される数列である。公開鍵生成部114は、まず下記式(2)を満たす法pをランダムに選択し、さらに、モジュラ変換を行うために、法pと互いに素な複数の乗数r(j=1,...,N)をさらに選択する。

【0029】
【数2】
JP0005464341B2_000003t.gif

【0030】
ここで、法pおよび乗数rは、gcd(r,p)=1を満たすものである。公開鍵生成部114は、続いて、法pおよび乗数rを用い下記式(3)に従って、秘密鍵数列Qの各要素qをモジュラ変換し、公開鍵数列Oの各要素oを算出する。

【0031】
【数3】
JP0005464341B2_000004t.gif

【0032】
それぞれn個の要素を有する秘密鍵数列Q、法pおよび乗数rは、本公開鍵暗号方式おいて秘密鍵を構成し、一方、公開鍵数列Oは、合計n×Nの要素から構成される公開鍵を構成する。送信側コンピュータ装置50は、公開鍵数列Oを取得し、この公開鍵数列Oを用いて暗号化を施し、本受信側コンピュータ装置10へメッセージを送信する。一方、秘密鍵数列Q、法pおよび乗数rは、公開鍵による暗号文を復号するために、コンピュータ装置10の記憶装置30などに、復号処理部120が参照可能なように安全に記憶される。

【0033】
送信側コンピュータ装置50の暗号化処理部160は、送信すべきメッセージの平文Mを平文入力部150から受け取り、公開された公開鍵数列Oを用いて平文Mに暗号化を施して、暗号文Cを受信側コンピュータ装置10へ送信する。送信すべきメッセージの平文Mは、n個の要素m(∈{0,1})から構成される配列である。暗号化処理部160は、下記式(4)に従い、公開鍵数列Oそれぞれと平文Mとの内積を求めてナップザックC(j=1,...,N)を計算し、計算した複数のナップザックCを上述した非線形関数fに対応して演算し、暗号文Cを生成する。

【0034】
【数4】
JP0005464341B2_000005t.gif

【0035】
ここで再び受信側コンピュータ装置10を参照する。受信側コンピュータ装置10の復号処理部120は、秘密鍵である法p、乗数rおよび秘密鍵数列Qを記憶装置30などから読み出し、まず乗数rの法pにおける乗法逆元r-1を算出する。復号処理部120は、続いて、受信した暗号文Cと乗法逆元r-1との積を逆モジュラ変換して、その法pにおける剰余D(C)を算出する。ここで、乗法逆元r-1は、r×r-1≡1(mod p)を満たすものであり、gcd(r,p)=1のとき、法pとするrの逆元r-1は必ず存在する。この剰余D(C)は、下記式(5)に示すように、秘密鍵数列Qそれぞれと平文Mとの内積であるナップザックを上記非線形関数fに対応して演算した結果に合同である。

【0036】
【数5】
JP0005464341B2_000006t.gif

【0037】
復号処理部120は、さらに、平文Mの各要素mについて、n番目から1番目に遡って、算出された剰余D(C)と、暗号鍵数列Qの各要素と、適宜判定済みの平文Mの要素とを用いた下記判定式(6)に従って、当該平文Mの要素mの値を判定し、メッセージの平文Mを一意に復号する。

【0038】
【数6】
JP0005464341B2_000007t.gif

【0039】
3.3つのナップザックを用いた公開鍵暗号方式による秘密通信
以下、図3および図4を参照して、N=3の場合について、より具体的に説明する。N=3の場合、秘密鍵数列は、Q=(q,q,...,q)、Q=(q,q,...,q)、Q=(q,q,...,q)となり、公開鍵数列は、O=(o,o,...,o)、O=(o,o,...,o)、Q=(o,o,...,o)となる。またこの場合において、上記非線形関数fは、例えば、第1変数および第2変数の積と、第3変数との和による3変数2次式(X×Y+Z)を採用することができる。かかる場合には、乗数はr,r,r(=r×r)となる。

【0040】
図3は、本実施形態のセキュア通信システムにおいて実行されるN=3の場合の秘密通信の処理を示すフローチャートである。なお、図3中の左側の処理は、受信側コンピュータ装置10が実行する処理を示し、右側の処理は、送信側コンピュータ装置50が実行する処理を示している。図3に示す処理は、ステップS200で送信側コンピュータ装置50の処理が開始し、送信側コンピュータ装置50は、ステップS201で、送信すべき送信メッセージの平文Mの入力を受け、ステップS202で、送信メッセージの送付先である受信側コンピュータ装置10へ、秘密通信の開始を依頼する。なお、この秘密通信の依頼には、例えば平文Mのビット数nといったセキュリティパラーメータの折衝が含まれてもよい。

【0041】
受信側コンピュータ装置10の処理は、ステップS100で開始され、ステップS101で、送信側コンピュータ装置50からの秘密通信開始の依頼を受け、鍵生成処理を開始する。ステップS102では、受信側コンピュータ装置10の秘密鍵生成部112は、まずq>0、q>0およびq≧0の条件下、各秘密鍵数列Q,Q,Qの1番目の各要素q,q,qを選択し、続いて、それ以降のi=2,...,nの要素qについて、下記不等式(7)を満たすように当該要素qをランダムに選択する。

【0042】
【数7】
JP0005464341B2_000008t.gif

【0043】
ステップS103では、受信側コンピュータ装置10の公開鍵生成部114は、まず下記式(8)を満たす法pを選択し、さらに、法pと互いに素な複数の乗数r,rをさらに選択し、続いて、法pおよび乗数r,rを用いて下記式(3’)に従い、各秘密鍵数列Q,Q,Qの各要素をモジュラ変換し、公開鍵数列O,O,Oの各要素を算出する。

【0044】
【数8】
JP0005464341B2_000009t.gif

【0045】
ステップS104では、生成した公開鍵数列O,O,Oを、秘密通信の要求元の送信側コンピュータ装置50へ送信し、これに対応して、送信側コンピュータ装置50は、ステップS203で、公開鍵数列O,O,Oを受信し、メモリ等に記憶する。ステップS204では、送信側コンピュータ装置50の暗号化処理部160は、下記式(9)に従って、公開鍵数列O,O,Oと平文Mとの内積を求めてナップザックC,C,Cを計算し、暗号文Cを生成する。

【0046】
【数9】
JP0005464341B2_000010t.gif

【0047】
図4は、本発明の実施形態の3つのナップザックを用いた公開鍵暗号方式による暗号化処理を概念的に示す図である。図4に示すように、各ナップザックC,C,Cの演算は、平文M中の値が1である要素mに対応する秘密鍵数列の要素qをそれぞれのナップザックC,C,Cに詰め込むことに相当する。最終的な暗号文Cは、このナップザックC,Cの重みの積とナップザックCの重みとの和として算出される。

【0048】
再び図3を参照すると、送信側コンピュータ装置50は、ステップS205で、生成した暗号文Cを宛先の受信側コンピュータ装置10へ送信し、処理を終了させる。これに対応して、受信側コンピュータ装置10は、ステップS105で、暗号文Cを受信する。ステップS106では、受信側コンピュータ装置10の復号処理部120は、秘密鍵である法p、乗数r,rおよび秘密鍵数列Q,Q,Qを読み出し、まず乗数r,rの法pにおける乗法逆元乗数r-1,r-1を算出し、下記式(10)に従って、暗号文Cと乗法逆元r-1,r-1との積を逆モジュラ変換して、その法pにおける剰余D(C)を算出する。

【0049】
【数10】
JP0005464341B2_000011t.gif

【0050】
ステップS107~ステップS109では、平文Mの各要素mについて、n番目から1番目に遡って、当該平文Mの要素mの値を判定し、メッセージの平文Mを一意に復号する。ステップS108では、復号処理部120は、i番目の要素mについて、上記剰余D(C)と、暗号鍵数列Qの各要素および適宜判定済みの平文Mの要素により算出される要素Iとを用いた下記判定式(11)に従って、要素mの値を判定する。

【0051】
【数11】
JP0005464341B2_000012t.gif

【0052】
より具体的には、上記判定式(11)は、下記のようになる。

【0053】
【数12】
JP0005464341B2_000013t.gif

【0054】
続いてステップS110では、平文出力部130は、一意に復元されたメッセージの平文Mを、例えば記憶装置30、ディスプレイ24等の出力装置に出力し、受信側コンピュータ装置10は、処理を終了させる。

【0055】
4.2つのナップザックを用いた公開鍵暗号方式による秘密通信
上述までは、N=3の場合の実施形態について説明してきた。公開鍵の鍵サイズと計算の高速性の両立の観点からは、N=3程度のものが好適であるが、N≧2であれば、特に限定されるものではない。他の実施形態では、N=2としても、本発明の実施形態による複数のナップザックを用いた公開鍵暗号方式に同様に適用することができる。N=2の場合、秘密鍵数列は、Q=(q,q,...,q)、Q=(q,q,...,q)となり、公開鍵数列は、O=(o,o,...,o)、O=(o,o,...,o)となる。またこの場合において、上記非線形関数fは、例えば、第1変数および第2変数の積による2変数2次式(X×Y)を採用することができる。

【0056】
かかる2つのナップザックを用いる公開鍵暗号方式では、上記非線形不等式(1)、上記式(2)、上記式(4)、上記式(5)および上記判定式(6)は、より具体的な形式では、それぞれ、下記非線形不等式(12)、下記式(13)、下記式(14)、下記式(15)および下記判定式(16)で表現される。

【0057】
【数13】
JP0005464341B2_000014t.gif

【0058】
5.計算例
以下、具体的な数列を用いた計算例を参照して説明する。以下の計算例では、N=3の場合について例示する。まず、秘密鍵生成部112は、上記式(7)を満たす条件のもと、秘密鍵数列Q=(1,2,3,6)と、Q=(2,1,3,7)と、Q=(1,2,4,3)とを選択する。これら秘密鍵数列は、単独では超増加性を必ずしも満たさないものである。公開鍵生成部114は、さらに秘密鍵として、法p=167(>12×13+10)と、乗数r=90と、乗数r=13とを定め、上記式(3’)に従って、公開鍵数列O=(90,13,103,39)と、O=(33,100,133,32)と、O=(149,131,95,113)とを算出する。

【0059】
ここで、平文をM=(0,1,0,1)とすると、暗号処理部160は、上記式(9)に従って、平文Mから暗号文C=(13+39)×(100+32)+(131+113)=7108を算出する。

【0060】
復号処理部120は、上記法p=167と、乗数r=90と、乗数r=13に対応して、乗数逆元r-1=13と、乗数逆元r-1=162とを算出し、上記式(10)に従って、D(C)≡13×162×7108(mod 167)≡69を算出する。さらに復号処理部120は、上記判定式(11)に従って、4番目の要素から1番目の要素まで大小判定を行う。この大小判定を通じて、q×q+q=6×7+3=45<D(C)より、m=1が判定され、(q+q)×(q+q)+(q+q)=(6+3)×(7+3)+(3+4)=97>D(C)より、m=0が判定され、(q+q)×(q+q)+(q+q)=(6+2)×(7+1)+(3+2)=69=D(C)より、m=1が判定され、(q+q+q)×(q+q+q)+(q+q+q)=(6+2+1)×(7+1+2)+(3+2+1)=96>D(C)より、m=0が判定される。これにより、平文(0,1,0,1)が復元される。

【0061】
6.複数のナップザックを用いた公開鍵暗号方式の安全性および処理速度の検討
上述までの複数のナップザックを用いる公開鍵暗号方式について、以下、安全性の検討を行う。総当たり攻撃に耐性を持たせるため、平文Mのビット数nを100以上に定めると、公開鍵数列それぞれの要素の数が100以上となるため、上記N=2の場合でも、要素を組み合わせた総数は少なくとも10000以上となる。LLLアルゴリズムを用いた攻撃について検討してみると、格子の次元が10000以上となるため、LLLアルゴリズムによる攻撃は、実質的に動作しないと考えられる。

【0062】
シャミア・アルゴリズムによる攻撃に対する耐性ついて検討する。上述したようにシャミアの攻撃法は、導入した秘密鍵の超増加性の特徴を利用するものである。本公開鍵暗号方式では、個々の秘密鍵数列が超増加性を有さないため、当該アルゴリズムにおける不等式は成り立たない。これは、シャミア・アルゴリズムは、線形不等式を扱うある種の線形計画法と見なすことができるが、複数の公開鍵の要素を組み合わせて得られる高次の超増加性を表現する非線形不等式を扱うことができないためである。よって、公開鍵にシャミア・アルゴリズムを適用しても復号可能な鍵を求めることが困難であり、シャミア・アルゴリズムによる攻撃にも耐性を示すと考えられる。

【0063】
より具体的に上述した3つのナップザックを用いた公開鍵暗号方式について検討してみると、仮にシャミア・アルゴリズムを適用して超増加性を有する数列の要素q×q+qが得られたとしても、解読するためには、少なくともq×qと、qとに分離する必要があるが、この和分解は通常困難である。よって、3つのナップザックの積と和による公開鍵暗号方式は、さらに、2つのナップザックの積による方式に比べて、シャミア・アルゴリズムによる攻撃に対する耐性がさらに高いものと考えられる。

【0064】
さらに本公開鍵暗号方式では、複数の公開鍵数列から1つの鍵数列を導出し得たとしても、解読には、N個の公開鍵数列からN個の秘密鍵数列に対応する鍵数列を求めることが必要であるため、復号が困難となるという利点もある。さらに、本公開鍵暗号方式では、通常のナップザック暗号方式に比べて鍵サイズが大きくなるが、ナップザック間の演算(例えば乗算)が追加される程度の計算量の増加で済み、高速な暗号化処理および復号処理が実現される。

【0065】
以上説明してきたように、本発明の実施形態によれば、解読法として代表的なLLLアルゴリズムを用いる攻撃およびシャミア攻撃法による攻撃に対して耐性を有し、高速な処理が可能な新奇なナップザック問題を安全性の根拠とするナップザック暗号方式による暗号システム、鍵生成を実行する鍵生成装置、暗号化処理を実行する暗号化装置、暗号文の復号処理を実行する復号装置、データ交換方法およびプログラムを提供することができる。

【0066】
なお、上述までの実施形態では、暗号システムの一例として、ネットワークを介して秘密通信を実行する複数のコンピュータ装置を含むセキュア通信システムを用いて説明してきたが、通信システムの他、認証、署名、情報記憶などの従来より暗号方式が適用可能ないかなるシステムに応用することができる。また、上述した実施形態では、鍵生成装置、暗号化装置、復号装置の例として、コンピュータ装置について説明してきたが、上述した複数のナップザックを用いる公開鍵暗号方式をハードウェアまたはソフトウェアとハードウェアとの協働により実装する如何なる装置として構成することができる。

【0067】
なお、本発明につき、発明の理解を容易にするために各機能部および各機能部の処理を記述したが、本発明は、上述した特定の機能部が特定の処理を実行する外、処理効率や実装上のプログラミングなどの効率を考慮して、いかなる機能部に、上述した処理を実行するための機能を割当てることができる。

【0068】
本発明の上記機能は、C++、Fortran、Pascal、Java(登録商標)、Java(登録商標)Beans、Java(登録商標)Applet、Java(登録商標)Script、Perl、Rubyなどのオブジェクト指向プログラミング言語などで記述された装置実行可能なプログラムにより実現でき、装置可読な記録媒体に格納して頒布または伝送して頒布することができる。

【0069】
これまで本発明を、特定の実施形態をもって説明してきたが、本発明は、実施形態に限定されるものではなく、他の実施形態、追加、変更、削除など、当業者が想到することができる範囲内で変更することができ、いずれの態様においても本発明の作用・効果を奏する限り、本発明の範囲に含まれるものである。
【符号の説明】
【0070】
10…コンピュータ装置、12…CPU、14…キャッシュ・メモリ、16…システム・メモリ、18…システム・バス、20…グラフィックス・ドライバ、22…NIC、24…ディスプレイ、26…I/Oバス・ブリッジ、28…I/Oバス、30…記憶装置、32…入力装置、50…コンピュータ装置、110…鍵生成処理部、112…秘密鍵生成部、114…公開鍵生成部、120…復号処理部、130…平文出力部、150…平文入力部、160…暗号化処理部
図面
【図1】
0
【図2】
1
【図3】
2
【図4】
3