(57)【特許請求の範囲】
【請求項１】
鍵生成処理部と暗号化処理部と復号処理部を備え、
鍵生成処理部は、
ｎとｋを整数としたとき、
素数ｐ、互いに素である数列｛ｐ１，・・・，ｐｎ｝、生成元ｇを生成し、
各々の１≦ｉ≦ｎに対してｐｉ≡ｇａｉ  （ｍｏｄ  ｐ）を満たすようなａ１，・・・，ａｎを求め、
乱数ｄを生成し、
各々の１≦ｉ≦ｎに対して公開鍵ｂｉ＝（ａｉ＋ｄ）  ｍｏｄ  （ｐ−１）を求め、
暗号化処理部は、
長さ
【数１】
0003615132.tif 000007
の平文をＭとしたとき、
Ｍを長さｎでハミング重さｋである二進列ｍ＝（ｍ１，ｍ２，・・・，ｍｎ）に変換し、
暗号文
【数２】
0003615132.tif 000008
を生成し、
復号処理部は、
暗号文ｃからｒ＝（ｃ−ｋｄ）  ｍｏｄ  （ｐ−１）を生成し、
ｕ＝ｇｒ  （ｍｏｄ  ｐ）を求め、
長さｎでハミング重さｋである二進列ｍ＝（ｍ１，ｍ２，・・・，ｍｎ）を、ｐｉがｕの因数ならばｍｉ＝１とし、因数でないならばｍｉ＝０とすることにより生成し、
ｍを平文Ｍに変換すること
を特徴とする公開鍵暗号化復号方法。
【請求項２】
鍵生成処理部と暗号化処理部を備え、
鍵生成処理部は、
ｎとｋを整数としたとき、
素数ｐ、互いに素である数列｛ｐ１，・・・，ｐｎ｝、生成元ｇを生成し、
各々の１≦ｉ≦ｎに対してｐｉ≡ｇａｉ  （ｍｏｄ  ｐ）を満たすようなａ１，・・・，ａｎ  を求め、
乱数ｄを生成し、
各々の１≦ｉ≦ｎに対して公開鍵ｂｉ＝（ａｉ＋ｄ）  ｍｏｄ  （ｐ−１）を求め、
暗号化処理部は、
長さ
【数３】
0003615132.tif 000009
の平文をＭとしたとき、
Ｍを長さｎでハミング重さｋである二進列ｍ＝（ｍ１，ｍ２，・・・，ｍｎ）に変換し、
暗号文
【数４】
0003615132.tif 000010
を生成すること
を特徴とする暗号化方法。
【請求項３】
鍵生成処理として、
ｎとｋを整数としたとき、
素数ｐ、互いに素である数列｛ｐ１，・・・，ｐｎ｝、生成元ｇを生成し、
各々の１≦ｉ≦ｎに対してｐｉ≡ｇａｉ  （ｍｏｄ  ｐ）を満たすようなａ１，・・・，ａｎ  を求め、
乱数ｄを生成し、
各々の１≦ｉ≦ｎに対して公開鍵ｂｉ＝（ａｉ＋ｄ）  ｍｏｄ  （ｐ−１）を求め、
暗号化処理として、
長さ
【数５】
0003615132.tif 000011
の平文をＭとしたとき、
Ｍを長さｎでハミング重さｋである二進列ｍ＝（ｍ１，ｍ２，・・・，ｍｎ）に変換し、
暗号文
【数６】
0003615132.tif 000012
を生成する暗号化方法により生成された暗号文ｃを入力し、
復号処理部は、
暗号文ｃからｒ＝（ｃ−ｋｄ）  ｍｏｄ  （ｐ−１）を生成し、
ｕ＝ｇｒ  （ｍｏｄ  ｐ）を求め、
長さｎでハミング重さｋである二進列ｍ＝（ｍ１，ｍ２，・・・，ｍｎ）を、ｐｉがｕの因数ならばｍｉ＝１とし、因数でないならばｍｉ＝０とすることにより生成し、
ｍを平文Ｍに変換すること
を特徴とする公開鍵復号方法。
【請求項４】
鍵生成処理として、
ｎとｋを整数としたとき、
素数ｐ、互いに素である数列｛ｐ１，・・・，ｐｎ｝、生成元ｇを生成する乱数発生器Ａと、
各々の１≦ｉ≦ｎに対してｐｉ≡ｇａｉ  （ｍｏｄ  ｐ）を満たすようなａ１，・・・，ａｎを求める離散対数計算器と、
乱数ｄを生成する乱数発生器Ｂと、
各々の１≦ｉ≦ｎに対して公開鍵ｂｉ＝（ａｉ＋ｄ）  ｍｏｄ  （ｐ−１）を求める加算器Ａと、
暗号化処理として、
長さ
【数７】
0003615132.tif 000013
の平文をＭとしたとき、
Ｍを長さｎでハミング重さｋである二進列ｍ＝（ｍ１，ｍ２，・・・，ｍｎ）に変換する平文変換器と、
暗号文
【数８】
0003615132.tif 000014
を生成する加算器Ｂと、
復号処理として、
暗号文ｃからｒ＝（ｃ−ｋｄ）  ｍｏｄ  （ｐ−１）を生成する減算器と、
ｕ＝ｇｒ  （ｍｏｄ  ｐ）を求める冪乗演算部と、
長さｎでハミング重さｋである二進列ｍ＝（ｍ１，ｍ２，・・・，ｍｎ）を、ｐｉがｕの因数ならばｍｉ＝１とし、因数でないならばｍｉ＝０とすることにより生成する因数検査器と、
ｍを平文Ｍに変換する中間復号変換器を備えたこと
を特徴とする公開鍵暗号化復号システム。
【請求項５】
鍵生成処理として、
ｎとｋを整数としたとき、
素数ｐ、互いに素である数列｛ｐ１，・・・，ｐｎ｝、生成元ｇを生成する乱数発生器Ａと、
各々の１≦ｉ≦ｎに対して公開鍵ｐｉ≡ｇａｉ  （ｍｏｄ  ｐ）を満たすようなａ１，・・・，ａｎ  を求める離散対数計算器と、
乱数ｄを生成する乱数発生器Ｂと、
各々の１≦ｉ≦ｎに対して公開鍵ｂｉ＝（ａｉ＋ｄ）  ｍｏｄ  （ｐ−１）を求める加算器Ａと、
暗号化処理として、
長さ
【数９】
0003615132.tif 000015
の平文をＭとしたとき、
Ｍを長さｎでハミング重さｋである二進列ｍ＝（ｍ１，ｍ２，・・・，ｍｎ）に変換する平文変換器と、
暗号文
【数１０】
0003615132.tif 000016
を生成する加算器Ｂを備えたこと
を特徴とする暗号化装置。
【請求項６】
鍵生成処理として、
ｎとｋを整数としたとき、
素数ｐ、互いに素である数列｛ｐ１，・・・，ｐｎ｝、生成元ｇを生成する乱数発生器Ａと、
各々の１≦ｉ≦ｎに対してｐｉ≡ｇａｉ  （ｍｏｄ  ｐ）を満たすようなａ１，・・・，ａｎ  を求める離散対数計算器と、
乱数ｄを生成する乱数発生器Ｂと、
各々の１≦ｉ≦ｎに対して公開鍵ｂｉ＝（ａｉ＋ｄ）  ｍｏｄ  （ｐ−１）を求める加算器Ａと、
長さ
【数１１】
0003615132.tif 000017
の平文をＭとしたとき、
Ｍを長さｎでハミング重さｋである二進列ｍ＝（ｍ１，ｍ２，・・・，ｍｎ）に変換する平文変換器と、
暗号文
【数１２】
0003615132.tif 000018
を生成する加算器Ｂを備えた暗号化装置により生成された暗号文ｃを入力し、復号処理として、
暗号文ｃからｒ＝（ｃ−ｋｄ）  ｍｏｄ  （ｐ−１）を生成する減算器と、
ｕ＝ｇｒ  （ｍｏｄ  ｐ）を求める冪乗演算器と、
長さｎでハミング重さｋである二進列ｍ＝（ｍ１，ｍ２，・・・，ｍｎ）を、ｐｉがｕの因数ならばｍｉ＝１とし、因数でないならばｍｉ＝０とすることにより生成する因数検査器と、
ｍを平文Ｍに変換する中間復号文変換器を備えたこと
を特徴とする公開鍵復号装置。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は公開鍵暗号化復号方法及びシステムに関し、特に、ナップサック問題をよりどころとする公開鍵暗号化復号方法及びシステムに関するものである。
【０００２】
【従来の技術】
公開鍵暗号システムは、その安全性のよりどころとする問題により類別される。
このような、よりどころとなる問題としては、素因数分解問題、離散対数問題、ナップサック問題などが挙げられる。これらの問題のうち、ナップサック問題を安全性のよりどころとする公開鍵暗号システムとしては、Ｍａｒｋｌｅ−Ｈｅｌｌｍａｎ（マークル−ヘルマン）暗号やＣｈｏｒ−Ｒｉｖｅｓｔ（コール−リベスト）暗号などがあるが、そのいずれについても攻撃が成功した例が報告されている。
【０００３】
【発明が解決しようとする課題】
本発明は、ナップサック問題を安全性のよりどころとする新しい公開鍵暗号化復号方法及びシステムを実現する。
【０００４】
【課題を解決するための手段】
本発明では、有理整数環上の離散対数問題を用いて鍵生成処理を行い、長さ
【０００５】
【数１３】
0003615132.tif 000002
【０００６】
の整数と長さｎでＨａｍｍｉｎｇ（ハミング）重さｋである二進列との変換を用いて暗号化処理と復号処理を行う新しい手法を示す。
【０００７】
【発明の実施の形態】
本発明で用いる公開鍵暗号方式の構成法の実施例について、図１，図２，図３を用いて説明する。
（鍵生成処理：図１）
鍵生成処理部は、乱数発生器Ａ（１０１）、離散対数計算器（１０２）、乱数発生器Ｂ（１０３）、及び加算器Ａ（１０４）から構成される。
（１）ベクトルのサイズをそれぞれ整数ｎ、ｋとし（ｎ、ｋは公開される。）、このｎとｋを入力し、乱数発生器Ａ（１０１）を用いてベクトル｛ｐ１，ｐ２，・・・，ｐｎ｝からの任意の部分集合｛ｐｉ１，ｐｉ２，・・・，ｐｉｋ｝が
【０００８】
【数１４】
0003615132.tif 000003
【０００９】
を満たすような素数ｐ、互いに素である数ｐ１，ｐ２，・・・，ｐｎ∈Ｚ／ｐＺ（素数ｐを法とする整数の体）、及び群（Ｚ／ｐＺ）の生成元ｇを発生させる。
（２）次に乱数発生器Ａ（１０１）で発生させたｐ１，ｐ２，・・・，ｐｎ，ｇを入力し、離散対数計算器（１０２）を用いて、各々の１≦ｉ≦ｎに対してｐｉ  ≡ｇａｉ（ｍｏｄ  ｐ）を満たすようなａ１，・・・，ａｎを求める。
（３）さらに乱数発生器Ｂ（１０３）を用いて、Ｚ／（ｐ−１）Ｚからの整数ｄを発生させる。
（４）最後に、乱数発生器Ａ（１０１）で発生させたｐ、離散対数計算器（１０２）で発生させたａ１，・・・，ａｎ、乱数発生器Ｂ（１０３）で発生させたｄを入力し、加算器Ａ（１０４）を用いて、各々の１≦ｉ≦ｎに対して公開鍵ｂｉ＝（ａｉ＋ｄ）  ｍｏｄ（ｐ−１）を求めて出力する。
（暗号化処理：図２）
暗号化処理部は、平文変換器（２０１）、加算器Ｂ（２０２）から構成される。
【００１０】
長さ
【数１５】
0003615132.tif 000004
【００１１】
（１）平文Ｍ、ｎとｋを入力し、平文変換器（２０１）を用いて、Ｍを長さｎでＨａｍｍｉｎｇ重さｋである二進列ｍ＝（ｍ１，ｍ２，・・・，ｍｎ）に変換する。
（２）平文変換器（２０１）で変換されたｍと鍵生成処理部で求めた公開鍵ｂｉを入力し、加算器Ｂ（２０２）を用いて、暗号文
【００１２】
【数１６】
0003615132.tif 000005
【００１３】
を生成して出力する。
（復号処理：図３）
復号処理部は、減算器（３０１）、冪乗演算器（３０２）、因数検査器（３０３）、及び中間復号文変換器（３０４）から構成される。
（１）暗号文ｃ、秘密鍵ｄ，ｐ、ｋを入力し、減算器（３０１）を用いて、暗号文ｃからｒ＝（ｃ−ｋｄ）  ｍｏｄ（ｐ−１）を求める。
（２）次に、乱数発生器Ａ（１０１）で発生させたｇと減算器（３０１）で求めたｒを入力し、冪乗演算器（３０２）を用いて、ｒからｕ＝ｇｒ  （ｍｏｄ  ｐ）を生成する。
（３）さらに、乱数発生器Ａ（１０１）で発生させたｐ１，ｐ２，・・・，ｐｎと冪乗演算器（３０２）で生成したｕを入力し、因数検査器（３０３）を用いて、長さｎでＨａｍｍｉｎｇの重さｋである二進列ｍ＝（ｍ１，ｍ２，・・・，ｍｎ）を、ｐｉがｕの因数ならばｍｉ＝１とし、因数でないならばｍｉ＝０とすることにより求める。
（４）最後に、ｎ，ｋと因数検査器（３０３）で求めたｍを入力し、中間複合文変換器（３０４）を用いて、ｍを平文Ｍに変換する。
【００１４】
【発明の効果】
本発明で実現する公開鍵暗号システムは、鍵生成処理において有理整数環上の離散対数問題を利用すること、および、ｐ，ｐ１，・・・，ｐｎ，ｇ，ｄを秘密にすることにより、公開鍵から秘密鍵を直接求める攻撃に耐えうる。また、暗号化処理と復号処理において、長さ
【００１５】
【数１７】
0003615132.tif 000006
【００１６】
の整数と長さｎでＨａｍｍｉｎｇ重さｋである二進列との変換を利用することにより、ナップサック暗号の安全性の指標であるｄｅｎｓｉｔｙ（密度）を十分高めることができ、したがって、平文から暗号文を直接求めるｌｏｗ−ｄｅｎｓｉｔｙ攻撃にも耐える。なお、安全性についてのフォーマルな記述は、文献（Ｔ．Ｏｋａｍｏｔｏ，Ｋ．Ｔａｎａｋａ，Ｓ．Ｕｃｈｉｙａｍａ，”Ｑｕａｎｔｕｍ    Ｐｕｂｌｉｃ−Ｋｅｙ    Ｃｒｙｐｔｓｙｓｔｅｍｓ”，Ｐｒｏｃ．ｏｆ  ＣＲＹＰＴＯ２０００，Ｓｐｒｉｎｇｅｒ，２０００）に掲載されている。
【図面の簡単な説明】
【図１】鍵生成処理部の構成を示すブロック図。
【図２】暗号化処理部の構成を示すブロック図。
【図３】復号処理部の構成を示すブロック図。
【符号の説明】
１０１        乱数発生器Ａ
１０２        離散対数計算器
１０３        乱数発生器Ｂ
１０４        加算器Ａ
２０１        平文変換器
２０２        加算器Ｂ
３０１        減算器
３０２        冪乗演算器
３０３        因数検査器
３０４        中間復号文変換器
【図１】
0003615132.tif 000019
【図２】
0003615132.tif 000020
【図３】
0003615132.tif 000021