The F <sub> 4 </ Sub> On The ¦Ò-linear Feedback Shift Register

Linear Feedback Shift Register( LFSR ) are used as pseudorandom keystream generators in cryptographic schemes. Hardware implementation of LFSRs is simple and fast but their software implementation is not quite efficient. Therefore, in the 1994 conference on fast software encryption, a challenge was set forth by B. Preneel to design LFSR's which expoit the parrallelism offered by the word oriented operations of modern processor. In 2002, Tsaban and Vishne introduced the notation of linear transformation shift registers (TSRs) to exploit word-oriented operations for LFSRs.This paper takes into account the challenge set forth by Preneel from another angle, and introduces a new type of word-oriented shift register called σ - linear feedback shift registers (σ-LFSRs), which are built by adding in-word cycle shift operator (abbreviated as σ henceforth) to LFSR. Research shows TSRs is special case of σ - LFSR over finite field.Originated from study on cryptographic one-way Hash function, σ - LFSR is the outcome of mutual combination and mutual penetration of stream cipher and Hash function design rationale and technology. On one hand, fast software implementation of σ-LFSR based on word operation is available and problem raised by Preneel is partly solved. On the other hand, this class of shift register is also applicable to hardware implementation.Some basic properties of σ - LFSR over F4 are studied, such as nonlinearity, cycle structure distribution of state graph, the largest period and counting problem related. The conclusions are as follows:The coefficient ring of σ-LFSR is isomorphic to the matrix ring over F,. The cycle structure of σ- LFSR is consistent with that of the determinant of the corresponding polynomial matrix if and only if the feedback polynomial of - LFSR does not contain nontrivial factor over F2,. The counting formula of the number of σ - LFSR with inconsistent cycle structure is also showed in that part. The period of σ-LFSR with degree n is maximum if and only if the determinant of the corresponding polynomial matrix is the primitive polynomial with order 2n over F2,.Conclusions presented in the paper can also be generalized into finite field F2...