Encrypting a plaintext message with authenticaion

Abstract

An encryption and authentication technique that achieves enhanced integrity verification through assured error-propagation using a multistage sequence of pseudorandom permutations. The present invention generates intermediate data-dependent cryptographic variables at each stage, which are systematically combined into feedback loops. The encryption technique also generates an authentication tag without any further steps that is N times longer than the block size where N is the number of pseudorandom permutations used in the encipherment of each block. The authentication tag provides a unique mapping to the plaintext for any number of plaintext blocks that is less than or equal to N. In addition to being a stand alone encryption algorithm, the disclosed technique is applicable to any mode that uses pseudorandom permutations such as, key dependent lookup tables, S-Boxes, and block ciphers such as RC5, TEA, and AES.

1 . A method for encrypting a plaintext message, comprising:
 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.   
   
   
       2 . The method of  claim 1 , comprising generating at least one ciphertext block from the output of each plaintext block's final pseudorandom permutation. 
   
   
       3 . The method of  claim 1 , comprising partitioning the plaintext message into a plurality of equal size plaintext blocks. 
   
   
       4 . The method of  claim 3 , comprising padding the plaintext message to facilitate the equal sized plaintext blocks. 
   
   
       5 . The method of  claim 1 , 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.   
   
   
       6 . The method of  claim 5 , 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. 
   
   
       7 . The method of  claim 5 , wherein the state variables are modified using a bitwise exclusive or (XOR). 
   
   
       8 . The method of  claim 1 , comprising initializing the state variables before encrypting the first plaintext block by randomizing a nonce. 
   
   
       9 . The method of  claim 8 , comprising padding the nonce in order to facilitate the initialization of the state variables. 
   
   
       10 . The method of  claim 8 , wherein the initialized state variables are unique from other initialized state variables in a context of a session key. 
   
   
       11 . The method of  claim 1 , wherein the number of pseudorandom permutations determines the number of state variables. 
   
   
       12 . The method of  claim 1 , wherein the pseudorandom permutations are at least one of: block ciphers, keyed substitution tables, S-Boxes, and rotors. 
   
   
       13 . The method of  claim 1 , wherein each pseudorandom permutation is keyed by at least one different key. 
   
   
       14 . The method of  claim 1 , wherein each pseudorandom permutation is keyed by a same key. 
   
   
       15 . The method of  claim 1 , wherein a portion of the pseudorandom permutations may be substituted for the inverses of a remaining portion of the pseudorandom permutations. 
   
   
       16 . The method of  claim 15 , wherein the pseudorandom permutations and inverse pseudorandom permutations may be arranged in any order. 
   
   
       17 . The method of  claim 1 , comprising generating an authentication tag from a combination of the state variables. 
   
   
       18 . The method of  claim 17 , wherein the generation consists of concatenating the resulting state variables after the encryption of the final plaintext block. 
   
   
       19 . The method as defined in  claim 17 , wherein the generation consists of concatenating the resulting state variables after the encryption of a chosen plaintext block. 
   
   
       20 . The method of  claim 17 , wherein the generation consists of 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). 
   
   
       21 . The method of  claim 17 , comprising attaching the authentication tag to a ciphertext message. 
   
   
       22 . The method of  claim 17 , wherein the number of state variables determines the size of the authentication tag. 
   
   
       23 . The method of  claim 1 , comprising modifying the input to a pseudorandom permutation by at least one counter. 
   
   
       24 . The method of  claim 23 , comprising initializing the counters before encrypting the first plaintext block by randomizing a nonce. 
   
   
       25 . An apparatus for encrypting a plaintext message, comprising:
 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's pseudorandom permutations, and inputs to the previous nonce block's pseudorandom permutations.   
   
   
       26 . The apparatus of  claim 25 , wherein the memory stores outputs of final pseudorandom permutations as initial values to use in an encryption or decryption. 
   
   
       27 . The apparatus of  claim 25 , wherein the memory stores final state variables as initial values for use in an encryption or decryption. 
   
   
       28 . The apparatus of  claim 25 , wherein the logic adds at least one bit of padding to the nonce to generate equal sized nonce blocks. 
   
   
       29 . The apparatus of  claim 25 , wherein the number of pseudorandom permutations is equal to the number of nonce blocks and the number of state variables. 
   
   
       30 . The apparatus of  claim 25 , wherein the pseudorandom permutations are at least one of: block ciphers, keyed substitution tables, S-Boxes, and rotors. 
   
   
       31 . The apparatus of  claim 25 , wherein a portion of the pseudorandom permutations may be substituted for inverses of a remaining portion of the pseudorandom permutations. 
   
   
       32 . 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.   
   
   
       33 . The computer readable medium of  claim 32  comprising instructions for initializing the at least one state variable before encrypting a first plaintext block by randomizing a nonce. 
   
   
       34 . The computer readable medium of  claim 32  comprising instructions for modifying the input to a pseudorandom permutation by an internal counter. 
   
   
       35 . The computer readable medium of  claim 32  comprising instructions for generating an authentication tag from a combination of the state variables. 
   
   
       36 . The computer readable medium of  claim 32  comprising instructions for generating at least one ciphertext block from an output of each plaintext block's final pseudorandom permutation. 
   
   
       37 . The computer readable medium of  claim 32 , wherein the pseudorandom permutations are at least one of block ciphers, keyed substitution tables, S-Boxes, and rotors.