A ring-oscillator-based true random number generator (TRNG) can be implemented using only digital standard cells. However, this requires significant hardware resources to compensate for the low bit rate. In this letter, we propose an improved Fibonacci and Galois ring oscillator (FIGARO) TRNG based on a multiple-sampling technique. We implemented FIGARO TRNGs with and without multiple sampling in the same field-programmable gate array and tested the generators’ randomness using the National Institute of Standards and Technology (NIST) random test suite. Our experimental results show that the proposed FIGARO TRNG with multiple sampling requires 3.67-4.76 times fewer resources than when only FIGAROs are used for the same bit rates.

※ The user interface design of www.jsts.org has been recently revised and updated. Please contact inter@theieie.org for any inquiries regarding paper submission.

### Journal Search

- (Software Education Committee, Hanyang University, 222 Wangsimni-ro, Seongdong-gu, Seoul 04763, Korea)
- (Dept. of Electronic and Electrical Engineering, Ewha Womans University, 52 Ewhayeodae-gil, Seodaemun-gu, Seoul 03760, Korea)
- (Dept. of Electronic Engineering, Hanyang University, 222 Wangsimni-ro, Seongdong-gu, Seoul 04763, Korea)

## 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 ^{(2)}.

In previous work ^{(6)}, 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 ^{(6)}. 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 ^{(10)}.

## II. PREVIOUS TRNG

The FIGARO TRNG was proposed in ^{(3)} 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 ^{(4)}. 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.

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 ^{(4)}.

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 ^{(5)}, where $M$ is the minimum number of FIGAROs required to pass the NIST random test
suite ^{(10)}. 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$.

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 ^{(5)}.

As a PPU, we chose to use a linear feedback shift register (LFSR), as used in ^{(6)}. 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 ^{(6)} 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 ^{(6)}, 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 ^{(10)}. 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.

Table 1. Random test results of our TRNG at 100 and 50 MHz

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. Implementation results at 50 and 100 MHz

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 ^{(6)}. Although the TRNG in ^{(6)} 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 ^{(6)}, 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)}.

### REFERENCES

## Author

Piljoo Choi received the B.S., M.S., Ph.D. degrees in Electronic Computer Engineering from Hanyang University, Seoul, South Korea, in 2010, 2012, and 2018, respectively. He is currently a professor in Software Education Committee at Hanyang University. His research interests are in the areas of security SoC (System on Chip), crypto-coprocessors, and information security.

Ji-Hoon Kim received the B.S. (summa cum laude) and Ph.D. degrees in electrical engineering and computer science from KAIST, Daejeon, South Korea, in 2004 and 2009, respectively. In 2009, he joined Samsung Electronics. In 2018, he joined the faculty of the department of electronic and electrical engineering, Ewha Womans University, where he is currently an associate professor. His current interests include CPU/DSP, communication modem, and low-power SoC design for security/biomedical systems. Dr. Kim is a technical committee member of the circuits and systems for communications and VLSI systems and applications in the IEEE Circuits and Systems Society. He was a recipient of the best design award at Dongbu HiTek IP Design Contest in 2007 and first place award at the International SoC Design Conference Chip Design Contest in 2008.

Dong Kyue Kim received the B.S., M.S. and Ph.D. degrees in Computer Engineering from Seoul National University in 1992, 1994, and 1999, respectively. From 1999 to 2005, he was an assistant professor in the Division of Computer Science and Engineering at Pusan National University. From 2006, he is a professor in the Department of Electronic Engineering at Hanyang University. His research interests are in the areas of security SoC, secure processor, crypto-coprocessors, and information security systems.