【課題】ナップザック暗号は暗号化および復号が短時間であり量子計算機によってさらに安全性が危うくなることはない利点があるが、解読法が存在する。
【解決手段】
秘密鍵生成部１０は、要素が単調増加に並び、任意の要素の値がその値よりも小さな要素それぞれに所定の自然数を乗じて和を取った値よりも大きな値となるベクトルを生成する低密度秘密鍵ベクトル生成部３８と、ベクトルの全ての要素に所定の自然数を乗じて和を取った値よりも大きな自然数を生成する法Ｍ生成部４０と、法Ｍと互いに素である自然数を生成する乗数生成部４２とを含む。公開鍵生成部１２は、低密度秘密鍵ベクトルの要素と乗数との積について法Ｍを法としてモジュラ乗算変換して公開鍵ベクトルを生成する公開鍵ベクトル生成部４４と、低密度秘密鍵ベクトルの要素と同数の自然数を要素とするベクトルを生成する暗号化乗数生成部４６とを含む。 （もっと読む）

【課題】 暗号文Ｃをモジュラー乗算し、中間平文Ｉとする。中間平文Ｉに対し法ｂiに対する剰余Ｔを求めて、ｂi以下のビット数を一括して復号する。中間平文ＩからＴを引き、法ｂiで除算して、次の法に対する剰余を求める。
【解決手段】 ナップザック暗号の新たなトラップドアを提供できる。 （もっと読む）

【課題】ナップザック暗号には低密度攻撃が知られており、密度によって解読が可能なことが知られている。したがって、ナップザック暗号の安全性をさらに高めることが課題である。また、公開鍵からの秘密鍵の露呈を防止することにある。
【解決手段】入力された暗号文をモジュラ変換し、互いに素な法Ｌ１，Ｌ２での剰余を求め、各剰余をナップザック暗号の中間平文と見なして部分鍵を用いて部分的に復号し、復号結果を連接し、逆プリコーディングする。中間平文を部分鍵で各々部分的に復号するので、部分鍵やそれに同等な鍵が露呈する可能性をさらに小さくできる。 （もっと読む）

【課題】合成数Ｎを法とした離散対数x≡g^a(mod N)においてx∈<g>となる整数ｘを効率的に特定する。
【解決手段】素数冪生成部１１１が、全てのｖ，ｗ（１≦ｖ＜ｗ≦ｓ）に対してgcd(φ(q_v),φ(q_w))=2となる素数冪ｑ_ｊ（ｊ＝１，...，ｓ）を生成し、生成元生成部１１２が、全てのｊについて、g mod q_jが、素数冪ｑ_ｊと互いに素な０以上ｑ_ｊ未満の整数集合〔Ｚ_ｑｊ^×（下付添え字のｑｊはｑ_ｊを示す）〕の生成元となる当該整数ｇを生成する。そして、合成数生成部１１３が、素数冪生成部１１１で生成された全ての素数冪ｑ_ｊの積である合成数Ｎ〔N=Π_j=1^sq_j〕を算出する。 （もっと読む）

【課題】既存の計算機でも比較的容易に利用可能でありながら、量子計算機が実現しても解読できないナップザック問題を安全性の拠り所とした公開鍵暗号を提供する。
【解決手段】素数冪の積である合成数Ｎを法とした既約剰余類群（Ｚ／ＮＺ）^×の部分巡回群において乗法型ナップザック暗号を構成する。あるいは、代数体Ｋの整数環Ｚ_Ｋにおける複数の素イデアルの積νを法とした既約剰余類群（Ｚ_Ｋ／ν）^×の巡回部分群において乗法型ナップザック暗号を構成する。 （もっと読む）

【課題】 ナップザック暗号の安全性を高める。
【解決手段】 秘密鍵ベクトルｖの一部をノイズ成分とし、Ｇをｕ行ｎ列(ｎ＞ｕ)の行列とし、Ｇ''^−１をｕ行ｕ列の行列とする。ｕ次元の平文ｍを行列Ｇによりｎ次元に拡大し、公開鍵ベクトルａとの積和演算により暗号文Ｃとする。暗号文Ｃを中間平文Ｍに復号し、秘密鍵ベクトルｖの一部のｕ個の成分により復号し、行列Ｇ''^−１と乗算して平文ｍへ復号する。 （もっと読む）

【構成】 秘密の数Ｐ,ｗと２つの秘密鍵ベクトルｖ^０,ｖ^１を用いたナップザック暗号の公開鍵として、秘密のベクトルｔを用い、
ａ_ｉ＝ｗｖ^ｔｉ_ｉ modＰ
ｂ_ｉ＝ｗｖ^１−ｔｉ_ｉ modＰ
により公開鍵ベクトルａ,ｂを得る。なおｖ^０は正整数の乱数ベクトル、ｖ^１は超増加ベクトルとする。
【効果】 ナップザック暗号の密度を増して低密度攻撃への耐性を向上させ、秘密鍵ベクトルの超増加性等を利用した攻撃も困難にできる。 （もっと読む）

【構成】 平文を符号語に変換し，ベクトルＶの全成分の和Ｓよりも小さな法Ｐを用いて，ナップザック暗号に変換し送信する．復号側では，中間平文の候補に変換し，この候補に中間平文の欠損部を推定して復号し，符号語が得られると復号に成功したものとし，符号語が得られないと欠損部の推定値を変更して，再度復号する．
【効果】 ナップザック暗号の強度を増すことができる． （もっと読む）