Affine Cipher - Apps for the TI89 Calculator - Free Download



Chapter 3 – Linear Cipher

In this chapter we will combine the previous two ciphers into one super cipher, the Linear Cipher. We first multiply a plain letter value and afterwards perform an additional Caesar shift. This allows more encryptions thus hampering an eavesdropper’s job. We will be able to use our knowledge of the two previous chapters to discover the number of possible unique encryptions for the Linear Cipher. The Linear Cipher turns out to be an insecure cipher as well. However, it offers the opportunity to study the “Euclidean Algorithm” to find the good encoding keys and the “Extended Euclidean Algorithm” to find the corresponding decoding keys. Furthermore, we will learn a very important aspect of cryptography: How to use letter frequency analysis in order to crack ciphers. After learning how to crack the Linear Cipher we will extend this technique to crack any Monoalphabetic Cipher, even the Random Substitution Cipher.

3.1 Encryption using the Linear Cipher

The Caesar and the Multiplication Cipher are not secure ciphers. To improve the security of an encrypted document we combine the Caesar and the Multiplication Cipher: we first multiply each plain letter by an integer a as done in the Multiplication Cipher and consequently shift it by b positions. We therefore obtain the following

Definition of the Linear Cipher:

The Linear Cipher encodes each plain letter P to a cipher letter C using the following encoding function:

C = a*P + b MOD M

where the encoding key consists of the pair of integers (a,b).

We call a the factor key and b the shift key.

Let us first investigate how many possible encryptions the Linear Cipher offers. Certainly more than the two previous ciphers, but how many exactly? Therefore, we have to first answer the following question: Does the Linear Cipher yield unique encryptions for any key pair (a,b)? Take a moment and come up with your guess.

Let’s start by checking the factor key a=2 and the shift key b=4. Thus, we use the encryption function C= 2*P + 4 MOD 26 to encode the virus carrier message as follows:

|PLAIN TEXT |A |

|P = 9*C - 36 MOD 26 |You can recognize already the linear form, however, we want to use keys that are |

| |between 0 and M. Thus, we replace the –36 by its positive equivalent between 0 and |

| |26, namely by 16. (Why 16 ?) |

|P = 9*C + 16 MOD 26 |Done we are. |

Hence, the decoding function P = 9*(C-4) MOD 26 with the decoding key pair (9,4) can be rewritten as the Linear Cipher P = 9*C + 16 MOD 26 with the decoding key pair (9,16).

The advantage of being able to rewrite the decoding function as a Linear Cipher of the the form P = A-1 * C + B MOD M becomes more evident when programming the decoding function of the Linear Cipher. Instead of writing extra code for a new decoding function we may use the same function used to encode the plain text. The only task remaining is to determine the correct decoding key pair (A-1, B).

