title: ElGamal Signature: Re-Calculate private key with Python
body: <p>For a project in university I got the following set up:</p>
  <ul>
  <li>Public key (p, g, h)</li>
  <li>Two ciphertext-files: (c1, c2) &amp; (c3, c4)</li>
  <li>Signature files of the above mentioned files: (r1, s1) &amp; (r2, s2)</li>
  </ul>
  <p>The goal is to recover the plaintexts.</p>
  <p>I recognized from the signature files, that the given r-values are the same (r1 = r2 = r). This leads to the possibility of re-calculating the used private key <a href="https://crypto.stackexchange.com/questions/1479/elgamal-signature-scheme-recovering-the-key-when-reusing-randomness">see</a>.</p>
  <p>Basically I need the two algorithms:</p>
  <blockquote>
  <p>k ≡ (m1 − m2)(s1 − s2)^−1 mod (p−1)</p>
  <p>k ≡ (m1 / (s1 - s2) - m2 / (s1 - s2)) mod (p-1)</p>
  </blockquote>
  <p>and then</p>
  <blockquote>
  <p>x ≡ (m1 − k*s1)r^−1 mod (p−1)</p>
  <p>x ≡ (m1 / r - k * s1 / r) mod (p-1)</p>
  </blockquote>
  <p>So I thought that writing a python program implementing the algorithms mentioned in the link should not be that hard. But I got stucked.
  For some reasons I don't get the right values from my calculations. Maybe someone can give me some nudge in here?</p>
  <pre><code>import random
  import base64
  from gmpy2 import *
  from Crypto.Util.number import inverse
  from binascii import hexlify, unhexlify
  
  g = 262470350957996892686231567...
  p = 394020061963944792122790401...
  h = 114121123070543781308127611...
  
  def getSign(file):
      enc_file = open(file, &quot;rb&quot;)
      enc_byte = enc_file.read()
      r, s = (enc_byte.decode(&quot;utf-8&quot;)).split()
      return r, s
  
  def getMess(file):
      enc_file = open(file, &quot;rb&quot;)
      enc_base64 = enc_file.read()
      enc_byte = base64.decodebytes(enc_base64)
      c1, c2 = (enc_byte.decode(&quot;utf-8&quot;)).split()
      c1, c2 = int(c1), int(c2)
      return c1, c2
  
  def decrypt(c1, c2, a):
          df = pow(c1, a, p)
          m = (c2 * inverse(df, p)) % p
          return m
  
  r1, s1 = getSign(&quot;secret1.enc.sig&quot;)
  c11, c12 = getMess(&quot;secret1.enc&quot;)
  r2, s2 = getSign(&quot;secret2.enc.sig&quot;)
  c21, c22 = getMess(&quot;secret2.enc&quot;)
  
  if(r1 == r2):
      r = int(hexlify(str.encode(r1)), 16)
      
      s1_hex = hexlify(str.encode(s1))
      s1_int = int(s1_hex, 16)
      
      s2_hex = hexlify(str.encode(s2))
      s2_int = int(s2_hex, 16)
  
      m1 = c12
      m2 = c22
      
      ds = s1_int - s2_int
      ps = p - 1
      k1 = (m1 * inverse(ds, ps)) % ps
      k2 = (m2 *  inverse(ds, ps)) % ps
      k = k1 - k2
      print(&quot;k  = {}&quot;.format(k))
  
      x1 = (m1 * inverse(r, ps)) % ps
      x21 = k * s1_int
      x2 = (x21 * inverse(r, ps)) % ps
      x = x1 - x2
      
      dm = decrypt(c21, c22, x)
      x = format(dm, 'x')
      message = unhexlify(x)
      
      print(&quot;g  = {}&quot;.format(g))
      print(&quot;p  = {}&quot;.format(p))
      print(&quot;h  = {}&quot;.format(h))
      print(&quot;r  = {}&quot;.format(r))
      print(&quot;k  = {}&quot;.format(k))
      print(&quot;x  = {}&quot;.format(x))
      print(&quot;Decrypted Hex (x)     : {}&quot;.format(x))
      print(&quot;Decrypted Message     : {}&quot;.format(message))
  </code></pre>