Rep

ELLIPTICAL CURVE CRYPTOGRAPHY CS 708 Seminar

MEENU ELSA VARGHESE (Roll No. 05086) B. Tech. Computer Science & Engineering

College of Engineering Kottarakkara Kollam 691 531 Ph: +91.474.2453300 http://www.cek.ihrd.ac.in [email protected]

Certificate

This is to certify that this report titled ELLIPTICAL CURVE CRYPTOGRAPHY is a bonafide record of the CS 708 Seminar work done by Miss.MEENU ELSA VARGHESE, Reg No. 10264041, Seventh Semester B. Tech. Computer Science & Engineering student, under our guidance and supervision, in partial fulfillment of the requirements for the award of the degree, B. Tech. Computer Science and Engineering of Cochin University of Science & Technology.

October 16, 2008

Guide

Coordinator & Dept. Head

Miss.Geetha Raj R Lecturer Dept. of Computer Science & Engg.

Mr.Ahammed Siraj K K Asst. Professor Dept. of Computer Science & Engg.

Acknowledgments I express my whole hearted thanks to our respected principal Dr.Jacob Thomas, our seminar coordinator Mr.Ahammed Siraj K K,Head of the Department, for making my seminar successful. I wish to express my sincere thanks to my guide Miss.Geetha Raj R,Lecturer in computer science Department , for providing valuable help and support necessary for my seminar. I thank all faculty members of computer science engineering department in College of Engineering, Kottarakara for their co-operation in completing my seminar. My sincere thanks to all those well wishers and friends who have helped me during the course of the seminar work and have made it a great success. Above all I would like to acknowledge with thanks ”THE LORD ALMIGHTY”,the foundation of all wisdom who have been wonderfully guiding me step by step.

MEENU ELSA VARGHESE

Abstract Elliptical curve cryptography is said to be ideal for resource constrained systems because it provides more security per bit than other types of assymmetric cryptography.Elliptical curve cryptography or ECC was invented by Neil Koblitz and by Victor Miller in 1986.The principles of ECC can be used to adapt many cryptographic algorithms such as Diffe-Hellman or ElGamal.ECC offers considerably greater security for a given key size. ECC is an approach,a set of algorithm for key generation,encryption and decryption,to doing assymmetric cryptography.ECC offers considerably symmetric cryptography.ECC is emergency as an attractive public key cryptosystem for mobile and wireless environments.Elliptic curve cryptography works with points on a curve.The security of this type of public key cryptography depends on the elliptic curve discrete logarithm problem.Public key cryptography system are usually based on the assumption that are particular mathematical operation is easy to do,but difficult to undo unless we know some particular secret. The main advantage of ECC is that the keys can be much smaller. Recommended key sizes are in the order of 160 bits.As we said public key schemes are often used to set up private keys for encryption.Because hackers will attack the weakest link,it’s necessary to match the strength of the private key used with that of the public or assymmetric key.ECC is a public key system that is increasingly being used by organization.It uses smaller key lengths than those used by older schemes to achieve the same given security level.

i

Contents 1 INTRODUCTION

1

2 CRYPTOGRAPHY

3

3 BASICS OF ELLIPTICAL CURVE CRYPTOGRAPHY (ECC). 6 4 ASYMMETRIC CRYPTOGRAPHIC OPERATIONS IN ECC 7 5 PRINCIPLES AND OPERATION OF ECC 5.1 ELLIPTIC CURVES . . . . . . . . . . . . . . . . . . . 5.2 THE ELLIPTIC CURVE DISCRETE LOGARITHM PROBLEM . . . . . . . . . . . . . . . . . . . . . . . .

10 10

6 DIFFIE-HELLMAN KEY EXCHANGE

19

14

7 APPLICATIONS OF ELLIPTICAL CURVE CRYPTOGRAPHY 26 8 ECC IN WIRELESS COMMUNICATION

29

9

32

ADVANTAGES OF ECC

10 ECC FOR PORTABLE DEVICES AND FOR THE FUTURE 34 11 CONCLUSION

37

REFERENCES

38

ii

1

INTRODUCTION

Cryptography is probably the most important aspect of security in communication and is becoming increasingly important as a basic building block for computer security. This is a method for securing data during transmission. An original message is known as the plain text, while the coded message is known as the cipher text. The process of converting the plain text to cipher text is known as enciphering or encryption; restoring the plain text from the cipher text is deciphering or decryption. The many schemes used for encryption constitute the area of study known as cryptography. Elliptic curve cryptography is one of the newer algorithms discovered to be able to do asymmetric encryption; that is an algorithm in which text can be encrypted by with one key, and decrypted with another key where someone with one key would not be able to calculate the other.Elliptic Curve Cryptography (ECC) is a public key cryptography. The mathematical operations of ECC is defined over the elliptic curve y2 = x3 + ax + b, where4a3 +27b2 !=0. Each value of the a and b gives a different elliptic curve. All points (x, y) which satisfies the above equation plus a point at infinity lies on the elliptic curve.In public key cryptography each user or the device taking part in the communication generally have a pair of keys, a public key and a private key, and a set of operations associated with the keys to do the cryptographic operations. Only the particular user knows the private key whereas the public key is distributed to all users taking part in the communication. Some public key algorithm may require a set of predefined constants to be known by all the devices taking part in the communication. Domain parameters in ECC is an example of such constants. Public key cryptography, unlike private key cryptography, does not require any shared secret between the communicating parties but it is much slower than the private key cryptography. The public key is a point in the curve and the private key is a random number. The public key is obtained by multiplying the private key with the generator point G in the curve. The generator point G, the curve parameters a and b, together with few more constants constitutes the domain parameter of ECC. One main advantage of ECC is its small key size. A 160-bit key in ECC is considered to be as secured as 1024-bit key in RSA.

1

