This service provides you an encrypted flag. Can you decrypt it with just N & e? Connect to the program with netcat: $ nc verbal-sleep.picoctf.net 58750 The program’s source code can be downloaded here.
fromsysimportexitfromCrypto.Util.numberimportbytes_to_long,inversefromsetupimportget_primese=65537defgen_key(k):"""
Generates RSA key with k bits
"""p,q=get_primes(k//2)N=p*qd=inverse(e,(p-1)*(q-1))return((N,e),d)defencrypt(pubkey,m):N,e=pubkeyreturnpow(bytes_to_long(m.encode('utf-8')),e,N)defmain(flag):pubkey,_privkey=gen_key(1024)encrypted=encrypt(pubkey,flag)return(pubkey[0],encrypted)if__name__=="__main__":flag=open('flag.txt','r').read()flag=flag.strip()N,cypher=main(flag)print("N:",N)print("e:",e)print("cyphertext:",cypher)exit()
The strength of RSA, which is an asymmetric key algorithm, lies in the difficulty of factorizing large numbers. Specifically, the difficulty of factoring the modulus N into its prime factors p and q. Indeed, N is generated by multiplying these primes together. In this specific case, p and q are small, meaning that N can be easily factored. Let’s move on to the exploitation phase.
🔬 Vulnerability Analysis
Potential Vulnerabilities
Weak Key Generation
🎯 Solution Path
Exploitation Steps
Initial setup
The first thing we need to do is find p and q such that:
$$N=p\times q$$
Once p and q are found, the next step is to calculate the private key, since in an asymmetric key algorithm, one part encrypts with the public key, and the other part can only decrypt with their own private key. Therefore, we use $\phi(N)$ to calculate d, the private key:
$$\phi(N)=(p-1)(q-1)$$
Using the modular inverse, we can then calculate the private key since we know that $e \times d = 1\ (mod\ \phi(N))$. Once we have calculated the private key d, we can decrypt the ciphertext c using the RSA decryption formula:
$$m=c^{d}\ mod\ N$$
By doing so, we will be able to decrypt the text and consequently obtain the flag.
Exploitation
To do this, I used the sympy library for factorization. But first, I extracted the data from the program execution on the server:
Data
Then, I factored N:
Factorization
yielding:
1
2
p = 2
q = 7950045289822903297510861777099505890300764300507691721133678696661597874809525930479020304499777054544735215602592934458749288236605059754549589782918949
Next, I calculated phi, found the private key d, and decrypted the text, retrieving the flag.
Flag capture
Manual Flag
🛠️ Exploitation Process
Approach
The automatic exploit connects to the server, extracts the data, and follows the same procedure described earlier.
