Abstract:
An encryption and authentication technique that achieves enhanced integrity verification through assured error-propagation using a multistage sequence of pseudorandom permutations. The method generates intermediate data-dependent cryptographic variables at each stage, which are systematically combined into feedback loops. The encryption technique also generates an authentication tag with minimal post processing that is the size of the state.

Description:
RELATED APPLICATIONS 
       [0001]    This application is a continuation-in-part of U.S. application Ser. No. 12/979,693 filed on Dec. 28, 2010 and entitled “ENCRYPTING A PLAINTEXT MESSAGE WITH AUTHENTICATION” which is a continuation of U.S. patent application Ser. No. 12/781,648 filed on May 17, 2010, which is a continuation-in-part of U.S. patent application Ser. No. 12/727,819, entitled “ENCRYPTING A PLAINTEXT MESSAGE WITH AUTHENTICATION”, filed on Mar. 19, 2010, which is a continuation of U.S. patent application Ser. No. 11/496,214, entitled “ENCRYPTING A PLAINTEXT MESSAGE WITH AUTHENTICATION”, filed on Jul. 31, 2006 (now U.S. Pat. No. 7,715,553), which claims the benefit of U.S. provisional patent application No. 60/595,720, filed Sep. 13, 2005, and this application claims the benefit of U.S. Provisional Patent Application Ser. No. 61/331,706 filed May 5, 2010 and entitled “HYBRID MODE CRYPTOGRAPHIC METHOD AND SYSTEM WITH MESSAGE AUTHENTICATION”, and said U.S. patent application Ser. No. 12/781,648 claims the benefit of U.S. Provisional Patent Application Ser. Nos. 61/213,194 filed May 15, 2009 and 61/264,527 filed Nov. 25, 2009, all of the above listed cases being incorporated by reference herein in their entirety. 
     
    
     FIELD 
       [0002]    The described embodiments relates generally to the technical field of data communication and storage. Specifically some embodiments relate to cryptographic methods and systems that allow for both the encryption and authentication of information through the use of a generic pseudorandom permutation. 
       BACKGROUND 
       [0003]    Data encryption methods provide privacy of the encrypted information over insecure communication channels. Encryption methods alone, however, lack manipulation detection abilities to ensure the integrity or authenticity of the information. Data authentication methods are required to detect when the received message was altered by an adversary during communication. 
         [0004]    Many known algorithms provide authentication separate from the privacy. One of the most well known methods for providing data authentication generates an authentication tag or Message Authentication Code (MAC) through the use of a key dependent one-way hash function. A one-way hash function is designed such that it is comparatively easy to compute but almost impossible to reverse. Because the length of the authentication tag is usually fixed and shorter than the length of the initial message, the authentication tag cannot ensure a one-to-one mapping of messages to authentication tags. The length of the authentication tag, however, is designed to be long enough to thwart brute force attacks. 
         [0005]    In the method for exchanging a message with an authentication tag, the sender initiates the exchange by generating an authentication tag from the authentic message using a shared key. The sender then transfers the message and authentication tag to the receiver. At the receiving end, the receiver must generate an authentication tag from the received message using the shared key as well. The receiver then compares his or her generated authentication tag with the received authentication tag. If the two tags match, then the receiver can be assured that the message has not been modified during transmission and that it was sent by someone who knows the secret key. 
         [0006]    The use of an authentication tag or MAC consumes time on the receiving end, because it requires the receiver to generate a MAC for comparison. When combined with a data encryption method, the receiver must decrypt the message and generate an authentication tag before the received information can be used. This conventional approach requires two passes over the same message on both the sending and receiving end, often with the same basic algorithm. Furthermore, this conventional approach often requires the use of separate keys for each function. The use of two separate functions uses excessive processing power, memory, and time. 
         [0007]    In applications focused on minimizing latency such as Supervisory Control and Data Acquisition (SCADA) networks, Radio Frequency Identification (RFID), and other real-time data exchange systems, received information must be used immediately making it impossible to use a separate MAC for data authentication. The devices used in such applications present further restrictions on processing power, code space, and memory. These applications highlight the need for methods that provide message integrity integrated with strong cryptographic privacy to minimize the latency and overhead imposed by separate conventional methods. 
         [0008]    In response to the disadvantages of the conventional approaches, various methods have been suggested. Based on a new proof in error detection, the SCADA community including the AGA12 committee suggested assured error-propagation as a means for providing integrity without the need for a traditional MAC. Various methods exist that include error-propagation to provide some level of integrity. Depending on the level of error-propagation, a one-bit modification to the transmitted ciphertext results in some amount of randomization of subsequent bits in order to provide enhanced manipulation detection. One such method, Propagating Cipher Block Chaining (PCBC) was designed to fully propagate a one-bit modification to all subsequent bits. Since its design, however, PCBC mode has been found to be vulnerable to some straight-forward attacks. For example, switching two ciphertext blocks leaves the rest of the message unchanged. 
         [0009]    Andrew Wright et al. recently proposed another solution, AES PE-mode for use in SCADA networks that was designed based on the error detection proof to assure at least six bits of randomization following a one-bit manipulation (viz., A. K. Wright, J. A. Kinast, and J. McCarty. Low-Latency Cryptographic Protection for SCADA Communications. In: Proc. 2nd Int. Conf. on Applied Cryptography and Network Security, ACNS 2004). While PE-mode lacks the straight-forward vulnerabilities of PCBC, PE-mode imposes a great deal of latency and overhead, because it is essentially a cascade cipher of two AES encryption modes. In addition to encrypting the message twice, PE-mode is designed to be used with a separate message authentication algorithm such as a CBC-MAC. The drawbacks of PCBC and PE-mode illuminate the need for an error-propagating encryption algorithm that is both fast and small and does not require further steps to achieve integrity. 
         [0010]    The proposed solutions are often implemented as block ciphers that require the plaintext message to fit within the fixed block size of the encryption algorithm. When a plaintext block is less than the fixed block size these conventional algorithms often pad the plaintext block resulting in a ciphertext message that is expanded from the plaintext message. In applications were it is desirable to minimize the number of transmitted bits while still providing message authentication this ciphertext expansion is undesirable. 
         [0011]    Some message authentication techniques are also prone to collision or birthday attacks. Authentication techniques where two separate messages may share an identical authentication code may be exploited by an attacker. 
       SUMMARY OF SOME EMBODIMENTS 
       [0012]    The described embodiments generally provide methods and systems for efficiently integrating integrity and strong encryption through assured error-propagation and an automatically generated authentication tag. The provided embodiments are designed to work with considerably low levels of needed code space, processing resources, memory, and latency requirements. Briefly, the described embodiments may include a multi-stage encryption system, wherein a plaintext block is passed through a sequence of pseudorandom permutations. The systems generate intermediate data-dependent cryptographic variables at each stage, which are systematically combined into feedback loops to produce assured error-propagation. At the conclusion of encryption, the embodiments generate a cryptographic hash using the final data-dependent cryptographic variables. 
         [0013]    The described embodiments include methods, systems, processes, devices, stand-alone cryptographic algorithms, and modes of existing cryptographic algorithms. Several of these embodiments are described below. 
         [0014]    In one embodiment, an encryption engine for multi-stage data encryption and authentication is defined wherein each stage is a pseudorandom permutation. The encryption engine performs the steps of: receiving plaintext data, partitioning the plaintext into equal size plaintext blocks, passing each plaintext block through a sequence of pseudorandom permutations, modifying the states of the pseudorandom permutations for the next block based on each current block&#39;s intermediate stage cryptographic variables each of which is the output of one stage in the sequence, possibly further modifying the states of the pseudorandom permutations for the next block based on a function of prior values of one or more states of the pseudorandom permutations, and generating ciphertext from the output of each plaintext block&#39;s final stage. It should be noted that pseudorandom permutations are usually considered stateless. The described embodiments create what will be referred to as states by storing variables that are used to modify the input to each pseudorandom permutation. Since the state of these variables directly affects the output of each pseudorandom permutation, the permutations can be seen as having states. 
         [0015]    In a further aspect of some embodiments, the implementation of each pseudorandom permutation can be achieved by one or multiple of the following: generating shifted permutation tables also known as S-Boxes, using existing cryptographic algorithms, including but not limited to AES, RC5, TEA, IDEA, Present, TWOFISH, or electronically implementing classical rotors. 
         [0016]    In a further aspect of some embodiments, the modification of the states of each pseudorandom permutation is accomplished by following the pattern which will be referred to as the “312 rule”. The pattern outlines the following steps:
       (a) The state of the first pseudorandom permutation is modified by the output of the next to the last pseudorandom permutation.   (b) The states of the middle pseudorandom permutations are modified by the output of previous pseudorandom permutation.   (c) The state of the last pseudorandom permutation is modified by both the state and output of the first pseudorandom permutation.       
 
         [0020]    In a further aspect of some embodiments, the pattern may also include one or more of the following steps:
       (d) The state of the second pseudorandom permutation is further modified by the state of the last pseudorandom permutation performed in step ‘c’.   (e) The state of each pseudorandom permutation is further modified by a function of current and/or previous state values of one or more of the pseudorandom permutations.       
 
         [0023]    In a further aspect of some embodiments, the method may generate an authentication tag using the final plaintext block&#39;s state variables. The generation of the authentication tag may be accomplished by either concatenating the final state variables or masking the final state variables by combining them with the initial permutation states before concatenation. 
         [0024]    In a further aspect of some embodiments, the method may generate an authentication tag using plaintext block&#39;s state variables after they have been obfuscated. The first step in the generation of the authentication tag is to create distance by advancing the final state variables so that the final state variables may not be ascertained from the authentication tag. This is accomplished by encrypting the sum of two of the state variables until the desired distance has been achieved. The state variables at this point in time may then be used to compose the authentication tag. 
         [0025]    In a further aspect of some embodiments, the method may generate an authentication tag by encrypting a plain text block known to a possible attacker, such as the initialization vector (IV) used in the initialization process, with the resulting cipher text being used as the authentication tag. 
         [0026]    In a further aspect of some embodiments, the method may generate an authentication tag by encrypting a plain text block known to a possible attacker after using the plaintext block&#39;s state variables to create distance by advancing the final state variables so that the final state variables may not be ascertained from the knowledge of the initial state variables used to encrypt the known plain text block. The resulting cipher text may then be used as the authentication tag. 
         [0027]    In a further aspect of some embodiments, the method may include the step of initializing the beginning state variables. The initialization process may be conducted by encrypting a nonce using a non-initialized version of the defined method and using the generated ciphertext and authentication tag as the beginning variables. 
         [0028]    In a further aspect of some embodiments, the initialization process may be conducted by encrypting a nonce using a non-initialized version of the defined method and using the sum of two of the state variables at time t as the input. This may be repeated for a number of iterations in order to resist cryptanalysis. The result is a state that is unique and unpredictable as long as the nonce is unique. 
         [0029]    In a further aspect of some embodiments, the initialization process may be conducted by encrypting a nonce using a non-initialized version of the defined method and using a known constant at time t as the input. This may be repeated for a number of iterations in order to resist cryptanalysis. The result is a state that is unique and unpredictable as long as the nonce is unique. 
         [0030]    In a further aspect of some embodiments, an internal counter may be used to further modify the states of the pseudorandom permutations. The addition of a counter, designed to eliminate short cycles, is performed by storing N counter variables where N is the number of pseudorandom permutation stages, incrementing the counter variables in an odometric fashion, and modifying each pseudorandom permutation state by the associated counter variable. 
         [0031]    In a further aspect of some embodiments, a LFSR may be used in place of an internal counter. The size of the LFSR may be chosen arbitrarily. A portion of the LFSR may be used to modify one or more of the permutations. 
         [0032]    In a further aspect of some embodiments, an accumulator may be used in place of an internal counter. Each accumulator updates its value via a function (such as an XOR) of the current accumulator value and the current value of its associated pseudorandom permutation state. A portion of each accumulator may be used to modify one or more of the pseudorandom permutation states. 
         [0033]    In a further aspect of some embodiments, the number of needed pseudorandom permutations may be reduced by substituting the inverse of pseudorandom permutations in use for some number of other pseudorandom permutations. For example, in a 4-stage method with pseudorandom permutations ABCD, the number of pseudorandom permutations required could be reduced by using the permutations ABA −1 B −1  (where A −1  and B −1  are the inverses of A and B, respectively). 
         [0034]    In a further aspect of some embodiments, the number of needed pseudorandom permutations may be reduced on one side of the communications channel by supplying only pseudorandom permutations on one side while the other side has both pseudorandom and inverse pseudorandom permutations. For example the server side can have both ABCD and A −1 B −1 C −1 D −1  permutations while the client side can have only ABCD permutations. Communication from the server to the client may be accomplished by first decrypting the plaintext message (which has the same effect as encrypting). The client can then recover the message by encrypting the ciphertext (which has the same effect as decrypting). Communication from the client to the server may be performed in the normal fashion i.e. client encrypts message, server decrypts message. 
         [0035]    In a further aspect of some embodiments, a data decryption method that is the inverse of the multi-stage data encryption and authentication method may be defined. The method comprises the steps of: receiving ciphertext data, partitioning the ciphertext into equal size ciphertext blocks, passing each block through a sequence of pseudorandom permutations where each permutation is an inverse of the permutations used in the encryption method, modifying the states of the pseudorandom permutations for the next block based on each current block&#39;s intermediate stage cryptographic variables, and generating plaintext from the output of each ciphertext block&#39;s final stage. The decryption method passes each ciphertext block backwards through the sequence in the encryption method. It should be noted that the chosen embodiment of the decryption method should match those in the chosen embodiment of the encryption method. For example, if the chosen embodiment of the encryption method uses RC5 as the pseudorandom permutation, generates an authentication tag, and utilizes counters, the chosen embodiment of the decryption method should also use RC5, generate an authentication tag, and use counters. 
         [0036]    In a further aspect of some embodiments, a method for performing an integrity check is defined. The method includes the steps of: performing the encryption method defined in order to generate ciphertext and an authentication tag, performing the decryption method defined on said ciphertext in order to generate plaintext and a second authentication tag, and comparing the two authentication tags for equality. It can be assured with high probability that the ciphertext was not modified after encryption if the two authentication tags are equal. 
         [0037]    In another embodiment, an encryption or decryption engine for encrypting or decrypting messages comprises memory (e.g. one or more data storage devices) for storing state variables and control logic that is configured to receive the message, apply one or more pseudorandom permutations to the blocks of the message, and modify the input to each pseudorandom permutations by at least one state variable which is modified by at least one of the previously generated permutation outputs, previously generated permutation inputs, ciphertext, and plaintext. The encryption/decryption engine may be further configured to generate or authenticate an authentication tag that is attached to the message. The control logic may be further configured to initialize the state variables and an LFSR by randomizing a nonce. Alternatively, in some embodiments the control logic may be further configured to initialize the state variables and at least one accumulator by randomizing a nonce. The control logic may be further configured to modify at least one state variable by an LFSR. Alternatively, in some embodiments the control logic may be further configured to modify at least one state variable by the accumulators. 
         [0038]    In a further aspect of some embodiments, an encryption or decryption engine may be further configured to operate in a hybrid mode for encrypting or decrypting sub-blocks less than the fixed block size of the encryption or decryption engine, where the control logic is further configured to receive the sub-block, generate a keystream by applying 2 or more pseudorandom permutations to the at least one state variable, apply the keystream to the sub-block, transform the sub-block to the fixed block size, and modify the input to each pseudorandom permutations by at least one state variable which is modified by at least one of the previously generated permutation outputs, previously generated permutation inputs, ciphertext, plaintext, and transformed sub-blocks. In a further aspect of some embodiments, the method may encrypt a nonce prior to generating an authentication tag. 
         [0039]    In another embodiment, an encryption or decryption engine for encrypting or decrypting messages comprises memory for storing state variables and control logic that is configured to receive the message, apply one or more pseudorandom permutations to the blocks of the message, and modify the input to each pseudorandom permutations by at least one state variable which is modified by at least one of the previously generated permutation outputs, previously generated permutation inputs, ciphertext, and plaintext. The encryption/decryption engine may be further configured to generate and/or authenticate an authentication tag that is attached to the message. The control logic may be further configured to initialize the state variables and accumulator variables by randomizing a nonce. The control logic may be further configured to accumulate the state changes in accumulator registers. The accumulator registers may be used to modify the key in one or more pseudorandom permutations. 
     
    
     
       DESCRIPTION OF VARIOUS EMBODIMENTS 
         [0040]    For a more complete understanding of the described embodiments and for further features and advantages, reference is now made to the following description, taken in conjunction with the accompanying drawings, in which: 
           [0041]      FIG. 1  is a first flowchart in accordance with one embodiment; 
           [0042]      FIG. 2  is a second flowchart in accordance with one embodiment; 
           [0043]      FIG. 3  is a schematic illustration of one embodiment of an encryption system; 
           [0044]      FIG. 4  is a schematic illustration of one embodiment of a decryption system; 
           [0045]    FIG. is a schematic illustration of one embodiment for initializing variables using a nonce; 
           [0046]      FIG. 6  is a schematic illustration of one embodiment for generating an authentication tag from final state variables; 
           [0047]      FIG. 7  is a schematic illustration of one embodiment for generating a masked authentication tag from a combination of the initial and final state variables; 
           [0048]      FIG. 8  is a schematic illustration of one embodiment for decrypting and verifying the integrity of the message using a received authentication tag; 
           [0049]      FIG. 9  is a schematic illustration of one embodiment of the encryption system from  FIG. 3  with the addition of counters; 
           [0050]      FIG. 10  is a schematic illustration of one embodiment of the decryption system from  FIG. 4  with the addition of counters; 
           [0051]      FIG. 11  is a schematic illustration of one embodiment for incrementing counters; 
           [0052]      FIG. 12  is a schematic illustration of an alternative embodiment of an encryption system; 
           [0053]      FIG. 13  is a schematic illustration of an alternative embodiment of a decryption system; 
           [0054]      FIG. 14  is a schematic illustration of an embodiment of an encryption system using an LFSR; 
           [0055]      FIG. 15  is a schematic illustration of an embodiment of a decryption system using an LFSR; 
           [0056]      FIG. 16  is a schematic illustration of an embodiment for initializing variables using a nonce; 
           [0057]      FIG. 17  is a schematic illustration of an embodiment wherein an authentication tag is generated from the final state variables; 
           [0058]      FIG. 18  is a schematic illustration of an embodiment of a method for decrypting and verifying the integrity of a message using a received authentication tag; 
           [0059]      FIG. 19  is a schematic illustration of a hardware embodiment of a system for encryption/decryption and authentication; 
           [0060]      FIG. 20  illustrates a hybrid mode of operation of an encryption engine shown encrypting a 40-bit plaintext message; 
           [0061]      FIG. 21  illustrates a hybrid mode of operation of a decryption engine shown decrypting a 40-bit ciphertext message; 
           [0062]      FIG. 22  is a schematic illustration of an embodiment for generating an authentication tag using a nonce as input to the encrypt engine; 
           [0063]      FIG. 23  is a schematic illustration of an embodiment of an encryption system using accumulators; 
           [0064]      FIG. 24  illustrates the equations that define the encryption method from  FIG. 23 ; and 
           [0065]      FIG. 25  is a schematic illustration of an embodiment for generating an authentication tag using a nonce as input to the encryption engine wherein the internal state is expanded by the inclusion of accumulators. 
       
    
    
     DETAILED DESCRIPTION 
       [0066]      FIGS. 1 and 2  represent two versions of a flow chart explaining the steps of encryption for some of the embodiments described herein.  FIG. 1  was the original diagram as can found in U.S. provisional patent Ser. No. 60/595,720. While maintaining the essential core,  FIG. 2  is the revised encryption diagram with a more clear representation and the elimination of unneeded steps. Before explaining the details of the revised diagram, it is good to note the difference between the two diagrams. 
         [0067]    The original diagram uses the term Variable Exchange Table (VET) which is now referred to as the more generally used and understood term, pseudorandom permutation. Furthermore, what was originally denoted as a VET Setting (VS) is now referred to as a state variable (SV), and the Output of a VET is now referred to as an intermediate cryptographic variable (CV). The terms have been modified for ease of understanding. 
         [0068]      FIG. 1  contains all of the same steps as the revised diagram except the generation of the authentication tag  270  and the initialization of the state variables  500 . In order to compensate for uncertainty, additional steps  115 ,  120 , and  150  were added to the encryption method to facilitate the combination of the output of the final pseudorandom permutation with an AES keystream through an exclusive or (XOR) function to produce ciphertext. Said additional steps were thought to further protect the ciphertext from attacks. Further consideration and evaluation have eliminated the need for said additional steps, and therefore they have been removed from the revised diagram. Note that corresponding steps in the two diagrams have been numbered the same (ex 125 corresponds to 225). 
         [0069]      FIG. 2  illustrates the steps involved in an encryption embodiment. From the start, a key and counter are loaded  200  in order to initialize the pseudorandom permutations if necessary  205  and  210 . The next step initializes the state variables and counters with a nonce  500  which is described in further detail in  FIG. 5 . Once the plaintext is acquired  225 , the first plaintext block is combined with the initialized state variables and stepped through a series of four pseudorandom permutations  230 - 245  resulting in the first ciphertext block  255 . Before the next plaintext block can be encrypted, the state variables are updated using the intermediate cryptographic variables  260 . This cycle continues  265  and  225  for all plaintext blocks. Optionally, the final state variables can be combined to form an authentication tag  270 . The details of the embodied encryption method are described to a greater extent in the next diagram. 
         [0070]      FIG. 3  represents an encryption embodiment wherein m plaintext blocks P i    301  are each passed through a sequence of four pseudorandom permutations  303  resulting in m ciphertext blocks  304 . In this embodiment each of the four permutations  303  are keyed with different keys k1, k2, k3, and k4. The embodied method includes the step of initializing the state variables  302  by passing a nonce  310  through a randomization function  500  that is discussed in detail below. Once the state variables are initialized, the first plaintext block P i    301   a  is combined with the initial state variable SV1 0    302   a  through modular 2 n  addition where n is the size of a plaintext block. The result of said combination is passed into the first pseudorandom permutation F k1    303   a  producing an intermediate cryptographic variable, CV12 i  (the cryptographic variable between the first pseudorandom permutation Fk 1    303   a  and the second pseudorandom permutation Fk 2    303   b ) which will be fed forward to encrypt the next plaintext block P 2    301   b . Continuing with the encryption of P 1    301   a , CV12 1  is combined with the second initialized state variable SV2 0    302   b  through modular 2 n  addition and passed into the second pseudorandom permutation F k2    303   b  resulting in CV23 1 . The encryption continues to follow the same pattern for the two remaining pseudorandom permutations Fk 3    303   c  and F k4    303   d  where the result of F k4    303   d  is the first ciphertext block C 1    304   a.    
         [0071]    For the encryption of the next plaintext block P 2    301   b , the state variables  305  should be updated using a feedback mechanism as will be described. The first state variable SV1 1    305   a  produced following the encryption of the first plaintext block P 1 ,  301   a  is generated by combining the previous state variable SV1 0    302   a  with the output from the previous block&#39;s third permutation CV34 1  through modular 2 n  addition where n is the size of a plaintext block. The second state variable SV2 1    305   b  is generated by combining the previous state variable SV2 0    302   b  with the output from the previous block&#39;s first permutation CV12 1  through modular 2 n  addition. Similarly, the third state variable SV3 1    305   c  is generated by combining the previous state variable SV3 0    302   c  with the output from the previous block&#39;s second permutation CV23 1  through modular 2 n  addition. The fourth state variable SV4 1    305   d  is generated by combining the previous state variable SV4 0    302   d  with the output from the previous block&#39;s first permutation CV12 1  and the current block&#39;s first state variable SV1 1    305   a , through modular 2 n  addition. It should be noted that the calculation of SV1 1    305   a  should occur before the calculation of SV4 1    305   d . Furthermore, while the described embodiment stores the state variables SV1, SV2, SV3, and SV4, derived embodiments could entail the same spirit of the present embodiments without actually storing the state variables. The step of storing state variables is disclosed for ease of understanding. 
         [0072]    The encryption of all further plaintext blocks P 2    301   b  through P m    301   c  may be conducted in the same manner as the encryption of P 1    301   a . For example, the second plaintext block P 2    301   b  is conducted in the same manner as the encryption of the first plaintext block P 1    301   a  substituting the updated state variables  305  for the previous state variables  302 . 
         [0073]      FIG. 4  represents a decryption embodiment wherein m ciphertext blocks C i    404  are each passed through a sequence of four inverse pseudorandom permutations FK −1    403  resulting in m plaintext blocks P i    401 . In this embodiment each of the four inverse permutations FK −1    403  are keyed with the same keys used in the encryption in  FIG. 3 . The embodied method includes the step of initializing the state variables  402  by passing a nonce  410  through a randomization function  500  that is discussed in detail below. Once the state variables  402  are initialized, the first ciphertext block C 1    404   a  is passed into the first inverse pseudorandom permutation  403   d . The result of said inverse pseudorandom permutation F k4   −1    403   d  is combined with the initial state variable SV4 0    402   d  through modular 2 n  subtraction where n is the size of a ciphertext block producing an intermediate cryptographic variable CV34 1  (the cryptographic variable between F k3   −1    403   c  and F k4   −1    403   d ) which will be fed forward to decrypt the next ciphertext block C 2    404   b . Continuing with the decryption of C 1    404   a , CV34 1  is passed into the second inverse psuedorandorandom permutation F k3   −1 403 c. The result of said inverse permutation F k3   −1    403   c  is combined with SV3 0  using modular 2 n  subtraction producing CV23 1 . The decryption continues to follow the same pattern for the two remaining inverse pseudorandom permutations F k2   −1    403   b  and F k1   −1    403   a  where the result of F k1   −1    403   a  is combined with SV1 0    402   a  using modular 2 n  subtraction to produce the first plaintext block P 1    401   a.    
         [0074]    For the decryption of the next ciphertext block C 2    404   b , the state variables  405  are updated using a feedback mechanism as will be described. The state variable SV 1 ,  405   a , produced following the decryption of the first ciphertext block C 1    404   a , is generated by combining the previous state variable SV1 0    402   a  with the input from the previous block&#39;s second inverse permutation CV34 1  through modular 2 n  addition where n is the size of a ciphertext block. The second state variable SV2 1    405   b  is the output of the previous block&#39;s third inverse permutation F k2   −1    403   b . Similarly, the state variable SV3 1    405   c  is the output of the previous block&#39;s second inverse permutation F k3   −1    403   c . The state variable SV4 1    405   d  is generated by combining the previous state variable SV4 0    402   d  with the input from the previous block&#39;s fourth inverse permutation CV12 1  and the current block&#39;s state variable SV1 1 ,  405   a , through modular 2 n  addition. It should be noted that the calculation of SV 1 ,  405   a  should occur before the calculation of SV4 1    405   d . Furthermore, while the described embodiment stores the state variables SV1, SV2, SV3, and SV4, derived embodiments could entail the same spirit of the present embodiments without actually storing the state variables. The step of storing state variables is disclosed for ease of understanding. 
         [0075]    The decryption of all further ciphertext blocks C 2    404   b  through C m    404   e  are conducted in the same manner as the decryption of C 1    404   a . For example, the second ciphertext block C 2    404   b  is conducted in the same manner as the decryption of the first ciphertext block C 1    404   a  substituting the updated state variables  405  for the previous state variables  402 . 
         [0076]      FIG. 5  illustrates the function of generating initial values by randomizing a nonce as used in  FIGS. 3 ,  4 ,  9 , 10 , and  23  for example. The purpose of said function is to initialize the state variables and counters to unique and unpredictable values. In some embodiments, the nonce or input to the function may be a random number, an incrementing counter, or any value as long as it has not been used before in the context of a given key(s). It should be noted that the nonce need not be secret. It should also be noted that repeating a nonce simply results in the initial state of the pseudorandom permutations being the same for each repeat of the nonce. The initialization function parses a unique value into m blocks N i    501  and passes each block through a sequence of m pseudorandom permutations  503  resulting in values that are used in the initial setup of both the encryption and decryption methods. Padding may be necessary in order to facilitate equal sized blocks. The number of blocks m and the number of pseudorandom permutations m should always be the same. In the present embodiment of the initialization function, m is equal to 4. The randomization function keys each of the four permutations F K    503  with different keys k1, k2, k3, and k4. The embodied method includes the step of initializing the state variables  502  to a constant such as zero. Once the state variables  502  are initialized, the first block N 1    501   a  is combined with the initial state variable SV1  502   a  through modular 2 n  addition where n is the size of a block. The result of said combination is passed into the first pseudorandom permutation F k1    503   a  producing an intermediate cryptographic variable CV12 1  (the cryptographic variable between the first pseudorandom permutation F k1    503   a  and the second F k2    503   b ) which will be fed forward to encrypt the next block N 2    501   b . Continuing with the randomization function of N 1    501   a , CV12 1  is combined with the second initialized state variable SV2 1    502   b  through modular 2 n  addition and passed into the second pseudorandom permutation F k2    503   b  resulting in CV23 1 . The randomization continues to follow the same pattern for the two remaining pseudorandom permutations F k3    503   c  and F k4    503   d  where the result of F k4    503   d  is the first CTR value CTR1 0    504   a . It should be noted that some embodiments may not use the generated CTR  504  values. 
         [0077]    For the next block N 2    501   b , the state variables  505  should be updated using a feedback mechanism as will be described. The first state variable SV1 n2    505   a  produced following the randomization of the first block N 1    501   a  is generated by combining the previous state variable SV1 n1    502   a  with the output from the previous block&#39;s third permutation CV34 1  through modular 2 n  addition where n is the size of a block. The second state variable SV2 n2    505   b  is generated by combining the previous state variable SV2 n1    502   b  with the output from the previous block&#39;s first permutation CV12 1  through modular 2 n  addition. Similarly, the third state variable SV3 n2    505   c  is generated by combining the previous state variable SV3 n1    502   c  with the output from the previous block&#39;s second permutation CV23 1  through modular 2 n  addition. The fourth state variable SV4 n2    505   d  is generated by combining the previous state variable SV4 n1    502   d  with the output from the previous block&#39;s first permutation CV12 1  and the current block&#39;s first state variable SV1 n2    505   a , through modular 2 n  addition. It should be noted that the calculation of SV1 n2    505   a  should occur before the calculation of SV4 2    505   d . Furthermore, while the described embodiment stores the state variables SV1, SV2, SV3, and SV4, derived embodiments could entail the same spirit of the present embodiments without actually storing the state variables. The step of storing state variables is disclosed for ease of understanding. 
         [0078]    The randomization of all further plaintext blocks N 2    501   b  through N 4    501   d  may be conducted in the same manner as the randomization of N 1    501   a . For example, the second plaintext block N 2    501   b  is randomized in the same manner as the randomization of the first plaintext block N 1    501   a  substituting the updated state variables  505  for the previous state variables  502 . After the four blocks  501  are each randomized, the resulting state variables SV1 0 , SV2 0 , SV3 0 , and SV4 0    508  can be used as initial state variables for  FIGS. 3 ,  4 ,  9 , and  10 , for instance. Similarly, the resulting randomized values, CTR1 0 , CTR2 0 , CTR3 0 , and CTR4 0    504  can be used as initial counters for  FIG. 9  and  FIG. 10 . 
         [0079]      FIG. 6  presents an elevated look at the method for generating an authentication tag from the results of the previously described encryption embodiment. The schematic diagram includes an abbreviated version of the encryption method  300  in which each sequence of pseudorandom permutations is depicted in a single encryption function E i    601 . The final encryption function E m    601   c  produces four final state variables  602  which are concatenated to form an authentication tag  603 . As explained previously, an authentication tag is used to provide an integrity check on encrypted data. 
         [0080]      FIG. 7  represents an alternative embodiment of the method for generating an authentication tag from the results of an encryption embodiment. As in  FIG. 6 , the diagram includes an abbreviated version of the encryption method  300 . In this alternative embodiment, each final state variable  702  is combined with its corresponding initial state variable  701  through an XOR function  703  before being concatenated to form the authentication tag  704 . This alternative embodiment masks the final state variables from being openly accessible to an attacker and may serve to increase the cryptographic strength. 
         [0081]      FIG. 8  represents an embodied method for performing an integrity check of a message after decryption. The schematic diagram includes an abbreviated version of the decryption method  400  in which each sequence of inverse pseudorandom permutations is depicted in a single decryption function D i    802 . The received message includes a previously generated authentication tag AT  805  in addition to the ciphertext  801 . Said authentication tag was previously generated during encryption as is depicted in  FIG. 6 . The final decryption function D m    802   c  produces four final state variables  803  which are concatenated to form an authentication tag AT′  804 . The received authentication tag AT  805  identifies the original message that was encrypted, while the newly generated authentication tag AT′  804  identifies the received message. 
         [0082]    With the two authentication tags, an integrity check  806  may be performed as follows. If the two authentication tags are not equal, the message was modified between its encryption and decryption and should be rejected. Conversely, if the authentication tags are equal, it can be assured with high probability that the message has not been tampered with and can be accepted. It should be noted that an integrity check could also be performed using a previously generated authentication tag as in  FIG. 7 . The method for generating an authentication tag during decryption would generally match the encryption method shown in  FIG. 7  followed by an integrity check as in the present figure. 
         [0083]      FIG. 9  represents a further embodiment wherein counters are added. In the same manner as the embodiment in  FIG. 3 , m plaintext blocks P i    901  are each passed through a sequence of four pseudorandom permutations F k    903  resulting in m ciphertext blocks C i    904 . Each of the four permutations F k    903  are keyed with different keys k1, k2, k3, and k4. The embodied method includes the step of initializing the state variables  902  and counters  906  by passing a nonce  900  through a randomization function  500  that has been previously defined. Once the state variables and counters are initialized, the first plaintext block P 1    301   a  is combined with the initial state variable SV1 0    902   a  through modular 2 n  addition where n is the size of a plaintext block. The result of said combination is passed into the first pseudorandom permutation F k1    903   a  producing an intermediate cryptographic variable CV12 1  (the cryptographic variable between the first pseudorandom permutation F k1    903   a  and the second F k2    903   b ) which will be fed forward to encrypt the next plaintext block P 2    901   b . Continuing with the encryption of P 1    901   a , CV12 1  is combined with the second initialized state variable SV2 0    902   b  through modular 2 n  addition and passed into the second pseudorandom permutation F k2    903   b  resulting in CV23 1 . The encryption continues to follow the same pattern for the two remaining pseudorandom permutations F k3    903   c  and F k4    903   d  where the result of F k4    903   d  is the first ciphertext block C 1    904   a.    
         [0084]    For the encryption of the next plaintext block P 2    901   b , the state variables  905  should be updated using counters and a feedback mechanism as will be described. The first state variable SV1 1    905   a  produced following the encryption of the first plaintext block P 1    901   a  is generated by combining the previous state variable SV1 0    902   a  with the output from the previous block&#39;s third permutation CV34 1  and a counter CTR1 0    906   a  through modular 2 n  addition where n is the size of a plaintext block. The second state variable SV2 1    905   b  is generated by combining the previous state variable SV2 0    902   b  with the output from the previous block&#39;s first permutation CV12 1  and a counter CTR2 0    906   b  through modular 2 n  addition. Similarly, the third state variable SV3 1    905   c  is generated by combining the previous state variable SV3 0    902   c  with the output from the previous block&#39;s second permutation CV23 1  and a counter CTR3 0    906   c  through modular 2 n  addition. The fourth state variable SV4 1    905   d  is generated by combining the previous state variable SV4 0    902   d  with the output from the previous block&#39;s first permutation CV12 1  and the current block&#39;s first state variable SV1 1    905   a  and a counter CTR4 0    906   d  through modular 2 n  addition. The counters  906  are then incremented using function  1100 . It should be noted that the calculation of SV1 1    905   a  should occur before the calculation of SV4 1    905   d . Furthermore, while the described embodiment stores the state variables SV1, SV2, SV3, and SV4, derived embodiments could entail the same spirit of the present embodiments without actually storing the state variables. The step of storing state variables is disclosed for ease of understanding. 
         [0085]    The encryption of all further plaintext blocks P 2    901   b  through P m    901   c  are conducted in the same manner as the encryption of P 1    901   a . For example, the second plaintext block P 2    901   b  is conducted in the same manner as the encryption of the first plaintext block P 1    901   a  substituting the updated state variables  905  for the previous state variables  902 . 
         [0086]      FIG. 10  represents a decryption embodiment wherein m ciphertext blocks C i    1004  are each passed through a sequence of four inverse pseudorandom permutations  1003  resulting in m plaintext blocks P i    1001 . In this embodiment each of the four inverse permutations  1003  are keyed with the same keys used in the encryption in  FIG. 9 . The embodied method includes the step of initializing the state variables  1002  and initial counters  1006  by passing a nonce  1000  through a randomization function  500  that has been previously defined. Once the state variables and counters are initialized, the first ciphertext block C 1    1004   a  is passed into the first inverse pseudorandom permutation F k4   −1    1003   d . The result of said inverse pseudorandom permutation F k4    1003   d  is combined with the initial state variable SV4 0    1002   d  through modular 2 n  subtraction where n is the size of a ciphertext block producing an intermediate cryptographic variable CV34 1  (the cryptographic variable between F k3   −1    1003   c  and F k4   −1    1003   d ) which will be fed forward to decrypt the next ciphertext block C 2    1004   b . Continuing with the decryption of C 1    1004   a , CV34 1  is passed into the second inverse psuedorandorandom permutation F k3   −1    1003   c . The result of said inverse permutation F k3   −1    1003   c  is combined with SV3 0  using modular 2 n  subtraction producing CV23 1 . The decryption continues to follow the same pattern for the two remaining inverse pseudorandom permutations F k2   −1    1003   b  and F k1   −1    1003   a  where the result of F k3   1    1003   a  is combined with SV1 0    1002   a  using modular 2 n  subtraction to produce the first plaintext block P 1    1001   a.    
         [0087]    For the decryption of the next ciphertext block C 2    1004   b , the state variables  1005  should be updated using a feedback mechanism as will be described. The state variable SV1 1    1005   a  produced following the decryption of the first ciphertext block C 1    1004   a  is generated by combining the previous state variable SV1 0    1002   a  with the input from the previous block&#39;s second inverse permutation CV34 1  and a counter CTR1 0    1006   a  through modular 2 n  addition where n is, the size of a ciphertext block. The second state variable SV2 1    1005   b  is the output from the previous block&#39;s third inverse permutation F k2   −1    1003   b  and a counter CTR2 0    1006   b  through modular 2 n  addition. Similarly, the state variable SV3 1    1005   c  is the output from the previous block&#39;s second pseudorandom permutation F k3   −1    1003   c  and a counter CTR3 0    1006   c  through modular 2 n  addition. The state variable SV4 1    1005   d  is generated by combining the previous state variable SV4 0    1002   d  with the input from the previous blocks fourth inverse permutation CV12 1  and the current block&#39;s state variable SV1 1    1005   a  and a counter CTR4 0    1006   a  through modular 2 n  addition. The counters  1006  are then incremented using function  1100 . It should be noted that the calculation of SV1 1    1005   a  should occur before the calculation of SV4 1    1005   d . Furthermore, while the described embodiment stores the state variables SV1, SV2, SV3, and SV4, derived embodiments could entail the same spirit of the present embodiments without actually storing the state variables. The step of storing state variables is disclosed for ease of understanding. 
         [0088]    The decryption of all further ciphertext blocks C 2    1004   b  through C m    1004   c  are conducted in the same manner as the decryption of C 1    1004   a . For example, the second ciphertext block C 2    1004   b  is conducted in the same manner as the decryption of the first ciphertext block C 1    1004   a  substituting the updated state variables  1005  for the previous state variables  1002 . 
         [0089]      FIG. 11  represents an embodied method for modifying the counters from one block encipherment to the next. The method takes as input four counters CTR1 i  through CRT4 i  and produces four counters CRT1 i+1  through CRT4 i+1 . The steps taken in the embodied method model a typical mileage odometer from an automobile where CRT1 is the lowest order of magnitude and CTR4 is the highest order of magnitude. The embodied method always begins by incrementing the lowest order counter CTR1  1105  through modular 2 n  addition where n is the size of the counter in bits. If CTR1 has reset itself and is equal to zero  1110 , the embodied method continues to increment CTR2  1115  in the same manner as CTR1. If CTR1 is not zero  1110 , the method exits  1140   a  and the resulting counters are stored for use in encrypting or decrypting the next block. Each subsequent counter may be incremented in the same manner as long as all lower order counters are equal to zero. 
         [0090]      FIG. 12  represents an embodiment of the encryption system using an alternative feedback mechanism to that shown in  FIG. 3 . The embodiment shown in  FIG. 12  is similar to that shown in  FIG. 3  and similar elements are similarly numbered. However, the second state variable SV2 1    1205   b  of  FIG. 12  is generated in a different manner. In this embodiment, SV2 1    1205   b  is generated by combining the previous state variable SV2 0    1202   b  with the output from the previous block&#39;s first permutation CV12 1  and the current block&#39;s fourth state variable SV4 1    1205   d  through modular 2 n  addition. It should be noted that the calculation of SV4 1    1205   d  should be available before the calculation of SV2 1    1205   b . Including this feedback mechanism allows the fourth state variable SV4 to influence the next state of the other state variables. This feedback may increase the strength of the cipher by providing an increase in the periodicity of the state variables. 
         [0091]    The encryption embodiment may also include a step for initializing the state variables  1202  by passing a nonce  1210  through a randomization function  1600  that is discussed in detail below. 
         [0092]      FIG. 13  represents an embodiment of the decryption system using an alternative feedback mechanism to that shown in  FIG. 4 . The embodiment shown in  FIG. 13  is similar to that shown in  FIG. 4  and where suitable similar elements are similarly numbered. In order to decrypt and authenticate messages encrypted by the embodiment shown in  FIG. 12 , the decryption embodiment has a similar feedback mechanism for calculating the state variables. The second state variable SV2 1    1305   b  is generated by combining the output of the previous block&#39;s third inverse permutation Fk 2   −1    1303   b  and the current block&#39;s state variable SV4 1    1305   d . It should be noted that the calculation of SV4 1    1305   d  should be available before the calculation of SV2 1    1305   b.    
         [0093]    Similar to the encryption embodiment, the decryption embodiment may also include a step for initializing the state variables  1302  by passing a nonce  1310  through a randomization function  1600  that is discussed in detail below. 
         [0094]      FIG. 14  represents an embodiment of the encryption system of  FIG. 12  where an LFSR is incorporated into the cipher. The incorporation of the LFSR prevents the state of the cipher from cycling before the state of the LFSR cycles. The size of the LFSR may be arbitrary. The embodiment shown in  FIG. 14  is similar to that shown in  FIG. 12  and similar elements are similarly numbered. The embodiment in  FIG. 14  uses the LFSR in the feedback mechanism of the third state variable SV3 1    1405   c . In this embodiment, SV3 1    1405   c  is generated by combining the previous state variable SV3 0    1402   c  with the output from the previous block&#39;s second permutation CV23 1  and the LFSR  1406  through modular 2 n  addition. 
         [0095]    If the LFSR is larger than n, the size of the plaintext blocks, then n bits may be used from the LFSR in the modular 2 n  addition. Either the upper or lower n bits may be used for simplicity. The LFSR  1406  may then be clocked, at least once, prior to the next use in calculation of state variable SV3 1 . The LFSR  1406  may be clocked using a Galois configuration. 
         [0096]    The feedback configuration shown in  FIG. 14  using an LFSR is similar to that shown in  FIG. 9  using counters. Using an LFSR tends to be a more efficient hardware solution than the counter approach shown in  FIG. 9  because LFSR themselves are more efficient in hardware and, due to the nature of the LFSR sequence, fewer of the state variables need to use the LFSR in the feedback mechanism. Although only one LFSR feedback is shown in  FIG. 14 , other embodiments could use the LFSR feedback in the feedback path of multiple or different state variables. 
         [0097]    The encryption embodiment may also include a step for initializing the state variables  1402  and LFSR  1406  by passing a nonce  1410  through a randomization function  1600  that is discussed below. 
         [0098]      FIG. 15  represents an embodiment of the decryption system where an LFSR is incorporated into the cipher. The embodiment shown in  FIG. 15  is similar to that shown in  FIG. 13  and where suitable similar elements are similarly numbered. In order to decrypt and authenticate messages encrypted by the embodiment shown in  FIG. 14 , the decryption embodiment has a similar feedback mechanism for calculating the state variables using an LFSR. The third state variable SV3 1    1505   c  is generated by combining the output of the previous block&#39;s second inverse permutation Fk 3   −1    1503   c  and  n  bits from the LFSR  1506  through modular 2 n  addition. The LFSR should then be clocked in the similar manner to the encryption embodiment used. 
         [0099]      FIG. 16  illustrates an embodiment for initializing variables using a nonce. The purpose is to initialize the state variables and LFSR to unique and unpredictable values that are used in the initial setup for both the encryption and decryption methods. In some embodiments, the nonce or input to the function may be a random number, an incrementing counter, or any value as long as it has not been used before in the context of a given key(s). It should be noted that the nonce need not be secret. The initialization function parses the nonce into m blocks V i    1609  that is used to populate the state variable registers  1602 . Padding may be necessary in order to facilitate equal sized blocks. The number of blocks m and the number of pseudorandom permutations m should always be the same. In the embodiment of the initialization function shown in  FIG. 16  m is equal to 4. The randomization function keys each of the four permutations F k    1603  with different keys k1, k2, k3, and k4. 
         [0100]    The input to the first pseudorandom permutation N i    1601  can be defined as the sum of the initial state variable SV1 ni    602   a +SV3 ni    1602   c  or any combination of the state variables. If an argument, in addition to the nonce, is passed to the said function, then this value may also be incorporated into the calculation of N i    1601  using mod 2 n  addition. 
         [0101]    Once the state variables  1602  are populated and the N 1    1601   a  calculation is complete, the first block N 1    1601   a  is combined with the initial state variable SV1 n1    1602   a  through modular 2 n  addition where n is the size of a block. The result of the combination is passed into the first pseudorandom permutation F k1    1603   a  producing an intermediate cryptographic variable CV12 1  (the cryptographic variable between the first pseudorandom permutation F k1    1603   a  and the second F k2    1603   b ) which will be fed forward to encrypt the next block N 2    1601   b . Continuing with the randomization function of N 1    1601   a , CV12 1  is combined with the second initialized state variable SV2 n1    1602   b  through modular 2 n  addition and passed into the second pseudorandom permutation F k2    1603   b  resulting in CV23 1 . The randomization continues to follow the same pattern for the two remaining pseudorandom permutations F k3    1603   c  and F k4    1603   d  where the result of F k4    1603   d  is the first LFSR n1    1604   a  value. It should be noted that some embodiments may not use all or any of the generated LFSR  1604  values. 
         [0102]    For the next block N 2    1601   b , the state variables  1605  should be updated using a feedback mechanism as will be described. In comparison with the nonce randomization embodiment shown in  FIG. 5 , the feedback mechanism provided in the embodiment of  FIG. 16  is simpler and easier to implement. Since the results of this encryption method are never revealed, that is, it is either discarded or used to populate the LFSR, the simpler feedback mechanism may be used to more efficiently randomize the nonce generally without any cryptographic vulnerability. The first state variable SV1 n2    1605   a  produced following the randomization of the first block N 1    1601   a  is generated by combining the previous state variable SV1 n1    1602   a  with the output from the previous block&#39;s fourth permutation LFSR n1    1604   a  through modular 2 n  addition where n is the size of a block. The second state variable SV2 n2    1605   b  is generated by combining the previous state variable SV2 n1    1602   b  with the output from the previous block&#39;s first permutation CV12 1  through modular 2 n  addition. Similarly, the third state variable SV3 n2    1605   c  is generated by combining the previous state variable SV3 n1    1602   c  with the output from the previous block&#39;s second permutation CV23 1  through modular 2 n  addition. Similarly, the fourth state variable SV4 n2    1605   d  is generated by combining the previous state variable SV4 n1    1602   d  with the output from the previous block&#39;s third permutation CV34 1  through modular 2 n  addition. N 2    1601   b  may now be updated by combining SV1 n2    1605   a  and SV3 n2    1605   c  using modular 2 n  addition. It should be noted that SV1 n2  and SV3 n2  should be available before the calculation of N 2    1601   b . Furthermore, while the described embodiment stores the state variables SV1, SV2, SV3, and SV4, derived embodiments could entail the same spirit of the present embodiments without actually storing the state variables. The step of storing state variables is disclosed for ease of understanding. 
         [0103]    The randomization of all further plaintext blocks N 2    1601   b  through N 4    16011  may be conducted in the same manner as the randomization of N 1    1601   a . For example, the second plaintext block N 2    1601   b  is randomized in the same manner as the randomization of the first plaintext block N 1    1601   a  substituting the updated state variables  1605  for the previous state variables  1602 . After the four blocks  1601  are each randomized, the resulting state variables SV1 0 , SV2 0 , SV3 0 , and SV4 0    1608  may be used as initial state variables for the encryption or decryption embodiments. Similarly, the resulting randomized values, LFSR n1 , LFSR n2 , LFSR n3 , and LFSR n4    1604  may be used as initial LFSR for  FIG. 14  or  15 . An LFSR register  1604  with a state of zero can be avoided by setting one or more of the bits in the register before clocking. The LFSR  1604  may be clocked at least once before being used in  FIG. 14  or  15 . 
         [0104]      FIG. 17  illustrates an embodiment wherein the authentication tag is generated from the final state variables. The encryption methods described above are represented as encryption function E t+i    1703  taken at time t. In this case time t represents the condition of the state variables SV1, SV2, SV3, SV4, LFSR1, and LFSR2  1701   a  after encrypting the final plaintext character. It should be noted that the nonce initialization is not necessary in the said encryption function  1703  since that would have occurred before encrypting the first plaintext character. 
         [0105]    The method for generating the authentication tag begins by advancing the state variables to a condition that bears no resemblance to the condition of the state variables at time t. This is referred to as creating distance. The distance is accomplished be summing the state variables SV1 t+i  and SV3 t+i    1702  using modular 2 n  addition and inputting the result into the encryption function  1703  in the place of the plain text. The encryption operation causes the state variables to change state, therefore creating distance, and creates ciphertext C t+i    1704  that may be discarded. This process is iterated three more times, however in other embodiments it may be advantageous to iterate fewer times or more times. 
         [0106]    After creating distance, a snapshot of the state variables  1701   e  taken at time t+i, where i represents the number of encryption iterations which in this embodiment is 4. Each of the state variables in the snapshot SV1 t+4 , SV2 t+4 , SV3 t+4 , SV4 t+4 , LFSR1 t+4 , LFSR2 t+4 ,  1701   e  is input into the encryption function  1703  resulting in an authentication tag AT  1705  that represents all of the state variables. As explained, an authentication tag is used to provide an integrity check on encrypted data. Alternate embodiments may generate the authentication tag  1705  by using any permutation or combination of the encrypted state variables. Alternative embodiments may also choose to encrypt the final state variables in a different order than that shown in  FIG. 17 . 
         [0107]      FIG. 18  illustrates an embodiment of a method for decrypting and verifying the integrity of a message using a received authentication tag. The decryption methods described above are represented by decryption function D i    1802 . The embodiment shown in  FIG. 18  is using the decryption process  1500  described with respect to the embodiment shown in  FIG. 15 . 
         [0108]    The received message to be decrypted includes the ciphertext C i    1801  along with an authentication tag AT  1805 . The embodiment shown in  FIG. 18  is configured to use the same process for generating an authentication as the embodiment shown in  FIG. 17 . As each decryption function D i    1802  decrypts the corresponding ciphertext C i    1801  the state variables are passed to each subsequent decryption function. The final state variables  1803  output from the decryption function may then be used to generate an authentication tag. The process of generating the authentication tag AT′  1804  is represented as process  1700  as described in the embodiment of  FIG. 17 . 
         [0109]    The received authentication tag AT  1805  identifies the original message that was encrypted, while the newly generated authentication tag AT′  1804  identifies the received message. With the two authentication tags, an integrity check  1806  is performed. The integrity check determines whether the two authentication tags are equal, if they are not equal the message may have been modified between its encryption and decryption and the message should be rejected. Conversely, if the authentication tags are equal, it can be assured with high probability that the message has not been tampered with and can be accepted. 
         [0110]    HG.  19  illustrates a hardware embodiment of a combined encryption and decryption engine for performing encryption/decryption and authentication as described above. The system  1900  is capable of performing both encryption and decryption along with generating and verifying the authentication tag. While the system  1900  is shown as a number of discrete blocks or modules, each may be implemented together with other blocks in either software or hardware. Each of these blocks may provide control logic, memory elements, and data path functions, either in whole or in part. 
         [0111]    The register or storage blocks are memory elements that may be used to store state variable inputs and outputs. In a hardware implementation, such as an ASIC or FPGA, these blocks may be hardware registers composed of flip-flops or other memory known memory elements such as various RAM implementations or register files. In a software implementation the memory elements may be any memory accessible by a processor for storing program data. 
         [0112]    The control logic is shown as a controlling finite state machine  1901  that responsible for controlling the various blocks of the system  1900  depending on the desired function. In some embodiments, the control logic  1901  may be implemented as a state machine in ASIC or FPGA, or in a software implementation, a microprocessor running specific software to implement the encryption/decryption functions. The connections between the control logic  1901  and the other modules are omitted from  FIG. 19  for simplicity. The control logic  1901  determines the function of the system  1900 , for example, whether the function is encrypting, decrypting, initialiazing or authenticating received data. Depending on the function, the control logic  1901  controls the state of the various logic blocks including whether the block is active or what function it is performing. For example, the finite state machine may indicate to the encryption/decryption logic that it should be in the encryption state and selecting the appropriate key. 
         [0113]    Although the diagram shows a centralized finite state machine  1901 , the control logic may also be distributed among various blocks within the system. As shown in  FIG. 19 , the initialization logic  1903  may also be considered control logic and is responsible for controlling the initialization of the system  1900 , however, part of this functionality could also be contained within the finite state machine  1901 . In a microprocessor-based implementation, some or all of this additional control logic distributed in  FIG. 19  may be embodied in the specific software running on the microprocessor in order to operate the encryption/decryption system. 
         [0114]    The function of the initialization logic  1903  is to generate initial values for the state variables  1905  and, if used, an LFSR or counter  1906 . The initialization logic  1903  uses a nonce  1904  that may be a random number, an incrementing counter, or any other value as long as it has not been used before with a given key. The nonce block  1904  may also contain the appropriate hardware to select another unique value sometime after the current nonce has been used. 
         [0115]    The initialization logic  1903  populates the state variable registers with the nonce  1904  by parsing the nonce similarly to the process described with respect to  FIG. 16 . The initialization logic  1903  may then calculate part of the input to the pseudorandom permutation logic  1902  similar to the calculations used to generate each of the N i  as described with respect to  FIG. 16 . 
         [0116]    Next, the initialization logic  1903  indicates to the pseudorandom permutation logic  1902  to select the inputs to the permutation function, this includes the key and the input data. According to the nonce randomization described with respect to  FIG. 16 , in the first stage the input data to the permutation function is the N i  variable combined with the initial state variable SV n1  through modular 2 n  addition. The output from the pseudorandom permutation function is stored in the appropriate intermediate cryptographic variable register  1907  as selected by either the initialization logic  1903  or the control logic  1901 . The initialization logic then repeats this process for each of the state variables, selecting the appropriate key and input data for the permutation function. The output from the final permutation function may be used to seed the LFSR  1906 . The feedback logic  1908 , under the control of either the finite state machine  1901  or the initialization logic  1903 , selects the appropriate combination of the intermediate cryptographic variables and current state variables to generate the next value of the state variable registers  1905 . The above process may then be repeated to either fill the LFSR  1906  or to create the desired distance from the nonce  1904 . 
         [0117]    After initialization, the system  1900  is ready to encrypt plaintext blocks. The controller  1901  selects plaintext input  1910  in appropriately sized blocks as input to the pseudorandom permutation function  1902  and selects one of the keys  1911 . The controller  1901  also selects the appropriate state variable as input to the pseudorandom permutation logic  1902  from the state variable registers block  1905 . The output from the pseudorandom permutation logic  1902  is then stored in one of the intermediate cryptographic variable registers  1907  as selected by the controller  1901 . This process may then be repeated using the state variables and the previously generated cryptographic variables as input to the pseudorandom permutation logic  1902 . The output from the final iteration of the pseudorandom permutation logic  1902  is the first ciphertext block that corresponds to the plaintext input. Under direction from the controller  1901 , the ciphertext block will be transmitted to ciphertext output block  1912 . 
         [0118]    After a plaintext block has been encrypted, the system  1900  should update the state variable registers  1905 . The control logic  1901  passes the intermediate cryptographic variables  1907  and the state variable registers  1905  to the feedback logic block  1908 . The output from feedback logic block  1908  is then use to update the state variable registers  1905 . The feedback logic may be configured to implement the modulo addition feedback mechanism discussed above. The LFSR  1906  may also be included as an input to the feedback mechanism, and the controller  1901  should clock the LFSR sometime after the current LFSR value has been used. Once the state variable registers  1905  have been updated, the system  1900  is ready to begin encrypting the next plaintext from plaintext input block  1910 . 
         [0119]    The system  1900  may also generate an authentication tag  1914  based on the previously encrypted plaintext so that a recipient of the ciphertext may be provided some assurance that the ciphertext has not been altered. This authentication logic  1913  may control the authentication tag generation process, or in alternative embodiments, this authentication tag generation process may be encompassed in the control logic  1901 . The authentication logic  1913  may employ the methods shown in  FIG. 6 ,  FIG. 7 , or  FIG. 17 . Implementing the approaches shown in  FIGS. 6 and 7  involve the authentication logic  1913  concatenating the state variables into the authentication tag  1914 , with or without masking. Implementing the approach shown in  FIG. 17  generally requires either the authentication logic  1913  or the controller  1901  to further encrypt the state variables to create distance from the post-encryption value of the state variables. The authentication logic  1913  or the control logic  1901  may further encrypt these state variables prior to concatenation in the authentication tag  1914 . 
         [0120]    The authentication logic  1913  is also responsible for verifying the integrity of decrypted messages. The decryption function of the system  1900  is carried out in a similar manner to encryption as discussed above. The control logic  1901  selects the state variables  1905 , the LFSR  1906  and the ciphertext input  1910  to the pseudorandom permutation logic  1902 . After decrypting all of the received ciphertext blocks, the authentication logic  1913  will generate an authentication tag  1914  as described above and compare the generated authentication tag  1914  to the authentication tag received with the ciphertext. 
         [0121]    When decrypting, if the system  1900  is not synchronized with the encrypting transmitter, the initialization logic  1903  may also be used to initialize the state variable registers  1905  and the LFSR  1906  prior to decryption operations. 
         [0122]      FIG. 20  illustrates a hybrid mode of operation  2000  of an encryption engine shown encrypting a 40-bit plaintext message. The encryption engine operates on fixed block sizes of 16-bits that require the plaintext message to be divided into plaintext blocks of 16-bits. This results in plaintext blocks PT 0-15    2010  and PT 16-31    2011  representing the first 32 bits of the 40-bit plaintext message. The encryption engine will encrypt the PT 0-15    2010  through encryption operation  2020 , as described above, to generate ciphertext CT 0-15    2030 . Similarly, ciphertext CT 16-31    2031  is generated through encryption operation  2021 . Since the plaintext message is not evenly divisible by the fixed block size of the encryption operation, the final 8 bits of the plaintext message, PT 32-39    2040  cannot be encrypted directly using the above described encryption operation. 
         [0123]    The mode of operation illustrated in  FIG. 20  is described as a hybrid mode of operation because it is able to operate on fixed block sizes, similar to a block cipher, and also on sub-blocks less than the fixed blocks size similar to a stream cipher. Stream ciphers generally create a keystream that is bit-wise XORed with the plaintext bits to generate the ciphertext bits. The hybrid mode of operation generates a keystream by encrypting at least one of the state variables of the encryption engine or an agreed upon constant. The keystream may also be generated by encrypting a combination of state variables, such as state variable 1 and state variable 3, as shown in keystream generation step  2070 . The keystream generation step  2070  generates a 16-bit word of keystream data. The ciphertext bits CT 32-39    2060  are generated by a bit-wise XOR function  2050  that combines plaintext bits PT 32-39    2040  with the output of the keystream generation step  2070 . The 8 least significant bits of the keystream data may be combined by the XOR function with the least significant bits of plaintext bits PT 32-39    2040 . 
         [0124]    Next, plaintext sub-block PT 32-39    2040  is cast as a 16-bit integer and input into the encryption engine at step  2080 . This allows plaintext sub-block PT 32-39    2040  to influence the state variables of the encryption engine so that when the authentication tag  2095  is generated in step  2090 , it will detect modification of ciphertext CT 32-39 . Other transformations may be performed on the plaintext sub-block to convert it to the fixed block size of the encryption engine. 
         [0125]      FIG. 21  illustrates a hybrid mode of operation  2100  of a decryption engine shown decrypting a 40-bit plaintext message. Ciphertext blocks CT 0-15    2110  and CT 16-31    2111  represent the first 32 bits of the 40-bit ciphertext message that is to be decrypted. The decryption engine will decrypt CT 0-15    2110  through decryption operation  2120 , as described above, to generate plaintext block PT 0-15    2130 . Plaintext block PT 15-31    2131  is generated similarly. The final 8 bits of the ciphertext message, sub-block CT 32-39    2140 , should be decrypted using the same keystream that was generated for encryption. It should be noted that the encryption engine used to generate the keystream  2070  in the encryption process shown in  FIG. 20  is the same encryption engine used to generate the keystream  2170  in the decryption process shown in  FIG. 21 . This is generally required in order to recover the plaintext in the final sub-block. Moreover, the recovered plaintext of the final sub-block  2160  is also encrypted  2180  in order to facilitate the generation of the authentication tag  2195 . If the message is genuine then authentication tag  2095  shown in  FIG. 20  and authentication tag  2195  shown in  FIG. 21  should be identical. 
         [0126]      FIG. 22  illustrates an embodiment wherein the authentication tag is generated using a nonce as input to the encryption engine. Using a nonce as input to the encryption function provides increased resistance to collision or birthday attacks. Associating a nonce with each message results in an authentication tag that is not only dependent upon the state of the encryption engine but also the nonce. In practice, this decreases the probability that any two separate messages will share identical authentication tags. 
         [0127]    The encryption methods described above are represented as encryption function E 1+i    2203  taken at time t. In this case time t represents the condition of the state variables SV1, SV2, SV3, SV4, and LFSR  2201   a  after encrypting the final plaintext block or sub-block. It should be noted that the nonce initialization shown in  FIG. 22  is performed in addition to the nonce initialization of the encryption function, such as that described with respect to  FIG. 5  and  FIG. 16 , for instance, for generating initial state variables of the encryption function. 
         [0128]    The nonce used in the  FIG. 22  is divided up by the block size of the encryption function  2203  into nonce blocks nonce 0    2202   a , nonce 1    2202   b , nonce 2    2202   c  and nonce 3    2202   d . The method for generating the authentication tag begins by encrypting the first word of the nonce 0    2202   a  and then discarding the resulting ciphertext  2204   a . This step is repeated two more times or until the next to the last block of the nonce, nonce 2    2202   c , is encrypted. The ciphertext  2204   a - c  is discarded. The repetition is to allow each bit of the nonce to influence the generation of the authentication tag. In the embodiment shown in  FIG. 22 , nonce 3    2202   d , the last word of the nonce, is used to generate the first word of the authentication tag  2205  since at this point every bit in the nonce has influenced the state of the encryption function. If a longer authentication tag is requested, the tag generation may continue by once again encrypting the nonce starting with nonce 0    2202   a  and continuing until the length of the authentication tag is the size requested. Other embodiments may use a smaller or larger nonce, and may also process the nonce blocks in any order. Alternative embodiments may also choose to encrypt additional data, either in place of the nonce or in addition to the nonce, in order to authenticate the additional data. For example header information may be encrypted if it is advantageous to authenticate the header information along with the ciphertext. 
         [0129]      FIG. 23  represents an alternative embodiment of the encryption system of  FIG. 3  where accumulators are used within each pseudorandom permutation. In this embodiment, one accumulator is associated with each pseudorandom permutation. The incorporation of the accumulators has the net effect of increasing the size of the state. The embodiment shown in  FIG. 23  is similar to that shown in  FIG. 3  and where suitable similar elements are similarly numbered. The embodiment in  FIG. 23  uses the accumulator variable ACC1  2306   a  to accumulate the changes in SV1 by using modular 2 n  addition. Similarly variable ACC2  2306   b  accumulates SV2, ACC3  2306   c  accumulates SV3, and ACC4  2306   d  accumulates SV4. Each accumulator value may be used within all of the pseudorandom permutation functions Fk. 
         [0130]    This embodiment also illustrates the use of adding a whitener to the output of the last permutation  2303 . This is accomplished by summing the output of the last pseudorandom permutation  2303  with SV1  2302  using modular 2 n  addition. 
         [0131]    In addition to expanding the state space, the accumulators may be used to modify the key inside one or more of the pseudorandom permutations. For example, in this case the accumulators are modifying the key in the second pseudorandom permutation  2303   b  and the third pseudorandom permutation  2303   c.    
         [0132]    The encryption embodiment may also include a step for initializing the state variables  2302  and accumulator variables  2306  by passing a nonce through a randomization function similar to that of  500  with the accumulators accumulating the changes in the state variables  502  in the manner as is done in  FIG. 23 . 
         [0133]    In some embodiments, decryption may be performed in using a decryption system corresponding to the encryption system shown in  FIG. 23 . 
         [0134]      FIG. 24  illustrates the equations for the encryption, decryption, and internal state updating process as illustrated in  FIG. 23 . 
         [0135]    Turning now to  FIG. 25 , illustrated therein is an embodiment of a system  2500  wherein the authentication tag is generated using a nonce as input to the encryption engine and the internal state is expanded by the inclusion of accumulators. Using a nonce as input to the encryption function provides increased resistance to collision or birthday attacks. Associating a nonce with each message results in an authentication tag that is not only dependent upon the state of the encryption engine but also the nonce. In practice, this decreases the probability that any two separate messages will share identical authentication tags. 
         [0136]    The encryption methods described above are represented as encryption function E t+i    2503  taken at time t. In this case time t represents the condition of the state variables SV1, SV2, SV3, SV4, and accumulator variables ACC1, ACC2, ACC3, ACC4,  2201   a  after encrypting the final plaintext block or sub-block. 
         [0137]    The nonce used in the  FIG. 25  is divided up by the block size of the encryption function  2503  into nonce blocks nonce 0    2502   a , nonce 1    2502   b , nonce 2    2502   c  and nonce;  2502   d . The method for generating the authentication tag begins by encrypting the sum of the authentication tag length, SV1 t , SV3 t  and the first word of the nonce 0    2502   a  using modular 2 n  addition. Including the authentication tag length in the first encryption block helps prevent length extension attacks. The result of the encryption is discarded  2504   a . This step is repeated two more times or until the next to the last block of the nonce, nonce 2    2502   c , is encrypted. The ciphertext  2504   a - c  is discarded. The repetition is to allow each bit of the nonce to influence the generation of the authentication tag. 
         [0138]    In the embodiment shown in  FIG. 25 , nonce 3    2502   d , the last word of the nonce, is used to generate the first word of the authentication tag  2505  since at this point every bit in the nonce has influenced the state of the encryption function. Encrypting the sum of SV1 and SV3 taken at time t generates the remainder of the words of the authentication tag  2505 . This process continues until the desired length of the tag is achieved. The length of the tag should be equal to or less than the size of the internal state, including accumulators. Alternative embodiments may also choose to encrypt additional data, either in place of the nonce or in addition to the nonce, in order to authenticate the additional data. For example header information may be encrypted if it is advantageous to authenticate the header information along with the ciphertext. 
         [0139]    In one embodiment, a method for encrypting a plaintext message comprises receiving at least one plaintext message, wherein the plaintext message forms at least one plaintext block, encrypting said plaintext block by applying 2 or more pseudorandom permutations to each block, and modifying an input to each said pseudorandom permutation by at least one state variable which is modified for each plaintext block by at least one of previously generated permutation outputs, previously generated permutation inputs, ciphertext, and plaintext. The method comprises generating at least one ciphertext block from the output of each plaintext block&#39;s final pseudorandom permutation, partitioning the plaintext message into a plurality of equal size plaintext blocks, padding the plaintext message to facilitate the equal sized plaintext blocks, wherein the modification of the state variables comprises at least one of: modifying the state variable for a first pseudorandom permutation by an output of a next to the last pseudorandom permutation from the previous block, modifying the state variable for a final permutation by an output of the first pseudorandom permutation from the previous block and the state variable for the first pseudorandom permutation from the current block, and modifying the state variables for all other pseudorandom permutations by an output of the preceding pseudorandom permutation from the previous block, wherein the state variables are modified using at least one of modular 2 n  addition and modular 2 n  subtraction wherein n represents the size of a block, and wherein the state variables are modified using a bitwise exclusive or (XOR). 
         [0140]    The method comprises initializing the state variables before encrypting the first plaintext block by randomizing a nonce and padding the nonce in order to facilitate the initialization of the state variables, wherein the initialized state variables are unique from other initialized state variables in a context of a session key, wherein the number of pseudorandom permutations determines the number of state variables, wherein the pseudorandom permutations are at least one of: block ciphers, keyed substitution tables, S-Boxes, and rotors, wherein each pseudorandom permutation is keyed by at least one different key, wherein each pseudorandom permutation is keyed by a same key, wherein a portion of the pseudorandom permutations may be substituted for the inverses of a remaining portion of the pseudorandom permutations, and wherein the pseudorandom permutations and inverse pseudorandom permutations may be arranged in any order. 
         [0141]    The method comprises generating an authentication tag from a combination of the state variables, wherein the generation includes concatenating the resulting state variables after the encryption of the final plaintext block, wherein the generation includes concatenating the resulting state variables after the encryption of a chosen plaintext block, wherein the generation includes concatenating the resulting state variables after the encryption of the final plaintext block, concatenating the initial state variables, and combining the two sets of concatenated, variables through an exclusive or (XOR), comprises attaching the authentication tag to a ciphertext message, wherein the number of state variables determines the size of the authentication tag, and comprises modifying the input to a pseudorandom permutation by at least one counter, and initializing the counters before encrypting the first plaintext block by randomizing a nonce. 
         [0142]    In another embodiment, an apparatus for encrypting a plaintext message comprises logic to form at least one nonce block from at least one nonce, memory to store at least one state variable, an initializer to set the at least one state variable to at least one initial value, wherein the logic is coupled to the memory and to the initializer, wherein the logic includes at least two pseudorandom permutations to sequentially randomize each nonce block, wherein the logic combines the at least one state variable with inputs to the pseudorandom permutations, and wherein the logic generates the at least one state variable of a current nonce block from at least one of: state variables of a previous nonce block, outputs from the previous nonce block&#39;s pseudorandom permutations, and inputs to the previous nonce block&#39;s pseudorandom permutations, wherein the memory stores outputs of final pseudorandom permutations as initial values to use in an encryption or decryption, wherein the memory stores final state variables as initial values for use in an encryption or decryption, wherein the logic adds at least one bit of padding to the nonce to generate equal sized nonce blocks, wherein the number of pseudorandom permutations is equal to the number of nonce blocks and the number of state variables, wherein the pseudorandom permutations are at least one of: block ciphers, keyed substitution tables, S-Boxes, and rotors, wherein a portion of the pseudorandom permutations may be substituted for inverses of a remaining portion of the pseudorandom permutations. 
         [0143]    In a further embodiment, a computer readable medium comprising instructions for: receiving at least one plaintext message, wherein the plaintext message forms at least one plaintext block, encrypting said plaintext block by applying 2 or more pseudorandom permutations to each block, modifying an input to the pseudorandom permutations by at least one state variable, modifying the at least one state variable after each plaintext block is encrypted for use in encrypting a next plaintext block, modifying the at least one state variable for a first pseudorandom permutation by an output of a next to last pseudorandom permutation from a previous block, modifying the at least one state variable for a final permutation by an output of the first pseudorandom permutation from the previous block and the at least one state variable for the first pseudorandom permutation from the current block, and modifying the at least one state variable for all other pseudorandom permutations by an output of a preceding pseudorandom permutation from the previous block. 
         [0144]    The computer readable medium comprises instructions for initializing the at least one state variable before encrypting a first plaintext block by randomizing a nonce, modifying the input to a pseudorandom permutation by an internal counter, generating an authentication tag from a combination of the state variables, generating at least one ciphertext block from an output of each plaintext block&#39;s final pseudorandom permutation, wherein the pseudorandom permutations are at least one of: block ciphers, keyed substitution tables, S-Boxes, and rotors. 
         [0145]    Although an exemplary embodiment of the system has been illustrated in the accompanied drawings and described in the foregoing detailed description, it will be understood that the invention is not limited to the embodiments disclosed, but is capable of numerous rearrangements, modifications, and substitutions without departing from the spirit of the invention as set forth and defined by the following claims. For example, the capabilities of the invention can be performed fully and/or partially by one or more of the elements. Also, these capabilities may be performed in the current manner or in a distributed manner and on, or via, any device able to provide and/or receive information. Further, although depicted in a particular manner, various modules or blocks may be repositioned without departing from the scope of the current invention. Still further, although depicted in a particular manner, a greater or lesser number of modules and connections can be utilized in order to provide additional known features, and/or provide greater efficiency. Also, the information sent between various modules can be sent between the modules via at least one of a wireless source, and a wired source and via plurality of protocols.