I have modulus and private exponent. How to construct RSA private key and sign a message?

Question

I am newbie in cryptography and pycrypto.

I have modulus n and private exponent d. From what I understand after reading some docs private key consists of n and d.

I need to sign a message and I can't figure out how to do that using pycrypto. RSA.construct() method accepts a tuple. But I have to additionally provide public exponent e to this method (which I don't have).

So here is my question. Do I have to compute e somehow in order to sign a message?

It seems I should be able to sign a message just by using n and d (that constitute private key). Am I correct? Can I do this with pycrypto?

Thanks in advance.

Answer 1

Actually for decrypting a message encrypted with the public key it's enough to have the private exponent.

That also means you can sign a message, because signing basically is just *de*crypting the plaintext with the private key, which when *en*crypted with the public key will give the plaintext again. Usually you use a hash digest on the plaintext before and sign that...

The reason why you can't decrypt a message uing only n and d with pyrcypto is that it does a blinding step during message decryption, which involves the public exponent, but isn't really needed for the decryption.

But by using some calls to the private API this step can be bypassed.

Therefore this should work:

from Crypto.PublicKey import RSA
from Crypto.Util.number import bytes_to_long, long_to_bytes

full = RSA.generate(2048)

# construct key using only n and d
try:
    # pycrypto >=2.5, only tested with _slowmath
    impl = RSA.RSAImplementation(use_fast_math=False)
    partial = impl.construct((full.n, 0L))
    partial.key.d = full.d
except TypeError:
    # pycrypto <=2.4.1
    partial = RSA.construct((full.n, 0L, full.d))   



pub = full.publickey()

# create message with padding
# http://en.wikipedia.org/wiki/RSA_%28algorithm%29#Padding_schemes
cleartext = ...

signature = partial.sign(cleartext, None)

print "validating message: ", pub.verify(cleartext, signature)


message = pub.encrypt(cleartext, None)

# bypassing the blinding step on decrypt
enc_msg=map(bytes_to_long, message)
dec_msg = map(partial.key._decrypt, enc_msg)

print "decrypting: "
for m in dec_msg:
    print long_to_bytes(m)