# A Classical Introduction To Cryptography Computer Science Essay

**Published:** **Last Edited:**

This essay has been submitted by a student. This is not an example of the work written by our professional essay writers.

Serge Vaudenay, in his book "A classical introduction to cryptography", writes: Cryptography is the science of information and communication security. Cryptography is the science of secret codes, enabling the confidentiality of communication through an insecure channel. Cryptography protects against unauthorized parties and intruders by preventing unauthorized alteration to the message. It uses a cryptographic system to convert a plain text into cipher text, during this transformation most of the time a key is used. A very simplistic example of cryptography is famous ROTATION 13(abbreviated as ROT13), It is a Caser-cipher that obscures text by replacing each letter with the letter 13 places down in the alphabet. It is easy to encrypt message to cipher text and decrypt cipher text back to original message, since our alphabets have 26 characters.

The signs of encryption methods are found way back to 4000 years ago but that are considered more as an ancient art. An encryption evolved, was used to send messages to hostile environment of war, crises and for negotiation processes between conflicting group of people. Through history, individuals and governments have worked to protect the messages by encrypting them. As time went, encryption methods used mathematical tools, algorithms and devices that used them increased there complexity were continually introduced and cryptography became an integrated part of computing world.

There are many cryptographic changes undergone through history with advancement in technology. The method of cryptography began with a person carving messages on wood or stone, this carved message is then passed to the intended individual who had necessary means to decipher the message. The messages that are carved on materials at that time is now being inserted into streams of binary code that passes through network wires, internet communication paths and airwaves. The stream of bits is shown in fig.1

Fig. 1 stream of bits passing through network wire

In past the transmission mechanism was performed by messengers and encryption himself protects the message in case the messenger is captured. But now a days, the transmission mechanism is changed to packets carrying 1's and 0's passing through network cables and airwaves. The messages are still encrypted in case an intruder captures the transmission mechanism (packets) as they travel through along their paths.

## 1.2 History of cryptography

Roots of cryptography is found way back around 2000 B.C. in Egypt when hieroglyphics were used to tell the story of the life of the deceased. This method was not used to hide the message at that time, but it was used to make them seem more noble, ceremonial and majestic.

In the Hebrew cryptographic method, the alphabet is flipped so that each letter is the original alphabet is mapped to a different letter in the flipped alphabet. This encryption method is called as ATBASH. Example of encryption key used in the atbash encryption scheme is as follows;

For example, the word "CRYPTOGRAPHY" is encrypted to "XIBKGLTIZKSB".

This is a type of substitution cipher, in which one character is replaced with another character. This substitution cipher is referred to as a MonoAlphabetic substitution because it uses only one alphabet. Many of other ciphers use multiple alphabets at a time.

Around 400 B.C., Spartans used a method of encrypting information known as Scytale cipher, in which message is written on a sheet of papyrus and it was wrapped on a staff. This method looks like a piece of paper wrapped over a stick or wooden rod. The sent was only readable if it was rewrapped around the correct size of staff. By selecting staff of correct size, the letters matches correctly. When the papyrus removed from staff, the written appeared as just a bunch of random characters.

The method was used by Greek government to instruct the soldiers on strategic moves and to provide military directives.

Fig. 2 The scytale used by Spartans to decipher the encrypted messages

In history, Julius Caesar also developed a simple method of shifting alphabets, similar to Atbash scheme. The scheme introduced by him is known as Caesar Cipher, is a substitution cipher substitute's one piece of information with another, which is frequently done by offsetting letters of alphabet. This is an example of symmetric cryptography. In this algorithm is to offset the alphabet and key is the number of characters to offset it. For example, if we encode the word "PROJECT" using Caesar's key value of 3, we offset the alphabet so that the 3rd letter down begins the alphabet. So starting at

On sliding everything up by 3, we get above sequence where, A=D, B=E, C=F and so on. By using this scheme, the plain text, "PROJECT" is encrypted to "SURMHFW". Now if we want someone to read the cipher text, then we have to tell him that the key is 3.

During World War 2, tactical communication was possible with mechanical and electromechanical technology. This communication was possible with telegraphic and radio communication. The rotor cipher machine which provided complexity that was difficult to break, substitute's letters using different rotors. The advancement of this rotor cipher led to a famous Enigma machine, having 3 rotors, a plug board and a reflecting rotor. Due to breaking of its security, the submarine forces were defeated. The cryptography has been a matter of concern of the intelligence collecting agencies and agencies of law enforcing. Because of its facilitation of privacy, and the diminution of privacy attendant on its prohibition, cryptography is also of considerable interest to civil rights supporters.

## 1.3 Encryption and Decryption

The data that is easily readable and understood without any special measures is called a plain text or a clear text. The method used to convert plain text in such a way to hide its substance is called Encryption. Encrypting plain text results in unreadable gibberish called cipher text. The encryption procedure is used to ensure that the information is kept hidden from anyone from whom it is not intended, even those who can access the hidden data. And the process to revert cipher text back to original plain text is called Decryption.

Fig. 3 Encryption and Decryption process

A mathematical function is used for encryption and decryption processes called as cryptographic algorithm or cipher. This algorithm works to encrypt the plain text, working in combination with key-word, number or phrases. The security to encrypted data depends on the strength of cryptographic algorithm and the secrecy of the key.

