Modular Arithmetic and Cryptology

In simple terms, cryptology is the encoding and decoding of data to enable secure (secret) transmission/communication of the data between individuals.

Caesar Cypher

Encoding
The Caesar Cypher encrypts letters of the alphabet by shifting each letter by three positions in the alphabet. So, for example, A becomes D, B becomes E, ... and Z becomes C where letters at the end of the alphabet wrap around to the beginning of the alphabet. One must keep in mind that computers only manipulate numbers so what is encrypted, transmitted and decrypted are numbers that represent characters such as letters or digits.
Decoding
Decoding simply shifts the letter back three positions in the alphabet.

The Caesar Cypher is a special case of applying simple modular arithmetic equations to encrypt characters as described below.

Linear Equations in Modular Arithmetic

The Caesar cipher mentioned above for the English alphabet can be defined using the function:
y = x + 3 (mod 26)

Using only uppercase letters is, of course, quite restrictive as the transmission of digits, spaces, commas, lowercase letters etc. is generally desirable.

If the entire extended ASCII character set is to be employed then one may use mod 256 rather than mod 26.

y = x + 3 (mod 256)

Generalized Caesar Cipher

Encoding
Of course you have probably realized that one could substitute any constant k for the 3 in the equation above yielding
y = x + k (mod 256)

Decoding
In order to decipher a message enciphered by the equation above one need only solve this equation for x. This may be done as expected.
x = y - k (mod 256)

Breaking the Code
All of the above encryption methods are generally easy to "crack" because there are only 255 possible encryptions. I.e. k = 1, 2, ..., 255

Symbol Substitution

A more sophicticated technique is to use a translation table to define a one to one mapping f:A to A where A is the ASCII character set.
So, for example, we may map A to F, B to Q, ..., Z to L sequencing through the alphabet and selecting the "mapped to" letter at random from the remaining letters. A disadvantage of this scheme is that the sender and receiver must exchange more information. In the Generalized Caesar Cipher the communicators need only agree on the shift number, k. In the symbol substitution method they must agree on an entire translation table. Although this method is more difficult to crack it is subject to several methods of attack including frequency analysis. For example, the letter e is generally the most frequently used letter in a document. Thus, the most frequently used letter in the encrypted text is likely to decrypt to an e. Likewise, when using the entire ASCII character set it may be easy to recognize the encryption of the "space" character.

Permutations

A method similar to the substitution method is a permutation method in which we define a permutation on blocks of text.
For example, consider the message, M = "The time is now.".

Encoding
The length of M is 16.
Let us define a block size to be 8 so that M consists of two blocks, B1 and B2.
B1 = "The time" and B2 = " is now."
The key for this method is a permutation of the digits 1 - 8.
Let's let the key = (7, 5, 1, 3, 8, 6, 4, 2)
This means that the first character in the block is moved to the 7th position and the 2nd character in the block is moved to the 5th position etc.
Thus, encrypting B1 we would obtain "ee mhiTt" and encrypting B2 we obtain "s. wio n".
Putting the blocks together we obtain the complete encrypted message, "ee mhiTts. wio n".

Decoding
To decode the message we simply apply the reverse permutation so that for each block the 7th position moves to the first, the 5th moves to the second etc. thus restoring the original string.

Breaking the Code
This particular code is not difficult to break for two reasons.
First, we are permuting entire characters so the characters we see in the encrypted message are the same as those of the plaintext.
Second, our block size is only 8 and so there are only 8 factorial = 40320 different permutations. A computer can check all of the permutations in much less than a second so the algorithm's security is limited. The algorithm may be made more secure by
1. increasing the block size and
2. permuting something other than byte-sized data items. For example, we might permute bits instead of bytes.

Unfortunately, all simple permutation algorithms are subject to an attack that looks at possible permutations based upon plaintext/cyphertext pairs.
Here is how.
Suppose that we know the cyphertext, "ee mhiTts. wio n", for the plaintext message "The time is now". And, further, suppose that we know the block size is 8. (We could actually figure out the block size by observing that none of the unique characters w, o, T, t, s, m, n and h in the cyphertext are moved more than 7 positions away from their original locations in the plaintext.).
We now know that "The time " encrypts to "ee mhiTt". Thus we know that the 'T', originally in the 1st position has moved to the 7th position and the h, originally in the 2nd position has moved to the 5th position, etc. Continuing in this manner with this block and, if required, other blocks we can deduce the entire permutation.

