Lec4: Digital Signature

Symmetric Key Cryptography

Cyptographic Hash Functions

Cyrptographic Hash Functions are used to guarantee the integrity of data.

 

Cytographic Hash Function H stasfies the following properties:

• Message Digest
• Preimage Resistant: it must be one way
• Collision Resistant

It's often used as a component of other cryptography algorithms

• used to compress a large data to a smaller one
• used to generate a deterministic random values
• ex. MD5, SHA1, SHA2, SHA3 -> MD5, SHA1 not recommended anymore for security implementations

Message Authentication Code (MAC)

Message Authentication Code (MAC)

• cryptographic primitive that is used to authenticate the origin and nature of message
• symmetric version of digital signature
• keyed hash functions
  • $t = MAC(k, M)$ where k is a key and $t$ is called a tag or MAC
  • ${0, 1} = Verify(k, t, M)$ where 0 = invalid, 1 = valid
  • without key, cannot compute a valid hash tags
  • sender and receiver have the same key

---

Public Key Cryptography

Digital Signature

Digital Signature

• output of digital signature provides a guarantee of three important security properties:
  1. message integrity: message has not been altered in transit
  2. message authentication: message was send by Alice
  3. non-repudiation: Alice cannot claim she did not send the message

First two properties are also provided by MAC. However, non-repudiation is not provided by MACs and has important applications in e-payment system.

 

Digital Signature Schema

• signer signs a message with signing key sk and signature is verified using the signer's verification key vk
  • Signing key sk is private key
  • Verification key vk is public key
• s = Sign(sk, M) where s: signature
• {"Invalid(0)" or "Valid(1)"} = Verify(vk, M, σ)

 

A definition of Digital Signature

• Key-generation algorithm Gen
  • input a security parameter $1^n$ and outputs a pair of keys (vk, sk)
• Signing algorithm Sign
  • input a signing key sk and message m and outputs a signature σ
  • σ <- $Sign_{sk}(m)$
• Deterministic verification algorithm Vrfy
  • input a verification key vk, a message m, and a signature σ, outputs a bit b with b=1 meaning valid and b=0 mean invalid
  • b := $Vrfy_{vk}(m, σ)$

 

Digital Signature Algorithm (DSA)

Digital Signature Algorithm (DSA) is a Federal Information Processing Standard for digital signatures.

 

Setup($1^𝜆$)

• Choose a cryptographic hash function H with output length |H| bits.
• Choose a key length L recommended lengths of 2048(or 3072) for keys with security lifetimes extending beyond 2010 (or 2030)
• Choose the modulus length N such that N < L and N <= |H|
  • specifying (L, N): (2048, 256), (3072, 2566)
• Choose an N-bit prime q and an L-bit prime p such that p-1 is a multiple of q
• Choose an integer ℎ ∈ {2, … , 𝑝 − 2} and set 𝑔 = $h^{(p−1)/q}$ 𝑚𝑜𝑑 𝑝 such that 𝑔 ≠ 1.
• Set (p, q, g) as the common parameters.

KeyGen(p, q, g)

• Choose an integer 𝑥 randomly from {1 … 𝑞 − 1}.
• Compute 𝑦 = $g^x$ 𝑚𝑜𝑑 𝑝.
• Set 𝑥 as a private key and publish 𝑦 as a public key.

Sign(m, x, p, q, g)

• Choose an integer 𝑘 randomly from 1 … 𝑞 − 1.
• Compute 𝑟: = ($𝑔^𝑘$ 𝑚𝑜𝑑 𝑝) 𝑚𝑜𝑑 𝑞. If 𝑟 = 0, start again with a different random 𝑘.
• Compute 𝑠: = ($𝑘^{−1}$(𝐻(𝑚) + 𝑥𝑟)) 𝑚𝑜𝑑 𝑞. If s=0, start again with a different random 𝑘.

Vrfy(m, r, s, p, q, g)

• Verify that 0 < 𝑟 < 𝑞 and 0 < 𝑠 < 𝑞.
• Compute 𝑤: = $𝑠^{−1}$ 𝑚𝑜𝑑 𝑞.
• Compute $𝑢_1$: = 𝐻(𝑚) ⋅ 𝑤 𝑚𝑜𝑑 𝑞
• Compute $𝑢_2$: = 𝑟 ⋅ 𝑤 𝑚𝑜𝑑 𝑞
• Compute 𝑣: = ($𝑔^{𝑢_1}$ ⋅ $𝑦^{𝑢_2}$ 𝑚𝑜𝑑 𝑝) 𝑚𝑜𝑑 𝑞
• The signature is valid if and only if 𝑣 = 𝑟

DSA vs ECDSA

• ECDSA: elliptic-curve cryptography (ECC)
• the bit size of the private key believed to be needed for ECDSA is about twice the size of the security level, in bits.
• at a security level of 80 bits - meaning attacker requires a maximum $2^{80}$ operations to find the private key
  • the size of an ECDSA private key would be 160 bits, which is a lot shorter than original DSA - 1024 bits

 

RSA vs ECC: Key Length Comparison

RSA is faster but ECC is efficient and more secure because ECC requires shorter key lengths and as a result, it  requires a lesser load for network and computing power

 

RSA	ECC
A well-established method of public-key cryptography	A newer public-key cryptography method compared to RSA
Works on the principle of the prime factorization method	Works on the mathematical representation of elliptic curves
RSA can run faster than ECC thanks to its simplicity	ECC requires bit more time as it's complex in natrue
RSA has been found vulnerable and is heading towards the end of its tenure	ECC is more secure than RSA and is in its adaptive phase. Its usage is expected to scale up in the future
RSA requires much bigger key lengths to implement encryption	ECC requires much shorter key lengths compared to RSA