Self-shrinking generator


Self-shrinking generator

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).

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 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: 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 outputa single bit.

See the LFSR article for details on how these rows are generated.

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.

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.

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.

Further reading

* [http://www.cacr.math.uwaterloo.ca/hac/ Handbook of Applied Cryptography]


Wikimedia Foundation. 2010.

Look at other dictionaries:

  • 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.The shrinking generator uses two… …   Wikipedia

  • Alternating step generator — In cryptography, an alternating step generator (ASG) is a cryptographic pseudorandom number generator intended to be used in a stream cipher. The design was published in 1987 by C. G. Günther. It is also known as the alternating stop and go… …   Wikipedia

  • Schlüsselstromgenerator — Ein Schlüsselstromgenerator ist der Kernbestandteil einer Stromverschlüsselung. Er erzeugt aus dem Schlüssel den Schlüsselstrom, der auf die Nachricht addiert wird, um sie zu verschlüsseln. Die gängigsten Konstruktionen basieren auf linear… …   Deutsch Wikipedia

  • генератор с обратной связью — Генератор с обратной связью, в котором выходной поток LFSR (см. Linear Feedback Shift Register (Регистр линейного сдвига с обратной связью) можно подать на вход. [http://www.morepc.ru/dict/] генератор с обратной связью [Лугинский Я. Н. и др.… …   Справочник технического переводчика

  • самосверточный генератор — Генератор с обратной связью, в котором выходной поток LFSR (регистра линейного сдвига с обратной связью) можно подать на вход. [http://www.rfcmd.ru/glossword/1.8/index.php?a=index&d=4286] Тематики защита информации EN self shrinking generator …   Справочник технического переводчика

  • Stream cipher — The operation of the keystream generator in A5/1, a LFSR based stream cipher used to encrypt mobile phone conversations. In cryptography, a stream cipher is a symmetric key cipher where plaintext digits are combined with a pseudorandom cipher… …   Wikipedia

  • List of electronics topics — Alphabetization has been neglected in some parts of this article (the b section in particular). You can help by editing it. This is a list of communications, computers, electronic circuits, fiberoptics, microelectronics, medical electronics,… …   Wikipedia

  • japan — japanner, n. /jeuh pan /, n., adj., v., japanned, japanning. n. 1. any of various hard, durable, black varnishes, originally from Japan, for coating wood, metal, or other surfaces. 2. work varnished and figured in the Japanese manner. 3. Japans,… …   Universalium

  • Japan — /jeuh pan /, n. 1. a constitutional monarchy on a chain of islands off the E coast of Asia: main islands, Hokkaido, Honshu, Kyushu, and Shikoku. 125,716,637; 141,529 sq. mi. (366,560 sq. km). Cap.: Tokyo. Japanese, Nihon, Nippon. 2. Sea of, the… …   Universalium

  • Economic Affairs — ▪ 2006 Introduction In 2005 rising U.S. deficits, tight monetary policies, and higher oil prices triggered by hurricane damage in the Gulf of Mexico were moderating influences on the world economy and on U.S. stock markets, but some other… …   Universalium


Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”

We are using cookies for the best presentation of our site. Continuing to use this site, you agree with this.