next up previous
Next: Some Things to Try

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 eA and eB 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 dA so that $e_A d_A =1 \ (mod \ (p-1))$. Similarly Bob finds dB so that $e_B d_B =1 \ (mod \ (p-1))$.
Alice's Step 1:
Compute $m_{eA}=x^{e_A} \
(mod \ p)$ and transmit meA 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 meAeB to Alice.
Alice's Step 2:
Compute $m_{eAeBdA}=(m_{eAeB})^{d_A} \
(mod \ p)$ and transmit meAeBdA 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 y2+z2=w2 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 dA and dB 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 eA dA + z (p-1) = 1.)

Then by Fermat's Little Theorem

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

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

So in the above algorithm

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)\\

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.

next up previous
Next: Some Things to Try