# True Random Number Generator Based on Fibonacci-Galois Ring Oscillators for FPGA
## 1 Introduction: Random Number Generation for Security  
With the increasing number of connected-devices the information security is becoming more important than ever before [1]. A large number of security operations, also in less conventional fields such as smart grids [2], require random numbers to protect the confidentiality, integrity and authenticity of the exchanged information. Secure cryptographic keys creation, nonces generation in authentication protocols and digital signatures require, in fact, unpredictable numbers [3]. In stream cyphers the key cannot be reused multiple times, then, the key must be a random bitstream which must never be repeated, hence the name One Time Pad. In block cyphers the key is reused in every encryption or decryption operation but, it must be necessarily chosen randomly. Random numbers are also widely used for the prevention of replay attacks. A countermeasure for such attacks is represented by the digest authentication mechanism [4], a challenge-response protocol which requires the generation of a new nonce for every tentative of authentication. Random numbers are fundamental also for the security of digital signature algorithms [5] and can be employed for the improvementof passwords security in user authentication contexts (e.g., One Time Passwords). A True-Random Bit (or Number) Generator (TRBG or TRNG) exploits physical phenomenons to acquire random data (with high entropy) from unpredictable sources, such as thermal noise and jitter. Depending on the nature of the entropy source, the randomness can be generated either in the analogue world (e.g., noise or sensors [6]) or in the digital world (e.g., jitter). There are also examples in literature [7] of Cryptographically Secure Pseudo-Random Number Generator (CSPRNG); such circuits, however, requires a TRNG to work. Due to their intrinsic close relationship with analogue parameters of the circuit, True Random Number Generators are usually tailored on specific silicon technology and are not easily scalable on programmable hardware, without affecting their entropy. Several relevant contributions reviewed the state of the art, both from a mathematical [8] and an architectural [9] point of view; however, the available information addresses the problem at a high level, not focusing on particular technologies, such as Field Programmable Gate Arrays (FPGAs). On the other hand, programmable hardware and programmable System on Chip are gaining large adoption rate, also in a security-critical application, where high-quality random number generation is mandatory. Digital TRNGs can be implemented using logic gates only, exploiting digital sources of randomness, such as supply voltage noise [10; 11] metastability [12; 13; 14] and jitter [15; 16; 17]: the area footprint, in this case, is dramatically reduced by the absence of analogue circuitry and the consequent possibility of mapping all the design in digital standard-cell. In this paper, we will focus on all-digital TRNGs, to investigate on which one is more optimized for Field Programmable Gate Array (FPGA) technology. The main contributions will be the introduction of an experimental methodology to evaluate entropy and place and route independence for TRNGs on FPGA. Up to the authors' knowledge, this contribution is the first to apply such a methodology to the available TRNG architecture. Thanks to that, we have been able to give our other major contribution: the selection of the best TRNG for FPGA architecture, as a trade-off between complexity, entropy and place and route independence. We also analyze the design space, demonstrating how the performance of the TRNG vary within the possible configurations. Such a solution is then compared to the state-of-the-art, demonstrated to be in line in terms of throughput with comparable entropy and complexity.