My question is about RSA signing. In case of RSA signing: encryption -> y = x^d mod n, decryption -> x = y^e mod n x -> original message y -> encrypted message n -> modulus (1024 bit) e -> public exponent d -> private exponent I know x, y, n and e. Knowing these can I determine d?

cryptographyrsapublic-key-encryption

Valacska

Reputation: 33

RSA private exponent determination

My question is about RSA signing.

In case of RSA signing:

encryption -> y = x^d mod n, decryption -> x = y^e mod n

x -> original message
y -> encrypted message
n -> modulus (1024 bit)
e -> public exponent
d -> private exponent

I know x, y, n and e. Knowing these can I determine d?

Upvotes: 3

Answers (3)

Jason S

Reputation: 189836

If you can factor n = p*q, then d*e ≡ 1 (mod m) where m = φ(n) = (p-1)*(q-1), (φ(m) is Euler's totient function) in which case you can use the extended Euclidean algorithm to determine d from e. (d*e - k*m = 1 for some k)

All these are very easy to compute, except for the factoring, which is designed to be intractably difficult so that public-key encryption is a useful technique that cannot be decrypted unless you know the private key.

So, to answer your question in a practical sense, no, you can't derive the private key from the public key unless you can wait the hundreds or thousands of CPU-years to factor n.

Public-key encryption and decryption are inverse operations:

x = y^e mod n = (x^d)^e mod n = x^de mod n = x^kφ(n)+1 mod n = x * (x^φ(n))^k mod n = x mod n

where (x^φ(n))^k = 1 mod n because of Euler's theorem.

Upvotes: 5

Omnifarious

Reputation: 56078

The answer is yes under two conditions. One, somebody factors n. Two, someone slips the algorithm a mickey and convinces the signer to use one of several possible special values for x.

Applied Cryptography pages 472 and 473 describe two such schemes. I don't fully understand exactly how they would work in practice. But the solution is to use an x that cannot be fully controlled by someone who wants to determine d (aka the attacker).

There are several ways to do this, and they all involve hashing x, fiddling the value of the hash in predictable ways to remove some undesirable properties, and then signing that value. The recommended techniques for doing this are called 'padding', though there is one very excellent technique that does not count as a padding method that can be found in Practical Cryptography.

Upvotes: 3

JoshuaRogers

Reputation: 405

No. Otherwise a private key would be of no use.

Upvotes: 1

RSA private exponent determination

Answers (3)

Related Questions