DSA/DSS

Digital Signature Algorithm / Digital Signature Standard.

Public key (p, q, g, y) where y = g·x mod p Private key (p, q, g, x)

SIGN:
k = random in [1, q-1]
r = g^k mod p mod q
s = k-1 (H(M) + x·r) mod q
--> (r, s)

VERIFY:
a = g^( H(M) · s-1 mod q ) mod p
b = y^( r ·    s-1 mod q ) mod p 
r == (a·b mod p) mod q

Repeat K Attack

s1 = k-1 (H(M1) + x·r) mod q
s2 = k-1 (H(M2) + x·r) mod q

x = (H(M1)s2 - H(M2)s1) · (r·(s1 - s2))-1  mod q

Demonstration

s1 = k-1 (H(M1) + x·r) mod q
s2 = k-1 (H(M2) + x·r) mod q

s1·k = H(M1) + x·r mod q
s2·k = H(M2) + x·r mod q

s1·k - x·r = H(M1) mod q
s2·k - x·r = H(M2) mod q

H(M1) - H(M2) = (s1·k - x·r)-(s2·k - x·r)  mod q
H(M1) - H(M2) = s1·k - x·r -s2·k + x·r     mod q
H(M1) - H(M2) = s1·k - s2·k                mod q
H(M1) - H(M2) = (s1 - s2)·k                mod q

k = (H(M1) - H(M2)) · (s1 - s2)-1  mod q

x·r = s1·k - H(M1)       mod q
x = s1·k - H(M1) · r-1   mod q

x = s1·( (H(M1) - H(M2)) · (s1 - s2)-1 ) - H(M1) · r-1.   mod q

x = (H(M1)s2 - H(M2)s1) · (r·(s1 - s2))-1  mod q

K with Linear Increment Attack

K, K + 1, K + 2, K + 3, ...

s1·k = H(M1) + x·r1 mod q
s2·k + s2 = H(M2) + x·r2 mod q

x = s1·( (H(M2) - s2 - H(M1)·r1-1·r2) · (s2 - s1·r1-1·r2)-1 )·r1-1 - H(M1)·r1-1 mod q

Demonstration

s1·k = H(M1) + x·r1 mod q
s2·k + s2 = H(M2) + x·r2 mod q

Gaussian elimination (x)
s1·k·r1-1 = H(M1)·r1-1 + x mod q       # Poniamo sola la x, divido per r1
s2·k + s2 - s1·k·r1-1 = H(M2) + x·r2 - (H(M1)·r1-1 + x)         mod q  # secondo passaggio meno terzo
s2·k + s2 - s1·k·r1-1·r2 = H(M2) + x·r2 - (H(M1)·r1-1 + x)·r2   mod q  # moltiplico per r2 la seconda componente
s2·k + s2 - s1·k·r1-1·r2 = H(M2) + x·r2 - H(M1)·r1-1·r2 - x·r2  mod q
s2·k + s2 - s1·k·r1-1·r2 = H(M2) - H(M1)·r1-1·r2 mod q

x = s1·k·r1-1 - H(M1)·r1-1 mod q    # Guardando la terza

# Divido la terza con s2 - s1·r1-1·r2
k = (H(M2) - s2 - H(M1)·r1-1·r2) · (s2 - s1·r1-1·r2)-1      mod q     # Divido la terza con s2 - s1·r1-1·r2
k = (s2·k + s2 - s2 - s1·k·r1-1·r2) · (s2 - s1·r1-1·r2)-1   mod q
k = (s2·k - s1·k·r1-1·r2) · (s2 - s1·r1-1·r2)-1             mod q
k = k·(s2 - s1·r1-1·r2) · (s2 - s1·r1-1·r2)-1               mod q
k = k 

x = s1·( (H(M2) - s2 - H(M1)·r1-1·r2) · (s2 - s1·r1-1·r2)-1 )·r1-1 - H(M1)·r1-1 mod q

K, K + N, K + 2N, K + 3N, ...

s1·k = H(M1) + x·r1 mod q
s2·k + Ns2 = H(M2) + x·r2 mod q

x = s1·( (H(M2) - Ns2 - H(M1)·r1-1·r2) · (s2 - s1·r1-1·r2)-1 )·r1-1 - H(M1)·r1-1 mod q

Demonstration

s1·k = H(M1) + x·r1 mod q
s2·k + Ns2 = H(M2) + x·r2 mod q

Gaussian elimination (x)
s1·k·r1-1 = H(M1)·r1-1 + x mod q       # Poniamo sola la x, divido per r1
s2·k + Ns2 - s1·k·r1-1 = H(M2) + x·r2 - (H(M1)·r1-1 + x)         mod q  # secondo passaggio meno terzo
s2·k + Ns2 - s1·k·r1-1·r2 = H(M2) + x·r2 - (H(M1)·r1-1 + x)·r2   mod q  # moltiplico per r2 la seconda componente
s2·k + Ns2 - s1·k·r1-1·r2 = H(M2) + x·r2 - H(M1)·r1-1·r2 - x·r2  mod q
s2·k + Ns2 - s1·k·r1-1·r2 = H(M2) - H(M1)·r1-1·r2 mod q

x = s1·k·r1-1 - H(M1)·r1-1 mod q    # Guardando la terza

# Divido la terza con s2 - s1·r1-1·r2
k = (H(M2) - Ns2 - H(M1)·r1-1·r2) · (s2 - s1·r1-1·r2)-1       mod q     # Divido la terza con s2 - s1·r1-1·r2
k = (s2·k + Ns2 - Ns2 - s1·k·r1-1·r2) · (s2 - s1·r1-1·r2)-1   mod q
k = (s2·k - s1·k·r1-1·r2) · (s2 - s1·r1-1·r2)-1               mod q
k = k·(s2 - s1·r1-1·r2) · (s2 - s1·r1-1·r2)-1                 mod q
k = k 

x = s1·( (H(M2) - Ns2 - H(M1)·r1-1·r2) · (s2 - s1·r1-1·r2)-1 )·r1-1 - H(M1)·r1-1 mod q