3 ms·
Yeah I think you are right, the article is weak. Even the first implementation advice it gives doesn't look right to me, if interpreted the obvious way: > Nor
by throwaway81523 5y ago
Yeah I think you are right, the article is weak. Even the first implementation advice it gives doesn't look right to me, if interpreted the obvious way:
> Normally for RSA you pick 2 random numbers and then find a prime close to each.
I.e. if you pick a number and then search upwaard til you find a prime, that gives a non-uniform distribution on the primes in that range. You instead want to pick a random number, and if it's composite, throw it away and pick another random number til you get a prime. Then repeat to get second prime.
- kwantam 5y ago"Pick a random odd number and keep adding 2 until you find a prime" is, perhaps unintuitively, essentially fine for RSA key generation---under mild conditions, the security loss is single-digit bits at best. See Abboud and Prest, "Cryptographic Divergences: New Techniques and New Applications", SCN 2020 [1], Section 4.1. (This is a relatively recent result. And as I mentioned in my other comment, this is not a defense of the article!) [1] https://eprint.iacr.org/2020/815 https://eprint.iacr.org/2020/815
- throwaway81523 5y agoInteresting. I'll look when I get a chance, but it sounds like deep math. The distribution of primes empirically seems well approximated by Cramér's random model, but it's incredibly hard to know anything for certain. For example, whether there are infinitely many twin primes is a famous open problem.