There are several slightly different versions of ECC, all of which rely on the (widely believed) difficulty of solving the discrete logarithm problem for the group of an elliptic curve over some finite field. The most popular finite fields for this are the integers modulo a prime number or a Galois field of size a power of two. Galois fields of size of power of some other prime have also been proposed but are cosecure data encryption is an essential part of modern communication technologies. It can help to prevent unauthorized access to sensitive data. This is particularly important for wireless networks. In general, symmetric encryption algorithms are used to obtain high data rates. These algorithms use identical keys to encrypt and decrypt data. One big issue with using symmetric algorithms is the key exchange problem. Both communication parties must exchange the key and ensure that the key remains secret. It is usually inconvenient and expensive to find a secure channel for the key exchange. These problems are solved by asymmetric encryption algorithms. They replace the single shared secret key with a pair of mathematically related keys: one Public Key that can be made publicly available and one secret Private Key. All asymmetric algorithms have in common that they rely on the special properties of one-way functions. In general it is simple to calculate a one-way function, but without additional information its nearly impossible to calculate the inverse function. Message-recovery schemes provide the most bandwidth-efficient signatures possible. With digital postal marks signature size is very important, because the size of the signature which is attached to the message to ensure the authentication of the source affects the size of the mark. In recent years, some new kinds of wireless communications like wireless sensor network and adhoc are also received lots attentions. The rapid development of wireless communication brings us some new questions. Security is an important one of these questions.The security of communication focus on the key agreement and derivation, digital signature, encryption,and so on. The wireless communication is different from traditional wired communication.

2

2

CRYPTOGRAPHY

Cryptography is probably the most important aspect of security in communication and is becoming increasingly important as a basic building block for computer security. This is a method for securing data during transmission. An original message is known as the plain text, while the coded message is known as the cipher text. The process of converting the plain text to cipher text is known as enciphering or encryption; restoring the plain text from the cipher text is deciphering or decryption. The many schemes used for encryption constitute the area of study known as cryptography. Such a scheme is known as a cryptographic system or a cipher. Techniques used for deciphering message without any knowledge of the enciphering details fall into the area of cryptanalysis. Cryptanalysis is what the layperson calls breaking the code. The area of cryptography and cryptanalysis together are called cryptology. Encryption is done using encryption algorithms and keys. As the encryption algorithms and keys change the generated cipher text also changes. Based on the keys used for encryption and decryption there are two types of cryptography. 1. Symmetric key cryptography. 2. Public key cryptography. 1. SYMMETRIC KEY CRYPTOGRAPHY Symmetric encryption is a form of cryptosystem in which encryption and decryption are performed using the same key. It is also known as conventional encryption. Symmetric encryption transforms plaintext into ciphertext using a secret key and encryption algorithm. Using the same key and a decryption algorithm, the plaintext is recovered from the ciphertext. A symmetric encryption scheme has five ingredients. Plaintext: This is the original intelligible message or data that is fed into the algorithm as input. Encryption algorithm: The encryption algorithm performs various substitutions and transformations on the plaintext. Secret key: The secret key is also input to the encryption algorithm. The key is a value independent of the plaintext and of the algorithm. The algorithm will produce a different output depending on the specific key being used at the time. The exact substitutions and transformations performed by the algorithm depend on the key.

3

Ciphertext:this is the scrambled message produced as output.It depends on the plaintext and the secret key.For a given message two different keys will produce two different ciphertext.The ciphertext is an apparently random stream of data and ,as it stands,is unintelligible . Decryption algorithm:This is essentially an encryption algorithm run in reverse.It takes the ciphertext secret key and produces the original plaintext.

Figure 1: block diagram of crytography AN EXAMPLE OF SYMMETRIC KEY CRYPTOGRAPHY ∗Alice and Bob agree on encryption method and a key ∗Alice encrypts the message with the key and sends it to Bob ∗Bob uses the same key to decrypt the message

4

Figure 2: Example of symmetric key cryptography

2. PUBLIC KEY CRYPTOGRAPHY This is also called asymmetric encryption. This is a form of cryptosystem in which encryption decryption are performed using the different keys-one a public key and one a private key. Asymmetric encryption transforms plaintext into ciphertext using a one of two keys and encryption algorithms. Using the paired key and a decryption algorithm, the plaintext is recovered from the ciphertext. Asymmetric encryption can be used for confidentiality, authentication or both. A public key encryption scheme has six ingredients: * Plaintext: This is the readable message or data that is fed into the algorithm as input. *Encryption algorithm: It performs various transformations on the plain text. *Public and private keys: This is a pair of keys that have been selected so that if one is used for encryption, other is used for decryption. The exact transformations performed by the algorithm depend on the public or private key that is provided as input. *Ciphertext: This is the scrambled message produced as output .It depends on the plaintext and key for a given message, two different keys will produce two different cipher texts. *Decryption algorithm: This algorithm accepts the ciphertext and the matching key and produces the original text.

5

3 BASICS OF ELLIPTICAL CURVE CRYPTOGRAPHY (ECC). ECC offers considerably greater security for a given key size. The smaller key size also makes possible much more compact implementations for a given level of security, which means faster cryptographic operations, running on smaller chips or more compact software. This means less heat production and less power consumption all of which is of particular advantage in constrained devices, but of some advantage anywhere. There are extremely efficient, compact hardware implementations available for ECC exponentiation operations, offering potential reductions in implementation footprint even beyond those due to the smaller key length alone. In short: asymmetric cryptography is demanding.

6

