Is there an encryption algorithm with a key that can only be used to decrypt?

Question

I was wondering if there were any encryption algorithms that kinda worked like RSA in the sense that there are two keys, however, one of the keys only decrypts (meaning you can't encrypt with it) and the other key that only encrypts. Is this possible?

Answer 1

There's two fundamental difficulties with what you're asking for.

First, in the usual definition of public-key encryption, the public key is assumed to be, well, public. That is, everybody is assumed to know it, and thus to be able to encrypt messages.

If you don't want everybody to be able to encrypt, then you're no longer doing public-key crypto in the usual sense, and you need to start paying attention to things like exactly who should be allowed to know the (not so) public half of the key pair and how the halves of the key pair should be distributed.

Second, in general, whoever first creates the key pair must, at least temporarily, possess the information necessary the construct both keys. If they want, they can save that information and use it to both encrypt and decrypt any messages.

In standard public-key crypto this is not an issue, since it's usually assumed that the keys are generated by the private key holder, who is supposed to know both keys anyway. But if the private key holder is not supposed to know the "public" key, then we need to either:

• trust the private key holder to forget the public key (and any other information that could be used to reconstruct it) after generating it,
• entrust the key pair generation to some trusted third party (who, if they're not as trustworthy as we think they are, could then eavesdrop on or tamper with any communications encrypted with the keys), or
• somehow generate the key pair using some kind of distributed multi-party computation scheme that doesn't allow any party to learn any parts of the keys they shouldn't know (which is far from a trivial task, if it's even possible).

---

All that said, if we handwave all those issues away (e.g. by assuming a trusted third party that handles key generation and distribution), plain old RSA can be used like this. In fact, I asked a question about using RSA in a very similar manner a while ago.

All we need to do is somehow ensure that:

1. only those who should be able to encrypt messages know the encryption exponent $e$,
2. only those who should be able to decrypt messages know the decryption exponent $d$, and
3. nobody (except maybe the 100% trustworthy key generator) knows the factors $p$ and $q$ of the modulus $n = pq$, or anything else (such as $\lambda(n) = \operatorname{lcm}(p-1,q-1)$) that could be used to reconstruct one exponent from the other.

(The modulus $n$ itself can still be public knowledge.)

Of course, this implies that we cannot use a fixed encryption exponent like $e = 65{,}537$, like most ordinary RSA implementations do, but must instead pick $e$ at random from the set of distinct possible encryption exponents (i.e. positive integers less than and coprime to $\lambda(n)$).

We can do this by repeatedly picking a random odd number $1 < e < \lambda(n)$ until we find one that satisfies $\gcd(e, \lambda(n)) = 1$, and compute $d = e^{-1} \pmod{\lambda(n)}$. Or, equivalently, we can pick $d$ randomly in the same way, and compute $e = d^{-1} \pmod{\lambda(n)}$. Modular inversion is a bijection, so picking $e$ uniformly at random from the entire set of invertible congruence classes ensures that $d$ is also uniformly distributed, and vice versa.

In fact, the latter scheme is essentially* what Rivest, Shamir and Adleman used in the original RSA paper. Using a small, fixed $e$ is a later optimization introduced after it was realized that $e$, being public, doesn't actually need to be random.

The tricky part, of course, is that whoever generates the key pair will still end up knowing both $e$ and $d$, and — if they're not supposed to retain the ability to both encrypt and decrypt — must be trusted to securely forget at least one of these exponents, as well as any other values (including $p$, $q$ and $\lambda(n)$) that would allow them to reconstruct those exponents later.

---

^{*) The original RSA paper uses $\phi(n) = (p-1)(q-1)$ instead of $\lambda(n)$ when computing the modular inverse. This has no real effect on security, it just sometimes produces larger exponents than necessary and allows multiple equivalent key pairs. The original RSA paper also does not specify an actual range to pick $d$ from, but only that it should be "a large, random integer".}