Class Notes (809,279)
Mathematics (837)
MATB24H3 (13)
Lecture

# Lecture10.pdf

8 Pages
181 Views

School
University of Toronto Scarborough
Department
Mathematics
Course
MATB24H3
Professor
Sophie Chrysostomou
Semester
Winter

Description
University of Toronto at Scarborough Department of Computer & Mathematical Sciences MAT B24S Fall 2011 Lecture 10 Cryptography Hill Ciphers This lecture will demonstrate a method of encoding and decoding mes- sages. Most of what was studied in this course so far will be used. This is the study of ﬁelds of the form Z where p is a prime, matrices, gaus- p sian elimination of matrices with entpies from Z , linear independence, linear transformations and change of basis matrices. The study of encoding and decoding secret messages is called cryptog- raphy. Codes are called ciphers. Uncoded messages are called plaintext and coded messages are ciphertext. The process of writing a plaintext into a ciphertext is called enciphering. The process of converting a ciphertext into plaintext is called deciphering. The process that we are going to study is called Hill Cipher after Lester S. Hill who introduced it. 1 Enciphering Using Hill n-cipher We will start by assigning the following numbers to the letters, period, comma and space as follows: A B C D E F G H I J K L M N O P Q R S 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 T U V W X Y Z . , 20 21 22 23 24 25 26 27 28 0 1 Note that we have used the numbers from 0 to 28. These are the elements of Z29 Note also that 29 is a prime and from our previous observations this implies that Z is a ﬁeld. (MATC15) Thus, every nonzero element has a 29 multiplicative inverse. Using the Hill n-cipher, to encipher we use the following steps: 1. We choose an invertible n × n matrix with entries from Z 29 . Call this matrix A. This matrix is known to the parties ciphering and deciphering text. 2. We divide the plaintext letters into groups of n letters each, adding a dummy letter to ﬁll the last group if necessary. Next we replace each letter by its numerical equivalent using the above table. Thus forming groups of n numbers each. I.e. v i,1 ,i,2 , v i,nare the n numbers of the ith group. 3. Each group of numbers v , i,1··i,2 v i,nfrom above forms a column   v i,1 v i, vector vi=  . . We will call the vector v i plaintext vector and  .  v i,n Av i u iis corresponding ciphertext vector. 4. Convert each ciphertext vector into its alphabetic equivalent. 5. Send the ciphertext message. 2 Deciphering To decipher we use the following steps: 1. Receive the ciphetext message. 2. Divide the ciphertext letters into groups of n letters each, adding dummy letters to ﬁll the last group if necessary . Next, replace each letter by its numerical equivalent using the above table. Thus forming groups of n numbers each. I.e. u , u ,··· , u are the n numbers of the ith i,1 i,2 i,n group. 2 3. Each group of n numbers u , u ,··· , u from above forms a column   i,1 i,2 i,n ui,1  ui.2 vector ui=  . . Then the plaintext vector ii v = Aui.  .  ui,n 4. We ﬁnally replace each of the numbers in the plaintext vectors with their alphabetic equivalents to get the plaintext. Originally Hill cipher was used with 26or Z27 Since 26 and 27 are not primes, they have nonzero elements that have no multiplicative inverses. This may pose some problems. That is why I use 29. In doing all the work in Z29 it is usefull to have the multiplicative inverses of all the nonzero elements. Here they are: a 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 −1 a 1 15 10 22 6 5 25 11 13 3 8 17 9 27 2 20 12 21 26 20 21 22 23 24 25 26 27 28 16 18 4 24 23 7 19 14 28 ▯ ▯ 5 2 EXAMPLE: Use the Hill 2-cipher with A = 3 8 to encipher the plain- text ”I like linear algebra”. Solution: 1. First ensure that the matrix A is indeed invertible and ﬁn. A ▯ ▯ ▯ ▯ ▯ ▯ ▯ ▯ ▯ 5 2 ▯ 1 0 6R1 1 12 ▯6 0 R2+28R1 1 12 ▯ 6 0 3 8 ▯ 0 1 −10R 1 22 ▯0 10 −−−−−→ 0 10 ▯ 23 10 2 ▯ ▯ ▯ ▯ ▯ ▯ 3R2 1 12 ▯ 6 0 R1+17R2 1 0 ▯19 17 −−−→ 0 1 ▯11 1 −−−−− → 0 1 ▯11 1 ▯ ▯ Thus A is invertible and A1= 19 17 11 1 3 2. Then the plaintext is divided into groups of 2 letters each. This is done to their equivalent numerical values also: I L I K E L I N E A R 9 0 12 9 11 5 0 12 9 14 5 1 18 0 A L G E B R A 1 12 7 5 2 18 1 0 Since there are an odd number of numbers above, a dummy variable is placed at the end with numerical value 0. 3. The ▯o▯lowing▯ve▯tors a▯e ▯btaine▯: ▯ ▯ ▯ ▯ ▯ 9 12 11 0 9 5 v1= , v2= , v3= , v4= , 5 = , 6 = , 0 9 5 12 14 1 ▯ ▯ ▯ ▯ ▯ ▯ ▯ ▯ ▯ ▯ v = 18 , v = 1 , v = 7 , v = 2 , and v = 1 . 7 0 8 12 9 5 10 18 11 0 4. Each of the above vectors is then multiplied with A to get Av = u i i where: ▯ ▯ ▯ ▯ ▯ ▯ ▯ ▯ ▯ ▯ ▯ ▯ u1= 16 , u2= 20 , u3= 7 , u4= 24 , u5= 15 , u6= 27 , 27 21 15 9 23 23 ▯ ▯ ▯ ▯ ▯ ▯ ▯ ▯ ▯ ▯ 3 0 13 17 5 u7= , u8= , u9= , u10= , and 11= . 25 12 3 5 3 5. These numbers are then placed next to each other along with their alphabetical equivalent: 16 17 20 21 7 15 24 9 15 23 27 23 3 25 0 12 13 3 17 5 5 3 P Q T U G O X I O W . W C Y L M C Q E E C Thus the ciphertext is : PQUVGOXIOW.WCY LMCQEEC 6. This is send to the party that we want to send the message to and who knows A and A−1. 4 Now the person receiving the ciphertext message must decipher it. This is how it is done: 1. Receive the ciphertext message. 2. Next we divide the ciphertext into grou
More Less

Related notes for MATB24H3

OR

Don't have an account?

Join OneClass

Access over 10 million pages of study
documents for 1.3 million courses.

Join to view

OR

By registering, I agree to the Terms and Privacy Policies
Just a few more details

So we can recommend you notes for your school.