Three-pass protocol

<h2 id="shamir-three-pass-protocol">Shamir three-pass protocol</h2>
The first three-pass protocol was the <a href="/facts/Adi_Shamir/CTnaUeP6">Shamir</a> three-pass protocol developed circa in 1980. It is also called the Shamir No-Key Protocol because the sender and the receiver do not exchange any keys, however the protocol requires the sender and receiver to have two private keys for encrypting and decrypting messages. The Shamir algorithm uses <a href="/facts/Exponentiation/pac6QY2g">exponentiation</a> modulo a large <a href="/facts/Prime_number/L20FLkgn">prime</a> as both the encryption and decryption functions. That is E(e,m) = me mod p and D(d,m) = md mod p where p is a large prime. For any encryption exponent e in the range 1..p-1 with gcd(e,p-1) = 1. The corresponding decryption exponent d is chosen such that de ≡ 1 (mod p-1). It follows from <a href="/facts/Fermat%27s_Little_Theorem/qIjSIm2s">Fermat's Little Theorem</a> that D(d,E(e,m)) = mde mod p = m.
The Shamir protocol has the desired commutativity property since E(a,E(b,m)) = mab mod p = mba mod p = E(b,E(a,m)).

<h2 id="masseyomura-cryptosystem">Massey–Omura cryptosystem</h2>
The Massey–Omura Cryptosystem was proposed by <a href="/facts/James_Massey/qyfqKnQH">James Massey</a> and <a href="/facts/Jim_K._Omura/gV7FkchV">Jim K. Omura</a> in 1982 as a possible improvement over the Shamir protocol. The Massey–Omura method uses <a href="/facts/Exponentiation/pac6QY2g">exponentiation</a> in the <a href="/facts/Finite_field/UkMGJo3m">Galois field</a> GF(2n) as both the encryption and decryption functions. That is E(e,m)=me and D(d,m)=md where the calculations are carried out in the Galois field. For any encryption exponent e with 0<e<2n-1 and gcd(e,2n-1)=1 the corresponding decryption exponent is d such that de ≡ 1 (mod 2n-1). Since the multiplicative group of the Galois field GF(2n) has order 2n-1 <a href="/facts/Lagrange%27s_theorem_(group_theory)/VgyNjGlz">Lagrange's theorem</a> implies that mde=m for all m in GF(2n)* .
Each element of the Galois field GF(2n) is represented as a <a href="/facts/Binary_numeral_system/a6JDSRPs">binary</a> <a href="/facts/Row_vector/pPuRr9Xk">vector</a> over a <a href="/facts/Normal_basis/3bhymK7j">normal basis</a> in which each <a href="/facts/Basis_vector/89IPoN6c">basis vector</a> is the square of the preceding one. That is, the basis vectors are v1, v2, v4, v8, ... where v is a field element of maximum <a href="/facts/Order_(group_theory)/Cl3tKGFg">order</a>. By using this representation, exponentiations by powers of 2 can be accomplished by <a href="/facts/Circular_shift/noSNJs87">cyclic shifts</a>. This means that raising m to an arbitrary power can be accomplished with at most n shifts and n multiplications. Moreover, several multiplications can be performed in parallel. This allows faster hardware realizations at the cost of having to implement several multipliers.

<h2 id="security">Security</h2>
A 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
 )
 
 
 {\displaystyle E(s,m)}
 
⁠, ⁠
 
 
 
 E
 (
 r
 ,
 E
 (
 s
 ,
 m
 )
 )
 
 
 {\displaystyle E(r,E(s,m))}
 
⁠ and ⁠
 
 
 
 E
 (
 r
 ,
 m
 )
 
 
 {\displaystyle E(r,m)}
 
⁠.
For the encryption functions used in the Shamir algorithm and the Massey–Omura algorithm described above, the security relies on the difficulty of computing <a href="/facts/Discrete_logarithm/k8TXh5bL">discrete logarithms</a> in a finite field. If an attacker could compute discrete logarithms in GF(p) for the Shamir method or GF(2n) for the Massey–Omura method then the protocol could be broken. The key s could be computed from the messages mr and mrs. When s is known, it is easy to compute the decryption exponent t. Then the attacker could compute m by raising the intercepted message ms to the t power. K. Sakurai and H. Shizuya show that under certain assumptions breaking Massey–Omura cryptosystem is equivalent to the <a href="/facts/Diffie%E2%80%93Hellman/xR4YQcaD">Diffie–Hellman</a> assumption.

<h2 id="authentication">Authentication</h2>
The three-pass protocol as described above does not provide any <a href="/facts/Authentication/64y4S69b">authentication</a>. Hence, without any additional authentication the protocol is susceptible to a <a href="/facts/Man-in-the-middle_attack/dx4cojdz">man-in-the-middle attack</a> if the opponent has the ability to create false messages, or to intercept and replace the genuine transmitted messages.

<ul><li><a href="https://patents.google.com/patent/US4567600">U.S. patent 4,567,600</a>, U.S. patent on the Massey–Omura cryptosystem</li>
<li>Konheim, Alan G. (1981). Cryptography: A Primer. pp. 346–347.</li>
<li>Menezes, A.; VanOorschot, P.; Vanstone, S. (1996). Handbook of Applied Cryptography. pp. 500, 642.</li>
<li>Sakurai, K.; Shizuya, H. (1998). <a href="https://doi.org/10.1007%2Fs001459900033">"A Structural Comparison of the Computational Difficulty of Breaking Discrete Log Cryptosystems"</a>. Journal of Cryptology. 11: 29–43. <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1007%2Fs001459900033">10.1007/s001459900033</a>.</li></ul>

Three-pass protocol open-in-new

Three-pass protocol