Method and apparatus for multiple CMEA iteration encryption/decryption for improving wireless telephone message security

Method and device for multiple CMEA iterative encryption and decryption for improving wireless telephone message security

This patent application claims the rights and interests of the U.S. Provisional Application Serial No. 60/043,536 filed on April 14, 1997. The name of the related application is "A method and device for improving the security of wireless telephone messages by expanding the key into a lookup table to enhance security". It was filed on the same date, and it is noted here and incorporated as a reference in its entirety. .

Technical field

The present invention relates generally to wireless telephone encryption. More specifically, the present invention relates to a security-improved encryption system for fast and secure encryption in a wireless telephone system.

Background technique

Messages in wireless phones are used for several purposes, such as: transmitting status information, reorganizing working modes, processing call terminals, transmitting system and user data such as user electronic serial numbers and telephone numbers, and conversations and other data sent by users . Different from ordinary wired telephones, there is a central service station connected to each user with wired lines, so it can ensure that it is not eavesdropped and tampered by unauthorized parties (intruders) to a considerable extent, while wireless telephone services Stations (ie, base stations), regardless of the physical location of the user, must send and receive messages through signals in the air.

Since the base station must be able to send and receive messages to and from users anywhere, message processing is completely dependent on the signals received and sent to and from the user equipment. And because the signals are transmitted over the air, they will be intercepted by eavesdroppers or interveners with precise equipment.

If the signal is transmitted in clear text by a wireless phone, there is a danger that an eavesdropper can intercept the signal and use it to impersonate the user, or intercept private data transmitted by the user. Such private data may include the content of the conversation. Private data may also include non-voice data transmitted by the user, such as computer data transmitted via a modem connected to a wireless telephone, and may include bank statements and other private user information, which are usually transmitted by means of buttons. An eavesdropper who listens to conversations or intercepts non-voice data can obtain private information from users. The message content of the unencrypted telephone signal (that is, the plaintext signal) is relatively easy to be intercepted by a suitably attached receiver.

In addition, the intervener can insert himself into the established connection with a larger transmission power, and send a signal to the base station to pretend to be one of the parties in the conversation.

When encryption is not used in messages transmitted by wireless signals, unauthorized use of telephone resources, eavesdropping of messages, and impersonation of the called party or calling party during the conversation are all possible. Facts have proved that such unauthorised intervention and/or wiretapping can become a major problem and are highly undesirable.

The encryption function in wireless phone applications provides solutions to the security issues discussed above; however, when standard encryption methods are used for wireless phones, serious difficulties are encountered due to a large number of calculations in such methods. In particular, this type of method is subject to the constraints imposed by the desire to produce small wireless handsets, and the processing power imposed by the small-sized handsets. The processing power presented in a typical wireless mobile phone is not sufficient to cope with the processing requirements of well-known encryption algorithms such as DES (Data Encryption Standard). Implementing such well-known encryption algorithms in a typical wireless telephone system may increase the time required for the process signal (that is, encryption and decryption), resulting in unacceptable signal delays for users.

An encryption system for wireless telephone applications is disclosed in Reeds' US Patent No. 5,159,634, which is incorporated herein by reference. Reeds described an encryption system introduced in an encryption algorithm called the Cellular Message Encryption Algorithm (CMEA) process. There is a need to significantly improve the existing encryption systems of this type or other in wireless telephones under the resources available for application.

Summary of the invention

The present invention can beneficially meet this and other needs. In a method according to the present invention, first and second CMEA keys are generated. After the plaintext message is input, it undergoes the first input transformation to generate a message transformed by the first input. Use the first CMEA key to process the first input transformed message by the first generation of the CMEA process, and generate the first intermediate ciphertext. The first intermediate ciphertext is subjected to a first output transformation to produce a message transformed by the first output. The first output transformed message is subjected to a second input transformation, resulting in a second input transformed message. The second CMEA key is used to process the second input transformed message in the second iteration of the CMEA process to generate a second intermediate ciphertext. The second intermediate ciphertext is subjected to a second output transformation, resulting in a message transformed by the second output. According to another aspect of the present invention, the first and second iterations of the CMEA process use the tbox function that replaces its input with a secret bias. According to another aspect of the present invention, the first and second CMEA keys can be used to process the plaintext by the first and second iterations of the CMEA process without undergoing input and output transformations. According to the instructions of the present invention, the ciphertext is introduced, and the steps applied to encrypt the plaintext are reversed in the reverse order, and the encrypted text can be decrypted appropriately.

