John Voight Seeks Prime Secrets
- By Joshua E. Brown
It used to be just generals, presidents and criminals who wanted to encrypt secrets. Now it's a necessity for anyone who wants some privacy on their phone, and math theorist John Voight is advancing today's science of secrecy.
For his insights into some of these patterns, including his work on elliptical curves (another mathematical principle at the backbone of today's cutting edge cryptography), Voight won the prestigious Selfridge Prize in 2010 given out by the Number Theory Foundation; he has received support for his research from the National Security Agency; and, in July of this year, he was the winner of a $400,000 CAREER grant from the National Science Foundation, one the government's highest honors for young scientists.
To get a glimpse into how Voight's research might protect privacy in coming decades try this easy problem: Multiply the prime numbers 6,451 and 7,307.
With your pencil, you'll get 47,137,457 in a few minutes. Simple. But now reverse the problem. Take this 47,137,457 and give it to some friends. Let them use a basic calculator. Ask them to find the prime factors -- the two whole numbers that multiply to get this number. They'll be at it for hours until they come to 6,451 and 7,307.
Sure, a computer could figure out this puzzle quickly, mostly by raw trial and error. But increase the size of your two prime numbers to something large, in the neighborhood of, say, 200 or 300 digits.
It's still pretty easy to multiply these two large numbers together. It would only take a moment for a computer. But going in reverse, finding the prime factors that made this large product "would take longer than the lifetime of the universe," Voight says, "using all the computing resources in the world."
Easy in, hard out
That one-way street, in essence, is the heart of modern cryptography and online security. "It is the difficulty of taking a large integer and factoring it into primes that is the basis of the most widely used cryptosystem, RSA, (named for its inventors, Rivest, Shamir, and Adleman)," Voight says.
Of course, there is a lot of complexity, padding, and variation in the application of this approach, but the central idea is this: the product of two or more prime numbers can be built into a so-called "public key" encryption system. This key can be made available to anyone, like shoppers on a website, who wants to encrypt a message quickly. (People won't tolerate waiting more than a few seconds on Amazon for their "Buy It Now" message to go through.) But only the people who know the original prime numbers can unlock the message at the other end.
It's the same basic mathematical tool used by the CIA or your smartphone to take plain words or credit card numbers -- and hide them within impregnable codes.
Or, at least today, codes made this way seem impregnable.
Since ancient times, mathematicians have tried and failed to find a solution to integer factorization. Many think it is a fundamental law of mathematics that there are no good shortcuts or fast algorithms to solve this problem.
But, Voight is quick to point out, the absence of success is by no means a rigorous mathematical proof. Somebody might solve this factorization problem tomorrow -- discovering a deep pattern -- and the systems that protect government secrets and clandestine purchases at Victoria's Secret would crumble.
"We don't have any proof yet that these systems are secure," Voight says. And the possible arrival of unfathomably fast quantum computers might also change the security equation.
Voight's research gets to the mathematical heart of these cyber security concerns. While his work is removed from applied cryptography, he is doing basic research that is expanding the mathematical toolbox that could improve current cryptography or give rise to the next generation of systems.
"Number theory is my subject," says Voight, an assistant professor with appointments in both mathematics and computer science, "and number theory at its heart is the study of prime numbers."
"The prime numbers conspire against those that try to study them in the sense that they do exhibit remarkable patterns," Voight says. "When you see them at large, you see patterns begin to arise. But proving that those patterns hold true is very difficult."
"John has a rare combination of computational wizardry with deep theoretical insight," says Matthew Greenberg, a professor at the University of Calgary and Voight's collaborator.
"Nothing could exist more purely in thought than primes," Voight says. Indeed, when astronomers are looking for extraterrestrial intelligence they beam out the sequence of prime numbers, he says, "because we know that whatever civilization is out there -- they won't care about the Kardashians -- but they will be able to understand the sequence of prime numbers."
And from this seemingly simple string of numbers, a torrent of theoretical complexity and chaotic practical problems rolls down.