JP2003005638A - Public key encryption communication method - Google Patents

Abstract

PROBLEM TO BE SOLVED: To provide a public key encryption communication technology capable of certifying security. SOLUTION: In a Rabin encryption, a composite number N as the public key is selected as p<d> q (p, q are prime numbers and d is more than 1). A hash function is combined with an OAEP by using uniqueness for decrypting. The security can be certified on conditions of a rapidly decrypting process and difficulty for factoring N into prime numbers. (The security shows strong concealment against an attack of adaptively selecting encrypted texts). The security against the attack of selecting the encrypted texts can be certified and the public key encryption communication technology capable of rapidly processing decryption can be provided. The public key encryption communication technology can also reduce a computational load when a transmitted data is encrypted and decrypted and certify as an IND-CCA2 on a condition of difficulty for computing an inverse function of one-way substitution (e.g. difficulty for factoring into prime numbers).

Description

Detailed Description of the Invention

[0001]

BACKGROUND OF THE INVENTION 1. Field of the Invention The present invention relates to a cryptographic communication technique, and more particularly to a communication communication technique using public key cryptography that can be proved to be confidential to an adaptive selection ciphertext attack.

[0002]

2. Description of the Related Art Conventionally, various public key cryptographic methods have been proposed. Among them, `` RL Rivest, A. Shamir, L.
Adleman: A Method for Obtaining Digital Signatur
es andPublic-Key Cryptosystems, Commun. of the AC
M, Vol.21, No.2, pp.120-126,1978. "(Hereinafter referred to as Reference 1
Is called) is the most popular public key encryption method.

In addition, "VS Miller: Use of Ell
iptic Curves in Cryptography, Proc. of Crypto'85,
LNCS218, Springer-Verlag, pp.417-426 (1985) "(hereinafter referred to as Reference 2) and" N. Koblitz: Elliptic Curv.
e Cryptosystems, Math.Comp., 48, 177, pp.203-209
(1987) ”(hereinafter referred to as Document 3) and the like, a public key encryption method using an elliptic curve is known.

Further, as a public key encryption method capable of certifying the security against a selected plaintext attack, "MORabin: Digital Si
gnatures and Public-Key Encryptions as Intractable
asFactorization, MIT, Technical Report, MIT / LCS / T
R-212 (1979) ”(hereinafter referred to as Reference 4) and the public key encryption method described in“ T. El Gamal: A Public Key C ”.
ryptosystem and a Signature Scheme Based on Discre
te Logarithms, IEEE Trans. On Information Theory,
IT-31, 4, pp.469-472 (1985) "(hereinafter referred to as reference 5)
The public key encryption method described in, and "S. Goldwasser
and S. Micali: Probabilistic Encryption, JCSS, 2
8, 2, pp.270-299 (1984) ”(hereinafter referred to as Reference 6), and the public key encryption method described in“ M. Blum and S. G ”
oldwasser: An Efficient Probabilistic Public-Key
Encryption Scheme which HidesAll Partial Informati
on, Proc. of Crypto'84, LNCS196, Springer-Verlag,
pp.289-299 (1985) "(hereinafter referred to as Reference 7), and the public key encryption method described in" S. Goldwasser and M.B. "
ellare: Lecture Notes on Cryptography, http: / www-
cse.ucsd.edu/users/ mihir / (1997) ”(hereinafter referred to as Reference 8
Public key encryption method described in "T. Oka
moto and S. Uchiyama: A New Public-KeyCryptosyste
m as Secure as Factoring, Proc. of Eurocrypt'98, L
NCS1403, Springer Verlag, pp.308-318 (1998) "(hereinafter referred to as Document 9) is known.

Further, as a public key cryptographic method capable of certifying the security against a selected ciphertext attack, "D. Dolve, C. Dwork an
d M. Naor: Non-Malleable Cryptography, In 23 ^rd An
nual ACM Symposium on Theory of Computing, pp.542-
552 (1991) "(hereinafter referred to as Reference 10), and the public key encryption method and" M. Naor and M. Yung: Public.
-Key Cryptosystems Provably Secure against Chosen
Ciphertext Attacks, Proc. Of STOC, ACM Press, pp.4
27-437 (1990) "(hereinafter referred to as Reference 11), and the public key encryption method and" R. Cramer and V. Shoup:
A Practical Public Key Cryptosystem Provably Secur
e against Adaptive Chosen Ciphertext Attack, Proc.
of Crypto98, LNCS1462, Springer-Verlag, pp.13-25
(1998) ”(hereinafter referred to as Reference 12) and the like are known.

In addition, "M. Bellare, A. Desai, D. Point
cheval and P. Rogaway: Relations Among Notions of
Security for Public-Key Encryption Schemes, Proc.
ofCrypto'98, LNCS1462, Springer Verlag, pp.26-45
(1998) ”(hereinafter referred to as Reference 13), IND-CCA2 (Keep secret against adaptive selected ciphertext attack) and NM-
Equivalence with CCA2 (robustness against adaptive choice ciphertext attack) is shown. At present, the public key cryptosystem that satisfies this condition is considered to be the most secure cryptosystem.

[M. Bellare and P. Rogaway: Op
timal Asymmetric Encryption Howto Encrypt with RS
A, Proc. Of Eurocrypt'94, LNCS950, Springer Verla
g, pp.92-111 (1994) ”(hereinafter referred to as reference 14), the public key cryptographic method is adaptive on the assumption that it is difficult to calculate the inverse function of one-way permutation. It has been considered to be a strong secret against selective ciphertext attacks. However, recently, `` V. Shoup: OAEP Reconsidered. Available on t
"He e-print library (2000/060), November 2000" (hereinafter referred to as Reference 15) pointed out that the proof of safety was insufficient from the point of view and the general point of view. A solution is also proposed.

[0008]

By the way, it is proved in the document that the public key encryption method described in the document 4 is one-way against a selective plaintext attack. This means that the public key encryption method described in Document 4 is weak against the selected ciphertext attack. Further, the public key encryption method described in Document 4 is excellent in high-speed encryption processing, but has a problem that high-speed decryption processing cannot be expected.

In general, in encrypted communication, transmission data is often encrypted using common key encryption, and the common key used to encrypt this transmission data is often encrypted using public key encryption. This is because in the public key encryption method described in each of the above documents, the length of plaintext that can be encrypted at one time is short and is limited in proportion to the key length.

For example, in the public key encryption method described in Document 1, when the key length is 1024 bits, the length of plaintext that can be encrypted at one time is 1024 bits. Also, reference 3
In the public key encryption method described in (1), when the base p is 160 bits, the length of plaintext that can be encrypted at one time is 160 bits.

However, in a practical cryptographic communication system,
In addition to the common key, user identification information (ID information) and the like are often sent together. Also, the key length to be transmitted is becoming longer with the progress of computing power. For this reason, if the length of plaintext that can be encrypted at one time is short, it is necessary to perform encryption in multiple times. When divided into multiple times, it becomes necessary to guarantee the correctness of the correspondence between each ciphertext and the plaintext. Therefore, extra work is required. For this reason, there is a demand for a cryptographic method capable of certifying the security that can encrypt a longer plaintext at one time.

The present invention has been made in view of the above circumstances, and it is an object of the present invention to provide a public key cryptographic communication technique capable of certifying the security.

For example, there is provided a public key cryptographic communication technique capable of proving security against a selected ciphertext attack and capable of high-speed decryption processing.

Also, a public key cryptographic communication technique capable of reducing the calculation load when encrypting and decrypting transmission data is provided.

Further, on the assumption that it is difficult to calculate the inverse function of unidirectional permutation (for example, the difficulty of the prime factorization problem), a public key cryptographic communication technique that can prove that it is IND-CCA2 is provided. .

[0016]

The public key cryptographic communication method of the present invention for solving the above problems is as follows.

According to one aspect of the present invention, based on the public key cryptographic method described in the above-mentioned document 4, the security can be proved against a selected ciphertext attack, and a high-speed decryption process can be performed. A possible public key cryptographic communication method is provided.

In the public key encryption method described in the above-mentioned document 4, the composite number N which is a public key is selected as N = pq, whereas in this embodiment, the composite number N is N = p ^d q ( d> 1). This enables high-speed decoding processing.

Further, the public key encryption methods described in the above Documents 14 and 15 are based on the premise that trapdoor-equipped unidirectional replacement is used. However, when x ² mod N (N is a composite number) is used as the encryption function, it does not become unidirectional replacement. With respect to this point, in this aspect, the hash function is used for decryption uniqueness, and is combined with the public key encryption method described in Document 14. This enhances the security against selective ciphertext attacks.

A specific example of the public key cryptographic communication method according to this aspect is as follows.

That is, a public-key cryptographic communication method in which a device on the sender side encrypts transmission data using the public key of the receiver and transmits the encrypted data to the device on the receiver side.

[0022]

[Expression 161]

Let be the recipient's private key (p, q),

[0024]

[Equation 162]

Is the public key (N, k, G, H) of the receiver,
(1) In the sender-side device, plaintext x (x ∈ {0,1} ⁿ )
, A random number r ∈ {0,1} ^k0 is selected, and using this random number r and the public key of the recipient,

[0026]

[Expression 163]

Is calculated (where n + k ₀ + k ₁ = k), and the result s, t
Using,

[0028]

[Equation 164]

And using the result w and the recipient's public key,

[0030]

[Equation 165]

[Mathematical formula-see original document] and sends the result y as a ciphertext to the device on the receiver side, and (2) the device on the receiver side uses the secret key of the receiver to transmit data on the sender side. From the ciphertext y received from the device,

[0032]

[Equation 166]

Is calculated, and the result is used as

[0034]

[167]

And calculate

[0036]

[Equation 168]

And then φ (x _p , x _q ), φ (-x _p , x
_q ), φ (x _p , -x _q ), φ (-x _p , -x _q ) (where φ is Z / (p) × Z / (q) to Z / (representing a homomorphic map to (pq)),

[0038]

[Equation 169]

Place it as shown in

[0040]

[Equation 170]

By calculating

[0042]

[Expression 171]

The decoding result shown in is calculated.

For a certain ciphertext, the decryption result is "*"
, It means that the correct decoding could not be performed. In this case, the ciphertext may be for an attack. Therefore, if the decryption result is "*", the device on the receiver side rejects the ciphertext. That is, the device on the receiver side refuses to decrypt the ciphertext in order to make the selected ciphertext attack impossible,
Do not output the plaintext that is the decryption result. At this time, the device on the receiver side may be configured not to output any decryption result, or may be configured to notify the operator that the decryption result could not be obtained.

Another aspect of the present invention is as follows.

That is, a public-key cryptographic communication method in which the sender device encrypts transmission data using the recipient's public key and sends it to the recipient device.

[0047]

[Expression 172]

Let be the recipient's public key,

[0049]

[Numerical Expression 173]

Is a secret key of the receiver (where k = k ₀ + k ₁ + n), and (1) the plaintext x (x∈ {0,
1} ⁿ ) for a random number r ∈ {0,1} ^k0 , and using this random number r and the public key of the recipient,

[0051]

[Expression 174]

And using the result s, t and the recipient's public key,

[0053]

[Expression 175]

Then, y ₁ and y ₂ are calculated and sent as ciphertext to the device of the recipient, and (2) the device of the receiver uses the secret key of the receiver to send the sender. From the ciphertext y ₁ , y ₂ received from the device on the side,

[0055]

[Expression 176]

Is calculated, and using the result,

[0057]

[Equation 177]

Then, using the result,

[0059]

[Expression 178]

Decryption result shown in (However, if the decryption result is "*", this ciphertext is rejected. Also, [a] ⁿ and [a] _n are the high order and low _order of a, respectively. (representing n bits).

For a certain ciphertext, the decryption result is "*"
, It means that the correct decoding could not be performed. In this case, the ciphertext may be for an attack. Therefore, if the decryption result is "*", the device on the receiver side rejects the ciphertext. That is, the device on the receiver side refuses to decrypt the ciphertext in order to make the selected ciphertext attack impossible,
Do not output the plaintext that is the decryption result. At this time, the device on the receiver side may be configured not to output any decryption result, or may be configured to notify the operator that the decryption result could not be obtained.

A specific example of the public key cryptographic communication method according to this aspect is as follows.

That is, it is a public key cryptographic communication method in which the device on the sender side encrypts the transmission data using the public key of the receiver, and transmits it to the device on the receiver side.

[0064]

[Equation 179]

Let be the recipient's secret key (p, q),

[0066]

[Equation 180]

Is the recipient's public key (N, k, G, H),
(1) In the sender-side device, plaintext x (x ∈ {0,1} ⁿ )
, A random number r ∈ {0,1} ^k0 is selected, and using this random number r and the public key of the recipient,

[0068]

[Formula 181]

Is calculated (where n + k ₀ + k ₁ <k-2) and the result is
Using s, t and the recipient's public key,

[0070]

[Equation 182]

(Where a = (m / N) represents a Jacobi symbol), and as a result, y ₁ , y ₂ and y ₃ are transmitted as ciphertexts to the recipient's device, and (2) In the device on the receiver side,
Using the private key of the receiver, from the ciphertext y ₁ , y ₂ , y ₃ received from the device on the sender side,

[0072]

[Equation 183]

And then φ (x _{1, p} , x _{1, q} ), φ (-
x _{1, p} , x _{1, q} ), φ (x _{1, p} , -x _{1, q} ), φ (-x _{1 , p} , -x _{1, q} ), where φ is the Chinese surplus Theorem Z / (p) × Z / (q) to Z / (p
(representing a ring isomorphism map to q)), (x / N) = y ₃ and 0 <x <2 ^k-2 , where s'

[0074]

[Formula 184]

By calculating

[0076]

[Equation 185]

Decryption result shown in (However, if the decryption result is "*", this ciphertext is rejected. Also, [a] ⁿ and [a] _n are the upper and lower bits of a, respectively. (representing n bits).

In this embodiment, the security can be proved, and the plaintext space can be efficiently enlarged as compared with the conventional public key encryption method (which can be security proved). . That is, a longer plaintext can be processed with one encryption, and therefore, efficient processing can be performed.

In the present invention, the plain text (also referred to as a message) to be encrypted is not limited to a character string, but any digital such as a common key used for encrypting images, sounds, or transmission data. The data applies.

In this specification and the drawings,
A symbol in which "+" is enclosed in a circle indicates an exclusive OR.

[0081]

BEST MODE FOR CARRYING OUT THE INVENTION Embodiments of the present invention will be described below.

First, the configuration of a public key cryptographic communication system common to the following embodiments will be described.

FIG. 1 is a schematic configuration diagram of a public key encryption communication system common to each embodiment of the present invention. As shown in the figure, the public-key cryptographic communication system includes a sender-side device 100 that performs an encryption process to create a ciphertext and a receiver-side device 200 that performs a decryption process to restore a plaintext. It has the structure connected via 300.

FIG. 2 is a schematic block diagram of the sender-side device 100 shown in FIG. As illustrated, an input unit 107 that receives various types of information including plaintext to be encrypted, a random number generation unit 101, a power multiplication unit 102, and a calculation unit 103.
, Remainder calculation unit 104, storage unit 105, and encryption unit 1
08, and a communication unit 106 that communicates with the receiver-side device 200 via the communication line 300.

FIG. 3 is a schematic block diagram of the receiver-side device 200 shown in FIG. As illustrated, a communication unit 206 that communicates with the sender-side device 100 via the communication line 300.
, Key generation unit 201, power multiplication unit 202, and operation unit 2
03, a remainder calculation unit 204, a storage unit 205, a decoding unit 208, and an output unit 207 that outputs various kinds of information including the decoding result.

The sender-side device 100 and the receiver-side device 200 having the above-described configurations each have a CPU 401 as shown in FIG.
And a memory 402 and an external storage device 403 such as an HDD
A reading device 405 that reads information from a portable storage medium 404 such as a CD-ROM or a DVD-ROM; an input device 406 such as a keyboard or a mouse; an output device 407 such as a display; and a communication line 300. In a general computer system including a communication device 408 for communicating with a partner device, the CPU 40
1 can be realized by executing a predetermined program loaded on the memory 402.

This predetermined program is read by the reading device 405.
From the storage medium 404 via the communication device 40
Alternatively, it may be downloaded from the communication line 300 to the external storage device 403 via 8, then loaded on the memory 402 and executed by the CPU 401. In addition, the communication line 300 is read from the storage medium 404 via the reader 405 or via the communication device 408.
Directly loaded on the memory 402 from the CPU 401
May be executed by.

(First Embodiment) Next, in the first embodiment of the present invention, an example will be given in which the sender transmits a message (length n) as transmission data to the receiver by cipher communication. explain. FIG. 5 is a diagram for explaining the operation procedure of the first embodiment of the present invention.

1. Key Generation Processing In the receiver-side device 200, the key generation unit 201 follows the instruction from the operator (recipient) and the secret key (p, q) of the receiver.
And the recipient's public key (N, k, G, H)
6, generated by equation 187. Then, the generation information is stored in the storage unit 205 (ST1100).

[0090]

[Expression 186]

[0091]

[Equation 187]

Here, n + k ₀ + k ₁ = k. Also, the value of d shall be decided by the administrator or receiver of this system in advance or when necessary, and the key generation unit 201 takes in the decided value of d and secret key of the recipient. And public key generation.

Next, the receiver sends the public information including the public key (N, k, G, H) of the receiver generated by the key generation unit 201 of the receiver side device 200 to the sender (sender side device). 100 operators)
(ST1101). For example, the receiver device 2
In 00, the key generation unit 201 transmits the public information to the sender-side device 100 via the communication unit 206 according to the instruction from the receiver. Alternatively, the recipient is, for example, a third party
By well-known methods such as registration with (public information management organization),
Make public information public. This public information is sent to the sender device 1
00 is stored in the storage unit 105.

The secret key (p, q) should be created by selecting a prime number such that p = 2p '+ 1 and q = 2q' + 1 from other prime numbers p'and q '. Is also possible.

2. In the encryption processing sender device 100, the input unit 107 receives an input of the message x (xε {0,1} ⁿ ) from the operator (sender) (ST1200). In response to this, the random number generator 10
1 selects a random number rε {0,1} ^k0 for the message x. Then, the calculation unit 103 uses the random number r and the storage unit 1 in advance.
Using the public key (N, k, G, H) of the receiver stored in 05, the exponentiation unit 102 is used to calculate the number 188 (ST1201).

[0096]

[Formula 188]

Next, arithmetic section 103 calculates equation 189 using calculation results s and t of equation 188 (ST120
2).

[0098]

[Formula 189]

Further, the calculation unit 103 uses the calculation result w of the formula 189 and the public key of the receiver to calculate the power multiplication unit 102.
The number 190 is calculated by using the remainder calculation unit 104 (ST1203).

[0100]

[Formula 190]

The communication unit 106 calculates the calculation result y
Is transmitted to the receiver-side device 200 via the communication line 300 as the ciphertext of the message x (ST120
4).

3. In the decryption processing recipient device 200, the communication unit 206 receives the ciphertext y from the sender device 100 via the communication line 300, and stores it in the storage unit 205. Now, the calculation unit 203 uses the exponentiation unit 202 and the remainder calculation unit 204 according to the instruction from the operator (sender), and the secret key (p, q) of the receiver stored in the storage unit 205. From the ciphertext y stored in the storage unit 205 using
Calculate 1.

[0103]

[Formula 191]

Next, the arithmetic unit 203 uses the calculation result of the equation 191 to calculate the power multiplication unit 202 and the remainder arithmetic unit 204.
Mathematical formulas 192 and 193 are calculated using
1300).

[0105]

[Formula 192]

[0106]

[Formula 193]

Then, the arithmetic unit 203 determines that φ (x _p , x _q ), φ
(-x _p , x _q ), φ (x _p , -x _q ), φ (-x _p , -x _q ) (where φ is Z / (p) × Z / according to Chinese Remainder Theorem (representing a ring isomorphism map from (q) to Z / (pq)) is set as shown in Formula 194 (ST1301 and ST1302).

[0108]

[Formula 194]

Next, arithmetic section 203 calculates equation 195 (ST1303) to calculate decryption result x '(that is, message x) of ciphertext y shown in equation 196 (ST1).
304).

[0110]

[Formula 195]

[0111]

[Expression 196]

Then, the arithmetic section 203 outputs the decoding result x ′ from the output section 207. However, the decryption result is "*"
In the case of, the arithmetic unit 203 refuses to decrypt the ciphertext y, and outputs the fact to the output unit 207 (ST130).
5).

In the present embodiment, the value of d (d ≧ 1) described above can be changed. For example, when the bit length of the message is always small, it is possible to speed up the decoding process by increasing the value of d in the range where it is difficult to factorize the above N.

Further, in the present embodiment, it is possible to prove that it is strong confidentiality against the selected ciphertext attack on the premise of the difficulty of the above-mentioned N prime factorization problem (IND-CCA2). The proof outline is shown below.

In the sense of strong confidentiality in the adaptive selection ciphertext attack, it is assumed that there is an algorithm capable of breaking the public key cryptographic communication method of this embodiment (the definition is described in, for example, Document 14). Exist). Using this algorithm, we can construct an algorithm that performs a factorization of N. From this, the public-key cryptographic communication method according to the present embodiment is based on the difficulty of the prime factorization problem.
It can be proved to be D-CCA2.

In the present embodiment, the above-mentioned value of w and N
Information that indicates the magnitude relationship of the value of / 2 (for example, the information that sets -1 when the value of w is smaller than N / 2 and 1 when it is large) is
The sender device 100 may be made public or may be transmitted to the receiver device 200. Receiver side device 2
00 uses the above information in the decoding process to obtain four φ (x _p , x _q ), φ (-x _p , x _q ), φ (x _p , -x _q ), φ (-x _p ,-
_Only two of x x) can be decrypted.

When the value of d is an odd number, the sender device 100 publishes the Jacobi symbol (w / N) or sends it to the receiver device 200, so that φ (x _p , x _q ) , φ (-x _p , x
_q ), φ (x _p , -x _q ), φ (-x _p , -x _q ) By calculating the value of the Jacobi symbol, the decoding is limited to two of these. You can

With such a device, the efficiency of the decoding process can be improved.

For the definition and calculation method of the Jacobi symbol, see, for example, “AJ Menezes, PC van Oorschot,
SA Vanstone: Jacobi Symbol: Definition & Algorit
hm, Handbook of Applied Cryptography, CRC Press, p
p.73, 1996 "(hereinafter referred to as Reference 16) and" H. Cohe
n: Jacobi Symbol: Definition & Algorithm, A Cours
e in Computational Algebraic Number Theory, Gradua
te Texts in Math. 138, Springer-Verlag, New York,
pp.27-31, 1993 "(hereinafter referred to as reference 17).

Further, in the present embodiment, from ciphertext y, φ (x _p , x _q ), φ (-x _p , x _q ), φ (x _p , -x _q ), φ (-x _p ,- As a method of calculating (x _q ), there is also a high-speed calculation method of obtaining a square root by using n = p ^d q as a modulus. This calculation method can be applied to other systems that calculate the square root (or mth root) modulo n = p ^d q. This enables high-speed calculation of the power root.

By the way, the public key cryptographic communication method of this embodiment can be used together with common key cryptography for the purpose of delivering the data encryption key in the common key cryptography. In this case, instead of the message x, the data encryption key (common key) K (Kε {0,1} ⁿ ) is the encryption / decryption target. Then, the data encryption key K is used to encrypt / decrypt the transmission data m. That is, the sender device 1
00 is a ciphertext c encrypted with the data encryption key K,
The data encryption key K and the public key encryption result for the data encryption key K are transmitted to the recipient device 200. The recipient device 200 decrypts the ciphertext c using the decryption result of the public key encryption result (that is, the data encryption key K) to obtain the transmission data m.

(Second Embodiment) Next, a second embodiment of the present invention will be described by taking as an example a case where a sender transmits a message as transmission data to a receiver by cipher communication. The present embodiment is a modification of the first embodiment described above. FIG. 6 is a diagram for explaining the operation procedure of the second embodiment of the present invention.

1. Key Generation Processing In the receiver-side device 200, the key generation unit 201 follows the instruction from the operator (recipient) and the secret key (p, q) of the receiver.
And the recipient's public key (N, k, G, H, H ')
7, generated by the number 198. Then, the generation information is stored in the storage unit 205 (ST2100).

[0124]

[Formula 197]

[0125]

[Number 198]

Here, n + k ₀ + k ₁ = k. Also, the value of d shall be decided by the administrator or receiver of the present system in advance or as necessary, and the key generation unit 201 takes in the decided value of d and secret key of the recipient. And public key generation.

Next, the receiver sends the public information including the public key (N, k, G, H, H ') of the receiver generated by the key generation unit 201 of the receiver side device 200 to the sender (transmission). The operator of the person-side device 100) is notified (ST2101). For example, in the receiver-side device 200, the key generation unit 201 transmits public information to the sender-side device 100 via the communication unit 206 according to an instruction from the receiver. Alternatively, the recipient publishes the public information by a known method such as registration with a third party (public information management organization). This public information is stored in the storage unit 105 of the sender device 100.

The secret key (p, q) should be created by selecting a prime number such that p = 2p '+ 1, q = 2q' + 1 from other prime numbers p ', q'. Is also possible.

2. In the encryption processing sender device 100, the input unit 107 accepts the input of the message x (xε {0,1} ⁿ ) from the operator (sender) (ST2200). In response to this, the random number generator 10
1 selects a random number rε {0,1} ^k0 for the message x. Then, the calculation unit 103 uses the random number r and the storage unit 1 in advance.
Using the public key (N, k, G, H, H ') of the receiver stored in 05, the number 199 is calculated (ST2201).

[0130]

[Numerical formula 199]

Next, arithmetic section 103 calculates equation 200 using calculation results s and t of equation 199 (ST220).
2).

[0132]

[Equation 200]

Further, the calculation unit 103 uses the calculation result w of the equation 200 and the public key of the receiver to calculate the power multiplication unit 102.
And the number 201 is calculated using the remainder calculation unit 104 (ST2203).

[0134]

[Equation 201]

The communication unit 106 calculates the calculation result y of the equation 201.
Is transmitted to the receiver-side device 200 via the communication line 300 as the ciphertext of the message x (ST220).
4).

3. In the decryption processing recipient device 200, the communication unit 206 receives the ciphertext y from the sender device 100 via the communication line 300, and stores it in the storage unit 205. Now, the calculation unit 203 uses the exponentiation unit 202 and the remainder calculation unit 204 according to the instruction from the operator (sender), and the secret key (p, q) of the receiver stored in the storage unit 205. From the ciphertext y stored in the storage unit 205 using
Calculate 2.

[0137]

[Equation 202]

Next, the arithmetic unit 203 uses the calculation result of the equation 202 to calculate the power multiplication unit 202 and the remainder arithmetic unit 204.
To calculate the number 203 and the number 204 (ST
2300).

[0139]

[Equation 203]

[0140]

[Equation 204]

Then, the arithmetic unit 203 determines that φ (x _p , x _q ), φ
(-x _p , x _q ), φ (x _p , -x _q ), φ (-x _p , -x _q ) (where φ is Z / (p) × Z / according to Chinese Remainder Theorem (representing a ring isomorphism map from (q) to Z / (pq)) is set as shown in Formula 205 (ST2301, ST2302).

[0142]

[Equation 205]

Next, arithmetic section 203 calculates decryption result x '(that is, message x) of ciphertext y shown in Formula 207 by calculating Formula 206 (ST2303) (ST2).
304).

[0144]

[Equation 206]

[0145]

[Equation 207]

Then, the arithmetic unit 203 outputs the decoding result x ′ from the output unit 207. However, the decryption result is "*"
In the case of, the arithmetic unit 203 refuses to decrypt the ciphertext y, and outputs the fact to the output unit 207 (ST230).
5).

