Key derivation

The present invention relates to data security, and more particularly to permutation data transform for enhanced security.

For thousands of years, humanity has recognized the need to keep secrets. However, the technique of keeping secrets has slowly developed in much of history. The Caesar shift cipher, allegedly used by Julius Caesar himself, was to shift the letters of the alphabet first to hide the message. Therefore, "A" was replaced with "D", "B" was replaced with "E", and so on. This is generally considered to be a very weak cipher, but until centuries later, few better cryptographic algorithms have been developed.

Cryptography has been the focus of enthusiastic research during the two World Wars. Much effort has been made to develop code that the enemy cannot decrypt and to learn how to decrypt the enemy's encrypted email. Mechanical devices that help with encryption have also been designed. The German Enigma machine is not the only mechanical cryptographic machine of the era, but one of the most famous.

And with the advent of computers, the environment for using encryption has changed dramatically. Computers can now encrypt and decrypt messages faster and at a fraction of the cost, without the need for complex machines or hours of manual labor. A new encryption algorithm was also introduced by understanding the mathematics that underlies computers. Diffie and Hellman's work has led to a method of exchanging private keys using "primitive arithmetic modulo primes". This is based on the fact that computing a shared key generated with public information is computationally infeasible. Also well known (inventor R. Rivest, The RSA algorithm (named after A. Shamir and L. Adleman) is due to the fact that factoring large numbers to decrypt encrypted data is also computationally infeasible. It is based on. Although the algorithms studied by Diffie and Hermann and the RSA algorithms can be logically deciphered, unsolved mathematical problems must be solved in order to decipher these algorithms. (As an aside, the RSA algorithm was also one of the first public key cryptosystems to use different keys for decryption and encryption, thereby delivering one key publicly without compromising security. Is now possible.)

<p num="0005"> However, no encryption algorithm is permanently unsolvable. For example, DES (Data Encryption Standard) was originally published in 1976. The government initially estimated its useful life to be 10 years. Although DES has a much longer life than initially estimated useful life, it is considered less than ideal because of its relatively short key. DES has already been superseded by AES (Next Generation Cryptographic Standard) as a government standard, but it is still widely used. Various improvements have been made to DES, but even these improvements cannot make DES permanently safe. After all, DES will generally be considered unsafe. Therefore, there is still a need for ways to increase the security of existing cryptographic algorithms.</p>

In one embodiment, the invention is a method and apparatus for transposed data conversion. The data is divided into two segments. The bits in the first segment control the application of the transpose function to the bits in the second segment. The transformed data includes a transposed group (transposed bit group) of the first segment and the second segment.

In the second embodiment, the present invention is a method and apparatus for exponential data conversion. The data is divided into two segments. The second segment is raised to the function of the first segment. Modulus is then applied to the result. The transformed data contains the first segment and the modulo modal remainder.

In a third embodiment, the present invention is a method and apparatus for deriving a key from a master key. In one embodiment, one part of the master key is hashed and two numbers are derived from another part of the master key. A general-purpose hash function using these two numbers is applied to the hash result, from which the bit as the derivation key is selected.

In a fourth embodiment, a generic hash function is applied to a portion of the master key using an encoded counter and the results are combined. The combined result is hashed and the bit as the derivation key is selected.

The above-mentioned or other features, purposes and advantages of the present invention will be more easily understood by the description and accompanying drawings described below.

Figure 1 shows a common method of executing a secure hash algorithm that generates a derivative key from a master key. The general concept is that the master key 105 is entered into the hash algorithm 110. One example of a secure hash algorithm is SHA-1 (Secure Hash Algorithm) 1). The result of that input is the derivation key 115-1. The secure hash algorithm 110 can be used multiple times. Depending on how the secure hash algorithm 110 is executed, the master key 105 can be repeatedly input to the secure hash algorithm 110 with or without modification. For example, if the secure hash algorithm 110 uses a clock that controls its output, the master key 105 can be used unchanged to generate the derivation keys 115-2 and 115-3. Otherwise, the master key 105 can somehow be combined with the counter to modify the master key 105 so that the derivation keys 115-2 and 115-3 are sufficiently different from the derivation key 115-1. When the secure hash algorithm 110 is properly executed, it is possible to make the derivation keys 115-2 and 115-3 completely independent of the derivation key 115-1 with only a single bit change of the master key 105. it can.

Figure 2 shows the typical behavior of the secure hash algorithm of Figure 1. As shown, the hash algorithm maps the input to multiple hash values. In FIG. 2, the hash value varies between 0 and n, which indicates some value. The output of the hash algorithm can be called a basket. FIG. 2 shows baskets 205, 210, 215, etc. to basket 220.

