The "message" M_{1}⋅M_{2} (mod n) may not make any sense
But still, this violates a security requirement
Problem Number 3: Existential forgery
Suppose Harry picks some S, computes M = S^{e} (mod n) using Blake's public key, and sends the message M and signature S to Alex, pretending they came from Blake
Alex, verifying the signature, will compute M' = S^{e} (mod n) and find M' = M, so the signature verifies
Again, the "message" S^{e} (mod n) may not make any sense
But still, this violates a security requirement
Secure RSA Digital Signatures
Solution to Problem Number 1: Sign the message's digest computed by a cryptographic hash function
Suppose Harry sees Blake compute signature S on message M
If Harry can find another message M' with the same digest as M, then Harry can use S as the signature on M'
But finding such an M' is hard, because the hash function is second preimage resistant
Solution to Problem Number 2, Homomorphic property of RSA:
Suppose Harry sees Blake sign two messages: S_{1} = Sign(Hash(M_{1})), S_{2} = Sign(Hash(M_{2}))
The signature for message M_{1}⋅M_{2} would be Sign(Hash(M_{1}⋅M_{2}))
But Hash(M_{1}⋅M_{2}) ≠ Hash(M_{1})⋅Hash(M_{2}), almost certainly
Therefore, Sign(Hash(M_{1}⋅M_{2})) ≠ S_{1}⋅S_{2}, almost certainly
Solution to Problem Number 3, Existential forgery:
Suppose Harry picks some signature S and computes S^{e} (mod n)
This is supposed to be Hash(M) for some message M
But finding such a message is hard, because the hash function is preimage resistant
Problem Number 4: Hash size
If we use SHA-1, Hash(M) is a 160-bit number
But the RSA signing algorithm wants to exponentiate a 2048-bit number
Signing numbers that always have 1888 high-order zero bits is undesirable
Solution to Problem Number 4: Expand Hash(M) using an encoding function
Alternative encoding function: Probabilistic Signature Scheme (PSS)
M. Bellare and P. Rogaway. The exact security of digital signatures -- how to sign with RSA and Rabin. Advances in Cryptology -- EUROCRYPT 1996, pages 399-416, 1996.
Alternative encoding function: Sponge construction
Use a sponge construction hash function, like Keccak, to hash the message and generate a 2048-bit digest, then sign that
Much simpler than PSS
Not provably secure like PSS -- but no one knows how to attack it either
Problem Number 5: Signature collisions
G. Yuval. How to swindle Rabin. Cryptologia, 3(3):187-189, 1979.
Blake, Alex's boss, asks Harry to write a letter recommending Alex for promotion, which Blake will digitally sign
Harry prepares two letters, the "good" letter recommending promoting Alex, and the "bad" letter recommending firing Alex
Say the hash digest is 64 bits
Say each letter has 32 lines
Harry can either append a space, or not, to each line -- innocuous changes that don't alter the meaning
Harry generates 2^{32} versions of each letter and computes the hash of each
There is a strong possibility that one of the good letters and one of the bad letters have the same hash value, H
Harry gets Blake to sign the good letter whose hash is H (Blake actually signs H = Hash(letter))
Harry puts that signature on the bad letter whose hash is H
Blake thought he signed the good letter, but his signature is valid on the bad letter, so Alex gets fired
Solution to Problem Number 5: Collision resistant hash function
Finding two messages with the same hash is hard, because the hash function is collision resistant
It's much easier to find hash function collisions (2^{n/2} work) than preimages (2^{n} work)
That's why we focus on collision resistance when hash functions are used for digital signatures
Secure hash functions have 160-bit (SHA-1) or longer (SHA-2) digests
Problem Number 6: Duplicate Signature Key Selection (DSKS) attack
N. Koblitz and A. Menezes. Another look at security definitions. Cryptology ePrint Archive, Report 2011/343, September 29, 2011. http://eprint.iacr.org/2011/343
Blake's RSA public key is (n, e); Blake's RSA private key is d
Blake has generated signature S for message M, S = M^{d} (mod n)
Alex verifies Blake's signature by checking whether S^{e} = M (mod n), which it does
Harry wants to generate an RSA public-private key pair such that Blake's signature will verify using Harry's public key also
Harry chooses n' = p'q' such that p'−1 and q'−1 are "smooth," i.e., have many small prime factors
In this case, the discrete logarithm algorithms are efficient
Harry takes S and M and finds the exponent d' such that S = M^{d'} (mod n') -- a discrete logarithm
Harry computes e' such that e'd' = 1 (mod Φ(n'))
Harry's RSA public key is (n', e'); Harry's RSA private key is d'
Alex verifies Harry's "signature" by checking whether S^{e'} = M (mod n'), which it does
So now Alex doesn't know who signed the message, Blake or Harry
Solution to Problem Number 6: Sign Hash(message||public key)
Blake generates signature S = Hash(M||n||e)^{d} (mod n)
Alex checks whether S^{e} = Hash(M||n||e) (mod n)
Now to do a DSKS attack, Harry has to find d' such that S = Hash(M||n'||e')^{d'} (mod n')
But Harry won't know e' until after he finds d', so Harry can't do a DSKS attack
Probabilistic RSA Digital Signatures
Deterministic scheme: Sign(Hash(M))
The same message produces the same signature
Probabilistic scheme: Sign(Hash(nonce||M))
The nonce (or salt, in PSS) is a random number that is different in every signature computation
The same message produces a different signature
Allows a "tighter" security proof, but has little practical effect on security
Now the signature consists of S plus the nonce
S = Sign(Hash(nonce||M)) = (Hash(nonce||M))^{d} (mod n)
Skein explicitly specifies how to include the nonce and the public key when hashing a message
Skein can generate a digest of any length -- no need for a padding function
RSA Digital Signatures With Message Recovery
The scheme described so far is "digital signature with appendix"
Blake has to send the message, plus the signature appended to the message
For short messages, an alternative is "digital signature with message recovery"
Apply the signing function to M concatenated with the hash of M
Then we only have to send the signature, not the message plus the signature
The message is automatically recovered from the signature during the verification process
Example: M is 128 bits (like an AES key), Hash(M) is 1920 bits, total 2048 bits
S = Sign(M||Hash(M)) = (M||Hash(M))^{d} (mod n)
Verify(S): Compute C = S^{e} (mod n); split C into M (128 bits) and H' (1920 bits); if H' = Hash(M), return (M, "verified"), else return "not verified"
Existential forgery is still impossible
Digital signature with message recovery is not encryption
Given S and Blake's public key, anyone can compute M
El Gamal Digital Signatures
Security based on the hardness of the DLP
Alex's key generation algorithm
Choose a large prime p
Choose a generator g for a large-order subgroup of Z_{p}^{*}
Choose a secret random number a
Compute y = g^{a} (mod p)
Alex's public key is (p, g, y)
Alex's private key is a
Alex signs a message m using her private key
Choose a secret random number k with gcd (k, p−1) = 1
Compute r = g^{k} (mod p)
Compute s = k^{−1}⋅(Hash(m) − ar) (mod p−1)
Alex's signature for m is (r, s)
Blake verifies signature (r, s) on message m using Alex's public key
Check whether g^{Hash(m)} = y^{r}⋅r^{s} (mod p)
Euler's Theorem: g^{Φ(n)} = 1 (mod n)
Corollary: If x = y (mod Φ(n)), then g^{x} = g^{y} (mod n)
Why the verification works:
s = k^{−1}⋅(Hash(m) − ar) (mod p−1)
ks = Hash(m) − ar (mod p−1)
Hash(m) = ar + ks (mod p−1)
g^{Hash(m)} = g^{(ar + ks)} (mod p) -- by the above corollary