Challenge description
This challenge is based on a weak el-gamal signature implementation. The goal is to be able to give a valid signature of a message m given by the server wiithout knowing the secret key x and $y=g^x$. What we know:
- g = 2
- m given by the server
- p prime given by the server
- p % 4 = 1
We need to provide r and s such as: $2^m = y^r r^s$
Solution
First of all, as we do not know y we need to provide r that will eliminates it.
With r = $\frac{p-1}{2}$ we have $y^r = (y^{p-1})^{\frac{1}{2}}$ According to the Fermat’s little theorem we have that $y^{p-1} = 1$ then $y^r= 1^{\frac{1}{2}} = 1$ or $-1$ (square root of 1).
Now we need s such as $g^m =$ + or $-(\frac{p-1}{2})^s$.
As the equations stand in $\mathbb{Z}/p\mathbb{Z}$ we have $p-1 = -1$ so $(\frac{p-1}{2})^{-1} = (\frac{-1}{2})^{-1}=-2$.
Then if we choose $s = -m$, $r^{-m}=((\frac{p-1}{2})^{-1})^m = (-2)^m = 2^m(-1)^m$
So with these values of r and s sometimes (if $y^r = 1$ and m is even so $(-1)^m=1$, or when $y^r = -1$ and m is odd) $y^r r^s = 2^m$. Because of the “sometimes” you might need to run your script a few times before getting the flag.
Necessary lib:
from pwn import *
from Cryptodome.Util.number import inverse
First of all this is a remote challenge and here is how we can use pwtools to receive the parameters depending on the format of the output of the server:
address = ("localhost", 4000)
conn = remote(address[0], address[1])
def sendAndRecieve(line):
conn.sendline(line)
return conn.recvline().decode().strip()
conn.recvline()
l = (conn.recvuntil(b'g')).decode().split(' ')
p = int(l[2][:-2])
conn.recvuntil(b'm = ')
l = (conn.recvuntil(b'>>>')).decode().split(' ')
m = int(l[0][:-6])
Then we send our values for r and s:
r = (p-1)//2
s = (-m % (p-1))
l = sendAndRecieve(str(r).encode())
l = sendAndRecieve(str(s).encode())
print(l)
#print the flag
print(conn.recvline())