4 ASYMMETRIC CRYPTOGRAPHIC OPERATIONS IN ECC ECC is an approach a set of algorithms for key generation, encryption and decryption to doing asymmetric cryptography.Asymmetric cryptographic algorithms have the property that you do not use a single key as in symmetric cryptographic algorithms but a key pair. One of the keys (the public key) is used for encryption, and its corresponding private key must be used for decryption. The critical feature of asymmetric cryptography, which makes it useful, is this key pair and more specifically, a particular feature of the key pair: the fact that one of the keys cannot be obtained from the other. Authentication With Asymmetric Cryptography The core technology behind digital signatures and certificates is asymmetric authentication methods we normally speak of a private key (in the possession of the entity wishing to prove its identity) and the public key (in the possession of anyone who wishes to verify the identity of the entity possessing the private key). You may, with the public key, verify that an entity has knowledge of the private key but you cannot derive the private key from the public. This is the critical feature of asymmetric cryptographic schemes that makes them so useful. This property is useful for a number of things:greatly simplifies key exchange,and it solves one critical problem symmetric cryptography cannot solve that is the problem of guaranteeing unique authentication and non-repudiation.In Symmetric hashing/authentication methods,there is only one key, and both parties in the exchange use it both for authentication and for signature generation have the distinct disadvantage that they do not, on their own, offer any way to distinguish which party to the exchange signed a given message. If both or all parties must know the key, based on cryptography alone, you cannot distinguish which signed any given message, because any of them could have. In asymmetric authentication schemes, only one party knows the private key, with which the message is signed. Any number may know the public key. Since the private key cannot be derived from the public, the signature serves as a unique identifier. If the message verifies as having been signed by the person with knowledge of the private key, we can narrow down who sent the message to one. But any number of people may have knowledge of the public key, and all of them can therefore verify the identity of the sender.

7

ASSYMETRIC CRYPTOGRAPHY IN DIGITAL SIGNATURES AND CERTIFICATES Digital signatures and certificates are particularly common applications of authentication with asymmetric cryptography. A digital signature is a transform performed on a message using the private key, whose integrity may be verified with the public key.

Figure 3: A digital signature Again, the unique properties of asymmetric cryptography make it particularly useful for generating digital signatures. The correct signature may only be generated with the private key. Knowledge of the public key is only useful for verifying the signature. Any number of people may have knowledge of the public key for verification purposes, without compromising the private key. Since only one entity knows the private key, the private key serves as proof of the sending party’s identity, and guarantees the integrity of messages they send. A digital certificate is a piece of information which is digitally signed by a trusted third party, or certificate authority (CA), and which contains critical identification information, vouching for the identity of an entity. Digital certificates often themselves contain a public key corresponding to the private key the entity itself uses to prove its identitythe well-known web server certificates are examples of this type. ENCRYPTION USING ASYMMETRIC CRYPTOGRAPHY Asymmetric encryption schemes are used in a variety of applications. Probably the most visible, well-known application is in encrypted email, in peer-to-peer ’keying’ schemes such as Pretty Good Privacy (PGP). In asymmetric encryption schemes, the public key is used for encrypting messages; these messages, once encrypted, can only be decrypted with the private key. So the recipient publishes or distributes the public key corresponding to a private key of which

8

Figure 4: A certificate is made up of a server URL and a server public key

only they have knowledge. Anyone wishing to communicate securely with the holder of the private key encrypts his or her message using the public key. Only the recipient may decrypt and use the message; other holders of the public key cannot. This feature of asymmetric cryptosystems greatly simplifies key exchange. In a large network of N communicating entities, if it is fully meshed, maintaining unique symmetric keys for each communicating pair of entities would require the management of (nxn-1) 2 keys. Using asymmetric cryptography, this quantity can be reduced to N key pairs. In a group of 1,000 users, it’s the difference between managing 1,000 key pairs or 499,500 keys.

9

5 PRINCIPLES AND OPERATION OF ECC Elliptic Curve Cryptography is a relative of discrete logarithm cryptography. The DL system, as described above, relies upon the difficulty of the discrete logarithm problem a logarithm problem calculated within the multiplicative group of a finite field to frustrate attempts to use the public key to compromise the private one.ECC uses groups and a logarithm problem too.ECC also offers, however, is a difference in the method by which the group is defined how the elements of the group are defined, and how the fundamental operations on them are defined.It’s the difference in the way the group is defined both the numbers in the set and the definitions of the arithmetic operations used to manipulate them that give ECC its more rapid increase in security as key length increases.

5.1

ELLIPTIC CURVES

The way that the elliptic curve operations are defined is what gives ECC its higher security at smaller key sizes.An elliptic curve is defined in a standard, two dimensional x,y Cartesian coordinate system by an equation of the form:y 2 = x3 + ax + b The graphs turns out to be gently looping lines of various forms.

Figure 5: an elliptic curve In elliptic curve cryptosystems, the elliptic curve is used to define

10

the members of the set over which the group is calculated, as well as the operations between them which define how math works in the group.It’s done as follows: imagine a graph labeled along both axes with the numbers of a large prime field. That is to say: a square graph, p x p in size, where p is a very large prime number. Fp is the field of integers modulo p, and consists of all the integers from 0 to p-1.Now the prime numbers actually employed in practical ECC implementations are quite large, so it’s difficult to visualize this graph if you use the real kinds of numbers used. But as an exercise, you can imagine a more comprehensible prime such as 17. So you’d be looking at a graph 17x17 units in size. Now if you define an elliptic curve an equation of the form given above so that there are points (x, y) on the curve that satisfy the condition that both x and y are members of the prime field, you have implicitly created a group from the set of integer points on the curve; it is a subset of all the points in the p by p matrix created when you drew the graph specifically the ones the curve passes directly through.Note that unlike the groups used in Diffie Hellman, the elements of the set aren’t integers, but points. But the system that will result is still going to be, in most senses, the same, familiar arithmetic system as those discussed above. It contains a set of elements (points, in this case), and when you add one point to another, or subtract one from another, there are rules that say what point in the set you wind up at when you do so just as for the integers in the groups used in Diffie Hellman. And these rules still follow many of the familiar rules for the arithmetic you already know. POINT MULTIPLICATION The dominant operation in ECC cryptographic schemes is point multiplication. This is the operation which is the key to the use of elliptic curves for asymmetric cryptography the critical operation which is itself fairly simple, but whose inverse (the elliptic curve discrete logarithm problem defined below) is very difficult. ECC arranges itself so that when you wish to perform an operation the cryptosystem should make easy encrypting a message with the public key, decrypting it with the private key the operation you are performing is point multiplication.Point multiplication is simply calculating kP, where k is an integer and P is a point on the elliptic curve defined in the prime field. In terms of the addition operation we defined above, and the corresponding diagram, we can see how the following would look: take a

