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

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

国内特許コード P100000641
整理番号 中央大139
掲載日 2010年4月16日
出願番号 特願2009-285093
公開番号 特開2011-128281
登録番号 特許第5464341号
出願日 平成21年12月16日(2009.12.16)
公開日 平成23年6月30日(2011.6.30)
登録日 平成26年1月31日(2014.1.31)
発明者
  • 辻井 重男
  • 小林 邦勝
  • 笠原 正雄
出願人
  • 学校法人 中央大学
発明の名称 複数のナップザックを用いる公開鍵暗号方式による暗号システム、鍵生成装置、暗号化装置、復号装置、データ交換方法およびプログラム
発明の概要 【課題】 高い安全性および処理の高速性を実現するナップザック暗号方式を提供すること。
【解決手段】 本発明の暗号システムは、個々は超増加性を示さない複数の秘密鍵数列を、数列それぞれの要素を変数として非線形関数により組み合わせると超増加性を満たすという条件のもと、生成する秘密鍵生成手段と、法と、法と互いに素な複数の乗数とをさらに秘密鍵として定めて、複数の秘密鍵数列それぞれの要素をモジュラ変換し、複数の公開鍵数列を生成する公開鍵生成手段とを含む鍵生成装置と、複数の公開鍵数列それぞれと平文との内積を求めて複数のナップザックを計算し、計算した複数のナップザックを非線形関数に対応して演算し、暗号文を生成する暗号化手段を含む暗号化装置と、法による乗数の乗法逆元と、法とを用いて、受信した暗号文を逆モジュラ変換し、複数の秘密鍵数列を用いて暗号文から平文を一意に復号する復号手段を含む復号装置を含む。
【選択図】 図2
従来技術、競合技術の概要



近年の情報通信技術の発達およびネットワークのブロードバンド化に伴い、暗号理論に基づく暗号化技術は、ネットワーク上を伝送するデータの機密性および完全性を保証する技術として、ますます重要な技術となっている。





このような暗号理論による暗号化方式は、素因数分解問題、離散対数問題、ラティス問題、ナップザック問題などの数学上の問題を安全性の根拠としている。ナップザック問題は、NP完全問題のひとつであり、この一般のナップザック問題に超増加性等の落とし戸を導入して暗号理論に応用したものがナップザック暗号方式である。この超増加性を導入したナップザック暗号方式は、暗号文から平文を一意に復号することができる一方、解読が容易となってしまう。そのため、Markle-Hellmanナップザック暗号(非特許文献1)やChor-Rivestナップザック暗号といった、これまでに提案されている多くのナップザック暗号方式は、LLLアルゴリズム(格子基底縮小アルゴリズム)を用いた攻撃(非特許文献2)や、シャミア攻撃法(非特許文献3)等の解読法による攻撃に対して脆弱性を有し、安全性の問題等から実用されるに至っていない。

産業上の利用分野



本発明は、ナップザック問題を安全性の根拠とした公開鍵暗号方式に関し、より詳細には、高い安全性および処理の高速性を実現するナップザック暗号方式による、鍵生成を実行する鍵生成装置と、暗号化処理を実行する暗号化装置と、暗号文の復号処理を実行する復号装置とを含む暗号システム、該鍵生成装置、該暗号化装置、該復号装置、データ交換方法およびプログラムに関する。

特許請求の範囲 【請求項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】


を満たすという条件である、請求項1に記載の暗号システム。

【請求項3】
前記法pは、下記式(2)
【数2】


を満たすように選択され、前記複数の公開鍵数列を生成するための前記モジュラ変換は、前記複数の公開鍵数列をO(j=1,...,N)とし、前記公開鍵数列Oそれぞれのn個あるうちのi番目の要素をoとし、前記複数の乗数をr(j=1,...,N)として、下記式(3)
【数3】


で表される、請求項2に記載の暗号システム。

【請求項4】
前記平文Mのn個あるうちのi番目の要素をm(∈{0,1})とし、前記ナップザックをCとして、前記暗号文Cは、下記式(4)
【数4】


で演算される、請求項3に記載の暗号システム。

【請求項5】
前記復号手段は、前記法pによる前記乗数rの前記乗法逆元r-1と、前記法pとを用いて、受信した暗号文Cを逆モジュラ変換し、下記式(5)
【数5】


にて表される剰余D(C)を算出し、下記判定式(6)
【数6】


に従って、平文Mの要素mを判定する、請求項4に記載の暗号システム。

【請求項6】
N=3であり、前記乗数rはr×rと等しく、前記非線形関数fは、2変数の積と変数との和であり、前記不等式(1)、前記式(2)、前記式(4)、前記式(5)および前記判定式(6)は、下記不等式(7)、下記式(8)、下記式(9)、下記式(10)および下記判定式(11)
【数7】


