Digital signatures Flashcards
How does MAC provide integrity and authentication?
Only an entity with the shared secret can generate a valid MAC tag
How does digital signatures obtain the property of MAC?
Use public key cryptography.
Only the private-key owner can generate a correct digital signature
How does digital signature provide non-repudiation?
Because a judge can decide which party formed the signature
Compare digital and physical signatures
Produced by: human-machine
Same on all documents - function of message
Easy to recognise - requires computer to check
Both must e difficult to forge
What is the flow of signatures?
Have a digital message
Hash this
Sign with private key
Verify with public key
What are the three algorithms of digital signature schemes?
Key generation (output private signing key Ks and public verification key Kv)
Signature generation
Signature verification
Describe the signature generation algorithm
Signature o = Sig(m, Ks)
m: Message
Ks: private signing key
Describe the verification algorithm
Ver(m, o, Kv) = true or false
m: Message
o: Claimed signature
Kv: public verification key
What are the required properties of verifying functions?
Correctness
Unforgeability
What is the correctness property?
If o = Sig(m, Ks) then Ver(m, o, Kv) = true, for any matching signing/verification keys
What is the unforgeability property?
It is computationally infeasible for anyone without Ks to construct m and o such that Ver(m, o, Kv) = true
What is key recovery?
Attacker tries to recover the private key from the public key and some known signatures
What is selective forgery?
Attacker chooses a message and tries to obtain a signature on that message
What is existential forgery?
The attacker attempts to forge a signature on any message not previously signed, even if it is a meaningless message
When are digital signatures considered secure?
If they can resist existential forgery under a chosen message attack
How are RSA signature keys generated?
A modulus n is computed:
n = pq, p and q are two large primes
e and d are generated such that:
ed mod o(n) = 1
Private key: sk = (d, p, q)
Public key: pk = (e, n)
A hash function h is also required and should be a fixed public parameter of the signature scheme
Describe RSA signature generation
o = h(m)^d mod n
m: message
n: modulus
d: private exponent
Describe RSA signature verification
h’ = h(m)
Check whether o^e mod n = h’
What are discrete logarithm signatures?
Signatures whose security relies on the difficulty of the discrete log problem
Describe the Elgamal signature scheme in Z_p^*
p: large prime
g: generator for Z_p^*
x: 0 < c < p-1, private signing key
y = g^x mod p: public verification key
Public knowledge: p, g, y
m: message with value between 0 and p-1 (maybe?)
Describe the Elgamal signature generation
Sign m with signing key x
- Select random k, 0 < k < p-1
- compute r = g^k mod p
- Compute s = k^-1(m - xr) mod (p-1)
- Signature o = (r, s)
Describe the Elgamal signature verification
Given m and claimed signature o = (r, s) and verification key y
Verify that g^m ≡ y^r* r^s mod p
Describe Schnorr signature scheme in Z_p^*
Public knowledge: p, g, y
p: large prime
g: generator for Z_p^*
x: 0 < x < p-1, private key
y = g^x mod p: public key
Describe the Schnorr signature generation
- select random k, 0 < k < p-1
- compute r=g^k mod p
- Let e = H(r||m)
- Compute s = k-xe mod (p-1)
- Signature: o = (s, e)
Describe the Schnorr signature verification
m: message
o = (s, e): claimed signature
y: Verification key
- r_v = g^s*y^e
- e_v = H(r_v||m)
- Check if e == e_v
Describe Digital signature algorithm DSA
Based on Elgamal signatures
Simpler calculations and shorter signatures because it restricts calculations to a subgroup of Z_p^* or to an elliptic curve group
Avoids some attacks that Elgamal may be vulnerable to
What are the parameters of DSA?
p: a prime modulus of L bits
q: a prime divisor of p-1 of N bits
Use valid combinations of L and N: (L=1024, N=160), (L=2048, N=224), (L=2048, N=256), (L=3072, N=256)
g = h^((p-1) / q) mod p
h is any integer, 1 < h < p-1
H: SHA hash family variant which outputs an N-bit digest
Describe DSA key generation
- Choose random integer x, 0 < x < q
- X is the secret signing key
- y = g^x mod p is the public key
Describe DSA signature generation
- Choose k at random, 0 < k < q
- Set r = (g^k mod p) mod q
- Set s = k^-1 (H(m) - xr) mod q
- Signature o = (r, s)
Describe DSA signature verification
Claimed signature (r, s)
Check that 0 < r < q
Check that 0 < s < q
Compute w = s^-1 mod q
u1 = H(m)w mod q
u2 = rw mod q
Check whether (g^y1 * y^-u2 mod p) mod q == r
What is ECDSA?
Elliptic curve DSA
Similar signatur gen and verification, except that:
- q becomes order of elliptic curve group
- multiplication mod p is replaced by elliptic curve group operation
- after operation on the group elements, only the x-coordinate is kept
What are the parameters of ECDSA?
E: An approved elliptic curve field and equation
G: The elliptic curve group generator, or base point
n: Order of curve group and a prime number
H: SHA-2 hash family variant which outputs an N-bit digest
Describe ECSDA key generation
Choose random d with 0 < d < n
d: secret key
Compute Y = dG
Y: public key in group G
It is required to check a public key before it is used, to be a point on the curve G different from the identity
Describe ECDSA signature generation
- e = H(m)
- Random k, 0 < k < n-1
- (x, y) = kG
- r = x, if r = 0 return to step 2
5.s = k^-1(e + rd) mod n - Signature o = (r, s)
Describe ECDSA signature verification
Claimed signature (r, s)
Check 0 < r < n
Check 0 < s < n
w = s^-1 mod ne = H(m)
u1 = ew mod n
u2 = rw mod n
Compute the point (x, y) = u1G + u2Y
Valid signature:
- (x, y) is not the identity element in the curve E
- r ≡ x mod n
What is deterministic ECDSA signatures?
The per-message key is deterministically computed as a function (based on HMAC) of the message to be signed and the private signing key d
What is EdDSA signatures?
Uses Edwards curve 25519
Deterministic version of Schnorr signatures
When is deterministic signatures recommended?
When a good random number generator is not available
What is a chosen message oracle?
When an attacker is able to obtain signatures on messages of their choice.