11

Figure 6: Eliptical curve cryptography

point, add it to itself (doubling). Then take the result, and the original point, and add them together again, using the chord and tangent rule. Then take that result, and the original point again, and use the chord and tangent rule yet again. And so on doing one doubling, and k-2 chord and tangent additions, until you’ve added P to itself k-1 times, giving kP.Now if the only way of doing this were in fact to repeat those precise operations finding the points P, 2P, 3P, and so on up to kP elliptic curves would be useless for cryptography, since the operation which searches for k given only P and kP (see the elliptic curve discrete logarithm problem, below) would be no harder than doing this. You could thus search for k from kP as quickly as you could calculate kP directly given p and k. However, there are shortcuts for point multiplication. Given the known shape of the curve, there are in fact several algorithms available which run in considerably less time

12

than would such a stepwise operation. Which of them you choose to use depends on a number of factors including which calculations you might be able to do ahead of time (which is practical for some cryptographic protocol purposes, in which P is known ahead of time), how much RAM you can set aside for lookup tables, and that sort of thing. None of the operations is exactly what you’d call trivial. But all of them are vastly easier than doing it by stepwise addition easier by many orders of magnitude. And they also run in nearconstant time for a given field size, regardless of what k and P you feed them as input. Some of the fastest working are in the NIST P192 curve, defined using the prime 2192 -264 +1. Here, you are able to get kP in the equivalent of 38 addition and 192 doubling operations, when counting only those which are usable even when P isn’t known ahead of time.You can do better still, in fact, in hardware implementations, in fields of order 2m . In these fields the fields called binary fields, or characteristic two finite fields hardware implementations that take advantages of opportunities for parallel processing, multiplication has been accelerated.Now these still aren’t trivial operations. But the important thing is this: compared to what the attacker has to do to get k back from kP, it’s nothing. Which brings us to the inverse operation.

13

5.2 THE ELLIPTIC CURVE DISCRETE LOGARITHM PROBLEM The inverse operation to point multiplication finding a log in a group defined on an elliptic curve over a prime field is defined as follows: given points Q and P, find the integer k such that Q=kP.This is the elliptic curve discrete logarithm problem and this is the inverse operation in the cryptosystem the one you effectively have to perform to get the plaintext back from the ciphertext, given only the public key.Now naively the obvious, certain way of finding k would be to perform repeated addition operations stepping through P, 2P, 3P, and so on, until you find kP. You’d start by doubling P, then adding P to 2P finding 3P, then 3P to P finding 4P and so on. This is the brute force method. The trouble with this is if you use a large enough prime field, the number of possible values for k becomes inconveniently large. So inconveniently large that it’s quite practical to create a sufficiently large prime field that searching through the possible values of k would take all the processor time currently available on the planet thousands of years.In the case of the NIST-defined P192 curve used as an example above, you’d have to do (on average) a doubling followed by on the order of 3x1057 additions. In the worst case, you’d have to do twice as many additions. It is probably unnecessary at this point to point out that 3x1057 is really a very, very large number. And a lot larger than the few hundreds of operations we needed to do the multiplication in the first place. This may sound unfair. And it is. It’s so grossly unfair, in fact, that you can, conveniently, do those multiplication operations in the rather limited processor of a tiny little handheld Blackberry unit or cellular phone operating on a 2.5 V battery in the course of routine communications, in a handshake at the beginning of a secure exchange, in considerably less than a second. And you can then quite safely send kP through the air where anyone can hear it. Indeed, you can publish kP and ask other people to use it as a component of the public key via which they communicate with you. And then that someone can take kP and go looking for k ,the value you’ve kept to yourself for use as your private key. And even if that someone isn’t restricted to a portable phone and less than a second even if that someone has a cave full of the latest massively parallel supercomputers and several years even then, they’re still not getting k back.That’s basically because 3x1057 divided by a few hundred adds up to an awfully large number. Though there is a bit more to the

14

story we have to get to now, to distinguish between how difficult it is to break ECC versus how difficult it is to break Diffie Hellman and RSA. POLLARD’S RHO ATTACK VERSUS INDEX CALCULUS As we noted earlier in this paper, there is a profound difference in the difficulty of the forward and inverse operations at the centre of all popular asymmetric schemes that is the soul of their usefulness. In RSA, it’s integer multiplication (forward) and factorization (inverse) that make the system work. In Diffie Hellman it’s discrete exponentiation (forward) and log (inverse). In ECC it’s point multiplication (forward) and the elliptic curve discrete logarithm problem (inverse).In all of these cases, it’s easy to see that the difficulty of the brute force approach to the inverse operation increases exponentially with the size of the key. Simply look at the number of values that must be tried; it doubles with each bit added to the key length.Now it turns out that for all of these cryptosystems, the brute force method isn’t quite the best you can do. You can, in fact, for Diffie Hellman and for RSA, try to retrieve the private key from the public (or the plaintext from the public key and the ciphertext) via the index calculus method. It’s difficulty grows subexpotentially with the key length.There are, in other words, shortcuts for doing the inverse operations, just as there was a shortcut for doing point multiplication.The difference is, the shortcuts for doing the inverse operations aren’t good shortcuts. It’s not as steep an increase as 2k, where k is the key length but a graph of the number of steps you must perform (on average) to find a key via the index calculus method versus the key size is still pretty steep.And that’s the point. That curve of number of steps versus key size and the index calculus attack it describes are what you have to keep in mind when you choose your key length in doing asymmetric cryptography. And that’s the calculation you’re actually doing when you choose the size of your RSA and your Diffie Hellman keys. How big do I have to make this so the best attack available index calculus, in this case is still too much trouble, for now and for some decades, assuming hardware continues to get faster at roughly the rate it has in the past? And that’s the estimate you’re counting on when you chose that 2048 bit key, and assume it’s good enough for the useful life of your product a figure taken as being 20 years and up, usually. Index calculus attacks are demanding enough that asymmetric cryptography is feasible despite them, provided the key is kept large enough.But ECC

