Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Public/private key algorithms such as RSA encrypt a message with a private key but only decrypted with another (mathematically related) key.

Can the public key decrypt the messages encrypted with the private key and the private key decrypt messages encrypted with the public key?
If the algorithm is based on multiplying two big numbers this seems possible. However, I'm not sure.

share|improve this question
    
It's possible in principle, but useless in practice. – CodesInChaos May 4 '12 at 18:58
up vote 10 down vote accepted

Well, first of all, the answer to your question depends quite a lot on whether your asking about RSA specifically, or public key algorithms in general (of which RSA is one example).

For raw RSA, the core operations to convert between the plaintext $M$ and the ciphertext $C$ is:

$C = (M^e) \bmod N$

$M = (C^d) \bmod N$

where the private key is the pair $(N, d)$ and the public key is the pair $(N, e)$. At this very high level, it is obvious that the operation is symmetric, and there's no inherent reason why one couldn't "encrypt" with the private key, and "decrypt" with the public (although "encryption" isn't quite the correct terminology if anyone can decrypt it).

However, it is rarely appropriate to use raw RSA as such; RSA has a homomorphic property that can easily leak information. To avoid such weaknesses, we generally perform padding before and after. So, for RSA public key encryption, we usually do:

$C = (Pad(M)^e) \bmod N$

$M = Depad( (C^d) \bmod N )$

and for performing signature operations, we do:

$C = (Pad(M)^d) \bmod N$

$M = Depad( (C^e) \bmod N )$

Now, it still looks symmetric; however, the security properties we need for the Padding operation differs between public key encryption and signatures. For example, we don't care if an attacker can use the homomorphic properties to cobble together a valid looking $Pad(M)^e$ value; we rather assume that he can compute that directly. However, we have to ensure that, for a signature, he absolutely cannot cobble together a valid looking $Pad(M)^d$ value.

The bottom line: if you want to use RSA to perform signature operations (which is what people usually mean when they ask about 'encrypting with the private key'), you should look at PKCS #1, and do what it says; it's subtler than it looks.

On the other hand (going back to your original question), if you're asking about public key algorithms in general, well, no, you can't usually "encrypt" with the private key; RSA is about the only public key algorithm that can be described as doing signatures that way. Other algorithms (such as DSA) work entirely differently.

share|improve this answer

There is no such thing as "the RSA algorithm", unless you mean raw RSA. There is the RSA problem on which the RSA algorithms rely. This is what Poncho already showed in his answer:

$$C = (M^e) \bmod N$$ and $$M = (C^d) \bmod N$$

so this is nicely symmetrical; you can switch $e$ and $d$ around and it would still work. You would do an entirely different thing semantically though, as providing confidentiality cannot be done by "encrypting" with a private key, as anybody with the public key would be able to decrypt.

Now if the public key would also become a private key, and if it would have the same security as the private key, then you could imagine a protocol that provides security. You'd need a trusted third party to securily create the key pair and to securily distribute the private keys though.


In general, this is not how RSA works in practice:

  • RSA requires a padding to be secure (see the answer of Poncho);
  • RSA often uses a small public exponent, which means that it is insecure to use RSA public exponent for a private key;
  • RSA private key operations must be protected against side channel attacks while RSA public key operations require less protection (as the public key obviously doesn't need to be protected);
  • RSA private key operations often use CRT parameters for a more efficient operation (4x speedup in general) which the public key doesn't provide.

In other words, although the modular exponentiation function may be mathematically identical; the keys, the padding mechanisms, optimizations and protection mechanisms are far from identical for public key and private key operations.


PKI, public key infrastructure, also relies on specific relationships between public and private key pairs. You cannot just switch the public key and private around and expect PKI to keep working as-is.

share|improve this answer
    
Added a higher level answer than that of Poncho, which seems to focus on the padding algorithms. Nothing wrong with that answer of course. – Maarten Bodewes Mar 22 at 16:24

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.