Digital signature
An amazing development first due to Diffie and Hellman ("New directions in public key cryptography" paper)
Alice m, s = sig(SK, m) Bob
> verify(m, PK, s)
Original Diffie Hellman idea: public key maps a plaintext to a ciphertext, and secret key unmaps.
Keygen(1^l) > PK (verification key), SK (signing key)
Sign(SK, m) > s_SK(m)
 this process may be randomized
 apparently no reason to have deterministic signatures
Verify(PK, m, s) > true/false
\forall m, Verify(PK, m, Sign(SK, m)) > true
Game:
(PK, SK)
keypair, sends PK
to adversarym1, m2, ..., mq
s_i = Sign(SK, m)
for each m_i
q = poly(l)
, m_i
may depend on signatures to previous messages(m, s*)
Verify(PK, m, s*) \and m \notin
the set
of previously queried messagesThis scheme is secure if Prob[Adversary wins] = negl(l)
The strong version, allows the message of the forgery to be one of the messages the adversary previously asked for as long as the forged signature is different than the one the adversary received.
Early on it became obvious that you should not encrypt or sign full messages,
because public key schemes were slow =>
sign h(m)
rather than m
As long as the hash function is collisionresistant, and it's hard to find m1
& m2
, s.t. h(m1) = h(m2)
, a signature for m1
is guaranteed to be for m1
only.
To sign M
, compute m = h(M)
. Need to create a particular message that will
fit into an RSA block.
We can define pad(m) = 0x 00 01 FF .. FF 00  hash_name  m
hash_name
is in ASN.1 (abstract syntax notation 1) formSigning:
RsaSign(SK = (d, n), m) = pad(m)^d (mod n)
No proof of security here... Not that used much anymore, because OAEP has a proof of security.
Diagram:
 
 m   r 
 
\ /
\ /
 / 
 h  </ 
 
 / g1 >+
\ / 
w/ 
\ \
\ r*
\>  g2 

\

0 w r* g2(w)


y
\

 RSA 


\
Sign(m) = y^d (mod n)
Anytime you see a little bit of randomization you have to ask the question of what will happen if the users don't have good enough random generators.
Sign, w = k, r = k0
:
r <R {0,1}^k_0
w < h(Mr)
r* < g1(w) \xor r
y < 0  w  r*  g2(w)
output s(m) = y^d mod n
Verify:
y < s(m)^e (mod n)
parse y as b  w  r*  g2w
r < r* \xor g1(w)
return true if b = 0 && h(mr) == w && g2(w) == g2w
Theorem: PSS is weaklyexistentially unforgeable under an adaptive chosen message attack in the Random Oracle Model if RSA is not invertible on random inputs
large prime p, generator g of Z_p*
 public
h is collisionresistant, outputs value in Z_p1
Keygen(1^l):
x <R {0, 1, ..., p2}
sk < x
pk < y = g^x (mod p)
Sign(M):
m = h(M)
k < R  Z_{p1}*, s.t. gcd(k, p1) = 1
 because we will need to compute the multiplicative inverse of k
in Z_{p1}*
r = g^k (mod p)
s = (mr*x)/k (mod p1)
 sort of shifting domains here
s(M) = (r, s)
Verify(M, y = g^x, (r, s)):
ensure that 0 < r < p
ensure that y^r * r^s = g^m (mod p)
Why does verification work?
y^r = g^(rx)
r^s = (g^k)^s = g^k*((mrx)/k) = g^(mr*x)
y^r * r^s = g^(rx + m  rx) = g^m (mod p)
or alternatively,
y^r * r^s = g^m (mod p) <=> g^(rx) * g^(sk) = g^m (mod p) <=>
rx + sk = m (mod p1) <=> s = (mrx)/k
Why the p1? The order of g
is p1
, so things repeat after raising g^{p1} = 1
Can you forge signatures? Yes you can.
Note that the identity function is CR hash function.
Theorem: ElGamal digital signatures are existentially forgeable.
Proof:
h(x) = x
as the hash functione <R Z_p1
r < g^e * y (mod p)
(y = g^x
is the PK of the guy whose signature we are forging)s < r (mod p)
(r, s)
is a valid signature for e*s
Is y^r * r^s = g^m
? g^xr * (g^e * y)^r = g^er = g^es = g^m
This is bad. It seems that we need more from our hash function, not just CR.
Fix:
Sign(M):
k < R  Z_{p1}*, s.t. gcd(k, p1) = 1
 because we will need to compute the multiplicative inverse of k
in Z_{p1}*
r = g^k (mod p)
m = h(Mr)
s = (mr*x)/k (mod p1)
 sort of shifting domains here
s(M) = (r, s)
Theorem: Modified ElGamal is existentially unforgeable against adaptive chosen message attack in the Random Oracle Model assuming discrete log problem (DLP) is hard.
Foundation for other schemes, such as the DSA scheme.
Read DSA FIPS standard here.
Diagram:
p = nq+1, p is a large prime
q = 160 bits
p = 1024 bits
end up with 320bit signature
g0 generates Z_p*
g = g0^n generates subgroup G_q of order q
 hard to tell appart G_q and Z_p*, given a random element
x <R Z_q* // 160 bits, x \in [1, q) (not in G_q)
y < g^x mod p // 1024 bits
SK = x, PK = y
Sign(M):
k <R Z_q* // 1 <= k < q
r < ((g^k mod p) mod q) // r = 160 bits
m < h(M)
s < (m+rx)/k mod q // + instead of , s = 160 bits
redo if r = 0 or s = 0
output (r, s)
Verify(M, r, s):
m < h(M)
check that 0 < r < q & 0 < s < q
check that y^(r/s) g^(m/s) (mod p)(mod q) = r
[ note that s = (rx + m)/k and r = g^k
y^(r/s) = g^(rx/s) =>
y^(r/s) * g^(m/s) = g^(rx + m)/s = g^(m+rx)/((m+rx/k)) = g^k = r ]
As before, it's forgeable with certain hash functions. Fix is the same.