|| Author: Cyerdude || Back to articles ||

#####-> [0x0] Introdution to DES algorithm, a simplification of Des: S-DES ####--> [0x1] Flux ciphrature and block ciphrature ###---> [0x2] Feistel's block ciphrature ##----> [0x3] DES - Data Encryption Standard #-----> [0x4] Block's ciphrature working terms Author: Ferraro Giuseppe aka Cyberdude Mailto: viromarquantebello[at]libero[dot]it ---------------------------[0x0 - Introdution to DES algorithm, a simplification of Des: S-DES ] Des is the initial of Data Encryption Standard and is the most important block ciphrature algorithm existend. The simplification of Des algorithm was born in santa clara universit from prof. Edward Schaefer In this text we named the simplification of Des algorithm as S-DES. To describe this algorithm we use an exemple and an image so the concept is more clear. [key of 10 bit] | V [8 bit of original message] [P10] [8 bit of original message] | | ^ V V | [IP] [SW] [IP^-1] | |---- ^ V V | | [fk]<-----------------------[P8]---|------------------------->[fk] | | ^ V | | [SW] [SW]<-- [SW] | | ^ V V | [fk]<-----------------------[P8]----------------------------->[fk] | ^ V | [IP^-1] [IP] | ^ V | [8 bit ciphred text] [8 bit ciphred text] we give in input to the algorithm the original message, the algorithm take 8 bit of original message and want a key of 10 bit. The position of 8 bit of original message is changed during the IP phase and the output of the changing of position of bit of original text go in input to another function named fk. The 10 bit of key are shiftated by SW function and 8 of this 10 bit go in P8 function where their order is changed (P= permutation). The output of this changing was send in input to fk function that with the 8 permutated bit of originale message and the 8 bit of a new key generated from the 10 bit sfiftated return another configuration of bit that is sended in input to another shift function named SW that change another time the order of 8 bit. When the 10 bit of the key are shifted and sended in input to P8 the was sended to another SW function too. This Sw function change the position of the 8 bit of the subkey and in this way can create another key permuting the order of the bit using another P8 method.The output of this is sended in input to the second fk method that with the 8 bit returned from prev Shift function return another configuration of 8 bit. This 8 bit final configuration is given in input to the IP^-1 function that is the inverse commutation of the initial permutation IP. The result of this procedure are 8 bit of ciphred text. If we want reobtain the original text we do the inverse procedure, we take 8 bit of ciphred text in input and the algorithm make an IP procedure on this bit, after this permutated bit was sended in input to fk method that contain the second subkey generated from the original key of 10 bit. The output of fk procedure is shifatated by SW method and go in input to the second fk procedure of the decodification process that take in input the first subkey of 8 bit generated by the 10 bit original key. The output of fk is given in input to the IP^-1 procedure that permute the final block of bit in the way opposite to the IP permutation procedure.The result of it is the original message that we have ciphred in the first time. We can rapresents the procedure now presentated in this way: => ciphred text = IP^-1(fk2(SW(fk1(IP(original message))))) => originale text = IP^-1(fk1(SW(fk2(IP(ciphred text))))) where fk2 and fk1 are the second and the first subkey generated from the original 10 bit key: => k1 = P8(shift(P10(key))) => k2 = P8(shift(Shift(P10(key)))) The next image explain the key1 and key2 creation from 10bit of original key procedure: [key of 10 bit] | V [ P10 ] | | V V [LS-1][LS-1] | | ----5 5---- | | | | | V V | | [ P8 ] | | | | | ------|--------> [K1] | | V V [LS-2] [LS-2] | | --- --- | | V V [ P8 ] | --------------> [K2] When we insert the key of 10 bit in input, the 10 bit are permutated in P10 procedure as I show here in this exemple position of 10 bit =>> |k1|k2|k3|k4|k5|k6|k7|k8|k9|k10| |--|--|--|--|--|--|--|--|--|---| key of 10 bit =>> | 1| 0| 1| 0| 0| 0| 0| 0| 1| 0 | permutation of position =>> |k3|k5|k2|k7|k4|k10|k1|k9|k8|k6| |--|--|--|--|--|---|--|--|--|--| key of 10 bit permutated =>> | 1| 0| 0| 0| 0| 0| 1| 1| 0| 0| After that the key of 10 bit : 1010000010 is permutated in 1000001100 the new bit sequence is divided in two subsequence of 5 bit 10000 and 01100. Boot the subsequence are shiftated of a one bit in the left direction in the LS-1 procedures. Now 10000 became 00001 and 01100 became 11000! Now we have a the key of 10 bit permutated and shiftated 5to5 bit : 0000111000! This bit configuration is sended in P8 procedure and divided in two block of 5 bit in LS-2 procedure. The P8 procedure take the 10 bit 0000111000 and permute 8 of this bit to create the first subkey: k1 the permutation procedure is definited as showed here: key : 0 0 0 0 1 1 1 0 0 0 k1 k2 k3 k4 k5 k6 k7 k8 k9 k10 permutation procedure: k6 k3 k7 k4 k8 k5 k10 k9 results: 1 0 1 0 0 1 0 0 the bit k1 and k2 are not considerated becouse we necessity to creat a subkey of 8 bit and not of 10 bit. To the end of this procedure we have created k1 = 10100100 But if you remember we have sended the 10 bit permutated and shiftated and divided in two part to the two procedure named LS-2, this procedures shidted the courrent bit of 2 position in the left direction. So: 10 bit 00001 11000 LS-2 of 00001 = 00100 LS-2 of 11000 = 00011 The result of the two procedure LS-2 is a new configuration of 10 bit(in our case is 0010000011) this bits was sended in input to another P8 procedure that is the same of the prev P8 procedure and creat another subkey of 8 bit: from 0010000011 we obtain the key k2 = 01000011 The next image rapresent the execution of IP-fk-SW-fk-IP^-1 procedure of 8 bit of original message to generate the 8 bit of ciphrate text [8 bit of original message] | V /4----[ IP ]-----/4 | | | [E/P]<-----| | | | | /8 | | | | | V | | (+)<------|----------/8----k1 | | | | | -/4- -/4- | | | | | | V V | | [S0] [S1] | | | | | | -/2- -/2- | | | | | | V V | | [ P4 ] | | | | | /4 | | | | | V | ------>(+) | | | /4 /4 | | V V [ S W ] | | /4--------- /4- | | | [E/P]<-----| | | | | /8 | | | | | V | | (+)<------|----------/8----k2 | | | | | -/4- -/4- | | | | | | V V | | [S0] [S1] | | | | | | -/2- -/2- | | | | | | V V | | [ P4 ] | | | | | /4 | | | | | V | ------>(+) | | | /4 /4 | | V V [ IP^-1 ] | V [8 bit ciphred text] We can see an exemple to understend this procedure. Imagine that the original message is the bit configuration : 11110011 in the first time this 8 bits are gived in input to the IP procedure where they are permutated in this way : k2 k6 k3 k1 k4 k8 k5 k7 So the output of IP proceure is a new configuration of the initial 8bit gived in input. The new configuration is this : 10111101. After that this 8 bits are divided in two block of 4 bits. The left block 1011 and the right block 1101. The right block (1101) is sended in E/P procedure where the 4 bit are expansed in this way: k4 k1 k2 k3 k2 k3 k4 k1 so the 4 bit 1101 becames this 11101011 so now we have 8 bit that go in input to another procedure : (+) this is a XOR procedure that execute the xor between the 8 bit output of E/P procedure and the 8 bit of the first subkey created by 10bit permutation and shifting procedure. If you remember in the first time we have obtenuted the first key k1 = 10100100, the xor with 11101011 is this: 01001111. Now this bit configuration 01001111 is divided in two part the left block 0100 and the right block 1111. The left block is gived in input to S0 procedure, the right to S1 procedure. S0 and S1 are two 4x4 matrix configurated in this way: 1 0 3 2 0 1 2 3 S0 = 3 2 1 0 S1 = 2 0 1 3 0 2 1 3 3 0 1 0 3 1 3 2 2 1 0 3 when arrive the left block of bit 0100 the algorithm use the bit in position 0 and in position 3 in this case 00 to generate a decimal value that in this case is 0. The bit in position 1 and 2 are used to generate another decimal value,since the bit in position 1 and 2 are 10 the decimal value is 2. The algorithm take the element in S0 that is in row 0 and column 2 that is the value 3.This value (3) is converted in binary value that is: 11. In this way from 4 left bit we obtain an output of 2 bit. The same procedure is execute for the 4 right bit on S1. So: 4 right bit => 1111 bit in position 0 and 4 = 11 => decimal value = 2 bit in position 1 and 2 = 11 => decimal value = 2 value stored in S1 to row 2 and column 2 => 3 binary value of decimal 3 is => 11 the result of S0 and S1 are 11 and 11 so we have obtenute a new configuration of 4 bit: 1111 this block of bit is gived in input to an P4 procedure that do a permutation of this bit in this way: P4 = bit2 bit4 bit4 bit1! in our case the configuration remain the same becouse the initial value of bit is 1111 so we can permute it in a single mode : 1111. this block of bit is gived in input to a xor procedure. If you remember in the first time we give the 8 bit of original message in IP and the output of it are 2 block of 4 bit.The left of 4 bit go in input to this xor procedure with the 4 bit now generated so we have: 4 left bit returned from IP procedure = 1011 4 bit output of S0 and S1 procedure = 1111 XOR result : 0100 This output of 4 bit is gived in input to the shift procedure. The shift procedure take in input 8 bit so the other 4 bit to create a 8 bit configuration message are the 4 right bit output of the initial permutation procedure namend IP.The result of this shift is a new configuration of 8 bits. This 8 bits are divided in two part of 4 bits. At this point the algoritm repeat the same operations illustated first but the second input of a key of 8 bits of the first Xor operation is the k2 bit configuration and not the k1 configuration key. In the first time we have named the block of operation: E/P + XOR + S0 + S1 + P4 + XOR as fk. If you resee the initial image and the last image descript you can unknow the structure of this algorithm ---------------------------------------------------[0x1 - Flux ciphrature and block ciphrature ] Is there only a little but important difference between a flux ciphrature and a block ciphrature The flux ciphrature consider one to one all the bits of original text to obtain a crypthed text.The flux ciphrature is different becouse consider a block of a particoular number of bit decided in the first time. For exemple if we have a message of 32 bit we can use a ciphrature that consider 4 bit to 4 bit. If our message is this : 01011100101010101000101010101010 we have this division in blocks of 4 bit: block[1] 0101 block[1] 1100 block[1] 1010 block[1] 1010 block[1] 1000 block[1] 1010 block[1] 1010 block[1] 1010 but this is only an example. The idea is that we must assign a block of "ciphrate" bit of the same number of the original. But this block of bit that we assign to the orinal configuration of bit must be reversible so must be like no one other bit configuration. To understend it we can have this exemple: imagine that we decide to use a block of 2 bit to ciphre our message, a reversible configuration can be it original case that we can have with 2 bits ciphred configuration decided for it 00 11 01 10 10 00 11 01 So when in our message we read 2 bits to 2 bits if we have 01 we change it in 10 and to decript change 10 in 01 to reobtain the original message. But if we use a irreversible table as this: original | ciphred ciphred | original ------------------ ------------------- 00 | 11 11 | 00 01 | 10 10 | 01 10 | 01 01 | 10 11 | 01 01 | 11 when I have a final ciphred message and I want obtain the original and I have the two bit of ciphred text equals to 01 I don' t know what is the 2 bits block that I must consider to decript it becouse I have two possible configurations: 10 and 11 (original bit) are boot equals to ciphred value 01 so this type of table is irreversible and I cannot use it to ciphre my message if I want reobtain the original message in the second time. Now reconsider the reversible table that we have considerated in the first time original | ciphred ciphred | original ------------------ ----------------- 00 | 11 00 | 10 01 | 10 01 | 11 10 | 00 10 | 01 11 | 01 11 | 00 our key to ciphrate a message using this 2to2bits block table is composit of all "little key" of change. In this case our key is this : 11 10 00 01 so for 2to2bits block we have a key of 2*2^2, in generale we have a key of n*2^n bits where n is the number of the bit that rapresents a single block. But if I want obtain a good ciphrature I must use a very big number of bits that composit one single block and If i use a big number of bits I must use a key that is most big. -------------------------------------------------------------[0x2 - Feistel's block ciphrature ] Now that we know the difference between the flux ciphrature and the block ciphrature we can see one of the most important and used struture of block ciphrature, the ciphrature of Feistel. This algorithm is created to render very difficult the decriptation of an encrypted message by an unautorized person. The Feistel's structure give in input an original message and a key.The next image show how work this algorithm. [original text] | V | L0<------- ------->R0 | | --------|---------------k1 | | | | | Phase 1 V V | | (+)<-----[F]------- | | | | \______ ______/ | \ / ----------------------------------- _______/ \_______ | | | | ... ... | | | | V V | L1<------- ------->R1 | | --------|---------------ki | | | | | Phase i V V | | (+)<-----[F]------- | | | | \______ ______/ | \ /------------------------------------ _______/ \_______ | | | | ... ... | | | | V V | Li<------- ------->Ri | | --------|---------------kn | | | | | Phase n V V | | (+)<-----[F]------- | | | | \______ ______/ | \ /------------------------------------ _______/ \_______ | Ln | |Rn | Last change \______ ______/ | \ /------------------------------------ _______/ \_______ | | V V Ln+1 Rn+1 \____ ____/ | V [Ciphred text] When arrive the original message in input, the number of its bits is divided in two se we have L0 and R0 that are the first n/2bit (Left) and the other n/2bit ( Right). We can divide this algorithm in several phase that work all in the same way but with the different input. The type of input of the everyone phase is the same but change the value.In the image I have rapresentate only three phase the initial phase (phase1) the intermedie phase (the phase in the middle, phase i) and the final phase (phase n). The final phase is n becouse n is a number that we decide and is the number that we want repeat the phase operations. After that we can describe how work this algorithm. When in the first time the message is divided in two part, the right part is gived in input to a function with the key. The output of this function is sended in input to a xor operation with the left block of bits. So we have that the only single phase do it: {[(right block + key) -> F] + left block} -> XOR = [ new bit configurazion ] |||_________________| | | || input of F | | ||________________________| | | result of F (new bit configuration)| |_______________________________________| input of XOR The output of this (the new bit configuration) is seed from the algorithm as a new configuration of a left block of initial message, the right original bits block is remembered by the algorithm and after that the two block are exchanged. So the new left block became the new right block and the original right block becamo the new left block. After that started the phase 2 where we have the same operations but with different input, the key is changed too. To the end, when we have repetuted this operations n times, we excange the the blocks another time and the final bit configuration (the union of the two block) rapresents the cyphrate message. To obtain a perfect criptography we can implements in this way this algorithm: [Number of bits that rapresents one block] = 64 bit [Number of bits that rapresents a key ] = 128 bit [Number of phase ] = 16 phases Besides we must use al algorithm to generate the subkey that is very difficult to deciphered by an attacker. The algorithm used to decipher the Faistel ciphrature is the same used to encrypt the original text but in the deciphrature procedure the key are used from kn to k1 ( in the opposite order that we have used in the ciphrature algorithm). The input of the decipher procedure is the ciphred text and the state of the text during the difference phase of the algorithm is the same that we have in the ciphrature algorithm but in the opposite order. For exemple if we use all 16 phases of our algorithm to cipher and decipher, the state of the text in the therd phase of cipher algorithm is the same of the 13th deciphrature phase. We can see it in the next image: The ciphrature algorithm that we can see int left of the image is the same ciphrature algorithm analized in the first time but print in different way, but the operations are the same. In the right section of the image we can see the deciphrature algorithm it start in the bottom of the image. In this rapresentation I use [LE] to indicate the [L]eft block of byte of [E]ncrypt phase and [RE] to indicate the [R]ight block of [E]ncrypt procedure. In the same way, [RD] is the [R]ight part of [D]ecrypt operation and [LD] the [L]eft part of it.The numbers are the number of phase. We can see that in the deciphrature algorithm the input text is the ciphred text so the the ciphred text = RE16|LE16 the result of the ciphrature algorithm where RE16 is the right part of text after the 16th phase and LE16 is the left part of text after the same phase. This output is the input of Deciphrature algorithm so RE16|LE16 = LD0|RD0. The function F is the same for boot algorithm but the key are used in opposite order: int the ciphrature algorithm we started with k1 and ended with k16, in the deciphrature algorithm we start with k16 and and with k1. The opposite procedure used in the deciphrature algorithm do that: ==> RD1|LD1 = LE15|RE15 ==> LD2|RD2 = RE14|LE14 ==> RD3|LD3 = LE13|RE13 ==> ... ==> RD15|LD15 = LE1|RE1 ==> LD16|RD16 = LE0|RE0 So the last phase of deciphrature algoritm is the same of the first phase of ciphrature algoritm and all text changing operated during the ciphrature phases are the same of opposite phase of dceiphrature algorithm [ CYPHRATURE ALGORITHM ] [ DECIPHRATURE ALGORITHM ] --------------------------- --------------------------------------- [input text] | [output text] | | | ----------- | ----------- LE0 | k1 | RE0 | RD16=LE0 | | LD16=RE0 | | | | | | V V | | \___ ___/ (+)<-[F]<-- | \ / RE1 | k2 | LE1 | ____/ \____ | | | | ^ ^ | V V | LD16=RE0 | | RD16=LE0 -->[F]->(+) | | | LE2 | | RE2 | --->[F]-->(+) | | | RD15=LE1 | ^ ^ LD15=RE1 V V | | | | ... ... | | k1 | LE14 | k15 | RE14 | (+)<--[F]<---| | | | | ^ ^ | V V | | LD14=LE2 | | | RD14=RE2 (+)<-[F]<-- | | k2 | RE15 | k16 | LE15 | ... ... | | | | ^ ^ | V V | LD2=RE14 | | RD2=LE14 -->[F]->(+) | | | LE16 | | | --->[F]-->(+) | | | | ^ ^ \__ __/ | RD1=LE15 | | | LD1=RE15 \ / | | k15 | ___/ \___ | (+)<--[F]<--- | | | ^ ^ | V V | LD0=RE16 | | | RD0=LE16 [ RE16 | LE16 ] | | k16 | [ ciphred text ] | |___________| | ^ | | | [ciphre text] ---------------------------------------------------------[0x3 - DES - Data Encryption Standard ] The des algorithm is the most used ciphrature algorithm. Hi is very similar to Feistel's algorithm but have other two procedure: the initial procredure of permutation and the ending procedure of permutation that is the inverse of the first. The input of the des algorithm is a configuration of 64bit of text, another input is a key of 64bit but only 56 of this are used. We can rapresent the des in this way: [Original text 64 bit] [ Key of 64 bits ] | | V V [Initial Permutation ] [Permutation type 1] | | V V [Phase 1]<------------[Permutation type 2]<-----[Left Shift] | | V V [Phase 2]<------------[Permutation type 2]<-----[Left Shift] | | V | ... | | | V V [Phase 16]<-----------[Permutation type 2]<-----[Left Shift] | V [ 32bit change ] | V [ Final Permutation ] | V [Ciphred text 64 bit ] In the firse time when we insert the original text in input the algorithm permute all bit using this permutation table : [ ORIGINAL BITS CONFIGURATION ] [ PERMUTATED BITS CONFIGURATION ] | 01 | 02 | 03 | 04 | 05 | 06 | 07 | 08 | | 58 | 50 | 42 | 34 | 26 | 18 | 10 | 02 | | 09 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | | 60 | 52 | 44 | 36 | 28 | 20 | 12 | 04 | | 17 | 18 | 19 | 20 | 21 | 22 | 23 | 24 | | 62 | 54 | 46 | 38 | 30 | 22 | 14 | 06 | | 25 | 26 | 27 | 28 | 29 | 30 | 31 | 32 | | 64 | 56 | 48 | 40 | 32 | 24 | 16 | 08 | | 33 | 34 | 35 | 36 | 37 | 38 | 39 | 40 | | 57 | 49 | 41 | 33 | 25 | 17 | 09 | 01 | | 41 | 42 | 43 | 44 | 45 | 46 | 47 | 48 | | 59 | 51 | 43 | 35 | 27 | 19 | 11 | 03 | | 49 | 50 | 51 | 52 | 53 | 54 | 55 | 56 | | 61 | 53 | 45 | 37 | 29 | 21 | 13 | 05 | | 57 | 58 | 59 | 60 | 61 | 62 | 63 | 64 | | 63 | 55 | 47 | 39 | 31 | 23 | 15 | 07 | So the bit that is in position 09 go in position 39 and in position 09 go the bit in position 60 All bits of the original text are changed in this way. The final premutation table is the inverse of this so we have that Y = IP^-1(X)= IP^-1(IP(M)) where: ----------------------------------------------- [M] = [M]essage original bit configuration [IP] = [I]nitial [P]ermutation [IP^-1] = Inverse [I]nitial [P]ermutation [X] = IP(M) [Y] = Inverse of IP(M) ----------------------------------------------- The Final Inverse Permutation is this: | 40 | 08 | 48 | 16 | 56 | 24 | 64 | 32 | | 39 | 07 | 47 | 15 | 55 | 23 | 63 | 31 | | 38 | 06 | 46 | 14 | 54 | 22 | 62 | 30 | | 37 | 05 | 45 | 13 | 53 | 21 | 61 | 29 | | 36 | 04 | 44 | 12 | 52 | 20 | 60 | 28 | | 35 | 03 | 43 | 11 | 51 | 19 | 59 | 27 | | 34 | 02 | 42 | 10 | 50 | 18 | 58 | 26 | | 33 | 01 | 41 | 09 | 49 | 17 | 57 | 25 | Now we can see the des algorithm in all his particoulars. The next image raprsent the internal structure of a single phase. The two input are the text of 64bits (in the left of image) and the key of 64 bits (in the right of image). Only 56 bits of 64bits of keys are used by the algorithm So now we descirbe this: [Phase i-1]<------------[Permutation type 2]<-----[Left Shift] In every one phase the 64bits of text are divided in two parts of 32 bits. In this image we have rapresentated the left part of 32 bit with the mane L(i-1) becouse we considery a generic i-1 number phase. The right block of 32 bits is named R(i-1). In the right part of the image we can see that out key of 64 bits is divided in two part of 28bits becouse we use only 56 bits and not all 64 bits, since we have named L and R the Left and Right part of the text configuation we can named C and D the two part of the courrent key. [32 left bits] [32 right bits] [28 letf bits] [28 right bits] [ L(i-1) ] [ R(i-1) ] [ C(i-1) ] [ D(i-1) ] | | | | --------|----------------| | | | | V V V | | [Expansion/Permutation] [Left shift] [Left shift] | | | | | | | /48 --------| |------- | | | | | | | | | V | V V | | | (+)<-----------k(i)--/48bits----|----[Permutation Contraction] | | | | | | | | /48 | | | | | | | | | V | | | | [Sobstitution S-box] | | | | | | | | | /32 | | | | | | | | | V | | | | [Permutation] | | | | | | | | | V | | | -------------->(+) | | | | | | V V V V [L(i)] [R(i)] [C(i)] [D(i)] The Right 32 bits of the text are given in input to the Expansion/Permutation method that return a new bit configuration that is composit of 48 bits and not 32 bits.This method use the next table to permutate and adding the other 16bits to the courrent configuration of 32. The initial configuration of 32 bits is this : | 01 | 02 | 03 | 04 | | 05 | 06 | 07 | 08 | | 09 | 10 | 11 | 12 | | 13 | 14 | 15 | 16 | | 17 | 18 | 19 | 20 | | 21 | 22 | 23 | 24 | | 25 | 26 | 27 | 28 | | 29 | 30 | 31 | 32 | This method insert the others bits in this way as showed by the next table: [Add ] [ Original config ] [Add ] ---- ------------------- ---- | 32 |+| 01 | 02 | 03 | 04 |+| 05 | | 04 |+| 05 | 06 | 07 | 08 |+| 09 | | 08 |+| 09 | 10 | 11 | 12 |+| 13 | | 12 |+| 13 | 14 | 15 | 16 |+| 17 | | 16 |+| 17 | 18 | 19 | 20 |+| 21 | | 20 |+| 21 | 22 | 23 | 24 |+| 25 | | 24 |+| 25 | 26 | 27 | 28 |+| 29 | | 28 |+| 29 | 30 | 31 | 32 |+| 01 | ---- ------------------- ---- The new bits configuration, output of the [Expansion/Permutation] procedure go in input to the Xor method (in the image rapresentated by (+)). The other input of this Xor method is a new key of 48 bits, this key is generated from the original key of 64 bit where only 56bits are used. The output of the Xor method between the 48bits of new configuration of the right part of text and the new generate 48bits of the courrent key is a new bit configuration of 48 bits that go in input to the sobstitution method that is a ridution from 48bits in 32bits. The output of this go in input to a new permutation method, this method use the next table to exchange the order of the bits. [ Table of Permutation function ] --------------------------------------- | 16 | 07 | 20 | 21 | 29 | 12 | 28 | 17 | | 01 | 18 | 23 | 26 | 05 | 18 | 31 | 10 | | 02 | 08 | 24 | 14 | 32 | 27 | 03 | 09 | | 19 | 13 | 30 | 06 | 22 | 11 | 04 | 25 | --------------------------------------- The output of this permutation is a new 32bits configuration that rapresents the courrent 32bits configuration of the right part of the initial input text of the courrent function. This bits go in input with the left 32 bits configuration in a xor method. the result of this is the new 32 bits configuration of the courrent right part of the text. The original 32bits block of right part that every one phase take in input is rememberd and used as left part of 32bits in the next phase. When the new key is generated too we remember the two 28bits configuration shifted and we use this as the new two 28 bits configuration of the key for the next phase. Now is interesting to see as work the [Sobstitution S-box] procedure. This method take in input the output of 48bits of the xor method and return in output a new bit configuration of 32 bits To do this the S-box method use 8 little box named box S. In the first time the 48 bits are divided in 8 block of 6 bits every one; one block for one box, 8 blocks for 8 boxs. Every Box is based on a personal table and use the 8 bits that have in input to take a value from his personal table. Now we report the table of the height Box-S and after that we do an exemple to understend it. Every table is composit of 4 rows and 16 columns [S1]|[C00][C01][C02][C03][C04][C05][C06][C07][C08][C09][C10][C11][C12][C13][C14[C15] ----|-------------------------------------------------------------------------------- [R0]| 14 04 13 01 02 15 11 08 03 10 06 12 05 09 00 07 [R1]| 00 15 07 04 14 02 13 01 10 06 12 11 09 05 03 08 [R2]| 04 01 14 08 13 06 02 11 15 12 09 07 03 10 05 00 [R3]| 15 12 08 02 04 09 01 07 05 11 03 14 10 00 06 13 [S2]|[C00][C01][C02][C03][C04][C05][C06][C07][C08][C09][C10][C11][C12][C13][C14[C15] ----|-------------------------------------------------------------------------------- [R0]| 15 01 08 14 06 11 03 04 09 07 02 13 12 00 05 10 [R1]| 03 13 04 07 15 02 08 14 12 00 01 10 06 09 11 05 [R2]| 00 14 07 11 10 04 13 01 05 08 12 06 09 03 02 15 [R3]| 13 08 10 01 03 15 04 02 11 06 07 12 00 05 14 09 [S3]|[C00][C01][C02][C03][C04][C05][C06][C07][C08][C09][C10][C11][C12][C13][C14[C15] ----|-------------------------------------------------------------------------------- [R0]| 10 00 09 14 06 03 15 05 01 13 12 07 11 04 02 08 [R1]| 13 07 00 09 03 04 06 10 02 08 05 14 12 11 15 01 [R2]| 13 06 04 09 08 15 03 00 11 01 02 12 05 10 14 07 [R3]| 01 10 13 00 06 09 08 07 04 15 14 03 11 05 02 12 [S4]|[C00][C01][C02][C03][C04][C05][C06][C07][C08][C09][C10][C11][C12][C13][C14[C15] ----|-------------------------------------------------------------------------------- [R0]| 07 13 14 03 00 06 09 10 01 02 08 05 11 12 04 15 [R1]| 13 08 11 05 06 15 00 03 04 07 02 12 01 10 14 09 [R2]| 10 06 09 00 12 11 07 13 15 01 03 14 05 02 08 04 [R3]| 03 15 00 06 10 01 13 08 00 04 05 11 12 07 02 14 [S5]|[C00][C01][C02][C03][C04][C05][C06][C07][C08][C09][C10][C11][C12][C13][C14[C15] ----|-------------------------------------------------------------------------------- [R0]| 02 12 04 01 07 10 11 06 08 05 03 15 13 00 14 09 [R1]| 14 11 02 12 04 07 13 01 05 00 15 10 03 09 08 06 [R2]| 04 02 01 11 10 13 07 08 15 09 12 05 06 03 00 14 [R3]| 11 08 12 07 01 14 02 13 06 15 00 09 10 04 05 03 [S6]|[C00][C01][C02][C03][C04][C05][C06][C07][C08][C09][C10][C11][C12][C13][C14[C15] ----|-------------------------------------------------------------------------------- [R0]| 12 01 10 15 09 02 06 08 00 13 03 04 14 07 05 11 [R1]| 10 15 04 02 07 12 09 05 06 01 13 14 00 11 03 08 [R2]| 09 14 15 05 02 08 12 03 07 00 04 10 01 13 11 06 [R3]| 04 03 02 12 09 05 15 10 11 14 01 07 06 00 08 13 [S7]|[C00][C01][C02][C03][C04][C05][C06][C07][C08][C09][C10][C11][C12][C13][C14[C15] ----|-------------------------------------------------------------------------------- [R0]| 04 11 02 14 15 00 08 13 03 12 09 07 05 10 06 01 [R1]| 13 00 11 07 04 09 01 10 14 03 05 12 02 15 08 06 [R2]| 01 04 11 13 12 03 07 14 10 15 06 08 00 05 09 02 [R3]| 06 11 13 08 01 04 10 07 09 05 00 14 13 02 03 12 [S8]|[C00][C01][C02][C03][C04][C05][C06][C07][C08][C09][C10][C11][C12][C13][C14[C15] ----|-------------------------------------------------------------------------------- [R0]| 13 02 08 03 06 15 11 01 10 09 03 14 05 00 12 07 [R1]| 01 15 13 08 10 03 07 04 12 05 06 11 00 14 09 02 [R2]| 07 11 04 01 09 12 14 02 00 06 10 13 15 03 05 08 [R3]| 02 01 14 07 04 10 08 13 15 12 09 00 03 05 06 11 The input that arrive to the S-Box method is an input of 6 bits the output must be the output of 4 bits so to the end of this procedure we have 8 block of 4 bits... 4*8 = 32 bits (the new right 32bits configuration). Imagine that we obtain in input to S-Box[1] the bit configuration: 011001 The first and the lost bits (01) raprsents the number of row, the other 4 bits(1100) the number of column, so we have that 01 = 1(in decimal) and 1100 = 2^2+2^3 = 4+8 = 12(in decimal). Since we have imaginated that this is the input of the S-Box[1] we must take the element row = 1 and column = 12 from the [S1] table that is the value 09. The binary value of 09 is 1001 and this is the output of S1. The same operation is repetuted by all the other S-Box and the total output is a 32 bits configuration. We can rapresents the [Sobstitution S-box] in this way: [Expansion/Permutation] [Left shift] [Left shift] | | | /48 --------| |------- | | | | | V | V V | (+)<-----------k(i)--/48bits----|----[Permutation Contraction] | | /48 | V ----------------------------------------------------------------------------------- |||||| |||||| |||||| |||||| |||||| |||||| |||||| |||||| [ S1 ] [ S2 ] [ S3 ] [ S4 ] [ S5 ] [ S6 ] [ S7 ] [ S8 ] |||| |||| |||| |||| |||| |||| |||| |||| --------------------------------------------------------------------------------- | V [32 bits] After that we know as work the S-Box procedure we can see as the algorithm generate the several subkey that hi use during the 16 phases. In the first time we have only a single key gived in input by the user, this key is a key of 64bits but 8 of this bits are ignored.To choose the bits that do not consider the algorithm use this table: | 01 | 02 | 03 | 04 | 05 | 06 | 07 |-| 08 | | 09 | 10 | 11 | 12 | 13 | 14 | 15 |-| 16 | | 17 | 18 | 19 | 20 | 21 | 22 | 23 |-| 24 | | 25 | 26 | 27 | 28 | 29 | 30 | 31 |-| 32 | | 33 | 34 | 35 | 36 | 37 | 38 | 39 |-| 40 | | 41 | 42 | 43 | 44 | 45 | 46 | 47 |-| 48 | | 49 | 50 | 51 | 52 | 53 | 54 | 55 |-| 56 | | 57 | 58 | 59 | 60 | 61 | 62 | 63 |-| 64 | The bits in position 08,16,24,32,40,48,56 and 64 are ignored so we have a new key of 56 bits The configuration of bits of the courrent key are permutated using the new table : | 57 | 49 | 41 | 33 | 25 | 17 | 09 | | 01 | 58 | 50 | 42 | 34 | 26 | 18 | | 10 | 02 | 59 | 51 | 43 | 35 | 27 | | 19 | 11 | 03 | 60 | 52 | 44 | 36 | | 63 | 55 | 47 | 39 | 31 | 23 | 15 | | 07 | 62 | 54 | 46 | 38 | 30 | 22 | | 14 | 06 | 61 | 53 | 45 | 37 | 29 | | 21 | 13 | 05 | 28 | 20 | 12 | 04 | After that we have obtenuted a new configuration of 56bits, now the algorithm consider it as two bits configuration of 28bits everyone.In the image we have named this two part C(i-1) and D(i-1) This two bits configurations are shifted in the left direction of 1 or 2 bits as showed in this table: number of phase: 01 02 03 04 05 06 07 08 09 10 11 12 13 14 15 16 number of shift: 01 01 02 02 02 02 02 02 01 02 02 02 02 02 02 01 So if we stay executing the phase number 3 boot the 28bits configuration of key are shifted of 2 bits in the left direction, else if we stay execution the phase number 2 the two subkey are shifted of only one bit in the left direction. Boot the subkey of 28bits are gived in input to the [Permutation Contraction] permute and restrict the bits configuration from 56bits to 48bits. To do this the permutation contraction use this table: | 14 | 17 | 11 | 24 | 01 | 05 | 03 | 28 | | 15 | 06 | 21 | 10 | 23 | 19 | 12 | 04 | | 26 | 08 | 16 | 07 | 27 | 20 | 13 | 02 | | 41 | 52 | 31 | 37 | 47 | 55 | 30 | 40 | | 51 | 45 | 33 | 48 | 44 | 49 | 39 | 56 | | 34 | 53 | 46 | 42 | 50 | 36 | 29 | 32 | As you can see the height bits (the bits in position 9,18,22,25,35,38,43,54) are ignored and the other are permutated as showed in the table. The output of this procedure is a key of 48bits that go in input to the xor method with the 48bits output of the expansion procedure seed first! As for the Feistel's ciphrature, the des decriptation algorithm is the same used to encrypt but in the decriptation procedure the subkey are used in opposite order respect to the ciphrature it -------------------------------------------------------[0x4 - Block's ciphrature working terms ] Are there 4 working terms that are used for all block's ciphrature as the DES algorithm that we have seed in the prev point. This working terms are utils to complicate the criptographic analize by an attacker. The four terms are showed in the next table: Electronic CodeBook(ECB) Cipher Block Chaining(CBC) Cipher Feedback(CFB) Output Feedback(OFB) The Electronic CodeBoock is the most simple of all terms, this procedure divided the text in several block on 64bits and use the same key to encrypt only one of they. Time 1 Time 2 ... Time n ------ ------ ------- P1 (64bits) P2 (64bits) Pn (64bits) | | | V V V Key -> [Encrypting] key -> [Encrypting] key -> [Encrypting] | | | V V V C1 C2 Cn So if you can imagine P1 is the first block of 64 bits of the original text and C1 is the 64bits block of ciphrated text, the key used is the same in the time 1, time 2 ... time n where n is the last complete ciphrature operation of a single block of 64bits. If when we divide the total text in blocks of 64 bits the last block is composit by a number of bits different from 64, we can adding to it several bits = 0 to obtain a block of 64bits with the same value of the original block. The ECB term is good if you want send a little text, for exemple if you want encrypt you key, you can use this term but if you want encrypt e very long text it is not good procedure becouse since all block of 64 bits are ciphrate using the same key, if are there two equals 64bits block the ciphrate text is the same and an attacker can use this information to find the correct key. If we want that this algorithm is more difficult to decrypt by an attacker we must apply a little modify to ECB term to obtain that if we entrypt in two differents time the same 64bits block of original text we obtain two different ciphred text. To do this the Cipher Block Chaining use a xor operation as showed in the next image: Time 1 Time 2 ... Time n ------ ------ ------ IV P1 P2 Pn | | | | | V V V ----->(+) ----->(+) ----->(+) | | | | | V | V | V k-->[Encr] | k-->[Encr] | k-->[Encr] |-------- |-------- | V V V C1 C2 ... Cn The procedure is similar to the ECB term, the total text is divided in several block of 64bits and all blocks are ciphrated using the same key, the difference is that the CBC procedure use an xor operation between the 64bits of original text and anoter block of 64 bits. In the first time the block of 64bits that go in input to the xor operation with the first block of original text is IV (Initialize Vector) the value of vector is defined by user and is similar to a key. After the first time, the next 64bits blocks are sended in input to the xor procedure with the prev output of ciphrature operation, so if you can see in the imagine in the time 2 the input of xor operation are the second block of 64 bits of original text and the output of the prev ciphrature operation (in this case the ciphrated text of the first block of original text). In this way, is more difficult that two equals 64bits of original text have the same prev ciphred output so when two equals 64bits block of original text go in input of a xor operation with two differents ciphrated text we obtain two differents value as we want. To decipher this text, is important that the user know the key and the Initialization Vector since the procedure is the same showed first for the ciphrature operation but the input is the ciphred text and the output is the original text as you can see in the next image: Time 1 Time 2 ... Time n ------ ------ ------ C1 C2 Cn |------ |------ | V | V | V k-->[Decr] | k-->[Decr] | k-->[Decr] | | | | | V | V | V IV-->(+) ----->(+) ----->(+) | | | V V V P1 P2 ... Pn If we use this algorithm to encrypt out text and want send the key and the Initialization Vector to our friend we can encrypt IV and key using the ECB algorithm since they are two block of 64 bits. The term number three that we consider in our ciphrature study is named Cipher Feedback (CFB) this procedure is more used when we want send a ciphred bits number different from 64. We can imagine that during a chat conference we want encrypt out text so we want send 8 bits to 8 bits ciphred our message or another number of bit. The CFB procedure work as showed in the next image ------------------------------ | | Initial Vector | <<<<<<<< LeftShift V [Register of 64 bits] | [Register of 64bits + C1] | | | /64 | /64 | | | V | V key--->[Ciphrature] | key--->[Ciphrature] | | | /64 | /64 | | | V | V [Select 8bits & Delete 56bits] | [Select 8bits & Delete 56bits] | | | /8 | /8 | | | P1--/8->(+) | P2--/8->(+) |-------------------/8------ |-------------------/8------ ... V V C1 C2 In the first time the user create an Initial Vector of 64 random bits and the key, this vector and the key are ciphrated using the Des ciphrature, after that we have a output of 64 bit of a 64bits vector ciphred from this output we take the number of bits that we want (in our exemple we imagine that want send 8bits), after that we take the 8 bits from the vector ciphrated of 64, we send it in input with the first 8 bits of out text that we want encrypt, in this way we have a new bit configuration of 8 bits that is the ciphrature of our first 8 bits of original text. Now we can send this 8bits of ciphrate text in the 64bits vector that we have created in the first time, we insert this bits in the right part of the vector and shift the vector of 8 bits in this way the new 64bits vector is different from the prev vector and the it change his status in dinamic way. After that we repeat the same operation that we have execute in the first part: we encrypt the vector with the same key and obtain a new 64bits configuration, we take 8 bits of this 64bits and send they in input to the xor operatio with the second block of 8bits of original text that we want encrypt, the output of this is a 8bits of ciphrate text assigned to the second block of 8 bits of our original text. This block of 8 ciphrate bits are sended in the Initial vector that is shifted of 8 bits in the left direction and used to encrypt the next 8 bits of original text that we want encrypt. The same procedure is repetuted while the ciphrature of the total text is not finished. The decriptation operation of this procedure is very similar to the encryptation it, you can see the rapresentation of decriptation procedure in the next image: ---------------------------- -------... | | | Initial Vector | <<<<<<<< Left Shift V | [Register of 64 bits] | [Register of 64bits + C1] | | | | | /64 | /64 | | | | | V | V | key--->[Ciphrature] | key--->[Ciphrature] | | | | | /64 | /64 | | | | | V | V | [Select 8bits & Delete 56bits] | [Select 8bits & Delete 56bits] | | | | | V | V | (+)<----------------------C1 (+)<----------------------C2 | | V V P1 P2 The CFB procedure have a little problem; imagine that during the xor operation between the 8bits of original text and the 8bits select from the ciphred vector have an error, since the output of this operation is accodated to the vector this error is propagate to the other text ciphrature. To resolve this little problem we can apply a little modify to the CFB procedure to obtain that if during the encryptation of a 8bits of original text is there an error this error don't involve the nexts block of original text. The modify of the CFB procedure is named Output FeedBack (OFB) and is showed in the next image: ------------------------------ | | Initial Vector | <<<<<<<< LeftShift V [Register of 64 bits] | [Register of 64bits + C1] | | | /64 | /64 | | | V | V key--->[Ciphrature] | key--->[Ciphrature] | | | /64 | /64 | | | V | V [Select 8bits & Delete 56bits] | [Select 8bits & Delete 56bits] | | | /8-----------------/8------- /8-----------------/8------- ... | | P1--/8->(+) P2--/8->(+) | | V V C1 C2 As you can see the algorithm of OFB procedure is the same of the CFB procedure, but the 8 bits that are sended and added to the vector are not the ciphred text but the output of the ciphrature operation of Register itself, in this way if C1 have an error, this error is not sended and added to the Initial Vector so C2 can be correct or can have another error but this error is not dipendence of C1 error.