12/21/2015

cryptography12

Cryptography 12


RSA

RSA is a block cipher, the block size must be less than or equal .\(\log_{2}(n)+1\), if block size =i bits \(2^{i}<n<2^{i}+1\)
The encryption and decryption are on the following form
\(C = M^{e} mod(n)\)
\(M = C^{d} mod(n) = (M^{e})^d mod(n) = M^{ed} mod(n)\)
The relationship between e and d are multiplicative inverse modulo Q(n) as in Euler Totient Function   ed mod(Q(n))=1
d is relatively prime to Q(n) and e also.

Now let us look at RSA ingredients 

1- q and p two prime numbers
2- n=q*p
3- e by using gcd(Q(n),e)=1   1<e<Q(n)
4- d mod(Q(n)) = \(e^{-1}\)

Example:

1- Two prime numbers p=17 q=11
2- n=q*p= 17*11=187
3- Q(n) = (p-1)*(q-1)= 16*10=160
4- Select e such that e is relatively prime to Q(n)=160 and less than Q(n) ,,, We choose e=7
5- Determine d such that ed mod(Q(n)) = 1 ,,, d=23   (23*7 mod(160) =1)

Choosing q and p:

1- q and p should be differ in length by only a few digits, in 1024 bit key (309+ decimal digits) both q and p should be on the order of magnitude of \(10^{75}\) to \(10^{100}\).
2- (q-1) and (p-1) should contain a large prime factor.
3- gcd((q-1),(p-1)) should be small.

Note: gcd stands for Greater common divisor http://en.wikipedia.org/wiki/Greatest_common_divisor
Note: If e < n and d < \( n^{1/4}\) then d can be easily determined.

Miller-Rabin Algorithm :

Miller-Rabin Algorithm is a primality test, an algorithm which determines whether a given number is prime or not.
In practice, we implement the Miller-Rabin test as follows:

1- Given n, find s so that n1=2sq for some odd q.
2- Pick a random a{1,...,n1}
3- If aq=1 then n passes (Prime).
4- For i=0,...,s1 see if a2iq=1. If so, n passes (Prime).
5- Otherwise n is composite. 

The pseudocode Of Miller-Rabin Algorithm :
Input: n > 2, an odd integer to be tested for primality;
       k, a parameter that determines the accuracy of the test
Output: composite if n is composite, otherwise probably prime
write n − 1 as 2s·q with q odd by factoring powers of 2 from n − 1
LOOP: repeat k times:
   pick a randomly in the range [2, n − 1]
   xaq mod n
   if x = 1 or x = n − 1 then do next LOOP
   for r = 1 .. s − 1
      xx2 mod n
      if x = 1 then return composite
      if x = n − 1 then do next LOOP
   return composite
return probably prime

Note: You can use this python code to try Miller-Rabin algorithm https://github.com/Hamza-Megahed/miller-rabin-test/blob/master/miller-rabin.py


11/20/2015

cryptography11

Cryptography 11


Pseudorandom Number Generation (PRNG)

We uses PRNGs everyday over internet, network security applications and Protocols such as RSA and authentication algorithms.
There are two requirements for generating a sequence of random numbers:
1- Randomness
2- Unpredictability

1- Randomness:

For sure, to generate a sequence of random numbers must has randomness and we can define this concept statistically by two criteria :
1- Uniform distribution:
Uniform distribution means the frequency of occurrence of ones and zeros should be approximately equal.
2- Independence:
Independence means no sequence can be inferred from another sequence.
Note: We can preform tests for uniform distribution but we can't prove independence.

2- Unpredictability:

Unpredictability means the successive members of sequence of numbers must be unpredictable.

Pseudorandom Number Generation is:

PRNGs take input called the seed, the seed is a fixed value, then producing output by using a deterministic algorithm and any additional outputs are feedback to PRNG algorithm again as input.
The seed must be secure because PRNG uses a deterministic algorithm so if the attacker can deduce the seed then he can determine the output of PRNG.

