Nova Patents
JPH1039751A

Communication by public key cipher and authentication method as well as apparatus therefor

Abstract

[Task] An object of the present invention is to provide a communication and authentication method using public key cryptography, which is faster and stronger against broadcast communication attacks, and a device thereof.

Solution.When encrypting plaintext, prime ideal P and prime ideal Q in the integer ring O on the algebra are generated, these are used as the private key, and the product N of these is generated as the public key, and these are used when decrypting. The gist is to use the Chinese Remainder Theorem for the remainder operation using the private key as the method and the remainder operation using the public key as the method based on the result of the remainder operation.

Term

Term ended

Projected expiry passed 20 July 2016, 10.2 years ago.

  1. Priority and filed
  2. Published
  3. Projected expiry
  4. Today

44 claims: 36 independent, 8 dependent

  1. 1
    【特許請求の範囲】 【請求項1】 公開鍵暗号方式を用いた通信または認証に使用される公開鍵暗号の鍵生成方法であって、 代数体上の整数環における2つの素イデアルをそれぞれ秘密鍵として生成すると共に、これら2つの素イデアルの積を公開鍵として生成することを特徴とする公開鍵暗号の鍵生成方法。
  2. 2
    【請求項2】 前記代数体は円分体、2次体、アイゼンシュタイン体若しくはガウス体の内のいずれかを利用したものであることを特徴とする請求項1記載の公開鍵暗号の鍵生成方法。
  3. 3
    【請求項3】 公開鍵暗号方式を用いた通信または認証を伴う通信を行う通信装置であって、 暗号化または復号化に際して、有理数体に平方因子を持たない有利整数の平方根を添加した体(2次体)において、平方剰余記号の演算を行うことを特徴とする通信装置。
  4. 4
    【請求項4】 公開鍵暗号方式を用いた通信または認証を伴う通信を行う通信装置であって、 暗号化または復号化に際して、有理数体に1の原始三乗根を添加した体(アイゼンシュタイン体)において三乗剰余記号の演算を行うことを特徴とする通信装置。
  5. 5
    【請求項5】 公開鍵暗号方式を用いた通信または認証を伴う通信を行う通信装置であって、 暗号化または復号化に際して、有理数体に1の原始四乗根を添加した体(第1のガウス体)において四乗剰余記号の演算を行うことを特徴とする通信装置。
  6. 6
    【請求項6】 公開鍵暗号方式を用いた通信または認証を伴う通信を行う通信装置であって、 暗号化または復号化に際して、有理数体に-1の平方根を添加した体(第2のガウス体)において平方剰余記号の演算を行うことを特徴とする通信装置。
  7. 7
    【請求項7】 公開鍵暗号方式を用いた通信または認証を伴う通信を行う通信装置であって、 暗号化または復号化に際して、有限体上の多項式環の最大公約数を求めることを特徴とする通信装置。
  8. 8
    【請求項8】 入力される平文を暗号化して送信する送信装置と、この送信装置から送信された暗号文を復号化して平文を出力する受信装置とを有する暗号通信装置であって、 前記送信装置は、暗号化に際し、受信装置側の公開鍵を法として、代数体の剰余類の範囲内の平文に対する剰余演算を伴う暗号化を行い、 前記受信装置は、受信暗号文に対して前記2つの秘密鍵を法とする剰余演算およびこの剰余演算の結果をもとに前記公開鍵を法とする剰余演算を中国人の剰余定理を用いて、復号化を行うことを特徴とする暗号通信装置。
  9. 9
    【請求項9】 公開鍵暗号方式を用いて認証を伴う通信を行うとき、送信に際して、送信者は代数体上の整数環における2つの素イデアルをそれぞれ秘密鍵として生成し、これら秘密鍵で自ら暗号化した後に、ハッシュ化処理を行い生成した認証子と平文の認証文とを対にして受信者に送信し、受信者はこの受信した認証子を自らの公開鍵で復号化したものと、認証文をハッシュ化処理したものとを照合することにより、送信者が受信者に対して個人認証を行うことを特徴とする通信装置。
  10. 10
    【請求項10】 円分体において、任意の自然数データm c についてオイラー関数値データφ(m c )を演算するオイラー関数値演算手段と、 任意のデータを入力とし、この入力データを基に素数データp c を生成する素数生成手段と、 前記オイラー関数値データφ(m c )を用いて前記素数データp c の素イデアル性を判定し、素イデアルであると判定されたときには当該値p c を第1の秘密鍵データとし、素イデアルではないと判定されたときには再度前記素数生成手段で素数データを生成し判定を繰り返す判定手段と、 この判定手段で素数データの値p c と異なる値q c が得られたときには当該値q c を第2の秘密鍵データとする秘密鍵生成手段と、 前記値p c と値q c との積を演算して得られた値n c を第1の公開鍵データとする公開鍵生成手段と、を有することを特徴とする公開鍵暗号の鍵生成装置。
  11. 11
    【請求項11】 2次体において、二乗因子を持たない任意の有理整数データm s について4を法とする剰余を計算し、計算値が1となる場合は値m s を書き込み、計算値が1以外の場合は値m s を4倍した値を書き込んだ判別式の値Dを得る判別値獲得手段と、 任意のデータを入力とし、この入力データを基に素数データp s を生成する素数生成手段と、 前記判別式の値Dの素数データp s に対する平方剰余記号の計算値が-1となるか否かを判定し、-1となった場合は当該値p s を第1の秘密鍵データとし、-1とならない場合には再度前記素数生成手段で素数データを生成し判定を繰り返す判定手段と、 この判定手段で前記値p s と異なる値q s が得られたときには当該値q s を第2の秘密鍵データとする秘密鍵生成手段と、 前記値p s と値q s とを乗じた値n s を計算して第1の公開鍵データとする公開鍵生成手段と、を有することを特徴とする公開鍵暗号の鍵生成装置。
  12. 12
    【請求項12】 アイゼンシュタイン体において、惰性もしくは分解する有理素数の組である値p e と値q e とを入力する入力手段と、 惰性する素数の場合はP e =p e 、Q e =q e とし、分解する素数のばあいはρを1の原始3乗根として、 値p e に対して、p e =a 2 -ab+b 2 を満たす有理整数の組(a,b)をa≡1(mod 3),b≡0(mod 3)の条件のもとで求め、P e =(a+ρb)を第1の秘密鍵とする第1の秘密鍵生成手段と、 値q e に対して、q e =c 2 -cd+d 2 を満たす有理整数の組(c,d)をc≡1(mod 3), d≡0(mod 3)の条件のもとで求め、Q e =(c+ρd)を第2の秘密鍵とする第2の秘密鍵生成手段と、 前記P e とQ e との積を求め第1の公開鍵とする公開鍵生成手段と、を有することを特徴とする公開鍵暗号の鍵生成装置。
  13. 13
    【請求項13】 ガウス体において、惰性もしくは分解する有理素数の組である値p g と値q g とを入力する入力手段と、 惰性する素数の場合はP g =p g 、Q g =q g とし、分解する素数のばあいはiを1の原始4乗根として、 値p g に対して、p g =a 2 +b 2 を満たす有理整数の組(a,b)を、a≡1(mod 4),b≡0(mod 4)、あるいはa≡3(mod 4),b≡2 (mod4)のいずれかの条件のもとで求め、P g =(a+ib)を求め第1の秘密鍵とする第1の秘密鍵生成手段と、 値q g に対して、q g =c 2 +d 2 を満たす有理整数の組(c,d)を、c≡1(mod 4),d≡0(mod 4)、あるいはc≡3(mod 4),d≡2 (mod4)のいずれかの条件のもとで求め、Q g =(c+id)を求め第2の秘密鍵とする第2の秘密鍵生成手段と、 前記P g とQ g との積を求め第1の公開鍵とする公開鍵生成手段と、を有することを特徴とする公開鍵暗号の鍵生成装置。
  14. 14
    【請求項14】 代数体上の整数環のイデアルに対して、その剰余類を一意的に決定するに際して、 m次円分体の場合は、公開鍵を素数イデアルの積Nとし、ζを1の原始m乗根とすると、φ(m)次元Z平面において原点とベクトル N,ζN,5 2 N,...,ζφ(m)-1N で張られる超平行体の内部と境界上の整数点を取り、 2次体の場合は、公開鍵を素数イデアルの積Nとし、ωを2次体の整数の基底とすると、2次元Z平面において原点とベクトル N,ωN で張られる平行四辺形の内部と境界上の整数点を取り、 アイゼンシュタイン体の場合は、公開鍵を素数イデアルの積N=(a+ρb)とすると、4点(0.0),(a,b),(-b,a-b),(a-b,a)で張られる平行四辺形の内部と境界上の整数点を取り、 第1のガウス体および第2のガウス体の場合は、公開鍵を素数イデアルの積N=(a+ib)とすると、4点(0.0),(a,b),(-b,a),(a-b,a+b)で張られる平行四辺形の内部と境界上の整数点を取ることを特徴とする請求項8に記載の暗号通信装置。
  15. 15
    【請求項15】 代数体上の整数環のイデアルに対して、所定の剰余類に対して剰余演算を行うに際して、 m次円分体の場合は、公開鍵を惰性する素数の積nとすると、φ(m)次元Z平面において、ベクトル各成分の成分で有理整数nによる剰余演算を行い、 2次体の場合は、公開鍵を惰性する素数の積nとすると、2次元Z平面において、ベクトル各成分の成分で有理整数nによる剰余演算を行い、 アイゼンシュタイン体の場合は、公開鍵を惰性する素数の積nとすると、2次元Z平面において、ベクトル各成分の成分で有理整数nによる剰余演算を行い、公開鍵を分解する素イデアルの積N=(a+ρb)とすると、2次元Z平面において、点(x,y)はガウス記号を[ ]とし,n e =a 2 -ab+b 2 とすると式 【数1】 による剰余演算を行い、第1のガウス体および第2のガウス体の場合は、公開鍵を惰性する素数の積nとすると、2次元Z平面において、ベクトル各成分の成分で有理整数nによる剰余演算を行い、公開鍵を分解する素イデアルの積N=(a+ρb)とすると、2次元Z平面において、点(x,y)は、ガウス記号[ ]とし、n g =a 2 +b 2 とすると式 【数2】 による剰余演算を行うことを特徴とする請求項8記載の暗号通信装置。
  16. 16
    【請求項16】 アイゼンシュタイン体においては、ユークリッドの互除演算とpおよび1-pによる除算を反復することにより3乗剰余記号を計算し、第1のガウス体においては、ユークリッドの互除演算と1+i,-1およびiによる除算を反復することにより4乗剰余記号を計算し、第2のガウス体においては、ユークリッドの互除演算と1+i,-1およびiによる除算を反復することにより平方剰余記号を計算することを特徴とするアイゼンシュタイン体,第1のガウス体,および第2のガウス体におけるべき乗剰余記号を用いることを特徴とする請求項8記載の暗号通信装置。
  17. 17
    【請求項17】 円分体において、値がMである平文データ、値がn c である第1の公開鍵データおよび任意の自然数データm c である第2の公開鍵データに対し、これらから前記平文データに該当する値がM c である暗号文データを生成する暗号化装置であって、 利用する体の次数に係り第2の公開鍵データのオイラー関数値r c を求めるオイラー関数値演算手段と、 前記平文データを値n c の剰余類の範囲に収まるように、この元に対応付け各次元に対応するr c 個の成分をメモリに順次格納する格納手段と、 これらメモリに順次格納された各次元を成分とする元に対して法n c のもとでm c 乗演算を施す演算手段と、 この演算手段の各演算結果をまとめて全体を元の値がM c である暗号文データとする統合手段と、を有することを特徴とする公開鍵暗号による暗号化装置。
  18. 18
    【請求項18】 2次体において、値がMである平文データ、値がN s である第1の公開鍵データおよび値がm s である第2の公開鍵データに対し、これらから前記平文データに該当する値がM s である暗号文データを生成する暗号化方法であって、 前記平文データを切り出して得られる平文ブロックM 0 ,M 1 に対して、2次体の元a+b√m s を(a,b)とベクトル表現するとき、式(C 0 ,C 1 )≡(M 0 ,M 1 )(M 0 +2B 0 ,M 1 +2B 1 )mod N(ただし(B 0 ,B 1 )はある整数の組)によって暗号化することを特徴とする公開鍵暗号による暗号化方法。
  19. 19
    【請求項19】 アイゼンシュタイン体において、値がMである平文データ、値がN e である第1の公開鍵データおよび値が3 e である第2の公開鍵データに対し、これらから前記平文データに該当する値がM s である暗号文データを生成する暗号化方法であって、 前記平文データを切り出して得られる平文ブロックM 0 ,M 1 に対して、アイゼンシュタイン体の元a+bρを(a,b)とベクトル表現するとき、式(C 0 ,C 1 )≡(M 0 ,M 1 )(M 0 +2B 0 -B 1 ,M 1 +B 0 +B 1 ) (M 0 +B 0 -B 1 ,M 1 +B 0 ) mod N e (ただし(B 0 ,B 1 )はある整数の組)によって暗号化を行うことを特徴とする公開鍵暗号による暗号化方法。
  20. 20
    【請求項20】 第1のガウス体において、前記暗号化は、暗号化処理の後に、三乗剰余記号 【数3】 を計算することを特徴とする請求項19記載の公開鍵暗号による暗号化方法。
  21. 21
    【請求項21】 値がMである平文データ、値がN g である第1の公開鍵データおよび値が3 g である第2の公開鍵データに対し、これらから前記平文データに該当する値がM g である暗号文データを生成する暗号化方法であって、 前記平文データを切り出して得られる平文ブロックM 0 ,M 1 に対して、第1のガウス体の元a+biを(a,b)とベクトル表現するとき、式 (C 0 ,C 1 )≡(M 0 ,M 1 )(M 0 +2B 0 ,M 1 +2B 1 )(M 0 +B 0 -B 1 ,M 1 +B 0 +B 1 )(M 0 +B 0 +B 1 ,M 1 -B 0 +B 1 ) mod N g (ただし(B 0 ,B 1 )はある整数の組)によって暗号化を行うことを特徴とする公開鍵暗号による暗号化方法。
  22. 22
    【請求項22】 前記暗号化は、暗号化処理の後に、四剰余記号 【数4】 を計算することを特徴とする請求項18記載の公開鍵暗号による暗号化方法。
  23. 23
    【請求項23】 第2のガウス体において、値がMである平文データ、値がN G である第1の公開鍵データおよび値が-4 G である第2の公開鍵データに対し、これらから前記平文データに該当する値がM G である暗号文データを生成する暗号化方法であって、 前記平文データを切り出して得られる平文ブロックM 0 ,M 1 に対して、第2のガウス体の元a+biを(a,b)とベクトル表現するとき、式 (C 0 ,C 1 )≡(M 0 ,M 1 )(M 0 +2B 0 ,M 1 +2B 1 ) mod N G によって暗号化を行うことを特徴とする公開鍵暗号による暗号化方法。
  24. 24
    【請求項24】 前記暗号化は、暗号化処理の後に、平方剰余記号 【数5】 ならびに、平文Mと(C+B 2 )/Bの各成分の大小関係δを計算することを特徴とする請求項23記載の公開鍵暗号による暗号化方法。
  25. 25
    【請求項25】 暗号文データと体の次元値のデータと第1の秘密鍵データ、第2の秘密鍵データおよび第1の公開鍵データとを入力し、前記暗号文データに対応する値がMである平文データを生成する公開鍵暗号における復号化方法であって、 前記暗号文データに対して、前記第1の秘密鍵データを法とする剰余演算と、前記第2の秘密鍵データを法とする剰余演算とをそれぞれ別個に実施し、これら2つの実施結果に対して前記第1の公開鍵データを法とする剰余演算を中国人の剰余定理を用いて、それぞれ実施することにより利用した体の元を求め、前記値がMである平文データを得ることを特徴とする公開鍵暗号による復号化方法。
  26. 26
    【請求項26】 円分体において、値がM c である暗号文データと、代数体の次元の値を示す数値データと、値がp c である第1の秘密鍵データと、値がq c である第2の秘密鍵データと、値がn c である第1の公開鍵データと、値がm c である任意の自然数データを第2の公開鍵データとして入力し、前記暗号文データに対応する値がMである平文データを生成する公開鍵暗号における復号化装置であって、 前記暗号文データに対し前記体の各次元値を構成するデータブロック毎に順次メモリに格納する格納手段と、 第1の体の元の値X c1 をm c 乗した値からM c を減じた値に対して、値p c を法とする剰余が0となるようなX c1 の値を求める第1の演算手段と、 第2の体の元の値X c2 をm c 乗した値からM c を減じた値に対して、値q c を法とする剰余が0となるようなX c2 の値を求める第2の演算手段と、 中国人の剰余定理に基づき前記第1の演算手段および第2の演算手段で演算された前記データ群を成分とする2つの体の元に対してイデアルn c を法とする体の元を求める第3の演算手段と、 この第3の演算手段で求められた拡大体の各成分データを順次連結し、値がMである平文データとする連結手段と、を有することを特徴とする公開鍵暗号による復号化装置。
  27. 27
    【請求項27】 2次体において、値がCである暗号文データ、値がP s である第1の秘密鍵データ、値がQ s である第2の秘密鍵データ、値がN s である第1の公開鍵データおよび値がm s である第2の公開鍵データとを入力し、前記暗号文データに対応する値がMである平文データを生成する公開鍵暗号における復号化方法であって、 前記平文データを切り出して得られる平文ブロックM 0 ,M 1 に対応する暗号文ブロックC 0 ,C 1 およびB 0 ,B 1 に対して、EをC 0 +(√m s )C 1 を意味するものとするとき、それぞれ、式x 2 +2Bx-E≡0 mod P s の解M Ps =(M 0P ,M 1P )と、式x 2 +2Bx-E≡0 mod Q s の解M Qs =(M 0Q ,M 1Q )とを求め、さらにM Ps ,M Qs からイデアルN s を法とする数Mを中国人剰余の定理により求め、当該Mを平文データとして得ることを特徴とする公開鍵暗号による復号化方法。
  28. 28
    【請求項28】 アイゼンシュタイン体において、値がCである暗号文データ、値がP e である第1の秘密鍵データ、値がQ e である第2の秘密鍵データ、値がN e である第1の公開鍵データおよび値が3 e である第2の公開鍵データとを入力し、前記暗号文データに対応する値がMである平文データを生成する公開鍵暗号における復号化方法であって、 前記平文データを切り出して得られる平文ブロックM 0 ,M 1 に対応する暗号文ブロックC 0 ,C 1 およびB 0 ,B 1 に対して、それぞれ、式x 3 +3Bx 2 +3B 2 x-E≡0 mod P e の解M Pe =(M 0P ,M 1P )と、式x 3 +3Bx 2 +3B 2 x-E≡0 mod Q e の解M Qe =(M 0Q ,M 1Q )とを求め、さらにM Pe ,M Qe からイデアルN e を法とする数Mを中国人剰余の定理により求め、当該Mを平文データとして得ることを特徴とする公開鍵暗号による復号化方法。
  29. 29
    【請求項29】 前記復号化は、復号化処理の途中において、三乗剰余記号(M Pe /N) 3 、(M Qe /N) 3 の値を計算し、所定の対応表に従ってCに対応する暗号文の候補を絞り、さらにイデアルNを法とする数Mを求め、このMについて解の正当性を検証することを特徴とする請求項28記載の公開鍵暗号による復号化方法。
  30. 30
    【請求項30】 第1のガウス体において、値がCである暗号文データ、値がP g である第1の秘密鍵データ、値がQ g である第2の秘密鍵データ、値がN g である第1の公開鍵データおよび値が4 g である第2の公開鍵データとを入力し、前記暗号文データに対応する値がMである平文データを生成する公開鍵暗号における復号化方法であって、 前記平文データを切り出して得られる平文ブロックM 0 ,M 1 に対応する暗号文ブロックC 0 ,C 1 およびB 0 ,B 1 に対して、それぞれ、式x 4 +4Bx 3 +6B 2 x 2 +4B 3 x-E≡0 mod P g の解M Pg =(M 0P ,M 1P )と、式x 4 +4Bx 3 +6B 2 x 2 +4B 3 x-E≡0 mod Q g の解M Qg =(M 0Q ,M 1Q )とを求め、さらにM Pg ,M Qg からイデアルN g を法とする数Mを中国人剰余の定理により求め、当該Mを平文データとして得ることを特徴とする公開鍵暗号による復号化方法。
  31. 31
    【請求項31】 前記復号化は、復号化処理の途中において、四乗剰余記号(M Pg /N) 4 、(M Qg /N) 4 の値を計算し、所定の対応表に従ってCに対応する暗号文の候補を絞り、さらにイデアルNを法とする数Mを求め、このMについて解の正当性を検証することを特徴とする請求項30記載の公開鍵暗号による復号化方法。
  32. 32
    【請求項32】 第2のガウス体において、値がCである暗号文データ、値がP G である第1の秘密鍵データ、値がQ G である第2の秘密鍵データ、値がN G である第1の公開鍵データおよび値が3 G である第2の公開鍵データとを入力し、前記暗号文データに対応する値がMである平文データを生成する公開鍵暗号における復号化方法であって、 前記平文データを切り出して得られる平文ブロックM 0 ,M 1 に対応する暗号文ブロックC 0 ,C 1 およびB 0 ,B 1 に対して、それぞれ、式x 2 +2Bx-E≡0 mod P G の解M PG =(M 0P ,M 1P )と、式x 2 +2Bx-E≡0 mod Q G の解M QG =(M 0Q ,M 1Q )とを求め、さらにM PG ,M QG からイデアルN G を法とする数Mを中国人剰余の定理により求め、当該Mを平文データとして得ることを特徴とする公開鍵暗号による復号化方法。
  33. 33
    【請求項33】 前記復号化は、復号化処理の途中において、平方剰余記号(M PG /N) 2 、(M QG /N) 2 の値を計算し、所定の対応表に従ってCに対応する暗号文の候補を絞り、さらにイデアルNを法とする数Mを求め、このMと(C+B 2 )/Mの各成分の大小関係がδと一致することを検証することを特徴とする請求項32記載の公開鍵暗号による復号化方法。
  34. 34
    【請求項34】 認証文データ、第1の秘密鍵データ、第2の秘密鍵データ、第1の公開鍵データおよび第2の公開鍵データとから認証文データに該当する暗号化認証文データを生成する公開鍵暗号における認証文生成装置であって、 前記認証文データをハッシュ関数を用いてハッシュ化するハッシュ化手段と、 このハッシュ化手段でハッシュ化したハッシュ化データに対し、第1の公開鍵の値である剰余類の範囲に収まるように、拡大体の元に対応付け、各次元成分に対応する成分をメモリに順次格納する格納手段と、 拡大体の元に対して、前記第1の秘密鍵データを法とする剰余演算と、前記第2の秘密鍵データを法とする剰余演算とを、それぞれ別個に実施し、これら2つの実施結果に対して、第1の公開鍵データを法とする剰余演算を中国人の剰余定理を用いて、それぞれ実施することにより拡大体の元を求める演算手段と、 この演算手段で求めた各次元成分を順次読み出すことにより、前記暗号化認証文データを生成する暗号化認証文生成手段と、を有することを特徴とする公開鍵暗号による暗号化認証文生成装置。
  35. 35
    【請求項35】 円分体において、値がTである認証文データ、値がr c である拡大体の次数データ、値がp c である第1の秘密鍵データ、値がq c である第2の秘密鍵データと、値がn c である第1の公開鍵データおよび値がm c である任意の素数データまたは任意の素数が自然数べき乗されたデータを第2の公開鍵データとから、認証文データに該当する値がT c である暗号化認証文データを生成する公開鍵暗号における認証文生成装置であって、 前記認証文データをハッシュ関数を用いてハッシュ化するハッシュ化手段と、 このハッシュ化手段でハッシュ化された認証文データを、各ブロックがn c の値である剰余類の範囲に収まるように拡大体の元に対応付け、各次元成分に対応するr c 個の成分をメモリに順次格納する格納手段と、 ある未知の拡大体の元の値X c1 をm c 乗した値からT c を減じた値に対して、値p c を法とする剰余が0となるようなX c1 の値を求める第1の演算手段と、 ある未知の拡大体の元の値X c2 をm c 乗した値からT c を減じた値に対して、値q c を法とする剰余が0となるようなX c2 の値を求める第2の演算手段と、 中国人の剰余定理に基づき、前記第1の演算手段および第2の演算手段で演算されたデータ群を成分とする2つの拡大体の元に対して、イデアルn c を法とする拡大体の元をそれぞれ求める第3の演算手段と、 この第3の演算手段で求められた拡大体の各成分データを順次連結し値がT c である暗号化認証文データとする連結手段と、を有することを特徴とする公開鍵暗号による暗号化認証文生成装置。
  36. 36
    【請求項36】 2次体において、値がMである認証文データ、値がP s である第1の秘密鍵データ、値がQ s である第2の秘密鍵データと、値がN s である第1の公開鍵データおよび値がm s である第2の公開鍵データとから、認証文データに該当する値がM s である暗号化認証文データを生成する公開鍵暗号における認証文生成装置であって、 認証文をハッシュ関数hでハッシュ化し、その結果をハッシュ化認証子h(M)とする認証文ハッシュ化手段と、 前記認証子h(M)の先頭から、剰余類の範囲内の2次体の元の2つの次元成分に対応する2個のブロックを切り出す認証子分割手段と、 秘密鍵P s ,Q s を用い、式x 2 -h(M)≡0 (mod N s )の解の1個h(C)=(h(C) 0 ,h(C) 1 )を求める認証子暗号化手段と、を有することを特徴とする公開鍵暗号による暗号化認証文生成方法。
  37. 37
    【請求項37】 アイゼンシュタイン体において、値がMである認証文データ、値がp e である第1の秘密鍵データ、値がq e である第2の秘密鍵データと、値がn e である第1の公開鍵データおよび値がm e である第2の公開鍵データとから、認証文データに該当する値がM e である暗号化認証文データを生成する公開鍵暗号における認証文生成方法であって、 認証文をハッシュ関数hでハッシュ化し、その結果をハッシュ化認証子h(M)とする認証文ハッシュ化手段と、 認証子h(M)の先頭から剰余類の範囲内の2次体の元の2つの次元成分に対応する2個のブロックを切り出す出認証子分割手段と、 秘密鍵P e ,Q e を用い、式x 3 -h(M)≡0(mod N e )の解の1個h(C)=(h(C) 0 ,h(C) 1 )を求める認証子暗号化手段と、を有することを特徴とする公開鍵暗号による暗号化認証文生成装置。
  38. 38
    【請求項38】 第1のガウス体において、値がMである認証文データ、値がp g である第1の秘密鍵データ、値がq g である第2の秘密鍵データと、値がn g である第1の公開鍵データおよび値がm g である第2の公開鍵データとから、認証文データに該当する値がM g である暗号化認証文データを生成する公開鍵暗号における認証文生成装置であって、 認証文をハッシュ関数hでハッシュ化し、その結果をハッシュ化認証子h(M)とする認証文ハッシュ化手段と、 認証子h(M)の先頭から剰余類の範囲内の2次体の元の2つの次元成分に対応する2個のブロックを切り出す認証子分割手段と、 秘密鍵P g ,Q g を用い式x 4 -h(M)≡0(mod N g )の解の1個h(C)=(h(C) 0 ,h(C) 1 )を求める認証子暗号化手段と、を有することを特徴とする公開鍵暗号による暗号化認証文生成装置。
  39. 39
    【請求項39】 第2のガウス体において、値がMである認証文データ、値がP G である第1の秘密鍵データ、値がQ G である第2の秘密鍵データと、値がN G である第1の公開鍵データおよび値が-4 G である任意の素数データまたは任意の素数が自然数べき乗されたデータを第2の公開鍵データとから、認証文データに該当する値がM G である暗号化認証文データを生成する公開鍵暗号における認証文生成装置であって、 認証文をハッシュ関数hでハッシュ化し、その結果をハッシュ化認証子h(M)とする認証文ハッシュ化手段と、 認証子h(M)の先頭から剰余類の範囲内の2次体の元の2つの次元成分に対応する2個のブロックを切り出す認証子分割手段と、 秘密鍵P G ,Q G を用い式x 2 -h(M)≡0 (mod N G )の解の1個h(C)=(h(C) 0 ,h(C) 1 )求める認証子暗号化手段と、を有することを特徴とする公開鍵暗号による暗号化認証文生成装置。
  40. 40
    【請求項40】 円分体において、値がTである認証文データ、値がT c である認証文データから生成した暗号化認証文データ、値がr c である認証文データのブロックの数、値がn c である第1の公開鍵データおよび値がm c である任意の素数データまたは任意の素数が自然数べき乗されたデータを第2の公開鍵データとから、認証文データが暗号化され再び復号化される過程が正常か否かを判定する公開鍵暗号における認証文検証装置であって、 前記認証文データを切り出して得られたr c 個のブロックの各ブロックのデータを各成分とする拡大体の元に対して法n c のもとでm c 乗演算を施す演算手段と、 この演算結果である拡大体の元の各次元成分を順次連結しハッシュ化された暗号文データを得る連結手段と、 前記認証文データおよびハッシュ関数を用いてハッシュ化するハッシュ化手段と、 前記連結手段で得られたデータとハッシュ化手段で得られたデータとを比較し一致した場合は、一連の認証文作成ないし検証過程が正常であったと判定し、不一致である場合は一連の認証文作成ないし検証過程のいずれかに異常があったと判定する判定手段と、を有することを特徴とする公開鍵暗号による認証文検証装置。
  41. 41
    【請求項41】 2次体において、値がMである認証文データ、値がM s である認証文データから生成した暗号化認証文データ、値が2である認証文データのブロックの数、値がN s である第1の公開鍵データおよび値がm s である第2の公開鍵データとから、認証文データが暗号化され再び復号化される過程が正常か否かを判定する公開鍵暗号における認証文検証装置であって、 2個のブロック暗号化認証子に対して、式(h(C) 0 ,h(C) 1 ) 2 ≡(h(M) 0 ,h(M) 1 ) mod N s の2乗演算による復号化処理を行う認証子復号化手段と、 復号された2個の認証子ブロックを暗号化認証子がある限り、復号化および統合処理を反復して連接する認証子統合手段と、 認証文に対してハッシュ関数hでハッシュ化を行う認証文ハッシュ化手段と、 前記認証子統合手段で統合された認証子と認証文ハッシュ化手段で得られたハッシュ化認証文が一致すれば認証成功を出力し、一致しなければ認証失敗を出力する認証確認手段と、を有することを特徴とする公開鍵暗号による認証文検証装置。
  42. 42
    【請求項42】 アイゼンシュタイン体において、値がMである認証文データ、値がM e である認証文データから生成した暗号化認証文データ、値が2である認証文データのブロックの数、値がN e である第1の公開鍵データおよび値が3 e である第2の公開鍵データとから、認証文データが暗号化され再び復号化される過程が正常か否かを判定する公開鍵暗号における認証文検証装置であって、 2個のブロック暗号化認証子に対して、式(h(C) 0 ,h(C) 1 ) 3 ≡(h(M) 0 ,h(M) 1 ) mod N e の3乗演算による復号化処理を行う認証子復号化手段と、 復号された2個の認証子ブロックを暗号化認証子がある限り復号化および統合処理を反復して連接する認証子統合手段と、 認証文に対してハッシュ関数hでハッシュ化を行う認証文ハッシュ化手段と、 前記認証子統合手段で統合された認証子と認証文ハッシュ化手段で得られたハッシュ化認証文が一致すれば認証成功を出力し、一致しなければ認証失敗を出力する認証確認手段と、を有することを特徴とする公開鍵暗号による認証文検証装置。
  43. 43
    【請求項43】 第1のガウス体において、値がMである認証文データ、値がM g である認証文データから生成した暗号化認証文データ、値が2である認証文データのブロックの数、値がN g である第1の公開鍵データおよび値が4 g である第2の公開鍵データとから、認証文データが暗号化され再び復号化される過程が正常か否かを判定する公開鍵暗号における認証文検証装置であって、 2個のブロック暗号化認証子に対して、式(h(C) 0 ,h(C) 1 ) 4 ≡(h(M) 0 ,h(M) 1 ) mod N g の2乗演算による復号化処理を行う認証子復号化手段と、 復号された2個の認証子ブロックを暗号化認証子がある限り、復号化および統合処理を反復して連接する認証子統合手段と、 認証文に対してハッシュ関数hでハッシュ化を行う認証文ハッシュ化手段と、 前記認証子統合手段で統合された認証子と認証文ハッシュ化手段で得られたハッシュ化認証文が一致すれば認証成功を出力し、一致しなければ認証失敗を出力する認証確認手段と、を有することを特徴とする公開鍵暗号による認証文検証装置。
  44. 44
    【請求項44】 第2のガウス体において、値がMである認証文データ、値がM G である認証文データから生成した暗号化認証文データ、値が2である認証文データのブロックの数、値がN G である第1の公開鍵データおよび値が-4 G である第2の公開鍵データとから、認証文データが暗号化され再び復号化される過程が正常か否かを判定する公開鍵暗号における認証文検証装置であって、 2個のブロック暗号化認証子に対して、式(h(C) 0 ,h(C) 1 ) 2 ≡(h(M) 0 ,h(M) 1 ) mod N G の2乗演算による復号化処理を行う認証子復号化手段と、 復号された2個の認証子ブロックを暗号化認証子がある限り、復号化および統合処理を反復して連接する認証子統合手段と、 認証文に対してハッシュ関数hでハッシュ化を行う認証文ハッシュ化手段と、 前記認証子統合手段で統合された認証子と認証文ハッシュ化手段で得られたハッシュ化認証文が一致すれば認証成功を出力し、一致しなければ認証失敗を出力する認証確認手段と、を有することを特徴とする公開鍵暗号による認証文検証装置。
Independent claims44