A device according to the present invention generates text and adds it to an I/O interface that identifies it as generated text, causes the text and identifier to be added to an encryption/decryption processor, which then encrypts the text And supply the transceiver for transmission. When the device receives a transmission via the transceiver, the transmission is identified as the input ciphertext, and the ciphertext and identifier are added to the encryption/decryption processor, which decrypts the ciphertext and supplies it as text The I/O processor specifies the route to its destination. In a preferred embodiment, devices consistent with standard microprocessors and memories currently typically used in such phones are utilized to integrate such devices into wireless phones.

Description of the drawings

From the following detailed description and accompanying drawings, it is apparent that the present invention is more fully understood, as well as its further features and advantages.

Figure 1 is a flowchart showing the prior art CMEA key generation process and CMEA implementation; Figure 2 is a flowchart showing an enhanced CMEA encryption method using multiple CMEA iterations according to the present invention; Figure 3 is A flowchart shows an enhanced CMEA encryption method using multiple CMEA iterations according to the present invention. Before each iteration, there is an input transformation followed by an output transformation; FIG. 4 is suitable for the encryption method according to the present invention. Figure 5 is a detailed diagram of an output transform suitable for use in an encryption method according to the present invention; Figure 6 is a flowchart showing that the method according to the present invention is Decryption of the ciphertext encrypted by the enhanced CMEA process; Fig. 7 is a circuit block diagram showing the telephone set using the enhanced CMEA encryption according to the present invention.

detailed description

The flowchart of FIG. 1 illustrates a prior art method 100, which uses a CMEA key to encrypt a certain type of strict user data sent during a call. The generation and description of CMEA keys are well known in the art. The CMEA key is used to generate a secret array, which is a 256-byte tbox(z). In another way, tbox can be implemented as a function call. Although this kind of realization reduces the application of RAM, the processing time is roughly increased by an order of magnitude.

At step 102, input unprocessed text. At step 104, for a system that implements the tbox as a static table instead of a function call, the static tbox table is derived therein. The tbox table is derived as follows: For each z in the range of 0z<256, tbox(z)=C(((C((C(((C((zXORk0)+k1)+z)XORk2)+ k3)+z)XORk4)+k5)+z)XORk6)+k7)+z, where "+" means mod 256 (mod256) addition, and "XOR" means bitwise Boolean algebraic exclusive OR operator, "Z" is the function argument, k0,..., k7 contain 8 octets (octets) of the CMEA key, and C() is the result of a CAVE (cellular authentication, voice privacy and encryption) 8-bit table lookup.

CMEA consists of three successive stages, each of which changes every byte string in the data buffer. In steps 106, 108, and 110, as will be described here, the first, second, and third stages of the CMEA process are implemented respectively. A data buffer is d bytes long, and each byte is marked by b(i). For integers in the range of 0i<d, the data is encrypted into a password in three stages. The first stage (I) of CMEA is as follows: 1. Initialize variable z to 0, 2. In the range of 0i<d, for successive integer values of i: a. By making q=zi the low-order byte , Form the variable q, where is the bitwise Boolean algebraic XOR operator, b. By making k=TBOX(q), the variable k is formed, c. With b(i)=b(i)+k mod256 Update b(i), and update z with z=b(i)+z mod 256.

The second stage (II) of CMEA is: 1. For all values of i in the range of 0i<(d-1)/2, b(i)=b(i)(b(d-1-i) OR1), where OR is a bit-wise Boolean algebra or operator.

The final or third stage (III) of CMEA is decryption, which is the reverse process of the first stage: 1. Initialize the variable z to 0, 2. In the range of 0i<d, for successive integer values of i: a. A variable q is formed by making q=zi low-order bytes, b. A variable k is formed by making k=TBOX(q), c. Z, d is updated by z=b(i)+z mod256 . Update b(i) with b(i)=b(i)-k mod256.

