PlaidCTF 2012 Write Up： RSA 200

This problem is the second time which try to break RSA. In the previous practice, the reason to break RSA is using module already factored. In this problem, the vulnerability to break RSA is using small exponent number.

In this problem, an encrypted data is given with an public key.
Using  RSA python module, we can find information about RSA algorithms.
(or use command: openssl rsa -pubin -in id-rsa.pub -text)

The exponent  number used is 3, which is very small. And increasing the risk of rsa. Observing that the encrypt message is related small too, this give us a clue to solve rsa.

According to RSA encrypt schema, the formula below

It can reduce to  

With e=3, we can get following formula 

Since we have value of M and N, while C is plain text we need to solve, only K is unknown. With small small M and e, we can consider N is related small.
So we wrote a program which use brute force to find K. To check if the 3-rd root of C-KN is an integer, we can find the true K and the key.

from Crypto.PublicKey import RSA
from Crypto.Util import asn1
from base64 import b64decode
import libnum
import math
import gmpy

pubkey = open('id-rsa.pub').read()
key = RSA.importKey(pubkey)
print "n = "
print key.publickey().n
print "e = "
print key.publickey().e
nkey = key.publickey().n
message = open("enc.dat",'r').read()
print libnum.s2n(message[:-1])

ct = libnum.s2n(message.rstrip())
print libnum.len_in_bits(ct)

c = ct
k = 1
while True:
        if k % 10000 == 0 :
                print k
        p = gmpy.root(c, 3)[0]
        if pow(p,3,nkey)==ct:
                print libnum.n2s(p)
                break

        c += nkey
        k+=1