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.