Algebra Applications: Encryption

[Music]

Narrator: We live in a world of coded information.

DNA is nature's code for creating new life.

Language is humanity's means of coded communication.

But DNA and language are public codes.

They are not encrypted.

Anyone who knows these languages can decipher strands

of DNA or sentences on a page.

But sometimes it's necessary to encode a message.

In World War II encrypted messages were constantly used

to communicate to troops in the field.

Today we use encrypted messages on the Internet so

often that we take it for granted.

The reason that information is encrypted is because it is

private information that is conveyed through public

information systems like telephone lines or

Internet connections.

Private information can include anything from banking

data to top-secret government intelligence.

So the practice of encoding messages has always been

important, but it has become a growing branch of mathematics

and linear systems are a way of encrypting information.

A cipher is a means of encrypting a message.

One of the simplest types of ciphers, called a substitution

cipher, is to replace each letter of the alphabet

with a number.

This chart shows how each letter is replaced

with a number.

The @ symbol is used as a substitution for the

space symbol.

So the message 'invasion at dawn' becomes the following

string of numbers.

Let's use the TI-Nspire to decipher some messages.

Create a new document.

You may need to save a previous document.

Create a spreadsheet.

Go to the top of column A and add the column heading

substitution.

This represents the numerical substitutions that will

be used.

Press ENTER.

We want to generate sequence of numbers from zero to

twenty-six.

The zero will represent a word space, and the numbers one

through twenty-six will represent the letters of

the alphabet.

Press MENU and under DATA select GENERATE SEQUENCE.

At the dialog box input this expression, which will

generate a set of consecutive numbers.

Press TAB to set the starting value at zero.

Press TAB again to set the maximum value.

Tab to OK and press ENTER.

If you scroll down you'll see the list of numbers from zero

to twenty-six.

Now move the cursor to the top of column B.

We want to assign the letters of the alphabet to the numbers

in column A.

In fact, we'll be using the numbers already assigned to

each character on the keyboard by the operating system.

Every computer uses a character set where number

sixty-four to eighty-nine are assigned the letters of

the alphabet.

At the top of column B input the heading alphabet and

press ENTER.

At the formula line input this formula.

The formula takes each value in column A and uses it to

generate the characters from code sixty-four to

eighty-nine.

Press ENTER and you will see twenty-seven characters.

This is your substitution cipher.

Now suppose you get the following encoded message.

Using the substitution cipher the message becomes this.

You can think of the cipher as the alphabet mapped to a

number line.

But this cipher is easy to break.

The numbers and letters are in sequential order.

Once you figure out one of the terms of the sequence then you

can figure out the rest very easily.

So this type of substitution cipher offers low security.

To make it a bit more complex you could take the values in

column A of the spreadsheet and assign them to a function

that generates the same numbers, zero to twenty-six,

but in a scrambled order.

So move to the top of column C and input the

heading encryption.

Press ENTER.

At the formula line you will be inputting a function that

deals with modular arithmetic.

In other words, the function will only generate numbers

from zero to twenty-six.

Input the following formula.

The formula finds all the remainders of twenty-seven

when divided by the term two a plus three.

Press ENTER and you will see the numbers zero to twenty-six

but in a non-sequential order.

Notice that each number in column C is used just once.

This is because of the way the function was defined.

Create a scatter plot of the data in columns A and C.

Press control-I and select a graphs and geometry window.

Press MENU and under graph type select scatter plot.

For the x variable select substitution, and for the y

variable select encryption.

Press MENU, and under WINDOW select zoom fit.

Try to get your screen to look like this.

The graph is beginning to look like a linear system.

Unlike the number line shown earlier this is a

two-dimensional mapping of the alphabet to the

coordinate grid.

The graph shows that the cipher does offer a bit more

security since the numbers are not in sequential order, but

even this encryption can be broken.

For example, take a look at the following

encrypted message.

Even if you didn't have the encryption cipher but

suspected that a substitution cipher was used you could

analyze the message.

Highlight the terms that occur most often.

These will correspond to the most frequently

occurring letters.

The more encrypted messages you could analyze that use the

same cipher the more you could eventually decipher

the message.

So, an additional layer of security could be added and

this involves using a three-dimensional mapping of

the letters to x y z coordinates on the 3-D

coordinate system.

Rather than mapping each letter of the alphabet to a

function, clusters of letters are multiplied by a three by

three matrix.

Let's start with a message that needs to be encoded.

Let's use the encryption cipher to convert the text to

a string of numbers.

Now convert this string of numbers into a series of three

by one matrices, as shown.

Note the last matrix has a three in the final position, a

blank space, since the last letter of the message was in

the second position.

Our additional layer of informational security comes

from taking each of these three by one matrices and

multiplying them by a three by three encoding matrix.

The encoding matrix adds the additional layer of security

that makes it extremely difficult to decipher

the message.

For our encoding matrix we will use this three by

three matrix.

Let's use this matrix to encode our message matrices.

Press control-I to create a new document.

Select one to create a calculator window.

Each of the matrices will be defined as a variable.

Press the catalog button and four to activate the fourth

tab within the catalog.

Use a nav pad to select the icon in the second row that

looks like a three by three matrix.

Press ENTER.

At the dialog box define a matrix that is a one column

and three rows.

Tab to OK and press ENTER.

Input the numbers for the first matrix.

Press the RIGHT ARROW key.

Assign this matrix to variable M1.

Press CONTROL and the VAR button.

You will see an arrow pointing to the right.

Input M1 and press ENTER.

This matrix is now stored in memory.

Continue this process with the other three by one matrices.

You will end up with matrices M1, M2, M3, up to M8.

Pause the video to enter these matrices.

After you have defined the eight message matrices, define

the encoding matrix.

Once again click on the catalog key, select the matrix

icon, but this time create a three by three matrix.

Tab to OK and press ENTER.

Fill out the matrix with the numbers from the

encoding matrix.

Store this matrix in a variable called encode.

You are now ready to encode the matrices.

You will be multiplying each three by one matrix by the

encoding matrix in this form.

Furthermore, you will assign the product to a new matrix in

this form.

Encode all eight matrices and assign them the

appropriate variables.

Pause the video to complete the multiplication.

Once you have multiplied the matrices and stored the

products you can see the result of your work.

Your results should look like this.

So now you know how to encode a message with a high degree

of security based on using an encoding matrix, but how do

you use it to decode a message?

Suppose you got the following encoded message.

How do you work backward to decode it?

First, take the message and turn it into a series of three

by one matrices.

Start each matrix in the calculator as a variable.

Use a different variable, as shown.

Rather than encoding the matrix with the three by three

matrix used earlier, you will use the inverse of the

encoding matrix.

So define a new variable as shown.

Now multiply the three by one matrices by the decoding

matrix, as shown.

Pause the video to multiply the encoded message matrices by

the decoding matrix.

Your decoded message yields this set of numbers.

Using the original substitution cipher yields

this message.

The matrix-based encoding system maps the text of the

message to a linear system in three-dimensional space, a

very effective means of encrypting information.