# An (N)LFSR…but for bytes!

A linear feedback shift register can be thought of as an array of bits where NEW_BIT is calculated using F(REGISTERS). F is a function that takes values from two or more elements of REGISTERS and XORs them together. The new value of REGISTERS is equal to (in Python) [F(REGISTERS)] + REGISTERS[1:]. Do the dynamics change if we store values greater than 1 in each register, like say bytes? If F invoked operations other than XOR, then it seems like that would make it more like an NLFSR. Are the dynamics different there, too? Is something like this used by any cipher out there?

A classic linear feedback shift register is in fact a representation of operations in a modular ring of binary polynomials. In mathematical terms, you have a base field, which is $\mathbb{Z}_2$, the field with two elements (0 and 1); then a register of $n$ bits is a polynomial of degree at most $n-1$ in $\mathbb{Z}_2[X]$, and shifting the register is equivalent to multiplying the polynomial by $X$ modulo a given polynomial $P$ of degree $n$; that polynomial $P$ corresponds to the "feedback bits", i.e. which elements of the register you take to compute the new bit.
This model naturally extends to the case of using another base field or ring. For instance, if you use bytes and additions, then you are working with $\mathbb{Z}_{256}$, i.e. the integers modulo 256. With $n$ bytes, you still have polynomials of degree at most $n-1$, but this time in $\mathbb{Z}_{256}[X]$ (and it is still linear). Like the classic LFSR, taken alone as, say, a pseudo-random generator, it is still quite weak; moreover, $\mathbb{Z}_{256}$ is not a field, which tends to make matters worst (to express it "with the hands", additions modulo 256 will propagate carries only toward higher bits, so, in particular, the low bits of each byte will only depend on each other, not on the higher bits).
• "Linear" is relative to a base field (or ring). Bitwise XOR is linear when the base field is $\mathbb{Z}_2$. Addition is linear when considering the base ring $\mathbb{Z}_r$ for some integer $r$ (here 256). Linearity is a relatively large concept. – Thomas Pornin Sep 20 '17 at 11:32