#! /usr/bin/env python
##
# Script for PicoCTF SmallRSA challenge
# Created by Amos (LFlare) Ng
##
import binascii

# Imports courtesy of @pablocelayes
import continuedfractions
import arithmetic

# Values we are given
e = 165528674684553774754161107952508373110624366523537426971950721796143115780129435315899759675151336726943047090419484833345443949104434072639959175019000332954933802344468968633829926100061874628202284567388558408274913523076548466524630414081156553457145524778651651092522168245814433643807177041677885126141
n = 380654536359671023755976891498668045392440824270475526144618987828344270045182740160077144588766610702530210398859909208327353118643014342338185873507801667054475298636689473117890228196755174002229463306397132008619636921625801645435089242900101841738546712222819150058222758938346094596787521134065656721069
c = 2729869850246221096831391096846794169956396740264942203903703342885290746934874117725386729017627214993949187059358671448548783102300956256114813913061908317052353475608677702004762353569798758999446296443701747957565699931341341707067812649227617863345146556649686184642966609793205244209896583560093620273

# Courtesy of @pablocelayes
# I'm too lazy to rebuild a library. Thanks mate.
def hack_RSA(e,n):
    '''
    Finds d knowing (e,n)
    applying the Wiener continued fraction attack
    '''
    frac = continuedfractions.rational_to_contfrac(e, n)
    convergents = continuedfractions.convergents_from_contfrac(frac)
    
    for (k,d) in convergents:
        if k!=0 and (e*d-1)%k == 0:
            phi = (e*d-1)//k
            s = n - phi + 1
            discr = s*s - 4*n
            if(discr>=0):
                t = arithmetic.is_perfect_square(discr)
                if t!=-1 and (s+t)%2==0:
                    return d

# Attempt to derive D
d = hack_RSA(e, n)

# Decrypt c to m
m = pow(c, d, n)
message = binascii.unhexlify(format(m, 'x')).decode()
print(message)