El-Gamal signature with two messages

Question

Alice uses an ElGamal signature with base the group $Z^*_{107}$ and parameter $g=3$ of order $q=53$.The private key of Alice is some $x \in \{0,1,.....,52\}$ and the public key of her is $y=10$. To sign the message m, she calculates $r=g^k \bmod107$ for $k \in \{0,1,......,52\}$ and $s=(k \cdot h(m)+r\cdot x) \bmod 53$. For signing the first message, Alice chooses a random $k_1 \in \{0,1,......,52\}$. To sign the second message she uses $k_2=(2 \cdot k_1 +1) \bmod 53$ and generally if for the signature of $i$-th message she has used the $k_i$ for the $(i+1)$-th message she uses the $k_{i+1}=(2\cdot k_i +1)\bmod 53$. You know two successive signatures of Alice: $(r,s)=(79,7)$ of message $m$ with $h(m)=2$ and the signature $(r',s')=(105,41)$ of message $m'$ with $h(m')=3$. Find the private key of Alice (of course withουt calculating directly any discrete logarithm in group $Z^*_{107}$)

I am trying to solve this. I tried to apply the ElGamal Algorithm but I do not know how to use the $h(m)$ hash function. Can anyone help to solve it and help me how to use correct the ElGamal signature?
(source: mathematical competition 2008,France)

Answer 1

Before continuing to read this answer, read my above hint:

Try writing down all the equations for the different s and try to solve the system of equations.

If you still can't solve this one, you may read the remainder of the answer.

First observe that $s_1 \equiv k_1 \cdot h(m) + r_1\cdot x \pmod {53}$ and $s_2 \equiv k_2 \cdot h(m') + r_2\cdot x \pmod {53}$ where only $k_1,k_2,x$ are unknown. So 3 variables for 2 equations, which isn't solvable, right?
Here's where the special relation comes into play. Replace $k_2$ by $2k_1+1$ which yields

$s_2\equiv (2k_1 + 1) \cdot h(m') + r_2\cdot x\equiv 2k_1\cdot h(m') + h(m') + r_2\cdot x \pmod {53}$

Now subtract the first equation twice times $h(m')$ from the second equation times $h(m)$ which yields:

$s_2\cdot h(m) - 2\cdot h(m')\cdot s_1 \equiv h(m)\cdot h(m')+r_2 \cdot h(m)\cdot x - 2r_1 \cdot h(m') \cdot x \equiv h(m)\cdot h(m')+ x \cdot (r_2\cdot h(m) - 2r_1\cdot h(m')) \pmod {53}$

Finally multiply by the inverse of $r_2\cdot h(m) - 2r_1\cdot h(m')$ ($=(r_2\cdot h(m) - 2r_1\cdot h(m'))^{-1}\bmod 53$) and subtract $h(m)\cdot h(m')$. This gives us the following equation for retrieving $x$:

$x = (s_2\cdot h(m) - 2\cdot h(m')\cdot s_1)\cdot (r_2\cdot h(m) - 2r_1\cdot h(m'))^{-1} - h(m)\cdot h(m') \bmod 53$

Answer 2

Key generation

• Select prime p and a generator g;

• Sender S selects a random integer r (secret key) such that

  0 < r < p − 1 and calculates K=(g^r)(modp);

  K, g and p are in public domain;

Signing

• To authenticate message M, the sender selects another random integer R (0 < R < p − 1 and gcd(R,p-1)=1 and computes

  X=(g^R)(modp);

• The sender finds Y such that M=rX+RY mod(p-1); (X,Y) is the signature of M:

  M=rX+RY mod(p-1)

  Y = ? mod (p-1)

  RY = (M – rX) mod (p-1)

  Y = (M – rX) R-1 mod (p-1)

Verification

• The receiver B gets (M, X, Y) and computes A=(K^X)(X^Y)modp; (X,Y) is called the authenticator.
• B accepts M if and only if A=g^M(modp).

Hope this helps.