Decryption:

Now Alice can start the decryption process.  She finds a decryption exponent [Graphics:Images/index_gr_1.gif]such that

[Graphics:Images/index_gr_2.gif]

Since [Graphics:Images/index_gr_3.gif] and p-1 don't have any common prime factors, she can do this using the Euclidean Algorithm.

[Graphics:Images/index_gr_4.gif]
[Graphics:Images/index_gr_5.gif]
[Graphics:Images/index_gr_6.gif]

She keeps this private also, but for each number [Graphics:Images/index_gr_7.gif], she computes

[Graphics:Images/index_gr_8.gif]

We know

[Graphics:Images/index_gr_9.gif]

so

[Graphics:Images/index_gr_10.gif]

but

[Graphics:Images/index_gr_11.gif]

by Fermat's Little Theorem.  So

[Graphics:Images/index_gr_12.gif]

Alice doesn't know what [Graphics:Images/index_gr_13.gif] is, but it doesn't matter.  She just sends the numbers [Graphics:Images/index_gr_14.gif] back to Bob.

[Graphics:Images/index_gr_15.gif]
[Graphics:Images/index_gr_16.gif]
[Graphics:Images/index_gr_17.gif]
[Graphics:Images/index_gr_18.gif]
[Graphics:Images/index_gr_19.gif]
[Graphics:Images/index_gr_20.gif]
[Graphics:Images/index_gr_21.gif]

Likewise Bob finds a decryption exponent [Graphics:Images/index_gr_22.gif] such that

[Graphics:Images/index_gr_23.gif]
[Graphics:Images/index_gr_24.gif]
[Graphics:Images/index_gr_25.gif]
[Graphics:Images/index_gr_26.gif]

For each number [Graphics:Images/index_gr_27.gif], he computes

[Graphics:Images/index_gr_28.gif]

We know

[Graphics:Images/index_gr_29.gif]

so

[Graphics:Images/index_gr_30.gif]

and Bob has decoded the message.

[Graphics:Images/index_gr_31.gif]
[Graphics:Images/index_gr_32.gif]
[Graphics:Images/index_gr_33.gif]
[Graphics:Images/index_gr_34.gif]
[Graphics:Images/index_gr_35.gif]
[Graphics:Images/index_gr_36.gif]
[Graphics:Images/index_gr_37.gif]
[Graphics:Images/index_gr_38.gif]
[Graphics:Images/index_gr_39.gif]
[Graphics:Images/index_gr_40.gif]

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


Converted by Mathematica      March 17, 2001