There are two types of encryption: symmetric key encryption and public (asymmetric) key encryption. Symmetric key and public key encryption are used, often in conjunction, to provide a variety of security functions for network and information security.

## 1.3.1 Symmetric key encryption

In convention cryptography, also known as symmetric key or secret key encryption, only one key is used both for encryption and decryption. This key is called secret key because it is kept as a shared secret between the sender and receiver of information. Otherwise, the encrypted information's confidentiality is compromised.

Fig.4 Symmetric key encryption and decryption process

Symmetric key defines an equation which gives the number of key required by ' n ' number of users. The equation is given as:

No. of keys required = n* (n-1)/2

For example, if there are 1000 users then the number of key required will be 4,99,500 keys.

Symmetric key encryption is much faster than public key encryption, often by 100 to 1,000 times. This is because public key encryption applies high computational load on processor than symmetric key encryption. The symmetric key encryption method is generally applied on secrecy of information for bulk encryption and decryption.

Symmetric keys are commonly used by security protocols as session keys for confidential online communications. For example, the Transport Layer Security (TLS) and Internet Protocol security protocols use symmetric session keys with standard encryption algorithms to encrypt and decrypt confidential communications between parties. Different session keys are used for each confidential communication session and session keys are sometimes renewed at specified intervals.

Symmetric keys also are commonly used by technologies that provide bulk encryption of persistent data, such as e-mail messages and document files. For example, Secure/Multipurpose Internet Mail extensions (S/MIME) use symmetric keys to encrypt messages for confidential mail, and Encrypting File System (EFS) uses symmetric keys to encrypt files for confidentiality. Cryptography-based security technologies use a variety of symmetric key encryption algorithms to provide confidentiality. For more information about the specific encryption algorithms that are used by security technologies.

## 1.3.2 Asymmetric (public) key encryption

The concept of public key encryption was introduced by Whitefield Diffie and Martin Hellman in 1975. In public key encryption, asymmetric scheme is used that has a pair of keys to encrypt and decrypt the information. Under this scheme, public key is use to encrypt the data and a corresponding private key is used to decrypt that encrypted data.

In this scheme, public key is published to the world while private key is kept secret. Anyone with private key can encrypt the message and can send, but only recipient having private key can decrypt the coded message and can access that original information. It is not computationally feasible to deduce the private key from public key. Anyone having public key can encrypt information but they are not allowed to decrypt it. This decryption can only be done by the person having private key.

Fig.5 Public key encryption and decryption process

The main benefit of public key encryption is that it allows unknown people do not preexisting security arrangement can exchange messages securely. By using this method, need for sender and receiver to share secret keys via some secure channel is eliminated, all communication involves only public keys and no private key is ever transmitted or shared.

Some of the public key encryption examples are Elgamel( after inventor Taher Elgamel), RSA( after Ron rivest,Adi Shamir and Leonard Adleman), Diffie- Hellman( after Whitefield Diffie and Martin Hellman)and DSA, the digital signature algorithm(after David Kravitz).

The conventional cryptography was once the only available means for relying secret information, the expense to security channels and key distribution relegated its use only to those who could afford it, like government and large banks. Public key encryption was revolutionized by providing strong cryptography to adult masses.

## 1.3 Cryptosystem

Definition: A system created through hardware components or by program code in an application, capable of providing encryption and decryption task is called as cryptosystem.

The complexity of the system depends on how simple or complicated the process is used for encryption process. In encryption system most of the algorithms are complex mathematical formulas that are applied to the plain text in a fixed sequence. These encryption methods used are secret value called a KEY (a long string of bits), which takes parts with algorithm to encrypt and decrypt the message, as shown in fig. 6.

Fig. 6 Key is provided to algorithm and result is applied to the message, which ends up in cipher

There are 2 types of key based algorithms: symmetric key and asymmetric key based algorithms, also known as private key and public key algorithms respectively. Single key algorithm communicates with each other only after sender and receiver agrees on the key. Security of such algorithms depends on the key secrecy. Encryption and decryption of asymmetric algorithm is denoted by;

Ek (P) =C, Dk(C) =P

In which,

DK (EK (X)) =EK (DK(X)) = X (Plaintext)

Here, 'EK' is encryption with key 'k'; 'DK' is decryption with key 'k'; 'C' is the cipher text and 'P' is the message.

Symmetric key algorithms can also be divided into two more categories; first is stream cipher, it works on single bit at a time on the plain text. And when a group of bits called blocks operate on plain text algorithm then it is called as block cipher.

Fig.7 Model of conventional cryptosystem

## 1.4 Motivation

Our goal is to support high-bandwidth cryptography in the context of an embedded network processing element, such as will be necessary for high-end routers/gateways or SAN (storage area network) elements in the near future. The requirements here are high bandwidth (2 GB/sec-10GB/sec), low cost and low power.

In addition, it is critical that round-key generation (a central component of both AES) performed on the fly because the storage Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. To copy otherwise, to republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee.

## Organization of this Report

The project report consists of ten chapters, Appendix and References. The framework for the thesis is described as follows:

Chapter 1: Provides details on NIST's approach to making its selection, and discusses some of the more critical issues evaluating the algorithms.

Chapter 2: Provides the Literature Survey of Block Ciphers.

Chapter 3: Explains the AES features in detail. This chapter includes description of the implementation of AES.

Chapter 4: Presents the various factors and analysis results that were taken into consideration during the algorithms' evaluation by NIST.

