# True Random Number Generator Based on Fibonacci-Galois Ring Oscillators for FPGA
## 4 Implementation Results
### FiGaRO RNG Entropy Measurement  
To assess the quality of the output sequence generated by the Entropy Source, it was necessary to evaluate the min-entropy per bit of the generated sequence using specific tests. These tests are proposed and described in [29], while a test suite, based on these specifications, was provided by NIST itself and is openly available in [30]. Two things were investigated during these tests:  
* The first one regards how the output quality depended on the number of elements XORed together inside each FiGaRO stage. Ideally, the more elements were used, the more the output quality was high but this depended on an assumption of device independence, which had to be verified. * The second one regards how the output quality depended on the sampling frequency. Until this point sampling took place at 1 MHz but deriving a plot of entropy as a function of frequency may have allowed us to make a trade-off between entropy source throughput and output quality. Before testing, data collection had to be carried out in a specific way. In particular, for every test was provided a sequence of at least 1 million consecutive samples, called 5:  
\[S=[s_{0}\,s_{1}\,...\,\,{}_{5999999}] \tag{18}\]  
and a 1000 \(\times\) 1000 restart matrix, called from now on \(R\), constructed restarting the entropy source 1000 times and populating every row with 1000 consecutive samples:  
\[R= \begin{bmatrix}S_{0}^{0}&S_{1}^{0}&S_{2}^{0}&...&S_{999}^{0}\\ S_{0}^{1}&S_{1}^{1}&S_{2}^{1}&...&S_{999}^{1}\\ \vdots&\vdots&\vdots&\vdots&\vdots\\ S_{0}^{999}&S_{1}^{999}&S_{2}^{999}&...&S_{999}^{99}\\ \end{bmatrix}  \tag{19}\]  
From \(R\), two sequences were constructed: the row dataset, made up by the concatenation of all the rows of \(R\):  
\[R_{row}=[s_{0}^{0}\,...\,\,s_{999}^{0}\,s_{0}^{1}\,...\,\,s_{999}^{1}\,...\, \,s_{0}^{999}\,...\,\,s_{999}^{99}] \tag{20}\]  
Figure 16: Overall architecture of the implemented FiGaRO Random Number Generator (RNG). The columns dataset, composed by the concatenation of all the rows of \(R^{T}\):  
\[R_{col}=[s_{0}^{0}...\ S_{999}^{0}\ s_{0}^{0}...\ S_{1}^{999}\...\ S_{999}^{0}\...\ S_{999}^{99}] \tag{21}\]  
Once the dataset was constructed, it could be provided to the NIST statistical test suite described in [29], to check the Independent and Identically Distributed (IID) assumption: if the IID assumption was verified, the entropy assessment was greatly simplified, since only one test (the most common value entropy estimate) needed to run. Seven sampling frequencies were chosen for the frequency sweep:  
\[f=[1,2.5,5,10,25,50,100]MHz \tag{22}\]  
Then all three configurations of a FiGaRO Stage, which provided the sequence under test, were tested:  
* 1 FiRO and 1 GaRO XORed together
* 2 FiRO and 2 GaRO XORed together
* 4 FiRO and 4 GaRO XORed together  
This resulted in the acquisition of 21 different cases for each test run. For each case, it was necessary to acquire 1,048,576 sequential samples and of a 1000 \(\times\) 1000 restart matrix. An IID claim was made for all the sequential sequences and NIST tests (permutation and chi-square tests) confirmed this claim. The entropy awarded at the end of testing was:  
\[H_{min}=min(H_{I},H_{R},H_{C}) \tag{23}\]  
where \(H_{I}\) is the initial entropy estimate of the sequential dataset and \(H_{R}\) and \(H_{C}\) are awarded to the restart dataset. Figure 17 shows \(H_{min}\) values obtained in two runs of tests. All configurations showed high quality quite independently from the sampling frequency, with all entropies settling around 0.995. Since sometimes these types of results are presented with Shannon metric of Entropy, a conversion from \(H_{min}\) to \(H_{S}\) is provided below. \[ \begin{split} H_{min}\approx 0.995\rightarrow\max_{i}(p_{i})& =2^{-H_{min}}\\ &=0.50173587425\end{split}  \tag{24}\]  
\[ \begin{split} H_{s}=-2^{-H_{min}}\log_{2}(2^{-H_{min}})-(1-2^{-H_{ min}})*\\ \log_{2}(1-2^{-H_{min}})=0.9999913\end{split}  \tag{25}\]  
Please note that just the 1 FiRO-1 GaRO configuration had a slightly lower entropy level.