Security and Efficiency of Linear Feedback Shift Registers in GF(2n) Using n-Bit Grouped Operations - Javier Espinosa García; Guillermo Cotrina; Alberto Peinado; Andrés Ortiz (Mathematics, 2022)
Many stream ciphers employ linear feedback shift registers (LFSRs) to generate pseudorandom sequences. Many recent LFSRs are defined in <semantics>GF(2n)</semantics> to take advantage of the n-bit processors, instead of using the classic binary field. In this way, the bit generation rate increases at the expense of a higher complexity in computations. For this reason, only certain primitive polynomials in <semantics>GF(2n)</semantics> are used as feedback polynomials in real ciphers. In this article, we present an efficient implementation of the LFSRs defined in <semantics>GF(2n)</semantics>. The efficiency is achieved by using equivalent binary LFSRs in combination with binary n-bit grouped operations, n being the processor word’s length. This improvement affects the general considerations about the security of cryptographic systems that uses LFSR. The model also allows the development of a faster method to test the primitiveness of polynomials in <semantics>GF(2n)</semantics>.