TOP > 国内特許検索 > 公開鍵生成装置、暗号化装置および復号装置 > 明細書

明細書 :公開鍵生成装置、暗号化装置および復号装置

発行国 日本国特許庁(JP)
公報種別 特許公報(B2)
特許番号 特許第4200259号 (P4200259)
公開番号 特開2002-139995 (P2002-139995A)
登録日 平成20年10月17日(2008.10.17)
発行日 平成20年12月24日(2008.12.24)
公開日 平成14年5月17日(2002.5.17)
発明の名称または考案の名称 公開鍵生成装置、暗号化装置および復号装置
国際特許分類 G09C   1/00        (2006.01)
H04L   9/08        (2006.01)
FI G09C 1/00 620Z
H04L 9/00 601F
請求項の数または発明の数 19
全頁数 37
出願番号 特願2000-335953 (P2000-335953)
出願日 平成12年11月2日(2000.11.2)
審査請求日 平成17年7月21日(2005.7.21)
特許権者または実用新案権者 【識別番号】593165487
【氏名又は名称】学校法人金沢工業大学
発明者または考案者 【氏名】林 彬
個別代理人の代理人 【識別番号】110000198、【氏名又は名称】特許業務法人湘洋内外特許事務所
【識別番号】100084032、【弁理士】、【氏名又は名称】三品 岩男
審査官 【審査官】青木 重徳
参考文献・文献 林彬,垣本真司,“新しいナップザック行列暗号の鍵生成法”,2001年暗号と情報セキュリティシンポジウム予稿集,2001年 1月23日,Volume II of II,p.553-558
小林邦勝,木村真樹,菅野泰之,田中敦,“暗号鍵を選択するナップザック暗号”,電子情報通信学会技術研究報告(ISEC95-7~14),日本,社団法人電子情報通信学会,1995年 7月21日,Vol.95 No.172,p.29-40
片柳磨子,村上恭通,笠原正雄,“積和型暗号に関する二,三の考察”,2000年暗号と情報セキュリティ・シンポジウム,2000年 1月26日,B-VI公開鍵暗号,B40
林彬,“ナップザック暗号の改良の試み”,電子情報通信学会技術研究報告(ISEC96-1~7),日本,社団法人電子情報通信学会,1996年 5月20日,Vol.96 No.47,p.33-36
石野豊,林彬,“ナップザック暗号に対するLagarias-Odlyzko法における格子の構成に関する検討”,電子情報通信学会技術研究報告(ISEC2002-83~95),日本,社団法人電子情報通信学会,2002年11月 8日,Vol.102 No.437,p.41-44
調査した分野 G09C 1/00
H04L 9/08
JSTPlus(JDreamII)
JMEDPlus(JDreamII)
JST7580(JDreamII)
特許請求の範囲 【請求項1】
公開鍵a=(a,a,・・・,a)を生成する公開鍵生成装置であって、
超増加ベクトルb=(b,b,・・・,b)を記憶する手段と、互いに素な自然数pとqとを記憶する手段と、乱数を要素とするベクトルr=(r,r,・・・,r)を記憶する手段と、
前記超増加ベクトルbと、自然数pおよびqと、ベクトルrとを参照して、
≡b (mod p)
≡r (mod q)
を満たすa=(a,a,・・・,a)を生成する演算手段と
を備えることを特徴とする公開鍵生成装置:
ただし、
0≦r<q
【数1】
JP0004200259B2_000035t.gif
を満たすものとする。
【請求項2】
開鍵a=(a,a,・・・,a)を用いて、平文xを暗号文Cに変換する暗号化装置であって、
前記公開鍵aを記憶する手段と、前記平文xを記憶する手段と、
【数2】
JP0004200259B2_000036t.gif
を計算する演算手段とを備えることを特徴とする暗号化装置:
ただし、前記公開鍵aは、
超増加ベクトルb=(b,b,・・・,b)、
互いに素な自然数pとq、
乱数を要素とするベクトルr=(r,r,・・・,r)、とすると、
≡b (mod p)
≡r (mod q)
を満たし、
0≦r<q
【数3】
JP0004200259B2_000037t.gif
を満たすものとする。
【請求項3】
開鍵a=(a,a,・・・,a)を用いて暗号化された暗号文Cを平文xに変換する復号装置であって、
前記暗号文Cを記憶する手段と、
公開鍵a=(a,a,・・・,a)を生成するときに用いた超増加ベクトルb=(b,b,・・・,b)と、pとを記憶する手段と、
C'=C mod p
を算出し、
について、
1)C'≧bを満たす場合は、xを1とし、C'をC'-bとする、
2)C'≧bを満たさない場合は、xを0とする、
という処理を逆算カウンタ変数iがnから1になるまで繰り返し、得られたx=(x,x,・・・,x)を平文とする演算手段と
を備えることを特徴とする復号装置:
ただし、前記公開鍵aは、
超増加ベクトルb=(b,b,・・・,b)、
互いに素な自然数pとq、
乱数を要素とするベクトルr=(r,r,・・・,r)、とすると、
≡b (mod p)
≡r (mod q)
を満たし、
0≦r<q
【数4】
JP0004200259B2_000038t.gif
を満たすものとする。
【請求項4】
公開鍵a=(a,a,・・・,a)を生成する公開鍵生成装置であって、
超増加ベクトルb=(b,b,・・・,b)を記憶する手段と、
整数Lと、0≦r<|L/n|を満たす乱数のベクトルr=(r,r,・・・,r)と、乱数を要素とするベクトルR=(R,R,・・・,R)とを記憶する手段と(ただし、|L/n|は、L/nを超えない最大の整数)、
'=Lb+rとして、b'=(b',b',・・・,b')を求め、
【数5】
JP0004200259B2_000039t.gif
を満たすUと、互いに素な整数mとwとを生成し、記憶するとともに、a=w(b'+UR) mod mを計算して、a=(a,a,・・・,a)を生成する演算手段と
を備えることを特徴とする公開鍵生成装置:
ただし、
【数6】
JP0004200259B2_000040t.gif
を満たすものとする。
【請求項5】
開鍵a=(a,a,・・・,a)を用いて、平文xを暗号文Cに変換する暗号化装置であって、
前記公開鍵aを記憶する手段と、前記平文xを記憶する手段と、
【数7】
JP0004200259B2_000041t.gif
を計算する演算手段とを備えることを特徴とする暗号化装置:
ただし、前記公開鍵aは、
超増加ベクトルb=(b,b,・・・,b)、
整数L、
0≦r<|L/n|(|L/n|は、L/nを超えない最大の整数)を満たす乱数のベクトルr=(r,r,・・・,r)、
乱数を要素とするベクトルR=(R,R,・・・,R)、
'=(b',b',・・・,b')(b'=Lb+r)、
【数8】
JP0004200259B2_000042t.gif
を満たすU、
互いに素な整数mとw、とすると、
=w(b'+UR) mod mを計算することにより算出されたものであり、
【数9】
JP0004200259B2_000043t.gif
を満たすものとする。
【請求項6】
開鍵a=(a,a,・・・,a)を用いて暗号化された暗号文Cを平文xに変換する復号装置であって、
前記暗号文Cを記憶する手段と、
この暗号文Cの生成に用いた公開鍵a=(a,a,・・・,a)を生成するときに用いた超増加ベクトルb=(b,b,・・・,b)と、wとmと、Uと、Lとを記憶する手段と、
C'=w-1C mod mとし、C''=C' mod Uとし、さらに、C'''=|C''/L|とし(|C''/L|はC''/Lを超えない最大の整数)、
について、
1)C'''≧bを満たす場合は、xを1とし、C'''をC'''-bとする、
2)C'''≧bを満たさない場合は、xを0とする、
という処理を逆算カウンタ変数iがnからになる1まで繰り返し、得られたx=(x,x,・・・,x)を平文とする演算手段と
を備えることを特徴とする復号装置:
ただし、前記公開鍵aは、
超増加ベクトルb=(b,b,・・・,b)、
整数L、
0≦r<|L/n|(|L/n|は、L/nを超えない最大の整数)を満たす乱数のベクトルr=(r,r,・・・,r)、
乱数を要素とするベクトルR=(R,R,・・・,R)、
'=(b',b',・・・,b')(b'=Lb+r)、
【数10】
JP0004200259B2_000044t.gif
を満たすU、
互いに素な整数mとw、とすると、
=w(b'+UR) mod mを計算することにより算出されたものであり、
【数11】
JP0004200259B2_000045t.gif
を満たすものとする。
【請求項7】
記憶装置と、処理装置と、を有する電子計算機が、公開鍵a=(a,a,・・・,a)を生成する方法であって、
前記記憶装置は、超増加ベクトルb=(b,b,・・・,b)と、互いに素な自然数pとqと、乱数を要素とするベクトルr=(r,r,・・・,r)と、を格納し、
前記処理装置は、
≡b (mod p)
≡r (mod q)
を満たすa=(a,a,・・・,a)を算出して、得られたaを公開鍵とする公開鍵生成方法。
ただし、
0≦r<q
【数12】
JP0004200259B2_000046t.gif
を満たすものとする。
【請求項8】
記憶装置と、処理装置と、を有する電子計算機が、公開鍵a=(a,a,・・・,a)を用いて、平文xを暗号文Cに変換する暗号化方法であって、
前記記憶装置は、前記公開鍵aと、前記平文xと、を格納し、
前記処理装置は、
【数13】
JP0004200259B2_000047t.gif
を計算して、得られたCを暗号文とする暗号化方法。
ただし、前記公開鍵aは、
超増加ベクトルb=(b,b,・・・,b)、
互いに素な自然数pとq、
乱数を要素とするベクトルr=(r,r,・・・,r)、とすると、
≡b (mod p)
≡r (mod q)
を満たし、
0≦r<q
【数14】
JP0004200259B2_000048t.gif
を満たすものとする。
【請求項9】
記憶装置と、処理装置と、を有する電子計算機が、公開鍵a=(a,a,・・・,a)を用いて暗号化された暗号文Cを平文xに変換する復号方法であって、
前記記憶装置は、前記暗号文Cと、公開鍵a=(a,a,・・・,a)を生成するときに用いた超増加ベクトルb=(b,b,・・・,b)と、pと、を格納し、
前記処理装置は、
C'=C mod p
を算出し、
について、
1)C'≧bを満たす場合は、xを1とし、C'をC'-bとする、
2)C'≧bを満たさない場合は、xを0とする、
という処理を逆算カウンタ変数iがnから1になるまで繰り返し、得られたx=(x,x,・・・,x)を平文とする復号方法。
ただし、前記公開鍵aは、
超増加ベクトルb=(b,b,・・・,b)、
互いに素な自然数pとq、
乱数を要素とするベクトルr=(r,r,・・・,r)、とすると、
≡b (mod p)
≡r (mod q)
を満たし、
0≦r<q
【数15】
JP0004200259B2_000049t.gif
を満たすものとする。
【請求項10】
公開鍵行列
【数16】
JP0004200259B2_000050t.gif
を生成する公開鍵生成装置であって、
超増加行列
【数17】
JP0004200259B2_000051t.gif
を記憶する手段と、
互いに素な自然数pとqとを記憶する手段と、乱数を要素とする行列
【数18】
JP0004200259B2_000052t.gif
とを記憶する手段と、
ji≡bji (mod p)
ji≡rji (mod q)
を満たすA=(aj1,aj2,・・・,ajn)を生成する演算手段と
を備えることを特徴とする公開鍵生成装置:
ただし、
0≦rji<q
【数19】
JP0004200259B2_000053t.gif
を満たすものとする(ただし、bmax=max{b1i,b2i,・・・,bhi})。
【請求項11】
開鍵行列A=(aj1,aj2,・・・,ajn)を用いて、平文xを暗号文Cに変換する暗号化装置であって、
前記公開鍵行列Aを記憶する手段と、前記平文xを記憶する手段と、
【数20】
JP0004200259B2_000054t.gif
を計算する演算手段とを備えることを特徴とする暗号化装置:
ただし、c∈{a1i,a2i,・・・,ahi}における、ajiの添字j=j(i)は、以下のように定めるものとする。
1)変数n1を初期値-1とする
2)変数iをi=nから、i=1まで変化させて、次の処理を行なう。
n1=n1+x, j=(n1 mod h)+ 1
また、前記公開鍵行列Aは、
超増加行列
【数21】
JP0004200259B2_000055t.gif
互いに素な自然数pとq、
乱数を要素とする行列
【数22】
JP0004200259B2_000056t.gif
ji≡bji (mod p)
ji≡rji (mod q)
を満たし、
0≦rji<q
【数23】
JP0004200259B2_000057t.gif
を満たすものとする(ただし、bmax=max{b1i,b2i,・・・,bhi})。
【請求項12】
開鍵行列A=(aj1,aj2,・・・,ajn)を用いて暗号化された暗号文Cを平文xに変換する復号装置であって、
前記暗号文Cを記憶する手段と、
公開鍵行列A=(aj1,aj2,・・・,ajn)を生成するときに用いた超増加行列B=(bj1,bj2,・・・,bjn)と、pとを記憶する手段と、
C'=C mod p
を算出し、
jiについて、j=1とし、
1)C’≧bjiを満たす場合は、xを1とし、C'をC'-bjiとする、
2)C'≧bjiを満たさない場合は、xを0とする、
という処理を逆算カウンタ変数iがnから1になるまで繰り返し、得られたx=(x,x,・・・,x)を平文とする演算手段と
を備えることを特徴とする復号装置:
ただし、前記公開鍵行列Aは、
超増加行列
【数24】
JP0004200259B2_000058t.gif
互いに素な自然数pとq、
乱数を要素とする行列
【数25】
JP0004200259B2_000059t.gif
ji≡bji (mod p)
ji≡rji (mod q)
を満たし、
0≦rji<q
【数26】
JP0004200259B2_000060t.gif
を満たすものとする(ただし、bmax=max{b1i,b2i,・・・,bhi})。
【請求項13】
公開鍵行列
【数27】
JP0004200259B2_000061t.gif
を生成する公開鍵生成装置であって、
超増加行列
【数28】
JP0004200259B2_000062t.gif
を記憶する手段と、
整数Lと、0≦rij<|L/n|を満たす乱数を要素とする行列
【数29】
JP0004200259B2_000063t.gif
と、乱数を要素とする行列
【数30】
JP0004200259B2_000064t.gif
とを記憶する手段と、
ji'=Lbji+rjiとして、bji'を求め、
【数31】
JP0004200259B2_000065t.gif
を満たすUと、互いに素な整数mとwとを生成し、記憶するとともに、aji=w(bji'+URji) mod mを計算して、公開鍵行列A=(aj1,aj2,・・・,ajn)を生成する演算手段と
を備えることを特徴とする公開鍵生成装置:
ただし、
【数32】
JP0004200259B2_000066t.gif
を満たすものとする。
【請求項14】
開鍵行列A=(aj1,aj2,・・・,ajn)を用いて、平文xを暗号文Cに変換する暗号化装置であって、
前記公開鍵行列Aを記憶する手段と、前記平文xを記憶する手段と、
【数33】
JP0004200259B2_000067t.gif
を計算する演算手段とを備えることを特徴とする暗号化装置:
ただし、c∈{a1i,a2i,・・・,ahi}における、ajiの添字j=j(i)は、以下のように定めるものとする。
1)変数n1を初期値-1とする
2)変数iをi=nから、i=1まで変化させて、次の処理を行なう。
n1=n1+x, j=(n1 mod h)+ 1
また、公開鍵行列Aは、
超増加行列
【数34】
JP0004200259B2_000068t.gif
整数L、
0≦rij<|L/n|を満たす乱数を要素とする行列
【数35】
JP0004200259B2_000069t.gif
乱数を要素とする行列
【数36】
JP0004200259B2_000070t.gif
ji'(bji'=Lbji+rji)、
【数37】
JP0004200259B2_000071t.gif
を満たすU、
互いに素な整数mとw、とすると、
ji=w(bji'+URji) mod mを計算することにより算出されたものであり、
【数38】
JP0004200259B2_000072t.gif
を満たすものとする。
【請求項15】
開鍵行列A=(aj1,aj2,・・・,ajn)を用いて、暗号化された暗号文Cを平文xに変換する復号装置であって、
前記暗号文Cを記憶する手段と、
公開鍵行列A=(aj1,aj2,・・・,ajn)を生成するときに用いた超増加行列B=(bj1,bj2,・・・,bjn)と、UとLとmとwとを記憶する手段と、
C'=w-1C mod mとし、C''=C' mod Uとし、さらに、C'''=|C''/L|とし、
jiについて、
1)C'''≧bjiを満たす場合は、xを1とし、C'''をC'''-bjiとする、
2)C'''≧bjiを満たさない場合は、xを0とする、
という処理を逆算カウンタ変数iがnから1になるまで繰り返し、得られたx=(x,x,・・・,x)を平文とする演算手段と
を備えることを特徴とする復号装置。
ただし、公開鍵行列Aは、
超増加行列
【数39】
JP0004200259B2_000073t.gif
整数L、
0≦rij<|L/n|を満たす乱数を要素とする行列
【数40】
JP0004200259B2_000074t.gif
乱数を要素とする行列
【数41】
JP0004200259B2_000075t.gif
ji'(bji'=Lbji+rji)、
【数42】
JP0004200259B2_000076t.gif
を満たすU、
互いに素な整数mとw、とすると、
ji=w(bji'+URji) mod mを計算することにより算出されたものであり、
【数43】
JP0004200259B2_000077t.gif
を満たすものとす。
【請求項16】
公開鍵a=(a,a,・・・,a)を生成する公開鍵生成装置であって、
ブロック化係数kと、n=0と、0<n<n<・・・<n=nを満たすk個の正整数とを記憶する手段と、
以下に示す1)2)の処理をカウンタ変数jが1からkになるまで繰り返し、得られたb(k)を公開鍵a=(a,a,・・・,a)とする演算手段と
を備えることを特徴とする公開鍵生成装置(S=0、b(0)の初期値は空ベクトルとする)。
1)要素数nj-1のベクトルb(j-1)を以下の処理により要素数nのベクトルb(j-1)に伸張する。
1-1)Sj-1,bn(j-1)+1(j-1),・・・,bnj(j-1)が超増加になるように、bn(j-1)+1(j-1),・・・,bnj(j-1)を生成する。
1-2)生成したbn(j-1)+1(j-1),・・・,bnj(j-1)を、ベクトルb(j-1)に付加して、b(j-1)=(b(j-1)+,・・・,+bnj(j-1))とする。
2)以下の処理を行ない、ベクトルb(j-1)からベクトルb(j)を生成して、記憶する。
【数44】
JP0004200259B2_000078t.gif
を満たす互いに素なmとwとを生成し記憶する。
(j)=w(j-1) mod mを算出して、ベクトルb(j)とする。
【数45】
JP0004200259B2_000079t.gif
を算出して、記憶する。
【請求項17】
開鍵a=(a,a,・・・,a)を用いて、平文xを暗号文Cに変換する暗号化装置であって、
前記公開鍵aを記憶する手段と、前記平文xを記憶する手段と、
【数46】
JP0004200259B2_000080t.gif
を計算する演算手段とを備えることを特徴とする暗号化装置。
ただし、公開鍵aは、
ブロック化係数k、
=0、
0<n<n<・・・<n=nを満たすk個の正整数、とすると、
以下に示す1)2)の処理をカウンタ変数jが1からkになるまで繰り返し、得られたb(k)を公開鍵a=(a,a,・・・,a)としたものとする(ただし、S=0、b(0)の初期値は空ベクトル)。
1)要素数nj-1のベクトルb(j-1)を以下の処理により要素数nのベクトルb(j-1)に伸張する。
1-1)Sj-1,bn(j-1)+1(j-1),・・・,bnj(j-1)が超増加になるように、bn(j-1)+1(j-1),・・・,bnj(j-1)を生成する。
1-2)生成したbn(j-1)+1(j-1),・・・,bnj(j-1)を、ベクトルb(j-1)に付加して、b(j-1)=(b(j-1)+,・・・,+bnj(j-1))とする。
2)以下の処理を行ない、ベクトルb(j-1)からベクトルb(j)を生成する。
【数47】
JP0004200259B2_000081t.gif
を満たす互いに素なmとwとを生成する。
(j)=w(j-1) mod mを算出して、ベクトルb(j)とする。
【数48】
JP0004200259B2_000082t.gif
を算出する。
【請求項18】
公開鍵行列
【数49】
JP0004200259B2_000083t.gif
を生成する公開鍵生成装置であって、
ブロック化係数kと、n=0と、0<n<n<・・・<n=nを満たすk個の正整数とを記憶する手段と、
以下に示す1)2)の処理をカウンタ変数jが1からkになるまで繰り返し、得られた行列B(k)を公開鍵行列A=(ag1,ag2,・・・,agn)とする演算手段と(ただし、1≦g≦h)を備えることを特徴とする公開鍵生成装置(S=0、B(0)は空行列とする)。
1)1行の要素数nj-1の行列B(j-1)を以下の処理により1行の要素数nの行列B(j-1)に伸張する。
1-1)(Sj-1,b n(j-1)+1(j-1),・・・,b nj(j-1))が超増加行列になるように、b n(j-1)+1(j-1),・・・,b nj(j-1)を生成する。
1-2)生成したb n(j-1)+1(j-1),・・・,b nj(j-1)を、行列B(j-1)に付加して、B(j-1)=(b (j-1)+,・・・,+b nj(j-1))とする。
2)以下の処理を行ない、行列B(j-1)から行列B(j)を生成して、記憶する。
【数50】
JP0004200259B2_000084t.gif
を満たす互いに素なmとwとを生成し記憶する。
(j)=w (j-1) mod mを算出して、行列B(j)とする。
【数51】
JP0004200259B2_000085t.gif
を算出して、記憶する。
【請求項19】
開鍵行列A=(ag1,ag2,・・・,agn)を用いて、平文xを暗号文Cに変換する暗号化装置であって、
前記公開鍵行列Aを記憶する手段と、前記平文xを記憶する手段と、
【数52】
JP0004200259B2_000086t.gif
を計算する演算手段とを備えることを特徴とする暗号化装置:
ただし、c∈{a1i,a2i,・・・,ahi}における、agiの添字g=g(i)は、以下のように定めるものとする。
1)変数n1を初期値-1とする
2)変数iをi=nから、i=1まで変化させて、次の処理を行なう。
n1=n1+x, g=(n1 mod h)+ 1
ただし、公開鍵行列Aは、
ブロック化係数k、
=0、
0<n<n<・・・<n=nを満たすk個の正整数、とすると、
以下に示す1)2)の処理をカウンタ変数jが1からkになるまで繰り返し、得られた行列B(k)を公開鍵行列A=(ag1,ag2,・・・,agn)としたものである(ただし、1≦g≦h、S=0、B(0)は空行列)。
1)1行の要素数nj-1の行列B(j-1)を以下の処理により1行の要素数nの行列B(j-1)に伸張する。
1-1)(Sj-1,b n(j-1)+1(j-1),・・・,b nj(j-1))が超増加行列になるように、b n(j-1)+1(j-1),・・・,b nj(j-1)を生成する。
1-2)生成したb n(j-1)+1(j-1),・・・,b nj(j-1)を、行列B(j-1)に付加して、B(j-1)=(b (j-1)+,・・・,+b nj(j-1))とする。
2)以下の処理を行ない、行列B(j-1)から行列B(j)を生成する。
【数53】
JP0004200259B2_000087t.gif
を満たす互いに素なmとwとを生成する。
(j)=w (j-1) mod mを算出して、行列B(j)とする。
【数54】
JP0004200259B2_000088t.gif
を算出する。
発明の詳細な説明 【0001】
【発明の属する技術分野】
本発明は、暗号技術に係り、特に、暗号化、復号化速度が速く、しかも安全性が高い公開鍵暗号方式に関する。
【0002】
【従来の技術】
コンピュータネットワークを利用したデータ通信における代表的な暗号化方式として、共通鍵暗号法と公開鍵暗号法とがある。共通鍵暗号法は、暗号化と復号化とで同じ暗号鍵を使う方法である。公開鍵暗号法は、暗号化と復号化とで違う暗号鍵を使う方法である。公開鍵暗号法では、一方の暗号鍵で暗号化したデータは、もう一方の鍵を使わないと復号できない。このため一方の鍵を公開し、他方の鍵を秘密にしておく。
【0003】
一般に、共通鍵暗号法は、暗号化、復号化の処理速度が速いが、通信相手に安全な方法で暗号鍵を渡すことが難しい。一方の公開鍵暗号方式は、片方の鍵は公開することができるので、相手に暗号鍵を渡すことは非常に楽である。
【0004】
公開鍵暗号方式としては、RSA方式が代表的で、よく知られている。しかし、RSA方式は、暗号化、復号化とも共通鍵方式に比べ、1000倍程度処理速度が遅い。このため、コンピュータネットワークを利用したデータ通信においては、共通鍵の受け渡し、あるいは、比較的少量のデータ伝送等に使われている程度にとどまっている。
【0005】
公開鍵暗号方式で、処理速度が速い方式としてMerkle-Hellmanによって提案されたナップザック暗号方式(MH型ナップザック暗号)がある(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))。MH型ナップザック暗号は、秘密鍵として、整数を要素とする超増加ベクトルb=(b1,b2,...,bn)と、
【0006】
【数27】
JP0004200259B2_000002t.gif【0007】
の制約を満たす、互いに素な関係を有する乗数wと法mとを用いる。
【0008】
そして、公開鍵として、ベクトルbにモジュラ乗算を施して得られるベクトルa=(a1,a2,...,an)を利用する。すなわちaとbとの要素間には次の関係がある。
【0009】
i=wbi mod m
ナップザック暗号における暗号化は、nビットの平文x=(x1,x2,...,xn)を、次の式にしたがって整数Cに変換し、このCを暗号文とする。
【0010】
【数28】
JP0004200259B2_000003t.gif【0011】
iは、超増加ベクトルでないため、一般に、このナップザック暗号を解くのは容易でない。
【0012】
暗号文Cの復号化は、Cを逆モジュラ乗算して、
C'=w-1C mod m
とする。すると
【0013】
【数29】
JP0004200259B2_000004t.gif【0014】
となり、易しいナップザック問題を解くことによって平文を得ることができる(biが超増加ベクトルの場合、ナップザック暗号は容易に解ける)。
【0015】
このように、ナップザック暗号は、計算処理の負荷が少ないため、暗号化、復号化とも、共通鍵暗号方式と同等の処理速度を得ることができる。
【0016】
しかし、ナップザック暗号は、Shamirによって提案された解読法(S法)が知られており、今では安全な暗号法ではないとされている((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).)。
【0017】
【発明が解決しようとする課題】
S法は、w,mを知らない解読者が、W,Mというパラメータを見付け、公開鍵(a1,a2,...,an)を、超増加ベクトル(b1',b2',...,bn')に変換することによって、復号を易しいナップザック問題にしてしまうものである。
【0018】
すなわち、公開鍵aにモジュラ乗算を施して得られるベクトルであって、超増加であるb'を見出すものである。このとき一般にはbとb'とは異なるが、b'が超増加であれば十分である。したがって、本来の秘密超増加ベクトルbでなくても、Wbi' mod M=aiとなる、超増加ベクトル(b1',b2',...,bn')を得ることができれば、
【0019】
【数30】
JP0004200259B2_000005t.gif【0020】
という、易しいナップザック問題を解くことにより、平文xを得ることができる。
【0021】
S法は、公開鍵ベクトルaが、秘密鍵である超増加ベクトルbにモジュラ乗算を施して得られるものであるときに適用できるものである。すなわち、S法によってMH型ナップザック暗号が解読されるのは、公開鍵ベクトルaと秘密鍵ベクトルbとが、単純なモジュラ乗算の関係を有しているためと考えられる。
【0022】
本発明の目的は、Shamir法による攻撃に強いナップザック暗号の公開鍵を生成する装置、および、この公開鍵を用いて暗号文を作成する装置と、この暗号文を復号する装置を提供することにある。
【0023】
また、本発明の目的は、暗号化、復号化の処理を速く行なえる公開鍵方式の暗号を取り扱う装置を提供することにある。
【0024】
【課題を解決するための手段】
上記課題を解決するため、本発明の第1の態様によれば、
公開鍵a=(a1,a2,...,an)を生成する公開鍵生成装置であって、
超増加ベクトルb=(b1,b2,...,bn)を記憶する手段と、互いに素な自然数pとqとを記憶する手段と、乱数を要素とするベクトルr=(r1,r2,...,rn)を記憶する手段と、これらの値を参照して、
i≡bi (mod p)
i≡ri (mod q)
を満たすa=(a1,a2,...,an)を生成する演算手段と
を備えることを特徴とする公開鍵生成装置が提供される。
【0025】
ただし、
0≦ri<q
【0026】
【数31】
JP0004200259B2_000006t.gif【0027】
を満たすものとする。
【0028】
上記課題を解決するため、本発明の第2の態様によれば、
本発明の第1の態様の公開鍵a=(a1,a2,...,an)を用いて、平文xを暗号文Cに変換する暗号化装置であって、
前記公開鍵aを記憶する手段と、前記平文xを記憶する手段と、
【0029】
【数32】
JP0004200259B2_000007t.gif【0030】
を計算する演算手段とを備えることを特徴とする暗号化装置が提供される。
【0031】
さらに、本発明の第3の態様によれば、
本発明の第1の態様の公開鍵a=(a1,a2,...,an)を用いて、暗号化された暗号文Cを平文xに変換する復号装置であって、
前記暗号文Cを記憶する手段と、
公開鍵a=(a1,a2,...,an)を生成するときに用いた超増加ベクトルb=(b1,b2,...,bn)と、pとを記憶する手段と、
C'=C mod p
を算出し、
下記1)2)の処理を変数iをnから1まで繰り返し、得られたx=(x1,x2,...,xn)を平文とする演算手段と
を備えることを特徴とする復号装置が提供される。
【0032】
1)C'≧biを満たす場合は、xiを1とし、C'をC'-biとする
2)C'≧biを満たさない場合は、xiを0とする
【0033】
【発明の実施の形態】
本発明の実施の形態について、図面を参照して説明する。以下においては、本発明を電子計算機に適用した場合について説明する。
【0034】
本発明を適用する電子計算機は、中央処理装置、主記憶装置、補助記憶装置、外部入出力装置等を備える一般的な電子計算機とすることができる。また、ネットワークを介して外部と通信を行なえる構成としてもよい。
【0035】
本実施の形態において、電子計算機は公開鍵生成装置100として機能する。この公開鍵生成装置100は、本発明の処理を実現させるためのプログラムを、電子計算機の主記憶装置に格納し、中央処理装置がプログラムにしたがって動作を行うことにより実現することができる。また、公開鍵生成装置100等は、以下に説明する処理において、乗算、mod演算(剰余算)、加算等の演算を行なう必要があるが、これらの演算は、乗算器、加算器、除算器等を用いてハードウェアで行なうようにしてもよいし、ソフトウェアで実行させるようにしてもよい。
【0036】
公開鍵生成装置100は、公開鍵生成のための演算を行なう演算部101と、秘密鍵を保持する秘密鍵保持部102と、作業用変数、乱数等を一時的に保持する作業用記憶部103とを備えている。演算部101は中央処理装置によって実現することができ、秘密鍵保持部102は、例えば、主記憶装置、外部記憶装置によって実現することができる。作業用記憶103は、主記憶装置等によって実現することができる。演算部101が生成した公開鍵は、主記憶装置、外部記憶装置等に出力することができる。
【0037】
また、電子計算機は、生成された公開鍵を用いて、平文を暗号化する暗号化装置200として機能することもできる。
【0038】
暗号化装置200は、暗号化のための演算を行なう演算部201と、暗号化するための平文を保持する平文保持部202と、上述の公開鍵生成装置によって生成された公開鍵を保持する公開鍵保持部203とを備えている。演算部201は中央処理装置によって実現することができ、平文保持部202と公開鍵保持部203とは、例えば、主記憶装置、外部記憶装置によって実現することができる。演算部201が暗号化した暗号文は、主記憶装置、外部記憶装置等に出力することができる。
【0039】
さらに、電子計算機は、秘密鍵を用いて、暗号文を復号する復号装置300として機能することもできる。
【0040】
復号装置300は、復号のための演算を行なう演算部301と、上述の暗号化装置で生成された暗号文を保持する暗号文保持部302と、この暗号文を生成するときに使用した公開鍵を生成した秘密鍵を保持する秘密鍵保持部303とを備えている。演算部301は中央処理装置によって実現することができ、秘密鍵保持部302と暗号文保持部303とは、例えば、主記憶装置、外部記憶装置によって実現することができる。演算部301が復号した平文は、主記憶装置、外部記憶装置等に出力することができる。
【0041】
本発明による公開鍵生成装置100と暗号化装置200と復号装置300とは、例えば、インターネットにおける電子メールの送受信時に使用することができる。図1はこのときの構成を説明するためのブロック図である。
【0042】
電子メールの受け手10は、秘密鍵を用いて公開鍵生成装置100で生成した公開鍵を公開ファイル等に置くことにより公開する。電子メールの送り手20は、この公開鍵を入手し、暗号化装置200を用いて電子メールを暗号化した後、受け手に送信する。この電子メールを受信した受け手は、秘密鍵を用いて復号装置300で、暗号化された電子メールを復号することができる。このようにすることにより、安全性の高い電子メールの送受信を行うことができる。もちろん、本発明の適用例は、これらに限られるものではない。
【0043】
以下の実施形態において、秘密鍵は超増加ベクトルb=(b1,b2,...,bn)を用いることとする。ここで、超増加ベクトルとは、bi>b1+b2+...+bi-1が成り立つベクトルをいう。
【0044】
また、公開鍵生成装置100が生成または受け付ける超増加ベクトル、乱数等のパラメータのサイズは、特に限定はされないが、例えば、nを100程度としし、各パラメータを200ビット~300ビットとすることができる。なお、本発明によれば、これらのサイズを大きくすることにより、当然、安全性を高めることができる。しかも、この場合でも、暗号化、復号とも処理速度がほとんど低下しない。
【0045】
(1.第1実施形態)
本発明の、第1実施形態は、中国式剰余定理を用いて、公開鍵を生成する装置に係るものである。ここで、中国式剰余定理とは、n1,...nkが互いに素であるとすると、次の連立合同式
x≡a1(mod n1
・・・
x≡ak(mod nk
は、0≦x<n=n1・・・nkの範囲で一意的解を持ち、特にn1=p、n2=q、k=2のとき、
x=a1qq-1+a2pp-1 mod pq
が成り立つことをいう。ただし、pp-1≡1(mod q)、qq-1≡1(mod p)である。
【0046】
(1.1公開鍵生成)
第1実施形態における公開鍵生成装置100の処理について説明する。図2は、このときの処理の流れを説明する図である。
【0047】
秘密鍵保持部102は、自然数pと超増加ベクトルbとを格納する。
【0048】
作業用記憶部103は、自然数qと、適当な大きさの乱数のベクトルr=(r1,r2,...,rn)とを格納する。
【0049】
ただし、pとqとは互いに素である。また、riは整数で、0≦ri<qを満たし、pは、
【0050】
【数33】
JP0004200259B2_000008t.gif【0051】
を満たすものとする。
【0052】
なお、pとqとは、互いに素となるように演算部101で生成するようにしてもよいし、入力装置を介して入力するようにしてもよい。乱数riについても、演算部101で生成するようにしてもよいし、入力装置を介して入力するようにしてもよい。
【0053】
演算部101は、秘密鍵保持部102に格納してある秘密鍵と作業用記憶部103に格納している乱数とを用いて、
i≡bi (mod p)
i≡ri (mod q), 1≦i≦n
を満たすa=(a1,a2,...,an)を作成する。そして、このaを公開鍵として出力する。
【0054】
なお、上記の2式を満たすaiは、中国式剰余定理(Chinese Remainder Theorem)によって、
i≡biqq-1+ripp-1 (mod pq)
と表され、0≦ai<pqの範囲で一意に求めることができる。ただし、pp-1≡1(mod q)、qq-1≡1(mod p)である。
【0055】
上記の演算によって求められたaは、超増加ベクトルbからモジュラー乗算によって得られるベクトルではない。このため、本実施形態に対してS法は適用できないものと考えられる。
【0056】
(1.2暗号化)
第1実施形態における暗号化装置200の処理について説明する。図3は、このときの処理の流れを説明する図である。
【0057】
平文保持部202は、nビットの平文x=(x1,x2,...,xn)を保持する。ただし、xiは0または1である。
【0058】
公開鍵保持部203は、公開鍵生成装置100によって作成された公開鍵a=(a1,a2,...,an)を保持する。
【0059】
演算部201は、
【0060】
【数34】
JP0004200259B2_000009t.gif【0061】
を計算し、Cを暗号文として出力する。
【0062】
このように、本実施例において、暗号化は加算のみによって行うことができる。このため、本装置における暗号化の処理は、べき乗剰余演算が必要なRSA方式を用いた装置に比して、極めて高速であるといえる。
【0063】
(1.3復号)
第1実施形態における復号装置300の処理について説明する。図4は、このときの処理の流れを説明する図である。
【0064】
暗号文保持部302は、暗号化装置200が作成した暗号文Cを格納する。秘密鍵保持部303は、暗号文Cを生成した公開鍵aを生成するときに使用した、自然数pと超増加ベクトルbとを格納する。
【0065】
演算部301は、C mod pを算出する。これをC'とすると、C'は、bを用いて、
【0066】
【数35】
JP0004200259B2_000010t.gif【0067】
と表せる。bは超増加ベクトルであるから、これは易しいナップザック暗号である。このため、平文x=(x1,x2,...,xn)を容易に求めることができる。
【0068】
このときの易しいナップザック暗号を解く処理について、図4に示すフロー図を参照して説明する。
【0069】
演算部301は、変数iをnから1まで変化させて、以下の処理を行なう。まず、C'≧biを満たすかどうかを調べる(S101)。そして、C'≧biを満たす場合は、xiを1とし、C'をC'-biとする(S102)。C'≧biを満たさない場合は、xiを0とする(S103)。この結果得られたx=(x1,x2,...,xn)が求めるべき平文である。
【0070】
復号装置300は、この処理によって得られたxを、復号した平文として出力する。
【0071】
このように、本実施例において、復号は比較と減算のみによって行うことができる。このため、本装置における復号の処理は、べき乗剰余演算が必要なRSA方式を用いた装置に比して、極めて高速であるといえる。
【0072】
(2.第2実施形態)
本発明の第2実施形態は、超増加ベクトルbに対して、下位ビットおよび上位ビットに乱数を付加して超増加性を隠し、その後、wとmとでモジュラー乗算変換を施して公開鍵を生成する装置に係るものである。
【0073】
(2.1公開鍵生成)
第2実施形態における公開鍵生成装置100の処理について説明する。なお、図面の符号は第1実施形態と同じものを用いる。
【0074】
秘密鍵保持部102は、超増加ベクトルbと、適当な大きさの整数Lとを格納する。
【0075】
作業用記憶部103は、乱数のベクトルr=(r1,r2,...,rn)を格納する。
【0076】
ただし、0≦ri<|L/n|を満たすものとする。ここで、|L/n|は、L/nを超えない最大の整数である。すなわち、Lは、乱数の大きさを制限するために用いられる。
【0077】
なお、整数Lは、演算部101で生成するようにしてもよいし、入力装置を介して入力するようにしてもよい。乱数riについても、演算部101で生成するようにしてもよいし、入力装置を介して入力するようにしてもよい。
【0078】
次に演算部101の動作について図5に示すフロー図を参照して説明する。
【0079】
演算部101は、
i'=Lbi+ri
として、b'=(b1',b2',...,bn')を求め、作業用記憶部103に格納する(S201)。
【0080】
次に演算部101は、
【0081】
【数36】
JP0004200259B2_000011t.gif【0082】
を満たすような、整数Uを生成し、秘密鍵保持部102に格納する(S202)。
【0083】
そして、演算部101は、適当な大きさの乱数を要素とするベクトルR=(R1,R2,...,Rn)を生成し、作業用記憶部103に格納する(S203)。なお、乱数ベクトルRは、乱数ベクトルr同様に、あらかじめ用意して作業用記憶部103に格納しておいてもよい。
【0084】
演算部101は、次の関係を満たす、互いに素な整数mとwとを生成し、秘密鍵保持部102に格納する(S204)。
【0085】
【数37】
JP0004200259B2_000012t.gif【0086】
演算部101は、ai=w(bi'+URi) mod mを計算し、a=(a1,a2,...,an)を作成する。そして、このaを公開鍵として出力する(S205)。
【0087】
上記の演算によって求められたaは、超増加ベクトルbからモジュラ乗算によって得られるベクトルではない。このため、本実施形態に対してS法は適用できないものと考えられる。
【0088】
(2.2暗号化)
第2実施形態における暗号化装置200の処理は、第1実施形態と同じである。
【0089】
(2.3復号)
第2実施形態における復号装置300の処理について説明する。
【0090】
暗号文保持部302は、暗号文Cを格納する。秘密鍵保持部303は、暗号文Cを生成した公開鍵aを生成するときに使用した、互いに素な整数wとmと、Uと、Lと、超増加ベクトルbとを格納する。
【0091】
演算部301は、w-1C mod mを求め、C'とする。ここで、C'は、
【0092】
【数38】
JP0004200259B2_000013t.gif【0093】
である。
【0094】
演算部301は、次にC' mod Uを求め、C''とする。ここで、C''は、
【0095】
【数39】
JP0004200259B2_000014t.gif【0096】
である。また、bi'=Lbi+riである。
【0097】
さらに、演算部301は、|C''/L|を求め、C'''とする。ここで、C'''は、
【0098】
【数40】
JP0004200259B2_000015t.gif【0099】
となる。bは超増加ベクトルであるから、これは易しいナップザック暗号である。このため、第1実施形態で示した処理を行うことにより、平文x=(x1,x2,...,xn)を容易に求めることができる。復号装置300は、xを求め、得られたxを復号した平文として出力する。
【0100】
本実施例においても、簡単な演算で復号することができるため、第1実施例同様に、RSA方式に比して、極めて高速に復号処理を行うことができる。
【0101】
(3.第3実施形態)
本発明の第3実施形態は、超増加ベクトルbに対し、多重にモジュラ乗算変換を施して、公開鍵を生成する装置に係るものである。本実施形態に係る装置は、超増加ベクトルbのn個の要素すべてを同一のwとmとでモジュラ乗算変換するのではなく、n個の要素を、いくつかのブロックに分割する。そして、第1のブロックから始め、ブロックを追加する毎に、別のwiとmiとでモジュラ乗算していく。すなわち、0<n1<n2<...<nk=nを満たすk個の正整数を定めておき、まず、n1個の要素からなる超増加ベクトルを作る。これにモジュラ乗算変換を施し、次いで、それらn1個の要素の和と次のn2個-n1個の要素からなる超増加ベクトルを作り、これにモジュラ乗算変換を施す。そして、このような処理をk回繰り返すようにする。これにより、最初のブロックはk回のモジュラ乗算変換を、第2のブロックはk-1回のモジュラ乗算変換を施され、最後の第kブロックは1回のモジュラ乗算変換を施される。
【0102】
(3.1公開鍵生成)
第3実施形態における公開鍵生成装置100の処理について説明する。
【0103】
秘密鍵保持部102は、ブロック化係数kと、0<n1<n2<...<nk=nを満たすk個の正整数と、超増加ベクトルb(ただし、b=(b1,b2,...,bn1))と、次の制約を満たす、互いに素な整数m1とw1とを格納する。
【0104】
ブロック化係数kと、k個の正整数とは、演算部101で生成するようにしてもよいし、入力装置を介して入力するようにしてもよい。
なお、以下の説明において、活字の制約上「n1」を「n1」のように表す場合があるものとする。
【0105】
【数41】
JP0004200259B2_000016t.gif【0106】
演算部101は、超増加ベクトルb=(b1,b2,...,bn1)に対して、w1とm1とを用いてモジュラ乗算を施し、
(1)=(b1(1),b2(1),...,bn1(1)
を生成する。
【0107】
次に、演算部101は、S1=b1(1)+b2(1)+...+bn1(1)として、S1を秘密鍵保持部101に格納するとともに、(S1, bn1+1(1),bn1+2(1),...,bn2(1))が超増加ベクトルになるように、bn1+1(1),bn1+2(1),...,bn2(1)を生成して、秘密鍵保持部101に格納する。そして、b(1)を新たに、b(1)=(b1(1),b2(1),...,bn1(1),|bn1+1(1),bn1+2(1),...,bn2(1))とする。なお、「|」は、ブロックの区切りを便宜的に表している。
【0108】
演算部101は、次の制約を満たす互いに素な整数m2とw2とを生成し、秘密鍵保持部102に格納する。
【0109】
【数42】
JP0004200259B2_000017t.gif【0110】
そして、演算部101は、b(1)に対して、m2とw2とを用いて2回目のモジュラ乗算変換を施し、
(2)=(b1(2),b2(2),...,bn1(2),|bn1+1(2),bn1+2(2),...,bn2(2)
を生成する。
【0111】
すなわち、j回のモジュラ乗算変換を施した結果、要素がnj個のb(j)=(b1(j),...,bn1(j),|...|bn(j-1)+1(j),...,bnj(j))が得られているとする。演算部101は、この場合に、Sj=b1(j)+b2(j)+...+bnj(j)としたときに、(Sj, bnj+1(j),bnj+2(j),...,bn(j+1)(j))が超増加ベクトルになるように、bnj+1(j),bnj+2(j),...,bn(j+1)(j)を生成して、秘密鍵保持部101に格納する。そして、b(j)を新たに、b(j)=(b1(j),...,bn1(j),|...|bnj+1(j),...,bn(j+1)(j))とする。
【0112】
演算部101は、次の制約を満たす互いに素な整数mj+1とwj+1とを生成し、秘密鍵保持部102に格納する。
【0113】
【数43】
JP0004200259B2_000018t.gif【0114】
そして、演算部101は、b(j)に対して、mj+1とwj+1とを用いてj+1回目のモジュラ乗算変換を施し、
(j+1)=(b1(j+1),...,bn1(j+1)|...|bnj+1(j+1),...,bn(j+1)(j+1)
を生成する。
【0115】
演算部101は、以上の処理をj=k-1になるまで繰り返す。その結果b(k)が得られる。そして、
i=bi(k) i=1,2,...,n
とし、a=(a1,a2,...,an)を作成する。そして、このaを公開鍵として出力する。
【0116】
(3.2暗号化)
第3実施形態における暗号化装置200の処理は、第1実施形態と同じである。
【0117】
(3.3復号)
第3実施形態における復号装置300の処理について説明する。
【0118】
暗号文保持部302は、暗号文Cを格納する。秘密鍵保持部303は、暗号文Cを生成した公開鍵aを生成するときに使用した、互いに素な整数wiとmiの組と、Siと超増加ベクトルb(i)と、ブロック化係数kとを格納する。
【0119】
まず、演算部301は、
(1)=wk-1C mod mk
とする。この演算によって、第k回目のモジュラ演算がはずれるので、
【0120】
【数44】
JP0004200259B2_000019t.gif【0121】
となる。このとき、Sk-1,bn(k-1)+1(k-1),...,bnk(k-1)が、超増加になっているので、演算部301は、xn,xn-1,...,xn(k-1)+1までを、第1実施例で示した易しいナップザック暗号を解く処理を行うことにより、復号することができる。
【0122】
次に、演算部301は、
【0123】
【数45】
JP0004200259B2_000020t.gif【0124】
として、第k-1回目のモジュラ乗算をはずす。ここで、
【0125】
【数46】
JP0004200259B2_000021t.gif【0126】
としているのは、すでに復号を終えた部分を、暗号文Cから引く必要があるからである。
【0127】
そして、演算部301は、C(2)に対し、易しいナップザック暗号を解く処理を行うことにより、xn(k-1),...,xn(k-2)+1までを、復号することができる。
【0128】
以下同様にして、演算部301は、x1まで復号することができる。演算部301は、上述の処理の結果得られたx=(x1,...,xn)を復号した平文として出力する。
【0129】
(変形)
上述の第1~第3実施形態によって、Shamir法による攻撃に強いと考えられるナップザック暗号を生成することができる。
【0130】
しかし、MH型ナップザック暗号は、Shamir法以外にも、Lagarias-Odlyzko法(LO法)と呼ばれる解読法が知られている(J.C.Lagarias and A.M. Odlyzko:"Solving low density subset sum problems", J. ACM, vol. 32, pp.229-246 (1985))。このため、上述の第1~第3実施形態を実際の暗号化処理に使用するためには、LO法による攻撃に対しても強くなければならない。
【0131】
LO法は、ナップザック暗号の解読を、公開鍵aに関係して定められるベクトルを基底とする格子における短いベクトルの探索に帰着させるものである。短いベクトルを探し出すアルゴリズムとしては、既知のLLL法(A. K. Lenstra, H. W. Lenstra, and L. Lovasz, "Factoring polynomials with rational coefficients", Mathematische Annalen, vol.261, pp.515-534, 1982)を使うことができる。これにより短いベクトルが見つかれば、そのベクトルが平文に対応している可能性が非常に高いというものである。このため、平文に対応するベクトルと同等以下の短いベクトルがたくさん存在すれば、平文がこれらの中に紛れて、見つかりにくくなり、LO法による攻撃に対して強くなると考えられる。そして、この考えを用いた暗号方式が、提案されている(林 彬: “ナップザック暗号の改良の試み”,信学技法, Vol. ISEC96-4(1996-05))。
【0132】
提案された方式は、通常のナップザック暗号の公開鍵aが、1つのベクトルa=(a1,a2,...,an)であるのに対し、公開鍵をh行n列の行列Aとするものである。この行列は、h行n列の秘密鍵行列B=(bji)からモジュラ乗算によって作られる。ただし、行列Bは、第i列のどの要素も第1~第i-1列の各最大要素の和よりも大きいものとする(この意味で超増加である)。
【0133】
すなわち、
【0134】
【数47】
JP0004200259B2_000022t.gif【0135】
としたときに、行列Bの要素bjiは、以下の性質を有する。
【0136】
【数48】
JP0004200259B2_000023t.gif【0137】
【数49】
JP0004200259B2_000024t.gif【0138】
そして、通常のナップザック暗号と同様に、互いに素な乗数wと法mとを定め、aji=wbji mod mによって、公開鍵行列
【0139】
【数50】
JP0004200259B2_000025t.gif【0140】
を生成する。すなわち、公開鍵行列は、公開鍵ベクトルを生成するモジュラ乗算を各行ごとに繰り返すことにより作成される。
【0141】
公開鍵行列Aを用いた暗号化は、平文x=(x1,...,xn)に対して、次の操作を施して、整数Cを求め、このCを暗号文とする。
【0142】
【数51】
JP0004200259B2_000026t.gif【0143】
ただし、ci∈{a1i,a1i,...,ahi}における、ajiの添字j=j(i)は、以下のように定める。
【0144】
まず、変数n1を初期値-1とする。そして、変数iをi=nから、i=1まで変化させて、次の処理を行なう。
【0145】
n1=n1+xi, j=(n1 mod h)+ 1
すなわち、xnに適用するa1nから始まって、列方向には、各ビットごとにnから1方向に移動し、行方向には、各ビットに1が現れるたびに一つ下の行へ(最下位行の次は、1行目に戻る)下がっていくようにajiが選択される。
【0146】
図6は、この処理の一例を説明するための図である。本図において、xn-4,xn-3,xn-2,xn-1,xn=(0,1,0,0,1)とする。
【0147】
まず、公開鍵行列Aのa1nとxnとを用いてa1nnの乗算を行なう。ここで、Xnは1であるので、n-1列目では、1行下がって、a2(n-1)を用いてxn-12(n-1)の乗算を行なう。xn-1は0であるので、n-2列目では、行の移動は行なわず、xn-22(n-1)の乗算を行なう。以下同様にして、xiに1が現れるたびに、1行ずつ下がって乗算を行なう。これをx1まで繰り返し、乗算結果の和を暗号文Cとする。
【0148】
上記の処理により作成された暗号文Cの復号は、基本的にMH型ナップザック暗号と同じであるが、秘密鍵行列Bの何行目の要素を比較して、引いていくかを判断しなければならない。
【0149】
すなわち、Cを逆モジュラ乗算して、
C'=w-1 mod m
とする。
【0150】
そして、秘密鍵行列Bのb1nは、xnに適用されるのは明らかであるため、jを1とし、変数iをi=nから、i=1まで変化させて、次の処理を行なう。
【0151】
C'≧bjiを満たす場合は、xiを1とし、C'=C'-bjiとする。そして、j=j mod h+1として、秘密鍵行列の採用する要素の行を1行下に移動する。
【0152】
C'≧bjiを満たさない場合は、xiを0とする。
【0153】
なお、この例では、xiが1であれば、行列中の採用する要素を1行下にずらすようにしている。しかし、暗号化時の公開鍵行列Aと、復号時の秘密鍵行列Bにおいて採用する要素は、互いに対応が取れてれば足り、要素の選択方法は、本例に限られるものではない。
【0154】
以下の実施形態は、上述の実施形態1~3のそれぞれについて、LO法による攻撃に対しても安全性を高めるために、前述の提案された方式を適用したものである。すなわち、実施形態1~3で用いた秘密鍵ベクトルbを、秘密鍵行列Bとしたものであり、基本的な考え方は同じである。このため、主として、上述の実施形態と異なる点について説明するものとする。
【0155】
以下の実施形態において、秘密鍵は、超増加ベクトルbに代え超増加行列
【0156】
【数52】
JP0004200259B2_000027t.gif【0157】
を用いることとする。ただし、超増加行列Bとは、第i列のどの要素も第1~第i-1列の各最大要素の和よりも大きい行列をいう。また、特に混乱のない限り、B=(bji)、あるいは、B=(bj1,bj2,...,bjn)のように表す場合もある。
【0158】
(4.第1実施形態の変形)
(4.1公開鍵生成)
作業用記憶部103は、適当な大きさの乱数のベクトルr=(r1,r2,...,rn)に代え、適当な大きさの乱数の行列R=(rji)を格納する。
【0159】
ただし、
0≦rji<q
【0160】
【数53】
JP0004200259B2_000028t.gif【0161】
を満たすものとする。
【0162】
そして、演算部101は、秘密鍵保持部102に格納してある秘密鍵行列と作業用記憶部103に格納している乱数行列とを用いて、
ji≡bji (mod p)
ji≡rji (mod q), 1≦i≦n,1≦j≦h
を満たすA=(aj1,aj2,...,ajn)を作成する。そして、
【0163】
【数54】
JP0004200259B2_000029t.gif【0164】
を公開鍵行列として出力する。
【0165】
ここで、上記の2式を満たすajiは、
ji≡bjiqq-1+rjipp-1 (mod pq)
と表すことができる。
【0166】
(4.2暗号化)
公開鍵保持部203は、公開鍵aに代え、公開鍵生成装置100によって作成された公開鍵行列A=(aj1,aj2,...,ajn)を保持する。
【0167】
演算部201は、
【0168】
【数55】
JP0004200259B2_000030t.gif【0169】
を計算し、Cを暗号文として出力する。
【0170】
ただし、ci∈{a1i,a1i,...,ahi}における、ajiの添字j=j(i)は、前述のように、以下のように定める。
【0171】
まず、変数n1を初期値-1とする。そして、変数iをi=nから、i=1まで変化させて、次の処理を行なう。
【0172】
n1=n1+xi, j=(n1 mod h)+ 1
【0173】
(4.3復号)
秘密鍵保持部303は、超増加ベクトルbに代え、公開鍵行列Aを生成するときに使用した超増加行列Bを格納する。
【0174】
演算部301は、Cを逆モジュラ乗算して、
C'=w-1 mod m
とする。
【0175】
そして、前述のように、j=1とし、変数iをi=nから、i=1まで変化させて、次の処理を行なう。
【0176】
C'≧bjiを満たす場合は、xiを1とし、C'=C'-bjiとする。そして、j=j mod h +1として、秘密鍵行列の採用する要素の行を1行下に移動する。
【0177】
C'≧bjiを満たさない場合は、xiを0とする。
【0178】
復号装置300は、この結果得られたx=(x1,x2,...,xn)を、復号した平文として出力する。
【0179】
(5.第2実施形態の変形)
(5.1公開鍵生成)
作業用記憶部103は、乱数のベクトルr=(r1,r2,...,rn)に代え、乱数の行列R1=(rji)を格納する。ただし、0≦rji<|L/n|を満たすものとする。
【0180】
演算部101は、
ji'=Lbji+rji
として、B'=(bj1'、bj2',...,bjn')を求め、作業用記憶部103に格納する。
【0181】
次に演算部101は、
【0182】
【数56】
JP0004200259B2_000031t.gif【0183】
を満たすような、整数Uを生成し、秘密鍵保持部102に格納する。
【0184】
そして、演算部101は、適当な大きさの乱数を要素とする行列R2=(Rji)を生成し、作業用記憶部103に格納する。
【0185】
演算部101は、次の関係を満たす、互いに素な整数mとwとを生成し、秘密鍵保持部102に格納する。
【0186】
【数57】
JP0004200259B2_000032t.gif【0187】
演算部101は、aji=w(bji'+URji) mod mを計算し、A=(aj1,aj2,...,ajn)を作成する。そして、このAを公開鍵行列として出力する。
【0188】
(5.2暗号化)
第2実施形態の変形における暗号化装置200の処理は、第1実施形態の変形と同じである。
【0189】
(5.3復号)
第2実施形態の変形における復号化装置200の処理は、
【0190】
【数58】
JP0004200259B2_000033t.gif【0191】
を求めるところまで、第1実施形態と同じである。ただし、biはbjiと表される。
【0192】
その後の処理は、第1実施形態の変形と同様にして、x=(x1,x2,...,xn)を算出し、復号した平文として出力する。
【0193】
(6.第3実施形態の変形)
(6.1公開鍵生成)
本実施形態において、演算部101は、1~nj列の各列の最大要素の和を算出してSjとする。
【0194】
また、演算部101が生成する互いに素な整数mj+1とwj+1とは、
【0195】
【数59】
JP0004200259B2_000034t.gif【0196】
の関係を満たすものとする。そして、1行目からh行目までのg行目について、実施形態3同様のモジュラ乗算を施して
g(j+1)=(bg1(j+1),...,bg n1(j+1)|...|bg nj+1(j+1),...,bk n(j+1)(j+1)
を生成する。
【0197】
演算部101は、以上の処理をj=k-1になるまで繰り返す。
【0198】
そして、
gi=bgi(k) i=1,2,...,n
とし、A=(a11,a12,...,ahn)を作成し、このAを公開鍵行列として出力する。
【0199】
(6.2暗号化)
第3実施形態の変形における暗号化装置200の処理は、第1実施形態の変形と同じである。
【0200】
(6.3復号)
第3実施形態の変形における復号化装置200の処理は、第3実施形態同様に、ブロック毎にモジュラ乗算をはずす。そして、第1実施形態の変形と同様に、得られたxiが1であれば、秘密鍵行列A中の採用する要素を1行下にずらすようにして、復号処理を進める。その結果、得られたx=(x1,...,xn)を復号した平文として出力する。
【0201】
【発明の効果】
上述のように、本発明によれば、Shamir法による攻撃に強いナップザック暗号の公開鍵を生成する装置、および、この公開鍵を用いて暗号文を作成する装置と、この暗号文を復号する装置を実現できる。
【0202】
また、本発明の目的は、暗号化、復号化の処理を速く行なえる公開鍵方式の暗号を取り扱う装置を実現できる。
【図面の簡単な説明】
【図1】は、本発明をインターネットにおける電子メールの送受信時に適用したときの構成を説明するブロック図である。
【図2】は、第1実施形態の公開鍵生成装置100の処理を説明するための説明図である。
【図3】は、第1実施形態の暗号化装置200の処理を説明するための説明図である。
【図4】は、第1実施形態の復号装置300の処理を説明するための説明図である。
【図5】は、第2実施形態の公開鍵生成装置100の演算部101の処理を説明するための説明図である。
【図6】は、公開鍵行列から要素を選択する処理の一例について説明するための説明図である。
【符号の説明】
100…公開鍵生成装置
101…演算部、102…秘密鍵保持部、103…作業用記憶部
200…暗号化装置
201…演算部、202…平文保持部、203…公開鍵保持部
300…復号装置
301…演算部、302…暗号文保持部、303…秘密鍵保持部
図面
【図1】
0
【図2】
1
【図3】
2
【図4】
3
【図5】
4
【図6】
5