A Message Transfer Method Using Powers mod a Prime

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 $e_A d_A =1 \ (mod \ (p-1))$. Similarly Bob finds d_B so that $e_B d_B =1 \ (mod \ (p-1))$.

Alice's Step 1:

Compute $m_{eA}=x^{e_A} \ (mod \ p)$ 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 $m_{eAeB}=(m_{eA})^{e_B} \ (mod \ p)$ and transmit m_eAeB to Alice.

Alice's Step 2:

Compute $m_{eAeBdA}=(m_{eAeB})^{d_A} \ (mod \ p)$ and transmit m_eAeBdA to Bob.

Bob's Step 2:

Compute $m_{eAeBdAdB}=(m_{eAeBdA})^{d_B} \ (mod \ p)$. 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 $x \neq 0 \ (mod \ p)$ then $x^{p-1}=1 \ (mod \ p)$.

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²+z²=w² 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 $e_A d_A =1 \ (mod \ (p-1))$ 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

$$\begin{eqnarray*} x^{e_A d_A} & = & x^{1+k(p-1)} \ (mod \ p)\\ \ & = & x^{1}\cd... ... p)\\ \ & = & x \cdot 1 \ (mod \ p)\\ \ & = & x \ (mod \ p)\\ \end{eqnarray*}$$

and similarly $x^{e_B d_B}=x \ (mod \ p)$.

So in the above algorithm

$$\begin{eqnarray*} x^{e_A e_B d_A d_B} & = & (x^{e_A d_A})^{e_B d_B} \ (mod \ p)\\ \ & = & x^{e_B d_B} \ (mod \ p)\\ \ & = & x \ (mod \ p)\\ \end{eqnarray*}$$

Bob will have the original message x that Alice sent while eavesdroppers will only have heard x to various powers without knowing what those powers were.