Cryptography – Particular algorithmic function encoding
Reexamination Certificate
1998-07-29
2002-04-23
Hayes, Gail (Department: 2131)
Cryptography
Particular algorithmic function encoding
C380S042000
Reexamination Certificate
active
06377687
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates generally to wireless telephone cryptography. More particularly, the invention relates to an improved security cryptosystem for rapid and secure encryption in a wireless telephone system without requiring large amounts of additional system resources.
BACKGROUND OF THE INVENTION
Wireless telephony uses messaging for several purposes including, for example, conveying status information, reconfiguring operating modes, handling call termination, and conveying system and user data such as a subscriber's electronic serial number and telephone number, as well as conversations and other data transmitted by the user. Unlike ordinary wire telephony, in which a central serving station is connected to each subscriber by wire, thus ensuring a fair degree of protection from eavesdropping and tampering by an unauthorized party (attacker), wireless telephone serving stations (i.e., base stations) must transmit and receive messages via signals over the air, regardless of the physical location of the subscribers.
Because the base station must be able to send and receive messages to and from a subscriber anywhere, the messaging process is wholly dependent on signals received from and sent to the subscriber equipment. Because the signals are transmitted over the air, they can be intercepted by an eavesdropper or interloper with the right equipment.
If a signal is transmitted by a wireless telephone in plaintext, a danger exists that an eavesdropper will intercept the signal and use it to impersonate a subscriber, or to intercept private data transmitted by the user. Such private data may include the content of conversations. Private data may also include non-voice data transmitted by the user such as, for example, computer data transmitted over a modem connected to the wireless telephone, and may also include bank account or other private user information transmitted typically by means of keypresses. An eavesdropper listening to a conversation or intercepting non-voice data may obtain private information from the user. The message content of an unencrypted telephone signal (i.e., plaintext signal) is relatively easily intercepted by a suitably adapted receiver.
Alternatively, an interloper can interect himself into an established connection by using a greater transmitting power, sending signals to the base station, and impersonating a party to the conversation.
In the absence of applying cryptography to messages being transmitted by wireless signals, unauthorized use of telephone resources, eavesdropping of messages, and impersonation of called or calling parties during a conversation are possible. Such unauthorized interloping and/or eavesdropping has in fact proven to be a grave problem and is highly undesirable.
The application of cryptography to wireless telephone applications offers a solution to the security problems discussed above, but the application of standard cryptography methods to wireless telephony has encountered significant difficulties due to the computationally-intensive nature of these methods. Specifically, these methods are subject to the constraints imposed by the desire to furnish a small wireless handset and the constraints on processing power imposed by the small size of the handset. The processing power present in typical wireless handsets is insufficient to handle the processing requirements of commonly known cryptographic algorithms such as DES (Data Encryption Standard). Implementing such a commonly known cryptographic algorithm in a typical wireless telephone system would potentially increase the time needed to process signals (i.e., encrypt and decrypt), thereby causing unacceptable delays for subscribers.
One cryptographic system for wireless telephony is disclosed in Reeds U.S. Pat. No. 5,159,634 (“Reeds”), incorporated herein by reference. Reeds describes a cryptographic process known as the CMEA (“Cellular Message Encryption Algorithm”) process. Central to the operation of the CMEA is the tbox function, which is a one to one mapping of one octet to another, using a known table and a secret key. Beginning with an initial index, key material is combined with table material in multiple iterations to perform the mapping. The tbox function can be implemented either as a function call or as a static memory-resident tbox table. The tbox table's purpose, when implemented as in the latter case, is to allow significant speed-up of encryption for a given security level.
Enhancements to the CMEA process exist, disclosed in our patent application Ser. No. 09/059,107, entitled “Methods and Apparatus for Multiple-Iteration CMEA Encryption and Decryption for Improved Security for Cellular Telephone Messages” filed on Apr. 13, 1998, and our patent application Ser. No. 09/059,116, entitled “Methods and Apparatus for Enhanced Security Expansion of a Secret Key Into a Lookup Table for Improved Security for Wireless Telephone Messages” filed on Apr. 13, 1998. These enhancements provide significantly increased security to the CMEA process. However, additional enhancements would provide further increased security.
The CMEA process of the prior art may be significantly improved as described in greater detail below. These improvements provide an additional degree of security which is highly advantageous. The cryptographic process of Reeds can be improved through modification and simplification. Either the original process of Reeds, or the modified and simplified process, which will hereinafter be referred to as the modified CMEA, can be used in an improved process including further improvements which are collectively termed ECMEA (Enhanced CMEA).
SUMMARY OF THE INVENTION
The present invention provides an additional degree of security to cryptographic algorithms such as CMEA by providing a forward enhanced CMEA, or ECMEA, process, as well as a reverse ECMEA process. Information encrypted by the forward process is decrypted by the reverse process, and information encrypted by the reverse process is decrypted by the forward process. The forward ECMEA process subjects the message to a transformation before an iteration of the CMEA process, and an inverse transformation after the iteration of the CMEA process. The iteration of the CMEA process may be either the original process of Reeds, or the modified CMEA process. Where the original process of Reeds is meant, the term ‘original CMEA’ will be used, and where the modified CMEA process is meant, the term ‘modified CMEA’ will be used. Where the term ‘CMEA process’ is used without further definition, either the original CMEA or the modified CMEA may be used, the choice being dependent on design preference. It is preferred, however, that the modified CMEA be used unless design preferences suggest otherwise. The iteration of the CMEA process is enhanced by permutation of the inputs to the tbox function by a first secret offset. The tbox function employed by the CMEA process is enhanced through the use of an involutary lookup table. The transformation and inverse transformation employ the first secret offset and a second secret offset. The transformation performs an offset rotation of the first offset and an involutary lookup of each octet, and performs bit-trades between each pair of adjacent octets. For all octets except the last octet, the transformation performs a random octet permutation, which is an exchange between the previous octet and a random one below it. The transformation also performs a final octet permutation, which is an exchange between the last octet and a random one below it.
The inverse transformation performs an initial offset rotation on the second offset, and an initial octet permutation on the last octet, which is an exchange of the last octet with a random one below it. For all octets except the last octet, the inverse transformation performs a random octet permutation, which is an exchange between the octet and a random one below it. The transform performs bit-trades between each pair of adjacent octets, and performs an involutary lookup of each octet foll
Etzel Mark H.
Frank Robert John
Heer Daniel Nelson
McNelis Robert Joseph
Mizikovsky Semyon B.
Birch & Stewart Kolasch & Birch, LLP
Hayes Gail
Lucent Technologies - Inc.
Seal James
LandOfFree
Methods and apparatus for enhanced CMEA employing enhanced... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Methods and apparatus for enhanced CMEA employing enhanced..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Methods and apparatus for enhanced CMEA employing enhanced... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2897602