Unlike general hash algorithms, which can use the desired mapping method to map input to multiple baskets, secure hash algorithms are unpredictable (sometimes also referred to as "no collisions"). .. Knowing that one input produces a particular output, but not knowing how to find another that produces the same output. For example, knowing that the input "5" is mapped to the basket 215 does not know the other input values that are also mapped to the basket 215. In fact, for some specific hash algorithms, there may be no other input that maps to basket 215. This makes the secure hash algorithm 110 "safe" in the sense that there is no easy way to find other inputs that map to the desired output. The only way to find other inputs that map to a particular output is to try different inputs in the hope of finding other values that map to that desired output.

The weakness of the secure hash algorithm is that not all baskets may be mapped equally. That is, there may be only one input mapped to basket 215, but 100 inputs mapped to basket 205. Also, as mentioned above, some baskets may have no inputs mapped to them.

The general purpose hash algorithm has a distribution feature that the secure hash algorithm lacks. As shown in FIG. 3, the generic hash algorithm 305 also maps inputs to baskets 310, 315, 320, 325. However, unlike the secure hash algorithm of FIG. 2, the general purpose hash algorithm 305 evenly distributes its input to multiple baskets. Therefore, the basket 310 is mapped with the same frequency as the baskets 315, 320, 325, and so on.

The weakness of the generic hash algorithm is that it is generally easy to find other inputs that map to the same basket. For example, suppose you have a generic hash algorithm that selects the basket corresponding to the last digit of the input and maps it to the 10 baskets numbered 0-9. It is easy to see that this hash algorithm evenly distributes its output to all baskets. However, it is also easy to find other inputs that map to the same basket as given inputs. For example, 1, 11, 21, 31, etc. are all mapped to basket 315.

Therefore, it should be understood that both the secure hash algorithm and the general purpose hash algorithm have advantages and disadvantages. From a security standpoint, the best solution is to somehow combine the benefits of both secure and general purpose hash algorithms. FIG. 4 shows how the secure hash algorithm of FIGS. 1 and 2 and the general purpose hash algorithm of FIG. 3 can be combined to generate a more secure derivation key according to an embodiment of the present invention. In sequence 405, the master key 105 is first sent to the secure hash algorithm 110. The result of the secure hash algorithm 110 is then used as an input to the general purpose hash algorithm 305, from which the derivation key 115-1 is generated.

Sequence 405 shows the situation where the secure hash algorithm 110 is used before the generic hash algorithm 305, whereas sequence 410 reverses this order. Therefore, the master key 105 is used as an input to the general purpose hash algorithm 305. The result of the generic hash algorithm 305 can then be used as input to the secure hash algorithm 110, from which the derivation key 115-1 can be generated.

The secure hash algorithm 110 and the general purpose hash algorithm 305 can be executed in a desired form. For example, the secure hash algorithm 110 and the general purpose hash algorithm 305 can be executed in various Read Only Memory (ROM) and firmware, or as software stored in a storage device, and the secure hash algorithm 110 and the general purpose hash algorithm 305 can be executed. Some examples are provided in which the 305 is run by a general purpose processor. These executions can also include executions on dedicated equipment. For example, the processor can be specially designed to run the secure hash algorithm 110 and the generic hash algorithm 305. Therefore, as another example, the computer can be designed to execute either the secure hash algorithm 110 or the general purpose hash algorithm 305. Those skilled in the art will understand other ways in which both the secure hash algorithm 110 and the generic hash algorithm 305 can be performed.

FIG. 5 shows a server and device capable of performing data conversion, key generation, key wrapping, and data encryption according to an embodiment of the present invention. Figure 5 shows the server 505. The server 505 includes a data converter 510, a key derivation function (hereinafter referred to as "key derivation function unit") 515, a key wrapping function (hereinafter referred to as "key wrapping function unit") 520, and an encryption function (hereinafter referred to as "key wrapping function unit") 520. Includes 525 (referred to as "encryption function unit"). The data converter 510 is responsible for performing the data conversion. Data conversion is inherently insecure, as described below with reference to Figures 8-9, 10A-10C, and 11, but scrambling the encoded data increases the complexity of the data. , Which makes cryptanalysis more difficult. For example, data conversion can mask the pattern of encoded data (data that has not been converted).

The key derivation function unit 515 is in charge of deriving the key used for data encryption. Certainly any key can be used to encrypt data, but the more specific a key you use, the more likely it is that the key will be found by cryptanalysis. Therefore, some systems utilize the master key to generate multiple derivation keys, which are used to encrypt the data. New derivation keys can be generated as needed. Data encrypted using only the derivation key does not help decrypt messages encrypted with such a new derivation key. There are several existing key derivation functions, and three new key derivation functions are described below with reference to Figures 12-13 and 15-16.

