wCTF3 Crypto 100 (RSA encryption)

weirdCTF3 crypto 100 (RSA encryption)
by Brahimi Zakaria


After downloading the compressed file (here) and having it extracted, we find two files named : 'public.key' (which contain the public key of the rsa keypair) and 'flag.crypted' (which contain the flag encrypted).

The task is clear, we have to recover the private key to get the flag.

Let's begin with exploring informations within the public key with openssl like this :

Input :
openssl rsa -noout -text -inform PEM -in public.key -pubin

Output :
openssl rsa -noout -text -inform PEM -in public.key -pubin
Modulus (565 bit):
    12:fb:b2:17:cc:d5:a2:a9:8c:73:67:77:7a:1d:e9:
    37:c7:7d:73:87:65:1e:20:84:b3:8f:4e:f9:3e:c4:
    96:8e:1b:be:9b:b2:30:23:45:05:33:7e:79:fc:fd:
    b7:78:37:7d:7a:c0:07:37:47:f2:27:5b:f9:c4:de:
    03:56:de:df:be:83:79:be:14:c6:75
Exponent: 65537 (0x10001)

It's an RSA public key with a non common size of 565 bits.

The public key only contains the modulus N and the exponent e. N could be factorized into 2 prime numbers p and q, so N = p x q.
Based on those 2 numbers we will be able to generate the private key.

As the modulus above is in a hexadecimal form, we have to convert it to a decimal form like this :

Input :
python -c "print int('12fbb217ccd5a2a98c7367777a1de937c77d7387651e2084b38f4ef93ec4968e1bbe9bb230234505337e79fcfdb778377d7ac0073747f2275bf9c4de0356dedfbe8379be14c675', 16)"

Output :
71641831546926719303369645296528546480083425905458247405279061196214424558100678947996271179659761521775290973790597533683668081173314940392098256721488468660504161994357


The modulus is made of 565 bits. Thus it couldn't be factorised easily.
Another possibility is fermat's factorisation.

By running a script (factorisation.py) which implement the Fermat's factorisation against this large prime number, we could spits out the two primes immediately.

Input :
python factorisation.py

Output :
p : = 8464149782874043593254414191179506861158311266932799636000173971661904149225893113387
q : = 8464149782874043593254414191179506861158311266932799636000173971661904149225893113311


Now we could regenerate the private key using another script called rsatool.py like this :

Input :

python rsatool.py -p 8464149782874043593254414191179506861158311266932799636000173971661904149225893113387 -q 8464149782874043593254414191179506861158311266932799636000173971661904149225893113311 -o private.pem

Output :

n = 12fbb217ccd5a2a98c7367777a1de937c77d7387651e2084b38f4ef93ec4968e1bbe9bb230234505337e79fcfdb778377d7ac0073747f2275bf9c4de0356dedfbe8379be14c675

e = 65537 (0x10001)

d = fdc0a8949cf7e4b8a94ebef6cadcaa7985a1e081319dd6f2098ed10dd38ded3b12848e2890cc75db5c9ed94e0b3f570bfdce9ef781e3db2e7d99069e78fe6425ec168752d64ed

p = 45b62603351c22f7148bcaa5cf013ad3c05dfcc054a146945d907c24d0f7053a461ae2b

q = 45b62603351c22f7148bcaa5cf013ad3c05dfcc054a146945d907c24d0f7053a461addf

Saving PEM as private.pem


We can now decrypt the base64 encoded cipher within the file 'flag.crypted' and decipher the content with the private key we had generated :

Input :

cat flag.crypted | base64 -d > flag
openssl rsautl -decrypt -in flag -inkey private.pem

Output :
wctf{RSA_c1n_b3_w3AK_b3_c4reFuL}


That's it.