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 . Similarly Bob finds dB so that .
Alice's Step 1:
Compute 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 and transmit meAeB to Alice.
Alice's Step 2:
Compute and transmit meAeBdA 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 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 is the same as finding a solution of the diophantine equation eA dA + z (p-1) = 1.)

Then by Fermat's Little Theorem

and similarly .

So in the above algorithm

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: Some Things to Try
root
2002-08-23