↓Skip to main content

HTB - RsaisEasy

·437 words·3 mins
Hack the Box CTF Python Cryptography
Table of Contents

Challenge Description #

I think this is safe… Right?

Provided files #

Python Script #

from Crypto.Util.number import bytes_to_long, getPrime
from secrets import flag1, flag2
from os import urandom

flag1 = bytes_to_long(flag1)
flag2 = bytes_to_long(flag2)

p, q, z = [getPrime(512) for i in range(3)]

e = 0x10001

n1 = p * q
n2 = q * z

c1 = pow(flag1, e, n1)
c2 = pow(flag2, e, n2)

E = bytes_to_long(urandom(69))

print(f'n1: {n1}')
print(f'c1: {c1}')
print(f'c2: {c2}')
print(f'(n1 * E) + n2: {n1 * E + n2}')

Output file #

n1: 101302608234750530215072272904674037076286246679691423280860345380727387460347553585319149306846617895151397345134725469568034944362725840889803514170441153452816738520513986621545456486260186057658467757935510362350710672577390455772286945685838373154626020209228183673388592030449624410459900543470481715269
c1: 92506893588979548794790672542461288412902813248116064711808481112865246689691740816363092933206841082369015763989265012104504500670878633324061404374817814507356553697459987468562146726510492528932139036063681327547916073034377647100888763559498314765496171327071015998871821569774481702484239056959316014064
c2: 46096854429474193473315622000700040188659289972305530955007054362815555622172000229584906225161285873027049199121215251038480738839915061587734141659589689176363962259066462128434796823277974789556411556028716349578708536050061871052948425521408788256153194537438422533790942307426802114531079426322801866673
(n1 * E) + n2: 601613204734044874510382122719388369424704454445440856955212747733856646787417730534645761871794607755794569926160226856377491672497901427125762773794612714954548970049734347216746397532291215057264241745928752782099454036635249993278807842576939476615587990343335792606509594080976599605315657632227121700808996847129758656266941422227113386647519604149159248887809688029519252391934671647670787874483702292498358573950359909165677642135389614863992438265717898239252246163

Solution #

So my first incstinct was to plug n1 into factordb to see if I can cheese p and q and I’ve cheesed it successfully.

p = 8413387656561188778435613942028835678781206299389177514340760123063579360223360470566083306606450007991287094526418200038784207648097820069671213638771543
q = 12040644312371555810530782070969893153760288255333349208608058511112776958879208815174991008199408527954332776642365069284747758115478414463195873149420483

It’s still solvable without factordb, but knowing them straightaway makes things a bit easier. All I need to do now is find z.

Let’s say the last expression of the output is l. $$ l = \text{n1}*E + \text{n2} $$

$$ l = p*q*E + q*z $$

$$ l = q(p*E + z) $$

So, I can divide l by q and find the modulo p of the result to get z. In case z is larger than p, I just need to add it at most p to get z because, in this case, the modulo operation will result in a number smaller than z.

A Python script to easily do this would be something like this:

from Crypto.Util.number import isPrime
import gmpy2 as gm
n1 = 101302608234750530215072272904674037076286246679691423280860345380727387460347553585319149306846617895151397345134725469568034944362725840889803514170441153452816738520513986621545456486260186057658467757935510362350710672577390455772286945685838373154626020209228183673388592030449624410459900543470481715269
p = 8413387656561188778435613942028835678781206299389177514340760123063579360223360470566083306606450007991287094526418200038784207648097820069671213638771543
q = 12040644312371555810530782070969893153760288255333349208608058511112776958879208815174991008199408527954332776642365069284747758115478414463195873149420483
l = 601613204734044874510382122719388369424704454445440856955212747733856646787417730534645761871794607755794569926160226856377491672497901427125762773794612714954548970049734347216746397532291215057264241745928752782099454036635249993278807842576939476615587990343335792606509594080976599605315657632227121700808996847129758656266941422227113386647519604149159248887809688029519252391934671647670787874483702292498358573950359909165677642135389614863992438265717898239252246163
if l%p == 0:
    p,q = q,p
pos_z = (gm.divexact(l,q)) % p
while True:
    if isPrime(pos_z):
        break
    pos_z += p
print(f'z: {pos_z}')
print(f'q: {q}')
print(f'n2: {pos_z*q}')

I first have to check which prime is actually p and q. If l is divisible by p, then p’s value should actually be q’s. Then, I find the possible z by dividing z by q and then finding the modulo p. If the result is prime, then I can be fairly sure it’s z. Otherwise, I probably need to add p to the result.

z: 11902090706985450385711168746097079051837131924073767206823087288985169946406322955178859673901568871635087104842289268116429662526641184231035970230536659
q: 8413387656561188778435613942028835678781206299389177514340760123063579360223360470566083306606450007991287094526418200038784207648097820069671213638771543
n2: 100136903041423020991425823526737746365573197640035952973693624809721624428963253203282593974533722584391447008912397042291986993273828302711324440847902763039627790146764630023926517236880457533976468679976683705170312329736955922713306570804595070537102421450884645497775455984735279182873866159334387494837

If I weren’t able to cheese p and q, it’s still easy to find them. Given n1 and n1*E + n2, you can find the greatest common divisor between the two, which will be q. Then you just divide n1 by q to find p.

With this info, you can make a script to decrypt both parts of the flag. However, dcode.fr will do just fine with the data obtained.

Partial flag #

HTB{1_m1ght_h4v3_m3ss3d_uP_jU$t...