This paper presents a design and an implementation of an on-line quality control method for a TRNG (True Random Number Generator) on an FPGA. It is based on a TRNG with RS latches and a temporal XOR corrector, which can make a trade-off between throughput and randomness quality by changing the number of accumulations by XOR. The goal of our method is to increase the throughput within the range of keeping the quality of output random numbers. In order to detect a sign of the loss of quality from the TRNG in parallel with random number generation, our method distinguishes random bitstrings to be tested from those to be output. The test bitstring is generated with the fewer number of accumulations than that of the output bitstring. The number of accumulations will be increased if the test bitstring fails in the randomness test. We designed and evaluated a prototype of on-line quality control system, using a Zynq-7000 FPGA SoC. The results indicate that the TRNG with the proposed method achieved 1.91-2.63 Mbits/s of throughput with 16 latches, following the change of the quality of output random numbers. The total number of logic elements in the prototype system with 16 latches was comparable to an existing system with 256 latches, without quality control capabilities.

Linear complexity can be used to detect predictable nonrandom sequences, and hence it is included in the NIST randomness test suite. But, as shown in this paper, the NIST test suite cannot detect nonrandom sequences that are generated, for instance, by concatenating two different M-sequences with low linear complexity. This defect comes from the fact that the NIST linear complexity test uses deviation from the ideal value only in the last part of the whole linear complexity profile. In this paper, a new faithful linear complexity test is proposed, which uses deviations in all parts of the linear complexity profile and hence can detect even the above nonrandom sequences. An efficient formula is derived to compute the exact area distribution needed for the proposed test. Furthermore, a simple procedure is given to compute the proposed test statistic from linear complexity profile, which requires only O(M) time complexity for a sequence of length M.

Accurate values for occurrence probabilities of the template used in the overlapping template matching test included in NIST randomness test suite (NIST SP800-22) have been analyzed. The inaccurate values used in the NIST randomness test suite cause significant difference of pass rate. When the inaccurate values are used and significance level is set to 1%, the experimental mean value of pass rate, which is calculated by use of random number sequences taken from DES (Data Encryption Standard), is about 98.8%. In contrast, our new values derived from a set of recurrence formulas for the NIST randomness test suite give an empirical distribution of pass rate that meets the theoretical binomial distribution. Here, the experimental mean value of pass rate is about 99%, which corresponds to the significance level 1%.