In
cryptography
Cryptography, or cryptology (from "hidden, secret"; and ''graphein'', "to write", or ''-logy, -logia'', "study", respectively), is the practice and study of techniques for secure communication in the presence of Adversary (cryptography), ...
, an alternating step generator (ASG) is a
cryptographic pseudorandom number generator used in
stream ciphers, based on three
linear-feedback shift register
In computing, a linear-feedback shift register (LFSR) is a shift register whose input bit is a Linear#Boolean functions, linear function of its previous state.
The most commonly used linear function of single bits is exclusive-or (XOR). Thus, ...
s. Its output is a combination of two LFSRs which are stepped (clocked) in an alternating fashion, depending on the output of a third LFSR.
The design was published in 1987 and patented in 1989 by C. G. Günther.
Overview
Linear-feedback shift register
In computing, a linear-feedback shift register (LFSR) is a shift register whose input bit is a Linear#Boolean functions, linear function of its previous state.
The most commonly used linear function of single bits is exclusive-or (XOR). Thus, ...
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 register
In computing, a linear-feedback shift register (LFSR) is a shift register whose input bit is a Linear#Boolean functions, linear function of its previous state.
The most commonly used linear function of single bits is exclusive-or (XOR). Thus, ...
s, 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
Exclusive or, exclusive disjunction, exclusive alternation, logical non-equivalence, or logical inequality is a logical operator whose negation is the logical biconditional. With two inputs, XOR is true if and only if the inputs differ (on ...
of the last bit produced by LFSR0 and LFSR1. The initial state of the three LFSRs is the key.
Customarily, the LFSRs use
primitive polynomials of distinct but close degree, preset to non-zero state, so that each LFSR generates a
maximum length sequence. Under these assumptions, the ASG's output demonstrably has long period, high linear complexity, and even distribution of short subsequences.
Example code in
C:
/* 16-bit toy ASG (much too small for practical usage); return 0 or 1. */
unsigned ASG16toy(void)
An ASG is very simple to implement in hardware. In particular, contrary to the
shrinking generator and
self-shrinking generator, an output bit is produced at each clock, ensuring consistent performance and resistance to
timing attacks.
Security
Shahram Khazaei, Simon Fischer, and Willi Meier
give a
cryptanalysis
Cryptanalysis (from the Greek ''kryptós'', "hidden", and ''analýein'', "to analyze") refers to the process of analyzing information systems in order to understand hidden aspects of the systems. Cryptanalysis is used to breach cryptographic se ...
of the ASG allowing various tradeoffs 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.
References
* Schneier, Bruce. ''Applied Cryptography'' (p383-384), Second Edition, John Wiley & Sons, 1996.
{{cryptography navbox , stream
Stream ciphers
de:Schlüsselstromgenerator