JP6723958B2 - Encrypted data generation device, decrypted data generation device, authentication encryption system with additional data, method thereof, and program - Google Patents

Description

The present invention relates to an authentication encryption technique with additional data that simultaneously conceals a message and detects tampering.

The authentication cipher with additional data is a common key cryptographic primitive for simultaneously concealing the message M and authenticating the message M and the additional data A (alteration detection). Examples of conventional authentication encryption with additional data include APE (Authenticated Permutation-Based Encryption) described in Non-Patent Document 1 and Non-Patent Document 2. The authentication cipher with additional data is composed of two functions, an encryption function and a decryption function. In the authentication encryption with additional data, the secret key K is shared in advance between the receiver and the sender.

In addition to the message M and the additional data A, the sender selects a value N called a nonce that changes each time the encryption function is called. The encryption function generates the encrypted data C and the tag T corresponding to the message M, the additional data A, and the nonce N, and sends the set (C,T,A,N) to the recipient.

The recipient receives the (C,T,A,N) pair, but at this point there is no guarantee that these values have not been tampered with by a malicious third party. The receiver uses the received (C, T, A, N) pair and the key K held by the receiver to calculate a decryption function for performing verification at the same time.

There are several types of decryption functions that perform verification at the same time. In many authentication ciphers with additional data, verification is performed by checking whether the tag T'recalculated by the receiver matches the tag T received from the sender. The APE verifies whether the value of the intermediate state recalculated by the receiver matches a certain value. In any case, when the values do not match, the result that the decryption has failed (data has been tampered with) is output.

APE is a method of constructing encryption and decryption functions for authentication encryption with additional data. The feature is that the encryption function and the decryption function are configured by using a permutation (bijective map) of a relatively large size compared to the security level (number of bits) to be guaranteed. As described above, the APE decryption function is verified by a special method different from the conventional decryption function.

A specific calculation procedure of the APE encryption function will be described with reference to FIG. The APE encryption function replaces b-bit data called state with b-bit replacement f:{0,1} ^b →{0,1} ^b , input data (N,A,M), and key K. The encrypted data C and the tag T are calculated while iteratively updating using. The details of the substitution f are described in Non-Patent Document 2. Note that the nonce N is not required to be input, and even when the nonce N is present, the nonce N becomes a part of the additional data A. Therefore, it is sufficient for the input data to consider the additional data A, the message M, and the key K. Also, the additional data A is processed before the message M. Such additional data A is called a header. The length of both the additional data A and the message M is limited to the double length of r bits.

The b-bit state is divided into r bits called rate and c (=b-r) bits called capacity. When calculating the encryption function, the value of the b-bit state is initialized to 0 for the r bits of the rate part (that is, a bit string in which all bits are 0) and the c bit of the capacity part to the value of the key K. To do.

Step 1. The additional data A is divided into blocks of r bits. An exclusive OR with the first block of the additional data A is calculated for the r bits in the rate portion of the b-bit state, and the permutation f is calculated for the b-bit state. The output of this replacement f is taken as the value of the new state. This operation is repeated until the final block of the additional data A is exclusive ORed.

Step 2. For the c bits in the capacity portion of the b bit state, the exclusive OR is calculated with the integer value 1 (that is, the bit string in which only the least significant bit is 1).

Step 3. Divide message M into blocks of r bits. An exclusive OR with the first block of the message M is calculated for the r bits in the rate portion of the b-bit state, and the permutation f is calculated for the b-bit state. The output of this replacement f is used as a new state value, and the r bits of the rate portion are output as the first block of the encrypted data C. This operation is repeated until the final block of the message M is exclusive ORed.

Step 4. An exclusive OR of the c bits in the capacity portion of the b bit state with the c bit key K is calculated, and the calculation result is output as a c bit tag T.
A specific calculation procedure of the APE decoding function will be described with reference to FIG. The APE decryption function performs the calculation of the APE encryption function in almost reverse order. The decryption function normally takes a set of (C,T,A,N) as an input, but since the nonce N can be regarded as a part of the additional data A in APE, the set of (C,T,A) is Considered as input.

When calculating the decryption function, the value of the b-bit state is initialized to a value obtained by concatenating the final block (C 2 in the example of FIG. ₂ ) of the r-bit encrypted data C and the c-bit tag T.

Step 1. An exclusive OR of the c bits in the capacity part of the b-bit state with the c-bit key K is calculated, and the c bits in the capacity part are updated according to the calculation result.

Step 2. For the b-bit state, calculate the inverse function f ⁻¹ :{0,1} ^b →{0,1} ^b of the permutation f. The output of the inverse function f ^-1 of this permutation f is taken as the value of the new state. For the r bits of the rate part, the exclusive OR of the block immediately before the final block of the encrypted data C (C _{1 in} the example of FIG. 2) is calculated, and the calculation result is the final block of the message M (see FIG. In the example of 2, it is output as M ₂ ). Further, the r bits of the rate portion are updated by the block immediately before the final block of the encrypted data C (C _{1 in} the example of FIG. 2), and the updated state is set as a new state value. This operation is repeated until the first block (C _{0 in} the example of FIG. 2) of the encrypted data C is processed. Thus, the last block of the message M (M ₂ in the example of FIG. 2) to a second block (M ₁ in the example of FIG. 2) is restored. Of the last updated state, the r-bit value of the rate part is S _r , and the c-bit value of the capacity part is S _c .

Step 3. The method of restoring the first block (M _{0 in} the example of FIG. 2) of the message M is different from the other blocks. First, the same calculation as the procedure 1 to the procedure 2 of the encryption function is performed. Of the updated state, the value of r bits of rate portion S _'r, the value of c bit capacity portion S' and _c. The exclusive OR of the r-bit value S _r and the r-bit value S′ _r is calculated, and the calculation result is output as the first block (M _{0 in} the example of FIG. 2) of the message M.

Step 4. The c-bit value S _c is compared with the c-bit value S′ _c, and if the values match, the decoded message M (M=M ₀ ||M ₁ ||M _{2 in} the example of FIG. ₂ ) is output. To do. The decrypted message M is also referred to as decrypted data. If they do not match, the message M is not output, and only the error code indicating that the decoding has failed is output.

Elena Andreeva, Begul Bilgin, Andrey Bogdanov, Atul Luykx, Bart Mennink, Nicky Mouha and Kan Yasuda, "APE: Authenticated Permutation-Based Encryption for Lightweight Cryptography," FSE 2014, (eds.) Carlos Cid and Christian Rechberger, LNCS, Vol 8540, pages 168-186, Springer, 2015. Elena Andreeva, Begul Bilgin, Andrey Bogdanov, Atul Luykx, Florian Mendel, Bart Mennink, Nicky Mouha, Qingju Wang and Kan Yasuda, "PRIMATEs v1 | Submission to the CAESAR Competition," Submitted to CAESAR, 2014.

However, the APE of the prior art is based on the specifications that both the additional data A (which may include the nonce N) and the message M are double lengths of the number r of bits in the rate portion. Therefore, the application destination is limited.

For example, the following method can be considered as a method of accepting A and M of arbitrary length. For each of A and M, if the size is not a multiple of r, add bit 1 and then add bit 0 until it becomes a multiple of r. This operation is called 10 ^* padding. 10 ^* padding adds a maximum of r-1 bits of information.

FIG. 3 shows the encryption process of APE modified to accept A and M of arbitrary length including 10 ^* padding. In this encryption processing, if the length of M is not a multiple of r, the length of the encrypted data C becomes longer than the length of the message M, and the communication cost increases.

The present invention accepts additional data A and message M of arbitrary length, and can suppress an increase in communication cost, an encrypted data generation device, a decryption data generation device, an authentication encryption system with additional data, a method thereof, and a program. The purpose is to provide.

