Digital signatures, DSA and RSA

Why MACs cannot give non-repudiation or scale to many parties, how a digital signature fixes both with public-key cryptography, and the RSA and DSA approaches to building one.

State the three limitations of MACs that digital signatures solve: no third-party proof, no scaling, no non-repudiation.
Trace the generic digital signature process from hashing through generation to verification.
Describe the RSA signature approach and reproduce its signing and verification steps.
Describe DSA at the high level the lecture expects: signature-only, global parameters, and the (r, s) signature pair.

16 min read

Intuition

A MAC gives integrity and origin authentication, but it depends on sender and receiver already sharing a secret key. That shared key is also its limit: since Bob could have computed the exact same MAC Alice did, nobody outside the two of them can tell which of them actually sent a given message. A digital signature replaces the shared secret with a private key only the sender holds, which changes what can be proven.

Mechanism

MACs run into three specific limits. They cannot prove authorship to a third party: a judge or outside verifier has no way to distinguish Alice’s MAC from one Bob could have forged himself, since both know the same key. They do not scale: if Alice wants to talk securely with 1000 people, she needs 1000 separate shared keys. And they give no non-repudiation: Alice can later deny sending a message, and there is no way to prove otherwise.

Digital signatures solve all three by using asymmetric, public-key cryptography instead of a shared secret. Alice signs with her own private key; anyone can verify with her public key. No shared secret is needed, a third party can verify the signature independently, and Alice cannot deny having signed it.

Mechanism

The generic process. Suppose Bob wants to send Alice a message and does not care about its confidentiality, only about proving he sent it. Bob hashes the message with a secure hash function such as SHA-512, then feeds that hash and his own private key into a signature generation algorithm, producing a short block: the signature. Bob sends the message and the signature together.

Alice computes the hash of the received message herself, then feeds that hash and Bob’s public key into a verification algorithm. If it reports the signature valid, two things follow: Alice is assured the message was signed by Bob, since only Bob holds the private key that could produce a signature verifiable under his public key, and she is assured the message’s integrity, since nobody without that private key could alter the message and still produce a hash that verifies correctly.

Threat

Every guarantee above depends on Alice being certain the public key she is using genuinely belongs to Bob. A forged or substituted public key breaks all of it: an attacker who gets Alice to trust their own public key as “Bob’s” can sign messages that verify successfully, with none of Bob’s actual involvement. This is the public key authentication problem, and it is solved later in the unit through PKI and digital certificates, not addressed further here.

Mechanism

Two approaches build a digital signature this way. Both use SHA for hashing.

RSA approach. The message is hashed with SHA to produce $h(m)$ , and that hash is encrypted with the sender’s private key to form the signature: $E(PR_a, h(m))$ . Both the message and the signature are sent. The receiver computes their own $h(m)$ from the received message, decrypts the received signature with the sender’s public key, and checks the two match. Because RSA is a general-purpose public-key scheme, it can also be used for encryption and key exchange, not only signing.

Formula

RSA signature generation

\text{Signature} = E(PR_a, H(M))

$M$: the message being signed
$H(M)$: the message's secure hash, e.g. under SHA
$PR_a$: the sender's (Alice's) private key
$E$: RSA encryption, here used to produce the signature rather than for confidentiality

Formula

RSA signature verification

D(PU_a, \text{Signature}) \stackrel{?}{=} H(M)

$PU_a$: the sender's public key
$D$: RSA decryption, applied here to the received signature
$H(M)$: the verifier's own hash of the received message

The signature is accepted only if decrypting it with the sender's public key reproduces the verifier's own computed hash exactly.

Mechanism

DSA (Digital Signature Algorithm) approach. Proposed in 1991 and published by NIST as FIPS 186, DSA uses SHA but provides only the signature function: unlike RSA, it cannot be used for encryption or key exchange.

DSA generates a hash code from the message, then feeds that hash, a fresh random number $k$ generated for that one signature, the sender’s private key $PR_a$ , and a set of parameters shared by a whole group of communicating principals (a global public key $PU_G$ ) into a signature function. The result is two values, $r$ and $s$ : the signature. On receipt, the hash code of the incoming message is recomputed, and it is fed together with the signature into a verification function that depends on $PU_G$ and the sender’s own public key $PU_a$ . Verification succeeds when the function’s output equals $r$ . Only someone holding the matching private key could have produced a signature that verifies this way.

Exam detail

The notes flag this directly in their own practice quiz explanations for the DSA questions: DSA was not covered in detail in lecture, and the exam expects only the high-level ideas of DSA, not a full derivation. That means: DSA is signature-only, it needs a global shared parameter set $PU_G = (p, q, g)$ , a private key $x$ with $0 < x < q$ , a fresh random $k$ per signature, and it produces a signature pair $(r, s)$ . Deriving how $r$ and $s$ are actually computed from those inputs is beyond what this unit tests.

Compare

General-purpose: the same algorithm signs, encrypts, and does key exchange. Signing encrypts the message hash with the sender’s private key; verifying decrypts the signature with the sender’s public key and compares it to a freshly computed hash.

Signature-only: cannot encrypt or exchange keys. Needs a group-wide set of global parameters plus a fresh random number for every signature, and produces a two-part signature (r, s) rather than an encrypted hash.

Pitfall

A slide table headed “Digital Signature Algorithm Parameters” gives Alice and Bob each computing $X = g^a \bmod p$ and $Y = g^b \bmod p$ , exchanging them, and both arriving at $k = Y^a \bmod p = X^b \bmod p$ . That is a Diffie-Hellman-style key exchange, not DSA’s signature generation, it never produces the $(r, s)$ pair DSA actually signs with. This looks like the slides mixing in unrelated content under a DSA heading rather than a genuine part of the DSA algorithm, and it is not reproduced here so as not to teach a wrong mechanism for how DSA signs a message.

Recall

Alice sends a message to Bob with only a MAC attached, no signature. Bob is completely convinced it came from Alice. Can Bob prove that to a judge?

No. Since Bob also knows the shared MAC key, he could have produced that exact same MAC himself. A judge, or any outside third party, has no way to distinguish a MAC Alice actually sent from one Bob could have forged. This is precisely the non-repudiation gap a digital signature closes, by replacing the shared key with a private key only Alice holds.

Source

Week 6 Notes PDF