Author : Brian Raiter
Page : << Previous 3 Next >>
then T^(S * phi(R)) = 1 (mod R), where S can be any number.
That's our first variation. Now, let's tweak this further by multiplying both sides by T:
T^(S * phi(R)) * T = 1 * T (mod R).
Simplifying leaves us with:
T^(S * phi(R) + 1) = T (mod R).
If we repeat this, we will get:
T^(S * phi(R) + 1) * T = T * T (mod R),
or:
T^(S * phi(R) + 2) = T^2 (mod R).
Doing this yet again will give us:
T^(S * phi(R) + 3) = T^3 (mod R),
and so on.
What makes this so interesting is that S can be any number. It means that, when calculating the value of:
T^E (mod R),
if E happens to be greater than phi(R), we can subtract phi(R) from E, and keep on subtracting it until we have a number less than phi(R), and the new formula will still produce the same value.
Guess what? This is just another way of describing modulus arithmetic. So, what this boils down to is the rather surprising rule:
T^E = T^F (mod R) whenever E = F (mod phi(R)).
(again, as long as T < R, and T and R are relatively prime). In other words, when doing modulus arithmetic, exponentiation works differently than addition and multiplication. You can reduce an exponent, but you need to use phi(R), and not R itself.
The Plot Thickens
We just blew past something very important. Let's back up and look at this equation more closely:
T^(S * phi(R) + 1) = T (mod R).
Notice what we have here. We take a number, T, and raise it to a power, and when we do the calculation in modulus arithmetic, we wind up with T again. In short, we have a recipe for a function that returns its own input (presuming that R has been chosen ahead of time, and T is relatively prime to R).
If you're thinking to yourself, "What's so interesting about that?", then consider what we would have if we broke this function up into two separate steps. Specifically, let's imagine that we can find two new numbers P and Q such that:
P * Q = S * phi(R) + 1, for some value of S that we choose.
Then we could rewrite:
T^(S * phi(R) + 1) = T (mod R)
as:
T^(P * Q) = T (mod R).
Now, this is equivalent to:
(T^P)^Q = T (mod R),
and this is something that can be broken up into two steps:
T^P = X (mod R), and then
X^Q = T (mod R).
Now, if you don't see the value in doing this, imagine now that the two steps are performed on separate computers. And that X is sent from the first computer to the second over an insecure phone line....
Does This Really Work?
T stands for the plaintext, the message that is to be sent. P, Q, and R together form the cipher's keys -- P and R make up the public key, and Q and R make up the private key. And X becomes the encrypted message.
Here, again, is the central equation that makes it all possible:
P * Q = S * phi(R) + 1.
Note here that P and Q will both automatically be relatively prime to phi(R). (Why? Because their product, P * Q, is one more than a multiple of phi(R). Any factors of P or Q must also be factors of P * Q. Any number that is a factor of S * phi(R) + 1 can't also be a factor of phi(R).) This is important, since it helps to assure us that a P and Q can actually be found.
Imagine a clockface, with just an hour hand, and imagine yourself placing the hour hand on midnight and then moving it forward by jumps, over and over, each jump covering N hours. If you pick a value for N that is divisible by 2 or 3 (the prime factors of 12), then you will find that you will only hit certain numbers before you return to midnight, and the sequence will then repeat. If N is 2, then the hour hand will visit 12, 2, 4, 6, 8, 10, 12, 2, 4, 6, 8, 10, 12 ...
If, however, your N is relatively prime with 12, then you will wind up hitting every number exactly once before finally returning to midnight 12 jumps later. For example, using 7 for your N, the itinerary would be: 12, 7, 2, 9, 4, 11, 6, 1, 8, 3, 10, 5, 12, ... In addition, the order in which you visit the numbers is entirely dependent on what value you pick for N.
In a similar vein, it is important that both P and Q be relatively prime to phi(R). Because of this, we know that every possible value for T, when raised to the power P modulo R, will land on a different number. (Remember that when doing exponents in modulus arithmetic, it is actually phi(R), and not R itself, that determines the length of the cycles.) If this weren't true -- if P, for example, shared a factor in common with phi(R) -- then some values for T could get mapped to the same value for X, and it would clearly be impossible to tell which was originally which. There could not be one value for Q that would correctly map X back to T every time.
The question of which T-values will wind up going to which X-values depends entirely on the value used for P -- and here's the rub for the would-be codebreaker: Just about every possible mapping of T-values to X-values does in fact exist. Somewhere out there is a P that will make that mapping.
If this:
T^P = X
X^Q = T
was the cipher's scheme, there'd be no cipher. With P already being public knowledge, it's tedious but no great trick to take an X and compute backwards to T. But, instead, we have this:
T^P = X (mod R)
X^Q = T (mod R)
as the cipher's scheme, and that changes everything. The modulus arithmetic erases too much information. There's no way to deduce how many times the hour hand needs to spin around the clockface when it goes from X back to T. Without knowing what Q is, a given X could wind up going to any of the possible values for T.
But what is really maddening to our would-be codebreaker is that even when T and P and X are all known, Q still can't be deduced! (Of course, it actually can -- but not necessarily within anyone's lifetime. But we're getting ahead of ourselves.)
So, let's see how to make this recipe work.
Making a Pair of Keys
To construct our own personal cipher keys, we need an appropriate value for R. So, we start by randomly picking two prime numbers, U and V, and multiplying them together:
R = U * V.
There are two good reasons for selecting a value for R that has exactly two prime factors. Not only do we have an easy formula for calculating phi(R):
phi(R) = (U - 1) * (V - 1),
but we also want R to be hard to factor. The fewer factors a number has, the longer it takes to find them.
We then need to figure out values for P, Q, and S, such that:
P * Q = S * phi(R) + 1.
When the numbers have been chosen, P and R together become the public key, and Q and R make up the private key. U, V, and S are no longer needed, and can be forgotten.
An Example
In order to see all this in action, we want to stick with numbers that we can actually work with. So, for our example, we will select the primes 5 and 7 to be our U and V. This gives R a value of 35, and:
phi(35) = (5 - 1) * (7 - 1) = 4 * 6 = 24.
Now, we need to find numbers to fit the equation:
P * Q = S * 24 + 1.
We'd prefer P and Q to not share any factors with each other, since that would make it easier to derive one from the other. (And we certainly don't want P and Q to be the same number, since that would turn our trapdoor cipher into a garden-variety symmetric cipher!) So, P and Q should be relatively prime. We will try assigning values to S and see what S *
Page : << Previous 3 Next >>