HK1081020A - Efficient encryption and authentication for data processing systems - Google Patents

Description

Efficient encryption and authentication for data processing systems

Background

Technical Field

The present invention relates to the field of data processing systems, and more particularly to improving security in data processing systems.

Background

Security is a major concern in many different areas, such as e-commerce, communications and broadcasting. Security measures provide accountability, fairness, accuracy, confidentiality, operability, and other criteria desired for data processing systems and information systems in these areas. Encryption methods that provide such security are generally categorized according to two objectives: encryption and authentication. Encryption is a technique that makes data unreadable by unauthenticated parties. Authentication is a technique to verify the integrity of data. Verifying the integrity of the data involves verifying the identity of the author of the data and/or verifying whether the data has been altered.

Encryption systems are commonly referred to as cryptosystems and have symmetric or asymmetric properties. Symmetric encryption systems use keys to encrypt information and use the same keys to decrypt the encrypted information. An asymmetric encryption system, such as a public key cryptosystem, uses a first key to encrypt information and a different key to decode the encrypted information.

In many symmetric cryptosystems, a key is used for encryption and a separate key is used for authentication. Thus in a data processing system using a symmetric cryptographic system, encryption and authentication are performed as two separate entities. Since authentication requires approximately the same processing power as encryption, the total amount of processing is equal to the amount of processing required to encrypt data twice. In data processing systems operating in power limited or hardware limited environments, such as cellular telephones, personal digital assistants, or other portable communication devices, it is desirable to have a cryptographic system that can perform encryption and authentication as a single entity in order to reduce the computational load on the device.

In the article "Encryption models with model Free Message Integrity", written by Charanjit Jutla, in the lecture eurocpt 2001 "development of cryptography" in "computer science" volume 2045 of Springer-Verlag 2001, cryptographic systems are proposed that can encrypt messages and authenticate encrypted messages in a way that requires almost no more processing than Encryption alone. In other words, encryption and authentication may be performed using a single entity. Thus, the amount of processing resources required to provide security is reduced.

The Jutla cryptosystem is designed to encrypt all data to be sent. However, in some applications, the requirement that all data of the message must be encrypted is undesirable. For example, in a communication protocol such as IPSec, encrypting all data is invalid. The header of the data must be sent unencrypted for addressing purposes. The principles of IPSec are specified in RFC 1825 entitled "Security Architecture for Internet Protocol", RFC 1826 entitled "IP Authentication Header", and RFC 1827 entitled "IP Encapsulating Security Payload (ESP)", all of which were filed by R.Atkinson at 8.1995.

Therefore, there is a need for a secure and efficient system for encrypting and authenticating data, wherein all data bits of a message need not be encrypted.

Disclosure of Invention

Methods and apparatus are presented herein that address the above-mentioned needs. In particular, methods and apparatus are presented that allow portions of a data message to be sent in the clear, portions of the data message to be sent in the cipher, and a single authentication tag to be used to verify both the clear and the cipher portions of the data message.

In one aspect, a method of encrypting and authenticating data as a single entity is presented, the method comprising: arranging the data into a plurality of plaintext blocks, each plaintext block sized according to a cipher block size; specifying at least one cleartext (cleartext) position for which the at least one ciphertext block is identical to the corresponding plaintext block; determining a plurality of noise blocks using the nonce value and the first key; determining a plurality of intermediate ciphertext blocks, wherein a first intermediate ciphertext block corresponds to the encrypted nonce, and the remaining intermediate ciphertexts are determined as follows: for each of a plurality of plaintext blocks specified by a cleartext position, combining the plaintext block with a corresponding noisy block; and for each of a plurality of plaintext blocks not specified by a cleartext position, constructing an intermediate ciphertext block using the plaintext block and a preceding intermediate ciphertext block, and then encrypting the intermediate plaintext block using a second key; determining a plurality of ciphertext blocks, wherein the plurality of ciphertext blocks are determined as follows: setting the first ciphertext block to be equal to the first intermediate ciphertext block; setting each ciphertext block specified by a cleartext position to be equal to a corresponding plaintext block; and determining each remaining ciphertext block by combining the respective intermediate ciphertext block with the respective noise block; determining a plurality of authentication blocks, wherein the plurality of authentication blocks are determined as follows: setting the authentication block equal to the plaintext block if the authentication block is associated with a plaintext block that is not specified by a cleartext position; if the authentication block is associated with the original text block specified by the cleartext position, determining the authentication block by decrypting the associated intermediate ciphertext block and combining the decrypted associated intermediate ciphertext block with a previous intermediate ciphertext block; calculating an authentication mark by combining all of the plurality of authentication blocks with the noise block and then encrypting the result of the combination; and adding the authentication tag to the plurality of ciphertext blocks.

In another aspect, a method of decrypting and verifying a plurality of transport blocks accompanied by an authentication mark is presented, the method comprising: determining a plurality of noise blocks using the nonce value and the first key; determining a plurality of intermediate ciphertext blocks by combining each of the plurality of transmission blocks with a corresponding noise block; determining a plurality of authentication blocks, wherein each of the plurality of authentication blocks is constructed by decrypting a corresponding intermediate ciphertext block and then combining the decrypted intermediate ciphertext block with a previous intermediate ciphertext block; setting each of a plurality of authentication blocks that are not associated with any predetermined cleartext position as a plaintext block; setting each of a plurality of transport blocks associated with any one of the predetermined cleartext positions as a plaintext block; and verifying the authentication mark by determining whether the last authentication block is equal to a combination of all other authentication blocks.

