## New Algorithm based on The Three Pass Protocol

This blog is authored by Rohit Pandharkar a fellow CRYPTOcrat. Rohit is currently pursuing his under graduate studies at College of Engineering Pune. He has great interests in Cryptography, Mathematics and at this early stage has already published couple of research papers related to Cryptography.

You can find more information about Rohit on his LI Profile.

**Introduction:**

**Adi Shamir’s** **Three Pass Protocol** was proposed around 1980 is a creative thought of using commutative property of certain mathematical functions. It calls for 3 passes between Alice and Bob for communicating certain message ‘x’. It enables the message to be transferred from first party to the other without exchanging any encryption keys.

Here is a quick summary of Shamir’s idea:

Pass 1: A to B-Transmission of a masked message ‘x’ from Alice to Bob

Pass 2: B to A- Introducing a contribution/impression from Bob’s end

Pass 3: A to B-Alice removes the mask on the original message ‘x’ that she had introduced but the imprint inserted by Bob still prevents it from being revealed.

After Pass 3: Bob removes this imprint after the third pass, by a computation at his end.

This effectively, recovers the message ‘x’ as all masks have been removed now and since this recovery happens at Bob’s end, Eavesdropper E will not have access to ‘x’

**Massey Omura Algorithm:**

Let us now look at this well known algorithm based on Shamir’s protocol:

Alice and Bob agree over prime: **‘p’**

Alice decides private keys: **m,n** such that **m*n=k(p-1)+1,** **k**: **Integer,** **secret message ‘x’ < p**

Bob decides private keys: **M,N** such that **M*N=z(p-1)+1**, **z**: **Integer.**

Passes:

Pass 1: **Alice** sends **A = [x ^{m} mod p]** to

**Bob**.

Pass 2: **Bob** raises **A** by **‘M’**, and sends back **B= [A ^{M} mod p]**

Pass 3: **Alice** raises this **B** by **‘n’** and sends **C= [B ^{n} mod p] **to

**Bob**

At **Bob’s** end: **Bob** computes **D=[C ^{N }mod p]**=

**‘x’**è

**Secret Message**

The proof is very simple, based on Fermat’s little theorem, for details you may refer to the following link http://www.mathlab.cornell.edu/computer_and_portfolio/discrete/prime_power/

**New Proposal**:

As mentioned before the Massey Omura algorithm uses *exponentiation* of the part sent by Alice, Bob has to wait for Alice to send in the result of first pass. This dependency continues in the subsequent second pass, with roles reversed, and repeats in the third pass.

This adds an element of ‘wait period’ during processing and transmission. Secondly, Bob is required to carry out (x^{m} mod p)^{M}.

Now let’s look at a possible improvement in the processing above. The rationale for this improvement is as follows

1. Is it possible for Bob to be ready with his imprint, even before the first pass is received, and immediately add it once Bob receives it?

2. Is it possible to have simple multiplication by some (what we call) “Adulteration” rather than exponentiation for masking.

So here we go:

How about, having a **Salting number** – **‘y’**, decided at Bob’s end, just like **‘x’**, however, here **‘y’** need not really be a **secret**, but only a salting number used to add the so called **adulteration**. This apparently provides an affirmative answer to both the questions raised above.

Now the requirement is, the adulteration must also be **cleaned-up** after third pass, at Bob’s end, so that he unfurls the real hidden message.

All this sounds on the lines of Shamir’s core idea, however, we could use a **multiplicative** **adulteration**, instead of **exponential masking** used by Massey Omura.

The questions that need deeper research are -

1. What are the possible constraints on the selection of **salting number ‘y’** for using it as **adulterating** element?

2. How to find the **Multiplicative Inverse** of **‘y’** to reveal the hidden message **‘x’** enabling us to clean-up the **adulteration** introduced? (to be done at Bob’s end after the third pass).

3. Will that create symmetry issues? (Massey Omura is symmetric in terms of private key selection criterion for Alice and Bob.)

