Skip to content

Latest commit

 

History

History
186 lines (139 loc) · 13.1 KB

triple-secure.md

File metadata and controls

186 lines (139 loc) · 13.1 KB

triple-secure

Challenge information

Points: 150
Tags: picoMini by redpwn, Cryptography
Author: BOOLEAN

Description:
To get the flag, you must break RSA not once, but three times!

Hints:
(None)

Challenge link: https://play.picoctf.org/practice/challenge/209

Solution

Analyze the given files

We start by looking at the given files. First the python script

#!/usr/bin/env python3

from Crypto.Util.number import getPrime, bytes_to_long

with open('flag.txt', 'rb') as f:
    flag = f.read()

p = getPrime(1024)
q = getPrime(1024)
r = getPrime(1024)

n1 = p * q
n2 = p * r
n3 = q * r

moduli = [n1, n2, n3]

e = 65537
c = bytes_to_long(flag)

for n in moduli:
    c = pow(c, e, n)

with open('public-key.txt', 'w') as f:
    f.write(f'n1: {n1}\n')
    f.write(f'n2: {n2}\n')
    f.write(f'n3: {n3}\n')
    f.write(f'e: {e}\n')
    f.write(f'c: {c}\n')

The script randomly selects 3 primes (p, q, r) and then calculates 3 different, but interdependent, modulus (n1, n2, n3).
This means we could derive p, q and r by calculating the GCD from pairs of n1, n2 and n3.

Alternatively, we could search for known factorizations of the modulus in databases such as factordb.

The public-key.txt file looks like this

n1: 15192492059814175574941055248891268822162533520576381643453916855435310880285336743521199057138647926712835561752909538944229702432795423884081992987060760867003375755338557996965825324749221386675061886921763747311599846248565297387814717840084998677273427776535730840343260681623323972936404815862969684384733188827100528542007213405382537935243645704237369770300643318878176739181891072725262069278646319502747718264711249767568106460533935904219027313131270918072460753061248221785076571054217566164086518459844527639082962818865640864990672033657423448004651989761933295878220596871163544315057550871764431562609
n2: 15896482259608901559307142941940447232781986632502572991096358742354276347180855512281737388865155342941898447990281534875563129451327818848218781669275420292448483501384399236235069545630630803245125324540747189305877026874280373084005881976783826855683894679886076284892158862128016644725623200756074647449586448311069649515124968073653962156220351541159266665209363921681260367806445996085898841723209546021525012849575330252109081102034217511126192041193752164593519033112893785698509908066978411804133407757110693612926897693360335062446358344787945536573595254027237186626524339635916646549827668224103778645691
n3: 16866741024290909515057727275216398505732182398866918550484373905882517578053919415558082579015872872951000794941027637288054371559194213756955947899010737036612882434425333227722062177363502202508368233645194979635011153509966453453939567651558628538264913958577698775210185802686516291658717434986786180150155217870273053289491069438118831268852205061142773994943387097417127660301519478434586738321776681183207796708047183864564628638795241493797850819727510884955449295504241048877759144706319821139891894102191791380663609673212846473456961724455481378829090944739778647230176360232323776623751623188480059886131
e: 65537
c: 5527557130549486626868355638343164556636640645975070563878791684872084568660950949839392805902757480207470630636669246237037694811318758082850684387745430679902248681495009593699928689084754915870981630249821819243308794164014262751330197659053593094226287631278905866187610594268602850237495796773397013150811502709453828013939726304717253858072813654392558403246468440154864433527550991691477685788311857169847773031859714215539719699781912119479668386111728900692806809163838659848295346731226661208367992168348253106720454566346143578242135426677554444162371330348888185625323879290902076363791018691228620744490

Factorize n1 through n3

These modulus are in fact known at factordb:

However, let's calculate their GCDs with the help of the gmpy2 Python module instead since it's pretty straight forward

#!/usr/bin/python

from gmpy2 import gcd

