I. INTRODUCTION

Random numbers can be generated by two types of generators: pseudo-random number generators (PRNGs) and true random number generators (TRNGs). PRNGs use complex algorithms, whereas TRNGs can be implemented via simple structures. TRNGs based on ring oscillators (ROs) ^(1-6) are widely used because of their simple structures and low cost of implementation; such generators use only digital standard cells without complex analog circuits. However, the main entropy in RO-based TRNGs occurs because of jitter accumulation in ROs, which is very time consuming. Although low bit rates due to jitter accumulation can be overcome by using multiple ROs, this uses more hardware resources ⁽²⁾.

In previous work ⁽⁶⁾, we proposed a multiple-sampling technique and compared it to a conventional RO-based TRNG method. To compensate for the low bit rate, we did not increase the number of ROs like the conventional method, but used multiple clock signals with different phases instead of a single clock signal. Here, using our multiple-sampling technique as a basis, we improve the Fibonacci and Galois ring oscillator (FIGARO) TRNG ^(3-5), which is widely used ^(7-9).

Because jitter accumulates randomly in a FIGARO, a TRNG using a FIGARO can generate entropy faster than TRNGs using only normal ROs. Although a FIGARO TRNG also requires multiple FIGAROs to achieve high bit rates, the number of required FIGAROs can be reduced by using multiple sampling ⁽⁶⁾. We implemented both the original FIGARO TRNG without multiple sampling and our new FIGARO TRNG with multiple sampling in the same field-programmable gate array (FPGA) and compared these two types of TRNGs in terms of their bit rates and hardware resource usage. During our experiments, we verified the randomness of the TRNGs using the National Institute of Standards and Technology (NIST) random test suite ⁽¹⁰⁾.

II. PREVIOUS TRNG

The FIGARO TRNG was proposed in ⁽³⁾ and only approximately 50 ns are required after a restart until the standard deviation of its outputs reaches a value close to 0.5. This is a much shorter duration than the thousands of ns required for a normal RO ⁽⁴⁾. Compared to a normal RO, this difference is caused by the more complex structure of the FIGARO, which consists of a Fibonacci RO (FIRO) and a Galois RO (GARO), as illustrated in Fig. 1.

Fig. 1. Structure of FIGARO.

A FIRO and a GARO are configured using the binary polynomials$f\left(x\right)=1+\sum _{i=1}^{r_{1}- 1}f_{i}x^{i}+x^{{r_{1}}}$and$g\left(x\right)=1+\sum _{i=1}^{r_{2}- 1}g_{i}x^{i}$ $+x^{{r_{2}}}$, respectively. The paths marked $f_{i}$ and $g_{i}$ are shorted or open depending on the values of $f_{i}$ and $g_{i}$. This creates multiple inner loops in the feedback structure, which causes pseudo-randomness. In contrast, a normal RO has only a single loop. As a result, sampling the FIGARO rather than a normal RO is much more advantageous for obtaining entropy ⁽⁴⁾.

Depending on the frequency of the system clock or the required bit rate, more than one FIGARO can be used; for example, $M$ = 5 at 12 MHz in ⁽⁵⁾, where $M$ is the minimum number of FIGAROs required to pass the NIST random test suite ⁽¹⁰⁾. When $M$ > 1, before being sampled by the system clock, $clk_{\mathrm{system}}$, the FIGARO outputs are combined into one signal using simple logic gates, such as the exclusive-or (XOR) gate shown in Fig. 1. To remove bias and further improve randomness, the XOR gate can be replaced with more complex logic gates, called a $post-processing$ $unit$ (PPU).

III. PROPOSED DESIGN

By applying multiple-sampling technique, our improved TRNG can generate random bits at high bit rates and requires a single FIGARO rather than multiple FIGAROs. Including the additional circuits for multiple sampling, the structure of our TRNG is described in Fig. 2, where $N$ is the number of cells in the $clock$ $generator$.

Fig. 2. Our new FIGARO TRNG using multiple sampling.

In contrast to a conventional FIGARO TRNG depicted in Fig. 1, our new TRNG additionally has a $multiple-sampling$ $unit$ (MSU) before the FIGAROs are sampled by the $clk_{\mathrm{system}}$. The $N$-phase clock signals for MSU come from the cells connected within a feedback structure in the clock generator, and one by one, they are distributed to $N$ pairs of falling-edge and rising-edge-triggered flip-flops (FFs) in the MSU. The total 2$N$ FFs sample the common data signal from the FIGARO at the falling-edge and rising-edge of the $N$-phase clock signals.