In another aspect, a method of secure data transmission is presented; wherein a first portion of the data transmission is sent as plaintext, a second portion of the data transmission is sent as ciphertext, and all of the data transmission is authenticated, the method comprising: generating a set of cleartext positions; encrypting a first portion of the data transmission and a second portion of the data transmission as ciphertext, wherein the first portion of the data transmission is specified by the set of cleartext positions and the second portion of the data transmission is not associated with any of the set of cleartext positions; determining a plurality of intermediate ciphertext blocks through an iterative process; generating a plurality of authentication blocks, wherein a first portion of each plurality of authentication blocks is set equal to a first portion of a respective member of the data transmission and a second portion of each plurality of authentication blocks is derived from combining a respective intermediate ciphertext block with a previous intermediate ciphertext block; generating an authentication mark by combining each of a plurality of authentication blocks with a noise block and encrypting the combined result; the plaintext, the ciphertext, and the authentication tag are transmitted, wherein the plaintext is a first portion of a data transmission specified by the set of cleartext positions.

In another aspect, an apparatus for secure data transfer is presented; wherein a first portion of the data transmission is sent as plaintext, a second portion of the data transmission is sent as ciphertext, and all of the data transmission is authenticated, the method comprising: means for generating a set of cleartext positions; means for encrypting a first portion of the data transmission and a second portion of the data transmission into ciphertext, wherein the first portion of the data transmission is specified by the set of cleartext positions and the second portion of the data transmission is not associated with any of the set of cleartext positions; means for determining a plurality of intermediate ciphertext blocks by an iterative process.

Drawings

FIGS. 1A, 1B, and 1C are block diagrams of a basic cryptographic system, a symmetric encryption system, and an asymmetric encryption system.

Fig. 2A and 2B are block diagrams of a symmetric authentication system and an asymmetric authentication system, respectively.

FIG. 3 is a block diagram of an Integrity Aware (Integrity Aware) cipher Block chaining mode.

FIG. 4A is a block diagram of the CBC-A mode.

FIG. 4B is a hardware block diagram configured to perform CBC-A mode.

FIG. 5 is a block diagram of decrypting and verifying messages encrypted and authenticated via CBC-A mode.

Fig. 6A, 6B, 6C, and 6D are different hardware configurations for performing verification of an authentication mark.

Detailed Description

Encryption makes the data unreadable by an unauthenticated party. The original data message is referred to as a plaintext message or plaintext. The encrypted message is referred to as ciphertext, where encryption encompasses any method of converting plaintext into ciphertext, such as block cipher, hash function, or any other encryption function. Decryption includes any method of converting ciphertext into plaintext, i.e., recovering the original message. Fig. 1A illustrates a basic cryptographic system 10 designed for use as encryption. The plaintext message 11 is operated on by an encryption scheme 12 to form ciphertext 13. Ciphertext 13 is then transmitted over a communication channel (not shown) and is recovered at another site (not shown) by decoding scheme 14 to form plaintext 15. Plaintext and ciphertext may refer to any data, including audio and video data that appears in digital form.

Cryptanalysis is a technique to intelligently gain the security of a cryptographic system. The entity performing the cryptographic translation is known in the art as an adversary or attacker. The cryptographic translation of the encryption scheme is about decrypting unauthenticated messages. The cryptographic translation of the authentication scheme is a component of the message that can be verified as being sent by others.

Cryptographic systems are based on secrets. A group of entities share the secret, which is said to act as a security association for the group of entities if entities outside the group cannot obtain the key without expending significant resources.

Typically, a secret contains a key or a set of keys, which are measured in bits. The longer the key, the higher the secret security of the key. Symmetric cryptosystems use the same key to encrypt messages, as well as decrypt messages. A symmetric encryption system 20 is illustrated in fig. 1B, where both encryption and decryption use the same private key. The plaintext 21 is operated on by an encryption scheme 22. The key 23 is used in an encryption scheme 22 to form a ciphertext 24. The ciphertext 24 is transmitted over a communication channel (not shown) to another station where the decryption scheme 25 uses the same key 23 to form the plaintext 26.

In contrast, asymmetric cryptography systems use a first key to encrypt a message and a different key to decrypt it. Fig. 1C illustrates an asymmetric encryption system referred to as a public key cryptosystem 30, where a public key is used for encryption and a private key is used for decryption. The public key is published so that any user can use the public key to encrypt any message. However, only a private, unpublished key may be used to decrypt this public key encrypted message. The plaintext 31 is entered into an encryption scheme 32 that uses a public key 33 associated with the specified user and obtained from the publication. The resulting ciphertext 34 may be transmitted over a communication channel (not shown) to the designated user. The designated user converts the ciphertext 34 into plaintext 37 using the key 36 in the decryption scheme 35.

Symmetric encryption is generally much faster than asymmetric encryption. However, sending the key from the sending peer to the recipient is problematic as it may be intercepted by an adversary. One solution is to use a trusted third party to hold the key, which will only share the key with authorized parties. The embodiments described herein do not address this issue, but assume that the sender and recipient share a secret key.

The integrity of the ciphertext generated by the cryptosystem described above is typically provided by appending some authentication data to the transmitted ciphertext. The authentication data is typically computed as a function of the message content and the integrity key.

In a symmetric authentication system, the authentication data is called a Message Authentication Code (MAC). The MAC is computed as a function of the message content and an integrity key that the sender and the specified target share. The sender sends the message and attaches the MAC. The message may be plaintext or ciphertext. The recipient recalculates the MAC from the message and approves the integrity of the message only if the recalculated MAC is consistent with the sent MAC. In theory, only the sender of a message is able to generate a valid signature of the message, thereby authenticating the message to the recipient.

A symmetric authentication system 40 is illustrated in fig. 2A, where both signing and verification use the same key. The message 41 is acted upon with an authentication scheme 42 using a key 43 to form authentication data 44. The authentication data 44 and the message 41 are then sent to the other party (not shown) over a communication channel (not shown). The message 41 is acted upon with a verification scheme 45 using the same key 43 to determine authentication data 46. There is a comparison of the authentication data 46 generated by the recipient with the authentication data 44 received over the communication channel.

