Class Notes
(809,279)

Canada
(493,607)

University of Toronto Scarborough
(30,820)

Mathematics
(837)

MATB24H3
(13)

Sophie Chrysostomou
(12)

Lecture

# Lecture10.pdf

by
OneClass8101

Unlock Document

University of Toronto Scarborough

Mathematics

MATB24H3

Sophie Chrysostomou

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