solve.py

#coding=utf-8
import os
import socket
import select
from time import sleep
import binascii

class Client(object):

  def __init__(self):
    self.host = '52.0.217.48'
    self.port = 60231
    # self.host = "localhost"
    # self.port = 60231
    self.buffer = ''
    self.timeout = 0.5

    self.client = socket.socket(socket.AF_INET, socket.SOCK_STREAM)
    self.client.connect((self.host,self.port))
    self.client.setblocking(1)

  def read(self):
    while True:
      ready = select.select([self.client], [], [], self.timeout)
      if ready[0]:
          data = self.client.recv(4096)
          if data == "": break
          self.buffer += data
      else:
        break
    if self.buffer == "":
      return None
    s = self.buffer.split('\n')
    self.buffer = ""
    ret = s[0]
    if len(s) != 1:
      self.buffer = '\n'.join(s[1:])
    return ret

  def send(self,val):
      self.client.sendall(val)
      sleep(0.1)

  def close(self):
    self.client.close()

print "-" * 80  # 区切り表示(開始)

cl = None

def nl():
  val = cl.read()
  if val is not None:
    print "<Read> : " + val
  return val

def wt(b):
  print "<Write> : " + b
  cl.send(b)

def warr(b):
  x = ''.join([chr(i) for i in b])
  print b
  wt(x)

from dsa_prime import SAFEPRIME, GENERATOR
from dsa_key import PUBKEY, SECKEY
import json,hashlib

def elgamal_verify(r, s, m):
    if r <= 0 or r >= SAFEPRIME:
        return False
    if s <= 0 or s >= SAFEPRIME-1:
        return False
    h = int(hashlib.sha384(m).hexdigest(), 16)
    left = pow(GENERATOR, h, SAFEPRIME)
    right = (pow(PUBKEY, r, SAFEPRIME) * pow(r, s, SAFEPRIME)) % SAFEPRIME
    return left == right

def egcd(a, b):
    (x, lastx) = (0, 1)
    (y, lasty) = (1, 0)
    while b != 0:
        q = a / b
        (a, b) = (b, a % b)
        (x, lastx) = (lastx - q * x, x)
        (y, lasty) = (lasty - q * y, y)
    return (lastx, lasty, a)

# ax ≡ 1 (mod m)
def modinv(a, m):
    (inv, q, gcd_val) = egcd(a, m)
    return inv % m

from fractions import gcd

def gen_json():
    l = []
    rd = set()
    same_r = None
    for i,sig_text in enumerate(open('use.txt', 'r').read().split('\n')[:-1]):
        sig = json.loads(sig_text)
        r = sig["r"]
        s = sig["s"]
        m = sig["m"]
        h = int(hashlib.sha384(m).hexdigest(), 16)
        l.append((r,s,h))
        if r in rd:
          same_r = r
        rd.add(r)

    rsh_1,rsh_2 = [(r,s,h) for r,s,h in l if r == same_r]
    r1,s1,h1 = rsh_1
    r2,s2,h2 = rsh_2
    assert r1 == r2

    x1 = pow(5, h1, SAFEPRIME)
    x2 = pow(5, h2, SAFEPRIME)
    y1 = pow(same_r,s1,SAFEPRIME)
    y2 = pow(same_r, s2, SAFEPRIME)
    assert x1 == pow(PUBKEY,same_r,SAFEPRIME) * y1 % SAFEPRIME
    assert x2 == pow(PUBKEY,same_r,SAFEPRIME) * y2 % SAFEPRIME

    x1divx2 = x1 * modinv(x2,SAFEPRIME) % SAFEPRIME
    x1divx2_ = pow(5,h1 - h2,SAFEPRIME)
    y1divy2 = y1 * modinv(y2,SAFEPRIME) % SAFEPRIME
    y1divy2_ = pow(same_r,s1 - s2,SAFEPRIME)
    assert x1divx2 == x1divx2_
    assert y1divy2 == y1divy2_
    assert x1divx2 == y1divy2

    h12 = (h1 - h2)
    s12 = (s1 - s2)
    (inv, q, gcd_val) = egcd(s12, SAFEPRIME - 1)
    inv%= SAFEPRIME-1
    assert pow(same_r,s12,SAFEPRIME) == pow(5,h12,SAFEPRIME)
    assert same_r **2 % SAFEPRIME == pow(5,h12 * inv,SAFEPRIME)
    u1 = s1 / 2 * (h12 * inv) % (SAFEPRIME - 1)
    assert pow(same_r,s1,SAFEPRIME) == pow(5,u1,SAFEPRIME)
    v1 = (h1 - u1) % (SAFEPRIME-1)
    assert pow(5,v1,SAFEPRIME) == pow(PUBKEY,same_r,SAFEPRIME)

    (inv2, q2, gcd_val2) = egcd(same_r, SAFEPRIME - 1)
    assert gcd_val2 == 2
    c = v1 * inv2 % (SAFEPRIME-1)
    assert pow(5,c,SAFEPRIME) == PUBKEY**2 % SAFEPRIME

    r3,s3,h3 = [None] * 3
    for r,s,h in l:
      if r % 2 == 0 and gcd(s,SAFEPRIME-1) == 1:
         r3,s3,h3 = r,s,h
         break

    assert pow(5,(h3 - r3 / 2 * c) % (SAFEPRIME-1),SAFEPRIME) == pow(r3,s3,SAFEPRIME)
    s3inv = modinv(s3,SAFEPRIME-1)
    w = (h3 - r3 / 2 * c) * s3inv % (SAFEPRIME-1)
    assert  pow(5,w,SAFEPRIME)  == r3
    x = r3 / 2 * c

    message = "There is no need to be upset"
    hans = int(hashlib.sha384("There is no need to be upset").hexdigest(), 16)
    rans = r3
    sans = (hans  - x) * modinv(w,SAFEPRIME-1) % (SAFEPRIME-1)

    assert elgamal_verify(rans,sans,message)

    return '{ "s":%s ,"r":%s, "m":"%s" }' % (sans,rans,message)

    # print h1
    # print h2
    # print h3

    # for i in xrange(1,10**5):
    #   use = pow(5,i,SAFEPRIME - 1)
    #   if use % 2 == 0:
    #     print i
    #     break

    # print h1 > h2
    # print s1 > s2
    # left = pow(5,h1 - h2,SAFEPRIME)
    # right = pow(5,s1 - s2,SAFEPRIME)

import subprocess

def sha1(ca):
  print "sha1input : ", ca
  outp = subprocess.check_output("./sha " + ca,shell=True)
  print "sha1output : ", outp
  return outp

def captcha():
  ca = None
  while ca is None:
    ca = nl()
  p = sha1(ca)
  return p

def main():
  # sha1("123456789012")
  ans = gen_json()
  global cl
  cl = Client()
  capt = captcha()[:20]
  wt(capt + ans)
  hoge = None
  while hoge is None:
    hoge = nl()

main()