At step 112, the final processed output is provided.

The CMEA process is self-reversing, that is, the same steps applied in the same order are both used to encrypt plaintext and decrypt ciphertext. Therefore, there is no need to determine whether encryption or decryption is being implemented. However, it has been shown that the CMEA process will suffer a blow, which will reproduce the CMEA key applied to a call.

In order to provide additional security to user information, the encryption system according to the present invention preferably implements two iterations of the CMEA process, each iteration using a different key. Before and after the first iteration of the CMEA process, the first input transformation and the first output transformation are performed, and after the second iteration of the CMEA process, the second input transformation and the second output transformation are performed. According to another encryption system of the present invention, it is preferable to add at least one input permutation of tbox to one or more iterations of the CMEA process to improve the application of the tbox function. The application of the improved tbox function is published in our related patent application, entitled "Method and device for improving the security of wireless telephone messages and expanding the key into the lookup table to enhance security". It is in line with this patent. The application was filed on the same day and is hereby incorporated for reference. In another aspect of the present invention, the first and second iterations of the CMEA process can be implemented, but no input and output changes are made before and after each iteration of the CMEA process.

Figure 2 is a flowchart showing the steps performed by the encryption process 200 according to another aspect of the present invention. The encryption process in Figure 2 includes two iterations of the CMEA process associated with the discussion in Figure 1, and a different CMEA key is used in each iteration. At step 202, the plaintext is introduced into the encryption process. At step 204, the CMEA process using the first CMEA key is used to encrypt the plaintext in the first iteration. At step 206, the first iteration is completed, and an intermediate ciphertext is generated. At step 208, the CMEA process of applying the second CMEA key causes the intermediate ciphertext to undergo the second iteration. At step 210, the final ciphertext is generated.

Fig. 3 is a flowchart illustrating an encryption process 300 according to another aspect of the present invention. At step 302, the plaintext message is introduced into the encryption process. At step 304, the plaintext message undergoes a first input transformation, and a message transformed by the first input is generated. At step 306, the first CMEA key is applied to subject the first input transformed message to the first iteration of the CMEA process, and the first intermediate ciphertext is generated. Preferably, an improved application of the tbox function is used in the first iteration of the CMEA process, in which each input of the tbox function undergoes a permutation. The application of the improved tbox function is disclosed in our above-mentioned related patent application. At step 308, the output of the first iteration of the CMEA process is subjected to a first output transformation, and a message with the first output transformation is generated. At step 310, the first intermediate ciphertext undergoes a second input transformation, and a message transformed by the second input is generated. In step 312, the second CMEA key is applied to subject the transformed intermediate ciphertext to the second iteration of the CMEA process, and a second intermediate ciphertext is generated. In the second iteration of the CMEA process, it is desirable to use the improved tbox function application described in the patent application described above. At step 314, the second intermediate ciphertext is subjected to a second output transformation, resulting in a second output transformed message. At step 316, the message transformed by the second output is output as the final ciphertext.

FIG. 4 is a diagram showing the input transformation 400 in detail, which is suitable for application in the encryption process 300 described in relation to FIG. 3. The inverse input transform 400 is self-inverting. Each of j+1 input data octets (octets), j+1, j, ..., 2, 1, and a transform octet are XOR (exclusive OR) operation. The transform octet is a confidential value, and it can be generated by any one of many techniques commonly used in this technical field. Preferably, two transformation octets are applied, which are added to the input data octet in an alternating form. The transformation octet I2 is added to the input data octet j+1, the transformation octet I1 is added to the input data octet j, the transformation octet I2 is added to the input data octet j-1, and so on. After applying the transformation, a new input data set octet j+1', j'...2', 1'is generated, and then used in conjunction with the narrative in the discussion in Figure 3 above.

FIG. 5 is a diagram showing the forward/reverse output conversion 500, which can be suitably applied in the encryption process 300 described in relation to FIG. 3. For the forward output transformation, each of j+1 output data octets, j+1, j, ..., 2, 1, is added to one transformation octet. The transform octet is a confidential value, and it can be generated by any of many techniques commonly used in this technical field. For the inverse output transformation, subtraction is used instead of addition. Preferably, two transform octets are applied, which are added to the output data octet in an alternating fashion. The transformation octet O2 is added to the output data octer j+1, the transformation octet O1 is added to the output data octet j, the transformation octet O2 is added to the output data octet j-1, and so on. After applying the transformation, a new output data set octet j+1', j'...2', 1'is generated, and then used in conjunction with the narrative in the discussion of Figure 3 above.

