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):
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
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
So in the above algorithm