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

公開鍵生成装置、暗号化装置および復号装置

国内特許コード P07A012793
整理番号 PA12-047
掲載日 2008年1月18日
出願番号 特願2000-335953
公開番号 特開2002-139995
登録番号 特許第4200259号
出願日 平成12年11月2日(2000.11.2)
公開日 平成14年5月17日(2002.5.17)
登録日 平成20年10月17日(2008.10.17)
発明者
  • 林 彬
出願人
  • 金沢工業大学
発明の名称 公開鍵生成装置、暗号化装置および復号装置
発明の概要 【課題】 Shamir法による攻撃に強いナップザック暗号の公開鍵を生成する装置、および、この公開鍵を用いて暗号文を作成する装置と、この暗号文を復号する装置を実現する。
【解決手段】 公開鍵生成装置100は、超増加ベクトルbと、互いに素な自然数pとqと、乱数ベクトルrを格納し、ai≡bi (mod p),ai≡ri(mod q)を満たすa=(a1,a2,...,an)を公開鍵とする。暗号化装置200は、平文xと公開鍵aの対応する各要素とを乗じた値の和を暗号文Cとする。復号装置300は、C'=C mod pとして、容易なナップザック問題に変換して平文xを得る。
従来技術、競合技術の概要 コンピュータネットワークを利用したデータ通信における代表的な暗号化方式として、共通鍵暗号法と公開鍵暗号法とがある。共通鍵暗号法は、暗号化と復号化とで同じ暗号鍵を使う方法である。公開鍵暗号法は、暗号化と復号化とで違う暗号鍵を使う方法である。公開鍵暗号法では、一方の暗号鍵で暗号化したデータは、もう一方の鍵を使わないと復号できない。このため一方の鍵を公開し、他方の鍵を秘密にしておく。一般に、共通鍵暗号法は、暗号化、復号化の処理速度が速いが、通信相手に安全な方法で暗号鍵を渡すことが難しい。一方の公開鍵暗号方式は、片方の鍵は公開することができるので、相手に暗号鍵を渡すことは非常に楽である。公開鍵暗号方式としては、RSA方式が代表的で、よく知られている。しかし、RSA方式は、暗号化、復号化とも共通鍵方式に比べ、1000倍程度処理速度が遅い。このため、コンピュータネットワークを利用したデータ通信においては、共通鍵の受け渡し、あるいは、比較的少量のデータ伝送等に使われている程度にとどまっている。公開鍵暗号方式で、処理速度が速い方式として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)と、
【数27】
の制約を満たす、互いに素な関係を有する乗数wと法mとを用いる。そして、公開鍵として、ベクトルbにモジュラ乗算を施して得られるベクトルa=(a1,a2,...,an)を利用する。すなわちaとbとの要素間には次の関係がある。ai=wbi mod mナップザック暗号における暗号化は、nビットの平文x=(x1,x2,...,xn)を、次の式にしたがって整数Cに変換し、このCを暗号文とする。
【数28】
iは、超増加ベクトルでないため、一般に、このナップザック暗号を解くのは容易でない。暗号文Cの復号化は、Cを逆モジュラ乗算して、C'=w-1C mod mとする。すると
【数29】
となり、易しいナップザック問題を解くことによって平文を得ることができる(biが超増加ベクトルの場合、ナップザック暗号は容易に解ける)。このように、ナップザック暗号は、計算処理の負荷が少ないため、暗号化、復号化とも、共通鍵暗号方式と同等の処理速度を得ることができる。しかし、ナップザック暗号は、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).)。
産業上の利用分野 本発明は、暗号技術に係り、特に、暗号化、復号化速度が速く、しかも安全性が高い公開鍵暗号方式に関する。
特許請求の範囲 【請求項1】 公開鍵a=(a,a,・・・,a)を生成する公開鍵生成装置であって、 超増加ベクトルb=(b,b,・・・,b)を記憶する手段と、互いに素な自然数pとqとを記憶する手段と、乱数を要素とするベクトルr=(r,r,・・・,r)を記憶する手段と、 前記超増加ベクトルbと、自然数pおよびqと、ベクトルrとを参照して、 a≡b (mod p) a≡r (mod q)を満たすa=(a,a,・・・,a)を生成する演算手段とを備えることを特徴とする公開鍵生成装置: ただし、 0≦r<q
【数1】<EMI LX=0250 HE=014 WI=020 ID=000035 LY=2462>を満たすものとする。
【請求項2】 公開鍵a=(a,a,・・・,a)を用いて、平文xを暗号文Cに変換する暗号化装置であって、 前記公開鍵aを記憶する手段と、前記平文xを記憶する手段と、
【数2】<EMI LX=0250 HE=014 WI=024 ID=000036 LY=0355>を計算する演算手段とを備えることを特徴とする暗号化装置: ただし、前記公開鍵aは、 超増加ベクトルb=(b,b,・・・,b)、 互いに素な自然数pとq、 乱数を要素とするベクトルr=(r,r,・・・,r)、とすると、 a≡b (mod p) a≡r (mod q)を満たし、 0≦r<q
【数3】<EMI LX=0250 HE=014 WI=020 ID=000037 LY=1023>を満たすものとする。
【請求項3】 公開鍵a=(a,a,・・・,a)を用いて暗号化された暗号文Cを平文xに変換する復号装置であって、 前記暗号文Cを記憶する手段と、 公開鍵a=(a,a,・・・,a)を生成するときに用いた超増加ベクトルb=(b,b,・・・,b)と、pとを記憶する手段と、 C'=C mod pを算出し、 bについて、 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)、とすると、 a≡b (mod p) a≡r (mod q)を満たし、 0≦r<q
【数4】<EMI LX=0250 HE=014 WI=020 ID=000038 LY=2411>を満たすものとする。
【請求項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を超えない最大の整数)、 b'=Lb+rとして、b'=(b',b',・・・,b')を求め、
【数5】<EMI LX=0250 HE=014 WI=021 ID=000039 LY=0457>を満たすUと、互いに素な整数mとwとを生成し、記憶するとともに、a=w(b'+UR) mod mを計算して、a=(a,a,・・・,a)を生成する演算手段とを備えることを特徴とする公開鍵生成装置: ただし、
【数6】<EMI LX=0250 HE=014 WI=065 ID=000040 LY=0920>を満たすものとする。
【請求項5】 公開鍵a=(a,a,・・・,a)を用いて、平文xを暗号文Cに変換する暗号化装置であって、 前記公開鍵aを記憶する手段と、前記平文xを記憶する手段と、
【数7】<EMI LX=0250 HE=014 WI=024 ID=000041 LY=1383>を計算する演算手段とを備えることを特徴とする暗号化装置: ただし、前記公開鍵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')(b'=Lb+r)、
【数8】<EMI LX=0250 HE=014 WI=021 ID=000042 LY=1999>を満たすU、 互いに素な整数mとw、とすると、 a=w(b'+UR) mod mを計算することにより算出されたものであり、
【数9】<EMI LX=0250 HE=014 WI=065 ID=000043 LY=2411>を満たすものとする。
【請求項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を超えない最大の整数)、 bについて、 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')(b'=Lb+r)、
【数10】<EMI LX=0250 HE=014 WI=021 ID=000044 LY=1228>を満たすU、 互いに素な整数mとw、とすると、 a=w(b'+UR) mod mを計算することにより算出されたものであり、
【数11】<EMI LX=0250 HE=014 WI=065 ID=000045 LY=1640>を満たすものとする。
【請求項7】 記憶装置と、処理装置と、を有する電子計算機が、公開鍵a=(a,a,・・・,a)を生成する方法であって、 前記記憶装置は、超増加ベクトルb=(b,b,・・・,b)と、互いに素な自然数pとqと、乱数を要素とするベクトルr=(r,r,・・・,r)と、を格納し、 前記処理装置は、 a≡b (mod p) a≡r (mod q)を満たすa=(a,a,・・・,a)を算出して、得られたaを公開鍵とする公開鍵生成方法。 ただし、 0≦r<q
【数12】<EMI LX=0250 HE=014 WI=020 ID=000046 LY=2565>を満たすものとする。
【請求項8】 記憶装置と、処理装置と、を有する電子計算機が、公開鍵a=(a,a,・・・,a)を用いて、平文xを暗号文Cに変換する暗号化方法であって、 前記記憶装置は、前記公開鍵aと、前記平文xと、を格納し、 前記処理装置は、
【数13】<EMI LX=0250 HE=014 WI=024 ID=000047 LY=0509>を計算して、得られたCを暗号文とする暗号化方法。 ただし、前記公開鍵aは、 超増加ベクトルb=(b,b,・・・,b)、 互いに素な自然数pとq、 乱数を要素とするベクトルr=(r,r,・・・,r)、とすると、 a≡b (mod p) a≡r (mod q)を満たし、 0≦r<q
【数14】<EMI LX=0250 HE=014 WI=020 ID=000048 LY=1177>を満たすものとする。
【請求項9】 記憶装置と、処理装置と、を有する電子計算機が、公開鍵a=(a,a,・・・,a)を用いて暗号化された暗号文Cを平文xに変換する復号方法であって、 前記記憶装置は、前記暗号文Cと、公開鍵a=(a,a,・・・,a)を生成するときに用いた超増加ベクトルb=(b,b,・・・,b)と、pと、を格納し、 前記処理装置は、 C'=C mod pを算出し、 bについて、 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)、とすると、 a≡b (mod p) a≡r (mod q)を満たし、 0≦r<q
【数15】<EMI LX=0250 HE=014 WI=020 ID=000049 LY=2513>を満たすものとする。
【請求項10】 公開鍵行列
【数16】<EMI LX=0250 HE=028 WI=051 ID=000050 LY=0303>を生成する公開鍵生成装置であって、 超増加行列
【数17】<EMI LX=0250 HE=028 WI=051 ID=000051 LY=0766>を記憶する手段と、 互いに素な自然数pとqとを記憶する手段と、乱数を要素とする行列
【数18】<EMI LX=0250 HE=028 WI=050 ID=000052 LY=1228>とを記憶する手段と、 aji≡bji (mod p) aji≡rji (mod q)を満たすA=(aj1,aj2,・・・,ajn)を生成する演算手段とを備えることを特徴とする公開鍵生成装置: ただし、 0≦rji<q
【数19】<EMI LX=0250 HE=014 WI=026 ID=000053 LY=1948>を満たすものとする(ただし、bmax=max{b1i,b2i,・・・,bhi})。
【請求項11】 公開鍵行列A=(aj1,aj2,・・・,ajn)を用いて、平文xを暗号文Cに変換する暗号化装置であって、 前記公開鍵行列Aを記憶する手段と、前記平文xを記憶する手段と、
【数20】<EMI LX=0250 HE=014 WI=024 ID=000054 LY=2462>を計算する演算手段とを備えることを特徴とする暗号化装置: ただし、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】<EMI LX=0250 HE=029 WI=152 ID=000055 LY=0509> 互いに素な自然数pとq、 乱数を要素とする行列
【数22】<EMI LX=0250 HE=029 WI=152 ID=000056 LY=0971> aji≡bji (mod p) aji≡rji (mod q)を満たし、 0≦rji<q
【数23】<EMI LX=0250 HE=014 WI=026 ID=000057 LY=1537>を満たすものとする(ただし、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を算出し、 bjiについて、j=1とし、 1)C’≧bjiを満たす場合は、xを1とし、C'をC'-bjiとする、 2)C'≧bjiを満たさない場合は、xを0とする、という処理を逆算カウンタ変数iがnから1になるまで繰り返し、得られたx=(x,x,・・・,x)を平文とする演算手段とを備えることを特徴とする復号装置: ただし、前記公開鍵行列Aは、 超増加行列
【数24】<EMI LX=0250 HE=029 WI=152 ID=000058 LY=0252> 互いに素な自然数pとq、 乱数を要素とする行列
【数25】<EMI LX=0250 HE=029 WI=152 ID=000059 LY=0714> aji≡bji (mod p) aji≡rji (mod q)を満たし、 0≦rji<q
【数26】<EMI LX=0250 HE=014 WI=026 ID=000060 LY=1280>を満たすものとする(ただし、bmax=max{b1i,b2i,・・・,bhi})。
【請求項13】 公開鍵行列
【数27】<EMI LX=0250 HE=028 WI=051 ID=000061 LY=1691>を生成する公開鍵生成装置であって、 超増加行列
【数28】<EMI LX=0250 HE=028 WI=051 ID=000062 LY=2154>を記憶する手段と、 整数Lと、0≦rij<|L/n|を満たす乱数を要素とする行列
【数29】<EMI LX=0250 HE=028 WI=050 ID=000063 LY=0252>と、乱数を要素とする行列
【数30】<EMI LX=0250 HE=028 WI=054 ID=000064 LY=0663>とを記憶する手段と、 bji'=Lbji+rjiとして、bji'を求め、
【数31】<EMI LX=0250 HE=014 WI=038 ID=000065 LY=1126>を満たすUと、互いに素な整数mとwとを生成し、記憶するとともに、aji=w(b'+URji) mod mを計算して、公開鍵行列A=(aj1,aj2,・・・,ajn)を生成する演算手段とを備えることを特徴とする公開鍵生成装置: ただし、
【数32】<EMI LX=0250 HE=014 WI=070 ID=000066 LY=1588>を満たすものとする。
【請求項14】 公開鍵行列A=(aj1,aj2,・・・,ajn)を用いて、平文xを暗号文Cに変換する暗号化装置であって、 前記公開鍵行列Aを記憶する手段と、前記平文xを記憶する手段と、
【数33】<EMI LX=0250 HE=014 WI=024 ID=000067 LY=2051>を計算する演算手段とを備えることを特徴とする暗号化装置: ただし、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】<EMI LX=0250 HE=029 WI=152 ID=000068 LY=0252> 整数L、 0≦rij<|L/n|を満たす乱数を要素とする行列
【数35】<EMI LX=0250 HE=029 WI=152 ID=000069 LY=0714> 乱数を要素とする行列
【数36】<EMI LX=0250 HE=029 WI=152 ID=000070 LY=1126> bji'(bji'=Lbji+rji)、
【数37】<EMI LX=0250 HE=014 WI=038 ID=000071 LY=1537>を満たすU、 互いに素な整数mとw、とすると、 aji=w(bji'+URji) mod mを計算することにより算出されたものであり、
【数38】<EMI LX=0250 HE=014 WI=070 ID=000072 LY=1948>を満たすものとする。
【請求項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|とし、 bjiについて、 1)C'''≧bjiを満たす場合は、xを1とし、C'''をC'''-bjiとする、 2)C'''≧bjiを満たさない場合は、xを0とする、という処理を逆算カウンタ変数iがnから1になるまで繰り返し、得られたx=(x,x,・・・,x)を平文とする演算手段とを備えることを特徴とする復号装置。 ただし、公開鍵行列Aは、 超増加行列
【数39】<EMI LX=0250 HE=029 WI=152 ID=000073 LY=0457> 整数L、 0≦rij<|L/n|を満たす乱数を要素とする行列
【数40】<EMI LX=0250 HE=029 WI=152 ID=000074 LY=0920> 乱数を要素とする行列
【数41】<EMI LX=0250 HE=029 WI=152 ID=000075 LY=1331> bji'(bji'=Lbji+rji)、
【数42】<EMI LX=0250 HE=014 WI=038 ID=000076 LY=1742>を満たすU、 互いに素な整数mとw、とすると、 aji=w(bji'+URji) mod mを計算することにより算出されたものであり、
【数43】<EMI LX=0250 HE=014 WI=070 ID=000077 LY=2154>を満たすものとす。
【請求項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】<EMI LX=0250 HE=014 WI=056 ID=000078 LY=0766>を満たす互いに素なmとwとを生成し記憶する。 b(j)=w(j-1) mod mを算出して、ベクトルb(j)とする。
【数45】<EMI LX=0250 HE=014 WI=023 ID=000079 LY=1126>を算出して、記憶する。
【請求項17】 公開鍵a=(a,a,・・・,a)を用いて、平文xを暗号文Cに変換する暗号化装置であって、 前記公開鍵aを記憶する手段と、前記平文xを記憶する手段と、
【数46】<EMI LX=0250 HE=014 WI=024 ID=000080 LY=1588>を計算する演算手段とを備えることを特徴とする暗号化装置。 ただし、公開鍵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)を生成する。
【数47】<EMI LX=0250 HE=014 WI=056 ID=000081 LY=0252>を満たす互いに素なmとwとを生成する。 b(j)=w(j-1) mod mを算出して、ベクトルb(j)とする。
【数48】<EMI LX=0250 HE=014 WI=023 ID=000082 LY=0612>を算出する。
【請求項18】 公開鍵行列
【数49】<EMI LX=0250 HE=028 WI=051 ID=000083 LY=0971>を生成する公開鍵生成装置であって、 ブロック化係数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】<EMI LX=0250 HE=014 WI=070 ID=000084 LY=2154>を満たす互いに素なmとwとを生成し記憶する。 b (j)=w (j-1) mod mを算出して、行列B(j)とする。
【数51】<EMI LX=0250 HE=014 WI=040 ID=000085 LY=2513>を算出して、記憶する。
【請求項19】 公開鍵行列A=(ag1,ag2,・・・,agn)を用いて、平文xを暗号文Cに変換する暗号化装置であって、 前記公開鍵行列Aを記憶する手段と、前記平文xを記憶する手段と、
【数52】<EMI LX=0250 HE=014 WI=024 ID=000086 LY=0406>を計算する演算手段とを備えることを特徴とする暗号化装置: ただし、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、 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)を生成する。
【数53】<EMI LX=0250 HE=014 WI=070 ID=000087 LY=1742>を満たす互いに素なmとwとを生成する。 b (j)=w (j-1) mod mを算出して、行列B(j)とする。
【数54】<EMI LX=0250 HE=014 WI=040 ID=000088 LY=2102>を算出する。
産業区分
  • その他通信
  • 電信
国際特許分類(IPC)
Fターム
出願権利状態 権利存続中
ライセンスをご希望の方、特許の内容に興味を持たれた方は、「問合せ先」まで直接お問合せ下さい。


PAGE TOP

close
close
close
close
close
close
close