The key wrapping function unit 520 is in charge of wrapping the key for transmission. Key wrapping is generally done by encrypting the key for transmission. As an example, RSA can be used to encrypt (ie, wrap) a key. A key that is currently sufficiently secure can be sent to other machines, even on insecure connections, where the key is unwrapped (decrypted) and the data is encrypted. / Can be used for decryption.

Usually, the wrapped key is a private key or a key used in symmetric, cryptosystem, which uses public key or asymmetric, cryptosystem. Wrapped up. The private key cryptosystem uses the same key for encryption and decryption, as opposed to the public key cryptosystem which uses different keys for encryption and decryption. For example, DES and AES are private key cryptosystems, and RSA is public key cryptosystem. Public-key cryptography allows you to securely distribute (deliver) keys (no fear that a third party can intercept and use the key to decrypt a secret message), but public-key cryptography Often takes longer to process than private key cryptography, resulting in longer messages. Wrapping a key using public key cryptography clearly means that server 505 needs to know the public key of the device to which the wrapped key is sent. However, those skilled in the art will appreciate that any cryptographic algorithm can be used to wrap the key and that the wrapped key can accommodate any type of cryptography.

The encryption function unit 525 is used to encrypt the data. Normally, the data is encrypted using the key wrapped in the key wrapping function unit 520, but any person in the industry can use any key to encrypt the data, and the data is desired to be encrypted. You will understand that any data can be used and any desired encryption function can be used.

Further, FIG. 5 shows a device 530 capable of performing data conversion, key wrapping, and data encryption according to an embodiment of the present invention. Despite the fact that device 530 resembles a personal digital assistant (PDA), those skilled in the art will appreciate that device 530 can be any device that uses security algorithms similar to server 505. You will understand. Thus, for example, device 530 may be a computer (eg, a desktop or laptop) that exchanges files with server 505 (the person that exchanges files with may be an ordinary computer rather than the server itself. ). Further, the device 530 may be, for example, a digital medium device that provides digital contents to the user, in which case the server 505 provides the contents to the device 530. Alternatively, device 530 may receive content from legitimate sources, in which case server 505 identifies the rights granted to device 530 with respect to the content. The device 530 may also be software that performs some function stored in some medium used with a general purpose machine such as a computer. In these variations, it is the software executed by device 530, rather than the hardware of device 530, that makes device 530 part of the system shown in FIG. If you are a trader, the software can perform the desired functions, such as floppy (registered trademark) discs, various compact discs (CDs), digital video discs (sometimes called digital versatile discs), and tapes. You will understand that it can also be stored on a medium, or a suitable medium such as a universal serial bus (USB) key, and given some more commonly accepted nomenclature. Alternatively, the device 530 may be a mobile phone and the server 505 may be a base station, in which case the mobile phone and the base station communicate in an encrypted manner. Those skilled in the art will understand other aspects of device 530 and server 505. It will be understood that the communication mode between the server 505 and the device 530 may be any communication mode. For example, it may be a wired, wireless or other communication mode.

The device 530 is similar to the server 505 of FIG. 5 in that it has a data converter 510, a key wrapping function unit 520, and an encryption function unit 525. It should be noted that unlike the server 505 of FIG. 5, the device 530 does not have the key derivation function unit 515. This is because key derivation is generally required only on server 505. If there is a way to communicate with other devices, only one device needs to generate the derivation key. Of course, device 530 (although it may not require key derivation function 520) if both devices can generate the exact same derivation key without a secure way to transmit the derivation key. ) The key derivation function unit 515 can be provided.

FIG. 6 shows a data security device according to an embodiment of the present invention. This data security device can be operated to enhance security by using a data converter in combination with a key wrapping function unit, a key derivation function unit, and an encryption function unit. The data security device 605 can function as either part of the server 505 or device 530 of FIG. 5 with modifications that add or remove components as needed. In the data security device 605, the input port 610 controls the reception of data. The data may be the data of the master key, from which the derived key, the wrapped key, or the encrypted data is generated, among other things. The divider 615 is responsible for splitting the data into multiple blocks. These functional parts apply data transformations to multiple parts of the input data, as described below with reference to Figures 12-13 and 14-16. That is, the divider 615 divides the input data into a plurality of blocks of a desired size so that the data converter 510 can apply to each block. In addition, the data converter 510 is responsible for performing the data conversion, as described below with reference to FIGS. 12-13 and 14-16. The combiner 620 (Combiner) is in charge of combining each block in order to have an appropriate security function after data conversion of each block. The various security functions that can be used include the function of the key derivation function unit 515, the function of the key wrapping function unit 520, or the function of the encryption function unit 525. Finally, the output port 625 outputs the data after the data conversion and / or security function is applied.

