Encryption technique using stream cipher and block cipher

[0002] This application relates to the following commonly assigned, concurrently filed U.S. patent application:

[0003] Ser. No. 09/203,236 invented by Charles M. Doland entitled “METHOD AND APPARATUS FOR DETECTING ALTERATIONS IN DATA MESSAGES”, which is incorporated herein by reference.

[0004] The present invention relates generally to the field of message encryption and more particularly to the field of pseudo-random sequence generation for message encryption.

[0005] A wide area network such as the Internet may connect thousands of network nodes, including routers, bridges, hubs, servers, and user terminals. In transmitting a message from a sender node to a receiver node over a wide area network, security is a great concern, because messages in transmission are susceptible to interception by unintended third parties at any network node. This problem is typically addressed by encrypting a private message at the sender node prior to transmission of the message, then decrypting the message at the receiver node. Encryption refers to a process of disguising a message sent from a sender node so that an unintended third party cannot recover the meaning of the message, even if the unintended third party has intercepted the message. Decryption refers to a process of recovering an encrypted message after an intended receiver node has received the encrypted message. For a receiver to recover an encrypted message received from a sender, the sender and the receiver must both agree on a predetermined encryption and decryption system.

[0006] An encryption and decryption system can be conveniently described using the following notations, where:

[0007] (1) a plain (not encrypted) message is denoted by P;

[0008] (2) an encryption transformation function is denoted by E;

[0009] (3) an encrypted message is denoted by C, where C=E(P);

[0010] (4) a decryption transformation is denoted by D; and

[0011] (5) a decrypted message is also denoted by P, where P=D(E(P)).

[0012] Note that a decrypted message has the same notation as a plain message, because decrypting an encrypted message returns the original, unencrypted message.

[0013] To enhance security, most modern encryption systems use an encryption key, denoted by K_e, to encrypt messages prior to transmitting the messages, and a decryption key, denoted by K_d, to decrypt the messages upon receiving the messages. (The decryption key is often transmitted to the receiver node using a secure communication channel, to improve the security of the message, which can then be sent over an insecure channel.) In the available art, there are two general forms of key-based encryption and decryption systems: symmetric-key and public-key. In symmetric-key systems, the encryption key can be calculated from the decryption key and vice versa. Since in many such systems the encryption key K_eand the decryption key K_dare the same, the encryption key and the decryption key can be denoted by K. Thus, a symmetric encryption and decryption system can be described using the following notations, where:

[0014] (6) a plain message is denoted by P;

[0015] (7) a symmetric key is denoted by K;

[0016] (8) an encryption transformation is denoted by E_K;

[0017] (9) an encrypted message is denoted by C, where C=E_K(P);

[0018] (10) a decryption transformation is denoted by D_K; and

[0019] (11) a decrypted message is also denoted by P, where P=D_K(E_K(P)).

[0020] A simple exemplary symmetrical transformation between a sender and a receiver is the XOR logic operation. In this transformation, the plain message is “XORed” bit by bit with the key to generate an encrypted message. To regenerate the message at the receiver node, the encrypted message is once again XORed with the key. This series of operations reproduces the original message. Using the XOR logic operation, a symmetric-key encryption and decryption process can be described as follows:

[0021] E_K(x)=x XOR K;  (12)

[0022] D_K(x)=x XOR K;  (13)

[0023] C=E_K(P)=P XOR K;  (14)

[0024] and

[0025] P=D_K(C)=C XOR K=(P XOR K)XOR K.  (15)

[0026] Symmetric encryption and decryption systems are divided into two categories: stream ciphers and block ciphers. A cipher refers to a mathematical function (such as XOR) used for encryption and decryption. In a stream cipher, a message is encrypted one bit at a time. In a block cipher, a message is encrypted a block at a time.

[0027] In real world applications, encrypted messages are subject to attack, a process of recovering the encrypted messages without being informed about the encryption algorithm or the encryption key. The security of an encryption system against attack typically depends on two elements: the strength of the encryption algorithm selected and the length of the key used.

[0028] Usually, a more secure encryption algorithm is more complicated than a less secure encryption algorithm. Consequently, greater expense and time are required to attack a more secure encryption algorithm. However, often more time and computing power are also required to perform the encryption and decryption using a more secure encryption algorithm. In some commercial settings, such costs are not necessary or feasible. By way of example, a consumer may use a desktop computer at home to conduct a real-time business transaction. The consumer's desktop computer may not have the computing power to perform a complicated encryption and decryption at such high speed. Further, if the amount of the business transaction is less than $1,000.00, an attacking cost above $1,000.00 will make the attack non-advantageous. As another example, some messages are only confidential for a short period of time, e.g., two months. A simple encryption algorithm is sufficient for such messages, if the attacking time takes more than two months. However, selecting a simple encryption algorithm leaves a user more vulnerable to attack than selecting a more complicated encryption algorithm.

[0029] The bit length of the key also affects the security of an encryption system. Any key-based encryption method is susceptible to a “brute force” attack. A brute force attack attempts to decrypt a message by applying the decryption function to the message, using each of the possible keys. To be secure against this type of attack, there must be a sufficient number of possible keys to make the attack too time-consuming to be useful. If a key is represented as a binary integer, the number of possible keys is 2ⁿ, where n is the number of bits in the key. Thus, in general, longer keys provide greater security against a brute force attack. For any given encryption method, there may be other methods of attacking or breaking the encryption, as well.

[0030] The choice between simple and complicated encryption algorithms presents a dilemma. While it is desirable to use simple encryption algorithms to suit some business transaction settings, selecting a simple encryption algorithm leaves an encrypted message vulnerable to attack. Similarly, increasing a key bit length increases the number of possible keys, thus enhancing the security of a encrypted message.

[0031] Therefore, there is a need to provide a method of encrypting messages adaptable to using a relatively simple encryption algorithm without compromising the security of encryption.

[0032] The present invention provides a novel method of generating a pseudo-random sequence of integers, and applies the method to the encryption of messages. The method uses a key K and a pair of prime numbers p and q, where q=2p+1. Specifically, a sequence of integers z(i), i=1, 2, . . . , n, is generated as follows.

[0033] y(i)=Kⁱmod q  (16)

[0034] z(i)=y(i), if y(i)≦p  (17)

[0035] z(i)=q−y(i), if y(i)>p  (18)