In an asymmetric authentication system, the authentication data is called a data signature. The data signature is computed as a function of the message content and the integrity key of the sender. The sender sends the digital signature to the receiver, which then performs a verification of the digital signature using the sender's public key. An asymmetric authentication system 50 is illustrated in fig. 1E, where a signature uses a private key and an authentication uses a corresponding public key.

In some schemes, the MAC or digital signature is derived from a 'message digest' that contains a unique mathematical description of the secret message. The computed message digest is shorter in length than the original message, so that computation of the message digest is more easily performed. Since the secret message or message digest is not kept constant, the dependency of the MAC or digital signature on the secret message or message digest ensures that the authentication data is not kept constant. If the authentication data is kept constant for multiple messages, an adversary can fraudulently and easily steal the authentication data.

The message digest is typically computed using a cryptographic hash function. The cryptographic hash function computes a value (containing a fixed number of bits) from any input, regardless of the length of the input. One characteristic of cryptographic hash functions is that given an output value, it is computationally difficult to determine the input that would result in that output. An example of a cryptographic Hash function is SH-1, as described in Federal information processing Standard publication (FIPS PUBS) published and in the National Institute of Standards and Technology (NIST) published FIP PUB 180-1, "Secure Hash Standard".

Block ciphers are symmetric encryption schemes for which the input to the scheme is always a fixed length in bits. This length is called the packet size of the block cipher. An example of a block cipher is the Data Encryption Standard (DES), as described in FIPS PUB 46-1, "Data Encryption Standard," published by FIPS PUBS and published by NIST. The packet size of DES is 64 bits. Another example of a block cipher is the Advanced Encryption Standard (AES), as described in FIPS PUB 46-1, "Advanced encryption Standard," published by FIPS PUBS and by NIST. The packet size of AES is 128 bits.

The key length of a block cipher is the length of the key in a binary representation. However, the entropy of a key is the logarithm of the number of possible values of the key (base 2). Entropy is also written in binary bits. For example, DES has a 64-bit key, with 8 of these bits used as a checksum to detect errors in key transmission. Thus, the key-entropy of DES is (64-8) ═ 56 bits.

Given several pairs of inputs and corresponding outputs of a block cipher, the keys of the block cipher may be derived by an adversary who tests all possible key values to determine which inputs result in the correct outputs. This type of attack is known as exhaustive key search. The computational complexity of such an attack is the number of cryptographic operations required for the attack. Therefore, in the exhaustive key search, an attack to extract a K-bit key requires about 2K encryption operations to extract a block cipher key.

Block ciphers are useful for constructing other cryptographic entities. The way in which block ciphers are used is called the mode of operation. Four Modes of operation have been standardized for DES and are described in FIPS PUB81, "DES models of Operaion," issued by FIPS PUBS and published by NIST. These four modes are Electronic Codebook (ECB), Cipher Block Chaining (CBC), Output Feedback (OFB) and Cipher Feedback (CFB). For purposes of illustration, only ECB and CBC are discussed herein to encrypt plaintext Block P₁,., and P_mAnd (4) sequencing.

In ECB mode, a block cipher is used to encrypt each block of plaintext into a ciphertext block in accordance with the following relationship:

C_i＝E_K(P_i)

wherein E_K(P_i) Representing block P using key K_iEncryption of (2). Thereafter, use D_K(P_i) Representing block P using key K_iEncryption of (2).

In CBC mode, the first block of plaintext is ored with a secret Initial Value (IV) to form a result, which is then encrypted. The mathematical description of the process is written in terms of the following relationship:

C_i＝E_k(P_iIV)

thereafter, each plaintext block is exclusive-ored with the previous ciphertext before encryption, as follows:

C_i＝E_k(P_iC_i-1)

in symmetric cryptosystems, efficient encryption and authentication can be problematic. Until recently, the only solution to meet this demand was to use a natural approach: encryption and authentication are provided as two separate functions. These two functions require approximately equal amounts of computation and therefore use of both functions is twice as expensive as use of only one or the other method.

In the article "Encryption MoJutla proposed two methods in des with all the above Free Message Integrity ″, which provide slightly more computationally intensive encryption and authentication than encryption or authentication alone. These methods have a general form and use block ciphers as the cipher core. In the cryptographic community, such methods are also referred to as "modes of operation". One of the modes of operation of Jutla, referred to as Integrity Aware Parallelable Mode (IAPM) mode, is not discussed in this document. Another mode of operation of Jutla, referred to as Integrity Aware Cipher Block Chaining (IACBC) mode, is shown in fig. 3. The IACBC uses two keys: k₀And K₁. Suppose the sender wishes to encrypt and authenticate with the slave P₁To P_m-1Of (m-1) message blocks. The sender sets t equal to the next integer greater than the logarithm of (m +1) (base 2). The sender selects a random value r, encrypts r to form a ciphertext block C₀. The values r +1 to r + t are encrypted to form the value W₀To W_t-1Wherein the encryption uses a secret key K₀. Value W₀To W_t-1Are then used to derive pairs of independent values S₀To S_m. These S_iThe values are referred to herein as noise blocks. If uniformly distributed to S₀，...，S_mAn n-bit random number having the following characteristics: for each pair S_iAnd S_jWhere i ≠ j, and each pair of n-bit numbers contains c₁And c₂，S_i＝c₁And S_j＝c₂Has a probability of 2_-2nThen value S₀，...，S_mAre independent in pairs. To S₀To S_mThe actual calculation of (c) is not relevant for understanding the IACBC and will not be described below. Iteratively deriving ciphertext block c for 1 ≦ i ≦ m-1 according to the following relationship₁To c_m-1The value of (c):

M_i＝P_iN_i-1