15

can do better, and with smaller keys.And that’s because ECC cryptosystems aren’t vulnerable to index calculus attacks. Index calculus attacks rely on certain group properties not present in groups defined using elliptic curves.The best you can do for ECC is another attack a more general-purpose attack called Pollard’s rho attack. Pollard’s rho attack is a class of what are known as ’collision search’ attacks. They also do better than brute force. But they also get a lot harder a lot faster than do the index calculus attacks, as the field size increases.Pollard’s rho attack gets more difficult as (n)/2, where n is the group size (again, remember, itself exponential to the key size). The resulting curve a plot of the number of operations against key length is considerably steeper than is the curve for the index calculus attack described above. FINITE FIELDS AND DIFFIE HELMAN A finite field is a finite set of numbers and a set of rules for doing arithmetic with the numbers in that set.Usually, you define two operations in defining a field one rule for adding two of the set members together to arrive at a third set member and another operation which gives the rule for multiplication. Subtraction and division are defined in terms of addition and multiplication, respectively, and all other operations are defined in terms of these four. Essentially, therefore, you can view a finite field as a sort of self-contained, fully defined system of arithmetic. In many ways, the systems are very much like the normal system of arithmetic you’re used to working with the one you learned in grade school. There are however, some differences in the case of the finite fields used in cryptography. The two big differences are: 1. The number systems contain only integers, and 2. The number systems are finite in size The principal similarities are that you can add, subtract, divide, and multiply within them. All the basic operations are defined, and they work much the same as they do in normal arithmetic.There is one odd feature, however, about the math, which follows from the fact that the field is finite in size: the field, in essence, ’wraps around’. Since all operations on the set must have a result that maps back into the set, if you add two numbers and get a result that would take you outside the set, you reduce the number so it maps back into the set. The operation used to do this in many finite fields is modulo: you divide the number by the size of the set, and take the remainder as a trivial example, in a finite field of 7 elements, 2+13=1. This is because 2+13 = 15, and 15 mod 7 is 1. The members excluding 0 of a finite

16

field, together with the multiplication operation, form a group. This group is called the multiplicative group of a finite field. ELLIPTIC CURVE GROUP OPERATIONS The group operations the manipulations you perform to add one member to another, and subtract one from another are defined based on the curve. They work as follows: To add point a to point b, you draw a line between the two points. That line always intersects the curve at a third point point c.You then draw a vertical line through point c. That line will intersect the curve at a fourth point point d the reflection of c in the x-axis. Point d is taken as the result of summing points a and b.

Figure 7: addition a + b = d The double of point a is found as follows: draw a tangent line to the curve at a. The line will intersect the curve at a second point, b. Draw a vertical line through b. This intersects the curve at c, the reflection of b about the x-axis. c is the double of a. From these basic operations are derived all the remaining mathematical operations that can be performed in the field. Including the critical one for cryptographic purposes point multiplication and its very intractable inverse discrete log.

17

Figure 8: Doubling rule: 2a = c

6

DIFFIE-HELLMAN KEY EXCHANGE

Diffie-Hellman key exchange (D-H) is a cryptographic protocol that allows two parties that have no prior knowledge of each other to jointly establish a shared secret key over an insecure communications channel. This key can then be used to encrypt subsequent communications u The scheme was first published publicly by Whitfield Diffie and Martin Hellman in 1976, although it later emerged that it had been seperately invented a few years earlier within GCHQ, the British signals intelligence agency, by Malcolm J.Williamson but was kept classified. In 2002, Hellman suggested the algorithm be called Diffie-Hellman-Merkle key exchange in recognition of Ralph Merkles contribution to the invention of public key cryptography (Hellman, 2002).Although Diffie-Hellman key agreement itself is an anonymous (non-authenticated)key agreement protocol, it provides the basis for a variety of authenticated protocols, and is used to provide perfect forward secrecy in Transport Layer Securitys ephemeral modes. ANALOG OF DIFFIE HELLMAN KEY EXCHANGE Key exchange using elliptic curves can be done in the following manner.First pick a large integer q,which is either a prime number

18

p or a integer of the form 2m and elliptic curve parameters a and b. This defines the elliptic group of points Eq(a,b).Next,pick a base point G=(x1,y1) in Ep(a,b) whose order is a very large value n.The order n of a point G on an elliptic curve is the smallest positive integer n such that nG=O.Eq(a,b) and G are parameters of the cryptosystem known to all participants.A key exchange between user A and B can be accomplished as follows. 1.A select an integer nA less than n.This is As private key.A then generate a public key PA=nA X G;the public key is a point in Eq(a,b). 2.B similarly selects a private key nB and computes the public key PB. 3.A generates the secret key K=nA X PB.B generate the secret key K=nB X PA. The two calculations in step 3 produce the same result because nA X PB=nA X (nB X G)=nB X (nA X G)=nB X PA

Figure 9: ECC Diffie-Hellman Key Exchange

19

The simplest, and original, implementation of the protocol uses the Multiplicative group of integers modulo p, where p is prime and g is primitive root mod p. Here is an example of the protocol:

Figure 10: Chart showing implementation of protocol used in the above example 1.Alice and Bob agree to use a prime number p=23 and base g=5. 2.Alice chooses a secret integer a=6, then sends Bob (ga mod p) 56 mod23 = 8. 3.Bob chooses a secret integer b=15, then sends Alice (gb mod p) 515 mod 23=19. 4.Alice computes (gb mod p)a mod p 196 mod 23=2. 5.Bob computes (ga mod p)b mod p 815 mod 23 = 2. Both Alice and Bob have arrived at the same value, because gab and gba are equal. Note that only a, b and gab = gba are kept secret. All the other values are sent in the clear. Once Alice and Bob compute the shared secret they can use it as an encryption key, known only to them, for sending messages across the same open communications channel. Of course, much larger values of a, b, and p would be needed to make this example secure, since it is easy to try all the possible values of gab mod 23 (there will be, at most, 22 such values, even if a and b are large). If p were a prime of at least 300 digits, and a and b were at least 100 digits long, then even the best algorithms known today could not find a given only g, p, and gp ,ven using all of mankind’s computing power. The problem is known as the discrete logarithm problem. Note that g need not be large at all, and in practice is usually either 2 or 5. Here’s a more general description of the protocol:

