Self-shrinking generator
Encyclopedia
A self-shrinking generator is a pseudorandom generator
, which is based on the shrinking generator
concept. Various variants of the self-shrinking generator based on a linear feedback shift register
(LFSR) are studied for use in cryptography
.
, which uses as second feedback shift register to control the output of the first, the self-shrinking generator uses alternating output bits of a single register to control its final output. The procedure for clocking this kind of generator is as follows:
and an initial register fill of 1 0 1 1 0 1 1 0.
Below table lists, for each iteration of the LFSR
, its intermediate output before self-shrinking, as well as the final generator output. The tap positions defined by the connection polynomial are marked with blue headings. The state of the zeroth iteration represents the initial input.
At the end of four iterations, the following sequence of intermediate bits is produced: 0110.
The first pair of bits, 01, is discarded since it does not match either 10 or 11.
The second pair of bits, 10, matches the second step of the algorithm so a zero is output.
More bits are created by continuing to clock the LFSR and shrinking its output as described above.
Furthermore, they show that any self-shrinking generator can be represented as a shrinking-generator. The inverse is also true:
Any shrinking generator can be implemented as a self-shrinking generator, although the resultant generator may not be of maximal length.
An attack presented by the authors requires about 20.7L steps, assuming a known connection polynomial.
A more advanced attack [2], discovered by Mihaljević, is able to break a register a hundred bits in length in around 257 steps, using an output sequence of only 4.9 x 108 bits.
Pseudorandom number generator
A pseudorandom number generator , also known as a deterministic random bit generator , is an algorithm for generating a sequence of numbers that approximates the properties of random numbers...
, which is based on the shrinking generator
Shrinking generator
In cryptography, the shrinking generator is a form of pseudorandom number generator intended to be used in a stream cipher. It was published in Crypto 1993 by Don Coppersmith, Hugo Krawczyk, and Yishay Mansour....
concept. Various variants of the self-shrinking generator based on a linear feedback shift register
Linear feedback shift register
A linear feedback shift register is a shift register whose input bit is a linear function of its previous state.The most commonly used linear function of single bits is XOR...
(LFSR) are studied for use in cryptography
Cryptography
Cryptography is the practice and study of techniques for secure communication in the presence of third parties...
.
Algorithm
In difference to the shrinking generatorShrinking generator
In cryptography, the shrinking generator is a form of pseudorandom number generator intended to be used in a stream cipher. It was published in Crypto 1993 by Don Coppersmith, Hugo Krawczyk, and Yishay Mansour....
, which uses as second feedback shift register to control the output of the first, the self-shrinking generator uses alternating output bits of a single register to control its final output. The procedure for clocking this kind of generator is as follows:
- Clock two bits from the LFSR.
- If the pair is 10 output a zero.
- If the pair is 11 output a one.
- Otherwise, output nothing.
- Return to step one.
Example
This example will use the connection polynomial x8 + x4 + x3 + x2 + 1,and an initial register fill of 1 0 1 1 0 1 1 0.
Below table lists, for each iteration of the LFSR
Linear feedback shift register
A linear feedback shift register is a shift register whose input bit is a linear function of its previous state.The most commonly used linear function of single bits is XOR...
, its intermediate output before self-shrinking, as well as the final generator output. The tap positions defined by the connection polynomial are marked with blue headings. The state of the zeroth iteration represents the initial input.
| Iteration # | 8 | 7 | 6 | 5 | 4 | 3 | 2 | 1 | Intermediate output | Generator output |
|---|---|---|---|---|---|---|---|---|---|---|
| 0 | 1 | 0 | 1 | 1 | 0 | 1 | 1 | 0 | N/A | N/A |
| 1 | 1 | 1 | 0 | 1 | 1 | 0 | 1 | 1 | 0 | N/A |
| 2 | 1 | 1 | 1 | 0 | 1 | 1 | 0 | 1 | 1 | |
| 3 | 1 | 1 | 1 | 1 | 0 | 1 | 1 | 0 | 1 | 0 |
| 4 | 1 | 1 | 1 | 1 | 1 | 0 | 1 | 1 | 0 |
At the end of four iterations, the following sequence of intermediate bits is produced: 0110.
The first pair of bits, 01, is discarded since it does not match either 10 or 11.
The second pair of bits, 10, matches the second step of the algorithm so a zero is output.
More bits are created by continuing to clock the LFSR and shrinking its output as described above.
Cryptanalysis
In their paper [1], Meier and Steffelbach prove that a LFSR based self-shrinking generator with a connection polynomial of length L results in an output sequence period of at least 2L/2, and a linear complexity of at least 2L/2-1.Furthermore, they show that any self-shrinking generator can be represented as a shrinking-generator. The inverse is also true:
Any shrinking generator can be implemented as a self-shrinking generator, although the resultant generator may not be of maximal length.
An attack presented by the authors requires about 20.7L steps, assuming a known connection polynomial.
A more advanced attack [2], discovered by Mihaljević, is able to break a register a hundred bits in length in around 257 steps, using an output sequence of only 4.9 x 108 bits.