[0036] According to a first aspect of the invention, the sequence of integers is used to generate a stream cipher. Specifically, a sequence of integers z(i) is formed according to equations (16)-(18), where i=1, 2, . . . , n. A sequence of bits b(i) is then formed from integers z(i), for example by selecting the least significant (or most significant) bit from each value z(i). The sequence of bits b(i) is then used to encrypt a message using a selected encryption algorithm such as the XOR algorithm. In another embodiment, the sequence of integers is used to encrypt the message without generating a sequence of b(i).

[0037] According to a second aspect of the invention, the pseudo-random sequence of integers is used to generate a block cipher. A sequence of bits b(i) is formed from integers z(i) as in the previously described embodiment. However, in this embodiment the sequence of bits b(i) is then used to encrypt a message by performing a bit position permutation on one or more message blocks.

[0038] According to a third aspect, the sequence of bits b(i) is used to encrypt a message by performing a bit pattern permutation on one or more message blocks.

[0039] According to a fourth aspect of the invention, a message block is divided into sub-blocks. The message block is encrypted by alternately applying a bit position permutation to the entire message block and applying a bit pattern permutation to each of the sub-blocks. In another embodiment, other (non-alternating) patterns of permutations are applied.

[0040] The present invention is illustrated by way of example, and not by way of limitation, in the following figures, in which like reference numerals refer to similar elements.

[0041] FIG. 1. illustrates a memory storing an array A and how it is used to perform a bit position permutation (i.e., a type 1 transformation), in accordance with one embodiment of the present invention.

[0042] FIG. 2. illustrates a memory storing an array V and how it is used to perform an inversion of the bit position permutation shown in FIG. 1.

[0043] FIG. 3. illustrates a memory storing array A and how it is used to perform a bit pattern permutation (i.e., a type 2 transformation), in accordance with one embodiment of the present invention.

[0044] FIG. 4. illustrates a memory storing array V and how it is used to perform an inversion of the bit pattern permutation shown in FIG. 3.

[0045] FIG. 5 illustrates an exemplary encryption process including alternate application of bit position and bit pattern permutations (type 1 and type 2 transformations), in accordance with one embodiment of the present invention.

[0046] FIGS. 6-8 illustrate a process of generating a pseudo-random string of bits to encrypt messages, in accordance with one embodiment of the invention.

[0047] FIGS. 9A-9J illustrate a process of generating permutation index values, in accordance with one embodiment of the invention.

[0048] FIG. 10 is a flowchart illustrating the steps of encrypting a message or message block, in accordance with one embodiment of the invention.

[0049] The present invention provides a novel method for deriving a pseudo-random sequence of integers from a key K and a pair of prime numbers p and q, where q=2p+1, and applies the method to the encryption and decryption of messages. A sequence Z of n integers z(i), i=1, 2, . . . , n, is created based on the following equations.

[0050] y(i)=Kⁱmod q  (19)

[0051] z(i)=y(i), if y(i)≦p  (20)

[0052] z(i)=q−y(i), if y(i)>p  (21)

[0053] In the equations herein, a superscript represents exponentiation, and “mod” represents the modulus or remainder operation. The value z(i) is the ith integer in the sequence Z of values z(i).

[0054] Sequence Z is a sequence of integers that repeats with period T. Further, values z(i) are unique within any one period. Since the values of z(i) are distinct within a period, they provide outstanding material for reliable encryption. It should be appreciated that the repeating period T of sequence Z depends on the value of p, and not on the bit length of key K. Therefore, the present invention potentially provides (depending on the value of p) a selected encryption algorithm with a level of security significantly higher than current schemes based on key bit length.

[0055] The present invention provides two applications for the sequence of integers denoted by equations (19)-(21): a stream cipher and a symmetric block cipher. Exemplary embodiments are described for each type of cipher.

[0056] Stream Ciphers

[0057] A stream cipher is a symmetric encryption system in which a single key K is used to both encrypt and decrypt a message stream. Stream ciphers often use a key to generate a sequence of bits that is used to encrypt the message. For example, let P be the plain text of a message with n bits, where P(i) represents the i^thbit of the message for i=1, 2, . . . , n. Let B_Kbe a sequence of bits generated by the encryption algorithm when key K is used, where b_K(i) represents the i^thbit in the sequence. (This sequence of bits B_Kis generated independently of the message. Therefore, the sequence of bits can be generated without the message; however, the key K is of course required.) C denotes the encrypted text of the message, where C(i) represents the i^thbit in the encrypted message, and C(i)=P(i) XOR b_K(i). (XOR is the exclusive OR operation.)

[0058] A recipient of the encrypted message C can recover the plain text P of the message provided that he or she has the key K. First, the recipient generates the sequence of bits B_Kfrom the key K. Then, each plain text bit P(i) is generated as follows: $\begin{array}{cc}\begin{array}{c}{b}_K\left(i\right)\mathrm{XOR}C\left(i\right)=b_K\left(i\right)\mathrm{XOR}\left(P\left(i\right)\mathrm{XOR}{b}_K\left(i\right)\right)\\ =b_K\left(i\right)\mathrm{XOR}\left(b_K\left(i\right)\mathrm{XOR}P\left(i\right)\right)\\ =\left(b_K\left(i\right)\mathrm{XOR}{b}_K\left(i\right)\right)\mathrm{XOR}P\left(i\right)\\ =0\mathrm{XOR}P\left(i\right)\\ =P\left(i\right)\end{array}& \left(22\right)\end{array}$

[0059] The decryption transformation is identical to the encryption transformation. Therefore, the message can be decrypted by anyone, provided that he or she has the bit sequence that was used to encrypt the message. Typically, generating the sequence is straightforward if one has the key K, but it should be difficult to do so if one does not have the key K. Thus, for effective encryption, the sequence of bits should have no easily discernable pattern. Sequences with no easily discernable pattern are sometimes called “pseudo-random” bit sequences.

[0060] There are a number of known methods for generating pseudo-random sequences. Most such methods result in a sequence that repeats after some period T. If the repeat period T is short, then the security of the encryption is weak. For example, if the repeat period T is much shorter than the message, then there are many bits in the message that are encrypted using the same value of b_K(i). If any one of these bits is decrypted, then all others of these bits may also be easily decrypted. The present invention uses a novel technique for generating a pseudo-random bit sequence having a long repeat period.