Chapter 5: Summarizes the intellectual property of AES process.

Chapter 6: Candidate algorithm profiles summarize the Operational info. that NIST accrued for each Process, based on the results summarized.

Chapter 7: Takes the information from the algorithm profiles and draws comparisons and contrasts, in terms of the advantages and disadvantages identified for each algorithm.

Chapter 8: Gives the Hardware implementation specifications for the Basic Architecture, Design Methodologies and Goals of the project.

Chapter 9: Deals with the HDL Entry, synthesis and implementation of the VHDL and FPGA Design Flow.

Chapter 10: This includes test results and discussion, which provides description of the encryption and decryption process followed for effective validation.

Chapter 11: Includes the summary of the project and conclusions drawn from the activity. It also briefly describes the future scope of the project.

## Appendix & Glossary

Reference includes the list of references.

## 1.6 Project Objective

AES is a symmetric block cipher that is approved standard for a wide range of cryptographic application. AES supports a block length of 128 bits and can have key length of 128, 192 and 256 bits. The project aim is to design a n FPGA implementation OF RIJINDEAL AES algorithm The design is 128 bits key and 128 bit data block implementation of the algorithm. The design includes on the fly key scheduler, this implementation is done using VHDL at algorithmic level using bottom-up methodology. The modules are simulated with standard test vector using modelsim and active VHDL tool the design is synthesized using Xilinx ISE7.1i synthesis tool.

## 1.7 Problem Statement

Design AES cipher VHDL module

Design AES Decipher VHDL Module

Test AES top level module with standard test vector provided by FIPS197

Implementation on SPARTAN II @ FPGA.

CHAPTER -2

## LITERATURE SURVEY

## 2.1 Type of cipher algorithm

There are two types of symmetric key algorithms: stream cipher algorithm and block cipher algorithm. Stream cipher works on 1 bit or byte at a single time while block cipher works on block of plain text or cipher text.

## 2.1.1 Block cipher

This type of block cipher is used for encryption and decryption of data, in which the message is divided into blocks of bits. During encryption and decryption process, blocks of bits are put through substitution, transposition and mathematical functions. The algorithm used, decides the order of these functions which take place to process the secret message.

Generally, the Boolean transformation of the block ciphers is divided into 3 layers namely substitution, diffusion and key mixing. The three layers create confusion, and diffusion properties of a cipher. Different key values being used create confusion, as the key value is not known by the intruder. The diffusion process is performed by placing the bits in plain text through different functions to disperse them through the algorithm.

Following is the figure which shows a block cipher, having 16 inputs and each input represent a bit. It has 2 layers of 4-bit s-boxes (substitution boxes), where each s-box has a lookup table. By using this lookup table bits are moved around and permuted. The key being used in the encryption process decides which s-box is to be used and in which order.

In the following fig. 7, key decides which s-box is to be used, which converts plain text from readable form to encrypted unreadable cipher text. Every s-box has different function, mathematical formulas and different methods to be performed in each particular bit. This is very simple example. Generally, block cipher works with 64 bits blocks and more number of s-boxes are used. The size of key may determine the number of transformations.

Fig.8 Block cipher algorithm

## 2.1.2 Stream cipher

A stream cipher individually performs mathematical operations on the message as a stream of bits or bytes. During encryption process, the bit or byte of plain text are converted into bit or byte of cipher text. Stream cipher is not suitable for hardware implementation because this cipher encrypts and decrypt one bit at a time.

Fig. 9 The stream of bits is XORed with plain text

In stream cipher, key stream generator is used, that generates a stream of bits. These generated bits are XORed with the bits of the plain text. The key in the stream cipher provides the randomness to the key stream applied to the plain text. The key provides random values that are input of the stream cipher; this ensures the randomness of the key stream data.

Fig.10 key stream and key needed for encryption and decryption

## 2.2 Iterative and iterated block cipher

In iterative block ciphers, the transformations are iterated many times. Each iteration is called a round and the corresponding transformation is called round transformation. These round transformation are key dependent.

Each transformation may or may not be unique and different from the cipher's other round transformations. Each round will have a different key and the round keys are compared from cipher key. The number of rounds in iterative block cipher depends upon the desired level of security. In many cases, round increment increases the security offered by cipher, but in some cases it is not practical to implement number of rounds required to achieve security.

Feistel cipher is a type of iterated cipher by which cipher text is calculated from plain text by repeatedly applying some transformation function. Feistel cipher is also called as DES-like cipher.

Fig. 11 Feistel cipher network

In above shown Feistel cipher, the text is splitted into 2 halves. The first half is applied to the round function 'F' using a sub key and the output of function is XORed with the other half. After that 2 halves are swapped. Remaining rounds also follow the same method except the last round where swapping is not done.

Feistel cipher has encryption and decryption which are structurally identical. Sub keys which are used during encryption are taken in reverse order during decryption at each round.

## 2.4 Key altering cipher

In this type of cipher, the round transformation has no involvement of the key. The cipher is considered as an alternated application of the round transformation and the key addition. Usually, the key addition is the simple XOR operation.

Fig. 12 XOR operation of key alternating cipher

Block cipher that alternates key addition with key independent rounds are key alternating ciphers. This key alternating ciphers is easy to implement, sometimes implemented with only OR operations and lookup tables.

Chapter -3

## Advanced Encryption Algorithm

## 3.1 Origin of Advanced Encryption Standard

