HK1108984B - Permutation data transform to enhance security - Google Patents

Abstract

One data transformation permutes certain bits in a data input (1005) based on other bits in the data input (1030). Another data transformation raises one segment of a data input (1120) to a power of a function of another segment, the power being relatively prime to a function of a predefined modulus (1115). The modulus is then applied to the result (1125), and the transformed data assembled (113). In one key derivation application, a segment of the master key is hashed (1415). Two numbers are derived from another segment of the master key (1420). A universal hash function is applied to the result (1430) of the hash, from which bits are selected as the derived key (1435). In another embodiment, an encoded counter is combined with segments (1510) of the master key. The result is then hashed (1520), from which bits are selected as the derived key (1525).

Description

Permuted data transformation for improved security

Technical Field

The present invention relates to data security, and more particularly to permuted data transformations to improve security.

Background

For thousands of years, people have found it necessary to keep secrets. But for most of the history, security techniques have evolved very slowly. It is speculated that the Caesar shift cipher used only by Julius Caesar itself involves taking one letter and moving it forward through the alphabet to hide the message. Thus, "A" becomes "D", "B" becomes "E", and so on. Although this encryption algorithm is generally considered a very weak encryption, until the last centuries, almost no better encryption algorithm has been developed.

Encryption has been the focus of intense research in two world war operations. Much effort has been expended both in developing codes that are indecipherable by enemies and in studying how enemy encrypted letters are read. Mechanical devices were designed to aid in encryption. The best known one of these machines is the Ennigma (Enigma) machine in Germany, although Ennigma is by no means the only mechanical encryption machine of that age.

