How can we find the private key?

[mathmari]

Hey!

Alice uses the ElGamal signature scheme with the variables $p=47$, $q=23$ and $g=2$. For two different messages $m_1, m_2$ with $h(m_1)=4, h(m_2)=3$ she produces the signatures $(r_1, s_1)=(14, 8)$ and $r_2, s_2)=(14, 15)$. Calculate the private key of Alice, without calculating a discrete logarithm.

We have the following relations: $$r_1=g^{k_1} \ \ , \ \ s_1=k_1^{-1}(h(m_1)+af(r))\pmod q \\ r_1=g^{k_2} \ \ , \ \ s_2=k_2^{-1} (h(m_2)+af(r))\pmod q$$

What can we do to find $a$ ?? (Wondering)

 

[Sudharaka]

Hey!

Alice uses the ElGamal signature scheme with the variables $p=47$, $q=23$ and $g=2$. For two different messages $m_1, m_2$ with $h(m_1)=4, h(m_2)=3$ she produces the signatures $(r_1, s_1)=(14, 8)$ and $r_2, s_2)=(14, 15)$. Calculate the private key of Alice, without calculating a discrete logarithm.

We have the following relations: $$r_1=g^{k_1} \ \ , \ \ s_1=k_1^{-1}(h(m_1)+af(r))\pmod q \\ r_1=g^{k_2} \ \ , \ \ s_2=k_2^{-1} (h(m_2)+af(r))\pmod q$$

What can we do to find $a$ ?? (Wondering)

Hi mathmari,

I don't understand the $f$ in your relations. The relations should be,

\[s_1=k_1^{-1}(h(m_1)+ar_1)\pmod q \]

\[s_2=k_2^{-1} (h(m_2)+ar_2)\pmod q$\]

Refer: https://en.wikipedia.org/wiki/ElGamal_signature_scheme

Note that, $r_1=g^{k_1}\mbox{ and }r_2=g^{k_2}$. Since $r_1=r_2$ it implies that, $k_1=k_2=k$.

Now all you a got to do is substitute the given values into the equations and you'll get two equations with $k$ and $a$ as unknowns.

 

[mathmari]

Ok... Thanks a lot! (flower)

 

[Sudharaka]

Ok... Thanks a lot! (flower)

You are welcome. :)