JP4934010B2

Movatterモバイル変換

Info

Publication number: JP4934010B2
Application number: JP2007306081A
Authority: JP
Inventors: 正幸阿部; 龍明岡本
Original assignee: Nippon Telegraph and Telephone Corp; NTT Inc
Current assignee: Nippon Telegraph and Telephone Corp; NTT Inc
Priority date: 2007-11-27
Filing date: 2007-11-27
Publication date: 2012-05-16
Anticipated expiration: 2027-11-27
Also published as: JP2009128792A

Description

この発明は、いわゆるハイブリッド方式の公開鍵暗号システム、公開鍵暗号方法、暗号化装置、復号化装置、暗号化プログラム及び復号化プログラムに関する。 The present invention relates to a so-called hybrid public key encryption system, public key encryption method, encryption apparatus, decryption apparatus, encryption program, and decryption program.

第一の従来の公開鍵暗号方法について説明をする。この方法は、非特許文献１に記載されているＤＨＩＥＳと呼ばれるハイブリッド暗号方式における秘密鍵暗号を、任意長の入力を扱える強擬似ランダム置換に置き換えたものである（例えば、非特許文献２参照。）。強擬似ランダム置換の構成例については、非特許文献３に詳しい。
ｑを素数、Ｇを生成元ｇが作る位数ｑの群とする。Ｇの元の最大ビット長をｌとする。Ｚ_ｑを０以上ｑ−１以下の整数の集合とする。Ｚ_ｑ^＊をＺ_ｑから０を除いた集合とする。Ｈをハッシュ関数とする。Ｅ_ｋ，Ｄ_ｋをそれぞれセッション鍵ｋにより定まる強擬似ランダム置換とその逆関数とする。The first conventional public key encryption method will be described. In this method, the secret key encryption in the hybrid encryption method called DHIES described in Non-PatentDocument 1 is replaced with strong pseudo-random replacement that can handle an input of any length (see Non-PatentDocument 2, for example). ). A configuration example of strong pseudo-random substitution is detailed inNon-Patent Document 3.
Let q be a prime number and G be a group of orders q created by the generator g. Let the original maximum bit length of G be l. Let Z_{q be} a set of integers between 0 and q-1. Let Z_q^{* be} a set obtained by subtracting 0 from Z_q . Let H be a hash function. Let E_k and D_{k be} strong pseudo-random replacement determined by the session key k and its inverse function, respectively.

鍵生成手順：
・ｘをランダムにＺ_ｑから選択する。
・ｙ＝ｇ^ｘを計算する。
・ｘを秘密鍵、ｙを公開鍵とする。
暗号化手順：
・ｒをランダムにＺ_ｑ^＊から選ぶ。
・Ｒ＝ｇ^ｒ，ｋ＝Ｈ（Ｒ），ｃ＝Ｅ_ｋ（ｍ），ｕ＝ｙ^ｒ
・（ｕ，ｃ）を暗号文として出力する。
復号化手順：
・Ｒ＝ｕ^{（１／ｘ）}，ｋ＝Ｈ（Ｒ），ｍ＝Ｄ_ｋ（ｃ）
・ｍをメッセージとして出力する。Key generation procedure:
· X is selected from_{Z q} at random.
Calculate y = g^x
X is a private key and y is a public key.
Encryption procedure:
・ R is selected from Z_q^* at random.
R = g^r , k = H (R), c = E_k (m), u = y^r
Output (u, c) as ciphertext.
Decryption procedure:
R = u^{(1 / x)} , k = H (R), m = D_k (c)
-Output m as a message.

第二の従来の公開鍵暗号方法について説明をする（例えば、非特許文献４参照。）。
ｑを素数、Ｇを生成元ｇが作る位数ｑの群とする。Ｇの元の最大ビット長をｌとする。Ｚ_ｑを０以上ｑ−１以下の整数の集合とする。Ｚ_ｑ^＊をＺｑから０を除いた集合とする。Ｈ_１，Ｈ_２をハッシュ関数とする。Ｅ_ｋ，Ｄ_ｋをそれぞれセッション鍵ｋにより定まるlength-preservingな暗号化関数、復号化関数とする。length-preservingな関数とは、出力されるビットの長さが、入力されるビットの長さと等しい関数のことである。A second conventional public key encryption method will be described (for example, see Non-Patent Document 4).
Let q be a prime number and G be a group of orders q created by the generator g. Let the original maximum bit length of G be l. Let Z_{q be} a set of integers between 0 and q-1. Let Z_q^{* be} a set obtained by subtracting 0 from Zq. Let H₁ and H₂ be hash functions. Let E_k and D_{k be a} length-preserving encryption function and decryption function determined by the session key_k , respectively. A length-preserving function is a function in which the output bit length is equal to the input bit length.

鍵生成手順：
・ｘ_１，ｘ_２をそれぞれランダムにＺ_ｑから選ぶ。
・ｙ_１＝ｇ^ｘ１，ｙ^２＝ｇ^ｘ２を計算する。ｘ１，ｘ２はそれぞれｘ_１，ｘ_２を意味する。以下、同様である。
・ｘ_１を第一の秘密鍵，ｘ_２を第二の秘密鍵，ｙ_１を第一の公開鍵，ｙ_２を第二の公開鍵とする。
暗号化手順：
・ｒをランダムにＺ_ｑ^＊から選ぶ。
・Ｒ＝ｇ^ｒ，ｋ＝Ｈ（Ｒ），ｃ＝Ｅ_ｋ（ｍ），ａ＝Ｇ（ｃ），ｕ＝ｙ_１^ｒｙ_２^ｒａ
・（ｕ，ｃ）を暗号文として出力する。
復号化手順：
・ａ＝Ｇ（ｃ），Ｒ＝ｕ^{（１／（ｘ１＋ａｘ２））}，ｋ＝Ｈ（Ｒ），ｍ＝Ｄ_ｋ（ｃ）
・ｍをメッセージとして出力する。Key generation procedure:
• x₁ and x₂ are each selected from Z_{q at} random.
Calculate y₁ = g^x1 and y² = g^x2 x1 and x2 mean x₁ and x₂ , respectively. The same applies hereinafter.
• The x₁ first of the secret key, the x₂ second of the secret key, the y₁ first public key, the y₂ and the second public key.
Encryption procedure:
・ R is selected from Z_q^* at random.
R = g^r , k = H (R), c = E_k (m), a = G (c), u = y₁^r y₂^ra
Output (u, c) as ciphertext.
Decryption procedure:
A = G (c), R = u^{(1 / (x1 + ax2))} , k = H (R), m = D_k (c)
-Output m as a message.