The advanced encryption standard, abbreviated as AES, was the winner of the contest held in 1997, by US Government. The requirements of new encryption standard was felt when the Data Encryption Standard was found too weak because having small size and technological advancement of the power of the processor. In 1998, fifteen applications were accepted and out of these fifteen only five of them were finalized in1999. Next year in October 2000, AES was declared the winner. This AES was a modified version of the Rijndael.

AES is based on a design principle known as a Substitution permutation network, it is fast in both software and hardware, is relatively easy to implement, and requires little memory. Unlike its predecessor DES, AES does not use a Feistel network. Assuming one byte equals 8 bits, the fixed block size of 128 bits is 128 ÷ 8 = 16 bytes. AES operates on a 4Ã-4 array of bytes, termed the state (versions of Rijndael with a larger block size have additional columns in the state). Most AES calculations are done in a special finite field.

The AES cipher is specified as a number of repetitions of transformation rounds that convert the input plain-text into the final output of cipher-text. Each round consists of several processing steps, including one that depends on the encryption key. A set of reverse rounds are applied to transform cipher-text back into the original plain-text using the same encryption key.

## AES ROUND

SubBytes

Function

Round

Input State

SubByte

Output

State

ShiftRow

Function

MixColumn

Function

AddRoundKey

Function

Round

Input

(State)

Din_

Valid

Round

Key

(State)

Clk

Dout_

Valid

Round

Output

(State)

## AES LAST ROUND

SubBytes

Function

Round

Input State

SubByte

Output

State

ShiftRow

Function

AddRoundKey

Function

DFF

(128)

DFF

Round

Input

(State)

Din_

Valid

Round

Key

(State)

Clk

DFF

(128)

DFF

Dout_

Valid

Round

Output

(State)

Fig. 13 Architecture of AES

Rijndael is a block cipher which works on a fixed- length group of bits. This group of bits is called as Blocks. Rijndael is based on the name of Belgium inventors, Vincent Rijmen and Joan Daemen. Usually this Rijndael, take an input block of 128 bit size and gives corresponding output block of the same size. One more input is required for transformation called as Secret key. This secret key used can be of any size, which depends on the type of cipher used. In AES key size used can be of 128, 192 or 256 bit size.

Fig.14 AES Encryption & Decryption

The earlier encryption standard used was based on Feistel network but the AES is a substitution- permutation based network. In AES a series of mathematical operation are used which includes substitution (S-boxes) and permutation (P-boxes). These mathematical operations imply that each output bit depends on each input bit.

Fig.15 AES rounds

## 3.2 Description of AES Algorithm

AES is an iterated block cipher having 128 bit block size and 128 bit key size. The different rounds of transformation are performed of the intermediate results, called as STATE, which is a rectangular array. The block size is of 128 bits (16 bytes). So, the array dimensions will be 4X4. In Rijndael, the blocks are variable, the size of rows is also fixed to 4 and the number of columns varies. The number of columns, denoted by Nb, is Block size divided by 32. The number of columns of cipher key, denoted by Nk, is key length divided by 32.

## A state:

## -----------------------------

## | S0,0 | S0,1 | S0,2 | S0,3 |

## | S1,0 | S1,1 | S1,2 | S1,3 |

## | S2,0 | S2,1 | S2,2 | S2,3|

## | S3,0 | S3,1 | S3,2 | S3,3 |

## A key:

## -----------------------------

## | k0,0 | k0,1 | k0,2 | k0,3 |

## | k1,0 | k1,1 | k1,2 | k1,3 |

## | k2,0 | k2,1 | k2,2 | k2,3 |

## | k3,0 | k3,1 | k3,2 | k3,3 |

The input bytes of cipher are copied the state in the order S0,0, S1,0, S2,0 ----- and the bytes of the cipher key are copied in the key array in the order k0,1, k1,0, k2,0 ------. At the cipher operations end, the output is fetched from the state by taking the bytes of state in the same order. A key of 128 bits has 10 rounds of operation, 192 bits has 12 rounds of operation and 256 bits have 14 operational rounds.

## Key size

## Number of rounds

128

10

192

12

256

14

Some of the operations performed at each round on the state are;

Sub bytes: using S-box, every byte of state is replaced by another byte.

Shift row: every row in 4X4 array is circularly shifted a certain amount to the left.

Mix column: a linear transformation is performed on each column of state.

Add round key: at each round, different round key derived from the Rijndael key schedule, is combined with each byte of the state.

## 3.2 Rijndael- a short definition

Rijndael is a key alternating block cipher given by,

B[t] = f (Ti)*p (i)*f (Ti-1)*p (i-1) ----------------f (T1)*p (1)*f (0)

Where, f (di) is the ith round key addition and p (i) is the round transformation.

For experimental purpose of this project, 128-bit block and 128-bit key size is used.

## 3.2.1 Rijndael key schedule

For expansion of short key into a larger key Rijndael key schedule is used, its parts are used during different key iterations. Every key size is expanded to different size.

128 bit key is expanded to 176 byte key.

192 bit key is expanded to 208 byte key.

256 bit key is expanded to 240 byte key.

The relation between cipher key size, number of rounds and expanded key size is given by;

## Expanded key size= (nbrRounds + 1) * blocks size

Example, for 128 bit key, there is 1 initial add round key operation plus there 10 rounds has a new 16 byte key. So, we need 10+1 round keys for 16 byte, i.e. 176 byte.

