Exchanging encrypted messages, and decrypting without a public key?

Question

I know very little about encryption, but I was hoping someone could shed light on this cipher text exchange scheme I worked out in my head this morning:

Bob wants to send Alice a message but doesn't want anyone in the middle to discover what the message is.

We'll call the message $p$ and encode it as a number. This is how it goes; Bob chooses a random but secret number $x$. He calculates $p \times x = c$ and sends his cipher text $c$ to Alice. Alice then chooses a random but secret number $a$. She calculates $a \times c = q$ and then sends $q$ back over to Bob. Bob does $q / x = f$ and sends it back to Alice. Alice then does $f / a = p$.

Sorry if it makes no sense, but what kind of encryption is this called when there's no public key yet a message is transferred encrypted and deciphered without any secret passwords being exchanged?

Answer 1

You're describing a form of three-pass protocol, which is a communication mechanism where neither party needs to know each other's secret key. Wikipedia describes a helpful metaphor using a box that can be locked by two padlocks:

First, Alice puts the secret message in a box, and locks the box using a padlock to which only she has a key. She then sends the box to Bob through regular mail. When Bob receives the box, he adds his own padlock to the box, and sends it back to Alice. When Alice receives the box with the two padlocks, she removes her padlock and sends it back to Bob. When Bob receives the box with only his padlock on it, Bob can then unlock the box with his key and read the message from Alice.

I assume you're using multiplication and division simply as example functions, but as others have mentioned these aren't suitable operations for this task because they're too easy to reverse. However there do exist actual encryption and decryption functions which do work this way - the necessary property is for the operations to be commutative, so that the encrypting and decrypting do not need to be done in a certain order.

In order for the encryption function and decryption function to be suitable for the Three-Pass Protocol they must have the property that for any message m, any encryption key e with corresponding decryption key d and any independent encryption key k, D(d,E(k,E(e,m))) = E(k,m). In other words, it must be possible to remove the first encryption with the key e even though a second encryption with the key k has been performed. This will always be possible with a commutative encryption. A commutative encryption is an encryption that is order-independent, i.e. it satisfies E(a,E(b,m))=E(b,E(a,m)) for all encryption keys a and b and all messages m. Commutative encryptions satisfy D(d,E(k,E(e,m))) = D(d,E(e,E(k,m))) = E(k,m).

...

A [further] necessary condition for a three-pass algorithm to be secure is that an attacker cannot determine any information about the message m from the three transmitted messages E(s,m), E(r,E(s,m)) and E(r,m).

This second condition eliminates multiplication and division, since we could look at the three transmitted messages s*m, r*s*m, and r*m and easily compute m from them.

Answer 2

First up: it does use public keys in contrast to your claims. To be more specific – $q$ is Alice’s public key, and $f$ is Bob‘s public key. Both are transferred in public and might be intercepted by a MITM.

This brings me to the next point: the system you worked out in your head is highly insecure.

We'll call the message $p$ and encode it as a number. This is how it goes; Bob chooses a random but secret number $x$. He calculates $p \times x = c$ and sends his cipher text $c$ to Alice. Alice then chooses a random but secret number $a$. She calculates $a \times c = q$ and then sends $q$ back over to Bob. Bob does $q / x = f$ and sends it back to Alice. Alice then does $f / a = p$.

So, practically your idea goes like this:

• $X_{Bob} \times P_{Bob} = C_{Bob}$
• $C_{Bob} \rightarrow$ Alice.
• $A_{Alice} \times C_{Bob} = Q_{Alice}$
• $Q_{Alice} \rightarrow$ Bob.
• …

Note: at this stage, a MITM attacker could simply take the intecepted $Q_{Alice}$ and the intercepted ciphertext $C_{Bob}$ to calculate Alice’s secret $A_{Alice}$, doing a simple $C_{Bob} / Q_{Alice} = A_{Alice}$. This means that – in contrast to what you think – Alice’s secret $a$ is not secret at all.

There are a few other issues with your idea, but since things are practically broken at this point already, I will refrain from diving in any deeper. My advice would be to not try to reinvent the wheel and rather rely on available, well-vetted cryptographical protocols instead. (One of the things that comes to mind is the Diffie–Hellman key exchange, which comes remarkably close to your idea.)

Answer 3

This cryptosystem can be broken very easily after the first response sent by Alice. Let's say the Man in the middle (M) captures the first 2 messages, c and q. M simply calculates q/c which reveals the secret number: a. If M is able to read the third message (f) then he concludes the attack by calculating f/a.

Answer 4

Why do you want to create your own crypto instead of looking at an existing one? You are looking for a hybrid encryption scheme in which users with a Diffie Hellman key exchange. They agree on a secret symmetric key and then they encrypt their data with a common secret key. What you proposed seems vulnerable to man in the middle attacks.

This is malleable: an adversary who intercepts the first message $xp$, instead transmits to Alice a $w$. Alice computes $aw$, then Bob computes $aw/x$ and finally Alice recovers gibberish data