Because the intervals between the sampling points at 2$N$ FFs are very short, the multiple-sampling technique increases the probability that the data signals are sampled near the threshold voltage. This unstable state, which does not have a definite value of one or zero, is referred to as meta-stable. This meta-stability is a source of entropy in TRNGs. Multiple sampling can cause meta-stability, which improves randomness and reduces $M$ compared to TRNGs using FIGAROs alone ⁽⁵⁾.

As a PPU, we chose to use a linear feedback shift register (LFSR), as used in ⁽⁶⁾. The LFSR is configured using an irreducible polynomial $p\left(x\right)=1+\sum _{i=1}^{2N- 1}p_{i}x^{i}$ $+x^{2N},$ which is similar to the configuration method used for the FIRO and GARO. Because of its complex structure, the LFSR is more advantageous for post-processing than the XOR gate in Fig. 1. Note that to generate one random bit, the TRNG in ⁽⁶⁾ requires the accumulation of multiple clock cycles in the PPU. In contrast, our TRNG can generate one random bit every clock cycle without accumulation. Therefore, unlike in ⁽⁶⁾, the bit rate does not decrease.

IV. IMPLEMENTATION AND TESTING RESULTS

Our TRNG was implemented in Xilinx XC6SLX150 (Spartan 6) using the same configuration described in ^(4-6) : $f\left(x\right)=x^{15}+x^{14}+x^{7}+x^{6}+x^{5}+x^{4}+x^{2}+1,$ $g\left(x\right)=x^{31}+x^{27}+x^{23}+x^{21}+x^{20}+x^{17}+x^{16}+x^{15}+x^{13}+x^{10}+x^{9}+x^{8}+x^{6}+x^{5}+x^{4}+x^{3}+x+1,$ $N=3,$ and $p\left(x\right)=x^{6}+$ $x^{5}+1$. A total of 10$^{9}$ bits were generated continuously at a clock frequency of 100 MHz. Then, the bit sequence was extracted via USB and examined using the NIST random test suite ⁽¹⁰⁾. We also conducted an additional test at 50 MHz. In the additional test, we replaced the FIGARO with a smaller RO: a FIRO. The test results in Table 1 show that all proportions are > 0.9805607 and all P-value$_{T}$ are > 0.001. This means that the bit sequences from our TRNG passed the test suite with acceptable proportions for a level of significance of $\alpha $= 0.01 and with a uniform distribution.

We compared the performance of our improved TRNG with that of the original FIGARO TRNG. For a fair comparison, we also implemented the original FIGARO TRNG in the same FPGA with an LFSR-based PPU instead of just the XOR gate in Fig. 1. Only the size of the LFSR in the PPU was different, depending on $M$. The implementation results for 50 and 100 MHz are shown in Table 2. A FIRO is considered as $M$ = 0.5 because a FIRO is a part of the FIGARO.

Table 2 shows that the use of multiple-sampling technique can significantly reduce the value of $M$. Considering that a FIGARO occupies 70 LUTs and an MSU occupies only six registers and nine LUTs, adding an MSU is more effective for entropy enhancement than adding more multiple FIGAROs. As a result, our TRNG requires 3.67 and 4.76 times fewer resources at 50 and 100 MHz, respectively, than the original FIGARO TRNGs for the same bit rates.

Table 2 also shows that our new TRNG has much higher bit rate and BPA than the TRNG in our previous work ⁽⁶⁾. Although the TRNG in ⁽⁶⁾ already has a higher BPA than those of the TRNGs in ^(11,12) for compliance with the NIST random test suite, it is difficult to increase its bit rate any further even when higher bit rates are required. For higher bit rates, our new TRNG can be a good alternative rather than the TRNG in ⁽⁶⁾, requiring small area overhead.

V. CONCLUSIONS

We proposed an improved FIGARO TRNG using multiple sampling; this allowed the number of FIGAROs to be reduced in exchange for small additional logic costs for the multiple sampling. Our implementation results showed that for the same bit rate, our improved FIGARO TRNG required fewer resources than the previous method that uses only multiple FIGAROs. This means that applying multiple sampling is very effective to improve bit rates, and we expect that the multiple-sampling technique will be also applicable to other RO-based TRNGs. Additionally, the NIST random test results showed that our TRNG generated random numbers sufficiently secure to be used in applications such as cryptography ^(7-9).