I. Field of the Invention
The present invention relates to encryption. More particularly, the present invention relates to a method and apparatus for synchronizing encryption stream ciphers.
II. Background
Encryption is a process whereby a random process manipulates data such that the data is made unintelligible by all but the intended recipient. One method of encryption for digitized data is through the use of stream ciphers, which are generated by secret keys. A widely used secret key system is the Data Encryption Standard (DES) which employs a 56 bit key and 8 non-key parity bits. DES was published as a U.S. Federal Information Processing Standard in 1977. In an encryption scheme using a stream cipher, data and a stream of pseudo-random bits (or encryption bit stream) are combined, usually with the exclusive-or (XOR) operation. Many of the techniques used for generating the stream of pseudo-random numbers are based on linear feedback shift registers over a Galois finite field. The register is updated by shifting a new bit into the register, shifting the other bits over by one bit position, and calculating a new output bit. Decryption is simply the process of generating the same encryption bit stream and removing the encryption bit stream with the corresponding operation from the encrypted data. If the XOR operation was performed at the encryption side, the same XOR operation is also performed at the decryption side. For a secured encryption, the encryption bit stream must be computationally difficult to predict.
An exemplary application that utilizes stream ciphers is wireless telephony. An exemplary wireless telephony communication system is a code division multiple access (CDMA) system. The operation of a CDMA system is disclosed in U.S. Pat. No. 4,901,307, entitled “SPREAD SPECTRUM MULTIPLE ACCESS COMMUNICATION SYSTEM USING SATELLITE OR TERRESTRIAL REPEATERS,” assigned to the assignee of the present invention, and incorporated by reference herein. The CDMA system is further disclosed in U.S. Pat. No. 5,103,459, entitled “SYSTEM AND METHOD FOR GENERATING SIGNAL WAVEFORMS IN A CDMA CELLULAR TELEPHONE SYSTEM,” assigned to the assignee of the present invention, and incorporated by reference herein. Another CDMA system includes the GLOBALSTAR communication system for world wide communication utilizing low earth orbiting satellites. Other wireless telephony systems include time division multiple access (TDMA) systems and frequency division multiple access (FDMA) systems. The CDMA systems can be designed to conform to the “TIA/EIA/IS-95 Mobile Station-Base Station Compatibility Standard for Dual-Mode Wideband Spread Spectrum Cellular System,” hereinafter referred to as the IS-95 standard. Similarly, the TDMA systems can be designed to conform to the TIA/EIA/IS-54 (TDMA) standard or to the European Global System for Mobile Communication (GSM) standard.
Encryption of digitized voice data in wireless telephony has been hampered by the lack of computational power in the remote station. This has led to weak encryption processes such as the Voice Privacy Mask used in the TDMA standard or to hardware generated stream ciphers such as the A5 cipher used in the GSM standard. The disadvantages of hardware-based stream ciphers are the additional manufacturing cost of the hardware and the longer time and larger cost involved in the event the encryption process needs to be changed. Since many remote stations in wireless telephony systems and digital telephones comprise a microprocessor and memory, a stream cipher that is fast and uses little memory is well suited for these applications.
There is a problem of how to generate a specific segment of the stream cipher efficiently without having to generate all of the stream cipher preceding that specific segment. This problem arises due to the required synchronization of the stream cipher at the transmission end and the receiving end of the encrypted data stream. This problem can arise in numerous circumstances. In one circumstance, a mobile station that is “roaming” from the coverage of one base station to a second base station can face difficulties when transmitting an encrypted data stream. The second base station has to regenerate the stream cipher to the current state at which the mobile station is transmitting the encrypted data stream in order for the second base station to continue the decrypt the encrypted data stream. Regenerating the entire stream cipher can be computationally time consuming, which can interfere with the voice quality of the live communication.
In another circumstance, a single stream of encrypted data may be intended for multiple receivers, such as multiple computers on a single network. It would be desirable that the receivers be able to decrypt only those portions of the encrypted data stream for which they are the intended recipients.
Other circumstances arise where it is desirable to avoid the use of system resources on the regeneration of a stream cipher from an initial state to a current state.