N_i＝E_K1(M_i)，

C_i＝N_iS_i，

wherein the secret key K₁Is used for each cipher block and initialized with value N₀Is set to C₀. These values M_iCalled intermediate plaintext block, value N_iReferred to as an intermediate ciphertext block. The sender then calculates a checksum value P_mDefined as:

P_m＝P₁P₂...P_m-1.

by using a secret key K₁Encryption (P)_mN_i-1) And combining the encrypted result with S₀Exclusive OR, from P_mCalculating MAC tag C_m. Mathematically, this calculation can be expressed as follows:

C_m＝E_K1(P_mN_i-1)S₀.

sender sends C₀...C_m。

Assume that the receiver receives C'₀...C’_m. The receiver decrypts C 'by first'₀Starting the decryption process with the formation r', wherein the decryption uses the key K₁. Encrypting the values r ' +1 to r ' + t to form a value W '₀To W'_t-1Wherein the encryption uses a key K₀. The receiver then calculates value S'₀To S'_m. The ciphertext block P is iteratively derived for 1 ≦ i ≦ m-1 according to the following relationship₁To P_m-1The value of (c):

N’_i＝C’_iS’_i，

M’_i＝D_K1(N’_i)，

P_i＝N’_i-1M’_i，

wherein the secret key K₁Is used for each plaintext block, and has an initial value of N'₀Is set equal to C'₀. The recipient then calculates a checksum value P'_mDefined as:

P_m’＝P’₁P’₂...P’_m-1.

by using a secret key K₁Encryption P_mAnd N_m-1Exclusive OR of, then, the encrypted result is compared with S'₀The value X is calculated by xoring. Mathematically, the process can be described as follows:

X＝E_K1(P’_mN’_m-1)S’₀.

if X and C'_mEqual, the receiver can be assured of the integrity of the encrypted message.

Gligor and Donescu in the paper "Fast Encryption and authentication: a similar schema is proposed in XCBCEncryption and XEBC Authentication models, "called extended ciphertext packet chaining mode (XCBC mode), which uses similar computational effort to provide encryption and Authentication. The main difference between XCBC and IACBC is the noise block S₀To S_mThe representation of (2) is independent of this file.

The operation of the IACBC and XCBC modes has certain undesirable characteristics. The first undesirable characteristic is that these modes require all data to be sent encrypted. In internet protocols such as IPSec, it is not desirable to send messages in which all data is encrypted. In particular, the header containing the addressing information must be sent in clear. The embodiments described herein propose variants of the IACBC and XCBC modes that allow blocks of data to be sent in the clear, with only a small amount of processing added. The deformation is referred to herein as the CBC-a mode.

It should be noted that either the hardware or software in the data or communication system may be configured to perform different embodiments of the CBC-a mode. Hardware may include, but is not limited to: the processing element implements a set of instructions stored on a computer-readable medium, such as a memory, to perform the encryption, authentication, decryption, and verification processes described below. In addition, various combining steps are described using bitwise logical XOR operators. Other implementations of embodiments may be performed using modulo integer addition operations, where two inputs are treated as integers of a binary representation, the binary representation of the sum of the two integers constitutes an intermediate value, and the output is constructed by truncating the intermediate value to the cipher block size. Other group operators may be substituted for the various combining steps, however, for ease of illustration, only embodiments using exclusive OR operators are described herein.

One embodiment of the CBC-A mode is illustrated in FIG. 4A. The CBC-a mode of operation uses two keys: k₀And K₁. It is assumed that the sender wishes to encrypt and authenticate the data block P₁To P_m-1The (m-1) message of (c). The sender and receiver agree to send the set of blocks of plaintext in unencrypted form. The set of plaintext block indices to be sent in unencrypted form is denoted by U, the elements of which are referred to as plaintext positions. At step 400, the sender selects r and computes a noise block S in the IACBC or XCBC mode₀To S_m. At step 402, the sender calculates N₀＝C₀＝E_k1(r) of (A). At step 404, the iterative process begins by determining whether i ∈ U, where 1 ≦ i ≦ m-1. If i ∈ U, program flow proceeds to step 410. If it is notThen program flow proceeds to step 420.

If i ∈ U, then at step 410, C is set_i＝P_i. At step 415, calculate:

N_i＝P_iS_i，

M_i＝E_K1(N_i) And are and

Y_i＝N_i-1M_i.

program flow proceeds to step 417.

If it is notThen at step 420, letPut Y_i＝P_i. At step 425, calculate:

M_i＝P_iN_i-1，

N_i＝E_K1(M_i) And are and

C_i＝N_iS_i.

the program flow proceeds to step 417. At step 417, the exponent i is incremented, i.e., the next block is to be operated on. If another block is to be processed, then the program flows back to step 404. If there are no more blocks to process, then program flow proceeds to step 430. The above process is for obtaining ciphertext C₀To C_m-1And an authentication block Y₁To Y_m-1. Value N₀To N_m-1Referred to as an intermediate ciphertext block. At step 430, the sender calculates a checksum value P_mComprises the following steps:

P_m＝Y₁Y₂...Y_m-1.

at step 432, M is encrypted_mCalculating MAC tag C_mWherein by reacting P_mAnd N_m-1By differentiating or forming M_m. Using a secret key K₁Encryption M_m. This process is described mathematically as follows:

C_m＝E_K1(P_mN_m-1).

at step 434, the sender marks the MAC with a C_mAppended to the message. At step 436, the sender sends C₀...C_m。

FIG. 4B is a block diagram of hardware configured to perform the CBC-A mode described above. It should be noted that FIG. 4B illustrates an implementation that may be an alternative to a software implementation, where the processor and memory are configured to execute a set of instructions for performing the CBC-A mode described above. Memory element 440 stores a block of text P_iSome of which are to be encrypted and all of which are to be authenticated. Encryption elements 450A, 450B, 450C, 450D, and 450E is configured to perform cryptographic functions using a key K1, the key K₁Agreement is reached between the sender and the recipient during the key agreement process, the details of which are not discussed here. For purposes of illustration, five (5) encryption elements are shown in FIG. 4B for encrypting a plaintext block, but those skilled in the art will appreciate that more or fewer encryption elements may be implemented without affecting the scope of the present embodiment. The input to the first encryption element 450A is a nonce r, which will be used to determine the noise block S₀，S₁，...，S_m-1. The hardware configuration for generating the noise block is not shown here. The output of the first encryption element 450A is a first ciphertext block C₀It is set equal to the first intermediate ciphertext block N₀。

The inputs to the other encryption elements 450B, 450C, 450D, and 450E are each an intermediate block of text M at each respective encryption element₁，...，M_m. Middle original text block M₁，...，M_mIs the output of the combination elements 444A, 444B, 444C and 444D. The input to each of the combining elements 444A, 444B, 444C, and 444D is a plaintext block P_i(wherein) And an intermediate ciphertext block N_i-1. In one aspect, the combination elements described herein are exclusive or gates. In another aspect, the combination element is a group operator.

The output to the encryption elements 450B, 450C, 450D, and 450E is an intermediate ciphertext block N_iWhereinTo pairEach intermediate ciphertext block N_iAt combining elements 462A, 462B, 462C or 462D with corresponding noise blocks S_iCombined to form ciphertext block C_iWhereinIntermediate ciphertext block N_i(wherein) Also to one of the switching elements 470A, 470B, 470C or 470D, as will be discussed later.

The decryption elements 455A, 455B, and 455C are configured to perform an encryption function, which is the reverse function for the encryption elements 450A, 450B, 450C, 450D, and 450E. The input to decryption elements 455A, 455B, and 455C is an intermediate ciphertext block N_iWhere i ∈ U. Intermediate ciphertext block N_i(where i ∈ U) is the output of combining elements 442A, 442B, and 442C. The input to each combination element 442A, 442B, or 442C is a plaintext block P_iAnd noise block S_i. The output of the decryption elements 455A, 455B, and 455C is the intermediate text block M_iWhere i ∈ U. Middle original text block M_i(where i e U) is associated with the previous intermediate ciphertext block N at each of the combining elements 460A, 460B, and 460C, respectively_i-1Combined to form an authentication block Y_m-1。

At each stage, an intermediate ciphertext block (where i ∈ U) and an intermediate ciphertext block (where i ∈ U)) Is input to the switching element 470A, 470B, 470C, or 470D. Control lines (not shown) from the processing elements control the decision to use any intermediate ciphertext block for the next stage of computation.

At the last stage, by dividing the last intermediate ciphertext block N_mAnd a first noise block S₀Combine to form an authentication mark C_m。

FIG. 5 is a block diagram of decrypting and verifying CBC-A mode encrypted and authenticated messages. Assume that the receiver receives transmission module C 'at step 500'₀...C’_m. Note that for i ∈ U, C'_iIs sent unencrypted. At step 502, the recipient decrypts C'₀To obtain r'And deriving therefrom S'₀To S'_mThe value of (c). In alternative embodiments, the nonce r may be a pre-negotiated or predetermined value.

At step 510, for 1 ≦ i ≦ m, the recipient pairs C 'according to the relationship'_iAnd S'_iXOR to form an intermediate ciphertext block N'_i：

N’_i＝C’_iS’_i.

At step 520, the recipient constitutes N'_m＝C’_mS’₀Where the receiver sets N'₀＝C’₀. At step 530, the recipient decrypts the intermediate ciphertext N 'using decryption in CBC mode'₀，...，N’_mTo form an authentication block Y'₁，...，Y’_m. This is done iteratively and is mathematically represented as follows:

Y_i＝D_K1(N’₁)N’_i-1，for 1≤i≤m.

at step 540, the iterative process begins to be P'_iA value is determined. For i ∈ U, program flow proceeds to step 542 where the recipient sets P'_i＝C’_i. Program flow proceeds to step 544. For theProgram flow proceeds to step 546 where the plaintext block is set to be the same as the authentication block, i.e., recipient set P'_i＝Y’_i. The program flows to step 544. At step 544, the recipient determines whether another block is to be processed. If so, the program flow returns to step 540. If not, program flow proceeds to step 550. The recipient now decodes the ciphertext into data block P'₁，...P’_m-1But the receiver needs to verify integrity.

To verify the authentication indicia, at step 550, the recipient confirms Y'_mIs equal to (Y'₁ Y’₂… Y’_m-1) The value of (c). If the authentication token is verified, then the message is P'₁，...，P’_m-1。

In alternative embodiments that reduce processing time, the verification of the authentication indicia at step 550 may be performed immediately after step 530, or before step 540 or in parallel with step 540. Thus, the recipient may authenticate the received message before determining the text of the message. If the received message is not authenticated, the recipient may determine plaintext Block P 'by omitting'_iTo conserve processing resources. Conversely, the IACBC mode proposed by Jutla requires the determination of plaintext Block P'_iAnd encrypts the form of the result thereof to thereby calculate a test authentication mark.

