title: RSA Primes

category: Crypto

difficulty: -

point: 484

author: -

description:

More primes, more security!

Auteur : Raccoon (BZHack Friends)

Solution

On connait N et 2 facteurs des 3 facteurs de celui-ci. On peut s’en servir pour calculer le 3ème :

N = p * q * r <=> r = N / (p * q)

Une fois qu’on connaît les 3 facteurs premiers de N, on peut calculer l’inverse de e dans N.

En Python :

from Crypto.Util.number import long_to_bytes

# Au lieu de réécrire les variables, on peut les "importer" depuis le fichier
# output = open('output.txt').read()
# exec(output)

n = 3131198763047134866159982163287352060393193886319536672485854564276792042784691919260159092293215560472492392809826557635935034987201243162828659255600887421694715057360772776595251660808296747011665088441906057008497534447316855524574547061223821075029078651427490509540265528454081862607163096403678864142346139789322886630998558510840679574467255701421104148933391489753240586611964412522778337663351351759989025193082078730667308571138476391273721887658145701111897135484856267019491046487452500145999292812641448227294578476852854041472133527166857230058354081160380698354611560861081772069570367953795631066631375081326336237222236154290262332236700047689280166357265137106665363980594255511167881329711823463904654406479596328236955474955575204700841039036929088351178334025540759542220383364299556161015374538600271660550511060890187251107956682058246004243144533505379166250429246260971107972659002864328882404279397
p = 164604182051202401075939359173250177861944040758102085897301653817265999581063831188359362570697839356127666960216890439096327950998754846406958697384471452578568570691048862363842286287284126594025170954748830113959728854437048573426127867248847768466808396895893741313136167571211127240478728319607889278213
q = 146874866873296409794408237346466893390119037608475668671003697611901716627079037110400447627933981171726006405932450142616150950129684209444381260682725715741185677480582782126380551918423177168006118096188314308611861412086976757504732438718446744835548072606911776149642829644570830891272198507022047678629
e = 65537
c = 1785824787695951154831145465217381355417258248841341613265343769815730963705688576404837459720918620142970650984234543533413565797244289567435129555004071427307693250359430242638378550021149193197723037459018101661845488375015350973432528344834383747207459570380239393258919955724169798869477627713752907315192791455765321580231613191333350588868757241056470404831983792542192026705304903630282600667339631252205685949393185065188876660489261788660100315763049082927183608563158413348066767714403454618783838750387950805378246322651942785324429025786758531032375398929950078138020904093073827734730065163750339508094216403410915447708387884984995228466284364548078272532580024174929946702490878451005440389615548009472862614591796708319742719385335580201299996412052810438515494569174830421002976403642534544557480266694642371766189204855440757585139063616470000861560668946862896936366355245431004671025924037022364605388035

# Le double slash (//) permet de forcer l'utilisation de Integer et donc de ne pas arrondir le résultat
r = n // (p * q)

# Calcul de l'inverse de e dans N
d = pow(e, -1, (p-1) * (q-1) * (r-1))

# Déchiffrement du cipher
m = long_to_bytes(pow(c, d, n)).decode()
print(m)

FLAG{7c5c82d886c556bb181618ee}

FLAG : FLAG{7c5c82d886c556bb181618ee}