Computer Security and Cryptography

8.11 NONLINEAR KEY STREAM GENERATION

We illustrate two ways for nonlinear key stream generation, using a read-only memory ROM to implement a nonlinear mapping. A k-bit ROM is a table with k-bit input x = (x₀, x₁, …, x_k−1) and output y = (y₀, y₁, …, y_k−1)

Figure 8.11 uses the outputs of k-LFSRs as the input of a k-bit ROM from which either a single or k-bit output can be read:

Figure 8.11 XORing to a ROM.

• A min-term for n Boolean variable s₀, s₁, …, s_n−1 is a product in which either s_i or its complement occurs;
• An mth order product a product of m distinct Boolean variables;
• The algebraic normal form for a Boolean function f(s₀, s₁, …, s_n−1) is the (modulo 2) sum of different mth products; and
• The nonlinear order of f is the maximum order of the terms appearing in its algebraic normal form.

Example 8.8

1. is a min-term in the Boolean variables s₀, s₁, …, s_n−1,
2. The Boolean function f(s₀, s₁, …, s_n−1) = s₁ + s₂ + s_n−1 and has nonlinear order 1,
3. The Boolean function f(s₀, s₁, …, s_n−1) = s₁ + s₁s₂ + s₀s₁s₃ has nonlinear order 3.

        Proposition 8.10: [Menezes et al., 1996, p. 205] If the lengths N₀, N₁, …, N_k−1 of the k LFSRs are pairwise distinct and >2, the nonlinear order of the ...