5
$\begingroup$

The program Scallion can generate vanity PGP keys and .onion addresses using the following method:

  1. Generate RSA key using OpenSSL on the CPU
  2. Send the key to the GPU
  3. Increase the key's public exponent
  4. Hash the key
  5. If the hashed key is not a partial collision go to step 3
  6. If the key does not pass the sanity checks recommended by PKCS #1 v2.1 (checked on the CPU) go to step 3
  7. Brand new key with partial collision!

As RSA is susceptible to various attacks when its parameters are not properly selected, e.g. small difference of prime factors, does this method of iteratively increasing the public exponent yield any weaknesses in the generated keys?

Of course, it is possible to generate a key with a fingerprint you desire using gpg itself but it is much slower.

Improve this question
$\endgroup$
3
  • 2
    $\begingroup$ Interesting question. I can't think of any weaknesses off the top of my head. How long do we wait without an answer before we assume that there is no weakness? In other words, I doubt anyone can prove that there is no weakness. $\endgroup$
    – mikeazo
    Commented Feb 28, 2018 at 18:25
  • $\begingroup$ @mikeazo Actually, any choice of public exponent is equally good as long as we don't induce a short private exponent, but this should be caught by step 6. So at the end we get a "normal" RSA key-pair that passes all known checks for bad properties, the fact that we tried many others before that should be irrelevant. $\endgroup$
    – SEJPM
    Commented Feb 28, 2018 at 20:01
  • $\begingroup$ @SEJPM, good point. I forgot that the algorithm was to change the exponent. For some reason I was thinking tweaking the primes was the approach. Sounds like a good answer to me if you want to write it up. $\endgroup$
    – mikeazo
    Commented Feb 28, 2018 at 20:02

1 Answer 1

Reset to default
4
$\begingroup$

This method is fine (if it does actually check for short private exponents).

Any choice of public exponent is functionally and security-wise equivalent as long as it doesn't induce a short private exponent and as long as it is co-prime to $\lambda(n)$. The latter being caught by the fact that key generation won't be able to finish and the former being caught by the PKCS#1 v2.1 induced check (which I couldn't actually find, so beware!), which should check for short private exponents.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.