Design Of Secure Post-Processing Algorithm In True Random Number Generator

In cryptography, especially such as generating symmetric and public keys, and certain algorithms and protocols, the output of random number generator is supposed to possess not only good statistical distribution but also unpredictability. Even if the attackers know the design structure of the random number generator and parts of its output, they can not find its unknown output. It means that the designers have to analyze the ability of the attackers and prove the unpredictability theoretically, which are much more important than testing its output in the ideal condition. Thus, security analysis is essential in the design of true random number generator.Previously, the design of true random number generator lacks of precise security analysis. Most of them evaluate the random number by statistical test, but do not provide strict mathematical analysis and proof to verify their performance in the environment where the attackers impose interference. According to the requirement of cryptographic applications, this paper analyzes the security target for true random number generator, makes the attacker model hypothesis, and constitutes the security strategy accordingly. Furthermore, the design principles of entropy source and post-processing algorithm are proposed, and the secure mechanism given is proved to fulfill the security target.Based on the design principles given by security analysis, a secure post-processing algorithm is designed, which can extract random bits from the entropy source even in certain changing environment and resilient to certain attacks, and its security is guaranteed through mathematical proof. When the algorithm is transferred from theory to practice, the designer have to make a tradeoff between hardware cost and theoretical performance. In this paper, we use Toeplitz Matrix to construct a class of randomness extractor which fulfill the security demand above, and extend it to be a secure post-processing algorithm whose input can be arbitrarily long by CBC-MAC mode. Circuit implementation and verification analysis show that, it can attain good performance within reasonable cost, and it is suitable for cryptosystem.