Is the RSA private key useless without the password?

Question

I notice whenever I generate a new gpg key (using pgp) I always have to assign a password to it, which makes perfect sense. But if I'm not mistaken, gpg is based on prime numbers. How is this password integrated into the private key? And if someone stole a private key but didn't know the password, would all encrypted data still be safe?

I'm assuming the main problem is brute forcing that password is trivial compared to brute forcing the private key? If this is the issue, then would having a sufficiently long enough password ensure that your data is safe even if you private key is compromised?

Possible duplicate of [Security of passphrase-protected private key](http://security.stackexchange.com/questions/5085/security-of-passphrase-protected-private-key) — techraf, Apr 03 '16 at 22:43
I don't think so @techraf. This question has some basic misconceptions/questions about how GPG works (eg: 'How is this password integrated into the private key?') that aren't answered in that question. Though it is a good reference. — Neil Smithline, Apr 03 '16 at 22:45
I would really like to know the technical aspects of how the password is integrated into the private key. Please let me know if you would like me to edit the title and body to emphasize this — user3256725, Apr 03 '16 at 22:47
@NeilSmithline I think reading the answers under the other question would clear the misconceptions. — techraf, Apr 03 '16 at 22:47
I think @NeilSmithline is right that the OP is asking for an explanation of the fundamentals, but Neil's answer kinda skips all the good stuff. I'll try to post a deeper answer. — Mike Ounsworth, Apr 04 '16 at 14:11

score 7 · Answer 1 · edited Mar 17 '17 at 10:46

You seem to be asking for a fundamental understanding of how GPG generates keys, and what the role the password plays in this process. I will give some background, and then answer your direct questions at the end.

The short answer is: each time you need to access your RSA private key, your password is used as a "seed" to re-generate the AES-256 key that you need to decrypt your RSA private key (keep reading for details).

RSA Key Generation

When generating an RSA key, you want it as random as possible, pulling randomness from the operating system's cryptographic random number generator (/dev/random on linux, for example). According to wikipedia/RSA_(cryptosystem):

A cryptographically strong random number generator, which has been properly seeded with adequate entropy, must be used to generate the primes p and q

Protecting the Key File

As discussed in this question, gpg uses its default symmetric cipher to encrypt the RSA private key before it is saved to a file. Gpg's default symmentric cipher used to be 3DES, but is now AES-256. This is also configurable if you would rather use a different cipher (the linked question has a list of available ciphers).

Role of the Password

In order to use a symmetric cipher like AES-256 to encrypt your RSA private key, you need an AES-256 key. Oh no! Recursion! How do you store that key in a safe way? The answer is: you don't - you generate each time you need it using the password as a seed. Specifically, it uses the PBKDF2 algorithm to stretch your password into a full-length, random-looking AES-256 key. Since this AES-256 key is never saved anywhere, your password is essentially the gate-keeper that unlocks your RSA key.

Why not just stretch the password directly into an RSA key?

I'll throw this here just because it's an obvious question.

Symmetric ciphers like AES-256 or 3DES have no structure or properties for their keys, literally any string of bits of the correct length can be used as a key (256-bits and 168-bits respectively).

For public key ciphers (RSA, Elliptic Curve, new post-quantum ciphers like McEliece, NTRU, etc) the keys needs to have very a specific mathematical structure. For example, with RSA the private key must consist of two primes numbers and several numbers derived from them, so if you stretched your password up to the right length and tried to use that as an RSA key, 99.99...% of the time it would be an invalid RSA key (ie the resulting bits would not be two prime numbers and the related values).

Answering your direct questions:

1.

And if someone stole a private key but didn't know the password, would all encrypted data still be safe?

I'm assuming you mean "if someone stole the private key file but didn't know the password". Yes, your data is safe. All they have is an encrypted file, they have no way of extracting the private key from that.

However, if they manage to get your decrypted private key (say from a memory dump of your running computer) then you're sunk, the password is only used to protect the private key while it's on disk.

I'm assuming the main problem is brute forcing that password is trivial compared to brute forcing the private key?

Yes, if an attacker gets their hands on your encrypted key file, it will take them fewer guesses to guess your password than to guess your RSA key directly.

Some numbers

Exact estimates of the number of guesses required to break RSA-n, where n is 1024, 2048, 4096, etc, is hard to find, keylength.com is probably the closest you'll get, so take the numbers below with a huge grain of salt.

Let's say that a 1024-bit RSA key gives you (according to keylength.com) 72 bits of security, meaning that an attacker would have to make, on average, 2⁷² guesses to crack your RSA key. By comparison, a 12-character password using numbers, uppers and lowers gives 71.4 bits of security [link to calc] (an attacker has to do ~2^71.4 guesses) - assuming that it's completely randomly generated, if it's full of dictionary words then it's much much weaker than 71.4 bits.

A 32-character password using all 95 printable ascii characters gives you ~ 210 bits of security [link to calc], almost as much as a fully-random AES-256 bit key. While an RSA-8192 key only gives 136 bits of security, so with a long enough and random enough password, your password can actually be stronger than the RSA key it's protecting (really?!).

score 4 · Answer 2 · answered Apr 03 '16 at 22:49

The password is not part of the key, but used to encrypt the private key. Technically, the password is input to a key stretching algorithm whose output is used to encrypt the private key.

The strategies for securing the password are:

Make the password long and strong.
Slow down the key stretching algorithm as much as you can tolerate. This answer describes some command line arguments to GPG that you can pass to achieve this.

This statement:

If this is the issue, then would having a sufficiently long enough password ensure that your data is safe even if you private key is compromised?

If your private key is compromised, it's game over. But I think you are asking what happens if a file containing an encrypted copy of your private key is compromised. In that case, the password must be cracked for the user to recover the private key. That is why a strong password and a slow key stretching operation are helpful.