A Study on Network Security Using Symmetric Data Encryption

By
Md. Monir Hossain Mia Roll No.: 99739 & Md. Foizul Islam Chowdhury Roll No.: 99750

A thesis submitted in partial fulfillment of the requirements for the degree of Bachelor of Science in Computer Science and Engineering

Supervisor:

Muhammad Nazrul Islam Lecturer, Dept. of Computer Science and Engineering Khulna University of Engineering and Technology Bangladesh

Signature

Co-Supervisor:M. A. Matin Lecturer, Dept. of Computer Science and Engineering BRAC University Bangladesh.

Signature

Department of Computer Science and Engineering Khulna University of Engineering and Technology Khulna 9203, Bangladesh September 2004

Acknowledgments

The authors wish to express their profound gratitude to their supervisor; Muhammad
Nazrul Islam for his helpful contribution giving valuable guidance, suggestions and encouragement throughout all phases of this research based thesis work. The authors would like to thank the researchers in the field encryption and decryption algorithms s, like Vincent Rijmen Katholieke Universiteit Leuven, ESAT-COSIC K. Mercierlaan 94 B-3001 Heverlee, Belgium and Joan Daemen for providing the published papers. The authors would also like to thank Dr. Brian Gladman, for providing the proper specification of Advanced Encryption Standard (AES) in his paper on v3.11, 12th Sept 2003 which give the authors idea about the encryption and decryption scheme. The authors would also like thank Bruce Schneier, John Kelsy, Doug Whiting, David Wagner, Chris Hall, Niels Ferguson for providing the comparison among various AES submission which give the authors thorough idea on the efficiency of various encryption scheme. The authors also like to thank Mark Johnson, David Wangner, and Kannan Ramchandran, department of Electrical Engineering and computer sciences, University of California, Berkely, CA 94720, USA for providing the idea of compressing encrypted data. The authors also like to thank M.A. Matin Dept. of CSE BRAC University for his contribution in this research work. The authors also like to thank Professor Dr. M.M.A Hashem, Head Dept. of Computer Science and Engineering, Khulna University of Engineering and Technology (KUET), for his valuable advice to this research work.

The authors also like to thank all the teachers of CSE Department who helped authors in various ways throughout this research work. Authors

ii

Abstract
The

selective application of technological and related procedural safeguards is an important responsibility of every organization in providing adequate security to its electronic data systems. Protection of data during transmission or while in storage may be necessary to maintain the confidentiality and integrity of the information represented by the data. The algorithm uniquely defines the mathematical steps required to transform data into a cryptographic cipher and also to transform the cipher back to the original form. Data encryptions standard (DES) use64 bits block size as well as 64 bits key size that are vulnerable to brute-force attack. But for both efficiency and security a larger block size is desirable. In this paper, we introduce the Advanced Encryption Standard (AES) which use 128 block size as well as 128 bits key size. We also propose an algorithm which is higher secure than Rijndael algorithm but less efficient than that. The difference of efficiency between Rijndael and our propose algorithm is very negligible. We explain all this term in this paper elaborately.

iii

Table of Contents

Page
Title.....i Acknowledgement......ii Abstract.....iii Table of Contents......iv List of Figures...vi List of Tables....vii List of Illustrations and Abbreviations....viii

Chapter Title
1

Introduction
1.1 1.2 1.3 1.4 1.5

Background. ....1 Statement of the problem.....1 Goals of the thesis....2 Scope of the thesis... 2 Organization of the thesis3

Introduction to Cryptography

2.1 Definition of Cryptography ....4 2.2 Computational Difficulty ...5 2.3 To publish or Not to Publish .6 2.4 Secret Codes ...6 2.5 Breaking An Encryption Scheme ...7 2.5.1 Ciphertext only.7 2.5.2 Known Plaintext...8 2.5.2 Chosen Plaintext...8 2.6 Types of Cryptographic Functions 9 2.7 Secret Key Cryptography ..9 2.7.1 Secret Uses of Secret Key Cryptography...10 2.7.2 Transmitting Over an Insecure Channel.10 2.7.3 Secure Storage on Insecure Media.10 2.7.4 Authentication....11 2.7.5 Integrity Check...11

iv

2.8 2.9 3

Public Key Cryptography ..12 Summery....13

Finite field and Mathematical Preliminaries

3.1 Introduction. ..14 3.2 Groups, Ring, And Fields .......14 3.2.1 Groups....14 3.2.2 Rings..15 3.2.3 Fields..16 3.3 Modular Arithmetic ..........16 3.3.1 Divisors .....17 3.3.2 Properties of the Modulo Operator....17 3.3.3 Modular arithmetic operations...18 3.3.4 Properties of modular arithmetic operations..19 3.4 Finite field of the form GF(p)........21 3.4.1 Finite field of order p .....21 3.5 Finite field of the form GF(2n)..23 3.6 Modular Polynomial Arithmetic..25 3.7 Finding the Multiplicative Inverse......26 3.8 The field GF(28)..27 3.8.1 Addition....27 3.8.2 Multiplication...28 3.8.3 Multiplication by x.28 3.9 Summery...29

An Overview of AES

4.1 Introduction.....30 4.2 The Origins of AES ....30 4.3 The AES Cipher..........30 4.4 Details AES structure.......33 4.4.1 Substitute Bytes Transformation..33 4.4.1.1 Forward substitution byte transformation.33 4.4.1.2 Inverse substitution byte ransformation34 4.4.1.3 S-box construction.34 4.4.1.4 Inverse S-box construction36 4.4.2 Shift Row Transformation.37 4.4.3 Mix Column Transformation..37 4.4.4 Add round Key Transformation.40 4.5 AES Key Expansion..............41 4.6 Summary..42

Proposed algorithm

5.1 Introduction.. ..43 5.2 Mathematical preliminaries /..43 5.3 Our proposed algorithm..43 5.3.1 The round transformation.......44 5.3.2 The ByteSub transformation.....45 5.3.3 The ShiftRow transformation.....45 5.3.4 The MixColumn transformation.45 5.3.5 The Round Key addition46 5.4 Key expansion.....46 5.5 Implementation Techniques47 5.6 Advantages..47 5.7 Limitations .....48 5.8 Summery48.

Result and conclusion

6.1 6.2 6.3 6.4

Introduction49 Simulating result.....49 Conclusions ..51 Recommendations For Future Works...51

Appendices A52 References.....55

vi

List of Figures

Figure

Page

Figure 3.1: Group, Ring and field..8 Figure 4.1: AES Encryption and Decryption...9 Figure 4.2: Substitute byte transformation..11 Figure 4.3: S-box.....19 Figure 4.4: Inverse S-box...20 Figure 4.5: Shift Row transformation .23 Figure 4.6: Add round key transformation.......25 Figure 4.7: AES Key Expansion....30 Figure-5.1: Matrix representation of data block and key of our proposd system...31 Figure 5.2: Matrix multiplication for MixColumn transformation.....32 Figure 6.1: Timing comparison of both our proposed syste and Rijndael scheme.........35

vii

List of Tables

Table

Page

Table 3.1:- Arithmetic Modulo 8....34 Table 3.2: Properties of modular arithmetic for integer in Zn.....42 Table 3.3 Arithmetic in GF(7).....46 Table 3.4: Arithmetic in GF(23)...51 Table 3.5: Polynomial Arithmetic Modulo (x3 + x + 1) .......51 Table 3.6: Extended Euclid (x7 + x + 1), (x8 + x4+ x3 +x + 1) .......52

viii

List of Illustrations and Abbreviations

Illustrations/Abbreviations

Meaning

1. AESAdvanced Encryption standard 2. DES.Data Encryption standard 3. TDES..Triple Data Advanced Encryption standard 4. NIST....National Institute of Standard and technology

ix

Chapter 1

Introduction
1.1

Background

requirements of information security within an organization have undergone two major changes in the last several decades. Before the widespread use of data processing equipment, the security of information felt to be valuable to an organization was provided primarily by physical and administrative means. With the introduction of computer, the need for automated tools for protecting files and other information stored on the computer become evident. This is especially the case for a shared system, such as a time sharing-system and the need is even more acute for systems that can be accessed over a public telephone network, or the internet. Inter network security is both fascinating and complex. Security involving communications and networks is not as simple as it might first appear to the novice. The requirements seem to be straightforward; indeed, most of the major requirements for security services can be given self-explanatory. But the mechanisms used to meet those requirements can be quite complex, and understanding them may involve rather subtle reasoning. In developing a particular security mechanism or algorithm, one must always consider potential attacks on those security features. In many cases, successful attacks are designed by looking at the problem in a completely different way, therefore exploiting an unexpected weakness in the mechanism. Having designed various security mechanisms, it is necessary to decide where to use them. This is true both in terms of physical placement (e.g., at what points in a network are certain security mechanism needed) and in a logical sense [e.g., at what layer or layers of an architecture such as TCP/IP (Transmission Control Protocol/Internet Protocol) should mechanisms be placed]. Security mechanisms usually involve more than a particular algorithm or protocol. They usually also require that participants be in possession of some secret information (e.g.; an encryption key), which raises questions about the creation, distribution, and protection of that secret information.

The

1.2

Statement of The Problem

The requirement

of providing adequate security to electronic data systems grows high as the network grows rapidly in the world. To provide the security during data transmission National Institute of Standard and Technology (NIST) has published an encryption scheme known as Data Encryption Standard (DES) in 1977. But in July 1998 it has been proved insecure. So another encryption scheme require most. The principle drawback of DES is

that the algorithm is relatively sluggish in software. A secondary drawback of DES is that DES use a 64-bit block size. For reason of both efficiency and security, a larger block size is required. In this thesis we tried to expand the block size as well as the key size for the reason of increasing the security. For this we have choose the Advanced Encryption Standard (AES) as or basis, which was published by NIST in 2001, for this work.

1.3

Goals of the Thesis

aims of this research work are threefold: First is to learn about the Advanced Encryption Standard (AES) which was proposed by Rijndael. Second is to enhance the basic block size from 128 bit to 200 bit to increase the security. And third is to simulate both encryption scheme of Rijndael and our proposed system for comparing the efficiency of these two systems. Most elaborately, the aims are itemized as:

The

To know about the Advanced Encryption scheme (AES). To increase the block size as well as key size to enhancing the security in
symmetric encryption. To simulate the Rijndael proposed scheme and our proposed scheme for comparing the efficiency using 8 bit processing.

1.4

Scope of The Thesis

Protection of data during transmission or while in storage requires most to maintain the
confidentiality and integrity of the information. As the private key encryption scheme is much efficient than public key cryptography, the application of private key cryptography grows high. To provide both security and efficiency in private key encryption scheme, which is also known as symmetric encryption scheme, the block size as well as the key size has to be large. Rijndael proposed scheme has no known security attacks. Rijndael uses S-boxes as nonlinear components. It performs encryption and decryption very well across a variety of platform. In general, Rijndael is very well suited for restricted-space environments where either encryption or decryption is implemented. It supports on-the-fly subkey computation for both encryption and decryption. This study deals with the algorithm that uniquely defines the mathematical steps required to transform data into a cryptographic cipher and also to transform the cipher back to the original form.

xi

