
RSA versus DSA
I was just having a play with SSH and I came across the option to generate RSA or DSA keys. What is the difference between these two options?
Also, It was my understanding that this made it unnecessary to type my password. I specified a passphrase and know it asks for that one all the time. Is this normal behaviour?
Can you change the passphrase because I chose a loooong one :)
Cheers

RSA and DSA are two different algorithms. RSA can be used both for encrypting and signing, while DSA can only be used for signing. I think DSA is considered more secure if you just want to sign stuff, but I'm not sure about that.
Indeed, it is normal behaviour for it to ask for the passphrase every time. The passphrase is the key for the symmetric cipher that the key is encrypted with, so SSH can't decrypt the key for usage if you don't specify the passphrase. You can change the passphrase with "sshkeygen p". You can even choose not to have a passphrase, which is convienent for jumping between computers without using a password. Of course, it's bad if someone would get your private key, since they would be able to do the same, but as long as you keep your secret key in a safe place and unreadable for other users than yourself, you're safe.

The difficulty of cracking RSA and DSA with identical key lengths are the same. RSA keys are not allowed to be exported out of the US which makes DSA preferrable for ssh keys if you want to be a law abiding citizen.

Is that it? But that can't be, right?
CERT uses an RSA key for PGP message signing, and I downloaded it from here, with no warning from their site. So can that really be?

You need to get a license from the US government to be able to export RSA to other countries but they just recently made a change to the law on 61703 which states that you can export it for personal use to any country not listed(Cuba, Iran, Iraq, Libya, North Korea, Serbia, Sudan, Syria, and some others).

There you see... I had no idea.
Can DSA be used for encryption? I think I read somewhere that DSA only could be used for signing, but seeing that most PGP/GPG keys are DSA keys, that suddenly sounds rather improbable.
I need to read up on my cryptography, it seems.
By the way, there's something I've been wondering. Would you happen to know why countries like France and Russia have illegalized strong encryption (if they define that by lengthy keys or anything else I don't know, but anyway...)? It seems pretty stupid to me. Why would the government want to limit people's ability to use cryptography, especially in democratic nations?

DSA(Digital Signature Algorithm) can be used for ecryption but I heard it is extremely slow. DSA is based off of ElGamal which is an asymmetric key encryption algorithm. When the NSA released DSA, they didnt intend for it to be used for encryption but someone hacked it and was able to use it for encryption. About the pgp keys, I thought most were RSA or DH/DSS. Atleast I do know that those are the only algorithms used by the US govt for pgp keys. But we are currently moving away from pgp and using PKI instead which uses 4096bit keys(PKCS #1(padding scheme) SHA1(signing alg) with RSA encryption). Any key greater then 56bit is considered strong encryption. I imagine they made that law so they could intercept and crack encrypted data if they had to. That is only a guess though, I didn't know they even had a law like that. Oh yeah only reason I know this stuff is cause I use this everyday at work :)

I just looked at gpg and it only uses DSA for signing and ElGamal for encryption.

That explains a lot, I guess.
I don't know which is really the most common PGP key type, but on my keyring, only two keys are RSA and the rest are DSA.
I think that encryption is really important, and it captivates me a lot. Especially asymmetric encryption... it has to be on the top list of the coolest inventions through all time. =) The problem is that I don't know half as much about it as I would want to. On the other hand, that's understandable, since I don't really have any use for it on a regular basis. I just find the concept so attractive.

For clarity's sake...
Be it a bit late, I would like to clarify a few concepts
proposed in this thread. First, I'll start off by pointing
out the two main differences between RSA and DSA.
This lies simply in the problem of which renders their
assumed security. I'll also spare any mathematical
notation, aside from a handful of variables, unless
asked to elaborate otherwise.
Obviously, most of us know that the RSA algorithm relies
on the difficulty of factoring large primes for its assumed
security. I use the word "assumed" because it is just that.
There is no inherent proof that one must factor n, in
order to deduce m from c and e. This, however, is our best
cryptanalytic viewpoint thus far. Consider RSA's security
a mere conjecture. Perhaps a safe one, but still volatile.
It was pointed out that DSA is based off of the ElGamal
algorithm. To be more exact, it is modeled from the quite
similar ElGamal and Schnorr schematics. These
algorithms are based upon a much different problem.
This problem being, calculation difficulty in regards to
discrete logarithms in a finite field. One thing to keep
in mind of  DSA isn't derived from the aforementioned
algorithms; it is only similar in mathematical approach.
DSA may be the official standard, but RSA has always
been the de facto king of asymmetry. My main argument
is that the construction of DSA was private, thus minimizing public
analysis, whereas RSA has seen many, many solid years of
cryptanalysis. It's faster than DSA and gives us the confidence
of such triedandtrue robustness.
Now for the miscellany.
DSA can in fact be used for encryption, but is not intended
for this, apparently. I won't go into this, but this is just to
confirm any speculation. Either way, I don't recommend it,
for various reasons. If you can't or don't want to use RSA
at all, then encrypt via ElGamal and sign with DSA. It's the
second most common configuration, in many applications.
Also, GnuPG can use RSA for signatures; not just DSA.
"The difficulty of cracking RSA and DSA with identical key lengths
are the same"  another conjecture of which isn't exactly
accurate, but isn't worthy of a discussion for this particular
thread.
Last but not least, I saw the phrase stating that any key larger
than that of 56 bits is secure. Highly false, this statement. I
have a very strong, and rationaleinduced, opinion on this very
thing. Regardless of what you've been told, what hype suggests,
or what the majority of utilities implement by default, there is
an important "rule" that one should follow  2n for n.
This simply means, to maximize your chance of actually
reaping n bits of security, use a 2nbit key. I won't go
off into the mathematical spree of this reasoning, but I will point
you to my article of which explains it. Just mosey on over to:
Just How Secure ARE Those 128bit Keys?
Now, to why I believe that statement to be "highly false."
To summarize my take on it  use 256bit keys at minimum to
best assure yourself of 128bit security, of which is generally
regarded as the most conservative minimum. Don't be fooled,
however. Not just everything is better than 56bit. Take 64bit,
for example, of which was recently exhausted via distributed.net's
RC564 challenge. Many cryptographers will agree than 80 to 90
bits is just above the assumed "safefrombruteforce" mark, in
most predictions of computing growth. Disregard that assumption,
though, as it just isn't worth risking. Besides, as 128bit keys will
render approximately equal setup times as those of 64bit keys 
why go any smaller?
In all actuality, it isn't even so much brute force that worries us,
in many cases, but collision attacks, which call for the 2n for n
guidelines. You may read more pertaining to that, via the
supplied link.
Even then, I'm willing to bet that the majority of users do not
understand the concept of proper key creation and management.
'tis a shame and the one facet of cryptography that isn't taught
enough. Aside from establishing the importance of flawless
implementation, this is one of the more common reasons that
many cryptosystems fail.
But I suppose all of this lies in your interpretation of security. As
civilians, it isn't likely that we'll face cryptanalytical attacks or such
a hefty key exhaust as that of which would require immense power
from the civilian world. It isn't impossible, by any means, but let's
face it ... in terms of what is practical and likely to happen, even
somewhat small key sizes will suffice. But that's another ball game.
The more important issue is theoretical, longterm security. The
better choice is 256bit, right now. It makes perfect sense to those
who understand the cryptanalytical theory. Given a read of the link
I provided, that should wellprepare you for understanding just that.
Well, that concludes a cryptanalyst's opinionated rant. Pardon me.
Cheers, fellas.