2

I am looking for a password based key derivation scheme that results in an asymmetric key pair. I have worked with PBKDF and its variants but could not come up with any way of generating a key pair. I have studied stuff online but the restrictions on the password do not suit me like password must be from a cyclic group etc. Any directions will be much appreciated!

  • Yuck. What problem are you actually trying to solve? – Deer Hunter Mar 1 '16 at 11:36
  • @DeerHunter Basically I need to generate an asymmetric key using PBKDF or anything similar. The input is a password and the output is a keypair. – The Nutty Professor Mar 1 '16 at 11:44
  • An asymmetric key has peculiar mathematical properties that are unlikely to be true for a random bit sequence. Your use case is also mighty unclear. – Deer Hunter Mar 1 '16 at 11:58
  • 1
    If you have a password that has sufficient entropy against bruteforcing, you could use it as a seed to an appropriate PRNG to generate large numbers to be sieved by primality tests to obtain a pair of primes to be the modulus of RSA keys. But why do you need to choose a password? You could much better (secure) use system randomness for getting the large numbers and you can also use an algorithm to generate provable primes instead of the statistically highly probable primes. – Mok-Kong Shen Mar 1 '16 at 14:06
  • 1
    @DeerHunter I am doing research on a system in which the key pairs are never present on the system. You generate the key pairs and then discard them thus eliminating key theft (an Achilles heel in crypto). – The Nutty Professor Mar 2 '16 at 10:44
2

Any asymmetric key pair generation can be described as a deterministic algorithm that feeds on a random source. Thus, generically speaking, you can turn a password into a public/private key pair by doing the following:

  1. Process the password into a "seed" of sufficient length (say, at least 128 bits) with a password hashing function.

  2. Feed that seed into a cryptographically secure PRNG to extend that seed into as many pseudorandom bits as necessary.

  3. Run the key pair generation algorithm with the seeded CSPRNG as source of randomness.

This kind of process has several important drawbacks that you should be aware of:

  • It requires a completely specified and unchanging key pair generation algorithm. For instance, for RSA, the algorithm concept is to produce random numbers until prime integers of the right size are found, but in the password-based setup you would have to be very precise on how exactly you turn the random bits into a candidate integer, and so on.

    Using an elliptic-curve based algorithm like ECDSA / ECDH may help, because private key is then just a random integer, with no condition on primality or anything like that. You still have to specify the generation algorithm, but at least it is simple.

  • If you change your password, you also change your key pair, which might have consequences in whatever system you are envisioning.

  • Good password hashing requires a salt, which is not a secret value, but should not be fixed either. You would need a storage space for that salt, somewhere.

  • The resulting public key would, by construction, be usable in an offline dictionary attack. Offline dictionary attacks are not a good thing for passwords. Properly configured password hashing functions can help fend off dictionary attacks, but there are limits to their power. A password-generated public key thus requires a really random password. Unfortunately, really random passwords are hard to memorize (see this question for some discussion -- the "correct horse" method, as presented in the post, yields passwords with 44 bits of entropy, which is good for a password, but not good enough to make offline dictionary attacks really tolerable).

  • Could you please elaborate if I use RSA for key generation then where do I get my prime number pairs from? – The Nutty Professor Mar 2 '16 at 12:47
  • The primes are "just there", mathematically speaking. See this answer. – Tom Leek Mar 2 '16 at 12:50
  • So you mean that the prime numbers are part of using RSA? – The Nutty Professor Mar 2 '16 at 13:06
  • "produce random numbers until prime integers of the right size are found" - this is done for security reasons, not procedural ones. If you're deducing a key from password, the prime number search may be sequential after the seed starting point. – Todd Jun 5 '17 at 1:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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