|| 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.