1
import math
2

3
n = 30610867131545893573245403370929044810375908252345734515216335567761070674235240557970829245356614030481955825874376565524126172250295479286829004996105122106474627414932278394880727207687247106535964451736524423676062227917939094755601312619938974463767105253817030590414646900543888347805544511989816392901347341338737906837896070023751031260815782973250734600300683094949304509692321753534435264794596296780586539085130232106649876660029506699244567866816756904364396378546670735017278059889632347338673055259053699246622809620909022329749464060132071464884484682112534813343645706384624586841979729464134335809829
4
e = 13118943056376811531390887158969590633018246393862457649378429529040458860386531667701783962295691727349409639660447099510339788107269491122926716426902195188489126034970976454948883089008820188515413336458510467289740954821973897752400562551402417627328759394493013110177705814518809291916661933709921311243284600780240090861401353930215487292827235572235250164436683130292475464090785626013810206032736933354696930489144983575446495078404329829091193678240029445525658582548485531996972340914370823232033916046942293331266006647674886928834212203547468218609381456317192256524737280398698305720035095438106008915543
5
c = 18491889164810617543569456750416875989184817880137548014973592642069416208831086398288449741333647958301433206462225905089767171227296166302076329585813204145393998300807912284373441125769784091235480355305999860836226228064817001671079683866140595167104080925862489688205706558563994071054217252661751197090938128540101902284587959897970686920835999487758527543265902558413502613239565915919268373782402562042295965144636399280059309987259722405692758942811072888497222424752062745376152606372092707679048892146955016482797824514120865462676167840311292744307891590740707933408465096337716317714272609074408402855672
6

7
def is_perfect_square(x):
8
    r = int(math.isqrt(x))
9
    return r*r == x, r
10

11
def continued_fraction(a, b):
12
    q = []
13
    while b:
14
        q.append(a // b)
15
        a, b = b, a % b
16
    return q
17

18
def convergents_from_cf(cf):
19
    num1, num2 = 1, cf[0]
20
    den1, den2 = 0, 1
21
    yield (cf[0], 1)
22
    for k in cf[1:]:
23
        num = k*num2 + num1
24
        den = k*den2 + den1
25
        yield (num, den)
26
        num1, num2 = num2, num
27
        den1, den2 = den2, den
28

29
def wiener_attack(e, n):
30
    cf = continued_fraction(e, n)
31
    for (k, d) in convergents_from_cf(cf):
32
        if k == 0:
33
            continue
34
        phi_num = e*d - 1
35
        if phi_num % k != 0:
36
            continue
37
        phi = phi_num // k
38
        s = n - phi + 1
39
        D = s*s - 4*n
40
        is_sq, r = is_perfect_square(D)
41
        if not is_sq:
42
            continue
43
        p = (s + r) // 2
44
        q = (s - r) // 2
45
        if p*q == n and p > 1 and q > 1:
46
            return d, p, q
47
    return None
48

49
res = wiener_attack(e, n)
50
if not res:
51
    print("Wiener attack failed.")
52
else:
53
    d, p, q = res
54
    print("Recovered d:", d)
55
    m = pow(c, d, n)
56
    flag = m.to_bytes((m.bit_length() + 7)//8, 'big')
57
    print("Flag:", flag)

1
Recovered d: 7
2
Flag: b'QnQSec{I_l0v3_Wi3n3r5_@nD_i_l0v3_Nut5!!!!}'

1
QnQSec{I_l0v3_Wi3n3r5_@nD_i_l0v3_Nut5!!!!}