(57)【特許請求の範囲】
【請求項１】
鍵生成処理装置と、暗号化処理装置と、復号処理装置とよりなり、
鍵生成処理装置に整数ｎ，ｋ（ｋ＜ｎ）とｓ（ｓは１以上）が入力して、
素数ｐ、互いに素である整数ｐ１  ，…，ｐｎ  、生成元ｇを生成し、
各々の１＜ｉ＜ｎに対してｐｉ  ≡ｇａｉ（ｍｏｄ  ｐ）を満たすようなａ１  ，…，ａｎ  を求め、
整数ｃ１  ，ｃ２  ，…，ｃｓ  ，ｄ１  ，ｄ２  ，…，ｄｓ  ，ｑ１  ，ｑ２  ，…，ｑｓを生成し、
各々の１＜ｉ＜ｎに対して、
ｂｉ，１  ＝（ｃ１  ａｉ  ＋ｄ１  ）ｍｏｄ  ｑ１  を求め、さらにｊ＝２，３，４，…，ｓと順にｂｉ，ｊ  ＝（ｃｊ  ｂｉ，ｊ−１  ＋ｄｊ  ）ｍｏｄ  ｑｊ    を求め、
ｐ，ｇ，ｐ１  ，…，ｐｎ  ，ｃ１  ，…，ｃｓ  ，ｄ１  ，…，ｄｓ  ，ｑ１  ，…，ｑｓ  を秘密鍵として秘密に保持し、ｂ１，ｓ  ，…，ｂｎ，ｓ  を公開鍵として公開し、かつｎ，ｋを公開し、
暗号化処理装置に長さ［ｌｏｇ２（  ｎＣｋ  ）］の平文Ｍと、公開鍵ｂ１，ｓ  ，…，ｂｎ，ｓとｋを入力して（ただし［＊］は＊を超えない最大整数）、
平文Ｍを、長さｎでハミング重さがｋの二進列ｍ＝（ｍ１  ，ｍ２  ，…，ｍｎ  ）に変換し、
暗号文ｃ＝Σｉ＝１ｎｍｉ  ｂｉ，ｓを生成して出力し、
復号処理装置に暗号文ｃ、上記秘密鍵を入力して、
ｒｓ  ＝（ｃ−ｋｄｓ  ）／ｃｓ  ｍｏｄ  ｑｓ  を生成し、
ｊ＝ｓ−１，ｓ−２，ｓ−３，…，１と順にｒｊ    ＝（ｒｊ＋１  −ｋｄｊ  ）／ｃｊ  ｍｏｄ  ｑｊ  を生成し、
ｕ＝ｇｒ１ｍｏｄ  ｐ求め、
ｐｉ  がｕの因数ならばｍｉ  ＝１とし、因数でないならばｍｉ  ＝０として、長さｎでハミング重さｋの二進列ｍ＝（ｍ１  ，ｍ２  ，…，ｍｎ  ）を生成し、
その二進列ｍを平文Ｍに変換して出力する
ことを特徴とするナップサック型公開鍵暗号化復号システム。
【請求項２】
整数ｎ，ｋが入力され、素数ｐと、互いに素である数ｐ１  ，…，ｐｎ  ∈Ｚ／ｐＺ（ｐを法とする整数の体）と、生成元ｇを発生出力する第１乱数発生器と、
上記ｐ，ｐ１  ，…，ｐｎ  ，ｇ  が入力され、０＜ｉ＜ｎに対してｐｉ  ＝ｇａｉ（ｍｏｄ  ｐ）を満たすａ１  ，…，ａｎ  を生成出力する離散対数計算器と、
整数ｓが入力されて、乱数群ｃ１  ，…，ｃｓ  ，ｄ１  ，…，ｄｓ  ，ｑ１  ，…，ｑｓ  を生成出力する第２乱数発生器と、
上記ａ１  ，…，ａｎ  、上記ｃ１  ，…，ｃｓ  ，ｄ１  ，…，ｄｓ  ，ｑ１  ，…，ｑｓ  が入力され、
ｂｉ，１  ＝（ｃ１  ａｉ  ＋ｄ１  ）ｍｏｄ  ｑ１  
ｂｉ，ｊ  ＝（ｃｊ  ｂｉ，ｊ−１  ＋ｄｊ  ）ｍｏｄ  ｑｊ
（ｊ  ＝２からｓまで）
を演算してｂ１，ｓ  ，…，ｂｎ，ｓ  を出力する剰余乗算・加算器と
を備え、秘密鍵として上記ｐ，ｇ，ｐ１  ，…，ｐｎ  ，ｃ１  ，…，ｃｓ  ，ｄ１  ，…，ｄｓ  ，ｑ１  ，…，ｑｓ  を生成し、公開鍵として上記ｂ１，ｓ  ，…，ｂｎ，ｓ  を生成するナップサック型公開鍵暗号用鍵生成処理装置。
【請求項３】
請求項２記載の鍵生成装置により生成された公開鍵ｂ１，ｓ  ，…，ｂｎ，ｓ  を記憶する記憶部と、
整数ｎ，ｋと平文Ｍが入力され、長さ［ｌｏｇ２（  ｎＣｋ  ）］の平文を、長さＭでハミング重みがｋの二進列ｍ＝（ｍ１  ，…，ｍｎ  ）に変換して出力する平文変換器と（［＊］は＊を超えない最大整数を表わす）、
上記二進列ｍと、上記公開鍵ｂ１，ｓ  ，…，ｂｎ，ｓ  が入力され、ｃ＝Σｉ＝１ｎｍｉ  ｂｉ，ｓ  を演算して暗号文ｃを生成出力する加算器とを備えるナップサック型公開鍵暗号化処理装置。
【請求項４】
公開情報ｎ，ｋ、秘密鍵ｐ，ｇ，ｐ１  ，…，ｐｎ  ，ｃ１  ，…，ｃｓ  ，ｄ１  ，…，ｄｓ  ，ｑ１  ，…，ｑｓ  を格納した記憶部と、
暗号文ｃと、上記ｋ，ｃ１  ，…，ｃｓ  ，ｄ１  ，…，ｄｓ  ，ｑ１  ，…，ｑｓ  が入力され、
ｒｓ  ＝（ｃ−ｋｄｓ  ）／ｃｓ  ｍｏｄ  ｑｓ  
ｒｊ  ＝（ｒｉ＋１  −ｋｄｊ  ）／ｃｊ  ｍｏｄ  ｑｊ  
（ｊ＝ｓ−１から１まで）
を演算してｒ１  を出力する剰余乗算・減算・割算器と、
上記演算結果ｒ１  と上記ｐ，ｇが入力され、
ｕ＝ｇｒ１  ｍｏｄｐ
を演算してｕを出力する冪乗演算器と、
その演算結果ｕと上記ｐ１  ，…，ｐｎ  が入力されて、各ｐｉ  （ｉ＝１，…，ｎ）についてｐｉ  がｕの因数であればｍｉ  ＝１、因数でなければｎｉ  ＝０として中間復号文ｍ＝（ｍ１  ，…，ｍｎ  ）を出力する因数検査器と、
上記ｍと上記ｎ，ｋが入力されて平文Ｍを出力する中間復号文変換器と、
を具備するナップサック型公開鍵暗号の復号処理装置。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
この発明は長さが［ｌｏｇ２（  ｎＣｋ  ）］（［＊］は＊を超えない最大整数）、  ｎＣｋ  はｎ個からｋ個とった組合せの総数）ビットの平文を長さがｎでハミング（Ｈａｍｍｉｎｇ）重みがｋの二進列に変換して暗号化するナップサック型公開鍵暗号システム及びその装置に関する。
【０００２】
【従来の技術】
公開鍵暗号システムは、その安全性のよりどころとする問題により類別される。このような、よりどころとなる問題としては、素因数分解問題、離散対数問題、ナップサック問題などが挙げられる。これらの問題のうち、ナップサック問題を安全性のよりどころとする公開鍵暗号システムとしては、Ｍａｒｋｌｅ−Ｈｅｌｌｍａｎ暗号やＣｈｏｒ−Ｒｉｖｅｓｔ  暗号などがあるが、そのいずれについても攻撃が成功した例が報告されている。Ｃｈｏｒ−Ｒｉｖｅｓｔ  暗号は例えば米国雑誌ＩＥＥＥ  ＴＲＡＮＳ．ＯＮ  ＩＮＦＯＲＭＡＴＩＯＮ  ＴＨＥＯＲＹ，ＶＯＬ．３４，ＮＯ．５，ＳＥＰ．，１９８８，ｐｐ．９０１  〜９０９  （文献１と呼ぶ）に示されている。
【０００３】
【発明が解決しようとする課題】
この発明は、ナップサック問題を安全性のよりどころとし、従来よりも安全性の高い公開鍵暗号システム及びその装置を提供することを目的とする。
【０００４】
【課題を解決するための手段】
この発明によれば、整数ｎとｋ（ｎ＞ｋ）を決め、素数ｐと、互いに素である整数ｐ１  ，…，ｐｎ  と生成元ｇを生成し、１＜ｉ＜ｎの各ｉについてｐｉ  ≡ｇａｉ（ｍｏｄ  ｐ）を満たすａ１  ，…，ａｎ  を求め、更に整数ｓを決め、整数ｃ１  ，…，ｃｓ  ，ｄ１  ，…，ｄｓ  ，ｑ１  ，…，ｑｓ  を生成し、１＜ｉ＜ｎの各ｉについてｂｉ，１  ＝（ｃ１  ａｉ  ＋ｄ１  ）ｍｏｄ  ｇ１  を求め、更にｊ＝２，３，４，…，ｓと順ｊを＋１させ、その各ｊについてｂｉ，ｊ  ＝（ｃｊ  ｂｉ，ｊ−１  ＋ｄｊ  ）ｍｏｄ  ｑｊ  を求め、ｐ，ｇ，ｐ１  ，…，ｐｎ  ，ｃ１  ，…，ｃｓ  ，ｄ１  ，…，ｄｓ  ，ｑ１  ，…，ｑｓ  を秘密鍵として秘密に保持し、ｂ１，ｓ  ，…，ｂｎ，ｓ  を公開鍵として公開すると共にｎ，ｋを公開し、
暗号化処理の際には、長さ［ｌｏｇ２（  ｎＣｋ  ）］（［＊］は＊を超えない最大整数）ビットの平文Ｍを、長さｎでハミング重みがｋの二進列ｍ＝（ｍ１  ，ｍ２  ，…，ｍｎ  ）に変換し、これに対し公開鍵を用いてｃ＝Σｉ＝１ｎｍｉ  ｂｉ，ｓを生成して、暗号文ｃを出力し、
復号処理の際には、暗号文ｃと秘密鍵とからｒｓ  ＝（ｃ−ｋｄｓ  ）／ｃｓ  ｍｏｄ  ｑｓ  を生成し、ｊ＝ｓ−１，ｓ−２，ｓ−３，…，１と順次−１した各ｊについてｒｊ  ＝（ｒｊ＋１  −ｋｄｊ  ）／ｃｊ  ｍｏｄ  ｑｊ  を生成し、その最後のｒ１  を用いてｕ＝ｇｒ１ｍｏｄ  ｐを求め、１＜ｔ＜ｎの各ｐｉ  についてｐｉ  がｕの因数であればｎｉ  ＝１とし因数でなければｍｉ  ＝０として、長さｎ、ハミング重さｋの二進列を生成し、この二進列を平文Ｍに変換する。
【０００５】
【発明の実施の形態】
この発明の実施例を以下に説明する。
（鍵生成処理：図１）
図１にこの発明の鍵生成処理装置の実施例を示す。この装置は整数ｎとｋとｓが入力されて、鍵生成処理を行う。ｎは大きな値である程、暗号の安全性が大となるが、例えば１０００程度とされ、ｋはｎより小さい整数であり、一般にｌｏｇ  ｎの整数倍であるが、例えば２００程度とされ、ｓは１以上の整数であり、この値も大きい程、安全性が高くなるが、例えば１０程度とされる。
【０００６】
このｎとｋが乱数発生器１０１に入力され、乱数発生器１０１は｛ｐ１  ，ｐ２  ，…，ｐｎ  ｝からの任意の部分集合｛ｐｉ１，ｐｉ２，…，ｐｉｋ｝がΠｊ＝１ｋｐｉｊ＜ｐを満たすような素数ｐと、互いに素である数ｐ１  ，…，ｐｎ  ∈Ｚ／ｐＺ、および、群（Ｚ／ｐＺ）ｘ  の生成元ｇを発生させる。ここでＺ／ｐＺは素数ｐを法とする整数の体、つまり０，１，２，…，ｐ−１の群であり、（Ｚ／ｐＺ）ｘ  は０を含まない素数ｐを法とする整数の体である。つまりｇは群（Ｚ／ｐＺ）ｘ  の１要素である。
【０００７】
次に、離散対数計算器１０２を用いて、１＜ｉ＜ｎの各ｉに対してｐｉ  ≡ｇａｉ（ｍｏｄ  ｐ）を満たすようなａ１  ，…，ａｎ  を求める。さらに、乱数発生器１０３に整数ｓが入力され、乱数発生器１０３から整数ｃ１  ，ｃ２  ，…，ｃｓ  ，ｄ１  ，ｄ２  ，…，ｄｓ  ，ｑ１  ，ｑ２  ，…，ｑｓを発生させる。
最後に、剰余乗算・加算器１０４を用いて、１＜ｉ＜ｎの各ｉに対して、ｂｉ，１  ＝（ｃ１  ａｉ  ＋ｄ１  ）ｍｏｄ  ｑ１  を求め、さらにｊ＝２，３，４，…，ｓの順に各ｊについてｂｉ，ｊ  ＝（ｃｊ  ｂｉ，ｊ−１  ＋ｄｊ  ）ｍｏｄ  ｑｊ  を求め、最終的にｂ１，ｓ  ，ｂ２，ｓ  ，…，ｂｎ，ｓを得る。このｂ１，ｓ  ，…，ｂｎ，ｓ  を公開鍵として公開し、またｎ，ｋを公開情報として公開し、ｐ，ｇ，ｐ１  ，…，ｐｎ  ，ｃ１  ，…，ｃｓ  ，ｄ１  ，…，ｄｓ  ，ｑ１  ，…，ｑｓ  を秘密鍵として秘密に保持させる。
（暗号化処理：図２）
図２に暗号化処理装置の実施例を示す。記憶部２００には図１に示した鍵生成処理装置で生成され、公開された公開鍵ｂ１，ｓ  ，…，ｂｎ，ｓ  と公開情報ｎ，ｋが記憶されている。入力される平文は、長さ［ｌｏｇ２（  ｎＣｋ  ）］ビット（［＊］は＊を超えない最大整数、  ｎＣｋ  はｎ個からｋ個を取出す組合せの総数）ごとの平文Ｍに分割され、この平文Ｍは平文変換器２０１を用いて、長さｎでＨａｍｍｉｎｇ（ハミング）重さｋである二進列ｍ＝（ｍ１  ，ｍ２  ，…，ｍｎ  ）に変換される。つまり二進列ｍ中の“１”の数はｋであり、その他は“０”である。この二進列変換の手法は例えば前記文献１中に記載されてある。ｎは［ｌｏｇ２（  ｎＣｋ  ）］より大である。平文を長さ［ｌｏｇ２（  ｎＣｋ  ）］ごとに分割し、最後が［ｌｏｇ２（  ｎＣｋ  ）］よりも短くなった場合は例えば０を埋めて［ｌｏｇ２（  ｎＣｋ  ）］の長さにする。
【０００８】
この二進列ｍと公開鍵とが加算器２０２に入力されて、その対応ｉ番目のものとの乗算値が加算され、つまり、ｍ中のｍｉ  ＝１と対応するｂｉ，ｓ  が加算されて、暗号文ｃ＝Σｉ＝１ｎｍｉ  ｂｉ，ｓ  を生成して出力する。
（復号処理：図３）
図３にこの発明の復号処理装置の実施例を示す。記憶部３００には図１で述べた鍵生成処理装置で生成した秘密鍵ｐ，ｇ，ｐ１  ，…，ｐｎ  ，ｃ１  ，…，ｃｓ  ，ｄ１  ，…，ｄｓ  ，ｑ１  ，…，ｑｓ  と公開情報ｎ，ｋが格納されてある。これは、この復号処理装置に図１に示した鍵生成処理装置１００が設けられ、この装置１００で生成された秘密鍵が記憶部３００に秘密に記憶され、または他の所で生成された秘密鍵を秘密に記憶部３００に格納してもよい。
【０００９】
まず剰余乗算・減算・割算器３０１に暗号文ｃと、秘密鍵ｃ１  ，…，ｃｓ  ，ｄ１  ，…，ｄｓ  ，ｑ１  ，…，ｑｓ  が入力され、ｒｓ  ＝（ｃ−ｋｄｓ  ）／ｃ１  ｍｏｄｑｓが演算され、さらに、ｊ＝ｓ−１，ｓ−２，ｓ−３，…，１の順に各ｊについてｒｊ  ＝（ｒｉ＋１  −ｋｄｊ  ）／ｃｊ  ｍｏｄ  ｑｊ  が演算され、最終的にｒ１  が発生される。次に、冪乗演算器３０２としてのｒ１  と秘密鍵ｐ，ｇが入力されてｕ＝ｇｒ１ｍｏｄ  ｐが演算される。このｕと秘密鍵ｐ１  ，…，ｐｎ  が因数検査器３０３に入力され、長さｎでＨａｍｍｉｎｇ  重さｋである二進列ｍ＝（ｍ１  ，ｍ２  ，…，ｍｎ  ）を１＜ｉ＜ｎの各ｐｉ  についてｐｉ  がｕの因数ならばｍｉ  ＝１とし、因数でないならばｍｉ  ＝０として求める。最後に、中間復号文変換器３０４を用いて、ｍを平文Ｍに変換する。
【００１０】
以上のようにして復号できることを、以下に簡単に説明する。簡単のためｓ＝１の場合についてみると、公開鍵はｂ１，１  ＝（ｃ１  ａ１  ＋ｄ１  ）ｍｏｄ  ｑ１  ，ｂ２，１  ＝（ｃ１  ａ２  ＋ｄ１  ）ｍｏｄ  ｑ１  ，…，ｂｎ，１  ＝（ｃ１  ａｎ  ＋ｄ１  ）ｍｏｄ  ｑ１  であり、これらのうち、ｍｉ  ＝１と対応する公開鍵が加算された値が暗号文ｃとなる。二進列ｍ中の１の数はｋであるから、暗号文ｃ中にはｋｄ１  が存在する。ｓ＝１であるから剰余乗算・減算・割算器３０１の演算はｒｉ  ＝（ｃ−ｋｄ１  ）／ｃ１  ｍｏｄ  ｑ１  となり、（ｃ−ｋｄ１  ）により暗号文Σｉ＝１ｎ（ｃ１  ａｉ  ＋ｄ１  ）中のｋｄ１  が除去され、Σｉ＝１ｎｃ１  ａｉ  これがｃ１  で割算され、ｒｉ  ＝Σｉ＝１ｎａｉ  、つまりｍｉ  ＝１と対応するａｉ  の加算値となる。
【００１１】
従ってｕ＝ｇｒ１ｍｏｄ  ｐの演算は、仮りにｋ個のｍｉ  ＝１と対応するａｉ  をａ１，１  ，ａ１，２  ，…，ａ１，ｋ  とすればｒ１  ＝ａ１，１  ＋ａ１，２  ＋…＋ａ１，ｋ  となりｕ＝ｇｒ１＝ｇ（ａ１，１＋ａ１，２＋・・・＋ａ１，ｋ）＝ｇａ１，１−ｇａ１，２−…−ｇａ１，ｋとなる。
因数検査器３０３でｐｉ  ＝ｇａｉであり、ｍｉ  ＝１のａｉ  はａ１，１  ，ａ１，２  ，…，ａ１，ｋ  であるから、これらと対応するｐｉ  はｐ１，１  ＝ｇａ１，１，ｐ１，２  ＝ｇａ１，２，…，ｐ１，ｋ  ＝ｇａ１，ｋであり、これらのｐｉ  でｕ＝ｇｒ１を割算すればｐ１  ，…，ｐｎ  が互いに素であるから、ｕは必ず割り切れ、つまりｐｉ  がｕの因数となり、このことはそのｐｉ  はｍｉ  ＝１に相当することを意味し、割り切れなければ、つまりｕの因数でなければｍｉ  ＝０とする。このようにして、暗号文ｃが正しいものであれば、二進列ｍが復号される。
【００１２】
この二進列ｍから平文Ｍへの変換は、例えば文献１に示す手法によればよい。なおｓを２以上と大きくすればする程、公開鍵を複雑にかき混ぜたことになり、安全性が高くなる。このかき混ぜ方と先に述べたように復号時に、順次逆に解きほぐすことにより、ｒ１  を得ることができる。
【００１３】
【発明の効果】
以上述べたようにこの発明によれば、鍵生成処理においてｐｉ  ≡ｇａｉ（ｍｏｄ  ｐ）を演算し、そのａｉ  を公開鍵の要素としており、つまり、有理整数環上の離散対数問題を利用しており、しかもｐ，ｇ，ｐ１  ，…，ｐｎ  ，ｇ，ｃ１  ，ｃ２  ，…，ｃｓ  ，ｄ１  ，ｄ２  ，…，ｄｓ  ，ｑ１  ，ｑ２  ，…，ｑｓ  を秘密にすることにより、公開鍵から秘密鍵を直接求める攻撃に耐えうる。また、暗号化処理と復号処理において、長さ［ｌｏｇ２（  ｎＣｋ  ）］の整数と長さｎでＨａｍｍｉｎｇ  重さｋである二進列との変換を利用することにより、ナップサック暗号の安全性の指標であるｄｅｎｓｉｔｙ（重度）を十分高めることができ、したがって、平文から暗号文を直接求めるｌｏｗ−ｄｅｎｓｉｔｙ攻撃にも耐えうる。
【図面の簡単な説明】
【図１】この発明による鍵生成処理装置の実施例を示すブロック図。
【図２】この発明による暗号化処理装置の実施例を示すブロック図。
【図３】この発明による復号処理装置の実施例を示すブロック図。
【図１】
0003615137.tif 000002
【図２】
0003615137.tif 000003
【図３】
0003615137.tif 000004