The advent of computers has greatly changed the state of use of encryption. No longer requiring complex machinery or hours of manual labor, computers are able to encrypt and decrypt information at high speeds and at low cost. The understanding of the mathematics upon which computers are based has also introduced new encryption algorithms. The work of Diffie and Hellman (Hellman) has led to a way of exchanging keys using exponential arithmetic modular primes (exponential arithmetric modules) and relies on the fact that it is computationally infeasible to compute a shared key that gives public information. Popular RSA algorithms (named after their inventors r.rivest, a.shamir and l.adleman) rely on the fact that factoring large numbers is also computationally infeasible to decrypt encrypted data. The work of diffie and hellman and RSA algorithms can be theoretically deciphered, but deciphering these algorithms relies on solving the mathematical problem to be solved. (incidentally, the RSA algorithm is also one of the earliest public-key cryptosystems, which uses a different key than encryption for decryption.

However, none of the encryption algorithms has an infinite life span. For example, DES (data encryption standard) was first released in 1976. The government initially estimated its life to be 10 years. DES lasts much longer than the originally estimated life span, but due to its relatively short key, DES is considered to be shorter than the ideal life span. Thus AES (advanced encryption standard) replaces DES as a government standard, but DES is still widely used. There are many improvements to DES, but these cannot guarantee that DES is always secure. Eventually, DES will generally be considered unsafe.

There remains a need for a method to enhance the security of existing encryption algorithms.

Disclosure of Invention

In one embodiment, the present invention is a method and apparatus for permuting data transformations. The data is split into two segments. The bits in the first segment control the application of the permutation function to the groups of bits in the second segment. The transformed data includes the first segment, and the permuted set of the second segment.

In a second embodiment, the present invention is a method and apparatus for exponential data transformation. The data is split into two segments. The second segment is raised (raise) to the power of the function of the first segment (power). A modulus is then applied to this result. The transformed data includes the first segment and a remainder modulo the modulus.

In a third embodiment, the present invention is a method and apparatus for performing key derivation from a master key. In one embodiment, a portion of the master key is hashed (hash). Two digits are derived from another part of the master key. A universal hash function using these two numbers is applied to the result of the scrambling, from which bits are selected as the derived key.

In a fourth embodiment, a universal hash function using an encoded counter is applied to portions of the master key and the results combined. The result of the combination is then scrambled, selecting bits from it as the derived key.

The above and other features, objects, and advantages of the present invention will become more apparent from the following detailed description when taken in conjunction with the accompanying drawings.

Drawings

Fig. 1 shows a general implementation (initialization) of a secure hash algorithm for generating derived keys from master keys.

Fig. 2 shows a typical operation of the secure hash algorithm (secure hash algorithm) of fig. 1.

Fig. 3 shows a typical operation of a universal hash algorithm (univeral hash algorithm).

FIG. 4 shows different ways of combining the secure hash algorithm and the universal hash algorithm of FIG. 1 to generate a more secure derived key, according to one embodiment of the invention.

Fig. 5 shows a server and a device capable of performing data transformation, key generation, key wrapping and data encryption according to an embodiment of the present invention.

Fig. 6 shows a data security device for improving security using a combination of a data transformer and a key wrapper, key deriver or cryptographic function, according to one embodiment of the invention.

Figures 7A-7B illustrate a flow diagram for using the data security device of figure 6 in accordance with one embodiment of the present invention.

Fig. 8 shows details of the data transformer of fig. 5 and 6, in accordance with an embodiment of the present invention.

Fig. 9 shows details of the data transformer of fig. 5 and 6 according to another embodiment of the present invention.

Fig. 10A-10C show a flow chart for using the data transformer of fig. 8, in accordance with one embodiment of the present invention.

Fig. 11 shows a flow diagram for using the data transformer of fig. 9, in accordance with an embodiment of the present invention.

Fig. 12 shows details of the key derivation function of fig. 5 and 6, in accordance with an embodiment of the present invention.

Fig. 13 shows details of the key derivation function of fig. 5 and 6, in accordance with another embodiment of the present invention.

Fig. 14 shows a flow diagram for using the key derivation function of fig. 12 in accordance with one embodiment of the present invention.

Fig. 15 shows a flow diagram for using the key derivation function of fig. 13 in accordance with one embodiment of the present invention.

Fig. 16 shows a flow diagram of the use of a key derivation function in the data security apparatus of fig. 5, in accordance with one embodiment of the present invention.

Detailed Description

Fig. 1 shows a general implementation of a secure hash algorithm for generating a derived key from a master key. The general concept is to input the master key 105 to the secure hash algorithm 110. An example of a secure hash algorithm is SHA-1 (secure hash algorithm 1). The result is derived key 115-1. The secure hash algorithm 110 may be used multiple times. Depending on the implementation of the secure hash algorithm 110, the master key 105 may be reused as input to the secure hash algorithm 110, with or without modification. For example, if the secure hash algorithm 110 uses one clock to control its output, the master key 105 may be used without modification to generate the derived keys 115-2 and 115-3. In addition, the master key 105 may be combined with a counter in some manner to modify the master key 105 sufficiently to distinguish the derived keys 115-2 and 115-3 from the derived key 115-1. If the secure hash algorithm 105 is implemented properly, even as little as a single bit change in the master key 105 may result in the derived keys 115-2 and 115-3 being completely unrelated to the derived key 115-1.

FIG. 2 illustrates an exemplary operation of the secure hash algorithm of FIG. 1. As shown, the hash algorithm maps the input to a hash value. In fig. 2, for a certain value n, the hash value varies between 0 and n. The output of the hashing algorithm may be referred to as a basket (basket); fig. 2 shows baskets 205, 210, 215 and so on to basket 220.

With general hashing algorithms (which may use any desired mapping to map inputs to baskets), secure hashing algorithms are unpredictable (sometimes also called collision-free): knowing that one input produces a particular output does not give any information about how to find another input that produces the same output. For example, knowing that the input "5" maps to basket 215 does not help us find any other input value that also maps to basket 215. In fact, for some particular hashing algorithms, there may be no other inputs mapped to the basket 215. This is why the secure hash algorithm 110 is "secure": there is no simple way to find another input that maps to the desired output. The only way to find another input that maps to a particular output is to try a different input in the hope of finding another value that maps to the expected output.

A disadvantage of the secure hash algorithm is that the baskets may not all be mapped equally (equially). In other words, there may be only one input mapped to basket 215, but there may be 100 inputs mapped to basket 205. And as described above, some baskets may not have inputs mapped to them.

The universal hashing algorithm provides the distribution characteristic that the secure hashing algorithm lacks. As shown in FIG. 3, the universal hashing algorithm 305 also maps inputs to baskets 310, 315, 320 through 325. But unlike the secure hash algorithm of fig. 2, the universal hash algorithm 305 evenly distributes its inputs to the baskets (evenly). Thus, basket 310 is mapped at the same frequency as baskets 315, 320, 325, etc., and so on.

A disadvantage of the universal hashing algorithm is that it is often easy to find other inputs that map to the same basket. For example, consider a generic hashing algorithm that maps to 10 baskets, numbered from 0 to 9, by selecting the basket corresponding to the last digit (digit) of the input. It is easy to see that this hashing algorithm distributes its output evenly across all baskets. It is easy to see how to find another input that maps to the same basket as the given input. For example, 1, 11, 21, 31, etc. are mapped to basket 315.

Thus, it is apparent that both secure hash algorithms and universal hash algorithms have advantages and disadvantages. From a security point of view, the best solution is to combine the advantages of the secure hash algorithm and the universal hash algorithm in some way. Fig. 4 shows how the secure hash algorithm of fig. 1-2 and the universal hash algorithm of fig. 3 may be combined to generate a more secure derived key, in accordance with one embodiment of the present invention. In sequence 405, the master key 105 is first passed to the secure hash algorithm 110. The result of the secure hash algorithm 110 is then used as an input to the universal hash algorithm 305, and from this result, the derived key 115-1 may be generated.

Although sequence 405 shows the secure hash algorithm 110 being used before the universal hash algorithm 305, sequence 410 reverses this order. Thus, the master key 105 serves as an input to the universal hash algorithm 305. The result of the universal hashing algorithm 305 is then used as input to the secure hashing algorithm 110, from which a derived key 115-1 may be generated.

The secure hash algorithm 110 and the universal hash algorithm 305 may be implemented in any desired form. For example, the secure hash algorithm 110 and the universal hash algorithm 305 may be implemented in any kind of read-only memory (RAM), in firmware, or as software stored in memory, which are a few examples of the secure hash algorithm 110 and the universal hash algorithm 305 being implemented in a general purpose processor. Implementations may also include special purpose devices: for example, the processor may be specially designed to implement the secure hash algorithm 110 and the universal hash algorithm 305. Thus, as another example, a calculator may be designed to implement the secure hash algorithm 110 or the universal hash algorithm 305. Those skilled in the art will recognize other ways in which the secure hash algorithm 110 and the universal hash algorithm 305 may be implemented.

Fig. 5 shows a server and a device capable of performing data transformation, key generation, key wrapping and data encryption according to an embodiment of the present invention. The server 505 is shown in fig. 5. Server 505 includes data transformer 510, key derivation function 515, key wrapping function 520, and encryption function 525. The data transformer 510 is responsible for performing data transformation. As discussed below with reference to fig. 8-9, 10A-10C, and 11, when an otherwise unsafe condition exists, the data transformation increases the complexity of the encoded data by scrambling the data, thus making cryptanalysis more difficult. For example, data transforms can mask patterns that exist in the encoded data but not in the transformed data.

Key derivation function 515 is responsible for deriving keys for encrypting data. While any key may be used to encrypt data, the more a particular key is used, the more likely it is that the key is to be determined by cryptanalysis. Thus, some systems rely on a master key to generate a derived key, which is then used to encrypt data. As often desired, a new derived key may be generated; any data encrypted with only the derived key has no value for the hacking of the information encrypted with the new derived key. Existing key derivation features exist; three new key derivation features will be described below with reference to fig. 12-13 and 15-16.

Key wrapping function 520 is responsible for wrapping keys for transmission. Key wrapping is typically accomplished by encrypting the key for transmission. For example, RSA can be used to encrypt (i.e., wrap) keys. The now fully protected key can be transferred to other machines even over an insecure connection where it can be unpacked (decrypted) and used for data encryption/decryption.

Often, the wrapped key is a key used with a private key (or symmetric) cryptographic system, which is wrapped with a public key (or asymmetric) cryptographic system. Private key cryptosystems use the same key for encryption and decryption, as opposed to public key cryptosystems that use different keys for encryption and decryption. For example, DES and AES are private key cryptosystems; RSA is a public key cryptosystem. While public key cryptosystems make it possible to distribute keys securely (without fear that the keys are intercepted by third parties and used to decrypt secret information), public key cryptosystems are often slower to implement and result in longer messages than private key cryptosystems. Obviously, to use a public key cryptography system to wrap a key, the server 505 needs to know the public key of the device to which the wrapped key is to be delivered. Those skilled in the art will recognize that any encryption algorithm may be used to wrap the key, and that the key to be wrapped may be used in any type of cryptographic system.

Encryption function 525 is used to encrypt data. Typically, the data is encrypted using a key wrapped using key wrapping function 520, although one skilled in the art will recognize that any key may be used to encrypt the data, and that the data may be any data desired to be encrypted, and that any desired encryption function may be used.

Fig. 5 also shows an apparatus 530 capable of performing data transformation, key wrapping, and data encryption in accordance with an embodiment of the present invention. Although the device 530 appears like a Personal Digital Assistant (PDA), those skilled in the art will recognize that the device 530, and thus the server 505, may be any device that uses a security algorithm. Thus, for example, the device 530 may be a computer (e.g., a desktop computer or a notebook computer) that exchanges files with the server 505 (which may be a general computer that is not a server in nature). Alternatively, device 530 may be a digital media device: for example, digital content is presented to the user, which is provided by the server 505 to the device 530. Alternatively, the device 530 may receive content from any legitimate source, from which the server 505 specifies the rights granted to the device 530. Alternatively, the device 530 may be software to implement some of the functionality stored in some medium for use with a general purpose machine (such as a computer). In this variation, the device 530 becomes part of the system shown in FIG. 5 because it relies less on the hardware of the device 530 and more on the software executed by the device 530. Those skilled in the art will recognize that the software may implement any desired functionality, and that the software may be stored on any suitable medium, such as a floppy disk, any type of Compact Disc (CD) or digital video disc (DVD, also sometimes called digital versatile disc), tape media, or a Universal Serial Bus (USB) key, to name just a few of the more popular possibilities. Alternatively, the device 530 may be a cellular telephone and the server 505 may be a base station, wherein the cellular telephone and the base station communicate in an encrypted manner. Those skilled in the art will recognize other variations of the device 530 and the server 505 and will also recognize that the manner of communication between the server 505 and the device 530 may be any form of communication channel: such as wired, wireless, or any other form of communication.

Device 530 is similar to server 505 in FIG. 5 in that it includes data transformer 510, key wrapping function 520, and encryption function 525. Note that device 530 does not include key derivation function 515, unlike server 505 in fig. 5. This is because key derivation is typically only required at the server 505. Given a way to communicate with another device, only one device needs to generate the derived key. Of course, if there is no way to securely transfer the derived key but both devices can accurately generate the same derived key, then device 530 may include key derivation function 515 (although key wrapping function 520 may not be needed for device 530).

Figure 6 shows a data security device for improving security using a data transformer in combination with a key wrapper, key deriver or encryption function, in accordance with one embodiment of the present invention. Data security appliance 605 may be part of server 505 or device 530 of fig. 5, with modifications to add or remove components as needed. In data security apparatus 605, input port 610 is responsible for receiving data. The data may be a master key (from which a derived key is generated), a key to be wrapped or data to be encrypted, etc. Partitioner 615 is responsible for partitioning data into blocks. As discussed below with reference to fig. 12-13 and 14-16, sometimes these features apply data transformations to portions of the data; the divider 615 splits the data into blocks of a desired size so that the data transformer 510 can be applied to each block. The data transformer 510 is responsible for performing data transformations, which will be discussed further below with reference to fig. 12-13 and 14-16. Combiner (combiner)620 is responsible for recombining the data blocks together after the data transformation for application of the appropriate security features. The various security features that may be used include a key derivation feature 515, a key wrapping feature 520, or an encryption feature 525. Finally, output port 625 outputs data after the security features are transformed and/or applied.

It is noted that while typically the segmenter 615 breaks the data into blocks of a size that conforms to the data transformation algorithm, this is not required. Thus, the partitioner 615 may break the data into blocks that are smaller or larger than the desired input to the data transformer 510. If divider 615 breaks the data into smaller blocks than expected by data transformer 510, the data can be padded (pad) large enough; if divider 615 splits the data into blocks larger than expected by data transformer 510, data transformer 510 may apply the data transform to only the number of bits in the data that are needed by the data transformer. For example, if the data transformer 510 is implemented as described in the embodiment of fig. 10, the data transformer 510 acts on an 8 byte input. If the data transformer 510 receives more than 8 bytes of data, the data transformer 510 may only apply to 8 bytes of the input. This can be any 8 bytes in the data: for example, the first 8 bytes, the last 8 bytes, or any other desired combination.

It is also noted that any data may be transformed. Thus, the data to be transformed may be a master key, wherein the transformed master key is to be used for generating the derived key. Alternatively, the data may be a derived key to be wrapped prior to transmission. Alternatively, the data may be data to be encrypted using an implementation of an encryption algorithm. Those skilled in the art will recognize other types of data that may be transformed.

Figures 7A-7B illustrate a flow diagram for using the data security device of figure 6 in accordance with one embodiment of the present invention. In fig. 7A, at block 705, data is partitioned into blocks. At block 710, each block is transformed using a data transform. Each block may be independently data transformed or not transformed as desired; in other words, some blocks may be transformed while others are not. At block 715, the blocks may be reassembled. As indicated by dashed line 720, blocks 705-715 are optional and may be skipped if not required.

In fig. 7B, the data security device may be used in different ways. At block 725, a key wrapping algorithm may be applied to the data. At block 730, a key derivation algorithm may be applied to the data. And at block 730, a data encryption algorithm may be applied to the data.

Fig. 8 shows details of the data transformer of fig. 5 and 6, in accordance with an embodiment of the present invention. In the embodiment of the data transformer 510 shown in fig. 8, the data transformer 510 operates by permuting the bit groups using a permutation function. The data transformer 510 includes: an input port 805 for receiving data to be transformed, a splitter 810, a padder (padder)815, a permuter 820, and an output port 825 for outputting transformed data. The divider 810 is responsible for dividing the input data into groups of bits for applying the permutation function. In fact, the partitioner 810 begins by dividing the data into two segments. The first segment includes bits for controlling application of the permutation function on the bit groups, the bits being partitioned from the second segment. In one embodiment, the data includes 64 bits; the first segment comprises 8 bits and the second segment comprises 8 groups of 7 bits. Those skilled in the art will recognize that the data may be of any length and that the data may be divided into groups of any desired length, even if the different groups are of different lengths. Finally, if an individual (individual) group is always to be permuted, the first segment (which includes the bits that control the application of the permutation group) may be omitted.

If data transformer 510 supports receiving data of unpredictable size (rather than assuming that the data is always a fixed size), divider 810 may not be able to properly divide the data into groups of bits.

The data may be padded with additional bits using a padding device 815 to make the data of the appropriate length to be properly partitioned.

In one embodiment, the application of the permutation function is controlled by the bits of the first segment: if the corresponding bit in the first segment is set (set), the group of bits is permuted using a particular permutation function. For example, if the value of the corresponding bit is 1, the corresponding group is permuted using an appropriate permutation function; if the value of the corresponding bit is 0, the corresponding group is not permuted. Alternatively, if the value of the corresponding bit is 0, the corresponding group of bits may be considered as having been permuted using an identity permutation function (identity permutation function). The permutation function may also be indexed; if the number of permutation functions matches the number of groups of bits in the second segment (and thus also the number of bits in the first segment), a single index may identify three corresponding cells (elements): a bit in the first segment, a group of bits in the second segment, and a permutation function to be applied to the group of bits.

The permuter 820 is responsible for controlling the permutation of the bit groups of the second segment. In one embodiment, the permuter 820 performs the permutation according to the functions shown in table 1 below, although one skilled in the art will recognize that any permutation function may be used.

TABLE 1

Function(s)	Substitution (of abcdefg)
		P1	faebdgc
P2	gfdabce
		P3	cgbfaed
P4	ecagfdb
		P5	defcgba
P6	bdgecaf
		P7	ecagfdb
P8	cgbfaed

The permutations shown in table 1 have some interesting characteristics. First, each permutation function is a permutation function P₁To the power of (c). Thus, P₂＝P₁○P₁，P₃＝P₂○P₁(＝P₁○P₁○P₁) And so on. Because of P₆○P₁Will again result in P₁So that P is₇And P₈Is selected to repeat the previous P₁To the power of (c). This means that the data transformer 510 only needs to know the implementation of one permutation function; the remaining permutation functions may be derived from the base permutation function. Secondly, the first step is to carry out the first,the permutations of table 1 do not introduce any structure in the data similar to that found in encryption functions such as RAS, DES, AES, SHA-1.

Because the permutation function is invertible, the data transformation resulting from applying the permutation function using table 1 is easily invertible. The permutation functions shown in table 2 are the inverses (inverses) of the permutation functions of table 1.

TABLE 2

Function(s)	Substitution (of abcdefg)
		P1 -1	bdgecaf
P2 -1	defcgba
		P3 -1	ecagfdb
P4 -1	cgbfaed
		P5 -1	gfdabce
P6 -1	faebdgc
		P7 -1	cgbfaed
P8 -1	ecagfdb

Thus, to reverse the data transformation applied to the permutation function of Table 1, all that needs to be done is to apply the second data transformation using the permutation function of Table 2. To make this inverse transformation possible, the output port 825 outputs the bits of the first segment directly along with the permuted group; otherwise, the receiver of the transformed data will not know which bit group has been permuted.

Just like the permutation functions of table 1, all permutation functions in table 2 can be derived from a single basis function: in this case P₆ ^-1. Thus, P₅ ^-1＝P₆ ^-1○P₆ ^-1，P₄ ^-1＝P₅ ^-1○P₆ ^-1(＝P₆ ^-1○P₆ ^-1○P₆ ^-1) And so on.

Fig. 9 shows details of the data transformer of fig. 5 and 6 according to another embodiment of the present invention. In fig. 9, the operation of the input port 905 and the output port 910 is similar to the data converter 510 in fig. 8. The data transformer 510 in fig. 9 does not permute the data using a permutation function, but operates by computing an exponential permutation on the data: this calculation is performed by calculator 915. In one embodiment, data transformer 510 acts on a 3 byte long data input. The first segment is used to calculate the power to which the last two bytes are raised. The result is then modulo by one. For example, one embodiment calculates the data transformation as Y ═ ((B +1)^(2A+1)mod 65537) -1, where A is theThe first byte of the data input, B is the last two bytes of the data input. The transformed data then includes a and Y and is 3 bytes long. Those skilled in the art will recognize that the inputs may be of different lengths and that different exponential permutation functions may be applied.

The exponential permutation function shown above has several advantages. First, abstract algebra shows that when an exponent is relatively prime to a modulus (minus 1), the function cycles through all possible values between 1 and the modulus, which means that the exponent permutation function is a permutation. By selecting 65537 as the prime number, one that is 1 less than 65537 is 65536, which is a power of 2. Therefore, regardless of the value of a, (2A +1) is odd and therefore interdependent with 65536. Second, if A is 0, the data output is unchanged. Finally, like the permuted data transformer of FIG. 8, the structure of the data transformer 510 of FIG. 9 uses structures not found in encryption algorithms such as RSA, DES, AES, SHA-1, etc.

If data transformer 510 supports receiving data of unpredictable size (rather than assuming that the data is always a fixed size), then divider 920 may not be able to divide the data into appropriately sized segments. Like the padder 815 in the data transformer of fig. 8, the padder 925 may be used to pad the data with additional bits so that the data has the appropriate length to be properly divided.

Like the permuted data transformer of fig. 8, the data transformer 510 of fig. 9 is reversible. To enable the inversion of this data transformation, output port 910 outputs a constant a along with Y. Then, to invert the exponential permutation, calculator 915 calculates the inverse of 2A +1 modulo 65536 (i.e., 65537-1). If the e is called reversely, the inverted index is replaced by ((Y +1)^emod 65537) -1. The result of this calculation restores the original byte B. In this way, by applying the second data transformation, changing the exponent of the data transformer, the exponent permutation can be easily reversed.

Now that the devices of fig. 8 and 9 have been shown, their method of use can be understood. Fig. 10A-10C show a flow chart for using the data transformer of fig. 8 according to an embodiment of the present invention. In fig. 10A, data is received at block 1005. At block 1010, the data is partitioned into two segments (assuming that the permutation of the bit groups is controlled by the bits in the first segment). At block 1015, the data transformer checks whether the second data segment can be uniformly divided into groups. If not, the data is padded to support the splitting of the second segment into uniformly sized groups at block 1020. (this assumes that the data transformer attempts to partition the data input into uniformly sized groups; blocks 1015 and 1020 may be omitted if the data transformer does not need to partition the input data into uniformly sized groups.)

At block 1025 (FIG. 10B), the second segment is partitioned into groups of bits. Although block 1025 describes the second segment being partitioned into equal sized groups, as described above, these groups may also be partitioned into unequal sized groups if supported by the data transformer. At block 1030, each group is associated with one bit in the first segment. At block 1035, a basic permutation function is defined. At block 1040, other permutation functions are defined as powers of the base permutation function. (again, the permutations are not required to be power of the basic permutation function; each permutation function may be unrelated to the other permutation functions, in which case blocks 1035 and 1040 may be altered/omitted.) at block 1045, the permutation functions are indexed.

At block 1050 (FIG. 10C), the data transformer checks whether there are bits remaining to be checked in the first segment (which controls the application of the permutation function to the set of bits in the second segment). If there is an unchecked bit, the data transformer checks if the bit is set, block 1055. If the bit is set, at block 1060 the permutation function indexed by the bit is identified, and at block 1065 the identified permutation is applied to the associated permutation group. Control then returns to block 1050 to check whether there are any more unchecked bits in the first segment. After all bits in the first segment have been examined, the data transformer constructs a data transform from the first segment and the permuted group of bits, at block 1070.

Fig. 11 shows a flow diagram for using the data transformer of fig. 9, in accordance with an embodiment of the present invention. At block 1105, the data transformer receives data. At block 1110, the data transformer splits the data into two pieces. At block 1115, the first segment is used to construct a power of the modulus that is relatively prime to the selected modulus. At block 1120, the second segment is raised to the calculated power. At block 1125, the remainder is computed by modulo the result by the modulus. Finally, at block 1130, a data transform is constructed from the first segment and the remainder.

As described above with reference to fig. 5, existing key derivation features exist. However, as described above with reference to fig. 4, existing key derivation features do not provide the advantages of both secure and universal hash functions. Figure 12 shows details of a key derivation function that combines the advantages of both secure and universal hash functions. In fig. 12, the key derivation function 515 includes an input port 1205 and an output port 1210 for providing input to the key derivation function and the derived key output, respectively. The key derivation function 515 further includes a splitter 1215, a combiner 1220, a hashing device (hash)1225, a determiner 1230, a calculator 1235, and a bit selector 1240.

A splitter 1215 splits the master key into two parts. The combiner combines the first part of the master key with a counter, which may be part of the input data. One way to combine the master key with the counter is to concatenate the first part of the master key with a counter, which may be of any size (e.g., 4 bytes). This joining may be performed in either order: that is, either the first part of the master key or the counter may be in front of the combination. The combined result is then scrambled using a hash function 1225, which may be a secure hash function. (in this embodiment, the hash function 1225 replaces the secure hash algorithm 110 in the sequence 405 of FIG. 4.)

Arbiter 1230 is used to determine two digits from the second part of the master key. In one embodiment, the two numbers, a and b, are determined as the first and last 32 bytes of the second portion of the master key, modulo a prime number p. Selecting a and b in this manner requires that the master key be of sufficient length to enable the second part of the master key to be 64 bytes long. Those skilled in the art will recognize that the master key need not be so long. For example, if computing a and b changes the bits of a and b sufficiently modulo p, a and b may be selected in such a way that: i.e. their original bits overlap in the second part of the master key.

One particular choice for the prime number may be P₁₉₂＝2¹⁹²-2⁶⁴-1, although one skilled in the art will recognize that other prime numbers may be selected. The calculator 1235 may then implement a universal hash function ax + bmod, where x is the result of the hashing device 1225. (this universal hash function replaces the universal hash algorithm 305 in the sequence 405 of FIG. 4). Finally, bit selector 1240 selects bits for the derived key from the result of the universal hash function, which bits may then be output. For example, the bit selector 1240 may select the least significant bits (the least significant bits) of the result of the universal hash function as the derived key.

Fig. 13 shows details of the key derivation function of fig. 5 and 6, in accordance with another embodiment of the present invention. In contrast to the embodiment of the invention shown in fig. 12, which implements the key derivation function in accordance with sequence 405 of fig. 4, key derivation function 515 of fig. 13 does not apply the universal hash algorithm after the secure hash algorithm. Instead, the embodiment of the invention shown in FIG. 13 applies a linear mapping to the input to the secure hash algorithm.

Like key derivation function 515 of fig. 12, key derivation function 515 of fig. 13 includes an input port 1305 and an output port 1310 that receive a master key as an input and output a derived key, respectively. Key derivation function 515 of fig. 13 further includes divider 1315, encoder 1320, combiner 1325, hashing device 1330, and bit selector 1335.

Divider 1315 divides the master key into two parts, just like divider 1215 of fig. 12. Encoder 1320 then encodes a counter. Encoder 1320 may operate in any desired manner. For example, encoder 1320 may operate by repeating the counter to extend it to the length of the first portion of the master key. Thus, for example, if the first portion of the master key is 64 bytes long and the counter is represented by 4 bytes, the encoder 1320 can repeat these 4 bytes 16 times to extend the counter to 64 bytes long. The combiner 1325 may then combine the encoded counter with each portion of the master key separately. For example, the combiner 1325 may combine these portions of the master key with the encoded counter at the bit level. One embodiment uses an XOR binary function (binary function) to combine these portions of the master key with the encoded counter. Those skilled in the art will recognize that the combiner 1325 may use any bitwise binary function (bitwise binary function), or indeed any function, to combine these portions of the master key with the encoded counter. The combiner 1325 then recombines these two parts of the master key together (after combination with the encoded counter): for example, the two parts may be joined together (although those skilled in the art will recognize that combiner 1325 may otherwise recombine the two parts of the master key). The combiner 1325 may also join the recombined part of the master key with the encoded counter again.

The hash device 1330 takes the output of the combiner 1325 and shuffles it. The hashing means 1330 may be a secure hash function. Just like bit selector 1240 in fig. 12, bit selector 1335 may then select bits from the results of hashing device 1330 as the derived key.

Now that the devices of fig. 12 and 13 have been shown, their method of use can be understood. Fig. 14 shows a flow diagram for using the key derivation function of fig. 12 in accordance with one embodiment of the present invention. At block 1405, the master key is partitioned into segments. At block 1410, the first segment is combined with the encoded counter. This combination may be the engagement of the first segment with the encoded counter, as described above with reference to fig. 12. At block 1415, the first segment of the combination is shuffled.

At block 1420, two numbers are determined from the second segment. These two numbers may be determined relative to a modulus, as described above with reference to fig. 12. At block 1425, a universal hash function is defined using the determined two numbers and the modulus. At block 1430, the result of the hash is applied to the universal hash function. At block 1435, bits are selected from the result of the universal hash as the derived key.

Fig. 15 shows a flow diagram for using the key derivation function of fig. 13 in accordance with one embodiment of the present invention. At block 1505, the master key is partitioned into segments. At block 1510, each segment is combined with an encoded counter. This may be accomplished by applying an XOR bit function to each segment of the counter, each with an encoding, as described above with reference to fig. 13. At block 1515, the combined blocks are recombined and may be (as described above with reference to FIG. 13) recombined with the encoded counter. At block 1520, the modified master key is scrambled, and at block 1525, bits are selected from the result of the scrambling as the derived key.

The key derivation functions shown in fig. 12-15 are but two examples. Other key derivation features that combine the advantages of a secure hash algorithm with a universal hash algorithm may also be used. Fig. 16 shows a flow diagram of another key derivation function for use in the data security apparatus of fig. 5, in accordance with an embodiment of the present invention. At block 1605, the master key is partitioned into segments. At block 1610, the segments are transformed using a data transform. Because these segments are typically larger than the data transformer can use, only a subset of these segments are used: for example, only the first bytes needed for the data transformation are used. At block 1615, the transformed segments are combined and combined with the encoded counters: for example, the segments and the encoded counter may be concatenated together. The result is scrambled at block 1620, and bits are selected from the scrambled result as the derived key at block 1625.

While the devices of fig. 12-13 and the flow diagrams of fig. 14-16 show the generation of a single derived key from a master key, it is worth noting that embodiments of the present invention can be readily adapted to generate duplicate derived keys. These additional derived keys may be generated in a variety of ways. For example, the flow diagrams of FIGS. 14-16 all include counters. The counter may be incremented for each desired additional derived key. Thus, to derive the first key, the counter may use the value 1, to derive the second key, the counter may use the value 2, and so on.

In another variation, instead of using bit selector 1240 of fig. 12 or bit selector 1335 of fig. 13 to select bits for deriving keys, enough results are generated at a time to select bits from the combined results for all derived keys. For example, assume that u keys are expected, each k bits long, and further assume that the apparatus of fig. 12-13 and/or the results of the flow diagrams of fig. 14-16 produce l bits prior to bit selection. If the key derivation function is applied m times such that m x l ≧ u x k, u derived keys can be simultaneously selected from m x l result bits. For example, m × l result bits may all be spliced together; the first key may be selected as the first k bits, the second key may be selected as the second k bits, and so on until all u keys have been selected.

The following discussion is intended to provide a brief, general description of a suitable machine in which some aspects of the present invention may be implemented. Typically, the machine includes a system bus to which are attached: a processor, memory (such as Random Access Memory (RAM), Read Only Memory (ROM), or other state preserving medium), storage, a video interface, and input/output interface ports. The machine may be controlled, at least in part, by: interact with a Virtual Reality (VR) environment, biometric feedback, or other input signals through input from conventional input devices, such as a keyboard, mouse, etc., as well as through directives received from another machine. The term "machine" as used herein is intended to broadly encompass a single machine, or a system of communicatively coupled machines or devices operating together. Examples of machines include computing devices (such as personal computers, workstations, servers, portable computers, handheld devices, telephones, tablets, etc.), and transportation devices (such as personal or public transportation devices, e.g., cars, trains, taxis, etc.).

The machine may include embedded controllers, such as programmable or non-programmable logic devices or arrays, application specific integrated circuits, embedded computers, smart cards, and the like. The machine may reach one or more remote machines using one or more connections, such as through a network interface, modem, or other communication connection. The machines may be interconnected by means of a physical and/or logical network, such as an intranet, the internet, a local area network, a wide area network, etc. Those skilled in the art will recognize that network communications may utilize a variety of wired and/or wireless short or long range carriers and protocols, including Radio Frequency (RF), satellite, microwave, IEEE (institute of electrical and electronics engineers) 802.11, bluetooth, optical, infrared, cable, laser, and so forth.

The invention may be described with reference to or in conjunction with associated data (including functions, procedures, data structures, application programs, etc.) that, when accessed by a machine, cause the machine to perform tasks or define abstract data types or low-level hardware contexts. The associated data may be stored, for example, in volatile and/or non-volatile memory (e.g., RAM, ROM, etc.) or in other storage devices and their associated storage media (including hard disks, floppy disks, optical storage, tapes, flash memory, memory sticks, digital video disks, biological memory, etc.). The associated data may also be transmitted over transmission environments (including physical and/or logical networks) in the form of packets, serial data, parallel data, propagated signals, etc., and may be used in compressed or encrypted form. The association data may be used in a distributed environment and stored locally or remotely for machine access.

While the principles of the invention have been described and illustrated with reference to the illustrated embodiments, it should be recognized that the illustrated embodiments can be modified in arrangement and detail without departing from such principles of the invention. And while the above discussion has focused on particular embodiments, other configurations are also contemplated. In particular, although expressions such as "in one embodiment" or the like have been used herein, these expressions refer to embodiment possibilities generally and are not intended to limit the invention to the configuration of the particular embodiment. These expressions as used herein may refer to the same or different embodiments, which may be combined with other embodiments.

Thus, in view of the wide variety of variations of the embodiments described herein, this detailed description and the accompanying materials are intended to be illustrative only and should not be taken as limiting the scope of the invention. What is claimed, therefore, is all such modifications as may come within the scope and spirit of the following claims and equivalents thereto.

Claims (36)

1. A data transformer comprising:

an input port for receiving data;

a divider for dividing the data into a first segment and a second segment and dividing the second segment into at least two groups;

a permuter including an implementation of at least two permutation functions to permute at least one of said groups into permuted groups according to corresponding bits in said first segment; and

an output port for outputting the first segment and at least the permuted group as transformed data,

wherein one of the at least two permutation functions is a base permutation function and each remaining permutation function is a power of the base permutation function.

2. The data transformer of claim 1, wherein the divider is operative to divide the second segment into groups such that the number of groups in the second segment is equal to the number of bits in the first segment.

3. The data transformer of claim 1, wherein the divider is operative to divide the second segment into the groups, each of the groups having a predetermined size.

4. A data transformer as claimed in claim 3, wherein said divider comprises a padding for padding said second segments so that each of said groups has said predetermined size.

5. The data transformer of claim 1, wherein a number of permutation functions is equal to a number of the groups in the second segment.

6. The data transformer of claim 5, wherein the permuter is operative to permute each of the groups using one of the permutation functions according to the corresponding bit in the first segment.

7. A data security device comprising:

a data transformer, comprising:

an input port for receiving data;

a divider for dividing the data into a first segment and a second segment and dividing the second segment into at least two groups, each group having a predetermined size such that the number of groups in the second segment is equal to the number of bits in the first segment;

a permuter including an implementation of at least two permutation functions to permute at least one of said groups into permuted groups according to corresponding bits in said first segment; and

an output port for outputting the first segment and at least the permuted group as transformed data; and

an implementation module of a security algorithm for protecting said transformed data,

wherein one of the at least two permutation functions is a base permutation function and each remaining permutation function is a power of the base permutation function.

8. The data security device of claim 7, wherein:

the data includes a master key; and

the implementation module of the security algorithm comprises an implementation module of a key derivation function to generate a derived key of the master key using the transformed data.

9. The data security device of claim 7, wherein:

the data comprises a key to be wrapped; and

the implementation module of the security algorithm includes an implementation module of a key wrapping function to wrap the transformed data.

10. The data security device of claim 9, wherein the implementation module of the key wrapper function comprises an implementation module of RSA to wrap the transformed data.

11. The data security device of claim 7, wherein the implementation module of the security algorithm comprises an implementation module of an encryption algorithm to encrypt the data using the transformed data.

12. The data security device of claim 11, wherein the implementation module of the security algorithm comprises an implementation module of AES to encrypt the data using the transformed data.

13. A data security device according to claim 7, further comprising a second divider to divide the input into at least two blocks, the data transformer acting on each block separately.

14. A data security device according to claim 13, further comprising a combiner to combine the results of the data transformer for each block into a single transformed data to be protected by the implementation module of the security algorithm.

15. The data security device of claim 7, wherein the permuter includes a module for implementing a number of permutation functions equal to the number of groups in the second segment.

16. The data security device of claim 15, wherein the permuter is operative to permute each of the groups using one of the permutation functions according to the corresponding bit in the first segment.

17. A method for generating a data transformation, comprising:

receiving data;

partitioning the data into a first segment and a second segment, each of the first and second segments comprising at least one bit;

dividing the second segment into at least two groups;

associating each of the groups with a bit in the first segment;

applying a permutation function to at least one of the groups according to the associated bits in the first segment, wherein the permutation function is selected from at least two permutation functions, one of the at least two permutation functions being a basic permutation function, and each remaining permutation function being a power of the basic permutation function; and

constructing the data transformation from the first segment and at least the permuted group.

18. The method of claim 17, wherein partitioning the second segment into at least two groups comprises: the second segment is partitioned into a number of groups equal to the number of bits in the first segment.

19. The method of claim 17, wherein partitioning the second segment into at least two groups comprises: the second segment is partitioned into at least two groups, each group having the same number of bits.

20. The method of claim 19, wherein partitioning the second segment into at least two groups comprises: padding data to enable said second segment to be partitioned into said groups, each of said groups comprising the same number of bits.

21. The method of claim 17, further comprising defining the permutation function.

22. The method of claim 21, wherein defining the permutation function comprises: a number of permutation functions is defined, the number of permutation functions being equal to the number of groups.

23. The method of claim 22, wherein applying a permutation function to at least one of the groups comprises: applying a different permutation function to each of the groups according to the corresponding bit in the first segment.

24. The method of claim 23, wherein:

defining a plurality of permutation functions includes assigning an index to each of the permutation functions; and

applying a different permutation function to each of the groups includes selecting a permutation function with the index, the index corresponding to a number for the bits associated with the group in the first segment.

25. A method for enhancing data security, comprising:

generating a data transformation comprising:

receiving data;

partitioning the data into a first segment and a second segment, each of the first and second segments comprising at least one bit;

partitioning the second segment into a number of groups equal to the number of bits in the first segment;

associating each of the groups with a bit in the first segment;

applying a permutation function to at least one of the groups according to the associated bits in the first segment, wherein the permutation function is selected from at least two permutation functions, one of the at least two permutation functions being a basic permutation function, and each remaining permutation function being a power of the basic permutation function; and

constructing the data transformation from the first segment and at least the permuted group; and applying a security algorithm to the data transformation to protect the data transformation.

26. The method of claim 25, wherein:

receiving data includes receiving a master key from which derived keys are generated; and

applying a security algorithm to the data transformation includes applying a key derivation function to the data transformation to generate the derived key for the master key.

27. The method of claim 26, wherein applying a key derivation function to the data transformation comprises:

combining the transformed data with an encoded counter to produce a combined result;

securely obfuscating the combined result to produce a hash; and

a subset of bits is selected in the hash as the derived key.

28. The method of claim 26, wherein:

generating the data transformation further comprises combining the master key with a counter to produce transformed data; and

applying a key derivation function to the data transformation comprises:

securely obfuscating the transformed data to produce a hash; and

a subset of bits is selected in the hash as the derived key.

29. The method of claim 25, wherein:

receiving data comprises receiving a key to be wrapped as the data; and

applying a security algorithm to the data transformation includes applying a key wrapping function to the data transformation to wrap the key.

30. The method of claim 29, wherein applying a key wrapping function to the data transformation comprises applying RSA to the data transformation to wrap the key.

31. The method of claim 25, wherein applying a security algorithm to the data transformation comprises applying an encryption algorithm to the data transformation to encrypt the data using the data transformation as a key.

32. The method of claim 31, wherein applying an encryption algorithm to the data transform comprises applying AES to the data transform to use the data transform as the key to encrypt the data.

33. The method of claim 25, wherein partitioning the second segment into a plurality of groups comprises: the second segment is partitioned into a number of groups equal to the number of bits in the first segment, each group having the same number of bits.

34. The method of claim 25, further comprising defining the permutation function.

35. The method of claim 34, wherein defining the permutation function comprises defining a number of permutation functions, the number of permutation functions being equal to the number of groups.

36. The method of claim 25, further comprising:

dividing an input into at least two blocks, and respectively converting each block; and

combining the results of the data transformation for each block into a single transformed data to be protected by applying the security algorithm.