[0061] In the present invention, a key K is used to derive the sequence Z of z(i), where i=1, 2, . . . , n, in accordance with equations (19)-(21). A pseudo-random sequence of bits b(i) is then formed by selecting a specific bit (e.g., the least significant bit or last bit) or several bits (e.g., the last several bits, or every other bit) from each integer z(i).

[0062] In the preferred stream cipher, a message containing a stream of bits P(i), where i=1, 2, . . . , n, is encrypted one bit at a time. The message is encrypted, for example, by performing the XOR operation between corresponding bits of the message and the pseudo-random sequence of bits b(i). Using notations (6)-(11), encryption of the i^thbit C(i) of the encrypted message C can be denoted as:

[0063] C(i)=P(i)XOR b(i)  (23)

[0064] The message is decrypted by performing the XOR operation between corresponding bits of the encrypted message and the pseudo-random sequence of bits b(i). Decryption of the message can be denoted as:

[0065] P(i)=C(i)XOR b(i)  (24)

[0066] Note that the encryption and decryption algorithms denoted by equations (23) and (24) are rather simple. As described in the background section of the present application, the level of security provided by known encryption systems depends on two elements: the strength of the encryption algorithm selected, and the bit length of the encryption key used. When the method of the invention is used, even though the encryption algorithm is rather simple and the bit length for the encryption key K is a fixed number, selection of a prime number p that is larger than the key bit length enhances the encryption security provided.

[0067] Improved Security for Stream Ciphers

[0068] In equations (19)-(21), note that y(1)=z(1)=K. Thus, if b(i) is the least significant bit of z(i), then b(1) is always equal to the least significant bit of K. This limitation is undesirable, because it allows one bit of K to be determined if only one bit (the first bit) of the plain text is discovered. To overcome this vulnerability, a constant offset value F can be added to the bit position in equation (23), as follows.

[0069] C(i)=P(i)XOR b(i+F)  (25)

[0070] and the corresponding decryption of the message can be denoted as:

[0071] P(i)=C(i)XOR b(i+F)  (26)

[0072] In further analyzing equations (19)-(21), it is noted that b(p)=1 for all keys K. Therefore, the message bit encrypted by bit b(p) is vulnerable to attack. To avoid this problem, the prime number p is preferably sufficiently large that for most or all messages, b(p) is not used to encrypt any bit of the message. If N denotes the largest anticipated message length in bits, then the last bit of the message is encrypted with bit b(N+F). Therefore, if p and F are chosen such that p>N+F (or, equivalently, p−F>N), this vulnerability is avoided.

[0073] Combining a Plurality of Stream Ciphers

[0074] To further enhance security, one embodiment of the present invention provides a plurality of stream ciphers. Each bit of the message is encrypted (and decrypted) by XORing the bit with each of the corresponding bits from each of the stream ciphers. To form m stream ciphers, a set of keys K(j) and two sets of prime numbers p(j) and q(j) are selected, where j=1, 2, . . . , m and q(j)=2p(j)+1. Thus, a plurality of pseudo-random sequences of integers can be generated as follows.

[0075] y(i,j)=K(j)ⁱmod q(j)  (27)

[0076] z(i,j)=y(i,j), if y(i,j)≦p(j)  (28)

[0077] z(i,j)=q(j)−y(i,j), if y(i,j)>p(j)  (29)

[0078] A plurality of pseudo-random sequences of bits b(i,j) is then formed by selecting one bit (e.g., the least significant bit), or several bits, from z(i,j).

[0079] Thus, in this embodiment the encryption of a message can be denoted as:

[0080] C(i)=P(i)XOR b(i,1)XOR b(i,2) . . . XOR b(i,m)  (30)

[0081] and corresponding decryption of the message can be denoted as:

[0082] P(i)=C(i)XOR b(i,1)XOR b(i,2) . . . XOR b(i,m)  (31)

[0083] It should be noted that y(1,j), z(1,j), b(1,j), and b(p,j) have similar vulnerabilities to those of y(1), z(1), b(1), and b(p), respectively. To overcome these vulnerabilities, in one embodiment of the invention a set of constant offset values F(j) is selected. Therefore, in this embodiment the encryption of a message can be denoted as:

[0084] C(i)=P(i)XOR b(i+F(1),1)XOR b(i+F(2),2) . . . XOR b(i+F(m),m)  (32)

[0085] and corresponding decryption of the message can be denoted as:

[0086] P(i)=C(i)XOR b(i+F(1),1)XOR b(i+F(2),2) . . . XOR b(i+F(m),m)  (33)

[0087] For reasons similar to those discussed above in connection with constant offset value F, each F(j) is selected such that p(j)−F(j) is much larger than the length of most messages.

[0088] Symmetric Block Ciphers

[0089] A block cipher breaks a message into blocks and encrypts and decrypts the message blocks. In a symmetric block cipher, the message blocks are encrypted and decrypted using a single key K. Electronic book (ECB) mode is a simple symmetric block cipher mode well known to those skilled in the relevant art. In ECB mode, one plain message block is encrypted into only one encrypted cipher block and one encrypted cipher block corresponds to a plain message block. In other words, in ECB mode, each plain message block is encrypted independently from all other message blocks. Other block cipher modes exist and are well-known to those of ordinary skill in the relevant arts. In these other block cipher modes, the output block is dependent both on the input block and on previous blocks. The methods of the invention can be applied to these modes as well as to ECB modes.

[0090] Using notations (6)-(11), the encryption and decryption of a symmetric block cipher can be denoted, respectively, as:

[0091] C=E_K(P)  (34)

[0092] P=D_K(C)  (35)

[0093] In equations (34) and (35), C represents an encrypted message block, E_Krepresents a transformation using key K, P represents a plain message block, and D_Krepresents a reverse transformation of E_Kalso using the key K.

[0094] The present invention performs a message block transformation by using one or both of two transformation types, referred to herein as type 1 and type 2 transformations. A type 1 transformation is a bit position permutation, and a type 2 transformation is a bit pattern permutation.