PRNG Types:

1- Purpose-built algorithm:
Algorithms that are design for generating pseudorandom such as RC4.

2- Algorithms based on existing cryptographic algorithms:
There are some cryptographic algorithms need a random input to produce a ciphertext such as in a symmetric key encryption and hashing functions.

PRNG Algorithm Types:

1- Linear Congruential Generators:

This algorithm is widely used to produce random numbers and it's proposed by Lehmer.
This algorithm has 4 parameters:
1- m   --> The modules
2- a   --> The multiplier
3- c   --> The increment
4- X0  --> The starting value

And the equation is :

This algorithm should pass three tests:
1- The function should generate all numbers from 0 to m before repeating.
2- The sequence should be random.
3- The function should implement efficiently with 32 bit arithmetic.

For example:
If we use Linear Congruential Generator a=7, c=0, m=32, x0=1
Then the output = {7,17,23,1,7,...}
We have a repeating value after 5th time {7}

So we need some modifications, m value should be equal to the maximum representable non-negative integer for the computer such as \(2^{31}\), It's recommended to use m as a prime number such as \(2^{31} - 1\)
That gives us about 2 billion choices for a, but a few choices will pass the three tests such as \(a=7^{5}\)  c=0.

2- Blum Blum shub Generator (BBS):

BBS is a secure PRNG , first we need a prime numbers p and q so that (p mod(4))=(q mod(4))=3  for example 7 and 11
Then let n=p*q, the we choose a random number S, and S should be relatively prime to n.
Then BBS generates a sequence of bits Bi according to the next algorithm
\({X}_{0}={S}^{2} mod (n)\)
\(For \ i=0\ to\ \infty\)
\({X}_{i}=(X-1)^{2}mod(n)\)
\({B}_{i}={X}_{i}mod(2)\)

True Random Number Generation (TRNG)

TRNG uses nondeterministic source to produce random numbers by measuring unpredictable natural processes such as radiation, gas discharge , ..etc
We can use some source of randomness on our computers such as sound input ,video input .

Note #1: TRNG is not practical for stream cipher.
Note #2: TRNG may produce an output that is biased (the number of ones and zeros are not equal) and to eliminate this bias is by passing the bit stream through a hashing function such as MD5 and SHA1.

6/23/2015

cryptography10

Cryptography 10

AES

AES takes a plaintext block 16 bytes (128 bits) and key length 16, 24, 32 bytes (128, 192, 256 bits) AES-128, AES-192, AES-256 depending on key length.
The input to encryption or decryption algorithm in AES is 128 bits block = 16 bytes as 4x4 matrix, this matrix is copied into a state array, then the state array passes through and modified in each stage and then the state array is copied to output matrix.
The algorithm consists of N rounds, and N depends on key length
For 16 bytes key --> N=10 rounds
For 24 bytes key --> N=12 rounds
For 32 bytes key --> N=14 rounds

Initial transformation(Round 0) consists of add round key.
All rounds (except the final round) consists of 4 functions
1- Substitute Bytes
2- Shift Row
3- Mix Column
4- Add round key
The final round consists of 3 functions
1- Substitute Bytes
2- Shift Row
3- Add round key

AES in not a Feistel structure because in Feistel half of data is used to modify the other half and then the two halves are swapped, but AES processes the entire block.

The input key is expanded to 44 words 33 bits each, and every 4 words(128 bits) serve as input to each round

AES Transformation Function :

1- Substitute Bytes Transformation :

Substitute Bytes Transformation maps each state into a new value by a table look up process from S-Box table.

S-Box table is 16x16 matrix that contain a permutation of all possible 8-bits value by the following rules:
A- The leftmost 4 bits are used as row value.
B- The rightmost 4 bits are used as column value.
C- The intersection to select a unique 8-bits value in S-Box.

For example :

