Suppose Harry picks some S, computes M = Se (mod n) using Bob's public key, and sends the message M and signature S to Alice, pretending they came from Bob
Alice, verifying the signature, will compute M' = Se (mod n) and find M' = M, so the signature verifies
Again, the "message" Se (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 hash of the message
S = Sign(Hash(M)) = (Hash(M))d (mod n)
Verify(M,S): Compute H' = Se (mod n); if H' = Hash(M), return "verified", else return "not verified"
Security of signed hashes
Suppose Harry sees Bob compute signature S on message M
If Harry can find another message M' with the same hash 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, Mathematical structure:
Suppose Harry sees Bob sign two messages: S1 = Sign(Hash(M1)), S2 = Sign(Hash(M2))
Then S1S2 is the signature for a message whose hash is Hash(M1)*Hash(M2)
But finding such a message is hard, because the hash function is preimage resistant
Solution to Problem Number 3, Existential forgery:
Suppose Harry picks some signature S and computes Se (mod n)
This is supposed to be the hash of 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.
Bob, Alice's boss, asks Harry to write a letter recommending Alice for promotion, which Bob will digitally sign
Harry prepares two letters, the "good" letter recommending promoting Alice, and the "bad" letter recommending firing Alice
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 232 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 Bob to sign the good letter whose hash is H (Bob actually signs H = Hash(letter))
Harry puts that signature on the bad letter whose hash is H
Bob thought he signed the good letter, but his signature is valid on the bad letter, so Alice 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 (2n/2 work) than preimages (2n 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
Bob's RSA public key is (n, e); Bob's RSA private key is d
Bob has generated signature S for message M, S = Md (mod n)
Alice verifies Bob's signature by checking whether Se = M (mod n), which it does
Harry wants to generate an RSA public-private key pair such that Bob'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 = Md' (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'
Alice verifies Harry's "signature" by checking whether Se' = M (mod n'), which it does
So now Alice doesn't know who signed the message, Bob or Harry
Solution to Problem Number 6: Sign Hash(message||public key)
Bob generates signature S = Hash(M||n||e)d (mod n)
Alice checks whether Se = 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)
Verify(M,S,nonce): Compute H' = Se (mod n); if H' = Hash(nonce||M), return "verified", else return "not verified"
Skein, a SHA-3 finalist candidate hash algorithm
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"
Bob 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 = Se (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 Bob's public key, anyone can compute M
El Gamal Digital Signatures
Security based on the hardness of the DLP
Alice's key generation algorithm
Choose a large prime p
Choose a generator g for a large-order subgroup of Zp*
Choose a secret random number a
Compute y = ga (mod p)
Alice's public key is (p, g, y)
Alice's private key is a
Alice signs a message m using her private key
Choose a secret random number k with gcd (k, p−1) = 1
Compute r = gk (mod p)
Compute s = k−1⋅(Hash(m) − ar) (mod p−1)
Alice's signature for m is (r, s)
Bob verifies signature (r, s) on message m using Alice's public key
Check whether gHash(m) = yr⋅rs (mod p)
Euler's Theorem: gΦ(n) = 1 (mod n)
Corollary: If x = y (mod Φ(n)), then gx = gy (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)
gHash(m) = g(ar + ks) (mod p) -- by the above corollary