20

1.Alice and Bob agree on a finite cyclic group G and a generating element g in G.(This is usually done long before the rest of the protocol; g is assumed to be known by all attackers.) We will write the group G multiplicatively. 2.Alice picks a random natural number a and sends ga to Bob. 3.Bob picks a random natural number b and sends gb to Alice. 4.Alice computes (gb )a . 5.Bob computes (ga )b . Both Alice and Bob are now in possession of the group element gab , which can serve as the shared secret key. The values of (gb )a and (ga )b are the same because groups are power associative.

21

CHART Here is a chart to help simplify who knows what. (Eve is an eavesdroppershe watches what is sent between Alice and Bob, but she does not alter the contents of their communications.) Let s = shared secret key.s = 2 Let a = Alice’s private key. a = 6 Let b = Bob’s private key. b = 15 Let g = public base. g=5 Let p = public (prime) number. p = 23

Figure 11: chart1

22

Figure 12: chart2

Note: It should be difficult for Alice to solve for Bob’s private key or for Bob to solve for Alice’s private key. If it isn’t difficult for Alice to solve for Bob’s private key (or vice versa), Eve may simply substitute her own private / public key pair, plug Bob’s public key into her private key, produce a fake shared secret key, and solve for Bob’s private key (and use that to solve for the shared secret key. Eve may attempt to choose a public / private key pair that will make it easy for her to solve for Bob’s private key).

23

Figure 13: chart3

SECURITY The protocol is considered secure against eavesdroppers if G and g are chosen properly. The eavesdropper (”Eve”) must solve the Diffie-Hellman problem to obtain gab . This is currently considered difficult. An efficient algorithm to solve the discrete logarithm problem would make it easy to compute a or b and solve the Diffie-Hellman problem, making this and many other public key cryptosystems insecure.The order of G should be prime or have a large prime factor to prevent use of the Pohlig-Hellman algorithm to obtain a or b. For this reason, a Sophie Germain prime q is sometimes used to calculate p=2q+1, called a safe prime, since the order of G is then only divisible by 2 and q. g is then sometimes chosen to generate the order q subgroup of G, rather than G, so that the Legendre symbol of ga never reveals the low order bit of a.If Alice and Bob use random number generators whose outputs are not completely random and can be predicted to some extent, then Eve’s task is much easier.The secret integers a and b are discarded at the end of the session. Therefore, Diffie-Hellman key exchange by itself trivially achieves perfect forward secrecy because no long-term private keying material exists to be disclosed.

24

AUTHENTICATION In the original description, the Diffie-Hellman exchange by itself does not provide authentication of the communicating parties and is thus vulnerable to a man-in-the-middle attack. A person in the middle may establish two distinct Diffie-Hellman key exchanges, one with Alice and the other with Bob, effectively masquerading as Alice to Bob, and vice versa, allowing the attacker to decrypt (and read or store) then re-encrypt the messages passed between them. A method to authenticate the communicating parties to each other is generally needed to prevent this type of attack. A variety of cryptographic authentication solutions incorporate a Diffie-Hellman exchange. When Alice and Bob have a public key infrastructure, they may digitally sign the agreed key, or ga and gb , as in MQV, STS and the IKE component of the IPsec protocol suite for securing Internet Protocol communications. When Alice and Bob share a password, they may use a password-authenticated key agreement form of Diffie-Hellman.

25

7

APPLICATIONS OF ELLIPTICAL CURVE CRYPTOGRAPHY

ECDSA is a very important application of ECC. As we know, digital signature is an important tool of authentication in E-business. It plays an important rule in data integrity, non-repudiation and anonymity. In some sense, digital signature is more efficient than the traditional way, especially for long messages or documents. Because the traditional way cant assure that each page is unchanged.Wireless communication is another application of ECC. DIGITAL SIGNATURE ALGORITHM(DSA) DSA is an asymmetric cryptographic algorithm that produces a digital signature in the form of a pair of large numbers, which is used in the Digital Signature Standard. Its main idea is to calculate one number by two different parties. If DSA is exploited, the message sender should provide as follows: ∗ Message digest, which can be regarded as a large ∗ A random number. ∗ Private key After a serial of operations, DSA outputs a signature that is composed of two numbers (r and s). The receiver also should provides several parameters as follows: ∗ Message digest, which is a number created according to the received messages. ∗ s, which comes from signature. ∗ The public key of the sender. After operations, if the result (v) is consistent with r (comes from sender), then the message is certificated. ECDSA ECDSA is the elliptic curve analogue of DSA. it is a rapid way of digital signature. It is implemented by ECC and MDF. ECDSA takes the two important advantages of ECC that are its small size and short certificate. For example, the security of 322-bit ECDSA is equal to the 1024-bit RSA, and the length of ECDSA certificate is 62 bytes, while that of RSA is 256 bytes,DSA is 168 bytes.ECDSA was accepted in 1999 as an ANSI standard and in 2000 as IEEE and NIST standards. As digital signatures become more and more important in theE-Business, the use of ECDSA will become all pervasive.

26

1. THE FLOW OF ECDSA

