# Do public/private pairs work both ways?

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.

-
It's possible in principle, but useless in practice. –  CodesInChaos May 4 '12 at 18:58

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.

-