In the present embodiment, the above-mentioned value of d (d ≧ 1) can be changed. For example, when the bit length of the message is always small, it is possible to speed up the decoding process by increasing the value of d in the range where it is difficult to factorize the prime number of N described above.

In addition, this embodiment is similar to the above-described first embodiment in that it is premised on the difficulty of the N factorization problem.
-Can prove to be CCA2.

Further, in the present embodiment, similarly to the case of the above-mentioned first embodiment, in the decoding process, φ (x _p , x _q ), φ (-
For the purpose of limiting x _p , x _q ), φ (x _p , -x _q ), φ (-x _p , -x _q ), publish or send the value of the Jacobi symbol (w / N). Alternatively, it is also possible to publish or transmit information indicating the magnitude relationship between the value of w and the value of N / 2.

Further, the public key cryptographic communication method of this embodiment can be used together with common key cryptography for the purpose of delivering a data encryption key in common key cryptography, as in the first embodiment. It is possible.

(Third Embodiment) Next, a third embodiment of the present invention will be described by taking as an example a case where a sender sends a message as transmission data to a receiver by cipher communication. FIG. 7 is a diagram for explaining the operation procedure of the third embodiment of the present invention.

1. Key Generation Processing In the receiver-side device 200, the key generation unit 201 follows the instructions from the operator (recipient) and the public key (f, G,
H) and the recipient's private key are the number 208 and the number 209, respectively.
Generated by. Then, the generation information is stored in the storage unit 205 (ST3100).

[0153]

[Equation 208]

[0154]

[Equation 209]

Here, n + k ₀ + k ₁ = k.

Next, the receiver sends the public information including the public key (f, G, H) of the receiver generated by the key generation unit 201 of the receiver side device 200 to the sender (sender side device 100 Notify the operator) (ST3101). For example, the receiver device 20
0, the key generation unit 201 sends public information via the communication unit 206 to the sender-side device 1 according to an instruction from the receiver.
Send to 00. Alternatively, the recipient is, for example, a third party
By well-known methods such as registration with (public information management organization),
Make public information public. This public information is sent to the sender device 1
00 is stored in the storage unit 105.

2. In the encryption processing sender device 100, the input unit 107 receives an input of the message x (xε {0,1} ⁿ ) from the operator (sender) (ST3200). In response to this, the random number generator 10
1 selects a random number rε {0,1} ^k0 for the message x. Then, the calculation unit 103 uses the random number r and the storage unit 1 in advance.
Using the public key (f, G, H) of the recipient stored in 05, the power multiplication unit 102 is used to calculate the number 210 (ST3201).

[0158]

[Equation 210]

Next, arithmetic section 103 calculates expression 211 using calculation results s, t of expression 210 (ST320).
2).

[0160]

[Equation 211]

The communication unit 106 calculates the calculation result y ₁ , y of the equation 211.
₂ as the ciphertext of the message x is transmitted to the receiver-side device 200 via the communication line 300 (ST320).
4).

3. In the decryption processing receiver device 200, the communication unit 206 transmits the ciphertexts y ₁ and y ₂ from the sender device 100 via the communication line 300.
Is received and stored in the storage unit 205. Now, the calculation unit 203 uses the power multiplication unit 202 and the remainder calculation unit 204 in accordance with the instruction from the operator (sender), using the secret key of the receiver stored in the storage unit 205,
From the ciphertext y ₁ , y ₂ stored in the storage unit 205,
2 is calculated (ST3300).

[0163]

[Equation 212]

Next, arithmetic section 203 calculates equation 213 using the calculation result of equation 212 (ST3301).

[0165]

[Equation 213]

Next, the arithmetic section 203 uses the calculation result of the equation 213 to calculate the decoding result shown in the equation 214 using the power multiplication section 202. [A] ⁿ and [a] _n represent the upper and lower n bits of a, respectively (S330).
2).

[0167]

[Equation 214]

Then, the arithmetic section 203 outputs the decoding result x ′ from the output section 207. However, the decryption result is "*"
In the case of, the arithmetic unit 203 refuses to decrypt the ciphertexts y ₁ and y ₂ , and outputs a message to that effect from the output unit 207 (ST330).
3).

In this embodiment, on the assumption that it is difficult to find the inverse function of the one-way permutation f, it can be proved that the ciphertext is strongly confidential to the selected ciphertext attack (IND-CC).
A2). The proof outline is shown below.

In the sense of strong confidentiality in the adaptive selection ciphertext attack, an enemy who attempts to break the public key cryptographic communication method of the present embodiment (this definition is described in, for example, Reference 15) is a decryption oracle. In order to get information from, we need to know the original message x for the question ciphertext y ₁ , y ₂ . That is, the adversary cannot obtain new information from the decryption oracle. Further, by the same method as the public key encryption method described in Document 14, it can be easily shown that the public key encryption communication method of the present embodiment is IND-CPA (confidential against selected plaintext attack). From this, it can be proved that the public key cryptographic communication method of this embodiment is IND-CCA2.

Further, according to this embodiment, the problem of the document 14 pointed out in the document 15 (the proof of the safety is insufficient on the assumption that it is difficult to calculate the inverse function of f) is solved. it can. Further, according to this embodiment, it is possible to secure a large plaintext space while maintaining safety.

(Fourth Embodiment) Next, a specific example of the third embodiment will be described as a fourth embodiment of the present invention.
FIG. 8 is a diagram for explaining the operation procedure of the fourth embodiment of the present invention.

1. Key Generation Processing In the receiver-side device 200, the key generation unit 201 follows the instruction from the operator (recipient) and the secret key (p, q) of the receiver.
, And the recipient's public key (N, k, G, H)
5, which is generated by the equation 216. Then, the generation information is stored in the storage unit 205 (ST4100).

[0174]

[Equation 215]

[0175]

[Expression 216]

Here, the value of d is determined by the administrator or receiver of this system in advance or when necessary, and the key generation unit 201 takes in the determined value of d and receives it. The private key and public key of the person are to be generated.

Next, the receiver sends the public information including the public key (N, k, G, H) of the receiver generated by the key generation unit 201 of the receiver side device 200 to the sender (sender side device). 100 operators)
(ST4101). For example, the receiver device 2
In 00, the key generation unit 201 transmits the public information to the sender-side device 100 via the communication unit 206 according to the instruction from the receiver. Alternatively, the recipient is, for example, a third party
By well-known methods such as registration with (public information management organization),
Make public information public. This public information is sent to the sender device 1
00 is stored in the storage unit 105.

The secret key (p, q) should be created by selecting a prime number such that p = 2p '+ 1, q = 2q' + 1 from other prime numbers p ', q'. Is also possible.

2. In the encryption processing sender device 100, the input unit 107 receives an input of the message x (xε {0,1} ⁿ ) from the operator (sender) (ST4200). In response to this, the random number generator 10
1 selects a random number rε {0,1} ^k0 for the message x. Then, the calculation unit 103 uses the random number r and the storage unit 1 in advance.
Using the public key (N, k, G, H) of the receiver stored in 05, the power multiplication unit 102 is used to calculate the number 217 (ST4201).

[0180]

[Expression 217]

Here, n + k ₀ + k ₁ <k-2. Next, the calculation unit 103 uses the calculation results s, t of Expression 217 and uses the power multiplication unit 102 and the remainder calculation unit 104 to calculate Expression 218.
Is calculated (ST4202).

[0182]

[Equation 218]

Here, a = (m / N) represents the Jacobi symbol. Next, the communication unit 106 uses the calculation results y ₁ , y ₂ , y ₃ of Equation 218 as
The ciphertext of the message x is transmitted to the receiver device 200 via the communication line 300 (ST4203).

3. In the decryption processing receiver side device 200, the communication unit 206 receives the ciphertexts y ₁ , y ₂ , from the sender side device 100 via the communication line 300.
It receives y ₃ and stores it in the storage unit 205. Now, the calculation unit 203 uses the exponentiation unit 202 and the remainder calculation unit 204 according to the instruction from the operator (sender), and the secret key (p, q) of the receiver stored in the storage unit 205. Using, the equation 219 is calculated from the ciphertext y ₁ , y ₂ , y ₃ stored in the storage unit 205 (ST4300).

[0185]

[Formula 219]

Then, the arithmetic unit 203 determines that φ (x _{1, p} ,
x _{1, q} ), φ (-x _{1, p} , x _{1, q} ), φ (x _{1, p} , -x _{1, q} ), φ (-x _{1, p} ,-
x _{1, q} ) (where φ is Z / (p) according to the Chinese Remainder Theorem
× Z / (q) to Z / (pq) is represented as a homomorphic map), and (x / N) = y ₃ and 0 <x <2 ^k-2 is ^defined as s', and Formula 220 is calculated. (ST4301 to ST4303).

[0187]

[Equation 220]

[0188] Next, operation unit 203, the ciphertext y ₁ of the equation 221, y _2, y ₃ of the decoding results x 'is calculated (i.e. message x) (ST4304).

[0189]

[Equation 221]

Here, [a] ⁿ and [a] _n represent the upper and lower n bits of a, respectively. Then, the arithmetic unit 203 outputs the decoding result x ′ from the output unit 207.
However, when the decryption result is “*”, the arithmetic unit 203 rejects the decryption of the ciphertext y ₁ , y ₂ , y ₃ and notifies the output unit 20 of that effect.
It outputs from 7 (ST4305).

