Breaking RSA

Room progress ( 0% )

To access material, start machines and answer questions login.

Task 1Capture the flag

A brief overview of RSA

The security of RSA relies on the practical difficulty of factoring the product of two large prime numbers, the "factoring problem". RSA key pair is generated using 3 large positive integers -

e A constant, usually 65537

Known as the modulus of public-private key pair. It is a product of 2 large random prime numbers, p and q.

n = p x q

A large positive integer that makes up the private key. It is calculated as,

d = modinv(e, lcm(p - 1, q - 1))

Where modinv is the modulus inverse function and lcm is the least common multiple function.

(e, n) are public variables and make up the public key. d is the private key and is calculated using p and q. If we could somehow factorize n into p and q, we could then be able to calculate d and break RSA. However, factorizing a large number is very difficult and would take some unrealistic amount of time to do so, provided the two prime numbers are randomly chosen.

Introduction

In a recent analysis, it is found that an organization named JackFruit is using a deprecated cryptography library to generate their RSA keys. This library is known to implement RSA poorly. The two randomly selected prime numbers (p and q) are very close to one another, making it possible for an attacker to generate the private key from the public key using Fermat's Factorization method.

Below is an implementation of Fermat's factorization algorithm in Python.

#!/usr/bin/python3
# gmpy2 is a C-coded Python extension module that supports
# multiple-precision arithmetic.
# pip install gmpy2
from gmpy2 import isqrt
from math import lcm

def factorize(n):
    # since even nos. are always divisible by 2, one of the factors will
    # always be 2
    if (n & 1) == 0:
        return (n/2, 2)

    # isqrt returns the integer square root of n
    a = isqrt(n)

    # if n is a perfect square the factors will be ( sqrt(n), sqrt(n) )
    if a * a == n:
        return a, a

    while True:
        a = a + 1
        bsq = a * a - n
        b = isqrt(bsq)
        if b * b == bsq:
            break

    return a + b, a - b

print(factorize(105327569))

I suggest using the pycryptodome Python library to answer the RSA-related questions below.

Answer the questions below

How many services are running on the box?

What is the name of the hidden directory on the web server? (without leading '/')

What is the length of the discovered RSA key? (in bits)

What are the last 10 digits of n? (where 'n' is the modulus for the public-private key pair)

Factorize n into prime numbers p and q

What is the numerical difference between p and q?

Generate the private key using p and q (take e = 65537)

What is the flag?

Created by

tryhackme

hackerinthehouse

Room Type

Free Room. Anyone can deploy virtual machines in the room (without being subscribed)!

Users in Room

5,430

Created

553 days ago

Ready to learn Cyber Security? Create your free account today!

TryHackMe provides free online cyber security training to secure jobs & upskill through a fun, interactive learning environment.

Already have an account? Log in