It should be noted that the divider 615 generally divides the data into blocks that fit the size of the data conversion algorithm, but this is not always necessary. Therefore, the divider 615 may split the data into blocks that are smaller or larger than the expected input to the data converter 510. If the divider 615 divides the data into smaller blocks expected by the data converter 510, the data can be padded to make those blocks large enough. Also, if the divider 615 divides the data into blocks larger than expected by the data converter 510, the data converter 510 can perform data conversion only on the required number of bits of data. .. For example, if the data converter 510 operates as described in the embodiment of FIG. 10, the data converter 510 handles an 8-byte input. If the data converter 510 receives an input of 8 bytes or more, the data converter 510 can only support 8 bytes of the input. This 8 bytes can be any 8 bytes in the data. For example, it may be the first 8 bytes, the last 8 bytes, or any other desired combination of 8 bytes.

It should also be noted that any data can be converted. Therefore, the data to be converted may be the data of the master key, in which case the converted master key is used to generate a plurality of derived keys. Further, the data to be converted may be the data of the derivation key wrapped before transmission. Alternatively, the data may be encrypted by executing an encryption algorithm. Those skilled in the art will understand other types of data that can be converted.

FIG. 7A-7B shows a flowchart for using the data security device of FIG. 6 according to the embodiment of the present invention. In block 705 of FIG. 7A, the data is divided into a plurality of blocks. At block 710, each block is transformed using data transformation. Each block may or may not undergo individual data conversion as needed. That is, some blocks may be converted and others may not. At block 715, these blocks are reconstructed. Blocks 705-715 are selective and can be omitted if desired, as indicated by the dashed line 720.

In Figure 7B, the data security device is used differently. At block 725, a key wrapping algorithm is applied to the data. At block 730, a key derivation algorithm is applied to the data. Then, at block 735, a data encryption algorithm is applied to the data.

FIG. 8 shows the details of the data converters of FIGS. 5 and 6 according to the embodiment of the present invention. In the embodiment of the data converter 510 shown in FIG. 8, the data converter 510 is a permutation function. It works by transposing (sorting) bits using functions). The data converter 510 has an input port 805 for receiving the data to be converted and a divider 810, a padder 815, a permuter 820, and an output port 825 for outputting the converted data. The divider 810 is responsible for splitting the input data into bits for the application of the transposed function. In fact, the divider 810 first splits the data into two segments. The first segment contains the bits used to control the application of the transposed function to the bit group separated from the second segment. In one embodiment, the data has 64 bits. The first segment has 8 bits. And the second segment has eight 7-bit groups. However, one of ordinary skill in the art can divide the data into groups of any length, the data can be divided into groups of desired length, and different groups can be divided into groups of different lengths. You will understand that it is possible. Finally, the first segment containing the bits that control the application of transposed groups can be omitted if the individual groups are always sorted.

If the data converter 510 supports receiving data of unpredictable size (rather than assuming that the data is always of fixed size), the divider 810 may not be able to properly divide the data into bits. .. The padder 815 can be used to pad the data with additional bits so that the data has a reasonable length to be properly split.

In one embodiment, the application of the transposed function is controlled by the bits of the first segment. If the bits corresponding to the first segment are set, the bits are transposed using a particular transpose function. For example, if the corresponding bit has a value of 1, the corresponding group is transposed using the appropriate transpose function. If the corresponding bit has a value of 0, the corresponding group is not transposed. Alternatively, if the corresponding bit has a value of 0, it can be determined that the corresponding bit group has been sorted using the identity permutation function. it can. You can also index the transposed function. If the number of transposed functions matches the number of bits in the second segment (and therefore also the number of bits in the first segment), then one index identifies the three corresponding elements. be able to. That is, the bits of the first segment, the bit group of the second segment, and the transpose function applied to the bit group can be specified.

The Pamuter 820 is responsible for controlling the transposition (sorting) of bits in the second segment. Those skilled in the art will appreciate that any transposition function can be used, but in one embodiment the Pamuter 820 transposes according to the transpose functions shown in Table 1 below. table 1<img id="000002" he="51" wi="143" file="JP5323908B2_D0001.tif" img-format="tif" img-content="drawing" />

The transpositions shown in Table 1 have some interesting features. First, each transpose function is a transpose function P₁Is a power of. Therefore, P₂ = P₁оP₁, P₃ = P₂оP₁ (= P₁оP₁оP₁) Etc. P₆оP₁Is P again₁Therefore, P₇And P₈Is P₁It is determined by repeating the power before. This means that the data converter 510 only needs to know the execution of one transposed function. That is, the rest of the transpose functions arise from (derive) from the basic transpose functions. Second, the order in Table 1 does not introduce data structures similar to those found in cryptographic functions such as RSA, DES, AES, and SHA-1.

Since the transpose function is reversible (invertable), the data conversion caused by the application of the transpose function in Table 1 can be easily inverted. Table 2 shows the inverse transpose function (inverted transpose function) of the transpose function in Table 1. Table 2<img id="000003" he="51" wi="143" file="JP5323908B2_D0001.tif" img-format="tif" img-content="drawing" />

