Deterministically generate a RSA public/private key pair from a passphrase (with sufficient entropy)?

Question

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.)

Answer 1

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 Argon2, Scrypt (or the better known but less not 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.

Answer 2

i personally have just been implementing:

i create an "extended hash" of multiple digests of sha512 (feeding the password in the hash object, collecting the digest each time to append to our result. You could do this or use a hash that supports different lengths like blake2 (but it cannot be salted!).

so we want a 2048 bit private key, we create therefore 2048 bits (256 bytes) or hash data from our password

we turn this into TWO large numbers, 1024 bits each are converted to the long/int whatever where we won't loose any information (python has infinite precision)

so we now have two huge numbers, for each of them i hunt for the first valid prime from their position by incrementing them and checking if the number is prime.... on average it seems it can take about a thousand checks to find that prime... entirely acceptable

with regard to the safety of this, (we have about 2^512 bits of entropy in a 1024 bit number!... this means that on average p and q will be 2^512/2 values apart. log(2**512/2,10)=153.8 .... so to put this in perspective, in decimal this number has about 153 digits

the concern might have been the same primes would turn up for different passwords, or the spacing of the primes (of which we have no theorems to predict).... but with such a ridiculous average distance between p and q i can't really see the issue

the way it's insecure is it uses a password for a RSA, which can't possibly be as secure as AES as it has to show some of it's information, combining brute forcing passwords with this might compromise security.

HOWEVER, I have seen some similar ideas about and it's something like if you could write your key on paper etc, be able to tell it down a telephone line... many of these sort of things, could, especially for the IT illiterate, in SOME situations, it might improve security. I was sort of imagining niche uses like I could enter a pin into a digital radio to authenticate my identity (they'll never see that information, but they will be able to confirm the pin hasn't changed)