1. 13
  1.  

  2. 4

    That’s a wild speedup, and the results (from 2012, folks on HN note) suggest way too little entropy was being used to generate some keys–6.2 million is about 8 million or 2^23 keys, 2^24 primes, so if everyone used 48 bits of entropy to generate a prime (less than they should use) you would expect about one coincidence in the set, not 12K. Of course, it doesn’t mean everyone’s keys are bad–can be a small (we hope) subset of keys generated with way too little entropy and a lot of collisions among those. (This eprint and https://factorable.net/ are the sources linked from the top HN reply for anyone who wants to read more.)

    1. 3

      Nadia Heninger et al at UPenn extended Daniel J. Bernstein’s work to formulate another efficient approach. She does quite a bit of cool work in this space.

      1. 2

        So…, uhhh, write your own crypto with unique prime generation? :)

        Also, it’s a real good thing we put our public RSA keys in key servers to make this so easy for malicious actors.

        1. 2

          it’s a real good thing we put our public RSA keys in key servers

          Uh, it was, at the time? The ideal was that I could look up your PK in a keyserver and send you an encrypted message without having to go through the rigmarole of first contacting you in plaintext and arranging a key exchange.

          And public keyservers could let you periodically update your keys with newer versions (maybe with different RNGs!) and still let people communicate with you with encryption.

          I’m betting that the majority of the keys that were broken had been used to encrypt one or two test messages, at most. At least that’s my experience from the heady days of PGP and creating keys.

          1. 1

            i should have used me sarcasm hat.

            1. 1

              Yep, sorry I missed that!

          2. 1

            Right. And the way to generate unique primes is to have lots of entropy, it’s as simple as that. You’re trying to choose a number at random from a very, very large set of candidates, of course you need a large pool of entropy.

            I bought some entropykeys while they were still being made. I don’t know anyone who makes a similar product now.

            1. 2

              I bought some entropykeys while they were still being made. I don’t know anyone who makes a similar product now.

              There’s a couple of hardware RNGs on crowdsupply, like: https://www.crowdsupply.com/13-37/infinite-noise-trng

              I might get one now that I understand why there’s such concern about the RNG…

              1. 2

                Note that some modern CPUs have real RNGs. I don’t trust those completely, but they do mean that if your CPU is modern and you run linux, then the worst case isn’t even nearly as bad as it was a decade ago.

          3. 1

            So the takeaway here is to ensure you use a randomly selected prime?