RSA School 1st Grade

142 solves - 50 points

Description

First day of school!

Given Files

First_Grade.py
output.txt

Solution

En regardant le contenu de First_Grade.py :

from Crypto.Util.number import *
p=getPrime(512)
q=getPrime(512)
n=p*q
e=65537
msg=bytes_to_long(b'UDCTF{REDACTED}')
ct=pow(msg,e,n)
print(p)
print(n)
print(e)
print(ct)

et output.txt :

7009789528005665925389589645247771843738610365138497450285434114825324963561464592190523618045678504210355855286077875965585945664408796837853566415684077
73061872549912499570368059392056653520123131891860048946474996807859190776947568485365189613739847632132597352816568237525325622321891749472819811314630053648031678826291232292672975634200777457699671848298242827252269004463672931479153540235625891818449660268924228002522141737330313259535617652381070426543
65537
8099012654842320180974620472267007973324910863630262955526926760464542904631823196320598910081443799605804614201671967967929893760527002416689993003801924422327762868245291561376910828637706061326005113536536357969201659290874169593264337355365186414719656091960977568710047843815328537885731546232759484717

On peut voir qu'il s'agit d'un chiffrement RSA simple avec un exposant de 65537.

On peut faire un script python permettant de retrouver msg:

from Crypto.Util.number import *

p = 7009789528005665925389589645247771843738610365138497450285434114825324963561464592190523618045678504210355855286077875965585945664408796837853566415684077
n = 
73061872549912499570368059392056653520123131891860048946474996807859190776947568485365189613739847632132597352816568237525325622321891749472819811314630053648031678826291232292672975634200777457699671848298242827252269004463672931479153540235625891818449660268924228002522141737330313259535617652381070426543
e = 65537
ct =
8099012654842320180974620472267007973324910863630262955526926760464542904631823196320598910081443799605804614201671967967929893760527002416689993003801924422327762868245291561376910828637706061326005113536536357969201659290874169593264337355365186414719656091960977568710047843815328537885731546232759484717

q = n // p
phi = (p-1)*(q-1)
d = inverse(e, phi)
m = pow(ct, d, n)
print(long_to_bytes(m))

UDCTF{y3a_b0i_b4by_RSA!}

RSA School 2nd Grade

133 solves - 50 points

Description

Ok a little tougher

Given Files

Second_Grade.py
output.txt

Solution

En regardant le contenu de Second_Grade.py :

from Crypto.Util.number import *
n=166045890368446099470756111654736772731460671003059151938763854196360081247044441029824134260263654537
e=65537
msg=bytes_to_long(b'UDCTF{REDACTED}')
ct=pow(msg,e,n)
print(n)
print(e)
print(ct)

et output.txt :

166045890368446099470756111654736772731460671003059151938763854196360081247044441029824134260263654537
65537
1419273799864099208451947034999412629880613167064332422893537768023750745252956889042151134458835896538

Le solve est quasiment identique au précédent. Il suffit de changer les variables et de lancer le script python.

On décompose n en produit de facteurs premiers :

p = 51700365364366863879483895851106199085813538441759
q = 3211696652397139991266469757475273013994441374637143

Puis avec la même méthode on trouve :

UDCTF{pr1m3_f4ct0r_the1f!}

RSA School 4th Grade

67 solves - 304 points

Description

Getting tired of school yet?

Given Files

Fourth_Grade.py
output.txt

Solution

En regardant le contenu de Fourth_Grade.py :

from Crypto.Util.number import *
e=65537
your_e = getPrime(20)
msg=bytes_to_long(b'UDCTF{REDACTED}')
p=getPrime(512)
q=getPrime(512)
n=p*q
assert(msg < n)
ct=pow(msg, e, n)
your_d = inverse(your_e, (p-1)*(q-1))
print(your_e)
print(your_d)
print(n)
print(e)
print(ct)

et output.txt :

548861
95173232432571941329231712692828118443780574466702093807146321250099677631827067825710345421542241500117509827717221625523077656554170307232963298108032249257829668442277402436905496971410095631707035128294281318370127935482352287840967522858886054571972660826718745245567014905338023490270530223206547055189
128923276994737790032784225847154420815473322545569053376748335367791339027988282369445542202224938698537424444443434684524386629219697192340629226569242894844874718895350330788650992608621499779776079293063355076268941953990983854217613662005027668855183281795022629934463967333582234624036115283306256019477
65537
101925091511033045433108849975441961999589763870098425244810307722908781911184299892072334641669931066841662878745617845011689451171244453969963211155840837507751273716371760271643490363012983256424608885239953158409708266675819028960222627654995967984657602529298637614235721996131897162063485544360691578861

