There are definitely possible (though perhaps not immediate) applications for primes of this size. For example, in 2009, researchers were awarded $100k for the discovery of the Mersenne prime 2^43112609-1.
This number, while too large for RSA or ECC, could very well be useful for (R)LWE schemes (used to make post-quantum secure public-key cryptography and partial/fully homomorphic encryption schemes). In particular, it is free to modularly reduce by this prime (take the bottom 43112609 bits), so schemes that rely on doing large matrix multiplication on a modular elements (or even elements in a polynomial ring) would benefit greatly.
Since 43112609 bits is only 5.3MB, this is not at all a ridiculous size - multiplying numbers of 2^26 bits is feasible in well under 1 second in modern hardware, and so making accumulation and modular reduction free is actually valuable.
Am I missing something? 2^3 - 1 is a Mersenne prime; but taking a number mod 7 is not taking the 3 low bits (there's a relatively low cost trick to take numbers modulo b-1, the same "divide by 9" tricks we can do in base 10... but it's not as easy as looking at the last digit).
There's notably also the all 1's case to deal with as an exception.
In that timeframe, the main technical advances that helped GIMPS get more efficient were being made by Richard E. Crandall (https://en.wikipedia.org/wiki/Richard_Crandall), who also wrote Prime Numbers: A Computational Perspective with Carl Pomerance (https://en.wikipedia.org/wiki/Carl_Pomerance). If these folks are trying to help governments keep a monopoly on expertise about number theory and the difficulty of the RSA problem, they seem to be doing a pretty bad job of it.
> The EFF [...] is sponsoring cooperative computing awards [...] to encourage ordinary Internet users to contribute to solving huge scientific problems.
What is "cooperative computing" and what does it mean by "encourage ordinary Internet users to contribute"? You must know a bit of history to see the context here. Back in the 1970s, the NSA drafted the Data Encryption Standard, or DES, as the national standard of data encryption for sensitive data, the NIST standardized it. However, Despite the decision by IBM to use a 64-bit key and the strong criticism from academic cryptographers (most prominently Diffie and Hellman [0]) that anything shorter than 128-bit is untrustworthy, a key length of 56-bit was selected by the NSA. D&H estimated that the NSA could theoretically construct a DES cracker for $20 million in 1976.
Fast forward to the 1990s, the security of DES has become a serious problem. Just as predicted, its 56-bit key could not keep up with the progress in semiconductors and it could be broken even by a small organization at any moment. And after 1995, Internet access opened to the public, if the government mandated the use of DES (instead of replacing it by something stronger), it would create a serious threat to security and privacy to both ordinary citizens and businesses.
However, the NIST refused to acknowledge DES's insecurity due to NSA and the FBI's effort to prevent the use of strong cryptography by the public, the FBI even described DES-encrypted data as a threat to national security. Around the same time, the U.S. government was also trying to suppress Phil Zimmermann for his PGP and was pushing a backdoored phone encryption system (sounds familiar?) known as the Clipper Chip. It was the First Crypto War.
Because the insecurity of DES was both a threat to citizens and businesses interests, RSA Security, Inc cooperated with the civil libertarians in the crypto war to push the NSA back. One thing it did was launching an anti-DES campaign. To demonstrate that the claims of DES's security by the U.S. government was false, in 1997, RSA Security Inc started "The DES Challenge" - the company published an encrypted ciphertext, and anyone who can break DES and discover the plaintext would win $10,000.
A group of computer scientists led by Rocke Verser, assisted by Justin Dolske and Matt Curtin, responded this challenge by started the DESCHALL Project. They created a distributed computing network - anyone who didn't like the NSA could help by contributing CPU time from a PC. It was truly an innovative idea. Later known as distributed.net, it's arguably the first volunteer-run distributed computing network, the predecessor of BONIC, SETI@Home or Folding@Home (the only competitor is GIMPS, which was established around the same time).
The server was on a 486-based PS/2 PC with 56 MiB of memory, and they announced the project via Usenet towards the end of March. Client software was rapidly written for a large variety of home machines and eventually some more powerful 64 bit systems. About 10,000 people joined, and the DES Challenge was broken in 96 days, DES was demonstratively broken, a definite proof. Later, RSA launched another DES Challenge, the DES Challenge II-1. DES Challenge II-1 was cracked by distrbuted.net in 39 days in early 1998. The plaintext message being solved for was "The secret message is: Many hands make light work." It was the first significant demonstration of the distributed computing's power. Distributed.net celebrated this moment in an email,
> Distributed.net is equivalent in processing power to:
11,264 DEC Alpha 21064 533s
15,316 Sun Ultra I 167s
22,393 Intel Pentium II 333s
68,859 Macintosh PowerPC 604e/200s.
41,712 Intel Pentium 166s
399,374 Intel 486DX2/66s
7,446,033 Intel 386SX/20s
> Prospective:
> If Keys were dollars, we could pay off the U.S. National Debt in 6.25 minutes
> If Keys were pennies, we could buy 536249385 Mazda Miatas each day.
> If Keys were pennies, we could buy 256728249 Jeep Cherokees each day!
> If you printed a single page to represent each key block as it was checked and placed those pages in a stack, it would grow 12.83 inches taller every minute.
> If blocks were liters of Dr. Pepper, we could produce 6381493 six-packs each day
> If Key Blocks were cheeseburgers, fries, and a large Dr. Pepper, we could feed the entire city of Toronto, Ontario lunch each day.
After this incident, the government still refused to acknowledge the insecurity of DES. FBI director Louis Freeh told Congress,
> "If we hooked together thousands of computers and worked together for months we might, as was recently demonstrated, decrypt one message bit. That is not going to make a difference in a kidnapping case. It is not going to make a difference in a national security case. We don't have the technology or the brute force capability to get to this information."
The RSA started yet another challenge, DES Challenge II-2. Meanwhile, the Electronic Frontier Foundation joined the game, thanks to its sponsors, the EFF spent $250,000 to build The EFF DES Cracker (nickname Deep Crack), a special purpose computer with 29 circuit boards and 1,856 ASIC chips. DES Challenge II-2 was solved in just 56 hours in July 1998. And the third challenge, DES Challenge II-3, was a cooperation between EFF and distributed.net, the key was found in just 22 hours 15 minutes in January 1999, and the plaintext was "See you in Rome (second AES Conference, March 22-23, 1999)".
And the rest was history, DES was retired in late 1999s, the review of the Advanced Encryption Standard was performed in a highly transparent manner, later completed in 2001, Rijndael won, and became the most widely used cipher on the Internet.
As you see, the First Crypto War was won largely due to > distributed computing. It was under this historical context that the EFF set up the cooperative computing award from an anonymous sponsor around 2000. Based on the history, it's persuadable to assume the intention by the anonymous donor was to encourage the applications of distributed computing, so the next Crypto War can be won.
Finally, fun fact: After the First Crypto War, distributed.net is irrelevant, but it still exists, and the RC5-72 cracking project from the 2000s is still running, it's estimated that the brute-force search of the keyspace will complete within 150 years.
“Cracking DES”, a book published by the EFF, contains the necessary information to build your own Deep Crack DES brute force appliance. It’s available in the Internet Archive: https://archive.org/details/crackingdes00elec
https://www.copacobana.org/docs.html
(I'm a little confused at why crack.sh had to spend roughly as much money per key per second as Copacobana, when it was being built with a more advanced model of the same manufacturer's FPGAs around a decade later. I wonder if the Virtex-6 has some high-end features that crack.sh doesn't really benefit from, but still had to pay for.)
Clearly, no smaller primes are secret either, nor are they so numerous that iterating over them is computationally difficult. And mathematically, anyone can discover primes. Why does it matter whether primes are secret?
That's not correct; for a given bound x, the expected number of primes is x/ln(x).
For example, if you need to choose a prime of 100 digits, there are something like 10^96 of them; you can find a random one using probabilistic methods, do your cryptography, and know that your attacker would have to try 10^96 primes to break it. Since they can't really do this, this is not the weak point of your cryptosystem.
If you chose a Mersenne prime, there are only 51 of them. Your attacker would have to try less than 10^2 of them.
Some cryptosystems like ECDSA are based on secret elements selected from a field, and the primes there are public.
Otherwise, reductio ad absurdum, Following the same line of logic, all cryptography is "security through obscurity" because there exists a secret key, which is not incorrect. The practice of hiding the design of a system is obscurity, the practice of hiding a specific key to a ciphertext is security, not obscurity, as long as the method of generating and using it is publicly available. If there's nothing to reverse engineer, there can be no obscurity. The method of finding a symmetric key or finding a RSA key is well-known, not obscured, it's simply the size of the problem is not computationally tractable in practice by today's computers.
Because of EFF's advocacy for cryptography, people always thought that there was a more direct connection between the Mersenne prime search and cryptographic techniques, but the connection is at best distant and tenuous. The record primes that GIMPS finds and that can receive EFF's awards are
* much (much much) bigger than the primes that we use for cryptography
* too big to do almost any kind of practical computation with
* not secret, so couldn't be used as part of a secret key
The distribution or explicit values of Mersenne primes (and, correspondingly, perfect numbers) also don't really help in our assessment of the difficulty of the RSA problem or the security of public-key cryptography, because they aren't closely related to any of the fastest factorization algorithms that apply to arbitrary numbers.
(Mersenne primes are much easier to deterministically test for primality than numbers in general, which is why the record primes that GIMPS finds are Mersenne primes. The runtime complexity of primality-testing algorithms for special-form numbers is sometimes much less than algorithms for an arbitrary number, and this is a great example.)
I think the main contribution of projects like GIMPS to cryptography and computer security lies in getting people more interested in number theory and mathematics in general. Hopefully that will lead to faster improvements in humanity's knowledge of mathematics in ways that lead to more secure public-key algorithms or to better public assessments of the algorithms that we have now. (Although a lot of the important current research on public-key cryptography is not about factorization but rather about elliptic-key systems and post-quantum systems.)
I always felt I had a hard time explaining to people that the awards existed in order to publicize the idea of cooperative distributed computing projects, which were quite novel when EFF's awards were first created, and which were a demonstration of the power of the Internet to help people who've never even met each other work together. (The awards, contrary to the hopes and dreams of math enthusiasts and cranks around the world, didn't anticipate progress through new research or ideas so much through more volunteer computer time.)
Probably today we have ample other demonstrations of that power, and that concept is no longer in much doubt, and the GIMPS project probably no longer even registers for most people as a particularly impressive example. But it is impressive in continuing to set multiple world records on one of the simplest, purest, most basic mathematical problems.