Cryptography plays a key role to protect the data from unauthorized access. Nowaday s various cryptographic algorithms are used. It is not meant of information technology to secure proposed work main target to achieve these tasks and goals. In research study related to any field of science is based on some basic definitions and understandings of some pre vious res ults. Therefore we introduce the basic definition s of Algebra and information security system in this chapter which is important to understand the dissertation of the coming chapters. This chapter is further divided into sections which explain the various concepts comprehensively. Keywords: Algebra, Cryptography , Information Security System, Fundamental Algebraic Concepts, Crypto -Algebra, Analysis on Algebra 1.1 Fundamental Algebraic concepts This section is further divided into many subsections which explained the fundamental algebraic concepts included group, ring, field, vector space, affine space, symmetric group, etc. Further Galois field, substitution boxes and group action are al so expla ined in detail which is most important for our dissertation. Binary operation Definition 1: Let a set 𝑀 ≠ ɸ and ‘𝑔’ be a mapping such that 𝑔: 𝑀 × 𝑀 𝑀 then ‘𝑔’ is called a binary operation if 𝑀 is closed under the operation ‘ 𝑔’. In mathematical notation ; 3 𝑔(𝑝,𝑞)=𝑝𝑔𝑞 Ɐ p , 𝑞∈𝑀 Example 1: “+”addition is a binary operation for the non -empty sets ℤ, ℝ, ℚ and ℂ . These sets are closed under addition . Remark 1 : If we divide one integer to another integer then the result would not be necessary an integer so the division is not a binary operation. Algebraic Structure Definition 2 : A set 𝐵 ≠ ɸ is called an Algebraic structure if it has at least one binary operatio n. Groupoid Definition 3 : A set 𝐴 ≠ ɸ with a binary operation is called groupoid if it is closed under that binary operation. Example 2 : i. (ℝ, +) under addition set of real number s ii. ( ℚ, +) under addition set of rational numbers iii. ( ℂ, +) under addition set of complex numbers Semigroup Definition 4 : A groupoid 𝐴 ≠ ɸ is called semigroup if it satisfies the associative property under the same binary operation. Mathematically, 𝑎*( 𝑏 ∗𝑐) = ( 𝑎* 𝑏) ∗𝑐 Ɐ 𝑎 , 𝑏, 𝑐∈ A Example 3 : ℤ, ℝ, ℚ and ℂ are semigroup under the binary operation multiplication and addition. Remark 2 : ℤ the set of integers is not semigroup under the binary operation division. Monoid Definition 5 : A semigroup (𝑆,*) is called monoid if it has the identity under the same binary operation. Mathematically, 4 s*e = s =e*s Ɐ s ∈ 𝑆 Example 4 : The set of integers, rational, real and complex numbers are monoid under the binary operation “+” and “.” Remark 3: The set of natural number is not monoid under “+” . 1.1.1 Group Definition 6 : If each element in the monoid ( 𝐺,*) has the inverse, then the set is known as a group. It means for Mathematically, 𝑠 ɛ G ⱻ 𝑠′∈ G such that 𝑠*𝑠′= 𝑠′*𝑠 = e Ɐ s ∈ G where e is identity. Example 5: ℝ, ℚ and ℂ are group s under multiplication and addition with identity 1 and 0 respectively. Remark 4 : In the set of integer ℤ each element is not invertible under the binary operation multiplication so ℤ is not a group. Similarly under the binary operation “.” and “+” respectively {1} and {0} are trivial group. Remark 5 : In a group , the identity and inverse of each element are always unique. Subgroup Definition 7: A subset 𝑆 ≠ ɸ of group G with binary operation “*” is known as subgroup if S is also subgroup under the binary operation “*” which has the set G. Example 6 : The set of integer ℤ is subgroup under the binary operation “+” ℝ, ℚ and ℂ . 5 Remark 6 : Every group G has two trivial subgroups {e} and {G} itself. Abelian group Definition 8 : A group G is called an abelian group with binary operation “*” if “*” is commutative. Mathematically, 𝑔1 ∗ 𝑔2 = 𝑔2 ∗ 𝑔1 , Ɐ 𝑔1, 𝑔2∈ G Example 7 : i. ℚ, the rational numbers ii. ℝ, the real numbers iii. ℂ, the complex numbers are the abelian g roup under multiplication. Remark 22 : 𝑀𝒏(ℝ) Matrices having entries from the set of real numbers called the real matrices. It forms the non abelian group under the binary operation multiplication . Cyclic group Definition 9 : If a group G is generated by a single element of G, then G is known as cyclic. I f G is cyclic under addition we represent it mathematically, G = ‹ 𝑔› = {n𝑔: n ∈ ℤ} And if G is cyclic group under multiplication then we write it as, G = ‹ 𝑔› ={𝑔𝑛: n ∈ ℤ} Example 8 : let G be the set of nth root of unity then G is called cyclic group and denoted by G = ‹w› = {1, w, 𝑤2,…,𝑤𝑛−1} where 𝑤𝑛=1 Remark 7 : The order of the cyclic group and its generator are equal and t he subgroup’s order and the element ’s order divide the order of the group. Remark 8 : The set of integer ℤ has two g enerators under addition 1 and -1.So ℤ is infinite cyclic group under addition and the group of prime order is always cyclic. 6 1.1.2 Ring Definition 10 : A set R ≠ ɸ with two binary operation s “+” and “.” is known as a ring if it satisfies the following properties which are given below . i- R is an abelian group under the operation “+ ” ii- R is semigroup under the operation “.” iii- “+” is distributive over “.” Example 9 : The set of integer ℤ is a ring und er the binary operation which is men tioned above . Example 10 : The set of rational numbers ℚ is a ring under th e binary operation which is mentioned above . Example 11 : The set of real numbers ℝ is a rin g under the binary operation which is discussed above . Example 12 : The set of complex numbers ℂ is a ring under the above mentioned binary operation. Example 13 : Similarly 𝑀𝑛 (ℝ), 𝑀𝑛(ℤ), 𝑀𝑛(ℚ), and 𝑀𝑛(ℂ) are the example of rings. Example 14 : ℤ𝑛 and n ℤ are also the example of a ring. Commutative Ring Definition 11 : A ring R is said to be a commutative ring if “.” is commutative. Example 15 : The set of integers form a commutative ring. Example 1 6: ℝ, ℚ and ℂ are the example of commutative ring. Remark 9 : 𝑀𝑛 (ℝ), 𝑀𝑛(ℤ), 𝑀𝑛(ℚ), and 𝑀𝑛(ℂ) are the examples of non–commutative ring. Ring having identity Definition 12 : A ring R is known as a ring with identity if R contains the multiplicative identit y. 7 Mathematically, a.1 =1.a = a, Ɐ a ∈𝑅 Example 17 : (ℤ, +, .) is a ring with identity. Example 18 : (ℚ, +, .) is a ring with identity. Example 19 : (ℝ, +, .) is a ring with identity. Example 20 : (ℂ, +, .) is a ring with identity. Remarks 10 : nℤ where n >1 is a ring without identity. Subring Definition 13 : A subset S ≠ ɸ of a commutative ring R is called a subring of R if it fulfills the following conditions. i- If 𝑟, 𝑡 ∈ S then 𝑟−𝑡 ∈ S ii- If 𝑟, 𝑡 ∈ S then 𝑟𝑡 ∈ S iii- 1 ∈ S Example 21 : ℤ is a subring of ℚ . Example 22 : ℚ is a subring of ℝ. Example 23 : ℝ is a subring of ℂ. Example 24 : nℤ is a subring of ℤ. 1.1.3 Field Definition 14 : A set F which is non empty is known as a field if it satisfies the properties which are given below . i- (𝐹,+) is abelian group . 8 ii- 𝐹 - {0} form a multiplicative group. iii- Distributive la w holds multiplication over addi tion, i.e 𝑝(𝑞+𝑟)=𝑝𝑞+𝑝𝑟 Ɐ 𝑝,𝑞,𝑟∈ 𝐹 Example 25 : ℝ is a field. Example 26 : ℚ is a field. Example 27 : ℂ is a field. Remark 11 : The set ℤ𝑛 = {0, 1, 2, … , 𝑝−1} is a field wh ere 𝑝 is any prime number. In cryptography , we always prefer to choose field having finite elements called fi nite field or Galois field. The total number of elements in the field is known as order of the field. Finite field or Galois Field Definition 15 : A field in which the number of elements is finite , is called finite field or sometimes called Galois field in which we can subtract, add, multiply and invest. If this finite field has p elements then w e write it as 𝐺𝐹(𝑝). Example 28 : ℤ5 = {0, 1, 2, 3, 4} is a finite field having five elements. Remark 12: A real field is an infinite field. Theorem 1 : A finite field having order m occurs if m is a power of a prime. i.e m =𝑝𝑛 for some positive integers n and prime number p and p is known as characteristic of the finite field. There does not exist finite field of order 24 since 24 = 23.3 so 24 is not the power of a prime. Prime field Definition 16 : The prime order ’s fields are the most important and vital in the algebraic system. The field’s elements 𝐺𝐹(𝑝) can be shown by integers 0 , 1, 2, 3,…𝑝−1. 9 Theorem 2 : Let 𝑝 be a prime number and the integers ring 𝑍𝑝 is represented by 𝐺𝐹(𝑝). This is said to be a prime field or Galois field having a prime numbe r of elements. Also the elements other than zero of the field have their inverse s. 1.1.4 Vector Space Definition 17 : Let 𝑉 be set which is non empty and 𝐹 is a field then 𝑉 is known as Vector Spa ce if the below mentioned conditions are satisfied. i- 𝑉 is abelian group under addition. ii- 1(𝑚+𝑛)=1𝑚+1𝑛 Ɐ l ∈𝐹 and 𝑚,𝑛 ∈ iii- (𝑠+𝑡)𝑚=𝑠𝑚+𝑡𝑚 Ɐ 𝑠,𝑡 ∈𝐹 , 𝑚 ∈ 𝑉 iv- 𝑠(𝑡𝑚)=(𝑠𝑡)𝑚 Ɐ 𝑠,𝑡 ∈ 𝐹, m ∈ 𝑉 v- 1.m = m.1 = m Ɐ 1 ∈ F, m ∈ V, 1 is identity under multiplication. Example 29 : The set 𝑀𝑛 of all matrices of order n is known as vector space over 𝐹. Example 30 : For a field the set 𝐹𝑛 = {( 𝑥1, 𝑥2, 𝑥3, …, 𝑥𝑛)}/𝑥𝑖ɛ F, 1 ≤ I ≤ n} is a vector space. Subspace Definition 18 : The non empty subset 𝑊 is cal led subspace of a vector space 𝑉 if 𝑊 is also a vector space under the same operation defined in 𝑉. Theorem 3: A non empty subset 𝑊 ≠ ɸ of a vector space 𝑉 is called subspace if and only if i- 𝑤1 ,𝑤2 ∈ 𝑊 then 𝑤1 + 𝑤2 ∈ 𝑊 ii- 𝐼𝑓 𝑝 ∈ 𝐹 and 𝑤∈W then 𝑝𝑤∈W Remark 13 : V itself and {0} are subspaces of 𝑉, called the trivial or improper subspaces of 𝑉. Example 31 : 𝑁= {0 𝑥 𝑦 Where 𝑥,𝑦 ∈ ℝ, is a subspace of ℝ3. 10 Linear Transformation Definition 19 : Let 𝑊 and 𝑉 over the same field 𝐹 are two vector spaces then 𝑠 from 𝑊 to 𝑉 is called linea r transformation if it satisfies the properties which are mentioned below . i- 𝑠(𝑢+𝑣)=𝑠(𝑢)+𝑠(𝑣) ii- 𝑠(𝑝𝑢)=𝑝𝑠(𝑢) where 𝑝 is a scalar. Example 32 : The transformation 𝑠(𝑥,𝑦)=(2𝑥,𝑦−𝑥) is linear transformation. Affine Transformation Definition 20 : A set 𝐸having vecto r space properties and mapping 𝑓 such that 𝑓: 𝐸×𝐸 𝐸 𝑓(𝐴,𝐵)=𝐴𝐵 Remark 14 : Chasless relation explain direction 𝐴𝐴=0 and 𝐴𝐵=−𝐵𝐴 Remark 15 : Every vector space is affine spac e. Permutation Definition 21: Let 𝑌 = {1, 2, 3,…,n} and then 𝑓:𝑌 𝑌 be the collections of all bijective mappings are called permutation. Symmetry Definition 22: It is a transformation which acts upon the objects and leave s it apparently unchanged. Symmetric Group Definition 23: If 𝑋= {1, 2, 3, … 𝑛} then the collection of all permutation of this set 𝑋 is known as the symmetric group and denoted by 𝑆𝑛 Remark 16 : 𝑆𝑛contains the n! 11 Remark 17 : 𝑆3 is the symmetry of equilateral triangle . Group Action Definition 24 : Let 𝐺 be a group and 𝑌 be a set along with rule w hich associates every element 𝑝 ∈ 𝐺 and 𝑦 ∈ 𝑌 to an element 𝑝𝑦 ∈ 𝑌 such that the following conditions are satisfied . i- 1.𝑦 = 𝑦 Ɐ 𝑦 ∈ Y ii- 𝑠,𝑡 ∈ 𝐺 and y ∈ Y such that (𝑠𝑡).𝑦=𝑠.(𝑡.𝑦) If such an association exists we say that 𝐺 is acting on Y and this association is called group action. Example 33 : The group of permutation of n objects if 𝑝 ∈ 𝐺and 𝑦 ∈ Y such that 𝑝.y = 𝑝(y) Example 34 : G is any group Y = 𝐺, define action such that 𝑔.y = 𝑔y𝑔−1 then 𝐺 is acting by conjugation onto itself. Stabil izer Definition 25 : Let G be a group which is acting on the Y then stabilizer of y ∈ Y is defined as 𝐺𝑦 = { 𝑔 ∈ G : 𝑔.𝑦=𝑦 } 1.2 Fundamental cryptographic concepts Now we shall discuss basic terms related to cryptography which are useful and important for understanding the main idea of crypto graphy and also very important for the proposed 12 work in the coming chapter. Now we shall explain some basic definitions related to cryptography. Plaintext Definition 26 : The original text or message through which one person wants to communicate with the other person is termed as plaintext. It may be a word fi le, numerical data, audio file or video file and denoted by M. Example 35 : “please give me a glass of water” is a word file which is a plaintext. Ciphertext Definition 27 : The text or message which cannot understand by any one or meaningless is known as ciphertext. The original message is transformed into a message which cannot be reada ble in cryptography. It is denoted by C . Plaintext Alphabets Definition 28 : The alphabets or characters are used in plaintext is known as plaintext alphabets. These may be numerical data, English alphabets or symbols etc. Ciphertext Alphabets Definition 29 : The alphabets or characte rs which are used to convert the message from plaintext to ciphertext are known as ciphertext alphabets. These may be different from original alphabets. Cipher Definition 30 : The process through which a readable message can be converted into unreadable text or meaningless form is known as cipher . It may be substitution or transformation and known as cipher substitution or cipher transformation. Key Definition 31 : When the sender sends a text, he also sends some extra information so that receiver used this information or code to read the ciphertext which is known as the key. In 13 other words , the key is some rules which are used during the encryption and decryption by sender and receiver. It is denoted by K . Encryption Definition 32 : The process through which the plaintext is converted into ciphertext is known as encryption. In cryptography , there are used some encryption techniques to send the confidential message from an insecure system. For encryption there are two main requirements; ➢ An algorithm ➢ Key It is used by a sender to encrypt the plaintext. Encryption Algorit hm Definition 33 : The process or mathematical process through which we convert the plaintext into unreadable and meaningless form is called encryption algorithm. It is used by a sender to encrypt the plaintext into ciphertext. Decryption Definition 34 : The process through which the unreadable and meaningless ciphertext convert into plaintext is said to be decryption. Decryption is the alter proces s of encryption. This process is used on the receiver side to decrypt the meaningless message to plaintext. The process of decryption has two requirements; ➢ Secure algo rithm ➢ Key Decryption Algorithm 14 Definition 35 : The process or mathematical process that converts the unreadable or meaningless message into readable text (plaintext) is known as decryption algorithm. In other words , these are techniques which are used in decryption. It will be cleared from the below image: Figure 1 .1: A compl ete cipher 1.2.1 Cryptology and its classification Cryptology Definition 36 : Cryptology is the branch of science related to information security. This word is derived from the Greek word kryptos, means hidden so C ryptology is the study of secret message. Classification of Cryptology Cryptology is further divided into two main branches ; ➢ Cryptography ➢ Cryptanalysis Cryptography Definition 37 : It is the study of the method of transforming a secret message such a way that only the authorized person can understand it. Cryptanalysis 15 Definition 38 : It is the branch which deals to break the cryptosystem. It is ref erred to as “breaking the code”. 1.2.2 Purpose of Cryptography Cryptography plays a vital role to achieve the security goals to make sure the privacy of the secret data from the unauthorized channel. It has wide use in daily life now a day due to high security advantages. The various goals of cryptograp hy are given below . Confidentiality To make sure that the secre t data in the computer is disseminated and can be accessed only the unapproved party or channel and not by the unauthorized party. Authentication The information or data which is accepted by any system or party to be check ed whether the data receive d from an authorized party or from a wrong party. Integrity Only the certified person or channel is allowed to makes a change in the given text or message, no one can alter the message between the sender and receiver. Non Repudiation It will ensure that neither the receiver nor the consigner (sender) of a message can deny from the transmission. Access Control Only the authorized party can access to the confidential data or secret information. 1.2.3 Classification of Cryptography 16 Cryptography is furth er divided into two main categories ; ➢ Symmetric key cryptography ➢ Asymmetric key cryptography Symmetric Key C ryptography In such type of cryptography encryption and decryption both have the same key as shown in the following fig. Fig 1.2 : Symmetric Key Cryptography In such type of cryptography , the key plays an important role in the security of the data depends on the nature of the key and length of the key . There are various symmetric algorithms which are DES, TRIPLE DES and AES. It is further divided into two subclasses; ➢ Block Cipher ➢ Stream Cipher Block Cipher 17 It is a symmetric key algorithm which is used for encryption . It is mapping which maps n bits of plaintext to n bits of cipher text where n is known as block length or key length. It is usually known as simple substitution cipher with large block size. Stream Cipher This cipher is also symmetric key encryption system. It is an important kind of encryption algorithm. It works usually smaller part of the information as compare d to the block cipher which works on the large block of information. It is normally faster than the block cipher in hardware and having less complex hardware circuitry. It may also be advantageous in such situation where the transmission errors are mostly probable . 1.2.4 Asymmetric key cryptography Asymmetric key cryptography or public key cryptography is c ryptography which has a pair of key s which are used to decrypt and encrypt the data to make the algorithm more secure. In this type of cryptography , there are two dispar ate keys which are used to encrypt and decrypt the given data as shown in fig. 3 Fig 1.3: Asymmetric key cryptography It is not replace d by the symmetric key. The example of such type cryptography is elliptic curve cryptography. 1.2.5 Theory of S -Box 18 In the following section , we will discuss about the substitution boxe s(s-boxes). The main task of S -box theory is contributed to help in the research work to achieve the goal s and dissertation s. Substitution Box (S -box) In cryptography, an S -box is the important and basic compo nent of symmetric key process through which substitutions are made. In such type block ciphers, they are used to develop the correspondence between the cipher text and key . What is an S -box? The S -Boxes are basically Boolean functions from {0,1}𝑚 {0,1}𝑛 m×n mappings Thus this can be explained as there are n component s mapping each bei ng connect from m bits to 1 bit , in other sense, each component mapping is a Boolean mapping in m Bool ean variable. 1.2.6 Balanced Function A Boolean mapping is considered as balanced if the number of zeros and ones are same in the truth table in counting . The Hamming weight of this binary sequence is how many ones in number. Properties of good S -box: ➢ Balanced Component mapping ➢ The non -linearity of Component should be very high . ➢ The Non -zero linear combinations of Component mapping should be highly non -linear and balanced. ➢ The s -boxes should be highly algebraic degree. 1.2.7 Substitution –Permutation Network (SPN) 19 Product Cipher Definition 94: Two or more transformation get together in a cipher to make new cipher which is analogously ( comparatively ) more secure than the separate ciphers is known as product cipher. Definition 9 5: Permutation is the substitution of the sequence of the element of the text by the sequence of these elements which are permuted . There are no addition and subtraction of the elements. W e just reshuffle the elements. Substitution Network Definition 96: The substitution network or SP network is the product of two or more ciphers. There are used a chain of functions related to mathematics are used in this algorithm. In these algorithms , there are used S -boxes and P boxes for substitution and permutation. 1.2.8 Block cipher and advance d encryption standard Many cryptographic algorithms have been proposed but AES is the latest and secure crypto -algorithm. This cryptographic algorithm used permutations operations to make information more secure. We now give a brief description of the cryptosystem approved for general standards and technology (NIST). It is called the Advance Encryption Standard (AES) and was adopted and effective on May 26, 2002. The Advance Encryption Standard (AES) also known as Rijn dael Algorithm. It was offered by two cryptographers from Bel gian, Joan Daemen and Vincent Rijmen who has submitted this proposal to NIST during the process of selection of AES . The AES was developed to replace two currently existing standards, DES (Data Encryption Standard) and T riple DES because these two standard s were no longer a secure cryptosystem. Therefore it was necessary to phase out the DES and adopt a more sec ure encryption standard. For this algorithm , NIST selected three members of the Rijndael family, each of them with a 20 block size of 128 bits but with different key length 128, 192, and 256 bits. The size of the key space in AES is 2128, or approximately 3.4× 1038. This number is so large that the fastest “Cracker Machine” available at present would take tr illion of years to crack the AES code by doing an exhaustive key search. It is therefore expected that AES will remain a secure cryptosystem for many years to come. The enciphering algorithm in AES developed by two cryptographers, Dr. Joan Daeman and Dr. Vincent Rijmen from Belgian and was given the n ame Rijndael. The basic structure of this algorithm is that of an iterated block cipher but with some additional steps. We now discuss briefly the Rijndael algorithm in AES. There are several versions of Rijndael algorithm in AES; there is a difference in the blo ck/key length and the rounds in numbers . The possible values for the key length are 256, 192 and 128 bits. Similarly , the number of rounds can be 8, 10 or 12. There are few steps: ➢ Round key addition ➢ S-bit substitution ➢ Permutations ➢ Row shift operation ➢ Column mix AES algorithm can be understood by the following diagram: 21 Fig 1.4: AES Algorithm 1.3 Some Historical Ciphers Ciphers play a vital role in the field of cryptography. There are different ciphers which are used in cryptography depend on different algebraic structures like groups, rings and fields. Here we discuss some historical ciphers in detail with examples. 1.3.1 Process of Transforming a Message Basically , there are two ways to transform the message in cryptography . One is called transposition a nd other is called substitution. H ere we shall discuss those substitution methods especially those that employ algebraic techniques and make use of the algebraic system like fields and rings. The general principle involved in the substitution method is to select a permutation 𝑓 of the set of letters in the alphabets and replace each letter 𝑥 in the message by 𝑓(𝑥). Suppose we want to send a message to a friend that ALGEBRA IS GREAT FUN; Plaintext Since we don ’t want that an unauthorized recipient can know this message, we decide to send the message in secret form . Let us take 𝑓 to be the permutation given by t able 2.1; for each letter 𝑥 in the top of the row, 𝑓(𝑥) is the letter directly below 𝑥. A B C D E F G H I N F P R K S C E L J K L M N O P Q R 22 Table 1 .1: fixed table for cipher Replacing each letter in the message by 𝑓(x) without blank spaces we transform the original message to NQCKFDNLHCDKNOSXT ; Cipher -text We send this message to our friend who has been already provided the secret key in advance. Our friend can recover the message by replacing the letter 𝑦 in the received message by 𝑓−1(𝑦). But the unaut horized person who does not aware the secret key, he can’t find out the original message. It looks that one can try all the possible permutations to find out the meaning full message and such a process to breaking the code is known as exhaustive key search. But the number of permutation i n the set of 26 English alphabets is equal to 26! = 403291461126605635584000000 ≈ 4× 1026 This number is so large that it is very hard to find out all possible permutations. If our enemy can take one second for one permutation it will take 1019 years to go through all the permutations. So it is not an easy task to find the exhaustive key. It is clear from the above discussion that it is computationally infeasible to break the code by selecting all the permutation but still there are available such type of computers which find out the original message in the short interval of time from the ciphertext. It is required that build up such algebraic system like rings and fields to make the system more secure. Before discussing the algebraic methods in which s imple algorithm is used which needs no abstract . 1.3.2 Caesar Cipher A J Q G T B I M D S T U V W X Y Z H O X Z V Y U W 23 This is a mono alphabetic cipher . It works by arranging the alphabet around a circle as shown in figure 2.2. If we shift each letter forward by k places in the circle we get the resulting permutations called the k length cycle shift and such type of enciphering in which cycle shifting is used called the Caesar cipher. The actual cipher which was used by Caesar with cyclic shift k = 3. In such type of cyclic shift ing letter, we shift A to D, B to E and so on. It is shown in the figure below completely , Figure 1.5: Caesar cipher with k = 3 In the form of table , we can make the arrangement of alphabets as A B C D E F G H I D E F G H I J K L J K L M N O P Q R M N O P Q R S T U S T U V W X Y Z V W X Y Z A B C Table 1 .2: Caesar cipher with k = 3 Example 36 : Encipher the plaintext “ HARD WORK IS KEY TO SUCCESS ” Using Caesar cipher with k = 3 24 Solution : We use the key k = 3 for enciphering as show n in above table 2.3, by substituting each alphabet in the plaintext by the alphabet below it. By converting all the alphabets of the plaintext we obtain the ciphertext KDUG ZRUN LV NHB WR VXFFHVV As a result , we obtain the text which is meaningless. We can decipher this meaningless text by replacing each letter in the text by the letter above each one . As a result , we obtain the original plaintext HARD WORK IS KEY TO SUCCESS . 1.3.3 Vigenere Cipher We now explain a periodic substitution cipher composed of shifts ciphers. This cipher is called V igenere cipher named after Claise de Vigenere, a cryptologist of the 16th century. This cipher with period p and key sequence (𝑘1 , 𝑘2,𝑘3 ,…, 𝑘𝑝) . It is simple to identify the shift cipher by the letter which moves to A. For example , the letter A for key cipher with k = 3 is D. The word f ormed by this cipher is called V igenere cipher . Each letter in the key word, the table contains the each row with one al phabet. The letter below the A forms the cipher. It is given below the table 2.4 with key word TASK . A B C D E F G H I J K L M N O P Q R S T U V W X Y Z U V W X Y Z A B C D E F G H I J K L M N O P Q R S T B C D E F G H I J K L M N O P Q R S T U V W X Y Z A T U V W X Y Z A B C D E F G H I J K L M N O P Q R S L M N O P Q R S T U V W X Y Z A B C D E F G H I J K Table 1 .3: Vigenere cipher with key word Task Example 37 : Encipher the given p laintext using the V igenere cipher with key word TASK. I MISS YOU Solution: To encrypt the plaintext we follow the following procedure, we see the each word in the sentence, and for example the first word I in the message is replaced with the 25 letter c and similarly M the second lett er in the second word is replaced by G and I is replaced by J, and continuing this procedure we get the cipher text C GJLD SPN We obtain a text which is meaningless. Similarly, we can decipher the message by taking key word in reverse direction and in this way obtain the original message which is I MISS YOU 1.3.4 Modular Enciphering and Affine Cipher Let n be the number of characters in the message alphabet A. Let S = ℤ𝑛 be the ring of integers modulo n. The enciphering in which algebraic operations of ℤ𝑛 are used is called modular enciphering. An affine cipher is the simplest example of modular ciphering. Let a, b ∈ ℤ𝑛 and suppose 𝑎 is co prime to 𝑛. Then 𝑎 has inverse in ℤ𝑛. Hence the mapping ɸ: ℤ𝑛 ℤ𝑛 ɸ (𝑥)=𝑎𝑥+𝑏 (2.2) It is a bijective mapping. The mapping in the can be express as the operations of multiplication and addition in ℤ𝑛 is given by ɸ (𝑥)=𝑎𝑥+𝑏 mod n (2.3) Where x mod n represent the remainder left by dividing by n. For deciphering , we use the inverse mapping which is given by ɸ−1(𝑦)= 𝑎−1(𝑦−𝑏)= 𝑎−1𝑦−𝑎−1𝑏 (2.4) For every 𝑦∈ℤ𝑛 If the plaintext alphabets A i s the set of alphabets A, B, C, …, Z then n = 26. We take the mapping ɸ: A B as shown in table 2.4 A B C D E F G H I 26 Table 1 .4: Affine cipher Example 38: Use the mapping ɸ given above and the affine cipher ɸ(x)=(5x+5) mod 26 (2.5) and for deciphering the mapping ɸ(x)=(7x+4) mod 26 (2.6) 1. To encipher ALGEBRA. 2. To decipher AMEQMNZW. Solution : As 5 is co -prime to 26 therefore , ɸ is bijective. 1. Replace each letter in the plaintext by a number which is shown above in the table and th en ap plying the mapping ɸ. We write the alphabet relate to ɸ(x). It is completely described in table 2.5. Plaintext A L G E B R A 𝑥 1 12 7 5 2 18 7 5 𝑥 +5 10 65 40 30 15 95 40 5 𝑥+5 mod 26 10 13 14 4 15 17 14 Cipher -text J M N D O Q N 1 2 3 4 5 6 7 8 9 J K L M N O P Q R 10 11 12 13 14 15 16 17 18 S T U V W X Y Z 19 20 21 22 23 24 25 0 27 Table 1 .5: Enciphering process 2. To decipher the text we use the inverse mapping ɸ−1.If 7x + 4 = y then x = 7−1(𝑦−4). In ℤ26 , = 7−1=15 as 15 × 7 = 105 = 1 (mod 26) so for deciphering the mapping is d(y) = 15y – 60 = 15y + 18 The decipheri ng process is given below in table 2.6 Ciphertext A M E Q M N Z W y 1 13 5 17 13 14 0 23 15y + 18 33 213 93 273 213 228 18 25 15y+ 18 mod 26 7 5 15 13 5 20 18 25 Plaintext G E O M E T R Y Table 1 .6: Deciphering procedure 1.3.5 Hill Cipher We now discuss the impo rtance of the affine cipher which is called as Hill Cipher . Let n be the number of alphabetic letter s and r be any positive integer such that 𝑟 ≥ 1. Then the mapping 𝑓: A ℤ𝑛 which can be extended to 𝑓: 𝐴𝑟 ( ℤ𝑛)𝑟 by defining the mapping ɸ (𝑏1, 𝑏2, 𝑏3, … 𝑏𝑟) = (ɸ(𝑏1), ɸ((𝑏2), ɸ((𝑏3), …, ɸ((𝑏𝑟)) (2.7) Let us denote the elements of ( ℤ𝑛)𝑟 as columns and let ( ℤ𝑛)𝑟×𝑟 denote the set of 𝑟×𝑟 matrices having entries from ℤ𝑛. If M is invertible then (det𝑀) (𝑑𝑒𝑡𝑀−1)=det( 𝑀 𝑀−1)=det𝐼=𝐼 (2.8) Therefore det𝑀 is an invertible element in ℤ𝑛. In the other direction if det𝑀 is invertible in ℤ𝑛 then 𝑀−1 is given by 𝑀−1=(det𝑀)−1𝑎𝑑𝑗𝑀 28 Therefore we can say that a square matrix M over ℤ𝑛 is an invertible if det𝑀 is co - prime to 𝑛. If M be a matrix whose inverse exist in ℤ𝑛 and D ∈ ( ℤ𝑛)𝑟. Then the mapping ɸ(𝑋)=𝐾𝑋+𝐷 ; Ɐ ∈ ( ℤ𝑛)𝑟 (2.9) This is called Hill Cipher. To deciphe r we use the inverse direction ɸ−1(𝑌)= 𝑀−1(𝑌−𝐷) (2.10) Example 3 9: Use the Hi ll cipher with n = 26 and r = 2 ɸ[𝑥1 𝑥2]= [85 56][𝑥1 𝑥2] + [7 9] (mod 26) (2.11) 1. Encipher the word MOUNTAIN 2. Decipher the word AJGLLRKE Solution : We firstly verify that det [85 56]=23 is co -prime to 26. We div ide the word into blocks of two letters. We represent each block by the number of columns given by the mapping 𝑓 and then apply the mapping ɸ. This enciphering process is given by Plaintext MO UN TA IN [𝑥1 𝑥2] [13 15] [21 14] [20 1] [9 14] ɸ[𝑥1 𝑥2] [4 8] [11 16] [16 11] [19 8] Ciphertext DH KP PK S Table 1 .7: Deciphering Algorithm 2. In ℤ26 (𝑑𝑒𝑡𝑀)−1= 23−1 =17. Therefore 𝑀−1=17[6 −5 −5 8] = [24 19 19 6]. To decipher the message the following mapping is used. ɸ−1[𝑦1 𝑦2] = [24 19 19 6]([𝑦1 𝑦2]−[7 9]) (2.12) The deciphering process is given below in the table completely. Ciphertext AJ GL LR KE 29 [𝑦1 𝑦2] [1 10] [7 12] [12 18] [11 5] ɸ−1[𝑦1 𝑦2] [5 22] [5 18] [5 19] [20 0] Plaintext EV ER ES TZ Table 1 .8: Hill Deciphering procedure CHAPTER 2 REVIEW OF S -BOX THEORY The l iterature review is very important and vital not only to connect the conceptual ideas with handy examples and applications . It provides the light for the role of a research study and this study is linked to secure communication. So in this chapter fun damental background is lighted by stating important results in numbers . Therefore literature review plays a vital role in the field of a research study. 2.1 Rijnd ael A lgorithm Belgian cr yptographer Daemen and Rijmen [4 ] designed the new algorithm to enciphering. It is known as Rijndael algorithm. There are several versions Rijndael in AES; they are differing in key length, block and number of rounds. The possible values for this block l ength and the key length are 256, 192 and 128 bits. It is a substitution - permutation network (SPN) with 14, 12 and 10 rounds depending on the size of the key. As mentioned earlier the general scheme of Rijndael is like an iterated block cipher. There are several operations that are used in Rijndael; ➢ Round key addition ➢ Byte substitution ➢ Row shift ➢ Column mix The deta il discussion is presented in [5 ]. 31 2.2 Polynomial Description of AES Rosenthal [16 ] explained the co mplete the Rijndael Advance Encryption Standard in the sense of complete polynomial description which was taken for selection by the National Institute of Standard and Technology (NIST) and it described the structure of S -boxes. It is also shown how the whole algorithm can d escribe in a finite ring through a sequence of algebra ic manipulation in . In [16] it was explored that description relate to Algebra of substitution box so called ‘S -Box’ and the most important non - linear pa rt of the AES system. It was explained how the s parse polynomial explained the S -box. 2.3 Action of Symmetric Group 𝑺𝟖 on AES S -box Iqtadar Hussain , Tariq Shah and Hasan Mahmood [7] described a new 𝑆8 S-box which is made by acting symmetric group 𝑆8 on AES S -box and these obtained S-boxes are used to construct 4032040320 secret key. Thus in this way , we obtain the encryption keys with the permutations of the se existing S -boxes which give 40320 new S-boxes which improve the security and system become more reliable and safe . In [7 ] it is explained that how we construct the new S -boxes, there are several steps which are used to construct the 𝑆8 S- box; ➢ Conversion hexadecimal to decimal ➢ Conversion decimal to binary ➢ Acting 𝑆8 on the elements of AES S-box ➢ Conversion to decimal There are 40320 elements in symmetric group 𝑆8, acting all the elements on AES S-box we get newly 𝑆8 AES S-boxes whose nonlinearity is same as the original one. Actually , on the elements of the AES S-box we act the symmetric group 𝑆8 and we reshuffle the elements of the S-box. Here the elements of 𝑆8 are p ermutation s which are acting on the binary digits and permute the original elements. Here is the example of 𝑆8 AES S -box whose nonlinearity is same as the original one. 32 Table 2.1 : 𝑆8 AES S -box 2.4 Image Encryption Iqtadar Hussain, Tariq Shah and Muhammad Asif Gondal [8] described with the help of two basic and key concepts image encryption : one is the theory of replacement or substitution , permutation network and the other is called Chaos theory . Furthermore, it is analyzed the proposed algorithm ’s strength by applying it on a color image and derive that the color image can be encrypted through the algorithm successfully and it make s secure and safe against many classic attacks. In [8 ] he demonstrate s that chaotic encryption system is not secured and it can attack easily, So in order to i mprove the security he offered to adopt the non -linear functions, limited in time and space to alter the key continuously 2.5 Permutation properties Beth and Ding [2 ] explained the vital permutation’s properties which one can use in secure key block cipher as a round function to secure it from different attacks . Good nonlinearity and high order of s everal classes of almost complete nonlinear permutations 209 118 215 243 91 241 243 204 18 128 213 177 127 207 185 87 105 9 232 246 123 226 197 90 188 78 25 189 46 28 83 72 159 254 139 21 23 183 223 108 22 156 220 218 210 106 146 134 4 205 145 201 34 15 132 43 133 3 8 89 249 149 27 214 160 137 52 35 163 117 99 24 67 179 79 155 176 217 181 12 195 202 0 252 16 126 154 227 113 233 63 178 97 100 98 237 74 253 57 251 193 228 147 140 196 250 1 247 66 54 175 56 194 153 64 173 11 174 50 222 62 31 107 144 2 255 219 75 236 36 131 124 231 143 68 135 76 157 119 182 84 230 162 211 80 136 229 110 17 49 10 40 69 125 58 6 111 103 161 235 88 19 51 33 224 5 20 102 73 203 60 81 138 142 92 242 221 104 151 244 172 206 101 184 116 71 94 121 212 115 61 32 59 114 148 53 38 29 30 77 120 238 86 167 225 190 169 41 82 55 158 85 96 129 95 37 208 150 199 186 13 200 166 47 216 122 42 130 240 234 45 14 171 39 141 248 109 198 48 239 44 152 168 164 191 93 65 112 192 170 180 165 26 70 187 7 33 and other permutations in GF (2)𝑛 are presented. In [2 ] key and basic properties of APN permutation network are highlighted , in this way we obtained highly nonlinear S -boxes. 2.6 Analysis of S -box Hussain et al. [9 ] divided the work in to two sections, 1st section represents the analysis of S-box and bit independent criterion, their nonlinearity etc. whereas 2nd section represents conclusion. It is also analyzed against different criterions such as bit independent criterions, differential approximation probability and l inear approximation probability; in the view of this work by linear fractional transformation we can constru ct new s -boxes . 2.7 Analysis of residue prime S -box Hussain et al. [ 10] made some useful efforts to analyze the S-box which is based on the residue of a prime number, which includes differential approximation probability (DP), bit independ ent criterion (BIC) , linear approximation probability (LP) and non -linearity. With the hel p of these results, we derive the result which is linked with the algebraic encryptio n strength and weakness of this S -box. In [10] they analyzed S -box for different criteria and derived that the residue prime S-box is not satisfied all criteria absolutely . 2.8 Construction of S -boxes using projective general linear group Anas et al. [1] have developed new techniques to construct highly non -linear S -boxes. Firstly, they used the action of 𝑃𝐺𝐿 (2,𝐺𝐹(28)) on the Galois field of 256 elements and then use permutations to construct new kind S -boxes . They computed the strengt h of these S -boxes and made some useful analysis. They compared these S -boxes with the well known existing S -boxes and show that the analysis of these S -boxes is compar atively 34 better. By the action of the projective general linear group , they constructed 1 6776960 number s of S-boxes. 2.9 Cryptographi c criteria of Boolean functions It was studied the mathematical and practical cryptographic criteria of Boolean functions in [6 ]. Elhosary et al. introduced the algorithm that fulfill s the criteria and introduced the Boolean functions that satisfy the better cryptographic criteria. The Boolean function representation and cryptographi c assessment were presented in [6 ]. It was beginning of cryptographic algorithms and opened the new door for the analysis and further, studied the Hash function. 2.10 Matrix manipulation of cryptographic functions Some efforts were made to investigate the matrix manipulation o f cryptographic functions in [14 ]. G.C. Meletious , D.S Triantafyllou and M.N. Vrahatis firstly, considered the cryptographic repeated applicatio ns of orbit and found difficult to derive the cryptographic functions which are related to the orbit’s length. They investigated the behavior of matrix’s power which is made from t he generator of the multiplicative group of several primes 𝑝 in ℤ𝑝. It was studied matrix factoriza tion approach at the end in [14 ]. 2.11 A method to construct S-boxes based on permutations In a block cipher, S -boxes are very important nonlinear components. The nonlinear ity makes the system more safe against the differential and linear cryptanalysis. These S- 35 boxes are key dependent. In [11 ], simple four algorithm s are presented to construct the S - boxes which are based on the key dependent. Kazys Kazlauskas , Robertas Smaliukas and Gytis Vaicekauskas presented eight distance metrics for the analysis of these key dependent S -boxes. In the last sectio n of [11 ], they experimentally investigated the quality analysis of these key dependent S -boxes. These S -boxes can be used in block cipher like AES cipher. It was studied that by changing the secret key , the or der of the elements of the S -boxes based on key dependent are also changed. 2.12 Constructi on of 𝑺𝟏𝟔 AES S -boxes As earlier some efforts are made to construct the 𝑆8 S-boxes by the action of symmetric group 𝑆8 and construc ted 40320 newly 𝑆8 S-boxes as the or der of the symmetric group in [7]. In [17 ], Siddiqui et al. used the action of 𝑆16 instead of 𝑆8 to construct the new 𝑆16 S-boxes and generate new 16!(20922789888000) S -boxes as the order of the symmetric group 𝑆16. At the end finally, they analyzed the st rength of the proposed S -boxes by different properties like balance prop erties, nonlinearity, bijection, bit independent criterion and linear approximation probability etc. These S -boxes are used to develop 𝑚16! secret keys which are used to make the system more reliable and secure. One of the advantages of AES algorithm usin g 𝑆16 S-boxes gives more reliable keys as compare d to the algorithm using in 𝑆8 S-boxes. 2.13 Construction of large cryptographic S -boxes It is clear that large S -boxes have better cryptographic properties than the smaller S - boxes. The main target is to achieve the large S -boxes w ith bent functions. In [5 ] J. Detombe and S. Tavares constructed 5×5 S -boxes with the required bent function. Whenever, these variables are odd in numbers then they have desired cryptographic properties and can be construct ed easily. These newly constructed S -boxes fulfill the 36 criterion of good S -boxes . Bent function plays key role to achieve the maximum nonlinearity. 2.14 Improvement in cryptographic properties of AES S -box by multiplication Many cryptographic algorithms have been proposed but AES is the latest and secure crypto -algorithm. This cryptographic algorithm used permutations operations to make information more secure. We now give a brief description of the cryptosystem approved for general standards a nd technology (NIST). It is called the Advance Encryption Standard (AES) and was adopted and effective on May 26, 2002 . Florin Medeleanu , Ciprian Racuciu and Marius Rogobete studied the chances to improve the cryptographic properties of AES algorithm in [15] and effect of these improvements. It is also described that all the cryptographic properties could not improve at the same time. 2.15 Construction of S -boxes for lightweight block cipher During the study of different techniques for the construction of S -boxes, it is derived that there is some space for the improvement in the cryptographic properties. H. Mihajloska and D. Gligoroski made some useful efforts by using Quasigroup of order 4 to construct new cryptographic S -boxes in [13]. Fur ther, it has opened new door to construct new S - boxes which are satisfied the criterion for the good S -box. They also compare the properties of these constructed S -boxes with the well known existing S -boxes. 2.16 Affine -power Affine S -box In [3 ] L. Cui and Y. Cao studied the algebraic and polynomial structure of the AES S -box and derive that only 9 terms are involved for algebraic expression, while 255 terms for 37 the inverse S -box. They presented new affine -power -affine S -box to improve the algebraic compl exity. The algebraic complexity improve s of AES S -box from 9 to 253 while for the inverse 255 remain same. They compare the properties of this affine -power - affine S -box with the well known S -boxes and derived that this S -box fulfills the criterion for the good S -box. 2.17 Linear cryp tanalysis method for DES cipher M. Ma tsui derived a new technique for cryptanalysis of DES cipher, which is a well known plaintext attack. It is possible to break 8 rounds with 222 and 16 rounds with 247 plaintext. We can apply this method on any situation as describe d in [12]. It was studied that these attacks for the ciphertext can deal with any non -random situation at any stage. CHAPTER 3 CONSTRUCTION OF 𝑺𝟖 RESIDUE PRIME AND AFFINE AES S-BOXES Introduction Rijndael Blo ck Cipher is based on 128 bits and developed by two cryptographers, Joan Daemen and Vincent Rijmen, was taken on Advanced Encryption Standard (AES) by (NIST) on October 2, 2000. AES is one of the most reliable algorithms which are used in cryptography of symmetric key . The S -box has a vital role in AES, therefore most of the work is focused on the battlement of the S -boxes. In this section , we represent new 𝑆8 S- boxes by using action of 𝑆8 on residue prime S -box as earlier some effort s were made Hussain et al. in [7 ]. Furthermore, we utilize these S -boxes to construct 4032040320 secret keys from 𝑆8 S-boxes and then we utilize these keys and propose a new algorithm which is more reliable when two channels or persons communicate each other. S -box is the only non-linear component which provides confusion capability for AES. 3.1 Algebraic Expression of Residue Prime S -box The expression for residue prime s -box is obtain ed from the function in GF (28) . As GF(28) is a finite field, therefore inverse with respect to multiplicat ion of every element exists and 0 0. This inversion of multiplication for the function is as follows 39 𝐹(𝑥)= 𝑥−1 0 𝑥≠0 𝑥=0 This affine transformation which can be decomposed into two steps: 1. The linear transformation 𝐿(𝑥) 𝑦=𝐿(𝑥) And the propose d implementation depends on the residue of a prime number and the complete entries in S -box are 256. These entries are the residue of 257, there is logic behind the choice of the number 257 becau se the residues from 1 to 255 have unique inverses. Further more, these residues can be utilized in all bl ock size of AES. 3.2 𝑺𝟖 residue prime S-boxes Firstly , we perform the action of 𝑆8 on the original residue prime S -box as the new S - boxes was developed on similar action on AES S -box [3] and sequentially construct 40320 new residues prime S -boxes. This process is preceded with the conversion of the elements into bytes and the elem ents in bytes are permuted by the action of the symmetric group 𝑆8 which gives 40320 new S -boxes. Fo r the formation of new S -boxes, the resulting algebraic expression is 𝑓: 𝑆8× residue prime S -box 𝑆8 S-boxes In this way , the number of total new S -boxes is 40320 due to an order of the symmetric group because we are acting the elements of symmetric group 𝑆8 on the elements of S- box. 𝜋1((𝑆𝑏𝑜𝑥 𝑟𝑒𝑠𝑖𝑑𝑢𝑒 𝑝𝑟𝑖𝑚𝑒 ) = 𝑆𝑏𝑜𝑥 1 𝜋2((𝑆𝑏𝑜𝑥 𝑟𝑒𝑠𝑖𝑑𝑢𝑒 𝑝𝑟𝑖𝑚𝑒 ) = 𝑆𝑏𝑜𝑥 2 … … … … … … … … … 𝜋40320 ((𝑆𝑏𝑜𝑥 𝑟𝑒𝑠𝑖𝑑𝑢𝑒 𝑝𝑟𝑖𝑚𝑒 ) = 𝑆𝑏𝑜𝑥 40320 Table 3 .1: Action of 𝑆8 on residue prime S -box 40 Where 𝜋1, 𝜋2, 𝜋3,…, 𝜋40320 are the elements in 𝑆8. In this algorithm , the elements of original residue prime S -box is converted into binary form and then applying the action of symmetric group 𝑆8 we get the 40320 new 𝑆8 residue prime S -boxes. This process can be presented as follows Table 3.2 : Algorithm for 𝑆8 S-boxes An example to construct new 𝑆8 resid ue prime S -boxes from the main S-box is shown in table 2.12 Table 3.3 : An example of bijective 𝑆8 S-boxes 3.3 Generating Affine AES S-box through affine mapping We introduce the affine mapping between byte and the AES S-box. In this case , we firstly convert the elements of the S -box into binary digits and then develop a relation between Residue prime S -box Convert elements of residue prime S -boxes into bytes Acting 𝑆8on these elements We get 40320 new 𝑆8 S-boxes 0 2 130 105 194 91 23 163 210 196 184 183 169 177 197 116 242 118 88 217 101 50 237 189 71 68 102 221 90 195 60 203 246 168 190 215 49 136 179 162 46 147 166 9 95 20 111 159 153 42 24 125 158 82 123 243 179 244 209 62 45 55 216 89 254 107 69 213 239 170 249 186 38 150 65 36 181 251 198 248 171 154 225 80 206 127 3 66 180 37 40 226 176 164 228 29 99 58 135 139 33 44 63 10 235 152 178 250 188 208 245 28 229 120 124 25 114 137 175 57 15 34 173 140 113 236 51 106 255 1 156 205 26 143 122 83 240 241 199 81 119 160 231 138 142 27 234 11 18 74 12 96 110 21 252 193 218 223 117 121 204 157 227 22 86 98 48 222 219 70 192 253 129 56 146 31 108 85 14 52 5 75 214 191 100 212 76 7 92 17 43 187 149 8 167 46 201 211 200 47 6 77 13 133 144 104 131 238 220 103 97 145 230 161 247 84 253 232 112 141 126 207 41 72 94 4 53 202 61 172 35 148 182 185 67 19 224 155 39 174 132 32 134 59 79 87 73 78 54 16 93 233 165 64 151 128 41 byte and all the elements of residue prime S -box. So we define a mapping between two bytes such as 𝑓:(10101010 ) (11111111) We define an affine mapping between the each binary pairs of the byte s, in the above case we get the result (01010101). After converting all the elements through such type of affine mapping we convert all these byte s into decimal. Here we generate new S -box through affine mapping of the byte (10101010) a nd the elements of AES S-box and by chan ging the byte we can generate finite many S -boxes. Also we develop an algorithm to construct all possible 256 AES S -boxes having pseudo code is given below . ➢ Pseudo Code 1-fetch data from AESSbox.txt to work on and store in an array 2- loop on this array 2.1 convert each element to binary 3- Get a random value r from converted binary elements 4-Permenute each element of array with r 4.1 Loop on each array eleme nt 4.1.1 Split each element to array 4.1.2 Loop on this sub_array 4.1.3 Perform permute step that is subtract each subvalue of sub_array with every value of random number (r) binary 4.1.4 save result in permute variable 4.2 Save permute variable in permuted_array 5- Convert permuted_array back to decimal 6- Write permuted_array on file(data.txt) using file operations ➢ Flow Chart The flow chart of the above Pseudo is given below which e laborate the complete algorithm which consist of the following t hree steps. 42 ➢ Step 1 ➢ Step 2 43 ➢ Step 3 Flow Chart 3.4 Analysis of 𝑺𝟖 residue prime S-boxes and affine S -boxes We discuss most important ordinary properties which are found ed in disparate S-boxes to improve the strength of this recommend ed algorithm. 3.4.1 Algebraic complexity The algebraic complexity of 𝑆8 residue prime S -boxes is the same as the AES in [2]. We are acting 𝑆8on the original S -box where the elements of 𝑆8are permutations and these permutations do not affect the S-box’s algebraic complexity . In the case of affine S -boxes we are developing the affine mapping between the fix ed byte and the original S -box where this fixed byte reshuffle the elements of S -box just like permutation s. These byte s do not affect the algebraic complexity of S -box. 44 3.4.2 𝑺𝟖 S-boxes and affine S -boxes are Bijective In the Galois field GF(28) if we consider the input to all the elements of S-box, then the output take s the unique values in GF (28). The example of bijective affine S-box is given in table 2.13 below. Table 3.4: Affine AES S -box 3.4.3 Nonlinearity Nonlinearity ’s upper bound is 𝑁(𝑓)=2𝑛−𝐼−2𝑛 2−𝐼 for S -box in GF (28).As the elements of S-box are in GF (28), 120 is the optimal value of N . Through Walsh Hamamard transform of Boolean function we calculate the nonlinearity . The 𝑆8 resid ue prime S -box is not entirely a non linear function and its nonlinearity is remain ed same 99.5 as the original residue prime S -box whereas t he nonline arity of affine AES S -box is decreased by 110.875 as the original AES S-box has 112 . 3.4.4 Balance Property A Boolean function 𝑓𝑛: 𝑍2𝑛 𝑍2 is known as balance function if # {𝑥| (𝑥) = 0} = #{ 𝑥|𝑓(𝑥) = 1} or 𝐻𝑊(𝑓) = 2𝑛−1. The main feather of this property is that with higher the magnitude imbalance of a function, moreover due to this property we obtained a high probability linear approximation. Thus, due to imbalance property Boolean function becomes weak for linear crypt analysis. Like AES and 𝑆8AES S -boxes, all the Boolean functions 𝑓𝑖 𝑖 = 1,2,3,…,8 used in the structure of the Affine and 156 131 136 132 13 148 144 58 207 254 152 212 01 40 84 09 72 125 54 130 05 166 184 15 62 43 93 80 99 91 141 63 72 02 108 217 201 192 08 51 203 90 26 14 142 39 206 234 251 56 220 60 231 105 250 101 248 237 127 29 20 216 77 138 246 124 211 229 228 145 165 95 173 196 41 76 214 28 208 123 172 46 255 18 223 03 78 164 149 52 65 198 181 179 167 48 47 16 85 04 188 178 204 122 186 06 253 128 175 195 96 87 174 92 191 112 109 98 199 10 67 73 37 222 239 00 12 45 50 243 36 19 160 104 187 232 58 88 129 194 155 162 230 140 159 126 176 35 221 213 111 119 185 17 71 235 33 161 244 36 31 205 197 245 182 249 219 163 61 44 83 157 110 106 27 134 24 55 200 146 114 42 177 86 147 169 11 21 154 133 81 247 69 135 218 209 227 89 75 57 23 34 139 224 180 66 116 117 143 193 74 153 183 252 09 241 158 202 168 70 121 62 226 97 30 07 103 238 150 38 113 107 100 225 120 22 49 170 215 32 115 94 118 242 64 25 189 151 190 102 210 240 79 171 68 233 45 𝑆8 residue prime S-boxes fulfill the criteria of balance property. Hence, our S -boxes are balanced. 3.4.5 Bit independence crite rion In cryptographic output bits independence criterion plays very vital role. It needs pair wise all the avalanche variables however given set’s independent of avalanche vectors. The avalanche vectors are constructed by the complementing of a single pla intext bit. The main results of BIC analysis of proposed affine S -box are presented in Table 2.15. The BIC of this affine S -box is acceptable as compare with the other S -boxes in the regard of encryption strength. So our S -box is comparable by analysis. It satisfies bit independent criterion as presented in Tables 2.14 and 2.15. Analysis Max. Min. Average Square Deviation The differential approximatio n probability The linear approximatio n probability Nonlinearit y 104 94 99.5 SAC 0.67187 5 0.3437 5 0.51684 6 0.033111 2 BIC 94 102 3.5051 BIC- SAC 0.4687 5 0.50251 1 0.018005 8 DP 0.273438 LP 162 0.136719 Table 3.5: Performance Indexes for S -box based on action of S 8 on residue Prime 3.4.6 Linear approximation probability We examine the variation of an event in the LP. This amount play key role in determining the maximum imbalance value for the output in an event. The two masks 𝛤𝑥 and 𝛤𝑦 which are used to link of the input bits and output bits. The LP is also expressed as 𝐿𝑃 = max ⎹ {#{x|x.Γx = S(x).Γy 2𝑛 } - 1 2⎹ Where all inputs contains in set X and total elements are 2𝑛. The LP result of this affine S-box is presented in table 2.15. 3.4.7 Differential approximation probability The nonlinear transformation should be unique and lies in their differential uniformity which is essential quality. The output differential 𝐷𝑦𝑖 maps by an input differential 𝐷𝑥𝑖which assure that uniformity in function probability for each. T he DAP of affine S - box is measured and expressed as: 46 𝐷𝑃𝑠 (∆𝑥 → ∆ 𝑦) = [# {x ∈ X|S(x) ⊕ S(x ⊕ ∆x) = ∆y} 2𝑚 ] The differential approximation probability’s maximum value for proposed affine S -box is 0.0234.Table 2.14 and Table 2.15 shows the comparison of differential approximation probability of proposed S -boxes with AES, APA, Gray, 𝑆8 AES, Skipjack, residue of prime and Xyi S -box. The differential approximation probabili ty is shown below in the table 2.15 Analysis Max. Min. Average Square Deviation The differential approximatio n probability The linear approximatio n probability Nonlinearit y 113 109 110.875 SAC 0.562 5 0.42968 8 0.50585 9 0.016046 6 BIC 108 110.607 1.01204 BIC- SAC 0.48632 8 0.50516 2 0.011663 DP 0.0234375 LP 149 0.0820313 Table 3.6: Performance Indexes for affine AES S -box 3.4.8 Strict avalanche criterion analytically The SAC depends on the changing of input bit results and output bits. When a single bit varies on input, it levels half of output bits and an S -box is satisfied SAC. The avalanche of changes causes by a single variation in the input of network while Substitution Permutation (S -P) network is used in S -box. The comparison of affine S -box is shown in the table 2.16 below S-boxes Nonlinearity SAC BIC– SAC BIC DP LP AES S -box 112 0.5058 0.504 112.0 0.0156 0.062 APA S -box 112 0.4987 0.499 112.0 0.0156 0.062 Gray S -box 112 0.5058 0.502 112.0 0.0156 0.062 Skipjack S -box 105.7 0.4980 0.499 104.1 0.0468 0.109 Xyi S-box 105 0.5048 0.503 103.7 0.0468 0.156 Residue Prime 99.5 0.5012 0.502 101.7 0.2810 0.132 Affine AES S -box 110.875 0.505859 0.505162 110.607 0.0234375 0.0820313 Table 3.7: Comparison of Performance indexes of proposed Affine AES S -box and other S-boxes The comparison tells that the analyzed values are good with compare to some other S - boxes. 47 3.5 Image encryption applications It turn to a major issue that how can we make secure and reliable confi dentiality, authenticity and probity of image. The encryption of the image is to mediate the image reliably over the channel or network so that any unofficial user can free to decrypt the image. The encryption of the image and video encryption have vast ap plications and usage in the area including the communication through internet, mediation, armed communications etc. The progression of encryption is moving toward a future of endless possibilities. Here we encrypt the Lena’s image through affine AES and re sidue prime 𝑆8 S-box. We do some statistical analysis and compare them with other S -boxes. 3.6 Statistical Analysis Here, we evaluate the plain and encrypted image by some statistical analyses namely; energy, homogeneity, contrast, correlation and entr opy. Instead of algebraic analysis we implement this newly proposed balanced 8×8 S-box in image encryption through these statistical analyses. 3.6.1 Energy The energy of encrypted image is assessed by energy analysis. The Gray -Level Co - occurrence Matrix (GLCM) is used for this resolve. Energy is defined as the sum of squared components in GLCM. That is (),,2vup E vu= where u and v show the pixels in the image and ()vup, provides the number of GLCM. For constant image the value of energy is .1 48 3.6.2 Homogeneity The substances of an image are surely distributed. In homogeneity analysis, the nearness of distributed elements of GLCM to GLCM diagonal is calculated. It is also famous as gray tone spatial dependency matrix. The GLCM exemplifies the statistics of arrang ement of pixel gray levels in tabular form. The analysis can be lengthy further by treating entries from GLCM table. The precise form of Homogeneity is ().1, vuvupH vu−−= 3.6.3 Contrast The value of contrast supports the observer to detect the object s of an image. A balanced contrast value in the image soaks the objects which permits the more accurate image ID. By way of the value of randomness upsurges in encrypted image, it also increases the contrast to very high level. Due to nonlinearity of mappi ng, the objects of the image are slanted entirely. That is the high value of contrast in the encrypted image displays the strong encryption since it is reliably related to the confusion produced by the S -box. That is ()().,2vupvu C vu−= In the case of c onstant image, the value of contrast is zero. 3.6.4 Correlation Correlation analysis is done in three diverse ways. The vertical, horizontal and diagonal formats are designated for this purpose. By allowing for the texture of entire image, the correlation of pixel to its neighbors is examined. For the resolution, the complete image is also analyzed together with partial regions. The correlation is considered as ()()()., ,vuvuvupvvuuK−−= For a faultlessly positive or perfectly negative images, the value of cor relation is 1 or 1− respectively. And for constant image, the correlation is zero, which means that it is not a number, it is just a data type for demonstrating the redefined value. 49 3.6.5 Entropy The q uantity of randomness is measured by entropy. The degree of entropy is related with the organization of the objects in an image. The randomness of an image is enlarged by substituting nonlinear components in the system. The top level of randomness styles the image ha rd to detect. Nevertheless, due to lacking in randomness, the encrypted image is just recognized. Hereafter, the encryption strength of an encrypted image is straight measured with entropy and its mathematical form is ()(), log 0k b kn kxp xp H =−= where kx represents the histogram calculations. The results of newly proposed 8×8 S- box for this analysis are shown in T able 1 7 and Table 18 which are closed to the standard values. Images Entropy Contrast Correlation Energy Homogeneity Plain image 7.4451 0.2100 0.9444 0.1455 0.9084 Affine AES S -box 7.5710 9.6320 0.1341 0.0182 0.4669 Residue prime 𝑆8 S-box 7.5647 9.5568 0.1363 0.0184 0.4625 Table 3.8: Contrast, Correlation, Energy, Homogeneity and entropy of plain image and cipher image of Lena (512x512, png) by affine AES S -box and residue prime 𝑆8 S-box. Images Entropy Contrast Correlation Energy Homogeneity 50 Plain image 7.4451 0.2100 0.9444 0.1455 0.9084 Affine AES S-box 7.5710 9.6320 0.1341 0.0182 0.4669 residue prime 𝑆8 S- box 7.5647 9.5568 0.1363 0.0184 0.4625 AES S-box 7.2531 7.5509 0.0554 0.0202 0.4662 APA S-box 7.2531 8.1195 0.1473 0.0183 0.4676 Residue p rime S-box 7.2531 7.6236 0.0855 0.0202 0.4640 𝑆8 AES S-box 7.2357 7.4852 0.1235 0.0208 0.4707 Gray S-box 7.2531 7.5283 0.0586 0.0203 0.4623 Xyi S-box 7.2531 8.3108 0.0417 0.0196 0.4533 Skipjack S-box 7.2531 7.7058 0.1025 0.0193 0.4689 Table 3.9: Comparison of P Contrast, Correlation, Energy, Homogeneity and entropy of plain im age and cipher image of Lena (512x512, png) of affine AES S -box and residue prime 𝑆8 S-box with different S -boxes Fig 3.1: Lena image 51 Fig 3.2: Lena encrypted image by affine AES S -box Fig 3.3 : Lena encrypted image by residue prime 𝑆8 S-box 3.7 Objectives and conclusion S-boxes play very important role to make the information to more secure and reliable. Therefore , most of the work is going out for the betterment of the S -boxes and for the improving the nonlinearity and other properties. In daily life, we are always planning to make our confidential data more secure and reliable. Therefore, we can make our data more secure by achieving better nonlinear S-box and by improving the other properties. In this proposed work we have develop ed two different techniques to generate the new S - 52 boxes and then di scussed their different properties like nonlinearity, BIC, DAP, and L AP etc. We compare the strength and properties with other well known S -boxes and the comparison is given in table s. The nonlinearity of the 𝑆8 residue prime S -box do not change whereas in the case of affine AES S -boxes are decre ased. In the sec ond techniq ue we can generate finite many S -boxes with different nonlinearity. In this technique , we can get different 256 S -boxes by changing the fixed byte with different nonlinearity whereas by the action of symmetric group 𝑆8 we get 40320 S -boxes with same nonlinearity. Although for the nonlinearity point of view it has deficiency but an improvement in the strength for image encryption as shown in statistical analysis. There are still lot of works for analysis point of view of these newly constructed S -boxes and further we can apply this newly develop technique on different S -boxes to construct new S -boxes . 53