Énoncé

I think i might leaked something but i dont know what

Author : Bebo07

On a:

Deux fichier -> chall2.py et chall2.txt

chall2.py contient le code source qui a servit à chiffrer le flag chall2.txt contient l'output de chall2.py + hint=411

On sait que:

eq1 est calculée comme le prochain nombre premier après out1, où out1 est une puissance de p + 5 * q La valeur chiffrée c est calculée avec le message m à la puissance eq1 modulo n

n est bien trop grand pour être simplement factorisé, mais on peut toujours tester plusieurs nombre, les mutlitpliés et les comparer avec n. Au lieu de partir de 1 jusqua atteindre notre valeur, on peut essayer avec des nombre tel que :

q1 = pow(out1, power2, n) q2 = pow(out2, power1, n)

Une manière rapide de determiner si q1 et q2 sont de bon candidat pour être les facteurs premier de n est de créer une relation s entre les deux et de vérifier si ce nombre est divisible par n tel que: s = pow(2, power1 * power2, n) * q1 - pow(1, power1 * power2, n) * q2 q = gcd(s, n) p = n // q

Ensuite on vérife que p*q=n et que q!=1

Si c'est bon, il ne nous reste plus qu'a retrouver la celf privé à partir de p et q en cherchant phi puis en calculant l'inverse modulaired'eq1 et de phi

PS: le hint=411 qui est dans chall2.txt correspond au nombre de décrémentation nécéssaire pour trouver out1 a partir d'eq1

Decrypt.py

from math import gcd
from Crypto.Util.number import long_to_bytes, inverse

#value in chall2.txt
n = 14478207897963700838626231927254146456438092099321018357600633229947985294943471593095346392445363289100367665921624202726871181236619222731528254291046753377214521099844204178495251951493800962582981218384073953742392905995080971992691440003270383672514914405392107063745075388073134658615835329573872949946915357348899005066190003231102036536377065461296855755685790186655198033248021908662540544378202344400991059576331593290430353385561730605371820149402732270319368867098328023646016284500105286746932167888156663308664771634423721001257809156324013490651392177956201509967182496047787358208600006325742127976151
power1 = 281633240040397659252345654576211057861
power2 = 176308336928924352184372543940536917109
c = 11590329449898382355259097288126297723330518724423158499663195432429148659629360772046004567610391586374248766268949395442626129829280485822846914892742999919200424494797999357420039284200041554727864577173539470903740570358887403929574729181050580051531054419822604967970652657582680503568450858145445133903843997167785099694035636639751563864456765279184903793606195210085887908261552418052046078949269345060242959548584449958223195825915868527413527818920779142424249900048576415289642381588131825356703220549540141172856377628272697983038659289548768939062762166728868090528927622873912001462022092096509127650036
out2 = 224716457567805571457452109314840584938194777933567695025383598737742953385932774494061722186466488058963292298731548262946252467708201178039920036687466838646578780171659412046424661511424885847858605733166167243266967519888832320006319574592040964724166606818031851868781293898640006645588451478651078888573257764059329308290191330600751437003945959195015039080555651110109402824088914942521092411739845889504681057496784722485112900862556479793984461508688747584333779913379205326096741063817431486115062002833764884691478125957020515087151797715139500054071639511693796733701302441791646733348130465995741750305
eq1=2215046782468309450936082777612424211412337114444319825829990136530150023421973276679233466961721799435832008176351257758211795258104410574651506816371525399470106295329892650116954910145110061394115128594706653901546850341101164907898346828022518433436756708015867100484886064022613201281974922516001003812543875124931017296069171534425347946706516721158931976668856772032986107756096884279339277577522744896393586820406756687660577611656150151320563864609280700993052969723348256651525099282363827609407754245152456057637748180188320357373038585979521690892103252278817084504770389439547939576161027195745675950581
decrementC = 0

#get p and q
while True:

    #au lieu de factoriser n, on cherche deux nbr q1 et q2 tel que q1*q2=n

    #A cause de `eq1 = next_prime(out1)`, on doit retrouver out1
    out1 = eq1-decrementC

    # Calcul de q1 et q2 à partir de out1 et out2
    #l'idée est d'optimiser des résultats plus probables
    q1 = pow(out1, power2, n)
    q2 = pow(out2, power1, n)

    # Ensuite on crée une relation entre q1 et q2 a partir de:
    # pow((2*p-3*q),power2,n) pow((p+5*q),power1,n)
    s = pow(2, power1 * power2, n) * q1 - pow(1, power1 * power2, n) * q2

    #si s est divisible par n, p et q sont candidats pour être facteur
    q = gcd(s, n)
    p = n // q

    # check the value
    if p * q == n and q != 1:
        print(f'p: {p}')
        print(f'q: {q}')
        break
    decrementC += 1

# Euler function
phi = ((p-1) * (q-1)) %n

#get the private ey
d = inverse(eq1, phi)

#decrypt c
flag = pow(c, d, n)

# get the flag
flag = long_to_bytes(flag)

print(flag)