2
$\begingroup$

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?

$\endgroup$
  • 2
    $\begingroup$ I believe that essentially any known public key encryption algorithm, other than RSA, works like that; the public key only encrypts, and the private key only decrypts... $\endgroup$ – poncho Sep 29 '17 at 13:23
  • 1
    $\begingroup$ ... with the caveat that you will always be able to derive the public key from the private key.. $\endgroup$ – SEJPM Sep 29 '17 at 13:30
  • $\begingroup$ BillRichards, if you are the same as the Charles Gates who asked this question, you may want to get your accounts merged so you can actually reply to comments yourself. $\endgroup$ – SEJPM Sep 29 '17 at 13:40
  • 1
    $\begingroup$ @poncho there was an edit attempt on the question saying "@poncho, I can't create comments, but I believe that you can make a public key from a private key.". $\endgroup$ – SEJPM Sep 29 '17 at 13:40
  • $\begingroup$ Yeah, this is true, for most algorithms, there's an efficient way to generate the public key from the private one; you're looking for something that make it infeasible to encrypt with the private key? $\endgroup$ – poncho Sep 29 '17 at 14:08
3
$\begingroup$

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".

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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