Alan Kaminsky • Department of Computer Science • Rochester Institute of Technology • 4572 + 2433 = 7005
 Foundations of Cryptography • CSCI 662-01 • Spring Semester 2018
Course Page

## CSCI 662—Foundations of Cryptography Chapter 10. Digital Signatures Lecture Notes

Prof. Alan Kaminsky
Rochester Institute of Technology—Department of Computer Science

### The High Level Picture

• Goals of digital signatures
• Authentication
• Integrity
• Nonrepudiation

• Digital signature operation
• Blake has a private signing key and a public verifying key
• Blake computes signature S on message M: S = SignBlakesSigningKey(M)
• Blake sends M and S to Alex
• Alex verifies signature S on message M: VerifyBlakesVerifyingKey(M,S) → {verified, not verified}

• Security requirements
• Without Blake's private signing key, it must be impossible to sign a message that will verify as coming from Blake
• It must be impossible to derive Blake's private signing key from Blake's public verifying key

### Naive RSA Digital Signatures

• Key generation (same as for RSA encryption)
• Choose primes p and q (e.g., 1024 bits)
• n = pq
• Φ(n) = (p−1)(q−1)
• Choose exponents e and d with ed = 1 (mod Φ(n))
• Public verifying key = (n, e)
• Private signing key = d

• Signing operation: Sign(M)
• S = Md (mod n)

• Verifying operation: Verify(M,S)
• Compute M' = Se (mod n)
• If M' = M, return "verified", else return "not verified"
• This works because Se = (Md)e = M (mod n) — see RSA public key encryption for a proof

• Short public exponent, e.g. e = 3 or 65537, speeds up verification

• Security of RSA digital signatures: same as RSA encryption
• Harry cannot compute a signature without knowing d, the private key
• Harry cannot derive d from (n, e), the public key, because integer factorization is hard

• Problem Number 1: Message size
• This only works if the message M is a number less than n (e.g., a 2048-bit number)

• Problem Number 2: Homomorphic property of RSA
• Suppose Harry the Hacker sees Blake sign two messages: S1 = Sign(M1), S2 = Sign(M2)
• Then Harry can compute the signature on the message M1⋅M2 (mod n) as S1⋅S2 (mod n) without knowing Blake's private key
• Sign(M1⋅M2) = (M1⋅M2)d (mod n) = M1d⋅M2d (mod n) = S1⋅S2 (mod n)
• The "message" M1⋅M2 (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 = Se (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' = 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 message's digest computed by a cryptographic hash function
• 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 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: S1 = Sign(Hash(M1)), S2 = Sign(Hash(M2))
• The signature for message M1⋅M2 would be Sign(Hash(M1⋅M2))
• But Hash(M1⋅M2) ≠ Hash(M1)⋅Hash(M2), almost certainly
• Therefore, Sign(Hash(M1⋅M2)) ≠ S1⋅S2, almost certainly

• Solution to Problem Number 3, Existential forgery:
• Suppose Harry picks some signature S and computes Se (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)

• 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 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 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 (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
• Blake's RSA public key is (n, e); Blake's RSA private key is d
• Blake has generated signature S for message M, S = Md (mod n)
• Alex verifies Blake's signature by checking whether Se = 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 = 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'
• Alex verifies Harry's "signature" by checking whether Se' = 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 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"
• 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 = 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 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 Zp*
• Choose a secret random number a
• Compute y = ga (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 = gk (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 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
• gHash(m) = gar⋅gks (mod p)
• gHash(m) = (ga)r⋅(gk)s (mod p)
• gHash(m) = yr⋅rs (mod p)

### Digital Signatures With DSA

• Digital Signature Standard (DSS). Federal Information Processing Standards Publication 186-4, July 2013. http://nvlpubs.nist.gov/nistpubs/FIPS/NIST.FIPS.186-4.pdf

• DSS permits using any of three digital signature algorithms:
• RSA
• Digital Signature Algorithm (DSA) -- a variation of El Gamal signature algorithm
• Elliptic Curve Digital Signature Algorithm (ECDSA)

• DSS permits using the SHA-1 or SHA-2 hash functions

• DSS with RSA
• Must use a 1024-, 2048-, or 3072-bit modulus n
• Security based on hardness of integer factorization

• DSS with DSA
• Uses a subgroup of Zp*, subgroup order is q
• Allowed sizes:
• p = 1024 bits, q = 160 bits
• p = 2048 bits, q = 224 bits
• p = 2048 bits, q = 256 bits
• p = 3072 bits, q = 256 bits
• Security based on hardness of discrete logarithm problem in Zp*

• DSS with ECDSA
• Uses an elliptic curve group (mod p)
• Recommended curves (bit sizes q): P-192, P-224, P-256, P-384, P-521
• Security based on hardness of discrete logarithm problem in elliptic curve group

• Signature generation computations
• RSA: One exponentiation modulo n, (log2 n)-bit exponent
• DSA: One exponentiation modulo p, q-bit exponent, plus some small stuff
• ECDSA: One point multiplication, q-bit multiplier

• Signature size
• RSA: One (log2 n)-bit number
• DSA: Two q-bit numbers
• ECDSA: Two q-bit numbers

• Signature verification computations
• RSA: One exponentiation modulo n, small exponent (if we use e = 3 or 65537)
• DSA: Two exponentiations modulo p, q-bit exponents, plus some small stuff
• ECDSA: Two point multiplications, q-bit multipliers, one point addition, plus some small stuff

• RSA vs. DSA or ECDSA
• RSA signature generation takes more time than DSA or ECDSA
• RSA signatures are larger than DSA or ECDSA signatures
• RSA signature verification (with small e) takes much less time than DSA or ECDSA signature verification

• RSA is the most popular digital signature algorithm
• Faster signature verification
• Simpler implementation

### Authentication with Digital Signatures

• Authenticated Diffie-Hellman key exchange
• Alex signs her message, Blake verifies it
• Blake signs his message, Alex verifies it

• Problem: While the messages are authenticated, the public keys are not authenticated
• Harry can still do a man-in-the-middle attack if he can:
• Make Alex think Harry's public key is Blake's public key
• Make Blake think Harry's public key is Alex's public key

• Solution: Public Key Infrastructure (PKI) -- Chapter 13

 Foundations of Cryptography • CSCI 662-01 • Spring Semester 2018
Course Page
 Alan Kaminsky • Department of Computer Science • Rochester Institute of Technology • 4572 + 2433 = 7005