WEBVTT 00:06.010 --> 00:10.000 Okay, welcome to the last session of Algorithms for Internet 00:10.000 --> 00:12.680 Applications in the year 2009. 00:13.220 --> 00:14.980 Good that a few of you actually came. 00:16.260 --> 00:20.680 And all the others will listen to this sometime later, maybe after 00:20.680 --> 00:21.100 Christmas. 00:22.800 --> 00:27.340 So, we have been looking at cryptographic algorithms. 00:27.520 --> 00:31.540 Remember that we looked at all kinds of attacks to cryptographic 00:31.540 --> 00:33.200 algorithms. 00:33.420 --> 00:39.080 For example, at passive attacks, at active attacks, like redirection 00:39.080 --> 00:42.100 or masquerade or things like that. 00:42.120 --> 00:45.180 We have looked at different types of algorithms. 00:46.260 --> 00:50.980 I've shown you the requirements of secure algorithms or secure 00:50.980 --> 00:51.640 communication. 00:52.120 --> 00:59.000 We looked at the typical cryptosystem, where we would like to transmit 00:59.000 --> 01:02.280 some information over an insecure channel. 01:02.480 --> 01:08.720 And therefore, we will encrypt the message and decrypt it. 01:08.880 --> 01:12.240 And for that, we need certain secret information, which is the key. 01:13.160 --> 01:15.900 We have noticed that there are different methods for that. 01:15.980 --> 01:19.920 That there are symmetric methods and asymmetric methods. 01:19.920 --> 01:25.420 I showed you the simple encryption method, or I showed you, just back 01:25.420 --> 01:29.720 to this here, I showed you the Caesar cipher, the table cipher, then 01:29.720 --> 01:31.440 the Visionnaire cipher. 01:31.940 --> 01:38.980 And if you have noticed last night, the programming exercise is 01:38.980 --> 01:43.260 available on the web, where you are supposed to do a bit of work on 01:43.260 --> 01:47.620 the Visionnaire cipher, just to do some work, just to do certain 01:47.620 --> 01:49.300 things with encryption. 01:50.500 --> 01:54.080 A Visionnaire cipher certainly is not the one that everybody would use 01:54.080 --> 01:58.800 nowadays, but we had to choose something which is related to the 01:58.800 --> 02:02.860 course, having to do with the major topics. 02:03.300 --> 02:06.540 And it shouldn't be too difficult to implement. 02:07.080 --> 02:13.240 So this is something I think you can manage in that exercise. 02:13.620 --> 02:17.160 Okay, then I showed you the stream cipher, a simple one where you have 02:17.160 --> 02:22.440 just a random sequence as a key, or the actual key is the seed for 02:22.440 --> 02:25.120 this random sequence generator. 02:25.900 --> 02:33.900 I showed you then the DES algorithm, where we noticed that there are 02:33.900 --> 02:40.480 16 rounds of certain simple, or not very simple, but standard 02:40.480 --> 02:44.600 encryption mechanisms, which are Feistel rounds. 02:45.080 --> 02:50.420 We looked at the details of these Feistel rounds, which have the major 02:50.420 --> 02:53.860 property that we can use them both ways for encryption and for 02:53.860 --> 02:54.420 decryption. 02:55.040 --> 03:00.540 And so this is something which is quite interesting, how this actually 03:00.540 --> 03:01.220 can be done. 03:01.380 --> 03:05.420 You know, you notice that, or you know that there are, that XORing is 03:05.420 --> 03:06.640 one of the major operations. 03:06.900 --> 03:12.960 The XORing actually is the idea behind this possibility to retrieve 03:12.960 --> 03:17.460 the plain text from the ciphertext, because you just have to generate 03:17.460 --> 03:24.200 appropriate information that is applied twice if you decipher an 03:24.200 --> 03:25.700 encrypted text. 03:26.100 --> 03:31.160 Okay, we looked at these expansion permutations, we looked at this 03:31.160 --> 03:33.960 generation of keys, we looked at the S-box. 03:34.420 --> 03:39.600 So the next slide here was the S-box, where I showed you how actually 03:39.600 --> 03:46.720 these six bits are transformed again to four bits by using the six 03:46.720 --> 03:49.380 bits as addresses in some table. 03:49.980 --> 03:55.200 And we have several, like eight S-boxes, which are each four by 03:55.200 --> 04:00.340 sixteen tables, showing how to map these values. 04:00.960 --> 04:06.220 Okay, and the final thing I did last time was to mention that there 04:06.220 --> 04:07.880 are all kinds of attacks. 04:09.520 --> 04:14.640 And so I would like to start again today with the first presented 04:14.640 --> 04:19.320 slide, where we look at typical cryptanalytic attacks on DES. 04:19.500 --> 04:23.960 You know that DES is no longer assumed to be secure of, or no longer 04:23.960 --> 04:31.300 viewed to be secure, because it is meanwhile possible to decrypt DES 04:31.300 --> 04:35.120 encrypted text, even if you don't spend too much money. 04:35.560 --> 04:40.780 But too much money is a relative thing, it can be a few hundred 04:40.780 --> 04:45.940 thousand dollars, but if the message that you can decrypt is highly 04:45.940 --> 04:49.420 sensitive, then this might be worth the investment. 04:49.820 --> 04:54.280 So the brute force attack certainly is not really feasible. 04:54.880 --> 04:58.620 You would have to test all the different keys. 04:59.260 --> 05:02.720 Certainly there are some keys which are more reasonable than others, 05:03.140 --> 05:08.140 but so the brute force attack would be to look at all 256 different 05:08.140 --> 05:09.540 possible keys. 05:10.060 --> 05:13.960 You can always cancel out a few that are very insecure. 05:14.860 --> 05:20.020 In the assignments you have an example of a very insecure key, where 05:20.020 --> 05:24.440 the permutation leads to a sequence of zeros followed by a sequence of 05:24.440 --> 05:27.420 ones, and so the key in every round is actually the same. 05:27.800 --> 05:30.520 So this would be some pattern that certainly is insecure. 05:31.160 --> 05:33.040 The other ones were also quite insecure. 05:34.080 --> 05:38.100 But if you just look at that with a very rough estimate, and you 05:38.100 --> 05:43.260 assume that you have, for example, a one tera instruction per seconds 05:43.260 --> 05:48.260 computer or processing element, and assume you just need one 05:48.260 --> 05:53.380 instruction per encryption, which is definitely not very much. 05:53.440 --> 06:00.760 One instruction per encryption is certainly the least thing you have 06:00.760 --> 06:01.220 to do. 06:01.740 --> 06:09.060 Maybe you use quite a bit of pipelining, so that in every instance, at 06:09.060 --> 06:13.020 every clock cycle, you can start a new encryption. 06:13.700 --> 06:18.220 But even then, if you have one tera instructions per second, you still 06:18.220 --> 06:26.740 need something like 20 hours for actually computing all these things. 06:27.240 --> 06:30.380 But one tera instruction is quite a bit, you don't have that much 06:30.380 --> 06:31.740 power available. 06:32.180 --> 06:37.480 Although if you look, like, the fastest DS chips can do something like 06:37.480 --> 06:40.120 up to 250 million encryptions per second. 06:40.820 --> 06:45.300 So this is quite far away from one tera instructions. 06:45.820 --> 06:51.560 And even if you would have one giga encryptions per second, you would 06:51.560 --> 06:56.460 need 1000 chips working concurrently in order to achieve these one 06:56.460 --> 06:58.360 tera encryptions per second. 07:00.880 --> 07:07.920 So this is not really feasible, very expensive. 07:09.120 --> 07:17.220 So what you could do is you could try to reduce the task, like you 07:17.220 --> 07:23.140 compute for known plaintext all possible encryptions and use this to 07:23.140 --> 07:23.880 determine the key. 07:24.100 --> 07:31.900 For that you certainly need access to the, well, this encryption 07:31.900 --> 07:37.440 device, or you have to make sure that you will actually have this 07:37.440 --> 07:39.460 plaintext which is encrypted. 07:40.120 --> 07:45.540 Then you can use this to determine the key, because if you look at a 07:45.540 --> 07:50.440 certain encrypted message and you know this is your, you know the 07:50.440 --> 07:55.480 plaintext has been encrypted, then you can compare that to all the pre 07:55.480 --> 08:00.120 -processed encryptions and find out which key actually has been used. 08:00.880 --> 08:07.560 So this would be a gigantic table, and so this is also very expensive, 08:08.040 --> 08:12.200 much too high memory requirements, you wouldn't really do that. 08:13.400 --> 08:18.020 So you would have to have something like 72 times 10 to the 15 08:18.020 --> 08:19.960 different encryptions, which doesn't make sense. 08:20.840 --> 08:25.360 Then you could do that only partially, you just compute certain 08:25.360 --> 08:30.180 encryptions and then you have a smaller table, smaller database for 08:30.180 --> 08:36.520 known encryptions, and you do the rest, or the remaining encryptions, 08:36.840 --> 08:39.580 when you actually perform this attack. 08:40.720 --> 08:45.300 And there are all kinds of things in between that. 08:45.420 --> 08:51.000 You do certainly a certain number of encryptions and then, or pre 08:51.000 --> 08:56.040 -process certain things, and then you just try out certain systematic 08:56.040 --> 09:00.200 attacks to these keys. 09:01.140 --> 09:05.420 If you're interested how this actually is done for the, or has been 09:05.420 --> 09:11.100 done for the DES standard, there is the so-called Electronic Franchise 09:11.100 --> 09:17.200 Foundation, which is dealing with topics in, like security topics, in 09:17.200 --> 09:20.540 information and communication. 09:21.300 --> 09:25.240 And this is the website that, where you can look at. 09:25.340 --> 09:28.300 I don't want to go actually into this website in the moment. 09:29.980 --> 09:38.940 There have been quite a few approaches to attack the DES and they have 09:38.940 --> 09:46.280 actually shown that it is possible to decrypt DES encrypted messages 09:46.280 --> 09:48.700 at not too much 09:51.820 --> 09:52.280 expense. 09:52.940 --> 09:57.380 I thought I had a... let me just look at... no, I don't have it here. 09:59.820 --> 10:04.920 I think you can look on that website yourself, and I don't want to 10:04.920 --> 10:10.960 spend the time now to attach to the internet and go on that website. 10:12.000 --> 10:17.780 They just give a bit of information on how these attacks were actually 10:17.780 --> 10:18.340 performed. 10:19.340 --> 10:24.900 One standard method, meanwhile, to try to decrypt encrypted messages 10:24.900 --> 10:27.400 is to use so-called Differential Crypt Analysis. 10:28.140 --> 10:30.000 And for that, what you do is the following. 10:30.580 --> 10:35.880 You take a known plaintext and you encrypt the known plaintext 10:35.880 --> 10:41.880 slightly changed, like suitably chosen different plaintext. 10:42.340 --> 10:49.400 Maybe you have... you just move the plaintext by position or you just 10:49.400 --> 10:53.520 modify certain parts in that plaintext. 10:54.120 --> 10:58.520 And then you look at the differences in the keys that you... or in the 10:58.520 --> 11:00.840 encrypted text that you actually get. 11:01.400 --> 11:03.780 We know that it is very hard to 11:06.960 --> 11:13.120 get really information on the individual keys because we have this 11:13.120 --> 11:24.880 effect that we... like if this is the plaintext or the key, like 11:24.880 --> 11:29.500 plaintext or key, we know that if we change just an individual bit in 11:29.500 --> 11:34.000 the resulting ciphertext, usually all the bits will be changed. 11:34.120 --> 11:38.240 And this is the same for changing one bit in the key or changing one 11:38.240 --> 11:39.100 bit in the plaintext. 11:39.240 --> 11:45.360 So the effect of actually changing only a little bit in the plaintext 11:45.360 --> 11:52.060 and comparing the results will, at first sight, will not show you 11:52.060 --> 11:58.120 really interesting things because you have this avalanche effect that 11:58.120 --> 12:01.500 information from one bit position is spread over the complete 12:01.500 --> 12:02.600 ciphertext. 12:03.840 --> 12:07.600 Nevertheless, differential cryptanalysis turned out to be an 12:07.600 --> 12:09.820 interesting cryptanalytic attack. 12:10.300 --> 12:14.900 The most interesting thing is that this method has been published in 12:14.900 --> 12:21.680 1990 by two scientists, Biham and Shamir, and it turned out that DES 12:21.680 --> 12:25.780 is especially resistant against this type of attack. 12:26.360 --> 12:33.160 And so people assume that when DES was actually designed that those 12:33.160 --> 12:36.720 people at NSA already knew about differential cryptanalysis, about 12:36.720 --> 12:42.540 this way of attacking encrypted messages, although it had been 12:42.540 --> 12:44.840 published only 13 years later. 12:45.620 --> 12:50.740 So it is an assumption that it has been designed specifically to 12:50.740 --> 12:52.460 resist this type of attack. 12:52.860 --> 12:57.160 But certainly an institution like the NSA will not publish all the 12:57.160 --> 13:01.820 ways they know how to attack secret information. 13:03.400 --> 13:10.880 Okay, I don't go deeper into these cryptanalytic methods. 13:11.120 --> 13:18.240 I just want to mention a few aspects that are in some way orthogonal 13:18.240 --> 13:23.520 to what you would normally do, or what you would assume if you try to 13:23.520 --> 13:29.000 make a statement on the security of a cryptographic method. 13:29.840 --> 13:33.440 So what you could do is so-called physical cryptanalysis. 13:34.480 --> 13:39.220 And physical cryptanalysis is just doing the following. 13:39.660 --> 13:44.420 It's trying to change the execution of the algorithm by interfering 13:44.420 --> 13:47.100 physically with the execution. 13:47.600 --> 13:52.000 So you could try to interfere with the smart card. 13:52.560 --> 13:54.440 You change the execution of the code. 13:54.480 --> 13:56.360 How can you change the execution of the code? 13:56.960 --> 14:02.580 Well, you have control over the clock signals, over the... like you 14:02.580 --> 14:05.260 can influence in some way. 14:05.560 --> 14:11.220 If you have your smart card, there is this... somewhere there's this 14:11.220 --> 14:11.680 processor. 14:12.620 --> 14:19.860 And you can influence the clocking signals of the processor on this 14:19.860 --> 14:20.440 smart card. 14:21.000 --> 14:28.000 If you do that in a systematic way, you can manipulate the way a 14:28.000 --> 14:29.440 certain algorithm is executed. 14:30.380 --> 14:37.600 And in that way, you modify the execution of the algorithm and you 14:37.600 --> 14:42.080 observe the differences that these changes in the execution of the 14:42.080 --> 14:49.000 algorithm produce in the ciphertext that is produced from executing 14:49.000 --> 14:50.100 the DES algorithm. 14:51.500 --> 14:57.740 And people who did that in a systematic way actually were capable to 14:57.740 --> 15:01.560 systematically retrieve on the average something like five key bits 15:01.560 --> 15:03.060 per modified encryption. 15:03.840 --> 15:09.500 And in that way, they could find out information about the secret 15:09.500 --> 15:09.960 keys. 15:10.560 --> 15:14.920 And so a few attacks, something like less than 12 attacks, suffice to 15:14.920 --> 15:20.140 retrieve the key, which definitely is a very important attack. 15:20.720 --> 15:27.520 The major point that I would like to make here is that usually if you 15:27.520 --> 15:30.980 would like to prove something about your algorithm, you prove 15:30.980 --> 15:35.000 something making certain assumptions, you assume that this is the 15:35.000 --> 15:36.140 algorithm that is executed. 15:36.760 --> 15:40.120 And you prove something about the security of this algorithm, about 15:40.120 --> 15:44.800 possible attacks, you have the 16 rounds, you have certain execution 15:44.800 --> 15:49.500 of these S-boxes, you have compressions, you have XORing, and so on. 15:50.460 --> 15:57.940 You can prove certain statements on the cost of attacking that 15:57.940 --> 15:58.600 algorithm. 15:59.600 --> 16:03.040 And now somebody comes and modifies your algorithm, and in that way is 16:03.040 --> 16:07.420 capable to actually find out information on the secret information 16:07.420 --> 16:09.780 that has been used in your algorithm. 16:10.840 --> 16:14.200 And this is its so-called side-channel attack. 16:21.040 --> 16:26.820 And a side-channel attack has this name because you have a completely 16:26.820 --> 16:33.580 different access to the secret information by just changing the model 16:33.580 --> 16:37.380 that was used to make statements on the security of the code. 16:38.580 --> 16:40.040 This is very important. 16:40.560 --> 16:46.220 If you argue about the security of your algorithm, you have to take 16:46.220 --> 16:51.140 into account that there might be certain side-channel attacks that 16:51.140 --> 16:53.940 attack your algorithm in a totally unexpected way. 16:54.280 --> 16:57.420 Now, if it's totally unexpected, you cannot prepare for that, but... 16:57.420 --> 17:00.420 so you should just look for possible attacks. 17:00.900 --> 17:06.880 And another attack that was not considered before was just to measure 17:06.880 --> 17:07.820 power consumption. 17:09.940 --> 17:13.460 How can power consumption be interesting? 17:13.920 --> 17:19.920 Now, we know that CMOS circuitry behaves differently depending on 17:19.920 --> 17:25.240 whether you process a zero or a one. 17:26.680 --> 17:28.400 The power consumption is different. 17:29.460 --> 17:33.200 And so, by just measuring the power consumption, you get specific 17:33.200 --> 17:40.440 patterns, like you measure the way your power consumption looks like. 17:41.440 --> 17:48.060 And you can find out specific differences depending on the values that 17:48.060 --> 17:50.260 actually have been processed on your chip. 17:50.720 --> 17:53.800 And if you have a smart card, you definitely can measure the power 17:53.800 --> 17:55.660 consumption on that smart card. 17:57.720 --> 18:04.360 And so, you have to be careful if you design an algorithm and you know 18:04.360 --> 18:08.760 somebody might measure the power consumption, you have to design your 18:08.760 --> 18:16.060 algorithm such that the power consumption does not allow anybody to 18:16.060 --> 18:20.940 retrieve information on the bits that have been processed. 18:22.000 --> 18:27.360 So, if you have differences in key bits, or in particular in different 18:27.360 --> 18:32.280 key bits, the effect on power consumptions should be the same. 18:33.220 --> 18:37.940 It should not be visible from the power consumption what type of 18:37.940 --> 18:39.420 secret information you have used. 18:40.120 --> 18:44.720 That means you have to design your circuitry in a way such that 18:44.720 --> 18:49.440 differences between processing zeros and ones are actually compensated 18:49.440 --> 18:49.720 for. 18:52.220 --> 19:00.160 But this is a totally different aspect of designing a cryptographic 19:00.160 --> 19:00.960 algorithm. 19:02.380 --> 19:06.480 Because you have to look at the way this is actually implemented and 19:06.480 --> 19:10.900 then how that is actually executed in a physical way. 19:11.240 --> 19:15.820 You have certain characteristic features that can be observed from the 19:15.820 --> 19:17.680 physical execution of your algorithm. 19:17.920 --> 19:23.100 And these specific features that have essentially nothing to do with 19:23.100 --> 19:28.700 your algorithm, but are observable anyway, you have to deal with that 19:28.700 --> 19:33.040 and just design your hardware such that this is compensated for. 19:33.880 --> 19:40.900 So, this is the reason why I emphasize that this is very important to 19:42.560 --> 19:48.560 look at these things if you design some secure ways of communication. 19:49.260 --> 19:52.000 Now, there are even other approaches. 19:52.540 --> 19:57.800 A trivial cryptanalysis could be, well, you know this is here your 19:57.800 --> 20:02.900 area where your processor is, your small processor on a smart card, 20:03.320 --> 20:08.120 and you know that there are certain regions where the memory is. 20:08.980 --> 20:12.920 And normally there are specific regions where secret keys are stored. 20:13.740 --> 20:21.500 Now, you could just get one pin or one device for pointing at these 20:21.500 --> 20:30.000 specific locations and then you modify, you just modify individual 20:30.000 --> 20:33.840 bits by external interference with the memory locations. 20:35.560 --> 20:41.080 Now, if you modify a memory cell such that there is a 1, definitely 20:41.080 --> 20:47.560 there has to be a 1 at this position or maybe 0, then you just run the 20:47.560 --> 20:54.420 algorithm again and if you get, for example, a parity error, you know 20:54.420 --> 20:58.040 that the value was different before. 20:59.680 --> 21:05.820 So you can observe the effects of modifying individual bits of the key 21:05.820 --> 21:10.960 because you know the area where actually on the smart card the key 21:10.960 --> 21:11.820 bits are stored. 21:12.600 --> 21:13.700 This has been done. 21:14.540 --> 21:19.040 So this was possible on old-fashioned smart cards. 21:19.420 --> 21:23.280 They all had to be redesigned in order to prevent this type of attack. 21:25.080 --> 21:29.460 And also these attacks looking at power consumption, they had to be 21:29.460 --> 21:32.800 redesigned because this was too simple to retrieve the information 21:32.800 --> 21:33.760 that had been processed. 21:35.060 --> 21:35.220 Okay. 21:35.220 --> 21:42.740 By the way, you may know that if somebody would sit outside of the 21:42.740 --> 21:51.200 room and measure the effect of showing some information on the screen 21:51.200 --> 21:56.360 here, it can be determined what kind of information is on the screen 21:56.360 --> 21:57.180 of my laptop. 21:58.000 --> 22:04.780 But just analyzing the magnetic waves or whatever, the information 22:04.780 --> 22:09.440 that is displayed here or that is that this can be measured quite far 22:09.440 --> 22:09.780 away. 22:10.840 --> 22:16.400 And these are typical attacks to very secure or very, very secret 22:16.400 --> 22:17.920 information sources. 22:18.340 --> 22:24.740 So if you are actually doing something which is very, very secret, you 22:24.740 --> 22:29.820 have to completely shield off the room where the processing is done, 22:30.200 --> 22:35.840 because it must be made impossible to measure anything outside of the 22:35.840 --> 22:38.060 place where you're actually doing the information processing. 22:38.840 --> 22:44.280 And the methods there are very, very sophisticated and can really 22:44.280 --> 22:50.460 retrieve information in a way that we would not really imagine that 22:50.460 --> 22:51.320 that would be possible. 22:52.300 --> 22:55.660 So the consequence was that software-based 22:59.020 --> 23:05.720 cryptanalysis of DES certainly requires immense effort. 23:06.780 --> 23:13.520 So in 1998, there were public attacks, they had 100,000 computers on 23:13.520 --> 23:19.720 the internet, but they managed to actually meet the so-called DES 23:19.720 --> 23:22.060 challenge within 22 hours. 23:22.520 --> 23:28.260 And this was in 98, so information processing performance improved and 23:28.260 --> 23:33.980 integration density improved, so the power that we have, the 23:33.980 --> 23:37.900 information processing power we have, is much higher meanwhile. 23:38.620 --> 23:46.040 Therefore, like physical attacks succeeded quite fast on DES, so this 23:46.040 --> 23:53.440 was no longer considered to be safe, and therefore DES is no longer 23:53.440 --> 23:54.060 the standard. 23:55.300 --> 23:59.960 If you use DES, you should not use DES alone, but use triple DES, 24:00.700 --> 24:07.800 where you have triple encryption with two different keys, which are 24:07.800 --> 24:15.860 used in sequence on the blocks of data, and so triple DES is a much 24:15.860 --> 24:19.380 stronger method than single DES. 24:21.360 --> 24:26.460 I will not go into triple DES, I will show you later on two other 24:26.460 --> 24:33.740 symmetric methods in detail, the IDEA algorithm and also the AES 24:33.740 --> 24:36.860 algorithm, the new advanced encryption standard, because the advanced 24:36.860 --> 24:41.960 encryption standard, I think, is the one that you should know of 24:41.960 --> 24:44.100 nowadays, because that's the current standard. 24:44.100 --> 24:49.080 I just wanted to, like by showing you DES, I just wanted to show you a 24:49.080 --> 24:55.040 few typical approaches to designing symmetric methods, like these, 24:55.460 --> 25:01.040 like all these methods have some XORing operations in there, and like 25:01.040 --> 25:05.940 this intelligent way of using the same algorithm for encryption and 25:05.940 --> 25:08.060 decryption certainly is interesting to see. 25:09.160 --> 25:13.320 But the major problem of symmetric methods is that if you want to 25:13.320 --> 25:17.680 communicate securely between n persons, like you have here all your 25:17.680 --> 25:21.840 persons, if you would like to have secure communications, you just 25:21.840 --> 25:26.280 need, like if one person communicates with all these different others, 25:26.920 --> 25:32.300 you just need n squared keys, because you need secure communication 25:32.300 --> 25:37.500 for, or secure keys for every communication, you have n squared over 25:37.500 --> 25:42.680 two different connections, so it's order of n square keys, which is 25:42.680 --> 25:46.620 quite a bit of keys, and you have to transmit all these keys in a 25:46.620 --> 25:51.320 secure way, which really shows that this is a difficult problem, 25:51.680 --> 25:57.540 because you have to make sure that the exchange of keys is done with 25:57.540 --> 26:01.080 highest security, nobody should be able to interfere with that. 26:01.980 --> 26:07.680 The approach is to just not use symmetric methods, where you use the 26:07.680 --> 26:13.700 same key on both sides, but only use public key cryptosystems, where 26:13.700 --> 26:18.360 you use an asymmetric method, where you have one key that is only 26:18.360 --> 26:23.920 known to a specific person, and the other key is publicly known. 26:24.860 --> 26:31.140 Now, this idea at first sight is very strange, how can you assume that 26:31.140 --> 26:37.760 something works in a secure way if the key actually is publicly known, 26:38.440 --> 26:42.540 because usually we should use something which is not known, so we have 26:42.540 --> 26:46.720 to show it to see how that actually works, so here the idea is that 26:46.720 --> 26:52.420 everybody has, or every person has their own public key, and this 26:52.420 --> 26:57.360 public key is used to send, so if you have person A, you send 26:57.360 --> 27:02.840 information to person B, Alice to Bob, then you have a public key, 27:03.460 --> 27:11.680 public key of Bob, which is used to encrypt a method, a message, and 27:11.680 --> 27:17.880 you have a secret key, that Bob has his secret key and can decrypt the 27:17.880 --> 27:18.720 message. 27:19.800 --> 27:25.760 So this is the major idea, and the public key in a naive way could be 27:25.760 --> 27:29.120 assumed to be in some kind of public key book. 27:29.660 --> 27:33.700 We will come back to that issue of how to actually get information on 27:33.700 --> 27:36.460 about public keys a bit later. 27:37.500 --> 27:42.300 So every person has her own secret key for decrypting messages, and 27:42.300 --> 27:47.340 the idea is that if you have a message you just encrypt it using the 27:47.340 --> 27:53.440 public key, and then you send the, or you transmit the encrypted 27:53.440 --> 27:58.560 message, and you use the secret key at the recipient side to decrypt 27:58.560 --> 28:04.720 this encrypted message, and the requirements certainly are that you 28:04.720 --> 28:09.400 retrieve the old message that M and M' actually are the same. 28:12.120 --> 28:18.800 Actually, what is nice to get is that not only S of P of M is equal to 28:18.800 --> 28:24.900 M, but also that P of S of M is also equal to M. 28:25.280 --> 28:30.620 Regardless of the sequence at which you actually use these two keys, 28:31.140 --> 28:34.000 you still get, you retrieve the same message. 28:34.860 --> 28:43.200 So this is also an important point, which is not really the original 28:43.200 --> 28:49.100 requirement, but this is a nice side effect which is exploited quite 28:49.100 --> 28:52.940 significantly, because this would mean you could encrypt something 28:52.940 --> 28:56.880 with your personal information, with your personal secret key, and 28:56.880 --> 28:59.960 everybody else would be able to decrypt that message. 28:59.960 --> 29:03.360 This is something which looks strange, why would you do that, that 29:03.360 --> 29:09.920 everybody else can decrypt a message that you have encrypted, but this 29:09.920 --> 29:14.140 is important if you would like to show to somebody that you actually 29:14.140 --> 29:20.360 have touched that message and nobody else could have encrypted it. 29:20.360 --> 29:23.000 This has to do with digital signatures. 29:24.480 --> 29:30.160 Then all the pairs S, P are different, so secret P, private key, 29:30.560 --> 29:39.160 secret key and public key pairs should be certainly different, and 29:39.160 --> 29:43.540 then to derive the secret information from the public information 29:43.540 --> 29:48.340 should be, like secret key from the public key, should be as hard as 29:48.340 --> 29:54.140 decrypting the encrypted message without knowing the secret key. 29:54.980 --> 29:58.520 So the public information, you have the public key and you have the 29:58.520 --> 30:04.880 encrypted messages, and now it should be very hard, very expensive to 30:04.880 --> 30:07.480 retrieve the secret key information. 30:09.360 --> 30:14.160 Both S and P, both secret or both keys, that secret public key should 30:14.160 --> 30:20.020 be easily computed and certainly encryption and decryption should also 30:20.020 --> 30:22.120 be not too expensive. 30:22.820 --> 30:26.780 We will see later on that this is not actually achieved, but all the 30:26.780 --> 30:28.060 other things are achieved. 30:28.960 --> 30:35.340 Just one background information, what we actually need in this, like 30:35.340 --> 30:40.140 when we say we can encrypt something easily but it's hard to decrypt, 30:40.460 --> 30:43.520 this is something which we also call one-way functions. 30:43.520 --> 30:46.860 One-way functions are essential type of functions that we use in 30:46.860 --> 30:47.520 cryptography. 30:48.380 --> 30:51.560 So one-way function is a function that is easy to compute but hard to 30:51.560 --> 30:56.680 invert, that means it's easy to compute f of x, but if you have f of 30:56.680 --> 31:07.280 x, it's very hard to determine this y such that this y, like f of y 31:07.280 --> 31:10.060 actually is x, so to invert it or 31:14.060 --> 31:20.580 so this is, like it should be just very difficult to invert to 31:20.580 --> 31:25.860 determine the original x from knowing f of x. 31:27.100 --> 31:32.260 Simple examples are if you look up a phone number, that's easily done. 31:32.640 --> 31:37.900 If you try to retrieve the phone or retrieve the person from the phone 31:37.900 --> 31:41.160 number, this is more difficult because usually you don't have an 31:41.160 --> 31:44.980 inverted phone book, you just have a listing of names, not a listing 31:44.980 --> 31:48.520 of phone numbers, although nowadays we have also that as a service on 31:48.520 --> 31:49.040 the internet. 31:50.480 --> 31:53.860 Another example, a famous example, is factorization. 31:54.420 --> 32:00.040 You want to compute the product of two prime numbers which results in 32:00.040 --> 32:06.140 some value n and then somebody else gets this value n, the product, 32:06.560 --> 32:09.900 and tries to find out the two prime numbers that had been used to 32:09.900 --> 32:10.840 produce that number. 32:11.860 --> 32:15.620 And it is believed that this is a very hard problem because there's no 32:15.620 --> 32:20.220 efficient method known, unless you use something like quantum 32:20.220 --> 32:28.220 computing, but the known methods are just very expensive, and so if 32:28.220 --> 32:33.620 the product of two numbers, the prime numbers, is the information that 32:33.620 --> 32:38.000 you have publicly available, and the secret is these two prime 32:38.000 --> 32:44.460 numbers, then you have to invest quite a bit of effort to compute or 32:44.460 --> 32:46.500 to find out these two prime numbers. 32:47.000 --> 32:52.860 So factorization is the hard way, computing the product is the easy 32:52.860 --> 33:03.240 way, so multiplication in this case is the one-way function in this 33:03.240 --> 33:03.520 case. 33:05.040 --> 33:10.640 So in cryptography, we usually assume that we have a so-called 33:10.640 --> 33:14.940 backdoor, that means we can compute the encrypted text in an easy way, 33:15.400 --> 33:19.840 and then we need some additional information, a key, to retrieve the 33:19.840 --> 33:22.500 original information back. 33:23.040 --> 33:29.840 Simple example would be a lock, which you can easily lock, but if you 33:29.840 --> 33:32.740 don't have the key, it's very hard to open it. 33:32.960 --> 33:36.200 If you have the key, you just insert the key and you open up this 33:36.200 --> 33:38.600 closed lock. 33:39.220 --> 33:44.980 Okay, it's simple, very simplified way of actually telling you what 33:44.980 --> 33:49.660 one -way function actually is, so the major point is it's very hard to 33:49.660 --> 33:54.160 invert such a function, to get back the original, the argument from 33:54.160 --> 33:56.220 the image of that function. 33:57.100 --> 34:02.600 Now in the RSA cryptosystem, things like that had to be designed, and 34:02.600 --> 34:08.620 Rivest, Shamir Edelman, they are the three scientists who actually 34:08.620 --> 34:13.560 designed the first public key algorithm, that's why it's called RSA 34:13.560 --> 34:19.980 system, and there you have as a public key a pair of integers n and c. 34:21.320 --> 34:29.440 c is used because it's used for coding, for encoding, and then you 34:29.440 --> 34:34.060 have a secret key, which is again this n, so the actual secret key is 34:34.060 --> 34:44.520 this value d, and this is called d for decode, and c and d are numbers 34:44.520 --> 34:51.540 having at most as many bits as n, so about the same size, maybe quite 34:51.540 --> 34:56.960 a bit smaller, but the standard lengths of n are, well 512 is not 34:56.960 --> 35:03.460 really a standard length anymore, 1024, 2048, or any large number 35:03.460 --> 35:07.600 actually, these powers of two are just used for convenience. 35:09.020 --> 35:13.940 So you have many bits in these numbers, so if you have a thousand 35:13.940 --> 35:19.500 bits, you have something like 300 digits, so very large numbers. 35:21.240 --> 35:26.200 And c and d again are also large numbers, at least one of them usually 35:26.200 --> 35:27.140 is a very large number. 35:29.340 --> 35:33.820 The idea is that in RSA encryption, what you do is you take your 35:33.820 --> 35:40.560 original sequence, and then you chop that into pieces as we did with 35:40.560 --> 35:50.080 DES, but with a larger size, so these m i, so this is m1, m2, and so 35:50.080 --> 35:56.120 on, are numbers that are smaller than this value n, so having 35:56.120 --> 36:01.140 something like 300 digits or a thousand bits. 36:02.980 --> 36:11.040 And then you compute, you take every m i, every segment to the power 36:11.040 --> 36:19.480 c, and compute the result modulo n, so the result is again of the same 36:19.480 --> 36:27.340 size as the values m i, but it's m i to the c modulo n. 36:29.580 --> 36:37.240 Okay, large numbers, you have m i is a number having something like a 36:37.240 --> 36:42.380 thousand or a few thousand bits, take it to a power which can again be 36:42.380 --> 36:48.620 a number having something like a thousand bits, compute that modulo n, 36:48.920 --> 36:56.660 so the length of your numbers does not explode, and this results in 36:56.660 --> 36:58.280 some value c i. 36:59.880 --> 37:06.360 Then, the decryption, what you do is you get the message c, which is 37:06.360 --> 37:12.600 again this, like here you have this message consisting of now our c1, 37:12.800 --> 37:19.280 c2, c3, and so on, and you take that to the power d i, like c i to the 37:19.280 --> 37:29.040 power, not d i, sorry, the power d, and d is your key for decrypting a 37:29.040 --> 37:36.040 message, and the claim is that you retrieve the original message m i 37:36.040 --> 37:40.660 back from those two computations. 37:41.520 --> 37:45.700 So taking to the power c, taking to the power d, gives you the 37:45.700 --> 37:46.780 original message back. 37:48.240 --> 37:58.820 And just, that means that m i is supposed to be equal to c i to the, 37:59.220 --> 38:03.660 well, c times d, modulo n. 38:04.360 --> 38:09.880 Now, since c times d is a computative, like the multiplication of 38:09.880 --> 38:16.560 those two powers is a computative operation, you can perform the same, 38:16.740 --> 38:21.120 either first code and decode then, or first decode and then code. 38:21.220 --> 38:23.980 So you have this property that I mentioned briefly on the previous 38:23.980 --> 38:28.860 slide, that it doesn't matter whether you first apply the secret key 38:28.860 --> 38:32.800 and then the public key, or first apply the public key and then the 38:32.800 --> 38:35.960 secret key, you always get the original message back. 38:36.980 --> 38:40.340 Okay, now I have to explain to you how that actually works. 38:41.000 --> 38:43.240 How can we design such a system? 38:43.520 --> 38:44.520 It looks like magic. 38:45.220 --> 38:48.200 How is it possible you compute this in this strange way? 38:48.400 --> 38:52.640 Why does it actually provide you the same number again? 38:53.980 --> 39:01.580 So, how do we choose actually this modulus n, the value of c and d? 39:01.900 --> 39:05.660 By the way, have you ever looked at modular arithmetic? 39:06.480 --> 39:08.720 Who of you has never looked at modular arithmetic? 39:10.160 --> 39:12.280 One, two, three, four, okay. 39:13.040 --> 39:17.900 So if we do something like modular arithmetic, we just, like if you 39:17.900 --> 39:25.140 have, for example, you multiply two values, and this, the result of 39:25.140 --> 39:30.480 multiplying two values certainly is a value having double the size. 39:32.200 --> 39:35.960 Now, normally what we do is, in a computer we always perform modular 39:35.960 --> 39:40.680 arithmetic, because we usually discard the leading bits and only take 39:40.680 --> 39:41.460 the remainder. 39:42.900 --> 39:49.000 So this would be taking something modulo a certain power of two. 39:49.360 --> 39:53.440 So if this here is two to the k, for example, then you compute 39:53.440 --> 39:55.140 something modulo two to the k. 39:56.320 --> 40:00.040 Normally we compute something two to the, like modulo two to the 32, 40:00.220 --> 40:01.440 if you have 32-bit words. 40:02.640 --> 40:08.780 Because we only take this part here, the remainder, after dividing by 40:08.780 --> 40:09.480 two to the k. 40:10.340 --> 40:17.020 So this is just taking only some part of the information, and in that 40:17.020 --> 40:23.480 way you restrict your values to a finite range of values. 40:25.020 --> 40:30.080 So you don't have infinitely many numbers, but you only have a finite 40:30.080 --> 40:35.800 range of numbers, and now you have to design this, or you have to look 40:35.800 --> 40:37.360 at the property that you get there. 40:38.280 --> 40:45.680 And we know that if you compute modulo certain primes, then you have 40:45.680 --> 40:50.840 the nice effect that multiplication is invertible, and things like 40:50.840 --> 40:54.520 that, that you can have all the interesting operations like addition, 40:54.720 --> 40:58.080 subtraction, multiplication, division, which means you have two 40:58.080 --> 41:02.720 operations, addition and multiplication, and their inverses are 41:02.720 --> 41:06.880 always, every number has an inverse, a unique inverse with respect to 41:06.880 --> 41:13.040 multiplication or addition, and these are important aspects of 41:13.040 --> 41:20.560 arithmetic, and so if you look at number theory, you can look at the 41:20.560 --> 41:27.020 different ways of actually computing in finite fields. 41:27.740 --> 41:32.200 So compute in finite fields, 41:36.270 --> 41:41.630 this is something which is done in number theory, and there's the so 41:41.630 --> 41:44.190 -called Galois theory, 41:48.310 --> 41:53.730 which is dealing with computing in finite fields, and have you ever 41:53.730 --> 41:56.430 heard about Galois fields, Galois theory? 41:57.770 --> 41:58.770 No, you have not. 41:59.410 --> 42:05.230 And so in cryptography, you know, or you use quite a bit of the 42:05.230 --> 42:09.790 results of Galois theory, you know so-called Galois fields, and the 42:09.790 --> 42:13.410 field is just a field. 42:13.730 --> 42:17.190 Who of you knows what a field is, as an algebraic structure? 42:19.530 --> 42:24.830 One of you is nodding his head, but most of you don't know. 42:25.390 --> 42:26.230 So what is a field? 42:26.310 --> 42:28.090 You don't know what a field is, wow. 42:29.170 --> 42:37.130 So a field is just a set with two operations, addition and 42:37.130 --> 42:42.870 multiplication, and M together with plus, and M together with 42:42.870 --> 42:51.530 multiplication, are semi-groups, actually are groups in the field, 42:51.630 --> 42:57.110 they are groups, that means you have commutative operations, you have 42:57.110 --> 43:00.850 associative operations, the first of all is you have associative 43:00.850 --> 43:08.030 operations, then you have also commutativity, you have like 43:08.030 --> 43:16.690 multiplication, and plus have this law of distributivity, and the 43:16.690 --> 43:22.870 important point is what I mentioned already, that every element of M 43:22.870 --> 43:27.090 has an inverse, a unique inverse with respect to addition, a unique 43:27.090 --> 43:31.830 inverse with respect to multiplication, that means there is something 43:31.830 --> 43:39.110 like you can add to A, to value A, you can add something called minus 43:39.110 --> 43:43.810 A, which will result in a value zero, which is a neutral element with 43:43.810 --> 43:53.070 respect to addition, or you can have A times A minus 1, which leads to 43:53.070 --> 43:58.890 1, which is the inverse element with respect to multiplication, and 1 43:58.890 --> 44:03.770 is the neutral element with respect to multiplication, that means A 44:03.770 --> 44:08.910 times 1 is A, and zero is the neutral element with respect to 44:08.910 --> 44:16.170 addition, that means A plus zero is A, and these are the important 44:16.170 --> 44:22.030 properties, so M together with plus is a group, M together with 44:22.030 --> 44:26.670 multiplication is a group, and since this is the combination of two 44:26.670 --> 44:30.510 groups, an additive and a multiplicative group, this is called a 44:30.510 --> 44:35.250 field, that means a field essentially is an algebraic structure where 44:35.250 --> 44:39.130 you have essentially addition, subtraction, multiplication, and 44:39.130 --> 44:47.130 division in a unique way, and this is interesting if you have finite 44:47.130 --> 44:51.710 fields only, and the point is that in a computer we only operate on 44:51.710 --> 44:57.690 finite sets of numbers, because we have restricted number of bits for 44:57.690 --> 45:00.890 representing numbers, and so we have to find out how can we actually 45:00.890 --> 45:07.370 perform reasonable arithmetic in a closed form in these finite sets. 45:08.190 --> 45:16.290 Okay, and so there's quite some elaborate theory based on these finite 45:16.290 --> 45:20.710 fields and how finite fields of different sizes relate to each other, 45:21.130 --> 45:25.870 you can extend fields into other fields and things like that. 45:26.870 --> 45:31.730 We'll come back to that when I tell you something about the advanced 45:31.730 --> 45:40.870 encryption standard AES, because that relies heavily on this modular 45:40.870 --> 45:46.730 arithmetic and using arithmetic of polynomials, for example. 45:47.410 --> 45:48.770 I come back to that a bit later. 45:49.430 --> 45:52.510 First, we have to look at this again here. 45:52.870 --> 45:54.530 How do we determine these numbers? 45:55.030 --> 46:02.550 So, we have, for example, here two prime numbers having 512 bits each. 46:04.530 --> 46:06.950 We just randomly generate those prime numbers. 46:07.030 --> 46:10.850 We come back to the problem, how can we actually know that a randomly 46:10.850 --> 46:14.670 generated number is a prime number, but this is a very interesting 46:14.670 --> 46:20.270 algorithm that we will look at testing for primality of a number. 46:21.250 --> 46:26.150 For small numbers it's easy, for large numbers having 500 bits it's 46:26.150 --> 46:26.610 more difficult. 46:27.790 --> 46:32.230 Then we compute the product of these two prime numbers and we get this 46:32.230 --> 46:32.850 value n. 46:33.510 --> 46:38.130 I mentioned already the factorization, which is an interesting 46:38.130 --> 46:41.470 operation because it's a one-way function. 46:41.930 --> 46:45.870 It's hard to retrieve the two primes if you don't know them, but you 46:45.870 --> 46:46.970 only know the value of n. 46:47.930 --> 46:55.290 And then you determine randomly some value c, which is prime relative 46:55.290 --> 46:57.830 to p-1 times q-1. 46:59.310 --> 47:06.570 We had our primes, p and q, now we look at the product p-1 times q-1. 47:07.630 --> 47:10.770 In a moment I will show you why we look at that particular number. 47:11.770 --> 47:20.690 If we say c is prime relative to p-1 times q-1, this means c is not 47:20.690 --> 47:29.930 some divisor or some part of that product and p-1, q-1 doesn't have a 47:29.930 --> 47:31.650 common factor with c. 47:33.330 --> 47:42.050 So there are no common non-trivial divisors of c and p-1, q-1. 47:42.810 --> 47:52.130 So if I say c is prime relative to two numbers or... so c prime to, 47:52.370 --> 47:58.170 for example, a and... no, c is prime relative to that number or if I 47:58.170 --> 48:07.430 say that a is prime relative to b, it means that the greatest common 48:07.430 --> 48:12.590 divisor of a and b is equal to 1. 48:13.890 --> 48:18.370 Yeah, that's what I mean when I say one number is prime with respect 48:18.370 --> 48:18.990 to the other one. 48:20.910 --> 48:27.510 Okay, and then we determine a value d, so we randomly choose this c 48:28.010 --> 48:33.410 and then we can systematically determine a d such that the product of 48:33.410 --> 48:40.290 c times d is congruent to 1 modulo this number p-1 times q-1. 48:40.490 --> 48:45.890 What does it mean that something is congruent to 1 modulo p-1 times q 48:45.890 --> 48:46.330 -1? 48:46.450 --> 48:53.450 It means that the product c times d has the same residual with respect 48:53.450 --> 48:58.490 to division by p-1 times q-1 as 1. 48:59.210 --> 49:14.630 That means c times d is equal to some k times p-1 times q-1 plus 1. 49:15.450 --> 49:25.710 If I now divide, like this is, if you divide by p-1 times q-1, you 49:25.710 --> 49:28.250 get, as a remainder, you get 1. 49:29.890 --> 49:37.010 Yeah, so it's the remainder if you divide by this number, this is, 49:37.250 --> 49:40.930 this means two values are congruent to each other, or you could say 49:40.930 --> 49:48.990 that the difference of cd and 1 is congruent to 0, is a multiple of p 49:48.990 --> 49:50.410 -1 times q-1. 49:50.490 --> 49:52.350 This is the same as I mentioned here. 49:53.110 --> 50:01.850 So if it is congruent to 1, it means, as I said, cd is a multiple of p 50:01.850 --> 50:04.150 -1 times q-1 plus 1. 50:06.010 --> 50:14.350 And the interesting lemma now is, so the interesting lemma is that is 50:14.350 --> 50:23.290 the essential statement about the RSA method, is that for this choice 50:23.290 --> 50:30.570 of n, c, and d, we have for all m that are less than this value n, 50:31.310 --> 50:35.150 that m to the cd is congruent to m modulo n. 50:35.450 --> 50:39.610 And this is what we need for the correctness of the RSA algorithm, 50:40.150 --> 50:46.970 that taking first to the power c and then to the power d results in 50:46.970 --> 50:48.110 the original value. 50:49.630 --> 50:55.570 So this is the essential statement, and you have a question. 50:59.970 --> 51:00.950 Very simple. 51:02.430 --> 51:03.170 For example, 51:09.050 --> 51:16.530 301 is congruent to 1 modulo 100. 51:18.830 --> 51:22.790 But definitely 301 is not equal to 1. 51:24.510 --> 51:28.570 But 301 is 3 times 100 plus 1. 51:30.190 --> 51:35.650 Yeah, so this is, congruence just means you get the same remainder 51:35.650 --> 51:43.470 after division, if you divide by that modulus that is named here. 51:43.530 --> 51:49.210 In this case 100, and there you had, here you have just this value n. 51:51.010 --> 52:01.690 Yes, so you know that if you, for example, if you have, somehow I have 52:01.690 --> 52:08.250 to, somewhere I have to draw that, if you, for example, divide a 52:08.250 --> 52:15.090 number having a certain number of bits by a power of, like some power 52:15.090 --> 52:22.850 of 2, for example, divided by 2 to the k, then this here is the 52:22.850 --> 52:23.170 modulus. 52:23.170 --> 52:31.290 This is the result if you divide it by 2 to the k, then this part here 52:31.290 --> 52:41.670 is some x times 2 to the k, plus a value which is the modulus with 52:41.670 --> 52:42.790 respect to 2 to the k. 52:44.310 --> 52:50.130 So multiplying or dividing using powers of 2 is very simple. 52:50.130 --> 52:55.710 You can just chop off a certain, like the leading part of your number. 52:56.370 --> 53:00.570 Here it's not a power of 2, but it's a value n, which is a power of 2 53:00.570 --> 53:04.970 primes, and so it's a bit more difficult to compute that modulus 53:04.970 --> 53:05.590 operation. 53:08.690 --> 53:12.450 So this lemma now looks like, it still looks like magic. 53:12.850 --> 53:21.510 How is that possible that this choice of value c and d, or n, c and d, 53:21.690 --> 53:23.710 actually leads to that property? 53:25.010 --> 53:30.010 And this lemma relies or is based on two insights. 53:30.590 --> 53:36.810 One insight is the small or the little theorem by Fermat, which is 53:36.810 --> 53:37.930 telling the following. 53:38.890 --> 53:46.730 If p is prime and a is not divisible by p, that means a and p are 53:46.730 --> 53:52.770 relatively prime, then a to the p minus 1 is congruent to 1 modulo p. 53:54.810 --> 54:05.450 So that means a to the p minus 1, I could state it now like this, a to 54:05.450 --> 54:13.490 the p minus 1 is equal to some k times p plus 1. 54:14.470 --> 54:20.330 There exists some k such that, sorry, yes, no, it's right. 54:20.450 --> 54:25.570 a to the p minus 1 is congruent to 1 modulo p means that a to the p 54:25.570 --> 54:27.830 minus 1 is a multiple of p plus 1. 54:30.410 --> 54:37.110 And this is one essential insight, but this requires that p is a 54:37.110 --> 54:37.450 prime. 54:38.530 --> 54:43.670 Now, up there we have a product of two primes, we don't have just one 54:43.670 --> 54:44.030 prime. 54:45.570 --> 54:51.090 There's a generalization by the mathematician Euler who stated the 54:51.090 --> 54:51.430 following. 54:52.670 --> 54:59.970 If you have two values n and a, two numbers n and a, and these numbers 54:59.970 --> 55:04.130 are relatively prime, that means the greatest common divisor is 1, 55:05.090 --> 55:10.570 then a to the phi of n is congruent to 1 modulo n. 55:10.670 --> 55:19.810 And phi of n is the Euler function of the number, which is the number 55:19.810 --> 55:25.190 of values that are prime relative to n. 55:26.610 --> 55:33.410 So if you, for example, have p and q, p is not prime relative to n, 55:34.210 --> 55:37.170 because it is a factor of n. 55:38.350 --> 55:47.710 p minus 1 probably is prime with respect to, relative to, this value n 55:47.710 --> 55:48.890 up here. 55:49.650 --> 55:54.510 We'll come back to that, like to the Euler function of capital N. 55:55.630 --> 56:00.250 So this looks very similar to the statement we had up there, but here 56:00.250 --> 56:06.130 we have the statement that a to the Euler function of n is congruent 56:06.130 --> 56:07.570 to 1 modulo n. 56:09.590 --> 56:16.790 Okay, so just remember that we have Fermat's little theorem and we 56:16.790 --> 56:17.970 have Euler's theorem. 56:18.290 --> 56:22.730 And these two theorems, which I will not prove to you, but you can 56:22.730 --> 56:28.290 look that up in the literature on number theory, these are the results 56:28.290 --> 56:32.890 that are used in the design of the RSA algorithm. 56:32.890 --> 56:40.170 It will show you how we can derive the validity of this lemma by using 56:40.170 --> 56:42.510 Euler's theorem and Fermat's little theorem. 56:43.910 --> 56:49.590 Okay, the corollary certainly is if I know that a to the phi of n is 56:49.590 --> 56:59.490 congruent to 1 modulo n, then certainly a to the phi of n minus 1 is 56:59.490 --> 57:08.470 the modular inverse of a with respect to n, that means a times a to 57:08.470 --> 57:21.990 the phi of n minus 1 then is congruent to 1 modulo n. 57:22.170 --> 57:24.770 This is just the same as written up there. 57:25.050 --> 57:28.250 I just write here a times a to the phi n minus 1. 57:28.390 --> 57:34.450 So we have, in this way, we have determined the modular inverse with 57:34.450 --> 57:37.090 respect to multiplication of a. 57:39.250 --> 57:45.750 Okay, and certainly what we also know is if we would compute a to the 57:46.410 --> 57:55.650 phi of n plus 1, then that will be congruent to a modulo n. 57:56.310 --> 58:05.470 If we just multiply both sides with a, then definitely a times 1 is a, 58:06.170 --> 58:12.110 and a to the phi of n times 1 is a to the phi of n plus 1, and so here 58:12.110 --> 58:16.110 we have something which looks very similar to what we would like to 58:16.110 --> 58:16.410 get. 58:18.450 --> 58:24.550 And so this actually shows that this c times d has to or should have a 58:24.550 --> 58:28.570 structure that is similar to a phi of n plus 1. 58:30.250 --> 58:34.290 This is the major idea behind the RSA algorithm. 58:35.390 --> 58:36.870 I'll show you how that is done. 58:39.270 --> 58:44.450 Okay, first of all, let's look at the Euler function of our value n. 58:44.930 --> 58:51.890 You know that pq is the value that they use in RSA, p times q, and the 58:51.890 --> 58:56.370 lemma that I briefly showed to you is that the Euler function of the 58:56.370 --> 59:02.070 product of two prime numbers is just the product of the numbers that 59:02.070 --> 59:05.790 are decremented, prime numbers, by one each. 59:06.810 --> 59:09.030 So the proof is very simple. 59:09.950 --> 59:16.410 If p and q are prime, we know that certain numbers are or have a 59:16.410 --> 59:18.010 common divisor with p times q. 59:18.850 --> 59:24.510 These are these numbers here, like p definitely is a divisor of p 59:24.510 --> 59:25.070 times q. 59:26.310 --> 59:30.630 Now, 2 times p also has a common divisor with p times q. 59:32.050 --> 59:39.270 p times 3 has also a common divisor, and certainly p times q, which 59:39.270 --> 59:42.870 does not count, but there are, like, p times q minus 1 is also common, 59:43.370 --> 59:45.830 has a common divisor with p times q. 59:46.590 --> 59:52.930 And certainly, 1 times q, 2 times q, and p minus 1 times q all have 59:52.930 --> 59:54.670 common divisors with p times q. 59:55.570 --> 01:00:03.470 And the statement was on this previous slide, it's the number of the, 01:00:03.670 --> 01:00:12.130 all the values that are prime relative to n is the Euler function, and 01:00:12.130 --> 01:00:17.130 so we have to look at, now at all the others, which do have a common 01:00:17.130 --> 01:00:27.490 divisor with this value n, and so these are exactly those values. 01:00:27.710 --> 01:00:32.610 So p times q certainly has the common divisor p times, or has a common 01:00:32.610 --> 01:00:36.490 divisor with p times q, p and q are the common divisors here. 01:00:37.510 --> 01:00:40.130 So how many numbers are these? 01:00:40.130 --> 01:00:47.630 Here we have exactly q values, 1 to q, and here we have p minus 1. 01:00:49.370 --> 01:00:50.030 Oops. 01:00:52.910 --> 01:00:56.250 And so, so this was p values. 01:00:56.490 --> 01:01:03.370 So these are not, these are q values, so these are p plus q minus 1 01:01:03.370 --> 01:01:10.350 values, and that means the total number of values we could have are p 01:01:10.350 --> 01:01:10.990 times q. 01:01:12.030 --> 01:01:17.590 We have to subtract those that are not prime with respect to p times 01:01:17.590 --> 01:01:22.490 q, and this just is this value, p minus 1 times q minus 1. 01:01:24.110 --> 01:01:30.630 Yeah, if you multiply this, then you just have here p times q minus p, 01:01:32.830 --> 01:01:39.850 yeah, minus p minus q plus 1, which is exactly what we have there. 01:01:41.190 --> 01:01:47.410 Okay, so this is simple arithmetic, and so now we go back to the RSA 01:01:47.410 --> 01:01:48.010 algorithm. 01:01:48.570 --> 01:01:52.710 We know that if p and q are prime, the Euler function is just this 01:01:52.710 --> 01:02:04.050 value, and now if m is relative, is prime relative to n, that means 01:02:04.050 --> 01:02:09.490 they don't have a greatest common divisor that is unequal to 1, then 01:02:09.490 --> 01:02:15.050 we know because of Euler's theorem that m to this value is congruent 01:02:15.050 --> 01:02:16.190 to 1 modulo n. 01:02:16.530 --> 01:02:17.610 This is the Euler theorem. 01:02:20.390 --> 01:02:26.390 Two values m and n are prime, m is prime relative to n, then we know 01:02:26.390 --> 01:02:31.070 that m to the Euler function of n is congruent to 1 modulo n. 01:02:31.770 --> 01:02:34.950 And now the Euler function value we know, it's p minus 1 times q minus 01:02:34.950 --> 01:02:35.250 1. 01:02:35.670 --> 01:02:40.790 Then definitely, if we multiply both sides by 1, we have this equality 01:02:40.790 --> 01:02:48.430 here, or this congruence, which is what we are interested in, and so 01:02:48.430 --> 01:02:59.570 we just have to make sure that c times d is congruent to 1 modulo p 01:02:59.570 --> 01:03:01.310 minus 1 times q minus 1. 01:03:02.090 --> 01:03:04.550 So that's what we would like to see. 01:03:04.550 --> 01:03:11.630 We know that m to the p minus 1 times q minus 1 plus 1 is congruent to 01:03:11.630 --> 01:03:11.910 m. 01:03:14.890 --> 01:03:21.730 And so we had m to the c times d was supposed to be equal to m. 01:03:23.310 --> 01:03:31.230 And so c times d must be of that form that cd minus 1 is a multiple of 01:03:31.230 --> 01:03:32.810 the Euler number of n. 01:03:33.710 --> 01:03:39.630 So k times, some k times, or we have to show that there exists some k 01:03:39.630 --> 01:03:45.810 such that cd minus 1 is k times p minus 1 times q minus 1. 01:03:48.930 --> 01:03:55.610 And if that is the case, then certainly m times cd is congruent to m. 01:03:56.450 --> 01:04:00.470 Like cd minus 1 is k times p minus 1 times q minus 1. 01:04:00.490 --> 01:04:07.450 Up here it states that m to the p minus 1 q minus 1 plus 1 is 01:04:07.450 --> 01:04:08.270 congruent to m. 01:04:10.350 --> 01:04:15.090 cd minus 1 now is some multiple of this, but if you look at this 01:04:15.090 --> 01:04:21.750 equation here, if you take a multiple of p minus 1 times q minus 1, it 01:04:21.750 --> 01:04:23.610 still is congruent to 1. 01:04:24.610 --> 01:04:30.910 This does not change, because you can just take it m to the, like, 01:04:31.090 --> 01:04:37.010 square that, square that again, and so on, and you still get something 01:04:37.010 --> 01:04:38.770 which is congruent to 1. 01:04:39.730 --> 01:04:43.430 Because you square on both sides, it doesn't change that here you 01:04:43.430 --> 01:04:44.590 still have the value 1. 01:04:47.340 --> 01:04:52.420 So, we can have this multiple of the Euler value, Euler function 01:04:52.420 --> 01:04:59.160 value, and we only have to show that we can select c and d having such 01:04:59.160 --> 01:04:59.600 a property. 01:05:03.630 --> 01:05:12.830 Now, if we look back to our, the way we actually chose our cd minus 1, 01:05:12.910 --> 01:05:19.070 or our values of cd, we had determined d such that cd is congruent to 01:05:19.070 --> 01:05:21.510 1 modulo p minus 1 times q minus 1. 01:05:21.770 --> 01:05:25.250 This was the way we have actually determined the value of d. 01:05:26.970 --> 01:05:31.570 And so, that's why we, like, this is what I stated here. 01:05:32.290 --> 01:05:37.170 We know then that we have this form, and therefore m to the c times d 01:05:37.170 --> 01:05:38.450 is congruent to m. 01:05:39.530 --> 01:05:46.150 But here we assumed that m actually is prime relative to this product 01:05:46.150 --> 01:05:47.770 of p and q. 01:05:48.070 --> 01:05:51.430 What happens if we have one of those numbers that are not prime? 01:05:51.950 --> 01:05:59.210 That means if we have one of those values that are some t times q, for 01:05:59.210 --> 01:06:03.630 example, 1 times q, 2 times q, or whatever, t times q. 01:06:04.550 --> 01:06:09.570 This is a value that is not prime with respect to a capital N. 01:06:11.110 --> 01:06:14.510 In that case, certainly t is less than p. 01:06:15.350 --> 01:06:20.090 p is a prime number, and so by the Little-Fermat, we know that t to 01:06:20.090 --> 01:06:22.530 the p minus 1 is congruent to 1 modulo p. 01:06:23.650 --> 01:06:24.930 p is a prime number. 01:06:25.750 --> 01:06:28.750 So this was the statement of the Little-Fermat theorem. 01:06:30.090 --> 01:06:36.470 And certainly we also know that q to the p minus 1 is congruent to 1, 01:06:37.110 --> 01:06:39.470 because, well, p is prime. 01:06:42.760 --> 01:06:45.620 And so we have these two statements. 01:06:47.380 --> 01:06:55.580 And now we also know we can just take arbitrary multiples of t to the 01:06:55.580 --> 01:07:00.460 p minus 1, and it will still be congruent to 1 modulo p. 01:07:01.760 --> 01:07:06.080 So arbitrary is not really arbitrary, we just take a specific 01:07:06.080 --> 01:07:13.240 multiple, the multiple which is t to the k times p minus 1 times q 01:07:13.240 --> 01:07:14.080 minus 1. 01:07:15.500 --> 01:07:18.580 We can do the same for the other equation. 01:07:19.220 --> 01:07:24.260 We can take q to the p minus 1 and take multiples of that, square 01:07:24.260 --> 01:07:30.480 that, and so on, and get q to the k times p minus 1 times q minus 1. 01:07:31.000 --> 01:07:32.600 Still congruent to 1 modulo p. 01:07:33.680 --> 01:07:37.100 And now we can multiply those two values. 01:07:37.720 --> 01:07:44.300 We multiply that value and that value, which will still give us the 01:07:44.300 --> 01:07:45.300 same modulus. 01:07:47.460 --> 01:07:56.420 So, if we take t times q to that power, it's still congruent to 1 01:07:56.420 --> 01:07:57.100 modulo p. 01:07:57.520 --> 01:08:04.240 If we multiply that by t, we get that this is congruent to t modulo p. 01:08:04.680 --> 01:08:11.320 And if we multiply that by q, we have a value that is congruent to t 01:08:11.320 --> 01:08:15.720 times q modulo p times q in that case. 01:08:20.960 --> 01:08:31.840 And here we have now t times q to the, well, since we multiplied, like 01:08:31.840 --> 01:08:39.800 this was just t times tq to the k times p minus 1 q minus 1, now we 01:08:39.800 --> 01:08:40.820 have here this plus 1. 01:08:43.020 --> 01:08:47.540 So this is now exactly what we would like to get. 01:08:48.100 --> 01:08:54.020 We now have that t times q actually is retrieved again if we take it 01:08:54.020 --> 01:08:59.360 to this power, and this power was just the power we have here as cd. 01:09:02.080 --> 01:09:09.660 Okay, so it also holds for values of m that are not prime relative to 01:09:09.660 --> 01:09:16.500 n, to this modulus n, and so it holds for every m that is less than 01:09:16.500 --> 01:09:21.180 capital N, and therefore the lemma is proven. 01:09:22.880 --> 01:09:26.540 So we can do that the same way for all multiples of p, we did it for 01:09:26.540 --> 01:09:30.760 multiples of q, we can do it for multiples of p, and then we have 01:09:30.760 --> 01:09:32.460 shown it for all the possible values. 01:09:32.900 --> 01:09:39.080 So this shows that the algorithm actually is correct. 01:09:39.560 --> 01:09:41.420 We can retrieve the original values. 01:09:41.980 --> 01:09:43.200 Now what does it actually cost? 01:09:45.740 --> 01:09:49.820 Encryption decryption use exponentiation. 01:09:50.000 --> 01:09:54.800 Now how can we, like if we compute something a to the x or a to the n, 01:09:55.720 --> 01:09:57.100 how do we do that? 01:09:57.100 --> 01:10:02.200 Well, the claim is we can do that with order of log n arithmetic 01:10:02.200 --> 01:10:02.980 operations. 01:10:04.840 --> 01:10:11.240 Order of, sorry, I shouldn't have written here a to the x, should have 01:10:11.240 --> 01:10:17.920 looked at this here, for all x and n, we can compute x to the n having 01:10:17.920 --> 01:10:20.320 order of log n arithmetic operations. 01:10:20.580 --> 01:10:24.980 That means we just have to look at the number of bits of n, and this 01:10:24.980 --> 01:10:27.460 is the number of operations that we have to use. 01:10:29.500 --> 01:10:36.140 Which is not intuitively clear how that is done, but I can easily show 01:10:36.140 --> 01:10:37.160 you how that is done. 01:10:38.160 --> 01:10:43.640 We just look at the way we can represent numbers. 01:10:44.020 --> 01:10:45.700 So x is an arbitrary integer. 01:10:47.840 --> 01:10:50.620 n, we would like to compute x to the n. 01:10:51.740 --> 01:10:59.860 Now, n certainly is some, can be represented as a binary number. 01:11:01.460 --> 01:11:09.600 And so x to the n is x to the, well, this sum of powers of two. 01:11:10.560 --> 01:11:16.720 Now if you take x to the sum of powers of two, you can also take the 01:11:16.720 --> 01:11:21.900 product of all these powers of, like x to the powers of two. 01:11:24.360 --> 01:11:35.860 If you have x to r times x to s, this definitely is x to the r plus s. 01:11:37.000 --> 01:11:45.320 Yeah, that's why we get from the addition of values in the exponent, 01:11:45.620 --> 01:11:46.520 we get the product. 01:11:47.220 --> 01:11:50.680 Now we have the ai times two to the i. 01:11:51.140 --> 01:11:53.140 ai are binary values. 01:11:53.600 --> 01:11:57.120 So this is a product of certain powers of x. 01:11:58.740 --> 01:12:03.180 And all these powers of x are powers of the type x to the two to the 01:12:03.180 --> 01:12:03.500 i. 01:12:04.020 --> 01:12:08.160 If you would like to get all these x to the two to the i, what do you 01:12:08.160 --> 01:12:08.780 have to compute? 01:12:08.920 --> 01:12:13.660 You just have to square x and do that several times. 01:12:14.450 --> 01:12:22.900 Every squaring, like if you square x to the two to the i, square that, 01:12:22.980 --> 01:12:27.240 that means you compute that product that leads to x to the two to the 01:12:27.240 --> 01:12:28.720 i plus one. 01:12:29.760 --> 01:12:37.700 This way you get all the successive powers of x that you need, x to 01:12:37.700 --> 01:12:39.360 some powers of two. 01:12:40.740 --> 01:12:45.080 Now you can represent that product in different ways. 01:12:45.780 --> 01:12:48.360 One way would be to write it like this. 01:12:49.640 --> 01:12:55.100 You have x to the a0 times two to the zero, which is one. 01:12:56.520 --> 01:13:06.100 You have, now here it shows x squared to the a1, a1 is zero of one. 01:13:07.080 --> 01:13:15.360 Then you have x to the four times a, or to the power a2 is zero of 01:13:15.360 --> 01:13:19.660 one, that means this value is either x to the four or it's one. 01:13:21.020 --> 01:13:26.020 And the final value here is x to the two to the k to the power a to 01:13:26.020 --> 01:13:26.420 the k. 01:13:26.640 --> 01:13:31.900 But here, essentially this means you just take this, the product of 01:13:31.900 --> 01:13:37.800 all the powers of x, to where you have powers of two in the exponent, 01:13:38.720 --> 01:13:49.920 and your bits a0 to a k determine whether a certain power is used or 01:13:49.920 --> 01:13:50.620 is not used. 01:13:51.880 --> 01:13:59.200 So you can compute that as successive squarings and using the values 01:13:59.200 --> 01:14:03.120 that are relevant, and you know which values are relevant by looking 01:14:03.120 --> 01:14:07.340 at the bits of the binary representation of n. 01:14:07.960 --> 01:14:15.180 Starting from the least significant value, so normally like n would, 01:14:15.320 --> 01:14:25.200 this would be written as a n, no in this case a k, a k minus one to a 01:14:25.200 --> 01:14:25.760 zero. 01:14:27.140 --> 01:14:29.260 Okay, starting from the least significant bit. 01:14:29.920 --> 01:14:32.620 But you could also write this in a different way. 01:14:33.380 --> 01:14:42.360 You could start taking x to the a k, that means if a k is one, this is 01:14:42.360 --> 01:14:45.500 x, if it's zero, this is just one. 01:14:46.300 --> 01:14:55.440 You take that, or you just square that, and then you multiply with x 01:14:55.440 --> 01:14:59.760 or with one, and you square again. 01:15:01.040 --> 01:15:03.780 So this is just a different representation. 01:15:03.780 --> 01:15:08.180 We know that these operations are associative, so we can change the 01:15:08.180 --> 01:15:09.180 sequence of operations. 01:15:10.360 --> 01:15:13.600 And in this representation of that product, here it's all this 01:15:13.600 --> 01:15:19.840 product, we would, like if we would compute that, we would start using 01:15:19.840 --> 01:15:22.640 the value a k and then square. 01:15:24.480 --> 01:15:29.520 And we would use the value of a k minus one and square and so on. 01:15:30.180 --> 01:15:36.180 And we always decide whether we actually multiply with x or whether we 01:15:36.180 --> 01:15:38.700 just multiply with one. 01:15:40.180 --> 01:15:43.000 And we always perform this successive squaring. 01:15:44.100 --> 01:15:51.420 So in the end, you have x to the a k times two to the k, and the 01:15:51.420 --> 01:15:55.040 others just are, like have these smaller powers. 01:15:55.140 --> 01:15:59.080 So these are just two ways of representing that large product. 01:15:59.620 --> 01:16:03.280 And that means that you have two different approaches to actually 01:16:03.280 --> 01:16:07.360 compute that exponent of this power of x. 01:16:08.120 --> 01:16:11.900 You start with the least significant and go to the most significant 01:16:11.900 --> 01:16:16.600 bit of n, or you start from the most significant and go to the least 01:16:16.600 --> 01:16:17.620 significant bit of n. 01:16:18.100 --> 01:16:21.260 You always do certain sequences of squarings. 01:16:21.840 --> 01:16:23.400 That's the essential point. 01:16:23.940 --> 01:16:28.620 And the number of squarings that you have to do is bounded by log n, 01:16:28.840 --> 01:16:30.780 the number of bits you have for n. 01:16:31.220 --> 01:16:34.740 Because every bit here, if all the bits are one, then you have exactly 01:16:34.740 --> 01:16:37.540 log n squarings. 01:16:38.190 --> 01:16:46.200 And you have to multiply all those x's onto those intermediate values, 01:16:46.400 --> 01:16:53.500 so you have two log n multiplications in total, as a maximum number of 01:16:53.500 --> 01:16:54.720 operations that you need here. 01:16:54.720 --> 01:17:09.620 So this is an important way to compute the power of a value of x with 01:17:09.620 --> 01:17:13.500 a logarithmic number of multiplications. 01:17:14.100 --> 01:17:19.120 This still is quite a large number of multiplications, because we know 01:17:19.120 --> 01:17:21.100 that we have very large numbers. 01:17:22.020 --> 01:17:29.620 So we have numbers having 1024 bits or something in that area, and the 01:17:29.620 --> 01:17:31.680 numbers themselves are very large. 01:17:33.380 --> 01:17:39.640 So this means we have something like 1000 multiplications or 2000 01:17:39.640 --> 01:17:42.200 multiplications of very large numbers. 01:17:43.140 --> 01:17:47.120 And so what do we do when we have to multiply very large numbers? 01:17:47.240 --> 01:17:51.020 So you have to multiply two very large numbers. 01:17:51.860 --> 01:17:53.000 How can we do that? 01:17:53.120 --> 01:17:59.360 We can just... we have to chop them somehow into our normal word size, 01:17:59.460 --> 01:18:05.520 32 -bit numbers, and then we have to use multiple length arithmetic, 01:18:06.220 --> 01:18:12.500 extended arithmetic, in order to operate on k-word integers. 01:18:13.840 --> 01:18:18.780 Now, if you do that in a naive way, you would get a order of k squared 01:18:18.780 --> 01:18:20.280 single word operations. 01:18:21.100 --> 01:18:27.660 You remember, we had something like 1000 or 2000 multiplications. 01:18:28.860 --> 01:18:35.080 Now, on these... like, on the individual bits, we had something like 01:18:35.080 --> 01:18:37.580 32 -bit words. 01:18:37.720 --> 01:18:40.900 You have 1024 bits. 01:18:41.620 --> 01:18:47.200 That means it's another... it's 32 32-bit words in a 1000-bit number. 01:18:48.580 --> 01:18:56.400 And so you have 32 squared single word operations, which means for an 01:18:56.400 --> 01:19:01.700 individual multiplication, you again have many, many operations, 01:19:01.900 --> 01:19:06.220 something like 1000 individual multiplications for that, if you use 01:19:06.220 --> 01:19:11.540 this order of squared single word operations method, which means it's 01:19:11.540 --> 01:19:12.580 a very expensive thing. 01:19:13.600 --> 01:19:17.040 Now, you can try to reduce this order of k squared. 01:19:17.200 --> 01:19:21.240 You can use a simple divide-and-conquer approach for multiplication, 01:19:22.200 --> 01:19:27.140 and reduce the number of single word operations to something like 01:19:27.140 --> 01:19:28.780 order of k to the 1.5. 01:19:29.840 --> 01:19:32.700 This is rather simply done. 01:19:33.600 --> 01:19:37.460 Or you could apply the fast Fourier transform, which is much more 01:19:37.460 --> 01:19:47.440 sophisticated, to get a multiplication of two k-word integers with 01:19:47.440 --> 01:19:48.080 k... 01:19:48.080 --> 01:19:51.180 log k single word operations. 01:19:52.560 --> 01:19:56.340 This is a very sophisticated method, but it's possible to do that. 01:19:56.440 --> 01:19:59.020 And so you certainly have to try... 01:19:59.020 --> 01:20:02.860 have to use methods like that, because you have to reduce the number 01:20:02.860 --> 01:20:06.320 of operations that are needed to actually compute those products. 01:20:07.980 --> 01:20:13.880 So for 32-bit arithmetic, an exponent length of 1024 bit, we need 01:20:13.880 --> 01:20:22.900 something like 327,000-28,000 operations per plaintext block of 1024 01:20:22.900 --> 01:20:23.420 bits. 01:20:24.560 --> 01:20:26.400 Many, many operations. 01:20:27.200 --> 01:20:33.080 And so this requirement, it should be simple, to encrypt or decrypt is 01:20:33.080 --> 01:20:34.760 certainly violated here. 01:20:35.520 --> 01:20:36.980 It's a very expensive thing. 01:20:38.300 --> 01:20:41.880 We know we have very powerful computers, so even that can be done in a 01:20:41.880 --> 01:20:43.060 very short amount of time. 01:20:43.480 --> 01:20:45.260 But it's many operations. 01:20:46.760 --> 01:20:49.880 This is a naive estimate, definitely. 01:20:50.440 --> 01:20:54.140 Like here, I make a statement on order of k log k. 01:20:54.700 --> 01:21:01.440 Here, I make an estimate over the thumb, just using constants of one, 01:21:02.080 --> 01:21:06.360 which is not really justified, but it's some constant variation of 01:21:06.360 --> 01:21:06.860 that number. 01:21:06.920 --> 01:21:13.720 Just showing you some order of the cost that you actually get here. 01:21:14.640 --> 01:21:22.240 If you use powerful RSA chips, you can actually achieve RSA encryption 01:21:22.820 --> 01:21:24.460 about 100 megabit per second. 01:21:24.660 --> 01:21:29.060 This is actually a value that is about 5, 6, 7 years old. 01:21:29.580 --> 01:21:34.700 So, like the Stolar 1024, I mentioned that one, because it's one of 01:21:34.700 --> 01:21:38.240 the products that is a spin-off of former research that we did. 01:21:38.860 --> 01:21:42.360 It's a 1000 processor extension card of the standard PC. 01:21:42.660 --> 01:21:49.160 And on that processor, on this extension card, which was available 01:21:49.160 --> 01:21:55.520 some 10 years ago, you could achieve very fast RSA encryption. 01:21:56.480 --> 01:21:59.220 So, it is possible to do that. 01:21:59.280 --> 01:22:02.400 And if you use current technology, you can actually process 01:22:02.400 --> 01:22:04.280 information much faster than that. 01:22:04.340 --> 01:22:10.080 And if you look at the communication bandwidth that we have, if we can 01:22:10.080 --> 01:22:13.480 communicate with 100 megabit per seconds, that's okay. 01:22:14.080 --> 01:22:17.180 Normally, we have, like in local area networks, we have something like 01:22:17.180 --> 01:22:18.700 100 megabits per second. 01:22:19.180 --> 01:22:21.700 If you use DSL, you have less than that. 01:22:21.920 --> 01:22:27.240 So, if you have a device on your PC that is supporting encryption at 01:22:27.240 --> 01:22:28.820 that speed, you are fine. 01:22:29.680 --> 01:22:29.880 Okay. 01:22:30.740 --> 01:22:34.900 So, this was fast exponentiation. 01:22:35.020 --> 01:22:36.080 I showed you that already. 01:22:36.860 --> 01:22:43.440 And I would like to maybe just briefly mention this, the cost of 01:22:43.440 --> 01:22:44.240 cryptanalysis. 01:22:44.960 --> 01:22:51.280 If we want to actually factor a number, factor this number N, there 01:22:51.280 --> 01:22:54.500 are many different methods known. 01:22:54.640 --> 01:22:59.100 People try to do that in an efficient way, actually change the value 01:22:59.100 --> 01:23:01.980 that is on the previous slides. 01:23:01.980 --> 01:23:08.520 This is what I found as the current upper bound for, or the best upper 01:23:08.520 --> 01:23:11.780 bound for computing the factors of a number. 01:23:12.760 --> 01:23:14.280 But still, it's very large. 01:23:14.400 --> 01:23:21.120 It's e to the something like 64 over 9 b to the one third. 01:23:21.400 --> 01:23:24.400 So, it's the third root of that one. 01:23:24.820 --> 01:23:26.280 And here you have log of b. 01:23:26.780 --> 01:23:31.160 And b is, in this case, the number of bits of N. 01:23:31.880 --> 01:23:36.260 So, the b here is log of capital N. 01:23:36.780 --> 01:23:38.920 Log b is log log of capital N. 01:23:39.340 --> 01:23:43.020 If you compare that to the value that I had there before, there you 01:23:43.020 --> 01:23:47.500 had not the third root, but the simple root. 01:23:48.200 --> 01:23:49.620 And here now we have the third root. 01:23:49.700 --> 01:23:52.060 But still, it's a very large value. 01:23:52.680 --> 01:23:55.720 And it just takes a lot of time. 01:23:59.300 --> 01:24:03.380 And it's here as stated that a worst case time of several thousand 01:24:03.380 --> 01:24:05.000 years may be reduced. 01:24:05.100 --> 01:24:09.840 But even if it's several hundred years, meanwhile, or just a few 01:24:09.840 --> 01:24:13.660 years, this is just a lot of work that has to be done. 01:24:15.140 --> 01:24:21.280 And the problem is, maybe you can use probabilistic methods to get 01:24:21.280 --> 01:24:22.780 faster factorization. 01:24:23.420 --> 01:24:28.220 Or, and that is an important thing that people get worried about, if 01:24:28.220 --> 01:24:31.000 we actually make progress with respect to quantum computing. 01:24:31.100 --> 01:24:36.060 In quantum computing, you get the factorization at almost no cost. 01:24:38.100 --> 01:24:40.480 And so, it's... 01:24:41.420 --> 01:24:45.280 Like, currently, people are not very optimistic that we will actually 01:24:45.280 --> 01:24:49.360 get quantum computers that will be able to perform something in a 01:24:49.360 --> 01:24:50.180 realistic time. 01:24:50.910 --> 01:24:55.020 But in principle, in theory, a quantum computer could do that. 01:24:55.840 --> 01:24:59.780 So, what we need is very long keys. 01:24:59.980 --> 01:25:04.160 So, the more secure, the more secret information is, the longer the 01:25:04.160 --> 01:25:05.380 keys that you should use. 01:25:05.600 --> 01:25:07.900 Several thousand bits should be sufficient. 01:25:08.780 --> 01:25:13.400 Okay, it's 11.15, so it's the end of today's lecture. 01:25:13.480 --> 01:25:18.740 But I briefly wanted to show you one thing, which is, like, let me 01:25:18.740 --> 01:25:23.960 just end this presentation. 01:25:24.460 --> 01:25:30.460 I briefly wanted to show you something which shows you what we 01:25:30.460 --> 01:25:35.600 actually can do with a tablet PC, or some nice application of the 01:25:35.600 --> 01:25:36.140 tablet PC. 01:25:36.320 --> 01:25:43.260 Some of you might have seen that already in some other course, when 01:25:43.260 --> 01:25:51.520 you had your Informatics 3, no, Informatics 2 course with me, then you 01:25:51.520 --> 01:25:52.580 would have seen that already. 01:25:53.260 --> 01:25:55.080 My assistants will not have shown you that. 01:25:55.560 --> 01:25:59.020 So, this is just a tool which allows you to do funny things. 01:25:59.340 --> 01:26:04.060 For example, you can draw something and it turns into some object. 01:26:05.460 --> 01:26:10.540 And so I can draw another thing, it turns into that object. 01:26:11.260 --> 01:26:14.760 And I could say, this should move into that direction. 01:26:16.960 --> 01:26:27.400 And maybe I take another object and I say this should move into that. 01:26:32.140 --> 01:26:34.400 What happens if I animate that? 01:26:35.760 --> 01:26:38.180 They just move into that direction. 01:26:39.660 --> 01:26:43.740 Now I make the same, and I say, we have an additional force, which is 01:26:43.740 --> 01:26:47.260 gravitational force. 01:26:47.420 --> 01:26:48.260 What happens then? 01:26:49.380 --> 01:26:50.540 Things fall down. 01:26:52.940 --> 01:26:54.360 Okay, simple thing. 01:26:55.440 --> 01:27:01.340 And what I could also do is, I could, for example, say, well, I could 01:27:01.340 --> 01:27:02.460 look at the properties. 01:27:02.940 --> 01:27:07.280 I could choose different materials, rubber, steel, wood, ice, plastic, 01:27:07.520 --> 01:27:08.300 clay or so. 01:27:08.720 --> 01:27:14.240 So, if I would take clay for that, for example, what would happen if I 01:27:14.240 --> 01:27:16.380 use that now? 01:27:16.740 --> 01:27:17.840 Oops, you can't see it. 01:27:18.500 --> 01:27:20.100 I should take away that here. 01:27:21.160 --> 01:27:21.360 Oops. 01:27:27.930 --> 01:27:29.250 Okay, it just moves away. 01:27:30.430 --> 01:27:32.810 Let me show you a different thing. 01:27:33.490 --> 01:27:37.330 There are some pre-designed things that I can just show you. 01:27:37.530 --> 01:27:44.550 For example, you can make some experiments by looking, for example, 01:27:44.830 --> 01:27:45.510 at... 01:27:45.510 --> 01:27:47.610 This is quite nice. 01:27:52.810 --> 01:27:55.570 I didn't want to store, I wanted to open. 01:27:58.540 --> 01:27:58.940 Nope. 01:28:00.040 --> 01:28:01.880 So, off-road. 01:28:02.300 --> 01:28:05.980 I would like to show you what this is doing. 01:28:06.420 --> 01:28:11.740 This is just two circles attached to a rectangle, and now it's 01:28:11.740 --> 01:28:16.100 attached with some forces, and this is just moving according to those 01:28:16.100 --> 01:28:16.500 forces. 01:28:17.300 --> 01:28:18.640 Or a different thing. 01:28:19.140 --> 01:28:22.700 I could show you, for example, a catapult. 01:28:24.520 --> 01:28:27.800 And this catapult is looking like this. 01:28:27.900 --> 01:28:32.300 You have here this very heavy thing. 01:28:33.320 --> 01:28:36.020 Then we, like here, you have the gravitational force. 01:28:36.760 --> 01:28:40.100 And then what happens if we actually animate that? 01:28:41.180 --> 01:28:42.460 This is a catapult. 01:28:44.100 --> 01:28:44.860 Yeah. 01:28:45.430 --> 01:28:50.940 And just to show you a final picture, or two final pictures, I could 01:28:50.940 --> 01:28:56.860 show you what happens if we, for example, throw snowballs at the KIT. 01:28:57.700 --> 01:29:02.100 Then this just crumbles away. 01:29:04.820 --> 01:29:12.500 Or if we look at this here, the final slide. 01:29:12.500 --> 01:29:18.140 And not in English, but in German, Merry Christmas, and that can also 01:29:18.140 --> 01:29:18.840 be animated. 01:29:20.260 --> 01:29:27.000 And so this is Merry Christmas, and I hope that you have some time to 01:29:27.000 --> 01:29:32.120 relax a bit and come back in the new year with new strength and eager 01:29:32.120 --> 01:29:35.200 to learn more about algorithms for internet applications. 01:29:35.920 --> 01:29:39.460 Okay, thanks for today's attention and see you next year.