Many Messages

Loading...

Do curso por University of California San Diego

Number Theory and Cryptography

80 classificações

University of California San Diego

Number Theory and Cryptography

80 classificações

Curso 4 de 5 em 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.

Na lição

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

Conheça os instrutores

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

What if A and B want to send many messages to each other.

For example, Alice wants to send several messages to B?

Turns out that they need a separate secret key for each sent message.

Otherwise, Eve can decipher messages at least partially.

Now this is what actually happened in practice.

There was a so-called Project Venona by the US and due to this project,

the US deciphered thousands of Soviet Union secret messages that they

sent during the World War II in 1941 to 1945.

Why that happened?

Because, of course,

the Soviets knew that they need to cipher

their messages and they used what we've just described,

called One Time Pad,

to cipher those messages.

But, the process of creating a random key

and exchanging it with another party was pretty laborious.

And the demand for sending secret messages during the war exploded and so,

they just didn't catch up with a lot,

and so, some of the keys were re-used.

So, what was meant as a One Time Pad,

just one key to encode one message,

was actually used as a many-time pad.

And then, if you used the same key to encode

several messages in plaintext Russian or in plaintext English,

it turns out that the eavesdropper can decipher at least part of it.

Let's see how that happens.

So, let's just assume that instead of using the same key once,

we use it just two times.

And so, what will Eve see during these two communications?

First, she will see the ciphertext, c1,

which is message m1 encoded with a key,

k. Then, she will see the ciphertext, c2,

which is the message m2 encoded with the same key,

k. What she can compute then is the XOR of c1 and

c2 which is equal to m1 XOR_k, XOR_k, XOR_m2.

And you notice that I've changed places of m2 and k in this operation,

but obviously, XOR operation is symmetric so this doesn't change anything.

And in the middle, we get k_XOR_k which is zero.

And you can just remove zero because nothing changes when you XOR something with zero.

So, in the end what Eve will get is the XOR of the initial two messages, m1 and m2.

And it turns out that if m1 and m2 are,

for example, plain English,

it is possible to at least partially decipher both given just m1_XOR_m2

because there is some redundancy in the encoding of English language.

So, for example, if we know the XOR of m1 and m2 and somehow,

we know the ith character of m1,

character and position i, of course,

we can already decipher the corresponding ith character of m2

because we know the m-prime which is equal to m1_XOR_m2.

And this m-prime consists of corresponding source of bits on each position,

the first position, second position,

and up to Nth position.

And on the ith position,

m-prime_i is the XOR of m1i and m2i.

So, to compute m2i,

we can XOR back the known bit m-prime_i and the known bit m1i.

So if we just know the XOR of two messages and some bit in one of them,

we immediately know the same bit in another one.

How does this help?

How do we learn even one bit of one message?

Well, it turns out that, for example,

plain English messages contain lots of spaces of this.

So, they contain some letters,

maybe some punctuation marks,

some numbers and lots,

lots of spaces between words.

Typically, computers store messages of plaintext in the so-called ASCII code.

And it turns out that exclusive OR of any English letter with

a space in this ASCII code is always different from exclusive OR of any two letters.

So, if at some position,

one of the messages contains a letter and another one contains an space,

then you will be always able to distinguish

this situation from the situation when there are two letters on this position,

and of course, from this situation,

when there are two spaces in this position, because, why?

Well, because if you XOR two spaces,

you just get zero,

and this is different from what you get if you

XOR two different characters being spaces or letters or anything.

So, you can try to find positions of spaces in both messages,

and using the XOR of the two messages,

you will know what are the positions where there

is a space in one message and a letter in another one.

And then, you just have two possibilities of where

is the space and what is here in another message.

And doing that, you will decode the letters and the corresponding positions.

And another thing, you can actually use is,

that plaintext English messages are probably going

to also contain some very common words,

like the word "the" in the English language is the most frequent word.

And it is very likely that one of the messages will

contain "space the space" in some place,

and another message will contain some other words,

probably some letters, in these positions,

and you will be able to guess that again.

These five subsequent positions,

we got space, the, and space.

And this way, you will be able to gradually decode some,

or at least some, of the positions in both of the messages.

Even better, if you have not just two messages encoded with the same key,

but many, like 10,

and you'll actually do this yourself as an exercise.

So to conclude, the One Time Pad using XOR enables secure communication.

And B, to do that,

must share some secret key, k,

and use the XOR to encode plaintext message,

m, with secret key, k,

and to get ciphertext, c. And,

they need to use each key to encode only one message,

otherwise, the One Time Pad becomes two-time pad or many-time pad and it

becomes possible to decipher at least part of the message.

And, if they use the key just once,

and this key is really random,

then Eve cannot tell anything new about the message being

sent apart from what she already knew about this message before it was sent.

But the question is, in the end, how to

efficiently establish a common secret key in the first place?

Because A and B have to communicate somehow to do that,

and Eve will be able to eavesdrop on everything they do within.

So, in the next lecture,

we're going to study an algorithm called RSA,

which allows you to do exactly that even though Eve is listening.

Explore nosso catálogo

Registre-se gratuitamente e obtenha recomendações, atualizações e ofertas personalizadas.

O Coursera proporciona acesso universal à melhor educação do mundo fazendo parcerias com as melhores universidades e organizações para oferecer cursos on-line.

© 2018 Coursera Inc. Todos os direitos reservados.

Baixar na App Store

Baixar no Google Play