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)

Answer 2

No, you can't compute e from d.

RSA is symmetric in d and e: you can equally-well interchange the roles of the public and the private keys. Of course, we choose one specially to be private and reveal the other -- but theoretically they do the same thing. Naturally, since you can't deduce the private key from the public, you can't deduce the public key from the private either.

Of course, if you have the private key that means that you generated the keypair, which means that you have the public key somewhere.

Answer 3

If you don't have the public exponent you may be able to guess it. Most of the time it's not a random prime but a static value. Try the values 65537 (hex 0x010001, the fourth number of Fermat), 3, 5, 7, 13 and 17 (in that order).

[EDIT] Simply sign with the private key and verify with the public key to see if the public key is correct.

Note: if it is the random prime it is as hard to find as the private exponent; which means you would be trying to break RSA - not likely for any key sizes > 512 bits.