Decryption:

Now Alice can start the decryption process.  She finds a decryption exponent such that

Since and p-1 don't have any common prime factors, she can do this using the Euclidean Algorithm.

She keeps this private also, but for each number , she computes

We know

so

but

by Fermat's Little Theorem.  So

Alice doesn't know what is, but it doesn't matter.  She just sends the numbers back to Bob.

Likewise Bob finds a decryption exponent such that

For each number , he computes

We know

so

and Bob has decoded the message.

The Massey-Omura system, like the Diffie-Hellman system, seems to be secure as long as the DLP is hard.

Conclusion

Appendix 1

Appendix 2