Digital Signature#

What is a digital signature#

A digital signature is a cryptographic result attached to data that helps a receiver verify three things:

1	2	3
Who sent it	It was not changed	Sender cannot easily deny it
Origin authentication	Integrity	Non-repudiation

Important: a digital signature does not hide the message. Confidentiality comes from encryption, not from the signature itself.

Simple idea: sign with the private key, verify with the public key.

Why we need it#

Without protection, a digital file can be copied, edited, or impersonated in transit. The receiver needs proof of source and integrity.

If there is no digital signature

Anyone can claim “I sent this.”
A message can be modified silently.
The receiver has no easy proof for a third party.

trust is weak

With a valid digital signature

The public key checks the sender’s signature.
Any change to the signed data breaks verification.
It supports accountability in software, email, and documents.

trust can be checked

Building blocks#

#	K	V	ID
Hash function	Private key	Public key	Certificate / PKI
Turns any message into a fixed-size digest. Small changes in the message create a very different digest.	Kept secret by the signer. It is used to create the signature.	Shared with others. It is used to verify a signature.	Binds a public key to an identity so that people know whose key they are using.

Together these components answer two questions: “Did this come from the claimed sender?” and “Has anything changed?”

How digital signatures work#

Hash the message
A hash function converts the message into a short fingerprint.
Sign the hash
The sender uses a private key to sign that fingerprint.
Verify
The receiver recomputes the hash and uses the public key of the sender to check the signature.

Key insight#

The signature is created over a hash, not by encrypting the whole document. That makes signing efficient even for large files.

Verification fails if#

the content changes
the wrong public key is used
the signature was forged

1. Hash
message

2. Encrypt hash
with private
key

3. Send
message
+ signature

4. Decrypt with
public key

5. Compute
message hash
& compare
hashes

If both hashes match, the signature is valid.

Algorithms and common uses#

Common signature algorithms

RSA

Widely taught and widely
deployed

ECDSA

Strong security with smaller
key sizes

EdDSA

Modern design; included in
FIPS 186-5 as Ed25519 /
Ed448 family

Common uses

Software signing

Proves a program or update
came from its publisher.

Signed email

Lets recipients verify sender
identity and tamper detection.

PDF / contract approval

Supports trusted document
workflows and audit trails.

Certificates on the web

Certificates themselves are
digitally signed by a CA.

Limitations and best practices#

Limitations / risks

If the private key is stolen, an attacker can create valid signatures.
Verification only works if the receiver trusts the correct public key or certificate.
A signature proves integrity and origin, but it does not prove the content is true or safe.

Best practices

Protect private keys with strong storage and access control.
Use trusted certificates and check validity / revocation status when relevant.
Choose modern approved algorithms and key sizes.

RSA Signature: Choosing Public and Private Keys#

Choose two prime numbers: $p = 3$ and $q = 11$
Compute $n = p \times q = 3 \times 11 = 33$
Compute $\phi(n) = (p − 1)(q − 1) = 2 \times 10 = 20$
Choose e such that $1 < e < \phi(n)$ and $\gcd(e, \phi(n)) = 1$ . Let $\textcolor{blue}{e = 3}$
Find d such that $e \cdot d \equiv 1 (\bmod \phi(n))$
Here, $3 \times 7 = 21 \equiv 1 (\bmod 20)$ , so $\textcolor{blue}{d = 7}$

Public key

(e, n) = (3, 33)

Private key

(d, n) = (7, 33)

These keys are used for signing and verifying

RSA Signature: Signing the Message#

Let the message hash be $h = 2$
Use the private $key (d, n) = (7, 33)$
Compute signature: $\textcolor{blue}{s = h^d \bmod n}$

$\begin{aligned}s &= 2^7 \bmod 33 \\ &= 128 \bmod 33 \\ &= 29\end{aligned}$

Therefore, the digital signature is $\textcolor{blue}{s = 29}$

Sender uses private key to sign

RSA Signature: Verifying the Signature#

Receiver uses the public $key (e, n) = (3, 33)$
Verify signature $s = 29$ by computing $h' = s^e \bmod n$
If $\textcolor{blue}{h'}$ equals the original hash $h = 2$ , the signature is valid

$\begin{aligned}h' &= 29^3 \bmod 33 \\ &= 24389 \bmod 33 \\ &= 2 \end{aligned}$

Since $\textcolor{blue}{h' = 2 = h}$ , the signature is valid

Signature is

VALID

because

h' = h

2 = 2