Notre but ici va être d'utiliser l'algoithme de Pohlig-Hellman nous permettant de calculer à plusieurs reprise le PGCD du nombre et d'un nombre aléatoire. Si le PGCD > 1, alors on a trouvé un facteur premier de n.

On va donc utiliser le script suivant :

from math import gcd
from Crypto.Util.number import long_to_bytes
from random import randint
n = 128923276994737790032784225847154420815473322545569053376748335367791339027988282369445542202224938698537424444443434684524386629219697192340629226569242894844874718895350330788650992608621499779776079293063355076268941953990983854217613662005027668855183281795022629934463967333582234624036115283306256019477
d = 95173232432571941329231712692828118443780574466702093807146321250099677631827067825710345421542241500117509827717221625523077656554170307232963298108032249257829668442277402436905496971410095631707035128294281318370127935482352287840967522858886054571972660826718745245567014905338023490270530223206547055189
c = 101925091511033045433108849975441961999589763870098425244810307722908781911184299892072334641669931066841662878745617845011689451171244453969963211155840837507751273716371760271643490363012983256424608885239953158409708266675819028960222627654995967984657602529298637614235721996131897162063485544360691578861
e = 548861
def find_pq(n,e,d):
    k = e * d - 1
    r = k
    t = 0
    while r % 2 == 0:
        t += 1
        r = r // 2
    p = 0
    g = randint(1, n-1)
    while p == 0:
        for i in range(t+1):
            x = pow(g,k//2**i,n)
            p = gcd(x-1,n)
            if (x > 1 and p > 1):
                break
        g = randint(1, n-1)
    return p, n//p
p, q = find_pq(n, e, d)
phi = (p-1) * (q-1)
print(phi)
d = pow(65537, -1, phi)
m = pow(c, d, n)
print(long_to_bytes(m))

UDCTF{m0d_mult1pl1c4tiv3_inv3r5e_nd_57uff}

RSA School 7th Grade

71 solves - 280 points

Description

It's grind time

Given Files

Seventh_Grade.py
output.txt

Solution

En regardant le contenu de Seventh_Grade.py :

from Crypto.Util.number import *
import sympy.ntheory as nt
import random
p=getPrime(1024)
q=nt.nextprime(p)
for _ in range(random.randint(500,10000)):
    q=nt.nextprime(q)
N=p*q
msg="UDCTF{REDACTED}"
pt=bytes_to_long(msg)
e=655
ct=pow(pt,e,N)
print(N)
print(e)
print(ct)

et output.txt :

17740803753336460891508014077951088945415214329359164945595622460861617151883658129377771074141448545977293824812472806768754107334272113784618671425945265453677763300584120796664192793654787317526905676618168560287204392207536711238413377822113265783504873957094131330620182217422910507867161033695120195691266283498385072573721376398480018719760538723050237163598524153522595496137288270407836138586188296538117138982579560625325815068701431157466298638302885600982291990551448117534677697122276691651611734934147801954625280213769902451417946572231015611006746186167211313556716518863585799128114202130873384852581
65537
7617664236008252568996899627946125782926068188323112773389474654757630578865481085502759186904920518615173703165984894164411436709177950136929724052191922739861682189280802963747906815275683543148623167088950096943169566195634558711652670745197446307315888349532981492405588457559228674864147994684328968321710022127803384848143475788457274558988285904875669797926919759123645348144531804252200718312650929926931919262408975771593313266992606751663814830129337536342634243623652919127335934704778878412649409415730419077839365246227059700689395639431013008985996793686430486195007712091309878718060405038405039494286

On peut voir que le nombre de chiffrement est très grand. On va donc utiliser la méthode de Fermat pour trouver les facteurs premiers de N.

On a de la chance, RsaCtfTool permet de faire cela :

python3 RsaCtfTool.py -n 17740803753336460891508014077951088945415214329359164945595622460861617151883658129377771074141448545977293824812472806768754107334272113784618671425945265453677763300584120796664192793654787317526905676618168560287204392207536711238413377822113265783504873957094131330620182217422910507867161033695120195691266283498385072573721376398480018719760538723050237163598524153522595496137288270407836138586188296538117138982579560625325815068701431157466298638302885600982291990551448117534677697122276691651611734934147801954625280213769902451417946572231015611006746186167211313556716518863585799128114202130873384852581 -e 65537 --uncipher 7617664236008252568996899627946125782926068188323112773389474654757630578865481085502759186904920518615173703165984894164411436709177950136929724052191922739861682189280802963747906815275683543148623167088950096943169566195634558711652670745197446307315888349532981492405588457559228674864147994684328968321710022127803384848143475788457274558988285904875669797926919759123645348144531804252200718312650929926931919262408975771593313266992606751663814830129337536342634243623652919127335934704778878412649409415730419077839365246227059700689395639431013008985996793686430486195007712091309878718060405038405039494286

UDCTF{F3rma7_c4n_sur3_fac70r!}

Greatest Hits 2 of 4

64 solves - 100 points

Description

Given Files

rsa.py
rsaout.txt

Solution

En regardant le contenu de rsa.py :

from Crypto.Util.number import *
p=getPrime(1024)
q=getPrime(1024)
n=p*q
e1=32
e2=94
msg=bytes_to_long("REDACTED")
assert(pow(msg,2) < n)
c1 = pow(msg, e1, n)
c2 = pow(msg, e2, n)
print(n)
print(e1)
print(e2)
print(c1)
print(c2)

et rsaout.txt :

15144989296069059933372368453196092175005161975349151110345314566785160131088640293080496647831336241835434081246752372095089223274410617149601529995353586979709767320781773241635911841825135157128620635284850556358212336804356913383250552153118005157608892746468253056994929497147176358510660250974046147584489593314250043332900225627695013699452589204281775937461626931870469970564649337891804670484615877731064389199146553155645996166903057997780769847954473558252319887360004797752922471164238094762917170732419058459198871816368754874928563582062094607146743861963241102686280889624636580265012154494857871226911
32
94
517413713703886999866857886363089094585257050613499021392236739949207714015445698823055234855661713319078211477553629447153099784179447532323740595057178898139959674381355432131055787089201673781698752057672521217038516832753572594045829378268006522196608125682968252235804171902500675561571516482830716057356093346644739755000641419389456649384154636696468100735075639775740773984117668523785494430624107703773927953688140653884319491595701619752757483259322185639861570200460175036940484201361523531829151771132059047908439112074722779866239565825707838090161372153338024174748440497243107864663782108641727771659
7627448403143228380990811828784190441589966806784538493012623116575366382931836531487460665746937844089811800210162413422176546183916362252942569359187329261606901744873414894672206518833504277712248120517227097337821671357183002903689123275299969496743046843235865472598002895668376113637844709030956945481612135136663699655327584977008477587437014970931004029432308882904616641276931607404737262279319635052041442201857436898171408177118684300765925831306704477989772422231625570934627171304088385754161129883791893955034648200851254688716049371226939666530556140959866437156338956068301001303202802889970914365861

Le challenge ressemble fortement à BrokenRSA sur CryptoHack, seulement ici on a 2 exposants différents.

Les deux exposants ne sont pas premiers. On peut oublier la plupart des attaques car e1 et e2 sont coprimes.

Si e1 et e2 sont premieux entre eux, alors il existe u et v tels que (a ^ u) mod n = (a ^ v) mod n.

On va donc chercher un c1_u et c2_v, avec libnum :

from Crypto.Util.number import long_to_bytes
from math import isqrt
import libnum
n = 15144989296069059933372368453196092175005161975349151110345314566785160131088640293080496647831336241835434081246752372095089223274410617149601529995353586979709767320781773241635911841825135157128620635284850556358212336804356913383250552153118005157608892746468253056994929497147176358510660250974046147584489593314250043332900225627695013699452589204281775937461626931870469970564649337891804670484615877731064389199146553155645996166903057997780769847954473558252319887360004797752922471164238094762917170732419058459198871816368754874928563582062094607146743861963241102686280889624636580265012154494857871226911
e1 = 32
e2 = 94
c1 = 517413713703886999866857886363089094585257050613499021392236739949207714015445698823055234855661713319078211477553629447153099784179447532323740595057178898139959674381355432131055787089201673781698752057672521217038516832753572594045829378268006522196608125682968252235804171902500675561571516482830716057356093346644739755000641419389456649384154636696468100735075639775740773984117668523785494430624107703773927953688140653884319491595701619752757483259322185639861570200460175036940484201361523531829151771132059047908439112074722779866239565825707838090161372153338024174748440497243107864663782108641727771659
c2 = 7627448403143228380990811828784190441589966806784538493012623116575366382931836531487460665746937844089811800210162413422176546183916362252942569359187329261606901744873414894672206518833504277712248120517227097337821671357183002903689123275299969496743046843235865472598002895668376113637844709030956945481612135136663699655327584977008477587437014970931004029432308882904616641276931607404737262279319635052041442201857436898171408177118684300765925831306704477989772422231625570934627171304088385754161129883791893955034648200851254688716049371226939666530556140959866437156338956068301001303202802889970914365861
u, v, z_gcd= libnum.xgcd(e1, e2)
c1_u = pow(c1, u, n) 
c2_v = pow(c2, v, n)

print(long_to_bytes(isqrt((c1_u * c2_v) % n)))

UDCTF{l4rg3_int3ger_sqrt_w1th0ut_fl04ts}