If you have answers, more questions or comments about this post please feel free to send in those using the “Comments” section below.

I shall leave this post unconcluded and in the following part we will look at a much detailed analysis which apparently is my proposal of this new algorithm. Stay tuned.

## Update : 3rd August 2008

Continuing our previous discussion on this topic We will now look at the details of this proposed algorithms.

**Selection of private Keys : **Alice and Bob agree over a big prime ‘p’.

**Decide over primes : **Alice and Bob privately pick some large primes m and M respectively. Each also checks that their primes have no common factor with *p*-1. (Here *p* is the publicly known prime).

**Solving Diophantine equations : **Alice privately finds an integer n so that **m+n=(p-1)z+1, **where z is any integer. And Bob finds an integer N so that that **M+N=(p-1) k, **where k is any integer. *Then, m and n are the private keys of Alice, and M and N are private keys of Bob.*

**Message and Secret number selection : **Alice selects her message x and Bob decides his secret number y such that x<<p and y<<p.

**The Scheme**

Alice (User A) | Bob (User B) |

Alice’s Step 1:Compute A=x and transmit A to Bob. ^{m} (mod p) Alice’s Step 2: Compute C=[(B)*x and transmit to Bob.^{n} ](mod p) |
Bob’s Step 1: Compute B=and transmit B to Alice. [(A)*y ^{M} ] (mod p) Bob’s Step 2: Compute D=This will actually be the original message x.[(C)*y ^{N} ](mod p) |

The proof of the algorithm is based on the Fermat’s little theorem, where in ‘y is the salting number used for multiplicative addition. Here, the powers of ‘y’ die down, (refer selection of M+N) and only a single power of ‘x’ survives because of Fermat’s little theorem. The introduction of salting number ‘y’ and multiplicative adulteration help us.

*Questions answered by this technique*

**1. Is it possible for Bob to be ready with his imprint, even before the first pass is received, and immediately add it once Bob receives it? **Yes: The imprints can be based on powers of ‘y’ which Bob already knows.

**2. Is it possible to have simple multiplication by some (what we call) “Adulteration” rather than exponentiation for masking.**

Yes, the above algorithm does so by multiplying by y^{M} and y^{N}

*Now, answering further questions raised in the earlier part of the article:*

1. What are the possible constraints on the selection of **salting number ‘y’** for using it as **adulterating** element?

y is an integer <p.

2. How to find the **Multiplicative Inverse** of **‘y’** to reveal the hidden message **‘x’** enabling us to clean-up the **adulteration** introduced? (to be done at Bob’s end after the third pass).

The multiplicative inverse of **y ^{M}** is indirectly,

**y**by using Fermat’s little theorem.

^{N }3. Will that create symmetry issues? (Massey Omura is symmetric in terms of private key selection criterion for Alice and Bob.)

Yes, it does, the selection of private keys by Bob and Alice does not use symmetric expressions.

If you have answers, more questions or comments about this post please feel free to send in those using the “Comments” section below.

## 2 Comments

** Please note the views expressed in the comments below are that of the commenter and the owners of this website may not agree with the views expressed.**

RSS feed for comments on this post.

Sorry, the comment form is closed at this time.

Massey Omura also has elliptic curve version. It would be interesting to know your solution of “salting” but in the proposal you are indicating, do you still want Alice and Bob to agree on the prime p? You will only be cutting down on exponentiation time by this approach. Problem of authentication will still remain in practical application. I am not recalling of serious cryptanalysis of Massey Omura scheme. If you know any reference it would be worth reading and do let me know.

Sir,

I looked over for the cryptanalysis of Massey Omura and found that Samuel S. Wagstaff has given the detailed cryptanalysis of Massey Omura in his book “Crytanalysis of Number Theoretic Ciphers”. What you say is correct though, my algorithm still needs A and B to agree over p, and it only reduces the “waiting time” involved in Massey Omura as Bob has to wait for Alice to send message first as he will raise the same message in Massey Omura system.I am looking over the possible solutions for authentication problems in general. I am working on the same.