Further, in an alternative embodiment, verification of the authentication mark may be by comparing the value (Y'₁Y’₂…Y’_m-1) And another is not Y'_mAre performed in comparison to the amount of. Fig. 6A shows an alternative hardware implementation. The checksum value CHK is set equal to (Y'₁Y’₂…Y’_m-1). The CHK value is combined with the intermediate ciphertext block N 'by the combiner element 602'_m-1Are combined. The CHK value is passed through the combination element 600 and the intermediate ciphertext block N'_m-1Are combined. The output of combining element 602 is then combined with a first noise block S 'at combining element 604'₀Are combined. The output of combining element 604 is then compared with the last ciphertext block C 'at comparing element 606'_mA comparison is made wherein a match indicates that the authentication mark was verified.

Fig. 6B is another alternative hardware embodiment for verifying the authenticity of a received message. The CHK value is combined with the intermediate ciphertext block N 'by the combining element 610'_m-1Are combined. The output of the combining element 610 is then encrypted by an encryption element 612. Final ciphertext Block C 'by combination element 614'_mAnd a first noise block S'₀Are combined. If the output of the encryption element 612 matches the output of the combination element 614 at the comparison element 616, the received message is verified.

Fig. 6C is another alternative hardware embodiment for verifying the authenticity of a received message. The CHK value is combined with the intermediate ciphertext block N 'by the combining element 620'_m-1Are combined. Final ciphertext Block C 'by combining element 622'_mAnd a first noise block S'₀Are combined. The output of the combining element 622 is then encrypted by a decryption element 624. If the output of the decryption element 624 matches the output of the combination element 620 at the comparison element 626, the received message is verified.

Fig. 6D is another alternative hardware embodiment for verifying the authenticity of a received message. Final ciphertext Block C 'by composition element 630'_mAnd a first noise block S'₀Are combined. The output of the combining element 630 is then decrypted by the decryption element 632. The output of decryption element 632 is then combined with intermediate ciphertext block N 'by combining element 634'_m-1Are combined. If the output of the combining element 634 matches the CHK value at the comparing element 636, the received message is verified.

Note that for a given ciphertext C'₀...C’_m-1Authentication flag C 'for the set of U of all plaintext positions'_mAre the same: the process of verifying the authentication mark is independent of the set of clear locations. Verification of authentication flag Only verifying sender's transmission ciphertext C'₀...C’_mWithout verifying which locations are clear locations and which are not. This may allow an attacker to make use of the wrong set of clear locations when the recipient decrypts the message. To prevent such attacks, the sender and receiver must use other methods to verify the cleartext position applied to a particular ciphertext message. There is a simple solution to this problem. One solution is to have a standard protocol for those locations that are clear. Another approach is to include a representation of the set U of cleartext positions in the data block, such that the verification of the ciphertext includes verification of the set of cleartext positions.

In CBC-a mode, if the underlying block cipher is secure, then the encryption and authentication functions are secure. Formal notations are known in the art as to what the phrase "the encryption and authentication functions are secure", however, such formal notations are irrelevant to the subject matter of the present invention and are not discussed here. Those skilled in the art will be familiar with the meaning of the phrase "the encryption and authentication functions are an object secure".

The security proof is not included, but some observations about security are shown here. The CBC-a mode has the same security proof for the encryption function as the IACBC and XCBC modes. Generating the authentication tag in CBC-a mode is different from generating the authentication tag in IACBC and XCBC modes. However, CBC-a verifies the authentication token using the same steps as the IACBC and XCBC modes. Thus, only if an attacker can compromise the IACBC or XCBC authentication functions can the attacker compromise the CBC-a authentication functions (i.e., generate a CBC-a authentication tag that will be verified as correct). Since designers of the IACBC and XCBC modes have shown that attackers cannot compromise the IACBC and XCBC authentication functions, it follows that attackers cannot compromise the CBC-a authentication functions. Thus, the CBC-A authentication function is secure.

Note that the sender may choose to send P_iOr C_iThis does not jeopardize the authentication. The embodiments described herein allow a party to send encrypted or unencrypted blocks without compromising the security of the authentication scheme. If P is_iSent in the clear, then P_iIs still secure and unpredictable, and thus P_iMay be used as a security certificate.

It is common practice to define the MAC as only part of the final block when using authentication mode. The invention may also be modified so that only a portion of the final block is sent as MAC.

Those of skill in the art would understand that information and signals may be represented using any of a variety of different technologies and techniques. For example, data, instructions, commands, information, signals, bits, symbols, and chips that may be referenced throughout the above description may be represented by voltages, currents, electromagnetic waves, magnetic fields or particles, optical fields or particles, or any combination thereof.

Those of skill would further appreciate that the various illustrative logical blocks, modules, circuits, and algorithm steps described in connection with the embodiments disclosed herein may be implemented as electronic hardware, computer software, or combinations of both. To clearly illustrate this interchangeability of hardware and software, various illustrative components, blocks, modules, circuits, and steps have been described above generally in terms of their functionality. Whether such functionality is implemented as hardware or software depends upon the particular application and design constraints imposed on the overall system. Skilled artisans may implement the described functionality in varying ways for each particular application, but such implementation decisions should not be interpreted as causing a departure from the scope of the present invention.

The implementation or execution of the various illustrative logical blocks, modules, and algorithm steps described in connection with the embodiments described herein may be implemented or performed with: a general purpose processor, a Digital Signal Processor (DSP), an Application Specific Integrated Circuit (ASIC), a Field Programmable Gate Array (FPGA) or other programmable logic device, discrete gate or transistor logic, discrete hardware components, or any combination designed to perform the functions described herein. A general purpose processor may be a microprocessor, but in the alternative, the processor may be any conventional processor, controller, microcontroller, or state machine. A processor may also be implemented as a combination of computing devices, e.g., a combination of a DSP and a microprocessor, a plurality of microprocessors, one or more microprocessors in conjunction with a DSP core, or any other such configuration.

The steps of a method or algorithm described in connection with the embodiments disclosed herein may be embodied directly in hardware, in a software module executed by a processor, or in a combination of the two. A software module may reside in RAM memory, flash memory, ROM memory, EPROM memory, EEPROM memory, registers, hard disk, a removable disk, a CD-ROM, or any other form of storage medium known in the art. An exemplary storage medium is coupled to the processor such the processor can read information from, and write information to, the storage medium. In the alternative, the storage medium may be integral to the processor. The processor and the storage medium may reside in an ASIC. The ASIC may reside in a user terminal. In the alternative, the processor and the storage medium may reside as discrete components in a user terminal.

The previous description of the preferred embodiments is provided to enable any person skilled in the art to make or use the present invention. Various modifications to these embodiments will be readily apparent to those skilled in the art, and the generic principles defined herein may be applied to other embodiments without the use of the inventive faculty. Thus, the present invention is not intended to be limited to the embodiments shown herein but is to be accorded the widest scope consistent with the principles and novel features disclosed herein.

Claims (15)

1. A method of encrypting and verifying data as a single entity, the method comprising:

arranging the data into a plurality of plaintext blocks, and determining the size of each plaintext block according to the size of the cipher block;

specifying at least one cleartext position for which at least one ciphertext block will be identical to a corresponding plaintext block;

determining a plurality of noise blocks using the nonce value and the first key;

determining a plurality of intermediate ciphertext blocks, wherein the first intermediate ciphertext block corresponds to an encrypted nonce, and remaining intermediate ciphertexts are determined as follows:

for each of a plurality of plaintext blocks specified by a cleartext position, combining the plaintext block with a corresponding noisy block; and

for each of a plurality of plaintext blocks not specified by a cleartext position, forming an intermediate plaintext block using the plaintext block and a preceding intermediate ciphertext block, and then encrypting the intermediate plaintext block using a second key;

determining a plurality of ciphertext blocks, wherein the plurality of ciphertext blocks are determined as follows:

setting the first ciphertext block to be equal to the first intermediate ciphertext block;

setting each ciphertext block, each specified by a cleartext position, equal to a corresponding plaintext block; and

determining each remaining ciphertext block by combining the respective intermediate ciphertext block with the respective noise block;

determining a plurality of authentication blocks, wherein the plurality of authentication blocks are determined as follows:

setting an authentication block equal to a plaintext block that is not specified by a cleartext position if the authentication block is associated with the plaintext block;

if the authentication block is associated with a plaintext block specified by the cleartext position, determining the authentication block by decrypting the associated intermediate ciphertext block and combining the decrypted associated intermediate ciphertext block with a previous intermediate ciphertext block;

calculating an authentication flag by combining all of the plurality of authentication blocks with the noise block, and then encrypting the combination result; and

an authentication tag is appended to the plurality of ciphertext blocks.

2. The method of claim 1, wherein the encryption uses block cipher encryption.

3. The method of claim 1, wherein the encrypting and decrypting comprises:

selecting to apply block cipher encryption or block cipher decryption;

selecting a key or block cipher for use according to a set of predefined selection rules; and

a key with a block cipher is used on a plurality of input blocks to obtain a plurality of output blocks.

4. The method of claim 1, wherein combining is performed using a bit exclusive or operation.

5. The method of claim 1, wherein combining is performed using group operators.

6. The method of claim 5, wherein the group operator is a modulo integer addition operator.

7. A method for decrypting and verifying a plurality of transport blocks accompanied by an authentication mark, the method comprising:

determining a plurality of noise blocks using the nonce value and the first key;

determining a plurality of intermediate ciphertext blocks by combining each of the plurality of transmission blocks with a respective noise block;

determining a plurality of authentication blocks, wherein each of the plurality of authentication blocks is formed by decrypting a respective intermediate ciphertext block and then combining the decrypted intermediate ciphertext block with a preceding intermediate ciphertext block;

setting each of a plurality of authentication blocks that are not associated with any predetermined cleartext position as a plaintext block;

setting each of a plurality of transport blocks associated with any one of the predetermined cleartext positions as a plaintext block; and

the authentication mark is verified by determining whether the last authentication block is equal to the combination of all other authentication blocks.

8. The method of claim 6, wherein the nonce is pre-negotiated between a sender of the plurality of transport blocks and a receiver of the plurality of transport blocks.

9. The method of claim 5, wherein the nonce is derived from the first transport block.

10. Apparatus for encrypting and authenticating data as a single entity, the apparatus comprising:

at least one memory element; and

at least one processing element configured to execute a set of instructions stored in at least one memory element, the set of instructions for:

arranging the data into a plurality of plaintext blocks, and determining the size of each plaintext block according to the size of the cipher block;

specifying at least one cleartext position for which at least one ciphertext block will be identical to a corresponding plaintext block;

determining a plurality of noise blocks using the nonce value and the first key;

determining a plurality of intermediate ciphertext blocks, wherein the first intermediate ciphertext block corresponds to an encrypted nonce, and remaining intermediate ciphertexts are determined as follows:

for each of a plurality of plaintext blocks specified by a cleartext position, combining the plaintext block with a corresponding noisy block; and

for each of a plurality of plaintext blocks not specified by a cleartext position, forming an intermediate plaintext block using the plaintext block and a preceding intermediate ciphertext block, and then encrypting the intermediate plaintext block using a second key;

determining a plurality of ciphertext blocks, wherein the plurality of ciphertext blocks are determined as follows:

setting the first ciphertext block to be equal to the first intermediate ciphertext block;

setting each ciphertext block specified by a cleartext position equal to a corresponding plaintext block; and

determining each remaining ciphertext block by combining the respective intermediate ciphertext block with the respective noise block;

determining a plurality of authentication blocks, wherein the plurality of authentication blocks are determined as follows:

setting an authentication block equal to a plaintext block that is not specified by a cleartext position if the authentication block is associated with the plaintext block;

if the authentication block is associated with the plaintext block specified by the cleartext position, determining the authentication block by decrypting the associated intermediate ciphertext block and combining the decrypted associated intermediate ciphertext block with a previous intermediate ciphertext block;

calculating an authentication flag by combining all of the plurality of authentication blocks with the noise block, and then encrypting the combination result; and

an authentication tag is appended to the plurality of ciphertext blocks.

11. Apparatus for decrypting and verifying a plurality of transport blocks accompanied by an authentication tag, the apparatus comprising:

at least one memory element; and

at least one processing element configured to execute a set of instructions stored in at least one memory element, the set of instructions for:

determining a plurality of noise blocks using the nonce value and the first key;

determining a plurality of intermediate ciphertext blocks by combining each of the plurality of transmission blocks with a corresponding noise block;

determining a plurality of authentication blocks, wherein each of the plurality of authentication blocks is formed by decrypting a corresponding intermediate ciphertext block and then combining the decrypted intermediate ciphertext block with a previous intermediate ciphertext block;

setting each of a plurality of authentication blocks that are not associated with any predetermined cleartext position as a plaintext block;

setting each of a plurality of transport blocks associated with any one of the predetermined cleartext positions as a plaintext block;

the authentication mark is verified by determining whether the last authentication block is equal to the combination of all other authentication blocks.

12. Apparatus for encrypting and authenticating data as a single entity, the apparatus comprising:

means for arranging the data into a plurality of plaintext blocks, each plaintext block sized according to a cipher block size;

means for designating at least one cleartext position for which at least one ciphertext block will be identical to a corresponding plaintext block;

means for determining a plurality of noise blocks using the nonce value and the first key;

means for determining a plurality of intermediate ciphertext blocks, wherein the first intermediate ciphertext block corresponds to an encrypted nonce, and remaining intermediate ciphertexts are determined as follows:

for each of a plurality of plaintext blocks specified by a cleartext position, combining the plaintext block with a corresponding noisy block; and

for each of a plurality of plaintext blocks not specified by a plaintext position, forming an intermediate plaintext block using the plaintext block and a preceding intermediate ciphertext block, and then encrypting the intermediate plaintext block using a second key;

means for determining a plurality of ciphertext blocks, wherein the plurality of ciphertext blocks are determined as follows:

setting the first ciphertext block to be equal to the first intermediate ciphertext block;

setting each ciphertext block specified by a cleartext position equal to a corresponding plaintext block; and

determining each remaining ciphertext block by combining the respective intermediate ciphertext block with the respective noise block;

means for determining a plurality of authentication blocks, wherein the plurality of authentication blocks are determined as follows:

setting an authentication block equal to a plaintext block that is not specified by a cleartext position if the authentication block is associated with the plaintext block;

if the authentication block is associated with a plaintext block specified by the cleartext position, determining the authentication block by decrypting the associated intermediate ciphertext block and combining the decrypted associated intermediate ciphertext block with a previous intermediate ciphertext block;

means for calculating an authentication flag by combining all of the plurality of authentication blocks with the noise block, and then encrypting the result of said combining; and

means for appending an authentication tag to the plurality of ciphertext blocks.

13. Apparatus for decrypting and verifying a plurality of transport blocks accompanied by an authentication tag, the apparatus comprising:

means for determining a plurality of noise blocks using the nonce and the first key;

means for determining a plurality of intermediate ciphertext blocks by combining each of the plurality of transmission blocks with a respective noise block;

means for determining a plurality of authentication blocks, wherein each of the plurality of authentication blocks is formed by decrypting a corresponding intermediate ciphertext block and then combining the decrypted intermediate ciphertext block with a preceding intermediate ciphertext block;

means for setting each of a plurality of authentication blocks that are not associated with any predetermined cleartext position as a plaintext block;

means for setting each of a plurality of transport blocks associated with any one of the predetermined clear code positions as a text block;

means for verifying the authentication mark by determining whether the last authentication block is equal to the combination of all other authentication blocks.

14. A method for secure data transmission, wherein a first portion of the data transmission is sent as plaintext, a second portion of the data transmission is sent as ciphertext, and all of the data transmission is authenticated, the method comprising:

generating a set of cleartext positions;

encrypting the first portion of the data transfer and the second portion of the data transfer into ciphertext, wherein the first portion of the data transfer is specified by the set of cleartext positions and the second portion of the data transfer is not associated with any of the set of cleartext positions;

determining a plurality of intermediate ciphertext blocks via an iterative process;

generating a plurality of authentication blocks, wherein a first portion of each plurality of authentication blocks is set equal to a respective number of first portions of the data transmission and a second portion of each plurality of authentication blocks is derived by combining a respective intermediate ciphertext block with a previous intermediate ciphertext block;

generating an authentication mark by combining each of a plurality of authentication blocks with a noise block, and encrypting the combined result; and

transmitting the plaintext, the ciphertext, and the authentication tag, wherein the plaintext is a first portion of a data transmission specified by the set of cleartext positions.

15. Apparatus for secure data transmission, wherein a first portion of the data transmission is sent as plaintext, a second portion of the data transmission is sent as ciphertext, and all of the data transmission is authenticated, the method comprising:

means for generating a set of cleartext positions;

means for encrypting the first portion of the data transmission and the second portion of the data transmission into ciphertext, wherein the first portion of the data transmission is specified by the set of cleartext positions and the second portion of the data transmission is not associated with any of the set of cleartext positions;

means for determining a plurality of intermediate ciphertext blocks by an iterative process;

means for generating a plurality of authentication blocks, wherein a first portion of each plurality of authentication blocks is set equal to a respective number of first portions of the data transmission and a second portion of each plurality of authentication blocks is derived by combining a respective intermediate ciphertext block with a previous intermediate ciphertext block;

means for generating an authentication mark by combining each of a plurality of authentication blocks with a noise block and encrypting the combined result; and

means for transmitting the plaintext, the ciphertext, and the authentication tag, wherein the plaintext is a first portion of a data transmission specified by the set of cleartext positions.