Eu gerou uma chave privada e pública com os seguintes comandos:

openssl genrsa -out private_key.pem 512
openssl rsa -in private_key.pem -pubout -out public_key.pem

Eu então tentei carregá-los com um script python usando Python-RSA:

import os
import rsa

with open('private_key.pem') as privatefile:
    keydata = privatefile.read()
privkey = rsa.PrivateKey.load_pkcs1(keydata,'PEM')

with open('public_key.pem') as publicfile:
    pkeydata = publicfile.read()

pubkey = rsa.PublicKey.load_pkcs1(pkeydata)

random_text = os.urandom(8)

#Generate signature
signature = rsa.sign(random_text, privkey, 'MD5')
print signature

#Verify token
try:
    rsa.verify(random_text, signature, pubkey)
except:
    print "Verification failed"

Meu script python falha quando tenta carregar a chave pública:

ValueError: No PEM start marker "-----BEGIN RSA PUBLIC KEY-----" found