Therefore, in order to invert (reverse) the data conversion to which the transpose function of Table 1 is applied, it is sufficient to apply the second data conversion to which the transpose function of Table 2 is applied. To allow the reverse conversion, the output port 825 outputs the bits of the first segment directly with the transpose group. Otherwise, the receiver of the converted data will not know which bit group is transposed (or sorted).

Similar to the transposed function in Table 1, one basic function (P in this case)₆^-1), All of the transposed functions in Table 2 can be obtained. Therefore, P₅^-1 = P₆^-1оP₆^-1, P₄^-1 = P₅^-1оP₆^-1(= P₆^-1оP₆^-1оP₆^-1) Etc.

FIG. 9 shows the details of the data converters of FIGS. 5 and 6 according to another embodiment of the present invention. In FIG. 9, the input port 905 and the output port 910 operate in the same manner as the data converter 510 of FIG. However, the data converter 510 of FIG. 9 operates by calculating an exponential permutation of the data, rather than transposing the data using the transpose function. This calculation is performed by the computer 915. As one embodiment, the data converter 510 converts input data having a length of 3 bytes. The first segment is used to calculate the power to the last 2 bytes. Then, the remainder (modulo a modulus) obtained by dividing the calculation result by the modulus (prime number to be the modulus) is obtained. For example, in one example, the data transformation is Y = ((B + 1)).^{(2A + 1)} mod 65537) Calculate as -1. Here, A is the first byte of the input data, and B is the last two bytes of the input data. And the converted data is 3 bytes long including A and Y. However, those skilled in the art will appreciate that the inputs may be of different lengths and that different exponential transpose functions can be applied.

The exponential transpose function shown above has several advantages. First, abstract algebra shows that when the exponent and its modulus minus 1 are relatively prime, the function circulates through all possible values between 1 and the modulus. This means that the exponential transpose function transposes. By selecting 65537 as the prime number, the prime number one less than 65537 becomes 65536, which is a power of 2. Therefore, regardless of the value of A, (2A + 1) is odd and relatively prime to 65536. Next, if A is 0, the output data does not change. Finally, the structure of the data converter 510 in FIG. 9 is similar to the transposed data converter in FIG. 8 and is a structure that does not exist in cryptographic algorithms such as RSA, DES, AES, and SHA-1.

If the data converter 510 supports receiving data of unpredictable size (instead of assuming that the data is always of fixed size), the divider 920 cannot split the data into segments of the appropriate size. there is a possibility. Similar to the data converter padder 815 in FIG. 8, the padder 925 can be used to pad the data with additional bits so that the data is properly divided to the appropriate length.

Similar to the transposed data converter of FIG. 8, the data converter 510 of FIG. 9 can also be inverted. Output port 910 outputs unchanged A with Y to allow inversion of the transformed data. Then, in order to reverse the exponential translocation, the computer 915 calculates the reciprocal of "2A + 1 modulo 65536 (that is, 65537-1)" (the reciprocal of the remainder obtained by dividing 2A + 1 by 65536). If this reciprocal is e, the inverted exponential transpose is ((Y + l))^e mod 65537) -1. As a result of this calculation, it returns to the original byte B. Therefore, the exponential transpose can be easily inverted (reversed) by changing the index of the data conversion and applying the second data conversion.

Since the devices shown in FIGS. 8 and 9 have been described above, how to use them will be described next. 10A-10C show a flowchart for using the data converter of FIG. 8 according to the embodiment of the present invention. Data is received at block 1005 in Figure 10A. At block 1010, the data is split into two segments (assuming that the transpose of the bits is controlled by the bits in the first segment). Block 1015 examines whether the data converter can evenly divide the second data segment into groups. If it cannot be split evenly, in block 1020 data is padded to support splitting the second segment into groups of even size. (This assumes that the data converter is trying to divide the input data into groups of equal size, even if the data converter does not need to divide the input data into groups of equal size. For example, blocks 1015 and 1020 can be omitted.)

In block 1025 (FIG. 10B), the second segment is divided into multiple bit groups. As mentioned above, block 1025 explained that the second segment is divided into groups of equal size, but it is possible to divide it into groups of different sizes if the data converter supports it. In block 1030, each group is associated with a bit in the first segment. Block 1035 defines the basic transpose function. In block 1040, other transpose functions are defined as powers of the basic transpose functions. (But the other transpose functions do not have to be powers of the basic transpose functions. Each transpose function may be independent of each other, in which case blocks 1035 and 1040 can be modified or omitted.) In block 1045 , These transposed functions are indexed.