Figure 14: Flow of ECDSA 2. SOFTWARE IMPLEMENTATION OF ECDSA Java is an easy-to-use, object-oriented language that includes a set of libraries that facilitate cross-platform development. The following emphasizes on Java implementation scheme of ECDSA. So does C++. ∗ Import the Bouncy Castle Crypto API package: This package is an open source, lightweight cryptography package that supports a large number of cryptography algorithms and provides an implementation for DSA, RSA and ECC. It provides classes to retrieve the model and validate the signature, the statement is import org. bouncycastle. crypto. *; ∗ Import the Java core API packages, such as security package which contains classes related with security and signature, and util package related with stacks and so on.

27

import java. security. *; import java. util. *; ∗ Define the elliptical curve model: With the help of APIs , we can define a serial of indispensable parameters of a elliptic curve. ∗ Generate the random key pairs: by using the parameters, construct serial instants of EC*(EC* denote those instants whose name begin with EC)classes and call the methods such as init (),genertateKeyPairs (), etc. ∗ Encrypt the digest and retrieve the signature r and s: make use of ECDSASigUtil class and get a DSA signature (r and s) from a digest. ∗ Decrypt and validate signature reconstruct the public key according to the received message and call for the verified method. The wireless communication can be found in all fields of our life. And as the 3G become popular, more and more businesses will be done in the wireless way.

28

8 ECC IN WIRELESS COMMUNICATION The wireless communication can be found in all fields of our life. And as the 3G become popular, moreand more businesses will be done in the wireless way.The security of communication focus on the key agreement and derivation, digital signature, encryption, and so on. The wireless communication is different from traditional wired communication. Its bandwidth is less, and its terminal equipment always is mobile phones, PDAs, whose resource, power, and the capacity of computation all are limited. So, the traditional encryption way is difficult to be used in the wireless communication. We must find some new methods which fits the characteristic of the wireless environment. As we will see in the following, the elliptic curve cryptosystem (ECC) is a good choice.For the same level of security per best currently known attacks, elliptic curve based systems can be implemented with much smaller parameters, leading to significant performance advantages, which is very important in the wireless environment As analyzed before, in the wireless condition,the equipment’s recourse, power and compute capacity all are limited. So the encryption system in it must be low power and RAM consumption. But current the most popular algorithm RSA does not satisfy it. The ECC is more effective than RSA. There some companson between ECC and RSA. Table 2 shows the energy cost of RSA and ECDSA(a signature algorithm of ECC).From it we can clearly see that ECC has much better performance than RSA. The ECC can give a total solution for the security problems in the wireless communication, such as authentication, signature, key exchange. The encryption example in the section2 can also be used tosession key exchange. The ECDSA is the elliptic curve analogue of DSA. It is a very important one of ECC. The security of 322-bit ECDSA is equal to the 1024-bit RSA signature, and the length of ECDSA certification is 62 bytes, while that of RSA is 256 bytes, DSA is 168 bytes. In this protocol, Diffie-Hellmann’ scheme. ElGamal cryptosystem and ECDSA are applied to the ECC/UMTS authentication protocol for key exchange and for encryption. The ECDSA is used in the authentication protocol

29

Figure 15: Table for keysize ratio,energy cost of digital signature and key exchange

to form a certificate between the visiting location register and the mobile station. Ozkan Merdem improved Kerberos authentication protocol for wireless communication based elliptic curve cryptographic operations.Proposed protocol requires less bandwidth than other public key cryptography enabled Kerberos solutions. According to the paper, in the 32-bit Strong ARMI processor running at 206 IVMZ, Proposed protocol offers the strength of public key cryptography and costs only 68.7 ms extra load to standard Kerberos without using pre-computation tables for 160 bit curve andscalable architecture, whereas with customized curve library it costs 57.3 ms extra load for the same key length. Using pre-computation tables reduces these timings to 55.8 ms and 51.6 ms respectively.Many wireless standard and protocol have already introduced ECC in themselves. The IEEE 802.1 lb uses WEP to provide the security for the data frame. But the initial development of the WEP protocol had missed to address the key exchange mechanism as well as individual user authen-

30

tication .The ECC can give a solution for authentication.The ECC can give a solution for this. The WLAN Authentication and Privacy Infrastructure (WAPI) use 192/224/256-bit ECC to provide the data security as well as key exchange mechanism and mutual authentication. The Wireless Application Protocol (WAP) is key protocol of modem wireless intemet, and Wireless Transport Layer Security is to support the safe transport for the WAP. WTLS employs public key cryptosystems during certificate validation,authentication and session key exchange. Both ECC and RSA are suggested in the WTLS. But Albert Levi and Erkay Savas found that ECC performs better than its rival RSA cryptosystem in WTLS .The result of there experiment also shows that, some stronger ECC curves, which are not considered in WTLS standard, could be used in WTLS for high security application with an acceptable degradation in performance.In the Wireless Public Key Infrastructure (WPKI),the ECC is also introduced to implement the signature.

31

9

ADVANTAGES OF ECC

As a new generation of public key cryptosystem,ECC has advantages over RSA or some other commonly used public key cryptosystems. (a) THE HIGH SECURITY The purpose of any public key cryptosystem is to maintain the security and integrity of the resources, avoid the attack of any people, any event, etc. while the anti-attack performance of the algorithm assures its security. In 6th International Cryptography Conferences in Jan.2000, ECC as well as RSA were the only two algorithms that were recommended. Actually in the term of security, ECC provides the highest strength per bit among all the cryptosystems.The best solution to ECC is Pollard Rho solution;whose time complicacy is an exponent (n), and n is thebinary digits of k in equation.This means: the fewer bits can assure the higher security in ECC. It is reported that the 1024-bit RSA or DH has the equal security as 160 bit ECC. (b) THE SMALL KEY SIZE Undoubtedly, the longer the key is, the higher the security strength it has. But it adversely affect the running performance. In Apr. 2000, there was a research on the cost of cracking the different encrypted algorithms, which was done by the RSA lab. Table 1 displays its results. where ECC shows its advantage in the condition of considering both running performance and strength. For the same security level, the key size of ECC is much shorter RSAs. In other words, ECC provides a more secure cryptosystem for the same key length as RSA. Table 1 also shows what the attacker need is the larger memory rather than the more computers with the increasing of key size. That means when ECC is exploited, it needs smaller memory In addition to the above advantages, fast speed is another characteristic of ECC. As we know, RSA is based on large integer factorisation, all the process is rather complicated and strisct. Although ECC processes of creating private key is complicated, we can calculate public key very easily. Because if k is the private key, then the public key is k*P. Speed in the process of the decrypted and signature is rather

