**Math Explorers Club**

**October 14, 2000**

This computer activity involves securely transferring a message *x* from
a Alice to Bob using a publically know prime number *p*. The channel
between Alice and Bob is assumed to possibly have eavesdroppers, and
the idea is to make it hard for the eavesdroppers to decode the
message. The message is assumed to have already been converted
to an integer between 1 and *p*-1.

Here's the algorithm (sometimes known as the Massey-Omura cryptosystem):

**Pick Some Primes:**- Both Alice and Bob privately
pick some large primes
*e*_{A}and*e*_{B}respectively. Each also checks that their primes have no common factor with*p*-1. (Here*p*is the publically known prime.) **Solve Some Diophantine Equations:**- Alice
privately finds a number
*d*_{A}so that . Similarly Bob finds*d*_{B}so that . **Alice's Step 1:**- Compute
and transmit
*m*_{eA}to Bob.*Here the subscript***eA**is a way of denoting which operation (**e)**and who (**A**for Alice) has applied the operation. **Bob's Step 1:**- Compute
and transmit
*m*_{eAeB}to Alice. **Alice's Step 2:**- Compute
and transmit
*m*_{eAeBdA}to Bob. **Bob's Step 2:**- Compute
.
This will actually be the original message
*x*.

A Maple worksheet *Prime Power Coding* illustrates some Maple
commands which can be used to implement the computational
parts of this. Note that Maple is rather unforgiving about syntax
errors, so you'll want to follow the suggested syntax carefully until
you become more expert with Maple.

The method is based on several results in number theory.
The first result is Fermat's Little Theorem:

**Theorem** If *p* is a prime and
then
.

A *diophantine equation* is an equation where one is only
interested in solutions which are integers. For example finding
all solutions of the diophantine equation *y*^{2}+*z*^{2}=*w*^{2} is
the pythagorean triplets problem.

The case of linear diophantine
equations *ay*+*bz*=*c* (where *y* and *z* are the integer unknowns) turns out to
have a very neat answer. Since any divisor of the integers *a* and *b*
will divide *ay*+*bz* as well, a necessary condition for solvability
is that *c* be divisible by the the greatest dommon divisor (gcd)
of *a* and *b*. The following theorem says this is sufficient as well:

**Theorem** The diophantine equation *ay*+*bz*=*c* has a solution if
and only if *gcd*(*a*,*b*) divides *c*.

In fact, by any one of several variants of the
*Euclidean division algorithm* the solutions may be found quite
efficiently, even for large (hundreds of digits) numbers. Appendix
A illustrates one by hand method which does illustrate (not prove)
why there is an efficient algorithmic solution.

Here's an explanation of why the coding method works:

First note that *d*_{A} and *d*_{B} exist because of the diophantine
equation result quoted above. (Remember
is the same as finding a solution of the diophantine equation
*e*_{A} *d*_{A} + *z* (*p*-1) = 1.)

Then by Fermat's Little Theorem

and similarly .

So in the above algorithm

Bob will have the original message