> ...nor are they so numerous that iterating over them is computationally difficult That's not correct; for a given bound x, the expected number of primes is x

> ...nor are they so numerous that iterating over them is computationally difficult 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.