で表される、請求項5に記載の暗号システム。

【請求項7】
N=2であり、前記非線形関数fは、2変数の積であり、前記不等式(1)、前記式(2)、前記式(4)、前記式(5)および前記判定式(6)は、下記不等式(12)、下記式(13)、下記式(14)、下記式(15)および下記判定式(16)
【数8】


で表される、請求項5に記載の暗号システム。

【請求項8】
ナップザック問題を安全性の根拠とした公開鍵暗号方式による鍵生成を実行する鍵生成装置であって、前記鍵生成装置は、
個々は超増加性を示さない複数の秘密鍵数列を、前記複数の秘密鍵数列それぞれの要素を変数として非線形関数により組み合わせると超増加性を満たすという条件のもと、生成する秘密鍵生成手段と、
法と、前記法と互いに素な複数の乗数とをさらに秘密鍵として定めて、前記複数の秘密鍵数列それぞれの要素をモジュラ変換し、複数の公開鍵数列を生成する公開鍵生成手段とを含む、鍵生成装置。

【請求項9】
ナップザック問題を安全性の根拠とした公開鍵暗号方式による複数の公開鍵数列を使用した暗号化処理を実行する暗号化装置であって、前記暗号化装置は、
前記複数の公開鍵数列それぞれと平文との内積を求めて複数のナップザックを計算し、秘密鍵生成に用いた非線形関数に対応して前記複数のナップザックを演算し、暗号文を生成する暗号化手段を含み、前記複数の公開鍵数列は、
個々は超増加性を示さない複数の秘密鍵数列であって、それぞれの要素を変数とした前記非線形関数により組み合わせると超増加性示すという条件のもと生成された当該複数の秘密鍵数列から、法と前記法と互いに素な複数の乗数とをさらに秘密鍵として用いて、前記複数の秘密鍵数列それぞれの要素をモジュラ変換して生成されたものである、暗号化装置。

【請求項10】
ナップザック問題を安全性の根拠とした公開鍵暗号方式による復号処理を実行する復号装置であって、前記復号装置は、
個々は超増加性を示さない複数の秘密鍵数列であって、それぞれの要素を変数として非線形関数により組み合わせると超増加性示す条件のもと生成される当該複数の秘密鍵数列と、前記秘密鍵数列から複数の公開鍵数列を生成する際に用いられた秘密鍵としての法および前記法と互いに素な複数の乗数とを用いて、前記法による前記乗数の乗法逆元を算出し、受信した暗号文を逆モジュラ変換し、前記複数の秘密鍵数列を用いて前記暗号文から平文を一意に復号する復号手段を含む、復号装置。

【請求項11】
ナップザック問題を安全性の根拠とした公開鍵暗号方式によるデータ交換方法であって、前記方法は、
個々は超増加性を示さない複数の秘密鍵数列を、前記複数の秘密鍵数列それぞれの要素を変数として非線形関数により組み合わせると超増加性を満たすという条件のもと生成するステップと、
法と、前記法と互いに素な複数の乗数とをさらに秘密鍵として定めて、前記複数の秘密鍵数列それぞれの要素をモジュラ変換し、複数の公開鍵数列を生成するステップと、
前記複数の秘密鍵数列と、前記法と、前記複数の乗数とをデータ受取側の装置で保持するとともに、前記複数の公開鍵数列をデータ受渡側の装置で保持するステップと、
前記データ受渡側の装置が、前記複数の公開鍵数列それぞれと平文との内積を求めて複数のナップザックを計算し、計算した前記複数のナップザックを前記非線形関数に対応して演算し、暗号文を生成するステップと、
前記データ受取側の装置が、前記法による前記乗数の乗法逆元と、前記法とを用いて、受信した暗号文を逆モジュラ変換し、前記複数の秘密鍵数列を用いて前記暗号文から平文を一意に復号するステップと
を含む、データ交換方法。

【請求項12】
コンピュータを、請求項8に記載の各手段として機能させるための装置実行可能なプログラム。

【請求項13】
コンピュータを、請求項9に記載の各手段として機能させるための装置実行可能なプログラム。

【請求項14】
コンピュータを、請求項10に記載の各手段として機能させるための装置実行可能なプログラム。
国際特許分類(IPC)
Fターム
画像

※ 画像をクリックすると拡大します。

JP2009285093thum.jpg
出願権利状態 登録
参考情報 (研究プロジェクト等) 中央大学 研究開発機構 「量子コンピュータの出現に対抗し得る公開鍵暗号の研究」
ライセンスをご希望の方、特許の内容に興味を持たれた方は、下記までご連絡ください


PAGE TOP

close
close
close
close
close
close
close