Key stream generator

from Wikipedia, the free encyclopedia

A key stream generator is the core component of stream encryption . It generates the keystream from the key, which is added to the message in order to encrypt it. The most common constructions are based on linear feedback shift registers (LFSR) or on block ciphers.

LFSR-based generators

For generators based on linear shift registers with feedback one or more LFSRs are used, which are mostly of different lengths and have different feedback polynomials. This is used to combine LFSRs to form non-linear generators. These generate a keystream.

Combination generators use several LFSRs whose output bits are linked via a non-linear function. Filter generators consist of a single LFSR, which combine bits from different levels of the internal state via a non-linear function. Both combination generators and filter generators were found to be unsafe. Newer generators are so-called clock-controlled generators. An internal output bit controls the behavior of the generator.

Stop-and-go generator

A stop-and-go generator consists of two LFSRs (registers R1 and R2), with the output of the first register (R1) controlling the clock of the second register (R2). If register R1 supplies the output value "1", the generator supplies the output value from register R2. If register R1 delivers the value "0", the value of the second register R2 is discarded. Then both registers (R1 and R2) each generate a new bit.

Alternating stop-and-go generator

An alternating stop-and-go generator works with a total of three registers (R1, R2 and R3). If register R1 supplies the output value "1", register R2 is clocked and register R3 repeats the previous value. If register R1 supplies the output value "0", register R3 is clocked and register R2 repeats the previous value. The generator supplies the bit-by-bit XOR operation of the two registers R2 and R3 as output.

Self-steering generator

The self-regulating generator controls its own clock. If the register supplies the output "0", it is clocked d times. If the register that supplies the output “1”, it is clocked k times.

Shrinking generator

The shrinking generator consists of two registers R1 and R2. If register R1 supplies the value "1", the output of register R2 is considered the output of the generator. If register R1 supplies the value "0", the output bit of register R2 is discarded in this cycle.

Self-shrinking generator

The self-shrinking generator consists of an LFSR (register). This register is clocked twice and the generated bit pair determines the output. If the first bit of the pair is a "1", the generator outputs the value of the second bit. If the first bit is a "0", the second bit is discarded. Then a new pair of bits is generated by the register.

Generators based on block ciphers

A block cipher can be operated in counter mode or in output feedback mode to serve as a key stream generator.

Proven safe generators

Parallel to the introduction of provable security in other areas of cryptography, there were also efforts to construct keystream generators whose security can be directly traced back to the severity of a number-theoretical problem. Examples of such generators are the Blum-Blum-Shub generator and the Blum-Micali generator . In practice, however, these designs are almost never used because they are orders of magnitude slower than the above.

literature

  • Alfred J. Menezes, Paul C. van Oorschot, and Scott A. Vanstone: Handbook of Applied Cryptography . 5th edition. CRC Press, 2001, ISBN 0-8493-8523-7 , chapter 6.