Talk:Alternating step generator

Cryptography: Computer science Low‑importance

	This article is within the scope of WikiProject Cryptography, a collaborative effort to improve the coverage of Cryptography on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks.CryptographyWikipedia:WikiProject CryptographyTemplate:WikiProject CryptographyCryptography articles
Low	This article has been rated as Low-importance on the importance scale.
	This article is supported by WikiProject Computer science (assessed as Low-importance).

link to Google's "I'm lucky"?

May be freely available as [1].

Now this is redirecting to ftp://zedz.net/pub/mirrors/Advances in Cryptology/HTML/PDF/E87/5.PDF, but this might change in future. Is there a reason not directly to link to the latter location? -- Paul Ebermann (talk) 17:45, 7 August 2011 (UTC)[reply]

Security section is out of date

The security section looks seriously out of date. There are several results that seem to have a complexity significantly lower than $O(2^{n})$ where n is the size of the LFSRs. E.g. one paper describing such attacks is "Reduced Complexity Attacks on the Alternating Step Generator" by Shahram Khazaei , Simon Fischer and Willi Meier [2] 62.202.80.49 (talk) 06:31, 8 August 2011 (UTC)[reply]

The slides for the above paper [3] give a simple account of one of their claimed results: Time complexity $O(n^{2}2^{2n/3})$ for $O(2^{2n/3})$ known keystream bits. Thanks to external help [4], I get more about the paper. I toured other sources, and it is the best attack I could locate. I have updated the main article.Fgrieu (talk) 21:48, 21 August 2011 (UTC)[reply]

LFSR0 not maximum length sequence?

I don't feel qualified to edit the page, but LFSR0 in the example uses taps that are not relatively prime (14 and 2), so that seems to violate one of the requirements for having a maximum length sequence. Is there any chance someone could address this (either by fixing it or by explaining why it's not actually a problem)? — Preceding unsigned comment added by Craigc40 (talk • contribs) 16:14, 22 January 2013 (UTC)[reply]

There is no need for the tap positions of a LFSR to be pairwise coprime. But if every tap position is divisible by an integer k>1 then the polynomial cannot be primitive and the corresponding LFSR would not give good output. E.g. it can be observed that changing a bit in the initial state could only affect every k-th output bit. 83.77.101.219 (talk) 19:58, 22 January 2013 (UTC)[reply]

Example code is confusing (and wrong?)

I'm not an expert - I came here to learn more about ASG's. The descriptive text is clear enough, but the example code is confusing, for the following reasons:

The relationship between the polynomials and their hex representation is not at all clear -- so much so that there may be none,
two of the three individual LFSR's run in isolation repeat significantly earlier than they should (suggesting the polynomials might be off),
the LFSR implementation itself is very confusing - what is the intent of the code: (-(lfsr2&1))&0x8016 ^ lfsr2>>1; ? Using two's complement negation on unsigned is clever, but has behavior that won't be obvious to non-experts (apparently zeroes it out or not, depending on the LSB of the state).

When I run the LFSR's in isolation, I see that lfsr_0 repeats after 0x3fff iterations, and lfsr_1 repeats after 0x7fff iterations, but lfsr_2 waits until 0xffff to repeat.

I wish I could say that the LFSR code in the Linear_feedback_shift_register article is better, but the relationship between the polynomial and the code (while correct) is also non-obvious (shifting out the taps one at a time). To me, representing the taps as set bits in a binary string would make the most sense, which is what I thought this article was doing, but no mater how I look at the constants, I don't see how they correspond to the claimed polynomials:

/* LFSR2 use  x^^16   x^^14   x^^13   x^^11   1 */
... 0x8016

0x8016 is a 16-bit number, but this polynomial would require 17 bits to represent. Maybe the code hard-wires in a 1 in either the 1st or 17th bit position, but then it would be wrong for the other polynomials, wouldn't it?

If I do the manual translation of this polynomial to binary, I'd either get 0x16801 or 0x1002d. If I do an intel-style endian reverse, I get 0x801680 (padded out to 24 bits).

Clarification welcome. I'd be happy to contribute code that IMO would be more clear to the layperson, or I'd welcome such code from another author. — Preceding unsigned comment added by Dylanmcnamee (talk • contribs) 18:30, 1 September 2015 (UTC)[reply]