Notice in our example that the decoding factor key A-1 = 9 is simply the inverse of the encoding factor key a=3. Thus, A-1 = a-1. That was easy. Computing B is a bit more tricky: The decoding function is P = a-1 *(C-b) MOD M. Distributing a-1 yields a-1 *C - (a-1 * b) MOD M. Therefore, we choose B to be that positive integer between 0 and M that is congruent to the negative integer – (a-1 * b). We may write this as: B ( - (a-1 * b) MOD M.

The Decoding Function as a Linear Cipher:

Messages that were encrypted with the encoding function of the Linear Cipher, C = a*P + b MOD M, have to be decrypted using the decoding function

P = a-1 *(C-b) MOD M.

Alternatively, we may express the decoding function as the Linear Cipher

P = A *C + B MOD M

with the decoding key pair (A,B) = (a-1, - (a-1 * b) MOD M)

Exercise1: Find the decoding key pair (A,B) for a message that was encoded with C = 5*P +17 MOD 26.

Exercise2: If we add a blank to the 26 letters in the previous exercise yielding an alphabet length of M=27. Therefore, a message is encoded with C = 5*P +17 MOD 27. Find the decoding pair (A,B).

How to determine the decoding key a-1

To find a decoding key a-1, we could just do it the fast way that I demonstrated to you in the previous chapter: Just look at the 26x26 multiplication table, find the only 1 in the row of the key a used and finally go up that column to obtain a-1. I.e. if a=3, then a-1=9 since the only 1 in the 3-row is in the 9-column. That works fine, no problem. However, what if we choose a large alphabet length M? It would be inefficient to use the same procedure as it gives more information than needed. The good news are that there exists a shortcut that finds the inverse a-1 for any key a and for any alphabet length M in an efficient manner.

The procedure is called Extended Euclidean Algorithm. It computes a-1 in two steps: Firstly, it computes the greatest common divisor (gcd) of a and M. This part of the whole procedure used is called Euclidean Algorithm. Secondly, extending the Euclidean Algorithm finds the desired inverse a-1 of a MOD M. In the following section you will learn how the Euclidean Algorithm finds the gcd of a and M. Thereafter, I will show you how the Extended Euclidean Algorithm computes the inverse a-1 by making use of the computations used to find the gcd of a and M.

1. The Euclidean Algorithm quickly finds the Greatest Common Divisor of two Integers

As you can imagine, the Euclidean Algorithm goes back to the Geek Philosopher and Mathematician Euclid. He described the algorithm in the 7th chapter of his book Elements written around 300 B.C. However, he did not invent it. This algorithm may be 300 years older. It is not known who invented it.

The word algorithm is derived from the name of the Persian Mathematician Mûsâ Al-Chowârizmi. In 825 A.D., he was the first to publish a book that describes procedures to solve mathematical problems (such as the Euclidean Algorithm).

Let’s study the Euclidean Algorithm. How does it find the greatest common divisor of two integers? I will explain the idea graphically. Picture the even divisors of one integer as divisor-lines.

Example1: The integer 5 has the divisors 1 and 5. Therefore, 5 can be reached by 1 jump of length 5 or by 5 jumps each of length 1. Graphically:

1 5

Example2: The integer 6 has the divisors 1,2,3 and 6. Thus, the 6 can be reached by 1 jump of length 6 or by 2 jumps of length 3 or by 3 jumps of length 2 or by 6 jumps of length 1. Graphically:

1 6

To now find a common divisor of two integers all we have to do is to compare the divisor-lines of both integers to find matching lengths. Our goal is to find the greatest common divisor of two integers. Thus, just find the longest line among those that match in length.

Example1: Consider the two integers 6 and 8. Their divisor lines look as follows:

1 2 3 4 5 6

1 2 3 4 5 6 7 8

We see that the lines of length 2 (in blue) are the longest among those that both have in common. Thus, 2 is the greatest common divisor of 6 and 8: gcd(6,8)=2.

Example2: Consider the two integers 12 and 8.

1 2 3 4 5 6 7 8 9 10 11 12

1 2 3 4 5 6 7 8

We observe that among the matching lines of length 1, 2 and 4, 4 is the longest and thus is the greatest common divisor of 12 and 8: gcd(12,8)=4.

Graphically, the concept is easy: to find the greatest common divisor of two integers just find the divisors of both integers and find the greatest divisor among those they have in common. The concept is easy, however, it can not be executed for large integers. I mentioned to you already earlier that there are no procedures devised (yet) that are guaranteed to produce the divisors of an arbitrary integer consisting of 100 digits and more. This is the caliber of integers to deal with in the RSA encryption. Here is where the Euclidean Algorithm comes in very handy. Although devised over 2000 years ago, it has proven to be a very efficient procedure to compute the greatest common divisor of two integers without knowing the divisors of both integers. Here is how:

We now picture the two integers using two dimensions: We draw the divisor line of the larger integer, here M=4, horizontally and the shorter one, a=2, vertically:

4

2

Instead of finding the longest common lines I now find the greatest common square that fills the rectangle perfectly. This reflects the fact that two integers urge us to work in 2 dimensions. In our example, two 2x2 squares fill the rectangle as the greatest square. Therefore, the greatest common divisor of 4 and 2 is the side of the greatest squares that fill the rectangle perfectly. It is 2. Certainly, any rectangle with integer-dimensions may be filled with 1x1 squares (just as any integer can be divided by 1). However, we want to find the greatest common divisor. Therefore, we want to find the greatest square that fills the rectangle.

Let’s look at further examples:

Example1: The greatest common divisor of 6 and 2 is 2 since the 6x2 rectangle can be filled with 2x2 squares:

Example2: The greatest common divisor of 6 and 3 is 3 since the 6x3 rectangle can be filled with 3x3 squares:

Example3: The greatest common divisor of 5 and 2 is 1 since the 5x2 rectangle can only be filled with 1x1 squares: Although two 2x2 squares fit into the rectangle they don’t fill the whole rectangle. Two rectangles each of size 1x1 are needed to cover the remainder.

Example4: The greatest common divisor of 5 and 3 is 1 since the 5x3 rectangle can only be filled with 1x1 squares:

Although one 3x3 and one 2x2 square fit in the rectangle they don’t suffice to fill the whole rectangle. Two rectangles each of size 1x1 are needed to cover the remainder.

Let’s use this gcd(5,3)=1 example to demonstrate the filling-the-rectangle-with-squares idea in the Euclidean Algorithm:

|The rectangle with longer side 5 holds one square with sides 3 |5 = 1 * 3 + 2. |

|and leaves a remainder of 2. | |

|The remaining rectangle with longer side 3 holds one square with|3 = 1 * 2 + 1 |

|sides 2 and leaves a remainder of 1. | |

|The remaining rectangle with longer side 2 holds two squares |2 = 2 * 1 |

|with sides 1 and leaves no remainder. | |

Visual example1 of the Euclidean Algorithm:

Architecturally, the greatest common divisor can be computed by finding the greatest square tiles that yet fill a rectangular room perfectly. Say, we have a 26 by 21 ft2 room that is to be tiled. What are the largest square-shaped tiles that will do the job?

21 1 1 1 1 1

26=1*21+5

21=4*5+1 5

5=5*1

21 5

5

5

21 5

26

We start off with a huge 21x21 tile. Apparently it doesn’t fill the room perfectly. Now the 21 x 5 remainder of the room can be filled with four 5x5 tiles leaving a 5 x 1 remainder. That remainder can only be filled using 5 1x1 tiles. Thus, to fill the room completely we have to use the smallest square tiles possible that have integer sides: 546(=21*26) 1x1 tiles will cover the 26x21 room perfectly. This shows that gcd(26,21)=1. Notice that we did not have to compute all divisors of 26 and 21 in order find their greatest common divisor.

Visual example2 of the Euclidean Algorithm:

Goal: Find the greatest common divisor of 25 and 5:

25=1*20+5

20=4*5+0 5

20 5

5

5

20 5

25

The 20x20 tile does not fill the room, it leaves a 20 x 5 remainder that can be perfectly filled using four 5x5 tiles. Why does that show that the gcd(25,20)=5? With other words: how do we know that the sixteen 5x5 tiles fill the big 20x20 perfectly? The reason is that the four 5x5 tiles don’t leave a remainder in the 20 x 5 rectangular area as we had in the first example. In both examples we had a horizontal fit of the 5x5 tiles, however, the vertical mattered. We could only fill the 20x20 or the 21x21 area perfectly with the 5x5 tiles if they additionally produce a perfect vertical fit. This is the case for the 20x20 but not for the 21x21 area. Thus, gcd(25,20)=5. However, besides forming a perfect horizontal fit, the 1x1 tiles also produce a perfect vertical fit in the 5x1 area which in turn shows that they fill the four 5x5 area and the 21x21 area perfectly.

We are now in a position to state the working principle of the Euclidean Algorithm:

The search for the gcd of 26 and 21 can be reduced by finding that of 21 and 5.

As an equation: gcd(26,21)=gcd(5,21).

This reduction principle continues until the room can be perfectly tiled with tiles whose length yield the gcd.

As an equation: gcd(5,21)=gcd(5,1)=1.

Altogether, we have the chain:

gcd(26,21)=gcd(5,21) =gcd(5,1)=1.

Example7:

The Euclidean Algorithm becomes really helpful when finding the gcd of two large integers. Say, we want to find the gcd of M=2322 and a=654. Would the answer be 2 or 3 or 4 or 6 or 7 or 8? We can’t really tell right away that the answer is 6. Here is why:

|2322 = 654*3 + 360 | |gcd(2322,654) = gcd(654,360) |

|654 = 360*1 + 294 | |gcd(654,360) = gcd(360,294) |

|360 = 294*1 + 66 | |gcd(360,294) = gcd(294,66) |

|294 = 66*4 + 30 | |gcd(294,66) = gcd(66,30) |

|66 = 30*2 + 6 | |gcd(66,30) = gcd(30,6) |

|30 = 6*5 | |gcd(30,6) = 6 |

Therefore, gcd(2322,654) = 6.

Exercise: Find the gcd of 2546 and 1728. Before doing it out, guess what it could be?

3.2.2 Proof of the Euclidean Algorithm

How can we prove that the Euclidean Algorithm yields the greatest common divisor of two integers. It worked fine in our tiling example. The foregoing made sense - intuitively. But how can we mathematically prove that the Euclidean Algorithm works correctly and will always yield the proper greatest common divisor. In other words, how can we transfer our intuitive understanding into sober mathematical equations? Now, this is a wonderful opportunity for you to learn the formal process to prove the correctness of the Euclidean Algorithm.

What we really have to prove is that the chain of equations eventually yields the greatest common divisor. How do we bridge two equations? In other words: Why is the equal sign correct? If we manage to bridge the first two equations we bridge all equations since the setup of the subsequent equations is identical. This would mean for the above example that we have to prove that the gcd of 2322 and 654 equals the gcd of 654 and 360: gcd(2322,654) = gcd(654,360). We would therefore also prove that gcd(654,360) = gcd(360,294) which bridges the next two equations. Continuing in this manner we eventually end up with the last equation that has a remainder of 0. Here, the smaller integer as a divisor of the larger integer turns out to be the gcd of the two integers we started with. In the example, the last equation is 30 = 5 * 6 so that the gcd(30,6) = 6 turns out to be the gcd of 2322 and 654.

Therefore, to prove the Euclidean Algorithm we will consider two cases. In both cases we assume that the integer b is greater than the integer a: b>a. In this case, Mathematicians use the standard clause “without a loss of generality” since the restriction that b>a is not at the cost of any generality. We just assign the greater of the two original integers to b and the smaller to a. (Why would it not make any sense to try to find the gcd of two equal integers, that is when a=b?)

Proof of the Euclidean Algorithm:

1. case: In case a is a divisor of b such that b=k*a for some integer k. Then

gcd(b,a) = a

because a’s greatest divisor is a which is also a divisor of b.

2. case: Starting with

b = q0*a + r1 and if r1 (0 we then obtain the following chain of equations:

a = q1*r1 + r2

r1 = q2*r2 + r3

r2 = q3*r3 + r4

:

:

rn-2 = qn-1*rn-1 + rn

rn-1 = qn*rn + 0 until the first equation yields a remainder of 0.

We are guaranteed to end up with an equation that contains a remainder of 0 since the integers in the left column are in decreasing order:

b > a > r1 > r2 > …. > rn-1 .

In the above example: 2322 > 654 > 360 > 294 > 66 > 30.

Since these integers get smaller and smaller but never become negative one of the equations must yield a remainder of 0. Then, the gcd(b,a) can be read off as the fifth remainder r5 (in the above example gcd(2322,654) = rn = 6) from the second to last equation (i.e. 66=30*2+6) or last equation (i.e. 30=6*5). I will now prove in general that gcd(b,a)=rn if the (n+1)st equation yields a remainder of 0 by proving the two inequalities I) gcd(b,a) < rn and II) rn < gcd(b,a) which when both proved to be true yield nothing but the equality.