In this embodiment, the value of d (d ≧ 1) described above can be changed. For example, when the bit length of the message is always small, it is possible to speed up the decoding process by increasing the value of d in the range where it is difficult to factorize the prime number of N described above.

Further, in the public key cryptographic communication method of the present embodiment, for example, when d = 3, it can be shown that complete decryption is impossible on the premise of the difficulty of the N factorization problem.
That is, if there is an algorithm for solving the prime factorization problem of N, the algorithm can be used to configure an algorithm for performing complete decryption of the public key cryptographic communication method of the present embodiment. Further, if there is an algorithm for performing complete decryption of the public key cryptographic communication method of the present embodiment, the algorithm can be used to construct an algorithm for solving the N factorization problem.

FIG. 9 shows the size of the plaintext space between the public key cryptographic communication method according to the present embodiment (fourth embodiment) and the conventional cryptographic methods (elliptic curve cryptography, RSA, OAEP + RSA), and it is a diagram illustrating a comparison of the safety _{(where, k 1 = k 0 = 128} ).
According to the present embodiment, it is understood that it is possible to secure a large plaintext space while maintaining safety, as compared with the conventional technique.

(Fifth Embodiment) Next, a modification of the fourth embodiment will be described as a fifth embodiment of the present invention.
FIG. 10 is a diagram for explaining the operation procedure of the fifth embodiment of the present invention.

1. Key Generation Processing In the receiver-side device 200, the key generation unit 201 follows the instruction from the operator (recipient) and the secret key (p, q) of the receiver.
And the recipient's public key (N, k, G, H),
2, generated by the equation 223. Then, the generation information is stored in the storage unit 205 (ST5100).

[0196]

[Equation 222]

[0197]

[Equation 223]

Here, the value of d is determined by the administrator or receiver of the present system in advance or when necessary, and the key generation unit 201 takes in the determined value of d and receives it. The private key and public key of the person are to be generated.

Next, the receiver sends the public information including the public key (N, k, G, H) of the receiver generated by the key generation unit 201 of the receiver side device 200 to the sender (sender side device). 100 operators)
(ST5101). For example, the receiver device 2
In 00, the key generation unit 201 transmits the public information to the sender-side device 100 via the communication unit 206 according to the instruction from the receiver. Alternatively, the recipient is, for example, a third party
By well-known methods such as registration with (public information management organization),
Make public information public. This public information is sent to the sender device 1
00 is stored in the storage unit 105.

The secret key (p, q) should be created by selecting a prime number such that p = 2p '+ 1, q = 2q' + 1 from other prime numbers p'and q '. Is also possible.

2. In the encryption processing sender device 100, the input unit 107 receives an input of the message x (xε {0,1} ⁿ ) from the operator (sender) (ST5200). In response to this, the random number generator 10
1 selects a random number rε {0,1} ^k0 for the message x. Then, the calculation unit 103 uses the random number r and the storage unit 1 in advance.
Using the public key (N, k, G, H) of the receiver stored in 05, the exponent 224 is calculated using the exponentiation unit 102 (ST5201).

[0202]

[Equation 224]

Here, n + k ₀ + k ₁ <k-2. Next, the calculation unit 103 uses the calculation result s, t of Expression 224 and uses the power multiplication unit 102 and the remainder calculation unit 104 to calculate Expression 225.
Is calculated (ST5202).

[0204]

[Equation 225]

Next, the communication unit 106 uses the calculation results y ₁ and y ₂ of the equation 225 as the ciphertext of the message x and the communication line 30.
To the receiver-side device 200 via 0 (ST52
03).

3. In the decryption processing receiver device 200, the communication unit 206 transmits the ciphertexts y ₁ and y ₂ from the sender device 100 via the communication line 300.
Is received and stored in the storage unit 205. Now, operation unit 2
03 uses the power multiplication unit 202 and the remainder calculation unit 204 in accordance with instructions from the operator (sender) to store the data in the storage unit 2
Using the recipient's private key (p, q) stored in 05,
From the ciphertext y ₁ and y ₂ stored in the storage unit 205,
6 is calculated (ST5300).

[0207]

[Equation 226]

Then, the arithmetic unit 203 determines that φ (x _{1, p} ,
x _{1, q} ), φ (-x _{1, p} , x _{1, q} ), φ (x _{1, p} , -x _{1, q} ), φ (-x _{1, p} ,-
x _{1, q} ) (where φ is Z / (p) according to the Chinese Remainder Theorem
XZ / (q) to Z / (pq)), and s '(s' may exist more than once) that satisfies 0 <x <2 ^k-2 Is calculated (ST5301 to ST5303).

[0209]

[Equation 227]

Next, arithmetic section 203 calculates decryption result x '(that is, message x) of ciphertext y ₁ and y ₂ shown in Expression 228 (ST5304).

[0211]

[Equation 228]

Here, [a] ⁿ and [a] _n represent the upper and lower n bits of a, respectively. Then, the arithmetic unit 203 outputs the decoding result x ′ from the output unit 207.
However, when the decryption result is “*”, the arithmetic unit 203 rejects the decryption of the ciphertexts y ₁ and y ₂ , and outputs that effect to the output unit 207.
Is output (ST5305).

In this embodiment, the above-mentioned value of d (d ≧ 1) can be changed. For example, when the bit length of the message is always small, it is possible to speed up the decoding process by increasing the value of d in the range where it is difficult to factorize the prime number of N described above.

In the public key cryptographic communication method of this embodiment, for example, when d = 3, it can be shown that complete decryption is impossible on the premise of difficulty of the N factorization problem.
That is, if there is an algorithm for solving the prime factorization problem of N, the algorithm can be used to configure an algorithm for performing complete decryption of the public key cryptographic communication method of the present embodiment. Further, if there is an algorithm for performing complete decryption of the public key cryptographic communication method of the present embodiment, the algorithm can be used to construct an algorithm for solving the N factorization problem.

(Sixth Embodiment) Next, another modification of the above-described fourth embodiment will be described as a sixth embodiment of the present invention. FIG. 11 is a diagram for explaining the operation procedure of the sixth embodiment of the present invention.

1. Key Generation Processing In the receiver-side device 200, the key generation unit 201 follows the instruction from the operator (recipient) and the secret key p _i (1 ≦ 1) of the receiver.
i ≦ d) and the recipient's public key (N, k, G, H), respectively, in Equation 2
29, generated by the number 230. Then, the generation information is stored in storage section 205 (ST6100).

[0217]

[Equation 229]

[0218]

[Equation 230]

Here, the value of d is determined by the administrator or receiver of the present system in advance or when necessary, and the key generation unit 201 takes in the determined value of d and receives it. The private key and public key of the person are to be generated.

Next, the receiver sends the public information including the public key (N, k, G, H) of the receiver generated by the key generation unit 201 of the receiver side device 200 to the sender (sender side device). 100 operators)
(ST6101). For example, the receiver device 2
In 00, the key generation unit 201 transmits the public information to the sender-side device 100 via the communication unit 206 according to the instruction from the receiver. Alternatively, the recipient is, for example, a third party
By well-known methods such as registration with (public information management organization),
Make public information public. This public information is sent to the sender device 1
00 is stored in the storage unit 105.

The secret key p _i is a prime number p ′ different from these.
Therefore, it is also possible to create it by selecting a prime number such that p = 2p '+ 1.

2. In the encryption processing sender device 100, the input unit 107 receives an input of the message x (xε {0,1} ⁿ ) from the operator (sender) (ST6200). In response to this, the random number generator 10
1 selects a random number rε {0,1} ^k0 for the message x. Then, the calculation unit 103 uses the random number r and the storage unit 1 in advance.
Using the public key (N, k, G, H) of the receiver stored in 05, the exponentiation unit 102 is used to calculate the number 231 (ST6201).

[0223]

[Expression 231]

Here, n + k ₀ + k ₁ ≦ log ₂ (N + 1). Next, arithmetic section 103 calculates mathematical expression 232 using power multiplication section 102 and remainder arithmetic section 104 using calculation results s, t of mathematical expression 231 (ST6202).

[0225]

[Equation 232]

Next, the communication unit 106 uses the calculation results y ₁ and y ₂ of the equation 232 as the ciphertext of the message x and the communication line 30.
To the receiver-side device 200 via 0 (ST62
03).

3. In the decryption processing receiver device 200, the communication unit 206 transmits the ciphertexts y ₁ and y ₂ from the sender device 100 via the communication line 300.
Is received and stored in the storage unit 205. Now, operation unit 2
03 uses the power multiplication unit 202 and the remainder calculation unit 204 in accordance with instructions from the operator (sender) to store the data in the storage unit 2
Using the secret key p _i of the recipient stored in 05, the number 233 is calculated from the ciphertext y ₁ and y ₂ stored in the storage unit 205 (ST6300).

[0228]

[Expression 233]

Then, the arithmetic unit 203 outputs 2 ^d φ (± x
_{1, p1} , ± x _{1, p2,.} ． ． , ± x _{1, pd} ) (where φ is Z / (p ₁ ) × Z / (q ₂ ) × ... × Z / (q _d ) to Z / (N) according to the Chinese Remainder Theorem. (Representing a ring isomorphic map to), and s ′ (there may be a plurality of s ′) satisfying 0 <s ′ <N / 2, the equation 234 is calculated.

[0230]

[Equation 234]

Next, arithmetic section 203 calculates decryption result x ′ (that is, message x) of ciphertext y ₁ and y ₂ shown in Expression 235 (ST6303).

[0232]

[Equation 235]

[A] ⁿ and [a] _n represent the upper and lower n bits of a, respectively. Then, the arithmetic unit 203 outputs the decoding result x ′ from the output unit 207.
However, when the decryption result is “*”, the arithmetic unit 203 rejects the decryption of the ciphertexts y ₁ and y ₂ , and outputs that effect to the output unit 207.
Is output (ST6304).

In this embodiment, the value of d (d> 1) described above can be changed. Further, in the public key cryptographic communication method of the present embodiment, it can be shown that complete decryption is impossible on the assumption that the N factorization problem is difficult. That is,
If there is an algorithm that solves the N factorization problem,
Using the algorithm, an algorithm for performing complete decryption of the public key cryptographic communication method of this embodiment can be configured. Further, if there is an algorithm for performing complete decryption of the public key cryptographic communication method of the present embodiment, the algorithm can be used to construct an algorithm for solving the N factorization problem.

(Seventh Embodiment) The public key encryption communication method of the third embodiment described above is used together with an existing encryption method (for example, common key encryption) for the purpose of delivering a data encryption key in common key encryption. A case in which it is used will be described as a seventh embodiment of the present invention.

1. Key Generation Processing In the receiver-side device 200, the key generation unit 201 follows the instructions from the operator (recipient) and the public key (f, G,
H) and the recipient's private key, respectively
Generated by. Then, the generated information is stored in the storage unit 205.

[0237]

[Equation 236]

[0238]

[Equation 237]

Here, n + k ₀ + k ₁ = k.

Next, the receiver sends the public information including the public key (f, G, H) of the receiver generated by the key generation unit 201 of the receiver side device 200 to the sender (transmitter side device 100 Notify the operator). For example, in the receiver-side device 200, the key generation unit 201 stores public information according to an instruction from the receiver.
The data is transmitted to the sender-side device 100 via the communication unit 206.
Alternatively, the recipient is, for example, a third party (public information management organization).
Disclosure of public information by well-known methods such as registration to. This public information is stored in the storage unit 105 of the sender device 100.
Memorized in.

2. Encryption processing In the sender device 100, the input unit 107 is an operator
Accept input of sent message m from (sender)
Then, the encryption unit 108 uses the data encryption / decryption key K (K∈ {0,1}ⁿ)
Encrypt the message m using the existing encryption method using
And generate the ciphertext c. Next, the random number generation unit 101
Is a random number r ∈ {0,1} for the data encryption / decryption key K. ^k0Choose
Bu Then, the calculation unit 103 stores this random number r in advance.
The public key (f, G, H) of the recipient stored in the storage unit 105
And calculate the number 238 using the power multiplication unit 102
To do.

[0242]

[Equation 238]

Next, the arithmetic part 103 calculates the equation 239 using the calculation result s, t of the equation 238.

[0244]

[Equation 239]

The communication unit 106 uses the cipher result y ₁ , y
₂ is transmitted to the receiver-side device 200 via the communication line 300 together with the ciphertext c of the message m.

3. In the decryption processing receiver side device 200, the communication unit 206 receives the encryption result y ₁ , y from the sender side device 100 via the communication line 300.
₂ is received together with the ciphertext c and stored in the storage unit 205. The calculation unit 203 uses the power multiplication unit 202 according to the instruction from the operator (sender) to store the data in the storage unit 20.
5, using the recipient's private key stored in
The formula 240 is calculated from the cipher results y ₁ and y ₂ stored in 05.

[0247]

[Equation 240]

Next, the arithmetic unit 203 calculates the equation 241 using the calculation result of the equation 240.

[0249]

[Formula 241]

Next, the arithmetic unit 203 calculates the decoding result shown in Expression 242 using the power multiplication unit 202 using the calculation result of Expression 241. Note that [a] ⁿ and [a] _n represent the upper and lower n bits of a, respectively.

[0251]

[Equation 242]

However, when the decryption result is “*”, the arithmetic unit 203 rejects the decryption of the encryption results y ₁ and y ₂ , and outputs the fact to the output unit 207.

Next, the decryption unit 208 uses the decryption result K '(that is, the data encryption / decryption key K) according to the equation 242,
The ciphertext c stored in the storage unit 205 is decrypted by the existing encryption method. Then, the decoding result (that is, the message m) is output from the output unit 207.

(Eighth Embodiment) The public key cryptographic communication method of the fourth embodiment described above is used together with an existing cryptographic method (for example, common key cryptography) for the purpose of delivering a data encryption key in common key cryptography. The case where it is used will be described as an eighth embodiment of the present invention.

1. Key Generation Processing In the receiver-side device 200, the key generation unit 201 follows the instruction from the operator (recipient) and the secret key (p, q) of the receiver.
And the recipient's public key (N, k, G, H)
3, generated by the equation 244. Then, the generated information is stored in the storage unit 205.

[0256]

[Numerical formula 243]

[0257]

[Equation 244]

Next, the receiver sends the public information including the public key (N, k, G, H) of the receiver generated by the key generation unit 201 of the receiver side device 200 to the sender (sender side device). 100 operators)
Let us know. For example, in the receiver-side device 200, the key generation unit 201 transmits public information to the sender-side device 100 via the communication unit 206 according to an instruction from the receiver. Alternatively, the recipient publishes the public information by a known method such as registration with a third party (public information management organization). This public information is stored in the storage unit 1 of the sender device 100.
It is stored in 05.

2. Encryption processing In the sender device 100, the input unit 107 is an operator
Accept input of sent message m from (sender)
Then, the encryption unit 108 uses the data encryption / decryption key K (K∈ {0,1}ⁿ)
Encrypt the message m using the existing encryption method using
And generate the ciphertext c. Next, the random number generation unit 101
Is a random number r ∈ {0,1} for the data encryption / decryption key K. ^k0Choose
Bu Then, the calculation unit 103 stores this random number r in advance.
Recipient's public key (N, k, G, H) stored in memory 105
And using the power multiplication unit 102 to calculate the number 245.
Calculate

[0260]

[Equation 245]

Here, n + k ₀ + k ₁ <k-2.

Next, the arithmetic part 103 calculates the expression 246 using the calculation result s, t of the expression 245.

[0263]

[Equation 246]

Here, a = (m / N) represents the Jacobi symbol.

Next, the communication section 106 transmits the cipher results y ₁ , y ₂ , y ₃ of the equation 246 together with the ciphertext c of the message m to the receiver side device 200 via the communication line 300.

3. In the decryption processing receiver side device 200, the communication unit 206 receives the encryption result y ₁ , y from the sender side device 100 via the communication line 300.
₂ and y ₃ are received together with the ciphertext c and stored in the storage unit 205. By the way, the arithmetic unit 203 follows the instruction from the operator (transmitter) to calculate the power multiplication unit 202 and the remainder arithmetic unit 2.
By using 04, the secret key of the recipient stored in the storage unit 205 is used to calculate Expression 247 from the cipher results y ₁ , y ₂ , y ₃ stored in the storage unit 205.

[0267]

[Equation 247]

Then, the arithmetic unit 203 outputs φ (x _{1, p} ,
x _{1, q} ), φ (-x _{1, p} , x _{1, q} ), φ (x _{1, p} , -x _{1, q} ), φ (-x _{1, p} ,-
x _{1, q} ) (where φ is Z / (p) according to the Chinese Remainder Theorem
X represents the homomorphic mapping from Z / (q) to Z / (pq)), and (x / N) = y ₃ and 0 <x <2 ^k-2 is ^defined as s', and Equation 248 is calculated. To do.

[0269]

[Equation 248]

Next, the arithmetic unit 203 calculates the decoding result shown in Expression 249 using the power multiplication unit 202 using the calculation result of Expression 248. Note that [a] ⁿ and [a] _n represent the upper and lower n bits of a, respectively.

[0271]

[Equation 249]

However, when the decryption result is “*”, the arithmetic unit 203 rejects the decryption of the encryption results y ₁ , y ₂ , y ₃ and outputs the fact to the output unit 207.

Next, the decryption unit 208 uses the decryption result K '(that is, the data encryption / decryption key K) according to the equation 249,
The ciphertext c stored in the storage unit 205 is decrypted by the existing encryption method. Then, the decoding result (that is, the message m) is output from the output unit 207.

(Ninth Embodiment) The public key cryptographic communication method of the fifth embodiment described above is used together with an existing cryptographic method (for example, common key cryptography) for the purpose of delivering a data encryption key in common key cryptography. The case of using it will be described as a ninth embodiment of the present invention.

1. Key Generation Processing In the receiver-side device 200, the key generation unit 201 follows the instruction from the operator (recipient) and the secret key (p, q) of the receiver.
And the recipient's public key (N, k, G, H)
0 is generated by the number 251. Then, the generated information is stored in the storage unit 205.

[0276]

[Equation 250]

[0277]

[Formula 251]

Next, the receiver sends the public information including the public key (N, k, G, H) of the receiver generated by the key generation unit 201 of the receiver side device 200 to the sender (sender side device). 100 operators)
Let us know. For example, in the receiver-side device 200, the key generation unit 201 transmits public information to the sender-side device 100 via the communication unit 206 according to an instruction from the receiver. Alternatively, the recipient publishes the public information by a known method such as registration with a third party (public information management organization). This public information is stored in the storage unit 1 of the sender device 100.
It is stored in 05.

