How can I create a key pair in Java, based on a password?

Question

I want to allow Alice to create a public/private key pair so that Bob can send her confidential messages. However, I want Alice to be able to check her messages from anywhere, and it would be a pain for her to have to carry around a memory stick containing her private key. Is there some way that Alice can create a public/private key pair based on a password which she remembers? In this way she could simply generate the private key (and public key) whenever she wanted to.

The short version of this question is: Where can I find the Java equivalent of cryptico.js.

Also, here's the same question on Stack Overflow, but for javascript.

Edit: Here's my first attempt at a solution:

    SecureRandom saltRand = new SecureRandom(new byte[] { 1, 2, 3, 4 });
    byte[] salt = new byte[16];
    saltRand.nextBytes(salt);

    int keyLength = 3248;
    SecretKeyFactory factory = SecretKeyFactory
            .getInstance("PBKDF2WithHmacSHA1");
    KeySpec spec = new PBEKeySpec(password.toCharArray(), salt, 8192, keyLength);
    SecretKey key = factory.generateSecret(spec);

    SecureRandom keyGenRand = SecureRandom.getInstance("SHA1PRNG");
    keyGenRand.setSeed(key.getEncoded());

    KeyPairGenerator gen = KeyPairGenerator.getInstance("RSA");
    gen.initialize(keyLength, keyGenRand);
    java.security.KeyPair p = gen.generateKeyPair();

Answer 1

When talking RSA: You could use the result of PBKDF2 to seed a pseudo random number generator, which can in turn be used to generate a key pair. Note that using SecureRandom won't work as it will add the seed to the pool instead of full reinitializing the rng. RSA needs a PRNG to find a random prime.

You are better off if you can use Elliptic Curve Cryptography. You could choose a standard NIST or Brainpool curve over F(p). Then you could use 32 bytes output of the PBKDF2 as the private key and calculte the public key. ECC only requires a random private key and as the output of PBKDF2 should be indistinguishable from random, the output would be fine. Not only don't you need an additional PRNG, you are saving yourself the time to calculate an RSA key pair as well - and this can be substantial.

Note that nothing will prevent a brute force attack against something encrypted with said calculated key, so you should better ask for a passphrase of 16 characters or more, containing non-dictionary words, numbers and signs. Anything less will likely fail, especially if the users are unaware of possible attacks. Note that if you don't have storage, you cannot use a random salt. If you cannot have a random salt you cannot defend against rainbow tables (for your specific application, you can use a application specific salt of course). Furthermore, persons with the same passphrase will generate the same private key.

Of course the default way - for instance in PGP - is to store the private key encrypted using password based encryption. This however requires a storage. The advantage of that approach is that you can have a fully random key, which means that without access to the key storage, brute force attacks against cipher texts are impossible. It adds an important extra layer.

Answer 2

You don't provide many details but if you want to generate your keypair using the java.security.KeyPairGenerator you will have to define your own class that extends SecureRandom, but uses only the supplied password as the entropy source.

You don't need to implement a SecureRandomSpi class, you can just call the protected constructor of the superclass with (null, null) arguments.

Answer 3

RSA key length is typically 1024 or 2048 bits. That makes 128 or 256 bytes.

Passwords are typically 8 bytes long (and use only a around 64 different bytes).

You would lose much of the strength of the algorithm if the RSA key was derived from the password. Attackers would only have to guess or brute-force an 8-bytes password rather than a 128 or 256-bytes long key.