第一の従来の公開鍵方法と第二の従来の公開鍵方法はいずれも、ハッシュ関数が完全なである場合には、適応的選択暗号文攻撃に対して安全であると考えられている。また、いずれの方法も、暗号文がｕとｃの２つの要素からなり、ｕは、Ｇの元であるためｌビットであり、ｃは、強擬似ランダム置換又はlength-preservingな暗号化関数にメッセージｍを入力した場合の出力値であるため、｜ｍ｜ビットである。ここで、｜・｜は、・のビット長を表す。したがって、いずれの方法においても、暗号文の長さは、ｌ＋｜ｍ｜ビットとなる。
Michel Abdalla, Mihir Bellare and Phillip Rogaway, “The Oracle Diffie-Hellman Assumptions and an Analysis of DHIES”, Topics in Cryptology - CT-RSA 2001, LNCS 2020, Springer-Verlag, 2001, pp.143-158Kaoru Kurosawa and Toshiki Matsuo, “How to Remove MAC from DHIES”, Information Security and Privacy: 9th Australasian Conference, ACISP 2004, LNCS 3108, Springer-Verlag, 2004, pp.236-247Shai Halevi, “EME*:Extending EME to Handle Arbitary-Length Messages with Associated Data”, INDOCRYPT 2004, LNCS 3348, Springer-Verlag, 2004, pp.315-327Xianhui Lu, Xuejia Lai and Dake He, “Efficient chosen ciphertext secure PKE scheme with short ciphertext”, IACR ePrint archive, 2007/210Both the first conventional public key method and the second conventional public key method are considered to be secure against an adaptive selection ciphertext attack if the hash function is complete. In both methods, the ciphertext is composed of two elements u and c. Since u is an element of G, l is 1 bit, and c is a strong pseudo-random replacement or length-preserving encryption function. Since it is an output value when the message m is input, it is | m | bits. Here, | · | represents the bit length of •. Therefore, in either method, the length of the ciphertext is l + | m | bits.
Michel Abdalla, Mihir Bellare and Phillip Rogaway, “The Oracle Diffie-Hellman Assumptions and an Analysis of DHIES”, Topics in Cryptology-CT-RSA 2001, LNCS 2020, Springer-Verlag, 2001, pp.143-158 Kaoru Kurosawa and Toshiki Matsuo, “How to Remove MAC from DHIES”, Information Security and Privacy: 9th Australasian Conference, ACISP 2004, LNCS 3108, Springer-Verlag, 2004, pp.236-247 Shai Halevi, “EME *: Extending EME to Handle Arbitary-Length Messages with Associated Data”, INDOCRYPT 2004, LNCS 3348, Springer-Verlag, 2004, pp.315-327 Xianhui Lu, Xuejia Lai and Dake He, “Efficient chosen ciphertext secure PKE scheme with short ciphertext”, IACR ePrint archive, 2007/210

第一の従来の公開鍵暗号方法においては、暗号化関数、復号化関数として、セッション鍵ｋにより定まる強擬似ランダム置換Ｅ_ｋ、Ｄ_ｋを用いている。このため、セッション鍵ｋのビット長（以下、セキュリティパラメータλとする。）よりも短いメッセージを暗号化することができないという問題があった。例えば、セキュリティパラメータλ＝１２８ビットの場合、１２８ビットよりも短い長さのメッセージを暗号化することができず、暗号化しても安全性が保障されないという問題があった。
また、第二の従来の公開鍵暗号方法においては、２つの公開鍵ｙ_１，ｙ_２を用いており、公開鍵の数が多いという問題があった。In the first conventional public key encryption method, strong pseudo-random replacement E_k and D_k determined by the session key_k are used as the encryption function and the decryption function. For this reason, there is a problem that a message shorter than the bit length of the session key k (hereinafter referred to as a security parameter λ) cannot be encrypted. For example, when the security parameter λ = 128 bits, there is a problem that a message having a length shorter than 128 bits cannot be encrypted, and security is not guaranteed even if the message is encrypted.
In addition, the second conventional public key encryption method uses two public keys y₁ and y₂ and has a problem that the number of public keys is large.

この発明は、任意の長さのメッセージを暗号化することができ、かつ、公開鍵の数が少ない公開鍵暗号システム、公開鍵暗号方法、暗号化装置、復号化装置、暗号化プログラム及び復号化プログラムを提供することを目的とする。 The present invention can encrypt a message having an arbitrary length and has a small number of public keys, a public key encryption system, a public key encryption method, an encryption device, a decryption device, an encryption program, and a decryption The purpose is to provide a program.

請求項１に記載された発明によれば、メッセージｍをセッション鍵ｋを用いて暗号化して対称暗号情報ｃを生成すると共に、セッション鍵ｋを公開鍵ｙを用いて暗号化して非対称暗号情報ｕを生成する暗号化装置と、非対称暗号情報ｕと秘密鍵ｘとを用いてセッション鍵ｋを生成すると共に、そのセッション鍵ｋと対称暗号情報ｃとを用いてメッセージｍを生成する復号化装置とを備えるハイブリット型の公開鍵暗号システムにおいて、秘密鍵ｘは、０以上ｑ−１以下の整数からなる第一の集合Ｚ_ｑから１つの元を選択することにより生成されたものであり、公開鍵ｙは、秘密鍵ｘに対応しており、位数ｑ（ｑは素数）の群Ｇの元であり、その群Ｇの生成元ｇと秘密鍵ｘとを用いて生成された１つの公開鍵ｙである。According to the first aspect of the invention, the message m is encrypted using the session key k to generate the symmetric cipher information c, and the session key k is encrypted using the public key y to obtain the asymmetric cipher information u. An encryption device that generates a session key k using the asymmetric encryption information u and the secret key x, and a decryption device that generates the message m using the session key k and the symmetric encryption information c. The secret key x is generated by selecting one element from a first set Z_q consisting of integers of 0 or more and q−1 or less, and is a public key. y corresponds to the secret key x, is an element of the group G of order q (q is a prime number), and one public key generated using the generator g of the group G and the secret key x y.

上記暗号化装置は、第一の集合Ｚｑから０を除いた第二の集合Ｚｑ＊から１つの元をランダムに選択することにより乱数ｒを生成する乱数生成手段と、生成元ｇと乱数ｒとから、群Ｇの元であるベアセッション鍵Ｒを生成する第一ベアセッション鍵生成手段と、予め定められたビット長のハッシュ値を出力するハッシュ関数Ｈ１に、ベアセッション鍵Ｒを入力することにより、セッション鍵ｋを生成する第一セッション鍵生成手段と、セッション鍵ｋによって定まり、入力されるメッセージと同じビット長の対称暗号情報を出力する暗号化関数Ｅｋ（ｍ）に、メッセージｍを入力することにより対称暗号情報ｃを生成する対称暗号情報生成手段と、群Ｇの元を出力するハッシュ関数Ｈ２に、対称暗号情報ｃを入力することにより、検証情報ａを生成する第一検証情報生成手段と、生成される非対称暗号情報ｕと秘密鍵ｘと検証情報ａとを用いて上記暗号化装置がベアセッション鍵Ｒを生成することができるように、検証情報ａと生成元ｇと公開鍵ｙとを用いて、群Ｇの元である非対称暗号情報ｕを生成する非対称暗号情報生成手段と、を備える。The encryption apparatus includes a random number generating means for generating a random number r by randomly selecting one element from a second set Zq * obtained by removing 0 from the first set Zq, a generator g, a random number r, By inputting the bare session key R to the first bare session key generating means for generating the bare session key R that is an element of the group G and the hash function H1 that outputs a hash value having a predetermined bit length. The message m is input to the first session key generating means for generating the session key k and the encryption function Ek (m) that is determined by the session key k and outputs symmetric encryption information having the same bit length as the input message. By inputting the symmetric encryption information c to the symmetric encryption information generation means for generating the symmetric encryption information c and the hash function H2 that outputs the elements of the group G, the verification information a A first verification information generating means for generating, using an asymmetric encryption information u and a secret key x and the verification information a that are generated asthe encrypted device cangenerate a bare session key R, the verification information a provided withusing a generator g and the public key y, and asymmetric encryption information generating means for generating asymmetric cryptographic information u is the original group G, a.

