WEBVTT
00:10.720 --> 00:11.860
Good morning.
00:13.860 --> 00:16.820
Next session on Algorithms for Internet Applications.
00:16.940 --> 00:18.660
Hope you had a nice Christmas break.
00:19.360 --> 00:21.620
And came well into the new year.
00:22.460 --> 00:23.940
I wish you all a happy new year.
00:24.240 --> 00:29.520
And we will have a few more lectures on Algorithms for Internet
00:29.520 --> 00:30.660
Applications.
00:31.620 --> 00:35.400
Currently we are in the chapter on cryptographic algorithms.
00:36.180 --> 00:40.760
Hope that you all had time to work on the assignment, the programming
00:40.760 --> 00:41.480
assignment.
00:41.920 --> 00:44.500
I don't know how you got around to that.
00:46.640 --> 00:53.040
You know that the registration for the exam, for the final exam, is
00:53.040 --> 00:53.800
starting now.
00:54.420 --> 00:58.600
So if you want to take part in the final exam at the end of the term,
00:58.700 --> 01:03.780
you should register for the exam as in the usual locations where you
01:03.780 --> 01:07.800
have to register depending on the type of studies you are in.
01:07.800 --> 01:13.680
Okay, and also the bonus exam, the registration for that ended at the
01:13.680 --> 01:14.460
end of last year.
01:14.580 --> 01:19.720
So I hope that you all registered and that you will pass all these
01:19.720 --> 01:22.320
exams in a very good way.
01:23.260 --> 01:25.420
So, what did we do in this chapter?
01:25.640 --> 01:32.100
We looked at all kinds of scenarios for secure communication or all
01:32.100 --> 01:39.360
kinds of potential attacks on security in communication active and
01:39.360 --> 01:39.760
passive.
01:39.900 --> 01:41.540
Passive and active attacks.
01:41.780 --> 01:47.900
We looked at, well, the cryptographic approaches to make the
01:47.900 --> 01:49.620
communication channels more secure.
01:50.580 --> 01:54.160
Showed you the simple methods for encryption.
01:54.400 --> 01:59.820
CaesarCypher, TableCypher, VisionaireCypher, OneTimeTab, and the
02:01.080 --> 02:08.680
encryption using random number generators using storing of a binary
02:08.680 --> 02:10.600
sequence with a binary method.
02:10.840 --> 02:16.500
And then simple storing again to have the original, to get the
02:16.500 --> 02:18.540
original plain text.
02:18.660 --> 02:20.520
So that's a very simple approach.
02:20.720 --> 02:24.320
And then we also looked at the transposition scheme.
02:24.440 --> 02:27.940
I showed you the BES algorithm, how that's working.
02:27.940 --> 02:33.560
And the major part there is the Feistel round, which has the nice
02:33.560 --> 02:36.760
property that you can use both ways for encryption and decryption.
02:38.100 --> 02:41.900
Again, due to the properties, certainly of the structure, but also of
02:41.900 --> 02:44.240
the storing operations.
02:45.020 --> 02:52.320
And we looked more closely into the particular ingredients of that
02:52.320 --> 02:53.220
Feistel round.
02:54.460 --> 02:58.840
And there the S-box is a particular important part.
03:00.100 --> 03:03.260
Showed you how that has been designed.
03:03.480 --> 03:08.160
I made a few remarks on cryptanalytic attacks on BES.
03:08.720 --> 03:16.240
And then this, I think that was the last lecture last time, or the
03:16.240 --> 03:17.740
last slide last time.
03:18.240 --> 03:23.200
So I showed you that certainly you can try to attack cryptographic
03:23.200 --> 03:23.820
algorithms.
03:23.820 --> 03:27.980
In particular, there have been massive attacks on BES because it was
03:27.980 --> 03:29.620
the standard cryptographic algorithm.
03:30.540 --> 03:34.940
And the important point is that there are so-called side-channel
03:34.940 --> 03:39.940
attacks, where you have possibilities just by looking at, for example,
03:40.080 --> 03:45.500
power consumption or things like that, you can find out what kind of
03:45.500 --> 03:48.380
information is processed internally.
03:48.980 --> 03:55.100
And so that way you can find out information that was supposed to be
03:55.100 --> 03:55.380
secret.
03:56.400 --> 04:04.260
So, things have to be modified and the consequence was that there were
04:04.260 --> 04:08.960
a few more... that other algorithms have been designed.
04:09.160 --> 04:14.620
I will show you later today the new algorithm AES, the advanced
04:14.620 --> 04:21.980
cryptic standard that has been selected in a competitive round of
04:21.980 --> 04:27.260
elections in the beginning of this century.
04:29.060 --> 04:31.160
BES is not completely phased out.
04:31.300 --> 04:32.740
Triple DES is still there.
04:33.660 --> 04:40.600
And the problem is that symmetric methods have some inherent problems
04:40.600 --> 04:43.600
that have to be considered if you look at cryptographic methods.
04:44.360 --> 04:50.180
One of the problems is that if you look at the requirements that you
04:50.180 --> 04:53.420
have, you have many persons who would like to communicate.
04:54.040 --> 04:58.260
And if you have just communication between all those different
04:58.260 --> 05:03.660
persons, if you have n persons, then you need n different, or n-1
05:03.660 --> 05:07.500
different keys just to communicate between one person and all the
05:07.500 --> 05:07.840
others.
05:08.860 --> 05:14.680
So, if you have communication between all of them, then obviously you
05:14.680 --> 05:19.720
need all of n keys, if you would like to have secure communication
05:19.720 --> 05:23.600
between each pair of persons that are there.
05:23.740 --> 05:29.200
Then you have to find out how to actually exchange the keys, and it's
05:29.200 --> 05:32.960
obviously a problem to do that in a secure way.
05:33.860 --> 05:36.920
And in particular, you would use the key for a longer time.
05:37.500 --> 05:43.780
And if you use the key for a longer time on a cryptographic method, it
05:43.780 --> 05:47.260
means that there are many possibilities to try to attack the
05:47.260 --> 05:52.880
communication, because you have many choices of looking at encrypted
05:52.880 --> 05:57.440
text to find out the original plain text.
05:57.680 --> 05:59.960
So, these are things that have to be considered.
06:00.220 --> 06:04.120
And so, there is an alternative approach for the public key
06:04.120 --> 06:08.760
cryptosystem, which at first sight is strange, because how can
06:08.760 --> 06:13.200
something that's supposed to be private and secure be done in a public
06:13.200 --> 06:13.900
way?
06:14.140 --> 06:18.260
So, public key looks like a contradiction in itself.
06:18.480 --> 06:23.680
So, the idea is that every person has her own public key to be used
06:23.680 --> 06:25.900
for sending her encrypted messages.
06:26.260 --> 06:31.420
So, if somebody wants to send a message from some person to another
06:31.420 --> 06:37.340
this is person A and that's person B, then person A has to know the
06:37.340 --> 06:42.420
public key of person B in order to send the message that is encrypted,
06:42.860 --> 06:45.280
and only person B can decrypt that.
06:46.400 --> 06:47.460
So, that's a different approach.
06:47.640 --> 06:51.280
You have a public key for encrypting that everybody can encrypt, but
06:51.280 --> 06:55.740
only by using secret information you can decrypt.
06:56.680 --> 07:01.580
And this is a nice idea, and the naive idea would be to just put all
07:01.580 --> 07:05.660
those public keys inside something which is similar to a telephone
07:05.660 --> 07:10.060
book, and then you can just look up the public key of some person and
07:10.060 --> 07:11.780
send the message and you're fine.
07:12.220 --> 07:16.580
But this is naive, and we will see later on that that is too naive and
07:16.580 --> 07:17.200
will not work.
07:18.640 --> 07:21.080
Nevertheless, public key methods are very important.
07:21.540 --> 07:24.720
The point is you have to know the public key of that person B.
07:25.260 --> 07:28.980
You have to make sure that it is exactly the public key of that person
07:28.980 --> 07:32.660
and not of somebody else, otherwise there would be attacks, which I
07:32.660 --> 07:33.740
will show you a bit later on.
07:34.620 --> 07:39.320
So, every person has their own secret key for decrypting, and the
07:39.320 --> 07:44.820
requirements are that if you have a message which you encrypt using
07:44.820 --> 07:50.080
the public key, then you will decrypt that with the secret key.
07:50.340 --> 07:54.080
So, certainly if you apply the secret key on the encrypted message,
07:54.220 --> 07:57.500
you should be able to retrieve the original message M.
07:59.000 --> 08:03.140
Those pairs S and T should be different for different persons,
08:03.140 --> 08:07.580
different users, so you have to make sure that.
08:07.780 --> 08:12.480
It should not be too expensive to work with such a public key system,
08:12.980 --> 08:14.660
and it should be secure.
08:14.780 --> 08:18.000
That means if you have some information, what kind of information do
08:18.000 --> 08:18.580
you have publicly?
08:18.760 --> 08:24.700
You have the public key, you have the message, and you can see the
08:24.700 --> 08:25.480
encrypted message.
08:25.680 --> 08:28.240
Because if you have a public key, you want to encrypt the message, you
08:28.240 --> 08:31.040
can see how that is transferred, or how that is changed.
08:33.320 --> 08:37.600
So, by knowing the public key, the original message, and the encrypted
08:37.600 --> 08:40.920
message, you should not be able to find out what the secret key is.
08:41.900 --> 08:49.360
And also to derive the secret key S from T should be as hard, or has
08:49.360 --> 08:56.460
to be as hard as decrypting the encrypted message without knowing the
08:56.460 --> 08:57.780
secret key.
08:57.880 --> 09:02.720
So this has to be ensured that it is hard to actually find out the
09:02.720 --> 09:04.000
secret key information.
09:05.280 --> 09:11.840
And then certainly to compute the, or to perform the encrypting, the
09:11.840 --> 09:15.060
decryption, should not be too expensive, because you don't want to
09:15.060 --> 09:18.800
spend too much time for encrypting, for making the communication
09:18.800 --> 09:19.340
secure.
09:20.500 --> 09:28.780
So this looks like quite some difficult list of requirements, and you
09:28.780 --> 09:34.560
will see that this is that this is not, it's really hard.
09:35.140 --> 09:41.900
I just noticed that I explained this requirement for like inadequately
09:41.900 --> 09:47.860
I explained requirement 5, decryption should be simple or should not
09:47.860 --> 09:54.240
be too expensive, and also the key should be generated in a way that
09:54.240 --> 09:55.820
should not be too expensive.
09:56.320 --> 10:01.700
So, although the keys are computed once, then you will use them for
10:01.700 --> 10:08.020
quite some time, and so that should not be too expensive to do that,
10:08.240 --> 10:11.220
and then the encryption and decryption certainly also should not be
10:11.220 --> 10:11.700
too expensive.
10:11.840 --> 10:15.760
So these are reasonable requirements, but it looks as if that would be
10:15.760 --> 10:18.760
almost impossible to actually satisfy.
10:19.660 --> 10:24.500
And the background on that is, so what we have to do here is, we have
10:24.500 --> 10:30.040
some ways of easily encrypting something, like if you look at this
10:30.040 --> 10:35.600
lock here, it's very simple to lock, to close such a lock.
10:36.320 --> 10:40.220
You just push it, but in order to open it again you need some secret
10:40.220 --> 10:40.540
key.
10:40.680 --> 10:46.480
If you don't have that key that you can insert here, it's very hard to
10:46.480 --> 10:46.920
open that.
10:47.080 --> 10:52.900
So, the background is that you need a way of some kind of function,
10:53.460 --> 11:00.160
which you can easily compute, but although it is very difficult to
11:00.160 --> 11:03.640
retrieve the original argument to invert that.
11:04.640 --> 11:12.260
And simple examples, so if you have a telephone number, if you know
11:12.260 --> 11:13.500
the...
11:13.500 --> 11:16.100
or if you would like to find a person's phone number in a phone book,
11:16.140 --> 11:16.660
that's easy.
11:17.100 --> 11:20.960
You just look up the person, but if you would like to find the person
11:20.960 --> 11:25.440
for a phone number, if you don't have an inverted list, then it is
11:25.440 --> 11:26.680
hard to find that.
11:27.080 --> 11:30.040
Although, certainly we know how you would do that in that example.
11:30.700 --> 11:32.340
It's just to invert the list.
11:32.520 --> 11:35.660
But if you don't have the inverted list, it's quite an effort to do
11:35.660 --> 11:35.860
that.
11:36.800 --> 11:39.360
Then the more practical example, factorization.
11:39.800 --> 11:43.220
Now we come closer to what we're actually heading at.
11:43.980 --> 11:49.280
If, for example, you have something like the problem of multiplying
11:49.280 --> 11:50.960
two prime numbers, this is easy.
11:51.140 --> 11:53.180
Multiplying two numbers, we know how to do that.
11:53.780 --> 11:57.260
Then we have some number which is the product of two prime numbers.
11:57.440 --> 12:01.840
But then, in order to find out what have been those prime numbers, you
12:01.840 --> 12:04.200
need to factorize the number n.
12:05.260 --> 12:13.040
And certainly that's not really simple to find out which prime numbers
12:13.040 --> 12:17.060
are the divisors of such a number.
12:18.560 --> 12:22.960
So the problem of factorization is believed to be hard.
12:23.880 --> 12:27.120
The known methods are still very expensive.
12:27.900 --> 12:33.240
So this is the problem which seems to be very hard to factorize a
12:33.240 --> 12:35.340
number, in particular if you have a very large number.
12:35.480 --> 12:38.340
Certainly if you have small numbers, this is easily found out.
12:38.920 --> 12:42.900
But if you have very large numbers, very large means, several hundred
12:42.900 --> 12:47.460
or thousand bits, then it is a really hard problem.
12:47.900 --> 12:49.620
And we will look at that problem in a moment.
12:52.620 --> 12:57.360
For cryptography, certainly a one-way function should have a backdoor
12:57.360 --> 13:01.860
that means if you have some additional information, it should be easy
13:01.860 --> 13:03.400
to invert it.
13:03.820 --> 13:08.160
And this additional information usually is key information, as we have
13:08.160 --> 13:10.360
here in that lock system.
13:10.360 --> 13:14.340
If you have the key, you can easily open it again, but without that
13:14.340 --> 13:16.240
it's very hard.
13:16.360 --> 13:17.120
It should be very hard.
13:17.740 --> 13:20.580
One-way functions are an important part in that.
13:20.960 --> 13:23.440
Easy to compute, but hard to invert.
13:24.220 --> 13:31.980
And the system that is one of the standard public key systems is the
13:31.980 --> 13:38.240
RFA cryptosystem by Rivers, Adelman, has been designed at the end of
13:38.240 --> 13:39.000
the 70's.
13:39.640 --> 13:43.180
And here you have, certainly, you have the public key, you have the
13:43.180 --> 13:48.680
secret key, and the public key is a pair of integers N and C.
13:49.500 --> 13:52.540
C is standing for code.
13:53.360 --> 13:58.780
And you have a secret key, a pair of integers N comma D, where only D
13:58.780 --> 14:04.100
is secret, N is known, D is secret, and D stands for decode.
14:05.180 --> 14:09.880
Although we will see that this just refers to the application that I
14:09.880 --> 14:11.060
initially mentioned.
14:11.680 --> 14:15.360
You would like to encode something with a public key and then decode
14:15.360 --> 14:16.320
with a secret key.
14:18.440 --> 14:23.100
And C and D have at most as many bits as N.
14:24.780 --> 14:28.260
And you will see how this actually is used.
14:28.680 --> 14:33.620
The standard lengths are well, this is almost not used anymore.
14:33.620 --> 14:36.340
Usually you have something like 2,048 bits.
14:37.040 --> 14:41.480
You can use any number of bits, but usually it's powers of two, what
14:41.480 --> 14:42.160
you have there.
14:42.760 --> 14:49.940
And the number of bits is the basis for the security or the strength
14:49.940 --> 14:52.920
of the photographic system that you get from that.
14:53.380 --> 14:54.720
How is it actually done?
14:55.140 --> 14:55.880
You have a message.
14:56.900 --> 15:00.240
The message is just some sequence of zeros and ones.
15:00.460 --> 15:03.660
You could say, okay, it's just a sequence of just one large number.
15:04.340 --> 15:06.760
Now you have that value N.
15:06.880 --> 15:11.720
You just chop the sequence into individual paths with some kind of
15:11.720 --> 15:13.220
block cipher, you could say.
15:14.080 --> 15:21.480
The message, chop it into paths M1, M2, M3, and so on, such that all
15:21.480 --> 15:26.220
these values M1 to Mk are smaller than N.
15:26.600 --> 15:29.600
You could just take one bit less than N.
15:29.600 --> 15:33.940
Then you always have the value that is in that range.
15:35.380 --> 15:40.240
So you just divide the message into such a sequence of blocks, and
15:40.240 --> 15:43.920
then you compute the following.
15:45.000 --> 15:51.200
You take all the individual paths there, the Mi, take them to the
15:51.200 --> 15:56.020
power c, and compute the modulo...it says that modulo N.
15:56.220 --> 15:59.860
So you divide by N and take the remainder of that.
16:00.860 --> 16:08.920
Then you have some part or some value Ci which is less than N.
16:09.640 --> 16:18.820
Now you have that value, and then you have a sequence of c1, c2, and
16:18.820 --> 16:19.240
so on.
16:19.760 --> 16:27.880
And the decryption then just works that way that you get the encrypted
16:27.880 --> 16:28.520
message.
16:28.820 --> 16:35.520
You just divide that message again into those parts c1 to ck, and now
16:35.520 --> 16:40.800
you take Ci to the power d, modulo N.
16:42.620 --> 16:43.120
And
16:46.620 --> 16:51.460
magically, here, we get the value Mi again.
16:51.680 --> 16:59.160
That's the claim that N, c, and d are chosen such that this works.
16:59.960 --> 17:05.260
So that you can take a message, the value Mi, take it to the power c,
17:05.960 --> 17:11.260
modulo N, and then if you take that to the power d again, you get the
17:11.260 --> 17:12.240
original value there.
17:13.460 --> 17:16.620
Looks like magic, this is just number theory as we will see in a
17:16.620 --> 17:16.860
moment.
17:18.220 --> 17:24.120
And so, this is all about that RFA cryptosystem, that you just have to
17:24.120 --> 17:24.440
do that.
17:24.540 --> 17:31.280
Or, just is a bit unfair, because just means, well, we have to compute
17:31.280 --> 17:32.940
Mi to the power c.
17:33.780 --> 17:39.120
Mi are values that have as many bits as N.
17:39.820 --> 17:42.880
So something like 2000 bits.
17:43.720 --> 17:49.080
And c and d are values which have at most as many bits as N, but may
17:49.080 --> 17:50.480
have as many bits as N.
17:51.060 --> 17:54.640
Usually they are, or at least one of them will be smaller, but they
17:54.640 --> 17:56.680
will have several hundred bits.
17:59.140 --> 18:02.080
And that means you have very, very large numbers.
18:03.100 --> 18:07.420
And so it means you have arithmetic of very large numbers, and
18:07.420 --> 18:12.700
modification of very large numbers is... takes quite some time.
18:14.100 --> 18:21.340
So it's a naive way to take the length of the numbers so you need
18:21.340 --> 18:24.180
multiple arithmetic here, which is expensive.
18:24.840 --> 18:27.700
And it's not just modification, it's Mi to the power c.
18:28.600 --> 18:34.440
Mi to a value, to an exponent, which is a very large number.
18:34.900 --> 18:40.260
So that really is an extensive computation, contradicting the
18:40.260 --> 18:44.520
requirement that encryption and decryption should be done in an
18:44.520 --> 18:45.100
efficient way.
18:45.660 --> 18:47.400
So this is a challenge.
18:47.520 --> 18:51.360
If you would like to use that, how can you make sure that this can be
18:51.360 --> 18:52.380
done efficiently?
18:53.180 --> 18:57.380
So there are many, many ways of actually performing those computations
18:57.380 --> 19:00.940
in more efficient ways than the naive ways.
19:01.040 --> 19:07.440
I will indicate just very simple ways of doing that, but there are
19:07.440 --> 19:11.840
more sophisticated ways of computing these powers using modular
19:11.840 --> 19:12.260
arithmetic.
19:13.120 --> 19:16.760
Using Chinese remainder theorem and things like that, but I will not
19:16.760 --> 19:19.700
go into the details of Chinese remainder theorem.
19:20.740 --> 19:25.060
So, the important thing, the basic thing, is how can we actually make
19:25.060 --> 19:25.780
sure that this works?
19:25.920 --> 19:30.240
How can we choose n, c, and d such that this works?
19:30.760 --> 19:35.120
And to assume 1024 bits, although the number of bits here is
19:35.120 --> 19:39.780
completely irrelevant at the moment, we just look at those values.
19:39.780 --> 19:46.560
And we want to have a number having around 1000 bits, so we just
19:46.560 --> 19:51.680
randomly generate two large prime numbers, p and q, both having half
19:51.680 --> 19:52.300
as many bits.
19:52.460 --> 19:58.160
If we multiply those two prime numbers, then we know that the product
19:58.160 --> 20:00.300
will have twice the number of bits.
20:01.140 --> 20:07.160
And so, in this way we can get a number n, which is the product of p
20:07.160 --> 20:07.540
and q.
20:08.260 --> 20:14.180
And I just mentioned when I talked about one-way functions, that
20:14.180 --> 20:18.620
factorization is such a one-way function that means it's easy to
20:18.620 --> 20:20.280
compute, but hard to invert.
20:21.260 --> 20:28.660
And so, if you only know n, if you have a very large number, it's very
20:28.660 --> 20:31.000
hard to actually find out what p and q are.
20:31.720 --> 20:35.620
So this is one thing that is used there, so that's how we get n.
20:35.620 --> 20:37.740
Now, how do we choose c and d?
20:38.680 --> 20:49.600
So we just randomly choose some c such that c is prime relative to p-1
20:49.600 --> 20:50.700
times q-1.
20:50.860 --> 21:02.400
What does it mean that a is prime with respect to b, if and only if
21:02.400 --> 21:08.380
the greatest common divisor of a and b equals 1.
21:09.360 --> 21:09.600
Yeah?
21:11.880 --> 21:12.140
Simple.
21:12.660 --> 21:15.520
There's no non-trivial common divisor.
21:17.560 --> 21:21.460
So, we just choose such a value.
21:21.920 --> 21:33.640
Now, since we have a number like p-1 times q-1, if we just choose a
21:33.640 --> 21:36.020
prime number c, then that is simple.
21:36.300 --> 21:44.720
We won't have a non-trivial common divisor, and c should be prime
21:44.720 --> 21:49.240
relative to not p times q, but p-1 times q-1.
21:49.340 --> 21:52.880
We'll see in a moment why we choose exactly that value.
21:53.980 --> 22:00.820
So, c should be prime relative to p-1 times q-1, and then we determine
22:00.820 --> 22:08.480
a value d, such that the product of c and d is congruent to 1 modulo p
22:08.480 --> 22:10.080
-1 times q-1.
22:10.920 --> 22:23.920
What does it mean that value like, if you have a congruent to b modulo
22:27.160 --> 22:40.430
x, for example, write that in a better way, modulo x means that if and
22:40.430 --> 22:51.250
only if there exists c such that a minus b equals c times x.
22:52.230 --> 22:58.310
So, a and b have the same remainder with respect to division by x.
22:59.750 --> 23:13.370
And so, that's the definition of cd is congruent to 1 modulo p-1 times
23:13.370 --> 23:20.570
q -1 They have the same remainder of that, so cd is a value that is a
23:20.570 --> 23:23.710
multiple of p-1 times q-1 plus 1.
23:24.050 --> 23:24.550
Very simple.
23:25.890 --> 23:32.070
Now, the interesting fact is that if we have chosen those values
23:32.070 --> 23:36.550
having those, satisfying those requirements, we have chosen them in
23:36.550 --> 23:44.730
this way, then the claim is that for these n, c, and d, we have that
23:44.730 --> 23:53.490
for all values m less than n, m to the c times d is congruent to m
23:53.490 --> 23:55.130
modulo n.
23:56.610 --> 24:03.090
Now, remember that we had computed in the RSA algorithm, first m to
24:03.090 --> 24:09.350
the c that was the encryption, and then the encrypted value to the
24:09.350 --> 24:15.530
power d, which means that well, it's essentially taking m to the c to
24:15.530 --> 24:21.690
the power d and that is, as it claims, c is congruent to m modulo n,
24:22.350 --> 24:25.050
and so this is what we need.
24:25.470 --> 24:29.890
If that lemma holds true, then we know that the RSA algorithm works
24:29.890 --> 24:30.430
correctly.
24:31.130 --> 24:36.210
The validity of that lemma is due to some results of number theory.
24:36.370 --> 24:40.150
I will not go into those results, but just use them.
24:40.530 --> 24:46.790
The first one is Fermat's little theorem which is saying that if p is
24:46.790 --> 24:52.490
a prime number and if you have another value a which is not divisible
24:52.490 --> 24:57.770
by p, then a to the p minus one is congruent to one modulo p.
24:58.230 --> 25:00.310
That is the first important point.
25:01.950 --> 25:08.910
That would mean in this case, a to the p would be congruent to a
25:08.910 --> 25:10.210
modulo p.
25:11.930 --> 25:18.170
Multiply the number times a, then you would have something a to the p
25:18.170 --> 25:21.730
congruent to a.
25:22.590 --> 25:27.130
Or a to the p minus one congruent to one modulo p.
25:27.250 --> 25:31.390
So this is something which will be used in showing that this actually
25:31.390 --> 25:32.030
holds true.
25:33.350 --> 25:40.290
The other thing is that this has been generalized by Euler, and Euler
25:40.290 --> 25:49.650
used a particular value for any integer value n or any natural number
25:49.650 --> 25:50.090
n.
25:51.650 --> 26:00.570
He looked at the number of values that are prime relative to such a
26:00.570 --> 26:01.550
value n.
26:01.830 --> 26:08.350
So all the values m that are smaller than n, but not divisors of which
26:08.350 --> 26:11.610
don't have a common divisor with x.
26:11.610 --> 26:16.490
And this value phi is called, or phi of n is called the Euler
26:16.490 --> 26:18.410
function, because Euler designed that.
26:19.450 --> 26:24.750
The theorem that we are using here is that for any values n and a,
26:25.490 --> 26:29.110
such that a is prime relative to n, so they have a greatest common
26:29.110 --> 26:35.110
divisor with one, we have the result that a to the phi of n is
26:35.110 --> 26:36.790
congruent to one modulo n.
26:38.270 --> 26:42.990
So here we had a to the p minus one is congruent to one modulo p, and
26:42.990 --> 26:47.630
now we have here a to the phi of n is congruent to one modulo n.
26:48.570 --> 26:54.490
And what we're interested in is certainly something where we can get
26:54.490 --> 27:02.530
this statement that something taken for some exponent is, or this is
27:02.530 --> 27:05.250
taken for some value is the identity function.
27:06.210 --> 27:11.310
And as I said, if you would take that a to the phi of n plus one, then
27:11.310 --> 27:14.470
that would be congruent to a modulo n.
27:14.730 --> 27:17.710
And then you would have exactly what you need for that lemma.
27:19.090 --> 27:25.430
So the corollary is that for all a, n out of n a to the phi of n minus
27:25.430 --> 27:31.610
one is the modulo inverse of a with respect to that modulo n, and
27:31.610 --> 27:35.850
these facts are used in showing that lemma holds true.
27:35.850 --> 27:38.530
And I will show you that this actually holds.
27:38.910 --> 27:42.970
I will not go into those theorems, but just show how we use those
27:42.970 --> 27:49.610
results of number theory in order to show that the basic method of the
27:49.610 --> 27:51.750
RSA algorithm actually is correct.
27:52.770 --> 27:57.850
And the first thing that we have to look at for that is what the Euler
27:57.850 --> 28:03.750
function actually is for this value capital N, which is p times q.
28:03.750 --> 28:09.870
So if p and q are prime, then phi of pq, the Euler function of p times
28:09.870 --> 28:13.670
q, is the product p minus one times q minus one.
28:14.230 --> 28:19.470
And if you look back at the previous slide, you see that here we had
28:20.350 --> 28:25.370
chosen c such that c is prime relative to p minus one times q minus
28:25.370 --> 28:27.950
one, so this has something to do with that.
28:32.400 --> 28:34.920
Then let's go again to this slide.
28:35.480 --> 28:36.720
So how can you prove that?
28:37.020 --> 28:40.820
We have a value which is the product of two prime numbers, p and q.
28:41.580 --> 28:45.500
Now if they are prime, then we can immediately say, or can list a
28:45.500 --> 28:53.300
certain number of values which are not prime with respect to p times
28:53.300 --> 28:53.460
q.
28:53.560 --> 28:56.740
They have a common, a non-trivial common divisor with p times q.
28:56.800 --> 29:02.900
Now what are these non-trivial common divisors of p times q over the
29:02.900 --> 29:07.120
value having a factor p or a factor q?
29:07.620 --> 29:12.880
We have a non-trivial common divisor, so these values, p times one, p
29:12.880 --> 29:19.080
times two, up to p times q, are values that are less or equal to p
29:19.080 --> 29:24.900
times q, which has a greatest common divisor which is not equal to
29:24.900 --> 29:25.120
one.
29:26.240 --> 29:32.780
And the same is true for multiples of q, and for how many multiples do
29:32.780 --> 29:39.720
we have here, these are q multiples, and these are p minus one
29:39.720 --> 29:47.800
multiples, so in sum we have p plus q minus one numbers, and these are
29:47.800 --> 29:51.980
exactly those numbers which are not prime with respect to the product
29:51.980 --> 29:52.800
of p times q.
29:54.360 --> 30:00.220
And so, how many numbers are there in total less or equal to p times
30:00.220 --> 30:00.560
q?
30:00.720 --> 30:02.760
These are just p times two different values.
30:03.340 --> 30:08.460
We know that p plus q minus one of those are not prime with respect to
30:08.460 --> 30:13.580
p times q, so if we subtract that, this is just the product of p to
30:13.580 --> 30:15.060
minus one times q minus one.
30:16.180 --> 30:19.900
As you can easily see that if you multiply that out, then you have
30:19.900 --> 30:21.700
exactly that equation.
30:22.660 --> 30:28.320
So, this is just this number of integers which are prime with respect
30:28.320 --> 30:33.980
to p times q, and now we use that fact for the following.
30:34.300 --> 30:37.480
We know that p minus one times q minus one is the Euler function of p
30:37.480 --> 30:37.900
times q.
30:39.060 --> 30:47.460
So that's what's stated here again, and we know because of the Euler
30:47.460 --> 30:55.140
theorem that if m is prime relative to that value n, then m to the
30:55.140 --> 30:59.340
Euler function of p minus one times n.
31:00.160 --> 31:04.900
m to the Euler function of n is congruent to one modulo n.
31:04.980 --> 31:10.820
That is the statement of the Euler theorem, and we certainly also know
31:10.820 --> 31:19.040
from that that if we multiply both values of m, then we have m to the
31:19.040 --> 31:25.340
p minus one times q minus one plus one is equal to m modulo n.
31:25.520 --> 31:27.700
So this is a simple thing.
31:28.480 --> 31:36.300
If you have problems with this modular arithmetic just put up your
31:36.300 --> 31:37.780
hand and I can explain it to you.
31:39.880 --> 31:53.300
So, from that, we also know that now c times d d is chosen such that
31:53.300 --> 32:00.180
the product of c and d is congruent to one modulo p minus one times q
32:00.180 --> 32:00.720
minus one.
32:01.740 --> 32:12.160
And that means that cd minus one is a multiple of p minus one times q
32:12.160 --> 32:12.760
minus one.
32:13.520 --> 32:17.280
This is what we know, this is just the same statement.
32:20.810 --> 32:32.130
And so m to the c times d c times d therefore is congruent to one
32:32.130 --> 32:34.690
modulo p minus one times q minus one.
32:35.610 --> 32:43.010
So it means that m to the c times d is congruent to m modulo n.
32:44.190 --> 32:51.370
Here we have we know that m to the... so c times d is a multiple of p
32:51.370 --> 32:56.770
minus one times q minus one we know that m to the p minus one times q
32:56.770 --> 33:02.650
minus one there, this statement is congruent to one modulo n.
33:05.230 --> 33:15.690
And so it means c times d is just a multiple of p minus one times q
33:15.690 --> 33:16.870
minus one plus one.
33:17.430 --> 33:22.470
So we know that we have here exactly that equation.
33:23.030 --> 33:24.730
This is what is stated here again.
33:24.930 --> 33:29.470
c times d is such a value such an exponent such that we have m there
33:29.470 --> 33:29.790
again.
33:30.430 --> 33:34.190
And certainly here we only have in the exponent p minus one times q
33:34.190 --> 33:34.750
minus one.
33:34.850 --> 33:43.510
Here we have that k times, but if that if m to the x is congruent to
33:43.510 --> 33:48.470
one modulo n, then m to the k times x certainly is also congruent to
33:48.470 --> 33:49.190
one modulo n.
33:49.290 --> 33:50.050
So this is simple.
33:52.390 --> 33:57.450
And so that means for all those values that are prime relative to n,
33:58.490 --> 34:03.030
we have exactly the equation that we are looking for, that m times m
34:03.030 --> 34:05.890
to the c times d is congruent to m modulo n.
34:05.890 --> 34:14.170
Now this is just because of that choice of values and the fact that we
34:14.170 --> 34:15.490
have the Euler theorem.
34:16.590 --> 34:21.710
Now the question is what happens if such a value m is not prime with
34:21.710 --> 34:23.290
respect to that value.
34:23.410 --> 34:27.710
We know that there are p minus, or p plus q minus one values which are
34:27.710 --> 34:30.210
not prime relative to n.
34:30.670 --> 34:38.990
Now these values we know are for example of the type multiples of q we
34:38.990 --> 34:43.150
have multiples of p and multiples of q, so if this value m is just
34:43.150 --> 34:47.710
some multiple of q what's happening in this case?
34:48.310 --> 34:53.450
We have to show that even for those values, m to the c times d will be
34:53.450 --> 34:54.850
congruent to m modulo n.
34:56.070 --> 34:59.230
And so t definitely is less than p.
35:00.830 --> 35:04.670
Otherwise it wouldn't be such a value.
35:05.710 --> 35:13.330
And since t is less than p t is a prime number, we know because of the
35:13.930 --> 35:19.450
little theorem of Fermat, that t to the p minus oops, that t to the p
35:19.450 --> 35:21.550
minus one is congruent to one modulo n.
35:22.990 --> 35:30.690
And we also know that q to the p minus one is congruent to one modulo
35:30.690 --> 35:30.950
q.
35:32.750 --> 35:38.930
Because q definitely is also, q is a prime number, p is a prime
35:38.930 --> 35:42.930
number, so this is just due to the little Fermat theorem.
35:43.910 --> 35:49.370
Now we can use that result, we certainly notice that if we have this
35:49.370 --> 35:55.670
for every k greater than zero, certainly if we just square those
35:55.670 --> 36:03.550
values if we take that k times p to the k times now p minus one times
36:03.550 --> 36:10.990
q minus one we can just take a multiple of that, it's still congruent
36:10.990 --> 36:11.890
to one modulo p.
36:11.990 --> 36:16.150
The same is true for q to the k times p minus one times q minus one.
36:16.750 --> 36:18.590
Also congruent to one modulo p.
36:19.170 --> 36:23.490
So this is just a simple consequence of the fact that those powers
36:23.490 --> 36:26.250
here are congruent to one modulo p.
36:26.730 --> 36:31.870
These are just multiples of those powers, and so this is again just
36:32.730 --> 36:33.810
congruent to one.
36:35.030 --> 36:41.810
And now, since both are congruent to one, we can just multiply those
36:41.810 --> 36:43.990
values.
36:44.250 --> 36:52.610
So as a product of those two values here are also, so if we have for
36:52.610 --> 37:02.670
example, the following holds true if a is congruent to b modulo p and
37:02.670 --> 37:15.910
c is congruent to d modulo p, then certainly a times c is congruent to
37:15.910 --> 37:18.290
c times d.
37:21.850 --> 37:25.850
Modulo modulo p, yes.
37:27.010 --> 37:27.210
Okay.
37:28.130 --> 37:32.410
So this is around that.
37:32.890 --> 37:37.270
So this is just simple fact from number theory.
37:38.490 --> 37:40.950
Are these facts known to you?
37:42.110 --> 37:42.990
Modular arithmetic?
37:46.480 --> 37:47.320
No response?
37:47.320 --> 37:49.620
Or new number theory?
37:49.840 --> 37:53.060
This is something which is standard mathematics.
37:56.420 --> 37:58.720
But it is really not that difficult.
37:58.940 --> 38:04.420
If you just use that basic definition that a is congruent to b, modulo
38:04.420 --> 38:08.680
x means a minus b is a modulo of x, then you can easily find that out.
38:09.220 --> 38:10.120
This is simple.
38:10.660 --> 38:17.520
So we have that, so we have the product of those t, power of t, power
38:17.520 --> 38:22.500
of q, product of those two is congruent to the product of the right
38:22.500 --> 38:26.940
-hand side, product of the right-hand side is still one, and we just
38:26.940 --> 38:38.740
multiply that with t, and then we have t times tq to that power is
38:38.740 --> 38:40.420
then congruent to t, modulo t.
38:40.760 --> 38:42.320
Both sides multiply to t.
38:43.240 --> 38:54.760
And it's also true that, like if we multiply that with q, this is also
38:54.760 --> 38:59.320
congruent then to tq, modulo t times t.
38:59.980 --> 39:05.240
This is also, again, another simple result, like if we multiply both
39:05.240 --> 39:12.860
sides with the same value, then those values are congruent again,
39:13.120 --> 39:17.520
modulo the original modulus, but also to the modulus that is
39:17.520 --> 39:19.040
multiplied to that value q.
39:19.500 --> 39:25.260
So this is another simple fact of, or simple implication of modular
39:25.260 --> 39:35.260
arithmetic, and so what we have now is that tq to the power k times t
39:35.260 --> 39:40.900
minus one times q minus one plus one is congruent to t times q, modulo
39:40.900 --> 39:41.840
t times q.
39:43.800 --> 39:49.540
But that is exactly what we are looking for, t times q is the value of
39:49.540 --> 39:56.840
m, and so we had to show that m to the t times d is congruent to m
39:56.840 --> 40:00.360
again, modulo n, but this is exactly what it stated.
40:00.920 --> 40:06.580
Because k times t minus one, q minus one, plus one is our product of t
40:06.580 --> 40:11.420
times d, and so we are done.
40:12.220 --> 40:16.980
And the same can be done for modulus of p, just in a symmetric way,
40:17.480 --> 40:21.600
and so in this way we have shown that for every value, for any value
40:21.600 --> 40:28.660
that is less than capital N, we have this result that m to the t times
40:28.660 --> 40:31.260
d is congruent to m modulo n.
40:32.040 --> 40:37.980
So if we just use the Euler Theorem and the Lim-Savart, both are the
40:38.820 --> 40:41.960
major two ingredients of that result.
40:42.780 --> 40:46.720
So, number theory gives us that nice result, we can just compute it in
40:46.720 --> 40:52.220
this way, and so we don't need all these structures like in the
40:52.220 --> 40:56.760
symmetric algorithm, we have these storing and table permutations and
40:56.760 --> 40:57.400
things like that.
40:58.160 --> 41:01.380
This is just done here by using number theory.
41:02.760 --> 41:07.620
And so we now have that result and now the question is, what about the
41:07.620 --> 41:11.940
requirements that we had, what about the cost of that algorithm?
41:12.740 --> 41:18.820
And one of the major points here is, well we have this exponent, like
41:18.820 --> 41:25.820
we have to take the power take it to a very large power, and it's very
41:25.820 --> 41:36.160
large numbers, very large numbers computing these exponentiation is
41:36.160 --> 41:36.760
expensive.
41:37.880 --> 41:45.460
So the naive way would be that if you have to compute a to the 4, for
41:45.460 --> 41:54.060
example, that is a times a times a times a, so that would mean you
41:54.060 --> 42:00.860
would have three modifications for that, which certainly would mean
42:00.860 --> 42:10.300
that for a to the x or x to the n, you would have something like n
42:10.300 --> 42:14.720
operations which would be a very, very, very large number.
42:15.220 --> 42:20.760
And you can easily see now that this can be done in a more easy way so
42:20.760 --> 42:27.560
if we go to the next slide I can briefly show you how that can be
42:27.560 --> 42:27.860
done.
42:29.240 --> 42:35.020
How can we compute x to the n in a more efficient way.
42:35.580 --> 42:38.500
I don't know whether you have seen that algorithm or those algorithms
42:38.500 --> 42:40.680
before it's a simple observation.
42:41.360 --> 42:48.020
You have an arbitrary integer and you have an arbitrary integer n and
42:48.020 --> 42:53.480
this n is supposed to be the exponent of x so if we compute x to the n
42:55.260 --> 43:04.980
n can be written certainly as a binary number, sum of ai 2 to the i.
43:05.560 --> 43:12.780
And now that means if we compute x to the n, this is just x to the n,
43:12.940 --> 43:19.640
n is the sum of those powers of 2 that means we can either write that
43:19.640 --> 43:29.080
as x to the sum of certain values or as a product of those powers.
43:30.920 --> 43:37.780
And so we have this equation here and we have to look at such a
43:37.780 --> 43:38.120
structure.
43:38.260 --> 43:44.120
Now if we look at that the product of powers of x and every power,
43:44.240 --> 43:46.660
like the ai, are either 0 or 1.
43:46.660 --> 43:55.700
That means we have certain powers x to the 2 to the i only those are
43:55.700 --> 44:01.920
in that product where the ai is not equal to 0, which is why.
44:02.960 --> 44:04.900
Now there are different ways of computing that.
44:05.420 --> 44:08.060
One way would be just take those powers.
44:08.600 --> 44:10.640
They're written in a slightly different way.
44:10.860 --> 44:20.200
So definitely you know it as x to the a times b that can be either
44:20.200 --> 44:31.540
written as x to the a to the b or x to the b to the a.
44:32.720 --> 44:42.720
Now this is also simple arithmetic so we could write here we take x to
44:42.720 --> 44:49.300
a0, which is binary that means we either take that or not.
44:49.660 --> 44:50.400
0 or 1.
44:52.480 --> 44:58.720
And then we have x squared and we decide whether we need that or not.
44:59.640 --> 45:03.880
We have to use x to the 4 and we look at whether we need that or not.
45:04.020 --> 45:06.460
Or x to the 2 to the k in the end.
45:06.600 --> 45:14.820
So all these powers of x where the exponent is a power of 2 and the
45:14.820 --> 45:18.160
bits tell us whether we need that power of x or not.
45:18.760 --> 45:26.780
And obviously we can get all those factors here by just squaring by
45:26.780 --> 45:30.080
successive squaring of the individual values.
45:30.180 --> 45:34.480
So we take x squared, x to the 4, x to the 8 and so on, x to the 2 to
45:34.480 --> 45:34.800
the i.
45:35.620 --> 45:40.480
So this is just successive squaring and deciding whether you need
45:40.480 --> 45:41.720
those powers or not.
45:42.780 --> 45:50.880
And if you have a number having k bits you need exactly k of those
45:50.880 --> 45:57.100
algorithms or k of those steps, so you have to square that value k
45:57.100 --> 46:03.800
times and while you are doing that you just multiply the immediate
46:03.800 --> 46:08.280
value with the additional power of x.
46:09.100 --> 46:10.740
This is one way of doing that.
46:11.140 --> 46:15.780
The other way would be a different way of looking at that product of x
46:16.360 --> 46:23.000
values is, well, to look at x to the 8k.
46:23.700 --> 46:26.180
That means do we need x or not?
46:27.140 --> 46:32.300
And then we need to know 8k times 2 to the k.
46:32.960 --> 46:40.080
Now, there is the 2 to the k, that's successive squaring, but we just
46:40.080 --> 46:49.660
multiply that with x to the 8k-1 and form this number of squarings and
46:49.660 --> 46:50.080
so on.
46:50.400 --> 46:52.380
So this is a nested way of doing it.
46:53.700 --> 47:00.120
And in the end we would have x to the a0 times that where that
47:00.120 --> 47:05.640
intermediate value x to the a1 times that value and so on.
47:06.060 --> 47:11.800
That means if we compute that here, we could compute it this way
47:11.800 --> 47:18.980
starting with x to the a0, compute x squared decide whether we need
47:18.980 --> 47:25.540
something here, whether it is 1 or, like, if a1 is 0, we have here the
47:25.540 --> 47:30.240
value that would be 1, or otherwise it is that power, and so on.
47:30.500 --> 47:34.020
We can do it starting from the least significant bit, going to the
47:34.020 --> 47:37.220
highest significant bit, or you could start with the highest
47:37.220 --> 47:43.920
significant bit, take x to the 8k, that means use that x, or put 1
47:43.920 --> 47:49.860
there, square that value, multiply with x if the appropriate bit is 1,
47:50.500 --> 47:57.140
square it again, multiply with x if the appropriate bit is 1, square
47:57.140 --> 48:01.080
again, and so on, until you finally get that value, because this is
48:01.080 --> 48:02.480
computed that way.
48:03.340 --> 48:10.000
Two different ways of computing the power x to the n, and obviously
48:10.000 --> 48:18.520
the number of operations that you need is the order of k.
48:19.380 --> 48:29.680
So both ways we have the order of k operations, in the worst case, 2k
48:29.680 --> 48:37.800
minus 1 operations, and it means that it is the logarithm of n, so we
48:37.800 --> 48:48.400
have a fast way of computing here, okay, so we have this fast
48:48.400 --> 48:55.880
exponentiation using logarithm of n arithmetic operations for taking x
48:55.880 --> 48:56.520
to the power n.
48:57.300 --> 48:59.960
So this is a simple way, now we know how to do that.
49:00.800 --> 49:09.980
Still, if we have an exponent having 1000 bits, we still need 1000
49:09.980 --> 49:10.980
operations for that.
49:11.760 --> 49:18.800
Not just 1000, but maybe more, at most two times that value.
49:18.800 --> 49:26.380
But it's a large number of individual operations, but still much less
49:26.380 --> 49:29.280
than in the naive way of computing them.
49:31.500 --> 49:36.920
And obviously these operations are all operations on large integers,
49:37.640 --> 49:41.480
so it is still quite expensive.
49:42.380 --> 49:47.460
So if we have naive multiplication of k word integers, we would need k
49:47.460 --> 49:48.940
squared single word operations.
49:50.380 --> 49:54.980
If you just take the school method for doing that, like multiplying
49:54.980 --> 50:02.940
two values, you know that we do it like having multiples of that
50:02.940 --> 50:05.280
value, and then summing all those up.
50:06.040 --> 50:10.780
And this is just something where you have k squared operations.
50:11.080 --> 50:18.440
Every operation here needs time k, linear time, and then you have k of
50:18.440 --> 50:23.900
those operations, times k squared, the naive school method.
50:24.660 --> 50:30.800
If you do that in a recursive way, you can easily reduce that to k to
50:30.800 --> 50:31.920
the 1.5.
50:33.720 --> 50:38.220
And if you do it with even more sophisticated approach, you can
50:38.220 --> 50:41.240
actually reduce that to k times log 6.
50:42.300 --> 50:44.520
For that you would need the past Fourier transform.
50:46.380 --> 50:48.660
Do you know the past Fourier transform?
50:48.960 --> 50:50.620
Who of you knows the past Fourier transform?
50:51.900 --> 50:55.380
None of you, if you would like to get to know how that works, come to
50:55.380 --> 50:57.120
my course on addition algorithms.
50:57.800 --> 51:00.240
I will not go into details of that in this course.
51:00.700 --> 51:06.060
So this is past Fourier transform, is that it's a way of... it allows
51:06.060 --> 51:12.680
you to perform that multiplication of k word numbers in that time k
51:12.680 --> 51:13.620
time log 6.
51:15.080 --> 51:15.440
Okay.
51:16.100 --> 51:20.300
So that means that we can reduce the time, but still if we look at 32
51:20.300 --> 51:28.280
-bit arithmetic, and we have exponent length of 1024 bits, we need
51:28.280 --> 51:34.820
something like, like in a simple way to compute that, something like
51:36.080 --> 51:40.340
327 operations per plaintext block of 1024 bits.
51:40.900 --> 51:46.660
So this is quite a large number of operations, but we have to pay
51:46.660 --> 51:48.040
something for getting security.
51:49.820 --> 52:00.080
And there are ways of even speeding that up, using using as I
52:00.080 --> 52:04.180
mentioned the sinus remainder theorem, and using a more sophisticated
52:04.180 --> 52:09.840
way, modern arithmetic, but I don't have the time here in this course
52:09.840 --> 52:11.600
to go into the details of that.
52:12.180 --> 52:18.140
That would be the topic of a different course where we would look more
52:19.780 --> 52:21.800
into fast arithmetic.
52:23.280 --> 52:23.880
Okay.
52:24.340 --> 52:28.580
Now you can implement that in hardware, and if you do that, just use
52:28.580 --> 52:36.780
those methods, if you use certain algorithms for performing those
52:36.780 --> 52:45.700
operations, you can actually perform RSA encryption in time, or in the
52:45.700 --> 52:46.400
high frequency.
52:46.920 --> 52:50.780
It's like you use modular arithmetic, use parallelization, use
52:50.780 --> 52:54.840
pipelining, and then you can support the data rates that are necessary
52:54.840 --> 52:55.500
currently.
52:56.180 --> 53:01.380
And you can easily actually do that online without slowing down the
53:01.380 --> 53:01.860
communication.
53:02.020 --> 53:07.200
You know that if we talk about communication, we are talking about
53:08.940 --> 53:13.540
data rates that are not that high, 100 megabits or things like that,
53:15.500 --> 53:21.460
100 megabits per second, and we know that we can perform many
53:21.460 --> 53:27.840
operations inside, the clock frequency is several magnitudes higher,
53:27.840 --> 53:35.880
so we can perform quite a number of operations internally compared to
53:35.880 --> 53:40.240
the communication speed, the communication bandwidth, and you can also
53:40.240 --> 53:47.200
use parallelization, and so we can actually use RSA without slowing
53:47.200 --> 53:49.660
down significantly the communication.
53:51.960 --> 53:57.040
And another point is that if you don't want to use that sophisticated
53:57.040 --> 54:04.860
method, then we can actually make our communication secure by not just
54:04.860 --> 54:09.840
using such a public key method like RSA, but by combining that with
54:09.840 --> 54:15.500
other methods which are much more efficiently computed, like symmetric
54:15.500 --> 54:20.880
methods, and in this combination get around the problems that we had
54:20.880 --> 54:24.440
with symmetric cryptographic methods.
54:24.540 --> 54:26.300
We will see how we do that in a moment.
54:27.940 --> 54:32.960
So this is the RSA algorithm that was passed for communication, as I
54:32.960 --> 54:33.720
showed you already.
54:34.860 --> 54:40.320
The question is, again, cryptanalysis, how expensive is it to actually
54:40.320 --> 54:41.880
attack that algorithm?
54:42.500 --> 54:51.420
The attack would mean as soon as you know the prime numbers, which are
54:51.420 --> 54:56.480
the factors of N, then certainly by knowing the public key, you
54:56.480 --> 54:57.500
immediately have D.
54:57.640 --> 55:03.180
Because if you know the prime number P and Q, you can compute P-1
55:03.180 --> 55:09.960
times Q-1 and then you can compute D which corresponds to C.
55:11.900 --> 55:17.440
But the problem, or the nice fact, is that currently the best known
55:17.440 --> 55:24.160
methods need a lot of time to factor large numbers, like this is
55:24.160 --> 55:30.420
showing the current upper bound on doing that, the best known upper
55:30.420 --> 55:37.060
bound with respect to my current knowledge of those factorization
55:37.060 --> 55:45.860
methods, and like D in that formula is the number of bits of N.
55:46.940 --> 55:53.980
That means if you just use that and disregard the constant values that
55:53.980 --> 56:00.000
are always in those big O locations, if we assume that we have 10 to
56:00.000 --> 56:05.080
the 12 operations per second, that means one operations per second,
56:05.760 --> 56:10.980
and we have this value having 300 decimal digits.
56:11.120 --> 56:14.700
300 decimal digits means around 1000 binary digits.
56:16.720 --> 56:24.020
Then, if we would just use that algorithm we would still need several
56:24.020 --> 56:26.040
thousand years for factorizing.
56:27.120 --> 56:36.240
So, this is still quite expensive, and the we always had the
56:36.240 --> 56:42.740
requirement that it should be more expensive to decrypt the encrypted
56:42.740 --> 56:47.980
value without knowing the secret keys and the value of that
56:47.980 --> 56:48.580
information.
56:49.240 --> 56:52.800
Well, if it takes several thousand years, that could be the case.
56:54.000 --> 56:58.260
So, this is just with respect to current knowledge, it means you
56:58.260 --> 57:01.660
certainly can decrypt that, but you need information that you can
57:01.660 --> 57:03.840
compute, but it takes some time to do that.
57:04.380 --> 57:08.660
Now, certainly, there would be ways of attacking it, which are
57:08.660 --> 57:15.980
different from just using exact methods for or deterministic methods
57:15.980 --> 57:17.180
for factorization.
57:17.860 --> 57:20.280
You could, for example, use probabilistic methods.
57:20.440 --> 57:23.780
You could just guess the value.
57:24.000 --> 57:29.180
Take some arbitrary values, guess methods, or guess factors, check
57:29.180 --> 57:32.100
whether they are factors or not, and then you are done.
57:32.980 --> 57:34.740
Or you could use random computing.
57:36.240 --> 57:39.100
Random computing is a completely different way of computing.
57:39.940 --> 57:44.640
Here, it has been shown that with random computing, factorization is
57:44.640 --> 57:44.980
easy.
57:46.880 --> 57:51.480
So, it would like to factor two numbers that can be done in very
57:51.480 --> 57:53.220
little time using random computing.
57:53.360 --> 57:55.880
Random computing is something which is working in theory.
57:57.620 --> 58:01.260
Certain progress has been made with respect to actually building
58:01.260 --> 58:09.480
random components for computing, but we are far away from actually
58:09.480 --> 58:16.940
having practical random computing devices which can be applied in
58:16.940 --> 58:18.920
practice to this problem.
58:19.180 --> 58:24.320
So, up to current knowledge, it is sufficiently secure to have those
58:24.320 --> 58:33.480
values or to use RSA using, well, it would like to be conservative,
58:33.860 --> 58:40.900
take 2048 bits for the keys, and then, or for the modulus, and then
58:40.900 --> 58:43.440
you are quite safe.
58:44.940 --> 58:50.960
So, we need very long keys, definitely, because the length of the keys
58:50.960 --> 58:56.620
is determining the strength of the cryptographic method, and these
58:56.620 --> 59:02.820
keys have to be much longer than for symmetric key algorithms, because
59:02.820 --> 59:08.840
in symmetric key algorithms, the strength of the algorithm was based
59:08.840 --> 59:10.040
on different things.
59:10.420 --> 59:14.920
There was information hiding and all kinds of these things that I
59:14.920 --> 59:15.440
showed you.
59:16.100 --> 59:22.480
Here, the major point is, if you are able to factor a number, or if
59:22.480 --> 59:25.600
you can do that efficiently, you have immediately a way of efficiently
59:25.600 --> 59:26.900
attacking that algorithm.
59:28.080 --> 59:28.600
Okay.
59:29.100 --> 59:35.000
So, this is just this remark on cryptanalysis, but there are still
59:35.000 --> 59:36.260
some problems remaining.
59:36.380 --> 59:40.280
We said we should be able to easily determine the public key and the
59:40.280 --> 59:41.280
secret key.
59:41.380 --> 59:42.460
Now, how would we do that?
59:42.800 --> 59:48.400
Just two prime numbers having 500, 1000 bits.
59:49.280 --> 59:53.920
Now, how do we know that a certain sequence of 1000 bits is a prime
59:53.920 --> 59:54.300
number?
59:55.260 --> 59:57.700
How can we actually determine that?
59:57.940 --> 01:00:02.940
We would like to find, for example, the largest prime number less than
01:00:02.940 --> 01:00:04.420
or equal to some value.
01:00:06.060 --> 01:00:11.200
So, less than 2 to the n, where n is a very large value.
01:00:12.300 --> 01:00:17.200
The simple way of doing that is a very old one, this book called Seed
01:00:17.200 --> 01:00:21.900
of Eratosthenes, and it works in the following way.
01:00:22.160 --> 01:00:25.260
You just write down all the numbers from 2 to n.
01:00:25.260 --> 01:00:46.060
So, we write down 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16,
01:00:46.800 --> 01:00:57.280
17, 18, 19, 20, 21, 22, 23, 24, and so on.
01:00:58.000 --> 01:01:06.000
It takes some time to do that on the tablet, but well, it doesn't take
01:01:06.000 --> 01:01:09.760
that long if you just do that on your computer, just write up all the
01:01:09.760 --> 01:01:09.920
numbers.
01:01:10.000 --> 01:01:16.760
But if it did well, if the value of n is a number having 1000 bits,
01:01:17.440 --> 01:01:18.680
this is quite a long sequence.
01:01:20.420 --> 01:01:21.080
Yeah?
01:01:21.080 --> 01:01:24.460
And then, what do you do in the next step?
01:01:25.000 --> 01:01:27.280
You delete the first number and all the multiples.
01:01:28.420 --> 01:01:29.140
Well, that's easy.
01:01:29.920 --> 01:01:37.500
If we delete 2, we delete all the like, half of the value disappears.
01:01:37.720 --> 01:01:38.380
Obviously.
01:01:40.320 --> 01:01:43.320
Even numbers cannot be prime.
01:01:44.080 --> 01:01:44.560
You know that.
01:01:46.120 --> 01:01:49.040
So, all the multiples of 2 are deleted.
01:01:49.220 --> 01:01:54.720
We would like to have the largest value that is prime, which is less
01:01:54.720 --> 01:01:55.540
than or equal to n.
01:01:56.000 --> 01:01:59.560
It shouldn't be the product of values that are smaller.
01:02:01.220 --> 01:02:02.980
So we take the next value.
01:02:04.600 --> 01:02:09.500
This is just done until the list consists of a single element only.
01:02:10.880 --> 01:02:20.120
So, we do that all the values from 2 to n and if, by crossing out all
01:02:20.120 --> 01:02:25.360
those values that are multiples of some other value and in the end we
01:02:25.360 --> 01:02:29.920
have only one value, this value has not been a multiple of any of the
01:02:29.920 --> 01:02:30.920
values that are smaller.
01:02:31.580 --> 01:02:35.960
So it must be a prime number, which is less than or equal to n.
01:02:36.240 --> 01:02:42.940
So we have 3, now the next multiple of 3 is there, the 9, then we have
01:02:42.940 --> 01:02:47.380
the 15, then we have the 21, that's it.
01:02:47.920 --> 01:02:56.620
And then we have the 5, multiple of that is not in that list anymore.
01:02:57.640 --> 01:03:04.340
We have to take out the 7 multiple of that, we don't find one there.
01:03:04.840 --> 01:03:10.620
Take out the 11, there's none over there.
01:03:11.060 --> 01:03:14.780
So, in this way, we just cross out all those values.
01:03:15.300 --> 01:03:24.380
You see that this list is getting smaller very fast, but still we have
01:03:24.380 --> 01:03:26.040
to do that for all those values.
01:03:26.140 --> 01:03:31.160
So this is very efficient very fast if you have small values of n, but
01:03:31.160 --> 01:03:35.480
if you have values having thousands of numbers, a thousand bits, it
01:03:35.480 --> 01:03:36.660
just takes too long.
01:03:38.180 --> 01:03:43.700
So it's unfeasible for those values, and so a different approach would
01:03:43.700 --> 01:03:45.780
be to just use a probabilistic approach.
01:03:46.500 --> 01:03:48.920
Certainly, just back to factorization.
01:03:49.340 --> 01:03:53.540
If you use a probabilistic approach, and you are lucky, and just
01:03:53.540 --> 01:03:58.860
guessed a correct prime value, then you have done factorization with
01:03:58.860 --> 01:03:59.720
almost no effort.
01:04:00.620 --> 01:04:04.660
You just guessed such a value, but you cannot guarantee that you find
01:04:04.660 --> 01:04:06.420
that with very few attempts.
01:04:08.360 --> 01:04:14.200
Now, I say, well, we just do or take that approach, the probabilistic
01:04:15.340 --> 01:04:21.540
approach, for finding that prime number, having a large number of
01:04:21.540 --> 01:04:21.720
bits.
01:04:22.400 --> 01:04:27.240
So we would like to find a prime value, so we just choose some random
01:04:27.240 --> 01:04:32.180
odd number, certainly not an even number, just a random odd number,
01:04:32.380 --> 01:04:36.480
having, for example, 512 bits, or 1024, or whatever you like.
01:04:37.720 --> 01:04:44.160
And now, while x is not prime, we just increase that value by two.
01:04:45.980 --> 01:04:50.800
So we just selected one arbitrary value, and then if we were unlucky,
01:04:51.080 --> 01:04:56.180
it was not prime, we just go to the next potential candidate, and
01:04:56.180 --> 01:05:00.600
certainly looking at the next odd value would be increase that value
01:05:00.600 --> 01:05:01.060
by two.
01:05:02.080 --> 01:05:07.780
Now this could be fine, but the question is, how do we actually
01:05:07.780 --> 01:05:09.800
determine whether a value is prime?
01:05:11.400 --> 01:05:16.000
The first thing, what I looked at here, was how do I find the largest
01:05:16.000 --> 01:05:17.620
prime number less than or equal to n?
01:05:18.460 --> 01:05:22.380
Now I say, okay, I just take some arbitrary value, now I have to test
01:05:22.380 --> 01:05:24.460
whether it is a prime number or not.
01:05:24.680 --> 01:05:31.880
So I have to check whether this is a potential value having no non
01:05:31.880 --> 01:05:33.920
-trivial factors.
01:05:34.860 --> 01:05:37.340
So the question is, how can we test whether it's prime?
01:05:38.180 --> 01:05:44.920
And there actually is a probabilistic method for doing that.
01:05:45.900 --> 01:05:51.440
So, this is a very important algorithm, because this has been the
01:05:51.440 --> 01:05:59.280
start of a new area of algorithmics, looking at randomized algorithms.
01:06:00.660 --> 01:06:06.700
Because, like, primality tests have always drawn some interest, and
01:06:07.000 --> 01:06:12.800
probabilistic algorithms always have been very extensive, although for
01:06:12.800 --> 01:06:18.940
a long time, it was not clear whether it was possible to find a
01:06:18.940 --> 01:06:21.700
polynomial time algorithm for primality testing.
01:06:22.040 --> 01:06:27.620
It was assumed that it is not a polynomial time algorithm, but a
01:06:27.620 --> 01:06:33.020
polynomial -type problem, but actually, as I will show you a little
01:06:33.020 --> 01:06:38.860
bit later, there has been some algorithm just recently, or some years
01:06:38.860 --> 01:06:42.960
ago, which shows that you can actually find a polynomial time
01:06:42.960 --> 01:06:44.060
algorithm for doing that.
01:06:44.420 --> 01:06:49.140
But this probabilistic time algorithm is really fast, and the
01:06:49.140 --> 01:06:56.120
interesting point is that the probability that it produces an
01:06:56.120 --> 01:06:59.180
incorrect result is marginally small.
01:06:59.500 --> 01:07:01.820
It can be made as small as you like.
01:07:02.900 --> 01:07:04.940
So, how does this work?
01:07:06.120 --> 01:07:13.000
Raban and Miller designed an algorithm where, first of all, you check
01:07:13.000 --> 01:07:20.500
the probability for just some initial small value, just take all
01:07:20.500 --> 01:07:24.140
primes less than 10,000, check whether your value that you have is
01:07:24.140 --> 01:07:25.600
divisible by that value.
01:07:26.280 --> 01:07:27.660
You can do that quite fast.
01:07:29.220 --> 01:07:37.380
And then, you look like if this did not lead to some prime factor,
01:07:38.700 --> 01:07:43.740
that for a composite value, if that value x that you would like to
01:07:43.740 --> 01:07:50.020
check is a composite number, very often you find then a value less
01:07:50.020 --> 01:07:53.320
than or equal to 10,000 which is a factor of that number.
01:07:53.500 --> 01:07:57.720
In most cases, this will already show you that this is not a prime
01:07:57.720 --> 01:07:58.060
number.
01:07:58.340 --> 01:08:04.240
But if this is not showing you, or giving you an indication that x is
01:08:04.240 --> 01:08:09.540
not prime, but a composite number, then you perform the second step.
01:08:09.860 --> 01:08:14.580
And in the second step, you repeat at most all times the following.
01:08:14.760 --> 01:08:17.940
You choose an arbitrary value that is less than x.
01:08:19.100 --> 01:08:20.000
Random value.
01:08:21.300 --> 01:08:22.080
Less than x.
01:08:23.840 --> 01:08:25.900
It's certainly larger than 10,000.
01:08:26.500 --> 01:08:27.880
That's just an arbitrary value.
01:08:30.320 --> 01:08:35.380
Until this function, witness of a and x, is true.
01:08:35.520 --> 01:08:37.160
Now, what is witness of a and x?
01:08:37.400 --> 01:08:46.240
Witness of a and x is a function which is one if a is a witness to the
01:08:46.240 --> 01:08:48.180
compositeness of x.
01:08:49.560 --> 01:08:55.800
That means if a is indicating that x is not, or showing that x is not
01:08:55.800 --> 01:08:56.560
a prime number.
01:08:58.080 --> 01:09:00.060
Now, what is this function doing?
01:09:00.220 --> 01:09:01.240
Witness of a and x.
01:09:01.300 --> 01:09:04.600
Witness of a and x works like this.
01:09:05.260 --> 01:09:11.200
If you want to get a witness of the compositeness of x, or a witness
01:09:11.200 --> 01:09:14.000
of the non-primality of x.
01:09:15.500 --> 01:09:17.440
Now, we know something about prime numbers.
01:09:18.380 --> 01:09:22.460
So we know, for example, that we know the theorem by Fermat.
01:09:22.600 --> 01:09:29.700
So if x is prime, then a to the x minus one should be congruent to one
01:09:29.700 --> 01:09:30.400
modulo x.
01:09:32.360 --> 01:09:38.200
So assume that we can show, like we have this arbitrary value a less
01:09:38.200 --> 01:09:38.680
than x.
01:09:39.840 --> 01:09:44.020
Then we should have the fact that a to the x minus one is congruent to
01:09:44.020 --> 01:09:44.940
one modulo x.
01:09:45.860 --> 01:09:52.020
If we just compute a to the x minus one, and find out that it is not
01:09:52.020 --> 01:10:00.380
congruent to one modulo x, then we would see that, okay, obviously, we
01:10:00.380 --> 01:10:02.680
have a witness to the compositeness.
01:10:02.680 --> 01:10:08.120
Now, we only know that, so we know that if this is not equal to one
01:10:08.120 --> 01:10:15.320
modulo x, then x is not prime.
01:10:18.460 --> 01:10:27.560
It does not mean that if a to the x minus one is congruent to one
01:10:27.560 --> 01:10:30.520
modulo x, x is prime.
01:10:30.520 --> 01:10:33.120
We don't have that indication.
01:10:33.920 --> 01:10:37.620
We only have the indication in the opposite way.
01:10:38.400 --> 01:10:40.360
If x is prime, then we know that.
01:10:40.440 --> 01:10:49.280
But there may be numbers which actually satisfy that equality, or that
01:10:49.280 --> 01:10:54.420
relationship, a to the x minus one is congruent to one modulo x, and
01:10:54.420 --> 01:10:56.040
they need not be prime.
01:10:56.320 --> 01:10:59.460
There are actually numbers like that, so-called Carmichael numbers,
01:11:00.040 --> 01:11:01.120
which have that value.
01:11:02.020 --> 01:11:03.080
But they are very rare.
01:11:04.300 --> 01:11:13.280
And so the idea is, if you just take an arbitrary value here, you
01:11:13.280 --> 01:11:14.980
should have that property.
01:11:16.700 --> 01:11:19.340
So, how does that work?
01:11:20.220 --> 01:11:24.000
We would like to compute a to the x minus one modulo x in order to
01:11:24.000 --> 01:11:28.520
find out whether that is congruent to one modulo x, whether it resides
01:11:28.520 --> 01:11:29.380
in the value one.
01:11:31.140 --> 01:11:35.960
And we know how to compute the power of the value a to the x minus
01:11:35.960 --> 01:11:36.320
one.
01:11:36.500 --> 01:11:42.640
We look at the binary representation of x minus one, and then do, or
01:11:42.640 --> 01:11:48.080
perform fast exponentiation following the scheme where we start with
01:11:48.080 --> 01:11:55.540
the most significant value, so we take this value and then perform
01:11:55.540 --> 01:11:58.600
successive squaring and modification.
01:11:59.520 --> 01:12:01.140
So, how do we start?
01:12:02.480 --> 01:12:05.360
The initial value b here is one.
01:12:06.820 --> 01:12:13.680
Then we compute what we said is the immediate term t, so b.
01:12:15.740 --> 01:12:22.440
And we square this value, take t times t, modulo x.
01:12:24.820 --> 01:12:34.120
And if now d is one, so this is essentially what we are interested in,
01:12:34.240 --> 01:12:36.360
a to the x minus one modulo x.
01:12:37.220 --> 01:12:39.440
We have one such power if d is one.
01:12:40.700 --> 01:12:43.320
Now this is something which we have not looked at.
01:12:43.380 --> 01:12:46.760
This is a different, or another theorem that we are actually using
01:12:46.760 --> 01:12:47.220
here.
01:12:48.040 --> 01:12:51.760
What we are finally interested in is whether the final value, after we
01:12:51.760 --> 01:12:57.600
have computed a to the x minus one mod x, that final value d, if that
01:12:57.600 --> 01:13:04.920
in the end here is not equal to one, we can conclude that x cannot
01:13:04.920 --> 01:13:06.320
have been a prime number.
01:13:07.660 --> 01:13:13.500
And then that is a firm statement, x has not been prime.
01:13:15.840 --> 01:13:22.820
If we don't have, or if d is actually one, so if a to the x minus one
01:13:22.820 --> 01:13:30.160
is equal to one, then we return false, we have not found a witness of
01:13:30.160 --> 01:13:35.820
the composedness of x, but then we can try it again.
01:13:37.180 --> 01:13:42.140
And in the intermediate step we look for a different property which
01:13:42.140 --> 01:13:46.460
also holds true for prime numbers, and this is stated here.
01:13:46.460 --> 01:13:58.740
If x is prime, and t squared is congruent to one modulo x, then t must
01:13:58.740 --> 01:14:01.320
be either one or minus one.
01:14:04.960 --> 01:14:10.620
Now this is something which can be derived by methods of number
01:14:10.620 --> 01:14:14.840
theory, and the corollary of that is, if you look at that statement,
01:14:17.800 --> 01:14:24.380
if t squared is congruent to one modulo x, so this here holds true,
01:14:25.820 --> 01:14:32.720
and this here is not true, t is not equal to one and t is not equal to
01:14:32.720 --> 01:14:37.970
minus one, then x cannot be prime.
01:14:39.570 --> 01:14:42.610
So we just take the contraposition of that, so this is just the
01:14:42.610 --> 01:14:44.150
contraposition of that.
01:14:44.150 --> 01:14:50.030
So here we have the statement a implies b, and here we have the
01:14:50.030 --> 01:14:53.270
statement not b implies
01:15:01.000 --> 01:15:01.960
not a.
01:15:02.120 --> 01:15:02.720
Contraposition.
01:15:03.640 --> 01:15:09.420
So this is exactly the same statement as in the theorem, just written
01:15:09.420 --> 01:15:10.260
in this way.
01:15:10.880 --> 01:15:18.860
Not b is t is not equal to one and t is not equal to minus one, and
01:15:20.160 --> 01:15:25.320
this would imply that x is not prime, or t squared is not equal to one
01:15:25.320 --> 01:15:29.960
modulo x, but since we assume that t squared is congruent to one
01:15:29.960 --> 01:15:32.440
modulo x, x cannot be prime.
01:15:34.160 --> 01:15:39.360
So this is a simple corollary, and this is just checked now while we
01:15:39.360 --> 01:15:43.340
are computing those squares here.
01:15:43.340 --> 01:15:45.780
t times t modulo x.
01:15:46.400 --> 01:15:50.720
Successive squaring of values is performing something like this, where
01:15:50.720 --> 01:15:56.420
as soon as we have found a value such that t squared which is the b in
01:15:56.420 --> 01:16:02.560
the moment here, is one, and t is not equal to one, t is not equal to
01:16:02.560 --> 01:16:08.700
x minus one which is congruent to minus one modulo x, then we have
01:16:08.700 --> 01:16:12.380
found a witness of the compositeness of x, a witness of the non
01:16:12.380 --> 01:16:18.900
-primality of x, on the way while we are computing a to the x minus
01:16:18.900 --> 01:16:19.720
one modulo x.
01:16:20.580 --> 01:16:27.240
And if we have not found such a value within that loop here, in the
01:16:27.240 --> 01:16:32.120
end we can check whether b is one or not, and we have this value.
01:16:33.000 --> 01:16:39.820
And this can be computed efficiently, just computing one this value,
01:16:40.600 --> 01:16:44.800
and maybe that on the path already we find such a value.
01:16:44.900 --> 01:16:50.240
Then we have at least one such value a, found out whether witness of
01:16:50.240 --> 01:17:00.660
ax is true or false, and so if witness of ax is false it does not mean
01:17:00.660 --> 01:17:04.940
that x actually is a prime number.
01:17:05.680 --> 01:17:09.580
It only means we have not found a witness of the compositeness.
01:17:10.640 --> 01:17:15.140
And, yeah, just this remark here, the complexity of primality testing
01:17:15.140 --> 01:17:17.900
has been, as I mentioned already, has been an open problem.
01:17:18.680 --> 01:17:28.020
And again, an indication of, or another occurrence of this interesting
01:17:28.020 --> 01:17:33.640
fact that quite often young students are ingenious in finding new
01:17:33.640 --> 01:17:36.440
methods because they are spoiled by standard methods.
01:17:37.200 --> 01:17:41.240
And so the polynomial time algorithm has been found by bachelor
01:17:41.240 --> 01:17:45.720
students at IIT Cantor, Indian Institute of Technology at Cantor.
01:17:45.820 --> 01:17:54.620
This problem having been stated as some assignment in some course on
01:17:54.620 --> 01:17:59.000
number theory, and those students found a nice method.
01:18:00.020 --> 01:18:07.000
So there are quite a few examples of events like that where unspoiled
01:18:07.000 --> 01:18:12.040
students found ingenious, or in an ingenious way, nice results.
01:18:12.980 --> 01:18:18.720
So, the probability of a false result of witness ax can be shown to be
01:18:18.720 --> 01:18:20.400
smaller than one quarter.
01:18:22.720 --> 01:18:27.540
Yeah, you select an arbitrary value, and you can show that the
01:18:27.540 --> 01:18:30.580
probability that you get a false result is less than one quarter.
01:18:31.500 --> 01:18:36.440
Now if you repeat that, the next choice, the next selection is
01:18:36.440 --> 01:18:37.880
independent of the first selection.
01:18:38.340 --> 01:18:41.740
Again, the probability of a false result is just one quarter.
01:18:42.480 --> 01:18:48.080
And so, repetition of that, we said we repeat that r times, up to r
01:18:48.080 --> 01:18:52.820
times, means that the probability of an incorrect result can be made
01:18:52.820 --> 01:18:56.080
less than two to the minus two r.
01:18:57.720 --> 01:19:05.400
And just increase the number of r, and you have marginally small
01:19:05.400 --> 01:19:08.220
remaining probability of a false result.
01:19:09.080 --> 01:19:13.180
And so, in this way, you can actually test primality.
01:19:14.520 --> 01:19:20.000
This is the important algorithm by Robin and Miller.
01:19:20.200 --> 01:19:25.560
It was one of the first randomized algorithms that was applied to a
01:19:25.560 --> 01:19:29.400
very significant problem, which was supposed to be very hard before.
01:19:29.940 --> 01:19:35.440
And the randomized algorithm, the randomized approach actually led to
01:19:35.440 --> 01:19:39.800
quite an improvement in the method, or in the complexity.
01:19:40.560 --> 01:19:44.800
And this is something which is done to a large extent in many
01:19:44.800 --> 01:19:47.120
different applications.
01:19:47.740 --> 01:19:51.780
Meanwhile, randomization is a very important technology or technique
01:19:51.780 --> 01:19:54.100
in algorithm design, algorithm engineering.
01:19:56.140 --> 01:20:02.460
Which could be the topic of another lecture or another course on
01:20:02.460 --> 01:20:03.520
randomized algorithms.
01:20:04.660 --> 01:20:10.240
Very sophisticated insights have been achieved there in that area,
01:20:10.760 --> 01:20:15.400
proving the way we can actually argue about complexity of algorithms.
01:20:16.160 --> 01:20:16.380
Okay.
01:20:17.060 --> 01:20:20.840
The remaining question now that we have not looked at is how do we
01:20:20.840 --> 01:20:29.200
actually find out those two numbers, c and d, such that c is prime
01:20:29.200 --> 01:20:34.140
with respect to the Euler number of n, and the product of c and d is
01:20:34.140 --> 01:20:36.640
congruent to one modulo that Euler number.
01:20:38.700 --> 01:20:40.040
Is that simple?
01:20:40.200 --> 01:20:40.880
Is that difficult?
01:20:41.080 --> 01:20:42.480
Well, actually it is quite simple.
01:20:44.020 --> 01:20:48.280
The first thing is that we can choose an arbitrary c, which is less
01:20:48.280 --> 01:20:52.300
than t minus one times q minus one, and it should be a small value in
01:20:52.300 --> 01:20:58.360
order to reduce the complexity of taking m, i, c.
01:20:59.160 --> 01:21:00.580
Just take a small value.
01:21:01.380 --> 01:21:04.060
And then you need to find that value d.
01:21:04.800 --> 01:21:05.880
How can we do that?
01:21:08.320 --> 01:21:13.140
The nice thing is that there is a simple algorithm, the Euclidean
01:21:13.140 --> 01:21:20.620
algorithm, which you know, like in the initial example for
01:21:20.620 --> 01:21:24.180
programming, very often you have the Euclidean algorithm for testing
01:21:24.180 --> 01:21:27.320
or finding the greatest common divisor of two values.
01:21:27.780 --> 01:21:28.780
Very simple algorithm.
01:21:29.260 --> 01:21:34.140
Here we use the extended algorithm.
01:21:35.760 --> 01:21:43.540
Somehow, like this, the green is sensitive to touching and also to
01:21:43.540 --> 01:21:44.400
using the pen.
01:21:44.900 --> 01:21:53.380
If I use both, then the purple also gets, sometimes doesn't know
01:21:53.380 --> 01:21:54.560
anymore which one to follow.
01:21:55.760 --> 01:22:01.400
I just have to make sure that I get the right touch here on the
01:22:01.400 --> 01:22:01.680
screen.
01:22:02.020 --> 01:22:02.220
Okay.
01:22:03.320 --> 01:22:06.180
Now, what is the extended Euclidean algorithm about?
01:22:06.680 --> 01:22:07.300
Here it is.
01:22:07.460 --> 01:22:09.080
There is some explanation of that.
01:22:10.240 --> 01:22:16.180
In the extended Euclidean algorithm we take two integers, c and e, and
01:22:16.180 --> 01:22:21.820
we would like to compute integers x, y, and r such that we find out
01:22:21.820 --> 01:22:24.420
the greatest common divisor of c and e.
01:22:24.860 --> 01:22:28.580
This is what the normal standard Euclidean algorithm does.
01:22:29.280 --> 01:22:33.660
But at the same time, we would like to find out also those values x
01:22:33.660 --> 01:22:42.360
and y such that ex plus cy is exactly that greatest common divisor.
01:22:43.160 --> 01:22:46.760
Normally, we just look at r.
01:22:48.300 --> 01:22:50.440
Why are we interested in those x and y?
01:22:51.140 --> 01:22:57.260
So, for our problem, what we are interested in is, that was the
01:22:57.260 --> 01:23:02.400
statement we have in the RSA algorithm, for integers c and e, and e in
01:23:02.400 --> 01:23:07.120
this case is t minus one times t minus one, the Euler value of the
01:23:07.120 --> 01:23:16.800
Euler number of n, and we know that c is prime with respect to e, that
01:23:16.800 --> 01:23:21.800
means we know that gcd of c and e is one, so we actually don't have to
01:23:21.800 --> 01:23:25.080
compute something here to find out the greatest common divisor.
01:23:27.040 --> 01:23:31.840
But if we have that, we would like to find...
01:23:31.840 --> 01:23:37.800
our problem is to find a d such that c times d is congruent to one
01:23:37.800 --> 01:23:38.400
modulo e.
01:23:38.460 --> 01:23:39.640
That's what we are interested in.
01:23:41.060 --> 01:23:46.720
We can write that equivalently such that cd minus one is equal to a
01:23:46.720 --> 01:23:47.580
multiple of x.
01:23:51.450 --> 01:23:56.750
Yeah, that was the definition of cd is congruent to one modulo e, so
01:23:56.750 --> 01:23:59.490
cd minus one is a multiple of x.
01:24:00.550 --> 01:24:03.670
No, not a multiple of x, certainly also a multiple of x, but a
01:24:03.670 --> 01:24:04.290
multiple of e.
01:24:05.750 --> 01:24:12.590
Or I could say if I rewrite that, e times minus x plus c times d is
01:24:12.590 --> 01:24:13.290
equal to one.
01:24:14.210 --> 01:24:15.550
That's the same equation.
01:24:17.190 --> 01:24:20.390
And this is what we have written up there.
01:24:22.410 --> 01:24:29.790
Yeah, so what we're interested in is this value d, which is the value
01:24:29.790 --> 01:24:36.950
y of that result of applying the extended Euclidean algorithm that
01:24:36.950 --> 01:24:37.750
we're interested in.
01:24:38.250 --> 01:24:42.590
We have to find out what that value is, the value y.
01:24:42.930 --> 01:24:46.510
This is the value d that we're interested in in our problem.
01:24:48.470 --> 01:24:49.110
Okay.
01:24:52.130 --> 01:24:58.290
So, the method that we use for the definition of the extended
01:24:58.290 --> 01:24:59.850
Euclidean algorithm looks like this.
01:25:00.930 --> 01:25:03.470
We have an iterative approach.
01:25:03.470 --> 01:25:09.970
We start with some initial values, have a sequence of values a, x, y.
01:25:11.070 --> 01:25:20.110
a0 is e, a1 is c, x0 is 1, x1 is 0, y0 is 0, y1 is 1.
01:25:20.730 --> 01:25:29.930
Then we have to compute ui, which is just the floor of the division of
01:25:29.930 --> 01:25:31.870
ai minus 1 over ai.
01:25:32.590 --> 01:25:37.350
In the first case, that would be e over c.
01:25:38.910 --> 01:25:40.390
Take the floor of that.
01:25:42.790 --> 01:25:50.530
And then we have to compute ai from ai minus 2 and ai minus 1.
01:25:51.330 --> 01:25:59.510
So just take the remainder that we have in the ai minus 1 over ai.
01:26:00.450 --> 01:26:09.810
So we just take the remainder of that division of ai minus 2 by ai
01:26:09.810 --> 01:26:10.730
minus 1.
01:26:12.230 --> 01:26:16.650
And then we have, for xi we have the same type of equation.
01:26:16.910 --> 01:26:19.130
For yi we have the same type of equation.
01:26:20.230 --> 01:26:25.950
And we can show that we have the following statements here.
01:26:27.350 --> 01:26:30.930
These values ai are getting smaller and smaller.
01:26:32.390 --> 01:26:40.910
And so if we look at the first index where ak gets 0, and then the
01:26:40.910 --> 01:26:45.870
greatest common divisor of this ak minus 1, then is exactly the
01:26:45.870 --> 01:26:47.590
greatest common divisor of those values.
01:26:47.750 --> 01:26:52.230
This is exactly what is done by the Euclidean algorithm.
01:26:53.390 --> 01:26:59.970
And in all the intermediate stages, we have this relationship between
01:26:59.970 --> 01:27:02.110
xi, yi, and ai.
01:27:02.970 --> 01:27:07.170
E times xi plus c times yi is ai.
01:27:07.930 --> 01:27:15.410
That means that if ak minus 1 is that greatest common divisor, then yi
01:27:15.410 --> 01:27:18.170
minus 1 is that value that we are interested in.
01:27:18.870 --> 01:27:26.910
So the moment where we have ak is 0, we have actually computed the
01:27:26.910 --> 01:27:29.050
value d that we are interested in.
01:27:29.830 --> 01:27:32.530
And so this is the extended Euclidean algorithm.
01:27:32.690 --> 01:27:38.450
It works very fast, so we can easily compute the value d such that
01:27:38.450 --> 01:27:44.150
here we have c times d congruent 1 modulo e.
01:27:44.570 --> 01:27:50.930
But when I say very easily, very fast, it certainly means division of
01:27:50.930 --> 01:27:53.010
quite large values.
01:27:53.230 --> 01:27:57.750
E is this product of t minus 1 and q minus 1.
01:27:58.150 --> 01:27:59.710
We know that these are very large numbers.
01:28:00.230 --> 01:28:04.510
So the numbers that we have here are very long, are multiple worth
01:28:04.510 --> 01:28:10.650
numbers, so it is a little more arithmetic, but it is reasonably fast.
01:28:11.510 --> 01:28:16.570
So consequently, then if the greatest common divisor of c and e is 1,
01:28:16.770 --> 01:28:25.390
then y is the multiplicative inverse of c modulo e and means that y is
01:28:25.390 --> 01:28:27.470
the required value of d, what I just indicated.
01:28:28.150 --> 01:28:30.110
So this is the RSA algorithm.
01:28:30.550 --> 01:28:38.370
The application of that would be to just encrypt messages.
01:28:38.670 --> 01:28:41.830
You don't have the problem of key transfer.
01:28:42.290 --> 01:28:43.910
You just have to know the public key.
01:28:43.910 --> 01:28:46.570
You can encrypt using the public key.
01:28:46.710 --> 01:28:48.370
You can decrypt using the secret key.
01:28:48.610 --> 01:28:51.010
The secret key need not be distributed.
01:28:51.430 --> 01:28:52.990
It must not be distributed.
01:28:55.450 --> 01:28:59.390
So the only thing is that you have to get to know the public key, and
01:28:59.390 --> 01:29:03.590
we will see later that that still becomes a problem, because you have
01:29:03.590 --> 01:29:07.270
to know that this is actually the appropriate public key of the person
01:29:07.270 --> 01:29:08.650
that you are sending the message to.
01:29:10.190 --> 01:29:15.550
So you have fewer number of keys, you only have k key pairs for k
01:29:15.550 --> 01:29:18.050
partners and not k squared and so forth.
01:29:18.550 --> 01:29:23.330
The disadvantages are that you have high computational costs, and if
01:29:23.330 --> 01:29:31.250
you have only few possible messages, then it is very simple to find
01:29:31.250 --> 01:29:32.970
out the plaintext message.
01:29:33.910 --> 01:29:41.090
Because, like, if you have only very few messages, m1 to mk, you would
01:29:41.090 --> 01:29:49.370
just encrypt them using the public key so we would have p of m1, p for
01:29:49.370 --> 01:29:57.690
mk, and if you observe the communication, which is encrypted, you just
01:29:57.690 --> 01:30:02.790
check whether one of those encrypted values is communicated, and you
01:30:02.790 --> 01:30:04.450
know what the original value was.
01:30:04.570 --> 01:30:07.770
Because if you know the plaintext messages, and you encrypt it with
01:30:07.770 --> 01:30:14.270
just a small number of values, for example, certain shares and certain
01:30:14.270 --> 01:30:19.730
assets in the stock market, if you know the values, like you would
01:30:19.730 --> 01:30:22.710
like to find out what are the recommendations, what kind of assets
01:30:22.710 --> 01:30:28.690
could you actually buy, and this is kept secret in communication, you
01:30:28.690 --> 01:30:32.250
know the possible values can be communicated, you can easily find out
01:30:32.250 --> 01:30:35.030
what's communicated if you just use that simple method.
01:30:35.910 --> 01:30:39.770
And this looks quite disappointing, because it shows that it's not
01:30:39.770 --> 01:30:40.670
that secure, really.
01:30:40.970 --> 01:30:45.030
Because you can easily compute those encrypted values, and then check
01:30:45.030 --> 01:30:49.090
for occurrence of those encrypted values, and there's no security
01:30:49.090 --> 01:30:49.390
anymore.
01:30:50.370 --> 01:30:52.830
And how to deal with that will be the topic of next week.
01:30:53.250 --> 01:30:54.810
Okay, thank you, that's it for today.