Chapter 2 : Multiplicative Cipher



Chapter 2 – Multiplicative Cipher

In this chapter we will study the Multiplicative Cipher. Instead of adding a number as we did in the Caesar Cipher, we will now multiply each plain letter by an integer a, our secret encoding key. As some of them fail to produce a unique encryption, we will discover an easy criterion for keys that produce the desired unique encryptions (the “good” keys) and apply it to different alphabet lengths. When doing so we will discover very important mathematical encryption tools such as Euler’s (-function, Euler’s and Lagrange’s Theorem and study further examples of groups, rings and fields.

2.1 Encryption using the Multiplication Cipher

Instead of encoding by adding a constant number, we multiply each plain letter by our secret key a. Since each plain letter turns into 0 for a=0 and remains unchanged for a=1, we start with a=2. We will multiply MOD 26 as we are using the 26 letters of the English alphabet. We get the following encoding and decoding table.

|PLAIN LETTER: |A |B |C |D |E |F |G |

|Secret key a=2 |13 |0 |19 | |0 |13 |19 |

| | | | | | | | |

| |0 |0 |12 | |0 |0 |12 |

|Cipher letter |a |a |m | |a |a |m |

You can see the dilemma of this message. Decoding “aam” can either yield NAT or ANT as the plain text. What would you do? Of course, you don’t want to receive any more ambiguous messages. Let’s simply test all possible keys of the multiplication ciphers MOD 26:

PLAIN LETTER

| |0 |

|1 |1 |

|3 |9 |

|5 |21 |

|7 |15 |

|9 |3 |

|11 |19 |

|15 |7 |

|17 |23 |

|19 |11 |

|21 |5 |

|23 |17 |

|25 |25 |

Three important observations:

1. All decoding keys a-1 in the right column are among the set of all encoding keys a. In fact, the sets of the encoding and decoding keys are identical. Coincidence? No, it is not. Just as the regular multiplication of two integers is commutative (i.e. 3 * 9 = 9 * 3 =27) the MOD- multiplication is commutative (3 * 9 = 9 * 3 = 1 MOD 26). You can observe this order-doesn’t-matter rule in the original 26x26 multiplication table: The diagonal line from the top left to the bottom right forms a reflection line. I.e. 21 is an inverse to 5 MOD 26, therefore 5 is inverse to 21 and the two 1’s are mirrored over the diagonal line. Therefore, the set of all encoding keys must equal the set of all decoding keys.

2. If we extract those rows with the good keys a = 1,3,5,7,9,11,15,17,19,21,23,25 and their corresponding columns, we obtain:

| |1 |

For the purpose of setting up an explicit formula for ((M), we now try to give the three factors (in parentheses) the same format. We factor p1=2 yielding

| = 2*(2-1)*(3-1)*(5-1) | = p1* (p1- 1)*( p2-1)*( p3-1). |

The three factors in the parentheses already have the same desired format, however, the single 2 destroys it. The ultimate trick to yet produce the same format is factoring: from each parentheses we factor the first integer (which is a divisor of M) and obtain:

|((60) = 22*(1 -1/2) * 3*(1 -1/3) * 5 * (1 -1/5) |((M) = p12 * (1 -1/ p1) * p2*(1 -1/ p2) * p3 * (1 -1/ p3) |

| = 22*3*5*(1 -1/2)*(1 -1/3)*(1 -1/5) | = p12* p2* p3*(1 -1/ p1)*(1 -1/ p2) * (1 -1/ p3) |

| = 60*(1 -1/2)*(1 -1/3)*(1 -1/5) | = M * (1 -1/ p1) * (1 -1/ p2) * (1 -1/ p3). |

This is it. Notice in the last row that all we need to know are the prime factors p of M without knowing how often they occur. We then write them in the form (1-1/p), multiply them and that product by M yielding ((M). On the right we ended up with the explicit formula for ((M) when M consists of one prime power and two primes. It surely acquires this simple form for any number of primes or prime powers. Notice, that all we need to find are the different primes, say p1, p2,..., pn, as our explicit formula for the number of unique encryptions appears to be:

Formula for the number of good keys for any alphabet length M:

For an alphabet length M, there are ((M) = M * (1- 1/p1) * (1- 1/p2) *…* (1- 1/pn) good keys where each pi is a prime divisor of M.

It is really enjoyable to use this simple formula as we just need to find all prime divisors of M and don’t have to worry about how often they occur. Therefore, a simple prime check program would be sufficient to find the divisors p of M. We then set up the factors of the form (1- 1/p), multiply them and eventually multiply that answer by M.

Example1:

Say M=180, then a prime check program yields the prime factors 2,3 and 5, so that

((180) = 180 * (1-1/2) * (1-1/3) * (1-1/5)

= 180 * (1/2) * (2/3) * (4/5)

= 90 * (2/3) * (4/5)

= 60 * (4/5)

= 48

Example2:

Say M=360, since 360=2*180 the prime factors are again 2,3 and 5, so that

((360) = 360 * (1-1/2) * (1-1/3) * (1-1/5)

= 360 * (1/2) * (2/3) * (4/5)

= 180 * (2/3) * (4/5)

= 120 * (4/5)

= 96

Example3 is for you:

Say M=90, since 90=____ the prime factors are _______, so that

((90) = 90 * (1-1/__) * (1-1/__) * (1-1/__)

= 90 * ____________________

= _______________

= _______________

= ___

Of course, I could have computed the answers in the above examples right away but I wanted to give you the chance of brushing up on your skills to multiply fractions. A little computer program turns out to be again very valuable as the number of good keys can be easily determined by first finding all prime factors of M to then use the above explicit formula.

//Author: Nils Hahnfeld 10-16-99

//Program to determine ((M)using M*(1-1/p1)*(1-1/p2)*...

#include

#include

void main()

{

int factor, M, m;

float phi;

clrscr();

cout ................
................

In order to avoid copyright disputes, this page is only a partial summary.

Google Online Preview   Download