Since the encryption system of the present invention needs to apply two keys, it is not self-reversing. That is, the same operation performed in the same order will neither encrypt the plaintext nor decrypt the ciphertext. Furthermore, the output transformation described in the discussion regarding FIG. 5 is not self-inverting. Therefore, as described later, there must be a separate decryption process.

Figure 6 shows a decryption process 600 according to one aspect of the present invention. In essence, the steps shown in FIG. 3 are followed, but the order shown in FIG. 3 is reversed. The first and second inverse input and inverse output transforms are used to replace the input and output transforms in Figure 3. The first inverse input transformation is simply the second input transformation described in the discussion above in conjunction with FIG. 3, and the second inverse input transformation is the first input transformation described in the discussion above in conjunction with FIG. 3.

At step 602, the ciphertext message is introduced into the decryption process. At step 604, the ciphertext message is subjected to a first inverse output transformation, and a message after the first inverse output transformation is generated. The first inverse output transformation is the inverse process of the second output transformation described in FIG. 3 and in more detail about the second output transformation described in FIG. 5. In particular, the addition step in the output transformation is offset by the subtraction in the inverse output transformation. At step 606, the first inverse output transformed message undergoes the first iteration of the CMEA process, and a ciphertext message that has been decrypted by the first intermediate is generated. Preferably, the first iteration of the CMEA process uses the application of the tbox function improved in accordance with our above-mentioned related patent applications. The key used in this first CMEA iteration is the second CMEA key and the second tbox input permutation. At step 608, the first intermediate ciphertext undergoes a first inverse input transformation, which is the same as the second input transformation described in the discussion about FIG. 3, to generate a message that has undergone the first inverse input transformation. Thereafter, in step 610, the message of the first inverse input transformation is subjected to the second inverse output transformation, which is the inverse process of the first output transformation described in the discussion of FIG. 3, to produce the second inverse output transformation. news. At step 612, the second inverse output transformed message undergoes the second iteration of the CMEA process, and a second intermediate decrypted ciphertext message is generated. Preferably, the second iteration of the CMEA process uses an improved application of the tbox function. The key applied to this iteration in the modified CMEA process is the first CMEA key and the first tbox input replacement. At step 614, the second intermediate decrypted ciphertext message is subjected to a second inverse input transformation, which is the same as the first input transformation described in the discussion of FIG. 4, to produce a second inverse input transformed message. In step 616, the second CMEA iteration is completed, and the message of the second inverse input transformation is output as the final plaintext.

The encryption described in the discussion of FIG. 2 can be similarly reversed. In order to decrypt the encrypted message with the characteristics of the present invention described above in conjunction with FIG. 2, the decryption shown in FIG. 6 is implemented, but the inverse input and inverse output transformations are not implemented.

Since the encryption described in Figure 3 cannot be simply implemented in the decryption described in Figure 6, it is necessary to have a device according to the present invention that applies the encryption and decryption system to identify when a message needs to be encrypted and when The message needs to be decrypted.

Figure 7 is a circuit block diagram showing a wireless telephone 700 according to the present invention, which is equipped with a circuit for message transmission and encryption/decryption. The circuit device must be able to identify whether a message needs to be encrypted or decrypted, but also Implement appropriate encryption or decryption. The telephone 700 includes a transceiver 702, an input/output (I/O) interface 704, an encryption/decryption processor 706, and a key generator 708. The key generator 708 receives and uses the stored confidential data to supply the key generator. Preferably, the stored confidential data is stored in a non-volatile memory 710, such as an EEPROM or a flash memory. The key generator 708 stores the generated key in the memory 712. The encryption/decryption processor 706 also includes a memory 714 to store the key, static tbox table and other values received from the key generator 708, where the static tbox table is when it is desired to implement the tbox function as a static table Other values are generated and stored during encryption and decryption. The telephone 700 also includes a message generator 716, which generates a message encrypted by the encryption/decryption processor 706, and is transmitted by the transceiver 702.

