The EMO-1 (Enhanced Massey-Omura system) Cryptosystem [2] is an enhancement to the Massey–Omura Cryptosystem and which was originally created 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\). 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. The enhancement of EMO-1 is that we create two prime numbers (\(p\) and \(q\)), rather than using a single prime number. This approach overcomes the core weakness of the Massey–Omura Cryptosystem, and where the discovery of \(e\) will allow the decryption key (\(d\)) to be easily discovered. In EMO-1, we define \(\phi=(p-1) \times (q-1)\), and we generate the keys in the same way as RSA.
EMO-1 (Enhanced Massey-Omura) Private Key System |
Theory
James Massey and Jim K. Omura created the Massey–Omura Cryptosystem in 1982 [1]. It uses exponentiation in the Galois field GF(\(n\)) for both the encryption and decryption functions. In this, if we have a message of \(M\), the encryption is:
\(C=E(e,M)=M^e \pmod n\)
and the decryption is:
\(D(d,M)=C^d \pmod n\)
This are operated on with the Galois field. As with RSA, we generate two prime numbers (\(p\) and \(q\)) and then compute a modulus (\(n\)):
\(n=p \times q\)
and:
\(\phi=(p-1) \times (q-1)\)
For this we define \(e\) within:
\(0 \le e \le n-1\)
and:
\(gcd(e,\phi)=1\)
The decryption exponent \(d\) is defined as:
\(de \equiv 1 \pmod {\phi}\)
which can also be defined as:
\(d = e^{-1} \pmod {\phi}\)
This is defined as the inverse of \(e\) mod \(\phi\). 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(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)) def chunkit(msg): msg = msg + " "*((FRAGMENT_SIZE - (len(msg)%FRAGMENT_SIZE))%FRAGMENT_SIZE) return (msg) 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=chunkit(msg) PRIME = getPrime(primebits, randfunc=get_random_bytes) e_a,d_a = generate_keys(PRIME) e_b,d_b = generate_keys(PRIME) print (f"Msg={msg}") print (f"PRIME={PRIME}") print (f"Bob: e={e_a}, d={d_a}") print (f"Alice: e={e_b}, d={d_b}") vect=[] for elem in chunkstring(msg,FRAGMENT_SIZE): enc=str(crypt(elem, e_a,PRIME)) vect.append(enc) enc="".join(vect) print("\nEncrypted (Alice): " + hexdump.dump(enc.encode())) vect=[] for elem in chunkstring(enc,FRAGMENT_SIZE): enc=str(crypt(elem, e_b,PRIME)) vect.append(enc) enc="".join(vect) print("Encrypted (Bob): " + hexdump.dump(enc.encode())) dec=[] for elem in chunkstring(enc, FRAGMENT_SIZE): dec.append(crypt(elem, d_a,PRIME)) enc="".join(dec) print("Decrypted (Alice): " + hexdump.dump(enc.encode())) dec=[] for elem in chunkstring(enc, FRAGMENT_SIZE): dec.append(crypt(elem, d_b,PRIME)) print("\nDecrypted: " + "".join(dec))
A sample run is:
Msg=Hello p=181500582922904300872610915937661833203, q=231472347045307200243179130188611524767, n=42012365919256061834119160354323674165039834812123973915841513271238257438701 e=40610362546959801263293802369681247999078144655897658264221358207730027268843, d=25321257325022610012703314703251540842240784665180841961930423145836963589451 Encrpyted: 4D C3 92 C2 BC 6E 30 C2 A1 C2 B2 C2 AA 0A 4F 73 C3 9D C3 90 C2 8A C3 99 C2 BF 7A C2 84 7E C2 AB C2 B1 54 75 43 4D C3 B3 C2 8A 4C 05 C3 9E 68 C2 9B 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].
[2] Winton, R. (2007). Enhancing the Massey-Omura Cryptosystem. Journal of Mathematical Sciences and Mathematics Education, 2(1), 21-29 [link].