[0095] To efficiently perform both types of transformations using computer hardware and/or software, the present invention uses an array A of n values, with each of the elements in the array A being denoted as v(i), where i=0, . . . , n−1. The value of v(i) is also an integer in a range from 0 to n−1. Values within the array are used to “swap around” bits in a message block in a controlled and reproducible fashion (reproducible, that is, when the contents of the array are available). It should be noted that an array A represents a valid permutation if and only if: 1) the value of each array element v(i) is in a range from 0 to n−1, where i=1, . . . , n−1; and 2) the n values of all elements v(i) are distinct.

[0096] Bit position permutations and bit pattern permutations are now explained in detail, with examples.

[0097] Bit Position Permutations (Type 1 Transformations)

[0098] In performing a bit position permutation (i.e., a type 1 transformation), each bit in a message block is treated as an object. As is well known, a set of n objects (or n bit positions) can be arranged in n! permutations, where n! stands for n factorial (which is defined for non-negative integers as: 0!=1 and n!=n(n−1)! for n>0). For example, for a message of 3 bits, there are 3 bit positions and three bits p0, p1, p2. Therefore, there are 6 (3!, or 3×2×1) permutations for the three bits in the three bit positions: 1) p0, p1 p2; 2) p0 p2 p1; 3) p1 p0 p2; 4) p1 p2 p0; 5) p2 p0 p1; and 6) p2 p1 p0.

[0099] As a simple example of a bit position permutation, a message block of 3 bits is arranged in the initial order p0 p1 p2 and mapped into an array A having three elements a(0), a(1), a(2), respectively. The values of a(0)=1, a(1)=2, and a(2)=0 represent a permutation p1 p2 p0 for the 3 bits.

[0100] The inverse of a permutation can be easily constructed from the permutation. For example, if the permutation is represented as an array A of values a(i), wherein i=0, 1, . . . , n−1, as described above, then the inverse permutation can be represented as an array V of values v(i), where v(i)=j, and where j is a unique value such that a(j)=i. A single scan through the A array can determine all values of the V array. For example, if the 3 bits are permuted as: p0 p1 p2, and mapped into an array A having 3 elements a(0)=1, a(1)=2, a(2)=0, then v(0)=2, v(1)=0, and v(2)=1. Thus, the inverse process of the permutation can be performed by scanning and matching the three elements in array A with the three elements in array V: 1) v(0)=2, therefore a(2)=0; 2) v(1)=0, therefore a(0)=1; and 3) v(2)=1, therefore a(1)=2. As a result, the permutation p1 p2 p0 is inverted back to initial bit order p0, p1, p2.

[0101] A slightly more complex example of two complimentary type 1 transformations (i.e., a permutation and its inverse) is shown in FIGS. 1-2. Transformations used in actual encryption and decryption may use much larger arrays than any of these examples.

[0102] FIG. 1 shows a memory 100 for storing an array A to perform a bit position permutation, in accordance with one embodiment of the present invention. Note that while FIG. 1 illustrates the bit position permutation for a message block of eight bits (since memory 100 contains eight logic memory cells), the inventive concept behind the example applies to a message block of any size.

[0103] As shown in FIG. 1, memory 100 includes an address column 102 having eight addresses (0, 1, 2, . . . , 7) for indicating eight array elements a(i), where i=0, 1, . . . , 7, and an index column 104 for storing eight index values (also 0, 1, 2, . . . , 7) for forming a bit position permutation of the eight array elements. Message block 106 has eight bits (bit0-bit7), and each of the eight bits is mapped to a respective address of memory 100 based on its position in the message block.

[0104] Specifically, as shown in FIG. 1, bits bit0-bit7 in message block 106 are mapped to addresses 0-7, respectively. The eight index values in index column 104 indicate a specific bit position permutation for the message block. For example, to 2 find the new location for the first bit, bit0, look at address column 102, at address 0. The corresponding index value in column 104 is 1. Therefore, bit0 is placed at location 1 in the new (encrypted) message block 108. New locations can be determined for bits bit1-bit7 in a similar fashion. The result is encrypted message block 108, which comprises the following sequence of bits: bit4, bit0, bit5, bit6, bit2, bit7, bit1, bit3.

[0105] FIG. 2 shows a memory 200 for storing an array V to perform the inverse of the bit position permutation shown in FIG. 1, in accordance with the present invention.

[0106] As shown in FIG. 2, memory 200 includes an address column 202 having eight addresses (0, 1, 2, . . . , 7) for indicating eight array elements v(i), where i=0, 1, . . . , 7, and an inverse index column 204 for storing eight values (also 0, 1, 2, . . . , 7) for forming an inverse permutation of the eight array elements. Encrypted message block 108 has 8 bits (bit′0-bit′7), and each of the 8 bits is mapped to a respective address of memory 200 based on its position in the encrypted message block.

[0107] Specifically, as shown in FIG. 2, bits bit′0-bit′7 in encrypted message block 108 are mapped to addresses 0-7, respectively. The eight index values in inverse index column 204 indicate a specific bit position permutation for the encrypted message block. For example, to find the new location for the first bit, bit′0, look at address column 202, at address 0. The corresponding inverse index value in column 204 is 4. Therefore, bit′0 is placed at location 4 in the new (decrypted or original) message block 106. New locations can be determined for bits bit′1-bit′7 in a similar fashion. As can be seen from FIG. 2, the array that performs an inverse permutation on array A=1, 6, 4, 7, 0, 2, 3, 5 is array V=4, 0, 5, 6, 2, 7, 1, 3.

[0108] Each of the eight values in inverse index column 204 indicates an address in memory 100 where the original bit position before the permutation is stored. Thus, by scanning memory 200 and memory 100, encrypted message block 108 can be transformed back to original message block 106.

[0109] Bit Pattern Permutations (Type 2 Transformations)

[0110] In performing a bit pattern permutation (i.e., a type 2 transformation), each bit pattern in a message block is treated as an object. A block of n bits can be arranged in 2ⁿbit patterns. For example, for a block of 3 bits, there are eight (2³) possible bit patterns: 1) 000; 2) 001; 3) 010; 4) 011; 5) 100; 6) 101; 7) 110; and 8) 111.

[0111] A type 2 transformation can also be performed using array A and inverse array V.

[0112] FIG. 3 shows a memory 300 for storing an array A to perform a bit pattern permutation, in accordance with one embodiment of the present invention. Note that while FIG. 3 illustrates the bit pattern permutation for a bit pattern of 3 bits (since memory 300 contains 8, or 2³, logic memory cells), the inventive concept behind the example applies to a message block of any size.

