THM - Cryptosystem

A writeup for the room “Cryptosystem” on TryHackMe

Learn public-key cryptography concepts by analyzing data.

Cryptosystem

Analysis

The challenge involves breaking a flawed RSA implementation to decrypt a message.

While the first prime number p is generated correctly, q is chosen as the nearest prime number to p, which is not recommended.

Ideally, both prime numbers should be generated randomly and should be sufficiently far apart to ensure security.

The attack is based on the fact that, if n = p * q, where p and q are two prime numbers close to each other, they can be found quickly using Fermat’s factorization method.

n = p * q

p = x + y
q = x - y
n = x^2 - y^2 = (x + y) * (x - y)

x^2 = n - y^2 -> We only need a perfect square to find p and q