(57)【特許請求の範囲】
【請求項１】
代数体Ｋ、Ｋの整数環ＯK 、整数ｎ，ｋ，ｈが入力され、
Ｏk のｈ個の素イデアルｐ1 ，…，ｐh を生成し、
ｐ1 ，…，ｐh を乗算してｐを求め、
１＜ｊ＜ｈを満す各ｊに対して、群ＯK ／ｐj （ただし０を除く）の生成元ｇj を生成し、
１＜ｉ＜ｎ，１＜ｊ＜ｈを満す各ｉ，ｊに対して、ｐj を除いたＯK からの元ｐijを生成し、
１＜ｉ＜ｎ，１＜ｊ＜ｈを満す各ｉ，ｊに対して、ｐij≡ｇjaij（mod ｐj）を満すａijを計算し、
中国人剰余定理による合成により、
ｇ＝（ｇ1 ,…,ｇh ）
ａi ＝（ａi1,…,ａih）
を満すｇ，ａ1 ，…,ａn を求め、
整数の乱数ｄを生成し、
１＜ｉ＜ｎを満す各ｉに対して、ｂi ＝（ａi ＋ｄ）mod（Ｎ（ｐ）−２）（Ｎ（ｐ）はｐのノルムを表わす）を計算して公開鍵ｂi を公開し、ｐ，ｇを秘密鍵とする公開鍵生成器と、
長さ［log nＣk ］の平文Ｍが入力され、（nＣk はｎからｋ個取出す組合せの数、［Ａ］はＡより大きい最小の整数）
整数ｋと公開鍵ｂi とＭを、長さｎでＨａｍｍｉｎｇ（ハミング）重さｋである二進列ｍ＝（ｍ1 ，ｍ2 ，…,ｍn）に変換し、
暗号文ｃ＝Σi=1nｍi ｂi を生成して出力する暗号器と、
ｋ，ｄ、秘密鍵ｐ，ｇを保持し、
暗号文ｃが入力されｒ＝（ｃ−ｋｄ）mod（Ｎ（ｐ）−２）を生成し、
ｕ＝ｇrmodｐを求め、
長さｎで、Ｈａｍｍｉｎｇ重さｋである二進列ｍ＝（ｍ1 ，…,ｍn ）を、１＜ｊ＜ｎを満す各ｊに対して、ｐijがｕmodｐj を割り切るならばｍi ＝１とし、そうでないならばｍi ＝０と生成し、
そのｍを平文Ｍに変換する復号器とを備える
ことを特徴とするナップサック型公開鍵暗号システム。
【請求項２】
ナップサック型公開鍵暗号の公開鍵生成方法であって、
代数体Ｋ、Ｋの整数環をＯK とし、ｎ，ｋ，ｈを整数とし、
ＯK のｈ個の素イデアルｐ1 ，…，ｐh を乱数発生器より生成し、
１＜ｊ＜ｈを満す各ｊについて、群ＯK ／ｐj （ただし０を含まない）の生成元ｇj を乱数発生器より生成し、
１＜ｉ＜ｎ，１＜ｊ＜ｈをそれぞれ満たす各ｉ,ｊについてｐj を除いたＯK からの元ｐijを乱数発生器より生成し、
１＜ｉ＜ｎ，１＜ｊ＜ｈをそれぞれ満す各ｉ，ｊについてｐij≡ｇjaij（modｐj）を満すａijを演算手段により計算し、
中国人剰余定理による合成により、
ｇ＝（ｇ1 ,…,ｇh ）
ａi ＝（ａi1,…,ａih）
を満すｇ，ａ1 ，…,ａn を演算手段により求め、
整数ｄを乱数発生器より生成し、
１＜ｉ＜ｎを満す各ｉについてｂi ＝（ａi ＋ｄ）mod（Ｎ（ｐ）−２）を演算手段により計算して公開鍵ｂi を得ることを特徴とするナップサック型公開鍵生成方法。
【請求項３】
代数体Ｋの整数環をＯK とし、ｎ，ｋ，ｈを整数とし、
Ｋ，ＯK ,ｎ，ｋ，ｈが入力され、ＯK のｈ個の素イデアルｐ1 ，…，ｐh と、１＜ｊ＜ｈを満す各ｊに対し、群ＯK ／ｐj （ただし０を除く）の生成元ｇj と、１＜ｉ＜ｎ，１＜ｊ＜ｈをそれぞれ満すｉｊに対して、ｐj を除いたＯK からの元ｐijと、整数ｄとを生成する乱数発生器と、
１＜ｉ＜ｎ，１＜ｊ＜ｈを満す各ｉｊについてｐij，ｇi ，ｐj が入力され、ｐij≡ｇjaijmodｐjを満すａijを計算して出力する離散対数計算量と、
ｇi(ｉ＝１，…,ｈ），ａij（ｉ＝１，…，ｎ,ｊ＝１，…，ｈ）が入力され、中国人剰余定理により、ｇ＝（ｇ1 ,…,ｇh ）、ａi ＝（ａi1,…,ａih）をそれぞれ計算する中国人剰余定理合成器と、
ｄとａi(ｉ＝１，…,ｎ)、Ｎ（ｐ）が入力され、（Ｎ（ｐ）はｐのノルムを表わす）
ｂi ＝（ａi ＋ｄ）mod（Ｎ（ｐ）−２）
を計算して公開鍵ｂi（ｉ＝１，…，ｎ）を得る加算器と
を具備するナップサック型公開鍵生成装置。
【請求項４】
ナップサック型公開鍵暗号の公開鍵を生成するためにコンピュータを、
代数体Ｋ、Ｋの整数環をＯK とし、ｎ，ｋ，ｈを整数とし、
ＯK のｈ個の素イデアルｐ1 ，…，ｐh を乱数により生成する手段、
１＜ｊ＜ｈを満す各ｊについて、群ＯK ／ｐj （ただし０を含まない）の生成元ｇj を乱数により生成する手段、
１＜ｉ＜ｎ，１＜ｊ＜ｈをそれぞれ満たす各ｉ,ｊについてｐj を除いたＯK からの元ｐijを乱数により生成する手段、
１＜ｉ＜ｎ，１＜ｊ＜ｈをそれぞれ満す各ｉ，ｊについてｐij≡ｇjaij（modｐj）を満すａijを演算する手段、
中国人剰余定理による合成により、
ｇ＝（ｇ1 ,…,ｇh ）
ａi ＝（ａi1,…,ａih）
を満すｇ，ａ1 ，…,ａn を演算する手段、
整数ｄを乱数により生成する手段、
１＜ｉ＜ｎを満す各ｉについて公開鍵ｂi ＝（ａi ＋ｄ）mod（Ｎ（ｐ）−２）を演算する手段、
として機能させるためのナップサック型公開鍵生成プログラム。
【請求項５】
ナップサック型公開鍵暗号の公開鍵を生成するためにコンピュータを、
代数体Ｋ、Ｋの整数環をＯK とし、ｎ，ｋ，ｈを整数とし、
ＯK のｈ個の素イデアルｐ1 ，…，ｐh を乱数により生成する手段、
１＜ｊ＜ｈを満す各ｊについて、群ＯK ／ｐj （ただし０を含まない）の生成元ｇj を乱数により生成する手段、
１＜ｉ＜ｎ，１＜ｊ＜ｈをそれぞれ満たす各ｉ,ｊについてｐj を除いたＯK からの元ｐijを乱数により生成する手段、
１＜ｉ＜ｎ，１＜ｊ＜ｈをそれぞれ満す各ｉ，ｊについてｐij≡ｇjaij（modｐj）を満すａijを演算する手段、
中国人剰余定理による合成により、
ｇ＝（ｇ1 ,…,ｇh ）
ａi ＝（ａi1,…,ａih）
を満すｇ，ａ1 ，…,ａn を演算する手段、
整数ｄを乱数により生成する手段、
１＜ｉ＜ｎを満す各ｉについて公開鍵ｂi ＝（ａi ＋ｄ）mod（Ｎ（ｐ）−２）を演算する手段
として機能させるためのナップサック型公開鍵生成プログラムを記録したコンピュータ読み取り可能な記録媒体。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
この発明はナップサック型公開鍵暗号システムとその公開鍵の生成方法及びその装置、そのプログラム及びその記録媒体に関する。
【０００２】
【従来の技術】
公開鍵暗号システムは、その安全性をよりどころとする問題により類別される。このような、よりどころとなる問題としては、素因数分解問題、離散対数問題、ナップサック問題などが挙げられる。これらの問題のうち、ナップサック問題を安全性のよりどころとする公開鍵暗号システムとしては、Ｍａｒｋｌｅ−Ｈｅｌｌｍａｒ暗号やＣｈｏｒ−Ｒｉｖｅｓｔ暗号などがあるが、そのいずれについても攻撃が成功した例が報告されている。また、これらの鍵生成処理における動作速度は非常に遅いことが知られている。
【０００３】
【発明が解決しようとする課題】
この発明の目的はナップサック問題を安全性のよりどころとし、解読が困難であり、鍵生成処理を含むすべての処理速度が高速である新しい公開鍵暗号システムとその公開鍵生成方法及びその装置を提供することにある。
【０００４】
【課題を解決するための手段】
この発明では乱数ｐij（ｉ＝１，…，ｎ，ｊ＝１，…，ｈ）と、乱数ｇi ，ｐj に対し、ｐij≡ｇjaij（modｐj）を満すａijを計算し、ａi ＝（ａi1，…,ａih）を中国人剰余定理を用いることにより、鍵生成処理で行う離散対数の計算及び復号処理を高速化している。つまり、従来ではｐi＝ｇiai（modｉ）を満たすａi を直接求めていたため、その計算に長時間を要し、かつａi を短かくすると、攻撃に対し弱いものとなる。
【０００５】
また、長さ［log nＣk］の平文を長さｎでＨａｍｍｉｎｇ（ハミング）重さｋである二進列に変換することにより、方式の安全性を高めている。
【０００６】
【発明の実施の形態】
この発明で用いる公開鍵暗号システムの実施の形態について、図を参照して説明する。このシステムは鍵生成装置と暗号化装置と復号装置とよりなる。
鍵生成装置：（図１）
Ｋを代数体、ＯKをＫの整数環、ｎ，ｋ，ｈを整数とする。ｎは整数環ＯKの箇数であり、例えば１０００などの大きな値であり、ｋは例えば２００程度、ｈは例えば１０程度である。ｎ，ｋは公開される。
【０００７】
図１にこの発明の公開鍵生成装置の実施形態を示す。Ｋ，ＯK，ｎ，ｋ，ｈがキーボードなどの入力部１００から入力され、これらの値は記憶部１１０に一旦格納され、その後、これらが取り出されて乱数発生器１０１に入力される。乱数発生器１０１はＯKのｈ個の素イデアルｐ1，…，ｐhを１＜ｊ＜ｈを満す各ｊに対して、群（ＯK／pj）（ただしゼロを除く）の生成元ｇj，つまりｇ1，…，ｇhを１＜ｉ＜ｎ，１＜ｊ＜ｈを満す各ｉ，ｊに対して、ｐjを除いたＯK／ｐjからの元ｐij、つまりｐ11，…，ｐ1h，ｐ21，…，ｐ2h，……，ｐn1，…，ｐnhを発生させる。
【０００８】
素イデアルｐ1，…，ｐhが乗算器１０２に入力されこれらの積ｐ＝ｐ1，…ｐhが求められる。
またｐ1，…，ｐh1，ｇ1，…，ｇh,ｐ11，…，ｐ1h，ｐ21，…，ｐ2h，……，ｐn1…ｐnhが離散対数計算器１０３に入力されて、
１＜ｉ＜ｎ，１＜ｊ＜ｈを満す各ｉ，ｊに対して
ｐij≡ｇjaij（modｐj）                        …（１）
を満たすようなａijが計算される。
【０００９】
さらに、ｇ1，…，ｇh，ａij（ｉ＝１，２，…，ｎ，ｊ＝１，２，…，ｈ）が中国人剰余定理による合成器１０４に入力され、１＜ｉ＜ｎを満す各ｉに対して、
ｇ＝（ｇ1，…，ｇh）
ａi＝（ａi1，…，ａih）
を満たすｇ，ａ1，…，ａnが計算される。
乱数発生器１０５を用いて整数ｄが発生され、このｄ，ａi，ｐが加算器１０６に入力され、
１＜ｉ＜ｎを満す各ｉに対して、
ｂi＝（ａi＋ｄ）ｍｏｄ（Ｎ（ｐ）−２）        …（２）
が計算され、最終的に公開鍵ｂ1，…，ｂnが出力され、公開される。ｐ，ｐij，ｇは秘密鍵であり、これらは乱数ｄと共に記憶部１１０に秘密に記憶される。整数ｄは例えば０〜Ｎ（ｐ）−１程度、これ以上でもよく、またｄは乱数発生器１０１から発生させてもよい。
暗号化処理：（図２）
暗号装置は図２に示すように記憶部２００に、公開情報ｎ、ｋ、公開鍵ｂ1，…，ｂnが格納されている。入力される平文Ｍの長さは[log nＣk]である。logは２を程とし、nＣkはｎからｋを取り出す組合せの数、［Ａ］はＡ以上の最小の整数を表す。
【００１０】
この平文Ｍは平文変換器２０１でＨａｍｍｉｎｇ重さがｋ（１の数がｋ個）のｎビットの２進列ｍ＝（ｍ1，ｍ2，…，ｍn）に変換される。この変換は例えばｑをｋとし、ｉ＝１からｎまで以下のことを実行する。
Ｍ＞ n-iＣqであれば、ｍiを１とし、Ｍ− n-iＣq-1をＭとし、ｑ−１をｑとし、Ｍ＞ n-iＣqでなければ、ｍiを０とする。ただしｑ＞０に対し qＣ0＝０とし、ｑ＞１に対し 0Ｃq＝０とする。
この２進列ｍと、公開鍵ｂiとが加算器２０２に入力されて、
ｃ＝Σi=1n ｍiｂi                      …（３）
の計算が行われ、暗号文ｃが出力される。
復号処理：（図３）
図３に復号装置を示す。記憶部３００にはｐ，ｐij，ｐj，ｇ，ｋ，ｄが記憶されてある。入力された暗号文ｃとｋ，ｄ，ｐが減算器３０１に入力されて、
ｒ＝（ｃ−ｋｄ）mod（Ｎ（ｐ）−２）      …（４）
Ｎ（ｐ）はｐのノルム
が計算される。その計算結果ｒとｇ，ｐがべき乗演算器３０２に入力されて、
ｕ＝ｇr mod ｐ                        …（５）
が計算される。この計算結果ｕとｐi，ｊ，ｐjが検査器３０３に入力され、検査器３０３では、長さｎでＨａｍｍｉｎｇ重さｋである２進列ｍ＝（ｍ1，…，ｍn）を、その１＜ｊ＜ｎを満たす各ｊに対してｐijがｕ mod ｐjを割り切るならばｍ1＝１とされ、そうでなければｍi＝０とされる。このようにして２進列ｍが復号される。この復号された２進列ｍが中間復号文変換器３０４にｎ，ｋと共に入力されて、ｍ＝（ｍ1，…，ｍn）が平文Ｍに変換され、復号平文Ｍが出力される。この変換は例えばＭを０とし、ｑをｈとし、ｉ＝１からｎまで下記を実行する。
【００１１】
ｍiが１であればＭ＋ p-iＣqをＭとし、ｑ−１をｑとする。
所で式（５）に式（４）を代入すると
ｕ≡ｇc-hd mod ｐ                    …（６）
となり、式（３）よりｇの指数は、
Σi=1n ｍiｂi−ｋｄ
となり、式（２）よりｂi＝（ａi＋ｄ）であり、２進列ｍ中のｋ個が１であるからｇの指数は、
Σi=1n ｍiｂi mod ｐ
となる。この指数を式（５）に代入して、指数の積の形式に変形すると
ｕ≡Πi=1n（ｇai）mi  mod ｐ
となる。式（１）の関係から
ｕ≡Πi=1n ｐimi
となる。従ってｕをｐijが割り切るならばｍi＝１とし、そうでなければ、ｍi＝０として、２進列ｍが復号される。
【００１２】
図１に示した公開鍵生成装置、図２に示した暗号装置、図３に示した復号装置は、それぞれコンピュータによりプログラムを実行させて機能させることができる。つまり例えば公開鍵生成装置は入力手段、出力手段、記憶部１１０、公開鍵生成プログラムを格納したプログラムメモリ、ＣＰＵ（マイクロプロセッサ）などを備えるコンピュータにおいて、ＣＰＵにより公開鍵生成プログラムを実行させて、前述したように公開鍵ｇiを生成させるようにすることもできる。
【００１３】
【発明の効果】
この発明によれば、鍵生成処理における離散対数の計算について中国人剰余定理を用いることにより高速化している。また、中国人剰余定理を用いることにより復号処理も高速化している。
つまり従来においてはａ1，…，ａnを式（１）の離散対数計算により直接求めていた。例えばｈを１０とすると、ａiは１００となり、このような大きな値の指数を求めるには非常に長い時間がかかる。よってａiの値を小さくすると、攻撃され易いものとなる。しかし、この発明によれば、ａijに分割しているためａijは例えば１０程度の値で済み、比較的簡単にａijを求めることができ、しかも、中国人剰余定理によりａi＝（ａi1，…，ａih）を比較的簡単に求めることができ、全体として高速化することができ、かつ攻撃に対しても強いものとすることができる。
【００１４】
暗号化処理と復号処理において、長さ［ｌｏｇ（kn）］の平文を長さｎでＨａｍｍｉｎｇ重さｋである２進列へ変換することにより、ナップサック暗号の安全性の指標である密度を十分に高めることができ、したがって、平文から暗号文を直接求める低密度攻撃にも耐えうる。
【図面の簡単な説明】
【図１】この発明のシステム中の公開鍵生成装置の機能構成例を示す図。
【図２】この発明のシステム中の暗号化装置の機能構成例を示す図。
【図３】この発明のシステム中の復号装置の機能構成例を示す図。
【図１】
0003740659.tif 000002
【図２】
0003740659.tif 000003
【図３】
0003740659.tif 000004