n1 = 15192492059814175574941055248891268822162533520576381643453916855435310880285336743521199057138647926712835561752909538944229702432795423884081992987060760867003375755338557996965825324749221386675061886921763747311599846248565297387814717840084998677273427776535730840343260681623323972936404815862969684384733188827100528542007213405382537935243645704237369770300643318878176739181891072725262069278646319502747718264711249767568106460533935904219027313131270918072460753061248221785076571054217566164086518459844527639082962818865640864990672033657423448004651989761933295878220596871163544315057550871764431562609
n2 = 15896482259608901559307142941940447232781986632502572991096358742354276347180855512281737388865155342941898447990281534875563129451327818848218781669275420292448483501384399236235069545630630803245125324540747189305877026874280373084005881976783826855683894679886076284892158862128016644725623200756074647449586448311069649515124968073653962156220351541159266665209363921681260367806445996085898841723209546021525012849575330252109081102034217511126192041193752164593519033112893785698509908066978411804133407757110693612926897693360335062446358344787945536573595254027237186626524339635916646549827668224103778645691
n3 = 16866741024290909515057727275216398505732182398866918550484373905882517578053919415558082579015872872951000794941027637288054371559194213756955947899010737036612882434425333227722062177363502202508368233645194979635011153509966453453939567651558628538264913958577698775210185802686516291658717434986786180150155217870273053289491069438118831268852205061142773994943387097417127660301519478434586738321776681183207796708047183864564628638795241493797850819727510884955449295504241048877759144706319821139891894102191791380663609673212846473456961724455481378829090944739778647230176360232323776623751623188480059886131

p = gcd(n1, n2)
q = gcd(n1, n3)
r = gcd(n2, n3)

print(f"p = {p}\nq = {q}\nr = {r}")

Then we run this script called factorize.py

┌──(kali㉿kali)-[/mnt/…/picoCTF/picoMini_by_redpwn/Cryptography/triple-secure]
└─$ ~/python_venvs/gmpy2/bin/python ./factorize.py 
p = 119660120407416342093521198875970200503652030026184999838840951544471188235057764512149622436334754517070092115889922087976143409261665862157884453930404483415351610238154321433871054239568905273137919725917526056473901359312949883646592913381637999260828599289383860301717085920912559762712295164989106012643
q = 126963703597214242111055793388455179890379067770512076858587717197146928847759121114335398860091528260297687323794942479532566444647858389461128295471609299505781851499310733099158304584543771415239918097328230929655601250453281393102266829307661217314893414986784482323832179578849867366834284687012845412763
r = 132846951895793538897077555403967847542050766700952197146228251113081712319440889155149846202888542648969351063239105740434095718011829001684551658508591803707420131965877374781379009502046474415909376904718002094203010990824838428607725944298259738507797326637681632441750845743202171364832477389321609195337

Now we can proceed to decrypt the flag.

Decrypt and get the flag

We can now write a decrypt.py script to decrypt and print the flag

#!/usr/bin/python

from gmpy2 import invert

def decrypt(c, p, q, e):
     ph = (p-1) * (q-1)
     d = invert(e, ph)
     n = p * q
     return pow(c, d, n)

# Given in the challenge
e = 65537
c = 5527557130549486626868355638343164556636640645975070563878791684872084568660950949839392805902757480207470630636669246237037694811318758082850684387745430679902248681495009593699928689084754915870981630249821819243308794164014262751330197659053593094226287631278905866187610594268602850237495796773397013150811502709453828013939726304717253858072813654392558403246468440154864433527550991691477685788311857169847773031859714215539719699781912119479668386111728900692806809163838659848295346731226661208367992168348253106720454566346143578242135426677554444162371330348888185625323879290902076363791018691228620744490