2. Encryption processing In the sender device 100, the input unit 107 is an operator
Accept input of sent message m from (sender)
Then, the encryption unit 108 uses the data encryption / decryption key K (K∈ {0,1}ⁿ)
Encrypt the message m using the existing encryption method using
And generate the ciphertext c. Next, the random number generation unit 101
Is a random number r ∈ {0,1} for the data encryption / decryption key K. ^k0Choose
Bu Then, the calculation unit 103 stores this random number r in advance.
Recipient's public key (N, k, G, H) stored in memory 105
Using and, the power multiplication unit 102 is used to calculate the number 252.
Calculate

[0280]

[Expression 252]

Here, n + k ₀ + k ₁ <k−2.

Next, the arithmetic unit 103 uses the calculation result s, t of the equation 252 to calculate the power multiplication unit 102 and the remainder arithmetic unit 1.
The number 253 is calculated using 04.

[0283]

[Equation 253]

Next, the communication section 106 sends the cipher results y ₁ and y ₂ of the equation 253 together with the ciphertext c of the message m to the communication line 30.
It is transmitted to the receiver-side device 200 via 0.

3. In the decryption processing receiver side device 200, the communication unit 206 receives the encryption result y ₁ , y from the sender side device 100 via the communication line 300.
₂ is received together with the ciphertext c and stored in the storage unit 205. By the way, the calculation unit 203 follows the instruction from the operator (sender) and the power multiplication unit 202 and the remainder calculation unit 204.
Using the private key of the recipient stored in the storage unit 205, the encryption result stored in the storage unit 205
Mathematical formula 254 is calculated from y ₁ and y ₂ .

[0286]

[Formula 254]

Then, the arithmetic unit 203 determines that φ (x _{1, p} ,
x _{1, q} ), φ (-x _{1, p} , x _{1, q} ), φ (x _{1, p} , -x _{1, q} ), φ (-x _{1, p} ,-
x _{1, q} ) (where φ is Z / (p) according to the Chinese Remainder Theorem
X represents a homomorphic mapping from Z / (q) to Z / (pq)), and s '(s' may exist more than one) that satisfies 0 <x <2 ^k-2 To calculate.

[0288]

[Equation 255]

Next, the arithmetic unit 203 calculates the decoding result shown in Expression 256 by using the exponentiation unit 202, using the calculation result in Expression 255. Note that [a] ⁿ and [a] _n represent the upper and lower n bits of a, respectively.

[0290]

[Equation 256]

However, when the decryption result is “*”, the arithmetic unit 203 rejects the decryption of the encryption results y ₁ and y ₂ , and outputs the fact to the output unit 207.

Next, the decryption unit 208 uses the decryption result K '(that is, the data encryption / decryption key K) according to the equation 256,
The ciphertext c stored in the storage unit 205 is decrypted by the existing encryption method. Then, the decoding result (that is, the message m) is output from the output unit 207.

(Tenth Embodiment) Next, a modified example of the fourth embodiment will be described together with an existing encryption method (for example, common key encryption) for the purpose of delivering a data encryption key in common key encryption. The case of using the first of the present invention
0 embodiment will be described.

1. Key Generation Processing In the receiver-side device 200, the key generation unit 201 follows the instruction from the operator (recipient) and the secret key p _i (1 ≦ 1) of the receiver.
i ≦ d) and the recipient's public key (N, k, G, H), respectively, in Equation 2
57 and the number 258. Then, the generated information is stored in the storage unit 205.

[0295]

[Equation 257]

[0296]

[Equation 258]

Here, the value of d is determined by the administrator or receiver of this system in advance or when necessary, and the key generation unit 201 takes in the determined value of d and receives it. The private key and public key of the person are to be generated.

Next, the receiver sends the public information including the public key (N, k, G, H) of the receiver generated by the key generation unit 201 of the receiver side device 200 to the sender (sender side device). 100 operators)
Let us know. For example, in the receiver-side device 200, the key generation unit 201 transmits public information to the sender-side device 100 via the communication unit 206 according to an instruction from the receiver. Alternatively, the recipient publishes the public information by a known method such as registration with a third party (public information management organization). This public information is stored in the storage unit 105 of the sender device 100.

2. Encryption processing In the sender device 100, the input unit 107 is an operator
Accept input of sent message m from (sender)
Then, the encryption unit 108 uses the data encryption / decryption key K (K∈ {0,1}ⁿ)
Encrypt the message m using the existing encryption method using
And generate the ciphertext c. Next, the random number generation unit 101
Is a random number r ∈ {0,1} for the data encryption / decryption key K. ^k0Choose
Bu Then, the calculation unit 103 stores this random number r in advance.
Recipient's public key (N, k, G, H) stored in memory 105
Using and, the power multiplication unit 102 is used to calculate the number 259.
Calculate

[0300]

[Equation 259]

Here, n + k ₀ + k ₁ ≦ log ₂ (N + 1).

Next, the arithmetic unit 103 uses the calculation result s, t of the equation 259 to calculate the power multiplication unit 102 and the remainder arithmetic unit 1.
The number 260 is calculated using 04.

[0303]

[Equation 260]

Next, the communication unit 106 sends the cipher texts y ₁ and y ₂ of Expression 260 together with the cipher text c of the message m to the communication line 30.
It is transmitted to the receiver side device 200 via 0.

3. In the decryption processing receiver side device 200, the communication unit 206 receives the encryption result y ₁ , y from the sender side device 100 via the communication line 300.
₂ is received together with the ciphertext c and stored in the storage unit 205. By the way, the calculation unit 203 follows the instruction from the operator (sender) and the power multiplication unit 202 and the remainder calculation unit 204.
Using the private key of the recipient stored in the storage unit 205, the encryption result stored in the storage unit 205
Expression 261 is calculated from y ₁ and y ₂ .

[0306]

[Formula 261]

[0307] Then, the arithmetic unit 203 outputs 2 ^d φ (± x
_{1, p1} , ± x _{1, p2,.} ． ． , ± x _{1, pd} ) (where φ is Z / (p ₁ ) × Z / (q ₂ ) × ... × Z / (q _d ) to Z / (N) according to the Chinese Remainder Theorem. (Representing a ring isomorphism map to), and s ′ (there may be a plurality of s ′) satisfying 0 <s ′ <N / 2, the equation 262 is calculated.

[0308]

[Equation 262]

Next, the arithmetic unit 203 calculates the decoding result shown in Expression 263 using the power multiplication unit 202, using the calculation result of Expression 262. Note that [a] ⁿ and [a] _n represent the upper and lower n bits of a, respectively.

[0310]

[Equation 263]

However, when the decryption result is “*”, the arithmetic unit 203 refuses to decrypt the encryption results y ₁ and y ₂ , and outputs the fact to the output unit 207.

Next, the decryption unit 208 uses the decryption result K '(that is, the data encryption / decryption key K) according to the equation 263,
The ciphertext c stored in the storage unit 205 is decrypted by the existing encryption method. Then, the decoding result (that is, the message m) is output from the output unit 207.

(Eleventh Embodiment) Next, the eleventh embodiment of the present invention.
The embodiment will be described by taking as an example a case where a sender transmits a message as transmission data to a receiver by cipher communication. FIG. 12 is a diagram for explaining the operation procedure of the eleventh embodiment of the present invention.

1. Key Generation Processing In the receiver-side device 200, the key generation unit 201 follows the instructions from the operator (recipient) and the public key (f, G,
H) and the recipient's private key are given in Eq. 264 and Eq. 265, respectively.
Generated by. Then, the generation information is stored in storage section 205 (ST7100).

[0315]

[Equation 264]

[0316]

[Equation 265]

Next, the receiver sends the public information including the public key (f, G, H) of the receiver generated by the key generation unit 201 of the receiver side device 200 to the sender (transmitter side device 100). Notify the operator) (ST7101). For example, the receiver device 20
0, the key generation unit 201 sends public information via the communication unit 206 to the sender-side device 1 according to an instruction from the receiver.
Send to 00. Alternatively, the recipient is, for example, a third party
By well-known methods such as registration with (public information management organization),
Make public information public. This public information is sent to the sender device 1
00 is stored in the storage unit 105.

2. In the encryption processing sender device 100, the input unit 107 receives an input of a message x (xε {0,1} ⁿ ) from an operator (sender) (ST7200). In response to this, the random number generator 10
1 selects a random number rε {0,1} ^k0 for the message x. Then, the calculation unit 103 uses the random number r and the storage unit 1 in advance.
Using the public key (f, G, H) of the receiver stored in 05, the number 266 is calculated (ST7201).

[0319]

[Equation 266]

Next, arithmetic section 103 calculates Expression 267 using calculation results s and t of Expression 266 (ST720).
2).

[0321]

[Equation 267]

The communication unit 106 calculates the calculation result y ₁ , y of the equation 267.
₂ is transmitted to the receiver-side device 200 via the communication line 300 as the ciphertext of the message x (ST720).
3).

3. In the decryption processing receiver device 200, the communication unit 206 transmits the ciphertexts y ₁ and y ₂ from the sender device 100 via the communication line 300.
Is received and stored in the storage unit 205. Now, the calculation unit 203 uses the recipient's private key stored in the storage unit 205 according to the instruction from the operator (sender),
From the ciphertext y ₁ and y ₂ stored in the storage unit 205,
8 is calculated (ST7300).

[0324]

[Equation 268]

Next, arithmetic section 203 calculates Expression 269 using the calculation result of Expression 268 (ST7301).

[0326]

[Equation 269]

However, x′ε {0,1} ⁿ and r′ε {0,1} ^k0 .

Next, the arithmetic unit 203 calculates the decoding result shown in Expression 270 using the calculation result of Expression 269 (S).
T7302).

[0329]

[Equation 270]

Then, the arithmetic section 203 outputs the decoding result x ′ from the output section 207. However, the decryption result is "*"
In this case, arithmetic section 203 refuses to decrypt the ciphertexts y ₁ and y ₂ , and outputs a message to that effect from output section 207 (ST730).
3).

According to the public key cryptographic communication method of the present embodiment, it is difficult to find the inverse function of the one-way permutation f, as in the third embodiment, and the selected ciphertext is used. It can be proved that the attack is confidential.

The present embodiment has a feature that the message length n can be set independently of the function f, as compared with the third embodiment. That is, the user can arbitrarily set the value of n according to the length of the message to be transmitted.

(Twelfth Embodiment) Next, a specific example of the eleventh embodiment will be described as a twelfth embodiment of the present invention. FIG. 13 is a diagram for explaining the operation procedure of the twelfth embodiment of the present invention.

1. Key Generation Processing In the receiver-side device 200, the key generation unit 201 follows the instruction from the operator (recipient) and the secret key (p, q) of the receiver.
And the recipient's public key (N, k, G, H),
It is generated by the equation 272. Then, the generated information is stored in the storage unit 2.
It is stored in 05 (ST8100).

[0335]

[Formula 271]

[0336]

[Formula 272]

Here, the value of d is determined by the administrator or receiver of this system in advance or when necessary, and the key generation unit 201 takes in the determined value of d and receives it. The private key and public key of the person are to be generated.

Next, the receiver sends the public information including the public key (N, k, G, H) of the receiver generated by the key generation unit 201 of the receiver side device 200 to the sender (sender side device). 100 operators)
(ST8101). For example, the receiver device 2
In 00, the key generation unit 201 transmits the public information to the sender-side device 100 via the communication unit 206 according to the instruction from the receiver. Alternatively, the recipient is, for example, a third party
By well-known methods such as registration with (public information management organization),
Make public information public. This public information is sent to the sender device 1
00 is stored in the storage unit 105.

The secret key (p, q) should be created by selecting a prime number such that p = 2p '+ 1, q = 2q' + 1 from other prime numbers p ', q'. Is also possible.

2. In the encryption processing sender device 100, the input unit 107 receives an input of the message x (xε {0,1} ⁿ ) from the operator (sender) (ST8200). In response to this, the random number generator 10
1 selects a random number rε {0,1} ^k0 for the message x. Then, the calculation unit 103 uses the random number r and the storage unit 1 in advance.
Using the public key (N, k, G, H) of the receiver stored in 05, the number 273 is calculated (ST8201).

[0341]

[Numerical Expression 273]

Next, the arithmetic unit 103 uses the calculation result s, t of the equation 273 to calculate the power multiplication unit 102 and the remainder arithmetic unit 1.
The number 274 is calculated using 04 (ST8202).

[0343]

[Formula 274]

Here, a = (m / N) represents the Jacobi symbol. Next, the communication unit 106 uses the calculation results y ₁ , y ₂ , y ₃ of Equation 274 as
The ciphertext of the message x is transmitted to the receiver-side device 200 via the communication line 300 (ST8203).

3. In the decryption processing receiver side device 200, the communication unit 206 receives the ciphertexts y ₁ , y ₂ , from the sender side device 100 via the communication line 300.
It receives y ₃ and stores it in the storage unit 205. Now,
The calculation unit 203 follows the instruction from the operator (sender),
From the ciphertexts y ₁ , y ₂ , y ₃ stored in the storage unit 205, by using the receiver's private key stored in the storage unit 205 and using the power multiplication unit 102 and the remainder calculation unit 104. The number 275 is calculated (ST8300).

[0346]

[Equation 275]

Then, the arithmetic unit 203 determines that φ (x _{1, p} ,
x _{1, q} ), φ (-x _{1, p} , x _{1, q} ), φ (x _{1, p} , -x _{1, q} ), φ (-x _{1, p} ,-
x _{1, q} ) (where φ is Z / (p) according to the Chinese Remainder Theorem
× Z / (q) to Z / (pq) represents a homomorphic map), and (x / N) = y ₃ and 0 <x <2 ^k-2 is ^defined as s', and Equation 276 is calculated. (ST8301 to ST8303).

[0348]

[Equation 276]

Here, x′ε {0,1} ⁿ and r′ε {0,1} ^k0 .

Next, the arithmetic unit 203 calculates the decoding result shown in Expression 277 using the calculation result of Expression 276 (S).
T8304).

[0351]

[Equation 277]

Then, the arithmetic unit 203 outputs the decoding result x ′ from the output unit 207. However, the decryption result is "*"
In the case of, the arithmetic unit 203 refuses to decrypt the ciphertext y ₁ , y ₂ , y ₃ and outputs the fact to the output unit 207 (ST830).
5).

In this embodiment, the value of d (d ≧ 1) described above can be changed. For example, when the bit length of the message is always small, it is possible to speed up the decoding process by increasing the value of d in the range where it is difficult to factorize the prime number of N described above.

Further, in the public key cryptographic communication method of the present embodiment, for example, when d = 3, it can be shown that complete decipherment is impossible on the premise of the difficulty of the N factorization problem.
That is, if there is an algorithm for solving the prime factorization problem of N, the algorithm can be used to configure an algorithm for performing complete decryption of the public key cryptographic communication method of the present embodiment. Further, if there is an algorithm for performing complete decryption of the public key cryptographic communication method of the present embodiment, the algorithm can be used to construct an algorithm for solving the N factorization problem.

(Thirteenth Embodiment) Next, a modified example of the twelfth embodiment will be described as a thirteenth embodiment of the present invention. FIG. 14 is a diagram for explaining the operation procedure of the thirteenth embodiment of the present invention.

1. Key Generation Processing In the receiver-side device 200, the key generation unit 201 follows the instruction from the operator (recipient) and the secret key (p, q) of the receiver.
And the recipient's public key (N, k, G, H), respectively, in the number 278,
It is generated by the equation 279. Then, the generated information is stored in the storage unit 2.
It is stored in 05 (ST9100).

[0357]

[Equation 278]

[0358]

[Equation 279]

Here, the value of d is determined by the administrator or receiver of this system in advance or when necessary, and the key generation unit 201 takes in the determined value of d and receives it. The private key and public key of the person are to be generated.

Next, the receiver sends the public information including the public key (N, k, G, H) of the receiver generated by the key generation unit 201 of the receiver side device 200 to the sender (sender side device). 100 operators)
(ST9101). For example, the receiver device 2
In 00, the key generation unit 201 transmits the public information to the sender-side device 100 via the communication unit 206 according to the instruction from the receiver. Alternatively, the recipient is, for example, a third party
By well-known methods such as registration with (public information management organization),
Make public information public. This public information is sent to the sender device 1
00 is stored in the storage unit 105.

The secret key (p, q) should be created by selecting a prime number such that p = 2p '+ 1, q = 2q' + 1 from other prime numbers p ', q'. Is also possible.

2. In the encryption processing sender device 100, the input unit 107 receives an input of the message x (xε {0,1} ⁿ ) from the operator (sender) (ST9200). In response to this, the random number generator 10
1 selects a random number rε {0,1} ^k0 for the message x. Then, the calculation unit 103 uses the random number r and the storage unit 1 in advance.
Using the public key (N, k, G, H) of the receiver stored in 05, the formula 280 is calculated (ST9201).

[0363]

[Equation 280]

Next, the arithmetic unit 103 uses the calculation results s and t of Equation 280 to calculate the power multiplication unit 102 and the remainder arithmetic unit 1.
The number 281 is calculated using 04 (ST9202).

[0365]

[Formula 281]

Next, the communication unit 106 uses the calculation results y ₁ and y ₂ of the equation 281 as the ciphertext of the message x and the communication line 30.
To the receiver-side device 200 via 0 (ST92
03).

3. In the decryption processing receiver device 200, the communication unit 206 transmits the ciphertexts y ₁ and y ₂ from the sender device 100 via the communication line 300.
Is received and stored in the storage unit 205. Now, the calculation unit 203 uses the recipient's private key stored in the storage unit 205 according to the instruction from the operator (sender),
Utilizing the power multiplication unit 102 and the remainder calculation unit 104,
From the ciphertext y ₁ and y ₂ stored in the storage unit 205,
Calculate 2 (ST9300).

[0368]

[Equation 282]

Then, the arithmetic unit 203 outputs φ (x _{1, p} ,
x _{1, q} ), φ (-x _{1, p} , x _{1, q} ), φ (x _{1, p} , -x _{1, q} ), φ (-x _{1, p} ,-
x _{1, q} ) (where φ is Z / (p) according to the Chinese Remainder Theorem
XZ / (q) to Z / (pq)), and s '(s' may exist more than once) satisfying 0 <x <2 ^k-2. Is calculated (ST9301 to ST9303).

[0370]

[Equation 283]

Here, x′ε {0,1} ⁿ and r′ε {0,1} ^k0 .