上記復号化装置は、ハッシュ関数Ｈ_２に対称暗号情報ｃを入力することにより、検証情報ａを生成する第二検証情報生成手段と、非対称暗号情報ｕと、秘密鍵ｘと、第二検証情報生成手段が生成した検証情報ａとを用いて、ベアセッション鍵Ｒを生成する第二ベアセッション鍵生成手段と、ハッシュ関数Ｈ_１に、第二非対称暗号情報生成手段が生成したベアセッション鍵Ｒを入力することにより、セッション鍵ｋを生成する第二セッション鍵生成手段と、セッション鍵ｋによって定まり、暗号化関数Ｅ_ｋに対応し、入力される対称暗号情報と同じビット長のメッセージを出力する復号化関数Ｄ_ｋに、対称暗号情報ｃを入力することによりメッセージｍを生成するメッセージ生成手段と、を備える。The decoding device, by inputting a symmetric encryption information c to the hash function H_2, and the second verification information generating means for generating verification information a, and asymmetric encryption information u, and the private key x, the second verification information Using the verification information a generated by the generating means, the second bare session key generating means for generating the bare session key R, and the bare session key R generated by the second asymmetric encryption information generating means to the hash function H₁ A second session key generation unit that generates a session key k by inputting and a decryption that is determined by the session key k and that corresponds to the encryption function E_k and outputs a message having the same bit length as the input symmetric encryption information Message generating means for generating a message m by inputting the symmetric encryption information c into the conversion function D_k .

秘密鍵ｘと公開鍵ｙの数がそれぞれ１つであり、秘密鍵と公開鍵の数が十分に少ない。また、暗号化関数Ｅ_ｋ、復号化関数Ｄ_ｋとして、強擬似ランダム置換ではなく、秘密鍵暗号（共通鍵暗号ともいう。）で通常用いられるlength-preservingな任意の関数を用いているため、１ビット以上の任意のメッセージを暗号化することができる。There are one secret key x and one public key y, and the number of secret keys and public keys is sufficiently small. In addition, as the encryption function E_k and the decryption function D_k , not a strong pseudo-random replacement, but an arbitrary length-preserving function that is normally used in secret key cryptography (also referred to as common key cryptography) is used. Any message of 1 bit or more can be encrypted.

［理論］
ｑを素数、群Ｇを生成元ｇが作る位数ｑの群とする。以下、群Ｇを乗法群として記述する。群Ｇの元の最大ビット長をｌとする。群Ｇは、Gap Diffie-Hellman計算問題が難しいと考えられる群ならばどのような群でも良い。例えば、楕円曲線が作る群等が考えられる（例えば、参考文献参照。）。
≪参考文献≫Tatsuaki Okamoto and David Pointcheval, “The Gap-Problems: A New Class of Problems for the Security of Cryptographic Schemes”, PKC 2001, LNCS 1992, Springer-Verlag, 2001, pp.104-118[theory]
Let q be a prime number and group G be a group of orders q created by the generator g. Hereinafter, the group G is described as a multiplicative group. Let the original maximum bit length of group G be l. The group G may be any group as long as the Gap Diffie-Hellman calculation problem is considered difficult. For example, a group formed by an elliptic curve is conceivable (for example, see the reference).
≪Reference≫Tatsuaki Okamoto and David Pointcheval, “The Gap-Problems: A New Class of Problems for the Security of Cryptographic Schemes”, PKC 2001, LNCS 1992, Springer-Verlag, 2001, pp.104-118

Ｚ_ｑを０以上ｑ−１以下の整数の集合とする。Ｚ_ｑ^＊をＺ_ｑから０を除いた集合とする。Ｈ_１は、セキュリティパラメータλで定まるビット長（例えば１２８ビット）のビット列を出力するハッシュ関数である。Ｈ_２は、値域が群Ｇであるハッシュ関数である。
Ｅ_ｋ，Ｄ_ｋをそれぞれ、セッション鍵ｋで定まる、length-preservingな暗号化関数、復号化関数とする。length-preservingな関数とは、出力されるビットの長さが、入力されるビットの長さと等しい関数のことである。
ベアセッション鍵Ｒ、検証情報ａ及び非対称暗号情報ｕは群Ｇの元であり、セッション鍵ｋはセキュリティパラメータλで定まるビット長であり、メッセージｍ及び対称暗号情報ｃは任意のビット長である。Let Z_{q be} a set of integers between 0 and q-1. Let Z_q^{* be} a set obtained by subtracting 0 from Z_q . H₁ is a hash function that outputs a bit string having a bit length (for example, 128 bits) determined by the security parameter λ. H₂ is a hash function whose range is the group G.
Let E_k and D_{k be} a length-preserving encryption function and decryption function determined by the session key k, respectively. A length-preserving function is a function in which the output bit length is equal to the input bit length.
The bare session key R, the verification information a, and the asymmetric encryption information u are elements of the group G, the session key k has a bit length determined by the security parameter λ, and the message m and the symmetric encryption information c have an arbitrary bit length.

〔手順１〕
鍵生成手順：
・ｘをランダムにＺ_ｑから選ぶ。
・ｙ＝ｇ^ｘを計算する。
・ｘを秘密鍵、ｙを公開鍵とする。
暗号化手順：
・ｒをランダムにＺ_ｑ^＊から選ぶ。
・Ｒ＝ｇ^ｒ，ｋ＝Ｈ_１（Ｒ），ｃ＝Ｅ_ｋ（ｍ），ａ＝Ｇ（ｃ），ｕ＝ｙ^ｒｇ^ｒａ
・（ｕ，ｃ）を暗号文として出力する。
復号化手順：
・ａ＝Ｇ（ｃ），Ｒ＝ｕ^{（１／（ｘ＋ａ））}，ｋ＝Ｈ_１（Ｒ），ｍ＝Ｄ_ｋ（ｃ）
・ｍをメッセージとして出力する。
鍵生成手順において秘密鍵ｘと公開鍵ｙをそれぞれ１つだけ生成し、それらを用いて上記ように暗号化手順と復号化手順を行うことにより、秘密鍵と公開鍵の数を少なくすることができる。また、暗号化関数Ｅ_ｋ、復号化関数Ｄ_ｋとして、強擬似ランダム置換ではなく、秘密鍵暗号（共通鍵暗号ともいう。）で通常用いられるlength-preservingな任意の関数を用いているため、１ビット以上の任意のメッセージを暗号化することができる。[Procedure 1]
Key generation procedure:
• Choose x from Z_q at random.
Calculate y = g^x
X is a private key and y is a public key.
Encryption procedure:
・ R is selected from Z_q^* at random.
R = g^r , k = H₁ (R), c = E_k (m), a = G (c), u = y^r^gra
Output (u, c) as ciphertext.
Decryption procedure:
A = G (c), R = u^{(1 / (x + a))} , k = H₁ (R), m = D_k (c)
-Output m as a message.
In the key generation procedure, only one secret key x and one public key y are generated, and the encryption procedure and the decryption procedure are performed using them, thereby reducing the number of secret keys and public keys. it can. In addition, as the encryption function E_k and the decryption function D_k , not a strong pseudo-random replacement, but an arbitrary length-preserving function that is normally used in secret key cryptography (also referred to as common key cryptography) is used. Any message of 1 bit or more can be encrypted.

