Solved RSA 4096 bit using Low Public Exponent Attack - Write up for InCTF 2014 - Crypto 200

This challenge had made me mad, Somehow I finally I managed to solve the challenge. This is an RSA Crypto, given a cipher and public key. This is RSA low public exponent attack, e=3.

It's a 4096 bit key and its difficult to break it. But we got a low public exponent value, e=3. While googling I got a nice writeup from the blog http://eindbazen.net/2012/05/plaidctf-2012-rsa/

""" 
ciphertext = pow(plaintext, 3) % modulus
 
# 'ciphertext' is the remainder, so all we need to know to take the cubic root is the quotient 'k'

ciphertext + modulus * k = pow(plaintext, 3) 

"""

I used this idea to solve the challenge but I got failed, after so many tries I found that the program does checks the condition at test = 0.

The output is

GMpy is the nice package for solving the large numbers in python. Masking is the nice idea, I learnt from his blog. Printable characters are always from the ascii value 32 - 128 which are lesser than 2**7. In 8 bit representation, the printable's 8th bit is always 0. So we used masking to find the exact number we want.