[0113] As shown in FIG. 3, memory 300 includes an address column 302 having eight addresses (0, 1, 2, . . . , 7) for indicating eight array elements a(i), where i=0, 1, . . . , 7, and an index column 304 for storing eight index values (also 0, 1, 2, . . . , 7) for forming a pattern permutation of the eight array elements. Each bit pattern in message block 306 contains three bits; therefore, there are a total of eight (2³) possible patterns. Each of the eight bit patterns is mapped to a respective address based on the value of the bit pattern. (Note the difference from the position or type 1 permutation, wherein each bit is mapped to a respective address based on its position in the message block.)

[0114] Specifically, as shown in FIG. 3, the eight bit patterns (000, 001, . . . , 111) in original message block 306 are mapped to addresses 0-7, respectively. Index column 304 contains a permutation of the values from 0 to 7. Thus, each of the eight possible bit patterns is mapped into one of the eight values from 0-7, depending on the permutation indicated by the index column 304. For example, for the embodiment shown in FIG. 3, the eight possible bit patterns (000, 001, . . . , 111) of original message block 306 are mapped to the eight index values (1, 6, 4, 7, 0, 2, 3, 5), respectively. The index values are then represented as a bit pattern to generate encrypted message block 308. In the pictured embodiment, encrypted message block 308 comprises the following sequence of 3-bit patterns: 001, 110, 100, 111, 000, 010, 011, 101.

[0115] FIG. 4 shows a memory 400 for storing an array V to perform the inverse of the bit pattern permutation shown in FIG. 3, in accordance with the present invention.

[0116] As shown in FIG. 4, memory 400 includes an address column 402 having eight addresses (0, 1, 2, . . . , 7) for indicating eight array elements v(i), where i=0, 1, . . . , 7, and an inverse index column 404 for storing eight values (also 0, 1, 2, . . . , 7) for forming an inverse pattern permutation of the eight array elements. Encrypted message block 308 contains eight transformed 3-bit patterns, and each of the eight patterns is mapped to a respective address based on the value of the bit pattern. (Because address mapping is based on the value of the bit pattern, and not on the position in the encrypted message block, encrypted message block 308 and encrypted message block 408 both correspond to the same message block, although they are represented differently in FIG. 4.)

[0117] Specifically, as shown in FIG. 4, the eight transformed bit patterns (001, 110, 100, 111, 000, 010, 011, 101) in encrypted message block 308/408 are mapped to addresses 1, 6, 4, 7, 0, 2, 3, 5, respectively. The eight index values in inverse index column 404 indicate a specific bit pattern permutation for the encrypted bit pattern. For example, to find the new bit pattern for the first encrypted bit pattern in encrypted message block 308, which is 001, look at address column 402, at address 1. The corresponding inverse index value in column 404 is 0. Therefore, encrypted bit pattern 001 is replaced by bit pattern 000 in the new (decrypted or original) message block 306. (Because index mapping is based on the value of the bit pattern, original message block 406 and original message block 306 both correspond to the same message block, although they are represented differently in FIG. 4.) New bit patterns can be determined for encrypted bit patterns 000 and 010-111 in a similar fashion. As can be seen from FIG. 4, the array that performs an inverse permutation on array A=1, 6, 4, 7, 0, 2, 3, 5 is array V=4, 0, 5, 6, 2, 7, 1, 3. Note that this inverse permutation array is the same array as in the type 1 transformation of FIG. 2.

[0118] Each of the eight values in inverse index column 404 indicates an address in memory 300 where the original bit pattern before the permutation is stored. Thus, by scanning memory 400 and memory 300, encrypted message block 308 can be transformed back to original message block 306.

[0119] “Subdividing” a Type 2 Transformation

[0120] To ensure a manageable value range, a type 2 transformation may further divide a message block of n bits into w sub-blocks of h bits each. A sub-block of h bits has 2^hbit patterns. A given one of the 2^hbit patterns can be transformed into any value in a range of 0 to 2^h−1, depending on a permutation of the values of 0, 1, . . . , 2^h−1.

[0121] Alternating Type 1 and Type 2 Transformations

[0122] To further enhance security, one embodiment of the present invention alternately applies type 1 and type 2 transformations for several passes, to encrypt a plain message block P of n bits. (Other embodiments apply type 1 and type 2 transformations in previously agreed patterns other than a simple alteration, thereby adding another level of security. In some embodiments, the type 2 transformations operate on sub-blocks of different sizes, adding yet another level of security.) Thus, transformation of a message block P of n bits can be denoted as:

[0123] C=G(P)=G[r](G[r−1] . . . (G[i] . . .(G[1](P)) . . . ) . . . )  (36)

[0124] In equation (36), C is the encrypted message block; G is the overall transformation; G[i] is the i^thtransformation, where i=1, 2, . . . , r; G[i] is either a type 1 or type 2 transformation; and r is the number of transformations.

[0125] The original message block P can be recovered from the encrypted message block C using the inverse transformation of G, as follows:

[0126] P=G′(C)=G′[1](G′[2] . . . (G′[i] . . .(G′[r](C)) . . . ) . . . )  (37)

[0127] In equation (37), G′ is the inverse of the overall transformation G, G′[i] is the inverse of the i^thtransformation G[i], and r is the number of transformations.

[0128] To discuss the overall transformation G of equation (36) in further detail, it is assumed that there are m type 1 transformations and s type 2 transformations, where r=m+s. The m type 1 transformations and the s type 2 transformations are now separately described.

[0129] In performing m type 1 transformations in equation (36), the present invention uses m keys K₁(j), j=1, 2, . . . , m. Thus, each of the m type 1 transformations T₁can be denoted as:

[0130] C=T₁[K₁(j)](B), j=1, 2, . . . , m  (38)

[0131] In equation (38), T₁[K₁(j)] represents a type 1 permutation selected by the key K₁(j), B represents the input block, and C represents the output block.

[0132] More specifically, for performing each of the m type 1 transformations, the present invention selects two sets of prime numbers p₁(j) and q₁(j), where q₁(j)=2p₁(j)+1, j=1, 2, . . . , m. Using these prime numbers, a sequence of n integers can be derived as follows:

[0133] y₁(i,j)=K₁(j)ⁱmod q₁(j),  (39)

