Quote from: gaom094 on Today at 03:44:30 PM

You are right, but there is a problem, it should be S_i-1 XOR (S_i-1 >> 1) = S_i XOR w₁.

If the proof is stuck, you can put it away first.

for example.
w0=10010110, w1=01110101
s0=10100010
s0 >> 1 = 01000101
give m=0
s1=w0 xor (s0 xor (s0 >> 1)) = 10010110 xor (10100010 xor 01000101) = 10010110 xor 11100111 = 01110001.
suppose we know s1=01110001, we don't know whether m=0 or m=1, now we guess w=1, we have s0 xor (s0 >> 1) = s1 xor w1 = 00000100.
by the definition of cycle shift, no s0 can be found.

Thanks, now this is starting to make sense.

A question though: presumably, since both w0 and w1 are known, we have both s1 xor w1 and s1 xor w0 already known. Meaning s0 xor (s0 >> 1) is left to be determined.

A cyclic shift of A by n bits, can be represented as (A_i - 1) % n, according to Wikipedia. The paper says that a unique s0 can't be found if n is odd. Presumably it's because even n make the same modulus for the circular shift above and so an s0 can be found for it (example: w0 = 1100 and w1 = 1111, s1 = 0000, would give us 1100 and 1111 respectively for the xor. s0 could be set to 1000 which satisfies the equation) . But wouldn't w0 and w1 with odd, non-prime different number of bits also have some s0 that can be found for it, or am I going off on something completely unrelated?