WEBVTT 00:00.000 --> 00:05.160 Now, there are also other methods available, not just substitution of 00:05.160 --> 00:07.680 symbols, but you can use transposition. 00:07.880 --> 00:14.440 Transposition means that you don't substitute necessarily the 00:14.440 --> 00:18.360 individual characters, but you just modify the sequence in which they 00:18.360 --> 00:19.500 are actually listed. 00:20.520 --> 00:26.240 And this is in some way also called, or can be called diffusion. 00:26.500 --> 00:30.020 That means to distribute the information of the plaintext over the 00:30.020 --> 00:30.640 ciphertext. 00:31.480 --> 00:36.600 You will see methods like that on the next slides, but also here in 00:36.600 --> 00:37.560 this simple example. 00:38.420 --> 00:42.520 This is an example where you write the plaintext into the columns of a 00:42.520 --> 00:47.140 matrix, and then read it out in row major order. 00:48.060 --> 00:54.540 So the message is listed here, our message that we have looked at 00:54.540 --> 00:55.320 before also. 00:55.780 --> 00:58.460 And now you read it out in this way. 00:59.320 --> 01:02.360 And if you do that, you get a message which looks like this. 01:03.140 --> 01:08.280 And certainly here, you can only retrieve the original message by 01:08.280 --> 01:12.660 certainly permuting this letter sequence in a reasonable way. 01:13.840 --> 01:24.160 But to rearrange it, what you need to know is the shape of that matrix 01:24.160 --> 01:25.080 that you have used. 01:25.860 --> 01:31.760 And it actually had been used in former times by having some thick 01:31.760 --> 01:37.660 pole or some thick stick, wooden stick. 01:38.140 --> 01:48.060 And then you had a piece of, or a stripe of paper just wrapped around 01:48.060 --> 01:49.560 that stick. 01:50.380 --> 01:54.440 And you wrote the message on that stick, like this way. 01:55.680 --> 02:04.600 Then you took that piece of linen or whatever you had there and took 02:04.600 --> 02:05.060 it away. 02:05.340 --> 02:10.840 And then you had exactly this transformation from a matrix into a 02:10.840 --> 02:11.680 sequence of letters. 02:11.920 --> 02:16.080 This reading out by row major order where you have written a message 02:16.080 --> 02:19.780 in column major order is exactly what you do here. 02:19.780 --> 02:26.820 And in order to decrypt what you have, like, I should write it like 02:26.820 --> 02:27.100 that. 02:27.260 --> 02:34.900 So you unwrap that and by unwrapping, you get this long piece of linen 02:34.900 --> 02:36.860 or whatever with some letters on it. 02:37.100 --> 02:40.700 In order to retrieve the original message, you need a pole or a stick 02:40.700 --> 02:42.640 having exactly that diameter. 02:43.600 --> 02:45.180 That's the size of the matrix. 02:45.180 --> 02:50.520 Very old, ancient method to actually encrypt messages. 02:51.260 --> 02:54.600 So here, the key is the form of the matrix or the chosen permutation. 02:55.920 --> 03:06.540 And another difference is that using substitution, the characters are 03:06.540 --> 03:09.820 encrypted independently of each other. 03:10.220 --> 03:14.220 So independent of the position, whereas what we do here in this 03:14.220 --> 03:20.300 example is that we look at the complete message and we need the 03:20.300 --> 03:25.080 complete message in order to actually get the encrypted version. 03:26.020 --> 03:35.680 So in substitution, we can have stream ciphers and here we have 03:35.680 --> 03:39.760 something where we need the complete information. 03:41.880 --> 03:48.540 So this is not a stream cipher if we have that type of system. 03:49.040 --> 03:53.080 So what we need is some adequate combination of all these different 03:53.080 --> 03:53.620 approaches. 03:54.780 --> 04:01.560 And so if you just use substitution and or transposition, you can 04:01.560 --> 04:06.260 attack those methods and you can explore the frequency of letters and 04:06.260 --> 04:07.660 letter sequences. 04:07.660 --> 04:11.580 You can try different transposition schemata. 04:12.080 --> 04:13.820 So this is not really secure. 04:14.700 --> 04:17.580 You can also exploit partial knowledge of plain text. 04:17.720 --> 04:25.080 Like you can assume that certain words are in such a message, some 04:25.080 --> 04:30.840 greeting formulas or the date or the name of the location where this 04:30.840 --> 04:32.460 message has been sent from. 04:33.080 --> 04:38.120 Things like that usually are also used for trying to exploit or trying 04:38.120 --> 04:43.520 to attack encrypted messages. 04:44.500 --> 04:49.580 And certainly a way to get around that is to combine these different 04:49.580 --> 04:53.740 approaches and also to use methods with several stages of encryption. 04:54.000 --> 04:59.100 So if you do that several times, then every time you get a stronger 04:59.100 --> 05:06.220 degree of hiding information, of spreading or of getting a higher 05:06.220 --> 05:09.040 degree of diffusion in that message. 05:09.980 --> 05:14.660 And so one of those methods that did this in a very systematic way was 05:14.660 --> 05:20.000 the data encryption standard DES, which is a method which is no longer 05:20.000 --> 05:24.800 the data encryption standard, but it has an interesting structure. 05:25.020 --> 05:29.100 And I just want to show you how that algorithm actually works. 05:29.100 --> 05:37.120 Then you see some or you find out there about some interesting aspects 05:37.120 --> 05:40.080 of how to design these systems. 05:40.740 --> 05:47.200 So it has been developed in the 70s by IBM in cooperation with the 05:47.200 --> 05:47.540 NSA. 05:48.540 --> 05:53.780 And in 77, it was accepted as an encryption standard. 05:54.120 --> 06:01.140 Now we have the advanced encryption standard that was in the late 90s 06:01.140 --> 06:09.400 when we got the, or around the year 2000, when we got the new advanced 06:09.400 --> 06:10.680 encryption standard. 06:11.640 --> 06:17.440 That was not something designed by a company together with the 06:17.440 --> 06:21.940 security agency, but there was an open competition for a new standard. 06:22.460 --> 06:27.240 And this competition, all the different submissions were really 06:27.240 --> 06:31.080 analyzed very, very thoroughly. 06:31.380 --> 06:40.500 And then this AES standard actually was found, actually designed by 06:40.500 --> 06:47.360 people from Europe, not from North America, but it was accepted by the 06:47.360 --> 06:49.840 Americans as the advanced encryption standard. 06:50.680 --> 06:54.420 And what we do here is that we have a continuous encryption of 06:54.420 --> 07:01.280 plaintext blocks of 64 bits, so in the DES, using a 56-bit key. 07:03.060 --> 07:09.160 And how that is done, I will show you here in these, first showing you 07:09.160 --> 07:15.960 a small, or some overview of the structure of that algorithm, and then 07:15.960 --> 07:17.220 we go into more details. 07:17.800 --> 07:22.860 So it starts with a plaintext block of 64 bits. 07:23.350 --> 07:25.660 Here we have 56 bits in the key. 07:26.500 --> 07:32.040 The first thing we do is we permute the bits in that plaintext block 07:32.040 --> 07:33.460 or in the key in some way. 07:33.600 --> 07:38.500 This has some reason for that, which is not that essential actually 07:38.500 --> 07:39.340 for the encryption. 07:39.500 --> 07:44.720 Then we have the first encryption round where we generate from that 07:44.720 --> 07:47.520 permuted key, the round key for the first round. 07:48.300 --> 07:55.240 From that, we select certain bits and encrypt our permuted plaintext 07:55.240 --> 07:58.520 and get some internal format. 07:59.120 --> 08:04.860 Then generate the next round key and do that 16 times. 08:05.860 --> 08:12.100 After 16 rounds, we actually then do another final permutation and get 08:12.100 --> 08:13.060 the ciphertext block. 08:14.860 --> 08:21.160 And so you see it's a sequence of different, of encryptions. 08:21.400 --> 08:25.500 The structure is always the same and we will look into that structure 08:25.500 --> 08:26.100 in a moment. 08:26.240 --> 08:31.180 So the initial permutation is the same as the inverse of the final 08:31.180 --> 08:31.780 permutation. 08:33.260 --> 08:40.340 So this has no real cryptographic relevance and we will now look into 08:40.340 --> 08:44.420 the individual encryption routes, what's actually done in there. 08:45.460 --> 08:49.940 We have to transform the key in some way to get the round key. 08:50.260 --> 08:59.240 So initially we have here our permuted round key, which is, as I said, 08:59.440 --> 09:02.260 it's 56 bits. 09:02.820 --> 09:06.660 And this is split into two halves of 28 bits each. 09:07.540 --> 09:13.540 And then these parts are shifted, left shifted. 09:16.660 --> 09:19.460 Both parts are left shifted in every round. 09:19.740 --> 09:25.060 Those parts are left shifted by one bit in rounds one, two, nine, and 09:25.060 --> 09:27.360 16, and by two bits in the other ones. 09:28.160 --> 09:36.500 And then from those modified bit sequences, we select by compression 09:36.500 --> 09:41.100 permutation, 48 bits from those 56. 09:42.020 --> 09:45.520 And those 48 bits are the actual round key. 09:48.640 --> 09:54.260 The idea is that different bits of the key are used in every round. 09:55.540 --> 10:04.680 And each bit is used in about 14 rounds, but in a somehow irregular 10:04.680 --> 10:09.960 way, that's achieved by those cyclic shifts that we have here. 10:11.100 --> 10:13.500 So the compression permutation is always the same. 10:13.980 --> 10:20.200 And since the bit positions are moved around, these bits are used in, 10:20.280 --> 10:25.740 or are used in different ways in the different rounds. 10:26.920 --> 10:33.300 These encryption rounds that we use there are called Feistel rounds, 10:33.700 --> 10:38.420 after a scientist called Feistel, who worked at IBM. 10:38.420 --> 10:46.460 And this Feistel round is a generic pattern for encryption, which has 10:46.460 --> 10:50.420 a very nice property, which I will explain to you now. 10:51.100 --> 10:56.680 So what we do there is we have a text block before round I, before 10:56.680 --> 10:58.560 just some round. 11:00.500 --> 11:03.700 And one thing we have to look at is we certainly would like to 11:03.700 --> 11:06.760 encrypt, but we also would like to decrypt. 11:07.640 --> 11:11.020 The DES algorithm is a symmetric method. 11:12.440 --> 11:20.100 And this schema for encryption and decryption uses the same key. 11:21.080 --> 11:23.660 And in some way, it should also use the same method. 11:24.940 --> 11:28.920 So you need something which is reversible in some way. 11:29.120 --> 11:31.380 And this schema is reversible. 11:31.600 --> 11:33.640 And we will see how that actually can be done. 11:34.280 --> 11:36.780 So this is the schema that is used. 11:36.880 --> 11:37.980 You have a text block. 11:38.620 --> 11:41.780 You split that, so these are the 64 bits. 11:42.280 --> 11:46.580 Then you have two text blocks of 32 bits, the two halves, a left half 11:46.580 --> 11:47.420 and a right half. 11:48.840 --> 11:52.480 And now, actually, you don't modify the right half. 11:52.560 --> 11:57.980 You just put it in for the next round as the new left half. 12:00.240 --> 12:02.420 So this is just transmitted. 12:03.020 --> 12:10.220 And the left half of this round here is XORed. 12:10.980 --> 12:12.860 Here again, you have the XOR operation. 12:13.120 --> 12:17.740 The nice thing of this that it is, we know that it's easily reversible 12:17.740 --> 12:22.500 by using the same XORing with the same values again. 12:23.540 --> 12:27.220 So you XOR something with the left half. 12:28.620 --> 12:35.260 And this, what you XOR it with, is the modified right half. 12:35.700 --> 12:43.580 So the right half was moved on to the next stage as the new left half, 12:43.660 --> 12:52.160 but it's also used here for creating the other operand for that XORing 12:52.160 --> 12:52.600 operation. 12:52.600 --> 12:58.780 So the right half is transformed by some function fi using that key. 12:59.540 --> 13:03.240 The result of that is XORed with the left half of that round. 13:03.660 --> 13:05.720 Then you get the new right half. 13:07.260 --> 13:10.000 So this is the operation or the general schema. 13:11.680 --> 13:18.980 And what are the properties or what can we find out about the way we 13:18.980 --> 13:21.280 can actually reverse that operation? 13:22.600 --> 13:27.420 If we would like to reverse that, we have to look at this direction. 13:27.660 --> 13:30.440 We know Li plus one, Ri plus one. 13:31.300 --> 13:34.380 And we certainly also know the function and the key. 13:35.200 --> 13:38.240 And we would like to retrieve Li and Ri. 13:39.220 --> 13:44.460 The question is, how can I retrieve Li and Ri by knowing Li plus one, 13:44.560 --> 13:49.520 Ri plus one, and certainly this transformation there. 13:50.260 --> 13:56.220 So the relationship that we know about is that Ri plus one, as shown 13:56.220 --> 14:04.780 on the left, is the XORing of Li and the transformed previous right 14:04.780 --> 14:05.100 half. 14:06.100 --> 14:09.700 And Li plus one is just the right half. 14:09.780 --> 14:11.400 So this is easily retrieved. 14:11.700 --> 14:15.800 If we know Li plus one, certainly we immediately know Ri. 14:21.220 --> 14:31.420 And so if we do the following, if we look at the XORing of Ri plus 14:31.420 --> 14:39.320 one, this is this part here, and we XOR that with Fi of Li plus one. 14:39.380 --> 14:44.220 Li plus one is the left part of what we have here, what we would like 14:44.220 --> 14:45.640 to reverse. 14:46.520 --> 14:50.060 We know that Ri plus one is just Li. 14:54.320 --> 15:05.100 And this Fi of Li plus one, like Li plus one is just Ri. 15:06.180 --> 15:13.180 So this here is Li XOR, Ri plus one is Li. 15:13.540 --> 15:23.380 This Li plus one is, sorry, Ri plus one is Li XOR Fi of Ri. 15:23.820 --> 15:30.080 Ri plus one is Li, this here, this part is Li XOR F of Ri. 15:33.180 --> 15:38.520 Li plus one is Ri, so we have here twice F of Ri. 15:38.780 --> 15:40.260 Sorry that I mixed up things here. 15:40.260 --> 15:47.740 So again, what we have here in this line is Ri plus one and Li plus 15:47.740 --> 15:48.040 one. 15:48.280 --> 15:53.200 We know that Li plus one is equal to Ri, this is stated there again. 15:54.280 --> 16:02.320 And so if we look at the operation Ri plus one XOR F of Li plus one, 16:05.340 --> 16:11.280 then Ri plus one, as we know, is Li XOR F of Ri. 16:11.660 --> 16:16.740 Li plus one is Ri, so we have Li XOR twice with F of Ri. 16:17.420 --> 16:19.520 And this certainly is Li again. 16:20.580 --> 16:26.740 And this operation now is exactly the same structure as we have in the 16:26.740 --> 16:27.280 encryption. 16:28.720 --> 16:30.420 Yes, so this was encryption. 16:31.580 --> 16:35.480 And this here would be what we do for decryption. 16:36.220 --> 16:38.960 We would like to retrieve the previous level. 16:40.060 --> 16:48.060 And so it is exactly the same structure, just here we have the, if we 16:48.060 --> 16:51.840 take the right half and modify the left half, but this is just a 16:51.840 --> 16:54.640 simple shift of the structure. 16:55.240 --> 17:03.980 So it shows that this Feistel scheme allows for a method that uses the 17:03.980 --> 17:06.720 same structure for encryption and decryption. 17:07.460 --> 17:14.360 So if you know the key, you can easily invert those different levels 17:14.360 --> 17:18.700 or those different stages or those different rounds of encryption and 17:18.700 --> 17:23.300 retrieve the original plaintext message. 17:23.970 --> 17:29.160 So this is the important structural idea of that algorithm. 17:29.880 --> 17:37.180 Another question is how actually this Fi here looks like and how this 17:37.180 --> 17:37.760 can be done. 17:37.940 --> 17:43.800 So DS encryption is, or DS decryption, is just some application of DS 17:43.800 --> 17:48.260 with the opposite round key sequence, as I outlined now. 17:49.780 --> 17:54.780 Another question is how this Feistel round within DS looks like. 17:55.040 --> 18:03.760 So for that we have our function F, which was called before, now looks 18:03.760 --> 18:04.700 as follows. 18:04.880 --> 18:09.340 Here we have both parts, how we select the key and how we actually use 18:09.340 --> 18:09.740 that. 18:10.500 --> 18:18.620 So we have our 56 bits there, as I said, split into two 28 parts. 18:19.360 --> 18:23.660 They are cyclically shifted, left shifted, by one or two positions. 18:24.240 --> 18:29.100 Then we have the selection by the compression permutation, which leads 18:29.100 --> 18:30.560 to those 48 bits. 18:31.240 --> 18:37.320 Now here in the right half we just have 32 bits, but we have to XOR 18:37.320 --> 18:39.020 that with 48 bits. 18:39.020 --> 18:47.040 So we have to in some way generate 16 more bits for XORing. 18:47.560 --> 18:54.040 And then we have to in some way get rid of 16 additional bits, because 18:54.040 --> 18:57.300 we have to get back from 48 to 32 bits. 18:57.980 --> 19:03.300 Then we have a P-box, which is another permutation, and the result is 19:03.300 --> 19:05.600 XORed with the old left part. 19:06.320 --> 19:10.880 So this is, again, the scheme, and now I have to show you a few more 19:10.880 --> 19:13.480 details how we actually do that. 19:13.780 --> 19:16.900 The first thing is the compression permutation. 19:17.500 --> 19:19.660 I will not go into the details of that. 19:21.200 --> 19:23.280 It's not that interesting, really. 19:24.120 --> 19:28.520 You can easily read it in publications on DES. 19:29.460 --> 19:33.600 The expansion permutation is a simple way of... 19:34.400 --> 19:46.960 If these are the positions of your sequence, of your right part there, 19:47.280 --> 19:48.960 what you do is the following. 19:49.820 --> 19:53.920 You insert certain bits by repeating bits that you have in the 19:53.920 --> 19:54.600 original message. 19:55.040 --> 20:00.300 So you have here, for example, 1, 2, 3, 4. 20:01.260 --> 20:03.300 You just say, OK, I take... 20:03.880 --> 20:10.380 Now I assume that I can repeat here bit number 32 from the right end. 20:11.960 --> 20:15.300 And then I have the bits 32, 1, 2, 3, 4, 5. 20:16.240 --> 20:17.920 Now I do the same for the next. 20:19.120 --> 20:21.960 These were these four bits, 1, 2, 3, 4. 20:22.560 --> 20:25.540 Now I have 5, 6, 7, 8, and I do the same here. 20:26.200 --> 20:28.420 5, 6, 7, 8, 9. 20:29.680 --> 20:34.660 And then 5, 6, 7, 8. 20:34.780 --> 20:37.140 And then the same is done for the next block. 20:37.400 --> 20:41.360 So here you would take those bits. 20:41.520 --> 20:46.080 So you have a sequence of bits, 32, 1, 2, 3, 4. 20:46.420 --> 20:49.020 Then you have 5, and then you have 4 again. 20:49.520 --> 20:51.700 5, 6, 7, 8, and 9. 20:52.280 --> 20:53.960 Then you have the next 4-bit block. 20:53.960 --> 21:00.000 That means you always take the 2 bits surrounding 4-bit blocks and you 21:00.000 --> 21:03.040 just put these blocks of bits in sequence. 21:03.280 --> 21:07.880 And so you have these additional 16 bits. 21:08.480 --> 21:16.620 Since you have the 8 4-bit parts there, for each 4-bit part you insert 21:16.620 --> 21:17.680 2 additional bits. 21:18.500 --> 21:21.080 And so you have 48 bits in total. 21:21.700 --> 21:24.520 So this is a very simple expansion permutation. 21:24.720 --> 21:29.380 You use the same bits as you have in that ciphertext in the moment, or 21:29.380 --> 21:31.340 in that right part here. 21:32.280 --> 21:34.360 And so you have 48 bits. 21:38.180 --> 21:42.760 And in this way you have generated these 48 bits. 21:43.460 --> 21:46.340 And then, OK, the next thing, just look back at this. 21:47.040 --> 21:48.560 Then we have the 48 bits. 21:48.560 --> 21:52.440 First we perform the XORing with the selected round key. 21:53.540 --> 21:55.920 And then we have something which is called S-boxes. 21:56.060 --> 21:59.020 Now these S-boxes initially have been secret. 22:00.800 --> 22:04.760 And so this is something, as we know, is not a good idea. 22:05.500 --> 22:11.120 But in this case, when actually they became known to the public, it 22:11.120 --> 22:16.940 did not change actually the difficulty to attack that code. 22:16.940 --> 22:18.900 They were designed in a very clever way. 22:19.520 --> 22:21.740 Now what is their task? 22:21.820 --> 22:22.940 What should they do? 22:23.960 --> 22:31.480 The S-box is transforming something which is consisting of 48 bits to 22:31.480 --> 22:32.420 32 bits. 22:32.420 --> 22:38.420 And this is done by transforming... 22:39.140 --> 22:46.260 this is essentially just something transforming 6 bits into 4 bits. 22:47.400 --> 22:50.620 And you have several of those. 22:51.700 --> 23:00.900 And in this way you get, if you combine those, you have 48 to 32 bits. 23:00.900 --> 23:03.680 You split that into 6-bit blocks. 23:04.460 --> 23:07.820 And now you have to transform 6 bits back into 4 bits. 23:09.040 --> 23:15.840 And for this you have these 16... no, sorry, 8. 23:15.940 --> 23:17.320 You have 8 S-boxes. 23:18.040 --> 23:21.840 8 times 6 is 48. 23:22.900 --> 23:26.000 And you have 8 of these S-boxes. 23:26.160 --> 23:29.640 And they all consist of a specific table. 23:29.640 --> 23:32.480 And I give you an example of one of those tables. 23:32.900 --> 23:40.040 So this is a table containing numbers between 0 and 15. 23:41.080 --> 23:44.040 So these are 4-bit values coded in 4 bits. 23:45.080 --> 23:57.140 And now you take 6 bits, let's say 0, 1, 0, 1, 1, 2, 3... 23:57.860 --> 24:00.340 For example, something like this here. 24:00.620 --> 24:02.020 How would this be transformed? 24:03.600 --> 24:10.120 2 bits, the first and last, provide the row index, 0, 1. 24:10.980 --> 24:15.120 This is 0, so it would be this row. 24:16.200 --> 24:22.360 If we take this here as our 6-bit pattern that has to be transformed. 24:23.560 --> 24:30.800 And now the remaining bits, here in between, 1, 0, 1, 1. 24:31.120 --> 24:34.640 That should be 13. 24:36.000 --> 24:41.700 So 13 should be this here, should be that value. 24:42.160 --> 24:49.100 So a number from 0 to... we have 4 bits, so we can select 16 different 24:49.100 --> 24:49.600 columns. 24:49.600 --> 24:54.200 Column number 13 is this one here. 24:54.360 --> 25:00.800 So we would replace those 6 bits with the 4 bits which code the number 25:00.800 --> 25:01.220 9. 25:03.220 --> 25:09.800 And so here we would have... the result would be just the number 9, so 25:09.800 --> 25:12.540 it would be 1, 0, 0, 1. 25:14.140 --> 25:15.240 8 plus 1. 25:16.240 --> 25:21.080 Okay, so this way we transform these 6 bits into 4 bits. 25:21.720 --> 25:26.840 And certainly the way this is designed is one of the secrets of how 25:26.840 --> 25:29.020 this was constructed. 25:30.500 --> 25:33.500 It was designed in a very clever way. 25:35.100 --> 25:41.200 So it was actually like this, these S-boxes were designed in a way 25:41.200 --> 25:46.800 such that it is really very difficult to perform a systematic attack 25:46.800 --> 25:54.560 on these algorithms in order to find out key or parts of the keys that 25:54.560 --> 25:55.080 are used. 25:55.860 --> 26:00.220 And then the final thing is the P-box which is just a permutation 26:00.840 --> 26:05.020 which makes sure that what you get as output of the individual S-boxes 26:05.020 --> 26:13.860 is in some way moved to different parts of that bit block, these 32 26:13.860 --> 26:14.260 bits. 26:14.960 --> 26:20.080 And in this way you make sure that the next round this bit will move 26:20.080 --> 26:22.000 through a different S-box. 26:23.100 --> 26:28.440 So they are designed such that the output of each S-box will influence 26:28.440 --> 26:31.400 many other boxes in the next round. 26:32.090 --> 26:37.460 And so the idea is that in the end you have here your initial 26:37.460 --> 26:44.900 plaintext, you have your final outcome, and if you look at any one 26:44.900 --> 26:50.380 position here, if you change that, you will completely change that 26:50.380 --> 26:50.980 ciphertext. 26:52.620 --> 26:56.700 That's the idea that every position here influences all the other 26:56.700 --> 26:58.780 positions in that ciphertext. 26:58.780 --> 27:03.860 And so if you want to find out something about that individual bit, 27:04.840 --> 27:07.760 you need the complete ciphertext. 27:08.400 --> 27:11.000 You cannot just concentrate on parts of it. 27:12.700 --> 27:15.720 Okay, so that's about that message. 27:16.240 --> 27:20.640 This expansion permutation and P-box, as I said, introduce that 27:20.640 --> 27:27.540 diffusion that every bit influences every other bit there. 27:27.540 --> 27:32.400 And also the bits of the key, as I said, if you modify bits of the 27:32.400 --> 27:36.980 key, it also changes completely the ciphertext. 27:39.060 --> 27:44.960 And so in this way, this really is quite secure. 27:46.120 --> 27:52.620 These S-boxes introduce non-linearity, so it's not just a linear 27:52.620 --> 27:53.320 transformation. 27:54.980 --> 28:01.180 And in this way, it was immune against differential cryptanalysis. 28:01.620 --> 28:11.020 So if you would like to find out the secret key in a DES method, and 28:11.020 --> 28:18.420 you are able to actually send different plaintext messages to this 28:18.420 --> 28:23.780 encryption module, you would like to find out what is actually the 28:23.780 --> 28:35.140 secret key, then you would just send messages which are almost the 28:35.140 --> 28:41.040 same, but just shifted by some part or modified in specific ways. 28:41.220 --> 28:45.980 And by knowing the differences in the plaintext, you look at the 28:45.980 --> 28:49.860 differences in the ciphertext and try to find out in which way 28:49.860 --> 28:54.660 actually these differences influence the ciphertext and conclude from 28:54.660 --> 28:58.960 that what kind of key bits must have been used. 28:59.020 --> 29:05.200 So this is a way of attacking cryptographic algorithms. 29:06.180 --> 29:13.620 And it turned out that differential cryptanalysis was not successful 29:13.620 --> 29:14.280 for DES. 29:14.960 --> 29:21.840 The method of differential cryptanalysis was known or was published 29:21.840 --> 29:28.500 sometime in the 80s, but this algorithm was already immune against 29:28.500 --> 29:31.740 that method, so people at that time must have known already this 29:31.740 --> 29:35.840 approach or must have used it, but certainly did not publish what they 29:35.840 --> 29:37.220 knew about. 29:37.970 --> 29:45.640 You can be sure that these security agencies have quite some knowledge 29:45.640 --> 29:50.000 about how to attack certain methods without telling everybody how they 29:50.000 --> 29:50.440 do that. 29:52.680 --> 30:04.300 Okay, so this is the other part that is interesting here, is that the 30:04.300 --> 30:10.380 DES algorithm is very easily implemented in hardware, so that means 30:10.380 --> 30:16.580 that you can build very small chips, small circuits for encryption. 30:17.440 --> 30:23.340 That's why it is very common on smart cards, but as I said, it's not 30:23.340 --> 30:28.820 used anymore because it actually was possible to attack that 30:28.820 --> 30:32.100 algorithm, and I will tell you a little bit about ways of attacking 30:32.100 --> 30:32.520 that. 30:33.440 --> 30:35.300 So how can we attack such a method? 30:36.420 --> 30:41.640 I said that regardless of what kind of algorithm you use, if you have 30:41.640 --> 30:47.540 something like this, a block ciphering method having a certain key 30:47.540 --> 30:52.460 length, you can just look at all the possible keys and try them all 30:52.460 --> 30:52.760 out. 30:52.880 --> 30:54.560 Now you have 56 bits for the key. 30:55.920 --> 31:01.800 That means you need to check 2 to the 56 possible keys, which is a 31:01.800 --> 31:02.660 very large number. 31:03.240 --> 31:05.300 It would take a very long time. 31:05.300 --> 31:11.120 So if you have a computer with 1 tera instructions per second and 1 31:11.120 --> 31:14.800 instruction per encryption, which certainly for encryption usually you 31:14.800 --> 31:19.620 need lots of instructions, but if you assume you could do that, it 31:19.620 --> 31:24.380 would mean that you need 20 hours to test that under these very simple 31:24.380 --> 31:28.840 assumptions, and we know that we need a lot more than that. 31:29.540 --> 31:37.440 But if you look at the fastest DES chips, so there you can do 31:37.440 --> 31:42.540 something like 250 million or let's say half a million encryptions per 31:42.540 --> 31:42.820 second. 31:45.560 --> 31:51.120 And even if you would have 1 giga encryptions per second, you would 31:51.120 --> 31:57.280 need to have 1,000 chips working concurrently to achieve 1 tera 31:57.280 --> 31:58.440 encryptions per second. 31:59.580 --> 32:01.600 So this is really quite a requirement. 32:02.520 --> 32:05.040 And so brute force alone will not suffice. 32:05.260 --> 32:06.240 This is too expensive. 32:06.680 --> 32:10.240 We said that we would not invest more money than we can gain from 32:10.240 --> 32:12.220 knowing that information. 32:13.020 --> 32:21.100 So 20 hours time delay will be something which is of interest for many 32:21.100 --> 32:21.480 people. 32:23.340 --> 32:27.840 Some information is losing its value after a specific time. 32:29.240 --> 32:34.240 So to achieve something like 20 hours is something you really would 32:34.240 --> 32:34.840 like to get. 32:34.840 --> 32:44.480 And then you could say, okay, you compute for a known plain text all 32:44.480 --> 32:45.800 possible encryptions. 32:48.540 --> 32:53.460 And then you use these encryptions to determine the key. 32:56.360 --> 33:02.400 Because as soon as you see that, then you would know all the 33:02.400 --> 33:04.920 encryptions and you can... 33:04.920 --> 33:08.420 well, certainly the memory requirements are very, very high. 33:09.220 --> 33:12.840 This you could do to prepare for an attack. 33:14.020 --> 33:17.200 And it takes some time, a lot of time. 33:18.020 --> 33:22.640 But you also would have to store all those encryptions, which does not 33:22.640 --> 33:23.380 make sense. 33:24.020 --> 33:26.080 Memory requirements are definitely too high. 33:27.680 --> 33:30.900 And then you could say, I only compute those encryptions partially. 33:31.760 --> 33:35.760 And then you have at least encrypted some of them. 33:35.760 --> 33:43.740 And you might find then matches with what you had done previously with 33:43.740 --> 33:49.740 some encrypted message that you would like to decrypt. 33:50.980 --> 33:55.900 So then you would... here you have some trade-off between space and 33:55.900 --> 33:59.640 time, like how much you would like to invest beforehand and how much 33:59.640 --> 34:04.360 you have to invest when you actually would like to decrypt a certain 34:04.360 --> 34:04.840 message. 34:06.080 --> 34:13.100 And then you could try to find out certain information on the 34:13.100 --> 34:15.140 structure of the keys that are reasonable. 34:15.680 --> 34:22.400 Because not all the different keys, not all those 256 keys are 34:22.400 --> 34:22.900 reasonable. 34:23.400 --> 34:26.460 If you have only zeros in there, it doesn't make sense. 34:26.960 --> 34:29.740 So certain patterns don't make sense. 34:29.740 --> 34:34.020 It's like patterns which would lead to a situation where you have the 34:34.020 --> 34:36.780 same key in all the 16 rounds. 34:36.960 --> 34:39.260 You can design keys like that. 34:39.400 --> 34:40.500 They don't make sense. 34:40.620 --> 34:44.880 So you can make statements on the security, on the strength of certain 34:44.880 --> 34:45.280 keys. 34:45.780 --> 34:47.820 It means that you will not use every key. 34:48.440 --> 34:51.460 And so you can reduce the number of keys you actually have to look at. 34:52.820 --> 34:59.560 There have been many attempts to attack DES encryptions. 35:00.420 --> 35:08.360 And on this website here you find all kinds of information about these 35:08.360 --> 35:10.400 attacks that have been run there. 35:12.220 --> 35:16.040 I hope that it's still available. 35:16.180 --> 35:17.460 Let me just briefly... 35:18.500 --> 35:22.940 I'm not connected to the internet at the moment. 35:23.280 --> 35:25.320 We don't have to go on that webpage. 35:25.380 --> 35:26.620 You can do that on your own. 35:27.620 --> 35:33.680 And look at information about how these attacks have been run. 35:35.260 --> 35:42.080 And as I said, one way of attacking cryptographic algorithms is this 35:42.080 --> 35:43.560 differential cryptanalysis. 35:43.560 --> 35:51.820 So here you choose in some way different plaintexts and analyze the 35:51.820 --> 35:54.560 differences in the ciphertext. 35:54.800 --> 35:56.540 You know the difference in the plaintext. 35:57.140 --> 36:00.320 And from that you try to find out something about the way this is 36:00.320 --> 36:00.720 encrypted. 36:01.920 --> 36:04.240 And it was published 1990. 36:05.340 --> 36:09.740 But DES has been especially designed to resist this type of attack. 36:09.860 --> 36:11.420 So this is interesting. 36:12.370 --> 36:16.760 Another point is that if you modify the algorithm, so for example 36:16.760 --> 36:21.860 reduce it just to 8 rounds, don't use those 16 rounds, you can 36:21.860 --> 36:26.340 actually break that code within minutes using differential 36:26.340 --> 36:27.160 cryptanalysis. 36:28.040 --> 36:32.120 So it's also this number of rounds is essential for the security of 36:32.120 --> 36:32.680 that algorithm. 36:35.040 --> 36:40.000 So this is a point which is also interesting. 36:40.000 --> 36:45.380 And then there are completely other approaches. 36:45.920 --> 36:47.500 So physical cryptanalysis. 36:49.060 --> 36:57.660 If DES is executed on a smart card, you can just modify the way the 36:57.660 --> 37:02.300 algorithm is executed by modifying the clocking signal or making sure 37:02.300 --> 37:08.720 that certain statements are executed in a different way. 37:10.040 --> 37:15.140 And then you look at how these changes in the execution of the 37:15.140 --> 37:17.420 algorithm modify the ciphertext. 37:18.820 --> 37:22.600 And since you know what you have influenced and you see the changes, 37:22.760 --> 37:28.560 you can find out something about the information that has been 37:28.560 --> 37:29.320 processed there. 37:29.320 --> 37:41.040 And so this type of attack actually took something like 5 key bits 37:41.040 --> 37:46.140 could be retrieved by one such modified encryption and then just a few 37:46.140 --> 37:50.280 attacks were actually sufficient to retrieve the key. 37:51.280 --> 37:57.300 But this is in effect that I mentioned before, if you make a statement 37:57.300 --> 38:02.760 on the security of a certain method, you prove something based on 38:02.760 --> 38:03.760 certain assumptions. 38:04.460 --> 38:09.500 And in such an assumption on the security, the strength of DES, you 38:09.500 --> 38:13.780 assume that it's always executed exactly as we have specified the 38:13.780 --> 38:14.220 algorithm. 38:14.220 --> 38:20.000 Now, if somebody is able to modify the way this algorithm is executed, 38:21.360 --> 38:25.660 but still using the same secret information, you can actually get 38:25.660 --> 38:29.720 information on what kind of bits are in that secret key. 38:30.540 --> 38:32.120 And in this way it can be attacked. 38:33.300 --> 38:43.480 And these are so-called side-channel attacks. 38:45.500 --> 38:51.540 And the side-channel attacks use a completely different approach than 38:51.540 --> 38:56.480 the normal way you would actually try to look at or to attack. 38:56.480 --> 39:01.580 You have this algorithm and you look at how you can actually get 39:01.580 --> 39:03.840 information from the encrypted version. 39:05.180 --> 39:08.240 But to modify the algorithm is a completely different idea. 39:09.920 --> 39:13.200 And then another point is just to measure the power consumption. 39:14.920 --> 39:21.360 So you know that the power consumption of an electronic circuit is 39:21.360 --> 39:25.140 different for different information that is processed. 39:25.860 --> 39:35.820 Because we have CMOS technology and we know that if we have changes 39:35.820 --> 39:40.840 from 0 to 1 or from 1 to 0, this leads to power consumption. 39:41.320 --> 39:45.740 If you don't modify something, you have less power consumption. 39:46.880 --> 39:52.080 And so if you look at the power consumption while a certain algorithm 39:52.080 --> 39:56.020 is executed, this is characteristic for the information that is 39:56.020 --> 39:56.900 actually processed. 39:57.960 --> 40:10.780 Now if you can analyze that in an interesting way, you find out what 40:10.780 --> 40:13.580 those bits actually are of those secret keys. 40:15.320 --> 40:18.920 So this is another side-channel attack. 40:19.020 --> 40:20.560 You don't look at the algorithm at all. 40:20.620 --> 40:21.600 You don't modify it. 40:21.600 --> 40:24.520 You just look at the power consumption, which certainly was not 40:24.520 --> 40:27.300 considered by those who designed the algorithm. 40:29.180 --> 40:36.260 And then another idea is you have your chip, your smart card, and you 40:36.260 --> 40:38.220 have the chip in that. 40:38.820 --> 40:51.140 And if the location of the key in the memory is known, you can just 40:51.140 --> 40:57.840 try to retrieve that information from that part of the memory. 40:57.840 --> 41:05.360 Even if it is protected, if you can access that externally, you can 41:05.360 --> 41:08.020 get that information. 41:08.180 --> 41:11.440 You just modify the individual key bits. 41:12.160 --> 41:19.260 Now you can take some very small instrument and modify the value in 41:19.260 --> 41:24.740 one cell of that memory where you know the key is stored at that 41:24.740 --> 41:25.220 location. 41:25.220 --> 41:31.860 Now if you put in a zero there, or a one, and you notice that 41:31.860 --> 41:37.100 afterwards you have a parity error, you know that you modified the 41:37.100 --> 41:38.300 value that was there. 41:38.840 --> 41:42.720 If you don't get a parity error, you know that this is exactly the 41:42.720 --> 41:44.460 value that was there before. 41:45.280 --> 41:52.000 And so by doing that for all the different locations of your key, for 41:52.000 --> 42:02.100 all the bits of the key, you can find out the value of that key just 42:02.100 --> 42:06.680 by physical manipulation of that part of memory. 42:07.540 --> 42:12.020 So in order to protect against that, you have to make sure that it's 42:12.020 --> 42:19.140 not possible to modify the values stored in memory without destroying 42:19.140 --> 42:21.220 the memory completely. 42:22.620 --> 42:30.180 And so this just shows how difficult it is to protect against attacks 42:30.180 --> 42:35.920 by people who are very creative in the way they try to get access to 42:35.920 --> 42:36.640 that information. 42:36.640 --> 42:43.120 So the consequence is that you have to protect in many different ways, 42:43.440 --> 42:49.560 and all these attempts to actually attack that DES algorithm succeeded 42:49.560 --> 43:00.220 in repeatable attacks where they used hundreds of thousands of 43:00.220 --> 43:08.440 computers in the internet to actually decrypt an arbitrary DES message 43:08.440 --> 43:10.040 within 22 hours. 43:10.880 --> 43:14.260 And this was considered as sufficient evidence that it's not secure 43:14.260 --> 43:17.520 enough anymore for certain purposes. 43:17.520 --> 43:28.720 And so this then led to the design of a new algorithm. 43:28.980 --> 43:31.880 So DES should be used with care. 43:32.020 --> 43:36.000 It is still available on some smart cards, but quite often. 43:37.280 --> 43:42.000 Nobody would actually use hundreds of thousands of computers to 43:42.000 --> 43:48.100 retrieve the information that is on a smart card unless there are very 43:48.100 --> 43:49.780 specific circumstances. 43:50.480 --> 43:53.160 So quite often it is still reasonable to use that, but you have to 43:53.160 --> 43:54.040 know about the risks. 43:54.040 --> 44:02.160 If you use triple DES where you actually use two or three different 44:02.160 --> 44:07.640 keys depending on the schema of triple DES in order to have an 44:07.640 --> 44:13.780 extended encryption, then it is more secure and these methods that are 44:13.780 --> 44:16.920 used there are no longer successful. 44:16.920 --> 44:22.040 So triple DES is still considered to be a reasonable method of 44:22.040 --> 44:22.480 encryption. 44:22.840 --> 44:30.960 You just need to use DES in a slightly more complex way and then it is 44:30.960 --> 44:32.500 more secure. 44:35.460 --> 44:42.220 Now, I will come back to the advanced encryption standard a little bit 44:42.220 --> 44:43.160 later, not today. 44:43.160 --> 44:49.440 Today I will now switch to the alternative to using symmetric methods. 44:50.340 --> 44:56.920 So if we use symmetric methods, if you have many different persons you 44:56.920 --> 45:03.300 would like to communicate securely, they, like for every communication 45:03.300 --> 45:08.520 between any two persons here, you would need an individual key. 45:09.280 --> 45:13.220 So for n persons you would need order of n squared different keys 45:13.220 --> 45:17.660 because the communication between each pair should be made secure. 45:19.000 --> 45:25.540 And you have to transmit all these keys very securely and so this is a 45:25.540 --> 45:26.300 difficult problem. 45:26.740 --> 45:30.080 The alternative is to transmit the keys publicly. 45:31.000 --> 45:36.340 And you would say immediately what is the sense of transmitting a key 45:36.340 --> 45:44.680 publicly if this is the key for using encryption or decryption. 45:44.860 --> 45:45.620 It should be secret. 45:46.480 --> 45:52.680 So the ingenious idea here was that every person has her own public 45:52.680 --> 45:57.400 key to be used for sending her encrypted messages. 45:58.260 --> 46:04.600 So you have Alice and Bob. 46:04.900 --> 46:09.460 Bob wants to send a message, just uses the public key of Alice. 46:10.080 --> 46:16.840 Now here I have phrased it in a way that these public keys are in some 46:16.840 --> 46:18.680 kind of public key book. 46:19.500 --> 46:24.140 You will see a little bit later that this is somehow a naive idea. 46:24.140 --> 46:30.780 Nevertheless, you need some statements like Bob needs information on 46:30.780 --> 46:34.400 that public key of Alice. 46:35.620 --> 46:40.300 And this has to be done in a way that you can be sure that this is 46:40.300 --> 46:47.100 actually the public key of Alice and not the public key of Eve. 46:48.100 --> 46:54.880 Because if Eve would use redirection, and if Bob did not get the 46:54.880 --> 46:59.860 public key of Alice but the public key of Eve, Bob would send an 46:59.860 --> 47:02.420 encrypted message to Eve. 47:03.100 --> 47:10.400 Eve would then take that message, decrypt it with her secret key, and 47:10.400 --> 47:16.400 then use Alice's public key in order to send her a modified message. 47:16.400 --> 47:19.840 And in this way, she could actually interfere. 47:20.100 --> 47:22.020 So this is an important problem. 47:22.380 --> 47:26.640 You have to know about the validity of those public keys. 47:26.740 --> 47:33.000 One of the major problems of that kind of approach is public key 47:33.000 --> 47:37.240 cryptosystems need certified information on public keys. 47:38.340 --> 47:43.240 The other point that I already mentioned is that every person also has 47:43.240 --> 47:44.400 her own secret key. 47:44.400 --> 47:48.800 And so with a secret key, you can actually decrypt the message that 47:48.800 --> 47:52.980 somebody has sent to you and encrypt it with your public key. 47:54.160 --> 47:57.880 So if you don't have the secret key, you cannot retrieve the 47:57.880 --> 48:00.600 information that was in that message. 48:01.100 --> 48:02.460 So you have a message. 48:03.680 --> 48:08.940 You can encrypt that using your public key. 48:08.940 --> 48:14.220 And then if you have a secret key, the receiver can use his or her 48:14.220 --> 48:19.860 secret key to retrieve or to transform that cipher into some message 48:19.860 --> 48:23.240 which certainly should be the same as the original message. 48:24.120 --> 48:29.320 So S of P of M should be M for every message. 48:29.960 --> 48:32.340 Actually, the other way around also. 48:33.960 --> 48:40.120 So P of S of M also should be M. 48:41.100 --> 48:45.860 I've mentioned this because it's also of interest, although for this 48:45.860 --> 48:51.120 scenario, it looks a bit strange. 48:52.100 --> 48:56.860 Because if you have encrypted something with your secret key and sent 48:56.860 --> 49:04.260 that encrypted message somewhere, for what purpose would you need that 49:04.260 --> 49:09.900 everybody can use your public key to decrypt that and retrieve that 49:09.900 --> 49:10.360 message? 49:10.700 --> 49:12.900 This certainly is not for secure communication. 49:13.060 --> 49:14.240 It's not for confidentiality. 49:14.240 --> 49:17.480 But that relationship would be for authentication. 49:18.380 --> 49:23.700 That you can find out the secret key must have been used in order to 49:23.700 --> 49:24.780 send a certain message. 49:25.460 --> 49:29.120 So since the secret key is bound to a person, that person must have 49:29.120 --> 49:29.620 done that. 49:29.620 --> 49:36.120 So this here would be for authentication. 49:38.240 --> 49:41.980 And this here actually is for confidentiality. 49:45.920 --> 49:49.100 So let's look at this confidentiality requirement. 49:50.140 --> 49:54.920 And the question is what kind of information is actually in those 49:54.920 --> 49:55.300 keys. 49:55.300 --> 49:58.040 The pairs of keys should all be different. 50:00.100 --> 50:00.740 Definitely. 50:01.100 --> 50:05.760 Otherwise, people could use the same communication. 50:07.000 --> 50:09.820 And then it should be secret. 50:09.940 --> 50:13.440 It should be hard to actually get the information that is in there. 50:13.440 --> 50:18.580 So to derive the secret information, the secret key from the public 50:18.580 --> 50:26.460 key, should be as hard as decrypting the encrypted message without 50:26.460 --> 50:28.420 knowing the secret key. 50:28.960 --> 50:31.420 So it must be a difficult problem. 50:32.660 --> 50:35.920 Both keys should be easily generated. 50:37.180 --> 50:41.680 So it must not be very expensive to generate those keys. 50:41.680 --> 50:46.100 And encryption and decryption should also not be too expensive. 50:46.700 --> 50:47.980 Now this is a real problem. 50:48.700 --> 50:54.040 The standard method which I will present to you, the RSA algorithm, is 50:54.040 --> 50:54.540 expensive. 50:55.600 --> 50:58.560 This has consequences for the way we actually use that, as you will 50:58.560 --> 50:59.920 see a little bit later. 51:00.980 --> 51:08.800 But requirements one to four are actually quite well implemented 51:08.800 --> 51:09.200 meanwhile. 51:10.800 --> 51:16.060 Now there is one information that one should know about here. 51:16.580 --> 51:18.580 So-called one-way functions. 51:19.400 --> 51:24.520 So a one-way function is a function that is easy to compute but hard 51:24.520 --> 51:25.040 to invert. 51:25.440 --> 51:32.740 If you have a lock, for example, such a lock can be easily locked just 51:32.740 --> 51:37.340 by pushing that part here into some hole there. 51:37.340 --> 51:38.280 Then it is locked. 51:38.820 --> 51:41.780 But to unlock it, you need a specific key. 51:42.860 --> 51:48.440 So everybody can lock such a lock, but you cannot open it. 51:49.760 --> 51:54.700 So it is a function that is easy to compute but hard to invert. 51:55.700 --> 51:59.980 So if you have a certain value, you can compute f of x. 52:00.480 --> 52:05.160 But if you have f of x, it's very difficult to determine the original 52:05.160 --> 52:05.660 argument. 52:07.060 --> 52:10.060 And there are many different examples. 52:10.300 --> 52:16.700 So a simple example is that you can easily find a person's phone 52:16.700 --> 52:17.680 number in the phone book. 52:18.400 --> 52:23.820 But to find the person related to a certain phone number is more 52:23.820 --> 52:24.240 difficult. 52:25.120 --> 52:30.920 If we assume that you don't have an inverted table there. 52:32.800 --> 52:36.040 Then factorization is an interesting method. 52:37.080 --> 52:40.160 That means, like, what is factorization about? 52:41.340 --> 52:47.620 If you multiply two prime numbers, you can get a certain value n. 52:48.060 --> 52:49.240 A product of two numbers. 52:49.380 --> 52:50.400 To multiply is easy. 52:51.420 --> 52:54.040 Even if you have very large numbers, it's still easy. 52:54.840 --> 52:56.320 We know how to do that. 52:56.320 --> 53:03.960 But if you have just that product, n, how do you find out the two 53:03.960 --> 53:05.240 prime factors? 53:06.620 --> 53:10.840 And this is believed to be hard. 53:11.180 --> 53:15.920 So we don't know whether it's really a very, very, very difficult 53:15.920 --> 53:16.480 problem. 53:16.680 --> 53:18.380 That means if it is, then P complete. 53:18.380 --> 53:28.700 But it is, like, so far we don't have efficient methods of actually 53:28.700 --> 53:31.340 factoring a number into its prime factors. 53:32.340 --> 53:37.720 Unless you use quantum computing. 53:42.200 --> 53:50.240 Unless quantum computing is used. 53:51.360 --> 53:57.060 With a quantum computer, there are algorithms which can very fast 53:57.060 --> 53:58.480 factor a number. 53:58.480 --> 54:04.580 So if we have that technology in some time, then those methods, those 54:04.580 --> 54:08.860 factors, or that factorization problem is no longer very difficult. 54:10.800 --> 54:16.080 And for cryptography, certainly, we need some kind of backdoor. 54:16.300 --> 54:21.020 That means if we have some additional information, we can actually 54:21.020 --> 54:21.640 invert it. 54:21.760 --> 54:23.700 So this is, again, this example with the lock. 54:23.700 --> 54:27.460 If you have the right key to insert, you can easily unlock it. 54:28.860 --> 54:33.600 Okay, then, next week, actually, I don't know who of you will be here 54:33.600 --> 54:35.440 next week on the 23rd of December. 54:36.180 --> 54:38.040 I will be here and teach the course. 54:39.240 --> 54:41.340 I would be glad to see at least some of you. 54:42.380 --> 54:46.740 So, next week, I will introduce to you the RSA cryptosystem. 54:47.100 --> 54:49.780 One of the famous asymmetric methods. 54:50.120 --> 54:51.180 Okay, that's it for today. 54:59.100 --> 55:00.340 So, good morning. 55:00.740 --> 55:09.900 This is the last lecture of this year for algorithms for internet 55:09.900 --> 55:10.440 applications. 55:11.300 --> 55:19.720 And it is a novel that I am recording this lecture looking into a 55:19.720 --> 55:23.000 classroom where there are not that many people sitting. 55:23.660 --> 55:25.380 So welcome to those who are here. 55:26.980 --> 55:30.600 Last time, we have looked at cryptographic algorithms again. 55:31.340 --> 55:34.060 And we would like to continue with that. 55:34.180 --> 55:43.980 We have looked at the different notions like cryptology separated into 55:43.980 --> 55:45.460 cryptography and cryptanalysis. 55:45.460 --> 55:52.840 I showed you the separation into different areas like symmetric key 55:52.840 --> 55:54.580 algorithms, public key algorithms. 55:54.760 --> 55:57.500 We have looked already at symmetric key algorithms. 55:57.720 --> 56:07.560 I showed you the very simple examples of a Caesar cipher, of a table 56:07.560 --> 56:10.660 cipher, then the Vigenere cipher, one-time pad. 56:10.660 --> 56:14.700 I showed you the encryption with bit sequences, which is actually a 56:14.700 --> 56:18.320 standard method for stream encryption. 56:19.280 --> 56:25.020 And like a typical stream cipher, where the key, the secret, is in the 56:25.020 --> 56:27.220 seed for the random number generator. 56:28.180 --> 56:34.820 And then we also looked at the notion of transposition, different from 56:34.820 --> 56:37.920 substitution, which we looked at up to that point. 56:38.720 --> 56:43.640 We saw that simple example of reading out a matrix in different order 56:43.640 --> 56:46.020 than having written the text into it. 56:46.360 --> 56:50.240 And then we finally looked at the DES algorithm. 56:50.460 --> 56:54.520 I showed you the principle structure, the 16 rounds of the algorithm. 56:54.940 --> 57:03.760 I showed you the essential part, the Feistel encryption around having 57:03.760 --> 57:07.720 the property that it is easily invertible because it is a XORing 57:07.720 --> 57:08.200 operation. 57:08.360 --> 57:10.900 That's one of the benefits of the XORing operation, that you can 57:10.900 --> 57:18.120 easily decrypt it or invert it by just applying the same operand twice 57:18.120 --> 57:22.740 to the same other operand. 57:23.420 --> 57:29.380 And that way you can retrieve the previous ciphers from ciphers 57:29.380 --> 57:32.740 further down in this algorithm. 57:32.740 --> 57:37.500 And so in this way invert the encryption, which means decipher an 57:37.500 --> 57:39.640 encrypted message. 57:39.860 --> 57:43.680 And then we looked in more detail at the Feistel round within DES. 57:44.120 --> 57:50.120 I showed you that there we have these compression permutations for the 57:50.120 --> 57:51.900 key to extract the round key. 57:51.900 --> 58:02.520 We have the expansion permutation for the right half of the block that 58:02.520 --> 58:03.460 has to be encrypted. 58:04.360 --> 58:09.880 And then I also showed you what's inside the S-box, at least in one. 58:09.980 --> 58:13.800 You can easily look up the other ones in the internet or in documents. 58:13.800 --> 58:21.680 And so here we have a way of transforming a 6-bit entry, which is 58:21.680 --> 58:24.500 separated into row and column index. 58:25.960 --> 58:31.020 And by looking up the value there, which is a 4-bit value, in this way 58:31.020 --> 58:34.540 you get the mapping from 6 to 4 bits. 58:35.240 --> 58:38.980 And we also looked at the tags on DES. 58:39.480 --> 58:41.700 I at least showed you some of the results. 58:41.700 --> 58:44.740 Otherwise we didn't go really into details of the different 58:44.740 --> 58:45.280 approaches. 58:45.540 --> 58:50.900 I showed you some hint on where to look for more information on 58:50.900 --> 58:52.200 cryptanalytic attacks. 58:52.760 --> 58:58.560 We also looked at side-channel attacks, like physical attacks to 58:58.560 --> 59:03.540 cryptographic algorithms, which just modify the way you actually 59:03.540 --> 59:07.020 access information on what's being done in the algorithm. 59:07.020 --> 59:14.220 And so it is a really hard job to make statements on the security of 59:14.220 --> 59:18.780 an algorithm, because you have to consider all these potential side 59:18.780 --> 59:21.400 -channel attacks, which is a very difficult task. 59:22.720 --> 59:27.480 Then we looked also at an alternative, at public-key cryptosystems. 59:27.560 --> 59:30.220 I briefly showed you the requirements that we have. 59:30.220 --> 59:35.660 One important part there is the existence of one-way functions, which 59:35.660 --> 59:40.960 are easily computed, like one-way, but the inverse is hard to compute. 59:41.520 --> 59:46.240 I gave you simple examples, and the first new slide for today is the 59:46.240 --> 59:55.640 RSA cryptosystem, which I showed, which is the standard algorithm for 59:55.640 --> 59:57.080 public -key methods. 59:57.080 --> 59:59.120 There certainly are others around. 59:59.240 --> 01:00:04.320 I will briefly mention them at the end of today's lecture, or within 01:00:04.320 --> 01:00:05.380 this lecture today. 01:00:06.080 --> 01:00:08.240 So what is this algorithm about? 01:00:08.320 --> 01:00:12.440 The RSA cryptosystem, designed by Rivis, Charmy, and Edelman in 1978. 01:00:14.020 --> 01:00:23.420 They have a public key, p for public, which is a pair of integers, n 01:00:23.420 --> 01:00:26.320 and c, where c stands for code. 01:00:26.940 --> 01:00:31.980 There is a secret key, s, which is again a pair of integers, so the n 01:00:31.980 --> 01:00:36.160 is not really the secret, but the d is the secret, and d stands for 01:00:36.160 --> 01:00:36.680 decode. 01:00:37.540 --> 01:00:43.200 c and d are values which are very large numbers. 01:00:44.220 --> 01:00:51.300 They have at most as many bits as n, and the standard lengths of this 01:00:51.300 --> 01:00:57.260 n are a few thousand bits nowadays. 01:00:58.040 --> 01:01:02.220 The RSA encryption works in the following way, that you have your 01:01:02.220 --> 01:01:09.180 message, and you chop your message into segments, which are all less 01:01:09.180 --> 01:01:10.380 or equal than n. 01:01:11.500 --> 01:01:16.400 And so this is then m1, m2, and so on. 01:01:16.460 --> 01:01:23.240 So you have these sequences of blocks smaller than n, and actually not 01:01:23.240 --> 01:01:29.080 less or equal, but actually smaller, really smaller than n. 01:01:31.500 --> 01:01:37.900 The operation that you perform now is a numeric operation. 01:01:38.320 --> 01:01:42.420 You compute mi to the c modulo n. 01:01:43.110 --> 01:01:52.680 So you compute... mi is a value which can be almost as large as n, 01:01:53.260 --> 01:01:59.260 which may have a few thousand bits, and c is a value which can by 01:01:59.260 --> 01:02:01.240 itself have a few thousand bits. 01:02:01.440 --> 01:02:06.880 So you can imagine that that is a really time-consuming operation to 01:02:06.880 --> 01:02:11.040 compute mi to the c, and so you really have to do something about 01:02:11.040 --> 01:02:13.400 making that as efficient as possible. 01:02:14.460 --> 01:02:18.680 And then you always compute in the range of numbers less than n, 01:02:18.760 --> 01:02:22.340 because you computed modulo this value n. 01:02:23.000 --> 01:02:25.180 Now, this is the encryption. 01:02:25.440 --> 01:02:31.280 You get some new value, which again is a value that is less than n, by 01:02:31.280 --> 01:02:32.240 the modulo operation. 01:02:32.240 --> 01:02:39.120 And then the decryption works in a way that you divide the encrypted 01:02:39.120 --> 01:02:45.180 message, c, again into sequences of numbers c1, ck, smaller than n. 01:02:45.860 --> 01:02:57.120 And you compute mi now from this ci by taking ci to the power d modulo 01:02:57.120 --> 01:02:57.380 n. 01:02:57.380 --> 01:03:01.660 And again, we have very large numbers, may have very large numbers, 01:03:01.760 --> 01:03:04.260 certainly not all of these numbers will be large, but most of them. 01:03:05.120 --> 01:03:09.960 So this is a time-consuming operation, violating in some way the 01:03:09.960 --> 01:03:12.880 requirement that encryption and decryption should be easy. 01:03:14.240 --> 01:03:18.740 So, how can we choose, like this looks a bit strange, how is that 01:03:18.740 --> 01:03:28.540 possible that you can retrieve the value mi by computing the power of 01:03:28.540 --> 01:03:33.080 the original mi to the c and then the result taking the power to the 01:03:33.080 --> 01:03:33.320 d. 01:03:34.120 --> 01:03:42.140 Now this works because we specifically choose n, c, and d, and so 01:03:42.140 --> 01:03:46.400 certainly here I say for n having 1024 bits, but this certainly can be 01:03:46.400 --> 01:03:48.740 any other value also. 01:03:48.880 --> 01:03:50.640 This is just one assumption. 01:03:51.100 --> 01:03:56.620 Nowadays we would rather have 2048 or even 4096. 01:03:59.120 --> 01:04:00.920 So this is a 2 there. 01:04:01.760 --> 01:04:03.300 Now, what do we do? 01:04:03.380 --> 01:04:08.940 We randomly generate two large prime numbers p and q, both having, 01:04:09.140 --> 01:04:14.820 like if we have 1024 bits, we choose two numbers having 512 bits. 01:04:14.980 --> 01:04:24.240 In this way, the product has exactly double the number of bits, and so 01:04:24.240 --> 01:04:29.100 we want to have that many bits, so the two prime numbers should be 01:04:29.100 --> 01:04:29.720 very large. 01:04:30.920 --> 01:04:33.960 We will come back to the problem of how we can actually select those 01:04:33.960 --> 01:04:34.640 prime numbers. 01:04:35.080 --> 01:04:37.320 Now we compute the product of those prime numbers. 01:04:37.420 --> 01:04:41.080 This can be done certainly by standard arithmetic, although then it's 01:04:41.080 --> 01:04:44.000 quite time-consuming, it should be done more efficiently. 01:04:44.000 --> 01:04:47.780 And the product of p and q is our value n. 01:04:48.860 --> 01:04:55.440 You see, if you just have n, you actually don't know p and q unless 01:04:55.440 --> 01:05:00.440 you manage to factor that number n into those two prime factors, which 01:05:00.440 --> 01:05:07.760 I already mentioned is one of those one-way functions. 01:05:09.600 --> 01:05:17.040 Now, we determine randomly one value c, but the requirement is that c 01:05:17.040 --> 01:05:20.860 is prime relative to p-1 times q-1. 01:05:21.020 --> 01:05:24.440 I will explain to you in a moment why we have that requirement, that 01:05:24.440 --> 01:05:26.580 value p-1 times q-1. 01:05:26.580 --> 01:05:32.920 And then we determine a value d such that the product of c times d is 01:05:32.920 --> 01:05:37.560 congruent to one modulo p-1 times q-1. 01:05:38.420 --> 01:05:41.780 And we have the following lemma. 01:05:42.240 --> 01:05:49.440 If we have chosen n, c, and d in this way, then we have for all values 01:05:49.440 --> 01:05:55.080 less than n this nice property that m taken to the power cd is 01:05:55.080 --> 01:05:56.780 congruent to m modulo n. 01:05:56.780 --> 01:06:01.140 And we will go into a little bit into showing why that is the case. 01:06:01.340 --> 01:06:04.020 We don't go into the complete depth of that proof. 01:06:04.800 --> 01:06:10.480 But first of all, let's briefly look again what actually it means to 01:06:10.480 --> 01:06:15.100 say x and y are congruent modulo z. 01:06:15.100 --> 01:06:16.700 What does it mean? 01:06:17.160 --> 01:06:22.800 That the difference of x minus y is a multiple of z. 01:06:23.120 --> 01:06:28.480 So it means that the difference here, the difference of m to the c 01:06:28.480 --> 01:06:33.040 times d and m is a multiple of n. 01:06:33.850 --> 01:06:40.080 And up here, cd-1 is a multiple of p-1 times q-1. 01:06:40.420 --> 01:06:42.040 So this is the essential point. 01:06:42.380 --> 01:06:49.640 Or you could also say if you divide the values x and y by z, then you 01:06:49.640 --> 01:06:51.920 have the same remainder. 01:06:53.360 --> 01:06:59.840 Okay, now the validity of that lemma depends on two essential insights 01:06:59.840 --> 01:07:01.140 of number theory. 01:07:01.540 --> 01:07:06.140 The first one is the small or the little theorem of Fermat. 01:07:06.660 --> 01:07:11.280 And this little theorem is about the following. 01:07:11.280 --> 01:07:18.240 It states that if you have a prime number p and another value a which 01:07:18.240 --> 01:07:24.540 is not divisible by p, then a to the p minus 1 is congruent to one 01:07:24.540 --> 01:07:25.400 modulo p. 01:07:26.240 --> 01:07:29.020 Now this looks similar to what we have up here. 01:07:29.440 --> 01:07:30.560 We'll come back to that. 01:07:31.080 --> 01:07:36.880 So p-prime a not divisible by p means a to the p minus 1 is congruent 01:07:36.880 --> 01:07:37.960 to one modulo p. 01:07:37.960 --> 01:07:42.880 And then there is a generalization of that, which is the following. 01:07:43.100 --> 01:07:48.420 For n out of n, we define the following function phi of n, which is 01:07:48.420 --> 01:07:49.700 called the Euler function. 01:07:49.700 --> 01:07:59.920 And this Euler function counts the number of values m between 1 and n, 01:08:00.420 --> 01:08:04.900 which are prime relative to n, which means that they don't have a 01:08:04.900 --> 01:08:07.720 common divisor with n. 01:08:08.800 --> 01:08:13.000 We'll look at specific examples of that in a moment. 01:08:13.640 --> 01:08:15.780 So this is the Euler function. 01:08:16.780 --> 01:08:23.700 And the theorem that we utilize for this proof of the correctness of 01:08:23.700 --> 01:08:31.000 the RSA algorithm is that if n and a are natural numbers and a is 01:08:31.000 --> 01:08:36.360 prime relative to n, that means they don't have common divisors, non 01:08:36.360 --> 01:08:41.480 -trivial common divisors, then a to the phi of n is congruent to one 01:08:41.480 --> 01:08:42.200 modulo n. 01:08:42.200 --> 01:08:47.880 So another statement like the one we had in the little theorem of 01:08:47.880 --> 01:08:53.220 Fermat, but here it states, or it is not a to the p minus 1 where p is 01:08:53.220 --> 01:08:58.580 a prime number, but here it is a to the phi of n, which is the Euler 01:08:58.580 --> 01:09:00.280 function of that value n. 01:09:00.880 --> 01:09:07.420 Now, assume that this little theorem of Fermat and Euler's theorem 01:09:07.420 --> 01:09:14.040 hold, then we will show that the RSA algorithm actually is correct. 01:09:14.040 --> 01:09:21.140 The corollary of this certainly is that for all a and n, a to the phi 01:09:21.140 --> 01:09:26.820 of n minus 1 is the modular inverse of a with respect to n. 01:09:27.820 --> 01:09:37.400 So if you have modular computation for n, then a to the phi of n minus 01:09:37.400 --> 01:09:47.000 1 certainly is the modular inverse because a to the phi of n minus 1 01:09:47.000 --> 01:09:51.460 times a is congruent to one modulo n. 01:09:54.080 --> 01:09:55.280 So that's trivial. 01:09:56.080 --> 01:09:59.400 Okay, nice little corollary which will be used. 01:09:59.960 --> 01:10:05.460 Okay, now let's briefly look at our situation where we have these two 01:10:05.460 --> 01:10:09.340 numbers p and q, these two prime numbers p and q. 01:10:10.180 --> 01:10:15.520 And you know we have computed n, which is the product of p and q. 01:10:16.120 --> 01:10:20.180 And now the statement of this lemma is that the Euler function of p 01:10:20.180 --> 01:10:25.260 and q is just this value p minus 1 times q minus 1, which also 01:10:25.260 --> 01:10:31.040 appeared in the construction of the public and secret keys. 01:10:31.480 --> 01:10:32.980 So why is this the case? 01:10:32.980 --> 01:10:35.940 This is a rather simple observation. 01:10:36.740 --> 01:10:41.420 If p and q are prime, then we can easily see which numbers have a 01:10:41.420 --> 01:10:46.580 common divisor with p and q, so which are not prime relative to n. 01:10:48.260 --> 01:10:50.180 So which numbers are these? 01:10:50.280 --> 01:10:54.980 Well, it's just the multiples, all the multiples of p and all the 01:10:54.980 --> 01:10:56.100 multiples of q. 01:10:56.100 --> 01:11:00.860 They definitely have a non-trivial common divisor. 01:11:01.900 --> 01:11:07.340 In particular, these values here have a non-trivial common divisor p, 01:11:07.820 --> 01:11:11.080 and those here have a non-trivial common divisor q. 01:11:12.280 --> 01:11:14.000 So how many numbers are these? 01:11:14.120 --> 01:11:18.920 Here we have just definitely q values. 01:11:19.320 --> 01:11:23.920 Here we have p values, so we have p plus q values there. 01:11:23.920 --> 01:11:27.020 p plus q minus 1. 01:11:27.220 --> 01:11:29.200 You see here only up to p minus 1. 01:11:30.000 --> 01:11:35.820 So this is the number of values which have a common divisor with p 01:11:35.820 --> 01:11:42.100 times q, so all the remaining numbers are numbers which are prime 01:11:42.100 --> 01:11:44.420 relative to p times q. 01:11:45.360 --> 01:11:46.800 So, what is that? 01:11:46.800 --> 01:11:54.760 p times q are all the numbers, and we subtract p plus q minus 1. 01:11:58.100 --> 01:12:04.700 And these are the numbers which are smaller than p times q and have a 01:12:04.700 --> 01:12:06.180 non -trivial common divisor. 01:12:06.800 --> 01:12:10.360 And this is exactly p minus 1 times q minus 1. 01:12:10.360 --> 01:12:14.600 So, this is easily computed, certainly. 01:12:14.800 --> 01:12:20.260 So this is the number of integers which are prime relative to p times 01:12:20.260 --> 01:12:26.120 q, which is our value n, the modulus for the RSA computation. 01:12:27.020 --> 01:12:30.860 Now, let's go back to the RSA algorithm and see what this means for 01:12:30.860 --> 01:12:37.620 getting insights into the correctness of that algorithm. 01:12:37.620 --> 01:12:42.160 So if p and q are prime, we now know that the Euler function is p 01:12:42.160 --> 01:12:44.660 minus 1 times q minus 1. 01:12:46.180 --> 01:12:52.080 Thus, if we multiply, or if we compute m to the p minus 1 times q 01:12:52.080 --> 01:12:58.100 minus 1, this is m to the phi of n, this is congruent to 1 modulo n 01:12:58.100 --> 01:13:00.660 due to the result from Euler's theorem. 01:13:01.570 --> 01:13:07.240 Now, certainly if we multiply both sides with m, then m to the p minus 01:13:07.240 --> 01:13:12.440 1 times q minus 1 plus 1 is congruent to m modulo n. 01:13:13.280 --> 01:13:18.120 Now, it would be nice if this here actually would be in some way, or 01:13:18.120 --> 01:13:22.660 could be related to c times d, because remember that was what we were 01:13:22.660 --> 01:13:30.620 looking for, some exponent to m such that m to this exponent is 01:13:30.620 --> 01:13:32.280 congruent to m modulo n. 01:13:33.880 --> 01:13:40.740 Now, we have chosen c and d such that c times d is congruent to 1 01:13:40.740 --> 01:13:44.940 modulo p minus 1 times q minus 1, the Euler function of n. 01:13:45.640 --> 01:13:51.980 Now, this is exactly the same as stating that c d minus 1 is a 01:13:51.980 --> 01:13:57.560 multiple of that modulus, so a multiple of p minus 1 times q minus 1. 01:13:57.640 --> 01:14:01.940 There exists a k such that c d minus 1 is k times that modulus. 01:14:02.680 --> 01:14:10.420 And now this means if we compute m to the c times d, this c times d 01:14:10.420 --> 01:14:19.740 is, m to the c times d is, well, a multiple of p minus 1 times q minus 01:14:19.740 --> 01:14:21.120 1 plus 1. 01:14:25.840 --> 01:14:30.480 And a multiple of p minus 1 times q minus 1, each multiple of p minus 01:14:30.480 --> 01:14:38.540 1 times q minus 1 in the exponent of m is, as we have stated here, 01:14:39.000 --> 01:14:39.860 congruent to 1. 01:14:39.860 --> 01:14:46.100 So all these cancel out, and the only thing which remains is that m to 01:14:46.100 --> 01:14:49.000 the c times d is actually congruent to m. 01:14:49.640 --> 01:14:51.320 And so this is what we wanted to have. 01:14:52.400 --> 01:14:59.100 And so we have shown this is actually a correct algorithm. 01:14:59.760 --> 01:15:05.880 And the interesting point is that even if m is not prime relative to 01:15:05.880 --> 01:15:10.960 n, so this was the requirement here, m is prime relative to n, now we 01:15:10.960 --> 01:15:12.560 assume that m is not prime. 01:15:12.780 --> 01:15:17.680 We know that there are p plus q minus 1 values which are not prime 01:15:17.680 --> 01:15:18.500 relative to m. 01:15:19.040 --> 01:15:21.440 What happens to those values? 01:15:22.220 --> 01:15:27.160 Let's assume we have a value m which is a multiple of q. 01:15:29.040 --> 01:15:39.460 Now, if we, like t definitely is less than p, and so t is prime with 01:15:39.460 --> 01:15:44.660 respect to p, and so t to the p minus 1 is congruent to 1 modulo p 01:15:44.660 --> 01:15:50.700 because of the little fama, and also q to the p minus 1 definitely is 01:15:50.700 --> 01:15:52.260 congruent to 1 modulo p. 01:15:52.980 --> 01:15:58.880 Now we can compute, we can look at the product of those in a moment. 01:15:58.880 --> 01:16:06.740 So we also know that for all k greater 0, we have that t to the k 01:16:06.740 --> 01:16:11.840 times p minus 1 times q minus 1 is definitely also congruent to 1 01:16:11.840 --> 01:16:14.460 because it's just a repetition of what we have seen up here. 01:16:14.940 --> 01:16:20.000 And also q to the k times p minus 1 times q minus 1 is congruent to 1 01:16:20.000 --> 01:16:23.840 modulo p because this is also a repetition of what we have seen up 01:16:23.840 --> 01:16:24.080 here. 01:16:25.080 --> 01:16:33.160 And that means if we compute, if we now form the product of those 01:16:33.160 --> 01:16:40.280 values, t to this power and q to this power, if we take t times q to 01:16:40.280 --> 01:16:47.700 the power k times p minus 1 times q minus 1, we get that that is 01:16:47.700 --> 01:16:50.240 congruent to 1 modulo p. 01:16:51.600 --> 01:16:58.680 And it's also, if we multiply it with t, it is congruent to t modulo 01:16:58.680 --> 01:16:58.940 p. 01:16:59.900 --> 01:17:06.040 And now we can also multiply that with q, and an easy check with the 01:17:06.040 --> 01:17:11.320 modular arithmetic shows that the product, if we now multiply with q, 01:17:12.720 --> 01:17:21.120 then here we have multiplied this power of tq with t times q, so we 01:17:21.120 --> 01:17:26.700 have t times q to this power k times p minus 1 times q minus 1 plus 1. 01:17:27.360 --> 01:17:36.060 This is t times q, congruent to t times q modulo p times q, and this 01:17:36.060 --> 01:17:37.660 is exactly what we wanted to have. 01:17:37.660 --> 01:17:44.320 So this shows that even for m, we have this nice relationship that we 01:17:44.320 --> 01:17:49.060 can retrieve m by taking it to the power c times d. 01:17:50.680 --> 01:17:56.100 So this certainly can be done in an analogous way for all multiples of 01:17:56.100 --> 01:17:58.500 p, here this was a multiple of q. 01:17:59.380 --> 01:18:07.120 Okay, now we have shown that for all values less than n, we have this 01:18:07.120 --> 01:18:11.880 nice property that m to the c times d is congruent to m modulo n. 01:18:12.260 --> 01:18:14.600 And we are done with the proof of the correctness. 01:18:17.240 --> 01:18:21.280 So, let's look now at the efficiency of that algorithm. 01:18:21.460 --> 01:18:23.240 What are the costs of the RSA algorithm? 01:18:24.820 --> 01:18:29.120 Encryption and decryption, as you have seen, use exponentiation. 01:18:29.400 --> 01:18:31.260 We certainly have to do that in a fast way. 01:18:31.880 --> 01:18:36.600 Now, the problem is, what does it mean if you do it in a naive way, if 01:18:36.600 --> 01:18:41.220 you have to compute x to the n, you could say, okay, I just take x 01:18:41.220 --> 01:18:47.780 times x times x and so on times x and this n times, and this certainly 01:18:47.780 --> 01:18:53.340 would be n times the effort to multiply two numbers with increasingly 01:18:53.340 --> 01:18:54.340 larger numbers. 01:18:55.640 --> 01:19:04.680 Now, the interesting observation is that for all x and n, we can 01:19:04.680 --> 01:19:09.340 compute x to the n with order of log n arithmetic operations. 01:19:10.020 --> 01:19:13.900 The method, the easy method, as we'll see on the next slide, is that 01:19:13.900 --> 01:19:18.400 we just continuously square x and multiply the computed powers. 01:19:18.640 --> 01:19:20.720 So, let's go to the next slide. 01:19:22.180 --> 01:19:27.200 And there, now we look at the details of fast exponentiation. 01:19:28.200 --> 01:19:36.500 So, x is an arbitrary integer and n, we want to compute x to the n, is 01:19:36.500 --> 01:19:42.520 also an arbitrary integer and an integer can be represented as a 01:19:42.520 --> 01:19:43.300 binary number. 01:19:43.300 --> 01:19:55.080 So, we just represent it as a sequence of like n as a k, a k minus one 01:19:55.080 --> 01:19:58.840 down to a zero. 01:20:00.000 --> 01:20:03.700 Now, this is the dual representation or the binary representation of 01:20:03.700 --> 01:20:04.000 n. 01:20:04.500 --> 01:20:11.880 And if we now compute x to the n, it means that we take x to a sum of 01:20:11.880 --> 01:20:16.940 powers of two, which are weighted by these ai. 01:20:17.580 --> 01:20:21.100 So, that means the ai select the powers of two that are actually 01:20:21.100 --> 01:20:23.580 needed here because ai are either zero or one. 01:20:23.580 --> 01:20:29.740 Now, if we take x to a sum of values, we can also compute or rearrange 01:20:29.740 --> 01:20:38.960 this as a product of powers of x, which are just these x to the ai 01:20:38.960 --> 01:20:40.120 times two to the i. 01:20:40.120 --> 01:20:44.880 And it means that we can do exactly what I told you. 01:20:45.220 --> 01:20:56.620 We can successively square x, certainly to get up to two to the k, the 01:20:56.620 --> 01:21:00.660 largest power that may be contained in or that is contained in n. 01:21:01.540 --> 01:21:11.240 We just need k operations and k certainly is equal to log n. 01:21:12.460 --> 01:21:22.100 Actually, the ceiling of that, no, sorry, floor of that, but it is 01:21:22.100 --> 01:21:22.960 order of log n. 01:21:23.620 --> 01:21:26.380 And so these are the powers that we need. 01:21:27.360 --> 01:21:31.180 And so this was supposed to be k. 01:21:32.160 --> 01:21:41.740 And the ai are used to select which powers of x actually have to be 01:21:41.740 --> 01:21:42.140 multiplied. 01:21:42.860 --> 01:21:49.200 So, if ai is zero, this cancels, such a power cancels out. 01:21:49.660 --> 01:21:52.840 And those where ai is one are multiplied. 01:21:53.180 --> 01:21:58.500 And so this is a simple way of squaring and multiplying with some 01:21:58.500 --> 01:22:05.920 intermediate value to get in the end the appropriate product of x to a 01:22:05.920 --> 01:22:06.740 powers of two. 01:22:06.740 --> 01:22:11.060 Now, a different way of representing that would be that we just 01:22:11.060 --> 01:22:16.880 rearrange the computation and say, okay, we can also just take x to 01:22:16.880 --> 01:22:22.260 the a0, x to the a1, x to the a2, and so on, and actually start here 01:22:22.260 --> 01:22:25.100 with x to the ak and square that. 01:22:25.100 --> 01:22:29.960 And then multiply with x to the ak-1. 01:22:30.140 --> 01:22:39.800 That means if ak-1 or some ai is zero, it is multiplication with one, 01:22:39.920 --> 01:22:41.120 which means you don't have to multiply. 01:22:41.380 --> 01:22:44.140 If it is one, we have to multiply with x. 01:22:44.140 --> 01:22:52.600 And so here we would decide whether we have to multiply with x, and 01:22:52.600 --> 01:22:55.140 then we square the resulting value. 01:22:55.980 --> 01:23:01.160 And this is exactly the same result as we have up here, so those two 01:23:01.160 --> 01:23:05.500 are equal, and immediately shows that we have two different ways of 01:23:05.500 --> 01:23:09.640 computing this power x to the n. 01:23:10.340 --> 01:23:16.500 So, one way would be to start from the least significant bit and go to 01:23:16.500 --> 01:23:19.860 the most significant bit of n, so start with a0. 01:23:20.400 --> 01:23:21.920 This is what we do here. 01:23:23.060 --> 01:23:26.920 And then go to a1, a2, and so on. 01:23:26.920 --> 01:23:31.960 This is what we do in this way, so this is right-to-left computation 01:23:31.960 --> 01:23:37.620 with respect to the ordering of this direction with respect to the 01:23:37.620 --> 01:23:38.480 bits of n. 01:23:39.660 --> 01:23:45.160 And if we decide for this algorithm, we would start with the most 01:23:45.160 --> 01:23:50.440 significant and go to the least significant bit, which means there we 01:23:50.440 --> 01:23:55.080 go left-to-right looking at the bits of n. 01:23:55.780 --> 01:24:00.760 And so this is, here actually in this formula, we start, we go from 01:24:00.760 --> 01:24:06.200 right -to-left, but referring to the ordering of the bits in the 01:24:06.200 --> 01:24:09.780 binary representation of n, it is right-to-left or left-to-right. 01:24:10.600 --> 01:24:13.700 Least significant or most significant, or most significant or least 01:24:13.700 --> 01:24:14.180 significant. 01:24:14.880 --> 01:24:21.580 The complexity of both operations is, of both algorithms, is the same, 01:24:22.260 --> 01:24:25.980 but the arrangement, the way we compute is slightly different. 01:24:25.980 --> 01:24:31.520 So we have successive squarings and we have to decide what we do with 01:24:31.520 --> 01:24:33.940 the value of those bits of n. 01:24:34.780 --> 01:24:38.780 Okay, let's go back to the previous slide. 01:24:39.760 --> 01:24:44.580 Here we have to look at what that means for the costs. 01:24:44.580 --> 01:24:48.860 So we have to perform multiplication, squaring. 01:24:49.900 --> 01:24:51.540 Now, we have long integers. 01:24:51.840 --> 01:24:57.440 The values that we have here have several thousand bits, or at least a 01:24:57.440 --> 01:24:59.500 thousand, usually a few thousand bits. 01:24:59.500 --> 01:25:03.760 Now this means that our standard arithmetic is not sufficient. 01:25:04.220 --> 01:25:06.580 We have operations on long integers. 01:25:07.300 --> 01:25:13.080 So if this is the large number, we have to chop it into our root size, 01:25:13.280 --> 01:25:15.140 so maybe 32. 01:25:15.140 --> 01:25:21.860 If you are lucky, you have a 64-bit computer, then you have 64-bit 01:25:21.860 --> 01:25:25.700 values, but still this is not sufficient. 01:25:25.980 --> 01:25:37.840 So if you have 1024 bits in your number, you need 32 words in that 01:25:37.840 --> 01:25:39.200 value. 01:25:39.200 --> 01:25:42.840 So it will represent 1024 bits. 01:25:44.520 --> 01:25:51.140 Okay, so if you just perform naive multiplication, you have order of k 01:25:51.140 --> 01:25:53.960 -square single word operations. 01:25:54.120 --> 01:25:57.080 That's simple, naive matrix multiplication. 01:25:57.420 --> 01:26:01.340 Not matrix multiplication, this is number multiplication. 01:26:02.220 --> 01:26:09.200 Now, if you do it in a slightly more efficient way, you use a 01:26:09.200 --> 01:26:16.500 recursive approach, and you can take that complexity down to k to the 01:26:16.500 --> 01:26:17.480 1.5. 01:26:17.620 --> 01:26:20.320 It's an easy exercise to try to do that. 01:26:21.160 --> 01:26:25.740 And if you are even more knowledgeable, you would use FFT, the fast 01:26:25.740 --> 01:26:31.300 Fourier transform, which I don't cover in this course, but in my 01:26:31.300 --> 01:26:32.580 course on efficient algorithms. 01:26:33.580 --> 01:26:38.220 This FFT approach for multiplication actually leads to a reduction 01:26:38.220 --> 01:26:47.960 down to k log k operations on long operations. 01:26:48.850 --> 01:26:57.280 So here the approach is that if we have k word integers, that means k 01:26:57.280 --> 01:26:59.080 words which make up one value. 01:26:59.480 --> 01:27:05.240 This is showing the complexity of that, order of k log k. 01:27:05.240 --> 01:27:08.860 Now what does this mean for specific values? 01:27:09.020 --> 01:27:14.460 If we have 32-bit arithmetic, an exponent length of 1024 bits, that's 01:27:14.460 --> 01:27:17.520 the length of n for the exponent. 01:27:18.260 --> 01:27:20.040 Now the exponent is n. 01:27:23.420 --> 01:27:28.740 It means that... so actually the number of operations that we have 01:27:28.740 --> 01:27:34.620 here, the order of log n it states, it's 2 times log n actually. 01:27:34.620 --> 01:27:43.620 And now log n for a 1024-bit value is 1024 bits. 01:27:43.980 --> 01:27:48.960 So it's 2 times 1024 operations. 01:27:49.780 --> 01:27:56.980 And now each operation takes k log k single word operations. 01:27:56.980 --> 01:28:00.220 Now that is... k in this case is 32. 01:28:01.180 --> 01:28:02.380 And log k is 5. 01:28:03.020 --> 01:28:13.300 And this product is, as you see here, 327,680 operations. 01:28:13.300 --> 01:28:19.380 Now this is a rather naive approach to do it in this way, although we 01:28:19.380 --> 01:28:23.140 already have used here intelligent multiplication. 01:28:24.220 --> 01:28:27.560 But nevertheless, it can be done in a different way. 01:28:27.560 --> 01:28:32.200 You can actually use modular arithmetic. 01:28:32.500 --> 01:28:34.740 You can use the Chinese remainder theorem. 01:28:35.220 --> 01:28:41.440 You can use parallelization, pipelining, construct a hardware 01:28:41.440 --> 01:28:43.000 implementation of that algorithm. 01:28:43.000 --> 01:28:46.780 It would be a pleasure for me to tell you more about that, but we 01:28:46.780 --> 01:28:48.780 don't have the time for that, not in this course. 01:28:49.540 --> 01:28:53.420 But in this way, you can achieve RSA encryption at quite high data 01:28:53.420 --> 01:28:53.880 rates. 01:28:54.420 --> 01:28:57.920 But nevertheless, the costs are still quite high. 01:28:57.920 --> 01:29:06.140 And so usually RSA is viewed to be too large to be used on large 01:29:06.140 --> 01:29:07.420 amounts of data. 01:29:07.640 --> 01:29:09.440 The costs of RSA are just too large. 01:29:10.420 --> 01:29:12.520 And so we have to do something about that. 01:29:12.520 --> 01:29:19.020 And at first sight, it would mean, well, you don't use RSA at all on 01:29:19.020 --> 01:29:22.360 the documents that we would like to communicate. 01:29:22.980 --> 01:29:26.760 But you will see a little bit later how we actually get around that. 01:29:26.760 --> 01:29:33.280 So we just have to combine RSA with other cryptographic methods, which 01:29:33.280 --> 01:29:36.080 are computed in an easier way. 01:29:37.840 --> 01:29:46.700 Now let's look at how we can... this was fast exponentiation, which we 01:29:46.700 --> 01:29:47.500 have looked at already. 01:29:48.900 --> 01:29:52.100 Again, let's look now at the cost of cryptanalysis. 01:29:52.260 --> 01:29:56.220 The first was the cost of computing the encryption and decryption. 01:29:56.640 --> 01:29:58.340 Now what about cryptanalysis? 01:29:58.440 --> 01:30:02.640 I briefly mentioned that factorization is a one-way function. 01:30:02.640 --> 01:30:08.940 So the problem that we have to look at here is that we are given N, we 01:30:08.940 --> 01:30:14.540 are given C, and we would like, like this is the public key, and now 01:30:14.540 --> 01:30:16.920 you would like to get P and Q from that. 01:30:16.920 --> 01:30:21.820 Now this requires factorization of N, and I mentioned already that it 01:30:21.820 --> 01:30:23.160 is a very complex operation. 01:30:23.840 --> 01:30:29.220 So the currently best-known methods are in complexity around what I 01:30:29.220 --> 01:30:30.320 have stated here. 01:30:31.150 --> 01:30:34.640 And so B is the number of bits of N. 01:30:34.780 --> 01:30:39.900 You see that here you have that in the exponent of E, and then you 01:30:39.900 --> 01:30:41.900 have also log B in there. 01:30:42.140 --> 01:30:48.100 This is quite a large value, and if you assume or make certain 01:30:48.100 --> 01:30:55.660 assumptions on the speed of your computer, and if you just assume that 01:30:55.660 --> 01:31:03.740 N is a number having 300 decimal digits, then in a naive over-the 01:31:03.740 --> 01:31:08.640 -thumb computation, you get something like a few thousand years to 01:31:08.640 --> 01:31:13.100 actually compute the factorization regardless of which number of that 01:31:13.100 --> 01:31:14.000 size you have. 01:31:14.000 --> 01:31:19.240 Now this is at least true with respect to current knowledge. 01:31:20.080 --> 01:31:26.860 There may be some advances in algorithmics which might give us new 01:31:26.860 --> 01:31:29.220 insights on how to compute factorization. 01:31:29.460 --> 01:31:34.760 In particular, we know of one insight which is valid as soon as we 01:31:34.760 --> 01:31:36.180 have quantum computing. 01:31:36.180 --> 01:31:41.700 And so if you have a quantum computer, you can actually get 01:31:41.700 --> 01:31:47.640 factorization in a very simple way, and this certainly is some kind of 01:31:47.640 --> 01:31:55.180 threat to the security of everything which is encrypted using such a 01:31:55.180 --> 01:31:57.160 public key method like RSA. 01:31:57.160 --> 01:32:05.380 But to do something against that, if you are interested in having 01:32:05.380 --> 01:32:10.220 security over a long period of time, we need very long keys, much 01:32:10.220 --> 01:32:15.120 longer than for symmetric methods, because here, as I said, the 01:32:15.120 --> 01:32:20.360 strength of the algorithm, the cryptographic strength, depends on the 01:32:20.360 --> 01:32:23.060 complexity of factoring the numbers. 01:32:23.060 --> 01:32:32.240 And so these have to be very large numbers, whereas for the symmetric 01:32:32.240 --> 01:32:38.800 methods, we had other problems that had to be looked at in order to 01:32:38.800 --> 01:32:43.760 successfully attack these symmetric methods. 01:32:44.220 --> 01:32:45.980 So there the keys could be smaller. 01:32:47.380 --> 01:32:47.980 Okay. 01:32:49.700 --> 01:32:52.480 One question is, we need these prime numbers. 01:32:52.560 --> 01:32:53.280 How do we do that? 01:32:53.380 --> 01:32:56.120 How can we actually determine large prime numbers? 01:32:56.300 --> 01:33:01.480 So we have to find the largest prime number less than or equal to some 01:33:01.480 --> 01:33:02.880 value n. 01:33:03.880 --> 01:33:10.140 And so, like I said, we would like to have prime numbers having 512 or 01:33:10.140 --> 01:33:15.040 1024 bits, and so 2 to the 1024 would be that value. 01:33:15.040 --> 01:33:19.440 Now one simple method is the sieve of Eratosthenes. 01:33:19.920 --> 01:33:24.100 So there we just write down all numbers from 2 to n. 01:33:24.160 --> 01:33:25.980 Let me just do that. 01:33:46.640 --> 01:33:51.220 22, 23, 24, 25, and so on. 01:33:52.180 --> 01:33:53.460 Now, what is this for? 01:33:54.300 --> 01:34:00.580 So up to n, so here it's just, I can only write down a few numbers, 01:34:00.740 --> 01:34:05.260 but you just can see in a moment what the approach actually is about. 01:34:05.260 --> 01:34:07.240 Then we repeat the following. 01:34:08.020 --> 01:34:13.960 We delete the first number, which is 2, and all its multiples from the 01:34:13.960 --> 01:34:14.260 list. 01:34:14.860 --> 01:34:26.540 So we delete 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24, and so on. 01:34:27.220 --> 01:34:33.100 So we delete the first number and all its multiples until the list 01:34:33.100 --> 01:34:34.660 consists of a single element. 01:34:35.000 --> 01:34:35.920 So we repeat that. 01:34:36.440 --> 01:34:44.400 We delete 3, its next multiple is 9, its next multiple is 15, next 01:34:44.400 --> 01:34:49.880 multiple is 21, next multiple is, well, not on this list. 01:34:50.720 --> 01:34:52.700 We do the same with 5. 01:34:53.320 --> 01:34:59.160 We delete 5 multiple. 01:35:00.600 --> 01:35:01.880 There's 25. 01:35:02.720 --> 01:35:04.540 We delete 7. 01:35:05.960 --> 01:35:09.520 You can see there's no multiple of 7 on this list. 01:35:10.200 --> 01:35:12.500 We delete 11. 01:35:14.080 --> 01:35:17.360 You can see there's no multiple of 11 over there. 01:35:17.500 --> 01:35:23.060 We delete 17, we delete 19, we delete 23, and so on. 01:35:23.080 --> 01:35:23.920 And all their multiples. 01:35:23.920 --> 01:35:31.140 And in this way you see that the list is reduced quite fast to fewer 01:35:31.140 --> 01:35:37.020 elements, and the largest remaining value on the right-hand side 01:35:37.020 --> 01:35:46.220 certainly is the largest prime, which is less or equal to n. 01:35:46.220 --> 01:35:51.080 Certainly you only have to go to half the size of the list. 01:35:53.100 --> 01:35:56.540 Okay, you don't have to go all the way to the right. 01:35:56.620 --> 01:35:59.440 So it is quite an efficient algorithm. 01:35:59.440 --> 01:36:08.700 But if you imagine you have 2 to the 1024 values, that's a very, very 01:36:08.700 --> 01:36:13.120 long list, and it's still just unfeasible to do that. 01:36:14.140 --> 01:36:17.500 So if you have these large numbers, it's unfeasible. 01:36:17.500 --> 01:36:21.700 And so another approach is to use a probabilistic approach. 01:36:22.680 --> 01:36:30.060 We just choose a random odd number having 512 bits and test whether x 01:36:30.060 --> 01:36:30.660 is prime. 01:36:31.680 --> 01:36:35.040 If it is not prime, we just increase x by 2. 01:36:35.240 --> 01:36:37.060 Certainly we only have to look at odd numbers. 01:36:37.060 --> 01:36:42.780 And then we test it again, and we do that until we finally have found 01:36:42.780 --> 01:36:47.200 the next prime, which is larger than x. 01:36:48.540 --> 01:36:54.160 Now this sounds as being much simpler, because there will be some 01:36:54.160 --> 01:37:00.520 prime number in that region, and if we are lucky, the first one is 01:37:00.520 --> 01:37:03.960 actually a prime number. 01:37:03.960 --> 01:37:08.040 But then the question remains, how can we actually test whether x is 01:37:08.040 --> 01:37:08.400 prime? 01:37:09.360 --> 01:37:12.300 And this looks like an interesting question. 01:37:12.620 --> 01:37:16.020 So how can we test whether x actually is prime? 01:37:16.140 --> 01:37:20.620 Like in that sieve of Eratosthenes, we knew that the remaining values 01:37:20.620 --> 01:37:26.820 were prime because they have not been multiples of any smaller value. 01:37:27.760 --> 01:37:31.240 Now, there is a very interesting approach. 01:37:31.980 --> 01:37:38.960 It was a seminal paper by Rabban and Miller, and they designed one of 01:37:38.960 --> 01:37:46.500 the first probabilistic algorithms by just doing the following. 01:37:46.840 --> 01:37:53.960 They first of all checked whether x is divisible by some small prime. 01:37:56.020 --> 01:37:59.260 So, less than 10,000 for example. 01:37:59.880 --> 01:38:05.120 If you have just 10,000 values, you can easily do that using the sieve 01:38:05.120 --> 01:38:06.040 of Eratosthenes. 01:38:06.040 --> 01:38:12.400 And then you repeat at most r times, so this is a limit on the number 01:38:12.400 --> 01:38:13.220 of iterations. 01:38:14.000 --> 01:38:23.640 You choose a random value less than x until this value a is a witness 01:38:23.640 --> 01:38:27.920 of the compositeness of x. 01:38:28.700 --> 01:38:29.720 Now, what does it mean? 01:38:29.820 --> 01:38:38.960 If a is a value which can show you that a is not a prime number but a 01:38:38.960 --> 01:38:41.280 multiple of a smaller value than x. 01:38:43.260 --> 01:38:50.380 So, we would like to test whether x is prime, so if we stop by having 01:38:50.380 --> 01:38:56.760 found a value a, which is a witness of the compositeness of x, then we 01:38:56.760 --> 01:38:58.080 know x is not prime. 01:38:58.080 --> 01:39:04.820 If we have repeated that r times without having found such a witness, 01:39:05.080 --> 01:39:08.100 we conclude that x must be prime. 01:39:08.720 --> 01:39:12.980 Now, this is quite a courageous statement. 01:39:13.200 --> 01:39:17.940 We will see later that it is done or is made on quite good grounds. 01:39:18.680 --> 01:39:23.360 So, what is this algorithm actually doing? 01:39:23.540 --> 01:39:28.640 How can you say that you have a witness for the compositeness of x? 01:39:28.820 --> 01:39:29.420 What do we do? 01:39:30.320 --> 01:39:35.440 We just exploit again our insights that we had seen before. 01:39:35.560 --> 01:39:45.380 The little theorem by Fermat that if x is prime, then a to the x minus 01:39:45.380 --> 01:39:47.540 1 is congruent to 1 modulo x. 01:39:48.420 --> 01:39:51.580 We have seen that little theorem of Fermat already. 01:39:52.040 --> 01:39:56.820 Now, we would like to test whether x is prime, and we know that if x 01:39:56.820 --> 01:40:00.340 is prime, then we have this property. 01:40:04.740 --> 01:40:13.360 There is another theorem, another insight from number theory, that if 01:40:13.360 --> 01:40:22.020 x is prime and if t square, just some value t, t square is congruent 01:40:22.020 --> 01:40:29.020 to 1 modulo x, then t must be 1 or minus 1. 01:40:30.020 --> 01:40:32.640 congruent to x. 01:40:36.420 --> 01:40:48.640 Now, that means if we take the opposite of that, so if we say, okay, 01:40:48.820 --> 01:40:57.060 this is statement A, from A we conclude B, now here we just draw B, 01:40:57.400 --> 01:41:04.760 not B, then implies the contraposition is not B implies not A. 01:41:05.900 --> 01:41:19.780 So, if t square is congruent to 1 modulo x, and this here does not 01:41:19.780 --> 01:41:24.680 hold, that means t is not congruent to 1, and t is not congruent to 01:41:24.680 --> 01:41:29.320 minus 1, then x cannot be prime. 01:41:33.010 --> 01:41:38.210 Okay, so what we would like to compute, so the other thing is that if 01:41:38.210 --> 01:41:45.170 a to the x minus 1 is not congruent to 1 modulo x, then x cannot be 01:41:45.170 --> 01:41:45.470 prime. 01:41:45.470 --> 01:41:50.490 So those two properties, those two contrapositions actually are used 01:41:50.490 --> 01:41:55.810 in this algorithm by Robin and Miller to compute this witness 01:41:55.810 --> 01:41:56.250 function. 01:41:57.230 --> 01:42:01.450 So the idea is to compute a to the x minus 1 modulo x. 01:42:02.130 --> 01:42:05.970 We know this should be 1, if it is not 1, we know x is not prime. 01:42:05.970 --> 01:42:12.350 And on the way to that, we check whether we get values which are 01:42:12.350 --> 01:42:22.150 actually congruent to 1 modulo x, while t is not equal to 1 and t is 01:42:22.150 --> 01:42:31.030 not equal to minus 1 or not equal to x minus 1 modulo x, x is not 01:42:31.030 --> 01:42:32.730 prime, we know that. 01:42:34.090 --> 01:42:41.890 So we compute that value, we start with some value 1, this is our 01:42:41.890 --> 01:42:46.830 value t, you see here we have there we need a value t, this is the 01:42:46.830 --> 01:42:47.750 intermediate value. 01:42:48.590 --> 01:42:56.310 We compute t and d now is the square of t modulo x, so here we have t 01:42:56.310 --> 01:42:59.990 square, which is d, and there we look at t. 01:43:01.550 --> 01:43:10.010 So now we have t and t square, certainly modulo x, and if now d is 1, 01:43:10.790 --> 01:43:20.070 this is this test, if d is 1 and t is not equal to 1 and not equal to 01:43:20.070 --> 01:43:27.490 x minus 1, this is this test, then we know that x is not prime, we 01:43:27.490 --> 01:43:28.530 return true. 01:43:28.530 --> 01:43:31.610 That means we have found a witness for the compositeness of x. 01:43:33.150 --> 01:43:37.270 Otherwise, we have to continue with our computation of a to the x 01:43:37.270 --> 01:43:43.930 minus 1 mod x, and if now ai is 1, you see here we start with k, go 01:43:43.930 --> 01:43:48.270 down to 0, that means we start with the most significant bit, go down 01:43:48.270 --> 01:43:54.790 to the least significant bit of our power x minus 1. 01:43:54.790 --> 01:43:59.730 So ak to a0 is the binary representation of x minus 1. 01:44:00.870 --> 01:44:07.130 And so if ai is 1, you know that we have to multiply our value d, 01:44:07.670 --> 01:44:09.670 which we just have computed, we have squared. 01:44:09.670 --> 01:44:16.410 Now we have to compute it, or we have to multiply with a, and in this 01:44:16.410 --> 01:44:23.530 way that means we multiply with a to the ai modulo x. 01:44:24.630 --> 01:44:25.430 That's it. 01:44:26.050 --> 01:44:28.010 We just repeat this. 01:44:29.270 --> 01:44:32.910 So this is the block here, the inner block of that for statement. 01:44:34.090 --> 01:44:39.050 So this is just repeating this computation, successive squarings and 01:44:39.050 --> 01:44:43.270 multiplications with a, and in this way we compute a to the x minus 1 01:44:43.270 --> 01:44:44.810 modulo x. 01:44:46.790 --> 01:44:55.190 Now if the result d, if we did not jump out of this by returning true, 01:44:55.770 --> 01:44:59.430 then we check whether d is actually 1 or not. 01:44:59.530 --> 01:45:06.290 If it is not equal to 1, then if this is not equal to 1, we know that 01:45:06.290 --> 01:45:11.090 x cannot be prime, we return true. 01:45:11.090 --> 01:45:14.190 If it is equal to 1, we return false. 01:45:15.450 --> 01:45:25.190 Now, the property that a to the x minus 1 mod x is equal to 1 or 01:45:25.190 --> 01:45:29.970 congruent to 1 modulo x does not imply that x is prime. 01:45:31.410 --> 01:45:37.130 We just have found in that case, or it may be that we have some value 01:45:37.130 --> 01:45:40.430 which has this property without being prime. 01:45:41.090 --> 01:45:43.890 But there are some rare numbers having that property and they are 01:45:43.890 --> 01:45:45.010 really rare. 01:45:45.850 --> 01:45:50.330 And we come back to that in the next slide. 01:45:52.110 --> 01:45:59.470 Another interesting experience or interesting result is that, or 01:45:59.470 --> 01:46:06.950 information is that this problem of determining the complexity of the 01:46:06.950 --> 01:46:11.530 primality test, this has been an open problem. 01:46:11.650 --> 01:46:15.070 People did not know whether it is actually a polynomial algorithm or 01:46:15.070 --> 01:46:18.010 whether it is an NP-complete problem. 01:46:19.270 --> 01:46:25.910 And in 2002, so 12 years ago, the first polynomial time algorithm has 01:46:25.910 --> 01:46:26.630 been presented. 01:46:27.350 --> 01:46:33.250 And this was remarkable in particular because this algorithm was 01:46:33.250 --> 01:46:39.910 designed by students like Professor Agarwal at the IIT, the Indian 01:46:39.910 --> 01:46:41.730 Institute of Technology in Kanpur. 01:46:42.230 --> 01:46:45.310 And two of his students at the bachelor level, they just got an 01:46:45.310 --> 01:46:49.190 assignment where they had to solve a nice or small problem with 01:46:49.190 --> 01:46:51.370 respect to number theory. 01:46:51.370 --> 01:46:56.930 And they actually designed a polynomial time algorithm for testing 01:46:56.930 --> 01:46:57.550 primality. 01:46:58.230 --> 01:47:01.510 Remarkable, but things like that happen again and again that people 01:47:01.510 --> 01:47:06.050 who are not aware of all the interesting theories around an open 01:47:06.050 --> 01:47:12.070 problem just have an intuition which leads to a new algorithm. 01:47:13.070 --> 01:47:16.130 So, it is a polynomial time problem. 01:47:17.450 --> 01:47:22.310 Still, it is expensive, but this algorithm here certainly can be 01:47:22.310 --> 01:47:24.210 executed very fast. 01:47:24.910 --> 01:47:30.590 So, to compute this iteration is done very fast. 01:47:30.750 --> 01:47:34.530 We just have to do that r times which we can determine beforehand. 01:47:34.530 --> 01:47:36.850 Now, the question is how do we determine that? 01:47:37.110 --> 01:47:44.870 How often do we have to repeat that choice of a random value a less x 01:47:44.870 --> 01:47:52.530 before we actually can be sure that we have a prime number? 01:47:52.530 --> 01:47:58.190 So, the probability of a false result of witness AX, that means 01:47:58.190 --> 01:48:03.390 witness AX returns false, but the value is not a prime number. 01:48:03.850 --> 01:48:07.790 This probability is smaller than one quarter. 01:48:07.790 --> 01:48:11.850 Now, if we repeat that several times, and since these choices are 01:48:11.850 --> 01:48:15.750 independent of each other, the probability of a false result of the 01:48:15.750 --> 01:48:21.430 Rabin -Miller test, since we repeat that r times, is one over two to 01:48:21.430 --> 01:48:22.210 the two r. 01:48:22.990 --> 01:48:28.990 Now, this easily gets down to a very, very small probability. 01:48:29.870 --> 01:48:36.410 And so, even with a few repetitions, you have a very high probability 01:48:36.410 --> 01:48:45.290 than the result that x is actually a prime number. 01:48:45.290 --> 01:48:51.310 So, it is a suitable, fast, and sufficiently secure method for 01:48:51.310 --> 01:48:53.630 generating prime numbers. 01:48:54.270 --> 01:48:59.870 So, as I said, you select a random number with appropriate number of 01:48:59.870 --> 01:49:09.270 bits that you are interested in, and then you repeat that test until 01:49:09.270 --> 01:49:13.830 you finally have found a number which is, according to that test, a 01:49:13.830 --> 01:49:14.430 prime number. 01:49:15.830 --> 01:49:21.330 Another question is, we now know how to determine a prime number, so 01:49:21.330 --> 01:49:26.750 we can compute p times q, and now we have to find c and d. 01:49:27.790 --> 01:49:29.170 So, how do you find those? 01:49:29.170 --> 01:49:31.570 So, to find c is not that difficult. 01:49:32.270 --> 01:49:38.470 You just take c prime with respect to p minus one times q minus one. 01:49:38.470 --> 01:49:42.570 You just take some prime value. 01:49:42.790 --> 01:49:48.530 You can actually choose a not-too-large integer, because this is for 01:49:48.530 --> 01:49:56.270 coding, for encryption, and so this should be a small number. 01:49:56.390 --> 01:50:00.750 Not too small, but you have a choice of just taking any number there, 01:50:01.910 --> 01:50:04.130 any prime number less than n. 01:50:04.130 --> 01:50:08.670 Another question is, how do you actually get d with this property that 01:50:08.670 --> 01:50:13.590 c times d is congruent to one modulo the Euler value of the product p 01:50:13.590 --> 01:50:14.090 times q. 01:50:15.750 --> 01:50:21.770 So, the answer is that you use the extended Euclidean algorithm. 01:50:21.770 --> 01:50:25.390 Now, you know the Euclidean algorithm, which is the algorithm, the 01:50:25.390 --> 01:50:33.330 simple algorithm for determining the largest common divisor of two 01:50:33.330 --> 01:50:33.890 values. 01:50:34.770 --> 01:50:42.870 So, you test whether the greatest common divisor of c and p minus one 01:50:42.870 --> 01:50:44.490 q minus one is one. 01:50:44.490 --> 01:50:53.910 This is the Euclidean algorithm to test whether two values, x and y, 01:50:54.450 --> 01:50:59.170 have only a trivial largest common divisor. 01:51:00.930 --> 01:51:04.910 The interesting point is that we use an extended version of that. 01:51:05.070 --> 01:51:13.130 So, in the simple version, you just get this answer, well, they are 01:51:13.130 --> 01:51:15.150 prime with respect to each other or not. 01:51:16.510 --> 01:51:19.290 But in the extended version, you actually get more. 01:51:19.290 --> 01:51:24.830 So, in the extended Euclidean algorithm, what you compute is for 01:51:24.830 --> 01:51:30.850 integers c and e, which you are interested in, so here c and e, you 01:51:30.850 --> 01:51:38.050 compute integers x, y, and r, where r is that value. 01:51:38.050 --> 01:51:44.770 So, you compute those integers x, y, and r such that e times x plus c 01:51:44.770 --> 01:51:52.050 times y is equal to r, the greatest common divisor. 01:51:52.050 --> 01:51:59.370 So, this actually gives you the desired result. 01:51:59.530 --> 01:52:09.330 If r is one, you have that e times x plus c times y is equal to one. 01:52:09.330 --> 01:52:14.730 Now, for our problem, it means we take, like c is our prime number, 01:52:14.850 --> 01:52:21.070 which we have chosen for the public key, and now e is just this Euler 01:52:21.070 --> 01:52:22.770 value of n. 01:52:23.630 --> 01:52:30.890 Now, if we have, so the problem is we find, we look for some d such 01:52:30.890 --> 01:52:37.390 that c times d is congruent to one modulo e, or we can rephrase that 01:52:37.390 --> 01:52:45.210 and say that we look for some value of, we are interested, we look for 01:52:45.210 --> 01:52:54.970 some x such that cd minus one is a multiple of e. 01:52:55.950 --> 01:53:03.270 That's what we said is like x is congruent to y modulo z if that 01:53:03.270 --> 01:53:05.690 difference is a multiple of z. 01:53:05.690 --> 01:53:13.310 And here we have c and d and one, the difference is a multiple of the 01:53:13.310 --> 01:53:22.010 modulus e, or you could say e times minus x plus c times d is equal to 01:53:22.010 --> 01:53:22.270 one. 01:53:23.070 --> 01:53:26.890 Now this is exactly what we stated there with respect to e times x 01:53:26.890 --> 01:53:29.530 plus c times y equals to r. 01:53:30.330 --> 01:53:37.990 Okay, so if we have, if this extended Euclidean algorithm delivers us 01:53:37.990 --> 01:53:45.190 x and y, then we have exactly what we are, what we need, we have then 01:53:45.190 --> 01:53:47.670 found such a value d. 01:53:49.390 --> 01:53:59.110 Okay, and so this d is then, as I said, the d is then this value of x 01:53:59.110 --> 01:54:03.690 that we, no, sorry, this value of y that we are interested in. 01:54:04.310 --> 01:54:07.610 Y is what we look for, that will be our d. 01:54:09.050 --> 01:54:11.950 Okay, now what is this method doing? 01:54:12.250 --> 01:54:13.650 It is an iterative algorithm. 01:54:13.770 --> 01:54:16.690 As you know, the Euclidean algorithm is a simple iterative method. 01:54:17.440 --> 01:54:24.750 And so we have that schema, which is indicated here. 01:54:24.830 --> 01:54:26.270 We start with e and c. 01:54:26.890 --> 01:54:32.110 We have some intermediate values x0, x1, y0, y1. 01:54:32.730 --> 01:54:41.590 And we have some quotient qi, which is the integer, use integer 01:54:41.590 --> 01:54:51.590 division, ai minus 1 over ai, ai minus 1 over ai, a0, a1 are e and c. 01:54:51.590 --> 01:55:00.450 So we compute e over c, we divide e by c, and then take the integer 01:55:00.450 --> 01:55:01.210 value. 01:55:02.370 --> 01:55:14.890 Then we also look like here, ai minus 2, no, sorry, ai, then is ai 01:55:14.890 --> 01:55:20.030 minus 2 minus ai minus 1 times qi minus 1. 01:55:20.910 --> 01:55:31.030 And so a2 in this case would be a0, e minus ai minus 1 times qi minus 01:55:31.030 --> 01:55:40.650 1, in this case would be just the remainder of that value qi, which is 01:55:40.650 --> 01:55:45.670 the integer quotient of e over c in the initial round. 01:55:45.670 --> 01:55:49.970 And then we continue that, we just compute the appropriate, here some 01:55:49.970 --> 01:55:57.510 appropriate differences, continue that and iterate until the smallest, 01:55:58.270 --> 01:56:03.130 or until this ak actually is 0, you remember that from the Euclidean 01:56:03.130 --> 01:56:03.430 method. 01:56:04.250 --> 01:56:13.150 And then we know that the previous value of that a sequence, or ak 01:56:13.150 --> 01:56:19.090 minus 1, is the greatest common divisor, which certainly should be 1 01:56:19.090 --> 01:56:19.870 in this case. 01:56:19.870 --> 01:56:29.090 And we also have for all intermediate values that e times xi plus c 01:56:29.090 --> 01:56:39.630 times yi is ai, and so the yi minus 1 will have been the value d that 01:56:39.630 --> 01:56:41.410 we are interested in. 01:56:42.310 --> 01:56:53.490 And so then if the greatest common divisor of c and e is 1, then y is 01:56:53.490 --> 01:56:59.330 the multiplicative inverse of c and modulo e, this is the y in this 01:56:59.330 --> 01:57:00.090 statement here. 01:57:01.070 --> 01:57:05.550 c times y is congruent to 1 modulo e, that's what we wanted to get. 01:57:05.550 --> 01:57:10.770 So this is the simple extended Euclidean algorithm, so you see that c 01:57:10.770 --> 01:57:19.270 and d are easily computed as soon as we have computed n, which was 01:57:19.270 --> 01:57:24.830 based on the determination of two large prime numbers p and q. 01:57:25.650 --> 01:57:31.470 Nevertheless, when I say this is easily computed, we still have all 01:57:31.470 --> 01:57:39.710 the operations here are operations on large integers, so they are 01:57:39.710 --> 01:57:40.330 expensive. 01:57:42.730 --> 01:57:49.930 So y is the required value of d, as I said, and if we apply the RSA 01:57:49.930 --> 01:57:55.430 algorithm, certainly we can use it for encryption of messages. 01:57:55.430 --> 01:58:01.690 Certainly the asymmetry avoids the problem of secure key exchange. 01:58:03.030 --> 01:58:12.370 We don't need n squared, like if we have our n partners who would like 01:58:12.370 --> 01:58:17.690 to communicate, for every communication that we have here, we don't 01:58:17.690 --> 01:58:29.070 need to construct keys for every line in that complete graph here. 01:58:29.070 --> 01:58:37.390 These n square keys, but here every person only needs a public key and 01:58:37.390 --> 01:58:40.850 everybody can use the public key to send an encrypted message which 01:58:40.850 --> 01:58:43.070 only the recipient can decrypt. 01:58:43.790 --> 01:58:48.010 And so here we only need n public-private key pairs. 01:58:49.390 --> 01:58:57.210 So this is much better and the disadvantage certainly is that the cost 01:58:57.210 --> 01:59:02.330 for encryption and decryption is quite significant and so we have to 01:59:02.330 --> 01:59:03.010 consider that. 01:59:03.870 --> 01:59:08.410 Another problem is that it is easily broken if you only have few 01:59:08.410 --> 01:59:10.070 possible plain text messages. 01:59:10.070 --> 01:59:11.930 Why is this the case? 01:59:12.570 --> 01:59:22.630 Assume you have somebody who is taking care of a certain, like has a 01:59:22.630 --> 01:59:28.430 certain number of values in a bag and he wants to draw a certain value 01:59:28.430 --> 01:59:35.190 and then send the result to his friend and this friend would like to 01:59:35.190 --> 01:59:39.210 know and somebody else, you know, Alice, Bob and Eve. 01:59:39.210 --> 01:59:44.290 Now Eve would like to know what the selection actually is. 01:59:45.530 --> 01:59:54.190 Now she might know that in this box there are values, let's say A1, A2 01:59:54.190 --> 01:59:55.750 and so on up to AK. 01:59:56.330 --> 01:59:57.670 K different values. 01:59:57.670 --> 02:00:03.390 Now if these are K different values, potential names of participants, 02:00:03.530 --> 02:00:08.770 for example, in some draw or whatever you would like to do, maybe you 02:00:08.770 --> 02:00:12.950 would have to decide for buying certain assets on a stock market or 02:00:12.950 --> 02:00:17.630 you can easily imagine other situations where you have only a limited 02:00:17.630 --> 02:00:24.290 number of plain text messages which are known to Eve but she doesn't 02:00:24.290 --> 02:00:27.010 know which one of those actually is selected. 02:00:27.010 --> 02:00:32.370 Now what she can easily do is she can just, like Eve can do the 02:00:32.370 --> 02:00:40.810 following, she just takes the public key of Alice, no of Bob and like 02:00:40.810 --> 02:00:47.850 assuming that A will use this algorithm, like use Bob's public key to 02:00:47.850 --> 02:00:49.450 send the result of her draw. 02:00:49.930 --> 02:01:01.230 Eve just computes, uses Bob's public key, computes PB of A1 down to PB 02:01:01.230 --> 02:01:03.450 of AK. 02:01:05.970 --> 02:01:15.170 And then since Alice will send the encrypted value of AI which she has 02:01:15.170 --> 02:01:21.670 chosen, Eve only has to look at the encrypted values which can easily 02:01:21.670 --> 02:01:25.890 determine which one of those has been selected because she does not 02:01:25.890 --> 02:01:28.050 have to decrypt. 02:01:28.050 --> 02:01:33.410 She only has to know which message actually has been sent and since 02:01:33.410 --> 02:01:38.510 this is a limited number of messages that can be sent, she can easily 02:01:38.510 --> 02:01:42.110 find out what the information is that has been transmitted. 02:01:42.450 --> 02:01:48.230 So this is an important insight that you have to be very careful how 02:01:48.230 --> 02:01:53.190 you apply such a public key method because you have this public key 02:01:53.190 --> 02:01:54.610 which is used for encryption. 02:01:55.810 --> 02:01:57.770 So we have to do something about that. 02:01:58.570 --> 02:02:02.770 Whenever you have a limited number of potential alternatives which 02:02:02.770 --> 02:02:07.770 have to be encrypted, you can easily circumvent the problem of having 02:02:07.770 --> 02:02:09.650 to decrypt the message.