# Challenges: Cryptosystem (TryHackMe)

In this challenge, we intercepted an encrypted communication between Cipher and three associates—Rivest, Shamir, and Adleman. The intercepted file contained an RSA-encrypted message that we were tasked to decrypt in order to reveal a secret key. The encryption used a non-standard approach where one prime factor was chosen as the next prime after the other, which left the modulus vulnerable to factorization. By analyzing the given parameters and leveraging weaknesses in prime selection, we aimed to break the RSA encryption and retrieve the hidden flag.

## **Cryptosystem**

![Character Image](https://tryhackme-images.s3.amazonaws.com/user-uploads/62ff64c3c859dc0042b2b9f6/room-content/62ff64c3c859dc0042b2b9f6-1742203721107.png align="left")

We intercepted a communication between Cipher and some 3 associates: Rivest, Shamir and Adleman. We were only able to retrieve a file.

ORDER: Get the secret key from the recovered file.

```python
from Crypto.Util.number import *
from flag import FLAG

def primo(n):
    n += 2 if n & 1 else 1
    while not isPrime(n):
        n += 2
    return n

p = getPrime(1024)
q = primo(p)
n = p * q
e = 0x10001
d = inverse(e, (p-1) * (q-1))
c = pow(bytes_to_long(FLAG.encode()), e, n)
#c = 3591116664311986976882299385598135447435246460706500887241769555088416359682787844532414943573794993699976035504884662834956846849863199643104254423886040489307177240200877443325036469020737734735252009890203860703565467027494906178455257487560902599823364571072627673274663460167258994444999732164163413069705603918912918029341906731249618390560631294516460072060282096338188363218018310558256333502075481132593474784272529318141983016684762611853350058135420177436511646593703541994904632405891675848987355444490338162636360806437862679321612136147437578799696630631933277767263530526354532898655937702383789647510
#n = 15956250162063169819282947443743274370048643274416742655348817823973383829364700573954709256391245826513107784713930378963551647706777479778285473302665664446406061485616884195924631582130633137574953293367927991283669562895956699807156958071540818023122362163066253240925121801013767660074748021238790391454429710804497432783852601549399523002968004989537717283440868312648042676103745061431799927120153523260328285953425136675794192604406865878795209326998767174918642599709728617452705492122243853548109914399185369813289827342294084203933615645390728890698153490318636544474714700796569746488209438597446475170891
```

### Answer the questions below

What is the flag?

I improved the initial script and used this script to find the flag

```python
from Cryptodome.Util.number import long_to_bytes
from sympy import nextprime, gcd

# Given values from challenge
c = 3591116664311986976882299385598135447435246460706500887241769555088416359682787844532414943573794993699976035504884662834956846849863199643104254423886040489307177240200877443325036469020737734735252009890203860703565467027494906178455257487560902599823364571072627673274663460167258994444999732164163413069705603918912918029341906731249618390560631294516460072060282096338188363218018310558256333502075481132593474784272529318141983016684762611853350058135420177436511646593703541994904632405891675848987355444490338162636360806437862679321612136147437578799696630631933277767263530526354532898655937702383789647510
n = 15956250162063169819282947443743274370048643274416742655348817823973383829364700573954709256391245826513107784713930378963551647706777479778285473302665664446406061485616884195924631582130633137574953293367927991283669562895956699807156958071540818023122362163066253240925121801013767660074748021238790391454429710804497432783852601549399523002968004989537717283440868312648042676103745061431799927120153523260328285953425136675794192604406865878795209326998767174918642599709728617452705492122243853548109914399185369813289827342294084203933615645390728890698153490318636544474714700796569746488209438597446475170891
e = 0x10001

# Step 1: factor n
# n = p * q, q is next prime after p
# We can iterate primes until we find p
import gmpy2

p = gmpy2.iroot(n, 2)[0]   # approx sqrt(n)
while n % p != 0:
    p = gmpy2.next_prime(p)

q = n // p

# Step 2: compute φ(n)
phi = (p-1)*(q-1)

# Step 3: compute private key
d = gmpy2.invert(e, phi)

# Step 4: decrypt
m = pow(c, d, n)
flag = long_to_bytes(m)
print(flag)
```

libraries I had to install for it to run successfully

`pip3 install sympy`

`pip3 show pycryptodome`

then went ahead to run the python script

`python3 script.py`

Through factoring the RSA modulus nnn and computing the private key ddd, we successfully decrypted the ciphertext using Python and cryptographic libraries. The decryption process revealed the secret flag, confirming that the use of consecutive primes in RSA significantly weakens its security. This challenge demonstrated how mathematical weaknesses in cryptosystem design can be exploited to recover sensitive information, emphasizing the importance of secure key generation in cryptography.