Hastad's Broadcast Attack

Loading...

來自 University of California San Diego 的課程

Number Theory and Cryptography

67 個評分

University of California San Diego

Number Theory and Cryptography

67 個評分

課程 4（共 5 門，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.

從本節課中

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!

RSA Cryptosystem14:38

Simple Attacks5:16

Small Difference5:53

Insufficient Randomness7:42

Hastad's Broadcast Attack8:16

More Attacks and Conclusion5:33

與講師見面

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

Hi. This is our last video on

the cryptography module and we're going to study the Hastad's broadcast attack.

It's a very interesting different types of attack.

First, we studied some simple attacks based on wrong implementation of RSA,

or some prime numbers being smaller or difference between them being small,

and on some insufficient randomness which turned out to be a problem.

This is an attack from a completely different angle which comes from the fact that

sometimes we want to send the same message to many different recipients,

to broadcast this message.

If we do that not careful enough,

then it can be a problem.

Someone can break our cipher.

So Hastad came up with an attack in case Bob sends

the same message to several recipients using their public keys.

It uses the fact that it's basically the same message,

and it doesn't change at all.

It doesn't use any randomness,

and that is key for the attack.

It works in a very general case,

but we will consider a very simplified case as an example of how we

can break this code if the same message is broadcasted.

Let's imagine that Bob wants to send the same message to Alice, Angelina, and Adriana.

So he has a message, m, and he wants to send this message to all three.

But, of course, he doesn't want for anyone to

listen and he wants to send this message as a secret.

So instead, he will use the RSA algorithm to compute a three cipher text.

Cipher text one will be m to the power of e1 modulo N1,

where N1 and e1 is the public key that Alice provides to send messages to her.

C2 is equal to m to the power of e2 modulo N2,

and it is different.

It is using a different public key N2, e2.

And the same with the third message m to the power of e3 modulo N3.

So in our simplified case,

we assume that all e1,

e2, and e3 turn out to be equal to 3.

This potentially could happen.

What happens in this case is that c1 is equal to m cubed modulo N1,

c2 is equal to m cubed modulo N2 and c3 is equal to m cubed modulo N3.

So what happens next is that the greatest common user

of any two different public keys is equal to 1.

Well, otherwise we just learned in the previous video,

if some two public keys are not coprime,

then we can factor each of them and anyway decrypt the messages.

So we assume that we somehow avoided this problem.

These public keys don't have any common users. They are coprime.

As they are pairwise coprime,

we can use the Chinese Remainder Theorem.

In particular, we're going to to use it to construct such c that,

of course the c is a remainder modulo of the product of

these three modules between 0 and 1, and 2, and 3.

And also c has the same remainder modulo N1 and c1,

the same remainder modulo N2 and c2,

and the same remainder modulo N3 and c3.

This is not just possible,

this is possible and can be done using an algorithm

we learnt in the previous module which is based on the extended Euclid's algorithm.

So, you first construct the number with the required remainders modulo N1 and N2,

and you get some remainder modulo and N1

times N2 and then using the fact that N1 and N2 is coprime with N3,

you construct another number which has the required remainder module N1 times N2,

and the required remainder c3 modulo N3.

In the end you get a remainder modulo N1N2N3 which

has required remainders modulo N1, N2 and N3.

So, if we use our algorithm to construct such c,

then it turns out that c will be equal to m cubed modulo N1N2N3.

Why is that? Well, again,

by Chinese remainder Theorem.

Because c gives the same remainder as modulo N1N2N3 as m cubed from the above equations.

And this means as N1N2N3 are pairwise coprime,

that c and m cubed have the same remainder modulo the product of these modules.

Now we know that c is equal to m cubed modulo N1N2N3,

and also we know that c is between 0 and

N1N2N3 because c is just the remainder module of this product.

And also, m cubed is also between 0 and N1N2N3. Why is that?

Well, obviously it's non negative,

but also m is a message sent using public keys N1, N2 and N3.

So m must be less than N1,

N2 and N3 just to be used in the RSA scheme.

As m is less than each of these modules,

by multiplying these inequalities we get that m cubed is less than their product.

So, these two numbers have the same remainders modulo product N1N2N3,

and they are between 0 and N1, N2 and N3.

So they are both remainders modulo of this product.

And it means that these numbers are just equal because there are

no two different remainders which are equal.

So c is equal to m cubed in the end.

And then if we now see,

we'll construct it using Chinese Remainder Theorem and Euclid's algorithm,

then we can just decode m by completing the regular cube root,

not just some fancy modular cube root,

but just the regular cube root of an integer number c,

to get m. This is the way that Hastad's attack works in this simplified case.

So we just need to apply extended Euclid's algorithm to construct

number c and then we just compute the regular cube root.

We can do that in floating point arithmetic, but then,

just round up to the closest integer and it will turn out to be the exact message

that someone sent if intercepted the cipher text.

So broadcasting the same fixed message is a problem,

and Hastad's original attack works not just with

the case when all e1,e2 and e3 are equal to 3 and when there are three recipients.

It works even with bigger and different Ei and with different number of recipients,

if there is enough recipients to apply this attack.

The solution to avoid this attack

completely is to add a random padding to m before encryption.

Why that works, because then,

it is impossible to compute m using all the cipher text just

in some deterministic way because each ci includes some random part

apart from m and so there can not be

any deterministic algorithm that recovers the exact m out of c1, c2 and c3.

So c1, c2 and c3 share some common information in the form of m,

but they also differ by some random bits

which we added to m before encryption and so we can not

actually use such kind of algorithms to recover m. So general idea is,

it's a good thing to always apply some randomness,

to always leave some amount of randomness in

your message before encrypting it because it allows to avoid many,

many different attacks from the easy one with

the limited initial message set which was started in the beginning to

this advanced Hastad's attack which also is

not applicable if you add enough randomness to the messages before encrypting them.

探索我們的目錄

免費加入並獲得個性化推薦、更新和優惠。

Coursera 致力於普及全世界最好的教育，它與全球一流大學和機構合作提供在線課程。

© 2018 Coursera Inc. 保留所有權利。

通過 App Store 下載

通過 Google Play 獲取