6A references row=6 column=A of S-Box which contain 02.

The inverse of Substitute Byts(InvSubBytes) is the same but we look up in inverse S-Box table instead of S-Box.

2- Shift Row Transformation :

Shift Row Transformation apply the following on the state :

1- The first row is not altered.
2- The second row preform 1-byte circular left shift.
3- The third row preform 2-byte circular left shift.
4- The fourth row preform 3-byte circular left shift.

The inverse shift row(InvShiftRow) preform a circular shift to the right.

3- Mix Column Transformation.

Mix Column Transformation operate on each column individually, each byte of a column is mapped into a new value that is a function of all four bytes in that column.
Mix column can be defined by the next multiplication on state.
For example:

Note : Dot . notation refers to a multiplication in Galois field 2^8
The inverse min column called(Inv MixColumn) is defined by


4- Add round key Transformation

Add round key Transformation preform XOR operation between the round key and state each 128 bits.
The randomness and round key expansion increase the security of AES.

What is key expansion ?
The key expansion algorithm takes as input 16 bytes(4 words) and output 176 bytes(44 words) 4 words for each round and 4 words for initial add round key.

AES key expansion preform the next steps :
1- Use input key in the first 4 words (w0,w1,w2,w3).
2- Use the last word in each stage (w3,w7,w11,...) and preform one-byte shift left on the word
For example :
In stage one use w3(A,B,C,D)
After one-byte shift left
w3=(B,C,D,A)
3- Preform byte-substitution on each byte in word from S-box.
4- XOR with the round constant word, the round constant word is a word which the three right most bytes are zeros in all rounds.
Rcon[i] = Rcon ,0,0,0                    i=number of rounds
In
Rcon[1] = 01000000
Rcon[j] = 2.Rcon[j-1]

Note : The multiplication here in under Galois Field GF(2^8)
For example:
This is the input to AES
0F1571C947D9E8590CD7ADD6AF7F6798
W0 = 0F1571C9
W1 = 47D9E859
W2 = 0CD7ADD6
W3 = AF7F6798
Then we take the last word and preform key expansion
1- Preform one-byte shift left = 7F6798AF
2- preform byte-substitution = D2854679
3- Rcon for the first round = 01000000
4- XOR D2854679 and 01000000
x1=D3854679
w4 = w0 ⊕ x1 = DC9037B0
w5 = w1 ⊕ w4 = 9B49DFE9
w6 = w5 ⊕ w2 = 97FE723F
w7 = w6 ⊕ w3 = 388115A7

5/07/2015

cryptography9

Cryptography 9


Simplified AES

Simplified AES is an educational algorithm to understand AES encryption algorithm , Simplified AES has the exact same structure of AES but with smaller parameters.

Simplified AES takes 16 bits input block, 16 bits key and produces 16 bits output block cipher.

Encryption Algorithm :


Simplified AES encryption algorithm uses 4 different functions transformations
1- Add key
2- Nibble substitution
3- Shift row
4- Mix column

Encryption algorithm itself consists of 3 rounds and each round contains functions

Round 1 -- Add key
Round 2 -- Nibble substitution --> Shift row --> Mix column --> add key
Round 3 -- Nibble substitution --> Shift row --> Add key

As you can see in each round includes the add key function and make use of 16 bits key from the initial 16 bits key which expanded to 48 bits so each round can take 16 bits key(round key) to work with.

Each function operates on 16 bits as 2x2 matrix ordered in matrix by column , the first 8 bits of 16 bits of plaintext takes the first column and the second 8 bits takes the second column.

Now let's look at each function individually

1- Add key :

Add key function is operates XOR of 16 bits state matrix and 16 bits round key.

2- Substitution :

Substitution function maps each state into a new value by look up in S-Box table , this table contain all permutation of all 2^4 values by the following rules:


A- The leftmost 2 bits are used as row value.
B- The rightmost 2 bits are used as column value.
C- The intersection selects a unique value in S-Box.
For example :