Next, the arithmetic unit 203 calculates the decoding result shown in Expression 284 using the calculation result of Expression 283 (S).
T9304).

[0373]

[Formula 284]

Then, the arithmetic section 203 outputs the decoding result x ′ from the output section 207. However, the decryption result is "*"
In the case of, the arithmetic unit 203 refuses to decrypt the ciphertexts y ₁ and y ₂ and outputs a message to that effect from the output unit 207 (ST930).
5).

In this embodiment, the above-mentioned value of d (d ≧ 1) can be changed. For example, when the bit length of the message is always small, it is possible to speed up the decoding process by increasing the value of d in the range where it is difficult to factorize the prime number of N described above.

Further, in the public key cryptographic communication method of the present embodiment, for example, when d = 3, it can be shown that complete decryption is impossible on the premise of the difficulty of the factorization problem of N.
That is, if there is an algorithm for solving the prime factorization problem of N, the algorithm can be used to configure an algorithm for performing complete decryption of the public key cryptographic communication method of the present embodiment. Further, if there is an algorithm for performing complete decryption of the public key cryptographic communication method of the present embodiment, the algorithm can be used to construct an algorithm for solving the N factorization problem.

(Fourteenth Embodiment) Next, a modification of the twelfth embodiment will be described as a fourteenth embodiment of the present invention. FIG. 15 is a diagram for explaining the operation procedure of the fourteenth embodiment of the present invention.

1. Key Generation Processing In the receiver-side device 200, the key generation unit 201 follows the instruction from the operator (recipient) and the secret key p _i (1 ≦ 1) of the receiver.
i ≦ d) and the recipient's public key (N, k, G, H)
5, generated by the number 286. Then, the generation information is stored in storage section 205 (ST10100).

[0379]

[Formula 285]

[0380]

[Equation 286]

Here, the value of d is determined by the administrator or receiver of this system in advance or when necessary, and the key generation unit 201 takes in the determined value of d and receives it. The private key and public key of the person are to be generated.

Next, the receiver sends the public information including the public key (N, k, G, H) of the receiver generated by the key generation unit 201 of the receiver side device 200 to the sender (sender side device). 100 operators)
(ST10101). For example, in the receiver-side device 200, the key generation unit 201 transmits public information to the sender-side device 100 via the communication unit 206 according to an instruction from the receiver. Alternatively, the recipient may be, for example, a third
Public information is disclosed by a well-known method such as registration with a person (public information management organization). This public information is stored in the storage unit 105 of the sender device 100.

The secret key p _i is a prime number p ′ different from these.
Therefore, it is also possible to create it by selecting a prime number such that p = 2p '+ 1.

2. In the encryption processing sender device 100, the input unit 107 receives an input of the message x (xε {0,1} ⁿ ) from the operator (sender) (ST10200). In response to this, the random number generator 1
01 selects a random number rε {0,1} ^k0 for the message x.
Then, arithmetic section 103 uses this random number r and the public key (N, k, G, H) of the receiver stored in storage section 105 in advance to calculate Equation 287 (ST10201).

[0385]

[Formula 287]

Here, k−1 ≦ log ₂ (N + 1).

Next, the arithmetic unit 103 uses the calculation result s, t of the equation 287 to calculate the power multiplication unit 102 and the remainder arithmetic unit 1.
The number 288 is calculated using 04 (ST1020
2).

[0388]

[Equation 288]

Next, the communication unit 106 uses the calculation results y ₁ and y ₂ of the equation 288 as the ciphertext of the message x and the communication line 30.
To the receiver-side device 200 via 0 (ST10
203).

3. In the decryption processing receiver device 200, the communication unit 206 transmits the ciphertexts y ₁ and y ₂ from the sender device 100 via the communication line 300.
Is received and stored in the storage unit 205. Now, the calculation unit 203 uses the recipient's private key stored in the storage unit 205 according to the instruction from the operator (sender),
Utilizing the power multiplication unit 102 and the remainder calculation unit 104,
From the ciphertext y ₁ and y ₂ stored in the storage unit 205,
9 is calculated (ST10300).

[0391]

[Equation 289]

Then, the arithmetic unit 203 outputs 2 ^d φ (± x
_{1, p1} , ± x _{1, p2,.} ． ． , ± x _{1, pd} ) (where φ is Z / (p ₁ ) × Z / (q ₂ ) × ... × Z / (q _d ) to Z / (N) according to the Chinese Remainder Theorem. (Representing a ring isomorphism map) to s ′ (there may be a plurality of s ′) satisfying 0 <s ′ <N / 2, the number 290 is calculated (ST10301, ST10302).

[0393]

[Formula 290]

Here, x′ε {0,1} ⁿ and r′ε {0,1} ^k0 .

Next, the arithmetic unit 203 calculates the decoding result shown in Expression 291 using the calculation result of Expression 290 (S).
T10303).

[0396]

[Numeric 291]

Then, the arithmetic unit 203 outputs the decoding result x ′ from the output unit 207. However, the decryption result is "*"
In the case of, the arithmetic unit 203 refuses to decrypt the ciphertexts y ₁ and y ₂ , and outputs the fact to the output unit 207 (ST1030).
4).

In the present embodiment, the value of d (d> 1) described above can be changed. In the public key cryptographic communication method of the present embodiment, for example, when d = 3, it can be shown that complete decryption is impossible on the premise of difficulty of the N factorization problem.
That is, if there is an algorithm for solving the prime factorization problem of N, the algorithm can be used to configure an algorithm for performing complete decryption of the public key cryptographic communication method of the present embodiment. Further, if there is an algorithm for performing complete decryption of the public key cryptographic communication method of the present embodiment, the algorithm can be used to construct an algorithm for solving the N factorization problem.

(Fifteenth Embodiment) Next, the eleventh embodiment described above should be used together with an existing encryption method (for example, common key encryption) for the purpose of delivering a data encryption key in common key encryption. This case will be described as a fifteenth embodiment of the present invention.

1. Key Generation Processing In the receiver-side device 200, the key generation unit 201 follows the instructions from the operator (recipient) and the public key (f, G,
H) and the recipient's private key, respectively,
Generated by. Then, the generated information is stored in the storage unit 205.

[0401]

[Equation 292]

[0402]

[Numerical Expression 293]

Next, the receiver sends the public information including the public key (f, G, H) of the receiver generated by the key generation unit 201 of the receiver side device 200 to the sender (transmitter side device 100). Notify the operator). For example, in the receiver-side device 200, the key generation unit 201 transmits public information to the sender-side device 100 via the communication unit 206 according to an instruction from the receiver. Alternatively, the recipient publishes the public information by a known method such as registration with a third party (public information management organization). This public information is stored in the storage unit 105 of the sender device 100.

2. Encryption processing In the sender device 100, the input unit 107 is an operator
Accept input of sent message m from (sender)
Then, the encryption unit 108 uses the data encryption / decryption key K (K∈ {0,1}ⁿ)
Encrypt the message m using the existing encryption method using
And generate the ciphertext c. Next, the random number generation unit 101
Is a random number r ∈ {0,1} for the data encryption / decryption key K. ^k0Choose
Bu Then, the calculation unit 103 stores this random number r in advance.
The public key (f, G, H) of the recipient stored in the storage unit 105
Is used to calculate the number 294.

[0405]

[Numerical formula 294]

Next, the arithmetic part 103 calculates the equation 295 using the calculation result s, t of the equation 294.

[0407]

[Formula 295]

Next, the communication unit 106 sends the cipher results y ₁ and y ₂ of Equation 295 together with the ciphertext c of the message m to the communication line 30.
It is transmitted to the receiver side device 200 via 0.

3. In the decryption processing receiver side device 200, the communication unit 206 receives the encryption result y ₁ , y from the sender side device 100 via the communication line 300.
₂ is received together with the ciphertext c and stored in the storage unit 205. Now, the calculation unit 203 uses the secret key of the receiver stored in the storage unit 205 according to the instruction from the operator (sender), and outputs the encryption result stored in the storage unit 205.
The number 296 is calculated from y ₁ and y ₂ .

[0410]

[296]

Next, the arithmetic unit 203 calculates the equation 297 using the calculation result of the equation 296.

[0412]

[Numerical Expression 297]

Here, K′ε {0,1} ⁿ and r′ε {0,1} ^k0 . Next, the arithmetic unit 203 calculates the decoding result shown in Expression 298 using the calculation result of Expression 297.

[0414]

[Equation 298]

However, when the decryption result is “*”, the arithmetic unit 203 rejects the decryption of the encryption results y ₁ and y ₂ , and outputs the fact to the output unit 207.

Next, the decryption unit 208 uses the decryption result K '(that is, the data encryption / decryption key K) according to the equation 298,
The ciphertext c stored in the storage unit 205 is decrypted by the existing encryption method. Then, the decoding result (that is, the message m) is output from the output unit 207.

(Sixteenth Embodiment) Next, the above twelfth embodiment should be used together with an existing encryption method (for example, common key encryption) for the purpose of delivering a data encryption key in common key encryption. This case will be described as a 16th embodiment of the present invention.

1. Key Generation Processing In the receiver-side device 200, the key generation unit 201 follows the instruction from the operator (recipient) and the secret key (p, q) of the receiver.
And the recipient's public key (N, k, G, H),
It is generated by the number 300. Then, the generated information is stored in the storage unit 2.
Store in 05.

[0419]

[Numerical formula 299]

[0420]

[Equation 300]

Next, the receiver sends the public information including the public key (N, k, G, H) of the receiver generated by the key generation unit 201 of the receiver side device 200 to the sender (sender side device). 100 operators)
Let us know. For example, in the receiver-side device 200, the key generation unit 201 transmits public information to the sender-side device 100 via the communication unit 206 according to an instruction from the receiver. Alternatively, the recipient publishes the public information by a known method such as registration with a third party (public information management organization).
This public information is stored in the storage unit 105 of the sender device 100.

2. Encryption processing In the sender device 100, the input unit 107 is an operator
Accept input of sent message m from (sender)
Then, the encryption unit 108 uses the data encryption / decryption key K (K∈ {0,1}ⁿ)
Encrypt the message m using the existing encryption method using
And generate the ciphertext c. Next, the random number generation unit 101
Is a random number r ∈ {0,1} for the data encryption / decryption key K. ^k0Choose
Bu Then, the calculation unit 103 stores this random number r in advance.
Recipient's public key (N, k, G, H) stored in memory 105
The number 301 is calculated using and.

[0423]

[Equation 301]

Next, the arithmetic unit 103 uses the calculation result s, t of the equation 301 to calculate the power multiplication unit 102 and the remainder arithmetic unit 1.
The number 302 is calculated using 04.

[0425]

[Equation 302]

Here, a = (m / N) represents the Jacobi symbol. Next, the communication unit 106 uses the cipher results y ₁ , y ₂ , y ₃ of the equation 302 as
The ciphertext c of the message m is transmitted to the recipient device 200 via the communication line 300.

3. In the decryption processing receiver side device 200, the communication unit 206 receives the encryption result y ₁ , y from the sender side device 100 via the communication line 300.
₂ and y ₃ are received together with the ciphertext c and stored in the storage unit 205. Now, the arithmetic unit 203 uses the recipient's private key stored in the storage unit 205 in accordance with the instruction from the operator (sender), and outputs the cipher results y ₁ and y ₂ stored in the storage unit 205. , y ₃ is calculated as the number 303.

[0428]

[Equation 303]

Then, the arithmetic unit 203 determines that φ (x _{1, p} ,
x _{1, q} ), φ (-x _{1, p} , x _{1, q} ), φ (x _{1, p} , -x _{1, q} ), φ (-x _{1, p} ,-
x _{1, q} ) (where φ is Z / (p) according to the Chinese Remainder Theorem
× Z / (q) to Z / (pq) represents a homomorphic mapping), (x / N) = y ₃ and 0 <x <2 ^k-2 To do.

[0430]

[Equation 304]

Here, k′ε {0,1} ⁿ and r′ε {0,1} ^k0 . Next, the arithmetic unit 203 calculates the decoding result shown in Expression 305 using the calculation result of Expression 304.

[0432]

[Equation 305]

However, when the decryption result is “*”, the arithmetic unit 203 rejects the decryption of the encryption results y ₁ , y ₂ , y ₃ and outputs the fact to the output unit 207.

Next, the decryption unit 208 uses the decryption result K '(that is, the data encryption / decryption key K) according to the equation 305,
The ciphertext c stored in the storage unit 205 is decrypted by the existing encryption method. Then, the decoding result (that is, the message m) is output from the output unit 207.

(Seventeenth Embodiment) Next, the above thirteenth embodiment will be used together with an existing encryption method (for example, common key encryption) for the purpose of delivering a data encryption key in common key encryption. This case will be described as a 17th embodiment of the present invention.

1. Key Generation Processing In the receiver-side device 200, the key generation unit 201 follows the instruction from the operator (recipient) and the secret key (p, q) of the receiver.
And the recipient's public key (N, k, G, H) as
It is generated by Equation 307. Then, the generated information is stored in the storage unit 2.
Store in 05.

[0437]

[Equation 306]

[0438]

[Formula 307]

Next, the receiver sends the public information including the public key (N, k, G, H) of the receiver generated by the key generation unit 201 of the receiver side device 200 to the sender (sender side device). 100 operators)
Let us know. For example, in the receiver-side device 200, the key generation unit 201 transmits public information to the sender-side device 100 via the communication unit 206 according to an instruction from the receiver. Alternatively, the recipient publishes the public information by a known method such as registration with a third party (public information management organization).
This public information is stored in the storage unit 105 of the sender device 100.

2. Encryption processing In the sender device 100, the input unit 107 is an operator
Accept input of sent message m from (sender)
Then, the encryption unit 108 uses the data encryption / decryption key K (K∈ {0,1}ⁿ)
Encrypt the message m using the existing encryption method using
And generate the ciphertext c. Next, the random number generation unit 101
Is a random number r ∈ {0,1} for the data encryption / decryption key K. ^k0Choose
Bu Then, the calculation unit 103 stores this random number r in advance.
Recipient's public key (N, k, G, H) stored in memory 105
And are used to calculate the number 308.

[0441]

[Equation 308]

Next, the arithmetic unit 103 uses the calculation results s, t of the equation 308 to calculate the power multiplication unit 102 and the remainder arithmetic unit 1.
The number 309 is calculated using 04.

[0443]

[Formula 309]

Next, the communication unit 106 sends the cipher results y ₁ and y ₂ of Equation 309 together with the ciphertext c of the message m to the communication line 3
00 to the receiver-side device 200.

3. In the decryption processing receiver side device 200, the communication unit 206 receives the encryption result y ₁ , y from the sender side device 100 via the communication line 300.
₂ is received together with the ciphertext c and stored in the storage unit 205. Now, the calculation unit 203 uses the receiver's private key stored in the storage unit 205 in accordance with the instruction from the operator (sender), and the power multiplication unit 202 and the remainder calculation unit 20.
The encryption result stored in the storage unit 205 by using 4
The formula 310 is calculated from y ₁ and y ₂ .

[0446]

[Equation 310]

Then, the arithmetic unit 203 outputs φ (x _{1, p} ,
x _{1, q} ), φ (-x _{1, p} , x _{1, q} ), φ (x _{1, p} , -x _{1, q} ), φ (-x _{1, p} ,-
x _{1, q} ) (where φ is Z / (p) according to the Chinese Remainder Theorem
X Z / (q) to Z / (pq) is represented as a ring homomorphic map), and one satisfying 0 <x <2 ^k-2 is ^defined as s '(s' may exist more than once), To calculate.

[0448]

[Equation 311]

Here, k′ε {0,1} ⁿ and r′ε {0,1} ^k0 . Next, the arithmetic unit 203 calculates the decoding result shown in Expression 312, using the calculation result of Expression 311.

[0450]

[Equation 312]

However, when the decryption result is “*”, the arithmetic unit 203 rejects the decryption of the encryption results y ₁ and y ₂ , and outputs the fact to the output unit 207.

Next, the decryption unit 208 uses the decryption result K '(that is, the data encryption / decryption key K) according to the equation 312,
The ciphertext c stored in the storage unit 205 is decrypted by the existing encryption method. Then, the decoding result (that is, the message m) is output from the output unit 207.

(Eighteenth Embodiment) Next, a modified example of the twelfth embodiment will be described together with an existing encryption method (for example, common key encryption) for the purpose of delivering a data encryption key in common key encryption. The case of using the first of the present invention
This will be described as an eighth embodiment.

1. Key Generation Processing In the receiver-side device 200, the key generation unit 201 follows the instruction from the operator (recipient) and the secret key p _i (1 ≦ 1) of the receiver.
d) and the recipient's public key (N, k, G, H)
3 and 314 are generated. Then, the generated information is stored in the storage unit 205.

[0455]

[Equation 313]

[0456]

[Equation 314]

Next, the receiver sends the public information including the public key (N, k, G, H) of the receiver generated by the key generation unit 201 of the receiver side device 200 to the sender (sender side device). 100 operators)
Let us know. For example, in the receiver-side device 200, the key generation unit 201 transmits public information to the sender-side device 100 via the communication unit 206 according to an instruction from the receiver. Alternatively, the recipient publishes the public information by a known method such as registration with a third party (public information management organization).
This public information is stored in the storage unit 105 of the sender device 100.

2. Encryption processing In the sender device 100, the input unit 107 is an operator
Accept input of sent message m from (sender)
Then, the encryption unit 108 uses the data encryption / decryption key K (K∈ {0,1}ⁿ)
Encrypt the message m using the existing encryption method using
And generate the ciphertext c. Next, the random number generation unit 101
Is a random number r ∈ {0,1} for the data encryption / decryption key K. ^k0Choose
Bu Then, the calculation unit 103 stores this random number r in advance.
Recipient's public key (N, k, G, H) stored in memory 105
The number 315 is calculated using and.

[0459]

[Formula 315]

Here, k−1 ≦ log ₂ (N + 1). Next, the calculation unit 103 uses the calculation result s, t of Expression 315 and uses the power multiplication unit 102 and the remainder calculation unit 104 to calculate Expression 31.
Calculate 6.

[0461]

[Formula 316]

Next, the communication section 106 sends the cipher results y ₁ and y ₂ of the formula 316 together with the ciphertext c of the message m to the communication line 3
00 to the receiver-side device 200.

