Digital signatures

Question 1

How does MAC provide integrity and authentication?

Answer 1

Only an entity with the shared secret can generate a valid MAC tag

Question 2

How does digital signatures obtain the property of MAC?

Answer 2

Use public key cryptography.

Only the private-key owner can generate a correct digital signature

Question 3

How does digital signature provide non-repudiation?

Answer 3

Because a judge can decide which party formed the signature

Question 4

Compare digital and physical signatures

Answer 4

Produced by: human-machine
Same on all documents - function of message
Easy to recognise - requires computer to check

Both must e difficult to forge

Question 5

What is the flow of signatures?

Answer 5

Have a digital message
Hash this
Sign with private key
Verify with public key

Question 6

What are the three algorithms of digital signature schemes?

Answer 6

Key generation (output private signing key Ks and public verification key Kv)
Signature generation
Signature verification

Question 7

Describe the signature generation algorithm

Answer 7

Signature o = Sig(m, Ks)

m: Message
Ks: private signing key

Question 8

Describe the verification algorithm

Answer 8

Ver(m, o, Kv) = true or false

m: Message
o: Claimed signature
Kv: public verification key

Question 9

What are the required properties of verifying functions?

Answer 9

Correctness
Unforgeability

Question 10

What is the correctness property?

Answer 10

If o = Sig(m, Ks) then Ver(m, o, Kv) = true, for any matching signing/verification keys

Question 11

What is the unforgeability property?

Answer 11

It is computationally infeasible for anyone without Ks to construct m and o such that Ver(m, o, Kv) = true

Question 12

What is key recovery?

Answer 12

Attacker tries to recover the private key from the public key and some known signatures

Question 13

What is selective forgery?

Answer 13

Attacker chooses a message and tries to obtain a signature on that message

Question 14

What is existential forgery?

Answer 14

The attacker attempts to forge a signature on any message not previously signed, even if it is a meaningless message

Question 15

When are digital signatures considered secure?

Answer 15

If they can resist existential forgery under a chosen message attack

Question 16

How are RSA signature keys generated?

Answer 16

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

Question 17

Describe RSA signature generation

Answer 17

o = h(m)^d mod n

m: message
n: modulus
d: private exponent

Question 18

Describe RSA signature verification

Answer 18

h’ = h(m)
Check whether o^e mod n = h’

Question 19

What are discrete logarithm signatures?

Answer 19

Signatures whose security relies on the difficulty of the discrete log problem

Question 20

Describe the Elgamal signature scheme in Z_p^*

Answer 20

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?)

Question 21

Describe the Elgamal signature generation

Answer 21

Sign m with signing key x

1. Select random k, 0 < k < p-1
2. compute r = g^k mod p
3. Compute s = k^-1(m - xr) mod (p-1)
4. Signature o = (r, s)

Question 22

Describe the Elgamal signature verification

Answer 22

Given m and claimed signature o = (r, s) and verification key y

Verify that g^m ≡ y^r* r^s mod p

Question 23

Describe Schnorr signature scheme in Z_p^*

Answer 23

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

Question 24

Describe the Schnorr signature generation

Answer 24

1. select random k, 0 < k < p-1
2. compute r=g^k mod p
3. Let e = H(r||m)
4. Compute s = k-xe mod (p-1)
5. Signature: o = (s, e)

Question 25

Describe the Schnorr signature verification

Answer 25

m: message
o = (s, e): claimed signature
y: Verification key

1. r_v = g^s*y^e
2. e_v = H(r_v||m)
3. Check if e == e_v

Question 26

Describe Digital signature algorithm DSA

Answer 26

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

Question 27

What are the parameters of DSA?

Answer 27

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

Question 28

Describe DSA key generation

Answer 28

1. Choose random integer x, 0 < x < q
2. X is the secret signing key
3. y = g^x mod p is the public key

Question 29

Describe DSA signature generation

Answer 29

1. Choose k at random, 0 < k < q
2. Set r = (g^k mod p) mod q
3. Set s = k^-1 (H(m) - xr) mod q
4. Signature o = (r, s)

Question 30

Describe DSA signature verification

Answer 30

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

Question 31

What is ECDSA?

Answer 31

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

Question 32

What are the parameters of ECDSA?

Answer 32

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

Question 33

Describe ECSDA key generation

Answer 33

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

Question 34

Describe ECDSA signature generation

Answer 34

1. e = H(m)
2. Random k, 0 < k < n-1
3. (x, y) = kG
4. r = x, if r = 0 return to step 2
   5.s = k^-1(e + rd) mod n
5. Signature o = (r, s)

Question 35

Describe ECDSA signature verification

Answer 35

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

Question 36

What is deterministic ECDSA signatures?

Answer 36

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

Question 37

What is EdDSA signatures?

Answer 37

Uses Edwards curve 25519

Deterministic version of Schnorr signatures

Question 38

When is deterministic signatures recommended?

Answer 38

When a good random number generator is not available

Question 39

What is a chosen message oracle?

Answer 39

When an attacker is able to obtain signatures on messages of their choice.