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. In this case, we will generate keys for Bob (\(e_b,d_b\)) and for Alice (\(e_a,d_a\)). We will encrypt a message with \(e_b\) and then encrypt with \(e_a\). Normally we would decrypt with \(d_a\) and then with \(d_b\). In this case, we will decrypt out-of-order by decrypting with \(d_b\) and then by \(d_a\). 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.
Massey-Omura Cryptosystem Commutative |
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\).
\(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))\)
Three-pass key exchange
A basic scenario for this is in key exchange, and where Bob generates a symmetric key of \(K\). Bob now generates a prime number \(p\) and then generates a locker (\(e_b\)) and an unlocker (\(d_b\)). Bob encrypts with \(e_b\) and sends this and \(p\) to Alice. She then creates her own locker (\(e_a\)) and an unlocker (\(d_a\)). Alice then encrypts the cipher she received with \(e_a\) and sends it back to Bob. Bob then decrypts with his unlocker (\(d_b\)) and send this back to Alice. She then recovers \(K\) with her unlocker (\(d_a\)). Bob and Alice now have the same shared key (\(K\)).
Coding
In this case, we will generate keys for Bob (\(e_b,d_b\)) and for Alice (\(e_a,d_a\)). We will encrypt a message with \(e_a\) and then encrypt with \(e_b\). Normally we would decrypt with \(d_b\) and then with \(d_a\). In this case, we will decrypt out-of-order by decrypting with \(d_a\) and then by \(d_b\):
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(p,q): phi=(p-1)*(q-1) n=p*q while True: e = random.randint(0, n) if libnum.gcd(e, phi) == 1 and e > 2: break d = libnum.invmod(e, phi) return e,d,n 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//4 msg = msg + " "*((FRAGMENT_SIZE - (len(msg)%FRAGMENT_SIZE))%FRAGMENT_SIZE) res=chunkstring(msg,FRAGMENT_SIZE) p = getPrime(primebits, randfunc=get_random_bytes) q = getPrime(primebits, randfunc=get_random_bytes) e,d,n = generate_keys(p,q) vect=[] for elem in res: enc=str(crypt(elem, e,n)) vect.append(enc) enc="".join(vect) dec=[] for elem in chunkstring(enc, FRAGMENT_SIZE): dec.append(crypt(elem, d,n)) print (f"Msg={msg}") print (f"\np={p}, q={q}, n={n}") print (f"\ne={e}, d={d}") print("\nEncrpyted: " + hexdump.dump(enc.encode())) print("\nDecrypted: " + "".join(dec))
A sample run is:
Msg=Hello p=11092498745897444501, q=10463158242362952173, n=116062569681537556641198979558784850673 e=98999288377634519050323892620708130091, d=29814043792379792585051244499156117011 Encrpyted: 1A C2 92 71 18 C2 AE C3 8D 11 C3 A1 37 43 5D C2 91 C3 85 36 C2 BA 70 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].