Self-shrinking generator
From Wikipedia, the free encyclopedia
 |
The factual accuracy of part of this article is disputed. The dispute is about (minor): tap polynomial convention.
Please see the relevant discussion on the talk page before making changes.(March 2008) |
A self-shrinking generator is a pseudorandom number generator and a variant of the shrinking generator concept. It is a generator used in cryptography and has reasonable security properties when used in conjunction with a Linear feedback shift register (LFSR).
Contents |
[edit] Algorithm
Instead of using two distinct LFSR with one register driving the second register outputs, the self-shrinking generator operates with a single register. The procedure for clocking this kind of generator is as follows:
- Clock two bits from the LSFR.
- If the pair is 10 output a zero.
- If the pair is 11 output a one.
- Otherwise, output nothing.
- Return to step one.
[edit] Example
This example will use the connection polynomial: x^8 + x^4 + x^3 + x^2 + 0
The key will be: 1 0 1 1 0 1 1 0.
Below is the output of the LFSR before it is self-shrunk. The tap positions are marked with the blue headings. The key is loaded in to the zeroth iteration, so it has no output bit. The subsequent iteration numbers each output a single bit.
See the LFSR article for details on how these rows are generated.
| Iteration # | 8 | 7 | 6 | 5 | 4 | 3 | 2 | 1 | Output |
|---|---|---|---|---|---|---|---|---|---|
| 0 | 1 | 0 | 1 | 1 | 0 | 1 | 1 | 0 | N/A |
| 1 | 1 | 1 | 0 | 1 | 1 | 0 | 1 | 1 | 0 |
| 2 | 1 | 1 | 1 | 0 | 1 | 1 | 0 | 1 | 1 |
| 3 | 1 | 1 | 1 | 1 | 0 | 1 | 1 | 0 | 1 |
| 4 | 1 | 1 | 1 | 1 | 1 | 0 | 1 | 1 | 0 |
At the end of four iterations the following sequence of bits is produced: 0110.
The first pair of bits, 01, is discarded since it doesn't match either 10 or 11. The second pair of bits, 10, matches the second step of the algorithm so we output a zero.
To generate more bits, we simply continue to clock the LFSR and shrinking it as we have done above.
[edit] Cryptanalysis
Meier and Staffelbach [1] showed 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.
They went on to show that if the period is at least 2L/2 and also that the linear complexity of the construction is 2L/2-1. They presented an attack on the construction that requires 20.7L steps.
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.
[edit] References
- [1] "The self-shrinking generator", Advances in Cryptology-Eurocrypt 1994 (LNCS 950), 205-214, 1995.
- [2] "An security examination of the self-shrinking generator", Circencester, UK, December 1995.