Expanded key size = (nbrRounds +1) * Block size

= (10 + 1) * 16

= 11 * 16

Expanded key size = 176 bytes

The Rijndael key schedule is made of iterations works on 4-byte words. These iterations are of key schedule core, which uses number of operations like RCON, Rotate and S-box.

Rotate operation: In this operation, a 4-byte word is cyclically shifted one byte to the left.

Let us take a 4-byte word,

4a 3b 2c 2d

After circular left shift, the word will be;

3b 2c 2d 4a

Rcon: this section is highly mathematical and the values of Rcon are precalculated values of

Rcon lies with lookup table and these values result in simple substitution.

S-box: the key schedule uses the same S-box substitution as the main

algorithm body.

## 3.3 Rijndael- An Introduction

## 3.3.1 General Terminologies and concepts:

The state is an intermediate result of the cipher. The input of one stage is mapped to a state (called initial state) and the output is mapped from the final state of the last state. A state is a 2- dimensional matrix. It has fixed, 4 rows and variable columns, Nb. The number of columns varies according to the block size input.

The number of columns, Nb , is equal to the block size divided by 32. So, if block size is 128 bits then number of column will be 4, if block size is 192 bits(20 bytes) then, number of columns will be 192/32=5 and if block size is 256 bits then, the number of columns will be 256/32=6. The key is also viewed as a state. The plain text having 16, 20 or 24 bytes is denoted by P0, P1, P2 --------P. Similarly, the cipher is also denoted as C0, C1, C2 -------C. And state is denoted by ai,j , 0<i<4, 0<j<Nb. where ai,j denotes the number of bytes in row 'i' and column 'j'. The input bytes po,p1----- p4 are mapped to the state bytes in the order a0,0, a1,0, a2,0------.

Block size(in bits/bytes)

Number of columns(Nb)

128/16

4

192/20

5

256/24

6

## 3.3.2 Algebric nature of Rijndael

Rijndael defines several operations at byte level, with bytes representing elements in the finite field GF (28) called as Galois Field. Some of the operations are also defined in terms of 4-byte words.

The field GF (28) : finite field elements can be represented in different ways. All the representations of GF (28) are isomorphic because for any of the prime powers there is a single finite field. The coefficients [0,1]of a byte 'b' consisting bits b7, b6, b5, b4, b3, b2, b1, b0 is considered to be a polynomial;

b7x7+b6x6+b5x5+b4x4+b3x3+b2x2+b1x1+b0x0

Example: The byte with hexadecimal value '53' (0101 0011 in binary) is written in polynomial form as;

Binary: 0101 0011

Hexadecimal: x6+x4+x+1

There are two basic operations required by the algorithm, addition and multiplication of polynomials.

Addition: In polynomial representation, the addition of two elements is the polynomial corresponding coefficients given by sum modulo 2 (i.e. 1+1=0).

Example:

Hexadecimal: 2E + 63 = 4D

Polynomial: (x5+x3+x2+x) + (x6+x5+x+1) = (x6+x3+x2+1)

Binary: 0010 1110 + 0110 0011 = 0100 1101

From the above example, we can conclude that the addition corresponds to simple Bitwise XOR operation (denoted by ) at the byte level.

Multiplication: In multiplication of 2 polynomials, the output between the two has to be reduced to a polynomial of degree less than 8, so as to represent it in GF (28) form. The irreducible polynomial is one if it has no divisors other than 1 and itself. In Rijndael, this polynomial is given as;

m(x) = x8 + x4 + x3 + x + 1 polynomial form

or '11B' Hexadecimal form

The polynomial product in GF(28) is not simple as addition or subtraction.

Example for polynomial product is given as;

[2E] * [63] = [B0] hexadecimal

And in polynomial form:

(x5+x3+x2+x) * (x6+x5+x+1)

(x5+x3+x2+x) * x6 = x11 + x9 +x8+x7

(x5+x3+x2+x) * x5 = x10 + x8+x7+x6

(x5+x3+x2+x) * x = x6 + x4+x3+x2

(x5+x3+x2+x) * 1 = x5 + x3+x2+x

Addition = x11 +x10+x9 + x5+x4 + x

Intermediate result= x11 +x10+x9+x5+x4+x

So, multiplication of two polynomials is another polynomial but its degree is 11 which cannot be represented in a byte. Therefore, we have to take modulo m(x), which we can represent in a byte.

## 3.3.3 Rijndael components

AddRoundkey [S0=S+K], this component has a state 'S' as an input and this input is XORed with key 'K', to give 'S0'. All the rounds of Rijndael can have same or different key. This AddRoundKey operation can be represented in the form of addition of matrices.

Sub bytes, this component are similar to substitution in substitution permutation network (SPN) cipher. Substitution in SPN does not have linearity or algebraic definition, whereas substitution in Rijndael satisfies algebra.

Linearity exists if and only if F (A+B) =F (A) + F (B). By using this property, it can be easily verified that the components are linear or not. The non-linearity property is a strong cryptographic primitive. The other desirable properties stated are invariability, minimization of the largest non-trivial correlation between linear combinations of input bits and linear combination of output bits, minimization of the largest non-trivial value in the EX-OR table, complexity of its algebraic expression in GF(28) and simplicity of description.

Block cipher has to be secure against the attacks that are known, most of these criteria are necessary, especially in the linear and differential cryptanalysis.