〔手順２〕
また、暗号化手順と復号化手順を下記のように行ってもよい。暗号化手順におけるベアセッション鍵Ｒの計算方法、復号化手順におけるベアセッション鍵Ｒの計算方法のみが、上記の手順１とは異なる。
鍵生成手順：
・ｘをランダムにＺ_ｑから選ぶ。
・ｙ＝ｇ^ｘを計算する。
・ｘを秘密鍵、ｙを公開鍵とする。
暗号化手順：
・ｒをランダムにＺ_ｑ^＊から選ぶ。
・Ｒ＝ｙ^ｒ，ｋ＝Ｈ_１（Ｒ），ｃ＝Ｅ_ｋ（ｍ），ａ＝Ｇ（ｃ），ｕ＝ｙ^ｒｇ^ｒａ
・（ｕ，ｃ）を暗号文として出力する。
復号化手順：
・ａ＝Ｇ（ｃ），Ｒ＝ｕ^{（ｘ／（ｘ＋ａ））}，ｋ＝Ｈ_１（Ｒ），ｍ＝Ｄ_ｋ（ｃ）
・ｍをメッセージとして出力する。
手順２においては、暗号化手順で、非対称暗号情報ｕ＝ｙ^ｒｇ^ｒａを、ｕ＝Ｒｇ^ｒａと計算できる。このため、手順１に比べて計算量を小さくすることができるというメリットがある。[Procedure 2]
Further, the encryption procedure and the decryption procedure may be performed as follows. Only the calculation method of the bare session key R in the encryption procedure and the calculation method of the bare session key R in the decryption procedure are different from theabove procedure 1.
Key generation procedure:
• Choose x from Z_q at random.
Calculate y = g^x
X is a private key and y is a public key.
Encryption procedure:
・ R is selected from Z_q^* at random.
R = y^r , k = H₁ (R), c = E_k (m), a = G (c), u = y^r^gra
Output (u, c) as ciphertext.
Decryption procedure:
A = G (c), R = u^{(x / (x + a))} , k = H₁ (R), m = D_k (c)
-Output m as a message.
In theprocedure 2, the asymmetric encryption information u = y^r g^ra can be calculated as u = Rg^ra by the encryption procedure. For this reason, there is a merit that the amount of calculation can be reduced as compared with theprocedure 1.

手順１においては、復号化手順で、１／（ｘ＋ａ）ｍｏｄｑを計算しているのに対して、手順２においては、復号化手順で、ｘ／（ｘ＋ａ）ｍｏｄｑを計算している。分子が１ではなくｘである点において、手順２の方が計算量が多いとも考えられる。しかし、ｍｏｄｑにおける除算又は逆数算の計算効率は、分子が１であるか任意の数ｘであるかにほとんど依存しないので、分子がｘであっても計算量は増加しない。 Inprocedure 1, 1 / (x + a) modq is calculated in the decoding procedure, whereas inprocedure 2, x / (x + a) modq is calculated in the decoding procedure. In terms of the fact that the numerator is x instead of 1,procedure 2 is considered to be more computationally intensive. However, since the calculation efficiency of division or reciprocal calculation in mod q hardly depends on whether the numerator is 1 or an arbitrary number x, the calculation amount does not increase even if the numerator is x.