3. In the decryption processing receiver side device 200, the communication unit 206 receives the encryption result y ₁ , y from the sender side device 100 via the communication line 300.
₂ is received together with the ciphertext c and stored in the storage unit 205. Now, the calculation unit 203 uses the receiver's private key stored in the storage unit 205 in accordance with the instruction from the operator (sender), and the power multiplication unit 202 and the remainder calculation unit 20.
The encryption result stored in the storage unit 205 by using 4
Equation 317 is calculated from y ₁ and y ₂ .

[0464]

[Expression 317]

Then, the arithmetic unit 203 outputs 2 ^d φ (± x
_{1, p1} , ± x _{1, p2,.} ． ． , ± x _{1, pd} ) (where φ is Z / (p ₁ ) × Z / (q ₂ ) × ... × Z / (q _d ) to Z / (N) according to the Chinese Remainder Theorem. (Representing a ring isomorphism map to), and s ′ (there may be a plurality of s ′) satisfying 0 <s ′ <N / 2, the equation 318 is calculated.

[0466]

[Expression 318]

Here, K′ε {0,1} ⁿ and r′ε {0,1} ^k0 . Next, the arithmetic unit 203 calculates the decoding result shown in Expression 319 using the calculation result of Expression 318.

[0468]

[Formula 319]

However, when the decryption result is “*”, the arithmetic unit 203 rejects the decryption of the encryption results y ₁ and y ₂ , and outputs the fact to the output unit 207.

Next, the decryption unit 208 uses the decryption result K '(that is, the data encryption / decryption key K) according to the equation 319,
The ciphertext c stored in the storage unit 205 is decrypted by the existing encryption method. Then, the decoding result (that is, the message m) is output from the output unit 207.

(19th Embodiment) The 19th embodiment of the present invention will now be described.
The embodiment will be described by taking as an example a case where a sender transmits a message as transmission data to a receiver by cipher communication. FIG. 16 is a diagram for explaining the operation procedure of the nineteenth embodiment of the present invention.

1. Key Generation Processing In the receiver-side device 200, the key generation unit 201 follows the instructions from the operator (recipient) and the public key (f, G,
H) and the recipient's private key, respectively
Generated by. Then, the generation information is stored in the storage unit 205 (ST11100).

[0473]

[Equation 320]

[0474]

[Numerical Expression 321]

Next, the receiver sends the public information including the public key (f, G, H) of the receiver generated by the key generation unit 201 of the receiver side device 200 to the sender (transmitter side device 100 Notify the operator (ST11101). For example, the receiver device 2
In 00, the key generation unit 201 transmits the public information to the sender-side device 100 via the communication unit 206 according to the instruction from the receiver. Alternatively, the recipient is, for example, a third party
By well-known methods such as registration with (public information management organization),
Make public information public. This public information is sent to the sender device 1
00 is stored in the storage unit 105.

2. In the encryption processing sender device 100, the input unit 107 receives an input of the message x (xε {0,1} ⁿ ) from the operator (sender) (ST11200). In response to this, the random number generator 1
01 selects a random number rε {0,1} ^k for the message x.
Then, arithmetic section 103 calculates equation 322 using this random number r and the public key (f, G, H) of the receiver stored in storage section 105 in advance (ST7201).

[0477]

[Equation 322]

The communication unit 106 calculates the calculation result y ₁ , y of the equation 322.
₂ as the ciphertext of the message x is transmitted to the receiver-side device 200 via the communication line 300 (ST1120).
2).

3. In the decryption processing receiver device 200, the communication unit 206 transmits the ciphertexts y ₁ and y ₂ from the sender device 100 via the communication line 300.
Is received and stored in the storage unit 205. Now, the calculation unit 203 uses the recipient's private key stored in the storage unit 205 according to the instruction from the operator (sender),
From the ciphertexts y ₁ and y ₂ stored in the storage unit 205, Equation 32
3 is calculated (ST11300).

[0480]

[Expression 323]

Next, arithmetic section 203 calculates equation 324 using the calculation result of equation 323 (ST11301).

[0482]

[Expression 324]

However, x′ε {0,1} ⁿ and w′ε {0,1} ^k0 .

Next, the arithmetic unit 203 calculates the decoding result shown in Expression 325 using the calculation result of Expression 324 (S).
T11302).

[0485]

[Expression 325]

Then, the arithmetic section 203 outputs the decoding result x ′ from the output section 207. However, the decryption result is "*"
In the case of, the arithmetic unit 203 refuses to decrypt the ciphertexts y ₁ and y ₂ , and outputs a message to that effect from the output unit 207 (ST1130).
3).

According to the public key cryptographic communication method of the present embodiment, it is difficult to find the inverse function of the one-way permutation f, similarly to the third embodiment, and the selected ciphertext is used. It can be proved that the attack is confidential.

The present embodiment is a part of ciphertext, as compared with the third and eleventh embodiments.
There is an advantage that y ₁ can be preprocessed. That is, since y ₁ can be calculated independently of the message x, high-speed encryption can be performed by calculating in advance.

Further, this embodiment has an advantage that the message length n can be set without depending on the function f, as in the eleventh embodiment. That is, the user can arbitrarily set the value of n according to the length of the message to be transmitted.

(Twentieth Embodiment) Next, a specific example of the nineteenth embodiment will be described as a twentieth embodiment of the present invention. FIG. 17 is a diagram for explaining the operation procedure of the twentieth embodiment of the present invention.

1. Key Generation Processing In the receiver-side device 200, the key generation unit 201 follows the instruction from the operator (recipient) and the secret key (p, q) of the receiver.
And the recipient's public key (N, k, G, H), respectively, in the number 326,
It is generated by the equation 327. Then, the generated information is stored in the storage unit 2.
It is stored in 05 (ST12100).

[0492]

[Expression 326]

[0493]

[Expression 327]

Next, the receiver sends the public information including the public key (N, k, G, H) of the receiver generated by the key generation unit 201 of the receiver side device 200 to the sender (sender side device). 100 operators)
(ST12101). For example, in the receiver-side device 200, the key generation unit 201 transmits public information to the sender-side device 100 via the communication unit 206 according to an instruction from the receiver. Alternatively, the recipient may be, for example, a third
Public information is disclosed by a well-known method such as registration with a person (public information management organization). This public information is stored in the storage unit 105 of the sender device 100.

The secret keys p and q are prime numbers different from these.
It is also possible to create from p ', q' by p = 2p '+ 1, q = 2q' + 1.

2. In the encryption processing sender device 100, the input unit 107 receives an input of a message x (xε {0,1} ⁿ ) from an operator (sender) (ST12200). In response to this, the random number generator 1
01 selects a random number rε {0,1} ^k−2 for the message x. Then, the calculation unit 103 uses the random number r and the public key (N, k, G, H) of the receiver stored in the storage unit 105 in advance.
And are used,
Using, the equation 328 is calculated (ST12201).

[0497]

[Equation 328]

Here, a = (m / N) represents the Jacobi symbol. Communication
The belief unit 106 calculates the calculation result y of Equation 328. ₁, y₂, y₃The Messe
Received as ciphertext of page x via communication line 300
It is transmitted to the person-side device 200 (ST12202).

3. In the decryption processing receiver side device 200, the communication unit 206 receives the ciphertexts y ₁ , y ₂ , from the sender side device 100 via the communication line 300.
It receives y ₃ and stores it in the storage unit 205. Now,
The calculation unit 203 follows the instruction from the operator (sender),
Using the recipient's private key stored in storage unit 205, Equation 329 is calculated from ciphertext y ₁ , y ₂ , y ₃ stored in storage unit 205 (ST12300).

[0500]

[Numeric 329]

Then, the arithmetic unit 203 determines that φ (r _{1, p} ,
r _{1, q} ), φ (-r _{1, p} , r _{1, q} ), φ (r _{1, p} , -r _{1, q} ), φ (-r _{1, p} ,-
r _{1, q} ) (where φ is Z / (p) according to Chinese Remainder Theorem
× represents a ring isomorphism from Z / (q) Z / into (pq)), calculates the (r / N) = y ₃ and 0 <r <number 330 satisfies the 2 ^k-2 as r ' (ST12301 to ST12303).

[0502]

[Equation 330]

Here, x′ε {0,1} ⁿ and w′ε {0,1} ^k0 . Next, the arithmetic unit 203 calculates the decoding result shown in Expression 331 using the calculation result of Expression 330.

[0504]

[Formula 331]

However, when the decryption result is “*”, the arithmetic unit 203 rejects the decryption of the encryption results y ₁ , y ₂ , y ₃ and outputs the fact to the output unit 207.

In this embodiment, the value of d (d ≧ 1) described above can be changed. For example, when the bit length of the message is always small, it is possible to speed up the decoding process by increasing the value of d in the range where it is difficult to factorize the prime number of N described above.

In the public key cryptographic communication method of this embodiment, for example, when d = 3, it can be shown that complete decryption is impossible on the premise of the difficulty of the factorization problem of N. That is, if there is an algorithm for solving the prime factorization problem of N, the algorithm can be used to configure an algorithm for performing complete decryption of the public key cryptographic communication method of the present embodiment. Further, if there is an algorithm for performing complete decryption of the public key cryptographic communication method of the present embodiment, the algorithm can be used to construct an algorithm for solving the N factorization problem.

(Twenty-first Embodiment) Next, a modification of the above-mentioned nineteenth embodiment will be described as a twenty-first embodiment of the present invention. FIG. 18 is a diagram for explaining the operation procedure of the twenty-first embodiment of the present invention.

1. Key Generation Processing In the receiver-side device 200, the key generation unit 201 follows the instruction from the operator (recipient) and the secret key (p, q) of the receiver.
And the public key (N, k, G, H) of the recipient,
It is generated by the equation 333. Then, the generated information is stored in the storage unit 2.
It is stored in 05 (ST13100).

[0510]

[Expression 332]

[0511]

[Expression 333]

Next, the receiver sends the public information including the public key (N, k, G, H) of the receiver generated by the key generation unit 201 of the receiver side device 200 to the sender (sender side device). 100 operators)
(ST13101). For example, in the receiver-side device 200, the key generation unit 201 transmits public information to the sender-side device 100 via the communication unit 206 according to an instruction from the receiver. Alternatively, the recipient may be, for example, a third
Public information is disclosed by a well-known method such as registration with a person (public information management organization). This public information is stored in the storage unit 105 of the sender device 100.

The private keys p and q are prime numbers different from these.
It is also possible to create from p ', q' by p = 2p '+ 1, q = 2q' + 1.

2. In the encryption processing sender device 100, the input unit 107 accepts the input of the message x (xε {0,1} ⁿ ) from the operator (sender) (ST13200). In response to this, the random number generator 1
01 selects a random number rε {0,1} ^k−2 for the message x. Then, the calculation unit 103 uses the random number r and the public key (N, k, G, H) of the receiver stored in the storage unit 105 in advance.
And are used to calculate the power multiplication unit 102 and the remainder calculation unit 104.
Is used to calculate the equation 334 (ST13201).

[0515]

[Formula 334]

The communication unit 106 calculates the calculation result y ₁ , y of the equation 334.
₂ as the ciphertext of the message x is transmitted to the receiver-side device 200 via the communication line 300 (ST1320).
2).

3. In the decryption processing receiver device 200, the communication unit 206 transmits the ciphertexts y ₁ and y ₂ from the sender device 100 via the communication line 300.
Is received and stored in the storage unit 205. Now, the calculation unit 203 uses the recipient's private key stored in the storage unit 205 according to the instruction from the operator (sender),
From the ciphertext y ₁ and y ₂ stored in the storage unit 205,
5 is calculated (ST13300).

[0518]

[Formula 335]

Then, the computing section 203 determines that φ (r _{1, p} ,
r _{1, q} ), φ (-r _{1, p} , r _{1, q} ), φ (r _{1, p} , -r _{1, q} ), φ (-r _{1, p} ,-
r _{1, q} ) (where φ is Z / (p) according to Chinese Remainder Theorem
X Z / (q) to Z / (pq) represents a homomorphic map), and the one satisfying 0 <r <2 ^k-2 is ^defined as r '(there may be a plurality of r's).
36 is calculated (ST13301 to ST13303).

[0520]

[Formula 336]

Here, x′ε {0,1} ⁿ and w′ε {0,1} ^k0 . Next, the arithmetic unit 203 calculates the decoding result shown in Expression 337 using the calculation result of Expression 336.

[0522]

[Formula 337]

However, when the decryption result is “*”, the arithmetic unit 203 refuses to decrypt the encryption results y ₁ and y ₂ , and outputs the fact to the output unit 207.

In this embodiment, the value of d (d ≧ 1) described above can be changed. For example, when the bit length of the message is always small, it is possible to speed up the decoding process by increasing the value of d in the range where it is difficult to factorize the prime number of N described above.

In the public key cryptographic communication method of this embodiment, for example, when d = 3, it can be shown that complete decryption is impossible on the premise of the difficulty of the N factorization problem. That is, if there is an algorithm for solving the prime factorization problem of N, the algorithm can be used to configure an algorithm for performing complete decryption of the public key cryptographic communication method of the present embodiment. Further, if there is an algorithm for performing complete decryption of the public key cryptographic communication method of the present embodiment, the algorithm can be used to construct an algorithm for solving the N factorization problem.

(Twenty-second Embodiment) Next, a modification of the sixth embodiment will be described as a twenty-second embodiment of the present invention.

1. Key Generation Processing In the receiver-side device 200, the key generation unit 201 follows the instruction from the operator (recipient) and the secret key p _i (1 ≦ 1) of the receiver.
i ≦ d) and the recipient's public key (N, k, H ₁ , H ₂ ),
38, which is generated by the equation 339. Then, the generated information is stored in the storage unit 205.

[0528]

[Formula 338]

[0529]

[Formula 339]

Next, the receiver sends the public information including the public key (N, k, H ₁ , H ₂ ) of the receiver generated by the key generation unit 201 of the receiver side device 200 to the sender (sender). The operator of the side device 100). For example, in the receiver-side device 200, the key generation unit 201 transmits public information to the sender-side device 100 via the communication unit 206 according to an instruction from the receiver. Alternatively, the recipient publishes the public information by a known method such as registration with a third party (public information management organization). This public information is stored in the storage unit 105 of the sender device 100.

Note that the secret key p _i is a prime number p ′ different from these.
It is also possible to create from p = 2p '+ 1.

2. In the encryption processing sender device 100, the input unit 107 receives an input of the message x (xε {0,1} ⁿ ) from the operator (sender). In response to this, the random number generation unit 101 causes the message
Choose a random number rε {0,1} ^k0 for x. Then, the arithmetic unit 1
03 uses this random number r and the recipient's public key (N, k, H ₁ , H ₂ ) stored in the storage unit 105 in advance,
To calculate.

[0533]

[Expression 340]

Here, n + k ₀ + k ₁ ≦ log ₂ (N + 1). Next, the calculation unit 103 calculates the formula 341 using the calculation results s, t of the formula 340 and the power multiplication unit 102 and the remainder calculation unit 104.

[0535]

[Formula 341]

The communication unit 106 determines the calculation result y of the equation 341.
₁ is transmitted to the receiver-side device 200 via the communication line 300 as the ciphertext of the message x.

3. In the decryption processing recipient device 200, the communication unit 206 receives the ciphertext y ₁ from the sender device 100 via the communication line 300 and stores it in the storage unit 205. Now, the arithmetic unit 203 uses the recipient's private key stored in the storage unit 205 according to the instruction from the operator (sender), and uses the secret text of the ciphertext y ₁ stored in the storage unit 205 to calculate the number 342. To calculate.

[0538]

[Formula 342]

[0539] Then, the arithmetic unit 203^dΦ (± x
_{1, p1}, ± x_{1, p2},. ． ． , ± x_{1, pd}(However, φ is China
Z / (p₁) × Z / (q₂) ×. ． ． × Z / (q_d)
(Representing a homomorphic map to Z / (N)), 0 <w '<N / 2
Be w '(w' may exist more than once), and w '= s
₁'|| s₂'|| t' (s₁'∈ {0,1}ⁿ， S₂'∈ {0,1}^k1, T'∈ {0,
1} ^k0), The number 343 is calculated.

[0540]

[Formula 343]

Next, the arithmetic unit 203 calculates the decoding result shown in Expression 344 using the calculation result of Expression 343.

[0542]

[Formula 344]

However, when the decryption result is “*”, the arithmetic unit 203 refuses to decrypt the encryption result y ₁ and outputs a message to that effect from the output unit 207.

In the present embodiment, the value of d (d> 1) described above can be changed. In the public key cryptographic communication method of this embodiment, it is possible to show that complete decryption is impossible on the premise of the difficulty of the N factorization problem. That is, if there is an algorithm for solving the prime factorization problem of N, the algorithm can be used to configure an algorithm for performing complete decryption of the public key cryptographic communication method of the present embodiment. Further, if there is an algorithm for performing complete decryption of the public key cryptographic communication method of the present embodiment, the algorithm can be used to construct an algorithm for solving the N factorization problem.

The embodiments of the present invention have been described above.

The present invention is not limited to the above-mentioned embodiments, and various modifications can be made within the scope of the gist thereof.

For example, in each of the above-described embodiments, a general communication system in which a sender and a receiver perform cryptographic communication using their respective devices has been described as an example, but the present invention is applicable to various systems. Is applicable to.

For example, in the electronic shopping system,
The sender is a user, the sender device is a computer such as a personal computer, the receiver is a retail store, and the receiver device is a computer such as a personal computer. In this case, the order form of the user's product or the like is often encrypted with common key encryption,
The encryption key at that time is encrypted by the public key encryption communication method of the present invention and transmitted to the retail store side device.

Further, in the electronic mail system, each device is a computer such as a personal computer, and the transmitted text (mail) is often encrypted by common key encryption. In this case, the common key is encrypted by the public key cryptographic communication method of the present invention,
Sent to the recipient's computer.

Besides, it can be applied to various systems using the conventional public key encryption.

Further, each calculation in each of the above-described embodiments is C
It has been described as being performed by the PU executing the program loaded in the memory. But it's not just programs. The device that performs any of the calculations may be a hardware-based arithmetic device that exchanges data with another arithmetic device or a CPU.

[0552]

As described above, according to the present invention,
It is possible to provide a public-key cryptographic communication technology that can prove security.

[Brief description of drawings]

FIG. 1 is a schematic configuration diagram of a public key cryptographic communication system common to each embodiment of the present invention.

FIG. 2 is a schematic configuration diagram of a sender-side device 100 shown in FIG.

3 is a schematic configuration diagram of a receiver-side device 200 shown in FIG.

FIG. 4 is a sender device 100 and a receiver device 200.
3 is a diagram showing an example of the hardware configuration of FIG.

