cryptohack adrien_signs

adrien_sign.py

def pohligHellmanPGH(p,g,h):
  #p is the modulus
  #g is the argument (a)
  #h is the equivalence class i.e the result of pow(g,e,p). e is what we are looking for
	F=IntegerModRing(p)
	g=F(g)
	h=F(h)
	G=[]
	H=[]
	X=[]
	c=[]
	N=factor(p-1)
	for i in range(0,len(N)):
		G.append(g^((p-1)/(N[i][0]^N[i][1])))
		H.append(h^((p-1)/(N[i][0]^N[i][1])))
		X.append(log(H[i],G[i]))
		c.append((X[i],(N[i][0]^N[i][1])))

	#Using Chinese Remainder
	c.reverse()
	
	for i in range(len(c)):
		if len(c) < 2:
			break
		t1=c.pop()
		t2=c.pop()
		r=crt(t1[0],t2[0],t1[1],t2[1])
		m=t1[1]*t2[1]
		c.append((r,m))
	
	return c[0][0]
end

nums = list(open('output','r').read().strip().replace('[','').replace(']','').split(', '))
bitstring = ''
for h in nums:
  h = int(h)
  try:
    e = pohligHellmanPGH(p,g,h)
    bitstring += '1'
  except Exception as e:
    bitstring += '0'

print(bitstring)

#convert the above bitstring to an integer
bit_int = int(bitstring,2)
#convert the int above to bytes : assuming we have byte sizes of 8
bytes_val = bit_int.to_bytes((bit_int.bit_length() + 7 // 8),'big')
print(bytes_val.decode())