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
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.
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)
Answer the questions below
What is the flag?
I improved the initial script and used this script to find the flag
from Cryptodome.Util.number import long_to_bytes
from sympy import nextprime, gcd
c = 3591116664311986976882299385598135447435246460706500887241769555088416359682787844532414943573794993699976035504884662834956846849863199643104254423886040489307177240200877443325036469020737734735252009890203860703565467027494906178455257487560902599823364571072627673274663460167258994444999732164163413069705603918912918029341906731249618390560631294516460072060282096338188363218018310558256333502075481132593474784272529318141983016684762611853350058135420177436511646593703541994904632405891675848987355444490338162636360806437862679321612136147437578799696630631933277767263530526354532898655937702383789647510
n = 15956250162063169819282947443743274370048643274416742655348817823973383829364700573954709256391245826513107784713930378963551647706777479778285473302665664446406061485616884195924631582130633137574953293367927991283669562895956699807156958071540818023122362163066253240925121801013767660074748021238790391454429710804497432783852601549399523002968004989537717283440868312648042676103745061431799927120153523260328285953425136675794192604406865878795209326998767174918642599709728617452705492122243853548109914399185369813289827342294084203933615645390728890698153490318636544474714700796569746488209438597446475170891
e = 0x10001
import gmpy2
p = gmpy2.iroot(n, 2)[0]
while n % p != 0:
p = gmpy2.next_prime(p)
q = n // p
phi = (p-1)*(q-1)
d = gmpy2.invert(e, phi)
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.