FIG. 5 is a diagram for explaining an operation procedure of the first embodiment of the present invention.

FIG. 6 is a diagram for explaining an operation procedure of the second embodiment of the present invention.

FIG. 7 is a diagram for explaining an operation procedure of the third embodiment of the present invention.

FIG. 8 is a diagram for explaining an operation procedure of the fourth embodiment of the present invention.

FIG. 9 is a public key cryptographic communication method according to a fourth embodiment of the present invention and a conventional cryptographic method (elliptic curve cryptography, RSA, OAEP + R).
It is a figure showing the size of the plaintext space with SA and the comparison of safety.

FIG. 10 is a diagram for explaining an operation procedure of the fifth embodiment of the present invention.

FIG. 11 is a diagram for explaining an operation procedure of the sixth embodiment of the present invention.

FIG. 12 is a diagram for explaining an operation procedure of the eleventh embodiment of the present invention.

FIG. 13 is a diagram for explaining the operation procedure of the twelfth embodiment of the present invention.

FIG. 14 is a diagram for explaining the operation procedure of the thirteenth embodiment of the present invention.

FIG. 15 is a diagram for explaining the operation procedure of the fourteenth embodiment of the present invention.

FIG. 16 is a diagram for explaining the operation procedure of the nineteenth embodiment of the present invention.

FIG. 17 is a diagram for explaining the operation procedure of the twentieth embodiment of the present invention.

FIG. 18 is a diagram for explaining an operation procedure of the twenty-first embodiment of the present invention.

[Explanation of Codes] 100 ... Sender-side device, 101 ... Random number generator, 102 ...
Power multiplication unit, 103 ... Arithmetic unit, 104 ... Modulo arithmetic unit, 1
05 ... storage unit, 106 ... communication unit, 107 ... input unit, 10
8 ... Encryption unit, 200 ... Recipient side device, 201 ... Key generation unit, 202 ... Exponentiation unit, 203 ... Remainder calculation unit, 204
... arithmetic unit, 205 ... storage unit, 206 ... communication unit, 207 ...
Decoding unit, 300 ... Communication line, 401 ... CPU, 402
... memory, 403 ... external storage device, 404 ... storage medium,
405 ... reading device, 406 ... input device, 407 ... output device, 408 ... communication device, 409 ... bus

   ─────────────────────────────────────────────────── ─── Continued front page    (72) Inventor Naoki Sato             1099 Ozenji, Aso-ku, Kawasaki City, Kanagawa Prefecture             Ceremony company Hitachi Systems Development Laboratory F-term (reference) 5J104 AA22 EA04 EA28 EA32 JA23                       JA27 NA02 NA12 NA18

Claims (48)

