Digital Signature Algorithm (DSA) intuition and its relation to RSA

Question

I already understands how to use the RSA algorithm to sign messages, as you can see in this post of mine. Searching about elliptic curves, I found a general algorithm called Digital Signing Algorithm. I can't find any intuition on that, only proofs that it works, but I'm unable to get the idea of those proofs. Is RSA a specific case of DSA? Which mathematical principles does DSA uses? Like in my post, can you develop the ideia?

Answer 1

RSA, as you know, is based on an integer modulus $n = pq$ (public), composed of two primes (secret) and a public encryption exponent $e$ and a secret decryption exponent $d$. You can both encrypt messages using $e$, and sign messages using $d$ (and verify them using $e$ again). The security is based on the fact that we cannot (in egenral) extract $e$-th roots modulo a number $n$ of the form $pq$, where $p,q$ are distinct primes. And if we could factor $n$, then we could also extract those roots, so it's (secondarily) based on the hardness of factoring such $n$.

But we also have the discrete logarithm problem, based on a (large) subgroup of all non-zero integers modulo a public prime $p$, given by a public generator $g$. Here the hard problem is that given $g^x \pmod p$, it's generally hard to find $x$ (the discrete logarithm problem DL). The Diffie-Hellman (DH) key-exchange is based on this (the exact security depends on a somewhat stronger assumption than that DL is hard, the DH assumption). Note that DH by itself is no encryption, but the basis for a key-exchange protocol, where both parties participate to compute a common secret.

Subsequent work by El-Gamal and others have used the DH idea to build a crypto system (the El-Gamal crypto-system) and a signature scheme; actual several ones: El-Gamal has one, and DSA is another, which is more common and standardised by NIST.

Of course, we can do this in any group where the DL problem is supposed to be hard, so we get elliptic curve variants as well: ECDH-El-Gamal and ECDH-DSA, which have smaller parameters, and are more efficient.

So esentially they are based on different problems and assumptions. DH is actually older but as a crypto-signature scheme RSA is.