James Massey and Jim K. Omura created the Massey–Omura Cryptosystem in 1982 [1]. 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 \(E(e,M)=m^e\) and \(D(d,m)=m^d\). This are operated on with the Galois field. The Massey–Omura Cryptosystem is defined as a private key system, as releasing any of the keys, will allow the other key to be discovered. For this, the encryption keys of \(e\) and \(d\) must be kept secret, and only known by Bob and Alice, whereas the prime number used can be public.
Theory
James Massey and Jim K. Omura created the Massey–Omura Cryptosystem in 1982 [1]. 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 where \(p\) is a prime number:
\(C=E(e,M)=M^e \pmod {p}\)
and the decryption is:
\(D(d,M)=C^d \pmod {p}\)
This are operated on with the Galois field. For this we define \(e\) within:
\(0 \le e \le 2^n-1\)
and:
\(gcd(e,2^n-1)=1\)
The decryption exponent \(d\) is defined as:
\(de \equiv 1 \pmod {2^n-1}\)
which can also be defined as:
\(d = e^{-1} \pmod {2^n-1}\)
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)\).
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\), we can then decrypt with \(d_a\) and then \(d_b\), or decrypt with \(d_b\) and then \(d_a\).
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 decrypted with \(d_a\) and then \(d_b\), or \(d_b\) use first and then \(d_a\). 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))\)
Coding
The coding is here:
import libnum import random import sys import hexdump 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 = "Hello" 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"PRIME={PRIME}") print (f"e={e}, d={d}") print("Decrypted (Alice): " + hexdump.dump(enc.encode())) print("\nDecrypted: " + "".join(dec))
A sample run is:
Msg=Hello PRIME=10400633083477437259 e=8991731582362109977, d=786118510880209195 Encrpyted: 52 2F C3 BD C3 A2 C3 B8 6F 7B 49 Decrypted: Hello
References
[1] Method and apparatus for maintaining the privacy of digital messages conveyed by public transmission, James L. Massey and Jimmy K. Omura, Patent: US4567600A [link].