3- Shift row :

Shift row function preforms one circular shift on the second row in state matrix.

For example :


4- Mix column :

Mix column function operates on each column individually, each value in column is mapped into a new value that is a function of both values in column.
The transformation as in the following matrix multiplication :

Then we get :
Note: Dot . notation here refers to multiplication in GF(2^4).
For example:



5- Key Expansion :

The initial 16 bits key split into 2 words each of 8 bits (W0 and W1))and expanded to six words(3 keys)

W2 = W0 ⊕ Rcon(1) ⊕ Sub(W1)
W3 = W2 ⊕ W1
W4 = W2 ⊕ Rcon(2) ⊕ Sub(w3)
W5 = W4 ⊕ W3

Sub: preform a substitution from S-box

Rcon is Round constant so Rcon(i) = x^(i+2) to form the leftmost digits and the rest fill with zero
Rcon(1) = x^3 = 1000
Rcon(2) = x^4 mod(x^4+x+1) = (x+1) = 0011

3/19/2015

cryptography8

Cryptography 8


Finite Field

In this section we will talk about something in abstract algebra, and i'm trying to make it painless and simple.
Finite Fields is a vary important topic in cryptography and it is used in many encryption algorithms such as AES encryption algorithm.
I will skip a lot of branches in abstract algebra such as (modular,arithmetic Euclidean algorithms ... etc)and you can find it easily on Wikipedia.

Starting with some terminology

A set : Is a group of elements or members represented as a unit, set can be described in several ways such as braces {5,13,27,30}.
A field : Is a set of elements with two binary operations addition and multiplication.

Fields have the following properties :
1- Closure under addition          ---> If a and b belong to S, then a+b is also in S.
2- Associativity of addition        ---> a+(b+c) = (a+b)+c and a,b,c in S.
3- Additive identity                   ---> There is an element 0 in R such that a+0 = 0+a = a for all in S.
4- Additive inverse               ---> For each a in S there is an element -a in S such that a+(-a)=(-a)+a =0.
5- Commutativity of addition     ---> a+b=b+a for all a.b in S.
6- Closure under multiplication  ---> if a and b belong to S , then ab is also in S.
7- Associativity of multiplication ---> a(bc) = (ab)c for all a,b,c in S.
8- Distributed laws                   ---> a(b+c) = ab+ac for all a,b,c in S.
9- Multiplication Identity           ---> There is an element 1 in S such that a1 = 1a = a for all in S.
10- No zero division                 ---> if a,b in S and ab=0, then either a=0 or b=0.
11- Multiplication inverse          ---> If a belongs to S and a != 0 ,there is an element a^-1 is S such that aa^1 =1.

Finite Fields have a property called "order",order in finite field is the number of the elements in the filed and this order must be a power of a prime number GF(P^n)
GF is stands for Galois Field , and Galois is a mathematician who create the finite field.
p : Is a prime number.
n : Is a positive integer.

In finite field we preform operations such as addition and multiplication without leaving the set

For example :

in GF(7) , so the set will be {0,1,2,3,4,5,6}
six elements start from 0 to p-1
if we preform addition operation 5+4=9 mod(7) = 2
and 2 is in the set.

Polynomial Representation :

AES encryption algorithm work under GF(2^8) but in a binary representation, we will represent Galois Field by using polynomial, and it's much easier.
In GF(2^8) , if we want to represent GF(91)
First : we need to convert it into a binary 01011011
second : Convert it into a polynomial under one variable x (x^7+x^6+x^5+x^4+x^3+x^2+x^1+1)
and all zeros are discarded from the polynomial , so the polynomial representation will be
x^6+x^4+x^3+x+1

Mathematical operations (addition and multiplication) :

- Addition operation in polynomial representation in GF(2^8) Form :

To preform addition operation simply we will add two polynomials and then we take mod(2) to reduce 2 coefficients (remove any 2 coefficients).

