Cryptography – Particular algorithmic function encoding
Reexamination Certificate
1997-10-24
2001-06-26
Elmore, Reba I. (Department: 2181)
Cryptography
Particular algorithmic function encoding
C380S042000, C380S046000
Reexamination Certificate
active
06252958
ABSTRACT:
BACKGROUND OF THE INVENTION
I. Field of the Invention
The present invention relates to encryption. More particularly, the present invention relates to a method and apparatus for generating encryption stream ciphers.
II. Description of the Related Art
Encryption is a process whereby data is manipulated by a random process such that the data is made unintelligible by all but the targeted recipient. One method of encryption for digitized data is through the use of stream ciphers. Stream ciphers work by taking the data to be encrypted and a stream of pseudo-random bits (or encryption bit stream) generated by an encryption algorithm and combining them, usually with the exclusive-or (XOR) operation. 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 secure encryption, the encryption bit stream must be computationally difficult to predict.
Many of the techniques used for generating the stream of pseudo-random numbers are based on a linear feedback shift register (LFSR) over the Galois finite field of order 2. This is a special case of the Galois finite field of order 2
n
where n is a positive integer. For n=1, the elements of the Galois field comprise bit values zero and one. The register is updated by shifting the bits over by one bit position and calculating a new output bit. The new bit is shifted into the register. For a Fibonacci register, the output bit is a linear function of the bits in the register. For a Galois register, many bits are updated in accordance with the output bit just shifted out from the register. Mathematically, the Fibonacci and Galois register architectures are equivalent.
The operations involved in generating the stream of pseudo-random numbers, namely the shifting and bit extraction, are efficient in hardware but inefficient in software or other implementations employing a general purpose processor or microprocessor. The inefficiency increases as the length of the shift register exceeds the length of the registers in the processor used to generate the stream. In addition, for n=0, only one output bit is generated for each set of operations which, again, results in a very inefficient use of the processor.
An exemplary application which utilizes stream ciphers is wireless telephony. An exemplary wireless telephony communication system is a code division multiple access (CDMA) system. The operation of 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 which is fast and uses little memory is well suited for these applications.
SUMMARY OF THE INVENTION
The present invention is a novel and improved method and apparatus for generating encryption stream ciphers. In accordance with the present invention, the recurrence relation is designed to operate over finite fields larger than GF(2). The linear feedback shift register used to implement the recurrence relation can be implemented using a circular buffer or a sliding window. In the exemplary embodiment, multiplications of the elements of the finite field are implemented using lookup tables. A crytographically secured output can be obtained by using one or a combination of non-linear processes applied to the state of the linear feedback shift register. The stream ciphers can be designed to support multi-tier keying to suit the requirements of the applications for which the stream ciphers are used.
It is an object of the present invention to utilize a recurrence relation and output equation having distinct pair distances. Distinct pair distances ensure that, as the shift register used to implement the recurrence relation shifts, no particular pair of elements of the shift register are used twice in either the recurrence relation or the non-linear output equation. This property removes linearity in the output from the output equation.
It is another object of the present invention to utilize a recurrence relation having maximum length. An exemplary maximum length recurrence relation of order 17 is: S
n+17
=141
S
n+15
⊕S
n+4
⊕175
S
n
, where the operations are defined over GF(2
8
), ⊕ is the exclusive-OR operation on two bytes, and
is a polynomial modular multiplication. A recurrence relation of order 17 is well suited to accommodate 128-bit key material which is required for many applications.
REFERENCES:
patent: 4484027 (1984-11-01), Lee et al.
patent: 4617676 (1986-10-01), Jayant et al.
patent: 4769818 (1988-09-01), Mortimer
patent: 4875211 (1989-10-01), Murai et al.
patent: 4901307 (1990-02-01), Gilhousen et al.
patent: 5020060 (1991-05-01), Murai et al.
patent: 5097499 (1992-03-01), Cosentino
patent: 5103459 (1992-04-01), Gilhousen et al.
patent: 5153919 (1992-10-01), Reeds, III et al.
patent: 5172414 (1992-12-01), Reeds, III et al.
patent: 5204902 (1993-04-01), Reeds, III et al.
patent: 5343481 (1994-08-01), Kraft
patent: 5365588 (1994-11-01), Bianco et al.
patent: 5414719 (1995-05-01), Iwaki et al.
patent: 5428628 (1995-06-01), Hassner et al.
patent: 5440570 (1995-08-01), Wei et al.
patent: 5454039 (1995-09-01), Coppersmith et al.
patent: 5703952 (1997-12-01), Taylor
patent: 5835597 (1998-11-01), Coppersmith et al.
patent: 5910907 (1999-06-01), Chen
patent: 5943248 (1999-08-01), Clapp
patent: 5991857 (1999-11-01), Koethe et al.
patent: 6009135 (1999-12-01), Ozluturk
patent: WO94/16509 (1994-07-01), None
patent: 9416509 (1994-07-01), None
Coppersmith, et al. “The Shrinking Generator”Proc. Crypto '93Springer-Verlag, (1994).
Golic, Jovan “On the Security of Nonlinear Filter Generators”Proc. of Fast Software Encryption, Cambridge Workshop, Springer-Verlag, pp. 173-188 (1996).
Meier, et al. “The Self-Shrinking Generator”Communications and Cryptography: Two Sides of One Tapestry, pp. 205-214 R.E. Blahut, et al., eds. Kluwer Acad. Publishers (1994).
Shaheen, K. “Code Book Cipher System” IEEE Communications, pp. 66-71 (1994).
Zeng, et al. Pseudorandom Bit Generators in Stream-Cipher Cryptography IEEE 24(2); 8-17 (1991).
Bruce Scheier, “Applied Cryptography, Second Edition”, text book pages: 385-387, 412-413, 1996.*
Cain et al., “How to Break Gifford's Cipher”, Comp
Elmore Reba I.
Macek Kyong H.
Qualcomm Incorporated
Rouse Thomas R.
Wadsworth Philip R.
LandOfFree
Method and apparatus for generating encryption stream ciphers does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method and apparatus for generating encryption stream ciphers, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for generating encryption stream ciphers will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2494664