The standard Bitcoin client in version 0.6 apparently introduces compressed keys.
What are they? Are there any drawbacks to using them? Any incompatibilities with older software? Reductions in cryptographic strength?
A compressed key is just a way of storing a public key in fewer bytes (33 instead of 65). There are no compatibility or security issues because they are precisely the same keys, just stored in a different way. The original Bitcoin software didn't use compressed keys only because their use was poorly documented in OpenSSL. They have no disadvantages other than that a little bit of additional computation is needed before they can be used to validate a signature.
If you think of a public key as a point somewhere along a giant letter U, an uncompressed key is the x and y coordinates of the point. A compressed key is how high up on the U the point is along with a single bit indicating whether it's on the left or right side. As you can visualize, they both encode precisely the same thing, but the compressed form requires half as much space plus one bit. (Of course, they're really points on elliptic curve secp256k1, but the concept is the same.)
Format (private keys):
Obtained from the Bitcoin developer mailing list:
It may help to break the fields apart.
04 4f355bdcb7cc0af728ef3cceb9615d90684bb5b2ca5f859ab0f0b704075871aa 385b6b1b8ead809ca67454d9683fcf2ba03456d6fe2c4abe2b07f0fbdbb2f1c1 03 [could be 02] 4f355bdcb7cc0af728ef3cceb9615d90684bb5b2ca5f859ab0f0b704075871aa [discarded value can be computed from above value]
There is more detail omitted above. The 03 can be 02 because the discarded value has to be derived from the preserved value and one extra bit of info is needed. That is because there are two roots [plus and minus] when taking a square root.
a good explanation is available in How can I test if a bitcoin address is compressed or not?
More specifically, a public key in Bitcoin is a pair integers (x,y). For uncompressed public keys, these integers are encoded as 256-bit unsigned big-endian ints, concatenated together, and then prepended with a single 0x04 byte. The result is 65 bytes long.
For compressed public keys, only the x coordinate is encoded (like above, as 256-bit unsigned big-endian int). It turns out that the y coordinate can only be one of two values, one even and one odd. Instead of prepending a single 0x04 byte, a single 0x02 or 0x03 byte is prepended depending on y's value (0x02 for even, 0x03 for odd). The result is 33 bytes long.