Hill Ciphers

Mail: ccollins@math.utk.eduPreliminariesStart MATLAB (from Start Menu). Arrange your windows so you can see MATLAB and this webpage.Review Inverses and Mod ArithmeticIn MATLAB you can compute the determinant of a matrix by usingdetand the inverse usinginv. For example, try A = [1 2; 3 4]; det(A) inv(A) For the 2x2 case we know that we can construct the inverse by rearranging the entries of the matrix and dividing by the determinant. This is similar to what happens in general. IfAis a matrix with integer entries then det(A)*inv(A) also has integer entries, no matter how bigAis. In MATLAB we perform mod-arithmetic (mod-27) by using regular arithmetic but then usingmodon the result. The only thing we have to remember is that instead of dividing, we multiply by the inverse. To find the multiplicative inverse of a numberx(mod-27) we can use the following steps: x =numberthe number you want to find the inverse of num = [1:26] all the numbers from 1 to 26 res = mod(x*num,27) result of x*(1,...,26) mod 27 find(res==1) this finds which value gives a result of 1 find will either produce a number (the inverse) or will result in "ans = []" meaning there is no inverse. This is from the previous lab, and you should have used this method or something similar to fill in the multiplicative inverses in the HW.MATLAB functions (vs. scripts)Last lab you created two programs "code1.m" and "decode1.m". These are what are calledscripts. When you run them it works just like you had typed in those commands in the command window. The only problem with scripts (as some of you found out) is that they can change the values of variables that you don't want changed. A way to fix this is to convert these scripts intofunctions. In a function all the work and variables are done in their own workspace. This means that you must give the function all the information it needs and have it pass back everything that you want passed back. To tell MATLAB that the file is a function and what the input and output variables are you put a line like this at the top of the file: functionoutput=functionname(input) For example, we want the function version of code1.m to take a message as input and return the number values according to Cipher 1. Calling this version "code2.m" it might look like this: function cP = code2(P) % code2: converts a message to numbers P = upper(P); cP = real(P); cP = cP - 64; ind = find(cP<0); cP(ind) = 0; Copy this to a file and save as "code2.m". To use it, you type code2('my name is bob') or M = 'now is the time for all good mathematicians'; res = code2(M); You do not have to use the same variable names (P and cP) as the ones in the function when you call the function. Now, create a function from decode1.m and call it "decode2.m". The input should be the matrix of number values and the output should be the message. Make sure you put semi-colons (;) at the end of the lines so that no extra stuff gets displayed. If you aren't sure what to do, there's a copy of this function at the end of this file. When you have it done you can test it by decode2(code2('enter any thing here')) and you should get back the uppercase version of what you put in. Note: a function or a script can use a function, so if you find yourself running the same commands over and over, think about putting them into a script or a function.Hill CiphersFor the Hill Cipher we use an NxN matrix to encode our message. First we need to know how to do the transformation and then how to decode the message.EncodingLetEbe our 2x2 encoding matrix. And letPbe our message. The first step is to usecode2to get the matrix of numbers forP: cP = code2(P); Now we need to put this row matrix into the proper shape for our encoding matrix; it needs to be 2xM. That means it must have an even number of characters. l = length(cP); % number of characters if (mod(l,2)==1) % l is odd cP(l+1)=0; % add a 0 to the end l = l + 1; % increase length by one end cP = reshape(cP,2,l/2); % changes cP into 2xM IfEwas 3x3 we would have to see if we needed to add 1 or 2 extra spaces to the message to make the length a multiple of 3. Now we can encode our message (mod-27) eP = mod(E*cP,27); Before we can usedecode2to turn this back into text, we need to 'unfold' it (the result is 2xM). So we finish our encoding by eP = eP(:)'; % makes eP 1x(2M) C = decode2(eP); % transforms it back to text Use the following matrixEand messagePand see what you get: E = [1 2; 3 4]; P = 'Bobby builds baby bottles'; You should get: ELFNYUQIFUOGDHEKYUELFEVBSC Note that the 7 Bs in the original message get transformed into EFNQHKE thus the character frequencies get all messed up. I put a script "hill.m" at the bottom of this message for this process. Challenge: write a function which takes a message and a 2x2 matrix and produces the encoded message.DecodingDecoding is just like encoding, except that we need to use the inverse of our encoding matrix. Since we are using mod-27 arithmetic we can't just useinv(E). Remember the formula for the inverse: 1 ( d -b ) ( a b ) inverse of E = ----- ( ), where E = ( ). det E ( -c a ) ( c d ) We can use this same formula, but instead of dividing by the determinant, we multiply by the inverse (mod-27) of the determinant. And instead of using -b and -c, we use their additive inverses. In the case when E = [1 2; 3 4]; we havedet(E) = -2 = 25. The inverse of 25 is 13, so the inverse ofE(mod-27) is ( 4 25 ) ( 52 325) (25 1) 13 ( ) = ( ) = ( ) (mod-27) (24 1 ) (312 13) (15 13) Let D = [25 1; 15 13]; and repeat the steps above that we used to encode the message, replacingEbyDand starting with the coded messageCinstead ofP. That would look like cP = code2(C); l = length(cP); % number of characters if (mod(l,2)==1) % l is odd cP(l+1)=0; % add a 0 to the end l = l + 1; % increase length by one end cP = reshape(cP,2,l/2); % changes cP into 2xM eP = mod(D*cP,27); % decode message eP = eP(:)'; % make it a row vector M = decode2(eP); % convert to characters After performing these steps the messageMshould be the same as the upper case version of the original messageP.ExercisePick an encoding matrixE(different from above) and a messageP. Encode the message. Find the decoding matrixDand decode the message. Print out or send me: Your matricesEandDYour messages: original and encoded Challenge: Try a matrix bigger than 2x2Extra StuffComputing frequencies: Suppose we have the numbers from an encoded message in a matrixcP. How can we figure out the frequencies? Since we know the values must be between 0 and 26, we can just set up 27 'counters' and increment the appropriate counter when we see the corresponding value. It might look like this: counter = zeros(1,27); % row matrix of 27 zeros l = length(cP); % number of values to look at for i = 1:l % loop through all the values index = cP(i)+1; % value (+1 so in the range 1-27) counter(index) = counter(index) + 1; % increment counter end Now for further processing we might want to see these frequencies in order, with their appropriate percentages [x,order] = sort(-counter); % sorts from largest to smallest and % gives the order they are in for i = 1:27 index = order(i); % index of i-th most common perc = counter(index)/l*100; % frequency percent disp([index, perc]) % display results end Challenge: write this as a function which takescPas input and prints out the results not by number but by letter. You might need the commandnum2str---------------------------------SOLUTIONS------------------------------- To use these, select all the lines in green, copy them, and paste them into the M-file editor window. Save and run.decode2.mfunction M = decode2(cP) % decode2.m by Dr. Collins 6/19/01 for GSS:Math ind = find(cP==0); cP = cP + 64; cP(ind) = 32; M = char(cP);hill.m% script to encode a message P with matrix E cP = code2(P); l = length(cP); % number of characters if (mod(l,2)==1) % l is odd cP(l+1)=0; % add a 0 to the end l = l + 1; % increase length by one end cP = reshape(cP,2,l/2); % changes cP into 2xM eP = mod(E*cP,27); % peforms the encoding (mod-27) eP = eP(:)'; % converts back to a row matrix C = decode2(eP); % converts to text