In the same way we can add in the cyclic world, we can also multiply in the cyclic world. Given two numbers a and b, and the cycle length, or modulo n, we can first multiply the numbers a and b, like ordinary multiplication, then divide the result by n, keeping only the remainder. The procedure, called cyclic multiplication, is denoted by:
a * b mod n
If we use cyclic multiplication to encode, we must do something in order to decode. In ordinary math, we undo multiplication by division. In cyclic math, suprisingly, there is no division.
To undo multiplication in the cyclic world, we do another multiplication -- this is similar to undo addition by another addition in the cyclic world. How this can be done will be discussed in next section, when we look deeper into cyclic multiplication. Here, we just need to know that, given a modulo n, it is possible to generate two factors e and d, such that:
There is no special name for encoding by cyclic multiplication. Let's just invent a name: Fermat cipher. Here, you can pick a modulo, then press the "Generate" button. A pair of keys will be computed in the Encode and Decode boxes, along with the Chop size. Type in a message and press the "Fermat" button to see cyclic multiply encoding in action.
You can verify the calculations by this Modulo Multiply Calculator.
You can verify the gcd calculations by this GCD Calculator.
Back to table of content
Using cyclic multiply encoding, when a number x is encoded, the coded number is: y = x * e mod n.
To decode the number y, we compute: y * d mod n = (x * e) * d mod n = x * (e * d) mod n.
This means that, for the two multiplications to undo each other, we require: e * d = 1 mod n.
You can use this Cyclic Multiply Calculator to verify that the pair of keys generated above really undo each other in cyclic multiplication, that is:
e * d = 1 mod n
Using number theory, given a modulo n, it is possible to generate the pair of keys e and n, based on the above relationship.
Back to table of content
If the cyclic length, modulo, is a prime number p, then every non-zero number less than p is relatively prime to p -- by the very fact that p is a prime. In this case, you can choose any number less than p as your encode key e. Applying the previous key-pair generation method, you can compute the decode key d.
In this case, Fermat found a formula to compute the decode key d directly from encode key e and the prime modulo p.
Here, you can choose a prime p, and pick any number less than p as your encode key. Press the "Generate" button will compute a decode key using the previous key-generation method, and a Fermat key using Fermat's formula. They should be the same. The chop size is determined by the modulo prime p. Press the "Fermat Again" button and scroll up to see how your message is encoded/decode based on these keys via cyclic multiplication.
Back to table of content
If you use a pair of keys to encode/decode messages sending between you and your partner, who should keep the encode key (e,n), and who should keep the decode key (d,n) ?
The arrangement is generally as follows:
Back to table of content
Cyclic multiply encryption uses a pair of keys e and d derived from the modulo n. If someone can get hold of the encode key (e,n), he/she still needs the decode key (d,n) to read any message. If the decode key is difficult to find, this scheme will be very secure indeed.
To most ordinary people, given the encode key (e,n), it is indeed difficult to compute the decode key (d,n). The simplest way is to try every number d less than n and check the one that satisfies:
e * d = 1 mod nThis can be a time-consuming process if the modulo n is large enough.
However, to a math person, especially one with a good knowledge of number theory, the decode key can be computed by the extended Euclidean algorithm. In the case of a prime modulo p, there is even a direct formula for the decode key due to Fermat. There is no way to hide secrets using this scheme if the person who wants to know the secret is a number-theorist!
Can we find a pair of keys such that, given the encode key, the decode key is so hard to find that even mathematicians will surrender? This is part 5: cyclic power encoding.
Back to table of content