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?

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.