[Claims] 1. A public key encryption communication method in which a device on the sender side encrypts transmission data using a public key of the receiver and transmits the encrypted data to the device on the receiver side, wherein: Let be the recipient's private key (p, q), and Is the public key (N, k, G, H) of the receiver, and (1) in the device on the sender side, a random number r∈ {0,1 for plaintext x (x∈ {0,1} ⁿ } ^k0 is selected, and using this random number r and the public key of the receiver, Is calculated (however, n + k ₀ + k ₁ = k), and using the results s and t, Then, using the result w and the recipient's public key, Is transmitted to the device on the receiver side as a ciphertext, and (2) the device on the receiver side uses the secret key of the receiver to receive from the device on the sender side. From the encrypted ciphertext y, Is calculated, and using the result, And calculate And φ (x _p , x _q ), φ (-x _p , x _q ), φ (x _p ,-
x _q ), φ (-x _p , -x _q ) (where φ is the convolution map from Z / (p) × Z / (q) to Z / (pq) according to the Chinese Remainder Theorem. (Representing) Place as shown in By calculating, A public key cryptographic communication method characterized by calculating the decryption result shown in (However, if the decryption result is "*", this ciphertext is rejected). 2. A public-key cryptographic communication method in which a device on the sender side encrypts transmission data using the public key of the receiver, and transmits the encrypted data to the device on the receiver side. Let be the recipient's private key (p, q), and As the public key (N, k, G, H, H ') of the receiver, (1) In the device on the sender side, a random number r∈ {for plaintext x (x∈ {0,1} ⁿ ) 0,1} ^k0 is selected, and using this random number r and the public key of the recipient, (Where n + k ₀ + k ₁ = k), and using the results s and t, Then, using the result w and the recipient's public key, Is transmitted to the device on the receiver side as a ciphertext, and (2) the device on the receiver side uses the secret key of the receiver to receive from the device on the sender side. From the ciphertext y Is calculated, and using the result, And calculate And φ (x _p , x _q ), φ (-x _p , x _q ), φ (x _p ,-
x _q ), φ (-x _p , -x _q ) (where φ is the convolution map from Z / (p) × Z / (q) to Z / (pq) according to the Chinese Remainder Theorem. (Representing) Put as shown in, and By calculating A public key cryptographic communication method characterized by calculating the decryption result shown in (However, if the decryption result is "*", this ciphertext is rejected). 3. The public key cryptographic communication method according to claim 1, wherein the device on the sender side publishes or transmits the Jacobi symbol (w / N) to the device on the receiver side. Characterized public key cryptographic communication method. 4. The public key cryptographic communication method according to claim 1, 2 or 3, wherein in the device on the sender side, a magnitude relationship between the value of w and a value N / 2 that is half of N is established. A public key cryptographic communication method, characterized in that the information is disclosed or transmitted to the device on the recipient side. 5. The public key cryptographic communication method according to claim 1, 2, 3 or 4, wherein the prime numbers p ', q different from the prime numbers p, q constituting the secret key of the receiver. A public key cryptographic communication method characterized in that a prime number represented by 2p '+ 1,2q' + 1 is selected for '. 6. The public key cryptographic communication method according to claim 1, wherein the value of d (d ≧ 1) is variable. . 7. The public key cryptographic communication method according to claim 1, 2, 3, 4, 5 or 6, wherein the device on the receiver side generates and publishes the public information. Public key cryptographic communication method. 8. A public-key cryptographic communication method in which a device on the sender side encrypts transmission data using the public key of the receiver, and transmits the encrypted data to the device on the receiver side. Be the public key of the recipient, and Is the secret key of the receiver (however, k = k ₀ + k ₁ + n), and (1) in the device on the sender side, a random number r∈ for plaintext x (x∈ {0,1} ⁿ ) {0,1} ^k0 is selected, and using this random number r and the public key of the recipient, And the result s, t and the recipient's public key are used to calculate And transmit the results y ₁ and y ₂ as ciphertext to the device of the recipient, and (2) the device of the receiver uses the device of the sender using the secret key of the receiver. From the ciphertexts y ₁ and y ₂ received from Is calculated, and using the result, Then, using the result, Decryption result shown in (However, if the decryption result is "*", this ciphertext shall be rejected. Also, [a] ⁿ and [a] _n
Represents the upper and lower n bits of a), respectively, in the public key cryptographic communication method. 9. A public-key cryptographic communication method in which a device on the sender side encrypts transmission data using a public key of the receiver, and transmits the encrypted data to the device on the receiver side. Let be the recipient's private key (p, q), and Is the public key (N, k, G, H) of the receiver, and (1) in the device on the sender side, a random number r∈ {0,1 for plaintext x (x∈ {0,1} ⁿ ). } ^k0 is selected, and using this random number r and the public key of the receiver, (Where n + k ₀ + k ₁ <k-2), and using the result s, t and the recipient's public key, (Where a = (m / N) represents the Jacobi symbol), and as a result, y ₁ , y ₂ and y ₃ are transmitted as ciphertexts to the device of the recipient, and (2) the recipient. In the device on the side of the sender, using the secret key (p, q) of the receiver, from the ciphertext y ₁ , y ₂ , y ₃ received from the device on the sender side, And φ (x _{1, p} , x _{1, q} ), φ (-x _{1, p} , x _{1, q} ),
Of φ (x _{1, p} , -x _{1, q} ), φ (-x ₁ ,, _p , -x _{1, q} ), where φ is Z / (p) × Z / (according to Chinese Remainder Theorem q) to Z / (pq), which satisfies (x / N) = y ₃ and 0 <x <2 ^k-2
As s', By calculating Decryption result shown in (However, if the decryption result is "*", this ciphertext shall be rejected. Also, [a] ⁿ and [a] _n
Represents the upper and lower n bits of a), respectively, in the public key cryptographic communication method. 10. A public-key cryptographic communication method in which a device on the sender side encrypts transmission data using the public key of the receiver and transmits the encrypted data to the device on the receiver side, wherein: Let be the recipient's secret key (p, q), and Is the public key (N, k, G, H) of the receiver, and (1) in the device on the sender side, a random number r∈ {0,1 for plaintext x (x∈ {0,1} ⁿ ). } ^k0 is selected, and using this random number r and the public key of the receiver, (Where n + k ₀ + k ₁ <k-2), and using the result s, t and the recipient's public key, And transmit the results y ₁ and y ₂ as ciphertext to the device of the recipient, and (2) in the device of the recipient, using the secret key (p, q) of the recipient, From the ciphertexts y ₁ and y ₂ received from the sender side device, And φ (x _{1, p} , x _{1, q} ), φ (-x _{1, p} , x _{1, q} ),
Of φ (x _{1, p} , -x _{1, q} ), φ (-x ₁ ,, _p , -x _{1, q} ), where φ is Z / (p) × Z / (according to Chinese Remainder Theorem (representing a ring isomorphism map from q) to Z / (pq)), and s '(s' may exist more than one) satisfying 0 <x <2 ^k-2 , By calculating Decryption result shown in (However, if the decryption result is "*", this ciphertext shall be rejected. Also, [a] ⁿ and [a] _n
Represents the upper and lower n bits of a), respectively, in the public key cryptographic communication method. 11. The public key cryptographic communication method according to claim 9 or 10, wherein prime numbers p ', q'other than the prime numbers p, q constituting the secret key of the recipient are A public key cryptographic communication method characterized by selecting a prime number represented by 2p '+ 1, 2q' + 1. 12. A public key cryptographic communication method in which a device on the sender side encrypts transmission data using a public key of the receiver and transmits the encrypted data to the device on the receiver side, wherein: Be the recipient's private key p _i (1 ≦ i ≦ d), and Is the public key (N, k, G, H) of the receiver, and (1) in the device on the sender side, a random number r∈ {0,1 for plaintext x (x∈ {0,1} ⁿ } ^k0 is selected, and using this random number r and the public key of the receiver, (Where n + k ₀ + k ₁ ≦ log ₂ (N + 1)), and using the result s, t and the recipient's public key, And transmit the results y ₁ and y ₂ as ciphertext to the device of the recipient, and (2) the device of the receiver uses the device of the sender using the secret key of the receiver. From the ciphertexts y ₁ and y ₂ received from And then 2 ^d φ (± x _{1, p1,,} ±
x _{1, p2,.} ． ． , ± x _{1, pd} ) (where φ is Z / (p ₁ ) × Z / (q ₂ ) × ... × Z / (q _d ) to Z / (N) according to the Chinese Remainder Theorem.
, Which represents a ring isomorphism map to, s'that satisfies 0 <s'<N / 2
As (s ′ may exist more than once), By calculating Decryption result shown in (However, if the decryption result is "*", this ciphertext shall be rejected. Also, [a] ⁿ and [a] _n
Represents the upper and lower n bits of a), respectively, in the public key cryptographic communication method. 13. The public key cryptographic communication method according to claim 12, wherein the prime number p _i constituting the secret key of the recipient is represented by 2p ′ + 1 with respect to another prime number p ′. A public key cryptographic communication method characterized in that a selected prime number is selected. 14. The method according to claim 9, 10, 11, 12 or 13.
The disclosed public key cryptographic communication method, wherein the value of d (d ≧ 1) is variable. 15. The method according to claim 8, 9, 10, 11, 12, 13.
Or the public key cryptographic communication method according to Item 14, wherein the device on the recipient side generates and publishes the public information. 16. A public-key cryptographic communication method in which a device on the sender side encrypts a data encryption key using the public key of the receiver, and transmits the encrypted data encryption key to the device on the receiver side. Let be the recipient's public key, and Is the recipient's private key (where k = k ₀ + k ₁ + n), and (1) the data encryption key K (K ∈ {0,1} ⁿ ) is used in the sender device. While encrypting the transmission data m to create the ciphertext C, a random number rε {0,1} ^k0 is selected for the data encryption key K, and using this random number r and the public key of the receiver, Number 53] And using the result s, t and the public key of the recipient, And send the results y ₁ and y ₂ together with the ciphertext C to the device of the recipient, and (2) the device of the receiver uses the secret key of the receiver to send the sender. From the cipher results y ₁ and y ₂ received from the device on the side, Is calculated, and using the result, Then, using the result, Decryption result shown in (However, if the decryption result is "*", this encryption result is rejected. Also, [a] ⁿ and
[a] _n represents the upper and lower n bits of a, respectively, and further, using the calculation result K ′, decrypts the ciphertext C received from the sender-side device. A public key cryptographic communication method characterized by: 17. A public key encryption communication method in which a device on the sender side encrypts a data encryption key using the public key of the receiver and transmits the encrypted data encryption key to the device on the receiver side. Let be the recipient's private key (p, q), and As the recipient's public key (N, k, G, H) (where n + k ₀ + k ₁ <k-
2), (1) In the sender device, the transmission data m is encrypted by using the data encryption key K (K ∈ {0,1} ⁿ ) to create the ciphertext C, and the data encryption is performed. A random number r ∈ {0,1} ^k0 is selected for the key K, and using this random number r and the public key of the recipient, Then, using s, t and the public key of the recipient, (Where a = (m / N) represents the Jacobi symbol), and as a result, y ₁ , y ₂ and y ₃ are transmitted to the device of the recipient together with the ciphertext C, and (2) the above In the device on the receiver side, using the secret key of the receiver, from the cipher results y ₁ , y ₂ , y ₃ received from the device on the sender side, And φ (x _{1, p} , x _{1, q} ), φ (-x _{1, p} , x _{1, q} ),
Of φ (x _{1, p} , -x _{1, q} ), φ (-x ₁ ,, _p , -x _{1, q} ), where φ is Z / (p) × Z / (according to Chinese Remainder Theorem q) to Z / (pq), which satisfies (x / N) = y ₃ and 0 <x <2 ^k-2
As s', By calculating Decryption result shown in (However, if the decryption result is "*", this encryption result is rejected. Also, [a] ⁿ and
[a] _n represents the upper and lower n bits of a, respectively, and further, using the calculation result K ′, decrypts the ciphertext C received from the sender-side device. A public key cryptographic communication method characterized by: 18. A public-key cryptographic communication method, in which a device on the sender side encrypts a data encryption key using the public key of the receiver, and transmits the encrypted data encryption key to the device on the receiver side. Let be the recipient's private key (p, q), and As the recipient's public key (N, k, G, H) (where n + k ₀ + k ₁ <k-
2), (1) In the sender side device, the transmission data m is encrypted by using the data encryption key K (K ∈ {0,1} ⁿ ) to create the ciphertext C, and the data encryption is performed. A random number r ∈ {0,1} ^k0 is selected for the key K, and using this random number r and the public key of the recipient, Then, using s, t and the public key of the recipient, And send the results y ₁ and y ₂ together with the ciphertext C to the recipient's device, and (2) the recipient's device uses the recipient's private key (p, q). Then, from the cipher results y ₁ and y ₂ received from the sender side device, And φ (x _{1, p} , x _{1, q} ), φ (-x _{1, p} , x _{1, q} ),
Of φ (x _{1, p} , -x _{1, q} ), φ (-x ₁ ,, _p , -x _{1, q} ), where φ is Z / (p) × Z / (according to Chinese Remainder Theorem (representing a ring isomorphism map from q) to Z / (pq)), and s '(s' may exist more than one) satisfying 0 <x <2 ^k-2 , By calculating Decryption result shown in (However, if the decryption result is "*", this encryption result is rejected. Also, [a] ⁿ and
[a] _n represents the upper and lower n bits of a, respectively, and further, using the calculation result K ′, decrypts the ciphertext C received from the sender-side device. A public key cryptographic communication method characterized by: 19. The public key cryptographic communication method according to claim 17 or 18, wherein prime numbers p ', q'other than the prime numbers p, q constituting the secret key of the receiver are provided. A public key cryptographic communication method characterized by selecting a prime number represented by 2p '+ 1, 2q' + 1. 20. A public-key cryptographic communication method in which a device on the sender side encrypts a data encryption key using the public key of the receiver and transmits the encrypted data encryption key to the device on the receiver side, wherein: Be the recipient's private key p _i (1 ≦ i ≦ d), and As the recipient's public key (N, k, G, H) (where n + k ₀ + k ₁ <k-
2), (1) In the sender side device, the transmission data m is encrypted by using the data encryption key K (K ∈ {0,1} ⁿ ) to create the ciphertext C, and the data encryption is performed. A random number r ∈ {0,1} ^k0 is selected for the key K, and using this random number r and the public key of the receiver, (Where n + k ₀ + k ₁ ≦ log ₂ (N + 1)), and using the result s, t and the recipient's public key, And send the results y ₁ and y ₂ together with the ciphertext C to the device of the recipient, and (2) the device of the receiver uses the secret key of the receiver to send the sender. From the cipher results y ₁ and y ₂ received from the device on the side, And then 2 ^d φ (± x _{1, p1,,} ±
x _{1, p2,.} ． ． , ± x _{1, pd} ) (where φ is Z / (p ₁ ) × Z / (q ₂ ) × ... × Z / (q _d ) to Z / (N) according to the Chinese Remainder Theorem.
, Which represents a ring isomorphism map to, s'that satisfies 0 <s'<N / 2
As (s' may exist more than once), By calculating, Decryption result shown in (However, if the decryption result is "*", this encryption result is rejected. Also, [a] ⁿ and
[a] _n represents the upper and lower n bits of a, respectively, and further, using the calculation result K ′, decrypts the ciphertext C received from the sender-side device. A public key cryptographic communication method characterized by: 21. The public key cryptographic communication method according to claim 20, wherein the prime number p _i constituting the secret key of the recipient is represented by 2p '+ 1 with respect to another prime number p'. A public key cryptographic communication method characterized in that a selected prime number is selected. 22. A method according to claim 17, 18, 19, 20 or 2.
2. The public key cryptographic communication method according to 1, wherein the value of d (d ≧ 1) is variable. 23. A method according to claim 16, 17, 18, 19, 20,
23. The public key cryptographic communication method according to 21 or 22, wherein the device on the receiver side generates and publishes the public information. 24. A public-key cryptographic communication method in which a device on the sender side encrypts transmission data using the public key of the receiver and transmits the encrypted data to the device on the receiver side. Let be the recipient's public key, and Is used as a secret key of the receiver, and (1) in the device on the sender side, a random number r∈ {0,1} ^k0 is selected for the plaintext x (x∈ {0,1} ⁿ ) and Using the recipient's public key, And using the result s, t and the public key of the recipient, And transmit the results y ₁ and y ₂ as ciphertext to the device of the recipient, and (2) the device of the receiver uses the device of the sender using the secret key of the receiver. From the ciphertexts y ₁ and y ₂ received from And calculate the result using (Where x ′ ∈ {0,1} ⁿ , r ′ ∈ {0,1} ^k0 ) and using the result, A public key cryptographic communication method characterized by calculating the decryption result shown in (However, if the decryption result is "*", this ciphertext is rejected). 25. A public-key cryptographic communication method in which a device on the sender side encrypts transmission data using the public key of the receiver and transmits the encrypted data to the device on the receiver side, wherein: Let be the recipient's private key (p, q), and Is the public key (N, k, G, H) of the receiver, and (1) in the device on the sender side, a random number r∈ {0,1 for plaintext x (x∈ {0,1} ⁿ ). } ^k0 is selected, and using this random number r and the public key of the receiver, Then, using s, t and the recipient's public key, (Where a = (m / N) represents the Jacobi symbol), and as a result, y ₁ , y ₂ and y ₃ are transmitted as ciphertexts to the device of the recipient,
(2) In the device on the receiver side, using the secret key of the receiver, from the ciphertext y ₁ , y ₂ , y ₃ received from the device on the sender side, And φ (x _{1, p} , x _{1, q} ), φ (-x _{1, p} , x _{1, q} ),
Of φ (x _{1, p} , -x _{1, q} ), φ (-x ₁ ,, _p , -x _{1, q} ), where φ is Z / (p) × Z / (according to Chinese Remainder Theorem q) to Z / (pq), which satisfies (x / N) = y ₃ and 0 <x <2 ^k-2
As s', (Where x ′ ∈ {0,1} ⁿ , r ′ ∈ {0,1} ^k0 ) and using the result, A public key cryptographic communication method characterized by calculating the decryption result shown in (However, if the decryption result is "*", this ciphertext is rejected). 26. A public-key cryptographic communication method, wherein a device on the sender side encrypts transmission data using a public key of the receiver and transmits the encrypted data to the device on the receiver side. Let be the recipient's private key (p, q), and Is the public key (N, k, G, H) of the receiver, and (1) in the device on the sender side, a random number r∈ {0,1 for plaintext x (x∈ {0,1} ⁿ } ^k0 is selected, and using this random number r and the public key of the receiver, Then, using s, t and the public key of the recipient, And send y ₁ and y ₂ as ciphertexts to the device of the recipient, and (2) the device of the recipient uses the device of the sender using the secret key of the recipient. From the ciphertexts y ₁ and y ₂ received from And φ (x _{1, p} , x _{1, q} ), φ (-x _{1, p} , x _{1, q} ),
Of φ (x _{1, p} , -x _{1, q} ), φ (-x ₁ ,, _p , -x _{1, q} ), where φ is Z / (p) × Z / (according to Chinese Remainder Theorem (representing a ring isomorphism map from q) to Z / (pq)), and s '(s' may exist more than one) satisfying 0 <x <2 ^k-2 , (Where x ′ ∈ {0,1} ⁿ , r ′ ∈ {0,1} ^k0 ), and using the result, A public key cryptographic communication method characterized by calculating the decryption result shown in (However, if the decryption result is "*", this ciphertext is rejected). 27. The public key cryptographic communication method according to claim 25 or 26, wherein prime numbers p ', q'other than the prime numbers p, q constituting the secret key of the receiver are provided. A public key cryptographic communication method characterized by selecting a prime number represented by 2p '+ 1, 2q' + 1. 28. A public-key cryptographic communication method in which a device on the sender side encrypts transmission data using the public key of the receiver and transmits the encrypted data to the device on the receiver side. Be the recipient's private key p _i (1 ≦ i ≦ d), and Is the public key (N, k, G, H) of the receiver, and (1) in the device on the sender side, a random number r∈ {0,1 for plaintext x (x∈ {0,1} ⁿ } ^k0 is selected, and using this random number r and the public key of the receiver, (Where k−1 ≦ log ₂ (N + 1)), and using s, t and the recipient's public key, And transmit the results y ₁ and y ₂ as ciphertext to the device of the recipient, and (2) the device of the receiver uses the device of the sender using the secret key of the receiver. From the ciphertexts y ₁ and y ₂ received from And then 2 ^d φ (± x _{1, p1,,} ±
x _{1, p2,.} ． ． , ± x _{1, pd} ) (where φ is Z / (p ₁ ) × Z / (q ₂ ) × ... × Z / (q _d ) to Z / (N) according to the Chinese Remainder Theorem.
, Which represents a ring isomorphism map to, s'that satisfies 0 <s'<N / 2
As (s' may exist more than one), (Where x ′ ∈ {0,1} ⁿ and r ′ ∈ {0,1} ^k0 ), A public key cryptographic communication method characterized by calculating the decryption result shown in (However, if the decryption result is "*", this ciphertext is rejected). 29. The public key cryptographic communication method according to claim 28, wherein the prime number p _i constituting the secret key of the recipient is represented by 2p ′ + 1 with respect to another prime number p ′. A public key cryptographic communication method characterized in that a selected prime number is selected. 30. 25, 26, 27, 28 or 2
10. The public key cryptographic communication method according to 9, wherein the value of d (d ≧ 1) is variable. 31. 24, 25, 26, 27, 28,
31. The public key cryptographic communication method according to 29 or 30, wherein the device on the receiver side generates and publishes the public information. 32. A public key cryptographic communication method, wherein a device on the sender side encrypts a data encryption key using the public key of the receiver, and transmits the encrypted data encryption key to the device on the receiver side. Be the public key of the receiver, and Is used as a recipient's private key, and (1) in the device on the sender side, the transmission data m is encrypted using the data encryption key K (K ∈ {0,1} ⁿ ) to create a ciphertext C. At the same time, a random number rε {0,1} ^k0 is selected for the data encryption key K, and using this random number r and the public key of the receiver, Then, using s, t and the public key of the recipient, And send the results y ₁ and y ₂ together with the ciphertext C to the device of the recipient, and (2) the device of the receiver uses the secret key of the receiver to send the sender. From the cipher results y ₁ and y ₂ received from the device on the side, And calculate the result using (Where K ′ ∈ {0,1} ⁿ , r '∈ {0,1} ^k0 ) and using the result, Calculate the decryption result shown in (However, if the decryption result is "*", the encryption result is rejected), and further, using the calculation result K ', from the device on the sender side. A public key cryptographic communication method characterized by decrypting a received ciphertext C. 33. A public-key cryptographic communication method in which a device on the sender side encrypts a data encryption key using the public key of the receiver, and transmits the encrypted data encryption key to the device on the receiver side. Let be the recipient's private key (p, q), and Is the public key (N, k, G, H) of the receiver, and (1) in the device on the sender side, using the data encryption key K (K ∈ {0,1} ⁿ ), the transmission data m While encrypting to create the ciphertext C, a random number rε {0,1} ^k0 is selected for the data encryption key K, and using this random number r and the public key of the receiver, And the result s, t and the recipient's public key are used to calculate (Where a = (m / N) represents the Jacobi symbol), and as a result, y ₁ , y ₂ and y ₃ are transmitted to the device of the recipient together with the ciphertext C, and (2) the above In the device on the receiver side, using the secret key of the receiver, from the cipher results y ₁ , y ₂ , y ₃ received from the device on the sender side, And φ (x _{1, p} , x _{1, q} ), φ (-x _{1, p} , x _{1, q} ),
Of φ (x _{1, p} , -x _{1, q} ), φ (-x ₁ ,, _p , -x _{1, q} ), where φ is Z / (p) × Z / (according to Chinese Remainder Theorem q) to Z / (pq), which satisfies (x / N) = y ₃ and 0 <x <2 ^k-2
As s', (Where k ′ ∈ {0,1} ⁿ , r ′ ∈ {0,1} ^k0 ) and using the result, Calculate the decryption result shown in (However, if the decryption result is "*", the encryption result is rejected), and further, using the calculation result K ', from the device on the sender side. A public key cryptographic communication method characterized by decrypting a received ciphertext C. 34. A public-key cryptographic communication method in which a device on the sender side encrypts a data encryption key using the public key of the receiver and transmits the encrypted data encryption key to the device on the receiver side. Be the secret key (p, q) of the receiver, and Is the public key (N, k, G, H) of the receiver, and (1) in the device on the sender side, using the data encryption key K (K ∈ {0,1} ⁿ ), the transmission data m While encrypting to create the ciphertext C, a random number rε {0,1} ^k0 is selected for the data encryption key K, and using this random number r and the public key of the recipient, Then, using s, t and the public key of the recipient, And send the results y ₁ and y ₂ together with the ciphertext C to the device of the recipient, and (2) the device of the receiver uses the secret key of the receiver to send the sender. From the cipher results y ₁ and y ₂ received from the device on the side, And φ (x _{1, p} , x _{1, q} ), φ (-x _{1, p} , x _{1, q} ),
Of φ (x _{1, p} , -x _{1, q} ), φ (-x ₁ ,, _p , -x _{1, q} ), where φ is Z / (p) × Z / (according to Chinese Remainder Theorem (representing a ring isomorphism map from q) to Z / (pq)), and s '(s' may exist more than one) satisfying 0 <x <2 ^k-2 , (Where k ′ ∈ {0,1} ⁿ , r ′ ∈ {0,1} ^k0 ) and using the result, Calculate the decryption result shown in (However, if the decryption result is "*", the encryption result is rejected), and further, using the calculation result K ', from the device on the sender side. A public key cryptographic communication method characterized by decrypting a received ciphertext C. 35. The public key cryptographic communication method according to claim 33 or 34, wherein prime numbers p ', q'other than the prime numbers p, q constituting the secret key of the recipient are set. A public key cryptographic communication method characterized by selecting a prime number represented by 2p '+ 1, 2q' + 1. 36. A public-key cryptographic communication method in which a device on the sender side encrypts a data encryption key using the public key of the receiver, and transmits the encrypted data encryption key to the device on the receiver side. Be the recipient's private key p _i (1 ≦ i ≦ d), and Is the public key (N, k, G, H) of the receiver, and (1) in the device on the sender side, using the data encryption key K (K ∈ {0,1} ⁿ ), the transmission data m While encrypting to create the ciphertext C, a random number rε {0,1} ^k0 is selected for the data encryption key K, and using this random number r and the public key of the recipient, (Where k−1 ≦ log ₂ (N + 1)), and using the result s, t and the public key of the recipient, And send the results y ₁ and y ₂ together with the ciphertext C to the device of the recipient, and (2) the device of the receiver uses the secret key of the receiver to send the sender. From the cipher results y ₁ and y ₂ received from the device on the side, And then 2 ^d φ (± x _{1, p1,,} ±
x _{1, p2,.} ． ． , ± x _{1, pd} ) (where φ is Z / (p ₁ ) × Z / (q ₂ ) × ... × Z / (q _d ) to Z / (N) according to the Chinese Remainder Theorem.
, Which represents a ring isomorphism map to, s'that satisfies 0 <s'<N / 2
As (s ′ may exist more than once), (Where k ′ ∈ {0,1} ⁿ , r ′ ∈ {0,1} ^k0 ) and using the result, Calculate the decryption result shown in (However, if the decryption result is "*", the encryption result is rejected), and further, using the calculation result K ', from the device on the sender side. A public key cryptographic communication method characterized by decrypting a received ciphertext C. 37. The public key cryptographic communication method according to claim 36, wherein the prime number p _i constituting the secret key of the recipient is represented by 2p '+ 1 for another prime number p'. A public key cryptographic communication method characterized in that a selected prime number is selected. 38. A method according to claim 33, 34, 35, 36 or 3.
8. The public key cryptographic communication method according to 7, wherein the value of d (d ≧ 1) is variable. 39. 32, 33, 34, 35, 36,
39. The public key cryptographic communication method according to 37 or 38, wherein the device on the receiver side generates and publishes the public information. 40. A public-key cryptographic communication method in which a device on the sender side encrypts transmission data using the public key of the receiver, and transmits the encrypted data to the device on the receiver side. Be the public key of the receiver, and As a secret key of the receiver, (1) in the device on the sender side, a random number r∈ {0,1} ^k is selected for the plaintext x (x∈ {0,1} ⁿ ) and the random number r Using the recipient's public key, And transmit the results y ₁ and y ₂ as ciphertext to the device of the recipient, and (2) the device of the receiver uses the device of the sender using the secret key of the receiver. From the ciphertexts y ₁ and y ₂ received from Is calculated, and the result is used to calculate (Where x ′ ∈ {0,1} ⁿ and w ′ ∈ {0,1} ^k0 ), and using the result, A public key cryptographic communication method characterized by calculating the decryption result shown in (However, if the decryption result is "*", this ciphertext is rejected). 41. A public-key cryptographic communication method, wherein a device on the sender side encrypts transmission data using the public key of the receiver, and transmits the encrypted data to the device on the receiver side. Let be the recipient's secret key (p, q), and Is the public key (N, k, G, H) of the receiver, and (1) in the device on the sender side, a random number r∈ {0,1 for plaintext x (x∈ {0,1} ⁿ } ^k−2 is selected, and using this random number r and the public key of the receiver, (Where a = (m / N) represents the Jacobi symbol), and as a result, y ₁ , y ₂ and y ₃ are transmitted as ciphertexts to the device of the recipient,
(2) In the device on the receiver side, using the private key of the receiver, from the ciphertext y ₁ , y ₂ , y ₃ received from the device on the sender side, And φ (r _{1, p} , r _{1, q} ), φ (-r _{1, p} , r _{1, q} ),
Of φ (r _{1, p} , -r _{1, q} ), φ (-r _{1 , p} , -r _{1, q} ), where φ is Z / (p) × Z / (according to Chinese Remainder Theorem (representing a ring isomorphism map from (q) to Z / (pq)), (r / N) = y ₃ and 0 <r <2 ^k-2
As r ', (Where x ′ ∈ {0,1} ⁿ and w ′ ∈ {0,1} ^k0 ), and using the result, A public key cryptographic communication method characterized by calculating the decryption result shown in (However, if the decryption result is "*", this ciphertext is rejected). 42. A public-key cryptographic communication method in which a device on the sender side encrypts transmission data using the public key of the receiver, and transmits the encrypted data to the device on the receiver side. Let be the recipient's private key (p, q), and Is the public key (N, k, G, H) of the receiver, and (1) in the device on the sender side, a random number r∈ {0,1 for plaintext x (x∈ {0,1} ⁿ ). } ^k , and using this random number r and the public key of the recipient, And transmit the results y ₁ and y ₂ as ciphertext to the device of the recipient, and (2) the device of the receiver uses the device of the sender using the secret key of the receiver. From the ciphertexts y ₁ and y ₂ received from And φ (r _{1, p} , r _{1, q} ), φ (-r _{1, p} , r _{1, q} ),
Of φ (r _{1, p} , -r _{1, q} ), φ (-r _{1 , p} , -r _{1, q} ), where φ is Z / (p) × Z / (according to Chinese Remainder Theorem (representing a ring isomorphism map from q) to Z / (pq)), and r'that satisfies 0 <r <2 ^k-2 , (Where x ′ ∈ {0,1} ⁿ , w ′ ∈ {0,1} ^k0 ), and using the result, A public key cryptographic communication method characterized by calculating the decryption result shown in (However, if the decryption result is "*", this ciphertext is rejected). 43. The public key cryptographic communication method according to claim 8, 24 or 40, wherein: Let be the recipient's private key (p, q), and Is the recipient's public key (N, k), and (1) the sender's device uses the recipient's public key for plaintext x (x ∈ {0,1} ^k-2 ). , Numeral 155 (Where a = (m / N) represents a Jacobi symbol), and as a result, y ₁ and y ₂ are transmitted as ciphertexts to the device of the recipient,
(2) In the device on the receiver side, using the secret key of the receiver, from the ciphertexts y ₁ and y ₂ received from the device on the sender side, And φ (x _{1, p} , x _{1, q} ), φ (-x _{1, p} , x _{1, q} ),
Of φ (x _{1, p} , -x _{1, q} ), φ (-x ₁ ,, _p , -x _{1, q} ), where φ is Z / (p) × Z / (according to Chinese Remainder Theorem (representing a ring homomorphic map from q) to Z / (pq)), public key cryptography characterized by using a decryption result that satisfies (x / N) = y ₂ and 0 <x <2 ^k-2 Communication method. 44. The public key cryptographic communication method according to claim 43, wherein the plaintext, the process in the device on the sender side, and the process on the receiver side according to the conversion method for improving security. A public-key cryptographic communication method characterized in that a constraint condition based on a Jacobi symbol is deleted in processing by a device. 45. The public key cryptographic communication method according to claim 8, 24 or 40, wherein: Be the recipient's private key p _i (1 ≦ i ≦ d), and Is the recipient's public key (N, k), and (1) the sender's device uses the recipient's public key for plaintext x (x ∈ {0,1} ^k ). Number 159] And the result y ₁ is transmitted as a ciphertext to the device of the recipient, and (2) the device of the receiver receives it from the device of the sender using the private key of the receiver. From ciphertext y ₁ , Is calculated, and 2 ^d φ (± x _{1, p1} , ± x _{1, p2} , ...,
± x _{1, pd} ) (where φ is Z /
(p ₁ ) × Z / (q ₂ ) ×. ． ． X Z / (q _d ) represents a homomorphic mapping from Z / (N)), from 0 that satisfies 0 <x '<N / 2 to N greater than 0
A public key cryptographic communication method characterized by ensuring decryption uniqueness by using a constant smaller than / 2 as the decryption result from the ciphertext. 46. The public key cryptographic communication method according to claim 40, 41, 42, 43, 44 or 45, wherein the public information is generated and published in the device on the receiver side. Public key cryptographic communication method. 47. A program readable by an information processing device, wherein the program is transmitted to the information processing device in the public key encryption communication method according to any one of claims 1 to 46. A program characterized by causing the device to perform processing. 48. A program readable by an information processing device, wherein the program is provided to the information processing device in the public key encryption communication method according to any one of claims 1 to 46. A program characterized by causing the device to perform processing.