（转载）一次性加密和伪随机位序列

In this chapter we introduce a simple specialized machine called a linear feedback shift register (LFSR). We describe how it works, discover interesting applications, and study its limitations. Later, in the book, we will repeat the same process with a general-purpose computer.

One-time pad. As motivation for studying linear feedback shift registers, we will first consider an interesting application to cryptography. Cryptography is the science of creating secret codes, e.g., suppose Alice wants to send a secret message to Bob over the Internet. Alice's first step is to encrypt the message. Encrypting a message means transforming it into another message. She will send this encrypted message over the Internet. Of course, for the cryptographic scheme to be useful, Bob must be able to decrypt the encrypted message back into its original form. A one-time pad is a simple encryption method that is provably secure. That is, even if a malicious third party Eve is able to intercept the encrypted message, she will not be able to glean any information about the contents of the original message, other than its length.

Encryption. Now, we describe how Alice can use a one-time pad to send Bob a message.

    * First, we'll assume that Alice's message consists of N bits. A bit is one of two values 0 (false) or 1 (true). If Alice's message consists of text, then she must first pre-process it into a sequence of bits. A simple scheme for doing this is to use the Base64 encoding of the text: replace every occurrence of the letter 'A' with 000000, 'B' with 000001, and so forth according to the table below:

          Binary Char   Binary Char   Binary Char   Binary Char   Binary Char   Binary Char
          000000 A 001011 L 010110 W 100001 h 101100 s 110111 3
          000001 B 001100 M 010111 X 100010 i 101101 t 111000 4
          000010 C 001101 N 011000 Y 100011 j 101110 u 111001 5
          000011 D 001110 O 011001 Z 100100 k 101111 v 111010 6
          000100 E 001111 P 011010 a 100101 l 110000 w 111011 7
          000101 F 010000 Q 011011 b 100110 m 110001 x 111100 8
          000110 G 010001 R 011100 c 100111 n 110010 y 111101 9
          000111 H 010010 S 011101 d 101000 o 110011 z 111110 +
          001000 I 010011 T 011110 e 101001 p 110100 0 111111 /
          001001 J 010100 U 011111 f 101010 q 110101 1
          001010 K 010101 V 100000 g 101011 r 110110 2

      For example, to encode the 9-character message SENDMONEY, we would use the following sequence of N = 54 bits.

             S     E     N     D     M     O     N     E     Y        (message)
             010010000100001101000011001100001110001101000100011000   (message bits)

      It is also possible to convert audio, image, or video data into a sequence of bits. Digital computers do exactly this to store MP3, JPEG, and DivX files on your computer.
    * Now, we assume Alice and Bob have agreed on a random sequence of N bits ahead of time, which they each know, but have kept it a secret from the rest of the world. These random bits are called the one-time pad. In the example above, Alice and Bob need to share 54 bits ahead of time, say

             110010010011110110111001011010111001100010111111010010   (one-time pad)

    * Alice encrypts her message by lining it up with the one-time pad, combines pairs of bits using the exclusive or (XOR) function. The XOR function of two bits is 0 if the sum of the two bits is even and 1 if the sum is odd. Equivalently, the XOR function of two bits is 0 if the bits are the same, and 1 if they are different. The truth table below characterizes the behavior of the XOR function.
       x  y  XOR
      0 0 0
      0 1 1
      1 0 1
      1 1 0

      Applying the XOR function to Alice's message bits and the one-time pad yields:

         010010000100001101000011001100001110001101000100011000   (message bits)
      ^  110010010011110110111001011010111001100010111111010010   (one-time pad)
         ------------------------------------------------------
         100000010111111011111010010110110111101111111011001010   (encrypted bits)

      We note that ^ is the Java symbol for exclusive or. We use the XOR function to prevent an eavesdropper from discovering the original message. If each bit of the one-time pad is chosen according to a fair and independent coin flip, then the corresponding bit in Alice's message also has an equal chance of winding up 0 or 1. To an eavesdropper, the encrypted bits are indistinguishable from a sequence of random coin flips.
    * Finally, Alice converts the encrypted bits back to text using Base64 encoding.

         100000010111111011111010010110110111101111111011001010   (encrypted bits)
         g     X     7     6     W     3     v     7     K        (encrypted message)

      Alice encrypts the message "SENDMONEY" and sends it to Bob.

Decryption. Bob decrypts the encrypted message by applying the exact same procedure.

    * First, he converts the encrypted message to bits using the Base64 encoding.

    * Next, he takes the XOR of the encrypted message with the one-time pad.

    * Finally, he converts the bits to text using Base64 encoding.

         g     X     7     6     W     3     v     7     K        (encrypted message)
         100000010111111011111010010110110111101111111011001010   (encrypted bits)
      ^  110010010011110110111001011010111001100010111111010010   (one-time pad)
         ------------------------------------------------------
         010010000100001101000011001100001110001101000100011000   (message bits)
         S     E     N     D     M     O     N     E     Y        (message)

