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 = [xm mod p] to Bob.
Pass 2: Bob raises A by ‘M’, and sends back B= [AM mod p]
Pass 3: Alice raises this B by ‘n’ and sends C= [Bn mod p] to Bob
At Bob’s end: Bob computes D=[CN 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 (xm 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 m (mod p) and transmit A to Bob.
Alice’s Step 2: Compute C=[(B)*x n ](mod p) and transmit to Bob. |
Bob’s Step 1: Compute B= [(A)*y M ] (mod p) and transmit B to Alice.
Bob’s Step 2: Compute D=[(C)*y N ](mod p)This will actually be the original message x. |
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 yM and yN
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 yM is indirectly, yN by using Fermat’s little theorem.
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.
