Introduction
Modulo arithmetic can be used to make a stronger encryption system than the simple shift Caesar-type cipher. This cipher used a shift of three and can be represented by the table below (table 1).
| plaintext |
a |
b |
c |
d |
e |
f |
g |
h |
i |
j |
k |
l |
m |
n |
o |
p |
q |
r |
s |
t |
u |
v |
w |
x |
y |
z |
ciphertext
equivalent |
d |
e |
f |
g |
h |
i |
j |
k |
l |
m |
n |
o |
p |
q |
r |
s |
t |
u |
v |
w |
x |
y |
z |
a |
b |
c |
So, a -> d, b -> e etc. The letters in the table can also be represented by numbers like so (table 2).
| plaintext |
a |
b |
c |
d |
e |
f |
g |
h |
i |
j |
k |
l |
m |
n |
o |
p |
q |
r |
s |
t |
u |
v |
w |
x |
y |
z |
| 0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
11 |
12 |
13 |
14 |
15 |
16 |
17 |
18 |
19 |
20 |
21 |
22 |
23 |
24 |
25 |
ciphertext
equivalent
Shift = +3 |
d |
e |
f |
g |
h |
i |
j |
k |
l |
m |
n |
o |
p |
q |
r |
s |
t |
u |
v |
w |
x |
y |
z |
a |
b |
c |
| 3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
11 |
12 |
13 |
14 |
15 |
16 |
17 |
18 |
19 |
20 |
21 |
22 |
23 |
24 |
25 |
0 |
1 |
2 |
So, 0 -> 3, 1 -> 4 etc.
The reason to use numbers in place of letters is that arithmetic can be done on them.
Modulo arithmetic
Modulo arithmetic deals with remainders after division. For example, 4 modulo 2 is 0, because the remainder left after 4 is divided by 2 is 0 as it goes exactly. Another example is 5 modulo 2: this equals 1, as 2 goes twice into 5 with one remainder (2x2=4 and 5-4=1). Here is a table that shows numbers 0 to 10 modulo 5 (table 3).
| Number N |
Modulo M |
Remainder R |
| 0 |
5 |
0 |
| 1 |
5 |
1 |
| 2 |
5 |
2 |
| 3 |
5 |
3 |
| 4 |
5 |
4 |
| 5 |
5 |
0 |
| 6 |
5 |
1, because
1x5=5,and 6-5=1 |
| 7 |
5 |
2, because
1x5=5 and 7-5=2 |
| 8 |
5 |
3 |
| 9 |
5 |
4 |
| 10 |
5 |
0 |
Modulo 5 division can be formally written as N = R mod 5. (mod is short for modulo). Where N is the number that is being divided, R is the remainder after division. For any modulus M the notation is N = R mod M.
The Caesar cipher can be represented using this notation as C = (P + 3) mod 26. Where C is the encrypted value and P is the value being encrypted.
Here are two examples:
One: We know that a->d, or using the number notation 0->3 (see table 2 above). Using the formula above C = 3 and P = 0,
does 3 = (0 + 3) mod 26?
The answer is yes as 3 divided by 26 'does not go' and there is a remainder of 3.
Two: We know that y->b, or using the number notation 24->1 (see table 2 above). Using the formula above C = 1 and P = 24,
does 1 = (24 + 3) mod 26?
or 1 = 27 mod 26?
The answer is yes as 27 divided by 26 goes once and there is a remainder of 1 (1x26=26 and 27-26=1).
The corresponding deciphering formula is P = (C - 3) mod 26
As can be seen in table 2 the ciphertext, the numbers 0 to 25, are very regular 0->3, 1->4, 2->5 etc. This predictability makes it easy to crack. This is not the case if a different modulo system is used.
C = 5P mod 26
This is a much better system because as P increases by 1 C does not follow the same pattern. Here is a table showing the values (table 4).
| plaintext (P) |
a |
b |
c |
d |
e |
f |
g |
h |
i |
j |
k |
l |
m |
n |
o |
p |
q |
r |
s |
t |
u |
v |
w |
x |
y |
z |
|
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
11 |
12 |
13 |
14 |
15 |
16 |
17 |
18 |
19 |
20 |
21 |
22 |
23 |
24 |
25 |
ciphertext equivalent
(C = 5P mod 26) |
0 |
5 |
10 |
15 |
20 |
25 |
4 |
9 |
14 |
19 |
24 |
3 |
8 |
13 |
18 |
23 |
2 |
7 |
12 |
17 |
22 |
1 |
6 |
11 |
16 |
21 |
Here are two examples:
One: P = 4
C = (5x4 = 20) mod 26
C = 20 mod 26
C = 20 because 26 goes 0 times into 20 and the remainder is 20.
Two: P = 7
C = (5x7 = 35) mod 26
C = 35 mod 26
C = 9 because 26 goes 1 time into 35 and the remainder is 9 (1x26 = 26 and 35-26 = 9).
The deciphering formula is P = 21C mod 26, for an explanation of why this is so read Sarah Flannery's book "In Code", pages 71 to 112.
How this can be used
A sample of plaintext can be encrypted by:
- Taking a character at a time and taking its number representation (e.g. a = 0, b = 1, z = 25) and encoding it using C = 5P mod 26 values.
- The letter corresponding to this number is then substituted and added to the ciphertext string.
Here is an example:
plaintext = 'hello'; ciphertext = 'judds'
| P = 'h' -> 7 |
P = 'e' -> 4 |
P = 'l' -> 11 |
P = 'l' -> 11 |
P = 'o' -> 14 |
| C -> 9 |
C -> 20 |
C -> 3 |
C -> 3 |
C -> 18 |
| 9 -> 'j' |
20 -> 'u' |
3 -> 'd' |
3 -> 'd' |
18 -> 's' |
C = 5P mode 26 is the formula we have been using, where 5 is the multiplier
m. There are other values for m that can be used when working with modulus 26. They are: 1, 3, 5, 7, 9, 11, 15, 17, 19, 21, 23, 25.
These numbers guarantee a one to one relationship between a P number and a C number. m numbers such as 4 generate some C numbers that are the same for different P numbers, so they can not be used. The rule is that a 'good' m number must have no factor in common with 26 besides the number 1. They are said to be "relatively prime". The number 4 is ruled out and is a 'bad number' because it has the factor 2 in common with 26 (2x2 = 4 and 2x13 = 26).
So, using the modulus method of encryption increases the key space to 26 x 13 = 338 (the number of good multipliers). However, as an m value of 1 does not change the P value this can be ruled out as being useful. Taking this into account reduces the key space to 312.
The BYOB3 file attached to this page uses the C = 5P mod 26 formula.
The modulo method can be extended by adding in a shift. The general formula then becomes:
C = (mP + s) mod 26
Where C is the numeric equivalent of the encrypted character, m is the multiplier, s is the amount of shift (in the Caesar cipher s = 3) and P is the numeric representation of a plaintext character (a to z => 0 to 25). As there are 26 shifts that can be done the keyspace becomes 26 time bigger, or 312 x 26 = 8,112.
An example of this type is C = (5P + 18) mode 26 and P = (21P + 12) mod 26
Read Sarah Flannery's book "In code" to find out how the numbers 21 and 12 are arrived at.
Grouping characters
The encryption method can be made even stronger by encrypting letters in groups. For example groups of two give 26x26 = 676 combinations from aa, ab, ac...zx, zy, zz. Each one of these combinations can then be assigned a plaintext number starting with 0 for aa through to 675 for zz.
To encrypt a piece of plaintext group it into two characters like so:
plaintext = hellohowareyou
grouping = he ll oh ow ar ey ou
number pattern = ? ? ? ? ? ? ?
Then proceed in a similar manner to the 5P mod 26 method, though the formula becomes something like
C = (159P + 580) mod 676 and the decrypting formula becomes P = (659C + 396) mod 676.
Note, that by combining two characters the keyspace has increased by 26 again. How about combining three or four? Soon the keyspace size becomes astronomically big. To quote Sarah Flannery's book, page 105:
Although the cryptosystems based on enciphering blocks of plaintext by the "multiply and shift" rules described are vulnerable to various forms of attack, modern cryptosystems rely in part for their security on the "blocking" of plaintext into huge blocks. When the modulus is a 200 digit number, the blocks of text can be of length 95 or more, and the number of different blocks of this length is astronomical.