For example :

In GF(2^8) add 83 and 249

83 = 01010011 = x^6+x^4+x+1                          ----> 1
249 = 11111001 = x^7+x^6+x^5+x^4+x^3+1    ----> 2
add 1 and 2 =
(x^7+2x^6+x^5+2x^4+x^3+x+2)mod(2)
remove 2 coefficients (2x^6+2x^4+2)
= x^7+x^5+x^3+x (polynomial representation)
= 10101010 (binary representation)
= 170 (decimal representation)


- Addition operation in binary representation in GF(2^8) Form :

To add two numbers in binary representation in GF(2^8) form we just preform XOR operation instead of arithmetic addition.

For example :

In GF(2^8) add 83 and 249

83 = 01010011
249 = 11111001
01010011 ⊕ 11111001 = 10101010 = 170


- Multiplication in polynomial representation in GF(2^8) form :

Here we will multiply two polynomials and then we take mod(2) to reduce 2 coefficients, but if the results exceed 255 in binary or 11111111 in binary or X^7 in polynomial then we use irreducible polynomial to reduce the results by a long division the result over the irreducible polynomial and the result is the reminder of division, and in GF(2^8) irreducible polynomial m(x) = x^8+x^4+x^3+x+1

For example :

In GF(2^8) multiply 83 and 249

83 = x^6+x^4+x+1                             -----> 1
249 = x^6+x^6+x^5+x^4+x^3+x+1   -----> 2

multiply 1 and 2 and take mod(2)

= x^13+x^12+x^7+x^6+x^4+x^3+x+1

OR by using MATLAB and get the same result :

a = gf( [1 0 1 0 0 1 1] );
b = gf( [1 1 1 1 1 0 0 1] );
c = conv(a,b)

The results here exceed x^7 then we preform a long division by the irreducible polynomial and the result is the reminder

x^13+x^12+x^7+x^6+x^4+x^3+x+1
---------------------------------------- =  x^5+x^4+x     Remainder = x^5+x^4+x^3+x^2+1
x^8+x^4+x^3+x+1

The result
= x^5+x^4+x^3+x^2+1 (polynomial representation)
= 00111101 (binary form)
= 61 (decimal form)

OR by using MATLAB and get the same result :

a = gf( [1 1 0 0 0 0 1 1 0 1 1 0 1 1] );
b = gf( [1 0 0 0 1 1 0 1 1] );
[q,r] = deconv(a,b)

Note #1: If you found this hard to understand you can use GF-Calculator to preform addition and multiplication on two decimal numbers in GF(2^8) form https://github.com/Hamza-Megahed/gf-calculator
Note #2: You can multiply two polynomials by using Euclidean algorithm (Extended Euclid).
Note #3: A polynomial is irreducible if it cannot be expressed as the product of two or more such polynomials.
Note #4: m(x) = x^8+x^4+x^3+x+1 is one of 30 possible irreducible polynomials of degree 8.

3/07/2015

cryptography7

Cryptography 7


DES (Data Encryption Standard)

DES :

DES adopted in 1977 by (NIST) National Institute of Slandered and Technology).
In DES data are encrypted in 64 bit block with a key length 56 bits and with output ciphertext 64 bits.
DES has the exact structure of Feistel Cipher but without Initial Permutation (IP) and Inverse Initial Permutation \(IP^{-1}\).

Key generator algorithm :

The key generator passes through many steps to produces subkeys.


1- Key generator algorithm take 64 bits key as input,the input key numbered in a table from 1 to 64 as the following:


2- Every eighth bit is ignored and produce 56 bits.



3- 56 bits passes through a permutation Choice one(PC-1)as the following:


4- The output is separated into two 28 bits C and D , the first 28 bits are called  \({C}_{0}\)(left part) and the last 28 bits are called \({D}_{0}\).