[0134] where j=1, 2, . . . , m and i=1, 2, . . . , n

[0135] z₁(i,j)=y₁(i,j), if y₁(i,j)≦p₁(j);

[0136] and

[0137] z₁(i,j)=q₁(j)−y₁(i,j), if y₁(i,j)>p₁(j)  (40)

[0138] Once the sequence of integers z₁(i,j) has been formed, a sequence of bits b₁(i,j) can be formed by selecting a specific bit from z₁(i,j). The sequence of integers z₁(i,j) or the sequence of bits b₁(i,j) can be used to select a bit position permutation for each of the m type 1 permutations. (The process of selecting a bit position permutation from a sequence of integers or bits is shown in FIGS. 9A-9J, which are later described.)

[0139] The inverse of the type 1 permutation (i.e., the transformation that returns the original message block B) can be denoted as follows:

[0140] B=T₁′[K₁(j)](C), j=1, 2, . . . , m  (41)

[0141] In equation (41), T₁′[K₁(j)] represents an inverse of the first type 1 permutation T₁selected by the key K₁(j).

[0142] For performing s type 2 transformations in equation (36), the present invention uses s sets of keys K₂, each set of keys containing w sub-keys for performing a transformation for a sub-block (assuming that the block B is divided into w sub-blocks). Thus, the s key sets can be denoted as:

[0143] K₂(1,1), K₂(1,2), . . . , K₂(1,w)

[0144] K₂(2,1), K₂(2,2), . . . , K₂(2,w)

[0145] . . .

[0146] K₂(s,1), K₂(s,2), . . . , K₂(s,w)  (42)

[0147] If input block B is divided into w sub-blocks B(j), where j=1, 2, , . . . , w, then a type 2 transformation T₂can be denoted as:

[0148] C=T₂[K₂(i,1)](B(1)), T₂[K₂(i,2)](B(2)), . . . , T₂[K₂(i,w)](B(w)), where i=1, 2, . . . , s=T₂[K₂(i,1), K₂(i,2), . . . , K₂(i,w)](B)  (43)

[0149] In equation (43), C represents the output block, and T₂[K₂(i,j)] represents the type 2 transformation selected by the key K₂(i,j).

[0150] More specifically, for performing each of the s type 2 transformations, the present invention selects two sets of prime numbers p₂(i,j) and q₂(i,j), where q₂(i,j)=2p₂(i,j)+1, i=1, 2, . . . , s, and j=1, 2, . . . , w. Hence, a sequence of integers can be denoted as:

[0151] y₂(i,j)=K₂(i,j)ⁱmod q₂(i,j), where i=1, 2, . . . , sand j=1, 2, . . . , w  (44)

[0152] z₂(i,j)=y₂(i,j), if y₂(i,j)≦p₂(i,j);

[0153] and

[0154] z₂(i,j)=q₂(i,j)−y₂(i,j), if y₂(i,j)>p₂(i,j)  (45)

[0155] Once the sequence of integers z₂(i,j) has been formed, a sequence of bits b₂(i,j) can be formed by selecting a specific bit from each of integers z₂(i,j). The sequence of integers z₂(i,j) or the sequence of bits b₂(i,j) can be used to select a bit pattern permutation for each of s type 2 permutations.

[0156] The inverse of the type 2 transformation (i.e., the transformation that returns the original input block B) can be denoted as:

[0157] B=T₂′[K₂(i,1)](C(1)), T₂′[K₂(i,2)](C(2)), . . . , T₂′[K₂(i,w)](C(w))=T₂′[K₂(i,1), K₂(i,2), . . . , K₂(i,w)](C)  (46)

[0158] In equation (46), B represents the input block, C(i) represents the i^thone of w sub-blocks of the output block, and T₂′[K₂(i,j)] represents the type 2 inverse transformation.

[0159] The bit sequences used for the transformations need not all be separately generated. For example, in one embodiment, one T₂transformation uses a single key K, with a single pair of prime numbers p and q, to generate a single sequence of bits. The bits from the sequence are then used for the w sub-block transformations in sequence; i.e., the single sequence of bits is divided into multiple “sub-sequences”, each of which is used for a different sub-block. In other embodiments, sequences are divided in other ways among the various transformations.

[0160] Exemplary Encryption Process Using Alternating Transformations

[0161] FIG. 5 shows an exemplary encryption process wherein type 1 and type 2 transformations as denoted in equation (36) are alternately applied, in accordance with one embodiment of the present invention.

[0162] As shown in FIG. 5, nine transformations are performed over a message block 506 of 16 bits. Among these nine transformations, five are type 1 transformations (T1, T3, T5, T7, and T9 ) and four are type 2 transformations (T2, T4, T6, and T8). The sixteen lines labeled “I” represent the input bits of message block 506, and the sixteen lines labeled “O” represent the output bits of encrypted message block 508. Each rectangle labeled A represents a position permutation of 16 bits. Thus, the memory to store the index values for each position permutation requires 16 logic memory units, each containing four bits indicating one of the 16 possible bit positions. Likewise, the memory to store the inverse index values to each position permutation also requires 16 logic memory units, each containing four bits.

[0163] In performing type 2 transformations, the message block of 16 bits is divided into four sub-blocks of four bits. In FIG. 5, each rectangle labeled B represents a pattern permutation of four bits. Thus, the memory to store the index values for each 4-bit pattern permutation requires 16 logic memory units, each containing four bits indicating one of the 16 values from 0 to 15. Likewise, the memory to store the inverse index to each 4-bit pattern permutation requires 16 logic memory units, each containing four bits.

[0164] The embodiment of FIG. 5 uses the five sets of type 1 keys K₁(1), K₁(2), K₁(3), K₁(4), and K₁(5) to perform the type 1 transformations T1, T3, T5, T7, and T9, respectively.

[0165] In performing the type 2 transformations T2, T4, T6, and T8, the embodiment of FIG. 5 uses four sets of keys K₂(1,j), K₂(2,j), K₂(3,j), and K₂(4,j), where j=1, 2, 3, 4. Each of the four sets of keys contains four sub-keys to perform the type 2 transformations for the four sub-blocks. Thus, the four sets of keys can be denoted as follows:

[0166] K₂(1,1), K₂(1,2), K₂(1,3), K₂(1,4) for T2