Implementation. To implement one-time pads, we must generate and distribute long sequences of random bits since the number of random bits required is equal to the number of bits in the message we wish to send. To ensure security, we must not reuse the bits - hence the name one-time pad.

A simple machine. A LFSR is a simple machine that captures many of the properties of real computers. One of its main application is generating pseudo-random bits. To generate a random bit, we could flip a fair coin and associate heads with 0 and tails with 1. This is horrendously tedious if we need to generate a million random bits. Instead, we would like to produce random bits automatically, using some kind of mechanical device. However, traditional computers are deterministic: they follow a proscribed set of rules, and given the same input, they always produce the same output. Nevertheless, it is possible to generate sequence of random bits that "look" like truly random bits. Such sequences are called pseudo-random. Robert R. Coveyou once remarked, "The generation of random numbers is too important to be left to chance." But according to the famous physicist John von Neumann, "anyone who considers arithmetical methods of producing random digits is, of course, in a state of sin." Prepare yourself, as we are about to enter a state of sin.

A LFSR is comprised of four components. A cell is a storage element that holds one bit. A register is a sequence of cells. The behavior of the LFSR changes at discrete time intervals, when the clock ticks. A shift register is a register whose bits propagate one cell to the left when the clock ticks. Whatever bit is stored in cell i at time t is stored in cell i + 1 at time t + 1. To completely characterize the behavior of the machine, we must specify what happens at the boundary conditions (cell 0 and cell 10). We simply discard the bit stored in cell 10 since there is no room to store it in the next time step. The bit stored in cell 0 at time t + 1 is the exclusive or (XOR) of the bits stored in cells 8 and 10 at time t. Below are the contents of an 11-bit LFSR after the first eight time steps.

    time |  X  9  8  7  6  5  4  3  2  1  0
    ---------------------------------------
      0  |  0  1  1  0  1  0  0  0  0  1  0
    ---------------------------------------
      1  |  1  1  0  1  0  0  0  0  1  0  1
      2  |  1  0  1  0  0  0  0  1  0  1  1
      3  |  0  1  0  0  0  0  1  0  1  1  0
      4  |  1  0  0  0  0  1  0  1  1  0  0
      5  |  0  0  0  0  1  0  1  1  0  0  1
      6  |  0  0  0  1  0  1  1  0  0  1  0
      7  |  0  0  1  0  1  1  0  0  1  0  0
      8  |  0  1  0  1  1  0  0  1  0  0  1
      9  |  1  0  1  1  0  0  1  0  0  1  0
     ...

The description above completely specifies the behavior of the machine, except for the starting input or seed. Any value other than all 0's will do. If we specify 001101000010 as the seed, then the first 8 steps of the machine evolves as above. It is interesting in consider the sequence of bits that appear in cell 0. The first 1000 such bits are listed below.

    110010010011110110111001011010111001100010111111010010000100110100101
    111001100100111111101110000010101100010000111010100110100001111001001
    100111011111110101000001000010001010010101000110000010111100010010011
    010110111100011010011011100111101011110010001001110101011101000001010
    010001000110101010111000000010110000010011100010111011010010101100110
    000111111100110000011111100011000011011110011101001111010011100100111
    011101110101010101000000000010000000010100000010001000010101010010000
    000110100000111001000110111010111010100010100001010001001000101011010
    100001100001001111001011100111001011110111001001010111011000010101110
    010000101110100100101001101100011110111011001010101111000000100110000
    101111100100100011101101011010110001100011101111011010100101100001100
    111001111110111100001010011001000111111010110000100011100101011011100
    001101011001110001111101101100010110111010011010100111100001110011001
    101111111110100000001001000001011010001001100101011111100001000011001
    0100111110001110001101101101110110....

Can you see any pattern? These bits are not truly random, since they arise from a precise set of rules. Once the machine is started with a given seed, the same sequence of bits is produced.

