Is there a secure cryptographic algorithm where encryption and decryption can be in any order?

Question

I'm looking for a cryptographic algorithm that satisfies the following rules:

E(key1, E(key2, Message)) = E(key2, E(key1, Message))

And obviously the same for decryption as well.

This is probably a long shot as I doubt such an algorithm exists but thought it's worth asking.

Thanks

Answer 1

RSA with the same modulus will do this. Raising to the power a then the power b is the same as raising to power b then a.

But you wouldn't normally use RSA to encrypt your message, you'd use it to encrypt a key - RSA and most asymmetric cryptogrpahy is very time consuming.

Maybe you're after a symmetric algorithm with that property?

Answer 2

There's some references in this paper: http://www.cs.ucla.edu/wing/publication/papers/Yang.VTC04.pdf

One of those is this paper: http://icsd.i2r.a-star.edu.sg/publications/BaoFeng_21190190.pdf

Also, of course, all XOR-based stream ciphers have this property.

Answer 3

If E is just the XOR function between the key (or some cryptographically generated expansion thereof) and the text (cypher or plain), then it will exhibit the property that you are indicating.

That is (key1 XOR message) XOR key2 == (key2 XOR message) XOR key1, so that the keys may be applied in either order for encryption or decryption, but both keys are required to decrypt a message that is thus encrypted.

I can imagine this being used to encrypt a document that requires two participants with individual secret keys. But this scheme won't work, because given the cyphertext, plaintext, and either key, the other key may be trivially recovered.

Answer 4

Two known cryptosystems that satisfy

E(key1, E(key2, Message)) = E(key2, E(key1, Message))

are the Massey Omura crytosystem and Shamir's three-pass protocol. One reason to prefer these two schemes is the following property: an attacker with access to the ciphertexts E(key1, Message), E(key2, Message) and E(key1, E(key2, Message)) can not find the message. On the other hand, the solutions based on RSA or stream cipher can be broken under this assumption.

It does make sense to assume that the an attacker may have access to all the ciphertexts above, since commutative cryptosystems are most likely used in scenarios where the the two keys are kept on different systems. Why else would one need to reverse the order of decryption?

Answer 5

Hi,

Sorry about the barge in and late reply....

E(key1, E(key2, Message)) = E(key2, E(key1, Message))

...that is (key1 XOR message) XOR key2 == (key2 XOR message) XOR key1, so that the keys may be applied in either order for encryption or decryption, but both keys are required to decrypt a message that is thus encrypted.

These are not equivalent. Under the XOR proposal, it is possible to find a third key, key3, such that (key3 XOR message) == ((key1 XOR message) XOR key2). key3 would be (key1 XOR key2). I believe the property does not satisfy what the OP requires.

Going back to my cryptography class (and IIRC), it took mathematicians some time to prove that DES was not closed under its operation, so that there was not short cut into recovery of plain text using 2-key triple des and 3-key triple des. That is, E(key1, E(key2, Message)) != E(key3, message).

Jeff