In block 1050 (Figure 10C), the data converter checks to see if there are any unchecked bits in the first segment (which controls the application of the transpose function to the bits in the second segment). If there are unchecked bits, at block 1055 the data converter checks to see if the bits are set. If a bit is set, block 1060 identifies the transpose function indexed by the bit, and block 1065 applies the identified transpose function to the associated transpose group. Control returns to block 1050 to see if there are any further unexamined bits in the first segment. Eventually, all the bits of the first segment are examined, and at block 1070, the data converter constructs a data conversion (converted data) from the first segment and the transposed bits.

FIG. 11 shows a flowchart for using the data converter of FIG. 9 according to the embodiment of the present invention. At block 1105, the data converter receives the data. At block 1110, the data converter divides the data into two segments. In block 1115, the first segment is used to generate a primitive exponent (multiplier) for the selected modulus. At block 1120, the second segment is multiplied by the calculated exponent. In block 1125, the remainder of the result of multiplying the exponent divided by the modulo is calculated. Finally, in block 1130, a data transformation (converted data) is constructed from the first segment and the remainder.

As mentioned above with reference to Figure 5, there are some existing key derivation functions. However, as mentioned above with reference to FIG. 4, these existing key derivation functions do not have the advantages of both secure hash functions and general purpose hash functions. FIG. 12 shows the details of one key derivation function that combines the advantages of the secure hash function and the general-purpose hash function. In FIG. 12, the key derivation function unit 515 includes an input port 1205 and an output port 1210 used for input to the key derivation function unit and output of the derivation key, respectively. The key derivation function unit 515 also includes a divider 1215, a combiner 1220, a hash unit (hasher) 1225, a determiner 1230, a computer 1235, and a bit selector 1240.

The divider 1215 splits the master key into two parts. The combiner combines the first part of the master key with the counter and makes it part of the input data. One way to combine the master key with a counter is to concatenate the first part of the master key with a counter of any size (eg, 4 bytes). This concatenation can be done in either order. That is, either the first part of the master key or the counter may be the destination of the combination. Then, the result of this combination is hashed using the hash function 1225 to become a secure hash function. (In this example, this hash function 1225 replaces the secure hash algorithm 110 in sequence 405 of FIG. 4.)

The determination unit 1230 is used to determine two numbers from the second part of the master key. In one embodiment, these two numbers a and b are determined as the remainder of the first and last 32 bytes of the second part of the master key divided by the prime number p. In order to select a and b in this way, a master key having a length sufficient for the second part of the master key to be 64 bytes long is required. However, those skilled in the art will appreciate that the master key does not necessarily have to be this length. For example, if the calculation of the remainder of a and b divided by p changes the number of bits of a and b sufficiently, then a and b will have the original bits of those numbers from the second part of the master key. It may be selected in such a manner as to overlap.

Those skilled in the art will appreciate that other prime numbers can be chosen instead, but a particular choice of prime number is p.₁₉₂ = 2¹⁹²-2⁶⁴Can be -1. Calculator 1235 can then execute the general purpose hash function ax + b mod p (where x is the result of hash part 1225). (This generic hash function replaces the generic hash algorithm 305 in sequence 405 of Figure 4.) Finally, the bit selector 1240 can select bits from the result of the generic hash function of the derived key that can be output later. .. For example, the bit selector 1240 can select the least significant bit of the result of the general purpose hash function as the derivation key.

FIG. 13 shows the details of the key derivation function unit of FIGS. 5 and 6 according to another embodiment of the present invention. In contrast to the embodiment of the present invention shown in FIG. 12, which executes the key derivation function unit according to the sequence 405 of FIG. 4, the key derivation function unit 515 of FIG. 13 performs a general-purpose hash algorithm after the secure hash algorithm. Does not apply. Instead, the embodiment of the invention shown in FIG. 13 applies a liner mapping to the input to the secure hash algorithm.

Similar to the key derivation function unit 515 of FIG. 12, the key derivation function unit 515 of FIG. 13 has an input port 1305 and an output port 1310. Input port 1305 receives the master key as input, and output port 1310 outputs the derived key. Further, the key derivation function unit 515 of FIG. 13 has a divider 1315, an encoder 1320, a coupler 1325, a hash unit (hasher) 1330, and a bit selector 1335.

The divider 1315, like the divider 1215 of FIG. 12, divides the master key into two parts. The encoder 1320 then encodes the counter. The encoder 1320 can operate in a desired manner. For example, the encoder 1320 can operate by repeating the counter and extending it to the length of the first part of the master key. So, for example, if the first part of the master key is 64 bytes long and the counter uses 4 bytes, the encoder 1320 can repeat these 4 bytes 16 times to extend the counter to 64 bytes long. The combiner 1325 can then combine each portion of the master key with a coded counter. For example, combiner 1325 can combine a portion of the master key with an encoded counter at the bit level. In one embodiment, the XOR binary function (XOR binary) to combine the part of the master key with the coded counter. function) is used. However, those skilled in the art can use any bitwise function, or in fact any function, to combine the master key portion with the encoded counter. Will understand. The combiner 1325 can then rejoin the two parts of the master key (after binding with the encoded counter). For example, the two parts can be concatenated together (though those skilled in the art will appreciate that the combiner 1325 can rejoin the two parts of the master key in other ways). .. The combiner 1325 can also reconnect the recombined portion of the master key with the encoded counter.