Analysis. Now that we have a machine (LFSR) that generates pseudo-random bits, we are interested in analyzing properties of the machine and the bits they produces.

    * Repeating sequences. A natural question is to ask whether or not the bits repeat. For example, the sequence 1110111101111011110111101 repeats after every 5 bits. After very careful and tedious inspection, you might notice that the pattern of bits produced by the machine above repeats every 2047 steps, but not before. In fact, you would get a cycle length of 2047 regardless of the initial seed (as long as it is nonzero). This is essentially the best you can hope for with any 11-bit machine. The state of the LFSR is characterized by 11 bits, so the machine only has 211 = 2048 possible states. Once it revisits a state, it gets caught in a loop, and will repeat the same sequence of values forever. The LFSR can only go 2048 steps without revisiting a state.
    * Randomness. A sequence which takes a large number of steps to repeat is clearly necessary if we want a pseudo-random number generator, but it is not sufficient. For example, counting from 0 to 2047 in binary has the same property, but is far from anything we would consider to be random....
    * Taps. The cells that are XOR'ed together are called taps. What happens if we choose a different set of taps instead of 8 and 10? It turns out that the choice of taps is very important. The taps 1 and 10 would also produce a cycle of length 2047. However, if we chose 4 and 10 as the taps, the cycle length would decrease to 595 (for the same starting seed value). Understanding why this is the case requires mathematics beyond the scope of this book (abstract algebra and finite fields).
    * Scalability. The 11-bit LFSR produces 2047 pseudo-random bits before repeating. What if we need more? The LFSR naturally extends to store more bits. With a careful choice of tap positions, it is possible to get pseudo-random bits with a cycle length of 1 million with 20 cells (taps 2 and 19), or 1 billion with 30 cells (taps 0, 3, 5, and 29). Here are some taps of maximal length taps for N-bit linear feedback shift registers.
    * Security. Berlekamp and Massey discovered an amazing algorithm that can reconstruct an N-bit LFSR after seeing only 2N bits. That is, after seeing the first 2N bits from any LFSR, the Berlekamp-Massey algorithm can correctly predict every future bit. Thus, we should not use a LFSR to generate random bits for a one time pad in a mission critical application because a knowledgeable adversary can break the system. In Section 7.9 we will consider cryptographic methods that cannot be so easily circumvented.

One of the major drawbacks of one-time pads is key distribution. The two parties must exchanges private keys prior to their communication. Until somewhat recently, the White House and Kremlin would communicate this way. They employed trusted couriers who would travel with the one-time pads in a briefcase, handcuffed to themselves. Another problem is that if Alice sends Bob a message, there is no way that Bob can prove to a third party that Alice really sent it. In Section 10.x we will consider the very widely used RSA cryptosystem, which overcomes these obstacles and more.

Other applications. Most modern military cryptosystems use LFSR in some form. Cray supercomputers even have a built-in instruction called population count that directly supports the simulation of LFSRs, and this support is required in some government contracts! (Reference: Applied Crypto, p. 380)

DVD encryption. Another application of LFSRs is to encrypt DVDs with CSS (content scrambling system). CSS was designed to prevent copying DVD content and to prevent playing DVDs designed for one region in the world from being played in another region. CSS relies on two LFSRs (one of 17 bits, the other of 25 bits) and a 40-bit key to encrypt the data on a DVD. To play back the DVD, you need licensed hardware or software that is capable of decrypting the data. Since the CSS license is incompatible with open source software, Linux users could not play DVDs on their own computers. On October 6, 1999, in response to this dire situation, Norwegian teenager Jon Johansen released a program called DeCSS which decrypts CSS-encrypted DVDs and allows them to be played back (or copied). The security of the CSS encryption scheme relied on the bits generated from the LFSR to be random. However, they are not random, and this enabled programmers to completely reverse engineer the scheme and break the CSS system.

Context. The LFSR shares many important properties with everyday computers. Both are build from simple components; both scale to solve huge problems; both require a deep understanding to use effectively.

  Basic Component   LFSR Computer
Control Start, stop, load Start, stop, load
Clock Regular pulse 2.8 GHz pulse
Memory 11 bits 512 MB
Input Seed Sequence of bits
Computation XOR, shift Logic, arithmetic, ...
Output Pseudo-random bits Sequence of bits

The critical difference between a LFSR and a computer is that a computer can be programmed to simulate any abstract machine.

Simulating an LFSR in Java. It is possible to build an LFSR out of physical components. Another way to study its behavior is by writing a Java program. You will learn about writing Java programs soon, but to give you an idea, the Java program LFSR.java prints out the first N bits of the LFSR described above, where N is a parameter specified by the user. Even without any programming experience, you may be able to glean information from the code. In Java a boolean variables stores one of two values, true or false. The ^ operator means exclusive or.

/*************************************************************************
*  Compilation:  javac LFSR.java
*  Execution:    java LFSR N
* 
*  Simulate a LFSR for N steps and print results.
*
*  % java LFSR 40
*  0100110010000001100010001011101010111100
*
*************************************************************************/

public class LFSR {

    public static void main(String[] args) {
        // initial fill
        boolean[] a = { false, true, false, false, false,
                        false, true, false, true, true, false
                      };
        int T = Integer.parseInt("40");    // number of steps
        int N = a.length;                     // length of register
        int TAP = 8;                          // tap position


        // Simulate operation of shift register.
        for (int t = 0; t < T; t++) {

           // Simulate one shift-register step.
           boolean next = (a[N-1] ^ a[TAP]);  // Compute next bit.

           for (int i = N-1; i > 0; i--)
              a[i] = a[i-1];                  // Shift one position.

           a[0] = next;                       // Put next bit on right end.

           if (next) System.out.print("1");
           else      System.out.print("0");   
         }
        System.out.println();   
    }
}