JP3694242B2 - Signed cryptographic communication method and apparatus - Google Patents

Description

[0001]
BACKGROUND OF THE INVENTION
The present invention relates to an encryption communication method and apparatus for confirming a sender's identity in a telecommunication system and simultaneously concealing transmission contents.
[0002]
[Prior art]
There is a method in which an arbitrary digital signature method and a public key encryption method are combined as a method in which a sender and a receiver communicate securely via a communication network that may be wiretapped, falsified, and impersonated.
Signing key of the sender U _S, and the signature verification key of x, respectively, and y, the encryption key of the receiver U _R, respectively the decoding key e, is as d. It is assumed that y and d are open to the public, and the sender U _S and the receiver U _R hold these.
[0003]
The plaintext to be transmitted is m, E is an encryption function, E _e (m) represents a ciphertext obtained by encrypting the message m with the encryption key e, D is a decryption function corresponding to the encryption function E, and D _d (c) represents a plaintext obtained by decrypting the ciphertext c with the decryption key d. That is, m = D _d (E _e (m)) holds. S is a signature function, S _x (m) represents a signature with a signature key x for message m, V is a verification authority, V _y (a, m) is a signature message pair (a, m) and signature verification key y Indicates the result verified by. The verification result is either 1 or 0, and V _y (a, m) = 1 when and only when a = S _x (m).
[0004]
When transmitting the plaintext m, the sender U _S first encrypts the plaintext m with the encryption key e to obtain a ciphertext C = E _e (m). Next, a signature a = S _x (C) for the ciphertext C is created using the signature key x. The transmission sentence Σ is Σ = (C, a), and the sender U _S transmits the transmission sentence Σ to the receiver U _R.
Recipients U _R receives the signed a ciphertext C, first, V _y (a, C) to verify that the 1 using a signature verification key y. If not 1, the received C and a are regarded as invalid data and discarded. If the verification result is 1, m = D _d (C) is calculated using the decryption key d to obtain plaintext m.
[0005]
A specific method will be described for the case where the Schnorr signature and the ElGamal encryption are used for the signature and the encryption method, respectively. p _s, and large prime number q _s, q _s is assumed that divides the (p _s -1). The g _s Z ^* _ps (Z _ps is an integer 1, 2, ..., a group of ps) and the original of the order q _s in. p _r , q _r , and g _r are defined in the same manner (the subscript ps represents p _s, and so on). Let H ₁ (·) and H ₂ (·) be one-way hash functions, respectively, and the binary operator A‖B represents a value obtained by combining A and B, p _s , q _s , g _s , p _r , q _r and g _r are public.
The sender U _S randomly selects the signature key x of the Schnorr signature from Z _qs (Z _qs is a group of integers 0, 1, 2,..., Qs−1), and sets the signature verification key y to y = g _s ^x This y is made public by calculating mod p _s . Recipients U _R chose a decryption key d of ElGamal encryption at random from Z _qr, publish e by calculating the encryption key ^{_{e = g r d mod p r}} .
[0006]
Ciphertext C by ElGamal encryption is C = (G, M) = (g r u mod p r, E s K (m)), Schnorr signature a is a = for this C (c, z) = ( H ₁ (g _s ^v ‖C), v-cx mod q _s ). Here, u and v are random numbers randomly selected from Z _qr and Z _qs , E ^s is an encryption function of a symmetric key encryption such as DES, and K is K = H ₂ (e ^w mod
p _r ).
The receiver confirms that c = H ₁ (g _s ^x y ^c mod p _s ‖C) holds, and then K = H ₂ (G ^d mod p _r ), m = D ^s _K (M) To obtain plaintext m. Here, D ^s is a decryption function of symmetric key cryptography corresponding to E ^s .
[0007]
According to the prior art, the nature of the digital _{signature, V y (a, C)} = 1 and becomes able to create a signature a is only senders U _S holding the signature key x that corresponds to the verification key y Therefore, the creator of the ciphertext C can be authenticated, and the creator of the ciphertext C cannot deny the fact of the signature. Furthermore, the can decrypt the ciphertext C is only recipient U _R, it is not the content of the message m is leaked to a third party (eavesdropper).
[0008]
[Problems to be solved by the invention]
In the following, the calculation times of the functions E, D, S, and V are expressed as τ (E), τ (D), τ (S), and τ (V), respectively, and the ciphertext length and the signature length are expressed as L (C), respectively. , L (a).
According to the above conventional method, the calculation time required for the sender to create the transmitted sentence (C, a) is τ (E) + τ (S), and the calculation time required for the receiver is also τ (V) + τ (D). The bit length of the transmitted text (C, a) is at least L (C) + L (a).
In order to estimate the calculation time, the calculation time of the power-residue operation with mod p _s whose exponent part is Z _qs is set to 1. It is assumed that p _s and p _r , and q _s and q _r have the same number of bits, respectively, and the calculation time of the modular exponentiation with mod p _r whose exponent part is Z _qr is also regarded as 1. The 2-base power residue calculation can be calculated with a calculation amount approximately 1.4 times that of the 1-base power residue calculation. The bit lengths of p _s and q _s are represented by | p | and | q |, respectively, and the bit length of the hash function H ₁ (•) value is represented by | q |. The length of the ciphertext obtained by encrypting the ciphertext m with symmetric key cryptography is represented by | m |. modular multiplication in mod q _r, hash function, and mod q _s, the computation time in the mod q _r, usually, since mod p very small compared to the calculation time of modular exponentiation in _s, the following It will be ignored in the estimation. It is also assumed that the message length is sufficiently short and that the time for encryption and decryption of symmetric key cryptography is negligible.
[0009]
According to the above conditions, the calculation time required by the sender to create the transmitted sentence Σ = (C, a) is 1 for calculating e ^w mod p _r and 1 for calculating g _r ^u mod p _r . 1, g _s ^v takes 1 to calculate, so τ (E) + τ (S) = 2 + 1 = 3. The length of the transmitted text is such that the length of E ^s _K (m) in the ciphertext C is | m |, the length of g _r ^u mod p _r is | p |, and H ₁ in the signature a (g _s ^v The length of 長 C) is | q | and the length of v = cx mod q _s is | q |, and therefore L (C) + L (a) = | m | + | p | +2 | q | . The calculation time required for the signature verification and decryption by the receiver is 1.4 for the calculation of g _s ^x y ^c mod p _s and 1 for the calculation of G ^d mod p _r , and thus τ (V) + τ (D) = 1.4 + 1 = 2.4.
[0010]
The present invention provides safety against tampering, impersonation, and eavesdropping in the same manner as the conventional method described above, while the calculation time of the sender and the receiver is τ (E) + τ (S), τ (V) + τ (D It is an object of the present invention to provide an authenticated encryption method that requires less data length than L (C) + L (a).
[0011]
[Means for Solving the Problems]
In the present invention, a common parameter is used as a part of the public key, that is, for example, p _r , q _r , g _r made on the receiver side and p _s , q _s , g _s made on the sender side, P, q, and g are common to the system, and a random number used in the encryption function and a random number used in the signature function are common random numbers.
In this way, by using the common parameter and the common random number, it is possible to share the power-residue operation using the random number required at the time of encryption and the power-residue operation necessary at the time of signature. That is, it is possible to share the part calculated from the random number included in the ciphertext in the transmission text and the part calculated from the random number included in the signature. Furthermore, a part of the decryption procedure and a part of the signature verification procedure can be shared.
[0012]
DETAILED DESCRIPTION OF THE INVENTION
As shown in FIG. 1, the plaintext m is encrypted at the sender terminal 11, a digital signature a for the ciphertext C is created, (C, a) is sent to the receiver terminal 13 via the public line 12, An embodiment in which the present invention is applied to the case where the receiver terminal 13 verifies the signature of the received signal and decrypts the ciphertext C when it is passed will be described below.
Embodiment 1
Let E ^s be a secret key encryption function, and E ^s _K (m) represents a ciphertext that is obtained by encrypting plaintext m with the key K. Similarly, D _s is a secret key decryption function corresponding to E _s , and D ^s _K (C) represents a plaintext obtained by decrypting the ciphertext C with the key K. For example, for the functions E and D, an encryption function and a decryption function in the CBC mode and OFB mode of block cipher such as Triple-DES and IDEA may be used.
[0013]
Let p and q be large prime numbers, and q divide (p-1) . Let g be an element of order q in Z ^* _p . Let H ₁ (•) and H ₂ (•) be one-way hash functions, and the binary operator A‖B represents a value obtained by combining A and B. The p, q, g, and hash functions that constitute part of the public key are disclosed as system common parameters. For example, SHA-1 may be used as the hash function.
The stored sender randomly selects the signature key x from Z _q, and FIG. 2 shows a functional configuration example of the sender terminal 11. The memory 20 generates parameters p, q, g and the encryption key e, that is, the signature key x by the random number generator 21 of the sender terminal 11, stores the signature key x in the memory 20, and the signature verification key generator 22, y = g ^x mod q is calculated using x, q, and p to generate a signature verification key y, which is stored in the memory 20 and released.
[0014]
A functional configuration of the receiver terminal 13 is shown in FIG. The memory 40 stores parameters p, q, g, and a signature verification key y. The receiver randomly selects the decryption key d from Z _q , that is, generates the decryption key d from the random number generator 41, stores the decryption key d in the memory, and uses the g, d, and p to generate the encryption key generation unit 42. Then, e = gd mod p is calculated to generate the encryption key e, and the encryption key e is stored in the memory 40 and released.
When transmitting the plain text m, the sender terminal 11 creates a transmission text Σ by the following procedure. First, the random number w is randomly selected from Z _q , that is, the random number w is generated from the random number generator 23, and the random number w, the encryption key e, and the parameter p are input to the exponentiation remainder calculator 24 to calculate e ^w mod p Then, the calculation result is input to the hash unit 25 to calculate K = H ₁ (e ^w mod p) to obtain the session key K. The session key K and the message m are input to the encryption unit 26 to obtain m. The ciphertext C is obtained by encrypting with the key K by the encryption function Es, that is, calculating C = E ^s _K (m).
[0015]
Next, a random number w and parameters g and p are input to the power residue calculator 27 to calculate W = g ^w mod p, and the calculation result W and the ciphertext C from the encryptor 26 are input to the hash unit 28. Then, the hash value b = H ₂ (W‖C) of the concatenation of W and C is calculated, and b, q, the random number w, and the signature key x are input to the remainder multiplier / subtractor 29 and a = w− bx mod q is calculated to obtain signatures a and b. The transmitter 30 transmits the ciphertext C and the signatures a and b to the receiver terminal 13 as a transmission text Σ = (C, a, b).
In addition, control of each part of the transmission terminal 11 is performed by the control part 31, and each part is processed sequentially or in parallel. The random number generators 21 and 23 can be shared by one, and the exponentiation remainder calculators 24 and 27 can also be shared by one. The power-residue calculator 24, the hash unit 25, and the encryptor 26 constitute a ciphertext generation unit 70 that generates the ciphertext C, and the power-residue calculator 27, the hash unit 18, and the remainder multiplier / subtractor 29 generate a signature. The signature unit 90 is configured.
[0016]
The receiver terminal 13 verifies and decrypts the ciphertext received by the receiver 43 by the following means. First, the received signatures a and b, p and g from the memory 40, and the signature verification key y are input to the power residue calculator 44 to calculate W ′ = g ^a y ^b mod p, and the calculation result W ′ The received ciphertext C is input to the hash unit 45, a hash value H ₂ (W′‖C) of the combination of C and W ′ is calculated, and this calculation result is compared with the received b by the comparator 46. The signature is verified. That is, since a = w−bx mod p and y = g ^x mod p, if these are substituted into the formula of W ′, W ′ = g ^w mod p and H ₂ (W′‖C) is equal to b. The signature on the ciphertext C is correct. If this verification does not hold, the received sentence Σ is discarded. If this signature verification holds, a, b and g, p, y, d are input to the power residue calculator 47 to calculate (g ^a y ^b modp) ^d , or the output W of the power residue calculator 44 'And d are input to calculate (W') ^d mod p, and the calculation result is input to the hash unit 48 to calculate K = H ₁ ((g ^a y ^b mod p) ^d and the session key K Is decrypted with the key K, and a decryption function operation m = D ^s _K (C) is performed by the decryptor 49 to obtain a plaintext m.
[0017]
Each unit of the receiver terminal 13 is controlled by the control unit 50 so as to process sequentially or in parallel. The power residue calculator 47 may input the calculation result W ′ of the power residue calculator 44 and calculate (W ′) ^d .
In this embodiment, when the calculation time is evaluated under the same conditions as the calculation time estimation described above, the sender terminal 11 calculates 1 for e ^w mod p and 1 for g ^w mod p, that is, τ (E). + Τ (S) = 1 + 1 = 2, the time calculation for one power-residue operation is less than before, and the length of the transmitted sentence is E ^s _K (m) is | m |, b = H ₂ (W The length of 長 C) is | q | and the length of a = w-bx mod q is | q |, that is, L (C) + L (a) = | m | +2 | q | The receiver terminal 13 shortens the calculation time by 1.4 for the calculation of g ^a y ^b mod p, 1 for the calculation of (W ′) ^d mod p, that is, τ (V) + τ (D) = 1. 4 + 1 = 2.4, which is the same as before.
[0018]
That is, since the parameters p, q, g are common to the sender terminal 11 and the receiver terminal 13 and the random number w is commonly used for the cryptographic function and the signature function, the conventional ciphertext C = (G, signed G = g _r ^u mod p _r in M) a = (C, Z ) in the C = H ₁ (g _s ^v in mod p _s ‖C) computing g _s ^v mod p _s and the same It becomes calculation g ^w mod p, and it is possible to share the power-residue operation with a random number required at the time of encryption and the power-residue operation required at the time of signature, so that the calculation time is reduced and the ciphertext in the transmitted text The part G calculated from the random number and the part calculated from the random number included in the signature, W = g ^w mod p in b = H ₂ (W‖C), are shared, and G is transmitted. There is no need. That 'the calculation of ^{= g a y b mod p,} W' receiver in the terminal 13 at the time of the verification W = g ^v mod p is obtained by calculating the b = H ₂ (W'‖C), conventional A technology corresponding to G required for decoding in the technology is obtained, and reception of G is not required.
Embodiment 2
When transmitting the plain text m, the sender terminal 11 may create the transmission text Σ by the following means. The ciphertext C is created in the same manner as the above means, and then b = H ₂ (K‖C) is calculated by inputting the output K of the hash unit 25 instead of W as shown by the wavy line in FIG. Using this b, the remainder multiplier / subtractor 29 calculates a = w-bx mod q to obtain signatures a and b. The transmitted sentence Σ is Σ = (C, a, b).
[0019]
The receiver terminal 13 verifies and decrypts the ciphertext received by the following means. First, K = H ₁ ((g ^a y ^b ) ^d mod p) is calculated by the power-residue calculating unit 47 and the hash unit 48, and K is substituted for W in the hash unit 45 as indicated by a broken line in FIG. Then, H ₂ (K‖C) is input and calculated, and it is verified by the comparator 46 that b = H ₂ (K‖C) holds. If not, the received sentence Σ is discarded. If yes, then m = D ^s _K (C) is calculated to obtain plaintext m.
Also in the second embodiment, for the same reason as in the first embodiment, the calculation time at the sender terminal 11 can be set to 2, the transmission sentence length can be set to | m | +2 | q |, and the receiver terminal 13 The calculation time in is only 1.4 of the calculation of K.
[0020]
As can be easily understood from the change of the embodiment to the first embodiment, the inputs to the hash unit 28 may be W, C, and K, and H ₂ (W （C‖K) = b, or W, C, and enter the _{m, H 2 (W‖C‖m) =} b may be, or C, m may enter H ₂ (C‖m) = b a. When m is used as an input to the hash unit 28, the receiver terminal 13 obtains K at the time of verification, further decrypts m with K, and uses that m. In short, the hash device 28 of the sender terminal 11 inputs at least one of W, K, and m and C, calculates the combination of the inputs by H ₂ (·), and outputs b. In the hashing device 45, the input corresponding to the input of the hashing device 28 of the sender terminal is input, and the combination thereof is calculated by H ₂ (·).
Embodiment 3
When the plaintext m is transmitted, the sender terminal 11 may make it redundant by the following means. As shown in FIG. 4, in the sender terminal 11, first, the message converter 60 converts the input plaintext m into a message m ′ that is given redundancy. For example, as shown in FIG. 5, the plaintext m is subjected to hash function calculation H ₄ (m) by the hash unit 61, and the calculation result is further calculated by the hash unit 62 as hash function calculation H ₅ (H ₄ (m)). ) Is performed. An exclusive OR operation H ₅ (H ₄ (m)) (+) m for each bit of this operation result and the input plaintext m is performed by the exclusive OR operator 63, and this operation result and the hash unit 61 The combination with the calculation result H ₄ (m) is combined by the combiner 64 and output as m ′ = m (+) H ₅ (H ₄ (m)) ‖H ₄ (m).
[0021]
The message m ′ thus converted is encrypted by the ciphertext generation unit 70 in FIG. 4 by the same method as the ciphertext C in the first embodiment, for example, and the ciphertext C is generated. The ciphertext C is subjected to a hash function operation H ₂ (C) = b by the hash unit 71, and a remainder multiplication is performed using the calculation result b, x, q, a from the memory 20, and w from the random number generator 23. In the subtractor 29, a = w−bx mod q is calculated, a “a” of the signature is generated, and a transmission sentence Σ = (C, a) is transmitted from the transmitter 30.
In the receiver terminal 13, as shown in FIG. 6, C in C and a received by the receiver 43 is subjected to hash function calculation b = H ₂ (C) by the hash unit 81, and the calculation result b and reception are performed. Then, (g ^a y ^b ) ^d mod p is calculated by the exponentiation remainder calculator 47 based on a and d, y, p, g from the memory 40, and the hash function H ₁ ( -) Is performed, and the key K is obtained. A decryption function operation m ′ = D ^s _K (C) is performed by the decryptor 49 on the ciphertext C received by this key K.
[0022]
The decrypted message m ′ is divided into m ′ = A‖B by the bit divider 82 so that B becomes the same as the number of bits of the operation result of the hash function H ₄ (•). A hash function operation H ₅ (B) is performed on the B by the hash unit 83, and an exclusive OR operation m = H ₅ (B) (+) A for each bit of the operation result and A is performed by the calculator 84. Done. The operation result m and B are compared by the comparator 86. If they are equal, the operation result m is output as a correct decrypted plaintext, and if it is not equal, the received text (C, a) is invalid.
In the third embodiment, similarly to the second embodiment, each calculation time of the sender terminal 11 and the receiver terminal 13 can be reduced, and the length of the transmitted sentence can be reduced.
[0023]
In the above description, each of the sender terminal 11 and the receiver terminal 13 can be caused to function by causing a computer to execute a program.
The present invention is not limited to the first to third embodiments, and can be applied to encryption using a public key and signature of the ciphertext, parameters common to a part of the public key, and a random number used for encryption. What is necessary is just to make the random number used for a signature common.
[0024]
【The invention's effect】
As described above, according to the present invention, the calculation time at the sender terminal and the number of bits of the transmitted text can be reduced, and according to the embodiment, the calculation time at the receiver terminal can also be reduced.
[Brief description of the drawings]
FIG. 1 is a diagram showing a system configuration example to which the present invention is applied.
FIG. 2 is a diagram showing a functional configuration example of a sender terminal according to the present invention.
FIG. 3 is a diagram showing a functional configuration example of a recipient terminal according to the present invention.
FIG. 4 is a diagram showing another functional configuration example of the sender terminal of the present invention.
FIG. 5 is a diagram showing a functional configuration example of a message converter 60 in FIG. 4;
FIG. 6 is a diagram showing another functional configuration example of the receiver terminal of the present invention.

Claims (12)

Let p, q be a large prime number where q divides (p-1), g be an element of the order q in Z ^* _p , and these p, q, g be common to some parameters of both public keys. H ₁ (•) and H ₂ (•) are one-way hash functions, the binary operator A‖B represents the combined value of A and B, and E ^s is the private key E ^s _K (m) represents a ciphertext that can be obtained by encrypting plaintext m with a key K, D ^s is a secret key decryption function corresponding to E ^s , and D ^s _K (C) is a key K It represents the plaintext obtained by decrypting the ciphertext C,
Transmitter terminal generates a random signature key x belonging to Z _q, calculates the y = g ^x mod p, and published as the signature verification key y,
Receiver terminal generates a random decrypt key d belonging to Z _q, it calculates the e = g ^d mod p, published as an encryption key e,
At the time of transmission, the sender terminal generates a random number w belonging to _{Z q, K = H 1 (} e w mod p) to calculate generates a session key K, C = E ^s using K to message m Operate _K (m) to generate ciphertext C, and calculate signatures a and b by calculating W = g ^w mod p, b = H ₂ (WbC), and a = w−bx mod q , Send the transmission sentence Σ = (C, a, b) to the receiver terminal,
The receiver terminal that has received Σ = (C, a, b) first calculates W ′ = g ^a y ^b mod p, and verifies that b = H ₂ (W′‖C) holds. If not, the received sentence Σ is discarded. If true, K = H ₁ ((W ') ^d mod p) is calculated, and m = D ^s _K (C) is calculated to obtain the plain text m. A signed cryptographic communication method. Let p, q be a large prime number where q divides (p−1), g be an element of the order q in Z ^* _p , and these p, q, g are common to some parameters of both public keys. H ₁ (•) and H ₂ (•) are one-way hash functions, the binary operator A‖B represents the combined value of A and B, and E ^s is the private key E ^s _K (m) represents a ciphertext that can be obtained by encrypting plaintext m with a key K, D ^s is a secret key decryption function corresponding to E ^s , and D ^s _K (C) is a key K It represents the plaintext obtained by decrypting the ciphertext C,
Transmitter terminal generates a random signature key x belonging to Z _q, calculates the y = g ^x mod p, and published as the signature verification key y,
The receiver terminal is Z _q Randomly generate a decryption key d belonging to, calculate e = g ^d mod p and publish it as the encryption key e,
At the time of transmission, the sender terminal generates a random number w belonging to _{Zq, K = H 1 (e} w mod p) to calculate generates a session key K, the message m using a K to C = E ^s _K (m) is calculated to generate a ciphertext C, and b = H ₂ (K‖C), b = H ₂ (W‖C‖K) (W is g ^w mod p) and a = w− bx mod q is calculated to generate the signatures a and b, and the transmission sentence Σ = (C, a, b) is transmitted to the receiver terminal.
Σ = (C, a, b ) receiver terminal which receives ^{the, W = g a y b mod} p, and calculates the ^{_{K = H 1 (W d mod}} p), b = H 2 (K‖C), Verify that b = H ₂ (W‖C‖K) corresponds to the calculation of b at the sender terminal, and if not, discard received sentence Σ, and if m = D A signed cryptographic communication method characterized by calculating ^s _K (C) to obtain plaintext m. Let p, q be a large prime number where q divides (p−1), g be an element of the order q in Z ^* _p , and these p, q, g are common to some parameters of both public keys. H ₁ (•) and H ₂ (•) are one-way hash functions, the binary operator A‖B represents the combined value of A and B, and E ^s is the private key E ^s _K (m) represents a ciphertext that can be obtained by encrypting plaintext m with a key K, D ^s is a secret key decryption function corresponding to E ^s , and D ^s _K (C) is a key K It represents the plaintext obtained by decrypting the ciphertext C,
Transmitter terminal generates a random signature key x belonging to Z _q, calculates the y = g ^x mod p, and published as the signature verification key y,
The receiver terminal is Z _q The decrypt key d belonging to the randomly generated, to calculate the e = g ^d mod p, published as an encryption key e,
At the time of transmission, the sender terminal generates a random number w belonging to _{Zq, K = H 1 (e} w mod p) to calculate generates a session key K, the message m using a K to C = E ^s _K (m) is calculated to generate a ciphertext C, and b = H ₂ (W‖C‖m), (W is g ^w mod p), b = H ₂ (C‖m) and a = w -bx mod q is calculated, signatures a and b are generated, a transmission sentence Σ = (C, a, b) is transmitted to the receiver terminal,
Σ = (C, a, b ) receiver terminal which receives ^{the, W = g a y b mod} p, and calculates the ^{_{K = H 1 (W d mod}} p), calculates the m = D _K ^s (C) If b = H ₂ (W‖C‖m) and b = H ₂ (C‖m) correspond to the calculation of b at the sender terminal, it is verified. A signed cryptographic communication method characterized by discarding Σ and if m holds true, m is a correct plaintext. Let p, q be a large prime number where q divides (p−1), g be an element of the order q in Z ^* _p , and these p, q, g be common to some parameters of the public key. H ₁ (•) and H ₂ (•) are one-way hash functions, the binary operator A‖B represents the combined value of A and B, and E ^s is a secret key encryption E ^s _K (m) represents a ciphertext obtained by encrypting plaintext m with key K, D ^s is a secret key decryption function corresponding to E ^s , and D ^s _K (C) is encrypted with key K It represents a plaintext obtained by decrypting sentence C,
Transmitter terminal generates a random signature key x belonging to Z _q, calculates the y = g ^x mod p, and published as the signature verification key y,
The receiver terminal is Z _q The decrypt key d belonging to the randomly generated, to calculate the e = g ^d mod p, published as an encryption key e,
At the time of transmission, the sender terminal converts the message m to m ′ = m (+) H ₅ (H ₄ (m)) ‖H ₄ (using the hash functions H ₄ and H ₅ and the bitwise exclusive OR (+). m), a random number w belonging to Zq is generated , K = H ₁ (e ^w mod p) is calculated to generate a session key K, and C is used for the converted message m ′ using K. = E ^s _K (m ′) is calculated to generate a ciphertext C, b = H ₂ (C), a = w−bx mod q is calculated to generate a signature a, and a transmitted text Σ = (C , A) to the recipient terminal,
The receiver terminal that has received Σ = (C, a) calculates b = H ₂ (C), K = H ₁ ((g ^a y ^b ) ^d mod p), and uses this K to m ′ = calculate the D ^s _K (C) dividing 'a m' plaintext m = A‖B as B is H ₄ to m to be the same as the number of output bits of the (-) 'to a and B, H ₄ Whether (H ₅ (B) (+) A) = B holds is verified, and if not, the received sentence Σ is regarded as invalid, and if it does, the received sentence is regarded as correct. Signed cryptographic communication method. p and q are large prime numbers where q divides (p−1), g is an element of the order q in Z ^* _p , and H ₁ (•) and H ₂ (•) are one-way hash functions, The binary operator A‖B represents a value obtained by combining A and B, E ^s is a secret key encryption function, E ^s _K (m) is a ciphertext obtained by encrypting plaintext m with the key K, When d is a decryption key randomly selected from Z _q , the public encryption key is e = g ^d mod p, x is a signature key randomly selected from Z _q ,
a memory storing p, q, g, x, e;
A random number generator that generates and outputs a random number w belonging to Z _q ;
a first power residue calculator that receives w, e, and p, calculates e ^w mod p, and outputs the result;
a first ^{hasher that} receives the calculation result of e ^w mod p, calculates K = H ₁ (e ^w mod p), and generates and outputs a session key K;
An encryptor that receives a message m and a session key K, calculates C = E ^s _K (m), and generates and outputs a ciphertext C;
a second power residue calculator that receives w, g, and p, calculates W = g ^w mod p, and outputs the result;
A _second hasher that receives C and W, calculates b = H ₂ (W‖C), and outputs b;
a remainder multiplier / subtractor that receives b and x, q, w, calculates a = w-bx mod q, and outputs a;
A transmitter for transmitting the ciphertext C and the signatures a and b to the recipient terminal as transmission text (C, a, b);
A sender terminal comprising: p and q are large prime numbers where q divides (p−1), g is an element of the order q in Z ^* _p , and H ₁ (•) and H ₂ (•) are one-way hash functions, The binary operator A‖B represents a value obtained by combining A and B, E ^s is a secret key encryption function, E ^s _K (m) is a ciphertext obtained by encrypting plaintext m with the key K, When d is a decryption key randomly selected from Z _q , the public encryption key is e = g ^d mod p, x is a signature key randomly selected from Z _q ,
a memory storing p, q, g, x, e;
A random number generator that generates and outputs a random number w belonging to Z _q ;
a first power residue calculator that receives w, e, and p, calculates e ^w mod p, and outputs the result;
a first ^{hasher that} receives the calculation result of e ^w mod p, calculates K = H ₁ (e ^w mod p), and generates and outputs a session key K;
An encryptor that receives a message m and a session key K, calculates C = E ^s _K (m), and generates and outputs a ciphertext C;
a second power residue calculator that receives w, g, and p, calculates W ′ = g ^w mod p, and outputs the result;
A _second hasher that receives C and K, calculates b = H ₂ (K‖C), and outputs b;
a remainder multiplier / subtractor that receives b and x, q, w, calculates a = w-bx mod q, and outputs a;
A transmitter for transmitting the ciphertext C and the signatures a and b to the recipient terminal as transmission text (C, a, b);
A sender terminal comprising: Let p and q be large prime numbers where q divides (p−1), g be an element of the order q in Z ^* _p , and H ₁ (•), H ₂ (•), H ₄ (•), H ₅ (·) is a one-way hash function, binary operator A‖B represents a value obtained by combining A and B, E ^s is a secret key encryption function, and E ^s _K (m) is a key K in the ciphertext can encrypt the plaintext m, when a decryption key chosen randomly d from Z _q, the public encryption key and e = g ^d mod p, randomly chosen x from Z _q As a signing key,
a memory storing p, q, g, x, e;
A message converter that receives a message m, calculates m ′ = m (+) H ₅ (H ₄ (m)) ‖H ₄ (m), and outputs m ′;
A random number generator that generates and outputs a random number w belonging to Z _q ;
a first power residue calculator that receives w, e, and p, calculates e ^w mod p, and outputs the result;
a first ^{hasher that} receives the calculation result of e ^w mod p, calculates K = H ₁ (e ^w mod p), and generates and outputs a session key K;
An encryptor that receives a message m and a session key K, calculates C = E ^s _K (m), and generates and outputs a ciphertext C;
A second hasher that receives C, calculates b = H ₂ (C), and outputs b;
a remainder multiplier / subtractor that receives b and x, q, w, calculates a = w-bx mod q, and outputs a;
A transmitter that transmits the ciphertext C and the signature a as a transmission text (C, a) to the recipient terminal;
A sender terminal comprising: p and q are large prime numbers where q divides (p−1), g is an element of the order q in Z ^* _p , and H ₁ (•) and H ₂ (•) are one-way hash functions, The binary operator A‖B represents a value obtained by combining A and B, D ^s is a secret key decryption function, and D ^s _K (C) is a plaintext obtained by decrypting the ciphertext C with the key K. represents the decryption key d is assumed to have been selected at random from Z _q, the signature verification key y for signing key x belonging to Z _q and g ^x mod p,
a memory storing p, q, g, d, and y;
A receiver that outputs a received sentence (C, a, b) from a received signal from a sender terminal;
Received a, b and g from the memory, p, y is inputted, and ^{W '= g a y b mod} p the calculated W' first modular exponentiation operation for outputting a,
A hasher that receives W ′ and the received C, calculates H ₂ (W′‖C), and outputs the result;
A comparator that receives the calculation result of H ₂ (W′‖C) and the received b, and outputs a signature verification result according to whether or not they match;
A second power residue calculator that receives W ′, calculates (W ′) ^d mod p, and outputs the result;
A second hash calculator that receives the calculation result of the second power residue calculator, calculates K = H ₁ ((W ′) ^d mod p), and outputs the key K;
A decoder that receives K and received C, calculates m = D ^s _K (C), and outputs the calculation result as decrypted plaintext m;
A recipient terminal. p and q are large prime numbers where q divides (p−1), g is an element of the order q in Z ^* _p , and H ₁ (•) and H ₂ (•) are one-way hash functions, The binary operator A‖B represents a value obtained by combining A and B, D ^s is a secret key decryption function, and D ^s _K (C) is a plaintext obtained by decrypting the ciphertext C with the key K. represents the decryption key d is assumed to have been selected at random from Z _q, the signature verification key y for signing key x belonging to Z _q and g ^x mod p,
a memory storing p, q, g, d, and y;
A receiver that outputs a received sentence (C, a, b) from a received signal from a sender terminal;
A first power-residue computing unit that receives the received a, b and g, p, y, d from the memory, calculates W ′ = (g ^a y ^b ) ^d mod p, and outputs the result W ′; ,
A first hasher that receives W ′, calculates K = H ₁ (W ′), and outputs a key K;
A _second hasher that receives K and the received C, calculates H ₂ (K‖C), and outputs the result;
A comparator that receives the calculation result of H ₂ (K‖C) and the received b, and outputs a signature verification result according to whether or not they match;
A decoder that receives K and received C, calculates m = D ^s _K (C), and outputs the calculation result as decrypted plaintext m;
A recipient terminal. Let p and q be large prime numbers where q divides (p−1), g be an element of the order q in Z ^* _p , and H ₁ (•), H ₂ (•), H ₄ (•), H ₅ (·) is a one-way hash function, the binary operator A‖B represents a value obtained by combining A and B, D ^s is a secret key decryption function, and D ^s _K (C) is a key K in represents the plaintext obtained by decoding the ciphertext C, the decryption key d is assumed to have been selected at random from Z _q, the signature verification key y for signing key x belonging to Z _q and g ^x mod p,
a memory storing p, q, g, d, and y;
A receiver that outputs a received sentence (C, a) from a received signal from a sender terminal;
A first hasher that receives the received C, calculates b = H ₂ (C), and outputs b;
A first power-residue computing unit that receives b, the received a, and g, p, y, d from the memory, calculates W ′ = (g ^a y ^b ) ^d mod p, and outputs W ′;
A second hasher that receives W ′, calculates K = H ₁ (W ′), and outputs K;
A decoder that receives K and the received C, calculates m = D ^s _K (C), and outputs plaintext m ′;
A divider that divides m ′ into A and B so that m ′ is input, m ′ = A‖B, and B has the same number of bits as the number of output bits of H ₄ (•);
A and B are input, H ₄ (H ₅ (B) (+) A) (N (+) M represents an exclusive OR operation for each bit of N and M) is calculated, and the result is output And an arithmetic unit that outputs the operation result m = H ₅ (B) (+) A as a decoded message,
A comparator that inputs the calculation results H ₄ (H ₅ (B) (+) A) and B of the calculator and outputs a signature verification result according to whether or not they match;
A recipient terminal. p and q are large prime numbers where q divides (p−1), g is an element of the order q in Z ^* _p , and H ₁ (•) and H ₂ (•) are one-way hash functions, The binary operator A‖B represents a value obtained by combining A and B, E ^s is a secret key encryption function, E ^s _K (m) is a ciphertext obtained by encrypting plaintext m with the key K, When d is a decryption key randomly selected from Z _q , the public encryption key is e = g ^d mod p, x is a signature key randomly selected from Z _q ,
a memory storing p, q, g, x, e;
A random number generator that generates and outputs a random number w belonging to Z _q ;
a first power residue calculator that receives w, e, and p, calculates e ^w mod p, and outputs the result;
a first ^{hasher that} receives the calculation result of e ^w mod p, calculates K = H ₁ (e ^w mod p), and generates and outputs a session key K;
An encryptor that receives a message m and a session key K, calculates C = E ^s _K (m), and generates and outputs a ciphertext C;
a second power residue calculator that receives w, g, and p, calculates W ′ = g ^w mod p, and outputs the result;
A second hasher that receives C and X (X is one of W‖K, W‖m, and m), calculates b = H ₂ (X‖C), and outputs b;
a remainder multiplier / subtractor that receives b and x, q, w, calculates a = w-bx mod q, and outputs a;
A transmitter for transmitting the ciphertext C and the signatures a and b to the recipient terminal as transmission text (C, a, b);
A sender terminal comprising: p and q are large prime numbers where q divides (p−1), g is an element of the order q in Z ^* _p , and H ₁ (•) and H ₂ (•) are one-way hash functions, The binary operator A‖B represents a value obtained by combining A and B, D ^s is a secret key decryption function, and D ^s _K (C) is a plaintext obtained by decrypting the ciphertext C with the key K. represents the decryption key d is assumed to have been selected at random from Z _q, the signature verification key y for signing key x belonging to Z _q and g ^x mod p,
a memory storing p, q, g, d, and y;
A receiver that outputs a received sentence (C, a, b) from a received signal from a sender terminal;
Received a, b and g from the memory, p, y is inputted, and ^{W '= g a y b mod} p the calculated W' first modular exponentiation operation for outputting a,
A second power residue calculator that receives W ′, calculates (W ′) ^d mod p, and outputs the result;
A second hash calculator that receives the calculation result of the second power residue calculator, calculates K = H ₁ ((W ′) ^d mod p), and outputs the key K;
A decoder that receives K and received C, calculates m = D ^s _K (C), and outputs the calculation result as decrypted plaintext m;
A hashing unit for inputting X (X is one of W′‖K, W′‖m‖, m) and the received C, calculating H ₂ (X‖C), and outputting the result;
A comparator that receives the calculation result of H ₂ (X‖C) and the received b, and outputs a signature verification result according to whether or not they match;
A recipient terminal.

Images