MHB How can we find the private key?

  • Thread starter Thread starter mathmari
  • Start date Start date
AI Thread Summary
Alice utilizes the ElGamal signature scheme with parameters p=47, q=23, and g=2, generating signatures for two messages with identical r values. The correct relations for the signatures are clarified as s1=k1^{-1}(h(m1)+ar1) and s2=k2^{-1}(h(m2)+ar2), indicating that k1 and k2 are equal due to the shared r value. By substituting the known values into these equations, two equations can be formed with the unknowns k and a. This method allows for the calculation of Alice's private key without needing to compute a discrete logarithm. The discussion emphasizes the importance of correctly interpreting the signature equations for solving the problem.
mathmari
Gold Member
MHB
Messages
4,984
Reaction score
7
Hey! :o

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)
 
Mathematics news on Phys.org
mathmari said:
Hey! :o

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.
 
Ok... Thanks a lot! (flower)
 
mathmari said:
Ok... Thanks a lot! (flower)

You are welcome. :)
 
Seemingly by some mathematical coincidence, a hexagon of sides 2,2,7,7, 11, and 11 can be inscribed in a circle of radius 7. The other day I saw a math problem on line, which they said came from a Polish Olympiad, where you compute the length x of the 3rd side which is the same as the radius, so that the sides of length 2,x, and 11 are inscribed on the arc of a semi-circle. The law of cosines applied twice gives the answer for x of exactly 7, but the arithmetic is so complex that the...
Is it possible to arrange six pencils such that each one touches the other five? If so, how? This is an adaption of a Martin Gardner puzzle only I changed it from cigarettes to pencils and left out the clues because PF folks don’t need clues. From the book “My Best Mathematical and Logic Puzzles”. Dover, 1994.
Thread 'Imaginary Pythagoras'
I posted this in the Lame Math thread, but it's got me thinking. Is there any validity to this? Or is it really just a mathematical trick? Naively, I see that i2 + plus 12 does equal zero2. But does this have a meaning? I know one can treat the imaginary number line as just another axis like the reals, but does that mean this does represent a triangle in the complex plane with a hypotenuse of length zero? Ibix offered a rendering of the diagram using what I assume is matrix* notation...
Back
Top