"""
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"))