Fast construction of binary ring FCSRs for hardware stream ciphers (Q1741931)

\textit{A. Klapper} and \textit{M. Goresky} introduced in [Lect. Notes Comput. Sci. 809, 174--178 (1994; Zbl 0943.94515)] feedback with carry shift registers (FCSRs) as an alternative to linear feedback shift registers because the latter are sensible to algebraic attacks. However, FCSRs are also weak against algebraic attacks when the Galois representation is used. In order to solve thios problem \textit{F. Arnault} et al. have introduced a ring FCSRs [Lect. Notes Comput. Sci. 5867, 433--448 (2009; Zbl 1267.94032)]. A ring FCSRs has a main shift register on \(n\) binary cells \(m=(m_0,\dots,m_{n-1})\) and a carry register with \(n\) integer cells \(c=(c_0,\dots,c_{n-1})\). They are updated as follows: \(m(t+1)= A m(t)+c(t)\pmod 2\) \(c(t+1)= A m(t)+c(t)(\operatorname{div} 2)\) where the \(A\), the transition matrix, is an \(n\times n\) matrix with entries either \(0\) or \(1\) of the form \[ \begin{pmatrix} \ast & 1 & & & \\ &\ast & 1 & &(\ast) \\ &&\ast & 1 & \\ &(\ast)&&\ast & 1 \\ 1&&&&\ast \\ \end{pmatrix} \] i.e., \(a_{k,k+1}=1\) and \(a_{n,1}=1\). The authors provide a fast algorithm to construct binary ring FCSRs. In particular their algorithm construct a binary transition matrix , \(A\), satisfying the following conditions: {\parindent=0.7cm\begin{itemize}\item[(C1)] Let \(q=\det(I-2A)\) then \(| q|\) is a prime number with 2 as a primitive root. \item[(C2)] \((| q|-1)/2\) is a prime number. \item[(C3)] The super diagonal of the transition matrix is full of ones. \item[(C4)] The number of nonzero entries for a given row or a given column must be at most 2. \end{itemize}} For it they explicitly compute \(\det(I-2A)\) which help to ensure conditions (C1) and (C2) and design and strategy to construct \(A\) which also verify (C3) and (C4).