Forging Digital Signatures

#!/usr/bin/python from blessings import Terminal import sys, getopt, socket, json, hashlib, random, gmpy2 from timeit import default_timer as timer ######################################################################################### # These two functions should be of help to you. The first computes the modular inverse. # # You can also use gmpy2.invert(a,b) # # The second function computes an ElGamal Signature. # ######################################################################################### def modInv(a,b): # Generate a^(-1) mod b #print a #print b (A1,A2,A3) = (1,0,a) (B1, B2, B3) = (0,1,b) while(B3 > 1): Q = A3/B3 (T1,T2,T3) = (A1-Q*B1,A2-Q*B2,A3-Q*B3) (A1,A2,A3) = (B1,B2,B3) (B1,B2,B3) = (T1,T2,T3) if (B3==0): # there is no modular inverse print "No modInv" return -1 #gcd(a,b)=A3 if (B3 == 1): # modular inverse is B1 if (B1 < 0): B1 = B1 + b return B1 # This should never happen... print "Blerg" return -1 def sign(m, p, g, x): s=0 while(s==0): k = random.randint(p/2,p/2+20) while (modInv(k, p-1)<0): k = random.randint(p/2,p/2+20) r = gmpy2.powmod(g, k, p) print hex(r) h = int(hashlib.sha256(m).hexdigest(), 16) #print "Hash: " + str(h) kInv = modInv(k, p-1) s = ((h-(x*r))*kInv) % (p-1) return (r,s) ########################################################################### # This code will connect you to the server and retrieve the data you need # ########################################################################### BUFFER_SIZE = 2048 port=4635 host="192.168.1.40" print "Connecting to port " + str(port) # Create a TCP/IP socket sock = socket.socket(socket.AF_INET, socket.SOCK_STREAM) try: # Connect the socket to the port where the server is listening server_address = (host, port) #print >>sys.stderr, 'connecting to %s port %s' % server_address sock.connect(server_address) print 'Connected to %s port %s' % server_address except socket.error: print >>sys.stderr, "Could not connect to the server" exit(1) sock.send("0\n") params = sock.recv(2048) (p,g,y) = params.split(",") p=int(p) g=int(g) y=int(y) print "P: " + str(int(p)) print "G: " + str(int(g)) print "Y: " + str(int(y)) sock.send("3\n") targetMessage=sock.recv(2048).rstrip() print "Need to forge a signature for " + targetMessage ####################################################################### # This function will retrieve a message and signature from the server # ####################################################################### def getMessageAndSig(): sock.send("1\n") (m,r,s) = sock.recv(2048).rstrip().split("+") return (m,r,s) # This is an infinite loop, since sometimes the repeated r values don't let us find sInv # If you cannot compute sInv, just continue to hte next iteration of the loop while True: print "Starting the search:" print '-'*75 rs = {} (m,r,s) = getMessageAndSig() rs[r]=s+"+"+m (m,r,s) = getMessageAndSig() while r not in rs: rs[r] = s+"+"+m (m,r,s) = getMessageAndSig() print "Repeated R: " + str(int(r,16)) (firsts, firstm) = rs[r].split('+') print "First S: " + str(int(firsts,16)) print "Second S: " + str(int(s,16)) print "First M: " + firstm print "Second M: " + m r = int(r, 16) s1 = int(firsts,16) s2 = int(s,16) hm1 = int(hashlib.sha256(firstm).hexdigest(), 16) hm2 = int(hashlib.sha256(m).hexdigest(), 16) print "H1: " + str(hm1) print "H2: " + str(hm2) # At this point, we have a repeated r value and we have our hm1 and hm1, and s1 and s2 # Now it is up to you to compute k and then x # When you have found x, verify that it is correct by comparing pow(g,x,p) to y # If they don't match, just continue again # TODO # Assuming you have found the correct value for x # this will compute the signature and submit it print "Signing" (signR, signS) = sign(targetMessage,p,g,x) sock.send("4:"+str(signR)+","+str(signS)) print sock.recv(2048) # this will break out of the infinite loop, since you are done! exit()