[0167] K₂(2,1), K₂(2,2), K₂(2,3), K₂(2,4) for T4

[0168] K₂(3,1), K₂(3,2), K₂(3,3), K₂(3,4) for T6

[0169] K₂(4,1), K₂(4,2), K₂(4,3), K₂(4,4) for T8  (47)

[0170] To enhance encryption security, the embodiment of FIG. 5 forms pseudo-random sequences of bits using the five type 1 keys and the four sets of type 2 keys. The pseudo-random sequences of bits are then used to generate index values to initialize the index columns of the memory, similar to the index columns 104, 304 of memories 100, 300 , shown in FIGS. 1 and 3.

[0171] Generating a Sequence of Bits

[0172] FIGS. 6-8 show a process of generating a pseudo-random sequence of bits derived in accordance with equations (19)-(21), in which the prime numbers p and q are specifically selected as 11 and 23, respectively.

[0173] FIG. 6 shows a table 600 containing ten sequences of y(i) (shown in vertical columns) corresponding to ten different keys. Row 616 contains ten keys 2 to 11, and column 614 indicates twelve consecutive bit positions i, where i=0, 1, . . . , 11. Columns 602-611 contain the values for the ten sequences of y(i) corresponding to the keys 2 to 11, respectively.

[0174] FIG. 7 shows a table 700 containing ten sequences of z(i) corresponding to the ten sequences of y(i) shown in FIG. 6. Row 716 contains ten different keys 2 to 11, and column 714 indicates twelve consecutive bit positions i, where i=0, 1, . . . , 11. Columns 702-711 contain the values for the sequences of z(i) corresponding to the y(i) shown in FIG. 6, respectively, and keys 2 to 11, respectively.

[0175] FIG. 8 shows a table 800 containing ten pseudo-random sequences of bits b(i) corresponding to the ten sequences of z(i) shown in FIG. 7. Row 816 contains ten different keys 2 to 11, and column 814 indicates twelve consecutive bit positions i, where i=0, 1, . . . , 11. Columns 802-811 contain the ten pseudo-random sequences of bits corresponding to the z(i) shown in FIG. 7, respectively, and keys 2 to 11, respectively.

[0176] In FIG. 8, each of the ten pseudo-random sequences of bits is formed by selecting the least significant bit from z(i). For example, as shown in column 702 in FIG. 7, when K=2, the sequence of z(i) has twelve values: 1, 2, 4, 8, 7, 9, 5, 10, 3, 6, 11, and 1. The repeat period T for this sequence is 11; therefore z(i) has 11 distinct values. For example, the value “1” from position z(0) is repeated at position z(11). The binary representation of the twelve values in column 702 is: 0001; 0010; 0100; 1000; 0111; 1001; 0101; 1010; 0011; 0110; 1011; and 0001. The pseudo-random sequence (100011101011) shown in column 802 is formed by selecting the least significant bit from the binary representation of sequence z(i). The other nine pseudo-random sequences of bits (for K=3 to K=11) are formed using the same principle.

[0177] Generating Permutation Index Values from the Sequence of Bits

[0178] Referring to FIGS. 9A-J, a process (including 10 schemes) of generating permutation index values is shown for the type 1 and type 2 transformations using the pseudo-random sequences shown in FIG. 8, in accordance with the present invention.

[0179] In describing the examples shown in FIGS. 9A-9J, it is assumed that the type 1 transformation performs the bit position transformation over a message block of four bits. Thus, a memory of four logic memory units is able to store all possible bit permutation index values for the type 1 transformation. The type 2 transformation in this embodiment performs the bit pattern transformation over a message block of two bits. Thus, a memory of four logic memory units is able to store all possible bit pattern permutation index values for the type 2 transformation, because two bits can have four different bit patterns (00, 01, 10, and 11). Further, as shown in FIG. 8, b(0) is always 1 regardless of the value of key K. To enhance security, the process of FIGS. 9A-9J skips the b(0) bit in selecting bits from the sequence b(i).

[0180] Referring to FIG. 9A, a scheme 900 is shown using the pseudo-random sequence in column 802 of FIG. 8 (K=2) to generate permutation index values for type 1 and type 2 transformations, in accordance with the present invention.

[0181] As shown in FIG. 9A, column 902 contains four bit positions (b0, b1, b2, b3) for a message block of four bits, and column 903 contains four bit patterns (00, 01, 10, 11) for a message block of two bits. Column 906 contains combinations of four values (00, 01, 10, 11) for forming a permutation for the four bit positions in column 902 (if doing a type 1 transformation), or for the four bit patterns in column 903 (if doing a type 2 transformation). The four values (00, 01, 10, 11) in column 906 are stored in a quasi queue (quasi-Q) having four positions (Q00, Q01, Q10, Q11). Q00 is the head of the quasi-Q, and Q11 is the tail of the quasi-Q. The values stored at any of the four positions in the quasi-Q can be selected. However, after one value has been selected from the quasi-Q, all remaining values are sequentially moved from the tail to the head. Column 905 indicates a permutation obtained by selecting the four values stored in the quasi-Q, based on the values of the bits in column 904. Column 904 contains the bits sequentially selected from the pseudo-random sequence stored in column 802 of FIG. 8. Column 901 indicates the number of tries to select the values from the quasi-Q.

[0182] In try 1, scheme 900 selects two bits (bit 1 and bit 2) from column 802 of FIG. 8. (Since bit 0 is always 1 regardless of key K, scheme 900 skips bit 0.) As shown in column 904, bits 1 and 2 are 00, indicating position Q01 in the quasi-Q. As shown in column 905, the value 00 stored in Q00 is selected. As shown in column 906, after value 00 has been selected, the three values left (01, 10, 11) in the quasi-Q are shifted into positions Q00, Q01 and Q10, respectively.

[0183] In try 2, scheme 900 selects the next two bits (bit 3 and bit 4) from column 802 of FIG. 8. As shown in column 904, bits 3 and 4 are 01, indicating position Q01 in the quasi-Q. As shown in column 905, the value 10 stored in position Q01 is selected. As shown in column 906, after the value 10 has been selected, the value in Q10 is shifted into position Q01.

