1
$\begingroup$

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)

$\endgroup$
  • $\begingroup$ hint: Try writing down all the equations for the different s and try to solve the system of equations. $\endgroup$ – SEJPM Jul 24 '15 at 18:54
  • $\begingroup$ how many equations would be? $\endgroup$ – Paris Lamp Jul 24 '15 at 19:06
  • $\begingroup$ two should be enough $\endgroup$ – SEJPM Jul 24 '15 at 19:15
  • $\begingroup$ I've just quickly done the proposed calculations, you may or may not want to read the answer before figuring it out yourself. $\endgroup$ – SEJPM Jul 24 '15 at 19:32
  • $\begingroup$ @ SEJPM I am gon try to solve it, if i stuck somewhere i ll check the answer and ill tell you $\endgroup$ – Paris Lamp Jul 24 '15 at 20:38
1
$\begingroup$

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$

$\endgroup$
  • $\begingroup$ we don't use the public key $y=10$? $\endgroup$ – Paris Lamp Jul 25 '15 at 17:57
  • $\begingroup$ @paris, obviously not (other than for maybe verifying the private key $x$), we also don't need $g$ other than for maybe verifying the order and we don't need $q$ other for verifying the order. I made these calculations as efficient as possible $\endgroup$ – SEJPM Jul 25 '15 at 18:51
0
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Am I reading this right, that this is the definition of ElGamal signatures? $\endgroup$ – SEJPM Jul 24 '15 at 19:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.