The hash unit 1330 obtains the output of the combiner 1325 and hashes it. The hash 1330 part can be a secure hash function. Then, the bit selector 1335 can select a bit as a derivation key from the result of the hash unit 1330, similarly to the bit selector 1240 in FIG.

Since the devices shown in FIGS. 12 and 13 have been described above, how to use them will be described next. FIG. 14 shows a flowchart for using the key derivation function unit of FIG. 12 according to the embodiment of the present invention. In block 1405, the master key is divided into multiple segments. At block 1410, the first segment is coupled to the coded counter. As described above with reference to FIG. 12, this coupling can be a concatenation of the first segment and the encoded counter. At block 1415, the first combined segment is hashed.

In block 1420, two numbers are determined from the second segment. As mentioned above with reference to FIG. 12, these two numbers can be determined for the modulus. In block 1425, a generic hash function is defined using two determined numbers and modulus. At block 1430, the hash result is applied to the generic hash function. In block 1435, a bit is selected as the derivation key from the result of the general purpose hash.

FIG. 15 shows a flowchart for using the key derivation function unit of FIG. 13 according to the embodiment of the present invention. In block 1505, the master key is divided into multiple segments. At block 1510, each segment is coupled to a coded counter. As described above with reference to FIG. 13, this can be done by applying the XOR bit function individually to each segment, along with the encoded counters. At block 1515, the combined blocks can be recombined and combined with the re-encoded counter (as described above with reference to FIG. 13). At block 1520, this modified master key is then hashed, and at block 1525, a bit as the derived key is selected from the result of the hash.

The key derivation function shown in Figure 12-15 is just two examples. Other key derivation functions that combine the advantages of the secure hash algorithm and the general purpose hash algorithm can also be used. FIG. 16 shows a flowchart of another key derivation function unit in the data security device of FIG. 5 according to the embodiment of the present invention. In block 1605, the master key is divided into multiple segments. In block 1610, the segments are transformed using data transformation. Only a subset of segments are used, as segments are generally larger than data converters can use. For example, only the first byte required for data conversion is used. At block 1615, these transformed segments are combined and combined into a coded counter. For example, these segments and encoded counters can be concatenated together. In block 1620, the converted result is hashed, and in block 1625, a bit as the derivation key is selected from the hashed result.

The apparatus of FIG. 12-13 and the flowchart of FIG. 14-16 show that a single derivation key is generated from the master key, but the embodiment of the present invention repeatedly generates a plurality of derivation keys. It should be noted that it can be easily applied to. These additional derivation keys can be generated in a number of ways. For example, all flowcharts in Figure 14-16 include counters. The counter can be incremented for each additional derived key. Therefore, the counter can use the value 1 to derive the first key, the counter can use the value 2 to derive the second key, and so on.

In another embodiment, rather than using the bit selector 1240 of FIG. 12 or the bit selector 1335 of FIG. 13 to select the bits of the derived key, selecting the bits from the combined results for all the derived keys Sufficient results can be produced at one time. For example, suppose you want a u key, each k-bit long, and further assume that the device in Figure 12-13 and / or the result of the flowchart in Figure 14-16 creates l-bits before bit selection. If the key derivation function is applied m times and m * l u * k, all u derivation keys are selected at the same time as the resulting bits of m * l. For example, all the resulting bits of m * l may be concatenated together. Alternatively, the first key may be selected as the first k-bit and the second key may be selected as the second k-bit until all u keys are selected.

Below is a brief general description of a suitable machine that implements certain aspects of the invention. Machines are typically system buses equipped with, for example, processors, memory (eg, random access memory (RAM), read-only memory (ROM), and other state storage media), storage devices, video interfaces, and output / input interface ports. including. The machine can be controlled, at least in part, by input from conventional input devices such as keyboards and mice and instructions received from other machines, virtual reality (VR) environments, biometric feedback or information exchange with other input signals. It is possible.

As used herein, the term machine is intended to broadly include communication systems that combine a single machine or machines or devices that work together. Typical machines include personal computers, workstations, servers, portable computers, mobile terminals, phones, tablets and other computer devices, as well as transportation means such as personal or public transportation such as cars, trains and taxis. ..

