W8 - Signatures

Question 1

Textbook RSA Signature

Answer 1

σ = m^d mod N
m = σ^e mod N

Question 2

RSA-FDH

Answer 2

σ = H(m)^d mod N

Question 3

Fiat-Shamir ID-Scheme

Answer 3

pk = (N,v)
sk = (N,s)
v = s^2

1) z <- Zn*
I = r^2 modN
2) c <- {0,1}
3) z = r.s^c modN
4) z^2.v^-c mod N ?= I

Question 4

Schnorr ID-Scheme

Answer 4

pk = (G, g, q, h)
sk = (G, g, q, x)
h = g^x

1) r <- Zq
I = g^r mod N
2) c <- Zq
3) r +cx modq
4)g^z.h^-c mod N ?= I

Question 5

Fiat-Shamir Transform

Answer 5

Sign:
(I, State) <- P1(sk)
c = H(I,m)
z = P2(sk, state, c)
σ = (c,z)

Vf:
Compute I = V(pk,c,z)
Return H(I,m) == c