how to decrypt a message using exported RSA public key with PyCrypto?

Question

I faced this challenge where I asked to decrypt an encrypted message using the exported public key. I am given with 3 files:

The encryption python script
The encrypted message
The exported public key

I tried to import the public key and then decrypt but I think I have to figure out the private key in order to decrypt the message.

The encryption code is:

import gmpy
from Crypto.Util.number import *
from Crypto.PublicKey import RSA
from Crypto.Cipher import PKCS1_v1_5

message = open('message', 'r').read() * 30

def ext_rsa_encrypt(p, q, e, msg):
    m = bytes_to_long(msg)
    while True:
        n = p * q
        try:
            phi = (p - 1)*(q - 1)
            d = gmpy.invert(e, phi)
            pubkey = RSA.construct((long(n), long(e)))
            key = PKCS1_v1_5.new(pubkey)
            enc = key.encrypt(msg).encode('base64')
            return enc
        except:
            p = gmpy.next_prime(p**2 + q**2)
            q = gmpy.next_prime(2*p*q)
            e = gmpy.next_prime(e**2)

p = getPrime(128)
q = getPrime(128)
n = p*q
e = getPrime(64)
pubkey = RSA.construct((long(n), long(e)))
f = open('pubkey.pem', 'w')
f.write(pubkey.exportKey())
g = open('msg.enc', 'w')
g.write(ext_rsa_encrypt(p, q, e, message))

A 256 bit key (sic!) is quite small. You may be able to factor the modulus with a (general) number field sieve implementation. — Artjom B.
@ArtjomB. thanks, I now created the private key but how can I decrypt the message using "key = PKCS1_v1_5.new(privatekey); key.decrypt(encmsg.decode('base64'))"? PKCS1_v1_5 requires a sentinel. How can I know the sentinel in order to decrypt? — RAHAB2
A sentinel is an object that you get back in case there was a decryption error. You decide what the sentinel is. -1 could be a sentinel. "chicken" could be a sentinel. You get the idea. — Artjom B.
@ArtjomB., thank again! key.decrypt(encmsg.decode('base64'),"---") returns with the error "Ciphertext with incorrect length". I built the key in the right way using n, e, d (and private key corresponding exactly with the original public key). What could be the solution for that? — RAHAB2
@RAHAB2 You probably have to split the message using the key size. — Maarten Bodewes

Ivan Strelkov Ivan Strelkov · Accepted Answer · 2016-11-15T08:23:36

As pointed out in the comments 256 keys are quite small and can be factorized easily. First you have to reconstruct the prime numbers used in key generation. Finding the modulus and exponent is an easy one liner with openssl:

$ openssl rsa -in <your-public-key> -pubin -text -modulus

This should output something like

Exponent: <decimal-value> (<hex-value>)
Modulus=<hex-value>

Now you can factorize the modulus with msieve or search for it within the https://factordb.com/ database. This will give you your "p" and "q". Since the encryption code is not quite RSA you have to write your own decrypt function, which should look like this:

def ext_rsa_decrypt(p, q, e, msg):
    m = bytes_to_long(msg)
    while True:
        n = p * q
        try:
            phi = (p - 1)*(q - 1)
            d = gmpy.invert(e, phi)
            privkey = RSA.construct((long(n), long(e), long(d)))
            key = PKCS1_v1_5.new(privkey)
            enc = key.decrypt(msg, "a")
            return enc
        except Exception, ex:
            traceback.print_exc()
            p = gmpy.next_prime(p**2 + q**2)
            q = gmpy.next_prime(2*p*q)
            e = gmpy.next_prime(e**2)

Now you should have everything you need to decrypt the message, just don't forget to base64 decode the encrypted message before passing it to the decrypt function.

how to decrypt a message using exported RSA public key with PyCrypto?

1 Answers