In cryptography

Cryptography

Cryptography is the practice and study of techniques for secure communication in the presence of third parties...

, an alternating step generator (ASG) is a cryptographic pseudorandom number generator

Cryptographically secure pseudorandom number generator

A cryptographically secure pseudo-random number generator is a pseudo-random number generator with properties that make it suitable for use in cryptography.Many aspects of cryptography require random numbers, for example:...

 intended to be used in a stream cipher

Stream cipher

In cryptography, a stream cipher is a symmetric key cipher where plaintext digits are combined with a pseudorandom cipher digit stream . In a stream cipher the plaintext digits are encrypted one at a time, and the transformation of successive digits varies during the encryption...

. The design was published in 1987 by C. G. Günther. It is also known as the alternating stop-and-go generator.

Overview

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

s (LFSRs) are, statistically speaking, excellent pseudorandom generators, with good distribution and simple implementation. However, they cannot be used as-is because their output can be predicted easily.

An ASG comprises three linear feedback shift registers, which we will call LFSR0, LFSR1 and LFSR2 for convenience. The output of one of the registers decides which of the other two is to be used; for instance if LFSR2 outputs a 0, LFSR0 is clocked, and if it outputs a 1, LFSR1 is clocked instead. The output is the exclusive OR of the last bit produced by LFSR0 and LFSR1. The initial state of the three LFSRs is the key.

Customarily, the LFSRs use primitive polynomial

Primitive polynomial

In field theory, a branch of mathematics, a primitive polynomial is the minimal polynomial of a primitive element of the finite extension field GF...

s of distinct but close degree, preset to non-zero state, so that each LFSR generates a maximum length sequence

Maximum length sequence

A maximum length sequence is a type of pseudorandom binary sequence.They are bit sequences generated using maximal linear feedback shift registers and are so called because they are periodic and reproduce every binary sequence that can be reproduced by the shift registers...

. Under these assumptions, the ASG's output demonstrably has long period, high linear complexity, and even distribution of short subsequences.

Example code in C

C (programming language)

C is a general-purpose computer programming language developed between 1969 and 1973 by Dennis Ritchie at the Bell Telephone Laboratories for use with the Unix operating system....

:

/* 16-bit toy ASG (much too small for practical usage); return 0 or 1. */
unsigned ASG16toy(void)
{
static unsigned /* unsigned type with at least 16 bits */
lfsr2 = 0x8102, /* initial state, 16 bits, must not be 0 */
lfsr1 = 0x4210, /* initial state, 15 bits, must not be 0 */
lfsr0 = 0x2492; /* initial state, 14 bits, must not be 0 */

/* LFSR2 use x^^16 + x^^14 + x^^13 + x^^11 + 1 */
lfsr2 = (-(lfsr2&1))&0x8016 ^ lfsr2>>1;

if (lfsr2&1)
/* LFSR1 use x^^15 + x^^14 + 1 */
lfsr1 = (-(lfsr1&1))&0x4001 ^ lfsr1>>1;
else
/* LFSR0 use x^^14 + x^^13 + x^^3 + x^^2 + 1 */
lfsr0 = (-(lfsr0&1))&0x2C01 ^ lfsr0>>1;

return (lfsr0 ^ lfsr1)&1;
}


An ASG is very simple to implement in hardware. In particular, contrary to 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....

 and self-shrinking generator

Self-shrinking generator

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 are studied for use in cryptography.-Algorithm:...

, an output bit is produced at each clock, ensuring consistent performance and resistance to timing attack

Timing attack

In cryptography, a timing attack is a side channel attack in which the attacker attempts to compromise a cryptosystem by analyzing the time taken to execute cryptographic algorithms...

s.

Security

In Reduced Complexity Attacks on the Alternating Step Generator, Shahram Khazaei, Simon Fischer, and Willi Meier give a cryptanalysis

Cryptanalysis

Cryptanalysis is the study of methods for obtaining the meaning of encrypted information, without access to the secret information that is normally required to do so. Typically, this involves knowing how the system works and finding a secret key...

of the ASG allowing various tradeofs between time complexity and the amount of output needed to mount the attack, e.g. with asymptotic complexity and bits, where is the size of the shortest of the three LFSRs.