Proof that gcd(b,a) < rn :

In b = q0*a + r1, the greatest common divisor of b and a (unknown so far) also divides r1. (I.e. the gcd(36,28) = 4 also divides r1 = b – q0*a = 36 – 2*14 = 8). Therefore, the gcd(b,a) is a common divisor of a and r1 and we thus are guaranteed that the gcd(a, r1) cannot be greater than the gcd(b,a):

gcd(b,a) < gcd(a,r1). For the same reason, the second equation yields gcd(a, r1) < gcd(r1, r2), the third yields gcd(r1, r2) < gcd(r2, r3), etc. Finally, the next-to-last equation yields gcd(rn-2, rn-1) < gcd(rn-1, rn) = rn. The equality is what we just proved in the 1. case: Since the last equation rn-1 = qn*rn leaves no remainder, rn-1 is a divisor of rn so that gcd(rn-1, rn) = rn. The chain of inequalities yields: gcd(b,a) < rn.

Proof that rn < gcd(a,b):

The converse is also true. Starting from the last equation and working our way up we obtain the following chain of inequalities:

rn is a divisor of rn-1 ( from the last equation),

Therefore, rn also divides rn-2 which we obtain from the next-to-last equation using the same reasoning as in part I.

Continuing going from bottom to top, rn also divides rn-3, …., r2, r1, a and b. We see that rn is a common divisor of a and b and altogether we therefore obtain that