Machines may also include built-in controllers such as programmable or non-programmable logical devices and arrays, application specific integrated circuits (ASICs), built-in computers, smart cards, and the like. The machine may also utilize one or more connections to one or more remote machines via network interfaces, modems or other communication connections. In addition, machines can be interconnected through physical and / or logical networks such as intranets, the Internet, local area networks, wide area networks, and so on. If you are a trader, network communication can be various wired and / or various including radio frequency (RF), satellite, microwave, Institute of Electrical and Electronics Engineers (IEEE), 802.11, Bluetooth, optical, infrared cable, laser, etc. You will understand that wireless short-range or long-range carriers and protocols are available.

The present invention can refer to or be described in relation to related data including functions, procedures, data structures, application programs and the like. When accessed by a machine, these relevant data will either cause the machine to perform a task, or define an abstract data type or low-level hardware context. Related data can be, for example, volatile and / or non-volatile memory such as RAM, ROM, or hard drives, floppy (registered trademark) disks, optical storage devices, tapes, flash memories, memory sticks, digital video disks, biological data. It can be stored in other storage devices including storage devices and their related storage media. In addition, related data can be transmitted in the form of packets, serial data, parallel data, propagated signals, etc. and used in compressed or encrypted form in communication environments including physical and / or logical networks. .. Also, the relevant data can be used in a distributed environment and stored locally and / or remotely for machine access.

Although the principles of the invention have been described and described based on the illustrated examples, it should be understood that the illustrated examples can be modified in their configuration and details without departing from such principles. And while the above description has focused on a particular embodiment, other configurations can be considered. In particular, the phrase "in one embodiment", or similar, is used herein, but these terms generally mean that they can serve as reference embodiments, limiting the invention to the construction of a particular embodiment. Not intended to be done. As used herein, these terms may represent the same or different embodiments that can be combined with other embodiments.

In conclusion, given the wide variety of alternatives to the examples described herein, this detailed description and accompanying drawings are intended for illustration purposes only and should not be taken as limiting the scope of the invention. .. Therefore, what is required of the present invention includes all modifications that do not deviate from the scope and spirit of the claims and their equivalents.

<figref num="1">Figure 1 shows the general execution of a secure hash algorithm that generates multiple derived keys from a master key.</figref><figref num="2">FIG. 2 shows the typical operation of the secure hash algorithm of FIG.</figref><figref num="3">Figure 3 shows the typical behavior of a general purpose hash algorithm.</figref><figref num="4">FIG. 4 shows different methods of combining the secure hash algorithm of FIG. 2 with the general purpose hash algorithm of FIG. 3 to generate a more secure derivation key according to an embodiment of the present invention.</figref><figref num="5">FIG. 5 shows a server and an apparatus capable of performing data conversion, key generation, key wrapping, and data encryption according to an embodiment of the present invention.</figref><figref num="6">FIG. 6 shows a data security device according to an embodiment of the present invention that can operate to enhance security by using a data converter in combination with a key wrapping, key derivation, or encryption function.</figref><figref num="7A">FIG. 7A shows a flowchart for using the data security device of FIG. 6 according to the embodiment of the present invention.</figref><figref num="7B">FIG. 7B shows a flowchart for using the data security device of FIG. 6 according to the embodiment of the present invention (continuation of FIG. 7A).</figref><figref num="8">FIG. 8 shows the details of the data converters of FIGS. 5 and 6 according to the embodiment of the present invention.</figref><figref num="9">FIG. 9 shows details of the data converters of FIGS. 5 and 6 according to other embodiments of the present invention.</figref><figref num="10A">FIG. 10A shows a flowchart for using the data converter of FIG. 8 according to the embodiment of the present invention.</figref><figref num="10B">FIG. 10B shows a flowchart for using the data converter of FIG. 8 according to an embodiment of the present invention (continuation of FIG. 10A).</figref><figref num="10C">FIG. 10C shows a flowchart for using the data converter of FIG. 8 according to the embodiment of the present invention (continuation of FIG. 10B).</figref><figref num="11">FIG. 11 shows a flowchart for using the data converter of FIG. 9 according to the embodiment of the present invention.</figref><figref num="12">FIG. 12 shows the details of the key derivation function unit of FIGS. 5 and 6 according to the embodiment of the present invention.</figref><figref num="13">FIG. 13 shows the details of the key derivation function unit of FIGS. 5 and 6 according to another embodiment of the present invention.</figref><figref num="14">FIG. 14 shows a flowchart for using the key derivation function unit of FIG. 12 according to the embodiment of the present invention.</figref><figref num="15">FIG. 15 shows a flowchart for using the key derivation function unit of FIG. 13 according to the embodiment of the present invention.</figref><figref num="16">FIG. 16 shows a flowchart for using the key derivation function unit in the data security device of FIG. 5 according to the embodiment of the present invention.</figref>