# From the factorize.py run
p = 119660120407416342093521198875970200503652030026184999838840951544471188235057764512149622436334754517070092115889922087976143409261665862157884453930404483415351610238154321433871054239568905273137919725917526056473901359312949883646592913381637999260828599289383860301717085920912559762712295164989106012643
q = 126963703597214242111055793388455179890379067770512076858587717197146928847759121114335398860091528260297687323794942479532566444647858389461128295471609299505781851499310733099158304584543771415239918097328230929655601250453281393102266829307661217314893414986784482323832179578849867366834284687012845412763
r = 132846951895793538897077555403967847542050766700952197146228251113081712319440889155149846202888542648969351063239105740434095718011829001684551658508591803707420131965877374781379009502046474415909376904718002094203010990824838428607725944298259738507797326637681632441750845743202171364832477389321609195337

# Decrypt in reverse order
first = decrypt(c, q, r, e)
second = decrypt(first, p, r, e)
third = decrypt(second, p, q, e)

print(bytes.fromhex(format(third, 'x')).decode())

Finally, time to run the script and get the flag

┌──(kali㉿kali)-[/mnt/…/picoCTF/picoMini_by_redpwn/Cryptography/triple-secure]
└─$ ~/python_venvs/gmpy2/bin/python ./decrypt.py  
picoCTF{<REDACTED>}

For additional information, please see the references below.

Addendum

We really don't need to do the factorization and decryption in two separate steps. Here is a total.py script that does everything in one go

#!/usr/bin/python

from gmpy2 import gcd, invert

def decrypt(c, p, q, e):
     ph = (p-1) * (q-1)
     d = invert(e, ph)
     n = p * q
     return pow(c, d, n)

# Given in the challenge
n1 = 15192492059814175574941055248891268822162533520576381643453916855435310880285336743521199057138647926712835561752909538944229702432795423884081992987060760867003375755338557996965825324749221386675061886921763747311599846248565297387814717840084998677273427776535730840343260681623323972936404815862969684384733188827100528542007213405382537935243645704237369770300643318878176739181891072725262069278646319502747718264711249767568106460533935904219027313131270918072460753061248221785076571054217566164086518459844527639082962818865640864990672033657423448004651989761933295878220596871163544315057550871764431562609
n2 = 15896482259608901559307142941940447232781986632502572991096358742354276347180855512281737388865155342941898447990281534875563129451327818848218781669275420292448483501384399236235069545630630803245125324540747189305877026874280373084005881976783826855683894679886076284892158862128016644725623200756074647449586448311069649515124968073653962156220351541159266665209363921681260367806445996085898841723209546021525012849575330252109081102034217511126192041193752164593519033112893785698509908066978411804133407757110693612926897693360335062446358344787945536573595254027237186626524339635916646549827668224103778645691
n3 = 16866741024290909515057727275216398505732182398866918550484373905882517578053919415558082579015872872951000794941027637288054371559194213756955947899010737036612882434425333227722062177363502202508368233645194979635011153509966453453939567651558628538264913958577698775210185802686516291658717434986786180150155217870273053289491069438118831268852205061142773994943387097417127660301519478434586738321776681183207796708047183864564628638795241493797850819727510884955449295504241048877759144706319821139891894102191791380663609673212846473456961724455481378829090944739778647230176360232323776623751623188480059886131
e = 65537
c = 5527557130549486626868355638343164556636640645975070563878791684872084568660950949839392805902757480207470630636669246237037694811318758082850684387745430679902248681495009593699928689084754915870981630249821819243308794164014262751330197659053593094226287631278905866187610594268602850237495796773397013150811502709453828013939726304717253858072813654392558403246468440154864433527550991691477685788311857169847773031859714215539719699781912119479668386111728900692806809163838659848295346731226661208367992168348253106720454566346143578242135426677554444162371330348888185625323879290902076363791018691228620744490

# Calculate the primes
p = gcd(n1, n2)
q = gcd(n1, n3)
r = gcd(n2, n3)

# Decrypt in reverse order
first = decrypt(c, q, r, e)
second = decrypt(first, p, r, e)
third = decrypt(second, p, q, e)

print(bytes.fromhex(format(third, 'x')).decode())

References