To install click the Add extension button. That's it.

The source code for the WIKI 2 extension is being checked by specialists of the Mozilla Foundation, Google, and Apple. You could also do it yourself at any point in time.

4,5
Kelly Slayton
Congratulations on this excellent venture… what a great idea!
Alexander Grigorievskiy
I use WIKI 2 every day and almost forgot how the original Wikipedia looks like.
Live Statistics
English Articles
Improved in 24 Hours
Added in 24 Hours
Languages
Recent
Show all languages
What we do. Every page goes through several hundred of perfecting techniques; in live mode. Quite the same Wikipedia. Just better.
.
Leo
Newton
Brights
Milds

Alternating step generator

From Wikipedia, the free encyclopedia

In cryptography, an alternating step generator (ASG) is a cryptographic pseudorandom number generator used in stream ciphers, based on three linear-feedback shift registers. 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.[1][2]

YouTube Encyclopedic

  • 1/3
    Views:
    326 207
    190 028
    1 340 489
  • Alternating Current vs Direct Current - Rms Voltage, Peak Current & Average Power of AC Circuits
  • Transformers - working & applications (step up and step down) | A.C. | Physics | Khan Academy
  • Electric generator (A.C. & D.C.) | Magnetic effects of current | Khan Academy

Transcription

Overview

Linear-feedback shift registers (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 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)
{
  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 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[3] give a cryptanalysis 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

  1. ^ Günther, C. G. (1988). "Alternating Step Generators Controlled by de Bruijn Sequences". Advances in Cryptology — EUROCRYPT '87. Lecture Notes in Computer Science. Vol. 304. Berlin, Heidelberg: Springer. pp. 5–14. doi:10.1007/3-540-39118-5_2. ISBN 978-3-540-39118-0.
  2. ^ Gunther, Christoph-Georg (1989-03-28). "US4817145A - Generator for generating binary ciphering sequences". Google Patents.
  3. ^ Khazaei, Shahram; Fischer, Simon; Meier, Willi (2007). "Reduced Complexity Attacks on the Alternating Step Generator". Selected Areas in Cryptography. Lecture Notes in Computer Science. Vol. 4876. Berlin, Heidelberg: Springer. pp. 1–16. doi:10.1007/978-3-540-77360-3_1. ISBN 978-3-540-77360-3.
  • Schneier, Bruce. Applied Cryptography (p383-384), Second Edition, John Wiley & Sons, 1996. ISBN 0-471-11709-9
This page was last edited on 29 October 2023, at 21:37
Basis of this page is in Wikipedia. Text is available under the CC BY-SA 3.0 Unported License. Non-text media are available under their specified licenses. Wikipedia® is a registered trademark of the Wikimedia Foundation, Inc. WIKI 2 is an independent company and has no affiliation with Wikimedia Foundation.