When an internally generated message is to be encrypted and transmitted by the telephone 700, the message is transmitted from the message generator 712 to the I/O interface 704. The I/O interface 704 identifies the message as an internally generated message to be encrypted, and transmits the message to the encryption/decryption processor 706 together with the identifier. The encryption/decryption processor 706 receives one or more keys from the key generator 708 and then uses it to encrypt the message. Preferably, the encryption/decryption processor 706 receives two keys from the key generator 708, and then applies the input and output transformations described above with respect to FIG. 3, using these two keys to implement two CMEA iterative encryption .

The encryption/decryption processor 706 provides the plaintext message to the first input transformation, and generates a message after the first input transformation. Thereafter, the first input transformed message undergoes the first iteration of the CMEA process using the first CMEA key, and the first intermediate ciphertext message is generated. The first iteration of the CMEA process can be suitably applied using the modified tbox function, where each tbox function input undergoes a permutation. The first intermediate ciphertext message is subjected to a first output transformation, resulting in a first output transformed message. Thereafter, the first output transformed message undergoes a second input transformation, resulting in a second input transformed message. Then, the second input transformed message is subjected to the second iteration of the modified CMEA process applying the second CMEA key, and a second intermediate ciphertext message is generated. The second iteration of the CMEA process can also be applied appropriately using the improved tbox function. Then, the output of the second iteration of the CMEA process undergoes a second output transformation, producing a message that has been transformed by the second output. Finally, the second iteration is completed, and the message transformed by the second output is generated as the final ciphertext. After the encryption is completed, the final ciphertext can be stored in the memory 714, and routed to the I/O interface 704, and then to the transceiver 702 for transmission.

When the phone 700 receives the encrypted message, the transceiver 702 transmits it to the I/O interface 704. The I/O interface 704 identifies that the message is an encrypted message, and transmits the identifier together with the message to the encryption/decryption processor 706. The encryption/decryption processor 706 receives one or more keys from the key generator 708 and decrypts the message; preferably, the two-iteration CMEA decryption process described in FIG. 6 is applied here.

When the encryption/decryption processor 706 receives the ciphertext message from the I/O interface 704, the ciphertext message undergoes the first inverse output transformation, and generates a message after the first inverse output transformation. This first inverse output transformation is the inverse process of the second output transformation shown in FIG. 3 and in more detail in FIG. 5. In particular, the addition step in the output transformation is cancelled out by the subtraction in the inverse output transformation. After that, the first iteration of the CMEA process was implemented, which desirably used the improved tbox function application to produce the first intermediate decrypted ciphertext message. The keys used in this first CMEA iteration are the second CMEA key and the second tbox input permutation. Thereafter, the first intermediate decrypted ciphertext message is subjected to the first inverse input transformation, and a message subjected to the first inverse input transformation is generated. This first inverse input transformation is the same as the second input transformation described in the discussion with respect to FIG. 3. Then, the second inverse input transformed message is subjected to the second inverse output transformation, resulting in a second inverse output transformed message. This second inverse output transformation is the inverse process of the first output transformation described in the discussion of FIG. 3. Then, implement the second iteration of the CMEA process, which desirably uses the improved tbox function application to produce a second intermediate decrypted ciphertext message. The keys used in the iteration of the modified CMEA process are the first CMEA key and the first tbox replacement. Then, the second intermediate decrypted ciphertext message is subjected to a second inverse input transformation to generate a message that has undergone the second inverse input transformation. This second inverse input transformation is the same as the first input transformation described in the discussion with respect to FIG. 3. The second inverse input transformed message is routed to the I/O interface 704 in plain text, where it is then routed to the location of the final application.

The above description strengthens the CMEA processing. On the one hand, it significantly increases the security. On the other hand, it does not significantly increase the processing or system resources, so it is very suitable for use in environments such as wireless telephone systems. Some equipment units, such as mobile equipment units, often have limited processing power.

Although the present invention has been disclosed through the presented preferred embodiments, it can be known that those skilled in the art can adopt a wide variety of implementation methods, which are consistent with the above discussion and the following claims.