(57)【特許請求の範囲】
【請求項１】
公開鍵ａ＝（ａ１，ａ２，・・・，ａｎ）を生成する公開鍵生成装置であって、
超増加ベクトルｂ＝（ｂ１，ｂ２，・・・，ｂｎ）を記憶する手段と、互いに素な自然数ｐとｑとを記憶する手段と、乱数を要素とするベクトルｒ＝（ｒ１，ｒ２，・・・，ｒｎ）を記憶する手段と、
前記超増加ベクトルｂと、自然数ｐおよびｑと、ベクトルｒとを参照して、
ａｉ≡ｂｉ  （ｍｏｄ  ｐ）
ａｉ≡ｒｉ  （ｍｏｄ  ｑ）
を満たすａ＝（ａ１，ａ２，・・・，ａｎ）を生成する演算手段と
を備えることを特徴とする公開鍵生成装置：
ただし、
０≦ｒｉ＜ｑ
【数１】
0004200259.tif 000035
を満たすものとする。
【請求項２】
公開鍵ａ＝（ａ１，ａ２，・・・，ａｎ）を用いて、平文ｘを暗号文Ｃに変換する暗号化装置であって、
前記公開鍵ａを記憶する手段と、前記平文ｘを記憶する手段と、
【数２】
0004200259.tif 000036
を計算する演算手段とを備えることを特徴とする暗号化装置：
ただし、前記公開鍵ａは、
超増加ベクトルｂ＝（ｂ１，ｂ２，・・・，ｂｎ）、
互いに素な自然数ｐとｑ、
乱数を要素とするベクトルｒ＝（ｒ１，ｒ２，・・・，ｒｎ）、とすると、
ａｉ≡ｂｉ  （ｍｏｄ  ｐ）
ａｉ≡ｒｉ  （ｍｏｄ  ｑ）
を満たし、
０≦ｒｉ＜ｑ
【数３】
0004200259.tif 000037
を満たすものとする。
【請求項３】
公開鍵ａ＝（ａ１，ａ２，・・・，ａｎ）を用いて暗号化された暗号文Ｃを平文ｘに変換する復号装置であって、
前記暗号文Ｃを記憶する手段と、
公開鍵ａ＝（ａ１，ａ２，・・・，ａｎ）を生成するときに用いた超増加ベクトルｂ＝（ｂ１，ｂ２，・・・，ｂｎ）と、ｐとを記憶する手段と、
Ｃ'＝Ｃ  ｍｏｄ  ｐ
を算出し、
ｂｉについて、
１）Ｃ'≧ｂｉを満たす場合は、ｘｉを１とし、Ｃ'をＣ'−ｂｉとする、
２）Ｃ'≧ｂｉを満たさない場合は、ｘｉを０とする、
という処理を逆算カウンタ変数ｉがｎから１になるまで繰り返し、得られたｘ＝（ｘ１，ｘ２，・・・，ｘｎ）を平文とする演算手段と
を備えることを特徴とする復号装置：
ただし、前記公開鍵ａは、
超増加ベクトルｂ＝（ｂ１，ｂ２，・・・，ｂｎ）、
互いに素な自然数ｐとｑ、
乱数を要素とするベクトルｒ＝（ｒ１，ｒ２，・・・，ｒｎ）、とすると、
ａｉ≡ｂｉ  （ｍｏｄ  ｐ）
ａｉ≡ｒｉ  （ｍｏｄ  ｑ）
を満たし、
０≦ｒｉ＜ｑ
【数４】
0004200259.tif 000038
を満たすものとする。
【請求項４】
公開鍵ａ＝（ａ１，ａ２，・・・，ａｎ）を生成する公開鍵生成装置であって、
超増加ベクトルｂ＝（ｂ１，ｂ２，・・・，ｂｎ）を記憶する手段と、
整数Ｌと、０≦ｒｉ＜｜Ｌ／ｎ｜を満たす乱数のベクトルｒ＝（ｒ１，ｒ２，・・・，ｒｎ）と、乱数を要素とするベクトルＲ＝（Ｒ１，Ｒ２，・・・，Ｒｎ）とを記憶する手段と（ただし、｜Ｌ／ｎ｜は、Ｌ／ｎを超えない最大の整数）、
ｂｉ'＝Ｌｂｉ＋ｒｉとして、ｂ'＝（ｂ１'，ｂ２'，・・・，ｂｎ'）を求め、
【数５】
0004200259.tif 000039
を満たすＵと、互いに素な整数ｍとｗとを生成し、記憶するとともに、ａｉ＝ｗ（ｂｉ'＋ＵＲｉ）  ｍｏｄ  ｍを計算して、ａ＝（ａ１，ａ２，・・・，ａｎ）を生成する演算手段と
を備えることを特徴とする公開鍵生成装置：
ただし、
【数６】
0004200259.tif 000040
を満たすものとする。
【請求項５】
公開鍵ａ＝（ａ１，ａ２，・・・，ａｎ）を用いて、平文ｘを暗号文Ｃに変換する暗号化装置であって、
前記公開鍵ａを記憶する手段と、前記平文ｘを記憶する手段と、
【数７】
0004200259.tif 000041
を計算する演算手段とを備えることを特徴とする暗号化装置：
ただし、前記公開鍵ａは、
超増加ベクトルｂ＝（ｂ１，ｂ２，・・・，ｂｎ）、
整数Ｌ、
０≦ｒｉ＜｜Ｌ／ｎ｜（｜Ｌ／ｎ｜は、Ｌ／ｎを超えない最大の整数）を満たす乱数のベクトルｒ＝（ｒ１，ｒ２，・・・，ｒｎ）、
乱数を要素とするベクトルＲ＝（Ｒ１，Ｒ２，・・・，Ｒｎ）、
ｂ'＝（ｂ１'，ｂ２'，・・・，ｂｎ'）（ｂｉ'＝Ｌｂｉ＋ｒｉ）、
【数８】
0004200259.tif 000042
を満たすＵ、
互いに素な整数ｍとｗ、とすると、
ａｉ＝ｗ（ｂｉ'＋ＵＲｉ）  ｍｏｄ  ｍを計算することにより算出されたものであり、
【数９】
0004200259.tif 000043
を満たすものとする。
【請求項６】
公開鍵ａ＝（ａ１，ａ２，・・・，ａｎ）を用いて暗号化された暗号文Ｃを平文ｘに変換する復号装置であって、
前記暗号文Ｃを記憶する手段と、
この暗号文Ｃの生成に用いた公開鍵ａ＝（ａ１，ａ２，・・・，ａｎ）を生成するときに用いた超増加ベクトルｂ＝（ｂ１，ｂ２，・・・，ｂｎ）と、ｗとｍと、Ｕと、Ｌとを記憶する手段と、
Ｃ'＝ｗ−１Ｃ  ｍｏｄ  ｍとし、Ｃ''＝Ｃ'  ｍｏｄ  Ｕとし、さらに、Ｃ'''＝｜Ｃ''／Ｌ｜とし（｜Ｃ''／Ｌ｜はＣ''／Ｌを超えない最大の整数）、
ｂｉについて、
１）Ｃ'''≧ｂｉを満たす場合は、ｘｉを１とし、Ｃ'''をＣ'''−ｂｉとする、
２）Ｃ'''≧ｂｉを満たさない場合は、ｘｉを０とする、
という処理を逆算カウンタ変数ｉがｎからになる１まで繰り返し、得られたｘ＝（ｘ１，ｘ２，・・・，ｘｎ）を平文とする演算手段と
を備えることを特徴とする復号装置：
ただし、前記公開鍵ａは、
超増加ベクトルｂ＝（ｂ１，ｂ２，・・・，ｂｎ）、
整数Ｌ、
０≦ｒｉ＜｜Ｌ／ｎ｜（｜Ｌ／ｎ｜は、Ｌ／ｎを超えない最大の整数）を満たす乱数のベクトルｒ＝（ｒ１，ｒ２，・・・，ｒｎ）、
乱数を要素とするベクトルＲ＝（Ｒ１，Ｒ２，・・・，Ｒｎ）、
ｂ'＝（ｂ１'，ｂ２'，・・・，ｂｎ'）（ｂｉ'＝Ｌｂｉ＋ｒｉ）、
【数１０】
0004200259.tif 000044
を満たすＵ、
互いに素な整数ｍとｗ、とすると、
ａｉ＝ｗ（ｂｉ'＋ＵＲｉ）  ｍｏｄ  ｍを計算することにより算出されたものであり、
【数１１】
0004200259.tif 000045
を満たすものとする。
【請求項７】
記憶装置と、処理装置と、を有する電子計算機が、公開鍵ａ＝（ａ１，ａ２，・・・，ａｎ）を生成する方法であって、
前記記憶装置は、超増加ベクトルｂ＝（ｂ１，ｂ２，・・・，ｂｎ）と、互いに素な自然数ｐとｑと、乱数を要素とするベクトルｒ＝（ｒ１，ｒ２，・・・，ｒｎ）と、を格納し、
前記処理装置は、
ａｉ≡ｂｉ  （ｍｏｄ  ｐ）
ａｉ≡ｒｉ  （ｍｏｄ  ｑ）
を満たすａ＝（ａ１，ａ２，・・・，ａｎ）を算出して、得られたａを公開鍵とする公開鍵生成方法。
ただし、
０≦ｒｉ＜ｑ
【数１２】
0004200259.tif 000046
を満たすものとする。
【請求項８】
記憶装置と、処理装置と、を有する電子計算機が、公開鍵ａ＝（ａ１，ａ２，・・・，ａｎ）を用いて、平文ｘを暗号文Ｃに変換する暗号化方法であって、
前記記憶装置は、前記公開鍵ａと、前記平文ｘと、を格納し、
前記処理装置は、
【数１３】
0004200259.tif 000047
を計算して、得られたＣを暗号文とする暗号化方法。
ただし、前記公開鍵ａは、
超増加ベクトルｂ＝（ｂ１，ｂ２，・・・，ｂｎ）、
互いに素な自然数ｐとｑ、
乱数を要素とするベクトルｒ＝（ｒ１，ｒ２，・・・，ｒｎ）、とすると、
ａｉ≡ｂｉ  （ｍｏｄ  ｐ）
ａｉ≡ｒｉ  （ｍｏｄ  ｑ）
を満たし、
０≦ｒｉ＜ｑ
【数１４】
0004200259.tif 000048
を満たすものとする。
【請求項９】
記憶装置と、処理装置と、を有する電子計算機が、公開鍵ａ＝（ａ１，ａ２，・・・，ａｎ）を用いて暗号化された暗号文Ｃを平文ｘに変換する復号方法であって、
前記記憶装置は、前記暗号文Ｃと、公開鍵ａ＝（ａ１，ａ２，・・・，ａｎ）を生成するときに用いた超増加ベクトルｂ＝（ｂ１，ｂ２，・・・，ｂｎ）と、ｐと、を格納し、
前記処理装置は、
Ｃ'＝Ｃ  ｍｏｄ  ｐ
を算出し、
ｂｉについて、
１）Ｃ'≧ｂｉを満たす場合は、ｘｉを１とし、Ｃ'をＣ'−ｂｉとする、
２）Ｃ'≧ｂｉを満たさない場合は、ｘｉを０とする、
という処理を逆算カウンタ変数ｉがｎから１になるまで繰り返し、得られたｘ＝（ｘ１，ｘ２，・・・，ｘｎ）を平文とする復号方法。
ただし、前記公開鍵ａは、
超増加ベクトルｂ＝（ｂ１，ｂ２，・・・，ｂｎ）、
互いに素な自然数ｐとｑ、
乱数を要素とするベクトルｒ＝（ｒ１，ｒ２，・・・，ｒｎ）、とすると、
ａｉ≡ｂｉ  （ｍｏｄ  ｐ）
ａｉ≡ｒｉ  （ｍｏｄ  ｑ）
を満たし、
０≦ｒｉ＜ｑ
【数１５】
0004200259.tif 000049
を満たすものとする。
【請求項１０】
公開鍵行列
【数１６】
0004200259.tif 000050
を生成する公開鍵生成装置であって、
超増加行列
【数１７】
0004200259.tif 000051
を記憶する手段と、
互いに素な自然数ｐとｑとを記憶する手段と、乱数を要素とする行列
【数１８】
0004200259.tif 000052
とを記憶する手段と、
ａｊｉ≡ｂｊｉ  （ｍｏｄ  ｐ）
ａｊｉ≡ｒｊｉ  （ｍｏｄ  ｑ）
を満たすＡ＝（ａｊ１，ａｊ２，・・・，ａｊｎ）を生成する演算手段と
を備えることを特徴とする公開鍵生成装置：
ただし、
０≦ｒｊｉ＜ｑ
【数１９】
0004200259.tif 000053
を満たすものとする（ただし、ｂｉｍａｘ＝ｍａｘ｛ｂ１ｉ，ｂ２ｉ，・・・，ｂｈｉ｝）。
【請求項１１】
公開鍵行列Ａ＝（ａｊ１，ａｊ２，・・・，ａｊｎ）を用いて、平文ｘを暗号文Ｃに変換する暗号化装置であって、
前記公開鍵行列Ａを記憶する手段と、前記平文ｘを記憶する手段と、
【数２０】
0004200259.tif 000054
を計算する演算手段とを備えることを特徴とする暗号化装置：
ただし、ｃｉ∈｛ａ１ｉ，ａ２ｉ，・・・，ａｈｉ｝における、ａｊｉの添字ｊ＝ｊ（ｉ）は、以下のように定めるものとする。
１）変数ｎ１を初期値−１とする
２）変数ｉをｉ＝ｎから、ｉ＝１まで変化させて、次の処理を行なう。
ｎ１＝ｎ１＋ｘｉ，  ｊ＝（ｎ１  ｍｏｄ  ｈ）＋  １
また、前記公開鍵行列Ａは、
超増加行列
【数２１】
0004200259.tif 000055
互いに素な自然数ｐとｑ、
乱数を要素とする行列
【数２２】
0004200259.tif 000056
ａｊｉ≡ｂｊｉ  （ｍｏｄ  ｐ）
ａｊｉ≡ｒｊｉ  （ｍｏｄ  ｑ）
を満たし、
０≦ｒｊｉ＜ｑ
【数２３】
0004200259.tif 000057
を満たすものとする（ただし、ｂｉｍａｘ＝ｍａｘ｛ｂ１ｉ，ｂ２ｉ，・・・，ｂｈｉ｝）。
【請求項１２】
公開鍵行列Ａ＝（ａｊ１，ａｊ２，・・・，ａｊｎ）を用いて暗号化された暗号文Ｃを平文ｘに変換する復号装置であって、
前記暗号文Ｃを記憶する手段と、
公開鍵行列Ａ＝（ａｊ１，ａｊ２，・・・，ａｊｎ）を生成するときに用いた超増加行列Ｂ＝（ｂｊ１，ｂｊ２，・・・，ｂｊｎ）と、ｐとを記憶する手段と、
Ｃ'＝Ｃ  ｍｏｄ  ｐ
を算出し、
ｂｊｉについて、ｊ＝１とし、
１）Ｃ’≧ｂｊｉを満たす場合は、ｘｉを１とし、Ｃ'をＣ'−ｂｊｉとする、
２）Ｃ'≧ｂｊｉを満たさない場合は、ｘｉを０とする、
という処理を逆算カウンタ変数ｉがｎから１になるまで繰り返し、得られたｘ＝（ｘ１，ｘ２，・・・，ｘｎ）を平文とする演算手段と
を備えることを特徴とする復号装置：
ただし、前記公開鍵行列Ａは、
超増加行列
【数２４】
0004200259.tif 000058
互いに素な自然数ｐとｑ、
乱数を要素とする行列
【数２５】
0004200259.tif 000059
ａｊｉ≡ｂｊｉ  （ｍｏｄ  ｐ）
ａｊｉ≡ｒｊｉ  （ｍｏｄ  ｑ）
を満たし、
０≦ｒｊｉ＜ｑ
【数２６】
0004200259.tif 000060
を満たすものとする（ただし、ｂｉｍａｘ＝ｍａｘ｛ｂ１ｉ，ｂ２ｉ，・・・，ｂｈｉ｝）。
【請求項１３】
公開鍵行列
【数２７】
0004200259.tif 000061
を生成する公開鍵生成装置であって、
超増加行列
【数２８】
0004200259.tif 000062
を記憶する手段と、
整数Ｌと、０≦ｒｉｊ＜｜Ｌ／ｎ｜を満たす乱数を要素とする行列
【数２９】
0004200259.tif 000063
と、乱数を要素とする行列
【数３０】
0004200259.tif 000064
とを記憶する手段と、
ｂｊｉ'＝Ｌｂｊｉ＋ｒｊｉとして、ｂｊｉ'を求め、
【数３１】
0004200259.tif 000065
を満たすＵと、互いに素な整数ｍとｗとを生成し、記憶するとともに、ａｊｉ＝ｗ（ｂｊｉ'＋ＵＲｊｉ）  ｍｏｄ  ｍを計算して、公開鍵行列Ａ＝（ａｊ１，ａｊ２，・・・，ａｊｎ）を生成する演算手段と
を備えることを特徴とする公開鍵生成装置：
ただし、
【数３２】
0004200259.tif 000066
を満たすものとする。
【請求項１４】
公開鍵行列Ａ＝（ａｊ１，ａｊ２，・・・，ａｊｎ）を用いて、平文ｘを暗号文Ｃに変換する暗号化装置であって、
前記公開鍵行列Ａを記憶する手段と、前記平文ｘを記憶する手段と、
【数３３】
0004200259.tif 000067
を計算する演算手段とを備えることを特徴とする暗号化装置：
ただし、ｃｉ∈｛ａ１ｉ，ａ２ｉ，・・・，ａｈｉ｝における、ａｊｉの添字ｊ＝ｊ（ｉ）は、以下のように定めるものとする。
１）変数ｎ１を初期値−１とする
２）変数ｉをｉ＝ｎから、ｉ＝１まで変化させて、次の処理を行なう。
ｎ１＝ｎ１＋ｘｉ，  ｊ＝（ｎ１  ｍｏｄ  ｈ）＋  １
また、公開鍵行列Ａは、
超増加行列
【数３４】
0004200259.tif 000068
整数Ｌ、
０≦ｒｉｊ＜｜Ｌ／ｎ｜を満たす乱数を要素とする行列
【数３５】
0004200259.tif 000069
乱数を要素とする行列
【数３６】
0004200259.tif 000070
ｂｊｉ'（ｂｊｉ'＝Ｌｂｊｉ＋ｒｊｉ）、
【数３７】
0004200259.tif 000071
を満たすＵ、
互いに素な整数ｍとｗ、とすると、
ａｊｉ＝ｗ（ｂｊｉ'＋ＵＲｊｉ）  ｍｏｄ  ｍを計算することにより算出されたものであり、
【数３８】
0004200259.tif 000072
を満たすものとする。
【請求項１５】
公開鍵行列Ａ＝（ａｊ１，ａｊ２，・・・，ａｊｎ）を用いて、暗号化された暗号文Ｃを平文ｘに変換する復号装置であって、
前記暗号文Ｃを記憶する手段と、
公開鍵行列Ａ＝（ａｊ１，ａｊ２，・・・，ａｊｎ）を生成するときに用いた超増加行列Ｂ＝（ｂｊ１，ｂｊ２，・・・，ｂｊｎ）と、ＵとＬとｍとｗとを記憶する手段と、
Ｃ'＝ｗ−１Ｃ  ｍｏｄ  ｍとし、Ｃ''＝Ｃ'  ｍｏｄ  Ｕとし、さらに、Ｃ'''＝｜Ｃ''／Ｌ｜とし、
ｂｊｉについて、
１）Ｃ'''≧ｂｊｉを満たす場合は、ｘｉを１とし、Ｃ'''をＣ'''−ｂｊｉとする、
２）Ｃ'''≧ｂｊｉを満たさない場合は、ｘｉを０とする、
という処理を逆算カウンタ変数ｉがｎから１になるまで繰り返し、得られたｘ＝（ｘ１，ｘ２，・・・，ｘｎ）を平文とする演算手段と
を備えることを特徴とする復号装置。
ただし、公開鍵行列Ａは、
超増加行列
【数３９】
0004200259.tif 000073
整数Ｌ、
０≦ｒｉｊ＜｜Ｌ／ｎ｜を満たす乱数を要素とする行列
【数４０】
0004200259.tif 000074
乱数を要素とする行列
【数４１】
0004200259.tif 000075
ｂｊｉ'（ｂｊｉ'＝Ｌｂｊｉ＋ｒｊｉ）、
【数４２】
0004200259.tif 000076
を満たすＵ、
互いに素な整数ｍとｗ、とすると、
ａｊｉ＝ｗ（ｂｊｉ'＋ＵＲｊｉ）  ｍｏｄ  ｍを計算することにより算出されたものであり、
【数４３】
0004200259.tif 000077
を満たすものとす。
【請求項１６】
公開鍵ａ＝（ａ１，ａ２，・・・，ａｎ）を生成する公開鍵生成装置であって、
ブロック化係数ｋと、ｎ０＝０と、０＜ｎ１＜ｎ２＜・・・＜ｎｋ＝ｎを満たすｋ個の正整数とを記憶する手段と、
以下に示す１）２）の処理をカウンタ変数ｊが１からｋになるまで繰り返し、得られたｂ（ｋ）を公開鍵ａ＝（ａ１，ａ２，・・・，ａｎ）とする演算手段と
を備えることを特徴とする公開鍵生成装置（Ｓ０＝０、ｂ（０）の初期値は空ベクトルとする）。
１）要素数ｎｊ−１のベクトルｂ（ｊ−１）を以下の処理により要素数ｎｊのベクトルｂ（ｊ−１）に伸張する。
１−１）Ｓｊ−１，ｂｎ（ｊ−１）＋１（ｊ−１），・・・，ｂｎｊ（ｊ−１）が超増加になるように、ｂｎ（ｊ−１）＋１（ｊ−１），・・・，ｂｎｊ（ｊ−１）を生成する。
１−２）生成したｂｎ（ｊ−１）＋１（ｊ−１），・・・，ｂｎｊ（ｊ−１）を、ベクトルｂ（ｊ−１）に付加して、ｂ（ｊ−１）＝（ｂ１（ｊ−１）＋，・・・，＋ｂｎｊ（ｊ−１））とする。
２）以下の処理を行ない、ベクトルｂ（ｊ−１）からベクトルｂ（ｊ）を生成して、記憶する。
【数４４】
0004200259.tif 000078
を満たす互いに素なｍｊとｗｊとを生成し記憶する。
ｂｉ（ｊ）＝ｗｊｂｉ（ｊ−１）  ｍｏｄ  ｍｊを算出して、ベクトルｂ（ｊ）とする。
【数４５】
0004200259.tif 000079
を算出して、記憶する。
【請求項１７】
公開鍵ａ＝（ａ１，ａ２，・・・，ａｎ）を用いて、平文ｘを暗号文Ｃに変換する暗号化装置であって、
前記公開鍵ａを記憶する手段と、前記平文ｘを記憶する手段と、
【数４６】
0004200259.tif 000080
を計算する演算手段とを備えることを特徴とする暗号化装置。
ただし、公開鍵ａは、
ブロック化係数ｋ、
ｎ０＝０、
０＜ｎ１＜ｎ２＜・・・＜ｎｋ＝ｎを満たすｋ個の正整数、とすると、
以下に示す１）２）の処理をカウンタ変数ｊが１からｋになるまで繰り返し、得られたｂ（ｋ）を公開鍵ａ＝（ａ１，ａ２，・・・，ａｎ）としたものとする（ただし、Ｓ０＝０、ｂ（０）の初期値は空ベクトル）。
１）要素数ｎｊ−１のベクトルｂ（ｊ−１）を以下の処理により要素数ｎｊのベクトルｂ（ｊ−１）に伸張する。
１−１）Ｓｊ−１，ｂｎ（ｊ−１）＋１（ｊ−１），・・・，ｂｎｊ（ｊ−１）が超増加になるように、ｂｎ（ｊ−１）＋１（ｊ−１），・・・，ｂｎｊ（ｊ−１）を生成する。
１−２）生成したｂｎ（ｊ−１）＋１（ｊ−１），・・・，ｂｎｊ（ｊ−１）を、ベクトルｂ（ｊ−１）に付加して、ｂ（ｊ−１）＝（ｂ１（ｊ−１）＋，・・・，＋ｂｎｊ（ｊ−１））とする。
２）以下の処理を行ない、ベクトルｂ（ｊ−１）からベクトルｂ（ｊ）を生成する。
【数４７】
0004200259.tif 000081
を満たす互いに素なｍｊとｗｊとを生成する。
ｂｉ（ｊ）＝ｗｊｂｉ（ｊ−１）  ｍｏｄ  ｍｊを算出して、ベクトルｂ（ｊ）とする。
【数４８】
0004200259.tif 000082
を算出する。
【請求項１８】
公開鍵行列
【数４９】
0004200259.tif 000083
を生成する公開鍵生成装置であって、
ブロック化係数ｋと、ｎ０＝０と、０＜ｎ１＜ｎ２＜・・・＜ｎｋ＝ｎを満たすｋ個の正整数とを記憶する手段と、
以下に示す１）２）の処理をカウンタ変数ｊが１からｋになるまで繰り返し、得られた行列Ｂ（ｋ）を公開鍵行列Ａ＝（ａｇ１，ａｇ２，・・・，ａｇｎ）とする演算手段と（ただし、１≦ｇ≦ｈ）を備えることを特徴とする公開鍵生成装置（Ｓ０＝０、Ｂ（０）は空行列とする）。
１）１行の要素数ｎｊ−１の行列Ｂ（ｊ−１）を以下の処理により１行の要素数ｎｊの行列Ｂ（ｊ−１）に伸張する。
１−１）（Ｓｊ−１，ｂｇ ｎ（ｊ−１）＋１（ｊ−１），・・・，ｂｇ ｎｊ（ｊ−１））が超増加行列になるように、ｂｇ ｎ（ｊ−１）＋１（ｊ−１），・・・，ｂｇ ｎｊ（ｊ−１）を生成する。
１−２）生成したｂｇ ｎ（ｊ−１）＋１（ｊ−１），・・・，ｂｇ ｎｊ（ｊ−１）を、行列Ｂ（ｊ−１）に付加して、Ｂ（ｊ−１）＝（ｂｇ １（ｊ−１）＋，・・・，＋ｂｇ ｎｊ（ｊ−１））とする。
２）以下の処理を行ない、行列Ｂ（ｊ−１）から行列Ｂ（ｊ）を生成して、記憶する。
【数５０】
0004200259.tif 000084
を満たす互いに素なｍｊとｗｊとを生成し記憶する。
ｂｇ ｉ（ｊ）＝ｗｊｂｇ ｉ（ｊ−１）  ｍｏｄ  ｍｊを算出して、行列Ｂ（ｊ）とする。
【数５１】
0004200259.tif 000085
を算出して、記憶する。
【請求項１９】
公開鍵行列Ａ＝（ａｇ１，ａｇ２，・・・，ａｇｎ）を用いて、平文ｘを暗号文Ｃに変換する暗号化装置であって、
前記公開鍵行列Ａを記憶する手段と、前記平文ｘを記憶する手段と、
【数５２】
0004200259.tif 000086
を計算する演算手段とを備えることを特徴とする暗号化装置：
ただし、ｃｉ∈｛ａ１ｉ，ａ２ｉ，・・・，ａｈｉ｝における、ａｇｉの添字ｇ＝ｇ（ｉ）は、以下のように定めるものとする。
１）変数ｎ１を初期値−１とする
２）変数ｉをｉ＝ｎから、ｉ＝１まで変化させて、次の処理を行なう。
ｎ１＝ｎ１＋ｘｉ，  ｇ＝（ｎ１  ｍｏｄ  ｈ）＋  １
ただし、公開鍵行列Ａは、
ブロック化係数ｋ、
ｎ０＝０、
０＜ｎ１＜ｎ２＜・・・＜ｎｋ＝ｎを満たすｋ個の正整数、とすると、
以下に示す１）２）の処理をカウンタ変数ｊが１からｋになるまで繰り返し、得られた行列Ｂ（ｋ）を公開鍵行列Ａ＝（ａｇ１，ａｇ２，・・・，ａｇｎ）としたものである（ただし、１≦ｇ≦ｈ、Ｓ０＝０、Ｂ（０）は空行列）。
１）１行の要素数ｎｊ−１の行列Ｂ（ｊ−１）を以下の処理により１行の要素数ｎｊの行列Ｂ（ｊ−１）に伸張する。
１−１）（Ｓｊ−１，ｂｇ ｎ（ｊ−１）＋１（ｊ−１），・・・，ｂｇ ｎｊ（ｊ−１））が超増加行列になるように、ｂｇ ｎ（ｊ−１）＋１（ｊ−１），・・・，ｂｇ ｎｊ（ｊ−１）を生成する。
１−２）生成したｂｇ ｎ（ｊ−１）＋１（ｊ−１），・・・，ｂｇ ｎｊ（ｊ−１）を、行列Ｂ（ｊ−１）に付加して、Ｂ（ｊ−１）＝（ｂｇ １（ｊ−１）＋，・・・，＋ｂｇ ｎｊ（ｊ−１））とする。
２）以下の処理を行ない、行列Ｂ（ｊ−１）から行列Ｂ（ｊ）を生成する。
【数５３】
0004200259.tif 000087
を満たす互いに素なｍｊとｗｊとを生成する。
ｂｇ ｉ（ｊ）＝ｗｊｂｇ ｉ（ｊ−１）  ｍｏｄ  ｍｊを算出して、行列Ｂ（ｊ）とする。
【数５４】
0004200259.tif 000088
を算出する。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、暗号技術に係り、特に、暗号化、復号化速度が速く、しかも安全性が高い公開鍵暗号方式に関する。
【０００２】
【従来の技術】
コンピュータネットワークを利用したデータ通信における代表的な暗号化方式として、共通鍵暗号法と公開鍵暗号法とがある。共通鍵暗号法は、暗号化と復号化とで同じ暗号鍵を使う方法である。公開鍵暗号法は、暗号化と復号化とで違う暗号鍵を使う方法である。公開鍵暗号法では、一方の暗号鍵で暗号化したデータは、もう一方の鍵を使わないと復号できない。このため一方の鍵を公開し、他方の鍵を秘密にしておく。
【０００３】
一般に、共通鍵暗号法は、暗号化、復号化の処理速度が速いが、通信相手に安全な方法で暗号鍵を渡すことが難しい。一方の公開鍵暗号方式は、片方の鍵は公開することができるので、相手に暗号鍵を渡すことは非常に楽である。
【０００４】
公開鍵暗号方式としては、ＲＳＡ方式が代表的で、よく知られている。しかし、ＲＳＡ方式は、暗号化、復号化とも共通鍵方式に比べ、１０００倍程度処理速度が遅い。このため、コンピュータネットワークを利用したデータ通信においては、共通鍵の受け渡し、あるいは、比較的少量のデータ伝送等に使われている程度にとどまっている。
【０００５】
公開鍵暗号方式で、処理速度が速い方式としてＭｅｒｋｌｅ−Ｈｅｌｌｍａｎによって提案されたナップザック暗号方式（ＭＨ型ナップザック暗号）がある（R. C. Merkle and M. E. Hellman : "Hiding information and signatures in trapdoor knapsacks", IEEE Trans . Inform. Theory, vol. IT-24, no.5, pp.525-530 (1978)）。ＭＨ型ナップザック暗号は、秘密鍵として、整数を要素とする超増加ベクトルｂ＝（ｂ1，ｂ2，...，ｂn）と、
【０００６】
【数２７】
0004200259.tif 000002
【０００７】
の制約を満たす、互いに素な関係を有する乗数ｗと法ｍとを用いる。
【０００８】
そして、公開鍵として、ベクトルｂにモジュラ乗算を施して得られるベクトルａ＝（ａ1，ａ2，...，ａn）を利用する。すなわちａとｂとの要素間には次の関係がある。
【０００９】
ａi＝ｗｂi  ｍｏｄ  ｍ
ナップザック暗号における暗号化は、ｎビットの平文ｘ＝（ｘ1，ｘ2，...，ｘn）を、次の式にしたがって整数Ｃに変換し、このＣを暗号文とする。
【００１０】
【数２８】
0004200259.tif 000003
【００１１】
ａiは、超増加ベクトルでないため、一般に、このナップザック暗号を解くのは容易でない。
【００１２】
暗号文Ｃの復号化は、Ｃを逆モジュラ乗算して、
Ｃ'＝ｗ-1Ｃ  ｍｏｄ  ｍ
とする。すると
【００１３】
【数２９】
0004200259.tif 000004
【００１４】
となり、易しいナップザック問題を解くことによって平文を得ることができる（ｂiが超増加ベクトルの場合、ナップザック暗号は容易に解ける）。
【００１５】
このように、ナップザック暗号は、計算処理の負荷が少ないため、暗号化、復号化とも、共通鍵暗号方式と同等の処理速度を得ることができる。
【００１６】
しかし、ナップザック暗号は、Ｓｈａｍｉｒによって提案された解読法（Ｓ法）が知られており、今では安全な暗号法ではないとされている（(A. Shamir : "A polynomial time algorithm for breaking the basic Merkle-Hellman cryptosystems", IEEE Trans. Inform. Theory, vol. IT-30, no.5, pp.699-704 (1982).）。
【００１７】
【発明が解決しようとする課題】
Ｓ法は、ｗ，ｍを知らない解読者が、Ｗ，Ｍというパラメータを見付け、公開鍵（ａ1，ａ2，...，ａn）を、超増加ベクトル（ｂ1'，ｂ2'，...，ｂn'）に変換することによって、復号を易しいナップザック問題にしてしまうものである。
【００１８】
すなわち、公開鍵ａにモジュラ乗算を施して得られるベクトルであって、超増加であるｂ'を見出すものである。このとき一般にはｂとｂ'とは異なるが、ｂ'が超増加であれば十分である。したがって、本来の秘密超増加ベクトルｂでなくても、Ｗｂi'  ｍｏｄ  Ｍ＝ａiとなる、超増加ベクトル（ｂ1'，ｂ2'，...，ｂn'）を得ることができれば、
【００１９】
【数３０】
0004200259.tif 000005
【００２０】
という、易しいナップザック問題を解くことにより、平文ｘを得ることができる。
【００２１】
Ｓ法は、公開鍵ベクトルａが、秘密鍵である超増加ベクトルｂにモジュラ乗算を施して得られるものであるときに適用できるものである。すなわち、Ｓ法によってＭＨ型ナップザック暗号が解読されるのは、公開鍵ベクトルａと秘密鍵ベクトルｂとが、単純なモジュラ乗算の関係を有しているためと考えられる。
【００２２】
本発明の目的は、Ｓｈａｍｉｒ法による攻撃に強いナップザック暗号の公開鍵を生成する装置、および、この公開鍵を用いて暗号文を作成する装置と、この暗号文を復号する装置を提供することにある。
【００２３】
また、本発明の目的は、暗号化、復号化の処理を速く行なえる公開鍵方式の暗号を取り扱う装置を提供することにある。
【００２４】
【課題を解決するための手段】
上記課題を解決するため、本発明の第１の態様によれば、
公開鍵ａ＝（ａ1，ａ2，...，ａn）を生成する公開鍵生成装置であって、
超増加ベクトルｂ＝（ｂ1，ｂ2，...，ｂn）を記憶する手段と、互いに素な自然数ｐとｑとを記憶する手段と、乱数を要素とするベクトルｒ＝（ｒ1，ｒ2，...，ｒn）を記憶する手段と、これらの値を参照して、
ａi≡ｂi  （ｍｏｄ  ｐ）
ａi≡ｒi  （ｍｏｄ  ｑ）
を満たすａ＝（ａ1，ａ2，...，ａn）を生成する演算手段と
を備えることを特徴とする公開鍵生成装置が提供される。
【００２５】
ただし、
０≦ｒi＜ｑ
【００２６】
【数３１】
0004200259.tif 000006
【００２７】
を満たすものとする。
【００２８】
上記課題を解決するため、本発明の第２の態様によれば、
本発明の第１の態様の公開鍵ａ＝（ａ1，ａ2，...，ａn）を用いて、平文ｘを暗号文Ｃに変換する暗号化装置であって、
前記公開鍵ａを記憶する手段と、前記平文ｘを記憶する手段と、
【００２９】
【数３２】
0004200259.tif 000007
【００３０】
を計算する演算手段とを備えることを特徴とする暗号化装置が提供される。
【００３１】
さらに、本発明の第３の態様によれば、
本発明の第１の態様の公開鍵ａ＝（ａ1，ａ2，...，ａn）を用いて、暗号化された暗号文Ｃを平文ｘに変換する復号装置であって、
前記暗号文Ｃを記憶する手段と、
公開鍵ａ＝（ａ1，ａ2，...，ａn）を生成するときに用いた超増加ベクトルｂ＝（ｂ1，ｂ2，...，ｂn）と、ｐとを記憶する手段と、
Ｃ'＝Ｃ  ｍｏｄ  ｐ
を算出し、
下記１）２）の処理を変数ｉをｎから１まで繰り返し、得られたｘ＝（ｘ1，ｘ2，...，ｘn）を平文とする演算手段と
を備えることを特徴とする復号装置が提供される。
【００３２】
１）Ｃ'≧ｂiを満たす場合は、ｘiを１とし、Ｃ'をＣ'−ｂiとする
２）Ｃ'≧ｂiを満たさない場合は、ｘiを０とする
【００３３】
【発明の実施の形態】
本発明の実施の形態について、図面を参照して説明する。以下においては、本発明を電子計算機に適用した場合について説明する。
【００３４】
本発明を適用する電子計算機は、中央処理装置、主記憶装置、補助記憶装置、外部入出力装置等を備える一般的な電子計算機とすることができる。また、ネットワークを介して外部と通信を行なえる構成としてもよい。
【００３５】
本実施の形態において、電子計算機は公開鍵生成装置１００として機能する。この公開鍵生成装置１００は、本発明の処理を実現させるためのプログラムを、電子計算機の主記憶装置に格納し、中央処理装置がプログラムにしたがって動作を行うことにより実現することができる。また、公開鍵生成装置１００等は、以下に説明する処理において、乗算、ｍｏｄ演算（剰余算）、加算等の演算を行なう必要があるが、これらの演算は、乗算器、加算器、除算器等を用いてハードウェアで行なうようにしてもよいし、ソフトウェアで実行させるようにしてもよい。
【００３６】
公開鍵生成装置１００は、公開鍵生成のための演算を行なう演算部１０１と、秘密鍵を保持する秘密鍵保持部１０２と、作業用変数、乱数等を一時的に保持する作業用記憶部１０３とを備えている。演算部１０１は中央処理装置によって実現することができ、秘密鍵保持部１０２は、例えば、主記憶装置、外部記憶装置によって実現することができる。作業用記憶１０３は、主記憶装置等によって実現することができる。演算部１０１が生成した公開鍵は、主記憶装置、外部記憶装置等に出力することができる。
【００３７】
また、電子計算機は、生成された公開鍵を用いて、平文を暗号化する暗号化装置２００として機能することもできる。
【００３８】
暗号化装置２００は、暗号化のための演算を行なう演算部２０１と、暗号化するための平文を保持する平文保持部２０２と、上述の公開鍵生成装置によって生成された公開鍵を保持する公開鍵保持部２０３とを備えている。演算部２０１は中央処理装置によって実現することができ、平文保持部２０２と公開鍵保持部２０３とは、例えば、主記憶装置、外部記憶装置によって実現することができる。演算部２０１が暗号化した暗号文は、主記憶装置、外部記憶装置等に出力することができる。
【００３９】
さらに、電子計算機は、秘密鍵を用いて、暗号文を復号する復号装置３００として機能することもできる。
【００４０】
復号装置３００は、復号のための演算を行なう演算部３０１と、上述の暗号化装置で生成された暗号文を保持する暗号文保持部３０２と、この暗号文を生成するときに使用した公開鍵を生成した秘密鍵を保持する秘密鍵保持部３０３とを備えている。演算部３０１は中央処理装置によって実現することができ、秘密鍵保持部３０２と暗号文保持部３０３とは、例えば、主記憶装置、外部記憶装置によって実現することができる。演算部３０１が復号した平文は、主記憶装置、外部記憶装置等に出力することができる。
【００４１】
本発明による公開鍵生成装置１００と暗号化装置２００と復号装置３００とは、例えば、インターネットにおける電子メールの送受信時に使用することができる。図１はこのときの構成を説明するためのブロック図である。
【００４２】
電子メールの受け手１０は、秘密鍵を用いて公開鍵生成装置１００で生成した公開鍵を公開ファイル等に置くことにより公開する。電子メールの送り手２０は、この公開鍵を入手し、暗号化装置２００を用いて電子メールを暗号化した後、受け手に送信する。この電子メールを受信した受け手は、秘密鍵を用いて復号装置３００で、暗号化された電子メールを復号することができる。このようにすることにより、安全性の高い電子メールの送受信を行うことができる。もちろん、本発明の適用例は、これらに限られるものではない。
【００４３】
以下の実施形態において、秘密鍵は超増加ベクトルｂ＝（ｂ1，ｂ2，...，ｂn）を用いることとする。ここで、超増加ベクトルとは、ｂi＞ｂ1＋ｂ2＋...＋ｂi-1が成り立つベクトルをいう。
【００４４】
また、公開鍵生成装置１００が生成または受け付ける超増加ベクトル、乱数等のパラメータのサイズは、特に限定はされないが、例えば、ｎを１００程度としし、各パラメータを２００ビット〜３００ビットとすることができる。なお、本発明によれば、これらのサイズを大きくすることにより、当然、安全性を高めることができる。しかも、この場合でも、暗号化、復号とも処理速度がほとんど低下しない。
【００４５】
（１．第１実施形態）
本発明の、第１実施形態は、中国式剰余定理を用いて、公開鍵を生成する装置に係るものである。ここで、中国式剰余定理とは、ｎ1，...ｎkが互いに素であるとすると、次の連立合同式
ｘ≡ａ1（ｍｏｄ  ｎ1）
・・・
ｘ≡ａk（ｍｏｄ  ｎk）
は、０≦ｘ＜ｎ＝ｎ1・・・ｎkの範囲で一意的解を持ち、特にｎ1＝ｐ、ｎ2＝ｑ、ｋ＝２のとき、
ｘ＝ａ1ｑｑ-1＋ａ2ｐｐ-1  ｍｏｄ  ｐｑ
が成り立つことをいう。ただし、ｐｐ-1≡１（ｍｏｄ  ｑ）、ｑｑ-1≡１（ｍｏｄ  ｐ）である。
【００４６】
（１．１公開鍵生成）
第１実施形態における公開鍵生成装置１００の処理について説明する。図２は、このときの処理の流れを説明する図である。
【００４７】
秘密鍵保持部１０２は、自然数ｐと超増加ベクトルｂとを格納する。
【００４８】
作業用記憶部１０３は、自然数ｑと、適当な大きさの乱数のベクトルｒ＝（ｒ1，ｒ2，...，ｒn）とを格納する。
【００４９】
ただし、ｐとｑとは互いに素である。また、ｒiは整数で、０≦ｒi＜ｑを満たし、ｐは、
【００５０】
【数３３】
0004200259.tif 000008
【００５１】
を満たすものとする。
【００５２】
なお、ｐとｑとは、互いに素となるように演算部１０１で生成するようにしてもよいし、入力装置を介して入力するようにしてもよい。乱数ｒiについても、演算部１０１で生成するようにしてもよいし、入力装置を介して入力するようにしてもよい。
【００５３】
演算部１０１は、秘密鍵保持部１０２に格納してある秘密鍵と作業用記憶部１０３に格納している乱数とを用いて、
ａi≡ｂi  （ｍｏｄ  ｐ）
ａi≡ｒi  （ｍｏｄ  ｑ），  １≦ｉ≦ｎ
を満たすａ＝（ａ1，ａ2，...，ａn）を作成する。そして、このａを公開鍵として出力する。
【００５４】
なお、上記の２式を満たすａiは、中国式剰余定理（Ｃｈｉｎｅｓｅ  Ｒｅｍａｉｎｄｅｒ  Ｔｈｅｏｒｅｍ）によって、
ａi≡ｂiｑｑ-1＋ｒiｐｐ-1  （ｍｏｄ  ｐｑ）
と表され、０≦ａi＜ｐｑの範囲で一意に求めることができる。ただし、ｐｐ-1≡１（ｍｏｄ  ｑ）、ｑｑ-1≡１（ｍｏｄ  ｐ）である。
【００５５】
上記の演算によって求められたａは、超増加ベクトルｂからモジュラー乗算によって得られるベクトルではない。このため、本実施形態に対してＳ法は適用できないものと考えられる。
【００５６】
（１．２暗号化）
第１実施形態における暗号化装置２００の処理について説明する。図３は、このときの処理の流れを説明する図である。
【００５７】
平文保持部２０２は、ｎビットの平文ｘ＝（ｘ1，ｘ2，...，ｘn）を保持する。ただし、ｘiは０または１である。
【００５８】
公開鍵保持部２０３は、公開鍵生成装置１００によって作成された公開鍵ａ＝（ａ1，ａ2，...，ａn）を保持する。
【００５９】
演算部２０１は、
【００６０】
【数３４】
0004200259.tif 000009
【００６１】
を計算し、Ｃを暗号文として出力する。
【００６２】
このように、本実施例において、暗号化は加算のみによって行うことができる。このため、本装置における暗号化の処理は、べき乗剰余演算が必要なＲＳＡ方式を用いた装置に比して、極めて高速であるといえる。
【００６３】
（１．３復号）
第１実施形態における復号装置３００の処理について説明する。図４は、このときの処理の流れを説明する図である。
【００６４】
暗号文保持部３０２は、暗号化装置２００が作成した暗号文Ｃを格納する。秘密鍵保持部３０３は、暗号文Ｃを生成した公開鍵ａを生成するときに使用した、自然数ｐと超増加ベクトルｂとを格納する。
【００６５】
演算部３０１は、Ｃ  ｍｏｄ  ｐを算出する。これをＣ'とすると、Ｃ'は、ｂを用いて、
【００６６】
【数３５】
0004200259.tif 000010
【００６７】
と表せる。ｂは超増加ベクトルであるから、これは易しいナップザック暗号である。このため、平文ｘ＝（ｘ1，ｘ2，...，ｘn）を容易に求めることができる。
【００６８】
このときの易しいナップザック暗号を解く処理について、図４に示すフロー図を参照して説明する。
【００６９】
演算部３０１は、変数ｉをｎから１まで変化させて、以下の処理を行なう。まず、Ｃ'≧ｂiを満たすかどうかを調べる（Ｓ１０１）。そして、Ｃ'≧ｂiを満たす場合は、ｘiを１とし、Ｃ'をＣ'−ｂiとする（Ｓ１０２）。Ｃ'≧ｂiを満たさない場合は、ｘiを０とする（Ｓ１０３）。この結果得られたｘ＝（ｘ1，ｘ2，...，ｘn）が求めるべき平文である。
【００７０】
復号装置３００は、この処理によって得られたｘを、復号した平文として出力する。
【００７１】
このように、本実施例において、復号は比較と減算のみによって行うことができる。このため、本装置における復号の処理は、べき乗剰余演算が必要なＲＳＡ方式を用いた装置に比して、極めて高速であるといえる。
【００７２】
（２．第２実施形態）
本発明の第２実施形態は、超増加ベクトルｂに対して、下位ビットおよび上位ビットに乱数を付加して超増加性を隠し、その後、ｗとｍとでモジュラー乗算変換を施して公開鍵を生成する装置に係るものである。
【００７３】
（２．１公開鍵生成）
第２実施形態における公開鍵生成装置１００の処理について説明する。なお、図面の符号は第１実施形態と同じものを用いる。
【００７４】
秘密鍵保持部１０２は、超増加ベクトルｂと、適当な大きさの整数Ｌとを格納する。
【００７５】
作業用記憶部１０３は、乱数のベクトルｒ＝（ｒ1，ｒ2，...，ｒn）を格納する。
【００７６】
ただし、０≦ｒi＜｜Ｌ／ｎ｜を満たすものとする。ここで、｜Ｌ／ｎ｜は、Ｌ／ｎを超えない最大の整数である。すなわち、Ｌは、乱数の大きさを制限するために用いられる。
【００７７】
なお、整数Ｌは、演算部１０１で生成するようにしてもよいし、入力装置を介して入力するようにしてもよい。乱数ｒiについても、演算部１０１で生成するようにしてもよいし、入力装置を介して入力するようにしてもよい。
【００７８】
次に演算部１０１の動作について図５に示すフロー図を参照して説明する。
【００７９】
演算部１０１は、
ｂi'＝Ｌｂi＋ｒi
として、ｂ'＝（ｂ1'，ｂ2'，...，ｂn'）を求め、作業用記憶部１０３に格納する（Ｓ２０１）。
【００８０】
次に演算部１０１は、
【００８１】
【数３６】
0004200259.tif 000011
【００８２】
を満たすような、整数Ｕを生成し、秘密鍵保持部１０２に格納する（Ｓ２０２）。
【００８３】
そして、演算部１０１は、適当な大きさの乱数を要素とするベクトルＲ＝（Ｒ1，Ｒ2，...，Ｒn）を生成し、作業用記憶部１０３に格納する（Ｓ２０３）。なお、乱数ベクトルＲは、乱数ベクトルｒ同様に、あらかじめ用意して作業用記憶部１０３に格納しておいてもよい。
【００８４】
演算部１０１は、次の関係を満たす、互いに素な整数ｍとｗとを生成し、秘密鍵保持部１０２に格納する（Ｓ２０４）。
【００８５】
【数３７】
0004200259.tif 000012
【００８６】
演算部１０１は、ａi＝ｗ（ｂi'＋ＵＲi）  ｍｏｄ  ｍを計算し、ａ＝（ａ1，ａ2，...，ａn）を作成する。そして、このａを公開鍵として出力する（Ｓ２０５）。
【００８７】
上記の演算によって求められたａは、超増加ベクトルｂからモジュラ乗算によって得られるベクトルではない。このため、本実施形態に対してＳ法は適用できないものと考えられる。
【００８８】
（２．２暗号化）
第２実施形態における暗号化装置２００の処理は、第１実施形態と同じである。
【００８９】
（２．３復号）
第２実施形態における復号装置３００の処理について説明する。
【００９０】
暗号文保持部３０２は、暗号文Ｃを格納する。秘密鍵保持部３０３は、暗号文Ｃを生成した公開鍵ａを生成するときに使用した、互いに素な整数ｗとｍと、Ｕと、Ｌと、超増加ベクトルｂとを格納する。
【００９１】
演算部３０１は、ｗ-1Ｃ  ｍｏｄ  ｍを求め、Ｃ'とする。ここで、Ｃ'は、
【００９２】
【数３８】
0004200259.tif 000013
【００９３】
である。
【００９４】
演算部３０１は、次にＣ'  ｍｏｄ  Ｕを求め、Ｃ''とする。ここで、Ｃ''は、
【００９５】
【数３９】
0004200259.tif 000014
【００９６】
である。また、ｂi'＝Ｌｂi＋ｒiである。
【００９７】
さらに、演算部３０１は、｜Ｃ''／Ｌ｜を求め、Ｃ'''とする。ここで、Ｃ'''は、
【００９８】
【数４０】
0004200259.tif 000015
【００９９】
となる。ｂは超増加ベクトルであるから、これは易しいナップザック暗号である。このため、第１実施形態で示した処理を行うことにより、平文ｘ＝（ｘ1，ｘ2，...，ｘn）を容易に求めることができる。復号装置３００は、ｘを求め、得られたｘを復号した平文として出力する。
【０１００】
本実施例においても、簡単な演算で復号することができるため、第１実施例同様に、ＲＳＡ方式に比して、極めて高速に復号処理を行うことができる。
【０１０１】
（３．第３実施形態）
本発明の第３実施形態は、超増加ベクトルｂに対し、多重にモジュラ乗算変換を施して、公開鍵を生成する装置に係るものである。本実施形態に係る装置は、超増加ベクトルｂのｎ個の要素すべてを同一のｗとｍとでモジュラ乗算変換するのではなく、ｎ個の要素を、いくつかのブロックに分割する。そして、第１のブロックから始め、ブロックを追加する毎に、別のｗiとｍiとでモジュラ乗算していく。すなわち、０＜ｎ1＜ｎ2＜...＜ｎk＝ｎを満たすｋ個の正整数を定めておき、まず、ｎ1個の要素からなる超増加ベクトルを作る。これにモジュラ乗算変換を施し、次いで、それらｎ1個の要素の和と次のｎ2個−ｎ1個の要素からなる超増加ベクトルを作り、これにモジュラ乗算変換を施す。そして、このような処理をｋ回繰り返すようにする。これにより、最初のブロックはｋ回のモジュラ乗算変換を、第２のブロックはｋ−１回のモジュラ乗算変換を施され、最後の第ｋブロックは１回のモジュラ乗算変換を施される。
【０１０２】
（３．１公開鍵生成）
第３実施形態における公開鍵生成装置１００の処理について説明する。
【０１０３】
秘密鍵保持部１０２は、ブロック化係数ｋと、０＜ｎ1＜ｎ2＜...＜ｎk＝ｎを満たすｋ個の正整数と、超増加ベクトルｂ（ただし、ｂ＝（ｂ1，ｂ2，...，ｂn1））と、次の制約を満たす、互いに素な整数ｍ1とｗ1とを格納する。
【０１０４】
ブロック化係数ｋと、ｋ個の正整数とは、演算部１０１で生成するようにしてもよいし、入力装置を介して入力するようにしてもよい。
なお、以下の説明において、活字の制約上「ｎ1」を「ｎ１」のように表す場合があるものとする。
【０１０５】
【数４１】
0004200259.tif 000016
【０１０６】
演算部１０１は、超増加ベクトルｂ＝（ｂ1，ｂ2，...，ｂn1）に対して、ｗ1とｍ1とを用いてモジュラ乗算を施し、
ｂ(1)＝（ｂ1(1)，ｂ2(1)，...，ｂn1(1)）
を生成する。
【０１０７】
次に、演算部１０１は、Ｓ1＝ｂ1(1)＋ｂ2(1)＋...＋ｂn1(1)として、Ｓ1を秘密鍵保持部１０１に格納するとともに、（Ｓ1，  ｂn1+1(1)，ｂn1+2(1)，...，ｂn2(1)）が超増加ベクトルになるように、ｂn1+1(1)，ｂn1+2(1)，...，ｂn2(1)を生成して、秘密鍵保持部１０１に格納する。そして、ｂ(1)を新たに、ｂ(1)＝（ｂ1(1)，ｂ2(1)，...，ｂn1(1)，｜ｂn1+1(1)，ｂn1+2(1)，...，ｂn2(1)）とする。なお、「｜」は、ブロックの区切りを便宜的に表している。
【０１０８】
演算部１０１は、次の制約を満たす互いに素な整数ｍ2とｗ2とを生成し、秘密鍵保持部１０２に格納する。
【０１０９】
【数４２】
0004200259.tif 000017
【０１１０】
そして、演算部１０１は、ｂ(1)に対して、ｍ2とｗ2とを用いて２回目のモジュラ乗算変換を施し、
ｂ(2)＝（ｂ1(2)，ｂ2(2)，...，ｂn1(2)，｜ｂn1+1(2)，ｂn1+2(2)，...，ｂn2(2)）
を生成する。
【０１１１】
すなわち、ｊ回のモジュラ乗算変換を施した結果、要素がｎj個のｂ(j)＝（ｂ1(j)，...，ｂn1(j)，｜...｜ｂn(j-1)+1(j)，...，ｂnj(j)）が得られているとする。演算部１０１は、この場合に、Ｓj＝ｂ1(j)＋ｂ2(j)＋...＋ｂnj(j)としたときに、（Ｓj，  ｂnj+1(j)，ｂnj+2(j)，...，ｂn(j+1)(j)）が超増加ベクトルになるように、ｂnj+1(j)，ｂnj+2(j)，...，ｂn(j+1)(j)を生成して、秘密鍵保持部１０１に格納する。そして、ｂ(j)を新たに、ｂ(j)＝（ｂ1(j)，...，ｂn1(j)，｜...｜ｂnj+1(j)，...，ｂn(j+1)(j)）とする。
【０１１２】
演算部１０１は、次の制約を満たす互いに素な整数ｍj+1とｗj+1とを生成し、秘密鍵保持部１０２に格納する。
【０１１３】
【数４３】
0004200259.tif 000018
【０１１４】
そして、演算部１０１は、ｂ(j)に対して、ｍj+1とｗj+1とを用いてｊ＋１回目のモジュラ乗算変換を施し、
ｂ(j+1)＝（ｂ1(j+1)，...，ｂn1(j+1)｜...｜ｂnj+1(j+1)，...，ｂn(j+1)(j+1)）
を生成する。
【０１１５】
演算部１０１は、以上の処理をｊ＝ｋ−１になるまで繰り返す。その結果ｂ(k)が得られる。そして、
ａi＝ｂi(k)      ｉ＝１，２，...，ｎ
とし、ａ＝（ａ1，ａ2，...，ａn）を作成する。そして、このａを公開鍵として出力する。
【０１１６】
（３．２暗号化）
第３実施形態における暗号化装置２００の処理は、第１実施形態と同じである。
【０１１７】
（３．３復号）
第３実施形態における復号装置３００の処理について説明する。
【０１１８】
暗号文保持部３０２は、暗号文Ｃを格納する。秘密鍵保持部３０３は、暗号文Ｃを生成した公開鍵ａを生成するときに使用した、互いに素な整数ｗiとｍiの組と、Ｓiと超増加ベクトルｂ(i)と、ブロック化係数ｋとを格納する。
【０１１９】
まず、演算部３０１は、
Ｃ(1)＝ｗk-1Ｃ  ｍｏｄ  ｍk
とする。この演算によって、第ｋ回目のモジュラ演算がはずれるので、
【０１２０】
【数４４】
0004200259.tif 000019
【０１２１】
となる。このとき、Ｓk-1，ｂn(k-1)+1(k-1)，...，ｂnk(k-1)が、超増加になっているので、演算部３０１は、ｘn，ｘn-1，...，ｘn(k-1)+1までを、第１実施例で示した易しいナップザック暗号を解く処理を行うことにより、復号することができる。
【０１２２】
次に、演算部３０１は、
【０１２３】
【数４５】
0004200259.tif 000020
【０１２４】
として、第ｋ−１回目のモジュラ乗算をはずす。ここで、
【０１２５】
【数４６】
0004200259.tif 000021
【０１２６】
としているのは、すでに復号を終えた部分を、暗号文Ｃから引く必要があるからである。
【０１２７】
そして、演算部３０１は、Ｃ(2)に対し、易しいナップザック暗号を解く処理を行うことにより、ｘn(k-1)，...，ｘn(k-2)+1までを、復号することができる。
【０１２８】
以下同様にして、演算部３０１は、ｘ1まで復号することができる。演算部３０１は、上述の処理の結果得られたｘ＝（ｘ1，...，ｘn）を復号した平文として出力する。
【０１２９】
（変形）
上述の第１〜第３実施形態によって、Ｓｈａｍｉｒ法による攻撃に強いと考えられるナップザック暗号を生成することができる。
【０１３０】
しかし、ＭＨ型ナップザック暗号は、Ｓｈａｍｉｒ法以外にも、Ｌａｇａｒｉａｓ−Ｏｄｌｙｚｋｏ法（ＬＯ法）と呼ばれる解読法が知られている（J.C.Lagarias and A.M. Odlyzko:"Solving low density subset sum problems", J. ACM, vol. 32, pp.229-246 (1985)）。このため、上述の第１〜第３実施形態を実際の暗号化処理に使用するためには、ＬＯ法による攻撃に対しても強くなければならない。
【０１３１】
ＬＯ法は、ナップザック暗号の解読を、公開鍵ａに関係して定められるベクトルを基底とする格子における短いベクトルの探索に帰着させるものである。短いベクトルを探し出すアルゴリズムとしては、既知のＬＬＬ法（A. K. Lenstra, H. W. Lenstra, and L. Lovasz, "Factoring polynomials with rational coefficients", Mathematische Annalen, vol.261, pp.515-534, 1982）を使うことができる。これにより短いベクトルが見つかれば、そのベクトルが平文に対応している可能性が非常に高いというものである。このため、平文に対応するベクトルと同等以下の短いベクトルがたくさん存在すれば、平文がこれらの中に紛れて、見つかりにくくなり、ＬＯ法による攻撃に対して強くなると考えられる。そして、この考えを用いた暗号方式が、提案されている（林  彬:  “ナップザック暗号の改良の試み”，信学技法， Vol. ISEC96-4(1996-05)）。
【０１３２】
提案された方式は、通常のナップザック暗号の公開鍵ａが、１つのベクトルａ＝（ａ1，ａ2，...，ａn）であるのに対し、公開鍵をｈ行ｎ列の行列Ａとするものである。この行列は、ｈ行ｎ列の秘密鍵行列Ｂ＝（ｂji）からモジュラ乗算によって作られる。ただし、行列Ｂは、第ｉ列のどの要素も第１〜第ｉ−１列の各最大要素の和よりも大きいものとする（この意味で超増加である）。
【０１３３】
すなわち、
【０１３４】
【数４７】
0004200259.tif 000022
【０１３５】
としたときに、行列Ｂの要素ｂjiは、以下の性質を有する。
【０１３６】
【数４８】
0004200259.tif 000023
【０１３７】
【数４９】
0004200259.tif 000024
【０１３８】
そして、通常のナップザック暗号と同様に、互いに素な乗数ｗと法ｍとを定め、ａji＝ｗｂji  ｍｏｄ  ｍによって、公開鍵行列
【０１３９】
【数５０】
0004200259.tif 000025
【０１４０】
を生成する。すなわち、公開鍵行列は、公開鍵ベクトルを生成するモジュラ乗算を各行ごとに繰り返すことにより作成される。
【０１４１】
公開鍵行列Ａを用いた暗号化は、平文ｘ＝（ｘ1，...，ｘn）に対して、次の操作を施して、整数Ｃを求め、このＣを暗号文とする。
【０１４２】
【数５１】
0004200259.tif 000026
【０１４３】
ただし、ｃi∈｛ａ1i，ａ1i，...，ａhi｝における、ａjiの添字ｊ＝ｊ（ｉ）は、以下のように定める。
【０１４４】
まず、変数ｎ１を初期値−１とする。そして、変数ｉをｉ＝ｎから、ｉ＝１まで変化させて、次の処理を行なう。
【０１４５】
ｎ１＝ｎ１＋ｘi，  ｊ＝（ｎ１  ｍｏｄ  ｈ）＋  １
すなわち、ｘnに適用するａ1nから始まって、列方向には、各ビットごとにｎから１方向に移動し、行方向には、各ビットに１が現れるたびに一つ下の行へ（最下位行の次は、１行目に戻る）下がっていくようにａjiが選択される。
【０１４６】
図６は、この処理の一例を説明するための図である。本図において、ｘn-4，ｘn-3，ｘn-2，ｘn-1，ｘn＝（０，１，０，０，１）とする。
【０１４７】
まず、公開鍵行列Ａのａ1nとｘnとを用いてａ1nｘnの乗算を行なう。ここで、Ｘnは１であるので、ｎ−１列目では、１行下がって、ａ2(n-1)を用いてｘn-1ａ2(n-1)の乗算を行なう。ｘn-1は０であるので、ｎ−２列目では、行の移動は行なわず、ｘn-2ａ2(n-1)の乗算を行なう。以下同様にして、ｘiに１が現れるたびに、１行ずつ下がって乗算を行なう。これをｘ1まで繰り返し、乗算結果の和を暗号文Ｃとする。
【０１４８】
上記の処理により作成された暗号文Ｃの復号は、基本的にＭＨ型ナップザック暗号と同じであるが、秘密鍵行列Ｂの何行目の要素を比較して、引いていくかを判断しなければならない。
【０１４９】
すなわち、Ｃを逆モジュラ乗算して、
Ｃ'＝ｗ-1  ｍｏｄ  ｍ
とする。
【０１５０】
そして、秘密鍵行列Ｂのｂ1nは、ｘnに適用されるのは明らかであるため、ｊを１とし、変数ｉをｉ＝ｎから、ｉ＝１まで変化させて、次の処理を行なう。
【０１５１】
Ｃ'≧ｂjiを満たす場合は、ｘiを１とし、Ｃ'＝Ｃ'−ｂjiとする。そして、ｊ＝ｊ  ｍｏｄ  ｈ＋１として、秘密鍵行列の採用する要素の行を１行下に移動する。
【０１５２】
Ｃ'≧ｂjiを満たさない場合は、ｘiを０とする。
【０１５３】
なお、この例では、ｘiが１であれば、行列中の採用する要素を１行下にずらすようにしている。しかし、暗号化時の公開鍵行列Ａと、復号時の秘密鍵行列Ｂにおいて採用する要素は、互いに対応が取れてれば足り、要素の選択方法は、本例に限られるものではない。
【０１５４】
以下の実施形態は、上述の実施形態１〜３のそれぞれについて、ＬＯ法による攻撃に対しても安全性を高めるために、前述の提案された方式を適用したものである。すなわち、実施形態１〜３で用いた秘密鍵ベクトルｂを、秘密鍵行列Ｂとしたものであり、基本的な考え方は同じである。このため、主として、上述の実施形態と異なる点について説明するものとする。
【０１５５】
以下の実施形態において、秘密鍵は、超増加ベクトルｂに代え超増加行列
【０１５６】
【数５２】
0004200259.tif 000027
【０１５７】
を用いることとする。ただし、超増加行列Ｂとは、第ｉ列のどの要素も第１〜第ｉ−１列の各最大要素の和よりも大きい行列をいう。また、特に混乱のない限り、Ｂ＝（ｂji）、あるいは、Ｂ＝（ｂj1，ｂj2，...，ｂjn）のように表す場合もある。
【０１５８】
（４．第１実施形態の変形）
（４．１公開鍵生成）
作業用記憶部１０３は、適当な大きさの乱数のベクトルｒ＝（ｒ1，ｒ2，...，ｒn）に代え、適当な大きさの乱数の行列Ｒ＝（ｒji）を格納する。
【０１５９】
ただし、
０≦ｒji＜ｑ
【０１６０】
【数５３】
0004200259.tif 000028
【０１６１】
を満たすものとする。
【０１６２】
そして、演算部１０１は、秘密鍵保持部１０２に格納してある秘密鍵行列と作業用記憶部１０３に格納している乱数行列とを用いて、
ａji≡ｂji  （ｍｏｄ  ｐ）
ａji≡ｒji  （ｍｏｄ  ｑ），  １≦ｉ≦ｎ，１≦ｊ≦ｈ
を満たすＡ＝（ａj1，ａj2，...，ａjn）を作成する。そして、
【０１６３】
【数５４】
0004200259.tif 000029
【０１６４】
を公開鍵行列として出力する。
【０１６５】
ここで、上記の２式を満たすａjiは、
ａji≡ｂjiｑｑ-1＋ｒjiｐｐ-1  （ｍｏｄ  ｐｑ）
と表すことができる。
【０１６６】
（４．２暗号化）
公開鍵保持部２０３は、公開鍵ａに代え、公開鍵生成装置１００によって作成された公開鍵行列Ａ＝（ａj1，ａj2，...，ａjn）を保持する。
【０１６７】
演算部２０１は、
【０１６８】
【数５５】
0004200259.tif 000030
【０１６９】
を計算し、Ｃを暗号文として出力する。
【０１７０】
ただし、ｃi∈｛ａ1i，ａ1i，...，ａhi｝における、ａjiの添字ｊ＝ｊ（ｉ）は、前述のように、以下のように定める。
【０１７１】
まず、変数ｎ１を初期値−１とする。そして、変数ｉをｉ＝ｎから、ｉ＝１まで変化させて、次の処理を行なう。
【０１７２】
ｎ１＝ｎ１＋ｘi，  ｊ＝（ｎ１  ｍｏｄ  ｈ）＋  １
【０１７３】
（４．３復号）
秘密鍵保持部３０３は、超増加ベクトルｂに代え、公開鍵行列Ａを生成するときに使用した超増加行列Ｂを格納する。
【０１７４】
演算部３０１は、Ｃを逆モジュラ乗算して、
Ｃ'＝ｗ-1  ｍｏｄ  ｍ
とする。
【０１７５】
そして、前述のように、ｊ＝１とし、変数ｉをｉ＝ｎから、ｉ＝１まで変化させて、次の処理を行なう。
【０１７６】
Ｃ'≧ｂjiを満たす場合は、ｘiを１とし、Ｃ'＝Ｃ'−ｂjiとする。そして、ｊ＝ｊ  ｍｏｄ  ｈ  ＋１として、秘密鍵行列の採用する要素の行を１行下に移動する。
【０１７７】
Ｃ'≧ｂjiを満たさない場合は、ｘiを０とする。
【０１７８】
復号装置３００は、この結果得られたｘ＝（ｘ1，ｘ2，...，ｘn）を、復号した平文として出力する。
【０１７９】
（５．第２実施形態の変形）
（５．１公開鍵生成）
作業用記憶部１０３は、乱数のベクトルｒ＝（ｒ1，ｒ2，...，ｒn）に代え、乱数の行列Ｒ1＝（ｒji）を格納する。ただし、０≦ｒji＜｜Ｌ／ｎ｜を満たすものとする。
【０１８０】
演算部１０１は、
ｂji'＝Ｌｂji＋ｒji
として、Ｂ'＝（ｂj1'、ｂj2'，...，ｂjn'）を求め、作業用記憶部１０３に格納する。
【０１８１】
次に演算部１０１は、
【０１８２】
【数５６】
0004200259.tif 000031
【０１８３】
を満たすような、整数Ｕを生成し、秘密鍵保持部１０２に格納する。
【０１８４】
そして、演算部１０１は、適当な大きさの乱数を要素とする行列Ｒ2＝（Ｒji）を生成し、作業用記憶部１０３に格納する。
【０１８５】
演算部１０１は、次の関係を満たす、互いに素な整数ｍとｗとを生成し、秘密鍵保持部１０２に格納する。
【０１８６】
【数５７】
0004200259.tif 000032
【０１８７】
演算部１０１は、ａji＝ｗ（ｂji'＋ＵＲji）  ｍｏｄ  ｍを計算し、Ａ＝（ａj1，ａj2，...，ａjn）を作成する。そして、このＡを公開鍵行列として出力する。
【０１８８】
（５．２暗号化）
第２実施形態の変形における暗号化装置２００の処理は、第１実施形態の変形と同じである。
【０１８９】
（５．３復号）
第２実施形態の変形における復号化装置２００の処理は、
【０１９０】
【数５８】
0004200259.tif 000033
【０１９１】
を求めるところまで、第１実施形態と同じである。ただし、ｂiはｂjiと表される。
【０１９２】
その後の処理は、第１実施形態の変形と同様にして、ｘ＝（ｘ1，ｘ2，...，ｘn）を算出し、復号した平文として出力する。
【０１９３】
（６．第３実施形態の変形）
（６．１公開鍵生成）
本実施形態において、演算部１０１は、１〜ｎｊ列の各列の最大要素の和を算出してＳjとする。
【０１９４】
また、演算部１０１が生成する互いに素な整数ｍj+1とｗj+1とは、
【０１９５】
【数５９】
0004200259.tif 000034
【０１９６】
の関係を満たすものとする。そして、１行目からｈ行目までのｇ行目について、実施形態３同様のモジュラ乗算を施して
ｂg(j+1)＝（ｂg1(j+1)，...，ｂg n1(j+1)｜...｜ｂg nj+1(j+1)，...，ｂk n(j+1)(j+1)）
を生成する。
【０１９７】
演算部１０１は、以上の処理をｊ＝ｋ−１になるまで繰り返す。
【０１９８】
そして、
ａgi＝ｂgi(k)      ｉ＝１，２，...，ｎ
とし、Ａ＝（ａ11，ａ12，...，ａhn）を作成し、このＡを公開鍵行列として出力する。
【０１９９】
（６．２暗号化）
第３実施形態の変形における暗号化装置２００の処理は、第１実施形態の変形と同じである。
【０２００】
（６．３復号）
第３実施形態の変形における復号化装置２００の処理は、第３実施形態同様に、ブロック毎にモジュラ乗算をはずす。そして、第１実施形態の変形と同様に、得られたｘiが１であれば、秘密鍵行列Ａ中の採用する要素を１行下にずらすようにして、復号処理を進める。その結果、得られたｘ＝（ｘ1，...，ｘn）を復号した平文として出力する。
【０２０１】
【発明の効果】
上述のように、本発明によれば、Ｓｈａｍｉｒ法による攻撃に強いナップザック暗号の公開鍵を生成する装置、および、この公開鍵を用いて暗号文を作成する装置と、この暗号文を復号する装置を実現できる。
【０２０２】
また、本発明の目的は、暗号化、復号化の処理を速く行なえる公開鍵方式の暗号を取り扱う装置を実現できる。
【図面の簡単な説明】
【図１】は、本発明をインターネットにおける電子メールの送受信時に適用したときの構成を説明するブロック図である。
【図２】は、第１実施形態の公開鍵生成装置１００の処理を説明するための説明図である。
【図３】は、第１実施形態の暗号化装置２００の処理を説明するための説明図である。
【図４】は、第１実施形態の復号装置３００の処理を説明するための説明図である。
【図５】は、第２実施形態の公開鍵生成装置１００の演算部１０１の処理を説明するための説明図である。
【図６】は、公開鍵行列から要素を選択する処理の一例について説明するための説明図である。
【符号の説明】
１００…公開鍵生成装置
１０１…演算部、１０２…秘密鍵保持部、１０３…作業用記憶部
２００…暗号化装置
２０１…演算部、２０２…平文保持部、２０３…公開鍵保持部
３００…復号装置
３０１…演算部、３０２…暗号文保持部、３０３…秘密鍵保持部
【図１】
0004200259.tif 000089
【図２】
0004200259.tif 000090
【図３】
0004200259.tif 000091
【図４】
0004200259.tif 000092
【図５】
0004200259.tif 000093
【図６】
0004200259.tif 000094