rn < gcd(a,b).

This completes the proof. The two inequalities now prove that

rn = gcd(a,b)

Exercise: Go through the two cases of the proof one more time. Check that the gcd(72,56) = 8. In that way you make the proof more concrete and thus more tangible. Remember: Any abstraction has its origin in a sufficient repertoire of concrete examples.

The C++ implementation of the Euclidean Algorithm

Devising the Euclidean Algorithm can be accomplished quite easily as we just have to inspect the steps and then formalize them. Let’s take a closer look at the example7 when we found the gcd of L=2322 and S=654.

We started off by dividing the larger integer L by S yielding the quotient Q and the remainder R as follows:

| L = Q * S + R |We will just use the values S and R for the next step (see the arrow). However, we |

| |won’t need Q and L anymore. |

|2322 = 3 *654 + 360 | |

| | |

|654 = 1* 360 + 294 |I first compute R in the above equation from L and S as follows: R = L MOD S, here |

| |360. It becomes the new value of S. In terms of programming this procedure, we have |

| |to be aware of a technicality: Before assigning it to S, we have to assign the value |

| |of S to the new L. Otherwise, we would lose the value of S, here 654. Thus, the order|

| |of the three computer statements here has to be: |

| |R = L MOD S, L=S, S=R. |

| | |

|360 = 1* 294 + 66 |Similarly, we have to perform the same computations here: |

| |R = L MOD S, L=S, S=R. |

| | |

|294 = 4* 66 + 30 |Similarly, R = L MOD S, L=S, S=R. |

| | |

|66 = 2* 30 + 6 |Again: R = L MOD S, L=S, S=R. |

| | |

|30 = 5 * 6 |Finally here: R = L MOD S, L=S, S=R. |

| |Since the new remainder equals 0 for the first time, we are done now. The desired |

| |gcd is the remainder of the second last equation (in bold), here 6, which is the |

| |value of S in the last equation. |

|Hence, gcd(2322,654)=6. | |

We can translate the pseudo-code of the Euclidean Algorithm (to the left) into C++ code as follows:

|As pseudo-code: |As C++ code: |

|As long as R is not 0 do the following: |While(R!=0) |

| |{ |

|R=L MOD S; |R=L%S; |

|L=S; |L=S; |

|S=R; |S=R; |

| |} |

|Finally, output the gcd of L and S |cout S;

while(R!=0)

{

R=L%S;

L=S;

S=R;

}

cout S;

cout(x[0]*a[1]))

{cout ................
................

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

Google Online Preview   Download