""" Get numbthy module from http://www.cl.cam.ac.uk/~rx201/numbthy.py It has various number theory funtions that can be handy. Python's native integer type is multiprecision-capable, which means addition("+"), subtraction("-"), multiplication("*") and modulo("%") can be used directly. To perform division in the multiplicative field, use the provided function div(a,b,n), as div(a,b,n) * b == a (mod n) """ from numbthy import powmod,xgcd """ Compute a/b in Z(n), it will raise an assertion error if b has no multiplicative inverse. """ def div(a,b,n): g,x,y = xgcd(b,n) assert g == 1 return ((x*a % n) + n) % n p = 0xF14B06B1EB g = 2 k = 0x5FBB67D614 ##powmod(g, ????, p) def solve(g,k,p): ## Your turn now. pass """ Once you have the private key, you can view my own attempt here by print show_solution(private key here as integer, ct.decode("hex")) """ ct = "6280a67b27b1dce7396cd1add02cebdf203fb5bd6e160fbdf324df4e380395a45a8b7d059e3a0413ea0a00aa10dfb2703b35d58ec5325455e43543403c5ebc24863912b7f17af57de466dcc588aca155e6989738fb23ea74ee34311ae488ed656063ad642d7310bb56ff43e3e889b88dfbb87176f8e309501c0ab3f711def354ea66fab60739753315a069d047af2583e17ff66ef49465ed7f5d88807a3e15ad185cffb70605e0e5e18f316a6f8f3b022ff09054ebdd56999549c7d59ac401ac8cc56f570315e835b3e58bb3bda584fa093fb927df507ed4ba47a948f85ec6c037382d0261b4c1535770e130c82991e11ce6d9701e6adceab75112e8f7f4bd0d88cb69bed6282663b64a0055a946feb78446834b0dd46e6dfdf0a71c891b4c2cd8d36055f985025d593aaf43601536388362e083ba7c" def show_solution(key, ciphertext): import hashlib bkey = hashlib.sha256(str(key)).digest() otp = "".join([hashlib.sha256(bkey+str(i)).digest() for i in range((len(ciphertext)+31) / 32)]) return "".join([chr(ord(x) ^ ord(y)) for (x,y) in zip(ciphertext, otp)]) if __name__ == "__main__": pk = solve(g,k,p) assert k == powmod(g, pk, p) print "The private key is", pk print show_solution(pk, ct.decode("hex"))