Can a public key have a different length (encryption) than the private key?
I have a 1024 bits private key, and use it to generate a public key. Does that automatically mean that my public key also has 1024 encryption? Or can it be of a lesser encryption size? (512, 256...)
PS: What i'm mostly interested in, and talking about, is the size of the modulus ("n") in RSA keys. The size is typically 1024 or 2048 bits. But I'm glad to see that this sparked a discussion, and all this is feeding my interest in cryptography.
Answer
This depends on the encryption algorithm and on what precisely you call public/private key. Sometimes it's possible to use a different size in RAM compared to serialization on disk or the network.
RSA
An RSA public key consists of a modulus n and a public exponent e. We usually choose a small value for e (3, or 65537 are common). The size of e has little influence on security. Since e is usually less than four bytes and n over a hundred, the total size is dominated by the modulus. If you really want to, you can fix e as part of your protocol specification so there is only n to store.
An RSA private key can be represented in different forms, but typically we store the values p, q, dp, dq, e, d, n, InvQ. Their combined size is larger than the public key. Most of these aren't strictly required, but it's convenient to have them available instead of regenerating them. Regenerating all of them given e, p and q is straight forward.
When we talk about key-size in the context of RSA we always mean the size of the modulus, ignoring all the other elements. This is a useful convention, since this is the only value that affects security. A typical size for n is 2048 bits.
Finite field crypto (Diffie-Hellman, DSA, etc.)
The private key is a scalar twice the size of the security level. A typical value is 256 bits.
The public key is a group element, which is much larger than the private key. A typical value is 2048 bits.
So with finite field crypto the public key is much larger than the private key.
Elliptic curves
The private key is a scalar twice the size of the security level. A typical value is 256 bits. This part is identical to finite field crypto.
The public key is a group element. There are two forms of serializing such an element. The compressed form is slightly larger than the private key (a couple of bits at most). The uncompressed form is about twice the size of the private key. A typical value for the compressed form is 256 bits and 512 bits for the uncompressed form.
Private key as seed
When you generate public/private key pairs yourself, you can always store them as seeds for a PRNG. That way they're quite small, 160 bits or so regardless of the scheme you use. The downside of this is that regenerating the natural form of the private key may be expensive. It is required that the method of creating the key pair remains constant.
Fingerprint of public key
Instead of storing the full public key, you can often store only a fingerprint, which is 160 bits or so in size. The downside of this is that it increases the size of the message/signature.
Summary
For some algorithms the size of public and private key are the same, for some they differ, and it is often possible to compress either or both of them at a cost (decompression time or message size).