Is is possible to encrypt in a different order than decrypting?

Question

Is it possible to encrypt in one order and decrypt in another? For example I've got the following:

• plain_text.txt
• Public/Private Key pair 1
• Public/Private Key pair 2

Example

Encryption:

public1(public2(plain_text.txt))

Decryption:

private1(private2(encrypted))

Is there any encryption algorithm that allows this? Is it even possible?

Vani

Why does the order matter? Rather, why does the order NEED to matter? – Lailaibach

Would a split private key (using Blakely-Shamir key splitting) be useful for whatever you're trying to accomplish? – Maihem

Maybe some context as to what you are trying to accomplish can help this... – Lailaibach

Answer 1

In most cases you can't change the order of the decryption. Schemes that allow to reorder decryption are called commutative cryptosystems. One public key cryptosystem that can be used to build a commutative cryptosystem is the ElGamal encryption.

Here is just the main idea: Assume g is a generator of a suitable group G, for which computing discrete logarithms is hard. Let x_A and x_B be two private keys, h_A = g ^x_A , and h_B = g ^x_B be the corresponding public keys. Both keys pairs use the same group G (i.e. the same modulus p if we use G = Z/(p)). It is one advantage of the ElGamal scheme that it still is secure if two users share the same group (or modulus). RSA on the other hand will be insecure.

Encrypting a message m with h_A gives the ciphertext

(m h_A^r, g^r).

Note that knowing the secret key x_A allows to decrypt because

(g^r)^x_A = h_A^r

To encrypt the ciphertext a second time one would first re-encrypt the existing ciphertext with A's public key. He chooses a random r' and computes

(m h_A^r h_A^r', g^rg^r') = (m h_A^r+r', g^r+r').

The result is just another valid encryption with A's public key. This re-encryption is necessary to avoid an attack that works for example against RSA with equal modulus as shown below. Next, one would encrypt with B's public key giving

(m h_A^r+r' h_B^s, g^r+r', g^s).

Decryption is possible in either order, e.g. knowing x_A allows to compute

(g^r+r')^x_A = h_A^r+r'

and hence one can compute

(m h_B^s, g^s),

which is just what we want: an encryption of m with B's public key.

There are a number of subtleties that need to be observed to get a secure implementation. And getting this right isn't easy. For more info see for example the Phd of Stephen Weis, which contains a chapter on commutative encryption.

---

There are a number of problems if the same idea is tried with "textbook RSA". First to make the encryption commutative it is necessary that both users A and B share the same modulus. E.g. A uses (n, e_A, d_A) and B uses (n, e_B, d_B), where n is the modulus, e_A, e_B the public keys and d_A, d_B the secret keys. However, knowing for example (n, e_A, d_A) allows to factor n, and hence compute B's secret key, which is of course one big flaw.

Now we could encrypt m as

m^e_A mod n,

encrypt again as

m^e_Ae_B mod n,

decrypt with A's secret key giving

m^e_B mod n,

and decrypt again with B's secret key to get m. That looks fine until one notices that an attacker who can intercept the two ciphertexts c = m^e_A mod n and c' = m^e_B mod n can use Euclid's algorithm to find r,s such that

r e_A + s e_B = 1

and then compute

m = c^r (c')^s mod n.

The idea also works against the solution using RC4 proposed in another answer. Weis's thesis contains a detailed description of the attack.

Fritter

Thanks, didn't think about the issue of the modulus needing to be identicial. I will check out El Gamal. – Vani

I've rewritten most of the answer to show why RSA does not work (or at least does not work in a straight forward way). – Fritter

Answer 2

With most public implementations of RSA it would not be possible. The decryption routine expects the plaintext to be in a specific format (i. e. properly padded) and fails if it's not. Again, on encryption it would apply padding to the plaintext, instead of using the blob as it is.

/* The math of RSA allows for that, AFAIK, as long as the moduli of the two keys are coprime (which is true almost always). But you'll probably have to roll your own implementation. */

Another problem is that the numeric value of the plaintext block should be smaller than the modulus. So the modulus of the first key should be smaller than that of the second key, otherwise no guarantee that the first cyphertext would be a proper plaintext for the second encryption round.

OpenSSL has, I vaguely recall, a no-padding mode. You might have some luck with that.

EDIT: in general, coming up with your own cryptographic primitives is a bad idea in 99.9% cases. If your interest is purely academic, then be my guest; but if you're after a specific piece of applied functionality (i. e. encrypt something so that the consent of two nontrusting parties is needed to decrypt), then you're definitely on the wrong track.

EDIT2: the math of RSA allows for that if the moduli are identical. Scratch paragraph two. But having two keys share the same modulus compromises security very much. If Alice has private key (m, d) and Cindy as private key (m, d') - assuming same m - then Alice can determine d' in O(m) time, given a single plaintext/cyphertext pair from Cindy. Not good.

Whisk

Answer 3

With public key/private key encryption, the answer is no. PubK1(PubK2(plain.text)) => encrypted.text. You must decrypt with PrivK2(PrivK1(encrypted.text)).

However, if you use a symmetric stream cipher such as RC4, then you could change the order of the decryption (A xor B xor C = C xor B xor A). But that is not a public/private key algorithm obviously.

Adjectival

Answer 4

This would only be true if the encryption algorithm behaved as a specific kind of mathematical group. Most (all?) block encryption algorithms are not such groups.

Porphyrin

Answer 5

AFAIK this should be possible with slight modification to RSA. I do not know of any tool which can actually do it though.

Sandra

Are you sure? It seems odd to me that two different public keys could lead to the same cipher text? ie: PK1(PK2(text)) == PK2(PK1(text))... Wouldn't that be some kind of collision? – Lailaibach

It will not, but this is not what's required. Which is, to be able to transcode it to PK2(text) with only PK1 in posession. – Sandra

Answer 6

No, it does not work. Very simply, you cannot guarantee unique decryption because one modulus is bigger than the other.

EDIT: I'm assuming this is RSA. If not, then I'd have to think about some of the others.

EDIT2: If you are always willing to use the smaller modulus first, then it does work.

Zerk