Welcome to week 2 lecture 1. We start from product ciphers. Idea of forming products of crypto systems is due to Shannon. Now, we know that a crypto system can be specified by P C K E and D. where P is the set of plain text, C is the set of cipher texts, K is the set of keys, E is the set of encryption functions and D is the set of decryption functions.
Now, we consider For simplicity, the situations where P is equal to C and we consider a cipher crypto system S 1 which is denoted by P, P then K 1 the set of keys for S 1, E 1 and D 1. We consider another cryptosystem S2, which has the same plaintext and ciphertext sets and these sets are equal, then we have K2, then E2 and D2. According to Shannon, The product of these two cryptosystems S 1 and S 2 is written as S 1 cross S 2 and we have a cryptosystem. P P K 1 cross K 2 by this K 1 cross K 2 we mean the Cartesian product of the set K 1 and K 2 that means that it is a set of all ordered pairs of keys first one coming from the key set of the first crypto system and the second one coming from the key set of the second crypto system and then we have E and D which we will have to define. So, we see that. S 1 cross S 2 which is a product of S 1 and S 2 that is P P and then K 1 cross K 2 then E and D.
Now, the question is that how we define E and D which is given in the next slide. This one, so encryption and decryption of product cipher, so we have to know how to define E and D. In the case of individual ciphers S 1 and S 2, the encryption functions were like this E k 1 belonging to E 1 and E k 2 belonging to E 1. e 2 whereas, the corresponding decryption function d k 1 belongs to d 1 and d k 2 belongs to d 2. Now, we have a combined encryption function for the product cipher, we call the ordered pair of the keys as k.
So, that is k 1 comma k 2 and the encryption function is labeled by k which is the ordered pair k 1 k 2 and it operates over x. The plaintext P, plaintext in P, so it is x and then we have a sequence of functions the first one coming from e 1 that is e k 1 applied over x and then e k 2 applied over e k 1 x. So, this is the result of the operation of E k 1 k 2 over x in the product cipher S 1 cross S 2. Now, the question is that what is the decryption function?
The decryption function D again k 1 k 2 applied over y will be equal to d k 1 applied over d k 2 y, where y is an element of c that is the cipher text and in this case c and p are same. Now, we know that if we apply encryption function over a plain text and we apply the decryption function with the same key over the cipher text generated from that plain text then we should get the plain text back. Now, we have to check whether that property holds for this new definition.
So, let us see suppose I take D. K 1 K 2 applied over E K 1 K 2 x. Then by using this rule I can write D K 1 K 2 applied over E K 2. of E k 1 x. Now, we use the second rule, now the argument of the decryption function is sequence of encryption functions. Therefore, we will write D of k 1 applied over D of k 2 applied over E k 2 E k 1 x, I close a bracket, I close the other bracket, I close the last bracket.
Now, look at this one, since S 2 is a cipher system or a crypto system, we know that d k 2 e k 2 x is equal to x for all x in P. Therefore, when d k 2 is applied over e k 2, I know that I will get this argument back and therefore, I will get d k 1. applied over E k 1 x and then since S 1 is a cipher system I know that B k 1 E k 1 x x and therefore, I will get x. Thus we have this result that d k 1 k 2 e k 1 k 2 x gives me x for all k 1 k 2 and all x and therefore, we see that we indeed have a crypto system. Now, an example of a product cipher. is a combination of multiplicative cipher and a shift cipher.
And we will see that if we take a multiplicative cipher and product it with a shift cipher. then we get our affine cipher. Now, let us look at this a multiplicative cipher is something easier than affine cipher, we have got p and c both equal to Z sub 26 and the set of keys is all numbers co prime to 26 as I have written over here and the encryption function is just multiplication modulo.
26 with a chosen key in this case it is a and decryption is done by taking a inverse and multiplying to the cipher text modulo 26. So, this is a multiplicative cipher and now We know that we have the usual shift cipher and let M be the multiplicative cipher that we have seen just now and usual shift cipher is just to add the key modulo 26 to the plain text between 0 to 25. If we take the product S cross M, then we will get a fine cipher. I will quickly show this result and I will ask you to check this in more details after the class. So, we take the multiplicative cipher M.
P and C both are Z sub 26 and the key let us call it K m which is equal to all a belonging to Z sub 26 such that G c d of a and 26 is equal to 1. Now For the shift cipher P is equal to C is equal to z 26 and K s which is the shift cipher the key set that is equal to K an element of z 26 any element of z 26. So, if I am taking S cross M. Then, according to the definition P will be Z 26, C will be Z 26 that is all right and the keys will be K. m k s k s cross k m and then I will have the encryption function and decryption function.
So, now, let us see the encryption function. So, the encryption function of m that is E a of x is equal to a x mod 26. Now, the encryption function of let us superscript it with m to indicate that this is the encryption function of the multiplicative cipher, then for the shift cipher the encryption function e s on x is going to give me x plus k. with the key k is going to give me x plus k mod 26. And now if I apply E a m on E k s like this over x, I will get E k s.
and here I will get A x mod 26 and this is going to be A x plus k mod 26. And this is exactly the encryption function of the shift cipher, the encryption function of the affine cipher with the affine cipher. So, it is the encryption function of that. Now, only thing that we will see is that here the key set is turned in a way turn the other way round in the case of affine cipher we write the key space as this a comma b z 26 by z 26 where a 26 g c d is equal to 1. which is equal to K m cross K s, but in this case I have got this K s cross K m, but that is not going to be a big problem because they are essentially the same set. Now, there is a question. Are these two sets S cross M, M cross S, I am sorry are these two crypto systems same?
Now this question I leave as an exercise. please try to prove it whether these two crypto systems are same and the answer is yes they are same, but it needs a proof. Now we move on to block ciphers, the idea of block cipher is based on product ciphers and on something more specifically a iterated product cipher.
So, we have a particular cipher which we keep on. applying over a plain text iteratively several times and in the process get something which is called a block cipher. It is called a block cipher because it is applied over a block of plain text or a block itself is called the plain text.
In more particularly, we will be taking a 64 bit segment. and call it a block and we will apply our transformation of the crypto system on that 64 bit block or it may be a 32 bit block or something like that, but it will be a block. And we will essentially apply a simple transformation over and over again and then that will result in security. Now, there are some terms which are used in the context of block ciphers very frequently.
So, each iteration is called a round, each round involves one round function and a round key which is obtained from a key schedule specified to the cipher. Now, it is like this that we will have a. key, a kind of master key which is in the key space and from this key we will generate a key schedule of this type. may be some k and I have to see what we have written in the slides. But, so it is called some kind of sub key or round key or something like that and we will have a round right now I am writing it as a box.
So, we will have a input let us say x and It is a first round, so first sub key or first round key will go here, we will somehow combine these two things. So, I will have a function g x k 1, a function g which combines x and k 1 and gives me something let us call it w 1. Then this w 1 will be passed to the next round. it is an iterative cipher.
So, usually it is a same function. So, applied over w 1, with the round 2 key. So, it is W 2 it will again pass on to the next round and so on. Ultimately, it will come to the last round and it will give me the final enciphered, final enciphered segment. Now, this whole thing can be written by using some standard symbols.
Now, the rounds we will be denoting by n r. So, n r is a number of rounds and as I have said the key is k and these are the round keys. Then as I have explained g is the round function and here I put a particular symbol Instead of x I will write w to the power 0, which is the input to the first round, then w to the power 1 that is the input to the second round and so on.
So, this is what I have written over here, which I have explained already on the blackboard. Now, what about the rth round, what is happening in the rth round? In the rth round, In the first round what is going in?
w 0 is going in, in the second round w 1 is going in. So, if I am considering the r th round, then w r minus 1 is going in. In the first round what is the key?
It is k 1, in the second round it is k 2. So, in the rth round the key is k r. So, the round function g is going to process w r minus 1 comma k r and it will produce w r. and that is what I have written here. So, this is the input to the next round, we will keep on doing this for n r rounds and eventually we will arrive at the final ciphertext. These steps are formally represented in this slide over here that is x first w 0, then how w 1 is constructed, how w 2 is constructed so on and ultimately how W n r which is the ciphertext is constructed.
Now, this n r has to be decided by the designer that how many rounds we are going to apply the function g successively over a plaintext and with a sequence of round keys that has to be done by the designer. For decryption We have to take care of one point when we are defining the round function which is this one that the round function g should be such that g inverse g of w y comma y has to give me w, suppose y is the key. So, if y is the key, suppose I have computed the image of w with y and suppose I want to compute back w, I can do that by applying g inverse over this thing and I will get w. So, this is a very important condition that a round function has to obey in order that a block cipher is practically useful or meaningful. So, if you look at this.
sequence of steps you will see that this is how we decrypt. We had W n r and we apply this property over and over again and from that we will have W n r minus 1 and then the next step. we will have w n r minus 2 and eventually we will have w 0 which is equal to not y, but it is x.
So, here is a correction in the slide in the last line w 0 goes to x and not w 0 goes to y please note that. I will update the slide when we upload all the slides. Coming to block ciphers in general, when block ciphers are used for cryptography, then they are used according to certain modes of operations.
We will discuss four important modes of operations right now. The first one is called electronic code book mode or in short ECB mode. This is the first one. This is the easiest possible mode where the plaintexts are segmented into blocks and these blocks are x 1, x 2 and so on.
So, we have x 1, x 2 and so on and we choose a key which is fixed and each time I am using the encryption function with the same key, let us say this time on x 1. So, I am getting y 1, this time on x 2. So, I am getting y 2 and so on, this is called the ECB mode. Next we have the cipher feedback mode. In short, C F B mode, we introduce something called We introduce something called an initialization vector in short I 0 and say y 0 is equal to that initialization vector called I v and we say that y 0 is equal to I v and we compute z, z i which is e k. y i minus 1 where i starts from 1 and increases. So, if i equal to 0 we get let us say not i equal to 0, but if i equal to 1. Then we get z 1 is equal to a k y 0, y 0 is a public vector which is the i v initialization vector.
So, I get this and then z 2 for i equal to 2, z 2 is e k of y 1. And, I have to calculate y 1 once I know z 1. So, y 1 is x 1 plus z 1. So, here from e 0 I will know z 1. Once I know z 1, I sum that is I take the x or bitwise x or. with x 1 and z 1 and I get y 1 once I know y 1 I will get z 2 and so on I will keep on encrypting. So, this is the ciphertext feedback mode and two last modes are like this, this cipher block chaining mode, where I start with a initialization vector and then add that initialization vector bit wise modulo 2 to the message and then apply the encryption and construct y i again this y i will be pushed into this and so on.
And output feedback mode is where we start from initialization vector and then keep on generating this Z sub i's by applying successively over the results and then add the Z i's to X i's and generate Y i. So, these are the four important modes of operations of block ciphers. So, summing up we started with product ciphers in this lecture, after that we studied the general principles and designs of block ciphers and then at the end we have talked about the modes of operations of block ciphers. This is all for this lecture, we will study block ciphers in more details in the subsequent lectures.
Thank you.