LFSR provides encryption
Edited by Bill Travis and Anne Watson Swager
Antonella Di Lillo and Giovanni Motta, Brandeis University, Waltham, MA -- EDN, September 13, 2001
LFSRs (linear-feedback shift registers) find extensive use in cryptography. For example, the cryptographic algorithms in the GSM (Global System for Mobile communications) mobile-phone system rely on the use of LFSRs. An LFSR comprises a register containing a sequence of bits and a feedback function. In general, this function is an XOR (exclusive-OR) operation on certain bits in the register. The list of these bits is a "tap sequence." You use an LFSR to generate a pseudorandom sequence of bits that undergo an XOR operation. The XOR result then connects to the input of the LFSR. Repeating the process at the decoder side returns the original sequence of bits. Listing 1 presents the encryption and decryption process. To generate a pseudorandom sequence, you load the register with a nonzero content, and the software then computes the XOR of the taps and shifts all bits in the register one bit to the left. Finally, the routine inserts the results of the XOR operation in the rightmost position (Figure 1). The program adds this 1-bit result to the sequence and repeats the procedure to generate other bits.
LFSRs are well-suited to hardware implementations, but their use in software programs unfortunately often suffers from inefficient implementations. LFSRs with few taps, or sparse LFSRs, are easier to use because you need calculate the XOR of only a few bits. On the other hand, for cryptographic purposes, you must avoid sparse polynomials because the resulting algorithms are easy to break. The C program in Listing 1 has the advantage of implementing the XOR of a 32-bit integer with an efficient algorithm, thus making an efficient way to implement the software of an LFSR. The program encrypts a standard input into a standard output one character at a time. You use an LFSR to generate eight random bits at a time, and the routine XORs the random bits to the current character. The encryption key is a nonzero integer that you use as the initial status of the register. The key is the same for both encoding and decoding. The variable taps represent the 32 binary coefficients of a primitive polynomial of degree 31. Several other choices are possible; Listing 1 suggests five of them in the comments. You can safely remove the code that describes the number of characters encrypted and the running time to make the program even smaller.
Is this the best Design Idea in this issue? Vote at www.ednmag.com.
