This challenge is an implementation of the ElGamal signature scheme without hashing the message. This system is vulnerable to existential forgery, as described by celi0n in their solution.
In this case, the goal is to forge a single signature. There is an easier solution than using the one-parameter forgery described by ElGamal in his paper.
Knowing the parameters p, g and the public key y, set $r=y^{-1}(\text{mod } p)$ and $s=r$. Then the tuple $(r,s)$ is a valid signature for the message $m=0$.
Indeed, we have:
- $g^{m}(\text{mod } p)=g^0(\text{mod } p)=1$,
- $y^rr^s (\text{mod } p)= (y^{(y ^ {-1})})(y^{-1})^{y^{-1}}(\text{mod } p)=(yy^{-1})^{y^{-1}}(\text{mod } p)=1$.
The following Python script implements this solution.
from pwn import *
conn = remote("localhost", 4000)
conn.recvuntil(b"p =")
p = int(conn.recvline())
conn.recvuntil(b"g =")
g = int(conn.recvline())
conn.recvuntil(b"y =")
y = int(conn.recvline())
m = 0
r = pow(y, -1, p)
s = r
conn.recvuntil(b">>> ")
conn.sendline(str(m).encode())
conn.recvuntil(b">>> ")
conn.sendline(str(r).encode())
conn.recvuntil(b">>> ")
conn.sendline(str(s).encode())
conn.interactive()