> For the complete documentation index, see [llms.txt](https://ivalexev.gitbook.io/rednote/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://ivalexev.gitbook.io/rednote/pentesting-process/crypto-attacks/dsa-dss.md).
# DSA/DSS
**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
```