Cryptography - Lecture 19 - Digital Signature Algorithms

1. Digital Signature Schemes

• public key signature schemes
  • the private-key signs (creates) signatures
  • the public-key verifies signatures
• only the owner (of the private-key) can create the digital signature
• hence it can be used to verify who created a message
• anyone knowing the public key can verify the signature
  • provided they are confident of the identity of the owner of the public key
  • the key distribution problem
• usually don't sign the whole message
• since this would double the amount of information exchanged)
• rather just a hash of the message
• digital signatures can provide non-repudiation of message origin, since an asymmetric algorithm is used in their creation, provided suitable timestamps and redundancies are incorporated in the signature

2. RSA

• RSA encryption and decryption are commutative
• hence it may be used directly as a digital signature scheme
• given an RSA scheme {(e,R), (d,p,q)}
• to sign a message, compute:
  • S = Md(mod R)
• to verify a signature, compute:
  • M = Se(mod R) = Me.d(mod R) = M(mod R)

3. RSA Usage

• when using RSA for both encryption and authentication:
  • use the senders public key to sign the message
  • use the recipients public key to encrypt the message
• seems obvious a message can be encrypted, then signed, using RSA without increasing it size
  • but have blocking problem, since it is encrypted using the receivers modulus, but signed using the senders modulus (which may be smaller)
  • can overcome this by swapping order of operations, but
• more commonly use a hash function to create a digest which is then signed
• and send this signed digest separate to the message

4. El Gamal Signature Scheme

• the ElGamal encryption algorithm is not commutative
• however a closely related signature scheme exists
• security depends on the difficulty of computing discrete logarithms
• setup (key generation) is the same:
• have shared prime p, public primitive root a
• each user chooses as private (key) a random number x
• and computes public key: y = ax mod p
• public key is (y,a,p)
• private key is (x)

5. El Gamal Signature Scheme In Use

• to sign message M:
  • choose a random number k, GCD(k,p-1)=1
  • compute K = ak(mod p)
  • use extended Euclidean (inverse) algorithm to find S:
    M = x.K + k.S mod (p-1); that is find
    S = k-1(M - x.K) mod (p-1)
  • the signature is (K,S)
  • note that k should be destroyed after use
  • like ElGamal encryption the signature is double the message size
• to verify a signature (K,S) on message M confirm that:
  • yK.KSmod p = aMmod p

6. Example of ElGamal Signature Scheme

• given p=11, g=2
• choose private key x=8
• compute: y = ax mod p = 28 mod 11 = 3
• public key is: y=3,g=2,p=11
• to sign a message M=5
  • choose random k=9
  • confirm gcd(10,9)=1
  • compute: K = ak mod p = 29 mod 11 = 6
  • solve: 5 = 8.6+9.S mod 10; nb 9-1 = 9 mod 10;
hence S = 9.(5-8.6) = 3 mod 10
  • signature is (K=6,S=3)
• to verify the signature, confirm:
  36.63 = 25 mod 11
3.7 = 32 = 10 mod 11

7. DSA (Digital Signature Algorithm)

• US Federal Govt approved signature scheme (FIPS PUB 186)
• used with SHA hash alg
• designed by NIST & NSA in early 90's
  • DSA is the algorithm, DSS is the standard
  • there was considerable reaction to its announcement!
    • debate over whether RSA should have been used
    • debate over the provision of a signature only alg
• DSA is a variant on the ElGamal and Schnorr algorithms
• creates a 320 bit signature, but with 512-1024 bit security
• security again rests on difficulty of computing discrete logarithms
• has been quite widely accepted

8. DSA Key Generation

• firstly shared global public key values (p,q,g) are chosen:
  • choose a large prime p = 2L
  • where L= 512 to 1024 bits and is a multiple of 64
  • choose q, a 160 bit prime factor of p-1
  • choose g = h(p-1)/q
  • for any h<p-1, h(p-1)/q(mod p)>1
• then each user chooses a private key and computes their public key:
  • choose x<q
  • compute y = gx(mod p)

9. DSA Signature Creation and Verification

• to sign a message M
  • generate random signature key k, k<q
  • compute
    • r = (gk(mod p))(mod q)
    • s = k-1.SHA(M)+ x.r (mod q)
  • send signature (r,s) with message
• to verify a signature, compute:
  • w = s-1(mod q)
  • u1= (SHA(M).w)(mod q)
  • u2= r.w(mod q)
  • v = (gu1.yu2(mod p))(mod q)
  • if v=r then the signature is verified

10. DSA Security

• basic security rests on difficulty of computing discrete logarithms mod p
• original recommendation was to use a common modulus p - a tempting target
• now recommend different groups choose own public parameters (p,q,g)
• possible to do both ElGamal and RSA encryption using DSA routines, this was probably not intended :-)
• DSA is patented with royalty free use, but this patent has been contested, situation unclear
• Gus Simmons has found a subliminal channel in DSA, could be used to leak the private key from a library - make sure you trust your library implementer

11. Fiat-Shamir

• originally a signature scheme
• subsequently modified into a zero knowledge proof of identity scheme
• based on difficulty of finding square roots mod pq
• this algorithm is patented
• precursor to DSA

12. Schnorr

• combines ideas from ElGamal and Fiat-Shamir schemes
• uses exponentiation mod p and mod q
• much of the computation can be completed in a pre-computation phase before signing
• for the same level of security, signatures are significantly smaller than with RSA
• this algorithm is patented

13. Keyed Hash Functions

• all the above signature schemes involve public key methods
• with the cost and size overheads they involve
• have a need for a private key signature scheme
• interesting proposal was to use a fast hash function
• but to include a key along with the message:
  KeyedHash = Hash(Key|Message)
• found some weaknesses with original proposal
• then suggested something like:
  KeyedHash = Hash(Key1|Hash(Key2|Message))

14. HMAC

• HMAC is the result of the idea of using a keyed hash function
• specified as an Internet standard (RFC2104)
• uses hash function on the message:

  HMACK = Hash((K+ XOR opad)||Hash((K+ XOR ipad)||M))
  

• where K+ is the key padded out to size
• and opad, ipad are specified padding values
• overhead of this is just 3 more hash calcs than message needs
• security is directly related to the security of the underlying hash
• any of MD5, SHA-1, RIPEMD-160 hash algs can be used

15. Summary

• digital signatures (RSA, ElGamal, DSA, HMAC)

16. Exercises

1. Illustrate the operation of El Gamal signatures, given the following parameters:
   • prime p=31
   • prim root a=3
   Determine a suitable private and public key, and then show the signing and verification of a message M=7.
2. Illustrate the operation of El Gamal encryption, given the following parameters:
   • prime p=31
   • prim root a=12
   Determine a suitable private and public key, and then show the signing and verification of a message M=19.