JP4934010B2 - Public key encryption system, public key encryption method, encryption device, decryption device, encryption program, and decryption program - Google Patents

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-Patent Document 1 is replaced with strong pseudo-random replacement that can handle an input of any length (see Non-Patent Document 2, for example). ). A configuration example of strong pseudo-random substitution is detailed in Non-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.

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.

Both 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 as the encrypted device can generate a bare session key R, the verification information a provided with using 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 .

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.

[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

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.

[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 the above 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 the procedure 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 the procedure 1.

  In procedure 1, 1 / (x + a) modq is calculated in the decoding procedure, whereas in procedure 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 public key cryptosystem 1 will be described with reference to FIGS.
As illustrated in FIG. 1, the public key cryptosystem 1 includes a key 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 a decryption 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, the key generation device 100 includes a secret key generation unit 11 and a public key generation unit 12.
The secret key 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 public key generation unit 12. In this example, the secret key x is sent to the decryption device 300.

<Step S2>
The public key 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 the encryption 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 cipher information 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 session key 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, the encryption device 200 includes a random number generation unit 21, a first bare session key generation unit 22, a first session key generation unit 23, a symmetric encryption information generation unit 24, and a first verification information generation unit 25. Asymmetric encryption information generation unit 26, storage unit 27, and transmission unit 28.
The random number 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 session key generation unit 22.

<Step S4>
First bare session key 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 session key generation unit 23.

<Step S5>
The first session key 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 cipher information 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.

<Step S6>
The symmetric encryption information generation unit 24 generates the symmetric encryption information c by inputting the message m read from the storage 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 verification information generation unit 25 and the transmission 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 verification information 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 encryption information generation unit 26.
Hash function H ₂ is a hash function that outputs the original group G.

<Step S8>
The asymmetric cipher information 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 session key 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 the transmission unit 28.

<Step S9>
The transmission unit 28 transmits the ciphertext (u, c), which is information including the asymmetric cipher information u and the symmetric cipher information c, to the decryption device 300. You may transmit to the decoding 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, the decryption device 300 includes a second verification information generation unit 31, a second bare session key generation unit 32, a second session key generation unit 33, a message generation unit 34, and a storage unit 35.

The second verification information generator unit 31 of the decoding 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 the encryption device 200 is first stored in the storage unit 35. The second verification information generator unit 31 reads the asymmetric encryption information c from the storage unit 35, and inputs to the hash function H _2. The generated verification information a is sent to the second bare session key generation unit 32.
The hash function H ₂ is the same as the hash function H ₂ that appeared in the process of the first verification information generation unit 25 of the encryption device 200.

<Step S11>
The second bare session key 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 session key generation unit 33.
<Step S12>
Second session key 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 the message generator 34.
The hash function H ₁ is the same as the hash function H ₁ that appeared in the processing of the first session key generation unit 23 of the encryption device 200.

<Step S13>
The message generator 34 decrypts the message m by inputting the symmetric encryption information c extracted from the ciphertext (u, c) sent from the encryption 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 session key generation unit 22, instead of the R = g ^r, by calculating R = y ^r, obtains a bare session key R, the second bare session The key 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, the determination unit 29 of the encryption device 200 includes the group of asymmetric encryption information u generated by the asymmetric encryption information 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, the encryption 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 public key 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 public key cryptosystem 1 from step S3 is performed. Processing may begin.
In the above example, as illustrated in FIG. 1, the key generation device 100 is a different device from the encryption device 200 and the decryption device 300, but the key generation device 100 is different from the encryption device 200. It may be included. In this case, the secret key x generated in the key generation device 100 in the encryption device 200 is sent to the encryption device 200, and the public key y generated in the key generation device 100 is sent to the decryption device 300. It is done.

In the public key encryption system 1, the key generation device 100, the encryption device 200, and the decryption 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 the key generation device 100, the encryption device 200, and the decryption 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 secret key generation unit 11, the public key generation unit 12, the first bare session key generation unit 22, the first session key generation unit 23, and the symmetric encryption information generation unit 24. , First verification information generation unit 25, asymmetric encryption information generation unit 26, transmission unit 28, determination unit 29, second verification information generation unit 31, second bare session key generation unit 32, second session key generation unit 33, message Functions such as the generation unit 34 are realized. Storage units such as the storage unit 27, the storage unit 35, and a storage unit (not shown) are realized by storage units such as a memory and a hard disk.

  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.

  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 OF SYMBOLS 1 Public key encryption system 11 Secret key generation part 12 Public key generation part 21 Random number generation part 22 First bare session key generation part 23 First session key generation part 24 Symmetric encryption information generation part 25 First verification information generation part 26 Asymmetric encryption Information generation unit 29 Determination unit 31 Second verification information generation unit 32 Second bare session key generation unit 33 Second session key generation unit 34 Message generation unit 100 Key generation device 200 Encryption device 300 Decryption device

Claims (10)

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 A hybrid public key cryptosystem including a decryption device that generates a message key using the session key k and the symmetric cipher information c, and generates a session key k using the key and the secret key x
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 generating means for generating symmetric cipher information c by inputting a message m to an encryption function E _k that is determined by the session key k and outputs symmetric cipher information having the same bit length as the input message;
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 are generated so that the encryption device can generate the bare session key R using the generated 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 G using the public key y;
With
The decryption device
Second verification information generating means for generating verification information a by inputting the symmetric encryption information c to the hash function H ₂ ;
Second bare session key generation means for generating the bare session key R using the asymmetric encryption information u, the secret key x, and the verification information a generated by the second verification information generation means;
A second session key generating means for generating a session key k by inputting the bare session key R generated by the second bare session key generating means to the hash function H ₁ ;
The message is obtained by inputting the symmetric encryption information c to the decryption function D _k which is determined by the session key k and 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 m,
Comprising
A public key cryptosystem characterized by that. 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 step in which the encryption device encrypts the message m using the session key k to generate symmetric encryption information c, and encrypts the session key k using the public key y to generate asymmetric encryption information u; The decryption apparatus includes a decryption step of generating a session key k using the asymmetric encryption information u and the secret key x, and generating a message m using the session key k and the symmetric encryption information c. In the hybrid type public key encryption method,
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 step is
Random number generating means comprises a random number generation step of generating a random number r by selecting from said second set Z _q ^* excluding 0 from the first set Z _q one original randomly,
A first bare session key generation step in which key generation means generates 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 step in which a first session key generating means generates 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 means generates the symmetric cipher information c by inputting the message m to the encryption function E _k that is determined by the session key k and outputs symmetric cipher information having the same bit length as the input message. A symmetric encryption information generation step;
Is first verification information generator unit, to the hash function H ₂ for outputting the original of the group G, by inputting the symmetric encryption information c, the first verification information generating step of generating verification information a,
Asymmetric encryption information generating means, as by using an asymmetric encryption information u generated and the above secret key x and the verification information a is the encryption apparatus can generate a bare session key R, the verification information a Asymmetric cipher information generating step for generating asymmetric cipher information u that is an element of the group G using the generator g and the public key y;
Have
The decoding step is
The second verification information generator unit, by inputting the symmetric cipher information c to the hash function H _2, and the second verification information generating step of generating verification information a,
A second bare session key generation unit generates a second bare session key R using the asymmetric encryption information u, the secret key x, and the verification information a generated by the second verification information generation unit. A bare session key generation step;
A second session key generation step in which a second session key generation means generates a session key k by inputting the bare session key R generated in the second bare session key generation step to the hash function H ₁ When,
A message generating means determines the symmetric encryption information c in a decryption function D _k that is determined by the session key k and that outputs a message corresponding to the encryption function E _k and having the same bit length as the input symmetric encryption information. A message generation step for generating a message m by inputting;
Having
A public key encryption method characterized by the above. 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 are generated so that the encryption device can generate the bare session key R using the generated 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 G using the public key y;
Comprising
An encryption device 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 decryption device
Second verification information generating means for generating verification information a by inputting the symmetric encryption information c generated in the encryption device to the hash function H ₂ ;
Second bare session key generation means for generating the bare session key R using the asymmetric encryption information u, the secret key x, and the verification information a;
A second session key generating means for generating a session key k by inputting the bare session key R into the hash function H ₁ ;
The symmetric encryption information c is determined by the decryption function D _k which is determined by the session key k and corresponds to the encryption function E _k used by the encryption device 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
Comprising
A decoding device characterized by the above.   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.

Images