John Voight Seeks Prime Secrets
- By Joshua E. Brown
When mathematician John Voight enters his credit card number on Amazon.com he doesn’t worry too much. Even an expert hacker with a supercomputer will have a hard time breaking the code that keeps the number secret as it zips through cyberspace.
To understand why — and to also 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.
What’s a prime number? Fair question; I had to double-check with my son in fifth grade. Recall that prime numbers have the nifty property that they can only be divided evenly by 1 and themselves, like 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, etc. They sprout like weeds along the positive number line and, as Euclid discovered, they seem to go on forever. The largest prime number calculated so far has more than 12 billion digits.
“The prime numbers are a mysterious classical object,” Voight says. “They’re beguiling and deceptively simple.” As one of the nation’s most capable mathematical theorists, Voight doesn’t say this lightly.
Now back to the problem. 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. “When my students come in and say: we’ve thought about this for a long time and this is the best we could come up with,” he says, laughing, “I say: are you sure we can’t do better?”
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 teaches a course on the mathematics of cryptography. “I love this class,” says his student, sophomore Meraz Mostafa. “Sometimes Voight says something is hard, and that gives me hope. I like that he is still learning.”
But what Voight is learning does not come from being a practicing cryptographer, or from working directly on real-world security systems.
“I’m several steps removed from applied cryptography,” he says. Instead, 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.”
For his insights into some of these patterns, 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.
“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.
One of the difficult areas in number theory where Voight works is on elliptic curves, a strange donut-shaped progeny of the prime numbers. These geometric objects too have been used in cryptography systems, including on some of today’s smartphones.
“We can uses elliptic curves as one of these one-way functions that takes plain text and creates gobbledygook,” Voight says. “Anyone can go that direction, but it’s very hard to undo without some secret information.”
These elliptic curves have the potential to create the same or a higher level of security as other systems, but with smaller keys, reducing the amount of information that needs to be transmitted — a key, practical consideration as computers get faster.
Or, Voight thinks, elliptic curves might be able to rebuff the categorically different speed of not-yet-invented quantum computers that might break other code systems.
“For the first time in human history we’re all connected to one node, and those connections are shrinking the world,” Voight says. And privacy “is intrinsically human,” he believes. “So how do you maintain that privacy?” he wonders.
“I don’t think the solution is to have no secrets,” he says, “so we have to have an ability to maintain them.”
“I’m dancing with these mathematical objects,” John Voight says, “that we may need to turn to in the near future to develop secure communication.”