Subscriber unit for generating a stream cipher6714614Abstract One embodiment of the invention is a subscriber unit for transmitting communication signals. The subscriber unit comprises a cipher stream generator which generates a cipher stream to encipher a digital data stream. A data stream mixer mixes the cipher stream with the digital data stream. An antenna radiates the mixed cipher and data stream as a communication signal. Another embodiment of the invention is a subscriber unit for receiving communication signals. The subscriber unit comprises a cipher stream generator for generating a cipher stream with the received communication signal to produce a decoded data stream. The cipher steam generator includes first and second linear feedback shift registers. Each has a clock input and an output. The outputs are combined to generate the cipher stream. The output of the second register is combined with a clock signal which is inputted to the clock input to the first register. Claims What is claimed is: Description BACKGROUND OF THE INVENTION
Initial loading .fwdarw. 111
011
001
100
010
101
110
Repeat .fwdarw. 111
011
.
.
.
The three bit LFSR 34, as shown above, has a very small period (i.e. seven). Accordingly, a LFSR of this size does not provide very secure transmission of data. A spread spectrum transmitter 200 made in accordance with the present invention is shown in FIG. 5. The transmitter 200 includes all of the components of the spread spectrum transmitter 10 shown in FIG. 1, which function in the same manner except for the cipher stream generator 220 and keys 210 which will be explained in further detail hereinafter. Although FIG. 5 shows a transmitter 200 for transmitting one channel, multiple channels may be combined and then enciphered by cipher stream generator 220. Referring to FIG. 6, the cipher stream generator 220 includes two LFSR circuits, (L.sub.1, L.sub.2). The output of the second LFSR circuit L.sub.2 is used to control the clock of the first LFSR circuit, L.sub.1. For example, the output of the second LFSR L.sub.2 is preferably connected to an AND gate 222, which is connected to the clock input of the first LFSR L.sub.1. The AND gate 222 could be replaced by a NAND gate. Other gates such as OR, NOR, XOR, etc. or a combination of gates may also be used in place of the AND gate 222. Exclusive-OR gates 38 provide feed back to shift registers L.sub.1, L.sub.2. The cipher stream generator 220 also includes an exclusive-OR gate 224, which is connected to the outputs of the LFSRs L.sub.1, L.sub.2. The exclusive-OR gate 224 combines the outputs of the LFSRs L.sub.1, L.sub.2 and then outputs the cipher stream. The initial states of the two LFSRs L.sub.1, L.sub.2 are the two keys that are shared between the cipher stream generator 220 and decipher stream generator 320. The decipher stream generator 320, which will be explained in more detail hereinafter, is preferably the same as the cipher stream generator 220. The cipher stream generator 220 and decipher stream generator 320 are preferably used in synchronous mode (as opposed to self-synchronous mode) because the self-synchronous mode is subject to error propagation due to single bit errors common in wireless transmission. In self-synchronous stream ciphers, the enciphered digital data is used as a part of the key for enciphering the following data bits. The problem with this approach is that if a bit is corrupted during transmission and it is deciphered incorrectly, it corrupts the following bits as well since it is also used as the cipher key for the following data bits. All ciphering schemes other than a one time lookup table are periodic. In order to send a secure transmission, the cipher stream generator 220 and decipher stream generator 320 should have as long a period as practical. The two LFSRs L.sub.1, L.sub.2 generate the maximum period if the tap coefficients of the feedback correspond to a primitive polynomial. Such a sequence is called a maximum length sequence (m-sequence). Although it is not required, in one embodiment, the maximum period is obtained when the periods of the individual outputs of the two LFSRs L.sub.1, L.sub.2 are relatively prime (the periods of the individual outputs do not have a common factor). For example, if the first LFSR L.sub.1 has a bit length of three, the individual output period is seven. If the second LFSR L.sub.2 has a bit length of two, the individual output period is three. Therefore, the output periods do not have the same common factor. A primitive polynomial, which is well known in finite field algebra, generates a period 2.sup.L -1 if it is of degree L. A set of polynomials form a finite field. A finite field has at least one primitive element such that all nonzero elements of the field are powers of this primitive element. A polynomial that has a primitive element as a root is called a primitive polynomial. Therefore, when the LFSR circuits L.sub.1, L.sub.2 have lengths L.sub.E1 and LE.sub.E2 respectively, the output of both the cipher stream generator 220 and decipher stream generator 320 have the period: Output period.apprxeq.2 L.sub.E1 +L.sub.E2 Equation (2) When lengths of the two LFSRs L.sub.1,L.sub.2 are in the order of .about.20, the period of the stream cipher is .about.10.sup.12 bits. This means that a 32 kbits/sec data stream can be encrypted continuously for over a year without repeating the stream cipher. The linear complexity of the cipher stream generator 220 is the length of the shortest LFSR that can generate the output of the cipher stream generator 220. It is often used as a measure of randomness of the cipher stream generator 220 output. The linear complexity of this cipher stream generator 220 is in the order of Linear complexity.apprxeq.(2.sup.L.sup..sub.E .sup.1)L.sub.E2 +(2.sup.L.sup..sub.E2 )L.sub.E1 i Equation (3) If the output of the cipher stream generator 220 were to be repeated using a single equivalent LFSR, the register would have to be over 20 million stages long (for L.sub.E1 and L.sub.E2.about.20 as above). A cipher stream generator 220 is called balanced if its output is the same as the output of each internal LFSR circuit L.sub.1, L.sub.2 with the same probability. Preferably, the output value should be the same as the output of either one of the LFSR circuits L.sub.1, L.sub.2, i.e. a probability of 0.5. It is important to have a cipher that is balanced because it is easier to break ciphers that are not balanced. If the combinations of the outputs of the LFSR circuits L.sub.1, L.sub.2 and the output of the cipher stream generator 220 are considered, it can be seen that the cipher stream is perfectly balanced and is the same as each LFSR L.sub.1, L.sub.2 output half of the time. The initial state of the cipher stream generator 220 is determined by the two keys K.sub.1 and K.sub.2, which are the initial states of the two LFSRs L.sub.1, L.sub.2 respectively. To protect against insertion attacks, the keys K.sub.1 and K.sub.2 should be changed often, (preferably at least once every period of the cipher). The more combinations for the keys K.sub.1 and K.sub.2, the more secure the transmission. The number of key combinations in this example is Key combinations.apprxeq.2L.sub.E1 +L.sub.E2 Equation (4) which is an extremely large number. The cipher stream generator 220 of the present invention has the following advantages: 1) it has a very large linear complexity; 2) it has a very large period; 3) its output is balanced with respect to the outputs of the two LFSR circuits L.sub.1, L.sub.2; 4) it is implemented with minimal hardware; and 5) it takes two keys K.sub.1 and K.sub.2 which increases its security. For example, as shown in FIG. 6, it is assumed that the first LFSR circuit L.sub.1 has a bit length of 3 and the second LFSR circuit L.sub.2 has a bit length of 2. Further, it is assumed that key K.sub.1 is "111" and key K.sub.2 is "11." The keys K.sub.1 and K.sub.2 are loaded into L.sub.1 and L.sub.2 respectively. Table 1 below provides the states of the LFSR circuits L.sub.1, L.sub.2 ; the outputs of the LFSR circuits L.sub.1, L.sub.2 ; and the cipher stream for several consecutive clock cycles.
TABLE 1
Clock L.sub.1 L.sub.2 Output Output Cipher
Cycle state state of L.sub.1 of L.sub.2 Stream
1 111 11 1 1 0
2 011 01 1 1 0
3 001 10 1 0 1
4 001 11 1 1 0
5 100 01 0 1 1
6 010 10 0 0 1
7 010 11 0 1 1
8 101 01 1 1 0
9 110 10 0 0 1
10 110 11 0 1 1
11 111 01 1 1 0
12 011 10 1 0 1
13 011 11 1 1 0
14 001 01 1 1 0
15 100 10 0 0 1
16 100 11 0 1 1
17 010 01 0 1 1
18 101 10 1 0 1
19 101 11 1 1 0
20 110 01 0 1 1
21 111 10 1 0 1
end of one period
22 111 11 1 1 0
23 011 01 1 1 0
24 001 10 1 0 1
25 001 11 1 1 0
From Table 1, the period of the cipher stream is 21 clocks, which is a multiplication of the individual periods of the LFSR circuits L.sub.1 (7) and L.sub.2 (3). The cipher stream may also be generated using software as shown in the flow diagram of FIG. 7. The initial states, which are the two keys K.sub.1 and K.sub.2, are loaded into registers or memory locations (S1). If the current output of the second LFSR circuit L.sub.2 is "1"(S2), the value of the first LFSR circuit L.sub.1 is updated (S3), and then the second LFSR circuit L.sub.2 is updated (S4). However, if the current output of LFSR circuit L.sub.2 is zero (S2), then the LFSR circuit L.sub.1 is not updated and only LFSR circuit L.sub.2 is updated (S4). The outputs of the LFSR circuits L.sub.1, L.sub.2 are then forwarded to an XOR gate, which outputs the cipher stream (S5). Steps (S2) through (S5) are then repeated. A spread spectrum receiver 300 made in accordance with the present invention as shown in FIG. 8 includes all of the components of the spread spectrum receiver 100 of FIG. 2, which function in the same manner, except for the decipher stream generator 310 and the keys 320. The cipher stream generator 220 or the decipher stream generator 320 can be used in a multiple stage configuration, as shown in FIG. 9, in which case the security is greatly enhanced since the linear complexity and period increase exponentially. If L.sub.1.about.L.sub.2.about.L, then the linear complexity of the multiple stage configuration with N stages is approximately .apprxeq.2L2.sup.LN and the period of the output becomes approximately .apprxeq.2.sup.2LN. The stream cipher algorithm explained above can be used in a cascade structure as in FIG. 9 to further increase its security. Each stage may have the same bit length or the stages may have different bit lengths. In cascade form, prior stages generate clocks for the following stages. As shown in FIG. 9, the output of the first LFSR circuit L.sub.1 from stage 1 and the output of the second LFSR circuit L.sub.2 from stage 2 are coupled to an AND gate to form a digital signal which is used as the clock for the first LFSR circuit L.sub.1 of stage 2. Similarly, output of the second LFSR circuit L.sub.2 from stage 1 becomes the clock for the second LFSR circuit L.sub.2 of stage 2. More stages can be added in the same manner. An LFSR is clocked when the signal in its clock input changes from 0 to 1. Although the LFSRs L.sub.1, L.sub.2 at each stage preferably have the same bit length, they may also be different. Although the invention has been described by making detailed reference to certain specific embodiments, such details are intended to be instructive rather than restrictive. It will be appreciated by those skilled in the art that many variations may be made in a structure and mode of operation without departing from the spirit and scope of this invention as disclosed in the teachings herein.
|
Same subclass Same class Consider this |
||||||||||