Fig.16 substitution operation in GF (28)

The S-box functionality depends on the operations in Galois field (28), also called as finite field. The above figure fig.16 shows substitution operation in finite field. This substitution has 2 sub components, multiplicative inverse and affine transformation.

The S-box table bytes are input. These input bytes are converted into field and multiplicative inverse of these fields is calculated. This multiplicative inverse is very simple transformation ad it can be algebraically attacked, like interpolation attack. So, multiplicative inverse is followed by affine transformation, to make sub bytes a complex algebraic expression.

Chapter -4

## NOTATION AND CONVENTION

## 4.1 Input and output

In AES algorithm, the input and output is a binary sequence ( 0's and 1's) of 128 bits. The input to the AES algorithm is a plain text which is converted into a bit sequence of length multiple of 128, which is further divided into blocks of length 128. Another very important input to AES algorithm is its key also known as cipher key, which is a sequence of 128, 192 and 256 bits. Any other input, output and cipher key lengths are permitted by this AES algorithm. In this sequence, the bit number starts with 0 and ends up at one led then the sequence length (block length or key length). The index of the bit is represented by 'i' its range lies between;

0< i < 128, for block length 128 bits

0< i < 192, for block length 192 bits

0< i < 256, for block length 256 bits

## 4.2 Bytes

It is a single entity having 8-bit sequence.it is the most fundamental unit of processing in the AES algorithm. The input, output and cipher key bit sequences are processed as array of bytes. The input sequence of 0's and 1's is divided into group of eight bits to form byte array. The input, output and cipher key arrays are denoted by an or a[n]. The value of 'n' depends on the key length. The range of 'n' is given in tabular for different key lengths.

Key length( in bits)

Range of 'n'

128

0< n<16

192

0< n<24

256

0< n<32

The byte value in AES algorithm is value of individual bit value, the bit values can be 0 or 1 and the order of representation is;

{D7 +D6 +D5 +D4 +D3 +D2 +D1 +D0}

The bytes in AES algorithm is represented in Galois finite field, in the form of a polynomial given as; 7

D7x7 +D6x6 +D5x5 +D4x4 +D3x3 +D2x2 +D1x1 +D0 = âˆ‘ Dpxp

p=0

For example;

{1010 0110} is represented in the polynomial form as x7 +x5 +x2 +x.

The above represented byte values are in the binary form but it is more convenient to denote these byte values in hexadecimal form. To do this we have to make pair of 4 bits, denoted by single hexadecimal character.

## Bit pattern

## Character

## Bit pattern

## Character

## Bit pattern

## Character

## Bit pattern

## Character

0000

0

0100

4

1000

8

1100

C

0001

1

0101

5

1001

9

1101

D

0010

2

0110

6

1010

A

1110

E

0011

3

0111

7

1011

B

1111

F

Fig: 9 Hexadecimal representations of bit patterns

For example, binary number {1011 0110} is denoted by {B6} in hexadecimal notation. Some finite field operations involves an additional bit {D8} to the left most end of the 8th bit of byte. When this extra {D8} bit is present, it is represented by {01}, fixed at the left of the D7th bit.

For example, this extra bit is represented as {01} {B6} as a 9-bit sequence.

## 4.3 Array of bytes

In AES algorithm, the input pattern can be of 128, 192 and 256 bit. For AES-128, the input sequence can be represented in the form in0, in1, in2, -------- in127. And as discussed earlier, a byte is a group of 8- bits, represented in the form an array as,

Byte0 = {in0, in1, in2 ------- in7}

Byte1 = {in8, in9, in10 ------ in15}

## -

## -

## -

## -

Byte15 = {in120, in121, in122 ------ in127}

So, we can write input in the form of bytes ranging from Byte0 to Byte15. This group of bytes from Byte0 to Byte15 is called as array of bytes, which can be written in general form as,

Bytet = { in8t, in8t+1, in8t+2, ---------- in8t+7}

Where, range of 't' lies between 0<t<16.

Indices for bytes and bits

Above is an example showing the byte designation and numbering within bytes for an input sequence of 128 bits.

## 4.4 State

In AES algorithm, the input sequence in0, in1, in2 ----- in127 is represented in the form of array of bytes is copied into the state array to perform different algorithmic operations. This state is an intermediate cipher on which all operations are done.

This state is a rectangular 2-dimentional array of bytes. The state array has 4 rows, 'r' and number of columns are denoted by 'c'. Each row consists of 'Nb' number of bytes, where 'Nb' is equal to block length divided by 32. Similarly, the cipher key can also be plotted as a rectangular array of 4 rows. In cipher key the number of columns can be denoted by 'NK' and is equal to the key length divided by 32.

So, state array can be denoted by 'S' having 2 indices rows, 'r' and columns, 'c' having range 0< r<4 and 0< c< Nb, respectively.

Fig.17 Example of state (with Nb=8)

Fig.18 Example of key (with Nk=6)

At the beginning of the cipher and inverse cipher, the input- the array of bytes, Byte0, Byte1, Byte2 ----- Byte15 is copied into state array and at the output during the inverse cipher, the final values are copied to the array of bytes out0, out1, out2 ------ out15.

Comparing from last section;

Byte0 = in0, Byte1 = in1, Byte2 = in2------- Byte15 = in15

Fig.19 State array, input and output