32

Figure 16: time spent on cracking all size keys

Figure 17: key size ratio faster. In the equivalent of security, the speed of exploiting 160-bit ECC is about 10 times faster than that of 1024-bit RSA or DSA. More and more communication processes are performed by small and mobile devices which are typically limited in their CPU, memory, battery and bandwidth resources. Special integrated circuits can help to disburden the general purpose CPU from exhausting cryptographic calculations. Often, traditional public-key algorithms can not offer satisfying solutions for this class of mobile devices. At this point, elliptic curve based algorithms are an attractive alternative to traditional methods.

33

10 ECC FOR PORTABLE DEVICES AND FOR THE FUTURE The fact that the security and practicality of a given asymmetric cryptosystems relies upon the difference in difficulty between doing a given operation and its inverse. The difference in difficulty between the forward and the inverse operation in a given system is a function of the key length in use, due to the fact that the difficulty of the forward and the inverse operations increase as very different functions of the key length; the inverse operations get harder faster. As you are forced to use longer key lengths to adjust to the greater processing power now available to attack the cryptosystem, even the ’legitimate’ forward operations get harder, and require greater resources (chip space and/or processor time), though by a lesser degree than do the inverse operations. ECC’s advantage is this: its inverse operation gets harder, faster, against increasing key length than do the inverse operations in Diffie Hellman and RSA. What this means is: as security requirements become more stringent, and as processing power gets cheaper and more available, ECC becomes the more practical system for use. And as security requirements become more demanding, and processors become more powerful, considerably more modest increases in key length are necessary, if you’re using the ECC cryptosystem to address the threat. This keeps ECC implementations smaller and more efficient than other implementations. ECC can use a considerably shorter key and offer the same level of security as other asymmetric algorithms using much larger ones. Moreover, the gulf between ECC and its competitors in terms of key size required for a given level of security becomes dramatically more pronounced, at higher levels of security. And this, in the end, is the reason ECC is a stronger option than the RSA and discrete logarithm systems for the future. And this, in the end, is why ECC is such an excellent choice for doing asymmetric cryptography in portable, necessarily constrained devices right now. As an example: as of this writing, a popular, recommended RSA key size for most applications is 2,048 bits. For equivalent security using ECC,

34

Figure 18: Equivalent key sizes for ECC and RSA you need a key of only 224 bits.The difference becomes more and more pronounced as security levels increase (and, as a corollary, as hardware gets faster, and the recommended key sizes must be increased). A 384 -bit ECC key matches a 7680-bit RSA key for security. The smaller ECC keys mean the cryptographic operations that must be performed by the communicating devices can be squeezed into considerably smaller hardware, that software applications may complete cryptographic operations with fewer processor cycles, and operations can be performed that much faster, while still guaranteeing equivalent security. This means, in turn, less heat, less power consumption, less real estate consumed on the printed circuit board, and software applications that run more rapidly and make lower memory demands. Leading in turn to more portable devices which run longer, and produce less heat.In short, if you’re trying to make your devices smaller and if you need to do asymmetric cryptography, you need ECC. If you’re trying to make them run longer on the same battery, and produce less heat, and you need asymmetric cryptography, you need ECC. And if you want an asymmetric cryptosystem that scales for the future, you want ECC. And if you just want the most elegant, most efficient asymmetric cryptosystem going, you want ECC. If you just want the most elegant, most efficient asymmetric cryptosystem going, you want ECC. The technical merits of ECC-based digital certificates make them an excellent choice for applications, now and in the future. The strength and small size provides numerous per-

35

formance and security benefits. Additionally, the longevity of the security is assured. In addition to the applications listed above, they also have a wide range of possible uses in other markets such as consumer and healthcarefor applications such as 2D bar codes, digital imaging and digital rights management. As the full effect of the U.S. Governments strategy for Crypto Modernization spreads throughout the government and into other industries, ECC-based digital certificate use will become more widespread.

36

11

CONCLUSION

For efficient implementation of ECC, it is important for the point multiplication algorithm and the underlying field arithmetic to be efficient. There are different methods for efficient implementation point multiplication and field arithmetic suited for different hardware configurations. Implementation of ECC using projective coordinates has shown considerable improvement in efficiency compared to the affine coordinate implementation. This improvement in efficiency is due to the elimination of multiplicative inverse operation in point addition and doubling that would otherwise cost considerable processor cycles. The elliptic curve cryptosystem has better performance than traditional cryptosystem with high speed,low consumption and resource consumption. So It is very suitable for the wireless enviroriment. But because of not all the wireless communication protocol have introduced ECC, and the ECC’s fast hardware implementation is also being researched , the use of ECC in wireless communication is more academic than in industry now. In past few years ECC has evolved from a fringe activity to a major challenger to popular RSA.Elliptic curve uses major advantages over traditional systems such as increased speed,less memory and smaller key size.Although doing group operations is slower for an ECC system than for RSA or other discrete log system of the same size,equal security can be provided by much smaller key length using ECC,to this extent that it can actually be faster than others. In addition,less storage,less power and less memory than other systems make it possible to implement cryptography in many special platforms such as wireless devices,laptop computers and smart cards.So do the situations where efficiency is important.

37

References [1] Lauter K. The advantages of elliptical curve cryptography for wireless security and wirelees communication. IEEE, 11(1):234–241, February 2004. [2] S.Patz Malhotra.K.Gardener. University of glamorgan ponty pridd. In The papers in networking,sensing and control, pages 128–137, May 2007. [3] William Stallings. Cryptography and network security. Pearson Prentice Hall, 4 edition, 2006.

38