#!/user/bin/env

--coding: utf-8 --ppython3

from Crypto.Util.number import sieve_base, bytes_to_long, getPrime,long_to_bytes
import libnum
import gmpy2

e = 11850552481503020257392808424743510851763548184936536180317707155841959788151862976445957810691568475609821000653594584717037528429828330763571556164988619635320288125983463358648887090031957900011546300841211712664477474767941406651977784177969001025954167441377912326806132232375497798238928464025466905201977180541053129691501120197010080001677260814313906843670652972019631997467352264392296894192998971542816081534808106792758008676039929763345402657578681818891775091140555977382868531202964486261123748663752490909455324860302967636149379567988941803701512680099398021640317868259975961261408500449965277690517
n = 12238605063252292170613110607692779326628090745751955692266649177882959231822580682548279800443278979485092243645806337103841086023159482786712759291169541633901936290854044069486201989034158882661270017305064348254800318759062921744741432214818915527537124001063995865927527037625277330117588414586505635959411443039463168463608235165929831344586283875119363703480280602514451713723663297066810128769907278246434745483846869482536367912810637275405943566734099622063142293421936734750356828712268385319217225803602442033960930413469179550331907541244416573641309943913383658451409219852933526106735587605884499707827
c = 4218884541887711839568615416673923480889604461874475071333225389075770098726337046768413570546617180777109293884545400260353306419150066928226964662256930702466709992997796154415790565112167663547017839870351167884417142819504498662037048412313768450136617389372395690363188005647619061128497371121168347810294424378348301835826084732747005110258557662466626720961279087145559906371505117097599774430970980355531235913439823966628008554872896820907555353892843539526041019103819804854883231421963308265517622470779089941078841902464033685762524196275032288319744157255628189204988632871276637699312750636348750883054

#winner attack
def transform(x,y): #使用辗转相处将分数 x/y 转为连分数的形式
res=[]
while y:
res.append(x//y)
x,y=y,x%y
return res

def continued_fraction(sub_res):
numerator,denominator=1,0
for i in sub_res[::-1]: #从sublist的后面往前循环
denominator,numerator=numerator,i*numerator+denominator
return denominator,numerator #得到渐进分数的分母和分子，并返回

#求解每个渐进分数
def sub_fraction(x,y):
res=transform(x,y)
res=list(map(continued_fraction,(res[0:i] for i in range(1,len(res))))) #将连分数的结果逐一截取以求渐进分数
return res

def get_pq(a,b,c): #由p+q和pq的值通过维达定理来求解p和q
par=gmpy2.isqrt(bb-4ac) #由上述可得，开根号一定是整数，因为有解
x1,x2=(-b+par)//(2a),(-b-par)//(2*a)
return x1,x2

def wienerAttack(e,n):
for (d,k) in sub_fraction(e,n): #用一个for循环来注意试探e/n的连续函数的渐进分数，直到找到一个满足条件的渐进分数
if k==0: #可能会出现连分数的第一个为0的情况，排除
continue
if (ed-1)%k!=0: #ed=1 (mod φ(n)) 因此如果找到了d的话，(ed-1)会整除φ(n),也就是存在k使得(ed-1)//k=φ(n)
continue

    phi=(e*d-1)//k               #这个结果就是 φ(n)
    px,qy=get_pq(1,n-phi+1,n)
    if px*qy==n:
        p,q=abs(int(px)),abs(int(qy))     #可能会得到两个负数，负负得正未尝不会出现
        d=gmpy2.invert(e,(p-1)*(q-1))     #求ed=1 (mod  φ(n))的结果，也就是e关于 φ(n)的乘法逆元d
        return d
print("该方法不适用")
​

d=wienerAttack(e,n)
print("d=",d)
m=pow(c, d, n)
print(long_to_bytes(m))