[0184] In try 3, scheme 900 selects the next single bit (bit 5) from column 802 of FIG. 8. Since only two values are left in the quasi-Q, one bit is sufficient to select between these two values; therefore, only one bit is selected. (In another embodiment, two bits are always selected regardless of the minimum number of bits required.) As shown in column 904, bit number 5 is 1, indicating position Q01 in the quasi-Q. As shown in column 905, the value 11 stored in position Q01 is selected. As shown in column 906, the one value left (01) in the quasi-Q remains in position Q01.

[0185] In try 4, since only one value is left in the quasi-Q, scheme 900 simply selects the value stored in position Q00. As shown in column 905, a permutation (00, 10, 11, 01; or 0231) is formed.

[0186] Referring to FIG. 9B, a scheme 910 of using the pseudo-random sequence in column 803 of FIG. 8 (K=3) is shown to generate permutation index values for type 1 and type 2 transformations, in accordance with the present invention. The steps generating the permutation index values for FIG. 9B are similar to those described above in connection with FIG. 9A.

[0187] Referring to FIG. 9C, a scheme 920 is shown for using the pseudo-random sequence in column 804 of FIG. 8 (K=4) to generate permutation index values for type 1 and type 2 transformations, in accordance with the present invention. In FIG. 9C, the functions of columns 921-926 are the same as those of columns 901-906, respectively.

[0188] In try 1, scheme 920 selects two bits (bit 1 and bit 2) from column 804 of FIG. 8. (Since bit 0 is always 1, regardless of the key K, scheme 920 skips bit 0.) As shown in column 924, bits 1 and 2 are 01, indicating position Q01 in the quasi-Q. As shown in column 925, the value 01 stored in Q01 is selected. As shown in column 926, the values 10 and 11 in the quasi-Q are shifted to positions Q01 and Q10, respectively. Consequently, three values (00, 10, 11) remain in the quasi-Q at positions Q00, Q01 and Q10, respectively.

[0189] In try 2, scheme 920 selects the next two bits (bit 3 and bit 4) from column 804 of FIG. 8. As shown in column 924, bits 3 and 4 are 11, indicating position Q11 in the quasi-Q. Since position Q11 is now empty, scheme 920 further selects the next two bits (bit 5 and bit 6). As shown in column 924, bits 5 and 6 are 10, indicating position Q10 in the quasi-Q. As shown in column 925, the value 11 stored in position Q10 is selected. As shown in column 926, values 00 and 10 remain in the quasi-Q at positions Q00 and Q01, respectively.

[0190] In try 3, scheme 920 selects the next single bit (bit 7) from column 804 of FIG. 8. (Since only two values are left in the quasi-Q, one bit is sufficient to select between these two values.) As shown in column 924, bit 7 is 0, indicating position Q00 in the quasi-Q. As shown in column 925, the value 00 stored in position Q00 is selected. As shown in column 926, after the value 01 has been selected, the value 10 previously stored in position Q01 is shifted into position Q00.

[0191] In try 4, since only one value is left in the guasi-Q, scheme 920 simply selects the value stored in position Q00. As shown in column 905, a permutation (01, 11, 00, 10; or 1302) is formed.

[0192] The steps for generating the permutation index values for FIGS. 9D-9J are similar to those described above in connection with FIGS. 9A and 9C.

[0193] Referring to FIG. 9D, a scheme 930 of using the pseudo-random sequence in column 805 of FIG. 8 (K=5) is shown to generate permutation index values for type 1 and type 2 transformations, in accordance with the present invention.

[0194] Referring to FIG. 9E, a scheme 940 of using the pseudo-random sequence in column 806 of FIG. 8 (K=6) is shown to generate permutation index values for type 1 and type 2 transformations, in accordance with the present invention.

[0195] Referring to FIG. 9F, a scheme 950 of using the pseudo-random sequence in column 807 of FIG. 8 (K=7) is shown to generate permutation index values for type 1 and type 2 transformations, in accordance with the present invention.

[0196] Referring to FIG. 9G, a scheme 960 of using the pseudo-random sequence in column 808 of FIG. 8. (K=8) is shown to generate permutation index values for type 1 and type 2 transformations, in accordance with the present invention.

[0197] Referring to FIG. 9H, a scheme 970 of using the pseudo-random sequence in column 809 of FIG. 8 (K=9) is shown to generate permutation index values for type 1 and type 2 transformations, in accordance with the present invention.

[0198] Referring to FIG. 9I, a scheme 980 of using the pseudo-random sequence in column 810 of FIG. 8 (K=10) is shown to generate permutation index values for type 1 and type 2 transformations, in accordance with the present invention.

[0199] Referring to FIG. 9J, a scheme 990 of using the pseudo-random sequence in column 811 of FIG. 8. (K=11) is shown to generate permutation index values for type 1 and type 2 transformations, in accordance with the present invention.

[0200] The process depicted in FIGS. 9A-J generates ten permutation index values as listed in Table 1.

[0201] Among the ten permutations, two are duplicates (K=3 and K=7, which generate the same permutation index value 3102). The ten permutations can be used to initialize a permutation index memory similar to memories 100 and 300 of FIGS. 1 and 3.

[0202] Flow Chart for Message Encryption

[0203] FIG. 10 shows the steps of encrypting a message or message block in accordance with one embodiment of the present invention. At step 1002, a pair of prime numbers p and q=2p+1 and a key K are selected. At step 1004, a sequence of integers y(i)=Kⁱmod q is generated. At step 1006, a sequence of integers z(i) is generated, where z(i)=y(i) if y(i)≦p, and z(i)=q−y(i) if y(i)>p. At step 1008, the system generates a sequence of bits b(i) by selecting a bit from z(i). At step 1010, the system encrypts a message or a message block using either z(i) or b(i). As described above, the sequences z(i) and b(i) are utilized to generate stream ciphers and/or block ciphers.

[0204] The encryption and decryption schemes of the present invention can be performed on a computer system such as are well known in the relevant art. Note, however, that the method of the invention can be performed without such a computer system, e.g., in dedicated hardware such as an integrated circuit or circuit board designed specifically for this purpose.

[0205] The present invention therefore provides a novel method for generating a pseudo-random sequence and implementing an encryption and decryption scheme based on the sequence. Although the present invention has been shown and described with respect to preferred embodiments, various changes and modifications lie within the spirit and scope of the claimed invention. Accordingly, all such modifications and additions are deemed to be within the scope of the invention, which is to be limited only by the appended claims and their equivalents.