]> AND Private Git Repository - prnggpu1.git/blob - PRNG/Cellular_Automata.tex.bak
Logo AND Algorithmique Numérique Distribuée

Private GIT Repository
initialisation
[prnggpu1.git] / PRNG / Cellular_Automata.tex.bak
1 \textit{Cellular Automata} or CA are proposed as a third class for exhibit chaotic or pseudo-random behavior presented by Wolfram "A New Kind of Science". It's can be represented as an array of cells that can hold and update their internal state dependent on local rules and the state of their neighborhood. The basic CA can combine 3 cells, each of them has two possibilities ${0,1}$. It's resuming a state machine with a total of 8 ($2^{3}$ binary configuration possibilities for each CA and resulting a 256 ($2^{8}$) possible rules generally referred to by their Wolfram code. If the rule of a CA involves only XOR logic it's called a linear rule. It will be referred to as complement rules when using XNOR logic. Otherwise, a linear CA represent all cells that has linear rules and an additive CA if they combine the linear and complement rules. Another type is the uniform CA, which has the same rule for all cells else it's a hybrid CA. Finally, a null boundary CA is when both the left and right neighborhood of the leftmost and rightmost terminal cell is connected to logic 0-state. 
2
3 In 2003 \cite{tkacik2003hardware}, the author implemented a custom IC of HCA that combines the outputs of a hybrid 90/150 rules of a 37-bit CA with a 43-bit of LFSR to produce a maximum length PRNG. However and to pass pass all the statistic tests, the LFSR and HCA must be clocked at different frequencies to create a random output sequence. To resolve Clocking issue, a new solution presented in \cite{cerda2012efficient}. Here, the authors propose to XOR the last bit of HCA with the last bit of LFSR to generate 1-bit per clock cycle. Following that, they found the best combination for a high quality of PRNG is 16-bit CA with a 37-bit LFSR. In \cite{comer2012random}, they compare the previews work LFSR/HCA \cite{cerda2012efficient} with a new implementation of CA called \emph{Self-Programmable} CA (SPCA) and presented in \cite{guan2003pseudorandom}. It uses the super-rule 90/156 to determine when to make a dynamic rule change in each CA cell. Here, the the inputs rules of his neighboring cells is it self a second CA working in parallel with the main CA. However, even it gives a better throughput than the LFSR/HCA combination \cite{comer2012random}, it fails in the statistical test. Another CA combination solution is cited in \cite{raut2013stream}. Here, the authors propose another combination circuit of CA and Non-LFSR block based on A2U2 design. The main objective is to resist more of the various forms of cryptanalysis, such as correlation attacks and algebraic attacks. As for the outputs generated, they will pass to a mixer mechanism to increase the complexity for decryption. 
4
5 In \cite{anghelescu2007vlsi}, the authors propose two Hybrid CA for an encryption system application. The first HCA-1 implemention work as a PRNG and use two rules 90/150 to generate a real-time key stream. The second HCA-2 is implemented as a block cipher and use a combination of 51/153/195 rules. However, to select witch rules will be used by the block cipher HCA-2, the PRNG or HCA-1 generate an encryption rules to switch the rules and provide each cell of HCA-2 is own rules. 
6
7 A new implementation CA is presented in \cite{dogaru2010algebraic}, where the authors create an automatic software tool to generator CA. It's based on the \emph{algebraic normal form} (ANF) representation to generate a RTL code of any hybrid CA depending on ID rules provided as inputs. Using ANF representation and with ID=101 for 3 neighbor, the outputs  generated will be identical to Matlab results following this formula $(y = \ [K_{0} \ \bigotimes \ K_{1}(U_{1}) \ \bigotimes \ K_{2}(U_{2}) \ \bigotimes \ K_{3}(U_{3}) \ \bigotimes \ K_{4}(U_{1}*U_{2}) \ \bigotimes \ ... \ K_{7}(U_{1}*U_{2}*U_{3})] \ ... * mask)$. Then in recent papers \cite{ioana2014fpga}, they claim by using a chain of HCA instead of single HCA will increase the ratio of frequency/ares and cryptography.
8
9 Another and different concept of CA is proposed in \cite{kotoulas20061}. It uses a new way to implement the rules for 1-d CA using the real time computer clock sequence. Here, the initial state configuration and his length is the product of day, month, year, hour, min and seconds. However, over a period of $t = x(60-x)$, it uses two functional rules. The first rule is the product of minutes by seconds $m*s$, and the second rule is the number of minutes divided by the number of seconds multiplied by a constant$\frac{m}{s} *c$.