1.5

Organization of The Thesis

After this introduction, an overview private and public cryptography scheme is presented in Chapter 2.
Chapter 3 discusses and about the Group, Rings, Finite field, Extended Euclid algorithm to finding the inverse of an element and other mathematical background to get the algorithm properly Chapter 4 presents a detail description of Advanced Encryption Standard which was proposed by Rijndael. Chapter 5 presents our proposed encryption scheme Chapter 6 presents the simulation result of both our proposed scheme and Rijndael proposed Advanced Encryption Standard (AES) and the conclusions and future works.

xii

Chapter 2

Introduction to Cryptography
2.1 Definition of Cryptography

The word cryptography comes from the Greek words po (hidden or secret) and
p (written). So cryptography is the art of secret writing. More generally, people think of cryptography as the art of mangling information into apparent unintelligibility in a manner allowing a secret method of unmangling. The basic service provided by cryptography is the ability to send information between participants in a way that prevents others from reading it. In this paper we will concentrate on the kind of cryptography that is based on representing information as numbers and mathematically manipulating those numbers. This kind of cryptography can provide other services. Such as
Integrity checkingreassuring the recipient of a message that the message has not been altered since it was generated by a legitimate source Authenticationverifying someones (or somethings) identity.

But back to traditional use of cryptography. A message in its original form is known as plaintext or cleartext. The mangled information is known as ciphertext. The process for producing ciphertext from plaintext is known as encryption. The reverse of encryption is called decryption.

While cryptographers invert clever secret codes, cryptanalysis attempt to break these codes. These two disciplines constantly try to keep ahead of each other.

Cryptographic systems tend to involve both an algorithm and a secret value. The secret value is known as the key. The reason for having a key in addition to an algorithm is that it is difficult to keep devising new algorithms that will allow reversible scrambling of information, and it is difficult to quickly explain a newly devised algorithm to the person with whom you'd like to start communicating securely. With a good cryptographic scheme it is perfectly OK to have everyone, including the bad guys (and the cryptanalysts) know the algorithm because knowledge of the algorithm without the key does not help unmangle the information. The concept of a key is analogous to the combination for a combination lock. Although the concept of a combination lock is well known (you dial in the secret
xiii

numbers in the correct sequence and the lock opens). You cant open a combination lock easily without knowing the combination.

2.2

Computational Difficulty

It is important for cryptographic algorithms to be reasonably efficient for the good

guys to compute. The good guys are the ones with knowledge of the keys, Cryptographic algorithms are not impossible to break without the key. A bad guy can simply try all possible keys until one works. The security of a cryptographic scheme depends on how much work it is for the bad guy to break it. If the best possible scheme will take 10 million years to break using all of the computers in the world, then it can be considered reasonably secure. Going back to the combination lock example, a typical combination might consist of three numbers, each a number between 1 and 40. Lets say it takes 10 seconds to dial in a combination. That's reasonably convenient for the good guy. How much work is it for the bad guy? There are 403 possible combinations. Which is 64000. At 10 seconds per try, it would take a week to try all combinations though on average it would only take half that long (even though the right number is always the last one you try!). Often a scheme can be made more secure by making the key longer. In the combination lock analogy, making the key longer would consist of requiring four numbers to be dialed in. This would make a little more work for the good guy. It might now take 13 seconds to dial in the combination. But the bad guy has 40 times as many combinations to try, at 13 seconds each, so it would take a year to try all combinations. (And if it took that long, he might want to stop to eat or sleep). With cryptography, computers can be used to exhaustively try keys. Computers are a lot faster than people and they don't get tired, so thousands or millions of keys can be tried per second. Also, lots of keys can be tried in parallel if you have multiple computers, so time can be saved by spending money on more computers. Sometimes a cryptographic algorithm has a variable-length key. It can be made more secure by increasing the length of the key. Increasing the length of the key by one bit makes the good guys job just a little bit harder, but makes the bad guy's job up to twice as hard (because the number of possible keys doubles). Some Cryptographic algorithms have a fixed-length key, but a similar algorithm with a longer key can be devised if necessary. If computers get 1000 times faster, so that the bad guy's job becomes reasonably practical, making the key l0 bits longer will make the bad guys job as hard as it was before the advance in computer speed. However, it will be much easier for the good guys (because their computer speed increase far outweighs the increment in key length). So the faster computers get, the better life gets for the good guys.

xiv

Keep in mind that breaking the cryptographic scheme is often only one way of getting what you want. For instance, a bolt cutter works no matter how many digits are in the combination.

2.3

To publish or Not to Publish

Some people believe that keeping a cryptographic algorithm as secret as possible

wi11 enhance its security. Others argue that publishing the algorithm, so that it is widely known, will enhance its security. On the one hand, it would seem that keeping1he algorithm secret must be more secureit makes for more work for the cryptanalyst to try to figure out what the algorithm is. The argument for publishing the algorithm is that the bad guys will probably find out about it eventually anyway, so its better to tell a lot of nonmalicious people about the algorithm so that in case there are weaknesses, a good guy will discover them rather than a bad guy. A good guy who discovers a weakness will warn people that the system has a weakness. Publication provides an enormous amount of free consulting from the academic community as cryptanalysts look for weaknesses so they can publish papers about them. A bad guy who discovers a weakness will exploit it for doing bad-guy things like embezzling money or stealing trade secrets. It is difficult to keep the algorithm secret because if an algorithm is to be widely used, it is highly likely that determined attackers will manage to learn the algorithm by reverse engineering whatever implementation is distributed, or just because the more people who know something the more likely it is for the information to leak to the wrong places. In the past,good cryptosystems were not economically feasible, so keeping the algorithms secret was needed extra protection. We believe (we hope?) today's algorithms are sufficiently secure that this is not necessary. Common practice today is for most commercial cryptosystems to be published and for military cryptosystems to be kept secret. If a commercial algorithm is unpublished today, it's probably for trade secret reasons or because this makes it easier to get export approval rather than to enhance its security. We suspect the military ciphers are unpublished mainly to keep good cryptographic methods out of the hands of the enemy rather than to keep them from cryptanalyzing our codes.

2.4

Secret Codes

xv

We use the terms secret code and cipher interchangeably to mean any method of
encrypting data. Some people draw a subtle distinction between these terms that we don't find useful. The earliest documented cipher is attributed to Julius Caesar. The way the Caesar cipher would work if the message were in English is as follows. Substitute for each letter of the message, the letter which is 3 letters later in the alphabet (and wrap around to A from Z). Thus an A would become a D, and so forth. For instance, DOZEN would become GRCHQ. Once you figure out what's going on, it is very easy to read messages encrypted this way (unless, of course, the original message was in Greek). A slight enhancement to the Caesar cipher was distributed as a premium with Ovaltime in the 1940s as Captain Midnight Secret Decoder rings. (There were times when this might have been a violation of export controls for distributing cryptographic hardware!) The variant is to pick a secret number n between 1 and 25, instead of always using 3. Substitute for each letter of the message, the letter which is n higher (and wrap around to A from Z of course). Thus if the secret number was 1, an A would become a B, and so forth. For instance HAL would become IBM. If the secret number was 25 then IBM would become HAL. Regardless of the value of n, since there are only 26 possible ns to try, it is still very easy to break this cipher if you know it's being used and you can recognize a message once it's decrypted. The next type of cryptographic system developed is known as a monoalphabetic cipher, which consists of an arbitrary mapping of one letter to another letter. There are 26! possible pairings of letters, which is approximately 4x1026. [Remember, n!, which reads "n factorial", means n(n-1 )(n-2)...1.] This might seem secure, because to try all possibilities, if it took 1 microsecond to try each one, would take about 10 trillion years. However, by statistical analysis of language (knowing that certain letters and letter combinations are more common than others), it turns out to be fairly easy to break. For instance, many daily newspapers have a daily cryptogram, which is a monoalphabetic cipher, and can be broken by people who enjoy that son of thing during their subway ride to work. An example is Cf Iqr'xs xsnyctm n eqxxqgsy iqul qf wdcp eqqh, erl lqrx qgt iqul! Computers have made much more complex cryptographic schemes both necessary and possible. Necessary because computers can try keys at a rate that would exhaust an army of clerks; and possible because computers can execute the complex algorithms quickly and without errors.

xvi

2.5

Breaking An Encryption Scheme

What do we mean when we speak of a bad guy Fred breaking an encryption

scheme? The three basic attacks are known as ciphertext only, known plaintext, and chosen plaintext.

2.5.1 Ciphertext only

