Cryptography

Loading...

From the course by University of California San Diego

Number Theory and Cryptography

74 ratings

University of California San Diego

Number Theory and Cryptography

74 ratings

Course 4 of 5 in the Specialization Introduction to Discrete Mathematics for Computer Science

We all learn numbers from the childhood. Some of us like to count, others hate it, but any person uses numbers everyday to buy things, pay for services, estimated time and necessary resources. People have been wondering about numbers’ properties for thousands of years. And for thousands of years it was more or less just a game that was only interesting for pure mathematicians. Famous 20th century mathematician G.H. Hardy once said “The Theory of Numbers has always been regarded as one of the most obviously useless branches of Pure Mathematics”. Just 30 years after his death, an algorithm for encryption of secret messages was developed using achievements of number theory. It was called RSA after the names of its authors, and its implementation is probably the most frequently used computer program in the word nowadays. Without it, nobody would be able to make secure payments over the internet, or even log in securely to e-mail and other personal services. In this short course, we will make the whole journey from the foundation to RSA in 4 weeks. By the end, you will be able to apply the basics of the number theory to encrypt and decrypt messages, and to break the code if one applies RSA carelessly. You will even pass a cryptographic quest! As prerequisites we assume only basic math (e.g., we expect you to know what is a square or how to add fractions), basic programming in python (functions, loops, recursion), common sense and curiosity. Our intended audience are all people that work or plan to work in IT, starting from motivated high school students.

From the lesson

Cryptography

Modern cryptography has developed the most during the World War I and World War II, because everybody was spying on everybody. You will hear this story and see why simple cyphers didn't work anymore. You will learn that shared secret key must be changed for every communication if one wants it to be secure. This is problematic when the demand for secure communication is skyrocketing, and the communicating parties can be on different continents. You will then study the RSA cryptosystem which allows parties to exchange secret keys such that no eavesdropper is able to decipher these secret keys in any reasonable time. After that, you will study and later implement a few attacks against incorrectly implemented RSA, and thus decipher a few secret codes and even pass a small cryptographic quest!

Cryptography7:14

One-time Pad4:33

Many Messages7:40

Meet the Instructors

Alexander S. Kulikov
Visiting Professor
Department of Computer Science and Engineering
Michael Levin
Lecturer
Computer Science
Vladimir Podolskii
Associate Professor
Computer Science Department

Hi, in this module,

we're going to study cryptography.

At first, we'll learn how to establish secure communication in case both parties,

Alice and Bob, share some secret key.

What is the standard way to do that?

Then, we will study the most frequently used cryptographic algorithm called RSA which

allows Alice and Bob exchange some information

even if they don't share any common secret key initially.

And in particular, it allows them to exchange

their secret keys using this way of communication.

And in the end, we will learn that still there are

so many subtle details and so many unexpected attack angles on RSA that of course,

there are some secure implementations,

but if you try to implement RSA yourself and meet some of those details,

the cipher becomes breakable again.

And in the end,

you will actually train to break some secrets skills yourself. So let's start.

Cryptography advanced the most during the last two World Wars.

That's because everybody was spying on everybody and still

they needed to send some secret communications like attack or don't attack.

And the German invented the Enigma machine.

This is the photo of a four-rotor Enigma machine

which was invented and used during the World War I.

And then, the allies during the World War II,

led by Alan Turing,

built a computer which broke the Enigma codes.

It tried all possible combinations of the rotors,

and then tried to decipher the ciphertexts intercepted by the counterintelligence,

and if what was on the output was looking like English plaintext,

that meant that the cipher was decoded.

Otherwise, it looked like just a random sequence of bits.

After the World War,

it became clear that to be a superpower,

countries need to be able to launch and aim nuclear missiles,

and also, to defend against them.

And the US launched these kinds of radars

which try to detect unrecognized flying objects and alarm about the potential threat.

And this alarm went through one of the first computer networks to

the control center where

the top army officers could make some decisions and react quickly,

thanks to the quick information flow through the computer networks.

And then, the [inaudible] were first who understood the potential of computer networks,

and they appeared in the classrooms.

After that, there appeared some startups and then we got

things that we cannot imagine our life today

without like cash machines and money transfers,

like e-mail, like online commerce,

and like messengers, one of the latest inventions.

So what is secure communication?

Typically, we describe it as two parties,

Alice and Bob, A and B,

want to exchange some information.

But they always have to assume that there is always

an evil E who is stepping on the wire and listening to everything they say to each other.

That doesn't depend really on what is the channel of communication.

If they're just standing right next to each other,

someone could be eavesdropping.

If they're talking over the phone,

somebody could be listening to the phone line.

So anyway, they have to assume that everything they say explicitly is known to E.

The only thing they can keep in secret is

something that they keep to themselves and don't tell to anyone.

And so, for example,

Alice wants to send Bob some message like yes or no,

or attack, don't attack, something like that.

They can invent some cipher like change

word yes to swordfish and change word no to buddy.

But if this cipher,

if this algorithm is known,

then basically, it means that E can do the deciphering herself also.

And if this cipher needs to be known to both A and B,

then probably, they have to at some point tell it to each other,

so the algorithm will become known.

So, in a sense,

this type of communication with the algorithm which is public,

doesn't work as a secure communication.

And typically, in cryptography,

we assume that all algorithms are publicly known.

Because it is too hard to exchange the whole algorithm

without it becoming at least partially known to a third party.

So, the way we can establish some secure communication, first,

in the presence of some secret key is the

following: we assume that A wants to send B some message,

and message m is a plain text message.

It can be encoded as a sequence of bits,

m₁, m₂, and up to mn, and bits.

And then they also have a common secret key k,

which has the same length in terms of bits.

So, it's k₁, k₂, and up to kn.

Those are all bits.

And we assume that somehow both A and B know this key,

but they don't have to send it over the network or to communicate it in any way,

they just both know it.

And then the standard way to encrypt the message is to compute ciphertext c,

which is computed as m ⊕ k,

where ⊕ or exclusive or,

is a bitwise operation on the messages of

the same length which does very simple thing for any position i,

in both message and the key.

It takes the corresponding bits mᵢ, and kᵢ,

and it sums them up,

modulo two, it just takes the remainder modulo two.

So, cᵢ is also a bit.

It is either zero or one.

Because it is a remainder modulo two.

And it turns out that if we add the secret key to message m,

not only the message itself changes,

and if cannot recognize what was in the initial text,

if we select these secret key in a special way,

it will be not possible for E to learn anything about the initial message.

Not just decipher the whole message,

but she won't be able even to guess one bit of message m with some increase probability.

Why is that and how all that works?

We will learn in the next video.

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.

© 2018 Coursera Inc. All rights reserved.

Download on the App Store

Get it on Google Play