WEBVTT 00:06.200 --> 00:07.140 Okay. 00:08.560 --> 00:09.440 Good morning. 00:09.700 --> 00:13.000 Welcome you back to our course on Algorithms for Internet 00:13.000 --> 00:13.740 Applications. 00:13.980 --> 00:18.400 Hope you had a good time over Christmas and New Years and wish you a 00:18.400 --> 00:19.000 Happy New Year. 00:19.280 --> 00:20.960 Hope that it is successful for all of us. 00:21.980 --> 00:26.740 And now we have to look again at cryptographic algorithms. 00:27.180 --> 00:32.540 As you remember, last time we looked at cryptographic algorithms. 00:32.540 --> 00:37.600 You remember we had looked at all kinds of different algorithms. 00:37.860 --> 00:40.560 We had looked at the requirements for secure communication. 00:40.900 --> 00:46.420 We have looked at simple methods of encryption like Caesar Cipher, 00:47.140 --> 00:49.480 Table Cipher or Visionnaire Cipher. 00:50.400 --> 00:53.580 I hope you all worked on that programming assignment. 00:53.580 --> 01:03.740 Then we looked at the very old standard algorithm, the DES algorithm. 01:04.440 --> 01:08.260 And I showed you the essential ingredients of that. 01:08.820 --> 01:14.840 The Feistel rounds and their property that it is possible to use them 01:14.840 --> 01:18.060 for encryption and for decryption in a very similar way. 01:18.060 --> 01:20.860 So that was one important point. 01:20.980 --> 01:25.620 And then this was the explicit way the Feistel rounds are implemented 01:25.620 --> 01:29.080 in the DES algorithm using these S-boxes. 01:29.680 --> 01:34.940 Then we looked at a few more details and I showed you something about 01:34.940 --> 01:37.740 the cryptanalytic attacks. 01:38.720 --> 01:44.400 And I, in particular, pointed out the problems of side-channel 01:44.400 --> 01:45.080 attacks. 01:45.080 --> 01:50.180 So that means that if you prove something about the security of a 01:50.180 --> 01:55.060 certain algorithm, you always have to consider also vulnerabilities 01:55.060 --> 01:59.620 due to the side-channel attacks that attack an algorithm in completely 01:59.620 --> 02:05.020 different ways than you would anticipate if you just look at the 02:05.020 --> 02:08.340 algorithm and how it actually does something and you are certain that 02:08.340 --> 02:09.580 it is safe. 02:09.580 --> 02:14.800 You have to look at these things like measuring the power consumption 02:14.800 --> 02:18.920 or other things that I pointed out to you here. 02:19.700 --> 02:24.380 So then we looked at further things. 02:24.640 --> 02:33.000 We looked at the public key cryptosystems and I showed you the 02:33.000 --> 02:33.600 requirements. 02:33.600 --> 02:41.480 I showed you the way the RSA cryptosystem works designed by Rivis, 02:41.540 --> 02:42.440 Chamier, and Edelman. 02:42.800 --> 02:47.500 And here the important point is that you use a number of theoretic 02:47.500 --> 02:55.760 properties in order to get the desired effect that you can encrypt and 02:55.760 --> 03:00.380 decrypt information in a way that is quite secure. 03:00.380 --> 03:05.380 At least we think so currently since we don't have quantum computers 03:05.380 --> 03:05.860 available. 03:07.080 --> 03:11.780 The problem is that what we need or what we would need in order to 03:11.780 --> 03:16.000 break that code is to just be able to factorize large numbers and 03:16.000 --> 03:17.900 that's considered to be a very hard problem. 03:18.520 --> 03:23.040 So that's why we think that it is quite safe. 03:23.040 --> 03:28.680 Here on this slide where I put quite a few annotations on which you 03:28.680 --> 03:31.800 can only follow really if you look at the recorded lecture. 03:33.200 --> 03:41.040 Here I showed that we have these statements from number theory, 03:41.540 --> 03:45.240 Fermat's little theorem, and Euler's theorem which are heavily used in 03:45.240 --> 03:50.060 order to show that the RSA algorithm is functionally correct. 03:50.060 --> 04:00.300 That was the next slide where we showed how we actually, or how that 04:00.300 --> 04:00.740 works. 04:00.820 --> 04:07.140 So that actually this value M taken to the power C times D gives back 04:07.140 --> 04:14.600 the same value taken to the modulus N where N is this product of two 04:14.600 --> 04:16.200 large prime numbers. 04:17.360 --> 04:20.640 So this was the RSA algorithm. 04:20.840 --> 04:23.440 I showed you something about the cost of that algorithm. 04:24.340 --> 04:31.280 And this was a brief slide on showing you the complexity of taking 04:31.280 --> 04:32.660 some number to some power. 04:32.780 --> 04:38.320 So the algorithms for exponentiation which are essential for the RSA 04:38.320 --> 04:38.880 algorithm. 04:39.400 --> 04:43.240 Actually to implement the RSA algorithm you need quite sophisticated 04:43.240 --> 04:45.380 methods for exponentiation. 04:46.600 --> 04:52.720 And the first approach would be to use this algorithm which certainly 04:52.720 --> 04:56.760 is used but it is extended by further details which I don't show you 04:56.760 --> 05:01.620 because they go beyond that what I can present you in this course. 05:02.340 --> 05:06.520 But the first thing is that you notice that you can take a number to 05:06.520 --> 05:13.880 the power, in this case power, N, X to the N, with log N or 05:13.880 --> 05:19.240 essentially two log N multiplications which is an important point to 05:19.240 --> 05:19.560 notice. 05:19.680 --> 05:22.320 And we saw here that we have two ways of doing that. 05:22.720 --> 05:26.980 Either starting with the least significant bit, A0, and then 05:26.980 --> 05:32.780 multiplying all these different powers of X which are just obtained by 05:32.780 --> 05:34.780 successive squaring of X. 05:35.060 --> 05:43.100 Or starting with the highest significant bit, A K, and then taking or 05:43.100 --> 05:47.780 squaring X and multiplying again with X and squaring again and so on. 05:47.840 --> 05:52.280 So a sequence of squaring and multiplying with that value X that is to 05:52.280 --> 05:53.480 be taken to this power. 05:53.480 --> 06:01.960 Okay, so on... then we looked at the cost of cryptanalysis and now we 06:01.960 --> 06:04.180 come to the first slide that is new today. 06:05.480 --> 06:09.400 By the way, I should mention that this, the end of this week, there is 06:09.400 --> 06:10.440 this bonus exam. 06:10.920 --> 06:14.880 I was surprised to see how many people actually registered for that 06:14.880 --> 06:15.620 bonus exam. 06:15.760 --> 06:18.420 We have 120 people who registered for that. 06:18.420 --> 06:23.040 A bit more than are actually present here in the lecture room, but 06:23.040 --> 06:28.260 that's the effect of recording a lecture so people can attend the 06:28.260 --> 06:30.400 course without actually being present in this room. 06:31.040 --> 06:37.220 Now, the problem that we have with the RSA algorithm is that we need 06:37.220 --> 06:38.160 these prime numbers. 06:38.260 --> 06:41.980 We need very large prime numbers and we certainly must be able to 06:41.980 --> 06:46.900 determine prime or to find prime numbers very fast because we want 06:46.900 --> 06:51.640 that these algorithms can be used by many people, many occasions. 06:52.060 --> 06:58.520 We have to generate these public-private key pairs and so we need 06:58.520 --> 07:03.440 effective methods for testing what a prime number actually is. 07:03.500 --> 07:07.140 So we have to find the largest prime number less than or equal to N 07:07.140 --> 07:12.120 and definitely this is a problem that people have looked at for quite 07:12.120 --> 07:12.820 some time. 07:12.820 --> 07:16.120 So there is the sieve of Eratosthenes, for example. 07:16.520 --> 07:19.920 So if you are interested of finding, for example, all prime numbers up 07:19.920 --> 07:26.480 to a certain value N, then let me briefly switch to the pen again. 07:26.860 --> 07:30.860 So we would like to get, like, the largest prime number less than or 07:30.860 --> 07:31.520 equal to N. 07:33.220 --> 07:35.480 And N certainly can be a very large number. 07:35.580 --> 07:38.940 Now, if it's a quite small number, we could write down all these 07:38.940 --> 07:39.340 numbers. 07:39.340 --> 07:42.020 So, for example, to start here with all these numbers 07:49.060 --> 07:51.520 and so on. 07:52.060 --> 07:56.780 And then what we do is, in the sieve of Eratosthenes, we delete the 07:56.780 --> 07:57.520 first numbers. 07:57.780 --> 08:01.720 Well, certainly to start with one doesn't make sense. 08:01.860 --> 08:04.460 We should skip that immediately. 08:04.940 --> 08:14.120 But we check for all non-trivial factors of numbers. 08:14.120 --> 08:19.520 So what we do is we first look at all the multiples of 2. 08:19.700 --> 08:27.240 So we delete the first number, 2, 4, and then so we certainly have to 08:27.240 --> 08:29.140 delete all the even numbers. 08:29.220 --> 08:29.900 That's obvious. 08:30.280 --> 08:32.260 No even number can be a prime number. 08:32.900 --> 08:39.820 So we could have started by writing down all the uneven or the odd 08:39.820 --> 08:40.240 numbers. 08:40.240 --> 08:45.240 And then what we do is we repeat that. 08:46.400 --> 08:50.940 We delete the first number and all its multiples, 3. 08:51.720 --> 08:54.420 Now, the next multiple here is 9. 08:54.980 --> 08:57.340 Then the next multiple here is 15. 08:58.260 --> 09:01.200 Then we take the first number, which is 5. 09:02.020 --> 09:06.600 And we have to... well, there is no 1 anymore. 09:06.600 --> 09:09.800 And then we would have to delete 11. 09:09.960 --> 09:13.940 And we find that 13 in this case is the largest prime number, less or 09:13.940 --> 09:14.780 equal to 15. 09:15.360 --> 09:17.980 Which we would have known without that algorithm. 09:18.040 --> 09:21.000 But if you have a very large number, you see how this actually is 09:21.000 --> 09:21.260 done. 09:21.860 --> 09:26.420 It is quite good heuristic. 09:27.100 --> 09:32.440 But obviously if n is a very large number, then this takes quite some 09:32.440 --> 09:32.760 time. 09:32.760 --> 09:36.560 Because you have to go through all the numbers on the list from 2 to 09:36.560 --> 09:36.800 n. 09:37.200 --> 09:41.900 So this is not feasible if you have numbers having something like 512 09:41.900 --> 09:46.840 bits or 1000 bits as we need in the RSA algorithm. 09:46.840 --> 09:55.800 So this is feasible certainly for values having, well, like the range 09:55.800 --> 09:59.480 of 2 to the 10, 2 to the 20 or so it's okay. 09:59.860 --> 10:01.560 But not really more. 10:02.680 --> 10:03.920 So we need something else. 10:04.540 --> 10:08.420 And so the other approach is an approach that actually was the 10:08.420 --> 10:15.040 starting point for a sequence of algorithms that really gave us new 10:15.040 --> 10:18.600 insights about the possibility to solve problems. 10:19.200 --> 10:24.920 The essential thing is that we use a probabilistic algorithm, not a 10:24.920 --> 10:27.300 deterministic algorithm, but a probabilistic algorithm. 10:28.000 --> 10:33.240 And so what we do in a probabilistic algorithm is we flip a coin at 10:33.240 --> 10:33.860 some points. 10:34.420 --> 10:38.620 And flipping a coin in this case means that we just choose a random 10:38.620 --> 10:42.120 odd number X having 512 bits. 10:42.240 --> 10:43.320 Well, this is the first thing. 10:44.000 --> 10:48.800 Sorry, I'm not really at the point where I can start with, where I 10:48.800 --> 10:52.340 present you this probabilistic algorithm. 10:53.060 --> 10:55.260 But it will come on one of the next slides. 10:55.620 --> 11:00.340 So the idea is we choose some value X. 11:01.380 --> 11:05.220 So we don't look at all the numbers smaller than this value N. 11:05.280 --> 11:07.660 This was the problem with the sieve of Eratosthenes. 11:08.260 --> 11:12.520 And so what we do is we just choose some random number and check 11:12.520 --> 11:13.960 whether that number is prime. 11:14.740 --> 11:17.620 That means you only look at this one number, check whether it is 11:17.620 --> 11:17.980 prime. 11:18.300 --> 11:21.600 And if it is not prime, we just increase it by 2. 11:22.360 --> 11:27.440 It certainly doesn't make sense to increase it by 1, because that 11:27.440 --> 11:29.380 would be an even number which definitely is not prime. 11:29.380 --> 11:33.660 So we just choose this simple method. 11:34.100 --> 11:37.940 But the essential point here definitely is how we can test whether X 11:37.940 --> 11:38.380 is prime. 11:38.520 --> 11:42.180 And that is the point where we actually use this probabilistic method 11:42.180 --> 11:44.920 that I mentioned already. 11:45.660 --> 11:47.240 So how can we do that? 11:48.000 --> 11:54.900 And the essential approach was by Robin and Miller who found out this 11:54.900 --> 11:55.400 method. 11:55.400 --> 12:02.060 By the way, a test of primality for a long time was not known actually 12:02.060 --> 12:05.180 whether it would be in P or not. 12:05.660 --> 12:09.140 Like whether it would be a problem that could be solved with a 12:09.140 --> 12:10.360 polynomial time algorithm. 12:11.060 --> 12:15.460 And just some years ago it turned out that primality testing actually 12:15.460 --> 12:16.340 is polynomial. 12:17.260 --> 12:21.580 Certainly quite a high polynomial, but still it is polynomial. 12:21.580 --> 12:25.020 So it is not in a P-complete problem. 12:25.580 --> 12:29.640 It's not beyond P, but still it is a hard problem. 12:30.000 --> 12:34.240 And the algorithm that was found by some people, which I won't mention 12:34.240 --> 12:41.360 in the moment, it's just still too complex in order to be used very 12:41.360 --> 12:44.260 often for these prime testing. 12:44.320 --> 12:46.100 And prime testing has to be done very fast. 12:46.100 --> 12:50.240 So the idea, the essential idea, was due to Robin and Miller. 12:51.080 --> 12:57.840 And so here we have the coin flipping in the algorithm of Robin and 12:57.840 --> 12:58.020 Miller. 12:58.320 --> 13:05.180 They would like to check first whether X is divisible by some small 13:05.180 --> 13:05.500 prime. 13:05.600 --> 13:06.860 This can be done deterministically. 13:06.860 --> 13:14.040 And then, at most r times, we choose a random value less than X and 13:14.040 --> 13:22.220 check whether A is a witness for the compositeness of X. 13:22.820 --> 13:25.820 So we would like to test whether X is a prime number. 13:27.400 --> 13:30.220 And now we have to find out, is it actually a prime number? 13:30.520 --> 13:33.060 It's not a prime number if it is a composite number. 13:33.980 --> 13:39.880 And what we do here is we look for values less than X and then execute 13:39.880 --> 13:42.140 this function witness of AX. 13:42.200 --> 13:46.800 And witness of AX is a function which actually is like it's, the 13:46.800 --> 13:48.660 algorithm is shown here. 13:49.020 --> 14:01.540 It is a function which returns the value true if X actually is 14:01.540 --> 14:07.160 composite number and returns the value false if it is not a composite 14:07.160 --> 14:07.780 number. 14:09.740 --> 14:14.600 So we do this a few times, at most r times. 14:16.180 --> 14:21.360 The question now is, well, what is actually this function AX? 14:21.360 --> 14:25.680 And certainly we also have to check whether that actually gives us 14:25.680 --> 14:32.600 some certainty about the question, is that a random number or is that 14:32.600 --> 14:33.740 a prime number or not? 14:34.440 --> 14:36.940 So let's look at what witness AX actually does. 14:37.960 --> 14:41.820 The idea is to actually use two theorems. 14:43.400 --> 14:47.420 You remember the theorem by Fermat, the little theorem by Fermat, if X 14:47.420 --> 14:52.540 is a prime number, then A to the X minus one is congruent to one 14:52.540 --> 14:53.380 modulo X. 14:54.380 --> 15:06.940 What we could do is compute some, like this is the random value A and 15:06.940 --> 15:08.600 A is less than X. 15:09.720 --> 15:13.820 So we just compute A to the X minus one. 15:13.820 --> 15:20.060 And if that is not equal to one, then this would imply that X is not 15:20.060 --> 15:20.420 prime. 15:22.360 --> 15:25.600 Just the contraposition of that statement here. 15:26.440 --> 15:27.380 So that's what we check. 15:27.500 --> 15:29.980 You see, this is the final statement here. 15:30.380 --> 15:35.460 If D is not equal to one, and D in this case in the algorithm actually 15:35.460 --> 15:37.140 is A to the X minus one. 15:38.140 --> 15:41.180 If D is not equal to one, then return true. 15:41.540 --> 15:45.080 That means X is not a prime number. 15:45.500 --> 15:46.580 It is a composite number. 15:47.320 --> 15:50.060 Otherwise, we return false. 15:52.860 --> 16:02.000 So, because then we at least have not found a value which lets us 16:02.000 --> 16:05.920 indicate that X actually is not a prime number. 16:06.980 --> 16:13.660 So, this theorem does not say if A to the X minus one is equal to one, 16:14.080 --> 16:16.100 that X then is a prime number. 16:17.080 --> 16:18.240 Cannot conclude that. 16:18.440 --> 16:22.780 This is just, we just have the implication in one direction, not in 16:22.780 --> 16:23.420 the other direction. 16:24.020 --> 16:28.180 But if we can show that A to the X minus one is not equal to one 16:28.180 --> 16:32.040 modulo X, then X definitely is not prime. 16:32.970 --> 16:36.660 This is what we would like to check. 16:37.740 --> 16:46.500 But on the way to that computation of A to the X minus one, we test 16:46.500 --> 16:48.060 for an additional property. 16:48.220 --> 16:51.900 And this additional property which I just cite here is the following. 16:51.900 --> 16:59.920 If X is a prime number and T square... 16:59.920 --> 17:02.280 No, what is T? 17:05.760 --> 17:12.840 This is just some value. 17:12.840 --> 17:21.440 So, if X is prime and T square is congruent to one modulo X, then this 17:21.440 --> 17:25.560 number T is either one or minus one. 17:26.480 --> 17:36.080 Now, minus one is, in this case, we talk about arithmetic modulo X. 17:37.660 --> 17:46.380 Minus one is the value X minus one modulo X. 17:46.380 --> 17:53.200 So, the inverse of one with respect to addition in the modulo ring, 17:54.800 --> 17:57.400 modulo X is X minus one. 17:57.400 --> 18:04.360 If we add one plus X minus one, 18:09.020 --> 18:10.080 definitely is X. 18:10.860 --> 18:18.160 And that is congruent to zero modulo X. 18:18.580 --> 18:23.880 And so, this is the inverse of one, so this is the same as minus one. 18:23.880 --> 18:28.400 And so, this is the other statement that is looked at. 18:28.660 --> 18:35.620 If we have some value T, which has the property that T square is 18:35.620 --> 18:44.680 congruent to one modulo X and X is prime, then the implication is that 18:44.680 --> 18:47.320 T must be either one or X minus one. 18:51.460 --> 18:57.580 Now, what we do here is the following in this statement or in this 18:57.580 --> 18:59.100 condition that we check here. 18:59.260 --> 19:04.680 That is, on the way to computing A to the X minus one, we check 19:04.680 --> 19:09.700 whether we have a value which is actually one. 19:09.820 --> 19:14.140 So, D is the intermediate value on the path to computing A to the X 19:14.140 --> 19:14.700 minus one. 19:14.700 --> 19:15.940 Initially, D is one. 19:19.800 --> 19:26.200 If D is one, and you see D here on the line above is computed as T 19:26.200 --> 19:32.640 square modulo X, so this is exactly this here, T square modulo X. 19:33.240 --> 19:40.440 If that is one, and if T has been not equal to one and not equal to X 19:40.440 --> 19:48.140 minus one, that means both these conditions are not true, then X 19:48.140 --> 19:48.980 cannot be prime. 19:49.700 --> 19:55.240 Because if T is not equal to one and T is not equal to minus one, it's 19:55.240 --> 20:02.060 the same as T is not equal to X minus one, then X is not prime or T 20:02.060 --> 20:04.420 square is not equal to one modulo X. 20:04.420 --> 20:10.960 But we know that T square, with that condition, T square is congruent 20:10.960 --> 20:12.600 to one modulo X. 20:13.000 --> 20:15.880 So, in that case, X cannot be prime. 20:16.700 --> 20:23.820 So, this statement checks for violations of four statements that refer 20:23.820 --> 20:27.800 to the contraposition of that statement here. 20:27.800 --> 20:33.500 And so, these are the two tests that are performed here. 20:35.360 --> 20:43.540 One is this test, and this can be checked on the path, on the way to 20:43.540 --> 20:49.720 actually finding or going to the, or computing A to the X minus one. 20:50.420 --> 20:54.520 It would have been sufficient, or it would be one possibility to just 20:54.520 --> 20:59.740 check for this statement here, for the little theorem of Fermat, but 20:59.740 --> 21:04.300 it is just more effective to also look at this theorem. 21:05.140 --> 21:11.300 So, what we do is we start at a value of one, and then we start with, 21:11.960 --> 21:18.500 like here, a k to a zero is supposed to be the binary representation 21:18.500 --> 21:20.820 of X minus one. 21:21.240 --> 21:23.740 We want to compute A to the X minus one. 21:24.600 --> 21:30.000 So, we have to look at the binary decomposition of, or the binary 21:30.000 --> 21:31.580 representation of that value. 21:32.180 --> 21:36.460 And now you remember our methods of fast exponentiation, where we 21:36.460 --> 21:41.740 started with the highest significant bit, which is the k in this case. 21:42.560 --> 21:45.760 So, we start with that value. 21:46.060 --> 21:47.240 Now, initially, this is one. 21:47.520 --> 21:51.240 So, initially, certainly, this just goes through. 21:51.340 --> 21:52.340 Nothing happens here. 21:52.880 --> 21:57.580 Just compute, like, T, then it gets the value of D. 21:57.780 --> 21:58.720 This is squared. 21:58.840 --> 21:59.660 This is still one. 22:00.260 --> 22:03.420 So, this here, this statement is not true. 22:03.420 --> 22:10.320 And then, if a k is one, we have to multiply D with a. 22:11.460 --> 22:13.860 This is exactly what we had to do. 22:13.980 --> 22:16.440 We had, like, we want to compute A to the X minus one. 22:16.560 --> 22:20.580 So, we have to take, to multiply the intermediate value D with a 22:20.580 --> 22:21.560 modulo X. 22:22.260 --> 22:24.600 And then, this is repeated. 22:25.280 --> 22:35.040 And so, we square it again, multiply if a I is one with a, square 22:35.040 --> 22:36.100 again, and so on. 22:36.140 --> 22:40.460 And after each squaring, we check whether this statement here is true. 22:40.680 --> 22:45.260 That means whether we have found a statement that allows us to deduce 22:45.260 --> 22:46.820 that X is not a prime number. 22:46.820 --> 22:54.300 So, we try to find incidents that show us X is not a prime number. 22:55.080 --> 22:59.080 And one is checked after each squaring of this value T. 22:59.480 --> 23:04.120 The other one is done at the end when we have computed A to the X 23:04.120 --> 23:04.720 minus one. 23:05.000 --> 23:07.740 We check whether that is actually one. 23:08.360 --> 23:12.640 If it's the value one, then it would be, or if it's not the value one, 23:12.640 --> 23:18.380 then we have a witness for the compositeness of this value X. 23:19.520 --> 23:23.940 Otherwise, we have not found a witness for the compositeness of X. 23:24.220 --> 23:30.100 That means then we choose the next random value and perform this 23:30.100 --> 23:31.760 algorithm, witness AX, again. 23:32.720 --> 23:40.480 So, to repeat again, witness AX delivers the value true if we have 23:40.480 --> 23:47.340 found some indication or proof that this value is not a prime number 23:47.340 --> 23:48.560 but a composite number. 23:48.920 --> 23:54.020 But if it returns the value false, we have no idea whether this value 23:54.020 --> 23:55.680 X actually is a prime number. 23:55.680 --> 23:59.940 We have only the statement, A has not been a witness for the 23:59.940 --> 24:01.380 compositeness of X. 24:02.460 --> 24:05.500 So we have to check for the next random value. 24:06.840 --> 24:10.460 Now, so this is the way this algorithm works. 24:10.620 --> 24:17.500 We just try to find these indications that X is not a prime number. 24:18.540 --> 24:20.420 And we do that a few times. 24:20.420 --> 24:26.640 Now, just this brief remark here that in, as I mentioned already, in 24:26.640 --> 24:32.700 2002, some students at the Indian Institute of Technology at Kanpur 24:32.700 --> 24:38.380 found out, or found an algorithm, a polynomial time algorithm for 24:38.380 --> 24:42.860 testing primality of numbers, which was quite a breakthrough because 24:42.860 --> 24:47.260 for a very, very long time, this has been an open problem. 24:47.260 --> 24:53.120 And it actually was done by two students on the bachelor level. 24:54.640 --> 24:59.400 So if you are interested in or get fascinated by some open problem, 25:00.000 --> 25:01.520 just try to work on it. 25:01.860 --> 25:02.860 Sometimes it works. 25:02.980 --> 25:07.280 There are several incidents of several times it happened that some 25:07.280 --> 25:12.520 professor just gave interesting problems as assignment problems in 25:12.520 --> 25:17.420 undergraduate courses or graduate courses, and students just, in some 25:17.420 --> 25:19.780 cases, came up with the correct answer. 25:20.600 --> 25:25.720 And this is, like, always the fact that young people who have open 25:25.720 --> 25:29.740 minds sometimes have bright ideas, and they are not spoiled by the 25:29.740 --> 25:33.700 standard methods that people who have worked for a long time on these 25:33.700 --> 25:35.540 problems actually would use. 25:35.540 --> 25:40.820 So they can use new ideas that other people have not had so far. 25:41.540 --> 25:41.740 Okay. 25:42.220 --> 25:50.540 Now, the essential point is that the probability of a false result of 25:50.540 --> 25:53.940 witness AX is smaller than one quarter. 25:54.700 --> 26:05.940 Now, false result means that you find or you get, like, if the witness 26:05.940 --> 26:12.500 AX returns true, then you would say this is a composite number, it's 26:12.500 --> 26:13.100 not prime. 26:13.640 --> 26:18.120 If it returns false, you would say, well, it's not a composite number, 26:18.480 --> 26:20.120 so you could deduce it's prime. 26:20.120 --> 26:24.980 Now, if you would say that it's prime, then it might be false. 26:25.100 --> 26:28.500 It might be that it is still a composite number, but you just didn't 26:28.500 --> 26:29.100 detect it. 26:29.840 --> 26:34.400 The interesting point is that if you just take a random number smaller 26:34.400 --> 26:39.120 than X, the probability of a false result of that function is smaller 26:39.120 --> 26:39.920 than one quarter. 26:41.300 --> 26:46.440 I don't prove this to you, this is a number theoretic thing, which is 26:46.440 --> 26:55.900 not the task of this course, but this is the essential basis for this 26:55.900 --> 26:56.640 algorithm. 26:57.940 --> 27:04.060 And so, since this test is repeated R times, every time the 27:04.060 --> 27:08.480 probability that you get a false result is less than one quarter. 27:09.640 --> 27:13.500 And so, if you repeat that R times, and these are independent 27:13.500 --> 27:21.500 selections of values A, then you can multiply the probabilities, and 27:21.500 --> 27:25.740 so you have a probability for a false result that is less than 2 to 27:25.740 --> 27:26.840 the minus 2R. 27:28.400 --> 27:33.340 If the probability of a false result is less than 2 to the minus 2R, 27:34.180 --> 27:41.760 you just have to repeat that a few times, and you can be very certain 27:41.760 --> 27:46.600 that if the algorithm did not find out that this is a composite 27:46.600 --> 27:48.240 number, it will be prime. 27:49.700 --> 27:53.360 So this is the way this algorithm works, and it is very fast, because 27:53.360 --> 27:59.420 this algorithm on the previous slide actually is a fast algorithm. 28:01.180 --> 28:07.160 It's not doing really very complex things, and this is just done R 28:07.160 --> 28:09.940 times, and this can be a very small number. 28:10.380 --> 28:12.880 It takes something less than 10, it's completely sufficient. 28:13.800 --> 28:20.760 And so, like in many cases, by the way, in many cases, this first step 28:20.760 --> 28:24.720 here, checking for the first, or checking whether X is divisible by 28:24.720 --> 28:31.580 some small prime less than 10,000, will give you the result that the 28:31.580 --> 28:37.340 number that you have chosen is not prime, and then the second step 28:37.340 --> 28:40.080 here actually will do the rest. 28:40.820 --> 28:45.840 Okay, so this is the Rabin-Miller algorithm, and the interesting point 28:45.840 --> 28:50.480 was that you had here a simple algorithm, a simple heuristic, which 28:50.480 --> 28:53.920 solved a problem that was, and still is, quite hard. 28:54.240 --> 28:58.060 It's not beyond polynomial, but still it's quite complex. 28:58.580 --> 29:04.320 And so, you have quite a reduction in complexity by using such a 29:04.320 --> 29:05.300 probabilistic method. 29:06.080 --> 29:11.220 And meanwhile, we have a broad range of technologies for actually 29:11.220 --> 29:15.740 designing probabilistic algorithms for problems that are hard. 29:15.740 --> 29:23.000 And I don't go into that area in this course, showing you something 29:23.000 --> 29:24.340 about probabilistic algorithms. 29:24.760 --> 29:28.880 For that, you would have to go to a course by Peter Zanders, who 29:28.880 --> 29:33.280 teaches a complete course on probabilistic algorithms, showing you 29:33.280 --> 29:40.220 methods on how you can actually use random decisions and algorithms in 29:40.220 --> 29:43.740 an efficient way, or in a very effective way, to actually get 29:43.740 --> 29:47.600 interesting results to hard problems. 29:48.760 --> 29:50.340 Now, one problem still remains. 29:52.100 --> 29:56.100 The first step of the RSI algorithm was to find these two prime 29:56.100 --> 29:58.040 numbers, these very large numbers. 29:58.120 --> 29:59.380 We now know how to do that. 29:59.380 --> 30:03.880 This is actually implemented also in this way in the PGP package, 30:04.340 --> 30:08.600 where they generate for you these public-private key pairs. 30:08.920 --> 30:11.140 And it's done using exactly this method. 30:11.900 --> 30:15.460 So now, we have our modulus N. 30:15.620 --> 30:19.460 We have the two values P and Q, which are both prime. 30:20.340 --> 30:27.080 Now, what we need for the RSA algorithm is this pair of values C and 30:27.080 --> 30:33.660 D, such that C times D is congruent to one modulus, the Euler number 30:33.660 --> 30:38.800 of P times Q, which is this, as you know, P minus 1 times Q minus 1. 30:40.540 --> 30:41.980 How do we do that? 30:41.980 --> 30:50.100 And here, the answer is that I just choose an arbitrary value C less 30:50.100 --> 30:52.320 than P minus 1 times Q minus 1. 30:52.480 --> 30:57.140 So, I need a value which is prime with respect to this P minus 1 times 30:57.140 --> 30:57.940 Q minus 1. 30:59.140 --> 31:06.160 You can choose a small number for that, so that reduces the complexity 31:06.160 --> 31:10.600 of the RSI algorithm if you just have at least one of those numbers. 31:11.420 --> 31:14.040 So, that would be the private key in this case. 31:14.380 --> 31:19.600 If you take a small number for that, this is not bad, but you can 31:19.600 --> 31:23.720 choose an arbitrary number that is less than P minus 1 times Q minus 31:23.720 --> 31:24.120 1. 31:24.580 --> 31:33.560 We had seen before that this works for all these values C. 31:34.540 --> 31:41.840 Okay, and then we need this value D, which has the property that C 31:41.840 --> 31:45.780 times D is congruent to one modulo P minus 1 times Q minus 1. 31:46.620 --> 31:51.640 And for that, we use the so-called extended Euclidean algorithm to 31:51.640 --> 31:57.540 test whether the greatest common divisor of C, this value C that we 31:57.540 --> 32:03.440 have just chosen here, and this product P minus 1 times Q minus 1 is 32:03.440 --> 32:03.740 1. 32:08.180 --> 32:11.060 So, this is something we have to test. 32:11.700 --> 32:19.400 We need a value C that actually has the greatest common divisor of 1, 32:19.480 --> 32:25.140 so we can say that C is prime with respect to that product. 32:25.140 --> 32:30.500 Most of those values that we choose have that property because P and Q 32:30.500 --> 32:38.100 are prime numbers, but about the product of P minus 1, Q minus 1, you 32:38.100 --> 32:39.840 have to check whether it actually is true. 32:40.480 --> 32:46.700 So, you just use that algorithm and the extended Euclidean algorithm 32:46.700 --> 32:52.940 actually produces at the same time this value D that we need and an 32:52.940 --> 32:53.920 answer to that test. 32:53.920 --> 32:59.020 So, if the answer to that test would be the greatest common divisor is 32:59.020 --> 33:05.640 larger than 1, certainly you cannot choose C, but if it is 1, then you 33:05.640 --> 33:06.960 also get that value D. 33:07.080 --> 33:08.800 And I have to show you how that is actually done. 33:09.160 --> 33:12.400 I just show you the algorithm, how it is set up. 33:12.400 --> 33:20.960 So, what we have to compute is we want to compute the greatest common 33:20.960 --> 33:29.040 divisor of C and this Euler value of the product of P and Q, which I 33:29.040 --> 33:30.660 just say, okay, it's a value E. 33:31.480 --> 33:32.800 Just some value E. 33:32.960 --> 33:36.880 We take the greatest common divisor of... 33:36.880 --> 33:43.800 I want to compute that greatest common divisor of C and E and so these 33:43.800 --> 33:50.500 are C and E and we want to compute integers X, Y, and R such that E 33:50.500 --> 33:58.940 times X plus C times Y is the greatest common divisor of C and E, 33:59.420 --> 34:00.700 which is equal to R. 34:05.740 --> 34:09.780 So, why is that an answer to our problem? 34:10.420 --> 34:24.900 If we have that result, then we know that C times Y is equal to R 34:24.900 --> 34:28.440 minus E times X. 34:32.260 --> 34:40.320 And that means that we have here, like if R is 1, we see that, like we 34:40.320 --> 34:52.840 look at a value such that C times D is congruent to 1 modulo E and so 34:52.840 --> 35:02.140 we have exactly, we have C times Y then is a multiple of X and we have 35:02.140 --> 35:08.320 here just, if R is 1, we have exactly what we wanted to get. 35:08.320 --> 35:20.500 We have a value that is a multiple of 1 and, no sorry, a multiple of X 35:20.500 --> 35:27.020 plus 1 and this is what we actually need here. 35:27.020 --> 35:36.290 So, here we have the algorithm. 35:37.190 --> 35:41.610 What we do is we perform an iterative algorithm as you know from the 35:41.610 --> 35:45.150 Euler, no sorry, for the Euclidean algorithm. 35:45.590 --> 35:53.930 We start with two values A0 and A1 which we set to E and C and you see 35:53.930 --> 35:57.530 that in the first step we compute that quotient as you know from the 35:57.530 --> 35:58.430 Euclidean algorithm. 35:58.930 --> 36:09.910 You just divide E by, no, in this case you divide, yes, E by C and so 36:09.910 --> 36:14.890 E is the larger one, you divide it by C and take the, 36:17.950 --> 36:25.170 this is the integer division, so we take Qi here as the, that is the 36:25.170 --> 36:33.570 quotient of integer division of A minus 1 and Ai and then the next 36:33.570 --> 36:44.290 value as you see here, the next value is the remainder of that like Ai 36:44.290 --> 36:53.510 minus 1 times Qi minus 1 just is the, this is just the remainder of 36:53.510 --> 36:58.030 the next value Ai that is computed here and then we have some 36:58.030 --> 37:06.130 additional values X0, X1, Y0 and Y1, they are set to 1 and 0 in this 37:06.130 --> 37:14.350 way and so we have these additional values Xi is computed in that way 37:14.350 --> 37:16.470 and Yi is computed in that way. 37:17.850 --> 37:27.370 This is the setting of this, in this extended Euclidean algorithm and 37:27.370 --> 37:35.450 if we look at the smallest index such that Ak is 0, that means the 37:35.450 --> 37:45.830 remainder of dividing Ai minus 1 by Ai is 0 then the previous 37:45.830 --> 37:48.550 remainder is just the greatest common divisor. 37:48.670 --> 37:51.890 This is what we know from the Euclidean algorithm which we have seen 37:51.890 --> 37:57.690 in one of your first courses on programming, I guess but usually you 37:57.690 --> 38:01.390 don't see it with these extended values, you don't see it in this form 38:01.390 --> 38:05.370 here that you would like to compute these values X and Y at the same 38:05.370 --> 38:11.390 time and now what we have to prove looking at these settings here, you 38:11.390 --> 38:15.070 have to prove that for all i greater or equal to 0, we have this 38:15.070 --> 38:24.610 property that E times Xi plus C times Yi is equal to Ai and if we 38:24.610 --> 38:29.890 have, if we can, if we prove that, which is actually something which 38:29.890 --> 38:33.550 you can prove very easily by induction starting from these initial 38:33.550 --> 38:39.550 values, so initially for example here with X0 equal 1 and X1 is equal 38:39.550 --> 38:51.690 0, then here for example you would have that X2 is 1, no sorry, here, 38:51.930 --> 39:08.510 E times Xi, X, A0 was supposed to be E, so X0 is 1, Y0 is 0, so this 39:08.510 --> 39:19.710 is A, or this is E in this case, A0 is E and if we look at X1 which is 39:19.710 --> 39:25.390 0 and Y1 which is 1, we have that A1 is actually C, which is the 39:25.390 --> 39:26.370 setting that we have there. 39:27.370 --> 39:31.570 So this is easily checked, you can look at the inductive step there, I 39:31.570 --> 39:36.250 don't want to go in this induction which can be done easily, but which 39:36.250 --> 39:41.330 is just checking these equations and I don't want to spend time on 39:41.330 --> 39:41.570 that. 39:42.610 --> 39:49.510 Now if the greatest common divisor of C and E now is 1, then Y is the 39:49.510 --> 39:54.950 multiplicative inverse of C modulo E, that means C times Y is 39:54.950 --> 40:02.930 congruent to 1 modulo E, this is what we needed, and so this is just a 40:02.930 --> 40:11.550 consequence of that equation, and so, sorry, so that means by 40:11.550 --> 40:15.010 computing that Euclidean algorithm, which is done in a very fast way, 40:15.510 --> 40:23.710 we have that value Y, which is the requested second value for our 40:23.710 --> 40:26.050 public and private key pairs. 40:26.050 --> 40:33.470 So we have a value C then and this value D that can be, or that has 40:33.470 --> 40:35.090 this desired property. 40:35.950 --> 40:40.190 So this is the property that we need, E was the product of P minus 1 40:40.190 --> 40:49.030 and Q minus 1, then we have that second key pair, or second element of 40:49.030 --> 40:49.810 the key pair. 40:49.810 --> 40:56.690 This is sufficient for looking at these RSA, or the ingredients of the 40:56.690 --> 41:03.210 RSA algorithm, and I mentioned briefly that the implementation of the 41:03.210 --> 41:07.810 RSA algorithm requires quite some... 41:09.650 --> 41:14.990 if you would like to have that, or to really perform these 41:14.990 --> 41:18.290 multiplications in a very efficient way, you know that you have very 41:18.290 --> 41:23.150 large numbers, you have to use methods from modular arithmetic, 41:23.750 --> 41:27.030 usually you also use things like the Chinese remainder theorem to 41:27.030 --> 41:31.670 split that into several multiplications in a very sophisticated and 41:31.670 --> 41:36.930 clever way, which I have no time to actually go deeper into. 41:39.290 --> 41:45.130 And so we now look at the ways how we can actually use the RSA 41:45.130 --> 41:45.690 algorithm. 41:47.110 --> 41:50.170 So if we have such an algorithm available, having these properties, 41:50.830 --> 41:58.810 that we can encrypt and decrypt using these C and D, the advantages 41:58.810 --> 42:04.470 are that the asymmetry avoids the problem of secure key exchange. 42:04.710 --> 42:08.550 If you remember that in the symmetric methods, we had the problem that 42:08.550 --> 42:14.890 both sides for encryption and decryption needed the same key, the same 42:14.890 --> 42:20.110 secret information, and so we had to exchange that secret information 42:20.110 --> 42:23.630 as a basis for actually using this algorithm. 42:24.570 --> 42:28.710 And the asymmetry relieves us of that problem. 42:28.890 --> 42:33.650 We only have to send or to make available the public key, and then we 42:33.650 --> 42:39.490 can use the private key to decrypt something which somebody else has 42:39.490 --> 42:42.390 encrypted using the public key. 42:43.750 --> 42:48.470 So in the public key system, everybody can send encrypted messages 42:48.470 --> 42:53.690 without prior communication with the receiver, which is essential, 42:54.450 --> 43:00.230 although if you look deeper into that, it is not quite true that there 43:00.230 --> 43:05.210 is no prior communication with the receiver, because what you need is, 43:05.470 --> 43:06.630 you need the public key. 43:07.550 --> 43:11.650 You have to get that public key from somewhere, and you must be sure 43:11.650 --> 43:16.470 that this is actually the public key of the person that is the 43:16.470 --> 43:21.750 recipient of the confidential message that you would like to send. 43:21.750 --> 43:26.390 We will come back to that problem of finding out actually what the 43:26.390 --> 43:28.950 public key of somebody actually is. 43:29.970 --> 43:33.650 This is another problem in this area. 43:34.310 --> 43:39.510 But the definite advantage is, if we know, if we have ways of actually 43:39.510 --> 43:46.590 distributing public keys, then the secure communication between key 43:46.590 --> 43:53.750 partners only requires key pairs, because every person in such a 43:53.750 --> 43:59.370 communication, this person can communicate with all these others just 43:59.370 --> 44:05.810 using one key pair, whereas in the symmetric algorithms, you would use 44:05.810 --> 44:09.350 different keys for every communication. 44:11.550 --> 44:16.590 Okay, so this is an advantage, you have a reduction in the number of 44:16.590 --> 44:17.550 keys that you need. 44:17.550 --> 44:21.690 The disadvantage certainly is that you have a high computational cost 44:21.690 --> 44:25.630 for encryption and decryption, because you have to perform these very 44:25.630 --> 44:33.630 long multiplications on very long numbers, which is quite costly. 44:34.630 --> 44:40.890 And another problem is, if you have only few possible plaintext 44:40.890 --> 44:44.630 messages, certainly this is easily broken. 44:45.350 --> 44:47.290 Why is that easily broken? 44:48.450 --> 44:51.730 Now, I think I don't have, no, I don't have an example here. 44:52.350 --> 45:00.910 Assume you have some stock market and somebody is giving advice on 45:00.910 --> 45:04.790 whether, like here you have your stock market and you have certain 45:04.790 --> 45:14.650 values there, for example, like shares of ABB, of Daimler, of 45:14.650 --> 45:17.970 whatever, Siemens and so on, or IBM. 45:19.210 --> 45:23.390 So you have all kinds of shares that you would like to sell or buy. 45:24.270 --> 45:29.730 And now somebody would send messages and certainly would like to send 45:29.730 --> 45:37.330 advice on what to buy or what to sell in some confidential way, then 45:37.330 --> 45:46.470 you could say that would be messages like sell or buy one of those 45:46.470 --> 45:49.090 assets. 45:50.410 --> 45:55.230 Now, if you have only very few values, so the essential point, what I 45:55.230 --> 45:58.630 would like to, what I want to tell you is the following, that we have 45:58.630 --> 46:06.310 only a certain number of, let's say, K different messages, plain text 46:06.310 --> 46:07.990 messages, that would be sent. 46:09.030 --> 46:12.890 If you have some previous knowledge about the possible messages that 46:12.890 --> 46:17.670 can be sent, and what you would like to find out is which of these 46:17.670 --> 46:22.730 messages actually is sent, and you know that it is sent in an 46:22.730 --> 46:30.390 encrypted way, what you could do is you just take the public key, like 46:30.390 --> 46:40.500 you take the public key of that person who is sending this 46:40.500 --> 46:45.780 information, this is public, so everybody can use that public key, and 46:45.780 --> 46:51.340 so you just compute all the encryptions of those messages, which 46:51.340 --> 46:55.020 certainly are longer text as I indicated here, you just compute all 46:55.020 --> 46:58.860 the encryptions using that public key, and you know all the encrypted 46:58.860 --> 46:59.320 messages. 47:00.240 --> 47:05.040 So, if you know the plain text, you can compute all the encrypted 47:05.040 --> 47:11.540 messages using this public key, and so if somebody sends a message, 47:11.820 --> 47:18.700 one of these messages out of that pool here, to some recipient, you 47:18.700 --> 47:21.840 would like to find out which of these messages has been sent, you just 47:21.840 --> 47:26.220 look into your database that you have pre-computed using this public 47:26.220 --> 47:30.960 key, and you just don't need to know the plain text, you just check 47:30.960 --> 47:32.100 for the encrypted text. 47:33.820 --> 47:43.840 And so, if you encrypt text from some small set of possible messages, 47:44.620 --> 47:49.280 then you should not do that using a public key system. 47:49.280 --> 47:55.300 Because everybody can compute those possible messages, and just has to 47:55.300 --> 47:59.160 check for the encrypted messages, it's not necessary anymore to look 47:59.160 --> 48:00.520 at the plain text messages. 48:01.600 --> 48:06.220 So, this is a disadvantage that you have to be aware of, and so you 48:06.220 --> 48:10.780 have to use that method with care in a reasonable way. 48:11.500 --> 48:13.520 And I will show you how we actually use that. 48:13.600 --> 48:14.120 You have a question? 48:19.410 --> 48:19.930 Definitely. 48:21.530 --> 48:27.490 But if you do that, you have extended the range of possible messages 48:27.490 --> 48:31.630 definitely, so if a random number of some size, there are all kinds of 48:31.630 --> 48:35.250 possible random numbers, certainly there are ways of getting around 48:35.250 --> 48:35.550 that. 48:37.370 --> 48:42.170 But I just want to point out, and certainly there have been examples 48:42.170 --> 48:47.230 where people used the RSA algorithm or public key method in a naive 48:47.230 --> 48:49.970 way, and ran exactly into that problem. 48:50.270 --> 48:53.530 Certainly there are ways around that, and your suggestion certainly is 48:53.530 --> 49:01.730 good to just add some random number XR to that value, and then 49:01.730 --> 49:05.790 certainly you extend the set of possible messages in a reasonable way, 49:05.970 --> 49:08.170 and you have relieved that problem. 49:08.170 --> 49:11.410 But there are other ways of getting around that, and I will show you 49:11.410 --> 49:12.690 how that is actually done. 49:14.190 --> 49:18.830 What you could do certainly is use a secure key exchange, and this 49:18.830 --> 49:20.710 goes into the direction that you just mentioned. 49:22.970 --> 49:30.090 I will show you how we can actually use the public key methods for 49:30.090 --> 49:32.690 actually exchanging secret keys. 49:32.690 --> 49:37.850 But let us briefly look at how we could actually exchange secret keys 49:37.850 --> 49:39.030 in symmetric methods. 49:39.850 --> 49:46.030 So if we do that without making use of public key methods, then Alice 49:46.030 --> 49:51.230 and Bob, our two standard partners, could agree upon some general key, 49:53.370 --> 49:59.590 and could agree on that using some reasonable communication method, by 49:59.590 --> 50:01.930 phone, by letter, by courier, or whatever. 50:02.770 --> 50:08.530 And you could transmit that completely, like if this is your initial 50:08.530 --> 50:16.350 value, you could just chop that into certain segments, where segments 50:16.350 --> 50:20.470 could be actually bit segments, or could be every second bit, or every 50:20.470 --> 50:21.950 third bit, or something like that. 50:22.030 --> 50:26.790 So you can just chop that into some parts, just that the original key 50:26.790 --> 50:32.010 can be retrieved from those partial information that could be set. 50:32.170 --> 50:37.730 So there are methods of exchanging secret information if you have 50:37.730 --> 50:44.090 agreed in some way on this way you actually reconstruct the key G from 50:44.090 --> 50:48.290 those things here, these G1 to GK. 50:48.750 --> 50:55.370 This is a possibility to actually exchange some general key, and then 50:55.370 --> 51:01.770 you could generate some other keys from that general key. 51:03.390 --> 51:10.410 Or you could use a new random session key for every... 51:10.410 --> 51:17.330 Then the second step here is that you use a new random session key for 51:17.330 --> 51:18.650 every exchange of messages. 51:18.890 --> 51:22.610 So whenever you want to exchange a message, you just use a random key 51:22.610 --> 51:23.230 for that. 51:24.390 --> 51:32.550 And you encrypt your message using this random session key. 51:33.370 --> 51:39.310 And this session key S is encrypted using this general key and sent 51:39.310 --> 51:40.350 together with a message. 51:41.550 --> 51:46.510 And so you have this general key that is known to both partners, to 51:46.510 --> 51:49.150 Alice and to Bob. 51:49.670 --> 51:53.010 They have knowledge of this general key G. 51:53.450 --> 51:58.370 They can use the general key G to encrypt and decrypt their session 51:58.370 --> 51:58.830 keys. 51:59.610 --> 52:06.130 And then they can use the session key to encrypt and decrypt again the 52:06.130 --> 52:06.490 messages. 52:06.490 --> 52:12.870 So they have G and S and that, and Bob also can have access to G and 52:12.870 --> 52:13.170 S. 52:13.850 --> 52:15.490 And this is true vice versa. 52:16.070 --> 52:18.070 So this is a possibility to do that. 52:18.830 --> 52:25.070 And since this session key is just used only once, for every exchange 52:25.070 --> 52:31.330 of messages you have a new session key, you cannot really use some of 52:31.330 --> 52:34.730 these standard attacks that you send several plain text that have to 52:34.730 --> 52:36.910 be encrypted with the same key S. 52:37.070 --> 52:40.230 If it's done with a new session key every time, it's very hard to 52:40.230 --> 52:40.710 break that. 52:41.850 --> 52:46.970 But certainly you send, you always use the same value G here for 52:46.970 --> 52:51.570 encrypting the random session keys. 52:51.950 --> 52:57.150 But these session keys will be something like 64 bits or 128 bits, 52:57.510 --> 52:58.390 random values. 52:58.390 --> 53:02.330 And there's such a large number of possible values that can be sent 53:02.330 --> 53:10.970 that it is very hard to really find out what this value G is. 53:11.350 --> 53:14.190 Still, this is a vulnerability you have. 53:14.430 --> 53:20.710 Here you could certainly try to file some attack or to use some attack 53:20.710 --> 53:26.530 using different session keys and then try to find out what the general 53:26.530 --> 53:27.270 key G is. 53:27.990 --> 53:33.130 Okay, so G is used for short messages only, only for session keys. 53:33.490 --> 53:36.530 That means you have little information to actually find out something 53:36.530 --> 53:39.810 about that general key. 53:40.450 --> 53:43.610 And S is used for one message only, so it is quite secure. 53:44.690 --> 53:50.250 And so this is a way of using only symmetric methods for exchanging 53:50.250 --> 53:53.390 keys and for encrypting messages. 53:54.830 --> 53:59.990 So, it certainly is an approved protection, but this is not the only 53:59.990 --> 54:00.990 way of doing that. 54:01.070 --> 54:05.970 We can use public key methods for exchanging keys and we do that in 54:05.970 --> 54:06.810 the following way. 54:07.290 --> 54:11.050 Essentially we replace this general key with the RSA method, or the 54:11.050 --> 54:11.810 public key method. 54:12.370 --> 54:14.930 So Alice and Bob want to exchange their messages. 54:15.490 --> 54:20.930 They choose a new session key for that and so this is the session key. 54:21.590 --> 54:23.890 And then the session key is used to encrypt the message. 54:25.070 --> 54:29.230 And for that we use some sufficiently secure symmetric method. 54:29.830 --> 54:33.730 As on the previous slide, here we use just the symmetric method for 54:33.730 --> 54:34.090 that. 54:34.570 --> 54:37.290 Whatever Alice and Bob like to use. 54:37.910 --> 54:42.570 Certainly not DES, but some other method, unless DES is sufficiently 54:42.570 --> 54:43.830 secure for their purposes. 54:44.590 --> 54:50.070 And then we encrypt the session key with the public key. 54:50.310 --> 54:51.410 So this is the next step. 54:51.670 --> 54:59.690 That the public key is used of some public key method to encrypt the 54:59.690 --> 55:00.350 session key. 55:00.770 --> 55:06.110 And then the encrypted message is sent together with the encrypted 55:06.110 --> 55:06.630 key. 55:07.690 --> 55:13.010 And sometimes we say that the key is put into some sealed envelope. 55:13.010 --> 55:15.990 You cannot really get to that content. 55:16.670 --> 55:22.570 So this is just this encrypted session key which is sent to Bob. 55:22.930 --> 55:31.390 And then he can use his private key to actually retrieve the session 55:31.390 --> 55:33.890 key that Alice used for encrypting the message. 55:34.210 --> 55:37.290 And in that way he can decrypt this message. 55:37.290 --> 55:43.030 So this is the way you can use now a public key method. 55:43.690 --> 55:47.110 Before on the previous slide I showed you essentially the same thing. 55:47.350 --> 55:52.130 But there we didn't use the public private key pairs for encrypting 55:52.130 --> 55:52.830 session keys. 55:53.050 --> 55:59.810 But here we use, or there we use just the idea of a general key. 55:59.970 --> 56:03.330 But then you still have the problem of exchanging this general key. 56:03.330 --> 56:07.590 And so here we have the advantage of just using a public private key 56:07.590 --> 56:07.930 pair. 56:08.370 --> 56:14.250 And as long as Alice knows what the public key of Bob is, she can use 56:14.250 --> 56:14.910 that method. 56:15.190 --> 56:20.630 And nobody else can actually retrieve the encrypted session key unless 56:20.630 --> 56:24.770 that other person has access to the secret key of Bob. 56:25.450 --> 56:25.850 Okay. 56:26.710 --> 56:32.250 So here there's no need for a secretly transmitted general key. 56:33.770 --> 56:37.630 The high cost of RSA certainly has to be considered. 56:38.310 --> 56:43.950 But you can only use that on the quite short session key, just a few 56:43.950 --> 56:47.930 bits of 128 or 64 bits. 56:47.930 --> 56:54.130 And so another point is that every key of the symmetric method is used 56:54.130 --> 56:54.790 only once. 56:55.470 --> 56:59.410 And so it doesn't really make sense to file an attack on that. 56:59.530 --> 57:02.510 This is a secure way of communicating. 57:03.270 --> 57:10.310 The only problem that still remains is that we have to know what the 57:10.310 --> 57:12.950 public key of the recipient is. 57:12.950 --> 57:18.670 So essentially this is one of the standard methods meanwhile for 57:18.670 --> 57:19.730 secure communication. 57:20.750 --> 57:26.190 But as I said, we have to know what this public key is. 57:27.150 --> 57:31.030 And I will come back to the problem in a moment. 57:31.670 --> 57:38.290 Another point is to use like these in way of encrypting information. 57:38.890 --> 57:41.510 You would like to avoid passive attacks in the Internet. 57:41.510 --> 57:47.130 So what you could do is encrypt every datagram sent over the Internet. 57:48.970 --> 57:55.430 Now we know a datagram has these several headers in front here. 57:55.890 --> 58:00.790 Now if we encrypt everything, then at the intermediate hops, at least 58:00.790 --> 58:05.390 up to the IP header, everything has to be decrypted again. 58:06.650 --> 58:12.970 So at least the IP header has to be transformed into plain text at 58:12.970 --> 58:13.570 every router. 58:14.090 --> 58:19.690 But that means every router must be able to decrypt and needs this key 58:19.690 --> 58:20.230 information. 58:20.910 --> 58:22.410 So this needs a fast method. 58:22.550 --> 58:25.450 We don't want to slow down the Internet traffic too much. 58:28.470 --> 58:31.910 So what we would use is a fast symmetric algorithm. 58:31.910 --> 58:35.090 We would like to get new session keys for every datagram. 58:36.210 --> 58:39.510 But that means you have to generate a new session key, encrypt that 58:39.510 --> 58:41.130 new session key, and so on. 58:41.210 --> 58:43.850 And you have to transfer that session key. 58:44.810 --> 58:48.550 But this could be done in that way. 58:50.230 --> 58:56.490 And if you would not do it that way, if the key is used for a longer 58:56.490 --> 59:02.850 period of time, then you have many chances actually for plain text 59:02.850 --> 59:03.430 attacks. 59:03.710 --> 59:09.130 So as soon as a key for encrypting the messages between two routers, 59:09.550 --> 59:15.650 you could just generate traffic on that connection between, or on that 59:15.650 --> 59:21.390 communication between two nodes in the Internet. 59:21.390 --> 59:27.110 And you could find out, or you could use these known plain text 59:27.110 --> 59:27.590 attacks. 59:28.130 --> 59:34.050 So this is something which would not be advisable to do. 59:34.430 --> 59:42.090 So one should use the session keys as rarely as possible, or just as 59:42.090 --> 59:48.350 seldom as possible, just in the best case only once. 59:48.350 --> 59:54.030 But definitely this causes significant overhead leading to reduced 59:54.030 --> 59:56.710 throughput, but you always have to pay for security that you would 59:56.710 --> 59:57.250 like to get. 59:57.530 --> 59:59.530 But this is a way you could actually use. 59:59.930 --> 01:00:05.290 There are methods using that, like IPSec, which is using encryption 01:00:05.290 --> 01:00:10.710 where you have these types of protocols included. 01:00:11.830 --> 01:00:20.130 Now, before I come to that problem of finding out what the public key 01:00:20.130 --> 01:00:26.290 of your communication partner is, I would like to briefly introduce to 01:00:26.290 --> 01:00:32.290 you two other methods for symmetric encryption, because we have seen 01:00:32.290 --> 01:00:35.990 now that symmetric encryption is something which is still around, 01:00:36.110 --> 01:00:39.690 which is very essential for encrypting large messages. 01:00:39.690 --> 01:00:46.170 And DES was one algorithm that I presented to you that was for a long 01:00:46.170 --> 01:00:47.730 time considered to be quite secure. 01:00:48.150 --> 01:00:52.170 And then there is this other method, IDEA, the International Data 01:00:52.170 --> 01:00:56.790 Encryption Algorithm, which has been designed by people independent of 01:00:56.790 --> 01:01:02.450 the United States at the ETH at Zurich in the beginning of the 90s. 01:01:02.950 --> 01:01:07.870 And this algorithm uses a longer key of 128 bits. 01:01:08.950 --> 01:01:12.530 Block size, as in DES, is also 64 bits. 01:01:12.970 --> 01:01:18.670 And it uses standard operations in a sophisticated way, as you will 01:01:18.670 --> 01:01:19.450 see in a moment. 01:01:19.830 --> 01:01:22.790 It uses operations bitwise XOR. 01:01:23.410 --> 01:01:27.270 We have seen that already in other methods, like I showed you this RC4 01:01:27.270 --> 01:01:29.150 algorithm, where we have XORing. 01:01:29.290 --> 01:01:31.750 In the EDS algorithm, we also had XORing. 01:01:31.750 --> 01:01:35.770 This is one of the standard things that you use in particular because 01:01:35.770 --> 01:01:40.110 you would like to be able to use these encryption methods in both ways 01:01:40.110 --> 01:01:41.630 for encrypting and decrypting. 01:01:42.130 --> 01:01:47.130 And so we know that XORing has the nice property that if you apply it 01:01:47.130 --> 01:01:50.990 twice with the same value, you get the original value back. 01:01:50.990 --> 01:01:55.530 And then there are two other operators, addition modulo 2 to the 16, 01:01:56.390 --> 01:02:01.410 and addition, no, multiplication modulo 2 to the 16 plus 1. 01:02:03.090 --> 01:02:06.870 Now, so these are just standard operations that are used there. 01:02:06.990 --> 01:02:11.010 And these are, they are indicated on the next slides using those 01:02:11.010 --> 01:02:17.170 symbols, this XOR symbol plus and multiplication. 01:02:18.170 --> 01:02:26.750 And here, as the authors of that algorithm showed, there is a larger 01:02:26.750 --> 01:02:28.630 diffusion effect than in DES. 01:02:29.530 --> 01:02:38.870 That means the, like if you look at the bits of the key and the plain 01:02:38.870 --> 01:02:43.230 text, if you change some bit value here, this, the effect is very 01:02:43.230 --> 01:02:48.430 large on all the other bits of the, I should say, on the encrypted 01:02:48.430 --> 01:02:49.510 message then. 01:02:49.510 --> 01:02:57.290 And I have mentioned already the necessity to have some large 01:02:57.290 --> 01:03:02.590 diffusion effect because we would like to make it difficult to attack 01:03:02.590 --> 01:03:03.830 that method. 01:03:04.090 --> 01:03:08.470 That means if you, if you, if you would have a small diffusion effect, 01:03:08.810 --> 01:03:11.450 it would be much easier to file such an attack. 01:03:12.590 --> 01:03:16.690 Now, this IDEA algorithm is actually one of the algorithms that is, 01:03:17.550 --> 01:03:19.130 that can be used with PGP. 01:03:19.490 --> 01:03:23.650 That's why I have it in here in this course. 01:03:23.990 --> 01:03:28.850 Certainly nowadays, it's also like the AES algorithm, which I will 01:03:28.850 --> 01:03:33.850 present to you also in a moment, is also one of the standard methods 01:03:33.850 --> 01:03:34.570 in PGP. 01:03:34.810 --> 01:03:38.970 But it is reasonable to know what IDEA actually looks at, it looks 01:03:38.970 --> 01:03:39.350 like. 01:03:39.350 --> 01:03:48.730 So here we have the 64-bit plain text and our 128-bit key Z. 01:03:48.730 --> 01:03:58.670 And this key, the original key here, is used to generate certain 01:03:58.670 --> 01:04:00.590 subkeys Z1 to Z. 01:04:02.870 --> 01:04:10.570 Actually, these are several subkeys which are used in successive 01:04:10.570 --> 01:04:13.770 rounds of IDEA. 01:04:13.770 --> 01:04:19.270 And so in the first iteration, what is used here are Z1 to Z6. 01:04:19.650 --> 01:04:26.590 So six subkeys that are generated from this 128-bit key Z. 01:04:27.190 --> 01:04:34.090 And the 64-bit plain text message is actually chopped into four parts 01:04:34.090 --> 01:04:35.430 of 16 bits. 01:04:36.150 --> 01:04:42.430 And these here, Z1 to Z6, are also 16-bit subkeys. 01:04:43.010 --> 01:04:48.590 And they are combined in a way that I will show you in a moment into 01:04:48.590 --> 01:04:54.430 values W1 to W1-1 to W1-4. 01:04:55.090 --> 01:04:59.250 Intermediate encrypted parts, again 16-bit values. 01:04:59.250 --> 01:05:04.410 And they are then transformed using the second iteration. 01:05:05.310 --> 01:05:10.110 It's the same structure but using different subkeys. 01:05:10.730 --> 01:05:12.270 And this is done eight times. 01:05:12.530 --> 01:05:16.850 And then there is some output transformation leading to this 64-bit 01:05:16.850 --> 01:05:17.410 ciphertext. 01:05:17.530 --> 01:05:20.810 So similar to the DES algorithm, you have several rounds here. 01:05:21.150 --> 01:05:22.970 In this case, we have eight iterations. 01:05:23.650 --> 01:05:27.890 And every iteration in this case looks like this. 01:05:27.890 --> 01:05:32.130 So this is one of those iterations. 01:05:32.450 --> 01:05:33.870 All these blocks look the same. 01:05:34.530 --> 01:05:37.390 This is the structure of such a block. 01:05:37.990 --> 01:05:45.970 Here you have the subkeys Z1, Z2, Z3, Z4, Z5, and Z6. 01:05:47.570 --> 01:05:49.610 And here are the operations. 01:05:50.230 --> 01:05:51.830 We have the bitwise XOR. 01:05:51.830 --> 01:05:54.590 We have addition modulo 2 to the 16. 01:05:55.210 --> 01:05:58.330 And multiplication modulo 2 to the 16 plus 1. 01:05:59.770 --> 01:06:03.610 And so you see how that is actually done here. 01:06:03.930 --> 01:06:06.670 There you multiply Z1 and X1. 01:06:07.130 --> 01:06:10.810 Here you actually add Z2 and X2. 01:06:11.730 --> 01:06:13.390 And then you do that. 01:06:13.610 --> 01:06:19.030 This information or this product and that sum is used in two ways. 01:06:19.030 --> 01:06:22.610 It is used here in another addition. 01:06:23.390 --> 01:06:24.390 There is another addition. 01:06:24.670 --> 01:06:27.610 This is the bitwise XOR. 01:06:27.950 --> 01:06:30.890 Here the yellow plus. 01:06:32.210 --> 01:06:34.210 And so here we have two XORing operations. 01:06:34.990 --> 01:06:41.710 This is used in a XORing operation with the results of the other two 01:06:41.710 --> 01:06:44.270 additions and multiplications. 01:06:44.970 --> 01:06:51.170 And then these XORed values here in the middle are again combined with 01:06:51.170 --> 01:06:52.770 Z5 and Z6. 01:06:53.770 --> 01:06:57.290 So you see you have here multiplication, then an addition. 01:06:57.910 --> 01:07:00.410 So those two values here are combined also. 01:07:01.490 --> 01:07:05.310 And then this again is combined to get this sum here. 01:07:05.630 --> 01:07:09.750 And then you have this value which is also used in two XORing 01:07:09.750 --> 01:07:11.430 operations. 01:07:12.770 --> 01:07:18.150 And this finally leads to those W1-1 and W1-4. 01:07:18.530 --> 01:07:22.650 So it's just a sequence of multiplication, XORing, multiplication, 01:07:23.170 --> 01:07:24.570 addition, XORing. 01:07:24.910 --> 01:07:27.830 And then you get that value there. 01:07:29.370 --> 01:07:34.550 And so what you see here immediately is that information from X1 is 01:07:34.550 --> 01:07:39.990 influencing information on every one of those parts. 01:07:39.990 --> 01:07:43.630 So from X1 here you get down to W1. 01:07:44.690 --> 01:07:51.750 You get here in this way, if you go this way to that XORing, you get 01:07:51.750 --> 01:07:53.410 into this middle box here. 01:07:53.950 --> 01:07:59.510 You get over here to that value. 01:07:59.950 --> 01:08:00.790 Here is the sum. 01:08:01.190 --> 01:08:02.830 There is a product. 01:08:02.830 --> 01:08:08.250 And then we influence that value or that operation. 01:08:08.510 --> 01:08:09.790 It's an operand to that operation. 01:08:10.310 --> 01:08:12.310 And so you get this W1-2 here. 01:08:12.430 --> 01:08:15.210 And if you look at all the different paths, you notice that 01:08:15.210 --> 01:08:21.050 information from X1 and Z1 is actually used in all these four values 01:08:21.050 --> 01:08:21.310 here. 01:08:21.310 --> 01:08:29.170 This is the same for all the combinations of Xi and Zi here. 01:08:29.770 --> 01:08:35.770 And Z5 and Z6 are also, again, influencing several parts of these, 01:08:35.890 --> 01:08:38.590 certainly only the middle parts. 01:08:38.730 --> 01:08:41.190 No, they are also influencing those parts. 01:08:41.450 --> 01:08:48.470 So Z5 and Z6 also influence all four values of that ciphertext. 01:08:48.470 --> 01:08:50.950 So that's the diffusion effect. 01:08:52.210 --> 01:09:00.990 This is just this scheme of computing, of encrypting certain values. 01:09:01.870 --> 01:09:06.650 Now, the output transformation, that was the last step. 01:09:07.090 --> 01:09:11.090 The previous slide, we had these eight iterations and then some output 01:09:11.090 --> 01:09:11.610 operation. 01:09:11.610 --> 01:09:16.750 You see that this here actually is very similar to that one. 01:09:18.370 --> 01:09:27.170 And so we have here this final step, which is just using only this 01:09:27.170 --> 01:09:29.410 initial part of the other iterations. 01:09:30.350 --> 01:09:31.750 Why is it done this way? 01:09:31.870 --> 01:09:39.290 Because in this way, you can now use this algorithm backwards and 01:09:39.290 --> 01:09:39.630 forwards. 01:09:39.630 --> 01:09:44.890 So if I go to the previous slide, this was our iteration. 01:09:45.550 --> 01:09:49.090 The output transformation now is just this initial part. 01:09:50.050 --> 01:09:55.630 And so you can either use this in that direction or in that direction. 01:09:58.310 --> 01:10:04.390 Because this initial part is now followed by this intermediate part of 01:10:04.390 --> 01:10:05.270 the iteration eight. 01:10:05.270 --> 01:10:07.810 And so again, you have eight iterations. 01:10:08.190 --> 01:10:12.150 And if you use it in that direction, you have at the end also some 01:10:12.150 --> 01:10:13.050 output transformation. 01:10:14.070 --> 01:10:19.910 And you certainly have to make sure that if you use it in the backward 01:10:19.910 --> 01:10:24.190 direction, that you use an appropriate selection of subkeys for that. 01:10:24.850 --> 01:10:32.150 But this is the major point here, that you can use this method in both 01:10:32.150 --> 01:10:34.670 ways as we did with the DES algorithm. 01:10:34.670 --> 01:10:38.110 You could use the same scheme for encrypting and decrypting. 01:10:38.650 --> 01:10:39.930 And here it's the same again. 01:10:40.270 --> 01:10:42.030 You can use it in both ways. 01:10:42.850 --> 01:10:48.430 Since we have here this simple structure, we can do it like that. 01:10:48.970 --> 01:10:51.210 And so it's not a simple structure. 01:10:51.370 --> 01:10:53.530 It's a quite interconnected structure. 01:10:54.130 --> 01:10:57.610 And the generation of subkeys is done in the following way. 01:10:57.610 --> 01:11:03.610 This is our initial key, 128 bits. 01:11:04.690 --> 01:11:12.830 And then we just have here, we just take here 16-bit parts. 01:11:13.490 --> 01:11:19.130 So we have eight 16-bit parts, which sum up to 128 bits. 01:11:19.870 --> 01:11:24.970 And then we perform a left shift by 25 bits. 01:11:25.620 --> 01:11:31.230 And then again take the 16-bit parts. 01:11:31.990 --> 01:11:35.590 And again perform left shifts of 25 bits. 01:11:36.070 --> 01:11:43.450 And always determine in this way the next subkeys for all these 01:11:43.450 --> 01:11:44.790 intermediate iteration rounds. 01:11:45.300 --> 01:11:53.350 So it's just some left shifting of the original key that is used for 01:11:53.350 --> 01:11:59.090 the encryption or for the subkey generation. 01:11:59.730 --> 01:12:06.150 But the way we separate these bits into 16-bit subkeys is just 01:12:06.150 --> 01:12:10.850 modified by this left shifting of 25 bits. 01:12:12.050 --> 01:12:17.350 So this is the way we actually get all these bits. 01:12:18.230 --> 01:12:24.450 And you see here that the initial bits of Z1 are certainly just 0 to 01:12:24.450 --> 01:12:27.770 15 and so on. 01:12:28.490 --> 01:12:38.050 And so Z9, after shifting by 25 bits, this is just the bits 25 to 40 01:12:38.050 --> 01:12:38.850 and so on. 01:12:38.850 --> 01:12:48.530 And in this way you get all these 49, no, this 49 up to 52, all these 01:12:48.530 --> 01:12:49.310 different keys. 01:12:49.310 --> 01:12:57.810 So these are all the, so this would always be the first, like what is 01:12:57.810 --> 01:13:07.350 indicated here is always the first subkey that is generated by this 01:13:07.350 --> 01:13:08.990 subkey generation scheme. 01:13:09.470 --> 01:13:15.310 Okay, so this is the method of generating the subkeys. 01:13:15.310 --> 01:13:20.230 And now, as I mentioned already, we can use the same structure for 01:13:20.230 --> 01:13:23.310 decrypting as we used for encrypting. 01:13:23.410 --> 01:13:29.910 You can check the structure and find out that the, or you look at the 01:13:29.910 --> 01:13:32.350 sequence of operations that is used there. 01:13:32.350 --> 01:13:38.090 And now we have to make sure that the subkeys that we use are actually 01:13:38.090 --> 01:13:46.090 performing inverse operations to the operations we did with the 01:13:46.090 --> 01:13:46.650 encryption. 01:13:46.650 --> 01:13:55.990 And so if we have some, if we have these nine iterations, if we 01:13:55.990 --> 01:14:03.350 include the final iteration, then we have, in every iteration we have 01:14:03.350 --> 01:14:07.190 our six subkeys that are used there. 01:14:09.450 --> 01:14:14.750 And, like in one iteration round, and then we have to generate 01:14:14.750 --> 01:14:18.090 appropriate subkeys for the decryption. 01:14:19.350 --> 01:14:26.010 And these subkeys for the decryption, like here, as I have here this 01:14:26.010 --> 01:14:29.750 remark that certainly we have eight iteration rounds plus this output 01:14:29.750 --> 01:14:33.590 transformation, so in the final iteration we only have four subkeys. 01:14:34.370 --> 01:14:42.110 These iteration, or these subkeys are chosen such that we exactly have 01:14:42.110 --> 01:14:45.710 the, or get the inverse operation. 01:14:46.850 --> 01:14:55.330 If we look at the, like here for example, ZI1' is chosen such that 01:14:55.330 --> 01:15:06.630 ZI1' times Z10-I,1 is congruent to 1 modulo this operation 2 to the 16 01:15:06.630 --> 01:15:07.290 plus 1. 01:15:07.290 --> 01:15:09.730 Let's look at that scheme again. 01:15:10.610 --> 01:15:19.290 Here we would have the operation, the modulo operation, here this Z1, 01:15:19.830 --> 01:15:26.510 no here, this is the, we start with these, so here we have such an 01:15:26.510 --> 01:15:30.910 operation, there we have such an operation, this modulo modification 01:15:30.910 --> 01:15:36.510 operation, and we have to make sure that the key that is used for the 01:15:36.510 --> 01:15:44.010 decryption actually is chosen appropriately such that the second 01:15:44.010 --> 01:15:50.930 multiplication of this value Y4 here with another value here in this 01:15:50.930 --> 01:16:01.730 case, is the appropriate value in the, sorry, in this, this is exactly 01:16:01.730 --> 01:16:05.270 the, these, like the numbering here is different from the numbering on 01:16:05.270 --> 01:16:13.230 this slide 41, but we have to make sure that these subkeys for the 01:16:13.230 --> 01:16:18.690 decryption are chosen such that these inverse operation or the, that 01:16:18.690 --> 01:16:23.430 we have inverse operations and so for the multiplications they have to 01:16:23.430 --> 01:16:28.070 multiply or the product has to be congruent to 1. 01:16:28.070 --> 01:16:33.790 And for the additive operations the sum of the keys has to add up to 0 01:16:33.790 --> 01:16:43.050 and so this is just making sure that the subkeys match those of the 01:16:43.050 --> 01:16:50.010 encryption in a reasonable way and these values, these prime subkeys 01:16:50.010 --> 01:16:55.790 can be computed from these equations in a quite simple way. 01:16:56.990 --> 01:17:01.050 And they, like the question here is whether they are actually uniquely 01:17:01.050 --> 01:17:05.850 defined, certainly they are uniquely defined, but one certainly has to 01:17:05.850 --> 01:17:12.810 prove that and the buff choice of these values guarantees that the 01:17:12.810 --> 01:17:18.770 application of IDEA to the ciphertext with these subkeys produces 01:17:18.770 --> 01:17:20.290 again the plaintext. 01:17:21.270 --> 01:17:34.330 So, that means if we use, whoops, 41 again, no, 40, if we use this 01:17:34.330 --> 01:17:38.870 structure I said here, we use it once in that way and once in the 01:17:38.870 --> 01:17:44.770 backward way, essentially we use the same structure because it looks 01:17:44.770 --> 01:17:49.050 from the algorithmic structure here, it looks the same looking from 01:17:49.050 --> 01:17:54.270 top to bottom or from bottom to top and so what we only have to do, we 01:17:54.270 --> 01:18:00.170 only have to generate different keys so in the decryption we would 01:18:00.170 --> 01:18:09.110 need these keys Z1 prime to Z52 prime based on things that we had on 01:18:09.110 --> 01:18:14.670 this slide here, this is the way we actually compute these subkeys for 01:18:14.670 --> 01:18:15.210 the decryption. 01:18:15.210 --> 01:18:20.590 So this is quite a clever algorithm, if you look at this structure, 01:18:22.090 --> 01:18:27.850 you have to, you need some experience with these encryption methods in 01:18:27.850 --> 01:18:32.430 order to find out that these are reasonable operations, these are 01:18:32.430 --> 01:18:35.890 reasonable operations because you can find out these inverse values in 01:18:35.890 --> 01:18:39.270 quite an efficient way, it's uniquely defined to get these inverse 01:18:39.270 --> 01:18:40.170 values and so on. 01:18:40.170 --> 01:18:51.710 So this is our idea algorithm and then certainly there are, and this 01:18:51.710 --> 01:18:58.190 idea algorithm is more secure than the DES algorithm, we don't have 01:18:58.190 --> 01:19:04.610 known, at least I don't know about successful attacks to that idea 01:19:04.610 --> 01:19:05.170 algorithm. 01:19:06.020 --> 01:19:14.710 There are more algorithms around like the RC4 algorithm, I think I 01:19:14.710 --> 01:19:20.710 mentioned that already, that using such a random sequence is a 01:19:20.710 --> 01:19:29.430 possible way of encrypting, just like the, what you need here is just 01:19:29.430 --> 01:19:34.330 the generator for the random sequence and so here the plain text is 01:19:34.330 --> 01:19:41.010 just XORed with a randomly generated binary sequence and if you have 01:19:41.010 --> 01:19:46.610 the same random sequence for decryption on the recipient side, you can 01:19:46.610 --> 01:19:51.170 use that for decryption, so the only thing you need is the seed value 01:19:51.170 --> 01:19:56.910 for the random generator and for RC4 the key length in the United 01:19:56.910 --> 01:20:00.510 States is 128 bits, it's a method that has been designed in the United 01:20:00.510 --> 01:20:06.010 States, and outside only 40 bits because then it's easier to break the 01:20:06.010 --> 01:20:09.930 code or to find out what the actual message was, so these are the 01:20:09.930 --> 01:20:14.330 typical export regulations of the United States, who always are 01:20:14.330 --> 01:20:18.990 sensitive that they have to know everything that is communicated 01:20:18.990 --> 01:20:23.250 across the borders of the United States and also outside of the United 01:20:23.250 --> 01:20:28.150 States, you know that if you would have an ingenious idea, you should 01:20:28.150 --> 01:20:32.070 never send that by electronic communication, because all the 01:20:32.070 --> 01:20:36.470 electronic communication is actually analyzed by certain people, 01:20:36.890 --> 01:20:40.610 although we know that even if people, if they find out interesting 01:20:40.610 --> 01:20:47.210 information, it's not always used by the institutions that should know 01:20:47.210 --> 01:20:48.290 about that information. 01:20:48.290 --> 01:20:55.870 So, nevertheless, they, like, that is the standard policy of the NSA, 01:20:56.150 --> 01:21:00.230 the National Security Agency of the United States, to check every 01:21:00.230 --> 01:21:05.030 information that is exchanged between interesting people. 01:21:06.190 --> 01:21:11.050 It is a stream cipher, and it is sensitive against attack by 01:21:11.050 --> 01:21:15.870 insertion, so if you use the same plaintext, or if you use the same 01:21:15.870 --> 01:21:21.890 seed for the random sequence, if you use the same random sequence on 01:21:21.890 --> 01:21:33.570 several plaintexts, then you can just find out certain messages, or 01:21:33.570 --> 01:21:42.010 find out information by just performing simple changes to the 01:21:42.010 --> 01:21:48.190 sequence, so you would just insert a value, some value, into your 01:21:48.190 --> 01:21:51.850 plaintext, and then look at the result, everything else remains the 01:21:51.850 --> 01:21:58.670 same, and since then the XORing is just moved by one position, you can 01:21:58.670 --> 01:22:03.230 look at the changes that you have, you know that at a certain position 01:22:03.230 --> 01:22:09.530 something was changed, was inserted, then you can analyze the changes 01:22:09.530 --> 01:22:13.590 in the ciphertext, and in that way find out the random sequence that 01:22:13.590 --> 01:22:19.170 has been used at least following that point where you inserted some 01:22:19.170 --> 01:22:20.310 information. 01:22:20.310 --> 01:22:29.470 And so, such a XORing operation is okay as long as you don't, as long 01:22:29.470 --> 01:22:35.170 as you don't use that very often, and that's what I mentioned already 01:22:35.170 --> 01:22:39.130 before, that you should not use a secret key in a symmetric method 01:22:39.130 --> 01:22:40.770 more than once, really. 01:22:43.170 --> 01:22:48.890 So, then there is, there are more algorithms, so these RC algorithms 01:22:48.890 --> 01:22:54.890 are always methods from Rivest, Rivest is one of the authors of the 01:22:54.890 --> 01:23:00.290 RSA algorithm, so it's a Rivest Cipher 4, Rivest Cipher 5, they have, 01:23:00.650 --> 01:23:07.150 Rivest has designed quite a range of symmetric methods, symmetric 01:23:07.150 --> 01:23:13.550 encryption methods, and RC5 is also one method that is used in 01:23:13.550 --> 01:23:15.850 different applications. 01:23:16.770 --> 01:23:23.630 Cast is another algorithm, generalization of DES, which is more secure 01:23:23.630 --> 01:23:24.190 than DES. 01:23:24.190 --> 01:23:28.390 So, you see there is a range of algorithms around, and then there is 01:23:28.390 --> 01:23:33.130 AES, the Advanced Encryption Standard, which is, well, here I said 01:23:33.130 --> 01:23:42.450 newly, I should, this is the current encryption standard, it's around 01:23:42.450 --> 01:23:46.430 now already for several years, so it's not that new anymore, but it's 01:23:46.430 --> 01:23:49.490 definitely the successor of the DES algorithm. 01:23:50.240 --> 01:23:56.270 And there are quite a few more algorithms around, and the next thing I 01:23:56.270 --> 01:24:00.630 will present to you is an introduction into that Advanced Encryption 01:24:00.630 --> 01:24:04.870 Standard, just that you see what kind of methods are actually used. 01:24:04.870 --> 01:24:10.050 This has been designed at the end of the 90s, there had been a 01:24:10.050 --> 01:24:17.290 competition for determining the successor to DES, and there have been 01:24:17.290 --> 01:24:23.330 several suggestions from different authors, different countries, and 01:24:23.330 --> 01:24:32.370 the interesting point is that actually not, that no algorithm, no 01:24:32.370 --> 01:24:37.270 competitor from the United States won, but somebody from Belgium. 01:24:37.270 --> 01:24:42.950 So, John Damon and Vincent Ryman were the two persons who actually 01:24:42.950 --> 01:24:47.810 were the winners of that contest. 01:24:47.810 --> 01:24:58.650 So, the winner was Reindahl, so the Vincent Ryman and John Damon, I 01:24:58.650 --> 01:25:05.050 don't know exactly how you pronounce that, but, so this was the name 01:25:05.050 --> 01:25:09.990 of the algorithm, and next time I will show you how that algorithm 01:25:09.990 --> 01:25:13.270 looks like, what its structure is, it's again an algorithm having 01:25:13.270 --> 01:25:17.890 several iterations, but in a very, with very sophisticated operations 01:25:17.890 --> 01:25:18.470 in there. 01:25:18.990 --> 01:25:23.930 You can look at all kinds of information on AES and the internet, one 01:25:23.930 --> 01:25:29.810 standard source is the URL that I highlighted here, and there's also a 01:25:29.810 --> 01:25:36.730 document on Reindahl available on the webpage of this course, so, and 01:25:36.730 --> 01:25:41.130 you can, if you are interested in using that, you have public domain 01:25:41.130 --> 01:25:47.010 programs for, again, different languages, for actually using the AES 01:25:47.010 --> 01:25:47.550 algorithm. 01:25:48.150 --> 01:25:51.330 So, next time we will look at that in more detail. 01:25:51.870 --> 01:25:54.330 Thanks for your attention today, see you again next week.