Large even prime number discovered

Many people are under the erroneous belief that two is the only even prime number, but as Professor Paul Forester explains, “tings get really meshuga vhen numbers get large.” For example, when some number n gets very large, it becomes approximately the same as its successor. Because:

we can see that n must get closer and closer to n+1 when n is very large. So when numbers are pretty much the same as their neighbors at these large values, the notion of odd and even don’t hold in the traditional sense.

What does this mean for cryptography

First of all, this surprising mathematical discovery has no (immediate) bearing on the security of 1Password, as 1Password does not use the kind of cryptography that depends heavily on the theory of prime numbers. But this might have some implications for cryptography. At the moment, the only immediately visible impact is that it should make some of the slowest cryptographic computations quicker and more efficient.

In some cryptographic systems (though not 1Password), the software must generate large, randomly chosen prime numbers. This is a very time consuming process, and it works by first picking large random numbers, then checking whether they are prime through a series of tests. Almost all software implementations of this will only pick odd numbers by setting the least significant bit of the random number of 1. But this excludes half of the numbers it could pick, thus failing to find any of the even large primes.

Testing for primes

Once a random number is picked in the appropriate range it needs to be tested for primality. Many of the tests result in answers that aren’t quite definitive. Indeed, a number of tests produce results of either “definitely not prime” and “possibly prime” and each of these tests may different amounts of time to run. The general strategy is to run the quickest tests first on your candidate number, and only then run the more expensive tests. If your candidate number passes a sufficient number of those tests, then you can determine with sufficiently high probability that the number really is prime.

There is a way, of course, to definitively test whether a number, N, is prime. And that is to attempt to divide by every prime number less than or equal to the square root of N. But while that approach if definitive, it is simply far too many divisions to actually test.

The prime numbers in cryptography

The prime numbers used in cryptographic systems are typically 1024 bits (about 308 digits) long. Pairs of these are generated and multiplied together to produce 2048 bit (about 616 digit) products. Note that when you multiply, say, a five digit number by a three digit number you usually end up with an eight (five plus three) digit number. This holds when using bits instead of decimal numbers. So the product of two 1024 bit numbers will typically be a 2048 bit number.

Even for 300 digit numbers, which are far, far smaller than the million digit prime announced Saturday, it isn’t feasible to run definitive primality tests in the time we need when picking prime numbers. Indeed, it is probably near the edge of the NSA’s capability to factor 1024 bit products of 512 bit primes. This is why it is no longer recommended to use 1024 bit RSA keys.

A note on key sizes

If I am saying that 1024 bit keys aren’t safe, why does 1Password “only” use 256 bit keys? This is because different kinds of encryption systems have different kinds of keys. Keys used for the AES algorithm are completely random numbers. Guessing the key means trying every single 256 bit key until you find the one that works. That just isn’t possible even for a 128 bit key. But for public key encryption systems, not just any public key will do. Not just any 2048-bit numbers can be an Rivest-Shamir-Adleman (RSA) public key. Instead, it must (essentially) be the product of two 1024-bit prime numbers (which are, in essence, the private key).

I say “essentially” in there because if two prime numbers are p and q, then the actually public key isn’t p times q, pq, but is in fact Φ(p)Φ(q), which works out to (p-1)(q-1) in this case. The Φ function is known of as Euler’s totient function. For quite some time, I believed that there was a mathematician whose name sounded like “Oiler” who worked on similar stuff as the mathematician I’d read about, whose name I pronounced “Yuler”. Along the same lines, it was only when someone read the Little Prince aloud that I realized that the word I’d heard as “yu-neek” was the same as the one that I pronounce “un-ee-cue”. I still think of the Prince as “un-ee-cue in all the world.”

Let’s get back to key sizes. Not every public key system uses the RSA algorithm. The Diffie-Hellman (DH) system uses different mathematics, but has key length requirements similar to RSA. 1024 bits is no longer considered secure against the likes of the NSA. The third kind of public key algorithm in use is based on elliptical curves, and is sometimes called ECDH because it is actually based on the same logic as Diffie-Hellman at its heart, though it works through different mathematical operations. One advantage of ECDH is that it works with much smaller keys. So a 256-bit ECDH key is perfectly reasonable.

What to trust in this article

This article was posted on April 1, 2014. The claim that an even prime number other than two has been found is bogus. The notion of odd and even holds for all integers, no matter how large. The fictitious University of Southern North Dakota at Hoople is the creation of the real Peter Schickele. The fictitious mathematician Paul Forester is my resurrection of the great 20th century mathematician, Pál Erdős. Everything else here is actually meant to be reliable information. Including those bits that are un-ee-cue in all the world.

Jeffrey Goldberg

Principal Security Architect