This page uses content from Wikipedia and is licensed under CC BY-SA.

A **self-shrinking generator** is a pseudorandom generator that is based on the shrinking generator concept. Variants of the self-shrinking generator based on a linear feedback shift register (LFSR) are studied for use in cryptography.

In difference to the shrinking generator, which uses a 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 the LFSR twice to obtain a pair of bits as LFSR output.
- If the pair is 10 output a zero.
- If the pair is 11 output a one.
- Otherwise, output nothing.
- Return to step one.

This example will use the connection polynomial *x ^{8} + x^{4} + x^{3} + x^{2} + 1*,
and an initial register fill of

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.

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.

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 2^{L/2}, and a linear complexity of at least 2^{L/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 2^{0.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 2^{57} steps, using an output sequence of only 4.9 x 10^{8} bits.

Another attack ^{[3]}

**^**"The self-shrinking generator", Advances in Cryptology-Eurocrypt 1994 (LNCS 950), 205-214, 1995.**^**"An security examination of the self-shrinking generator", Circencester, UK, December 1995.**^**Zenner, Erik; Krause, Matthias; Lucks, Stefan. "Improved Cryptanalysis of the Self-Shrinking Generator" (PDF).*Information Security and Privacy 13th Australasian Conference ACISP 2008*: 30. Retrieved 12 April 2016.