In a ciphertext only attack, Fred has seen (and presumably stored) some ciphertext
that he can analyze at leisure. Typically it is not difficult for a bad guy to obtain ciphertext. (If a bad guy can't access the encrypted data, then there would have been no need to encrypt the data in the first place!) How can Fred figure out the plaintext if all he can see is the ciphertext? One possible strategy is to search through all the keys. Fred tries the decrypt operation with each key in turn. It is essential for this attack that Fred be able to recognize when he has succeeded. For instance, if the message was English text, then it is highly unlikely that a decryption operation with an incorrect key could produce something that looked like intelligible text. Because it is important for Fred to be able to differentiate plaintext from gibberish, this attack is sometimes known as a recognizable plaintext attack. It is also essential that Fred have enough ciphertext. For instance, using the example of a monoalphabetic cipher, if the only ciphertext available to Fred were XYZ, then there is not enough information. There are many possible letter substitutions that would lead to a legal three-letter English word. There is no way for Fred to know whether the plaintext corresponding to XYZ is THE or CAT or HAT. As a matter of fact, in the following sentence, any of the words could be the plaintext for XYZ:
The hot cat was sad but you may now sit and use her big red pen.

Often it isn't necessary to search through a lot of keys. For instance, the authentication scheme Kerberos assigns to user Alice a DES key derived from Alice's password according to a straightforward, published algorithm. If Alice chooses her password unwisely (say a word in the dictionary), then Fred does not need to search through all 256 possible DES keysinstead he only needs to try the derived keys of the 10000 or so common English words. A cryptographic algorithm has to be secure against a ciphertext only attack because of the accessibility of the ciphertext to cryptanalysts. But in many cases cryptanalysts can obtain additional information, so it is important to design cryptographic systems to withstand the next two attacks as well.

xvii

2.5.2 Known Plaintext

Sometimes life is easier for the attacker. Suppose Fred has somehow obtained some
(plaintext. ciphertext) pairs. How might he have obtained these? One possibility is that secret data might not remain secret forever. For instance, the data might consist of specifying the next city to be attacked. Once the attack occurs, the plaintext to the previous day's ciphertext is now known. With a monoalphabetic cipher, a small amount of known plaintext would be a bonanza. From it, the attacker would learn the mappings of a substantial fraction of the most common letters (every letter that was used in the plaintext Fred obtained). Some cryptographic schemes might be good enough to be secure against ciphertext only attacks but not good enough against known plaintext attacks. In these cases, it becomes important to design the systems that use such a cryptographic algorithm to minimize the possibility that a bad guy will ever be able to obtain (plaintext, cipher- text) pairs.

2.5.3 Chosen Plaintext

On rare occasions, life may be easier still for the attacker. In a chosen plaintext
attack, Fred can choose any plaintext he wants, and get the system to tell him what the corresponding ciphertext is. How could such a thing be possible? Suppose the telegraph company offered a service in which they encrypt and transmit messages for you. Suppose Fred had eavesdropped on Alice's encrypted message. Now he'd like to break the telegraph company's encryption scheme so that he can decrypt Alice's message. He can obtain the corresponding ciphertext to any message he chooses by paying the telegraph company to send the message for him, encrypted. For instance, if Fred knew they were using a monoalphabetic cipher, he might send the message
The quick brown fox jumps over the lazy dog.

knowing that he would thereby get all the letters of the alphabet encrypted .and then be able to decrypt with certainty any encrypted message. It is possible that a cryptosystem secure against ciphertext only and known plaintext attacks might still be susceptible to chosen plaintext attacks. For instance, if Fred knows that Alice's message is either Surrender or Fight on, then no matter how wonderful an encryption scheme the telegraph company is using, all he has to do is send the two messages and see which one looks like the encrypted data he saw when Alice's message was transmitted.

xviii

A cryptosystem should resist all three sorts of attacks. That way its users don't need to worry about whether there are any opportunities for attackers to know or choose plaintext. Like wearing both a belt and suspenders, many systems that use cryptographic algorithms will also go out of their way to prevent any chance of chosen plaintext attacks.

2.6

Types of Cryptographic Functions

There are three kinds of cryptographic functions: hash functions, secret key functions,
and public key functions. We will describe what each kind is, and what it is useful for. Public key cryptography involves the use of two keys. Secret key cryptography involves the use of one key. Hash functions involve the use of zero keys! Try to imagine what that could possibly mean, and what use it could possibly havean algorithm everyone knows with no secret key, and yet it has uses in security. Since secret key cryptography is probably the most intuitive, we'll describe that first.

2.7

Secret Key Cryptography

Secret key cryptography involves the use of a single key. Given a message (called
plaintext) and the key, encryption produces unintelligible data (called an IRS Publication, that was just a finger slip, we mean to say ciphertext"), which is about the same length as the plaintext was. Decryption is the reverse of encryption, and uses the same key as encryption.

Secret key cryptography is sometimes referred to as conventional cryptography or symmetric cryptography. The Captain Midnight code and the monoalphabetic cipher are both examples of secret key algorithms, though both are easy to break. In this chapter we describe the functionality of cryptographic algorithms, but not the details of particular algorithms.

xix

2.7.1 Secret Uses of Secret Key Cryptography

The next few sections describe the types of things one might do with secret key
cryptography.

2.7.2 Transmitting Over an Insecure Channel

It is often impossible to prevent eavesdropping when transmitting information. For

instance, a telephone conversation can be tapped, a letter can be intercepted, and a message transmitted on a LAN can be received by unauthorized stations. If you and I agree on a shared secret (a key), then by using secret key cryptography we can send messages to one another on a medium that can be tapped, without worrying about eavesdroppers. All we need to do is have the sender encrypt the messages and the receiver decrypt them using the shared secret. An eavesdropper will only see unintelligible data. This is the classic use of cryptography.

2.7.3 Secure Storage on Insecure Media

If I have information I want to preserve but which I want to ensure no one else can
look at, I have to be able to store the media where I am sure no one can get it. Between clever thieves and court orders, there are very few places that are truly secure, and none of these is convenient. If I invent a key and encrypt the information using the key, I can store it anywhere and it is safe so long as 1 can remember the key. Of course, forgetting the key makes the data irrevocably lost, so this must be used with great care.

2.7.4 Authentication

In spy movies, when two agents who don't know each other must rendezvous, they
are each given a password or pass phrase that they can use to recognize one another. This has the problem that anyone overhearing their conversation or initiating one falsely can gain information useful for replaying later and impersonating the person to whom they are talking. The term strong authentication means that someone can prove knowledge of a secret without revealing it. Strong authentication is possible with cryptography. Strong authentication is particularly useful when two computers are trying to

xx

communicate over an insecure network (since few people can execute cryptographic algorithms in their heads). Suppose Alice and Bob share a key KAB and they want to verify they are speaking to each other. They each pick a random number, which is known as a challenge. Alice picks rA Bob picks rB. The value x encrypted with the key KAB is known as the response to the challenge x. If someone, say Fred, were impersonating Alice, he could get Bob to encrypt a value for him (though Fred wouldn't be able to tell if the person he was talking to was really Bob), but this information would not be useful later in impersonating Bob to the real Alice because the real Alice would pick a different challenge. If Alice and Bob complete this exchange, they have each proven to the other that they know KAB without revealing it to an impostor or an eavesdropper. Note that in this particular protocol, there is the opportunity for Fred to obtain some (chosen plaintext, cipher- text) pairs, since he can claim to be Bob and ask Alice to encrypt a challenge for him. For this reason, it is essential that challenges be chosen from a large enough space, say 264 values, so that there is no significant chance of using the same one twice. That is the general idea of a cryptographic authentication algorithm, though this particular algorithm has a subtle problem that would prevent it from being useful in most computer-to-computer cases. (We would have preferred not bringing that up, but felt we needed to say that so as not to alarm people who already know this stuff and who would realize the protocol was not secure.)

2.7.5 Integrity Check

A secret key scheme can be used to generate a fixed-length cryptographic

checksum associated with a message. This is a rather nonintuitive use of secret key technology. What is a checksum? An ordinary (noncryptographic) checksum protects against accidental corruption of a message. The original derivation of the term checksum comes from the operation of breaking a message into fixed-length blocks (for instance. 32-bit words) and adding them up. The sum is sent along with the message. The receiver similarly breaks up the message, repeats the addition, and checks the sum. If the message had been garbled en route, the sum will not match the sum sent and the message is rejected, unless, of course, there were two or more errors in the transmission that canceled one another. It turns out this is not terribly unlikely, given that if flaky hardware turns a bit off somewhere, it is likely to turn a corresponding bit on somewhere else. To protect against such regular flaws in hardware, more complex checksums called CRCs were devised. But these still only protect against faulty hardware and not an intelligent attacker. Since CRC algorithms are published, an attacker who wanted to change a message could do so, compute the CRC on the new message, and send that along.

xxi

To provide protection against malicious changes to a message, a secret checksum algorithm is required, such that an attacker not knowing the algorithm can't compute the right checksum for the message to be accepted as authentic. As with encryption algorithms, it's better to have a common (known) algorithm and a secret key. This is what a cryptographic checksum does. Given a key and a message, the algorithm produces a fixed-length message authentication code (MAC) that can be sent with the message. A MAC is often called a MIC (message integrity code). We prefer the term MIC, and MIC is used in standards such as PEM but the term MAC seems to have become more popular. If anyone were to modify the message and they didn't know the key, they would have to guess a MAC and the chance of getting it right depends on the length. A typical MAC is at least 48 bits long, so the chance of getting away with a forged message is only one in 280 trillion (or about the chance of going to Las Vegas with a dime and letting it ride on red at the roulette table until you have enough to payoff the U.S. national debt). Such message integrity codes have been in use to protect the integrity of large interbank electronic funds transfers for quite some time. The messages are not kept secret from an eavesdropper, but their integrity is ensured.

2.8

Public Key Cryptography

Public key cryptography is sometimes also referred to as asymmetric cryptography.

Public key cryptography is a relatively new field, invented in 1975 [DIFF76b] (at least that's the first published record-it is rumored that NSA or similar organizations may have discovered this technology earlier). Unlike secret key cryptography, keys are not shared. Instead, each individual has two keys: a private key that need not be revealed to anyone, and a public key that is preferably known to the entire world. Note that we call the private key a private key and not a secret key. This convention is an attempt to make it clear in any context whether public key cryptography or secret key cryptography is being used. Some people use the term secret key for the private key in public key cryptography, or use the term private key for the secret key in secret key technology. We hope to convince people to use the term secret key only as the single secret number used in secret key cryptography. The term private key should refer to the key in public key cryptography that must not be made public. Unfortunately, both words public and private begin with p. We will sometimes want a single letter to refer to one of the keys. The letter p won't do. We will use the letter e to refer to the public key, since the public key is used when encrypting a message. We'll use the letter d to refer to the private key, because the

xxii

private key is used to decrypt a message. Encryption and decryption are two mathematical functions that are inverses of each other.

2.9 Summery
In practical situation private key cryptography is more efficient than public key cryptography. And in this thesis paper we work on private key cryptography. This type of

xxiii

Chapter 3

Finite field and Mathematical

Preliminaries

3.1

Introduction

in the finite field GF(28). Finite fields have become increasingly important in cryptography. A number of cryptographic algorithms rely heavily on properties of finite fields, notably the AES. The chapter begins with a brief overview of the concepts of group, ring, and field. Next we introduce a brief overview of some elementary background in modular arithmetic. We are then ready to discuss finite fields of form GF(p), where p is a prime number. This chapter concludes with a discussion of finite fields of the form GF(2n ), where n is a positive integer.

Several operations in Rijndael are defined at byte level, with bytes representing elements

3.2

Groups, Ring, And Fields

Groups, rings, and fields are the fundamental elements of a branch of mathematics known
as abstract algebra, or modern algebra. In abstract algebra, we are concerned with sets on whose elements we can operate algebraically: that is we can combine two elements of the sets, perhaps in several ways, to obtain a third element of the set. These operations are subject to specific rules, which define the nature of the set. By convention the notation for the two principle classes of operations on set elements is usually the same as the notation for addition and multiplication on ordinary numbers. However, it is important to note that, in abstract algebra, we are not limited to ordinary arithmetic operations.

3.2.1 Groups A group G sometime denoted by {G, }, is a set of elements with a binary operation,
denoted by , that associate to each ordered pair (a, b) of elements in G an element (a b) in G, such that the following axioms are obeyed:1 (A1)Closure If a and b belong to G, then a b belong to G. (A2)Associative a (b c) = (a b) c for all a, b, c in G (A3)Identity element: There is an element e in G such that a e = e a = a for all a in G. (A4)Inverse element: For each a in G there is an element a in G such that a a = a a = e
______________________________________________________________________________
1

The operator is generic and can refer to addition multiplication, or some other mathematical operation

xxiv

If a group has a finite number of elements, it is referred to as a finite group, and the order of the group is equal to the number of elements in the group. Otherwise, the group is an infinite group. A group is said to be abelian if it satisfy the following additional condition:

(A5)Commutative: a b = b a for all a, in G

When the group operation is addition, the identity element is 0; the inverse element
is of a is a

Cyclic group We define exponentiation within a group as repeated application of the group operator, so that a3 = a a a. Further, we define a0 = e, the identity element; and a-n = ( a)n . A group G is cyclic if every element of G is a power ak (k is a integer) of a fixed element a G. The element a is said to generate the group G, or to be a generator of G. A cyclic group is always abelian, and may be finite or infinite.

3.2.2 Rings

A ring R sometime denoted by {R,+, x }, is a set of elements with two binary operations, called
addition and multiplication, such that for all a, b, c in R the following axioms are obeyed: (A1-A5) R is an abelian group with respect to addition; that is, R satisfies axioms A1 through A5. For this case of an additive group, we denote the identity element as 0 and the inverse of a as a. (M1) Closure under multiplication: If a and b belong to R, then ab is also in R. (M2) (M3) Associativity of multiplication: a(bc)=(ab)c for all a, b, c in R. Distributive laws: a( b + c)=ab + ac for all a, b, c in R. (a + b)c=ac + bc for all a, b, c in R.

In essence, a ring is a set in which we can do addition, subtraction[a-b=a+(-b)], and multiplication without leaving the set. A ring is said to be commutative if it satisfy the following additional condition: (M4) Commutativity of multiplication: ab=ba for all a, b in R.

Now we define an integral domain, which is a commutative ring that obeys the following axioms: (M5) Multiplicative identity: There is an element in R such that a1 = 1a = a for all a in R No zero divisor: If a,b in R and ab=0 then either a=0 or b=0.

(M6)

xxv

3.2.3 Fields

A field F, sometime denoted by {F,+, x }, is a set of elements with two binary

operation, called addition and multiplication, such that for all a, b ,c in F the following axioms are obeyed: (A1-M6) (M7) F is an integral domain; that is F satisfies axioms A1 through A5 and M1 through M6. Multiplicative inverse: For each a in F, except 0, there is an element a-1 in F such that aa-1=(a-1)a=1

In essence, a field is a set in which we can do addition, subtraction, multiplication, and division without leaving the set. Division is defined with the following rule: a / b = a( b-1)

Figure3.1: Group, Ring and field.

3.3

Modular Arithmetic

Given any positive integer n and any integer a, if we divide a by n, we get an integer
quotient q and an integer remainder r that obey the following relationship:

For example, a = 11; a = -11; n = 7; n = 7; 11 = 1 x 7 + 4; -11 = (-2) x 7 + 3; r=4 r=3

xxvi

If a is an integer and n is a positive integer, we define a mod n to be the remainder when a is divided by n. Thus for any integer a, we can write:

a=

a/n

x n + (a mod n)

Two integer a and b are said to be congruent modulo n, if ( a mod n ) = ( b mod n ) This can be written as: a b mod n.

3.3.1 Divisors

We say that a nonzero b divides a if a = mb for some m, where a, b, and m are integers. That is b divides a if there is no remainder on division. The notation b/a is commonly used to mean b divides a. Also if b/a, we say that b is a divisor of a.
The following relations hold: If a/1, then a = 1 If a/b, and b/a then a = b Any b0 divides 0 If b/g, and b/h then b/(mg + nh) for arbitrary integer m and n To see the last point, note that If b/g, then g is of the form g= b x g1 for some integer g1 If b/h, then h is of the form h= b x h1 for some integer h1 So mg+nh=mbg1 + nbh1 = b x (mg1 + nh1 ) and therefore b divides mg+nh.

3.3.2 Properties of the Modulo Operator

The modulo operator have the following properties:

1. a b mod n if n/(a-b) 2. a b mod n implies b a mod n 3. a b mod n and b c mod n imply a c mod n.

xxvii

To demonstrate the first point, if n/(a-b),then (a-b)=kn for some k. o we can write a=b+kn. Therefore (a mod n)=(remainder when b+kn is divided by n)= (remainder when b is divided by n)= (b mod n) For example: 23 = 8( mod 5) because 23-8=15=5 x 3 -11 = 5( mod 8) because -11-5= -16=8 x (-2) 81 = 0( mod 27) because 81-0=81=27 x 3 The remaining points are as easily proved.

3.3.3 Modular arithmetic operations

By definition, the ( mod n) operator maps all integers into the set of integers{0,1,..(n1)}.Modular arithmetic exhibit the following properties: 1. [( a mod n) + ( b mod n)] mod n = (a+b) mod n 2. [( a mod n) - ( b mod n)] mod n = (a-b) mod n 3. [( a mod n) x ( b mod n)] mod n = (a x b) mod n We demonstrate the first property. Define ( a mod n)= ra and ( b mod n)= rb. Then we can write a= ra +jn for some integer j and b= rb +kn for some integer k. Then (a+b) mod n =( ra +jn+ rb +kn) mod n = ( ra + rb +( k + j )n) mod n = ( ra + rb ) mod n =[( a mod n) + ( b mod n)] mod n The remaining properties are easily proved As for example: 11 mod 8=3; 15 mod 8=7 [(11 mod 8) + ( 15 mod 8)] mod 8 = 10 mod 8=2 (11+15) mod 8=26 mod 8 = 2 [(11 mod 8) - ( 15 mod 8)] mod 8 = -4 mod 8=4 (11-15) mod 8=-4 mod 8 = 4 [(11 mod 8) x ( 15 mod 8)] mod 8 = 21 mod 8=5 (11 x 15) mod 8=165 mod 8 = 5 Exponentiation is performed by repeated multiplication, as in ordinary arithmetic. For example to find 117 mod 13, we can proceed as follows: 112 = 121 4 mod 13 114 42 3 mod 13 117 11 x 4 x 3 132 2 mod 13 Thus , the rules for ordinary arithmetic involving addition, subtraction, and multiplication carry over into modular arithmetic.

xxviii

3.3.4 Properties of modular arithmetic operations

Define the set Zn as the set of nonnegative integers less then n:

Zn = {0,1,..(n-1)} This is referred as the set of residues, or residues modulo n. To be more precise, each integer in Zn represent residue class. We can label the residue classes modulo n as [0],[1],[2],.,[n-1],where [r] = {a: a is an integer, a r mod n} The residue classes modulo 4 are [0] = {,-16,-12,-8,-4,0,4,8,12,16..} [1] = {,-15,-11,-7,-3,1,5,9,13,17..} [2] = {,-14,-10,-6,-2,2,6,10,14,18..} [3] = {,-13,-9,-5,-1,3,7,11,15,19..} Of all the integers in a residue class, the smallest nonnegative integer is the one used to represent the residue class. Finding the nonnegative integer to which k is congruent modulo n is called reducing k modulo n. If we perform modular arithmetic within Zn, the properties shown in Table 4.2 hold for integers in Zn. Thus, Zn is a commutative ring with a multiplicative identity element (figure-4.1). There is one peculiarity of modular arithmetic that sets it apart from ordinary arithmetic. First, observe that, as in ordinary arithmetic, we can write the following:

Table 3.1:- Arithmetic Modulo 8

+ 0 1 2 3 4 5 6 7
0 1 2 3 4 5 6 7
0 1 2 3 4 5 6 7 1 2 3 4 5 6 7 0 2 3 4 5 6 7 0 1 3 4 5 6 7 0 1 2 4 5 6 7 0 1 2 3 5 6 7 0 1 2 3 4 6 7 0 1 2 3 4 5 7 0 1 2 3 4 5 6

(a) Addition modulo 8

xxix

0
0 0 0 0 0 0 0 0

1
0 1 2 3 4 5 6 7

2
0 2 4 6 0 2 4 6

3
0 3 6 1 4 7 2 5

4
0 4 0 4 0 4 0 4

5
0 5 2 7 4 1 6 3

6
0 6 4 2 0 6 4 2

7
0 7 6 5 4 3 2 1

0 1 2 3 4 5 6 7

(b) Multiplication Modulo 8

W
0 1 2 3 4 5 6 7

-W
0 7 6 5 4 3 2 1

W-1
--1 --3 --5 --7

( c ) Additive and multiplicative inverse modulo 8 if (a+b) ( a + c ) mod n then b c mod n For example (5+23) ( 5 + 7 ) mod 8; 23 7 mod 8 Equation 3.1 is consistent with the existence of an additive inverse. Adding the additive inverse of a to both sides of equation 3.1, we have] ((-a)+ a +b) ((-a) + a + c) mod n b c mod n However, the following statement is true only with the attached condition: If ( a x b ) mod n (a x c ) mod n Then b c mod n if a is relatively prime to n (3.2) Where the term relatively prime are defined as follows: Two integers are relatively prime if there only common positive integer factor is 1. Similar to the case of Equation (3.1), we can say that equation (3.2) is consistent with the existence of a multiplicative inverse. Applying the multiplicative inverse of a to both sides of Equation (3.1), we have ((a-1)ab) ((a-1)ac) mod n b c mod n xxx (3.1)

For example: ( 6 x 3 ) = 18 2 mod 8 ( 6 x 7 ) = 42 2 mod 8 But since 6 and 8 are not relatively prime we have 3 7 mod 8 The reason for this strange result is that for any general modulus n. a multiplier a that is applied in turn to the integer 0 through (n-1) will fail to produce a complete set of residues if a and n have any factor in common.

Table3.2: Properties of modular arithmetic for integer in Zn Property Expression Commutative laws (w + x) mod n = (x + w) mod n (w x x) mod n = (x x w) mod n Associative laws [(w + x) + y] mod n = [(w +(x + y)] mod n [(w x x) x y] mod n = [(w x (x x y)] mod n Distributive laws [w x ( x+ y)] mod n = [(w x x)+ (w x y)] mod n [w + ( xx y)] mod n = [(w +x) x (w+ y)] mod n Identities (o+w) mod n = w mod n (1x w)mod n = w mod n Additive inverse(-w) For each w Zn there exist a z such that w+z=0 mod n

3.4

Finite field of the form GF(p)

In section 3.2 we defined a field as a set that obeys all of the axioms of figure 3.1 and gave
some examples of infinite fields. Infinite fields are not of particular interest in the context of cryptography. However, finite fields play a crucial role in many cryptographic algorithms. It can be shown that the order of a finite field (number of elements in the field) must be a of a prime pn , where n is a positive integer. Here, we need to say that a prime number is an integer whose only positive integer factors are itself and 1. The finite field of order pn is generally written GF(pn): GF stands for Galois field, in honor of the mathematician who first studied finite fields. Two special cases are of interest for our purpose. For n=1, we have the finite field GF(p):this finite field has different structure than that for finite fields with n>1. In next two section we look at finite field of the form GF(p) and GF(pn) respectively.

3.4.1 Finite field of order p For a given prime, p, ther finite field of order p, GF(p) is defined as the set Zp of
integer with the arithmetic operations modulo we p. We have already shown that the set Zn of integers {0,1,..,n-1},together with the arithmetic operations modulo n. is a commutative ring. We further observed that any xxxi

integer in Zn has a multiplicative inverse if and only if that integer is relative prime to n, and therefore there exist a multiplicative inverse for all of the nonzero integers in Zn. Thus we can add the following properties to those listed in table 3.2 for Zp: Multiplicative inverse w-1 For each w Zp, w 0,there exist a z Zp such that (w x z) 1 mod p

Because w is relatively prime to p, if we multiply all the elements of Zp by w, the resulting residues are all of the elements of Zp permuted. Thus exactly one of the residues has the value 1. That integer is the multiplicative inverse of w, designated w-1. Therefore, Zp is in fact a finite field. Further equation 3.1 is consistent with the existence of a multiplicative inverse and can be rewritten without the condition. If ( a x b ) (a x c ) mod p then b c mod p (3.4)

Multiplying, both sides of Equation (3.4) by the multiplicative inverse of a, we have ((a-1) x a x b) ((a-1) x a x c) mod n b c mod n

Table 3.3 Arithmetic in GF(7) + 0 1 2 3 4 5 0 0 1 2 3 4 5 1 1 2 3 4 5 6 2 2 3 4 5 6 0 3 3 4 5 6 0 1 4 4 5 6 0 1 2 5 5 6 0 1 2 3 6 6 0 1 2 3 4 (a) Addition modulo 7 X 0 1 2 3 4 5 6 0 0 0 0 0 0 0 0 1 0 1 2 3 4 5 6 2 0 2 4 6 1 3 5 3 0 3 6 2 5 1 4 4 0 4 1 5 2 6 3 5 0 5 3 1 6 4 2

6 6 0 1 2 3 4 5

6 0 6 5 4 3 2 1

(b)Multiplication modulo 7

xxxii

w
0 1 2 3 4 5 6

-w 0 6 5 4 3 2 1

w-1
--1 4 5 2 3 6

(c) Additive and multiplicative inverse modulo 7

3.5

Finite field of the form GF(2n)

Virtually all encryption algorithms, both symmetric and public key involve and
arithmetic operations on integers. If one of the operations that is used in the algorithm is division then we need to work in arithmetic defined over a field. For convenience and for implementation efficiency, we would also like to work with integers that fit exactly into a given number of bits, with no wasted bit patterns. That is we wish to work with the integers in the range 0 through 2n -1, which fit into an n-bit word.Suppose we wish to define a conventional encryption algorithm that operates on data 8 bits at a time and we wish to perform division with 8 bits we can represent integers in the range 0 through 255. However, 256 is not a prime number, so that if arithmetic is performed in Z256 (arithmetic modulo 256), this set of integers will not be a field. The closest prime number less then 256 is 251. Thus the set Z251, using arithmetic modulo 251, is a field. However, in this case the 8 bit patterns representing the integers 251 through 255 word not be used, resulting in inefficient use of storage.
As for the preceding example points out, if all arithmetic operations are to be used, and we wish to represent a full range of integers in n bits, then arithmetic modulo 2n will not work; equivalently, the set of integers modulo 2n, for n>1, is not a field. Furthermore, even if the encryption algorithm uses only addition and multiplication, But not division, the use of the set Z2n is questionable, as the following example illustrates. Suppose we wish to use 3-bit blocks m our encryption algorithm, and use only the operations of addition and multiplication. Then arithmetic modulo 8 is well defined as shown in table 1. However, note that in the multiplication table, the nonzero integers do not appear an equal number of times. For example, there are only four occurrences of 3, but twelve occurrences of 4. On the other hand, as was mentioned, there are finite fields of the form GF(2n), so there is in particular a finite field of order 23 = 8. Arithmetic for these

xxxiii

fields is shown in table 2. In this case, the number of occurrences of the nonzero integers is uniform. To summarize, Integer Occurrences in Z8 Occurrences in GF(23) 1 4 7 2 8 7 3 4 7 4 12 7 5 4 7 6 8 7 7 4 7

Intuitively, it would seem that an algorithm that maps the integers unevenly onto themselves might be cryptographically weaker than one that provides a uniform mapping. Thus, the finite fields of the form GF(2n) are attractive for cryptographic algorithms. Table 3.4: Arithmetic in GF(23) 000 001 010 011 100 101 110 111 0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7 1 0 3 2 5 4 7 6 2 3 0 1 6 7 4 5 3 2 1 0 7 6 5 4 4 5 6 7 0 1 2 3 5 4 7 6 1 0 3 2 6 7 4 5 2 3 0 1 7 6 5 4 3 2 1 0 (a) Addition

000 001 010 011 100 101 110 111

+ 0 1 2 3 4 5 6 7

000 001 010 011 100 101 110 111

X 0 1 2 3 4 5 6 7

000 001 010 011 100 101 110 111 0 1 2 3 4 5 6 7 0 0 0 0 0 0 0 0 0 1 2 3 4 5 6 7 0 2 4 6 3 1 7 5 0 3 6 5 7 4 1 2 0 4 3 7 6 2 5 1 0 5 1 4 2 7 3 6 0 6 7 1 5 3 2 4 0 7 5 2 1 6 4 3 (b) Multiplication w-1 --1 5 6 7 2 3 4

w 0 1 2 3 4 5 6 7

-w 0 1 2 3 4 5 6 7

xxxiv

(c) Additive and Multiplicative inverse

3.6

Modular Polynomial Arithmetic

Consider the set S of all polynomials of degree n-1 or less over the field Zp. Thus, each
polynomial has the form

Where each ai takes on a value in the set {0, 1 P 1}. There are a total of pn different polynomials in S. With the appropriate definition of arithmetic operations, each such set S is a a finite field. The definition consists of the following elements: 1. Arithmetic follows the ordinary rules of polynomial arithmetic using the basic rules of algebra, with the following two refinements. 2. Arithmetic on the coefficients is performed modulo p. That is, we use the rules of arithmetic for the finite field Zp. 3. If multiplication result in a polynomial of degree greater than n-1, then the polynomial is reduced modulo some irreducible polynomial m(x) of degree n. That is, we divide by m(x) and keep the remainder for a polynomial f(x), the remainder s expressed as r(x)=f(x) mod m(x). As with ordinary modular arithmetic, we have the notion of a set of residues in modular polynomial arithmetic. The set of residues modulo m(x), an nth-degree polynomial, consist of pn elements. Each of these elements is represented by one of the pn polynomials of degree m<n. The residue class [x+1], modulo m(x), consist of all polynomials a(x) such that a(x) (x+1) mod m(x). Equivalently the residue class [x+1] consist of all polynomial a(x) that satisfy the equality a(x) mod m(x) = (x+1). To construct the finite field GF(23), we need to choose an irreducible polynomial of degree 3. There are only two such polynomial: (x3 + x2 + 1) and (x3 + x + 1). Using the latter, table 3.5 shows the addition and multiplication table for GF(23).

xxxv

Table 3.5: Polynomial Arithmetic Modulo (x3 + x + 1)

000 001 1 1 0 x+1 x 2 x +1 2 x 2 x +x+1 2 x +x x x x+1 0 1 2 x +x 2 x +x+1 2 x 2 x +1 010 011 x+1 x+1 x 1 0 2 x +x+1 2 x +x 2 x +1 2 x 100 2 x 2 x 2 x +1 2 x +x 2 x +x+1 0 1 x x+1 101 2 x +1 2 x +1 2 x 2 x +x+1 2 x +x 1 0 x+1 x 110 2 x +x 2 x +x 2 x +x+1 2 x 2 x +1 x x+1 0 1 111 2 x +x+1 2 x +x+1 2 x +x 2 x +1 2 x x+1 x 1 0

+
0 1 x x+1 2 x 2 x +1 2 x +x 2 x +x+1

0 0 1 x x+1 2 x 2 x +1 2 x +x 2 x +x+1

000 001 010 011 100 101 110 111

(a)Addition

000

001 1 0 1 x x+1 2 x 2 x +1 2 x +x 2 x +x+1 x 0 x 2 x 2 x +x x+1

010 x+1 0

011 2 x 0 2 x

100

101 2 x +1 0 2 x +1 1 2 x x 2 x +x+1 x+1 2 x +x

110 2 x +x 0 2 x +x 2 x +x+1 1 2 x +1 x+1 x 2 x

111 2 x +x+1 0 2 x +x+1 2 x +1 x 1 2 x +x 2 x x+1 000 001 010 011 100 101 110 111

X
0 1 x x+1 2 x 2 x +1 2 x +x 2 x +x+1

0 0 0 0 0 0 0 0 0

1 2 x +x+1 2 x +1

x+1 2 x +x 2 x +1 2 x +x+1 2 x 1 x

x+1 2 x +x+1 2 x +x x 2 x +1 1

(b) Multiplication

3.7

Finding the Multiplicative Inverse

Just as Euclids algorithms can be adapted to find the greatest common devisor of two one
polynomials, the expended Euclids algorithm can be adapted to find the multiplicative inverse of a polynomial. Specially, the algorithm will find the multiplicative inverse of b(x) modulo m(x) if the degree of b(x) is less than the degree of m(x) and gcd[m(x),b(x) = 1. If m(x) is an irreducible polynomial, then it has no factor other than itself or 1, so that gcd[m(x),b(x)] = 1. The algorithm is as follows: Extended Euclid [m(x), b(x)] 1. [A1(x),A2(x),A3(x)] [1,0,m(x)]; [B1(x), B2(x), B3(x)] [0,1,b(x)] 2. if B3(x) = 0 return A3(x) = gcd[m(x),b(x); no inverse 3. if B3(x) = 1 return B3(x) = gcd[m(x),b(x); B2(x) = b(x)-1mod m(x) 4. Q(x) = quotient of A3(x)/B3(x) 5. [T1(x),T2(x),T3(x)][A1(x) Q(x)B1(x), A2(x) Q(x)B2(x), A3(x) QB3(x)] 6. [A1(x),A2(x),A3(x)][B1(x),B2(x),B3(x)] 7. [B1(x),B2(x),B3(x)] [T1(x),T2(x),T3(x)] 8. goto 2

xxxvi

Table 3.6 shows the calculation of the multiplicative inverse of (x7 + x + 1)mod (x8 + x4 + x3 + x + 1). The result is (x7 + x + 1)-1 = (x7). That is, (x7 + x + 1) (x7) 1 mod (x8 + x4 + x3 + x + 1)

Table 3.6: Extended Euclid (x7 + x + 1), (x8 + x4+ x3 +x + 1) Initialization A1(x)=1; A2(x)=0; A3(x)= x8 + x4+ x3 +x + 1 B1(x)=0; B2(x)=1; B3(x)= x7 + x + 1 Iteration 1 Q(x)=x A1(x)=0; A2(x)=1; A3(x)= x7 + x + 1 B1(x)=1; B2(x)=x; B3(x)= x4+ x3 +x2 + 1 Iteration 2 Q(x)= x3 + x2 + 1 A1(x)=1; A2(x)=x; A3(x)= x4+ x3 +x2 + 1 B1(x)= x3 + x2 + 1; B2(x)= x4 + x3+ x +1; B3(x)= x Iteration 3 Q(x)= x3 + x2 + x A1(x)= x3 + x2 + 1; A2(x)= x2 + 1; A3(x)= x B1(x)= x6+ x2 +x + 1; B2(x)= x7 ; B3(x)= 1 Iteration 4 B3(x)= gcd[(x7 + x + 1), (x8 + x4+ x3 +x + 1)]=1 B2(x)= (x7 + x + 1)-1 mod (x8 + x4+ x3 +x + 1) = x7

3.8 The field GF(28)

elements of a finite field [LiNi86] can be represented in several different ways. For any prime power there is a single finite field, hence all representations of GF(28) are isomorphic. Despite this equivalence, the representation has an impact on the implementation complexity. We have chosen for the classical polynomial representation. A byte b, consisting of bits b7 b6 b5 b4 b3 b2 b1 b0, is considered as a polynomial with coefficient in {0, 1}: b7 x7 + b6 x6 + b5 x5 + b4 x4 + b3 x3 + b2 x2 + b1 x + b0 Example: the byte with hexadecimal value 57 (binary 01010111) corresponds with polynomial: x6 + x4 + x2 + x + 1 .

The

3.8.1 Addition
the polynomial representation, the sum of two elements is the polynomial with coefficients that are given by the sum modulo 2 (i.e., 1 + 1 = 0) of the coefficients of the two terms. Example: 57 + 83 = D4, or with the polynomial notation:

In

xxxvii

( x6 + x4 + x2 + x + 1 ) + ( x7 + x + 1) = x7 + x6 + x4 + x2 . In binary notation we have: 01010111 + 10000011 = 11010100. Clearly, the addition corresponds with the simple bitwise EXOR (denoted by ) at the byte level. All necessary conditions are fulfilled to have an Abelian group: internal, associative, neutral element (00), inverse element (every element is its own additive inverse) and commutative. As every element is its own additive inverse, subtraction and addition are the same.

3.8.2 Multiplication

In the polynomial representation, multiplication in GF(28) corresponds with multiplication

of polynomials modulo an irreducible binary polynomial of degree 8. A polynomial is irreducible if it has no divisors other than 1 and itself. For Rijndael, this polynomial is called m( x ) and given by m( x ) = x8 + x4 + x3 + x + 1 or 11B in hexadecimal representation. Example: 57 83 = C1, or: ( x6 + x4 + x2 + x + 1) ( x7 + x + 1) = x13 + x11 + x9 + x8 + x7 + x7 + x5 + x3 + x2 + x + x6 + x4 + x2 + x + 1 x13 + x11 + x9 + x8 + x6 + x5 + x4 + x3 + 1

x13 + x11 + x9 + x8 + x6 + x5 + x4 + x3 + 1 modulo x8 + x4 + x3 + x + 1 = x7 + x6 + 1 Clearly, the result will be a binary polynomial of degree below 8. Unlike for addition, there is no simple operation at byte level. The multiplication defined above is associative and there is a neutral element (01). For any binary polynomial b(x) of degree below 8, the extended algorithm of Euclid can be used to compute polynomials a(x), c(x) such that b(x) a(x) + m(x) c(x) = 1 . Hence, a(x) b(x) mod m(x) = 1 or b-1(x) = a(x) mod m(x) Moreover, it holds that a(x) ( b(x) + c(x)) = a(x) b(x) + a(x) c(x). It follows that the set of 256 possible byte values, with the EXOR as addition and the multiplication defined as above has the structure of the finite field GF(28).

xxxviii

3.8.3 Multiplication by x

If we multiply b(x) by the polynomial x, we have:

b7x8 + b6 x7 + b5 x6 + b4 x3 + b3 x4 + b2 x3 + b1 x2 + b0 x x b( x ) is obtained by reducing the above result modulo m( x ). If b7 = 0, this reduction is the identity operation, If b7 = 1, m(x) must be subtracted (i.e., EXORed). It follows that multiplication by x (hexadecimal 02) can be implemented at byte level as a left shift and a subsequent conditional bitwise EXOR with 1B. This operation is denoted by b = xtime(a). In dedicated hardware, xtime takes only 4 EXORs. Multiplication by higher powers of x can be implemented by repeated application of xtime. By adding intermediate results, multiplication by any constant can be implemented. Example: 57 13 = FE 57 02 = xtime(57) = AE 57 04 = xtime(AE) = 47 57 08 = xtime(47) = 8E 57 10 = xtime(8E) = 07 57 13 = 57 (01 02 10 ) = 57

AE

07 = FE

3.9 Summery:

The

whole mathematics are which are described are required to understanding our proposed algorithm as well as the Rijndael algorithm.

xxxix

Chapter 4

An Overview of AES
4.1 Introduction

The Advance Encryption Standard (AES) was published by NIST (National Institute of
Standard and Technology) in 2001. AES is a symmetric block cipher that is intended to replace DES as the approved standard for a wide range of applications. In this chapter we give an overview description of the AES.

4.2 The Origins of AES In 1999, NIST issued a new version of its DES standard that indicates that DES should
only be used for legacy systems and that triple DES (3DES) be used. 3DES has two attractions that assure its widespread use over the next few years. First, with its 168 bit key length, it overcomes the vulnerability to brute-force attack of DES. Second, the underlying encryption algorithm in 3DES is the same as in DES. The principal drawback of 3DES is that the algorithm is relatively sluggish in software. The original DES was designed for mid-1970s hardware implementation and does not produce efficient software code. 3DES, which has three times as many rounds as in DES, is correspondingly slower. A secondary drawback is that both DES and 3DES use a 64-bit block size. For reasons of both efficiency and security, a larger block size is desirable. Because of these drawbacks, 3DES is not a reasonable candidate for long-term use. As a replacement, NIST in 1997 issued a call for proposals for a new Advance Encryption Standard (AES), which should have a security strength equal to or better than 3DES and significantly improved efficiency. In addition to these general requirements, NIST specified that AES must be a symmetric block cipher with a block length of 128 bits and support for key lengths of 128, 192, and 256 bits. The two researchers who developed and submitted Rijndael for the AES are both cryptographers from Belgium: Dr. Joan Daemen and Dr. Vincent Rijmen.

4.3

The AES Cipher

The Rijndale proposal for AES defined a cipher in which the block length and the key
length can be independently specified to be 128,192,256 bits. The AES specification uses the same three key size alternatives but limit the block length to 128 bits. The algorithms have the following characteristics.

xl

Resistance against all Known attacks Speed and code compactness on a wide range of platforms. Design simplicity

The fig-4.1 shows the overall structure of AES. The input to the encryption and decryption algorithms is a single 128-bit block. This block can be depicted as a square matrix of bytes. This block is copied into the state array, which is modified at each step of encryption or decryption. After the final stage, state is copied to a output matrix. This operation is depicted in fig-2a. Similarly the 128-bit key is depicted as a square matrix of bytes. This key is then expanded into an array of key schedule words; each word is four bytes and the total key schedule is 44 words for the 128-bit key (fig-2b). Note that the ordering of bytes within a matrix is by column. So, for example, the 1st four bytes of a 128 bit plaintext input to the encryption cipher occupy the 1st column of the in matrix, the 2nd four bytes occupy the second column, and so on. Similarly, the 1st four bytes of the expanded key, which form a word, occupy the 1st column of the w matrix. Before delving into details, we can make several comments about the overall AES structure. 1. One noteworthy feature of this feature is that it is not Feistel structure. 2. The key that is provided as input is expanded into an array of forty-four 32bit words, w[i]. Four distinct words (128-bits) serve as a round key for each round; these are indicated in fig-1. 3. Four different stages are used, one of permutation and three of substitution. Substitute byte: Uses an S-box to perform a byte-by-byte substitution of the block Shift rows: A simple permutation. Mix columns: A substitution that makes use of arithmetic over GF(28) Add round key: A simple bitwise XOR of the current block with a portion of the expand key. 4. The structure is quite simple. For both encryption and decryption, the cipher begins with an add round key stage, followed by 9 rounds that each includes all four stages, followed by a 10th round of three stage. Fig-3 depicts the structure of a full encryption round. 5. Only the Add round key stage makes use of the key. For this reason, the cipher begins and ends with an Add round key stage. Any other stage, applied at the beginning or end, is reversible without knowledge of the key and so would add no security. 6. The Add round key stage, in effect, a form of Vernam cipher and by itself would not be formidable. The other three stages together provide confusion, diffusion, and nonlinearity, but by themselves would provide no security because they do not use the key. We can view the cipher as alternative operations of XOR encryption (Add round key) of a block, followed by scrambling of the block (the other three stages), followed by XOR encryption, and so on. This scheme is both efficient and highly secure. 7. Each stage is easily reversible. For the substitute byte, Shift Row, and mix column stage, an inverse function is used in the decryption algorithm. For

xli

the Add round key stage, the inverse is achieved by XORing the same round key to the block, using the result A A B = B. 8. As with most block ciphers, the decryption algorithm makes use of the expanded key in reverse order. However, the decryption algorithm is not identical to the encryption algorithm. This is a consequence of of the particular structure of AES. 9. Once it is established that all four stage are reversible, it is easy to verify that decryption does recover the plaintext. Fig-4.1 lays out encryption and decryption going in opposite vertical direction. At each horizontal point (e.g., the dashed line in the figure), state is the same for both encryption and decryption. 10. The final round of both encryption and decryption consost of only three stage. Again, this is a consequence of the particular structure of AES and is required to make the cipher reversible.

Figure 4.1: AES Encryption and Decryption

xlii

4.4 Details AES structure We now turn to a discussion of each of the four stages used in AES. For each stage, we
describe the forward (encryption) algorithm, the inverse (decryption) algorithm, and the rationale for the stages. This is followed by a discussion of key expansion. The AES uses arithmetic in the finite field GF(28 )with the irreducible polynomial m(x) = x8 + x4 + x3 + x + 1. The developers of Rijndael gives as their motivation for selecting this one of the 30 possible irreducible polynomials of degree 8 that it is the 1st one on the list given in[LIDL94].

4.4.1 Substitute Bytes Transformation

4.4.1.1 Forward substitution byte transformation

AES defines a 16 X 16 matrix of bytes values, called an S-box that contains a permutation
of all possible 256 8-bit values. Each individual byte of state is mapped into a new byte in the following way: The leftmost 4 bits of the byte are used as a row value and the rightmost 4 bits are used as a column value. These row and column values serve as indexes into the S-box to select a unique 8-bit output value. For example, the hexadecimal value {95} references row 9, column 5 of the S-box, which contains the value {2A}. Accordingly, the value {95} is mapped into the value {2A}.

Here is an example of the Sub Bytes transformation:

xliii

Fig 4.2: Substitute byte transformation

4.4.1.2

Inverse substitution byte transformation

The inverse substitution byte transformation, called InvSubBytes, makes use of the inverse
S-box. For example, the input {2A} produces the output {95}, and the input {95} to the Sbox produces {2A}.

4.4.1.3

S-box construction

The S-box is constructed in the following fashion:

1. Initialize the S-box with the byte values in ascending sequence row. The 1st row contains {00},{01},{02},......................,{0F}; the second row contains {10},{11},{12},......................,{1F}; and so on. 2. Take the multiplicative inverse in the finite field GF(28); the element {00} is mapped to itself. 3. Apply the following transformation to each bit of each byte in the S-box:

. (4.1) Where Ci is the ith bit of a byte C with the value {63} or {01100011}.

The AES standard depicts this transformation in matrix form as follows:

xliv

........................................ (4.2)

Example: AES S-Box

Fig 4.3: S-box

xlv

Consider the input value {95}. The multiplicative inverse in GF(28) is {95}-1 ={8A} which is 10001010 in binary. Using Equation (4.2):

The result is {2A}, which should appear in row {09} column {05} of S-box. This is verified by checking Table Fig 4.3.

4.4.1.4

Inverse S-box construction

(1) followed by taking the multiplicative inverse in GF(28). The inverse transformation is

The inverse S-box is constructed by applying the inverse of the transformation in equation

Where byte d = {05}, or 00000101. We can depict this transformation as follows:

Fig 4.4: Inverse S-box

xlvi

4.4.2 Shift Row Transformation

second row, a 1-byte circular left shift is performed. For the 3rd row, a 2-byte circular left shift is performed. For 3-byte circular left shift is performed.

In forward shift row transformation, called ShiftRows, first row is not altered. For

The inverse shift row transformation, called InvShiftRows, performs the circular shifts in the opposite direction for each of the last three rows, with a one-byte circular right shift for the second row, and so on.

Figure 4.5: Shift Row transformation The following is an example of ShiftRows:

4.4.3 Mix Column Transformation

Mix Column operates on each column individually. Each byte of a column is mapped into
a new value that is a function of all four bytes in the column. The transformation can be defined by the following matrix multiplication:

xlvii

.(4.3) Each element in the product matrix is the sum of products of elements of one row and one column. In this case, the indivisual addition and multiplication are performed in GF(28 ) .The mix columns transformation on a single column j can be expressed as:

.(4.4) Example:
The following is an example of MixColumns:

Let us verify the 1st column of this example. In GF(28), addition is the bitwise XOR operation. In particular, multiplication of a value by x (i.e., by {02}) can be implemented as a 1-bit left shift followed by a conditional bitwise XOR with (00011011) if the leftmost bit of the original value (prior to the shift) is 1. Thus, to verify the MixColumns transformation on the first column, we need to show that:

xlviii

For the first equation, we have {02} {87} = (00001110) (00011011) = (00010101) and {03} {6E} = {6E} ({02}{6E}) = (01101110) (11011100) = (10110010).Then {02} {87} = 00010101 {03} {6E} = 10110010 {46} = 01000110 {A6 } = 10100110 01000111 = {47} The other equations can be similarly verified. The inverse mix column transformation, called InvMixcolumn, is defined by the following matrix multiplication

.(5.5) It is not immediately clear that Equation (5.5) is the inverse of Equation (5.3). We need to show that

xlix

(5.6) That is the inverse transformation matrix times the forward transformation matrix equals the identity matrix. To verify the first column of Equation (5.6), we need to show that ({0E} {02}) ({09} {02}) ({0D} {02}) ({0B} {02}) {0B} {0D} ({09} {03}) = {01} {0E} {0B} ({0D} {03}) = {00} {09} {0E} ({0B} {03}) = {00} {0D} {09} ({0E} {03}) = {00}

For the first equation, we have {0E}{02}= 00011100; and {09}{03}= {09} ({09}{02}) = 00001001 00010010 = 0001011. Then

{0E}{02}= {0B} = {0D} = {09} {03}=

00011100 00001011 00011011 00011011 00000001

The other equation can be similarly verified The AES document describes another way of characterizing the MixColumns transformation, which is in terms of polynomial arithmetic. In the standard, MixColumns is defined by considering each column of State to be a four-term polynomial with coefficient in GF(28). Each column is multiplied modulo (x4+1) by the fixed polynomial a(x), given by a(x) = {03}x3 + {01}x2 + {01}x + {02} (5.7)

Appendix A demonstrates multiplication of each column of state by a(x) can be written as the matrix multiplication of Equation (5.3). Similarly, it can be seen the transformation of Equation (4.5) corresponds to treating each column as a four-term polynomial and multiplying each column by b(x), given by b(x) = {0B}x3 + {0D}x2 + {09}x + {0E} It can readily be shown that b(x) = a-1(x) mod (x4+1). (4.8)

4.4.4 Add round Key Transformation

In the forward add round key transformation, called AddroundKey, the 128 bits of state are bitwise XORed with the 128 bits of the round key. As shown in Fig-4b, the operation is viewed as a columnwise operation between the 4 bytes of a state column and one word of the round key; it can also be viewed as a byte-level operation.

Figure4.6: Add round key transformation

The following is an example of AddRoundKey:

4.5 AES Key Expansion

The AES key expansion algorithm takes as input a 4-word (16-bytes) key and produces a
linear array of 44 words (156-bytes). This is sufficient to provide a 4-word round key for the initial Add round Key stage and each of the 10 rounds of the cipher. The following pseudocode describes the expansion: KeyExpansion(byte key[16],word w[44]) { word temp; for(I=0;I<4;I++) w[I]=(key[4*I],key[4*I+1],key[4*I+2],key[4*I+3]); li

for(I=4;I<44;I++) { temp=w[I-1]; if(I mod 4 = 0) temp = Subword (Rotword(temp)) w[I]=w[I-1] temp; } }

Rcon[i/4];

The key is copied into the 1st four words of the expanded key. The remainder of the expanded key is filled in four words at a time. Each added word w[I] depends on the immediately preceding word w[I-1], and the word four position back w[I-4]. In three out of four cases, a simple XOR is used. For a word whose position in the w array is a multiple of 4,a more complex function is used. Figure 6 illustrate the generation of the 1st eight words of the expanded key, using the symbol g to represent that complex function. The function g consist of the following subfunction 1. RotWord performs a one byte circular left shift on a word. This means that an input word [b0,b1,b2,b3] is transformed into [b1,b2,b3,b0]. 2. SubWord perform a byte substitution on each byte of itd input word, using the Sbox 3. The result of steps 1 and 2 is XORed with a round constant Rcon[j] The round constant is a word in which the three rightmost bytes are always 0.Thus the effect of an XOR of a word with Rcon is to only perform an XOR on the leftmost byte of the word. The round constant is different for each round and is defined as Rcon[j]= (RC[j],0,0,0), with RC[1]=1,RC[j]=2RC[j-1] and with multiplication defined over the field GF(28).The values of RC[j] in hexadecimal are

1 RC[j] 01

2 02

3 04

4 08

5 10

6 20

7 40

8 80

9 1B

10 36

lii

Fig 4.7: AES Key Expansion

4.6 Summery: This is the complete

description of Rijndael proposed Advanced Encryption Standard (AES) which is presently use in many application.

liii

Chapter 5

Our proposed algorithm

5.1 Introduction In this chapter we describe about our proposed symmetric cipher. Our proposed algorithm is much
more similar to that of Rijndael. The difference is that in Rijndael algorithm the block size start from 128bits and then increase by appending column [Rijn99] whereas the basic block size of our algorithm is 200bits and then the size can be increased by appending column. We describe the cipher of our proposed algorithm first. The mathematical basis necessary for getting the algorithm was described previously. Here we describe the algorithm.

5.2 Mathematical preliminaries Our proposed algorithm use several operations that are defined at byte level, with bytes
representing elements in the finite field GF(28).

5.3 Our proposed algorithm The different transformations operate on the intermediate result, called the State: Definition: the intermediate cipher result is called the State. The State can be pictured as a
rectangular array of bytes. This array has five rows; the number of columns is denoted by Nb and is equal to the block length divided by 40.

As the security is the function of block length and the size of key length, we increase the block length as well as the key length. Our basic block length is 200 bits which can be shown as a 5 by 5 matrix of byte. This is illustrated in figure5.1.We can increase our block by appending a column at a time. But we like to emphasize on 200 bit and then compare the security & efficiency between our 200 bits block cipher and Rijndael 128 bits cipher.

Figure-5.1: Matrix representation of data block and key of our proposd system

liv

The input and output used by our proposed algorithm at its external interface are considered to be one dimensional arrays of 8-bit bytes numbered upwards from 0 to the 5*Nb-1. The Cipher Key is considered to be a one-dimensional arrays of 8-bit bytes numbered upwards from 0 to the 5*Nk-1. The cipher input bytes (the plaintext if the mode of use is ECB encryption) are mapped onto the state bytes in the order a0,0, a1,0, a2,0, a3,0, a4,0, a0,1, a1,1, a2,1, a3,1, a4,1 ... , and the bytes of the Cipher Key are mapped onto the array in the order k0,0, k1,0, k2,0, k3,0, k4,0, k0,1, k1,1, k2,1, k3,1, k4,1 ... At the end of the cipher operation, the cipher output is extracted from the state by taking the state bytes in the same order. Hence if the one-dimensional index of a byte within a block is n and the two dimensional index is ( i ,j ), we have:

i = n mod 5 ;

j= n/5 ;

n=i+ 5* j

5.3.1 The round transformation

The round transformation is composed of four different transformations. It is similar to

that of Rijndael. In pseudo C notation we have: Round(State,RoundKey) { ByteSub(State); ShiftRow(State); MixColumn(State); AddRoundKey(State,RoundKey); }

The final round of the cipher is slightly different. It is defined by:

FinalRound(State,RoundKey) { ByteSub(State) ; ShiftRow(State) ; AddRoundKey(State,RoundKey); } In this notation, the functions (AddRound, ByteSub, ShiftRow ) operate on arrays to which pointers (State, RoundKey) are provided. It can be seen that the final round is equal to the round with the MixColumn step removed. The component transformations are specified in the following subsections.

lv

5.3.2 The ByteSub transformation The Bytesub transformation is similar as that of Rijndael Substitute Bytes Transformation which has already been described in previous chapter. For increasing the efficiency we have use the S-box that are use by Rijndael proposed scheme which has no known security attack. 5.3.3 The ShiftRow transformation For encryption the 1st row remain unchanged, 2nd Row is shifted 1 byte to the left,3rd is 2
byte to the left 4th is 3 byte to the left and 5th row is shifted 4 byte to the left. For decryption the operation is similar to that for encryption but in reverse direction.

5.3.4 The MixColumn transformation

In MixColumn, the columns of the State are considered as polynomials over GF(28) and multiplied modulo x5 + 1 with a fixed polynomial c( x ), given by c( x ) = 04 x4 + 03 x3 + 01 x2 + 01 x +02 This polynomial is coprime to x5 + 1 and therefore invertible. This can be written as a matrix multiplication. Let b(x) = c(x) a(x),

Fig 5.2:Matrix multiplication for MixColumn transformation The application of this operation on all columns of the State is denoted by MixColumn(State). The inverse of MixColumn is similar to MixColumn. Every column is transformed by multiplying it with a specific multiplication polynomial d( x ), defined by (04 x4 + 03 x3 + 01 x2 + 01 x +02) d( x ) = 01 . This polynomial d( x ) is given by: d( x ) = 7D x4 + 09 x3 + 8A x2 + 4C x + E0 .

lvi

5.3.5 The Round Key addition

In this operation, a Round Key is applied to the State by a simple bitwise EXOR. The
Round Key is derived from the Cipher Key by means of the key schedule. The transformation that consists of EXORing a Round Key to the State is denoted by: AddRoundKey(State,RoundKey).

5.4 Key expansion The Expanded Key is a linear array of 5-byte. Every variable represent byte. In c code this
is given as follows: keyexpansion(unsigned short int *key,unsigned short int *expandkey) { unsigned short int temp[5], *temp1; int i, j; for(i=0;i<5;i++){ for(j=0;j<5;j++){ expandkey [i*5+j]=key[i*5+j]; } } for(i=5;i<55;i++){ for(j=0;j<5;j++) temp[j]= expandkey [(i-1)*5+j]; if(i%5==0){ temp1=subword (rotbyte (temp)); for (j=0;j<5;j++) temp[j]=temp1[j]; temp[0]=temp[0] ^ Rcon[i/5-1]; } for(j=0;j<5;j++) expandkey [i*5+j]= expandkey [(i-5)*5+j]^temp[j]; } } Note: Here we expand key for 10 round. And the rotbyte and subbyte is stand for rotation of byte in a single vector and substitute a byte using S-box. Rcon[I] is defined in previous chapter.

5.5 Implementation Techniques In the pseudo code in this section the following symbols will be used:
* & | a pointer to a variable bits in result are the AND of the corresponding bits in the two operands bits in result are the OR of the corresponding bits in the two operands

lvii

^ >> << <> 0x.

bits in result are the XOR of the corresponding bits in the two operands right shift of left operand by amount given by right operand left shift of left operand by amount given by right operand not equal hexadecimal value

5.6 Advantages Implementation aspects:

Our proposed algorithm can be implemented to run at speeds unusually fast for a block cipher on a Pentium (Pro). There is a trade-off between table size/ performance. Our proposed algorithm can be implemented on a Smart Card in a small amount of code, using a small amount of RAM and taking a small number of cycles. There is some ROM/ performance trade-off. The round transformation is parallel by design, an important advantage in future processors and dedicated hardware. As the cipher does not make use of arithmetic operations, it has no bias towards bigor little endian processor architectures.

Simplicity of Design: The cipher is fully self-supporting. It does not make use of another cryptographic component, S-boxes lent from well-reputed ciphers, bits obtained from Rand tables, digits of p or any other such jokes. The cipher does not base its security or part of it on obscure and not well understood interactions between arithmetic operations. The tight cipher design does not leave enough room to hide a trapdoor. Variable block length: Although the number of rounds of Rijndael is fixed in the specification, it can be modified as a parameter in case of security problems.

5.7 Limitations The limitations of the cipher have to do with its inverse:
The inverse cipher is less suited to be implemented on a smart card than the cipher itself: it takes more code and cycles. (Still, compared with other ciphers, even the inverse is very fast) In software, the cipher and its inverse make use of different code and/or tables. In hardware, the inverse cipher can only partially re-use the circuitry that implements the cipher. This algorithm is less efficient then Rijndael algorithm.

lviii

5.8 Summery: This is the whole description of our proposed system. We have compared the efficiency
for various types of operation in the next chapter for our proposed system and Rjndael proposed system.

lix

Chapter 6

Simulation result and conclusion

6.1 Introduction

We

have already described Rijndael proposed Encryption scheme for Advanced Encryption Standard (AES) and our proposed encryption scheme. In this chapter we give

the simulation result of time comparison between the original Rijndael implementation on 128bits block size having 128 bits key and our proposed algorithm which operate on 200 bits block size having 200 bits key size. We conclude with the references and the list of annexes.

6.2 Simulation
The increment of bit size in a packet increases the amount of time to encrypt the packet. Our proposed algorithm will run once to encrypt the whole data whereas Rijndael algorithm has to run two times to encrypt the data if the packet size is 200bits long. In a common sense it seems that our proposed algorithm is more efficient. But actually it is less efficient. The difference of the efficiency is very negligible. But our proposed cipher is much efficient than saffer+, RC5. A comparison of various types of Encryption and Decryption algorithm is given in [PCAS99]. The simulated result is given below.

Tim e require to encrypt w hole packet by using Rijndael 128 bit block ciper Required time 200 150 100 50 0 1 2 3 4 5 6 7 8 9 10 Num ber of bits.( 1 unit = 200 bit)

Time require to encrypt whole packet by using our 200 bit proposed algorithm Required time 300 200 100 0 1 2 3 4 5 6 7 8 9 10

Number of bits ( 1 unit = 200 bis )

lx

Tim e require to decrypt w hole packet by using Rijndael 128 bit block Required time 300 200 100 0 1 2 3 4 5 6 7 8 9 10 Num ber of bits( 1 unit = 200 bits)

Tim e require to decrypt w hole packet by using our 200 bit proposed algorithm Required time 400 300 200 100 0 1 2 3 4 5 6 7 8 9 10 Num ber of bits ( 1 unit = 200 bits )

Fig 6.1: Timing comparison of both our proposed syste and Rijndael scheme

6.3 Conclusion

Though

there is some difference in efficiency between our proposed algorithm and Rijndael, it is negligible. If any user requires the security high enough, then he can use our proposed algorithm. But if the efficiency is considered first then the user must use the Rijndael algorithm. And we want to claim that if the block size is increase by increasing the matrix order then there is degradation in efficiency. As we increase the key size as well as the block size the security has enhanced.

6.4 Proposal for Future work

In [MJDK], they have examined the possibility of first encrypting a data stream and then compressing it, where the compressor does not have knowledge of the encryption key. The encrypted data can be compressed using distributed source coding principle [SPKR99], because the key will be available at the decoder. They have studied both the compression efficiency and the cryptographic aspect of this problem. Their principal contribution is the observation that the problem of compressing encrypted data is a special case of the source coding with side information problem. As they use an encryption algorithm which may be of any type and as our algorithm increase the security, we like to proposed that the future work may be of using our proposed algorithm before data compression.

lxi

Appendix A

Polynomial with coefficient in GF(28)

A.1

Introduction

In section 3.6, we discussed polynomial arithmetic in which the coefficients are in Zp, and the polynomials are defined modulo a polynomial M(x) whose highest power is some integer n. In this case, additional and multiplication of coefficients occurred within the field Zp; that is, addition and multiplication were performed modulo p.
2
3 A.2 Rule of Addition and Multiplication

The AES document defined polynomial arithmetic for polynomials of degree 3 or less with coefficients in GF(28). The following rules apply:
1. Addition is performed by adding corresponding coefficients in GF(28). As was pointed out Section 4.5, if we treat the elements of GF(28) as 8 bit strings, then addition is equivalent to the XOR operation. So if we have

Then a(x) + b(x) = (a3 b3 ) x3 + (a2 b2 ) x2 + (a1 b1 ) x + (a0 b0 )

2. Multiplication is performed as in ordinary polynomial multiplication, with two refinements: a. Coefficients are multiplied in GF(28). b. The resulting polynomial is reduced mod(x4 +1). When need to keep straight which polynomial we are taking about. Recall from Section 4.6 that each element of GF(28) is a polynomial of degree 7 or less with binary coefficients of the corresponding polynomial. For the sets defined in this section, we are defining a polynomial ring in which each element of this ring is a polynomial of degree 3 or less with coefficients in GF(28), and multiplication is carried out modulo a polynomial of degree 4. Equivalently, each element of this ring can be viewed as a 4-byte values are elements of GF(28) that correspond to the 8-bit coefficients of the corresponding polynomial. We denote the modular product of a(x) and b(x) by a(x) b(x). To compute d(x)=a(x) b(x), the first step is to perform a multiplication without the modulo operation and to collect coefficients of like powers. Let us express this as c(x) = a(x) * b(x) Then

lxii

The final step is to perform the modulo operation: d(x) = c(x) mod (x4 + 1) That is, d(x) must satisfy the equation c(x) = [(x4 + 1) x q(x)] Such that the degree of d(x) is 3 or less. A particular technique for performing multiplication over this polynomial ring is based on the observation that xi mod (x4 + 1) = xi mod 4 ------------------------A(2) If we now combine Equation A(1) and A(2), we end up with d(x) = c(x) mod (x4 +1) = [c 6 x2 + c5 x + c4 + c3x3 + c2x2 + c1x + c0 ] mod (x4 + 1) = c3 x3 + ( c2 c6 ) x2 + (c1 c5 ) x + (c0 c4 ) d(x)

Expanding the ci coefficients, we have the following equations for the coefficients of d(x):

This can be written in matrix form:

lxiii

3.1 A.3. MixColumn Transformation

In the discussion of MixColumn, it was stated that there were two equivalent ways of defining the transformation. The first was is the matrix multiplication shown previous is repeated here:

The second method is treat each column of state as a four term polynomial with coefficients in GF(28). Each column is multiplied modulo (x4 + 1) by the fixed polynomial a(x), given by a(x) = {03} x3 + {01} x2 + {01} x + {02} Here a3 = {03}; a2 = {01}; a1 = {01}; a0 = {02}

3.2 A.4.
We have

Multiplication by x
c(x) = x c(x) = x b(x)

Consider the multiplication of a polynomial in the ring by x:

b(x) = [x x (b3 x3 + b2x2 +b1x1 + b0) mod (x4 + 1) = (b3x4 + b2x3 + b1x2 + b0x) mod (x4 + 1) = b2x3 + b1x2 + b0x + b3

Thus, multiplication by x corresponds to a 1-byte circular left shift of the 4 bytes in the word representing the polynomial. If we represent the polynomial as a 4-byte column vector, then we have

lxiv

References

[1] Joan Daemen and Vincent Rijmen,AES submission document on Rijndael,June 1998.

[2][Rijn99]Joan Daemen and Vincent Rijmen, AES submission document on Rijndael, Version 2,September 1999.http://csrc.nist.gov/CryptoToolkit/aes/rijndael/Rijndael.pdf [3] FIPS PUB 197, Advanced Encryption Standard (AES), National Institute of Standards and Technology, U.S. Department of Commerce, November 2001. http://csrc.nist.gov/publications/fips/fips197/fips-197.pdf [4] Joan Daemen and Vincent Rijmen, The Design of Rijndael, AES - The Advanced Encryption Standard, Springer-Verlag 2002 (238 pp.) [5] [DaKnRi97] J. Daemen, L.R. Knudsen and V. Rijmen, "The block cipher Square," Fast Software Encryption, LNCS 1267, E. Biham, Ed., Springer-Verlag, 1997, pp. 149-165. Also available as http://www.esat.kuleuven.ac.be/rijmen/square/fse.ps.gz. [6] [DaCl98] J. Daemen and C. Clapp, Fast hashing and stream Encryption with PANAMA, Fast Software Encryption, LNCS 1372, S.Vaudenay, Ed., Springer-Verlag, 1998,pp. 60-74. [7] [KeScWa96] J. Kelsey, B. Schneier and D. Wagner, "Key-schedule cryptanalysis of IDEA, GDES, GOST, SAFER, and Triple-DES," Advances in Cryptology, Proceedings Crypto '96,LNCS 1109, N. Koblitz, Ed., Springer-Verlag, 1996, pp. 237-252. [8][PCAS99]Bruce Schneier, John Kelsey, Doug Wagner, Chris hall, Niels Ferguson Performance Comparison of the AES Submission [9][CNSPP03]Willam Staling Cryptography and network security-principle and practice [10][MJDK]Mark Johnson, David Wanger, Kannan Ramchandran On compressing

lxv

Encrypted Data Without The Encryption Key. [11][SPKR99]S.S. Pradhan and K. Ramchandran,Distributed Source Coding Using Syndromes (DISCUS):Design and Construction, in Proceeding of the Data Compression Conference(DCC), (Snowbird,UT),March 99 [12][BS96] B. Schneier, applied cryptography. New York: Wiley,1999. [13][AZC2002] D. Liveris, Z. Xiong, and C.N. Georghiades,Compression of Binery Sources with Side. Information Using Low-Density Parity-Check Codes, in IEEE communication Letters,2002. [14][LiNi86] R. Lidl and H. Niederreiter, Introduction to finite fields and their applications,Cambridge University Press, 1986.

lxvi