An efficient high quality random number generator for multi-programmed systems

Article type: Research Article

Authors: Zúquete, André

Affiliations: IEETA/UA, Campus Univ. de Santiago, 3810-193 Aveiro, Portugal. Tel.: +351 234 370504; Fax: +351 234 370545; E-mail: avz@det.ua.pt

Abstract: This document presents an efficient, high quality random number generator for multi-programmed environments, in particular for UNIX/Linux and Windows systems. The algorithm uses a system's notion of the time, given by a high-precision real-time counter, to obtain random bits, and a combination of system calls to reduce the correlation between consecutive random bits. The combination of system calls introduces variable and unpredictable real-time gaps in the execution of the generator. We present a rationale for such variation and unpredictability, and we show that in fact they exist even when the generator runs in an adverse scenario, i.e., a lightly loaded system. We also show how the generator resists several attacks attempting to guess or control the values it produces. The quality of the generator is evaluated both in terms of its performance and the randomness of the byte sequences it produces. Comparing against other similar generators, CryptoLib and librand, our generator produces equally good random byte sequences, but its performance increases with the speed of the processor, while the performance of CryptoLib and librand is rather constant for each operating system, independently of the processor were it runs.

Keywords: Random number generators, operating systems, Pentium processors, time samples

DOI: 10.3233/JCS-2005-13202

Journal: Journal of Computer Security, vol. 13, no. 2, pp. 243-263, 2005