Deterministically generate a RSA public/private key pair from a passphrase (with sufficient entropy)? Is it possible to deterministically generate public/private RSA key pairs from passphrases?

Would giving the (key generating) algorithm data made from key-stretching the passphrase (instead of a source of random data) be sufficient and strong?



Extra credit:

Is it possible to generate a key pair from one public and one private passphrase, such that the public key can be generated from only the public passphrasse?  (The private key can use both.)

(I'm trying to deal with the difficulties in using RSA keys as pasted/exchanged things.)
Yes, it is possible to deterministically generate public/private RSA key pairs from passphrases. For even passable security, the passphrase must be processed by a key-stretching function, such as Scrypt (or the better known but less recommendable PBKDF2), and salt (at least, user id) must enter the key-stretching function; the output can then be used as the seed material for the RSA key generation. This works for any public-key cryptosystem.

Security is equivalent to what you have in e.g. PGP/GPG when assuming an adversary has access to the private key file protected by the (unknown, key-stretched) passphrase. However, there are drawbacks:


one is giving away the considerable degree of security obtained, in normal practice, by not making the  private key file public; that first line of defense is lost, only the (stretched) passphrase remains;
it is impossible to change the passphrase while keeping the same key and the advantage that only the passphrase is needed;
the key pair generation method should remain static; any change will end up with a different key pair; that precludes periodically increasing the passphrase-stretching parameters to take into account hardware progress (while keeping the same key and the advantage that only the passphrase is needed);
as a consequence, there's a very difficult compromise between security for many years with the same public key, and acceptable usage speed now;
as a minor aside, due to variability of RSA key generation time (at least by standard techniques), some passphrases/keys will require more time than others when deciphering or signing.




No, it is not currently possible that a public key of a traditional public-key cryptosystem (not based on communication with some server) can be (re-)generated from something that a typical human is willing to memorize (perhaps, 80 bit worth of entropy, about 24 digits, or 3 phone numbers), much less from a passphrase a typical human can choose and no other information.

In RSA with $n$-bit modulus, we can reduce the public key to about $n/2$ bits with a good argument that it does not reduce security, or to $n/3$ bits with no argument that it reduces security (see this question), but apparently not much further. Other public-key cryptosystem (like ECDSA) have a more compact public key for equivalent security, but it is still several times above that 80-bit limits, thus impractical to memorize, and even painful to key-in from paper. I have strong doubts that we can ever have a reasonably secure public-key cryptosystem with a public key less than 160 bits.