Creating sets of truly random numbers may be harder to accomplish than people think, but that hasn’t stopped UT computer science professor David Zuckerman from trying.
Computers can obtain randomness by monitoring things such as thermal noise or intervals between keystrokes, but they often fail to provide high-quality randomness, Zuckerman said.
“Think of choosing a number from 1 to 100,” Zuckerman said. “It’s perfectly random if each number has a probability of 1 in 100. [In] low-quality randomness, some of these probabilities are as high as 1 in 10.”
In a study in the Society for Industrial and Applied Mathematics, Zuckerman and a team of researchers developed an algorithm called a two-source random extractor. The algorithm takes two independent low-quality random number generators and combines them into a high-quality one.
Random numbers have scientific applications, from computer security to simulating climate models to polling for public support of a presidential candidate. Such calculations require a great deal of complexity and unknown variables, which are generally too complicated for a computer.
Scientists can instead use random numbers to model this complexity. However, current random number generation is not completely random, which can warp scientific results or create weaknesses in computer security.
“The computer … just takes one instruction after the other. Computers can look at things like randomness in keystrokes, so we have ways of getting low-quality random sources,” Zuckerman said. “The question is how can we convert these low-quality random sources into high-quality random sources.”
In cryptography, two secret randomly generated prime numbers are multiplied together to create an encryption security key, which allows two parties to communicate privately over a public channel.
Yevgeniy Dodis, computer science professor at New York University and first author of the study, said if the numbers are not random enough, it becomes easier to factor them from their product and break through security.
“Cryptography is based on the assumption that you can securely generate good random numbers as a security key,” Dodis said. “This number is chosen completely at random, because if there are biases, it means that the hacker has a much easier time breaking the system.
The two-source extractor was found to exponentially improve random number quality, providing greater security. Zuckerman said that although this extractor must be made more efficient before it becomes practical, it does have applications in theoretical math and computer science.
According to Dodis, random numbers are often neglected in conversations about cybersecurity.
The National Institute of Standards of Technology released a random number generation algorithm called Dual_EC_DRBG in 2006. According to documents leaked by Edward Snowden, the National Security Administration allegedly inserted a backdoor into the program that allowed for mass surveillance. NIST withdrew Dual_EC_DRBG from its recommendations for random number generators in 2014.
“People talk a lot about computer security, but random numbers are often overlooked. They’re less popular than breaks into firewalls or software bugs,” Dodis said. “Random numbers are the foundation of everything. Without that, you just can’t talk about computer security.”
