The Massey–Omura Cryptosystem: A Public Key Commutative encryption Method

The Massey–Omura Cryptosystem: A Public Key Commutative encryption Method

I love reading classic papers and the patents that have helped build the Internet. One classic patent was written by James Massey and Jim K. Omura created the Massey–Omura Cryptosystem in 1982 [1]. It took over three years to be assigned and was assigned to Omnet Associates [here]:

It uses exponentiation in the Galois field GF(2^n) for both the encryption and decryption functions. In this, if we have a message of M, the encryption is:

and

This are operated on with the Galois field. For this we define e

within:

and:

The decryption exponent d is defined as:

This works because the multiplicative group of the Galois field GF(2^n) has order 2^n−1, and where Lagrange’s theorem defines that m^{de}=m for all the values of m in GF(2^n).

The coding is here [link]:

import libnum
import random
import sys

from Crypto.Util.number import getPrime
from Crypto.Random import get_random_bytes

def chunkstring(string, length):
    return (string[0+i:length+i] for i in range(0, len(string), length))
 
def generate_keys(prime):
	while True:
		e = random.randint(0, prime-2)
		if libnum.gcd(e, prime-1) == 1 and e > 2:
			break
	d = libnum.invmod(e, prime-1)

	return e,d

def crypt(chunk, key,prime ):
  num = 0
  for c in chunk:
    num *= 256
    num += ord(c)
  res = pow(num, key, prime)
  vect = []
  for i in range(0, len(chunk)):
    vect.append(chr(res%256))
    res = res // 256

  return "".join(reversed(vect))

primebits=64
msg = "HellHe"

if (len(sys.argv)>1):
  primebits=int(sys.argv[1])
if (len(sys.argv)>2):
  msg=(sys.argv[2])

FRAGMENT_SIZE = primebits//8

msg = msg + " "*((FRAGMENT_SIZE - (len(msg)%FRAGMENT_SIZE))%FRAGMENT_SIZE)

res=chunkstring(msg,FRAGMENT_SIZE)

PRIME = getPrime(primebits, randfunc=get_random_bytes)

e,d = generate_keys(PRIME)

vect=[]
for elem in res:
  enc=str(crypt(elem, e,PRIME))
  vect.append(enc)

enc="".join(vect)

dec=[]
for elem in chunkstring(enc, FRAGMENT_SIZE):
  dec.append(crypt(elem, d,PRIME))

print (f"Msg={msg}")
print (f"e={e}, d={d}")
print("Decrypted: " + "".join(dec))

A sample run is [link]:

Msg=Hello   
e=16153579288865179167, d=10300837874192230633
Decrypted: Hello

The code is here:

One of the advantages of the Massey–Omura Cryptosystem is that we can apply commutative encryption. In this way, Bob may have keys of (e_b,d_b) and Alice has keys of (e_a,d_a). We can then apply the keys in any order, such as encrypting with e_a and then encrypting with e_b, and where we can then decrypt with d_a and then decrypt with d_b, or decrypt with d_b first and then decrypt with d_a (as we would normally do).

To encrypt:

Cipher=E(a_b,E(e_a,M))=E(e_a,E(e_b,M))

To decrypt:

E(d_b,E(d_a,Cipher))=E(d_a,E(d_b,Cipher))

Here is an example:

Conclusions

The work in these classic patents is better than the majority of all the papers published today. If you are interested, here are some other classic patents:

and: