Public Key Encryption -- Part 3

Public Key Encryption -- Part 3: Cyclic Add

Table of Content

Counting in a cycle
Reverse by going forward
A Pair of Keys
Symmetric and Asymmetric
How good is cyclic add encryption?

We have seen how addition be used in encoding. To prevent the result from getting bigger and bigger, we can use cyclic addition. We choose a cycle length, and call this n. Every time a result goes beyond n, we simply divide the result by n, keeping only the remainder. The remainder of division by n is always a number less than n. This, as you'll see, is important for improving our previous encoding schemes.

The technical term for cyclic math is modular arithmetic, and the cycle length n is called the modulo. We write:

 x mod n

to mean the remainder of number x divided by n.

The best way to represent a cyclic world is a circle, but we can use a linear diagram:

    0      1      2      3      4      5      ...                         n
    +------+------+------+------+------+------+------+------+------+------+

As long as we treat the right-end (n) the same as the left-end (0), this is effectively a circle, or cycle: a world without ends.

An example of cyclic math being used in daily life is the counting of weekdays.

We can modify our encoding by addition as follows:

Pick a modulo n. Choose an constant key k.
To each chop-up number x, we perform the cyclic addition: y = (x+k) mod n.
We send the resulting numbers y as our encoded message.

To decode the message, our partner needs to know the modulo n and the constant key k:

To each recieving number y, partner performs the cyclic subtraction: x = (y-k) mod n.
This recovers each of the chop-up numbers x.
Putting the chop-up numbers into a binary stream reveals the original message.

Cyclic subtraction is the reverse of cyclic addition. Here is an example using weekdays.

To apply cyclic addition to our encoding, we need to determine the chop size. Since chopping the data stream by chunks of b-bits means you get numbers ranging from 0 to 2^b-1, we can take them as numbers in modulo n=2^b. Or, if we have chosen the modulo n, we just take b such that 2^b < n. In math terms, b is the integer less than log₂n.

Encoding by cyclic addition is sometimes called Casear cipher. Let's see how this cyclic add can do encoding:

You can verify the first step (from symbols to binary) by this ASCII converter.
You can verify the last step (from binary to symbols) by this ASCII decoder.

You can verify the calculations by this Modulo Addition Calculator.

Back to table of content

Reverse by going forward

If you think of addition as taking steps forward, then subtraction is taking step backwards. Within ordinary math, going backwards is the only way to undo going forward. In the world of cyclic math, however, there is an alternative method:

    0      1      2      3             e                                  n
    +------+------+------+------+------+------+------+------+------+------+
    
    +---------------------------------->
              e steps                                d steps
                                       +---------------------------------->

For a cyclic world of modulo n, the right end (n) is the same as the left end (0). After you have taken e steps forward, you can take a further d steps forward to reach the right end (n), which is the same as returning to the starting point (0). For the two sets of steps to undo each other, it is easy to see that:

                  e + d = n

         or       d = n - e

This is related to the fact that cyclic math deals with remainders: there are no negative numbers (remember the range?).

Therefore, in cyclic arithmetic, you can cancel addition by another addition. This allows us to view encryption and decryption in a different light.

Back to table of content

A Pair of Keys

In cyclic arithmetic of modulo n, let us do encryption by the key e, that is, (add e, mod n).
Then, we can do decryption by another key d, that is, (add d, mod n).

What we need to have is that (add e, mod n) and (add d, mod n) cancel each other.
We can achieve this by taking d = n-e, for cyclic addition.

We call (e,n) the encryption key.
We call (d,n) the decryption key.
Both encryption and decryption use the same method: addition modulo n.

Note that we can swap the keys: they are just inverses with respect to the underlying method (cyclic addition) which is identical in both encryption and decryption.

Let's see how this coding scheme works. Here you can choose a modulo n. When you click the "Generate" button, a pair of keys will be generated: one is e, the other is d = n-e. The chop-size b-bits is determined by the modulo chosen. Then press the button "Casear Again" and scroll up to view how the message is encoded/decoded by this pair of keys.

Back to table of content

Symmetric and Asymmetric

Let's take a look at these two ways to encode using cyclic addition:

Given a modulo n and a key k, you can:
- encode by (add k mod n),
- decode by (subtract k mod n).
This is called symmetric encryption: one key, and applying opposite methods.
Given a modulo n, a pair of keys (e,n) and (d,n) can be generated. One can:
- encode by (add d mod n),
- decode by (add e mod n).
Both encoding and decoding apply the same method: add key mod n.
This is called asymmetric encryption: a pair of keys, but applying the same method.

This cyclic addition encoding is the only scheme where we can look at it in two ways, either as symmetric or asymmetric encoding. As we improve our schemes within the cyclic world, you'll find asymmetric encoding becoming more and more important.

Back to table of content

How good is cyclic add encryption?

We need to improve this scheme using cyclic addition, because of the following weakness.

If someone knows the encode key (e,n), the decode key (d.n) can be easily deduced. In this case of cyclic addition, d = n-e. As a result, he/she can read any encoded message sent according to this method. Because of this weakness, we must keep both keys secret.

Is there a way to make the deduction of the decode key difficult even if the encode key is exposed? If this is possible, we can just keep one key secret.

We shall investigate this possibility in the next part: cyclic multiply encoding.

Back to table of content

Back to home.