In order to solve the above problems, according to an aspect of the present invention, an authentication cryptographic system with additional data includes an encrypted data generation device and a decrypted data generation device. The encrypted data generation device sets the bit length of the secret key K to c bits, sets the b bit information including the r bit rate part and the c bit capacity part to the state, and sets the bit length |M| of the message M to The remainder when divided by r bits is (rx), x bits of data A ^x included in the additional data A is embedded in the message M, and the embedding part that obtains the message M'after embedding and the additional data A or additional data The part A'' from the data A excluding the data A ^x is added with a predetermined bit string so that the bit length is a minimum integer multiple of r, and the padding part for obtaining the value A'after the addition and the value A' of the bit length | a '| and then, n = 1,2, ..., | a' | / and r, 'a | a' | value a / r is divided into pieces each value obtained by the a _'n , A value obtained by concatenating a predetermined bit string and the secret key K is the initial value S ₀ of the encryption state, and for the r-bit of the rate part S _R,n-1 of the b-bit encryption state S _n-1 , 'XOR S _R and _{n, n-1} XOR a' value a and the first exclusive OR unit for obtaining the _n, the function of replacing the bit string d b-bit bit string e of b bits and replacing f , rate portion of the encrypted state S _n-1 S _R, the exclusive OR S _R a _n-1, the bit string is replaced with _n-1 XOR a _'n to replace with substitution f, encrypted state S _n To determine the bit length of the message M', and the boundary setting part that inverts the predetermined bits of the capacity part S _C,|A'|/r of the encryption state S _|A'|/r. | M '| and then, m = 1,2, ..., | M' | / r and, 'a | M' | message M / r pieces each value obtained by dividing the a M _'m, b bits encryption state S _{| a '|} rate portion of the _{/ r + m-1 S R} , | a' | / r + to r bits of _m-1, the exclusive OR S _R of the message M _{'m, | a |} a second exclusive OR unit for obtaining a _{'/ r + m-1 XOR} M' m, encrypted state _{S | a '| / r +} m-1 of the rate portion _{S R, | a' | /} r _{+ m-1} XOR S _{R, | a |} a _{'/ r + m-1 XOR} M' bit string is replaced with _m replaced with a substituent f, encrypted state S _{| a '| / r + m,} and the r bits of the rate part S _R,|A'|/r+m of the encryption state S _|A'|/r+m is the encrypted data C _m, and |M'|/r Encrypted data including encrypted data C _m C=(C ₁ , C ₂ ,..., C _|M'|/r ), and the second permutation that outputs the encryption state S _{|A'|/r+|M'|/r} capacity part S _{C,|A'|/r+|M'|} A tag generation unit that outputs the exclusive OR of _/r and the secret key K as a tag T, and an output unit that outputs the encrypted data C, the tag T, and the portion A″. The decrypted data generation device is based on the input unit that receives the encrypted data C, the tag T, and the part A″, and the bit length |A| of the additional data A and the bit length |A″| of the part A″. data bit length of a ^x | a ^x | and delete bit length calculation unit for obtaining the encrypted data _{C = (C 1, C 2} , ..., C | M '| / r) encrypted data contained in the C _{| M} A value obtained by concatenating the _||r and the c-bit tag T is set as the initial value S _|M'|/r of the state S _m , and the capacity part S _{C,|M'| of the} state S _|M'|/r is set. The exclusive OR of S _{/C and |M'|/r} XOR K of _/r and the secret key K of c bit and the inverse function of the permutation f are f ^-1 , and the state S _{| M '| / r} capacity portion S _{C of, | M' | / r} XOR _{S C, | M '| /} r bit string is replaced with XOR K was replaced with an inverse function f ^-1 , State S _|M'|/r-1 for the third permutation part, and m=1,2,3,...,|M'|/r-2, for rate part S _{R,m of} state S _m , a fourth exclusive OR unit that outputs the exclusive OR S _R and the encrypted data C _m, the _m XOR C _m as decoded data _{M m + 1, D, m} = 1,2, ..., | M '|/r-1, the fourth permutation for obtaining the state S _m-1 by substituting the bit string in which the rate part S _R,m of the state S _m is replaced with the encrypted data C _m by using the inverse function f ^-1 And the rate part S _{R,|M'|/r of} the state S _|M'|/r and the encrypted data C _|M'|/r S _R,|M'|/r XOR C _|M'|/r is divided into x bits corresponding to data A ^x and other rx bits using bit length |A ^x |, and exclusive OR S _{R,|M'|/ r} XOR C _|M'|/r A division unit that outputs rx bits of data with x bits removed as decoded data M _|M'|/r,D and an exclusive OR S _{R,|M'|/ r} XOR C _|M'|/r combines x bits into the part A'' to form the decoded additional data A _D , and the decoded additional data A _D has a bit length that is the smallest integer multiple of r adding a predetermined bit sequence as, 'padding unit for obtaining the _D, the value a' the value a after adding the bit length of the _D | a _'D | and then, n = 1,2, ..., | a' D | /r, and each value obtained by dividing the value _A'D into |A' _D |/r is A'n _,D. And a value obtained by connecting the meta bit stream and the secret key K and an initial value S _{0, D} decoding state, the b-bit decoding state S _{n-1, D} rate portion S _R, the r-bit _{n-1, D} contrast, the value a _'n, XOR _{S R, n-1, D} XOR a and _{D' D,} a fifth exclusive OR unit for obtaining the _n, rate portion of the decoding state S _{n-1, D} S _R, and substituted with _n-1, exclusive of _{D S R, n-1,} D XOR a 'n, replacing the bit string is replaced with _D f, the decoding state S _n, the fifth obtaining the _D The replacement part and the decoding part S _{|A'_D|/r,D} of the capacity part S _{C,|A'_D|/r,D} of the predetermined bit is inverted and the decoding state S _{|A'_D|/r , The} boundary removal part that updates _D , and the updated decoding state S _{|A'_D|/r,D} capacity part S _{C,|A'_D|/r,D} and state S ₀ capacity part S Message authentication is performed depending on whether or not _C,0 matches _, and if they match _, the rate part S _{R,|A'_D|/r,D} of the decoding state S _{|A'_D|/r,D} An authentication unit that outputs the exclusive OR of the rate part S _R,0 of the state S ₀ as the decoded data M _1,D .

According to the present invention, it is possible to receive the additional data A and the message M having an arbitrary length and to suppress an increase in communication cost.

The figure for demonstrating the conventional encryption function. The figure for demonstrating the conventional decoding function. The figure for demonstrating the conventional encryption function. The figure which illustrates the functional structure of the authentication encryption system with additional data. The figure which illustrates the functional structure of an encryption device. The figure which illustrates the functional structure of an additional data calculation part. The figure which illustrates the functional structure of a message calculation part. The figure which illustrates the functional structure of a decoding device. The figure which illustrates the functional structure of the encrypted data inverse calculation part. The figure which illustrates the functional structure of an additional data calculation part. The figure which illustrates the processing procedure of an encryption method. The figure for demonstrating an example of the encryption function of embodiment. The figure which illustrates the processing procedure of a decoding method. The figure for demonstrating an example of the decoding function of embodiment.

Hereinafter, embodiments of the present invention will be described. In the drawings used for the following description, components having the same function and steps for performing the same process are denoted by the same reference numerals, and duplicate description will be omitted.

<First embodiment>
The embodiment of the present invention is a method in which APE is obviously extended to a message M of arbitrary length, and the length of A (or nonce N which is a part of A) is shared with the recipient who decrypts before the decryption process. If yes, then A (or nonce N that is part of A) rather than 10 ^* padding as the padding if the length of message M is not a multiple of length r of the rate portion of the state Is embedded at the end of the message M until the length r of the rate part is doubled. The embedded data is not separately transmitted to the receiver, but is restored by the receiver during the decoding process.

As shown in FIG. 4, the authentication encryption system with additional data according to the embodiment includes an encryption device 1 that executes an encryption function of an authentication encryption with additional data and a decryption device 2 that executes a decryption function of an authentication encryption with additional data. Including and In this embodiment, the encryption device 1 and the decryption device 2 are each connected to the communication network 3. The communication network 3 is a circuit-switched or packet-switched communication network configured so that the connected devices can communicate with each other. For example, the Internet, a LAN (Local Area Network), or a WAN (Wide Area Network). Etc. can be used. Note that each device does not necessarily need to be able to communicate online via the communication network 3. For example, the information output from the encryption device 1 may be stored in a portable recording medium such as a magnetic tape or a USB memory, and the offline information may be input to the decryption device 2 from the portable recording medium.

As shown in FIG. 5, the encryption device 1 included in the authentication encryption system with additional data includes a storage unit 10, an input unit 11, an initialization unit 12, an embedding unit 13, an additional data calculation unit 14, a boundary setting unit 15, It includes a message calculation unit 16, a tag generation unit 17, and an output unit 18. As shown in FIG. 6, the additional data calculation unit 14 included in the encryption device 1 includes a padding unit 140, a dividing unit 141, an exclusive OR unit 142, and a replacing unit 143. The message calculation unit 16 included in the encryption device 1 includes a division unit 161, an exclusive OR unit 162, and a replacement unit 163, as shown in FIG. 7.

As shown in FIG. 8, the decryption device 2 included in the authentication encryption system with additional data includes, for example, a storage unit 20, an input unit 21, a deletion bit length calculation unit 211, a first initialization unit 22, a tag decryption unit 23, The encrypted data inverse calculation unit 24, the division unit 251, the combination unit 252, the padding unit 253, the additional data calculation unit 26, the boundary removal unit 27, the authentication unit 29, and the output unit 30 are included. The encrypted data inverse calculation unit 24 included in the decryption device 2 includes an inverse replacement unit 241 and an exclusive OR unit 242, as shown in FIG. 9. As shown in FIG. 10, the additional data calculation unit 26 included in the decoding device 2 includes a division unit 261, an exclusive OR unit 263, and a replacement unit 264.

The encryption device 1 performs the process of each step shown in FIG. 11, and the decryption device 2 performs the process of each step shown in FIG. 13 to implement the authentication encryption method with additional data of the embodiment. Note that, of the authentication encryption method with additional data, the part executed by the encryption device 1 is also called an encryption method, and the part executed by the decryption device 2 is also called a decryption method.

For the encryption device 1 and the decryption device 2, for example, a special program is read by a known or dedicated computer having a central processing unit (CPU), a main storage device (RAM: Random Access Memory), and the like. It is a special device configured. The encryption device 1 and the decryption device 2 execute each process under the control of the central processing unit, for example. The data input to the encryption device 1 and the decryption device 2 and the data obtained in each process are stored in, for example, the main storage device, and the data stored in the main storage device is sent to the central processing unit as necessary. It is read and used for other processing. At least a part of each processing unit of the encryption device 1 and the decryption device 2 may be configured by hardware such as an integrated circuit. Each storage unit included in the encryption device 1 and the decryption device 2 is, for example, a main storage device such as a RAM (Random Access Memory), a hard disk, an optical disk, or an auxiliary device configured by a semiconductor memory element such as a flash memory (Flash Memory). It can be configured by a storage device or middleware such as a relational database or a key-value store.

<Encryption device 1>
Of the authentication encryption method with additional data executed by the authentication encryption system with additional data according to the embodiment, an encryption method executed by the encryption device 1 will be described with reference to FIGS. 11 and 12.

<Memory unit 10>
The storage unit 10 of the encryption device 1 has a b-bit state composed of an r-bit rate part and a c-bit capacity part (hereinafter, to be distinguished from the state stored in the storage part 20 of the decryption device 2). , And the common key K shared in advance with the decryption device 2 are stored. For example, the state is 512 bits, the rate part is 256 bits, and the capacity part is 256 bits (that is, b=512, r=256, c=256). The ratio of the length of the rate part to the length of the capacity part has a trade-off relationship between processing speed and safety. As the length of the rate portion increases, the processing speed increases, but the safety decreases. On the contrary, if the length of the capacity portion is increased, the safety is improved but the processing speed is reduced. Therefore, the values of b, r, and c may be appropriately designed in consideration of the desired balance between processing speed and safety.

<Input unit 11>
In step S11, the set (A,M) of the additional data A and the message M is input to the input unit 11 of the encryption device 1. Note that the nonce N may be input as a part of the additional data as in the conventional APE. Both the additional data A and the message M are data of arbitrary length. The input unit 11 inputs the message M and the additional data A to the embedding unit 13.

<Initializer 12>
In step S12, the initialization unit 12 of the encryption device 1 sets a value obtained by concatenating the predetermined bit string and the secret key K as the initial value S ₀ of the encryption state. For example, in the encryption state stored in the storage unit 10, the initialization unit 12 sets the value of the rate portion to 0 (that is, a bit string in which all bits are 0) and sets the value of the capacity portion to the common key K. Set to the value of and initialize.

<Embedding part 13>
In step S13, the embedding unit 13 of the encryption device 1 receives the message M and the additional data A from the input unit 11, embeds x bits of data A ^x included in the additional data A in the message M, and inserts the message after the embedding. M′ and a portion A″ obtained by removing the data A ^x from the additional data A are obtained. Here, the remainder when the bit length |M| of the message M is divided by r bits is (rx). For example, when the message M has x bits (1≦x≦r−1) shorter than the double length of r bits, the embedding unit 13 adds the last x bits of the additional data A to the end of the message M (data A ^x ) is embedded and the message M′ and the part A″ are obtained.

<Additional data calculation unit 14>
In step S14, the additional data calculation unit 14 of the encryption device 1 receives the additional data A from the input unit 11 or the part A″ from the embedding unit 13, and uses the additional data A or the part A″ to store the data in the storage unit 10. Update the encryption state value stored in.

In this case, the additional data calculation unit 14 is configured as follows.

(Padding part 140)
The padding unit 140 receives the additional data A from the input unit 11 or the part A″ from the embedding unit 13, and a predetermined bit string such that the additional data A or the part A″ has a bit length that is a minimum integer multiple of r. Is added, and the value A′ after the addition is calculated. For example, if the additional data A is not double-length r bits, A is updated to a value with 10 ^* padding. The value that has been updated and is a multiple of r is A'. If the nonce is guaranteed in the portion A″, only the portion A″ is padded with 10 ^* to obtain the value A′.

(Split unit 141)
The division unit 141 of the additional data calculation unit 14 divides the value A′ into blocks of r bits. Note that the bit length of the value A'is |A'|, n=1,2,...,|A'|/r, and each value obtained by dividing the value A'into |A'|/r Be _A'n .

(Exclusive OR section 142)
The exclusive-OR unit 142 of the additional data calculation unit 14 performs an exclusive-OR S _R, with the value A′ _n for the r bits of the rate portion S _R,n−1 of the b-bit state S _{n−1 .} seek _n-1 XOR a _'n.

(Replacement unit 143)
The replacement unit 143 of the additional data calculation unit 14 replaces the bit string in which the rate part S _R,n-1 of the encryption state S _n-1 is replaced with the exclusive OR S _R,n-1 XOR A′ _n by the replacement f. Substitution is performed to obtain the encryption state S _n . The replacement f:{0,1} ^b → {0,1} ^b is a function that replaces the b-bit bit string d with the b-bit bit string e, and the inverse function f ^-1 that restores the input value. :{0,1} ^b →{0,1} ^b (function that replaces b-bit bit string e with b-bit bit string d). As the substitution f, for example, the technique described in Non-Patent Document 2 can be used. The processing of the exclusive OR section 142 and the replacing section 143 is repeated from n=1 to n=|A′|/r in order.

<Boundary setting unit 15>
In step S15, the boundary setting unit 15 of the encryption apparatus 1 the encrypted state S from the additional data generator 14 _{| '|} receive _{/ r,} encrypted state S _{| A' | A /} Capacity part of _r S _{C ,|A'|/r} is inverted, and the encryption state S _|A'|/r is updated. For example, the boundary setting unit 15 calculates the exclusive OR of the capacity part of the encryption state and the integer value 1 (that is, the bit string in which only the least significant bit is 1), and the calculation result determines the capacity of the encryption state. Update the city part. In other words, the boundary setting unit 15 inverts only the least significant bit of the encryption state. This operation is performed so that the receiver can distinguish the boundary between the encrypted data C and the additional data A.

<Message calculator 16>
In step S16, the message calculation unit 16 of the encryption device 1 receives the message M′ from the embedding unit 13 and updates the value of the encryption state stored in the storage unit 10 using the message M′.

(Dividing unit 161)
The division unit 161 of the message calculation unit 16 divides the message M′ into blocks of r bits. The bit length of the message M'is |M'|, m=1,2,...,|M'|/r, and each value obtained by dividing the message M'into |M'|/r is M. ' _m .

(Exclusive OR section 162)
Exclusive OR of the message calculation unit 16 162, b-bit encryption state _{S | A '| / r +} m-1 of the rate portion _{S R, | A' | /} r + a r-bit _m-1 against, 'XOR S _R with _{m, | a' |} message M Request _{/ r + m-1 XOR M} 'm.

(Replacement unit 163)
The substitution unit 163 of the message calculation unit 16 performs an exclusive OR S _{R,|A on} the rate part S _{R,|A′|/r+m−1} of the encryption state S _{|A′|/r+m−1. '|/r+m-1} XOR M'The bit string replaced with _m is replaced with the replacement f to obtain the encryption state S _|A'|/r+m , and the encryption state S _|A'|/r Let r bits of the rate part of _{+m be} the encrypted data C _m, and the encrypted data C=(C ₁ , C ₂ , ..., C _|M'| that contains |M'|/r encrypted data C _{m. /r} ) is output.

<Tag generator 17>
In step S17, the tag generator 17 of the encryption apparatus 1 the encrypted state _{S | A '| / r +} | M' | / capacity portion _{r S C, | A '|} / r + | M' | / r And an exclusive OR of the secret key K with the secret key K, and the calculation result is output as a tag T.

<Output unit 18>
In step S18, the output unit 18 of the encryption device 1 decrypts the set (C,T,A'') of the encrypted data C, the tag T, and the portion A″ of the additional data A excluding the data A ^x. Send to device 2.

<Decoding device 2>
Of the authentication encryption method with additional data executed by the authentication encryption system with additional data according to the embodiment, the decryption method executed by the decryption device 2 will be described with reference to FIGS. 13 to 14.

<Memory unit 20>
In the storage unit 20 of the decryption device 2, two b-bit states each consisting of an r-bit rate portion and a c-bit capacity portion (hereinafter, the encryption state stored in the storage unit 10 of the encryption device 1 and For the sake of distinction, one state is simply referred to as a state and the other is referred to as a decryption state), and the common key K shared in advance with the encryption device 1 and the bit length |A| of the additional data A are stored. Has been done. The values of b, r, and c are the same as the states stored in the storage unit 10 of the encryption device 1. It is assumed that the bit length |A| of the additional data A can be shared between the encryption device 1 and the decryption device 2 (or between the sender and the receiver) prior to the decryption process.

<Input unit 21>
In step S21, the set (C, T, T) of the encrypted data C received from the encryption device 1, the tag T, and the part A″ from which the data A ^x is removed from the additional data A is input to the input unit 21 of the decryption device 2. A'') is entered. The input unit 21 transfers the final block of the encrypted data C and the tag T to the first initialization unit 22, the part A″ to the additional data calculation unit 26 and the deleted bit length calculation unit 211, and the final block of the encrypted data C. Each block other than the block is input to the encrypted data inverse calculation unit 24.

<Deleted bit length calculation unit 211>
In step S211, the deletion bit length calculation unit 211 of the decoding device 2 receives the part A″ from the input unit 21, extracts the bit length |A| of the additional data A from the storage unit 20, and determines the bit length |A| The bit length |A ^x |(=|A|-|A″|) of the data A ^x is calculated based on the length |A″|. With this configuration, calculate how many bits at the end of A are embedded in M (that is, the value of x) from the original length of A and the length of A'' that was actually received. You can

<First initialization unit 22>
In step S22, the first initialization unit 22 of the decryption device 2 receives the final block of the encrypted data C and the tag T from the input unit 21, and determines the value of the rate portion of the states stored in the storage unit 20. Is set to the value of the final block of the encrypted data C, and the value of the capacity part is set to the value of the tag T for initialization. In other words, the first initialization unit 22 uses the encrypted data C _|M'|/r and c-bit data of the encrypted data C=(C ₁ , C ₂ ,..., C _|M'|/r ) included in the encrypted data C=(C ₁ , C ₂ ,... The value that is connected with the tag T is set as the initial value S _|M'|/r of the state S _m . In the subsequent processing, the state S _m is updated in the order of m=|M'|/r,(|M'|/r)-1,...,0.

<Tag decoding unit 23>
In step S23, the tag decoding unit 23 of the decoding device 2 receives the state S _|M'|/r from the first initialization unit 22, and its capacity part S _C,|M'|/r and the c-bit secret. Find exclusive OR S _C,|M'|/r XOR K with key K.

<Encrypted data inverse calculation unit 24>
In step S24, the encrypted data inverse calculation unit 24 of the decryption device 2 receives each block other than the final block of the encrypted data C from the input unit 21, and uses each block C _m of the encrypted data C as a storage unit. The value of the state S _m stored in 20 is updated.

(Reverse replacement unit 241)
The inverse permutation unit 241 of the encrypted data inverse calculation unit 24 calculates the inverse function f ⁻¹ of the permutation f of the permutation f with respect to the entire b-bit state, and sets the calculation result as the value of the new state. For example, in m=|M'|/r (the final block of the encrypted data C), the inverse replacement unit 241 _excludes the capacity part S _C,|M'|/r of the state S _|M'|/r. The bit string replaced with the logical OR S _C,|M'|/r XOR K is replaced with the inverse function f ^-1 to obtain the state S _|M'|/r-1 . Also, in m=(|M'|/r)-1,(|M'|/r)-2,...,1, the inverse permutation unit 241 encrypts the rate part S _R,m of the state S _m . The bit string replaced with the data C _m is replaced with the inverse function f ⁻¹ to obtain the state S _m ⁻¹ . Note that the inverse function f ⁻¹ :{0,1} ^b →{0,1} ^b is an inverse function of the permutation f and replaces the b-bit bit string e with the b-bit bit string d.

(Exclusive OR unit 242)
In m=(|M'|/r)-2,(|M'|/r)-3,..., 3,2,1, the exclusive OR unit 242 of the encrypted data inverse calculation unit 24 is rate portion of the S _m S _R, and _m, the exclusive OR S _R and the encrypted data C _m, to calculate the _m XOR C _m, output from the output unit 30 the calculation result as decoded data M _{m + 1, D} To do. Note that the decoded data M _D =(M _1,D ||M _2,D ||...||M _|M that is the final output of the combination of |M'|/r decoded data M _{m,D '|/r,D} ). However, the decoded data M _|M'|/r,D is not used as it is as the exclusive OR S _R,M'|/r XOR C _M'|/r-1 , but is divided by the dividing unit 251 described later. Value is used. Further, as the decrypted data M _{1 and D} , values obtained by the authentication unit 29 described later are used. If it has not been tampered with, M=M _D.

<Dividing unit 251>
In S251, the dividing unit 251 causes the exclusive OR S _R,|M′|/r XOR C _|M′|/r to be output from the exclusive OR unit 242 and the bit length |A ^x | to be deleted. , And the exclusive OR S _R,|M'|/r XOR C _|M'|/r with the bit length |A ^x | is the x bit corresponding to the data A ^x (for example, the last x bit) And other rx bits, and the exclusive OR S _R,|M'|/r XOR C _|M'|/r removes x bits (for example, the last x bits) and decodes the rx bit data Output as data M _|M'|/r,D .

<Coupling unit 252>
In S252, the combining unit 252 divides the part A″ from the input unit 21 into the exclusive OR S _R,|M′|/r XOR C _|M′|/r into x bits corresponding to the data A ^x. The X bit of the exclusive OR S _R,|M′|/r XOR C _|M′|/r is received from the unit 251 and is combined with the portion A″ to obtain the decoded additional data A _D , which is output. For example, the last x bits of the exclusive OR S _R,|M'|/r XOR C _|M'|/r are added to the end of the part A″.

<Padding section 253>
In S253, the padding unit 253 receives the decoded additional data A _D from binding unit 252, the decoded additional data A _D is, adding a predetermined bit string so as to minimize the integral multiple of the bit length of r, after addition obtaining a value a _'D. For example, if the decoded additional data A _D is not a double length of r bits, the decoded additional data A _D is updated to a value with 10 ^* padding.

<Additional data calculation unit 26>
In step S26, the additional data calculation unit 26 of the decoding device 2 receives the value A′ _D from the padding unit 253 and updates the value of the decoding state stored in the storage unit 20 using the value A′ _D. In this case, the additional data calculation unit 26 is configured as follows.

(Division unit 261)
The division unit 261 of the additional data calculation unit 26 divides the value A′ _D into r-bit blocks. Note that 'the bit length of the _D | A' value A _D | and then, n = 1,2, ..., | '| a / r, the value A _D' a _{D | A A 'D | /} r pieces to divide _Let each value obtained by this be _A'n,D .

(Exclusive OR unit 263)
The exclusive OR unit 263 of the additional data calculation unit 26 compares the value A′ _n,D with the r bits of the rate part S _R,n-1,D of the b-bit decoding state S _n-1,D . exclusive OR _{S R, n-1, D} XOR a 'D, seek _n. As the initial value S _0,D of the decryption state S _n-1,D , the same value as the initial value S ₀ used in the encryption device 1 is used.

(Replacement unit 264)
Substitution unit 264 of the additional data generator 26, the decoded state S _{n-1, D} rate portion S _{R, n-1, D} XOR _{S R, n-1, D} XOR A 'n, the _D The replaced bit string is replaced using the replacement f to obtain the decoding state S _n,D . The replacement can be performed by the same method as the replacement unit 163.

The additional data calculation unit 26 repeats the processes of the exclusive OR unit 263 and the replacement unit 264 from n=1 to n=|A′ _D |/r.

<Border removal unit 27>
In step S27, the boundary removing unit 27 of the decoding device 2 inverts a predetermined bit of the capacity part S _{C,|A′_D|/r,D} of the decoding state S _{|A′_D|/r,D} . Incidentally, subscript A'_D means A _'D. For example, the exclusive OR of the capacity part of the decoding state and the integer value 1 is calculated, and the capacity part of the decoding state is updated by the calculation result. That is, the boundary removing unit 27 inverts only the least significant bit of the decoding state.

<Authentication unit 29>
In step S29, the authentication unit 29 of the decryption device 2 receives the state S ₀ from the encrypted data inverse calculation unit 24, and the updated capacity portion S _{C,|A′_D|/r,D} from the boundary removal unit 27. (Original capacity part S _{C,|A'_D|/r,D} is a bit string obtained by inverting a predetermined bit), and the capacity part S _{C,|A'_D|/r,D} and state S _{0 are received.} Message authentication is performed depending on whether or not the capacity part S _C,0 of the is matched. For example, the decoding state S _{|A′_D|/r,D} and the state S ₀ are stored in the storage unit 20 or the like. Then, S _{C,|A′_D|/r,D} stored in the storage unit 20 is compared with S _C,0 . If the two values are equal, the process proceeds to step S301, and the decoding state S _{|A'_D|/r,D} rate part S _{R,|A'_D|/r,D} and state S ₀ rate part S _{R, 0} the exclusive OR of the outputs from the output unit 30 as the first block of the decoded data M _D (decoded data M _{1, D).} If the two values are not equal, the process proceeds to step S302, and an error code indicating that the decoding has failed is output from the output unit 30.

<Effect>
With the above configuration, a part A ^x of the embedded A (or the nonce N that is a part of A) is not transmitted to the receiver, so that the embedded x bits improve the communication cost.

Note that the encryption device according to the present embodiment is also referred to as an encrypted data generation device in the sense that it generates encrypted data, and the decryption device according to the present embodiment is in the sense that it generates decryption data. Also called a generator. Note that the encrypted data and the decrypted data are information used for processing by the electronic computer, and (i) the invention relating to the encrypted data generating method using the encrypted data generating device and (ii) the decrypted data generating device are used. It goes without saying that the invention relating to the decrypted data generation method described above corresponds to the “invention of a method for producing a product” in Article 2, paragraph 3, item 3 of the Patent Law.

<Other modifications>
The present invention is not limited to the above embodiments and modifications. For example, the above-described various processes may be executed not only in time series according to the description but also in parallel or individually according to the processing capability of the device that executes the process or the need. Other changes can be made as appropriate without departing from the spirit of the present invention.

<Program and recording medium>
Further, various processing functions in each device described in the above-described embodiments and modifications may be realized by a computer. In that case, the processing content of the function that each device should have is described by the program. Then, by executing this program on a computer, various processing functions of the above devices are realized on the computer.

The program describing the processing contents can be recorded in a computer-readable recording medium. The computer-readable recording medium may be, for example, a magnetic recording device, an optical disc, a magneto-optical recording medium, a semiconductor memory, or the like.

The distribution of this program is performed by selling, transferring, or lending a portable recording medium such as a DVD or a CD-ROM in which the program is recorded. Further, the program may be stored in a storage device of a server computer and transferred from the server computer to another computer via a network to distribute the program.

A computer that executes such a program first stores, for example, the program recorded in a portable recording medium or the program transferred from the server computer in its own storage unit. Then, when executing the process, this computer reads the program stored in its own storage unit and executes the process according to the read program. Further, as another embodiment of this program, a computer may directly read the program from a portable recording medium and execute processing according to the program. Further, each time a program is transferred from the server computer to this computer, the processing according to the received program may be executed successively. In addition, a configuration in which the above-described processing is executed by a so-called ASP (Application Service Provider) type service that realizes a processing function only by the execution instruction and result acquisition without transferring the program from the server computer to this computer May be Note that the program includes information that is used for processing by an electronic computer and that conforms to the program (such as data that is not a direct command to a computer but has the property of defining computer processing).

Further, although each device is configured by executing a predetermined program on a computer, at least a part of these processing contents may be realized by hardware.

Claims (8)

The bit length of the secret key K is c bits, and the b bit information including the r bit rate part and the c bit capacity part is the state,
The remainder when the bit length |M| of message M is divided by r bits is set to (rx), x bits of data A ^x included in additional data A are embedded in message M, and message M'after embedding is obtained. Embedded part,
The additional data A or the portion A″ obtained by removing the data A ^x from the additional data A is added with a predetermined bit string so that the bit length is a minimum integer multiple of r, and the value A′ after the addition is added. The desired padding section,
Each value obtained by dividing the value A′ into |A′|/r pieces by setting the bit length of the value A′ to |A′|, n=1,2,..., |A′|/r was the a _'n, and the predetermined bit sequence and a value obtained by connecting the secret key K and an initial value S ₀ of the encrypted state, rate portion of the encrypted state S _n-1 of b bits S _R, the _n-1 to r bits, 'XOR S _R and _{n, n-1} XOR a' value a and the first exclusive OR unit for obtaining the _n,
A function that replaces a b-bit bit string d with a b-bit bit string e is a permutation f, and the rate portion S _R,n-1 of the encryption state S _{n-1 is} the exclusive OR S _R,n-1. the bit string is replaced with XOR a _'n to replace with substitution f, a first replacement unit for obtaining an encrypted state S _n,
A boundary setting unit that inverts a predetermined bit of the capacity part S _C,|A'|/r of the encryption state S _|A'|/r ,
Each value obtained by dividing the message M′ into |M′|/r pieces by setting the bit length of the message M′ to |M′|, m=1,2,..., |M′|/r the 'and _m, b-bit encryption state _{S | a' | M / r} + m-1 of the rate portion S _{R, | a '|} to _{/ r + m-1} of r bits, the message M' and _m exclusive OR S _{R of, |} a _{| '/ r + m-1} XOR M' second exclusive OR unit for determining the _{m, a}
The exclusive OR S _{R,|A'|/r+m- of the} rate portion S _R,|A'|/r+m-1 of the encryption state S _{|A'|/r+m-1 1} XOR M 'bit string is replaced with _m and substituted with the substituent f, encrypted state S _{| a' | / r +} seek _m, the encrypted state S _| rate portion of the _{/ r + m | a '} S _{R, | a '|} a r bits _{/ r + m} and the encrypted data C _m, | _M' | / encrypted data containing the r the encrypted data _{C m C = (C 1,} C 2, ,, C _|M'|/r ) and the second permutation part,
_A tag T is an exclusive OR of the capacity part S _{C,|A'|/r+|M'|/r of the} encryption state S _{|A'|/r+ |M'|/r} and the secret key K. A tag generator that outputs
An output unit that outputs the encrypted data C, the tag T, and the portion A'',
Encrypted data generator. The bit length of the secret key K is c bits, the b bit information including the r bit rate part and the c bit capacity part is the state, and the bit length of the message M is |M|
An input unit for receiving the encrypted data C, the tag T, and the part A'' obtained by removing the data A ^x from the additional data A,
A deletion bit length calculation unit for ^obtaining a bit length |A ^x | of the data A ^x based on the bit length |A| of the additional data A and the bit length |A″| of the portion A″,
The remainder when the bit length |M| is divided by r bits is (rx), and the data obtained by embedding the data A ^x for x bits included in the additional data A in the message M is M′, The bit length of the data M′ is |M′|, m=1,2,...,|M′|/r, and the encrypted data C=(includes |M′|/r encrypted data C _{m. C 1, C 2, ...,} C | M '| / encrypted data C included in _{r) | M' | / r} and state a value obtained by connecting the tag T of the c-bit S _m initial value S of _{| Let M'|/r} be the exclusive OR S _C,|M'|/ of the capacity part S _{C,|M'|/r of} the state S _{|M'| /r} and the c-bit secret key K. _a third exclusive OR section for finding _r XOR K,
The inverse function of the permutation f used for encryption is f ^−1, and the capacity portion S _C,|M′|/r of the state S _{|M′|/r is} the exclusive OR S _{C, A} third permutation unit that finds the state S _|M'|/r-1 by substituting the bit string replaced with _|M'|/r XOR K using the inverse function f ^-1 ;
m = 1,2,3, ..., | M '| / In r-2, state S rate portion S _R of _{m, m} and an exclusive OR S _R and the encrypted data C _{m, m} XOR C _m And a fourth exclusive OR unit for outputting as decoded data M _m+1,D ,
m = 1,2, ..., | M '| / In r-1, the rate portion S _R of the state S _m, the bit string is replaced with the encrypted data C _m and _m by using the inverse function f ^-1 A fourth permutation unit that substitutes for the state S _m-1 ;
Exclusive OR S _R,|M'|/r XOR C _| of rate part S _{R,|M'|/r of} state S _|M'|/r and encrypted data C _{|M'|/r The} bit length |A ^x | is used to divide _M'|/r into x bits corresponding to the data A ^x and other rx bits, and the exclusive OR S _R,|M'|/r XOR C A dividing unit that outputs rx-bit data obtained by removing x bits from _|M'|/r as decoded data M _|M'|/r,D ,
The exclusive OR S _R,|M'|/r XOR C _|M'|/r is connected to the portion A'', and a combining unit is used as decoded additional data A _D ,
The decoding additional data A _D is a padding unit that adds a predetermined bit string so that the bit length is a minimum integer multiple of r, and obtains a value A′ _D after the addition,
The bit length of the value A′ _D is |A′ _D |, n=1,2,...,|A′ _D |/r, and the value A′ _D is divided into |A′ _D |/r. Each value obtained by _{A'n,D, a} value obtained by concatenating a predetermined bit string and the secret key K is the initial value S _0,D of the decryption state, b-bit decryption state S _n-1,D the rate portion S _R, with respect to r-bit _{n-1, D,} the value a _'n, XOR S _R and _{D, n-1, D XOR} a' D, a fifth exclusive OR to obtain the _n With Wabe,
A bit string obtained by replacing the rate part S _R,n-1,D of the decoding state S _{n-1,D with} the exclusive OR S _R,n-1,D XOR A'n _,D is replaced with the replacement f. A fifth permutation unit for substituting using _, to obtain the decoding state S _n,D ,
Decryption state S _{|A'_D|/r,D} capacity part S _{C,|A'_D|/r,D} is inverted and the decoding state S _{|A'_D|/r,D} is updated. A boundary removal section that
Whether or not the updated decoding state S _{|A'_D|/r,D} capacity part S _{C,|A'_D|/r,D} matches the capacity part S _{C,0 of} state S ₀ The message authentication is performed by the above, and if they match _, the rate portion S _{R,|A'_D|/r,D of the} decryption state S _{|A'_D|/r,D and} the rate portion S of the state S ₀ are An authentication unit that outputs an exclusive OR with _R,0 as decrypted data M _1,D ,
Decoded data generation device. An authentication encryption system with additional data including an encrypted data generation device and a decryption data generation device,
The encrypted data generation device,
The bit length of the secret key K is c bits, and the b bit information including the r bit rate part and the c bit capacity part is the state,
The remainder when the bit length |M| of message M is divided by r bits is set to (rx), x bits of data A ^x included in additional data A are embedded in message M, and message M'after embedding is obtained. Embedded part,
The additional data A or the portion A″ obtained by removing the data A ^x from the additional data A is added with a predetermined bit string so that the bit length is a minimum integer multiple of r, and the value A′ after the addition is added. The desired padding section,
Each value obtained by dividing the value A′ into |A′|/r pieces by setting the bit length of the value A′ to |A′|, n=1,2,..., |A′|/r was the a _'n, and the predetermined bit sequence and a value obtained by connecting the secret key K and an initial value S ₀ of the encrypted state, rate portion of the encrypted state S _n-1 of b bits S _R, the _n-1 to r bits, 'XOR S _R and _{n, n-1} XOR a' value a and the first exclusive OR unit for obtaining the _n,
A function that replaces a b-bit bit string d with a b-bit bit string e is a permutation f, and the rate portion S _R,n-1 of the encryption state S _{n-1 is} the exclusive OR S _R,n-1. the bit string is replaced with XOR a _'n to replace with substitution f, a first replacement unit for obtaining an encrypted state S _n,
A boundary setting unit that inverts a predetermined bit of the capacity part S _C,|A'|/r of the encryption state S _|A'|/r ,
Each value obtained by dividing the message M′ into |M′|/r pieces by setting the bit length of the message M′ to |M′|, m=1,2,..., |M′|/r the 'and _m, b-bit encryption state _{S | a' | M / r} + m-1 of the rate portion S _{R, | a '|} to _{/ r + m-1} of r bits, the message M' and _m exclusive OR S _{R of, |} a _{| '/ r + m-1} XOR M' second exclusive OR unit for determining the _{m, a}
The exclusive OR S _{R,|A'|/r+m- of the} rate portion S _R,|A'|/r+m-1 of the encryption state S _{|A'|/r+m-1 1} XOR M 'bit string is replaced with _m and substituted with the substituent f, encrypted state S _{| a' | / r +} seek _m, the encrypted state S _| rate portion of the _{/ r + m | a '} S _{R, | a '|} a r bits _{/ r + m} and the encrypted data C _m, | _M' | / encrypted data containing the r the encrypted data _{C m C = (C 1,} C 2, ,, C _|M'|/r ) and the second permutation part,
_A tag T is an exclusive OR of the capacity part S _{C,|A'|/r+|M'|/r of the} encryption state S _{|A'|/r+ |M'|/r} and the secret key K. A tag generator that outputs
An output unit for outputting the encrypted data C, the tag T, and the portion A'',
The decrypted data generation device,
An input unit for receiving the encrypted data C, the tag T, and the portion A'',
A deletion bit length calculation unit for ^obtaining a bit length |A ^x | of the data A ^x based on the bit length |A| of the additional data A and the bit length |A″| of the portion A″,
The value obtained by concatenating the encrypted data C _|M'|/r and the c-bit tag T included in the encrypted data C=(C ₁ , C ₂ , ..., C _|M'|/r ) is the state. _'| and _{/ r,} state S _{| M' | M |} initial value S of the S _{m /} capacity portion _{r S C, | M '|} / r and exclusive OR S between the secret key K c bits _C,|M'|/r XOR K third exclusive OR section,
Wherein the inverse function of the substitution f and f ^-1, the state S _{| M '| /} the capacity portion of _r S _{C, | M' |} said _{/ r} XOR _{S C, | M '| /} r A third permutation part for substituting the bit string replaced with XOR K using the inverse function f ^-1 to obtain the state S _|M'|/r-1 ;
m = 1,2,3, ..., | M '| / In r-2, state S rate portion S _R of _{m, m} and an exclusive OR S _R and the encrypted data C _{m, m} XOR C _m And a fourth exclusive OR unit for outputting as decoded data M _m+1,D ,
m = 1,2, ..., | M '| / In r-1, the rate portion S _R of the state S _m, the bit string is replaced with the encrypted data C _m and _m by using the inverse function f ^-1 A fourth permutation unit that substitutes for the state S _m-1 ;
Exclusive OR S _R,|M'|/r XOR C _| of rate part S _{R,|M'|/r of} state S _|M'|/r and encrypted data C _{|M'|/r The} bit length |A ^x | is used to divide _M'|/r into x bits corresponding to the data A ^x and other rx bits, and the exclusive OR S _R,|M'|/r XOR C A dividing unit that outputs rx-bit data obtained by removing x bits from _|M'|/r as decoded data M _|M'|/r,D ,
The exclusive OR S _R,|M'|/r XOR C _|M'|/r is connected to the portion A'', and a combining unit is used as decoded additional data A _D ,
The decoding additional data A _D is a padding unit that adds a predetermined bit string so that the bit length is a minimum integer multiple of r, and obtains a value A′ _D after the addition,
The bit length of the value A′ _D is |A′ _D |, n=1,2,...,|A′ _D |/r, and the value A′ _D is divided into |A′ _D |/r. Each value obtained as _{A'n,D, a} value obtained by concatenating a predetermined bit string and the secret key K is the initial value S _0,D of the decryption state, and the b-bit decryption state S _n-1,D the rate portion S _R, with respect to r-bit _{n-1, D,} the value a _'n, XOR S _R and _{D, n-1, D XOR} a' D, a fifth exclusive OR to obtain the _n With Wabe,
A bit string in which the rate portion S _R,n-1,D of the decoding state S _{n-1 ,D} is replaced with the exclusive OR S _R,n-1,D XOR A′ _n,D is replaced with the replacement f. A fifth permutation unit that performs the permutation using to obtain the decoding state S _n,D ,
Decryption state S _{|A'_D|/r,D} capacity part S _{C,|A'_D|/r,D} is inverted and the decoding state S _{|A'_D|/r,D} is updated. A boundary removal section that
Whether or not the updated decoding state S _{|A'_D|/r,D} capacity part S _{C,|A'_D|/r,D} matches the capacity part S _{C,0 of} state S ₀ Message authentication is performed by the above, and if they match _, the rate portion S _{R,|A'_D|/r,D of the} decryption state S _{|A'_D|/r,D and} the rate portion S of the state S ₀ An authentication unit that outputs an exclusive OR with _R,0 as decrypted data M _1,D ,
Authentication encryption system with additional data. The bit length of the secret key K is c bits, and the b bit information including the r bit rate part and the c bit capacity part is the state,
The encrypted data generation device
The remainder when the bit length |M| of message M is divided by r bits is set to (rx), x bits of data A ^x included in additional data A are embedded in message M, and message M'after embedding is obtained. Embedding step,
The additional data A or the portion A″ obtained by removing the data A ^x from the additional data A is added with a predetermined bit string so that the bit length is a minimum integer multiple of r, and the value A′ after the addition is added. The desired padding step,
Each value obtained by dividing the value A′ into |A′|/r pieces by setting the bit length of the value A′ to |A′|, n=1,2,..., |A′|/r was the a _'n, and the predetermined bit sequence and a value obtained by connecting the secret key K and an initial value S ₀ of the encrypted state, rate portion of the encrypted state S _n-1 of b bits S _R, the _n-1 to r bits, 'XOR S _R and _{n, n-1} XOR a' value a and the first exclusive OR step of determining _n,
A function that replaces a b-bit bit string d with a b-bit bit string e is a permutation f, and the rate portion S _R,n-1 of the encryption state S _{n-1 is} the exclusive OR S _R,n-1. the bit string is replaced with XOR a _'n to replace with substitution f, a first replacement step of obtaining the encrypted state S _n,
A demarcation step of inverting a given bit of the capacity part S _C,|A'|/r of the encryption state S _|A'|/r ,
Each value obtained by dividing the message M′ into |M′|/r pieces by setting the bit length of the message M′ to |M′|, m=1,2,..., |M′|/r the 'and _m, b-bit encryption state _{S | a' | M / r} + m-1 of the rate portion S _{R, | a '|} to _{/ r + m-1} of r bits, the message M' and _m exclusive OR S _{R of, |} a second exclusive OR step of obtaining _{| '/ r + m-1} XOR M' m, a
The exclusive OR S _{R,|A'|/r+m- of the} rate portion S _R,|A'|/r+m-1 of the encryption state S _{|A'|/r+m-1 1} XOR M 'bit string is replaced with _m and substituted with the substituent f, encrypted state S _{| a' | / r +} seek _m, the encrypted state S _| rate portion of the _{/ r + m | a '} S _{R, | a '|} a r bits _{/ r + m} and the encrypted data C _m, | _M' | / encrypted data containing the r the encrypted data _{C m C = (C 1,} C 2, ,, C _|M'|/r ) and the second permutation step,
_A tag T is an exclusive OR of the capacity part S _{C,|A'|/r+|M'|/r of the} encryption state S _{|A'|/r+ |M'|/r} and the secret key K. Tag generation step to output,
Performing an output step of outputting the encrypted data C, the tag T, and the portion A'',
Encrypted data generation method. The bit length of the secret key K is c bits, the b bit information including the r bit rate part and the c bit capacity part is the state, and the bit length of the message M is |M|
The decrypted data generator is
An input step of receiving the encrypted data C, the tag T, and the portion A'' of the additional data A excluding the data A ^x ,
A deletion bit length calculation step of ^obtaining a bit length |A ^x | of the data A ^x based on the bit length |A| of the additional data A and the bit length |A″| of the portion A″,
The remainder when the bit length |M| is divided by r bits is (rx), and the data obtained by embedding the data A ^x for x bits included in the additional data A in the message M is M′, The bit length of the data M′ is |M′|, m=1,2,...,|M′|/r, and the encrypted data C=(includes |M′|/r encrypted data C _{m. C 1, C 2, ...,} C | M '| / encrypted data C included in _{r) | M' | / r} and state a value obtained by connecting the tag T of the c-bit S _m initial value S of _{| Let M'|/r} be the exclusive OR S _C,|M'|/ of the capacity part S _{C,|M'|/r of} the state S _{|M'| /r} and the c-bit secret key K. _a third exclusive-OR step to find _r XOR K,
The inverse function of the permutation f used for encryption is f ^−1, and the capacity portion S _C,|M′|/r of the state S _{|M′|/r is} the exclusive OR S _{C, A} third permutation step of permuting the bit string permuted with _|M'|/r XOR K using the inverse function f ^-1 to obtain the state S _|M'|/r-1 ;
m = 1,2,3, ..., | M '| / In r-2, state S rate portion S _R of _{m, m} and an exclusive OR S _R and the encrypted data C _{m, m} XOR C _m A fourth exclusive-OR step for outputting as decoded data M _m+1,D ,
m = 1,2, ..., | M '| / In r-1, the rate portion S _R of the state S _m, the bit string is replaced with the encrypted data C _m and _m by using the inverse function f ^-1 A fourth permutation step of substituting to obtain the state S _m-1 ;
Exclusive OR S _R,|M'|/r XOR C _| of rate part S _{R,|M'|/r of} state S _|M'|/r and encrypted data C _{|M'|/r The} bit length |A ^x | is used to divide _M'|/r into x bits corresponding to the data A ^x and other rx bits, and the exclusive OR S _R,|M'|/r XOR C A dividing step of outputting rx-bit data obtained by deleting x bits from _|M'|/r as decoded data M _|M'|/r,D ,
A combination step of combining the exclusive OR S _R,|M'|/r XOR C _|M'|/r with x bits of the part A'' to obtain decoded additional data A _D ;
The decoding additional data A _D is a padding step of adding a predetermined bit string so that the bit length is a minimum integer multiple of r, and obtaining a value A′ _D after the addition,
The bit length of the value A′ _D is |A′ _D |, n=1,2,...,|A′ _D |/r, and the value A′ _D is divided into |A′ _D |/r. Each value obtained by _{A'n,D, a} value obtained by concatenating a predetermined bit string and the secret key K is the initial value S _0,D of the decryption state, b-bit decryption state S _n-1,D the rate portion S _R, with respect to r-bit _{n-1, D,} the value a _'n, XOR S _R and _{D, n-1, D XOR} a' D, a fifth exclusive OR to obtain the _n Sum step,
A bit string obtained by replacing the rate part S _R,n-1,D of the decoding state S _{n-1,D with} the exclusive OR S _R,n-1,D XOR A'n _,D is replaced with the replacement f. A fifth permutation step of substituting using _, to obtain the decoding state S _n,D ,
Decryption state S _{|A'_D|/r,D} capacity part S _{C,|A'_D|/r,D} is inverted and the decoding state S _{|A'_D|/r,D} is updated. A boundary removal step to
Whether or not the updated decoding state S _{|A'_D|/r,D} capacity part S _{C,|A'_D|/r,D} matches the capacity part S _{C,0 of} state S ₀ The message authentication is performed by the above, and if they match _, the rate portion S _{R,|A'_D|/r,D of the} decryption state S _{|A'_D|/r,D and} the rate portion S of the state S ₀ are _And an authentication step of outputting an exclusive OR with _R,0 as decrypted data M _1,D ,
Decoded data generation method. An authentication encryption method with additional data using an encrypted data generation device and a decryption data generation device,
The encrypted data generation device,
The bit length of the secret key K is c bits, and the b bit information including the r bit rate part and the c bit capacity part is the state,
The remainder when the bit length |M| of message M is divided by r bits is set to (rx), x bits of data A ^x included in additional data A are embedded in message M, and message M'after embedding is obtained. Embedding step,
The additional data A or the portion A″ obtained by removing the data A ^x from the additional data A is added with a predetermined bit string so that the bit length is a minimum integer multiple of r, and the value A′ after the addition is added. The desired padding step,
Each value obtained by dividing the value A′ into |A′|/r pieces by setting the bit length of the value A′ to |A′|, n=1,2,..., |A′|/r was the a _'n, and the predetermined bit sequence and a value obtained by connecting the secret key K and an initial value S ₀ of the encrypted state, rate portion of the encrypted state S _n-1 of b bits S _R, the _n-1 to r bits, 'XOR S _R and _{n, n-1} XOR a' value a and the first exclusive OR step of determining _n,
A function that replaces a b-bit bit string d with a b-bit bit string e is a permutation f, and the rate portion S _R,n-1 of the encryption state S _{n-1 is} the exclusive OR S _R,n-1. the bit string is replaced with XOR a _'n to replace with substitution f, a first replacement step of obtaining the encrypted state S _n,
A demarcation step of inverting a given bit of the capacity part S _C,|A'|/r of the encryption state S _|A'|/r ,
Each value obtained by dividing the message M′ into |M′|/r pieces by setting the bit length of the message M′ to |M′|, m=1,2,..., |M′|/r the 'and _m, b-bit encryption state _{S | a' | M / r} + m-1 of the rate portion S _{R, | a '|} to _{/ r + m-1} of r bits, the message M' and _m exclusive OR S _{R of, |} a second exclusive OR step of obtaining _{| '/ r + m-1} XOR M' m, a
The exclusive OR S _{R,|A'|/r+m- of the} rate portion S _R,|A'|/r+m-1 of the encryption state S _{|A'|/r+m-1 1} XOR M 'bit string is replaced with _m and substituted with the substituent f, encrypted state S _{| a' | / r +} seek _m, the encrypted state S _| rate portion of the _{/ r + m | a '} S _{R, | a '|} a r bits _{/ r + m} and the encrypted data C _m, | _M' | / encrypted data containing the r the encrypted data _{C m C = (C 1,} C 2, ,, C _|M'|/r ) and the second permutation step,
_A tag T is an exclusive OR of the capacity part S _{C,|A'|/r+|M'|/r of the} encryption state S _{|A'|/r+ |M'|/r} and the secret key K. Tag generation step to output,
Performing an output step of outputting the encrypted data C, the tag T, and the portion A'',
The decrypted data generation device,
An input step of receiving the encrypted data C, the tag T, and the portion A'',
A deletion bit length calculation step of ^obtaining a bit length |A ^x | of the data A ^x based on the bit length |A| of the additional data A and the bit length |A″| of the portion A″,
The value obtained by concatenating the encrypted data C _|M'|/r and the c-bit tag T included in the encrypted data C=(C ₁ , C ₂ , ..., C _|M'|/r ) is the state. _'| and _{/ r,} state S _{| M' | M |} initial value S of the S _{m /} capacity portion _{r S C, | M '|} / r and exclusive OR S between the secret key K c bits _A third exclusive-OR step for finding _C,|M'|/r XOR K,
Wherein the inverse function of the substitution f and f ^-1, the state S _{| M '| /} the capacity portion of _r S _{C, | M' |} said _{/ r} XOR _{S C, | M '| /} r A third permutation step for permuting the bit string substituted for XOR K using the inverse function f ⁻¹ to obtain the state S _|M'|/r-1 ;
m = 1,2,3, ..., | M '| / In r-2, state S rate portion S _R of _{m, m} and an exclusive OR S _R and the encrypted data C _{m, m} XOR C _m A fourth exclusive-OR step for outputting as decoded data M _m+1,D ,
m = 1,2, ..., | M '| / In r-1, the rate portion S _R of the state S _m, the bit string is replaced with the encrypted data C _m and _m by using the inverse function f ^-1 A fourth permutation step of substituting to obtain the state S _m-1 ;
Exclusive OR S _R,|M'|/r XOR C _| of rate part S _{R,|M'|/r of} state S _|M'|/r and encrypted data C _{|M'|/r The} bit length |A ^x | is used to divide _M'|/r into x bits corresponding to the data A ^x and other rx bits, and the exclusive OR S _R,|M'|/r XOR C A dividing step of outputting rx-bit data obtained by deleting x bits from _|M'|/r as decoded data M _|M'|/r,D ,
A combination step of combining the exclusive OR S _R,|M'|/r XOR C _|M'|/r with x bits of the part A'' to obtain decoded additional data A _D ;
The decoding additional data A _D is a padding step of adding a predetermined bit string so that the bit length is a minimum integer multiple of r, and obtaining a value A′ _D after the addition,
The bit length of the value A′ _D is |A′ _D |, n=1,2,...,|A′ _D |/r, and the value A′ _D is divided into |A′ _D |/r. Each value obtained by _{A'n,D, a} value obtained by concatenating a predetermined bit string and the secret key K is the initial value S _0,D of the decryption state, b-bit decryption state S _n-1,D the rate portion S _R, with respect to r-bit _{n-1, D,} the value a _'n, XOR S _R and _{D, n-1, D XOR} a' D, a fifth exclusive OR to obtain the _n Sum step,
A bit string obtained by replacing the rate part S _R,n-1,D of the decoding state S _{n-1,D with} the exclusive OR S _R,n-1,D XOR A'n _,D is replaced with the replacement f. A fifth permutation step of substituting using _, to obtain the decoding state S _n,D ,
Decryption state S _{|A'_D|/r,D} capacity part S _{C,|A'_D|/r,D} is inverted and the decoding state S _{|A'_D|/r,D} is updated. A boundary removal step to
Whether or not the updated decoding state S _{|A'_D|/r,D} capacity part S _{C,|A'_D|/r,D} matches the capacity part S _{C,0 of} state S ₀ The message authentication is performed by the above, and if they match _, the rate portion S _{R,|A'_D|/r,D of the} decryption state S _{|A'_D|/r,D and} the rate portion S of the state S ₀ are _And an authentication step of outputting an exclusive OR with _R,0 as decrypted data M _1,D ,
Authentication encryption method with additional data. And an encrypted data generation equipment according to claim 1, a program for causing a computer to function. A program for causing a computer to function as the decrypted data generation device according to claim 2.

Images