This course will introduce you to the foundations of modern cryptography, with an eye toward practical applications.
Introduction
Loading...
From the course by University of Maryland, College Park
Cryptography
511 ratings
From the lesson
Week 1
Introduction to Classical Cryptography
Meet the Instructors
Jonathan KatzProfessor, University of Maryland, and Director, Maryland Cybersecurity Center
Maryland Cybersecurity Center
[SOUND].
Welcome back.
Recall from the first lecture that historically speaking,
cryptography was exclusively concerned with ensuring secrecy of
the communication between two parties.
This put us squarely in the context of encryption.
Which is where we'll begin our study of cryptography.
In addition, classical cryptography always assumed that
the two communicating parties shared some secret information.
What we'll a key, an event for their communication.
This put us in the setting of what's known as private-key cryptography.
This setting is also variously known as the secret-key, shared-key or
symmetric-key settings for reasons that should become clear.
But I'll try to consistently use the terminology private-key cryptography.
So in the setting of private-key encryption, we have two users.
Often called Alice and Bob.
Who shares some secret information, a key in advance.
When Bob has a message or a plain text that he wants to send to Alice,
he will encrypt that message using the shared-key.
This generates a ciphertext that he sends to
Alice over a public communication channel.
Alice can then decrypt that ciphertext using the shared-key to
recover the original message.
Informally, the security guarantee we want is that
no eavesdropper who can observe the ciphertext sent
across the channel can figure out anything about the underlying message.
On the previous slide, we had two distinct users separated in space.
Private-key cryptography is also commonly used for ensuring secrecy for
a single user communicating with themselves as it were over time.
Here, Bob holds a message that he wants to store safely on his laptop.
As before, Bob can encrypt the message to obtain a ciphertext and
now store that ciphertext on his laptop.
At some later point in time, when Bob wants to recover the message,
he can read the ciphertext from the hard drive.
And then decrypt it using his key to recover the original message.
Here if an attacker steals a laptop or is otherwise able to compromise it, that
attacker should still be unable to learn anything about the underlying message.
I now want to define an encryption scheme more rigorously.
Formally speaking, an encryption scheme is defined by specifying a message space M of
allowable messages.
Along with three algorithms, a key-generation algorithm,
an encryption algorithm and a decryption algorithm.
The key-generation algorithm is a randomized algorithm that chooses a key k.
The encryption algorithm takes two inputs.
A key k and a message m in the message space.
It outputs a ciphertext c.
Finally, the decryption algorithm takes as input a key k and a ciphertext c.
It outputs a message m or possible some error.
I want to highlight here some notation I'll be using throughout the course.
I use a left arrow to denote assignment to the output of
an algorithm that might be randomized.
Meaning that the output of the algorithm may be different,
even when run twice on the same set of inputs.
I use a colon equals to denote an assignment to
the output of a deterministic algorithm.
So in this case, this means that we're allowing encryption to
possibly be randomized, whereas we're assuming that decryption is deterministic.
I use a single equal sign to denote mathematical equality
in contrast to assignment.
Any encryption scheme is required to satisfy the following basic
correctness requirement.
For any m message m in a message base and
any key k output by the key generation algorithm.
If we encrypt m using k to obtain some ciphertext and then decrypt that
cypher text using the same key, we should get back the same message we started with.
I want to illustrate all of this using a simple example of a historical encryption
scheme called the shift cipher.
Consider encrypting regular English text.
We will identify English letters with the numbers from 0 to 25.
So a will be associated with 0, b with 1 and so on.
The key k will be an integer in the range from 0 to 25.
To encrypt a message m using the key k,
we seem to shift every letter of the plaintext by k positions.
Wrapping around at the end of the alphabet.
So for example, if we encrypt the plain text,
hello world using the key t, which, which corresponds to two.
Then we simply shift each letter of the plain text forward by two positions.
For example, h becomes j, et cetera.
Decryption will simply reverse the process by shifting backward.
Before defining the scheme more formally, I want to introduce some notation for
modular arithmetic that we'll see again later on in the course.
You're all probably used to the, the notation x equals x prime mod N.
Which means that x and x prime have the same remainder when divided by n.
Or equivalently, that n divides x minus x prime.
In contrast to this, I use the notation bracket x mod N
to denote the remainder of x when divided by N.
That is the unique value x prime in the range of 0 to N minus 1.
Such that x is equal to x prime mod N.
Just to illustrate,
we have 25 is equal to 35 mod 10 because they both have the same remainder.
But 25 is not equal to bracket 35 mod N, because bracket 35 mod N is equal to 5.
Now we can define the shift cipher formally.
The message space M will the set of all strings over
the lowercase English alphabet.
Note that we do not handle uppercase letters.
Nor do we handle any non-alphabetic characters like numbers,
spaces or punctuation.
Our key generation algorithm will choose a uniform key in the range from 0 to 25.
This means that each value between 0 and 25 is chosen with equal probability.
Now to encrypt a message consisting of the characters m1 through mt, using the key k.
We output the ciphertext, c1 through ct.
Where each character ci is computed as mi plus k mod 26.
As we have said, decryption just reverses this process.
So that the decryption of a ciphertext consisting of character c1 through ct
using the key k is done, by simply outputting the message consisting of
the characters m1 through mt.
Where each mi is the c1 minus k mod 26.
I leave it to you to convince yourselves that correctness holds.
Is the shift cipher secure?
It should be pretty clear that it's not.
Note that there are only 26 possible keys.
So given a ciphertext,
an attacker can simply try decrypting that ciphertext using every possible key.
At a minimum, this will narrow down the plaintext to one of only 26 possibilities.
More likely though,
only one of those possibilities will make sense as normal English text.
And that will immediately let the attacker identify that
possibility as the true message.
For example, imagine you've intercepted the ciphertext displayed here.
If you tried decrypting using every possible value of the key.
You'll get a list containing 25 strings of gibberish plus one that says, hello world.
That tells you exactly what message was encrypted to give the ciphertext.
Something implicit in the attack I just described is that the attacker is
assumed to know the encryption scheme the communicating parties are using.
This is known as Kerckhoffs's principle,
which states that the encryption scheme being used is not to be considered secret.
But instead, the only secret information is the key shared by the parties.
This implies that the key must be chosen randomly.
If not, then the attacker knows it.
And furthermore, that this key must be kept secret by the parties
sharing that key.
Sometimes, people argue that Kerckhoff's principle doesn't make sense.
And that it might give better security to also keep the encryption scheme
itself secret.
There are several arguments against this line of thinking.
First, it is much easier to maintain secrecy of a short key,
rather than a more complex algorithm.
Similarly, it's easier to change the key shared by two parties than to
change the algorithms they're using.
Perhaps most importantly,
allowing the details of the encryption scheme to be public.
Means that we can develop standardized encryption schemes that anyone can use.
This makes it much easier for encryption schemes to be deployed and adopted.
And also ensures that these schemes receive public scrutiny.
Thereby increasing our confidence in their security.
The key space of an encryption scheme is just the set of all possible keys that
can be output by the key generation algorithm.
An important take away point from our analysis of the shift cipher is that in
order to be secure, an encryption scheme must at a minimum have a key
space large enough to prevent a brute force exhaustive search attack.
Like the one we just described.
As we will see however, having a large key space does not necessarily guarantee that
an encryption scheme is secure.
Explore our Catalog
Join for free and get personalized recommendations, updates and offers.
Coursera provides universal access to the world’s best education,
partnering with top universities and organizations to offer courses online.
© 2019 Coursera Inc. All rights reserved.
