Cryptography Reference
In-Depth Information
1.4 Modular Arithmetic and More Historical Ciphers
In this section we use two historical ciphers to introduce modular arithmetic with
integers. Even though the historical ciphers are no longer relevant, modular arith-
metic is extremely important in modern cryptography, especially for asymmetric
algorithms. Ancient ciphers date back to Egypt, where substitution ciphers were
used. A very popular special case of the substitution cipher is the
Caesar cipher
,
which is said to have been used by Julius Caesar to communicate with his army.
The Caesar cipher simply shifts the letters in the alphabet by a constant number of
steps. When the end of the alphabet is reached, the letters repeat in a cyclic way,
similar to numbers in modular arithmetic.
To make computations with letters more practicable, we can assign each letter of
the alphabet a number. By doing so, an encryption with the Caesar cipher simply
becomes a (modular) addition with a fixed value. Instead of just adding constants,
a multiplication with a constant can be applied as well. This leads us to the
affine
cipher
.
Both the Caesar cipher and the affine cipher will now be discussed in more detail.
1.4.1 Modular Arithmetic
Almost all crypto algorithms, both symmetric ciphers and asymmetric ciphers, are
based on arithmetic within a finite number of elements. Most number sets we are
used to, such as the set of natural numbers or the set of real numbers, are infinite. In
the following we introduce modular arithmetic, which is a simple way of performing
arithmetic in a finite set of integers.
Let's look at an example of a finite set of integers from everyday life:
Example 1.4.
Consider the hours on a clock. If you keep adding one hour, you ob-
tain:
1
h
,
2
h
,
3
h
,...,
11
h
,
12
h
,
1
h
,
2
h
,
3
h
,...,
11
h
,
12
h
,
1
h
,
2
h
,
3
h
,...
Even though we keep adding one hour, we never leave the set.
Let's look at a general way of dealing with arithmetic in such finite sets.
Example 1.5.
We consider the set of the nine numbers:
{
0
,
1
,
2
,
3
,
4
,
5
,
6
,
7
,
8
}
We can do regular arithmetic as long as the results are smaller than 9. For instance:
2
3 = 6
4 + 4 = 8
×