So, at the beginning of cipher or inverse cipher the input array, 'In', is copied to state array as,

S[r,c] = In [r + 4c] 0< r<4 , 0< c<Nb

And at the end of the cipher or inverse cipher, the state is copied to the output array 'Out' as,

Out[r + 4c] = S [r,c] 0<r<4 , 0<c<Nb

## 4.5 The state as an array of columns

In Rijndael, there is 'c' number of columns having 4 bytes in each column. These four bytes in each column forms 32- bit words. So, we obtain 4 words from each column can be denoted by W0, W1, W2 and W3. In these words the row number 'r' provides an index for the 4 bytes within each word.

The word is therefore, considered as the 1-dimensional array of column, which are 32-bit in length.

Fig. 20 Four 32 bit words

Therefore, as shown in fig.15, the state can be considered as an array of four words. The four words are:

W0 = [S0,0 , S1,0 , S2,0 , S3,0]

W1 = [S0,1 , S1,1 , S2,1 , S3,1]

W2 = [S0,2 , S1,2 , S2,2 , S3,2]

And W3 = [S0,3 , S1,3 , S2,3 , S3,3]

Chapter - 5

## MATHEMATICAL PRELIMINARIES

## 5.1 Addition

In polynomial addition, the sum of two polynomials is also a polynomial with coefficients that sum modulo 2 of the coefficients of two terms. In polynomial addition, the process is performed by XOR operation, denoted by . The XOR operation is given as,

A

B

A+B

0

0

0

0

1

1

1

0

1

1

1

0

The addition in GF (28)

Consequently, the addition of polynomial is same as subtraction of polynomial. For