［装置構成］
図１から図５を参照して、公開鍵暗号システム１の一実施例について説明をする。
図１に例示するように、公開鍵暗号システム１は、秘密鍵ｘとそれに対応する公開鍵ｙを生成する鍵生成装置１００と、公開鍵ｙを用いてメッセージｍを暗号化して暗号文（ｕ，ｃ）を生成する暗号化装置２００と、秘密鍵ｘを用いて暗号文（ｕ，ｃ）を復号してメッセージｍを得る復号化装置３００とからなる。
図５にそれぞれ示す、ステップＳ１からステップＳ２が上記［理論］の鍵生成手順に対応し、ステップＳ３からステップＳ９が上記［理論］の暗号化手順に対応し、ステップＳ１０からステップＳ１３が上記［理論］の復号化手順に対応する。[Device configuration]
An embodiment of the publickey cryptosystem 1 will be described with reference to FIGS.
As illustrated in FIG. 1, the publickey cryptosystem 1 includes akey generation device 100 that generates a secret key x and a public key y corresponding to the secret key x, and a ciphertext (u , C) and adecryption device 300 that decrypts the ciphertext (u, c) using the secret key x to obtain the message m.
Steps S1 to S2 shown in FIG. 5 correspond to the [theory] key generation procedure, steps S3 to S9 correspond to the [theory] encryption procedure, and steps S10 to S13 correspond to the above [ This corresponds to the decoding procedure of [Theory].

以下、各ステップについて順に説明をする。
＜ステップＳ１＞
図２に例示するように、鍵生成装置１００は、秘密鍵生成部１１と公開鍵生成部１２とを含む。
秘密鍵生成部１１は、集合Ｚ_ｑから１つの元を選択して、秘密鍵ｘとする（ステップＳ１）。秘密鍵ｘは、公開鍵生成部１２に送られる。また、この例では、秘密鍵ｘは、復号化装置３００に送られる。Hereinafter, each step will be described in order.
<Step S1>
As illustrated in FIG. 2, thekey generation device 100 includes a secretkey generation unit 11 and a publickey generation unit 12.
The secretkey generation unit 11 selects one element from the set Z_q and sets it as a secret key x (step S1). The secret key x is sent to the publickey generation unit 12. In this example, the secret key x is sent to thedecryption device 300.

＜ステップＳ２＞
公開鍵生成部１２は、ｙ＝ｇ^ｘを計算することにより、群Ｇの元である１つの公開鍵ｙを生成する（ステップＳ２）。公開鍵ｙは、暗号化装置２００に送られる。
ｙ＝ｇ^ｘを計算するとは、群Ｇ上定義された演算を生成元ｇについてｘ回行った場合の演算結果を求めることを意味する。言い換えれば、式によって定義される演算結果を求めさえすれば良く、必ずしも群Ｇ上定義された演算を生成元ｇについて実際にｘ回行う必要はない。このことは、群Ｇ上の他の計算についても同様である。例えば、後述する非対称暗号情報生成部２６は、非対称暗号情報ｕ＝ｙ^ｒｇ^ｒａを計算するが、Ｒ＝ｙ^ｒという第一ベアセッション鍵生成部２２において既に得られた計算結果を用いて、非対称暗号情報ｕを、ｕ＝Ｒｇ^ｒａを計算することにより求めてもよい。<Step S2>
The publickey generation unit 12 generates one public key y that is an element of the group G by calculating y = g^x (step S2). The public key y is sent to theencryption device 200.
The calculation of y = g^x means that a calculation result when the calculation defined on the group G is performed x times for the generation source g is obtained. In other words, it is only necessary to obtain the calculation result defined by the equation, and it is not always necessary to actually perform the calculation defined on the group G x times for the generation source g. The same applies to other calculations on the group G. For example, the asymmetric cipherinformation generation unit 26 described later calculates the asymmetric cipher information u = y^r g^ra , but uses the calculation result already obtained in the first bare sessionkey generation unit 22 with R = y^r , The asymmetric encryption information u may be obtained by calculating u = Rg^ra .

＜ステップＳ３＞
ステップＳ３からステップＳ９が上記［理論］の暗号化手順に対応する。
図３に例示するように、暗号化装置２００は、乱数生成部２１、第一ベアセッション鍵生成部２２、第一セッション鍵生成部２３、対称暗号情報生成部２４、第一検証情報生成部２５、非対称暗号情報生成部２６、記憶部２７、送信部２８を含む。
乱数生成部２１は、集合Ｚ_ｑ^＊から１つの元をランダム選択することにより、乱数ｒを生成する（ステップＳ３）。生成された乱数ｒは、第一ベアセッション鍵生成部２２に送られる。<Step S3>
Steps S3 to S9 correspond to the [theory] encryption procedure.
As illustrated in FIG. 3, theencryption device 200 includes a randomnumber generation unit 21, a first bare sessionkey generation unit 22, a first sessionkey generation unit 23, a symmetric encryptioninformation generation unit 24, and a first verificationinformation generation unit 25. Asymmetric encryptioninformation generation unit 26,storage unit 27, andtransmission unit 28.
The randomnumber generation unit 21 generates a random number r by randomly selecting one element from the set Z_q^* (step S3). The generated random number r is sent to the first bare sessionkey generation unit 22.

＜ステップＳ４＞
第一ベアセッション鍵生成部２２は、Ｒ＝ｇ^ｒを計算することにより、ベアセッション鍵Ｒを求める（ステップＳ４）。生成されたベアセッション鍵Ｒは、第一セッション鍵生成部２３に送られる。<Step S4>
First bare sessionkey generation unit 22, by calculating R =^{g r,} determine the bare session key R (Step S4). The generated bare session key R is sent to the first sessionkey generation unit 23.

＜ステップＳ５＞
第一セッション鍵生成部２３は、予め定められたビット長のハッシュ値を出力するハッシュ関数Ｈ_１に、ベアセッション鍵Ｒを入力することにより、セッション鍵ｋを生成する（ステップＳ５）。すなわち、ｋ＝Ｈ_１（Ｒ）を計算する。生成されたセッション鍵ｋは、対称暗号情報生成部２４に送られる。
セッション鍵ｋのビット長は、セキュリティパラメータλとして予め定められている。ハッシュ関数Ｈ_１が出力するハッシュ値のビット長は、セキュリティパラメータλと等しい。<Step S5>
The first sessionkey generation unit 23, the hash function H₁ outputs a hash value of a predetermined bit length, by entering a bare session key R, generates a session key k (step S5). That is, k = H₁ (R) is calculated. The generated session key k is sent to the symmetric cipherinformation generation unit 24.
The bit length of session key k is predetermined as security parameter λ. Bit length of the hash value hash function H₁ outputs is equal to the security parameter lambda.

＜ステップＳ６＞
対称暗号情報生成部２４は、暗号化関数Ｅ_ｋに、記憶部２７から読み込んだメッセージｍを入力することにより、対称暗号情報ｃを生成する（ステップＳ６）。すなわち、ｃ＝Ｅ_ｋ（ｍ）を計算する。生成された対称暗号情報ｃは、第一検証情報生成部２５と送信部２８に送られる。
メッセージｍのビット長は任意でよい。暗号化関数Ｅ_ｋは、セッション鍵ｋをパラメータとして持ち、セッション鍵ｋによって定まる関数である。また、暗号化関数Ｅ_ｋは、length-preservingな関数であるため、対称暗号情報ｃのビット長は、メッセージｍのビット長と同じである。<Step S6>
The symmetric encryptioninformation generation unit 24 generates the symmetric encryption information c by inputting the message m read from thestorage unit 27 to the encryption function E_k (step S6). That is, c = E_k (m) is calculated. The generated symmetric encryption information c is sent to the first verificationinformation generation unit 25 and thetransmission unit 28.
The bit length of the message m may be arbitrary. The encryption function E_k has a session key k as a parameter and is a function determined by the session key k. Further, since the encryption function E_k is a length-preserving function, the bit length of the symmetric encryption information c is the same as the bit length of the message m.

＜ステップＳ７＞
第一検証情報生成部２５は、ハッシュ関数Ｈ_２に、対称暗号情報ｃを入力することにより、検証情報ａを生成する（ステップＳ７）。すなわち、ａ＝Ｈ_２（ｃ）を計算する。生成された検証情報ａは、非対称暗号情報生成部２６に送られる。
ハッシュ関数Ｈ_２は、群Ｇの元を出力するハッシュ関数である。<Step S7>
The first verificationinformation generator unit 25, the hash function H_2, by inputting a symmetric encryption information c, generates verification information a (Step S7). That is, a = H₂ (c) is calculated. The generated verification information a is sent to the asymmetric encryptioninformation generation unit 26.
Hash function H₂ is a hash function that outputs the original group G.

＜ステップＳ８＞
非対称暗号情報生成部２６は、生成される非対称暗号情報ｕと秘密鍵ｘと検証情報ａとを用いてベアセッション鍵Ｒを復号することができるように、検証情報ａと生成元ｇと公開鍵ｙとを混合して、群Ｇの元である非対称暗号情報ｕを生成する。
具体的には、この例では、ｕ＝ｙ^ｒｇ^ｒａを計算することにより、非対称暗号情報ｕを求める。この際、ｕ＝ｙ^ｒｇ^ｒａ＝ｙ^ｒｇ^ｒｇ^ａであるため、第一ベアセッション鍵生成部２２において既に得られた計算結果Ｒ＝ｇ^ｒを用いることにより、非対称暗号情報ｕの計算量を低減してもよい。生成された非対称暗号情報ｕは、送信部２８に送られる。<Step S8>
The asymmetric cipherinformation generation unit 26 uses the generated asymmetric cipher information u, the secret key x, and the verification information a to decrypt the bare session key R so that the verification information a, the generation source g, and the public key can be decrypted. y is mixed to generate asymmetric encryption information u which is an element of the group G.
Specifically, in this example, asymmetric encryption information u is obtained by calculating u = y^r^gra . At this time, since u = y^r g^ra = y^r g^r g^a , the calculation result R = g^r already obtained in the first bare sessionkey generation unit 22 is used to calculate the asymmetric encryption information u. The amount may be reduced. The generated asymmetric encryption information u is sent to thetransmission unit 28.

＜ステップＳ９＞
送信部２８は、非対称暗号情報ｕと対称暗号情報ｃとを含む情報である暗号文（ｕ，ｃ）を、復号化装置３００に送信する。復号化装置３００に対して、直接的ではなく、第三者のサーバー装置等を介して間接的に送信してもよい。
＜ステップＳ１０＞
ステップＳ１０からステップＳ１３が上記［理論］の復号化手順に対応する。
図４に例示するように、復号化装置３００は、第二検証情報生成部３１、第二ベアセッション鍵生成部３２、第二セッション鍵生成部３３、メッセージ生成部３４、記憶部３５を含む。<Step S9>
Thetransmission unit 28 transmits the ciphertext (u, c), which is information including the asymmetric cipher information u and the symmetric cipher information c, to thedecryption device 300. You may transmit to thedecoding apparatus 300 not indirectly but indirectly via a third party server apparatus.
<Step S10>
Steps S10 to S13 correspond to the [theory] decoding procedure.
As illustrated in FIG. 4, thedecryption device 300 includes a second verificationinformation generation unit 31, a second bare sessionkey generation unit 32, a second sessionkey generation unit 33, amessage generation unit 34, and astorage unit 35.

復号化装置３００の第二検証情報生成部３１は、ハッシュ関数Ｈ_２に、暗号化装置２００から送られた暗号文（ｕ，ｃ）から取り出された対称暗号情報ｃを入力することにより、検証情報ａを生成する。すなわち、ａ＝Ｈ_２（ｃ）を計算する。この例では、暗号化装置２００から送られた暗号文（ｕ，ｃ）は、まず記憶部３５に格納される。第二検証情報生成部３１は、記憶部３５から非対称暗号情報ｃを読み込み、ハッシュ関数Ｈ_２に入力する。生成された検証情報ａは、第二ベアセッション鍵生成部３２に送られる。
ハッシュ関数Ｈ_２は、暗号化装置２００の第一検証情報生成部２５の処理で登場したハッシュ関数Ｈ_２と同じものである。The second verificationinformation generator unit 31 of thedecoding device 300, the hash function H_2, by inputting a symmetric encryption information c retrieved from the ciphertext sent from the encryption device 200 (u, c), verification Information a is generated. That is, a = H₂ (c) is calculated. In this example, the ciphertext (u, c) sent from theencryption device 200 is first stored in thestorage unit 35. The second verificationinformation generator unit 31 reads the asymmetric encryption information c from thestorage unit 35, and inputs to the hash function H_2. The generated verification information a is sent to the second bare sessionkey generation unit 32.
The hash function H₂ is the same as the hash function H₂ that appeared in the process of the first verificationinformation generation unit 25 of theencryption device 200.

＜ステップＳ１１＞
第二ベアセッション鍵生成部３２は、Ｒ＝ｕ^{（１／（ｘ＋ａ））}を計算することにより、ベアセッション鍵Ｒを求める。生成されたベアセッション鍵Ｒは、第二セッション鍵生成部３３に送られる。
＜ステップＳ１２＞
第二セッション鍵生成部３３は、ハッシュ関数Ｈ_１に、ベアセッション鍵Ｒを入力することにより、セッション鍵ｋを計算する。すなわち、ｋ＝Ｈ_１（Ｒ）を計算する。生成されたセッション鍵ｋは、メッセージ生成部３４に送られる。
ハッシュ関数Ｈ_１は、暗号化装置２００の第一セッション鍵生成部２３の処理で登場したハッシュ関数Ｈ_１と同じものである。<Step S11>
The second bare sessionkey generation unit 32 calculates the bare session key R by calculating R = u^{(1 / (x + a))} . The generated bare session key R is sent to the second sessionkey generation unit 33.
<Step S12>
Second sessionkey generation unit 33, the hash function H_1, by inputting a bare session key R, to calculate the session key k. That is, k = H₁ (R) is calculated. The generated session key k is sent to themessage generator 34.
The hash function H₁ is the same as the hash function H₁ that appeared in the processing of the first sessionkey generation unit 23 of theencryption device 200.

＜ステップＳ１３＞
メッセージ生成部３４は、復号化関数Ｄ_ｋに、暗号化装置２００から送られた暗号文（ｕ，ｃ）から取り出された対称暗号情報ｃを入力することにより、メッセージｍを復号する。すなわち、ｍ＝Ｄ_ｋ（ｃ）を計算する。
length-preservingな関数である復号化関数Ｄ_ｋは、暗号化関数Ｅ_ｋに対応する復号化関数であり、両関数には、Ｄ_ｋ（Ｅ_ｋ（ｍ））＝ｍの関係が成立している。<Step S13>
Themessage generator 34 decrypts the message m by inputting the symmetric encryption information c extracted from the ciphertext (u, c) sent from theencryption device 200 to the decryption function_Dk . That is, m = D_k (c) is calculated.
The decryption function D_k that is a length-preserving function is a decryption function corresponding to the encryption function E_k , and the relationship of D_k (E_k (m)) = m is established between the two functions. Yes.

上記〔手順２〕を行う場合には、第一ベアセッション鍵生成部２２が、Ｒ＝ｇ^ｒに代えて、Ｒ＝ｙ^ｒを計算することにより、ベアセッション鍵Ｒを求め、第二ベアセッション鍵生成部３２が、Ｒ＝ｕ^{（１／（ｘ＋ａ））}に代えて、Ｒ＝ｕ^{（ｘ／（ｘ＋ａ））}を計算することにより、ベアセッション鍵Ｒを求めればよい。When performing the above-mentioned [step 2], the first bare sessionkey generation unit 22, instead of the R = g^r, by calculating R = y^r, obtains a bare session key R, the second bare session Thekey generation unit 32 may calculate the bare session key R by calculating R = u^{(x / (x + a))} instead of R = u^{(1 / (x + a))} .

［変形例等］
図３に破線で例示するように、また、図５のステップＳ８’に例示するように、暗号化装置２００の判定部２９が、非対称暗号情報生成部２６が生成した非対称暗号情報ｕが、群Ｇの単位元ｅであるか否かを判定して、非対称暗号情報ｕが単位元ｅである場合には、暗号化装置２００が、ステップＳ３の乱数ｒを生成する処理からやり直して、再度非対称暗号情報ｕを生成してもよい。非対称暗号情報ｕが単位元ｅである場合には、検証情報ａの値によらず、ベアセッション鍵Ｒ及びセッション鍵ｋの値が同じになるため、対称暗号情報ｃが改ざんされたかどうかを復号化装置が判定することができないためである。[Modifications, etc.]
As illustrated by a broken line in FIG. 3 and as illustrated in step S8 ′ of FIG. 5, thedetermination unit 29 of theencryption device 200 includes the group of asymmetric encryption information u generated by the asymmetric encryptioninformation generation unit 26. It is determined whether or not the unit element e is G. If the asymmetric cipher information u is the unit element e, theencryption device 200 starts again from the process of generating the random number r in step S3, and again asymmetric. The encryption information u may be generated. When the asymmetric encryption information u is the unit element e, the values of the bare session key R and the session key k are the same regardless of the value of the verification information a, so that it is decrypted whether the symmetric encryption information c has been tampered with. This is because the information processing apparatus cannot make the determination.

上記の例では、公開鍵暗号システム１の処理がステップＳ１から始まるとしているが、既に生成された１つの秘密鍵ｘ及び１つの公開鍵ｙを元にして、ステップＳ３から公開鍵暗号システム１の処理を始めてもよい。
上記の例では、図１に例示するように、鍵生成装置１００は、暗号化装置２００及び復号化装置３００とは異なる別の装置となっているが、鍵生成装置１００が暗号化装置２００に含まれていてもよい。この場合には、暗号化装置２００内の鍵生成装置１００において生成された秘密鍵ｘは暗号化装置２００に送られ、同鍵生成装置１００において生成された公開鍵ｙは復号化装置３００に送られる。In the above example, the process of the publickey cryptosystem 1 starts from step S1, but based on one private key x and one public key y that have already been generated, the process of the publickey cryptosystem 1 from step S3 is performed. Processing may begin.
In the above example, as illustrated in FIG. 1, thekey generation device 100 is a different device from theencryption device 200 and thedecryption device 300, but thekey generation device 100 is different from theencryption device 200. It may be included. In this case, the secret key x generated in thekey generation device 100 in theencryption device 200 is sent to theencryption device 200, and the public key y generated in thekey generation device 100 is sent to thedecryption device 300. It is done.

図１から４に例示した公開鍵暗号システム１、鍵生成装置１００、暗号化装置２００、復号化装置３００においては、装置の各部から各部へデータが直接送られている箇所があるが、図示していない記憶部を介して、間接的にデータが送られてもよい。
上述の構成をコンピュータによって実現する場合、鍵生成装置１００、暗号化装置２００、復号化装置３００の各部が有すべき機能の処理内容はそれぞれプログラムによって記述される。そして、このプログラムをコンピュータで実行することにより、上記各部の機能がコンピュータ上で実現される。In the publickey encryption system 1, thekey generation device 100, theencryption device 200, and thedecryption device 300 illustrated in FIGS. 1 to 4, there are locations where data is directly sent from each part of the device to each part. Data may be sent indirectly through a storage unit that is not.
When the configuration described above is realized by a computer, the processing contents of the functions that each unit of thekey generation device 100, theencryption device 200, and thedecryption device 300 should have are described by a program. By executing this program on a computer, the functions of the above-described units are realized on the computer.

すなわち、ＣＰＵが各プログラムを逐次読み込んで実行することにより、秘密鍵生成部１１、公開鍵生成部１２、第一ベアセッション鍵生成部２２、第一セッション鍵生成部２３、対称暗号情報生成部２４、第一検証情報生成部２５、非対称暗号情報生成部２６、送信部２８、判定部２９、第二検証情報生成部３１、第二ベアセッション鍵生成部３２、第二セッション鍵生成部３３、メッセージ生成部３４等の機能が実現される。また、記憶部２７、記憶部３５及び図示していない記憶部等の記憶部は、メモリ、ハードディスク等記憶手段により実現される。 That is, when the CPU sequentially reads and executes each program, the secretkey generation unit 11, the publickey generation unit 12, the first bare sessionkey generation unit 22, the first sessionkey generation unit 23, and the symmetric encryptioninformation generation unit 24. , First verificationinformation generation unit 25, asymmetric encryptioninformation generation unit 26,transmission unit 28,determination unit 29, second verificationinformation generation unit 31, second bare sessionkey generation unit 32, second sessionkey generation unit 33, message Functions such as thegeneration unit 34 are realized. Storage units such as thestorage unit 27, thestorage unit 35, and a storage unit (not shown) are realized by storage units such as a memory and a hard disk.

この処理内容を記述したプログラムは、コンピュータで読み取り可能な記録媒体に記録しておくことができる。コンピュータで読み取り可能な記録媒体としては、例えば、磁気記録装置、光ディスク、光磁気記録媒体、半導体メモリ等どのようなものでもよいが、具体的には、例えば、磁気記録装置として、ハードディスク装置、フレキシブルディスク、磁気テープ等を、光ディスクとして、ＤＶＤ（Digital Versatile Disc）、ＤＶＤ−ＲＡＭ（Random Access Memory）、ＣＤ−ＲＯＭ（Compact Disc Read Only Memory）、ＣＤ−Ｒ（Recordable）／ＲＷ（ReWritable）等を、光磁気記録媒体として、ＭＯ（Magneto-Optical disc）等を、半導体メモリとしてＥＥＰ−ＲＯＭ（Electronically Erasable and Programmable-Read Only Memory）等を用いることができる。 The program describing the processing contents can be recorded on a computer-readable recording medium. The computer-readable recording medium may be any medium such as a magnetic recording device, an optical disk, a magneto-optical recording medium, or a semiconductor memory. Specifically, for example, the magnetic recording device may be a hard disk device or a flexible Discs, magnetic tapes, etc. as optical disks, DVD (Digital Versatile Disc), DVD-RAM (Random Access Memory), CD-ROM (Compact Disc Read Only Memory), CD-R (Recordable) / RW (ReWritable), etc. As the magneto-optical recording medium, MO (Magneto-Optical disc) or the like can be used, and as the semiconductor memory, EEP-ROM (Electronically Erasable and Programmable-Read Only Memory) or the like can be used.

また、このプログラムの流通は、例えば、そのプログラムを記録したＤＶＤ、ＣＤ−ＲＯＭ等の可搬型記録媒体を販売、譲渡、貸与等することによって行う。さらに、このプログラムをサーバコンピュータの記憶装置に格納しておき、ネットワークを介して、サーバコンピュータから他のコンピュータにそのプログラムを転送することにより、このプログラムを流通させる構成としてもよい。 The program is distributed by selling, transferring, or lending a portable recording medium such as a DVD or CD-ROM in which the program is recorded. Furthermore, the program may be distributed by storing the program in a storage device of the server computer and transferring the program from the server computer to another computer via a network.

また、上述した実施形態とは別の実行形態として、コンピュータが可搬型記録媒体から直接このプログラムを読み取り、そのプログラムに従った処理を実行することとしてもよく、さらに、このコンピュータにサーバコンピュータからプログラムが転送されるたびに、逐次、受け取ったプログラムに従った処理を実行することとしてもよい。また、サーバコンピュータから、このコンピュータへのプログラムの転送は行わず、その実行指示と結果取得のみによって処理機能を実現する、いわゆるＡＳＰ（Application Service Provider）型のサービスによって、上述の処理を実行する構成としてもよい。なお、本形態におけるプログラムには、電子計算機による処理の用に供する情報であってプログラムに準ずるもの（コンピュータに対する直接の指令ではないがコンピュータの処理を基底する性質を有するデータ等）を含むものとする。 As an execution form different from the above-described embodiment, the computer may read the program directly from the portable recording medium and execute processing according to the program. Each time is transferred, the processing according to the received program may be executed sequentially. Also, the program is not transferred from the server computer to the computer, and the above-described processing is executed by a so-called ASP (Application Service Provider) type service that realizes the processing function only by the execution instruction and result acquisition. It is good. Note that the program in this embodiment includes information that is used for processing by an electronic computer and that conforms to the program (data that is not a direct command to a computer but has a property that is based on computer processing).

また、この形態では、コンピュータ上で所定のプログラムを実行させることにより、本装置を構成することとしたが、これらの処理内容の少なくとも一部をハードウェア的に実現することとしてもよい。
また、上述の各種の処理は、記載に従って時系列に実行されるのみならず、処理を実行する装置の処理能力あるいは必要に応じて並列的にあるいは個別に実行されてもよい。その他、本発明の趣旨を逸脱しない範囲で適宜変更が可能であることはいうまでもない。In this embodiment, the present apparatus is configured by executing a predetermined program on a computer. However, at least a part of these processing contents may be realized by hardware.
In addition, the various processes described above are not only executed in time series according to the description, but may be executed in parallel or individually according to the processing capability of the apparatus that executes the processes or as necessary. Needless to say, other modifications are possible without departing from the spirit of the present invention.

公開鍵暗号システムの機能構成を例示する図。The figure which illustrates the function structure of a public key encryption system.鍵生成装置の機能構成を例示する図。The figure which illustrates the function structure of a key generation apparatus.暗号化装置の機能構成を例示する図。The figure which illustrates the function structure of an encryption apparatus.復号化装置の機能構成を例示する図。The figure which illustrates the function structure of a decoding apparatus.公開鍵暗号システムの処理の流れを例示するフローチャート。The flowchart which illustrates the flow of a process of a public key encryption system.

符号の説明Explanation of symbols

１公開鍵暗号システム
１１秘密鍵生成部
１２公開鍵生成部
２１乱数生成部
２２第一ベアセッション鍵生成部
２３第一セッション鍵生成部
２４対称暗号情報生成部
２５第一検証情報生成部
２６非対称暗号情報生成部
２９判定部
３１第二検証情報生成部
３２第二ベアセッション鍵生成部
３３第二セッション鍵生成部
３４メッセージ生成部
１００鍵生成装置
２００暗号化装置
３００復号化装置DESCRIPTION OFSYMBOLS 1 Publickey encryption system 11 Secretkey generation part 12 Publickey generation part 21 Randomnumber generation part 22 First bare sessionkey generation part 23 First sessionkey generation part 24 Symmetric encryptioninformation generation part 25 First verificationinformation generation part 26 Asymmetric encryptionInformation generation unit 29Determination unit 31 Second verificationinformation generation unit 32 Second bare sessionkey generation unit 33 Second sessionkey generation unit 34Message generation unit 100Key generation device 200Encryption device 300 Decryption device

Claims

Translated fromJapanese

請求項１に記載された公開鍵暗号システムにおいて、
上記公開鍵ｙは、ｙ＝ｇ^ｘであり、
上記第一ベアセッション鍵生成手段は、Ｒ＝ｇ^ｒを計算することにより、ベアセッション鍵Ｒを生成する手段であり、
上記非対称暗号情報生成手段は、ｕ＝ｙ^ｒｇ^ｒａを計算することにより、非対称暗号情報ｕを生成する手段であり、
上記第二ベアセッション鍵生成手段は、Ｒ＝ｕ^{（１／（ｘ＋ａ））}を計算することにより、ベアセッション鍵Ｒを生成する手段である、
ことを特徴とする公開鍵暗号システム。In the public key cryptosystem described in claim 1,
The public key y is y = g^x ,
The first bare session key generation means, by calculating R = g^r, a means for generating a bare session key R,
The asymmetric cipher information generation means is means for generating asymmetric cipher information u by calculating u = y^r^gra .
The second bare session key generation means is means for generating a bare session key R by calculating R = u^{(1 / (x + a))} .
A public key cryptosystem characterized by that.

請求項１に記載された公開鍵暗号システムにおいて、
上記第一ベアセッション鍵生成手段は、上記生成元ｇと上記乱数ｒとに代えて、上記公開鍵ｙと上記乱数ｒとから、上記群Ｇの元であるベアセッション鍵Ｒを生成する手段である、
ことを特徴とする公開鍵暗号システム。In the public key cryptosystem described in claim 1,
The first bare session key generation means is means for generating a bare session key R that is an element of the group G from the public key y and the random number r instead of the generation source g and the random number r. is there,
A public key cryptosystem characterized by that.

請求項２に記載された公開鍵暗号システムにおいて、
上記第一ベアセッション鍵生成手段は、Ｒ＝ｇ^ｒに代えて、Ｒ＝ｙ^ｒを計算することにより、ベアセッション鍵Ｒを生成する手段であり、
上記第二ベアセッション鍵生成手段は、Ｒ＝ｕ^{（１／（ｘ＋ａ））}に代えて、Ｒ＝ｕ^{（ｘ／（ｘ＋ａ））}を計算することにより、ベアセッション鍵Ｒを生成する手段である、
ことを特徴とする公開鍵暗号システム。In the public key cryptosystem described in claim 2,
The first bare session key generation means, instead of the R = g^r, by calculating R = y^r, a means for generating a bare session key R,
The second bare session key generation means is means for generating a bare session key R by calculating R = u^{(x / (x + a))} instead of R = u^{(1 / (x + a)).} ,
A public key cryptosystem characterized by that.

請求項１から４に記載された公開鍵暗号システムにおいて、
上記非対称暗号情報生成手段が生成した非対称暗号情報ｕが、上記群Ｇの単位元ｅであるかどうかを判定する判定手段を更に備え、
非対称暗号情報ｕが単位元ｅであると判定された場合には、上記暗号化装置は再度非対称暗号情報ｕを生成する、
ことを特徴とする公開鍵暗号システム。In the public key cryptosystem described in claims 1 to 4,
A determination means for determining whether the asymmetric encryption information u generated by the asymmetric encryption information generation means is a unit element e of the group G;
When it is determined that the asymmetric encryption information u is the unit element e, the encryption device generates the asymmetric encryption information u again.
A public key cryptosystem characterized by that.

メッセージｍをセッション鍵ｋを用いて暗号化して対称暗号情報ｃを生成すると共に、セッション鍵ｋを公開鍵ｙを用いて暗号化して非対称暗号情報ｕを生成する暗号化装置と、非対称暗号情報ｕと秘密鍵ｘとを用いてセッション鍵ｋを生成すると共に、そのセッション鍵ｋと対称暗号情報ｃとを用いてメッセージｍを生成する復号化装置とを備えるハイブリット型の公開鍵暗号システムに用いられる暗号化装置において、
上記秘密鍵ｘは、０以上ｑ−１以下の整数からなる第一の集合Ｚ_ｑから１つの元を選択することにより生成されたものであり、
上記公開鍵ｙは、上記秘密鍵ｘに対応しており、位数ｑ（ｑは素数）の群Ｇの生成元ｇと上記秘密鍵ｘとを用いて生成された、群Ｇに属する１つの公開鍵ｙであり、
上記暗号化装置は、
上記第一の集合Ｚ_ｑから０を除いた第二の集合Ｚ_ｑ^＊から１つの元をランダムに選択することにより乱数ｒを生成する乱数生成手段と、
上記生成元ｇと上記乱数ｒとから、上記群Ｇの元であるベアセッション鍵Ｒを生成する第一ベアセッション鍵生成手段と、
予め定められたビット長のハッシュ値を出力するハッシュ関数Ｈ_１に、上記ベアセッション鍵Ｒを入力することにより、セッション鍵ｋを生成する第一セッション鍵生成手段と、
上記セッション鍵ｋによって定まり、入力されるメッセージと同じビット長の対称暗号情報を出力する暗号化関数Ｅ_ｋ（ｍ）に、メッセージｍを入力することにより対称暗号情報ｃを生成する対称暗号情報生成手段と、
上記群Ｇの元を出力するハッシュ関数Ｈ_２に、上記対称暗号情報ｃを入力することにより、検証情報ａを生成する第一検証情報生成手段と、
生成される非対称暗号情報ｕと上記秘密鍵ｘと上記検証情報ａとを用いて上記暗号化装置がベアセッション鍵Ｒを生成することができるように、上記検証情報ａと上記生成元ｇと上記公開鍵ｙとを用いて、上記群Ｇの元である非対称暗号情報ｕを生成する非対称暗号情報生成手段と、
を備える、
ことを特徴とする暗号化装置。An encryption device that encrypts a message m using a session key k to generate symmetric encryption information c, and encrypts the session key k using a public key y to generate asymmetric encryption information u; and asymmetric encryption information u And a secret key x are used to generate a session key k, and a hybrid public key encryption system including a decryption device that generates a message m using the session key k and symmetric encryption information c. In the encryption device,
The secret key x is generated by selecting one element from a first set Z_q composed of integers of 0 or more and q-1 or less,
The public key y corresponds to the secret key x, and is generated by using the generator g of the group G of order q (q is a prime number) and the secret key x, and belongs to the group G. Public key y,
The encryption device is
A random number generating means for generating a random number r by selecting from the second set Z_q^* excluding 0 from the first set Z_q one original randomly,
First bare session key generation means for generating a bare session key R that is an element of the group G from the generation source g and the random number r;
A first session key generating means for generating a session key k by inputting the bare session key R into a hash function H₁ that outputs a hash value having a predetermined bit length;
Symmetric cipher information generation for generating symmetric cipher information c by inputting message m to encryption function E_k (m) that is determined by session key k and outputs symmetric cipher information having the same bit length as the input message Means,
First verification information generating means for generating verification information a by inputting the symmetric encryption information c to the hash function H₂ that outputs the element of the group G;
The verification information a, the generation source g, and the above aregenerated so that theencryption device cangenerate the bare session key R using thegenerated asymmetric encryption information u, the secret key x, and the verification information a. Asymmetric cipher information generating means for generating asymmetric cipher information u which is an element of the group Gusing the public key y;
Comprising
An encryption device characterized by that.

請求項７に記載された暗号化装置の各手段としてコンピュータを機能させるための暗号化プログラム。 The encryption program for functioning a computer as each means of the encryption apparatus described in Claim 7.

請求項８に記載された復号化装置の各手段としてコンピュータを機能させるための復号化プログラム。 A decoding program for causing a computer to function as each unit of the decoding device according to claim 8.