Skip to main content

PSA: Do Not Use the New Prime Number for RSA Encryption

You might be tempted to use that shiny new prime number for RSA encryption. Don't do it.

This article was published in Scientific American’s former blog network and reflects the views of the author, not necessarily those of Scientific American


You may have heard that there’s a new largest prime number in town. The number, 274,207,281-1, or M74207281, has 22,338,618 decimal digits, although the more sensible way to write it is in binary: it’s just 74,207,281 ones. This, like most of the other largest primes we know, is a Mersenne prime, a number that's one less than a power of 2. I know it’s shiny and new and tempting, but do not, I repeat, do not, use it for RSA encryption.

RSA encryption uses the difficulty of factoring the product of two large prime numbers to make sure hackers can't find your credit card number. To implement it, first you have to find two really big prime numbers and multiply them together. 

In general, the bigger the prime numbers you find, the safer your secret will be. 91 is pretty easy to factor; a 600-digit product of two 300-digit primes, not so much. Ergo, it seems logical that the new Mersenne prime would be a perfect candidate. 


On supporting science journalism

If you're enjoying this article, consider supporting our award-winning journalism by subscribing. By purchasing a subscription you are helping to ensure the future of impactful stories about the discoveries and ideas shaping our world today.


The only problem is that you will instantly be hackable. People are used to seeing public keys that are several hundred digits long. If they see one that’s several million, it’s going to raise some eyebrows. You’re not too likely to just stumble on a several million digit prime number. The prime number theorem says only about 1 in every 50 million numbers is prime by the time you get up to M74207281. People are going to start to wonder where you got that prime, and they’ll check and see if M74207281 or one of its little siblings is one of the factors of your public key. It might take them a while to check, but not as long as factoring the number without any divisors in mind.

I may have lied when I said hackability was the only problem. There's another more technical potential complication. RSA works by raising numbers to a large power and then finding the remainder when divided by a big number. It's actually a little easier to understand in mathematical notation. We call our message m, our exponent e, and our big number N. To encode something using RSA, you find me mod N. Mod, short for modular, just means the remainder when you divide by N. M74207281 is so big that, depending on the sizes of m and e, the encrypted message me might not be bigger than N, so it will be its own remainder mod N. That’s not great because you could just take the plain old e-th root of the number to find the original message m. Oopsie.

So just fight the temptation to use millions-of-digits primes for RSA, at least for the time being. It took academics two years to crack RSA-768, a 232-digit number. We’re constantly getting faster at factoring big numbers, but it will be quite a while before we need the full power of those big Mersennes.

And if you're wondering why all the big primes are Mersenne primes, check out my Slate article about it.