2-bytes, (a7, a6, a5, a4, a3, a2, a1, a0) and (b7, b6, b5, b4, b3, b2, b1, b0) we get (c7, c6, c5, c4, c3, c2, c1, c0.

Where, c7 = b7 a7

c6 = b6 a6

## ---

## ---

## ---

c0 = b0 a0

So, we can write, cw = bw aw , where, 'w' is the bit position.

Example,

2E + 63 = 4D hexadecimal

{0010 1110} + {0110 0011} = {0100 1101} binary

And taking in polynomial form;

(x5+x3+x2+x) + (x6+x5+x+1) = (x6+x3+x2+1)

Solving L.H.S., we get

= > (x6 + (11)x5 + x3+x2+ (11) x +1)

= > (x6+x3+x2+1) = R.H.S.

## 5.2 Multiplication

In Galois field(28), multiplication is much complex than finite field addition. It can be done by multiplying the 2 of the polynomials concerned and eliminating like powers of 'x' from the result. Since , both of the polynomial terms are having powers of 'x' up to 7, so, the result will have powers of 'x' up to 14. This result cannot be shown in a single byte. So, to convert this larger size result into presentable form, the result of multiplication of 2 polynomials is modulo an irreducible polynomial of degree 8 i.e. the result is replaced by remainder polynomial after division by 8- bit irreducible polynomial, given by,

m(x) = x8 + x4 + x3 + x + 1

This polynomial has degree 8 and it cannot be written in single byte. So, it can be represented as

1{0001 1011} or {01} {1B}. The multiplication process is given by following example of the product,

[2E] * [63] = [B0] hexadecimal

[2E] = (x5+x3+x2+x)

[63] = (x6+x5+x+1)

And in polynomial form, the multiplication between the 2 is given by:

(x5+x3+x2+x) * (x6+x5+x+1)

(x5+x3+x2+x) * x6 = x11 + x9 +x8+x7

(x5+x3+x2+x) * x5 = x10 + x8+x7+x6

(x5+x3+x2+x) * x = x6 + x4+x3+x2

(x5+x3+x2+x) * 1 = x5 + x3+x2+x

Addition = x11 +x10+x9 + x5+x4 + x

Intermediate result= x11 +x10+x9+x5+x4+x

This intermediate result is now divided by m(x).

x11 +x10+x9 + x5+x4 + x

(x8 + x4 + x3 + x + 1)* x3 = x11 + x7+x6 + x4+x3

Subtracting x10+x9+x7+x6 + x5+ x3 + x

(x8 + x4 + x3 + x + 1)* x2 = x10 + x6 + x5+ x3+x2

Subtracting x9+x7 + x2+ x

(x8 + x4 + x3 + x + 1)* x = x9 + x5+x4+x2+x

Subtracting for

Final remainder x7+ x5+x4 = {1011 0000} = [B0]

This reduction by m(x) ensures that the result is a binary polynomial of power less than 8, hence, can be represented by a byte.

In Galois field, every element except {00} has a multiplicative inverse. The inverse of polynomial 'a' is unique polynomial 'b' such that;

a * b = 1 mod m(x)

this can be calculated by Extended Euclidian Algorithm.

For example, if we take g=x+1= {0000 0011} = 0X03

Then,

GF(28) = {g,g2, -----------g254,g255(g0=1)} U{0}

The product of 2 element,

a= gi and b= gj different from 0x00 is,

a*b = gi * gj

= gi+j

= gi+jmod 255

And inverse of 'a' is 'a-1'given by,

a-1 = (gi)-1

= g-i

= g255-i

So, product and computation of inverse can be performed by search in 255 elements.

## 5.3 Multiplication of 'x' by repeated rows

Let us take a polynomial, which was defined earlier,

7

D7x7 +D6x6 +D5x5 +D4x4 +D3x3 +D2x2 +D1x1 +D0 = âˆ‘ Dpxp

p=0

Multiplying the polynomial by 'x' we get,

7 7

D7x8 +D6x7 +D5x6 +D4x5 +D3x4 +D2x3 +D1x2 +D0x = x*âˆ‘ Dpxp = âˆ‘ Dpxp+1

p=0 p=0

The polynomial 'x' is represented as [0000 0010] in Galois field, which concludes that if we multiply this polynomial with another polynomial increases all its powers of 'x' by 1, which is equivalent to shifting each of the bits up by 1 position so that 'r' moves to position 'r+1'. If MSB is set then prior to this move it will result in an overflow and generates x8th term. In this case, the polynomial m(x) is added to cancel out this extra bit. For example; multiplying [1010 1100] by 'x' will give 1[0101 1000]. This 'overflow', x8 bit is to be removed by adding modular polynomial m(x) = 1[0001 1011]. This addition is the XOR operation which gives the result [0100 0011].

By repeating this operation again and again all the powers of 'x' from 0 to 7 can be multiplied by a finite field element. So, multiplication of 2 elements can be obtained by adding the results for appropriate powers of 'x'. For example; product of 2 finite field elements is:

{57}*{13} = {FE}

Its multiplication procedure is explained in the following table,

p

[57]*xp

+m(x)

[57]*xp

Bit p of [13] ƒ

Result

0

[0101 0111]

[0101 0111]

1 [0101 0111]

[0101 0111]

1

[1010 1110]

[1010 1110]

1 [1010 1110]

[1111 1001]

2

1[0101 1100]

1[0001 1011]

[0100 0111]

0 [0000 0000]

[1111 1001]

3

[1000 1110]

[1000 1110]

0 [0000 0000]

[1111 1001]

4

1[0001 1100]

1[0001 1011]

[0000 0111]

1 [1010 1110]

[1111 1110]

5

[0000 1110]

[0000 1110]

0 [0000 0000]

[1111 1110]

6

[0001 1100]

[0001 1100]

0 [0000 0000]

[1111 1110]

7

[0011 1000]

[0011 1000]

0 [0000 0000]

[1111 1110]

## 5.3 Polynomials with coefficients in Galosis field

Let us take 2 polynomials with coefficients,

A(x) = A3x3 + A2x2 + A1x + A0

And

B(x) = B3x3 + B2x2 + B1x + B0

Each of the polynomial is represented by a byte and can be denoted as a 32-bit word in the form [A3, A2, A1, A0] and [B3, B2, B1, B0] respectively.

Addition : this operation is done by adding the like powers of 'x' of the coefficients of the finite field. This addition corresponds to an XOR operation between the corresponding bytes in each of the words. So,

A(x) + B(x) = Q3x3 + Q2x2 + Q1x + Q0

Where, Q3 = A3 B3

Q2 = A2 B2

Q1 = A1 B1

Q0 = A0 B0

Multiplication: The multiplication between 2 polynomials in Galois field is performed in two steps. In first step, the product is calculated with algebraic expression and like powers is collected to give;

C(x) = A(x) * B(x)

C(x) = (A3x3 + A2x2 + A1x + A0) * (B3x3 + B2x2 + B1x + B0)

C(x) = C6x6 + C5x5 + C4x4 + C3x3 + C2x2 + C1x + C0 ----------------------- (1)

On solving, above equation;

C(x) = (A3 B3) x6 + (A3 B2 A2 B3) x5 + (A3 B1 A2 B2 A1B3) x4

+ (A3 B0 A2 B1 A1 B2 A0 B3) x3 + (A2 B0 A1 B1 A0 B2) x2

+ (A1 B0 A0 B1) x + A0 B0

Comparing this equation with equation (1), we get

C0 = A0 B0

C1 = (A1 B0 A0 B1)

C2 = (A2 B0 A1 B1 A0 B2)

C3 = (A3 B0 A2 B1 A1 B2 A0 B3)

C4 = (A3 B1 A2 B2 A1B3)

C5= (A3 B2 A2 B3)

C6= (A3 B3)

This 6-byte polynomial cannot be represented into 4- byte word. So, 2nd step will be to reduce C(x) modulo a degree 4 polynomial to produce a result of degree less than 4.

In Rijndael, the polynomial used is x4+1 and reduction with this polynomial gives following polynomial coefficients.

D3 = (A3 B0 A2 B1 A1 B2 A0 B3)

D2 = (A2 B0 A1 B1 A0 B2 A3 B3)

D1 = (A1 B0 A0 B1 A3 B2 A2 B3))

D0 = (A0 B0A3 B1 A2 B2 A1B3)

By fixing A(x) polynomial, we can write the above 4 coefficients in matrix form as;

Since, x4+1 is not an irreducible polynomial, all the polynomial multiplications are not invertible. However, Rijndael gives a fixed 4 term polynomial that has inverse, given as

## A(x) = {03}x3 + {01}x2 + {01}x + {02}

## A-1(x) = {0B}x3 + {0D}x2 + {09}x + {0E}

Another polynomial that Rijndael uses has A0=A2= {00} and A1= {01} which is the polynomial 'x'. The above given matrix provides an output word by rotating the input word bytes. This means [B3, B2, B1, B0] is transformed into [B2, B1, B0, B3] with bytes shifting to higher index position and the highest byte wrapping back to the least position.