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