More Generalized Linear Equations in Modular Arithmetic

As mentioned above, equations used for encryption such as y = x + k (mod 256) simply shift the character set k characters and, therefore, are quite easy to "crack".

Encoding
A more sophisticated approach is to use a more general linear equation such as the following to encode data.

y = ax + b (mod m)

Decoding
As long as the coefficient, a, and the modulus, m, are relatively prime, the equation may be solved for x yielding the decryption equation, x = a^-1*(y - b) (mod m)
where a^-1 is the multiplicative inverse of a in mod m.

Applying Linear Equations to nibbles

Rather than mapping entire 8 bit characters to other 8 bit characters using an equation like
y = ax + b (mod 256) one may map nibbles to nibbles (4 bits) and reduce the mod to 16.

As an illustration the word H E L L O in hexadecimal is 48 45 4C 4C 4F.
Since 3 is relatively prime to 16 we may use the equation y = 3x + 1 to encrypt nibbles.

3*4 + 1 = 13 (mod 16) so 4 maps to D
3*8 + 1 = 9 (mod 16) so 8 maps to 9
3*5 + 1 = 0 (mod 16) so 45 maps to 0
3*12 + 1 = 5 (mod 16) so C maps to 5
3*15 + 1 = 14 (mod 16) so F maps to E

Therefore H E L L O = 48 45 4C 4C 4F encrypts to D9 D0 D5 D5 DE

Unfotunately, this equates to a simple translation which we know is not very secure.

Applying Linear Equations to odd length bit patterns,

If we view H E L L O in binary rather than hex we obtain the following:
01001000 01000101 01001100 01001100 01001111
Rather than divide this sequence of bits into blocks of 4 or 8 bits, we may divide it into blocks of 3 bits obtaining
010 010 000 100 010 101 001 100 010 011 000 100 111 1
Where the number of bits is not evenly divisible by three we may pad the end of the message with zeros or random bits.
Translating the bit patterns below into decimal numbers we obtain
010 010 000 100 010 101 001 100 010 011 000 100 111 100
2 2 0 4 2 5 1 4 2 3 0 4 7 4

Now we may apply a linear equation such as y = 3x + 1 to encrypt these numbers. The advantage to this method is that we are no longer treating individual characters as encryption units and attacks that look for simple character patterns or frequencies will not work so easily. However, since the decryption is now much more difficult we probably cannot expect a human with pencil and paper to decode the message easily. The individual decoding will more likely wish to rely on some electronic device to decode the message in a timely fashion.
Oftentimes what seems to be a good code is very easy to crack. The above code is easy to crack because we are only using 3-bit patterns and these correspond to only 8 numbers (0 - 7). A similar encoding scheme that used, say, 13 bits would likely be more difficult to crack.

The XOR Method

An interesting method of encoding and decoding involves the use of the XOR function.
The XOR function takes two bits as inputs and returns a single bit as output.
The XOR function returns 1 if its two inputs are unequal. Otherwise it returns 0.

Let's look at an example using the message "HI".

Encoding
The ASCII code for H is 72 = 01001000 and the ASCII code for I is 73 = 01001001.
We select a key which is simply a byte if we are encoding 8 bits at a time.
Let the key = 01101101
The XOR function has the property that the 0's leave their corresponding bits unchanged and the 1's reverse theirs.
So, H XOR key = 01001000 XOR 01101101 = 00100101
and I XOR key = 01001001 XOR 01101101 = 00100100
So "HI" encrypted using the above key and the XOR operation is 00100101 00100100.

Decoding
The beauty of using the XOR operation for encoding is that the exact same operation is used to decode.
So, 00100101 XOR 01101101 = 01001000 = H and 00100100 XOR 01101101 = 01001001 = I.

Breaking the Code
The simplicity of the XOR operation for encoding and decoding is also a disadvantage since it is easy to "crack".
Suppose that we know the plaintext (for example, H = 01001000) and its corresponding cyphertext, 00100101. Then we can easily deduce the key that was used to encode H since we know that everywhere a bit remains the same from the plaintext to the cyphertext the key contained a 0 and everywhere a bit was changed the key contained a 1.
Because of this XOR alone is practically worthless as a cypher method. Amazingly, it works quite well in combination with other methods such as permutations/substitutions. Most of the best cryptographic methods use XOR as an important part of their algorithms.