Public Key Encryption -- Part 2

Public Key Encryption -- Part 2: Sending Numbers

Table of Content

Chop to other sizes
Add a constant
Multiply by a factor
Raise to a power
How good is the secret?

Chop to other sizes

We have seen standard ASCII encoding: Each symbol converts to an 8-bit binary.
We have seen standard ASCII decoding: Split into 8-bit binaries and lookup each symbol.

This is 8-bit chopping. However, the data stream is just a long string of 0's and 1's. You can chop the data stream in various sizes, so that you can think of the data stream as a stream of numbers in various sizes.

If you chop the data stream by chunks of b-bits, you get numbers ranging from 0 to 2^b-1, or 2^b - 1.

Let's see how this chopping of message works.

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

Note the padding character '~'. This is used to extend the message so that it can be evenly chopped by b-bits, where b is the value chosen above.

Of course, your partner needs to know how many bits you are chopping, and do the following to recover the message:

Convert the numbers to b-bits binary
Pack the binaries into a long stream
Chop the stream by 8-bits binary and use ASCII to decode

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

Reading the example above, you can see that we are sending decimal numbers from one computer and the other computer is receiving decimal numbers.

From now on, we assume that computers can talk using numbers, decimal or binary. If you are wondering technically how the numbers can be sent again as a binary stream, here is an explanation.

Back to table of content

Add a constant

To keep a secret, you need to do some tricks with these chop-up numbers, and send the results instead. As long as your partner can undo the trick you apply, your partner can recover the message through the results.

For example, you can add 17 to each number. To recover the message, your partner will do the reverse, subtract 17 from each number. As long as outsiders cannot figure out your tricks, you and your partner can exchange messages secretly.

The number 17 is called the key. We shall denote the key by k. We have the methods:

to encode, add key to each number, or (add k)
to decode, subtract key from each number, or (subtract k)

Since both methods of encryption and decryption use the same key, this kind of scheme is called symmetric encryption. Obviously, the key must be kept secret to enable the secrecy of the message.

Click here for a demonstration.

Try to set your own key and click the "Encode/Decode" again.
If you need a calculator to check the computations, here is one.

Back to table of content

Multiply by a factor

We can multiply each number by the key k, and send out the resulting products as encoding. To decode, we undo the multiplication by division: we divide each received number by the key k. This would give us a scheme for encryption by multiplication with key k:

to encode, perform to each number (multiply k)
to decode, perform to each number (divide by k)

Click here for a demonstration. Try to keep the chop size greater than 8, otherwise there are zeroes. The encode of zero is still zero with this coding. To check the computations, use this calculator.

Back to table of content

Raise to a power

Instead of multiplying by the key k, we can multiply the number by itself, k times. This is raising each number to its k-th power. To decode, we need to undo this power raising: we take the k-th root of each receiving number.

These are the methods for encryption by raising power with key k:

to encode, perform to each number (raise to k-th power)
to decode, perform to each number (take the k-th root)

Click here for a demonstration. Keep the power less than 8. This is to keep the calculations within precision.

Back to table of content

How good is the secret?

How secure are these coding schemes?

The art or science of breaking codes is called cryptanalysis. The technique depends heavily on statistical analysis. By collecting as much as possible the information about the numbers composing a secret message, a cryptanalyst can try a variety of tools to decode the message.

For the schemes above, it is straight-forward to break the codes by examining the range of the encoded numbers: the smallest and the largest of the encoded numbers. If the message is long enough message, the range can reveal the following:

for addition encoding, the range is simply shifted, by the constant. The width of the range is a power of 2.
for multiplication encoding, the range is expanded. The expanded range is the factor times a power of 2.
for raising to power encoding, the range is greated expanded -- in fact, exploded. The maximum will be some power of a power of 2.

Indeed, for multiplication encoding, there is a simple way to extract the factor, if you know some math. The multiplying factor is the greatest common factor among the numbers. For the math people, computation of the greatest common factor (gcd) is a fast operation, because they don't need to even factorize either of the numbers.

Note that adding a constant does not change the result by much. But multiplying a constant affects the result: factor growth is acceptable. However, raising to a power greatly affects the result: power growth is powerful!

Whichever way, the resulting numbers expands the range of numbers being used. This range expansion creates inconveniences, and provides a clue to those trying to break your coding, as we have seen.

Is it possible to keep secrets by having numbers all within a convenient range? This is for part 3.

Back to table of content

Back to home.