Digital Signatures
1/18
What do we expect from a “signature?”
To certify, to a recipient of a document, that a concrete entity has produced the document
and/or agrees to be bound by the contents of a document.
2/18
What do we expect from a “signature?”
To certify, to a recipient of a document, that a concrete entity has produced the document
and/or agrees to be bound by the contents of a document.
Couldn’t this be done by a MAC? Yes, but we expect more from a “signature”.
2/18
What do we expect from a “signature?”
To certify, to a recipient of a document, that a concrete entity has produced the document
and/or agrees to be bound by the contents of a document.
Couldn’t this be done by a MAC? Yes, but we expect more from a “signature”.
To certify, to a recipient of a document and any other 3rd party, at any time after
producing the signature, that a concrete entity has produced the document and/or agrees
to be bound by the contents of a document.
The additional property is called non-repudiation: the signatory cannot deny signing the
document.
2/18
Digital signature scheme
Definition 1
A digital signature scheme over (Kp, Ks, M, Sg) is a triple Ds = (Gen, S, V ) where
• Gen is an input-less randomized algorithm which produces a pair of keys
(kp, ks) ∈ Kp × Ks. Possible outputs of Gen are called valid keys for Ds, and we
denote by V(Gen) ⊆ Kp × Ks the set of all Ds’s valid keys;
• S : Ks × M → Sg is a (possibly randomized) signing algorithm s.t.
• V : Kp × M × Sg → {true, false} is a deterministic verification algorithm such that
∀m ∈ M ∀(kp, ks) ∈ V(Ds) : V (kp, m, S(ks, m)) = true with probability 1.
Secure digital signatures = resistant against forgery.
3/18
Levels of security of digital signatures
The security level depends on forger’s intent:
• key recovery
• selective forgery
• existential forgery
... and forger’s capabilities:
• passive adversary
• chosen message attacks
• adaptive chosen-message attacks (correspond to CPA security of ciphers)
4/18
Existential forgery attack game for digital signatures
Let Ds = (Gen, S, V ) be a dig. signature scheme over (Kp, Ks, M, Sg). An existential forgery
attack game between the challenger and the adversary A proceeds as follows:
• The challenger generates a pair (kp, ks) using Gen. The public key kp is revealed to the
adversary while ks is kept secret.
• The adversary selects a number of rounds N for which the game will be played.
• In each round i:
• The adversary computes a message mi ∈ M and sends it to the challenger.
• The challenger computes σi = S(ks , mi ) and send σi to the adversary.
After the final round, the adversary computes a tuple (m, σ) ∈ M × Sg s.t.
m ̸∈ {m1, . . . , mN }. The adversary wins the game if V (kp, m, σ) = true.
The advantage of A against Ds is the quantity
ADVSig(Ds, A) = P(A wins the e.f. game).
Ds is ε-secure if ADVSig(Ds, A) ≤ ε for every efficient adversary A. 5/18
EF attack game for digital signatures: picture
6/18
Role of hashing in digital signature schemes
Since asymmetric crypto primitives are less efficient than symmetric ones, it is preferable to
apply the algorithms only on relatively short messages.
7/18
Role of hashing in digital signature schemes
Since asymmetric crypto primitives are less efficient than symmetric ones, it is preferable to
apply the algorithms only on relatively short messages.
This is why practical signature schemes do not sign the original messages but hashes of these
messages, computed by collision-resistant hash functions.
In some literature, this is omitted from the description of the algorithms, i.e. it is assumed that
M is a hash space of some collision resistant hash functions.
One can show that this use of signatures is secure in the sense that if Ds is a d.s. scheme
operating over some general message space M, then a scheme Dsh which applies a
collision-resistant hash function h before signing and verifying the message is also secure. 7/18
Generic construction: Full domain hash
Recall that a trapdoor function f : Kp × X → Y is specified by two polynomial-time
algorithms: Fwd and Inv satisfying:
• given m ∈ X and kp ∈ Kp, the algorithm Fwd computes f (kp, m), and
• given c ∈ Y and ks ∈ Ks, the algorithm Inv computes an element of X s.t. for all m ∈ X,
and all valid key pairs (kp, ks) it holds
Inv(ks, f (kp, m)) = m.
Moreover, when given c ∈ Y , without the knowledge of ks, it is hard to compute m ∈ X s.t.
f (kp, m) = c.
8/18
Generic construction: Full domain hash
Recall that a trapdoor function f : Kp × X → Y is specified by two polynomial-time
algorithms: Fwd and Inv satisfying:
• given m ∈ X and kp ∈ Kp, the algorithm Fwd computes f (kp, m), and
• given c ∈ Y and ks ∈ Ks, the algorithm Inv computes an element of X s.t. for all m ∈ X,
and all valid key pairs (kp, ks) it holds
Inv(ks, f (kp, m)) = m.
Moreover, when given c ∈ Y , without the knowledge of ks, it is hard to compute m ∈ X s.t.
f (kp, m) = c.
Full domain hash: use the secret key operation Inv(ks, ·) for signing and the public-key
operation Fwd(kp, ·) for verification.
8/18
Full domain hash: pseudocode
When using a trapdoor permutation to construct a d.s. scheme (Gen, S, V ), the key generation
algorithm is the same as for the corresponding encryption scheme, while signing and
verification are performed as follows:
Algorithm 1: Signing using the secret-key operation Inv(ks, ·) and hash function h
Input: Secret key ks ∈ Ks, message m ∈ M
Output: S(ks, m)
return Inv(ks, h(m))
Algorithm 2: Verification using the public-key operation Fwd(kp, ·) and hash function h
Input: Public key kp ∈ Kp, message m ∈ M, signature σ ∈ Sg
Output: V (kp, m, σ)
if Fwd(kp, σ) = h(m) then return true;
else return false;
9/18
Full domain hash: pseudocode
When using a trapdoor permutation to construct a d.s. scheme (Gen, S, V ), the key generation
algorithm is the same as for the corresponding encryption scheme, while signing and
verification are performed as follows:
Algorithm 1: Signing using the secret-key operation Inv(ks, ·) and hash function h
Input: Secret key ks ∈ Ks, message m ∈ M
Output: S(ks, m)
return Inv(ks, h(m))
Algorithm 2: Verification using the public-key operation Fwd(kp, ·) and hash function h
Input: Public key kp ∈ Kp, message m ∈ M, signature σ ∈ Sg
Output: V (kp, m, σ)
if Fwd(kp, σ) = h(m) then return true;
else return false;
The use of hash function is essential for security here! 9/18
Hash is essential in FDH
10/18
Digital signatures from trapdoor functions: security theorem (informal)
Theorem 1
Let f be a trapdoor function and h a collision-resistant hash function. Then the fulldomain
hash derived from f and h is secure.
11/18
RSA signature scheme
• Instantiates the generic construction with Fwd(kp, m) = me
(mod N) and Inv(ks, c) = cd
(mod N).
• First widely adopted digital signature scheme.
• In practice, often the PKCS1 form is used:
However, if implemented badly, it is susceptible to a variant of the Bleichenbacher’s attack.
12/18
DL-based digital signatures: Schnorr’s signature
• Developed from Schnorr’s authentication protocol via Fiat-Shamir trick (see next lecture).
• Strong security guarantees and efficiency. Not widely adopted due to patent protection at
time of standardization.
• Depends on the use of ephemeral key which must be unique and randomly chosen for each
signed message.
• Can be formulated over an arbitrary group. In the following, we have a group G of order p
and some generator b of a cyclic sub-group of prime order q. I.e., the secret key is
ks = (G, b, q, k) and the public key is kp = (G, b, q, bk
) for some k ∈ {0, . . . , q − 1}.
13/18
Schnorr’s signature
Algorithm 3: Signing in Schnorr’s signature with a hash function h mapping inputs into Z×
q
Input: Secret key ks = (G, b, q, k), message m ∈ M
Output: SSchnorr(ks, m)
r ← sample randomly from Z×
q ;
z ← k · h(m || br
) + r (mod q);
return (br
, z)
Algorithm 4: Verification in Schnorr’s signature
Input: Pub. key kp = (G, b, q, κ = bk
), message m ∈ M, signature (ρ, z) ∈ Sg
Output: VSchnorr(kp, m, (ρ, z))
v ← bz
· κ−h(m || ρ)
;
if v = ρ then return true;
else return false;
14/18
DSS and DSA
• Digital signature standard (DSS) adopted by NIST as a US federal standard in 1994.
• Further revisions published subsequently, the latest in 2013.
• Contains a specification of Digital signature algorithm (DSA), a digital signature scheme
based on the discrete logarithm problem in Z×
p .
15/18
DSA
DSA key generation (high-level) for M-bit modulus length (recommended 3072) and L-bit
signature length (recommended 256):
• Randomly select an L-bit prime q.
• Randomly select an M-bit prime p s.t. q | p − 1 (DSS recommends concrete algorithms
for this selection).
• Compute a generator g of Z×
p .
• Compute a generator b of a sub-group of Z×
p of order q by putting b = g
p−1
q . The
element b will serve as the base of the discrete logarithm in the scheme.
• Select a random number k ∈ {1, . . . , q − 1}.
• Put κ = bk
(mod p).
The public key is (p, q, b, κ), the secret key is (p, q, b, k).
16/18
DSA (pseudocode)
SHA-256 is used as h. If hash size < L, only leftmost L bits of the hash are taken.
Algorithm 5: Signing in DSA
Input: Secret key ks = (p, q, b, k), message m ∈ M
Output: SDSA(ks, m)
r ← sample randomly from {1, . . . , q − 1};
ρ ← (br
(mod p)) (mod q);
z ← r−1
· (h(m) + k · ρ) (mod q);
return (ρ, z)
Algorithm 6: Verification in DSA
Input: Pub. key kp = (p, q, b, κ = bk
(mod p)), message m ∈ M, signature (ρ, z) ∈ Sg
Output: V (kp, m, (ρ, z))
compute z−1
(mod q) and µ = bh(m)
(mod p);
v ← (µz−1
· κρ·z−1
(mod p)) (mod q);
if ρ = v then return true;
else return false;
17/18
ECDSA
• A variant of DSA with elliptic curves. Also standardized by NIST.
• Works exactly as DSA, but with operations (mod p) replaced by the operations in the EC
group.
• The only difference: how to get from a member x = br
of the group G an exponent: a
number ρ in {1, . . . , |G|}:
• In DSA, x was an integer, so we just performed ρ ← x (mod q).
• In ECDSA, x is a point (x1, x2) where the coordinates are integers modulo some prime. We
put ρ ← x1 (mod |G|). If, by coincidence, ρ = 0, we need to sample a new x.
• In both DSA an ECDSA (and in Schnorr), it is important that r is indeed random,
unpredictable, and not re-used (guaranteed with high probability if random): otherwise,
the signature scheme is completely insecure (e.g. the PlayStation 3 exploit).
18/18