Three-pass Protocol - Massey-Omura Cryptosystem

Massey-Omura Cryptosystem

The Massey-Omura Cryptosystem was proposed by James Massey and Jim K. Omura in 1982 as a possible improvement over the Shamir protocol. The Massey-Omura method uses exponentiation in the Galois field 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 Lagrange's theorem implies that mde=m for all m in GF(2n)* .

Each element of the Galois field GF(2n) is represented as a binary vector over a normal basis in which each basis vector 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 order. By using this representation, exponentiations by powers of 2 can be accomplished by cyclic shifts. 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.