5- At each round a circular left shift is preformed on  \({C}_{i}-1\) and  \({D}_{i}-1\) by 1 or 2 bits by the next table.


6- Then \({C}_{i}-1\) and  \({D}_{i}-1\) in each round passes through permutation choice two (PC-2) to produces 48 bits.


7- The permutation Choice Two output in each round is use as input to encryption algorithm.



Encryption Algorithm :

There are two inputs to encryption algorithm 1- Plaintext 64 bits 2- Encryption key 48 bits.
Encryption algorithm also passes through many steps to produce a ciphertext, The next figure



1- The plaintext block 64 bits pass through an initial permutation (IP) that rearranged bits and produces the permuted input.

Initial Permutation :

A- Initial Permutation takes the plaintext as input table consists of 64 bits numbered from 1 to 64


B- Then the initial permutation will be permuted input 64 bits as the following :


C- The Inverse Initial Permutation is:


2- The permuted input block split into two halves each is 32 bits, the first 32 bits are called L and the last 32 bits are called R.

Now The F function will start by the rest of all steps.

3- Expand R 32 bits to 48 bits to fit the subkey by preform Expansion permutation(E) as the following:


4- Preform Exclusive-OR between the subkey and Expansion Permutation (E) on R .
     E(\({R}_{i}\)-1)⊕ \({K}_{i}\).

5- The result of E(\({R}_{i}\)-1)⊕ \({K}_{i}\) pass through a substitution function and produces 32 bits output

Substitution Function :


Substitution Function is rolled by S-Box , S-Box consists of 8 boxes each of which accepts 6 bits as input and produces 4 bits output by the following:


A- Break the result of E(\({R}_{i}\)-1)⊕ \({K}_{i}\) into 8 blocks each contain 6 bits , These blocks are numbered from 1 to 8.
B- Each block will perform a substitution with S-Box with the same number by the following roles :



A- The first and the last bits of each block together as 2 bit value to indicate the number of row in the same number S-Box.
B- The middle four bits of each block together as-bit value to indicate the number of column in the same number S-Box.
C- The decimal value which selected by the row and the column converted to-bit value in all S-Boxes.

For Example :

Suppose the first 6 bits of the result of E(\({R}_{i}\)-1)⊕ \({K}_{i}\) = 010101.
So, the input to \({S}_{1}\) = 010101.
The row value = 0 1 = 1 (decimal).
The column value = 1010 = 10 (decimal).
The decimal value will be 12 = 1100 (4-bit value).

D- Combine results of each S-Box together 32 bits.

6- The result of the substitution operation (output of S-Boxes) passes through a Permutation Function (P).


At this point the function F is finished.

7- Perform Exclusive-OR between the output of the Permutation Function(P) and \({L}_{i}-1\)  , and then put the result in \({R}_{i}\) , and put \({R}_{i}-1\) in\({L}_{i}\).

The overall formulas for DES Encryption Algorithm.
\({L}_{i}\) = \({R}_{i}-1\).
\({R}_{i}\) = \({L}_{i}-1\) ⊕ F(\({R}_{i}-1\),\({K}_{i}\)).


8- Perform 32-bit swap on the result of the final round , then perform Inverse Initial Permutation(\({IP}^{-1}\)) on the swapped data to produces the ciphertext 64 bits.


Decryption Algorithm :

The inputs to decryption algorithm are ciphertext and subkey \({K}_{i}\) but in reverse order, start with \({K}_{n}\) then \({K}_{(n-1)}\) and so on until \({K}_{1}\) in the last round.

Note: You can use DES-Calculator https://github.com/Hamza-Megahed/des-calculator to study each round in detail.

1/26/2015

cryptography6

Cryptography 6

Block Cipher

Block cipher is an encryption method which the encryption algorithm operates on a plaintext block of n bits and produces a block of n bits ciphertext.
Block Cipher has \({2}^{n}\) possible different plaintext block to encrypt.

Nonsingular Transformation:

Nonsingular Transformation mean the encryption algorithm must be reversible (Nonsingular) to decrypt the ciphertext into the original plaintext.
The ciphertext must be unique for each plaintext block.

Example:

Encryption block cipher with a plaintext block length n=4 bits and ciphertext, with \({2}^{4}=16\) possible input states

plaintext | Ciphertext    
0000         0101
0001         0111
0010         1001
0011         0000
0100         1100
0101         0110
0110         1010
0111         0011
1000         1011
1001         1000
1010         0010
1011         1111
1100         1110
1101         0001
1110         0100
1111         1101

This example has 16 possible input states, with a Nonsingular transformation as you can see in the next table

Ciphertext  |  Plaintext
0000            0011
0001            1101
0010            1010
0011            0111
0100            1110
0101            0000
0110            0101
0111            0001
1000            1001
1001            0010
1010            0110
1011            1000
1100            0100
1101            1111
1110            1100
1111            1011

As we can see this algorithm is reversible (Nonsingular).

There is a problem with a small block size n that this system is vulnerable to statistical analysis, but if n is large enough so the statistical analysis will be much harder.
Also it is not practical to establish a large enough reversible substitution cipher (The ideal block cipher), the solution of this problem is Feistel Cipher.

Feistel Cipher:

Feistel proposed that we can approximate the ideal block cipher system for large n ,built up by components that are easily realizable, which is the execution of 2 or more simple cipher in sequence and the result is a strong encryption.
The required form this approach is to develop a block cipher with a key length = k bits, and a block length = n bits with a total possible transformation = \({2}^{k}\) rather than \({2}^{n}\).

Feistel Structure:

Feistel Cipher consists of a number of identical rounds of processing, and in each round a substitution is preformed on one half of data being processed followed by a permutation that make interchange the two halves.
The original key is expanded so that a different key is used for each round.

Feistel Encryption Algorithm:

Feistel encryption algorithm(at the left hand side) , the inputs to encryption algorithm are plaintext block of length 2w bits, and key K.
The plaintext is divided into two halves \({L}_{o}\) and \({R}_{o}\), passes through n rounds of processing, each round i has inputs \({L}_{i}-1\) and \({R}_{i}-1\), and then combined to produce the ciphertext block.
The subkey \({K}_{i}\) is derived from the overall \(K\), \({K}_{i}\) is different from \(K\) and from each other.

Feistel Cipher actually performs two operations

1- A substitution is performed on the left half of data by applying a round function F to the right half of data, then by doing XOR the output of round function F with the left half of data.
The round function F has the same structure every round but there is a change in parameter subkey \({K}_{i}\) for each round.
2- A permutation is performed that consists of interchange on the two halves of data.
Feistel Cipher structure is form of substitution permutation network (SPN).

Feistel Decryption Algorithm:

Feistel Decryption Algorithm(at the right hand side), the inputs to decryption algorithm are ciphertext and subkey \({K}_{i}\) but in reverse order, start with \({K}_{n}\) then \({K}_{n}-1\) and so on until \({K}_{1}\) in the last round.

Note #1: At every round the value of encryption algorithm is equal to the corresponding value(n-ith) of decryption algorithm, but the two halves are swapped.

For example :

For a system with 16 rounds, the  value of 5th round in encryption algorithm is equal to the value of 12th round of decryption algorithm, but L and R are swapped.

Note #2: The round function F does not required to be a reversible function.

Feistel Cipher parameters and design features:

1- Block size: Large block size mean greater security but reduced encryption and decryption speed.
2- Key size: Large key size mean greater security but may also reduced the encryption and decryption speed.
3- Number of rounds: Increasing security can be achieved by increasing the number of rounds.
4- Round Function F:  Increasing the complexity of round function F increasing the resistance to cryptanalysis.
5- Subkey generation algorithm: Increasing of complexity here also increasing the resistance to cryptanalysis.