from Crypto.Util.number import *
from sage.all import *

def wiener(e, n, c):
    
    lst = continued_fraction(Integer(e)/Integer(n))
    convList = lst.convergents()
    #print(len(convList))
    for i in convList:
	#m = pow(12345, e, 
    	k = i.numerator()
    	
    	d = int(i.denominator())   
    	#print "d: ", d		
    	m = long_to_bytes((pow(c, d, n)))	
    	print(m)
    	
    	if "inctf" in m:
		print "Mila: ", m
		break
    	else:
    		continue
    

#keeping keys in a list
keys = [34961, 3617491, 68962801, 293200159531, 1191694878666066510321450623792489136756229172407332230462797663298426983932272792657383336660801913848162204216417540955677965706955404313949733712340714861638106185597684745174398501025724130404133569866642454996521744281284226124355987843894614599718553178595963014434904833]
e1 = 1

for e in keys:
	e1 *= e


cipher = "5d695edb47b81a303d162611f7d407579160ef8818929031e1e13ca20cb7094eddbb0658d95980e1753182c5d5c529fb45062891bb5da573c618e35df0103233ded582a53ed807846b19ea82be427f2bbc63e5c7eb685d8a22b2b7539cf45d4ad93bbf5b892b66288b568b6bbff6bb263d809475e6f0aa3cfd01539d8364c243"
ciphertext = bytes_to_long(cipher.decode("hex"))


n = 135568509670260054049994954417860747085442883428459182441559553532993752593294067458983143521109377661295622146963670193783017382697726454953197805014428888491744355387957923382241961401063461549210355871385000347645387907568135032087942016502668629010859519249039662555733548461551175133582871220209515648241

'''Before encryption, the public key exponent e is manipulated multiple times(count of 5).
As shown, c1 = m^e1 % n 
          c2 = (m^e1 % n) ^ e2 % n  or c2 = c1 ^ e2 % n
		   c3 = c2 ^ e3 % n
		   c4 = c3 ^ e4 % n
		   c5 = c4 ^ e5 % n
 So, there are 5 ciphertexts in total but we are provided with the last, i.e., c5

 rewriting c5, gives 
	c5 = ((m^e1)*(m^e2)*(m^e3)*(m^e4)*(m^e5)) % n    which can further be written as
    c5 = m^(e1*e2*e3*e4*e5) % n
    now, the challenge can be easily solved as we have all that we need.
        we may try wiener's attack 
    conditions necessary, d < 1/3*(pow(n, 1/4))
    calling wiener with n and e = e1*e2*e3*e4*e5'''

wiener(e1, n, ciphertext)
